Burrows-Wheeler變換

Burrows–Wheeler Transform（簡稱 BWT，嘛叫做塊排序壓縮）， 是一个予人應用佇數據壓縮技術（如 bzip 二）中的算法。該當是一九九四年被 Michael Burrows 和 David Wheeler 佇咧加利福尼亞州帕洛阿爾托的 DEC 系統研究中心發明。伊的基礎是進前 Wheeler 佇一九八三年發明的一種無公開的轉換方法。

做一个字符串用該算法轉換的時陣，算法干焦改變這字符合串中字符仔的順序並無改變其字符仔。若這原字符捾有幾若改出現濟改，遐爾轉換過的字符串頂懸就會有一寡連紲重複的字符，這對壓縮是足有路用的。這个方法會當予因為處理字符合連紲重複字符的技術（如 MTF 變換佮遊程編碼）的編碼閣較容易予人壓縮著。

比一个例：

該算法的輸出因為有閣較濟的重複字符仔閣較會去予人壓縮去。

Burrows–Wheeler 變換過程

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

Burrows–Wheeler 換的閣原過程

• 是因為上述的 BWT 變換過程，以字符符合「banana」做例，咱得著矣變換結果「annb $ aa」。 其他的過程見以下過程：

一 . 是因為原字符串矩陣的上尾仔一列做「annb $ aa」，咱進行該列進行排序，得著「$ aaabnn」, 嘛共其做為還原矩陣的第一列一列 . 二經過一刀一的轉移、排序佮組合，咱得著七對鄰接字符串：< a $ > < na > < na > < ba > < $ b > < an > < an >，共這七對鄰接字符合來做排序了後，得著 < $ b > < a $ > < an > < an > < ba > < na > < na >，由此，咱得著矣還原矩陣的第二列「b $ nnaaa」 一 . 三經過一鋪二的轉移、排序佮組合，咱得著七對鄰接字符串：< a $ b > < na $ > < nan > < ban > < $ ba > < ana > < ana >，共這七對鄰接字符合來做排序了後，得著 < $ ba > < a $ b > < ana > < ana > < ban > < na $ > < nan >，由此，咱得著矣還原矩陣的第三列「abaan $ n」 一 . 四經過一鼻三的轉移、排序佮組合，咱得著七對鄰接字符串：< a $ ba > < na $ b > < nana > < bana > < $ ban > < ana $ > < anan >，共這七對鄰接字符合來做排序了後，得著 < $ ban > < a $ ba > < ana $ > < anan > < bana > < na $ b > < nana >，由此，咱得著矣還原矩陣的第四列「na $ naba」 一 . 五經過一爿四的轉移、排序佮組合，咱得著七對鄰接字符串：< a $ ban > < na $ ba > < nana $ > < banan > < $ bana > < ana $ b > < anana >，共這七對鄰接字符合來做排序了後，得著 < $ bana > < a $ ban > < ana $ b > < anana > < banan > < na $ ba > < nana $ >，由此，咱得著矣還原矩陣的第五列「anbana $」 一 . 六經過一刀五的轉移、排序佮組合，咱得著七對鄰接字符串：< a $ bana > < na $ ban > < nana $ b > < banaan > < $ banan > < ana $ ba > < anana $ >，共這七對鄰接字符合來做排序了後，得著 < $ banan > < a $ bana > < ana $ ba > < anana $ > < banana > < na $ ban > < nana $ b >，由此，咱得著矣還原矩陣的第六列「naa $ anb」。

經過六改排序轉移佮組合，閣原出了原有的字符串即「$ banana」。

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

通過佇尾溜咧添加唯一字符 ( 無和輸入字串中任何字符相仝 ) 了後才閣進行變換，會當無需要傳遞索引值列表，毋過顛倒變換的時陣愛做閣較濟計算。

下跤的偽代碼提供一个逆過程的素實現（輸入字符串 s 為原過程之輸出）：

` ` ` functioninverseBWT ( _ string _ s ) 生成 length（s）個空串 repeatlength ( s )times 鋪字符串 s 做吐一列插入每一字符串的串頭歕所有的字符合排序倒轉去塗尾溜 EOF 的行 ` ` `

外部連結

• 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-v 一垺五 . 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 )