相似度

/**
	 * 计算字符串之间的编辑距离，反映其相似度
	 * @param str           待比较字符串
	 * @param strCmp        待比较字符串
	 * @return
	 */
	public static double editDistance (String str,String strCmp)
	{
		double result=0;
		if((str!=null && strCmp!=null))
		{
			String strTemp=str;
			String strLargeTemp=strCmp;
			if(strTemp.length()>strCmp.length())
			{
				strTemp=strCmp;
				strLargeTemp=str;
			}
			int[] tempInt=new int[strTemp.length()+1];	
			int[] resultInt=new int[strTemp.length()+1];
			//initialize the array "tempInt" 
			for(int i=0;i<=strTemp.length();i++)
			{
				tempInt[i]=i;
				resultInt[i]=i;
			}
			
			for(int j=1;j<=strLargeTemp.length();j++)
			{
			    resultInt[0]=j;
				for(int k=1;k<=strTemp.length();k++)
				{
					if(strTemp.charAt(k-1)==strLargeTemp.charAt(j-1))
						resultInt[k]=tempInt[k-1];
					else
					{
						int min=tempInt[k]<tempInt[k-1]? tempInt[k]:tempInt[k-1];
						min=min<resultInt[k-1]? min:resultInt[k-1];
						resultInt[k]=min+1;
					}
					
				}
				
				for(int l=0;l<=strTemp.length();l++)
				{
					tempInt[l]=resultInt[l];
				}

			}
			
			if(strLargeTemp.length()!=0)
				result=(double)(resultInt[strTemp.length()])/(strLargeTemp.length());
			if(resultInt[strTemp.length()]==strLargeTemp.length()-strTemp.length())
			{
				result=-result;
			}
		}
		return result;
	}
	
	
	/**
	 * 计算两个字符串的最长公共子序列
	 * @param str
	 * @param strCmp
	 * @return
	 */
	public static double longestSubstring(String str,String strCmp)
	{
		double result=0;
		if((str!=null && strCmp!=null))
		{
			str=sortString(str);
			strCmp=sortString(strCmp);
			String strTemp=str;
			String strLargeTemp=strCmp;
			if(strTemp.length()>strCmp.length())
			{
				strTemp=strCmp;
				strLargeTemp=str;
			}
			int[] tempInt=new int[strTemp.length()+1];	
			int[] resultInt=new int[strTemp.length()+1];
			//initialize the array "tempInt" 
			for(int i=0;i<=strTemp.length();i++)
				tempInt[i]=0;
			
			for(int j=1;j<=strLargeTemp.length();j++)
			{
			    resultInt[0]=0;
				for(int k=1;k<=strTemp.length();k++)
				{
					if(strTemp.charAt(k-1)==strLargeTemp.charAt(j-1))
						resultInt[k]=tempInt[k-1]+1;
					else
					{
						resultInt[k]=tempInt[k]>resultInt[k-1]? tempInt[k]:resultInt[k-1];
					}
					
				}
				
				for(int l=0;l<=strTemp.length();l++)
				{
					tempInt[l]=resultInt[l];
				}

			}
			
			if(strLargeTemp.length()!=0 && strTemp.length()!=0)
			{
				double  biZhi=(double)(strLargeTemp.length())/strTemp.length();
				double  divisor=Math.pow(strTemp.length(),2)*(2-Math.pow(2, (1-biZhi)));
				divisor=Math.sqrt(divisor);
				result=((double)(resultInt[strTemp.length()]))/divisor;
			}
		}
		return (result);
	}
	
	/**
	 * 字符串排序（包含中文字符）
	 * @param str
	 * @return
	 */
	public static String sortString(String str)
	{
		if (str==null)
			return "";
		StringBuilder strTemp=new StringBuilder("");
		int i=0,j=0;
		int length=str.length();
		int temp=0;
		int[] arrayTemp=new int[length];
		for(i=0;i<length;i++)
		{
			arrayTemp[i]=str.codePointAt(i);
		}
		
		for (i=0;i<length;i++)
		{
			for(j=0;j<length-1-i;j++)
			{
				if(arrayTemp[j]>arrayTemp[j+1])
				{
					temp=arrayTemp[j];
					arrayTemp[j]=arrayTemp[j+1];
					arrayTemp[j+1]=temp;
				}
			}
		}
		
		
		for(i=0;i<length;i++)
		{
			strTemp.appendCodePoint(arrayTemp[i]);
		}
		
		return strTemp.toString();
	}