Con la reciente discusión sobre el uso de herramientas de compresión en el golf de código , pensé que sería un buen desafío escribir su propio compresor y descompresor de texto.

Reto:

Escriba dos programas : uno para comprimir el texto ASCII en una secuencia de bytes y otro para descomprimirlo. Los programas no necesitan estar en el mismo idioma.

El primer programa debe leer un fragmento de texto ASCII (de un archivo o de una entrada estándar, o usar cualquier mecanismo que sea más natural para el lenguaje) y generar una versión comprimida del mismo. (La salida comprimida puede consistir en bytes arbitrarios; no necesita ser legible). El segundo programa debería leer la salida del primero y recrear el texto de entrada original.

Tanteo:

El puntaje de una solución será la suma de los siguientes tres recuentos:

1. La longitud del programa del compresor en caracteres.
2. La longitud de la salida del compresor, dada la entrada de prueba a continuación, en bytes.
3. La longitud del programa descompresor (si es diferente del compresor) en caracteres.

Debe tener en cuenta los tres recuentos y su suma en su respuesta. Como se trata de un código de golf, cuanto menor sea el puntaje, mejor.

Reglas y restricciones:

• No puede utilizar ninguna herramienta o biblioteca de compresión o descompresión preexistente, incluso si vienen incluidas con el idioma elegido. Si tiene dudas sobre si una herramienta o función determinada está permitida, pregunte.

• Su programa de compresor debe ser capaz de manejar entradas que consisten en cualquier texto ASCII imprimible , incluidas las pestañas (ASCII 9) y los avances de línea (ASCII 10). Puede, pero no es obligatorio, manejar entradas arbitrarias Unicode y / o binarias.

• Su programa de descompresor debe producir exactamente la misma salida que se le dio al compresor como entrada. En particular, tenga cuidado de no generar un avance de línea final si la entrada no tiene uno. (La entrada de prueba a continuación tiene un avance de línea final, por lo que deberá probar esto por separado. Sugerencia para GolfScript:. '':n)

• Su compresor y descompresor pueden ser el mismo programa (con el modo apropiado seleccionado, por ejemplo, con un interruptor de línea de comando). En ese caso, su longitud solo se cuenta una vez .

• Los programas no deben ser excesivamente lentos ni hambrientos de memoria . Si comprimir o descomprimir la entrada de prueba tarda más de un minuto en mi escritorio no tan nuevo (2.2GHz AMD Athlon64 X2) o consume más de un gigabyte de RAM, descartaré la solución como inválida. Estos límites son deliberadamente laxos; intente no forzarlos. (Consulte la enmienda a continuación: debe poder manejar al menos 100 kB de entrada dentro de estos límites).

• Aunque solo la entrada de prueba es importante para la puntuación, al menos debe hacer un esfuerzo para comprimir texto de entrada arbitrario. Una solución que logra una relación de compresión decente solo para la entrada de prueba, y para nada más, es técnicamente válida pero no va a obtener un voto positivo de mi parte.

• Sus programas de compresor y descompresor deben ser independientes . En particular, si dependen de poder leer algún archivo o recurso de red que no es parte del entorno de tiempo de ejecución estándar de su idioma elegido, la longitud de ese archivo o recurso debe contarse como parte de la longitud de los programas. (Esto es para no permitir "compresores" que comparan la entrada a un archivo en la web y generan cero bytes si coinciden. Lo siento, pero eso ya no es un truco nuevo).

Enmiendas y aclaraciones:

• Su compresor debe poder manejar archivos que contengan al menos 100 kB de texto típico en inglés dentro de un tiempo razonable y uso de memoria (como máximo un minuto y un GB de memoria). Su descompresor debe poder descomprimir la salida resultante dentro de los mismos límites. Por supuesto, ser capaz de manejar archivos por más tiempo es perfectamente correcto y recomendable. Está bien dividir archivos de entrada largos en fragmentos y comprimirlos individualmente, o utilizar otros medios para cambiar la eficiencia de compresión por la velocidad de las entradas largas.

• Su compresor puede requerir su entrada a darse usando de su plataforma preferida representación nativa salto de línea (LF, CR + LF, CR, etc.), siempre y cuando su descompresor utiliza la misma representación nueva línea en su salida. Por supuesto, también está bien que el compresor acepte cualquier tipo de líneas nuevas (o incluso solo líneas nuevas de Unix, independientemente de la plataforma), siempre que su descompresor emita el mismo tipo de líneas nuevas que en la entrada original.

Prueba de entrada:

