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

我已经为我正在编写的compression testbed成功实现了BWT阶段(使用常规的字符串排序)。我可以应用BWT，然后进行BWT逆变换，并且输出与输入匹配。现在，我想使用后缀数组来加速BW索引表的创建。我发现了2种相对简单的，据说是快速的O(n)后缀数组创建算法DC3和SA-IS，它们都随C++/C源代码一起提供。我尝试使用源(现成的编译SA-IS源也可以找到here)，但是未能获得正确的后缀数组/BWT索引表。这是我所做的:

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

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

我创建一个整数输出数组SA(对于DC3，大小为n；对于KA-IS，大小为n + 1)，并应用算法。我得到的结果与我的排序BWT转换相似，但是有些值是奇数的(请参阅UPDATE 1)。两种算法的结果也略有不同。 SA-IS算法在前面产生一个多余的索引值，因此所有结果都需要向左复制一个索引(SA [i] = SA [i + 1])。

要将后缀数组转换为适当的BWT索引，我从后缀数组的值中减去1，取模，并应具有BWT索引(根据this):BWT [i] =(SA [i] -1)％ 。

这是我的代码，用于馈送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 used as an EOF marker)
        std::vector<int32_t> 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<int32_t> 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<int32_t> & 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”或较大的文本文件(来自Canterbury语料库的alice29.txt)，它们可以正常工作。实际上，甚至没有必要使用toBWT()函数。
当将算法应用于包含完整8位字节字母(可执行文件等)的文件中的二进制数据时，它们似乎无法正常工作。将算法的结果与常规BWT索引的结果进行比较，我注意到前面出现了错误的索引(在我的情况下为4)。索引的数量(顺便说一下？)对应于算法的递归深度。索引指向原始源数据最后一次出现0的位置(在构建T时我将它们转换为1之前)...

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

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

我发现将数据转换为32位有点尴尬的整个过程。如果有人有更好的解决方案(纸张，更好的一些源代码)来从带有256个字符的字母的字符串中直接生成后缀数组，我会很高兴的。

最佳答案

我现在已经弄清楚了。我的解决方案有两个方面。有人建议使用一个库，我是Yuta Mori的SAIS-lite。
真正的解决方案是复制并连接输入字符串，然后在此字符串上运行SA代。保存输出字符串时，您需要过滤掉超出原始数据大小的所有SA索引。这不是理想的解决方案，因为您需要分配两倍的内存，复制两次并对两倍的数据量进行转换，但是它仍然比std::sort快50-70％。如果您有更好的解决方案，我很想听听。
您可以找到更新的代码here。