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（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。