文章轉(zhuǎn)發(fā)自51CTO【ELT.ZIP】OpenHarmony啃論文俱樂部——《人工智能短字符串壓縮》

1.技術(shù)DNA

2. 智慧場(chǎng)景

場(chǎng)景	技術(shù)	開源項(xiàng)目
自動(dòng)駕駛 / AR	點(diǎn)云壓縮	Draco/ 基于深度學(xué)習(xí)算法/PCL/OctNet
語(yǔ)音信號(hào)	稀疏快速傅里葉變換	SFFT
流視頻	有損視頻壓縮	AV1/H.266編碼/H.266解碼/VP9
GPU 渲染	網(wǎng)格壓縮	MeshOpt/Draco
科學(xué)、云計(jì)算	動(dòng)態(tài)選擇壓縮算法框架	Ares
內(nèi)存縮減	無(wú)損壓縮	LZ4
科學(xué)應(yīng)用	分層數(shù)據(jù)壓縮	HCompress
醫(yī)學(xué)圖像	醫(yī)學(xué)圖像壓縮	DICOM
數(shù)據(jù)庫(kù)服務(wù)器	無(wú)損通用壓縮	Brotli
人工智能圖像	人工智能圖像壓縮	RAISR
文本傳輸	短字符串壓縮	AIMCS
GAN媒體壓縮	GAN 壓縮的在線多粒度蒸餾	OMGD
圖像壓縮	圖像壓縮	OpenJPEG
文件同步	文件傳輸壓縮	rsync
數(shù)據(jù)庫(kù)系統(tǒng)	快速隨機(jī)訪問字符串壓縮	FSST

3.前言概覽

“人工智能”大家應(yīng)該不陌生，這算是近幾年的“熱詞”，而”壓縮算法“長(zhǎng)期關(guān)注我們團(tuán)隊(duì)的讀者也應(yīng)該挺熟悉，但是何為“短字符串”呢？非計(jì)科專業(yè)背景的讀者乍一聽，可能有點(diǎn)茫然。簡(jiǎn)而言之，我們聊qq，發(fā)微信用的一條條消息籠統(tǒng)的說(shuō)就是短字符串，從專業(yè)角度定義的話，就是平均長(zhǎng)度為160個(gè)字符的字符串。

現(xiàn)在大家對(duì)我們今天介紹的主角有了一個(gè)基本的認(rèn)知，那么接下來(lái)我們步入正題。

4.時(shí)代背景

近年來(lái)，在空間通信，衛(wèi)星回程等領(lǐng)域，短文本在數(shù)據(jù)通信中的使用急劇增加。為了降低帶寬的利用率和成本，必須對(duì)短寫文本采用新的壓縮方法。在本文中我們將介紹一種基于人工智能的無(wú)損壓縮算法，旨在減少網(wǎng)絡(luò)上消息傳輸過程中的數(shù)據(jù)量。

4.1 應(yīng)用場(chǎng)景

4.1.1 空間通訊

4.1.2inReach（手持式衛(wèi)星通信器）

4.1.3 衛(wèi)星回程

4.1.4帶寬匱乏的移動(dòng)網(wǎng)狀網(wǎng)絡(luò)

5.技術(shù)現(xiàn)狀

5.1Huffman編碼

基本思想：基于字符串中字符的重復(fù)次數(shù)進(jìn)行編碼，出現(xiàn)頻率越高編碼越短。

局限性：

• 所有的數(shù)據(jù)和統(tǒng)計(jì)信息都必須在壓縮時(shí)可用。不適合那些連續(xù)生成數(shù)據(jù)的應(yīng)用程序。

• 壓縮少量數(shù)據(jù)時(shí)，無(wú)法減少數(shù)據(jù)的大小，甚至隨著開銷的增大而增大，壓縮后數(shù)據(jù)超過原始數(shù)據(jù)大小。

5.2基于單詞的字符串壓縮方法

基本思想：文本根據(jù)其大小進(jìn)行分類。找到在不同大小文本中形成壓縮基本單元以提高壓縮性能。

基本單元分為三組:word、vavel和character（word是一組字符，而vavel比character短，但比character長(zhǎng)）

• 文本的大小超過 5 MB ——> word

• 文字大小為 200 KB - 5 MB——> vavel

• 文本大小為 100 - 200 KB——> character

測(cè)試結(jié)果：該方法應(yīng)用于數(shù)據(jù)大小為 100KB 的批數(shù)據(jù)

