莱文斯坦距离基本原理

关键词Levenshtein Distance一、说明莱文斯坦距离是用于衡量两个序列之间差异的字符串度量计算将一个字符串转换为另一个字符串所需的最少单字符编辑次数——插入、删除或替换。该算法由弗拉基米尔·列文斯坦于1965年开发广泛应用于拼写检查器、DNA分析和模糊字符串匹配。 本文仅关注莱文斯坦距离不会深入探讨算法的复杂度、转置或可变操作成本。二、从实际问题引出在开发一个项目的过程中我遇到了一个棘手的挑战。我需要为用户提供一个用于搜索标签的文本框。问题在于标签通常比较长导致用户在输入时容易出现拼写错误。在这种情况下我有两个选择要么要求用户输入标签的完整名称要么提供一定的搜索灵活性即使存在一些小的拼写错误也能找到匹配项。例如用户可能输入“汽车和赛车运动”而实际标签却是“汽车.赛车运动”。这虽然只是细微的差别但足以导致标准搜索找不到匹配项。为了解决这个问题我实现了莱文斯坦距离计算方法。该方法可以确定将一个字符串转换为另一个字符串所需的插入、删除和替换操作次数。通过这种方法我不仅能够找到最相似的标签还能向用户展示几个相关的标签。在我的任务中我将莱文斯坦距离的阈值设定为 5。这意味着如果将输入的字符串转换为现有标签只需要不超过五次的插入、删除或替换操作则该标签被认为是合适的。如果需要更多修改我希望向用户显示没有找到符合其查询条件的标签。选择 5 这个数字是出于直觉。在实际操作中处理字符串及其比较时通常会使用高级算法这些算法不仅考虑基本的莱文斯坦距离还考虑字符替换、转置和其他操作等其他方面。为了确定莱文斯坦距离使用以下公式莱文斯坦公式这是一个用于计算长度分别为 M 和 N 的两个字符串 S1 和 S2 之间的莱文斯坦距离的递归公式。首先需要理解的是如果两个字符串都为空则它们之间的距离为 0。其次如果第一个字符串为空而第二个字符串的长度大于 0等于 N则需要执行 N 次插入操作才能使第一个空字符串与目标字符串匹配。因此如果 M 0 且 N 0则莱文斯坦距离为 N。最后如果 M 0 且 N 0则需要执行 M 次删除操作才能使目标字符串与目标空字符串匹配此时莱文斯坦距离为 M。三、算法分析如果两个字符串都不为空计算莱文斯坦距离的算法首先构建一个矩阵。在这个矩阵中第一行将原始字符串的符号分别放置在不同的列中第一列将待变换字符串的符号分别放置在不同的单元格中。实际上字符串的顺序可以任意因为将字符串 A 变换为字符串 B 所需的距离与将字符串 B 变换为字符串 A 所需的距离相同。此外每行的第一个符号应代表空字符串。这些空字符串对于计算基本情况至关重要。为了说明这一点我们来计算一下字符串 APPLE 和 APRLE 之间的莱文斯坦距离。矩阵初始化所需的距离值位于右下角的单元格中。要计算每个单元格的值我们需要知道其上方、左侧以及左对角线上的单元格的值。这意味着要获得右下角单元格的值我们必须计算整个矩阵中的值。首先我们需要将原始字符串的每个子字符串与待转换字符串的每个子字符串与空字符串进行比较。这被称为基准情况它将使我们能够获得初始数据以便后续正确地填充矩阵。当比较两个空字符串时显然将一个空字符串转换为另一个空字符串所需的运算次数为零。因此矩阵中的第一个值为 0。第一细胞接下来我们填充第一行和第一列。为了计算其他单元格的值我们将使用其左侧、上方以及左上方对角线上的单元格的值。但对于第一行我们只有左侧的单元格。左侧的单元格用于执行删除操作。因此使用公式D(i, j-1) 1其中i始终为 0因为它是第一行我们发现每个后续单元格的值都应该比前一个单元格的值大 1。这告诉我们例如要将子字符串APP删除为空字符串我们需要执行三次删除操作。第一列的情况也类似。唯一的区别在于对于第二列我们考虑的是插入操作的次数因为我们只能访问其上方的单元格。这样我们就可以回答例如“将空字符串转换为子字符串APR需要多少次插入操作”这样的问题。基本情况接下来对于每个单元格我们需要执行三个小操作得到这些操作的值找出这三个值中的最小值并将其记录在相应的单元格中。对于表示字符 A 和 A 交集的单元格 [1,1]我们需要检查删除的成本、插入的成本和替换的成本。给定单元格的值为i 1j 1。删除的代价是[i, j-1] 1 [1, 0] 1 1 1 2。插入成本为[i-1, j] 1 [0, 1] 1 1 1 2。替代成本为[i-1, j-1] m(a, b) [0, 0] m(a, b) 0 0 0。这里m(a, b) 是一个比较两个字符的函数如果两个字符相同则返回 0如果不同则返回 1。因此我们可以得出结论min(2, 2, 0) 等于 0所以单元格 D(1, 1) 的值为 0。在不同的情况下操作的成本可能会有所不同。在这种常规情况下删除、插入和替换操作的成本都相同即 1。细胞 1,1有人可能会问为什么我们需要用基本值初始化矩阵在上面的例子中最终的矩阵如下所示显然在替换操作的情况下单元格左侧和上方的值总是大于对角线上的值替换值。完整矩阵这是因为在上面的例子中我们比较的是长度相同的字符串删除、插入和替换操作的成本都相同。在这种情况下最优操作始终是替换如果替换的是不同的字符则最优操作是不进行任何操作。这是因为莱文斯坦距离公式的设计目标是最优的而替换操作比任何删除和插入的组合都更高效。因此在字符串长度相同且所有操作成本都相同的情况下可以通过仅计算对角线值来优化算法因为对这些字符串进行插入和删除操作的成本总是更高。但是如果我们考虑长度不同的字符串例如APP和APRLE情况就有所不同了。APP 和 APRLE 的矩阵在这种情况下我们不仅需要考虑替换操作还需要考虑删除操作。为了得到这个矩阵我们只需要从原矩阵中删除最后两列。然后我们立即看到右下角单元格中的值这将是问题的答案APP和APRLE之间的莱文斯坦距离是多少。计算莱文斯坦距离时最重要的是要理解它很大程度上依赖于累积效应。我们需要找到右下角单元格的值而只有准确计算出每个子串与其他所有子串之间的距离才能正确计算出该值。四、代码实现用 JavaScript 实现 Levenshtein 距离。代码尽可能简洁以便更好地理解其实现原理。function levenshteinDistance ( a, b ) { const matrix []; // 初始化矩阵 for ( let i 0 ; i a. length ; i) { matrix[i] []; for ( let j 0 ; j b. length ; j) { matrix[i][j] 0 ; } } // 基本情况初始化 for ( let i 0 ; i a. length ; i) { matrix[i][ 0 ] i; // 从 a 中删除所有字符的成本 } for ( let j 0 ; j b. length ; j) { matrix[ 0 ][j] j; // 从 b 中插入所有字符的成本 } // 填充矩阵 for ( let i 1 ; i a. length ; i) { for ( let j 1 ; j b. length ; j) { matrix[i][j] Math . min ( matrix[i - 1 ][j] 1 , // 删除 matrix[i][j - 1 ] 1 , // 插入 matrix[i - 1 ][j - 1 ] (a[i- 1 ] b[j- 1 ] ? 0 : 1 ) // 替换 ); } } // 返回莱文斯坦距离它 位于矩阵的右下角 return matrix[a.length ][b.length ] ; }