Ukkonenのアルゴリズム - tanakakenji/Rinko GitHub Wiki

ここでは、Ukkonenのサフィックスツリー構築アルゴリズムについて議論します。 ブルートフォース方式から始め、Ukkonenのアルゴリズムに含まれる様々な概念やトリックを理解しようとし、最後の部分でコード実装について議論します。

Dan Gusfield著の書籍**「Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology」**は、概念を非常に上手く説明しています。

m文字の文字列Sに対するサフィックスツリーTは、1からmまでの番号が付けられたm個の葉を持つ、根付き有向木です。

ukkonen_1_1

  • 根は0個、1個、または複数の子を持つことができます。
  • 根以外の各内部ノードは、少なくとも2つの子を持ちます。
  • 各エッジはSの空でない部分文字列でラベル付けされています。
  • 同じノードから出る2つのエッジが、同じ文字で始まるエッジラベルを持つことはできません。

根から葉iへのパス上のエッジラベルの連結は、位置iから始まるSの接尾辞、つまりS[i...m]を与えます。

注意: 位置は1から始まります（ゼロインデックスではありませんが、後でコード実装する際には、ゼロインデックスの位置を使用します）

文字列 S = xabxac（m = 6）の場合、サフィックスツリーは以下のようになります：

ukkonen_1_1

1つのルートノード、2つの内部ノード、6つの葉ノードがあります。

  • 赤いパスの文字列深さは1で、位置6から始まる接尾辞 c を表します
  • 青いパスの文字列深さは4で、位置3から始まる接尾辞 bxca を表します
  • 緑のパスの文字列深さは2で、位置5から始まる接尾辞 ac を表します
  • オレンジのパスの文字列深さは6で、位置1から始まる接尾辞 xabxac を表します

ラベル a（緑）と xa（オレンジ）のエッジは非葉エッジ（内部ノードで終わる）です。他のすべてのエッジは葉エッジ（葉で終わる）です。

Sの1つの接尾辞がSの別の接尾辞の接頭辞と一致する場合、エッジは葉で終わりません。 例えば、a には、ac と abxac があるので、分岐を使います。

文字列にまだ存在しない文字を追加します。通常、$、# などを終端文字として使用します。 以下は、文字列 S = xabxa$（m = 6）のサフィックスツリーで、これで6つの接尾辞すべてが葉で終わります。 ukkonen_1_3

サフィックスツリー構築アルゴリズムの解説

サフィックスツリーを構築する素朴なアルゴリズム

長さmの文字列Sが与えられた場合、以下の手順でサフィックスツリーを構築します：

  1. まず、接尾辞S[1..m]$（全体の文字列）に対する単一のエッジを木に挿入します。 ukkonen_1_4

  2. 次に、iを2からmまで増加させながら、接尾辞S[i..m]$を成長中の木に順次挿入します。 ukkonen_1_5 ukkonen_1_6

  3. Niを、1からiまでのすべての接尾辞をエンコードする中間的な木とします。 ukkonen_1_7

Ni+1はNiから以下のように構築されます：

flowchart TD
    A[開始] --> B[入力文字列Sに終端文字'$'を追加]
    B --> C[ルートノードを作成]
    C --> D[最初のサフィックス全体をルートに接続]
    D --> E{すべてのサフィックスを処理したか?}
    E -->|いいえ| F[次のサフィックスを選択]
    F --> G[ルートノードから開始]
    G --> H{現在のノードにマッチする\n文字で始まるエッジがあるか?}
    H -->|はい| I[エッジに沿って進む]
    I --> J{エッジのラベル全体が\nマッチするか?}
    J -->|はい| K[エッジの終点ノードに移動]
    K --> H
    J -->|いいえ| L[エッジを分割し\n新しいノードを挿入]
    L --> M[残りの文字で\n新しいエッジを作成]
    M --> E
    H -->|いいえ| N[現在のノードから\n新しいエッジを作成]
    N --> E
    E -->|はい| O[終了]

長さmの文字列Sの接尾辞ツリーを構築するには O(m 2 )かかります。

Ukkonenのサフィックスツリー構築アルゴリズム

ukkonen_1_9

ルール2-新しい葉ノード

ukkonen_1_10

ルール1-既存の葉エッジのパスラベルを拡張する

ルール2-新しい葉ノード

ukkonen_1_11

ukkonen_1_12

ルール1-既存の葉エッジのパスラベルを拡張する

ルール3-何もしない（ラベル x のパスが既に存在する）

ukkonen_1_13

ukkonen_1_14

ルール1-既存の葉エッジのパスラベルを拡張する

ルール2-3つの新しい葉エッジと2つの新しい内部ノードを作成

Ukkonenのサフィックスツリー構築アルゴリズム

長さmの文字列Sのサフィックスツリー構築において、m個のフェーズがあり、フェーズj（1 <= j <= m）では、これまでに構築された木にj番目の文字を追加します。これはj個の拡張を通じて行われます。すべての拡張は、3つのルールのいずれかに従います。

フェーズi+1のj番目の拡張（文字S[i+1]の追加）を行うには、まず現在の木の根からS[j..i]でラベル付けされたパスの終点を見つける必要があります。一つの方法は、根から始めてS[j..i]文字列と一致するエッジをたどることです。これではサフィックスツリーの構築にO(m^3)の時間がかかります。いくつかの観察と実装のトリックを使用することで、O(m)で行うことができます。これについて、これから見ていきます。

サフィックスリンク

内部ノードvのパスラベルがxAである場合（xは単一の文字を表し、Aは（おそらく空の）部分文字列を表す）、パスラベルAを持つ別のノードs(v)がある場合、vからs(v)へのポインタをサフィックスリンクと呼びます。

  • Aが空文字列の場合、内部ノードからのサフィックスリンクは根ノードに向かいます。
  • 根ノードからのサフィックスリンクはありません（根ノードは内部ノードとみなされないため）。

image

あるフェーズiの拡張jで、パスラベルxAを持つ新しい内部ノードvが追加された場合、同じフェーズiの拡張j+1では：

  1. パスラベルAがすでに内部ノード（またはAが空の場合は根ノード）で終わっている
  2. または、文字列Aの終点に新しい内部ノードが作成される

同じフェーズiの拡張j+1で、j番目の拡張で作成された内部ノードから、パスラベルAを持つノードへのサフィックスリンクを作成します。

サフィックスリンクの性質

  1. 任意のフェーズにおいて、新しく作成された内部ノード（パスラベルxA）は、次の拡張の終わりまでにサフィックスリンク（パスラベルAを持つ別のノードを指す）を持つことになります。

  2. フェーズi後の任意の暗黙的サフィックスツリーTiにおいて、内部ノードvがパスラベルxAを持つ場合、TiにはパスラベルAを持つノードs(v)が存在し、ノードvはサフィックスリンクを使用してノードs(v)を指します。

  3. 常に、最も最近追加された内部ノードを除くすべての内部ノードは、別の内部ノード（または根）へのサフィックスリンクを持ちます。最新の内部ノードは、次の拡張の終わりまでにサフィックスリンクを受け取ります。

サフィックスリンクによる実装の高速化

フェーズi+1の拡張jでは、現在の木の根からS[j..i]でラベル付けされたパスの終点を見つける必要があります。サフィックスリンクは、このパスの終点を見つけるための近道を提供します。

  1. パスS[j-1..i]の終点から開始します。
  2. 1つのエッジを上に移動してノードv（つまり親ノード）に到達します。
  3. サフィックスリンクに従ってs(v)に移動します。
  4. パスy（図17では "abcd"）に沿って下に移動します。

このように、パスS[j..i]の終点を見つけるために根から走査する必要はありません。これはプロセスの改善を示しています。

注意：次のパート3では、"上への移動"を避けるのに役立つアクティブポイントを導入します。ノードvからノードs(v)に直接移動できるようになります。

スキップ/カウントトリック

ノードs(v)から葉に向かって下に移動する際、文字ごとにパスを照合する代わりに、以下のようにスキップできます：

  1. エッジ上の文字数が移動する必要がある文字数より少ない場合、次のノードに直接スキップします。
  2. エッジ上の文字数が移動する必要がある文字数より多い場合、そのエッジの最後の文字に直接スキップします。

実装が、任意のエッジ上の文字数や文字列S内の特定の位置の文字を定数時間で取得できるようになっている場合、スキップ/カウントトリックは、文字数ではなくノード数に比例して下への移動を行います。

サフィックスリンクとスキップ/カウントトリックを使用することで、サフィックスツリーをO(m^2)で構築できます（mフェーズあり、各フェーズがO(m)かかるため）。

エッジラベル圧縮

これまで、パスラベルは文字列内の文字として表現されていました。このようなサフィックスツリーは、パスラベルを格納するのにO(m^2)の空間を必要とします。これを避けるために、部分文字列自体の代わりに、各エッジのパスラベルに対して2つの指標のペア（開始、終了）を使用できます。開始と終了の指標は、文字列S内のパスラベルの開始位置と終了位置を示します。これにより、サフィックスツリーはO(m)の空間を必要とします。

観察1：ルール3はストッパー

フェーズiでは、i個の拡張（1からi）を行う必要があります。フェーズi+1の任意の拡張jでルール3が適用される場合（つまり、S[j..i]でラベル付けされたパスが文字S[i+1]で続く場合）、同じフェーズの以降のすべての拡張（つまり、フェーズi+1の拡張j+1からi+1）でも適用されます。

ルール3が適用されるとすぐに、任意のフェーズの処理を停止します。以降のすべての拡張は、既に木に暗黙的に存在しています。

観察2：一度葉になれば、常に葉

一度葉が作成され、j（文字列S内の位置jから始まる接尾辞用）とラベル付けされると、この葉は後続のフェーズと拡張で常に葉となります。葉がjとラベル付けされると、拡張ルール1が後続のすべてのフェーズの拡張jに常に適用されます。

フェーズの進行とルールの適用

任意のフェーズiにおいて：

  1. 最初に、ルール1またはルール2が適用される連続した拡張のシーケンスがあります。
  2. ルール3が適用されるとすぐに、フェーズiが終了します。
  3. ルール2は常に新しい葉を作成し（時には内部ノードも）ます。

Jiをフェーズiでルール1または2が適用された最後の拡張とすると：

  • i番目のフェーズ後、1, 2, 3, ..., Jiとラベル付けされたJi個の葉が存在します。
  • Ji <= Ji+1 となります。
  • フェーズi+1で新しい葉が作成されない場合（つまり、Ji+1拡張でルール3が適用される場合）、Ji = Ji+1 となります。

