Możliwe jest kompresowanie niektórych rodzajów danych, takich jak tekst ludzki lub kod źródłowy, za pomocą gramatyk liniowych. Zasadniczo tworzysz gramatykę, której język zawiera dokładnie jedno słowo - nieskompresowane dane. W tym zadaniu musisz napisać program, który implementuje tę metodę kompresji danych.

Wejście

Dane wejściowe to ciąg nie dłuższy niż 65535 bajtów. Gwarantuje się, że dane wejściowe są zgodne z wyrażeniem regularnym [!-~]+(tj. Co najmniej jeden drukowalny znak ASCII z wyłączeniem białych znaków).

Przykładowym wejściem jest

abcabcbcbcabcacacabcabab

Wynik

Dane wyjściowe to zestaw reguł, które tworzą gramatykę opisującą dokładnie jedno słowo (dane wejściowe). Każdy nieterminalny jest oznaczony liczbą dziesiętną większą niż 9. Symbolem początkowym jest symbol dziesiąty. Przykładowe dane wyjściowe odpowiadające przykładowym danym wejściowym podano poniżej; jego składnia jest opisana poniżej:

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

Każda reguła ma postać <nonterminal>=<symbol> <symbol> ...z dowolną liczbą symboli oddzielonych spacjami po prawej stronie. Każde wyjście, które spełnia poniższe ograniczenia i wywodzi dokładnie ciąg wejściowy, jest poprawne.

Ograniczenia

Aby powstrzymać ludzi od robienia dziwnych rzeczy, obowiązują liczne ograniczenia:

• Każdy nieterminal musi pojawić się co najmniej dwa razy po prawej stronie reguły. Na przykład poniższa gramatyka dla danych wejściowych abcabcjest nielegalna, ponieważ reguła 12 pojawia się tylko raz:

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

• Żadna sekwencja dwóch sąsiednich symboli nie może pojawić się więcej niż jeden raz po wszystkich prawych stronach wszystkich reguł, chyba że się pokrywają. Na przykład następująca gramatyka dla danych wejściowych abcabcbcjest nielegalna, ponieważ sekwencja bcpojawia się dwukrotnie:

  10=11 11 b c
  11=a b c
  

  Prawidłowa gramatyka to:

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

• Twój program musi zakończyć się w mniej niż minutę za każde prawidłowe wejście, które nie jest dłuższe niż 65535 bajtów.

• Jak zwykle nie możesz używać żadnych funkcji w swoim języku ani funkcji bibliotecznej, która sprawia, że ​​rozwiązanie jest trywialne lub implementuje dużą jego część.

Przykładowe dane wejściowe

Wygeneruj przykładowe dane wejściowe za pomocą następującego programu C.

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

Przykładowe dane wejściowe wygenerowane przez powyższy program zwykle nie dają dobrych wyników kompresji. Rozważ użycie tekstu ludzkiego lub kodu źródłowego jako przykładowego wejścia.

Kryteria wygranej

To jest kod golfowy; program z najkrótszym kodem źródłowym wygrywa. Aby uzyskać dodatkowy kredyt, napisz program, który rekonstruuje dane wejściowe z danych wyjściowych.

GolfScript, 111 108 znaków

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

Jest to dość niezdarne podejście przy użyciu GolfScript. Druga wersja działa znacznie lepiej niż początkowa. Jest on znacznie dłuższy niż zamierzony kod, ale moja implementacja zagnieżdżała pętle do, a to powodowało problemy z tłumaczem.

Przykłady:

> 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

Wycofany - algorytm nie może obsłużyć wszystkich przypadków. C, 422 (naprawiono, aby usunąć duplikaty wyjściowe i upuszczony znak)

Wstępne wdrożenie rozpocznie grę w golfa.

Ponieważ zasady nie wymagają, aby kompresja tego brutalnego naiwnego podejścia zrobiła ...

Może przetworzyć długość 65535 w ciągu 10 sekund

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

}

Przykładowy przebieg:

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