LZW演算法

『壹』 LZW演算法問題

LZW演算法全名叫做Lempel-Ziv-Welch Encoding，是一種數據壓縮演算法，它是有專利的，不過現今大部分專利都己經過期。它可以對文本進行簡單的壓縮，壓縮比對於一般場合還是可以適用的，另外使用的比較多的就是GIF圖像了。
LZW演算法中有幾個比較重要的概念：字元，字元串，編碼表。它把數據流看成一個字元序列，並將字元序列組織成一系列的字元串，並給每個字元串一個編碼，最後存儲的就是字元串的編碼，這樣就節省了空間。如將ababba表示為編碼1532，而1523用12bit就可以表示出來，比原來5*8bit就節省了不少空間。LZW的編碼表是動態創建的，並且通過編碼後的數據流可以恢復出與編碼時同樣的編碼表，這樣在數據存儲與傳輸的時候就不需要保存原始的編碼表，這也是與一些在編碼之前就有固定的編碼表的演算法有著巨大的區別。
1.編碼過程：
LZW是一個固長編碼的演算法的，即對於每一個字元或字元串的編碼都是等長的。為了說明的方便，我決定用16bit作為編碼，前255作為字元編碼，256，257另作它用，這將在3中進行說明。所以字元串的編碼將從258開始。
編碼的整個過程如下：
1. 初始化編碼表，編碼起始號，並置當前字元串為空；
2. 讀入一個字元，如果為EOF，輸出當前字元串，並結束，否則進入3；
3. 將新讀入的字元與當前字元串組成新的字元串，如果新的字元串在編碼表中出現，則繼續進行2，否則進入4；
4. 將新的字元串加入到編碼表中，分配編號，設當前字元串的長度為N，輸入新字元串的N-1長度前綴的編碼，並將當前字元串置為當前字元串的一個長度為1的後綴，再執行2。

2.解碼過程：
對於解碼，唯一需要知道的就是編碼的長度了，每次從編碼流中讀取相應bit的長度，就形成一個編碼，再通過該編碼從編碼表中找出相對應的串輸出即可。由於沒有存儲編碼時對應的編碼表，在解碼時需要同時構造編碼表。
解碼過程如下：
1. 初始化編碼表，並置前一個編碼為空；
2. 取一個編碼，如果編碼為結束，則結束。否則進行3；
3. 輸出編碼所代表的字元串，如果前一個編碼不為空，將前一個編碼的字元串與當前字元串的第一個字元作為新的串加入編碼表中，置前一個編碼為當前編碼，並執行2。

『貳』 LZW演算法的LZW演算法簡介

字元串和編碼的對應關系是在壓縮過程中動態生成的，並且隱含在壓縮數據中，解壓的時候根據表來進行恢復，算是一種無損壓縮.
根據 Lempel-Ziv-Welch Encoding ，簡稱 LZW 的壓縮演算法，用任何一種語言來實現它.
LZW壓縮演算法 的基本概念：LZW壓縮有三個重要的對象：數據流（CharStream）、編碼流（CodeStream）和編譯表（String Table）。在編碼時，數據流是輸入對象（文本文件的據序列），編碼流就是輸出對象（經過壓縮運算的編碼數據）；在解碼時，編碼流則是輸入對象，數據流是輸出對象；而編譯表是在編碼和解碼時都須要用藉助的對象。
字元（Character）：最基礎的數據元素，在文本文件中就是一個位元組，在光柵數據中就是一個像素的顏色在指定的顏色列表中的索引值；
字元串（String）：由幾個連續的字元組成；
前綴（Prefix）：也是一個字元串，不過通常用在另一個字元的前面，而且它的長度可以為0；
根（Root）：一個長度的字元串；
編碼（Code）：一個數字，按照固定長度（編碼長度）從編碼流中取出，編譯表的映射值；圖案：一個字元串，按不定長度從數據流中讀出，映射到編譯表條目.
LZW壓縮演算法 的基本原理：提取原始文本文件數據中的不同字元，基於這些字元創建一個編譯表，然後用編譯表中的字元的索引來替代原始文本文件數據中的相應字元，減少原始數據大小。看起來和調色板圖象的實現原理差不多，但是應該注意到的是，我們這里的編譯表不是事先創建好的，而是根據原始文件數據動態創建的，解碼時還要從已編碼的數據中還原出原來的編譯表.

