Burrows-Wheeler變換

Burrows–Wheeler Transform（簡稱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變換過程

演算法將輸入字串的所有循環字串按照字典序排序，並以排序後字串形成的矩陣的最後一列為其輸出。

Burrows–Wheeler變換過程

輸入｜所有的循環字串｜將所有的字串按照字典序排序｜輸出最後一列

banana｜$ b a n a n a a $ b a n a n n a $ b a n a a n a $ b a n n a n a $ b a a n a n a $ b b a n a n a $｜$ b a n a n a a $ b a n a n a n a $ b a n a n a n a $ b b a n a n a $ n a $ b a n a n a n a $ b a｜a n n b $ a a

## Burrows–Wheeler變換的還原過程

- 基於上述的BWT變換過程，以字串「banana」為例，我們得到了變換結果「annb$aa」。其還原過程見以下過程：
- 1 基於原字串矩陣的最後一列為「annb$aa」，我們進行該列進行排序，得到「$aaabnn」,並將其作為還原矩陣的第一列

Burrows–Wheeler 還原過程 1

輸入｜轉移｜排序｜組合

- - - - - - a - - - - - - n - - - - - - n - - - - - - b - - - - - - $ - - - - - - a - - - - - - a｜a - - - - - - n - - - - - - n - - - - - - b - - - - - - $ - - - - - - a - - - - - - a - - - - - -｜$ - - - - - - a - - - - - - a - - - - - - a - - - - - - b - - - - - - n - - - - - - n - - - - - -｜$ - - - - - a a - - - - - n a - - - - - n a - - - - - b b - - - - - $ n - - - - - a n - - - - - a

- 2 經過1.1的轉移、排序和組合，我們得到了7對鄰接字串：，將這7對鄰接字串進行排序後，得到，由此，我們得到了還原矩陣的第二列「b$nnaaa」

Burrows–Wheeler 還原過程 2

輸入｜轉移｜排序｜組合

$ - - - - - a a - - - - - n a - - - - - n a - - - - - b b - - - - - $ n - - - - - a n - - - - - a｜a $ - - - - - n a - - - - - n a - - - - - b a - - - - - $ b - - - - - a n - - - - - a n - - - - -｜$ b - - - - - a $ - - - - - a n - - - - - a n - - - - - b a - - - - - n a - - - - - n a - - - - -｜$ b - - - - a a $ - - - - n a n - - - - n a n - - - - b b a - - - - $ n a - - - - a n a - - - - a

- 3 經過1.2的轉移、排序和組合，我們得到了7對鄰接字串：，將這7對鄰接字串進行排序後，得到，由此，我們得到了還原矩陣的第三列「abaan$n」

Burrows–Wheeler 還原過程 3

輸入｜轉移｜排序｜組合

$ b - - - - a a $ - - - - n a n - - - - n a n - - - - b b a - - - - $ n a - - - - a n a - - - - a｜a $ b - - - - n a $ - - - - n a n - - - - b a n - - - - $ b a - - - - a n a - - - - a n a - - - -｜$ b a - - - - a $ b - - - - a n a - - - - a n a - - - - b a n - - - - n a $ - - - - n a n - - - -｜$ b a - - - a a $ b - - - n a n a - - - n a n a - - - b b a n - - - $ n a $ - - - a n a n - - - a

- 4 經過1.3的轉移、排序和組合，我們得到了7對鄰接字串：，將這7對鄰接字串進行排序後，得到，由此，我們得到了還原矩陣的第四列「na$naba」

Burrows–Wheeler 還原過程 4

輸入｜轉移｜排序｜組合

$ b a - - - a a $ b - - - n a n a - - - n a n a - - - b b a n - - - $ n a $ - - - a n a n - - - a｜a $ b a - - - n a $ b - - - n a n a - - - b a n a - - - $ b a n - - - a n a $ - - - a n a n - - -｜$ b a n - - - a $ b a - - - a n a $ - - - a n a n - - - b a n a - - - n a $ b - - - n a n a - - -｜$ b a n - - a a $ b a - - n a n a $ - - n a n a n - - b b a n a - - $ n a $ b - - a n a n a - - a

- 5 經過1.4的轉移、排序和組合，我們得到了7對鄰接字串：，將這7對鄰接字串進行排序後，得到，由此，我們得到了還原矩陣的第五列「anbana$」

Burrows–Wheeler 還原過程 5

輸入｜轉移｜排序｜組合

