使用后缀数组算法进行Burrows Wheeler变换

我成功地为我正在编写的压缩测试平台实现了一个BWT阶段(使用常规字符串排序).我可以应用BWT然后反BWT变换,输出匹配输入.现在我想加速使用后缀数组创建BW索引表.我找到了2个相对简单的,假设快速的O(n)算法用于后缀数组创建,DC3和SA-IS都带有C++/C源代码.我尝试使用这些源代码(开箱即用的编译SA-IS源代码也可以在这里找到),但无法获得正确的后缀数组/ BWT索引表.这就是我所做的:

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

我处理8位字节,但两种算法都需要一个零字节形式的唯一标记/ EOF标记(DC3需要3,SA-IS需要一个),因此我将所有输入数据转换为32位整数,增加所有符号均为1,并附加标记零字节.这是T.

我创建了一个整数输出数组SA(DC3的大小为n,KA-IS的大小为n +)并应用算法.我得到的结果类似于我的排序BWT变换,但有些值是奇数(见更新1).两种算法的结果也略有不同.SA-IS算法在前面产生一个超额索引值,因此所有结果都需要被一个索引(SA [i] = SA [i + 1])左侧复制.

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

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

std::vector SuffixArray::generate(const std::vector & data)
{
    std::vector 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 used as an EOF marker)
        std::vector T(data.size() + 3, 0);
        std::copy(data.cbegin(), data.cend(), T.begin());
        std::for_each(T.begin(), std::prev(T.end(), 3), [](int32_t & n){ n++; });
        SA.resize(data.size());
        SA_DC3(T.data(), SA.data(), data.size(), 256);

        OR

        //copy data over. we need to append a zero byte, 
        //as the algorithm expects T[n-1]=0 (where n is the size of its input data)
        //also increase the symbol value by 1, because the algorithm alphabet is [1,K] 
        //(0 is used as an EOF marker)
        std::vector T(data.size() + 1, 0);
        std::copy(data.cbegin(), data.cend(), T.begin());
        std::for_each(T.begin(), std::prev(T.end(), 1), [](int32_t & n){ n++; });
        SA.resize(data.size() + 1); //crashes if not one extra byte at the end
        SA_IS((unsigned char *)T.data(), SA.data(), data.size() + 1, 256, 4); //algorithm expects size including sentinel
        std::rotate(SA.begin(), std::next(SA.begin()), SA.end()); //rotate left by one to get same result as DC3
        SA.resize(data.size());
    }
    else
    {
        SA.push_back(0);
    }
    return SA;
}

void SuffixArray::toBWT(std::vector & SA)
{
    std::for_each(SA.begin(), SA.end(), [SA](int32_t & n){ n = ((n - 1) < 0) ? (n + SA.size() - 1) : (n - 1); });
}

我究竟做错了什么？

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

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

更新3
我尝试修改一个简单的输入字符串,直到两个算法都"失败".更改字符串的两个字节后"这是一个测试".到255或0(从746869732069732061 20 74657374 2E小时,例如746869732069732061 FF 74657374 FF小时,最后一个字节必须改变!)指数和变换的串不正确了.它似乎足以将字符串的最后一个字符更改为字符串中已经出现的字符,例如"这是一个测试"7468697320697320612074657374 73 h.然后交换两个索引和两个转换字符串的字符(比较使用SA的常规排序BWT和BWT).

我发现必须将数据转换为32位有点尴尬的整个过程.如果有人有更好的解决办法(纸,更好的是,一些源代码)生成与256字符字母直接将字符串后缀阵列,我会很高兴.