[Grey-Walter] curioso ojo al lenguaje

[Jonathan]

El vie, 19-09-2003 a las 07:44, Francesc Benavent escribió:

> [Nota: "Distancia de Levenshtein" o distancia de edición entre dos
> palabras se define como el número entero de operaciones elementales
> (inserción, borrado y sustitución) que permite transformar una cadena
> de carácteres en la otra.]

La Distancia de Levenshtein (DL) es de un coste computacional bastante
alto (hay que construir por cada par de palabras una matriz ). Una
profesora q tuve hace unos años investigó sobre búsquedas de cadenas
similares en su tesis doctoral y definió una nueva distancia que llamó
Distancia Invariante Trasposicional (DIT), que no depende de las
operaciones de trasposición a que pueda ser sometida una cadena, por lo
que más que distancia es una semidistancia. Y su utilidad radica en que
su coste comput. es bastante menos que el de DL y que
DIT(palabra1,palabra2) <= 2*DL (palabra1,palabra2), por lo que puede
usarse como filtro para no hayar DL para cada conjunto de palabras.

Haciendo uso de esta semidistancia construyó una estructura de búsqueda
que llamó SD (Santana-Díaz) en la que se indexan las palabras de un
diccionario y es muy eficiente encontrar las más similares a una dada.
Además existe otra estructura más avanzada que se llama SDU (SD
unificada) de la cual no sabría apuntar las características ahora mismo.

Hice en su momento implementaciones medianamente eficientes (tendría que
revisarlas) de varios algoritmos de búsqueda, entre ellos estos que
nombro. Están en clases C++ con interfaz Builder (cosas de los
profesores, you know), empecé a portarlas a linux pero dejé el trabajo a
medias.

Como dato, la práctica consistía en indexar 10400 palabras en una
estructura de datos y luego encontrar esas 10400 palabras después de
haber sido aleatoriamente perturbadas con sustituciones, supresiones e
inserciones. 
Usando una estructura arbórea BK y la distancia DL se tardó 7:53 minutos
en acabar el algoritmo. Se emplearon en cambio 1:53 minutos utilizando
la distancia DIT como filtro. No tengo a mano los datos de la SD y la
SDU. 

Dicho todo esto..... no sé si encaja en a_s este tipo de cosas, si es
así y hay interés tengo algunas(poquitas) más que aportar (ingeniería
del conocimiento, ia --art, clips--, automatas celulares y "automatas
reconocedores inversos" (análisis sintáctico revolucionario ;-))).

más sobre DIT y SD aquí:

http://gedlc.ulpgc.es/docencia/doctorado/tesmar.htm
http://protos.dis.ulpgc.es/ -> docencia -> seminarios -> busqueda de
cadenas -> Estructura y esquemas de búsqueda por similitud. Son unas
imagenes pesadas y feas, pero es lo que hay.

saludos,
jonhattan

PS: anotar q sólo soy un curioso de estos temas de los q he hablado, no
me dedico a ellos activamente, pero quien sabe....