php - 编辑距离 : how to better handle words swapping positions?

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

我更喜欢一种能够看到前两个更相似的算法。

我怎样才能想出一个比较函数来识别已切换位置的子字符串以区别于编辑？

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

我想要实现的是比较关于人的两个自由文本字符串事实，并确定这些事实表明同一事实的可能性有多大。事实可能是某人就读的学校，例如他们的雇主或出版商的名称。两条记录可能有同一所学校的不同拼写、不同顺序的单词、额外的单词等，因此如果我们要很好地猜测它们指的是同一所学校，则匹配必须有些模糊。到目前为止，它对拼写错误的效果非常好(我在这一切之上使用了一种类似于变音位的语音算法)，但如果你改变在学校里似乎很常见的单词顺序，效果会很差:“xxx college” vs “xxx学院”。

Answer 1

N-gram

使用N-grams ，它支持在整个文本中进行多字符换位。

一般的想法是，将有问题的两个字符串拆分为所有可能的 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-grams

总共 20 个可能。

这已在 Gravano et al. paper 中进行了更详细的讨论。 .

tf-idf 和余弦相似度

一个不那么简单但基于信息论的替代方案是使用术语 term frequency–inverse document frequency (tf-idf)权衡标记，构建句子向量，然后使用 cosine similarity作为相似性度量。

算法是:

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

编辑修饰和变音位

关于其他答案。 Damerau–Levenshtein修改只支持两个相邻字符的转置。 Metaphone旨在匹配听起来相同和不同的单词用于相似性匹配。