5.3LZW算法

它是一種適合字符串壓縮的方法。LZW是1977年提出的LZ算法的改進(jìn)版本。許多壓縮軟件如winzip, pkzip, gzip都是基于LZW的。

這種方法根據(jù)掃描目標(biāo)文本動(dòng)態(tài)更新構(gòu)造字符串索引字典。

但是，這種方法不適合壓縮小字符串因?yàn)楹凸蚵幋a一樣有時(shí)字典和壓縮數(shù)據(jù)的大小會(huì)超過原始數(shù)據(jù)的大小。

5.4SMAZ

這種方法的目的是通過查找人們發(fā)送的消息的模式，找出重復(fù)次數(shù)最多的單詞，然后將這些單詞映射到索引中。

這種方法減小了短文本消息的大小。例如短文本在推特的比例分別為29%和19%。

SMAZ的缺點(diǎn)識(shí)別發(fā)送信息的模式并不容易，特別是使用不同方言的人在與不同類型的人交談時(shí)發(fā)送的消息。

5.5其他方案

一種利用BP網(wǎng)絡(luò)預(yù)測(cè)字符重復(fù)的方法，使數(shù)據(jù)量減少了30%。神經(jīng)網(wǎng)絡(luò)被用于減小圖像的大小。提出了一種新的實(shí)用的、通用的字符串無(wú)損壓縮算法——神經(jīng)馬爾可夫預(yù)測(cè)壓縮(NMPC)。

該方法基于貝葉斯神經(jīng)網(wǎng)絡(luò)(BNN)和隱馬爾可夫模型(HMM)的結(jié)合，具有線性處理時(shí)間、恒定的內(nèi)存存儲(chǔ)性能和對(duì)并行的適應(yīng)性。然而，這種方法適用于那些大小至少為8 KB的批數(shù)據(jù)。

5.6結(jié)論

在大多數(shù)討論的短文本壓縮方法中，壓縮數(shù)據(jù)的大小和壓縮開銷都大于原始數(shù)據(jù)的大小。

尚未解決問題

• 減少小字符串的大小。

• 是否適合壓縮不同語(yǔ)言和口音的文本

• 可以在生成數(shù)據(jù)流的應(yīng)用程序中使用

• 針對(duì)所有討論的挑戰(zhàn)和問題，我們提出了一種新的壓縮方法。

6.AIMCS

AIMCS顯著降低了數(shù)據(jù)的大小。將我們的算法與lzw和霍夫曼方法進(jìn)行比較，也表明，在字符串的壓縮過程中，我們的方法在壓縮方面具有更好的性能。壓縮時(shí)間增加，壓縮時(shí)間增加，與需要實(shí)時(shí)文本傳輸時(shí)的傳輸時(shí)間相比不顯著。

AIMCS是一種基于人工智能的方法，用于壓縮小于160字節(jié)的微小字符串。

我們已經(jīng)考慮過這個(gè)大小的小字符串，因?yàn)樵谙馮witter這樣的即時(shí)消息傳遞網(wǎng)絡(luò)中，一條消息的遠(yuǎn)小于160字節(jié)。

6.1 基本方法

我們提出了一個(gè)四層壓縮小字符串的算法，其中形成了一個(gè)表，每個(gè)字符都映射到一個(gè)索引。因此，在下一次字符的重復(fù)使用中，將使用索引而不是字符，這會(huì)導(dǎo)致數(shù)據(jù)大小的減少。

6.2以“shorttexttest”為例

• 首先用A表存儲(chǔ)最初的字符串。

• 然后把每個(gè)字符轉(zhuǎn)化成ASCII碼存儲(chǔ)在對(duì)應(yīng)位置得到B表。

記錄新字符插入從左到右的順序表每個(gè)字符的使用數(shù)量，索引編號(hào)，對(duì)應(yīng)的字符和ASCll 碼。

• 接著統(tǒng)計(jì)每個(gè)字符的出現(xiàn)次數(shù)得到C表。

• 接下來(lái)，同時(shí)考慮B和C，我們就可以得到D。

B 中的ASCII碼在d中分為兩種類型，

“0” 表示該字符為新字符，<用原來(lái)的ascll碼表>，“1”表示該字符是否重復(fù)。<用c中索引坐標(biāo)代替>

• E表就將其轉(zhuǎn)化為二進(jìn)制代碼。

E中前一位表示ASCII碼的類型（1 or 0），后四位等于索引或字符的最大二進(jìn)制長(zhǎng)度。

