李 冰 龍冰潔劉 勇

(東南大學(xué)集成電路學(xué)院 南京 210000)

一種基于后綴排序快速實現(xiàn)Burrows-Wheeler變換的方法

李 冰 龍冰潔*劉 勇

(東南大學(xué)集成電路學(xué)院 南京 210000)

近年來，Bzip2壓縮算法憑借其在壓縮率方面的優(yōu)勢，得到了越來越多的應(yīng)用，Bzip2的核心算法是Burrows-Wheeler變換(BWT), BWT能有效的將數(shù)據(jù)中相同的字符聚集到一起，為進(jìn)一步壓縮創(chuàng)造條件。在硬件實現(xiàn)BWT時，常用的基于后綴排序的算法能有效克服BWT消耗存儲資源大的問題，該文對基于后綴排序?qū)崿F(xiàn)BWT的方法進(jìn)行了詳細(xì)分析，并且在此基礎(chǔ)上提出了一種快速實現(xiàn)BWT的方法后綴段算法。仿真結(jié)果表明后綴段算法在處理速度上比傳統(tǒng)的基于后綴排序的算法有很大的提高。

信號處理；數(shù)據(jù)壓縮；Bzip2；Burrows-Wheeler變換；后綴排序

1 引言

數(shù)據(jù)壓縮在信息技術(shù)中占有很重要的地位，傳統(tǒng)的LZ系列和ZIP系列壓縮算法利用了數(shù)據(jù)內(nèi)部的重復(fù)性，對數(shù)據(jù)重復(fù)性進(jìn)行記錄，然后對數(shù)據(jù)進(jìn)行編碼處理，從而得到壓縮數(shù)據(jù)。這些壓縮算法的壓縮率在一定程度上取決于數(shù)據(jù)內(nèi)部的重復(fù)性。Bzip2與這些傳統(tǒng)的算法不同，Bzip2的核心變換算法Burrow-Wheeler 變換(Burrows-Wheeler Transform, BWT)是一種不依賴于數(shù)據(jù)內(nèi)部重復(fù)性的變換方法，它能將數(shù)據(jù)內(nèi)部相同的字符聚集到一起，這使得Bzip2的壓縮率基本不會受到數(shù)據(jù)內(nèi)部重復(fù)性的影響，Bzip2壓縮數(shù)據(jù)主要由游程編碼(Run-Length Encoding, RLE), BWT，前移變換(Move-To-Front, MTF)以及霍夫曼(Huffman)編碼4個步驟組成，Bzip2的壓縮性能比其它傳統(tǒng)的壓縮算法都要高，但是耗費的壓縮時間比較長[1-4]。

Bzip2壓縮數(shù)據(jù)過程中耗時最多的是BWT，快速實現(xiàn)BWT能有效地減少Bzip2壓縮數(shù)據(jù)的時間。BWT由Burrows和Wheeler在1994年提出[5]，這種算法的核心思想是對字符串輪轉(zhuǎn)后得到的字符矩陣進(jìn)行排序和變換，得到的結(jié)果序列中相同的字符在很大程度上聚集到了一起，這樣的特性很適合使用通用的統(tǒng)計壓縮模型(Huffman編碼、PPM算法等)進(jìn)行壓縮，并得到理想的壓縮率[5-7]。BWT原始算法是通過矩陣完成的，需要占用大量存儲資源，交織(Weavesort, WS)編碼算法的出現(xiàn)解決了這個問題，但是這種算法處理的速度太慢[8-11]，基于后綴排序的算法(Suffix sorting)比WS算法在速度上提高了很多，其中雙向搜索算法(Bi-directional search)進(jìn)一步提高了處理速度[12-16]。本文通過對基于后綴排序?qū)崿F(xiàn)BWT算法的研究，結(jié)合后綴排序以及BWT自身的特點，提出了一種快速實現(xiàn)BWT的算法，稱其為后綴段算法，仿真結(jié)果證實了這種算法能在存儲資源消耗與雙向搜索算法基本相當(dāng)?shù)那闆r下大大減少BWT的時間。

