Este artículo puede ser de interés para aquellos que se dedican a la compresión de datos o desean escribir su propio archivador.
El artículo está escrito principalmente sobre los materiales del
blog , que es mantenido por Fabian Giesen.
Introduccion
El método de codificación de entropía rANS (
r ange + ANS) es el hermano del algoritmo FSE, sobre el que
escribí anteriormente . La abreviatura ANS significa
Sistemas de números asimétricos , y el rango de palabras en el nombre sugiere la similitud de este método con la
codificación por intervalos . El autor de rANS es
Yarek Duda .
El método rANS le permite lograr una compresión casi óptima a una velocidad muy alta. En este rANS no es peor que FSE, lo cual no es sorprendente: ambos algoritmos se basan en una base teórica común. Sin embargo, el algoritmo rANS es mucho más simple de implementar que FSE.
Primero, habrá una larga parte "teórica", y luego intentaremos escribir un archivador simple.
Descripción del método
El funcionamiento del algoritmo está determinado por las siguientes fórmulas simples:
Codificación: C(s,x): x := (x / Fs) * M + Bs + (x % Fs)Decodificación: D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - BsAnalicemos en detalle.
La función de codificación
C (s, x) recibe los caracteres
s a codificar (que sea un número entero) y el estado actual del codificador
x (también un número entero).
F s - frecuencia de símbolo
s . La división por Fs anterior es entera.
M es la suma de las frecuencias de todos los símbolos del alfabeto (
M = Σ
F s ).
En s , el comienzo del intervalo correspondiente al carácter codificado (en la figura siguiente).
x %
Fs es el resto de dividir
x por
F s .
El principio de operación es el mismo que en la
codificación aritmética : tomamos el segmento
[ 0,
M) y lo dividimos en partes para que cada carácter
s corresponda a un intervalo de tamaño igual a la frecuencia del carácter
F s . La aparición del valor
x% M en cualquier intervalo denota la codificación del símbolo correspondiente.
Al comienzo de la codificación, inicialice
x con un valor arbitrario adecuado y luego calcule la función
C (s, x) para todos los caracteres codificados en secuencia.
Cada cálculo de la función
C (s, x) aumenta el valor de
x . Cuando se vuelve demasiado grande, debe volcar los datos en la salida:
while (x >= x_max) { writeToStream(x % b);
Este paso se llama
renormalización . Después de eso, puede continuar codificando.
Arriba en el código, aparecieron nuevas constantes:
x_max y
b . En teoría, los números
M ,
b y
x_max están relacionados por algunas relaciones, pero en la práctica es más efectivo usar los siguientes valores si el estado uint32 se usa para el estado
x :
M = 2 ^
k , donde
k <= 16
b = 2 ^ 16 (la mitad del tamaño de uint32)
La elección de
M = 2 ^
k se debe al hecho de que hay una división por
M en la función de decodificación, por lo que la división con el resto se puede reemplazar con operaciones bit a bit.
El valor de
k se selecciona de las siguientes consideraciones: cuanto mayor es, mayor es la precisión de
Fs y más eficiente es la compresión. En este caso, se deben tener en cuenta algunos gastos generales para almacenar la tabla de frecuencias, por lo que no siempre vale la pena utilizar los valores máximos de
k .
El valor de
x_max debe ser tal que no se produzca un desbordamiento. Según la función de codificación, obtenemos que
x <
uint32_max *
Fs /
M o de una manera ligeramente diferente:
x_max <= (
b *
L ) *
Fs /
M , donde
L <=
uint32_max /
b . En código real, la condición toma la forma x / b> = L / M * Fs para evitar el desbordamiento en los cálculos.
El valor
b = 2 ^ 16 (la mitad del tamaño de uint32) se elige de tal manera que si
x excede
x_max , entonces una división por
b es suficiente para continuar trabajando. Como resultado, el
while finalizará después de la primera iteración, lo que significa que se puede reemplazar con un simple
if .
Como resultado, la función de codificación toma la siguiente forma:
typedef uint32_t RansState; constexpr uint32_t RANS_L = 1u << 16; constexpr uint32_t k = 10;
Al final de la codificación, debe guardar el valor de
x , ya que la decodificación comenzará desde allí. Y sí, decodificaremos desde el final hasta el principio, es decir, desde el último carácter codificado hasta el primero. (El artículo sobre
FSE explica este punto con suficiente detalle).
Quiero detenerme un poco más sobre cómo funciona la fórmula de codificación.
x := (x / Fs) * M + Bs + (x % Fs)
Después de calcular (
x / Fs) * M , la variable
x contiene los
k bits menos significativos (recuerde que
M = 2 ^
k ). Agregar
+ Bs + (x % Fs) esencialmente escribe en estos bits un cierto valor del
intervalo del carácter
s , porque
Bs es el comienzo del intervalo, y (x% Fs) es el número dentro de este intervalo (el tamaño del intervalo es Fs). Por lo tanto, al decodificar, podemos determinar el carácter codificado por el intervalo en el que cae (x% M).
DecodificaciónPasemos a la función de decodificación.
D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - Bs
Como ya entendimos anteriormente, el carácter deseado
s está determinado por el resto de la división
x %
M. En qué intervalo cayó el valor (x% M), se codificó dicho carácter.
Anteriormente, definimos específicamente M = 2 ^ k para simplificar la función de decodificación. Terminó así:
uint32_t RansDecode(RansState& x, RansInBuf& in) { assert(x >= RANS_L);
La decodificación comienza con la misma
x que se obtuvo al final de la codificación. Para hacer esto, debe guardarse junto con los datos codificados.
Al final de la decodificación, el estado del decodificador
x debe ser exactamente el mismo que el de la codificación. En general, en cada paso
x debe ser exactamente el mismo que en el paso de codificación correspondiente. Este hecho ayuda mucho al depurar.
Como puede ver, la decodificación funciona más rápido que la codificación, ya que no hay operaciones de división.
El momento más difícil en la función de decodificación es el método para determinar en qué intervalo cayó el valor (x% M).
El método más fácil y rápido es usar la tabla
sym [] , tamaño
M. En este caso, obtenemos una tabla del mismo tamaño que en el algoritmo FSE, con la diferencia de que en rANS la tabla no está "mezclada", los caracteres están en orden y esa tabla es mucho más fácil de construir.
El principal inconveniente de este enfoque es el tamaño de la tabla de
símbolos , que crece exponencialmente con el aumento de
k .
Método alias
Se inventó un
método de alias para determinar de manera más eficiente el golpe en un intervalo. Este método le permite determinar rápidamente el intervalo deseado utilizando tablas pequeñas, por la cantidad de caracteres en el alfabeto.
Una explicación larga y larga se puede encontrar aquí:
dardos, dados y monedas . Describiré brevemente la esencia del método: tomamos un fragmento del intervalo más largo y lo adjuntamos al intervalo más corto para que el tamaño total sea exactamente
M /
N (donde
N es el número de caracteres en el alfabeto). Resulta que si haces esto secuencialmente, siempre terminarás con
N pares de tamaño
M /
N.Naturalmente,
M debe ser divisible por
N. Y si recordamos que tenemos
M = 2 ^
k , entonces el tamaño del alfabeto también resulta ser una potencia de dos. Esto no es un problema, ya que siempre puede complementar el alfabeto al tamaño deseado con caracteres no utilizados con una frecuencia cero.
El hecho de que el intervalo de caracteres se divida en varias partes complica un poco el procedimiento de codificación, pero no mucho. Si recuerda el FSE, entonces los intervalos generalmente se extendieron en todo el rango, como si un mezclador loco hubiera trabajado en ellos, y nada funcionó =)
Determinar el intervalo deseado no es difícil: dividir
x entre
N y caer en uno de los pares. A continuación, comparamos el resto de la división de
x% N con el límite entre los segmentos en un par y cae en un intervalo o en otro.
Lo intentamos en la práctica
Usaremos el código del
ejemplo terminado .
Tomamos los datos para la compresión del archivo:
size_t in_size; uint8_t* in_bytes = read_file("book1", &in_size);
1. Primero debe decidir sobre
la estructura de datos .
Usamos la opción más simple: codificaremos un byte usando el alfabeto [0 ... 255].
2. El siguiente paso es determinar la
frecuencia de los caracteres del alfabeto:
(función
stats.count_freqs )
for (size_t i = 0; i < in_size; i++) { freqs[in_bytes[i]]++; }
3. Entonces, tenemos frecuencias de símbolos, pero ahora necesitamos
normalizarlas , es decir, reducirlas (o aumentarlas) proporcionalmente para que en total obtengamos M = 2 ^ k. Esta no es una tarea tan simple como podría parecer, por lo que utilizamos una función preparada:
stats.normalize_freqs(...);
Por cierto, debes determinar el valor de
k . Como nuestro alfabeto consta de 256 caracteres, no se deben tomar
k menos de 8. Primero, tome el máximo - 16, y luego intente con otros valores.
4. Construir
tabla de alias :
stats.make_alias_table();
5. Codificamos
desde el final , luego para decodificar en el orden normal.
RansState rans;
Además, el ejemplo por referencia decodifica datos comprimidos utilizando estadísticas ya hechas. En la vida real, para decodificar, debe guardar una tabla de frecuencias (estadísticas) junto con datos comprimidos. En el caso más simple, tendrá que gastar N * k bits en él.
Como se prometió anteriormente, veamos los resultados de compresión para varios valores de k (en el código es
prob_bits ), teniendo en cuenta el aumento de tamaño debido al registro de la tabla de frecuencias:
(
Tamaño del archivo original del libro1 : 768771)
k = 16: 435059 + 512 = 435571 bytes
k =
15 : 435078 + 480 =
435558 bytes
k = 14: 435113 + 448 = 435561 bytes
k = 13: 435239 + 416 = 435655 bytes
k = 12: 435603 + 384 = 435987 bytes
k = 11: 436530 + 352 = 436882 bytes
k = 10: 440895 + 320 = 441215 bytes
k = 9: 453418 + 288 = 453706 bytes
k = 8: 473126 + 256 = 473382 bytes
Puede ver que cuanto mayor sea k, mejor será la compresión. Pero en cierto punto (en k = 16), la sobrecarga de la tabla de frecuencias comienza a superar los beneficios de aumentar la precisión. Si comprime un archivo más pequeño, este efecto aparecerá en k más pequeño.
También debe decir algunas palabras sobre el truco llamado "rANS intercalados", que se implementa adicionalmente
en este ejemplo . La idea es que el uso alternativo de dos variables de estado independientes hace un mejor uso del paralelismo del procesador. Como resultado, la decodificación es aún más rápida.
En conclusión, quiero señalar que el método de compresión de archivos seleccionado es demasiado simple. No tiene en cuenta las características de los datos, por lo que la compresión dista mucho de ser óptima. Si observa de cerca la entrada, puede encontrar que algunas
combinaciones de letras son más comunes que otras, y algunas no ocurren en absoluto. Usando este hecho, la compresión se puede mejorar significativamente. Pero este es un tema para un artículo separado.
Epílogo
¿Por qué escribir su propio archivador cuando hay muchas utilidades probadas? La respuesta es bastante simple: los archivadores adaptados a un formato específico se comprimen mucho mejor.
Cuando desarrollamos juegos en
Playrix , a menudo confiamos en la necesidad de reducir el tamaño de construcción. Los juegos evolucionan constantemente, la cantidad de contenido está creciendo y el espacio es limitado.
Una vez más
, mirando con
anhelo los recursos, nos dimos cuenta de que algunos archivos se pueden comprimir mucho mejor que zip, dada su estructura. Durante los experimentos, logramos reducir significativamente el tamaño de nuestro propio formato de animación, también hay algunos cambios en la compresión de archivos gráficos.
Al desarrollar algoritmos de compresión, un codificador de entropía universal, como rANS o FSE, es una herramienta indispensable. Asume completamente la tarea de escribir caracteres con el menor número de bits, lo que permite al desarrollador centrarse en los detalles principales del algoritmo. Y también funciona muy rápido tanto en codificación como en decodificación.
Espero que este artículo te ayude a conocer RANS y comenzar a usarlo en tus proyectos.
Referencias
Aquí puede ver ejemplos de trabajo de implementación de rANS (con diferentes opciones de optimización):
Fabian Giesen:
github.com/rygorous/ryg_ransPuede leer detalles interesantes y detalles en el blog de Fabian (en inglés):
→
notas RANS→
RANS con distribuciones de probabilidad estáticas→
RANS en la práctica