國 立 中 央 大 學
通 訊 工 程 研 究 所
碩 士 論 文
即時性無失真壓縮編碼之研究
指導教授：林銀議 博士
研 究 生：曹登鈞
中華民國 九十三 年 七 月
國立中央大學圖書館
碩博士論文電子檔授權書
(93 年 5 月最新修正版)
本授權書所授權之論文全文電子檔，為本人於國立中央大學，撰寫之
碩/博士學位論文。(以下請擇一勾選)
( ˇ )
同意 (立即開放)
( )
同意 (一年後開放)，原因是：
( )
同意 (二年後開放)，原因是：
( )
不同意，原因是：
以非專屬、無償授權國立中央大學圖書館與國家圖書館，基於推動讀
者間「資源共享、互惠合作」之理念，於回饋社會與學術研究之目的，
得不限地域、時間與次數，以紙本、微縮、光碟及其它各種方法將上
列論文收錄、重製、公開陳列、與發行，或再授權他人以各種方法重
製與利用，並得將數位化之上列論文與論文電子檔以上載網路方式，
提供讀者基於個人非營利性質之線上檢索、閱覽、下載或列印。
研究生簽名:
曹登鈞
論文名稱:
即時性無失真壓縮編碼之研究
指導教授姓名： 林銀議
系所 ： 通訊工程研究 所 博士 ■碩士班
學號： 91523017
日期：民國 93 年 7 月 5 日
備註：
1. 本授權書請填寫並親筆簽名後，裝訂於各紙本論文封面後之次頁（全文電子檔內之授權
書簽名，可用電腦打字代替）。
2. 請加印一份單張之授權書，填寫並親筆簽名後，於辦理離校時交圖書館（以統一代轉寄
給國家圖書館）。
3. 讀者基於個人非營利性質之線上檢索、閱覽、下載或列印上列論文，應依著作權法相關
規定辦理。
論文名稱：即時性無失真壓縮編碼之研究 頁數: 122
系所組別：國立中央大學通訊工程研究所 訊號處理組
畢業時間及提要別：九十三年度第二學期碩士論文提要
研究生：曹登鈞 指導教授：林銀議 博士
論文提要及內容
目前無失真壓縮技術的種類眾多，但是大部分的壓縮技術均需要大量
的壓縮時間，才能發揮最佳的壓縮效能，但是大量的壓縮時間，根本配合
不上目前高速的網路傳輸速度，因此能配合高速網路所做的即時性無失真
壓縮技術就變的相當重要。本篇論文之研究目的在於，研究高速地即時性
無失真壓縮技術，希望從研究過程中，獲得解決的方法。
研究者在研究提升壓縮處理速度方式的期間，發現了目前壓縮處理速
度最快的演算法 Lempel Ziv Oberhumer。LZO 的壓縮演算原理根據 LZSS
壓縮原理做改良，而且 LZO 屬於字典模式的壓縮方法，所以本篇論文中，
會深入的探討與分析字典模式的無失真壓縮編碼，並與 LZO 演算法做分析
與比較，藉由分析的過程進一步了解 LZO 的高速壓縮原理與壓縮特性。了
解 LZO 的壓縮原
理後，再針對 LZO 的缺點提出改進方式，而 LZO 的改進
方法研究，均在不影響 LZO 高速壓縮的前提之下進行，因此本篇論文最主
要的重點是，在影響 LZO 壓縮速度最小的情況之下，研究 LZO 壓縮演算
法的最佳改良方式。
誌 謝
首先，我要感謝指導老師 林銀議教授，這兩年的碩士生活，讓登鈞
成長很多，尤其在待人與做事方法上受益最多，在往後的生活上，登鈞會
繼續在這兩方面做更多的學習。在此登鈞也要特別感謝中央大學通訊系老
師 張寶基教授，登鈞在張寶基老師身上學到受用一輩子的做事態度，登
鈞非常感謝張寶基老師不吝惜得指導，讓登鈞的論文可以順利完成，感謝
兩位老師的栽培。我也感謝碩士兩年中，認識的學長與同學們，因為有你
們兩年的陪伴，讓登鈞這兩年過得非常充實，沒有留下任何的遺憾，希望
大家都能在往後生活過得順心，也希望我們的友誼可以繼續保持，永遠延
續下去。
最後我要感謝一路陪伴我成長的父母與家人，因為有你們的支持與鼓
勵，讓我有勇氣面對各種不同的挑戰，謝謝陪伴與支持我的每一位家人與
朋友，非常感謝!
目錄 頁碼
第一章 緒論
………………………………………………………………1
1.1 研究目的 …………………………………………………………1
1.2 研究動機……………………………………………………………1
1.3 章節介紹……………………………………………………………2
第二章 無失真壓縮法—字典基礎模式……………………………………4
2.1 各式壓縮法簡介
……………………………………………………4
2.1.1 無失真壓縮法─字典基礎模式
……………………………5
2.2 無失真壓縮法─LZ77 系列…………………………………………7
2.2.1 Lempel Ziv 77 壓縮法則
……………………………………7
2.2.2 LZSS 壓縮法則
……………………………………………11
2.2.3 Lempel Ziv Oberhumer 壓縮法則
…………………………16
2.3 無失真壓縮法─LZ78 系列
………………………………………40
2.3.1 Lempel Ziv 78 壓縮法………………………………………40
2.3.2 LZW 壓縮法 ………………………………………………42
2.4 Run Length Encoding 的介紹……………………………………46
2.5 各個演算法效能比較
……………………………………………50
2.5.1 LZW 與 LZO 的效能比較
…………………………………50
2.5.2 LZSS 與 LZO 的效能比較
…………………………………58
第三章 LZO 壓縮法之改進與研究
………………………………………67
3.1 簡介
………………………………………………………………67
3.2 Two level 的搜尋方式
……………………………………………68
3.3 LZO 匹配搜尋方式的改進
………………………………………75
3.3.1 使用 Two level hashing 來做搜尋匹配
…………………75
3.4 改進的效能評估與實驗結果
……………………………………87
第四章 LZO 壓縮法加上前處理的研究
…………………………………99
4.1 簡介
………………………………………………………………99
4.2 RLE 的改進………………………………………………………100
4.2.1 LZO 加上 RLE 處理的探討與研究………………………100
4.2.2 RLE 的改進 ………………………………………………104
4.3 改進的效能評估與實驗結果
…………………………………110
I
- 1
- 2
- 3
- 4
- 5
前往页