【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮

本文出自 ELT.ZIP 團隊，ELT<=>Elite(精英)，.ZIP為壓縮格式，ELT.ZIP即壓縮精英。
成員：
- 上海工程技術大學大二在校生
- 合肥師範學院大二在校生
- 清華大學大二在校生
- 成都資訊工程大學大一在校生
- 黑龍江大學大一在校生
- 華南理工大學大一在校生
我們是來自 6個地方 的同學，我們在 OpenHarmony成長計劃啃論文俱樂部 裡，與 華為、軟通動力、潤和軟體、拓維資訊、深開鴻 等公司一起，學習和研究 作業系統技術 …

【往期回顧】

① 2月23日《老子到此一遊系列》之老子為什麼是老子 —— ++綜述視角解讀壓縮編碼++

② 3月11日《老子到此一遊系列》之老子帶你看懂這些風景 —— ++多元探秘通用無損壓縮++

③ 3月25日《老子到此一遊系列》之老子見證的滄海桑田 —— ++輕翻那些永垂不朽的詩篇++

④ 4月4日《老子到此一遊系列》之老子遊玩了一條河 —— ++細數生活中的壓縮點滴++

⑤ 4月18日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——一文穿透多媒體過往前沿++

⑥ 4月18日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——這些小風景你不應該錯過++

⑦ 4月18日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——淺析稀疏表示醫學圖像++

⑧ 4月29日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——計算機視覺資料壓縮應用++

⑨ 4月29日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——點燃主緩存壓縮技術火花++

⑩ 4月29日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——即刻征服3D網格壓縮編碼++

⑪ 5月10日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——雲計算資料壓縮方案++

⑫ 5月10日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——大資料架構性能優化系統++

⑬ 5月10日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——物聯網搖擺門趨勢算法++

【本期看點】

HCompress在多層存儲環境中大放光彩
揭秘消費類電子裝置軟體更新壓縮算法
AIMCS如何壓縮短字元串

【技術DNA】

【智慧場景】

**********	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************	********************
場景	自動駕駛 / AR	語音信号	流視訊	GPU 渲染	科學、雲計算	記憶體縮減	科學應用	醫學圖像	資料庫伺服器	人工智能圖像	文本傳輸	GAN媒體壓縮	圖像壓縮	檔案同步
技術	點雲壓縮	‎稀疏快速傅裡葉變換‎	有損視訊壓縮	網格壓縮	動态選擇壓縮算法架構	無損壓縮	分層資料壓縮	醫學圖像壓縮	無損通用壓縮	人工智能圖像壓縮	短字元串壓縮	GAN 壓縮的線上多粒度蒸餾	圖像壓縮	檔案傳輸壓縮
開源項目	Draco / 基于深度學習算法/PCL/OctNet	SFFT	AV1 / H.266編碼 / H.266解碼/VP9	MeshOpt / Draco	Ares	LZ4	HCompress	DICOM	Brotli	RAISR	AIMCS	OMGD	OpenJPEG	rsync

引言

“人工智能”大家應該不陌生，這算是近幾年的“熱詞”，而”壓縮算法“長期關注我們團隊的讀者也應該挺熟悉，但是何為“短字元串”呢？非計科專業背景的讀者乍一聽，可能有點茫然。簡而言之，我們聊qq，發微信用的一條條消息籠統的說就是短字元串，從專業角度定義的話，就是平均長度為160個字元的字元串。
現在大家對我們今天介紹的主角有了一個基本的認知，那麼接下來我們步入正題。

時代背景

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

應用場景

空間通信

【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮
inReach（手持式⭐衛⭐星⭐通信器）

【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮
⭐衛⭐星⭐回程

【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮
帶寬匮乏的移動網狀網絡

【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮

技術現狀

Huffman編碼

基本思想：基于字元串中字元的重複次數進行編碼，出現頻率越高編碼越短。
局限性：
1. 所有的資料和統計資訊都必須在壓縮時可用。不适合那些連續生成資料的應用程式。
2. 壓縮少量資料時，無法減少資料的大小，甚至随着開銷的增大而增大，壓縮後資料超過原始資料大小。

基于單詞的字元串壓縮方法。

