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

Question

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

Answer 1

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

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

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

更新:

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

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