Expresiones Regulares y Métodos de Estados Finitos

Técnicas prácticas basadas en lenguajes regulares — coincidencia de patrones con expresiones regulares y mapeo de cadena a cadena con transductores de estados finitos — que manejan la tokenización, normalización y análisis morfológico de manera eficiente.

Definition

Los métodos de estados finitos son técnicas de procesamiento del lenguaje en las que los patrones y mapeos se expresan como expresiones regulares o autómatas y transductores de estados finitos, garantizando un reconocimiento eficiente en tiempo lineal.

Scope

Cubre las expresiones regulares como un lenguaje de patrones sobre cadenas, los autómatas y transductores de estados finitos como su realización computacional, y su aplicación a la normalización de texto, tokenización, ortografía y morfología computacional. Incluye métodos de estados finitos ponderados utilizados en el procesamiento del habla y el procesamiento superficial. La teoría fonológica completa y el análisis sintáctico profundo están fuera del alcance.

Core questions

• ¿Cómo pueden las expresiones regulares especificar y extraer patrones textuales con precisión?
• ¿Cómo mapean los transductores de estados finitos las formas superficiales a los análisis léxicos, como en la morfología?
• ¿Por qué se prefieren los métodos de estados finitos para la tokenización y la normalización?

Key concepts

• expresión regular
• transductor de estados finitos
• tokenización
• normalización de texto
• análisis morfológico
• morfología de dos niveles
• autómatas ponderados
• distancia de edición

Key theories

Modelos regulares de morfología y fonología

El resultado de que las reglas de reescritura fonológica y las alternancias morfológicas pueden compilarse en transductores de estados finitos, haciendo del análisis y la generación un único marco eficiente.

Equivalencia de expresiones regulares y autómatas finitos

Las expresiones regulares, las gramáticas regulares y los autómatas de estados finitos describen exactamente los lenguajes regulares, por lo que un patrón declarativo puede compilarse en un reconocedor eficiente.

History

Las expresiones regulares entraron en la computación a partir del trabajo de Kleene y se volvieron omnipresentes en las herramientas de texto. En la década de 1980, la morfología de dos niveles de Koskenniemi y la compilación de reglas fonológicas en transductores por Kaplan y Kay establecieron la tecnología de estados finitos como la herramienta principal del procesamiento morfológico, un enfoque consolidado en el manual de Beesley y Karttunen.

Debates

¿Hasta dónde pueden escalar los métodos de estados finitos?

Las técnicas de estados finitos son extremadamente eficientes pero se limitan a fenómenos regulares; el debate se centra en qué tareas de procesamiento del lenguaje siguen siendo mejor atendidas por ellas frente a modelos estadísticos o neuronales más ricos.

Key figures

• Martin Kay
• Ronald Kaplan
• Kimmo Koskenniemi
• Lauri Karttunen

Seminal works

• kaplan1994
• beesley2003

Frequently asked questions

¿Por qué usar un transductor de estados finitos en lugar de solo una tabla de consulta para la morfología?

Un transductor codifica de forma compacta las alternancias sistemáticas y puede analizar o generar formas de palabras que nunca ha visto, mientras que una tabla solo almacena las formas explícitamente listadas en ella.