Burrows-Wheeler變換
Burrows-Wheeler變換
ar ar ar
Burrows–Wheeler變換(BWT，也稱作塊排序壓縮)，是一個被應用在數據壓縮技術(如bzip2)中的演演算法。該演演算法於1994年被Michael Burrows和David Wheeler在位於加利福尼亞州帕洛阿爾托的DEC系統研究中心發明。它的基礎是之前Wheeler在1983年發明的一種沒有公開的轉換方法。
當一個字元串用該演演算法轉換時，演演算法只改變這個字元串中字元的順序而並不改變其字元。如果原字元串有幾個出現多次的子串，那麼轉換過的字元串上就會有一些連續重複的字元，這對壓縮是很有用的。該方法能使得基於處理字元串中連續重複字元的技術(如MTF變換和遊程編碼)的編碼更容易被壓縮。
舉個例子:
| 演演算法輸入 | SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES |
|---|---|
| 演演算法輸出 | TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT |
該演演算法的輸出因為有更多的重複字元而更容易被壓縮了。
演演算法將輸入字元串的所有循環字元串按照字典序排序，並以排序后字元串形成的矩陣的最後一列為其輸出。
| Burrows–Wheeler變換過程 | |||||
|---|---|---|---|---|---|
| 演演算法輸入 | 序號 | 所有的循環字元串 | 將所有的字元串按照字典序排序 | next值 | 輸出最後一列 |
| abracadabra | 1 2 3 4 5 6 7 8 9 10 | a b r a c a d a b r a b r a c a d a b r a a r a c a d a b r a a b a c a d a b r a a b r c a d a b r a a b r a a d a b r a a b r a c d a b r a a b r a c a a b r a a b r a c a d b r a a b r a c a d a r a a b r a c a d a b a a b r a c a d a b r | a a b r a c a d a b r a b r a a b r a c a d a b r a c a d a b r a a c a d a b r a a b r a d a b r a a b r a c b r a a b r a c a d a b r a c a d a b r a a c a d a b r a a b r a d a b r a a b r a c a r a a b r a c a d a b r a c a d a b r a a b | 10 7 3 5 8 1 4 6 9 2 | rdarcaaaabb |
下面的偽代碼提供了一個樸素的演演算法過程，設s為輸入的字元串並以EOF為結尾：
function BWT (string s) 生成s所有的循環字元串 將這些字元串按字典序排序 返回最後排序后字元串的最後一列
前面的next數值記錄了某個循環字元串向右移動一位之後的字元串在排序之前的位置。知道next之後很容易恢復原字元串。
下面的偽代碼提供了一個逆過程的樸素實現(輸入字元串s為原過程之輸出)：
function inverseBWT (string s)
生成length(s)個空串
repeat length(s) times
將字元串s的第i個字元插入第i個字元串的串首//第一次插入的為空串
將length(s)個字元串按照首字母排序
返回結尾為EOF的行