文本比较算法--LD算法(C++实现)

标签: 文本 算法 ld | 发表时间:2012-10-25 09:39 | 作者:xiaoxiong5227
出处:http://blog.csdn.net

在日常应用中,文本比较是一个比较常见的问题。文本比较算法也是一个老生常谈的话题。

  文本比较的核心就是比较两个给定的文本(可以是字节流等)之间的差异。目前,主流的比较文本之间的差异主要有两大类。一类是基于编辑距离 (Edit Distance)的,例如LD算法。一类是基于最长公共子串的(Longest Common Subsequence),例如Needleman/Wunsch算法等。

  LD算法(Levenshtein Distance)又成为编辑距离算法(Edit Distance)。他是以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B,那么操作的过程的次数表示两个字符串的差异。

  例如:字符串A:kitten如何变成字符串B:sitting。

    第一步:kitten——》sitten。k替换成s

    第二步:sitten——》sittin。e替换成i

    第三步:sittin——》sitting。在末尾插入g

  故kitten和sitting的编辑距离为3

 

  定义说明:

  LD(A,B)表示字符串A和字符串B的编辑距离。很显然,若LD(A,B)=0表示字符串A和字符串B完全相同

  Rev(A)表示反转字符串A

  Len(A)表示字符串A的长度

  A+B表示连接字符串A和字符串B

  

  有下面几个性质:

  LD(A,A)=0

  LD(A,"")=Len(A)

  LD(A,B)=LD(B,A)

  0≤LD(A,B)≤Max(Len(A),Len(B))

  LD(A,B)=LD(Rev(A),Rev(B))

  LD(A+C,B+C)=LD(A,B)

  LD(A+B,A+C)=LD(B,C)

  LD(A,B)≤LD(A,C)+LD(B,C)(注:像不像“三角形,两边之和大于第三边”)

  LD(A+C,B)≤LD(A,B)+LD(B,C)

 

  为了讲解计算LD(A,B),特给予以下几个定义

  A=a 1a 2……a N,表示A是由a 1a 2……a N这N个字符组成,Len(A)=N

  B=b 1b 2……b M,表示B是由b 1b 2……b M这M个字符组成,Len(B)=M

  定义LD(i,j)=LD(a 1a 2……a i,b 1b 2……b j),其中0≤i≤N,0≤j≤M

  故:  LD(N,M)=LD(A,B)

      LD(0,0)=0

      LD(0,j)=j

      LD(i,0)=i

 

  对于1≤i≤N,1≤j≤M,有公式一

  若a i=b j,则LD(i,j)=LD(i-1,j-1)

  若a i≠b j,则LD(i,j)=Min(LD(i-1,j-1),LD(i-1,j),LD(i,j-1))+1

 

  举例说明:A=GGATCGA,B=GAATTCAGTTA,计算LD(A,B)

  第一步:初始化LD矩阵  

 

LD算法矩阵
    G A A T T C A G T T A
  0 1 2 3 4 5 6 7 8 9 10 11
G 1                      
G 2                      
A 3                      
T 4                      
C 5                      
G 6                      
A 7                      

 

  第二步:利用上述的公式一,计算第一行

 

LD算法矩阵
    G A A T T C A G T T A
  0 1 2 3 4 5 6 7 8 9 10 11
G 1 0 1 2 3 4 5 6 7 8 9 10
G 2                      
A 3                      
T 4                      
C 5                      
G 6                      
A 7                      

 

  第三步,利用上述的公示一,计算其余各行 

LD算法矩阵
    G A A T T C A G T T A
  0 1 2 3 4 5 6 7 8 9 10 11
G 1 0 1 2 3 4 5 6 7 8 9 10
G 2 1 1 2 3 4 5 6 6 7 8 9
A 3 2 1 1 2 3 4 5 6 7 8 8
T 4 3 2 2 1 2 3 4 5 6 7 8
C 5 4 3 3 2 2 2 3 4 5 6 7
G 6 5 4 4 3 3 3 3 3 4 5 6
A 7 6 5 4 4 4 4 3 4 4 5 5

 

  则LD(A,B)=LD(7,11)=5


C++代码实现

#include <iostream>
#define N 100
using namespace std;

int min(int a,int b,int c)
{
	return (a<b?a:b)<c?(a<b?a:b):c;
}

int LD(char pa[],char pb[],int a_length,int b_length)
{
	int dis[N][N];
	for(int i=0;i<=a_length;i++)
		dis[i][0]=i;
	for(int j=1;j<=b_length;j++)
		dis[0][j]=j;
	for(i=1;i<=a_length;i++)
		for(j=1;j<=b_length;j++)
		{
			if(pa[i-1]==pb[j-1])
				dis[i][j]=dis[i-1][j-1];
			else
				dis[i][j]=min(dis[i-1][j],dis[i-1][j-1],dis[i][j-1])+1;
		}
	return dis[a_length][b_length];
}

