编程之美3.3 计算字符串的相似度 (编辑距离)

Part 1: 题目描述

许多程序会大量使用字符串。对于不同的字符串,我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:

1.修改一个字符(如把“a”替换为“b”);

2.增加一个字符(如把“abdd”变为“aebdd”);

3.删除一个字符(如把“travelling”变为“traveling”);

比如,对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一 次 。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于“距离+1”的倒数。也就是说,“abcdefg”和“abcdef”的距离为1,相似度 为1/2=0.5。

给定任意两个字符串,你是否能写出一个算法来计算它们的相似度呢?

Part 2:分析

书中给出的解法是通过递归来做的。其实有更快更简便的方法——动态规划。

此题其实就是算法中的求“最短编辑距离”。

编辑距离定义:计算两个字符串的距离,完全相同的字符串距离为0,可以通过修改一个字符、增加一个字符或删除一个字符三种方式来使两个字符串相同,但这些方式会使得距离加1。

假设现在有两个字符串A和B

A:David

B:Taisy

用二维数组d[i][j]表示A中取前i个字符到B中取前j个字符的最短编辑距离。比如d[2][1]就代表从”Da”到”T”的最短编辑距离。这里为2(即把D换成T,去掉A 或者去掉D,把a换成T)。

首先我们作出初始化d[0][j] = j(字符串A子串长度为0,字符串B子串有多少个字符,就作多少次增加操作;于是同理,作删除操作,可得d[i][0] = i)

其中d[i][j]只有3个来源:

1). 来自d[i – i][j – 1],即 “A的前i-1个字符组成的子串” 到 “B的前j-1个字符组成的子串” 的编辑距离,此时如果A[i] = B[j],则最短编辑距离不变,否则最短编辑距离加1(即把A[i]变为B[j] ),所以d[i][j] = d[i – 1][j – 1] + (A[i] == B[j] ?  0 : 1)

2). 来自d[i – 1][j],即 “A的前i-1个字符组成的子串” 到 “B的前j个字符组成的子串” 的编辑距离。此时删除在A的第i个位置上的字符即可,所以d[i][j] = d[i – 1][j] + 1

3). 来自d[i][j – 1], 即 “A的前i个字符组成的子串” 到 “B的前j-1个字符组成的子串” 的编辑距离。此时在A的子串后面添加一个字符B[j]即可,所以d[i][j] = d[i][j – 1] + 1

于是状态转移方程就写出来啦。

d[i][j] = min (d[i – 1][j – 1] + (A[i] == B[j] ?  0 : 1) ,  d[i – 1][j] + 1 ,  d[i][j – 1] + 1)

 

Part 3: 实现代码。

测试代码如下:

[cpp]
#include
#include

using std::cout;
using std::endl;

int min(int a, int b, int c)
{
int small = a;
if(b < small)
small = b;
if(c < small)
small = c;
return small;
}

int main()
{
char s[] = "David_and_Sophia"; // the last character is ‘\0’
char d[] = "Dadiudiu_and_Xiaodiugirl"; // the last character is ‘\0’

int len_s = strlen(s); // 16
int len_d = strlen(d); // 24
int dist[len_s + 1][len_d + 1];

cout << len_s << endl;
cout << len_d << endl;

for(int i = 0; i <= len_s; i++)
dist[i][0] = i;
for(int i = 0; i <= len_d; i++)
dist[0][i] = i;

for(int i = 1; i <= len_s; i++)
for(int j = 1; j <= len_d; j++)
dist[i][j] = min((dist[i – 1][j] + 1), dist[i][j – 1] + 1, dist[i – 1][j – 1] + (s[i – 1] == d[j – 1] ? 0 : 1));

cout << dist[len_s][len_d] << endl;

return 0;
}
[/cpp]

POJ上有对应的题目, POJ 3356,很类似。链接如下,顺带解题参考代码:
http://poj.org/problem?id=3356

AC的代码:

[cpp]
/*
* Author: David
* Date: 2013-9-4 23:27:11
* Brief: edit distance, DP
* Link: http://poj.org/problem?id=3356
*
* POJ info:
* Problem: 3356 User: davidloves
* Memory: 4632K Time: 16MS
* Language: G++ Result: Accepted
*/

#include

#define SIZE 1001

using std::cin;
using std::cout;
using std::endl;

int min(int a, int b, int c)
{
int small = a;
if(small > b)
small = b;
if(small > c)
small = c;
return small;
}

int main()
{
char x[SIZE];
char y[SIZE];
int len_x, len_y;

while((cin >> len_x >> x >> len_y >> y))
{
int dist[len_x + 1][len_y + 1];

for(int i = 0; i <= len_x; i++)
dist[i][0] = i;
for(int j = 0; j <= len_y; j++)
dist[0][j] = j;

for(int i = 1; i <= len_x; i++)
for(int j = 0; j <= len_y; j++)
dist[i][j] = min((dist[i – 1][j] + 1), dist[i][j – 1] + 1, dist[i – 1][j – 1] + (x[i – 1] == y[j – 1] ? 0 : 1));
cout << dist[len_x][len_y] << endl;
}

return 0;
}
[/cpp]

Enjoy!

POJ 2453 解题报告

题目意思:给定正整数x,求出在二进制表示中与他有相同个数的‘1’,且比他大的最小的数。

可以把此题当成求二进制中1的个数来做。而该算法在我的其他帖子(点击这里)中已经有详细说明。

代码:

[cpp]
#include <iostream>

using namespace std;

int Count (int);
int main()
{
int x, num;

while(cin >> x)
{
if(!x)
break;
num = Count(x);
while(x++)
if(Count(x) == num)
{
cout << x << endl;
break;
}
}
return 0;
}

int Count(int x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);

return x;
}
[/cpp]

原题连接http://poj.org/problem?id=2453