[Ash]
in
基于Gestalt Pattern Matching的SequenceMatcher代码详解
SequenceMatcher是difflib中的一个类，其中包含几个函数：
初始化函数：初始化函数主要是传入需要做比较的两个sequence，并且利用__chain_b函数对sequence b（通过set_seq2传入）做了索引处理，因此想要1 to many sequence做对比的话，保持b不变，只用set_seq1去修改sequence a效率比较高，因为不用多次做索引。
init set_seqs set_seq1 set_seq2 __chain_b 主要计算函数：
find_longest_match：在指定范围内找到最长的连续匹配子序列 get_matching_blocks：返回所有匹配块的列表 ratio：计算序列的相似度 (0到1之间) quick_ratio：快速计算相似度的上界估计 real_quick_ratio：最快速计算相似度的上界估计 其他无关紧要的：
get_opcodes：返回将序列 a 转换为序列 b 的操作列表 get_grouped_opcodes：将操作码分组，每组包含最多 n 行上下文 原理 核心算法：Gestalt Pattern Matching SequenceMatcher基于Gestalt Pattern Matching算法，这是Ratcliff和Obershelp在1980年代提出的一种模式匹配方法。该算法的核心思想是：
递归查找最长公共子序列 (LCS) 分而治之：在找到LCS后，递归处理LCS左右两侧的子序列 累积所有匹配块 但是SequenceMatcher是其变体，一些算法有所改变，比如使用队列+循环模拟递归，避免长文本的深度递归问题。
def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None): a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__ if ahi is None: ahi = len(a) if bhi is None: bhi = len(b) besti, bestj, bestsize = alo, blo, 0 # !!!!!核心：动态规划!!!!! j2len = {} # j2len[j] = 以序列b的位置j结尾的最长匹配子序列长度 nothing = [] for i in range(alo, ahi): j2lenget = j2len.get # 优化技巧，后面直接使用j2lenget，避免重复引用 newj2len = {} for j in b2j.get(a[i], nothing): # 在 b 里找依次找 a # a[i] matches b[j] if j < blo: # b是有上下界的，可能从中间开始匹配，通过定义blo continue if j >= bhi: break k = newj2len[j] = j2lenget(j-1, 0) + 1 # 动态规划思想，直接取以b[j-1]结尾的最长匹配子序列长度，加上1，与 j2len = newj2len 相互合作 if k > bestsize: besti, bestj, bestsize = i-k+1, j-k+1, k j2len = newj2len # 这句话是重点，j2len并不是往后append，而是直接替换，也就是说只会保留当前阶段的状态，所以每一次通过j2lenget(j-1, 0)得到的都是上一个循环中的状态，保证了字符串的连续性 # !!!!!!!!!!!!!!!!!!!! # 以下是用于扩展垃圾元素（junk）和流行元素（popular，出现频率>1%），这两类都不包含在b2j中，所以不能被以上的逻辑检测到 while besti > alo and bestj > blo and \ not isbjunk(b[bestj-1]) and \ a[besti-1] == b[bestj-1]: besti, bestj, bestsize = besti-1, bestj-1, bestsize+1 while besti+bestsize < ahi and bestj+bestsize < bhi and \ not isbjunk(b[bestj+bestsize]) and \ a[besti+bestsize] == b[bestj+bestsize]: bestsize += 1 while besti > alo and bestj > blo and \ isbjunk(b[bestj-1]) and \ a[besti-1] == b[bestj-1]: besti, bestj, bestsize = besti-1, bestj-1, bestsize+1 while besti+bestsize < ahi and bestj+bestsize < bhi and \ isbjunk(b[bestj+bestsize]) and \ a[besti+bestsize] == b[bestj+bestsize]: bestsize = bestsize + 1 return Match(besti, bestj, bestsize) 从核心代码中可以看出该算法强调LCS的连续性，也就是说比如对于a=“abca”, b=“acba”，得到的LCS是1，而不是3（aca）。
