JPH08265167A

JPH08265167A - データ圧縮装置

Info

Publication number: JPH08265167A
Application number: JP6234795A
Authority: JP
Inventors: Masaru Kobayashi; 優小林
Original assignee: Casio Computer Co Ltd
Current assignee: Casio Computer Co Ltd
Priority date: 1995-03-22
Filing date: 1995-03-22
Publication date: 1996-10-11

Abstract

(57)【要約】【目的】データ圧縮装置の規模を小型化するととも
に、そのコストを低減することを目的とする。【構成】制御部１０２は、入力レジスタ１０１にスト
アされた入力文字が部分文字列の先頭文字であるか否か
判別し、この判別結果に応じて各一致位置ポインタ１０
９〜１１２に保持させたアドレスを変更しながら、辞書
メモリ１０３から読み出した文字と入力文字を比較回路
１０６を用いて比較していくことで最大一致系列を検出
する。この最大一致系列の一致長は一致長カウンタ１１
４によりカウントし、その一致長、及び減算器１１６か
ら出力されるそれの一致位置を一致フラグとともに符号
出力部１１５から出力させる。また、制御部１０２は、
入力ポインタ１１３の書込アドレスを変更しながら、入
力された文字を随時辞書メモリ１０３に書き込む。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データを入力しながら
それを圧縮する技術に関する。

【０００２】

【従来の技術】近年、コンピュータや通信等の各分野に
おいては扱うデータ量が急速に増大している。このデー
タ量の増大に伴い、データの記憶に要するコスト、電話
料金といった通信に要するコストが増大していることか
ら、このようなコストを抑えるために、データ列の中に
含まれる冗長性を取り除くことでそれを圧縮するデータ
圧縮技術が広く利用されてきている。データ圧縮技術
は、ファイル・アーカイバや分散ファイル・システム、
データ通信、音声・画像通信、コンピュータ・ネットワ
ークなどの分野では既に非常に重要な役割を果たしてお
り、これからさらにその重要度が増していくと考えられ
ている技術である。

【０００３】データ圧縮方式は、圧縮後のデータ列（圧
縮データ列）を元のデータ列（入力データ列）に復元す
る復号化を行った際の歪みの有無により、歪みを有する
有雑音圧縮（非可逆符号化）と、歪みがない無雑音圧縮
（可逆符号化）とに大別される。通常、有雑音圧縮は、
画像、音声といったある程度の歪みを許容できるデータ
に対して利用され、他方の無雑音圧縮は、ファイル（例
えばプログラム）や文書といった歪みが許されないデー
タに対して利用される。

【０００４】無雑音圧縮として今日広く利用されている
ものに、Ｌｅｍｐｅｌ−Ｚｉｖ方式（以降、ＬＺ方式と
記す）がある。このＬＺ方式は、文字列を読み込みなが
らその統計的な性質を抽出して符号化を行う、所謂適応
符号化方式の一種である。ここでの文字の定義は、符号
化対象である入力データ列の最小の処理単位のことであ
る。

【０００５】図５は、上記ＬＺ方式を採用した従来のデ
ータ圧縮装置５００の構成を示すブロック図である。こ
の図５を参照して、従来のデータ圧縮装置５００につい
て説明する。

【０００６】このデータ圧縮装置５００は、図５に示す
ように、外部から入力した入力データ列（文字列）ＩＷ
を記憶する入力メモリ５０１と、該入力メモリ５０１内
の符号化が終了した部分文字列が順次記憶される辞書メ
モリ５０２と、入力メモリ５０１から読み出された文字
を辞書メモリ５０２から読み出された文字と比較する比
較回路５０３と、装置５００全体の制御を実行する制御
部５０４と、制御部５０４が生成した符号語が格納され
る符号メモリ５０５、及びフラグレジスタ５０６と、符
号メモリ５０５、及びフラグレジスタ５０６に格納され
た符号語を出力するために用いられる出力メモリ５０７
とから構成される。

【０００７】上記の構成において、辞書メモリ５０２に
記憶された文字列は辞書として利用される。制御部５０
４は、入力メモリ５０１、辞書メモリ５０２の文字を読
み出すアドレスを変更させながら、比較回路５０３を用
いて各メモリ５０１、５０２から読み出された文字が一
致するか否かを比較していくことにより、入力メモリ５
０１の符号化の対象となっている部分文字列と一致する
辞書メモリ５０２の部分文字列（一致系列）を検索す
る。

【０００８】この制御部５０４による一致系列（部分文
字列）の検索は、例えば次のようにして行われる。先
ず、現時点の符号化を行う対象となっている部分文字列
の先頭文字と一致する文字を、辞書メモリ５０２の最も
過去に記憶された文字から順次探していき、この先頭文
字と一致する文字を見つける。先頭文字と一致する文字
を見つけると、その文字が記憶されているアドレス（以
降、一致位置と記す）を記憶した後、辞書メモリ５０２
のこの見つけた文字に続く文字と入力メモリ５０１の部
分文字列の先頭文字に続く文字とを順次比較していき、
一致すると比較した文字数（一致長）をカウントする。
このカウントは２つの文字が一致しないと比較するまで
継続して行い、カウントした値（一致長）は既に記憶し
た先頭アドレスと対応させて記憶する。これにより１つ
の一致系列の抽出が終了し、このような一致系列の抽出
を繰り返し行い、抽出した一致系列のなかからその一致
長が最大のものを最大一致系列として抽出する。

