La façon la plus efficace de calculer la distance Levenshtein
je viens d'implémenter un algorithme de recherche de fichier de meilleure correspondance pour trouver la correspondance la plus proche d'une chaîne dans un dictionnaire. Après avoir établi le profil de mon code, j'ai découvert que l'écrasante majorité du temps est passé à calculer la distance entre la requête et les résultats possibles. Je suis en train d'implémenter l'algorithme pour calculer la Distance Levenshtein en utilisant un tableau 2-D, ce qui fait de l'implémentation une opération O(N^2). J'espérais que quelqu'un pourrait proposer un moyen plus rapide de faire de même.
Voici mon implémentation:
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 réponses
la entrée Wikipédia sur la distance de Levenshtein a des suggestions utiles pour optimiser le calcul -- La plus applicable dans votre cas est que si vous pouvez mettre une limite k sur la distance maximale d'intérêt (tout au-delà de ce pourrait aussi bien être l'infini!) vous pouvez réduire le calcul à O(n times k) au lieu de O(n squared) (essentiellement en abandonnant dès que la distance minimale possible devient > k ).
Puisque vous êtes à la recherche de la correspondance la plus proche, vous pouvez diminuer progressivement k à la distance de la meilleure correspondance trouvée jusqu'à présent -- cela n'affectera pas le comportement du pire cas (comme les correspondances pourrait être dans l'ordre décroissant de la distance, ce qui signifie que vous ne vous renflouerez jamais plus tôt) mais le cas moyen devrait améliorer.
je crois que, si vous avez besoin d'obtenir substantiellement meilleure performance, vous pouvez avoir à accepter certains solide compromis qui calcule une distance plus approximative (et obtient ainsi "un assez bon match" plutôt que nécessairement l'optimal).
selon un commentaire sur ce blog, accélérer Levenshtein , vous pouvez utiliser VP-Trees et réaliser O(nlogn). Un autre commentaire sur le même blog pointe vers une implémentation python de VP-Trees et Levenshtein . S'il vous plaît laissez-nous savoir si cela fonctionne.
j'ai modifié la fonction VBA distance Levenshtein trouvée sur ce post pour utiliser un tableau unidimensionnel. Il fonctionne beaucoup plus vite.
'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
j'ai testé cette fonction avec la chaîne 's1' de longueur 11.304 et 's2' de longueur 5.665 (comparaisons de caractères > 64 millions). Avec la version simple dimension ci-dessus de la fonction, le temps d'exécution est d'environ 24 secondes sur ma machine. La fonction originale bidimensionnelle à laquelle j'ai fait référence dans le lien ci-dessus nécessite ~37 secondes pour les mêmes chaînes. J'ai optimisé la fonction unidimensionnelle comme montré ci-dessous et il faut ~10 secondes pour les mêmes chaînes.
'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
l'article de Wikipedia traite de votre algorithme, et de diverses améliorations. Cependant, il semble qu'au moins dans le cas général, O(N^2) est le meilleur que vous pouvez obtenir.
il y a cependant quelques améliorations si vous pouvez limiter votre problème (par exemple si vous êtes seulement intéressé par la distance si elle est plus petite que d , la complexité est O(dn) - cela pourrait avoir un sens comme un match dont la distance est proche de la longueur de la chaîne est probablement pas très intéressant ). Vois si tu peux exploiter les détails de ton problème...
Commons-lang a une mise en œuvre assez rapide. Voir http://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm .
voici ma traduction de cela en 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)
}
}
je sais que c'est très tard, mais c'est pertinent pour la discussion en cours.
comme mentionné par d'autres, si tout ce que vous voulez faire est de vérifier si la distance d'édition entre deux chaînes est dans un certain seuil k, vous pouvez réduire la complexité de temps à O(kn) . Une expression plus précise serait O ((2k+1)n) . Vous prenez une bande qui s'étend sur K cellules de chaque côté de la cellule diagonale (longueur de bande 2k+1) et de calculer le valeurs des cellules gisant sur cette bande.
fait intéressant, il y a eu une amélioration par Li et. Al. et cela a été encore réduit à O ((k+1)n).