OCR: distancia Levenshtein ponderada

Question

Estoy tratando de crear un sistema de reconocimiento óptico de caracteres con el diccionario.

De hecho no tengo un diccionario aplicado todavía =)

He oído que hay indicadores simples basados ​​en Levenstein distancia que toman en cuenta diferentes distancias entre los diferentes símbolos. P.ej. 'N' y 'H' están muy cerca uno del otro y d ("TEATRO", "TNEATRE") debe ser menor que d ("TEATRO", "TOEATRE"), lo cual es imposible usando la distancia básica de Levenstein.

¿Podría ayudarme a encontrar esa métrica, por favor?

Tanques para la atención.

Answer 1

Esto podría ser lo que buscas: http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance (y amablemente algo de código de trabajo está incluido en el enlace)

Actualización:

http://nlp.stanford.edu/IR-book/html/htmledition/edit-distance-1.html

Answer 2

Aquí es un ejemplo (C#) donde el peso de la operación "reemplazar caracteres" depende de la distancia entre los códigos de caracteres:

 static double WeightedLevenshtein(string b1, string b2) { 
     b1 = b1.ToUpper(); 
     b2 = b2.ToUpper(); 

     double[,] matrix = new double[b1.Length + 1, b2.Length + 1]; 

     for (int i = 1; i <= b1.Length; i++) { 
      matrix[i, 0] = i; 
     } 

     for (int i = 1; i <= b2.Length; i++) { 
      matrix[0, i] = i; 
     } 

     for (int i = 1; i <= b1.Length; i++) { 
      for (int j = 1; j <= b2.Length; j++) { 
       double distance_replace = matrix[(i - 1), (j - 1)]; 
       if (b1[i - 1] != b2[j - 1]) { 
        // Cost of replace 
        distance_replace += Math.Abs((float)(b1[i - 1]) - b2[j - 1])/('Z'-'A'); 
       } 

       // Cost of remove = 1 
       double distance_remove = matrix[(i - 1), j] + 1; 
       // Cost of add = 1 
       double distance_add = matrix[i, (j - 1)] + 1; 

       matrix[i, j] = Math.Min(distance_replace, 
            Math.Min(distance_add, distance_remove)); 
      } 
     } 

     return matrix[b1.Length, b2.Length] ; 
    } 

Verá cómo funciona aquí: http://ideone.com/RblFK