algorithm - LZ77 压缩速度慢
问题描述
我正在使用 LZ77 算法编写简单的压缩程序。我的问题是任何大文件的压缩速度都非常慢(对于 2 MB 图像,如果缓冲区大小为 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);
}
}
解决方案
如前所述,这是您的问题的算法。您可以使用像 deflate 这样的链式哈希或后缀树。
推荐阅读
- python-3.x - 当我们附加数据框时指定行的来源
- api - GET请求返回单个ID信息
- php - 从 JSON 到 PHP Foreach 循环的日期/时间对象
- angular - 如何合并使用 FROM 创建的 observables 数组的所有映射
- java - 使用 asList() 方法时出现编译器错误
- python - 从 groupby 对象中过滤所有行
- rust - 通过本地生命周期来满足特征
- r - 如何让 org-mode 导出宽或长表以便在 PDF 中可读?
- javascript - 在 chrome 扩展中从 api 获取数据的问题
- arrays - 从Ruby中的排序获取数组索引