Avec la récente discussion sur l'utilisation des outils de compression dans le code de golf , j'ai pensé que ce serait un beau défi d'écrire votre propre compresseur et décompresseur de texte.

Défi:

Ecrivez deux programmes : l’un pour compresser le texte ASCII en une suite d’octets et l’autre pour le décompresser. Les programmes ne doivent pas nécessairement être dans la même langue.

Le premier programme doit lire un morceau de texte ASCII (à partir d'un fichier ou d'une entrée standard, ou utiliser le mécanisme le plus naturel du langage) et en générer une version compressée. (La sortie compressée peut être constituée d'octets arbitraires; elle n'a pas besoin d'être lisible.) Le deuxième programme doit lire la sortie du premier et recréer le texte d'entrée d'origine.

Notation:

Le score d'une solution sera la somme des trois comptes suivants:

1. La longueur du programme de compression en caractères.
2. La longueur de la sortie du compresseur, étant donné l'entrée de test ci - dessous, en octets.
3. La longueur du programme du décompresseur (si différent du compresseur) en caractères.

Vous devriez noter les trois chefs d'accusation et leur somme dans votre réponse. Puisqu'il s'agit d'un code de golf, plus le score est bas, mieux c'est.

Règles et restrictions:

• Vous n'êtes pas autorisé à utiliser des outils ou des bibliothèques de compression ou de décompression préexistants, même s'ils sont fournis avec le langage choisi. En cas de doute sur l’utilisation d’un outil ou d’une fonction donnée, veuillez demander.

• Votre programme de compresseur doit être capable de gérer une entrée composée de tout texte ASCII imprimable , y compris des onglets (ASCII 9) et des sauts de ligne (ASCII 10). Vous pouvez, sans y être obligé, gérer des entrées Unicode et / ou binaires arbitraires.

• Votre programme de décompresseur doit produire exactement la même sortie que celle fournie au compresseur. En particulier, veillez à ne pas générer de saut de ligne de fin si l’entrée n’en avait pas. (L'entrée de test ci-dessous a un saut de ligne final, vous devrez donc le tester séparément. Astuce pour GolfScript:. '':n)

• Votre compresseur et votre décompresseur peuvent être le même programme (avec le mode approprié sélectionné, par exemple avec un commutateur de ligne de commande). Dans ce cas, sa longueur n'est comptée qu'une fois .

• Les programmes ne doivent pas être excessivement lents ou gourmands en mémoire . Si la compression ou la décompression de l'entrée de test prend plus d'une minute sur mon tout nouveau bureau (AMD Athlon64 X2 à 2,2 GHz) ou consomme plus d'un gigaoctet de RAM, je vais déclarer la solution invalide. Ces limites sont délibérément laxistes - essayez de ne pas les pousser. (Voir amendement ci-dessous: vous devez être en mesure de gérer au moins 100 ko d'entrées dans ces limites.)

• Même si seule l'entrée de test est importante pour la notation, vous devez au moins essayer de compresser du texte d'entrée arbitraire. Une solution qui n'atteint un taux de compression décent que pour l'entrée de test, et pour rien d'autre, est techniquement valable, mais ne suscitera pas un vote positif de ma part.

• Les programmes de votre compresseur et de votre décompresseur doivent être autonomes . En particulier, s'ils dépendent de la capacité de lire un fichier ou une ressource réseau qui ne fait pas partie de l'environnement d'exécution standard de la langue de votre choix, la longueur de ce fichier ou de cette ressource doit être comptée dans la longueur du ou des programmes. (Ceci est destiné à interdire les "compresseurs" qui comparent l'entrée à un fichier sur le Web et produisent zéro octet s'ils correspondent. Désolé, mais ce n'est plus une astuce.)

Amendements et clarifications:

• Votre compresseur doit être en mesure de gérer des fichiers contenant au moins 100 Ko de texte anglais typique dans des délais raisonnables et avec une utilisation de la mémoire suffisante (au plus une minute et un Go de mémoire). Votre décompresseur doit pouvoir décompresser le résultat obtenu dans les mêmes limites. Bien sûr, être capable de gérer des fichiers plus longs que cela est tout à fait correct et louable. Vous pouvez diviser de longs fichiers d'entrée en morceaux et les compresser individuellement, ou utiliser d'autres moyens pour compenser l'efficacité de la compression par la vitesse pour des entrées longues.

