私は約Triesと一般に知られているPrefix treesとSuffix Treesです。
Trieのコードが見つかりましたが、Suffix Treeの例は見つかりません。また、Trieを構成するコードがSuffix Treeのコードと同じであるという唯一の違いは、前者の場合は接頭辞が格納されているが後者の接尾辞は同じであるという感覚を得る。
これは本当ですか？誰かが私の頭の中でこれをクリアするのを助けることができますか？サンプルコードは大きな助けになるでしょう！接尾辞ツリーと試行。違いはなんですか？
サフィックスツリーは、文字列自体をトライに追加するのではなく、その文字列のすべての可能な接尾辞を追加するトライの上に構築されたデータ構造として見ることができます。それはあなたが任意のnグラムを検索し、かどうかを確認することができます完了だ後は
banana
anana
nana
ana
na
a
：あなたは接尾辞木にインデックスに文字列バナナを望んでいた場合の例として、次のような文字列でトライを構築しますそれはあなたのインデックス文字列に存在します。つまり、nグラム検索は、文字列のすべての可能な接尾辞のプレフィックス検索です。
これは、サフィックスツリーを構築する最も簡単で最速の方法です。このデータ構造には、スペースとビルド時間のどちらか一方、または両方を改善する多くのより派手な変形があることが判明しました。私は十分に精通しているわけではありませんが、suffix arraysまたはこのクラスadvanced data structures（講義16と18）に目を通すことから始めることができます。
このanswerも、このデータ構造の変種を説明するすばらしい仕事をしています。
これは私が疑っているものです。トライはサフィックスツリーを構築するために使用されています。そのため、ほとんどの教科書では試行のコードしか提供されていません。しかし、これは最悪の実装です。 – Cratylus
@Cratylusサフィックスの木は、非常に大きな文字列（例えば、シェイクスピアのすべての作品のインデックス作成）で最も役に立ちます。ここで、O（n^2）のスペースとビルド時間は単純にカットしません。幸運なことに、これらの範囲はかなり小さくすることができます。 –
単語のサフィックスを入れるTrieを想像すると、文字列の部分文字列を非常に簡単に検索することができます。これは接尾辞ツリーの背後にある主なアイデアです。基本的に接尾辞トライです。
しかし、この素朴なアプローチを使用すると、サイズnの文字列に対してこのツリーを構築すると、O（n^2）となり、多くのメモリが必要になります。
このツリーのすべてのエントリは同じ文字列の接尾辞なので、多くの情報が共有されるため、より効率的に作成できる最適化アルゴリズムがあります。たとえば、Ukkonenのアルゴリズムでは、O（n）時間の複雑さでサフィックスツリーをオンラインで作成することができます。
サフィックスの木と接尾辞の試行は同じだと言っていますか？ – batman
違いは非常に簡単です。接尾辞ツリーは接尾辞トライよりも「ダミー」ノードが少ない。これらのダミーノードは、ツリー上のルックアップ操作を増加させる単一の文字です
TL; DR文字列の接尾辞ツリーは、すべての[patricia trie]（https://en.wikipedia.org/wiki/Radix_tree）です。接尾辞。それについての唯一の特別なことは、エッジラベルが元の文字列の部分文字列であるため、インデックスのペアとして表現でき、一定のスペースしか取れないことです。これはまた、線形時間で構築できる理由です。 –