Я только что реализовал алгоритм поиска файла наилучшего совпадения, чтобы найти наиболее близкое совпадение со строкой в ​​словаре. После профилирования моего кода я обнаружил, что подавляющее большинство времени тратится на вычисление расстояния между запросом и возможными результатами. В настоящее время я реализую алгоритм для вычисления расстояния Левенштейна с использованием двумерного массива, что делает реализацию операцией O (n ^ 2). Я надеялся, что кто-то может предложить более быстрый способ сделать то же самое.

Вот моя реализация:

public int calculate(String root, String query)
{
  int arr[][] = new int[root.length() + 2][query.length() + 2];

  for (int i = 2; i < root.length() + 2; i++)
  {
    arr[i][0] = (int) root.charAt(i - 2);
    arr[i][1] = (i - 1);
  }

  for (int i = 2; i < query.length() + 2; i++)
  {
    arr[0][i] = (int) query.charAt(i - 2);
    arr[1][i] = (i - 1);
  }

  for (int i = 2; i < root.length() + 2; i++)
  {
    for (int j = 2; j < query.length() + 2; j++)
    {
      int diff = 0;
      if (arr[0][j] != arr[i][0])
      {
        diff = 1;
      }
      arr[i][j] = min((arr[i - 1][j] + 1), (arr[i][j - 1] + 1), (arr[i - 1][j - 1] + diff));
    }
  }
  return arr[root.length() + 1][query.length() + 1];
}

public int min(int n1, int n2, int n3)
{
  return (int) Math.min(n1, Math.min(n2, n3));
}