第四算法系列: 字符串相似度

第四算法系列: 字符串相似度

我们将两个字符串的相似性定义为: 将一个字符串转换为另一个字符串的成本（转换方法可能不是唯一的），转换成本越高，两个字符串的相似性越低. 例如，两个字符串: “ SNOWY”和“ SUNNY”，这是将“ SNOWY”转换为“ SUNNY”的两种方法:

转化1:

S-N O W Y

S N N-Y

成本= 3（插入U，替换O，删除W）

转化2:

-S N O W-Y

U N--N Y

成本= 5（插入S，替换S字符串相似度匹配，删除O，删除W，插入N）

我们可以将这种相似性理解为: 通过诸如“插入，删除和替换”之类的编辑操作将一个字符串（源）转换为另一个字符串（目标）所需的最小编辑次数. 两个字符串之间的编辑距离. 您能否给出一种算法来解决任意两个字符串之间的编辑距离？

从标题中给出的示例中，我们可以看到，有多种方法可以通过插入，删除或替换等操作将一个字符串转换为另一个字符串，并且所需的编辑次数也有所不同. 如果有方法只需最少的修改即可完成转换. 此方法中的编辑次数是所需的编辑距离. 显然，这是找到最佳解决方案的问题.

当提到最优解问题时，可以首先考虑贪婪方法，但是这个问题显然是一个多阶段决策类型的最优解问题. 将源字符串的最小修改量转换为目标字符串，需要对其进行处理. 过程中的每个阶段都选择修改最少的方式，但是此问题中的每个阶段都不是孤立的. 它受之前已经确定的决策以及后来的可选决策的影响，并且无法通过最优决策. 仅将最终的最优结果叠加起来即可，因此排除了贪婪方法.

对于多阶段决策，应优先考虑动态规划（DP）. 动态规划法是解决多阶段决策优化问题的常用思维方法[1]，也是所有问题求解方法中最抽象的方法. 使用动态编程解决问题有两个关键点. 一种是定义子问题的最佳子结构[注1]，另一种是确定最佳子问题的堆叠方法. 定义最佳子结构是分解子问题字符串相似度匹配，该子问题可以是递归的也可以是递归的. 基本原理是将问题分解为M个子问题，并同时确定每个子问题与其他N个问题（N小于M）的最优解. 子问题最优解的堆叠方法是指最优决策序列与其子序列之间的递归关系，包括子问题最优解的递归关系和边界值. 对于一个问题，如果可以找到最优子结构的定义（包括子问题之间的关系）和子问题的最优解的堆叠方法，并且每个子问题的最优解都不满足后注[注2]，那么该问题可以通过动态编程解决.

以这个问题为例，假设源字符串有n个字符，目标字符串有m个字符. 如果将问题定义为将源的1-n个字符转换为目标的1-m个字符的解决方案，则可以将最小问题数（最小编辑距离）定义为最小问题数. 将源的1-i字符转换为目标的1-j字符所需的编辑，这是最佳的子结构. 我们使用d [i，j]表示源[1..i]与目标[1..j]之间的最小编辑距离，然后计算d [i，j]的递归关系，如下所示:

如果源[i]等于目标[j]，则:

d [i，j] = d [i，j] + 0（递归公式1）

如果源[i]不等于目标[j]，则根据插入，删除和替换这三种策略，计算使用这三种策略获得的编辑距离，然后取最小的一种:

d [i，j] = min（d [i，j-1] + 1，d [i-1，j] + 1，d [i-1，j-1] + 1）（递归公式2）

d [i，j-1] +1表示在插入源[​​i]后计算最小编辑距离

d [i-1，j] +1表示删除源[i]后计算最小编辑距离

d [i-1，j-1] +1表示在将源[i]替换为目标[i]后计算最小编辑距离

d [i，j]的边界值是当目标是空字符串（m = 0）或源是空字符串（n = 0）时计算出的编辑距离:

m = 0，对于所有i: d [i，0] = i

n = 0，对于所有j: d [0，j] = j

根据最优解的最优子结构，递归关系和边界值，很容易编写一种使用动态规划求解最小编辑距离的算法. 下面的代码是计算两个字符串中最小的算法的编辑距离的实现:

除了贪婪法和动态规划法外，穷举法也是求解最优解的常用方法. 详尽的方法比动态编程的方法更容易理解. 穷举法的原理是搜索问题域的整个解空间，并通过比较所有可能的解来选择最优解. 详尽的方法的目的实际上是解决问题的所有法律解决方案. 最佳解决方案可以理解为只是搜索过程的副产品. 根据主题，穷举方法的实现也有所不同. 如果问题的解决方案空间是线性结构，则可以使用循环方法；如果问题的解决方案空间是树结构，则可以使用递归方法. 这个问题的解决方案空间显然不是线性结构，因此请考虑使用递归方法穷举所有解决方案. 递归算法需要解决两个问题，一个是如何将问题递归分解为子问题，另一个是如何确定递归终止条件.