基本思想：文本根據其大小進行分類。找到在不同大小文本中形成壓縮基本單元以提高壓縮性能。
基本單元分為三組: word 、 vavel 和 character （word是一組字元，而 vavel 比 character 短，但比 character 長）
- 文本的大小超過 5 MB ——> word
- 文字大小為 200 KB - 5 MB——> vavel
- 文本大小為 100 - 200 KB——> character
測試結果：該方法應用于資料大小為 100KB 的批資料

LZW算法

它是一種适合字元串壓縮的方法。LZW是1977年提出的LZ算法的改進版本。許多壓縮軟體如 winzip , pkzip , gzip 都是基于LZW的。
這種方法根據掃描目标文本動态更新構造字元串索引字典。
但是，這種方法不适合壓縮小字元串因為和哈夫曼編碼一樣有時字典和壓縮資料的大小會超過原始資料的大小

SMAZ

這種方法的目的是通過查找人們發送的消息的模式，找出重複次數最多的單詞，然後将這些單詞映射到索引中。
這種方法 減小了短文本消息的大小 。例如短文本在推特的比例分别為29%和19%。
SMAZ的缺點識别發送資訊的模式并不容易，特别是使用不同方言的人在與不同類型的人交談時發送的消息。

其他方案

一種利用BP網絡預測字元重複的方法，使資料量減少了30%。神經網絡被用于減小圖像的大小。提出了一種新的 實用的、通用的 字元串無損壓縮算法—— 神經馬爾可夫預測壓縮(NMPC) 。
該方法基于 貝葉斯神經網絡(BNN) 和 隐馬爾可夫模型(HMM) 的結合，具有線性處理時間、恒定的記憶體存儲性能和對并行的适應性。然而，這種方法适用于那些大小至少為8 KB的批資料，

結論

在大多數讨論的短文本壓縮方法中，壓縮資料的大小和壓縮開銷都大于原始資料的大小。

尚未解決問題

減少小字元串的大小。
是否适合壓縮不同語言和口音的文本
可以在生成資料流的應用程式中使用

針對所有讨論的挑戰和問題，我們提出了一種新的壓縮方法。

AIMCS

AIMCS顯著降低了資料的大小。将我們的算法與lzw和霍夫曼方法進行比較，也表明，在字元串的壓縮過程中，我們的方法在壓縮方面具有更好的性能。壓縮時間增加，壓縮時間增加，與需要實時文本傳輸時的傳輸時間相比不顯著。
AIMCS是一種 基于人工智能 的方法，用于壓縮 小于160位元組 的微小字元串。
我們已經考慮過這個大小的小字元串，因為在像Twitter這樣的即時消息傳遞網絡中，一條消息的遠小于160位元組。

基本方法

我們提出了一個四層壓縮小字元串的算法，其中形成了一個表，每個字元都映射到一個索引。是以，在下一次字元的重複使用中，将使用索引而不是字元，這會導緻資料大小的減少。

以“shorttexttest”為例

首先用A表存儲最初的字元串

【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮
然後把每個字元轉化成ASCII碼存儲在對應位置得到B表

【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮
接着統計每個字元的出現次數得到C表

【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮
- 記錄新字元插入從左到右的順序表每個字元的使用數量，索引編号，對應的字元和ASCll 碼。
接下來，同時考慮B和C，我們就可以得到D

【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮
- B 中的ASCII碼在d中分為兩種類型，
- “ ” 表示該字元為新字元，<用原來的ascll碼表>，“ 1 ”表示該字元是否重複。<用c中索引坐标代替>
E表就将其轉化為二進制代碼

【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮
- E 中前一位表示ASCII碼的類型（1 or 0），後四位等于索引或字元的最大二進制長度。
- 在 E1 中，ASCII碼和索引的二進制類型以每個類型的最大值的固定長度顯示。
- 在 E2 中，将E1的最大二進制長度不變的7個零加上.
G中，F中已有的位将被轉換成位元組，然後通過網絡媒體進行通信

【ELT.ZIP】OpenHarmony啃論文俱樂部——人工智能短字元串壓縮
- 接收端接收位元組，将其轉換為位，并将其插入到表中。最後，直接從比特中導出ASCII碼，進而實作“ shorttextttest ”。

注意事項

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

因為當較短的索引映射到最頻繁的字元時，字元串的總大小會減少。
表C的順序必須基于字元的使用數量

