¿Existe una generalización de la codificación Huffman a la codificación aritmética?

Al tratar de comprender las relaciones entre la codificación Huffman, la codificación aritmética y la codificación por rango, comencé a pensar en las deficiencias de la codificación Huffman en relación con el problema del empaquetado de bits fraccional .

Es decir, suponga que tiene 240 valores posibles para un símbolo, y que necesita codificar esto en bits, estaría atascado con 8 bits por símbolo, aunque no necesite un 8 "completo", ya que 8 puede expresar 256 valores posibles por símbolo Una solución a este problema es algo que he visto referido como "empaquetamiento de bits fraccional", en el que puede "desplazar bits" por una no potencia de dos mediante la multiplicación. Al igual que la multiplicación de potencias de dos está cambiando x * 2 == x << 1y x * 4 == x << 2así sucesivamente para todas las potencias de dos, también puede "cambiar" con una potencia no-2 multiplicando en su lugar, y empacar en símbolos de tamaño de bits fraccionales .

El problema es similar con la codificación de Huffman: terminas con códigos que deben tener una longitud de tamaño de bits no fraccional y, por lo tanto, tiene esta ineficiencia de empaque. Sin embargo, no puede simplemente usar la solución de empaquetado fraccional de bits, porque esta solución asume símbolos de tamaño fijo.

La pregunta es, ¿hay documentos o soluciones para mejorar la codificación de Huffman con una idea similar al empaquetado de bits fraccionales para lograr algo similar a la codificación aritmética? (o cualquier resultado en contrario).

Veamos una forma ligeramente diferente de pensar sobre la codificación de Huffman.

Suponga que tiene un alfabeto de tres símbolos, A, B y C, con probabilidades 0.5, 0.25 y 0.25. Debido a que todas las probabilidades son potencias inversas de dos, esto tiene un código Huffman que es óptimo (es decir, es idéntico a la codificación aritmética). Utilizaremos el código canónico 0, 10, 11 para este ejemplo.

Supongamos que nuestro estado es un número entero grande, al que llamaremos . Puede pensar en la codificación como una función que toma el estado actual, y un símbolo para codificar, y devuelve el nuevo estado:$s$

$$\begin{align*} \hbox{encode}(s, A) &= 2s\\ \hbox{encode}(s, B) &= 4s + 2\\ \hbox{encode}(s, C) &= 4s + 3\\ \end{align*}$$

Comencemos con el estado 11 (que es 1011 en binario), codifique el símbolo B. El nuevo estado es 46, que es 101110 en binario. Como puede ver, este es el estado "antiguo" con la secuencia 10 agregada al final. Básicamente, hemos "generado" la secuencia de bits 10.

Hasta ahora tan bueno.

