algorithm - distancias - La manera más eficiente de calcular la distancia Levenshtein

distancias de levenshtein

Question

Acabo de implementar un algoritmo de búsqueda de archivos de mejor coincidencia para encontrar la coincidencia más cercana a una cadena en un diccionario. Después de crear un perfil de mi código, descubrí que la gran mayoría del tiempo se dedica a calcular la distancia entre la consulta y los posibles resultados. Actualmente estoy implementando el algoritmo para calcular la distancia de Levenshtein usando una matriz 2-D, que hace que la implementación sea una operación O (n ^ 2). Esperaba que alguien pudiera sugerir una forma más rápida de hacer lo mismo.

Aquí está mi implementación:

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

Commons-lang tiene una implementación bastante rápida. Ver http://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm .

Aquí está mi traducción de eso 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)
}

}

Answer 2

De acuerdo con un comentario en este blog, Speeding Up Levenshtein , puedes usar VP-Trees y lograr O (nlogn). Otro comentario en el mismo blog apunta a una implementación python de VP-Trees y Levenshtein . Por favor, háganos saber si esto funciona.

Answer 3

El artículo de Wikipedia analiza su algoritmo y varias mejoras. Sin embargo, parece que, al menos en el caso general, O (n ^ 2) es lo mejor que puede obtener.

Sin embargo, hay algunas mejoras si puedes restringir tu problema (por ejemplo, si solo estás interesado en la distancia si es más pequeña que d , la complejidad es O (dn) , esto podría tener sentido ya que la distancia es cercana a la longitud de la cuerda probablemente no sea muy interesante). Vea si puede explotar los detalles de su problema ...

Answer 4

La entrada de wikipedia en la distancia de Levenshtein tiene sugerencias útiles para optimizar el cálculo, la más aplicable en su caso es que si puede poner un límite k en la distancia máxima de interés (¡cualquier cosa más allá de eso podría ser infinito!) Puede reduzca el cálculo a O(n times k) lugar de O(n squared) (básicamente renunciando tan pronto como la distancia mínima posible sea > k ).

Dado que está buscando la coincidencia más cercana, puede disminuir progresivamente k hasta la distancia de la mejor coincidencia encontrada hasta el momento; esto no afectará el peor de los casos (ya que las coincidencias pueden ser en orden decreciente de distancia, lo que significa que nunca saldré de allí más pronto), pero el caso promedio debería mejorar.

Creo que, si necesita obtener un rendimiento sustancialmente mejor, es posible que tenga que aceptar un compromiso fuerte que calcule una distancia más aproximada (y así obtener "una coincidencia razonablemente buena" en lugar de necesariamente la óptima).

Answer 5

Modifiqué la función de distancia VBA de Levenshtein que se encuentra en esta post para usar una matriz unidimensional. Se realiza mucho más rápido.

''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

He probado esta función con la cadena ''s1'' de longitud 11.304 y ''s2'' de longitud 5.665 (> 64 millones de comparaciones de caracteres). Con la versión de una dimensión anterior de la función, el tiempo de ejecución es ~ 24 segundos en mi máquina. La función bidimensional original a la que hice referencia en el enlace de arriba requiere ~ 37 segundos para las mismas cadenas. He optimizado la función dimensional única adicionalmente como se muestra a continuación y requiere ~ 10 segundos para las mismas cadenas.

''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

Answer 6

Sé que esto es muy tarde, pero es relevante para la discusión en cuestión.

Como lo mencionaron otros, si todo lo que desea hacer es verificar si la distancia de edición entre dos cadenas está dentro de algún umbral k, puede reducir la complejidad del tiempo a O (kn) . Una expresión más precisa sería O ((2k + 1) n) . Usted toma una tira que abarca celdas k a cada lado de la celda diagonal (longitud de la tira 2k + 1) y calcula los valores de las celdas que se encuentran en esta banda.

Curiosamente, ha habido una improvement por Li et. Alabama. y esto se ha reducido aún más a O ((k + 1) n).