在E1中，ASCII碼和索引的二進(jìn)制類型以每個(gè)類型的最大值的固定長(zhǎng)度顯示。

在E2中，將E1的最大二進(jìn)制長(zhǎng)度不變的7個(gè)零加上.

• G中，F(xiàn)中已有的位將被轉(zhuǎn)換成字節(jié)，然后通過網(wǎng)絡(luò)媒體進(jìn)行通信

接收端接收字節(jié)，將其轉(zhuǎn)換為位，并將其插入到表中。最后，直接從比特中導(dǎo)出ASCII碼，從而實(shí)現(xiàn)“shorttextttest”。

6.3 注意事項(xiàng)

因?yàn)楫?dāng)較短的索引映射到最頻繁的字符時(shí)，字符串的總大小會(huì)減少。

重復(fù)次數(shù)最多的字符必須在第一行，其他字符必須按照重復(fù)次數(shù)的降序排列。

• 表C的順序直接影響壓縮率

• 表C的順序必須基于字符的使用數(shù)量

• 當(dāng)發(fā)送幾個(gè)字符時(shí)，必須檢出表C，確保行順序合適。如果順序不合適，表必須重新排序才能再次使用。

  • 檢測(cè)重新排序表格所需的時(shí)間是我們進(jìn)行這項(xiàng)研究的主要挑戰(zhàn)。

  • 我們的最終目標(biāo)是預(yù)測(cè)表重排序過程的評(píng)估時(shí)間，它直接影響壓縮比。

  • B表的AIMCS在通信過程開始的時(shí)候，表是空的，沒有要排序的東西，這是表最適合的狀態(tài)。當(dāng)發(fā)送幾個(gè)字符(Brecognition或β)時(shí)，表必須被檢出。

  • 通過排序質(zhì)量(Sq)公式(1)對(duì)表進(jìn)行求值，n是重復(fù)次數(shù)，m是行數(shù)

• • 上述公式的結(jié)果是一個(gè)介于0到1之間的數(shù)字，分別代表表的最佳狀態(tài)和最差狀態(tài)。

  • 在表求值的每一步中，在發(fā)送 βr 字符后，將Sq公式得到的結(jié)果與常數(shù)參數(shù)a進(jìn)行比較。

  • 如果Sq > a，則If -condition為true，并且表必須重新排序，并且接收方也必須被告知表的重新排序。

  • 如果我們認(rèn)為a是一個(gè)小的數(shù)量，那么被記錄的機(jī)會(huì)就會(huì)增加，從而增加更多的過載。

  • 反之，如果我們認(rèn)為a很大，表的情況就會(huì)很糟糕，會(huì)對(duì)壓縮比產(chǎn)生不利的影響。

• • 由圖2可知，“period”是表的最佳狀態(tài)到表必須重新排序的狀態(tài)之間的時(shí)間間隔。每個(gè)周期還由幾個(gè)子周期組成，它們分別顯示表的最佳狀態(tài)(白色矩形)、if-condition必須被檢查的狀態(tài)(綠色矩形)和表必須被重新排序的狀態(tài)(黑色矩形)。時(shí)期I和其他時(shí)期之間的區(qū)別是，在時(shí)期1中，表一開始是空的，但在其他時(shí)期，表包含一些實(shí)體，周期的長(zhǎng)度可以不同。

• • 在一個(gè)周期的第一步，經(jīng)過?r字符傳輸后，計(jì)算排序質(zhì)量和壓縮率，將Sq與a進(jìn)行比較。

  • 如果Sq < a, If -condition為假，另一個(gè)?為必須發(fā)送的數(shù)據(jù)量。

  • 如果Sq > a，表必須重新排序。當(dāng)if-condition為True時(shí)，此表用于提高神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的準(zhǔn)確性。

7.實(shí)驗(yàn)

作者使用 AIMCS 和其它的壓縮方法分別壓縮一組 ASCII 編碼和 Unicode 編碼的短文本。這些短文本是在沒有任何過濾的情況下從英語(yǔ)、阿拉伯語(yǔ)以及波斯語(yǔ)的 Twitter 和短文本消息中提取的。

為什么使用不同語(yǔ)言來(lái)進(jìn)行實(shí)驗(yàn)?zāi)兀?/span>

