3

Burrows Wheeler Transformation のちょっとした問題で立ち往生しています。これは大学のプロジェクトですが、これはごく一部です。プロジェクト全体は、データ圧縮のためにまとめられた 3 つの異なるアルゴリズムで構成されています。

Burrows Wheeler Transformation でサフィックスの並べ替えに使用する、最もメモリ効率と時間効率の良い並べ替えアルゴリズムを見つけようとしています。エンコードは可能な限り効率的である必要があります。

より小さい配列では、並べ替えは実​​際には影響しませんが、圧縮しているテキスト ファイルがますます大きくなる一方で、非効率的な並べ替えアルゴリズムを使用すると、時間とメモリの効率が実際に損なわれます。

どんな助けでも大歓迎です、事前に感謝します!

編集

ちなみに、私たちはJavaでコーディングしていますが、それについて言及したことがないことに気づきました。

4

2 に答える 2

6

多くの実用的な BWT ベースの圧縮ツールは、DivSufSortとMSufSortに基づいています。ただし、パフォーマンスは O(n^2) 最悪です。並べ替える前に、データに対していくつかの前処理方法を使用する必要があります。

理論的に最適な時間/空間コストを得るには、 sa-isとsa-dsを試してください。

サフィックスの並べ替えアルゴリズムを自分で作成しようとしている場合は、高速でシンプルなQSufSortから始めることをお勧めします。

于 2013-04-12T10:41:17.650 に答える
1

richselian が述べたように、並べ替えは 2 次ですが、接尾辞配列ベースのアルゴリズムは線形です。配列が小さい場合は問題ありませんが、配列が大きいほど圧縮結果が向上します。例として、サフィックス配列に基づく BWT の完全な Java 実装を見つけることができます: https://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/BWT.java (arrays 16MBまで）。「Java は遅い」という議論については、私は丁重に反対します。

于 2013-12-04T06:17:42.610 に答える