1. 概述
Burrows-Wheeler 变换 (BWT) 是一种算法，它重新排列字符串的字符以将相似的字符分组。 转换后的字符串更适合于 压缩。 该转换是可逆的，即可以重建原始字符串。
著名的 bzip2 工具使用 BWT 进行文件压缩。
在本教程中，我们将讨论 BWT 的工作原理。 我们将首先描述变换和逆变换。 然后，我们将通过一个示例来了解它的工作方式。
2. 变换如何工作？
在本节中，我们将看到变换及其逆变换。
2.1. 变换
要变换输入字符串，我们首先需要添加一个字符。 附加的字符不应存在于字符串中；它可以添加到字符串中的任何位置。 我们更喜欢将其添加到字符串的末尾以表示结束。
然后，我们循环移动字符串以获得所有可能的 循环移位。 如果字符串包含N个字符，包括添加的字符，那么所有循环移位的数量也是N。
最后，我们按字母顺序对输入字符串的所有循环移位进行排序并创建一个表格。 表格的最后一列是输入字符串的 BWT。 我们将把这个排序后的表格称为 BWT 表。
这是变换的伪代码
algorithm BWT(str):
// INPUT
// str = input string
// OUTPUT
// bwt = the BWT of str
str_with_eof <- append eof character to str
create a table whose rows are all possible circular shifts of str_with_eof
sort rows of the table alphabetically
bwt <- last column of the alphabetically sorted table
return bwt
我们获得 BWT 表的最后一列作为输入字符串的 BWT，因为相同的字符倾向于在这列中分组。 例如，当我们变换包含许多“the”冠词的英文长文本时，以“he”开头的排序后的循环移位将分组在一起。 因此，以“t”字符结尾的循环移位也将分组在一起。 压缩具有分组重复字符的字符串更容易。
使用 BWT 转换后的字符串可能不是最大可压缩的循环移位。 但是，我们可以重建由 BWT 转换的原始字符串，但不能使用其他循环移位来做到这一点。
2.2. 逆变换
我们可以使用一系列的添加和排序从转换后的字符串重建原始输入字符串。 我们可以通过对最后一列进行排序来重建 BWT 表的第一列，该列包含输入字符串的按字母顺序排序的循环移位。 最后一列是输入字符串的 BWT。 因此，我们获得 BWT 表的第一列和最后一列。
将第一列和最后一列组合起来并按字母顺序排序，可以重建 BWT 表的第一列和第二列。 然后，将输入字符串的 BWT 再次附加为一列，并对由三个字符组成的字符串进行排序，可以重建 BWT 表的前三列。 继续以相同的方式，我们最终重建了整个 BWT 表。 当然，该表中以我们之前添加的特殊字符结尾的字符串是原始输入字符串。
这是逆变换的伪代码
algorithm inverseBWT(bwt):
// INPUT
// bwt = a string transformed by the BWT() algorithm
// OUTPUT
// str = the original string
create an empty table
n <- length of bwt
for i <- 1 to n:
append bwt as a column to the table from the left side
sort the rows of the table alphabetically
str <- the row that ends with the eof character
return str without the eof character
3. 一个例子
在本节中，我们将首先使用 BWT 转换字符串 PEPPER。然后，我们将转换结果转换回原始字符串。
3.1. 转换
我们在字符串 PEPPER 的末尾添加美元符号 $，以指示字符串的结束。添加的字符可以是字符串中不存在的任何字符。
PEPPER$ 的所有循环移位及其排序后的对应项，即 BWT 表，如下表的第一列和第二列所示
| 循环移位 | 排序后的循环移位
(BWT 表) |
BWT（最后一列） |
|---|---|---|
| PEPPER$ | $PEPPER | R |
| $PEPPER | EPPER$P | P |
| R$PEPPE | ER$PEPP | P |
| ER$PEPP | PEPPER$ | $ |
| PER$PEP | PER$PEP | P |
| PPER$PE | PPER$PE | E |
| EPPER$P | R$PEPPE | E |
因此，输入字符串 PEPPER$ 的 BWT 是 RPP$PEE，这是 BWT 表的最后一列。我们在排序时假定 $ 的字母顺序小于其他字符。
在转换后的字符串中，存在由相同字符组成的两个组，即 PP 和 EE。然而，原始字符串中唯一的组是 PP。因此，即使对于这个简短的字符串，转换后的字符串更适合压缩。
当然，像 $PPPEER 这样的顺序更适合压缩，而不是 RPP$PEE。但是，无法使用 $PPPEER 重构 PEPPER$，而可以使用 RPP$PEE 重构它，正如我们将在下一小节中看到的。
3.2. 反向转换
下表列出了从转换后的字符串 RPP$PEE 重构原始字符串的前三个迭代的加法和排序过程
| 加法1 | 排序1 | 加法2 | 排序2 | 加法3 | 排序3 |
|---|---|---|---|---|---|
| R | $ | R$ | $P | R$P | $PE |
| P | E | PE | EP | PEP | EPP |
| P | E | PE | ER | PER | ER$ |
| $ | P | $P | PE | $PE | PEP |
| P | P | PP | PE | PPE | PER |
| E | P | EP | PP | EPP | PPE |
| E | R | ER | R$ | ER$ | R$P |
我们首先将转换后的字符串 RPP$PEE 添加到一个空表中。这对应于表中的 加法1 列。然后，我们对该列进行排序，得到 排序1 列。该列与 BWT 表的第一列相同。
我们通过组合两列，加法1 和 排序1，在 加法2 列中继续。然后，我们对 加法2 列进行排序，得到 排序2 列。该列与 BWT 表的前两列相同。
我们从将 加法1 列添加到 排序2 列开始第三次迭代。因此，我们得到 加法3 列。然后，我们对其进行排序以获得 排序3 列。该列与 BWT 表的前三列相同。
继续这样，我们最终构建了 排序7 列，它与 BWT 表相同
| 加法4 | 排序4 | 加法5 | 排序5 | 加法6 | 排序6 | 加法7 | 排序7 |
|---|---|---|---|---|---|---|---|
| R$PE | $PEP | R$PEP | $PEPP | R$PEPP | $PEPPE | R$PEPPE | $PEPPER |
| PEPP | EPPE | PEPPE | EPPER | PEPPER | EPPER$ | PEPPER$ | EPPER$P |
| PER$ | ER$P | PER$P | ER$PE | PER$PE | ER$PEP | PER$PEP | ER$PEPP |
| $PEP | PEPP | $PEPP | PEPPE | $PEPPE | PEPPER | $PEPPER | PEPPER$ |
| PPER | PER$ | PPER$ | PER$P | PPER$P | PER$PE | PPER$PE | PER$PEP |
| EPPE | PPER | EPPER | PPER$ | EPPER$ | PPER$P | EPPER$P | PPER$PE |
| ER$P | R$PE | ER$PE | R$PEP | ER$PEP | R$PEPP | ER$PEPP | R$PEPPE |
原始字符串是此表中以 $ 结尾的字符串。这对应于第四个字符串，PEPPER$。因此，原始字符串是 PEPPER。
4. 结论
在本文中，我们讨论了BWT的工作原理。
首先，我们了解到我们需要添加一个在我们要转换的字符串中不存在的字符。然后，我们构造字符串的所有循环移位并使用旋转后的字符串创建一个表格。然后，我们按字母顺序对表格的行进行排序。输入字符串的BWT是排序后表格的最后一列。
然后，我们学习了如何从转换后的字符串重建原始字符串。我们看到可以通过 N 次连续的添加和排序来重建原始字符串，其中 N 是字符串的BWT。
最后，我们使用一个例子应用了我们所学到的知识。