Levenshtein距离:如何更好地处理单词交换位置？

Question

我使用PHP levenshtein函数比较字符串有一些成功.

但是,对于包含已交换位置的子串的两个字符串,算法会将这些字符串计为全新的子字符串.

例如:

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

被视为没有共同点:

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

我更喜欢一种算法,它看到前两个更相似.

我怎么能想出一个比较函数,它可以识别将位置切换为与编辑不同的子串？

我想到的一种可能的方法是在比较之前将字符串中的所有单词按字母顺序排列.这使得单词的原始顺序完全脱离了比较.然而,这样做的一个缺点是,只更改一个单词的第一个字母可能会造成比单个字母更改所造成的更大的中断.

我想要实现的是比较两个关于自由文本字符串的人的事实,并决定这些事实表明相同事实的可能性.事实可能是有人上学的学校,例如雇主或出版商的名字.两个记录可能有相同的学校拼写不同,单词的顺序不同,额外的单词等,所以如果我们要好好猜测他们指的是同一所学校,那么匹配必须有些模糊.到目前为止,它在拼写错误方面表现得非常好(我使用的是一种类似于metaphone的phoenetic算法),但是如果你改变学校中常见的单词顺序则非常糟糕:"xxx college"vs "xxx学院".

Answer 1

N元

使用N-gram,它支持整个文本中的多字符转置.

一般的想法是你将所讨论的两个字符串分成所有可能的2-3个字符子串(n-gram),并将两个字符串之间的共享n-gram数量视为它们的相似性度量.然后可以通过将共享数除以较长字符串中的n-gram总数来对其进行归一化.这很难计算,但相当强大.

对于例句:

A. The quick brown fox
B. brown quick The fox
C. The quiet swine flu

A和B分享18 克2克

A和C只分享8个 2克

出的20总的可能.

这已在Gravano等人中更详细地讨论过.纸.

tf-idf和余弦相似度

一个不那么简单的替代方案,但基于信息理论将使用术语频率 - 逆文档频率(tf-idf)来权衡令牌,构造句子向量,然后使用余弦相似度作为相似性度量.

算法是:

1. 计算每个句子的2个字符的令牌频率(tf).
2. 计算逆句频率(idf),它是语料库中所有句子数(在这种情况下为3)的商的对数除以特定标记在所有句子中出现的次数.在这种情况下,th在所有句子中,因此它具有零信息内容(log(3/3)= 0).
3. 通过将tf和idf表中的相应单元相乘来生成tf-idf矩阵.
4. 最后,计算所有句子对的余弦相似度矩阵,其中A和B是来自tf-idf表的权重,用于相应的标记.范围从0(不相似)到1(相等).
   
   

Levenshtein修改和Metaphone

关于其他答案.Damerau-Levenshtein修改仅支持两个相邻字符的转置.Metaphone旨在匹配听起来相同而不是相似匹配的单词.

Answer 2

这很简单.只需使用Damerau-Levenshtein距离而不是字母.

Answer 3

爆炸空间,排序数组,内爆,然后做Levenshtein.