2 BWT與后綴排序

對于一個包含N字節(jié)的字符串S，對其進(jìn)行BWT由3個步驟組成：

步驟 1 構(gòu)造一個N×N矩陣M(M中的每一行分別是S左移0,1,…,n-1個字符)；

步驟 2 對矩陣M行向量按字典順序進(jìn)行升序排序，得到新的矩陣MT；

步驟3 輸出MT中最后一列(記為L)以及原字符串S在MT中的行號index。

以abraca為例，其BWT變換過程如圖1所示。

圖1 BWT實例

abraca的BWT結(jié)果L=caraab , index = 1是用于進(jìn)行BWT反變換的。BWT之后，數(shù)據(jù)長度并沒用縮短，但相同字符很大程度上被排列到了一起。

對于字符串S:X1X2…XN，將它的子字符串XiXi+1…XN稱為后綴Si，后綴之間存在著大小關(guān)系，假設(shè)有后綴Xi與Xj，定義其大小關(guān)系為：

(1)如果Xi＞Xj，則Si＞Sj；

(2)如果Xi＜Xj，則Si＜Sj；

(3)如果Xi=Xj，則繼續(xù)比較Si+1和Sj+1，比較規(guī)則同(1)和(2)。

對于字符串S:X1X2…XN，在其后面添加一個$，得到S′:X1X2…XN$其中$ 需要滿足條件$>Xt,t=1,2,…,N ，即$要比S中所有字符的字典序都要大，將S′的所有后綴進(jìn)行升序排序，同樣以abraca為例，首先在其后面添加一個$ ，這樣這個字符串就有7個后綴，分別是S1:abraca$,S2: braca$,S3:raca$,S4:aca$,S5:ca$,S6:a$,S7:$根據(jù)后綴大小的比較規(guī)則，這些后綴的升序排列結(jié)果為S1S4S6S2S5S3S7，現(xiàn)在用每個后綴在S′中的前一個字符代替，得到X7X3X5X1X4X2X6，即$rcaaba，同樣，參照圖1所示的方法對S′進(jìn)行BWT，可以發(fā)現(xiàn)其BWT結(jié)果也是$rcaaba，也就是說只要進(jìn)行BWT的字符串滿足最后一個字符的字典序比其它出現(xiàn)在字符串中的字符的字典序都大這個條件，那么就可以用后綴排序來得到它的BWT結(jié)果，實際上滿足這個條件的字符串很少，但是一般在讀入數(shù)據(jù)流的時候，都會默認(rèn)添加一個文件結(jié)束符(End of File, EOF)，而EOF恰好是滿足這個條件的，所以后綴排序的時候帶上EOF就可以了。

對于一個字符串S:X1X2…XN對其后綴進(jìn)行排序，從第1個后綴S1(S)開始處理，直到最后一個后綴SN(XN)，處理后綴Si相當(dāng)于是都在S1S2…Si-1的升序排列集合中插入Si，用Ti-1來表示這個升序排列集合，將這樣的集合稱為后綴鏈表。當(dāng)所有后綴完成排序后，得到后綴鏈表TN，將TN中的所有后綴用它在S中的前一個字符(圖1中矩陣MT的最后一列)替換，即后綴用字符替換(S1用XN替換)，這樣得到的字符串就是S的BWT結(jié)果，這就是后綴排序?qū)崿F(xiàn)BWT的原理，也是基于后綴排序?qū)崿F(xiàn)BWT的基本算法。

