Я пишу простую программу сжатия по алгоритму LZ77. Моя проблема заключается в очень низкой скорости сжатия любых больших файлов (для изображения размером 2 МБ требуется более 1 минуты, если размер буфера равен 12, а размер словаря равен 4096). Я использую алгоритм Бойера-Мура-Хорспула для поиска текущих префиксов буфера в словаре. Подскажите, пожалуйста, что могло вызвать такое замедление и есть ли способы улучшить производительность этого кода?
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);
}
}