问题标签 [burrows-wheeler-transform]

我在掌握 Burrows Wheeler 变换 (BWT) 的解码算法时遇到了困难。我已经在线阅读并浏览了一些示例代码，但是，它们似乎都在使用“主索引”来解码编码字符串。

我的问题是，我们如何将像“rdacraaaabb”这样的 BWT 编码字符串解码为其原始的“abracadabra”。

一些示例代码会很棒。

您好，我在优化burrows Wheeler 变换时遇到了一些困难。我正在尝试转换文本文件，但是转换像圣经这样的大文本文件需要的时间太长了。

关于如何进行的任何想法？

我正在阅读 Burrows 和 Wheeler 论文中的块排序算法。这是算法的一个步骤：

假设 S=abracadabra

初始化一个包含 N 个单词 W[0, ... , N - 1] 的数组 W，使得 W[i] 包含字符 S'[i, ... , i + k - 1] 的排列，以便整数比较这些词与 k 字符串的字典比较一致。将字符打包成单词有两个好处：它允许使用对齐的内存访问一次比较两个前缀 k 字节，并且它允许消除许多缓慢的情况

（注意：S'是原始的，附加S了 kEOF个字符，k 是适合机器字的字符数（我在 32 位机器中，所以k=4）

如我错了请纠正我：

然后，算法说你必须通过索引S数组来对（命名为 V）的后缀数组进行排序。W

我不完全理解如何通过索引来对后缀进行排序W。例如：在排序的某个时刻，假设你有两个后缀，i和j，你必须比较它们。由于您正在索引W，因此您当时正在检查 4 个字符。
假设它们具有相同的前 4 个字符。然后，您必须检查每个后缀的下一个 4 个字符，并通过从W. 这是正确的吗？这种“将字符打包成单词”真的可以加快速度吗？

我正在尝试实现块排序。这是来自 Burrows Wheeler 的论文。

（在此步骤之前，您创建一个 S 的 V 后缀数组）

Q4。[基数排序]
对 V 的元素进行排序，使用每个后缀的前两个字符作为排序键。这可以使用基数排序有效地完成。

所以我知道您正在使用基数排序对后缀进行排序。
这应该如何更新数组 V？只有在基数排序完成后，我才能知道后缀的排序位置。假设第 4 个后缀最终成为排序后的第一个。所以 V[0] = i。在这种情况下，我们知道（因为我告诉过你）i = 4。但是算法如何知道这一点，因为我们没有跟踪它们的位置。我应该创建一个包含后缀及其后缀编号的类吗？

我正在尝试使用 Java 编写带有 Huffman 压缩程序的BWT 。在BWT中，我想实现距离编码 (DC)。我正在寻找一些例子，但没有那么多。

我找到了这个例子：

http://www.cs.ucr.edu/~stelo/cpm/cpm07/move_to_front_gagie.pdf

DC 从 29 页开始。但这真的很难理解，因为没有评论。

也许有人已经实现了 DC 或知道如何在实际代码中实现它的理论？:)

我理解首先需要写出 char 是什么的那部分。但后来随着距离我没有得到它。

我红色的是，对于每个字符，DC 在序列中找到它的下一个出现并将其写入 S 并输出到它的距离。如果没有出现，则写 0。

谢谢。

我需要在线性时间内执行著名的 Burrows-Wheeler 变换。我找到了一个带有后缀排序和 EOF 字符的解决方案，但是附加 EOF 会改变转换。例如：考虑字符串bcababa 和两个旋转

• s1 =abababc
• s2 =ababcab

很明显 s1 < s2。现在使用 EOF 字符：

• s1 = ababa#bc
• s2 = aba#bcab

现在 s2 < s1。并且由此产生的转变会有所不同。如何在没有 EOF 的情况下执行 BWT？

在对“abracdabra!”的输入文本进行转换后，我的转换向量是 [3, 0, 5, 6, 7, 9, 10, 8, 2, 1, 4]，然后将文本通过管道进行更多的转换和压缩到磁盘。

关闭程序后，我们显然无法再访问变换向量了。我们是否希望将转换向量写入磁盘？向量的大小实际上不等于 n 个字符吗？这实际上不会增加​​压缩文件的大小吗？

我一直在尝试在wikipedia上重新创建 Burrows-Wheeler 变换的示例。为了增加乐趣，我试图通过递归策略来做到这一点。但是，我陷入了第一步，创建了字符串的所有旋转。这是我的代码：

这会生成以下输出：

这类似于维基百科的例子，但不完全相同，我似乎无法弄清楚为什么。根据示例，输出应如下所示：

我已经盯着这个有一段时间了，虽然问题应该是相当直接的，但我似乎无法弄清楚。你能看出我做错了什么吗？

我尝试在 burrow Wheelers 循环字符串数组中旋转一个非常大的字符串。

但是我的输入大约是 200000 个字符，当输入这么大时，我无法运行代码，因为它用完了堆空间。

我的教授说实现它的唯一方法是线性内存占用。我不知道这意味着什么。

我能知道还有什么其他方法可以创建一个内存高效的循环字符串并在不耗尽内存的情况下使用它吗

我是编码新手，所以我试图了解基础知识。我遇到了一个描述无损文本压缩技术的文档，在这个文档中，有一张图说明了他们的压缩是如何工作的。它是这样工作的：

我不明白为什么他们会在 Move to Front Transform 之后使用 Run-Length Transform，这对我来说似乎效率不高。据我了解，MTF 本身不会产生很多运行，因此使用 RLT 后记没有用。

一些解释将不胜感激！