BWT变换及其应用

Burrows-Wheeler变换及其应用

引言

在数学中，经常需要对研究的对象做一些变换，使得问题的处理变得更简单，例如最常见的Fourier变换可以将信号从时域信号变换为频域信号。Burrows-Wheeler变换（后面简称BWT）也是一种变换，它接收一个串，输出一个变换后的串，BWT最开始被用在压缩算法，后来在index上也有很重要的应用。

BWT的过程

step1：产生所有输入串的循环串

假设$字符是输入串的结尾
下面给个例子： 若输入串是banana$
则这个串的所有的循环串为：
b a n a n a $
a n a n a $ b
n a n a $ b a
a n a $ b a n
n a $ b a n a
a $ b a n a n
$ b a n a n a
实现这个过程的python代码如下:

def rotate(s):
'''string -> [string] '''
	ss = s*2
	return [ss[i:i+len(s)] for i in range(len(s)]

step2

对上面产生的循环串按字典序排序 （$的ASCII码比字母小，可以认为在字典序中最小)
则上面排序后的串为:

$ 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

step3

将排序后的数组的最后一列作为变换后的串输出：
即：a n n b $ a a

BWT(banana$) = annb$aa

为什么BWT可以实现压缩

从上面的例子可以看到，如果有重复的字串（上例中的nana),则重复字串中的字符也必定重复，则这些重复的字符在变换后的串中都尽可能的挤压在一起，所以当这种挤压相同字符挤压在一起的个数很多时显然可以做到有效的压缩。
当然BWT之后的字符串可以做到压缩存储的前提是从BWT(T)能转换到T，下面将证明这一性质成立并且给出过程。

BWT的逆过程

逆过程能够实现基于下面的事实:

• BWT(S) 和 S只是顺序上的不同，没有字符丢失或增加
• 由字典序排序从最后一列可以得到第一列
• 由第一列和最后一列可以得到 n对相邻的字符，继而可以得到第2列，继续这一过程可以恢复整个原始串

mark 留坑以后再填