计算Levenshtein距离的最有效方法

Question

我刚刚实现了一个最佳匹配文件搜索算法,以找到与字典中字符串最接近的匹配.在分析我的代码之后,我发现绝大部分时间花在计算查询和可能结果之间的距离上.我目前正在使用2-D数组实现算法来计算Levenshtein距离,这使得实现成为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));
}

Answer 1

关于Levenshtein距离的维基百科条目提供了有用的优化计算建议 - 在您的情况下最适用的是如果您可以设置k最大感兴趣距离(超出可能无限远的任何东西!),您可以减少计算O(n times k)而不是O(n squared)(基本上只要最小可能的距离变为放弃> k).

由于您正在寻找最接近的匹配,您可以逐渐减少k到目前为止找到的最佳匹配距离 - 这不会影响最坏情况的行为(因为匹配可能是距离的递减顺序,这意味着你'永远不会纾困,但平均情况应该有所改善.

我认为,如果你需要得到显着更好的性能,你可能不得不接受一个计算更接近的距离(因此得到"一个相当不错的比赛",而不是一定是最优的)一些有实力的妥协.

Answer 2

根据本博客的评论,Speeding Up Levenshtein,您可以使用VP-Trees并实现O(nlogn).同一博客上的另一条评论指出了VP-Trees和Levenshtein的python实现.如果有效,请告诉我们.