Ich habe gerade einen Suchalgorithmus für die beste Übereinstimmungsdatei implementiert, um die beste Übereinstimmung mit einer Zeichenfolge in einem Wörterbuch zu finden. Nachdem ich meinen Code profiliert hatte, stellte ich fest, dass die überwiegende Mehrheit der Zeit damit verbracht wird, die Entfernung zwischen der Abfrage und den möglichen Ergebnissen zu berechnen. Ich implementiere derzeit den Algorithmus zur Berechnung der Levenshtein-Distanz unter Verwendung eines 2D-Arrays, wodurch die Implementierung zu einer O (n ^ 2) -Operation wird. Ich hatte gehofft, jemand könnte einen schnelleren Weg vorschlagen, dasselbe zu tun.

Hier ist meine Implementierung:

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