0

我有一个大文档，我想建立一个用于单词搜索的索引。（我听说这种类型的数组真的被称为索引）。目前大约需要 10 分钟。有没有快速的方法呢？目前我遍历每个段落，如果我找到一个我以前没有遇到过的单词，我也将它添加到我的单词数组中，以及辅助数组中的段落编号，每当我再次遇到同一个单词时，我添加段落编号到索引。：

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

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

除了线性蛮力之外，还有更快的方法来构建文本索引吗？我不是在寻找可以为我做索引的产品，只是最快的已知算法。索引应该准确，不模糊，不需要部分搜索。

4

4 回答 4

2

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

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

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

于 2013-09-03T08:42:06.407 回答
1

我会使用HashMap<String, List<Occurrency>>这种方式，您可以检查一个单词是否已经在大约O(1)的 yoz 索引中。

最后，当您收集了所有单词并希望经常搜索它们时，您可能会尝试找到一个没有或几乎没有冲突的哈希函数。通过这种方式，您可以保证O(1)的搜索时间（如果仍有一些冲突，则接近 O(1)）。

于 2013-09-03T08:44:20.720 回答
1

好吧，除了同意 MrSmith42 的使用内置的建议之外HashMap，我还想知道您花了多少时间跟踪段落编号？

改为跟踪行号会更快吗？（特别是如果您正在逐行阅读输入）。

于 2013-09-04T04:04:27.143 回答
0

您的问题中有一些不清楚的地方，例如“我尝试将此数组转换为字符串，但它太大了，即使在删除停用词之后也无法包含在程序文件中，并且无论如何都需要一段时间才能转换回数组。”？！什么数组，是您输入的段落数组形式，还是您的意思是每个单词的索引条目，或者什么。

也不清楚为什么你的程序这么慢，可能那里效率低下 - 我怀疑你检查“如果我找到一个我以前没有遇到过的词” - 我假设你在字典中查找这个词然后迭代出现的数组以查看段落# 是否存在？那是缓慢的线性搜索，你会更好地使用set那里（想想你只关心键的哈希/字典），有点

concord = {
    'chocolate': {10:1, 30:1, 35:1, 200:1, 50001:1}, 
    'parsnips': {5:1, 500:1, 100403:1}  
}

然后您的检查就变成if paraNum in concord[word]: ...了循环或二进制搜索。

PS。实际上假设您在数组中保留出现的列表并从第一段到最后一段扫描文本，这意味着数组将形成排序，所以您只需要检查最后一个元素if word in concord and paraNum == concord[word][-1]:。（示例在伪代码/python 中，但您可以翻译成您的语言）

于 2013-12-30T03:40:14.393 回答