Po niedawnej dyskusji na temat korzystania z narzędzi kompresji w kodzie golfowym pomyślałem, że napisanie własnego kompresora i dekompresora byłoby niezłym wyzwaniem.

Wyzwanie:

Napisz dwa programy : jeden do kompresji tekstu ASCII do sekwencji bajtów, a drugi do jego dekompresji. Programy nie muszą być w tym samym języku.

Pierwszy program powinien odczytać fragment tekstu ASCII (z pliku lub ze standardowego wejścia lub używając dowolnego mechanizmu najbardziej naturalnego dla języka) i wypisać jego skompresowaną wersję. (Skompresowane dane wyjściowe mogą składać się z dowolnych bajtów; nie muszą być czytelne.) Drugi program powinien odczytać dane wyjściowe pierwszego i odtworzyć oryginalny tekst wejściowy.

Punktacja:

Wynik rozwiązania będzie sumą następujących trzech liczb:

1. Długość sprężarki programu w postaci.
2. Długość wyjściu sprężarki, ze względu na wejście testu poniżej, w bajtach.
3. Długość dekompresor programu (jeżeli różni się od sprężarki) w znakach.

Powinieneś zanotować wszystkie trzy liczby i ich sumę w swojej odpowiedzi. Ponieważ jest to kod golfowy, im niższy wynik, tym lepiej.

Zasady i ograniczenia:

• Nie możesz używać żadnych wcześniej istniejących narzędzi lub bibliotek do kompresji lub dekompresji, nawet jeśli są dostarczane w pakiecie z wybranym językiem. W razie wątpliwości, czy dane narzędzie lub funkcja jest dozwolona, ​​zapytaj.

• Twój program kompresujący musi być w stanie obsłużyć dane wejściowe składające się z dowolnego tekstu ASCII do wydruku , w tym tabulatorów (ASCII 9) i znaków nowej linii (ASCII 10). Użytkownik może, ale nie musi, obsługiwać dowolne dane Unicode i / lub dane binarne.

• Twój program dekompresyjny musi wytwarzać dokładnie takie same wyjście, jakie podano sprężarce jako wejście. W szczególności uważaj, aby nie wysyłać końcowego wiersza linii, jeśli dane wejściowe go nie miały. (Poniżej Wejście Test ma nowego wiersza spływu, więc trzeba do tego testu oddzielnie dla GolfScript Tip. '':n).

• Kompresor i dekompresor mogą być tym samym programem (z wybranym trybem wybranym np. Z przełącznikiem wiersza poleceń). W takim przypadku jego długość jest liczona tylko raz .

• Programy nie powinny być zbyt wolne ani wymagające pamięci . Jeśli kompresja lub dekompresja wejścia testowego zajmie więcej niż minutę na moim nie tak nowym komputerze stacjonarnym (AMD Athlon64 X2 2,2 GHz) lub zużyje więcej niż gigabajt pamięci RAM, będę orzekać, że rozwiązanie jest nieprawidłowe. Limity te są celowo luźne - staraj się ich nie przekraczać. (Patrz poprawka poniżej: musisz być w stanie obsłużyć co najmniej 100 kB danych wejściowych w tych granicach).

• Nawet jeśli tylko wejście testowe ma znaczenie dla punktacji, powinieneś przynajmniej starać się skompresować dowolny tekst wejściowy. Rozwiązanie, które osiąga przyzwoity stopień kompresji tylko dla wejścia testowego i nic poza tym, jest technicznie ważne, ale nie dostanie ode mnie opinii.

• Programy kompresora i dekompresora powinny być samodzielne . W szczególności, jeśli zależy to od możliwości odczytania pliku lub zasobu sieciowego, który nie jest częścią standardowego środowiska wykonawczego wybranego języka, długość tego pliku lub zasobu należy liczyć jako część długości programu (programów). (Ma to na celu wyłączenie „kompresorów”, które porównują dane wejściowe z plikiem w sieci i jeśli pasują, wyprowadzają zero bajtów. Przepraszam, ale to już nie jest nowa sztuczka.)

Poprawki i wyjaśnienia:

• Kompresor musi obsługiwać pliki składające się z co najmniej 100 kB typowego tekstu w języku angielskim w rozsądnym czasie i przy użyciu pamięci (maksymalnie jedna minuta i jeden GB pamięci). Twój dekompresor musi być w stanie dekompresować wynikowy wynik w tych samych granicach. Oczywiście możliwość dłuższego przetwarzania plików jest w porządku i godna pochwały. Można podzielić długie pliki wejściowe na fragmenty i skompresować je indywidualnie lub użyć innych środków, aby obniżyć wydajność kompresji w celu uzyskania szybkości dla dużych danych wejściowych.

