我写的描述两个字符串相似程度的算法

Question

自己测试了一下感觉效果还可以package com; public class how { /** 
 * @param args 
 */ 
private String source1; 
private String source2; 
public static void main(String[] args) { 
// TODO Auto-generated method stub 
System.out.println(new how("nameto","tostrame").get());//返回一个介于0-1之间的double值,值越大代表越相似 
} public how(String a,String b){ 
if(a==null||b==null){ 
throw new RuntimeException(); 
} 
if(a.length()==0||b.length()==0){ 
throw new RuntimeException(); 
} 
source1=a; 
source2=b; 
} 
public double get(){ 
return (get(source1,source2)+get(source1,source2))/(source1.length()+source2.length()); 
} 
private static double get(String a,String b){ 
double result1=0; 
double result2=0; 
int[] some; 
some=new int[b.length()]; 
int i; 
for(i=0;i<a.length();i++){ 
double max=0; 
int index=-1; 
for(int j=0;j<b.length();j++){ 
if(a.charAt(i)==b.charAt(j)){ 
double the=(1-Math.abs(((double)i/a.length()-(double)j/b.length())))/(some[j]+1); 
if(the>max){ 
max=the; 
index=j; 
} 
} 
} 
if(index!=-1){ 
result1+=max; 
some[index]++; 
} 
} 
some=new int[b.length()]; 
for(i=a.length()-1;i>=0;i--){ 
double max=0; 
int index=-1; 
for(int j=0;j<b.length();j++){ 
if(a.charAt(i)==b.charAt(j)){ 
double the=(1-Math.abs(((double)i/a.length()-(double)j/b.length())))/(some[j]+1); 
if(the>max){ 
max=the; 
index=j; 
} 
} 
} 
if(index!=-1){ 
result2+=max; 
some[index]++; 
} 
} 
return (result1+result2)/2; 
} 
} 

Answer 1

我是楼主.我对我的程序解释:
首先说一下我对字符的位置的处理
因为被比较的两个字符串的长度未必相等,所以用下标方式表示两个字符分别在两个字符串的位置是否相等来判断很显然不合适，而是应该其下标与其所在字符串的长度的比作为比较依据
例如字符串"pod"和字符串"asogha"中的中间字母o第一个下标是1总长度是3，所在字符串位置比例是1/3
而第二个下标是2，总长度是6，比例也是1/3,事实上这两个o我的处理就是对应的,即是同一个对应字符.(即都在字符串的中央)。我暂且称这个比值为下标比例接下来就是解释整体字符串:
我这里还有一个思想:大多数字符串比较的时候只比较位置相同的字符是否相同，而事实上字符串有可能因为内容改动鹅一些字符错位，虽然错位的相似度不比相同的强，但相似度也不应比没有强，所以我用下标比例之差作为相似度的判断依据，然后用1减去这个差的值就能代表这两个字符的位置的相似度。1就代表另外一个字符串相应位置正好有一个与之相同的，0当然代表没有，而在之间就代表位置差出多少
这样当我判断A是否像B的时候,是对A的每个字符采取遍历的方式,即对于A中的每个字符所对应的下标比例值和B中的所有的和A得这个字符相等的字符中的下标比例做差用1减去，然后取其中的最大值。这里还有一个问题，那么就是字符重复问题.像"qaae" 和"rat"中的第一个字符串中的两个a映射到第二个字符串中的一个"a"，事实上第二个只有一个a，而第一个有两个如果第一个的两个a都直接加上的话就不合理，总应该有些影响.所以我定义了一个int数组some。some的长度等于第二个字符串的长度.初始状态some里的值都是0,每当第二个字符串相应的某个位置的字符和第一个想对应的时候,some对应下标加1,加1并不代表这个位置的字符不能用，因为一个字符串中的字符被多写了几遍，虽然影响相似度，但是应该不会完全不像了.所以下次计算下标比例差判断位置是否相似的时候要除以相应的some+1数值来判断相应的相似度.当然这样前面的字符内容会影响到后面的内容，所以我正面字符串遍历之后还反过来字符串遍历然后取平均值，最后A相似B的值反过来考虑B相似A的值和再考虑它们的长度除以A和B字符串长度的和最后的结果就是我计算出来的代表两个字符串相似度的介于0-1之间的double值

Answer 2

那么我就加个注释:
package com; public class how { /** 
 * @param args 
 */ 
private String source1; 
private String source2; 
public static void main(String[] args) { 
// TODO Auto-generated method stub 
System.out.println(new how("nameto","tostrame").get());//返回一个介于0-1之间的double值,值越大代表越相似 
} public how(String a,String b){ 
if(a==null||b==null){ 
throw new RuntimeException(); 
} 
if(a.length()==0||b.length()==0){ 
throw new RuntimeException(); 
} 
source1=a; 
source2=b; 
} 
public double get(){ 
return (get(source1,source2)+get(source1,source2))/(source1.length()+source2.length()); //分权求值
} 
private static double get(String a,String b){ 
double result1=0; 
double result2=0; 
int[] some; 
some=new int[b.length()]; 
int i; 
for(i=0;i<a.length();i++){ 
double max=0; 
int index=-1; 
for(int j=0;j<b.length();j++){ 
if(a.charAt(i)==b.charAt(j)){ //如果相等
double the=(1-Math.abs(((double)i/a.length()-(double)j/b.length())))/(some[j]+1); //计算相似比例
if(the>max){ 
max=the; 
index=j; //如果最大记住最大值和其位置
} 
} 
} 
if(index!=-1){ 
result1+=max; //加上最大值
some[index]++; //证明已经有了一个
} 
} 
/** 
 下面的意思差不多只不过倒过来遍历 
 */ 
some=new int[b.length()]; 
for(i=a.length()-1;i>=0;i--){ 
double max=0; 
int index=-1; 
for(int j=0;j<b.length();j++){ 
if(a.charAt(i)==b.charAt(j)){ 
double the=(1-Math.abs(((double)i/a.length()-(double)j/b.length())))/(some[j]+1); 
if(the>max){ 
max=the; 
index=j; 
} 
} 
} 
if(index!=-1){ 
result2+=max; 
some[index]++; 
} 
} 
return (result1+result2)/2; 
} 
} 

Answer 3

我大致看了楼主的解释，有句名言说的好，任何定理只有从数学上证明了才是完美的。比如一个字符串A和B，如果A与B比较，相似度是一个数值x；那么B与A比较，相似度也应该是x。很简单的一个例子，A和B相同，那应该都是1，不相同，那就都应该是0。但是楼主的这个例子中"nameto"和"tostrame"这两个参数交换位置，得出的值确实不一样的，这是不是一个问题呢？所以，我觉得楼主的这个算法不满足逻辑中的对称原理（symmetric）。

Answer 4

是我搞错了。应该是
return (get(source1,source2)+get(source2,source1))/(source1.length()+source2.length());
这样就对称了,我忘记换过来了