编程之美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

寻找发帖“水王”

编程之美第2.3题————寻找发帖“水王”

题目描述:

Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说,Tango有一大“水王”,他不但喜欢发贴,还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子(包括回帖)的列表,其中帖子作者的ID也在表中,你能快速找出这个传说中的Tango水王吗?

首先,我们可以假设有这样一个数据结构来表示帖子

[cpp]
type struct post
{
char* title;
char* content;
int uid;
}post_t;
[/cpp]

题目告诉我们已知所有帖子的列表,也就是说我们知道了所有帖子的链表 post_t* post_list,或者是所有帖子的数组post_array[num]。然后让我们找到出现次数最多的uid是多少,并且该uid一定超过了总和的一半。为了叙述方便,下面用数组举例。最容易就想到的方法,就是遍历整个数组,记录每一个uid出现的次数,然后再比较一下,求出最大的。

其实,这个问题就可以等价于:求数组中出现次数大于一半的那个数

解法一

对数组排序,然后遍历排好序的数组,统计各ID出现的次数,找到超过一半的那个即可。代码如下:

[cpp]
int Find (int* post, int len)
{
sort(post, post + len);

int num = 1;
for(int i = 0; i < len; i++)
{
if(post[i] == post[i + 1])
num++;
else
num = 1;
if(num > len / 2)
return post[i];
}
return 0;
}
[/cpp]

这里先调用了一下sort函数排序,也可以换成自己的排序函数。

因为采用了排序,复杂度有所提升,于是书中提出了第二种解法,我觉得是比较巧妙的。

解法二

由于x出现的次数大于总数的一半,所以如果每次删除两个不同的值,不管是否有x,在剩下的数中,x的次数依然会大于总数的一半。

于是,算法可以这样设计

[cpp]
int Find2 (int* post, int len)
{
int x;
int times = 0;
for(int i = 0; i < len; i++)
{
if(times == 0)
{
x = post[i];
times = 1;
}
else
{
if(x == post[i])
times++;
else
times–;
}
}
return x;
}
[/cpp]

该算法不用排序,很巧妙的通过向前移动达到了“删除”的目的,自己真的没想到:)。

越来越觉得优美的代码就是美了,简洁明了,而又功能强大。

扩展问题:

随着Tango的发展,管理员发现,“超级水王”没有了。统计结果表明,有3个发帖很多的ID,他们的发帖数目都超过了帖子总数目N的1/4。你能从发帖ID列表中快速找出他们的ID吗?

解法x

这个思路就是一样的了,设a,b,c三人的发帖数都超过了 1/4,那么把4个不同id删除以后,并不影响剩余数组中a,b,c三人的发帖数都超过1/4这个结果。示意图如下所示。

QQ图片20130721232439

把数组分为四个四个数字一组的来看。由于a的发帖数超过了1/4,所以,平均下来,在每一个分组里都有一个a,并且至少在某一组中有大于一个的a,假如分组1中的四个数字都不相同,我们删除分组1,如果a不在分组1里面,那么在剩余的2~n组中,a出现的次数显然会继续大于1/4;如果a在分组1里面,那么在剩余2~n组中,平均下来,a还是会至少在每一个分组出现一次。所以只要分组1中4个数字不相同(主要是保证没有两个a),那么删除分组1,并不改变a在剩余数组中出现次数依然大于1/4的事实。同理b,c。

代码如下:

[cpp]
void Findx(int* post, int len)
{
int a, b, c;
int ta = 0;
int tb = 0;
int tc = 0;

for(int i = 0; i < len; i++)
{
if(ta == 0)
{
a = post[i];
ta++;
}
else if(a == post[i])
ta++;
else if(tb == 0)
{
b = post[i];
tb++;
}
else if(b == post[i])
tb++;
else if(tc == 0)
{
c = post[i];
tc++;
}
else if(c == post[i])
tc++;
else
{
ta–;
tb–;
tc–;
}
}

cout << "a: " << a << "\t";
cout << "b: " << b << "\t";
cout << "c: " << c << "\t";
}
[/cpp]