【０００９】制御部５０４は、この検索を行った結果に
基づいて符号化を行う。具体的には、上記のようにして
見つけた最大一致系列の長さが所定数以上であった場
合、一致フラグに“１”をセットしてこれをフラグレジ
スタ５０６に格納し、該最大一致系列の一致位置、及び
その一致長を符号メモリ５０５に格納する。反対に符号
化対象である部分文字列の先頭文字と一致する文字が辞
書メモリ５０２に見つけられなかった場合を含め、最大
一致系列の長さが所定数未満であった場合、一致フラグ
に“０”をセットしてこれをフラグレジスタ５０６に格
納し、該先頭文字を表すデータ（例えば、ＡＳＣＩＩコ
ード）を符号メモリ５０５にそのまま格納する。

【００１０】制御部５０４は、上記のようにして入力メ
モリ５０１の文字列に対する符号化を部分文字列に分け
て順次行うとともに、入力メモリ５０１、辞書メモリ５
０２に記憶させる内容（文字列）を更新する。具体的に
は、例えば入力メモリ５０１のある部分文字列に対する
符号化が終了すると、この符号化が終了した部分文字列
を辞書メモリ５０２に新たに登録し、入力メモリ５０１
にはこの部分文字列の文字数分、入力データ列ＩＷを新
たに書き込む。

【００１１】また、制御部５０４は、フラグレジスタ５
０６にそのビット数の一致フラグを格納すると、このフ
ラグレジスタ５０６、符号メモリ５０５に格納されてい
る内容を出力メモリ５０７に格納する。その後、この出
力メモリ５０７に格納された符号語を圧縮符号出力ＯＷ
として外部に出力する。

【００１２】上記の動作を繰り返すことで入力データ列
（文字列）ＩＷに対する圧縮が行われる。出力メモリ５
０７から随時出力される圧縮符号出力ＯＷは、例えば磁
気記憶装置に出力され、ここで磁気ディスク上に格納さ
れる。

【００１３】なお、圧縮符号出力（符号語）ＯＷの復号
は、過去に復号化した文字列を辞書として利用し、一致
フラグの値が“０”のときは符号語が表す文字、その値
が“１”のときは辞書として記憶している復号した文字
列から符号語に応じて部分文字列を抽出して複写してい
くことで行われる。

【００１４】

【発明が解決しようとする課題】しかしながら、上述し
た従来のデータ圧縮装置５００は、一致系列の抽出を繰
り返すことで最大一致系列を検索していることから、符
号化を行う文字列を記憶させておかなければならなかっ
た。符号化を行う文字列は入力メモリ５０１に記憶させ
ているが、このようなメモリを備えたことによって装置
５００が大型化していたという問題点があった。

【００１５】データ圧縮装置は、例えばコンピュータの
バスに接続して、その主記憶装置や外部記憶装置に記憶
させるデータの圧縮に利用される。このため、バス等に
接続して用いられるように、ＬＳＩ（Large Scale Inte
grated Circuit）化が望まれている。このＬＳＩ化を容
易とし、また、そのコストを抑えられるように、その規
模が小さいデータ圧縮装置が望まれていた。

【００１６】本発明の課題は、データ圧縮装置の規模を
小型化するとともに、そのコストを低減することにあ
る。

【００１７】

【課題を解決するための手段】本発明のデータ圧縮装置
は、過去に入力された文字列を記憶する記憶手段を備
え、該記憶手段に記憶された文字列を参照し、繰り返し
入力された部分文字列を検出することで文字列を表すデ
ータ量の圧縮を行うことを前提とし、以下の手段を備え
る。

【００１８】先ず、文字判別手段は、入力された文字が
部分文字列の先頭文字であるか否かを判別する。一致位
置記憶手段は、文字判別手段が入力された文字を先頭文
字と判別したとき、該入力された文字と一致する文字が
記憶されている記憶手段のアドレスを一致位置として記
憶する。

【００１９】読出手段は、先頭文字であると文字判別手
段が判別した文字に続く文字が入力される度に、該文字
の入力に応じて一致位置から順次アドレスを変更しなが
ら記憶手段に記憶されている文字を読み出す。

【００２０】比較手段は、入力された文字と読出手段が
記憶手段から読み出した文字が一致するか否かを比較
し、書込手段は、文字が入力される度に、該入力された
文字を記憶手段に随時書き込む。

【００２１】計数手段は、文字判別手段が入力された文
字を先頭文字と判別してから比較手段が一致すると比較
した回数を計数することで、記憶手段に記憶されている
部分文字列の長さを計数する。

【００２２】符号生成手段は、文字判別手段が入力され
た文字を先頭文字と判別した後に比較手段の比較結果が
不一致となったとき、記憶手段に記憶されている部分文
字列を表す符号語を一致位置、計数手段が計数した文字
数から生成する。

