本文是對Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding的翻譯。

目錄

• Abstract
• 1.Introduction
• 2. Basic concepts and versions
• • 2.1 Basic concepts
  • 2.2 Uniform asymmetric binary systems (uABS)
  • 2.3 Range variants (rABS, rANS)
• 3 Stream version - encoding finite-state automaton
• • 3.1 Algorithm
  • 3.2 Example
  • 3.3 Necessary condition and remarks for stream formulas
  • 3.4 Analysis of a single step
  • 3.5 Stationary probability distribution of states
  • 3.6 Bound for ?H
  • 3.7 Initial state and direction of encoding/decoding
• 4 Tabled asymmetric numeral systems (tANS)
• • 4.1 Precise initialization algorithm
  • 4.2 Inaccuracy bound
  • 4.3 Quasi ABS (qABS) and tuning
  • 4.4 Combining tANS with encryption
• 5 Conclusions

Abstract

現代數據壓縮主要基于兩種熵編碼方法：霍夫曼（HC）和算術/范圍編碼（AC）。前者速度更快，但是以2的冪次近似于概率，通常導致較低的壓縮率。后者使用幾乎精確的概率，容易接近理論壓縮率極限（Shannon熵），但以更大的計算成本為代價。

非對稱數字系統(tǒng)（ANS）是一種用于精確熵編碼的新方法，它可以結束速度和速率之間的折衷：對于256個大小的字母，最新的實現方法的解碼速度比HC快50％，壓縮率類似于AC。此優(yōu)勢是因為它比AC更簡單：使用單個自然數作為狀態(tài)，而不是使用兩個自然數來表示范圍。除了簡化重新規(guī)范化之外，它還允許將給定概率分布的整個行為放入一個相對較小的表中：定義熵編碼自動機。對于256個大小的字母，此表的存儲成本為幾千字節(jié)。選擇特定表時有很大的自由度-使用為此目的使用加密密鑰初始化的偽隨機數生成器可以同時加密數據。

本文還介紹和討論了這種新的熵編碼方法的許多其他變體，它們可以為標準AC，大字母范圍編碼（large alphabet range coding）或近似準算術編碼（approximated quasi arithmetic coding）提供直接替代。

1.Introduction

在標準數字系統(tǒng)中，不同的數字被視為包含相同數量的信息：二進制系統(tǒng)中為1位，或者基本b數字系統(tǒng)中通常為$lg(b)$位（$lg\equiv lo{g}_2$）。但是，概率為$p$的事件包含$lg(1/p)$位信息。因此，盡管標準數字系統(tǒng)對于統(tǒng)一的數字概率分布是最佳的，但是為了最佳地編碼通用分布（這是數據壓縮的核心），我們應該嘗試以某種方式使該概念不對稱。我們可以通過這種方式獲得算術/范圍編碼（AC）（[10]，[9]）或最新的不對稱數字系統(tǒng)（ANS）（[2]，[3]），具體取決于我們添加后續(xù)數字的位置。

具體來說，在標準的二進制數字系統(tǒng)中，將信息存儲在自然數$x$（具有m位）中，我們可以通過兩種基本方式添加來自數字$s\in (0,1)$的信息：在最高有效位置$（x\to x+2^{m}s）$或最低有效位置$（x\to 2x+s）$。前者意味著新數字在較大范圍之間進行選擇-我們可以通過更改這些范圍的比例，進行算術/范圍編碼來使其不對稱。但是，在標準數字系統(tǒng)中，我們需要記住該最高有效數字（m）的位置，而AC需要指定給定時刻的范圍-其當前狀態(tài)是代表范圍的兩個數字。

相反，在最不重要的位置添加信息時，當前狀態(tài)只是一個自然數。對于非對稱化來說，這個優(yōu)勢仍然存在：ANS。盡管在標準二進制系統(tǒng)中，x成為對應的偶數（s = 0）或奇數（s = 1）的第x個出現，但是這次我們想將N的這種分裂重新定義為偶數和奇數。這樣它們仍然“均勻分布”，但是具有不同的密度-對應于我們想要編碼的符號概率分布，如圖1所示。

