快速计算文本相似度

梦中的挂念

考虑求出最长子序列（LCS），再除以两串中最长的，得出相似度。


求最长子序列有穷举法，设字符串长度为n，其计算量为2的n次方，十分恐怖。


所以考虑使用动态规划递推解决。

注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。


首先，子序列和子串是不一样的。子串是连续的，而子序列中的元素组成可以是不连续的，但元素的位置下标一定是递增的。以一个字串S = "abcdef"为例，字串S的一个子串是"abc",'cdef'这种连续的，而子序列可以是"abc"，也可以是"af "，给人的直观感觉就是用S中的字符拼凑成的，但f一定在a之前。

      我们设有两个字符串X和Y，其中，X={x0, x1, x2, ....xi }，Y={y0, y1, y2, yj }。用lcs(i , j)表示字符串X与Y的最长公共子序列的长度。
由动态规划思想可知，问题的最优解是由子问题的最优解构成的，所以lcs(i,j) 的值与lcs(i-1, j-1), lcs(i-1, j), lcs(i, j-1) 都有一定的关系。
要确定lcs(i,j)的值，首先比较一下xi, yj 的值，有以下2种情况：

1. xi == yj，说明xi与yj 一定在最长公共子序列中，所以lcs (i , j) 是由lcs(i-1,j -1)之前的值决定的，即
     lcs(i,j) = lcs(i-1, j-1) + 1；
2. xi != yj ，设在最长公共子序列中的最后一个值为zk，可能zk == xi，也可能zk == yj，也可能zk与xi, yj的值都不同。
    这3种情况的分析如下：
     a. zk == xi, 那么最长公共子序列取决于去掉yj的Y字符串与X字符串的最长公共子序列，
         即lcs(i, j) = lcs(i, j-1)；
     b. 与a同理，若yj在最长公共子序列中，那么lcs(i, j) = lcs(i - 1, j)；
     c. zk与xi, yj的值都不同，那么lcs( i, j ) 的值取决于去掉xi的X字串与去掉yj的Y字串的最长公共子序列的长度，即
         lcs(i, j) = lcs( i-1, j-1)。

     结合a,b,c的情况，因为最长公共子序列必有最大的长度，所以
     lcs(i, j) = max ( lcs( i-1, j) , lcs( i, j-1) )。这个公式之所以包含情况c，是因为在情况c下，最长公共子序列的最后一个
     值zk肯定是xi与yj之前的位置上的值，xi 与yj 在这种情况下对最长公共子序列的长度没有影响力，所以在这种情况下，
      lcs( i-1, j) 和 lcs( i, j-1)都等于lcs (i -1, j -1)，可归并到公式中。


因此可得状态转移方程为：



if (xi == yj) LCS(i,j) = LCS(i-1, j-1) + 1
if (xi != yj) LCS(i, j) = max ( LCS( i-1, j) , LCS( i, j-1) )


具体请看源码
快速计算文本相似度.zip (2.2 KB, 下载次数: 963)

2016-4-19 01:41 上传

点击文件名下载附件

w322zkkw

一曲长歌入冬流

精彩文章希望继续努力

aosheng

666666666666666666666

single刘

为什么是短整数型啊？我要比较的字符串比较长呢？

Conquer

谢谢分享，学习一下

itoljeipw

谢谢分享，学习一下

小情缘

谢谢分享，学习一下

kfccfk

谢谢分享，学习一下

shelkio

我来看看了

瀚伟00

学习一下