論文發表網征稿LZW算法研究

　　LZW算法的實質是無損壓縮技術[1-3]，LZW算法通過對輸入流進行分析，自適應地生成一個包含輸入流中不重復子串的串表，將每一子串映射為一獨立的碼字輸出。發表的一篇電子論文，辦的非常成功，極具口碑。在這里，你可以找到最具時事性的文章和最具代表性的各類文章。當然，因為免費和開源，大家都可以學習、借鑒和共同使用，如果你需要專屬于個人的原創文章，請點擊鏈接獲得專業文秘寫作服務。

　　【摘　要】 在分析LZW算法的基礎上，對LZW算法的缺陷進行了探討。并對LZW算法進行了改進，大幅度減少了編碼的長度，降低了匹配長度取值變化的影響，完全兼容LZW算法，在平均壓縮率方面有較大的提高，而且對改進的算法進行了分析論證。

　　【關鍵詞】 數據壓縮 LZW算法 緩沖區

　　這樣，它就充分利用了相鄰輸入之間的相關性，可以取得超過信源一階熵的編碼效率。然而，受緩存容量、計算復雜度和計算速度等因素的限制，串表的長度受到一定限制，且一般信源所具有的局部平穩性隨緩存容量加大，編碼效率提高不大。即：它自身固有一定的缺陷與不足，難以滿足人們的需要，對它進行改進一直成為人們的研究目標之一[4-6]。為了解決這一問題，本文對LZW算法進行了改進，命名為LZWC編碼算法。它兼有LZW算法的優點，還具有自身的優越性。首先對LZW算法進行一些必要的介紹和分析。

　　1. LZW算法

　　LZW算法[1]由韋爾奇(T.A.Welch)于1984年通過對LZ算法的改進。開發出的一種更優算法。它是一種基于字典的編碼方法。并且它是LZ系列碼中應用最廣，變形最多的一種算法。LZW壓縮有3個重要的對象：數據流、編碼流和編譯表。在編碼時，數據流是輸入對象，編碼流就是輸出對象;在解碼時，編碼流則是輸入對象，數據流是輸出對象;而編譯表是在編碼和解碼時都需要借助的對象。

　　1.1LZW算法的編碼原理

　　LZW算法的編碼原理為：對消息序列xn=x1x2x3…xn從左到右進行閱讀，并以此進行LZW編碼：

　　(1)對x1顯然是第一次出現，它的前面也沒有字符，那么他的編號是1，它的碼元為(1,0, x1)。

　　(2)對于x2它可能有兩種情況發生，即x1=x2或x1≠x2。對此，有

　　①如果x1=x2，那么對于x2不作編碼，而對x3的編碼位點取2，連接位點則為1，這表示對x3作第二次編碼，它與第一次編碼的x1相連接。

　　②如果x1≠x2，那么x2的編碼位點取為2，連接位點則為0，這表示對x2作第二次編碼，它的前面沒有出現過相同的字符。

　　(3)依照上述步驟遞推，如果對向量xn=x1x2x3…xn，n

　　對上式的C滿足的條件:對每一個i有且只有一對(i,li)，使li

　　(4)如向量xn中的編碼C及相應的樹確定，那么我們就可讀xn+1,xn+2,…, xn+k,并對它們繼續進行編碼，如果有一個i≦k使xαi=(xn+1,xn+2,…, xn+k)成立，而且對任何i≦k都有：xαi≠( xn+1,xn+2,…, xn+k，xn+k+1)成立。那么：

　　①不對字符xn+1,xn+2,…, xn+k進行編碼。

　　②對xn+k+1作它的編碼為(K+1,i, xn+k+1)。

　　以此類推，就可以完成對xn的編碼C。

　　2.2 LZW算法的原理

　　LZW算法通過編碼表來組織輸人字符串，并把它們轉換成一定長度的編碼。LZW算法有一個重要的特性稱作前綴性，即如果一個字符串在編碼表上，那它的前綴串也在編碼表上。例如:A、B為兩個不同的字符串，AB組成一新的字符串，A為B的前綴串，如果B在編碼表中，則一定在編碼表中。

　　LZW通過編碼表識別源輸人字符序列，通過向編碼表中增加新的字符串，從而識別更多、更長的字符序列。但由于前綴性的約束，這種識別一般每次只在原來的基礎上增加一個字符，依次進行。同時，由于編碼算法沒有很強的分析功能，使它不知道哪些字符序列將來出現的概率較大，所以它具有一定的盲目性。例如，有一個長度為n的字符序列，LZW編碼表要完全識別它，則至少需要該序列部分或全部重復出現n次。但是，當一個較長的字符串重復出現兩次，我們就能夠容易識別它，而且這樣的字符串再次出現的概率是非常大的。基于這樣一種認識，本文在LZW算法的基礎上，構造了一種新的編碼算法，我們把新算法稱為LZWC編碼算法，一般情況下它對數據的壓縮率比LZW算法有大幅度提高。新算法在最差的情況下可退化成標準的LZW算法。下面對LZWC算法的原理進行詳細的介紹。

　　2 LZWC算法

　　LZWC算法的基本原理是針對源輸人數據中不同特點的數據序列，采用不同的編碼器分別編碼。數據序列的分類則是根據它的特點，通過對原始數據序列的分析來完成。

　　LZWC算法共有兩個編碼器，它們是：

　　(1) 重復編碼器(RepeatCorder)，簡稱RC。

　　(2) LZW編碼器。

