人工智能短字符串压缩

文章转发自51CTO【ELT.ZIP】OpenHarmony啃论文俱乐部——《人工智能短字符串压缩》

1. 技术DNA

2. 智慧场景

场景	技术	开源项目
自动驾驶 / AR	点云压缩	Draco / 基于深度学习算法/PCL/OctNet
语音信号	稀疏快速傅里叶变换	SFFT
流视频	有损视频压缩	AV1 / H.266编码 / H.266解码/VP9
GPU 渲染	网格压缩	MeshOpt / Draco
科学、云计算	动态选择压缩算法框架	Ares
内存缩减	无损压缩	LZ4
科学应用	分层数据压缩	HCompress
医学图像	医学图像压缩	DICOM
数据库服务器	无损通用压缩	Brotli
人工智能图像	人工智能图像压缩	RAISR
文本传输	短字符串压缩	AIMCS
GAN媒体压缩	GAN 压缩的在线多粒度蒸馏	OMGD
图像压缩	图像压缩	OpenJPEG
文件同步	文件传输压缩	rsync
数据库系统	快速随机访问字符串压缩	FSST

3. 前言概览

“人工智能”大家应该不陌生，这算是近几年的“热词”，而”压缩算法“长期关注我们团队的读者也应该挺熟悉，但是何为“短字符串”呢？非计科专业背景的读者乍一听，可能有点茫然。简而言之，我们聊qq，发微信用的一条条消息笼统的说就是短字符串，从专业角度定义的话，就是平均长度为160个字符的字符串。

现在大家对我们今天介绍的主角有了一个基本的认知，那么接下来我们步入正题。

4. 时代背景

近年来，在空间通信，卫星回程等领域，短文本在数据通信中的使用急剧增加。为了降低带宽的利用率和成本，必须对短写文本采用新的压缩方法。在本文中我们将介绍一种基于人工智能的无损压缩算法，旨在减少网络上消息传输过程中的数据量。

4.1 应用场景

4.1.1 空间通讯

4.1.2 inReach（手持式卫星通信器）

4.1.3 卫星回程

4.1.4 带宽匮乏的移动网状网络

5. 技术现状

5.1 Huffman编码

基本思想：基于字符串中字符的重复次数进行编码，出现频率越高编码越短。

局限性：

所有的数据和统计信息都必须在压缩时可用。不适合那些连续生成数据的应用程序。
压缩少量数据时，无法减少数据的大小，甚至随着开销的增大而增大，压缩后数据超过原始数据大小。

5.2 基于单词的字符串压缩方法

基本思想：文本根据其大小进行分类。找到在不同大小文本中形成压缩基本单元以提高压缩性能。

基本单元分为三组:word、vavel和character（word是一组字符，而vavel比character短，但比character长）

文本的大小超过 5 MB ——> word
文字大小为 200 KB – 5 MB——> vavel
文本大小为 100 – 200 KB——> character

测试结果：该方法应用于数据大小为 100KB 的批数据

5.3 LZW算法

它是一种适合字符串压缩的方法。LZW是1977年提出的LZ算法的改进版本。许多压缩软件如winzip, pkzip, gzip都是基于LZW的。

这种方法根据扫描目标文本动态更新构造字符串索引字典。

但是，这种方法不适合压缩小字符串因为和哈夫曼编码一样有时字典和压缩数据的大小会超过原始数据的大小。

5.4 SMAZ

这种方法的目的是通过查找人们发送的消息的模式，找出重复次数最多的单词，然后将这些单词映射到索引中。

这种方法减小了短文本消息的大小。例如短文本在推特的比例分别为29%和19%。

SMAZ的缺点识别发送信息的模式并不容易，特别是使用不同方言的人在与不同类型的人交谈时发送的消息。

5.5 其他方案

一种利用BP网络预测字符重复的方法，使数据量减少了30%。神经网络被用于减小图像的大小。提出了一种新的实用的、通用的字符串无损压缩算法——神经马尔可夫预测压缩(NMPC)。

该方法基于贝叶斯神经网络(BNN)和隐马尔可夫模型(HMM)的结合，具有线性处理时间、恒定的内存存储性能和对并行的适应性。然而，这种方法适用于那些大小至少为8 KB的批数据。

5.6 结论

在大多数讨论的短文本压缩方法中，压缩数据的大小和压缩开销都大于原始数据的大小。

尚未解决问题

减少小字符串的大小。
是否适合压缩不同语言和口音的文本
可以在生成数据流的应用程序中使用
针对所有讨论的挑战和问题，我们提出了一种新的压缩方法。

6. AIMCS

AIMCS显著降低了数据的大小。将我们的算法与lzw和霍夫曼方法进行比较，也表明，在字符串的压缩过程中，我们的方法在压缩方面具有更好的性能。压缩时间增加，压缩时间增加，与需要实时文本传输时的传输时间相比不显著。

