Trie與後綴樹與後綴數組

Question

哪種結構可提供最佳性能結果; trie（前綴樹），後綴樹還是後綴數組？還有其他類似的結構嗎？這些結構的Java實現是什麼？

編輯：在這種情況下，我想打一個大字典的名稱和一個大集自然語言文本之間的字符串匹配，以便查明在文本詞典的名字。

Answer 1

這個trie是這種被發現的第一個數據結構。

後綴樹是對trie的改進（它具有允許線性錯誤搜索的後綴鏈接，後綴樹修剪了trie的不必要的分支，因此它不需要太多的空間）。

後綴陣列是基於後綴樹一個精簡的數據結構（無後綴鏈路（慢錯誤匹配），但是模式匹配是非常快）。

特里並不適合現實世界使用，因爲它消耗太多空間。

後綴樹比trie更輕更快，用於索引DNA或優化一些大型的網絡搜索引擎。

後綴數組在某些模式搜索中比後綴樹慢，但使用的空間較少，並且比後綴樹更廣泛地使用。

在同一個家庭的數據結構：

還有其他的實現中，CST是使用後綴數組和一些額外的數據結構來獲得一些後綴樹的搜索功能後綴樹的實現。

FCST更進一步，它實現了帶後綴數組的採樣後綴樹。

DFCST是FCST的動態版本。

擴大：

兩個重要因素是空間使用和操作執行時間。你可能認爲，用現代機器這不是相關的，但索引單個人的DNA將需要40千兆字節的內存（使用未壓縮和未優化的後綴樹）。而要在這麼多的數據上構建其中的一個索引可能需要幾天時間。想象一下Google，它有很多可搜索的數據，它們需要對所有網絡數據有一個大的索引，並且每次有人構建網頁時都不會改變它。他們有某種形式的緩存。但主要指標可能是靜態的。每隔幾個星期左右他們就會收集所有新的網站和數據，並建立一個新的索引，在完成新的索引時替換舊的索引。我不知道他們使用哪種算法進行索引，但它可能是在分區數據庫中具有後綴樹屬性的後綴數組。

CST使用8千兆字節，但後綴樹操作速度大大降低。

後綴數組可以在700 megas到2 Gigas中執行相同的操作。然而，你不會在帶有後綴數組的DNA中發現遺傳錯誤（意思是：用通配符搜索模式要慢得多）。

FCST（完全壓縮的後綴樹）可以創建800到1.5 gigas的後綴樹。 CST的速度相對較小。

DFCST使用比FCST多20％的空間，並且速度減慢到FCST的靜態實現（但動態索引非常重要）。

後綴樹沒有太多可行的（空間明智的）實現，因爲它很難使操作速度提高來補償數據結構的RAM空間成本。

這就是說，後綴樹具有非常有趣的模式匹配搜索結果與錯誤。 aho corasick沒有那麼快（儘管對於某些操作來說速度幾乎一樣快，而不是錯誤匹配），而且Boyer摩爾被留在塵土中。

Answer 2

使用後綴樹，你可以寫的東西，將符合您的字典文本在O（N + M + k）的時間，其中n是字母在你的字典裏，m是在你的文字字母，k是數量火柴。嘗試對此慢得多。我不確定後綴數組是什麼，所以我不能對此發表評論。

這就是說，這是代碼不平凡，我不知道任何Java庫提供必要的功能。

Answer 3

編輯：在這種情況下，我想打一個大字典的名稱和一大套的 自然語言文本之間的字符串匹配，以便查明在文本詞典的名字。

這聽起來像是爲Aho-Corasick algorithm的應用程序：構建從字典的自動機（線性時間），其然後可以被用於發現的任何的在多個文本字典字所有出現（也以線性時間）。

（在these lecture notes的描述，從維基百科頁面的「外部鏈接」部分聯繫在一起，是一個更容易比頁面本身的描述閱讀。）

Answer 4

你打算做什麼操作？ libdivsufsort曾經是C中最好的後綴數組實現。

Answer 5

This實施誘導排序算法（稱爲sais）有一個用於構建後綴數組的Java版本。

Answer 6

特里VS後綴樹

兩個數據結構，確保一個非常快的查找，搜索的時間是成正比的查詢詞，複雜時間O（M）的lenght其中m爲查詢的lenght字。

這意味着如果我們有查詢詞有10個字符，所以我們最多需要10個步驟才能找到它。

Trie：用於存儲字符串的樹，其中每個公共前綴有一個節點。字符串存儲在額外的葉節點中。

suffix tree：對應於給定字符串的後綴的樹狀結構的緊湊表示，其中具有一個子元素的所有節點都與其父元素合併。

DEF是從： 字典算法與數據結構的

通常Trie的用於索引字典中的單詞（詞彙）或字符串 例如d = {ABCD，abcdd，bxcdf的任何集合，.....，ZZZZ}

通過使用相同的數據結構 「Trie樹」 在我們的文本T = {abcdabcg，abcdabc，abcdab，ABCDA，ABCD T = abcdabcg 所有後綴的所有後綴來索引文本後綴樹， abc，ab，a}

現在它看起來像一組字符串。 我們在這組字符串（T的所有後綴）上構建了一個Trie。

兩種數據結構的構造都是線性的，它在時間和空間上都需要O（n）。

在dicionary（一組字符串）的情況下：n =所有單詞的字符總和。文本中的 ：n =文本的長度。

後綴數組：是一種表示壓縮sapce中的後綴樹的技術，它是一個包含字符串後綴的所有起始位置的數組。

它在搜索時間內比後綴樹慢。

欲瞭解更多信息，請轉至維基百科，有一篇關於此主題的優秀文章。