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

php algorithm levenshtein-distance similarity edit-distance

2022-08-30 13:09:20

我已经使用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学院”与“xxx学院”。

答案 1

N-克

使用 N 元语法，它支持在整个文本中使用多字符转置。

一般的想法是，您将有问题的两个字符串拆分为所有可能的2-3个字符的子字符串（n-grams），并将两个字符串之间的共享n-gram数视为它们的相似性度量。然后，可以通过将共享数除以较长字符串中的 n 元语法总数来对其进行规范化。这计算起来微不足道，但功能相当强大。

对于示例句子：

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）来权衡令牌，构造句子向量，然后使用余弦相似性作为相似性度量。

算法为：

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