编辑问题

发布于 2024-08-16 20:48:43 字数 301 浏览 13 评论 0原文

在 Levenshtein Distance 算法中，这条线的作用是什么？：

    d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);

虽然它得到了所有距离中的最小值在这些值中，为什么成本添加到末尾，为什么我们在每个数组索引器（前两个参数）的末尾有 + 1？

原文

In the Levenshtein Distance algorithm, what does this line do?:

    d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);

Although it gets the minimum of all of those values, why is cost added to the end, and why do we have + 1 at the end of each array indexer (first two parameters)?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

丢了幸福的猪 2024-08-23 20:48:47

这是一个公式：

$alt text$

m(a,b) = if a==b then 0 else 1

带“min”的行是递归公式本身，其他情况是递归导致的非递归情况。

您的线路正在使用数组中的“缓存”结果。尝试将其视为：

 d(i, j) = Minimum (d(i-1, j)+1, d(i, j-1)+1, d(i-1, j-1) + cost);

cost 为 m(a,b)，如果 a==b 则为零，并且在其他情况

Here is a formula:

$alt text$

m(a,b) = if a==b then 0 else 1

The line with "min" is the recursive formula itself, the others are non-recursive cases to which the recursion leads.

Your line is using "caching" the results in array. Try to look at it as at:

 d(i, j) = Minimum (d(i-1, j)+1, d(i, j-1)+1, d(i-1, j-1) + cost);

cost is m(a,b), and it's zero if a==b and one in the other case

回复收藏 0 原文

情深如许 2024-08-23 20:48:47

摘自文章：

                (
                  d[i-1, j] + 1,  // deletion
                  d[i, j-1] + 1,  // insertion
                  d[i-1, j-1] + 1 // substitution
                )

该算法的目的是找到将一个字符串（或列表）转换为另一个字符串的最便宜的路径。任何给定操作的“成本”都在您引用的行中考虑。在你的系统中，“删除”被认为是成本 1，“插入”也是 1，而“替换”则被认为是可变成本。

From the article:

                (
                  d[i-1, j] + 1,  // deletion
                  d[i, j-1] + 1,  // insertion
                  d[i-1, j-1] + 1 // substitution
                )

The algorithm's purpose is to find the cheapest path to convert one string (or list) to another string. The "cost" for any given operation is considered in the line you've referenced. In yours, "deletes" are considered to be a cost of 1, "inserts" also 1, and "substitution" at a variable cost.

回复收藏 0 原文