• Votre compresseur peut nécessiter que son entrée soit donnée à l'aide de la représentation de nouvelle ligne native de votre plate-forme (LF, CR + LF, CR, etc.), à condition que votre décompresseur utilise la même représentation de nouvelle ligne dans sa sortie. Bien entendu, le compresseur accepte également tout type de saut de ligne (ou même uniquement les sauts de ligne Unix, quelle que soit la plate-forme), à ​​condition que votre décompresseur génère ensuite le même type de saut de ligne que dans l'entrée d'origine.

Test d'entrée:

Pour juger de l'efficacité de la compression des réponses, on utilisera l' entrée de test suivante ( The Raven d'Edgar Allan Poe, gracieuseté de 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!

L'entrée de test correcte (codée avec des retours à la ligne LF de style Unix) doit comporter 7043 octets de long et comporter le hachage MD5 hexadécimal 286206abbb7eca7b1ab69ea4b81da227. ( md5sum -tdevrait produire la même valeur de hachage même si vous utilisez des nouvelles lignes CR + LF sous DOS / Windows.) La sortie de votre décompresseur doit avoir la même longueur et la même valeur de hachage.

Ps. Gardez à l'esprit que ce défi est aussi difficile que vous le faites. Vraiment, rien de moins que 7043 compte comme un bon score. (À l'autre bout de l'échelle, je serai extrêmement impressionné si quelqu'un obtient un score inférieur à 2500.)

Perl, 3502 = 133 + 3269 + 100

Le codeur:

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

Et le décodeur:

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

Pour les puristes qui préfèrent ne pas utiliser les commutateurs de ligne de commande: Vous pouvez supprimer la ligne shebang et l'ajouter $/=chr;au codeur et $/=$,;au décodeur pour obtenir le même effet. (Cela porterait le score à 3510.)

Ce code utilise un schéma de compression très primitif:

• Trouvez le bigramme à deux caractères qui apparaît le plus souvent dans le texte source.
• Remplacez bigram par une valeur d'octet actuellement non utilisée.
• Répétez jusqu'à ce qu'il n'y ait plus de bigrammes répétés (ou plus de valeurs d'octets non utilisées).

Quelqu'un peut reconnaître cela comme une version simplifiée de la compression "re-pair" (abréviation de paires récursives).

Ce n'est pas un très bon schéma de compression général. Cela ne fonctionne bien qu'avec des choses comme le texte ASCII, où il y a beaucoup de valeurs d'octets inutilisées, et même dans ce cas, le rapport n'est généralement pas supérieur à 45-50%. Cependant, il a l’avantage d’être implémenté avec un minimum de code. Le décompresseur en particulier peut être assez compact. (La plupart des caractères de mon script de décodeur servent à récupérer le dictionnaire bigram.)

Voici une version non codée du code:

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

Une expression dans le codeur de golf nécessite une explication, à savoir (sort{$p{$a}<=>$p{$b}}keys%p)[-1], pour obtenir la clé avec la valeur la plus élevée. Cela ressemble à cela devrait être écrit comme (sort{$p{$b}<=>$p{$a}}keys%p)[0], ce qui fait la même chose et est un caractère plus court. La raison pour laquelle je ne l'ai pas écrit de cette façon est que cela modifie la clé sélectionnée dans le cas où il y a plusieurs clés avec la valeur la plus élevée. Par pure chance, la sortie résultante pour l'entrée de test a été allongée de 10 octets. Je détestais prendre le caractère supplémentaire inutile, mais pas assez pour sacrifier 9 points de mon score.

Face à vous, Golfscript! (Haha, Golfscript viendrait totalement ici et me botterait le cul s'il pouvait m'entendre.)

Python, 3514 = 294 + 2894 + 326

