10

我在大学里最喜欢的数据结构之一是Trie。如果前缀是共享的，它是一个很好的数据结构，用于保存大量字符串。查找也很好，因为无论集合中有多少字符串，它们都是在字符串的 O(|length|) 处完成的。

相比之下，平衡树的设置项目数量为 O(log N)，加上您为比较支付的任何费用。哈希表将涉及哈希计算、比较等。

因此，令我惊讶的是，大多数语言的标准库中都没有 Trie 实现。

我能想出的唯一原因是内存访问成本可能使其过于昂贵。如果进行树查找，而不是调查 O(log N) 个位置，而不是执行 O(|length|) 个不同的位置，这会带来所有后果。如果字符串很长，这最终可能会太多。

所以我想知道：我刚才描述的问题有多少？当您需要存储大量字符串或字符串时，您会怎么做？

4

5 回答 5

7

以前我不认为这是一个值得关注的领域，但现在你提到它，有时标准的 Trie 实现可能会很方便。另一方面，据我所知，Python 和 Perl 以及我现在使用的其他精通字符串的语言都使用 Tries。

最后我检查了一下，那是很久以前的事了，BSD 内核代码在代码中使用了 Tries (Patricia Tries) 来选择发送数据包的最佳接口。看起来维基百科有一些信息。

于 2009-03-09T00:16:04.150 回答
4

您可以只构建两个示例应用程序，然后看看哪一个表现更好。假设您没有页面错误，内存访问很便宜。然后它非常昂贵。对于客户端应用程序开发，出于这个原因，处理几乎总是比访问内存更好。现代处理器速度快得离谱，但缓存未命中仍然会受到伤害。

于 2009-03-09T00:13:59.913 回答
2

我在 C# 中使用 Trie 和 Dictionary（强类型哈希表）进行了一些性能测试。我发现 Dictionary 比 Trie 快 5-10 倍。也许我对 Trie 的实现可以稍微优化一下，但还不足以比字典快得多（或者甚至快得多）。

字典中的 ContainsKey 方法接近于 O(1) 操作（取决于散列算法的好坏），因此只要散列算法相当快，就不容易制作出一个优于该值的集合。

使用自定义 IEqualityComparer，您可以将大多数任何内容用作字典中的键，这使得它相当灵活。Trie 在您可以用作键的方面受到更多限制，因此在一定程度上限制了有用性。

于 2009-03-09T08:45:00.183 回答
0

尝试对于 IP 地址和子网查找特别有用，并且始终适用于任何架构。您可以在The open-source IPAddress Java library中找到地址的 trie 实现。免责声明：我是那个图书馆的项目经理。

尝试按地址前缀组织，如下例所示：

● 0.0.0.0/0 (10)
└─○ 0.0.0.0/1 (9)
  ├─○ 8.0.0.0/6 (8)
  │ ├─● 8.9.8.0/24 (7)
  │ │ └─○ 8.9.8.0/28 (6)
  │ │   ├─● 8.9.8.0/29 (1)
  │ │   └─● 8.9.8.8/29 (5)
  │ │     ├─○ 8.9.8.8/30 (2)
  │ │     │ ├─● 8.9.8.9 (1)
  │ │     │ └─● 8.9.8.10 (1)
  │ │     └─● 8.9.8.12/30 (2)
  │ │       └─● 8.9.8.12/31 (1)
  │ └─● 10.0.2.15 (1)
  └─● 127.0.0.1 (1)

该结构允许有效的查找、路由和包含检查。

于 2021-01-29T03:26:35.217 回答
0

很难使标准的 Trie 类具有广泛的用途，足以证明将其放入标准库是合理的。

当然，它需要您放入其中的任何内容来实现一个通用的类似字符串的接口。

而且由于 Trie 实际上并不存储字符串，因此迭代它要么很慢，因为它必须重构所有元素，要么很尴尬，因为你实际上并没有得到字符串。

而且，您知道，average_length 和 max_length 都至少为 O(log N)。如果您知道元素是字符串，那么您可以在 O(length + log N) 中搜索 BST，这与 O(length) 几乎相同，并且您保留了结构中实际包含字符串的优势。

Tries真正赢得的唯一优势是具有长公共前缀的字符串的内存高效存储。它会发生，但并不常见。我想没有一种语言认为值得麻烦包括一种。

于 2021-01-29T04:07:09.183 回答