高克承 徐 桓 劉 巖 劉 洋 張 曦*

大數(shù)據(jù)時代，信息產(chǎn)出量成指數(shù)型爆炸增長，不斷增長的數(shù)據(jù)量對于信息的存儲和傳輸造成極大困擾，深刻的影響著多個行業(yè)和領(lǐng)域。醫(yī)療衛(wèi)生方面，隨著患者的不斷增加及醫(yī)患關(guān)系的交流深入，與之相關(guān)的醫(yī)療文本的數(shù)字化勢在必行，由此引發(fā)一系列重要問題：一方面，醫(yī)院常年累月的運轉(zhuǎn)會產(chǎn)生龐大的醫(yī)療文本數(shù)據(jù)，應(yīng)如何存儲如此龐大的數(shù)據(jù)量；另一方面，隨著遠程醫(yī)療和網(wǎng)絡(luò)診斷的出現(xiàn)及應(yīng)用，需要存儲和傳輸?shù)尼t(yī)療文本信息量與日俱增，以上信息又該以何種方式存在。

當前，醫(yī)療文本信息的存儲和傳輸已逐漸成為國內(nèi)多數(shù)醫(yī)院亟需解決的難題之一，迫切需要一種適合于醫(yī)療衛(wèi)生領(lǐng)域的文本壓縮算法改善此難題。調(diào)研并閱讀文本數(shù)據(jù)壓縮類文獻，闡述各類經(jīng)典文本壓縮算法的簡單原理，發(fā)掘近年來文本數(shù)據(jù)壓縮算法的新發(fā)展，嘗試分析和探索適用于當前醫(yī)療文本數(shù)據(jù)的壓縮算法。

1 經(jīng)典文本壓縮算法

1948年，信息論之父香農(nóng)提出了“香農(nóng)編碼”，自此數(shù)據(jù)壓縮方法層出不窮，各種變體衍生而出[1]。立足于文本數(shù)據(jù)壓縮問題，依次介紹三種經(jīng)典的無損壓縮算法，即Huffman編碼、串表壓縮算法(Lempel-Ziv and Welch，LZW)編碼和基于部分匹配預(yù)測(prediction by partial matching，PPM)的壓縮算法，并分析各算法的優(yōu)缺點。

1.1 基于Huffman編碼的文本壓縮算法

Huffman編碼是由Huffman DA于1952年提出的一種基于統(tǒng)計概率模型的經(jīng)典壓縮算法[2]。其運行機制類似于摩爾斯(morse)電碼機，每個字符的編碼只有幾個比特序列，即利用初始信號出現(xiàn)的概率進行編碼，常出現(xiàn)的信號編碼較短，不常出現(xiàn)的信號編碼則較長。

Huffman編碼基本上是一個表示為二叉樹的前綴碼(prefix code)。二叉樹的左分支標記為0，右分支標記為1，從根到葉的每個路徑上形成的比特序列是用于匹配對應(yīng)字符的前綴碼，如此形成的二叉樹稱為Huffman樹[3-4]。算法如下：①計算所有信號的頻次并排序得到集合；②取最小兩個頻次的信號組成左右Huffman樹放入原來的集合中；③重復(fù)②中的內(nèi)容，直到集合只剩一個元素時結(jié)束；④根據(jù)樹枝的左邊為0，右邊為1的規(guī)則進行編碼，結(jié)束。

文本壓縮算法是一種最佳編碼方式，碼不唯一，平均碼長相同，但不影響效率和壓縮性能，但也具有以下缺點：①碼長參差不齊，存在輸入和輸出速率匹配的問題，可設(shè)置緩沖器；②誤碼存在連續(xù)傳播；③編碼效率和壓縮比率受輸入信號影響；④必須與其他壓縮算法相結(jié)合來提高其過低的壓縮比率。

1.2 基于LZW編碼的文本壓縮算法

1977年，以色列的Lempel和Ziv共同提出了查找冗余字符及用較短的符號標記代替冗余字符的技術(shù)，簡稱LZ壓縮技術(shù)。1985年，美國的Welch將LZ壓縮技術(shù)從概念發(fā)展到使用階段，簡稱LZW壓縮技術(shù)，廣泛應(yīng)用于文本壓縮領(lǐng)域。

LZW編碼又稱“串表壓縮算法”。是一種對字符串進行編碼的同時生成特定字符串及與之對應(yīng)的索引字符串表的無損壓縮算法[5]。LZW壓縮算法流程見圖1。