例：

  • 図11（フェーズ3）：最初の2つの拡張でルール1が適用され、3番目の拡張でルール2が適用されます。ここでJ3 = 3。
  • 図12（フェーズ4）：新しい葉は作成されません（最初の3つの拡張でルール1が適用され、4番目の拡張でルール3が適用されてフェーズが終了）。ここでJ4 = 3 = J3。
  • 図13（フェーズ5）：新しい葉は作成されません（最初の3つの拡張でルール1が適用され、4番目の拡張でルール3が適用されてフェーズが終了）。ここでJ5 = 3 = J4。
  • 図14（フェーズ6）：新しい葉が作成されます（最初の3つの拡張でルール1が適用され、最後の3つの拡張でルール2が適用されてフェーズが終了）。ここでJ6 = 6 > J5。

トリック3：葉エッジの効率的な更新

フェーズiで、葉エッジは(p, i), (q, i), (r, i), ... のように見えます（p, q, rは異なるエッジの開始位置、iはすべての終了位置）。フェーズi+1では、これらの葉エッジは(p, i+1), (q, i+1), (r, i+1), ... のようになります。

各フェーズで全ての葉エッジの終了位置をインクリメントする代わりに：

  1. グローバルインデックスeを維持し、eをフェーズ番号と等しくします。
  2. 葉エッジを(p, e), (q, e), (r, e)... として表現します。
  3. 任意のフェーズで、eをインクリメントするだけで、すべての葉エッジの拡張が行われます。

線形時間でのサフィックスツリー構築

サフィックスリンクとトリック1、2、3を使用することで、サフィックスツリーを線形時間で構築できます。

注意点：

  • ツリーTmは、ある接尾辞が別の接尾辞の接頭辞である場合、暗黙的なツリーになる可能性があります。
  • 真のサフィックスツリー（すべての接尾辞を明示的に含む）を得るには、最初に$終端記号を追加してからアルゴリズムを実行します。
  • 各葉に対応する接尾辞の開始位置でラベル付けするには、ツリーに対して線形時間の走査を行うことができます。

ここでは、文字列S = "abcabxabcd"を例にとり、ステップバイステップでツリーを作成していきます。 $を追加するので（パート1でその理由を説明しました）、文字列Sは"abcabxabcd$"となります。

長さmの文字列Sのサフィックスツリーを構築する際：

  1. 1からmまでのm個のフェーズがあります（各文字に1つのフェーズ）。
  2. 現在の例では、m = 11なので、11のフェーズがあります。
  3. 最初のフェーズで最初の文字'a'を木に追加し、2番目のフェーズで2番目の文字'b'を木に追加し、以下同様に進みます（これによりUkkonenのアルゴリズムはオンラインアルゴリズムとなります）。
  4. 各フェーズiは最大i個の拡張（1からi）を行います。
  5. 3つの拡張ルール（1, 2, 3）があり、各フェーズiの各拡張j（1からi）はこれらの3つのルールのいずれかに従います。
    • ルール1：既存の葉エッジに新しい文字を追加します。
    • ルール2：新しい葉エッジを作成します（パスラベルがエッジの途中で終わる場合、新しい内部ノードも作成する可能性があります）。
    • ルール3：現在のフェーズを終了します（現在の文字が走査中のエッジで見つかった場合）。

フェーズ1

  1. 文字列から最初の文字を読み取り、1つの拡張を行います。
  2. 拡張1：接尾辞"a"を木に追加します。根から始まり、ラベル'a'のパスを走査します。根からラベル'a'で出ていくパスがないので、葉エッジを作成します（ルール2）。
  3. フェーズ1は拡張1の完了とともに終了します。

フェーズ2

  1. 2番目の文字'b'を読み取り、最低1つ、最大2つの拡張を行います。
  2. 追加する接尾辞は"ab"と"b"です。
  3. 拡張1：接尾辞"ab"を木に追加します。ラベル'a'のパスは葉エッジで終わるので、このエッジの終わりに'b'を追加します（ルール1）。
  4. 拡張2：接尾辞"b"を木に追加します。根からラベル'b'で出ていくパスがないので、葉エッジを作成します（ルール2）。
  5. フェーズ2は拡張2の完了とともに終了します。

フェーズ3

  1. 3番目の文字'c'を読み取り、最低1つ、最大3つの拡張を行います。
  2. 追加する接尾辞は"abc"、"bc"、"c"です。
  3. 拡張1：接尾辞"abc"を木に追加します（ルール1）。
  4. 拡張2：接尾辞"bc"を木に追加します（ルール1）。
  5. 拡張3：接尾辞"c"を木に追加します（ルール2）。
  6. フェーズ3は拡張3の完了とともに終了します。

フェーズ4

  1. 4番目の文字'a'を読み取り、最低1つ、最大4つの拡張を行います。
  2. 追加する接尾辞は"abca"、"bca"、"ca"、"a"です。
  3. 拡張1：接尾辞"abca"を木に追加します（ルール1）。
  4. 拡張2：接尾辞"bca"を木に追加します（ルール1）。
  5. 拡張3：接尾辞"ca"を木に追加します（ルール1）。
  6. 拡張4：接尾辞"a"を木に追加しようとしますが、ラベル'a'のパスが既に木に存在するため、これ以上の作業は必要ありません（ルール3とトリック2）。これは暗黙的サフィックスツリーの例です。
  7. フェーズ4は拡張4でルール3が適用されるとすぐに完了します。

これらの観察と実装方法について、さらに詳しく見ていきます。

Ukkonenのサフィックスツリー構築アルゴリズム - パート4

