Java滚动数组计算编辑距离操作示例

发布时间: 2019-12-02 13:30:10 来源: 互联网 栏目: Java 点击:

这篇文章主要介绍了Java滚动数组计算编辑距离操作,涉及java字符串与数组的遍历、计算、转换等相关操作技巧,需要的朋友可以参考下

本文实例讲述了Java滚动数组计算编辑距离操作。分享给大家供大家参考,具体如下:

编辑距离(Edit Distance),也称Levenshtein距离,是指由一个字符串转换为另一个字符串所需的最少编辑次数。

下面的代码摘自org。apache。commons。lang。StringUtils

用法示例:

StringUtils.getLevenshteinDistance(null, *)       = IllegalArgumentException
StringUtils.getLevenshteinDistance(*, null)       = IllegalArgumentException
StringUtils.getLevenshteinDistance("","")        = 0
StringUtils.getLevenshteinDistance("","a")       = 1
StringUtils.getLevenshteinDistance("aaapppp", "")    = 7
StringUtils.getLevenshteinDistance("frog", "fog")    = 1
StringUtils.getLevenshteinDistance("fly", "ant")    = 3
StringUtils.getLevenshteinDistance("elephant", "hippo") = 7
StringUtils.getLevenshteinDistance("hippo", "elephant") = 7
StringUtils.getLevenshteinDistance("hippo", "zzzzzzzz") = 8
StringUtils.getLevenshteinDistance("hello", "hallo")  = 1

Java代码:

public static int getLevenshteinDistance(String s, String t) {
  if (s == null || t == null) {
    throw new IllegalArgumentException("Strings must not be null");
  }
  int n = s.length(); // length of s
  int m = t.length(); // length of t
  if (n == 0) {
    return m;
  } else if (m == 0) {
    return n;
  }
  if (n > m) {
    // swap the input strings to consume less memory
    String tmp = s;
    s = t;
    t = tmp;
    n = m;
    m = t.length();
  }
  int p[] = new int[n+1]; //'previous' cost array, horizontally
  int d[] = new int[n+1]; // cost array, horizontally
  int _d[]; //placeholder to assist in swapping p and d
  // indexes into strings s and t
  int i; // iterates through s
  int j; // iterates through t
  char t_j; // jth character of t
  int cost; // cost
  for (i = 0; i<=n; i++) {
    p[i] = i;
  }
  for (j = 1; j<=m; j++) {
    t_j = t.charAt(j-1);
    d[0] = j;
    for (i=1; i<=n; i++) {
      cost = s.charAt(i-1)==t_j ? 0 : 1;
      // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
      d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost);
    }
    // copy current distance counts to 'previous row' distance counts
    _d = p;
    p = d;
    d = _d;
  }
  // our last action in the above loop was to switch d and p, so p now 
  // actually has the most recent cost counts
  return p[n];
}

实际上,上述代码的空间复杂度还可以进一步简化,使用一维数组替换滚动数组。

Java代码:

public int minDistance(String s, String t) {
  if (s == null || t == null) {
    throw new IllegalArgumentException("Strings must not be null");
  }
  int n = s.length(); // length of s
  int m = t.length(); // length of t
  if (n == 0) {
    return m;
  } else if (m == 0) {
    return n;
  }
  if (n > m) {
    // swap the input strings to consume less memory
    String tmp = s;
    s = t;
    t = tmp;
    n = m;
    m = t.length();
  }
  int d[] = new int[n+1]; // cost array, horizontally
  // indexes into strings s and t
  int i; // iterates through s
  int j; // iterates through t
  char t_j; // jth character of t
  int cost; // cost
  for (i = 0; i<=n; i++) {
    d[i] = i;
  }
  for (j = 1; j<=m; j++) {
    t_j = t.charAt(j-1);
    int pre = d[0];
    d[0] = j;
    for (i=1; i<=n; i++) {
      int temp = d[i];
      cost = s.charAt(i-1)==t_j ? 0 : 1;
      // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
      d[i] = Math.min(Math.min(d[i-1]+1, d[i]+1), pre+cost);
      pre = temp;
    }  
  }
  return d[n];
}

更多关于java相关内容感兴趣的读者可查看本站专题:《Java数组操作技巧总结》、《Java字符与字符串操作技巧总结》、《Java数学运算技巧总结》、《Java数据结构与算法教程》及《Java操作DOM节点技巧总结》

希望本文所述对大家java程序设计有所帮助。

本文标题: Java滚动数组计算编辑距离操作示例
本文地址: http://www.cooldogg.com/ruanjian/java/290094.html

如果认为本文对您有所帮助请赞助本站

支付宝扫一扫赞助微信扫一扫赞助

  • 支付宝扫一扫赞助
  • 微信扫一扫赞助
  • 支付宝先领红包再赞助
    声明:凡注明"本站原创"的所有文字图片等资料,版权均属编程客栈所有,欢迎转载,但务请注明出处。
    Spring boot2X负载均衡和反向代理实现过程解析Java string.trim()究竟去掉了什么
    Top 新疆喜乐彩 长江彩票计划群 极速赛车单双公式计划 快赢彩票 山东11选5开奖 上海11选5 顺发彩票计划群 百万彩票 上海11选5计划 极速赛车为什么老是输