Zynq 高层次综合HLS 项目开发经历(2) LZ77 x86软件实现

LZ77的x86软件实现repo地址可参见[1]。

要想实现软件,肯定需要把LZ77的算法读懂。慢慢啃就是了。我查询的参考资料可参见[2]。我主要参考了其中的“短语字典的维护”、“压缩和解压缩数据”、“LZ77的接口定义”三部分。而实现与定义则完全由自己制定。

我的LZ77算法要达到的目标是压缩二进制数据,对于一个Byte,有256种可能。对于“短语标记”,必须加上相应的定界符作为标志。因此对于定界符在普通数据中出现的情况,必须进行转义(Escape)。我选择的转义符和定界符(Escape Char)是反斜杠(\)[3]。即:[4]

对于符号标记:如果非转义符,原样输出;如果为转义符,输出两个转义符。
对于短语标记:边界输出一个转义符以标记其为短语。

此时,短语标记的结构伪代码如下:

1
2
3
4
5
6
7
struct phrase{
int8 escape_start; //反斜杠
int32 slide_window_offset;
int32 origin_string_length;
int8 buffer_first_char;
int8 escape_end; //反斜杠
};

但是,在后面调试时发现了短语标记的结构定义存在问题。对于x86体系结构,数字是小端法存储的。当slide_window_offset的最低字节是0x5c,也即反斜杠时。就出现了两个转义符相连的情况。解压程序就会将短语标记的开始识别为符号标记,这是严重错误的。为了避免这个问题,加入一个split_char(\0即字符串结束符,为0x00[5]),放在escape_start后面和escape_end前面。这样escape_start后面绝对不会再跟一个escape,也就避免了上述问题的发生。此时,短语标记的结构伪代码如下:

1
2
3
4
5
6
7
8
9
struct phrase{
int8 escape_start; //反斜杠
int8 split_start; //0x00
int32 slide_window_offset;
int32 origin_string_length;
int8 buffer_first_char;
int8 split_end; //0x00
int8 escape_end; //反斜杠
};

再一个问题,当待压缩文件末尾恰好可以以一个短语标记代替时,前向缓冲区中的第一个符号(即buffer_first_char)为空,需要进行特殊标记。我选择两个右方括号0x5d进行代替[6]。并在解压缩时进行特判[7]。

实际上,对于getLongestMatchingPhrase函数来说,可以使用KMP算法进行优化。当前的暴力做法复杂度O(N^2),而KMP做法可以做到O(N+M)。[8]

参考:
[1]: LZ77-Demo,LZ77算法的x86软件实现: https://github.com/bjrjk/LZ77-Demo
[2]: 数据压缩算法—LZ77算法 的分析与实现: https://www.cnblogs.com/idreamo/p/9249367.html
[3]: https://github.com/bjrjk/LZ77-Demo/blob/5b6e718cd45cbe337a0eac04eb685cd7e7ad4549/LZ77-Demo/lz77.cpp#L9
[4]: https://github.com/bjrjk/LZ77-Demo/blob/5b6e718cd45cbe337a0eac04eb685cd7e7ad4549/LZ77-Demo/lz77.cpp#L11
[5]: https://github.com/bjrjk/LZ77-Demo/blob/5b6e718cd45cbe337a0eac04eb685cd7e7ad4549/LZ77-Demo/lz77.cpp#L10
[6]: https://github.com/bjrjk/LZ77-Demo/blob/5b6e718cd45cbe337a0eac04eb685cd7e7ad4549/LZ77-Demo/lz77.cpp#L97
[7]: https://github.com/bjrjk/LZ77-Demo/blob/5b6e718cd45cbe337a0eac04eb685cd7e7ad4549/LZ77-Demo/lz77.cpp#L114
[8]: https://github.com/bjrjk/LZ77-Demo/blob/5b6e718cd45cbe337a0eac04eb685cd7e7ad4549/LZ77-Demo/lz77.cpp#L48

发表评论

邮箱地址不会被公开。 必填项已用*标注