计算字符串的相似度

时间:2023-01-05 03:10:25

来源:http://wdhdmx.iteye.com/blog/1343856

1.百度百科介绍:

Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。

许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

编辑距离的算法是首先由俄国科学家Levenshtein提出的,故又叫Levenshtein Distance。

2.用途

模糊查询

3.实现过程

a.首先是有两个字符串,这里写一个简单的 abc和abe

b.将字符串想象成下面的结构。

A处 是一个标记,为了方便讲解,不是这个表的内容。

 

  abc a b c
abe 0 1 2 3
a 1 A处    
b 2      
e 3      

c.来计算A处 出得值

它的值取决于:左边的1、上边的1、左上角的0.

按照Levenshtein distance的意思:

上面的值和左面的值都要求加1,这样得到1+1=2。

A处 由于是两个a相同,左上角的值加0.这样得到0+0=0。

这是后有三个值,左边的计算后为2,上边的计算后为2,左上角的计算为0,所以A处 取他们里面最小的0.

d.于是表成为下面的样子

  abc a b c
abe 0 1 2 3
a 1 0    
b 2 B处    
e 3      

B处 会同样得到三个值,左边计算后为3,上边计算后为1,在B处 由于对应的字符为a、b,不相等,所以左上角应该在当前值的基础上加1,这样得到1+1=2,在(3,1,2)中选出最小的为B处的值。

e.于是表就更新了

 

  abc a b c
abe 0 1 2 3
a 1 0    
b 2 1    
e 3 C处    

C处 计算后:上面的值为2,左边的值为4,左上角的:a和e不相同,所以加1,即2+1,左上角的为3。

在(2,4,3)中取最小的为C处 的值。

f.于是依次推得到

    a b c
  0 1 2 3
a 1 A处 0 D处 1 G处 2
b 2 B处 1 E处 0 H处 1
e 3 C处 2 F处 1 I处 1

 

I处: 表示abc 和abe 有1个需要编辑的操作。这个是需要计算出来的。

同时,也获得一些额外的信息。

A处: 表示a      和a      需要有0个操作。字符串一样

B处: 表示ab    和a      需要有1个操作。

C处: 表示abe  和a      需要有2个操作。

D处: 表示a      和ab    需要有1个操作。

E处: 表示ab    和ab    需要有0个操作。字符串一样

F处: 表示abe  和ab    需要有1个操作。

G处: 表示a      和abc   需要有2个操作。

H处: 表示ab    和abc    需要有1个操作。

I处: 表示abe   和abc    需要有1个操作。

g.计算相似度

先取两个字符串长度的最大值maxLen,用1-(需要操作数除maxLen),得到相似度。

例如abc 和abe 一个操作,长度为3,所以相似度为1-1/3=0.666。

 

#include <iostream>
#include <string>
using namespace std;

int minValue(int a,int b,int c)
{
	if (a>b)
	{
		return b>c? c:b;
	}
	else
	{
		return a>c? c:a;
	}
}
//这个方法是编程之美的递归方法。
int calStringDis(string strA, int pABegin,int pAEnd,string strB, int pBBegin,int pBEnd)
{  
	if (pABegin > pAEnd)  
	{  
		if (pBBegin > pBEnd)  
			return 0;   
		else  
			return pBEnd - pBBegin + 1;  
	}  
	if (pBBegin > pBEnd)  
	{  
		if(pABegin > pAEnd)  
			return 0;  
		else  
			return pAEnd - pABegin + 1;  
	}  
	if (strA[pABegin] == strB[pBBegin])  
	{  
		return calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd);  
	}  
	else  
	{  
		int t1 = calStringDis(strA,pABegin,pAEnd,strB,pBBegin+1,pBEnd);  
		int t2 = calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin,pBEnd);  
		int t3 = calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd);  

		return minValue(t1,t2,t3)+1;  
	}  
}

//Levenshtein算法实现求编辑距离
int calStringDistance(string &str1,string &str2)
{
	int len1,len2;
	len1=str1.length();
	len2=str2.length();
	int i,j;
	if (len1==0)
	{
		return len2;
	}
	if (len2==0)
	{
		return len1;
	}
	int **c=new int *[len2+1];
	for (i=0;i<=len2;i++)
	{
		c[i]=new int[len1+1];
	} 
	c[0][0]=0;
	for (i=1;i<=len2;i++)
	{
		c[i][0]=i;
	}
	for (j=1;j<=len1;j++)
	{
		c[0][j]=j;
	}
	for (i=1;i<=len2;i++)
	{
		for (j=1;j<=len1;j++)
		{
			if (str2[i-1]==str1[j-1])
			{
				c[i][j]=minValue(c[i-1][j-1],c[i-1][j]+1,c[i][j-1]+1);
			}
			else
			{
				c[i][j]=minValue(c[i-1][j-1]+1,c[i-1][j]+1,c[i][j-1]+1);
			}
		}
	}
	return c[len2][len1];
}

