Hispanopedia Wiki
Articulo de referencia

Sistemas numéricos asimétricos

Los sistemas numéricos 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...

Hispanopedia WikiContenido en espanolLectura gratuita

Los sistemas numéricos 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 Jaguelónica , utilizados en la compresión de datos desde 2014 [ ‡4 ] debido a su rendimiento mejorado en comparación con métodos anteriores. [ 1 ] 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 coste de procesamiento similar al de la codificación Huffman . [ ‡1 ] En la variante ANS tabulada (tANS), 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. [ ‡2 ]

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

La idea básica es codificar la información en un único número natural.incógnita{\displaystyle x}. [ ‡ 2 ] En el sistema numérico binario estándar, podemos agregar un bits∈{0,1}{\displaystyle s\in \{0,1\}}de información aincógnita{\displaystyle x}adjuntandos{\displaystyle s}al final deincógnita{\displaystyle x}, lo que nos daincógnita′=2incógnita+s{\displaystyle x'=2x+s}Para un codificador de entropía, esto es óptimo siPr(0)=Pr(1)=1/2{\displaystyle \Pr(0)=\Pr(1)=1/2}ANS generaliza este proceso para conjuntos arbitrarios de símbolos.s∈S{\displaystyle s\in S}con una distribución de probabilidad adjunta(pags)s∈S{\displaystyle (p_{s})_{s\in S}}. En ANS, si la información des{\displaystyle s}se adjunta aincógnita{\displaystyle x}para resultar enincógnita′{\displaystyle x'}, entoncesincógnita′≈incógnita⋅pags−1{\displaystyle x'\approx x\cdot p_{s}^{-1}}. De forma equivalente,registro2⁡(incógnita′)≈registro2⁡(incógnita)+registro2⁡(1/pags){\displaystyle \log _{2}(x')\approx \log _{2}(x)+\log _{2}(1/p_{s})}, dónderegistro2⁡(incógnita){\displaystyle \log _{2}(x)}es el número de bits de información almacenados en el númeroincógnita{\displaystyle x}, yregistro2⁡(1/pags){\displaystyle \log _{2}(1/p_{s})}es el número de bits contenidos en el símbolos{\displaystyle s}. [ ‡ 2 ]

Para la regla de codificación, el conjunto de números naturales se divide en subconjuntos disjuntos que corresponden a diferentes símbolos , como en números pares e impares, pero con densidades que corresponden a la distribución de probabilidad de los símbolos a codificar. Luego, para agregar información del símbolo s{\displaystyle s}en la información ya almacenada en el número actualincógnita{\displaystyle x}, vamos al númeroincógnita′=do(incógnita,s)≈incógnita/pag{\displaystyle x'=C(x,s)\approx x/p}siendo la posición de laincógnita{\displaystyle x}-aparición dels{\displaystyle s}-ésimo subconjunto. [ ‡ 2 ]

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). [ ‡ 1 ] La renormalización se utiliza para prevenir incógnita{\displaystyle x}yendo al infinito : transferencia de bits acumulados hacia o desde el flujo de bits. [ ‡ 2 ] 

Codificación de entropía

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

Generalmente, tales secuencias de longitudnorte{\displaystyle n}que contienepagnorte{\displaystyle pn}ceros y(1−pag)norte{\displaystyle (1-p)n}unos, por alguna probabilidadpag∈(0,1){\displaystyle p\in (0,1)}, se denominan combinaciones . Usando la aproximación de Stirling obtenemos su número asintótico siendo

