Burrows - Wheeler Data Transform Algorithm in Java

理解 Burrows-Wheeler 变换

为了改进数据压缩，一种称为Burrows-Wheeler 变换 (BWT) 的数据变换技术重新排列字母字符串。这种由Michael Burrows 和 David Wheeler 创建的方法通常用于预处理数据，以便压缩方法能够更好地处理它。

BWT 如何工作？

BWT 的主要目标是重新组织字符串，使相似的字符聚集在一起。这种聚集有利于更有效的编码方法，这些方法可以利用数据中的重复模式。

BWT 最重要的特点是变换是可逆的。这意味着修改后的版本可以用于重建原始字符串，而不会丢失任何信息。

BWT 示例

让我们看一个示例字符串：“BANANA$”。BWT 将此 字符串 转换为“ANNB$AA”。请注意相似的字符是如何分组在一起的，从而提高了压缩效率。

BWT 的工作原理

应用 Burrows-Wheeler 变换的过程包括以下步骤：

1. 追加终止符：在输入字符串中添加一个唯一的字符串结束字符（通常是 $）。这有助于在重建过程中确定字符串的结尾，并确保变换是可逆的。

2. 创建旋转：使用循环字符移位来创建输入字符串的每个旋转。

3. 对旋转进行排序：按字典序（字母顺序）对这些旋转进行排序。对于“BANANA$”，排序后的旋转是

4. 形成变换后的字符串：取每个排序后的旋转的最后一个字符，形成变换后的字符串。对于上面的排序旋转，最后一个字符是

因此，变换后的字符串是：“ANNB$AA”。

此变换后的字符串是 BWT 算法的输出。请注意相似的字符（“A”和“N”）是如何分组在一起的。

反向变换

BWT 的美妙之处在于其可逆性。可以从变换后的版本（“ANNB$AA”）重建原始字符串。这可以通过以下步骤完成：

1. 创建表：从一个空表开始，每行对应变换后的字符串中的每个字符。通过将变换后的字符串作为新列添加到每行前面并迭代地填充此表，并在每次添加后对表进行排序。
2. 重建原始字符串：一旦表被完全填充，包含字符串结束标记（$）的行就是原始字符串。

使用 BWT 的优点

BWT 在数据压缩方面很有用，因为它将相似的字符分组在一起，这对于行程长度编码和其他压缩算法非常有益。一些优点包括：

• 效率：通过对相似字符进行分组，提高了 Huffman 编码和算术编码等熵编码方法的效率。
• 适应性：BWT 不与任何特定的压缩技术绑定；它可以与各种方法结合使用，如移至前端 (MTF) 编码、行程长度编码等。

让我们在 Java 程序中实现 BWT 逻辑。

文件名：BurrowsWheelerTransform.java

输出

 
BWT: ANNB$AA
Original: BANANA$   

这验证了 Burrows-Wheeler 变换及其逆变换正在按预期工作。

代码解释

1. bwt() 方法
   
   • 此方法接受输入字符串并生成其所有旋转（通过移位字符）。
   • 然后，它使用 `Arrays.sort()` 按字典序对这些旋转进行排序。
   • 提取排序后的旋转的最后一列以形成变换后的字符串。
2. inverseBWT() 方法
   
   • 此方法接受 BWT 字符串并重建原始字符串。
   • 它通过将变换后的字符串作为新列添加到每行前面来迭代地构建一个表，并在每次添加后对表进行排序。
   • 包含终止符（$）的行作为原始字符串返回。
3. main() 方法
   
   • main 方法使用示例字符串“BANANA$”测试 BWT 及其逆变换。
   • 它同时打印变换后的原始字符串和重建的原始字符串。

BWT 的应用

Burrows-Wheeler 变换在数据压缩方面有多种实际应用：

• bzip2 压缩算法：bzip2 压缩工具的一个基本部分是 BWT。为了获得高压缩率，它与其他方法（如 Huffman 编码、行程长度编码和移至前端 (MTF) 编码）协同工作。
• 基因组数据压缩：BWT 在 生物信息学 中用于高效压缩基因组数据。通过对相似序列进行分组，可以更有效地存储和检索基因组信息。
• 搜索应用程序：BWT 在全文搜索应用程序中也很有用，可以在其中预处理文本。这种预处理可以提高搜索操作的速度和效率。

结论

总之，Burrows-Wheeler 变换是一种有效的工具，具有重要的数据压缩意义。它通过将字符串转换为更有条理的格式来提高多种压缩技术的效率，使其成为许多领域中的关键方法。

提供的 Java 实现演示了如何执行 BWT 及其逆变换，确保对该算法的工作原理有深入的理解。