【ELT.ZIP】OpenHarmony啃論文成長計劃——多維探祕通用無失真壓縮

語言: CN / TW / HK
  • 本文出自 ELT.ZIP 團隊,ELT<=>Elite(精英),.ZIP為壓縮格式,ELT.ZIP即壓縮精英。

  • 成員:

    • 上海工程技術大學大二在校生
    • 合肥師範學院大二在校生
    • 清華大學大二在校生
    • 成都資訊工程大學大一在校生
  • 我們是來自4個地方的同學,我們在OpenHarmony成長計劃啃論文俱樂部裡,通過啃論文方式學習作業系統技術...

@[toc]

引言

壓縮的標準方法是定義產生不同型別資料來源的類別,假設資料是由某一類源產生的,並應用為其特殊設計的壓縮演算法,若可以在近似為輸出的資料上良好執行,便可被稱為通用壓縮演算法

熵編碼器

  • 熵編碼器(entropy coder)是一種根據字元出現的概率為字母表中的每個字元分配編碼的方法。更有可能出現的字元被分配的編碼比不太可能出現的更短,這種方式可以使壓縮序列的預期長度最小。目前流行的熵編碼器是Huffman編碼器算術編碼器,這兩種方法都做到了相對最優,所以不能分配比預期長度更小的壓縮序列編碼。其中,Huffman在分配整數長度編碼的方法類中是最優的,算術編碼則不受這種限制,因此,它通常可產生更短的期望編碼長度。 圖1:序列abracadabra的Huffman樹 

圖2:算術編碼過程 

BWT演算法

  • 塊排序壓縮演算法(block-sorting compression algorithm),通常被稱為Burrows-Wheeler變換演算法*(Burrows–Wheeler compression algorithm)***,是一個被應用在資料壓縮技術(如bzip2)中的演算法,於1994年被Michael Burrows和David Wheeler在位於加利福尼亞州帕洛阿爾託的DEC系統研究中心發明。

  • 原理思想:

  1. 構造矩陣,其行儲存壓縮序列的所有單字元迴圈移位
  2. 按字典順序對行進行排序
  3. 使用矩陣最後一列進行後續處理

BWT演算法與以往的壓縮演算法有所不同,比較著名的壓縮演算法如Lempel-Ziv(LZ77,LZ78)、PPM、DMC針對的是通用的資料流模型,比如無記憶源(Memoryless sources),馬爾可夫源(Markov sources),有限階FSM源(finite-order FSM sources),一次讀取一個或多個位元組,而BWT可以處理成塊的資料。BWT演算法的核心思想是對一個字串中的字元進行位置變換,使相同的字元相鄰的概率增大。 上述過程被稱為Burrows-Wheeler變換*(BWT)*。隨後,變換的輸出由一個前移變換處理,最後階段,由熵編碼器壓縮,可以是Huffman編碼算術編碼。結果是,獲得了一個序列,其中出現在相似上下文中的所有字元被分組。 字串經過BWT演算法轉換後並沒有被壓縮,而是因其極有規律性的字母內聚的特點使其他文字壓縮演算法大大簡化,提高壓縮速率和壓縮比。

基於BWT演算法的重要特點是執行速度快、壓縮比合理,比LZ演算法好得多,只比現有最佳部分匹配*(PPM, prediction by partial matching)*演算法稍差;是Ziv-Lempel快速壓縮演算法和PPM演算法的有趣替代品,前者壓縮比較差,後者壓縮比較好,但工作速度較慢

  • 對於一個長度為n的序列x,可以將序列輪轉形成一個的矩陣: 然後將矩陣以行為單位按照字母表順序重新排列成矩陣,得到,並用R(x)記錄在新矩陣中原序列x所在的行數。取矩陣的最後一列記為即得到BWT的最終結果。

下面我們用字元序列x=“abracadabra”,且為了獲得更好的關係型別的序列,我們在x前加上哨兵字元“$”。最終得到x^bwt^ = $drcraaaabba,R(x) = 1。可以看出通過BWT演算法,一些字元連續出現的概率增大

BWT演算法的逆過程則比較複雜,但在程式設計實現上也比較簡單。其主要思想是以x^bwt^為基礎,對字元序列進行轉移、排序和組合構建BWT轉換後得到的矩陣M~(x)。還是以$drcraaaabba為例:

輸入 轉移 排序 組合
-----------$ $----------- a----------- a----------$
-----------d d----------- a----------- a----------d
-----------r r----------- a----------- a----------r
-----------c c----------- a----------- a----------c
-----------r r----------- a----------- a----------r
-----------a a----------- b----------- b----------a
-----------a a----------- b----------- b----------a
-----------a a----------- c----------- c----------a
-----------a a----------- d----------- d----------a
-----------b b----------- r----------- r----------b
-----------b b----------- r----------- r----------b
-----------a a----------- $----------- $----------a
輸入 轉移 排序 組合
a----------$ $a---------- ab---------- ab---------$
a----------d da---------- ab---------- ab---------d
a----------r ra---------- ac---------- ac---------r
a----------c ca---------- ad---------- ad---------c
a----------r ra---------- a$---------- a$---------r
b----------a ab---------- br---------- br---------a
b----------a ab---------- br---------- br---------a
c----------a ac---------- ca---------- ca---------a
d----------a ad---------- da---------- da---------a
r----------b br---------- ra---------- ra---------b
r----------b br---------- ra---------- ra---------b
$----------a a$---------- $a---------- $a---------a
輸入 轉移 排序 組合
ab---------$ $ab--------- abr--------- abr--------$
ab---------d dab--------- abr--------- abr--------d
ac---------r rac--------- aca--------- aca--------r
ad---------c cad--------- ada--------- ada--------c
a$---------r ra$--------- a$a--------- a$a--------r
br---------a abr--------- bra--------- bra--------a
br---------a abr--------- bra--------- bra--------a
ca---------a aca--------- cad--------- cad--------a
da---------a ada--------- dab--------- dab--------a
ra---------b bra--------- rac--------- rac--------b
ra---------b bra--------- ra$--------- ra$--------b
$a---------a a$a--------- $ab--------- $ab--------a
輸入 轉移 排序 組合
abr--------$ $abr-------- abra-------- abra-------$
abr--------d dabr-------- abra-------- abra-------d
aca--------r raca-------- acad-------- acad-------r
ada--------c cada-------- adab-------- adab-------c
a$a--------r ra$a-------- a$ab-------- a$ab-------r
bra--------a abra-------- brac-------- brac-------a
bra--------a abra-------- bra$-------- bra$-------a
cad--------a acad-------- cada-------- cada-------a
dab--------a adab-------- dabr-------- dabr-------a
rac--------b brac-------- raca-------- raca-------b
ra$--------b bra$-------- ra$a-------- ra$a-------b
$ab--------a a$ab-------- $abr-------- $abr-------a
輸入 轉移 排序 組合
abra-------$ $abra------- abrac------- abrac------$
abra-------d dabra------- abra$------- abra$------d
acad-------r racad------- acada------- acada------r
adab-------c cadab------- adabr------- adabr------c
a$ab-------r ra$ab------- a$abr------- a$abr------r
brac-------a abrac------- braca------- braca------a
bra$-------a abra$------- bra$a------- bra$a------a
cada-------a acada------- cadab------- cadab------a
dabr-------a adabr------- dabra------- dabra------a
raca-------b braca------- racad------- racad------b
ra$a-------b bra$a------- ra$ab------- ra$ab------b
$abr-------a a$abr------- $abra------- $abra------a

