Le barème est donné à titre indicatif et est susceptible d'être adapté. Lisez attentivement les explications. Commentez vos fonctions.
Le Byte Pair Encoding (BPE) est un algorithme qui génère une séquence de jetons (tokens en anglais) à partir d'un corpus de documents (des séquences de symboles). Ces jetons sont des unités statistiques qui servent ensuite à segmenter les documents en séquences de jetons plutôt qu'en séquences de symboles.
Cette représentation des documents constitue un prétraitement standard pour les LLM, tant pour leur apprentissage que pour leur utilisation. Le BPE rappelle les techniques de compression de données dans lesquelles des motifs fréquents sont remplacés par des symboles plus compacts ; mais l'objectif est ici de construire un encodage adapté à l'apprentissage statistique, pas de compresser. Nous en proposons ici une version simplifiée.
L'algorithme reçoit deux paramètres en entrée :
L'idée est de compléter un lexique initial jeton après jeton et en segmentant le corpus en séquence de jetons de ce lexique en évolution.
Initialisation : On crée le lexique de départ comme une séquence de jetons «atomiques» : un tableau de chaînes de caractères de longueur 1 constituées par les symboles distincts du corpus. Le corpus est codé par une liste chaînée contenant les indices de ces jetons dans le lexique.
Évolution du lexique et segmentation du corpus : Tant que le lexique ne contient pas le nombre de jetons exigés, l'algorithme en génère un nouveau qu'il ajoute à la fin du lexique. Ensuite l'algorithme segmente le corpus en une nouvelle séquence de jetons de ce lexique enrichi. Le nombre d'itérations de l'algorithme est donc exactement le nombre de jetons qu'il faut rajouter au lexique initial pour qu'il atteigne la taille requise (la taille du tableau à allouer pour le lexique est donc connue au départ).
Génération d'un nouveau jeton : On déplace une fenêtre glissante de taille 2 sur la séquence des n jetons qui forment le corpus afin de calculer les fréquences des digrammes, c'est-à-dire des couples de jetons adjacents. La fenêtre se déplace donc n - 1 fois. Les deux jetons du digramme le plus fréquent sont alors concaténés pour former le nouveau jeton ajouté à la fin du lexique. La segmentation du corpus est alors mise à jour : chaque couple de jetons adjacents formant ce digramme est fusionné en ce nouveau jeton (dans la liste chaînée qui code le corpus, le nœud droit est supprimé et le nœud gauche contient le nouveau jeton). On obtient ainsi une nouvelle segmentation plus courte du corpus.
NB. Un prétraitement du corpus assurant sa normalisation (ponctuation, espaces, etc.) est systématiquement réalisé avant d'être traité par l'algorithme BPE. Les mots peuvent être explicitement marqués par un symbole de préfixe _ afin de signaler leur début. Cette convention relève uniquement de la représentation des données et ne modifie pas le principe de l'algorithme BPE, qui opère sur une séquence de jetons.
Avec le corpus de 30 caractères/jetons : _le_lapin_lit_la_lettre_au_lit et un lexique de 16 jetons à générer, l'algorithme va réaliser 6 fusions car le lexique initial contient 10 caractères distincts soit autant de jetons «atomiques». Dans la trace de cet algorithme ci-dessous :
[idx:jeton] code l'index d'un jeton et le jeton,[idxg:gauche] | [idxd:droit] -fx-> [idx:fusion], où f est la fréquence du digramme. $ ./BPE corpus.txt 16
========== CHARGEMENT DU CORPUS ==========
CORPUS : 30 JETONS
LEXIQUE CRÉÉ : 10 JETONS
============== ETAT INITIAL ===============
0 1 2 3 4 5 6 7 8 9
LEXIQUE [10] : [_, l, e, a, p, i, n, t, r, u]
CORPUS [30] : _|l|e|_|l|a|p|i|n|_|l|i|t|_|l|a|_|l|e|t|t|r|e|_|a|u|_|l|i|t
FUSION # 1 : [0:_] | [1:l] -6x-> [10:_l]
0 1 2 3 4 5 6 7 8 9 0
LEXIQUE [11] : [_, l, e, a, p, i, n, t, r, u, _l]
CORPUS [24] : _l|e|_l|a|p|i|n|_l|i|t|_l|a|_l|e|t|t|r|e|_|a|u|_l|i|t
FUSION # 2 : [10:_l] | [2:e] -2x-> [11:_le]
0 1 2 3 4 5 6 7 8 9 0 1
LEXIQUE [12] : [_, l, e, a, p, i, n, t, r, u, _l, _le]
CORPUS [22] : _le|_l|a|p|i|n|_l|i|t|_l|a|_le|t|t|r|e|_|a|u|_l|i|t
FUSION # 3 : [5:i] | [7:t] -2x-> [12:it]
0 1 2 3 4 5 6 7 8 9 0 1 2
LEXIQUE [13] : [_, l, e, a, p, i, n, t, r, u, _l, _le, it]
CORPUS [20] : _le|_l|a|p|i|n|_l|it|_l|a|_le|t|t|r|e|_|a|u|_l|it
FUSION # 4 : [10:_l] | [3:a] -2x-> [13:_la]
0 1 2 3 4 5 6 7 8 9 0 1 2 3
LEXIQUE [14] : [_, l, e, a, p, i, n, t, r, u, _l, _le, it, _la]
CORPUS [18] : _le|_la|p|i|n|_l|it|_la|_le|t|t|r|e|_|a|u|_l|it
FUSION # 5 : [10:_l] | [12:it] -2x-> [14:_lit]
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
LEXIQUE [15] : [_, l, e, a, p, i, n, t, r, u, _l, _le, it, _la, _lit]
CORPUS [16] : _le|_la|p|i|n|_lit|_la|_le|t|t|r|e|_|a|u|_lit
FUSION # 6 : [0:_] | [3:a] -1x-> [15:_a]
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
LEXIQUE [16] : [_, l, e, a, p, i, n, t, r, u, _l, _le, it, _la, _lit, _a]
CORPUS [15] : _le|_la|p|i|n|_lit|_la|_le|t|t|r|e|_a|u|_lit
============== FIN : 16 jetons dans le lexique ==============
Noter en particulier la fusion #5 : les digrammes à fusionner
[_l] | [it] → [_lit] sont eux-mêmes constitués de deux jetons fusionnés
précédemment — c'est le caractère récurrent de l'algorithme BPE.
Le lexique est un simple tableau LEXIQUE de chaînes de caractères alloué dynamiquement et dont la taille est fixée au départ : maxjetons. Il contient initialement nbjetons «atomiques» déterminé par le nombre de caractères distincts du corpus initial.
La séquence de jetons qui forme le corpus est codée par une liste chaînée dont chaque cellule contient l'indice du jeton dans le lexique (seul le lexique contient la chaîne de caractère pour ne pas la stocker plusieurs fois). Par exemple, après la fusion #4, on a le lexique et la segmentation du corpus suivants :
0 1 2 3 4 5 6 7 8 9 0 1 2 3
LEXIQUE = [_, l, e, a, p, i, n, t, r, u, _l, _le, it, _la]
CORPUS = _le|_la|p|i|n|_l|it|_la|_le|t|t|r|e|_|a|u|_l|it
Le corpus est composé de 18 jetons et la liste chaînée contient donc la séquence
11 → 13 → 4 → 5 → 6 → 10 → 12 → 13 → 11 → 7 → 7 → 8 → 2 → 0 → 3 → 9 → 10 → 12
NB. Il n'est pas nécessaire de maîtriser tous les détails de cette section, le code correspondant est fourni.
La fréquence d'un digramme de jetons, en position i pour le premier et j pour le second dans le lexique est fournie par FREQ[i][j] dans un tableau FREQ de dimension 2. Ce tableau est alloué dynamiquement, sa taille est fixée au départ : maxjetons × maxjetons.
La mise à jour de FREQ après une fusion se fait de la manière suivante (elle est faite, vous n'aurez pas à le programmer) :
Lorsque l'on fusionne toutes les occurrences du digramme de jetons (ijetG, jetD) du corpus en le nouveau jeton d'indice ijet du lexique, la table des fréquences doit être mise à jour pour refléter la nouvelle segmentation du corpus. Seules les fréquences des digrammes adjacents de chaque occurrence fusionnée sont affectées ; les autres restent inchangées.
Pour chaque occurrence ... → iavant → ijetG → ijetD → iapres → ... remplacée par ... → iavant → ijet → iapres → ..., deux digrammes disparaissent et deux nouveaux apparaissent :
Ces mises à jour sont effectuées occurrence par occurrence dans la fonction Fusionner, au fil du parcours de la liste chaînée. À chaque incrément de FREQ, une nouvelle entrée est insérée dans le tas via InsererFinTas avec la fréquence mise à jour — c'est ce qui alimente le mécanisme d'effacement paresseux décrit ci-dessous.
Plutôt que de chercher le digramme le plus fréquent dans la table des fréquences après chaque mise à jour à cause de l'introduction d'un nouveau jeton, on le récupère à la racine d'un tas dont les éléments sont des digrammes (le couple des index des deux jetons dans le lexique), la valuation associée à l'APO est leur fréquence.
Lors d'une fusion, nous avons vu que les fréquences des digrammes adjacents sont mises à jour dans FREQ. Plutôt que de retrouver et corriger les entrées correspondantes dans le tas, ou de reconstruire le tas ce qui serait coûteux, on se contente d'insérer le nouveau digramme avec sa fréquence à jour via InsererFinTas. Les anciennes entrées restent dans le tas mais sont désormais obsolètes : elles référencent un digramme avec une fréquence qui n'est plus à jour. C'est donc le tableau FREQ qui fait foi.
À l'extraction (EteterTas), on retire le digramme à la racine du tas selon la procédure habituelle : on le remplace par le dernier élément, on décrémente tailletas, puis on appelle TamiserVersBas pour rétablir la propriété APO. Le nœud extrait est «éliminé» du tas dans tous les cas. On compare alors sa fréquence avec celle de référence dans FREQ :
C'est le principe de l'effacement paresseux (lazy deletion) : on ne nettoie jamais le tas, on se contente d'éliminer les entrées périmées au moment où elles remontent naturellement à la racine.
Les variables globales suivantes sont disponibles dans tout le programme :
tlexique LEXIQUE; // LEXIQUE[i] = i-ème jeton (chaîne) int nbjetons; // nombre de jetons courant dans le lexique int maxjetons; // taille finale du lexique tfreq FREQ; // FREQ[i][j] = fréquence du digramme (i,j) ttas TAS; // le tas int tailletas; // nombre d'éléments courant dans le tas
Votre travail se limite à compléter certaines fonctions du fichier BPE.c distribué. Un fichier exécutable est fourni pour que vous puissiez tester les exemples que vous souhaitez pour vous familiariser avec l'algorithme. Les fonctions les plus complexes sont fournies ; vous n'avez qu'à compléter les fonctions indiquées ci-dessous.
NB : la procédure RAZFrequences() (fournie) remet à zéro toute la table avant l'appel à cette procédure.
Cette fonction est utilisée par Entasser et EteterTas (toutes deux fournies).
Cette fonction est utilisée par InsererFinTas (fournie), appelée lors de la mise à jour du tas après chaque fusion.
NB. Après extraction, si la fréquence du digramme ne correspond pas à celle dans FREQ, on l’ignore et on recommence l’extraction. La fonction renvoie 1 si un digramme valide a été trouvé (dans *maxfdigramme), 0 si le tas est épuisé.
Indication : Utilisez strcpy et strcat.