Buscador de palabras por similitud en Flash

Supongamos que tenemos un buscador en Flash para una página de turismo en Argentina.

En esta página probablemente contemos con muchas provincias, por ejemplo "Buenos Aires". Si el usuario ingresa cualquiera de estas búsquedas, va a obtener los resultados esperados (a menos que sea case intensive):

• buenos aires
  
• BuEnoS AiReS (o cualquier otra combinación de de mayúsculas y minúsculas)
  
• bueno

Pero si pone una letra de menos (que no sea la última), el buscador va a tener problemas.

• Buenoz Aires
  
• Buens Aires
  
• BuXnos Aires

Pero, esto tiene solución. Vamos a emplear una función que nos diga cuántas letras hay que cambiar, quitar o agregar para convertir una cadena en otra (lo que se denomina "distancia levenshtein entre dos cadenas"). En php esta función se llama levenshtein (como es lógico) y forma parte de las funciones nativas del lenguaje.

Lamentablemente en Flash no tenemos nada parecido. Entonces, tenemos que crear la función "a mano".

Un ejemplo sería éste que nos dice cúales son las capitales de las provincias (si desconocen los nombres de las provincias argentinas prueben con "Buen Aires", "Formoza", "entren rio", etc.)



La función podría ser ésta:

Código :

levenshtein = function (cadena1:String, cadena2:String) {
   cadena1.toLowerCase ();
   cadena2.toLowerCase ();
   //
   var arrayCadena1 = new Array ();
   var arrayCadena2 = new Array ();
   //
   var largoMax = Math.max (cadena1.length, cadena2.length);
   var cadenaMax = (cadena1.length == largoMax) ? "Cadena1" : "Cadena2";
   var cadenaMin = (cadenaMax == "Cadena1") ? "Cadena2" : "Cadena1";
   //
   arrayCadena1 = (cadena1.length == largoMax) ? cadena1.split ("") : cadena2.split ("");
   arrayCadena2 = (cadena1.length == largoMax) ? cadena2.split ("") : cadena1.split ("");
   var valor = 0;
   for (var a in arrayCadena1) {
      if (arrayCadena1[a] != arrayCadena2[a]) {
         valor++;
      }
   }
   return valor;
};

Esta función funciona como podría esperarse. Donde el valor devuelto es la distancia de la que habíamos hablado antes.

Pero tenemos un problema con búsquedas de múltiples palabras. Volvamos al ejemplo de las provincias argentinas.

Obviamente, esta función podría ser agregada a un buscador. Entonces, tenemos 2 provincias, Jujuy y Buenos Aires.

Si buscamos Buenos Ayres y el buscador nos devuelve la palabra que más se acerca a nuestra entrada, obviamente recibiremos Buenos Aires como salida. Pero si buscamos Junos Aires, recibiremos Jujuy. Aunque esa búsqueda tiene solo 2 letras en común con Jujuy y 9 con Buenos Aires (10 si contamos el espacio)

Pero si lo analizan se van a dar cuenta que al faltar una letra (la B está reemplazada por una J, pero la e simplemente no está), nuestra función comienza a comparar caracteres equivocados. Recordemos que busca los caracteres del mismo índice y no hace una búsqueda caracter a caracter (que demoraría mucho más).

Entonces, para propósitos prácticos armé una segunda función que emplea a la primera, pero que agrega un poco más de funcionalidad:

Código :

levenshtein2 = function (cadena1:String, cadena2:String) {
   //
   var miValor = 0;
   var arrayPalabras1 = new Array ();
   var arrayPalabras2 = new Array ();
   var largoMax = Math.max (arrayPalabras1.length, arrayPalabras2.length) + 1;
   //
   arrayPalabras1 = cadena1.split (" ");
   arrayPalabras2 = cadena2.split (" ");
   //
   // Si los arrays tienen distinto número de elementos, agregamos los que hacían falta
   for (i = 0; i <= largoMax; i++) {
      if (arrayPalabras1[i] == undefined) {
         arrayPalabras1[i] = "";
      }
      if (arrayPalabras2[i] == undefined) {
         arrayPalabras2[i] = "";
      }
   }
   //
   for (i = 0; i <= largoMax; i++) {
      miValor += levenshtein (arrayPalabras1[i], arrayPalabras2[i]);
   }
   return miValor;
};

Recordemos que para usar levenshtein2 tenemos que definir la función levenshtein primero (o juntarlas en una sola función, lo que complicaría más entender su funcionamiento, algo especialmente tonto en un tutorial)

Espero les sea útil, últimamente vi en el foro varios pedidos de buscadores y creo que la búsqueda por similitud es algo a tener en cuenta.

¿Sabes SQL? ¿No-SQL? Aprende MySQL, PostgreSQL, MongoDB, Redis y más con el Curso Profesional de Bases de Datos que empieza el martes, en vivo.