【００２３】なお、上記の構成において、一致位置記憶
手段を複数備え、読出手段は、文字が入力される度に、
複数の一致位置記憶手段に記憶されているそれぞれの一
致位置から順次変更させたアドレスに記憶されている文
字を記憶手段から各々読み出し、比較手段は、読出手段
が記憶手段から文字を読み出す毎に、該記憶手段から読
みだされた文字と入力された文字を順次比較し、計数手
段は、読出手段が記憶手段から読み出した文字のなかで
比較手段が入力された文字と一致すると比較した文字が
あった場合に計数を１度行い、符号生成手段は、読出手
段が記憶手段から読み出した文字のなかで比較手段が入
力された文字と一致すると比較した文字がなかった場合
に、記憶手段に記憶されている部分文字列を表す符号語
を生成する、ことが望ましい。

【００２４】

【作用】本発明のデータ圧縮装置は、文字が入力される
度に、該入力された文字が部分文字列の先頭文字に該当
するか否か判別し、該判別結果に応じてこの入力された
文字が辞書（記憶手段）に記憶されているか否か検索す
るとともに、この入力された文字を辞書に新たに登録し
ながら繰り返し入力された部分文字列を検出することで
符号化を行う。

【００２５】例えば、入力された文字が部分文字列の先
頭文字に該当すると判別した場合、この入力された文字
に一致する文字が記憶されている辞書のアドレス（一致
位置）を複数検索する。この入力された文字に続けて入
力される文字は、文字が入力される度に各一致位置から
連続させて変更させたアドレスから読み出したそれぞれ
の文字と一致するか否か比較し、これらの文字のなかで
一致すると比較された文字が入力された数をカウントし
ていくことで、最大一致系列、及びその一致長を確定す
る。最大一致系列が確定すると、その一致位置、一致長
から符号語を生成することで、この最大一致系列に対応
する入力された部分文字列の符号化を行う。この符号化
を行う一方、入力された文字は随時辞書に新たに登録す
る。

【００２６】上記のように、一致位置を検索しておくこ
とで文字の入力に合わせて随時符号化を行うことが可能
となり、また、入力された文字を辞書に随時登録するこ
とが可能となる。これにより、符号化対象の文字列を記
憶しておく必要性が回避され、メモリ数、及びその容量
の低減が可能となる。従って、装置の規模の小型化、及
びそのコストの低減が実現される。

【００２７】

【実施例】以下、本発明の実施例を、図面を参照しなが
ら詳細に説明する。図１は、本実施例によるデータ圧縮
装置１００の構成を示すブロック図である。

【００２８】このデータ圧縮装置１００における入力デ
ータ列ＩＤは、特には図示しない外部装置（例えばＣＰ
Ｕ）から、例えば１文字を８ビットで表現するＡＳＣＩ
Ｉコードで入力される。外部装置からは、入力データ列
ＩＤは１ビットの書込信号とともに入力され、その書込
信号がアクティブになると、１文字の入力データ列ＩＤ
は入力レジスタ１０１にストアされる。

【００２９】書込信号は、入力レジスタ１０１の他に、
制御部１０２に入力される。制御部１０２は、装置１０
０全体の制御を行うものであり、この書込信号がアクテ
ィブになる度に符号化処理（その動作は以下に説明す
る）を起動する。

【００３０】入力レジスタ１０１にストアされている文
字（以降、入力文字と記す）は、データセレクタ１０
４、及び前データレジスタ１０５に出力される。この前
データレジスタ１０５は、特には図示していないが、制
御部１０２から入力する書込信号がアクティブになるこ
とで入力文字（入力レジスタ１０１にストアされている
文字）をストアする。

【００３１】データセレクタ１０４は、前データレジス
タ１０５、入力レジスタ１０１がストアしている文字を
各々入力し、制御部１０２からのセレクト信号に従って
選択した一方を比較回路１０６に出力する。比較回路１
０６は、データセレクタ１０４から出力された文字と、
辞書メモリ１０３から読み出された文字とが一致するか
否かを比較し、この比較結果を制御部１０２に出力す
る。

【００３２】本実施例における辞書メモリ１０３は、４
Ｋｂｙｔｅの記憶容量（辞書サイズ）を有し、過去に入
力された４Ｋｂｙｔｅ分の文字（符号化済入力）が記憶
される。辞書メモリ１０３の読出アドレス、書込アドレ
スは、アドレスセレクタ１０７に接続された各ポインタ
により指定される。

【００３３】このアドレスセレクタ１０７には、辞書先
頭ポインタ１０８、一致位置ポインタ１０９〜１１２、
及び入力ポインタ１１３の各ポインタが接続されてい
る。アドレスセレクタ１０７は制御部１０２からのセレ
クト信号に従ってこれらのなかから１つを選択する。

【００３４】ここで、上記各ポインタについて、図２を
参照して説明する。図２は、各ポインタが示す辞書メモ
リ１０３上のアドレス例を示す図である。図２（ａ）
は、符号化済入力が辞書サイズ（本実施例では４Ｋｂｙ
ｔｅ）よりも小さい場合、図２（ｂ）は、符号化済入力
が辞書サイズよりも大きい場合を各々示し、斜線で示す
部分は文字が記憶されている領域を表している。また、
Ｐ１〜Ｐ４は、各々一致位置ポインタ１０９〜１１２が
指示（保持）しているアドレスの位置を示す。

