java - 在java中构建trie

Question

如何从文件构造树？我希望能够从文件中读取它们，然后添加到适当的级别

Answer 1

在我看来，您正在尝试实施 trie。

在这里寻找一个很好的java实现：http ://www.cs.duke.edu/~ola/courses/cps108/fall96/joggle/trie/Trie.java

Answer 2

添加

从根开始，搜索第一个（或当前）字母。如果找到该字母，则移动到该节点并搜索下一个字母。如果没有找到该字母，则搜索与当前字母匹配的单词，如果有相似的单词，则将当前字母添加为新节点并将两个单词移到其下，否则添加该单词。

注意：这将产生一个比示例中显示的树更适合搜索的树。（adamant 和 adapt 将分组在另一个 'a' 节点下）

更新：查看关于Trie的 Wikipedia 文章

Answer 3

如果在叶子（实际单词）之前的树中只有两个级别，则可以简单地从包含 28 个元素的数组开始，并将字母转换为索引（即 a==1、b==2 等）。数组元素可以是一些包含完整单词的集合/列表。您可以懒惰地创建数组和列表（即创建根数组，但其他数组和单词列表为空值，然后在需要时/如果需要创建数组/列表）。

我是否在阅读您应该正确遵守的规则？

PS我认为使用每个全尺寸的数组不会太浪费空间，而且它应该很快解决

更新：@user1747976，每个数组大约需要 28*4 或 28*8 位 + 12 字节开销。希望您使用压缩操作，因此每个数组是 28*4+12=116bytes。现在取决于您是想提高内存效率还是提高处理效率。为了提高内存效率，您可以使用某种哈希图而不是数组，但我不确定额外的开销是否会小于使用数组的开销。处理肯定会更糟。您需要根据树部门的要求多次使用一些巧妙的循环。一些用于插入树的丑陋伪代码：

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];
   }
}

您可以使用类似的循环来检索单词。