我们什么时候使用Trie？

我开始阅读关于Trie。 我在这里也得到了朋友的参考资料：关于Trie的教程

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

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

然后，我们从S构建trie并执行搜索（非常快）
我的问题是：我们是如何以S开头的？
我的意思是在开始阅读有关尝试之前，我想象S将是一个任意长的文本，例如Shakespeare一段。

然后使用Trie我们可以快速找到事情。
但似乎并非如此。

这里假定输入通道（例如Shakespeare ）是经过预处理的，首先提取所有单词以获得S ？

因此，如果有人想要搜索模式（与Google时的方式相同，并且您的搜索查询中的所有网页都有空格），Trie是不合适的？
我们什么时候才能知道Trie是否是我们实际可以使用的数据结构？

---

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

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

---

我们可以在线性时间内使用try来进行子字符串搜索，而不需要每次都预处理字符串。 你可以用简单的英语获得后缀树生成@ Ukkonen后缀树算法的最佳教程吗？

---

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

为此，您只需带上您的文本，插入全文，然后印第一个字母，插入结果文本，插入第二个字母，插入...

所以如果我们有文本“文本”，我们会插入以下集合：

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

在生成的后缀特里结构中，我们可以轻松搜索任何种类的前缀。 这也是节省空间的，因为我们不需要存储整个字符串，因为通用前缀只存储一次。

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

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

链接地址: http://www.djcxy.com/p/40091.html

上一篇: When do we actually use a Trie?

下一篇: How to call module written with argparse in iPython notebook