こんにちは。レトリバのリサーチャーの木村@big_wingです。

今回は業務で久しぶりに触れる機会があったこともあり、極大部分文字列について紹介したいと思います。極大部分文字列については、有志の方のブログやスライドが公開されています。私も今回久しぶりに極大部分文字列に触れるにあたってこれらの資料は大変参考になりました、ありがとうございます。特にshiba_yu36氏のブログに極大部分文字列の元論文と各種資料へのリンクがまとまっています。

極大部分文字列とは？
- 極大部分文字列の大雑把な定義
- 極大部分文字列を考えるモチベーション
極大部分文字列を求めるための準備
極大部分文字列の高速な求め方
まとめ

極大部分文字列とは？

まず極大部分文字列の大雑把なインフォーマルな定義と極大部分文字列を考えるモチベーションについて簡単に説明します。極大部分文字列の正確な定義は全ての部分文字列を考慮した文書分類を参照して下さい。

極大部分文字列の大雑把な定義

極大部分文字列の大雑把な定義は、入力の文字列の中で2回以上出現する部分文字列のうち、出現回数と出現場所が同一のもので長さが最長のものです。出現場所が同一の部分文字列を同値類としてまとめ、その中で最長の部分文字列を代表元としたものが極大部分文字列です。これだけだと全くわからないので具体例を見てみましょう。

以下具体例として入力の文字列 $T$ を $T=abracadabra$$ として説明していきます。ここで $T$ の最後の文字 $$$ は入力の文字列における辞書順で最小の文字とします。この例の場合、極大部分文字列は $\{a, abra\}$ となります。まず、2回以上出現する部分文字列を出現回数と出現場所が同一のものでまとめると、

$\{a\}, \{b, r, ab, br, ra, abr, bra, abra\}$

となります。なぜなら $\{b, r, ab, br, ra, abr, bra\}$ はいずれも、 $T=\underline{abra}cad\underline{abra}$$ において下線部の2箇所の $abra$ の部分文字列としてのみ出現し、それ以外の場所では出現しないからです。これが出現場所が同一という意味です。一方で $a$ という部分文字列について見てみると、下線部の2箇所の $abra$ の部分文字列以外にもう一箇所出現しており、出現場所が異なります。そのためこれら2回以上出現する部分文字列は上記のような同値類にまとめることができます。それぞれの同値類の中で長さが最長のものを考えることで極大部分文字列 $\{a, abra\}$ が得られます。これら同値類と極大部分文字列は例のように入力の文字列の末尾に $$$ をつけることで一意に定まります。

極大部分文字列を考えるモチベーション

さてこのような極大部分文字列を考えるモチベーションですが、形態素解析なしにBag of Words(BOW)よりもリッチな素性を高速に計算することが可能であるということが挙げられます。通常、日本語のようにわかち書きされていない言語の場合は形態素解析を行い、分かち書きされた単語やそれらのN-gramを素性として扱います。しかし、形態素解析を精度よく行うためには対象分野の十分な量のコーパスや専門の辞書が必要となります。またN-gramのNを大きくしていくと最終的に扱う素性の次元は $\rm{O}$ $(|T|^2)$ と入力の文字列の2乗オーダーとなってしまいます。

このような問題に対し極大部分文字列を考えると、入力の文書を形態素解析することなくBOWよりもリッチな特徴量を得ることができます。また以降で説明していきますが、極大部分文字列の個数はたかだか $|T|$ 個であり、 $\rm{O}$ $(|T|)$ 時間で高速に求めることができます。

極大部分文字列を求めるための準備

ここでは極大部分文字列を高速に求めるために必要なデータ構造について簡単に紹介したいと思います。以下の図1に $T=abracadabra$$ の場合の各種データ構造の例を示します。それぞれのデータ構造がわからなくなった場合はこの図に戻っていただければと思います。

f:id:big_wing_ik:20211028165003p:plain — 図1: 各種データ構造の例。左側において、iはインデックス、SAは接尾辞配列、LCPは高さ配列、BWTはBWT配列、 $\rm{BWT}\it_{rank}$ はBWTのrank配列、suffixは接尾辞配列に対応する接尾辞。右側は接尾辞木、この接尾辞木の図は全ての部分文字列を考慮した文書分類より引用。

