快速检查大型数据库以获取编辑距离相似性。

Question

快速检查大型数据库以获取编辑距离相似性。

pythonpython-3.xsimilarityedit-distance

10

我有一个包含350,000个字符串的数据库，平均长度约为500个字符。这些字符串不是由单词组成的，而是基本上是一组随机字符。

我需要确保没有两个字符串太相似，其中“相似性”定义为编辑距离除以字符串平均长度。分母是因为较小的字符串更容易接受较小的编辑距离。如果出于性能原因使用其他指标，则可以接受，但编辑距离是首选基准指标。

朴素地说，我们用运行时间为O(a*b)的方法计算编辑距离，其中a,b是两个字符串的长度。我们对所有n^2对执行此操作，这使得总运行时间为O(n^2*a*b)，很明显对于 n=350,000,a,b=500 会耗时过长。

数据库以Python列表的形式存在于csv文件中。如果可能的话，我希望以Pythonic的方式处理它。

如何加速处理？我不确定朴素算法要花多长时间才能完成(大约需要几周)，但它理想情况下应该在一天内完成。

- Evan Weissburg

1

构建一个FST将使您能够更快地进行搜索。 - user2722968

1

ratio或partial_ratio从https://pypi.python.org/pypi/fuzzywuzzy对您有用吗？还是您只需要编辑距离？ - Tarun Lalwani

应该可以工作@TarunLalwani。问题在于它可能仍然需要太长的时间O(n^2*m)，假设比率以线性m时间运行。 - Evan Weissburg

1

看起来您可能想使用某种局部敏感哈希算法https://en.wikipedia.org/wiki/Locality-sensitive_hashing。对于汉明距离，已经有一些开发好的算法。 - Haochen Wu

我尝试了一下，使用8个核心的速度是每秒3500次比较，这并不起作用。改进的基本思路是不要进行暴力的一对一比较，并减少比较次数。 - Tarun Lalwani

显示剩余10条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Haochen Wu · Accepted Answer

我用Python写了一个非常简单的局部敏感哈希算法的原型。但是，有一些注意事项，你可能也想优化一些部分。我们在看到它们时会提及。假设所有的字符串都存储在strings中。

import random
from collections import Counter

MAX_LENGTH = 500
SAMPLING_LENGTH = 10

def bit_sampling(string, indices):
    return ''.join([string[i] if i<len(string) else ' ' for i in indices])

indices = random.sample(range(MAX_LENGTH),SAMPLING_LENGTH)
hashes = [bit_sampling(string, indices) for string in strings]

counter = Counter(hashes)
most_common, count = counter.most_common()[0]
while count > 1:
    dup_indices = [i for i, x in enumerate(hashes) if x == most_common]
    # You can use dup_indices to check the edit distance for original groups here.
    counter.pop(most_common)
    most_common, count = counter.most_common()[0]

首先，这是比特采样的一种轻微变体，最适用于汉明距离。理想情况下，如果所有字符串长度相同，则可以为汉明距离提供理论概率界限。当两个字符串的汉明距离很小时，它们具有不同哈希的可能性非常小。这可以由参数SAMPLING_LENGTH指定。较大的SAMPLING_LENGTH将更有可能将类似的字符串哈希到不同的哈希中，但也会降低哈希不太相似的字符串到相同哈希的概率。对于汉明距离，您可以轻松计算这种权衡。

多次运行此代码片段可以增加您对没有相似字符串的信心，因为每次都会在不同的位置进行采样。

为了适应您比较不同长度字符串的目的，一种可能的方法是在较短的字符串左侧填充空格并复制它们。

尽管此代码片段中的所有操作都是线性的（O(n)），但仍可能消耗大量内存和运行时间，并且可能可以减少一个常数因子。

您还可以考虑使用更复杂的局部敏感哈希算法，例如在此处进行调查：https://arxiv.org/pdf/1408.2927.pdf