重複次數最多的字元必須在第一行，其他字元必須按照重複次數的降序排列。
當發送幾個字元時，必須檢出表C，確定行順序合适。如果順序不合适，表必須重新排序才能再次使用。
- 檢測重新排序表格所需的時間是我們進行這項研究的主要挑戰。
- 我們的最終目标是預測表重排序過程的評估時間，它直接影響壓縮比。
- B表的AIMCS在通信過程開始的時候，表是空的，沒有要排序的東西，這是表最适合的狀态。當發送幾個字元(Brecognition或β)時，表必須被檢出。
- 通過 排序品質 (Sq)公式(1)對表進行求值，n是重複次數，m是行數

- 上述公式的結果是一個介于0到1之間的數字，分别代表表的最佳狀态和最差狀态。
- 在表求值的每一步中，在發送 `βr` 字元後，将Sq公式得到的結果與常數參數a進行比較。
- 如果`Sq > a`，則`If -condition`為`true`，并且表必須重新排序，并且接收方也必須被告知表的重新排序。
- 如果我們認為a是一個小的數量，那麼被記錄的機會就會增加，進而增加更多的過載。
- 反之，如果我們認為a很大，表的情況就會很糟糕，會對壓縮比産生不利的影響。<br>

- 由圖2可知，“

period

”是表的最佳狀态到表必須重新排序的狀态之間的時間間隔。每個周期還由幾個子周期組成，它們分别顯示表的最佳狀态(白色矩形)、

if-condition

必須被檢查的狀态(綠色矩形)和表必須被重新排序的狀态(黑色矩形)。時期I和其他時期之間的差別是，在時期1中，表一開始是空的，但在其他時期，表包含一些實體，周期的長度可以不同。

- 在一個周期的第一步，經過ßr字元傳輸後，計算排序品質和壓縮率，将Sq與a進行比較。

- 如果

Sq < a

If -condition

為假，另一個

ß

為必須發送的資料量。

- 如果

Sq > a

，表必須重新排序。當

if-condition

為

True

時，此表用于提高神經網絡學習的準确性。

實驗

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

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

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

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

語言	類型	算法	原始大小(Bytes)	壓縮比(%)	運作時間(min)
English	SMS	LZW	80904070	85.60	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 壓縮這兩種文本的壓縮比

實驗二：壓縮阿拉伯和波斯語字元串（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 低，極大地降低了傳輸文本的時間和成本。

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

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

可以看到，随着消息數量的增加，AIMCS 在壓縮 tweet 的壓縮比會降低，壓縮性能會更好。

結果分析

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.

開源項目

整體概述

為了提高帶寬使用率和降低成本，我們提出了 AIMCS ，這是一種專門為壓縮短字元串 (平均長度為160個字元)而設計的壓縮算法。
AIMCS 接收一個短字元串作為輸入，并使用索引方法。然後它建立一個表，其中每個字元都映射到一個索引。是以，在下次字元重複使用時，使用索引代替字元，導緻資料的大小減少。正如描述中所提到的，這裡我們讨論我們在論文中提出的基本壓縮算法。是以， α 和 β 參數必須手動設定。例如，我們準備了幾個微小的字元串，它們被認為是由發送方連續生成的，并一個接一個地發送給接收方。AIMCS算法的介紹可以在youtube上找到。更多資訊也可以在本文和AIMCS首頁中找到。

在下面的内容中，我們将展示AIMCS代碼如何用于壓縮ascii和Unicode小字元串

執行要求

我們在Windows環境下用c#編寫了AIMCS算法。必須注意的是，代碼執行過程需要。net framework 2和Visual Studio。此外，AIMCSAv1.cs檔案必須添加到項目檔案中。

這裡我們提供了兩個壓縮 ASCII 小字元串的示例。在第一個示例(可以認為是我們的方法的模式)中展示了AIMCS如何壓縮一個小字元串。

例 1：

AIMCSAv1 AIMCSSend = new AIMCSAv1();
AIMCSAv1 AIMCSReceive = new AIMCSAv1();
byte[] t_byte = AIMCSSend.Compress("Mytext");
string decompressed = AIMCSReceive.Decompress(t_byte);

在第二個例子中，我們展示了 AIMCS 如何對幾個不同的小字元串進行壓縮。