对于本文中的问题，可以按如下方式递归分解子问题: 位置i表示源字符串和目标字符串中的公共字符位置. 对于每个i位置，从i位置开始计算子字符串的编辑距离. 这是比较源[i]和目标[i]的值. 如果它们相等，则表示此位置所需的编辑数为0. 从位置i开始的子字符串的编辑距离等于从位置i开始的源字符串和目标字符串+ 1子字符串的编辑距离. 如果它们不相等，则尝试在源字符串的位置i处插入，删除和替换字符，以计算新子字符串的编辑距离，然后加1以编辑从位置i开始的子字符串的距离. 通过插入，删除和替换来计算新子字符串的开始位置. 您需要单独调整. 如果在i位置插入一个字符，则源字符串的i位置不会更改，目标字符串的i位置将移动到i +1. 该位置继续. 如果在i位置删除了字符，则源字符串的i位置将移至i + 1位置，而目标字符串的i位置将保持不变. 如果在i位置替换了字符，则源字符串和目标字符串的i位置都将移动到i +1位置.

随着子问题的递归分解，还需要确定递归计算的终止条件. 从上面的递归子问题的定义可以看出，此问题的终止条件非常简单，当源字符串和目标字符串之一为空时，可以终止递归. 达到递归终止条件时，编辑距离的值是源字符串和目标字符串中不为空的其余子字符串的长度. 这更容易理解. 如果source的最后一个子字符串不为空，则表示它需要这些字符. 可以删除这些字符以使其与目标相同. 如果目标的最后一个子字符串不为空，则意味着这些字符需要与目标中的字符插入源中，因此最终的编辑距离是剩余子字符串的长度.

根据上述对递归子问题的分解方法和递归终止条件的分析，很容易编写使用递归方法解决此问题的算法实现. 递归算法通常效率不高，但与人类解决问题的思路是一致的. 该代码通常简洁明了，易于理解. 本文给出的算法实现仅使用9行代码:

14int EditDistance（const std ::字符串和源，const std ::字符串和目标）

15 {

16 if（source.empty（）|| target.empty（））

17 return std :: abs（source.length（）-target.length（））;

18

19 if（源[0] ==目标[0]）

20 return EditDistance（source.substr（1），target.substr（1））;

21

22 int edIns = EditDistance（source，target.substr（1））+ 1; //源插入字符

23 int edDel = EditDistance（source.substr（1），target）+ 1; //源删除字符

24 int edRep = EditDistance（source.substr（1），target.substr（1））+ 1; //源替换字符

25

26 return std :: min（std :: min（edIns，edDel），edRep）;

27}

就时间复杂度而言，动态编程方法的时间复杂度为O（n2），在最佳情况下，即每次执行时，穷举算法的时间复杂度为O（n）. [0] ==目标[0]）在分支的情况下，最坏的情况当然是O（3n）. 这种时间复杂度是一种指数算法，基本上是一种不可用的算法. 仅具有理论价值，这种时间复杂度的算法不会在实际工程中应用.

就空间复杂度而言，动态编程方法的空间复杂度为O（mn），但是可以在很大程度上优化该空间复杂度，并且优化程度根据算法而有所不同. 以本文中的算法为例，从（递归公式2）可以看出，d [i，j]的结果只需要知道i，i-1和j，j-1位置的结果递归计算出来后，其他位置的信息可以在计算完成后释放，并且不需要从头到尾占用mxn空间. 类似的优化只是有关数据组织的一些技巧，因此在本文中我将不做详细介绍. 有兴趣的读者可以自行修改EditDistance（）函数.

评论:

【1】最优子结构: 对于多阶段决策问题，如果每个阶段的最优决策序列的子序列也都是最优的，且决策序列没有“后效”，则可以进行决策. 被理解为最佳子结构.

【2】无后效: 动态规划方法的最优解通常是由一系列最优决策组成的决策序列. 最优子结构是这些最优决策序列的子序列. 如果该序列再次做出最优决策，它将产生一个新的最优决策（子）序列. 如果一个决策仅受当前最优决策子序列的影响，那么它将不受当前决策可能产生的新的最优决策子序列的影响. ，您可以了解到，这种最佳决策没有后效.

参考文献:

[1]. 算法艺术与信息学比赛. 刘如家，黄亮. 清华大学出版社. 2003

[2].

[3].

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-206449-1.html