Los sistemas numéricos asimétricos ( ANS ) [1] son una familia de métodos de codificación de entropía introducidos por Jarosław (Jarek) Duda [2] de la Universidad Jagiellonian , utilizados en la compresión de datos desde 2014 [3] debido a un rendimiento mejorado en comparación con los métodos utilizados anteriormente, siendo hasta 30 veces más rápido. [4] 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 (tANS) en tabla, esto se logra mediante la construcción de una máquina de estados finitos para operar en un alfabeto grande sin utilizar la multiplicación.
Entre otros, ANS se usa en el compresor Zstandard de Facebook [5] [6] (también se usa, por ejemplo, en el kernel de Linux , [7] el sistema operativo Android [8] , se publicó como RFC 8478 para MIME [9] y HTTP [10] ), en el compresor Apple LZFSE , [11] el compresor Google Draco 3D [12] (utilizado, por ejemplo, en el formato de descripción de escena universal de Pixar [13] ) y el compresor de imagen PIK, [14] en el compresor CRAM DNA [15] de las utilidades SAMtools , Compresor Dropbox DivANS, [16] y en JPEG XL [17] estándar de compresión de imagen de próxima generación.
La idea básica es codificar la información en un solo número natural. . En el sistema numérico binario estándar, podemos agregar un poco de información a agregando al final de 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 es el resultado de adjuntar la información de a , luego . Equivalentemente,, dónde 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 .
Para la regla de codificación, el conjunto de números naturales se divide en subconjuntos disjuntos correspondientes 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 en la información ya almacenada en el número actual , vamos al numero siendo la posición del -a aparición de la -th subconjunto.
Hay 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 prevenir yendo al infinito - transfiriendo bits acumulados hacia o desde el flujo de bits.
Codificación de entropía
Suponga que se codificaría una secuencia de 1000 ceros y unos, lo que requeriría 1000 bits para almacenar 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, que requiere solo bits aquí en lugar de los 1000 bits originales.
Generalmente, tal longitud secuencias que contienen ceros y unos, por alguna probabilidad , se llaman combinaciones . Usando la aproximación de Stirling obtenemos que su número asintótico es
llamada entropía de Shannon .
Por lo tanto, para elegir una de esas secuencias necesitamos aproximadamente bits. Aún es bits si sin embargo, también puede ser mucho más pequeño. Por ejemplo, solo necesitamos bits para .
Un codificador de entropía permite la codificación de una secuencia de símbolos utilizando aproximadamente los bits de entropía de Shannon por símbolo. Por ejemplo, ANS podría usarse directamente para enumerar combinaciones: asigne 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, interpretado como conteniendo 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 debe ser.
Conceptos básicos de ANS
Imagina que hay información almacenada en un número natural. , por ejemplo, como 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 función de decodificación permite recuperar el anterior y este poco añadido: . Podemos empezar con estado inicial, luego use el función en los sucesivos bits de una secuencia de bits finita para obtener un final número que almacena esta secuencia completa. Luego usando funcionar varias veces hasta permite recuperar la secuencia de bits en orden inverso.
El procedimiento anterior es óptimo para la distribución de probabilidad uniforme (simétrica) de símbolos . ANS lo generaliza para que sea óptimo para cualquier distribución de probabilidad de símbolos elegida (asimétrica):. Tiempo en el ejemplo anterior estaba eligiendo 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 apariciones de símbolo .
La función de codificación devuelve el -ésima aparición de dicho subconjunto correspondiente al símbolo . El supuesto de densidad es equivalente a la condición. Suponiendo que un número natural contiene bits de información, . De ahí el símbolo de probabilidad está codificado como conteniendo bits de información que se requieren de los codificadores de entropía .
Variante binaria uniforme (uABS)
Comencemos con el alfabeto binario y una distribución de probabilidad. , . Hasta la posición queremos aproximadamente análogos de números impares (por ). Podemos elegir este número de apariciones como, obtener . Esta variante se llama uABS y conduce a las siguientes funciones de decodificación y codificación: [18]
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) = (nueva_matriz_x, 0), este es el mismo que nueva_matriz_x = floor (x * (1-p)) si s = 1 entonces nueva_matriz_x = ceil ( x * p ) // D (x) = (nuevo_x, 1)
Codificación:
si s = 0 entonces nueva_matriz_x = ceil (( x + 1 ) / ( 1 - p )) - 1 // C (x, 0) = nueva_matriz_x si s = 1 entonces nueva_matriz_x = piso ( x / p ) // C ( x, 1) = nuevo_x
Para equivale al sistema binario estándar (con 0 y 1 invertidos), para un se vuelve óptimo para esta distribución de probabilidad dada. Por ejemplo, para estas fórmulas conducen a una tabla para valores pequeños de :
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | dieciséis | 17 | 18 | 19 | 20 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ||||||||
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 posiciones . Como, estas posiciones aumentan en 3 o 4. Porque aquí, el patrón de símbolos se repite cada 10 posiciones.
La codificación se puede encontrar tomando la fila correspondiente a un símbolo dado , y eligiendo el dado en esta fila. Entonces la fila superior proporciona. Por ejemplo, de la fila media a la superior.
Imagine que nos gustaría codificar la secuencia '0100' a partir de . Primero nos lleva a , luego a , luego a , luego a . Utilizando la función de decodificación en esta final , podemos recuperar la secuencia de símbolos. Usando 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 correspondiente y .
Variantes de rango (rANS) y transmisión
La variante de rango también usa fórmulas aritméticas, pero permite la operación en un alfabeto grande. Intuitivamente, divide el conjunto de números naturales en tamaño. rangos, y dividir cada uno de ellos de manera idéntica en subrangos de proporciones dadas por la distribución de probabilidad supuesta.
Comenzamos con la cuantificación de la distribución de probabilidad para denominador, donde se elige n (generalmente 8-12 bits): para algo natural números (tamaños de subintervalos).
Denotar , función de distribución acumulativa:
Para denotar función (generalmente en tabla)
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 imponenpor renormalización: el envío de los bits menos significativos de x desde o hacia el flujo de bits (por lo general L y b son potencias de 2).
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 sea necesario:
si ( x < ( 1 << 16 )) x = ( x << 16 ) + read16bits ()
Variante de tabla (tANS)
La variante tANS coloca el comportamiento completo (incluida la renormalización) para en una tabla que produce una máquina de estados finitos que evita la necesidad de multiplicar.
Finalmente, el paso del ciclo de decodificación se puede escribir como:
t = decodingTable ( x ); x = t . newX + readBits ( t . nbBits ); // estado de transición writeSymbol ( t . símbolo ); // símbolo decodificado
El paso del ciclo de codificación:
s = ReadSymbol (); nbBits = ( x + ns [ s ]) >> r ; // # de bits para la 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 Pr (a) = 3/8, Pr (b) = 1/8, Pr (c) = 2/8, Pr (d) = 2/8 distribución de probabilidad. Si los símbolos se asignan en rangos de longitudes que sean potencias de 2, obtendríamos la codificación de Huffman . Por ejemplo, un código de prefijo a-> 0, b-> 100, c-> 101, d-> 11 se obtendría para tANS con la asignación de símbolo "aaaabcdd".
Observaciones
En cuanto a la codificación de Huffman, modificar la distribución de probabilidad de tANS es relativamente costoso, por lo que se usa principalmente en situaciones estáticas, generalmente 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 símbolo se cuentan de forma independiente, luego, después de la aproximación (cuantificación), se escribe en el encabezado del bloque y se utiliza como distribución de probabilidad estática para tANS.
Por el contrario, rANS se usa generalmente como un reemplazo más rápido para la codificación de rango (por ejemplo , CRAM , LZNA, Draco, [12] AV1 ). Requiere multiplicación, pero es más eficiente en memoria y es apropiado para adaptar dinámicamente 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 hacia atrás, después de lo cual la decodificación se puede hacer hacia adelante. Para la dependencia del contexto, como el modelo de Markov , el codificador necesita usar el contexto desde la perspectiva de la decodificación posterior. Para la adaptabilidad, el codificador debe avanzar primero para encontrar probabilidades que serán utilizadas (predichas) por el decodificador y almacenarlas en un búfer, luego codificar en dirección hacia atrás usando las probabilidades almacenadas en búfer.
Se requiere el estado final de codificación para comenzar a decodificar, por lo tanto, 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 adicionales almacenados, 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.
Ver 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
- ^ 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.
- ^ http://th.if.uj.edu.pl/~dudaj/
- ^ Duda, Jarek (6 de octubre de 2019). "Listado de compresores que utilizan ANS, implementaciones y otros materiales" . Consultado el 6 de octubre de 2019 .
- ^ "Google acusado de intentar patentar tecnología de dominio público" . Ordenador que suena . 11 de septiembre de 2017.
- ^ Compresión de datos más pequeña y rápida con Zstandard , Facebook, agosto de 2016
- ^ 5 formas en que Facebook mejoró la compresión a escala con Zstandard , Facebook, diciembre de 2018
- ^ Compresión Zstd para Btrfs y Squashfs configurado para Linux 4.14, ya utilizado en Facebook , Phoronix, septiembre de 2017
- ^ "Lanzamiento de Zstd en Android P" .
- ^ Zstandard Compression y la aplicación / zstd Media Type (estándar de correo electrónico)
- ^ Parámetros del Protocolo de transferencia de hipertexto (HTTP) , IANA
- ^ Fuentes abiertas de Apple su nuevo algoritmo de compresión LZFSE , InfoQ, julio de 2016
- ^ a b Biblioteca de compresión Google Draco 3D
- ^ Google y Pixar agregan Draco Compression al formato de descripción de escena universal (USD)
- ^ Google PIK: nuevo formato de imagen con pérdida para Internet
- ^ Especificación de formato CRAM (versión 3.0)
- ^ Construyendo una mejor compresión junto con DivANS
- ^ Rhatushnyak, Alexander; Wassenberg, Jan; Sneyers, Jon; Alakuijala, Jyrki; Vandevenne, Lode; Versari, Luca; Obryk, Robert; Szabadka, Zoltan; Kliuchnikov, Evgenii; Comsa, Iulia-Maria; Potempa, Krzysztof; Bruse, Martin; 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 ].
- ^ Explicación de la compresión de datos , Matt Mahoney
enlaces externos
- Arquitecturas de hardware de alto rendimiento para codificación de entropía de sistemas numéricos asimétricos SM Najmabadi, Z. Wang, Y. Baroud, S. Simon, ISPA 2015
- https://github.com/Cyan4973/FiniteStateEntropy Implementación de entropía de estado finito (FSE) de tANS por Yann Collet
- https://github.com/rygorous/ryg_rans Implementación de rANS por Fabian Giesen
- https://github.com/jkbonfield/rans_static Implementación rápida de rANS y codificación aritmética por James K. Bonfield
- https://github.com/facebook/zstd/ Compresor Zstandard de Facebook de Yann Collet (autor de LZ4 )
- https://github.com/lzfse/lzfse Compresor LZFSE (LZ + FSE) de Apple Inc.
- Compresor de ADN CRAM 3.0 (orden 1 rANS) (parte de SAMtools ) por el Instituto Europeo de Bioinformática
- https://chromium-review.googlesource.com/#/c/318743 implementación para Google VP10
- https://chromium-review.googlesource.com/#/c/338781/ implementación para Google WebP
- https://github.com/google/draco/tree/master/core Biblioteca de compresión Google Draco 3D
- https://aomedia.googlesource.com/aom/+/master/aom_dsp implementación de Alliance for Open Media
- http://demonstrations.wolfram.com/DataCompressionUsingAsymmetricNumeralSystems/ Proyecto de demostraciones Wolfram
- http://gamma.cs.unc.edu/GST/ GST: Texturas supercomprimidas decodificables por GPU
- Comprensión del libro de compresión por A. Haecky, C. McAnlis