人工智能短字符串壓縮

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

1.技術DNA

2. 智慧場景

3.前言概覽

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

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

4.時代背景

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

4.1 應用場景

4.1.1 空間通訊

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

4.1.3 衛(wèi)星回程

4.1.4帶寬匱乏的移動網狀網絡

5.技術現(xiàn)狀

5.1Huffman編碼

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

局限性：

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

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

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

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

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

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

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

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

測試結果：該方法應用于數(shù)據(jù)大小為 100KB 的批數(shù)據(jù)

5.3LZW算法

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

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

但是，這種方法不適合壓縮小字符串因為和哈夫曼編碼一樣有時字典和壓縮數(shù)據(jù)的大小會超過原始數(shù)據(jù)的大小。

5.4SMAZ

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

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

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

5.5其他方案

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

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

5.6結論

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

尚未解決問題

• 減少小字符串的大小。

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

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

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

6.AIMCS

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

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

我們已經考慮過這個大小的小字符串，因為在像Twitter這樣的即時消息傳遞網絡中，一條消息的遠小于160字節(jié)。

6.1 基本方法

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

6.2以“shorttexttest”為例

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

• 然后把每個字符轉化成ASCII碼存儲在對應位置得到B表。

記錄新字符插入從左到右的順序表每個字符的使用數(shù)量，索引編號，對應的字符和ASCll 碼。

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

• 接下來，同時考慮B和C，我們就可以得到D。

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

“0” 表示該字符為新字符，<用原來的ascll碼表>，“1”表示該字符是否重復。<用c中索引坐標代替>

• E表就將其轉化為二進制代碼。

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

在E1中，ASCII碼和索引的二進制類型以每個類型的最大值的固定長度顯示。

在E2中，將E1的最大二進制長度不變的7個零加上.

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

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

6.3 注意事項

因為當較短的索引映射到最頻繁的字符時，字符串的總大小會減少。

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

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

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

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

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

  • 我們的最終目標是預測表重排序過程的評估時間，它直接影響壓縮比。

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

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

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

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

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

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

  • 反之，如果我們認為a很大，表的情況就會很糟糕，會對壓縮比產生不利的影響。

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

• • 在一個周期的第一步，經過?r字符傳輸后，計算排序質量和壓縮率，將Sq與a進行比較。

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

  • 如果Sq > a，表必須重新排序。當if-condition為True時，此表用于提高神經網絡學習的準確性。

7.實驗

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

為什么使用不同語言來進行實驗呢？

那是因為每種語言都有自己的熵，而熵直接影響了壓縮比。在運行時間和壓縮比方面，分別比較了 AIMCS 和 LZW 與 Huffman 壓縮方法的性能。結果在下面的表中。

7.1 實驗一：壓縮英語字符串（ASCII）得到的結果

由上表可知：

• LZW 算法在壓縮英文文本的速度要比其它討論的算法更快

• AIMCS 在壓縮英文文本的壓縮比其它討論的算法要低

• AIMCS 在壓縮 SMS 和 Twitter 的英文文本時的壓縮比要遠低于 LZW 壓縮這兩種文本的壓縮比

7.2 實驗二：壓縮阿拉伯和波斯語字符串（Unicode）得到的結果

由上表知：

• 在幾乎 相同的運行時間 內，AIMCS 的壓縮比要明顯低于 LZW 算法的壓縮比。

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

7.3 實驗三：一段時間內壓縮900萬條推文的壓縮比

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

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

7.4結果分析

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

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

AIMCS 獨立于語言和語法，可以用于壓縮任何具有語法結構的語言。另外，AIMCS 是通過壓縮數(shù)據(jù)流來進行壓縮的，所以詞法錯誤并不會影響 AIMCS 的性能。

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

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

AIMCS的局限性：

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

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

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

<本文完>

參考文獻

[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成長計劃啃論文俱樂部里，與來自華為、軟通動力、潤和軟件、拓維信息、深開鴻等公司的高手一起，學習、研究、切磋操作系統(tǒng)技術...

寫在最后

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

啃論文俱樂部的宗旨是希望同學們在開源活動中得到軟件技術能力提升、得到技術寫作能力提升、得到講解技術能力提升。大學一年級新生〇門檻參與，已有俱樂部來自多所高校的大一同學寫出高居榜首的技術文章。

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

OpenHarmony開源與開發(fā)者成長計劃—“啃論文俱樂部”學習資料合集

1）入門資料：啃論文可以有怎樣的體驗

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

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

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

4）往期啃論文俱樂部同學分享會精彩回顧：

同學分享會No1.成長計劃啃論文分享會紀要（2022/02/18）https://docs.qq.com/doc/DY2RZZmVNU2hTQlFY

同學分享會No.2 成長計劃啃論文分享會紀要（2022/03/11）https://docs.qq.com/doc/DUkJ5c2NRd2FRZkhF

同學們分享會No.3 成長計劃啃論文分享會紀要（2022/03/25）

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

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

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

后續(xù)，我們會在服務中心公眾號陸續(xù)分享一些 OpenHarmony 開源與開發(fā)者成長計劃—“啃論文俱樂部”學習心得體會和總結資料。記得呼朋引伴來看哦。