Wyzwanie kompresji tekstu bezstratnego w języku angielskim [zamknięte]

Wyzwanie:

Twoim wyzwaniem (jeśli zdecydujesz się je zaakceptować) jest skompresowanie i rozpakowanie 5 MB „ Kompletnych dzieł Williama Szekspira ”, które można znaleźć tutaj: http://www.gutenberg.org/cache/epub/100/pg100.txt

(MD5: a810f89e9f8e213aebd06b9f8c5157d8)

Zasady:

• Państwo musi wziąć wejście za pośrednictwem STDINi poprzez wyjście STDOUT...
• ... i musisz podać identyczny wynik dekompresji na wejściu.
  • (To znaczy, że musisz być w stanie cat inpt.txt | ./cmprss | ./dcmpress | md5uzyskać taki sam MD5 jak powyżej.)
  • (Wszystko za pośrednictwem STDERRnależy odrzucić.)
• Państwo musi użyć mniej niż 2048 znaków na kodzie źródłowym całkowitej.
  • (To nie code-golf. Teraz nie jest liczony w oparciu o długości kodu źródłowego. To jest właśnie zasada, aby utrzymać wszystko skończone).
  • (Weź podzieloną długość całego kodu źródłowego, jeśli go podzieliłeś).
• Państwo musi być w stanie (teoretycznie) proces podobny wejść zwykłego tekstu zbyt.
  • (na przykład twarde kodowania mechanizm, który jest tylko zdolna do wysyłania dostarczona Szekspir wejściowego jest nie do przyjęcia).
  • (Skompresowany rozmiar innych dokumentów nie ma znaczenia - pod warunkiem, że zdekompresowany wynik jest identyczny z alternatywnym wejściem.)
• Państwo może użyć dowolnego wyboru języka (S).
  • (np. możesz kompresować za pomocą awki dekompresować za pomocą java)
• Państwo może napisać dwa oddzielne programy lub połączyć je z jakiejś formy „switch”, jak należy.
  • (Muszą być wyraźne demonstracje, jak wywoływać tryby kompresji i dekompresji)
• Być może nie używać żadnych zewnętrznych poleceń (poprzez exec()).
  • (Jeśli używasz języka powłoki - przepraszam. Musisz zadowolić się wbudowanymi. Możesz opublikować „niedopuszczalną” odpowiedź ze względu na dzielenie się i przyjemność - ale nie zostanie to ocenione! )
• Być może nie stosować żadnych wbudowanych funkcji lub bibliotek dostarczonych który stwierdził celem jest kompresować danych (takich jak gz, etc)
  • (Zmiana kodowania nie jest w tym kontekście uważana za kompresję. Można tu zastosować pewną dyskrecję. Nie wahaj się argumentować, czy Twoje rozwiązanie jest akceptowalne).
• Spróbuj się dobrze bawić, jeśli zdecydujesz się wziąć udział!

Wszystkie dobre zawody mają obiektywną definicję wygranej; ergo:

• Pod warunkiem przestrzegania wszystkich reguł, najmniejsze skompresowane wyjście (w STDOUTbajtach) wygrywa.
  • (Zgłoś swoje dane wyjściowe za pośrednictwem ./cmprss | wc -c)
• W przypadku remisu (identyczne rozmiary wyjściowe) wygrywa najwięcej osób, które uzyskały najwyższe poparcie społeczności.
• W przypadku drugiego losowania (identyczne głosy społeczności) wybiorę zwycięzcę na podstawie całkowicie subiektywnego badania elegancji i czystego geniuszu. ;-)

Jak przesłać:

Sformatuj swój wpis za pomocą tego szablonu:

<language>, <compressed_size>
-----------------------------

<description>  (Detail is encouraged!)

    <CODE...
    ...>

<run instructions>

Zachęcam czytelników i autorów do konwersacji poprzez komentarze - uważam, że ludzie mają prawdziwą okazję do nauki i zostania lepszymi programistami dzięki codegolf.stack.

Zwycięski:

Niedługo wyjeżdżam na wakacje: w ciągu kilku najbliższych tygodni mogę (lub nie będę) monitorować zgłoszenia i dobiegną końca do końca 19 września. Mam nadzieję, że będzie to dobra okazja dla ludzi do myślenia i poddania się - oraz do pozytywnego dzielenia się technikami i pomysłami.

Jeśli nauczyłeś się czegoś nowego od uczestniczenia (jako czytelnik lub autor), zostaw komentarz zachęty.

Perl 5, 3651284

Po prostu prosty słownikowy słownik. Analizuje częstotliwość słowa korpusu i używa go do określenia, czy użyć jednego czy dwóch bajtów narzutu na słowo. Używa dwóch specjalnych symboli dla bajtów \ 0 i \ 1, ponieważ nie pojawiają się one w korpusie. Istnieje wiele innych symboli, których można użyć. Nie zostało to zrobione. Nie wykonuje żadnego kodowania huffmana ani żadnego takiego jazzu.

Skrypt kompresji shakespeare.pl:

use strict;
use warnings;
use bytes;

my $text = join "", <>;
my @words = split/([^a-zA-Z0-9]+)/, $text;


my %charfreq;
for( my $i = 0; $i<length($text); ++$i ) {
    $charfreq{ substr($text, $i, 1) }++
}
for my $i ( 0..255 ) {
    my $c = chr($i);
    my $cnt = $charfreq{$c} // 0;
}



my %word_freq;
foreach my $word ( @words ) {
    $word_freq{ $word }++;
}


my $cnt = 0;
my ( @dict, %rdict );
foreach my $word ( sort { $word_freq{$b} <=> $word_freq{$a} || $b cmp $a } keys %word_freq ) {
    last if $word_freq{ $word } == 1; 


    my $repl_length = $cnt < 127 ? 2 : 3;
    if( length( $word ) > $repl_length ) {
        push @dict, $word;
        $rdict{ $word } = $cnt;
        $cnt++;
    }
}


foreach my $index ( 0..$
    print "$dict[$index]\0";
}
print "\1";


foreach my $word ( @words ) {
    my $index = $rdict{ $word };
    if ( defined $index && $index <= 127 ) {
        print "\0" . chr( $index );
    } elsif ( defined $index ) {
        my $byte1 = $index & 127;
        my $byte2 = $index >> 7;
        print "\1" . chr( $byte2 ) . chr( $byte1 );
    } else {
        print $word;
    }
}

Skrypt dekompresyjny deshakespeare.pl:

use strict;
use warnings;
use bytes;

local $/;
my $compressed = <>;
my $text = $compressed;
$text =~ s/^.+?\x{1}//ms;
my $dictionary = $compressed;
$dictionary =~ s/\x{1}.*$//ms;


my $cnt = 0;
my @dict;
foreach my $word ( split "\0", $dictionary ) {

    push @dict, $word;
}


my @words = split /(\x{0}.|\x{1}..)/ms, $text;
foreach my $word ( @words ) {
    if( $word =~ /^\x{0}(.)/ms ) {
        print $dict[ ord( $1 ) ];
    } elsif( $word =~ /^\x{1}(.)(.)/ms ) {
        my $byte1 = ord( $1 );
        my $byte2 = ord( $2 );
        my $index = ( $byte1 << 7 ) + $byte2;
        print $dict[ $index ];
    } else {
        print $word;
    }
}

Uruchom używając:

perl shakespeare.pl < pg100.txt >pg100.txt.compressed
perl deshakespeare.pl <pg100.txt.compressed >pg100.txt.restored
diff pg100.txt pg100.txt.restored