問題タブ [burrows-wheeler-transform]

Burrows Wheeler変換（BWT）のデコードアルゴリズムを理解するのに苦労しています。オンラインで読んでサンプルコードを調べましたが、すべて「プライマリインデックス」を使用してエンコードされた文字列をデコードしているようです。

私の質問は、「rdacraaaabb」のようなBWTでエンコードされた文字列を元の「abracadabra」にデコードするにはどうすればよいかということです。

いくつかのサンプルコードは素晴らしいでしょう。

こんにちは、burrows wheeler transformの最適化に苦労しています。テキスト ファイルを変換しようとしていますが、聖書のような大きなテキスト ファイルの変換には時間がかかりすぎます。

続行する方法について何か考えはありますか？

Burrows and Wheeler の論文からブロック ソート アルゴリズムを読んでいます。これはアルゴリズムのステップです:

S=アブラカダブラとする

N 個の単語 W[0, ... , N - 1] の配列 W を初期化し、W[i] に文字 S'[i, ... , i + k - 1] が含まれるようにします。単語は、k 文字列の辞書式比較と一致します。文字を単語にパックすることには 2 つの利点があります。アラインされたメモリ アクセスを使用して、一度に 2 つのプレフィックスを k バイトずつ比較でき、多くの遅いケースを排除できます。

(注:はk文字が追加されS'たオリジナルです。kは機械語に収まる文字数です (私は 32 ビット マシンを使用しているので、)SEOFk=4

私が間違っている場合は修正してください：

次に、アルゴリズムは、配列にインデックスをS付けることにより、 (V という名前の)のサフィックス配列をソートする必要があると言います。W

にインデックスを付けてサフィックスをソートする方法が完全にはわかりませんW。例: ソートのある時点で、2 つの接尾辞 と を取得iしj、それらを比較する必要があるとします。にインデックスを付けているためW、一度に 4 文字をチェックしています。
最初の 4 文字が両方とも同じであるとします。次に、サフィックスごとに次の 4 文字をチェックする必要があり、W. これは正しいですか？この「文字を言葉に詰め込む」ことは本当にスピードアップするのでしょうか?

ブロックソートを実装しようとしています。これはBurrowsWheelerの論文からのものです。

（この手順の前に、SのV接尾辞配列を作成します）

Q4。[基数ソート]
各サフィックスの最初の2文字をソートキーとして使用して、Vの要素をソートします。これは、基数ソートを使用して効率的に実行できます。

基数ソートでサフィックスをソートしているとのことですが。
これはどのようにアレイVを更新することになっていますか？基数ソートが終了して初めて、接尾辞のソートされた位置を知ることができます。4番目のサフィックスがソート後の最初のサフィックスになるとします。したがって、V [0]=iです。この場合、（私があなたに言ったので）i = 4であることがわかります。しかし、アルゴリズムは、それらの位置を追跡していないので、どのようにしてそれを知るのでしょうか。サフィックスとそのサフィックス番号の両方を含むクラスを作成する必要がありますか？

Javaでハフマン圧縮プログラムを使ってBWTを書こうとしています。BWTでは、Distance Coding (DC) を実装したいと考えています。いくつかの例を探していますが、それほど多くはありません。

私はこの例を見つけました：

http://www.cs.ucr.edu/~stelo/cpm/cpm07/move_to_front_gagie.pdf

DCは29ページから始まります。しかし、コメントがないので、本当にわかりにくいです。

誰かがDCを実装したか、実際のコードでそれを実装する方法を知っているのでしょうか? :)

まず最初にcharが何であるかを書く必要があるという部分を理解しました。しかし、その後、私はそれを得ることができませんでした。

各文字について、DC はシーケンス内の次の出現を見つけ、それを S に書き込み、距離を出力します。発生がない場合は 0 を書き込みます。

ありがとう。

よく知られているバロウズ・ウィーラー変換を線形時間で実行する必要があります。サフィックスソートとEOF文字を使用した解決策を見つけましたが、EOFを追加すると変換が変更されます。例: 文字列bcababa と 2 つの回転を 考えてみましょう

• s1 =abababc
• s2 =ababcab

s1 < s2 であることは明らかです。EOF 文字を使用すると、次のようになります。

• s1 = アババ#bc
• s2 = アバ#bcab

そして今、s2 < s1。そして、結果として生じる変換は異なります。EOF なしで BWT を実行するにはどうすればよいですか?

「abracdabra!」の入力テキストを変換した後、変換ベクトルは [3, 0, 5, 6, 7, 9, 10, 8, 2, 1, 4] になり、テキストはさらにいくつかの変換を経てパイプ処理され、ディスクに圧縮されます。

プログラムを閉じると、変換ベクトルにアクセスできなくなります。変換ベクトルをディスクに書き込む必要がありますか? ベクトルのサイズは実際には n 文字に等しくないでしょうか? これにより、実際には圧縮ファイルのサイズが大きくなりませんか?

ウィキペディアでBurrows-Wheeler変換の例を再現しようと遊んでいます。楽しみに追加するために、私は再帰的な戦略によってそうしようとしています。しかし、私は最初のステップで立ち往生し、文字列のすべての回転を作成します。これが私のコードです：

これにより、次の出力が生成されます。

これはウィキペディアの例に似ていますが、同一ではなく、理由がわからないようです。例によると、出力は次のようになります。

私はしばらくの間これを見つめていました、そして問題はかなり簡単であるはずですが、私はそれを理解することができないようです。私が間違っていることを見つけられますか？

バロウウィーラーのサイクリックストリングアレイで非常に大きなストリングを回転させてみました。

しかし、私の入力は約200000文字であり、入力がこれほど大きい場合、ヒープスペースが不足するため、コードを実行できません。

私の教授は、それを実装する唯一の方法は線形メモリフットプリントであると言いました。それが何を意味するのか私にはわかりません。

メモリ効率の高い循環文字列を作成し、メモリを使い果たすことなくそれを使用する他の方法を知ることができますか？

私はエンコーディングが初めてなので、基本を理解しようとしています。可逆テキスト圧縮技術について説明している文書を見つけました。この文書には、圧縮がどのように機能するかを示す図がありました。次のように機能します。

Move to Front Transform の後に Run-Length Transform を使用する理由がわかりません。効率的ではないようです。私が理解しているように、MTF自体は多くの実行を生成しないため、RLTのあとがきを使用するのは役に立ちません.

いくつかの説明をいただければ幸いです。