阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター 生命情報学特論 （２）文字列データ構造 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

接尾辞木

接尾辞木 (suffix tree) 文字列 S[1..n] の接尾辞(suffix) 接尾辞木 S[1..n], S[2..n], S[3..n], ・・・, S[n-1..n], S[n..n] 接尾辞木 文字列のすべての 接尾辞から構成されるトライ（trie） S[n+1]=$ を追加し最後尾を表す （以降は $ を追加後に n 文字とする） ただし、子が1個しか ない頂点は縮約 S=aabbccdabbca$ の接尾辞 $ a$ ca$ bca$ . abbccdabbca$ aabbccdabbca$

接尾辞木の応用： パターン検索 テキスト文字列の接尾辞木を構成（１回のみ） パターン文字列の入力の毎に、根から一致する文字を順にたどる パターン文字列長に比例する時間（O(m)時間）で検索が終了 テキスト文字列長に無関係　⇒ データベース検索に有用

接尾辞木の応用： Longest Common Substring ２個の文字列 S1, S2 に共通に出現する最長の連続部分文字列の検出 「k文字ずらしては一致する部分をチェックする」というアルゴリズムではO(|S1|・|S2|)時間 接尾辞木を用いれば 線形時間（なお、接尾辞木も線形時間で構築可能） S=S1#S2$ の接尾辞木を作成 ⇒ #を含む葉へのパスと含まない葉へのパスを持つ頂点をマーク ⇒ 根からの文字数最大のマークつき頂点を探す S1=aabbcc S2=abbdd S=aabbcc#abbdd$

接尾辞木の構成：単純な方法 接尾辞木の葉の数は n 個 ⇒ 接尾辞木の頂点数、枝数はO(n) 枝の文字列は S 中の位置で記憶　⇒　接尾辞木は O(n)領域 接尾辞木の構築法　　（単純な方法） i が1から n まで S[i…n] を1個ずつ追加しながらトライを作成 子が１個しかない頂点を縮約 時間計算量 1個の追加にO(n)時間 　　⇒全部の追加にO(n2)時間 縮約もO(n2)時間 ⇒　全体でO(n2)時間

Ukkonenアルゴリズム [Ukkonen: Algorithmica 1995]

Ukkonenアルゴリズム：アイデア オンライン・アルゴリズム 接尾辞木の簡潔な表現 接尾辞リンクの活用（後で説明） S の最初の文字から始め、１文字ずつ文字を読み込む i 文字目を読み込む度に、 S[1..i] の接尾辞木に更新 接尾辞木の簡潔な表現 そのまま接尾辞木を保持すると更新のたびに多くの時間が必要 　　⇒ 　$ のみからなる枝は持たない 接尾辞リンクの活用（後で説明） ⇒ 線形時間アルゴリズム

Ukkonenアルゴリズム：基本版 for i←1 to n-1 do for j←1 to i+1 do S[1] に対応する接尾辞木 T1 を構成; for i←1 to n-1 do for j←1 to i+1 do S[j..i] に一致する根からのパスをたどる; 次の位置に文字 S[i+1] がなければ枝を追加; （更新後の接尾辞木を Ti+1 とする） 1回の S[j..i] のチェックに O(n) 時間、全部で O(n2) 回のチェック ⇒ O(n3) 時間 S[i] の次が葉の場合は、枝を追加しない （葉は最後の文字に対応するので、枝につく文字が増えても何もしなくて良い）

Ukkonenアルゴリズム：文字追加の規則 S[i+1]の追加の規則 規則1: S[j…i] に対応する根からのパスが葉で終われば、その枝のラベルの最後に S[i+1] を追加 （ただし、実際は何もしない） 規則2: S[i+1] に対応する葉も枝もなければ、S[i+1]をラベルにもつ新たな枝と、新たな内部頂点を追加 規則3: S[i+1] に対応する枝があれば、何もしない 規則1 規則2 規則3

