臺灣博碩士論文加值系統

本論文探討具有防止錯誤擴散能力、且壓縮率仍能維持相當高比率的文字壓縮演算法。其中，包含了目前最受廣泛應用的 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.