Dengan diskusi baru-baru ini tentang penggunaan alat kompresi dalam kode golf , saya pikir itu akan menjadi tantangan yang bagus untuk menulis kompresor teks Anda dan dekompresor.

Tantangan:

Tulis dua program : satu untuk mengompresi teks ASCII menjadi urutan byte, dan yang lain untuk mendekompresnya. Program tidak harus dalam bahasa yang sama.

Program pertama harus membaca sepotong teks ASCII (dari file atau dari input standar, atau menggunakan mekanisme apa pun yang paling alami untuk bahasa) dan mengeluarkan versi terkompresi dari itu. (Output terkompresi dapat terdiri atau byte arbitrer; tidak perlu dibaca.) Program kedua harus membaca output yang pertama dan membuat ulang input teks asli.

Mencetak:

Skor solusi akan menjadi jumlah dari tiga hitungan berikut:

1. The Panjang kompresor program karakter.
2. The Panjang output dari kompresor, mengingat masukan tes di bawah ini, dalam byte.
3. The panjang decompressor Program (jika berbeda dari kompresor) dalam karakter.

Anda harus mencatat ketiga hitungan dan jumlah mereka dalam jawaban Anda. Karena ini adalah kode golf, semakin rendah skornya, semakin baik.

Aturan dan batasan:

• Anda tidak dapat menggunakan alat atau pustaka kompresi atau dekompresi yang sudah ada sebelumnya, bahkan jika mereka dibundel dengan bahasa pilihan Anda. Jika ragu tentang apakah alat atau fungsi yang diberikan diizinkan, tanyakan.

• Program kompresor Anda harus mampu menangani input yang terdiri dari teks ASCII yang dapat dicetak , termasuk tab (ASCII 9) dan umpan baris (ASCII 10). Anda dapat, tetapi tidak diharuskan untuk, menangani Unicode dan / atau input biner yang berubah-ubah.

• Program dekompresor Anda harus menghasilkan output yang sama persis seperti yang diberikan kepada kompresor sebagai input. Secara khusus, berhati-hatilah untuk tidak mengeluarkan umpan garis tambahan jika input tidak memilikinya. (Input tes di bawah ini memang memiliki umpan garis tambahan, jadi Anda harus menguji ini secara terpisah. Tip untuk GolfScript:. '':n)

• Kompresor dan dekompresor Anda mungkin merupakan program yang sama (dengan mode yang sesuai dipilih misalnya dengan sakelar baris perintah). Dalam hal itu, panjangnya hanya dihitung satu kali .

• Program tidak boleh terlalu lambat atau haus akan memori . Jika mengompresi atau mendekompresi input tes membutuhkan waktu lebih dari satu menit pada desktop saya yang tidak terlalu baru (2.2GHz AMD Athlon64 X2) atau mengkonsumsi lebih dari satu gigabyte RAM, saya akan memutuskan bahwa solusi tidak valid. Batas-batas ini sengaja dibuat longgar - mohon jangan mendorongnya. (Lihat amandemen di bawah ini: Anda harus mampu menangani setidaknya 100 kB input dalam batas-batas ini.)

• Meskipun hanya input tes yang penting untuk penilaian, Anda setidaknya harus berupaya mengompresi teks input yang berubah-ubah. Sebuah solusi yang mencapai rasio kompresi yang layak hanya untuk input tes, dan untuk hal lain, secara teknis valid tetapi tidak akan mendapatkan upvote dari saya.

• Program kompresor dan dekompresor Anda harus lengkap . Secara khusus, jika mereka bergantung pada kemampuan untuk membaca beberapa file atau sumber daya jaringan yang bukan bagian dari lingkungan runtime standar bahasa yang Anda pilih, panjang file atau sumber daya itu harus dihitung sebagai bagian dari panjang program. (Ini untuk melarang "kompresor" yang membandingkan input ke file di web dan menghasilkan nol byte jika cocok. Maaf, tapi itu bukan trik baru lagi.)

Amandemen dan klarifikasi:

• Kompresor Anda harus dapat menangani file yang terdiri dari setidaknya 100 kB teks bahasa Inggris khas dalam waktu yang wajar dan penggunaan memori (paling banyak satu menit dan satu GB memori). Dekompresor Anda harus dapat mendekompresi output yang dihasilkan dalam batas yang sama. Tentu saja, mampu menangani file lebih lama dari itu baik-baik saja dan terpuji. Tidak apa-apa untuk membagi file input panjang menjadi potongan dan kompres secara individual, atau menggunakan cara lain untuk menukar efisiensi kompresi untuk kecepatan untuk input panjang.

