当语料库有 100 亿个唯一的 DNA 序列时，如何使用 BK 树实现快速模糊搜索引擎？
How to implement a fast fuzzy-search engine using BK-trees when the corpus has 10 billion unique DNA sequences?
我正在尝试使用 python 中的 BK-tree 数据结构来存储具有约 100 亿个条目 (1e10) 的语料库，以实现快速模糊搜索引擎。
一旦我将超过 1000 万 (1e7) 个值添加到单个 BK 树中，我开始发现查询性能显着下降。
我正在考虑将语料库存储到一千个 BK 树的森林中并并行查询它们。
这个想法听起来可行吗？我应该同时创建和查询 1,000 个 BK 树吗？为了在这个语料库中使用 BK-tree，我还能做什么。
我使用 pybktree.py，我的查询旨在查找编辑距离 d.
内的所有条目
是否有某种体系结构或数据库可以让我存储这些树？
注意：我没有运行内存不足，而是树开始效率低下（大概每个节点都有太多子节点）。
没什么想法
BK-树
感谢 Ben Hoyt 和他的 link 以及我将借鉴的 issue。话虽如此，上述问题的第一个观察结果是 BK 树并不完全是对数的。根据您告诉我们的情况，您通常的 d 是 ~6，这是字符串长度的 3/10。不幸的是，这意味着如果我们查看问题中的 tables，您将得到 O(N^0.8) 到 O(N) 之间某处的复杂性。在乐观的情况下
指数为 0.8（可能会稍微差一些），您的 10B 条目的改进系数约为 100。因此，如果您有相当快的 BK 树实现，使用它们或将它们用作进一步优化的基础仍然是值得的。
这样做的缺点是，即使您并行使用 1000 棵树，您也只会从并行化中获得改进，因为树的性能取决于 d 而不是而不是树内节点的数量。但是，即使您 运行 使用大型机器一次处理所有 1000 棵树，我们的速度也会达到 ~10M nodes/tree，您报告说速度很慢。尽管如此，在计算方面，这似乎是可行的。
暴力方法
如果您不介意支付一点费用，我会考虑 Google 云大查询之类的东西，前提是这不会与某种数据机密性发生冲突。他们会为您暴力破解解决方案——收费。当前费率是 5 美元/TB 的查询。您的数据集是 ~10B 行 * 20 个字符。每个字符占用一个字节，一个查询将占用 200GB，因此如果您采取懒惰的方式，则每个查询大约需要 1 美元。
但是，由于按列中数据的每个字节收费，而不是按问题的复杂性收费，因此您可以通过将字符串存储为位来改进这一点——每个字母 2 位，这将为您节省 75% 的费用。
进一步改进，您可以将查询编写为一次请求十几个字符串。您可能需要小心使用一批类似的字符串来进行查询，以避免一次性结果过多而阻塞结果。
BK 树的暴力破解
因为如果你走上面的路线，你将不得不根据数量付费，所需计算量减少约 100 倍变成价格减少约 100 倍，这可能很有用，特别是如果你有很多查询至 运行.
但是，您需要想出一种方法将此树存储在多层数据库中以递归查询，因为 Bigquery 定价取决于查询中的数据量 table。
为查询的递归处理构建智能批处理引擎以最小化成本可能是有趣的优化练习。
语言选择
还有一件事。虽然我认为 Python 是一种用于快速原型设计、分析和思考一般代码的好语言，但您已经过了那个阶段。您目前正在寻找一种方法来尽快执行 特定的、定义明确且经过深思熟虑的 操作。正如 this example 所示，Python 并不是一种很好的语言。虽然我使用了 Python 中我能想到的所有技巧，但 Java 和 C 解决方案仍然快了几倍。 （更不用说打败我们所有人的 rust 了——但他也在算法上打败了我们，所以很难比较。）因此，如果你从 python 转向一种更快的语言，你可能会获得另一个因子或十个因子或也许更多的是性能提升。这可能是另一个有趣的优化练习。
注意：我对估计相当保守，因为 fuzzywuzzy 已经提供在后台使用 C 库，所以我不太确定有多少工作仍然取决于python。我在类似情况下的经验是，从纯 python（或更糟，纯 R）到编译语言，性能增益可以提高 100 倍。
FuzzyWuzzy
既然你提到了你使用 FuzzyWuzzy 作为距离度量，我将专注于实现 FuzzyWuzzy 使用的 fuzz.ratio 算法的有效方法。 FuzzyWuzzy为fuzz.ratio提供了以下两种实现：
- difflib，完全实现在Python
- python-Levenshtein，它使用权重为 2 的加权 Levenshtein 距离进行替换（替换为删除 + 插入）。 Python-Levenshtein 是用 C 实现的，比纯 Python 实现快很多。
在 python-Levenshtein
中实施
python-Levenshtein的实现使用了以下实现：
- 去掉两个字符串的公共前缀和后缀，因为它们对最终结果没有任何影响。这可以在线性时间内完成，因此匹配相似的字符串非常快。
- 修剪后的字符串之间的 Levenshtein 距离是通过二次运行时间和线性内存使用实现的。
快速模糊
我是库 RapidFuzz 的作者，它以更高效的方式实现了 FuzzyWuzzy 使用的算法。 RapidFuzz 为 fuzz.ratio 使用以下接口：
def ratio(s1, s2, processor = None, score_cutoff = 0)
附加的 score_cutoff 参数可用于提供分数阈值，作为 0 到 100 之间的浮点数。对于比率 < score_cutoff，则返回 0。在某些情况下，实现可以使用它来使用更多更优化的实现。在下文中，我将根据输入参数描述 RapidFuzz 使用的优化。下面的max distance指的是在没有低于分数阈值的情况下可能的最大距离。
最大距离== 0
可以使用直接比较来计算相似度，
因为不允许字符串之间存在差异。的时间复杂度
这个算法是 O(N).
最大距离 == 1 和 len(s1) == len(s2)
也可以使用直接比较来计算相似度，因为替换会导致编辑距离高于最大距离。该算法的时间复杂度为O(N).
删除公共前缀
两个比较字符串的共同prefix/suffix不影响
Levenshtein 距离，因此在计算相似度之前删除词缀。此步骤针对以下任何算法执行。
最大距离 <= 4
使用了mbleven算法。这个算法
检查所有可能的编辑操作
阈值 max distance。可以找到原始算法的描述 here。我更改了此算法以支持 2 的权重进行替换。作为与正常 Levenshtein 距离的差异，此算法甚至可以在此处使用高达 4 的阈值，因为较高的替换权重会减少可能的编辑操作量。该算法的时间复杂度为O(N).
len(较短的字符串) <= 64 删除公共词缀后
使用BitPAl算法，计算Levenshtein距离为
平行线。该算法被描述 here 并在支持下得到扩展
对于此实现中的 UTF32。该算法的时间复杂度为O(N).
长度 > 64 的字符串
Levenshtein 距离是使用
具有 Ukkonens 优化的 Wagner-Fischer。该算法的时间复杂度为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
- OS：软呢帽 32
基准得分手
可以找到此基准测试的代码here
基准 extractOne
对于此基准测试，process.extractOne 的代码略有更改以删除 score_cutoff 参数。这样做是因为在 extractOne 中，每当找到更好的匹配时 score_cutoff 就会增加（一旦找到完美匹配就会退出）。将来，对没有此行为的 process.extract 进行基准测试会更有意义（基准测试使用 process.extractOne 执行，因为 process.extract 尚未在 C++ 中完全实现）。可以找到基准代码 here
这表明在可能的情况下不应直接使用记分器，而应通过处理器使用，这样可以执行更多优化。
备选
作为替代方案，您可以使用 C++ 实现。 RapidFuzz 库可用于 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 万 words/sec 和 1.23 亿 words/sec。这大约是 Python 实现的 1.5 倍（由于 Python 和 C++ 类型之间的转换）。然而，C++ 版本的主要优点是您可以相对自由地以任何方式组合算法，而在 Python 版本中，您被迫使用 C++ 中实现的 process 函数来实现良好的效果性能。
来晚了，但这里有一个可能的解决方案
如果我是你的情况我会实施：
将数据集保存为文本文件，并将该文件放在一个非常
快速磁盘区域（最好在 tmpfs 上）。
准备一台具有许多 CPU 个物理内核的强大计算机（例如
作为具有 64 个内核的 Threadripper 3990X）。
使用 this implementation and GNU parallel 来理解数据集。
以下是此解决方案背后的一些技术信息：
Myers 算法的优化版本（上面链接）可以
在单个 CPU 核心上每秒处理大约 1400 万个条目。
如果能充分利用全部64个物理核心，就可以
存档每秒 8.96 亿的吞吐量（= 14m * 64 核）。
这个速度，你可以单次查询100亿
使用一台机器在 12 秒内处理数据集。
我在 this article 上发布了更详细的分析。
如文章所示，我可以对 1 亿条记录的数据集执行查询
用我便宜的台式机在 1.04 秒内。
通过使用性能更高的 CPU（或将任务拆分为
多台计算机），我相信你可以存档想要的结果。
希望这有帮助。
我正在尝试使用 python 中的 BK-tree 数据结构来存储具有约 100 亿个条目 (1e10) 的语料库，以实现快速模糊搜索引擎。
一旦我将超过 1000 万 (1e7) 个值添加到单个 BK 树中，我开始发现查询性能显着下降。
我正在考虑将语料库存储到一千个 BK 树的森林中并并行查询它们。
这个想法听起来可行吗？我应该同时创建和查询 1,000 个 BK 树吗？为了在这个语料库中使用 BK-tree，我还能做什么。
我使用 pybktree.py，我的查询旨在查找编辑距离 d.
是否有某种体系结构或数据库可以让我存储这些树？
注意：我没有运行内存不足，而是树开始效率低下（大概每个节点都有太多子节点）。
没什么想法
BK-树
感谢 Ben Hoyt 和他的 link 以及我将借鉴的 issue。话虽如此，上述问题的第一个观察结果是 BK 树并不完全是对数的。根据您告诉我们的情况，您通常的 d 是 ~6，这是字符串长度的 3/10。不幸的是，这意味着如果我们查看问题中的 tables，您将得到 O(N^0.8) 到 O(N) 之间某处的复杂性。在乐观的情况下
指数为 0.8（可能会稍微差一些），您的 10B 条目的改进系数约为 100。因此，如果您有相当快的 BK 树实现，使用它们或将它们用作进一步优化的基础仍然是值得的。
这样做的缺点是，即使您并行使用 1000 棵树，您也只会从并行化中获得改进，因为树的性能取决于 d 而不是而不是树内节点的数量。但是，即使您 运行 使用大型机器一次处理所有 1000 棵树，我们的速度也会达到 ~10M nodes/tree，您报告说速度很慢。尽管如此，在计算方面，这似乎是可行的。
暴力方法
如果您不介意支付一点费用，我会考虑 Google 云大查询之类的东西，前提是这不会与某种数据机密性发生冲突。他们会为您暴力破解解决方案——收费。当前费率是 5 美元/TB 的查询。您的数据集是 ~10B 行 * 20 个字符。每个字符占用一个字节，一个查询将占用 200GB，因此如果您采取懒惰的方式，则每个查询大约需要 1 美元。
但是，由于按列中数据的每个字节收费，而不是按问题的复杂性收费，因此您可以通过将字符串存储为位来改进这一点——每个字母 2 位，这将为您节省 75% 的费用。
进一步改进，您可以将查询编写为一次请求十几个字符串。您可能需要小心使用一批类似的字符串来进行查询，以避免一次性结果过多而阻塞结果。
BK 树的暴力破解
因为如果你走上面的路线，你将不得不根据数量付费，所需计算量减少约 100 倍变成价格减少约 100 倍，这可能很有用，特别是如果你有很多查询至 运行.
但是，您需要想出一种方法将此树存储在多层数据库中以递归查询，因为 Bigquery 定价取决于查询中的数据量 table。
为查询的递归处理构建智能批处理引擎以最小化成本可能是有趣的优化练习。
语言选择
还有一件事。虽然我认为 Python 是一种用于快速原型设计、分析和思考一般代码的好语言，但您已经过了那个阶段。您目前正在寻找一种方法来尽快执行 特定的、定义明确且经过深思熟虑的 操作。正如 this example 所示，Python 并不是一种很好的语言。虽然我使用了 Python 中我能想到的所有技巧，但 Java 和 C 解决方案仍然快了几倍。 （更不用说打败我们所有人的 rust 了——但他也在算法上打败了我们，所以很难比较。）因此，如果你从 python 转向一种更快的语言，你可能会获得另一个因子或十个因子或也许更多的是性能提升。这可能是另一个有趣的优化练习。
注意：我对估计相当保守，因为 fuzzywuzzy 已经提供在后台使用 C 库，所以我不太确定有多少工作仍然取决于python。我在类似情况下的经验是，从纯 python（或更糟，纯 R）到编译语言，性能增益可以提高 100 倍。
FuzzyWuzzy
既然你提到了你使用 FuzzyWuzzy 作为距离度量，我将专注于实现 FuzzyWuzzy 使用的 fuzz.ratio 算法的有效方法。 FuzzyWuzzy为fuzz.ratio提供了以下两种实现：
- difflib，完全实现在Python
- python-Levenshtein，它使用权重为 2 的加权 Levenshtein 距离进行替换（替换为删除 + 插入）。 Python-Levenshtein 是用 C 实现的，比纯 Python 实现快很多。
在 python-Levenshtein
中实施python-Levenshtein的实现使用了以下实现：
- 去掉两个字符串的公共前缀和后缀，因为它们对最终结果没有任何影响。这可以在线性时间内完成，因此匹配相似的字符串非常快。
- 修剪后的字符串之间的 Levenshtein 距离是通过二次运行时间和线性内存使用实现的。
快速模糊
我是库 RapidFuzz 的作者，它以更高效的方式实现了 FuzzyWuzzy 使用的算法。 RapidFuzz 为 fuzz.ratio 使用以下接口：
def ratio(s1, s2, processor = None, score_cutoff = 0)
附加的 score_cutoff 参数可用于提供分数阈值，作为 0 到 100 之间的浮点数。对于比率 < score_cutoff，则返回 0。在某些情况下，实现可以使用它来使用更多更优化的实现。在下文中，我将根据输入参数描述 RapidFuzz 使用的优化。下面的max distance指的是在没有低于分数阈值的情况下可能的最大距离。
最大距离== 0
可以使用直接比较来计算相似度，
因为不允许字符串之间存在差异。的时间复杂度
这个算法是 O(N).
最大距离 == 1 和 len(s1) == len(s2)
也可以使用直接比较来计算相似度，因为替换会导致编辑距离高于最大距离。该算法的时间复杂度为O(N).
删除公共前缀
两个比较字符串的共同prefix/suffix不影响 Levenshtein 距离，因此在计算相似度之前删除词缀。此步骤针对以下任何算法执行。
最大距离 <= 4
使用了mbleven算法。这个算法
检查所有可能的编辑操作
阈值 max distance。可以找到原始算法的描述 here。我更改了此算法以支持 2 的权重进行替换。作为与正常 Levenshtein 距离的差异，此算法甚至可以在此处使用高达 4 的阈值，因为较高的替换权重会减少可能的编辑操作量。该算法的时间复杂度为O(N).
len(较短的字符串) <= 64 删除公共词缀后
使用BitPAl算法，计算Levenshtein距离为
平行线。该算法被描述 here 并在支持下得到扩展
对于此实现中的 UTF32。该算法的时间复杂度为O(N).
长度 > 64 的字符串
Levenshtein 距离是使用
具有 Ukkonens 优化的 Wagner-Fischer。该算法的时间复杂度为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
- OS：软呢帽 32
基准得分手
可以找到此基准测试的代码here
基准 extractOne
对于此基准测试，process.extractOne 的代码略有更改以删除 score_cutoff 参数。这样做是因为在 extractOne 中，每当找到更好的匹配时 score_cutoff 就会增加（一旦找到完美匹配就会退出）。将来，对没有此行为的 process.extract 进行基准测试会更有意义（基准测试使用 process.extractOne 执行，因为 process.extract 尚未在 C++ 中完全实现）。可以找到基准代码 here
这表明在可能的情况下不应直接使用记分器，而应通过处理器使用，这样可以执行更多优化。
备选
作为替代方案，您可以使用 C++ 实现。 RapidFuzz 库可用于 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 万 words/sec 和 1.23 亿 words/sec。这大约是 Python 实现的 1.5 倍（由于 Python 和 C++ 类型之间的转换）。然而，C++ 版本的主要优点是您可以相对自由地以任何方式组合算法，而在 Python 版本中，您被迫使用 C++ 中实现的 process 函数来实现良好的效果性能。
来晚了，但这里有一个可能的解决方案 如果我是你的情况我会实施：
将数据集保存为文本文件，并将该文件放在一个非常 快速磁盘区域（最好在 tmpfs 上）。
准备一台具有许多 CPU 个物理内核的强大计算机（例如 作为具有 64 个内核的 Threadripper 3990X）。
使用 this implementation and GNU parallel 来理解数据集。
以下是此解决方案背后的一些技术信息：
Myers 算法的优化版本（上面链接）可以 在单个 CPU 核心上每秒处理大约 1400 万个条目。
如果能充分利用全部64个物理核心，就可以 存档每秒 8.96 亿的吞吐量（= 14m * 64 核）。
这个速度，你可以单次查询100亿 使用一台机器在 12 秒内处理数据集。
我在 this article 上发布了更详细的分析。 如文章所示，我可以对 1 亿条记录的数据集执行查询 用我便宜的台式机在 1.04 秒内。
通过使用性能更高的 CPU（或将任务拆分为 多台计算机），我相信你可以存档想要的结果。 希望这有帮助。