数据结构基础字符串相似度与最长公共子序列

我就是我 2022-08-21 04:42 7阅读 0赞

字符串的相似性：如果将一个串转换成为另一个串所需的操作数最少，那么可以说这两个串是相似的。另外一种权衡的方法是，寻换第三个串s3，如果s3都出现在s1和s2中，且出现的顺序相同，但不要求在s1和s2中连续，那么s3的长度越大，就说明相似度越高。

后一种对相似度概念命名为最长公共子序列。

1、最长公共子序列的特征

如果用暴力搜索的方法求解LCS问题，就要穷举X的所有子序列，对每个子序列进行检查，看它是否是Y的子序列，记录找到的最长的子序列。X对应下标人格集合\{1，2，3……m\}的一个子集，那么X的子序列就有2^m个。

但其实LCS是具有最优子结构的：

令X=\{x1,x2,x3……xm\}, Y=\{y1,y2,y3……yn\}。Z=\{z1,z2,z3……zk\}为X和Y的任意LCS.则有：

（1）如果xm=yn, 则zk = xm = yn,且Zk-1是Xm-1与Yn-1的LCS.

(2)如果xm!=yn,则zk!=xm意味着Zk-1是Xm-1与Y的LCS

(3)如果xm!=yn,则zk!=yn意味着Zk-1是Yn-1与X的LCS

2、递归解

用dp\[i\]\[j\]表示Xi与Yj的LCS的长度。

dp\[i\]\[j\] = 0 if i = 0 or j =0

dp\[i\]\[j\] = dp\[i-1\]\[j-1\] +1 if xi = yj

dp\[i\]\[j\] = max(dp\[i-1\]\[j\], dp\[i\]\[j-1\]) if x1!=yj

代码如下：

**\[cpp\]** [view plain][] [copy][view plain]

1.  // LCS.cpp : Defines the entry point for the console application.
2.  //
3.  
4.  \#include "stdafx.h"
5.  \#include <string.h>
6.  \#include <iostream>
7.  
8.  **using****namespace** std; 
9.  
10. \#define MaxLength 100
11. 
12. **int** max(**int** a,**int** b) 
13. \{ 
14. **return** a>=b?a:b; 
15. \} 
16. 
17. //既保存了长度值，又记录了最长公共子序列
18. **void** LCS\_Length(**char** x\[\], **char** y\[\], **int** m, **int** n, **int** c\[\]\[MaxLength\], **int** b\[\]\[MaxLength\]) 
19. \{ 
20. **for**(**int** i=0;i<m;i++) 
21.  c\[i\]\[0\] = 0; 
22. **for**(**int** j=0;j<n;j++) 
23.  c\[0\]\[j\] = 0; 
24. **for**(**int** i=1;i<=m;i++) 
25.  \{ 
26. **for**(**int** j=1;j<=n;j++) 
27.  \{ 
28. **if**(x\[i-1\] == y\[j-1\]) 
29.  \{ 
30.  c\[i\]\[j\] = c\[i-1\]\[j-1\] + 1; 
31.  b\[i\]\[j\] = 0; 
32.  \} 
33. **else****if**(c\[i-1\]\[j\]>=c\[i\]\[j-1\]) 
34.  \{ 
35.  c\[i\]\[j\] = c\[i-1\]\[j\]; 
36.  b\[i\]\[j\] = 1; 
37.  \} 
38. **else**
39.  \{ 
40.  c\[i\]\[j\] = c\[i\]\[j-1\]; 
41.  b\[i\]\[j\] = -1; 
42.  \} 
43. 
44.  \} 
45.  \} 
46.  cout<<"LCS = "<<c\[m\]\[n\]<<endl; 
47. \} 
48. 
49. **int** LCS(**char** x\[\],**char** y\[\],**int** m,**int** n, **int** c\[\]\[MaxLength\]) 
50. \{ 
51. **int** i = 0, j =0; 
52. **for**(i = 0;i<m;i++) 
53.  c\[i\]\[0\] = 0; 
54. **for**(j = 0;j<n;j++) 
55.  c\[0\]\[j\] = 0; 
56. **for**(i = 1 ;i<=m;i++) 
57.  \{ 
58. **for**(j = 1;j<=n;j++) 
59.  \{ 
60. **if**(x\[i-1\]==y\[j-1\]) 
61.  c\[i\]\[j\] = c\[i-1\]\[j-1\]+1; 
62. **else**
63.  c\[i\]\[j\] = max(c\[i-1\]\[j\],c\[i\]\[j-1\]); 
64.  \} 
65.  \} 
66. **return** c\[m\]\[n\]; 
67. \} 
68. **void** Print\_LCS(**int** b\[\]\[MaxLength\], **char** x\[\], **int** m, **int** n) 
69. \{ 
70. **if**(m==0||n==0) 
71. **return**; 
72. **if**(b\[m\]\[n\] == 0) 
73.  \{ 
74.  Print\_LCS(b,x,m-1,n-1); 
75.  printf("%c ",x\[m-1\]); 
76.  \} 
77. **else****if**(b\[m\]\[n\] == 1) 
78.  Print\_LCS(b,x,m-1,n); 
79. **else**
80.  Print\_LCS(b,x,m,n-1); 
81. \} 
82. **int** \_tmain(**int** argc, \_TCHAR\* argv\[\]) 
83. \{ 
84. **char** x\[8\] = "abcbdab"; 
85. **char** y\[7\] = "bdcaba"; 
86. **int** c\[MaxLength\]\[MaxLength\], b\[MaxLength\]\[MaxLength\]; 
87.  LCS\_Length(x,y,7,6,c,b); 
88.  Print\_LCS(b,x,7,6); 
89.  cout<<"LCS = "<<LCS(x,y,7,6,c); 
90. **return** 0; 
91. \}

