Qu'est ce qu'un transducteur à états finis?
Quelqu'un peut-il me dire ce qu'est un transducteur à état fini?
J'ai lu L'article Wikipedia et je ne comprends rien.
3 réponses
Un transducteur à état fini (FST) est un automate à état fini (FSA, FA) qui produit une sortie ainsi qu'une entrée de lecture, ce qui signifie qu'il est utile pour l'analyse (alors qu'un FSA "nu" ne peut être utilisé que pour la reconnaissance, c'est-à-dire la correspondance de motifs).
Un FST se compose d'un nombre fini d'États qui sont liés par des transitions étiquetées avec une paire entrée/sortie. Le FST démarre dans un État de démarrage désigné et saute à différents états en fonction de l'entrée, tout en produisant une sortie en fonction à sa table de transition.
Les FST sont utiles en PNL et en reconnaissance vocale car ils ont de belles propriétés algébriques, notamment qu'ils peuvent être combinés librement (former une algèbre) sous composition, ce qui implémente une composition relationnelle sur des relations régulières (pensez à cela comme une composition de fonction non déterministe) tout en restant très compact. FSTs peut faire l'analyse des langages réguliers en chaînes dans le temps linéaire.
À titre d'exemple, j'ai déjà implémenté l'analyse morphologique en tant que tas de FST. Mon principal FST pour les verbes transformerait un verbe régulier, dire "marché", en "marche+passé". J'avais aussi un FST pour le verbe "être", qui transformerait " est " en "être + présent + 3ème" (3ème personne), et de même pour d'autres verbes irréguliers. Tous les FST ont été combinés en un seul en utilisant un compilateur FST, qui a produit un seul FST qui était beaucoup plus petit que la somme de ses parties et a couru très vite. FSTs peut être construit par une variété d'outils qui acceptent une syntaxe d'expression régulière étendue.
Un transducteur à état fini est essentiellement un automate à état fini qui fonctionne sur deux bandes (ou plus). La façon la plus courante de penser aux transducteurs est comme une sorte de `machine à traduire". Ils lisent l'une des bandes et écrivent sur l'autre. Ceci, par exemple, est un transducteur qui traduit
as enbs:
a:bau niveau de l'arc signifie que dans cette transition, le transducteur litaà partir de la première bande et écritbsur le deuxième.
Référence: Transducteurs À État Fini
En termes aussi simples que possible, je comprends qu'un FST est essentiellement une "chose" qui se déplace d'un État à l'autre en fonction d'une bande d'entrée et écrit sur une bande de sortie différente. Une bande est essentiellement un ensemble d'entrées comme des caractères dans une chaîne.
Le FST entier est représenté par un ensemble d'États et de liens entre eux. Un lien est "activé" lorsque sa condition d'entrée est correcte et donne ensuite l'état suivant la bande ajustée.
Par exemple, disons qu'un FST commence avec la bande abc à l'état 1. Un lien vers l'état 2 correspond à a et le change en b. Cela serait activé, définissez la bande de sortie sur b et passez le bc restant à l'état 2. Comme vous pouvez le voir, chaque État n'est activé que s'il y a un lien vers celui-ci dont la condition d'entrée était correcte, passe l'entrée restante à l'état suivant et écrit sur une bande de sortie séparée. Chaque FST traverse la bande une fois et la sortie sur une autre bande une fois.
Pour obtenir une compréhension plus claire de les lire et jeter un oeil aux diagrammes dans cet article (lien cassé original).