• Kompresor Anda mungkin memerlukan inputnya untuk diberikan menggunakan representasi baris baru asli platform yang Anda pilih (LF, CR + LF, CR, dll.), Selama decompressor Anda menggunakan representasi baris baru yang sama dalam outputnya. Tentu saja, kompresor juga boleh untuk menerima segala jenis baris baru (atau bahkan hanya baris Unix terlepas dari platform), selama decompressor Anda kemudian mengeluarkan jenis baris yang sama seperti pada input asli.

Masukan tes:

Untuk menilai efisiensi kompresi dari jawaban, input tes berikut ( The Raven oleh Edgar Allan Poe, milik Project Gutenberg ) akan digunakan:

Once upon a midnight dreary, while I pondered, weak and weary,
Over many a quaint and curious volume of forgotten lore,
While I nodded, nearly napping, suddenly there came a tapping,
As of some one gently rapping, rapping at my chamber door.
"'T is some visiter," I muttered, "tapping at my chamber door--
                                          Only this, and nothing more."

Ah, distinctly I remember it was in the bleak December,
And each separate dying ember wrought its ghost upon the floor.
Eagerly I wished the morrow:--vainly I had sought to borrow
From my books surcease of sorrow--sorrow for the lost Lenore--
For the rare and radiant maiden whom the angels name Lenore--
                                          Nameless here for evermore.

And the silken sad uncertain rustling of each purple curtain
Thrilled me--filled me with fantastic terrors never felt before;
So that now, to still the beating of my heart, I stood repeating
"'T is some visiter entreating entrance at my chamber door
Some late visiter entreating entrance at my chamber door;--
                                          This it is, and nothing more."

Presently my soul grew stronger; hesitating then no longer,
"Sir," said I, "or Madam, truly your forgiveness I implore;
But the fact is I was napping, and so gently you came rapping,
And so faintly you came tapping, tapping at my chamber door,
That I scarce was sure I heard you"--here I opened wide the door;--
                                          Darkness there, and nothing more.

Deep into that darkness peering, long I stood there wondering, fearing,
Doubting, dreaming dreams no mortal ever dared to dream before;
But the silence was unbroken, and the darkness gave no token,
And the only word there spoken was the whispered word, "Lenore!"
This I whispered, and an echo murmured back the word, "Lenore!"
                                          Merely this and nothing more.

Back into the chamber turning, all my soul within me burning,
Soon again I heard a tapping, somewhat louder than before.
"Surely," said I, "surely that is something at my window lattice;
Let me see, then, what thereat is, and this mystery explore--
Let my heart be still a moment and this mystery explore;--
                                          'T is the wind and nothing more!"

Open here I flung the shutter, when, with many a flirt and flutter,
In there stepped a stately Raven of the saintly days of yore.
Not the least obeisance made he; not a minute stopped or stayed he;
But, with mien of lord or lady, perched above my chamber door--
Perched upon a bust of Pallas just above my chamber door--
                                          Perched, and sat, and nothing more.

Then this ebony bird beguiling my sad fancy into smiling,
By the grave and stern decorum of the countenance it wore,
"Though thy crest be shorn and shaven, thou," I said, "art sure no craven,
Ghastly grim and ancient Raven wandering from the Nightly shore,--
Tell me what thy lordly name is on the Night's Plutonian shore!"
                                          Quoth the Raven, "Nevermore."

Much I marvelled this ungainly fowl to hear discourse so plainly,
Though its answer little meaning--little relevancy bore;
For we cannot help agreeing that no living human being
Ever yet was blessed with seeing bird above his chamber door--
Bird or beast upon the sculptured bust above his chamber door,
                                          With such name as "Nevermore."

But the Raven, sitting lonely on the placid bust, spoke only
That one word, as if his soul in that one word he did outpour.
Nothing further then he uttered--not a feather then he fluttered--
Till I scarcely more than muttered, "Other friends have flown before--
On the morrow _he_ will leave me, as my hopes have flown before."
                                          Then the bird said, "Nevermore."

Startled at the stillness broken by reply so aptly spoken,
"Doubtless," said I, "what it utters is its only stock and store,
Caught from some unhappy master whom unmerciful Disaster
Followed fast and followed faster till his songs one burden bore--
Till the dirges of his Hope that melancholy burden bore
                                          Of 'Never--nevermore.'"

But the Raven still beguiling all my sad soul into smiling,
Straight I wheeled a cushioned seat in front of bird and bust and door;
Then, upon the velvet sinking, I betook myself to linking
Fancy unto fancy, thinking what this ominous bird of yore--
What this grim, ungainly, ghastly, gaunt and ominous bird of yore
                                          Meant in croaking "Nevermore."

