王國政，朱光彥

(中州大學(xué)信息工程學(xué)，鄭州 450044)

一、BWT算法簡介以及項目背景

云技術(shù)的普及使得越來越多的用戶數(shù)據(jù)從個人終端被轉(zhuǎn)移到了云端。而移動互聯(lián)網(wǎng)的廣泛應(yīng)用則在很大程度上成就了云端數(shù)據(jù)與個人用戶之間的橋梁。隨著移動終端平臺的發(fā)展，其軟硬件能力也得到了大幅度的提升。由此而來的云端數(shù)據(jù)本地化就成為了移動平臺應(yīng)用的新的發(fā)展方向之一。大量的云端數(shù)據(jù)的本地化涉及到數(shù)據(jù)的下載、上傳和移動平臺對離線數(shù)據(jù)的處理。雖然移動平臺有了不錯的硬件能力，但是其互聯(lián)網(wǎng)帶寬、硬件空間和內(nèi)存處理能力仍然存在著很大的局限性。而由此也對該平臺上有云端數(shù)據(jù)本地化需求的應(yīng)用程序的數(shù)據(jù)壓縮和處理能力提出了很高的要求。

Burrows-Wheeler Transform，也稱為BWT變換，就是一種被廣泛應(yīng)用于數(shù)據(jù)壓縮領(lǐng)域的系列算法。其高效的壓縮和搜索性能使它的使用領(lǐng)域非常廣泛。從一般文本壓縮到基于DNA串的高級壓縮和搜索操作，都能看到BWT技術(shù)的身影。雖然該技術(shù)在文本壓縮領(lǐng)域有著廣泛和深遠(yuǎn)的影響，其使用范圍卻受到了運行環(huán)境的限制。比如在移動平臺(手機、平板電腦)上，該方法對于平臺的運算能力和運行時內(nèi)存的需求就會顯得過于繁重。從另一個角度來講，雖然移動平臺在運行時內(nèi)存和處理速度方面提供具有高束縛性的環(huán)境，但也正是這種移動平臺對高效的數(shù)據(jù)壓縮類算法有著很大需求。而基于其驚人的壓縮比和在保持壓縮比的同時提供的高效數(shù)據(jù)搜索效率的性質(zhì)，BWT算法在移動平臺有著廣泛的需求和前景。這種平臺束縛性和平臺需求的矛盾，使得關(guān)于BWT算法是否合適被應(yīng)用在移動平臺之上，就成為了一個非常值得考量的問題。本論文以實際項目為背景，對此問題進行了深入探究。其軟件項目基礎(chǔ)是一個基于測驗的互聯(lián)網(wǎng)教育類網(wǎng)站“Tenclip”的手機移動平臺應(yīng)用(APP)實現(xiàn)。該網(wǎng)站對其APP處理大量離線的測驗數(shù)據(jù)有著很高的需求，因此產(chǎn)生的對基于文本的數(shù)據(jù)壓縮和搜索的需求，使其理所當(dāng)然的成為BWT算法實現(xiàn)的優(yōu)質(zhì)平臺。

二、BWT算法的項目應(yīng)用

在項目的硬件和軟件基礎(chǔ)上，BWT作為算法核心支撐著該項目主要功能的實現(xiàn)。BWT算法是現(xiàn)今最高效的壓縮算法之一，同時它也對高速的搜索功能有著強有力的支持。正如其英文名稱Burrows–Wheeler Transform(變換)所揭示的一樣，BWT壓縮算法最核心的概念就是對文本T進行的變換。舉例來說，如果T=BANANA$，則經(jīng)過BWT轉(zhuǎn)化后，T就變成了ANNB$AA。通過這種變化，在保證高效(時間復(fù)雜度和空間復(fù)雜度)的原文全文搜索的基礎(chǔ)上，可以進而對變化文本進行高效的壓縮。［1］

該移動端應(yīng)用APP的流程包括:用戶首先通過APP測試瀏覽窗口或者搜索窗口獲得需要的Quiz(小測試)。小測試包含單項選擇題、多項選擇題、填空題和簡答題。選定測試之后用戶可以直接點擊測試題目進入測試進行答題，在答題的過程當(dāng)中需要網(wǎng)絡(luò)連接，用戶回答完問題后提交自己的答案，APP通過網(wǎng)絡(luò)對用戶的答案進行評估、評分和評獎?；蛘哂脩艨梢赃x擇離線答題模式。APP則會下載用戶所選擇的測試，以供用戶進行離線答題。當(dāng)網(wǎng)絡(luò)連接恢復(fù)之后，用戶的評價體系就會自動完成。

對于每一個測試的數(shù)據(jù)結(jié)合，系統(tǒng)采用BWT算法生成其索引文件(Index Files)，這里應(yīng)用到的是“BWT生成算法”。因為所有通過網(wǎng)絡(luò)傳輸?shù)娇蛻舳说奈募家粔嚎s存儲，在此應(yīng)用的是“BWT壓縮算法”。而之后索引文件ID的獲得則用到“BWT搜索算法”。

