無失真資料壓縮之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：13

、訪客IP：18.219.22.169

姓名

呂智文(Steve Lu) 查詢紙本館藏

畢業系所

電機工程學系

論文名稱

無失真資料壓縮之研究
(The Research of Lossless Data Compression)

相關論文

★ 資料儲存系統之渦輪碼與訊號處理研究	★ 插值時序恢復之研究與應用
★ 資料儲存系統之通道研究	★ 全數位化π/4-shifted DQPSK 之分析與實現
★ 校園多媒體無線通訊系統通道編∕解碼器之研究	★ 資料儲存系統之調變碼研究
★ 利用紅外線傳輸動態影像(H.263)之研究	★ 數位式上昇餘弦函數濾波器最佳化設計
★ 資料儲存PRML通道系統之全數位插值時序恢復研究及設計	★ IrTran-P環境下之JPEG影像錯誤偵測與改善
★ FIR濾波器於二冪次係數空間之研究與分析	★ 影像縮放之插值器研究
★ 動態影像在紅外線中傳輸與錯誤消除技術之研究	★ 紅外線協定控制器之研究與設計
★ 空時碼系統之研究	★ 正交分頻多重接取通訊系統之資源配置演算法設計

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

無失真資料壓縮在通訊工程的應用上使用的十分廣泛，且由於演算法的種類繁多，在實際應用上必須根據資料的特性以及硬體的特性而去做演算法的選擇，在這篇論文裡探討了各個演算法的特性，並針對Vitter的動態霍夫曼編碼的架構做個改良，再以複合式演算法的概念且對各個演算法的特性做合併的動作，並和公用演算法zip比較，最後則針對資料的特性先做分類區塊並同時進行壓縮，對於壓縮率的影響。

關鍵字(中)

★ 資料壓縮

關鍵字(英)

★ lossless data compression

論文目次