在后綴排序中將后綴Si插入到后綴鏈表Ti-1的過程中，需要將Si與Ti-1中所有后綴進(jìn)行比較，從而確定Si在Ti-1中的位置，稱這個過程為搜索。以降序搜索為例，當(dāng)Ti-1中所包含的后綴很多，并且Si比Ti-1中絕大多數(shù)后綴都要小的時候，搜索過程耗費的時間是很長的，這種情況下采用升序搜索就能很快確定Si在后綴鏈表中的位置，于是基于后綴排序?qū)崿F(xiàn)BWT的雙向搜索算法也很自然地被提出，就是在后綴鏈表中升序搜索和降序搜索同時進(jìn)行，只有有一個方向上找到Si對應(yīng)的位置，即停止搜索，并插入Si，然后更新相應(yīng)的信息。但是當(dāng)數(shù)據(jù)塊很大，處理過程中Ti-1包含的后綴越來越多，而且Si處于Ti-1的中間位置的時候，即使采用雙向搜索算法，耗費的時間也是很長的。

3 后綴段算法

仔細(xì)分析一下后綴排序的特點，可以發(fā)現(xiàn)有很多特點是可以利用的。

對于字符串S，定義集合Pi:{Sj:j＜i,Xi= Xj,Si+1＜Sj+1}，它表示當(dāng)前后綴鏈表Ti-1中首字符與Si的首字符Xi相同并且比Si小的所有后綴集合，在插入Si的過程中會出現(xiàn)以下3種情況：

(1)Ti-1中存在以Xi為首字符的后綴Si，并且也滿足Xj=Xi, Sj+1＜Si+1，這時Pi不是空集；

(2)Ti-1中存在以Xi為首字符的后綴Si，但是不滿足Xj=Xi, Sj+1＜Si+1，這時Pi是空集；

(3)Ti-1中不存在以Xi為首字符的后綴，這時Pi也是空集。

以降序搜索為例，在后綴排序過程中，情況(1)出現(xiàn)的可能性最大，出現(xiàn)情況(1)時，需要在Pi中搜索并插入Si；對于情況(2)和情況(3)，需要有更進(jìn)一步的分析，參照雙向搜索算法的原理以及集合Pi，同樣可以定義集合Pi:{Sj:j＜i,Xi=Xj,Si+1＞Sj+1}，它表示當(dāng)前后綴鏈表Ti-1中首字符與Si的首字符Xi相同并且比Si大的所有后綴集合，出現(xiàn)情況(2)時，檢測Qi是否為空集，如果Qi不是空集，則在Qi中搜索并插入Si。

假設(shè)Pi和Qi中的后綴都是按照升序排列的，定義集合Ri:{Pi,Qi}，表示Ti-1中首字符與后綴Si的首字符相同的所有后綴的集合，稱其為后綴段，并且將Si的首字符Xi稱為后綴段Ri的段首字符。顯然，根據(jù)后綴大小的判斷規(guī)則，在后綴排序的過程中，后綴鏈表由0～256個后綴段(假設(shè)文件是以ASCⅡ碼的形式讀入)按照段首字符升序排列組成。當(dāng)出現(xiàn)情況(1)和情況(2)時，Ri不是空集，在插入后綴Si時，只要能確定以Xi為段首字符的后綴段Ri在后綴鏈表中的位置，接下來在Ri中搜索并插入Si就可以了。當(dāng)出現(xiàn)情況(3)時，Ri是空集，這時需要做的就是找到段首字符與Xi距離最近的段，然后根據(jù)大小情況將Si插入到對應(yīng)的位置。

通過以上分析可以知道在后綴排序過程中，有3條信息是可以利用的：(1)Ri是否已經(jīng)存在于當(dāng)前的后綴鏈表Ti-1中，這個信息可以用一個數(shù)組appear記錄，appear[i]=1表示Ri已經(jīng)存在于后綴鏈表中，appear[i]=0表示Ri還不存在；(2)當(dāng)前Ri中最大的后綴max[i], max[i]里面存放的是當(dāng)前Ri中最大的后綴在后綴鏈表中的地址；(3)當(dāng)前Ri中最小的后綴min[i], min[i] 里面存放的是當(dāng)前Ri中最小的后綴在后綴鏈表中的地址，信息(2)和(3)用于確定Ri在后綴鏈表中的位置。在后綴排序過程中后綴鏈表結(jié)構(gòu)如圖2所示。

