2

我的任务是在非常短（比如 200 个字符长）的文档列表中搜索字符串或模式。但是，假设有 100 万份这样的时间文件。执行此搜索的最有效方法是什么？我正在考虑标记每个文档并将单词放入哈希表中，单词作为键，文档编号作为值，在那里创建一个单词包。然后执行单词搜索并检索包含该单词的文档列表。据我所知，这个操作需要 O(n) 次操作。还有其他方法吗？可能不使用哈希表？

另外，是否有可以执行高效搜索的 python 库或第三方包？

4

4 回答 4

4

既然你正在寻找一个库，你有没有看过 PyLucene？

http://lucene.apache.org/pylucene/features.html

虽然 Lucene 通常实现排名检索（基于相对分数的匹配） - 与完全匹配相反 - 它可用于精确短语搜索。这是一个关于如何使用 Lucene 搜索确切短语的链接。它是用 Java 编写的，但给出了这样的想法：

使用 Lucene 的精确短语搜索？

您的问题专门询问了效率。效率在什么方面？我假设您的意思是用户的最快查找时间。如果您确实纯粹根据用户的查找时间来谈论速度，那么没有比实际索引文档中的所有单词更快的方法了，前提是您愿意忍受初始时间来索引语料库中的所有文档. 这通常是合乎逻辑的选择，因为索引是一次性事件，并且用户搜索经常发生。但是，显然，这会带来相当大的内存使用量。因此，如果您谈论的是内存使用方面的效率，那么您可能希望遍历所有文档并对每个文档执行正则表达式搜索。如果您想避免索引的初始查找时间，您也可以使用此方法，但是，考虑到语料库的大小，这不太可能是逻辑限制因素，并且考虑到关注点通常会满足将多个查询。

我要指出的唯一另一件事是，由于您提到您正在搜索模式而不仅仅是单词，如果您尝试支持查询模式，那么仅索引单词将无济于事（除非该模式是其中的单词之一文件！）

如果您不打算使用 Lucene，而是想自己实现它，请查看使用倒排索引的索引。如果您要进行短语查询，这里是关于如何创建倒排索引的一个很好的解释：

http://www.searchenginepeople.com/blog/how-search-really-works-the-index-2.html

于 2012-10-28T05:57:01.227 回答
3

大多数搜索引擎都是按照倒排索引的原理工作的。基本上，对于每个标记（单词、三元组等），您都会存储包含此标记的文档的排序列表。匹配查询时，您合并连接所有必需标记的列表以生成候选文档列表。如果索引匹配不能保证查询匹配，则必须在匹配的文档上重新测试查询表达式。

存储倒排索引的解决方案有很多，其中一些（Lucene、Sphinx、PostgreSQL FTS）已经支持在倒排索引上计算表达式。

搜索引擎的魔力主要发生在对文档进行预处理和标记化以及根据用户请求生成搜索查询方面。预处理技巧包括通过词干词干和每个词存储多个不同表示的词规范化。对于查询构造，您可能需要执行同义词替换之类的操作。正则表达式有点棘手，但是关于在 PostgreSQL 中实现对正则表达式搜索的索引支持有一个很好的讨论。

于 2012-10-28T09:53:07.713 回答
1

虽然您使用哈希表制作词袋的想法听起来很有趣，但我认为当您打开每个文件，将其读入内存，对其进行标记，制作哈希表，将每个标记放入哈希表，对搜索词进行哈希处理，然后索引到您的哈希表来查找包含该单词的每个文档的文档 ID，与仅使用正则表达式并在每个文件中进行搜索相比，您花费的时间要多得多：

import re
import os
import sys

searchterm = sys.argv[1]
searchexp = re.compile("(%s)" % searchterm, re.M)

for filename in os.listdir(sys.argv[2]):
    f = open(os.path.join(sys.argv[2], filename), 'r')
    contents = f.read()
    f.close()
    if searchexp.search(contents):
        print(filename)

是不是太慢了？

于 2012-10-28T04:51:05.337 回答
1

我认为没有比Russ Cox在这里描述的解决方案更好的解决方案了，他为不幸退役的谷歌代码搜索引擎开发了这个解决方案。

于 2012-10-28T04:54:40.673 回答