可逆圧縮と非可逆圧縮
連続回数と過去の列への参照を使い、圧縮後のデータを復元して照合します。
説明
可逆圧縮は元のデータを完全に復元できる変換です。連続する同じ値を回数でまとめるランレングスや、前に現れた列への参照を使う辞書方式などがあります。どの方法も全ての入力を短くできるわけではなく、データの規則性と形式の付加情報が影響します。
同じ文字が続く列を回数で符号化し、ABCの繰り返しを後方参照で復元します。次にzlibで二種類のバイト列を圧縮・復元し、最後に値を10刻みへ丸める非可逆変換と比較します。
1連続した同じ文字をまとめる
AAAAABBBBCCを、連続回数と文字の組へ変換します。別の位置に同じ文字が出ても、連続していなければ別の組です。
from itertools import groupby連続区間をまとめる; text = 'AAAAABBBBCC'繰り返しのある入力; runs = [(sum(1 for _ in group), ch) for ch, group in groupby(text)]回数と文字へ変換; runs連続区間5A・4B・2Cの3組です。元は11文字でした。ここでは回数とASCII文字をそれぞれ1バイトに格納する形式を定めます。
2バイト列へ符号化
各組を回数・文字の順で2バイトにします。この例の回数は255以下、文字はASCII範囲です。
encoded = bytes(value for count, ch in runs for value in (count, ord(ch)))回数とASCII値を格納; encoded.hex(' ')符号化したバイト列, len(text.encode('ascii')), len(encoded)元と符号化後の長さ05 41 04 42 02 43の6バイトになり、元の11バイトより短くなりました。256回以上の連続は区間を分けるなど別の規則が必要です。
3回数から復元する
2バイトごとに回数と文字を読み、回数分だけ文字を繰り返します。
restored = ''.join(chr(encoded[i+1])*encoded[i] for i in range(0, len(encoded), 2))組から元の文字数を復元; restored, restored == text復元結果を照合元の文字列と完全に一致します。この形式では、文字0などを回数として取り違えないよう、常に2バイト単位で解釈します。
4繰り返しがないと増える
ABABABは同じ文字が連続しないため、各文字が回数1の組になります。
alternating = 'ABABAB'交互に出る文字; alternate_runs = [(sum(1 for _ in group), ch) for ch, group in groupby(alternating)]連続区間へ分ける; alternate_runs, len(alternating), 2*len(alternate_runs)元と符号化後の長さ元6バイトに対して12バイトです。全体にはABの繰り返しがありますが、単一文字の連続回数では活用できません。別の規則性に対応する圧縮方式が必要です。
5過去の列を参照する
ABCを出力した後、距離3だけ前から6文字コピーするとABCABCを追加できます。コピーしたばかりの文字も次の参照元になります。
output = list('ABC')先頭の文字をそのまま出力; distance = 3; length = 6後方参照の距離と長さ; output, (distance, length)初期出力と参照後方参照の組は(距離3, 長さ6)です。長さが距離を超えるので、最初の3文字だけを一度に切り出すのではなく、出力を伸ばしながら一文字ずつコピーします。
6重なるコピーを復元
現在の末尾から3文字前を読み、末尾へ加える処理を6回行います。次の段階で通常の文字Xを追加します。
for _ in range(length):6文字分コピー
output.append(output[-distance])現在末尾から3文字前を追加
print(''.join(output))伸びる出力ABCABCABCまで伸びます。最初のABC、参照(3,6)、末尾Xという表現なら、繰り返しを過去の列として表せます。この表示は後方参照の仕組みを示し、特定形式のビット符号までは定めていません。
7末尾文字と実用の圧縮形式
Xを足して元の列と照合し、zlibでは繰り返すバイト列と256種類のバイト列を圧縮します。
output.append('X')末尾の通常文字; import zlib圧縮ライブラリ; repeated = b'ABC'*100; varied = bytes(range(256))二種類の入力; packed = [zlib.compress(data) for data in [repeated, varied]]圧縮; ''.join(output)後方参照の復元結果, [(len(raw), len(blob), zlib.decompress(blob) == raw) for raw, blob in zip([repeated, varied], packed)]元サイズ・圧縮サイズ・復元一致復元例はABCABCABCXです。zlibの両方で復元一致はTrueですが、繰り返しの多い入力と全種類の値が一回ずつ出る入力では圧縮後の長さが違います。zlib形式にはヘッダーや検査値もあり、小さい入力では元より大きくなることがあります。
8情報を捨てる変換
11・14・19・21を10刻みで切り捨てます。異なる値が同じ値へ変わるため、変換後の値だけでは元を一意に復元できません。
samples = [11, 14, 19, 21]元の値; reduced = [(x//10)*10 for x in samples]10刻みへ量子化; list(zip(samples, reduced))変換前後, len(set(samples)), len(set(reduced))異なる値の種類数11・14・19は全て10になります。この量子化は非可逆変換の例で、データを格納する圧縮形式そのものではありません。画像や音声では、許容する誤差とサイズの関係を考えて情報を減らし、その後に符号化します。
まとめ
ランレングスは同一値の連続に向き、繰り返しがないと回数の分だけ大きくなります。
後方参照は過去の列を再利用し、重なったコピーでは出力しながら参照範囲を伸ばせます。
可逆方式は復元一致を照合できます。量子化のように複数の値を一つにまとめる変換は元へ一意に戻せません。
操作履歴と解説を振り返れます。
Python 3
from itertools import groupby; text = 'AAAAABBBBCC'; runs = [(sum(1 for _ in group), ch) for ch, group in groupby(text)]; runs[(5, 'A'), (4, 'B'), (2, 'C')]
encoded = bytes(value for count, ch in runs for value in (count, ord(ch))); encoded.hex(' '), len(text.encode('ascii')), len(encoded)('05 41 04 42 02 43', 11, 6)restored = ''.join(chr(encoded[i+1])*encoded[i] for i in range(0, len(encoded), 2)); restored, restored == text('AAAAABBBBCC', True)alternating = 'ABABAB'; alternate_runs = [(sum(1 for _ in group), ch) for ch, group in groupby(alternating)]; alternate_runs, len(alternating), 2*len(alternate_runs)([(1, 'A'), (1, 'B'), (1, 'A'), (1, 'B'), (1, 'A'), (1, 'B')], 6, 12)
output = list('ABC'); distance = 3; length = 6; output, (distance, length)(['A', 'B', 'C'], (3, 6))
for _ in range(length):
output.append(output[-distance])
print(''.join(output))ABCA ABCAB ABCABC ABCABCA ABCABCAB ABCABCABC
output.append('X'); import zlib; repeated = b'ABC'*100; varied = bytes(range(256)); packed = [zlib.compress(data) for data in [repeated, varied]]; ''.join(output), [(len(raw), len(blob), zlib.decompress(blob) == raw) for raw, blob in zip([repeated, varied], packed)]('ABCABCABCX', [(300, 15, True), (256, 267, True)])samples = [11, 14, 19, 21]; reduced = [(x//10)*10 for x in samples]; list(zip(samples, reduced)), len(set(samples)), len(set(reduced))([(11, 10), (14, 10), (19, 10), (21, 20)], 4, 2)
演習完了