Java滾動數(shù)組計算編輯距離操作示例

更新時間：2019年12月02日 10:12:08 作者：在線瘋狂

這篇文章主要介紹了Java滾動數(shù)組計算編輯距離操作,涉及java字符串與數(shù)組的遍歷、計算、轉(zhuǎn)換等相關(guān)操作技巧,需要的朋友可以參考下

本文實例講述了Java滾動數(shù)組計算編輯距離操作。分享給大家供大家參考，具體如下：

編輯距離（Edit Distance），也稱Levenshtein距離，是指由一個字符串轉(zhuǎn)換為另一個字符串所需的最少編輯次數(shù)。

下面的代碼摘自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];
}

實際上，上述代碼的空間復雜度還可以進一步簡化，使用一維數(shù)組替換滾動數(shù)組。

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];
}

更多關(guān)于java相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)組操作技巧總結(jié)》、《Java字符與字符串操作技巧總結(jié)》、《Java數(shù)學運算技巧總結(jié)》、《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》及《Java操作DOM節(jié)點技巧總結(jié)》

希望本文所述對大家java程序設(shè)計有所幫助。

您可能感興趣的文章: