Fast approximate string matching with finite automata

Abstract

En este artículo se presenta un algoritmo eficiente para dada una cadena de caracteres extraer las cadenas más cercanas de un autómata de estado finitos según alguna métrica de distancia. El algoritmo puede ser adaptado con el fin de beneficiarse de una variedad de métricas para determinar la similitud entre palabras.

We present a fast algorithm for finding approximate matches of a string in a finite-state automaton, given some metric of similarity. The algorithm can be adapted to use a variety of metrics for determining the distance between two words.