Fast aproximate string matching with finite automata

• Autores: Mans Hulden
• Localización: Procesamiento del lenguaje natural, ISSN 1135-5948, Nº. 43, 2009, págs. 57-64
• Idioma: inglés
• Títulos paralelos:
  • Rapida búsqueda aproximada con autómatas de estado finito
• Enlaces
  • Texto completo
• Resumen
  • español

    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.

  • English

    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.

• Referencias bibliográficas
  • Aho, Alfred V., John E. Hopcroft, and Jeffrey D. Ullman. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley.
  • Beesley, Kenneth and Lauri Karttunen. 2003. Finite-State Morphology. CSLI, Stanford.
  • Hart, P.E., N.J. Nilsson, and B. Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on...
  • Hulden, Mans. 2009. Foma: a finite-state compiler and library. In EACL 2009 Proceedings, pages 29–32.
  • Oflazer, Kemal. 1996. Error-tolerant finite-state recognition with applications to morphological analysis and spelling correction. Computational...
  • Pearl, Judea. 1984. Heuristics: intelligent search strategies for computer problem solving. Addison-Wesley.
  • Schulz, Klaus and Stoyan Mihov. 2002. Fast string correction with Levenshtein automata. International Journal on Document Analysis and Recognition,...
  • Tarjan, Robert E. 1972. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1(2):146–160