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

Question

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

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

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

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

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

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

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

Answer 1

模糊模糊

既然您提到了使用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++中实现的^ {