Expressions régulières et méthodes à états finis

Techniques pratiques basées sur les langages réguliers — la reconnaissance de motifs (pattern matching) avec des expressions régulières et le mappage de chaînes de caractères (string-to-string mapping) avec des transducteurs à états finis — qui gèrent efficacement la tokénisation, la normalisation et l'analyse morphologique.

Definition

Les méthodes à états finis sont des techniques de traitement du langage dans lesquelles les motifs et les mappages sont exprimés sous forme d'expressions régulières ou d'automates et transducteurs à états finis, garantissant une reconnaissance efficace en temps linéaire.

Scope

Couvre les expressions régulières en tant que langage de motifs sur les chaînes de caractères, les automates et transducteurs à états finis comme leur réalisation computationnelle, et leur application à la normalisation de texte, à la tokénisation, à l'orthographe et à la morphologie computationnelle. Il inclut les méthodes à états finis pondérées utilisées dans le traitement de la parole et le traitement superficiel. La théorie phonologique complète et l'analyse syntaxique profonde sont hors de portée.

Core questions

• Comment les expressions régulières peuvent-elles spécifier et extraire des motifs textuels avec précision ?
• Comment les transducteurs à états finis mappent-ils les formes de surface aux analyses lexicales, comme en morphologie ?
• Pourquoi les méthodes à états finis sont-elles préférées pour la tokénisation et la normalisation ?

Key concepts

• expression régulière
• transducteur à états finis
• tokénisation
• normalisation de texte
• analyse morphologique
• morphologie à deux niveaux
• automates pondérés
• distance d'édition

Key theories

Modèles réguliers de morphologie et de phonologie

Le fait que les règles de réécriture phonologique et les alternances morphologiques peuvent être compilées en transducteurs à états finis, faisant de l'analyse et de la génération un cadre unique et efficace.

Équivalence des expressions régulières et des automates finis

Les expressions régulières, les grammaires régulières et les automates à états finis décrivent tous exactement les langages réguliers, de sorte qu'un motif déclaratif peut être compilé en un reconnaisseur efficace.

History

Les expressions régulières ont été introduites en informatique à partir des travaux de Kleene et sont devenues omniprésentes dans les outils textuels. Dans les années 1980, la morphologie à deux niveaux de Koskenniemi et la compilation par Kaplan et Kay de règles phonologiques en transducteurs ont établi la technologie à états finis comme l'outil essentiel du traitement morphologique, une approche consolidée dans le manuel de Beesley et Karttunen.

Debates

Jusqu'où les méthodes à états finis peuvent-elles être mises à l'échelle ?

Les techniques à états finis sont extrêmement efficaces mais limitées aux phénomènes réguliers ; le débat porte sur les tâches de traitement du langage qui restent le mieux servies par elles par rapport aux modèles statistiques ou neuronaux plus riches.

Key figures

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

Seminal works

• kaplan1994
• beesley2003

Frequently asked questions

Pourquoi utiliser un transducteur à états finis plutôt qu'une simple table de consultation pour la morphologie ?

Un transducteur encode de manière compacte les alternances systématiques et peut analyser ou générer des formes de mots qu'il n'a jamais rencontrées, tandis qu'une table ne stocke que les formes qui y sont explicitement listées.