香農凡諾演算法舉例

❶ vlc版是什麼意思

VLC（variable-length coding），變長編碼，即編碼時每個符號的碼字長度不一樣。例如經典的霍夫曼編碼（Huffman Coding）、香農-凡諾演算法等。

❷ 無損數據壓縮的無損壓縮編碼技術

最早闡述和實現這種編碼的是Shannon（1948年）和Fano（1949年），因此被稱為香農-范諾（Shannon-Fano）演算法。
這種方法採用從上到下的方法進行編碼。首先按照符號出現的頻度或概率排序，例如，A、B、C、D和E，如表1所示。然後使用遞歸方法分成兩個部分，每一部分具有近似相同的次數。按照這種方法進行編碼得到的總位數為91。壓縮比約為1.3 : 1。
表1 Shannon-Fano演算法舉例表 符號 出現的次數（Pi) log2（1/P) 分配的代碼 需要的位數 A 15 (0.375） 1.4150 00 30 B 7 (0.175） 2.5145 01 14 C 7 (0.175） 2.5145 10 14 D 6 (0.150） 2.7369 110 18 E 5 (0.125） 3.0000 111 15 詞典編碼（dictionary encoding）的根據是數據本身包含有重復代碼這個特性。例如文本文件和光柵圖像就具有這種特性。詞典編碼法的種類很多，歸納起來大致有兩類。
第一類詞典法的想法是企圖查找正在壓縮的字元序列是否在以前輸入的數據中出現過，然後用已經出現過的字元串替代重復的部分，它的輸出僅僅是指向早期出現過的字元串的「指針」。這里所指的「詞典」是指用以前處理過的數據來表示編碼過程中遇到的重復部分。這類編碼中的所有演算法都是以Abraham Lempel和Jakob Ziv在1977年開發和發表的稱為LZ77演算法為基礎的，例如1982年由Storer和Szymanski改進的稱為LZSS演算法就是屬於這種情況。
第二類演算法的想法是企圖從輸入的數據中創建一個「短語詞典（dictionary of the phrases）」，這種短語不一定是像「嚴謹勤奮求實創新」和「國泰民安是坐穩總統寶座的根本」這類具有具體含義的短語，它可以是任意字元的組合。編碼數據過程中當遇到已經在詞典中出現的「短語」時，編碼器就輸出這個詞典中的短語的「索引號」，而不是短語本身。

❸ 算數編碼和香農編碼的區別

摘要 您好，香農(Shannon)編碼是一種常見的可變字長編碼，與哈夫曼編碼相似，當信源符號出現的概率正好為2的負冪次方時，採用香農-范諾編碼同樣能夠達到100%的編碼效率。

❹ 香農范諾編碼原理

霍夫曼
（Huffman）編碼屬於碼詞長度可變的編碼類，是霍夫曼在1952年提出的一種編碼方法，即從下到上的編碼方法。同其他碼詞長度可變的編碼一樣，可區別的不同碼詞的生成是基於不同符號出現的不同概率。生成霍夫曼編碼演算法基於一種稱為「編碼樹」（coding
tree）的技術。演算法步驟如下：
（1）初始化，根據符號概率的大小按由大到小順序對符號進行排序。
（2）把概率最小的兩個符號組成一個新符號（節點），即新符號的概率等於這兩個符號概率之和。
（3）重復第2步，直到形成一個符號為止（樹），其概率最後等於1。
（4）從編碼樹的根開始回溯到原始的符號，並將每一下分枝賦值為1，上分枝賦值為0。
以下這個簡單例子說明了這一過程。
1)．字母A,B,C,D,E已被編碼，相應的出現概率如下：
p(A)=0.16,
p(B)=0.51,
p(C)=0.09,
p(D)=0.13,
p(E)=0.11
2)．C和E概率最小，被排在第一棵
二叉樹
中作為樹葉。它們的根節點CE的組合概率為0.20。從CE到C的一邊被標記為1，從CE到E的一邊被標記為0。這種標記是強制性的。所以，不同的
哈夫曼編碼
可能由相同的數據產生。
3)．各節點相應的概率如下：
p(A)=0.16,
p(B)=0.51,
p(CE)=0.20,
p(D)=0.13
D和A兩個節點的概率最小。這兩個節點作為葉子組合成一棵新的二叉樹。根節點AD的組合概率為0.29。由AD到A的一邊標記為1，由AD到D的一邊標記為0。
如果不同的二叉樹的根節點有相同的概率，那麼具有從根到節點最短的最大路徑的二叉樹應先生成。這樣能保持編碼的長度基本穩定。
4)．剩下節點的概率如下：
p(AD)=0.29,
p(B)=0.51,
p(CE)=0.20
AD和CE兩節點的概率最小。它們生成一棵二叉樹。其根節點ADCE的組合概率為0.49。由ADCE到AD一邊標記為0，由ADCE到CE的一邊標記為1。
5)．剩下兩個節點相應的概率如下：
p(ADCE)=0.49,
p(B)=0.51
它們生成最後一棵根節點為ADCEB的二叉樹。由ADCEB到B的一邊記為1，由ADCEB到ADCE的一邊記為0。
6)．圖03-02-2為霍夫曼編碼。編碼結果被存放在一個表中：
w(A)=001,
w(B)=1,
w(C)=011,
w(D)=000,
w(E)=010
圖03-02-2
霍夫曼編碼例
霍夫曼編碼器的編碼過程可用例子演示和解釋。
下面是另一個霍夫曼編碼例子。假定要編碼的文本是：
"EXAMPLE
OF
HUFFMAN
CODE"
首先，計算文本中符號出現的概率（表03-02-2）。
表03-02-2
符號在文本中出現的概率
符號
概率
E
2/25
X
1/25
A
2/25
M
2/25
P
1/25
L
1/25
O
2/25
F
2/25
H
1/25
U
1/25
C
1/25
D
1/25
I
1/25
N
2/25
G
1/25
空格
3/25
最後得到圖03-02-3所示的編碼樹。
圖03-02-3
霍夫曼編碼樹
在霍夫曼編碼理論的基礎上發展了一些改進的編碼演算法。其中一種稱為自適應霍夫曼編碼（Adaptive
Huffman
code）。這種方案能夠根據符號概率的變化動態地改變碼詞，產生的代碼比原始霍夫曼編碼更有效。另一種稱為擴展的霍夫曼編碼（Extended
Huffman
code）允許編碼符號組而不是單個符號。
同
香農-范諾編碼
一樣，霍夫曼碼的碼長雖然是可變的，但卻不需要另外附加同步代碼。這是因為這兩種方法都自含
同步碼
，在編碼之後的碼串中都不需要另外添加標記符號，即在
解碼
時分割符號的特殊代碼。當然，霍夫曼編碼方法的編碼效率比香農-范諾編碼效率高一些。
採用霍夫曼編碼時有兩個問題值得注意：①霍夫曼碼沒有錯誤保護功能，在解碼時，如果碼串中沒有錯誤，那麼就能一個接一個地正確譯出代碼。但如果碼串中有錯誤，那怕僅僅是1位出現錯誤，也會引起一連串的錯誤，這種現象稱為錯誤傳播(error
propagation)。計算機對這種錯誤也無能為力，說不出錯在哪裡，更談不上去糾正它。②霍夫曼碼是可變長度碼，因此很難隨意查找或調用壓縮文件中間的內容，然後再解碼，這就需要在存儲代碼之前加以考慮。盡管如此，霍夫曼碼還是得到廣泛應用。

