創建樹形數據結構

Question

我有一些數據：

A 
AXNHJNEHWXNOECMEJK 
DNFJNXYEEQWhsdbchjsxs 
XMJQWsdsEOJdfsKMDJE 

....

每一行是陣列，並且每個信對象。我有比較函數可以說字母A是字母a的等值（實際上它不是字母，它是俄語單詞和比較函數使用形態學讓我知道單詞是相等的，例如матрешка==матрешки==матрешкины和數組是俄語句子，例如：「Мамамылараму」）。我想要創建如下的樹形數據結構：

1) A 
2.1) BA 
2.2) DHBAFH 
3.1) BEDMEWA 
etc... 

否則，子節點必須包含來自父節點的字母。如果你知道如何工作谷歌AdWords，我認爲你可以理解我。我的問題是如何做到這一點。我需要用數千個數組創建樹。比較功能工作非常慢（它使用大字典），這就是爲什麼速度是真正的問題。

一些簡單的數據（對不起，俄語）：

這裏設置的句子

сайты   
сайты недорого 
сайты дешево 
сайты дешево и быстро 
красивый сайт по доступным ценам 
хочу купить хороший стул 
стул по доступным ценам 

我們必須創建下面的樹數據結構

1) сайты 
1->2.1) сайты недорого 
1->2.2) сайты дешево 
1->2.3) красивый сайт по доступным ценам 
1->2.2->3) сайты дешево и быстро 

其他父節點：

1) хочу купить хороший стул 
1) стул по доступным ценам 

子節點必須包含更多的單詞，然後是父級。

Answer 1

好，

看來，這個環節可能是你的問題有幫助

的快速字符串搜索後綴樹：http://marknelson.us/1996/08/01/suffix-trees/

和

後綴樹

http://en.wikipedia.org/wiki/Suffix_tree

Answer 2

從包含一個單詞的句子開始。他們都將成爲父節點，所以這很簡單。

然後繼續兩個單詞的句子。您必須將每個單詞父節點與每個單詞父節點進行匹配，因爲您的比較函數比較慢，所以這會非常緩慢。雖然你可以做兩個優化：首先檢查是否正好與相同。你可以自己做，它會很快。另一個是記住每對比較單詞的比較函數的結果。你會浪費一些記憶，但你會獲得一些速度。

當節點匹配時，將句子添加到它。當句子不匹配任何節點時，將其設爲父節點。

對於具有逐漸增加的長度的句子，除了必須嘗試匹配節點的匹配子節點以找到添加句子的正確位置之外，您也是這樣做的。