Calculate Distance Of String

字符串相似度算法介绍

Keyword: 余弦定理 向量空间算法 最长公共子串 编辑距离
Reference: http://www.360doc.com/content/09/0201/10/96202_2430786.shtml

1.编辑距离(Levenshtein Distance)

  编辑距离就是用来计算从原串(s)转换到目标串(t)所需要的最少的插入,删除和替换
的数目,在NLP中应用比较广泛,如一些评测方法中就用到了(wer,mWer等),同时也常用来计算你对原文本所作的改动数。编辑距离的算法是首先由俄国科学家Levenshtein提出的,故又叫Levenshtein Distance。
Levenshtein Distance算法可以看作动态规划。它的思路就是从两个字符串的左边开始比较,记录已经比较过的子串相似度(实际上叫做距离),然后进一步得到下一个字符位置时的相似度。 用下面的例子: GUMBO和GAMBOL。当算到矩阵D[3,3]位置时,也就是当比较到GUM和GAM时,要从已经比较过的3对子串GU-GAM, GUM-GA和GU-GA之中选一个差别最小的来当它的值. 所以要从左上到右下构造矩阵。
编辑距离的伪算法:
整数 Levenshtein距离(字符 str1[1..lenStr1], 字符 str2[1..lenStr2])
宣告 int d[0..lenStr1, 0..lenStr2]
宣告 int i, j, cost

   对于 i 等于 由 0 至 lenStr1
d[i, 0] := i
对于 j 等于 由 0 至 lenStr2
d[0, j] := j
对于 i 等于 由 1 至 lenStr1
对于 j 等于 由 1 至 lenStr2
若 str1[i] = str2[j] 则 cost := 0
否则 cost := 1
d[i, j] := 最小值(
d[i-1, j  ] + 1,     // 删除
d[i  , j-1] + 1,     // 插入
d[i-1, j-1] + cost   // 替换
)
返回 d[lenStr1, lenStr2]

2.最长公共子串 (LCS)

  LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1序列,其对应的位置就是最长匹配子串的位置。

  下面是字符串21232523311324和字符串312123223445的匹配矩阵,前者为X方向的,后者为Y方向的。不难找到,红色部分是最长的匹配子串。通过查找位置我们得到最长的匹配子串为:21232
但是在0和1的矩阵中找最长的1对角线序列又要花去一定的时间。通过改进矩阵的生成方式和设置标记变量,可以省去这部分时间。下面是新的矩阵生成方式:

当字符匹配的时候,我们并不是简单的给相应元素赋上1,而是赋上其左上角元素的值加一。我们用两个标记变量来标记矩阵中值最大的元素的位置,在矩阵生成的过程中来判断当前生成的元素的值是不是最大的,据此来改变标记变量的值,那么到矩阵完成的时候,最长匹配子串的位置和长度就已经出来了。

3. 余弦定理 (向量空间算法)

  余弦定理古老而广泛的数学概念,在各个学科及实践中都得到了大量的应用,这里简单的介绍下其在判断两个字符串相似度的应用。在余弦定理中基本的公式为:

  假如字符串s1与s2,比较两个字符串的相似度,sim(s1,s2),假设s1,s2中含有n个不同的字符,其分别为c1,c2,… cn,判断字符串的相似度转换为两个字符串对应的向量v1,v2之间夹角大小的判断,余弦值越大其向量之间的夹角越小,s1与S2的相似度越大。

向量空间算法的介绍:

  在向量空间模型中,文本泛指各种机器可读的记录。用D(Document)表示,特征项(Term,用t表示)是指出现在文档D中且能够代表该文档内容的基本语言单位,主要是由词或者短语构成,文本可以用特征项集表示为D(T1,T2,…,Tn),其中Tk是特征项,1<=k< =N。例如一篇文档中有a、b、c、d四个特征项,那么这篇文档就可以表示为D(a,b,c,d)。对含有n个特征项的文本而言,通常会给每个特征项赋予一定的权重表示其重要程度。即D=D(T1,W1;T2,W2;…,Tn,Wn),简记为D=D(W1,W2,…,Wn),我们把它叫做文本D的向量表示。其中Wk是Tk的权重,1<=k<=N。在上面那个例子中,假设a、b、c、d的权重分别为30,20,20,10,那么该文本的向量表示为D(30,20,20,10)。在向量空间模型中,两个文本D1和D2之间的内容相关度Sim(D1,D2)常用向量之间夹角的余弦值表示,公式为:  

  其中,W1k、W2k分别表示文本D1和D2第K个特征项的权值,1<=k<=N。我们可以利用类似的方法来计算两个字符串的相关度。    
这个算法网上没找到,虽然我写过,但是没什么通用性,就不贴出来。很简单的,有兴趣的可以自己写一个。

