Editar algoritmo de distancia

Question

Tengo un diccionario de 'n' palabras dadas y hay 'm' Consultas para responder. Quiero salida el número de palabras en el diccionario que se distancia de edición 1 o 2. Quiero optimizar el resultado conjunto dado que n y m son aproximadamente 3000.

Editar añadió de respuesta a continuación:

Trataré de decirlo de otra manera.

Inicialmente hay 'n' palabras dadas como un conjunto de palabras del diccionario. Se dan las siguientes 'm' palabras que son palabras de consulta y para cada palabra de consulta, necesito encontrar si la palabra ya existe en Diccionario (Editar Distancia '0') o el recuento total de palabras en el diccionario que están a distancia de edición 1 o 2 de las palabras del diccionario.

Espero que la pregunta sea ahora clara.

Bueno, se agota el tiempo si la Complejidad del Tiempo es (m * n) n.El uso ingenuo del Algoritmo de Distancia de Edición DP expira. Incluso calculando los elementos diagonales de 2k + 1 veces hacia afuera donde k es el umbral aquí k = 3 en el caso anterior.

Answer 1

Quiere usar el Levenshtein distance entre dos palabras, pero supongo que lo sabe porque eso es lo que dicen las etiquetas de la pregunta.

Tendría que repetir su Lista (suposición) y comparar cada palabra en la lista con la consulta actual que está ejecutando. Puede construir un BK-tree para limitar su espacio de búsqueda, pero eso suena como una exageración si solo tiene ~ 3000 palabras.

var upperLimit = 2; 
var allWords = GetAllWords(); 
var matchingWords = allWords 
     .Where(word => Levenshtein(query, word) <= upperLimit) 
     .ToList(); 

Agregado después de editar pregunta original

encontrar casos en los que la distancia = 0 sería fácil Contiene-consultas si tiene un diccionario de mayúsculas y minúsculas. Aquellos casos donde la distancia < = 2 requeriría un escaneo completo del espacio de búsqueda, 3000 comparaciones por palabra de consulta. Suponiendo que una cantidad igual de palabras de consulta daría como resultado 9 millones de comparaciones.

Mencionas que se agota el tiempo de espera, así que supongo que tienes un tiempo de espera configurado? ¿Podría su velocidad ser debido a una implementación pobre o lenta del cálculo de Levenshtein?

Graph showing visited search space using a bk-tree with different amount of input http://www.students.itu.edu.tr/~yazicivo/bk-tree-report.png gráfico anterior es robado de CLiki: bk-tree

Como se ve, el uso de bk-árbol con una distancia de edición < = 2 sólo sería visitar alrededor del 1% del espacio de búsqueda, pero eso es suponiendo que usted tiene una muy grande datos de entrada, en su caso hasta medio millón de palabras. Asumiría números similares en su caso, pero una cantidad tan baja de entradas no causaría muchos problemas incluso si está almacenado en una Lista/Diccionario.

Answer 2

Voy a tratar de decirlo de otra manera.

Inicialmente hay 'n' palabras dadas como un conjunto de palabras del diccionario. Se dan 'm' palabras que son palabras de consulta y para cada palabra de consulta, necesito encontrar si la palabra ya existe en Diccionario (Editar Distancia '0') o la cuenta total de palabras en el diccionario que están a distancia de edición 1 o 2 de las palabras del diccionario.

Espero que la pregunta sea ahora clara.

Bueno, se agota el tiempo si la Complejidad del Tiempo es (m * n) * n.El uso ingenuo del Algoritmo de Distancia de Edición DP expira. Incluso Cálculo de los elementos diagonales de 2 * k + 1 veces en donde k es el umbral aquí k = 3 en el caso anterior.

PD: BK Tree debería ser suficiente. Cualquier enlace sobre implementación en C++.

Answer 3

public class Solution { 
    public int minDistance(String word1, String word2) { 
     int[][] table = new int[word1.length()+1][word2.length()+1]; 
     for(int i = 0; i < table.length; ++i) { 
      for(int j = 0; j < table[i].length; ++j) { 
       if(i == 0) 
        table[i][j] = j; 
       else if(j == 0) 
        table[i][j] = i; 
       else { 
        if(word1.charAt(i-1) == word2.charAt(j-1)) 
         table[i][j] = table[i-1][j-1]; 
        else 
         table[i][j] = 1 + Math.min(Math.min(table[i-1][j-1], 
          table[i-1][j]), table[i][j-1]); 
       } 
      } 
     } 
     return table[word1.length()][word2.length()]; 
    } 
}