尧图网页设计 )
上接机器学习系列动态规划(2)三、经典应用场景例 5.序列编辑距离计算两个字符串之间转换所需的最少操作次数。序列编辑距离又称Levenshtein距离也叫做Edit Distance, 是指两个字串之间由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符插入一个字符删除一个字符。同时也可以成为字符串的相似度问题将一个字符串转换成另外一个字符串的代价转换的方法可能不唯一转换的代价越高则说明两个字符串的相似度越低。这个概念由俄罗斯科学家弗拉基米尔·莱文斯坦(Vladimir Levenshtein)在1965年提出通常用动态规划求解时间和空间复杂度都是O(m×n)其中m、n是两个序列的长度。比如有两个字符串“SNOWY”和“SUNNY”下面给出两种将“SNOWY”转换成“SUNNY”的方法1 第一种S - N O W YS U N N - Y插入U, 替换O为N, 删除W, 共3次操作。2第二种- S N O W - YS U N - - N Y插入S, 替换S为U, 删除O, 删除W插入N, 共5次操作。这说明将一个字符串经由插入、删除或替换等操作转换成另外一个字符串的方法不止一种所需要做的编辑次数也不相同如果有某种方法能够用最小的操作次数完成转换这种方法的编辑次数就是我们要求的编辑距离。很显然这是个求最优解的问题。 那么能否给出一个算法求解任意两个字符串之间的编辑距离序列编辑距离显然是一个多阶段决策类型的最优解问题对一个字符串做最小的修改变换到另一个字符串需要在处理过程中的每个阶段都选择修改最小的方式但是该问题中每个阶段之间都不是孤立的受到前面已经确定的决策和后面可选的决策共同影响无法通过对每一次决策的最优决策简单堆叠出最后的最优结果因此可以优先考虑动态规划法。解 假设有一待编辑的字符串S有n个字符要修改为另一个有m个字符的目标字符串T。其中S中的字符从左到右分别是, T的字符分别是。1 阶段划分 这里以对字符串S进行一次编辑操作作为一个阶段用符号表示S中的第i个字符与T中的第j个字符进行比较操作。 考虑从S与T的最后一个字符即S(n)和T(m)开始进行编辑则操作顺序可表示为。2状态变量: 由于每次操作都会改变S与T中剩余待匹配字符的范围因而状态变量定义为当前S与T中待匹配的第i个字符和第j个字符 记为。3决策变量这里决策是对待编辑的字符S(j)进行的编辑操作包括不变、插入、删除和替换。4状态转移这里状态转移的方向是从右到左的具体如下如果和相同时 则当前字符无需编辑状态可直转向两个字符串的前一个即如果和不相同时则可采取如下3种操作a 在之后插入字符, 则S仍保持i个待编辑的字符而S已减少一个于是状态转移为b) 删除 则S减少一个待编辑的字符而T仍保持j个与S比较的字符于是状态转移为c) 用T(j)替换S(i), 此时状态可直转向两个字符串的前一个即。5指标函数: 表示将S的前i个字符更改为T的前j个字符所需要的最小编辑次数。由于和相同时无需编辑而和不相同时需要进行一次编辑操作因此容易得到指标函数的递推式边界条件为: i, 即两个字符串都是空的无需操作ii), 即S是空的而T为非空 ,要逐个向S插入j个字符; iii), 即S是非空而T为空 , 要逐个i个字符。最终长度是n的字符串 S要更改为长度是m的字符串T最小编辑次数为。为便于在MATLAB下编写算法这里用一个的矩阵dp来记录各个阶段的指标函数这里约定于是递推式用矩阵dp表示为MATLAB下的算法实现如下function main() %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %用动态规划求解序列编辑问题 %序列编辑距离计算两个字符串之间转换所需的最少操作次数。 %2026.9.25 MiaoZhh %EditDistance.m %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Edit Distance clear all clc % tSNOWY; % sSUNNY; % tpack; % sbag; % thelo; % shello; %两个字符串 torse; shorse; dedit_distance(s,t); disp([The Levenshtein distance of two two strings is ,num2str(d)]) end function dedit_distance(s,t) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %计算两个字符串的Levenshtein距离 %输入 % s 是要编辑的字符串 % t 是目标字符串 %输出 % d 是s与t之间的Levenshtein距离 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %字符串长度 nlength(s); mlength(t); dpzeros(n1,m1); %边界条件 for i1:n dp(i1,1)i; end for j1:m dp(1,j1)j; end %指标函数递推 for i1:n for j1:m if s(i)t(j) dp(i1,j1)dp(i,j); else dp(i1,j1)1min([dp(i1,j),dp(i,j1),dp(i,j)]); end end end %最小编辑次数 ddp(n1,m1); end序列编辑问题应用场景拼写检查与纠正计算用户输入单词与字典中单词的距离推荐最相似的词。生物信息学DNA 序列比对衡量两个基因序列的相似度。自然语言处理机器翻译评估、语音识别结果校正等。通过这种建模方式我们将一个看似复杂的字符串转换问题转化为了标准的网格路径最短问题利用动态规划的高效性解决了指数级复杂度的暴力搜索难题。 机器学习系列：动态规划 (3)
上接机器学习系列动态规划(2)三、经典应用场景例 5.序列编辑距离计算两个字符串之间转换所需的最少操作次数。序列编辑距离又称Levenshtein距离也叫做Edit Distance, 是指两个字串之间由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符插入一个字符删除一个字符。同时也可以成为字符串的相似度问题将一个字符串转换成另外一个字符串的代价转换的方法可能不唯一转换的代价越高则说明两个字符串的相似度越低。这个概念由俄罗斯科学家弗拉基米尔·莱文斯坦(Vladimir Levenshtein)在1965年提出通常用动态规划求解时间和空间复杂度都是O(m×n)其中m、n是两个序列的长度。比如有两个字符串“SNOWY”和“SUNNY”下面给出两种将“SNOWY”转换成“SUNNY”的方法1 第一种S - N O W YS U N N - Y插入U, 替换O为N, 删除W, 共3次操作。2第二种- S N O W - YS U N - - N Y插入S, 替换S为U, 删除O, 删除W插入N, 共5次操作。这说明将一个字符串经由插入、删除或替换等操作转换成另外一个字符串的方法不止一种所需要做的编辑次数也不相同如果有某种方法能够用最小的操作次数完成转换这种方法的编辑次数就是我们要求的编辑距离。很显然这是个求最优解的问题。 那么能否给出一个算法求解任意两个字符串之间的编辑距离序列编辑距离显然是一个多阶段决策类型的最优解问题对一个字符串做最小的修改变换到另一个字符串需要在处理过程中的每个阶段都选择修改最小的方式但是该问题中每个阶段之间都不是孤立的受到前面已经确定的决策和后面可选的决策共同影响无法通过对每一次决策的最优决策简单堆叠出最后的最优结果因此可以优先考虑动态规划法。解 假设有一待编辑的字符串S有n个字符要修改为另一个有m个字符的目标字符串T。其中S中的字符从左到右分别是, T的字符分别是。1 阶段划分 这里以对字符串S进行一次编辑操作作为一个阶段用符号表示S中的第i个字符与T中的第j个字符进行比较操作。 考虑从S与T的最后一个字符即S(n)和T(m)开始进行编辑则操作顺序可表示为。2状态变量: 由于每次操作都会改变S与T中剩余待匹配字符的范围因而状态变量定义为当前S与T中待匹配的第i个字符和第j个字符 记为。3决策变量这里决策是对待编辑的字符S(j)进行的编辑操作包括不变、插入、删除和替换。4状态转移这里状态转移的方向是从右到左的具体如下如果和相同时 则当前字符无需编辑状态可直转向两个字符串的前一个即如果和不相同时则可采取如下3种操作a 在之后插入字符, 则S仍保持i个待编辑的字符而S已减少一个于是状态转移为b) 删除 则S减少一个待编辑的字符而T仍保持j个与S比较的字符于是状态转移为c) 用T(j)替换S(i), 此时状态可直转向两个字符串的前一个即。5指标函数: 表示将S的前i个字符更改为T的前j个字符所需要的最小编辑次数。由于和相同时无需编辑而和不相同时需要进行一次编辑操作因此容易得到指标函数的递推式边界条件为: i, 即两个字符串都是空的无需操作ii), 即S是空的而T为非空 ,要逐个向S插入j个字符; iii), 即S是非空而T为空 , 要逐个i个字符。最终长度是n的字符串 S要更改为长度是m的字符串T最小编辑次数为。为便于在MATLAB下编写算法这里用一个的矩阵dp来记录各个阶段的指标函数这里约定于是递推式用矩阵dp表示为MATLAB下的算法实现如下function main() %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %用动态规划求解序列编辑问题 %序列编辑距离计算两个字符串之间转换所需的最少操作次数。 %2026.9.25 MiaoZhh %EditDistance.m %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Edit Distance clear all clc % tSNOWY; % sSUNNY; % tpack; % sbag; % thelo; % shello; %两个字符串 torse; shorse; dedit_distance(s,t); disp([The Levenshtein distance of two two strings is ,num2str(d)]) end function dedit_distance(s,t) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %计算两个字符串的Levenshtein距离 %输入 % s 是要编辑的字符串 % t 是目标字符串 %输出 % d 是s与t之间的Levenshtein距离 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %字符串长度 nlength(s); mlength(t); dpzeros(n1,m1); %边界条件 for i1:n dp(i1,1)i; end for j1:m dp(1,j1)j; end %指标函数递推 for i1:n for j1:m if s(i)t(j) dp(i1,j1)dp(i,j); else dp(i1,j1)1min([dp(i1,j),dp(i,j1),dp(i,j)]); end end end %最小编辑次数 ddp(n1,m1); end序列编辑问题应用场景拼写检查与纠正计算用户输入单词与字典中单词的距离推荐最相似的词。生物信息学DNA 序列比对衡量两个基因序列的相似度。自然语言处理机器翻译评估、语音识别结果校正等。通过这种建模方式我们将一个看似复杂的字符串转换问题转化为了标准的网格路径最短问题利用动态规划的高效性解决了指数级复杂度的暴力搜索难题。