AIMCS是一种基于人工智能的方法，用于压缩小于160字节的微小字符串。

我们已经考虑过这个大小的小字符串，因为在像Twitter这样的即时消息传递网络中，一条消息的远小于160字节。

6.1 基本方法

我们提出了一个四层压缩小字符串的算法，其中形成了一个表，每个字符都映射到一个索引。因此，在下一次字符的重复使用中，将使用索引而不是字符，这会导致数据大小的减少。

6.2 以“shorttexttest”为例

首先用A表存储最初的字符串。

然后把每个字符转化成ASCII码存储在对应位置得到B表。

接着统计每个字符的出现次数得到C表。

记录新字符插入从左到右的顺序表每个字符的使用数量，索引编号，对应的字符和ASCll 码。

接下来，同时考虑B和C，我们就可以得到D。

B 中的ASCII码在d中分为两种类型，

“0” 表示该字符为新字符，<用原来的ascll码表>，“1”表示该字符是否重复。<用c中索引坐标代替>

E表就将其转化为二进制代码。

E中前一位表示ASCII码的类型（1 or 0），后四位等于索引或字符的最大二进制长度。

在E1中，ASCII码和索引的二进制类型以每个类型的最大值的固定长度显示。

在E2中，将E1的最大二进制长度不变的7个零加上.

G中，F中已有的位将被转换成字节，然后通过网络媒体进行通信

接收端接收字节，将其转换为位，并将其插入到表中。最后，直接从比特中导出ASCII码，从而实现“shorttextttest”。

6.3 注意事项

表C的顺序直接影响压缩率

因为当较短的索引映射到最频繁的字符时，字符串的总大小会减少。

表C的顺序必须基于字符的使用数量
当发送几个字符时，必须检出表C，确保行顺序合适。如果顺序不合适，表必须重新排序才能再次使用。
- 检测重新排序表格所需的时间是我们进行这项研究的主要挑战。
- 我们的最终目标是预测表重排序过程的评估时间，它直接影响压缩比。
- B表的AIMCS在通信过程开始的时候，表是空的，没有要排序的东西，这是表最适合的状态。当发送几个字符(Brecognition或β)时，表必须被检出。
- 通过排序质量(Sq)公式(1)对表进行求值，n是重复次数，m是行数

上述公式的结果是一个介于0到1之间的数字，分别代表表的最佳状态和最差状态。
在表求值的每一步中，在发送 βr 字符后，将Sq公式得到的结果与常数参数a进行比较。
如果Sq > a，则If -condition为true，并且表必须重新排序，并且接收方也必须被告知表的重新排序。
如果我们认为a是一个小的数量，那么被记录的机会就会增加，从而增加更多的过载。
反之，如果我们认为a很大，表的情况就会很糟糕，会对压缩比产生不利的影响。

由图2可知，“period”是表的最佳状态到表必须重新排序的状态之间的时间间隔。每个周期还由几个子周期组成，它们分别显示表的最佳状态(白色矩形)、if-condition必须被检查的状态(绿色矩形)和表必须被重新排序的状态(黑色矩形)。时期I和其他时期之间的区别是，在时期1中，表一开始是空的，但在其他时期，表包含一些实体，周期的长度可以不同。

在一个周期的第一步，经过ßr字符传输后，计算排序质量和压缩率，将Sq与a进行比较。
如果Sq < a, If -condition为假，另一个ß为必须发送的数据量。
如果Sq > a，表必须重新排序。当if-condition为True时，此表用于提高神经网络学习的准确性。

7. 实验

作者使用 AIMCS 和其它的压缩方法分别压缩一组 ASCII 编码和 Unicode 编码的短文本。这些短文本是在没有任何过滤的情况下从英语、阿拉伯语以及波斯语的 Twitter 和短文本消息中提取的。

为什么使用不同语言来进行实验呢？

那是因为每种语言都有自己的熵，而熵直接影响了压缩比。在运行时间和压缩比方面，分别比较了 AIMCS 和 LZW 与 Huffman 压缩方法的性能。结果在下面的表中。

7.1 实验一：压缩英语字符串（ASCII）得到的结果

语言	类型	算法	原始大小(Bytes)	压缩比(%)	运行时间(min)
English	SMS	LZW	80904070	85.6	5.43
English	SMS	AIMCS	80904070	77.81	16.3
English	Twitter	LZW	584630	86.79	0.04
English	Twitter	AIMCS	584630	84.31	0.13

由上表可知：

LZW 算法在压缩英文文本的速度要比其它讨论的算法更快
AIMCS 在压缩英文文本的压缩比其它讨论的算法要低
AIMCS 在压缩 SMS 和 Twitter 的英文文本时的压缩比要远低于 LZW 压缩这两种文本的压缩比