第一章緒論……………………………………………………………………1
1.1 研究目的…………………………………………………………………………1
1.2 研究動機…………………………………………………………………………1
1.3 章節介紹…………………………………………………………………………2
第二章無失真資料壓縮演算法介紹…………………………………………3
2.1 各式演算法簡介………………………………………………………………3
2.2 無失真壓縮演算法－統計模式………………………………………………3
2.2.1 動態霍夫曼編碼……………………………………………………………5
2.2.2 動態馬可夫鏈編碼………………………………………………………18
2.3 動態霍夫曼編碼(滑動視窗型)………………………………………………27
2.4 無失真壓縮演算法－字典基礎模式…………………………………………35
2.4.1 LZ77壓縮法則……………………………………………………………36
2.4.2 LZSS壓縮法則……………………………………………………………39
2.4.3 LZW 壓縮法則……………………………………………………………43
2.5 各個演算法效能比較…………………………………………………………47
第三章複合式壓縮演算法……………………………………………………49
3.1 混合式演算法簡介……………………………………………………………49
3.1.1 ZIP壓縮法則………………………………………………………………50
3.1.2 Deflate 壓縮格式…………………………………………………………51
3.1.2.1壓縮演算法…………………………………………………………51
3.1.2.2霍夫曼編碼…………………………………………………………52
3.1.2.3區塊格式……………………………………………………………55
3.2 複合式壓縮演算法……………………………………………………………61
3.2.1 LZSS+動態霍夫曼編碼……………………………………………………62
3.2.2 LZSS+動態馬可夫鏈編碼…………………………………………………67
3.2.3 LZW +動態霍夫曼編碼……………………………………………………70
3.3 結論……………………………………………………………………………77
第四章預先分割資料處理器於資料壓縮的影響……………………………79
4.1 簡介……………………………………………………………………………79
4.2 檔案格式………………………………………………………………………80
4.2.1 編解碼過程…………………………………………………………………81
4.3 壓縮結果………………………………………………………………………84
第五章結論…………………………………………………………………88
參考文獻 ………………………………………………………………………89
圖目、圖表
圖2.2-1 統計模式之編碼流程………………………………………………4
圖2.2-2 編碼樹………………………………………………4
圖2.2-3 可適應模式編碼流程………………………………………………5
圖2.2-4(a) 霍夫曼編碼過程………………………………………………6
圖2.2-4(b) 霍夫曼編碼過程………………………………………………7
圖2.2-5 動態霍夫曼樹更新過程………………………………………………10
圖2.2-6 動態霍夫曼樹更新過程(輸入新符號) …………………………………11
圖2.2-7 動態霍夫曼樹更新虛擬碼………………………………………………12
圖2.2-8 動態霍夫曼樹………………………………………………12
圖2.2-9 纏繞式編號………………………………………………14
圖2.2-10 演算法V更新過程………………………………………………15
圖2.2-11 演算法V虛擬碼…………………………………………………16
圖2.2-12 霍夫曼編碼壓縮率比較圖(動態vs傳統)………………………………18
圖2.2-13 馬可夫模型…………………………………………………26
圖2.2-14 動態馬可夫模型，配置新狀態示意圖…………………………………27
圖2.3-1動態霍夫曼節點權位值遞減過程…………………………………………29
圖2.3-2 滑動視窗…………………………………………29
圖2.3-3 動態霍夫曼樹更新過程…………………………………………31
圖2.3-4 動態霍夫曼編碼壓縮率比較圖(不同視窗長度，不同區塊大小) ………34
圖2.3-5 壓縮率比較圖(霍夫曼編碼VS動態霍夫曼(滑動視窗))………………35
圖2.4-1 LZ77滑動視窗…………………………………………………37
圖2.5-1各壓縮演算法比較法(壓縮比) ……………………………………………48
圖2.5-2 各壓縮演算法比較(壓縮速度bytes/sec) …………………………………48
圖3.1-1 霍夫曼樹……………………………………………………52
圖3.1-2 Deflate未壓縮區塊之資料格式…………………………………………55
圖3.1-3 碼字長度碼(code len code) 之定義………………………………………59
圖3.1-4 dynamic Huffman code壓縮區塊說明 …………………………………60
圖3.2-1 LZSS+DHC壓縮率變化(bible) ………………………………………66
圖3.2-2 LZSS+DMC壓縮率變化(bible) ………………………………………69
圖3.2-3 索引圖 ………………………………………75
圖3.2-4 壓縮率變化(bible) ………………………………………76
圖3.3-1 各壓縮演算法比較法(壓縮比) ………………………………………77
圖3.3-2 各壓縮演算法比較(壓縮速度bytes/sec) …………………………………78
圖4.1-1 編碼過程………………………………………79
圖4.2-2 編碼流程………………………………………82
圖4.2-3 解碼流程………………………………………………83
圖4.3-1 壓縮率比較(單一演算法) ……………………………………………87
圖4.3-2 壓縮率比較(複合式演算法) ……………………………………………87
表2.2-1 動態霍夫曼編碼壓縮效能………………………………………………17
表2.2-2 霍夫曼編碼壓縮效能………………………………………………17
表2.2-3 符號機率表………………………………………………20
表2.2-4 算術編碼(編碼過程)………………………………………………20
表2.2-5 算術編碼(解碼過程)………………………………………………21
表2.2-6 算術編碼(編碼過程)………………………………………………23
表2.2-7 算術編碼(解碼過程)………………………………………………24
表2.2-8動態馬可夫鏈編碼壓縮效能………………………………………………25
表2.3.-1動態霍夫曼編碼壓縮效能(視窗長度8kBytes，區塊大小8kBytes)……32
表2.3.-2動態霍夫曼編碼壓縮效能(視窗長度8k Bytes，區塊大小16k Bytes)…33
表2.3.-3動態霍夫曼編碼壓縮效能(視窗長度16k Bytes，區塊大小8k Bytes)…33
表2.3.-4動態霍夫曼編碼壓縮效能(視窗長度16k Bytes，區塊大小16kBytes)…34
表2.4-1 LZSS壓縮效能……………………………………………………43
表2.4-2 LZW索引配置表…………………………………………………46
表2.4-3 LZW壓縮效能…………………………………………………46
表2.5-1 各壓縮演算法需求之記憶體大小(壓縮)………………………………47
表2.5-2 執行程式之系統…………………………………………………47
表3.1-1 長度碼(length code)對應之重複長度表…………………………………56
表3.1-2距離碼(distance code)對應之指回距離表…………………………………57
表3.1-3固定長度霍夫曼碼及碼字長度……………………………………………58
表3.1-4利用dynamic Huffman 壓縮之區塊格式…………………………………60
表3.1-5 ZIP 壓縮效率……………………………………………………61
表3.2-1 LZSS+DHC壓縮效能…………………………………………………66
表3.2-2 LZSS+DMC壓縮效能…………………………………………………69
表3.2-3 LZW索引配置…………………………………………………73
表3.2-4 LZW碼字額外位元數…………………………………………………73
表3.2-5 索引映射表…………………………………………………74
表3.2-6 LZW+DHC壓縮效能…………………………………………………75
表3.3-1 各壓縮演算法需求之記憶體大小(壓縮)…………………………………75
表3.3-2 執行程式之系統…………………………………………………77
表4.2-1 欲壓縮資料格式…………………………………………………80
表4.2-2 變化量所對應的霍夫曼碼字……………………………………………84
表4.3-1 數位資料及類比資料大小……………………………………………85
表4.3-2 數位資料壓縮效率(單一演算法) ………………………………………85
表4.3-3 數位資料壓縮效率(複合式演算法) ……………………………………85
表4.3-4 類比資料壓縮效率(單一演算法) ………………………………………85
表4.3-5 類比資料壓縮效率(複合式演算法) ……………………………………86
表4.3-6 未分類資料壓縮效率(單一演算法) ……………………………………86
表4.3-7 未分類資料壓縮效率(複合式演算法) …………………………………86

參考文獻

[1]. PKZIP Applications Note-ZIP File Format Specificatio.PKWare Inc.
[2]. RFC1951 DEFLATE Compressed Data Format Specification V1.3.
[3].M. Nelson，”LZW Data Compression” Dr. Dobbs Journal， Vol.14，NO.10，Oct.，1989，pp29-37.
[4] T.A. Welch，”A Technique for High-performance Data Compression”，IEEE Computer，vol. 17，pp.8-19，Jun. 1984.
[5].T.C. Bell，J.G. Cleary，and I.H. Witten，Text Compression，NJ: Prentice Hall，1990
[6]. Ross N. Williams “Adaptive Data Compression”
[7]. Jeffrey Scott Vitter “Design and Analysis of Dynamic Huffman Codes”
JANUARY 1987
[8]. KNUTH, D. E. Dynamic Huffman coding. J. Algorithms 6 (1985), 163-180.
[9]. JEFFREY SCOTT VITTER “ALGORITHM 673 Dynamic Huffman
Coding” ACM Transactions on Mathematical Software, Vol. 15, No. 2, June 1989, Pages 158-167

指導教授

林銀議(Yin-Yi Lin)

審核日期

2003-7-14

推文