當前位置:首頁 » 編程語言 » c語言實現lzw編碼
擴展閱讀
冰箱存儲奶怎麼熱 2022-08-13 02:32:08

c語言實現lzw編碼

發布時間: 2022-08-06 10:27:20

『壹』 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圖像數據,實現圖像格式的轉換