This I sat engaged in guessing, but no syllable expressing
To the fowl whose fiery eyes now burned into my bosom's core;
This and more I sat divining, with my head at ease reclining
On the cushion's velvet lining that the lamplight gloated o'er,
But whose velvet violet lining with the lamplight gloating o'er
                                          _She_ shall press, ah, nevermore!

Then, methought, the air grew denser, perfumed from an unseen censer
Swung by seraphim whose foot-falls tinkled on the tufted floor.
"Wretch," I cried, "thy God hath lent thee--by these angels he hath sent thee
Respite--respite and nepenthe from thy memories of Lenore!
Quaff, oh quaff this kind nepenthe, and forget this lost Lenore!"
                                          Quoth the Raven, "Nevermore."

"Prophet!" said I, "thing of evil!--prophet still, if bird or devil!--
Whether Tempter sent, or whether tempest tossed thee here ashore,
Desolate yet all undaunted, on this desert land enchanted--
On this home by Horror haunted--tell me truly, I implore--
Is there--_is_ there balm in Gilead?--tell me--tell me, I implore!"
                                          Quoth the Raven, "Nevermore."

"Prophet!" said I, "thing of evil--prophet still, if bird or devil!
By that Heaven that bends above, us--by that God we both adore--
Tell this soul with sorrow laden if, within the distant Aidenn,
It shall clasp a sainted maiden whom the angels name Lenore--
Clasp a rare and radiant maiden whom the angels name Lenore."
                                          Quoth the Raven, "Nevermore."

"Be that word our sign of parting, bird or fiend!" I shrieked, upstarting--
"Get thee back into the tempest and the Night's Plutonian shore!
Leave no black plume as a token of that lie thy soul hath spoken!
Leave my loneliness unbroken!--quit the bust above my door!
Take thy beak from out my heart, and take thy form from off my door!"
                                          Quoth the Raven, "Nevermore."

And the Raven, never flitting, still is sitting, still is sitting
On the pallid bust of Pallas just above my chamber door;
And his eyes have all the seeming of a demon's that is dreaming,
And the lamplight o'er him streaming throws his shadow on the floor;
And my soul from out that shadow that lies floating on the floor
                                          Shall be lifted--nevermore!

Input tes yang benar (dikodekan dengan LF baris baru gaya Unix) harus sepanjang 7043 byte, dan memiliki hash MD5 heksadesimal 286206abbb7eca7b1ab69ea4b81da227. ( md5sum -tharus menghasilkan nilai hash yang sama bahkan jika Anda menggunakan baris baru CR + LF pada DOS / Windows.) Output dari dekompresor Anda harus memiliki panjang dan hash yang sama.

Ps. Ingatlah bahwa tantangan ini hanya sesulit yang Anda lakukan. Sungguh, apa pun di bawah 7043 dianggap sebagai skor yang baik. (Di ujung lain skala, saya akan sangat terkesan jika ada yang mencapai skor di bawah 2500.)

Perl, 3502 = 133 + 3269 + 100

Encoder:

#!/usr/bin/perl -0
$_=<>;for$e(map{~chr}0..255){++$p{$_}for/..|.\G./gs;
%p=$s=(sort{$p{$a}<=>$p{$b}}keys%p)[-1];$d.=/\Q$e/?$/:s/\Q$s/$e/g&&$s}print$_,$d

Dan dekoder:

#!/usr/bin/perl -0777
sub d{($p=$d{$_})?d(@$p):print for@_}
sub r{%d=map{chr,ord($c=pop)&&[pop,$c]}0..255;&d}r<>=~/./gs

Untuk pembuat puritan yang lebih suka menghindari penggunaan sakelar baris perintah: Anda dapat menghapus baris shebang dan menambahkan $/=chr; ke encoder dan $/=$,;ke decoder untuk mendapatkan efek yang sama. (Ini akan membawa skor hingga 3.510.)

Kode ini menggunakan skema kompresi yang sangat primitif:

• Temukan bigram dua-char yang paling sering muncul dalam teks sumber.
• Ganti bigram dengan nilai byte yang saat ini tidak digunakan.
• Ulangi sampai tidak ada lagi bigrams yang diulang (atau tidak ada lagi nilai byte yang tidak digunakan).

Seseorang di luar sana mungkin mengenali ini sebagai versi kompresi "re-pair" yang disederhanakan (kependekan dari pasangan rekursif).