• Twój kompresor może wymagać podania danych wejściowych przy użyciu natywnej reprezentacji nowej linii preferowanej platformy (LF, CR + LF, CR itp.), O ile dekompresor używa tej samej reprezentacji nowej linii na wyjściu. Oczywiście kompresor akceptuje również wszelkie nowe znaki (lub nawet nowe znaki uniksowe niezależnie od platformy), o ile dekompresor wypisuje te same znaki, co na oryginalnym wejściu.

Wejście testowe:

Aby ocenić skuteczność kompresji odpowiedzi, zostaną użyte następujące dane testowe ( The Raven Edgara Allana Poe, dzięki uprzejmości Project Gutenberg ):

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!

Prawidłowe wejście testowe (zakodowane za pomocą znaków nowej linii LF w stylu uniksowym) powinno mieć długość 7043 bajtów i mieć szesnastkowy skrót MD5 286206abbb7eca7b1ab69ea4b81da227. ( md5sum -tpowinien generować tę samą wartość skrótu, nawet jeśli używasz nowej linii CR + LF w systemie DOS / Windows). Wyjście dekompresora powinno mieć tę samą długość i skrót.

Ps. Pamiętaj, że to wyzwanie jest tak trudne, jak to tylko możliwe. Naprawdę, wszystko poniżej 7043 liczy się jako dobry wynik. (Na drugim końcu skali będę pod ogromnym wrażeniem, jeśli ktoś osiągnie wynik poniżej 2500.)

Perl, 3502 = 133 + 3269 + 100

Enkoder:

#!/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

I 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

Dla purystów, którzy wolą unikać używania przełączników wiersza polecenia: Możesz usunąć linię Shebang i dodać $/=chr;do kodera i $/=$,;dekodera, aby uzyskać ten sam efekt. (To zwiększyłoby wynik do 3510.)

Ten kod używa bardzo prymitywnego schematu kompresji:

• Znajdź dwuznakowy bigram, który pojawia się najczęściej w tekście źródłowym.
• Zamień bigram na aktualnie nieużywaną wartość bajtu.
• Powtarzaj, aż nie będzie już powtarzanych bigramów (lub nieużywanych wartości bajtów).

Ktoś może rozpoznać to jako uproszczoną wersję kompresji „sparuj ponownie” (skrót od par rekurencyjnych).

To nie jest bardzo dobry ogólny schemat kompresji. Dobrze sobie radzi tylko z tekstami ASCII, w których występuje wiele nieużywanych wartości bajtów, a nawet wtedy zwykle nie osiąga więcej niż 45-50%. Ma jednak tę zaletę, że można go wdrożyć przy minimum kodu. W szczególności dekompresor może być dość kompaktowy. (Większość znaków w moim skrypcie dekodera służy do wyszukiwania słownika bigram.)

Oto niepoznana wersja kodu:

#!/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, $_;
}

Myślę, że jedno wyrażenie w enkoderze golfowym wymaga wyjaśnienia, to znaczy (sort{$p{$a}<=>$p{$b}}keys%p)[-1]uzyskania klucza o najwyższej wartości. Wygląda na to, że powinien być napisany jako (sort{$p{$b}<=>$p{$a}}keys%p)[0], który robi to samo i jest o jeden znak krótszy. Nie napisałem tego w ten sposób, ponieważ zmienia on wybrany klucz w przypadku, gdy istnieje wiele kluczy o najwyższej wartości. Przez przypadek spowodowało to, że wynikowy wynik dla wejścia testowego był o 10 bajtów dłuższy. Nienawidziłem wybierać bezużytecznej dodatkowej postaci, ale nie dość, by poświęcić 9 punktów z mojego wyniku.

W twoją twarz, Golfscript! (Haha, Golfscript przyszedłby tutaj i skopałby mi tyłek, gdyby mnie usłyszał.)

Python, 3514 = 294 + 2894 + 326

Zasadniczo implementacja bzip2 . To robi Transformata Burrowsa-Wheelera , A move to front , prostego kodowania Huffmana w strumieniu bitowym, zamienia ten strumień bitów do liczby całkowitej i pisze się bajtów.

Enkoder:

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