Fondamentalement, une implémentation bzip2 . Il effectue une transformation Burrows-Wheeler , une transformation avant-gardiste , un simple encodage Huffman. en un flux binaire, convertit ce flux en un entier et écrit des octets.

Codeur:

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

Sest la file d'attente avec déplacement, Hest le codeur de Huffman, etN le train de bits.

L'encodage réduit l'entrée de test à environ 41% de sa taille d'origine.

Décodeur:

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

Compresseur: 155

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

Données: 3506

Décompresseur: 203

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

Total: 3864

Utilisez ce décodeur Base64 et enregistrez les fichiers binaires sous «compress.com» et «decompress.com», puis procédez comme suit:

compress < source > compressed_file
decompress < compressed_file > copy_of_source

dans un shell DOS (testé avec WinXP). Il n'y a pas d'erreur de vérification et la compression de gros fichiers créera des résultats incorrects. Quelques petits ajouts et il pourrait faire face à n'importe quel fichier de taille. En outre, il ne peut pas décompresser en binaire car il ne peut pas générer de valeur 0xff (les données compressées échappent à la valeur 0xff en tant que 0xfe 0xff, 0xfe étant échappé en tant que 0xfe 0xfe). L'utilisation de noms de fichiers en ligne de commande résoudrait le problème de la sortie binaire, mais constituerait un exécutable plus volumineux.

Poème Bash (566 + 117) + 4687 = 5370

Pour le plaisir, j'ai déguisé un compresseur en poème:

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

Il s’agit d’un compresseur unifié: exécuté avec l’option "c", il sera compressé et avec "d", il sera décompressé. Il comporte deux parties: une version de 566 octets du lecteur "digère" du poème et (2) un suffixe de 117 octets où toutes les "vraies" bashs sont effectuées.

Avec un peu de soin (par exemple, en commençant le poème avec "for I in"), bash interprétera la version "avec perte" du poème comme un tableau. Il remplace chaque élément du tableau par un caractère non-ASCII (nous supposons que l'entrée est ASCII, il n'y a donc pas de collision). Un avantage mineur de cette solution: puisque nous utilisons le fait que nous pouvons supposer que l’entrée est ASCII, la sortie de cette compression ne sera jamais plus longue que son entrée, quelle que soit la partie entrée et / ou avec perte.

La règle la plus proche de la violation est la règle de fournir un taux de compression décent sur d'autres textes. Cependant, il supprime 1386 octets du texte GPL V2, bien au-dessus de sa propre taille, ce qui semble correspondre à la définition des OP decent. Ainsi, il semble fournir une decentcompression dite sur des textes généraux. En effet, à peu près tout texte anglais aura "le" "que", etc. Cela fonctionnera mieux si vous remplacez la partie "avec perte" par un texte ressemblant à l'original que vous souhaitez compresser sans perte.

Fractionner des images et du son en parties avec et sans perte est une technique connue. Cela ne fonctionne pas aussi bien pour le texte: 4687 octets n’est pas très bon, même si nous excluons les 566 octets de la version avec pertes et que nous ne pouvons pas générer automatiquement une version avec pertes de texte identique à celle utilisée pour l’audio. Cela signifie que chaque fois que vous compressez quelque chose avec ce compresseur, vous pouvez vous amuser à créer une version avec pertes à la main. Cela semble donc être une solution raisonnable "pour le plaisir".

C ++, 4134 octets (code = 1357, compressé = 2777)

Ceci effectue une transformation Burrows-Wheeler + un déplacement vers l'avant comme celui de Keith Randall, mais compresse ensuite la séquence d'octets résultante à l'aide d'un codeur de plage adaptatif . Malheureusement, l'amélioration de la compression du codeur de plage ne suffit pas à compenser la verbosité de C ++. Je pourrais jouer un peu plus à ce code, à savoir utiliser une méthode d'entrée / sortie différente, mais cela ne serait pas suffisant pour battre les autres soumissions avec l'algorithme actuel. Le code est spécifique à Windows et seul le texte ASCII est pris en charge.
Pour compresser: "C text_file comprimé_file"
Pour décompresser: "D compressé-
fichier uncompressed_file" La plupart des erreurs de ligne de commande ou de fichier font planter le programme et il faut environ une minute pour coder ou décoder le poème.