重要な観察と実装のポイント

  1. フェーズiの終了時点で、最大i個の葉エッジが存在します（i番目の文字がこれまでに見られていない場合はi個、そうでない場合はi未満）。

  2. フェーズi完了後、全ての葉エッジの"end"インデックスはiです。これを効率的に実装するために、グローバル変数"END"を使用します。

  3. トリック3（一度葉になれば、常に葉）の実装：フェーズiの後にj個の葉エッジがある場合、フェーズi+1の最初のj個の拡張（1からj）は、変数"END"を1増やすだけで完了します。

  4. 前のフェーズiがどのように完了したかによって、次のフェーズi+1でのスタート地点と走査するパスが決まります。

activePointの概念

activePointは、任意の拡張で走査が開始される点です。これは、ルートノード、内部ノード、またはエッジの途中の任意の点である可能性があります。

activePointは3つの変数で表現されます：

  • activeNode：ルートノードまたは内部ノード
  • activeEdge：どのエッジを選択するかを示す情報
  • activeLength：activeNodeからactivePointまでの文字数

activePointの変更ルール

  1. 拡張ルール3のためのactivePoint変更（APCFER3）：

    • ルール3が適用される場合、activeLengthを1増やします。
    • activeNodeとactiveEdgeは変更しません。

  2. ウォークダウンのためのactivePoint変更（APCFWD）：

    • ウォークダウン中に内部ノードに遭遇した場合、そのノードが新しいactiveNodeになります。
    • activeEdgeとactiveLengthも適切に調整されます。

  3. activeLengthがゼロの場合のactivePoint変更（APCFALZ）：

    • activeLengthがゼロの時、activeEdgeは現在処理中の文字に設定されます。

実装上の注意点

  1. remainingSuffixCount変数を使用して、各フェーズで明示的に実行する必要がある拡張の数を追跡します。

  2. フェーズ終了時にremainingSuffixCountがゼロの場合、すべての接尾辞が明示的に木に追加されたことを意味します。

  3. フェーズ終了時にremainingSuffixCountが非ゼロの場合、その数の接尾辞が明示的に木に追加されていないことを意味しますが、暗黙的には木に存在します（これらの木を暗黙的サフィックスツリーと呼びます）。

  4. これらの暗黙的な接尾辞は、ユニークな文字が現れた後続のフェーズで明示的に追加されます。

この解説は、Ukkonenのアルゴリズムの効率的な実装方法を詳細に説明しています。activePointの概念と、それがどのようにアルゴリズムの性能を向上させるかが特に重要です。

次のパート5では、さらに詳細な実装の側面について議論し、パート6でコード実装について説明する予定です。

Ukkonenのサフィックスツリー構築アルゴリズム - パート5

この記事は以下の3つの記事の続きです：

  • Ukkonenのサフィックスツリー構築 – パート1
  • Ukkonenのサフィックスツリー構築 – パート2
  • Ukkonenのサフィックスツリー構築 – パート3

パート1、パート2、パート3を確認してから、この記事を読むことをお勧めします。これまでに、サフィックスツリーの基本、Ukkonenのアルゴリズムの概要、サフィックスリンク、3つの実装トリック、activePointに関する詳細、そして例として文字列"abcabxabcd"を用いたサフィックスツリー構築の4つのフェーズについて見てきました。

ここでは、パート3で見た4つのフェーズを、トリック2、トリック3、activePointの観点から再検討します。

初期化

  • activePointは(root, NULL, 0)に初期化されます。つまり、activeNodeはroot、activeEdgeはNULL（コード実装では文字のインデックスになります）、activeLengthはZEROです。
  • グローバル変数ENDとremainingSuffixCountはZEROに初期化されます。

フェーズ1

文字列Sから1文字目（a）を読み込みます。

  1. ENDを1に設定します。
  2. remainingSuffixCountを1増やします（ここではremainingSuffixCountは1になり、1つの拡張を実行する必要があることを意味します）。
  3. remainingSuffixCount回（つまり1回）ループを実行します：
    • activeLengthがZEROの場合、activeEdgeを現在の文字に設定します（ここではactiveEdgeは'a'になります）。これはAPCFALZです。
    • activeNode（このフェーズ1ではroot）からactiveEdgeに対応するエッジが出ているかチェックします。ない場合は葉エッジを作成し、ある場合はウォークダウンします。この例では、葉エッジが作成されます（ルール2）。
    • 拡張が実行されたら、remainingSuffixCountを1減らします。
    • この時点で、activePointは(root, a, 0)です。

フェーズ1の終了時、remainingSuffixCountはZEROです（すべての接尾辞が明示的に追加されています）。パート3の図20がフェーズ1後の結果のツリーです。

この説明は、Ukkonenのアルゴリズムの最初のフェーズを詳細に示しています。特に、activePointの初期化と変更、remainingSuffixCountの使用、そしてエッジの作成プロセスが重要です。

次のフェーズでは、これらの概念がどのように発展し、より複雑なツリー構造を構築していくかを見ていくことになります。

Ukkonenのサフィックスツリー構築アルゴリズム - パート5の続き

フェーズ2

文字列Sから2文字目（b）を読み込みます。

  1. ENDを2に設定します（これにより拡張1が実行されます）。
  2. remainingSuffixCountを1増やします（1つの拡張が残っています）。
  3. remainingSuffixCount回（1回）ループを実行：
    • activeLengthがZEROの場合、activeEdgeを'b'に設定します（APCFALZ）。
    • activeNodeからactiveEdgeに対応するエッジをチェックし、ない場合は葉エッジを作成します。
    • 拡張後、remainingSuffixCountを1減らします。
    • この時点で、activePointは(root, b, 0)です。

