logo标签列表

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

phpalgorithmlevenshtein-distancesimilarityedit-distance
36
我在使用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的音标算法），但如果你改变单词的顺序，它的表现非常差，而这在学校中似乎很常见：“xxx学院”与“学院xxx”。
你想要实现什么目标？Levenshtein有一个理论上简单的方法来检测小差异，例如识别打字错误。如果你的目标不同，你首先需要找到一种理论上的方法来区分两个字符串之间的“差异”，然后实现只是技艺问题。 - Csaba Kétszeri
9个回答
25

N-grams

使用N-grams，支持整个文本中的多字符转置。

总体思路是将两个字符串拆分成所有可能的2-3个字符子字符串（n-grams），并将两个字符串之间共享的n-grams数量视为它们的相似度指标。然后可以通过将共享数量除以较长字符串中的总n-grams数量来进行归一化。这很容易计算，但非常强大。

例如：

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

A和B共享18个2-gram

A和C只共享8个2-gram

总共有20个可能的。

这在Gravano et al. paper中有更详细的讨论。

tf-idf和余弦相似度

一种不那么琐碎的替代方法，但基于信息理论，是使用术语词频-逆文档频率（tf-idf）来加权标记，构建句向量，然后使用余弦相似度作为相似性度量。

算法如下:

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

Levenshtein修改和Metaphone

关于其他答案。Damerau-Levenshtein修改仅支持两个相邻字符的转置。Metaphone旨在匹配发音相同的单词，而不是用于相似性匹配。

1
我们可以两者兼顾吗？将术语分成二元组，然后找到余弦相似度？ - jxn
1
@Jenn 很好的问题，答案是肯定的，请参见http://ii.nlm.nih.gov/MTI/Details/trigram.shtml。 - Tomasz
1
谢谢您在写这篇文章时告诉我关于 n-gram 的知识。自从那以后，我已经在很多不同的项目中使用了基于单词（而不是单个字符）的 n-gram。 - thomasrutter
10
你的意思是：“对于A中的每个单词，找到它与B中每个单词的莱文斯坦距离，然后将结果相加”吗？ - thomasrutter
2
不，我的意思是将每个单词都转换为符号：例如 The = a，quick = b，brown = c等。然后在此基础上运行Levenshtein算法。 - Unknown
2
那么你可以看看类似的算法，比如http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance。 - Unknown
我喜欢这个Damerau-Levenshtein距离（包括转置）的声音。现在唯一让我担心的是，在PHP代码中实现它会慢多少。感谢您的提示！ - thomasrutter
一个实际的例子，展示“简单”距离是基于单词而不是字母的，这将非常棒。 - Nancy
显示剩余2条评论
6

按空格拆分字符串，对数组进行排序，再将其合并为字符串，最后进行Levenshtein操作。

1
这不会检测置换。 - winwaed
3
你也可以尝试这个。（只是额外的建议）
$one = metaphone("The quick brown fox"); // 0KKBRNFKS
$two = metaphone("brown quick The fox"); // BRNKK0FKS
$three = metaphone("The quiet swine flu"); // 0KTSWNFL

similar_text($one, $two, $percent1); // 66.666666666667
similar_text($one, $three, $percent2); // 47.058823529412
similar_text($two, $three, $percent3); // 23.529411764706

这将显示第一和第二个比第一个和第三个以及第二个和第三个更相似。

我认为分数的提高更多是来自于使用similar_text而不是metaphone。我目前正在使用与metaphone非常相似的音标算法。我还没有深入研究过similar_text使用的算法。我一直以为它比levenshtein要低效得多，但我想你得到你所付出的代价。我可能会尝试一下。 - thomasrutter
我尝试了只使用相似的文本，但得分比起一和三之间的得分要低得多，而且在一和二之间也得分较低。 - Ólafur Waage
3
我一直在实现一个拼写检查器中的莱文斯坦算法。
您要求计算转位作为1次编辑。
如果您只希望计算一个单词的转位，这很容易。但是对于两个或更多单词的转位，添加到算法中的情况最坏的情况是!(max(wordorder1.length(), wordorder2.length()))。将非线性子算法添加到已经是二次算法的算法中并不是一个好主意。
这是它的工作原理。
if (wordorder1[n] == wordorder2[n-1])
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1, workarray[x-2, y-2]);
}
  else
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1);
}

仅适用于简单的转位。如果您想要全部的转位，您需要从每个位置开始向后比较。

1[n] == 2[n-2].... 1[n] == 2[0]....

所以你可以看到为什么他们不将此纳入标准方法中。
1

参考 this answer 并进行以下更改：

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
  /* TRY SWAPPING FIRST TWO CHARACTERS */
  if (w[1]){
    swap(w[0], w[1]);
    match(t, w, s, budget-1);
    swap(w[0], w[1]);
  }
}

这是用于字典搜索的 trie，但对于匹配单个单词来说，它是相同的思路。您正在执行分支限界，并且在任何时候，您都可以进行任何更改，只要您给出一个成本。

这看起来可能非常有用，尽管我需要进行一些研究才能弄清它是如何工作的。我以前没有使用过 Trie，所以我会进行调查。 - thomasrutter
@thomas。只有在搜索字典时才需要trie。如果你只是比较两个字符串（或列表），那么“foreach”就成为一个简单的语句块。递归分支界限法是一个非常有用的瑞士军刀。 - Mike Dunlavey
1

我相信这是使用向量空间搜索引擎的一个典型例子。

在这种技术中，每个文档本质上都成为一个向量，其维数与整个语料库中不同单词的数量相同；相似的文档则占据该向量空间中相邻的区域。这个模型的一个好处是查询也只是文档：要回答一个查询，你只需计算它们在向量空间中的位置，然后你的结果就是你能找到的最接近的文档。我相信有一些PHP的即插即用解决方案。

为了模糊化向量空间的结果，您可以考虑进行词干提取/类似的自然语言处理技术，并使用Levenshtein构建次要查询，以获取在您的整体词汇表中出现的类似单词。

1

消除两个字符串之间的重复单词，然后使用Levenshtein算法。

0
如果第一个字符串是A，第二个字符串是B：
  1. 将A和B拆分成单词
  2. 对于A中的每个单词，在B中找到最佳匹配单词（使用levenshtein算法）
  3. 从B中删除该单词，并将其放入B*中，与A中匹配的单词在相同的索引处。
  4. 现在比较A和B*

示例：

A: The quick brown fox
B: Quick blue fox the
B*: the Quick blue fox

你可以通过多次操作来改进第二步，首先只查找精确匹配项，然后查找A中没有与B中对应的单词的相似匹配项，接着是更少相似的匹配项等。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接