判断字符串相似程度

Reference: http://www.xushine.com/?p=851

在使用搜索引擎的过程中~我们经常会会发现,搜索引擎会返回我们搜索关键词的相似词
这是一种非常人性话的功能
其实不光是搜索引擎~,我们在进行数据库的操作的时候其实也是希望能有相似词的返回~这样可以大大的简化我们的工作~

/*判断一个字符串是否包含另一个字符串函数(字符串中的字符即可以是字母数字又可以是文字)
用来判断一个字符串是否包含另一个字符串(即一个字符串是否是另一个字符串的子串)
a:接收长字符串 b:接收短字符串(即要判断的子串)
返回值:0:b不是a的子串 1:b是a的子串*/
int Contain(char* a,char *b)
{
int len=Strlen(b);
while(*a!='\0')
{
bool flag;
if(*a<0) //如果当前的字符的ASCII码为正(判断一位是否相等),为负(判断两位是否相等)
{
flag=(*a==*b&&*(a+1)==*(b+1)); //判断两位
}
else
{
flag=(*a==*b); //判断一位
}
if(flag)
{
char *p=a,*q=b,count=0;
while(*p!='\0'&&*q!='\0')
{
if(*p<0) //如果当前的字符的ASCII码为正(判断一位是否相等),为负(判断两位是否相等)
{
flag=(*p==*q&&*(p+1)==*(q+1)); //判断两位
}
else
{
flag=(*p==*q); //判断一位
}
if(flag) count++; //相等count加1
(*p>0)?p++:p=p+2; //如果当前的字符的ASCII码为正(指针下移一位),为负(指针下移两位)
(*q>0)?q++:q=q+2;
}
if(count==len) //count等于字符串b的准长度表示字符串a包含字符串b返回1
{
return 1;
}
}
(*a>0)?a++:a=a+2; //如果当前的字符的ASCII码为正(指针下移一位),为负(指针下移两位)
}
return 0;
}
/*姓名模糊查找函数(姓名或条件字符串中的字符即可以是字母数字又可以是文字)
功能说明:此函数用来判断姓名字符串与条件字符串的相似程度
(
例如:若查找条件字符串叫"李斌强",则程序将
按'李斌强'、'李斌'、'斌强'、'李'、'斌'、'强'
依次匹配,匹配一个相似程度相应增加一级,
若一个人的姓名叫"李斌强",则其相似程度为6级;
若一个人的姓名叫"李斌宾强",则其相似程度为4级;
若一个人的姓名叫"王斌强",则其相似程度为3级;
若一个人的姓名叫"李宾强",则其相似程度为2级;
若一个人的姓名叫"李bin强",则其相似程度为2级;
若一个人的姓名叫"Mr.李",则其相似程度为1级;
)
foun:接收姓名字符串 cond:接收条件字符串
返回值:相似程度(假设条件字符串有3个汉字,则最大相似程度为6级<1+2+3=6>)*/
int Namcmp(char* foun,char* cond)
{
char* p=cond;
int len=Strlen(cond);
int count=0; //记录相似程度
for(int i=0;i<len;i++) //条件字符串的准长度
{
p=cond;
for(int j=0;j<i+1;j++) //有多少个准长度相同的子串就循环多少次
{
char *s=p;
char temp[20];
char *t=temp;
for(int k=0;k<len-i;k++) //子串的准长度是多少就循环多少次
{
if(*s>0) //如果当前的字符的ASCII码为正(赋值一位),为负(赋值两位)
{
*t=*s; //赋值一位
}
else
{
*t=*s;
*(++t)=*(++s); //赋值两位
}
s++;
t++;
}
*t='\0';
t=new char[20];
strcpy(t,temp);
if(Contain(foun,t)) count++; //判断姓名字符串是否包含刚拆分的条件字符串的子串
delete t;
(*p>0)?p++:p=p+2; //如果当前的字符的ASCII码为正(指针下移一位),为负(指针下移两位)
}
}
return count;
}

数学之美 系列 12 - 余弦定理和新闻的分类

Reference: http://www.google.com.hk/ggblog/googlechinablog/2006/07/12_4010.html

余弦定理和新闻的分类似乎是两件八杆子打不着的事,但是它们确有紧密的联系。具体说,新闻的分类很大程度上依靠余弦定理。

Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻,它只能快速计算。这就要求我们设计一个算法来算出任意两篇新闻的相似性。为了做到这一点,我们需要想办法用一组数字来描述一篇新闻。

