Java动态规划之编辑距离问题示例代码

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

动态规划实际上是一类题目的总称，并不是指某个固定的算法。动态规划的意义就是通过采用递推（或者分而治之）的策略，通过解决大问题的子问题从而解决整体的做法。动态规划的核心思想是巧妙的将问题拆分成多个子问题，通过计算子问题而得到整体问题的解。而子问题又可以拆分成更多的子问题，从而用类似递推迭代的方法解决要求的问题。问题描述:

对于序列S和T,它们之间的距离定义为:对二者其一进行几次以下操作:1,删除一个字符;2,插入一个字符;3,改变一个字符.每进行一次操作,计数增加1.将S和T变为相等序列的最小计数就是两者的编辑距离(editdistance)或者叫相似度.请给出相应算法及其实现.

分析:

假设序列S和T的长度分别为m和n,两者的编辑距离表示为edit[m][n].则对序列进行操作时存在以下几种情况:

a,当S和T的末尾字符相等时,对末尾字符不需要进行上述定义操作中(亦即"编辑")的任何一个,也就是不需要增加计数.则满足条件:edit[m][n]=edit[m-1][n-1].

b,当S和T的末尾字符不相等时,则需要对两者之一的末尾进行编辑,相应的计数会增加1.

b1,对S或T的末尾进行修改,以使之与T或S相等,则此时edit[m][n]=edit[m-1][n-1]+1;

b2,删除S末尾的元素,使S与T相等,则此时edit[m][n]=edit[m-1][n]+1;

b3,删除T末尾的元素,使T与S相等,则此时edit[m][n]=edit[m][n-1]+1;

b4,在S的末尾添加T的尾元素,使S和T相等,则此时S的长度变为m+1,但是此时S和T的末尾元素已经相等,只需要比较S的前m个元素与T的前n-1个元素,所以满足edit[m][n]=edit[m][n-1]+1;

b5,在T的末尾添加S的尾元素,使T和S相等,此时的情况跟b4相同,满足edit[m][n]=edit[m-1][n]+1;

c,比较特殊的情况是,当S为空时,edit[0][n]=n;而当T为空时,edit[m][0]=m;这个很好理解,例如对于序列""和"abc",则两者的最少操作为3,即序列""进行3次插入操作,或者序列"abc"进行3次删除操作.

所以,以上我们不难推出编辑距离的动态规划方程为:

所以, 字符串编辑距离的动态规划算法的递归实现可以用如下的Java代码表示:

public static int editDistance(String a, String b) {
    if (a == null || b == null) {
      return -1;
    }
    return editDistance(a, a.length() - 1, b, b.length() - 1);
  }

  public static int editDistance(String a, int m, String b, int n) {
    if (m < 0 || n < 0) {
      return 1;
    } else if (a.charAt(m) == b.charAt(n)) {
      return editDistance(a, m - 1, b, n - 1);
    } else {
      return Math.min(Math.min(editDistance(a, m - 1, b, n) + 1, editDistance(a, m, b, n - 1) + 1), editDistance(a, m - 1, b, n - 1) + 1);
    }
  }

UPDATE:

同时, 由编辑距离的动态规划方程我们可以看出, edit[m][n]可以由edit[m - 1][n - 1], edit[m - 1][n], edit[m][n - 1]得出, 而如果edit是一个二维数组的话, edit[m][n]可以由它的上, 左, 左上三个位置的元素通过条件判断得出. 亦即我们可以通过遍历二维数组, 然后通过回溯来计算当前值.

例如对于字符串S = "sailn"和T = "failing", 对二维数组进行初始化为:

m\n   f a i l i n g
  0 1 2 3 4 5 6 7
s 1 1            
a 2              
i 3              
l 4              
n 5              

因为S[0] = s, T[0] = f, 则S[0] != T[0], 则对应于上述二维矩阵, edit[1][1] = min(edit[0][0], edit[0][1], edit[1][0]) + 1即edit[1][1] = min(0, 1, 1) + 1即edit[1][1] = 0 + 1 = 1.

m\n   f a i l i n g
  0 1 2 3 4 5 6 7
s 1 1 2 3 4 5 6 7
a 2 2 1          
i 3              
l 4              
n 5              

而对于S[1] = a, T[1] = a, S[1] = T[1], 则对应于二维矩阵, edit[2][2] = edit[1][1], 所以edit[2][2] = 1. 所以按照这种规则, 将上述二维矩阵填满则如下:

m\n   f a i l i n g
  0 1 2 3 4 5 6 7
s 1 1 2 3 4 5 6 7
a 2 2 1 2 3 4 5 6
i 3 3 2 1 2 3 4 5
l 4 4 3 2 1 2 3 4
n 5 5 4 3 2 2 2 3

所以, 两者的编辑距离为edit[m][n] = edit[5][7] = 3.

所以, 按照上述思路即动态规划的回溯解法的Java版本可以如下进行:

public static int editDistance(String a, String b) {
    if (a == null || b == null) {
      return -1;
    }
    int[][] matrix = new int[a.length() + 1][b.length() + 1];
    for (int i = 0; i < a.length() + 1; i++) {
      for (int j = 0; j < b.length() + 1; j++) {
        if (i == 0) {
          matrix[i][j] = j;
        } else if (j == 0) {
          matrix[i][j] = i;
        } else {
          if (a.charAt(i - 1) == b.charAt(j - 1)) {
            matrix[i][j] = matrix[i - 1][j - 1];
          } else {
            matrix[i][j] = 1 + Math.min(Math.min(matrix[i - 1][j], matrix[i][j - 1]), matrix[i - 1][j - 1]);
          }
        }
      }
    }
    return matrix[a.length()][b.length()];
  }

总结

以上就是本文关于Java动态规划之编辑距离问题示例代码的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。

赞 (0)

相关推荐

  • Java实现的最大匹配分词算法详解

    Java实现的最大匹配分词算法详解

    本文实例讲述了Java实现的最大匹配分词算法.分享给大家供大家参考,具体如下: 全文检索有两个重要的过程: 1分词 2倒排索引 我们先看分词算法 目前对中文分词有两个方向,其中一个是利用概率的思想对文章分词. 也就是如果两个字,一起出现的频率很高的话,我们可以假设这两个字是一个词.这里可以用一个公式衡量:M(A,B)=P(AB)/P(A)P(B),其中 A表示一个字,B表示一个字,P(AB)表示AB相邻出现的概率,P(A)表示A在这篇文章中的频度,P(B)表示B在这篇文章中的频度.用概率分词的好

  • 使用递归算法结合数据库解析成Java树形结构的代码解析

    1.准备表结构及对应的表数据 a.表结构: create table TB_TREE ( CID NUMBER not null, CNAME VARCHAR2(50), PID NUMBER //父节点 ) b.表数据: insert into tb_tree (CID, CNAME, PID) values (1, '中国', 0); insert into tb_tree (CID, CNAME, PID) values (2, '北京市', 1); insert into tb_tree

  • Java实现合并两个有序序列算法示例

    本文实例讲述了Java实现合并两个有序序列算法.分享给大家供大家参考,具体如下: 问题描述 输入:序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>,其中a0<a1<...<aq,aq+1<aq+2<...<ar 输出:序列B<b0,b1,...,br>,其中b0<b1<...<br 算法思想 创建一个长度为r的数组R,将A中的序列看作是两个有序序列 B=A<a0,a1,a2,...,aq> C

  • Java使用分治算法实现排序数索引功能示例【二分搜索】

    本文实例讲述了Java使用分治算法实现排序数索引功能.分享给大家供大家参考,具体如下: /** * Find the first q and return the index * First method is brutal force * Second may * be Divid and Conquer * * @author open201 * */ public class Ono { /** * f(n) = s.length = n; * * @param s * @param q

  • 详解Java数据结构和算法（有序数组和二分查找）

    一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默

  • Java贪心算法之Prime算法原理与实现方法详解

    Java贪心算法之Prime算法原理与实现方法详解

    本文实例讲述了Java贪心算法之Prime算法原理与实现方法.分享给大家供大家参考,具体如下: Prime算法:是一种穷举查找算法来从一个连通图中构造一棵最小生成树.利用始终找到与当前树中节点权重最小的边,找到节点,加到最小生成树的节点集合中,直至所有节点都包括其中,这样就构成了一棵最小生成树.prime在算法中属于贪心算法的一种,贪心算法还有:Kruskal.Dijkstra以及哈夫曼树及编码算法. 下面具体讲一下prime算法: 1.首先需要构造一颗最小生成树,以及两个节点之间的权重数组,在

  • Java 蒙特卡洛算法求圆周率近似值实例详解

    起源 [1946: John von Neumann, Stan Ulam, and Nick Metropolis, all at the Los Alamos Scientific Laboratory, cook up the Metropolis algorithm, also known as the Monte Carlo method.]1946年,美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis共同发明,

  • Java实现的两种常见简单查找算法示例【快速查找与二分查找】

    本文实例讲述了Java实现的两种常见简单查找算法.分享给大家供大家参考,具体如下: 前言: 查找是指从一批记录当中找出满足制定条件的某一记录的过程. 在平常的程序的编写当中很多时候时用得上的,这里简单介绍两个查找算法 1. 快速查找: 这个是相当简单的,以数组举例,就用一个for循环去查找数组中需要查找的数据 例子: public static boolean quickSearch(int a[], int x) { boolean f = false; int length = a.leng

  • Java动态规划之编辑距离问题示例代码

    Java动态规划之编辑距离问题示例代码

    动态规划过程是:每次决策依赖于当前状态,又随即引起状态的转移.一个决策序列就是在变化的状态中产生出来的,所以,这种多阶段最优化决策解决问题的过程就称为动态规划. 动态规划实际上是一类题目的总称,并不是指某个固定的算法.动态规划的意义就是通过采用递推(或者分而治之)的策略,通过解决大问题的子问题从而解决整体的做法.动态规划的核心思想是巧妙的将问题拆分成多个子问题,通过计算子问题而得到整体问题的解.而子问题又可以拆分成更多的子问题,从而用类似递推迭代的方法解决要求的问题.问题描述: 对于序列S和T,

  • Java连接postgresql数据库的示例代码

    Java连接postgresql数据库的示例代码

    本文介绍了Java连接postgresql数据库的示例代码,分享给大家,具体如下: 1.下载驱动jar 下载地址:https://jdbc.postgresql.org/download.html 2.导入jar包 新建lib文件夹,将下载的jar驱动包拖到文件夹中. 将jar驱动包添加到Libraries 3.程序代码如下:HelloWorld.java package test; import java.sql.Connection; import java.sql.DriverManage

  • java 生成文字图片的示例代码

    本文主要介绍了java 生成文字图片的示例代码,分享给大家,具体如下: import java.awt.Color; import java.awt.Font; import java.awt.FontMetrics; import java.awt.Graphics; import java.awt.Rectangle; import java.awt.image.BufferedImage; import java.io.File; import javax.imageio.ImageIO;

  • Java的静态类型检查示例代码详解

    关于静态类型检查和动态类型检查的解释: 静态类型检查:基于程序的源代码来验证类型安全的过程: 动态类型检查:在程序运行期间验证类型安全的过程: Java使用静态类型检查在编译期间分析程序,确保没有类型错误.基本的思想是不要让类型错误在运行期间发生. 在各色各样的编程语言中,总共存在着两个类型检查机制:静态类型检查和动态类型检查. 静态类型检查是指通过对应用程序的源码进行分析,在编译期间就保证程序的类型安全. 动态类型检查是在程序的运行过程中,验证程序的类型安全.在Java中,编译期间使用静态类型

  • Java随机生成身份证完整示例代码

    身份证算法实现 1.号码的结构 公民身份号码是特征组合码, 由十七位数字本体码和一位校验码组成. 排列顺序从左至右依次为:六位数字地址码,八位数字出生日期码  三位数字顺序码和一位数字校验码. 2.地址码(前六位数) 表示编码对象常住户口所在县(市.旗.区)的行政区划代码,按GB/T2260的规定执行. 3.出生日期码(第七位至十四位) 表示编码对象出生的年.月.日,按GB/T7408的规定执行,年.月.日代码之间不用分隔符. 4.顺序码(第十五位至十七位) 表示在同一地址码所标识的区域范围内,

  • java实现基因序列比较的示例代码

    设计算法,计算两给定基因序列的相似程度. 人类基因由4种核苷酸,分别用字母ACTG表示.要求编写一个程序,按以下规则比较两个基因序列并确定它们的相似程度.即给出两个基因序列AGTGATG和GTTAG,它们有多相似呢?测量两个基因相似度的一种方法称为对齐.使用对齐方法可以在基因的适当位置加入空格,让两个基因的长度相等,然后根据基因的分值矩阵计算分数. 看了很多代码基本上都是用c++或者c写的,但是习惯性写java就用java实现一下 基本的思路就是,和背包问题差不多,实现还是模仿填表的形式去实现的

  • 用java实现跳动的小球示例代码

    实现效果为一个小球接触左右侧时,会反向的运动. import javafx.application.Application; import javafx.event.ActionEvent; import javafx.event.EventHandler; import javafx.scene.Group; import javafx.scene.Scene; import javafx.scene.control.Button; import javafx.scene.paint.Colo

  • 在Java中操作Zookeeper的示例代码详解

    依赖 <dependency> <groupId>org.apache.zookeeper</groupId> <artifactId>zookeeper</artifactId> <version>3.6.0</version> </dependency> 连接到zkServer //连接字符串,zkServer的ip.port,如果是集群逗号分隔 String connectStr = "192.

  • Java 静态数据初始化的示例代码

    无论创建多少个对象,静态数据都只占用一份存储区域.static关键字不能应用于局部变量,因此它只能作用于域.如果一个域是静态的基本类型域,且也没有对它进行初始化,那么它就会获得基本类型的标准初始值:如果它是一个对象引用,那么它的默认初始值就是null class Bowl { public Bowl(int marker) { System.out.println("Bowl(" + marker + ")"); } void f1(int marker) { Sy

  • Java 设置Excel条件格式示例代码(高亮条件值、应用单元格值/公式/数据条等类型)

    Java 设置Excel条件格式示例代码(高亮条件值、应用单元格值/公式/数据条等类型)

    概述 在Excel中,应用条件格式功能可以在很大程度上改进表格的设计和可读性,用户可以指定单个或者多个单元格区域应用一种或者多种条件格式.本篇文章,将通过Java程序示例介绍条件格式的设置方法,设置条件格式时,因不同设置需要,本文分别从以下示例要点来介绍: 示例1: 1. 应用条件格式用于高亮重复.唯一数值 2. 应用条件格式用于高亮峰值(最高值.最低值) 3. 应用条件格式用于高亮低于或高于平均值的数值 示例2: 1. 应用单元格值类型的条件格式 2. 应用公式类型的条件格式 3. 应用数据条

随机推荐