当语料库有 100 亿个独特的 DNA 序列时，如何使用 BK 树实现快速模糊搜索引擎？
0x9*_*x90 5 python performance text fuzzy-search bk-tree
我正在尝试使用python 中的BK 树数据结构来存储一个包含约 100 亿个条目 ( 1e10)的语料库，以实现快速模糊搜索引擎。
一旦我将超过 1000 万 ( 1e7) 个值添加到单个 BK 树中，我开始看到查询性能显着下降。
我想将语料库存储到一千个 BK 树的森林中并并行查询它们。
这个想法听起来可行吗？我应该同时创建和查询 1,000 个 BK 树吗？为了在这个语料库中使用 BK 树，我还能做什么。
我使用pybktree.py并且我的查询旨在查找编辑距离内的所有条目d。
是否有一些架构或数据库可以让我存储这些树？
注意：我没有耗尽内存，而是树开始效率低下（大概每个节点都有太多子节点）。
模糊模糊
由于您提到使用 FuzzyWuzzy 作为距离度量，我将集中讨论实现fuzz.ratioFuzzyWuzzy 使用的算法的有效方法。FuzzyWuzzy 提供了以下两种实现fuzz.ratio：
- difflib，完全用Python实现
- python-Levenshtein 使用权重为 2 的加权 Levenshtein 距离进行替换（替换是删除 + 插入）。Python-Levenshtein 用 C 实现，比纯 Python 实现快得多。
python-Levenshtein 中的实现
的实现python-Levenshtein使用以下实现：
- 删除两个字符串的公共前缀和后缀，因为它们对最终结果没有任何影响。这可以在线性时间内完成，因此匹配相似的字符串非常快。
- 修剪后的字符串之间的编辑距离是通过二次运行时间和线性内存使用来实现的。
快速模糊测试
我是RapidFuzz库的作者，该库以更高性能的方式实现了 FuzzyWuzzy 使用的算法。RapidFuzz 使用以下接口fuzz.ratio：
def ratio(s1, s2, processor = None, score_cutoff = 0)
附加score_cutoff参数可用于提供分数阈值（0 到 100 之间的浮点数）。对于ratio < Score_cutoff，则返回 0。在某些情况下，实现可以使用它来使用更优化的实现。下面我将根据输入参数描述 RapidFuzz 使用的优化。下面max distance指的是在比率低于分数阈值的情况下可能的最大距离。
最大距离 == 0
可以使用直接比较来计算相似度，因为字符串之间不允许存在差异。该算法的时间复杂度为O(N)。
最大距离 == 1 且 len(s1) == len(s2)
也可以使用直接比较来计算相似度，因为替换会导致编辑距离高于最大距离。该算法的时间复杂度为O(N)。
删除公共前缀
两个比较字符串的公共前缀/后缀不会影响编辑距离，因此在计算相似度之前删除词缀。对于以下任何算法都执行此步骤。
最大距离 <= 4
使用mbleven算法。该算法检查阈值下所有可能的编辑操作max distance。可以在此处找到原始算法的描述。我更改了此算法以支持替换的权重为 2。作为与正常 Levenshtein 距离的区别，该算法甚至可以使用高达 4 的阈值，因为较高的替换权重会减少可能的编辑操作量。该算法的时间复杂度为O(N)。
len(较短的字符串) <= 64 删除公共词缀后
使用BitPAl算法，并行计算Levenshtein距离。此处描述了该算法，并在此实现中通过支持 UTF32 进行了扩展。该算法的时间复杂度为O(N)。
长度 > 64 的字符串
Levenshtein 距离是使用 Wagner-Fischer 和 Ukkonens 优化来计算的。该算法的时间复杂度为O(N * M)。未来这可能会被 BitPal 的区块实现所取代。
处理器的改进
FuzzyWuzzy 提供了多个类似的处理器process.extractOne，用于计算查询和多个选择之间的相似度。在 C++ 中实现这一点还可以实现两个更重要的优化：
当使用 C++ 实现的记分器时，我们可以直接调用记分器的 C++ 实现，而不必在 Python 和 C++ 之间来回切换，这提供了巨大的加速
我们可以根据所使用的评分器来预处理查询。举个例子，当
fuzz.ratio用作记分器时，它只需将查询存储到 BitPal 使用的 64 位块中一次，这在计算 Levenshtein 距离时节省了大约 50% 的运行时间
到目前为止，仅extractOne和extract_iter是在 Python 中实现的，而extract您将使用的仍然是在 Python 中实现的，并使用extract_iter. 所以它已经可以使用2.优化，但仍然需要在Python和C++之间进行大量切换，这不是最佳的（这可能也会在v1.0.0中添加）。
基准测试
我extractOne在开发过程中对各个评分器进行了基准测试，显示了 RapidFuzz 和 FuzzyWuzzy 之间的性能差异。请记住，您的情况（所有字符串长度均为 20）的性能可能不太好，因为使用的数据集中的许多字符串都非常小。
可重复科学数据的来源：
words.txt（包含 99171 个单词的数据集）
运行图形基准测试的硬件（规格）：
- CPU：单核i7-8550U
- 内存：8GB
- 操作系统：Fedora 32
基准得分者
该基准测试的代码可以在这里找到
基准提取一
对于此基准测试，代码process.extractOne略有更改以删除score_cutoff参数。这样做是因为每当找到更好的匹配时 inextractOne就会score_cutoff增加（并且一旦找到完美匹配就会退出）。将来，对process.extract没有这种行为的基准测试会更有意义（基准测试是使用 执行的process.extractOne，因为process.extract尚未在 C++ 中完全实现）。基准代码可以在这里找到
这表明，在可能的情况下，不应直接使用评分器，而应通过处理器来使用，这样可以执行更多的优化。
选择
作为替代方案，您可以使用 C++ 实现。此处可用于 C++ 的 RapidFuzz 库。C++的实现也比较简单
// function to load words into vector
std::vector<std::string> choices = load("words.txt");
std::string query = choices[0];
std::vector<double> results;
results.reserve(choices.size());
rapidfuzz::fuzz::CachedRatio<decltype(query)> scorer(query);
for (const auto& choice : choices)
{
results.push_back(scorer.ratio(choice));
}
或并行使用 open mp
// function to load words into vector
std::vector<std::string> choices = load("words.txt");
std::string query = choices[0];
std::vector<double> results;
results.reserve(choices.size());
rapidfuzz::fuzz::CachedRatio<decltype(query)> scorer(query);
#pragma omp parallel for
for (const auto& choice : choices)
{
results.push_back(scorer.ratio(choice));
}
在我的机器上（参见上面的基准测试），并行版本的评估速度为 4300 万字/秒和 1.23 亿字/秒。这大约是 Python 实现速度的 1.5 倍（由于 Python 和 C++ 类型之间的转换）。然而，C++ 版本的主要优点是您可以相对自由地以任何方式组合算法，而在 Python 版本中，您被迫使用processC++ 中实现的函数来获得良好的性能。