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 a 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 sólo si x puede transformarse en w mediante como máximo n inserciones, eliminaciones y sustituciones de un solo carácter. [1]
Los autómatas Levenshtein se pueden utilizar para la corrección ortográfica, al encontrar palabras en un diccionario determinado que se acerquen a una palabra mal escrita. En esta aplicación, una vez que se identifica que una palabra está mal escrita, se puede construir su autómata Levenshtein y luego aplicarlo a todas las palabras del diccionario para determinar cuáles se acercan a la palabra mal escrita. Si el diccionario se almacena en forma comprimida como trie , el tiempo para este algoritmo (después de que se haya 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 uno. palabra del diccionario. [1]
También es posible encontrar palabras en un lenguaje normal , en lugar de en un diccionario finito, que estén cercanas a una palabra objetivo determinada, calculando el autómata de Levenshtein para la palabra y luego usando una construcción de producto cartesiano para combinarla con un autómata para el lenguaje regular, dando un autómata para el lenguaje de intersección. Alternativamente, en lugar de utilizar la construcción del producto, tanto el autómata de Levenshtein como el autómata para el lenguaje regular dado pueden recorrerse simultáneamente utilizando un algoritmo de retroceso . [1]
Los autómatas Levenshtein se utilizan en Lucene para búsquedas de texto completo que pueden devolver documentos relevantes incluso si la consulta está mal escrita. [2]
Para cualquier constante fija n , el autómata de Levenshtein para w y n se puede construir en el tiempo O(| w |). [1]
Mitankin estudia una variante de esta construcción llamada autómata universal de Levenshtein , determinada únicamente por un parámetro numérico n , que puede reconocer pares de palabras (codificadas de cierta manera mediante vectores de bits) que se encuentran dentro de una 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 una constante. [5]