一種基于后綴排序快速實現(xiàn)Burrows-Wheeler變換的方法
doi: 10.11999/JEIT140232 cstr: 32379.14.JEIT140232
基金項目:
十二五國家科技支撐計劃(2013BAJ05B03)資助課題
A Fast Algorithm for Burrows-Wheeler Transform Using Suffix Sorting
-
摘要: 近年來，Bzip2壓縮算法憑借其在壓縮率方面的優(yōu)勢，得到了越來越多的應(yīng)用，Bzip2的核心算法是Burrows-Wheeler變換(BWT), BWT能有效的將數(shù)據(jù)中相同的字符聚集到一起，為進一步壓縮創(chuàng)造條件。在硬件實現(xiàn)BWT時，常用的基于后綴排序的算法能有效克服BWT消耗存儲資源大的問題，該文對基于后綴排序?qū)崿F(xiàn)BWT的方法進行了詳細(xì)分析，并且在此基礎(chǔ)上提出了一種快速實現(xiàn)BWT的方法后綴段算法。仿真結(jié)果表明后綴段算法在處理速度上比傳統(tǒng)的基于后綴排序的算法有很大的提高。
-
關(guān)鍵詞:
- 信號處理 /
- 數(shù)據(jù)壓縮 /
- Bzip2 /
- Burrows-Wheeler變換 /
- 后綴排序
Abstract: 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.-
Key words:
- Information processing /
- Data compress /
- Bzip2 /
- Burrows-Wheeler Transform (BWT) /
- Suffix sorting
-
計量
- 文章訪問數(shù): 2089
- HTML全文瀏覽量: 129
- PDF下載量: 1211
- 被引次數(shù): 0
下載:
