快速有限階Burrows-Wheeler變換的算法設(shè)計及應(yīng)用.pdf

1、本文基于對一種新的ST逆變換算法的分析，實現(xiàn)了快速ST正向變換算法，并將兩者結(jié)合實現(xiàn)了一個快速有限階BWT算法。此算法實現(xiàn)的目的在于驗證新逆ST算法的可行性及其能否保持ST正向變換相對于BWT的時間復(fù)雜度優(yōu)勢，同時使新的逆ST算法能夠?qū)嶋H應(yīng)用。ST是針對BWT正向變換中超線性排序時間復(fù)雜度改進(jìn)的一個BWT變種。現(xiàn)存逆ST算法由于采用了哈希表而導(dǎo)致了較高的復(fù)雜度，影響了sT正向變換帶來的優(yōu)勢。新的逆ST算法的提出使得ST正向變換相對于BW

2、T的優(yōu)勢能得以保持。因此要驗證新的逆ST算法的理論意義，ST正、逆變換的快速實現(xiàn)尤為關(guān)鍵。實現(xiàn)sT正向變換的主要難點是如何在線性的復(fù)雜度內(nèi)實現(xiàn)正向變換中的排序操作。本文采用了一種改進(jìn)的基數(shù)排序來解決此問題。為了驗證新的逆ST算法的可行性，本文對所實現(xiàn)的快速有限階BWT算法與無限階BWT算法進(jìn)行對比實驗，在Calgary數(shù)據(jù)集上進(jìn)行驗證和性能分析。實驗數(shù)據(jù)表明新的快速有限階BwT算法可在保持壓縮率為無限階BWT算法的99.83﹪的同時，提