例 2：

生成的小字元串可以在附加檔案 TinyStringExamples 中找到。在下面的文本中，我們對代碼的不同部分進行了解釋。
必須使用下列 .net 庫

using System;
using System.Text;
using System.IO;
using AIMCSA;

下面的函數讀取小字元串并将它們存儲在全局 Temp 數組中。 readTextFile 函數定義在這段代碼中的main函數之後。

readTextFile("TinyStringExmples.txt");

這部分代碼用于列印消息的數量(小字元串)和包含 TinyStringExamples 内容的臨時數組的大小。代碼如下：

Int32 originalSize = 0;
{
     int i = 0;
     for (; i < Temp.Length && Temp[i] != null; i++)
             originalSize += Temp[i].Length;
     Console.WriteLine("The number of strings:" + i.ToString());
     Console.WriteLine("\nThe size of original strings:" + '\t' + originalSize.ToString());
}

在接下來的部分中，将設定變量的初始值，并分别為發送方和接收方建立壓縮類(稱為 AIMCS )。如下所示，alpha和beta參數是手動設定的。

double sizeofNewMethod = 0;
int counterChar = 0;
int useResort = 0;
AIMCSAv1 AIMCSSend = new AIMCSAv1();
AIMCSAv1 AIMCSReceive = new AIMCSAv1();
AIMCSSend.beta = 70000;   //beta
AIMCSSend.alpha = 0.045;  //alpha

在下面的for循環中， AIMCS 類的對象在每次重複中壓縮微小的字元串。第一個 if-condition 還檢查表是否需要重新排序。如果需要重新排序，第二個If條件将重新排序表。

for (int i = 0; i < Temp.Length && Temp[i] != null; i++)
{
   byte[] t_byte = AIMCSSend.Compress(Temp[i]);
   counterChar += Temp[i].Length;
   sizeofNewMethod += t_byte.Length;
   string decompressed = AIMCSReceive.Decompress(t_byte);
   if (counterChar > AIMCSSend.beta)
    {
       counterChar = 0;
       AIMCSSend.checkUseOfChar();
       if (AIMCSSend.needResort)
       {
            useResort++;
            AIMCSSend.needResort = false;
            AIMCSSend.Resort();
            byte[] newTable = AIMCSSend.makeTableforSending();
            sizeofNewMethod += newTable.Length;
            AIMCSReceive.Decompress(newTable);
       }
    }

}

代碼的下一部分計算并列印壓縮比。

double percent = Math.Round((-1 * (((originalSize - sizeofNewMethod ) / originalSize) - 1)), 3);
Console.WriteLine("\nThe size of strings after getting compressed by AIMCS:" + '\t' + (sizeofNewMethod).ToString() +
                                 '\t' + percent.ToString() + "%" + '\t' + "Sort=" + useResort.ToString());         
Console.ReadKey();

下面的函數用于讀取必須壓縮的微小字元串。

public static void readTextFile(String path)
{
   path = AppDomain.CurrentDomain.BaseDirectory + "\\" + path;
   if (!File.Exists(path))
   {
       using (FileStream fs = File.Create(path))
       {
           Byte[] info =
                 new UTF8Encoding(true).GetBytes("The File Should replace this file.");
               fs.Write(info, 0, info.Length);
       }
   }
       int index = 0;
       string s = "";
       using (StreamReader sr = File.OpenText(path))
           while ((s = sr.ReadLine()) != null)
              Temp[index++] = s;
}

例2的輸出：

The number of strings:10101
The size of original strings:   584630
The size of strings compression with new method:        453206  0.775%  Sort=6

值得一提的是，該算法可用于壓縮任何應用程式上的任何類型的短字元串。
對于 Unicode 小字元串的壓縮，在上述代碼中，必須使用 AIMCSAv1 類而不是 AIMCSUv1 類。

出處

Github 項目首頁：MasoudAbedi/AIMCS-an-artificial-intelligence-based-method-for-compression-of-short-strings: The basic source code of the AIMCS algorithm (Abedi Method) that we presented in our paper in SAMI 2020. (github.com)
這個項目是在GNU Affero通用公共許可證v3.0下授權的-請參閱License 檔案了解詳細資訊。

附件連結：https://ost.51cto.com/resource/1986