BWT

Blind write 5生成的鏡像文件為B5T+B5I，Blind write 6生成的鏡像文件為B6T+B6I。

在windows下可以使用WinMount打開BWT格式的文件。

Burrows-Wheeler變換

在數據壓縮領域最近時間一個比較有趣的發展就是1994年 Michael Burrows 和 David Wheeler在《A Block-sorting Lossless Data Compression Algorithm》一文中共同提出了一種全新的通用數據壓縮演演算法，Burrows-Wheeler Transformation[5,8,10,13]。

1、原理

與ziv和lempel另闢蹊徑的做法如出一轍，burrows和wheeler設計的bwt演演算法與以往所有通用壓縮演演算法的設計思路都迥然不同。現有比較著名的壓縮演演算法都是處理數據流模型的，一次讀取一個或多個位元組，BWT使得處理成塊的數據成為可能。這種演演算法的核心思想是對字元串輪轉后得到的字元矩陣進行排序和變換。考慮一般的文本應用比如英語文本中the這個字元串經常會被用到，經過BW轉換之後，所有的t都被移動到最後並且聚合在一起，這樣變換之後的字元串用通用的統計壓縮模型(Huffman coding、LZ演演算法、PPM演演算法)等進行壓縮就能得到更好的壓縮比。

1.1、壓縮變換

為了方便闡述，我們假設輸入的字元串為S='abraca'，字元串長度N=6。

我們把字元串S循環移位后得到的字元串集合組合成一個N*N的矩陣。至少有一行包含了初始的字元串，I是第一行所在的序號。例子里變換后的矩陣M如下圖，I=1.

row

0 aabrac

1 abraca

2 acaabr

3 bracaa

4 caabra

5 racaab

圖6.1 變換后的矩陣

注意，這裡是 將輪轉之後的6個字元串按字典序進行排序過的。

假定L是矩陣M的最後一列，例子中L='caraab'，I=1；

1.2、解壓變換

解壓變換利用壓縮變換的結果L和I重新構建原有的字元串。output(L,I)=S(N)

我們首先要找到矩陣M中的第一列F，這裡只要把最後一列L進行排序就能得到。例子中F='aaabcr'；（每一列都是原字元串的一個排列，而矩陣M是把各行按照字典序排列的，哪個每一行的第一個字元也應該是有序的。）

首先要申明的是在壓縮和解壓過程中，我們並不知道矩陣M，我們有的信息只是L,F,I，需要從中構建出原始的字元串S。

考慮我們上面的例子，我們定義另外一個矩陣M'，其中M'中的每行是M中每行循環右移一位（如圖6-2）。M'[i,j] = M[i,(j-1)mod N];

row M M'

0 aabrac caabra

1 abraca aabrac

2 acaabr racaab

3 bracaa abraca

4 caabra acaabr

5 racaab bracaa

圖6-2 M和M'矩陣

這裡需要指出的是M'的每一行也都是字元串S的一個變換。因為M'是從M轉換過來的，也就是說M'是按照第二列進行嚴格排序過的。對於在M'中以某字元ch開頭的那些行，他們出現的相對位置也應該是嚴格排好序的（他們以第二個字元進行排序，而且他們的第一個字元都相等，不會影響排序的結果）。也就是說在M中以ch字元開始的行出現的相對順序和M'中以ch字元出現的相對順序應該是一樣的。比如例子中字元串'aabrac'，　'abraca'，'acaabr'在M中的順序是0,1,2，在M'中的順序是1,3,4。

F和L分別是矩陣M和M'的第一行，我們按照M'的第j行和M中的第T[j]行相同構建一個向量T。向量T就可表示兩個矩陣之間的轉換關係。例子中T=(4,0,5,1,2,3)。

其實，我們對M'進行字典序排序，就會轉化為M。轉變過程僅僅是行變換。

我們可以發現F和L分別是矩陣M的第一列和最後一列，而且其中的每一行都是S的一個變換，有L[i]肯定在F[i]前面。從T的構照中我們可以得出F[T[j]]=L[j]，我們把前面的i用T[j]代替，就有L[T[j]]在L[j]之前。由假設中I是第一行的序號，那麼L[I]就是最後一個字元，我們根據矩陣T依次找到字元的前序就可以構建整個初始化的字元串了。T0[x]=x，Ti+1[x]=T[Ti[x]]。

2、應用效果

如今， bwt演演算法在開放源碼的壓縮工具bzip中獲得了巨大的成功，bzip對於文本文件的壓縮效果要遠好於使用 lz系列演演算法的工具軟體。這至少可以表明，即便在日趨成熟的通用數據壓縮領域，只要能在思路和技術上不斷創新，我們仍然可以找到新的突破口。

以推動整個壓縮技術的不斷前進。