図1: 各種データ構造の例。左側において、iはインデックス、SAは接尾辞配列、LCPは高さ配列、BWTはBWT配列、 $\rm{BWT}\it_{rank}$ はBWTのrank配列、suffixは接尾辞配列に対応する接尾辞。右側は接尾辞木、この接尾辞木の図は全ての部分文字列を考慮した文書分類より引用。

接尾辞木

今入力 $T$ を長さ $|T|$ の文字列 $T=[1,...,|T|$ ]とし、例のように $T[|T|] =$$ と末尾の文字を $$$ とします。このとき $S_i = T[i,...,|T|] (i=1,...,|T|)$ を $T$ の接尾辞と定義します。これらすべての接尾辞に対してTrie木を構築し、子が一つしか存在しない内部ノードを一つにまとめたものを $T$ に対する接尾辞木と定義します。具体例として $T=abracadabra$$ に対する接尾辞木を図1に示します。根ノードから一つの葉ノードまでのパスが一つの接尾辞(Suffix)に対応しています。また図のスペースの都合上、葉に接続する枝上の文字列が一部省略されています。接尾辞木は $\rm{O}$ $(|T|)$ で構築することができ、文字列検索を始めとする様々な問題を高速に計算することができます¹。一方で接尾辞木は大量の作業領域量を必要とし、メモリ効率がよくありません。接尾辞木と同様の操作をより省メモリで行うことができるデータ構造として次に紹介する拡張接尾辞配列があります。

拡張接尾辞配列

拡張接尾辞配列は、接尾辞配列と高さ配列の2つの配列からなるデータ構造です。

今、入力の文字列 $T$ の接尾辞 $S_i = T[i,...,|T|] (i=1,...,|T|)$ において、これらを辞書順に昇順に並べた時のインデックスの配列 $SA[1,...,|T|$ ]を $T$ の接尾辞配列と定義します。

また2つの文字列 $s, t$ に対して $lcp(s,t)$ を $s,t$ の共通する接頭辞の長さとした時に、高さ配列 $LCP[1,...,| T|]$ を $LCP[i] = lcp(S_{SA[i-1]}, S_{SA[i]})$ と定義します。ただし $LCP[1] = 0$ とします。つまり、隣接する接尾辞の共通する接頭辞の長さを保存した配列になります。

式で見てもあまりピンとこないと思うのでこれも具体例を見てみましょう。図1に $T=abracadabra$$ の場合の接尾辞配列と高さ配列の例を示します。図の接尾辞木と見比べてほしいのですが、接尾辞配列が接尾辞木における葉の情報を、高さ配列が接尾辞辞木の内部ノードの深さの情報を保持しています。例えば $a$ という内部ノードは深さが1であり、インデックスの $[2,...6]$ の範囲が対応しています。これを見てなんとなく接尾辞配列と高さ配列を合わせた拡張接尾辞配列で、接尾辞木と同様の操作を実現できそうな気がしてくるでしょうか？また接尾辞木と比較すると非負整数型の配列2つを保持しているだけなのでデータ構造としても非常にシンプルです。

接尾辞配列²と高さ配列³はいずれも $\rm{O}$ $(|T|)$ 時間で構築することができます。

BWT配列

最後にBWT配列について説明します。今、入力の文字列 $T$ と $T$ に対する接尾辞配列 $SA[1,...,|T|$ ]が与えられた時にBWT配列 $BWT[1,...,| T|]$ を $BWT[i] = T[SA[i]-1]$ と定義します。ただし $SA[i]=1$ のとき $BWT[i]=T[|T|]$ とします。式で見るとパット見わかりにくいですが、意味するところは簡単で、対応する接尾辞の直前の1文字を保持した配列となっています。(先頭の文字の直前の文字は末尾の文字と見なす。)これも具体例として図1を見て確認してみましょう。例えば $BWT[5] = T[SA[5]-1] = T[4-1]= T[3] = r$ となっており、これは $S_{5}=acadabra$$ の直前の文字が $r$ であることを示しています。

