начать с малого
вы используете файлы, в которых слишком много данных для отладки. Начните с малого со струнных. Я взял этот хороший пример из 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"
Таким образом, вы можете шаг за шагом отлаживать свой код с перекрестным сопоставлением как ввода / вывода, так и содержимого словаря. Как только это будет сделано правильно, вы можете сделать то же самое для декодирования:
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"
Только затем перейдите к файлам и очистите обработку словаря.
битовый поток
после того, как вы успешно выполните LZW на маленьком алфавите, вы можете попробовать использовать полный алфавит и битовую кодировку. Вы знаете, что поток LZW может быть закодирован с любой длиной бит (не только 8/16/32/64 бит), что может сильно повлиять на коэффициент сжатия ios (в отношении используемых свойств данных). Поэтому я бы попытался сделать универсальный доступ к данным с переменной (или предопределенной длиной в битах).
Было немного любопытно, поэтому я закодировал простой пример C ++ / VCL для сжатия:
//---------------------------------------------------------------------------
// 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;
}
//---------------------------------------------------------------------------
и вывод с использованием // test ASCII input строк:
txt="abacdacacadaad"
enc="0102369803"
dec="abacdacacadaad"
, где AnsiString - единственный материал VCL, который я использовал, и это просто саморазмещающаяся строковая переменная, будьте осторожны, ее индексы начинаются с 1.
AnsiString s;
s[5] // character access (1 is first character)
s.Length() // returns size
s.c_str() // returns char*
s.SetLength(size) // resize
Так что просто используйте любую полученную строку ...
Если у вас нет BYTE,DWORD, используйте unsigned char и unsigned int вместо ...
Похоже, он работает и для длинных текстов (больше, чем размер словаря и / или буфера битового потока). Однако имейте в виду, что очистка может выполняться в нескольких разных местах кода, но должна быть синхронизирована в обоих кодировщиках / декодерах, иначе после очистки данные будут повреждены.
В примере может использоваться либо только "a,b,c,d" алфавит, либо полный 8it один. В настоящее время установлен на 8 бит. Если вы хотите изменить его, просто удалите строки // test ASCII input и удалите строки // full 8bit binary alphabet в коде.
Для проверки буферов пересечения и границ вы можете поиграть с:
const int LZW_bits=12; // encoded bitstream size
const int LZW_size=1<<LZW_bits; // dictinary size
, а также с:
const int siz=32; // bitstream buffer
константами ... Они также влияют на производительность, поэтому настройте по вашему вкусу. Помните, что bitstream_write не оптимизирован и может быть значительно ускорен ...
Также для отладки 4-битного выровненного кодирования я использую шестнадцатеричную печать закодированных данных (шестнадцатеричная строка вдвое длиннее, чем его версия ASCII ) вот так (игнорируйте материал VCL):
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())));
и результат:
"abacdacacadaadddddddaaaaaaaabcccddaaaaaaaaa"
"06106206106306410210510406106410FFFFFF910A10706110FFFFFFD10E06206311110910FFFFFFE11410FFFFFFD0"
"abacdacacadaadddddddaaaaaaaabcccddaaaaaaaaa"
ratio: 81%