我们来看看怎样找一组数字,或者说一个向量来描述一篇新闻。回忆一下我们在“如何度量网页相关性”一文中介绍的TF/IDF 的概念。对于一篇新闻中的所有实词,我们可以计算出它们的单文本词汇频率/逆文本频率值(TF/IDF)。不难想象,和新闻主题有关的那些实词频率高,TF/IDF 值很大。我们按照这些实词在词汇表的位置对它们的 TF/IDF 值排序。比如,词汇表有六万四千个词,分别为

单词编号 汉字词


1 阿
2 啊
3 阿斗
4 阿姨

789 服装
….
64000 做作

在一篇新闻中,这 64,000 个词的 TF/IDF 值分别为

单词编号 TF/IDF 值

1 0
2 0.0034
3 0
4 0.00052
5 0

789 0.034

64000 0.075

如果单词表中的某个次在新闻中没有出现,对应的值为零,那么这 64,000 个数,组成一个64,000维的向量。我们就用这个向量来代表这篇新闻,并成为新闻的特征向量。如果两篇新闻的特征向量相近,则对应的新闻内容相似,它们应当归在一类,反之亦然。

学过向量代数的人都知道,向量实际上是多维空间中有方向的线段。如果两个向量的方向一致,即夹角接近零,那么这两个向量就相近。而要确定两个向量方向是否一致,这就要用到余弦定理计算向量的夹角了。

余弦定理对我们每个人都不陌生,它描述了三角形中任何一个夹角和三个边的关系,换句话说,给定三角形的三条边,我们可以用余弦定理求出三角形各个角的角度。假定三角形的三条边为 a, b 和 c,对应的三个角为 A, B 和 C,那么角 A 的余弦 —

如果我们将三角形的两边 b 和 c 看成是两个向量,那么上述公式等价于

其中分母表示两个向量 b 和 c 的长度,分子表示两个向量的内积。举一个具体的例子,假如新闻 X 和新闻 Y 对应向量分别是
x1,x2,…,x64000 和
y1,y2,…,y64000,
那么它们夹角的余弦等于,

当两条新闻向量夹角的余弦等于一时,这两条新闻完全重复(用这个办法可以删除重复的网页);当夹角的余弦接近于一时,两条新闻相似,从而可以归成一类;夹角的余弦越小,两条新闻越不相关。

我们在中学学习余弦定理时,恐怕很难想象它可以用来对新闻进行分类。在这里,我们再一次看到数学工具的用途。

Php比较字符串相似度函数的利用

Reference: http://www.piaoyi.org/php/php-similar_text.html

做信息发布类网站的站长大多数要遇到很多用户发布一模一样的帖子,以增加自身信息的曝光率,而作为网站管理员来说,除了利用cookies、IP限制等技术外,我们还可以利用PHP自身带的similar_text函数来判断用户发帖内容的相似度。
similar_text() 函数计算两个字符串的匹配字符的数目,也可以计算两个字符串的相似度(以百分比计)。
啥话也不说了,看代码:
<?php
require('conn.php');
$sql="select title from content order by id desc limit 20"; //判断标题相似度
$result=mysql_query($sql,$conn);
$cf=0;
while($row=mysql_fetch_array($result)){
similar_text($row['title'], $title, $percent); //比较相似度 存放于$percent
if($percent>90){$cf=1;break;} //飘易注:相似度高于90% 则判断重复
}
if($cf==1){
echo "<SCRIPT language=JavaScript>alert('抱歉!禁止发布重复信息!');";
echo "this.location.href='vbscript:history.back()';</SCRIPT>";
mysql_close();
exit();
}
?>
这段代码非常有用,其中title字段可以扩展成其他字段,如 content 字段,也一样的比较相似度。PHP的函数库太强大了。

标题去重 如何快速判断两个字符串的相似度

http://obmem.info/?p=212

之所以需要这个是因为采集器需要区别重复信息
后来发现用电话号码来区分就足以,呵呵

判断两个字符串的相似度很容易,关键是如何提高速度。在搜索引擎中,往往有上百万的网页,怎么去重。速度最快。下面用一个hash的办法来快速计算相似度。

首先,我们用hash的方法把一个字符串变为一个整数数组:

void hashString(const string &amp; buf, set &amp; ret)
…{
for(int i = 0; i &lt; buf.length() - 4; ++i)
…{
string tmp;
tmp += buf[i];
tmp += buf[i+1];
tmp += buf[i+2];
tmp += buf[i+3];
ret.insert(hash(tmp));
}
}

相当于每4个字节把字符串hash成一个整数存起来。

那么如果我们有两个字符串 a, b
我们首先把它们hash成两个集合sa,sb

假设 sa sb的交集有 k个元素
那么相似度就可以定义为

k / max(|sa|,|sb|)

然后给定一个阈值就可以去重了。

这个方法特点是效果比较好,速度很快。