使用Levenstein计算编辑距离



问题:
我编写了一个Levenstein字符串编辑程序,它对我来说似乎工作正常,但显然给出了错误的答案。我想我误解了编辑距离的计算方式。

比较
对于字符串超级反引力,下面是最后两行的比较

矿:

    a n t i g r a v i t  a  t  i  o  n  a  l
c 6 6 6 6 6 6 6 6 7 8 9  10 11 12 13 14 15 16
a 7 6 7 7 7 7 7 6 7 8 9  9  10 11 12 13 13 14

其他:

    a n t i g r a v i t  a  t  i  o  n  a  l
c 6 6 6 6 6 6 6 6 7 8 9  10 11 12 13 14 15 16
a 7 6 7 7 7 7 7 6 7 8 9  9  10 11 12 13 14 15

在我的计算中,你可以看到,因为反引力中的最后一个"a"与超级跑车的"a"匹配,所以我给它一个值13,因为左边的数字是13。因此,成本为0。

在其他计算中,在这种情况下,人们似乎仍在增加成本。正如你在另一个例子中看到的,他们在我放置13的地方放置了一个14,最终的编辑距离为15(而不是我的14(。

我是对的,其他人都错了(不太可能(,还是我错过了一步?

我在YouTube上看了几段视频后找到了自己的答案。

我的错误
我的说明是:"如果你比较的字母匹配,请将成本设置为0,并复制最小值(左、对角线、上图(。如果不匹配,请加1。"。

更正
因此,指示有点不准确。在字母匹配的情况下,无论左边的值和上面的值是多少,都应该始终免费复制对角线。

最新更新