【００３５】上記したように辞書メモリ１０３は、過去
に入力された４Ｋｂｙｔｅ分の文字が記憶されることか
ら、各ポインタ１０８〜１１３は１２ビット（２¹²＝４
０９６）である。

【００３６】辞書先頭ポインタ１０８は、制御部１０２
から出力された、辞書メモリ１０３に記憶されている文
字列において最も過去に記憶された文字のアドレスを保
持する。このため、符号化済入力が辞書サイズよりも小
さい場合（図２（ａ）参照）、辞書先頭ポインタ１０８
は辞書メモリ１０３の先頭アドレスを示す値を保持し、
符号化済入力が辞書サイズよりも大きい場合、図２
（ｂ）に示すように、辞書先頭ポインタ１０８が指示す
るアドレスは先頭アドレスとは限らず、辞書メモリ１０
３上をそれに文字が書き込まれる度に移動（スライド）
する。

【００３７】入力ポインタ１１３は、制御部１０２から
出力された、辞書メモリ１０３に新たに文字を書き込む
アドレスを保持する。このため、符号化済入力が辞書サ
イズよりも小さい場合（図２（ａ）参照）、入力ポイン
タ１１３には辞書メモリ１０３のまだ文字が書き込まれ
ていない領域の先頭を示すアドレスが保持され、符号化
済入力が辞書サイズよりも大きい場合、図２（ｂ）に示
すように、最も過去に記憶された文字のアドレス、即ち
辞書先頭ポインタ１０８が保持しているアドレスと同じ
値が入力ポインタ１１３に保持される。

【００３８】入力ポインタ１１３（辞書先頭ポインタ１
０８）に保持されるアドレスは、辞書メモリ１０３を循
環させるように変更される。このため、辞書メモリ１０
３には過去に入力された４Ｋｂｙｔｅ分の文字が常に記
憶される。

【００３９】一致位置ポインタ１０９〜１１２は、辞書
メモリ１０３から文字を読み出すアドレスを保持するも
のであり、入力レジスタ１０１にストアされた入力文字
が部分文字列の先頭文字であると制御部１０２が判別し
たとき（この判別については後述する）、その入力文字
と一致する文字が記憶されているアドレス（一致位置）
を各々保持する。ここでは、以降の説明を簡単にするた
め、現在入力レジスタ１０１にストアされている入力文
字は先頭文字であるとし、この先頭文字と判別した入力
文字、この入力文字に続く文字が入力された際の制御部
１０２の動作を順次説明していくなかで、入力された文
字の種類の判別について説明することにする。

【００４０】本実施例では、上記一致位置の検索は辞書
先頭ポインタ１０８が示すアドレスから順次アドレスを
変更させながら行われる。一致位置ポインタ１０９に一
致位置を保持、即ち比較回路１０６の比較結果が一致を
示すと、制御部１０２はこのときの一致位置ポインタ１
０９の値を一致位置ポインタ１１０にストアさせる。そ
の後、アドレスセレクタ１０７に一致位置ポインタ１１
０を選択させ、一致位置ポインタ１１０をインクリメン
トしながら辞書メモリ１０３から読み出された文字を入
力文字と順次比較していくことにより、一致位置ポイン
タ１１０に一致位置を保持させる。以降、他の一致位置
ポインタ１１１、一致位置ポインタ１１２に対しても同
様に、一致位置を各々保持させる。

【００４１】上記した入力文字と一致する文字の検索
は、一致位置ポインタ１０９〜１１２の全てに一致位置
を保持させるか、或いは辞書メモリ１０３に記憶されて
いる文字を全て参照、即ち辞書先頭ポインタ１０８のア
ドレスから循環させて入力ポインタ１１３の直前のアド
レスまでの文字を参照することで終了する。一致位置を
保持する順序により、各一致位置ポインタ１０９〜１１
２が保持する一致位置は図２（ａ）、及び（ｂ）に示す
ようになる。

【００４２】制御部１０２は、この検索の結果、入力レ
ジスタ１０１の入力文字と一致する文字を見つけた場
合、入力文字を前データレジスタ１０５にストアさせる
とともに、アドレスセレクタ１０７に入力ポインタ１１
３を選択させ、入力ポインタ１１３が指示するアドレス
にこの入力文字を記憶させる。入力文字を辞書メモリ１
０３に記憶させると、制御部１０２は一致位置を保持さ
せた一致位置ポインタ、辞書先頭ポインタ１０８、入力
ポインタ１１３をインクリメントし、その後、制御部１
０２は外部装置に対して文字の出力を要求する。この外
部装置に対する文字の出力の要求は、例えばその旨を示
す割り込み信号を外部装置に送出することで行われる。

【００４３】一方、上記の検索により入力文字と一致す
る文字が見つからなかった場合、制御部１０２は、
“０”をセットした一致フラグを符号出力部１１５に出
力するととともに、データセレクタ１０４を介してこの
入力文字を符号出力部１１５に出力させる。また、これ
に続いて入力文字を辞書メモリ１０３に書き込み、辞書
先頭ポインタ１０８、入力ポインタ１１３をインクリメ
ントした後、外部装置に次の文字の出力を要求する。こ
の場合、現時点の入力文字は符号化が終了しているの
で、制御部１０２は外部装置から次に入力する文字を先
頭文字と判別する。

【００４４】外部装置から新たに次の文字が入力される
と、即ち入力レジスタ１０１に新たに文字がストアされ
ると、制御部１０２は、符号化処理を再開する。このと
き、１つ前の入力文字と一致する文字を辞書メモリ１０
３内に見つけられなかった場合、上記したように、この
新たに入力された文字は先頭文字に該当することになる
ので、各一致位置ポインタ１０９〜１１２に一致位置を
保持させるための検索を再度行う。

【００４５】一方、例えば各一致位置ポインタ１０９〜
１１２に一致位置を保持させていた場合（実際は、これ
らのなかで一致位置を保持するポインタが１つでもあれ
ばよい）、各々インクリメントしておいた各一致位置ポ
インタ１０９〜１１２が指示するアドレスに記憶された
文字がこの新たに入力された文字と一致するか否かの比
較を、一致位置ポインタ１０９が指示するアドレスに記
憶された文字から順次行う。これは、アドレスセレクタ
１０７が選択するポインタを順次切り換えていくことで
行われる。

【００４６】上記比較を行った結果、各一致位置ポイン
タ１０９〜１１２が指示するアドレスから読み出された
文字のなかで入力文字と一致する文字がなかった場合、
制御部１０２は符号出力部１１５に“０”の一致フラグ
を出力するとともに、データセレクタ１０４を介して前
データレジスタ１０５の文字を符号出力部１１５に入力
させる。これにより、入力文字までの符号化が終了した
ことになるので、制御部１０２はこの入力文字を先頭文
字と判別し、上述した一致位置の検索を再び行う。

【００４７】反対に、各一致位置ポインタ１０９〜１１
２が指示するアドレスから読み出された文字のなかで入
力文字と一致する文字があった場合、制御部１０２は辞
書メモリ１０３に記憶されている一致系列の長さ（文字
数）をカウントさせる一致長カウンタ１１４をリセット
（“０”をセット）する。この一致長カウンタ１１４の
リセットを行うと、続いて入力文字を入力ポインタ１１
３が指示するアドレスに書き込み、その後、入力文字と
一致する文字を指示した一致位置ポインタ、入力ポイン
タ１１３、辞書先頭ポインタ１０８を各々インクリメン
トし、現在の入力文字に続く文字が入力されるのを待
つ。

【００４８】一致長カウンタ１１４をリセットした以降
は、入力文字と一致する文字を読み出した一致位置ポイ
ンタだけをインクリメントしながら、辞書メモリ１０３
から読み出された文字が全て入力文字と一致しないと比
較回路１０６が比較するまで一致長カウンタ１１４のカ
ウントアップを継続して行う。このカウントアップを継
続している間、比較回路１０６による文字の比較が終了
した後に、入力文字の辞書メモリ１０３への書き込みが
行われる。

【００４９】辞書メモリ１０３から読み出された文字が
全て入力文字と一致しなくなると、或いは予め設定され
ている最大一致長（後述する）まで一致長カウンタ１１
４をカウントアップさせた後、次の文字が入力される
と、制御部１０２は、現時点で符号化を行っている部分
文字列の最大一致系列が確定したと判断し、符号出力部
１１５に“１”の一致フラグを出力する。また、符号出
力部１１５に対し、一致長カウンタ１１４からそのカウ
ント値（一致長）、減算器１１６からアドレスセレクタ
１０７の出力値から一致長カウンタ１１４のカウント値
に２を加算した値を減算した結果を順次入力させる。こ
のとき、各一致位置ポインタ１０９〜１１２のなかの最
後までインクリメントされていたものをアドレスセレク
タ１０７に選択させている。このため、減算器１１６の
減算結果は、各一致位置ポインタ１０９〜１１２に保持
されていた一致位置から始まる一致系列のなかの、最大
一致系列の一致位置となる。

【００５０】このように最大一致系列が確定すると、入
力レジスタ１０１にストアされている入力文字よりも過
去に入力された文字までの符号化が終了したことになる
ので、制御部１０２はこの入力文字を先頭文字と判別す
る。このため、制御部１０２は、符号出力部１１５が一
致長カウンタ１１４のカウント値、減算器１１６の減算
結果を入力した後、上述したように、各一致位置ポイン
タ１０９〜１１２に一致位置を保持させるための検索を
行う。

【００５１】符号出力部１１５は、特には図示しない
が、例えばセレクタ、シフトレジスタ等から構成されて
おり、制御部１０２によって制御される。符号出力部１
１５は、制御部１０２の制御に従ってセレクタの切り換
え、シフトレジスタのビットシフト等を行うことで、こ
のシフトレジスタに符号語として一致フラグ、及びその
一致フラグの値に応じて文字（ＡＳＣＩＩコード）、或
いは一致長（一致長カウンタ１１４のカウント値）及び
一致位置（減算器１１６出力）が順次格納される。シフ
トレジスタに格納された符号語は随時８ビット単位に切
り出されて外部に出力される。このシフトレジスタから
切り出されて出力されたものが圧縮符号出力ＯＤであ
る。

