Komprimieren Sie Daten mit kontextfreien Grammatiken

9

Es ist möglich, einige Arten von Daten, wie z. B. menschlichen Text oder Quellcode, mit geradlinigen Grammatiken zu komprimieren. Sie erstellen im Grunde eine Grammatik, deren Sprache genau ein Wort enthält - die unkomprimierten Daten. In dieser Aufgabe müssen Sie ein Programm schreiben, das diese Methode der Datenverdichtung implementiert.

Eingang

Die Eingabe ist eine Zeichenfolge mit einer Länge von nicht mehr als 65535 Byte. Es wird garantiert, dass die Eingabe mit dem regulären Ausdruck übereinstimmt [!-~]+(dh mindestens ein druckbares ASCII-Zeichen ohne Leerzeichen).

Eine Beispieleingabe ist

abcabcbcbcabcacacabcabab

Ausgabe

Die Ausgabe besteht aus einer Reihe von Regeln, die eine Grammatik bilden, die genau ein Wort (die Eingabe) beschreibt. Jedes Nichtterminal wird durch eine Dezimalzahl größer als 9 gekennzeichnet. Das Startsymbol ist die Symbolnummer zehn. Eine Beispielausgabe, die der Beispieleingabe entspricht, ist unten angegeben; Die Syntax wird weiter unten beschrieben:

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

Jede Regel hat die Form <nonterminal>=<symbol> <symbol> ...mit einer beliebigen durch Leerzeichen getrennten Anzahl von Symbolen auf der rechten Seite. Jede Ausgabe, die die folgenden Einschränkungen befolgt und genau die Eingabezeichenfolge ableitet, ist gültig.

Beschränkungen

Um Menschen davon abzuhalten, seltsame Dinge zu tun, gibt es eine Reihe von Einschränkungen:

  • Jedes Nichtterminal muss mindestens zweimal auf der rechten Seite einer Regel erscheinen. Beispielsweise ist die folgende Grammatik für die Eingabe abcabcunzulässig, da Regel 12 nur einmal vorkommt:

    10=12
    11=a b c
    12=11 11
    
  • Keine Folge von zwei benachbarten Symbolen darf mehr als einmal auf allen rechten Seiten aller Regeln erscheinen, außer wenn sie sich überlappen. Beispielsweise ist die folgende Grammatik für die Eingabe abcabcbcunzulässig, da die Sequenz bczweimal angezeigt wird:

    10=11 11 b c
    11=a b c
    

    Eine gültige Grammatik wäre:

    10=11 11 12
    11=a 12
    12=b c
    
  • Ihr Programm muss für jede gültige Eingabe, die nicht länger als 65535 Byte ist, in weniger als einer Minute beendet werden.

  • Wie üblich dürfen Sie keine Funktion Ihrer Sprache oder Bibliotheksfunktion verwenden, die die Lösung trivial macht oder einen großen Teil davon implementiert.

Beispieleingabe

Generieren Sie eine Probeneingabe mit dem folgenden C-Programm.

#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;
}

Die vom obigen Programm erzeugte Beispieleingabe führt normalerweise nicht zu guten Komprimierungsergebnissen. Verwenden Sie möglicherweise menschlichen Text oder Quellcode als Beispieleingabe.

Gewinnkriterien

Das ist Code Golf; Das Programm mit dem kürzesten Quellcode gewinnt. Schreiben Sie für zusätzliche Gutschrift ein Programm, das die Eingabe aus der Ausgabe rekonstruiert.

FUZxxl
quelle
Ha ha. Ich habe bereits einige Versionen davon in Java implementiert (aber nicht Golf gespielt) für die Fragen der Kolmogorov-Komplexität ...
Peter Taylor
@ PeterTaylor Welche Fragen genau?
FUZxxl
Es muss nicht unbedingt eine Antwort finden, die kurz genug ist, um veröffentlicht zu werden (ich füge langsam Strategien zur Grammatikerzeugung und Grammatik-Engines hinzu), aber das Kernskript in diesem Projekt probiert sie unter codegolf.stackexchange.com/questions/1682 , codegolf aus .stackexchange.com / question / 6043 , codegolf.stackexchange.com/questions/4191 , codegolf.stackexchange.com/questions/4356 und einige Komponenten anderer Fragen.
Peter Taylor

Antworten:

3

GolfScript, 111 108 Zeichen

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

Dies ist ein ziemlich ungeschickter Ansatz mit GolfScript. Die zweite Version bietet eine viel bessere Leistung als die erste. Es ist viel länger als der beabsichtigte Code, aber meine Implementierung hatte verschachtelte do-Schleifen und dies verursachte Probleme mit dem Interpreter.

Beispiele:

> 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
quelle
1

Zurückgezogen - Der Algorithmus kann nicht alle Fälle behandeln. C, 422 (behoben, um Dups in der Ausgabe zu entfernen und Zeichen zu löschen)

Die erste Implementierung beginnt mit dem Golfen.

Da die Regeln es nicht erfordern, diesen Brute-Force-naiven Ansatz tatsächlich zu komprimieren, reicht dies aus ...

Kann die Länge von 65535 innerhalb von 10 Sekunden verarbeiten

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");
    }

}

Probelauf:

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

Baby-Kaninchen
quelle
Ihr Code funktioniert nicht gemäß der Spezifikation. Es wird eine Ausgabe generiert, die gegen die Regel verstößt. Es darf keine Folge von zwei Zeichen zweimal erscheinen . Betrachten Sie die Eingabe abcdabcd. Außerdem entfernt Ihr Code anscheinend das letzte Byte aus dem Eingabestream. Schauen Sie hier für ein Beispiel, um beide Effekte zu beobachten: ideone.com/3Xvtyv
FUZxxl
Außerdem ist Ihre Beispielausgabe anscheinend falsch.
FUZxxl
Du hast recht - ich habe versagt - ich werde es mir ansehen, wenn ich von der Arbeit zurückkomme: P
Baby-Kaninchen
Es entfernt nicht das letzte Byte von der Eingabe für mich - und meine Beispielausgabe ist korrekt (für mich). Lassen Sie uns "Spot the Bug" spielen!
Baby-Kaninchen
Die Beispielausgabe, die Sie definitiv gepostet haben, ist. Die erweiterte Form von Regel 10 endet mit Regel 14, die wiederum mit "ca" endet. Das letzte c ist tatsächlich 5 Positionen vor dem Ende.
FUZxxl