Sistemas de numeración asimétricos

Métodos de codificación de entropía

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}$

Codificación de entropía

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}$

Ejemplos motivadores

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}$

Conceptos básicos del SNA

Comparación del concepto de codificación aritmética (izquierda) y ANS (derecha). Ambos pueden considerarse como generalizaciones de los sistemas numéricos estándar, óptimos para una distribución de probabilidad uniforme de dígitos, en optimizados para una distribución de probabilidad elegida. La codificación aritmética o de rango corresponde a la adición de nueva información en la posición más significativa, mientras que ANS generaliza la adición de información en la posición menos significativa. Su regla de codificación es " x va a la x -ésima aparición del subconjunto de números naturales correspondiente al símbolo codificado actualmente". En el ejemplo presentado, la secuencia (01111) se codifica en un número natural 18, que es menor que 47 obtenido mediante el uso del sistema binario estándar, debido a una mejor concordancia con las frecuencias de la secuencia a codificar. La ventaja de ANS es almacenar información en un solo número natural, en contraste con dos que definen un rango.

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})}$

Variantes

Variante binaria uniforme (uABS)

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}$

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}$

Variantes de rango (rANS) y transmisión

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 ()           

Variante tabulada (tANS)

Ejemplo simple de autómata ANS de 4 estados para distribución de probabilidad Pr( a ) = 3/4, Pr( b ) = 1/4. El símbolo b contiene −lg(1/4) = 2 bits de información y por lo tanto siempre produce dos bits. En contraste, el símbolo a contiene −lg(3/4) ~ 0.415 bits de información, por lo tanto a veces produce un bit (del estado 6 y 7), a veces 0 bits (del estado 4 y 5), solo aumentando el estado, que actúa como búfer que contiene un número fraccionario de bits: lg( x ). El número de estados en la práctica es, por ejemplo, 2048, para un alfabeto de tamaño 256 (para codificar bytes directamente).

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]}$

Ejemplo de generación de tablas tANS para un alfabeto de tamaño m = 3 y L = 16 estados, y luego aplicación de las mismas para la decodificación de flujos. Primero, aproximamos las probabilidades utilizando una fracción con el denominador como el número de estados. Luego, distribuimos estos símbolos de manera casi uniforme; opcionalmente, los detalles pueden depender de la clave criptográfica para el cifrado simultáneo. Luego, enumeramos las apariciones comenzando con el valor como su cantidad para un símbolo dado. Luego, rellenamos los bits más recientes del flujo para volver al rango asumido para x (renormalización).

Observaciones

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.

Controversia sobre patentes

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]

Véase también

• 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

Referencias

1. J. Duda, K. Tahboub, NJ Gadil, EJ Delp, El uso de sistemas numéricos asimétricos como un reemplazo preciso para la codificación de Huffman, Simposio de codificación de imágenes, 2015.
2. J. Duda, Sistemas numerales asimétricos: codificación de entropía que combina la velocidad de la codificación de Huffman con la tasa de compresión de la codificación aritmética, arXiv:1311.2540, 2013.
3. "Dr. Jarosław Duda (Jarek Duda)". Instituto de Física Teórica . Universidad Jagellónica de Cracovia . Consultado el 2 de agosto de 2021 .
4. Duda, Jarek (6 de octubre de 2019). «Lista de compresores que utilizan ANS, implementaciones y otros materiales» . Consultado el 6 de octubre de 2019 .
5. "Google acusado de intentar patentar tecnología de dominio público". Bleeping Computer . 11 de septiembre de 2017.
6. Compresión de datos más pequeña y rápida con Zstandard, Facebook, agosto de 2016.
7. 5 formas en que Facebook mejoró la compresión a escala con Zstandard, Facebook, diciembre de 2018.
8. Compresión Zstd para Btrfs y Squashfs configurada para Linux 4.14, ya utilizada en Facebook, Phoronix, septiembre de 2017.
9. Novedades en Chrome 123 (codificación de contenido), Google, marzo de 2024.
10. "Lanzamiento de Zstd en Android P". Archivado desde el original el 26 de agosto de 2020. Consultado el 29 de mayo de 2019 .
11. Compresión Zstandard y tipo de medio application/zstd (estándar de correo electrónico).
12. Parámetros del Protocolo de transferencia de hipertexto (HTTP), IANA .
13. Apple publica en código abierto su nuevo algoritmo de compresión LZFSE, InfoQ, julio de 2016.
14. la biblioteca de compresión Google Draco 3D.
15. Google y Pixar agregan Draco Compression al formato de descripción de escena universal (USD).
16. Google PIK: nuevo formato de imagen con pérdida para Internet.
17. Especificación del formato CRAM (versión 3.0).
18. Chen W, Elliott LT (2021). "Compresión de datos genéticos poblacionales mediante entropía de estados finitos". J Bioinform Comput Biol . 19 (5): 2150026. doi : 10.1142/S0219720021500268 . PMID  34590992.
19. Compresión de datos de alta velocidad mediante GPU NVIDIA.
20. Desarrollamos una mejor compresión junto con DivANS.
21. Descripción general de Microsoft DirectStorage.
22. Rhatushnyak, Alejandro; Wassenberg, enero; Sneyers, Jon; Alakuijala, Jyrki; Vandevenne, Lode; Versari, Luca; Obryk, Robert; Szabadka, Zoltan; Kliuchnikov, Evgenii; Comsa, Iulia-Maria; Potempa, Krzysztof; Bruse, Martín; Firsching, Moritz; Khasanova, Renata; Ruud van Asseldonk; Boukortt, Sami; Gómez, Sebastián; Fischbacher, Thomas (2019). "Borrador del comité del sistema de codificación de imágenes JPEG XL". arXiv : 1908.03565 [eess.IV].
23. Explicación de la compresión de datos, Matt Mahoney
24. "Codificación de coeficientes y tokens booleanos mixtos" . Consultado el 14 de junio de 2021 .
25. "Protesta contra Google" (PDF) . Instituto de Física Teórica. Universidad Jagellónica de Cracovia, Polonia . Profesor Jarosław Duda.
26. "Tras el rechazo de la Oficina de Patentes, es hora de que Google abandone su intento de patentar el uso de un algoritmo de dominio público". EFF. 30 de agosto de 2018.
27. "Características de la codificación y decodificación del sistema numérico asimétrico de rangos" . Consultado el 14 de junio de 2021 .
28. "¿La tercera es mala? Microsoft intenta que una patente de compresión rechazada dos veces sea aprobada por examinadores escépticos". The Register . Consultado el 14 de junio de 2021 .
29. "Después de la consideración final, piloto 2.0". Oficina de Patentes y Marcas de los Estados Unidos . Consultado el 14 de junio de 2021 .
30. "Características de la codificación y decodificación del sistema numérico asimétrico de rangos" . Consultado el 16 de febrero de 2022 .

Enlaces externos

• 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