硬件加速的快速无损压缩
基于
LZ
4
算法
Jee
hon
g
金
长安区西富路
SKKU
2066
电子与计算机工程系
水原，韩国
+
82
-
31
-
290
-
7200
jh
88.
kim
@
skku
.
ed
u
摘要
数据压缩可以有效地利用存储空间。特别是对于移动设备，其
CPU
(
Ce
ntr
a
l
P
ro
ce
ssin
g U
nit
)
操作时钟和电源等资源有限，
因此需要设计硬件压缩方法。大多数基于字典的自适应压缩方
法都起源于
Le
mp
e
l
-
Z
iv
算法。
LZ
4
是最快的压缩算法之一。
在本文中，我们提出了一种先进的算法和硬件架构，提高了压
缩比和速度。为了获得更高的压缩比，本文算法采用可变长度
格式，而
LZ
4
采用固定长度格式。实验结果表明，该体系结构
的压缩吞吐量可达
3.84
Gb
ps
，压缩比可达
4
。通过这种方
式，我们基于硬件的架构以低功耗提高了移动设备的内存性能
和电池寿命。
CCS
的概念
•
信息系统➝数据库管理系统➝数据结构➝数据布局➝数据
压缩
•
硬件➝通信硬件、接口和存储➝信号处理系统
关键字
无损压缩
;
LZ
4;
Le
mp
e
l
-
Z
iv
;
硬件架构
;
移动设备。
1.
介绍
随着高质量多媒体服务的增加，数据压缩已成为使用存储的电
子设备的必要条件。多年来，移动通信和视频服务的质量不断
提高，传输和存储数据的需求呈爆炸式增长。对大容量存储和
传输的需求增长速度至少是存储和传输容量增长
[
1
]
的两倍。
有两种类型的数据压缩
:
有损和无损数据制作数字许可或拷贝全
部或部分的努力对个人或教室使用授予提供副本不是没有费用
或分配利润或商业优势
,
承担此通知副本和完整的引文在第一
页。本作品的组成部分版权归
ACM
以外的其他人所有。信用证抽象化
是允许的。以其他方式复制、重新发布、在服务器上发布或重新发布到
列表，需要事先获得特定的许可和
/
或支付费用。从
Pe
rmis
-
sions
@
ac
m
.
or
g
请求权限。
ICDSP
2019, 2019
年
2
月
24
-
26
日，韩国济州岛。
©
2019
计算机
械协会。
ACM ISBN
978
-
1
-
4503
-
6204
-
7/19/02…15.00
美元
DOI
:
https
://
d
oi
.
or
g
/10.1145/3316551.3316564
J
un
d
on
g
曹
长安区西富路
SKKU
2066
电子与计算机工程系
水原，韩国
+
82
-
31
-
290
-
7200
j
dc
ho
7
@
skku
.
e
d
u
压缩
[
2
]
。有损数据压缩主要用于图像、视频等多媒体数据。与
有损压缩不同，无损压缩在压缩和解压缩后能很好地保存原始
文件中的信息。无损数据压缩分为基于树的编码和基于字典的
编码。代表性的基于树的代码有
H
u
ff
m
a
n
代码
[
3
]
和算术代码
[
4
]
。基于字典的代码不同于
H
u
ff
m
a
n
代码和算术代码，由源数
据生成的符号或符号串由字典索引表示。基于自适应字典的代
码在对源数据进行编码时构建字典。
LZ
算法是应用最广泛的自
适应字典编 码，它基于
Z
iv
和
Le
mp
e
l
的两篇里程碑式论文
[
5
][
6
]
。
本文提出了一种基于
LZ
4
的改进算法和一种优化的移动设备
硬件结构。根据
FPGA
实现的
LZ
算法
[
7
][
8
]
，硬件实现的压
缩算法比软件实现的压缩算法具有更快的压缩性能。智能手
机等移动设备有以下限制
:1)
时钟频率
;2)
功耗
;3)
芯片的大小。
必须考虑在移动设备中实现这些约束。
2.
LZ
4
[
9
]
是
LZ
77
[
10
]
的改进形式，是
C
oll
e
t
在
2011
年提
出的一种固定的、面向字节的算法。
LZ
4
类似于
LZ
77
，因为
它有一个由搜索缓冲区和向前查找缓冲区组成的滑动窗口。
LZ
4
搜索之前未压缩的数据流中的重复数据，并用索引替换它。
LZ
4
通过哈希表来匹配数据，从而提高了压缩速度。
LZ
4
的压缩数
据如图
1
[
8
]
所示，它由标记、文字长度、偏移量和匹配长度组
成。
LZ
4
序列的数据格式如下。
1)
T
ok
e
n
是每个序列的第一个值。
T
ok
e
n
是一个单字节值，包含
两个
4
位字段，文字长度和匹配长度。四个最高有效位，
即。，
tok
e
n
[
7:4
]
是文字长度，范围从
0
到
15
。四个最低有
效位，即。，
tok
e
n
[
3:0
]
的匹配长度从
0
到
15
。如果
tok
e
n
[
7:4
]
v
a
lu
e
为
0
，则没有文字。如果是
15
，字面值长度必须
有从
0
到
255
的额外字节，以表示字面值的完整长度。如果
tok
e
n
[
3:0
]
v
a
lu
e
为
0
，则表示最小匹配长度为
4
，称为
min
m
a
t
c
h
。因此，令牌
[
3:0
]
值从
0
到
15
意味着匹配长度值从
4
到
19
。如果
tok
e
n
[
3:0
]
为
15
，则匹配长度中有更多字节。
65
令
牌
文字长度
文
字
抵
消
匹配长度
1
个
字
节
低氮
字节
0
升
字节
2
字
节
低氮
字节
图
1
所示。
LZ
4
序列的数据格式
2)
当令牌
[
7:4
]
为
15
时，字面值长度是额外的字节。如果文字长
度为
0
~
254
，则没有更多的文字。如果文字长度是
255
，在
下一个文字长度中有更多字节。
3)
偏移量是
2
字节的值，小端格式。偏移量表示要复制的匹配的
位置。偏移值
1
表示
“
当前位置
-
1
字节
”
。最大偏移量为
65535
。
4)
匹配长度类似于文字长度。当令牌
[
3:0
]
达到可能的最高值
15
时，额外的字节被添加到匹配长度中，值从
0
到
255.
LZ
4
总是为偏移值分配
2
个字节。它对压缩比的性能没有有效
的影响。
LZ
4
算法最初是为一般处理器的软件实现而提出的，
因此在硬件
[
8
]
上实现
LZ
4
存在一定的约束。
3.
该方法
在本节中，我们提出了一种改进的序列和哈希计算的数据格式。
通过指定压缩单元的大小，可以优化哈希表的大小。压缩单元的
大小设置为
4
KB
，以便为内存页面进行优化并节省内部内存。
3.1
数据格式
我们的数据格式几乎与
LZ
4
相似，除了头部和偏移量。如图
2
所
示。报头位于每个压缩单元的开头，包含压缩大小和原始标志。
如果压缩后的大小大于原始大小，
r
a
w
标志被标记为
1
，原始数
据被添加到
h
eade
r
后，而不是压缩符号后，则解压缩器不需要
解压缩该压缩单元。在数据根本没有压缩的最坏情况下，
r
a
w
标
志使解压缩程序更快。在最坏的情况下，压缩单位大小被添加到