圖1 LZW壓縮算法流程圖

LZW壓縮使用字典庫查找方案，其讀入待壓縮的數(shù)據(jù)并與一個字典庫(庫開始是空的)中的字符串作對比，如有匹配的字符串，則輸出該字符串數(shù)據(jù)在字典庫中的位置索引，否則將該字符串插入字典中，該算法特點如下：①有效利用了字符出現(xiàn)的冗余度，字典自適應(yīng)生成，位置冗余度利用不足；②對可預(yù)測性不大或在數(shù)據(jù)流中反復(fù)出現(xiàn)的字符處理效果較好；③可用于圖像壓縮，實現(xiàn)迅速壓縮和解壓縮；④可處理大量數(shù)據(jù)的同時對計算機硬件性能要求不高。

1.3 基于PPM的文本壓縮算法

1.3.1 PPM文本壓縮算法

PPM算法是一種基于上下文的統(tǒng)計建模技術(shù)，采用有限數(shù)量并且已知字符的標準馬爾可夫模型(Markov model)進行近似預(yù)測[6-8]。通過一系列不同順序的上下文模型預(yù)測下一個即將出現(xiàn)的字符，一個新的字符出現(xiàn)在上下文中時，該字符將會自動獲取一個轉(zhuǎn)義概率，根據(jù)轉(zhuǎn)義方法的不同出現(xiàn)許多PPM的變體[9-11]。

PPM模型簡要論述如下：令A(yù)是由|A|>2組成的離散字符表，且D為該模型的最大階數(shù)，其中d(d≤D)為當前該模型的編碼階數(shù)。即將出現(xiàn)的字符xn+1=φ，φ∈A的概率取決于當前的上下文Sd=xn，…，xn-d+1。字符φ在上下文Sd中出現(xiàn)的概率為：

式中Cd(φ)表示字符φ在上下文Sd中出現(xiàn)的次數(shù)，Td=∑Cd(φ)表示上下文Sd被訪問的總次數(shù)。字符φ在上下文Sd中出現(xiàn)的轉(zhuǎn)義概率為：

式中D是該模型的最大階數(shù)，d(d≤D)是當前該模型的編碼階數(shù)PPM建模技術(shù)與算數(shù)編碼相結(jié)合的編碼方式具有高壓縮比率，但過于占用內(nèi)存且執(zhí)行速度較慢。

1.3.2 PPMO中文文本壓縮算法

PPMO是一種適合于中文文本的壓縮算法，由Wu和Teahan提出[10]。編碼過程分為兩部分：順序流和符號流[12]。順序流為每個編碼符號輸出一定的編碼順序；符號流是基于特定的上下文順序輸出編碼符號本身。簡要闡述該算法的編碼過程。

(1)若一個符號φ在一個上下文模型Sd中已出現(xiàn)過，則對順序流中當前最大的d進行編碼，而后是符號本身的符號流將采用以下公式進行編碼：

式中Cd(φ)表示字符φ在上下文Sd中出現(xiàn)的次數(shù)，T表示上下文Sd被訪問的總次數(shù)。

(2)若一個符號φ并未在上下文模型Sd中找到，將會倒退回上一級尋找，直到按照需要返回默認的-1序列為止。為確保一個符號總能在-1序列里面找到，在字母表中給每一個符號分配一個數(shù)字標志。選擇用于編碼符號的模型后，首先對模型順序進行編碼，而后再使用該模型對符號進行編碼。

由于順序流具有較小的字母表尺寸和重復(fù)性，使其成為一種高度可預(yù)測的編碼方式。如若一個上下文模型的符號流的最大編碼順序是2階，對于順序流而言，其可能的情況僅有4種，即{-1，0，1，2}。以下為中文版《圣經(jīng)》的順序流樣例：

1,2,0,1,0,1,2,2,0,0,1,0,1,2,1,0,0,0,0,0,0,0,1,2,0,0,0,1,1,0,1,2,2,-1,0,1,0,0,0,1,2,2,0,1,-1,-1,0,1,0,0,1,0,-1,0,-1,0,1,2,0,1,2,2,0,1,2,1,0,-1,0,-1,0,1,0,0,-1,0,0,1,0,0,1,0,1,2,2,2,2,2,2,2,2,2,2,2,0,1,2,0,1,0，可將順序d視為要編碼的一個單獨的實體，接著使用傳統(tǒng)的PPM編碼方式對該順序進行編碼。則順序d的條件概率為：

