Sobre compresión custom (para A. Villena)

[na_th_an]

O para quien pueda ayudarme. En principio pido ayuda a Antonio porque él es quien mejor maneja de compresiones de los presentes

Verás, el problema es el siguiente:

Tengo una lista medianamente extensa (un centenar, que crecerá) de cadenas. Tienen tamaños entre 10 y 200 bytes y todos los valores son entre 0 y 63 (pueden representarse con 6 bits).

Me gustaría saber qué opciones se te ocurren para comprimir esas cadenas. La mayoría de lo que hay ahí es texto, por lo que tiene cierta repetición, pero también hay otros valores. En un principio no me puedo permitir hacer reordenaciones ni nada por el estilo.

En realidad una compresión al 75% "tonta" podría conseguirse metiendo 4 valores cada 3 bytes (4*6 = 24 bits), pero me gustaría saber si puede conseguirse algo mejor sin requerir un algoritmo de descompresión muy complejo.

[radastan]

¿Has probado con RLE?

http://wiki.speccy.org/cursos/ensamblador/compresion_rle

[na_th_an]

RLE sólo funciona con repetición simple (AAAAAAAAAAAA), y en un texto no hay repetición simple. Necesito algo que use patrones.

[radastan]

Es que con patrones requiere de "diccionario" y eso supone un gasto ganso de memoria.

De todas formas en Brunilda (que tienes el código fuente) hacen uso de compresión de texto, echa un vistazo.

[na_th_an]

Lo ideal sería algo parecido a lo que estáis utilizando para comprimir los mapas, un compresor que permita comprimir el binario completo pero luego descomprimir sólo una parte.

[radastan]

$this->bbcode_second_pass_quote('na_th_an', 'L')o ideal sería algo parecido a lo que estáis utilizando para comprimir los mapas, un compresor que permita comprimir el binario completo pero luego descomprimir sólo una parte.

[na_th_an]

Pero es que no quiero comprimir solo texto

[antoniovillena]

Lo mejor es un LZ77 custom, y basarse en el código ZX7 de Einar Saukas (como hice en el compresor de mapas) es una buena idea. Lo único que hay que optimizar bien es el tamaño de las ventanas, para ello tienes que crearte un set de ejemplos que sean lo más parecido posible a lo que vayas a comprimir en la realidad.

Las ventanas por defecto del ZX7 son de 128/2048. ¿Necesitas que comprima hacia adelante o hacia atrás?

[na_th_an]

Einar, en WOS, me ha quitado un poco las ganas porque me ha contado algo de descomprimir todo en un buffer circular hasta que llegue al cachito que necesito, y además con una ventana enorme, de más de 2Kb

Tengo muy poca RAM libre. Apenas los 200 bytes que tengo para la cadena descomprimida, quizás algo más.

En realidad mis requerimientos no son muy allá. Ahora mismo tengo un índice de direcciones que apuntan al principio de cada cadena, sin comprimir. Lo que hago es buscar la dirección de cadena que quiero en el índice (posición 2*n, vaya) y copio desde ahí a mi buffer hasta encontrar un 0.

En realidad, si fuese capaz de, en vez de copiar un byte, extraer "N bits" de la cadena y expandirlos a un byte, ya tendría mucho ganado. Me monto un pseudo-huffman sencillaco y a tirar. Pero mi kung fu no es lo suficientemente bueno.

Quizá he formulado mal la pregunta: ¿Cómo podría leer de la cadena de 5 en 5 bits, por poner un ejemplo? He hecho experimentos pero, como digo, mi kung fu no es lo suficientemente bueno

[na_th_an]

Lo que quiero decir es que, más que una solución ya hecha, me gustaría un poco de orientación Así aprendo un poco más.