已填格子
编辑距离
保留的字母

  • 正在填写
  • 被读取
  • 答案

更多关于编辑距离

编辑距离(莱文斯坦距离)

把 kitten 变成 sitting 需要几次单字母修改?三次:把 k 替换为 s,把 e 替换为 i,再加上一个 g。这个数就是编辑距离,拼写检查器靠它给建议排序,生物学家靠它比较基因。输入两个单词,看表格如何把它求出来。 按“播放”观看表格填充过程,或用“单步”和“后退”一步一步查看。拖动步骤滑块可跳到任意位置。输入两个单词:第一个沿表格左侧竖向排列,第二个沿顶部横向排列。每个单元格记录的是:把到该行为止的字母变成到该列为止的字母,最少需要几次编辑。最后从右下角的单元格回溯出编辑操作。“新示例”会换一对单词。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 跳到开头和结尾。

它是如何运作的

  1. 输入两个单词:第一个沿表格左侧竖向排列,第二个沿顶部横向排列。
  2. 按“播放”,或用“单步”和“后退”一步一步移动。拖动步骤滑块可跳到任意位置。
  3. 观察每个单元格如何从三个相邻单元格中取代价最小的一个,然后看编辑操作以橙色回溯出来。

表格如何工作

一个单元格记录的是:把第一个单词到该行为止的字母变成第二个单词到该列为止的字母,最少需要几次编辑。第一行统计插入次数,即从空开始构造第二个单词;第一列统计删除次数。如果单元格对应的两个字母相同,就复制左上方的单元格:无需编辑。否则,它等于三个相邻单元格中的最小值加一:左上方对应替换,上方对应删除,左方对应插入。

回溯编辑操作

右下角的单元格就是编辑距离。应用从这里出发,找出该单元格的值来自哪个相邻单元格,然后移到那里:保留或替换的字母沿对角线移动,删除的字母向上,插入的字母向左。从左上角开始读,这些步骤就是一份最短的编辑列表,显示在表格下方:普通字母表示保留,k→s 表示替换,−e 表示删除,+g 表示插入。

常见问题

什么是莱文斯坦距离?

这是这种编辑距离的另一个名字:把一个字符串变成另一个字符串所需的最少单字母插入、删除和替换次数。它以 1965 年描述这一概念的弗拉基米尔·莱文斯坦(Vladimir Levenshtein)命名。

kitten 和 sitting 之间的编辑距离是多少?

3:把 k 替换为 s,把 e 替换为 i,再在末尾插入 g。表格表明不存在更短的编辑列表。

编辑距离算法有多快?

对于长度为 m 和 n 的单词,表格有 (m + 1)·(n + 1) 个单元格,每个单元格一步填好,所以需要 O(m·n) 时间。如果只需要距离,保留表格的两行就够了。

还有哪些编辑距离?

Damerau–Levenshtein 距离还把交换两个相邻字母算作一次编辑,适合处理打字错误。汉明距离(Hamming 距离)只允许替换,用于等长的字符串。LCS 距离只允许插入和删除。

会向任何地方发送数据吗?

不会。所有计算都在你的浏览器中完成,你最近的设置保存在此浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器