4

使用嵌套哈希映射创建 TRIE 有什么好处？

例如，让我们有一个嵌套的哈希映射，其中每个映射只有一个字符的键。myHashMap['d']['o']['g']['*'] = True所以对于“狗”这个词，我们会有类似的东西。末尾的“*”表示条目的结尾。

在书中，我从未见过这种方法，而是“经典”的 Node 类。为什么？

4

4 回答 4

2

这是一个很好的问题，也是我目前正在思考的一个问题。

Glenn 的回答没有考虑 Trie （或前缀树，给它另一个名字）的前缀存储性质。如果你想要的只是一本字典，那么 Hashtable 是一个更好的选择，但如果你想做一些自动完成风格的事情，那么 Trie 是理想的选择。我对需要对其进行排序的 Trie 也一无所知。

我想您所指的“经典”方法是使用字符索引数组 O(1) 查找来引用任何节点的子节点之一。这对于小型字母来说是快速且节省空间的，但正如您所观察到的那样，对于非常大的字符集 (Unicode) 来说，空间很快就会变得令人望而却步。

您提到的一种替代方法是在每个节点上都有一个 HashMap ，将每个字符映射到一个子节点。您保留了索引数组的恒定查找时间（假设一个真正的哈希实现），并且您希望每个节点不使用数千个字节来存储空字符槽。

对我来说似乎是一场全面的胜利，所以我也想知道为什么我不经常看到它被提及。

我确实考虑过的一种混合方法是，如果您预先知道整个字母表，则保留 char->array 索引（子数组的连续索引）的哈希映射，以实现两全其美。只需预先扫描您的字典，然后告诉 Trie 您将在构建时使用哪些 unicode 字符。

于 2014-01-21T15:17:34.603 回答
2

我用

Map<Character, TrieMap<K, V>> children = new TreeMap<>();

对于我实施的TrieMap. 它工作得很好。

使用普通Node结构的好处是您可以将指向父地图的链接包装到结构中，这样您就可以更轻松地迭代地图。我没有采取那条路线并构建一段Stack时间的迭代，因为我想确保我不会用不必要的内容使结构膨胀。然后我在迭代时构建堆栈。

a 的主要好处Trie是当按键相似时它可以节省空间 - 在我看来，给结构增加不必要的重量是愚蠢的。因此我决定只使用TreeMap. 另一种选择是 a ，Array或者List但对我来说，TreeMap当数据为 a 设计得很好时，它们都不像 a 那样节省空间Trie。

实际上 - 代码看起来更像：

/**
 * Map each character to a sub-trie.
 *
 * Could replace this with a 256 entry array of Tries but this will handle multi-byte character sets and I can discard
 * empty maps.
 *
 * Maintained at null until needed (for better memory footprint).
 *
 */
private Map<Character, TrieMap<K, V>> children = null;

....

/**
 * Create a new set of children.
 *
 * I've always wanted to name a method something like this.
 */
private void makeChildren() {
  if (children == null) {
    // Use a TreeMap to ensure sorted iteration.
    children = new TreeMap<>();
  }
}

因此，我通过确保无子节点不会保留浪费的空值来进一步减少内存占用Map（尽管我可以很容易地使用Collections.emptyMap()）。

于 2014-01-21T15:36:55.093 回答
0

如果每个节点只有 256 个条目，你为什么要考虑使用 hashmap？如果你让哈希图更小，你会增加在较低节点发生冲突的风险，并且好的属性就消失了……如果你让它动态化，你会得到所有的管理开销……

于 2013-11-11T00:59:17.273 回答
0
  1. 当你声明你的嵌套哈希图时——你会做多深如果它不是一个固定的深度——那么你刚刚复制了一个使用哈希图作为节点的“节点”方法
  2. hashmap->hashmap->hashmap 将占用更多空间并且比仅使用字符串散列更慢。
  3. Hashmaps 没有排序 - 所以现在你有一个未排序的地图，这真的不是一个 trie
于 2013-11-13T19:59:22.393 回答