はじめに
今回は J.Zip 氏と A.Lempel 氏が開発した LZ 符号 (Zip-Lempel 符号) を取り上げます。前回説明したシャノン・ファノ符号とハフマン符号は、出現頻度の高い記号には短い符号語を、低い記号には長い符号語を割り当てることでデータ圧縮を実現しました。
これに対して、LZ 符号は「辞書に基づく符号化方式 (辞書法, dictionary-based coding)」といって、ハフマン符号とはまったく異なるアプローチでデータ圧縮を実現しています。辞書法は入力された記号列を辞書に登録し、その辞書を使って符号化を行います。辞書法は多くの圧縮ツールで用いられているオーソドックスな方法です。
今回は辞書法の一つで「スライド辞書法」と呼ばれている LZ77 符号について説明します。
●LZ 符号の基礎知識
たとえば、『ALICE'S ADVENTURES IN WONDERLAND (不思議の国のアリス) 』を例に考えてみましょう。このテキストには 2 文字以上の単語が約 3000 種類含まれています。ここで、これらの単語をアスキーコード順に並べた辞書を定義すると、単語の位置情報は 12 ビットで表すことができます。2 文字の単語はアスキーコードで 16 ビットになるので、単語を位置情報に変換すれば 12/16 = 75 [%] に圧縮することができます。長い単語になるほど圧縮効果が高くなり、8 文字の単語は 64 ビットなので、18.75 [%] にまで圧縮することができます。
このように、可変長の記号列を固定長の符号語に対応させるような符号を「VF (Variable-to-Fix) 符号」といいます。また、可変長の記号列を可変長の符号語に対応させるような符号を「VV (Variable-to-Variable) 符号」といいます。
もし、ファイルごとに専用の辞書を用意すれば、高い圧縮率を実現できるはずです。符号化に先だって辞書を編集しておいて、その辞書に基づいて符号化を行う方法を「静的辞書法 (static dictionary method)」といいます。ところが、この方法では符号化と復号において同じ辞書を使わなければならないため、ハフマン符号と同様に辞書を渡す方法が問題となります。ハフマン木と違い辞書はかなりのサイズを必要とするので、ファイルに付加する方法では圧縮率の大幅な低下は避けられません。
この問題を解決する方法が「適応型辞書法 (adaptive dictionary method)」です。この方法は前もって辞書を用意せずに、ファイルを読み込みながら辞書を作成していきます。そして、辞書に登録されている記号列が出てきたら、辞書の位置情報に変換することで符号化を行います。最初は辞書が空の状態なので圧縮することはできませんが、ファイルを読み込むにしたがい、十分な記号列が辞書に登録されるので高い圧縮率を実現することができます。
そして、現在最も有名な適応型辞書法が「LZ 符号」なのです。LZ 符号には多数のバリエーションが存在しますが、「LZ77 符号」と「LZ78 符号」の 2 つに大別されます。LZ77 符号は 1977 年に、LZ78 符号は 1978 年に発表されました。両者の符号は互いに関係があるものの、辞書の作成方法はまったく異なっているので、混同しないように注意してください。LZ77 符号は「スライド辞書法」、 LZ78 符号は「動的辞書法」と呼ばれています。
●LZSS 符号
LZ77 符号には多数のバリエーションが存在しますが、その中で最も基本的で広く用いられている方法に「LZSS 符号」があります。参考文献, URL 1 によると、 『現在普及している圧縮プログラムで LZ77 符号と呼ばれているもののほとんどは、じつは LZSS 符号になっています。』 ということなので、今回は「LZSS 符号」を使って説明します。
LZSS 符号は、読み込んだ記号列をバッファに格納し、それを辞書として利用します。バッファの大きさは有限なので、新しく記号列を読み込んだ分だけ、古い記号列を捨てていかなければなりません。この動作は、ファイルをひとつの記号列として考えると、その上をバッファがスライドしていくように見えることから、このバッファを「スライド窓」と呼びます。
スライド窓には参照部と符号化部があり、符号化部の先頭が符号化の対象となる記号です。LZSS 符号は参照部の中から符号化部と最長一致する記号列 (最長一致系列) を探して、その位置情報と一致した長さで符号化を行います。上図では、参照部の大きさが 16 で、符号化部の大きさが 4 に設定されています。
参照部のとりうる値は 0 - 15 なので、位置情報は 4 ビットで表すことができます。一致長の情報は単純に考えると 3 ビット必要になりますが、不一致の場合は長さを符号化する必要はないので、長さ - 1 を符号化することにします。すると、一致長は 2 ビットで表すことができます。たとえば、最大 4 文字一致した場合、32 ビットの記号列が 6 ビットまで圧縮することができます。
LZSS 符号の場合、スライド窓の大きさは 1024 から 4096 程度、符号化部は 10 から 128 程度が選ばれるようです。スライド窓が 4096 で符号化部を 16 とすると、位置情報が 12 ビット、一致長の情報を 4 ビットの計 16 ビットで表すことができます。この場合、3 文字未満の記号列では圧縮できなので、3 文字以上の記号列に対して符号化を行うことにします。そうすると、符号化部の大きさは 18 まで増やすことができます。
ところで、近年になってコンピュータの性能が著しく向上したことにより、スライド窓を大きくすることが可能になりました。スライド窓を 8192 としても Python で問題なく動作します。
●LZSS 符号の符号化
それでは、具体的に符号化の様子を説明しましょう。
参照部には既に記号列が読み込まれているとします。この中から、符号化部と最も長く一致する部分列 (最長一致系列) を探します。参照部は 0 から数えるとすると、5 番目の "IS " が見つかります。符号は、参照部と一致したことを示すフラグ '1' と、位置情報 5 を表す '0101' と、長さ 3 から 1 引いた '10' の 7 ビットで表すことができます。
次に、一致した長さだけ新しい記号列を読み込みます。この場合、スライド窓を 3 文字分右へ動かします。
この場合は、2 番目の "IS " と一致するので、[1, 0010, 10] と符号化し、スライド窓を移動します。
参照部には、符号化部の先頭記号 A を含んでいないので、この場合は不一致となります。不一致を示すフラグ 0 と記号 'A' のアスキーコードを符号語として出力します。そのあと、1 文字分スライド窓を移動します。
あとは、符号化部に記号がなくなるまで、この処理を繰り返すだけです。
●LZSS 符号の復号
次に、復号の様子を説明します。
復号する場合、符号化部は必要ありません。参照部には "WHAT IS THIS? TH" まで復号されているとします。
符号語の最初の 1 ビットは 1 なので、次の 4 ビットが位置情報を、その次の 2 ビットが一致長を表しています。この場合は <5, 3> なので、参照部の 5 番目から 3 文字 "IS " と復号できます。これをファイルへ出力するとともに、参照部へ追加してバッファを更新します。このとき、古い文字（左側の文字）から順番に捨てられます。
次の符号語を読み込むと、最初のビットが 1 なので、先ほどと同様に位置情報と長さを求めます。符号語は <2, 3> なので、参照部の 2 番目から "IS " と復号できます。これを出力してバッファを更新します。
次の符号語は最初のビットが 0 なので、次の 8 ビットがアスキーコードを表しています。これは簡単に 'A' と復号できます。記号 A を出力してバッファを更新します。あとは符号語がなくなるまで、この処理を繰り返すだけです。
●スライド窓の構造
次に、バッファとスライド窓の構造を具体的に説明します。『Ｃ言語による最新アルゴリズム事典』(参考文献 2) ではスライド窓をリングバッファで実装していますが、本稿では LHA のプログラム (参考文献, URL 2) を参考にスライド窓を実装します。次の図を見てください。
スライド窓の大きさを N とし、符号化部の大きさを F とすると、データを読み込むバッファの大きさを 2 * N + F に設定します。スライド窓は符号化部の開始位置 rp で表します。
すると、符号化部は rp から rp + F - 1 まで、参照部は rp - N から rp - 1 までになります。rp は 0 に初期化するので、符号化開始直後の参照部は大きさ 0 になります。符号化を行うと rp の値が増えてスライド窓も移動します。参照部の大きさも増加しますが、N より大きくなることはありません。
この場合、最長一致系列の位置情報はバッファの位置ではなく、最長一致系列と rp との距離を符号化した方が簡単です。スライド窓の参照部が 8192 の場合、最短では 1 個前の記号列と、最長では 8192 個前の記号列と一致します。距離を -1 すれば、符号化する数値は 0 から 8191 までの 13 bit で表すことができます。つまり、最長一致系列の位置を pos とすると、rp - pos - 1 を符号化すればいいわけです。
rp の値が 2 * N 以上になったならばデータを移動します。次の図を見てください。
rp の後ろには符号化部に相当するデータしかありません。この場合、参照部と符号化部のデータ (N + F バイト) をバッファの先頭へ移動し、rp の値を rp - N に更新します。これでスライド窓をバッファの先頭に移動することができます。バッファの後ろには N バイトの空き領域ができるので、そこにファイルからデータを読み込みます。これを繰り返すことでバッファよりも大きなファイルを符号化することができます。
●最長一致系列の探索
LZSS 符号をプログラムする場合、参照部から最長一致系列を探す処理がポイントになります。スライド窓のサイズが N で符号化部が F とすると、これを力任せに探索した場合、最悪 N * F 回の比較が必要になります。このままでは、符号化に時間がとてもかかるので、この比較回数をできるだけ減らすような工夫が必要になります。
今回は ハッシュ法と連結リストを使って探索処理を実装します。記号列を辞書に登録するとき、先頭から 3 文字分の記号列でハッシュ値を求め、ハッシュ表に登録します。このとき、データを連結リストの先頭に追加するのがポイントです。
すると、連結リストは距離の短い順に記号列が並ぶので、最長一致系列の中で一番短い距離の記号列を簡単に見つけることができます。LZSS 符号の圧縮率は距離の長短に左右されることはありませんが、LZSS 符号を改良した他の符号化方式の場合、距離の短い方が圧縮率の点で有利になります。
実をいうと、ハッシュ法と連結リストだけの簡単な実装方法では、ハッシュ値の衝突が頻繁に発生すると、実行速度が極端に遅くなるという欠点があります。LHA のプログラム (参考文献, URL 2) は、この対応策が実装されていますが、まずは単純な方法でプログラムを作ってみることにします。
このように、LZSS 符号の符号化は探索処理が複雑で時間がかかりますが、復号は長さと位置を求めてバッファの内容を出力するだけなので、簡単に実行することができます。LZSS 符号は、符号化には時間がかかりますが復号は速いアルゴリズムなのです。
●補足 特許の問題
ところで、LZ77 符号とハッシュの組み合わせには多数の特許がありました。ハッシュの使い方 (手法) によっては、これらの特許に抵触する恐れもあったようです。現在 (2022 年)、これらの特許の多くは有効期限が切れていると思われますが、特許の話はとても難しくて M.Hiroi の手に負えません。ここまでにしておきましょう。特許については、奥村晴彦先生のページ データ圧縮と特許 をお読みください。
●スライド窓のプログラム
それではプログラムを作りましょう。最初にスライド窓を表すクラスを定義します。次のリストを見てください。
リスト : スライド窓の定義
# 定数
MIN_LEN = 3
MAX_LEN = 18
LEN_BITS = 4
POS_BITS = 13
# スライド窓
class Slide:
def __init__(self, s):
self.stream = s
self.size = 1 << POS_BITS
self.limit = self.size * 2
self.link = [None] * self.size
self.ht = {}
self.buff = [0] * (self.limit + MAX_LEN)
self.data_size = self.fread(0, self.limit + MAX_LEN)
self.match_len = 0
self.match_pos = 0
クラス名は Slide としました。インスタンス変数 stream が入力ファイル、size がスライド窓の大きさです。位置情報を POS_BITS (13) で表すことにすると、スライド窓の大きさは 8192 になります。limit は size * 2 の値で、符号化部の開始位置 rp が limit 以上になったらスライド窓を更新します。
インスタンス変数 ht と link でハッシュ表と連結リストを構成します。インスタンス変数 buff がバッファで、大きさは limit + MAX_LEN (18) になります。データの読み込みはメソッド fread() で行います。data_size が読み込んだデータ数です。match_len と match_pos は最長一致系列の探索結果を格納します。match_len はマッチングした長さ、match_pos はその位置を格納します。
MIN_LEN (3) は LZSS 符号で符号化を行う長さです。MAX_LEN は最長一致系列の最大値で 18 としました。符号化は MIN_LEN 以上になったら行うので、長さは 0 から 15 で表すことができます。したがって、ビット長 (LEN_BITS) は 4 になります。
次はハッシュ表にデータを挿入するメソッド insert() を作ります。
リスト : データの挿入処理
# ハッシュ値を求める
def hash_value(self, rp):
value = 0
for x in range(MIN_LEN):
value = (value << 8) + self.buff[rp + x]
return value
# データの挿入
def insert(self, rp):
value = self.hash_value(rp)
if value in self.ht:
self.link[rp & (self.size - 1)] = self.ht[value]
else:
self.link[rp & (self.size - 1)] = None
self.ht[value] = rp
insert() の引数 rp はハッシュ表に登録するデータの位置を表します。最初に、メソッド hash_value() でハッシュ値 value を求めます。これは self.buff[rp] から MIN_LEN 個の記号を使って計算します。今回は 3 バイトの記号列を単純に 24 ビットの整数値に変換しています。あとは Python の辞書 (ハッシュ表) にお任せです。
ハッシュ表 ht[value] には位置 rp を格納します。そして、配列 link[rp] には次の位置を格納します。つまり、link を使って連結リストを実現しています。次の図を見てください。
配列を使って連結リストを実装する場合、添字を使って要素をつないでいきます。たとえば、ハッシュ値が n で ht[n] の値が 2 の場合、連結リストの先頭の値は 2 で、その次の値は link[2] に格納されています。これを順番にたどっていくと、2 - 1 - 0 - None になります。また、ハッシュ値が m で ht[m] の値が 4 の場合、上図の連結リストは 4 - 3 - None になります。つまり、リストの先頭をハッシュ表に格納して、そのあとの連結を配列 link で表しているのです。
したがって、位置 x をハッシュ値 n のリストに追加する場合、ht[n] の値を link[x] にセットし、ht[n] に x をセットします。これで、連結リストの先頭に x が追加され、そのあと - 2 - 1 - 0 - None となります。ht に n が存在しない場合は、連結リストがないので、ht[n] に x をセットし、link[x] に終端を表す None をセットします。
それから、もう一つ注意点があります。link はスライド窓と同じ大きさに設定するので、位置 rp をそのまま添字に指定することはできません。next[rp & (size - 1)] として、下位 POS_BITS の値でアクセスすることに注意してください。
たとえば、link[x] が None で、link[y] の値が x とします。すると、連結リストは - y - x - None になります。位置 x と x + size は、link で同じ位置になりますが、x + size を挿入するとき、x はスライド窓の範囲外になるので、上書きしても問題はありません。このとき、link[x] の値 None が書き換えられるため、連結リストの終端がわからなくなるように思いますが、None のほかに位置がスライド窓の範囲内にあるかチェックすれば大丈夫です。
それでは、最長一致列を探索するメソッド search() を作ります。
リスト : 最長一致列の探索
def search(self, rp):
b = self.buff
value = self.hash_value(rp)
limit = rp - self.size
self.match_len = 0
self.match_pos = 0
if value in self.ht:
n = self.ht[value]
while n is not None and n >= limit:
if b[rp + self.match_len] == b[n + self.match_len]:
x = 0
while x < MAX_LEN:
if b[rp + x] != b[n + x]: break
x += 1
if self.match_len < x:
self.match_len = x
self.match_pos = n
if x == MAX_LEN: break
n = self.link[n & (self.size - 1)]
# データの終端をチェック
if self.match_len >= self.data_size - rp:
self.match_len = self.data_size - rp
引数 rp は符号化部の先頭位置です。まず、ハッシュ値を計算して value にセットします。変数 limit はスライド窓の範囲 (左端) を表します。limit から rp - 1 までがスライド窓の範囲になります。match_len と match_pos は 0 に初期化します。value がハッシュ表 ht に存在しない場合は、スライド窓に一致する記号列はありません。value がハッシュ表にある場合は探索処理を行います。
次に、ハッシュ表から位置 n を取り出します。while ループで連結リストをたどって最長一致列を探索します。n が None または limit よりも小さい場合は、連結リストの終端に達したので while ループを終了します。そうでなければ、n から始まる記号列と rp から始まる記号列を比較します。
match_len より長い記号列を探すので、最初に buff[n + match_len] と buff[rp + match_len] が等しいかチェックします。等しい場合は、match_len よりも長くなる可能性があるので、記号列の先頭から比較します。単純なチェックですが、実行速度はこの方が速くなるようです。
変数 x が一致長を表しています。これが match_len よりも大きい場合は match_len と match_pos を更新します。長さが MAX_LEN の記号列を見つけたら break で while ループを脱出します。最後に、buff の範囲外のデータとマッチングしていないかチェックします。buff の範囲は 0 から data_size - 1 までです。match_len が data_size - rp 以上であれば範囲外のデータとマッチングしています。match_len を data_size - rp に変更します。
次はスライド窓を更新するメソッド update() を作ります。
リスト : スライド窓の更新
def update(self, rp):
if self.data_size < self.limit + MAX_LEN: return rp
# buffer update
self.move_data(0, self.size, self.size + MAX_LEN)
n = self.fread(self.size + MAX_LEN, self.size)
self.data_size = self.size + MAX_LEN + n
# hash update
for k, v in list(self.ht.items()):
if v < self.size:
del self.ht[k]
else:
self.ht[k] = v - self.size
for x in range(self.size):
v = self.link[x]
if v == None or v < self.size:
self.link[x] = None
else:
self.link[x] = v - self.size
return rp - self.size
引数 rp は符号化部の開始位置です。rp が limit 以上になったら update() を呼び出します。data_size が buff の大きさ (limit + MAX_LEN) よりも小さい場合、ファイルからデータを全て読み込んだので、スライド窓の更新は行いません。ファイルのデータが残っている場合にのみ、スライド窓を更新します。
最初に、buff の後半のデータを move_data() で前へ移動します。そして、後半部分にファイルからデータを fread() で読み込みます。それから、ハッシュ表 ht を更新します。メソッド items() で ht からキーと値を取り出して k, v にセットします。v が size よりも小さい場合、そのデータはバッファから削除されたので、ハッシュ表 ht からも削除します。size よりも大きい場合、データはバッファの前半部分に移動したので、値を v - size に更新します。
次に、連結リスト link を更新します。link[x] の値を v にセットします。v が None または size よりも小さい場合、そのデータはバッファから削除されたので、link[x] の値を None に書き換えます。そうでなければ、v - size に更新します。最後に新しい符号化開始位置 rp - size を返します。
●符号化のプログラム
これでスライド窓のプログラムは完成です。次は符号化を行う関数 encode() を作ります。
リスト : 符号化
def encode(fin, fout):
s = Slide(fin)
rp = 0
while rp < s.data_size:
s.search(rp)
if s.match_len < MIN_LEN:
num = 1
fout.putbit(0)
fout.putbits(8, s.buff[rp])
else:
num = s.match_len
fout.putbit(1)
fout.putbits(LEN_BITS, num - MIN_LEN)
fout.putbits(POS_BITS, rp - s.match_pos - 1)
for _ in range(num):
s.insert(rp)
rp += 1
if rp >= s.limit: rp = s.update(rp)
最初にスライド窓のオブジェクトを生成して変数 s にセットし、符号化開始位置 rp を 0 に初期化します。そして、rp が data_size と等しくなるまで while ループで処理を繰り返します。最初に、メソッド search で最長一致系列を探索します。s.match_len が MIN_LEN よりも小さい場合は、不一致を表すフラグ 0 と記号 buff[rp] をそのまま出力します。
s.match_len が MIN_LEN 以上の場合は、長さと位置で符号化します。num に長さをセットして、putbit() でフラグ 1 を出力します。それから、長さと位置を putbits() で出力します。長さのビット長は LEN_BITS で、num - MIN_LEN を符号化します。位置のビット長は POS_BITS で、符号化開始位置からの距離 rp - s.match_pos - 1 を符号化します。
それから、for ループで符号化した num 個の記号列をメソッド insert() でハッシュ表に登録します。記号列を一つ登録したら、rp を +1 します。rp が limit 以上になったら、メソッド update() を呼び出してスライド窓を更新します。
●復号のプログラム
最後に復号処理を作ります。
リスト : 復号
def decode(fin, fout, size):
rp = 0
buff = [0] * (1 << POS_BITS)
while size > 0:
if fin.getbit() == 1:
num = fin.getbits(LEN_BITS) + MIN_LEN
pos = rp - (fin.getbits(POS_BITS) + 1)
if pos < 0: pos += len(buff)
for _ in range(num):
c = buff[pos]
fout.putc(c)
buff[rp] = c
pos += 1
rp += 1
if pos >= len(buff): pos = 0
if rp >= len(buff): rp = 0
else:
num = 1
c = fin.getbits(8)
fout.putc(c)
buff[rp] = c
rp += 1
if rp >= len(buff): rp = 0
size -= num
変数 rp が復号した記号を書き込むバッファの位置を表します。復号の場合、スライド窓は必要ありません。バッファをリングバッファとして使うので、大きさはスライド窓の大きさ (1 << POS_BITS) で十分です。rp がバッファの大きさよりも大きくなったならば、rp の値を 0 にしてバッファの先頭に戻します。
次に、getbit() で 1 ビット読み込み、その値が 1 ならば長さと位置を復号します。getbits() で長さと距離を求めます。そして、距離を位置 pos に変換します。位置と長さを復号したら、buff[pos] から num バイトを buff[rp] へコピーするとともに、ファイル fout へ復号した記号列を出力します。rp と pos の値が len(buff) 以上になったならば 0 に戻すことを忘れないでください。
フラグが 0 の場合は記号を復号します。getbits() で 8 ビット読み込み、ファイル fout へ出力します。そして、buff[rp] に復号した記号を書き込みます。rp を +1 して、値が len(buff) 以上になったら 0 に戻します。
●評価結果
それでは、実際に Canterbury Corpus で配布されているテストデータ The Canterbury Corpus を圧縮してみましょう。
表 : LZSS 符号の結果 (スライド窓 : 8192)
ファイル名 サイズ LZSS 符号化 復号
------------------------------------------------
alice29.txt 152,089 68,332 0.878 0.345
asyoulik.txt 125,179 61,789 0.645 0.400
cp.html 24,603 10,278 0.114 0.121
fields.c 11,150 3,859 0.044 0.031
grammar.lsp 3,721 1,594 0.016 0.014
kennedy.xls 1,029,744 291,968 3.939 1.773
lcet10.txt 426,754 184.684 2.095 0.987
plrabn12.txt 481,861 247,780 2.637 1.272
ptt5 513,216 107,289 7.368 0.713
sum 38,240 17,500 0.308 0.113
xargs.1 4,227 2,198 0.020 0.032
------------------------------------------------
合計 2,810,784 997,271 18.064 5.801
# 符号化と復号の単位 : 秒
実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
ptt5 の圧縮率はハフマン符号よりも低下しましたが、それ以外のファイルではハフマン符号よりも高い圧縮率になりました。適応型辞書法は高い圧縮率を実現できる優れた方法であることがわかります。
処理時間ですが、ハフマン符号に比べて符号化の時間が大幅に増加しましたが、復号の時間は少し速くなりました。LZSS 符号は「圧縮には時間がかかるが解凍は速いアルゴリズム」であることが、評価結果からも確かめることができました。
なお、実行時間の結果は M.Hiroi のコーディング、実行したマシン、プログラミング言語などの環境に大きく依存しています。また、これらの環境だけではなく、データの種類によっても実行時間はかなり左右されます。興味のある方は、いろいろなデータをご自分の環境で試してみてください。
●参考文献, URL
- 植松友彦, 『文書データ圧縮アルゴリズム入門』, ＣＱ出版社, 1994
- LHa for UNIX with Autoconf - GitHub, (Koji Arai さん)
- 広井誠, 『LZ77 符号によるファイルの圧縮とその改良 (前編)』, Interface 2006 年 6 月号, ＣＱ出版社
●プログラムリスト１
#
# lzss.py : LZSS coding
#
# Copyright (C) 2007-2022 Makoto Hiroi
#
import argparse, os.path, time
from bitio import *
# 定数
MIN_LEN = 3
MAX_LEN = 18
LEN_BITS = 4
POS_BITS = 13
# スライド窓
class Slide:
def __init__(self, s):
self.stream = s
self.size = 1 << POS_BITS
self.limit = self.size * 2
self.link = [None] * self.size
self.ht = {}
self.buff = [0] * (self.limit + MAX_LEN)
self.data_size = self.fread(0, self.limit + MAX_LEN)
self.match_len = 0
self.match_pos = 0
# ハッシュ値を求める
def hash_value(self, rp):
value = 0
for x in range(MIN_LEN):
value = (value << 8) + self.buff[rp + x]
return value
# データ入力
def fread(self, start, size):
for i in range(size):
c = self.stream.getc()
if c is None: return i
self.buff[start + i] = c
return size
# データ移動
def move_data(self, to, from_, size):
for n in range(size):
self.buff[to + n] = self.buff[from_ + n]
# スライド窓の更新
def update(self, rp):
if self.data_size < self.limit + MAX_LEN: return rp
# buffer update
self.move_data(0, self.size, self.size + MAX_LEN)
n = self.fread(self.size + MAX_LEN, self.size)
self.data_size = self.size + MAX_LEN + n
# hash update
for k, v in list(self.ht.items()):
if v < self.size:
del self.ht[k]
else:
self.ht[k] = v - self.size
for x in range(self.size):
v = self.link[x]
if v == None or v < self.size:
self.link[x] = None
else:
self.link[x] = v - self.size
return rp - self.size
# データの挿入
def insert(self, rp):
value = self.hash_value(rp)
if value in self.ht:
self.link[rp & (self.size - 1)] = self.ht[value]
else:
self.link[rp & (self.size - 1)] = None
self.ht[value] = rp
# 最長一致列の探索
def search(self, rp):
b = self.buff
value = self.hash_value(rp)
limit = rp - self.size
self.match_len = 0
self.match_pos = 0
if value in self.ht:
n = self.ht[value]
while n is not None and n >= limit:
if b[rp + self.match_len] == b[n + self.match_len]:
x = 0
while x < MAX_LEN:
if b[rp + x] != b[n + x]: break
x += 1
if self.match_len < x:
self.match_len = x
self.match_pos = n
if x == MAX_LEN: break
n = self.link[n & (self.size - 1)]
# データの終端をチェック
if self.match_len >= self.data_size - rp:
self.match_len = self.data_size - rp
# LZSS 符号 : 符号化
def encode(fin, fout):
s = Slide(fin)
rp = 0
while rp < s.data_size:
s.search(rp)
if s.match_len < MIN_LEN:
num = 1
fout.putbit(0)
fout.putbits(8, s.buff[rp])
else:
num = s.match_len
fout.putbit(1)
fout.putbits(LEN_BITS, num - MIN_LEN)
fout.putbits(POS_BITS, rp - s.match_pos - 1)
for _ in range(num):
s.insert(rp)
rp += 1
if rp >= s.limit: rp = s.update(rp)
# 符号化
def encode_file(name1, name2):
size = os.path.getsize(name1)
with ByteIO(name1, ROPEN) as fin, BitIO(name2, WOPEN) as fout:
fout.putbits(32, size)
if size > 0: encode(fin, fout)
# LZSS 符号 : 復号
def decode(fin, fout, size):
rp = 0
buff = [0] * (1 << POS_BITS)
while size > 0:
if fin.getbit() == 1:
num = fin.getbits(LEN_BITS) + MIN_LEN
pos = rp - (fin.getbits(POS_BITS) + 1)
if pos < 0: pos += len(buff)
for _ in range(num):
c = buff[pos]
fout.putc(c)
buff[rp] = c
pos += 1
rp += 1
if pos >= len(buff): pos = 0
if rp >= len(buff): rp = 0
else:
num = 1
c = fin.getbits(8)
fout.putc(c)
buff[rp] = c
rp += 1
if rp >= len(buff): rp = 0
size -= num
# 復号
def decode_file(name1, name2):
with BitIO(name1, ROPEN) as fin, ByteIO(name2, WOPEN) as fout:
size = fin.getbits(32)
if size > 0: decode(fin, fout, size)
# オプション解析
parser = argparse.ArgumentParser(description='LZSS符号')
parser.add_argument('name1', help='入力ファイル')
parser.add_argument('name2', help='出力ファイル')
parser.add_argument('-e', '--encode', action='store_true', help='符号化')
parser.add_argument('-d', '--decode', action='store_true', help='復号')
args = parser.parse_args()
# 実行
s = time.time()
if args.encode and not args.decode:
encode_file(args.name1, args.name2)
elif args.decode:
decode_file(args.name1, args.name2)
else:
print('option error')
e = time.time()
print('{:.3f}'.format(e - s))
改訂 2022 年 9 月 17 日