Java中的编辑距离：如何安排代码？

Question

我正在研究一个关于编辑距离的 Java 项目，即最小操作数（在定义的三个操作中，请参阅 here 了解更多信息！）。我对 Java 完全陌生，它似乎是一种很棒的面向对象语言，但可能不像 Matlab 那样面向数字。问题是我不知道 Matlab 或 Python 中的所有相应函数在 Java 中有哪些可以实现我对这个项目的解决方案，所以我需要的只是一点建设性的帮助。

代码如下（别担心，我不指望任何人都能理解 code/algorithm，但它确实有效！）

代码

import java.util.LinkedList;
import java.util.List;

public class ClosestWords {
  LinkedList<String> closestWords = null;
  int closestDistance = -1;

  int[][] partDist(String w1, String w2, int w1len, int w2len) {
      int[][] M = new int[w1len+1][w2len+1];
      for(int i=0;i<=w1len;i++) {
          for(int j=0;j<=w2len;j++) {
              if( i == 0) {
                  M[i][j] = j;
                  }
              else if(j==0) {
                  M[i][j] = i;
                  }
              else {
                  char a = w1.charAt(i-1);
                  char b = w2.charAt(j-1);
                  int I = (a == b ? 0:1);
                  M[i][j] = Math.min(Math.min(M[i-1][j]+1,M[i][j-1]+1),M[i-1][j-1]+I);
              }
          }
      }
  return M;
  }

  int[][] Distance(String w1, String w2) {
    return partDist(w1, w2, w1.length(), w2.length());
  }

  public ClosestWords(String w, List<String> wordList) {
      for (String s : wordList) {
          int[][] M = Distance(w, s);
          int dist = M[w.length()-1][s.length()-1];
          // int dist = Distance(w, s);
          // System.out.println("d(" + w + "," + s + ")=" + dist);
          if (dist < closestDistance || closestDistance == -1) {
              closestDistance = dist;
              closestWords = new LinkedList<String>();
              closestWords.add(s);
              }
          else if (dist == closestDistance)
              closestWords.add(s);
          }
      }

  int getMinDistance() {
    return closestDistance;
  }

  List<String> getClosestWords() {
    return closestWords;
  }
}

现在，我想做的（但我不知道该怎么做）是更新 ClosestWords 中 for 循环内的矩阵 M。在 Matlab 中，这很容易：我只需将矩阵设置为某种初始形式，然后对于每个循环，我们将从函数调用 Distance(w, s) 中获得一个新矩阵。反过来，我想修改这个新矩阵，即从中删除一些最后的行。我该怎么做呢？例如，我有一个 4 乘 4 的 M 矩阵，然后我删除最后一行，所以我得到 3 乘 4 的 M_new。这可能吗？

此外，如果我必须使用可能不同长度的字符串，我如何检查（以最简单的方式）它们的第一个字母中有多少是相同的？也就是说，从左边开始并且彼此相等的字符串的子串的最大长度？例如，compute 和 commute 将有三个共同的首字母（从左边开始），因此首字母中的三个相同。

此致，

Answer 1

Java 不太适合这类工作（这里想到 APL）。如果这不是一个练习，我会使用现有的库来做到这一点。如果这是一个练习，我会检查一个开源库是如何做到这一点的。

最后，你可以：

1) 将原始内容复制到一个新分配的较小尺寸的矩阵中。

2) 移动当前矩阵中的值并使用外部数据来跟踪矩阵的逻辑大小。

3) ...

对于你的第二个问题，我会将单词添加到树结构中，并找到从根开始的最长子分支，该子分支至少有两个子分支。

或者简单地按字母顺序排序并比较每个相邻的字符串。

Java中的编辑距离：如何安排代码？

Edit distance in Java: How arrange the code?

java

edit-distance