離線數(shù)據(jù)以兩種形式存儲在本地。一種被稱為“Personal Download個人下載”(簡稱PD);另一種叫做“Personal Bank個人數(shù)據(jù)銀行”(簡稱PB)。PB中存儲的是網(wǎng)站所有Quiz的離線文本文檔，它是用戶在下載APP的時候預(yù)裝的網(wǎng)站當(dāng)時所有Quiz的快照。PD則包含用戶下載的所有的Quiz。他們兩者之間可能會有交集。從體積上講，PD遠(yuǎn)遠(yuǎn)小于PB。因為PB的大小一般會超過60M，基于它的BWT創(chuàng)建算法是無法在移動端進行的，所以該部分?jǐn)?shù)據(jù)被預(yù)裝在了APP之中。而PB的大小一般小于1M(在50K左右)，稍后的BWT算法分析中可以看到，即使當(dāng)PB大小上升到1.5M，普遍的Android移動端還是能勝任其BWT的各種算法過程處理的。

三、BWT算法在移動平臺的應(yīng)用瓶頸

BWT雖然能夠同時實現(xiàn)驚人的壓縮比和對搜索的高級支持，但是BWT生成算法則可能會很輕易的成為整個算法過程的瓶頸，主要包含以下三點原因:

1.現(xiàn)在普遍認(rèn)可的 BWT生成算法有兩種［2］。一種叫做 Forward Transform Algorithm(簡稱FT算法)。FT算法基于對原文本的旋轉(zhuǎn)變體(cyclic shifting)的全排列。另一種叫做Native Suffix Array Construction Algorithm(簡稱NSAC算法)。這種算法首先生成原文本的Suffix Array(后綴數(shù)組)，然后通過后綴數(shù)組生成BWT文本。NSAC算法的后綴數(shù)組又可以通過兩種算法生成:原生排序算法或者更復(fù)雜的線性排序算法。NSAC算法是比較常用的算法，但是其時間復(fù)雜度在最壞的情況下是O(n2)，效率過于低下。

2.要考慮的第二個因素是由于移動系統(tǒng)硬件或者移動操作系統(tǒng)(在這里是Android)導(dǎo)致的在APP在運行的時候的強制的內(nèi)存限制［3］(試驗中為24 M)。

3.第三個阻力是在系統(tǒng)實現(xiàn)的時候可能利用到的Java的本地排序算法。通過Java文檔可知，Java的本地排序算法，在一般的排序狀況下是能夠保證O(nlgn)的時間復(fù)雜度的。但是經(jīng)過系統(tǒng)的實踐證明，在具體實現(xiàn)中，尤其是當(dāng)排序標(biāo)準(zhǔn)不是一般性數(shù)字比大小而是自定義排序標(biāo)準(zhǔn)的時候，Java類庫提供的本地排序算法并不一定是最好的選擇，因為它在時間復(fù)雜度和空間復(fù)雜度方面都不能提供最佳的運行效率。

下面就通過對三種BWT生成算法的效率以及可以實現(xiàn)的優(yōu)化兩個角度討論解決以上三個困境的有效途徑。

四、問題分析和解決方案

最原始的創(chuàng)建某文本的BWT變體的方式是通過FT算法［4］。該算法的核心思想如表1所示，是對原文本的所有旋轉(zhuǎn)變體進行排序。

表1

其中表格(1)部分為T的所有旋轉(zhuǎn)變體，(2)即為按照字典序?qū)λ凶凅w的字符串進行的排序。而通過對(2)的最后一個字符的順序掃描，即可獲得T的BWT變體文本:ANNB$AA。

可以看到以上算法的空間復(fù)雜度為O(n2)。通過實現(xiàn)一個輔助數(shù)組緩存可以實現(xiàn)把空間復(fù)雜度降低到O(n)。時間復(fù)雜度方面，理論上O(nlgn)的時間復(fù)雜度效率是可以實現(xiàn)的，但是一旦我們轉(zhuǎn)化的文本文字來自于英文文本，其最壞時間復(fù)雜度O(n2)就變得非常的常見了，因為Java原生排序的算法多是基于各種快速排序(Quick Sort)的變體。

第二種生成BWT變體的算法是通過后綴數(shù)組的線性變化實現(xiàn)的。思路很簡單，一段文本T的BWT變體即為T的后綴數(shù)組的每一個字符的前一個字符構(gòu)成。如表2所示F為后綴數(shù)組，L即為T的BWT變體。

表2

因為該算法通過線性掃描后綴數(shù)組實現(xiàn)，它的運行效率也就主要依賴于后綴數(shù)組的生成算法的選擇。3種主流算法在該項目中進行了比對研究。第一種算法叫做Native Suffix Array(NSA)創(chuàng)建算法，與前文討論過的FT算法類似，它也是依靠對所有后綴數(shù)組的全排序。其時間復(fù)雜度基于所選擇的排序算法在一般情況下可以控制在O(nlgn)，但是基于不同的原文文本語言，O(n2)的情況也會變得比較常見。

