Burrows-Wheeler变换（BWT） - 存储数据

Question

使用BWT后，我们需要在编码数据中使用哪组数据？我们是否需要编码（或导出）后缀数组？

输入：

stackoverflow

BWT输出：

wtavrcfkle$soo

后缀数组：

13, 2, 3, 7, 9, 4, 10, 5, 11, 8, 0, 1, 6, 12

Answer 1

后缀数组只需要计算bwt变换，变换完成后就可以丢弃。

BWT("stackoverflow")="wtavrcfkle$soo" 

UNBWT("wtavrcfkle$soo")="stackoverflow" 

您也可以恢复从转换输出的后缀数组，如果你喜欢:)

Answer 2

所有你需要反转跨表单是输出字符串（在您的示例中为wtavrcfkle$soo）。

Answer 3

您只需要传输BWT输出。

这个转换令人惊讶的是，原始字符串可以从排列后的输出字符串重建。

wikipedia article包含用于做这个反演的示例代码。

请注意，正常操作模式是使用运行长度编码在传输之前对BWT输出进行编码（或者您尚未实现任何压缩）。

转换的好处在于，它倾向于产生相似字符的长时间运行（如果源材料中存在结构）并且运行长度编码运行良好。

Answer 4

要反转BWT，只需要原始最后一个字符的索引，而不是整个后缀数组。如果你没有这个索引，我相信选择一个任意索引会导致原始字符串的旋转版本。

需要注意的是，如果包括结束行的代码（如你的例子），原来的最后一个字符是显而易见的，因此指数并不需要单独提供...

Answer 5

需要明确的是，后缀阵列和BWT输出是一样的。如果您查看示例中的后缀数组，它包含从BWT输入（从1开始）获取的BWT输出中字母的索引：13 - > w，2 - > t，3 - > a等。 .. 使用后缀数组只是一种计算线性时间内BWT输出的机制。传输后缀数组或BWT输出意味着传输相同的信息。