Este trabajo trata aspectos teóricos y experimentales en torno al problema de la búsqueda de las cadenas más similares a una dada. El concepto de similitud es en el sentido de la distancia de Levenshtein, DL. El objetivo que se persigue es la optimización de los recursos de tiempo y espacio de los esquemas de búsqueda y de la estructura de datos que los soporta.
Se define una nueva distancia que se ha denominado distancia invariante trasposicional, DIT, debido al hecho de que su valor no depende de las operaciones de trasposición a que pueda ser sometida una cadena. Si bien DIT no puede usarse por si sola para la determinación de las cadenas más similares, su importancia deviene de la circunstancia de que su valor entre
dos cadenas es siempre inferior o igual a la DL entre estas dos mismas cadenas, siendo su coste computacional sensiblemente inferior; lo cual puede ser aplicado para la construcción de un filtro adaptivo DIT/DL que tenga por misión reducir el número de cadenas de la base de datos a las que se les calcula la DL con la cadena de búsqueda.
Fuente: http://www.gedlc.ulpgc.es
