java - Java中编辑距离: How arrange the code?

Question

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

代码如下(别担心，我不希望任何人理解代码/算法，但它有效!)

代码

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

现在，我想做的(但我不知道该怎么做)是更新矩阵M里面for循环输入ClosestWords 。在 Matlab 中，这很容易:我只需将矩阵设置为某种初始形式，然后对于每个循环，我们都会从函数调用 Distance(w, s) 获得一个新矩阵。我又想修改这个新矩阵，即从中删除最后几行。我该怎么做呢？例如，我有一个 M 4 x 4 的矩阵，然后删除最后一行，得到 M_new那是 3 x 4。这可能吗？

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

最诚挚的问候，

Answer 1

Java 不太适合这种类型的工作(这里想到了 APL)。如果这不是练习，我会使用现有的库来完成此操作。如果这是一个练习，我会检查开源库是如何做到这一点的。

最后，您可以:

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

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

3) ...

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

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