[解決済み] サフィックスの木とトライ。その違いとは？

質問

について読んでいます。 Tries 一般に接頭辞ツリーと呼ばれるもので Suffix Trees .

のコードを見つけたものの Trie の例は見つかりませんでした。 Suffix Tree . また、私は Trie を構築するコードは Suffix Tree の場合と同じです。唯一の違いは、前者では接頭辞を、後者では接尾辞を格納することです。

これは本当でしょうか？誰か私の頭の中でこれをクリアにするのを助けることができますか？コード例があれば、とても助かります!

どのように解決するのですか？

サフィックスツリーはトライの上に構築されたデータ構造とみなすことができます。トライに文字列そのものを追加する代わりに、その文字列のすべての可能なサフィックスを追加することになります。例えば、文字列 バナナ という文字列をサフィックスツリーでインデックスしたい場合、以下のような文字列でトライを構築することになります。

banana
anana
nana
ana
na
a

これが終わると、任意のn-gramを検索して、それがインデックスされた文字列の中に存在するかどうかを見ることができます。言い換えれば、n-gram検索は文字列のすべての可能な接尾辞の前方一致検索となります。

これは接尾辞ツリーを構築する最も単純で最も遅い方法です。このデータ構造には、空間と構築時間のいずれかまたは両方を改善する、よりファンシーなバリエーションが多数あることが判明しています。私はこの分野に詳しくないので概要を説明することはできませんが、まずは サフィックス配列 またはこのクラス 高度なデータ構造 (講義16と18)を受講してください。

この 答え は、このデータ構造のバリエーションを説明する素晴らしい仕事も行っています。