讓我們從信息論的角度來看這兩種方法。對于AC，知道我們當前在給定范圍的一半中就值得1位信息，因此當前內容是lg（范圍大小/子范圍大小）位的信息。在對概率p的符號進行編碼時，子范圍的大小乘以p，從而按預期將信息內容增加$lg(1/p)$位。從ANS的角度來看，看到x包含信息的$lg(x)$位，則信息內容應增加到$lg(x)+lg(1/p)=lg(x/p)$位，同時添加概率$p$的符號。因此，我們需要確保$x\to \approx x/p$過渡關系。直觀地，規(guī)則：如果該子集以$Pr(s)$密度均勻分布，則x成為第s個子集的第x個出現，滿足此關系。

霍夫曼編碼可以看作是一種無記憶編碼器：類型為“符號→位序列”的規(guī)則集。 它將每個符號轉換為自然數位，以1/2的冪來近似其概率。 從理論上講，它可以通過對多個符號進行分組來盡可能接近容量（香農熵）。 但是，我們可以在圖2中看到，這種收斂速度相對較慢：在此處獲得?H≈0.001位/符號將是完全不切實際的。 可以在[11]中找到精確的分析。

讓我們總體上看一下近似概率的代價。 如果我們使用的編碼器可以完美地編碼$(q_s)$個符號分布來編碼$(p_s)$個符號序列，則每個符號平均使用${\sum }_s{p}_{s}lg(1/q_s)$位，而只需要香農熵：${\sum }_s{p}_{s}lg(1/q_s)$。 它們之間的差異稱為Kullback-Leiber距離：

其中稱為不準確度。

因此，要比霍夫曼收斂更好，我們需要更準確的編碼器-我們需要處理小數位數。可以通過向編碼器添加一個包含非整數位數的memory/buffer來完成。編碼器成為有限狀態(tài)自動機，具有

type (symbol, state) → (bit sequence, new state)
類型（符號，狀態(tài)）→（位序列，新狀態(tài)）編碼規(guī)則。

如前所述，當前狀態(tài)在AC情況下包含$lg（范圍大小/子范圍大小）$位，在ANS情況下包含$lg(x)$位。允許這種狀態(tài)包含大量位將要求在AC中以較高的精度進行操作，或者在ANS中以較大的arithmetric進行操作-這是不切實際的。為了防止這種情況，在AC中，我們會定期執(zhí)行重新規(guī)范化：如果子范圍在范圍的一半內，我們可以將單個bit發(fā)送到流（指向該一半），然后將這一半重新縮放到整個范圍。類似地，我們需要在ANS中收集累積的位：將狀態(tài)的某些最低有效位傳輸到流中，以便在對給定符號進行編碼后返回固定范圍$（I=1，..，2l?1）$。與AC相比，此處的位數很容易確定。$I=4,5,6,7$ 的這種基于4狀態(tài)ANS的自動機的示例可以在圖3中看到：雖然1/4概率的符號b總是產生2位信息，但是符號“ a”為3 / 4概率通常通過增加狀態(tài)來累積信息，最終產生完整的信息。解碼時，每個狀態(tài)都知道要使用的位數。

本文介紹并討論了應用ANS方法或其二進制案例的許多變體：非對稱二進制系統(tǒng)（ABS）。它們中的大多數在算術編碼系列中幾乎都有直接的替代方案：

現在將簡要描述這些變體。 ANS方法的最初優(yōu)點是更簡單的重新規(guī)范化(renormalization)。 在AC中，通常需要使用slow branches來提取單個bit，此外，當范圍包含中間點時，還會出現問題。 這些計算上昂貴的問題在ANS中消失了：我們可以從x迅速推斷出要在給定步驟中使用的位數，或者將它們存儲在表中-我們只需要每步一次直接傳輸整個位塊，從而使其速度更快。