(nortepagnorte)≈2norteh(pag) para grandes norte y h(pag)=−pagregistro2⁡(pag)−(1−pag)registro2⁡(1−pag),{\displaystyle {n \choose pn}\approx 2^{nh(p)}{\text{ para n grande y h(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p),}

llamada entropía de Shannon . [ 20 ]

Por lo tanto, para elegir una de esas secuencias necesitamos aproximadamentenorteh(pag){\displaystyle nh(p)}bits. Todavía lo esnorte{\displaystyle n}bits sipag=1/2{\displaystyle p=1/2}Sin embargo, también puede ser mucho más pequeño. Por ejemplo, solo necesitamos≈norte/2{\displaystyle \approx n/2}piezas parapag=0,11{\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 usarse directamente para enumerar combinaciones: asignar un número natural diferente a cada secuencia de símbolos con proporciones fijas de una manera casi óptima. [ ‡ 2 ]

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.pag{\displaystyle p}contieneregistro2⁡(1/pag){\displaystyle \log _{2}(1/p)}bits de información. ANS codifica la información en un solo número natural.incógnita{\displaystyle x}, interpretado como que contieneregistro2⁡(incógnita){\displaystyle \log _{2}(x)}fragmentos de información. Agregar información a partir de un símbolo de probabilidad.pag{\displaystyle p}aumenta este contenido informativo aregistro2⁡(incógnita)+registro2⁡(1/pag)=registro2⁡(incógnita/pag){\displaystyle \log _{2}(x)+\log _{2}(1/p)=\log _{2}(x/p)}Por lo tanto, el nuevo número que contiene ambas informaciones debe serincógnita′≈incógnita/pag{\displaystyle x'\approx x/p}. [ ‡ 2 ]

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. Entonces, un mensaje se codifica como ABC -> 01011.

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

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

Consideremos una fuente más general con k letras, con probabilidades racionales.norte1/norte,...,nortek/norte{\displaystyle n_{1}/N,...,n_{k}/N}. Entonces, realizar la codificación aritmética en el código fuente solo requiere aritmética exacta con números enteros. [ ‡ 1 ]

En general, ANS es una aproximación de la codificación aritmética que se aproxima a las probabilidades reales.r1,...,rk{\displaystyle r_{1},...,r_{k}}por números racionalesnorte1/norte,...,nortek/norte{\displaystyle n_{1}/N,...,n_{k}/N}con un denominador pequeñonorte{\displaystyle N}. [ ‡ 2 ]

Conceptos básicos de la ANS

Comparación del concepto de codificación aritmética (izquierda) y ANS (derecha). Ambos pueden considerarse generalizaciones de los sistemas numéricos estándar, óptimos para una distribución de probabilidad uniforme de los dígitos, 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 el número natural 18, que es menor que 47, obtenido mediante el sistema binario estándar, debido a una mejor concordancia con las frecuencias de la secuencia a codificar. La ventaja de ANS es que almacena información en un solo número natural, en contraste con los dos que definen un rango.

Imagina que hay alguna información almacenada en un número natural.incógnita{\displaystyle x}, por ejemplo, como la secuencia de bits de su expansión binaria. Para agregar información de una variable binaria.s{\displaystyle s}, podemos usar la función de codificaciónincógnita′=do(incógnita,s)=2incógnita+s{\displaystyle x'=C(x,s)=2x+s}, 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ónD(incógnita′)=(⌊incógnita′/2⌋,metrood(incógnita′,2)){\displaystyle D(x')=(\lfloor x'/2\rfloor ,\mathrm {mod} (x',2))}permite recuperar el anteriorincógnita{\displaystyle x}y este pequeño añadido:D(do(incógnita,s))=(incógnita,s), do(D(incógnita′))=incógnita′{\displaystyle D(C(x,s))=(x,s),\ C(D(x'))=x'}Podemos empezar conincógnita=1{\displaystyle x=1}estado inicial, luego usar eldo{\displaystyle C}función sobre los bits sucesivos de una secuencia finita de bits para obtener un resultado finalincógnita{\displaystyle x}Número que almacena toda esta secuencia. Luego, usando elD{\displaystyle D}funcionar varias veces hastaincógnita=1{\displaystyle x=1}permite recuperar la secuencia de bits en orden inverso. [ ‡ 2 ]

El procedimiento anterior es óptimo para la distribución de probabilidad uniforme (simétrica) de los símbolos.Pr(0)=Pr(1)=1/2{\displaystyle \Pr(0)=\Pr(1)=1/2}ANS lo generaliza para que sea óptimo para cualquier distribución de probabilidad (asimétrica) elegida de los símbolos:Pr(s)=pags{\displaystyle \Pr(s)=p_{s}}. Mientrass{\displaystyle s}En el ejemplo anterior se trataba de elegir entre par e impar.do(incógnita,s){\displaystyle C(x,s)}En ANS, esta división par/impar de los números naturales se reemplaza por una división en subconjuntos cuyas densidades corresponden a la distribución de probabilidad asumida.{pags}s{\displaystyle \{p_{s}\}_{s}}: hasta la posiciónincógnita{\displaystyle x}, hay aproximadamenteincógnitapags{\displaystyle xp_{s}}ocurrencias del símbolos{\displaystyle s}. [ ‡ 2 ]

La función de codificacióndo(incógnita,s){\displaystyle C(x,s)}devuelve elincógnita{\displaystyle x}-ésima aparición de dicho subconjunto correspondiente al símbolos{\displaystyle s}. La suposición de densidad es equivalente a la condiciónincógnita′=do(incógnita,s)≈incógnita/pags{\displaystyle x'=C(x,s)\approx x/p_{s}}Suponiendo que un número naturalincógnita{\displaystyle x}contieneregistro2⁡(incógnita){\displaystyle \log _{2}(x)}fragmentos de información,registro2⁡(do(incógnita,s))≈registro2⁡(incógnita)+registro2⁡(1/pags){\displaystyle \log _{2}(C(x,s))\approx \log _{2}(x)+\log _{2}(1/p_{s})}De ahí el símbolo de probabilidad.pags{\displaystyle p_{s}}está codificado como que contiene≈registro2⁡(1/pags){\displaystyle \approx \log _{2}(1/p_{s})}bits de información según lo requieran los codificadores de entropía . [ ‡ 2 ]

Variantes

Variante binaria uniforme (uABS)

Comencemos con el alfabeto binario y una distribución de probabilidad.Pr(1)=pag{\displaystyle \Pr(1)=p},Pr(0)=1−pag{\displaystyle \Pr(0)=1-p}. Hasta la posiciónincógnita{\displaystyle x}queremos aproximadamentepag⋅incógnita{\displaystyle p\cdot x}análogos de números impares (paras=1{\displaystyle s=1}). Podemos elegir este número de apariciones como⌈incógnita⋅pag⌉{\displaystyle \lceil x\cdot p\rceil }, conseguirs=⌈(incógnita+1)⋅pag⌉−⌈incógnita⋅pag⌉{\displaystyle s=\lceil (x+1)\cdot p\rceil -\lceil x\cdot p\rceil }. Esta variante se llama uABS y da lugar a las siguientes funciones de decodificación y codificación: [ 21 ]

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 new_x = ceil (( x + 1 ) / ( 1 - p )) - 1 // C(x,0) = new_x Si s = 1 , entonces new_x = floor ( x / p ) // C(x,1) = new_x

Parapag=1/2{\displaystyle p=1/2}equivale al sistema binario estándar (con 0 y 1 invertidos), para un propósito diferente.pag{\displaystyle p}se vuelve óptimo para esta distribución de probabilidad dada. [ 21 ] Por ejemplo, parapag=0,3{\displaystyle p=0.3}Estas fórmulas conducen a una tabla para valores pequeños deincógnita{\displaystyle x}:

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

La codificacióndo(incógnita,s){\displaystyle C(x,s)}Se puede encontrar tomando la fila correspondiente a un símbolo dado.s{\displaystyle s}y eligiendo el dadoincógnita{\displaystyle x}en esta fila. Luego la fila superior proporcionado(incógnita,s){\displaystyle C(x,s)}. Por ejemplo,do(7,0)=11{\displaystyle C(7,0)=11}desde la fila del medio hasta la fila superior.

Imaginemos que quisiéramos codificar la secuencia '0100' comenzando desdeincógnita=1{\displaystyle x=1}. Primeros=0{\displaystyle s=0}nos lleva aincógnita=2{\displaystyle x=2}, entoncess=1{\displaystyle s=1}aincógnita=6{\displaystyle x=6}, entoncess=0{\displaystyle s=0}aincógnita=9{\displaystyle x=9}, entoncess=0{\displaystyle s=0}aincógnita=14{\displaystyle x=14}. Utilizando la función de decodificaciónD(incógnita′){\displaystyle D(x')}en esta finalincógnita{\displaystyle x}, podemos recuperar la secuencia de símbolos. Usando la tabla para este propósito,incógnita{\displaystyle x}En la primera fila se determina la columna, luego la fila no vacía y el valor escrito determinan la correspondientes{\displaystyle s}yincógnita{\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. [ ‡ 2 ] Intuitivamente, divide el conjunto de números naturales en rangos de tamaño2norte{\displaystyle 2^{n}}y divide cada uno de ellos de forma idéntica en subrangos con proporciones dadas por la distribución de probabilidad supuesta.

Comenzamos cuantificando la distribución de probabilidad en pasos de2−norte{\displaystyle 2^{-n}}donde se elige n (normalmente de 8 a 12 bits):pags≈F[s]/2norte{\displaystyle p_{s}\approx f[s]/2^{n}}para algunos números naturalesF[s]{\displaystyle f[s]}(tamaños de los subrangos).

Denotarmascarilla=2norte−1{\displaystyle {\text{mask}}=2^{n}-1}y una función de distribución acumulativa:

CDF⁡[s]=∑i<sF[i]=F[0]+⋯+F[s−1].{\displaystyle \operatorname {CDF} [s]=\sum _{i<s}f[i]=f[0]+\cdots +f[s-1].}

Nótese que la función no es una verdadera función de distribución acumulada (CDF) , ya que la probabilidad del símbolo actual no se incluye 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 , puesto que no hay símbolos anteriores.CDF[s]CDF[s]CDF[0]=f[0]CDF[0]=0

Paray∈[0,2norte−1]{\displaystyle y\in [0,2^{n}-1]}denota la función (generalmente tabulada)

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

Ahora la función de codificación es:

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

Descodificación:

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

De esta forma podemos codificar una secuencia de símbolos en un número natural grande x . Para evitar el uso de aritmética de números grandes, en la práctica se utilizan variantes de flujo que imponenincógnita∈[L,b⋅L−1]{\displaystyle x\in [L,b\cdot L-1]}por renormalización: Enviar los bits menos significativos de x hacia o desde el flujo de bits (generalmente L y b son potencias de 2). [ ‡ 2 ]

En la variante rANS, x podría ser un entero de 32 bits, por ejemplo. Para la renormalización de 16 bits (incógnita∈[216,232−1]{\displaystyle x\in [2^{16},2^{32}-1]}), el decodificador rellena los bits menos significativos del flujo de bits cuando es necesario:

if ( x < ( 1 << 16 )) { x = ( x << 16 ) + read16bits () }

Variante tabulada (tANS)

Ejemplo sencillo de un autómata ANS de 4 estados para una 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, por lo que siempre produce dos bits. En cambio, el símbolo a contiene −lg(3/4) ~ 0,415 bits de información, por lo que a veces produce un bit (desde los estados 6 y 7), a veces 0 bits (desde los estados 4 y 5), incrementando únicamente el estado, que actúa como un búfer que contiene un número fraccional 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 directamente los bytes).     

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

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 ; // número de bits para la renormalización writeBits ( x , nbBits ); // enviar 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[L,2L−1]{\displaystyle [L,2L-1]}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 son 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ímbolos "aaaabcdd". [ ‡ 1 ]

Ejemplo de generación de tablas tANS para un alfabeto de tamaño m = 3 y L = 16 estados, y su posterior aplicación para la decodificación de flujo. Primero, aproximamos las probabilidades usando fracciones con denominador igual al 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. A continuación, enumeramos las apariciones comenzando con el valor que representa su cantidad para un símbolo dado. Finalmente, rellenamos los bits más jóvenes del flujo para volver al rango supuesto 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, generalmente con algún esquema de Lempel-Ziv (por ejemplo, ZSTD, [ 2 ] LZFSE [ 9 ] ). 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, luego, después de la aproximación (cuantización), se escriben en el encabezado del bloque y se utilizan como distribución de probabilidad estática para tANS. [ ‡ 1 ] 

En contraste, rANS se usa generalmente como un reemplazo más rápido para la codificación de rango (por ejemplo, CRAM , [ 13 ] LZNA, Draco [ 10 ] ). Requiere multiplicación, pero es más eficiente en memoria y es apropiado para adaptar dinámicamente las distribuciones de probabilidad. [ ‡2 ]

La codificación y decodificación de ANS se realizan en direcciones opuestas, lo que la convierte en una pila de símbolos. Este inconveniente suele resolverse codificando en sentido inverso, tras lo cual se puede decodificar en sentido directo. [ ‡ 2 ] Para la dependencia del contexto, como en el modelo de Markov , el codificador necesita utilizar el contexto desde la perspectiva de la decodificación posterior. Para la adaptabilidad, el codificador debe primero avanzar para encontrar las probabilidades que utilizará (predichará) el decodificador y almacenarlas en un búfer, luego codificar en sentido inverso utilizando las probabilidades almacenadas en el búfer. [ ‡ 2 ]

El estado final de la codificación es necesario para comenzar la decodificación, por lo que debe almacenarse en el archivo comprimido. Este costo puede compensarse 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 bits adicionales almacenados que pueden recuperarse al final de la decodificación. Alternativamente, este estado puede usarse como una suma de verificación, comenzando la codificación con un estado fijo y comprobando si el estado final de la decodificación es el esperado. [ ‡ 2 ]

Controversia sobre patentes

El autor del novedoso algoritmo ANS y sus variantes tANS y rANS pretendía específicamente que su trabajo estuviera disponible gratuitamente en el dominio público, por razones altruistas. No ha buscado lucrarse con ellos y tomó medidas para asegurar que no se convirtieran en un "campo minado legal", ni que otros los restringieran o se beneficiaran de ellos. [ 1 ] En 2015, Google publicó una patente en EE. UU. y luego a nivel mundial para "Codificación de coeficientes ans booleanos mixtos". [ 22 ] En ese momento, Google le había pedido al profesor Duda que les ayudara con la compresión de video, por lo que estaba íntimamente familiarizado con este campo, ya que el autor original les estaba ayudando.

Duda no quedó satisfecho al descubrir (accidentalmente) las intenciones de Google respecto a la patente, dado que había dejado claro que quería que fuera de dominio público y había ayudado a Google específicamente con ese propósito. [ 1 ] Posteriormente, Duda presentó una solicitud de terceros [ ‡ 5 ] ante la Oficina de Patentes de los Estados Unidos para solicitar su rechazo. La USPTO rechazó su solicitud en 2018, y Google posteriormente abandonó la patente. [ 23 ]

En junio de 2019, Microsoft presentó una solicitud de patente titulada "Características de codificación y decodificación de sistemas de números asimétricos de rango". [ 24 ] La USPTO emitió un rechazo final de la solicitud el 27 de octubre de 2020. [ 24 ] Sin embargo, el 2 de marzo de 2021, Microsoft presentó una declaración explicativa ante la USPTO indicando "El solicitante discrepa respetuosamente con los rechazos", [ 25 ] buscando revocar el rechazo final bajo el programa "After Final Consideration Pilot 2.0". [ 26 ] Después de la reconsideración, la USPTO otorgó la solicitud el 25 de enero de 2022. [ 24 ]

Véase también

Referencias

  1. 1 2 3 "Google, acusado de intentar patentar tecnología de dominio público" . Bleeping Computer . 11 de septiembre de 2017.
  2. 1 2 Compresión de datos más pequeña y rápida con Zstandard , Facebook, agosto de 2016.
  3. ↑ 5 maneras en que Facebook mejoró la compresión a gran escala con Zstandard , Facebook, diciembre de 2018.
  4. ↑ Zstd Compression For Btrfs & Squashfs Set For Linux 4.14, Already Used Within Facebook , Phoronix, septiembre de 2017.
  5. ↑ Novedad en Chrome 123 (Content-Encoding) , Google, marzo de 2024.
  6. ↑ "Zstd en la versión de Android P" . Archivado del original el 26 de agosto de 2020. Consultado el 29 de mayo de 2019 .
  7. ↑ Compresión Zstandard y el tipo de medio application/zstd (estándar de correo electrónico) .
  8. ↑ Parámetros del Protocolo de Transferencia de Hipertexto (HTTP) , IANA .
  9. 1 2 Apple publica el código fuente de su nuevo algoritmo de compresión LZFSE , InfoQ, julio de 2016.
  10. 1 2 Biblioteca de compresión 3D Google Draco .
  11. ↑ Google y Pixar añaden la compresión Draco al formato de descripción de escena universal (USD) .
  12. ↑ Google PIK: nuevo formato de imagen con pérdida para internet .
  13. 1 2 Especificación del formato CRAM (versión 3.0) .
  14. ↑ Chen W, Elliott LT (2021). "Compresión de datos genéticos poblacionales mediante entropía de estado finito" . J Bioinform Comput Biol . 19 (5) 2150026. doi : 10.1142/S0219720021500268 . PMID 34590992 . 
  15. ↑ Compresión de datos de alta velocidad mediante GPU NVIDIA .
  16. ↑ Mejorando la compresión junto con DivANS .
  17. ↑ Información general de Microsoft DirectStorage .
  18. ^ 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 ].
  19. ↑ Esenlik, Semih; Zhang, Kai; Ascenso, João (2025). "Una descripción general del estándar de codificación de imágenes basado en el aprendizaje JPEG AI". arXiv : 2510.13867 [ eess.IV ].
  20. ↑ Cover, Thomas M.; Thomas, Joy A. (2006). Elementos de la teoría de la información (2.ª ed.). Wiley. págs. 13–14 . ISBN   978-0-471-24195-9.
  21. 1 2 Explicación de la compresión de datos , Matt Mahoney
  22. ↑ "Codificación mixta de tokens booleanos y coeficientes" . Consultado el 14 de junio de 2021 .
  23. ↑ Nazer, Daniel (30 de agosto de 2018). "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" . Electronic Frontier Foundation .
  24. 1 2 3 "Características de la codificación y decodificación del sistema de numeración asimétrico de rango" . Consultado el 14 de junio de 2021 .
  25. ↑ Claburn, Thomas (13 de marzo de 2021). "¿A la tercera va la vencida? Microsoft intenta que su patente de compresión, rechazada dos veces, sea aprobada por examinadores escépticos" . The Register . Consultado el 14 de junio de 2021 .
  26. ↑ "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 .

Fuentes primarias

En el texto, estas referencias van precedidas de una doble daga (‡):

  1. 1 2 3 4 5 6 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. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 J. Duda, Sistemas numéricos 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" . Recuperado el 6 de octubre de 2019 .
  5. ↑ "Protesta a Google" (PDF) . Instituto de Física Teórica. Universidad Jaguelónica de Cracovia, Polonia . Profesor Jarosław Duda.
  • Duda, Jarek (2 de noviembre de 2008). "Codificación óptima en retículo discreto con restricciones invariantes traslacionales utilizando algoritmos estadísticos". arXiv : 0710.3861 [ cs.IT ]., posiblemente la primera mención de ANS
  • 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
  • Codificadores de entropía de nueva generación Implementación de entropía de estado finito (FSE) de tANS por Yann Collet
  • rygorous/ryg_rans 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
  • Compresor de ADN CRAM 3.0 (rANS de orden 1) (parte de SAMtools ) del Instituto Europeo de Bioinformática.
  • Implementación para Google VP10
  • Implementación para Google WebP
  • Biblioteca de compresión 3D Draco de Google
  • aom_dsp - aom - Implementación de Git en Google de Alliance for Open Media
  • Compresión de datos mediante sistemas numéricos asimétricos - Proyecto de demostraciones de Wolfram
  • GST: Texturas supercomprimidas decodificables por GPU GST: Texturas supercomprimidas decodificables por GPU
  • Comprender la compresión (libro de A. Haecky y C. McAnlis)