Burrows-Wheeler变换
维基百科,自由的 encyclopedia
Burrows–Wheeler Transform(简称BWT,也称作块排序压缩),是一个被应用在数据压缩技术(如bzip2)中的算法。该算法于1994年被Michael Burrows(英语:Michael Burrows)和David Wheeler(英语:David Wheeler)在位于加利福尼亚州帕洛阿尔托的DEC系统研究中心(英语:DEC Systems Research Center)发明[1]。它的基础是之前Wheeler在1983年发明的一种没有公开的转换方法。
当一个字符串用该算法转换时,算法只改变这个字符串中字符的顺序而并不改变其字符。如果原字符串有几个出现多次的子串,那么转换过的字符串上就会有一些连续重复的字符,这对压缩是很有用的。该方法能使得基于处理字符串中连续重复字符的技术(如MTF变换和游程编码)的编码更容易被压缩。
举个例子:
More information 算法输入, 算法输出 ...
算法输入 | SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES |
---|---|
算法输出 | TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT |
Close
该算法的输出因为有更多的重复字符而更容易被压缩了。