regex - 我们什么时候真正使用 Trie 树？

Question

我开始阅读有关 Trie 的信息。我还从这里的 friend 那里得到了引用:Tutorials on Trie

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

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

然后我们从 S 构建 trie 并进行搜索(非常快)
我的问题是:我们是如何以 S 开始的？
我的意思是，在开始阅读关于尝试的文章之前，我想象 S 将是一个任意长的文本，例如莎士比亚 段落。

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

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

因此，如果有人想搜索模式(就像您在 Google 上看到所有页面在您的搜索查询中也有空格时所做的那样)，那么 Trie 不合适吗？
我们什么时候才能知道 Trie 是不是我们真正可以使用的数据结构？

Answer 1

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

对于进行文本搜索，您通常会使用带权重的词法标记向量(可能基于出现频率)来表示文档，然后针对该向量进行搜索以获得针对特定搜索向量的文档排名。有许多标准库可以执行此操作，我建议使用它们而不是自己编写 - 特别是用于删除停用词、处理同义词和词干提取。