Ini bukan skema kompresi umum yang sangat baik. Itu hanya baik dengan hal-hal seperti teks ASCII, di mana ada banyak nilai byte yang tidak digunakan, dan bahkan kemudian itu biasanya tidak lebih dari rasio 45-50%. Namun, ini memiliki keuntungan karena dapat diterapkan dengan kode minimal. Dekompresor khususnya bisa sangat padat. (Sebagian besar karakter dalam skrip dekoder saya adalah untuk mengambil kamus bigram.)

Berikut adalah versi kode yang tidak dipisahkan:

#!/usr/bin/perl
use strict;
use warnings;
# Run with -d to decode.
if ($ARGV[0] eq "-d") {
    shift;
    $_ = join "", <>;
    my @in = split //;
    my %dict;
    foreach my $n (0 .. 255) {
        my $c = shift @in;
        $dict{chr $n} = [ $c, shift @in ] if ord $c;
    }
    sub decode {
        foreach (@_) {
            if ($dict{$_}) {
                decode(@{$dict{$_}});
            } else {
                print $_;
            }
        }
    }
    decode @in;
} else {
    $_ = join "", <>;
    my @dict;
    for (my $n = 255 ; $n >= 0 ; --$n) {
        my $symbol = chr $n;
        if (!/\Q$symbol/) {
            my %pop;
            ++$pop{$_} for /../gs, /(?!^)../gs;
            my $str = (sort { $pop{$b} <=> $pop{$a} } keys %pop)[0];
            s/\Q$str/$symbol/g;
            $dict[$n] = $str;
        }
    }
    for (0..255) { $dict[$_] ||= "\0" }
    print @dict, $_;
}

Satu ekspresi dalam encoder golf membutuhkan penjelasan, saya pikir, dan itu adalah (sort{$p{$a}<=>$p{$b}}keys%p)[-1], untuk mendapatkan kunci dengan nilai tertinggi. Itu sepertinya harus ditulis sebagai (sort{$p{$b}<=>$p{$a}}keys%p)[0], yang melakukan hal yang sama dan satu karakter lebih pendek. Alasan saya tidak menulis seperti itu adalah karena ia mengubah kunci yang dipilih dalam kasus ketika ada beberapa kunci dengan nilai tertinggi. Secara kebetulan, ini menyebabkan output yang dihasilkan untuk input uji menjadi 10 byte lebih lama. Saya benci untuk mengambil karakter ekstra yang tidak berguna, tetapi tidak cukup untuk mengorbankan 9 poin dari skor saya.

Di wajah Anda, Golfscript! (Haha, Golfscript benar-benar akan datang ke sini dan menendang pantatku jika itu bisa mendengarku.)

Python, 3514 = 294 + 2894 + 326

Pada dasarnya implementasi bzip2 . Itu melakukan transformasi Burrows-Wheeler , transformasi pindah ke depan , pengkodean Huffman sederhana menjadi aliran bit, mengubah aliran bit ke integer dan menulis byte.

Encoder:

import sys
S=range(128)
H={0:'0'}
for b in range(7):
 for i in range(1<<b,2<<b):H[i]='1'*b+'10'+bin(i)[3:]
I=sys.stdin.read()+'\0'
N='1'
for x in sorted(I[i:]+I[:i]for i in range(len(I))):i=S.index(ord(x[-1]));N+=H[i];S=[S[i]]+S[:i]+S[i+1:]
N=int(N,2)
while N:sys.stdout.write(chr(N%256));N>>=8

Sadalah antrian pindah-ke-depan, Hadalah enkoder Huffman, danN merupakan bitstream.

Pengkodean mengurangi input tes menjadi sekitar 41% dari ukuran aslinya.

Dekoder:

import sys
N=0
b=1
for c in sys.stdin.read():N+=ord(c)*b;b<<=8
N=bin(N)[3:]
S=range(128)
L=''
while N:
 n=N.find('0')
 if n:i=2**n/2+int('0'+N[n+1:2*n],2);N=N[2*n:]
 else:i=0;N=N[1:]
 L+=chr(S[i]);S=[S[i]]+S[:i]+S[i+1:]
S=''
i=L.find('\0')
for j in L:S=L[i]+S;i=L[:i].count(L[i])+sum(c<L[i]for c in L)
sys.stdout.write(S[:-1])

8086 Assembler / MS_DOS

Kompresor: 155

jNiAxBCO2I7AM/+9/QW5AAGK2TPAq4rDqv7D4va6AQkz9lK0BrL/zSFadDK7
/f+DwwM733QNOTd19ThHAnXwid7r34k1iEUC6BMAtACKRQJr8AODxwPryrQC
zSHrxFIz0ovGuwMA9/Nai9iKztPL0ePQ0nMWgPr+cgtSsv60Bs0hWoDq/rQG
zSGyAf7JdeA5/XUHA+2DxQP+xsM=

