NLP自然语言 之 LCS最长公共子序列（Longest Common Subsequence）（三）

NLP
LCS, NLP

前言

前面我们知道了通过TF-IDF找出文章中的关键词，以及通过余弦相似度来判断两个句子或者文章的相似程度。那么我们还可以通过LCS即最长公共子序列（Longest Common Subsequence）的方式来比对两段文字之间的相似度。

LCS定义

  • 一个序列S任意删除若干个字符得到的新序列T,则T叫做S的子序列
  • 两个序列X和Y的公共子序列中，长度最长的那个定义为X和Y的最长公共子序列
    • 字符串123456789与567891011的最长公共子序列为56789
    • 字符串adfa与afa的最长公共子序列为afa

LCS作用

  • 求两个序列中最长的公共子序列
  • 描述两段文字之间的相似度（根据最长子序列来判断，举例如果一个句子一共20个字符，另外一个15个字符，假如它们的最长子序列达到了10个字符，那么这里两个句子相似度应该就比较高了）

LCS公式

a = ‘BDCABA’
b = ‘ABCBDAB’

属于动态规划问题

  • 使用二维数组C(m,n)

  • C[i,j]记录序列X_i和Y_j的最长公共子序列的长度

    当i=0或j=0时，空虚了是X_i和Y_j的最长公共子序列，即C[i,j]=0

LCS代码实现

计算文本相似度

  • 将两个字符串分别以行和列组成矩阵。
  • 计算每个节点行列字符是否相同，如相同则为 通过公式计算。
  • 通过找出值变化 的最长对角线即可得到最长公共子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# coding=utf-8
def lcs(a, b):
    # a字符的长度
    n = len(a)
    # b字符的长度
    m = len(b)
    # 声明一个二维数组默认值全部为0
    # 外层长度为 a（n）字符的长度+ 1
    # 内层长度为 b（m）字符的长度+ 1
    # data[n][m] 即 n行m列
    l = [[0]*(m+1) for i in range(n+1)]

    # 从1开始循环到n+1行
    # 从1开始循环到m+1列

    # 如果相同，则取对角数值+1
    # 如果不相同，则取对角右和下的最大值
    for i in range(n+1)[1:]:
        for j in range(m+1)[1:]:
            if a[i-1] == b[j-1]:
                l[i][j] = l[i-1][j-1] + 1
            else:
                l[i][j] = max(l[i-1][j], l[i][j-1])
    print
    for data in l:
        print data

a = 'BDCABA'
b = 'ABCBDAB'
lcs(a, b)
1
2
3
4
5
6
7
8
9
代码结果输出：
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1]
[0, 0, 1, 1, 1, 2, 2, 2]
[0, 0, 1, 2, 2, 2, 2, 2]
[0, 1, 1, 2, 2, 2, 3, 3]
[0, 1, 2, 2, 3, 3, 3, 4]
[0, 1, 2, 2, 3, 3, 4, 4]
即最长公共子序列为：BDAB，即一个句子6个字符，一个句子7个字符。它们的公共子序列达到了4个字符，那么可以理解它们的相似度应该比较高了

代码：https://github.com/lishijia/py-data-demo/tree/master/nlp

NLP自然语言 之 余弦相似度 （一 Python代码实现）

NLP自然语言 之 TF-IDF（二）

分享到 评论