美文网首页
最小编辑距离

最小编辑距离

作者: 热爱生活的大川 | 来源:发表于2020-04-22 17:21 被阅读0次

1.定义

假设只有三种编辑方式：插入，删除，替换。每种编辑方式对应一次操作。按规定的编辑方式，将原始字符串变换到目标字符串所需的最少操作次数，被称为最小编辑距离。
Levenshtein距离中定义替换对应两次操作。

2.推导

设源字符串为A，长度m，目标字符串为B，长度n。

  1. 是否存在简单情况
    很明显，两字符串长度较短时情况会比较简单。
    如，m=0时，插入n次；n=0时，删除n次；m=n=1且A和B不同时，替换1次。

  2. 简单情况到复杂情况的变量是什么
    是两个字符串的长度。因此我们设最小编辑距离为D(m,n)。

  3. 是否存在简单情况到复杂情况的递推关系
    由1有\begin{cases}D(i,0)=i,i \in (0,m) \\ D(0,j)=j,j \in (0,n) \end{cases}
    从D(i,j)向前回溯，有三条路径，对应三种编辑方式，
    D(i,j) = min \begin{cases} D(i,j-1)+ins(B[j]) \\ D(i-1,j)+del(A[i]) \\ D(i-1,j-1)+sub(A[i],B[j]) \end{cases}这里，ins(x)=1，del(x)=1，sub(x,y) = \begin{cases} 1,x \neq y \\ 0,x = y \end{cases}。

  • 每一步取最短路径，最后一定是最短路径吗？对于每次都归结于一点的树形结构，这是必然的。

相关文章

  • 最小编辑距离

    编辑距离，又称为Levenshtein距离，由俄罗斯的数学家Vladimir Levenshtein在1965年提...

  • 最小编辑距离

    题目 给定一个源串S和目标串T，能够对源串进行如下操作：1.在给定位置上插入一个字符2.替换任意字符3.删除任意字...

  • 最小编辑距离

    定义：两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包...

  • 最小编辑距离

    1.定义 假设只有三种编辑方式：插入，删除，替换。每种编辑方式对应一次操作。按规定的编辑方式，将原始字符串变换到目...

  • 最小编辑距离

    求两个字符串最小编辑距离，word1->word2转换 word1的前i个字符串要想转换为word2的前j个字符串...

  • 最小编辑距离

    最小编辑距离 编辑距离有两种: Levenshtein距离: 允许插入,删除和替换一个字符, 最常见 Damera...

  • NLP-2012斯坦福课程第3课 基本问题

    一、最小编辑距离编辑距离（Minimum Edit Distance，MED），又称Levenshtein距离，是...

  • 72、最小编辑距离

    我太小看面试难度了，本来以为这样的题目不会遇到，但是小米面试的时候遇到了，好在没做出来也过了，所以一定要搞懂啊。 ...

  • 最小编辑距离_Python

    最小编辑距离或莱文斯坦距离（Levenshtein），指由字符串A转化为字符串B的最小编辑次数。允许的编辑操作有：...

  • 最小编辑距离算法

    https://github.com/youngwind/blog/issues/106

网友评论

      本文标题：最小编辑距离

      本文链接：https://www.haomeiwen.com/subject/osgiihtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|最小编辑距离|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！