一般化された接尾辞木
1. 序章
このチュートリアルでは、一般化されたサフィックスツリーとは何か、および最長の共通サブストリングを見つけるためにそれを使用する方法の例を探ります。 最長の共通部分文字列の検索は、文字列類似性メソッドから共通サブシーケンスの検索の特殊なケースです。このクラスのメソッドの「シーケンス」は部分文字列です。
最長の共通部分文字列を見つけることで、一般化された接尾辞木のアプリケーションを説明します。
次に、最初にサフィックストライとパトリシアトライを構築し（フィールドの用語を使用）、次にこれらのツリーに注釈を付けて一般化されたサフィックスツリーを形成することにより、一般化されたサフィックスツリーを構築します。
2. 接尾辞の試行
最初の質問に答えるために、いいえ、「ツリー」という単語のスペルを間違えませんでした。 接尾辞木の言語では、 trie は、タスクに使用できる完全に一般化された接尾辞木を構築するための中間体です。 接尾辞トライは、エッジ、つまりノードを接続する線が接尾辞の文字でラベル付けされているツリーです。
各接尾辞をたどり、最上位ノードから始めて各文字のエッジを作成することにより、接尾辞ツリーを構築します。 ツリーに配置される新しい接尾辞が、すでにツリーにある文字のセットで始まる場合、別の文字ができるまでそれらの文字をたどり、新しいブランチを作成します。
これは例で最もよく説明されます。 という言葉を使います。 この単語には8つの接尾辞と、空の接尾辞（$で示される）があります。
- $
- e
- se
- nse
- ense
- 検出
- nsense
- オンセンス
- ナンセンス
開始ノードと$でラベル付けされた空白の接尾辞を使用して接尾辞trieの作成を開始します。
次に、接尾辞トライがビルドアップされ、接尾辞の最初の文字が開始ノードに接続されます。 空でない最初の3つのサフィックスはすべて異なる文字で始まることがわかるので、空白のブランチに3つのブランチを追加します。
次の接尾辞は、で始まります。これには、開始ノードからのノードがすでに含まれています。 これをノードへのブランチとして追加するには、接尾辞の共通部分（この場合はちょうど）をたどり、文字が異なる場所に追加のブランチを追加します。
接尾辞が異なるブランチを追加し、必要に応じて新しいブランチを追加することで、このプロセスを続行します。 完了すると、次のようになります。
ここでは、で始まる3つのサフィックスがあることがわかります。 共通の部分文字列セクションがある場合、それらはforやsuffixなどの同じ分岐に従うことがわかります。
また、文字列のサイズが、の場合、接尾辞木には正確にリーフノードがあることがわかります。 の場合、ノードを持つツリーを構築しました。 アルゴリズムの複雑さは、ノードの数によって異なります。 したがって、次の質問をすることができます。
トライ内のノードの数を減らすことはできますか？
次のセクションで説明する答えは、「パトリシアトライ」と呼ばれるものを構築することです。
3. パトリシアトライ
Patricia trieは、子が1つだけ（分岐なし）のすべての「単純な」ノードがグループ化された接尾辞木です。 この例では、次のようになります。
ノードの数は減っていますが、リーフノードの数は同じです。つまり、接尾辞の数です。 Patriciaトライの構築は、接尾辞木（および一般化された接尾辞木）を構築するためのステップです。これは、部分文字列認識の多数のタスクを実行するために使用されます。
4. 接尾辞木
サフィックスツリーを使用すると、部分文字列認識タスクを容易にするためのデータ構造の作成に一歩近づきます。 文字列の接尾辞木は、対応する接尾辞がで始まるインデックスで各リーフにラベルが付けられているパトリシアトライです。 このラベルは、元のサフィックスへの直接参照を提供します。
5. 一般化された接尾辞木
接尾辞木には、単一の文字列の説明しかありません。 ただし、上記のデータ構造の一般化されたバージョンを使用して、複数の文字列にインデックスを付けることができます。 この場合、検索操作の結果は、指定された入力文字列を含む文字列への参照になる可能性があります。
の一般化された接尾辞木はの接尾辞木ですが、リーフノードのラベルには、文字列内の位置だけでなく、参照している文字列のインデックスもあります。 葉には、「文字列の接尾辞」を意味する「」というラベルが付いています。
これを、2つの文字列を持つ一般化された接尾辞木で説明します。
6. 最長の共通部分文字列
一般化された接尾辞木を使用して、部分文字列の認識を容易にすることができます。 主な考え方は、1つの文字列内のすべてのサブ文字列が、その文字列の接尾辞のプレフィックスであるということです。 言い換えると、ツリーにすべての接尾辞を配置する場合、接尾辞のすべての開始文字をツリーの最上部（開始ノードに接続）にも配置します。 接尾辞のこれらの開始文字は、接頭辞の開始でもあります。 2つのサブストリングは、ツリーの下で部分的に一致する必要があります。
最長の共通部分文字列を見つけるアルゴリズムには、次の3つのステップがあります。
- およびの一般化された接尾辞木を作成します。
- ツリー内の各内部ノードに、そのノードにとのそれぞれから少なくとも1つのリーフノードがあるかどうかを注釈します。
- ツリーに対して深さ優先探索を実行して、文字列の深さが最も高いマークされたノードを見つけます。
この例を使用して、2つの文字列、、およびを使用して一般化された接尾辞木を作成します。 次に、各ノードに、そのブランチに文字列のみ、文字列のみ、または両方の文字列があるかどうかを注釈します。
ツリー（深さ優先探索）を見ると、最も長い共通の部分文字列を表す赤いノードがあります。 緑のノードは短い文字列、およびを表します。 基数木が凝縮されているため、同じレベルで表示されます。
7. 結論
この記事では、部分文字列認識の問題を解決するために一般化された接尾辞木を構築する方法の概要を説明しました。 ここで概説したのは、一般化された接尾辞木を生成する簡単な方法でしたが、ヘルシンキ大学の接尾辞木のオンライン構築など、アルゴリズムを高速化するための高度なトリックがたくさんあります。