フェーズ2の終了時、remainingSuffixCountはZEROです（すべての接尾辞が明示的に追加されています）。

フェーズ3

文字列Sから3文字目（c）を読み込みます。

  1. ENDを3に設定します（これにより拡張1と2が実行されます）。
  2. remainingSuffixCountを1増やします（1つの拡張が残っています）。
  3. remainingSuffixCount回（1回）ループを実行：
    • activeLengthがZEROの場合、activeEdgeを'c'に設定します（APCFALZ）。
    • activeNodeからactiveEdgeに対応するエッジをチェックし、ない場合は葉エッジを作成します。
    • 拡張後、remainingSuffixCountを1減らします。
    • この時点で、activePointは(root, c, 0)です。

フェーズ3の終了時、remainingSuffixCountはZEROです。

フェーズ4

文字列Sから4文字目（a）を読み込みます。

  1. ENDを4に設定します（これにより拡張1、2、3が実行されます）。
  2. remainingSuffixCountを1増やします（1つの拡張が残っています）。
  3. remainingSuffixCount回（1回）ループを実行：
    • activeLengthがZEROの場合、activeEdgeを'a'に設定します（APCFALZ）。
    • activeNodeからのエッジ'a'が存在するため、ウォークダウンを行います（トリック1 - スキップ/カウント）。
    • activeLengthを0から1に増やし（APCFER3）、処理を停止します（ルール3）。
    • この時点で、activePointは(root, a, 1)で、remainingSuffixCountは1のままです。

フェーズ4の終了時、remainingSuffixCountは1です（最後の接尾辞'a'は明示的に追加されていませんが、暗黙的に存在します）。

フェーズ5

文字列Sから5文字目（b）を読み込みます。

  1. ENDを5に設定します（これにより拡張1、2、3が実行されます）。
  2. remainingSuffixCountを1増やします（2つの拡張が残っています）。
  3. remainingSuffixCount回（2回）ループを実行：
    • activeNodeからのエッジ'a'が存在するため、必要に応じてウォークダウンを行います。
    • 現在の文字'b'がactivePointの後に存在するかチェックし、存在する場合は処理を停止します（ルール3）。
    • activeLengthを1から2に増やし（APCFER3）、処理を停止します。
    • この時点で、activePointは(root, a, 2)で、remainingSuffixCountは2のままです。

フェーズ5の終了時、remainingSuffixCountは2です（最後の2つの接尾辞'ab'と'b'は明示的に追加されていませんが、暗黙的に存在します）。

フェーズ6

文字列Sから6文字目（x）を読み込みます。

  1. ENDを6に設定します（これにより拡張1、2、3が実行されます）。
  2. remainingSuffixCountを1増やします（3つの拡張が残っています）。
  3. remainingSuffixCount回（3回）ループを実行：
    • 拡張4では、activePointは(root, a, 2)で、エッジ'a'上の'b'を指しています。
    • 現在の文字'x'がactivePointの後の文字と一致しないため、ルール2を適用します。
    • 葉エッジを作成し、新しい内部ノードも作成します。
    • remainingSuffixCountを1減らします（3から2へ）。

ルール2適用後、activePointが変更されます。

Ukkonenのサフィックスツリー構築アルゴリズム - パート5の詳細

拡張ルール2のためのactivePoint変更（APCFER2）

ケース1（APCFER2C1）

activeNodeがrootで、activeLengthが0より大きい場合：

  1. activeLengthを1減少させます。
  2. activeEdgeを "S[i - remainingSuffixCount + 1]" に設定します（iは現在のフェーズ番号）。

理由：

  • 例えば、フェーズ6（i=6）で接尾辞"abx"を追加した後、次の拡張では"bx"を追加する必要があります。
  • 'b'（文字列Sの5番目の文字）が次の拡張のactiveEdgeになるべきで、そのインデックスは "i - remainingSuffixCount + 1"（6 - 2 + 1 = 5）となります。
  • activeLengthが1減少するのは、各拡張後にactivePointがrootに1文字分近づくためです。

注：activeNodeがrootでactiveLengthが0の場合は、APCFALZで既に処理されています。

ケース2（APCFER2C2）

activeNodeがrootでない場合：

  1. 現在のactiveNodeからサフィックスリンクをたどります。
  2. サフィックスリンクが指す新しいノード（rootノードまたは別の内部ノード）が次の拡張のactiveNodeになります。
  3. activeLengthとactiveEdgeは変更しません。

理由：

  • サフィックスリンクでつながれた2つのノードから下に向かう同じ文字で始まるすべてのパスのラベルは完全に同じになります。
  • したがって、これらのパス上の対応する2つの類似点について、activeEdgeとactiveLengthは同じになり、2つのノードがactiveNodeとなります。

フェーズ6の詳細な実装

  1. 拡張4：

    • 現在のactivePointは(root, a, 2)
    • APCFER2C1に基づき、次の拡張5のための新しいactivePointは(root, b, 1)になります

  2. 拡張5：

    • 追加する接尾辞は'bx'（remainingSuffixCountは2）
    • 現在の文字'x'がactivePointの後の文字と一致しないため、ルール2を適用
    • 葉エッジを作成し、新しい内部ノードも作成
    • 前の内部ノード（拡張4のもの）から新しい内部ノードへサフィックスリンクを作成
    • remainingSuffixCountを1減少（2から1へ）

  3. 拡張6：

    • 現在のactivePointは(root, b, 1)
    • APCFER2C1に基づき、次の拡張6のための新しいactivePointは(root, x, 0)になります
    • 追加する接尾辞は'x'（remainingSuffixCountは1）
    • rootからの新しいエッジとしてxを追加
    • 前の拡張の内部ノードからrootへのサフィックスリンクを作成
    • remainingSuffixCountを1減少（1から0へ）