按照這樣的規律一直操作下去,最終可以得到:

輸入 轉移 排序 組合
abracadabr-$ $abracadabr- abracadabra- abracadabra$
abra$abrac-d dabra$abrac- abra$abraca- abra$abracad
acadabra$a-r racadabra$a- acadabra$ab- acadabra$abr
adabra$abr-c cadabra$abr- adabra$abra- adabra$abrac
a$abracada-r ra$abracada- a$abracadab- a$abracadabr
bracadabra-a abracadabra- bracadabra$- bracadabra$a
bra$abraca-a abra$abraca- bra$abracad- bra$abracada
cadabra$ab-a acadabra$ab- cadabra$abr- cadabra$abra
dabra$abra-a adabra$abra- dabra$abrac- dabra$abraca
racadabra$-b bracadabra$- racadabra$a- racadabra$ab
ra$abracad-b bra$abracad- ra$abracada- ra$abracadab
$abracadab-a a$abracadab- $abracadabr- $abracadabra

最後一次操作的得到的組合即為x對應的矩陣M~(x),矩陣的第一行去掉最後的“$“就得到原字元序列x=”abracadabra”。

請新增圖片描述 BWT就是一個加標記,迴圈轉移,算出陣列,輸出結果的過程。

① 這裡我們輸入字串ababc,並給其加上標記得到ababc$這個標記$要比所有字元都要小。 請新增圖片描述

② 之後我們對處理後的字串進行迴圈轉移,此時你可以把ababc$當作一個圓,然後讓其旋轉,使得F列(第一列)的字元按照ASCII碼從小到大排列。 請新增圖片描述 請新增圖片描述

③ 得到的M陣列最後一列便是輸出的L列

BWT編碼及解碼的C++實現:

#include <iostream>
#include <string>
#include <algorithm>
#include <string.h>
using namespace std;

///編碼,生成last陣列
int getLastArray(char *lastArray,const string &str){    ///子串排序
    int len=str.size();
    string array[len];

    for(int i=0;i<len;i++){
        array[i] = str.substr(i);
    }
    sort(array,array+len);
    for(int i=0;i<len;i++){
        lastArray[i] = str.at((2*len-array[i].size()-1)%len);
    }
    return 0;
}

