判断两个字符串在Javascript中是否相似？

Question

假设我有两个字符串，有什么方法可以检查它们是否至少 90% 相似？

var string1 = "theBoardmeetstoday,tomorrow51";
var string2 = "Board meets today, tomorrow";

谢谢，

泰根

Answer 1

Levenshtein distance 的 wikipedia 条目包含一个示例实现。

Answer 2

jsdifflib 是 Python 优秀 difflib 库。

它有一个函数 ratio()，该函数“以 [0, 1] 范围内的浮点形式返回序列相似性的度量。”

Answer 3

另请考虑骰子系数，它被认为“基本上更好”比 string-similarity github 存储库及其相应的 npm 模块。

其文档中的用法：

var stringSimilarity = require('string-similarity');

var similarity = stringSimilarity.compareTwoStrings('healed', 'sealed'); 

var matches = stringSimilarity.findBestMatch('healed', ['edward', 'sealed', 'theatre']);

Answer 4

String.levenshtein（MooTools 插件）

查看一下： http://mootools.net/forge/p/string_levenshtein

GitHub：https://github.com/thinkphp/String.levenshtein

这个方法计算两个字符串之间的编辑距离。在信息论和计算机科学中，编辑距离是衡量两个序列之间差异量（称为编辑距离）的度量。两个字符串之间的编辑距离由将一个字符串转换为另一个给定字符串所需的最小操作数给出，其中可能的操作是插入、删除或替换单个字符。

Levenshtein 距离算法已用于：

• 拼写检查
• 语音识别
• DNA 分析
• 抄袭检测

Answer 5

借助其他人的答案，我编写了一个简单的 js 函数 stringsAreSimilar 来执行此操作：

// https://github.com/thinkphp/String.levenshtein/blob/master/Source/String.levenshtein.js

function getStringDifference(stringA, stringB) {
  var cost = [],
    str1 = stringA,
    str2 = stringB,
    n = str1.length,
    m = str2.length,
    i, j;

  var minimum = function (a, b, c) {
    var min = a;
    if (b < min) {
      min = b;
    }
    if (c < min) {
      min = c;
    }
    return min;
  };

  if (n == 0) {
    return;
  }
  if (m == 0) {
    return;
  }

  for (var i = 0; i <= n; i++) {
    cost[i] = [];
  }

  for (i = 0; i <= n; i++) {
    cost[i][0] = i;
  }

  for (j = 0; j <= m; j++) {
    cost[0][j] = j;
  }

  for (i = 1; i <= n; i++) {

    var x = str1.charAt(i - 1);

    for (j = 1; j <= m; j++) {

      var y = str2.charAt(j - 1);

      if (x == y) {

        cost[i][j] = cost[i - 1][j - 1];

      } else {

        cost[i][j] = 1 + minimum(cost[i - 1][j - 1], cost[i][j - 1], cost[i - 1][j]);
      }

    } //endfor

  } //endfor

  return cost[n][m];
}

function stringsAreSimilar(stringA, stringB) {
  var difference = getStringDifference(stringA, stringB);
  debugConsoleLog("stringA" + stringA);
  debugConsoleLog("stringB" + stringB);
  debugConsoleLog("difference" + difference);
  
  return difference < 10;
}

var string1 = "theBoardmeetstoday,tomorrow51";
var string2 = "Board meets today, tomorrow";

if(similar) {
    console.log("they are similar");
} else {
    console.log("they are not similar");
}

Answer 6

所以去年我就想这么做。我读到 Levenshtein distance 是 OP 在此询问的解决方案。

我看到了一个线程中的代码，但没有得到太多的支持。也许是因为它的时间复杂度（在 for 循环中有一个 for 循环）。我尝试过，它似乎对我有用。该函数返回一个分数，其中 0 表示非常匹配，另一方面，较高的分数意味着偏离接近的匹配。我将分享，也许有人可以扩展它或更好地解释它：

function editDistance(s1, s2) {
    s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();

    var costs = new Array();
    for (var i = 0; i <= s1.length; i++) {
        var lastValue = i;
        for (var j = 0; j <= s2.length; j++) {
            if (i == 0) costs[j] = j;
            else {
                if (j > 0) {
                    var newValue = costs[j - 1];
                    if (s1.charAt(i - 1) != s2.charAt(j - 1))
                        newValue =
                            Math.min(Math.min(newValue, lastValue), costs[j]) +
                            1;
                    costs[j - 1] = lastValue;
                    lastValue = newValue;
                }
            }
        }
        if (i > 0) costs[s2.length] = lastValue;
    }
    return costs[s2.length];
}

祝你好运并分享你对此的想法 - 那就太棒了！干杯!