フェーズ6の完了後、'abcabx'に対する真のサフィックスツリー（暗黙的でないツリー）が生成され、すべての接尾辞が明示的にツリーに含まれます。

重要な観察

  1. 新しく作成された内部ノードは、次の拡張の終わりまでに、サフィックスリンクを通じて別の内部ノードまたはrootを指します。
  2. サフィックスリンクは、次の接尾辞のパスラベル終点を検索する際のショートカットを提供します。
  3. 適切なactivePointの追跡により、rootからの不必要なウォークダウンを避けることができます。

次のパート5では、残りのフェーズ（7から11）を通じてツリーを完全に構築し、パート6でアルゴリズムのコードを見ていく予定です。

Ukkonenのサフィックスツリー構築アルゴリズム - パート6

この記事は以下の4つの記事の続きです：

  • Ukkonenのサフィックスツリー構築 – パート1
  • Ukkonenのサフィックスツリー構築 – パート2
  • Ukkonenのサフィックスツリー構築 – パート3
  • Ukkonenのサフィックスツリー構築 – パート4

パート1、パート2、パート3、パート4を確認してから、この記事を読むことをお勧めします。これまでに、サフィックスツリーの基本、Ukkonenのアルゴリズムの概要、サフィックスリンク、3つの実装トリック、activePointに関する詳細、そして例として文字列"abcabxabcd"を用いたサフィックスツリー構築の6つのフェーズについて見てきました。

ここでは、残りのフェーズ（7から11）を通じてツリーを完全に構築します。

フェーズ7

文字列Sから7文字目（a）を読み込みます。

  1. ENDを7に設定します（これにより拡張1、2、3、4、5、6が実行されます）。

    • 前のフェーズ6の終わりまでに6つの葉エッジがあるためです。

  2. remainingSuffixCountを1増やします（1つの拡張が残っています - 拡張7で接尾辞'a'を追加）。

  3. remainingSuffixCount回（1回）ループを実行：

    • activeLengthがZEROの場合[前のフェーズのactivePointは(root, x, 0)]、activeEdgeを現在の文字'a'に設定します（APCFALZ）。 これにより、activePointは(root, 'a', 0)になります。
    • activeNode（このフェーズ7ではroot）からactiveEdgeに対応するエッジをチェックします。
      • ない場合は葉エッジを作成します。
      • ある場合はウォークダウンします。
    • この例では、rootからエッジ'a'が存在するため、activeLengthをゼロから1に増やし（APCFER3）、処理を停止します。
    • この時点で、activePointは(root, a, 1)で、remainingSuffixCountは1のままです。

フェーズ7の終了時、remainingSuffixCountは1です（最後の接尾辞'a'は明示的に追加されていませんが、暗黙的に存在します）。

図33は、フェーズ7後の結果のツリーを示しています。

この説明は、Ukkonenのアルゴリズムのフェーズ7を詳細に示しています。特に、activePointの初期化と変更、APCFALZとAPCFER3の適用、そしてremainingSuffixCountの使用が重要です。

次のフェーズでは、これらの概念がどのように発展し、より複雑なツリー構造を構築していくかを見ていくことになります。

Ukkonenのサフィックスツリー構築アルゴリズム - パート6の続き

フェーズ8

文字列Sから8文字目（b）を読み込みます。

  1. ENDを8に設定します（これにより拡張1、2、3、4、5、6が実行されます）。
  2. remainingSuffixCountを1増やします（2つの拡張が残っています - 拡張7と8で接尾辞'ab'と'b'を追加）。
  3. remainingSuffixCount回（2回）ループを実行：
    • activeNodeからactiveEdgeに対応するエッジをチェックし、必要に応じてウォークダウンを行います。
    • 現在の文字'b'がactivePointの後に存在するかチェックし、存在する場合はactiveLengthを1から2に増やし（APCFER3）、処理を停止します（ルール3）。
    • この時点で、activePointは(root, a, 2)で、remainingSuffixCountは2のままです。

フェーズ8の終了時、remainingSuffixCountは2です（最後の2つの接尾辞'ab'と'b'は明示的に追加されていませんが、暗黙的に存在します）。

フェーズ9

文字列Sから9文字目（c）を読み込みます。

  1. ENDを9に設定します（これにより拡張1、2、3、4、5、6が実行されます）。
  2. remainingSuffixCountを1増やします（3つの拡張が残っています - 拡張7、8、9で接尾辞'abc'、'bc'、'c'を追加）。
  3. remainingSuffixCount回（3回）ループを実行：
    • activeNodeからactiveEdgeに対応するエッジをチェックし、必要に応じてウォークダウンを行います。
    • ウォークダウンが必要な場合、activePointは(Node A, c, 0)に変更されます（APCFWD）。
    • 現在の文字'c'がactivePointの後に存在するかチェックし、存在する場合はactiveLengthを0から1に増やし（APCFER3）、処理を停止します（ルール3）。
    • この時点で、activePointは(Node A, c, 1)で、remainingSuffixCountは3のままです。

