python - 有效地模糊搜索大量数据？

Question

我有一个格式如下的数据库:

"filename": {
        "url": "base64 of Zlib compressed URL to decrease size of file",
        "date": "Date added to database",
        "size": "Size of file in URL(not always present)"
}

格式是树状的。例如:

"dirname": {
        "url": "base64 of Zlib compressed URL to decrease size of file",
        "date": "Date added to database",
        [...files and directories in this directory...]
}

可以包含更多的文件和目录。

目标

我正在尝试 模糊搜索只是名称和 返回 URL/日期(/size) 数据库中的条目。它目前有 650 万个字符串，平均长度约为 36 个字符。数据库中存在重复的名称。


我试过的

我认为首先将数据加载到 RAM 会更快。我的笔记本电脑只有 8GB，所以我想降低使用率，我会以列表格式保存数据，其中 URL 使用 Zlib 压缩进一步减少 RAM 使用量。格式是这样的:

[["file or directory name", "zlib compressed url", "date", "size if exists"], ...]

目前四舍五入约为 3GB。
然后我使用迭代器将列表拼接成 20 block ，并将迭代器传递给一个函数并在单独的进程中运行它。

results = manager.list() # python multiprocessing shared list
#in a loop that splices into n pieces(20 currently):
    p = multiprocessing.Process(target=self.slice_search, args=(results, name, iter(self.minimal_data[start:i]), function_to_use, min_score,))
    processes.append(p)
    p.start()

“function_to_use”目前是fuzz.QRatio，来自fuzzywuzzy，“slice_search”是一个函数，如果字符串上的“function_to_use”结果超过某个阈值，则将数据附加到共享列表中。
结果以类似的格式存储:

[["score", "file or directory name", "zlib compressed url", "date", "size if exists"], ...]

并在搜索结束后进行排序并以人类可读的格式保存到文件中(URL 也被解压缩)。

问题

有了所有这些，搜索仍然需要大约 20-30 秒。我真的相信有更好的方法，但我没有实现它所需的知识。我的最终目标是让它工作至少快于 10 秒。我将不胜感激您可以指出我的任何帮助或方向。

Answer 1

对于这个答案，我将处理以下数据:

import string
import random
random.seed(18)
str_options = string.ascii_uppercase + string.ascii_lowercase + string.digits + ' '
query = \'\'.join(random.choice(str_options) for _ in range(30))
choices = [\'\'.join(random.choice(str_options) for _ in range(30)) for s in range(6500000)]

我暂时不会使用任何多处理，但这也可以以并行方式完成。

这是关于您当前的解决方案的样子:

from fuzzywuzzy import fuzz
results = []
for choice in choices:
    if fuzz.QRatio(query, choice) >= 80:
        results.append(choice)

正如您提到的，fuzzywuzzy 已经使用 python-Levenshtein 进行了非常优化的 levenshtein 计算。但是在计算fuzzywuzzy 之前检查两个字符串是否为空或相等，以便它可以提前返回而无需计算levenshtein 距离。虽然这听起来是个好主意，但实际上并非如此，因为检查两个字符串是否相同需要遍历整个字符串来检查它。在 levenshtein 计算之前删除公共(public)前缀和后缀要好得多(加速它，例如对于相等的字符串，它是时间线性的)。当字符串完全相同时，这会慢一些，但在处理模糊数据时，这种情况不太可能发生。
第一个解决方案大约在 55 seconds 中运行。在我的机器上

这用 RapidFuzz 替换了fuzzywuzzy (我是作者)它是 FuzzyWuzzy 的 MIT 许可重新实现，主要在 C++ 中实现并且性能更好，因为它修复了 FuzzyWuzzy

中的很多性能问题

from rapidfuzz import fuzz
results = []
for choice in choices:
    if fuzz.QRatio(query, choice) >= 80:
        results.append(choice)

这只需要大约 18 seconds在我的机器上，所以它已经是大约 3 倍的改进。另一个问题是使用 fuzz.QRatio 预处理两个字符串以将它们小写并删除一些不需要的字符。虽然这通常是有道理的，但这意味着这里的查询得到了 650 万次而不是一次的预处理。

这只对查询进行一次预处理

from rapidfuzz import fuzz, utils
results = []
processed_query = utils.default_process(query)
for choice in choices:
    processed_choice = utils.default_process(choice)
    if fuzz.ratio(processed_query, processed_choice, score_cutoff=80):
        results.append(choice)

需要 14 seconds在我的机器上。这表明您可能还希望以预处理的方式存储文件名，因此您在搜索时也不必对它们进行预处理(这将使其降至 11 seconds 左右)。此时主要的时间要求是计算 levenshtein 距离，这是一个 O(m*n) 操作。因此，最好减少必须执行此操作的结果数量。 RapidFuzz 默认情况下已经使用的一种快速方法是比较两个字符串的长度，因为当它们的长度差异很大并且可以在恒定时间内计算时，它们无法达到所需的比率，因为无论如何长度都是已知的.但是，在我的测试用例中，这永远不会适用，因为所有字符串的长度都是 30。当需要更快的解决方案时，您仍然可以在多个内核上进行计算。您可以使用 C++ 版本 RapidFuzz-cpp以及(它还没有 python 版本的所有功能，但也足以实现这一点)
纯 C++ 版本的 RapidFuzz 仍然需要一些工作，尤其是文档，但可以通过以下方式实现:

using rapidfuzz::string_utils::default_process;
using rapidfuzz::fuzz::CachedRatio;

std::string query("example");
std::vector<std::string> choices{"example", "example2", "example3"};

std::string processed_query = default_process(query);
std::vector<std::string> results;
CachedRatio<std::string> scorer(processed_query);
for (const auto& choice : choices) {
    std::string processed_choice = default_process(choice);

    if (scorer.ratio(processed_choice, 80)) {
        results.push_back(choice);
    }
}