c++ - LZW圧縮と辞書

Question

LZW圧縮をC++で実装することを検討していますが、最適な辞書の実装がわかりません。

ハッシュテーブルは理にかなっていますが、値を「再割り当て」する方法がわかりません。テーブルがいっぱいになった場合、以前の（最も古い）複数文字の辞書エントリの上書きを開始できるようにする必要があります。ハッシュテーブルでは、これらを追跡し、見つけて削除し、新しいものを挿入する必要があります。

助言がありますか？

Answer 1

Unixの圧縮ユーティリティ (ソース コード リンク)は、二重ハッシュと周期表のクリアを使用します。

高速な圧縮と解凍が必要な場合は、恐ろしく時代遅れになっている LZW よりもはるかに優れた選択肢があります。zlib (おそらく既にマシン上にある)、LZO、およびlz4の高速なレベル 1 圧縮を確認する必要があります。

教育的または娯楽的価値以外に、新しい LZW コードを作成する理由はありません。それは歴史的な興味だけです。また、そのような説明や娯楽のために圧縮ユーティリティを研究することもできます。

Answer 2

圧縮と解凍では、2 つの異なる構造を使用する必要があります。

圧縮中は、キーではなくコンテンツで辞書を検索する必要があるため、 Trieを使用する必要があります。

解凍中は、より従来の方法、つまりキーで辞書にアクセスします。その後、任意の連想配列構造を使用できます。ハッシュテーブルや文字列のベクター/両端キューのように（インデックスは連続した自然数であるため）。

Answer 3

あなたが探しているのは、実際には2 つのデータ構造を組み合わせたものです。

1. ハッシュ テーブル。
2. FIFO キュー (古いテーブル エントリを破棄するため))。

コメントが示唆するように練習を探している場合は、それらを自分で実装するか、stl/sgi/c++11 実装を使用できます (unordered_map は、sgi または c++11 を介した実際のハッシュ マップ、および FIFO キューです)。 std::deque などの双方向リンク リストです)。

最も古いディクショナリ エントリを破棄する場合は常に、キュー内の最後の要素をポップし、ハッシュ テーブルからも削除するという考え方です。