資料壓縮方法分為有損與無損兩種，而大部分無損壓縮法遇雜訊皆有嚴重錯誤擴散情形，例如Huffman編碼、算術編碼、Ziv-Lempel編碼等。只有Tunstall編碼因採用固定長度字碼，又未使用動態字典，有較高的容錯能力。可是Tunstall編碼的壓縮率並不高，故本文目的在於保持Tunstall容錯能力下，希望能提昇其壓縮率。由於傳統Tunstall符號剖析樹的建構法較無彈性，每次挑最大機率節點作擴展時，必長滿所有符號節點，容易浪費珍貴字碼於低機率符號節點上，或有多餘的字碼未指派。本文共提出A、B、C三種Tunstall符號剖析樹的改良方案，A、B兩方案以傳統Tunstall符號剖析樹為基礎，A方案經過新增，B方案經過刪除符號剖析樹節點，使字碼可以充分指派於高機率節點上；C方案則改以無窮延伸符號剖析樹為基礎，除了可以充分指派字碼外，指派字碼時亦盡可挑選符號剖析樹中機率最高的節點，以長出最佳符號剖析樹。最後，將上述三種改良方案與傳統Tunstall符號剖析樹比較其資料壓縮率表現。根據實驗結果顯示，在一般資料集上C方案擁有較佳達6%的壓縮提昇表現，且消耗時間也不會比A、B兩方案差。

There are lossy and lossless techniques for data compression. Most lossless compression techniques are vulnerable to noise. When bit flips occur due to noise, serious error propagation will be seen in such lossless compression techniques as Huffman coding, arithmetic coding, and Ziv-Lempel coding. By using fixed-length codewords and not using an adaptive dictionary, Tunstall coding stands out as an error-resilient lossless compression technique. However the compression ratio of Tunstall coding is not good. Therefore the aim of this work is to enhance the compression ratio of Tunstall coding without compromising its error-resilience.
Traditional Tunstall coding grows a parse tree by iterative expansion of the maximum probability leaf. On each node expansion, it adopts the exhaustive branching of all symbol leaves, which will cause some precious codewords unassigned or waste of codewords on low probability nodes. In this work, three revised versions A, B, C of Tunstall coding are proposed. Versions A and B are based on the traditional Tunstall parse tree and aim to improve assignment of the complete codewords to high probability nodes via node insertion and deletion respectively. Version C is based on an infinitely extended parse tree and aims to grow the optimal parse tree by assigning the complete codewords only to top probability nodes in the infinite tree.
For evaluation, the performances of the three revised versions are compared with that of the traditional Tunstall coding. The experiment shows that on common datasets, version C has better performance than versions A and B and can have up to 6% increase of compression ratio over traditional Tuntsall Coding. Furthermore, version C is not worse than version A and B in terms of compression time.

目錄
1	緒論	1
1.1	研究動機	1
1.2	論文架構	3
2	文獻探討	4
2.1	Huffman編碼	4
2.2	算術編碼	4
2.3	Ziv-Lempel編碼	6
2.4	Tunstall編碼	6
2.4.1	Tunstall編碼演算法	7
2.4.2	Tunstall編碼範例	8
2.5	Algra改良式Tunstall編碼	9
3	方法介紹	11
3.1	問題定義	11
3.2	符號剖析樹的改良方案	12
3.2.1	符號剖析樹改良方案A	12
3.2.2	符號剖析樹改良方案B	14
3.2.3	符號剖析樹改良方案C	16
3.3	傳統與改良方案的符號剖析樹比較	17
4	實作架構與實驗結果	24
4.1	系統架構	24
4.2	編碼與解碼	25
4.2.1	編碼	25
4.2.2	解碼	25
4.3	測試資料集	26
4.4	結果討論	27
5	結論與未來發展	42
參考文獻	44
附錄A. 符號剖析樹改良方案A詳細演算法	46
附錄B. 符號剖析樹改良方案B詳細演算法	49
附錄C. 符號剖析樹改良方案C詳細演算法	51

 
圖目錄
圖1︰可描述資料傳輸及存取過程之通訊系統模組	2
圖2︰符號串流”abc”使用算術編碼過程，編碼結果為︰0.5460數值	5
圖3︰Tunstall符號剖析樹，符號0機率0.25，符號1機率0.75，字碼數4	8
圖4︰編碼效率比較圖。橫軸為Laplacian分佈之標準差 ；縱軸為編碼效率。‧表Huffman編碼、 表Tunstall編碼、△表Algra 改良式Tunstall編碼	10
圖5︰Laplacian分佈圖	10
圖6︰Huffman編碼遇位元反轉，造成解碼後有錯誤擴散或符號位移情形，方框為符號解碼錯誤部份	11
圖7︰傳統Tunstall建構之符號剖析樹。節點旁數字表指派之字碼編號，其中編號8字碼未指派到	18
圖8︰先少後補改良方案A建構之符號剖析樹。編號4內部節點因未長全而需指派字碼，以底線標示之	19
圖9︰先多後刪改良方案B建構之符號剖析樹。虛線表刪除之節點，底線表因刪除而未長全之內部節點(故亦須指派字碼)	21
圖10︰以無窮延伸樹為基礎，改良方案C建構之符號剖析樹。底線表示自己為候選字碼，但並非所有子節點為候選字碼之內部節點，即未長全尚需要指派字碼，無法讓出字碼之內部節點。雙底線表示為彌補第一層符號節點所缺字碼，而讓出字碼之候選字碼節點	22
圖11︰編碼流程圖	24
圖12︰解碼流程圖	24
圖13︰Laplacian分佈下改良A、改良B、改良C與Algra改良方案對於傳統Tunstall之壓縮率比	36
圖14︰Laplacian分佈下改良A、改良B、改良C與Algra改良方案對於傳統Tunstall之編碼效率比	36
圖15︰Laplacian分佈下改良A、改良B、改良C與Algra改良方案對於傳統Tunstall之壓縮時間比	37
圖16︰Tunstall與改良C於Laplacian資料集之壓縮率	37
圖17︰Laplacian分佈資料下，改良C、Huffman編碼、算術編碼與Gzip分別跟Tunstall編碼的壓縮率比	41
 