Enjoy!

求二进制数中1的个数

编程之美第2.1题————求二进制数中1的个数

题目描述:对于一个字节(8bit)的无符号整形变量,求其中的二进制表示中“1”的个数,要求算法的执行效率尽可能的高。

书中由浅入深地给出了几种解法。

解法一

也是最容易想到的,因为对于无符号整数,若采取对2取余操作,结果只有两种,奇数余1,偶数余0,而奇数的二进制最后一位为1,偶数的二进制最后一位为0。这样我们就可以通过奇偶判断来得到结果,以二进制数1011和1100举例:

1011 对2取余,余数为1,二进制末尾为1,即含有一个1

1100 对2取余,余数为0,二进制末尾为0,即含有一个0

不管这个二进制数的高位有多少个0或者多少个1,对2取余的操作只与最低位相关。所以,如果能够把所有的位都作为最低位,对2取余一次,然后将结果相加,即可得到该题答案。而二进制数中,右移操作,就相当于除以2,所以有了以下解法。

[c]
unsigned int Count (unsigned int x)
{
unsigned int num = 0; // the result
while(x) // end of loop when x is 0
{
if(x % 2 == 1) // to judge whether the last bit is ‘1’
{
num++;
}
x = x / 2; // same as x >> 1
}
return num;
}
[/c]

当然你要是觉得除法耗费时间,可以把x = x / 2改成 x >> 1,本质上是一样的。

解法二

既然提到了右移,就能想到,右移的时候会把最后一位移丢,那我们只要在每一次移动的时候,判断一下最后一位是否为1,然后重复该步骤直到将所有位都移除。用1011举例:
1011,最后一位是1,结果加1,右移一位,变成0101

0101,最后一位是1,结果加1,右移一位,变成0010,

0010,最后一位是0,结果不加,右移一位,变成0001,

0001,最后移位是1,结果加1,右移一位,变成0000,所有位都已移除,结束算法。

而判断最后一位是否为1,可以用&操作,x & 0x1 即可。

算法如下:

[cpp]
unsigned int Count2 (unsigned int x)
{
unsigned int num = 0; // the result
while(x) // end the loop when x is 0
{
// x & 0x01 will be 0 if the last bit is ‘0’, otherwise ‘1’
num = num + (x & 0x01);
x = x >> 1; // right shift 1 bit
}
return num;
}
[/cpp]

可以看到,上述两种解法对每一位都进行了比较运算,时间复杂度都为O(log2x),出于降低时间复杂度的角度,书中又给出了第三种解法,让复杂度只与二进制数中‘1’的个数相关。

解法三

该解法确实好玩儿,让我有一种“让广大码农飞,让搞算法的死”的感觉,很巧妙。还是先举一个例子来阐述原理:对于无符号一个二进制数x,与 x – 1 采取&操作会消除x最低位的1,假设x为1010,0000:

x – 1 的二进制为 1001,1111,与x进行&以后得1000,0000,最低位的1没有了,让x = 1000,0000

x – 1 的二进制位 0111,1111,与x进行&作以后得0000,0000,最低位的1没有了,x 为0,结束算法

算法一共就执行了两次,即‘1’的个数。不管‘1’之后有多少个0,x & (x – 1) 总是会消除最低位的1,这就是该算法的巧妙之处了。代码如下。

[cpp]
unsigned int Count3 (unsigned int x)
{
unsigned int num = 0;
while(x)
{
x = x & (x – 1);
num++
}
return num;
}
[/cpp]

算法把时间复杂度降到了O(n),n为二进制中‘1’的个数。应该算是很不错了,关键是很巧妙,灰常好玩儿有木有。

书中还给出了查表法,因为题目是八位的二进制,那么一共也才256个数,完全可以开一个256大小的数组,将结果存起来,如255的二进制为1111,1111,让result[255] = 8,同理把其他所有数的结果都存一遍,以后需要的时候直接返回result[x]就可以了。只是如果不是八位的,变成了32位,那查表这种空间换时间的方法就很不划算了。

