Sistemas de numeración asimétricos

Este artículo incluye una lista de referencias generales , pero carece de suficientes citas en línea correspondientes . Ayúdenos a mejorar este artículo introduciendo citas más precisas. ( Mayo de 2017 ) ( Aprenda cómo y cuándo eliminar este mensaje )

Los sistemas numerales asimétricos ( ANS ) ^{[1] [2]} son ​​una familia de métodos de codificación de entropía introducidos por Jarosław (Jarek) Duda ^[3] de la Universidad Jagellónica , utilizados en la compresión de datos desde 2014 ^[4] debido a un rendimiento mejorado en comparación con los métodos anteriores. ^[5] ANS combina la relación de compresión de la codificación aritmética (que utiliza una distribución de probabilidad casi precisa ), con un costo de procesamiento similar al de la codificación de Huffman . En la variante ANS tabulada (tANS), esto se logra construyendo una máquina de estados finitos para operar en un alfabeto grande sin usar la multiplicación.

Entre otros, ANS se utiliza en el compresor Zstandard de Facebook ^{[6] [7]} (también utilizado, por ejemplo, en el kernel de Linux , ^{[8] el navegador} Google Chrome , ^{[9] el sistema operativo} Android ^[10] , se publicó como RFC 8478 para MIME ^[11] y HTTP ^[12] ), el compresor Apple LZFSE , ^{[13] el compresor 3D} Google Draco ^[14] (utilizado, por ejemplo, en el formato Pixar Universal Scene Description ^[15] ) y el compresor de imágenes PIK, ^{[16] el compresor} CRAM DNA ^[17] de las utilidades SAMtools , ^{[18] la biblioteca de compresión de alta velocidad} NVIDIA nvCOMP, ^{[19] el compresor} Dropbox DivANS, ^{[20] el compresor de textura} Microsoft DirectStorage BCPack, ^[21] y el compresor de imágenes JPEG XL ^[22] .

La idea básica es codificar la información en un único número natural . En el sistema numérico binario estándar, podemos añadir un poco de información a añadiendo al final de , lo que nos da . Para un codificador de entropía, esto es óptimo si . ANS generaliza este proceso para conjuntos arbitrarios de símbolos con una distribución de probabilidad acompañante . En ANS, si la información de se añade a para dar como resultado , entonces . De manera equivalente, , donde es el número de bits de información almacenados en el número , y es el número de bits contenidos en el símbolo .${\displaystyle x}$${\displaystyle s\in \{0,1\}}$${\displaystyle x}$${\displaystyle s}$${\displaystyle x}$${\displaystyle x'=2x+s}$${\displaystyle \Pr(0)=\Pr(1)=1/2}$${\displaystyle s\in S}$${\displaystyle (p_{s})_{s\in S}}$${\displaystyle s}$${\displaystyle x}$${\displaystyle x'}$${\displaystyle x'\approx x\cdot p_{s}^{-1}}$${\displaystyle \log _{2}(x')\approx \log _{2}(x)+\log _{2}(1/p_{s})}$${\displaystyle \log _{2}(x)}$${\displaystyle x}$${\displaystyle \log _{2}(1/p_{s})}$${\displaystyle s}$

