- 浏览: 2002602 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (651)
- ACE (35)
- BAT (9)
- C/C++ (116)
- fast-cgi (14)
- COM (27)
- python (59)
- CGI (4)
- C# (2)
- VC (84)
- DataBase (29)
- Linux (96)
- P2P (6)
- PHP (15)
- Web (6)
- Memcached (7)
- IME输入法 (11)
- 设计模式 (2)
- 搜索引擎 (1)
- 个人情感 (4)
- 笔试/面试 (3)
- 一亩三分地 (33)
- 历史 (2)
- 地理 (1)
- 人物 (3)
- 经济 (0)
- 不仅仅是笑哦 (43)
- 小故事大道理 (2)
- http://www.bjdsmyysjk120.com/ (0)
- http://www.bjdsmyy120.com/ (0)
- 它山之石可以攻玉 (15)
- 大学生你关注些什么 (28)
- 数据恢复 (1)
最新评论
-
luokaichuang:
这个规范里还是没有让我明白当浏览器上传文件时,STDIN的消息 ...
FastCGI规范 -
effort_fan:
好文章!学习了,谢谢分享!
com技术简介 -
vcell:
有错误os.walk(strPath)返回的已经是全部的文件和 ...
通过python获取目录的大小 -
feifeigd:
feifeigd 写道注意:文章中的CPP示例第二行 #inc ...
ATL入门:利用ATL编写简单的COM组件 -
feifeigd:
注意:文章中的CPP示例第二行 #include " ...
ATL入门:利用ATL编写简单的COM组件
昨天论坛看到的,简单写了一下
题目: 一个字符串可以通过增加一个字符,删除一个字符,替换一个字符得到另外一个字符串,假设,我们把从字符串A转换成字符串B,前面3种操作所执行的最少次数称为AB相似度
如 abc adc 度为 1
ababababa babababab 度为 2
abcd acdb 度为2
字符串相似度算法可以使用 Levenshtein Distance算法(中文翻译:编辑距离算法) 这算法是由俄国科学家Levenshtein提出的。其步骤
Step
Description
1
Set n to be the length of s.
Set m to be the length of t.
If n = 0, return m and exit.
If m = 0, return n and exit.
Construct a matrix containing 0..m rows and 0..n columns.
2
Initialize the first row to 0..n.
Initialize the first column to 0..m.
3
Examine each character of s (i from 1 to n).
4
Examine each character of t (j from 1 to m).
5
If s[i] equals t[j], the cost is 0.
If s[i] doesn't equal t[j], the cost is 1.
6
Set cell d[i,j] of the matrix equal to the minimum of:
a. The cell immediately above plus 1: d[i-1,j] + 1.
b. The cell immediately to the left plus 1: d[i,j-1] + 1.
c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost.
7
After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m].
#include <iostream> #include <vector> #include <string> using namespace std; //算法 int ldistance(const string source,const string target) { //step 1 int n=source.length(); int m=target.length(); if (m==0) return n; if (n==0) return m; //Construct a matrix typedef vector< vector<int> > Tmatrix; Tmatrix matrix(n+1); for(int i=0; i<=n; i++) matrix[i].resize(m+1); //step 2 Initialize for(int i=1;i<=n;i++) matrix[i][0]=i; for(int i=1;i<=m;i++) matrix[0][i]=i; //step 3 for(int i=1;i<=n;i++) { const char si=source[i-1]; //step 4 for(int j=1;j<=m;j++) { const char dj=target[j-1]; //step 5 int cost; if(si==dj){ cost=0; } else{ cost=1; } //step 6 const int above=matrix[i-1][j]+1; const int left=matrix[i][j-1]+1; const int diag=matrix[i-1][j-1]+cost; matrix[i][j]=min(above,min(left,diag)); } }//step7 return matrix[n][m]; } int main(){ string s; string d; cout<<"source="; cin>>s; cout<<"diag="; cin>>d; int dist=ldistance(s,d); cout<<"dist="<<dist<<endl; } #include <iostream> #include <vector> #include <string> using namespace std; //算法 int ldistance(const string source,const string target) { //step 1 int n=source.length(); int m=target.length(); if (m==0) return n; if (n==0) return m; //Construct a matrix typedef vector< vector<int> > Tmatrix; Tmatrix matrix(n+1); for(int i=0; i<=n; i++) matrix[i].resize(m+1); //step 2 Initialize for(int i=1;i<=n;i++) matrix[i][0]=i; for(int i=1;i<=m;i++) matrix[0][i]=i; //step 3 for(int i=1;i<=n;i++) { const char si=source[i-1]; //step 4 for(int j=1;j<=m;j++) { const char dj=target[j-1]; //step 5 int cost; if(si==dj){ cost=0; } else{ cost=1; } //step 6 const int above=matrix[i-1][j]+1; const int left=matrix[i][j-1]+1; const int diag=matrix[i-1][j-1]+cost; matrix[i][j]=min(above,min(left,diag)); } }//step7 return matrix[n][m]; } int main(){ string s; string d; cout<<"source="; cin>>s; cout<<"diag="; cin>>d; int dist=ldistance(s,d); cout<<"dist="<<dist<<endl; }
发表评论
-
Berkeley DB 使用经验总结
2012-08-27 14:41 3032作者:陈磊 NoSQL是现在互联网Web2.0时代备受 ... -
嵌入式数据库系统Berkeley DB
2012-08-27 14:37 1480前言 UNIX/LINUX平台下的数据库种类非常多 ... -
C语言中标准输入流、标准输出流、标准错误输出流
2011-06-13 14:32 9205C语言中标准输入流、标准输出流、标准错误输出流 在 ... -
Rsync 实现原理
2011-05-12 20:06 8256Rsync 实现原理 前言 关于rsync的原始文档 ... -
c++简单的虚函数测试
2011-04-27 14:25 969#include <iostream> u ... -
C++文件行查找
2011-04-26 14:10 1355#include <iostream> # ... -
c++偏特化简单示例
2011-04-13 11:17 2109c++偏特化 // temp1.c ... -
GDB调试精粹及使用实例
2011-03-16 14:06 1087GDB调试精粹及使用实例 一:列文件清单 1. ... -
简单的ini文件解析
2011-02-12 16:36 1576int GetKeyVal(const string s ... -
scanf族函数高级用法
2011-01-25 16:00 2490如何解释 fscanf(fd,&quo ... -
使用scons替代makefile(1)
2011-01-25 11:58 3642早在多年前我刚开始接触linux下的C程序时,经常被makef ... -
使用scons替代makefile(2)
2011-01-25 11:57 3536本篇文章接着上一篇进一步介绍scons的使用方法,主要介绍静态 ... -
使用scons替代makefile(3)
2011-01-25 11:55 4777在上两篇文章中已经简单介绍了用scons编译库文件,可执行程序 ... -
C 支持动态添加测试数据的测试代码
2011-01-13 17:22 1081/下面的定义为了支持可扩增。 //当需要增加一个新的测试用列 ... -
Linux下Makefile的automake生成
2010-12-28 16:55 1051******************helloworld.c* ... -
SCons笔记(详细版)
2010-12-23 16:11 103851. 基本使用 SConstruct文件就功能而言相当于Ma ... -
scons 学习
2010-12-23 11:14 2115scons 学习 作者:Sam(甄峰) sam_code@h ... -
scons随笔
2010-12-22 20:20 4643scons随笔 Scons是新一代的软件构件工具,或者说ma ... -
Scons在linux下的安装和使用
2010-12-21 11:59 3203因为正在用的一个开源软件需要的Developm ... -
排列组合的实现
2010-12-20 12:41 1014简单算法: 从前往后(或者从后往前)每次交换一个位置。当存在 ...
相关推荐
NULL 博文链接:https://biansutao.iteye.com/blog/326008
Levenshtein:快速计算编辑距离以及字符串的相似度
C#,字符串相似度的莱文斯坦距离(Levenshtein Distance)算法与源代码 莱文斯坦距离(Levenshtein Distance)用于衡量两个字符串之间的相似度。 莱文斯坦距离以俄国科学家(Vladimir I. Levenshtein)命名,他于...
两个字符串的相似度算法实现——编辑距离之Levenshtein距离
Java字符串相似度 一个实现不同字符串相似度和距离度量的库。 当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看下面的摘要表以获取完整列表... 下载 ...
Strutil strutil提供了用于计算字符串相似度的字符串度量标准以及其他字符串实用程序功能。 完整文档可在以下找到: : 。安装 go get github.com/adrg/strutil字符串指标杰罗·温克勒史密斯·沃特曼·高图索伦森-...
python字符串相似度 tdebatty likeity的Python3.x实现 一个实现不同字符串相似度和距离度量的库。 当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看...
目前实现了十几种算法(包括 Levenshtein 编辑距离和兄弟姐妹、最长公共子序列、余弦相似度等)。 查看下面的汇总表以获取完整列表... 参数 返回 排序匹配 参数 返回 参数 返回 发行说明1.x 版本 麻省理工学院 ...
(换句话来说,就计算两个字符串的相似度,值越小相似度越高)。该实现采用了编辑距离算法,详见:###2、使用方法:使用源代码的话,从第1步开始。如果是直接使用二进制发布包的话,直接从第4步开始即可。1)下载本...
编辑距离(EditDistance)定义 编辑距离就是用来计算从原串(s)转换到目标串(t)所需要的最少的插入,删除和替换的数目,在NLP中...编辑距离的算法是首先由俄国科学家Levenshtein提出的,故又叫Levenshtein Distance。
Levenshtein Distance算法可以看作动态规划 它的思路就是从两个字符串的左边开始比较 记录已经比较过的子串相似度 实际上叫做距离 然后进一步得到下一个字符位置时的相似度 用下面的例子: GUMBO和GAMBOL 当算到矩阵D...
简单的代码相似度检测,使用Java编写。 算法步骤: S1:剔除程序中所有注释、空行、空格 S2:剔除程序中所有变量、函数名 ...S4:两个特征串之间,使用字符串适量距离(Levenshtein Distance)计算相似度。
字符串相似度.NET Java字符串相似性的.NET端口: : 一个实现不同字符串相似度和距离度量的库。 当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看下面的...
使用Levenshtein距离的Python和C ++快速模糊字符串匹配 •••描述RapidFuzz是适用于Python和C ++的快速字符串匹配库,它使用的字符串相似度计算。 但是,有两个方面使RapidFuzz与FuzzyWuzzy脱颖而出: 它已获得MIT...
欢迎来到TNAS寻求数据字符串之间的相似性模式 TNAS估计事物之间的相似性或相异性。 它将任何一组字符与任何其他一组字符进行比较,并估计一个或多个项目之间的相似度百分比。概要 TNAS信息库包含John W.Ratcliff和...