私はエンコーディングが初めてなので、基本を理解しようとしています。可逆テキスト圧縮技術について説明している文書を見つけました。この文書には、圧縮がどのように機能するかを示す図がありました。次のように機能します。
Source -> BWT -> MTF -> RLT -> Proprietary Entropy Encoder
Move to Front Transform の後に Run-Length Transform を使用する理由がわかりません。効率的ではないようです。私が理解しているように、MTF自体は多くの実行を生成しないため、RLTのあとがきを使用するのは役に立ちません.
いくつかの説明をいただければ幸いです。
BWT 後の MTF の目標は、エントロピー コーディングに適したシンボルの範囲を縮小することです。MTF はシンボルを、BWT によって生成される反復のために通常小さいランクで置き換えます。その後、MTF によって多数の 0 が生成される可能性があるため、Zero Length Coding が適用される場合があります (0 の連続のみが長さによってエンコードされる RLE の特殊なケースです)。
実装例については、https://github.com/flanglet/kanzi-cppをご覧ください。BlockCompressor は、MTF+ZLE の有無にかかわらず、Block コーデックで実行できます。
効率的ではありません。
おそらくBWTに関する古い論文です。当時、RLE (ランレングス エンコーダー) を使用することは、速度を改善するための一般的な方法でした。RLE、ところで、BWT ステージを高速化するために、BWT の後だけでなく、BWT の前にも使用されました。同じロジックがエントロピー コーダーに適用される可能性がありますが、それほど多くのメリットが得られる可能性は低いです。
今日、このトリックは完全に時代遅れです。BWT の前は、特に長距離の一致 (ブロック サイズを超える) の場合に、ある種の LZP 前処理が見られる場合があります。これは、速度の向上に関して RLE とほぼ同じ意図を持っていますが、より強力です。MTF も完全に置き換えられました。これは、CPU を集中的に使用し、コストの割には効率的ではないためです。