臺灣博碩士論文加值系統

摘要

在本論文中，我們針對現今資訊流量的大量增加，提供了資料壓縮的論點來解決資料處理的問題。我們對機械碼進行研究，並嘗試設計一個壓縮架構，希望能達到資料處理的兩個目的－”能對任何資料壓縮”、”能壓縮多次以上”。另外，我們亦討論無失真的壓縮法所具有的優勢，以及所能帶來的好處。

Abstract

At present, we find that the largely increasing of information interchange will bring some problems of data process. According that, in this thesis, we provide a viewpoint of data compression to solve these problems. We research on the machine code, and try to design a compression structure. We hope that can attain the two purposes of “ can compress any type of data” and “ can compress more than twice”. We also discuss the advantages of the lossless data compression.

目錄
誌謝 I
摘要 II
Abstract III
目錄 IV
圖目錄 VI
表目錄 VII

第一章 緒論 1
第二章 資料壓縮的介紹與資料壓縮法的回顧 3
2.1 資料壓縮的定義 3
2.2 資料壓縮技術的背景與發展 4
2.2.1 資料壓縮與通訊系統 4
2.2.2 標準化的建立 4
2.2.3 資料壓縮技術的應用前景 5
2.3 資料壓縮的分類 5
2.4 信號編碼的概念 7
2.4.1 資訊量 7
2.4.2 熵（Entropy）的觀念 8
2.4.3 統計模式與字典基礎模式 8
2.4.4 變異長度編碼 9
2.4.5 唯一解碼與即時碼 9
2.4.6 擴充碼 10
2.5 Shannon-Fano編碼 11
2.6 Huffman編碼 12
2.7 算術編碼 14
2.8 LZ系列編碼 16
第一章 無失真機械碼壓縮法的架構 18
3.1 前言 18
3.2 無失真機械碼壓縮法架構 18
3.2.1 如何建立編碼架構 18
3.2.2 理論上的壓縮極限 20
3.2.3 各類別的編碼方法 25
3.3 編碼與解碼流程圖 31
第二章 壓縮架構討論與程式架構 34
4.1 壓縮架構的說明 34
4.2 壓縮架構的分析 35
4.3 程式架構 36
第三章 討論與未來展望 39
References 40








圖目錄

圖2.1 數位傳輸系統模型 3
圖2.2 資料壓縮比的定義 6
圖2.3 資料壓縮技術的歸類 7
圖2.4 Shannon-Fano的操作過程 12
圖2.5 Huffman編碼的操作過程 13
圖3.1 資料分項圖示 19
圖3.2 判斷字串的定義 19
圖3.3 判斷字串的處理過程例子 19
圖3.4 依判斷字串決定類别 20
圖3.5 第六類的排列法 21
圖3.6 第1到4類排列情形 23
圖3.7 第5到8類排列情形 24
圖3.8 翻轉情況 29
圖3.9 判斷的編碼情況 30
圖3.10 編碼動作流程圖 32
圖3.11 解碼動作流程圖 32
圖4.1 壓縮程式流程圖 37
圖4.2 壓縮時資料結構示意圖 38




表目錄

表2.1 無失真資料壓縮法與失真資料壓縮法的特性比較 6
表2.2 Shannon-Fano編碼與Huffman編碼的比較 13
表2.3 各個符號所出現機率與編碼範圍 14
表2.4 算術編碼的步驟 15
表3.1 2的次方表 22
表3.2 編碼極限列表 24
表3.3 每一類別編碼長度表 33
表4.1 各種檔案的分布趨勢 36

References：

[1] 才園哲人著，林庭語譯，「圖解後基因組」，品冠文化出版社，2003。
[2] 吳樂南著，「資料壓縮的原理與應用」，儒林圖書出版，1996。
[3] 康誦詩，「國際電信聯盟（ITU）的改組現況」，今日電子，1994年第3期。
[4] R. J. McEliece, The Theory of Information and Coding, Reading, MA : Addison-Wesley, 1977.
[5] C. E. Shannon, “A mathematical Theory of Communication.” Bell Sys. Tech. J., 27, 379-423, 623-656, 1948.
[6] C. E. Shannon, “Prediction and entropy of printed English.” Bell sys. Tech. J., 30, 50-64, 1951.
[7] R. M. Fano, The Transmission of Information, Tech. Rep. No. 65, M. I. T., Res. Lab. Of Electronics,1949.
[8] D. A. Huffman, “A method for the construction of minimum redundancy codes.” Pro. IRE, 40, 1098-1101, 1952.
[9] R. Hunter and A. H. Robinson, “International digital facsimile standards,” Pro. IEEE, 68, 854-867, 1980.
[10]W. B. Pennebaker, “JPEG Technical Specification, Revision 8.” Working Document No. JTC1/SC2/WG10/JPEG-8-R8, 1990.
[11]J. Rissanen and G. G. Langdon, “Arithmetic coding.” IBM J. Res. De., 23, 149-162, 1979.
[12]G. G. Langdon, “An Introduction to Arithmetic Coding.” IBM J. Res. De., 28, 135-149, 1985.
[13]J. Ziv and A. Lampel, “A Universal algorithm for sequential data compression.” IEEE Trans. Info. Theory, IT-23, 337-343, 1977.
[14]J. Ziv and A. Lampel, “Compression of individual sequence via variable-rate coding.” IEEE Trans. Info. Theory, IT-24, 530-536, 1978.
[15]T. C. Bell, J. G. Cleary and I. H. Witten, Text Compression, Prentice Hall,Englewood Cliffs, NJ., 1990.
[16]戴顯權著，「資料壓縮」，松崗電腦圖書出版，1998。
[17]N. Abramson, Information Theory and Coding, McGraw-Hill, New York, 1963.
[18]侯陽 編寫，「數據壓縮技術及C語言實例」，學苑出版社，1994。
[19]The Telecommunication Union homepage. http://www.itu.int/home/
[20]The International Organization for Standardization homepage. http://www.iso.org/iso/en/ISOOnline.frontpage
[21]The International Electrotechnical Commission homepage. http://www.iec.ch/