Ahora piense por un momento acerca de cómo funciona la codificación aritmética. Si coloca las probabilidades sobre un denominador común, el símbolo A en realidad representa el rango , el símbolo B representa el rango[$[\frac{0}{4},\frac{2}{4})$y el símbolo C representa el rango[$[\frac{2}{4},\frac{3}{4})$.$[\frac{3}{4},\frac{4}{4})$

Básicamente, lo que estamos haciendo aquí es multiplicar todo por el común denominador. Imagine que el estado estaba realmente en la base 4. La codificación de un símbolo B realmente genera el dígito 2 en esa base, y la codificación de un símbolo C genera el dígito 3 en esa base.

Sin embargo, el símbolo A es un poco diferente, porque no es un dígito completo en la base 4.

En cambio, podemos pensar en el alfabeto como el conjunto de símbolos A_0, A_1, B, C, con igual probabilidad. Esto, nuevamente, tiene un código óptimo de Huffman 00, 01, 10, 11. O, nuevamente, podemos pensar en esto en la base 4. Para codificar un símbolo, simplemente hacemos:

$$\begin{align*} \hbox{encode}(s, A_0) &= 4s + 0\\ \hbox{encode}(s, A_1) &= 4s + 1\\ \hbox{encode}(s, B) &= 4s + 2\\ \hbox{encode}(s, C) &= 4s + 3 \end{align*}$$

$A_0$$A_1$

$s$

$$s' = \left\lfloor \frac{s}{2} \right\rfloor$$ $$i = s \bmod 2$$

y luego .$\hbox{encode}(s', A_i)$

Usando nuestro ejemplo anterior, , encontramos que e , y luego . El nuevo estado es 10101 en binario.s ′ = 5 i = 1 codificar ( 5 , A 1 ) = 4 × 5 + 1 = $s=11$$s'=5$$i=1$$\hbox{encode}(5, A_1) = 4\times 5+1 = 21$

Ahora, esto no produce exactamente la misma salida de bits que la codificación Huffman, pero genera una salida que tiene la misma longitud. Y lo que espero que puedan ver es que esto también es decodificable de forma única. Para decodificar un símbolo, tomamos el resto cuando se divide entre 4. Si el valor es 2 o 3, entonces el símbolo es B o C, respectivamente. Si es 0 o 1, entonces el símbolo es A, y luego podemos recuperar el bit de información multiplicando el estado por 2 y agregando 0 o 1.

Lo bueno de este enfoque es que se extiende naturalmente a la codificación de bits fraccionales, cuando el numerador y / o denominador de las probabilidades no son potencias de dos. Supongamos que tenemos dos símbolos, A y B, donde la probabilidad de A es y la probabilidad de B es . Entonces podemos codificar un símbolo con:$\frac{3}{5}$$\frac{2}{5}$

$$\begin{align*} \hbox{encode}(s, A_0) &= 5s + 0\\ \hbox{encode}(s, A_1) &= 5s + 1\\ \hbox{encode}(s, A_2) &= 5s + 2\\ \hbox{encode}(s, B_0) &= 5s + 3\\ \hbox{encode}(s, B_1) &= 5s + 4 \end{align*}$$

Para codificar el símbolo A, tomamos e , y luego .$s' = \left\lfloor \frac{s}{3} \right\rfloor$$i = s \bmod 3$$\hbox{encode}(s', A_i)$

Esto es equivalente a la codificación aritmética. En realidad, es una familia de métodos conocidos como sistemas numéricos asimétricos , y fue desarrollada en los últimos años por Jarek Duda. El significado del nombre debe ser obvio: para codificar un símbolo con probabilidad , conceptualmente robas un dígito base-p del estado y luego agregas un dígito base-q. La asimetría proviene de interpretar el estado como un número en dos bases diferentes.$\frac{p}{q}$

La razón por la cual es una familia de métodos de codificación es que lo que hemos visto aquí no es práctico por sí mismo; necesita algunas modificaciones para lidiar con el hecho de que probablemente no tenga enteros de precisión infinita para manipular la variable de estado de manera eficiente, y hay varias formas de lograrlo. La codificación aritmética, por supuesto, tiene un problema similar con precisión para su estado.

Las variantes prácticas incluyen rANS (la "r" significa "relación") y tANS ("controlado por tabla").

ANS tiene algunas ventajas interesantes sobre la codificación aritmética, tanto práctica como teórica:

• A diferencia de la codificación aritmética, el "estado" es una sola palabra, en lugar de un par de palabras.
• No solo eso, sino que un codificador ANS y su decodificador correspondiente tienen estados idénticos y sus operaciones son completamente simétricas. Esto plantea algunas posibilidades interesantes, como que puede intercalar diferentes flujos de símbolos codificados y todo se sincroniza perfectamente.
• Las implementaciones prácticas necesitan, por supuesto, "generar" información sobre la marcha, y no solo recopilarla en un gran número entero que se escribirá al final. Sin embargo, el tamaño de la "salida" se puede configurar a cambio de una pérdida de compresión (generalmente modesta). Entonces, cuando los codificadores aritméticos deben generar un bit a la vez, ANS puede generar un byte o un nybble a la vez. Esto le proporciona un compromiso directo entre velocidad y compresión.
• Parece ser tan rápido en el hardware de la generación actual como la codificación aritmética binaria y, por lo tanto, competitivo con la codificación Huffman. Esto lo hace mucho más rápido que la codificación aritmética de alfabeto grande y sus variantes (por ejemplo, la codificación de rango).
• Parece estar libre de patentes.

No creo que vuelva a hacer codificación aritmética.

Como ejemplo simple, si tuviera tres símbolos con probabilidad de 1/3 de cada uno, su codificación Huffman óptima usaría los tres símbolos 0, 10 y 11 con un promedio de 5/3 bits.

Hay 243 símbolos creados al concatenar 5 de los símbolos originales, cada uno con probabilidad 1/243. Lo cual está mucho más cerca de 1/256. La codificación Huffman óptima codificará 13 de estos grupos en 7 bits y 230 grupos en 8 bits, para un promedio de 7.9465 bits por grupo o 1.5893 bits por símbolo original, por debajo de 1.6667 bits para la codificación original de Huffman, con una codificación aritmética que toma 1.5850 bits

Entonces, en teoría, podría combinar dos símbolos cada uno en un símbolo más grande, o tres símbolos cada uno en un símbolo más grande, y usar la codificación Hufman para las combinaciones.