java中的trie構建

Question

如何從文件構建樹？我希望能夠從文件中讀取它們，然後添加到適當的水平

Answer 1

在我看來，你正在試圖執行trie。

在這裏看到java的一個很好的實現：http://www.cs.duke.edu/~ola/courses/cps108/fall96/joggle/trie/Trie.java

Answer 2

添加

在根開始，搜索第一（或電流）的來信。如果找到該字母，則轉到該節點並搜索下一個字母。如果未找到該字母，則搜索與當前字母匹配的單詞，如果有相似的單詞，則將當前字母添加爲新節點，然後將該單詞移到該單詞下方，否則添加該單詞。

注意：這將導致爲搜索更優化的樹，然後顯示示例中顯示的樹。 （金剛和調整將在另一個「一」節點進行分組）

更新：看看維基百科文章Trie

Answer 3

如果你有樹只有兩個級別葉前（實際單詞），你可以簡單地從具有28個元素的數組開始，並將這些字母轉換爲索引（即a == 1，b == 2等）。數組的元素可以是一些包含完整單詞的集合/列表。您可以懶洋洋地創建數組和列表（即創建根數組，但對其他數組和列表有空值，然後在需要時創建數組/列表）。

我讀的規則，你應該遵循正確嗎？

P.S.我認爲使用全尺寸的陣列在空間上不會太浪費，它應該是非常快的地址

更新：@ user1747976，以及每個陣列需要約28 * 4或28 * 8位+ 12字節overhead。希望你使用壓縮操作，所以它是每個陣列28 * 4 + 12 = 116bytes。現在，這取決於您是否想要提高內存效率或處理效率。爲了提高內存效率，你可以使用某種類型的hashmap來代替數組，但我不確定額外的開銷會比使用數組少。處理將肯定會更糟。 根據樹部門的要求，您需要多次使用一些巧妙的循環。用於插入樹的一些難看的僞代碼：

root=new Object[28]; 
word="something"; 
pos = root; 
wordInd=1; 
for (int i=1; i<=TREE_DEPTH ; i++) { 
    targetpos = letterInd(letter(wordInd,word)); 
    if (i==TREE_DEPTH) { 
     if (pos[targetpos] == null) pos[targetpos] = new HashSet<String>(); 
     (Set) pos[targetpos].add(word); 
     break; 
    } else { 
     if (pos[targetpos] == null) pos[targetpos] = new Object[28]; 
     wordInd++; 
     pos = pos[targetpos]; 
    } 
} 

您可以用於檢索單詞的類似循環。