私が書いている圧縮テストベッドの 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 には 1 が必要です)。したがって、すべての入力データを 32 ビット整数に変換し、すべてのシンボルを 1 ずつ並べ、センチネルの 0 バイトを追加します。Tです。
整数出力配列 SA (DC3 の場合はサイズ n、KA-IS の場合は n+1) を作成し、アルゴリズムを適用します。ソート BWT 変換と同様の結果が得られますが、一部の値は奇数です (UPDATE 1 を参照)。また、両方のアルゴリズムの結果はわずかに異なります。SA-IS アルゴリズムは先頭に過剰なインデックス値を生成するため、すべての結果を 1 つのインデックス分左にコピーする必要があります (SA[i]=SA[i+1])。
接尾辞配列を適切な 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 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
「ヤバダバド」/「これはテストです」のような短い量のテスト テキスト データにアルゴリズムを適用する場合。/ "abaaba" または大きなテキスト ファイル (カンタベリー コーパスのalice29.txt ) で問題なく動作します。実際には toBWT() 関数は必要ありません。
完全な 8 ビット バイト アルファベット (実行可能ファイルなど) を含むファイルのバイナリ データにアルゴリズムを適用すると、正しく動作しないようです。アルゴリズムの結果を通常の BWT インデックスの結果と比較すると、先頭に誤ったインデックス (私の場合は 4) があることに気付きました。インデックスの数 (ちなみに?) は、アルゴリズムの再帰の深さに対応します。インデックスは、元のソース データで最後に 0 が発生した場所を指しています (T を構築するときにそれらを 1 に変換する前)...
UPDATE 2
通常の BWT 配列とサフィックス配列をバイナリ比較すると、さらに異なる値があります。公平な並べ替えは必ずしも標準的な並べ替えと同じである必要はないため、これは予想されるかもしれませんが、配列によって変換された結果のデータは同じである必要があります。そうではない。
UPDATE 3
両方のアルゴリズムが「失敗」するまで、単純な入力文字列を変更しようとしました。「これはテストです」という文字列の 2 バイトを変更した後。255 または 0 (746869732069732061 20 74657374 2E h から 746869732069732061 FF 74657374 FF h まで、最後のバイトを変更する必要があります!) インデックスと変換された文字列はもはや正しくありません。また、文字列の最後の文字を文字列に既に出現している文字に変更するだけでも十分なようです。たとえば、「これはテストです」7468697320697320612074657374 73 h 次に、変換された文字列の 2 つのインデックスと 2 つの文字が交換されます (通常の並べ替え BWT と SA を使用する BWT を比較)。
データを 32 ビットに変換するプロセス全体が少し厄介だと思います。誰かが 256 文字のアルファベットの文字列から直接サフィックス配列を生成するためのより良い解決策 (紙、さらにはソース コード) を持っていれば、私は幸せです。