$ b a n - - a a $ b a - - n a n a $ - - n a n a n - - b b a n a - - $ n a $ b - - a n a n a - - a｜a $ b a n - - n a $ b a - - n a n a $ - - b a n a n - - $ b a n a - - a n a $ b - - a n a n a - -｜$ b a n a - - a $ b a n - - a n a $ b - - a n a n a - - b a n a n - - n a $ b a - - n a n a $ - -｜$ b a n a - a a $ b a n - n a n a $ b - n a n a n a - b b a n a n - $ n a $ b a - a n a n a $ - a

- 6 經過1.5的轉移、排序和組合，我們得到了7對鄰接字串：，將這7對鄰接字串進行排序後，得到，由此，我們得到了還原矩陣的第六列「naa$anb」。

Burrows–Wheeler 還原過程 5

輸入｜轉移｜排序｜組合

$ b a n a - a a $ b a n - n a n a $ b - n a n a n a - b b a n a n - $ n a $ b a - a n a n a $ - a｜a $ b a n a - n a $ b a n - n a n a $ b - b a n a n a - $ b a n a n - a n a $ b a - a n a n a $ -｜$ b a n a n - a $ b a n a - a n a $ b a - a n a n a $ - b a n a n a - n a $ b a n - n a n a $ b -｜$ b a n a n a a $ b a n a n a n a $ b a n a n a n a $ b b a n a n a $ n a $ b a n a n a n a $ b a

經過六次排序轉移與組合，還原出了原有的字串即「$banana」。

## python實現(基於next值方式)

```python
def bwt(s):
    """对字符串进行Burrows-Wheeler变换 不使用唯一字符('EOF')做标记 返回索引值列表"""
    #创建所有循环字符串
    table = [s[i:] + s[:i] for i in range(len(s))]
    #获取排序后的结果
    table_sorted = table[:]
    table_sorted.sort()
    #获取已排序表每个字符串在未排序表中对应字符串的下一个字符串在已排序表中的索引值
    indexlist = []
    for t in table_sorted:
        index1 = table.index(t)
        index1 = index1+1 if index1 < len(s)-1 else 0
        index2 = table_sorted.index(table[index1])
        indexlist.append(index2)
    #取排序后结果的最后一列作为结果字符串
    r = ''.join([row[-1] for row in table_sorted])
    return r, indexlist

def ibwt(r,indexlist):
    """对字符串进行反Burrows-Wheeler变换 有索引值的反变换比使用唯一标记的反变换简单很多"""
    s=''
    x = indexlist[0]
    for _ in r:
        s = s + r[x]
        x = indexlist[x]
    return s

```

## python實現(基於末尾添加唯一字符方式)

通過在末尾添加唯一字符(不與輸入字串中任何字符相同)後再進行變換，可以不需要傳遞索引值列表，不過逆變換的時候要做更多計算。

下面的偽代碼提供了一個逆過程的樸素實現（輸入字串s為原過程之輸出）：

```
 '''function''' inverseBWT(''string'' s)
   生成length（s）个空串
   '''repeat''' length(s) '''times'''
       将字符串s作为一列插入每个字符串的串首
       对所有字符串排序
   返回结尾为EOF的行
```

```python
END = '\1'  #必须不与原字符串中任何字符相同

def bwt(s):
    """对字符串进行Burrows-Wheeler变换"""
    s = s + END
    #创建所有循环字符串
    table = [s[i:] + s[:i] for i in range(len(s))]
    #获取排序后的结果
    table_sorted = table[:]
    table_sorted.sort()
    #取排序后结果的最后一列作为结果字符串
    return ''.join([row[-1] for row in table_sorted])

def ibwt(r):
    table = [''] * len(r)
    for _ in r:
        table = sorted([r[m] + table[m] for m in range(len(r))])
    s = [row for row in table if row.endswith(END)][0]
    return s.rstrip(END)
```

## 外部連結

- Compression comparison of BWT based file compressors
- Article by Mark Nelson on the BWT
- A Bijective String-Sorting Transform, by Gil and Scott
- Yuta's openbwt-v1.5.zip contains source code for various BWT routines including BWTS for bijective version
- On Bijective Variants of the Burrows–Wheeler Transform, by Kufleitner
- Blog post and project page for an open-source compression program and library based on the Burrows–Wheeler algorithm
- MIT open courseware lecture on BWT (Foundations of Computational and Systems Biology)