87

Tries一般にプレフィックス ツリーおよび として知られているものについて読んでいSuffix Treesます。
のコードは見つかりましたがTrie、 の例が見つかりませんSuffix Tree。Trieまた、a を構築するコードは a のコードと同じであると感じますがSuffix Tree、前者の場合は接頭辞を格納し、後者の場合は接尾辞を格納するという唯一の違いがあります。
これは本当ですか？頭の中でこれをクリアするのを手伝ってくれる人はいますか? サンプルコードは非常に役立ちます!

4

6 に答える 6

68

サフィックス ツリーは、文字列自体をトライに追加するだけでなく、その文字列のすべての可能なサフィックスも追加する、トライの上に構築されたデータ構造と見なすことができます。例として、サフィックス ツリーで文字列バナナにインデックスを付けたい場合は、次の文字列でトライを作成します。

banana
anana
nana
ana
na
a

それが完了したら、任意の n-gram を検索して、インデックス付き文字列に存在するかどうかを確認できます。つまり、n-gram 検索は、文字列のすべての可能なサフィックスのプレフィックス検索です。

これは、サフィックス ツリーを構築する最も簡単で時間のかかる方法です。このデータ構造には、スペースとビルド時間のいずれかまたは両方を改善する、より洗練されたバリアントが多数あることがわかりました。私はこの分野に精通しておらず、概要を説明することができませんが、接尾辞配列またはこのクラスの高度なデータ構造を調べることから始めることができます(講義 16 および 18)。

この回答は、このデータ構造の変形を説明する素晴らしい仕事もします。

于 2012-12-15T16:52:40.113 に答える
8

いくつかの単語のサフィックスを入れた Trie を想像すると、文字列の部分文字列を非常に簡単にクエリできるようになります。これがサフィックス ツリーの背後にある主なアイデアであり、基本的には「サフィックス トライ」です。

しかし、この素朴なアプローチを使用すると、サイズ n の文字列に対してこのツリーを構築すると O(n^2) になり、多くのメモリが必要になります。

このツリーのすべてのエントリは同じ文字列のサフィックスであるため、多くの情報を共有しているため、より効率的に作成できる最適化されたアルゴリズムがあります。たとえば、ウッコネンのアルゴリズムを使用すると、O(n) 時間の複雑さでサフィックス ツリーをオンラインで作成できます。

于 2012-12-15T17:18:29.740 に答える
1

違いは非常に簡単です。サフィックス ツリーには、サフィックス トライよりも「ダミー」ノードが少ない。これらのダミー ノードは、ツリーでのルックアップ操作を増加させる単一の文字です。

于 2016-01-11T22:24:23.300 に答える
0

特定のテキストのサフィックス ツリーは、特定のテキストのすべてのサフィックスの圧縮されたトライです。

参照: https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/

于 2021-04-04T21:30:19.940 に答える