大规模字符串比较

Question

我正在尝试在大型字符串集中查找相似的字符串对。我有大约 1 亿个字符串，字符串相似性用编辑距离来衡量。例如，"this is a sentence" 和 "this is also a sentence" 是相似的。

计算每两个字符串之间的相似度是不切实际的，导致100M x 100M的计算。我正在考虑一种分而治之的策略，首先将字符串分组为 "roughly similar" 个子集，然后计算子集中的每个字符串对。例如，假设我有以下 5 个字符串，

str1 = "this is a sentence"
str2 = "this is also a sentence"
str3 = "Mary loves elephants"
str4 = "Mary loves an elephant"
str5 = "Mark loves elephants"

我希望有一个子集[str1, str2] 和另一个子集[str3, str4, str5]。然后我将比较 str1 和 str2 看它们是否相似。我还将比较 str3、str4、str5 以找到相似的一对。总计算量将从C^2_5=10减少到C^2_2+C^2_3=4.

分度要快，不要求分得准。子集可以重叠。如果偶尔一个字符串的相似对不包含在同一个子集中是可以接受的，--那么我将扫描一个附近的子集。

我试图找到一种保留顺序的哈希方法来粗略地将字符串映射到整数（冲突无关紧要），并根据具有接近整数的候选字符串检查每个字符串。但是我没找到这样的算法。

我正在使用 Python，如果解决方案仅适用于另一种编程语言，我将愿意尝试。

非常感谢。

Answer 1

您可以在排序时使用 Levenshtein 距离作为关键函数。

import requests
import Levenshtein as L

def download_moby_dick():
    moby_dick_url = 'https://www.gutenberg.org/files/2701/2701-0.txt'
    return requests.get(moby_dick_url).text

def sentences_in_book(book):
    sentences = (s for s in re.split(r'[.;?!]\s|\r\n\r\n', moby_dick))
    sentences = (re.sub('\s+', ' ', s).strip() for s in sentences)
    sentences = (s for s in sentences if len(s) > 10)
    return list(sentences)

sentences = sentences_in_book(download_moby_dick())

# sort by length
sentences.sort(key=len)

# median length sentence
target = sentences[len(sentences)//2]

# sort by levenshtein distance to target
def keyfunc(sentence):
    return L.distance(target, sentence) 

sentences.sort(key=keyfunc)

这将给出一个粗略的顺序，将相似的句子组合在一起。为了加快速度，您可能需要进一步拆分任务。例如通过仅使用每个单词中的一些字母来缩写输入句子，仅搜索长度大致相同的句子等

大规模字符串比较

large-scale string comparison

python

string-comparison

large-data