Algorithme de Sardinas-Patterson

En théorie des codes, l'algorithme de Sardinas-Patterson permet de déterminer si une partie d'un monoïde libre est un code en temps polynomial. Il est nommé d'après August Sardinas et George Patterson, qui le publièrent dans un article de 1953.

Objectif

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

L'objectif est de pouvoir transcrire un mot dans un alphabet $B$ en un mot dans l'alphabet $A$ en associant à chaque lettre de $B$ un nombre variable de lettres de $A$, $C$ étant alors l'ensemble des codages des lettres de $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.

Description de l'algorithme

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

• $D_0=C$ et $D_1=C^{-1}C\setminus \{ϵ\}$
• $D_{n+1}=C^{-1}{D}_n\cup D_n^{-1}C$ pour $n\ge 1$.

Si lors du calcul, on obtient un $D_n$ égal à un des précédents, alors $C$ est un code. Si l'un des $D_n$ contient $ϵ$, alors $C$ n'est pas un code.

Terminaison

Chacun des $D_n$ est une partie de l'ensemble des facteurs des éléments de $C$. Or $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 $(D_n)$ se répètent. L'algorithme s'arrête donc nécessairement.

Correction

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

Théorème. $C$ n'est pas un code si, et seulement si l'un des $D_n$ contient $ϵ$.

Démonstration.

(⇒) Supposons que $C$ n'est pas un code. Si $ϵ\in C$, alors $ϵ\in D_0$. Sinon, on dispose de $a_1{a}_2\dots a_k$ et $b_1{b}_2\dots b_l$ égaux avec $(a_i)$ et $(b_j)$ deux suites d'éléments de $C$ telles que $a_1\ne 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 $a_1=[A_0{A}_1]$, $a_2=[A_1{A}_2]$ et ainsi de suite et de même pour les $b_j$, avec les crochets notant le facteur délimité par les deux positions. Exécutons l'algorithme sur cet exemple : comme $a_1=[A_0{A}_1]$ et $b_1=[B_0{B}_1]$ (avec $A_0=B_0$) sont dans $C$, alors $a_1^{-1}{b}_1=[A_1{B}_1]$ est dans $D_1$. Ensuite, comme $a_2=[A_1{A}_2]$ est dans $C$, on a $[B_1{A}_2]=[A_1{B}_1{]}^{-1}[A_1{A}_2]\in D_1^{-1}C\subset D_2$. Ensuite$[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 $[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 $A$ et $B$ change dans les crochets, le terme de gauche sinon. Finalement, on arrive au même point à gauche et à droite : $ϵ=[B_4{A}_3]\in D_6$ et on obtient le critère voulu. Comme la suite des $(D_n)$ est définie par récurrence, elle ne peut pas se répéter avant d'inclure $ϵ$.

(⇐) Réciproquement, supposons $ϵ\in D_n$ pour un entier $n\ge 2$ (le cas $n=0$ est immédiat). Par exemple, on a $ϵ=c_{n-1}^{-1}{d}_{n-1}$ avec $c_{n-1}\in C$ et $d_{n-1}\in D_{n-1}$. Alors $c_{n-1}=d_{n-1}$. De même, on a par exemple $d_{n-1}=d_{n-2}^{-1}{c}_{n-2}$, et donc $d_{n-2}{c}_{n-1}=c_{n-2}$. En développant les $d_k$obtenus jusqu'à arriver dans $D_1$, on obtient une égalité donc chaque membre est une concaténation d'éléments de $C$. Par construction, le dernier mot de ces deux suites est différent : l'un est $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 $C$ : ce dernier n'est donc pas un code.