Ukkonenアルゴリズム：規則の性質 補題: 規則3が一度適用されたら、j’>j において S[j’..i] は調べる必要はない （S[j’..i] へのS[i+1]の追加は葉の伸長により自動的に対応） 証明: S[j’..i+1] は S[j..i+1] の接尾辞なので、 S[j..i+1] に対応する根からのパスがあれば、 S[j’..i+1] に対応するパスも存在 ⇒ 規則 3 が適用されたらステップiにおいて、それ以降のjをチェックしない 補題: S[j..i] のパスをたどって S[i+1] に対応する枝が新たに追加されたらば、i’>i において S[j..i’] を調べる必要はない 証明: 追加された枝の最後のラベルは常に S[i’+1] に対応 ⇒ 規則 2が適用されたら、以降のすべてのステップにおいて、そのjをチェックしない 上記補題から、S[j..i+1] のチェックは以下のように行えば十分 i: S[ji+1..i+1], S[ji+2..i+1], …, S[ji+1+1..i+1] i+1: S[ji+1+1..i+2], S[ji+1+2..i+2], …, S[ji+2+1..i+2] i+2: S[ji+2+1..i+3], S[ji+2+2..i+3], …, S[ji+3+1..i+3] i+3: S[ji+3+1..i+4], S[ji+3+2..i+4], …, S[ji+4+1..i+4] 　　　　　　　…

Ukkonenアルゴリズム：改良版 1回の S[j..i] のチェックに for i←1 to n-1 do O(n) 時間、 空の接尾辞木 T1 を構成; j1←0; for i←1 to n-1 do すべての葉を延長; for j←ji+1 to i+1 do S[j..i] に一致する根からのパスをたどる; if 次の位置に文字 S[i+1] がある（規則3） then 　　 ji+1←j-1; break; 規則2を適用; ji+1←j 1回の S[j..i] のチェックに O(n) 時間、 全部で O(n) 回のチェック ⇒ O(n2) 時間 葉がすべて先に延長されている ので、規則１の適用はない 規則3 規則2 規則2

Ukkonenアルゴリズム：接尾辞リンク 接尾辞リンク： x を文字、α を文字列とする。v をパスラベルが xα である内部頂点とする。パスラベルが α である内部頂点を w とする時、 v の接尾辞リンク s(v) は s(v)=w （αが空の時、s(v)は根） 補題： v を接尾辞木の内部頂点とすると、s(v) は必ず存在 証明： v が内部頂点なので、xαyβ と xαzγ という接尾辞があるはず（y≠z）。よって、αy、αz というパスラベルも存在し、α をパスラベルとする内部頂点が存在。 パスラベル： 根から頂点までのパスの枝のラベルを連結した文字列 接尾辞リンクは葉にも定義可能

Ukkonenアルゴリズム：接尾辞リンクの利用 接尾辞リンクをたどると、 S[j..i] を根から毎回たどらなくても、木の更新ができる。 枝を追加して新たな内部頂点ができる度に、接尾辞リンクを新たに追加。 例（下図）： Ti の構築が終了した時点で、ピンクの d を参照。（ピンクの d は S[ji+1..i] に対応。実際には、直前の頂点を記憶（d の位置は ji から計算可能）） Ti+1 の構築のために、cada, ada, da, a を追加する（他は葉をのばせばよい）。 接尾辞リンクをたどりながら、d で終わる文字を見つけ、その下に頂点を挿入。 最後の a （ピンクの a）は規則3により追加の必要がない。 この a が次の S[ji+1+1..i+1] に対応。 Ti Ti+1

Ukkonenアルゴリズム：接尾辞リンクの利用 根まで至らずに接尾辞リンクをたどるのが終わる場合（規則３が適用）の例 S=bdbeabdabcabe （葉の伸長部分は省略）

