编辑距离算法
㈠ 编辑距离的算法
比如要计算cafe和coffee的编辑距离。cafe→caffe→coffe→coffee
先创建一个6×8的表（cafe长度为4，coffee长度为6，各加2）
（1）： coffeecafe表1接着，在如下位置填入数字（表2）： coffee0123456c1a2f3e4表2从3,3格开始，开始计算。取以下三个值的最小值： 如果最上方的字符等于最左方的字符，则为左上方的数字。否则为左上方的数字+1。（对于3,3来说为0） 左方数字+1（对于3,3格来说为2） 上方数字+1（对于3,3格来说为2） 因此为格3,3为0（表3） coffee0123456c10a2f3e4表3循环操作，推出下表 取右下角，得编辑距离为3 动态规划经常被用来作为这个问题的解决手段之一。
整数 Levenshtein距离(字符串 str1[1..m], 字符串 str2[1..n])
//声明变量， d[i , j]用于记录str1[1...i]与str2[1..j]的Levenshtein距离
int d[0..m, 0..n]
//初始化
for i from 0 to m
d[i, 0] := i
for j from 0 to n
d[0, j] := j
//用动态规划方法计算Levenshtein距离
for i from 1 to m
for j from 1 to n
{
//计算替换操作的代价，如果两个字符相同，则替换操作代价为0，否则为1
if str1[i]== str2[j] then cost := 0
else cost := 1
//d[i,j]的Levenshtein距离，可以有
d[i, j] := minimum(
d[i-1, j] + 1, //在str1上i位置删除字符（或者在str2上j-1位置插入字符）
d[i, j-1] + 1, //在str1上i-1位置插入字符（或者在str2上j位置删除字符）
d[i-1, j-1] + cost // 替换操作
)
}
//返回d[m, n]
return d[m, n]
wikisource上有不同的编程语言的版本。
㈡ 如何计算大量字符串间的编辑距离
模拟构造一个（m + 1)行，（n+1）列的表格
每一次都是在前一次的计算结果下，得到当前的值
首先是三个特殊情况 用srcStr表示源字符串，dstStr 表示目标字符串
1) 两个空字符串的编辑距离D(srcStr, dstStr) = 0
2) 如果srcStr为空，dstStr不为空，则D(srcStr, dstStr) = dstStr.length(), 即在原空字符串上添加字符，形成dstStr
3) 如果dstStr为空，srcStr不为空，则D(srcStr, dstStr) = srcStr.length(), 及在源字符串上删除其所有字符，直至为空
㈢ [高分提问]关于编辑距离算法(也叫Edit Distance算法或者Levenshtein Distance算法)
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之中选一个差别最小的来当它的值. 所以要从左上到右下构造矩阵。
㈣ 最小编辑距离算法 怎么得到路径
用dp的方法，并在每一步记录一下是哪一步转移过来的
倒着找回去就可以了
用C++写了一发，有少许注释，供参考
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#defineMAX(a,b)((a)>(b)?(a):(b));
usingnamespacestd;
structPoint{
intx,y;
Point(intx=0,inty=0):x(x),y(y){}
};
/**************************************************/
//theoperator
structOperator{
inttype;
intto;
Operator(inttype=0,intto=0):type(type),to(to){}
/*
type0NoOpeartor
1Insertto
2Delete
3Change->to
*/
};
/**************************************************/
//newanddeletefor2Darray
template<classT>
T**new_2D_Array(intn,intm){
T**res=newT*[n];
res[0]=newT[n*m];
for(inti=1;i<n;i++)
res[i]=res[i-1]+m;
returnres;
}
template<classT>
voiddelete_2D_Array(T**src){
delete[]src[0];
delete[]src;
}
/**************************************************/
intget_eu(chari,charj){
returni==j?0:1;
}
/*dpformineditdistance*/
/**/
/**/
intmin_Edit_Dis(strings1,strings2,string&res,vector<Operator>&resop,vector<int>&respos){
intret=0,reti=-1,retj=-1,n=s1.size(),m=s2.size();
int**dp=new_2D_Array<int>(s1.size()+1,s2.size()+1);
Point**pre=new_2D_Array<Point>(s1.size()+1,s2.size()+1);
Operator**op=new_2D_Array<Operator>(s1.size()+1,s2.size()+1);
for(inti=0;i<n;i++){
for(intj=0;j<m;j++){
dp[i][j]=0;
pre[i][j]=Point(-1,-1);
}
}
dp[0][0]=0;
op[0][0]=Operator(0,'!');
for(inti=1;i<=n;i++){
dp[i][0]=i;
op[i][0]=Operator(2,64);
pre[i][0]=Point(i-1,0);
}
for(inti=1;i<=m;i++){
dp[0][i]=i;
op[0][i]=Operator(1,s2[i-1]);
pre[0][i]=Point(0,i-1);
}
pre[0][0]=Point(-1,-1);
for(inti=1;i<=n;i++){
for(intj=1;j<=m;j++){
dp[i][j]=dp[i-1][j]+1;
pre[i][j]=Point(i-1,j);
op[i][j]=Operator(2,64);
if(dp[i][j-1]+1<dp[i][j]){
dp[i][j]=dp[i][j-1]+1;
pre[i][j]=Point(i,j-1);
op[i][j]=Operator(1,s2[j-1]);
}
if(dp[i-1][j-1]+get_eu(s1[i-1],s2[j-1])<dp[i][j]){
dp[i][j]=dp[i-1][j-1]+get_eu(s1[i-1],s2[j-1]);
pre[i][j]=Point(i-1,j-1);
if(s1[i-1]==s2[j-1])
op[i][j]=Operator(0,'!');
else
op[i][j]=Operator(3,s2[j-1]);
}
}
}
ret=dp[n][m];
/*printpreopdp
printf("(%d,%d) ",reti,retj);
printf("");
for(inti=0;i<=m;i++)
if(i==0)printf("");
elseprintf("%5c",s2[i-1]);
printf(" ");
for(inti=0;i<=n;i++){
if(i==0)printf("");
elseprintf("%c",s1[i-1]);
for(intj=0;j<=m;j++){
printf("(%2d,%2d)",pre[i][j].x,pre[i][j].y);
}
cout<<endl;
}
printf("(%d,%d) ",reti,retj);
printf("");
for(inti=0;i<=m;i++)
if(i==0)printf("");
elseprintf("%5c",s2[i-1]);
printf(" ");
for(inti=0;i<=n;i++){
if(i==0)printf("");
elseprintf("%c",s1[i-1]);
for(intj=0;j<=m;j++){
printf("(%2d,%2c)",op[i][j].type,op[i][j].to);
}
cout<<endl;
}
printf("");
for(inti=0;i<=m;i++)
if(i==0)printf("");
elseprintf("%c",s2[i-1]);
printf(" ");
for(inti=0;i<=n;i++){
if(i==0)printf("");
elseprintf("%c",s1[i-1]);
for(intj=0;j<=m;j++){
printf("%2d",dp[i][j]);
}
cout<<endl;
}
*/
resop.clear();
respos.clear();
intcuri=n,curj=m;
/*togettheroad(includenullop)*/
while(curi!=-1){
resop.push_back(op[curi][curj]);
respos.push_back(curi-1);
inttmpi=pre[curi][curj].x;
curj=pre[curi][curj].y;
curi=tmpi;
}
returnret;
}
/*deletethenullop,andgetthestringofeachstep*/
/*Skill:
ChangeFormRighttoLeft,
*/
voidget_Recoder(stringsrc,vector<Operator>&op,vector<int>&pos,vector<string>&res){
res.clear();
res.push_back(src);
vector<Operator>tmpop;
vector<int>tmppos;
tmpop.clear();
tmppos.clear();
stringcurs=src;
charbuffer[2]={0,0};
for(inti=0;i<op.size();i++){
Operatorcurp=op[i];
intcurpos=pos[i];
if(curp.type==0)continue;
elseif(curp.type==1){
curs=curs.insert(curpos+1,1,curp.to);
res.push_back(curs);
}
elseif(curp.type==2){
curs=curs.erase(curpos,1);
res.push_back(curs);
}
elseif(curp.type==3){
curs[curpos]=curp.to;
res.push_back(curs);
}
tmppos.push_back(curpos);
tmpop.push_back(curp);
}
op.clear();
pos.clear();
for(inti=0;i<tmppos.size();i++){
op.push_back(tmpop[i]);
pos.push_back(tmppos[i]);
}
}
/*Printtheprocess*/
voidprintRecord(stringsrc,vector<Operator>&op,vector<int>&pos,vector<string>&road){
charoperatorList[4][15]={"GOAL","INSERT","DELETE","CHANGE"};
intspacesize=6;
for(inti=0;i<road.size();i++)
spacesize=MAX(spacesize,road[i].size());
for(inti=0;i<spacesize+32;i++)
printf("_");
/*
Pos:
kitten
0123456
*/
printf(" |%-*s|pos|operator|form|to| |",spacesize,"string");
for(inti=0;i<spacesize;i++)printf("-");
printf("------------------------------| ");
printf("|%-*s|/|SOURCE|/|/| ",spacesize,src.c_str());
for(inti=0;i<op.size();i++){
stringtmps=road[i];
Operatortop=op[i];
inttpos=pos[i];
printf("|%-*s|%4d|%s|%c|%c| ",spacesize,tmps.c_str(),tpos+(top.type==1?1:0),operatorList[top.type],(top.type==3||top.type==2)?src[tpos]:'/',(top.type==3||top.type==1)?top.to:('/'));
}
printf("|%-*s|/|TARGET|/|/| ",spacesize,road[road.size()-1].c_str());
for(inti=0;i<spacesize+32;i++)printf("-");
printf(" RoadFinished ");
}
intmain(){
stringA="kitten";
stringB="sitting";
stringC;
vector<Operator>op;
vector<int>pos;
vector<string>road;
intres=min_Edit_Dis(A,B,C,op,pos);
printf("Themineditdisis:%d ",res);
get_Recoder(A,op,pos,road);
printRecord(A,op,pos,road);
return0;
}
㈤ c语言 编辑距离算法 程序运行没问题 就是字符串长了会溢出 求修改
方法1:把要删除的字符后面的字符依次前移一位覆盖前面的字符即可.
方法2:建立另一个字符数组,将要删除的字符之后的字符复制到这个新数组,然后再将新数组中的字符复制到原数组中从要删除的字符开始的位置即可.
㈥ levenshtein — 计算两个字符串之间的编辑距离
总结后的知识希望能帮到你！
函数名：levenshtein
(PHP 4 >= 4.0.1, PHP 5, PHP 7, PHP 8)
levenshtein — 计算两个字符串之间的编辑距离
说明
levenshtein ( string $str1 , string $str2 ) : int
levenshtein ( string $str1 , string $str2 , int $cost_ins , int $cost_rep , int $cost_del ) : int
编辑距离，是指两个字串之间，通过替换、插入、删除等操作将字符串str1转换成str2所需要操作的最少字符数量。 该算法的复杂度是 O(m*n)，其中 n 和 m 分别是str1 和str2的长度 （当和算法复杂度为O(max(n,m)**3)的similar_text()相比时，此函数还是相当不错的，尽管仍然很耗时。）。
在最简单的形式中，该函数只以两个字符串作为参数，并计算通过插入、替换和删除等操作将str1转换成str2所需要的操作次数。
第二种变体将采用三个额外的参数来定义插入、替换和删除操作的次数。此变体比第一种更加通用和适应，但效率不高。
参数
str1
求编辑距离中的其中一个字符串
str2
求编辑距离中的另一个字符串
cost_ins
定义插入次数
cost_rep
定义替换次数
cost_del
定义删除次数
返回值
此函数返回两个字符串参数之间的编辑距离，如果其中一个字符串参数长度大于限制的255个字符时，返回-1。
㈦ 编辑距离问题的动态规划算法
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int _Min(int a,int b,int c)
{
int min=a;
if (b <min)
min=b;
if(c <min)
min=c;
return min;
}
int ComputeDistance(char s[],char t[])
{
int n = strlen(s);
int m = strlen(t);
//int d[][] = new int[n + 1, m + 1]; // matrix
int **d = (int **)malloc((n+1) * sizeof(int *));
for(int i=0; i<=n; ++i)
{
d[i] = (int *)malloc((m+1) * sizeof(int));
}
// Step 1
if (n == 0)
{
return m;
}
if (m == 0)
{
return n;
}
// Step 2
for (int i = 0; i <= n; i++)
{
d[i][0] =i;
}
for (int j = 0; j <= m; d[0][j] = j++)
{
d[0][j] =j;
}
// Step 3
for (int i = 1; i <= n; i++)
{
//Step 4
for (int j = 1; j <= m; j++)
{
// Step 5
int cost = (t[j-1] == s[i-1]) ? 0 : 1;
// Step 6
d[i][j] = _Min(d[i-1][j]+1, d[i][j-1]+1,d[i-1][j-1]+cost);
}
}
// Step 7
return d[n][m];
}
int main(int argc, char *argv[])
{
char a[9999];
char b[9999];
printf("请输入字符串1\n");
scanf("%s",&a);
printf("请输入字符串2\n");
scanf("%s",&b);
int result= ComputeDistance(a,b);
printf("%d\n",result);
system("PAUSE");
return 0;
}
////////////////////
Refrence : Dynamic Programming Algorithm (DPA) for Edit-Distance
编辑距离
关于两个字符串s1,s2的差别，可以通过计算他们的最小编辑距离来决定。
所谓的编辑距离: 让s1和s2变成相同字符串需要下面操作的最小次数。
1. 把某个字符ch1变成ch2
2. 删除某个字符
3. 插入某个字符
例如 s1 = “12433” 和s2=”1233”;
则可以通过在s2中间插入4得到12433与s1一致。
即 d(s1,s2) = 1 (进行了一次插入操作)
编辑距离的性质
计算两个字符串s1+ch1, s2+ch2的编辑距离有这样的性质:
1. d(s1,””) = d(“”,s1) = |s1| d(“ch1”,”ch2”) = ch1 == ch2 ? 0 : 1;
2. d(s1+ch1,s2+ch2) = min( d(s1,s2)+ ch1==ch2 ? 0 : 1 ,
d(s1+ch1,s2),
d(s1,s2+ch2) );
第一个性质是显然的。
第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法。
于是对ch1,ch2可能的操作只有
1. 把ch1变成ch2
2. s1+ch1后删除ch1 d = (1+d(s1,s2+ch2))
3. s1+ch1后插入ch2 d = (1 + d(s1+ch1,s2))
对于2和3的操作可以等价于:
_2. s2+ch2后添加ch1 d=(1+d(s1,s2+ch2))
_3. s2+ch2后删除ch2 d=(1+d(s1+ch1,s2))
因此可以得到计算编辑距离的性质2。
复杂度分析
从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记，并假设两个串长度都为 n )
可以看到，该问题的复杂度为指数级别 3 的 n 次方，对于较长的串，时间上是无法让人忍受的。
分析: 在上面的结构中，我们发现多次出现了 (n-1,n-1), (n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。
动态规划求解
首先为了避免重复计算子问题，添加两个辅助数组。
一. 保存子问题结果。
M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
二. 保存字符之间的编辑距离.
E[ |s1|, |s2| ] , 其中 E[ i, j ] = s[i] = s[j] ? 0 : 1
三. 新的计算表达式
根据性质1得到
M[ 0,0] = 0;
M[ s1i, 0 ] = |s1i|;
M[ 0, s2j ] = |s2j|;
根据性质2得到
M[ i, j ] = min( m[i-1,j-1] + E[ i, j ] ,
m[i, j-1] ,
m[i-1, j] );
复杂度
从新的计算式看出，计算过程为
i=1 -> |s1|
j=1 -> |s2|
M[i][j] = ……
因此复杂度为 O( |s1| * |s2| ) ，如果假设他们的长度都为n，则复杂度为 O(n^2)
㈧ 编辑距离算法
编辑距离是3，楼主看一下这篇博文：
http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html
也附有代码，可以试运行一下，动态规划求解
㈨ 编辑距离的应用
最小编辑距离通常作为一种相似度计算函数被用于多种实际应用中，详细如下： （特别的，对于中文自然语言处理，一般以词为基本处理单元） DNA分析：基因学的一个主要主题就是比较 DNA 序列并尝试找出两个序列的公共部分。如果两个 DNA 序列有类似的公共子序列，那么这些两个序列很可能是同源的。在比对两个序列时，不仅要考虑完全匹配的字符，还要考虑一个序列中的空格或间隙（或者，相反地，要考虑另一个序列中的插入部分）和不匹配，这两个方面都可能意味着突变（mutation）。在序列比对中，需要找到最优的比对（最优比对大致是指要将匹配的数量最大化，将空格和不匹配的数量最小化）。如果要更正式些，可以确定一个分数，为匹配的字符添加分数、为空格和不匹配的字符减去分数。 全局序列比对尝试找到两个完整的序列 S1和 S2之间的最佳比对。以下面两个 DNA 序列为例：
S1= GCCCTAGCG
S2= GCGCAATG
如果为每个匹配字符一分，一个空格扣两分，一个不匹配字符扣一分，那么下面的比对就是全局最优比对：
S1'= GCCCTAGCG
S2'= GCGC-AATG
连字符（-）代表空格。在 S2'中有五个匹配字符，一个空格（或者反过来说，在 S1'中有一个插入项），有三个不匹配字符。这样得到的分数是 (5 * 1) + (1 * -2) + (3 * -1) = 0，这是能够实现的最佳结果。
使用局部序列比对，不必对两个完整的序列进行比对，可以在每个序列中使用某些部分来获得最大得分。使用同样的序列 S1和 S2，以及同样的得分方案，可以得到以下局部最优比对 S1''和 S2''：
S1 = GCCCTAGCG
S1''= GCG
S2''= GCG
S2 = GCGCAATG
这个局部比对的得分是 (3 * 1) + (0 * -2) + (0 * -1) = 3。 拼写纠错（Spell Correction）：又拼写检查（Spell Checker），将每个词与词典中的词条比较，英文单词往往需要做词干提取等规范化处理，如果一个词在词典中不存在，就被认为是一个错误，然后试图提示N个最可能要输入的词——拼写建议。常用的提示单词的算法就是列出词典中与原词具有最小编辑距离的词条。 这里肯定有人有疑问：对每个不在词典中的词（假如长度为len）都与词典中的词条计算最小编辑距离，时间复杂度是不是太高了？的确，所以一般需要加一些剪枝策略，如： 因为一般拼写检查应用只需要给出Top-N的纠正建议即可（N一般取10），那么我们可以从词典中按照长度依次为len、len-1、len+1、len-2、len-3、...的词条比较； 限定拼写建议词条与当前词条的最小编辑距离不能大于某个阈值； 如果最小编辑距离为1的候选词条超过N后，终止处理； 缓存常见的拼写错误和建议，提高性能。 命名实体抽取（Named Entity Extraction）：由于实体的命名往往没有规律，如品牌名，且可能存在多种变形、拼写形式，如“IBM”和“IBM Inc.”，这样导致基于词典完全匹配的命名实体识别方法召回率较低，为此，我们可以使用编辑距离由完全匹配泛化到模糊匹配，先抽取实体名候选词。 具体的，可以将候选文本串与词典中的每个实体名进行编辑距离计算，当发现文本中的某一字符串的编辑距离值小于给定阈值时，将其作为实体名候选词；获取实体名候选词后，根据所处上下文使用启发式规则或者分类的方法判定候选词是否的确为实体名。 实体共指（Entity Coreference）：通过计算任意两个实体名之间的最小编辑距离判定是否存在共指关系？如“IBM”和“IBM Inc.”, "Stanford President John Hennessy "和"Stanford University President John Hennessy"。 机器翻译（Machine Translation）： 识别平行网页对：由于平行网页通常有相同或类似的界面结构，因此平行网页在HTML结构上应该有很大近似度。首先将网页的HTML标签抽取出来，连接成一个字符串，然后用最小编辑距离考察两个字符串的近似度。实际中，此策略一般与文档长度比例、句对齐翻译模型等方法结合使用，以识别最终的平行网页对。 自动评测：首先存储机器翻译原文和不同质量级别的多个参考译文，评测时把自动翻译的译文对应到与其编辑距离最小的参考译文上，间接估算自动译文的质量，如下图所示： 字符串核函数（String Kernel）：最小编辑距离作为字符串之间的相似度计算函数，用作核函数，集成在SVM中使用。
㈩ 相似度算法 称编辑距离算法 如何解决比较 1333333333和133 的问题
你应该再仔细看看别人的原代码哦，在选择最小值的时候，你的三选一的三的内容是错误的，按你的代码应该是：
diverdiff[col+1][row+1]=divermin(diverdiff[col][row]+diff,diverdiff[col][row+1]+1,diverdiff[col+1][row]+1);