式中D*表示順序流的最大編碼順序；d*≤D表示當前的編碼順序；表示當前順序流編碼的上下文，符號φ的總編碼概率為：

式中PO(d)是順序d的條件概率，Ps(φ)是符號φ本身的符號流。

Wu及Teahan[13]的實驗顯示，小文件的壓縮率為7.350 bpCc，大文件的壓縮率為5.938 bpCc，比GNU zip及bzip2壓縮軟件壓縮率高，該算法優(yōu)點體現(xiàn)在轉(zhuǎn)義頻率低和執(zhí)行速度快，缺點為每個字符都需要兩步的編碼。

上述數(shù)種經(jīng)典壓縮算法是目前文本壓縮的主流算法，其對于小文件可做到無損且快速壓縮。由于當前醫(yī)療文本數(shù)據(jù)的海量化，上述算法逐漸展現(xiàn)疲態(tài)，面對大量醫(yī)療文本數(shù)據(jù)，會出現(xiàn)壓縮速度慢、耗時長及準確率下降的缺點。因此，為滿足目前醫(yī)療文本壓縮需求，探索可壓縮海量文件的新型壓縮算法勢在必行。

2 文本壓縮算法新進展

由于社會數(shù)據(jù)量的爆炸增長及存儲的海量化，一些新型壓縮算法應(yīng)運而生。簡要闡述基于壓縮感知的文本壓縮技術(shù)，并對機器學(xué)習(xí)和深度學(xué)習(xí)用于文本壓縮的可能性進行討論。

2.1 基于壓縮感知的海量文本壓縮

壓縮感知(compressed sensiong，CS)是一種新興的壓縮方法，常用于圖像壓縮，近年出現(xiàn)了壓縮海量文本的方法[14-16]。壓縮感知理論指出：只要信號是可壓縮的或在某個變換域是稀疏的，便可用一個與變換基不相關(guān)的觀測矩陣將變換所得高維信號投影到一個低維空間上，然后通過求解一個優(yōu)化問題即可從這些少量的投影中以高概率重構(gòu)出原信號，可證明該投影包含了重構(gòu)信號的足夠信息[17]。在該理論框架下，采樣速率不再取決于信號的帶寬，而在很大程度上取決于兩個基本準則：稀疏性和非相關(guān)性，或稀疏性和等約束性。

2.2 基于壓縮感知理論的海量文本壓縮

研究的壓縮對象主要是社交媒體平臺，如推特(Twitter)、臉書(Facebook)和亞馬遜(Amazon)的用戶生成內(nèi)容，旨在解決兩個問題：①應(yīng)如何管理和存儲數(shù)量巨大且不斷變化的文本數(shù)據(jù)流；②如何從文本數(shù)據(jù)流中獲得高質(zhì)量的文本。

文本流如社交媒體等用戶生成的文本流有兩個壓縮過程：①根據(jù)指定的多樣性參數(shù)為每個文本段生成高質(zhì)量的文本集合；②降維壓縮上述集合。簡要闡述上述兩個過程：

(1)高質(zhì)量文本集合生成。一般而言，一個句子或一篇文章的質(zhì)量通常取決于其所包含的術(shù)語的重要性，這是已廣泛應(yīng)用于在線趨勢主題檢測和高質(zhì)量微博提取的基本原理[18-19]。將一個術(shù)語的重要性定義為其在一個片段中的出現(xiàn)頻率，文本的質(zhì)量定義為其所包含的所有術(shù)語的熵。因此，對一系列的文本段{抽象為文本術(shù)語矩陣X1，X2，…，Xl，…[∈R(n·Pl)(l=1，2，…，L，…)]}，第l段第i個文本的質(zhì)量由熵E(i，l)所決定：

基于文本熵，通過從文本段中選擇次優(yōu)文本集合來生成高質(zhì)量文本集合，以使其對應(yīng)于選定的分集參數(shù)值(以ω表示)。令文本段Xl按照熵的降序排列，由一個空白的文本集合Xl(ω)開始從Xl中選擇第一個文本，接著迭代的從Xl中添加直到在Xl(ω)中的熵的范數(shù)小于給定的ω。最后，生成一個高質(zhì)量的文本段落Xl(ω)(這些文本的熵值之和大約等于分集參數(shù)ω)。

