En informática , un autómata de Levenshtein para una cadena w y un número n es un autómata de estados finitos 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 es reconocida en el lenguaje formal 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]
Los autómatas de Levenshtein pueden utilizarse para la corrección ortográfica, al encontrar palabras en un diccionario determinado 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 de 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 lenguaje 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 de 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]
Para cualquier constante fija n , el autómata de Levenshtein para w y n puede construirse en el tiempo O(| w |). [1]
Mitankin estudia una variante de esta construcción llamada autómata universal de Levenshtein , determinado únicamente por un parámetro numérico n , que puede reconocer pares de palabras (codificadas de cierta manera por vectores de bits) que se encuentran dentro de la distancia de Levenshtein n entre sí. [3] Touzet propuso un algoritmo eficaz para construir este autómata. [4]
Una tercera construcción de autómata finito de la distancia de Levenshtein (o Damerau–Levenshtein ) son los transductores de Levenshtein de Hassan et al. , quienes muestran transductores de estados finitos que implementan la distancia de edición uno, y luego los componen para implementar distancias de edición hasta alguna constante. [5]