目录
- 一、什么是LCS
- 子序列
- 最长公共子序列
- 二、LCS的应用场景
- 三、LCS的查找方法
- 1. 动态规划法计算LCS的长度和两字符串的相似度
- 2. 回溯算法查找LCS
- 四、代码实现
一、什么是LCS
子序列
子序列:一个序列S任意删除若干个字符得到的新序列T，则T叫做S的子序列
最长公共子序列
最长公共子序列（Longest Common Subsequence）：两个序列X和Y的公共子序列中，长度最长的那个，定义为X和Y的最长公共子序列
例如：
字符串12455与245576的最长公共子序列为2455
字符串acdfg与adfc的最长公共子序列为adf
二、LCS的应用场景
文本匹配：即字面匹配，是自然语言处理中一个重要的基础问题，可以应用于大量的NLP任务中，如信息检索、问答系统、复述问题、对话系统、机器翻译等，这些NLP任务在很大程度上可以抽象为文本匹配问题。
局限性
- 词义局限：“的士”和“出租车”虽然字面上不相似，但实际为同一种交通工具；“苹果”在不同的语境下表示不同的东西，或为水果或为公司
- 结构局限：“机器学习”和“学习机器”虽然词汇完全重合，但表达的意思不同。
- 知识局限：“秦始皇打Dota”，这句话虽从词法和句法上看均没问题，但结合知识看这句话是不对的。
语义匹配：结合语义、语境和知识进行的文本匹配
比如 ‘苹果’ 这个词语，要结合上下文的语境才能判断指的是水果还是苹果品牌
多模态：
- 模态：模态指交流的渠道和媒介，包括语言、技术、图像、颜色、音乐等符号系统。
- 多模态：指的便是除了文本之外，还带有图像、图表等符合话语，或者说任何由一种以上符合编码实现意义的文本
- 多模态话语分析 ：就是分析单一感官的多符号语篇或多感官的多符号语篇。
三、LCS的查找方法
1. 动态规划法计算LCS的长度和两字符串的相似度
已知两个字符串X=‘ABCBDAB’,Y=‘BDCABA’，长度分别为i=7，j=6
构建二维数组C[i,j]，以0填充
将X的每个字符分别和Y的每个字符比较，
1.如果X和Y其中有任意一个字符串长度为0，则C[i,j]=0
2.如果X[i]=Y[j]，则C[i,j]取矩阵左上角数值+1，即C[i-1,j-1]+1
3.如果X[i]≠Y[j]，则C[i,j]取矩阵上和左数值中较大的一个，即max(C[i-1,j],C[i,j-1])
公式：
矩阵按照公式填满后如下图所示：
序列X 和Y 的最长公共子序列的长度为 C[i,j]=4
X和Y相似度=最长公共子序列的长度*2 / X和Y的长度之和，即
sim=len(lcs)*2 / len(X)+len(Y)
本例相似度 sim=4*2 / 13 = 0.615
2. 回溯算法查找LCS
在1 中的算法查到了LCS的长度，下边我们讲把LCS查找出来
从上文的中我们发现，真正使得LCS计算长度增加的有效数字，只有下边这种情况
2.如果X[i]=Y[j]，则C[i,j]取矩阵左上角数值+1，即C[i-1,j-1]+1
在矩阵中标识出这些数字
注：C[i-1,j-1]+1=max(C[i-1,j],C[i,j-1])，即 左上角数字+1=上、左数字较大值的情况，不计入有效
从C[i,j] 右下角出发，向左上角 i，j 递减的方向，每个梯度数字选择一个，找出所有满足条件的路径
找到每条路径路过的有效数字正上方Y中对应的字符，则找到所有的LCS
本例的结果为：BCBA,BCAB,BDAB
四、代码实现
# coding=utf-8
class LCS():def input(self,x, y):#读入待匹配的两个字符串if type(x) != str or type(y) != str:print ('input error')return Noneself.x = xself.y = ydef Compute_LCS(self):xlength = len(self.x)ylength = len(self.y)self.direction_list = [None] * xlength #这个二维列表存着回溯方向for i in range(xlength):self.direction_list[i] = [None] * ylengthself.lcslength_list = [None] * (xlength + 1)#这个二维列表存着当前最长公共子序列长度for j in range(xlength + 1):self.lcslength_list[j] = [None] * (ylength + 1)for i in range(0, xlength + 1):self.lcslength_list[i][0] = 0for j in range(0, ylength + 1):self.lcslength_list[0][j] = 0#下面是进行回溯方向和长度表的赋值for i in range(1, xlength + 1):for j in range(1, ylength + 1):if self.x[i - 1] == self.y[j - 1]:self.lcslength_list[i][j] = self.lcslength_list[i - 1][j - 1] + 1self.direction_list[i - 1][j - 1] = 0 # 左上elif self.lcslength_list[i - 1][j] > self.lcslength_list[i][j - 1]:self.lcslength_list[i][j] = self.lcslength_list[i - 1][j]self.direction_list[i - 1][j - 1] = 1 # 上elif self.lcslength_list[i - 1][j] < self.lcslength_list[i][j - 1]:self.lcslength_list[i][j] = self.lcslength_list[i][j - 1]self.direction_list[i - 1][j - 1] = -1 # 左else:self.lcslength_list[i][j] = self.lcslength_list[i - 1][j]self.direction_list[i - 1][j - 1] = 2 # 左或上self.lcslength=self.lcslength_list[-1][-1]#遍历矩阵for i in range(len(self.lcslength_list)): for j in range(len(self.lcslength_list[i])):print(self.lcslength_list[i][j], end='\t')print('')sum_len=xlength + ylengthsimilarity=float(float(self.lcslength * 2) / float(sum_len))print('max_len:',self.lcslength,',sum_len:',sum_len,'similarity:',similarity)return self.direction_list, self.lcslength_listdef printLCS(self, curlen, i, j, s):if i == 0 or j == 0:return Noneif self.direction_list[i - 1][j - 1] == 0:if curlen == self.lcslength:s += self.x[i - 1]for i in range(len(s)-1,-1,-1):print (s[i], end=''),print('')elif curlen < self.lcslength:s += self.x[i-1]self.printLCS(curlen + 1, i - 1, j - 1, s)elif self.direction_list[i - 1][j - 1] == 1:self.printLCS(curlen,i - 1, j,s)elif self.direction_list[i - 1][j - 1] == -1:self.printLCS(curlen,i, j - 1,s)else:self.printLCS(curlen,i - 1, j,s)self.printLCS(curlen,i, j - 1,s)def returnLCS(self):#回溯的入口self.printLCS(1,len(self.x), len(self.y),'')if __name__ == '__main__':p = LCS()p.input('ABCBDAB', 'BDCABA')p.Compute_LCS()p.returnLCS()
效果：
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 1 1 1 1 2 2
0 1 1 2 2 2 2
0 1 1 2 2 3 3
0 1 2 2 2 3 3
0 1 2 2 3 3 4
0 1 2 2 3 4 4
max_len: 4 ,sum_len: 13 similarity: 0.6153846153846154
BCBA
BCAB
BDAB
