`
zy3381
  • 浏览: 157636 次
  • 性别: Icon_minigender_1
  • 来自: 昆明
社区版块
存档分类
最新评论

编辑距离

 
阅读更多
直接递归形式的编辑距离求解(递归过程会产生很多重复计算,所以应该采用动态规划来提高效率)


public class LevenshteinDistance
{

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		//1
//		String str1 = "abc";
//		String str2 = "adc";
		
		//2
//		String str1 = "ababababa";
//		String str2 = "babababab";
		
		//2
//		String str1 = "abcd";
//		String str2 = "acdb";
		
		//3
		String str1 = "kitten";
		String str2 = "sitting";
		
		int result = Distance(str1, 0, str1.length()-1, str2, 0, str2.length()-1);
		System.out.println(result);
	}

	
	public static int Distance(String str1, int begin1, int end1, String str2, int begin2, int end2)
	{
		//如果第一个已经遍历完了
		if(begin1 > end1)
		{
			//如果第二个也遍历完了
			if(begin2 > end2)
			{
				return 0;
			}
			//如果第二个还没遍历完(剩余的第二个字符的长度依次删除就可以了)
			else
			{
				return end2 - begin2 + 1;
			}
		}
		
		//和上面同理
		if(begin2 > end2)
		{
			if(begin1 > end1)
			{
				return 0;
			}
			else
			{
				return end1 - begin1 + 1;
			}
		}
		
		//如果这两个字符相等,无需操作,均跳到下一个位置比较
		if(str1.charAt(begin1) == str2.charAt(begin2))
		{
			return Distance(str1, begin1 + 1, end1, str2, begin2 + 1, end2);
		}
		else
		{
			//删除str1中begin1位置的字符,继续比较str1的begin1+1和str2的begin2(或者在str2的begin2位置前面增加一个字符使之等于str1的begin1)
			int value1 = Distance(str1, begin1 + 1, end1, str2, begin2, end2) + 1;
			//删除str2中begin2位置的字符,继续比较str2的begin2+1和str1的begin1(或者在str1的begin1位置前面增加一个字符使之等于str2的begin2)
			int value2 = Distance(str1, begin1, end1, str2, begin2 + 1, end2) + 1;
			//修改str1的begin1位置的字符或者修改str2的begin2位置的字符,使二者相等,然后比较str1的begin1+1和str2的begin2+1
			int value3 = Distance(str1, begin1 + 1, end1, str2, begin2 + 1, end2) + 1;
			//返回最小值
			return min(value1, value2, value3);
		}
		
	}
	
	public static int min(int a, int b, int c)
	{
		int min = a;
		if(b<min)
		{
			min = b;
		}
		if(c<min)
		{
			min = c;
		}
		return min;
	}
}












动态规划形式:

public class LDistance
{

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		String str1 = "kitten";
		String str2 = "sitting";
//		System.out.println(min(4,5,1));
		int result = Distance(str1, str2);
		System.out.println(result);
	}
	
	public static int Distance(String str1, String str2)
	{
		int str1Length = str1.length();
		int str2Length = str2.length();
		if(str1Length == 0)
		{
			return str2Length;
		}
		if(str2Length == 0)
		{
			return str1Length;
		}
		int[][] d = new int[str1Length + 1][str2Length + 1];
		
		//填写纵向的第一列
		for (int i = 0; i < str1Length + 1; i++)
		{
			d[i][0] = i;
		}
		//填写横向的第一列
		for (int i = 0; i < str2Length + 1; i++)
		{
			d[0][i] = i;
		}
		
		for (int i = 1; i < str1Length + 1; i++)
		{
			for (int j = 1; j < str2Length + 1; j++)
			{
				int cost = 0;
				if(str1.charAt(i-1) != str2.charAt(j-1))
				{
					cost = 1;
				}
							//在str1上i位置删除字符(或者在str2上j-1位置插入字符)
				d[i][j] = min(d[i-1][j] + 1, 
							//在str1上i-1位置插入字符(或者在str2上j位置删除字符)
							d[i][j-1] + 1, 
							// 替换操作
							d[i-1][j-1] + cost);
			}
		}
		
		return d[str1Length][str2Length];
	}
	
	public static int min(int a, int b, int c)
	{
		int min = a;
		if(b<min)
		{
			min = b;
		}
		if(c<min)
		{
			min = c;
		}
		return min;
	}
}













分享到:
评论

相关推荐

    编辑距离算法的总结和分析

    编辑距离算法,也称为Levenshtein距离,是计算两个字符串之间差异的一种度量方法,广泛应用于文本处理、拼写纠正、生物信息学等领域。它通过衡量将一个字符串转换为另一个字符串所需的最少单字符操作数(包括删除、...

    SQL SERVER实现编辑距离(Edit Distance)算法

    编辑距离(Edit Distance)算法,也被称作Levenshtein距离算法,是一种用于字符串之间模糊匹配的常用方法。在SQL Server数据库中,我们可以通过创建一个函数来实现Levenshtein距离算法,进而进行字符串的比较和...

    编辑距离问题-算法导论.pdf

    编辑距离问题-算法导论 在计算机科学中,编辑距离问题是指将一个字符串转换成另一个字符串所需的最少操作步骤数。这些操作可以是插入、删除、替换和复制字符。编辑距离问题是一种典型的动态规划问题。 动态规划是...

    c或c++中求编辑距离的程序代码

    编辑距离(Edit Distance)是一种衡量两个字符串相似度的算法,广泛应用于文本处理、生物信息学等领域。这个算法基于动态规划的思想,计算出将一个字符串转换为另一个字符串所需要的最少操作次数,包括插入、删除和...

    编辑距离 字符串的相似度

    编辑距离(Edit Distance)是一种衡量两个字符串相似度的数学概念,它定义了将一个字符串转换成另一个字符串所需的最少单字符操作次数,包括插入、删除和替换。这些操作在自然语言处理(NLP)中有着广泛的应用,比如...

    计算两字符串的编辑距离

    编辑距离,又称Levenshtein距离,是一种衡量两个字符串相似度的指标,广泛应用于文本处理、数据校验、搜索引擎优化等多个领域。这个概念源于俄国科学家瓦迪姆·列文斯坦在1965年提出,它定义了将一个字符串转换成另...

    树编辑距离的 Python APTED算法_python_代码_下载

    这是 APTED 算法的 Python 实现,它是计算树编辑距离的最先进的解决方案 ,它取代了 RTED 算法 输入 目前,我们只支持输入树的所谓括号表示法,例如,编码{A{B{X}{Y}{F}}{C}}对应于以下树: A / \ B C /|\ X Y...

    一种编辑距离算法及其在网页搜索中的应用

    ### 编辑距离算法及其在网页搜索中的应用 #### 概述 在互联网时代,搜索引擎作为获取信息的主要工具之一,其核心竞争力在于如何更准确、更高效地将用户查询与相关网页进行匹配。传统的相关性排序算法往往侧重于...

    编辑距离JS算法

    ### 编辑距离JS算法详解 #### 一、编辑距离概念 编辑距离(Edit Distance),又称Levenshtein距离,是一种衡量两个字符串相似度的方法。它定义为通过插入、删除或替换一个字符的方式将一个字符串转换成另一个字符串...

    编辑距离原代码 根据编的

    编辑距离,又称Levenshtein距离,是一种衡量两个字符串相似度的度量方式。这个概念在计算机科学,尤其是文本处理、信息检索和生物信息学等领域有着广泛应用。原码(或称为原始代码)指的是程序员最初编写,未经任何...

    动态规划解决编辑距离问题

    编辑距离,又称为Levenshtein距离,是度量空间中的一个重要概念,它衡量了两个字符串通过插入、删除或替换操作相互转换所需的最小步骤数。在这个问题中,我们将深入探讨动态规划如何有效地计算编辑距离。 编辑距离...

    编辑距离的详细讲解

    ### 编辑距离详解 #### 一、编辑距离的基本概念 **编辑距离**(Edit Distance),也称为Levenshtein距离,是一种衡量两个序列相似度的方法。它定义为通过一系列预定义的操作(如插入、删除或替换一个字符)将一个...

    编辑距离问题 对于给定的字符串A和字符串B,编程计算其编辑距离d(A,B)。

    ### 编辑距离问题 #### 一、问题背景与定义 在计算机科学领域,编辑距离(Edit Distance)是一个衡量两个字符串相似度的重要概念。编辑距离指的是通过一系列预定义的操作(如插入、删除或替换字符)将一个字符串...

    基于编辑距离的拼写矫正算法

    **基于编辑距离的拼写矫正算法** 在计算机科学和自然语言处理领域,拼写矫正是一项重要的任务,尤其在文本输入、搜索引擎优化、机器翻译等方面有着广泛的应用。编辑距离(Edit Distance)是解决这一问题的一种经典...

    编辑距离问题-------txt

    ### 编辑距离问题解析 #### 一、问题定义与背景 编辑距离(Edit Distance),又称Levenshtein距离,是一种衡量两个字符串相似度的方法。它定义了将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数。...

    动态规划之编辑距离问题

    动态规划之编辑距离问题 编辑距离问题是计算机科学中一个经典问题,旨在寻找将一个字符串转换为另一个字符串所需的最少操作数。这个问题可以通过动态规划算法来解决,下面将对其进行详细的解释。 问题描述 编辑...

    Python-Levenshtein快速计算编辑距离以及字符串的相似度

    在Python编程环境中,Levenshtein库是一个非常实用的工具,用于计算两个字符串之间的编辑距离。编辑距离,也称为Levenshtein距离,是衡量两个字符串差异的一种度量,定义为由一个字符串转换成另一个字符串最少的单...

    编辑距离EditDistance

    **编辑距离(Edit Distance)** 编辑距离,也称为Levenshtein距离,是一种衡量两个字符串相似度的方法。在计算机科学和信息学中,它被广泛应用于文本比较、拼写检查、生物信息学等领域。编辑距离定义为从一个字符串...

    编辑距离算法例子

    编辑距离算法,也被称为Levenshtein距离,是一种衡量两个字符串相似度的度量方法。在信息技术、自然语言处理和生物信息学等领域有着广泛应用。它定义了将一个字符串转换成另一个字符串所需的最少单字符编辑操作次数...

    算法设计编辑距离问题

    ### 编辑距离问题解析与算法实现 #### 一、问题背景及定义 **编辑距离**(Edit Distance),也称为Levenshtein Distance,是一种衡量两个字符串相似度的方法,即通过最少的操作次数(如插入、删除或替换字符)将一个...

Global site tag (gtag.js) - Google Analytics