Наиболее эффективный способ расчета расстояния Левенштейна
Я только что реализовал алгоритм поиска файла наилучшего совпадения, чтобы найти наиболее близкое совпадение со строкой в словаре. После профилирования моего кода я обнаружил, что подавляющее большинство времени тратится на вычисление расстояния между запросом и возможными результатами. В настоящее время я реализую алгоритм для вычисления расстояния Левенштейна с использованием двумерного массива, что делает реализацию операцией 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));
}
6 ответов
В статье в Википедии о расстоянии Левенштейна есть полезные советы по оптимизации вычислений - наиболее применимым в вашем случае является то, что если вы можете поставить ограничение k на максимальной дистанции интереса (все, что может быть равно бесконечности!) вы можете уменьшить вычисление до O(n times k) вместо O(n squared) (в основном, сдаваясь, как только становится минимально возможное расстояние > k).
Так как вы ищете ближайший матч, вы можете постепенно уменьшать k на расстоянии лучшего совпадения, найденного до сих пор - это не повлияет на поведение наихудшего случая (так как совпадения могут быть в порядке убывания расстояния, что означает, что вы никогда не сможете спастись быстрее), но средний случай должен улучшиться.
Я считаю, что если вам нужно значительно повысить производительность, вам, возможно, придется пойти на какой-то сильный компромисс, который вычисляет более приблизительное расстояние (и, таким образом, получается "достаточно хорошее совпадение", а не обязательно оптимальное).
Согласно комментарию в этом блоге " Ускорение Левенштейна", вы можете использовать VP-Trees и достигать O(nlogn). Еще один комментарий в том же блоге указывает на реализацию на VP-деревьях и Левенштейне. Пожалуйста, дайте нам знать, если это работает.
Я изменил 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
В статье Википедии обсуждается ваш алгоритм и различные улучшения. Однако, похоже, что по крайней мере в общем случае O(n^2) - лучшее, что вы можете получить.
Однако есть некоторые улучшения, если вы можете ограничить свою проблему (например, если вас интересует только расстояние, если оно меньше d, сложность равна O (dn) - это может иметь смысл, поскольку совпадение, расстояние которого близко к длине строки, равно наверное не очень интересно). Посмотрите, сможете ли вы использовать особенности вашей проблемы...
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)
}
}
Я знаю, что очень поздно, но это актуально для обсуждения.
Как уже упоминалось другими, если все, что вы хотите сделать, это проверить, находится ли расстояние редактирования между двумя строками в пределах некоторого порога k, вы можете уменьшить сложность времени до O (kn). Более точное выражение будет O ((2k+1) n). Вы берете полосу, которая охватывает k ячеек по обе стороны от диагональной ячейки (длина полосы 2k+1), и вычисляете значения ячеек, лежащих на этой полосе.
Интересно, что Li et. и др. и это было дополнительно уменьшено до O((k+1)n).