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
abcabc
jest 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
abcabcbc
jest nielegalna, ponieważ sekwencjabc
pojawia 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.
źródło
Odpowiedzi:
GolfScript,
111108 znakówJest 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:
źródło
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
Przykładowy przebieg:
źródło