Burrows-Wheeler變換
Burrows–Wheeler Transform（簡稱BWT，也稱作塊排序壓縮），是一個被應用在數據壓縮技術（如bzip2）中的算法。該算法於1994年被Michael Burrows和David Wheeler在位於加利福尼亞州帕洛阿爾托的DEC系統研究中心發明[1]。它的基礎是之前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 |
$ b a n a n a |
a n n b $ a a | ||
Burrows–Wheeler變換的還原過程
- 基於上述的BWT變換過程，以字符串「banana」為例，我們得到了變換結果「annb$aa」。其還原過程見以下過程：
- 1 基於原字符串矩陣的最後一列為「annb$aa」，我們進行該列進行排序，得到「$aaabnn」,並將其作為還原矩陣的第一列
| Burrows–Wheeler 還原過程 1 | |||||
|---|---|---|---|---|---|
| 輸入 | 轉移 | 排序 | 組合 | ||
- - - - - - a |
a - - - - - - |
$ - - - - - - |
$ - - - - - a | ||
- 2 經過1.1的轉移、排序和組合，我們得到了7對鄰接字符串：<a$> <na> <na> <ba> <$b> <an> <an>，將這7對鄰接字符串進行排序後，得到<$b> <a$> <an> <an> <ba> <na> <na>，由此，我們得到了還原矩陣的第二列「b$nnaaa」
| Burrows–Wheeler 還原過程 2 | |||||
|---|---|---|---|---|---|
| 輸入 | 轉移 | 排序 | 組合 | ||
$ - - - - - a |
a $ - - - - - |
$ b - - - - - |
$ b - - - - a | ||
- 3 經過1.2的轉移、排序和組合，我們得到了7對鄰接字符串：<a$b> <na$> <nan> <ban> <$ba> <ana> <ana>，將這7對鄰接字符串進行排序後，得到<$ba> <a$b> <ana> <ana> <ban> <na$> <nan>，由此，我們得到了還原矩陣的第三列「abaan$n」
| Burrows–Wheeler 還原過程 3 | |||||
|---|---|---|---|---|---|
| 輸入 | 轉移 | 排序 | 組合 | ||
$ b - - - - a |
a $ b - - - - |
$ b a - - - - |
$ b a - - - a | ||
- 4 經過1.3的轉移、排序和組合，我們得到了7對鄰接字符串：<a$ba> <na$b> <nana> <bana> <$ban> <ana$> <anan>，將這7對鄰接字符串進行排序後，得到<$ban> < a$ba > <ana$> < anan > < bana > < na$b > < nana >，由此，我們得到了還原矩陣的第四列「na$naba」
| Burrows–Wheeler 還原過程 4 | |||||
|---|---|---|---|---|---|
| 輸入 | 轉移 | 排序 | 組合 | ||
$ b a - - - a |
a $ b a - - - |
$ b a n - - - |
$ b a n - - a | ||
- 5 經過1.4的轉移、排序和組合，我們得到了7對鄰接字符串：<a$ban> <na$ba> <nana$> <banan> <$bana> <ana$b> <anana>，將這7對鄰接字符串進行排序後，得到<$bana> <a$ban> < ana$b > <anana> <banan> <na$ba> <nana$>，由此，我們得到了還原矩陣的第五列「anbana$」
| Burrows–Wheeler 還原過程 5 | |||||
|---|---|---|---|---|---|
| 輸入 | 轉移 | 排序 | 組合 | ||
$ b a n - - a |
a $ b a n - - |
$ b a n a - - |
$ b a n a - a | ||
- 6 經過1.5的轉移、排序和組合，我們得到了7對鄰接字符串：<a$bana> <na$ban> <nana$b> <banaan> <$banan> <ana$ba> <anana$>，將這7對鄰接字符串進行排序後，得到<$banan> <a$bana> < ana$ba> <anana$> <banana> <na$ban> <nana$b>，由此，我們得到了還原矩陣的第六列「naa$anb」。
| Burrows–Wheeler 還原過程 5 | |||||
|---|---|---|---|---|---|
| 輸入 | 轉移 | 排序 | 組合 | ||
$ b a n a - a |
a $ b a n a - |
$ b a n a n - |
$ b a n a n a | ||
經過六次排序轉移與組合，還原出了原有的字符串即「$banana」。
python實現(基於next值方式)
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的行
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)（頁面存檔備份，存於網際網路檔案館）