LZW减压 [英] LZW Decompression
问题描述
我正在用C ++实现LZW算法.
字典的大小是用户输入的，但最小值为256，因此它应适用于二进制文件.如果到达字典的末尾，它将绕到索引0并从那里开始覆盖它.
例如，如果我在妙境脚本中放入 alice 并将其压缩为字典大小512我得到这本字典.
但是我在解压缩和从压缩的文件解压缩输出字典方面有问题看起来像这样./p>
我的解压缩代码如下:
struct字典{向量< unsigned char>入口;向量< bool>位;};无效解压缩(字典dict []，vector< bool>文件，int dictionarySize，int numberOfBits){//在这个例子中//dictionarySize = 512，告知字典的最大大小，如果达到513，则返回0//numberOfBits = log2(512)= 9//dictionary dict []包含位和字符串(字符串可以为空)//dict [0] =//entry =(unsigned char)0//位=(如果numberOfBits = 9)000000001//dict [255] =//entry =(unsigned char)255//位=(如果numberOfBits = 9)011111111//因此下一个条目将是dict [next](下一个当前为256)//dict [256] =//entry =在下面的代码中添加了什么//位= 100000000//所有位均已预先设置(字典大小为int dictionarySize)，因此在这种情况下，所有位(从0到511)都已设置，条目设置为0到255，因此扩展了ASCII向量< bool>currentCode;向量< unsigned char>currentString;向量< unsigned char>温度int next = 256;布尔发现=假;for(int i = 0; i< file.size(); i + = numberOfBits){for(int j = 0; j< numberOfBits; j ++){currentCode.push_back(file [i + j]);}for(int j = 0; j< dictionarySize; j ++){//当在字典中找到currentCode(size numberOfBits)时if(currentCode == dict [j] .bits){currentString = dict [j] .entry;//如果当前字符串不为空，则表示它在字典中找到了字符if(！currentString.empty()){发现=真;}}}//如果字典中的currentCode附加了字符串值如果(找到){for(int j = 0; j< currentString.size(); j ++){cout<< currentString [j];}temp.push_back(currentString [0]);//因此，它不只是将1个字符推入字典//例如，如果第一个读取字符为"r"，则它已经在字典中，因此不会添加if(temp.size()> 1){//如果next大于511，则写入该索引将导致错误，因此它将重置为0并返回if(next> dictionarySize-1)//下一个>512-1{下一个= 0;}dict [next] .entry.clear();dict [next] .entry = temp;下一个++;}//temp = currentString;}别的{currentString = temp;currentString.push_back(temp [0]);for(int j = 0; j< currentString.size(); j ++){cout<< currentString [j];}//如果next大于511，则写入该索引将导致错误，因此它将重置为0并返回if(next> dictionarySize-1){下一个= 0;}dict [next] .entry.clear();dict [next] .entry = currentString;下一个++;//休息;}temp = currentString;//清除currentCode，并在下一次迭代中将其写入currentCode.clear();//cout<< endl;发现=假;}} 我目前处于困境，不知道要在此处解决的问题以修复输出.我还注意到，如果我把字典放的足够大，那么它就不会绕过字典(它不会到达末尾并从0开始重新开始).
-
从小做起
您使用的文件中有太多数据需要调试.从字符串开始.我从 Wikli :
中举了一个很好的例子输入:"abacdacacadaad"步骤输入匹配输出new_entry new_index01122第3天1 abacdacacadaad a 0 ab 42 bacdacacadaad b 1 ba 53 acdacacadaad a 0 ac 64 cdacacadaad c 2 cd 75 dacacadaad d 3 da 86 acacadaad ac 6 aca 97 acadaad aca 9 acad 108天8天11天9广告0广告1210天3天输出:"0102369803"因此，您可以通过交叉匹配输入/输出和字典内容来逐步调试代码.一旦正确完成，就可以对解码进行相同的操作:
输入:"0102369803"步骤输入输出new_entry new_index01122第3天1 0 a2 1 b ab 43 0一ba 54 2交流65 3 d光盘76 6 ac da 87 9 aca aca 98 8天109 0天1110 3 d广告12输出:"abacdacacadaad"然后仅移至文件并清除字典处理.
-
比特流
成功完成小字母的LZW后，您可以尝试使用完整的字母和位编码.您知道LZW流可以以任何位长编码(不仅是8/16/32/64位)，这可以极大地影响压缩率(就使用的数据属性而言).因此，我将尝试对变量(或预定义的位长)处的数据进行统一访问.
有点好奇，所以我为压缩编码了一个简单的C ++/VCL示例:
<代码>//---------------------------------------------------------------------------//LZWconst int LZW_bits = 12;//编码的比特流大小const int LZW_size = 1<< LZW_bits;//字典大小//比特流读/写DWORD bitstream_tmp = 0;//---------------------------------------------------------------------------//从dat [adr，bit]和增量位置(adr，bit)返回LZW_bitsDWORD bitstream_read(BYTE * dat，int siz，int& adr，int& bit，int位){DWORD a ＝ 0，m ＝(1 ＜＜位)-1；//如果有足够的位，则保存tmpif(bit> = bits){a =(bitstream_tmp>(bit-bits))& m;位-=位;返回}为了 (;;){//插入字节bitstream_tmp<< == 8;bitstream_tmp& = 0xFFFFFF00;bitstream_tmp | = dat [adr]& 255;adr ++;位+ = 8;//如果有足够的位，则保存tmpif(bit> = bits){a =(bitstream_tmp>(bit-bits))& m;位-=位;返回}//数据结束如果(adr> = siz)返回0;}}//---------------------------------------------------------------------------//将LZW_bits从a写入dat [adr，bit]并递增位置(adr，bit)//如果缓冲区已满，则返回truebool bitstream_write(BYTE * dat，int siz，int& adr，int& bit，int bits，DWORD a){a<< == 32位;//与MSB对齐//如果对齐则保存tmpif((adr< siz)&&(bit == 32)){dat [adr] =(bitstream_tmp> 24)& 255;adr ++;位= 8;}if((adr< siz)&&(bit == 24)){dat [adr] =(bitstream_tmp> 16)& 255;adr ++;位= 8;}if((adr< siz)&&(bit == 16)){dat [adr] =(bitstream_tmp> 8)& 255;adr ++;位= 8;}if((adr< siz)&&(bit == 8)){dat [adr] =(bitstream_tmp)& 255;adr ++;位= 8;}//处理a的所有位对于(; bits; bits--){//插入位bitstream_tmp<< = 1;bitstream_tmp& = 0xFFFFFFFE;bitstream_tmp | =(a> 31)& 1;a<< = 1;位++;//如果对齐则保存tmpif((adr< siz)&&(bit == 32)){dat [adr] =(bitstream_tmp> 24)& 255;adr ++;位= 8;}if((adr< siz)&&(bit == 24)){dat [adr] =(bitstream_tmp> 16)& 255;adr ++;位= 8;}if((adr< siz)&&(bit == 16)){dat [adr] =(bitstream_tmp> 8)& 255;adr ++;位= 8;}if((adr< siz)&&(bit == 8)){dat [adr] =(bitstream_tmp)& 255;adr ++;位= 8;}}return(adr> = siz);}//---------------------------------------------------------------------------bool str_compare(char * s0，int l0，char * s1，int l1){如果(l1 ＜l0)返回false；为(; l0; l0-，s0 ++，s1 ++)如果(* s0！= * s1)返回false;返回true；}//---------------------------------------------------------------------------AnsiString LZW_encode(AnsiString raw){AnsiString lzw =";int i，j，k，l;int adr，bit;DWORD a;const int siz = 32;//比特流缓冲区BYTE buf [siz];AnsiString dict [LZW_size];//字典int dicts = 0;//字典的实际大小//初始化字典对于(dicts = 0; dicts <256; dicts ++)dict [dicts] = char(dicts);//完整的8位二进制字母//for(dicts = 0; dicts< 4; dicts ++)dict [dicts] = char('a'+ dicts);//测试字母"a，b，c，d"l = raw.Length();adr = 0;位= 0;对于(i = 0; i = LZW_size)dicts = 256;//完整的8位二进制字母//if(dicts> = LZW_size)dicts = 4;//测试字母"a，b，c，d"别的{dict [dicts] = dict [j] + AnsiString(raw [i + 1]);//AnsiString索引从1开始，因此+1dicts ++;}}a = j;j = -1;休息;//完整的二进制输出//a ='0'+ j;j = -1;休息;//测试ASCII输出}//将结果存储到比特流如果(bitstream_write(buf，siz，adr，bit，LZW_bits，a)){//将buf附加到lzwk = lzw.Length();lzw.SetLength(k + adr);对于(j = 0; j = LZW_size){dicts = 4;ix = -1;}//新字典条目如果(ix> = 0){if(a> = dicts){dict [dicts] = dict [ix] + AnsiString(dict [ix] [1]);dicts ++;}else {dict [dicts] = dict [ix] + AnsiString(dict [a] [1]);dicts ++;}} ix = a;//更新解码的输出raw + = dict [a];}退货}//--------------------------------------------------------------------------- 并使用//测试ASCII输入行进行输出:
txt ="abacdacacadaad"enc ="0102369803"dec ="abacdacacadaad" 其中 AnsiString 是我使用的唯一VCL东西，它只是自我分配的字符串变量，请注意其索引始于 1 .
AnsiString s;s [5]//字符访问(1是第一个字符)s.Length()//返回大小s.c_str()//返回char *s.SetLength(size)//调整大小 所以只要使用您得到的任何字符串...
如果您没有 BYTE，DWORD ，请改用 unsigned char 和 unsigned int ...
看起来也可以用于长文本(大于字典和/或位流缓冲区的大小).但是请注意，清除操作可能会在几个不同的代码位置进行，但必须在编码器/解码器中都进行同步，否则清除数据后会损坏数据.
该示例可以仅使用"a，b，c，d" 字母或完整的8it字母.当前设置为8bit.如果要更改它，只需取消//测试ASCII输入行，然后取消代码中的//完整8位二进制字母行.
要测试穿越缓冲区和边界，您可以使用:
const int LZW_bits = 12;//编码的比特流大小const int LZW_size = 1<< LZW_bits;//字典大小 以及:
const int siz = 32;//比特流缓冲区 常量...这也会影响性能，因此请根据自己的喜好进行调整.请注意， bitstream_write 尚未经过优化，可以大大提高速度...
也为了调试4位对齐的编码，我正在使用十六进制打印编码数据(十六进制字符串是其ASCII版本的两倍)，如下所示(忽略VCL内容):
AnsiString txt ="abacdacacadaadddddddaaaaaaaaaccccddaaaaaaaaaaa"，enc，dec，hex;enc = LZW_encode(txt);dec = LZW_decode(enc);//转换为十六进制hex =";for(int i = 1，l = enc.Length(); i <= l; i ++)hex + = AnsiString().sprintf(％02X"，enc [i]);mm_log-> Lines-> Add("\""+ txt +" \");mm_log-> Lines-> Add("\""+ hex +" \");mm_log-> Lines-> Add("\""+ dec +" \");mm_log-> Lines-> Add(AnsiString().sprintf("ratio:％i％"，(100 * enc.Length()/dec.Length())));; 和结果:
"abacdacacadaadddddddaaaaaaaaaccccddaaaaaaaaaaa""06106206106306410210510406106410FFFFFF910A10706110FFFFFFD10E06206311110910FFFFFFE11410FFFFFFD0""abacdacacadaadddddddaaaaaaaabcccddaaaaaaaaaaa"比例:81％ I am implementing a LZW algorithm in C++.
The size of the dictionary is a user input, but the minimum is 256, so it should work with binary files. If it reaches the end of the dictionary it goes around to the index 0 and works up overwriting it from there.
For example, if i put in a alice in wonderland script and compress it with a dictionary size 512 i get this dictionary.
But i have a problem with decompression and the output dictionary from decompressing the compressed file looks like this.
And my code for decompressing looks like this
struct dictionary
{
vector<unsigned char> entry;
vector<bool> bits;
};
void decompress(dictionary dict[], vector<bool> file, int dictionarySize, int numberOfBits)
{
//in this example
//dictionarySize = 512, tells the max size of the dictionary, and goes back to 0 if it reaches 513
//numberOfBits = log2(512) = 9
//dictionary dict[] contains bits and strings (strings can be empty)
// dict[0] =
// entry = (unsigned char)0
// bits = (if numberOfBits = 9) 000000001
// dict[255] =
// entry = (unsigned char)255
// bits = (if numberOfBits = 9) 011111111
// so the next entry will be dict[next] (next is currently 256)
// dict[256] =
// entry = what gets added in the code below
// bits = 100000000
// all the bits are already set previously (dictionary size is int dictionarySize) so in this case all the bits from 0 to 511 are already set, entries are set from 0 to 255, so extended ASCII
vector<bool> currentCode;
vector<unsigned char> currentString;
vector<unsigned char> temp;
int next=256;
bool found=false;
for(int i=0;i<file.size();i+=numberOfBits)
{
for(int j=0;j<numberOfBits;j++)
{
currentCode.push_back(file[i+j]);
}
for(int j=0;j<dictionarySize;j++)
{
// when the currentCode (size numberOfBits) gets found in the dictionary
if(currentCode==dict[j].bits)
{
currentString = dict[j].entry;
// if the current string isnt empty, then it means it found the characted in the dictionary
if(!currentString.empty())
{
found = true;
}
}
}
//if the currentCode in the dictionary has a string value attached to it
if(found)
{
for(int j=0;j<currentString.size();j++)
{
cout<<currentString[j];
}
temp.push_back(currentString[0]);
// so it doesnt just push 1 character into the dictionary
// example, if first read character is 'r', it is already in the dictionary so it doesnt get added
if(temp.size()>1)
{
// if next is more than 511, writing to that index would cause an error, so it resets back to 0 and goes back up
if(next>dictionarySize-1) //next > 512-1
{
next = 0;
}
dict[next].entry.clear();
dict[next].entry = temp;
next++;
}
//temp = currentString;
}
else
{
currentString = temp;
currentString.push_back(temp[0]);
for(int j=0;j<currentString.size();j++)
{
cout<<currentString[j];
}
// if next is more than 511, writing to that index would cause an error, so it resets back to 0 and goes back up
if(next>dictionarySize-1)
{
next = 0;
}
dict[next].entry.clear();
dict[next].entry = currentString;
next++;
//break;
}
temp = currentString;
// currentCode gets cleared, and written into in the next iteration
currentCode.clear();
//cout<<endl;
found = false;
}
}
Im am currently stuck and dont know what to fix here to fix the output. I have also noticed, that if i put a dictionary big enough, so it doesnt go around the dictionary (it doesnt reach the end and begin again at 0) it works.
start small
you are using files that is too much data to debug. Start small with strings. I took this nice example from Wikli:
Input: "abacdacacadaad" step input match output new_entry new_index a 0 b 1 c 2 d 3 1 abacdacacadaad a 0 ab 4 2 bacdacacadaad b 1 ba 5 3 acdacacadaad a 0 ac 6 4 cdacacadaad c 2 cd 7 5 dacacadaad d 3 da 8 6 acacadaad ac 6 aca 9 7 acadaad aca 9 acad 10 8 daad da 8 daa 11 9 ad a 0 ad 12 10 d d 3 Output: "0102369803"So you can debug your code step by step with cross matching both input/output and dictionary contents. Once that is done correctly then you can do the same for decoding:
Input: "0102369803" step input output new_entry new_index a 0 b 1 c 2 d 3 1 0 a 2 1 b ab 4 3 0 a ba 5 4 2 c ac 6 5 3 d cd 7 6 6 ac da 8 7 9 aca aca 9 8 8 da acad 10 9 0 a daa 11 10 3 d ad 12 Output: "abacdacacadaad"Only then move to files and clear dictionary handling.
bitstream
once you succesfully done the LZW on small alphabet you can try to use the full alphabet and bit encoding. You know the LZW stream can be encoded at any bitlength (not just 8/16/32/64 bits) which can greatly affect compression ratios (in respect to used data properties). So I would try to do univeral access to data at variable (or predefined bitlength).
Was a bit curious so I encoded a simple C++/VCL example for the compression:
//---------------------------------------------------------------------------
// LZW
const int LZW_bits=12; // encoded bitstream size
const int LZW_size=1<<LZW_bits; // dictinary size
// bitstream R/W
DWORD bitstream_tmp=0;
//---------------------------------------------------------------------------
// return LZW_bits from dat[adr,bit] and increment position (adr,bit)
DWORD bitstream_read(BYTE *dat,int siz,int &adr,int &bit,int bits)
{
DWORD a=0,m=(1<<bits)-1;
// save tmp if enough bits
if (bit>=bits){ a=(bitstream_tmp>>(bit-bits))&m; bit-=bits; return a; }
for (;;)
{
// insert byte
bitstream_tmp<<=8;
bitstream_tmp&=0xFFFFFF00;
bitstream_tmp|=dat[adr]&255;
adr++; bit+=8;
// save tmp if enough bits
if (bit>=bits){ a=(bitstream_tmp>>(bit-bits))&m; bit-=bits; return a; }
// end of data
if (adr>=siz) return 0;
}
}
//---------------------------------------------------------------------------
// write LZW_bits from a to dat[adr,bit] and increment position (adr,bit)
// return true if buffer is full
bool bitstream_write(BYTE *dat,int siz,int &adr,int &bit,int bits,DWORD a)
{
a<<=32-bits; // align to MSB
// save tmp if aligned
if ((adr<siz)&&(bit==32)){ dat[adr]=(bitstream_tmp>>24)&255; adr++; bit-=8; }
if ((adr<siz)&&(bit==24)){ dat[adr]=(bitstream_tmp>>16)&255; adr++; bit-=8; }
if ((adr<siz)&&(bit==16)){ dat[adr]=(bitstream_tmp>> 8)&255; adr++; bit-=8; }
if ((adr<siz)&&(bit== 8)){ dat[adr]=(bitstream_tmp )&255; adr++; bit-=8; }
// process all bits of a
for (;bits;bits--)
{
// insert bit
bitstream_tmp<<=1;
bitstream_tmp&=0xFFFFFFFE;
bitstream_tmp|=(a>>31)&1;
a<<=1; bit++;
// save tmp if aligned
if ((adr<siz)&&(bit==32)){ dat[adr]=(bitstream_tmp>>24)&255; adr++; bit-=8; }
if ((adr<siz)&&(bit==24)){ dat[adr]=(bitstream_tmp>>16)&255; adr++; bit-=8; }
if ((adr<siz)&&(bit==16)){ dat[adr]=(bitstream_tmp>> 8)&255; adr++; bit-=8; }
if ((adr<siz)&&(bit== 8)){ dat[adr]=(bitstream_tmp )&255; adr++; bit-=8; }
}
return (adr>=siz);
}
//---------------------------------------------------------------------------
bool str_compare(char *s0,int l0,char *s1,int l1)
{
if (l1<l0) return false;
for (;l0;l0--,s0++,s1++)
if (*s0!=*s1) return false;
return true;
}
//---------------------------------------------------------------------------
AnsiString LZW_encode(AnsiString raw)
{
AnsiString lzw="";
int i,j,k,l;
int adr,bit;
DWORD a;
const int siz=32; // bitstream buffer
BYTE buf[siz];
AnsiString dict[LZW_size]; // dictionary
int dicts=0; // actual size of dictionary
// init dictionary
for (dicts=0;dicts<256;dicts++) dict[dicts]=char(dicts); // full 8bit binary alphabet
// for (dicts=0;dicts<4;dicts++) dict[dicts]=char('a'+dicts); // test alphabet "a,b,c,d"
l=raw.Length();
adr=0; bit=0;
for (i=0;i<l;)
{
i&=i;
// find match in dictionary
for (j=dicts-1;j>=0;j--)
if (str_compare(dict[j].c_str(),dict[j].Length(),raw.c_str()+i,l-i))
{
i+=dict[j].Length();
if (i<l) // add new entry in dictionary (if not end of input)
{
// clear dictionary if full
if (dicts>=LZW_size) dicts=256; // full 8bit binary alphabet
// if (dicts>=LZW_size) dicts=4; // test alphabet "a,b,c,d"
else{
dict[dicts]=dict[j]+AnsiString(raw[i+1]); // AnsiString index starts from 1 hence the +1
dicts++;
}
}
a=j; j=-1; break; // full binary output
// a='0'+j; j=-1; break; // test ASCII output
}
// store result to bitstream
if (bitstream_write(buf,siz,adr,bit,LZW_bits,a))
{
// append buf to lzw
k=lzw.Length();
lzw.SetLength(k+adr);
for (j=0;j<adr;j++) lzw[j+k+1]=buf[j];
// reset buf
adr=0;
}
}
if (bit)
{
// store the remainding bits with zeropad
bitstream_write(buf,siz,adr,bit,LZW_bits-bit,0);
}
if (adr)
{
// append buf to lzw
k=lzw.Length();
lzw.SetLength(k+adr);
for (j=0;j<adr;j++) lzw[j+k+1]=buf[j];
}
return lzw;
}
//---------------------------------------------------------------------------
AnsiString LZW_decode(AnsiString lzw)
{
AnsiString raw="";
int adr,bit,siz,ix;
DWORD a;
AnsiString dict[LZW_size]; // dictionary
int dicts=0; // actual size of dictionary
// init dictionary
for (dicts=0;dicts<256;dicts++) dict[dicts]=char(dicts); // full 8bit binary alphabet
// for (dicts=0;dicts<4;dicts++) dict[dicts]=char('a'+dicts); // test alphabet "a,b,c,d"
siz=lzw.Length();
adr=0; bit=0; ix=-1;
for (adr=0;(adr<siz)||(bit>=LZW_bits);)
{
a=bitstream_read(lzw.c_str(),siz,adr,bit,LZW_bits);
// a-='0'; // test ASCII input
// clear dictionary if full
if (dicts>=LZW_size){ dicts=4; ix=-1; }
// new dictionary entry
if (ix>=0)
{
if (a>=dicts){ dict[dicts]=dict[ix]+AnsiString(dict[ix][1]); dicts++; }
else { dict[dicts]=dict[ix]+AnsiString(dict[a ][1]); dicts++; }
} ix=a;
// update decoded output
raw+=dict[a];
}
return raw;
}
//---------------------------------------------------------------------------
and output using // test ASCII input lines:
txt="abacdacacadaad"
enc="0102369803"
dec="abacdacacadaad"
where AnsiString is the only VCL stuff I used and its just self allocating string variable beware its indexes starts at 1.
AnsiString s;
s[5] // character access (1 is first character)
s.Length() // returns size
s.c_str() // returns char*
s.SetLength(size) // resize
So just use any string you got ...
In case you do not have BYTE,DWORD use unsigned char and unsigned int instead ...
Looks like its working for long texts too (bigger than dictionary and or bitstream buffer sizes). However beware that the clearing might be done in few different places of code but must be synchronized in both encoder/decoder otherwise after clearing the data would corrupt.
The example can use either just "a,b,c,d" alphabet or full 8it one. Currently is set for 8bit. If you want to change it just un-rem the // test ASCII input lines and rem out the // full 8bit binary alphabet lines in the code.
To test crossing buffers and boundary you can play with:
const int LZW_bits=12; // encoded bitstream size
const int LZW_size=1<<LZW_bits; // dictinary size
and also with:
const int siz=32; // bitstream buffer
constants... The also affect performance so tweak to your liking.
Beware the bitstream_write is not optimized and can be speed up considerably ...
Also in order to debug 4bit aligned coding I am using hex print of encoded data (hex string is twice as long as its ASCII version) like this (ignore the VCL stuff):
AnsiString txt="abacdacacadaadddddddaaaaaaaabcccddaaaaaaaaa",enc,dec,hex;
enc=LZW_encode(txt);
dec=LZW_decode(enc);
// convert to hex
hex=""; for (int i=1,l=enc.Length();i<=l;i++) hex+=AnsiString().sprintf("%02X",enc[i]);
mm_log->Lines->Add("\""+txt+"\"");
mm_log->Lines->Add("\""+hex+"\"");
mm_log->Lines->Add("\""+dec+"\"");
mm_log->Lines->Add(AnsiString().sprintf("ratio: %i%",(100*enc.Length()/dec.Length())));
and result:
"abacdacacadaadddddddaaaaaaaabcccddaaaaaaaaa"
"06106206106306410210510406106410FFFFFF910A10706110FFFFFFD10E06206311110910FFFFFFE11410FFFFFFD0"
"abacdacacadaadddddddaaaaaaaabcccddaaaaaaaaa"
ratio: 81%
这篇关于LZW减压的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