❺ 霍夫曼編碼演算法在何時效率最高何時效率最低

霍夫曼(Huffman)編碼是1952年為文本文件而建立，是一種統計編碼。屬於無損壓縮編碼。
霍夫曼編碼的碼長是變化的，對於出現頻率高的信息，編碼的長度較短;而對於出現頻率低的信息，編碼長度較長。這樣，處理全部信息的總碼長一定小於實際信息的符號長度。
霍夫曼計演算法步驟進行：
l)將信號源的符號按照出現概率遞減的順序排列。
2)將兩個最小出現概率進行合並相加，得到的結果作為新符號的出現概率。
3)重復進行步驟1和2直到概率相加的結果等於1為止。
4)在合並運算時，概率大的符號用編碼0表示，概率小的符號用編碼1表示。
5)記錄下概率為1處到當前信號源符號之間的0，l序列，從而得到每個符號的編碼。
霍夫曼計演算法舉例：

霍夫曼優點：
霍夫曼碼的碼長雖然是可變的，但卻自帶同步代碼。例如，碼串中的第1位為0，那末肯定是符號A，因為表示其他符號的代碼沒有一個是以0開始的，因此下一位就表示下一個符號代碼的第1位。同樣，如果出現「110」，那麼它就代表符號D。如果事先編寫出一本解釋各種代碼意義的「詞典」，即碼簿，那麼就可以根據碼簿一個碼一個碼地依次進行解碼。
霍夫曼編碼方法的編碼效率比香農-范諾編碼效率高一些
霍夫曼缺點：
① 霍夫曼碼沒有錯誤保護功能，在解碼時，如果碼串中沒有錯誤，那麼就能一個接一個地正確譯出代碼。但如果碼串中有錯誤，哪僅是1位出現錯誤，不但這個碼本身譯錯，更糟糕的是一錯一大串，全亂了套，這種現象稱為錯誤傳播(error propagation)。計算機對這種錯誤也無能為力，說不出錯在哪裡，更談不上去糾正它。
② 霍夫曼碼是可變長度碼，因此很難隨意查找或調用壓縮文件中間的內容，然後再解碼，這就需要在存儲代碼之前加以考慮。硬體實現有難度。
③ 由於"0"與"1"的指定是任意的，故由上述過程編出的最佳碼不是唯一的，但其平均碼長是一樣的，故不影響編碼效率與數據壓縮性能。
④ 壓縮與還原相當費時。
⑤ 對不同信號源的編碼效率不同