『叄』 關於LZW的演算法硬體實現

xzxzcvxzcvxzcxzcv

『肆』 LZW演算法的LZW演算法

LZW演算法基於轉換串表（字典）T，將輸入字元串映射成定長（通常為12位）的碼字。在12位4096種可能的代碼中，256個代表單字元，剩下3840給出現的字元串。
LZW字典中的字元串具有前綴性，即 ωK∈T=>；ωT。
LZW演算法流程：
步驟1： 開始時的詞典包含所有可能的根(Root)，而當前前綴P是空的；步驟2： 當前字元(C) ：=字元流中的下一個字元；步驟3： 判斷綴-符串P+C是否在詞典中(1) 如果「是」：P ：= P+C // (用C擴展P) ；(2) 如果「否」① 把代表當前前綴P的碼字輸出到碼字流;② 把綴-符串P+C添加到詞典;③ 令P ：= C //(現在的P僅包含一個字元C);步驟4： 判斷碼字流中是否還有碼字要譯(1) 如果「是」，就返回到步驟2；(2) 如果「否」① 把代表當前前綴P的碼字輸出到碼字流;② 結束。 具體解壓步驟如下：
(1)解碼開始時Dictionary包含所有的根。
(2)讀入在編碼數據流中的第一個碼字 cW(它表示一個Root)。
(3)輸出String.cW到字元數據流Charstream。
(4)使pW=cW 。
(5)讀入編碼數 據流 的下一個碼字cW 。
(6)目前在字典中有String.cW嗎?
YES：1)將String．cW輸出給字元數據流；
2)使P=String.pW；
3)使C=String.cW的第一個字元；
4)將字元 串P+C添 加進Dictionray。
NO ：1)使P=String.pW ；
2)使C=String.pW的第一個字元；
3)將字元串P+C輸出到字元數據流並將其添加進Dictionray(現在它與cW相一致)。
(7)在編碼數據 流中還有Codeword嗎?
YES：返回(4)繼 續進行 解碼 。
NO：結束解碼 。

『伍』 誰能提供個lzw壓縮演算法的c語言完整實現

