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

Question

我已经成功地为我正在编写的 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 转换，但有些值是奇怪的(请参阅更新 1)。两种算法的结果也略有不同。 SA-IS算法在前面产生了一个多余的索引值，所以所有的结果都需要向左复制一个索引(SA[i]=SA[i+1])。

要将后缀数组转换为正确的 BWT 索引，我从后缀数组值中减去 1，进行模运算并应具有 BWT 索引(根据 this):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 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”或大文本文件(来自坎特伯雷语料库的 alice29.txt)它们工作正常。实际上，甚至不需要 toBWT() 函数。
将算法应用于包含完整 8 位字节字母表(可执行文件等)的文件中的二进制数据时，它们似乎无法正常工作。将算法的结果与常规 BWT 索引的结果进行比较，我注意到前面有错误的索引(在我的情况下为 4)。索引的数量(顺便说一句？)对应于算法的递归深度。索引指向原始源数据最后一次出现 0 的位置(在我构建 T 时将它们转换为 1 之前)...

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

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

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

Answer 1

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