面向醫(yī)療文本數(shù)據(jù)壓縮的主流算法及發(fā)展趨勢(shì)*

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

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

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

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

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

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

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

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

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

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

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

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

圖1 LZW壓縮算法流程圖

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

1.3 基于PPM的文本壓縮算法

1.3.1 PPM文本壓縮算法

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

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

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

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

1.3.2 PPMO中文文本壓縮算法

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

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

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

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

由于順序流具有較小的字母表尺寸和重復(fù)性，使其成為一種高度可預(yù)測(cè)的編碼方式。如若一個(gè)上下文模型的符號(hào)流的最大編碼順序是2階，對(duì)于順序流而言，其可能的情況僅有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視為要編碼的一個(gè)單獨(dú)的實(shí)體，接著使用傳統(tǒng)的PPM編碼方式對(duì)該順序進(jìn)行編碼。則順序d的條件概率為：

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

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

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

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

2 文本壓縮算法新進(jìn)展

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

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

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

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

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

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

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

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

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

式中y∈RM×1是已知的測(cè)量向量；?∈RM×N是隨機(jī)測(cè)量矩陣。

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

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

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

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

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

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

3 展望

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