int main()
{
	string str1="abcd";
	string str2="bcdef";
	cout<<calStringDis(str1,0,str1.length()-1,str2,0,str2.length()-1)<<endl;
	cout<<calStringDistance(str1,str2)<<endl;
	return 0;
}


一个更加快速高效的Levenshtein算法http://www.cnblogs.com/ymind/archive/2012/03/27/fast-memory-efficient-Levenshtein-algorithm.html

说明

原来的算法是创建一个大小为StrLen1*StrLen2的矩阵。如果所有字符串加起来是1000个字符那么长的话,那么这个矩阵就会是1M;如果字符串是10000个字符,那么矩阵就是100M。如果元素都是整数(这里是指数字,Int32)的话,那么矩阵就会是4*100M == 400MB这么大,唉……

现在的算法版本只使用2*StrLen个元素,这使得后面给出的例子成为2*10,000*4 = 80 KB。其结果是,不但内存占用更少,而且速度也变快了!因为这使得内存分配只需要很少的时间来完成。当两个字符串的长度都是1k左右时,新算法的效率是旧算法的两倍!

示例

原来的版本将会创建一个矩阵[6+1, 5+1],而我的新算法将会创建两个向量[6+1](黄色元素)。在这两个算法版本中,字符串的顺序是无关紧要、无所谓的,也就是说,它也可以是矩阵[5+1, 6+1]和两个向量[5+1]。

新的算法

步骤

步骤 说明
1 设置n为字符串s的长度。("GUMBO") 
设置m为字符串t的长度。("GAMBOL") 
如果n等于0,返回m并退出。
如果m等于0,返回n并退出。
构造两个向量v0[m+1] 和v1[m+1],串联0..m之间所有的元素。
2 初始化 v0 to 0..m。
3 检查 s (i from 1 to n) 中的每个字符。
4 检查 t (j from 1 to m) 中的每个字符
5 如果 s[i] 等于 t[j],则编辑代价为 0;
如果 s[i] 不等于 t[j],则编辑代价为1。
6 设置单元v1[j]为下面的最小值之一:
a、紧邻该单元上方+1:v1[j-1] + 1
b、紧邻该单元左侧+1:v0[j] + 1
c、该单元对角线上方和左侧+cost:v0[j-1] + cost
7 在完成迭代 (3, 4, 5, 6) 之后,v1[m]便是编辑距离的值。

本小节将演示如何计算"GUMBO"和"GAMBOL"两个字符串的Levenshtein距离。

步骤1、2

  v0 v1        
    G U M B O
  0 1 2 3 4 5
G 1          
A 2          
M 3          
B 4          
O 5          
L 6          

步骤3-6,当 i = 1

 

  v0 v1        
    G U M B O
  0 1 2 3 4 5
G 1 0        
A 2 1        
M 3 2        
B 4 3        
O 5 4        
L 6 5        

步骤3-6,当 i = 2

    v0 v1      
    G U M B O
  0 1 2 3 4 5
G 1 0 1      
A 2 1 1      
M 3 2 2      
B 4 3 3      
O 5 4 4      
L 6 5 5      

步骤3-6,当 i = 3

 

      v0 v1    
    G U M B O
  0 1 2 3 4 5
G 1 0 1 2    
A 2 1 1 2    
M 3 2 2 1    
B 4 3 3 2    
O 5 4 4 3    
L 6 5 5 4    

步骤3-6,当 i = 4

 

        v0 v1  
    G U M B O
  0 1 2 3 4 5
G 1 0 1 2 3  
A 2 1 1 2 3  
M 3 2 2 1 2  
B 4 3 3 2 1  
O 5 4 4 3 2  
L 6 5 5 4 3  

步骤3-6,当 i = 5

 

          v0 v1
    G U M B O
  0 1 2 3 4 5
G 1 0 1 2 3 4
A 2 1 1 2 3 4
M 3 2 2 1 2 3
B 4 3 3 2 1 2
O 5 4 4 3 2 1
L 6 5 5 4 3 2

步骤7

编辑距离就是矩阵右下角的值,v1[m] == 2。由"GUMBO"变换为"GAMBOL"的过程对于我来说是很只管的,即通过将"A"替换为"U",并在末尾追加"L"这样子(实际上替换的过程是由移除和插入两个操作组合而成的)。

改良

如果您确信你的字符串永远不会超过2^16(65536)个字符,那么你可以使用ushort来表示而不是int,如果字符串少于2^8个,还可以使用byte。我觉得这个算法用非托管代码实现的话可能会更快,但我没有试过。