commit fb98ad5e6153231e475e88ae66f27179af554ed3
parent f8affa7cbb007a8d8edfb2d57c80bf058bd43fe4
Auteur: Loïc Daignault-Pichette <loic@asteride.xyz>
Date: Mon, 16 Feb 2026 11:41:21 -0500
Créer l’entête pour le format .tfd
Diffstat:
| A | tfd.h | | | 123 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 fichier modifié, 123 insertions(+), 0 suppressions(-)
diff --git a/tfd.h b/tfd.h
@@ -0,0 +1,123 @@
+#ifndef TFD_H
+#define TFD_H
+
+#include <stdio.h>
+
+#include "tfm.h"
+
+/* Le format .tfd est une représentation binaire du transducteur. Il a été
+ * conçu pour être rapide à charger et à interpréter: nul besoin de le
+ * désérialiser pour l’interpréter, et les structures de données qu’il utilise
+ * dispense d’un maximum de recherche. L’asbsence de sérialisation et de
+ * désérialisation freine la portabilité du fichier. En particulier, le format
+ * utilise le boutisme de l’hôte qui le compile.
+ * Le format est composé de cinq segments, indexés dans une entête placée en
+ * début de fichier. Les segments sont les suivants: index des symboles, liste
+ * de symboles, segmenteur, automate, tableau des identifiants de symbole de
+ * sortie.
+ *
+ * L’entête contient les champs suivants:
+ *
+ * 00 02 Nombre magique (0h5407)
+ * 02 04 Version (0)
+ * 04 06 Position de l’index des symboles
+ * 06 08 Taille du l’index des symboles
+ * 08 0a Position de la liste de symboles
+ * 0a 0c Taille de la liste de symboles
+ * 0c 0e Position du segmenteur
+ * 0e 10 Taille du segmenteur
+ * 10 12 Position de l’automate
+ * 12 14 Taille de l’automate
+ * 14 16 Position des identifiants de symbole de sortie
+ * 16 18 Taille des identifiants de symbole de sortie
+ *
+ * La liste des symboles se présente comme une suite chaînes de caractères
+ * encodées à la Pascal, dans lesquelles les chaînes sont immédiatement
+ * précédées d’un octet donnant la taille de la chaîne le suivant.
+ *
+ * L’index des symboles est un tableau de pointeurs vers les symboles de la
+ * liste de symboles. Les identifiants de symbole sont des indices dans l’index
+ * des symboles.
+ *
+ * La structure du segmenteur s’inspire de la structure à deux tableaux proposée
+ * par Aho (1989: An Efficient Digital Search Algorithm by Using a Double-Array
+ * Structure). Elle consiste en un tableau dont les cellules contiennent
+ * chacune deux champs: la base et l’origine. Chaque champ occupe 2 octets, pour
+ * un total de 4 octets par cellule. Ces deux champs contiennent un drapeau dans
+ * leur bit le plus à droite. Celui de la base marque un état comme final (1) ou
+ * comme non-final (0); celui de l’origine indique si le champ doit bel et bien
+ * être interprété comme une origine (0), ou comme un identifiant de symbole.
+ * Une paire (base, origine) représente un état. Un état peut être désigné par
+ * son indice i. On passe d’un état à l’autre par la formule
+ *
+ * i' = paire[i].base >> 1 + s,
+ *
+ * où s est un symbole d’entrée. Pour que la transition soit valide, il faut en
+ * plus satisfaire les équation suivante:
+ *
+ * paire[i'].orig & 1 == 0,
+ * paire[i'].orig >> 1 == i.
+ *
+ * Autrement, on pourrait quitter n’importe quel état avec n’importe quel
+ * symbole.
+ * Si, cependant, le drapeau de la base d’un symbole est brandi,
+ *
+ * i'' = paire[i'].base >> 1 et
+ * symbole = paire[i''].orig >> 1.
+ *
+ * La variable symbole contient l’identifiant du symbole. Elle est mise à jour
+ * chaque fois qu’un état final est rencontré parce que le segmenteur est
+ * glouton: il tente de reconnaître le symbole le plus long, ignorant ses
+ * préfixes qui sont aussi des symboles. Lorsque plus aucune transition n’existe
+ * qui n’accepte le prochain symbole d’entrée, le dernier symbole assigné est
+ * retourné et la position dans le mot entrée courante au moment où ce symbole
+ * a été assigné est restorée.
+ *
+ * La structure de l’automate est aussi un tableau double. Elle s’inspire
+ * cependant de l’extension de Mizobuchi, Sumitomo, Fuketa & Aoe (2000: An
+ * efficient representation for implementing finite state machines based on the
+ * double-array), qui augmente la structure d’Aho (1989) pour lui permettre de
+ * représenter des cycles. La structure originale n’en est pas capable,
+ * puisqu’elle force un état à n’avoir qu’une seule transition entrante, le
+ * champ orig ne pouvant contenir qu’un seul état. La solution proposée est de
+ * sélectionner une paire comme représentant canonique de l’état, les autres se
+ * chargeant de vérifier l’origine et de pointer vers le représentant canonique.
+ * Un drapeau placé dans le bit le plus à droite de la base indique que l’état
+ * de la paire à laquelle elle appartient est canonique (0) ou non (1). Cette
+ * solution ne fonctionne que pour les automates déterministes. Or,
+ * contrairement aux automates finis, les transducteurs finis ne peuvent pas
+ * tous être déterminisés: un symbole d’entrée peut mener à plus d’une
+ * transition. La solution que je propose est de créer, dans ces cas, une liste
+ * chaînée de transitions. Cette liste est signalée par un drapeau brandi dans
+ * le bit le plus à droite du champ origine. Les drapeaux de la base et de
+ * l’origine ne peuvent être brandis en même temps. On passe d’un état à l’autre
+ * par la formule:
+ *
+ * i' = paire[i].base >> 1 + s,
+ *
+ * si et seulement si
+ *
+ * paire[i'].orig & 1 == 0,
+ * paire[i'].orig >> 1 == i.
+ *
+ * Si, cepedant le drapeau de la base d’un symbole est brandi,
+ *
+ * i'' = paire[i'].base >> 1.
+ *
+ * Et si c’est le drapeau de l’origine qui est brandi, paire[i'].base >> 1
+ * contient l’indice vers le début de la liste de transitions. Dans cette
+ * liste, le champ base contient l’indice de la prochaine paire ayant le
+ * même symbole d’entrée et le champ origine l’indice de l’état vers lequel
+ * pointe la transition. Une valeur de 1 dans l’origine marque la fin de la
+ * liste.
+ *
+ * Un deuxième tableau contient les identifiants de symbole de sortie. Les
+ * identifiants y sont disposés de telle sorte que l’indice dans le
+ * transducteur de l’état cible d’une transition permette d’y obtenir
+ * l’identifiant du symbole de sortie correspondant. */
+
+/* Écrire une représentation .tfd du transducteur dans le fichier f.
+ * Renvoie 0, ou -1 en cas d’erreur. */
+int tfd_ecrire(FILE *f, struct tfm *tfm);
+
+#endif
