Java滚动数组计算编辑距离操作示例
本文实例讲述了Java滚动数组计算编辑距离操作。分享给大家供大家参考,具体如下:
编辑距离(EditDistance),也称Levenshtein距离,是指由一个字符串转换为另一个字符串所需的最少编辑次数。
下面的代码摘自org.apache.commons.lang.StringUtils
用法示例:
StringUtils.getLevenshteinDistance(null,*)=IllegalArgumentException StringUtils.getLevenshteinDistance(*,null)=IllegalArgumentException StringUtils.getLevenshteinDistance("","")=0 StringUtils.getLevenshteinDistance("","a")=1 StringUtils.getLevenshteinDistance("aaapppp","")=7 StringUtils.getLevenshteinDistance("frog","fog")=1 StringUtils.getLevenshteinDistance("fly","ant")=3 StringUtils.getLevenshteinDistance("elephant","hippo")=7 StringUtils.getLevenshteinDistance("hippo","elephant")=7 StringUtils.getLevenshteinDistance("hippo","zzzzzzzz")=8 StringUtils.getLevenshteinDistance("hello","hallo")=1
Java代码:
publicstaticintgetLevenshteinDistance(Strings,Stringt){ if(s==null||t==null){ thrownewIllegalArgumentException("Stringsmustnotbenull"); } intn=s.length();//lengthofs intm=t.length();//lengthoft if(n==0){ returnm; }elseif(m==0){ returnn; } if(n>m){ //swaptheinputstringstoconsumelessmemory Stringtmp=s; s=t; t=tmp; n=m; m=t.length(); } intp[]=newint[n+1];//'previous'costarray,horizontally intd[]=newint[n+1];//costarray,horizontally int_d[];//placeholdertoassistinswappingpandd //indexesintostringssandt inti;//iteratesthroughs intj;//iteratesthrought chart_j;//jthcharacteroft intcost;//cost for(i=0;i<=n;i++){ p[i]=i; } for(j=1;j<=m;j++){ t_j=t.charAt(j-1); d[0]=j; for(i=1;i<=n;i++){ cost=s.charAt(i-1)==t_j?0:1; //minimumofcelltotheleft+1,tothetop+1,diagonallyleftandup+cost d[i]=Math.min(Math.min(d[i-1]+1,p[i]+1),p[i-1]+cost); } //copycurrentdistancecountsto'previousrow'distancecounts _d=p; p=d; d=_d; } //ourlastactionintheaboveloopwastoswitchdandp,sopnow //actuallyhasthemostrecentcostcounts returnp[n]; }
实际上,上述代码的空间复杂度还可以进一步简化,使用一维数组替换滚动数组。
Java代码:
publicintminDistance(Strings,Stringt){ if(s==null||t==null){ thrownewIllegalArgumentException("Stringsmustnotbenull"); } intn=s.length();//lengthofs intm=t.length();//lengthoft if(n==0){ returnm; }elseif(m==0){ returnn; } if(n>m){ //swaptheinputstringstoconsumelessmemory Stringtmp=s; s=t; t=tmp; n=m; m=t.length(); } intd[]=newint[n+1];//costarray,horizontally //indexesintostringssandt inti;//iteratesthroughs intj;//iteratesthrought chart_j;//jthcharacteroft intcost;//cost for(i=0;i<=n;i++){ d[i]=i; } for(j=1;j<=m;j++){ t_j=t.charAt(j-1); intpre=d[0]; d[0]=j; for(i=1;i<=n;i++){ inttemp=d[i]; cost=s.charAt(i-1)==t_j?0:1; //minimumofcelltotheleft+1,tothetop+1,diagonallyleftandup+cost d[i]=Math.min(Math.min(d[i-1]+1,d[i]+1),pre+cost); pre=temp; } } returnd[n]; }
更多关于java相关内容感兴趣的读者可查看本站专题:《Java数组操作技巧总结》、《Java字符与字符串操作技巧总结》、《Java数学运算技巧总结》、《Java数据结构与算法教程》及《Java操作DOM节点技巧总结》
希望本文所述对大家java程序设计有所帮助。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。