無損數據壓縮

無損數據壓縮

無損數據壓縮（Lossless Data Compression）是指使用壓縮後的數據進行重構（或者叫做還原、解壓縮），重構後的數據與原來的數據完全相同，但通常壓縮比小於有損數據壓縮的壓縮比

基本介紹

  • 中文名：無損數據壓縮
  • 外文名：Lossless Data Compression
  • 相對：有損數據壓縮
  • 特點：壓縮比小於有損數據壓縮的壓縮比
  • 壓縮程度：原檔案的1/2～1/4
  • 套用學科：通信工程、計算機科學、控制科學
定義與特點,編碼技術,香農-范諾編碼,霍夫曼編碼,算術編碼,RLE編碼,詞典編碼,常見格式,

定義與特點

無損壓縮用於要求重構的信號與原始信號完全一致的場合。也就是說數據經過壓縮後信息不受損失，還能完全恢復到壓縮前的原樣。它和有損數據壓縮相對。這種壓縮通常壓縮比小於有損數據壓縮的壓縮比。
一個很常見的例子是磁碟檔案的壓縮。根據目前的技術水平，無損壓縮算法一般可以把普通檔案的數據壓縮到原來的1/2～1/4。一些常用的無損壓縮算法有霍夫曼（Huffman）算法和LZW(Lenpel-Ziv & Welch）壓縮算法。

編碼技術

香農-范諾編碼

最早闡述和實現這種編碼的是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

霍夫曼編碼

霍夫曼（Huffman)在1952年提出了另一種編碼方法，即從下到上的編碼方法。現仍以一個具體的例子說明它的編碼步驟：
  1. 初始化，根據符號機率的大小按由大到小順序對符號進行排序。
  2. 把機率最小的兩個符號組成一個節點，如D和E組成節點P1。
  3. 重複步驟2，得到節點P2、P3和P4，形成一棵“樹”，其中的P4稱為根節點。
  4. 從根節點P4開始到相應於每個符號的“樹葉”，從上到下標上“0”（上枝）或者“1”（下枝），至於哪個為“1”哪個為“0”則無關緊要，最後的結果僅僅是分配的代碼不同，而代碼的平均長度是相同的。
  5. 從根節點P4開始順著樹枝到每個葉子分別寫出每個符號的代碼，如表2所示。
    表2 霍夫曼編碼舉例
符號
出現的次數
log2（1/pi)
分配的代碼
需要的位數
A
15(0.3846）
1.38
0
15
B
7(0.1795）
2.48
100
21
C
6(0.1538）
2.70
101
18
D
6(0.1538）
2.70
110
18
E
5(0.1282）
2.96
111
15
霍夫曼碼的碼長雖然是可變的，但卻不需要另外附加同步代碼。例如，碼串中的第1位為0，那肯定是符號A，因為表示其他符號的代碼沒有一個是以0開始的，因此下一位就表示下一個符號代碼的第1位。同樣，如果出現“110”，那么它就代表符號D。如果事先編寫出一本解釋各種代碼意義的“詞典”，即碼簿，那么就可以根據碼簿逐個碼進行解碼。

算術編碼

算術編碼在圖像數據壓縮標準（如JPEG、JBIG）中扮演了重要的角色。在算術編碼中，訊息用0到1之間的實數進行編碼，算術編碼用到兩個基本的參數：符號的機率和它的編碼間隔。信源符號的機率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在0到1之間。編碼過程中的間隔決定了符號壓縮後的輸出。

RLE編碼

現實中有許多這樣的圖像，在一幅圖像中具有許多顏色相同的圖塊。在這些圖塊中，許多行上都具有相同的顏色，或者在一行上有許多連續的象素都具有相同的顏色值。在這種情況下就不需要存儲每一個象素的顏色值，而僅僅存儲一個象素的顏色值，以及具有相同顏色的象素數目就可以，或者存儲一個象素的顏色值，以及具有相同顏色值的行數。這種壓縮編碼稱為行程編碼，常用（run length encoding，RLE）表示，具有相同顏色並且是連續的象素數目稱為行程長度。

詞典編碼

詞典編碼（dictionary encoding）的根據是數據本身包含有重複代碼這個特性。例如文本檔案和光柵圖像就具有這種特性。詞典編碼法的種類很多，歸納起來大致有兩類。
第一類詞典法的想法是企圖查找正在壓縮的字元序列是否在以前輸入的數據中出現過，然後用已經出現過的字元串替代重複的部分，它的輸出僅僅是指向早期出現過的字元串的“指針”。這裡所指的“詞典”是指用以前處理過的數據來表示編碼過程中遇到的重複部分。這類編碼中的所有算法都是以Abraham Lempel和Jakob Ziv在1977年開發和發表的稱為LZ77算法為基礎的，例如1982年由Storer和Szymanski改進的稱為LZSS算法就是屬於這種情況。
第二類算法的想法是企圖從輸入的數據中創建一個“短語詞典（dictionary of the phrases）”，這種短語不一定是像“嚴謹勤奮求實創新”和“國泰民安是坐穩總統寶座的根本”這類具有具體含義的短語，它可以是任意字元的組合。編碼數據過程中當遇到已經在詞典中出現的“短語”時，編碼器就輸出這個詞典中的短語的“索引號”，而不是短語本身。

常見格式

圖片格式
  • Gif
  • PNG
  • TIFF
音頻格式
  • Ape
  • Flac
  • TTA
  • WV
視頻格式
  • Huffyuv

相關詞條

熱門詞條

聯絡我們