即時性無失真壓縮之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：12

、訪客IP：52.14.168.56

姓名

羅偉君(Wei-Jun Luo) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

即時性無失真壓縮之研究
(A Study of Real-Time Lossless Compression)

相關論文

★ 10Gb/s MM XFP光收發模組設計與實現	★ 資訊產品自動化測試之研究
★ 高電流密度鰭式氮化鎵高電子遷移率電晶體研究	★ 電子郵件及壓縮檔案解碼之研究
★ 渦輪碼在光學記錄系統上之應用	★ 離散餘弦轉換硬體架構之研究
★ 動態影像之錯誤隱藏研究	★ 即時性無失真壓縮編碼之研究
★ 類神經網路在手寫數字辨識之研究	★ 事後機率演算法則在資料儲存系統之研究
★ 紅外線傳輸協定及通道之研究	★ 低密度同位元檢查碼在數位資料儲存系統之研究
★ 一種新型的JPEG2000竄改偵測與還原技術	★ 混合快速模式決策演算法之研究
★ 光學記錄MEPR2通道系統之時序恢復探討與研究	★ 零區塊提前偵測在DCT轉換量化及移動搜尋應用探討

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

在曹登鈞學長的論文中，提出一種Two Level Hash 的搜尋方式，來改善目前無失真壓縮中速度最快的Lempel Ziv Oberhumer (LZO) 壓縮演算法則在壓縮率上的表現，亦針對LZO 所處理不好的檔案提出以加入Run Length Encoder 前處理器來改善。由於Two Level Hash 作法上的因素，使得對於特定類型的一些檔案會有失去效用的情況發生。
本篇論文針對了Two Level Hash 的缺點，由失效檔案的內容去分析，並深入的探討Two Level Hash 在作法上的缺陷與潛在的問題，找出了造成失效的原因，並針對造成失效的原因提出了因應的解決方法。經使用四組公開於網路上的測試資料時際遇壓縮測試之後，LZO 使用改進後的Two Level Hash 搜尋方式後，可以在壓縮率上有大幅的提升。若以使用One Level Hash 搜尋方式的LZO 壓縮方式為基準，使用改進之後的Two Level Hash 的壓縮率提升比率，比起原始Two Level Hash 可以再提升4.35 ~ 6.11%，而在壓縮速度上亦與使用原始的Two Level Hash 作法相近，在P3-450MHz 256MB 的Windows 98 SE 系統的測試環境下，速度只差了0.77 ~ 1.28 MByte/sec。使用前處理器結合改進後的Two Level Hash LZO，壓縮率比LZSS 好，壓縮速度亦比LZSS 快上3.9 ~ 4.47 MByte/sec，效能已完全超越LZSS 的表現。

關鍵字(中)

★ 無失真壓縮

關鍵字(英)

★ RLE
★ LZO
★ LZSS
★ LZ77
★ Two Level Hash

論文目次

第一章緒論 1
1.1 研究動機 1
1.2 研究目的 1
1.3 章節介紹 2
第二章研究背景與原理介紹 3
2.1 無失真壓縮法簡介 3
2.1.1 LZ77壓縮法則 4
2.1.2 LZSS壓縮法則 8
2.1.3 LZO壓縮法則 11
2.2 Run Length Encoder (RLE) 之簡介 19
2.3 搜尋方式簡介 20
2.3.1 二位元搜尋樹(Binary Search Tree) 20
2.3.2 Linked List 22
2.3.3 雜湊(Hash) 23
2.3.4 Multi-Level Hash 25
2.3.5 Two Level Hash 26
2.4 標準測試資料 30
2.4.1 Calgary Corpus 30
2.4.2 Canterbury Corpus 31
2.4.3 Maximum Compression 33
2.4.4 Silesia Compression Corpus 34
第三章 Two Level Hash LZO之分析與改進 36
3.1 Two Level Hash Algorithm 的缺點 36
3.1.1 雜湊搜尋法造成壓縮率下降的原因 36
3.1.2 Two Level Hash 的限制造成失效的結果 39
3.2 改進方法的探討與選擇 51
3.2.1 其他搜尋法解決記憶空間不足的方式 51
3.2.2 解決Two Level Hash記錄空間不足的方法 53
3.2.3 改進後的效果 56
3.3 改進後的問題 60
3.3.1 檔案越壓越大的問題 60
3.3.2 造成問題的原因 63
3.4 再改進方法之探討與選擇 69
3.4.1 僅更新One Level記錄 69
3.4.2 使用過就更新 71
3.5 改進後效能之評估與實驗結果 73
3.5.1 改進前後Two Level Hash效能比較 73
3.5.2 與其他壓縮方式效能之比較 80
第四章前處理器結合Two Level Hash LZO之探討 89
4.1 Two Level Hash處理不好的檔案 89
4.1.1 Calgary的PIC與Canterbury的PTT5 89
4.1.2 改進後Two Level Hash之處理效果 90
4.2 造成原因與解決方式 91
4.2.1 偏移量為零的問題 92
4.2.2 解決方式 97
4.3 前置處理器最佳設定 99
4.3.1 Run的最佳選擇 100
4.4 不同改進方式之效能評估與實驗結果 110
4.4.1 不同改進方式之效能評估 110
4.4.2 如何選擇解決方案 114
第五章結論 116
參考文獻 118

