Kompresuj dane za pomocą gramatyki bezkontekstowej

9

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.

FUZxxl
źródło
Ha ha. Mam już kilka zaimplementowanych (ale nie golfowych) wersji w Javie dla pytań o złożoność kolmogorowa ...
Peter Taylor,
@PeterTaylor Które pytania dokładnie?
FUZxxl,
Nie musi znaleźć wystarczająco krótkiej odpowiedzi, aby warto było ją opublikować (powoli dodam strategie generujące gramatykę i silniki gramatyczne), ale główny skrypt tego projektu wypróbowuje je na codegolf.stackexchange.com/questions/1682 , codegolf .stackexchange.com / pytania / 6043 , codegolf.stackexchange.com/questions/4191 , codegolf.stackexchange.com/questions/4356 i kilka elementów innych pytań.
Peter Taylor

Odpowiedzi:

3

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
Howard
źródło
1

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

króliczek
źródło
Twój kod nie działa zgodnie ze specyfikacją. Generuje dane wyjściowe, które naruszają regułę, żadna sekwencja dwóch znaków nie może pojawić się dwukrotnie ; rozważ wejście abcdabcd. Ponadto kod najwyraźniej usuwa ostatni bajt ze strumienia wejściowego. Spójrz tutaj na przykład, aby zaobserwować oba efekty: ideone.com/3Xvtyv
FUZxxl,
Ponadto dane wyjściowe próbki są najwyraźniej niepoprawne.
FUZxxl,
Masz rację - nie udało mi się - spojrzę na to, kiedy wrócę z pracy: P
króliczek
Dla mnie to nie usuwa ostatniego bajtu z wejścia - a moje przykładowe dane wyjściowe są poprawne (dla mnie). Zagrajmy w „zauważ błąd”!
króliczek
Przykładowy wynik, który opublikowałeś, to zdecydowanie. Rozszerzona forma reguły 10 kończy się regułą 14, która z kolei kończy się na „ca”. Ostatnie c to tak naprawdę 5 pozycji przed końcem.
FUZxxl,