　　RC對輸入流中重復的數據進行編碼，剩下的數據由則由LZW編碼器進行編碼。RC編碼器和LZW編碼器的編碼通過LZW編碼器的編碼表統一起來。

　　2.1 LZWC算法的編碼及原理

　　LZWC的算法過程如下：

　　對消息序列xn=x1x2x3…xn從左到右進行閱讀，并以此進行LZWC編碼：

　　(1) 輸入流中的數據x1，x2，…，xn依次經過前緩沖區。

　　(4) 假如還有數據進入緩沖區，則轉1)，繼續此過程。

　　(5) 否則，結束編碼過程。

　　LZWC算法和LZW算法一樣采用編碼表來組織輸入數據，顯然LZW的編碼表中包含RC和LZW兩個編碼器編碼的編碼表。我們分別稱其為編碼表中的RC項和LZW項。這兩項雖然對兩個編碼器來說是通用的，但實現時為了提高編碼表的搜索速度，可以把兩者分開處理。

　　RC的編碼識別很簡單，只在緩沖區中進行，對于較長的重復字符，這種編碼方式簡便易行，效率較高。

　　LZW編碼器編碼不連續的字符，當然是有效的，從而獲得較高的壓縮率。從LZWC編碼過程可以看出，如果RC編碼器在輸入流中找不到滿足條件的字符，則LZW編碼器將獨自編碼輸入數據。這時LZWC算法退化為LZW算法。

　　2.2 LZWC算法的解碼原理

　　LZWC壓縮算法的解碼過程是編碼過程的逆過程，以下是LZWC算法的解碼過程：

　　(1)讀一個編碼(按LZW方式確定的碼長);

　　(2)如果是結束碼，則結束解碼過程;

　　(3)如果是RC標志的編碼，則按照RC編碼規則解碼，輸出原始數據;

　　(4)否則，按LZW方式解碼;

　　(5)譯碼過程結束。

　　2.3 LZWC編碼的算例

　　下面，我們用一個例子來說明LZWC編碼算的過程。例如：假設信源發出的序列為：00110000111011100011001解：依題意，有：信源序列的數據依次經過前緩沖區，則

　　(1)RC編碼器對進入前緩沖區的數據進行檢測，x1=x2，x2≠x3，即：0重復出現2次，符合RC編碼的條件，則00的LZWC編碼為(1，2，0)。

　　(2)RC編碼器繼續對進入前緩沖區的數據進行檢測，x3=x4，x4≠x5，1重復出現2次，符合RC編碼的條件，則11的LZWC編碼為(2，2，1)。

　　(3)RC編碼器繼續對進入前緩沖區的數據進行檢測，x5=x6，x6=x7，x7=x8，x8≠x9，0重復出現4次，符合RC編碼的條件，則0000的LZWC編碼為(3，4，0)。

　　(4)RC編碼器繼續對進入前緩沖區的數據進行檢測，x9=x10，x10=x11，x11≠x12，1重復出現3次，符合RC編碼的條件，則111的LZWC編碼為(4，3，1)。

　　(5)RC編碼器繼續對進入前緩沖區的數據進行檢測，x12≠x13，0僅出現1次，不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則0的LZWC編碼為(5，1，0)。

　　(6)RC編碼器繼續對進入前緩沖區的數據進行檢測，x13=x14，x14=x15，x15≠x16，1重復出現3次，符合RC編碼的條件，則111的LZWC編碼為(6，3，1)。

　　(7)RC編碼器繼續對進入前緩沖區的數據進行檢測，x16=x17，x17=x18，x18≠x19，0重復出現3次，符合RC編碼的條件，則000的LZWC編碼為(7，3，0)。

　　(8)RC編碼器繼續對進入前緩沖區的數據進行檢測，x19=x20，x20≠x21，次，符合RC編碼的條件，則11的LZWC編碼為(8，2，1)，1重復出現2次，符合RC編碼的條件，則11的LZWC編碼為(8，2，1)。

　　(9)RC編碼器繼續對進入前緩沖區的數據進行檢測，x21=x22，x22≠x23，次，符合RC編碼的條件，則00的LZWC編碼為(9，2，0)。

　　(10)RC編碼器繼續對進入前緩沖區的數據進行檢測，x23是最后一個數據，1僅出現1次，不符合RC編碼的條件，所以，不能用RC編碼器對其進行編碼。但是，它符合LZW編碼的條件，由LZW編碼器，則1的LZWC編碼為(10，1，1)。

　　(11)前緩沖區沒有數據通過了，編碼到此結束。

　　所以，信源序列的LZWC編碼為：C′={(1，2，0)，(2，2，1)，(3，4，0)，(4，3，1)，(5，1，0)，(6，3，1)，(7，3，0)，(8，2，1)，(9，2，0)，(10，1，1)}。

　　閱讀范文：計算機論文范文家庭自動化系統

　　本篇文章是由《計算機輔助工程》發表的一篇計算機論文，是上海海事大學主辦的學術性刊物，創刊于1992年，是我國計算機界與工程界的重要學術性刊物之一。本刊主要刊登計算機技術及其應用和相關領域的學術論文，如計算機輔助設計與圖形學技術及應用、專家系統、知識工程、計算機網絡與通信、分布式系統、計算機軟件與理論、程序設計語言、操作系統、數據庫、計算機輔助教學、制造業信息化、物流工程信息化、交通運輸工程信息化、信息管理技術及應用、人工智能技術及應用、電氣自動化等領域的文章，以及有價值的研究報告和研究簡介。