Ukkonenアルゴリズム：枝の経由法 前の図では、各内部頂点から１文字たどるだけで目的の位置にたどりつけたが、場合によっては何文字もたどることが必要。 しかし、枝を1本たどるのは定数時間で可能（最初の文字だけ見てどの枝を選べばよいかわかれば、接尾辞の性質により他の文字は一致）。 もちろん、場合によっては複数の枝を経由することも必要であるが、計算量の ならし解析により、全部で O(n) 回の経由で済むことを示すことができる （詳細は省略）。

Ukkonenアルゴリズム：$の追加 定理： 接尾辞木は線形時間で構成可能 最後に $ を追加し、接尾辞木を完成させる。 $ の追加は（これまでに出現していない）新たな文字を最後尾に追加するのと全く同じ。 定理： 接尾辞木は線形時間で構成可能

Burrows-Wheeler変換 参照: [岡野原：　情報処理, 2012]

Burrows-Wheeler（BW）変換 例で示す：　S=abracadabra$ （$は終端を意味） この文字列を巡回させた文字列をすべて生成し、ソートし、終端の文字を並べたものが変換後の文字列 ソート ard$rcaaaabb

BW変換： 逆変換 変換後の文字列 逆変換：アイデア S=abracadabra$ 逆変換：方法 この作業を繰り返す 同じ文字が連続して並ぶことが多い ⇒ データ圧縮に有利 もとの文字が（同じ回数だけ）出現 終端 始端 逆変換：アイデア ソート後の巡回文字列の終端（BW変換）と始端の文字を並べる（文字には順番に番号を付加） 同じ行の（終端、始端）はS中で連続して出現 S=abracadabra$ 逆変換：方法 始端を並べた文字列を、BW変換後の文字をソートして作成 左側が$である行を探す⇒右側（a3）がSの1番目 左側がa3である行を探す⇒右側（b2）がSの2番目 左側がb2である行を探す⇒右側（r2）がSの3番目 この作業を繰り返す

始端と終端で順番が保存される理由 終端 始端 これをソートしたもの の末尾が a になる ので、 始端と終端で a の 順番が保存される

BW変換： 部分文字列検索 S=abracadabra$ 以下の関数（高速に計算可能）を利用 C(x): ソート後の表における、文字 x を先頭とする最初の接尾辞の位置 rankx(B,i): B[1…i-1] 中に出現する文字 x の個数 B 接尾辞 検索アルゴリズム P=bra の場合の(sp,ep) の変化 (1,13) ⇒ a ⇒ (2,7) ⇒ r ⇒ (11,13)⇒b⇒(7,9) P=braa の場合の(sp,ep)の変化 (1,13) ⇒ a ⇒ (2,7) ⇒ a ⇒ (3,3) ⇒ none C(a)=2, C(b)=7, C(c)=9, C(d)=10, C(r)=11 行iにおいて、B [i]は接尾辞の１個前の文字

BW変換： 部分文字列検索の例 S=abracadabra$ (2,7) (7,9) (11,13) C(b)=7 C(c)=9 C(d)=10 (2,7) a の前の r は、B中で 「最初から2番目まで」 だけであることがわかる (7,9) C(r)=11 (11,13) P=bra の時の(sp,ep) の変化 sp ep (1,13) ⇒ C(a)+ranka(B,1)=2+0=2 C(a)+ranka(B,13)=2+5=7 (2,7) ⇒ C(r)+rankr(B,2)=11+0=11 C(r)+rankr(B,7)=11+2=13 (11,13) ⇒ C(b)+rankb(B,11)=7+0=7 C(b)+rankb(B,13)=7+2=9 出現順が保存されることも利用 (sp,ep-1) がS[i..m] とマッチしている範囲

接尾辞配列

接尾辞配列 (suffix array) 接尾辞木と似た情報をより簡潔に表現 もとの文字列の接尾辞をソートし、接尾辞の開始位置のみを格納した配列（図中のSA） 文字列 S SA ソートした接尾辞

