Burrows-Wheeler变换

Burrows–Wheeler Transform（简称BWT，也称作块排序压缩），是一个被应用在数据压缩技术（如bzip2）中的算法。该算法于1994年被和在位于加利福尼亚州帕洛阿尔托的发明。它的基础是之前Wheeler在1983年发明的一种没有公开的转换方法。 当一个字符串用该算法转换时，算法只改变这个字符串中字符的顺序而并不改变其字符。如果原字符串有几个出现多次的子串，那么转换过的字符串上就会有一些连续重复的字符，这对压缩是很有用的。该方法能使得基于处理字符串中连续重复字符的技术（如MTF变换和游程编码）的编码更容易被压缩。 举个例子： 该算法的输出因为有更多的重复字符而更容易被压缩了。