表目錄
表1︰傳統Tunstall建構之編碼表	18
表2︰改良方案A建構之編碼表	20
表3︰改良方法B建構之編碼表	21
表4︰改良方案C建構之編碼表	23
表5︰測試資料集檔案明細	26
表6︰五資料集之平均壓縮率(CR)、平均編碼效率(CE)與平均壓縮時間(Time)比較表	30
表7︰改良A、改良B、改良C與傳統Tunstall之平均壓縮率比、平均編碼效率比與平均時間比	31
表8︰改良C方案壓縮下，壓縮率最好與最差之六個資料檔列表	33
表9︰改良式A、B、C及Algra和傳統Tunstall，在之Laplacian分佈下之比值結果	35
表10︰字碼位元長度固定為m=16位元，不同符號位元長度n=1~9之下Tunstall序列編碼對book1資料檔的壓縮率結果	38
表11︰符號位元長度固定為n=8位元，不同字碼位元長度m=8~18之下Tunstall系列編碼對book1資料檔的壓縮率結果	39
表12︰Tunstall編碼、改良C、Huffman編碼、算術編碼與Gzip比較	40
表13︰Laplacian分佈資料下，改良C、Huffman編碼、算術編碼與Gzip分別跟Tunstall編碼的壓縮率比與壓縮時間比	40

[1]	Abrahams, J., “Code and parse trees for lossless source encoding,” Compression and Complexity of Sequences, 1997, pp.145-171.
[2]	Algra, T., “Fast and efficient variable-to-fixed length coding algorithm,” Electronics Letters, 28(15), 1992, pp.1399-1401.
[3]	Briffa, J., “Investigation of the error performance of Tunstall coding,” B.Eng. Final Year Dissertation, Faculty of Engineering, University of Malta, 1997.
[4]	Gzip for Windows, Available at:
http://gnuwin32.sourceforge.net/packages/gzip.htm 
[5]	Hashempour, H., Schiano, L. and Lombardi, F., “Error-resilient test data compression using Tunstall codes,” 19th IEEE International Symposium, 2004, pp.316-323.
[6]	Hekland, F., “A Review of Joint Source-Channel Coding,” Dept. of Electronics and Telecommunications Norwegian University of Science and Technology, February 16, 2004.
[7]	Huffman, D.A., “A method for the construction of minimum redundancy code,” Proc. of the IRE, 40, 1952, pp.1098-1101.
[8]	Nelson, M., ”Arithmetic Coding + Statistical Modeling = Data Compression,” Dr. Dobb’s Journal, February 1991, pp.530-536.
[9]	Sayood, K., Introduction to Data Compression, Morgan Kaufmann Publishers, San Francisco, 2006.
[10]	The Canterbury, Calgary, Large, Pi Corpora available at :
http://corpus.canterbury.ac.nz/descriptions/
[11]	Tunstall, B.P., “Synthesis of noiseless compression codes,” Ph.D. Dissertation, Georgia Institute of Technology, Atlanta, GA, 1968.
[12]	Viterbi, A.J. and Omura, J.K., Principles of Digital Communication and Coding, McGraw-Hill, New York, 1979.
[13]	Wu, Y., Lonardi, S. and Szpankowski, W., “Error-resilient LZW data compression,” Data Compression Conference, March 2006, pp.193-202.
[14]	Ziv, J. and Lempel, A., “A universal algorithm for sequential data compression,” IEEE Transactions on Information Theory, 23(3), May 1977, pp.337-343.
[15]	Ziv, J. and Lempel, A., “Compression of individual sequences via variable-rate coding,” IEEE Transactions on Information Theory, 24(5), September 1978, pp.530-536.