Trabajo en la implementación de un Árbol BK para búsqueda veloz de cadenas de texto semejantes, esto utilizando como métrica la distancia de Levenstein.
La idea es aplicar este mecanismo de búsqueda en la comparación de nombres taxonómicos de una base de datos cualquiera contra una versión indexada y almacenada en formato binario en disco del Catálogo de La Vida (COL por sus siglas en inglés) para determinar nombres de taxones “sospechosos” y sugerir alternativas.
Como primer paso ya tengo listo el árbol y el mecanismo para escribir y recuperar de disco la información indexada del COL; lo que me costo un mundo por que desde hace una eternidad no programo un recorrido en postfijo de un árbol N-ario. Los siguientes pasos consisten en desarrollar una herramienta que procese por bloques una base de datos con información taxonómica y para cada registro sospechoso sugiera una lista al tipo:
El registro «ambyguus» parece ser victima de un error léxico y probablemente el autor quiso decir: [ambiguus, ambiguous, ...]
Problemas:
La idea original consistía en hacer esto solo en los niveles taxonómicos obligatorios, de manera independiente, pero esta decisión reduce la exactitud de la identificación como sospechoso y de su sugerencia.
Ejemplo:
Si el registro se refiere a la lapa verde o Ara ambiguus pero esta escrita como Ara ambyguus
Si comparo solo ambyguus contra el catálogo de la vida retorna como sugerencias [ambiguus, ambiguous, ...].
El primero esta bien, pero el segundo es epíteto específico de un insecto y uno de un ave, por lo que quiero explorar la posibilidad de limitar un poco más los resultados para que sean más exactos. Siempre y cuando los otros niveles taxonómicos esten presentes en la BD.
Bibliografía
Burkhard, W. (1973). Some approaches to best-match file searching. Communications of the ACM, 16(4), 230-236.
Baeza-Yates, R., & Navarro, G. (1998). Fast approximate string matching in a dictionary. String Processing and Information Retrieval: A South American Symposium, 1998. Proceedings (pp. 14–22). IEEE.
(Para la próxima trato de formatear mejor las referencias o solo pongo el titulo)
