Locally Consistent Parsing (局所一致分割)

この記事は文字列Advent Calendar 13日目の記事です。

　文字列Advent Calendar 12日目の文法圧縮と関連性の深いLocally Consistent Parsing (LCPR)についてです． 昨日が入門で申し訳ありませんが，いきなりかなり難しいことを書きます． 他のLCPRに関する日本語の解説は¹があります．当初は17日に書く予定でしたが，なるべく前から埋めた方がよいのと昨日の記事が文法圧縮入門ということで，本日に記事の日にちを変更しました．記法は文字列Advent Calendar 1日目の記事と同じです．難しすぎたり，ミスってたら申し訳ありません。。。

#Locally Consistent Parsing (LCPR)²とは?
　入力文字列 $\mathit{S}$ と入力整数 $\mathit{c}\ (\geq2)$ のLocally Conitsistent Parsing (LCPR)は文字列 $\mathit{S}$ を $\mathit{k}$ 個の重複のない部分文字列 $\mathit{S}_1\mathit{S}_2...\mathit{S_k}(\mathit{|S_i|}\in[\mathit{c,2c-1}]
(\mathit{i}\in[\mathit{1,k}]))$ に分割する文字列分割法であり，その分割は異なる位置に出現する同じ部分文字列の分割(parsing)が部分的(局所的(locally))に一致(consistent)するという特徴をもつ．具体的にはLCPRによる分割は $2$ つの異なる位置 $\mathit{i,j}$ に出現する同じ部分文字列 $\mathit{S}[\mathit{i,i+l}]$と $\mathit{S}[\mathit{j,j+l}]$ の左端と右端の分割のずれ
$\mathit{\gamma(c)}$ と $\mathit{\gamma'(c)}$ を除く，$\mathit{S}[\mathit{i+\gamma(c),i+l-\gamma'(c)}]$ と $\mathit{S}[\mathit{j+\gamma(c),j+l-\gamma'(c)}]$の部分(局所)の分割が一致することが保証される．LCPRは冒頭で述べた文法圧縮³や編集距離と編集距離の亜種の高速近似計算²⁴⁵に応用されています．

　ここから先は説明を簡単にするために，一般的な入力整数 $\mathit{c}$ に関するLCPRではなく， $\mathit{c}=2$ に固定した $2$ 文字か $3$ 文字の部分文字列で入力文字列 $\mathit{S}$ を分割し，かつ入力文字列 $\mathit{S}$ が $\mathit{aaaaaa}$ などの連続文字を含まないすなわち $\mathit{S}[\mathit{i-1}]\neq \mathit{S}[\mathit{i}](2 \geq \mathit{i}\geq \mathit{|S|})$ である場合のLCPRについて考えます⁶．

#LCPRの例と難しさ
　難しさを説明するために，先頭から単純に $2$ 文字ずつで区切るアルゴリズムを文字列
$\mathit{S=abracadabracadabra}$ に適用して見ますが，$\mathit{S=ab\ ra\ ca\ da\ br\ ac\ ad\ ab\ ra}$ のように，$\mathit{S}$ の位置 $1$ から始まる $\mathit{abracadabra}$ は$\ \mathit{ab\ ra\ ca\ da\ br\ a}$ となっていますが，
位置 $8$ から始まるのは $\mathit{a\ br\ ac\ ad\ ab\ ra}$ となり，ずれてしまいます．これを
$\mathit{S=ab\ ra\ ca\ dab\ ra\ ca\ dab\ ra}$ のように揃えるには過去に出現した部分文字列を記憶しておいてそれと揃える方法⁷もありますが，多くの領域が必要になってしまいます．

#高速かつ省領域なアルゴリズム
　そこで⁵などの高速かつ省領域に分割するLCPRを紹介します．$c=2$ に固定したとき，同じ部分文字列の左端と右端の分割のずれ $\mathit{\gamma}(\mathit{c}),\mathit{\gamma'}(\mathit{c})$ が$\mathit{O}(\mathit{\lg^* |S|})$($\mathit{\lg^* }$は反復対数)であることが保証されるアルゴリズムです⁵．本章では，まず，入力文字列　$\mathit{S}$ に対して，$\mathit{O}(\mathit{|S|\lg^* |S|})$ 時間・領域で計算可能なアルゴリズムを説明し，その後，$\mathit{O}(\mathit{|S|})$ 時間，$\mathit{O}((\mathit{\lg\lg |S|})^{\mathit{\lg^* |S|}})$ 領域で計算可能なアルゴリズムについて説明していきます．($\mathit{\lg^* |S|}$ は増加関数であり，$\mathit{|S|=}2^{65536}$ のとき，$\mathit{\lg^* |S|=}5$ であるため，実用的にはほぼ定数とみなせます．)

##O(S\lg^* S)時間・領域アルゴリズム
　紹介するLCPRは，まず，文字種類数 $\mathit{\sigma}$ の連続文字を含まない入力文字列 $\mathit
{S}$ から，Alphabet reduction (AR)という操作を行い，文字種類数 $\mathit{\lg \sigma}$ で長さ $\mathit{|S|}$の正の整数列 $\mathit{L_\mathrm{1}}$ を計算します．そして，そのARを再帰的に $\mathit{\lg^* |S|}$ 回繰り返して，文字種類数 $6$ で長さ $\mathit{|S|}$ の正の整数列 $\mathit{L_* }$計算し，その $\mathit{L_* }$の極大値に基づいて，$\mathit{S}$ の分割を決定します．

###Alphabet reduction (AR)
　ARでは文字列 $\mathit{S}$ の各文字を $2$ 進数で表現されているとみなします．各位置 $\mathit{i}\in [2,\mathit{|S|}]$ に対して，$\mathit{S}[\mathit{i}-1]$ と $\mathit{S}[\mathit{i}]$ を最下位ビットから見ていって初めて異なるビット位置 $\mathit{p}$ と $\mathit{S}[\mathit{i}]$ のその $\mathit{p}$ 番目のビット値 $\mathit{b}$ から $\mathit{L_\mathrm{1}}[\mathit{i}]=2\mathit{p+b}$ を計算します． 例えば下図の$\ \mathit{S}[2]=00001$ と $\mathit{S}[3]=10001$ から，$\mathit{p}=4,\mathit{b}=1$ より$\ \mathit{L_\mathrm{1}}[3]=9$となります．

　このARを再帰的に $\mathit{L_\mathrm{1}}$ から文字種類数 $\mathit{\lg \lg \sigma}$ で長さ $\mathit{|S|}$ の正の整数列 $\mathit{L_\mathrm{2}}$，$\mathit{L_\mathrm{2}}$から...と $\mathit{\lg^* |S|}$ 回繰り返すと文字種類数 $6$ の長さが $\mathit{|S|}$ の正の整数列 $\mathit{L_* }$ が計算できます．その $\mathit{L_* }[\mathit{i}]$ が極大 $\mathit{L_* }[ \mathit{i}-1]\leq \mathit{L_* }[ \mathit{i}]\geq$ $\mathit{L_* }[ \mathit{i}+1]$ であるときには，位置 $\mathit{i}$ をlandmarkとよび，$\mathit{S}[\mathit{i}-1]$ と $\mathit{S}[\mathit{i}]\mathit{S}[\mathit{i}+1]$ と $\mathit{S}[\mathit{i}+2]$ を分割する．各landmark $\mathit{i}$ から次のlandmark $\mathit{j}$ の間の $\mathit{S}[\mathit{i}+2,\mathit{j}-1]$ の分割は先頭から順に長さ $2$ で分割し，$\mathit{|S}[\mathit{i}+2,\mathit{j}-1]\mathit{|}$ が奇数のときは最後の分割の長さを $3$ にします．$\mathit{|S}[\mathit{i}+2,\mathit{j}-1]\mathit{|}=1$ のときは左側の分割に加え，左側が無いときには右側の分割に加えます．LCPRの例が下図です．

###計算量解析
　ARの $\mathit{p}$ は $\mathit{LSB}(\mathit{XOR}(\mathit{S}[\mathit{i}-1],\mathit{S}[\mathit{i}]))$⁸ と $\mathit{O}(1)$ 時間で計算でき，各 $\mathit{L_* }[\mathit{i}]$ の計算に $\mathit{O}( \mathit{\lg^* |S|})$ かかるため，$O(S\lg^* S)$時間・領域必要です．

###異なる位置に出現する同じ部分文字列の分割のずれる長さの保証
　同じ部分文字列の左端と右端の分割のずれ $\mathit{\gamma}(\mathit{c}),\mathit{\gamma'}(\mathit{c})$ は $\mathit{O}(\mathit{\lg^* |S|})$ であることが保証されます．まず $\mathit{L_\mathrm{1}}[\mathit{i}]$ の定義から，$\mathit{L_\mathrm{1}}$ の文字種類数は$\ \mathit{\lg\sigma}$ であり，$\mathit{S}[\mathit{i}-1]\neq \mathit{S}[\mathit{i}]\ (\mathit{i}\geq
\mathit{2})$ のとき，$\mathit{L_\mathrm{1}}[\mathit{i}-1]\neq \mathit{L_\mathrm{1}}[ \mathit{i}]\ (\mathit{i}\geq 2)$ です．また$\mathit{L_\mathrm{1}}[\mathit{i}]$ は $\mathit{S}[\mathit{i}-1]$ と $\mathit{S}[\mathit{i}]$ から計算されるため，$\mathit{S}$ 中の$\mathit{2}$ つの異なる位置 $\mathit{i,j}$ に出現する同じ部分文字列 $\mathit{S}[\mathit{i},\mathit{i+l}]$ と $\mathit{S}[\mathit{j},\mathit{j+l}]$ から計算される $\mathit{L_\mathrm{1}}[\mathit{i}+1,\mathit{i+l}]==\mathit{L_j}[\mathit{j}+1,\mathit{j+l]}$ であり，それを再帰的に繰り返すので $\mathit{L_* }[\mathit{i+\lg^* |S|,i+l}]==\mathit{L_* }[\mathit{j+\lg^* |S|,j+l}]$ になります．したがって，$\mathit{S}[\mathit{i,i+l}]$ と
$\mathit{S}[\mathit{j,j+l}]$ 上の区間 $\mathit{S}[\mathit{i+\lg^* S}+1,\mathit{i+l}]$ と $\mathit{S}[\mathit{j+\lg^* S}+1,\mathit{j+l}]$ に出現するlandmarkは同じになるため，その区間の最初のlandmarkから最後のlandmarkまでの分割は一致します． 文字種類数が $6$ であることと $\mathit{L_* }[\mathit{i}-1] \neq \mathit{L_* }[\mathit{i}] ( \mathit{i}\geq 2)$ よりlandmark（極大値）間の距離は高々 $10$ なので，$\mathit{S}[\mathit{i+\lg^* |S|}+11,\mathit{i+l-}10]$ と $\mathit{S}[\mathit{j+\lg^* |S|}+11,\mathit{j+l}-10]$の分割が一致することが保証されます．(このアルゴリズムは⁵などの簡単版であるため，⁵などはもう少しバウンドがよいです．)下図がここで述べていることになります．

##線形時間・領域アルゴリズム
上記のアルゴリズムで分割を決定するために重要なのは各位置 $\mathit{i}$ がladdnmarkかどうかを判定することであり，そこに $\mathit{O}(\mathit{\lg^* |S|})$ 時間かかってしまいます．　この計算を $\mathit{O}(1)$ 時間で行うには，まず，入力文字列 $\mathit{S}$ からARを再帰的に $2$ 回繰り返し，$\mathit{L_\mathrm{2}}$を計算します．$\mathit{L_* }[\mathit{i}]$ が極大 （位置$\ \mathit{i}$ がlandmarkになる）かどうかは $\mathit{L_\mathrm{2}}[\mathit{i-\lg^* |S|}+1,\mathit{i}+1]$ から計算されるため，$\mathit{L_\mathrm{2}}$ に出現しうる長さ $\mathit{\lg^* |S|}$ の数列の位置 $\mathit{\lg^* |S|}-1$ の数から計算される $\mathit{L_* }$ の値が極大かどうかを予め計算しておき，$\mathit{O}((\mathit{\lg\lg |S|})^{\mathit{\lg^* |S|}})$ のlook up tableに格納しておきます．そのlook up tableを用いると，$\mathit{L_\mathrm{2}}$ から位置 $\mathit{i}$ がlandmarkかどうかを $\mathit{O}(1)$ 時間で計算できるため，線形時間で計算可能です．

##線形時間・O((\lg\lg|S|)^{\lg^|S|})領域アルゴリズム
　位置 $\mathit{i}$ がlandmarkかどうかは，$\mathit{S}[\mathit{i-\lg^ |S|}-1,\mathit{i}+1]$ から計算されるため，上記の線形時間のアイデアと組み合わせると線形時間・$\mathit{O}((\mathit{\lg\lg |S|})^{\mathit{\lg^*|S|}})$領域で計算可能です．

#文法圧縮への応用
　分割された長さ $2$ の文字列 $\mathit{XY}$ からは $2$ 木 $\mathit{A\to XY}$ を構築し，長さ $3$ の文字列 $\mathit{WXY}$ からは $2$-$2$ 木 $\mathit{A_\mathrm{1}\to XY,A_\mathrm{2}\to WA_\mathrm{1}}$を構築する．新しくできた根の列を入力文字列 $\mathit{S}$ として，LCPRおよび木の構築を入力文字列 $\mathit{S}$ の長さが $1$ になるまで繰り返すことで，入力文字列 $\mathit{S}$ を導出する文法を構築可能である．この文法サイズはLZ77分解⁹の分解数を $\mathit{Z}$ とすると，$\mathit{O}(\mathit{Z\lg^* |S|\lg |S|})$ であることが保証される³．(LCPRによる同じ部分文字列の分割のズレが構築される構文木の各レベルで $\mathit{O}(\mathit{\lg^* |S|})$ であるため．)

#Open problem
分割のずれ$O(1)$，線形時間・look up table領域アルゴリズム　←解けそう．

1. 磯上　貞雄，城所　引泰，村上　登志男，久保山　哲二: 文字列の高速類似度計算・検索のための要素技術について ─ 系列分割手法 ─. ↩

2. Tugkan Batu, Süleyman Cenk Sahinalp:Locally Consistent Parsing and Applications to Approximate String Comparisons. Developments in Language Theory 2005: 22-35. (これはLCPRのsurvey論文でLCPRという言葉の初出の論文ではありません.) ↩ ↩²

3. Hiroshi Sakamoto, Shirou Maruyama, Takuya Kida, Shinichi Shimozono: A Space-Saving Approximation Algorithm for Grammar-Based Compression. IEICE Transactions 92-D(2): 158-165 (2009). ↩ ↩²

4. Tugkan Batu, Funda Ergün, Süleyman Cenk Sahinalp: Oblivious string embeddings and edit distance approximations. SODA 2006: 792-801. ↩

5. Graham Cormode, S. Muthukrishnan: The string edit distance matching problem with moves. ACM Trans. Algorithms 3(1): 2:1-2:19 (2007). ↩ ↩² ↩³ ↩⁴ ↩⁵

6. 連続文字列を含む場合も入力文字列に対して連長圧縮を施せば、同じ近似率・計算量で計算可能です． ↩

7. Artur Jez: A really simple approximation of smallest grammar. Theor. Comput. Sci. 616: 141-150 (2016) （正確にはLZ分解して、そのLZ分解の過去の出現と分割を一致させている） ↩

8. LSB（X）はXの最下位ビットが立っている場所を計算します． ハードウェア命令の__builtin_ctzll(bits)で$O(1)$で計算可能です． ↩

9. https://qiita.com/kgoto/items/53696f5d95919d158ad8 ↩