- 浏览: 3361709 次
- 性别:
- 来自: 珠海
文章分类
- 全部博客 (1633)
- Java (250)
- Android&HTML5 (111)
- Struts (10)
- Spring (236)
- Hibernate&MyBatis (115)
- SSH (49)
- jQuery插件收集 (55)
- Javascript (145)
- PHP (77)
- REST&WebService (18)
- BIRT (27)
- .NET (7)
- Database (105)
- 设计模式 (16)
- 自动化和测试 (19)
- Maven&Ant (43)
- 工作流 (36)
- 开源应用 (156)
- 其他 (16)
- 前台&美工 (119)
- 工作积累 (0)
- OS&Docker (83)
- Python&爬虫 (28)
- 工具软件 (157)
- 问题收集 (61)
- OFbiz (6)
- noSQL (12)
最新评论
-
HEZR曾嶸:
你好博主,这个不是很理解,能解释一下嘛//左边+1,上边+1, ...
java 两字符串相似度计算算法 -
天使建站:
写得不错,可以看这里,和这里的这篇文章一起看,有 ...
jquery 遍历对象、数组、集合 -
xue88ming:
很有用,谢谢
@PathVariable映射出现错误: Name for argument type -
jnjeC:
厉害,困扰了我很久
MyBatis排序时使用order by 动态参数时需要注意,用$而不是# -
TopLongMan:
非常好,很实用啊。。
PostgreSQL递归查询实现树状结构查询
http://itindex.net/detail/46929-java-%E5%AD%97%E7%AC%A6%E4%B8%B2-%E7%9B%B8%E4%BC%BC
Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明,用他的名字命名。不会拼读,可以叫它edit distance(编辑距离)。
原理很简单,就是返回将第一个字符串转换(删除、插入、替换)成第二个字符串的编辑次数。次数越少,意味着字符串相似度越高
Levenshtein distance可以用来:
Spell checking(拼写检查)
Speech recognition(语句识别)
DNA analysis(DNA分析)
Plagiarism detection(抄袭检测)
LD用m*n的矩阵存储距离值。算法大概过程:
Demo1:
Demo2:
Levenshtein distance最先是由俄国科学家Vladimir Levenshtein在1965年发明,用他的名字命名。不会拼读,可以叫它edit distance(编辑距离)。
原理很简单,就是返回将第一个字符串转换(删除、插入、替换)成第二个字符串的编辑次数。次数越少,意味着字符串相似度越高
Levenshtein distance可以用来:
Spell checking(拼写检查)
Speech recognition(语句识别)
DNA analysis(DNA分析)
Plagiarism detection(抄袭检测)
LD用m*n的矩阵存储距离值。算法大概过程:
Demo1:
/** * 编辑距离的两字符串相似度 * * @author jianpo.mo */ public class SimilarityUtil { private static int min(int one, int two, int three) { int min = one; if(two < min) { min = two; } if(three < min) { min = three; } return min; } public static int ld(String str1, String str2) { int d[][]; //矩阵 int n = str1.length(); int m = str2.length(); int i; //遍历str1的 int j; //遍历str2的 char ch1; //str1的 char ch2; //str2的 int temp; //记录相同字符,在某个矩阵位置值的增量,不是0就是1 if(n == 0) { return m; } if(m == 0) { return n; } d = new int[n+1][m+1]; for(i=0; i<=n; i++) { //初始化第一列 d[i][0] = i; } for(j=0; j<=m; j++) { //初始化第一行 d[0][j] = j; } for(i=1; i<=n; i++) { //遍历str1 ch1 = str1.charAt(i-1); //去匹配str2 for(j=1; j<=m; 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[n][m]; } public static double sim(String str1, String str2) { int ld = ld(str1, str2); return 1 - (double) ld / Math.max(str1.length(), str2.length()); } public static void main(String[] args) { String str1 = "chenlb.blogjava.net"; String str2 = "chenlb.javaeye.com"; System.out.println("ld="+ld(str1, str2)); System.out.println("sim="+sim(str1, str2)); } }
Demo2:
public class LevenshteinDistance { public static void main(String[] args){ String str1 = "i5rrrvan1"; String str2 = "ittvan2"; System.out.println("字符串1 {0}:"+str1); System.out.println("字符串2 {0}:"+str2); System.out.println("相似度 {0} %:"+ new LevenshteinDistance().LevenshteinDistancePercent(str1, str2) * 100); } private int LowerOfThree(int first, int second, int third) { int min = Math.min(first, second); return Math.min(min, third); } private int Levenshtein_Distance(String str1, String str2) { int[][] Matrix; int n = str1.length(); int m = str2.length(); int temp = 0; char ch1; char ch2; int i = 0; int j = 0; if (n == 0) { return m; } if (m == 0) { return n; } Matrix = new int[n + 1][ m + 1]; for (i = 0; i <= n; i++) { //初始化第一列 Matrix[i][ 0] = i; } for (j = 0; j <= m; j++) { //初始化第一行 Matrix[0][j] = j; } for (i = 1; i <= n; i++) { ch1 = str1.charAt(i - 1); for (j = 1; j <= m; j++) { ch2 = str2.charAt(j-1); if (ch1==ch2) { temp = 0; } else { temp = 1; } Matrix[i][j] = LowerOfThree(Matrix[i - 1][ j] + 1, Matrix[i][ j - 1] + 1, Matrix[i - 1][j - 1] + temp); } } for (i = 0; i <= n; i++) { for (j = 0; j <= m; j++) { System.out.println(" {0} :"+Matrix[i][j]); } System.out.println(""); } return Matrix[n][ m]; } public double LevenshteinDistancePercent(String str1, String str2) { //int maxLenth = str1.Length > str2.Length ? str1.Length : str2.Length; int val = Levenshtein_Distance(str1, str2); return 1 - (double)val / Math.max(str1.length(), str2.length()); } }
评论
1 楼
HEZR曾嶸
2018-08-28
你好博主,这个不是很理解,能解释一下嘛
//左边+1,上边+1, 左上角+temp取最小
d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+temp);
//左边+1,上边+1, 左上角+temp取最小
d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+temp);
发表评论
-
Java Comparable和Comparator
2016-06-26 08:52 654http://my.oschina.net/android52 ... -
Java集合框架之fastutil & koloboke
2016-06-23 14:04 2409Java集合框架之fastutil http://rensan ... -
ehcache 分布式支持
2016-06-05 22:26 1055原文 http://my.oschina.net/glenxu ... -
Intellij IDEA插件开发入门
2016-05-26 11:42 2839原文: http://blog.csdn.net/dc_726 ... -
阿里巴巴Druid数据源的配置与使用
2016-05-24 17:42 1494http://my.oschina.net/wjme/blog ... -
mysql中间件研究(Atlas,cobar,TDDL), 分库分表插件
2016-05-09 14:15 3387http://www.guokr.com/blog/47576 ... -
Java集合: Queue和Deque
2016-05-09 09:49 1825Queue http://my.oschina.net/kev ... -
使用gzip优化web应用(filter实现)
2016-05-07 01:45 997使用gzip优化web应用(filter实现) http:// ... -
Byteman 3.0.5 发布,Java 字节码注入工具
2016-04-23 10:29 1723Byteman 3.0.5 发布,Java 字 ... -
RandomStringUtils的说明和生成随机汉字
2016-04-20 15:21 1315更多参考: http://my.oschina.net/wil ... -
通过IP地址获取地理位置
2016-04-20 15:19 854http://my.oschina.net/githubhty ... -
Java编程中使用正则表达式过滤非数字字符串
2016-04-14 13:51 1673/** * * @param str ... -
非对称加密DH算法,DH代码实现
2016-04-13 11:33 1315RSA算法原理(一)http:// ... -
企业支付宝账号开发接口教程
2016-03-31 14:52 1192企业支付宝账号开发接口教程--JAVA-UTF-8(实际操作- ... -
java double类型数据操作工具类
2016-03-28 17:36 1176http://my.oschina.net/yxwblog/b ... -
double转换到BigDecimal
2016-03-28 17:11 1501BigDecimal b = new BigDecimal(d ... -
Java 生成好看的验证码
2016-03-23 10:52 3303http://www.oschina.net/code/sni ... -
Linux环境安装配置Swftools
2016-03-22 21:01 1048http://tetop.blog.51cto.com/188 ... -
java压缩与解压缩文件
2016-03-20 22:03 1428http://www.oschina.net/code/sni ... -
java图像压缩
2016-03-19 23:20 917http://my.oschina.net/686991/bl ...
相关推荐
Java 实现推荐系统 两个字符串 余弦相似度 算法。
java 计算字符串相似度
主要介绍了java字符串相似度算法,是Java实现比较典型的算法,具有一定参考借鉴价值,需要的朋友可以参考下
Java之词义相似度计算(语义识别、词语情感趋势、词林相似度、拼音相似度、概念相似度、字面相似度)
,用于计算两个字符串之间的归一化距离或相似度分数。 0.0 分表示两个字符串绝对不相似,1.0 表示绝对相似(或相等)。 介于两者之间的任何内容都表示两个字符串的相似程度。例子在这个简单的例子中,我们想要计算...
Java字符串相似度 一个实现不同字符串相似度和距离度量的库。 当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看下面的摘要表以获取完整列表... 下载 ...
相似度是由一系列算法组成的Java版相似度计算工具包,目标是传播自然语言处理中相似度计算方法。相似度是工具实用,性能高效,架构清晰,语料时新,可自定义的特点。 相似性提供下列功能:词相似度计算词林编码法...
simhash算法对字符串计算权重时,对中文要做特殊操作,及先分词,请自行下载sanford中文分词jar包及中文分词库
提出采用模式匹配中的基于字符串匹配的相似度算法,通过添加、删除、替换等操作还原文档,并计算文档间的相似距离,根据相似距离获得文档相似度,从而判断文档的抄袭比例。反抄袭算法的研究实现为遏制进一步恶化的抄袭...
java上机试题 非常经典 SQL 编程 不限制语言于不同的字符串,我们希望能有办法判断相似程度,我们定义了一套操作方法来把两个不相同的字符串变得...给定任意两个字符串,你是否能写出一个算法来计算出它们的相似度呢?
字符串相似度.NET Java字符串相似性的.NET端口: : 一个实现不同字符串相似度和距离度量的库。 当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看下面的...
1、解压下载的CollaborativeFilteringBasedText压缩文件 2、操作系统中需装java jdk1.7或者以上版本 3、点击start.bat,在运行过程中,输出文本之间的距离和相似度
Levenshtein Distance算法可以看作动态规划 它的思路就是从两个字符串的左边开始比较 记录已经比较过的子串相似度 实际上叫做距离 然后进一步得到下一个字符位置时的相似度 用下面的例子: GUMBO和GAMBOL 当算到矩阵D...
简单的代码相似度检测,使用Java编写。 算法步骤: S1:剔除程序中所有注释、空行、空格 S2:剔除程序中所有变量、函数名 ...S4:两个特征串之间,使用字符串适量距离(Levenshtein Distance)计算相似度。
Google发明的的文本去重算法,适合于大批量文档的相似度计算。 流程介绍 simhash是由 Charikar 在2002年提出来的,为了便于理解尽量不使用数学公式,分为这几步: 1、分词,把需要判断文本分词形成这个文章的特征...
D:\002 我的工具类\007 字符串\StringUtils.java D:\002 我的工具类\008 校验 D:\002 我的工具类\008 校验\一起使用 D:\002 我的工具类\008 校验\一起使用\008 校验 D:\002 我的工具类\008 校验\一起使用\008 校验\...
通用的Java工具类主要包括基础工具类(时间、正则表达式、字符串、随机数等等),excel解析生成、word解析生成、 文件操作、图片操作、敏感字、加解密等等。 通用工具库 分词 togoll/jcseg 基于mmseg算法的一个轻量...
这里的关键技术叫做感知哈希算法(Perceptual hash algorithm),它的作用是对每张图片生成一个"指纹"(fingerprint)字符串,然后比较不同图片的指纹。结果越接近,就说明图片越相似。下面是一个最简单的实现: 第...