フェーズ9の終了時、remainingSuffixCountは3です（最後の3つの接尾辞'abc'、'bc'、'c'は明示的に追加されていませんが、暗黙的に存在します）。

フェーズ10

文字列Sから10文字目（d）を読み込みます。

  1. ENDを10に設定します（これにより拡張1、2、3、4、5、6が実行されます）。
  2. remainingSuffixCountを1増やします（4つの拡張が残っています - 拡張7、8、9、10で接尾辞'abcd'、'bcd'、'cd'、'd'を追加）。
  3. remainingSuffixCount回（4回）ループを実行：

拡張7

  • activeNode(Node A)からactiveEdge(c)に対応するエッジをチェックします。
  • 現在の文字'd'がactivePointの後に存在しない場合、ルール2を適用し、新しい葉エッジと内部ノードを作成します。
  • 新しく作成された内部ノードcは、次の拡張8でサフィックスリンクが設定されます。
  • remainingSuffixCountを1減らします（4から3へ）。
  • activePointを更新します：新しいactivePointは(Node B, c, 1)になります（APCFER2C2）。

拡張8

  • 拡張7と同様のロジックを適用し、新しい葉エッジと内部ノードを作成します。
  • 前の拡張で作成された内部ノード(C)から、現在の拡張で作成された新しいノード(D)へサフィックスリンクを設定します。

この説明は、Ukkonenのアルゴリズムのフェーズ8から10、特に拡張7と8の詳細な実装を示しています。activePointの変更、ルール2とルール3の適用、そしてサフィックスリンクの設定が重要なポイントです。

Ukkonenのサフィックスツリー構築アルゴリズム - パート6の最終部分

フェーズ10の続き

拡張9

  • 拡張7と8と同様のロジックを適用し、新しい内部ノードEを作成します。
  • 前の拡張で作成された内部ノードDから、新しいノードEへサフィックスリンクを設定します。
  • remainingSuffixCountを1減らします（2から1へ）。
  • activePointを更新：新しいactivePointは(root, d, 0)になります（APCFER2C1）。

拡張10

  • 接尾辞'd'を追加します。rootノードから'd'で始まるエッジがないため、新しい葉エッジを作成します（ルール2）。
  • 前の拡張で作成された内部ノードEのサフィックスリンクをrootに設定します（この拡張で新しい内部ノードが作成されなかったため）。
  • remainingSuffixCountを1減らします（1から0へ）。

フェーズ10の観察

  1. サフィックスリンクでつながれた内部ノードは、その下に完全に同じ部分木を持ちます。
  2. 新しい内部ノードは、作成された拡張の次の拡張でサフィックスリンクが設定されます。
  3. すべての内部ノードは、他の内部ノードまたはrootへのサフィックスリンクを持ちます。

フェーズ11

文字列Sから11文字目（$）を読み込みます。

  1. ENDを11に設定します（これにより拡張1から10が実行されます）。
  2. remainingSuffixCountを1増やします（0から1へ）。
  3. activeLengthがZEROのため、activeEdgeを現在の文字'$'に変更します（APCFALZ）。
  4. rootノードから'$'で始まるエッジがないため、新しい葉エッジを作成します（ルール2）。
  5. remainingSuffixCountを1減らします（1から0へ）。

これで、文字列'abcabxabcd$'のすべての接尾辞がサフィックスツリーに追加されました。

サフィックスインデックスの割り当て

  • 各葉の終端に番号（サフィックスインデックス）を割り当てます。
  • この番号は、文字列S内の接尾辞の開始位置を表します。
  • DFS走査を使用して実装できます：
    • ラベルの長さを追跡し、葉の終端に到達したら、サフィックスインデックスを "文字列サイズ - ラベルサイズ + 1" として設定します。

サフィックスツリーを表現するデータ構造

サフィックスツリーには、ノード、エッジ、ラベル、サフィックスリンク、インデックスが含まれます。

主な操作/クエリ：

  1. エッジ上のパスラベルの長さを取得
  2. エッジ上のパスラベルを取得
  3. ノードから特定の文字の出力エッジがあるかチェック
  4. ノードからの特定の距離にあるエッジ上の文字値を取得
  5. 内部ノードのサフィックスリンクの行先を取得
  6. rootから葉へのパス上のサフィックスインデックスを取得
  7. 与えられた文字列がサフィックスツリーに存在するかチェック（部分文字列、接尾辞、または接頭辞として）

次のパート6では、コード実装で使用するデータ構造とコードについて議論する予定です。

Ukkonenのサフィックスツリー構築 - データ構造と実装

この記事は以下の5つの記事の続きです：

  • Ukkonenのサフィックスツリー構築 - パート1
  • Ukkonenのサフィックスツリー構築 - パート2
  • Ukkonenのサフィックスツリー構築 - パート3
  • Ukkonenのサフィックスツリー構築 - パート4
  • Ukkonenのサフィックスツリー構築 - パート5

この記事を見る前に、パート1からパート5までをご覧ください。そこでは、サフィックスツリーの基本、Ukkonenのアルゴリズムの概要、サフィックスリンク、3つの実装トリック、アクティブポイントについて見てきました。また、"abcabxabcd"という例文字列を使って、サフィックスツリー構築のすべてのフェーズを解説しました。

ここでは、サフィックスツリーを表現するために使用するデータ構造とコード実装について見ていきます。

パート5の記事の最後で、サフィックスツリーの構築中および後の異なるアプリケーションでサフィックスツリーを使用する際に行う操作のいくつかについて議論しました。