Sto kolejka przejścia do przodu, Hkoder Huffmana i Nstrumień bitów.

Kodowanie zmniejsza wejściowy test do około 41% jego pierwotnego rozmiaru.

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 Asembler / MS_DOS

Sprężarka: 155

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

Dane: 3506

Dekompresor: 203

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

Razem: 3864

Użyj tego dekodera Base64 i zapisz pliki binarne jako „compress.com” i „decompress.com”, a następnie:

compress < source > compressed_file
decompress < compressed_file > copy_of_source

w powłoce DOS (testowane z WinXP). Nie ma sprawdzania błędów, więc kompresja dużych plików spowoduje nieprawidłowe wyniki. Kilka małych dodatków i może poradzić sobie z plikiem o dowolnym rozmiarze. Ponadto nie może dekompresować do pliku binarnego, ponieważ nie może wyprowadzić wartości 0xff (skompresowane dane uciekają od wartości 0xff jako 0xfe 0xff, a 0xfe ucieka jako 0xfe 0xfe). Użycie nazw plików w wierszu poleceń rozwiązałoby problem z wyjściem binarnym, ale byłby większym plikiem wykonywalnym.

Wiersz uderzeniowy (566 + 117) + 4687 = 5370

Dla zabawy ukryłem kompresor jako wiersz:

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

Jest to zunifikowany kompresor: uruchamiany z opcją „c” spowoduje kompresję, a „d” - dekompresję. Składa się z dwóch części: 566-bajtowej wersji wiersza „podsumowanie czytelników” i (2) 117-bajtowy sufiks, w którym odbywa się całe „prawdziwe” bash.

Z pewną ostrożnością (np. Rozpoczynając wiersz od „for I in”) bash zinterpretuje „stratną” wersję wiersza jako tablicę. Zastępuje każdy element tablicy znakiem innym niż ASCII (zakładamy, że dane wejściowe to ASCII, więc nie ma kolizji). Jedna drobna zaleta tego rozwiązania: ponieważ korzystamy z faktu, że możemy założyć, że dane wejściowe to ASCII, dane wyjściowe tej kompresji nigdy nie będą dłuższe niż dane wejściowe, niezależnie od tego, jaka jest część wejściowa i / lub część stratna.

Reguła, że ​​jest to najbardziej zbliżone do naruszenia, to zasada zapewniania przyzwoitego stopnia kompresji w innych tekstach. Jednak goli 1386 bajtów tekstu GPL V2, znacznie przekraczając swój własny rozmiar, który wydaje się pasować do definicji OP decent. Wydaje się więc, że zapewnia tak zwaną decentkompresję tekstów ogólnych. Wynika to z faktu, że prawie każdy tekst w języku angielskim będzie zawierał „to”, „itd.”. Oczywiście będzie działał lepiej, jeśli zastąpisz część „stratną” tekstem przypominającym oryginał, który chcesz bezstratnie skompresować.

Znane jest dzielenie obrazu i dźwięku na części stratne i bezstratne . Nie działa to tak dobrze w przypadku tekstu: 4687 bajtów nie jest aż tak świetne, nawet jeśli wykluczymy 566 bajtów z wersji stratnej i nie będziemy w stanie automatycznie wygenerować stratnej wersji tekstu tak samo, jak w przypadku dźwięku. Na plus oznacza to, że za każdym razem, gdy kompresujesz coś za pomocą tego kompresora, możesz czerpać przyjemność z ręcznego tworzenia stratnej wersji. Wydaje się to rozsądnym rozwiązaniem „dla zabawy”.

C ++, 4134 bajtów (kod = 1357, skompresowany = 2777)

To robi transformację Burrows-Wheeler + Move-To-Front jak Keith Randall, ale następnie kompresuje wynikową sekwencję bajtów za pomocą adaptacyjnego Coder Range . Niestety poprawiona kompresja z kodera zakresu nie wystarcza, aby zrównoważyć gadatliwość C ++. Mógłbym jeszcze trochę zagrać w ten kod, a mianowicie użyć innej metody wejścia / wyjścia, ale nie wystarczyłoby pokonanie innych zgłoszeń za pomocą bieżącego algorytmu. Kod jest specyficzny dla systemu Windows i obsługiwany jest tylko tekst ascii.
Aby skompresować: „C plik_tekstowy skompresowany_plik”
Aby zdekompresować: „D plik_ skompresowany nieskompresowany_plik”
Prawie każdy błąd wiersza polecenia lub błąd pliku spowoduje awarię programu, a kodowanie lub dekodowanie wiersza zajmuje większą część minuty.

