Подтвердить что ты не робот

Самый эффективный способ расчета расстояния Левенштейн

Я только что реализовал алгоритм поиска наилучшего соответствия, чтобы найти самое близкое соответствие со строкой в ​​словаре. Профилировав мой код, я узнал, что в подавляющем большинстве случаев вычисляется расстояние между запросом и возможными результатами. В настоящее время я реализую алгоритм вычисления расстояния Левенштейна с использованием 2-мерного массива, что делает реализацию 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));
 }
4b9b3361

ОТВЕТЫ

Ответ 1

запись в википедии на расстоянии Левенштейна имеет полезные предложения для оптимизации вычислений - наиболее применимым в вашем случае является то, что если вы можете положить связанная k на максимальном расстоянии от интереса (все, что может быть бесконечно!), вы можете уменьшить вычисление до O(n times k) вместо O(n squared) (в основном, отказываясь, как только минимальное возможное расстояние становится > k).

Поскольку вы ищете ближайшее совпадение, вы можете постепенно уменьшать k до расстояния наилучшего совпадения, найденного до сих пор - это не повлияет на поведение худшего случая (так как совпадения могут быть в порядке убывания расстояния, то есть вы никогда не сможете выручить раньше), но средний случай должен улучшиться.

Я считаю, что если вам нужно получить более высокую производительность, вам, возможно, придется принять какой-то сильный компромисс, который вычисляет более приблизительное расстояние (и, таким образом, получает "достаточно хорошее соответствие", а не обязательно оптимальное).

Ответ 2

Согласно комментарию к этому блогу, Speeding Up Levenshtein, вы можете использовать VP-Trees и достичь O (nlogn). Еще один комментарий к тому же блогу указывает на реализацию python VP-Trees и Levenshtein. Пожалуйста, сообщите нам, если это сработает.

Ответ 3

Я изменил функцию VBA на расстоянии Левенштейна, найденную на этом сообщении, чтобы использовать одномерный массив. Он работает намного быстрее.

'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)

Public Function LevenshteinDistance2(ByRef s1 As String, ByRef s2 As String) As Long
Dim L1 As Long, L2 As Long, D() As Long, LD As Long 'Length of input strings and distance matrix
Dim i As Long, j As Long, ss2 As Long, ssL As Long, cost As Long 'loop counters, loop step, loop start, and cost of substitution for current letter
Dim cI As Long, cD As Long, cS As Long 'cost of next Insertion, Deletion and Substitution
Dim L1p1 As Long, L1p2 As Long 'Length of S1 + 1, Length of S1 + 2

L1 = Len(s1): L2 = Len(s2)
L1p1 = L1 + 1
L1p2 = L1 + 2
LD = (((L1 + 1) * (L2 + 1))) - 1
ReDim D(0 To LD)
ss2 = L1 + 1

For i = 0 To L1 Step 1: D(i) = i: Next i                'setup array positions 0,1,2,3,4,...
For j = 0 To LD Step ss2: D(j) = j / ss2: Next j        'setup array positions 0,1,2,3,4,...

For j = 1 To L2
    ssL = (L1 + 1) * j
    For i = (ssL + 1) To (ssL + L1)
        If Mid$(s1, i Mod ssL, 1) <> Mid$(s2, j, 1) Then cost = 1 Else cost = 0
        cI = D(i - 1) + 1
        cD = D(i - L1p1) + 1
        cS = D(i - L1p2) + cost

        If cI <= cD Then 'Insertion or Substitution
            If cI <= cS Then D(i) = cI Else D(i) = cS
        Else 'Deletion or Substitution
            If cD <= cS Then D(i) = cD Else D(i) = cS
        End If
    Next i
Next j

LevenshteinDistance2 = D(LD)
End Function

Я тестировал эту функцию со строкой 's1' длины 11,304 и 's2' длиной 5665 ( > 64 миллиона сопоставлений символов). С вышеупомянутой одноразмерной версией функции время выполнения составляет ~ 24 секунды на моей машине. Первоначальная двумерная функция, на которую я ссылался выше, требует ~ 37 секунд для тех же строк. Я оптимизировал одномерную функцию дальше, как показано ниже, и для тех же строк требуется ~ 10 секунд.

'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)
Public Function LevenshteinDistance(ByRef s1 As String, ByRef s2 As String) As Long
Dim L1 As Long, L2 As Long, D() As Long, LD As Long         'Length of input strings and distance matrix
Dim i As Long, j As Long, ss2 As Long                       'loop counters, loop step
Dim ssL As Long, cost As Long                               'loop start, and cost of substitution for current letter
Dim cI As Long, cD As Long, cS As Long                      'cost of next Insertion, Deletion and Substitution
Dim L1p1 As Long, L1p2 As Long                              'Length of S1 + 1, Length of S1 + 2
Dim sss1() As String, sss2() As String                      'Character arrays for string S1 & S2