【００５２】ここで、この符号出力部１１５から出力さ
れる圧縮符号出力ＯＤについて、図３を参照して説明す
る。図３は、圧縮符号出力ＯＤのデータ形式を説明する
図である。

【００５３】上記したように、本実施例では、入力され
た部分文字列と一致する部分文字列が辞書メモリ１０３
に記憶されているか否かにより、“１”、或いは“０”
が一致フラグにセットされ、図３に示すように、１ビッ
トで表される一致フラグの値により符号語のデータ形式
は互いに異なる。

【００５４】一致フラグに“１”がセットされた場合、
その符号語は該一致フラグ、４ビットの一致長、及び１
２ビットの一致位置からなり、その語長は１７ビットで
ある。一方、一致フラグに“０”がセットされた場合、
その符号語は該一致フラグ、及び８ビットで入力された
文字（不一致文字）からなり、その語長は９ビットであ
る。

【００５５】本実施例では、上記したようなデータ形式
としていることから、元のデータ量よりも符号化を行っ
た後のデータ量が大きくならないように、入力された符
号化の対象となる部分文字列と２文字以上一致する部分
文字列が辞書メモリ１０３に記憶されていない場合、そ
の部分文字列の先頭文字は不一致文字と判断するように
している。このため、一致フラグに“１”がセットされ
た際の一致長は４ビットで２文字から１７文字（最大一
致長）を表現させている。

【００５６】以上が本実施例によるデータ圧縮装置１０
０の概略圧縮動作である。次に、上述した圧縮動作につ
いて、具体例を挙げて説明する。図４は、データ圧縮装
置１００の圧縮動作例を具体的に説明するための図であ
る。図中、同図（ａ）は入力データ列ＩＤとして入力さ
れた入力文字列４０１、同図（ｂ）は該入力文字列４０
１における７番目の文字“Ｂ”が入力された際の各ポイ
ンタ１０８〜１１３が示す辞書メモリ１０３上のアドレ
ス、同図（ｃ）は該入力文字列４０１が入力されたこと
で出力される圧縮符号出力ＯＤを各々示す。

【００５７】図４（ａ）に示す入力文字列４０１は、入
力データ列ＩＤとして左から右に向かって１文字ずつ順
次入力レジスタ１０１にストアされる。この入力文字列
４０１において、現在７番目の文字“Ｂ”が現在入力値
としてこの入力レジスタ１０１にストアされていること
を表している。

【００５８】図４（ｂ）に示すように、この７番目の文
字“Ｂ”が入力レジスタ１０１にストアされていると
き、入力された文字は随時辞書メモリ１０３に書き込む
ことから、辞書メモリ１０３には辞書先頭ポインタ１０
８が指示するアドレスからそれ以前に入力された６文字
が順次記憶されている。

【００５９】１〜５番目の文字“ＡＢ＝０；”は、各々
それが始めて入力された種類であることから、制御部１
０２はこれらの文字を辞書メモリ１０３から検索するこ
とができない。このため、これら１〜５番目の各文字は
全て不一致文字と判断され、入力レジスタ１０１からデ
ータセレクタ１０４を介して符号出力部１１５に出力さ
れることで、“０”がセットされた一致フラグとその文
字とからなる符号語（圧縮符号出力ＯＤ）として符号出
力部１１５から出力される（図４（ｃ）参照）。

【００６０】一方、６番目の文字“Ｂ”は２番目に入力
された文字と一致するので、辞書メモリ１０３を検索し
た結果、図４（ｂ）においてＰ１で示す２番目の文字が
書き込まれているアドレス（一致位置）が一致位置ポイ
ンタ１０９に保持される。７番目の文字“Ｂ”が入力す
ると、インクリメントされた一致位置ポインタ１０９が
指示するアドレスから読み出された３番目の文字とこの
７番目の文字は比較回路１０６によって比較されるが、
これらの文字は一致しないので、６番目の文字は不一致
文字と判断される。このとき、６番目の文字は前データ
レジスタ１０５にストアされており、この６番目の文字
はデータセレクタ１０４を介して符号出力部１１５に出
力され、“０”がセットされた一致フラグが付加されて
出力される。

【００６１】上記したように、７番目の文字は３番目の
文字と一致しないので、制御部１０２はこの７番目の文
字を先頭文字と判別し、これと一致する文字を辞書メモ
リ１０３から検索する。７番目の文字は、２番目、及び
６番目の文字と一致しているので、この検索の結果、図
４（ｂ）においてＰ１で示す２番目の文字が書き込まれ
ているアドレス（一致位置）が一致位置ポインタ１０９
に保持され、また、図４（ｂ）においてＰ２で示す６番
目の文字が書き込まれているアドレス（一致位置）が一
致位置ポインタ１１９に保持される。この検索が終了す
ると、制御部１０２はこの７番目の文字を辞書メモリ１
０３の入力ポインタ１１３が指示するアドレスに書き込
み、一致位置ポインタ１０９、１１０、辞書先頭ポイン
タ１０８、入力ポインタ１１３の各ポインタをインクリ
メントした後、次の文字（８番目の文字“＝”）の入力
を待つ。