#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 (kod) + 3521 (test) = 3914 (łącznie)

Ten program iteracyjnie zastępuje nieużywane wartości bajtów fragmentami danych wejściowych o długości od 2 do 4 znaków. Każde podstawienie jest oceniane na podstawie częstotliwości i długości oryginalnego fragmentu, a najlepsze zastępowanie jest wybierane za każdym razem. Dodałbym ostatni etap kodowania Huffmana, gdybym mógł wymyślić, jak to zrobić przy stosunkowo małej liczbie znaków. Dekompresja jest zasadniczo serią operacji znajdowania i zastępowania.

Stosowanie

C () zapewnia kompresję; U () zapewnia dekompresję. Ponieważ ciągi JavaScript oparte są na 16-bitowych jednostkach kodu Unicode, tylko najmniej znaczące 8 bitów każdej jednostki kodu jest używanych w formacie skompresowanych danych; jest to zgodne z funkcjami btoa () i atob () Firefoksa dla kodowania Base64. ( przykład użycia )

Ten program może działać tylko w przeglądarce Firefox z powodu niestandardowej opcji „g” dla .replace ().

Kod

Kod do gry w golfa:

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}

Przed golfem:

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

Więc zastosowałem uproszczony słownik + podejście do podstawiania.

Jeśli słowo pojawia się wiele razy i jest krótsze do (zakoduj słowo + zapisz wpis podstawienia), wówczas zastępuje. Jeśli „słowo” zdarza się być liczbą, robi to i tak, aby zapobiec przypadkowym zamianom podczas dekompresji. Do „słownika” podstawień dołączane są bajty puste, po których następują dwa bajty puste, po których następuje treść, na której działa podstawienie.

Możliwe ulepszenia:

• System Windows nie lubi przesyłać więcej niż 4 KB danych, więc znajdź lepszy sposób niż używanie plików.
• Możliwość dopasowywania długich ciągów białych znaków i liczenia ich jako „słów” bez dodawania zbyt dużej ilości kodu.
• Wymyślanie lepszych podstawień zamiast liczb.

Zastosowanie: kompresor szuka pliku o nazwie „i” i zapisuje skompresowane dane w „o”. Dekompresor szuka „o” i zapisuje nieskompresowane dane do „d”. To jest moje tandetne obejście dla systemu Windows, który nie lubi przesyłać danych.

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);

Wersja rozszerzona z komentarzami i objaśnieniami.

Próbka wyjściowa bez słownika. Trochę zabawnie na to patrzeć.
Normalny rozmiar: 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);

Wersja rozszerzona z wyjaśnieniem.

Wszelkie sugestie dotyczące ulepszeń są mile widziane.

Edycja: Dodano „rozwinięte” wersje kodu i mnóstwo ton komentarzy. Powinny być łatwe do naśladowania.

GolfScript, 3647 (rozmiar skompresowany 3408 + rozmiar kodu 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

Zastosowany algorytm to kompresja LZW z kodami o zmiennej szerokości. Pierwszy wiersz to wspólny kod, drugi to kod kompresji, a trzeci to kod dekompresji.

Obsługuje pliki ze znakami ASCII z zakresu 1-127 i automatycznie rozpoznaje skompresowane pliki (zaczynają się od 0 bajtów), więc nie ma parametrów wymaganych do dekompresji.

Przykładowy przebieg:

$ 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  -

Uwaga: zacząłem to na długo przed dodaniem wymogu obsługi 100 kb, więc nie testowałem go na danych wejściowych tego rozmiaru. Jednak kompresja wejścia testowego zajmuje około 30 sekund, a dekompresja - 5 sekund, przy maksymalnym zużyciu około 20 MB pamięci.

Haskell, 3973

Późno na imprezę i nie zamierzam wygrać, ale dobrze się bawiłem, pisząc to, więc równie dobrze mogę to opublikować.

Jest to prosta implementacja LZW o zmiennej szerokości, ze słownikiem wyraźnie ograniczonym do drukowalnego ASCII, tabulatora i linii. Uruchamiany bez argumentów, kompresuje standardowe wejście do pliku C. Uruchom z dowolnym argumentem (ale „--decompress” byłby rozsądnym wyborem), dekompresuje plik Cna standardowe wyjście.

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)

• rozmiar kodu: 578
• rozmiar skompresowanej próbki: 3395