高效地模糊搜索大量数据？

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...]
}

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

目标

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

我试过的

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

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

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

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" 目前来自 fuzzywuzzy fuzz.QRatio，"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 之前检查两个字符串是否为空或相等，因此它可以 return 提前而不计算 levenshtein 距离。虽然这听起来是个好主意但实际上不是，因为检查两个字符串是否相同需要遍历整个字符串来检查它。在 levenshtein 计算之前删除公共前缀和后缀要好得多（加快速度，例如对于相等的字符串，它在时间上是线性的）。当字符串完全相同时，这会有点慢，但在处理模糊数据时，这种情况不太可能发生。第一个解决方案在我的机器上运行大约 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 版本的所有功能，但也足以实现它）

RapidFuzz 的纯 C++ 版本仍然需要一些工作，尤其是文档，但可以通过以下方式实现：

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);
    }
}

高效地模糊搜索大量数据？

Fuzzy searching a large set of data efficiently?

python

performance

fuzzy-search

目标

我试过的

问题