#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 (code) + 3521 (test) = 3914 (total)

Ce programme substitue de manière itérative les valeurs d'octet non utilisées par des morceaux de 2 à 4 caractères de l'entrée. Chaque substitution est notée en fonction de la fréquence et de la longueur du bloc d'origine, et la meilleure substitution est choisie à chaque fois. J'ajouterais une dernière étape de codage de Huffman si je pouvais comprendre comment le faire en un nombre relativement petit de caractères. La décompression est essentiellement une série d'opérations de recherche et de remplacement.

Usage

C () fournit la compression; U () fournit une décompression. Comme les chaînes de JavaScript sont basées sur des unités de code Unicode 16 bits, seuls les 8 bits les moins significatifs de chaque unité de code sont utilisés dans le format de données compressé. Ceci est compatible avec les fonctions btoa () et atob () de Firefox pour le codage Base64. ( exemple d'utilisation )

Ce programme ne peut fonctionner dans Firefox qu'à cause d'une option "g" non standard de .replace ().

Code

Code de 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}

Avant de jouer au 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

Je suis donc allé avec un dictionnaire simpliste + approche de substitution.

Si un mot apparaît plusieurs fois et qu'il est plus court (coder le mot + enregistrer l'entrée de substitution), le remplacement est effectué. Si le "mot" se trouve être un nombre, il le fait de toute façon pour empêcher les substitutions accidentelles pendant la décompression. Le "dictionnaire" des substitutions est joint par des octets nuls, suivis de deux octets nuls, suivis du corps sur lequel la substitution fonctionne.

Améliorations possibles:

• Windows n'aime pas transmettre plus de 4 ko de données, alors trouvez un meilleur moyen que d'utiliser des fichiers.
• La possibilité de faire correspondre de longues chaînes d'espaces et de les compter comme des "mots" sans ajouter trop de code.
• Venir avec quelque chose de meilleur substitutions au lieu d'utiliser des chiffres.

Utilisation: le compresseur recherche un fichier appelé "i" et écrit les données compressées dans "o". Le décompresseur recherche "o" et écrit les données non compressées dans "d". C’est la solution que je préconise pour éviter que Windows n’apprécie la navigation dans les bateaux de données.

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

Version développée avec commentaires et explications.

Exemple de sortie sans dictionnaire. Un peu drôle à regarder.
Taille normale: 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);

Version développée avec explication.

Toute suggestion d'amélioration est la bienvenue.

Edit: Ajout des versions "déroulées" du code et ajout de tonnes de commentaires. Devrait être facile à suivre.

GolfScript, 3647 (taille compressée 3408 + taille de code 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

L'algorithme utilisé est la compression LZW avec des codes à largeur variable. La première ligne est un code partagé, la seconde est le code de compression et la troisième est le code de décompression.

Il gère les fichiers contenant des caractères ASCII compris entre 1 et 127 et reconnaît les fichiers compressés automatiquement (ils commencent par un octet 0). Aucun paramètre n'est donc nécessaire pour la décompression.

Exemple d'exécution:

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

Remarque: j'ai commencé longtemps avant que l'exigence de gérer 100 Ko ne soit ajoutée. Je ne l'ai donc pas testée avec une entrée de cette taille. Cependant, il faut environ 30 secondes pour compresser l’entrée de test et 5 secondes pour la décompresser, en utilisant environ 20 Mo de mémoire à son maximum.

Haskell, 3973

En retard à la fête, et ne va pas gagner, mais je me suis amusé à l'écrire alors je pourrais aussi bien le poster.

C'est une implémentation directe de LZW, à largeur variable, avec un dictionnaire explicitement limité à l'ASCII imprimable, à la tabulation et au saut de ligne. Exécuté sans argument, il compresse l’entrée standard dans un fichier C. Exécuté avec n'importe quel argument (mais "--decompress" serait un pari raisonnable), il décompresse le fichier Cen sortie standard.

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)

• taille du code: 578
• taille de l'échantillon comprimé: 3395