arrays - 慢速 CPU 的快速索引？

Question

我有一个大型文档，我想为它建立索引以进行单词搜索。 (我听说这种类型的数组真的叫做索引)。目前大约需要 10 分钟。有快速的方法吗？目前我遍历每个段落，如果我找到一个我以前没有遇到过的词，我也会将它添加到我的词数组中，连同子数组中的段落编号，每当我再次遇到同一个词时，我都会添加段落编号到索引。 :

associativeArray={chocolate:[10,30,35,200,50001],parsnips:[5,500,100403]}

这需要很长时间，大约 5 分钟。我尝试将此数组转换为字符串，但它太大了，无法包含在程序文件中，即使在删除停用词后也是如此，并且无论如何都需要一段时间才能转换回数组。

有没有比线性暴力法更快的建立文本索引的方法？我不是在寻找可以为我创建索引的产品，我只是在寻找已知最快的算法。索引要准确，不能模糊，不需要局部搜索。

Answer 1

我认为最好的想法是构建一个 trie ，在您的文本时添加一个词，并为每片叶子提供一个位置列表，您可以找到该词。

这不仅会为您节省一些空间，因为存储具有相似前缀的单词需要的空间会更少，而且搜索速度也会更快。搜索时间为 O(M)，其中 M 是最大字符串长度，插入时间为 O(n)，其中 n 是您要插入的键的长度。

由于显而易见的替代方案是哈希表，here您可以找到两者之间的更多比较。