当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

编程之美-计算字符串的相似度

发表于: 2012-08-09   作者:bylijinnan   来源:转载   浏览:
摘要: public class StringDistance { /** * 编程之美 计算字符串的相似度 * 我们定义一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为: * 1.修改一个字符(如把“a”替换为“b”); * 2.增加一个字符(如把“abdd”变为“aebdd”); * 3.删除一个字符(如把“travelling”变为“trav

public class StringDistance {

	/**
	 * 编程之美 计算字符串的相似度
	 * 我们定义一套操作方法来把两个不相同的字符串变得相同,具体的操作方法为:
	 * 1.修改一个字符(如把“a”替换为“b”);
	 * 2.增加一个字符(如把“abdd”变为“aebdd”);
	 * 3.删除一个字符(如把“travelling”变为“traveling”);
	 * 比如,对于“abcdefg”和“abcdef”两个字符串来说,我们认为可以通过增加/减少一个“g”的方式来达到目的。
	 * 上面的两种方案,都仅需要一次 。把这个操作所需要的次数定义为两个字符串的距离,而相似度等于“距离+1”的倒数。
	 * 也就是说,“abcdefg”和“abcdef”的距离为1,相似度 为1/2=0.5。
	 * 给定任意两个字符串,你是否能写出一个算法来计算它们的相似度呢?
	 * 
	 * 解答:动态规划+备忘录
	 * 2012-11-04:主要思路还是递归。字符串记为A和B(当前比较的位置记为K,当前距离记为L),从第一个字符开始按位比较,分两种情况:
	 * 1、A和B在第K位的字符相等(L不变)。那好,各自向后移动,继续比较第K+1位
	 * 2、A和B在第K位的字符不相等(L=L+1)。采取递归,作三种操作,看哪种操作最后得到的距离最短:
	 * 一是A和B同时向后移动(相当于A和B同时删除这个字符),继续比较第K+1位
	 * 二是A移动B不移动,相当于A删除了这个字符,用剩余的字符与B作比较
	 * 三是A不移动B移动,相当于B删除了这个字符,用剩余的字符与A作比较
	 * 递归的好处就是可以递归得到这三种操作到最后得到的距离,哪个是最短
	 * 举个例子,A="abc",B="zbc"。我们可以一眼看出,采用第一种操作算得的距离最短(L=1)
	 * 但程序中要递归执行这另外两种操作并比较:
	 * A1="bc",B2="zbc" -->按位比较得到的L=1+3
	 * A2="abc",B2="bc" -->按位比较得到的L=1+3
	 * 因此程序会选择第一种操作,再接着进行第K+1位的比较
	 */
	
	private static int[][] record;	//记录子问题的解,0表示子问题未求解
	
	public static void main(String[] args) {
		String strA = "abcd";
		String[] strBB = {
				"",
				"z",
				"a",
				"ac",
				"adc"
		};
		for (String strB : strBB) {
			int distance = distanceBetween(strA, strB);
			System.out.println(distance);
		}
	}

	public static int distanceBetween(String strA, String strB) {
		int distance = -1;
		if (strA != null && strB != null) {
			int lenA = strA.length();
			int lenB = strB.length();
			if (lenA == 0 && lenB == 0) {
				distance = 0;
			}
			if (lenA != 0 && lenB == 0) {
				distance = lenA;
			}
			if (lenA == 0 && lenB != 0) {
				distance = lenB;
			}
			if (lenA != 0 && lenB != 0) {
				record = new int[lenA + 1][lenB + 1];
				char[] charArrayA = strA.toCharArray();
				char[] charArrayB = strB.toCharArray();
				distance = distanceHelp(charArrayA, charArrayB, 0, 0, lenA - 1, lenB - 1);
			}
		}
		return distance;
	}
	
	//endA和endB是不变的,因此记录子问题的解可用record[beginA][beginB]来表示
	public static int distanceHelp(char[] charArrayA, char[] charArrayB,
									 int beginA, int beginB, int endA, int endB) {
		if (beginA > endA) {				//递归出口:A从头到尾每个字符遍历完了,B有两种情况:
			if (beginB > endB) {			//1.B也同时遍历完了,说明这A=B
				return 0;	
			} else {
				return endB - beginB + 1;	//2.B还没遍历完,那B剩下的长度就是两个字符串不同的地方,即距离
			}
		}
		if (beginB > endB) {
			if (beginA > endA) {
				return 0;
			} else {
				return endA - beginA + 1;
			}
		}
		
		int distance = -1;
		if (charArrayA[beginA] == charArrayB[beginB]) {
			distance = record[beginA + 1][beginB + 1];
			if (distance == 0) {
				distance = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB + 1, endA, endB);
			}
		} else {
			int d1 = record[beginA + 1][beginB];
			if (d1 == 0) {
				d1 = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB, endA, endB); 
			}
			int d2 = record[beginA][beginB + 1];
			if (d2 == 0) {
				d2 = distanceHelp(charArrayA, charArrayB, beginA, beginB + 1, endA, endB); 
			}
			int d3 = record[beginA + 1][beginB + 1];
			if (d3 == 0) {
				d3 = distanceHelp(charArrayA, charArrayB, beginA + 1, beginB + 1, endA, endB); 
			}
			distance = min(d1, d2, d3) + 1;
		}
		record[beginA][beginB] = distance;
		return distance;
	}
	
	private static int min(int x, int...yy) {
		int m = x;
		for (int y : yy) {
			if (y < m) {
				m = y;
			}
		}
		return m;
	}
}

编程之美-计算字符串的相似度

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目:编写一个函数,把一个char组成的字符串循环右移n位。例如:原来是”abcdefghi”,如果n = 2,
一直不理解,为什么要计算两个字符串的相似度呢。什么叫做两个字符串的相似度。经常看别人的博客,
题目来自编程之美 题目 思路:其实就是求两个字符串的编辑距离,直接给出DP的思路 代码 #include &l
一、词语相似度   词义相似度计算在很多领域中都有广泛的应用,例如信息检索、信息抽取、文本分类
一、词语相似度   词义相似度计算在很多领域中都有广泛的应用,例如信息检索、信息抽取、文本分类
一、词语相似度   词义相似度计算在很多领域中都有广泛的应用,例如信息检索、信息抽取、文本分类
引言 相似度计算用于衡量对象之间的相似程度,在数据挖掘、自然语言处理中是一个基础性计算。其中的
转自:http://blog.sina.com.cn/s/blog_4a540be60100vjae.html 图像相似度计算主要用于对于两幅图像
思路是:把字符串的字符放入一个字典中,计算他们(相同的个数/开平方(字符串1的个数*字符串2的个数),
本文转自http://blog.sina.com.cn/s/blog_4a540be60100vjae.html 图像相似度计算主要用于对于两幅图
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号