15

我开始阅读有关 Trie 的信息。我还从这里的朋友那里得到了参考：Trie 教程

我不清楚以下几点：
似乎继续使用 Trie 假设所有将成为搜索空间并用于构建 Trie 的输入字符串都以不同的单词边界分隔。
例如，我见过的所有示例教程都使用输入，例如： 

S={ball, bid, byte, car, cat, mac, map etc...}

然后我们构建特里树S并进行搜索（非常快）
我的问题是：我们最终是如何S开始的？
我的意思是在开始阅读尝试之前，我想象这S将是一个任意长的文本，例如Shakespeare一段。

然后使用 Trie，我们可以非常快速地找到东西。
但似乎情况并非如此。

这里的假设是输入段落（Shakespeare例如）首先被预处理提取所有单词以获得S？

所以如果一个人想要搜索模式（就像你在谷歌上搜索并看到所有页面在你的搜索查询中也有空格一样），那么 Trie 不合适吗？
我们什么时候可以知道 Trie 是否是我们可以实际使用的数据结构？

4

4 回答 4

12

如果您有一个固定的字典，您想快速查找，尝试是很有用的。与哈希表相比，大型字典可能需要更少的存储空间，但查找时间可能更长。我使用它的一个例子是将 URL 映射到 Web 服务器上的操作，如果可能存在基于前缀的功能继承。在这里递归一个 trie 可以适当地查找需要为特定 url 调用的所有方法。存储字典也很有效。

对于进行文本搜索，您通常会使用具有权重的词法标记向量（可能基于出现频率）来表示文档，然后针对该词进行搜索以获得针对特定搜索向量的文档排名。有许多标准库可以做到这一点，我建议使用而不是自己编写 - 特别是用于删除停用词、处理同义词和词干。

于 2012-05-22T07:48:27.967 回答
2

我们可以使用尝试在线性时间内进行子字符串搜索，而无需每次都对字符串进行预处理。你可以得到一个关于后缀树生成的最佳教程 @Ukkonen 的简单英语的后缀树算法？

于 2012-05-22T07:39:11.600 回答
2

正如其他示例所说，trie 很有用，因为它提供了快速的字符串查找（或更一般地，查找任何序列）。我使用过的一些示例：

  • 我对这个问题的回答使用（稍微修改的）trie 来匹配句子：它是基于单词序列而不是字符序列的 trie。（该问题的其他答案可能更清楚地证明了这种尝试。）
  • 我还在一个游戏中使用了 trie，该游戏有大量带有名称的房间（总数和名称是在运行时定义的），这些名称中的每一个都必须是唯一的，并且必须能够搜索一个给定名字的房间。也可以使用哈希表，但在某些方面，使用字符串时 trie 更易于实现且速度更快。（我的 trie 实现最终是大约 50 行 C。）

标签可能还有更多示例。

于 2012-05-22T08:26:08.183 回答
2

有多种使用尝试的方法。典型的例子是一个查找，例如您提供的那个。然而，Tries 也可以用来完全索引一个完整的文本。要么使用 Ukkonen 后缀树算法来生成后缀树，要么通过存储后缀来显式构造后缀树（比 Ukkonens 算法慢得多，但也简单得多）。由于这是预处理，因此只需要在速度不是那么关键的情况下进行一次。

为此，您只需获取文本，插入全文，然后切掉第一个字母，插入生成的文本，切掉第二个字母，插入...

因此，如果我们有文本“The Text”，我们将插入以下集合：

{"The Text", "he Text", "e Text", " Text", "Text", "ext", "xt", "t"}

在生成的后缀 trie 中，我们可以轻松搜索任何类型的前缀。这也是节省空间的，因为我们不需要存储整个字符串，因为公共前缀只存储一次。

如果您需要有效地存储更长的字符串空间，最好不仅将前缀存储在一起，而且还存储后缀。在这种情况下，您可以构建一个有向无环词图 (DAWG)，它与概念中的 trie 非常相似。

因此，这种意义上的 trie 允许查找任意子字符串，包括部分单词。如果您只对存储单词感兴趣，则应使用不同的数据结构，例如倒排列表（如果顺序很重要）或基于向量空间的检索算法（如果单词顺序无关紧要）。

于 2012-05-22T12:45:28.520 回答