Algorithme de Sardinas-Patterson

On considère un monoïde libre ${\displaystyle A^{*}}$. On appelle code à longueur variable ou code une partie ${\displaystyle C}$ de ${\displaystyle A^{*}}$ telle que le sous-monoïde engendré ${\displaystyle C^{*}}$ est libre. L'algorithme de Sardinas-Patterson prend en entrée un alphabet ${\displaystyle A}$ et une partie finie ${\displaystyle C}$ de ${\displaystyle A^{*}}$ et détermine si ${\displaystyle C}$ est un code.

L'objectif est de pouvoir transcrire un mot dans un alphabet ${\displaystyle B}$ en un mot dans l'alphabet ${\displaystyle A}$ en associant à chaque lettre de ${\displaystyle B}$ un nombre variable de lettres de ${\displaystyle A}$, ${\displaystyle C}$ étant alors l'ensemble des codages des lettres de ${\displaystyle B}$. On cherche alors à ce que ce code ne soit pas ambiguë. Par exemple, en code Morse, A est codé par .-, E par . et F par ..-.. Mais alors, ..-. peut être interprété comme EAE ou comme F. Le code Morse nécessite ainsi l'usage d'un autre caractère séparant les lettres[2].

Si ${\displaystyle P}$ et ${\displaystyle Q}$ sont deux parties de ${\displaystyle A^{*}}$, on pose ${\displaystyle P^{-1}Q=\{u\in A^{*}|\exists p\in P,pu\in Q\}}$. On note ${\displaystyle \epsilon }$ le mot vide. L'algorithme calcule les éléments de la suite d'ensembles définie par récurrence :

• ${\displaystyle D_{0}=C}$ et ${\displaystyle D_{1}=C^{-1}C\setminus \{\epsilon \}}$
• ${\displaystyle D_{n+1}=C^{-1}D_{n}\cup D_{n}^{-1}C}$ pour ${\displaystyle n\geq 1}$.

Si lors du calcul, on obtient un ${\displaystyle D_{n}}$ égal à un des précédents, alors ${\displaystyle C}$ est un code. Si l'un des ${\displaystyle D_{n}}$ contient ${\displaystyle \epsilon }$, alors ${\displaystyle C}$ n'est pas un code[2].

Chacun des ${\displaystyle D_{n}}$ est une partie de l'ensemble des facteurs des éléments de ${\displaystyle C}$. Or ${\displaystyle C}$ est fini, donc l'ensemble des facteurs de ses éléments est fini (dans un monoïde libre, chaque élément ayant un nombre fini de facteurs), donc l'ensemble des parties de cet ensemble est fini. Par conséquent, des termes de la suite ${\displaystyle (D_{n})}$ se répètent. L'algorithme s'arrête donc nécessairement[2].

La correction de l'algorithme s'énonce comme suit.

Théorème. ${\displaystyle C}$ n'est pas un code si, et seulement si l'un des ${\displaystyle D_{n}}$ contient ${\displaystyle \epsilon }$.

Démonstration.

(⇒) Supposons que ${\displaystyle C}$ n'est pas un code. Si ${\displaystyle \epsilon \in C}$, alors ${\displaystyle \epsilon \in D_{0}}$. Sinon, on dispose de ${\displaystyle a_{1}a_{2}\dots a_{k}}$ et ${\displaystyle b_{1}b_{2}\dots b_{l}}$ égaux avec ${\displaystyle (a_{i})}$ et ${\displaystyle (b_{j})}$ deux suites d'éléments de ${\displaystyle C}$ telles que ${\displaystyle a_{1}\neq b_{1}}$. On peut voir ce mot comme un segment, par exemple :

A0B0-----------------A1--------B1---------B2-----A2-----------------B3---------A3B4

Les lettres en majuscules notent des positions dans le mot, de manière que ${\displaystyle a_{1}=[A_{0}A_{1}]}$, ${\displaystyle a_{2}=[A_{1}A_{2}]}$ et ainsi de suite et de même pour les ${\displaystyle b_{j}}$, avec les crochets notant le facteur délimité par les deux positions. Exécutons l'algorithme sur cet exemple : comme ${\displaystyle a_{1}=[A_{0}A_{1}]}$ et ${\displaystyle b_{1}=[B_{0}B_{1}]}$ (avec ${\displaystyle A_{0}=B_{0}}$) sont dans ${\displaystyle C}$, alors ${\displaystyle a_{1}^{-1}b_{1}=[A_{1}B_{1}]}$ est dans ${\displaystyle D_{1}}$. Ensuite, comme ${\displaystyle a_{2}=[A_{1}A_{2}]}$ est dans ${\displaystyle C}$, on a ${\displaystyle [B_{1}A_{2}]=[A_{1}B_{1}]^{-1}[A_{1}A_{2}]\in D_{1}^{-1}C\subset D_{2}}$. Ensuite${\displaystyle [B_{2}A_{2}]=[B_{1}B_{2}]^{-1}[B_{1}A_{2}]=b_{2}^{-1}[B_{1}A_{2}]\in C^{-1}D_{2}\subset D_{3}}$, puis ${\displaystyle [A_{2}B_{3}]=[B_{2}A_{2}]^{-1}b_{3}\in D_{4}}$. On peut ainsi faire augmenter de 1 l'indice de la lettre de gauche à chaque étape, en utilisant le terme de droite de l'union si l'ordre de ${\displaystyle A}$ et ${\displaystyle B}$ change dans les crochets, le terme de gauche sinon. Finalement, on arrive au même point à gauche et à droite : ${\displaystyle \epsilon =[B_{4}A_{3}]\in D_{6}}$ et on obtient le critère voulu. Comme la suite des ${\displaystyle (D_{n})}$ est définie par récurrence, elle ne peut pas se répéter avant d'inclure ${\displaystyle \epsilon }$.

(⇐) Réciproquement, supposons ${\displaystyle \epsilon \in D_{n}}$ pour un entier ${\displaystyle n\geq 2}$ (le cas ${\displaystyle n=0}$ est immédiat). Par exemple, on a ${\displaystyle \epsilon =c_{n-1}^{-1}d_{n-1}}$ avec ${\displaystyle c_{n-1}\in C}$ et ${\displaystyle d_{n-1}\in D_{n-1}}$. Alors ${\displaystyle c_{n-1}=d_{n-1}}$. De même, on a par exemple ${\displaystyle d_{n-1}=d_{n-2}^{-1}c_{n-2}}$, et donc ${\displaystyle d_{n-2}c_{n-1}=c_{n-2}}$. En développant les ${\displaystyle d_{k}}$obtenus jusqu'à arriver dans ${\displaystyle D_{1}}$, on obtient une égalité donc chaque membre est une concaténation d'éléments de ${\displaystyle C}$. Par construction, le dernier mot de ces deux suites est différent : l'un est ${\displaystyle c_{n-1}}$, l'autre en est un suffixe strict. On a donc obtenu un même mot en concaténant deux suites différentes de ${\displaystyle C}$ : ce dernier n'est donc pas un code[3].