Breadcrumb
基于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）。
垃圾字符处理机制
SequenceMatcher引入了"垃圾字符"概念，这是其相比其他算法的重要创新：
- 用户定义垃圾：通过isjunk函数，用户可以指定哪些字符应被视为垃圾（如空格、制表符）
- 自动垃圾识别：当序列长度≥200时，出现频率超过1%的字符会被自动标记为垃圾
- 智能匹配策略：算法首先忽略垃圾字符找到核心匹配，然后在两端扩展匹配垃圾字符 这种设计使得算法在处理包含大量重复元素（如代码中的空行、HTML中的标签）的文本时表现出色。
Ratio计算
核心计算ratio的方法：
$$ ratio = 2\cdot \frac{matches}{length} $$
其中：
- match：所有匹配块的字符总数
- length：两个序列的总长度(len(a)+len(b))
代码提供了三种计算ratio的方式：
- ratio：通过get_match_blocks函数得到，经过了完整算法的ratio
- quick_ratio：不考虑顺序，只把两个sequencial当成两个集合取交集
- real_quick_ratio：只是用长度做数学计算，完全不看序列内容
比较：
- 精确性：ratio > quick_ratio > real_quick_ratio（ratio最精确，real_quick_ratio最粗糙）
- 速度： ratio < quick_ratio < real_quick_ratio（ratio最慢，real_quick_ratio最快）
- 值的大小关系：real_quick_ratio ≥ quick_ratio ≥ ratio（都是上界或精确值，满足单调性）