Data: 3506

Dekompresor: 203

ieWD7CCM2IDEEI7YjsAz/7kAAYrZM8CrisOq/sPi9rYJxkb0Abn9BehtAIl2
/uhTAOhkAIl28Dv3cy3oRgCLRv6JBYt28Il2/oM8AHQEizTr94pEAohFAoPH
AznPddL+xgPJg8ED68mLdv6JNYM8AHQEizTr94pEAohFAol+/on+aFgBgzwA
dAdWizTo9f9etAaKVALNIcMz9ojz/k70dRu0BrL/zSF0IDz+cgi0BrL/zSEE
/sZG9AiIRvLQZvLR1v7Ldddr9gPDzSA=

Total: 3864

Gunakan dekoder Base64 ini dan simpan file biner sebagai 'kompres.com' dan 'dekompres.com' lalu lakukan:

compress < source > compressed_file
decompress < compressed_file > copy_of_source

dalam shell DOS (diuji dengan WinXP). Tidak ada kesalahan saat memeriksa sehingga mengompresi file besar akan membuat hasil yang salah. Beberapa tambahan kecil dan itu bisa mengatasi file berukuran apa pun. Juga, ia tidak dapat mendekompres ke biner karena tidak dapat menampilkan nilai 0xff (data terkompresi keluar dari nilai 0xff sebagai 0xfe 0xff dengan 0xfe lolos sebagai 0xfe 0xfe). Menggunakan nama file baris perintah akan mengatasi masalah output biner, tetapi akan menjadi executable yang lebih besar.

Bash Poem (566 + 117) + 4687 = 5370

Untuk bersenang-senang, saya menyamar sebagai sebuah puisi:

for I in my chamber nodded, nearly napping, suddenly heard rapping, tapping upon my door    \
"'T is some visiter" \ I\  muttered, o\'er lamplight "nothing more" \
just this sainted maiden whom the angels name Lenore    \
And "Prophet!" said me "thing of evil" -- "prophet still, if bird or devil!"    \
Leave no token of that lie thy soul hath spoken and sitting take thy ore from This floor    \
But you velvet bird from some shore above   \
here this with sad raven before his word still spoke nothing    \
"                                          " Quoth the Raven Never more;                    do C=$[C+1];E=`perl -e "print chr($C+128)"`;echo "s/$I/$E/g">>c;echo "s/$E/$I/g">>d;done;LANG=C sed -f $1;rm c d

Ini adalah kompresor terpadu: dijalankan dengan opsi "c" itu akan memampatkan, dan dengan "d" itu akan mendekompresi. Ini memiliki dua bagian: versi 566 byte "reader digest" dari puisi dan (2) sufiks 117 byte di mana semua "nyata" bash dilakukan.

Dengan hati-hati (misalnya memulai puisi dengan "for I in") bash akan menafsirkan versi "lossy" dari puisi sebagai sebuah array. Ini menggantikan setiap elemen array dengan karakter non-ASCII (kami menganggap inputnya adalah ASCII sehingga tidak ada tabrakan). Satu keuntungan kecil dari solusi ini: karena kita menggunakan fakta bahwa kita dapat mengasumsikan inputnya adalah ASCII, output dari kompresi ini tidak akan pernah lebih lama dari inputnya, terlepas dari apa input dan / atau bagian yang hilang.

Aturan yang paling dekat dengan pelanggaran adalah aturan tentang memberikan rasio kompresi yang layak pada teks lain. Namun, ini mencukur 1386 byte dari teks GPL V2, lebih dari ukurannya sendiri, yang tampaknya cocok dengan definisi OPs decent. Jadi tampaknya memberikan apa yang disebutdecent kompresi pada teks umum. Ini karena hampir semua teks bahasa Inggris akan memiliki "the" "that" dll. Jelas itu akan bekerja lebih baik jika Anda mengganti bagian "lossy" dengan teks yang menyerupai aslinya yang ingin Anda kompres tanpa kehilangan.

Memisahkan gambar dan audio menjadi bagian lossy dan non-lossy adalah teknik yang dikenal. Ini tidak berfungsi dengan baik untuk teks: 4687 byte tidak terlalu bagus bahkan jika kita mengecualikan 566 byte dari versi lossy dan kita tidak bisa benar-benar secara otomatis menghasilkan versi teks lossy seperti yang kita bisa untuk audio. Di sisi positifnya, ini berarti setiap kali Anda mengompres sesuatu dengan kompresor ini, Anda dapat bersenang-senang membuat versi lossy dengan tangan. Jadi ini sepertinya solusi "untuk bersenang-senang" yang masuk akal.

