Autómata de Levenshtein
En informática , un autómata de Levenshtein para una cadena w y un número n es un autómata de estado finito que puede reconocer el conjunto de todas las cadenas cuya distancia de Levenshtein de w es como máximo n . Es decir, una cadena x está en el lenguaje formal reconocido por el autómata de Levenshtein si y solo si x puede transformarse en w mediante como máximo n inserciones, eliminaciones y sustituciones de un solo carácter. [1]
Aplicaciones
Los autómatas de Levenshtein se pueden utilizar para corregir la ortografía, al encontrar palabras en un diccionario dado que están cerca de una palabra mal escrita. En esta aplicación, una vez que se identifica una palabra como mal escrita, se puede construir su autómata Levenshtein y luego aplicarlo a todas las palabras del diccionario para determinar cuáles están cerca de la palabra mal escrita. Si el diccionario se almacena en forma comprimida como un trie , el tiempo para este algoritmo (después de que se ha construido el autómata) es proporcional al número de nodos en el trie, significativamente más rápido que usar programación dinámica para calcular la distancia de Levenshtein por separado para cada palabra del diccionario. [1]
También es posible encontrar palabras en un idioma regular , en lugar de un diccionario finito, que estén cerca de una palabra objetivo dada, calculando el autómata de Levenshtein para la palabra y luego usando una construcción de producto cartesiano para combinarlo con un autómata para el lenguaje regular, dando un autómata para el lenguaje de intersección. Alternativamente, en lugar de usar la construcción del producto, tanto el autómata de Levenshtein como el autómata para el lenguaje regular dado pueden recorrerse simultáneamente usando un algoritmo de retroceso . [1]
Los autómatas de Levenshtein se utilizan en Lucene para búsquedas de texto completo que pueden devolver documentos relevantes incluso si la consulta está mal escrita. [2]
Construcción
Para cualquier constante fijo n , el autómata Levenshtein para w y n puede ser construido en el tiempo O (| w |). [1]
Mitankin estudia una variante de esta construcción llamada autómata universal de Levenshtein , determinada solo por un parámetro numérico n , que puede reconocer pares de palabras (codificadas de cierta manera por vectores de bits) que están dentro de la distancia de Levenshtein n entre sí. [3] Touzet propuso un algoritmo eficaz para construir este autómata. [4]
Sin embargo, una tercera construcción autómata finita de la distancia de Levenshtein (o Damerau-Levenshtein ) son los transductores de Levenshtein de Hassan et al. , que muestran transductores de estado finito que implementan la distancia de edición uno, luego los componen para implementar distancias de edición hasta alguna constante. [5]
Ver también
- agrep , herramienta (implementada varias veces) para la coincidencia aproximada de expresiones regulares
- TRE , biblioteca para la coincidencia de expresiones regulares que es tolerante a las ediciones de estilo Levenshtein
Referencias
- ↑ a b c d Schulz, Klaus U .; Mihov, Stoyan (2002). "Corrección rápida de cuerdas con Levenshtein-Automata" . Revista Internacional de Análisis y Reconocimiento de Documentos . 5 (1): 67–85. CiteSeerX 10.1.1.16.652 . doi : 10.1007 / s10032-002-0082-8 . S2CID 207046453 .
- ^ McCandless, Michael (24 de marzo de 2011). "FuzzyQuery de Lucene es 100 veces más rápido en 4.0" . Cambio de bits . Consultado el 7 de junio de 2021 .
- ^ Mitankin, Petar N. (2005). Autómatas universales de Levenshtein. Edificación y Propiedades (PDF) (Tesis). Universidad de Sofía St. Kliment Ohridski.
- ^ Touzet H. (2016). "Sobre el autómata de Levenshtein y el tamaño del vecindario de una palabra" (PDF) . Teoría y aplicaciones del lenguaje y los autómatas . Apuntes de conferencias en Ciencias de la Computación. 9618 . Apuntes de conferencias en Ciencias de la Computación. págs. 207–218. doi : 10.1007 / 978-3-319-30000-9_16 . ISBN 978-3-319-29999-0.
- ^ Hassan, Ahmed; Noeman, Sara; Hassan, Hany (2008). Corrección de texto independiente del idioma utilizando autómatas de estado finito . IJCNLP.
- Autómatas finitos
- Algoritmos de coincidencia de cadenas
