Compressez les données avec des grammaires sans contexte

9

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.

FUZxxl
la source
Ha ha. J'ai déjà quelques versions de cela implémentées (mais pas jouées) en Java pour les questions de complexité kolmogorov ...
Peter Taylor
@PeterTaylor Quelles questions exactement?
FUZxxl
Il ne trouve pas nécessairement une réponse suffisamment courte pour être publiée ( j'ajoute lentement des stratégies de génération de grammaire et des moteurs de grammaire), mais le script principal de ce projet les teste sur codegolf.stackexchange.com/questions/1682 , codegolf .stackexchange.com / questions / 6043 , codegolf.stackexchange.com/questions/4191 , codegolf.stackexchange.com/questions/4356 et quelques composants d'autres questions.
Peter Taylor

Réponses:

3

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
Howard
la source
1

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

bébé-lapin
la source
Votre code ne fonctionne pas conformément aux spécifications. Il génère une sortie qui viole la règle, aucune séquence de deux caractères ne peut apparaître deux fois ; considérez l'entrée abcdabcd. De plus, votre code supprime apparemment le dernier octet du flux d'entrée. Regardez ici un exemple pour observer les deux effets: ideone.com/3Xvtyv
FUZxxl
En outre, votre sortie d'échantillon est apparemment erronée.
FUZxxl
Tu as raison - j'ai échoué - je vais le regarder quand je reviens du travail: P
bébé-lapin
Cela ne supprime pas le dernier octet de l'entrée pour moi - et ma sortie d'échantillon est correcte (pour moi) .. Jouons "repérer le bug"!
bébé-lapin
L'exemple de sortie que vous avez définitivement publié est. La forme développée de la règle 10 se termine par la règle 14 qui à son tour se termine par "ca". Le dernier c est en fait 5 positions avant la fin.
FUZxxl