C ++, 4134 byte (kode = 1357, dikompresi = 2777)

Ini melakukan transformasi Burrows-Wheeler + Move-To-Front seperti Keith Randall, tetapi kemudian mengompresi urutan byte yang dihasilkan menggunakan Range Coder adaptif . Sayangnya, peningkatan kompresi dari range coder tidak cukup untuk mengimbangi verbositas C ++. Saya dapat menggunakan kode ini lagi, yaitu menggunakan metode input / output yang berbeda, tetapi tidak akan cukup untuk mengalahkan kiriman lainnya dengan algoritma saat ini. Kode ini spesifik untuk Windows, dan hanya teks ascii yang didukung.
Untuk mengkompres: "C text_file compressed_file"
Untuk mendekompresi: "D compressed_file uncompressed_file"
Hampir semua kesalahan baris perintah atau kesalahan file akan merusak program, dan perlu waktu lebih baik untuk menyandikan atau mendekodekan puisi.

#include <windows.h>
#include <algorithm>
typedef DWORD I;typedef BYTE u;
#define W while
#define A(x)for(a=0;a<x;a++)
#define P(x)*o++=x;
I q,T=1<<31,B=T>>8,a,l,f[257],b,G=127,p=G,N=255;I Y(u*i,u*j){return
memcmp(i,j,l)<0;}I E(u*i,u*o){b=0;I L=0,h=0,R=T;u*c=o,*e=i+l;W(i<e){I
r=R/p,s=0;A(*i)s+=f[a];s*=r;L+=s;R=*i<N?r*f[*i++]++:R-s;p++;W(R<=B){if((L>>23)<N){for(;h;h--)P(N)P(L>>23)}else{if(L&T){o[-1]++;for(;h;h--)P(0)P(L>>23)}else
h++;}R<<=8;L<<=8;L&=T-1;}}P(L>>23)P(L>>15)P(L>>7)return
o-c;}void D(u*i,u*o){I R=128,L=*i>>1;u*e=o+l;W(o<e){W(R<=B){L<<=8;L|=((*i<<7)|(i++[1]>>1))&N;R<<=8;}I
h=R/p,m=L/h,x=0,v=0;W(v<=m)v+=f[x++];P(--x);L-=h*(v-f[x]);R=h*f[x]++;p++;}}void
main(I Z,char**v){u d[1<<16];I c=*v[1]<68,s;HANDLE F=CreateFileA(v[2],T,0,0,3,0,0),o=CreateFileA(v[3],T/2,0,0,2,0,0);ReadFile(F,d,GetFileSize(F,0),&l,0);l=c?l:*(I*)d;A(G)f[a]=1;u M[256];A(G)M[a]=a+1;u*g=new u[l*3],*h=g+l;if(c){memcpy(d+l,d,l);u**R=new
u*[l];A(l)R[a]=d+a;std::sort(R,R+l,Y);A(l){b=R[a][l-1];I
i=strchr((char*)M,b)-(char*)M;memmove(M+1,M,i);*M=g[a]=b;h[a]=i;}s=E(h,d+l+8);}else{D(d+8,g);A(l){I
k=g[a];g[a]=M[k];memmove(M+1,M,k);*M=g[a];}}u**j=new u*[l];A(l)j[a]=new
u[l*2],memset(j[a],0,l*2),j[a]+=l;A(l){for(b=0;b<l;)*--j[b]=g[b++];std::sort(j,j+l,Y);}if(c){A(l){if(!memcmp(j[a],d,l)){I*t=(I*)(d+l);*t=l;t[1]=a;g=d+l,l=s+8;}}}else
g=j[*(I*)(d+4)];WriteFile(o,g,l,&q,0);}

JavaScript, 393 (kode) + 3521 (tes) = 3914 (total)

Program ini secara iteratif mengganti nilai byte yang tidak terpakai untuk potongan karakter 2- ke 4- dari input. Setiap substitusi dinilai berdasarkan frekuensi dan panjang chunk asli, dan subtitusi terbaik dipilih setiap kali. Saya akan menambahkan tahap pengkodean Huffman akhir jika saya bisa mencari tahu bagaimana melakukannya dalam jumlah karakter yang relatif kecil. Dekompresi pada dasarnya adalah serangkaian operasi mencari dan mengganti.

Pemakaian

