字符串相似度 -> 莱文斯坦距离

Question

我正在使用莱文斯坦算法来寻找两个字符串之间的相似度。这是我正在制作的程序中非常重要的一部分，因此它需要非常有效。

问题在于该算法不会将以下示例视为相似：

CONAIR
AIRCON

该算法将给出6的距离。所以对于这个有6个字母的单词（查看具有最多字母的单词），差异是100％=> 相似度为0％。

我需要找到一种方法来查找两个字符串之间的相似性，并考虑到像我之前提到的情况。

有没有更好的算法可以使用？还是你们有什么建议？

编辑：我还研究了"达马劳-莱文斯坦"算法，它添加了转置。但问题在于这些转置仅适用于相邻字符（而不适用于多个字符）。

- Fede Lerner

---

在你能够想出一个字符串距离算法之前，你需要清晰地定义哪些转换是可以接受的。是什么让这些字符串比两个随机的6个字母的字符串更相似？你能否以一种方式表达它，使得你可以从一个字符串“爬山”到另一个字符串，每一步都变得更加相似？ - Nick Johnson

Answer 1

我会将术语分成一元组、二元组和三元组，然后计算余弦相似度。

- maniek

---

对于任何想要了解如何实际操作的人，可以参考以下链接：https://gist.github.com/darcy/2896009 - keithhackbarth

Answer 2

我认为可以通过在其中一个字符串（例如“conair”）上应用最长公共子串/子序列算法，并将另一个字符串附加到其本身一次（例如“aircon”->“airconaircon”）来轻松解决此问题。

以下是C语言示例代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Returns the length of the longest common substring (LCS)
// between two given strings.
//
// This recursive implementation can be replaced by a
// more performant dynamic programming implementation.
size_t llcs(const char* s1, const char* s2)
{
  size_t len[3];

  if (*s1 == '\0' || *s2 == '\0') return 0;

  len[0] = (*s1 == *s2) + llcs(s1 + 1, s2 + 1);
  len[1] = llcs(s1 + 1, s2);
  len[2] = llcs(s1, s2 + 1);

  if (len[0] < len[1]) len[0] = len[1];
  if (len[0] < len[2]) len[0] = len[2];

  return len[0];
}

// Returns similarity of two given strings in the range
// from 0.0 to 1.0 (1.0 for equal strings).
double similarity(const char* s1, const char* s2)
{
  size_t s1len = strlen(s1);
  size_t s2len = strlen(s2);
  double sim;

  if (s1len == 0 && s2len == 0)
  {
    // Two empty strings are equal
    sim = 1;
  }
  else
  {
    size_t len;
    // Append s1 to itself in s1s1 (e.g. "aircon" -> "airconaircon")
    char* s1s1 = malloc(s1len * 2 + 1);
    strcpy(s1s1, s1);
    strcpy(s1s1 + s1len, s1);

    // Find the length of the LCS between s1s1 and s2
    // (e.g. between "airconaircon" and "conair")
    len = llcs(s1s1, s2);
    // We need it not longer than s1 (e.g. "aircon")
    // since we're actually comparing s1 and s2
    if (len > s1len) len = s1len;

    len *= 2;

    // Prevent 100% similarity between a string and its
    // cyclically shifted version (e.g. "aircon" and "conair")
    if (len == s1len + s2len && strcmp(s1, s2) != 0) len--;

    // Get the final measure of the similarity
    sim = (double)len / (s1len + s2len);

    free(s1s1);
  }

  return sim;
}

int main(int argc, char** argv)
{
  if (argc == 3)
    printf("Similarity of \"%s\" and \"%s\" is %.2f%%\n",
           argv[1], argv[2], 100 * similarity(argv[1], argv[2]));
  else
    printf("Usage:\n  %s string1 string2\n",
           argv[0]);
  return 0;
}

样本输出：

Similarity of "123" and "123" is 100.00%
Similarity of "123" and "1234" is 85.71%
Similarity of "0123" and "123" is 85.71%
Similarity of "a" and "aa" is 66.67%
Similarity of "aa" and "a" is 66.67%
Similarity of "aaaaaaa" and "aaaaaa" is 92.31%
Similarity of "aaaaaa" and "aaaaaaa" is 92.31%
Similarity of "aircon" and "conair" is 91.67%
Similarity of "spit" and "pits" is 87.50%
Similarity of "pits" and "spit" is 87.50%
Similarity of "spits" and "pits" is 88.89%
Similarity of "pits" and "spits" is 88.89%

- Alexey Frunze

---

谢谢，我已经实现了这种方法。我认为这种方法本身并不是找到两个字符串相似度的最佳方式（因为它无法正确处理许多情况），但如果你同时使用其他方法，它肯定是一个很好的选择。因此，我可能会加入这条规则，并结合其他规则来计算相似度。 - Fede Lerner

添加转置是微不足道的。 - Alexey Frunze

这确实是一个非常有趣的方法。你是自己想出来的还是这是一种已知的方法？ - druskacik

@druskacik 是我自己发明的。 - Alexey Frunze

Answer 3

对单词进行排序并找到Levenshtein，可以为您的示例提供100％匹配，但它也将为例如提供100％匹配。

CONAIR
RCIAON

也许并不是您想要的。

另一种定义相似度的方式是查找两个字符串的共同子字符串。您可以创建后缀树，找出所有公共子字符串，并尝试确定它们的相似程度。因此，对于您的例子，后缀树将给出共同子字符串CON和AIR，涵盖整个单词（对于您的2个字符串），从而得出它们相似的结论。

- user1168577

Answer 4

听起来你可能想尝试使用音节或音素而不是字母来进行Levenshtein距离计算。

- Sam Mussmann

---

我已经尝试过这种方法，使用音节。问题在于当你发现两个单词的音节分割方式取决于它们在单词中的位置时（不确定这是否是正确的英语单词分割方式，实际上我是用西班牙语做的）。 <code> CO NAIR AIR CON </code> - Fede Lerner

Answer 5

理论上，您正在使用的方法对于您要解决的问题是正确的。但是，Levenstein只会考虑两个集合中的单个字符。

可以使用最长公共子序列方法找到字符串相似度，然后可以在其余不匹配的部分上使用Levenstein。

如果您想要进行聚类方法，则以下答案似乎有一些详细信息，但显然更难实现。

- Senthil Kumaran

---

最长公共子序列方法与Levenshtein方法完全相同。Levenshtein距离是字符串长度差异和它们的LCS长度之和。 - reinierpost

Answer 6

尝试使用其他相似度度量方法，如Sorenson、Jaccard和Jaro Winkler。

个人而言，我非常喜欢Jaro Winkler，因为它在许多场合都能满足我的需求。

from Levenshtein import jaro_winkler
In [2]: jaro_winkler("conair","aircon")
Out[2]: 0.8333333333333334

- Yaswanth

Answer 7

请看Needleman-Wunsch算法或Smith-Waterman算法。它们用于通过适应的编辑距离处理DNA序列的字符串匹配，其中可以发生任何类型的插入、反转、转座子，长度和位置也都可以。但需要注意的是，对于足够长的字符串，不存在最优解。此外，编辑成本取决于算法的使用上下文（语义问题），而任何算法都是一个句法机器。

- monnoo