LZWL

LZWLは、 Lempel-Ziv-Welch（LZW）圧縮アルゴリズムの音節ベースの派生版であり、あらゆる音節分解アルゴリズムから生成された音節を処理できるように設計されています。このアプローチにより、LZWLは音節と単語の両方を効率的に処理し、データ圧縮のための繊細な手法を提供します。

アルゴリズム

LZWLアルゴリズムは、アルファベットのすべての文字を辞書に入力することで初期化します。次に、辞書と入力のエンコードされていない部分の接頭辞の両方に存在する最長文字列Sを検索します。アルゴリズムはSの識別子を出力し、 Sと入力内の後続の文字を組み合わせた新しいフレーズを辞書に追加します。入力位置はSの長さだけ進みます。デコード中、LZWLは受信したフレーズ識別子が辞書に存在しないシナリオに対処し、最後に追加されたフレーズとその先頭文字を連結して、不足しているフレーズを構築します。

音節ベースの適応

音節ベースの適応において、LZWLは音節のリストをアルファベットとして用います。初期化ステップでは空音節が含まれ、頻繁に出現する小さな音節が辞書に統合されます。Sの識別とその識別子のエンコードは元のアルゴリズムとほぼ同じですが、 Sは音節列を表すという点が異なります。Sが空音節の場合、アルゴリズムは入力から音節Kを抽出し、新しい音節用のメソッドを用いてKをエンコードした後、Kを辞書に追加し、それに応じて入力位置を進めます。

辞書の拡張

音節ベースのLZWLにおける注目すべきバリエーションとして、辞書拡張が挙げられます。文字列Sと後続の文字列S1の両方が空でない音節である場合、 S1とSの最初の音節を連結することで、新しいフレーズが辞書に追加されます。この手法により、一度しか出現しない音節から文字列が形成されるのを防ぎ、デコーダーが未定義のフレーズ識別子に遭遇するのを防ぎます。

参考文献

• LZWLアルゴリズムを使用したデータ圧縮
• Salomon, David; Motta, Giovanni (2010-01-18). 『データ圧縮ハンドブック』 . Springer. ISBN 9781848829039. Google Books . 2014-07-11閲覧.

カテゴリー