精通 JavaScript 中的莱文斯坦距离

简介

在本实验中，我们将探索莱文斯坦距离（Levenshtein Distance）算法及其在JavaScript中的实现。本实验的目的是了解如何通过测量将一个字符串转换为另一个字符串所需的最少单字符编辑（插入、删除、替换）次数来计算两个字符串之间的差异。在本实验结束时，你将对莱文斯坦距离算法以及如何在自己的JavaScript项目中使用它有深入的理解。

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL javascript(("JavaScript")) -.-> javascript/BasicConceptsGroup(["Basic Concepts"]) javascript(("JavaScript")) -.-> javascript/ToolsandEnvironmentGroup(["Tools and Environment"]) javascript/BasicConceptsGroup -.-> javascript/variables("Variables") javascript/BasicConceptsGroup -.-> javascript/data_types("Data Types") javascript/BasicConceptsGroup -.-> javascript/arith_ops("Arithmetic Operators") javascript/BasicConceptsGroup -.-> javascript/comp_ops("Comparison Operators") javascript/BasicConceptsGroup -.-> javascript/cond_stmts("Conditional Statements") javascript/BasicConceptsGroup -.-> javascript/loops("Loops") javascript/BasicConceptsGroup -.-> javascript/array_methods("Array Methods") javascript/ToolsandEnvironmentGroup -.-> javascript/debugging("Debugging") subgraph Lab Skills javascript/variables -.-> lab-28469{{"在 JavaScript 中实现莱文斯坦距离"}} javascript/data_types -.-> lab-28469{{"在 JavaScript 中实现莱文斯坦距离"}} javascript/arith_ops -.-> lab-28469{{"在 JavaScript 中实现莱文斯坦距离"}} javascript/comp_ops -.-> lab-28469{{"在 JavaScript 中实现莱文斯坦距离"}} javascript/cond_stmts -.-> lab-28469{{"在 JavaScript 中实现莱文斯坦距离"}} javascript/loops -.-> lab-28469{{"在 JavaScript 中实现莱文斯坦距离"}} javascript/array_methods -.-> lab-28469{{"在 JavaScript 中实现莱文斯坦距离"}} javascript/debugging -.-> lab-28469{{"在 JavaScript 中实现莱文斯坦距离"}} end

莱文斯坦距离算法

要计算两个字符串之间的差异，你可以使用莱文斯坦距离算法。具体做法如下：

如果任一字符串的 length 为零，则返回另一个字符串的 length。
使用嵌套的 for 循环遍历目标字符串和源字符串的各个字符。
分别计算在目标字符串和源字符串中替换对应于 i - 1 和 j - 1 的字符的成本（如果它们相同则为 0，否则为 1）。
使用 Math.min() 用以下三者中的最小值填充二维数组中的每个元素：上方单元格的值加一、左侧单元格的值加一、左上角单元格的值加上先前计算的成本。
返回生成数组最后一行的最后一个元素。

要开始练习这段代码，打开终端/SSH 并输入 node。以下是你可以使用的代码：

const levenshteinDistance = (s, t) => {
  if (!s.length) return t.length;
  if (!t.length) return s.length;
  const arr = [];
  for (let i = 0; i <= t.length; i++) {
    arr[i] = [i];
    for (let j = 1; j <= s.length; j++) {
      arr[i][j] =
        i === 0
          ? j
          : Math.min(
              arr[i - 1][j] + 1,
              arr[i][j - 1] + 1,
              arr[i - 1][j - 1] + (s[j - 1] === t[i - 1] ? 0 : 1)
            );
    }
  }
  return arr[t.length][s.length];
};

console.log(levenshteinDistance("duck", "dark")); // 2

总结

恭喜你！你已经完成了莱文斯坦距离实验。你可以在LabEx中练习更多实验来提升你的技能。