利用编辑距离(Edit Distance)计算两个字符串的相似度

标签: 利用 编辑距离 edit | 发表时间:2016-04-29 08:25 | 作者:InJavaWeTrust
出处:http://www.iteye.com

利用编辑距离(Edit Distance)计算两个字符串的相似度

 

        编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。

 

        例如将kitten一字转成sitting:

        sitten (k→s)
        sittin (e→i)
        sitting (→g)

        俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

 

        之前用jsoup做网络爬虫的时候用到了这个 来计算两个字符串的相似度,今天整理出来向Vladimir Levenshtein致敬。

 

/**
 * 编辑距离(Edit Distance)求字符串相似度
 * @author InJavaWeTrust http://injavawetrust.iteye.com
 *
 */
public class EditDistance {
	
	/**
     * 求三个数中最小的一个
     * @param one
     * @param two
     * @param three
     * @return
     */
	public int min(int one, int two, int three) {
		int min = one;
		if (two < min) {
			min = two;
		}
		if (three < min) {
			min = three;
		}
		return min;
	}

    /**
     * 求编辑距离(Edit Distance)
     * @param str1
     * @param str2
     * @return 编辑距离
     */
	public int editDistance(String str1, String str2) {
		int d[][]; // 矩阵
		int y = str1.length();
		int x = str2.length();
		char ch1; // str1的
		char ch2; // str2的
		int temp; // 记录相同字符,在某个矩阵位置值的增量,不是0就是1
		if (y == 0) {
			return x;
		}
		if (x == 0) {
			return y;
		}
		d = new int[y + 1][x + 1]; // 计算编辑距离二维数组
		for (int j = 0; j <= x; j++) { // 初始化编辑距离二维数组第一行
			d[0][j] = j;
		}
		for (int i = 0; i <= y; i++) { // 初始化编辑距离二维数组第一列
			d[i][0] = i;
		}
		for (int i = 1; i <= y; i++) { // 遍历str1
			ch1 = str1.charAt(i - 1);
			// 去匹配str2
			for (int j = 1; j <= x; j++) {
				ch2 = str2.charAt(j - 1);
				if (ch1 == ch2) {
					temp = 0;
				} else {
					temp = 1;
				}
				// 左边+1,上边+1, 左上角+temp取最小
				d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + temp);
			}
		}
		return d[y][x];
	}

    /**
     * 计算相似度
     * @param str1
     * @param str2
     * @return
     */
	public double similar(String str1, String str2) {
		int ed = editDistance(str1, str2);
		return 1 - (double) ed / Math.max(str1.length(), str2.length());
	}
	
	public static void main(String[] args) {
		String str1 = "1234";
		String str2 = "1254";
		System.out.println("字符串相似度: " + new EditDistance().similar(str1, str2));
	}
}

 

 运行结果:



 



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [利用 编辑距离 edit] 推荐:

利用编辑距离(Edit Distance)计算两个字符串的相似度

- - Java - 编程语言 - ITeye博客
利用编辑距离(Edit Distance)计算两个字符串的相似度.         编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数. 许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符. 一般来说,编辑距离越小,两个串的相似度越大.

编辑距离(Edit Distance | Levenshtein距离)

- - CSDN博客互联网推荐文章
编辑距离又称为Levenshtein距离,是指两个字符串之间,从一个字符串变成另一个字符串所需要的 最小编辑操作次数. 可以采用的编辑操作包括: 插入操作、替换操作和删除操作. 例如:字符串“a“ 与字符串 ”b“的编辑距离为1,只有一个替换操作. 将”kitten一字转成“sitting”的编辑距离为3:.

[记录]字符串相似度算法(编辑距离算法 Levenshtein Distance)

- - xilo's blog
在搞验证码识别的时候需要比较字符代码的相似度用到“编辑距离算法”,关于原理和C#实现做个记录. 编辑距离,又称Levenshtein距离(也叫做Edit Distance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数,如果它们的距离越大,说明它们越是不同. 许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符.

字幕編輯軟體Subtitle Edit的使用技巧

- - 簡睿隨筆
Subtitle Edit相較 AegiSub是比較少人使用的字幕編輯軟體,但是因為它仍持續在開發,因此我挑選了它做為我主要使用的字幕編輯工具. 本影片先介紹Subtitle Edit的安裝,再介紹快捷鍵的設定與語氣詞的刪除與替換,再說明使用上的一些小技巧,讓字幕的修改能更迅速、更有效率. 多重取代設定(Ctrl+Alt+M):加入要移除或變更的語氣詞.

java 两字符串相似度计算算法 (转)Levenshtein Distance编辑距离算法

- - 开源软件 - ITeye博客
Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明,用他的名字命名. 不会拼读,可以叫它edit distance(编辑距离). 原理很简单,就是返回将第一个字符串转换(删除、插入、替换)成第二个字符串的编辑次数. 次数越少,意味着字符串相似度越高 .

Komodo Edit – 免费跨平台文本编辑 | 小众软件 > 办公软件

- Coolxll - 小众软件
公广二狗每天切换于 Mac/Win/Linux 之间,刚习惯一种环境就换另一种,神经分裂的厉害. 在文本编辑方面,二狗用 Komodo Edit,不轻量不强大,但中规中矩该有的都有了,关键是免费且跨平台使用体验一致,减少精神病患风险. 下载: 官网 | 下载 | 来自小众软件. ©2011 Thruth for 小众软件 | 原文链接 | 17 留言 | 加入我们 | 投稿 | 订阅指南.

利用sockstunnel翻越

- - 0.618網絡空間
首先在你的linux vps上搭建python環境(一般來說,linux vps都已搭好了python 環境). 然後運行如下命令(假設你在/root下):. 這樣在/root/下,就生成了privkey.pem和cacert.pem. 修改sslserver.py裏的. keyfile="privkey.pem",為.

转角的空间利用

- Ivy - IDSOO
拐角的空间如果不充分利用似乎有一些浪费. 日本的设计工作室Torafu Architects设计的这个隔板巧妙地利用了拐角,搭建了一个可以放置物品的平台,设计实用、美观、大方.

旧灯泡的再利用

- Jimmy - 微奇生活
生活水平提高了,家家户户也用上了节能灯,那些废旧的白炽灯泡如何利用呢. 看看下面这些妙点子吧,可以种盆栽,做工艺品,还能用来养金鱼~~灯泡还会跳舞呢. 简洁的线圈灯:Coil Lamp. 微博:@新浪 | @腾讯     订阅:Google | 九点 | QQ | 鲜果 | 有道 | 邮箱.

[译]jboss漏洞利用

- - 互联网 - ITeye博客
原文地址:http://resources.infosecinstitute.com/jboss-exploitation/. JBoss Application Server是一个基于Jave EE的web应用服务器. 如果Jboss没有正确配置,它会允许攻击者进行各种恶意攻击. 由于JMX console可以通过端口8080远程访问,攻击者和恶意用户可以通过使用Jboss console中的DeploymentScanner功能部署他们自己的WAR(web archive)文件或shell脚本.