在大型字符串文件中查找部分字符串匹配的高效方法（python）
我下载了一个维基百科文章标题的文件，这个文件里包含了每个维基百科文章的名字。我需要找出所有可能匹配的文章标题。例如，我可能有一个词“hockey”，但我想要的维基百科文章是“Ice_hockey”。而且，这个搜索应该是不区分大小写的。
我在用Python，有没有比逐行搜索更有效的方法？理想情况下，我每分钟要进行大约500到1000次这样的搜索。如果逐行搜索是我唯一的选择，那我能在这个过程中做一些优化吗？
我觉得这个文件里有几百万行。
有什么想法吗？
谢谢。
3 个回答
1
我建议你把你的数据放进一个sqlite数据库里，然后在搜索的时候用SQL的'like'操作符。
4
如果你有一组固定的数据和一些变化的查询，那么通常的做法是把数据整理成更容易搜索的形式。简单来说，你可以把每个文章标题拆分成小写的单词，然后把这些单词放进一个Python的字典里。这样，当你收到一个查询时，只需要把查询的单词变成小写，然后在字典里查找。如果字典里的每个条目都对应一个标题列表，那么你就能轻松找到所有符合查询单词的标题。
这种方法适合简单的单词，但你还需要考虑是否要处理相似的单词，比如当查询是“smoke”时，是否也要找到“smoking”。
3
Greg的回答很好，如果你想匹配单个单词的话。不过，如果你想匹配字符串中的一部分，那就需要用到一些更复杂的东西，比如后缀树（可以查一下这个链接：http://en.wikipedia.org/wiki/Suffix_tree）。一旦建立了后缀树，它就能很高效地回答关于任意字符串部分的查询。所以在你的例子中，当有人搜索“hock”时，它就能匹配到“Ice_Hockey”。