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