Редактировать расстояние в Java: Как расположить код? - PullRequest
Новая
       62

Редактировать расстояние в Java: Как расположить код?

0 голосов
/ 06 февраля 2020

Я работаю над проектом Java о редактировании расстояния, то есть минимальном количестве операций (из трех определенных операций см. здесь для получения дополнительной информации!). Я совершенно новичок в 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 l oop в ClosestWords. В Matlab это было бы легко: я просто установил бы матрицу в некоторый начальный вид, тогда для каждого l oop мы получили бы новую матрицу из вызова функции Distance(w, s). Эту новую матрицу я, в свою очередь, хотел бы изменить, то есть удалить из нее номер последней строки. Как мне это сделать? Например, у меня матрица M, которая равна 4 на 4, затем я удаляю последнюю строку, чтобы получить M_new, то есть 3 на 4. Возможно ли это?

Кроме того, если мне нужно строки различной длины, как я могу проверить (самым простым способом), сколько их первых букв одинаковы? То есть максимальная длина подстрок строк, начинающихся слева и равных друг другу? Например, compute и commute будут иметь три общие первые буквы (начиная слева), поэтому три первые буквы будут одинаковыми.

С уважением,

1 Ответ

0 голосов
/ 06 февраля 2020

Java не очень хорошо подходит для этого типа работы (здесь на ум приходит APL). Если это не упражнение, я бы использовал существующие библиотеки для этого. Если это упражнение, я бы проверил, как это делает библиотека с открытым исходным кодом.

В конце концов, вы можете:

1) Скопировать исходный контент во вновь распределенную матрицу меньшего размера.

2) Сдвинуть значения в вашей текущей матрице и имея внешние данные для отслеживания логического размера матрицы.

3) ...

Для вашего второго вопроса я бы добавил слова в древовидную структуру и нашел бы самую длинную ветвь, начиная с root имеет как минимум две дочерние ветви.

Или просто сортирует по алфавиту и сравнивает каждую соседнюю строку.

...