editdistance.java

实现编辑距离的计算

/**
 * 编辑距离问题：EditDistance.java	JDK:1.6.0
 * 注:为简化问题，将原来的操作简化为四种，即 复制，插入，删除，替换。
 * 代价分别定义为0，1，1，1。
 */
package majesty;
import java.awt.*;
import java.awt.event.*;
import java.util.EventListener;
import javax.swing.*;   


public class EditDistance {
	public static void main (String[] args) {
		testFrame f=new testFrame();
		f.setResizable(false); 
		f.setVisible(true);
	}
}

//class Distance
class Distance {
	private static int d[][]; 				// cost matrix		
	private static int op[][];				//choose matrix	
	private static int[][] path;
	private static int cost;												//the cost for each compare
	private static int Minimum(int a, int b, int c) {				//return the min
		int min;
		min = c;
		if (b < min) {
			min = b;
		}
		if (a < min) {
			min = a;
		}
		return min;
	}
	private static int whoIsMin(int a,int b,int c) {				//return which is the min with 1,2,3
		if(a<b && a<c)
			return 1;
		else {
			if(b<c)
				return 2;
			else
				return 3;
		}
	}
	public static int getEditDistance(String aidStr, String rusStr) {			//return the editdistance
		// Step 1		if one is empty,return the other
		int n = aidStr.length();
		int m = rusStr.length();
		if (n == 0) {
			return m;
		}
		if (m == 0) {
			return n;
		}
		d=new int [n+1][m+1];
		op=new int [n+1][m+1];
		// Step 2		initialization of d[]
		for (int i = 0; i <= n; i++) {
			d[i][0] = i;
		}

		for (int j = 0; j <= m; j++) {
			d[0][j] = j;
		}
		// Step 3		fill up d[][] & op[][] row by row~
		for (int i = 1; i <= n; i++) {
			int s_i = aidStr.charAt(i - 1);
			for (int j = 1; j <= m; j++) {
				int t_j = rusStr.charAt(j - 1);
				if (s_i == t_j) {
					cost = 0;
				} 
				else {
					cost = 1;
				}
				op[i][j]=whoIsMin(d[i - 1][j] + 1, d[i][j - 1] + 1,d[i - 1][j - 1] + cost);
				d[i][j] = Minimum(d[i - 1][j] + 1, d[i][j - 1] + 1,d[i - 1][j - 1] + cost);
            		}
		}
       	return d[n][m];
	}
	public static String makingRus (String s1,String s2) {	//retrun the procedure of the transformation with a formatted string~
		String tempRus="\n";
		int len1=s1.length();
		int len2=s2.length();
		int maxlen=len1>len2?len1:len2;
		path=new int [3][len1+len2];			//the mat which record the trans path from the d[][]~
		
		if (len1*len2==0) {
			if (len1==0) {
				for(int k=0;k<len2;k++) {
					tempRus+="Step"+(k+1)+":  添加"+s2.charAt(k)+"\n";
				}
			}
			else {
				for(int k=0;k<len1;k++) {
					tempRus+="Step"+(k+1)+":  删除"+s1.charAt(k)+"\n";
				}
			}
		}
		else {
			int i=len1;
			int j=len2;
			int m=i+j-1;
			for(;i*j!=0;) {
				int k=Distance.op[i][j];
				switch(k) {
					case 1: {
						path[0][m]=Distance.d[i][j];
						path[1][m]=i;
						path[2][m]=j;
						i--;
						break;
					}
					case 2: {
						path[0][m]=Distance.d[i][j];
						path[1][m]=i;
						path[2][m]=j;
						j--;
						break;
					}
					case 3: {
						path[0][m]=Distance.d[i][j];
						path[1][m]=i;
						path[2][m]=j;
						i--;
						j--;
						break;
					}
				}
				m--;
			}
			
			if (i==0) {
				for (;j!=0;j--) {
					path[0][m]=Distance.d[i][j];
					path[1][m]=i;
					path[2][m]=j;
					m--;
				}
			}
			else if (j==0) {
				for (;i!=0;i--) {
					path[0][m]=Distance.d[i][j];
					path[1][m]=i;
					path[2][m]=j;
					m--;
				}
			}
			
		}
		
		int m=0;
		int n=0;
		int step=0;
		for (;m<len1+len2;) {							// analyze for making  the first part of the tempRus
			if (path[0][m]==0 && path[1][m]==0 && path[2][m]==0) {
				m++;
				continue;
			}
			else {
				for (int _i=m;_i<len1+len2;_i++) {						//use mm again,finish the tempRus~~
					//copy :	= + +
					if (path[0][_i]==path[0][_i-1] && path[1][_i]==path[1][_i-1]+1 && path[2][_i]==path[2][_i-1]+1) {
						tempRus+="Step"+(step+1)+":    复制"+s2.charAt(path[2][_i]-1)+"    代价:0\n";
						step++;
					}
					//change:    + + +
					else if (path[0][_i]==path[0][_i-1]+1 && path[1][_i]==path[1][_i-1]+1 && path[2][_i]==path[2][_i-1]+1) {
						tempRus+="Step"+(step+1)+":   "+s2.charAt(path[2][_i]-1)+" 替换 "+s1.charAt(path[1][_i]-1)+"    代价:1\n";
						step++;
					}
					//delete:     + + =
					else if (path[0][_i]==path[0][_i-1]+1 && path[1][_i]==path[1][_i-1]+1 && path[2][_i]==path[2][_i-1]) {
						tempRus+="Step"+(step+1)+":    删除"+s1.charAt(path[1][_i]-1)+"    代价:1\n";
						step++;
					}
					//insert:    + = +
					else if (path[0][_i]==path[0][_i-1]+1 && path[1][_i]==path[1][_i-1] && path[2][_i]==path[2][_i-1]+1) {
						tempRus+="Step"+(step+1)+":    插入"+s2.charAt(path[2][_i]-1)+"    代价:1\n";
						step++;
					}
					m++;
				}
			}
		}
		return tempRus;
	}
}