C () memberikan kompresi; U () memberikan dekompresi. Karena string JavaScript didasarkan pada unit kode Unicode 16-bit, hanya 8 bit yang paling signifikan dari setiap unit kode yang digunakan dalam format data terkompresi; ini kompatibel dengan fungsi btoa () dan atob () Firefox untuk pengkodean Base64. ( contoh penggunaan )

Program ini hanya dapat berfungsi di Firefox karena opsi "g" tidak standar untuk .replace ().

Kode

Kode golf:

S=String.fromCharCode;function C(c){h=[];for(f=0;129>f;++f){g='';i=0;for(e=2;5>e;++e){d={};for(a=0;a<=c.length-e;a+=e)b="K"+c.substr(a,e),d[b]=d[b]?d[b]+1:1;for(b in d)a=d[b],a=a*e-(1+e+a),a>i&&(g=b.slice(1),i=a)}if(!g)break;h[f]=g;c=c.replace(g,S(127+f),"g")}return h.join("\1")+"\1"+c}function U(a){c=a.split("\1");a=c.pop();for(b=c.length,d=127+b;b--;)a=a.replace(S(--d),c[b],"g");return a}

Sebelum bermain golf:

function compress(str) {

    var hash, offset, match, iteration, expansions, bestMatch, bestScore, times, length, score;

    expansions = [];

    for (iteration = 0; iteration < 129; ++iteration) {

        bestMatch = null;
        bestScore = 0;

        for (length = 2; length < 5; ++length) {

            hash = {};

            for (offset = 0; offset <= str.length - length; offset += length) {
                match = 'K' + str.substr(offset, length);
                hash[match] = hash[match] ? hash[match] + 1 : 1;
            }

            for (match in hash) {
                times = hash[match];
                score = times * length - (1 + length + times);
                if (score > bestScore) {
                    bestMatch = match.slice(1);
                    bestScore = score;
                }
            }

        }

        if (!bestMatch) {
            break;
        }

        expansions[iteration] = bestMatch;
        str = str.replace(bestMatch, String.fromCharCode(127 + iteration), 'g');

    }

    return expansions.join('\u0001') + '\u0001' + str;
}

function uncompress(str) {
    var i, j, expansions;

    expansions = str.split('\u0001');
    str = expansions.pop();

    for (j = expansions.length, i = 127 + j; j--;) {
        str = str.replace(String.fromCharCode(--i), expansions[j], 'g');
    }

    return str;
}

PHP, (347 + 6166 + 176) = 6689

Jadi saya pergi dengan pendekatan substitusi kamus + sederhana.

Jika sebuah kata muncul beberapa kali dan lebih pendek untuk (menyandikan kata + menyimpan entri substitusi) maka itu membuat penggantian. Jika "kata" kebetulan berupa angka, ia melakukannya untuk mencegah penggantian yang tidak disengaja selama dekompresi. "Kamus" substitusi digabungkan dengan byte nol, diikuti oleh dua byte nol, diikuti oleh badan pengganti bekerja.

Kemungkinan peningkatan:

• Windows tidak suka piping lebih dari 4kb data, jadi temukan cara yang lebih baik daripada menggunakan file.
• Kemampuan untuk mencocokkan string spasi panjang dan menghitungnya sebagai "kata-kata" tanpa menambahkan terlalu banyak kode.
• Menghasilkan pengganti yang lebih baik daripada menggunakan angka.

Penggunaan: kompresor mencari file bernama "i" dan menulis data yang dikompresi ke "o". Dekompresor mencari "o" dan menulis data yang tidak terkompresi ke "d". Ini adalah solusi buruk saya untuk Windows tidak menyukai pipa data di sekitar.

compress.php (347)

<?$d=file_get_contents('i');$z=chr(0);preg_match_all('|\b(\w+)\b|',$d,$m);$n=0;foreach($m[0]as$w){$l=strlen($w);$q[$w]=isset($q[$w])?$q[$w]+$l:$l;}arsort($q);foreach($q as$w=>$s){$l=strlen($w);$c=$s/$l;if($c*strlen($n)+$l<$s||is_int($w)){$d=preg_replace('|\b'.preg_quote($w).'\b|',$n++,$d);$f[]=$w;}}file_put_contents('o',implode($z,$f).$z.$z.$d);

Versi diperluas dengan komentar dan penjelasan.

Keluarkan sampel tanpa kamus. Agak lucu untuk dilihat.
Ukuran normal: 6166 .