【００６２】８番目の文字が入力すると、この８番目の
文字は各々インクリメントされた一致位置ポインタ１０
９、１１０が指示するアドレスから読み出された文字、
即ち３番目、７番目の文字と順次比較される。８番目の
文字は７番目の文字と一致しないが、３番目の文字とは
一致するので、制御部１０２は一致長カウンタ１１４を
ここでリセットし、また、この入力された８番目の文字
を入力ポインタ１１３が指示するアドレスに書き込む。
その後、一致位置ポインタ１０９、辞書先頭ポインタ１
０８、入力ポインタ１１３を各々インクリメントした
後、次の文字（９番目の文字“０”）の入力を待つ。

【００６３】図４（ａ）に示すように、９〜１０番目の
文字“０；”は、４〜５番目の文字と一致している。こ
のため、以降、１１番目の文字“Ｃ”が入力されるま
で、制御部１０２は一致位置ポインタ１０９をインクリ
メントしながら、この一致位置ポインタ１０９が指示す
るアドレスから読み出した文字と入力された文字とを順
次比較することになる。この結果、１１番目の文字が入
力されるまで一致長カウンタ１１４のカウントアップは
行われ、この１１番目の文字が入力された時点の一致長
カウンタ１１４のカウント値は“２”となる。また、辞
書メモリ１０３の先頭アドレス値を“０”と想定する
と、この時の一致位置ポインタ１０９の値は“５”であ
る。

【００６４】１１番目の文字が入力すると、この文字は
一致位置ポインタ１０９が指示するアドレスの文字、即
ち６番目の文字と比較される。図４（ａ）に示すよう
に、この両者は一致しないので、比較回路１０６は不一
致と比較した結果を制御部１０２に出力する。制御部１
０２は、比較回路１０６からこの比較結果を入力する
と、最大一致系列が確定したと判断し、続けて、この最
大一致系列の一致長が２文字以上であるか否か、即ち一
致フラグを“１”とした符号語を生成させるか否か判断
する。この場合、最大一致系列は図４（ｂ）にＰ１で示
す一致位置を先頭としたその文字数が４つの部分文字列
なので、制御部１０２は“１”をセットした一致フラグ
を符号出力部１１５に出力する。また、符号出力部１１
５に一致長カウンタ１１４のカウント値、及び減算器１
１６の減算結果を順次入力させる。

【００６５】このとき、制御部１０２は、アドレスセレ
クタ１０７に一致位置ポインタ１０９を選択させてい
る。従って、減算器１１６から符号出力部１１５に出力
される減算結果は図４（ｂ）のＰ１を示す値である。

【００６６】図４（ｃ）は、入力文字列４０１の１０番
目の文字までを符号化した際の圧縮符号出力ＯＤを示し
ている。入力文字列４０１を符号化対象とした場合、上
述したように圧縮動作（符号化処理）が行われるので、
図４（ｃ）に示すように、一致フラグに“０”がセット
されている符号語が６つ続き、７番目で符号語の一致フ
ラグに“１”がセットされる。

【００６７】この７番目の符号語は、７〜１０番目の４
文字からなる部分文字列を表したものである。上述した
ように、一致長は２文字を“０”として順次カウントア
ップさせた値なので、このときの一致長は“２”であ
る。符号語として出力する一致位置は実際の一致位置と
しているので、このときの一致位置は“１”である（こ
れは辞書メモリ１０３の先頭アドレスを“０”としたと
きの値である）。この図４（ｃ）に示す圧縮符号出力Ｏ
Ｄは、符号出力部１１５のシフトレジスタに格納された
符号語を８ビット単位で切り出すことで符号出力部１１
５から随時出力される。

【００６８】このように、本実施例は、符号化の対象と
なる部分文字列の先頭文字が記憶されている辞書メモリ
１０３の一致位置を確定し、その先頭文字に続く文字が
入力される度に、この文字の入力に対応させてその一致
位置から変更させたアドレスに記憶されている文字と新
たに入力された文字とを随時比較していくことで符号化
を行うため、符号化が済んでいない文字を記憶させるた
めのメモリが不要となり、装置においてメモリが占める
割合を小さくすることができる。これにより、装置の規
模、及びそのコストを抑えることができ、ＬＳＩ化も容
易となるので、本発明はコンピュータのバス等に直結し
て利用するデータ圧縮装置等に対して広く適用すること
ができる。

【００６９】また、本実施例では、符号出力部１１５を
用いて随時圧縮符号出力ＯＤを外部に出力させている。
このため、図５に示す従来のデータ圧縮装置５００と比
較すると、備えたメモリ数が低減、即ち入力メモリ５０
１、符号メモリ５０５等を備えなくともよいことから、
装置各部の個々の制御を簡易化することができるという
効果もある。

【００７０】一方、符号化に要する処理時間についてこ
の両者を比較すると、一致系列の抽出の打ち切りかた、
用いる一致位置ポインタ数といった両者の最大一致系列
の検索方法の違いにもよるが、データの入力に要する処
理時間が全体に占める割合は小さいことから、基本的に
はその処理時間に大きな差は発生しない。

