Algorithme de Sequitur

Sequitur (ou algorithme de Nevill-Manning–Witten ) est un algorithme récursif développé par Craig Nevill-Manning et Ian H. Witten en 1997 qui déduit une structure hiérarchique ( grammaire sans contexte ) à partir d'une séquence de symboles discrets. L'algorithme fonctionne dans un espace et un temps linéaires. Il peut être utilisé dans des applications logicielles de compression de données .

L'algorithme sequitur construit une grammaire en remplaçant les phrases répétitives dans la séquence donnée par de nouvelles règles et produit ainsi une représentation concise de la séquence. Par exemple, si la séquence est

S→abcab,

l'algorithme produira

S→AcA, A→ab.

Lors de l'analyse de la séquence d'entrée, l'algorithme suit deux contraintes pour générer efficacement sa grammaire : l'unicité du diagramme et l'utilité de la règle .

Chaque fois qu'un nouveau symbole est lu à partir de la séquence, il est ajouté au dernier symbole lu pour former un nouveau digramme . Si ce digramme a été formé plus tôt, une nouvelle règle est créée pour remplacer les deux occurrences des digrammes. Par conséquent, elle garantit qu'aucun digramme n'apparaît plus d'une fois dans la grammaire. Par exemple, dans la séquence S→abaaba , lorsque les quatre premiers symboles sont déjà lus, les digrammes formés sont ab, ba, aa . Lorsque le cinquième symbole est lu, un nouveau digramme 'ab' est formé qui existe déjà. Par conséquent, les deux occurrences de 'ab' sont remplacées par une nouvelle règle (par exemple, A) dans S. Maintenant, la grammaire devient S→AaAa, A→ab , et le processus continue jusqu'à ce qu'il n'existe plus de digramme répété dans la grammaire.

Cette contrainte garantit que toutes les règles sont utilisées plus d'une fois dans les parties droites de toutes les productions de la grammaire, c'est-à-dire que si une règle n'apparaît qu'une seule fois, elle doit être supprimée de la grammaire et son occurrence doit être remplacée par les symboles à partir desquels elle est créée. Par exemple, dans l'exemple ci-dessus, si l'on analyse le dernier symbole et applique l'unicité du digramme pour 'Aa', alors la grammaire produira : S→BB, A→ab, B→Aa . Maintenant, la règle 'A' n'apparaît qu'une seule fois dans la grammaire dans B→Aa . Par conséquent, A est supprimé et finalement la grammaire devient

S→BB, B→aba .

Cette contrainte permet de réduire le nombre de règles dans la grammaire.

L'algorithme fonctionne en analysant une séquence de symboles terminaux et en construisant une liste de toutes les paires de symboles qu'il a lues. Chaque fois qu'une deuxième occurrence d'une paire est découverte, les deux occurrences sont remplacées dans la séquence par un symbole non terminal inventé , la liste des paires de symboles est ajustée pour correspondre à la nouvelle séquence et l'analyse continue. Si le symbole non terminal d'une paire est utilisé uniquement dans la définition du symbole qui vient d'être créé, le symbole utilisé est remplacé par sa définition et le symbole est supprimé des symboles non terminaux définis. Une fois l'analyse terminée, la séquence transformée peut être interprétée comme la règle de niveau supérieur dans une grammaire pour la séquence d'origine. Les définitions de règles pour les symboles non terminaux qu'elle contient peuvent être trouvées dans la liste des paires de symboles. Ces définitions de règles peuvent elles-mêmes contenir des symboles non terminaux supplémentaires dont les définitions de règles peuvent également être lues ailleurs dans la liste des paires de symboles.