このような変換はブロックソート⁴ととも呼ばれ、変換後のBWT配列は同じ文字が連続して出現しやすくなるため圧縮アルゴリズムの前処理として用いられることもあります。BWT配列も $\rm{O}$ $(|T|)$ 時間で構築することができます。

極大部分文字列の高速な求め方

ここでは、これまで紹介した各種データ構造を用いることで極大部分文字列を高速に求めることができることを説明します。具体的には拡張接尾辞配列を用いて入力の文字列長である $\rm{O}$ $(|T|)$ 時間で求めることができます。

極大部分文字列であるための必要十分条件

まず天下り的ですが、極大部分文字列であるための必要十分条件として以下のものがあります。

部分文字列 $s$ が極大部分文字列 $\iff$ 部分文字列 $s$ が接尾辞木の内部ノードに対応し、かつその節点に対応するBWT配列が二種類以上の異なる文字を持つ

接尾辞木や拡張接尾辞配列に慣れている方にとってはこちらのほうがイメージしやすいかもしれません。今後の目標は拡張接尾辞配列を用いて極大部分文字列を求めることです。

まず具体例 $T=abracadabra$$ の場合に上記の条件を確認してみましょう。この場合の極大部分文字列は $\{a, abra\}$ の2つです。接尾辞木の内部ノードに対応しているのは図1から $\{a, abra, bra, ra\}$ の4つです。最初に $bra$ を考えてみます。この内部ノード以下の葉ノードである $SA$ は9と2であり、インデックスの7〜8に対応します。この範囲のBWT配列はいずれも $a$ の一種類であり、たしかに二種類以上の異なる文字を持つという条件に反しています。次に $ra$ を考えてみます。この内部ノード以下の葉ノードである $SA$ は10と3であり、インデックスの11〜12に対応します。この範囲のBWT配列はいずれも $b$ の一種類であり、やはり二種類以上の異なる文字を持つという条件に反しています。最後に極大部分文字列である $\{a, abra\}$ を見てみると、 $a$ に対応するインデックスの範囲は2〜6で、 $abra$ に対応するインデックスの範囲は3〜4であり、確かにこれら範囲におけるBWT配列は二種類以上の異なる文字を持っています。

拡張接尾辞配列における接尾辞木の内部ノード対応

ここでは接尾辞木の内部ノードが拡張接尾辞配列においてどのように対応するかについて説明します。先程の具体例で先に少し説明してしまいましたが、接尾辞木の内部ノードは拡張接尾辞配列において、内部ノードの深さと連続するインデックスの範囲の左端及び右端の位置のtripletで表現することができます。これも具体例を見てみましょう。例えば図1において内部ノード $a$ は拡張接尾辞配列において{内部ノードの深さ, インデックスの左端, インデックスの右端}= $\{1, 2, 6\}$ で表現されます。同様に $abra$ は $\{4, 3, 4\}$ 、 $bra$ は $\{3, 7, 8\}$ 、 $ra$ は $\{2, 11, 12\}$ と表現することができます。

このような内部ノードに対応するtripletは拡張接尾辞配列が与えられたもとでスタックを利用して $\rm{O}$ $(|T|)$ 時間で求めることができます⁵。以下にPythonのコード例を示します。 $LCP[i]$ > top_lcpの場合は現在の内部ノードより葉ノード方向に進み、内部ノードの深さとインデックスの左端を更新します。逆に $LCP[i]$ < top_lcpの場合は根ノードの方向に戻り、戻る前の内部ノードのtripletを返し、現在の内部ノードの深さとインデックスの左端を更新します。

def inner_node_interval():
    interval = []  # (lcp, left_boundary, right_boundary)
    s = [(0, 0)]  # (lcp, left_boundry)

    for i in range(2, |T|):
        lb = i - 1
        top_lcp, top_left = s[-1]

        while LCP[i] < top_lcp:
            rb = i - 1
            interval.append((top_lcp, top_left, rb))
            s.pop()
            lb = top_left
            top_lcp, top_left = s[-1]

        if LCP[i] > top_lcp:
            s.append((LCP[i], lb))

    rb = |T|
    lcp, lb = s[-1]
    if lcp > 0:
        interval.append((lcp, lb, rb))

    return interval

