logo标签列表

在大型字符串文件中查找部分字符串匹配的最有效方法（Python）

pythonstringsearchlarge-files
6
我下载了维基百科文章标题文件，其中包含每篇维基百科文章的名称。我需要搜索所有可能匹配的文章标题。例如，我可能有单词“hockey”，但我想要的冰球维基百科文章是“Ice_hockey”。这应该是一个不区分大小写的搜索。
我正在使用Python，除了逐行搜索，是否有更有效的方法？我希望能够每分钟进行500到1000次搜索。如果逐行搜索是唯一的选择，那么在其中有哪些优化措施？
我认为文件中有几百万行。
有什么好主意吗？
谢谢。
1
请展示期望的输入。文件格式是什么？不要让想要帮助你的人自己下载文件。 - aaronasterling
它只是一个简单的文本文件，每个标题都在自己的一行上。 - apexdodge
3个回答
4
如果你有一个固定的数据集和可变的查询，那么通常的技术是重新组织数据集以便更容易地进行搜索。在抽象的层次上，你可以将每篇文章标题拆分成单个小写单词，并将它们添加到Python字典数据结构中。然后，每当你收到一个查询时，将查询单词转换为小写并在字典中查找它。如果每个字典条目的值是标题列表，那么你可以轻松地找到所有与给定查询词匹配的标题。
这适用于简单的单词，但是你需要考虑是否要匹配类似的单词，例如在查询为"smoke"时找到"smoking"。
3

如果您想匹配单个词，请参考Greg的答案。如果您想匹配子字符串，则需要使用更复杂的方法，例如后缀树（http://en.wikipedia.org/wiki/Suffix_tree）。一旦构建完成，后缀树可以有效地回答任意子字符串的查询，因此在您的示例中，当有人搜索“hock”时，它可以匹配“Ice_Hockey”。

1

我建议您将数据放入SQLite数据库，并使用SQL的“like”操作符进行搜索。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接