Desafio de compactação de texto sem perdas no idioma inglês [fechado]

Desafio:

Seu desafio (se você optar por aceitá-lo) é compactar e descompactar as " Obras Completas de William Shakespeare ", de 5 MB, como encontradas aqui: http://www.gutenberg.org/cache/epub/100/pg100.txt

(MD5: a810f89e9f8e213aebd06b9f8c5157d8)

Regras:

• Você deve receber entrada via STDINe saída via STDOUT...
• ... e você deve fornecer um resultado descompactado idêntico à entrada.
  • (Isso significa que você deve ser capaz de cat inpt.txt | ./cmprss | ./dcmpress | md5obter o mesmo MD5 acima.)
  • (Qualquer coisa via STDERRdeve ser descartada.)
• Você deve usar menos de 2048 caracteres para o seu código-fonte total.
  • (Isso não é código-golfe. Você não está sendo pontuado com base no tamanho do código-fonte. Essa é apenas uma regra para manter as coisas finitas.)
  • (Pegue o comprimento concatenado de todo o código-fonte, se você o tiver dividido.)
• Você também deve (teoricamente) processar entradas de texto simples semelhantes.
  • (por exemplo, codificação embutida de um mecanismo que é capaz apenas de produzir a entrada fornecida por Shakespeare é inaceitável.)
  • (O tamanho compactado de outros documentos é irrelevante - desde que o resultado descompactado seja idêntico à entrada alternativa.)
• Você pode usar qualquer opção de idioma (s).
  • (por exemplo, sinta-se livre para comprimir awke descomprimir usando java)
• Você pode escrever dois programas separados ou combiná-los com algum tipo de "opção", como desejar.
  • (Deve haver demonstrações claras de como chamar os modos de compactação e descompactação)
• Você não pode usar nenhum comando externo (por exemplo, através exec()).
  • (Se você estiver usando uma linguagem shell - desculpe. Você terá que se contentar com os built-ins. Você pode postar uma resposta "inaceitável" para compartilhar e divertir - mas isso não será julgado! )
• Você não pode usar nenhuma função interna ou fornecida pela biblioteca que tenha o objetivo declarado de compactar dados (como gz, etc.)
  • (Alterar a codificação não é considerado compactação nesse contexto. Pode ser aplicada alguma discrição aqui. Sinta-se à vontade para argumentar sobre a aceitabilidade da sua solução no envio.)
• Por favor, tente se divertir se optar por participar!

Todas as boas competições têm uma definição objetiva de vitória; ergo:

• Desde que todas as regras sejam respeitadas, a menor saída compactada (em STDOUTbytes) vence.
  • (Relate sua saída por favor ./cmprss | wc -c)
• Em caso de empate (tamanhos de saída idênticos), o maior número de votados na comunidade vence.
• No caso de um segundo sorteio (votos idênticos da comunidade), escolherei um vencedor com base em um exame completamente subjetivo de elegância e pura genialidade. ;-)

Como enviar:

Formate sua entrada usando este modelo:

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

<description>  (Detail is encouraged!)

    <CODE...
    ...>

<run instructions>

Eu encorajaria leitores e apresentadores a conversar através de comentários - acredito que há uma oportunidade real para as pessoas aprenderem e se tornarem melhores programadores através do codegolf.stack.

Ganhando:

Estou de férias em breve: posso (ou não) monitorar os envios nas próximas semanas e encerrarei o desafio no dia 19 de setembro. Espero que isso ofereça uma boa oportunidade para as pessoas pensarem e se submeterem - e para um compartilhamento positivo de técnicas e idéias.

Se você aprendeu algo novo ao participar (como leitor ou remetente), deixe um comentário de incentivo.

Perl 5, 3651284

Apenas um esquema de dicionário baseado em palavras simples. Analisa a frequência da palavra do corpus e a utiliza para determinar se deve usar um ou dois bytes de sobrecarga por palavra. Usa dois símbolos especiais para os bytes \ 0 e \ 1, pois eles não aparecem no corpus. Existem muitos outros símbolos que podem ser usados. Isso não foi feito. Não faz nenhuma codificação huffman ou nada desse jazz.

Script de compressão 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;
    }
}

Script de descompressão 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;
    }
}

Execute usando:

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