Para juzgar la eficiencia de compresión de las respuestas, se utilizará la siguiente entrada de prueba ( The Raven por Edgar Allan Poe, cortesía del Proyecto 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!

La entrada de prueba correcta (codificada con líneas nuevas LF de estilo Unix) debe tener 7043 bytes de longitud y tener el hash MD5 hexadecimal 286206abbb7eca7b1ab69ea4b81da227. ( md5sum -tdebería producir el mismo valor hash incluso si usa líneas nuevas CR + LF en DOS / Windows). La salida de su descompresor debe tener la misma longitud y hash.

PD. Tenga en cuenta que este desafío es tan difícil como lo hace. Realmente, cualquier cosa por debajo de 7043 cuenta como una buena puntuación. (En el otro extremo de la escala, estaré extremadamente impresionado si alguien logra un puntaje inferior a 2500).

Perl, 3502 = 133 + 3269 + 100

El codificador:

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

Y el decodificador:

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

Para los puristas que prefieren evitar el uso de interruptores de línea de comandos: puede eliminar la línea shebang y agregarla $/=chr;al codificador y $/=$,;al decodificador para obtener el mismo efecto. (Esto elevaría el puntaje hasta 3510).

Este código usa un esquema de compresión muy primitivo:

• Encuentra el bigram de dos caracteres que aparece con más frecuencia en el texto fuente.
• Reemplace el bigram con un valor de byte no utilizado actualmente.
• Repita hasta que no haya más bigrams repetidos (o no más valores de bytes no utilizados).

Alguien por ahí puede reconocer esto como una versión simplificada de la compresión "volver a emparejar" (abreviatura de pares recursivos).

No es un muy buen esquema de compresión general. Solo funciona bien con cosas como el texto ASCII, donde hay una gran cantidad de valores de bytes no utilizados, e incluso entonces generalmente no obtiene más de una relación de 45-50%. Sin embargo, tiene la ventaja de ser implementable con un mínimo de código. El descompresor en particular puede ser bastante compacto. (La mayoría de los caracteres en mi script de decodificador son para recuperar el diccionario bigram).

Aquí hay una versión no codificada del código:

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

Una expresión en el codificador de golf requiere explicación, creo, y es (sort{$p{$a}<=>$p{$b}}keys%p)[-1]obtener la clave con el valor más alto. Parece que debería escribirse como (sort{$p{$b}<=>$p{$a}}keys%p)[0], que hace lo mismo y tiene un carácter más corto. La razón por la que no lo escribí de esa manera es porque altera la clave seleccionada en el caso de que haya varias claves con el valor más alto. Por pura casualidad, esto provocó que la salida resultante para la entrada de prueba fuera 10 bytes más larga. Odiaba asumir el carácter extra inútil, pero no lo suficiente como para sacrificar 9 puntos de mi puntaje.

En tu cara, Golfscript! (Jaja, Golfscript vendría totalmente aquí y me patearía el trasero si pudiera escucharme).

Python, 3514 = 294 + 2894 + 326

Básicamente una implementación de bzip2 . Realiza una transformación Burrows-Wheeler , una transformación de movimiento al frente , una simple codificación Huffman en una secuencia de bits, convierte esa secuencia de bits en un entero y escribe bytes.

Codificador:

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

Ses la cola de avance al frente, Hes el codificador Huffman y Nes el flujo de bits.

La codificación reduce la entrada de prueba a aproximadamente el 41% de su tamaño original.

Descifrador:

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

Ensamblador 8086 / MS_DOS

Compresor: 155

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

Datos: 3506

Descompresor: 203

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

Total: 3864

Use este decodificador Base64 y guarde los archivos binarios como 'compress.com' y 'decompress.com' y luego haga lo siguiente:

compress < source > compressed_file
decompress < compressed_file > copy_of_source

en un shell de DOS (probado con WinXP). No hay verificación de errores, por lo que comprimir archivos grandes creará resultados incorrectos. Algunas pequeñas adiciones y podría hacer frente a archivos de cualquier tamaño. Además, no puede descomprimirse en binario ya que no puede generar un valor 0xff (los datos comprimidos escapan del valor 0xff como 0xfe 0xff con 0xfe escapado como 0xfe 0xfe). El uso de nombres de archivo de línea de comando superaría el problema de salida binaria, pero sería un ejecutable más grande.

Bash Poema (566 + 117) + 4687 = 5370

Por diversión, he disfrazado un compresor como un poema:

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

Este es un compresor unificado: ejecute con la opción "c" se comprimirá y con "d" se descomprimirá. Tiene dos partes: una versión del poema de "resumen de lectores" de 566 bytes y (2) un sufijo de 117 bytes donde se realiza todo el golpe "real".

Con un poco de cuidado (por ejemplo, comenzar el poema con "for I in") bash interpretará la versión "con pérdida" del poema como una matriz. Reemplaza cada elemento de la matriz con un carácter no ASCII (suponemos que la entrada es ASCII, por lo que no hay colisiones). Una ventaja menor de esta solución: dado que utilizamos el hecho de que podemos asumir que la entrada es ASCII, la salida de esta compresión nunca será más larga que su entrada, independientemente de cuál sea la entrada y / o la parte con pérdida.

La regla que más se acerca a la violación es la regla sobre proporcionar una relación de compresión decente en otros textos. Sin embargo, elimina 1386 bytes del texto GPL V2, muy por encima de su propio tamaño, que parece coincidir con la definición de OP de decent. Por lo tanto, parece proporcionar la denominada decentcompresión en textos generales. Esto se debe a que casi cualquier texto en inglés tendrá "el" "eso", etc. Claramente funcionará mejor si reemplaza la parte "con pérdida" por un texto similar al original que desea comprimir sin pérdida.

La división de imágenes y audio en partes con pérdida y sin pérdida es una técnica conocida. Esto no funciona tan bien para el texto: 4687 bytes no es tan bueno incluso si excluimos los 566 bytes de la versión con pérdida y realmente no podemos generar automáticamente una versión con pérdida del mismo texto que para el audio. En el lado positivo, esto significa que cada vez que comprime algo con este compresor, puede divertirse creando una versión con pérdida a mano. Así que esto parece una solución razonable "por diversión".

C ++, 4134 bytes (código = 1357, comprimido = 2777)

Esto hace una transformación de Burrows-Wheeler + un movimiento al frente como el de Keith Randall, pero luego comprime la secuencia de bytes resultante usando un codificador de rango adaptativo . Desafortunadamente, la compresión mejorada del codificador de rango no es suficiente para compensar la verbosidad de C ++. Podría desarrollar este código un poco más, es decir, usar un método de entrada / salida diferente, pero no sería suficiente para vencer a las otras presentaciones con el algoritmo actual. El código es específico de Windows y solo se admite texto ascii.
Para comprimir: "Archivo de texto C archivo comprimido"
Para descomprimir: " Archivo D comprimido
archivo descomprimido" Casi cualquier error de línea de comando o error de archivo bloqueará el programa, y ​​lleva la mayor parte de un minuto codificar o decodificar el poema.

#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 (código) + 3521 (prueba) = 3914 (total)

Este programa sustituye iterativamente valores de bytes no utilizados por fragmentos de 2 a 4 caracteres de la entrada. Cada sustitución se puntúa en función de la frecuencia y la longitud del fragmento original, y la mejor sustitución se elige cada vez. Agregaría una etapa final de codificación de Huffman si pudiera descubrir cómo hacerlo en un número relativamente pequeño de caracteres. La descompresión es esencialmente una serie de operaciones de buscar y reemplazar.

Uso

C () proporciona compresión; U () proporciona descompresión. Como las cadenas de JavaScript se basan en unidades de código Unicode de 16 bits, solo se utilizan los 8 bits menos significativos de cada unidad de código en el formato de datos comprimido; Esto es compatible con las funciones btoa () y atob () de Firefox para la codificación Base64. ( ejemplo de uso )

Este programa solo puede funcionar en Firefox debido a una opción "g" no estándar para .replace ().

Código

Código 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}