Ah, distinctly I remember it 45 in 0 bleak December,
25 each separate dying ember wrought its ghost 39 0 37.
Eagerly I wished 0 88:--vainly I had sought to borrow
From 9 books surcease of 43--43 for 0 lost 8--
For 0 rare 1 67 40 54 0 26 38 8--
                                          Nameless 63 for evermore.

25 0 silken sad uncertain rustling of each purple curtain
Thrilled me--filled me 19 fantastic terrors never felt 17;
So 4 now, to 13 0 beating of 9 64, I stood repeating
"'T is 57 31 36 49 at 9 2 5
Some late 31 36 49 at 9 2 5;--
                                          58 it is, 1 10 16."

decompress.php (176)

<?$z=chr(0);$d=file_get_contents('o');list($w,$d)=explode($z.$z,$d);$w=explode($z,$w);$n=0;foreach($w as$r){$d=preg_replace('|\b'.$n++.'\b|',$r,$d);};file_put_contents('d',$d);

Versi diperluas dengan penjelasan.

Setiap saran untuk penyempurnaan diterima.

Sunting: Menambahkan versi kode "belum dibuka" dan menambahkan banyak komentar. Harus mudah diikuti.

GolfScript, 3647 (ukuran terkompresi 3408 + ukuran kode 239)

128,{[.;]''+}%:d;8:k;{2k?={1k+:k;}*}:|;{2base}:b;{.[0]*@b+0@->}:$;.0=
{'':&,:i;1/{.d&@+?.0<{;d,i@d&@:&.0=:i;[+]+:d;k$\|}{:i;&\+:&;}if}%[0]k*+[]*8/{b}%"\0"\+}
{1>{8$}/][]*:^;{^k<b^k>:^;}:r~{.}{d,|d=:&r..d,<{d=}{;&}if[1<&\+]d\+:d;}while;}if

Algoritma yang digunakan adalah kompresi LZW dengan kode lebar variabel. Baris pertama adalah kode bersama, yang kedua adalah kode kompresi dan yang ketiga adalah kode dekompresi.

Ini menangani file dengan karakter ASCII dalam kisaran 1-127, dan mengenali file yang dikompresi secara otomatis (mereka mulai dengan 0 byte), jadi tidak ada parameter yang diperlukan untuk dekompresi.

Contoh dijalankan:

$ md5sum raven.txt
286206abbb7eca7b1ab69ea4b81da227  raven.txt
$ ruby golfscript.rb compress.gs < raven.txt > raven.lzw
$ ls -l raven.lzw
-rw-r--r-- 1 ahammar ahammar 3408 2012-01-27 22:27 raven.lzw
$ ruby golfscript.rb compress.gs < raven.lzw | md5sum
286206abbb7eca7b1ab69ea4b81da227  -

Catatan: Saya memulai ini jauh sebelum persyaratan untuk menangani 100kb ditambahkan, jadi saya belum mengujinya pada input sebesar itu. Namun, dibutuhkan sekitar 30 detik untuk mengompresi input tes dan 5 detik untuk mendekompresnya, menggunakan sekitar 20MB memori pada puncaknya.

Haskell, 3973

Terlambat ke pesta, dan tidak akan menang, tapi aku senang menulisnya jadi aku mungkin juga mempostingnya.

Ini adalah implementasi lebar-lebar LZW yang mudah, dengan kamus yang secara eksplisit terbatas pada ASCII yang dapat dicetak, tab, dan umpan baris. Jalankan tanpa argumen, memampatkan input standar ke file C. Jalankan dengan argumen apa pun (tapi "--decompress" akan menjadi taruhan yang masuk akal), itu mendekompres file Cke output standar.

import List
import System
import Data.Binary
q=head
main=getArgs>>=m
m[]=getContents>>=encodeFile"C".s 97 128 1 0.e 97h
m _=decodeFile"C">>=putStr.d tail""96h.u 97 128
h=zip[0..].map(:[])$"\t\n"++[' '..'~']
e _ _[]=[]
e n s y=c:e(n+1)((n,take(1+l)y):s)(drop(l)y)where{Just(c,p)=find((`isPrefixOf`y).snd)s;l=length p}
d _ _ _ _[]=""
d f p n s(x:y)=t++d id t(n+1)(f$(n,p++[q t]):s)y where t=maybe(p++[q p])id$lookup x s
s _ _ _ a[]=a::Integer
s n w o a y|n>w=s n(2*w)o a y|0<1=s(n+1)w(o*w)(a+o*q y)(tail y)
u _ _ 0=[]
u n w x|n>w=u n(2*w)x|0<1=(x`mod`w::Integer):u(n+1)w(x`div`w)

• ukuran kode: 578
• ukuran sampel terkompresi: 3395