5

我正在尝试使用 python 中的BK-tree数据结构来存储具有约 100 亿个条目（1e10）的语料库，以实现快速模糊搜索引擎。

一旦我将超过 1000 万 ( 1e7) 个值添加到单个 BK 树中，我开始看到查询性能显着下降。

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

这个想法听起来可行吗？我应该同时创建和查询 1,000 个 BK 树吗？为了在这个语料库中使用 BK-tree，我还能做些什么。

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

是否有一些架构或数据库可以让我存储这些树？

注意：我没有用完内存，而是树开始效率低下（大概每个节点都有太多子节点）。

4

2 回答 2

2

几个想法

BK-trees
感谢 Ben Hoyt 和他与我将借鉴的问题的链接。话虽如此，上述问题的第一个观察结果是 BK 树并不完全是对数的。根据您告诉我们的情况，您通常的 d 约为 6，即字符串长度的 3/10。不幸的是，这意味着如果我们查看问题中的表格，您会发现复杂度介于 O(N^0.8) 到 O(N) 之间。在指数为 0.8（可能会稍差）的乐观情况下，您的 10B 条目的改进因子约为 100。因此，如果您有一个相当快速的 BK-trees 实现，那么使用它们或将它们用作进一步优化的基础仍然是值得的。

这样做的缺点是，即使您并行使用 1000 棵树，也只能从并行化中获得改进，因为树的性能取决于d而不是树中节点的数量。但是，即使您使用大型机器一次运行所有 1000 棵树，我们也处于您报告的缓慢的 ~10M 节点/树上。尽管如此，在计算方面，这似乎是可行的。

蛮力方法
如果您不介意花一点钱，我会研究像谷歌云大查询这样的东西，如果它不与某种数据机密性发生冲突。他们将为您强力解决解决方案 - 收费。当前的费率是 5 美元/TB 的查询。您的数据集约为 10B 行 * 20 个字符。每个字符占用一个字节，一个查询将占用 200GB，因此如果您采用懒惰的方式，每个查询约 1 美元。
但是，由于费用是按列中数据的每个字节而不是每个问题的复杂性，您可以通过将字符串存储为位来改进这一点 - 每个字母 2 位，这将为您节省 75% 的费用。
进一步改进，您可以编写查询，使其一次请求十几个字符串。为了查询的目的，您可能需要小心使用一批类似的字符串，以避免过多的一次性操作阻塞结果。

BK-trees的蛮力
因为如果你走上面的路线，你将不得不根据数量付费，所需的计算减少约100倍变成价格减少约100倍，这可能是有用的，尤其是如果您有很多查询要运行。
但是，您需要找到一种方法将此树存储在多层数据库中以递归查询，因为 Bigquery 定价取决于查询表中的数据量。
构建一个用于递归处理查询以最小化成本的智能批处理引擎可能是有趣的优化练习。

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

于 2021-01-18T11:48:13.687 回答
2

FuzzyWuzzy

由于您提到将 FuzzyWuzzy 用作距离度量，因此我将专注于实现fuzz.ratioFuzzyWuzzy 使用的算法的有效方法。FuzzyWuzzy 提供以下两种实现fuzz.ratio：

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

在 python-Levenshtein 中的实现

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

  1. 删除两个字符串的公共前缀和后缀，因为它们对最终结果没有任何影响。这可以在线性时间内完成，因此匹配相似的字符串非常快。
  2. 修剪后的字符串之间的 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)。

删除常用前缀

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

最大距离 <= 4

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

len(shorter string) <= 64 删除常用词缀后

使用 BitPA1 算法，并行计算 Levenshtein 距离。该算法在此处进行了描述，并在此实现中扩展了对 UTF32 的支持。该算法的时间复杂度为O(N)。

长度 > 64 的字符串

Levenshtein 距离是使用 Wagner-Fischer 和 Ukkonens 优化计算的。该算法的时间复杂度为O(N * M)。这可能会在未来被 BitPal 的分块实现所取代。

处理器的改进

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

  1. 当使用同样用 C++ 实现的记分器时，我们可以直接调用记分器的 C++ 实现，而不必在 Python 和 C++ 之间来回切换，这提供了巨大的加速

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

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

基准

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

可重复科学数据的来源：

运行图形基准测试的硬件（规范）：

  • CPU：i7-8550U单核
  • 内存：8 GB
  • 操作系统：Fedora 32

基准得分手

可以在此处找到此基准测试的代码 基准得分手

基准提取一

对于此基准测试，代码process.extractOne稍作更改以删除score_cutoff参数。这样做是因为每当找到更好的匹配时 inextractOne就会score_cutoff增加（一旦找到完美匹配就退出）。process.extract将来，对没有这种行为的基准进行基准测试会更有意义（基准是使用 执行的process.extractOne，因为process.extract尚未在 C++ 中完全实现）。基准代码可以在这里找到 基准提取一

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

选择

作为替代方案，您可以使用 C++ 实现。库 RapidFuzz在此处可用于 C++ 。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++ 中实现的函数来获得良好的性能。

于 2021-01-20T13:45:44.363 回答