标签: burrows-wheeler-transform

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

假设S = abracadabra

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

(注意:S'是附加S了k个EOF字符的原件,k是适合机器字的字符数(我是32位机器,所以k=4)

EOF = '$'

如我错了请纠正我:

S'= abracadabra$$$$  
W= abra brac raca acad cada adab dabr abra bra$ ra$$ a$$$

然后,算法说你必须S通过索引到数组W来对后缀数组(名为V)进行排序.

我不完全明白你如何通过索引来排序后缀W.例如:在分选的某一点,假设你得到两个后缀,i并且j,你必须对它们进行比较.由于您正在编入索引W,因此您当时要检查4个字符.
假设它们具有相同的前4个字符.然后,您必须检查每个后缀的下4个字符,并通过从每个后缀的第4个位置访问来完成W.这是正确的吗？这种"将字符包装成文字"真的能加快速度吗？

我成功地为我正在编写的压缩测试平台实现了一个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 +)并应用算法.我得到的结果类似于我的排序BWT变换,但有些值是奇数(见更新1).两种算法的结果也略有不同.SA-IS算法在前面产生一个超额索引值,因此所有结果都需要被一个索引(SA [i] = SA [i + 1])左侧复制.

4. 要将后缀数组转换为正确的BWT索引,我从后缀数组值中减去1,做一个模数并且应该有BWT索引(根据这个):BWT [i] =(SA [i] -1)%n .

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

std::vector<int32_t> SuffixArray::generate(const std::vector<uint8_t> & data)
{
    std::vector<int32_t> SA;
    if (data.size() >= 2)
    {
        //copy data over. we need to append 3 zero bytes, 
        //as the algorithm expects T[n]=T[n+1]=T[n+2]=0
        //also increase the symbol value by 1, because the algorithm alphabet is [1,K]
        //(0 is …

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

• s1 = abababc
• s2 = ababcab

很明显,s1 <s2.现在有了EOF字符:

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

现在s2 <s1.由此产生的转变将是不同的.如何在没有EOF的情况下执行BWT？

bzip2（即Julian Seward 的这个程序）列出了 100k 到 900k 之间的可用块大小：

 $ bzip2 --help
 bzip2, a block-sorting file compressor.  Version 1.0.6, 6-Sept-2010.

 usage: bzip2 [flags and input files in any order]

   -1 .. -9            set block size to 100k .. 900k

该数字对应于hundred_k_blocksize写入压缩文件头的值。

从文档来看，内存要求如下：

Compression:   400k + ( 8 x block size )

Decompression: 100k + ( 4 x block size ), or
               100k + ( 2.5 x block size )

在编写原始程序时（1996 年），我想 7.6M（400k + 8 …

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

我想出了这个,(cycle "string")但是感觉有点迫切:

(let [s (str "^" "banana" "|")
      l (count s)
      c (cycle s)
      m (map #(take l (drop % c)) (range l))]
  (apply map str m))
=> ("^banana|" "banana|^" "anana|^b" "nana|^ba" "ana|^ban" "na|^bana" "a|^banan" "|^banana")

我不确定这是否符合代码高尔夫的要求.有更清洁的方法吗？