algorithm - Levenshtein 的编辑距离算法如何工作？

Question

我正在浏览 Levenshtein distance algorithm其中我掌握了它的一些初始步骤，但在后续步骤开始计算“成本”时，我很难理解它。我不明白计算成本的目的以及它如何帮助算法实现其目标。请帮助我理解这个算法。

Answer 1

有许多不同的方法可以通过插入/删除/替换来编辑第一个字符串以获得第二个字符串(实际上是无限多个)。每个都有特定的基本编辑操作计数。

Levenshtein 距离定义为所需的最少操作次数，即最短序列的长度。这个数字是明确定义的，即使它可以通过几个不同的编辑序列来实现。

这与欧几里德距离的情况非常相似:您可以按照各种轨迹从一个点到另一个点，但只有直线达到最小路径长度。

更新:

需要补充的是，为不同的操作分配不同的成本可以提供更大的灵 active ，并允许偏袒一个或另一个。更重要的是，您可以为每个字符分配单独的权重，例如，将“O”换成“0”被认为比插入空格更“严重”。

成本最小化原则仍然存在。