莱文斯坦距离（第一部分：它是什么？）

莱文斯坦距离算法看似简单，实则不然——它通过遍历两个字符串，计算出两个字符串之间的“距离”（即差异的数量）。这些差异是根据“插入”、“删除”和“替换”来计算的。

“距离”实际上衡量的是两个字符串的相似程度。距离为 00表示这两个字符串完全相同（没有差异）。距离可以达到最长字符串的字符数——这意味着这两个字符串之间完全没有任何“相似之处”。

莱文斯坦距离算法的一个应用是拼写检查——通过了解两个单词的相似程度，它可以提供你可能想要输入的内容的建议。

计算莱文斯坦距离

以“星期六”和“星期日”这两个词为例。我们对这两个词了解多少？

• 星期六是 8 个字符，星期日是 6 个字符。
• 它们都以“S”开头，以“day”结尾。
• 相对于字符串的开头，共享的“u”位于不同的位置。
• 这样就只剩下星期六的“a”、“t”和“r”以及星期日的“n”这三个字母有所不同了。

计算这两个字符串的莱文斯坦距离实际上就像构建一个值矩阵，该矩阵表示所需的各种插入、删除和替换。

我们来自己构建一个矩阵。我们将从第一行最左边的列开始，填充从 00到字符串每个长度对应的数字。

从星号所在的位置开始，我们将查看上面的单元格（删除成本）、左边的单元格（插入成本）和左上角的单元格（替换成本）。

填充细胞的操作如下：

• 1取插入成本（ ）和删除成本（1）中的最小值，并将其加到1结果（MIN(1,1) + 1 = 2）中。
• 计算替代成本（0），1如果该列（“S”）和行（“S”）上的字母不同，则将其加到替代成本中（0 + 0 = 0）。
• 取这些数字中的最小值（MIN(2,0) = 0），并将其放入我们的单元格中。

对同一行的下一个单元格重复上述步骤：

• 0取插入成本（ ）和删除成本（2）中的最小值，并将其加到1结果（MIN(0,2) + 1 = 1）中。
• 计算替代成本（1），1如果该列（“a”）和行（“S”）上的字母不同，则将其加到替代成本中（1 + 1 = 2）。
• 取这些数字中的最小值（MIN(1,2) = 1），并将其放入我们的单元格中。

整行都是如此：

最终整张桌子都被搬走了：

实际的莱文斯坦距离可以在右下角的单元格中找到（3）。很神奇吧？

“看似简单”

我之前说过，这个算法看似简单——这是因为它的计算复杂度很高。它的“大O”表示法是，O(n*m)其中n表示一个字符串的长度，m表示另一个字符串的长度。从内存角度来看，构建上述矩阵实际上需要(n+1)*(m+1)个单元格。

以上述示例为例，共有 48 个字符比较和 96 次最小值检查。如果将该表存储在内存中（(6+1)*(8+1)假设每个单元格占用 4 个字节，且数字为 32 位），则需要 252 个字节！

我知道你肯定在翻白眼，觉得我纠结于252字节就这么大惊小怪。但问题在于，当你想比较更长的字符串时。比如说，比较两个1000个字符的字符串？那得占用……4兆字节。

对于一次查找来说，这听起来可能不算什么，但现在想象一下，如果使用垃圾回收机制的语言执行几十次或几百次这样的操作，分配的内存将会非常巨大！

我第一次了解到莱文斯坦距离时，就想把它应用到网页上，看看两个网页之间的差异有多大。如果把HTML中的每个字符都算进去（比如我写这篇文章时，这个网页在开发环境里就已经超过77000个字符了），或者仅仅计算每个文本节点（比如我写这篇文章时，这个网页就有6000多个字符），网页的大小就会非常大。如果按照上面的计算方法，6000个字符大约需要34兆字节，而77000个字符则需要惊人的5吉字节！

如果我们能将所需的单元格数量从 减少(n+1)*(m+1)到(MIN(n,m)+1)*2甚至 呢MIN(n,m)？在第二部分中，我将讨论如何让这个算法更快、更节省内存。

延伸阅读

• 维基百科上的莱文斯坦距离