Algoritmo de búsqueda palabras similares (Fuzzy Search)

[marioml13]

Buenas, os planteo mi problema a ver si alguien me puede echar una mano:

Actualmente estoy trabajando con OCR para reconocer texto, tras realizar el OCR necesito realizar consultas en una base de datos, donde dicho texto (en este caso un nick de usuario) puede que sea o no encontrado.
El problema viene a la hora de aplicar el OCR ya que este falla bastante, y la mayoría de veces confunde letras, por ejemplo:
I y l
0 y O
1 e i

He pensado que antes de realizar la consulta podría buscar usando un margen de error si hay algún nick de usuario en la base de datos que se parezca al que voy a usar para realizar la consulta, y si es así, ya puedo sustituir este por el correcto.

Para ello he usado una implementación del algoritmo de búsqueda basado en la distancia Levenshtein:

http://www.codeproject.com/Articles/36869/Fuzzy-Search

El algoritmo funciona bastante bien, pero no tiene en cuenta pesos en base a los tipos frecuentes de errores, es decir yo quiero que si tengo este texto obtenido por OCR:

programadror1ntel1gente

y en la base de datos tengo estos dos usuarios: programadorinteligente y programadorontelogente, me devuelva el primero y no un empate, ya que debería tener más peso el que un 1 se convierta en una "i" que el que un 1 se convierta en una "o".

Espero haberme explicado.

Muchisimas gracias


PD: Aunque es mi primer post llevo ya varios años entrando en este foro para leer dudas que me han resuelto la vida.

PD: Necesito este algoritmo para realizar mi PFC (Proyecto fin de carrera) de la ing informática superior xD.

Un saludo

[marioml13]

Al final creo que lo he solucionado modificando el código del algoritmo de Levensthein:

Código:

public static double LevenshteinDistance(string src, string dest)
		{
			double[,] d = new double[src.Length + 1, dest.Length + 1];
            int i, j;
            double cost;
			char[] str1 = src.ToCharArray();
			char[] str2 = dest.ToCharArray();

			for (i = 0; i <= str1.Length; i++)
			{
				d[i, 0] = i*1.0;
			}
			for (j = 0; j <= str2.Length; j++)
			{
				d[0, j] = j*1.0;
			}
			for (i = 1; i <= str1.Length; i++)
			{
				for (j = 1; j <= str2.Length; j++)
				{

                    if (str1[i - 1] == str2[j - 1]){
                        cost = 0.0;
                    }else
                    {
                        cost = 1.0;
                        //El 1 con la i
                        if (str1[i - 1] == 'i' && str2[j - 1] == '1')
                            cost = 0.4;
                        if (str1[i - 1] == '1' && str2[j - 1] == 'i')
                            cost = 0.4;
                        //La l con la i
                        if (str1[i - 1] == 'l' && str2[j - 1] == 'i')
                            cost = 0.4;
                        if (str1[i - 1] == 'i' && str2[j - 1] == 'l')
                            cost = 0.4;
                        //La L con la I
                        if (str1[i - 1] == 'L' && str2[j - 1] == 'I')
                            cost = 0.4;
                        if (str1[i - 1] == 'I' && str2[j - 1] == 'L')
                            cost = 0.4;
                        //El 0 con la o
                        if (str1[i - 1] == '0' && str2[j - 1] == 'o')
                            cost = 0.4;
                        if (str1[i - 1] == 'o' && str2[j - 1] == '0')
                            cost = 0.4;
                        //El 0 con la O
                        if (str1[i - 1] == '0' && str2[j - 1] == 'O')
                            cost = 0.4;
                        if (str1[i - 1] == 'O' && str2[j - 1] == '0')
                            cost = 0.4;
                        //La o con la O
                        if (str1[i - 1] == 'o' && str2[j - 1] == 'O')
                            cost = 0.4;
                        if (str1[i - 1] == 'O' && str2[j - 1] == 'o')
                            cost = 0.4;  
                        
                    }
                        

					d[i, j] =
						Math.Min(
							d[i - 1, j] + 1,					// Deletion
							Math.Min(
								d[i, j - 1] + 1,				// Insertion
								d[i - 1, j - 1] + cost));		// Substitution

					if ((i > 1) && (j > 1) && (str1[i - 1] == str2[j - 2]) && (str1[i - 2] == str2[j - 1]))
					{
						d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost);
					}
				}
			}
            Console.WriteLine("Distancia entre: "+src+" y "+dest+" es: "+d[str1.Length, str2.Length]);
			return d[str1.Length, str2.Length];
		}