当语料库有100亿个独特的DNA序列时，如何使用BKtrees实现快速模糊搜索引擎？

Question

我试图使用python中的BK-tree数据结构来存储一个包含约100亿条目的语料库（1e10），以便实现一个快速模糊搜索引擎

一旦我将超过1000万（1e7）的值添加到一个BK树中，我就开始看到查询性能的显著下降

我在考虑将语料库存储到由一千棵BK树组成的森林中，并并行查询它们

这个主意听起来可行吗？我应该同时创建和查询1000棵BK树吗？我还可以做些什么来使用这个语料库的BK树

我使用pybktree.py，我的查询旨在查找编辑距离d内的所有条目

是否有某种架构或数据库允许我存储这些树

注意：我没有耗尽内存，而是树开始效率低下（可能每个节点都有太多子节点）

Answer 1

没什么想法

BK树
感谢本·霍伊特和他与issue的联系，我将从中吸取教训。话虽如此，上述问题的第一个观察结果是BK树不是完全对数的。根据你告诉我们的，你通常的d是~6，这是你绳子长度的3/10。不幸的是，这意味着，如果我们从问题中查看表格，您将得到介于O（N^0.8）到O（N）之间的复杂性。在乐观的情况下 指数为0.8（可能会稍微差一点），您的10B条目的改善系数约为100。因此，如果你有一个相当快的BK树实现，那么使用它们或将它们作为进一步优化的基础仍然是值得的

这样做的缺点是，即使并行使用1000棵树，也只能从并行化中得到改进，因为树的性能取决于d，而不是树中的节点数量。然而，即使你用一台大型机器同时运行所有1000棵树，我们的节点数/棵数也达到了约10M，而你报告的速度很慢。不过，从计算角度来看，这似乎是可行的

暴力手段
如果你不介意付一点钱的话，我会研究谷歌云大查询之类的东西，如果这不与某种数据保密性冲突的话。他们将为您强制执行解决方案-收取费用。当前的查询费率为每TB 5美元。您的数据集是~10B行*20chars。每个字符占用一个字节，如果您采取懒惰的方式，一个查询将占用200GB，因此每个查询大约需要1美元。
但是，由于费用是按列中数据的每个字节计算的，而不是按问题的复杂程度计算的，因此您可以通过将字符串存储为每字母2比特的方式对此进行改进，这将为您节省75%的费用。
进一步改进，您可以以这样一种方式编写查询，它将一次请求十几个字符串。为了查询的目的，您可能需要小心使用一批类似的字符串，以避免使用过多的一次性字符串阻塞结果

对BK树的暴力强制
由于如果您按照上述路线进行，您将不得不根据数量付费，因此所需计算量的~100倍下降将变成价格的~100倍下降，这可能非常有用，特别是如果您有大量查询要运行。
但是，您需要找到一种方法，将此树存储在多层数据库中，以便递归查询，因为Bigquery定价取决于查询表中的数据量
构建一个用于递归处理查询以最小化成本的智能批处理引擎可能是一个有趣的优化练习

语言选择
还有一件事。虽然我认为Python是一种很好的快速原型设计、分析和思考代码的语言，但总体而言，您已经过了那个阶段。您目前正在寻找一种方法，以尽可能快地执行特定、定义明确且经过深思熟虑的操作。正如this example所示，Python并不是一种很好的语言。虽然我使用了Python中我能想到的所有技巧，但Java和C解决方案的速度仍然快了好几倍。（更不用说打败我们所有人的rust了——但他在算法上也打败了我们，所以很难比较。）因此，如果你从python转向更快的语言，你可能会获得另一个、十个甚至更多的性能提升。这可能是另一个有趣的优化练习。
注意：我对这个估计相当保守，因为FuzzyWuzy已经提供在后台使用C库，所以我不太确定有多少工作仍然依赖于python。我在类似情况下的经验是，从纯python（或者更糟糕的是，纯R）到编译语言，性能增益可以是100倍

Answer 2

模糊模糊

既然您提到了使用FuzzyWuzzy作为距离度量，我将集中讨论实现FuzzyWuzzy使用的fuzz.ratio算法的有效方法。fuzzyfuzzy为fuzz.ratio提供了以下两种实现：

1. difflib，完全用Python实现
2. python Levenshtein使用加权Levenshtein距离和权重2进行替换（替换是删除+插入）。Python Levenshtein是用C实现的，比纯Python实现快得多

python Levenshtein中的实现

python-Levenshtein的实现使用以下实现：

1. 删除两个字符串的公共前缀和后缀，因为它们对最终结果没有任何影响。这可以在线性时间内完成，因此匹配类似字符串的速度非常快
2. 修剪字符串之间的Levenshtein距离是通过二次运行时和线性内存使用实现的

RapidFuzz

我是库RapidFuzz的作者，该库以更高效的方式实现FuzzyWuzzy使用的算法。RapidFuzz对fuzz.ratio使用以下接口：

def ratio(s1, s2, processor = None, score_cutoff = 0)

附加的score_cutoff参数可用于提供分数阈值，作为介于0和100之间的浮点值。对于比率<；而是返回分数0。在某些情况下，实现可以使用这一点来使用更优化的实现。在下文中，我将根据输入参数描述RapidFuzz使用的优化。在下文中，{}指的是在不低于分数阈值的情况下可能达到的最大距离

最大距离==0

可通过直接比较计算相似度， 因为字符串之间不允许有差异。时间复杂性 这个算法是O(N)

最大距离==1且len（s1）==len（s2）

也可以使用直接比较来计算相似性，因为替换会导致编辑距离高于最大距离。该算法的时间复杂度为O(N)

删除公共前缀

两个比较字符串的公共前缀/后缀不影响 Levenshtein距离，因此在计算相似度之前移除词缀。此步骤针对以下任一算法执行

最大距离<；=四,

采用mbleven算法。该算法 检查下所有可能的编辑操作 阈值max distance。原始算法的描述可以在here中找到。我修改了这个算法，以支持替换的2的重量。作为与正常Levenshtein距离的差异，该算法在这里甚至可以使用高达4的阈值，因为更高的替换权重减少了可能的编辑操作量。该算法的时间复杂度为O(N)

len（短字符串）<；=64拆下普通固定件后

使用的是BitPAl算法，该算法在 平行的该算法在here中进行了描述，并在支持下进行了扩展 对于此实现中的UTF32。该算法的时间复杂度为O(N)

长度为>；六十四

Levenshtein距离是使用 Wagner Fischer和Ukkonens优化。该算法的时间复杂度为O(N * M)。 这可以在将来用BitPal的分块实现来代替

对处理器的改进

fuzzyfuzzy提供了多个处理器，如process.extractOne，用于计算查询和多项选择之间的相似性。在C++中实现这一点也允许两个更重要的优化：

<> L> > P>当在C++中使用的记分器也可以直接调用记分器的C++实现，不必在Python和C++之间来回切换，WHich提供了巨大的加速

1. 我们可以根据使用的记分器对查询进行预处理。例如fuzz.ratio用作记分器时，只需将查询存储到BitPal使用的64位块中一次，这在计算Levenshtein距离时节省了大约50%的运行时间

到目前为止，只有extractOne和extract_iter在Python中实现，而您将使用的extract仍然在Python中实现并使用extract_iter。因此，它已经可以使用2。优化，但仍然需要在Python和C++之间切换很多，这不是最优的（这也可能在V1.0.0中添加）。p>

基准

在开发过程中，我为extractOne和单个记分员执行了基准测试，显示了RapidFuzzy和FuzzyFuzzy之间的性能差异。请记住，您的案例（所有字符串长度均为20）的性能可能不太好，因为数据集中使用的许多字符串都非常小

可复制科学数据的来源：

• ^{}（包含99171个单词的数据集）

运行图形化基准的硬件（规格）：

• CPU：i7-8550U的单核
• 内存：8GB
• 操作系统：软呢帽32

基准得分者

这个基准的代码可以在here中找到

基准提取一号

对于这个基准测试，process.extractOne的代码稍微更改，以删除score_cutoff参数。之所以这样做，是因为在extractOne中，每当找到更好的匹配时score_cutoff就会增加（一旦找到完美匹配，它就会退出）。在将来，对不具有这种行为的基准{^ }的意义更大（基准是使用^ {CD13}}执行的，因为^ {CD25}}还没有完全在C++中实现）。基准代码可以在here中找到

这表明，在可能的情况下，记分器不应该直接使用，而应该通过处理器使用，这样可以执行更多的优化

另类

作为一种选择，你可以使用C++实现。库RAPIDFULF可用于C++ here。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万字/秒和1230万字/秒。这是Python实现的1.5倍（因为Python和C++类型之间的转换）。但是C++版本的主要优点是，无论你想用什么方法，你都相对自由地组合，而在Python版本中，你被迫使用C++中实现的^ {