Foros del Web » Programación para mayores de 30 ;) » Programación General »

Algoritmo de búsqueda palabras similares (Fuzzy Search)

Estas en el tema de Algoritmo de búsqueda palabras similares (Fuzzy Search) en el foro de Programación General en Foros del Web. 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 ...
  #1 (permalink)  
Antiguo 11/12/2013, 11:17
 
Fecha de Ingreso: diciembre-2013
Mensajes: 3
Antigüedad: 8 años, 5 meses
Puntos: 0
Algoritmo de búsqueda palabras similares (Fuzzy Search)

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
  #2 (permalink)  
Antiguo 12/12/2013, 03:30
 
Fecha de Ingreso: diciembre-2013
Mensajes: 3
Antigüedad: 8 años, 5 meses
Puntos: 0
Respuesta: Algoritmo de búsqueda palabras similares (Fuzzy Search)

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];
		}

Etiquetas: busqueda, search, string
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 15:53.