首页 / 算法 / 算法分析与设计(二)
算法分析与设计(二)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法分析与设计(二),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1628字,纯文字阅读大概需要3分钟。
内容图文
动态规划
-
编辑距离(Levenshtein距离)
比较两个字符串时,若字符串x长度为m,字符串y长度为n。
假设这两个字符串之间的编辑距离为E(m,n)。
要通过动态规划的方式解决它,那就需要将这样一个问题划分为子问题E(i,j),子问题表示串x中前i个字符与串y中前j个字符之间的编辑距离。
当计算子串的编辑距离时,子串的最右边一列对齐时有以下三种情形:
_x[i]x[i]y[j]_y[j]
根据以上的对齐方式,可以得到E(i,j)的递推公式:
E(i,j)=min{1+E(i?1,j), 1+E(i,j?1), diff(i,j)+E(i?1,j?1)};If x[i]==y[i] then diff(i,j)=0, otherwise diff(i,j)=1;E(0,j)=j; E(i,0)=i
根据以上递推公式,便能计算并填写下列表格,最终的E(m,n)即为最小编辑距离
E(i,j) | x[1] | x[2] | … | x[i] | … | x[m] | |
---|---|---|---|---|---|---|---|
0 | 1 | 2 | … | i | … | m | |
y[1] | 1 | ||||||
y[2] | 2 | ||||||
… | … | ||||||
y[j] | j | ||||||
… | … | ||||||
y[n] | n |
计算编辑距离的时间复杂度为
O(m?n)
计算出编辑距离后,要想求出字符串的编辑位置,则可以从E(m,n)开始与左边、上边或左上角移动一格的区域中找出最小的一个编辑距离即Edmin?=min{E(m?1,n), E(m,n?1), E(m?1,n?1)},将其与E(m,n)比较,若两者相等则说明x[m]与y[n]是对齐且相等的;否则认为这一位置是编辑点。同时继续以Edmin?对应的位置开始继续以上的步骤。
内容总结
以上是互联网集市为您收集整理的算法分析与设计(二)全部内容,希望文章能够帮你解决算法分析与设计(二)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。