Qu'est ce qu'un transducteur à états finis?

Un transducteur à états finis (TSF) est un FSA (finite state automaton, FA) qui produit une sortie ainsi que la lecture de l'entrée, ce qui signifie qu'il est utile pour l'analyse (tout en un "nu" FSA ne peut être utilisé pour la reconnaissance, c'est à dire le pattern matching).

Un FST se compose d'un nombre fini d'états qui sont liés par des transitions étiquetées avec une paire d'entrée/sortie. La FST commence désigné dans un état de départ et les sauts de différents états en fonction de l'entrée, tandis que la production en fonction de sa table de transition.

Fst sont utiles en PNL et en reconnaissance de la parole, car ils ont de belles propriétés algébriques, les plus notamment le fait qu'ils peuvent être librement combinés (forme une algèbre) en vertu de la composition, qui met en œuvre relationnelle de la composition sur des relations régulières (pensez à ce que les non-déterministe de la fonction de composition), tout en restant très compact. Fst peut faire de l'analyse syntaxique des langages réguliers dans les chaînes dans le temps linéaire.

Comme un exemple, une fois, j'ai mis en œuvre l'analyse morphologique comme un tas de Fst. Mon principal FST pour les verbes serait à son tour un verbe normal, dire "marché", dans "walk+PASSÉ". J'ai aussi eu un FST pour le verbe "être", ce qui "est" en "être+PRÉSENT+3ème" (3e personne), et de même pour les autres verbes irréguliers. Tous les Fst ont été combinés en un seul à l'aide d'un FST compilateur, qui a produit un seul FST qui était beaucoup plus petite que la somme de ses parties, et s'est très rapide. Fst peut être construit par une variété d'outils que d'accepter une extension de la syntaxe d'expression régulière.

En termes simples que possible, je comprends qu'un FST est essentiellement une "chose" qui passe d'un état à l'autre, selon une entrée de bande et écrit à une autre sortie de bande. Une bande est essentiellement un ensemble de facteurs comme caractères dans une chaîne.

L'ensemble de la FST est représenté par un ensemble d'états et les liens entre eux. Un lien est "activé" lorsque la condition d'entrée est correcte, puis donne alors l'état suivant le réglage de la bande.

Par exemple, disons qu'un FST commence avec la bande abc à l'état 1. Un lien vers l'état 2 matchs a et les changements de b. Cela permettrait de s'activer, définissez la sortie de la bande à juste b, et de passer le restant bc à l'état 2. Comme vous pouvez le voir, chaque état est activé uniquement si il y a un lien dont la condition d'entrée est correcte, passe le restant d'entrée à l'état suivant, et écrit à la sortie de la bande. Chaque FST pistes à travers la bande une fois et de sortie sur une autre bande une fois.

Pour avoir une compréhension claire d'entre eux de lire et de prendre un regard sur les diagrammes dans cet article (origine de lien brisé).