uABS代表用于均勻分布符號( uniformly distributing symbols)的直接??算術公式。 rABS代表在范圍內分配符號(distributing symbols in ranges)-導致仍然是直接公式，準確度稍差但計算更簡單。它的主要優(yōu)點是允許使用較大的字母版本：rANS，可以看作范圍編碼的直接替代方法，但有一個小的優(yōu)點：而不是每步2個乘法，它只需要一個即可。我們也可以把uABS的行為變成表格(tables)，得到tABS。它可以像許多AC近似之一一樣類似地應用，例如，現代視頻壓縮中的CABAC [8]中使用的M編碼器。 [7]中提供了tABS（fpaqb）和uABS（fpaqc）的Matt Mahoney實現。
雖然那些非常精確的版本可以很容易地在$?H\approx 0.001bits/symbol$以下的數量級上工作，但qABS類似于準算術編碼[5]近似值：我們希望構建一個小的熵編碼自動機家族，這樣我們就可以涵蓋（二進制）概率分布的整個空間。對于qABS，對于$\Delta H\approx 0.01bits/symbol$丟失，它是5個具有5個狀態(tài)的自動機，對于$\Delta H\approx 0.001bits/symbol$，它是具有16個狀態(tài)的大約20個自動機。
盡管上述可能性可能不會帶來真正的本質優(yōu)勢，但由于狀態(tài)空間要小得多，tabled ANS將大alphbet 的整個行為放入了一個相對較小的編碼表中，這對于AC方法而言可能太過苛刻了。此tANS有可用的交互式演示：[4]。對于ΔH≈0.01位/符號丟失，這種自動機的狀態(tài)數應比字母大小大大約2-4倍，而對于ΔH≈0.001位/符號則大約為8-16倍。對于256個大小的字母，這意味著每個此類編碼表的存儲成本為1-16kB。通常，ΔH隨狀態(tài)數的平方下降：將狀態(tài)數加倍意味著ΔH約小4倍。就像標題中那樣，我們獲得了非常快的熵編碼：最近的Yann Collet實現[1]比Huffman編碼的快速實現具有50％的解碼速度，并且壓縮率幾乎最佳-結合了Huffman和算術編碼的優(yōu)點。
選擇給定參數的編碼表時有很大的自由度：每個符號分布都定義了本質上不同的編碼。我們還將討論此熵編碼器混亂行為的三個原因：不對稱，遍歷和擴散，這使得在沒有完整知識的情況下跟蹤狀態(tài)的任何嘗試都極為困難。這兩個原因建議也將其用于加密應用程序：使用通過加密密鑰初始化的偽隨機數生成器來選擇確切的simbol分配/編碼。這樣，我們就同時獲得了對編碼數據的良好加密。

2. Basic concepts and versions

現在，我們將介紹用于以自然數編碼信息的基本概念，并找到uABS，rABS和rANS情況的解析公式。

2.1 Basic concepts

給定一個字母表$A=0，..，n?1$，并假設概率分布${ps}_{s\in A}$，${\sum }_s{p}_s=1$。此部分的狀態(tài)$x\in N$將包含整個已處理的符號序列。
我們需要找到編碼（C）和解碼（D）函數。 前者取$x\in N$和符號$s\in A$ 的狀態(tài)，并將它們轉換成$x^{\prime }\in N$并存儲它們中的信息。 將x視為從$0,1，..，x?1$間隔中選擇數字的可能性，它包含$lg（x）$bit 信息。 概率$p_s$的符號s包含信息的$lg（1/p_s）$位，因此$x_0$應包含大約$lg（x）+lg（1/p_s）=lg（x/p_s）$信息位：$x_0$應當近似于$x/p_s$，允許從較大的間隔$0,1，..，x_0?1$中選擇一個值。 最后，我們將具有定義單個步驟的函數：
對于標準二進制系統(tǒng)，我們有$C(s，x)=2x+s$，$D（x_0）=（mod（x，2）,x/2)$，我們可以看到s在偶數和奇數之間進行選擇。 如果我們假設x在某個間隔中選擇偶數（或奇數），則$x_0=2x+s$在該間隔中的所有數字之間進行選擇。
對于一般情況，我們將不得不重新定義對應于不同s的子集：像偶數/奇數一樣，它們仍應均勻覆蓋$N$，但是這次具有不同的密度：$\{ps{\}}_{s\in A}$。 我們可以通過符號分布s來定義$N$的這種劃分：$N\to A$