7.2 实验二：压缩阿拉伯和波斯语字符串（Unicode）得到的结果

语言	算法	原始大小(Bytes)	压缩比(%)	运行时间(s)
Persian	Huffman	3243550	67.55	32.56
Persian	AIMCS	3243550	58.82	35.37
Arabic	Huffman	265156	68.34	1.92
Arabic	AIMCS	265156	54.93	2.23

由上表知：

在几乎相同的运行时间内，AIMCS 的压缩比要明显低于 LZW 算法的压缩比。
在压缩相同大小的文本时，AIMCS 压缩比要比 Huffman 低，极大地降低了传输文本的时间和成本。

7.3 实验三：一段时间内压缩900万条推文的压缩比

上图描述了 AIMCS 在压缩大量 tweet 的性能。

可以看到，随着消息数量的增加，AIMCS 在压缩 tweet 的压缩比会降低，压缩性能会更好。

7.4 结果分析

AIMCS 最初对之前的数据没有足够的了解，无法建立足够大的字典，可能会因此无法预测之后会出现的字符串。随着字典中条目数量的增加，通过检测字符的种类和重复频率，随着时间的推移，AIMCS的压缩效果将会提升。

为了核对偏移现象（drift phenomenon），将会把预测的字符的数量发送给接收者。如果预测的字符的数量是准确的，将给予一个正向反馈，反之给予一个负向反馈。

AIMCS 独立于语言和语法，可以用于压缩任何具有语法结构的语言。另外，AIMCS 是通过压缩数据流来进行压缩的，所以词法错误并不会影响 AIMCS 的性能。

由于以上优点，AIMCS 也适用于基于雾计算（fog computing）的方法。

在物联网（IoT）的场景中，许多计算能力有限的小型智能设备需要不断产生极短字符串（tiny strings)的数据，并通过互联网将其发送到远程服务器上进行处理。在这些场景中，生成的原始数据将会由一个名为 Fog Server 的实体进行压缩，该实体位于产生数据的节点和远程服务器之间，以减少 Internet 流量。

AIMCS的局限性：

AIMCS 不太适合字符数量多、重复字符数量少的语言文本压缩

AIMCS 不适合压缩文本以外的数据

因为AIMCS 设计时的压缩单元是一个字符，压缩其它图像、音频等其它数据，这些数据包含很多与文本压缩不同的参数，这使得 AIMCS 需要在发送端进行大量计算，将会大大减少压缩效率。

<本文完>

参考文献

[1] Abedi M, Pourkiani M. AiMCS: An artificial intelligence based method for compression of short strings[C]//2020 IEEE 18th World Symposium on Applied Machine Intelligence and Informatics (SAMI). IEEE, 2020: 311-318.

[2] Zaccaria A, Del Vicario M, Quattrociocchi W, et al. PopRank: Ranking pages’ impact and users’ engagement on Facebook[J]. PloS one, 2019, 14(1): e0211038.

[3] Pourkiani M, Abedi M. An introduction to a dynamic data size reduction approach in fog servers[C]//2019 International Conference on Information and Communications Technology (ICOIACT). IEEE, 2019: 261-265.

ELT.ZIP是谁？

ELT<=>Elite(精英)，.ZIP为压缩格式，ELT.ZIP即压缩精英。

成员：

上海工程技术大学大二在校生闫旭

合肥师范学院大二在校生楚一凡

清华大学大二在校生赵宏博

成都信息工程大学大一在校生高云帆

黑龙江大学大一在校生高鸿萱

山东大学大三在校生张智腾

ELT.ZIP是来自6个地方的同学，在OpenHarmony成长计划啃论文俱乐部里，与来自华为、软通动力、润和软件、拓维信息、深开鸿等公司的高手一起，学习、研究、切磋操作系统技术…

写在最后：

OpenHarmony 成长计划—“啃论文俱乐部”（以下简称“啃论文俱乐部”）是在 2022年 1 月 11 日的一次日常活动中诞生的。截至 3 月 31 日，啃论文俱乐部已有 87 名师生和企业导师参与，目前共有十二个技术方向并行探索，每个方向都有专业的技术老师带领同学们通过啃综述论文制定技术地图，按“降龙十八掌”的学习方法编排技术开发内容，并通过专业推广培养高校开发者成为软件技术学术级人才。

啃论文俱乐部的宗旨是希望同学们在开源活动中得到软件技术能力提升、得到技术写作能力提升、得到讲解技术能力提升。大学一年级新生〇门槛参与，已有俱乐部来自多所高校的大一同学写出高居榜首的技术文章。

如今，搜索“啃论文”，人们不禁想到、而且看到的都是我们——OpenHarmony 成长计划—“啃论文俱乐部”的产出。