Python - 快速文件搜索

Question

我有一个拥有大量行（0.5-1.5百万）的文件，每一行都是一个文件名（长度约为50-100个字符）。我需要一个能快速搜索给定查询条件的程序。现在我的代码看起来像这样：

def similarity(haystack, needle):
    words = re.findall(r'\w+', haystack.lower()) # replacing by split with separators reduces time by about 4 seconds

    for word in words:
        if word == needle:
            return 10

    for word in words:
        if word.startswith(needle):
            return 10 ** (len(needle) / len(word))

    if needle in haystack:
        return 1

    return 0

def search(text):
    text = text.lower()
    lines = [(similarity(x, text), x) for x in lines]
    return [x[1] for x in sorted(lines, reverse = True)[:15]]

在我的电脑上，示例文件在大约15秒内运行完毕（几乎所有时间都花费在 similarity() 函数中），但我希望它能够在几秒钟内几乎立刻完成。如何实现这一点？

我认为索引可能有所帮助，但对其可能的结构一无所知。而且，如果可能的话，我希望搜索变得“更模糊”——例如，使用N-gram或类似的东西。但现在主要关注的是速度。

更新：

同样的lines会被多次搜索。 needle始终只是一个单词。

“更模糊”意味着即使needle略微输入错误，也应该能够找到相应的行。

- aplavin

---

建议不要重复造轮子，使用专门的全文搜索引擎，如Sphinx。 - georg

Answer 1

1. 这行代码没有任何作用：

   10 ** (len(t) / len(word))

2. 你需要更好的变量名，现在不清楚"s"和"t"是什么。单个字母的变量名只适用于数学和循环变量。s是你正在搜索的内容吗？还是t是你正在搜索的内容？按照目前的用法，这个函数对我来说没有太多意义。

3. 由于你只匹配任何搜索的第一个匹配项，所以在某些情况下分割是无意义的，因此你可能可以将分割移到最后，但这取决于你实际要搜索的内容，而这一点又不太清楚（参见第2条）。

更新：为了真正发挥最佳性能，你需要进行分析、测试和分析、测试。但作为第一步，我建议使用以下代码：

def similarity(haystack, needle):

    if needle not in haystack:
        return 0

    words = haystack.lower().split()

    if needle in words:
        return 10

    for word in words:
        if word.startswith(needle):
            return 10 ** (len(needle) / len(word))

    return 1

- Lennart Regebro

---

1. 当然，在此之前有一个return。
2. 好的，将名称更改为更有意义的名称。
3. 一行不太可能包含多个needle。

- aplavin

这是一个非常明显的优化，但确实很有帮助 =）谢谢，现在执行时间约为2-3秒。顺便问一下，有没有简单的方法可以使搜索“更模糊”？ - aplavin

@chersanya：简单？不太可能。更复杂的模糊匹配需要查找搜索字符串的各个部分，最好使用词干字典等来处理，进而进入全文检索引擎模式。事实上，有一种简单的方法：使用全文检索引擎。;-) 然而，编写一个全文检索引擎并非易事。 - Lennart Regebro

你会推荐使用哪个引擎吗？据我所知，大多数引擎都是用于搜索包含某种模式的文件，而不是用于在单个文件中搜索一行。 - aplavin

Answer 2

由于您正在使用相同的文件搜索字符串。如果您使用持久字典，可以加快搜索速度。

考虑到您的逻辑，您可以使用这个。

import shelve
import os

PERSISTENT_DICT_FILENAME = "my_persistent_dict"

def create_a_persitant_dict(haystack_filename):
    pd = shelve.open(PERSISTENT_DICT_FILENAME)
    f = open(haystack_filename)
    for filename in f:
        filename_len = len(filename) 
        filename = filename.lower()
        for i in range(1,filename_len):
            partial_filename = filename[:i]
                calculation = 10 ** ((len(partial_filename)*1.0)/filename_len)
                if pd.has_key(partial_filename):
                        if calculation > pd[partial_filename]:
                            pd[partial_filename] = calculation
                else:
                    pd[partial_filename] = calculation

    pd.close()

def search_string(needle):
    needle = needle.lower()
    pd = shelve.open(PERSISTENT_DICT_FILENAME)
    if pd.has_key(needle):
        return_val = pd[needle]
    else:
        return_val = 0
    pd.close()
    return return_val

if __name__ == "__main__":
    #create_a_persitant_dict("a_large_file.txt")
    needle = raw_input("Enter the string to search")
    print search_string(needle)

解释：

create_a_persitant_dict(haystack_filename)

将创建一个持久化的字典，读取一个大文件。键是在文件中找到的字符串（例如：如果文件中的一行是“World.txt”，则键将是“w”、“wo”、“wor”、“worl”等），而值是每个键的计算（10 **等等）。

这只是一次昂贵的操作。但是想法是加速搜索。

search_string(needle)

该函数将在持久化字典中搜索字符串，并根据您的逻辑给出计算结果。它比每次迭代都要快。

- pytroy

---

我尝试构建倒排索引，但仅针对分离的单词，而非每个子字符串。它大约占用了80 MB（未压缩）。我担心你建议的索引大小... - aplavin