那是因?yàn)槊糠N語(yǔ)言都有自己的熵，而熵直接影響了壓縮比。在運(yùn)行時(shí)間和壓縮比方面，分別比較了 AIMCS 和 LZW 與 Huffman 壓縮方法的性能。結(jié)果在下面的表中。

7.1 實(shí)驗(yàn)一：壓縮英語(yǔ)字符串（ASCII）得到的結(jié)果

語(yǔ)言	類型	算法	原始大小(Bytes)	壓縮比(%)	運(yùn)行時(shí)間(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 的英文文本時(shí)的壓縮比要遠(yuǎn)低于 LZW 壓縮這兩種文本的壓縮比

7.2 實(shí)驗(yàn)二：壓縮阿拉伯和波斯語(yǔ)字符串（Unicode）得到的結(jié)果

語(yǔ)言	算法	原始大小(Bytes)	壓縮比(%)	運(yùn)行時(shí)間(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

由上表知：

• 在幾乎 相同的運(yùn)行時(shí)間 內(nèi)，AIMCS 的壓縮比要明顯低于 LZW 算法的壓縮比。

• 在壓縮 相同大小的文本 時(shí)，AIMCS 壓縮比要比 Huffman 低 ，極大地降低了傳輸文本的時(shí)間和成本。

7.3 實(shí)驗(yàn)三：一段時(shí)間內(nèi)壓縮900萬(wàn)條推文的壓縮比

上圖描述了 AIMCS 在壓縮大量 tweet 的性能。

可以看到，隨著消息數(shù)量的增加，AIMCS 在壓縮 tweet 的壓縮比會(huì)降低，壓縮性能會(huì)更好。

7.4結(jié)果分析

AIMCS 最初對(duì)之前的數(shù)據(jù)沒有足夠的了解，無(wú)法建立足夠大的字典， 可能會(huì)因此無(wú)法預(yù)測(cè)之后會(huì)出現(xiàn)的字符串。隨著字典中條目數(shù)量的增加，通過檢測(cè)字符的種類和重復(fù)頻率，隨著時(shí)間的推移，AIMCS的壓縮效果將會(huì)提升。

為了核對(duì)偏移現(xiàn)象（drift phenomenon），將會(huì)把預(yù)測(cè)的字符的數(shù)量發(fā)送給接收者。如果預(yù)測(cè)的字符的數(shù)量是準(zhǔn)確的，將給予一個(gè)正向反饋，反之給予一個(gè)負(fù)向反饋。

AIMCS 獨(dú)立于語(yǔ)言和語(yǔ)法，可以用于壓縮任何具有語(yǔ)法結(jié)構(gòu)的語(yǔ)言。另外，AIMCS 是通過壓縮數(shù)據(jù)流來(lái)進(jìn)行壓縮的，所以詞法錯(cuò)誤并不會(huì)影響 AIMCS 的性能。

由于以上優(yōu)點(diǎn)，AIMCS 也適用于基于霧計(jì)算（fog computing）的方法。

在物聯(lián)網(wǎng)（IoT）的場(chǎng)景中，許多計(jì)算能力有限的小型智能設(shè)備需要不斷產(chǎn)生極短字符串（tiny strings)的數(shù)據(jù)，并通過互聯(lián)網(wǎng)將其發(fā)送到遠(yuǎn)程服務(wù)器上進(jìn)行處理。在這些場(chǎng)景中，生成的原始數(shù)據(jù)將會(huì)由一個(gè)名為 Fog Server 的實(shí)體進(jìn)行壓縮，該實(shí)體位于產(chǎn)生數(shù)據(jù)的節(jié)點(diǎn)和遠(yuǎn)程服務(wù)器之間，以減少 Internet 流量。

AIMCS的局限性：

AIMCS 不太適合字符數(shù)量多、重復(fù)字符數(shù)量少的語(yǔ)言文本壓縮

AIMCS 不適合壓縮文本以外的數(shù)據(jù)

因?yàn)锳IMCS 設(shè)計(jì)時(shí)的壓縮單元是一個(gè)字符，壓縮其它圖像、音頻等其它數(shù)據(jù)，這些數(shù)據(jù)包含很多與文本壓縮不同的參數(shù)，這使得 AIMCS 需要在發(fā)送端進(jìn)行大量計(jì)算，將會(huì)大大減少壓縮效率。

<本文完>

參考文獻(xiàn)