在標準二進制系統(tǒng)中，$x_0$是偶數/奇數的第x個出現，但是這次它將是第s個子集的第x個出現。 因此解碼功能將是

$C(s，x_s)=x$是它的反轉。顯然，我們有$x={\sum }_s{x}_s$。
由于$x/x_s$是我們目前用于編碼符號$s$的位數，為了減少不準確度，因此ΔH，我們希望$x_s\approx x{p}_s$近似值盡可能接近-直觀上意味著符號幾乎與$\{p_s\}$密度獨立分布。現在，我們僅通過取$x1:=[x_p]$就可以找到二進制情況的公式，在第4節(jié)中，我們將集中討論在較大字母的固定間隔上找到這種近似均勻的分布。
最后，我們可以想象x是符號的堆棧，C是push操作，D是pop操作。當前的編碼算法將是： x = 1，然后將C與后續(xù)符號一起使用。這將導致自然數很大，我們可以使用D以相反的順序從中提取所有符號。為防止對大數進行不方便的運算，在下一節(jié)中，我們將討論流版本，在該版本中，將累積的完整位提取為使x保持在固定間隔I中。

2.2 Uniform asymmetric binary systems (uABS)

現在，我們將為二進制情況和幾乎均勻的符號分布找到一些明確的公式：$A=\{0,1\}$。

此公式的起始值和$p=0.3$表示在圖1的右下角。這是通過插入后續(xù)符號進行編碼的示例：

2.3 Range variants (rABS, rANS)

現在，我們將介紹另一種方法，其中將符號外觀放置在范圍內。 它的準確性較差，但執(zhí)行的成本可能較低。 最重要的是，它允許使用較大的字母，從而可以直接替代范圍編碼-這次每個符號使用單個乘法，而不是范圍編碼中需要兩個乘法。 可以將這種方法視為采用標準數字系統(tǒng)并合并其一些后續(xù)數字。
我們將從二進制示例（rABS）開始，然后定義通用公式。
示例：查看$（1,3）/4$概率分布，我們想采用標準的以4為底的數字系統(tǒng)：使用數字0、1、2、3并僅合并其3個數字-假設1、2和3 因此，盡管標準三元系統(tǒng)的符號分布為$s(x)=mod(x,4)$：循環(huán)（0123），但我們將其不對稱化為（0111）循環(huán)分布：

類似地，我們可以為不同的分數定義編碼/解碼功能，這是現在將發(fā)現的大字母公式的特例：rANS。 假設概率分布是以下形式的一部分：$（l_0，l_1，...，l_{n?1}）/m$,其中$l_s\in N，m={\sum }_s{l}_s$。
現在讓我們類似地想象一下，我們從基數m的數字系統(tǒng)開始，然后將對應的后續(xù)數字的數字合并在一起：符號分布是循環(huán)的$（00..011..1...“n?1”）$，且符號s的外觀為$l_s$ 。 讓我們在此循環(huán)中將$s(x)$定義為$x\in [0，..，m?1]$位置中的符號：

如果我們選擇m作為2的冪，則可以通過移位，乘以除以mod（x，m）并使用掩碼進行乘以除法-解碼每步僅需一次乘法。
相反，在范圍編碼中，需要兩個-這種方法應該更快。

3 Stream version - encoding finite-state automaton

3.1 Algorithm

3.2 Example

3.3 Necessary condition and remarks for stream formulas

3.4 Analysis of a single step

3.5 Stationary probability distribution of states

3.6 Bound for ?H

3.7 Initial state and direction of encoding/decoding

4 Tabled asymmetric numeral systems (tANS)

4.1 Precise initialization algorithm

4.2 Inaccuracy bound

4.3 Quasi ABS (qABS) and tuning

4.4 Combining tANS with encryption

5 Conclusions

總結

以上是生活随笔為你收集整理的Asymmetric numeral systems 翻译的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。