當前位置:成語大全網 - 成語詞典 - 無損數據壓縮的無損壓縮編碼技術

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

最早闡述和實現這種編碼的是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)”,這種短語不壹定是像“嚴謹勤奮求實創新”和“國泰民安是坐穩總統寶座的根本”這類具有具體含義的短語,它可以是任意字符的組合。編碼數據過程中當遇到已經在詞典中出現的“短語”時,編碼器就輸出這個詞典中的短語的“索引號”,而不是短語本身。