目录:
定义-Burrows-Wheeler变换（BWT）是什么意思？
Burrows-Wheeler变换（BWT）是一种算法，该算法获取数据块（例如字符串），并将其重新排列成类似字符的行。 转换后，输出块在开始之前包含相同的确切数据元素，但是顺序不同。 该算法的性质倾向于将相似的字符彼此相邻放置，从而使所得到的数据顺序更易于压缩。 因此，它被用于许多压缩算法中。
Techopedia解释了Burrows-Wheeler变换（BWT）
Burrows-Wheeler变换算法是Michael Burrows和David Wheeler于1994年发明的相对较新的算法，它基于Wheeler在1983年发现的未公开的变换，该变换发表在他们的论文“一种块分类无损数据压缩算法”中。
在最基本的情况下，BWT会获取一个数据块（例如字符串），添加一个EOF字符，然后将该字符串的所有旋转顺序按字典顺序排序。 以下伪代码或步骤说明了该算法：
- 创建一个表，该表包含表示字符串的所有可能的一增量旋转的行。
- 按字母顺序对所有行进行排序。
- 输出表的最后一列。
例如：“香蕉”一词； 添加EOF字符会将其转换为“ banana $”，然后我们应用以下算法：
1.创建一个表，其中的行表示所有可能的旋转：
香蕉$
anana $ b
娜娜$ ba
ana $ ban
na $ bana
a $ banan
$香蕉
2.根据第一列的字母顺序/字典顺序对行进行排序：
$香蕉
a $ banan
ana $ ban
anana $ b
香蕉$
娜娜$ ba
na $ bana
3，返回最后一列作为BWT输出：annb $ aa
生成的字符串更易于压缩，因为重复的字符彼此相邻。 但是需要将其他数据与转换后的数据一起存储，以便可以进行反向转换。 即使生成的转换数据大于其原始形式，但其可压缩性却提高了许多倍，从根本上使其成为提高压缩方法效率的“免费”方法。