接尾辞配列の性質 接尾辞木があれば簡単に構成できるが、接尾辞木を作らなくても O(n) 時間で直接構成可能 部分文字列検索を、単純な二分探索法で O(m log n)時間で実行可。より精密な方法を使えば、O(m+log n）時間で実行可。 その他、接尾辞木でできる多くの操作が接尾辞配列でも可能（ただし、配列以外に付加的な情報が必要になる場合もある） 部分文字列検索の例： P=abraca a: (10,7,0,3,5) ⇒ ab: (7,0) ⇒ abr: (7,0) ⇒ abra (7,0) ⇒ abrac (0)

接尾辞配列作成の線形時間アルゴリズム(1) DC3アルゴリズム[Karkkainen et al., JACM 2006] を説明 アイデア： マージソート 文字列 T SA ソートした接尾辞

接尾辞配列作成の線形時間アルゴリズム(2) 配列位置を３の剰余により B0,B1,B2 に分割し、C=B1∪B2とする 例： B1={1,4,7,10}, B2={2,5,8,11}, C={1,4,7,10,2,5,8,11} Rk=[tktk+1tk+2][tk+3tk+4tk+5]… とし、R=R1・R2 とする 必要に応じて、末尾に $ を追加（$ < a）

接尾辞配列作成の線形時間アルゴリズム(3) R の各要素を（基数ソートで）順位づけしたものを R’ とする R’ の接尾辞配列 SAR’ を再帰的に構成 順位づけ R’=(1,2,4,6,4,5,3,7,$) R’ の 接尾辞配列

接尾辞配列作成の線形時間アルゴリズム(4) SAR’ により、 C=B1∪B2 の位置のソートが完了 残り B0 を Si ≦ Sj ⇔ (ti, rank(Si+1)) ≦ (tj, rank(Sj+1)) でソート Si : 入力文字列の i 番目文字から 始まる接尾辞 rank(Si): Si の接尾辞配列における順位 S12 < S6 < S9 < S3 < S0 上記規則でソート C の位置のソートが完了 S0 S3 S6 S9 S12

接尾辞配列作成の線形時間アルゴリズム(5) C のソート結果と B0 のソート結果を以下の規則でマージ B0 vs. B1 : Si ≦ Sj ⇔ (ti, rank(Si+1)) ≦ (tj, rank(Sj+1)) B0 vs. B2 : Si ≦ Sj ⇔ (ti, ti+1, rank(Si+2)) ≦ (tj, tj+1, rank(Sj+2)) S0 S3 S6 S9 S12 S12 < S6 < S9 < S3 < S0 S1 < S4 < S8 < S2 < S7 < S5 < S10 < S11 マージ S12 < S1 < S6 < S4 < S9 < S3 < S8 < S2 < S7 < S5 < S10 < S11 < S0 マージ規則の 適用例 S1 < S6 ⇔ (a, rank(S2)) < (a, rank(S7)) S3 < S8 ⇔ (b, a, rank(S5)) < (b, a, rank(S10))

接尾辞配列作成の線形時間アルゴリズム(6) S3 S6 S9 S12 定理： 接尾辞配列は線形時間で構成可能 証明： 上記アルゴリズムの正当性は明らか。また、再帰呼出し以外は線形時間。 再帰呼出しの際はデータのサイズが2/3になる。よって、DC3アルゴリズムの計算時間をT(n)とすると以下を得る。 T(n)=T(2n/3)+O(n)

まとめ 接尾辞木 BW変換 接尾辞配列 補足 接尾辞集合をコンパクトに表現 線形時間で構成可能 文字列をコンパクトに表現、圧縮にも有効、高速な検索が可能 接尾辞配列 接尾辞木と同様の目的、よりコンパクト 補足 UkkonenアルゴリズムはO(log |Σ|)時間のオーバーヘッドがあるが、一般のアルファベットに対して線形時間で動作するアルゴリズムも存在 [Farach: Proc. FOCS 1997] 近年ではコンパクトかつ検索その他を用意にする簡潔データ構造(succinct data structure)に関する研究が盛んに行われている