Para la regla de codificación, el conjunto de números naturales se divide en subconjuntos disjuntos que corresponden a diferentes símbolos, como números pares e impares, pero con densidades correspondientes a la distribución de probabilidad de los símbolos a codificar. Luego, para agregar información del símbolo a la información ya almacenada en el número actual , pasamos a número que es la posición de la -ésima aparición del -ésimo subconjunto.${\displaystyle s}$${\displaystyle x}$${\displaystyle x'=C(x,s)\approx x/p}$${\displaystyle x}$${\displaystyle s}$

Existen formas alternativas de aplicarlo en la práctica: fórmulas matemáticas directas para los pasos de codificación y decodificación (variantes uABS y rANS), o se puede poner todo el comportamiento en una tabla (variante tANS). La renormalización se utiliza para evitar llegar al infinito (transferir bits acumulados hacia o desde el flujo de bits).${\displaystyle x}$

Supongamos que se codifica una secuencia de 1000 ceros y unos, lo que requeriría 1000 bits para almacenarse directamente. Sin embargo, si de alguna manera se sabe que solo contiene 1 cero y 999 unos, sería suficiente codificar la posición del cero, lo que requiere solo bits en lugar de los 1000 bits originales.${\displaystyle \lceil \log _{2}(1000)\rceil \approx 10}$

En general, a estas secuencias de longitud que contienen ceros y unos, para una probabilidad determinada , se las llama combinaciones . Utilizando la aproximación de Stirling obtenemos que su número asintótico es${\displaystyle n}$${\displaystyle pn}$${\displaystyle (1-p)n}$${\displaystyle p\in (0,1)}$

${\displaystyle {n \choose pn}\approx 2^{nh(p)}{\text{ for large }}n{\text{ and }}h(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p),}$

llamada entropía de Shannon .

Por lo tanto, para elegir una de estas secuencias necesitamos aproximadamente bits. Sigue siendo bits si , pero también puede ser mucho más pequeño. Por ejemplo, necesitamos solo bits para .${\displaystyle nh(p)}$${\displaystyle n}$${\displaystyle p=1/2}$${\displaystyle \approx n/2}$${\displaystyle p=0.11}$

Un codificador de entropía permite codificar una secuencia de símbolos utilizando aproximadamente los bits de entropía de Shannon por símbolo. Por ejemplo, ANS podría utilizarse directamente para enumerar combinaciones: asignar un número natural diferente a cada secuencia de símbolos que tengan proporciones fijas de una manera casi óptima.

A diferencia de las combinaciones de codificación, esta distribución de probabilidad suele variar en los compresores de datos. Para este propósito, la entropía de Shannon puede verse como un promedio ponderado: un símbolo de probabilidad contiene bits de información. ANS codifica la información en un solo número natural , que se interpreta como que contiene bits de información. Agregar información de un símbolo de probabilidad aumenta este contenido informativo a . Por lo tanto, el nuevo número que contiene ambas informaciones debería ser .${\displaystyle p}$${\displaystyle \log _{2}(1/p)}$${\displaystyle x}$${\displaystyle \log _{2}(x)}$${\displaystyle p}$${\displaystyle \log _{2}(x)+\log _{2}(1/p)=\log _{2}(x/p)}$${\displaystyle x'\approx x/p}$

Consideremos una fuente con 3 letras A, B, C, con probabilidad 1/2, 1/4, 1/4. Es sencillo construir el código de prefijo óptimo en binario: A = 0, B = 10, C = 11. Luego, un mensaje se codifica como ABC -> 01011.

Vemos que un método equivalente para realizar la codificación es el siguiente:

• Comience con el número 1 y realice una operación en el número para cada letra ingresada.
• A = multiplicar por 2; B = multiplicar por 4, sumar 2; C = multiplicar por 4, sumar 3.
• Expresa el número en binario, luego elimina el primer dígito 1.

Consideremos una fuente más general con k letras, con probabilidades racionales . Entonces, para realizar la codificación aritmética en la fuente, solo se requiere aritmética exacta con números enteros.${\displaystyle n_{1}/N,...,n_{k}/N}$

En general, ANS es una aproximación de codificación aritmética que aproxima las probabilidades reales mediante números racionales con un denominador pequeño .${\displaystyle r_{1},...,r_{k}}$${\displaystyle n_{1}/N,...,n_{k}/N}$${\displaystyle N}$

Imaginemos que hay cierta información almacenada en un número natural , por ejemplo, como una secuencia de bits de su expansión binaria. Para agregar información de una variable binaria , podemos usar la función de codificación , que desplaza todos los bits una posición hacia arriba y coloca el nuevo bit en la posición menos significativa. Ahora, la función de decodificación permite recuperar el bit anterior y este agregado: . Podemos comenzar con el estado inicial, luego usar la función en los bits sucesivos de una secuencia de bits finita para obtener un número final que almacene esta secuencia completa. Luego, usar la función varias veces hasta permite recuperar la secuencia de bits en orden inverso.${\displaystyle x}$${\displaystyle s}$${\displaystyle x'=C(x,s)=2x+s}$${\displaystyle D(x')=(\lfloor x'/2\rfloor ,\mathrm {mod} (x',2))}$${\displaystyle x}$${\displaystyle D(C(x,s))=(x,s),\ C(D(x'))=x'}$${\displaystyle x=1}$${\displaystyle C}$${\displaystyle x}$${\displaystyle D}$${\displaystyle x=1}$

El procedimiento anterior es óptimo para la distribución de probabilidad uniforme (simétrica) de los símbolos . ANS lo generaliza para que sea óptimo para cualquier distribución de probabilidad (asimétrica) elegida de los símbolos: . Mientras que en el ejemplo anterior se elegía entre pares e impares , en ANS esta división par/impar de números naturales se reemplaza con la división en subconjuntos que tienen densidades correspondientes a la distribución de probabilidad supuesta : hasta la posición , hay aproximadamente ocurrencias del símbolo .${\displaystyle \Pr(0)=\Pr(1)=1/2}$${\displaystyle \Pr(s)=p_{s}}$${\displaystyle s}$${\displaystyle C(x,s)}$${\displaystyle \{p_{s}\}_{s}}$${\displaystyle x}$${\displaystyle xp_{s}}$${\displaystyle s}$

La función de codificación devuelve la -ésima aparición de dicho subconjunto correspondiente al símbolo . La suposición de densidad es equivalente a la condición . Suponiendo que un número natural contiene bits de información, . Por lo tanto, el símbolo de probabilidad se codifica como si contuviera bits de información, tal como lo exigen los codificadores de entropía .${\displaystyle C(x,s)}$${\displaystyle x}$${\displaystyle s}$${\displaystyle x'=C(x,s)\approx x/p_{s}}$${\displaystyle x}$${\displaystyle \log _{2}(x)}$${\displaystyle \log _{2}(C(x,s))\approx \log _{2}(x)+\log _{2}(1/p_{s})}$${\displaystyle p_{s}}$${\displaystyle \approx \log _{2}(1/p_{s})}$

Empecemos con el alfabeto binario y una distribución de probabilidad , . Hasta la posición queremos análogos aproximados de números impares (para ). Podemos elegir este número de apariciones como , obteniendo . Esta variante se llama uABS y conduce a las siguientes funciones de codificación y decodificación: ^[23]${\displaystyle \Pr(1)=p}$${\displaystyle \Pr(0)=1-p}$${\displaystyle x}$${\displaystyle p\cdot x}$${\displaystyle s=1}$${\displaystyle \lceil x\cdot p\rceil }$${\displaystyle s=\lceil (x+1)\cdot p\rceil -\lceil x\cdot p\rceil }$

Descodificación:

s = ceil (( x + 1 ) * p ) - ceil ( x * p ) // 0 si fract(x*p) < 1-p, de lo contrario 1 si s = 0 entonces new_x = x - ceil ( x * p ) // D(x) = (new_x, 0), esto es lo mismo que new_x = floor(x*(1-p)) si s = 1 entonces new_x = ceil ( x * p ) // D(x) = (new_x, 1)                       

Codificación:

si s = 0 entonces nuevo_x = techo (( x + 1 ) / ( 1 - p )) - 1 // C(x,0) = nuevo_x si s = 1 entonces nuevo_x = piso ( x / p ) // C(x,1) = nuevo_x                  

Dado que se trata del sistema binario estándar (con 0 y 1 invertidos), para un sistema diferente resulta óptimo para esta distribución de probabilidad dada. Por ejemplo, para estas fórmulas se obtiene una tabla para valores pequeños de :${\displaystyle p=1/2}$${\displaystyle p}$${\displaystyle p=0.3}$${\displaystyle x}$

${\displaystyle C(x,s)}$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
${\displaystyle s=0}$		0	1		2	3		4	5	6		7	8		9	10		11	12	13
${\displaystyle s=1}$	0			1			2				3			4			5				6

El símbolo corresponde a un subconjunto de números naturales con densidad , que en este caso son las posiciones . Como , estas posiciones aumentan en 3 o 4. Porque aquí, el patrón de símbolos se repite cada 10 posiciones.${\displaystyle s=1}$${\displaystyle p=0.3}$${\displaystyle \{0,3,6,10,13,16,20,23,26,\ldots \}}$${\displaystyle 1/4<0.3<1/3}$${\displaystyle p=3/10}$

La codificación se puede encontrar tomando la fila correspondiente a un símbolo dado y eligiendo el dado en esta fila. Luego, la fila superior proporciona . Por ejemplo, desde la fila del medio hasta la fila superior.${\displaystyle C(x,s)}$${\displaystyle s}$${\displaystyle x}$${\displaystyle C(x,s)}$${\displaystyle C(7,0)=11}$

Imaginemos que queremos codificar la secuencia '0100' a partir de . Primero nos lleva a , luego a , luego a , luego a . Al utilizar la función de decodificación en este , podemos recuperar la secuencia de símbolos. Utilizando la tabla para este propósito, en la primera fila determina la columna, luego la fila no vacía y el valor escrito determinan el y correspondiente .${\displaystyle x=1}$${\displaystyle s=0}$${\displaystyle x=2}$${\displaystyle s=1}$${\displaystyle x=6}$${\displaystyle s=0}$${\displaystyle x=9}$${\displaystyle s=0}$${\displaystyle x=14}$${\displaystyle D(x')}$${\displaystyle x}$${\displaystyle x}$${\displaystyle s}$${\displaystyle x}$

La variante de rango también utiliza fórmulas aritméticas, pero permite operar sobre un alfabeto grande. Intuitivamente, divide el conjunto de números naturales en rangos de tamaño y divide cada uno de ellos de manera idéntica en subrangos de proporciones dados por la distribución de probabilidad supuesta.${\displaystyle 2^{n}}$

Comenzamos con la cuantificación de la distribución de probabilidad al denominador, donde se elige n (generalmente 8-12 bits): para algunos números naturales (tamaños de subrangos).${\displaystyle 2^{n}}$${\displaystyle p_{s}\approx f[s]/2^{n}}$${\displaystyle f[s]}$

Denotemos , y una función de distribución acumulativa:${\displaystyle {\text{mask}}=2^{n}-1}$

${\displaystyle \operatorname {CDF} [s]=\sum _{i<s}f[i]=f[0]+\cdots +f[s-1].}$

Tenga en cuenta que la función no es una verdadera función de distribución de probabilidad (CDF) ya que la probabilidad del símbolo actual no está incluida en el valor de la expresión. En cambio, representa la probabilidad total de todos los símbolos anteriores. Ejemplo: en lugar de la definición normal de , se evalúa como , ya que no hay símbolos anteriores.CDF[s]CDF[s]CDF[0] = f[0]CDF[0] = 0

Para denotar función (normalmente en tabla)${\displaystyle y\in [0,2^{n}-1]}$

símbolo ( y ) = s tal que CDF [ s ] <= y < CDF [ s + 1 ]         

Ahora la función de codificación es:

C ( x , s ) = ( piso ( x / f [ s ]) << n ) + ( x % f [ s ]) + CDF [ s ]            

Descodificación:s = symbol(x & mask)

D ( x ) = ( f [ s ] * ( x >> n ) + ( x & máscara ) - CDF [ s ], s )              

De esta manera podemos codificar una secuencia de símbolos en un gran número natural x . Para evitar el uso de aritmética de números grandes, en la práctica se utilizan variantes de flujo: que se aplican mediante renormalización: enviando los bits menos significativos de x hacia o desde el flujo de bits (normalmente L y b son potencias de 2).${\displaystyle x\in [L,b\cdot L-1]}$

En la variante rANS, x es, por ejemplo, de 32 bits. Para la renormalización de 16 bits, el decodificador rellena los bits menos significativos del flujo de bits cuando es necesario:${\displaystyle x\in [2^{16},2^{32}-1]}$

si ( x < ( 1 << 16 )) x = ( x << 16 ) + leer16bits ()           

La variante tANS coloca todo el comportamiento (incluida la renormalización) en una tabla que produce una máquina de estados finitos evitando la necesidad de multiplicación.${\displaystyle x\in [L,2L-1]}$

Finalmente, el paso del bucle de decodificación se puede escribir como:

t = decodingTable ( x ); x = t.newX + readBits ( t.nbBits ) ; // transición de estado writeSymbol ( t.symbol ) ; // símbolo decodificado         

El paso del bucle de codificación:

s = ReadSymbol (); nbBits = ( x + ns [ s ]) >> r ; // # de bits para renormalización writeBits ( x , nbBits ); // envía los bits menos significativos al flujo de bits x = encodingTable [ start [ s ] + ( x >> nbBits )];                 

Una codificación tANS específica se determina asignando un símbolo a cada posición, su número de apariciones debe ser proporcional a las probabilidades asumidas. Por ejemplo, se podría elegir la asignación "abdacdac" para la distribución de probabilidad Pr(a)=3/8, Pr(b)=1/8, Pr(c)=2/8, Pr(d)=2/8. Si los símbolos se asignan en rangos de longitudes que sean potencias de 2, obtendríamos la codificación de Huffman . Por ejemplo, se obtendría el código de prefijo a->0, b->100, c->101, d->11 para tANS con la asignación de símbolo "aaaabcdd".${\displaystyle [L,2L-1]}$

En cuanto a la codificación de Huffman, modificar la distribución de probabilidad de tANS es relativamente costoso, por lo que se utiliza principalmente en situaciones estáticas, normalmente con algún esquema Lempel–Ziv (por ejemplo, ZSTD, LZFSE). En este caso, el archivo se divide en bloques: para cada uno de ellos, las frecuencias de los símbolos se cuentan de forma independiente y, después de la aproximación (cuantificación), se escriben en el encabezado del bloque y se utilizan como distribución de probabilidad estática para tANS.

Por el contrario, rANS se utiliza generalmente como un reemplazo más rápido para la codificación de rango (por ejemplo, CRAM , LZNA, Draco, ^[14] ). Requiere multiplicación, pero es más eficiente en el uso de la memoria y es adecuado para adaptar dinámicamente las distribuciones de probabilidad.

La codificación y decodificación de ANS se realizan en direcciones opuestas, lo que lo convierte en una pila de símbolos. Este inconveniente generalmente se resuelve codificando en dirección inversa, después de lo cual la decodificación puede realizarse hacia adelante. Para la dependencia del contexto, como el modelo de Markov , el codificador debe usar el contexto desde la perspectiva de la decodificación posterior. Para la adaptabilidad, el codificador primero debe avanzar para encontrar probabilidades que serán utilizadas (predichas) por el decodificador y almacenarlas en un búfer, luego codificar en dirección inversa utilizando las probabilidades almacenadas en el búfer.

El estado final de la codificación es necesario para iniciar la decodificación, por lo que debe almacenarse en el archivo comprimido. Este costo se puede compensar almacenando cierta información en el estado inicial del codificador. Por ejemplo, en lugar de comenzar con el estado "10000", comience con el estado "1****", donde "*" son algunos bits almacenados adicionales, que se pueden recuperar al final de la decodificación. Alternativamente, este estado se puede utilizar como suma de comprobación iniciando la codificación con un estado fijo y probando si el estado final de la decodificación es el esperado.

El autor del nuevo algoritmo ANS y sus variantes tANS y rANS tenía la intención específica de que su trabajo estuviera disponible de forma gratuita en el dominio público, por razones altruistas. No ha buscado lucrarse con ellos y tomó medidas para asegurarse de que no se convirtieran en un "campo minado legal", ni que otros los restringieran o se beneficiaran de ellos. En 2015, Google publicó una patente estadounidense y luego mundial para la "codificación de coeficientes ANS de tokens booleanos mixtos". ^[24] En ese momento, Google le había pedido al profesor Duda que lo ayudara con la compresión de video, por lo que conocía íntimamente este dominio, y contó con la asistencia del autor original.

Duda no se sintió satisfecho con el descubrimiento (accidental) de las intenciones de Google con respecto a la patente, dado que había dejado en claro que la quería como dominio público y había ayudado a Google específicamente sobre esa base. Posteriormente, Duda presentó una solicitud de un tercero ^[25] ante la Oficina de Patentes de los Estados Unidos para solicitar su rechazo. La USPTO rechazó su solicitud en 2018 y, posteriormente, Google abandonó la patente. ^[26]

En junio de 2019, Microsoft presentó una solicitud de patente denominada "Características de la codificación y decodificación de sistemas numéricos asimétricos de rango". ^[27] La ​​USPTO emitió un rechazo final de la solicitud el 27 de octubre de 2020. Sin embargo, el 2 de marzo de 2021, Microsoft presentó una presentación explicativa ante la USPTO en la que afirmaba "El solicitante respetuosamente no está de acuerdo con los rechazos", ^[28] buscando revocar el rechazo final en virtud del programa "After Final Consideration Pilot 2.0". ^[29] Después de la reconsideración, la USPTO concedió la solicitud el 25 de enero de 2022. ^[30]

• Codificación de entropía
• Codificación de Huffman
• Codificación aritmética
• Codificación de rango
• Compresor de Facebook Zstandard
• Compresor de Apple LZFSE

• Arquitecturas de hardware de alto rendimiento para sistemas numéricos asimétricos codificados por entropía SM Najmabadi, Z. Wang, Y. Baroud, S. Simon, ISPA 2015
• Implementación de entropía de estado finito (FSE) de codificadores de entropía de nueva generación de tANS por Yann Collet
• Implementación de rANS por Fabian Giesen
• jkbonfield/rans_static Implementación rápida de rANS y codificación aritmética por James K. Bonfield
• facebook /zstd Compresor Zstandard de Yann Collet (autor de LZ4 )
• Compresor LZFSE LZFSE (LZ+FSE) de Apple Inc.
• Compresor de ADN CRAM 3.0 (orden 1 rANS) (parte de SAMtools ) del Instituto Europeo de Bioinformática
• [1] Implementación para Google VP10
• [2] Implementación para Google WebP
• [3] Biblioteca de compresión 3D Draco de Google
• aom_dsp - aom - Git en la implementación de Google de Alliance for Open Media
• Compresión de datos mediante sistemas numéricos asimétricos - Proyecto de demostraciones Wolfram Proyecto de demostraciones Wolfram
• GST: Texturas supercomprimidas decodificables por GPU GST: Texturas supercomprimidas decodificables por GPU
• Comprensión del libro de compresión de A. Haecky y C. McAnlis