BWT生成算法在移動(dòng)平臺(tái)實(shí)現(xiàn)的對(duì)比和優(yōu)化研究

王國政，朱光彥

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

一、BWT算法簡介以及項(xiàng)目背景

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

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

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

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

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

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

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

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

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

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

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

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

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

四、問題分析和解決方案

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

表1

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

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

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

表2

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

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

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

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

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

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

五、結(jié)論

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

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