26

我正在使用 Levenshtein 算法来查找两个字符串之间的相似性。这是我正在制作的程序的一个非常重要的部分，因此它需要有效。问题是该算法没有发现以下示例相似：

康奈尔
空调

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

我需要找到一种方法来找到两个字符串之间的相似之处，同时还要考虑到我之前提出的情况。

我可以使用更好的算法吗？或者你们有什么推荐给我的？

编辑：我还研究了添加换位的“Damerau–Levenshtein”算法。问题是这种换位仅适用于相邻字符（而不适用于多个字符）。

4

7 回答 7

11

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

于 2012-07-26T18:00:40.530 回答
6

我认为这可以通过对其中一个字符串（例如“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%
于 2012-07-27T13:52:29.167 回答
2

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

于 2012-07-26T18:04:14.383 回答
2

从理论上讲，您使用的方法对于您要解决的问题是正确的。但列文斯坦只会考虑这两组的个别角色。

字符串相似性也可以使用最长公共子序列方法找到，然后您可以在其余未匹配项上看到 Levenstein。

如果你想做一个集群的方法，下面的答案似乎有一些细节，但显然它更难实现。

于 2012-07-26T18:04:23.060 回答
2

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

CONAIR
RCIAON

这可能不是你想要的。

定义相似性的另一种方法是找出 2 个字符串的公共子字符串。您可以创建后缀树并找出所有常见的子字符串并尝试确定它们的相似程度。因此，对于您的例如，后缀树将提供常见的子字符串作为 CON & AIR，它涵盖了整个单词（对于您的 2 个字符串），因此得出结论它们相似。

于 2012-07-27T08:15:30.680 回答
2

尝试使用其他相似性度量，例如 sorenson、jaccard 和 jaro_winkler

就我个人而言，我是 jaro winkler 的忠实粉丝，因为它多次达到了我的目的。

from Levenshtein import jaro_winkler
In [2]: jaro_winkler("conair","aircon")
Out[2]: 0.8333333333333334
于 2016-09-12T05:57:53.010 回答
1

看看 Needleman-Wunsch 或 Smith-Waterman 算法。它们用于通过调整 DNA 序列的编辑距离来处理字符串匹配，其中任何类型的插入、反转、转座子都可能发生在任何长度、任何位置。说到这里，我需要补充一点，对于足够长的字符串，没有最佳解决方案。并且不要忘记编辑成本取决于算法的使用上下文（语义问题），而任何算法始终是句法机器。

于 2014-01-11T22:50:26.357 回答