问题标签 [burrows-wheeler-transform]

似乎许多实现 BWT 的压缩器将它与算术编码或霍夫曼编码结合使用。（随意提名更多，特别是如果他们更好的话。）

我的第一个问题是：为什么像 LZW 或 LZSS 这样的字典编码器与 BWT 一起使用是更糟糕的选择？

我的第二个问题是：哪个是最好的全能算法？

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

输入：

stackoverflow

BWT 输出：

wtavrcfkle$soo

后缀数组：

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

如果我们将其aaabccba视为输入字符串，baaacacb则将是对输入应用 Burrows-Wheeler 变换后的输出字符串。观察输出你会发现两个聚集在一起c是分开的。很明显，输入字符串会比输出产生更好的压缩效果。

如何决定是否对输入字符串应用 Burrows-Wheeler 变换？我们可以做一些快速分析来做出决定吗？

Burrows-Wheeler Aligner (BWA)，一种将短核苷酸序列映射到参考基因组的生物信息学工具（算法）。我尝试使用 Hadoop Streaming 运行 BWA，但出现错误。

命令：

错误信息：

请建议如何解决这个问题？谢谢你的帮助。

我正在尝试找到最快的算法来进行前端转换。例如与 burrows Wheeler 变换结合使用的那个。

到目前为止，我在 Core i3 2.1GHz 上管理的最好速度约为 15MB/s。但我确信这不是最佳的。这是我迄今为止的最大努力。有什么更快的吗？

如何在 Clojure 中为Burrows-Wheeler 变换惯用地旋转字符串？

我想出了这个，它使用(cycle "string")，但感觉有点必要：

我不确定这是否符合代码高尔夫的条件。有没有更清洁的方法来做到这一点？

我已经成功地为我正在编写的压缩测试平台实现了 BWT 阶段（使用常规字符串排序） 。我可以应用 BWT，然后应用 BWT 逆变换，输出与输入匹配。现在我想使用后缀数组加快 BW 索引表的创建。我发现了 2 个相对简单的，据说是快速的 O(n) 后缀数组创建算法，DC3和SA-IS，它们都带有 C++/C 源代码。我尝试使用源（开箱即用的编译 SA-IS 源也可以在此处找到），但未能获得正确的后缀数组/BWT 索引表。这是我所做的：

1. T=输入数据，SA=输出后缀数组，n=T的大小，K=字母大小，BWT=BWT索引表

2. 我使用 8 位字节，但两种算法都需要一个零字节形式的唯一哨兵/EOF 标记（DC3 需要 3，SA-IS 需要一个），因此我将所有输入数据转换为 32 位整数，增加所有符号加 1 并附加标记零字节。这是T。

3. 我创建了一个整数输出数组 SA（DC3 的大小为 n，KA-IS 的大小为 n+1）并应用算法。我得到的结果类似于我的排序 BWT 变换，但有些值是奇数（参见更新 1）。两种算法的结果也略有不同。SA-IS算法在前面产生了一个多余的索引值，所以所有的结果都需要向左复制一个索引（SA[i]=SA[i+1]）。

4. 要将后缀数组转换为正确的 BWT 索引，我从后缀数组值中减去 1，进行模运算并且应该具有 BWT 索引（根据此）： BWT[i]=(SA[i]-1)%n .

这是我提供 SA 算法并转换为 BWT 的代码。您应该能够或多或少地插入论文中的 SA 构造代码：

我究竟做错了什么？

更新 1
将算法应用于少量测试文本数据时，例如“yabbadabbado”/“这是一个测试”。/“abaaba”或一个大文本文件（来自坎特伯雷语料库的alice29.txt ）它们工作正常。实际上 toBWT() 函数甚至不是必需的。
将算法应用于包含完整 8 位字节字母表（可执行文件等）的文件中的二进制数据时，它们似乎无法正常工作。将算法的结果与常规 BWT 索引的结果进行比较，我注意到前面有错误的索引（在我的例子中为 4）。索引的数量（顺便说一句？）对应于算法的递归深度。索引指向原始源数据最后出现 0 的位置（在构建 T 时将它们转换为 1 之前）...

更新 2
当我对常规 BWT 数组和后缀数组进行二进制比较时，会有更多不同的值。这可能是意料之中的，因为公平排序不一定与标准排序相同，但由数组转换的结果数据应该相同。它不是。

更新 3
我尝试修改一个简单的输入字符串，直到两个算法都“失败”。更改字符串“这是一个测试”的两个字节后。到 255 或 0（从 746869732069732061 20 74657374 2E h 到例如 746869732069732061 FF 74657374 FF h，最后一个字节必须更改！）索引和转换后的字符串不再正确。将字符串的最后一个字符更改为字符串中已经出现的字符似乎也足够了，例如“这是一个测试”7468697320697320612074657374 73 h。然后转换后的字符串的两个索引和两个字符将交换（比较使用 SA 的常规排序 BWT 和 BWT）。

我发现必须将数据转换为 32 位的整个过程有点尴尬。如果有人有更好的解决方案（论文，更好的是一些源代码）来直接从具有 256 个字符字母的字符串生成后缀数组，我会很高兴。

通常在 Burrows-Wheeler 变换算法中，使用 $ 字符来表示字符串的结束，但在很多情况下，这个 $ 被省略了。

我想知道如何在不知道最后一个字符的位置的情况下反转它？

例如，我有这个 BWT：

[[[[[1[[11endgnad1234245ndbnbbb]]]]]]]nnnngnabbbdiaaaaaaii

按照该算法，我可以轻松地构造 BWT 矩阵的第一列，我选择以压缩方式表示，如下所示：

在不知道原始字符串中的最后一个字符的情况下，我无法看到如何重建原始字符串。

任何帮助是极大的赞赏。唐

P/S：如果您想知道原始字符串是什么：

[1]ban[2]banana[3]band[4]bandage[12]bin[14]bind[15]绑定

以上是我目前在 Lua 中实现 BWT 编码的代码。问题是由于表的大小和循环的长度，它需要很长时间才能运行。对于 1000 个字符的输入，平均编码时间约为 1.15 秒。有人对制作更快的 BWT 编码功能有建议吗？

最大的放缓似乎出现在 fLexTblSort 和 fShallowCopy 中。我也将两者都包含在 BWT 函数之上。

I'm studying a Burrows-Wheeler transformation and so far I can get it from some Text. Now it's time for the reverse process and that's what I have trouble with.

Here's the input: TTCCTAACG$A.

That's my way of thinking:

1) compute the number of As, Cs, Gs, Ts in the input: A: 3, C: 3, G: 1, T: 3

2) let's write down the First and the Last column of Burrows-Wheeler transformation. The last column is our input. So here it is:

Here's my logic:

1. Initially, output = '$'
2. L[0] = 'T' => output = 'T$'
3. The first T in F has the index 8 => we need L[8] => output = 'GT$'
4. The first G in F has the index 7 => we need L[7] => output = 'CGT$'
5. The first C in F has the index 4 => we need L[4] => output = 'TCGT$'
6. It was our second T. The second T in F has the index 9, but L[9] = '$', thus
   we should stop.

Obviously, it's not over and something's wrong here. Could you please explain what?