圖2 后綴鏈表結(jié)構(gòu)

綜合以上對后綴排序特點的分析，可以總結(jié)出后綴段實現(xiàn)BWT的步驟：首先初始化后綴鏈表為空，接下來從后綴Si開始，一直到后綴SN，每次向后綴鏈表中插入一個后綴。插入后綴Si的步驟如圖3所示：首先檢查appear[i]的值，如果appear[i]=1，說明對應(yīng)的Ri已經(jīng)存在，接下來在Ri內(nèi)進(jìn)行雙向搜索并插入Si；如果appear[i]=0，說明對應(yīng)的Ri不存在，這時需要查找距離最近的后綴段，根據(jù)最近后綴段的大小確定Si所在的位置并更新后綴鏈表和相應(yīng)信息。

圖3 插入后綴Si的流程

圖4 查找距離最近的段流程

查找距離最近的段的步驟如圖4所示。查找距離最近的段是一個雙向的過程，從appear[i+1]和appear[i-1]開始依次往兩邊擴散，直到appear[t]的值為1，如果t＞i,Si就應(yīng)該插入到段Ri中最小后綴的左邊；如果t＜i,Si就應(yīng)該插入到段Ri中最大后綴的右邊。插入Si后，需要更新后綴鏈表以及相應(yīng)的max[i]和min[i]的值，且令appear[i]=1。

在段Ri中雙向搜索的步驟如圖5所示：首先根據(jù)max[i]min[i]的值確定Ri在后綴鏈表中的位置，接下來從max[i]和min[i]開始依次在兩個方向上往段內(nèi)取相鄰后綴與Si進(jìn)行比較，直到確定Si在Ri中的位置，插入Si，然后更新后綴鏈表以及相應(yīng)的max[i]和min[i]的值。

在所有后綴都已經(jīng)插入到后綴鏈表后，把后綴鏈表中的所有后綴用它在S中的前一個字符替換，這就是基于后綴段實現(xiàn)BWT的方法。

對于硬件實現(xiàn)來說，存儲資源是十分寶貴的資源，用硬件實現(xiàn)很多經(jīng)典的算法時，存儲資源往往成為瓶頸，一個算法是否能夠很好地用硬件實現(xiàn)也很大程度上與其所消耗的存儲資源有關(guān)，第2節(jié)曾提到用基于后綴排序的算法來實現(xiàn)BWT比起原始算法最大的優(yōu)勢就是節(jié)省了大量的存儲資源，但是在變換速度上仍然顯得不夠，后綴段算法利用了后綴排序算法的特點，在增加了一些存儲資源的情況下，大大提高了變換速度。

圖5 在段Ri中雙向搜索流程圖

對于一個長度為N字節(jié)，包含T個不同的字符的字符串S，采用后綴段算法實現(xiàn)BWT所消耗的主要存儲資源為(假設(shè)文件都是以ASCⅡ碼形式讀入)：

(1)位寬為8，深度為N的數(shù)組，用于存放字符串S；

(3)位寬為1，深度為256的數(shù)組，用于記錄以ASCⅡ值為0～255的字符為段首字符的后綴段是否存在于后綴鏈表中；

4 實驗結(jié)果分析

對基于后綴排序?qū)崿F(xiàn)BWT的3種算法進(jìn)行了仿真測試，測試代碼是用Verilog硬件語言進(jìn)行設(shè)計的，在Modelsim軟件下面進(jìn)行仿真。用于測試的數(shù)據(jù)是一系列長度不同的0～255的隨機數(shù)，3種基于后綴排序?qū)崿F(xiàn)BWT的算法在處理這些數(shù)據(jù)時所消耗的主要存儲資源如表1所示，完成BWT的時間如表2所示。

表1給出了3種基于后綴排序?qū)崿F(xiàn)BWT算法的存儲資源，3種算法的主要消耗在于后綴鏈表中記錄該處后綴在S中的地址，這是區(qū)分后綴的唯一標(biāo)識，另外，在后綴段算法中，增加了bit的消耗，這個消耗用于記錄后綴段在后綴鏈表中的位置，是提高排序速度必不可少的。

表1 3種算法實現(xiàn)BWT消耗的存儲資源(bit)

表2 3種算法完成BWT的時間(ms)

表2給出了3種基于后綴排序?qū)崿F(xiàn)BWT算法的速度結(jié)果，表中數(shù)據(jù)長度的單位是字節(jié)，后面3列數(shù)據(jù)表示該算法處理對應(yīng)大小的數(shù)據(jù)時所用的時間，單位是ms。這里由于采用基本算法處理16k字節(jié)以上大小的文件時耗時太長，所以沒有給出具體數(shù)據(jù)。

從測試結(jié)果數(shù)據(jù)上可以得出一些結(jié)論：當(dāng)數(shù)據(jù)的長度增加一倍時，基本算法完成后綴排序的時間大概會增加3倍；雙向算法所用的時間大概也會增加3～4倍；后綴段算法所用的時間大概會增加2～3倍。在數(shù)據(jù)長度相同的情況下，雙向算法完成后綴排序的時間比基本算法減少了20%，后綴段算法完成后綴排序的時間比起雙向算法則有了更加明顯的減少，隨著數(shù)據(jù)長度的增加，后綴段算法完成后綴排序的時間比起雙向算法減少的幅度也在增加，當(dāng)數(shù)據(jù)長度為32k時，后綴段算法完成后綴排序所用的時間只是雙向算法的十分之一不到，而且可以推測當(dāng)數(shù)據(jù)長度進(jìn)一步增加時，后綴段算法的優(yōu)勢會更加明顯。

5 結(jié)束語

本文針對Bzip2壓縮算法里面的BWT部分，對其原理算法進(jìn)行了介紹，對基于后綴排序的BWT算法進(jìn)行了詳細(xì)的分析，利用后綴排序中后綴鏈表的組成特點提出了后綴段算法，雖然比傳統(tǒng)的基本算法和雙向搜索算法消耗更多的存儲資源，但是在處理速度上得到了明顯的提高。測試結(jié)果表明在處理同樣長度的數(shù)據(jù)時，后綴段算法能明顯減少處理時間，在數(shù)據(jù)長度從2k增加到64k時，后綴段算法與雙向算法完成后綴排序所用的時間比從1:3逐漸減小到1:10不到，并且時間減少的幅度在不斷增加。在后綴段中進(jìn)行雙向搜索的優(yōu)化是進(jìn)一步研究的重點。

[1] Julian Seward, Bzip2[OL]. http://en.wikipedia.org/wiki/ Bzip2, 2010.9.20

[2] Szecówka P M, and Mandrysz T. Towards hardware implementation of bzip2 data compression algorithm [C]. Proceedings of the Mixed Design of Integrated Circuits and Systems, Lodz, Polland, 2009: 337-340.

[3] Sun Wei-feng, Zhang Nan, and Mukherjee A. Dictionarybased fast transform for text compression[C]. Proceedings of the International Conference on Information Technology: Computers and Communications, Nanjing, China, 2003: 176-182.

[4] Baloul F M, Abdulah M H, and Babikir E A. ETAOSD: static dictionary-based transformation method for text compression [C]. Prioeedings of the International Conference on Computing, Electrical and Electronic Engineering, Khartoum, Sudan, 2013: 384-389.

[5] Burrows M and Wheeler D. A block-sorting lossless data compression algorithm[R]. SRC Research Report 124, Digital Systems Research Center, Palo Alto, CA, USA, 1994.

[6] Arnsvut Z. Move-to-front and inversion coding[C]. Data Compress Conference, Snowbird, USA, 2000: 193-202.

[7] Effros M. PPM performance with BWT complexity: a fast and effective data compress algorithm[J]. Proceedings of the IEEE, 2000, 88(11): 1703-1712.

[8] Martínez J, Cumplido R, and Feregrino C. A fast algorithm for making suffix arrays and for Burrows-Wheeler transformation[C]. Proceedings of the International Conference on Reconfigurable Computing and FPGAs, Puebla City, Mexico, 2005: 28-30.

[9] Kong J M, Ang L M, and Seng K P. Low-complexity two instructions set for suffix sort in Burrows-Wheeler transform[C]. Proceedings of the International Conference on Advanced Computer Science Applications and Technologies, Kuala Lumpur, Malaysia, 2012: 181-186.

[10] Arming S, Fenkhuber R, and Handl T. Data compression in hardwarethe Burrows-Wheeler approach[C]. Proceedings of the Design and Diagnostics of Electronic Circuits and Systems (DDECS), Vienna, Austria, 2010: 60-65.

[11] Grajeda V Z, Uribe C F, and Parra R C. Parallel hardware/ aoftware architecture for the BWT and LZ77 lossless data compression algorithms[J]. Computation System, 2006, 10(2): 172-188.

[12] Sadakane K. A modified Burrows-Wheeler transformation for case-insensitive search with application to suffix array compression[C]. Proceedings of the Data Compression Conference, Snowbird, USA, 1999: 29-31.

[13] Hayashi S and Taura K. Parallel and memory-efficient Burrows-Wheeler transform[C]. Proceedings of the IEEE International Conference on Big Data, Silicon Valley, USA 2013: 43-50.

[14] Zhao Zhi-heng, Yin Jian-pin, and Xiong Wei. GPU-accelerated Burrows-Wheeler transform for genomic data[C]. Proceedings of the 5th International Conference on BioMedical Engineering and Informatics, Chongqing, China, 2012: 889-892.

[15] Cheema U I and Khokhar A A. High performance architecture for computing Burrows-Wheeler transform on FPGAs[C]. Proceedings of the International Conference on Reconfigurable and FPGAs, Cancun, Mexico, 2013: 1-6.

[16] Baron D and Bresler Y. Antisequential suffix sorting for BWT-based sata sompression[J]. Computers, 2005, 54(4): 385-397.

李 冰： 男，1963年生，教授，博士生導(dǎo)師，研究方向為現(xiàn)場集成系統(tǒng)與信息專用集成電路設(shè)計、數(shù)據(jù)壓縮等.

龍冰潔： 男，1988年生，碩士生，研究方向為嵌入式系統(tǒng)、數(shù)據(jù)壓縮.

劉 勇： 男，1979年生，博士生，研究方向為集成電路設(shè)計.

A Fast Algorithm for Burrows-Wheeler Transform Using Suffix Sorting

Li Bing Long Bing-jie Liu Yong
(College of Integrated Circuit, Southeast University, Nanjing 210000, China)

Bzip2, a lossless compression algorithm, is widely used in recent years because of its high compression ratio. Burrows-Wheeler Transform (BWT) is the key factor in Bzip2. This method can gather the same symbols together. The traditional methods which are based on suffix sorting used in implement of BWT in hardware can solve the problem of memory consumption effectively. Detail analysis of BWT algorithm based on suffix sorting is given and a new methodSuffix segment method is presented in this paper. Experimental results show that the proposed method can much decrease BWT time consumption without increasing memory consumption much.

Information processing; Data compress; Bzip2; Burrows-Wheeler Transform (BWT); Suffix sorting

TN492

A

1009-5896(2015)02-0504-05

10.11999/JEIT140232

2014-02-24收到，2014-07-17改回

十二五國家科技支撐計劃(2013BAJ05B03)資助課題

*通信作者：龍冰潔 longbj1107@sinacom