參考文獻

[AB97] Ross Arnold and Tim Bell. A corpus for the evaluation of lossless compression algorithms. Data Compression Conference, Proceedings 25 -27, pp. 201-210, March 1997.
[AHA04] Comtech AHA Corporation. (n.d.). Application Note, Compression performance: DCLZ algorithm on the Calgary corpus. Retrieved November 8, 2004, from http://www.aha.com/show_pub.php?id=95&BROKENMSIE=1/andc10_1199.pdf
[BCW89] T. C. Bell, J. G. Cleary, and I. H. Witten. Modeling for text compression. ACM Computing Surveys (CSUR), vol. 21, no. 4, pp. 557-591, December 1989.
[BCW90] T. C. Bell, J. G. Cleary, and I. H. Witten. Text Compression. Prentice Hall, Englewood Cliffs, NJ, 1990.
[Ben05] Jonathan Bennett. A C++ implementation of the LZSS / LZ77 algorithm. Retrieved March 12, 2005, from http://www.hiddensoft.com/cgi-bin/countdown.pl?code/LZSS.zip
[Bel86] Timothy C. Bell. Better OPM/L text compression. IEEE Transactions on Communications, vol. 34, no. 12, pp. 1176-1182, December 1986.
[Cao04] 曹登鈞(民93年7月)。即時性無失真壓縮編碼之研究。國立中央大學通訊所碩士論文，未出版。民93年8月10日，取自「國立中央大學圖書館」：http://opac2.lib.ncu.edu.tw/search*cht/a{214356}+{214c7c}{215d4c}/a{214356}{214c7c}{215d4c}/1,1,1,B/l856&FF=a{214356}{214c7c}{215d4c}&1,0,,1,0
[Cal90] Timothy Bell, John Cleary and Ian Witten.(1990). The Calgary Corpus. Retrieved June 10, 2004 from ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus
[Can97] Ross Arnold and Timothy Bell.(1997). The Canterbury Corpus. Retrieved June 28, 2004 from http://corpus.canterbury.ac.nz/descriptions/#cantrbry
[Gil04] Jeff Gilchrist. Archive Comparison Test-Summary of Winners. Retrieved June 12, 2004, from http://compression.ca/act/act-summary.html
[Huf52] D. Huffman, A Method for Construction of Minimum-Redundancy Codes, vol. 40, no. 10, pp. 1098-1101, September, 1952.
[Knu73] D. E. Knuth. The art of computer programming, Vol. 3 – Sorting and Searching. Addison-Wesley, Reading MA, 1973.
[LZO96] Markus F.X.J. Oberhumer. LZO Source Code. Retrieved March 20, 2004, from http://www.oberhumer.com/opensource/lzo/
[Max03] Maximum Compression. Lossless data compression software benchmarks / comparisons. Retrieved August 12, 2004, from http://www.maximumcompression.com/
[MNW98] A. Moffat, R. M. Neal, I. H. Witten. Arithmetic Coding Revisited. ACM Transactions on Information Systems, vol. 16, no. 3, pp. 256-294, July 1998.
[Nel04] Mark Nelson. DataCompression.info. Retrieved November 25, 2004, from http://www.datacompression.info/LZSS.shtml
[Pow01] Matt Powell. Evaluating lossless compression methods. Retrieved April 5, 2004, from http://corpus.canterbury.ac.nz/research/evaluate.pdf
[SI00] Kunihiko Sadakane, Hiroshi Imai. Improving the speed of LZ77 compression by hashing and suffix sorting. IEICE Transactions. Fundamentals, vol. E83-A, no.12, pp. 2689-2698, December 2000.
[Sed83] Robert Sedgewick. Algorithms. Addison-Wesley, ISBN: 0201066726, 1983.
[Sil03] Sebastian Deorowicz. (2003). Silesia Compression Corpus. Retrieved July 10, 2004, from http://sun.iinf.polsl.gliwice.pl/~sdeor/corpus-contents.htm
[SS82] J. A. Storer and T. G. Szymanski. Data compression via textual substitution. Journal of the ACM (JACM), vol. 29, no.4, pp. 928-951, Octember. 1982
[ZL77] J. Ziv and A. Lempel. An universal algorithm for sequential data compression. IEEE Transactions on Information Theory, vol. 23, no. 3, pp. 337-343, 1977.
[ZL78] J. Ziv and A. Lempel. Compression of individual sequences via variable rate coding. IEEE Transactions on Information Theory, vol. 24, no. 5, pp. 530-536, 1978.

指導教授

林銀議(Yin-Yi Lin)

審核日期

2005-7-14

推文