- 浏览: 14776 次
- 性别:
- 来自: 成都
最新评论
http://hxraid.iteye.com/blog/615469 【串和序列处理 2】字符串编辑距离算法 文章分类:综合技术 我们来看一个实际应用。现代搜索技术的发展很多以提供优质、高效的服务作为目标。比如说:baidu、google、sousou等知名全文搜索系统。当我们输入一个错误的query="Jave" 的时候,返回中有大量包含正确的拼写 "Java"的网页。当然这里面用到的技术绝对不会是我们今天讲的怎么简单。但我想说的是:字符串的相似度计算也是做到这一点的方法之一。 字符串编辑距离: 是一种字符串之间相似度计算的方法。给定两个字符串S、T,将S转换成T所需要的删除,插入,替换操作的数量就叫做S到T的编辑路径。而最短的编辑路径就叫做字符串S和T的编辑距离。 举个例子:S="eeba" T="abac" 我们可以按照这样的步骤转变:(1) 将S中的第一个e变成a;(2) 删除S中的第二个e;(3)在S中最后添加一个c; 那么S到T的编辑路径就等于3。当然,这种变换并不是唯一的,但如果3是所有变换中最小值的话。那么我们就可以说S和T的编辑距离等于3了。 动态规划解决编辑距离 动态规划(dynamic programming)是一种解决复杂问题最优解的策略。它的基本思路就是:将一个复杂的最优解问题分解成一系列较为简单的最优解问题,再将较为简单的的最优解问题进一步分解,直到可以一眼看出最优解为止。 动态规划算法是解决复杂问题最优解的重要算法。其算法的难度并不在于算法本身的递归难以实现,而主要是编程者对问题本身的认识是否符合动态规划的思想。现在我们就来看看动态规划是如何解决编辑距离的。 还是这个例子:S="eeba" T="abac" 。我们发现当S只有一个字符e、T只有一个字符a的时候,我们马上就能得到S和T的编辑距离edit(0,0)=1(将e替换成a)。那么如果S中有1个字符e、T中有两个字符ab的时候,我们是不是可以这样分解:edit(0,1)=edit(0,0)+1(将e替换成a后,在添加一个b)。如果S中有两个字符ee,T中有两个字符ab的时候,我们是不是可以分解成:edit(1,1)=min(edit(0,1)+1, edit(1,0)+1, edit(0,0)+f(1,1)). 这样我们可以得到这样一些动态规划公式: 如果i=0且j=0 edit(0, 0)=1 如果i=0且j>0 edit(0, j )=edit(0, j-1)+1 如果i>0且j=0 edit( i, 0 )=edit(i-1, 0)+1 如果i>0且j>0 edit(i, j)=min(edit(i-1, j)+1, edit(i,j-1)+1, edit(i-1,j-1)+f(i , j) ) 小注:edit(i,j)表示S中[0.... i]的子串 si 到T中[0....j]的子串t1的编辑距离。f(i,j)表示S中第i个字符s(i)转换到T中第j个字符s(j)所需要的操作次数,如果 s(i)==s(j),则不需要任何操作f(i, j)=0; 否则,需要替换操作,f(i, j)=1 。 这就是将长字符串间的编辑距离问题一步一步转换成短字符串间的编辑距离问题,直至只有1个字符的串间编辑距离为1。 编辑距离的实际应用 在信息检索领域的应用我们在文章开始的时候就提到了。另外,编辑距离在自然语言文本处理领域(NLP)中是计算字符串相似度的重要方法。一般而言,对于中文语句的相似度处理,我们很多时候都是将词作为一个基本操作单位,而不是字(字符)。 字符串编辑距离源代码 Java代码 收藏代码 1. package net.hr.algorithm.stroper; 2. /** 3. * 字符串编辑距离 4. * 5. * 这是一种字符串之间相似度计算的方法。 6. * 给定字符串S、T,将S转换T所需要的插入、删除、替代操作的数量叫做S到T的编辑路径。 7. * 其中最短的路径叫做编辑距离。 8. * 9. * 这里使用了一种动态规划的思想求编辑距离。 10. * 11. * @author heartraid 12. * 13. */ 14. public class StrEditDistance { 15. 16. /**字符串X*/ 17. private String strX=""; 18. /**字符串Y*/ 19. private String strY=""; 20. /**字符串X的字符数组*/ 21. private char[] charArrayX=null; 22. /**字符串Y的字符数组*/ 23. private char[] charArrayY=null; 24. 25. public StrEditDistance(String sa,String sb){ 26. this.strX=sa; 27. this.strY=sb; 28. } 29. /** 30. * 得到编辑距离 31. * @return 编辑距离 32. */ 33. public int getDistance(){ 34. charArrayX=strX.toCharArray(); 35. charArrayY=strY.toCharArray(); 36. return editDistance(charArrayX.length-1,charArrayY.length -1); 37. } 38. /** 39. * 动态规划解决编辑距离 40. * 41. * editDistance(i,j)表示字符串X中[0.... i]的子串 Xi 到字符串Y中[0....j]的子串Y1的编辑距离。 42. * 43. * @param i 字符串X第i个字符 44. * @param j 字符串Y第j个字符 45. * @return 字符串X(0...i)与字符串Y(0...j)的编辑距离 46. */ 47. private int editDistance(int i,int j){ 48. if(i==0&&j==0){ 49. //System.out.println("edit["+i+","+j+"]="+isModify (i,j)); 50. return isModify(i,j); 51. } 52. else if(i==0||j==0){ 53. if(j>0){ 54. //System.out.println("edit["+i+","+j+"]=edit["+i+" ,"+(j-1)+"]+1"); 55. if(isModify(i,j) == 0) return j; 56. return editDistance(i, j-1) + 1; 57. } 58. else{ 59. //System.out.println("edit["+i+","+j+"]=edit["+(i- 1)+","+j+"]+1"); 60. if(isModify(i,j) == 0) return i; 61. return editDistance(i-1,j)+1; 62. } 63. } 64. else { 65. //System.out.println("edit["+i+","+j+"]=min( edit["+(i-1)+","+j+"]+1,edit["+i+","+(j-1)+"]+1,ed it["+(i-1)+","+(j-1)+"]+isModify("+i+","+j+")"); 66. int ccc=minDistance(editDistance(i-1,j)+1,editDistance (i,j-1)+1,editDistance(i-1,j-1)+isModify(i,j)); 67. return ccc; 68. } 69. 70. } 71. /** 72. * 求最小值 73. * @param disa 编辑距离a 74. * @param disb 编辑距离b 75. * @param disc 编辑距离c 76. */ 77. private int minDistance(int disa,int disb,int disc){ 78. int dismin=Integer.MAX_VALUE; 79. if(dismin>disa) dismin=disa; 80. if(dismin>disb) dismin=disb; 81. if(dismin>disc) dismin=disc; 82. return dismin; 83. } 84. /** 85. * 单字符间是否替换 86. * 87. * isModify(i,j)表示X中第i个字符x(i)转换到Y中第j个字符y(j)所需要的操作次数。 88. * 如果x(i)==y(j),则不需要任何操作isModify(i, j)=0; 否则,需要替换操作,isModify(i, j)=1。 89. * @param i 字符串X第i个字符 90. * @param j 字符串Y第j个字符 91. * @return 需要替换,返回1;否则,返回0 92. */ 93. private int isModify(int i,int j){ 94. if(charArrayX[i]==charArrayY[j]) 95. return 0; 96. else return 1; 97. } 98. 99. /** 100. * 测试 101. * @param args 102. */ 103. public static void main(String[] args) { 104. System.out.println("编辑距离是:"+new StrEditDistance("eeba","abac").getDistance()); 105. } 106. 107. }
发表评论
-
awk正则表达式中调用ksh变量
2012-07-06 09:45 1024如果ksh中定义了变量pcname,而在嵌入ksh中的aw ... -
Android 正则表达式学习
2012-07-06 09:37 863Java正则表达式学习: 因为正则表达式是一个很庞杂 ... -
Javascript 使用对象(1)- 简单型 ( 含属性,方法)
2012-07-06 09:30 536定义属性: Skin={ 'data':{ ' ... -
JS操作HTML 我的笔记1
2012-07-05 20:45 6251. document.getElementBy ... -
核心Swing组件(六)
2012-07-03 13:42 606JButton组件是可以被 ... -
关于Flex 的渲染器的总结
2012-07-02 10:25 581关键字: Flex. 渲染 ... -
flex笔记--安装与项目建立
2012-07-02 10:25 555使用java做后台,采用Eclipse插件式安装 操 ... -
Flex权威指南3学习笔记之一------界面知识(一)
2012-07-02 10:24 570最近在学习flex,正 ... -
Building a custom Flex preloader
2012-07-02 10:24 593http://www.adobe.com/devnet/f ... -
采用数据库为Flex Tree组件的提供数据-Java与LCDS
2012-07-01 09:44 620Java与LCDS 俺在这里使用Adobe LiveCyc ... -
java Flex as3 数据类型对应关系表
2012-07-01 09:44 823LCDS只能与J2EE的服务端进行通信,目前只是Actio ... -
java ArrayList 转成Flex ArrayCollection
2012-07-01 09:43 5961. server package com.east. ... -
Flex TXT文件导入
2012-07-01 09:43 633在上一篇文章中,我们做了一个文件上传、导入组件,其实就是一 ... -
[转载]关于VS05里checkboxlist用JS获取不到value值的解决方法
2012-06-30 17:59 672页面上有个服务器控件checkboxlist,想要获取选中 ... -
win32 API创建tooltip的版本不匹配问题解决方法
2012-06-30 17:59 1270在visual studio 2005以上版本中使用API ... -
IBM JDK下访问SSL/HTTPS时候ClassNotFoundException解决方法
2012-06-30 17:59 1614项目代码会使用HTTPS,之前一直在Sun JDK+Tom ... -
python windows mysqldb安装错误解决方法
2012-06-30 17:59 1058首先会出现如下错误: serverKey = _wi ... -
infobright创建表时指定存储目录无效的解决方法
2012-06-30 17:59 638infobright是一个基于 ...
相关推荐
编辑距离算法,比较字符串相似度 pb11.5版本
输入任意两个字符串,计算它们的编辑距离。 编辑距离是指两个字符串之间,由一个转换为另一个所需的最少编辑操作次数。许可的编辑操作包括字符的替换、插入和删除。
计算两个字符串的编辑距离 -- 快速算法
算法-动态规划- 线性 DP- 字符串编辑距离(包含源程序).rar
设A 和B 是2 个字符串。要用最少的字符操作将字符串A 转换为字符...试设计一个有效算法,对任给的2 个字符串A和B,计算出它们的编辑距离d(A,B)。 编程任务: 对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)。
两个字符串的相似度算法实现——编辑距离之Levenshtein距离
Levenshtein:快速计算编辑距离以及字符串的相似度
编辑距离算法,即Levenshtein Distance (LD)算法。 这个算法其实是一个动态规划(DP)。levenshtein() 返回两个字符串之间的 Levenshtein 距离。 Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个...
设A和B是2个字符串.要用最少的字符操作将字符串A转换为字符串B.这里所说的字符操作包括: (1)删除一个字符 (2)插入一个字符 ...试设计一个有效算法,对任给的2个字符串A和B,计算出他们的编辑距离d(A,B)
使用最短编辑距离算法判断两个字符串的相似度
本题提出了一些关于将字符串x[1..m]转换成y[1..n]的操作。这些操作有复制、替代、删除、插入、互换和终止。这些操作所需的开销是不同的,但每个操作的开销都可以看是一个我们已经的常量,我们假设复制和替代这类操作...
比较两个字符串的相似度,利用Levenshein算法计算出两个字符串的最小编辑距离,根据最小编辑距离得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4/5。
NULL 博文链接:https://biansutao.iteye.com/blog/326008
编辑距离:字符串的相似度 编辑距离的伪算法 java实现
java-string-similarity, 各种字符串相似性和距离算法 java-string-similarity 实现不同字符串相似度和距离度量的库。 目前已经实现了许多算法( 包括Levenshtein编辑距离和 sibblings,jaro winkler,最长公共子序列...
试设计一个有效算法,对任给的2个字符串A和B,计算出它们的编辑距离d(A,B)。 编程任务: 对于给定的字符串A和B,编程计算其编辑距离d(A,B). 数据输入: 由文件input.txt提供输入数据.文件的第一行是字符串A,文件的第二行...
对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)。 Input 输入由多组测试数据组成。 每组测试数据输入的第1 行是字符串A,第2行是字符串B。 Output 对应每组输入,输出的每行中的数是编辑距离d(A,B)。...
参考清华大学的《算法设计与分析》课后的习题,输入两个字符串后输出其编辑距离。
这是用JS编写的一个编辑距离算法,可以用来在网页中检测语句相似性!检测两个字符串的相似性!