LZ77压缩速度慢

Question

我正在使用LZ77算法编写简单的压缩程序。我的问题是对任何大文件的压缩速度都很慢(对于2MB图像，如果缓冲区大小为12，字典大小为4096，则需要超过1分钟(。我使用Boyer-Moore Horspool算法在字典中搜索当前缓冲区前缀。请告诉我是什么原因导致了这种速度减慢，有什么方法可以提高代码的性能吗？

void findLongestMatch(unsigned char* d, unsigned char* b, short &len, short &off)
{
short alphabet[256];
short shift = 0;
short dict_pos=0;
bool found = false;
if(cur_dict_length==0) { return; }
for(int prefix_length=cur_buf_length-1; prefix_length>=0; prefix_length--)
{
found=false;
for(int j=0; j<256; j++)
{
alphabet[j]=prefix_length+1;
}
for(int j=prefix_length; j>=1; j--)
{
alphabet[(unsigned char)b[j]]=j;
}
shift = 0;
dict_pos = cur_dict_length-(prefix_length+1);
while(dict_pos>=0)
{
if(memcmp(&d[dict_pos], &b[0], prefix_length+1)==0)
{
found=true;
len=prefix_length+1;
off=cur_dict_length-dict_pos;
break;
}
shift = alphabet[(unsigned char)d[dict_pos]];
dict_pos = dict_pos-shift;
}
if(found==true) break;
}
return;
}
void compressData(long block_size, unsigned char* s, fstream &file_out)
{
unsigned char buf_out[3];
unsigned char* dict;
unsigned char* buf;
link myLink;
file_out.seekp(0, ios_base::beg);
cur_dict_length = 0;
cur_buf_length = buf_length;
for(int i=0; i<block_size; i++)
{
buf=&s[i];
dict=&s[i-cur_dict_length];
myLink.length=0;myLink.offset=0;
findLongestMatch(dict,buf,myLink.length,myLink.offset);
if(myLink.length<=buf_length) myLink.next=buf[myLink.length];
else myLink.next=s[i];
compactLink(myLink, buf_out);
for(int j=0; j<3; j++)
{
file_out << buf_out[j];
}
i=i+myLink.length;
if(cur_dict_length<dict_length) {
cur_dict_length=cur_dict_length+1+myLink.length;
if(cur_dict_length>dict_length) cur_dict_length=dict_length;
}
if(i+cur_buf_length>=block_size) cur_buf_length=cur_buf_length-1-(i+cur_buf_length-block_size);
}
}

Answer 1

如前所述，这是您的问题所在。您可以使用类似deflate的链式散列，也可以使用后缀树。