那么对于字符串相似度的前一种解释，延伸出这样一道算法题目：

计算字符串的相似度，定义了一套操作方法，把两个不同的字符串变得相同，具体操作方法：

(1) 修改一个字符;(2) 增加一个字符;(3) 删除一个字符。

如果所进行的操作数越少，相似度就越高，那么这道题目就转换成了，将两个字符串变为相同的字符串，所需的最小操作数。

对于两个字符：A=xabcdae, B=xfdfa。它们的第一个字符是相同的，那么只需要计算A\[2……7\]和B\[2……5\]的距离就可。如果第一个字符不同，那么可以进行这样的操作：

（1）删除A串的第一个字符，然后计算A\[2->lenA\]与B\[1->lenB\]。

（2）删除B串的第一个字符，然后计算A\[1->lenA\]与B\[2->lebB\]。

（3）修改A串的第一个字符为B串的第一个字符，然后计算A\[2……lenA\]与B\[2……lenB\]

（4）修改B串的第一个字符为A串的第一个字符，然后计算A\[2……lenA\]与B\[2……lenB\]

（5）增加A串的第一个字符到B串的第一个字符前，然后计算A\[1……lenA\]与B\[2……lenB\]

（6）增加B串的第一个字符到A串的第一个字符前，然后计算A\[2……lenA\]与B\[1……lenB\]

即，经过一步操作后，将A\[1->lenA\]与B\[2->lenB\]变为相同的字符串；将A\[2->lenA\]与B\[1->lenB\]变为相同的字符串；将A\[2->lenA\]与B\[2->lenB\]变为相同的字符串。这样求最小的操作数，就是求这三种情况的最小值。

令dp\[i\]\[j\]表示A从第i个字符开始，B从第j个字符开始，所需要的操作数。

那么if A\[i\]!=B\[j\] , dp\[i\]\[j\] = min(dp\[i+1\]\[j\] , dp\[i\]\[j+1\], dp\[i+1\]\[j+1\]) +1

else dp\[i\]\[j\] = dp\[i+1\]\[j+1\]

部分代码如下：

**\[cpp\]** [view plain][] [copy][view plain]

1.  **int** DP(**int** n, **int** m) 
2.  \{ 
3.  **int** i = 0,j=0; 
4.  //初始化dp,
5.  **for**(i=0;i<n;i++) 
6.   dp\[i\]\[m\] = MaxLength; 
7.  **for**(j=0;j<m;j++) 
8.   dp\[n\]\[j\] = MaxLength; 
9.  
10. **for**(i = n-1;i>0;i--) 
11.  \{ 
12. **for**(j = m-1;j>0;j--) 
13.  \{ 
14. **if**(X\[i\]==Y\[j\]) 
15.  dp\[i\]\[j\] = dp\[i+1\]\[j+1\]; 
16. **else**
17.  dp\[i\]\[j\] = min(dp\[i+1\]\[j\],dp\[i\]\[j+1\],dp\[i+1\]\[j+1\])+1; 
18.  \} 
19.  \} 
20. 
21. **return** dp\[0\]\[0\]; 
22. 
23. \}

[view plain]: http://blog.csdn.net/cyongxue/article/details/14119695#