要件を満たすために考えられる異なるデータ構造があり、一部の操作では遅く、一部の操作では速いものがあるかもしれません。ここでは、実装に以下のものを使用します：

サフィックスツリーの各ノードを表現するために、SuffixTreeNode構造体を使用します。SuffixTreeNode構造体は以下のメンバーを持ちます：

  1. children - アルファベットサイズの配列です。現在のノードから異なる文字で始まる異なるエッジ上のすべての子ノードを格納します。

  2. suffixLink - サフィックスリンクを介して現在のノードが指すべき他のノードを指します。

  3. start, end - 親ノードから現在のノードへのエッジラベルの詳細を格納します。(start, end)の間隔は、ノードが親ノードに接続されているエッジを指定します。各エッジは2つのノード（親と子）を接続し、与えられたエッジの(start, end)間隔は子ノードに格納されます。例えば、A（親）とB（子）の2つのノードがインデックス(5, 8)のエッジで接続されている場合、このインデックス(5, 8)はノードBに格納されます。

  4. suffixIndex - 葉ノードの場合は非負の値となり、根からこの葉へのパスのサフィックスのインデックスを与えます。非葉ノードの場合は-1となります。

このデータ構造は、必要なクエリに素早く答えることができます：

  • ノードが根かどうかを確認する方法 - 根は特別なノードで、親がないため、startとendは-1になります。他のすべてのノードでは、startとendのインデックスは非負になります。

  • ノードが内部ノードか葉ノードかを確認する方法 - suffixIndexがここで役立ちます。内部ノードの場合は-1、葉ノードの場合は非負になります。

  • あるエッジ上のパスラベルの長さを知る方法 - 各エッジにはstartとendのインデックスがあり、パスラベルの長さはend - start + 1になります。

  • あるエッジ上のパスラベルを知る方法 - 文字列がSの場合、パスラベルはSのstartインデックスからendインデックスまでの部分文字列（[start, end]）になります。

  • ノードAから与えられた文字cに対する発信エッジがあるかどうかを確認する方法 - A->childrenがNULLでない場合はパスがあり、NULLの場合はパスがありません。

  • ノードAからある距離dにあるエッジ上の文字の値を知る方法 - ノードAからの距離dにある文字は、S[A->start + d]になります（Sは文字列）。

  • 内部ノードがサフィックスリンクを介してどこを指しているかを知る方法 - ノードAはA->suffixLinkを指します。

  • 根から葉へのパス上のサフィックスインデックスを知る方法 - パス上の葉ノードがAの場合、そのパス上のサフィックスインデックスはA->suffixIndexになります。

以下は、Ukkonenのサフィックスツリー構築のC言語による実装です。コードはコメントが多いため、少し長く見えるかもしれません。

Ukkonenのサフィックスツリー構築 - 応用と問題

サフィックスツリーを線形時間で構築できるようになったので、多くの文字列問題を効率的に解決できます：

  • テキストTの部分文字列として与えられたパターンPが存在するかチェックする（テキストが固定でパターンが変化する場合に有用、それ以外の場合はKMPアルゴリズム）
  • テキストT内に存在する与えられたパターンPのすべての出現を見つける
  • 最長の繰り返し部分文字列を見つける
  • 線形時間でのサフィックス配列の作成

上記の基本的な問題は、サフィックスツリーのDFS走査で解決できます。上記の問題や以下のような問題に関する記事をすぐに投稿する予定です：

  • 一般化サフィックスツリーの構築
  • 線形時間での最長共通部分文字列問題
  • 線形時間での最長回文部分文字列
  • その他

理解度テスト

  1. 文字列 "AABAACAADAABAAABAA$" のサフィックスツリー（適切なサフィックスリンク、サフィックスインデックス付き）を紙に描き、コード出力と一致するか確認してください。

  2. すべての拡張は、ルール1、ルール2、ルール3のいずれかに従う必要があります。以下は、あるフェーズi（i > 5）の連続する5つの拡張に適用されるルールです。どれが有効ですか？ A) ルール1, ルール2, ルール2, ルール3, ルール3 B) ルール1, ルール2, ルール2, ルール3, ルール2 C) ルール2, ルール1, ルール1, ルール3, ルール3 D) ルール1, ルール1, ルール1, ルール1, ルール1 E) ルール2, ルール2, ルール2, ルール2, ルール2 F) ルール3, ルール3, ルール3, ルール3, ルール3

  3. フェーズ5で上記の有効なシーケンスは何ですか？

  4. すべての内部ノードは、別のノード（内部ノードまたは根）にサフィックスリンクを設定する必要があります。新しく作成されたノードが既存の内部ノードを指すことはできますか？拡張jで作成された新しいノードが、次の拡張j+1で正しいサフィックスリンクを取得せず、j+2、j+3などの後の拡張で正しいものを取得することはありますか？

  5. 上記で説明した基本的な問題を解いてみてください。

サフィックスツリーのアプリケーションに関する以下の記事を公開しています：

  • サフィックスツリーアプリケーション1 - 部分文字列チェック
  • サフィックスツリーアプリケーション2 - すべてのパターンの検索
  • サフィックスツリーアプリケーション3 - 最長繰り返し部分文字列
  • サフィックスツリーアプリケーション4 - 線形時間サフィックス配列の構築
  • 一般化サフィックスツリー1
  • サフィックスツリーアプリケーション5 - 最長共通部分文字列
  • サフィックスツリーアプリケーション6 - 最長回文部分文字列