burrows-wheeler-transform - 大きな文字列のバローウィーラーの実装

Question

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

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

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

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

Answer 1

n lg nメモリ使用量を減らす秘訣は、文字列内の各文字を個別に考慮するクイックソートのバリアントを使用して、平均的な場合に比例して（およびメモリに比例して）時間に比例して実行できる循環接尾辞配列を作成することですn（別名3ウェイ文字列クイックソート。概念的には基数ソートに似ています）。

それでもメモリが多すぎる場合は、固定サイズのブロックで動作するようにバロウズウィーラー変換を制限する必要があります（文字列全体をエンコードするまで、X文字、次のX文字などでエンコードを実行し、デコードのプロセス）。