Antes de jugar al 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

Así que fui con un enfoque simplista de diccionario + sustitución.

Si una palabra aparece varias veces y es más corta (codificar la palabra + guardar la entrada de sustitución), entonces se hace el reemplazo. Si la "palabra" es un número, de todos modos lo hace para evitar sustituciones accidentales durante la descompresión. El "diccionario" de sustituciones está unido por bytes nulos, seguido de dos bytes nulos, seguidos por el cuerpo en el que trabaja la sustitución.

Posibles mejoras:

• A Windows no le gusta canalizar más de 4kb de datos, así que encuentre una mejor manera que usar archivos.
• La capacidad de unir cadenas largas de espacios en blanco y contarlas como "palabras" sin agregar demasiado código.
• Proponer sustituciones algo mejores en lugar de usar números.

Uso: el compresor busca un archivo llamado "i" y escribe los datos comprimidos en "o". El descompresor busca "o" y escribe los datos sin comprimir en "d". Esta es mi solución de mala calidad para Windows que no le gusta canalizar los botes de datos.

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ón ampliada con comentarios y explicación.

Muestra de salida sin diccionario. Un poco gracioso de ver.
Tamaño 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ón ampliada con explicación.

Cualquier sugerencia de mejora bienvenida.

Editar: se agregaron las versiones "desenrolladas" del código y se agregaron toneladas de comentarios. Debería ser fácil de seguir.

GolfScript, 3647 (tamaño comprimido 3408 + tamaño de código 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

El algoritmo utilizado es la compresión LZW con códigos de ancho variable. La primera línea es código compartido, la segunda es el código de compresión y la tercera es el código de descompresión.

Maneja archivos con caracteres ASCII en el rango 1-127, y reconoce archivos comprimidos automáticamente (comienzan con un byte 0), por lo que no se requieren parámetros para descomprimir.

Ejemplo de ejecución:

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

Nota: Comencé en esto mucho antes de que se añadiera el requisito de manejar 100 kb, por lo que no lo he probado en entradas de ese tamaño. Sin embargo, lleva unos 30 segundos comprimir la entrada de prueba y 5 segundos descomprimirla, utilizando aproximadamente 20 MB de memoria en su punto máximo.

Haskell, 3973

Llego tarde a la fiesta y no voy a ganar, pero me divertí escribiéndolo, así que podría publicarlo.

Es una implementación sencilla de ancho variable de LZW, con un diccionario explícitamente limitado a ASCII imprimible, tabulación y salto de línea. Ejecutar sin argumentos, comprime la entrada estándar al archivo C. Ejecutar con cualquier argumento (pero "--decompress" sería una apuesta razonable), descomprime el archivo Ca la salida estándar.

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)

• tamaño del código: 578
• tamaño de muestra comprimido: 3395