問題タブ [burrows-wheeler-transform]

BWT を使用した後、エンコードされたデータにはどのデータ セットが必要ですか? Suffix Array をエンコード (またはエクスポート) する必要がありますか?

入力：

stackoverflow

BWT 出力:

wtavrcfkle$soo

サフィックス配列:

13, 2, 3, 7, 9, 4, 10, 5, 11, 8, 0, 1, 6, 12

これをaaabccba入力文字列と見なすと、入力baaacacbに Burrows-Wheeler 変換を適用した後の出力文字列になります。c出力を観察すると、2 つの塊が分離されていることがわかります。明らかに、入力文字列は出力よりも優れた圧縮になります。

入力文字列に Burrows-Wheeler 変換を適用するかどうかを決定する方法は? 決定を下すために何らかの迅速な分析を行うことはできますか?

Move to front 変換の最速のアルゴリズムを見つけようとしています。たとえば、burrows wheeler トランスフォームと組み合わせて使用​​されるもの。

Core i3 2.1GHz でこれまでに管理した最高のパフォーマンスは約 15MB/s です。しかし、それが最適ではないことは確かです。これまでの私の最善の努力はここにあります。もっと速いものはありますか？

私が書いている圧縮テストベッドの 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 には 1 が必要です)。したがって、すべての入力データを 32 ビット整数に変換し、すべてのシンボルを 1 ずつ並べ、センチネルの 0 バイトを追加します。Tです。

3. 整数出力配列 SA (DC3 の場合はサイズ n、KA-IS の場合は n+1) を作成し、アルゴリズムを適用します。ソート BWT 変換と同様の結果が得られますが、一部の値は奇数です (UPDATE 1 を参照)。また、両方のアルゴリズムの結果はわずかに異なります。SA-IS アルゴリズムは先頭に過剰なインデックス値を生成するため、すべての結果を 1 つのインデックス分左にコピーする必要があります (SA[i]=SA[i+1])。

4. 接尾辞配列を適切な BWT インデックスに変換するには、接尾辞配列の値から 1 を減算し、モジュロを実行して、BWT インデックスを取得する必要があります (これに従って): BWT[i]=(SA[i]-1)%n .

これは、SA アルゴリズムをフィードして BWT に変換するための私のコードです。多かれ少なかれ、論文から SA 構築コードを差し込むだけでよいはずです。

私は何を間違っていますか？

更新 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 文字のアルファベットの文字列から直接サフィックス配列を生成するためのより良い解決策 (紙、さらにはソース コード) を持っていれば、私は幸せです。

上記は、Lua で BWT エンコーディングを実現するための現在のコードです。この問題は、テーブルのサイズとループの長さが原因で、実行に時間がかかります。1000 文字の入力の場合、平均エンコード時間は約 1.15 秒です。より高速な BWT エンコーディング関数を作成するための提案はありますか?

最大の速度低下は fLexTblSort と fShallowCopy にあるようです。BWT 関数の上にも両方を含めました。