【００７１】なお、本実施例では、一致位置を保持する
一致位置ポインタの数を４つとしているが、この数はこ
れに限定したものではない。一致位置ポインタ数が少な
い程、データ圧縮を高速に行うことはできるが、この一
方で圧縮比（＝圧縮後のデータ量／圧縮前のデータ量）
が大きくなるという不具合が発生し易くなる。データ圧
縮に要求する処理速度、符号化の対象となるファイルの
種類等にもよるが、上記圧縮比が大きくなるのを抑える
ためには、この数を４つ以上とすることが望ましい。

【００７２】また、本実施例では、辞書メモリ１０３の
各アドレスを保持させる各種ポインタ１０８〜１１３を
備えているが、例えばこれらのポインタの役割を制御部
１０２に行わせてもよく、また、一致長カウンタ１１
４、減算器１１６の役割を制御部１０２に行わせてもよ
い。このように、本発明は圧縮符号出力ＯＤのデータ形
式を含めて柔軟に適用させることができるものである。

【００７３】

【発明の効果】以上、説明したように本発明によれば、
文字が入力される度に、該入力された文字が部分文字列
の先頭文字に該当するか否か判別し、該判別結果に応じ
てこの入力された文字が辞書（記憶手段）に記憶されて
いるか否か検索することで繰り返し入力された部分文字
列を検出するため、文字の入力に合わせて随時文字列の
符号化を行うことができ、また、入力された文字を随時
辞書に登録することができる。これにより、符号化対象
の文字列を記憶しておく必要性を回避され、装置の規模
を小型化するとともに、そのコストを低減することがで
きる。

【００７４】また、先頭文字に該当すると判別した文字
と一致する文字が記憶されている辞書の一致位置を複数
抽出して上記の検索を行うようにすることで、圧縮比が
大きくなるのを抑えることができる。

【図面の簡単な説明】

【図１】本実施例によるデータ圧縮装置の構成を示すブ
ロック図である。

【図２】各ポインタが示す辞書メモリ上のアドレス例を
示す図である。

【図３】圧縮符号出力のデータ形式を説明する図であ
る。

【図４】圧縮動作例を具体的に説明するための図であ
る。

【図５】従来のデータ圧縮装置の構成を示すブロック図
である。

【符号の説明】

１００データ圧縮装置１０１入力レジスタ１０２制御部１０３辞書メモリ１０６比較回路１０７アドレスセレクタ１０８辞書先頭ポインタ１０９〜１１２一致位置ポインタ１１３入力ポインタ１１４一致長カウンタ１１５出力制御部１１６減算器

Claims

【特許請求の範囲】

【請求項１】過去に入力された文字列を記憶する記憶
手段を備え、該記憶手段に記憶された文字列を参照し、
繰り返し入力された部分文字列を検出することで文字列
を表すデータ量の圧縮を行うデータ圧縮装置であって、入力された文字が部分文字列の先頭文字であるか否かを
判別する文字判別手段と、前記文字判別手段が入力された文字を先頭文字と判別し
たとき、該入力された文字と一致する文字が記憶されて
いる前記記憶手段のアドレスを一致位置として記憶する
一致位置記憶手段と、前記先頭文字であると前記文字判別手段が判別した文字
に続く文字が入力される度に、該文字の入力に応じて前
記一致位置から順次アドレスを変更しながら前記記憶手
段に記憶されている文字を読み出す読出手段と、入力された文字と前記記憶手段から読み出された文字が
一致するか否かを比較する比較手段と、前記文字判別手段が入力された文字を先頭文字と判別し
てから前記比較手段が一致すると比較した回数を計数す
ることで、前記記憶手段に記憶されている部分文字列の
長さを計数する計数手段と、前記文字判別手段が入力された文字を先頭文字と判別し
た後、前記比較手段の比較結果が不一致となったとき、
前記記憶手段に記憶されている部分文字列を表す符号語
を前記一致位置、前記計数手段が計数した文字数から生
成する符号生成手段と、を具備したことを特徴とするデータ圧縮装置。
【請求項２】文字が入力される度に、該入力された文
字を前記記憶手段に随時書き込む書込手段を、さらに具備したことを特徴とする請求項１記載のデータ
圧縮装置。
【請求項３】前記一致位置記憶手段を複数備え、前記読出手段は、文字が入力される度に、前記複数の一
致位置記憶手段に記憶されているそれぞれの一致位置か
ら順次変更させたアドレスに記憶されている文字を前記
記憶手段から各々読み出し、前記計数手段は、前記読出手段が前記記憶手段から読み
出した文字のなかで前記比較手段が入力された文字と一
致すると比較した文字があった場合に計数を１度行い、前記符号生成手段は、前記読出手段が前記記憶手段から
読み出した文字のなかで前記比較手段が入力された文字
と一致すると比較した文字がなかった場合に、前記記憶
手段に記憶されている部分文字列を表す符号語を生成す
る、ことを特徴とする請求項１、または２記載のデータ圧縮
装置。