程序由五個模塊組成。(1) lzw.h 定義了一些基本的數據結構，常量，還有變數的初始化等。#ifndef __LZW_H__
#define __LZW_H__
//------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <memory.h>
//------------------------------------------------------------------------------
#define LZW_BASE 0x102// The code base
#define CODE_LEN 12 // Max code length
#define TABLE_LEN 4099 // It must be prime number and bigger than 2^CODE_LEN=4096.
// Such as 5051 is also ok.
#define BUFFERSIZE 1024
//------------------------------------------------------------------------------
typedef struct
{
HANDLE h_sour; // Source file handle.
HANDLE h_dest; // Destination file handle.

HANDLE h_suffix; // Suffix table handle.
HANDLE h_prefix; // Prefix table handle.
HANDLE h_code; // Code table handle.

LPWORD lp_prefix; // Prefix table head pointer.
LPBYTE lp_suffix; // Suffix table head pointer.
LPWORD lp_code; // Code table head pointer. WORD code;
WORD prefix;
BYTE suffix; BYTE cur_code_len; // Current code length.[ used in Dynamic-Code-Length mode ]}LZW_DATA,*PLZW_DATA;
typedef struct
{
WORD top;
WORD index; LPBYTE lp_buffer;
HANDLE h_buffer;

BYTE by_left;
DWORD dw_buffer; BOOL end_flag;}BUFFER_DATA,*PBUFFER_DATA;
typedef struct //Stack used in decode
{
WORD index;
HANDLE h_stack;
LPBYTE lp_stack;}STACK_DATA,*PSTACK_DATA;
//------------------------------------------------------------------------------
VOID stack_create( PSTACK_DATA stack )
{
stack->h_stack = GlobalAlloc( GHND , TABLE_LEN*sizeof(BYTE) );
stack->lp_stack = GlobalLock( stack->h_stack );
stack->index = 0;
}
//------------------------------------------------------------------------------
VOID stack_destory( PSTACK_DATA stack )
{
GlobalUnlock( stack->h_stack );
GlobalFree ( stack->h_stack );
}
//------------------------------------------------------------------------------
VOID buffer_create( PBUFFER_DATA buffer )
{
buffer->h_buffer = GlobalAlloc( GHND, BUFFERSIZE*sizeof(BYTE) );
buffer->lp_buffer = GlobalLock( buffer->h_buffer );
buffer->top = 0;
buffer->index = 0;
buffer->by_left = 0;
buffer->dw_buffer = 0;
buffer->end_flag = FALSE;
}
//------------------------------------------------------------------------------
VOID buffer_destory( PBUFFER_DATA buffer )
{
GlobalUnlock( buffer->h_buffer );
GlobalFree ( buffer->h_buffer );
}
//------------------------------------------------------------------------------
VOID re_init_lzw( PLZW_DATA lzw ) //When code table reached its top it should
{ //be reinitialized.
memset( lzw->lp_code, 0xFFFF, TABLE_LEN*sizeof(WORD) );
lzw->code = LZW_BASE;
lzw->cur_code_len = 9;
}
//------------------------------------------------------------------------------
VOID lzw_create(PLZW_DATA lzw, HANDLE h_sour, HANDLE h_dest)
{
WORD i;
lzw->h_code = GlobalAlloc( GHND, TABLE_LEN*sizeof(WORD) );
lzw->h_prefix = GlobalAlloc( GHND, TABLE_LEN*sizeof(WORD) );
lzw->h_suffix = GlobalAlloc( GHND, TABLE_LEN*sizeof(BYTE) );
lzw->lp_code = GlobalLock( lzw->h_code );
lzw->lp_prefix = GlobalLock( lzw->h_prefix );
lzw->lp_suffix = GlobalLock( lzw->h_suffix );
lzw->code = LZW_BASE;
lzw->cur_code_len = 9;
lzw->h_sour = h_sour;
lzw->h_dest = h_dest;
memset( lzw->lp_code, 0xFFFF, TABLE_LEN*sizeof(WORD) );}
//------------------------------------------------------------------------------
VOID lzw_destory(PLZW_DATA lzw)
{
GlobalUnlock( lzw->h_code );
GlobalUnlock( lzw->h_prefix );
GlobalUnlock( lzw->h_suffix );GlobalFree( lzw->h_code );
GlobalFree( lzw->h_prefix );
GlobalFree( lzw->h_suffix );
}
//------------------------------------------------------------------------------
#endif(2) fileio.h 定義了一些文件操作#ifndef __FILEIO_H__
#define __FILEIO_H__
//------------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
//------------------------------------------------------------------------------
HANDLE file_handle(CHAR* file_name)
{
HANDLE h_file;
h_file = CreateFile(file_name,
GENERIC_READ|GENERIC_WRITE,
FILE_SHARE_READ|FILE_SHARE_WRITE,
NULL,
OPEN_ALWAYS,
0,
NULL
);
return h_file;
}
//------------------------------------------------------------------------------
WORD load_buffer(HANDLE h_sour, PBUFFER_DATA buffer) // Load file to buffer
{
DWORD ret;
ReadFile(h_sour,buffer->lp_buffer,BUFFERSIZE,&ret,NULL);
buffer->index = 0;
buffer->top = (WORD)ret;
return (WORD)ret;
}
//------------------------------------------------------------------------------
WORD empty_buffer( PLZW_DATA lzw, PBUFFER_DATA buffer)// Output buffer to file
{

DWORD ret;
if(buffer->end_flag) // The flag mark the end of decode
{
if( buffer->by_left )
{
buffer->lp_buffer[ buffer->index++ ] = (BYTE)( buffer->dw_buffer >> 32-buffer->by_left )<<(8-buffer->by_left);
}
}
WriteFile(lzw->h_dest, buffer->lp_buffer,buffer->index,&ret,NULL);
buffer->index = 0;
buffer->top = ret;
return (WORD)ret;
}
//------------------------------------------------------------------------------
#endif

『陸』 LZW演算法的LZW壓縮的特點

LZW碼能有效利用字元出現頻率冗餘度進行壓縮，且字典是自適應生成的，但通常不能有效地利用位置冗餘度。
具體特點如下：
l)LZW壓縮技術對於可預測性不大的數據具有較好的處理效果，常用於TIF格式的圖像壓縮，其平均壓縮比在2：1以上，最高壓縮比可達到3：1。
2）對於數據流中連續重復出現的位元組和字串，LZW壓縮技術具有很高的壓縮比。
3）除了用於圖像數據處理以外，LZW壓縮技術還被用於文本程序等數據壓縮領域。
4)LZW壓縮技術有很多變體，例如常見的ARC、RKARC、PKZIP高效壓縮程序。
5）對於任意寬度和像素位長度的圖像，都具有穩定的壓縮過程。壓縮和解壓縮速度較快。
6）對機器硬體條件要求不高，在 Intel 80386的計算機上即可進行壓縮和解壓縮。

