您的位置: 首页  >  文章  >  计算最长公共子序列LCS（Python实现）

计算最长公共子序列LCS（Python实现）

分类: 文章 • 2024-12-10 08:02:04

     最长公共子序列参考：https://blog.****.net/v_JULY_v/article/details/6110269

一、概念

     两个字符串X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最长公共子序列不要求在原字符串中是连续的，比如ADE和ABCDE的最长公共子序列是ADE。具体求解时关注于字符串最后一个字符：
计算最长公共子序列LCS（Python实现）
     相应的，设c[i,j]存储Xi与Yj的最长公共子序列的长度，由LCS的递归公式可得长度的递归公式如下：当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i,j]=0。
计算最长公共子序列LCS（Python实现）
     例如，设所给的两个序列为X=<A，B，C，B，D，A，B>和Y=<B，D，C，A，B，A>。由长度公式可得二维数组如下：


计算最长公共子序列LCS（Python实现）

     例如c[3,2]=1表示ABC和BD的LCS长度为1，计算时因为末尾字符C不等于D，故c[3,2] =max{c[2,2],c[3,1]}即max{AB和BD的LCS长度，ABC和B的LCS长度}。先填满第一行和第一列，再依次计算第二行直到第八行。c[7,6]即为字符串X和Y的LCS的长度。

二、实践

     利用两个字符串最长公共子序列的长度，求两个字符串的相似度，在推荐中可用于过滤相似标题的实例。

  • 输入数据部分如下：
    计算最长公共子序列LCS（Python实现）
  • 代码如下：
# -*- coding: utf-8 -*-
#!/usr/bin/python

import sys

def cal_lcs_sim(first_str, second_str):
    len_vv = [[0] * 50] * 50   %第一个50为列数，第二个50为行数

    first_str = unicode(first_str, "utf-8", errors='ignore')
    second_str = unicode(second_str, "utf-8", errors='ignore')

    len_1 = len(first_str.strip())
    len_2 = len(second_str.strip())

    for i in range(1, len_1 + 1):
        for j in range(1, len_2 + 1):
            if first_str[i - 1] == second_str[j - 1]:
                len_vv[i][j] = 1 + len_vv[i - 1][j - 1]
            else:
                len_vv[i][j] = max(len_vv[i - 1][j], len_vv[i][j - 1])

    return float(float(len_vv[len_1][len_2] * 2) / float(len_1 + len_2))  %两个字符串的相似度


for line in sys.stdin:
    ss = line.strip().split('\t')
    if len(ss) != 2:
        continue
    first_str = ss[0].strip()
    second_str = ss[1].strip()

    sim_score = cal_lcs_sim(first_str, second_str)
    print '\t'.join([first_str, second_str, str(sim_score)])

     若字符串S1的长度为m，S2的长度为n，LCS（S1,S2）的长度为c，则相似度=(c * 2) / (m + n)，将相似度缩放到[0,1]内，这是因为如果其中一个字符串很长，假设m = 1000，c = 1，那么相似度应该是很低；如果两个串长度一致且相同，那么相似度就该很高即100%相似。

  • 输出结果如下：
    计算最长公共子序列LCS（Python实现）

相关推荐