Il est possible de compresser certains types de données, comme le texte humain ou le code source, avec des grammaires linéaires. Vous créez essentiellement une grammaire dont la langue a exactement un mot - les données non compressées. Dans cette tâche, vous devez écrire un programme qui implémente cette méthode de compression de données.

Contribution

L'entrée est une chaîne d'une longueur maximale de 65 535 octets. Il est garanti que l'entrée correspond à l'expression régulière [!-~]+(c'est-à-dire au moins un caractère ASCII imprimable à l'exclusion des espaces).

Un exemple d'entrée est

abcabcbcbcabcacacabcabab

Production

La sortie est un ensemble de règles qui forment une grammaire qui décrit exactement un mot (l'entrée). Chaque non terminal est désigné par un nombre décimal supérieur à 9. Le symbole de début est le symbole numéro dix. Un exemple de sortie correspondant à l'exemple d'entrée est donné ci-dessous; sa syntaxe est décrite ci-dessous:

10=11 11 12 12 11 13 13 11 14 14
11=a 12
12=b c
13=a c
14=a b

Chaque règle a la forme <nonterminal>=<symbol> <symbol> ...d'un nombre arbitraire de symboles séparés par des espaces sur le côté droit. Chaque sortie qui obéit aux restrictions suivantes et dérive exactement la chaîne d'entrée est valide.

Restrictions

Afin d'empêcher les gens de faire des choses étranges, un certain nombre de restrictions ont lieu:

• Chaque non-terminal doit apparaître au moins deux fois sur le côté droit d'une règle. Par exemple, la grammaire suivante pour l'entrée abcabcest illégale car la règle 12 n'apparaît qu'une seule fois:

  10=12
  11=a b c
  12=11 11
  

• Aucune séquence de deux symboles adjacents ne peut apparaître plus d'une fois dans tous les côtés droit de toutes les règles, sauf si elles se chevauchent. Par exemple, la grammaire suivante pour l'entrée abcabcbcest illégale puisque la séquence bcapparaît deux fois:

  10=11 11 b c
  11=a b c
  

  Une grammaire valide serait:

  10=11 11 12
  11=a 12
  12=b c
  

• Votre programme doit se terminer en moins d'une minute pour chaque entrée valide ne dépassant pas 65 535 octets.

• Comme d'habitude, vous ne pouvez utiliser aucune fonctionnalité de votre langage ou toute fonction de bibliothèque qui rend la solution triviale ou en implémente une grande partie.

Exemple d'entrée

Générez un échantillon d'entrée avec le programme C suivant.

#include <stdlib.h>
#include <stdio.h>

int main(int argc, char **argv) {
  unsigned int i,j = 0,k;

  if (argc != 3
     || 2 != sscanf(argv[1],"%u",&i)
      + sscanf(argv[2],"%u",&k)) {
    fprintf(stderr,"Usage: %s seed length\n",argv[0]);
    return EXIT_FAILURE;
  }

  srand(i);

  while(j < k) {
    i = rand() & 0x7f;
    if (i > 34 && i != 127) j++, putchar(i);
  }

  return EXIT_SUCCESS;
}

L'exemple d'entrée généré par le programme ci-dessus ne donnera généralement pas de bons résultats de compression. Envisagez d'utiliser du texte humain ou du code source comme exemple d'entrée.

Critères gagnants

C'est le golf de code; le programme avec le code source le plus court gagne. Pour un crédit supplémentaire, écrivez un programme qui reconstruit l'entrée à partir de la sortie.

GolfScript, 111 108 caractères

1/{.}{:^1<{^1$/,2>.{;,)^<.0?)!}*}do-1<.,1>{^1$/[10):10]*0+\+}{;^}if(\}while][0]%.,,]zip{))9+`"="+\~" "*+}%n*

Il s'agit d'une approche assez maladroite en utilisant GolfScript. La deuxième version fonctionne bien mieux que la première. Il est beaucoup plus long que le code prévu, mais mon implémentation avait des boucles imbriquées et cela a causé des problèmes avec l'interpréteur.

Exemples:

> abcba
10=a b c b a

> abcabcbc
10=11 11 12
11=a 12
12=b c

> abcabcbcbcabcacacabcabab
10=11 12 12 13 14 14 c 11 15
11=15 13
12=c b
13=14 b
14=c a
15=a b

Rétracté - l'algorithme ne peut pas gérer tous les cas. C, 422 (corrigé pour supprimer les doublons en sortie et les caractères supprimés)

La mise en œuvre initiale commencera à jouer au golf.

Étant donné que les règles ne l'obligent pas à compresser réellement , cette approche naïve par force brute fera l'affaire ...

Peut traiter la longueur de 65535 en 10 secondes

n,m[99999];
c,r[99999][2];

g,i,s,t;

main(){
    for(;(m[n]=getchar())>32;n++);

    while(!g){ // loop until no further changes
        g=1;
        for(s=0;s<n-1;s++) {
            for(t=s+2;t<n-1;t++)if(m[s]==m[t]&&m[s+1]==m[t+1]){
                // create rule
                r[c][0]=m[s];
                r[c++][1]=m[s+1];
                g=0;
                // substitute
                for(i=t=s;i<n;i++){
                    if(m[i]==r[c-1][0]&&m[i+1]==r[c-1][1]){
                        m[t++]=-c;
                        i++;
                    }else
                        m[t++]=m[i];
                }
                n=t;
            }
        }
    }

    for(s=-1;s<c;s++){
        printf("%d=",s+11);
        for(t=0;t<(s<0?n:2);t++){
            i=(s<0?m:r[s])[t];
            i<0?printf("%d ",10-i):printf("%c ",i);
        }
        printf("\n");
    }

}

Exemple d'exécution:

echo abcabcbcbcabcacacabcabab | a.out
10=11 12 13 13 12 14 14 12 12 11 
11=a b 
12=c 11 
13=c b 
14=c a