《《编辑距离问题》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《编辑距离问题》PPT课件.ppt（12页珍藏版）》请在金锄头文库上搜索。
1、第三章动态规划编辑距离问题 问题描述 设A和B是2个字符串 要用最少的字符操作将字符串A转换为字符串B 这里所说的字符操作包括 1 删除一个字符 2 插入一个字符 3 将一个字符改为另一个字符 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离 记为 算法设计 对于给定的字符串A和字符串B 计算其编辑距离 数据输入 输入数据的第一行是一个正整数 表示一共有几组数据 每组数据两行 每行一个字符串 每个字符串长度不超过1000 结果输出 输出编辑距离 对于每组数据 请输出一个整数表示两个字符串的编辑距离 每个答案占一行 SampleInput SampleOutput 24da
2、vid3vivianabcaabbcc 分析与解答 设所给的两个字符串为A 1 m 和B 1 n 定义一个二维数组dp i j 表示状态 dp i j A 1 i B 1 j 表示字符串A 1 m 的子串A 1 i 变换到B 1 n 的子串B 1 j 的编辑距离 即子串A 1 i 至少要经过多少次操作 插入 删除 修改 可以变为B 1 j 单字符a b间的编辑距离定义为 例如 字符串A AGTAAGTAGGC转换为字符串B AGTCTGACGC 操作一 A串 AGTAAGT AGGCB串 AGT C TGACGC需要5步操作 2次删除 2次修改 1次删除 操作二 A串 AGTAAGTAGGCB
3、串 AGTCTG ACGC需要4次操作 3次修改 1次删除 我们计算的编辑距离是变换的最小步数 所以要取其中的最小值 考察从字符串A 1 i 到字符串B 1 j 的转换 有三种情况可以导致上面设计的状态发生转移 1 可以删除字符A i 需要1次操作 只将字符A i 从A串中删除 对序列B 1 j 没有任何影响 此时问题的最优子结构形式为将A 1 i 1 变为B 1 j 再加一步删除操作 可得dp i j dp i 1 j 1 2 可以在A i 后面插入一个字符ch ch B j 需要1次操作 在进行插入操作时 串A 1 i 无任何变化 在A串i 1位置上插入字符B j 问题的最优子结构形式为将
4、A 1 i 变为B 1 j 1 再加一步插入操作 可得dp i j dp i j 1 1 3 可以修改字符A i 使它变为B j 若A i B j 修改其实相当于用了0步 若A i B j 修改相当于用了1步 所以dp i j dp i 1 j 1 A i B j 0 1 最后的dp i j 就是选择上述3种状态转移中的最小值 综上所述 状态转移方程dp i j 可归结为如下情况 1 当两个字符相同 即A i B j 时 dp i j min dp i j 1 1 dp i 1 j 1 dp i 1 j 1 2 当两个字符不同 即A i B j 时 dp i j min dp i j 1 1
5、dp i 1 j 1 dp i 1 j 1 1 需要注意的是 要对dp 0 0 m dp 0 n 0 进行初始化 dp 0 i 就是说A串是一个空串 而B串是个长度为i的串 很显然A串变为B串就是插入i个字符 即dp 0 i i dp i 0 就是说A串是个长度为i的串 而B串是一个空串 很显然A串变为B串就是删除i个字符 即dp i 0 i 根据上述分析 编辑最短距离的算法可描述如下 intDP char s1 char s2 inti j m strlen s1 n strlen s2 tem 初始化for i 0 i n i dp 0 i i 从0个字符转换为i个字符 需要插入i次一重循
6、环时间复杂度为T n for i 0 i m i dp i 0 i 从i个字符转换为0个字符 需要删除i次一重循环时间复杂度为T m 用动态规划方法计算编辑距离for i 1 i m i for j 1 j n j if s1 i 1 s2 j 1 tem dp i 1 j 1 当两个字符相同时 替换操作代价为0 直接将dp i 1 j 1 转移过来elsetem dp i 1 j 1 1 当s1 i 1 s2 j 1 时 替换操作代价为1tem min tem dp i j 1 1 dp i j 1 1为在s1的i 1位置上插入字符s2 j tem min tem dp i 1 j 1 dp i 1 j 1为在s1的i位置上删除字符s1 i dp i j tem dp i j 取3种状态的最小值 returndp m n 返回dp m n 二重循环 时间复杂度为T n m 时间复杂度 总的时间复杂度为T n m n m O m n 最坏的时间复杂度为O n 2 运行结果示例 Theend thankyou