后来查阅网上一些题解的时候,发现很多大牛对此题书中解法的提出了质疑。比如解法三,虽然理论上一次地址计算就可以解决,但实际上这里用到一个访存操作,且第一次访存的时候很有可能那个数组不在cache里,这样一个cache miss导致的后果可能就是耗去几十甚至上百个时钟周期(因为要访问内存)。而对于这种数据规模给定,而且很小的情况下,耗去几十甚至上百个时钟周期是很慢的。所以对于这种“小操作”,这个算法的性能其实是很差的。

然后我看到了另外一个巧妙的解法,有点像二分,个人灰常喜欢。

解法X

怎么说呢,先举个例子,比如整数212的二进制1101,0100,一共有4个‘1’对吧。而正好又是8位大小,有没有一种“对折对折再对折”的冲动,有木有?

于是算法可以这样描述:

先把相邻的‘1’的个数算出来,同样二进制的形势保存起来

QQ图片20130720202159

那么现在 10,01,01,00分别代表了1101,0100中相邻两位中‘1’的个数。而且由于是计算的相邻两位,所以‘1’的个数最多为2,所以用两位足够表示。

现在的问题变成了,如何继续处理第一步得到的结果1001,0100呢,对于1001,0100,

第8位,第7位联合起来,即10,表示了原二进制数(1101,0100)中第8位与第7位所含‘1’的个数。

第6位,第5位联合起来,即01,表示了原二进制数(1101,0100)中第6位与第5位所含‘1’的个数。

第4位,第3位联合起来,即01,表示了原二进制数(1101,0100)中第4位与第3位所含‘1’的个数。

第2位,第1位联合起来,即01,表示了原二进制数(1101,0100)中第2位与第1位所含‘1’的个数。

现在我们就需要把新得到的二进制串1001,0100的

8、7联合位与6、5联合位相加,即把10和01相加,代表原第8,7,6,5位的‘1’的个数

(因为8、7联合起来才表示原第8位和原第7位一共有多少个‘1’,这里不能再次分开计算他们了,应该把他们当成一个整体。同理6、5位,也当成一个整体来看待)

4、3联合位与2、1联合位相加,即把01和01相加,代表原第4,3,2,1位的‘1’的个数

QQ图片20130720225843

后面就类似啦,把0011与0001相加,代表原第8,7,6,5,4,3,2,1位的‘1’的个数

QQ图片20130720230443

就得到最后的结果了,结果为4。

好了,现在剩下的问题就是怎么样让相邻的位相加,怎么样让相邻两位的相加,怎么样让相邻四位的相加。

拿相邻两位的相加举例,

(x & 0x55) + (x >> 1  & 0x55)

因为0x55展开成二进制就是0101,0101,观察1的位置,奇数位为1,偶数位为0,这样和x进行与操作的结果就是保留了x的奇数位。然后x右移一位以后,再与0x55进行与操作,对x>>1来说是保留了奇数位,但相对于原来的x则是保留了偶数位。最后将两式相加,就得到了x的二进制中,相邻两位的‘1’的个数。

同理因为0x33展开成二进制是0011,0011,所以相邻二位的相加则为

(x & 0x33) + (x >> 2 &  0x33)

因为0x0f展开成二进制是0000,1111,所以相邻四位的相加则为

(x & 0x0f) + (x >> 4 &  0x0f)

所以算法如下:

[cpp]
unsigned int CountX (unsigned int x)
{
x = (x & 0x55) + (x >> 1 & 0x55);
x = (x & 0x33) + (x >> 2 & 0x33);
x = (x & 0x0f) + (x >> 4 & 0x0f);
return x;
}
[/cpp]

优美的代码总是很简洁,这个算法估计只要十几行指令吧,速度应该是很不错了,至于网上其他更好的算法,写得让我半天看不懂哈哈~~感觉太复杂了也就失去了美。

最后,POJ的相关题目有Problem2453

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

解题报告:http://keping.me/poj2453/

That’s all,

Enjoy!