如圖1基準(zhǔn)測試所示，該算法只適用于對小于100K的文本文檔進行處理，對大于100K的原文本文檔，消耗的時間超過40秒。如果是大于400K的測試文檔，算法所消耗內(nèi)存超出Android系統(tǒng)的對于單個程序運行的內(nèi)存限制。在時間復(fù)雜度和空間復(fù)雜度方面的表現(xiàn)不佳，使得實施更加優(yōu)質(zhì)算法成為必要。

圖1 NSA算法的BWT變體生成效率基準(zhǔn)測試

第二種和第三種算法的后綴數(shù)組的生成算法都是線性的時間復(fù)雜度，他們都基于同一種思路:先把原文本部分排序，再用排序的部分對剩余的部分進行全排序。第二種算法被稱之為DC3(或者叫做skew)［5］。第三種線性算法叫做 SAIS［6］，它被稱為現(xiàn)階段時間復(fù)雜度和空間復(fù)雜度效率最高的算法。以下就這兩種算法的基準(zhǔn)測試效果如圖2所示(注:其中藍色(最左側(cè))曲線仍為NSA算法;橘黃色(右側(cè)倒數(shù)第二條)曲線為Skew算法;灰色(最右側(cè))線表示的是在對Skew算法進行了輕量級Java實現(xiàn)優(yōu)化后的表現(xiàn);紫色(左起第二條)曲線表示SAIS算法)。

可以看到SAIS實際上在SKEW沒有超出內(nèi)存的情況下并沒有速度優(yōu)勢。但是在空間使用方面，即使對于超過1.5M的文本文件，SAIS算法也能夠保證在不內(nèi)存溢出的情況下，25秒的時間內(nèi)完成任務(wù)，在移動平臺上這種運行效率是相當(dāng)驚人的。

圖2 兩種算法基準(zhǔn)測試效果

五、結(jié)論

經(jīng)過本項目的比對，在BWT生成算法階段，不同的算法體現(xiàn)出了對系統(tǒng)不同的要求和效率?？傮w來講，由于其在時間復(fù)雜度和空間復(fù)雜度方面的低效表現(xiàn)，原生排序算法應(yīng)該被排除在可選的算法行列。如果要處理的文件小于500K，Skew算法應(yīng)該被給予優(yōu)先考慮。因為在移動平臺硬件和軟件系統(tǒng)的限制下，Skew算法表現(xiàn)出了高效的運算效率和空間使用效率。而對于大于500K的數(shù)據(jù)，更加穩(wěn)定的SAIX算法應(yīng)該被采用。雖然在速度上稍遜一籌，其在時間和空間很好的平衡性使得其在更大的數(shù)據(jù)樣本上成為更加合適的選擇。通過以上的優(yōu)化，BWT的生成算法階段的三個瓶頸就可以被有效克服，使其在移動平臺上的高效應(yīng)用成為現(xiàn)實。

自從Michael Burrows和David Wheeler于1994年發(fā)明了BWT算法以來，其高效的壓縮比和變形后強大的數(shù)據(jù)獲取以及搜索能力都成為該算法被廣泛應(yīng)用于各個領(lǐng)域的重要原因。尤其是在大量云數(shù)據(jù)需要本地化的需求面前，其應(yīng)用前景也變得格外廣闊。移動平臺的硬件束縛與BWT搜索算法高需求之間的矛盾仍然是需要解決的一個很重要的問題，其解決方案也將成為今后相關(guān)研究的核心發(fā)展方向。

［1］Donald Adjeroh，Timothy Bell，Amar Mukherjee.The Burrows-Wheeler Transform，Data Compression，Suffix Arrays，and Pattern matching［M］.Berlin:Springer Science Business Media，2008.

［2］Ferragina P，Manzini G.Opportunistic data structures with applications［J］.Proc.41st Annual Symp.on Foundations of Comp.Sci.，2000:390.

［3］孔凡良.Java程序內(nèi)存泄漏研究［J］.科技廣場，2009(9).

［4］Raymond K W，F(xiàn)ranky Lam，William M S.Querying and maintaining a compact XML storage［R］.Proceedings of the 16th international conference on World Wide Web，2007.

［5］劉小華，翟有利.靈活的面向字節(jié)基于詞的壓縮搜索算法［EB/OL］.(2013-11-11).［2015-02-07］.http://www.paper.edu.cn/releasepaper/content/201311-193.

［6］Ge Nong，Sen Zhang，Wai Hong Chan.Two Efficient Algorithms for Linear Time Suffix Array Construction，IEEE Transactions on Computers［C］.IEEE computer Society Digital Library，2010.

［7］Kieffer J C，Yang E H，Nelson G J，et al.Universal lossless compression via multilevel pattern matching［J］.IEEE Transactions on Information Theory，2000，46(4):1227-1245.