// class testFrame~~
class testFrame extends JFrame {
	public boolean f=true;
	public testFrame() {
		setTitle("字符串比较");                
		setLocation(400,250);                           
		setSize(320,280);                                    
		final JTextField x=new JTextField();
		x.setFont(new Font(null,1,24));
		final JTextField y=new JTextField();
		y.setFont(new Font(null,1,24));
		JLabel lab1=new JLabel("From:");
		JLabel lab2=new JLabel("To:");
		JPanel pan1=new JPanel();
		JPanel pan2=new JPanel();
		pan1.setLayout(null);
		pan2.setLayout(null);
		
		pan1.add(lab1);
		pan1.add(x);
		lab1.setBounds(15,23,50,15);
		x.setBounds(60,15,250,40);
		pan2.add(lab2);
		pan2.add(y);
		lab2.setBounds(15,23,50,15);
		y.setBounds(60,15,250,40);		
		
		
		final JButton btn1=new JButton("匹配");        
		final JButton btn2=new JButton("关闭");            
		this.addWindowListener (
			new WindowAdapter() {
				public void windowClosing(WindowEvent e) {
					System.exit(0);
				}
			}
		);
		btn1.addActionListener (											//按钮1事件	
			new ActionListener() {
				public void actionPerformed(ActionEvent e) {
					//待添加主要代码～～～
					String str1=x.getText();
					String str2=y.getText();
					int l1=str1.length();
					int l2=str2.length();
					int finalCost=Distance.getEditDistance(str1,str2);
					String finalRus=Distance.makingRus(str1,str2);
			
					JOptionPane.showMessageDialog(null
						,"转换过程:"+finalRus+"------------------------------"
						+"\n总代价:"+finalCost,"\""+str1+"\" 到 \""+str2+"\" 的转换过程:"
						,JOptionPane.INFORMATION_MESSAGE);
					
				}
			}
		);
		btn2.addActionListener (											//按钮2事件
			new ActionListener() {
				public void actionPerformed(ActionEvent e) {
					System.exit(0);
				}
			}
		);			
		add(pan1);
		add(pan2);
		setLayout(new GridLayout(4,4,10,10));	
		add(btn1);
		add(btn2);
	}
}