测量字符串的相似度（在Javascript中）

Question

原则上，这个问题可以用任何语言回答，但是我正在寻找JavaScript实现的方法。

有没有库可以让我测量两个字符串之间的“相似度”？更普遍地说，是否有任何算法可以做到这一点，我可以在JavaScript中实现？

以以下字符串为例：

Abnormal Elasticity of Single-Crystal Magnesiosiderite across the Spin Transition in Earth’s Lower Mantle 再考虑稍微调整一下的字符串。请注意不同的加粗部分：

bnormal Elasticity of Single Crystal Magne sio-Sid erite across the Spin-Tra nsition in Eart hs Lower Mant le.

JavaScript的本机等号运算符不能告诉您这些字符串之间的关系。在这种特定情况下，您可以使用正则表达式匹配字符串，但通常仅在您知道预期差异时才起作用。如果输入字符串是随机的，则此方法的通用性迅速下降。

方法... 我可以想象编写一种算法，将输入字符串拆分成任意数量的子字符串，然后将目标字符串与所有这些子字符串进行匹配，并使用匹配数作为相似度的衡量标准。但是这感觉像一种不太理想的方法，我甚至不想思考O如何取决于N的大小。

对于这种算法，似乎有很多自由参数。例如，字符的大小写敏感性是否应该对相似度的测量产生同等/更多/更少的贡献，似乎是由设计者做出的任意选择，即：

相似度（“Abxy”，“bAxy”）与相似度（“Abxy”，“aBxy”）

更具体地定义要求...第一个示例是我可以使用它的情况。我正在加载一堆字符串（学术论文标题），并检查它们是否存在于我的数据库中。但是，来源可能包含拼写错误、约定差异、错误等，这使匹配变得困难。在这种特定情况下，可能有更简单的方法来匹配标题：因为您可以预期可能会出现什么问题，所以这允许您编写一些正则表达式。

- Maurits Moeys

---

请求一个图书馆是不恰当的。除此之外，其余内容非常有趣（对我来说），你可以看一下Levenshtein距离。 - Nina Scholz

有趣的是，我不知道这个算法。我已经找到了一个 JavaScript 的实现 在这里。 - Maurits Moeys

你也应该尝试找到最长公共子序列。这就是许多差异工具使用的内容。链接 - Dekay

你可能想要查看我在Code Review上的这个问题和我的回答。 - Redu

您可能也对余弦相似度/距离感兴趣。 cosine similarity/distance - Oleg Kovalov

Answer 1

您可以实现 Hirschberg算法 并区分删除/插入操作
（或更改Levenshtein）。

对于Hirschbers("Abxy", "bAxy")，结果如下：

It was 2 edit operations:
keep: 3
insert: 1
delete: 1

对于Hirschbers("Abxy", "aBxy")，结果如下：

It was 2 edit operations:
keep: 2
replace: 2

您可以在此页面上检查JavaScript实现。

'最佳'字符串对齐距离

function optimalStringAlignmentDistance(s, t) {
  // Determine the "optimal" string-alignment distance between s and t
  if (!s || !t) {
    return 99;
  }
  var m = s.length;
  var n = t.length;
  
  /* For all i and j, d[i][j] holds the string-alignment distance
   * between the first i characters of s and the first j characters of t.
   * Note that the array has (m+1)x(n+1) values.
   */
  var d = new Array();
  for (var i = 0; i <= m; i++) {
    d[i] = new Array();
    d[i][0] = i;
  }
  for (var j = 0; j <= n; j++) {
    d[0][j] = j;
  }
        
  // Determine substring distances
  var cost = 0;
  for (var j = 1; j <= n; j++) {
    for (var i = 1; i <= m; i++) {
      cost = (s.charAt(i-1) == t.charAt(j-1)) ? 0 : 1;   // Subtract one to start at strings' index zero instead of index one
      d[i][j] = Math.min(d[i][j-1] + 1,                  // insertion
                         Math.min(d[i-1][j] + 1,         // deletion
                                  d[i-1][j-1] + cost));  // substitution
                        
      if(i > 1 && j > 1 && s.charAt(i-1) == t.charAt(j-2) && s.charAt(i-2) == t.charAt(j-1)) {
        d[i][j] = Math.min(d[i][j], d[i-2][j-2] + cost); // transposition
      }
    }
  }
  
  // Return the strings' distance
  return d[m][n];
}

alert(optimalStringAlignmentDistance("Abxy", "bAxy"))
alert(optimalStringAlignmentDistance("Abxy", "aBxy"))

Damerau-Levenshtein Distance

function damerauLevenshteinDistance(s, t) {
  // Determine the Damerau-Levenshtein distance between s and t
  if (!s || !t) {
    return 99;
  }
  var m = s.length;
  var n = t.length;      
  var charDictionary = new Object();
  
  /* For all i and j, d[i][j] holds the Damerau-Levenshtein distance
   * between the first i characters of s and the first j characters of t.
   * Note that the array has (m+1)x(n+1) values.
   */
  var d = new Array();
  for (var i = 0; i <= m; i++) {
    d[i] = new Array();
    d[i][0] = i;
  }
  for (var j = 0; j <= n; j++) {
    d[0][j] = j;
  }
  
  // Populate a dictionary with the alphabet of the two strings
  for (var i = 0; i < m; i++) {
    charDictionary[s.charAt(i)] = 0;
  }
  for (var j = 0; j < n; j++) {
    charDictionary[t.charAt(j)] = 0;
  }
  
  // Determine substring distances
  for (var i = 1; i <= m; i++) {
    var db = 0;
    for (var j = 1; j <= n; j++) {
      var i1 = charDictionary[t.charAt(j-1)];
      var j1 = db;
      var cost = 0;
      
      if (s.charAt(i-1) == t.charAt(j-1)) { // Subtract one to start at strings' index zero instead of index one
        db = j;
      } else {
        cost = 1;
      }
      d[i][j] = Math.min(d[i][j-1] + 1,                 // insertion
                         Math.min(d[i-1][j] + 1,        // deletion
                                  d[i-1][j-1] + cost)); // substitution
      if(i1 > 0 && j1 > 0) {
        d[i][j] = Math.min(d[i][j], d[i1-1][j1-1] + (i-i1-1) + (j-j1-1) + 1); //transposition
      }
    }
    charDictionary[s.charAt(i-1)] = i;
  }
        
  // Return the strings' distance
  return d[m][n];
}

alert(damerauLevenshteinDistance("Abxy", "aBxy"))
alert(damerauLevenshteinDistance("Abxy", "bAxy"))

最优字符串对齐具有更好的性能表现

最优字符串对齐距离为0.20-0.30毫秒
达姆罗-莱文斯坦距离为0.40-0.50毫秒

- Panos Kalatzantonakis