编码.txt

lzw压缩算法的c语言实现及用C++实现算术编码

算术编码在图象数据压缩标准（如jpeg，jbig）中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码。算术编码用到了两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。 

算术编码需要输入的是符号，各个符号的概率还有需要编码的符号序列，根据概率可以算出初始编码间隔，先设几个变量在后面可用：High——当前编码的上限，Low——当前编码的下限，high——中间变量，用来计算下一个编码符号的当前间隔的上限，low——中间变量，用来计算下一个编码符号的当前间隔的下限，d——当前间隔之间的距离。第1个编码符号的当前间隔为其初始的编码间隔，第i个编码符号的当前间隔为第i-1个编码后的[Low，High），第i 1个编码符号的当前间隔算法如下：high=Low d*第i 1个初始编码符号对应的上限，low=Low d*第i 1个编码符号对应的下限，然后High=high，Low=low，d=d*第i个编码符号的概率。

编码程序如下：

#include 
#define M 100
#define N 4
class suanshu
{ 
int count,length;
char number[N],n;
long double chance[N],c;
char code[M];
long double High,Low,high,low,d;
public:
suanshu()
{High=0;Low=0;}
void get_number();
void get_code();
void coding();
~suanshu(){}
};

void suanshu::get_number()
{
cout<<"please input the number and its chance."< for(int i=0;i {
cin>>n>>c;
number=n;
chance=c;
}
if(i==20)
cout<<"the number is full."< count=i;
}

void suanshu::get_code()
{
cout<<"please input the code's length:";
cin>>length;
while(length>=M)
{
cout<<"the length is too larger,please input a smaller one.";
cin>>length;
}
for(int i=0;i {
cin>>code;
}
}

void suanshu::coding()
{
int i,j=0;
for(i=0;i if(code[0]==number) break;
while(j Low =chance[j ];
d=chance[j];
High=Low d;
for(i=1;i for(j=0;j {
if(code==number[j])
{
if(j==0)
{
low=Low;
high=Low chance[j]*d;
High=high;
d*=chance[j];
}
else
{
float chance_l=0.0;
for(int k=0;k<=j-1;k )
chance_l =chance[k];
low=Low d*chance_l;
high=Low d*(chance_l chance[j]);
Low=low;
High=high;
d*=chance[j];
}
}
else continue;
}
cout<<"the result is:"<}

int main()
{
suanshu a;
a.get_number();
a.get_code();
a.coding();
return 0;
}


lzw压缩算法的c语言实现
1 程序由五个模块组成。

(1) lzw.h 定义了一些基本的数据结构，常量，还有变量的初始化等。

#ifndef __LZW_H__
#define __LZW_H__
//------------------------------------------------------------------------------
#include 
#include 
#include 
#include 
//------------------------------------------------------------------------------
#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 
#include 
#include 
//------------------------------------------------------------------------------
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

(3) hash.h 定义了压缩时所用的码表操作函数，为了快速查找使用了hash算法，还有处理hash冲突的函数

#ifndef __HASH_H__
#define __HASH_H__
//------------------------------------------------------------------------------
#include 
#include 
#include 
//------------------------------------------------------------------------------
#define DIV TABLE_LEN
#define HASHSTEP 13 // It should bigger than 0.
//------------------------------------------------------------------------------
WORD get_hash_index( PLZW_DATA lzw )
{
DWORD tmp;
WORD result;
DWORD prefix;
DWORD suffix;
prefix = lzw->prefix;
suffix = lzw->suffix;
tmp = prefix<<8 | suffix;
result = tmp % DIV;
return result;
}
//------------------------------------------------------------------------------
WORD re_hash_index( WORD hash ) // If hash conflict occured we must recalculate
{ // hash index .
WORD result;
result = hash HASHSTEP;
result = result % DIV;
return result;
}
//------------------------------------------------------------------------------
BOOL in_table( PLZW_DATA lzw ) // To find whether current code is already in table.
{
BOOL result;
WORD hash;

hash = get_hash_index( lzw );
if( lzw->lp_code[ hash ] == 0xFFFF )
{
result = FALSE; 
}
else
{
if( lzw->lp_prefix[ hash ] == lzw->prefix &&
lzw->lp_suffix[ hash ] == lzw->suffix )
{
result = TRUE;
}
else
{
result = FALSE;
while( lzw->lp_code[ hash ] != 0xFFFF )
{
if( lzw->lp_prefix[ hash ] == lzw->prefix &&
lzw->lp_suffix[ hash ] == lzw->suffix )
{
result = TRUE;
break; 
}
hash = re_hash_index( hash );
}
}
}
return result;
}
//------------------------------------------------------------------------------
WORD get_code( PLZW_DATA lzw )
{
WORD hash;
WORD code;
hash = get_hash_index( lzw );
if( lzw->lp_prefix[ hash ] == lzw->prefix &&
lzw->lp_suffix[ hash ] == lzw->suffix )
{
code = lzw->lp_code[ hash ];
}
else
{
while( lzw->lp_prefix[ hash ] != lzw->prefix ||