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