L1 = Len(s1): L2 = Len(s2)
L1p1 = L1 + 1
L1p2 = L1 + 2
LD = (((L1 + 1) * (L2 + 1))) - 1
ReDim D(0 To LD)
ss2 = L1 + 1

For i = 0 To L1 Step 1: D(i) = i: Next i                    'setup array positions 0,1,2,3,4,...
For j = 0 To LD Step ss2: D(j) = j / ss2: Next j            'setup array positions 0,1,2,3,4,...

ReDim sss1(1 To L1)                                         'Size character array S1
ReDim sss2(1 To L2)                                         'Size character array S2
For i = 1 To L1 Step 1: sss1(i) = Mid$(s1, i, 1): Next i    'Fill S1 character array
For i = 1 To L2 Step 1: sss2(i) = Mid$(s2, i, 1): Next i    'Fill S2 character array

For j = 1 To L2
    ssL = (L1 + 1) * j
    For i = (ssL + 1) To (ssL + L1)
        If sss1(i Mod ssL) <> sss2(j) Then cost = 1 Else cost = 0
        cI = D(i - 1) + 1
        cD = D(i - L1p1) + 1
        cS = D(i - L1p2) + cost
        If cI <= cD Then 'Insertion or Substitution
            If cI <= cS Then D(i) = cI Else D(i) = cS
        Else 'Deletion or Substitution
            If cD <= cS Then D(i) = cD Else D(i) = cS
        End If
    Next i
Next j

LevenshteinDistance = D(LD)
End Function

Ответ 4

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

Однако есть некоторые улучшения, если вы можете ограничить свою проблему (например, если вас интересует только расстояние, если оно меньше d, сложность O (dn) - это может иметь смысл в качестве соответствия, расстояние которого близко к длина строки, вероятно, не очень интересна). Посмотрите, можете ли вы использовать специфику своей проблемы...

Ответ 5

Commons-lang имеет довольно быструю реализацию. См. http://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm.

Здесь мой перевод этого в Scala:

// The code below is based on code from the Apache Commons lang project.
/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements. See the NOTICE file distributed with this
 * work for additional information regarding copyright ownership. The ASF
 * licenses this file to You under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance with the
 * License. You may obtain a copy of the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations
 * under the License.
 */
/**
* assert(levenshtein("algorithm", "altruistic")==6)
* assert(levenshtein("1638452297", "444488444")==9)
* assert(levenshtein("", "") == 0)
* assert(levenshtein("", "a") == 1)
* assert(levenshtein("aaapppp", "") == 7)
* assert(levenshtein("frog", "fog") == 1)
* assert(levenshtein("fly", "ant") == 3)
* assert(levenshtein("elephant", "hippo") == 7)
* assert(levenshtein("hippo", "elephant") == 7)
* assert(levenshtein("hippo", "zzzzzzzz") == 8)
* assert(levenshtein("hello", "hallo") == 1)
*
*/
def levenshtein(s: CharSequence, t: CharSequence, max: Int = Int.MaxValue) = {
import scala.annotation.tailrec
def impl(s: CharSequence, t: CharSequence, n: Int, m: Int) = {
  // Inside impl n <= m!
  val p = new Array[Int](n + 1) // 'previous' cost array, horizontally
  val d = new Array[Int](n + 1) // cost array, horizontally

  @tailrec def fillP(i: Int) {
    p(i) = i
    if (i < n) fillP(i + 1)
  }
  fillP(0)

  @tailrec def eachJ(j: Int, t_j: Char, d: Array[Int], p: Array[Int]): Int = {
    d(0) = j
    @tailrec def eachI(i: Int) {
      val a = d(i - 1) + 1
      val b = p(i) + 1
      d(i) = if (a < b) a else {
        val c = if (s.charAt(i - 1) == t_j) p(i - 1) else p(i - 1) + 1
        if (b < c) b else c
      }
      if (i < n)
        eachI(i + 1)
    }
    eachI(1)

    if (j < m)
      eachJ(j + 1, t.charAt(j), p, d)
    else
      d(n)
  }
  eachJ(1, t.charAt(0), d, p)
}

val n = s.length
val m = t.length
if (n == 0) m else if (m == 0) n else {
  if (n > m) impl(t, s, m, n) else impl(s, t, n, m)
}

}

Ответ 6

Я знаю, что это очень поздно, но это актуально для обсуждения.

Как уже упоминалось другими, если все, что вы хотите сделать, - проверить, находится ли расстояние редактирования между двумя строками в пределах некоторого порога k, вы можете уменьшить сложность времени до O (kn). Более точное выражение было бы O ((2k + 1) n). Вы берете полосу, которая охватывает k клеток по обе стороны диагональной ячейки (длина полосы 2k + 1) и вычисляет значения клеток, лежащих на этой полосе.

Интересно, что было улучшение by Li et. и др. и это было далее уменьшено до O ((k + 1) n).