(2)線性測量的文本壓縮。在一般的CS框架中，并不是獲取信號x∈RM×N的N個樣本，而是通常將M個隨機測量值稱為以CS編碼獲取的隨機投影，其中M＜N。由欠定的線性方程組表示：

式中y∈RM×1是已知的測量向量；?∈RM×N是隨機測量矩陣。

該算法框架下，每個高質(zhì)量文本段Xl(ω)(l=1，2，…，L，…)以壓縮感知理論為基礎(chǔ)進行壓縮。對于給定的一個線性測量矩陣?，通過以下公式獲得Xl(ω)中的樣本矩陣Yl(ω)∈Rm×Pl(l=1，2，…，L，…)：

采用一種基本的循環(huán)編碼方式，將壓縮成一系列樣本片段Y1(ω)，Y2(ω)，…，Yl(ω)，其中Yl(ω)遠遠小于Xl(ω)。此外，每個段的單詞表被保存從而進行后續(xù)的解壓縮操作。與原始文本流相比，此樣本段的存儲所需消耗的內(nèi)存空間要小得多且更便于傳輸和檢索。

Gaussian隨機矩陣的實體滿足一個獨立且同一的高斯分布，均值為0，方差為(i.e.，?ij～N(0，))，滿足該條件的矩陣被用于測量線性矩陣?。已經(jīng)證明，只有在滿足m≥cK log(+1)，c>0的條件下才能從樣本Y中恢復(fù)出信號X。該壓縮方法壓縮率高、速度快且解壓縮誤差低，缺點為算法是有損壓縮。目前，已證明該算法可用于壓縮社區(qū)聊天，經(jīng)過改善將有可能成為一種適合于海量醫(yī)療文本壓縮的新型算法。

2.3 機器學(xué)習(xí)和深度學(xué)習(xí)用于文本壓縮的可能性

機器學(xué)習(xí)和深度學(xué)習(xí)用于文本壓縮較為新穎，目前可能存在一些不太成熟的方法，但關(guān)于機器學(xué)習(xí)用于醫(yī)學(xué)圖像的高密度壓縮的方法已出現(xiàn)[20]。其基本思路如下：①構(gòu)建一個可識別圖像中關(guān)于人體器官或組織中的關(guān)鍵元素的智能學(xué)習(xí)模型；②提取出上述關(guān)鍵元素并存儲；③填充圖片僅剩背景圖，接著將其壓縮存儲。如上述將特征單獨存儲，同時將不重要的背景圖層壓縮后，得到的即為壓縮后的醫(yī)學(xué)圖片。針對于醫(yī)療文本，探索是否可模仿圖像壓縮方法，首先構(gòu)建一個智能學(xué)習(xí)模型，該模型可提出醫(yī)療文本中的關(guān)鍵元素，同時篩選出相關(guān)主要特征，最后將主要特征進行存儲，得到壓縮后的文件，類似主成分分析法(principal components analysis，PCA)，解壓縮時根據(jù)提取的主要特征進行還原[21]。如結(jié)合PCA和機器學(xué)習(xí)，有可能建立一種醫(yī)療文本壓縮算法。

目前關(guān)于深度學(xué)習(xí)的壓縮主要集中在視頻及醫(yī)學(xué)圖像的再壓縮[22]。方法是先訓(xùn)練出一個準確的卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural networks，CNN)標準數(shù)據(jù)集，再對視頻進行切割分類，最后進行壓縮。由于當前醫(yī)院的醫(yī)療文本信息量足夠多，可訓(xùn)練出類如前文所述的CNN數(shù)據(jù)集。可借鑒醫(yī)學(xué)圖像再壓縮方法，首先訓(xùn)練一個CNN數(shù)據(jù)集，再對醫(yī)療文本進行有效的切割分類，最后進行壓縮。

3 展望

當前主流的醫(yī)療文本壓縮算法仍為上述經(jīng)典的壓縮算法或其組合，存在壓縮速度慢，壓縮效率低等問題。由于機器學(xué)習(xí)面對海量數(shù)據(jù)處理具有極大的優(yōu)越性，并且隨著醫(yī)療文本數(shù)據(jù)的增多，為提高壓縮速度和壓縮效率，未來文本壓縮算法將會以結(jié)合機器學(xué)習(xí)的算法為主。