從基數256轉換爲多基數並返回的算法

Question

我有一個字節數據流，也稱爲基數256個符號。什麼是最好的算法，在理想情況下將其轉換爲新的符號流，每個符號的基數變化並且只在運行時才知道？輸入字節流和目標基數列表的長度都很長但是有限。所有非負整數，無浮點。此外，目標基數不能保證均勻分配或是256的倍數。

Answer 1

您的問題是算術編碼的一個子集，它被用作許多壓縮算法的最後一個階段。這是最酷的事情在CS學習一種：

http://www.drdobbs.com/cpp/data-compression-with-arithmetic-encodin/240169251 https://en.wikipedia.org/wiki/Arithmetic_coding

如何您的問題具體涉及：

你想要的編碼器是算術解碼器，併爲每個解碼您將使用一個不同大小的字母表（基數），所有符號的概率相同。

編碼器的主循環會做這樣的事情：

int val=0; //information from the stream 
int range=1; //val is in [0,range) 
while(...) 
{ 
    int radix = next_radix(); 
    //ensure adequate efficiency 
    while(range < radix*256) 
    { 
     val = (val<<8)|(next_byte()&255); 
     range<<=8; 
    } 
    int output = (int)(radix*(long)val/range); 
    //find the smallest possible val that produces this output 
    int low = (int)((output*(long)range+radix-1)/radix); 
    //find the smallest possible val that produces the next output 
    int high = (int)(((output+1)*(long)range+radix-1)/radix); 
    val-=low; 
    range = high-low; 
    write(output); 
} 

沒有與處理終止的條件和處理在您的解碼器進行（算術編碼器）的併發症，所以你必須閱讀文學，從我鏈接的東西開始。儘管如此，我希望這能夠讓你瞭解它的工作原理。

好運