[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是誰(shuí)？

ELT<=>Elite(精英)，.ZIP為壓縮格式，ELT.ZIP即壓縮精英。

成員：

上海工程技術(shù)大學(xué)大二在校生閆旭

合肥師范學(xué)院大二在校生楚一凡

清華大學(xué)大二在校生趙宏博

成都信息工程大學(xué)大一在校生高云帆

黑龍江大學(xué)大一在校生高鴻萱

山東大學(xué)大三在校生張智騰

ELT.ZIP是來(lái)自6個(gè)地方的同學(xué)，在OpenHarmony成長(zhǎng)計(jì)劃啃論文俱樂部里，與來(lái)自華為、軟通動(dòng)力、潤(rùn)和軟件、拓維信息、深開鴻等公司的高手一起，學(xué)習(xí)、研究、切磋操作系統(tǒng)技術(shù)...

寫在最后

OpenHarmony 成長(zhǎng)計(jì)劃—“啃論文俱樂部”（以下簡(jiǎn)稱“啃論文俱樂部”）是在 2022年 1 月 11 日的一次日常活動(dòng)中誕生的。截至 3 月 31 日，啃論文俱樂部已有 87 名師生和企業(yè)導(dǎo)師參與，目前共有十二個(gè)技術(shù)方向并行探索，每個(gè)方向都有專業(yè)的技術(shù)老師帶領(lǐng)同學(xué)們通過啃綜述論文制定技術(shù)地圖，按“降龍十八掌”的學(xué)習(xí)方法編排技術(shù)開發(fā)內(nèi)容，并通過專業(yè)推廣培養(yǎng)高校開發(fā)者成為軟件技術(shù)學(xué)術(shù)級(jí)人才。

啃論文俱樂部的宗旨是希望同學(xué)們?cè)陂_源活動(dòng)中得到軟件技術(shù)能力提升、得到技術(shù)寫作能力提升、得到講解技術(shù)能力提升。大學(xué)一年級(jí)新生〇門檻參與，已有俱樂部來(lái)自多所高校的大一同學(xué)寫出高居榜首的技術(shù)文章。

如今，搜索“啃論文”，人們不禁想到、而且看到的都是我們——OpenHarmony 成長(zhǎng)計(jì)劃—“啃論文俱樂部”的產(chǎn)出。

OpenHarmony開源與開發(fā)者成長(zhǎng)計(jì)劃—“啃論文俱樂部”學(xué)習(xí)資料合集

1）入門資料：啃論文可以有怎樣的體驗(yàn)

https://docs.qq.com/slide/DY0RXWElBTVlHaXhi?u=4e311e072cbf4f93968e09c44294987d

2）操作辦法：怎么從啃論文到開源提交以及深度技術(shù)文章輸出https://docs.qq.com/slide/DY05kbGtsYVFmcUhU

3）企業(yè)/學(xué)校/老師/學(xué)生為什么要參與 & 啃論文俱樂部的運(yùn)營(yíng)辦法https://docs.qq.com/slide/DY2JkS2ZEb2FWckhq

4）往期啃論文俱樂部同學(xué)分享會(huì)精彩回顧：

同學(xué)分享會(huì)No1.成長(zhǎng)計(jì)劃啃論文分享會(huì)紀(jì)要（2022/02/18）https://docs.qq.com/doc/DY2RZZmVNU2hTQlFY

同學(xué)分享會(huì)No.2 成長(zhǎng)計(jì)劃啃論文分享會(huì)紀(jì)要（2022/03/11）https://docs.qq.com/doc/DUkJ5c2NRd2FRZkhF

同學(xué)們分享會(huì)No.3 成長(zhǎng)計(jì)劃啃論文分享會(huì)紀(jì)要（2022/03/25）

https://docs.qq.com/doc/DUm5pUEF3ck1VcG92?u=4e311e072cbf4f93968e09c44294987d

現(xiàn)在，你是不是也熱血沸騰，摩拳擦掌地準(zhǔn)備加入這個(gè)俱樂部呢？當(dāng)然歡迎啦！啃論文俱樂部向任何對(duì)開源技術(shù)感興趣的大學(xué)生開發(fā)者敞開大門。

掃碼添加 OpenHarmony 高校小助手，加入“啃論文俱樂部”微信群

后續(xù)，我們會(huì)在服務(wù)中心公眾號(hào)陸續(xù)分享一些 OpenHarmony 開源與開發(fā)者成長(zhǎng)計(jì)劃—“啃論文俱樂部”學(xué)習(xí)心得體會(huì)和總結(jié)資料。記得呼朋引伴來(lái)看哦。