跳到主要內容

臺灣博碩士論文加值系統

(3.87.33.97) 您好!臺灣時間:2022/01/27 16:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:簡銘言
論文名稱:具抑制錯誤蔓延能力之LempelZivCodes
論文名稱(外文):Error resilient Lempel Ziv Codes
指導教授:黃育銘
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:65
中文關鍵詞:錯誤蔓延錯誤回復文字壓縮LZWLZ 78
外文關鍵詞:Error PropagationError ResilientLZWLZ 78
相關次數:
  • 被引用被引用:0
  • 點閱點閱:254
  • 評分評分:
  • 下載下載:17
  • 收藏至我的研究室書目清單書目收藏:0
本論文探討具有防止錯誤擴散能力、且壓縮率仍能維持相當高比率的文字壓縮演算法。其中,包含了目前最受廣泛應用的 LZW 演算法,及稍早文獻中所提出的 LZ 78 演算法。
在 LZW 演算法的部分,由於參考文獻中所載的演算法有所謬誤但一直沒有提出修正,於是,我們針對文獻所提出的具有防止錯誤擴散能力的 LZW 演算法,提出它可能的實作方式以及修正後的演算法,並將我們的實驗的數據具體表列並分析。
而 LZ 78 演算法的部分,我們根據文獻中對 LZW 所建構之錯誤模型的理論分析,推導出關於 LZ 78 的理論分析,接著我們依據這個理論,提出亦具有防止錯誤擴散能力之 LZ 78 演算法,同時,我們也將這個演算法的實驗數據具體表列並分析。

In this thesis, we explore error resilient compression algorithm that can prevent error propagation and owns a high compression ratio. The protocols, which are used to make LZW and LZ 78 algorithms have error resilient ability, are described elaborately.
First, we study the error resilient LZW algorithm. We find that there are some errors in the error resilient LZW algorithm which was first proposed in 1997. Therefore, some corrected and modified algorithms are proposed in this thesis, and our experimental results are included also.
Based on the theoretical analysis of error resilient LZW algorithm in the previous literature, we derive a theoretical analysis for error resilient LZ 78, and an error resilient algorithm for LZ 78 is also proposed.

內容目次 ---------------------------------------------- 1
表目次 ------------------------------------------------ 3
圖目次 ------------------------------------------------ 5
第一章 緒論 ------------------------------------------ 1
第二章 具抑制錯誤蔓延能力的 LZW 碼 ------------------- 2
2.1 節 Lempel-Ziv 碼的種類 ------------------------ 3
2.2 節 Lempel-Ziv Welch (LZW)碼 ---------------- 3
2.3 節 具抑制錯誤蔓延能力的 LZW 碼 --------------- 7
2.4 節 K-error Protocol 的謬誤及修正 ---------------- 14
2.5 節 K-error Protocol 實作問題之探討 -------------- 27
第三章 具抑制錯誤蔓延能力的 LZ 78 碼 ------------------ 35
3.1 節 LZ 78 碼 ---------------------------------- 35
3.2 節 具抑制錯誤蔓延能力的 LZ 78 碼 ------------- 38
3.3 節 LZ 78 碼的 LAG 理論 ---------------------- 41
3.4 節 LZ 78 的 K-Error Protocol -------------------- 46
3.5 節 LZW 、 LZ 78 碼於完美雜湊表的 LAG 理論 --- 49
3.6 節 Digital Search Tree ( DST ) -------------------- 49
第四章 實驗結果 --------------------------------------- 52
4.1 節 LZW 碼 ----------------------------------- 52
4.2 節 LZ 78 碼 ---------------------------------- 58
第五章 結論及未來展望 --------------------------------- 63
5.1 節 結論 ------------------------------------- 63
5.2 節 未來展望 --------------------------------- 63
參考文獻 ----------------------------------------------- 65
表目次
表2-1: LZW 編碼過程 --------------------------------- 5
表2-2: LZW 解碼過程 --------------------------------- 7
表2-3: LZW Method 1 編碼過程 ----------------------- 17
表2-4: LZW Method 1 解碼過程 ----------------------- 19
表2-5: LZW Method 2 編碼過程 ----------------------- 24
表2-6: LZW Method 2 解碼過程 ----------------------- 26
表3-1: LZ 78 編碼過程 ------------------------------- 37
表3-2: LZ 78 解碼過程 ------------------------------- 38
表3-3: LZ 78 Method 1 from [8] 編碼過程 --------------- 40
表3-4: LZ 78 Method 1 from [8] 解碼過程 --------------- 41
表3-5: LZ 78 with K-Error Protocol 編碼過程 ------------- 47
表3-6: LZ 78 with K-Error Protocol 解碼過程 ------------- 48
表4-1: LZW Dic Size = 65536 時各演算法之壓縮比 ------- 53
表4-2: LZW Dic Size = 16384 時各演算法之壓縮比 ------- 54
表4-3: LZW Dic Size = 4096 時各演算法之壓縮比 -------- 54
表4-4: Warming Value 的大小對壓縮比所造成之影響 ------ 55
表4-5~4-8:1/2000 錯誤率下 LZW 各演算法之錯誤比 ----- 57
表4-9: LZ 78 Dic Size = 65536 時各演算法之壓縮比 ------- 59
表4-10: LZ 78 Dic Size = 16384 時各演算法之壓縮比 ------ 59
表4-11: LZ 78 Dic Size = 4096 時各演算法之壓縮比 ------- 60
表4-12: Warming Value 的大小對壓縮比所造成之影響 ----- 60
表4-13~4-16:1/2000 錯誤率下 LZ 78 各演算法之錯誤比 --- 61
圖目次
圖3-1: Structure of DST -------------------------------- 50
圖3-2: Structure of b-DST ------------------------------ 50
圖4-1: Warming Value 的大小對壓縮比所造成之影響 ----- 56
圖4-2: Warming Value 的大小對壓縮比所造成之影響 ------ 61

[1] A. Wyner and J. Ziv, “Some Asymptotic Properties of the Entropy of a Stationary Ergodic Data Source with Application to Data Compression,” IEEE Trans. Inform. Theory, vol. 35, pp.1250-1258, 1989.
[2] J. A. Storer and J. Reif, “Error resilient optimal data compression,” SIAM J. Comput., vol. 26, no. 4, pp. 934—939, Aug, 1997.
[3] J. A. Storer and J. Reif, “Low-cost prevention of error propagation for data compression with dynamic dictionaries,” in Proc. IEEE Data Compression Conf., Snowbird, UT, 1997, pp. 171—180.
[4] J. A. Storer, “The prevention of error propagation in dictionary compression with update and deletion,” in Proc. IEEE Data Compression Conf., Snowbird, UT, 1998, pp. 199—208.
[5] J. A. Storer, “The prevention of error propagation in dictionary compression with update and deletion,” in Proc. of the IEEE , Volume: 88 Issue: 11 , Nov. 2000 pp. 1713 -1721
[6] J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” IEEE Trans. Inform. Theory, vol.23, no. 3, pp. 337-343, 1977.
[7] J. Ziv and A. Lempel, “Compression of Individual Sequences via Variable-Rate Coding,” IEEE Trans. Inform. Theory, vol. 4, pp. 536-550, 1978.
[8] Y. A. Reznik and W. Spankowski, “On the average redundancy rate of the Lempel—Ziv code with K-Error protocol,” in Proc. IEEE Data Compression Conf., Snowbird, UT, 2000, pp. 373—382.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文