int getCountPreSum(int *preSum,const string &str){
    memset(preSum,0,27*sizeof(int));
    for(int i=0;i<str.size();i++){
        if(str.at(i) == &#039;#&#039;)
            preSum[0]++;
        else
            preSum[str.at(i)-&#039;a&#039;+1]++;
    }

    for(int i=1;i<27;i++)
        preSum[i] += preSum[i-1];
    return 0;
}

///解碼,使用last陣列,恢復原來的文字塊
int regainTextFromLastArray(char *lastArray,char *reGainStr,int *preSum){
    int len=strlen(lastArray);
    int pos=0;
    char c;
    for(int i=len-1;i>=0;){
        reGainStr[i] = lastArray[pos];
        c = lastArray[pos];
        pos = preSum[c-&#039;a&#039;]+count(lastArray,lastArray+pos,c);
        i--;
    }
    return 0;
}

int main (){
    string str("sdfsfdfdsdfgdfgfgfggfgdgfgd#");
    int preSum[27];
    int len=str.size();

    char *lastArray = new char[len+1];
    char *reGainStr = new char[len+1];
    lastArray[len]=&#039;&#039;;
    reGainStr[len]=&#039;&#039;;

    getCountPreSum(preSum,str);
    getLastArray(lastArray,str);
    regainTextFromLastArray(lastArray,reGainStr,preSum);

    cout<<"       str: "<<str<<endl;
    cout<<"lastArray : "<<lastArray<<endl;
    cout<<"reGainStr : "<<reGainStr<<endl;

    delete lastArray;
    delete reGainStr;
    return 0;
}

研究者提出一種基於 Burrows-Wheeler 變換的改進演算法,該演算法在獲得最佳壓縮比的同時,其運算速度可以與該類演算法中最快的演算法媲美。

基於BWT的改進演算法

一般結構

演算法的第一階段是Burrows-Wheeler變換。BWT輸出序列在第二階段經歷一個加權頻率計數變換,第三階段是零執行長度編碼,它減少了0次執行的長度。在最後階段,序列x^(rle-0)^由二進位制算術編碼器編碼。算術編碼是一種行之有效的熵編碼方法,其中最重要的部分是概率估計方法。BWT只是對序列x的轉換,並不起到壓縮的作用,經過BWT演算法編碼後的序列還需要通過其他壓縮演算法才可以完成整個壓縮任務: 圖3:基於BWT的改進演算法

  • MTF*(Move-To-Front)*是一種資料編碼方式,作為一個額外的步驟,用於提高資料壓縮技術效果。MTF主要使用的是資料“空間區域性性”,也就是最近出現過的字元很可能在接下來的文字附近再次出現。MTF的主要思想是:
  1. 首先維護一個序列字符集大小的棧表,其中每個不同的字元在其中佔一個位置,位置從0開始編號
  2. 掃描需要重新編碼的序列資料,對於每個掃描到的字元,使用該字元在棧表中的索引替換,並將該字元提到棧表的棧頂的位置(索引為0的位置)
  3. 重複上一步驟,直到序列掃描結束

以經過BWT演算法得到的x^bwt^ = drcraaaabba為例:

迭代 序列 棧表
d 3 abcdr
r 4 dabcr
c 4 rdabc
r 1 crdab
a 3 rcdab
a 0 arcdb
a 0 arcdb
a 0 arcdb
b 4 barcd
b 0 barcd
a 1 abrcd

最終的得到的x^mtf^為34413000401. 相比於BWT演算法,MTF演算法的解碼過程更為簡單,其實就是上述過程的逆過程

序列 棧表 字元
34413000401 abrcd a
3441300040 barcd b
34413000 arcdb a
3441300 arcdb a
344130 arcdb a
34413 arcdb a
3441 rcdab r
344 crdab c
34 rdabc r
3 dabcr d

根據上表所示過程即可解碼x^mtf^.

  • RLE-0(Zero run length encoding)叫做零遊程編碼,不同於一般的RLE演算法,它只對序列中的0進行替換。在這裡使用RLE-0處理序列是由於經過BWT和MTF兩個過程,一般在序列中會存在大量的連續的零,因此用RLE-0對x^mtf^進行編碼會起到一定的壓縮效果。

RLE-0的原理是:

  1. 統計序列中由0組成的子序列含0的個數
  2. 用0~a~和0~b~符號表示數字m

第2步的具體做法是,先將(m+1)轉換成二進位制數,然後用0~a~代替0,0~b~代替1,最後捨棄最高位:

0的個數m m+1的二進位制表示 替換後 RLE-0 編碼
1 10 0~b~0~a~ 0~a~
2 11 0~b~0~b~ 0~b~
3 100 0~b~0~a~0~a~ 0~a~0~a~
4 101 0~b~0~a~0~b~ 0~a~0~b~
5 110 0~b~0~b~0~a~ 0~b~0~a~
6 111 0~b~0~b~0~b~ 0~b~0~b~
7 1000 0~b~0~a~0~a~0~a~ 0~a~0~a~0~a~
... ... ... ...

所以,x^mtf^ = 34413000401 經過RLE-0演算法得到的序列為x^rle-0^ = 344130~a~0~a~40~a~1,由於這裡的序列x過短,所以零遊程編碼的壓縮效果並未很好的體現出來;RLE-0的解碼過程就是根據個數和編碼的對應關係序列中的0~a~,0~b~替換成對應個數的0

實際效率

  • 選擇測試資料 為了比較壓縮演算法,需要一組檔案。通常情況下,有兩種選擇測試檔案的方式:
  1. 使用一個眾所周知的資料集
  2. 為測試準備新的資料集
  • 多標準優化 通常情況下,現實世界中有許多標準,我們不能優化所有的標準,所以不得不選擇一種折衷方案。如果沒有詳細瞭解將壓縮應用於的具體情況,我們就無法選擇最佳的壓縮方法。因此,這種情況下便需要討論多標準優化*(multi criteria optimisation)。 1896-1897年,Pareto首次對該領域進行了研究,討論了滿足許多排他性標準的問題。1906年,Pareto在他的著名著作《Manuale di economia politica, conuna introduzione alla scienca Sociale》中提出了非支配解決方案(non-dominated solutions)*的概念。其在經濟學術語中提出這樣一種解決方案:作為一種解決方案,沒有任何一個人可以更滿意而別人一點不滿意。目前,稱此解決方案為Pareto最優解,即,不是非劣勢解的解為劣勢解。 

有一些標準Q~1~,Q~2~...,Q~m~取決於一些變數: (1) Q~i~ = Q~i~(q~1~,q~2~,...,q~r~), 當 i = 1, 2, ... , m 一組變數: (2) q = <q~1~,q~2~,...,q~r~> 被稱為優化中的一個點。點q被稱為Pareto-optimal,如果沒有其他點p例如 (3) ∀1≤i≤m Q~i~(p) ≥ Q~i~(q) 多標準優化的目標是找到所有Pareto最優點的集合。Pareto最優集(方程3)的公式適用於所有標準Q~i~最大化的情況。一般情況下,所有或某些標準可以被最小化。 壓縮質量至少有三個標準:壓縮比、壓縮速率、解壓速率。通過每個輸入字元(bpc)的平均輸出位數度量壓縮比,因此壓縮比越小,效果越好

演算法比較

檢驗演算法

  • A02 —— 基於BWT的演算法,反演頻率變換作為第二階段,結果來自Arnavut的工作
  • acb —— Buyanovsky的關聯編碼器,壓縮結果來自於acb 2.00c專案的實驗
  • B97 —— Bunton提出的PPM演算法的最佳版本
  • boa —— 由Sutton編寫的boa 0.58b壓縮程式,是PPM演算法的實現
  • BS99 —— Balkenhol和Shtarkov提出的基於BWT的演算法
  • BW94 —— 初始Burrows-Wheeler演算法
  • Bzip —— Seward編寫的bzip 0.21壓縮程式,實現了與Fenwick方法的相同壓縮比
  • CTW —— Willems等提出的上下文樹加權方法
  • DM —— 基於BWT的改進演算法,第二階段是移動到前端的變換
  • DW —— 基於BWT的改進演算法,第二階段是加權頻率計數變換
  • F96 —— Fenwick提出的基於BWT的演算法,在Silesia corpus實驗的bzip 0.21程式中取得了相同壓縮比
  • gzip —— 標準gzip程式,是著名的LZ77演算法的實現
  • LDMC —— 目前最好的動態Markov編碼演算法,最初由Cormack和Horspool 引入,是由Bunton改進的LazyDMC版本
  • lgha —— 速度優化的ha壓縮程式,由Lyapko提供實現
  • LZMA —— Pavlov提出的Ziv-Lempel演算法,結果來自7-zip程式的實驗
  • LZW —— 標準UNIX壓縮程式,是LZW演算法的一個實現
  • MH —— Shkarin提出的cPPMII演算法,結果來自PPMonstr var. H程式的實驗
  • MI4 —— Shkarin的cPPMII演算法,結果來自4階PPMonstr var. I程式的實驗
  • MI64 —— Shkarin的cPPMII演算法,結果來自64階PPMonstr var. I程式的實驗
  • PPMdH —— Shkarin提出的PPMII演算法,結果來自PPMd var. H程式的實驗
  • PPMN —— Smirnov 的 PPMN 演算法,結果來自*ppmnb1+*程式的實驗
  • rar —— rar 2.90壓縮程式
  • szip —— Schindler提出的基於BWT的演算法,結果來自szip程式的實驗
  • T98 —— Teahan提出的PPMD+演算法,結果來自*ppmd+*程式的實驗
  • ufa —— Pavlov提出的二進位制PPM演算法,結果來自* ufa 0.04 Beta 1*程式的實驗
  • VW98 —— Volf和Willems提出的切換演算法
  • WM01 —— 基於BWT的最佳演算法,無第二階段,結果來自Wirth和Moffat的工作
  • ybs —— 基於BWT的壓縮程式,距離編碼器變換作為第二階段,是Yoockin的實現

表1:以bpc為單位的壓縮比 

表2:以bpc為單位的標準化壓縮比 

表3:以秒為單位的壓縮時間 

表4:以秒為單位的解壓時間 

以上其中幾幅表對解壓速度和壓縮比進行了比較。我們可以看到,PPM演算法的解壓速度幾乎與其壓縮速度相同;LZ演算法解壓比壓縮快得多;基於BWT演算法的解壓與壓縮速度之間有著明顯的差異,但低於LZ演算法;PPMdH演算法僅支配了兩種基於BWT的演算法,但其平均解壓縮速度的標準差遠遠高於這兩種演算法;DM演算法是Pareto最優的,而其在基於BWT的演算法中取得了最佳壓縮比;測試中的LZMA演算法實現了LZ系列中的最佳壓縮比,但其壓縮速度慢,比最慢的基於BWT的演算法慢兩倍以上,解壓速度方面優於所有基於BWT的演算法及LZW演算法。


實驗結論

演算法 優點 缺點
cPPMII 壓縮比顯著優 執行速度慢、記憶體消耗高
LZMA 壓縮比明顯優、解壓速度快 壓縮速度慢
PPM 壓縮比明顯優 壓縮、解壓速度慢
基於BWT系列 大檔案壓縮速度較快 小檔案壓縮比較差
  • 從多準則優化的角度對實驗結果進行分析,可將這些方法粗略地分為三組:
  1. 包括PPM、CTW、DMC演算法,達到了最佳壓縮比,但速度較慢
  2. 包括LZ演算法,速度較快,但壓縮比較差
  3. 包括基於BWT系列演算法,比PPM執行速度快,比LZ有更好的壓縮比

在基於BWT系列中,最佳壓縮比的是本文改進演算法——DW,其執行速度與其他BWT系列演算法相當。對不同大小檔案的測試表明,DW的壓縮與解壓速度比其他基於BWT的大尺寸塊演算法相對更穩定。

Lempel-Ziv Parsing

概述

Lempel-Ziv 演算法由 Abraham LempelJacob Ziv 在《A Universal Algorithm for Sequential Data Compression》最早引入。和 Burrows-Wheeler 演算法一樣,Lempel-Ziv的名稱也是由其發明者命名。

Lempel-Ziv 演算法有兩個版本,根據發明日期分別為 1977年的LZ77 和 1978年的LZ78,其後又衍生出了不少像deflate,lzx,lzma這樣優秀的變體演算法。 請新增圖片描述

這裡有一個比較有意思的事情,仔細看,會發現先發明出的LZ77演算法的變體比LZ78多,是因為LZ77被人們使用的時間長嗎?並不是,這是因為LZ78演算法在1984年被Sperry申請了其變體lzw演算法的專利,並開始起訴相關軟體供應商等在沒有許可證的情況下使用率GIF格式,之後LZ78演算法的普及逐漸衰減。儘管LZW的專利問題已經平息,並出現了很多 LZW變體,但目前只有在 GIF壓縮中被普遍使用,佔據主導地位的仍是LZ77演算法。

儘管 Lempel-Ziv演算法有很多變體,但它們都有一個共同的思想:<u>如果一些文字不是均勻隨機的,也就是說,所有字母出現的可能性不一樣,那麼已經出現過的子串會比沒有看過的子串更可能再次出現。</u>舉個例子,在我們日常生活中,我們都有一些日用語,比如“你好”,“你好嗎”;那麼,“你好”,“你好嗎”,“你好嗎”中包含字串“你好”,我們便可以把“你好”簡化為更短的二進位制碼,來替換“你好嗎”中的“你好”,從而簡化編碼。

LZ78

LZ78 演算法通過構建出現在⽂本中的⼦字元串字典來⼯作。

演算法有兩種情況:

  1. 若當前字元未出現在字典中,則將該字元編碼進字典
  2. 若當前字元出現在字典中,則從當前字元開始與字元做最長匹配,並將匹配到的最長子串後的第一個字元做特殊處理,並編碼進字典。

舉例:假設我們有字串 AABABBBABA ,我們使用 LZ78演算法對其進行壓縮 請新增圖片描述

① 先從左邊最短並從未出現過的短語開始,這裡是A,放入字典。 請新增圖片描述

② 接下來考慮剩下的字串,由於之前已經見過A了,匹配最長字串A,並取最長字串的下一個字元做特殊處理,取AB放入字典 請新增圖片描述

③ 再考慮剩下的字串,由於之前已經見過A了,繼續匹配下一位B,此時最長字串為AB,繼續匹配下一位,未匹配到最長字串,取ABB編入詞典 請新增圖片描述

④ 考慮剩下的字串,第一個字元是B,未匹配到最長字串,編入詞典 請新增圖片描述

⑤ 同理,匹配剩下的字元,匹配到最長字串AB,連同下一位編入詞典 請新增圖片描述

由於序號(index)2的字串AB中有A,可以用A的序號來替換字串A,編碼AB1B。同理,序號(index)3的字串ABB中有最長字串AB,可以用AB的序號替換ABB中的AB,編碼為2B。序號(index)4的字串B與前面的字串沒有匹配,為空集Ø,編碼為0B。序號(index)5的ABA編碼為2A請新增圖片描述

此時,我們就用字典將原來的字串編碼成了一個更簡單的串,簡化了相關變數,此時我們只需要給A和B賦值即可得到最終編碼的二進位制串。這裡假設A=0B=1請新增圖片描述

  • LZ78 演算法動態構建其字典,只遍歷資料一次,這意味著不必在開始編碼之前接收整個⽂檔。

雙標準資料壓縮

請新增圖片描述

概述

  • 問題: 解決 LZ77解析的<u>壓縮空間大小</u>和<u>解壓縮時間</u>的問題。

  • 目標:

  1. 確定一個 LZ77 解析,<u>在給定的時間T最小化壓縮檔案的空間佔用</u>
  2. 相應的,交換時間與空間兩種角色,<u>在預先給定壓縮空間中最小化壓縮時間</u>
  • 如何實現目標:
  1. 引入新的 Bicriteria LZ77-Parsing 問題,它以一種原則性的方式形式化了資料壓縮器傳統上通過啟發式方法處理問題
  2. 通過證明和部署加權圖的一些特定結構屬性,在 O(n log n²) 時間和 O(n) 空間字中有效地解決了這個問題,直到可以忽略的附加常數輸入檔案的 LZ77 解析
  3. 進行初步實驗,表明所製作的新型壓縮器對市面上高度工程化的競爭對手 (如 Snappy,LZMA,Bzip2)都具有很強的競爭力。

介紹

在這裡插入圖片描述

壓縮思想

隨著<u>海量資料集的出現</u>以及<u>隨之而來的高效能分散式儲存系統的設計</u>,不少大廠紛紛行動,企圖製作出一款可以實現<u>有效壓縮比</u>和非常<u>高效的解壓縮速度</u>的壓縮器,例如 Google的<a herf="[BigTable_百度百科 (baidu.com)](https://baike.baidu.com/item/BigTable/3707131)">BigTable </a>,Facebook的<a herf="[cassandra(開源分散式NoSQL資料庫系統)_百度百科 (baidu.com)](https://baike.baidu.com/item/cassandra/20140772)">Cassandra</a>,Apache的<a herf="[Hadoop_百度百科 (baidu.com)](https://baike.baidu.com/item/Hadoop)">Hadoop</a>等等,這些無不都重新點燃了科學界對更優秀的無失真壓縮器的設計的激情。

解決無失真壓縮器的有效壓縮比與實現非常高效的解壓縮速度之間的問題,打破效能瓶頸的方法有很多種,但從很多無失真壓縮器相關的論文中,都有一種思想:"<u><font color="red">compress once,decompress many times</font></u>"。(參考翻譯軟體及個人理解,翻譯為:一次壓縮,多次解壓縮)。

這種思想又可以被分為兩大家族,<font size="2" color="red">①</font><u>基於 Burrows-Wheeler 變換的壓縮器</u>和<font size="2" color="red">②</font><u>基於 Lempel-Ziv 解析方案的壓縮器</u>。 請新增圖片描述 這兩大家族的壓縮器在壓縮和解壓資料時需要的時間都是線性的,並且需要的壓縮空間可以用輸入的K階經驗熵來約束。

對兩個問題的思考

一直以來,時間和空間似乎一直是演算法中相互對立,但又相互依存的兩個因素,經常刷 leetcode 的人一定對此深有感觸,當我們解開一道演算法題,很多人又會精進自己的演算法,試圖用“空間換時間”,“時間換空間”,以及嘗試平衡兩者來降低自己的執行用時和記憶體消耗,來獲得更多的效益。 請新增圖片描述

壓縮演算法也是如此,要麼犧牲有效壓縮比,要麼犧牲解壓縮速度,或者嘗試用強大的技巧來平衡兩者,一直以來研究這個無失真壓縮器的人歸根到底都是在研究這個問題。由於研究困難,於是引出了兩個應用方面具有挑戰性的問題:

  • 分散式儲存系統問題(時間是主要影響因素): 分散式儲存系統,將資料分散儲存在多臺獨立的裝置上,可以拓展儲存空間,Google,阿里等網際網路公司,管理超過千萬億位元組級別的大資料,它們對效能的要求很高,需要更低的解壓縮時間。於是Snappy,LZ4等壓縮器出現,幫助解決分散式儲存系統上對解壓縮時間要求更低的情況。

  • 空間是主要影響因素的問題: 我們日常用的手機,手錶,平板等等,這些裝置對空間拓展比較難,需要儘可能在不改變其解壓縮速度的情況下降低其壓縮比,來讓這些難以拓展記憶體的裝置更好地利用記憶體。

Bicriteria Data Compression(雙標準資料壓縮),即解決這個問題: 請新增圖片描述

簡單描述,兩個引數(輸入檔案S限定時間T),解決一個目標(<u>控制解壓縮時間這個變數,儘可能的降低其壓縮比</u>),再反過來(<u>控制其壓縮比,儘可能地降低其解壓縮時間</u>)。

想要解決這個問題,我們就要解決<font color="red">兩個因素</font>:

  • ① 將該雙標準優化將在S的壓縮版本中進行。 解決這個因素,原文采取基於LZ77的壓縮器類別,因為它們在理論上和實踐中占主導地位。使用主流壓縮器,可以借鑑前人經驗,幫助我們解決更多問題。

  • ② 衡量待優化資源的計算模型 對於這個因素,可以從幾個常用計算模型中得到啟發,這些模型對多級記憶體層次和連續記憶體字的獲取進行了抽象。

三大貢獻:

    1. 提出新的圖模型 在《On the bit-complexity of Lempel-Ziv compression》中,提出了一個特殊的加權DAG,這個DAG由<font size="2" color="red">①</font><u>n=|S| 個 節點(nodes),每個節點代表 S 的一個字元</u>和<font size="2" color="red">②</font><u>m=O(n²) 條邊(edges),每條邊代表 LZ77 解析 S後可能出現的短語</u>組成: 請新增圖片描述

具有兩個權重(時間權重,空間成本)的新的圖模型,<u><font color="red">時間權重</font>即解壓縮短語的時間(根據上面提到的分層記憶模型派生)</u>,<u><font color="red">空間成本</font>即用於計算儲存與該邊關聯的 LZ77 短語所需的位數(根據壓縮機中採用的整數 編碼器匯出)</u>

    1. 證明並使用加權DAG的一些結構特性 之後證明了上述的加權DAG的一些結構特性,使得我們能夠設計一種演算法,在 O(n log² n ) 時間和 O(n) 的工作空間內近似地解決我們版本的 WCSPP。
    1. 將新的壓縮器與其它壓縮器對比 最後提出了一組初步的實驗結果,將我們的壓縮器的實現與最先進的基於LZ77 的演算法(Snappy、LZMA、LZ4、gzip)和基於BWT的演算法(具有有界和無界 的記憶體佔用)進行比較。

首先,它們為本文開始時 提出的兩個相關問題提供了實際依據,併為文中新穎的雙標準資料壓縮問題引入的理論分析。 請新增圖片描述

實驗結果表現出文中解析策略通過表現出接近Snappy和LZ4(即已知 最快的)的解壓速度,以及接近基於BWT和LZMA的壓縮器(即更簡潔的)的壓縮率, 在所有高度工程化的競爭對手中佔了優勢。

連續小波變換

**連續小波變換(CWT)**通常被用於訊號分析,即科學研究類。小波變換現在被大量不同的應用領域採納,有時甚至會取代了傅立葉變換的位置,在許多領域都有這樣的轉變。例如很多物理學的領域亦經歷了這個轉變,包括分子動力學,從頭計算(ab initio calculations),天文物理學,密度矩陣區域性化,地球物理學,光學,湍流,和量子力學。其他經歷了這種變化的學科有影象處理,血壓,心率和心電圖分析,DNA分析,蛋白質分析,氣象學,通用訊號處理,語言識別,計算機圖形學,和多分形分析

小波分析的產生是由於,最初用於處理資訊的技術,FT傅立葉變換,僅可在忽略時頻分量的情況下進行,但是相對於實際應用情形,絕大多數資訊的時頻分量是一個不可忽視的因素,為此對FT進行一定程度的優化,得到STFT即短時傅立葉變換。短時距傅立葉變換是傅立葉變換的一種變形用於決定隨時間變化的訊號區域性部分的正弦頻率和相位。實際上,計算短時距傅立葉變換(STFT)的過程是將長時間訊號分成數個較短的等長訊號,然後再分別計算每個較短段的傅立葉轉換。通常拿來描繪頻域與時域上的變化,為時頻分析中其中一個重要的工具。但是在實際應用的過程中我們又遇見了新的問題,人們無法知道訊號的確切時頻表示,即人們無法獲知在何種時間例項中存在何種頻譜分量。人們可知曉的是某些頻段存在的時間間隔,(其根源可以追溯到海森堡不確定性原理,但在這裡我們不做詳細論述。)這是一個解析度問題。

例證:

  • 我們使用的視窗函式只是一個高斯函式,形式為e^{-a \left( \frac{t^2}{2} \right)} 其中 a 確定視窗的長度,t 是時間。下圖顯示了由 a 的值確定的不同支援區域的四個視窗函式。請忽略 a 的數值,因為計算此函式的時間間隔也決定了函式。只需記下每個視窗的長度即可。上面給出的示例是使用第二個值 a = 0.001 計算得出的。現在,我們將顯示上面給出的與其他視窗計算的相同訊號的STFT。

首先,讓我們看一下第一個最窄的視窗。我們預計STFT具有非常好的時間解析度,但頻率解析度相對較差:

下圖顯示了此 STFT。該圖從頂部鳥瞰圖顯示,並帶有一個角度,以便更好地解釋。請注意,這四個峰值在時間上彼此之間有很好的分離。另請注意,在頻域中,每個峰值都覆蓋一個頻率範圍,而不是單個頻率值。現在,讓我們將視窗變寬,並檢視第三個視窗(第二個視窗已在第一個示例中顯示)。

請注意,與之前的情況不同,峰值在時間上彼此之間沒有很好的分離,但是,在頻域中,解析度會進一步提升,我們進一步增加視窗的寬度。左圖就明顯的體現出了當視窗過寬時解析度比較差。

鑑於上述問題CWT(連續小波變換)應運而生。

STFT與CWT之間的兩個主要區別

  1. 不採用視窗訊號的傅立葉變換,因此將看到對應於正弦的單個峰值,即不計算負頻率。
  2. 當為每個光譜分量計算變換時,視窗的寬度會發生變化,這可能是小波變換最重要的特徵。

公式表達:

CWT_x^\psi(\tau,s) = \Psi_x^\psi(\tau,s) = \frac{1}{\sqrt{|s|}} \int x(t) \psi^* \left( \frac{t - \tau}{s} \right) dt

如上面的等式所示,變換後的訊號是兩個變數的函式,tau 和 s,分別是平移標度引數。\psi(t) 是變換函式,稱為母小波,母小波是用於生成其他視窗函式的原型 如圖所示,訊號由 30 Hz、20 Hz、10 Hz 和 5 Hz 的四個頻率分量組成。

請注意,軸是平移和縮放,而不是時間和頻率。然而,平移與時間嚴格相關,因為它指示母小波的位置。母小波的平移可以被認為是自 t = 0 以來經過的時間。

較小的刻度對應於較高的頻率,即頻率隨著刻度的增加而降低,因此,比例約為零的圖形部分實際上對應於分析中的最高頻率,而具有高尺度的標度對應於最低頻率。

訊號首先具有 30 Hz(最高頻率)分量,這在 0 到 30 的轉換時以最低刻度顯示。然後是20 Hz分量,第二高頻率,依此類推。5 Hz 分量出現在平移軸的末端(如預期的那樣),並按預期再次以較高的比例(較低頻率)顯示。

OpenHarmony核心子系統之Linux

OpenHarmony的Linux核心基於開源Linux核心LTS 4.19.y / 5.10.y 分支演進,在此基線基礎上,回合CVE補丁及OpenHarmony特性,作為OpenHarmony Common Kernel基線。針對不同的晶片,各廠商合入對應的板級驅動補丁,完成對OpenHarmony的基線適配。

EROFS檔案系統

EROFS 檔案系統代表增強型只讀檔案系統。與其他只讀檔案系統不同,它旨在為靈活性、可擴充套件性而設計,但要保持簡單和高效能。EROFS由華為於2018年開源,現已合入Linux核心主線,在4.19版本釋出:

資料壓縮

  • EROFS 實現了 LZ4 固定大小演算法的輸出壓縮,與其他現有的固定大小的輸入解決方案相比,它從可變大小的輸入生成固定大小的壓縮資料塊。使用固定大小的輸出壓縮可以獲得相對更高的壓縮率,因為現在流行的資料壓縮演算法大多基於 LZ77,這種固定大小的輸出方法可以從歷史字典中受益。
  • 具體來說,原始資料被轉換成幾個可變大小的範圍,同時被壓縮成物理叢集。為了記錄每個可變大小的範圍,引入邏輯簇作為壓縮索引的基本單元,以指示是否在範圍內生成新的範圍。
         |<-    variable-sized extent    ->|<-       VLE         ->|
       clusterofs                        clusterofs              clusterofs
         |                                 |                       |
_________v_________________________________v_______________________v________
... |    .         |              |        .     |              |  .   ...
____|____._________|______________|________.___ _|______________|__.________
    |-> lcluster <-|-> lcluster <-|-> lcluster <-|-> lcluster <-|
         (HEAD)        (NONHEAD)       (HEAD)        (NONHEAD)    .
          .             CBLKCNT            .                    .
           .                               .                  .
            .                              .                .
      _______._____________________________.______________._________________
         ... |              |              |              | ...
      _______|______________|______________|______________|_________________
             |->      big pcluster       <-|-> pcluster <-|

由此可見,作業系統效能的提升能力一定程度上取決於其所採用的檔案系統,壓縮演算法是檔案系統設計上尤其重要同時又是不可或缺的一環。按照以上思路,我們得到如下具體例項:

/dev/block/dm-6 on / type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
tmpfs on /dev type tmpfs (rw,seclabel,nosuid,relatime,size=3827176k,nr_inodes=956794,mode=755)
devpts on /dev/pts type devpts (rw,seclabel,relatime,mode=600,ptmxmode=000)
proc on /proc type proc (rw,relatime,gid=3009,hidepid=2)
sysfs on /sys type sysfs (rw,seclabel,relatime)
selinuxfs on /sys/fs/selinux type selinuxfs (rw,relatime)
tmpfs on /mnt type tmpfs (rw,seclabel,nosuid,nodev,noexec,relatime,size=3827176k,nr_inodes=956794,mode=755,gid=1000)
tmpfs on /apex type tmpfs (rw,seclabel,nosuid,nodev,noexec,relatime,size=3827176k,nr_inodes=956794,mode=755)
/dev/block/dm-5 on /patch_hw type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/sdd66 on /metadata type ext4 (rw,seclabel,nosuid,nodev,noatime,discard,data=ordered)
/dev/block/dm-7 on /cust type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /hw_product type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-9 on /odm type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-10 on /preas type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-11 on /preload type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-12 on /vendor type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-13 on /vendor/modem/modem_driver type ext4 (ro,seclabel,relatime,data=ordered)
/dev/block/dm-14 on /vendor/preavs type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-15 on /version type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
none on /dev/blkio type cgroup (rw,nosuid,nodev,noexec,relatime,blkio)
none on /dev/cg2_bpf type cgroup2 (rw,nosuid,nodev,noexec,relatime)
none on /dev/cpuctl type cgroup (rw,nosuid,nodev,noexec,relatime,cpu)
none on /acct type cgroup (rw,nosuid,nodev,noexec,relatime,cpuacct)
none on /dev/cpuset type cgroup (rw,nosuid,nodev,noexec,relatime,cpuset,noprefix,release_agent=/sbin/cpuset_release_agent)
none on /dev/memcg type cgroup (rw,nosuid,nodev,noexec,relatime,memory)
none on /dev/stune type cgroup (rw,nosuid,nodev,noexec,relatime,schedtune)
debugfs on /sys/kernel/debug type debugfs (rw,seclabel,relatime)
none on /config type configfs (rw,nosuid,nodev,noexec,relatime)
bpf on /sys/fs/bpf type bpf (rw,nosuid,nodev,noexec,relatime)
pstore on /sys/fs/pstore type pstore (rw,seclabel,nosuid,nodev,noexec,relatime)
none on /dev/iolimit type cgroup (rw,relatime,iolimit)
overlay on /system/lib type overlay (ro,seclabel,relatime,lowerdir=/patch_hw/overlay/system/lib:/system/lib)
overlay on /system/lib64 type overlay (ro,seclabel,relatime,lowerdir=/patch_hw/overlay/system/lib64:/system/lib64)
none on /mnt/update_engine type tmpfs (rw,seclabel,nosuid,nodev,relatime,size=3827176k,nr_inodes=956794,mode=700)
none on /dev/workingset type cgroup (rw,nosuid,nodev,noexec,relatime,workingset)
adb on /dev/usb-ffs/adb type functionfs (rw,relatime)
hdb on /dev/usb-ffs/hdb type functionfs (rw,relatime)
none on /dev/frz type cgroup (rw,relatime,freezer)
/dev/block/sdd7 on /sec_storage type ext4 (rw,context=u:object_r:teecd_data_file:s0,nosuid,nodev,noatime,discard,nodelalloc,data=journal)
tracefs on /sys/kernel/debug/tracing type tracefs (rw,seclabel,relatime)
/dev/block/sdd18 on /splash2 type ext4 (rw,context=u:object_r:splash2_data_file:s0,nosuid,nodev,noatime,data=ordered)
/dev/block/sdd72 on /data type f2fs (rw,seclabel,nosuid,nodev,noatime,background_gc=on,discard,no_heap,user_xattr,inline_xattr,acl,inline_data,inline_dentry,extent_cache,mode=adaptive,inline_encrypt,sdp_encrypt,active_logs=6,alloc_mode=default,fsync_mode=posix)
/dev/block/sdd23 on /cache type ext4 (rw,seclabel,nosuid,nodev,noatime,data=ordered)
overlay on /system/product/priv-app type overlay (ro,seclabel,relatime,lowerdir=/preas/priv-app:/system/product/priv-app)
overlay on /system/product/app type overlay (ro,seclabel,relatime,lowerdir=/preas/app:/system/product/app)
overlay on /system/product/etc/permissions type overlay (ro,seclabel,relatime,lowerdir=/preas/china/permissions:/system/product/etc/permissions)
/dev/block/sdd3 on /mnt/modem/modem_secure type ext4 (rw,context=u:object_r:modem_secure_file:s0,noatime,noauto_da_alloc,data=ordered)
/dev/block/sdd51 on /vendor/modem/modem_fw type ext4 (ro,context=u:object_r:modem_fw_file:s0,relatime,data=ordered)
/dev/block/sdd10 on /mnt/modem/mnvm2:0 type ext4 (rw,context=u:object_r:modem_nv_file:s0,nosuid,nodev,noatime,noauto_da_alloc,data=ordered)
tmpfs on /storage type tmpfs (rw,seclabel,nosuid,nodev,noexec,relatime,size=3827176k,nr_inodes=956794,mode=755,gid=1000)/dev/block/loop2 on /apex/com.android.apex.cts.shim@1 type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop2 on /apex/com.android.apex.cts.shim type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop3 on /apex/com.android.conscrypt@292103000 type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop3 on /apex/com.android.conscrypt type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop4 on /apex/com.android.media@292103016 type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop4 on /apex/com.android.media type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop5 on /apex/com.android.media.swcodec@292103012 type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop5 on /apex/com.android.media.swcodec type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop6 on /apex/com.android.resolv@292103001 type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop6 on /apex/com.android.resolv type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop7 on /apex/com.android.runtime@1 type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop7 on /apex/com.android.runtime type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop8 on /apex/com.android.tzdata@292103002 type ext4 (ro,dirsync,seclabel,nodev,noatime)
/dev/block/loop8 on /apex/com.android.tzdata type ext4 (ro,dirsync,seclabel,nodev,noatime)
none on /sys/fs/cgroup type tmpfs (rw,seclabel,relatime,size=3827176k,nr_inodes=956794,mode=750,gid=1000)
none on /sys/fs/cgroup/pids type cgroup (rw,relatime,pids)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/translation.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/voicekit.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/dm-ondeviceai.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-facecluster-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-facecompare-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-videomulti-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-videosemantic-common-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-txtimagesr-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/compatible-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-screenshotocr-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-headpose-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-segsemantic-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-tableocr-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/asr.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/nlu-full.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/tts.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-labelobjectdetect-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-portraitseg-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/computecapability-common.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-videoanalysis-common-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-faceparsing-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-labeldetect-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-focusocr-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-scene-common-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-multiobjectdetect-cpu-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-sisr-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-facedetect-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-barcode-common-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-carddetect-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-aestheticsfull-cpu-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-docconverter-common-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-facerating-cpu-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-faceattribute-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-facelandmark-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-clothing-orlando-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-docrefine-common-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-8 on /data/app/com.huawei.hiai-N_iI4NIgGtBfIypkf94yJw==/visionplugin-tracking-common-china-release.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-6 on /data/app/com.huawei.systemmanager-d1_lLcBuvKjGe4gAL6voYA==/AiSecurityPlugin.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-6 on /data/app/com.huawei.systemmanager-d1_lLcBuvKjGe4gAL6voYA==/AntimalPlugin.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-6 on /data/app/com.huawei.systemmanager-d1_lLcBuvKjGe4gAL6voYA==/WlanSecurePlugin.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-6 on /data/app/com.huawei.behaviorauth-qn46_LzogY1uYUaAKOhlnA==/HwBehaviorAuth.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-6 on /data/app/com.android.settings-uITFrNjy4jz1Gl0p_aRLBQ==/Resolution.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/dev/block/dm-6 on /data/app/com.android.settings-uITFrNjy4jz1Gl0p_aRLBQ==/SettingsTheme.apk type erofs (ro,seclabel,relatime,user_xattr,lz4asm)
/data/media on /mnt/runtime/default/emulated type sdcardfs (rw,nosuid,nodev,noexec,noatime,fsuid=1023,fsgid=1023,gid=1015,multiuser,mask=6,derive_gid,default_normal,reserved=20MB,unshared_obb)
/data/media on /storage/emulated type sdcardfs (rw,nosuid,nodev,noexec,noatime,fsuid=1023,fsgid=1023,gid=1015,multiuser,mask=6,derive_gid,default_normal,reserved=20MB,unshared_obb)
/data/media on /mnt/runtime/read/emulated type sdcardfs (rw,nosuid,nodev,noexec,noatime,fsuid=1023,fsgid=1023,gid=9997,multiuser,mask=23,derive_gid,default_normal,reserved=20MB,unshared_obb)
/data/media on /mnt/runtime/write/emulated type sdcardfs (rw,nosuid,nodev,noexec,noatime,fsuid=1023,fsgid=1023,gid=9997,multiuser,mask=7,derive_gid,default_normal,reserved=20MB,unshared_obb)
/data/media on /mnt/runtime/full/emulated type sdcardfs (rw,nosuid,nodev,noexec,noatime,fsuid=1023,fsgid=1023,gid=9997,multiuser,mask=7,derive_gid,default_normal,reserved=20MB,unshared_obb)
/data/misc_ce/0/kdfs/storage on /mnt/mdfs/.hmdfs type hmdfs (rw,relatime,sensitive,merge_enable,ra_pages=128,account=10143583112313917499,recv_uid=1023,cache_dir=/data/misc_ce/0/kdfs/cache/16448759908547494974,real_dst=/mnt/mdfs/.hmdfs,offline_stash,dentry_cache)
/data/misc_ce/0/kdfs/storage on /mnt/mdfs/account_trust type hmdfs (rw,relatime,sensitive,merge_enable,ra_pages=128,account=10143583112313917499,recv_uid=1023,cache_dir=/data/misc_ce/0/kdfs/cache/16448759908547494974,real_dst=/mnt/mdfs/.hmdfs,offline_stash,dentry_cache)
/data/media/0 on /mnt/mdfs/sdcard type hmdfs (rw,relatime,insensitive,merge_disable,ra_pages=128,account=10143583112313917499,recv_uid=1023,cache_dir=/data/misc_ce/0/kdfs/cache/16448759910518911873,real_dst=/mnt/mdfs/sdcard,offline_stash,dentry_cache)
/mnt/media_rw on /mnt/mdfs/external_storage type hmdfs (rw,relatime,insensitive,merge_disable,ra_pages=128,account=10143583112313917499,recv_uid=1023,cache_dir=/data/misc_ce/0/kdfs/cache/14998924782874330279,real_dst=/mnt/mdfs/external_storage,no_offline_stash,dentry_cache,external_storage)
/data/misc_ce/0/kdfs/storage on /mnt/mdfs/10143583112313917499 type hmdfs (rw,relatime,sensitive,merge_enable,ra_pages=128,account=10143583112313917499,recv_uid=1023,cache_dir=/data/misc_ce/0/kdfs/cache/16448759908547494974,real_dst=/mnt/mdfs/.hmdfs,offline_stash,dentry_cache)
/dev/fuse on /mnt/appfuse/10008_2 type fuse (rw,fscontext=u:object_r:app_fusefs:s0,context=u:object_r:app_fuse_file:s0,nosuid,nodev,noexec,noatime,user_id=0,group_id=0,default_permissions,allow_other)
mdfs on /mnt/mdfs/groups type fuse (rw,nosuid,nodev,relatime,user_id=0,group_id=0,allow_other)

我們對其進行整理,得到如下參考表格:

目錄/裝置 掛載點 檔案系統 鍵值 備註
/dev/block/dm-6 / erofs ro,seclabel,relatime,user_xattr,lz4asm 系統盤採用華為自研開源EROFS檔案系統 面向終端場景 減小了元資料 隨機讀取效能有明顯提高
tmpfs /storage tmpfs rw,seclabel,nosuid,nodev,noexec,relatime,size=3827176k,nr_inodes=956794,mode=755,gid=1000 內部儲存目錄 採用tmpfs臨時檔案系統 對應於/tmp或swap 在記憶體利用上有很大價值
/dev/block/sdd72 /data f2fs rw,seclabel,nosuid,nodev,noatime,background_gc=on,discard,no_heap,user_xattr,inline_xattr,acl,inline_data,inline_dentry,extent_cache,mode=adaptive,inline_encrypt,sdp_encrypt,active_logs=6,alloc_mode=default,fsync_mode=posix 應用核心資料目錄 採用18個月不卡的F2FS格式 減輕了儲存器內部處理負擔
/dev/block/sdd66 /metadata ext4 rw,seclabel,nosuid,nodev,noatime,discard,data=ordered 各種元資料及快取目錄 採用常規第四代擴充套件格式 門檻相對較低 優化後可顯著提高執行效能
/dev/block/sdd7 /sec_storage ext4 rw,context=u:object_r:teecd_data_file:s0,nosuid,nodev,noatime,discard,nodelalloc,data=journal
/dev/block/sdd23 /cache ext4 rw,seclabel,nosuid,nodev,noatime,data=ordered
/data/media/0 /mnt/mdfs/sdcard hmdfs rw,relatime,insensitive,merge_disable,ra_pages=128,account=10143583112313917499,recv_uid=1023,cache_dir=/data/misc_ce/0/kdfs/cache/16448759910518911873,real_dst=/mnt/mdfs/sdcard,offline_stash,dentry_cache 資料媒體存取目錄 採用鴻蒙全自研跨裝置HMDFS 支援多裝置資料融合 4倍Samba效能
/mnt/media_rw /mnt/mdfs/external_storage hmdfs rw,relatime,insensitive,merge_disable,ra_pages=128,account=10143583112313917499,recv_uid=1023,cache_dir=/data/misc_ce/0/kdfs/cache/14998924782874330279,real_dst=/mnt/mdfs/external_storage,no_offline_stash,dentry_cache,external_storage
/data/media /mnt/runtime/default/emulated sdcardfs rw,nosuid,nodev,noexec,noatime,fsuid=1023,fsgid=1023,gid=1015,multiuser,mask=6,derive_gid,default_normal,reserved=20MB,unshared_obb 資料媒體執行時存取目錄 sdcardfs管理被作為外部儲存的/sdcard目錄 若對其進行優化 外存效能的提高極其有助於系統整體效能的提高

LZ4 固定大小輸出演算法

塊格式

  • LZ4 是 LZ77 型壓縮器,具有固定的、面向位元組的編碼沒有熵編碼器後端,也沒有成幀層。假設後者由系統的其他部分處理,這種設計有利於簡易及速度,有助於以後進行優化、緊湊及增強功能。

壓縮塊格式

  • LZ4 壓縮塊由序列組成。序列是一組文字(未壓縮的位元組),後跟一個匹配副本。每個序列都從一個標記開始。標記是一個位元組值,分為兩個 4 位欄位。因此,每個欄位的範圍從 0 到 15。第一個欄位使用了標記的 4 個高位元位,它提供了要遵循的文字的長度。
  • 如果欄位值為 0,則沒有文字。如果是15,那麼需要多加一些位元組來表示全長,然後每個額外的位元組代表一個從 0 到 255 的值,該值被新增到前一個值以產生總長度。當位元組值為 255 時,必須讀取並新增另一個位元組,以此類推。標記後面可以有任意數量的值為“255”的位元組,無大小限制:
示例 1:文字長度 48 表示為:
	15:4 位高欄位的值
	33 : (=48-15) 剩餘長度達到 48

示例 2:文字長度 280 表示為:
	15:4 位高欄位的值
	255 : 後面的位元組最大,因為 280-15 >= 255
	10 : (=280 - 15 - 255) ) 剩餘長度達到 280

示例 3:文字長度 15 表示為:
	15:4 位高欄位的值
	0 : (=15-15) 必須輸出零
  • 在標記和可選長度位元組之後,是文字本身。它們的數量與之前解碼的一樣多(字面量長度),字面量可能為零。文字之後是匹配複製操作。它從偏移量開始,是一個 2 位元組的值,採用小端格式(第一個位元組是“低”位元組,第二個是“高”位元組),偏移量表示要複製的匹配的位置。例如,1 表示“當前位置 - 1 個位元組”。最大偏移值為 6553565536 及以上無法編碼。0 是無效的偏移值。這種值的存在表示無效*(損壞)*塊。
  • 然後可以提取匹配長度。為此,我們使用第二個標記欄位,即低 4 位。顯然,這個值的範圍是 0 到 15。但是在這裡,0 意味著複製操作是最小的匹配的最小長度稱為 minmatch,為 4。因此,0 值表示 4 個位元組,15 值表示 19+ 個位元組。與文字長度類似,在達到可能的最高值 (15) 時,必須讀取額外的位元組,一次一個,值範圍從 0 到 255。它們被新增到總數中以提供最終匹配長度。 255 值意味著還有另一個位元組要讀取和新增。可以存在的可選“255”位元組的數量沒有限制。(注意:這指向大約 250 的最大可實現壓縮比)。
  • 解碼匹配長度到達當前序列的末尾。下一個位元組是另一個序列的開始。但在移動到下一個序列之前,這時需要使用解碼的匹配位置和長度了。解碼器將 matchlength 位元組從匹配位置複製到當前位置
  • 在某些情況下,matchlength 可以大於 offset。因此,由於 match_pos + matchlength > current_pos,稍後要複製的位元組尚未解碼,這稱為**“重疊匹配”**,需要特別小心處理。<u>常見的情況是偏移量為 1,這意味著最後一個位元組重複 matchlength 次。</u>

區塊限制終止

  • 終止 LZ4 塊需要特定的限制:
  1. 最後一個序列只包含文字,塊在他們之後結束
  2. 輸入的最後 5 個位元組始終是文字。因此,最後一個序列至少包含 5 個位元組
    • 特別的,如果輸入小於 5 個位元組,則只有一個序列,它包含整個輸入作為文字。空輸入可以用零位元組表示,解釋為沒有文字和匹配的最終標記
  3. 最後一個匹配必須在塊結束前至少 12 個位元組開始,緊隨其後的是最後一個序列,它只包含文字
    • 需要注意,不能壓縮 < 13 位元組的獨立塊,因為匹配必須複製“某些東西”,因此至少需要一個前位元組
    • 但是,當一個塊可以引用另一個塊的資料時,它可以立即以匹配方式而非文字開始,因此可以壓縮正好為 12 個位元組的塊

當某一個塊不符合以上這些終止條件時,允許一致的解碼器將會視該塊為錯誤從而拒絕; 這些條件是為了確保與各種歷史解碼器之間的相容性,解碼器在面向速度的設計中依賴它們。

參考文獻

[1] Deorowicz S . Universal Lossless Data Compression Algorithms[J]. Philosophy Dissertation Thesis, 2003. [2] Burrows M , Wheeler D J . A Block-Sorting Lossless Data Compression Algorithm[J]. technical report digital src research report, 1995. [3] Gao X , Dong M , Miao X , et al. EROFS: a compression-friendly readonly file system for resource-scarce devices. 2019. [4] Ni G . Research on BWT and Classical Compression Algorithms[J]. Computer & Digital Engineering, 2010. [5] Farruggia A , Ferragina P , Frangioni A , et al. Bicriteria data compression[J]. Society for Industrial and Applied Mathematics, 2013. [6] Alakuijala J , Farruggia A , Ferragina P , et al. Brotli: A General-Purpose Data Compressor[J]. ACM Transactions on Information Systems, 2018, 37(1):1-30. [7] Overview - The Hitchhiker's Guide to Compression (go-compression.github.io) [8] Wavelet Tutorial - Part 1 [9] Wavlet Tutorial - Part 2 [10] Wavelet Tutorial - Part 3