void main()
{
	char a[]="GGATCGA";
	char b[]="GAATTCAGTTA";
	int distance=LD(a,b,7,11);
	cout<<"distance is "<<distance<<endl;
}


作者:xiaoxiong5227 发表于2012-10-25 10:09:03 原文链接
阅读:0 评论:0 查看评论

相关 [文本 算法 ld] 推荐:

文本比较算法--LD算法(C++实现)

- - CSDN博客推荐文章
在日常应用中,文本比较是一个比较常见的问题. 文本比较算法也是一个老生常谈的话题.   文本比较的核心就是比较两个给定的文本(可以是字节流等)之间的差异. 目前,主流的比较文本之间的差异主要有两大类. 一类是基于编辑距离 (Edit Distance)的,例如LD算法. 一类是基于最长公共子串的(Longest Common Subsequence),例如Needleman/Wunsch算法等.

[转][转]文本相似度算法

- - heiyeluren的blog(黑夜路人的开源世界)
来源: http://www.cnblogs.com/liangxiaxu/archive/2012/05/05/2484972.html. 1.信息检索中的重要发明TF-IDF. Term frequency即关键词词频,是指一篇文章中关键词出现的频率,比如在一篇M个词的文章中有N个该关键词,则.

[转载]基于贝叶斯算法的文本分类算法

- - 小蚊子乐园
原文地址: 基于贝叶斯算法的文本分类算法 作者: TBKKEN.     因为要做一个关于数据挖掘的算法应用PPT,虽然知道很多数据挖掘的算法怎么使用,但是需要讲解它们的原理,还真的需要耗费很多精力,之前做一个曲线拟合,已经发在博客里,现在做贝叶斯算法的基础原理. 分类是把一个事物分到某个类别中.

基于Density Based Selection 的文本摘要算法

- - CSDN博客互联网推荐文章
    文本摘要算法大意是提取出文章的主要信息,以一种较为概括的简短的方式表达整篇文章,在搜索领域会经常用到,前段时间,yahoo以3000W刀的价格收购了一家创业公司,该公司据说是以一种机器学习的方法来对新闻进行摘要,跟传统的推送完整新闻的方式不同,该公司是展示新闻的摘要给用户的,这里只是介绍下简单的摘要算法.

[转][转] 文本相似性算法Simhash原理及实践

- - heiyeluren的blog(黑夜路人的开源世界)
simhash(局部敏感哈希)的原理. simhash广泛的用于搜索领域中,也许在面试时你会经常遇到这样的问题,如果对抓取的网页进行排重,如何对搜索结果进行排重等等. jaccard相似度也是一种相似 算法,它的计算方式比较直观,就是sim(x,y)= (x∩y) / (x∪y),例如:.      若  S={a, d}, T={a, c, d} .

[原]PySpark NaiveBayes算法之中文文本分类测试

- - moxiaomomo的专栏
假设现在有N行文本,每行文本的第一列已经打好标签, Y 或 N, 用于标识该行文本是否包含敏感词汇;第二列之后的每一列是对某些句子或文本进行中文分词之后的词汇. N 朴素贝叶斯算法 是 生成模型 中 最经典 分类算法 之一 Y 这是 一条 包含 色情 的 语句. 我们现在用pyspark结合NaiveBayes分类算法来进行训练和测试,这个过程大概包括:.

Spark-mllib 文本特征提取算法 - CSDN博客

- -
Spark MLlib 提供三种文本特征提取方法,分别为TF-IDF、Word2Vec以及CountVectorizer,. 词频-逆向文件频率(TF-IDF)是一种在文本挖掘中广泛使用的特征向量化方法,它可以体现一个文档中词语在语料库中的重要程度. 词语由t表示,文档由d表示,语料库由D表示. 词频TF(t,,d)是词语t在文档d中出现的次数.

文本比较算法Ⅵ——用线性空间计算最大公共子序列(翻译贴)

- Bo - 博客园-首页原创精华区
  研究文本比较算法有一段时间了. 近日研读了《A Linear Space Algorithm for Computing Maximal Common Subsequences》(D.S.Hirschberg著). 很多其他的论文都会引用这篇论文,可见这篇论文的质量. 同时,该文作者D.S.Hirschberg也写了很多有关LCS的文章,也都是经典中的经典.

文本挖掘算法、热度识别体系:美味爱读是如何搭建个性化阅读架构的

- - PingWest
最近我在使用一款AVOS公司推出的个性化新闻类阅读产品—— 美味爱读,与其他产品相比,它推送的内容更加精确并具有时效性. 令人意外的是,这款产品本身并不在AVOS公司的产品计划中,而是由AVOS中国团队的四位工程师——孙宁、倪华杰、杨朝中和庄晓丹所提出的. 2011年4月,Youtube的两位创始人Chad Hurley和陈士骏从雅虎手中收购了书签网站 Delicious,在此基础上成立了AVOS公司.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.