内部ノードに対応するBWT配列が二種類以上の異なる文字を持つかチェック

前回までで拡張接尾辞配列における内部ノードがtirpletによって得られることを説明しました。極大部分文字列を得るための最後のステップは内部ノードに対応するBWT配列が二種類以上の異なる文字を持つかチェックすることです。これについてはtakeda25氏のブログに詳しい解説がありますが、BWT配列の変化を記録する配列を用意すれば十分です。

今、これら変化を記録するための配列 $BWT_{rank}[1,...,|T|]$ を $BWT_{rank}[1]=0$ 、

$BWT\_{rank}[i+1]= \begin{eqnarray} \left\{ \begin{array}{1} \ \ \ BWT\_{rank}[i] \qquad (BWT[i+1] = BWT[i]) \\ BWT\_{rank}[i] + 1 \qquad (BWT[i+1] \neq BWT[i]) \end{array}\right. \end{eqnarray}$

と定義します。行っていることは簡単でBWT配列上において自身と直前の文字を比較し、同じ文字であれば値はそのままに、異なる文字であれば値をインクリメントしています。具体例は図1の $BWT_{rank}$ です。(ちなみに $BWT_{rank}$ を得るためには陽にBWT配列を構築する必要はなく、 $BWT_{rank}$ を直接構築することができます。)

このようにして得られた $BWT_{rank}$ と内部ノードのtripletにおける $lb=$ インデックスの左端、 $rb=$ インデックスの右端に対して $BWT_{rank}[rb]- BWT_{rank}[lb]$ の値を計算します。この値が0より大きければ内部ノードに対応するBWT配列が二種類以上の異なる文字を持つことになり、極大部分文字列となります。このようにして拡張接尾辞配列と $BWT_{rank}$ を用いることで極大部分文字列を列挙することができました。

これらのアルゴリズムで極大部分文字列を得るための時間計算量について確認します。入力の文字列 $T$ に対して拡張接尾辞配列と $BWT_{rank}$ は $\rm{O}$ $(|T|)$ 時間で構築することができます。さらに拡張接尾辞配列から内部ノードのtripletを得ることは、内部ノードの数が高々 $|T|$ 個であることから $\rm{O}$ $(|T|)$ 時間で得ることができます。最後にこれら内部ノードに対してBWT配列が二種類以上の異なる文字を持つかチェックします。内部ノード一つにあたりこのチェックは定数時間で実行できることから、内部ノードのチェックにかかる時間は $\rm{O}$ $(|T|)$ 時間です。以上から全体で極大部分文字列を $\rm{O}$ $(|T|)$ 時間で得ることができます。お疲れ様でした。

まとめ

今回は極大部分文字列について紹介しました。私自身久しぶりに文字列に触れてとても楽しかったです。また極大部分文字列を勉強することで、接尾辞木、拡張接尾辞配列、BWT変換など文字列検索周りの基本的な内容とそのアルゴリズムを勉強することができ、教育的な面でもいいなぁと思いました。興味がある方はぜひ極大部分文字列を学んでいただければと思います。

D. Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge University Press, 1997.↩
G. Nong, S. Zhang and W. H. Chan. Two Efficient Algorithms for Linear Time Suffix Array Construction. IEEE Transactions on Computers, vol. 60, no. 10, pp. 1471-1484, 2011.↩
T. Kasai, G. Lee, H. Arimura, S. Arikawa and K.Park. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications. Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching, pp.181-192, 2001. ↩
M. Burrows and D. J. Wheeler. A block-sorting lossless data compression algorithm, 1994.↩
MI Abouelhoda, S. Kurtz and E. Ohlebusch. Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms,Volume 2, Issue 1, pp. 53-86, 2004.↩

Retrieva TECH BLOG

再訪: 極大部分文字列