‘壹’ 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：结束译码 。
‘贰’ 跪求c语言进行哈夫曼编码、算术编码和LZW编码，要求源程序要有注释。
以下是哈夫曼编码
#include<iostream>
#include<math.h>
#include<string>
#include<iomanip>
using namespace std;
int n;
int isin(string str,char a)
{
int temp=0;
for(int i=0;i<str.length();i++)
{
if(str[i]==a) temp=1;
}
return temp;
}
void bubble(double p[],string sign[])//排序
{
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(p[i]<p[j])
{
double temp=p[i];
p[i]=p[j];
p[j]=temp;
string m=sign[i];
sign[i]=sign[j];
sign[j]=m;
}
}
}
}
void huff(double tempp[],string tempstr[])
{
double p[20][20];
string sign[20][20];
sign[0][i]=tempstr[i]; //符号放在sign数组中
for(int i=0;i<n;i++)
{
p[0][i]=tempp[i]; //p数组放对应的概率(第1列中)
}
for(i=0;i<n-1;i++)
{
bubble(p[i],sign[i]); //第一次排序
for(int j=0;j<n-2-i;j++)
{
p[i+1][j]=p[i][j]; //前n-2-i个概率重新放在p数组中(是数组的第2列中)
sign[i+1][j]=sign[i][j];
}
p[i+1][j]=p[i][j]+p[i][j+1];//第一次两个最小概率求和
sign[i+1][j]=sign[i][j]+sign[i][j+1];//符号跟随
for(j=n-1-i;j<n;j++)
{
p[i+1][j]=0;
}
}
string final[20];
for(i=n-2;i>=0;i--)
{
for(int k=0;k<n;k++)
{
if(isin(sign[i][n-2-i],sign[0][k][0])) final[k]+="0";
if(isin(sign[i][n-1-i],sign[0][k][0])) final[k]+="1";
}
}
cout<<setw(9)<<"哈弗曼编码如下:"<<endl;
for(i=0;i<n;i++)
{
cout<<setw(7)<<sign[0][i]<<setw(7)<<p[0][i]<<setw(10)<<final[i]<<
setw(7)<<final[i].length()<<endl;
}
}
void main()
{
char a[50];
cout<<"该字符串符号为:";
cin>>a;
string s=a;
n=s.length();
char b[20][2];
for(int i=0;i<n;i++)
{
b[i][0]=a[i];
b[i][1]='\0';
}
string str[20];
for(i=0;i<n;i++)
{
str[i]=b[i];
}
double tempp[20];
cout<<"字符概率依次为：";
for(i=0;i<n;i++)
{
cin>>tempp[i];
}
huff(tempp,str);
}
‘叁’ 在确定LZW算法C语言源代码后，如何压缩才能使代码直接运行而不需要在VC++环境下才能运行
源代码经过一次编译、链接后，在工程目录下会有个Debug（或者Release）文件夹，里面有个.exe的文件，是可以直接运行的！
‘肆’ 谁能提供个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码编、解码的Matlab实现程序！
文件1
function [output,table] = lzw2norm(vector)
%LZW2NORM LZW Data Compression (decoder)
% For vectors, LZW2NORM(X) is the uncompressed vector of X using the LZW algorithm.
% [...,T] = LZW2NORM(X) returns also the table that the algorithm proces.
%
% For matrices, X(:) is used as input.
%
% Input must be of uint16 type, while the output is a uint8.
% Table is a cell array, each element containig the corresponding code.
%
% This is an implementation of the algorithm presented in the article
% http://www.dogma.net/markn/articles/lzw/lzw.htm
%
% See also NORM2LZW
% $Author: Giuseppe Ridino' $
% $Revision: 1.0 $ $Date: 10-May-2004 14:16:08 $
% How it decodes:
%
% Read OLD_CODE
% output OLD_CODE
% CHARACTER = OLD_CODE
% WHILE there are still input characters DO
% Read NEW_CODE
% IF NEW_CODE is not in the translation table THEN
% STRING = get translation of OLD_CODE
% STRING = STRING+CHARACTER
% ELSE
% STRING = get translation of NEW_CODE
% END of IF
% output STRING
% CHARACTER = first character in STRING
% add translation of OLD_CODE + CHARACTER to the translation table
% OLD_CODE = NEW_CODE
% END of WHILE
% ensure to handle uint8 input vector
if ~isa(vector,'uint16'),
error('input argument must be a uint16 vector')
end
% vector as a row
vector = vector(:)';
% initialize table (don't use cellstr because char(10) will be turned to empty!!!)
table = cell(1,256);
for index = 1:256,
table{index} = uint16(index-1);
end
% initialize output
output = uint8([]);
code = vector(1);
output(end+1) = code;
character = code;
for index=2:length(vector),
element = vector(index);
if (double(element)+1)>length(table),
% add it to the table
string = table{double(code)+1};
string = [string character];
else,
string = table{double(element)+1};
end
output = [output string];
character = string(1);
[table,code] = addcode(table,[table{double(code)+1} character]);
code = element;
end
% ###############################################
function code = getcodefor(substr,table)
code = uint16([]);
if length(substr)==1,
code = substr;
else, % this is to skip the first 256 known positions
for index=257:length(table),
if isequal(substr,table{index}),
code = uint16(index-1); % start from 0
break
end
end
end
% ###############################################
function [table,code] = addcode(table,substr)
code = length(table)+1; % start from 1
table{code} = substr;
code = uint16(code-1); % start from 0
文件2
%LZW DEMO 1
% $Author: Giuseppe Ridino' $
% $Revision: 1.0 $ $Date: 10-May-2004 14:16:08 $
% string to compress
str = '/WED/WE/WEE/WEB/WET';
% pack it
[packed,table]=norm2lzw(uint8(str));
% unpack it
[unpacked,table]=lzw2norm(packed);
% transfor it back to char array
unpacked = char(unpacked);
% test
isOK = strcmp(str,unpacked)
% show new table elements
strvcat(table{257:end})
文件3
function [output,table] = norm2lzw(vector)
%NORM2LZW LZW Data Compression (encoder)
% For vectors, NORM2LZW(X) is the compressed vector of X using the LZW algorithm.
% [...,T] = NORM2LZW(X) returns also the table that the algorithm proces.
%
% For matrices, X(:) is used as input.
%
% Input must be of uint8 type, while the output is a uint16.
% Table is a cell array, each element containig the corresponding code.
%
% This is an implementation of the algorithm presented in the article
% http://www.dogma.net/markn/articles/lzw/lzw.htm
%
% See also LZW2NORM
% $Author: Giuseppe Ridino' $
% $Revision: 1.0 $ $Date: 10-May-2004 14:16:08 $
% How it encodes:
%
% STRING = get input character
% WHILE there are still input characters DO
% CHARACTER = get input character
% IF STRING+CHARACTER is in the string table then
% STRING = STRING+character
% ELSE
% output the code for STRING
% add STRING+CHARACTER to the string table
% STRING = CHARACTER
% END of IF
% END of WHILE
% output the code for STRING
% ensure to handle uint8 input vector
if ~isa(vector,'uint8'),
error('input argument must be a uint8 vector')
end
% vector as uint16 row
vector = uint16(vector(:)');
% initialize table (don't use cellstr because char(10) will be turned to empty!!!)
table = cell(1,256);
for index = 1:256,
table{index} = uint16(index-1);
end
% initialize output
output = vector;
% main loop
outputindex = 1;
startindex = 1;
for index=2:length(vector),
element = vector(index);
substr = vector(startindex:(index-1));
code = getcodefor([substr element],table);
if isempty(code),
% add it to the table
output(outputindex) = getcodefor(substr,table);
[table,code] = addcode(table,[substr element]);
outputindex = outputindex+1;
startindex = index;
else,
% go on looping
end
end
substr = vector(startindex:index);
output(outputindex) = getcodefor(substr,table);
% remove not used positions
output((outputindex+1):end) = [];
% ###############################################
function code = getcodefor(substr,table)
code = uint16([]);
if length(substr)==1,
code = substr;
else, % this is to skip the first 256 known positions
for index=257:length(table),
if isequal(substr,table{index}),
code = uint16(index-1); % start from 0
break
end
end
end
% ###############################################
function [table,code] = addcode(table,substr)
code = length(table)+1; % start from 1
table{code} = substr;
code = uint16(code-1); % start from 0
‘陆’ 急求lzw算法的英文文本压缩C语言源代码！
#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;
‘柒’ 一个字符串由ABC三种字符组成,用LZW对ABABCBABABA编码 急！！
根据LZW压缩算法，计算如下：
串表：A, B, C, AB, BA, ABC, CB, BAB, BABA
编码输出：A, B, AB, C, BA, BAB, A
‘捌’ 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。
‘玖’ 如何用c语言编一个程序把一个c语言的数组（如图片信息）转化成一个.mif文件
同意楼上意见，自己写（如果不用API），难度不小，用第三方的API接口，就简单多了，例如，你导入一张图片--->调用某个API（转化函数接口，这个接口我还真没有过，）--->产生.mif文件,大体就是这样
在网上找了一个其他的思路供参考下
在VC++环境下BMP图像文件与GIF图像文件的转换。首先分析了BMP与GIF2种图像的具体格式,然后在VC++环境下建立自己的函数库文件DIB.H和DIB.CPP,对即将使用的数据成员和函数成员进行初始化,从而实现BMP图像的读取、显示和保存等相关操作。在理解LZW编码算法原理的基础上,在VC++下实现该算法。同时,通过前面建立的BMP图像函数库,调用相关函数,就可以找到相应的具体的图像数据,进而通过LZW编码将BMP图像数据转换成GIF图像数据,实现图像格式的转换