コラム
2025/04/30
第107回 プログラミングについて『ファイルを圧縮してみよう！ その6』
～ＬＺ法で圧縮する その１～
前回まではハフマン法を使っての圧縮、伸長について考えてきました。今回からはＬＺ法について考えていきましょう。ＬＺ法は Ｌｅｍｐｅｌという人とＺｉｖという人が考え出した方法の総称なのだそうです。この圧縮方法は基本の考え方は１つなのですが実現方法に多くの方法があるようです。ここではその基本に従って考えていきます。
ハフマン法は文字の頻度の偏りを利用した圧縮法でしたが、ＬＺ法は頻度は利用しません。次の文字列を見て下さい。
ABACABA
この文字列で後半の ABA は最初のもの即ち４文字前から３文字同じですので、
ABAC(4,3)
と表現したとします。４と３を１バイトで表現したら合計２バイトですので、１バイト減ったことになります。次に、
ABABABABAB
では３文字目からは２文字前から８文字同じですので、
AB(2,8)
と表現することができます。多分ここですごく不思議な感じがするかも知れませんが、じっくり考えてみるとなんとなく理屈が通っているような気がしませんか。
圧縮した文字列を元に戻すには ABAC(4,3) の場合は、
ABAC
ABACA
ABACAB
ABACABA
という順番で元に戻す事ができ、AB(2,8) は、
AB
ABA
ABAB
ABABA
ABABAB
ABABABA
ABABABAB
ABABABABA
ABABABABAB
という順序で元にもどすことができるので理屈は通っています。
ＬＺ法の基本的な考え方はこれだけです。この考え方をどのように実現するかで圧縮率もかなり違うようです。ここではまさにこの基本に従ってプログラムを作っていくことにします。大前提として、文字数を示す値は１バイトを使用することにします。ですので最大で２５５文字前、長さも２５５文字までとします。またハフマン法のときと同じく入出力ファイル名も固定とします。
圧縮速度の要になる文字の検索方法は単純なものとしますので、実行速度はあまり速くはありません。おおよそ次のような方法で検索することにします。
予め２５５文字分の文字配列を用意しておきます。１文字ずつ文字を入力ファイルから読み込み、読み込んだ文字がその配列になければそのままの文字を出力し、その文字を文字配列に追加します。文字が発見されたときにはその文字を配列に追加し、次の文字を読み込みます。そしてその文字をそれまでに発見された文字に追加し、あるか否かを調べます。発見されればこの操作を繰り返し、発見されなかったときには発見された最大の長さの文字列を最初に説明したように置き換えます。文字配列は２５５文字以上になったときには最初の文字を捨て、全体を１文字先頭方向にシフトさせます。
まずグローバルな変数と定数部分です。
#include <stdio.h>
#define IN_FNAME "z.z"
#define OUT_FNAME "x.x"
#define MAX_TEXT 256
char text[MAX_TEXT];
int ltext;
char ochar;
int ochar_remain;
FILE *ifp,*ofp;
殆どハフマン法のときと同じですので説明する部分は多くはありません。
text 配列は２５５文字前（このプログラムでは２５６文字分）までの文字列を貯えておくもので、この文字配列に目的の文字列があるか否かを調べるためのものです。
メイン関数は
main()
{
ifp=fopen( IN_FNAME,"rb");
ofp=fopen(OUT_FNAME,"wb");
ltext=0;
ochar_remain=8;
compress();
fclose(ifp);
fclose(ofp);
}
で、これもハフマン法のときと殆ど変りませんので説明の必要はないと思います。
問題の compress() は次の通りです。ちょっとスッキリしなかったのですが我慢して理解して下さい。
compress()
{
char match[MAX_TEXT]; /* 検索する文字列を入れる配列 */
int lmatch; /* 検索する文字列の長さ */
int prev; /* 発見された文字列の位置
（何文字前かという値を入れます）*/
int p;
char c;
prev=0; /* 初期状態にします */
lmatch=0;
while(1){
c=fgetc(ifp); /* １文字読み込みます */
if(feof(ifp))break;
while(1){
match[lmatch]=c; /* 検索する文字列の最後に読み込んだ
１文字を追加し、２５５文字前まで
にあるか否かを調べます */
p=search(match,lmatch+1); /* 発見されたときには現在の位置から
何文字前かという値が返ります。
発見されなかったときには０が返りま
す。*/
if(p){ /* 発見された */
prev=p-lmatch; /* search 関数から返ってくるのは現在の
文字の位置から何文字前かという値なの
でその位置から検索文字の長さを引いて
検索文字の先頭位置から何文字前かと
いう値にします*/
lmatch++;
if(lmatch>=MAX_TEXT-1){ /* 検索文字の長さが２５５になったとき
には何文字前から、何文字一致してい
るという情報を書き込みます。
その後、検索文字は１文字目からに
なりますので prev と lmatch を
初期化します。*/
output_same(prev,lmatch);
prev=0;
lmatch=0;
}
}
else if(prev){ /* 現在の文字列と同じものがなかったと
きで、１文字短い文字列が発見されて
いる */
/* 一致している文字列が２文字以上のと
きには一致している文字列の情報を、
そうでないときにはその文字を出力
します */
if(lmatch>=2)output_same(prev,lmatch);
else output_char(match[0]);
prev=0; /* 初期状態に戻します */
lmatch=0;
/* 読み込んだ文字が次の検索の最初の
文字になるので continue 文で検索
を再開します */
continue;
}
else{ /* 発見されている文字がないので、
読み込んだ文字を出力します */
output_char(c);
}
break; /* while 文を終了させます */
}
add_char(c); /* ２５５文字前までの文字配列に１文字
追加します */
}
/* 入力ファイルをすべて読み込み終わったので一致している文字列があればそれを出力します */
if(prev){
if(lmatch>=2)output_same(prev,lmatch);
else output_char(match[0]);
}
/* ファイルの終了コードを書き込みます
この意味は後で説明します */
output_same(0,0);
add_bits(0,7); /* 最後の１バイトが出力されていないと
きには出力します */
}
かなり長いので読むのがちょっと辛いと思います。とりあえずは理屈通りになっていますので何度も読めばだんだんと動きが分かってくると思います。
次に add_bits 関数を紹介しましょう。ハフマン法のプログラムのときには可変長のビット列を出力しましたので、引数は０１という文字列を羅列したものを引数にしましたが、ＬＺ法では固定長を出力するので引数を変えてあります。
add_bits(v,l)
int v,l;
{
while(l-- >0){
ochar<<=1;
ochar_remain--;
if(v & (1<<l))ochar|=1;
else ochar|=0;
if(ochar_remain<=0){
fputc(ochar,ofp);
ochar_remain=8;
}
}
}
第１引数 v はビット列を出力したい整数値、第２引数 l は出力するビット数で、１としたときには最下位の１ビット、２としたときには１ビット目、０ビット目の順で２つのビットが出力されます。
ここで出力データについて１つ約束事を決めておきましょう。
・文字をそのまま出力するときのビット列
0 cccccccc
|
１文字分の８ビット
・前の文字列と同じときのビット列
1 pppppppp llllllll
| |
| 文字列の長さ
文字列の位置（何文字前を示す値）
・ファイルの終了
1 00000000 00000000
前の文字列と同じときのビット列は pppppppp が必ず 00000000 以外になりますので、
00000000 のときをファイルの終了ということにしておきます。
それでは文字をそのまま出力する output_char 関数本体は、
output_char(c)
char c;
{
add_bits( 0,1);
add_bits((int)c,8);
}
ということになります。これは問題ありませんね。前のものと同じ文字列を出力する関数 output_same も同様に
output_same(prev,len)
int prev,len;
{
add_bits( 1,1);
add_bits(prev,8);
add_bits( len,8);
}
となります。
今回は一気に圧縮するプログラムを作成してしまいましょう。
前の２５５文字の文字配列に１文字追加する関数は、
add_char(c)
char c;
{
if(ltext>=MAX_TEXT){
memcpy(text,text+1,MAX_TEXT-1);
text[ltext-1]=c;
}
else{
text[ltext++]=c;
}
}
となります。文字配列が一杯になったときには先頭の１文字を捨て、残りの文字列を先頭方向に１文字ずらします。
最後に前の２５５文字内の文字列を検索する関数は、
search(match,lmatch)
char *match;
int lmatch;
{
int i,l;
l=ltext-lmatch;
for(i=0;i<=l;i++){
if(memcmp(text+i,match,lmatch)==0)return ltext-i;
}
return 0;
}
となります。この関数は単純に文字配列の先頭から順に比較していく単純な方法ですの
で、難しくはないと思います。
これで圧縮は完成です。全文を紹介しましょう。
#include <stdio.h>
#define IN_FNAME "z.z"
#define OUT_FNAME "x.x"
#define MAX_TEXT 256
char text[MAX_TEXT];
int ltext;
char ochar;
int ochar_remain;
FILE *ifp,*ofp;
main()
{
ifp=fopen( IN_FNAME,"rb");
ofp=fopen(OUT_FNAME,"wb");
ltext=0;
ochar_remain=8;
compress();
fclose(ifp);
fclose(ofp);
}
compress()
{
char match[MAX_TEXT];
int lmatch;
int prev;
int p;
char c;
prev=0;
lmatch=0;
while(1){
c=fgetc(ifp);
if(feof(ifp))break;
while(1){
match[lmatch]=c;
p=search(match,lmatch+1);
if(p){
prev=p-lmatch;
lmatch++;
if(lmatch>=MAX_TEXT-1){
output_same(prev,lmatch);
prev=0;
lmatch=0;
}
}
else if(prev){
if(lmatch>=2)output_same(prev,lmatch);
else output_char(match[0]);
prev=0;
lmatch=0;
continue;
}
else{
output_char(c);
}
break;
}
add_char(c);
}
if(prev){
if(lmatch>=2)output_same(prev,lmatch);
else output_char(match[0]);
}
output_same(0,0);
add_bits(0,7);
}
add_bits(v,l)
int v,l;
{
while(l-- >0){
ochar<<=1;
ochar_remain--;
if(v & (1<<l))ochar|=1;
else ochar|=0;
if(ochar_remain<=0){
fputc(ochar,ofp);
ochar_remain=8;
}
}
}
output_char(c)
char c;
{
add_bits( 0,1);
add_bits((int)c,8);
}
output_same(prev,len)
int prev,len;
{
add_bits( 1,1);
add_bits(prev,8);
add_bits( len,8);
}
add_char(c)
char c;
{
if(ltext>=MAX_TEXT){
memcpy(text,text+1,MAX_TEXT-1);
text[ltext-1]=c;
}
else{
text[ltext++]=c;
}
}
search(match,lmatch)
char *match;
int lmatch;
{
int i,l;
l=ltext-lmatch;
for(i=0;i<=l;i++){
if(memcmp(text+i,match,lmatch)==0)return ltext-i;
}
return 0;
}
なんだか思ったより短いプログラムで完成しました。
このプログラムはＬＺ法の基本中の基本のアルゴリズムを使用していますので、圧縮率はそれ程高くはありません。それでもハフマン法のものと比べればかなり高くはなっています。また実行速度も我慢の限界ギリギリの速さ（遅さ？）です。実際に私のパソコンで１．３メガのファイルを圧縮するのに５５秒かかってしまいました。ＬＨＡでは７秒でしたのでその差はガッカリするほどです。
次回はこのプログラムで圧縮したファイルを伸長するのではなく、もう少しこのプログラムに手を加え実行時間の短縮に挑戦してみる予定です。
前回まではハフマン法を使っての圧縮、伸長について考えてきました。今回からはＬＺ法について考えていきましょう。ＬＺ法は Ｌｅｍｐｅｌという人とＺｉｖという人が考え出した方法の総称なのだそうです。この圧縮方法は基本の考え方は１つなのですが実現方法に多くの方法があるようです。ここではその基本に従って考えていきます。
ハフマン法は文字の頻度の偏りを利用した圧縮法でしたが、ＬＺ法は頻度は利用しません。次の文字列を見て下さい。
ABACABA
この文字列で後半の ABA は最初のもの即ち４文字前から３文字同じですので、
ABAC(4,3)
と表現したとします。４と３を１バイトで表現したら合計２バイトですので、１バイト減ったことになります。次に、
ABABABABAB
では３文字目からは２文字前から８文字同じですので、
AB(2,8)
と表現することができます。多分ここですごく不思議な感じがするかも知れませんが、じっくり考えてみるとなんとなく理屈が通っているような気がしませんか。
圧縮した文字列を元に戻すには ABAC(4,3) の場合は、
ABAC
ABACA
ABACAB
ABACABA
という順番で元に戻す事ができ、AB(2,8) は、
AB
ABA
ABAB
ABABA
ABABAB
ABABABA
ABABABAB
ABABABABA
ABABABABAB
という順序で元にもどすことができるので理屈は通っています。
ＬＺ法の基本的な考え方はこれだけです。この考え方をどのように実現するかで圧縮率もかなり違うようです。ここではまさにこの基本に従ってプログラムを作っていくことにします。大前提として、文字数を示す値は１バイトを使用することにします。ですので最大で２５５文字前、長さも２５５文字までとします。またハフマン法のときと同じく入出力ファイル名も固定とします。
圧縮速度の要になる文字の検索方法は単純なものとしますので、実行速度はあまり速くはありません。おおよそ次のような方法で検索することにします。
予め２５５文字分の文字配列を用意しておきます。１文字ずつ文字を入力ファイルから読み込み、読み込んだ文字がその配列になければそのままの文字を出力し、その文字を文字配列に追加します。文字が発見されたときにはその文字を配列に追加し、次の文字を読み込みます。そしてその文字をそれまでに発見された文字に追加し、あるか否かを調べます。発見されればこの操作を繰り返し、発見されなかったときには発見された最大の長さの文字列を最初に説明したように置き換えます。文字配列は２５５文字以上になったときには最初の文字を捨て、全体を１文字先頭方向にシフトさせます。
まずグローバルな変数と定数部分です。
#include <stdio.h>
#define IN_FNAME "z.z"
#define OUT_FNAME "x.x"
#define MAX_TEXT 256
char text[MAX_TEXT];
int ltext;
char ochar;
int ochar_remain;
FILE *ifp,*ofp;
殆どハフマン法のときと同じですので説明する部分は多くはありません。
text 配列は２５５文字前（このプログラムでは２５６文字分）までの文字列を貯えておくもので、この文字配列に目的の文字列があるか否かを調べるためのものです。
メイン関数は
main()
{
ifp=fopen( IN_FNAME,"rb");
ofp=fopen(OUT_FNAME,"wb");
ltext=0;
ochar_remain=8;
compress();
fclose(ifp);
fclose(ofp);
}
で、これもハフマン法のときと殆ど変りませんので説明の必要はないと思います。
問題の compress() は次の通りです。ちょっとスッキリしなかったのですが我慢して理解して下さい。
compress()
{
char match[MAX_TEXT]; /* 検索する文字列を入れる配列 */
int lmatch; /* 検索する文字列の長さ */
int prev; /* 発見された文字列の位置
（何文字前かという値を入れます）*/
int p;
char c;
prev=0; /* 初期状態にします */
lmatch=0;
while(1){
c=fgetc(ifp); /* １文字読み込みます */
if(feof(ifp))break;
while(1){
match[lmatch]=c; /* 検索する文字列の最後に読み込んだ
１文字を追加し、２５５文字前まで
にあるか否かを調べます */
p=search(match,lmatch+1); /* 発見されたときには現在の位置から
何文字前かという値が返ります。
発見されなかったときには０が返りま
す。*/
if(p){ /* 発見された */
prev=p-lmatch; /* search 関数から返ってくるのは現在の
文字の位置から何文字前かという値なの
でその位置から検索文字の長さを引いて
検索文字の先頭位置から何文字前かと
いう値にします*/
lmatch++;
if(lmatch>=MAX_TEXT-1){ /* 検索文字の長さが２５５になったとき
には何文字前から、何文字一致してい
るという情報を書き込みます。
その後、検索文字は１文字目からに
なりますので prev と lmatch を
初期化します。*/
output_same(prev,lmatch);
prev=0;
lmatch=0;
}
}
else if(prev){ /* 現在の文字列と同じものがなかったと
きで、１文字短い文字列が発見されて
いる */
/* 一致している文字列が２文字以上のと
きには一致している文字列の情報を、
そうでないときにはその文字を出力
します */
if(lmatch>=2)output_same(prev,lmatch);
else output_char(match[0]);
prev=0; /* 初期状態に戻します */
lmatch=0;
/* 読み込んだ文字が次の検索の最初の
文字になるので continue 文で検索
を再開します */
continue;
}
else{ /* 発見されている文字がないので、
読み込んだ文字を出力します */
output_char(c);
}
break; /* while 文を終了させます */
}
add_char(c); /* ２５５文字前までの文字配列に１文字
追加します */
}
/* 入力ファイルをすべて読み込み終わったので一致している文字列があればそれを出力します */
if(prev){
if(lmatch>=2)output_same(prev,lmatch);
else output_char(match[0]);
}
/* ファイルの終了コードを書き込みます
この意味は後で説明します */
output_same(0,0);
add_bits(0,7); /* 最後の１バイトが出力されていないと
きには出力します */
}
かなり長いので読むのがちょっと辛いと思います。とりあえずは理屈通りになっていますので何度も読めばだんだんと動きが分かってくると思います。
次に add_bits 関数を紹介しましょう。ハフマン法のプログラムのときには可変長のビット列を出力しましたので、引数は０１という文字列を羅列したものを引数にしましたが、ＬＺ法では固定長を出力するので引数を変えてあります。
add_bits(v,l)
int v,l;
{
while(l-- >0){
ochar<<=1;
ochar_remain--;
if(v & (1<<l))ochar|=1;
else ochar|=0;
if(ochar_remain<=0){
fputc(ochar,ofp);
ochar_remain=8;
}
}
}
第１引数 v はビット列を出力したい整数値、第２引数 l は出力するビット数で、１としたときには最下位の１ビット、２としたときには１ビット目、０ビット目の順で２つのビットが出力されます。
ここで出力データについて１つ約束事を決めておきましょう。
・文字をそのまま出力するときのビット列
0 cccccccc
|
１文字分の８ビット
・前の文字列と同じときのビット列
1 pppppppp llllllll
| |
| 文字列の長さ
文字列の位置（何文字前を示す値）
・ファイルの終了
1 00000000 00000000
前の文字列と同じときのビット列は pppppppp が必ず 00000000 以外になりますので、
00000000 のときをファイルの終了ということにしておきます。
それでは文字をそのまま出力する output_char 関数本体は、
output_char(c)
char c;
{
add_bits( 0,1);
add_bits((int)c,8);
}
ということになります。これは問題ありませんね。前のものと同じ文字列を出力する関数 output_same も同様に
output_same(prev,len)
int prev,len;
{
add_bits( 1,1);
add_bits(prev,8);
add_bits( len,8);
}
となります。
今回は一気に圧縮するプログラムを作成してしまいましょう。
前の２５５文字の文字配列に１文字追加する関数は、
add_char(c)
char c;
{
if(ltext>=MAX_TEXT){
memcpy(text,text+1,MAX_TEXT-1);
text[ltext-1]=c;
}
else{
text[ltext++]=c;
}
}
となります。文字配列が一杯になったときには先頭の１文字を捨て、残りの文字列を先頭方向に１文字ずらします。
最後に前の２５５文字内の文字列を検索する関数は、
search(match,lmatch)
char *match;
int lmatch;
{
int i,l;
l=ltext-lmatch;
for(i=0;i<=l;i++){
if(memcmp(text+i,match,lmatch)==0)return ltext-i;
}
return 0;
}
となります。この関数は単純に文字配列の先頭から順に比較していく単純な方法ですの
で、難しくはないと思います。
これで圧縮は完成です。全文を紹介しましょう。
#include <stdio.h>
#define IN_FNAME "z.z"
#define OUT_FNAME "x.x"
#define MAX_TEXT 256
char text[MAX_TEXT];
int ltext;
char ochar;
int ochar_remain;
FILE *ifp,*ofp;
main()
{
ifp=fopen( IN_FNAME,"rb");
ofp=fopen(OUT_FNAME,"wb");
ltext=0;
ochar_remain=8;
compress();
fclose(ifp);
fclose(ofp);
}
compress()
{
char match[MAX_TEXT];
int lmatch;
int prev;
int p;
char c;
prev=0;
lmatch=0;
while(1){
c=fgetc(ifp);
if(feof(ifp))break;
while(1){
match[lmatch]=c;
p=search(match,lmatch+1);
if(p){
prev=p-lmatch;
lmatch++;
if(lmatch>=MAX_TEXT-1){
output_same(prev,lmatch);
prev=0;
lmatch=0;
}
}
else if(prev){
if(lmatch>=2)output_same(prev,lmatch);
else output_char(match[0]);
prev=0;
lmatch=0;
continue;
}
else{
output_char(c);
}
break;
}
add_char(c);
}
if(prev){
if(lmatch>=2)output_same(prev,lmatch);
else output_char(match[0]);
}
output_same(0,0);
add_bits(0,7);
}
add_bits(v,l)
int v,l;
{
while(l-- >0){
ochar<<=1;
ochar_remain--;
if(v & (1<<l))ochar|=1;
else ochar|=0;
if(ochar_remain<=0){
fputc(ochar,ofp);
ochar_remain=8;
}
}
}
output_char(c)
char c;
{
add_bits( 0,1);
add_bits((int)c,8);
}
output_same(prev,len)
int prev,len;
{
add_bits( 1,1);
add_bits(prev,8);
add_bits( len,8);
}
add_char(c)
char c;
{
if(ltext>=MAX_TEXT){
memcpy(text,text+1,MAX_TEXT-1);
text[ltext-1]=c;
}
else{
text[ltext++]=c;
}
}
search(match,lmatch)
char *match;
int lmatch;
{
int i,l;
l=ltext-lmatch;
for(i=0;i<=l;i++){
if(memcmp(text+i,match,lmatch)==0)return ltext-i;
}
return 0;
}
なんだか思ったより短いプログラムで完成しました。
このプログラムはＬＺ法の基本中の基本のアルゴリズムを使用していますので、圧縮率はそれ程高くはありません。それでもハフマン法のものと比べればかなり高くはなっています。また実行速度も我慢の限界ギリギリの速さ（遅さ？）です。実際に私のパソコンで１．３メガのファイルを圧縮するのに５５秒かかってしまいました。ＬＨＡでは７秒でしたのでその差はガッカリするほどです。
次回はこのプログラムで圧縮したファイルを伸長するのではなく、もう少しこのプログラムに手を加え実行時間の短縮に挑戦してみる予定です。
