使用 BWT 后，我们在编码数据中需要哪组数据？我们是否需要编码（或导出）后缀数组？
输入：
stackoverflow
BWT 输出：
wtavrcfkle$soo
后缀数组：
13, 2, 3, 7, 9, 4, 10, 5, 11, 8, 0, 1, 6, 12
问问题
328 次
5 回答
1
反转转换所需的只是输出字符串（wtavrcfkle$soo在您的示例中）。
于 2013-05-03T18:09:21.750 回答
1
您只需要传输 BWT 输出。
这种转换令人惊讶的是，原始字符串可以仅从排列后的输出字符串中重构出来。
维基百科文章包含执行此逆向的示例代码。
请注意，正常的操作模式是在传输之前使用游程编码对 BWT 输出进行编码（或者您没有实现任何压缩）。
转换的好处是它倾向于产生类似字符的长时间运行（如果源材料中有结构），因此运行长度编码效果很好。
于 2013-05-03T18:09:32.807 回答
1
要反转 BWT，您只需要原始最后一个字符的索引，而不是整个后缀数组。如果您没有此索引，我相信选择任意索引将导致原始字符串的旋转版本。
请注意，如果您包含行尾代码（如您的示例中），则原始最后一个字符很明显，因此不需要单独提供索引...
于 2013-05-03T18:18:13.363 回答
1
后缀数组只需要计算 bwt 变换，变换完成后它可以被丢弃。
BWT("stackoverflow")="wtavrcfkle$soo"
UNBWT("wtavrcfkle$soo")="stackoverflow"
如果您愿意，还可以从转换后的输出中恢复后缀数组：)
于 2013-05-03T18:19:08.397 回答
0
需要明确的是，后缀数组和 BWT 输出是一回事。如果您查看示例中的后缀数组，它包含从 BWT 输入（从 1 开始）获取的 BWT 输出中字母的索引：13 -> w、2 -> t、3 -> a 等。 .. 使用后缀数组只是一种以线性时间计算 BWT 输出的机制。传输后缀数组或 BWT 输出意味着传输相同的信息。
于 2013-12-04T06:26:50.040 回答