LZSS 压缩算法 - lzss 算法的实施
一、前言
本文是基于我的上一篇博客《无损压缩算法专题——无损压缩算法介绍》的基础上来实现的,博客链接https://blog.****.net/qq_34254642/article/details/103651815,这一篇当中实现基本的LZSS算法功能,先不做改进,所以算法效率比较低,但是便于理解。写了Python和C两个版本,两种语言的代码结构是一样的,代码中都有详尽的注释。实现了对任意文件的压缩和解压功能。
二、LZSS算法实现
Python实现
import ctypes
import os
class LZSS():
def __init__(self, preBufSizeBits):
self.threshold = 2 #长度大于等于2的匹配串才有必要压缩
self.preBufSizeBits = preBufSizeBits #前向缓冲区占用的比特位
self.windowBufSizeBits = 16 - self.preBufSizeBits #滑动窗口占用的比特位
self.preBufSize = (1 << self.preBufSizeBits) - 1 + self.threshold #通过占用的比特位计算缓冲区大小
self.windowBufSize = (1 << self.windowBufSizeBits) - 1 + self.threshold #通过占用的比特位计算滑动窗口大小
self.preBuf = b'' #前向缓冲区
self.windowBuf = b'' #滑动窗口
self.matchString = b'' #匹配串
self.matchIndex = 0 #滑动窗口匹配串起始下标
#文件压缩
def LZSS_encode(self, readfilename, writefilename):
fread = open(readfilename, "rb")
fwrite = open(writefilename, "wb")
restorebuff = b'' #待写入的数据缓存区,满一组数据写入一次文件
itemnum = 0 #8个项目为一组,用来统计当前项目数
signbits = 0 #标记字节
self.preBuf = fread.read(self.preBufSize) #读取数据填满前向缓冲区
# 前向缓冲区没数据可操作了即为压缩结束
while self.preBuf != b'':
self.matchString = b''
self.matchIndex = -1
#在滑动窗口中寻找最长的匹配串
for i in range(self.threshold, len(self.preBuf) + 1):
index = self.windowBuf.find(self.preBuf[0:i])
if index != -1:
self.matchString = self.preBuf[0:i]
self.matchIndex = index
else:
break
#如果没找到匹配串或者匹配长度为1,直接输出原始数据
if self.matchIndex == -1:
self.matchString = self.preBuf[0:1]
restorebuff += self.matchString
else:
restorebuff += bytes(ctypes.c_uint16(self.matchIndex * (1 << self.preBufSizeBits) + len(self.matchString) - self.threshold))
signbits += (1 << (7 - itemnum))
#操作完一个项目+1
itemnum += 1
#项目数达到8了,说明做完了一组压缩,将这一组数据写入文件
if itemnum >= 8:
writebytes = bytes(ctypes.c_uint8(signbits)) + restorebuff
fwrite.write(writebytes);
itemnum = 0
signbits = 0
restorebuff = b''
self.preBuf = self.preBuf[len(self.matchString):] #将刚刚匹配过的数据移出前向缓冲区
self.windowBuf += self.matchString #将刚刚匹配过的数据加入滑动窗口
if len(self.windowBuf) > self.windowBufSize: #将多出的数据从前面开始移出滑动窗口
self.windowBuf = self.windowBuf[(len(self.windowBuf) - self.windowBufSize):]
self.preBuf += fread.read(self.preBufSize - len(self.preBuf)) #读取数据补充前向缓冲区
if restorebuff != b'': #文件最后可能不满一组数据量,直接写到文件里
writebytes = bytes(ctypes.c_uint8(signbits)) + restorebuff
fwrite.write(writebytes);
fread.close()
fwrite.close()
return os.path.getsize(writefilename)
#文件解压
def LZSS_decode(self, readfilename, writefilename):
fread = open(readfilename, "rb")
fwrite = open(writefilename, "wb")
self.windowBuf = b''
self.preBuf = fread.read(1) #先读一个标记字节以确定接下来怎么解压数据
while self.preBuf != b'':
for i in range(8): #8个项目为一组进行解压
# 从标记字节的最高位开始解析,0代表原始数据,1代表(下标,匹配数)解析
if self.preBuf[0] & (1 << (7 - i)) == 0:
temp = fread.read(1)
fwrite.write(temp)
self.windowBuf += temp
else:
temp = fread.read(2)
start = ((temp[0] + temp[1] * 256) // (1 << self.preBufSizeBits)) #取出高位的滑动窗口匹配串下标
end = start + temp[0] % (1 << self.preBufSizeBits) + self.threshold #取出低位的匹配长度
fwrite.write(self.windowBuf[start:end]) #将解压出的数据写入文件
self.windowBuf += self.windowBuf[start:end] #将解压处的数据同步写入到滑动窗口
if len(self.windowBuf) > self.windowBufSize: #限制滑动窗口大小
self.windowBuf = self.windowBuf[(len(self.windowBuf) - self.windowBufSize):]
self.preBuf = fread.read(1) #读取下一组数据的标志字节
fread.close()
fwrite.close()
if __name__ == '__main__':
Demo = LZSS(7)
Demo.LZSS_encode("115.log", "encode")
Demo.LZSS_decode("encode", "decode")
C实现
#include <string.h>
#include <stdio.h>
#define BYTE unsigned char
#define WORD unsigned short
#define DWORD unsigned int
#define TRUE 1
#define FALSE 0
BYTE bThreshold; //压缩阈值、长度大于等于2的匹配串才有必要压缩
BYTE bPreBufSizeBits; //前向缓冲区占用的比特位
BYTE bWindowBufSizeBits; //滑动窗口占用的比特位
WORD wPreBufSize; //通过占用的比特位计算缓冲区大小
WORD wWindowBufSize; //通过占用的比特位计算滑动窗口大小
BYTE bPreBuf[1024]; //前向缓冲区
BYTE bWindowBuf[8192]; //滑动窗口
BYTE bMatchString[1024]; //匹配串
WORD wMatchIndex; //滑动窗口匹配串起始下标
BYTE FindSameString(BYTE *pbStrA, WORD wLenA, BYTE *pbStrB, WORD wLenB, WORD *pwMatchIndex); //查找匹配串
DWORD LZSS_encode(char *pbReadFileName, char *pbWriteFileName); //文件压缩
DWORD LZSS_decode(char *pbReadFileName, char *pbWriteFileName); //文件解压
int main()
{
bThreshold = 2;
bPreBufSizeBits = 6;
bWindowBufSizeBits = 16 - bPreBufSizeBits;
wPreBufSize = ((WORD)1 << bPreBufSizeBits) - 1 + bThreshold;
wWindowBufSize = ((WORD)1 << bWindowBufSizeBits) - 1 + bThreshold;
LZSS_encode("115.log", "encode");
LZSS_decode("encode", "decode");
return 0;
}
BYTE FindSameString(BYTE *pbStrA, WORD wLenA, BYTE *pbStrB, WORD wLenB, WORD *pwMatchIndex)
{
WORD i, j;
for (i = 0; i < wLenA; i++)
{
if ((wLenA - i) < wLenB)
{
return FALSE;
}
if (pbStrA[i] == pbStrB[0])
{
for (j = 1; j < wLenB; j++)
{
if (pbStrA[i + j] != pbStrB[j])
{
break;
}
}
if (j == wLenB)
{
*pwMatchIndex = i;
return TRUE;
}
}
}
return FALSE;
}
DWORD LZSS_encode(char *pbReadFileName, char *pbWriteFileName)
{
WORD i, j;
WORD wPreBufCnt = 0;
WORD wWindowBufCnt = 0;
WORD wMatchStringCnt = 0;
BYTE bRestoreBuf[17] = { 0 };
BYTE bRestoreBufCnt = 1;
BYTE bItemNum = 0;
FILE *pfRead = fopen(pbReadFileName, "rb");
FILE *pfWrite = fopen(pbWriteFileName, "wb");
//前向缓冲区没数据可操作了即为压缩结束
while (wPreBufCnt += fread(&bPreBuf[wPreBufCnt], 1, wPreBufSize - wPreBufCnt, pfRead))
{
wMatchStringCnt = 0; //刚开始没有匹配到数据
wMatchIndex = 0xFFFF; //初始化一个最大值,表示没匹配到
for (i = bThreshold; i <= wPreBufCnt; i++) //在滑动窗口中寻找最长的匹配串
{
if (TRUE == FindSameString(bWindowBuf, wWindowBufCnt, bPreBuf, i, &wMatchIndex))
{
memcpy(bMatchString, &bWindowBuf[wMatchIndex], i);
wMatchStringCnt = i;
}
else
{
break;
}
}
//如果没找到匹配串或者匹配长度为1,直接输出原始数据
if ((0xFFFF == wMatchIndex))
{
wMatchStringCnt = 1;
bMatchString[0] = bPreBuf[0];
bRestoreBuf[bRestoreBufCnt++] = bPreBuf[0];
}
else
{
j = (wMatchIndex << bPreBufSizeBits) + wMatchStringCnt - bThreshold;
bRestoreBuf[bRestoreBufCnt++] = (BYTE)j;
bRestoreBuf[bRestoreBufCnt++] = (BYTE)(j >> 8);
bRestoreBuf[0] |= (BYTE)1 << (7 - bItemNum);
}
bItemNum += 1; //操作完一个项目+1
if (bItemNum >= 8) //项目数达到8了,说明做完了一组压缩,将这一组数据写入文件,同时清空缓存
{
fwrite(bRestoreBuf, 1, bRestoreBufCnt, pfWrite);
bItemNum = 0;
memset(bRestoreBuf, 0, sizeof(bRestoreBuf));
bRestoreBufCnt = 1;
}
//将刚刚匹配过的数据移出前向缓冲区
for (i = 0; i < (wPreBufCnt - wMatchStringCnt); i++)
{
bPreBuf[i] = bPreBuf[i + wMatchStringCnt];
}
wPreBufCnt -= wMatchStringCnt;
//如果滑动窗口将要溢出,先提前把前面的部分数据移出窗口
if ((wWindowBufCnt + wMatchStringCnt) > wWindowBufSize)
{
j = ((wWindowBufCnt + wMatchStringCnt) - wWindowBufSize);
for (i = 0; i < (wWindowBufSize - j); i++)
{
bWindowBuf[i] = bWindowBuf[i + j];
}
wWindowBufCnt = wWindowBufSize - wMatchStringCnt;
}
//将刚刚匹配过的数据加入滑动窗口
memcpy((BYTE *)&bWindowBuf[wWindowBufCnt], bMatchString, wMatchStringCnt);
wWindowBufCnt += wMatchStringCnt;
}
//文件最后可能不满一组数据量,直接写到文件里
if (0 != bRestoreBufCnt)
{
fwrite(bRestoreBuf, 1, bRestoreBufCnt, pfWrite);
}
fclose(pfRead);
fclose(pfWrite);
return 0;
}
DWORD LZSS_decode(char *pbReadFileName, char *pbWriteFileName)
{
WORD i, j;
BYTE bItemNum;
BYTE bFlag;
WORD wStart;
WORD wMatchStringCnt = 0;
WORD wWindowBufCnt = 0;
FILE *pfRead = fopen(pbReadFileName, "rb");
FILE *pfWrite = fopen(pbWriteFileName, "wb");
while (0 != fread(&bFlag, 1, 1, pfRead)) //先读一个标记字节以确定接下来怎么解压数据
{
for (bItemNum = 0; bItemNum < 8; bItemNum++) //8个项目为一组进行解压
{
//从标记字节的最高位开始解析,0代表原始数据,1代表(下标,匹配数)解析
if (0 == (bFlag & ((BYTE)1 << (7 - bItemNum))))
{
if (fread(bPreBuf, 1, 1, pfRead) < 1)
{
goto LZSS_decode_out_;
}
fwrite(bPreBuf, 1, 1, pfWrite);
bMatchString[0] = bPreBuf[0];
wMatchStringCnt = 1;
}
else
{
if (fread(bPreBuf, 1, 2, pfRead) < 2)
{
goto LZSS_decode_out_;
}
//取出高位的滑动窗口匹配串下标
wStart = ((WORD)bPreBuf[0] | ((WORD)bPreBuf[1] << 8)) / ((WORD)1 << bPreBufSizeBits);
//取出低位的匹配长度
wMatchStringCnt = ((WORD)bPreBuf[0] | ((WORD)bPreBuf[1] << 8)) % ((WORD)1 << bPreBufSizeBits) + bThreshold;
//将解压出的数据写入文件
fwrite(&bWindowBuf[wStart], 1, wMatchStringCnt, pfWrite);
memcpy(bMatchString, &bWindowBuf[wStart], wMatchStringCnt);
}
//如果滑动窗口将要溢出,先提前把前面的部分数据移出窗口
if ((wWindowBufCnt + wMatchStringCnt) > wWindowBufSize)
{
j = (wWindowBufCnt + wMatchStringCnt) - wWindowBufSize;
for (i = 0; i < wWindowBufCnt - j; i++)
{
bWindowBuf[i] = bWindowBuf[i + j];
}
wWindowBufCnt -= j;
}
//将解压处的数据同步写入到滑动窗口
memcpy(&bWindowBuf[wWindowBufCnt], bMatchString, wMatchStringCnt);
wWindowBufCnt += wMatchStringCnt;
}
}
LZSS_decode_out_:
fclose(pfRead);
fclose(pfWrite);
return 0;
}
三、性能分析
因为代码都是最基本的实现,并没有对匹配串搜索函数进行优化,所以时间性能上比较低,我们这里只对比压缩前后文件的字节大小。有一点要提到的就是代码里面有个threshold参数为2,意思是匹配串大于等于2才有必要进行压缩,因为(位置,长度)这个标记的输出长度为16比特位,所以匹配串只有1字节也用这种方式表示的话显然起不到压缩效果。大家还可以发现一个问题,写入文件时匹配长度并不是实际值,因为0和1的匹配长度是不存在的,所以干脆把0当做2,1当做3这样来看待,就可以把匹配长度扩充两个长度了。
确定了(位置,长度)的输出格式为两个字节后,接下里就是怎么选取“位置”和“长度”各自所应该占用的比特位是多少了,我们可以设置为(8,8),(9,7),(10,6)等等这样的组合,但是给“位置”设置的比特位一定要大于等于“长度”的比特位,原因是滑动窗口大小要大于等于前向缓冲区大小,不然没有意义。对于相同的文件,这两个参数选取不同,那么压缩率也会不同,下面是我对一个log文件选取不同的参数进行压缩后的文件大小对比图,图中preBufSizeBits就是指的“长度”所占的比特位数:
未压缩的原始文件大小是5.06MB,可以清晰的看出preBufSizeBits并不是越小越好,也不是越大越好,因为如果preBufSizeBits小了的话那么前向缓冲区也就小了,一次能匹配的数据串就小了;如果preBufSizeBits大了的话那么虽然前向缓冲区变大了,但是滑动窗口会缩小,数据串的匹配范围就变小了。所以需要选择一个合适的值才能使文件压缩性能最好。
算法内部的对比就到这里了,接下来我们和当前流行的ZIP和RAR进行压缩性能对比,虽然感觉自不量力,但是有对比才有进步嘛。
115.log是原始文件,encode2到encode8其实就是上边性能图里不同preBufSizeBits时生成的压缩文件,decode2到decode8是对应再解压缩出来的文件。115.rar是用电脑上RAR软件压缩的文件,115.zip是用电脑上ZIP软件压缩的文件。我们这个算法最好的性能是压缩到了197KB,和ZIP的161KB差距不是特别大,和RAR就差了相当一大截了。 因为ZIP其实也是类似的滑动窗口匹配压缩,所以接下来优化LZSS算法的话,还是要尽量向ZIP的性能看齐。
四、总结
接下来还会继续思考LZSS算法的改进,包括压缩率和压缩/解压时间的性能,因为我本人是嵌入式工程师,所以会思考实现在嵌入式设备上如何运用数据压缩,在网上查找资料的时候也找到了一些开源的压缩库,但是使用上可能会存在一些问题和限制,当然最好是我们使用的算法我们是知根知底的,这样我们就可以根据项目的需求和特点进行灵活的修改和运用,出了什么问题也不会太慌。
推荐阅读
-
压缩感知算法中的降序迭代法的性能
-
NeurIPS 2022 | 最强斗地主AI!网易互娱AI Lab提出基于完美信息蒸馏的方法-完美信息蒸馏(PTIE) 在斗地主游戏中,非完美信息的引入主要是由于三位玩家均不能看到别人的手牌,对于任意一位玩家而言,仅可知道其余两位玩家当前手牌的并集,而难于精准判断每位玩家当前手牌。完美信息蒸馏的思路是针对这种非完美问题,构建一个第三方角色,该角色可以看到三位玩家的手牌,该角色在不告知每位玩家完美信息的情况下通过信息蒸馏的方式引导玩家打出当前情况下合理的出牌。 以强化学习常用的 Actor-Critic 算法为例,PTIE 在 Actor-Critic 算法的应用中可以利用 Critic 的 Value 输出作为蒸馏手段来提升 Actor 的表现。具体而言即在训练中 Critic 的输入为完美信息(包含所有玩家的手牌信息),Actor 的输入为非完美信息(仅包含自己手牌信息),此种情况下 Critic 给予的 Value 值包含了完美信息,可以更好地帮助 Actor 学习到更好的策略。 从更新公式上来看,正常的 Actor-Critic 算法 Actor 更新的方式如下: 在 PTIE 模式下,对于每个非完美信息状态 h,我们可以在 Critic 中构建对应的完美信息状态 D(h),并用 Critic 的输出来更新 Actor 的策略梯度,从而达到完美信息蒸馏的效果。 PTIE 框架的整体结构如下图所示: 无论是训练还是执行过程中智能体都不会直接使用完美信息,在训练中通过蒸馏将完美信息用于提升策略,从而帮助智能体达到一个更高的强度。 PTIE 的另一种蒸馏方式是将完美信息奖励引入到奖励值函数的训练中,PerfectDou 提出了基于阵营设计的完美信息奖励 node reward,以引导智能体学习到斗地主游戏中的合作策略,其定义如下: 如上所示,完美信息部分 代表 t 时刻地主手牌最少几步可以出完,在斗地主游戏中可以近似理解为是距游戏获胜的距离, 代表 t 时刻地主阵营和农民阵营距游戏获胜的距离之差, 为调节系数。通过此种奖励设计,在训练时既可以一定程度地引入各玩家的手牌信息(出完的步数需要知道具体手牌才能计算),同时也鼓励农民以阵营的角度做出决策,提升农民的合作性。 特征构建: PerfectDou 针对牌类游戏的特点主要构建了两部分特征:牌局状态特征和动作特征。其中牌局状态特征主要包括当前玩家手牌牌型特征、当前玩家打出的卡牌牌型特征、玩家角色、玩家手牌数目等常用特征,动作特征主要用于刻画当前状态下玩家的所有可能出牌,包括了每种出牌动作的牌型特征、动作的卡牌数目、是否为最大动作等特征。 牌型特征为 12 * 15 的矩阵,如下图所示: 该矩阵前 4 行代表对应每种卡牌的张数,5-12 行代表该种卡牌的种类和对应位置。 网络结构和动作空间设计 针对斗地主游戏出牌组合数较多的问题,PerfectDou 基于 RLCard 的工作上对动作空间进行了简化,对占比最大的两个出牌牌型:飞机带翅膀和四带二进行了动作压缩,将整体动作空间由 27472 种缩减到 621 种。 PerfectDou 策略网络结构如下图所示: 策略网络结构同样分为两部分:状态特征部分和动作特征部分。 在状态特征部分,LSTM 网络用于提取玩家的历史行为特征,当前牌局状态特征和提取后的行为特征会再通过多层的 MLP 网络输出当前的状态信息 embedding。 在动作特征部分,每个可行动作同样会经过多层 MLP 网络进行编码,编码后的动作特征会与其对应的状态信息 embedding 经过一层 MLP 网络计算两者间的相似度,并经由 softmax 函数输出对应的动作概率。 实验结果
-
照相机白平衡的算法模拟实施
-
深入 PID 控制算法 (III) ---- 增量式和位置式 PID 算法的 C 语言实施和电机控制经验
-
流程互斥软件的四种实施方法 - 4.彼得森算法
-
韦伯斯特(Webster)算法的实施
-
数据压缩 -- 基于 LZ4 算法的快速无损压缩与硬件加速--摘要
-
LZSS 压缩算法 - lzss 算法的实施
-
适用于嵌入式单片机的压缩算法-3. 基准测试
-
.NET中的MD5加密和解密代码 - MD5的简要介绍: MD5是一种将大量信息在使用数字签名软件签署私钥之前进行“压缩”的保密格式转换方法。无论是MD4还是MD5,它们都需要获取一段随机长度的信息,并生成一个128位的信息摘要。 尽管这些算法在结构上略有不同,但MD2的设计与MD4和MD5完全不同,这是因为MD2是为了8位机器进行优化设计的,而MD4和MD5则是面向32位计算机的。这三个算法的详细描述和C语言源代码可以在Internet RFCs 1321中找到,这是最权威的文档,由Ronald L. Rivest于1992年8月提交给IETF。 以下是相关的代码实现: