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

李 冰 龍冰潔劉 勇

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

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

李 冰 龍冰潔*劉 勇

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

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

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

1 引言

數(shù)據(jù)壓縮在信息技術中占有很重要的地位，傳統(tǒng)的LZ系列和ZIP系列壓縮算法利用了數(shù)據(jù)內部的重復性，對數(shù)據(jù)重復性進行記錄，然后對數(shù)據(jù)進行編碼處理，從而得到壓縮數(shù)據(jù)。這些壓縮算法的壓縮率在一定程度上取決于數(shù)據(jù)內部的重復性。Bzip2與這些傳統(tǒng)的算法不同，Bzip2的核心變換算法Burrow-Wheeler 變換(Burrows-Wheeler Transform, BWT)是一種不依賴于數(shù)據(jù)內部重復性的變換方法，它能將數(shù)據(jù)內部相同的字符聚集到一起，這使得Bzip2的壓縮率基本不會受到數(shù)據(jù)內部重復性的影響，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]，這種算法的核心思想是對字符串輪轉后得到的字符矩陣進行排序和變換，得到的結果序列中相同的字符在很大程度上聚集到了一起，這樣的特性很適合使用通用的統(tǒng)計壓縮模型(Huffman編碼、PPM算法等)進行壓縮，并得到理想的壓縮率[5-7]。BWT原始算法是通過矩陣完成的，需要占用大量存儲資源，交織(Weavesort, WS)編碼算法的出現(xiàn)解決了這個問題，但是這種算法處理的速度太慢[8-11]，基于后綴排序的算法(Suffix sorting)比WS算法在速度上提高了很多，其中雙向搜索算法(Bi-directional search)進一步提高了處理速度[12-16]。本文通過對基于后綴排序實現(xiàn)BWT算法的研究，結合后綴排序以及BWT自身的特點，提出了一種快速實現(xiàn)BWT的算法，稱其為后綴段算法，仿真結果證實了這種算法能在存儲資源消耗與雙向搜索算法基本相當?shù)那闆r下大大減少BWT的時間。

2 BWT與后綴排序

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

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

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

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

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

圖1 BWT實例

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

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

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

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

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

3 后綴段算法

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

對于字符串S，定義集合Pi:{Sj:j＜i,Xi= Xj,Si+1＜Sj+1}，它表示當前后綴鏈表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)，需要有更進一步的分析，參照雙向搜索算法的原理以及集合Pi，同樣可以定義集合Pi:{Sj:j＜i,Xi=Xj,Si+1＞Sj+1}，它表示當前后綴鏈表Ti-1中首字符與Si的首字符Xi相同并且比Si大的所有后綴集合，出現(xiàn)情況(2)時，檢測Qi是否為空集，如果Qi不是空集，則在Qi中搜索并插入Si。

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

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

圖2 后綴鏈表結構

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

圖3 插入后綴Si的流程

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

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

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

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

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

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

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

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

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

4 實驗結果分析

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

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

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

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

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

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

5 結束語

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

[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年生，教授，博士生導師，研究方向為現(xiàn)場集成系統(tǒng)與信息專用集成電路設計、數(shù)據(jù)壓縮等.

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

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

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