文本相似度——编辑距离算法&java简单实现

56 阅读 0 评论 37 点赞

我是靠谱客的博主内向雪糕，最近开发中收集的这篇文章主要介绍文本相似度——编辑距离算法&java简单实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

从问题出发，来学算法~

问题：找出字符串的编辑距离，即把一个字符串s1最少经过多少步操作变成字符串s2？

操作有三种，添加一个字符，删除一个字符，修改一个字符。

分析：核心就是Function——edit（i,j），它表示字符串s1的长度为i的子串到字符串s2的长度为j的子串的编辑距离。

可以有如下动态规划公式：

# if i == 0 且 j == 0，edit(i, j) = 0

# if i == 0 且 j > 0，edit(i, j) = j

# if i > 0 且j == 0，edit(i, j) = i

# if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，当s1的第i 个字符不等于s2的第j个字符时，f(i, j) = 1；否则，f(i, j) = 0。

public class LevenshteinTest {
	private int[][] array;
	private String str1;
	private String str2;
	
	public LevenshteinTest(String str1,String str2){
		this.str1 = str1;
		this.str2 = str2;
	}
  
	
	public int edit()
	{
		int max1 = str1.length();
		int max2 = str2.length();
		//建立数组，比字符长度大一个空间 
        array = new int[max2+1][max1+1];
        for(int i=0;i<=max1;i++){
			array[0][i] = i;
		}
		for(int j=0;j<=max2;j++){
			array[j][0] = j;
		}
		
		for(int i=1;i<=max1;i++){
			for(int j=1;j<=max2;j++){
				array[j][i] = levenshtein(i,j,str1.charAt(i-1),str2.charAt(j-1));
				System.out.println("j=="+j+" i=="+i+"   "+array[j][i]);
			}
		}
		System.out.println("*********"+array[max2][max1]);
		return array[max2][max1];
		 
	}
	
	public int levenshtein(int i,int j,char si,char sj)
	{
		int result = 0;
		
	    if(i>=1&&j>=1){
	    	int a = array[j-1][i] + 1;
			int b = array[j][i-1] + 1;
		    int c = array[j-1][i-1] + ((si!=sj)?1:0);
		    result = min(a,b,c);
		}
		
		return result;
	}
	
	public int min(int a,int b,int c)
	{
		int temp = a<b?a:b;
		return temp<c?temp:c;
	} 

    //计算相似度   
    public float similarity(){
    	float similarity = 1 - (float) array[max2][max1] / Math.max(str1.length(), str2.length());   
        return similarity;
    }
	
	public static void main(String args[]){
		String str1 = "叶尖压力高";
		String str2 = "系统压力高";
		LevenshteinTest lt = new LevenshteinTest(str1,str2);
	    lt.edit();
	        
	}

}