『柒』 LZW演算法解題

拆

『捌』 lzw和lz78演算法的核心思想是什麼他們之間有什麼差別

LZ78是每讀入一個字元的同時，將其編入自己的字典，然後，再讀入字元的同時，則在已有的字典里查找，沒有的話該字元就在新編入辭典。如此循環。
LZW是先建立了ASCII碼的字典，這樣就事先花費了8個位元組（256個ASCII碼）的存儲空間，然後再像LZ78一樣讀入字元，沒有的再進行編入字典，如此循環。

『玖』 求LZW演算法源代碼！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>//用來計算壓縮的時間
using namespace std;

//定義常數
const int MAX = 1000003;//最大code數，是一個素數，求模是速度比較快
const int ascii = 256; //ascii代碼的數量
const int ByteSize = 8; //8個位元組

struct Element//hash表中的元素
{
int key;
int code;
Element *next;
}*table[MAX];//hash表

int hashfunction(int key)//hash函數
{
return key%MAX;
}
void hashinit(void)//hash表初始化
{
memset(table,0,sizeof(table));
}
void hashinsert(Element element)//hash表的插入
{
int k = hashfunction(element.key);
if(table[k]!=NULL)
{
Element *e=table[k];
while(e->next!=NULL)
{
e=e->next;
}
e->next=new Element;
e=e->next;
e->key = element.key;
e->code = element.code;
e->next = NULL;
}
else
{
table[k]=new Element;
table[k]->key = element.key;
table[k]->code = element.code;
table[k]->next = NULL;
}
}
bool hashfind(int key,Element &element)//hash表的查找
{
int k = hashfunction(key);
if(table[k]!=NULL)
{
Element *e=table[k];
while(e!=NULL)
{
if(e->key == key)
{
element.key = e->key;
element.code = e->code;
return true;
}
e=e->next;
}
return false;
}
else
{
return false;
}
}
void compress(void)//壓縮程序
{
//打開一個流供寫入
FILE *fp;
fp = fopen("result.dat", "wb");

Element element;
int used;
char c;
int pcode, k;

for(int i=0;i<ascii;i++)
{
element.key = i;
element.code = i;
hashinsert(element);
}
used = ascii;

c = getchar();
pcode = c;
while((c = getchar()) != EOF)
{
k = (pcode << ByteSize) + c;
if(hashfind(k, element))
pcode = element.code;
else
{
//cout<<pcode<<' ';
fwrite(&pcode, sizeof(pcode), 1, fp);
element.code = used++;
element.key = (pcode << ByteSize) | c;
hashinsert(element);
pcode = c;
}
}
//cout<<pcode<<endl;
fwrite(&pcode, sizeof(pcode), 1, fp);

}
int main(void)
{
int t1,t2;

//欲壓縮的文本文件
//freopen("input.txt","r",stdin);
freopen("book5.txt","r",stdin);

t1=time(NULL);
hashinit();
compress();
t2=time(NULL);

cout<<"Compress complete! See result.dat."<<endl;
cout<<endl<<"Total use "<<t2-t1<<" seconds."<<endl;
}