Conversión de base (CJam)
Una manera fácil de codificar cadenas ASCII que no comienzan con un byte nulo es convertir de base 128 a entero, luego a base 256:
128b256b:c e# Prints encoded string.
128b256b:c`"256b128b:c" e# Prints encoded string with decoder.
Esto usa 7 bits para codificar cada carácter ASCII.
Si la cadena original consta solo de, por ejemplo, letras minúsculas, y no comienza con una a , podemos comenzar por asignar "a...z"
a [0 ... 25]
, luego proceder como se indica arriba:
'afm26b256b:c e# Prints encoded string.
'afm26b256b:c`"256b26b'af+" e# Prints encoded string with decoder.
Finalmente, si la cadena original tiene solo unos pocos caracteres únicos (comunes en el arte ASCII), generalmente es mejor especificar el alfabeto explícitamente.
Por ejemplo:
" +-/\|"f#6b256b:c e# Prints encoded string.
" +-/\|"f#6b256b:c`"256b6b"" +-/\|"`"f=" e# Prints encoded string with decoder.
Como regla general, desea que el primer carácter de la cadena original sea el segundo carácter del alfabeto, el siguiente carácter distinto de la cadena original sea el primer carácter del alfabeto, el siguiente carácter distinto de la cadena original para ser el tercer caracter del alfabeto, el siguiente caracter distintivo de la cadena original para ser el cuarto caracter del alfabeto, etc.
El codificador del último ejemplo funciona de la siguiente manera:
" +-/\|"f# e# Replace each character by its index in that string.
6b256b e# Convert from base 6 (length of the alphabet) to base 256.
:c e# Cast each digit to character.
El decodificador del último ejemplo funciona de la siguiente manera:
256b6b e# Convert from base 256 to base 6.
" +-/\|"f= e# Replace each digit by the corresponding character of the alphabet.
Las preguntas más grandes de complejidad de Kolmogorov con cierta estructura pero sin una fórmula simple (por ejemplo, letras de canciones) generalmente se beneficiarán de un enfoque basado en la gramática. En esencia, extrae subcadenas repetidas y las codifica de alguna manera. Esto es lo que hace Lempel-Ziv, utilizando una clase de gramáticas bastante restringida; Si usa gramáticas más generales, entonces tiene que descubrir cómo codificar las reglas. Por ejemplo, uno de los enfoques aquí es "codificación de desplazamiento", donde cada byte a compensar fuente por el número de reglas (
n
), bytes asignar1
an
las reglas, utilizar el0
byte de reglas separadas, y en repetidas ocasiones sustituyen a bytei
con la regla evaluadoi
. Finalmente deshaces el desplazamiento restandon
de cada byte.De hecho, he escrito un programa Java que implementa varios enfoques:
También incluye un enfoque Lempel-Ziv, un enfoque de codificación base y un enfoque de codificación de longitud de ejecución, e identifica el que proporciona el programa más corto.
fuente
Stax
En el lenguaje de golf de código Stax , hay una pequeña herramienta útil llamada compresor literal de cadenas . No sé exactamente cómo funciona, pero hay otro en el que sí sé cómo funciona. Convierte cadenas en números, luego en Base 256. Es CP437 , con 0x00 y 0xFF convertidos para copiar. Es PackedStax. Puede convertir sus cadenas con el compresor literal de cadenas y luego empacarlo, para una buena compresión.
Usando este proceso, la cadena "Esta cadena es de treinta y dos bytes" se puede convertir a v * "A] - | W4]} 3"% (la cadena comprimida generalmente está rodeada por puntos de retroceso para indicar la diferencia entre una cadena normal en Stax ) y finalmente a üvìë! [┴╩qJu ← ▓α para una compresión / reducción de 18 bytes, más de la mitad.
fuente