JPH07135471A

JPH07135471A - データ圧縮装置およびデータ伸張装置

Info

Publication number: JPH07135471A
Application number: JP30335593A
Authority: JP
Inventors: Shuichi Kikuchi; 修一菊地
Original assignee: Tokyo Electron Ltd
Current assignee: Tokyo Electron Ltd
Priority date: 1993-11-09
Filing date: 1993-11-09
Publication date: 1995-05-23

Abstract

(57)【要約】【目的】順次入力されるデータ列をリアルタイムで処
理でき、しかも常に高い圧縮率を維持しながらデータの
圧縮および伸張を行うことができるデータ圧縮装置およ
びデータ伸張装置を提供すること。【構成】このデータ圧縮装置は、データバッファ１
０，辞書バッファ１２，バッファ更新部１４，一致長符
号化部１６，位置符号化部２０，順位符号化部２４，テ
ーブル更新部２８を含んで構成される。一致長符号化部
１６は、データバッファ１０内の文字列を先頭から見て
いって、辞書内の文字列との比較を行い、その一致長を
符号化して出力する。辞書内に一致した文字列が存在す
る場合には、位置符号化部２０は、辞書内のアドレスを
符号化して出力する。辞書内に一致した文字列がない場
合には、順位符号化部２４は、先頭文字について出現頻
度が高いものほど短いビット長の符号化を行う。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、例えば一般的なコンピ
ュータシステムにおいて、磁気ディスクやＩＣメモリ等
のデジタル記憶装置に記憶するデータを圧縮し、あるい
はこれらのデジタル記憶装置から読出したデータを伸張
するデータ圧縮装置およびデータ伸張装置に関する。

【０００２】

【従来の技術】近年、マイクロプロセッサの高速化およ
び高性能化にともない、コンピュータシステムにおける
処理内容も多様化しており、扱うデータ量も急激に増大
している。特に最近では、静止画や動画を対象とした画
像処理が盛んになりつつあり、このような画像処理を行
う場合には扱うデータ量も従来の文字データに比べて膨
大となる。そのため、この膨大な画像データを例えばハ
ードディスク装置に格納する場合に、その前処理として
データの圧縮を行っておいて、この圧縮されたデータを
ハードディスク装置に格納する方法が知られている。ま
た、データを読み出す場合には、圧縮して格納されてい
るデータを読み出した後に伸張し、この伸張データをパ
ーソナルコンピュータ（パソコン）に送ることになる。

【０００３】図１７は、ハードディスク装置あるいはメ
モリカードに対するデータの記憶を圧縮された形で行う
場合の一般的なシステム構成を示す図である。同図
（Ａ）は、パソコン１００に接続されたハードディスク
装置１０２内にデータの圧縮装置１０４および伸張装置
１０６を備えた場合が示されている。この場合には、パ
ソコン１００からハードディスク装置１０２に対して非
圧縮データが送られ、圧縮装置１０４によって圧縮が行
われた後にこの圧縮データが記憶される。データを読み
出す際には、まず読み出した圧縮データをハードディス
ク装置１０２内の伸張装置１０６によって伸張した後に
パソコン１００に向け出力する。

【０００４】また、同図（Ｂ）にはこの圧縮装置１０４
および伸張装置１０６をパソコン１００内に設けた場合
の構成が示されている。

【０００５】さらに、同図（Ｃ）には、記憶装置として
ハードディスク装置１０２の代わりにメモリカード１０
８を対象とした場合が示されている。この場合には、パ
ソコン１００に装着されたメモリカード１０８にデータ
を格納する前に圧縮装置１０４によってデータの圧縮が
行われる。また、メモリカード１０８から読み出された
圧縮データが伸張装置１０６によって伸張される。

【０００６】図１８は、パソコン１００とプリンタ１１
０の間に設けられたプリンタバッファ１１２に圧縮デー
タを格納する構成を示す図である。同図（ａ）には、パ
ソコン１００内に圧縮装置１０４を設けるとともに、プ
リンタバッファ１１２内に伸張装置１０６を設けるよう
にしたものである。また、同図（Ｂ）はプリンタバッフ
ァ１１２内に圧縮装置１０４と伸張装置１０６の両方を
設けたものである。これらの図に示すように、パソコン
１００の印刷データを圧縮装置１０４によって圧縮した
後にプリンタバッファ１１２に保持しているため、実際
の格納容量よりもたくさんの印刷データを保持すること
ができる。

【０００７】ところで、上述したデータの圧縮および伸
張を行う方式としては数々のものが提案されており、例
えば、ハフマン符号を用いる方法、動的辞書法、
スライド辞書法等が代表的なものとして挙げられる。

【０００８】ハフマン符号を用いる方法は、圧縮対象
となる全データ列内の各文字あるいは文字列の出現頻度
を予めカウントしておいて、出現頻度の高いものほどビ
ット長が短くなるような変換符号表を予め作成し、入力
データをこの変換符号表に従って符号化するものであ
る。この方法によれば、どのような入力データ列に対し
ても最適な変換符号表を作成することができ、効率よい
符号化、すなわち高い圧縮率のデータ圧縮が可能となる
という利点がある。

【０００９】動的辞書法は、入力されたデータ列に専
用の符号を割り当てて、順次辞書形式で登録する。処理
が進むにしたがって辞書内のデータが増えていくため、
動的辞書法と呼ばれているものであり、入力されたデー
タ列の中の文字列が辞書内に存在すると、辞書内の対応
する符号とこの文字列の次の１文字に対応する符号とを
出力する。存在しない場合には、存在しない旨のフラグ
とともに１文字分の生データを出力する。文字列の繰り
返し性に冗長成分を見付け出す方法であるため、高い圧
縮率が得られ、しかも入力されるデータ列を順次処理す
ることができるワンパス構成とすることができる。

【００１０】スライド辞書法は、既に処理が終了した
データ列を用いて辞書登録を行うものである。辞書の登
録内容は古いものから順に消されるため、有限の辞書サ
イズとすることができ、辞書の管理が容易となる利点が
ある。入力されたデータ列に対して辞書検索を行い、辞
書内に一致する文字列が存在する場合は、一致フラグに
続けてその位置と一致長を符号化したデータを出力す
る。存在しない場合には、不一致フラグとともに次の１
文字分の生データを出力する。の動的辞書法と同様
に、文字列の繰り返し性に上長成分を見付け出す方法で
あり、常に高い圧縮率が得られ、ワンパスで処理できる
という特徴がある。このスライド辞書法を用いたものと
しては、例えば特開平３−６８２１９号公報に開示され
た「データ圧縮装置及び方法」がある。

【００１１】

【発明が解決しようとする課題】ところで、上述した各
種の圧縮方法においては、種々の問題がある。すなわ
ち、ハフマン符号を用いる方法においてはデータ圧縮
を行う前処理として、入力されるデータ列内の各文字の
出現頻度をカウントし、出現頻度が高いものほど短いビ
ット長を有する符号を対応させた変換符号表を作成しな
ければならないため、順次入力されるデータ列をワンパ
スで処理することは不可能であり、必ずツーパス処理と
なるため、リアルタイムの処理が不可能であるという問
題があった。また、いくつかのデータ群が存在する場合
には、各データ群毎に異なる変換符号表を作成しなけれ
ばならないため、この変換符号表まで含めるとそれ程高
い圧縮率が得られないという問題があった。

【００１２】また、動的辞書法およびスライド辞書
法においては、辞書内に該当する文字が存在しない場合
には、不一致フラグ等と次の文字の生データを出力して
いるため、辞書内に該当するデータが存在しない場合に
は入力される元データよりもビット長の長い符号出力が
存在するという問題があった。さらに、動的辞書法に
おいては、有限の辞書サイズとするためには、辞書の更
新方法が複雑になってしまう。例えば、アクセス頻度の
低いものから順に更新していこうとすると、アクセス頻
度も情報として保持する必要がある。また、古い順に更
新していこうとすると、文字列とデータ登録時間とを対
応させて辞書を作成しなければならなくなる。

【００１３】そこで、本発明はこのような鑑みて創作さ
れたものであり、順次入力されるデータ列をリアルタイ
ムで処理することができ、しかも辞書内に該当するデー
タが存在しない場合であっても常に高い圧縮率を維持し
ながらデータの圧縮を行うことができるデータ圧縮装置
およびデータ伸張装置を提供することを目的とする。

【００１４】

【課題を解決するための手段】上述した課題を解決する
ために、請求項１の発明は、順次入力される非圧縮デー
タの中の最後尾に位置する所定ワード長のデータ列を処
理データとして、およびその前に位置する所定ワード長
のデータ列を辞書としてそれぞれ格納するデータバッフ
ァおよび辞書バッファと、前記データバッファ内の処理
データを構成する各ワードについて、前記辞書を構成す
る各ワードと一致するものがあるか否かを検索し、その
最も長い一致長を符号化した一致長符号を出力する一致
長符号化手段と、前記一致長符号化手段によって一致の
判定が行われた場合に、一致したワード列の中で最もワ
ード長が長いものの前記辞書内の位置を符号化した位置
符号を出力する位置符号化手段と、非圧縮データの各ワ
ードについて存在確率の高い順にビット長が短い順位符
号を対応させた順位テーブルを有しており、前記一致長
符号化手段によって不一致の判定が行われた場合に、前
記順位テーブルを検索することにより前記データバッフ
ァ内の処理データの先頭ワードに対応する順位符号を出
力する順位符号化手段と、前記順位符号化手段による符
号化処理が行われた場合に、符号化の対象となった前記
処理データの先頭ワードを考慮して前記順位テーブルを
更新するテーブル更新手段と、前記位置符号化手段ある
いは前記順位符号化手段による符号化が行われたとき
に、符号化が終了した前記処理データの一部あるいは全
部を前記辞書バッファ内の辞書に移すとともに、この移
した分の非圧縮データを前記データバッファに追加して
格納する処理を行うバッファ更新手段と、を備え、前記
辞書内に処理データの各ワードと一致したワードがある
場合には一致長とその位置とをそれぞれ符号化し、一致
したワードがない場合にはその旨を示す一致長と処理デ
ータの先頭ワードとをそれぞれ符号化することにより圧
縮データを得ることを特徴とする。

【００１５】請求項２の発明は、請求項１の発明におい
て、前記一致長符号化手段は、前記辞書バッファ内の辞
書の各ワードを先頭から順に見ていった場合に、異なる
ワード毎に先頭アドレスを格納するトップバッファと、
前記辞書バッファ内の辞書の各ワードを先頭から順に見
ていった場合に、同じワードが次に前記辞書内のどのア
ドレスに格納されているかを示すデータを格納するチェ
ーンバッファと、を含み、前記データバッファ内の処理
データの先頭ワードに基づいて前記トップバッファおよ
び前記チェーンバッファを検索することにより、該当す
る前記辞書内のアドレスを特定することを特徴とする。

【００１６】請求項３の発明は、請求項１の発明におい
て、前記辞書バッファおよびデータバッファは、各アド
レスが互いに連続している複数のメモリ素子により構成
されており、前記バッファ更新手段は、符号化が終了し
た前記処理データの一部あるいは全部を構成する各ワー
ドを、前記複数のメモリ素子のそれぞれに分散して格納
し、前記一致長符号化手段は、前記複数のメモリ素子の
それぞれから同時にデータを読み出すことにより、前記
一致検索を行うことを特徴とする。

【００１７】請求項４の発明は、圧縮データを伸張して
得られる非圧縮データの中の最後尾に位置する所定ワー
ド長のデータ列を辞書として格納する辞書バッファと、
順次入力される圧縮データの先頭部分に位置する一致長
符号を復号化して具体的な一致長データを出力する一致
長復号化手段と、前記圧縮データの先頭部分に位置する
一致長符号が一致を示している場合に、その次に位置す
る位置符号を復号化して、前記辞書内の格納位置を示す
データを出力する位置復号化手段と、前記圧縮データの
先頭部分に位置する一致長符号が一致を示している場合
に、前記位置復号化手段から出力されるデータに基づい
て前記辞書内の格納位置を特定し、この格納位置を先頭
アドレスとして前記一致長データの分だけ前記辞書から
データの読出しを行って、非圧縮データを出力する辞書
読出し制御手段と、前記非圧縮データの各ワードについ
て存在確率の高い順に短い順位符号を対応させた順位テ
ーブルを有しており、前記圧縮データの先頭部分に位置
する一致長符号が不一致を示している場合に、その次に
位置する順位符号に基づいて前記順位テーブルを検索す
ることにより前記非圧縮データの復号化を行う順位復号
化を行う順位復号化手段と、前記順位復号化手段により
復号化処理が行われたときに、復号化された非圧縮デー
タを考慮して前記順位テーブルを更新するテーブル更新
手段と、前記位置復号化手段あるいは前記順位復号化手
段による復号化が行われたときに、復号化が終了した非
圧縮データを含ませるように前記辞書の更新を行う辞書
更新手段と、を備え、一致長符号と位置符号および順位
符号のいずれか一方とを組み合わせた圧縮データを復号
化することにより伸張データを得ることを特徴とする。

【００１８】

【作用】請求項１のデータ圧縮装置は、既に圧縮処理が
終了した最も最近の所定ワード長のデータ列を辞書とし
て辞書バッファに格納するとともに、これから処理を行
う所定ワード長のデータ列をデータバッファに格納す
る。そして、データバッファに格納されたデータ列につ
いて辞書バッファ内の辞書を構成する各ワードと一致す
るものがあるか否かを検索し、一致した場合には一致し
たワード列の中で最もワード長が長いものの一致長を符
号化した一致長符号と、その辞書内の位置を符号化した
位置符号とを圧縮データとして出力する。

【００１９】また、一致しない場合には、一致していな
い旨を表す一致長符号と、各ワードについて存在確率の
高い順に短い順位符号を対応させた順位テーブルによっ
て処理データの先頭ワードに対応させて得られた順位符
号とを圧縮データとして出力する。

【００２０】上述した圧縮処理が終了した後、データバ
ッファ，辞書バッファ，順位テーブルのそれぞれが更新
され、常に最新の情報に基づくデータ圧縮が行われるよ
うになっている。

【００２１】請求項１の発明においては、順次入力され
るデータによって辞書が作成されるため、ワンパス構成
とすることができ、リアルタイムの圧縮処理が可能とな
る。また、辞書内に該当するデータ（ワード）が存在し
ない場合であっても、出現確率の高いものほど短い符号
に割り当てた圧縮処理が行われるため、元データよりも
短いビット長で符号化処理を行うことができ、全入力デ
ータに対して常に高い圧縮率を維持したデータ圧縮を行
うことが可能となる。

【００２２】また、請求項２の発明では、上述した一致
長符号化手段をトップバッファとチェーンバッファとを
含んで構成している。このトップバッファには、辞書の
各ワードを先頭から順に見ていった場合に異なるワード
毎の先頭アドレスが格納されており、チェーンバッファ
には辞書内の各ワードを先頭から順に見ていった場合に
同じワードが次に辞書内のどのアドレスに格納されてい
るかを示すデータが格納されている。したがって、デー
タバッファ内の各ワードを辞書内で検索する場合に、ト
ップファッファとチェーンバッファをアクセスすること
により、辞書の該当アドレスを速やかに知ることがで
き、処理の高速化が可能となる。

【００２３】また、請求項３の発明は、上述した辞書バ
ッファおよびデータバッファを複数のメモリ素子によっ
て構成しており、しかもこれら各メモリ素子は各アドレ
スが互いに連続している。そして、辞書を更新する際に
は、符号化が終了した非圧縮データの一部あるいは全部
を構成する各ワードを、これら複数のメモリ素子のそれ
ぞれに分散して格納し、辞書検索時にはこれら複数のメ
モリ素子から同時にデータの読出しを行う。したがっ
て、メモリ素子の個数分のワード長を同時に比較するこ
とができ、一致長が長い場合の一致長判定を高速に処理
することができる。

【００２４】また、請求項４のデータ伸張装置は、上述
したデータ圧縮装置によって圧縮されたデータを伸張す
ることにより、データの復号を行うものである。入力さ
れる圧縮データの先頭部分に位置する一致長符号が一致
を示している場合には、その次に位置する位置符号を復
号化することにより辞書内の格納位置が得られる。そし
て、この格納位置を先頭アドレスとして一致長の分だけ
辞書からデータの読出しを行うことによりデータの伸張
が行われ、非圧縮データが得られる。また、上述した一
致長符号が不一致を示している場合には、データ圧縮装
置内の順位テーブルと同じ内容の順位テーブルを検索す
ることにより、データの伸張が行われ、非圧縮データが
得られる。この順位テーブルは検索された後にその都度
変更され、上述したデータ圧縮装置内の順位テーブルと
常に同じ手順で更新が行われるようになっている。

【００２５】請求項４の発明においては、データ圧縮の
場合と同様にリアルタイムで伸張処理を行うことができ
る。

【００２６】

【実施例】以下、図面に基づいて本発明の一実施例につ
いて詳細に説明する。

【００２７】図１は、本発明を適用した一実施例のデー
タ圧縮装置の構成を示す図である。同図に示すデータ圧
縮装置は、データバッファ１０，辞書バッファ１２，バ
ッファ更新部１４，一致長符号化部１６，位置符号化部
２０，順位符号化部２４，テーブル更新部２８を含んで
構成される。

【００２８】データバッファ１０は、これから処理され
るデータ列を一時保持するものであり、圧縮処理が終了
したデータ分だけ新たなデータ列が入力され、順次内容
が更新されるようになっている。また、辞書バッファ１
２は、処理が終了した非圧縮データを辞書として格納す
るものであり、新たに圧縮処理が行われる毎に古い内容
が削除され更新が行われるようになっている。

【００２９】図２は、データバッファ１０および辞書バ
ッファ１２と入力データ列との関係を概略的に示す図で
ある。同図において、矢印ａは入力されるデータ列の方
向を示しており、入力データ列の各ワードを１文字のア
ルファベットで示した場合が示されている。入力された
データ列は、まずデータバッファ１０に順次入力され格
納される。そして、このデータバッファ１０に格納され
たデータ列の先頭から順にデータ圧縮処理が行われ、処
理が終了したデータ列が次に辞書バッファ１２に格納さ
れるようになっている。

【００３０】データバッファ１０および辞書バッファ１
２は所定の容量（例えば数千ワード分）を有している
が、図２では説明の都合上それぞれが１６ワード分の容
量を有するものとする。また、データバッファ１０に格
納したデータ列と辞書バッファ１２に格納したデータ列
とを比較する必要があるため、データバッファ１０と辞
書バッファ１２とは同じ容量であるか、あるいは辞書バ
ッファ１２の方が大きな容量を有している。

【００３１】バッファ更新部１４は、データバッファ１
０および辞書バッファ１２の内容を更新するものであ
る。データバッファ１０に格納された文字列は、その先
頭から順に符号化されるため、この符号化が終了したデ
ータ列を辞書バッファ１２に移すとともに、その分の新
たな非圧縮データをデータバッファ１０に追加して格納
する処理が行われる。

【００３２】一致長符号化部１６は、データバッファ１
０に格納されたデータ列の先頭部分に位置する１ワード
あるいは複数ワードが辞書バッファ１２内の辞書に存在
するか否かを検索し、その一致長に対応する一致長符号
を出力する。この一致長符号の作成は、一致長符号テー
ブル１８に基づいて、検出された一致長に１対１に対応
する一致長符号を得ることにより行われる。

【００３３】図３は、一致長符号テーブル１８の詳細な
内容を示す図である。同図に示すように、不一致の場合
には一致長符号“00”が割り当てられ、一致長が長くな
るにしたがって次第にビット長が長い一致長符号が割り
当てられている。ただし、一致長に比例して一致長符号
のビット長が長くなるわけではないので、一致長が長く
なるに従い圧縮率が高まるように一致長符号テーブル１
８が作成されている。

【００３４】また、位置符号化部２０は、一致長符号化
部１６によって一致判定が行われた場合に、一致したデ
ータの辞書内の位置を符号化した位置符号を出力するも
のである。この符号化は、位置符号テーブル２２を検索
することにより、辞書内の格納位置に１対１に対応した
位置符号を得ることにより行われる。また、辞書内の格
納位置としては、例えば図２においてデータバッファ１
０側に最も近いアドレスを「１」とし、以下遠ざかって
いくにしたがって「２」，「３」，……となる相対アド
レスが用いられる。

【００３５】図４は、位置符号化部２０内の位置符号テ
ーブル２２の詳細な一例を示す図である。同図に示すよ
うに、相対アドレス値（位置）が小さいものほど短いビ
ット長の位置符号が割り当てられており、一致長が同じ
である場合には最も最近に処理されたデータ列が繰り返
し現れた場合に最も圧縮率が高くなるようになってい
る。

【００３６】なお、上述した図３および図４で示した一
致長符号および位置符号は、ともに可変長符号となって
おり、それらの符号を分離するための特別なビットデー
タを挿入するわけではないので、後の伸張処理によって
その内容のみから分離できるような内容の符号が割り当
てられている。

【００３７】順位符号化部２４は、一致長符号化部１６
によって不一致判定が行われた場合に、データバッファ
１０に格納された先頭のワードに対応した順位符号を出
力するものである。この符号化は、この先頭のワードの
順位を順位テーブル２７を検索して読み出した後、各ワ
ードの最近の出現確率が高いもの程短い順位符号を対応
させた順位符号テーブル２６を検索することにより行わ
れる。

【００３８】図５は、順位符号化部２４内の順位符号テ
ーブル２６の詳細な一例を示す図である。同図に示すよ
うに、出現頻度の高い順位ほど短い符号が割り当てられ
ており、辞書内に該当する文字が存在しない場合であっ
ても高い圧縮率が得られるようになっている。

【００３９】テーブル更新部２８は、順位符号化部２８
内の順位符号テーブル２６の更新を行う。すなわち、上
述したように順位符号テーブル２６は、最近の出現頻度
の高い順に短い符号を割り当てる必要があるため、符号
化が行われる毎に該当する文字の順位を上げる必要があ
り、この処理をテーブル更新部２８によって行ってい
る。

【００４０】次に、上述した構成を有する一実施例のデ
ータ圧縮装置の動作を説明する。一例として、図２に示
すデータ列が入力され、データバッファ１０および辞書
バッファ１２のそれぞれに未処理のデータ列および処理
済みのデータ列が格納されているものとする。

【００４１】まず、一致長符号化部１６は、辞書バッフ
ァ１２内の辞書において、入力されてデータバッファ１
０内に格納されたデータ列に一致する最も長いデータ列
の検索を行う。図２に示す具体例においては、まずデー
タバッファ１０に格納された先頭の文字「Ｇ」が辞書バ
ッファ１２の辞書内に存在するか否かが検索され、存在
する場合には次に先頭の２文字「ＧＣ」が存在するか否
かが検索される。このようにして辞書内に一致する文字
列が見出だされなくなるまで、文字列の検索が行われ
る。

【００４２】ところで、図２に示す場合にはデータバッ
ファ１０内の先頭の文字「Ｇ」が辞書バッファ１２の辞
書内に存在しないため、一致長が「０」となる。一致長
符号化部１６は、図３に内容を示した一致長符号テーブ
ル１８を検索し、一致長「０」に対応する一致長符号
“00”を読出して出力する。

【００４３】また、上述した不一致を示す情報が一致長
符号化部１６から順位符号化部２４に入力され、順位符
号化部２４における処理が開始される。

【００４４】順位符号化部２４は、データバッファ１０
内の先頭に位置する文字「Ｇ」の順位を順位テーブル２
７から読出し、この順位に基づいて順位符号テーブル２
６を検索することにより、対応する順位符号を読出して
出力する。このように辞書バッファ１２内の辞書に該当
する文字が存在しない場合には、データバッファ１０内
の先頭文字に対応して、一致長符号化部１６から一致長
符号“00”が、順位符号化部２４から順位符号が順に圧
縮データとして出力される。

【００４５】このようにして、順位符号化部２４による
順位符号の作成が行われた後、テーブル更新部２８によ
って順位テーブル２７の更新が行われる。

【００４６】図６は、順テーブルの更新を説明するため
の図である。同図（Ａ）に示すように、例えば文字
「Ｇ」の出現頻度が現時点において第８番目であった場
合には、順位符号化部２４は、この順位「８」に対応す
る順位符号“010011”を図５に示した順位符号テーブル
２６から読み出す。この処理に続けて、あるいはこの処
理と並行してテーブル更新部２８は文字「Ｇ」の順位を
上げる処理を行う。例えば、図６（Ｂ）に示すように順
位を１つ上げて順位テーブル２７の更新を行う。

【００４７】このようにデータ圧縮が行われると、バッ
ファ更新部１４は、処理の対象となった文字「Ｇ」のみ
を辞書バッファ１２に移すとともに、データバッファ１
０を１文字分更新する。図７は、更新後のデータバッフ
ァ１０および辞書バッファ１２の内容を示す図である。
同図（Ａ）は、図２に示したデータバッファ１０の先頭
文字「Ｇ」のみが辞書バッファ１２に移された状態を示
している。

【００４８】以上は、辞書バッファ１２内の辞書に該当
する文字がない場合のデータ圧縮であったが、次に、辞
書内に該当する文字列が存在する場合について説明す
る。

【００４９】一致長符号化部１６は、次にデータバッフ
ァ１０の先頭に位置する文字あるいは文字列が辞書バッ
ファ１２の辞書内に存在するか否かを検出する。図７
（Ａ）に示す場合には、先頭の文字「Ｃ」が同図（ａ）
に示すように辞書バッファ１２の相対アドレス「２」に
存在する。同様に、先頭の２文字「ＣＢ」が同図（ｂ）
に示すように辞書バッファ１２の相対アドレス「９」，
「１０」に存在する。同様に、先頭の文字列「ＣＢＡＤ
ＡＣＢＥＢＡＤＦＤＡ」が辞書バッファ１２の相対アド
レス「３」〜「１６」に存在する。このように辞書内の
複数箇所にデータバッファ１０内の文字列が存在する
が、その中でも（ｃ）に示すものの一致長「１４」が最
も長いため、一致長符号化部１６は、この一致長「１
４」に対応する一致長符号“101001”を図３に内容を示
す一致長符号テーブル１８から読出して出力する。ま
た、このように一致した文字あるいは文字列がある場合
には、その旨の情報が位置符号化部２０に送られる。

【００５０】位置符号化部２０は、一致長符号化部１６
が検出した辞書内の最も長い文字列の先頭位置を相対ア
ドレスで表すとともに、この先頭位置に対応する位置符
号を図４に示した位置符号テーブル２２から読み出して
出力する。図７（Ａ）に示す場合においては、辞書内の
一致する文字列の先頭が相対アドレス「１６」に位置し
ており、位置符号化部２０は、この相対アドレス「１
６」に対応する位置符号“0100011 ”を図４に内容を示
す位置符号テーブル２２から読み出して出力する。

【００５１】このようにして、辞書内に対応する文字列
が存在する場合には、その一致長に対応する一致長符号
とその先頭文字の格納位置に対応する位置符号とを圧縮
データとして出力する。その後、バッファ更新部１４に
より、辞書バッファ１２およびデータバッファ１０の更
新が行われる。

【００５２】図７（Ｂ）には、このようにして更新が成
された後のデータバッファ１０および辞書バッファ１２
の内容が示されている。

【００５３】このように、本実施例のデータ圧縮装置に
よる処理を行った場合には、辞書内に該当する文字が存
在しない場合でもあっても出現頻度の高いもの程短いビ
ット長の符号によってデータ圧縮が行われ、辞書内に該
当する文字列が存在する場合にはその一致長と文字列の
格納位置とを符号化してデータ圧縮が行われる。したが
って、いずれの場合であっても元データよりもビット長
が短くなり、全体として非常に高い圧縮率を得ることが
できる。例えば、上述した処理によって得られる圧縮後
のデータは“00”，“010011”，“101001”，“010001
00”の計２１ビットであり、基データは「ＧＣＢＡＤＡ
ＣＢＥＢＡＢＦＤＡ」の１５文字となる。１文字を８ビ
ットで構成するものとすれば、１５文字は１２０ビット
であり、全体の圧縮率は（２１／１２０）×１００＝１
７％となり、圧縮効率が非常に高いことがわかる。

【００５４】また、上述した本実施例のデータ圧縮装置
によれば、入力される非圧縮データをデータバッファ１
０および辞書バッファ１２のそれぞれに順次格納するこ
とにより一連の圧縮処理が行われるため、予め辞書を作
成する等の処理が不要であり、リアルタイムで圧縮処理
を行うことができる。

【００５５】次に、上述したデータ圧縮に対応して行わ
れるデータ伸張について説明する。例えば上述したデー
タ圧縮によって得られた圧縮データ“00”，“01001
1”，“101001”，“01000100”が入力され、これらら
の圧縮データに基づいてデータ復元すなわちデータ伸張
を行う場合について説明する。

【００５６】図８は、本実施例のデータ伸張装置の構成
を示す図である。

【００５７】同図に示すデータ伸長装置は、一致長復号
化部３０，位置復号化部３４，順位復号化部３８，テー
ブル更新部４２，辞書読出し制御部４４，辞書バッファ
４６，辞書更新部４８を含んで構成される。

【００５８】一致長復号化部３０は、入力される圧縮デ
ータの先頭部分に位置する一致長符号を一致長符号テー
ブル３２に基づいて復号化することにより、対応する一
致長を出力する。また、この一致長符号は、“00”の場
合にはデータ圧縮において辞書内に該当する文字列がな
い不一致状態を示しているため、一致長復号化部３０
は、この一致長符号“00”が入力された場合には不一致
の旨を順位復号化部３８に通知する。一方、それ以外の
一致長符号が入力された場合には、一致した旨を位置復
号化部３４に通知する。

【００５９】なお、上述した一致長符号テーブル３２及
び後述する位置符号テーブル３６，順位符号テーブル４
０は、先に説明した一致長符号テーブル１８，位置符号
テーブル２２，順位符号テーブル２６と同一内容を有し
ており、その詳細は図３〜図５に示した通りである。

【００６０】位置復号化部３４は、一致長復号化部３０
から一致した旨の通知を受けた場合に、一致長符号に続
けて入力される位置符号の復号化を位置符号テーブル３
６に基づいて行う。この復号化処理によって辞書バッフ
ァ４６内の位置データが出力される。

【００６１】辞書読出し制御部４４は、位置復号化部３
４から出力される位置データに基づいて、辞書バッファ
４６内の格納位置を特定し、この格納位置を先頭アドレ
スとしてそれに続く一致長分のデータを伸張データとし
て出力する。

【００６２】また、順位復号化部３８は、一致長復号化
部３０から不一致の旨が通知されると、順位復号テーブ
ル４０に基づいて、一致長符号に続けて入力される順位
符号から対応する順位を読み出す。また、順位復号化部
３８は、順位テーブル４１に基づいて、順位復号テーブ
ルから読み出した順位に対応する文字を伸張データとし
て出力する。テーブル更新部４２は、順位復号化部３８
によって順位テーブル４１がアクセスされる毎にこの順
位テーブル４１の内容を更新する。

【００６３】また、辞書更新部４８は、辞書読出し制御
部４４あるいは順位復号化部３８から伸張データが出力
される毎に辞書バッファ４６の更新を行う。具体的に
は、伸張後の非圧縮データである文字あるいは文字列を
辞書バッファ４６内の辞書に含めると共に、古くなった
辞書内の文字をこの新規に含めた文字あるいは文字列の
分だけ削除する処理を行う。

【００６４】次に、上述した構成を有するデータ伸張装
置の動作について説明する。

【００６５】図９は、辞書バッファ４６の内容の一例を
示す図である。同図（Ａ）は、上述した圧縮処理によっ
て得られた圧縮データが入力される前の状態に対応する
ものであり、図２に示したデータ圧縮装置の辞書バッフ
ァ１２の格納内容と同じとなっている。

【００６６】圧縮データが入力されると、まず一致長復
号化部３０は、その先頭部分に位置する可変長の一致長
符号を分離し、一致長符号テーブル３２に基づいて復号
化処理を行う。最初に入力される一致長符号は“00”で
あるため、一致長復号化部３０は、図３に示すようにこ
の一致長符号に対応する一致長「０」を読出して出力す
る。

【００６７】次に順位復号化部３８は、上述した一致長
符号に続けて入力される順位符号“010011”に対応する
順位データ「８」を順位テーブル４１から読み出す。そ
して、この順位データに基づいて順位符号テーブル４０
をアクセスし、対応する１文字を特定し、伸張データと
して出力する。

【００６８】なお、この順位テーブル４１は上述した圧
縮装置の順位テーブル２７に対応するものであり、同一
の手順にしたがってテーブル更新部４２による更新が行
われるようになっている。すなわち、上述した順位復号
化部３８による処理は、図６（Ａ）に示した内容を有す
る順位テーブル４１を用いることにより行われ、この処
理が終了した後テーブル更新部４２よる更新処理が行わ
れて、順位テーブル４１は同図（Ｂ）の内容となる。

【００６９】このようにして、辞書バッファ４６内に該
当する文字が存在しない場合の伸張処理が行われる。同
様にして次の圧縮データが入力されると、一致長復号化
部３０は、その先頭部分に位置する一致長符号“10100
1”のみを分離し、一致長符号テーブル３２をアクセス
することにより、対応する一致長「１４」を出力する。

【００７０】また、位置復号化部３４、一致長復号化部
３０に入力される一致長符号が“00”でないことによ
り、あるいは一致長復号化部３０から出力される一致長
が「０」でないことにより処理を開始する。すなわち、
位置復号化部３４は、一致長符号に続けて入力される位
置符号“101001”を分離し、位置符号テーブル３６をア
クセスすることにより、対応する位置データ「１６」を
読出して出力する。

【００７１】次に、辞書読出し制御部４４は、位置復号
化部３４から出力される位置データに基づいて辞書バッ
ファ４６の格納位置（該当する文字列の先頭アドレス）
を特定し、この格納位置を先頭として格納されている一
致長分の文字列を順に読出し、伸張データとして出力す
る。上述したデータ圧縮装置において説明したように、
位置復号化部３４から出力される位置データは辞書内の
文字列の先頭部分の格納位置を示すものであり、データ
の最後尾からの相対アドレスとして認識されている。

【００７２】このようにして順位復号化部３８によって
伸張処理が行われた後、辞書更新部４８により図９
（Ｂ）に示すように辞書バッファ４６の更新が行われ
る。また、次に位置復号化部３４，辞書読出し制御部４
４等により伸張処理が行われた後、辞書更新部４８によ
り図９（Ｃ）に示すように辞書バッファ４６の更新が行
われる。

【００７３】このように、圧縮データが入力されると、
その先頭に位置する一致長符号に基づいて一致長の復号
が行われるとともに、この一致長符号に基づいて次に続
けて入力される符号が位置符号であるか順位符号である
かが判明し、位置符号化部３４あるいは順位符号化部３
８による処理が行われる。位置符号であった場合には、
さらに辞書読出し制御部４４によって辞書バッファ４６
内の辞書がアクセスされ、データの伸張処理が行われ
る。したがって、いずれの場合でもあっても順次入力さ
れる圧縮データに基づいてリアルタイムに伸張処理を行
うことができる。

【００７４】次に、上述した本実施例のデータ圧縮装置
をさらに具体化した構成および動作について説明する。
具体的にデータ圧縮処理を行う場合には、辞書バッファ
内の辞書の検索を速やかに行う必要がある。そのための
工夫として、辞書バッファに対応させてトップバッファ
およびチェーンバッファが設けられており、検索対象と
なる文字が速やかに検索できるようになっている。

【００７５】図１０は、トップバッファおよびチェーン
バッファの内容およびその使い方を説明するための図で
ある。同図において、トップバッファ５０は、辞書バッ
ファ１２の内容をデータバッファ１０側から見ていった
場合に、該当する文字が最初に現れる辞書バッファ１２
のアドレスをこの該当文字に対応させて格納するもので
ある。例えば、図１０に示すように辞書バッファ１２の
アドレスが設定されているものとすれば、文字「Ａ」に
対応してこの文字のアドレスデータ「１」が格納されて
いる。同様に、文字「Ｂ」，「Ｃ」，……のそれぞれに
対応してアドレスデータ「６」，「０」，……が格納さ
れている。

【００７６】また、チェーンバッファ５２は、辞書バッ
ファ１２の内容をデータバッファ１０側から見た場合
に、同一の文字が次にどのアドレスに格納されているか
を示すチェーンデータを格納するものである。例えば、
文字「Ｃ」に着目すると、辞書バッファ１２のアドレス
「０」，「９」，「ｅ」の各アドレスに格納されてい
る。したがって、チェーンバッファ５２のアドレス
「０」，「９］のそれぞれには次に文字「Ｃ」が表われ
るアドレスである「９」，「ｅ」のそれぞれが格納され
る。また、データバッファ１０側からみて最後尾側に対
応するチェーンバッファ５２のアドレス「ｅ」にはそれ
以後該当する文字が存在しないことを示す何らかのデー
タ、例えばその文字と同一のアドレスデータや先頭アド
レス「０」等が格納されており、それ以後の文字列の検
索が不要であることがわかるようになっている。

【００７７】例えば、データバッファ１０に格納された
文字列の先頭「Ａ」を辞書内で検索する場合、まずトッ
プバッファ５０をアクセスすることにより、この文字
「Ａ」に対応するアドレスデータ「１」が読み出され
る。このアドレスデータは、対応する文字「Ａ」が辞書
バッファ１２のどのアドレスに最初に格納されているか
を示すものであり、次にこのアドレスに対応してチェー
ンバッファ５２をアクセスすることによりチェーンデー
タ「５」の読出しが行われる。以下同様にして、このチ
ェーンデータ「５」をアドレスとしてチェーンバッファ
５２をアクセスすることにより次のチェーンデータ
「ａ」が読み出され、以下同様にしてチェーンデータ
「ｃ」が読み出される。このようにして、文字「Ａ」が
辞書バッファ１２のアドレス「１」，「５」，「ａ」，
「ｃ」のそれぞれに格納されていることが簡単にわかる
ようになっている。その後、このようにして読み出され
た各アドレスを先頭アドレスとして格納されている文字
列についてデータバッファ１０内の文字列との一致判定
を行うことにより、何文字目までが一致しているかがわ
かるようになっている。

【００７８】ところで、本実施例においてはこの文字列
の一致長判定も複数文字を同時に比較することにより高
速に行っている。

【００７９】図１１は、４文字同時に一致判定を行う場
合の辞書バッファ１２の概略構成を示す図である。同図
に示すように、辞書バッファ１２を並列読出しが可能な
４つのＲＡＭ５４，５６，５８，６０によって構成す
る。これら４つのＲＡＭ５４〜６０は、それぞれ連続し
たアドレスが割り振られており、辞書バッファ１２の更
新を行う際には、連続した文字列を各文字単位で異なる
ＲＡＭ５４〜６０に格納するようになっている。一方、
データバッファ１０に格納された文字列と辞書バッファ
１２の格納内容を比較する際には、これら４つのＲＡＭ
５４〜６０から同時に、すなわち４文字同時に読出し
て、この読出した４文字とデータバッファ１０内の４文
字とを同時に比較できるようになっている。なお、この
辞書に対するデータの読み書き、および４文字同時の比
較動作の詳細については後述する。

【００８０】図１２は、データ圧縮装置の順位テーブル
２７あるいはデータ伸張装置の順位テーブル４１を更新
するための一例を示す図である。同図において、順位メ
モリ６２は順位テーブル２７あるいは順位テーブル４１
が格納されている。例えば、順位を知りたい文字のアス
キーコードをアドレスとして順位データを格納する。ま
た、データメモリ６４は、この順位データをアドレスと
して対応する文字のアスキーコードを格納するものであ
る。

【００８１】このような順位メモリ６２およびデータメ
モリ６４を用いて例えば文字「Ｇ」の順位を読み出すと
ともに、この順位を更新する場合について考える。

【００８２】まず、文字「Ｇ」対応するアスキーコ
ード“47h ”をアドレスとして、順位メモリ６２から順
位データ「８」の読出しが行われる。

【００８３】次に、この文字「Ｇ」の順位を上げる
ために、読出した順位「８」から１つだけ減算した順位
データ「７」を同一アドレスに書き込む。この状態で
は、順位データ「７」が２つ存在するので、もう一方の
順位データ「７」を「８」に変更する必要がある。

【００８４】このため、この重複した順位データ
「７」をアドレスとしてデータメモリ６４をアクセス
し、対応するデータ“54h ”（文字Ｔのアスキーコー
ド）の読出しを行う。そして、この読出したデータを一
旦保持するとともに、このアドレスに文字「Ｇ」のアス
キーコードである“47h ”を書き込む。

【００８５】次に、下げたい順位データ「８」をア
ドレスとしてデータメモリ６４をアクセスし、対応する
データとして上述したにおいて一旦保持したデータ
“54h”を格納する。

【００８６】最後に、において新たに書き込んだ
データ“54h ”をアドレスとして順位メモリ６２をアク
セスし、その内容である順位データ「７」に１だけ加算
した新たな順位データ「８」を書き込む。

【００８７】このようにして、順位メモリ６２の内容で
ある順位テーブル２７あるいは４１の検索および更新が
行われる。

【００８８】以下、このような各種の工夫を行ったデー
タ圧縮装置の具体的な構成について説明する。

【００８９】図１３および図１４は、本実施例のデータ
圧縮装置の詳細な構成を示す図である。同図に示す圧縮
制御部３００は、このデータ圧縮装置の全体を制御する
ものである。

【００９０】このデータ圧縮装置に入力された非圧縮デ
ータ列は、まず最初に入力ＦＩＦＯ２００に入力され
る。この入力ＦＩＦＯ２００は、データの入力速度と処
理速度の違いを吸収するためのものであり、例えば５１
２ワードの容量を有する。レジスタ（ＲＥＧ）２０２
は、入力ＦＩＦＯ２００から出力される１ワード分の文
字を一時保持するものであり、この保持した文字が辞書
・データバッファ２０４に入力されるとともに、マルチ
プレクサ（ＭＵＸ）２０６を介してトップアドレス演算
部２０７に入力される。

【００９１】辞書・データバッファ２０４は、図１に示
したデータバッファ１０と辞書バッファ１２とを１つの
メモリで構成したものである。データバッファ１０およ
び辞書バッファ１２は、図２および図７に示すように連
続して入力される２つのデータ列をそれぞれ格納すると
ともに、符号化の進行にともなってその境界を次第に移
動させるようになっている。したがって、これら２つの
バッファ１０，１２を１つのメモリで構成し、２つのバ
ッファの境界を示すポインタを設けることにより実現す
ることができる。

【００９２】このようにして構成される辞書・データバ
ッファ２０４は、データバッファ１０と辞書バッファ１
２とを合計した容量を有しており、例えば３文字分の圧
縮処理が終了した場合には、ポインタを３アドレス分進
めるとともに、データバッファ１０の最後尾部分に相当
する３アドレスに新たな入力データ列を書き込めばよ
い。

【００９３】また、マルチプレクサ２０６を介してトッ
プアドレス演算部２０７に入力される文字に基づいて、
トップバッファ２０８に対する新規登録処理あるいはチ
ェーンバッファ２２０に対する更新処理が行われる。す
なわち、図１０に示したように、トップバッファ５０
は、辞書バッファ内に最初に現れる文字のアドレスを格
納するものであり、辞書・データバッファ２０４が１文
字分更新されると、この１文字分のデータがデータバッ
ファから辞書バッファに移るため、この新規に移った文
字についてトップバッファ５０に対する新規登録が行わ
れる。また、このようにトップバッファ５０が更新され
ることにより、その更新情況に応じてチェーンバッファ
５２も更新される。

【００９４】このようにして、データ圧縮処理が終了し
た文字数分の新たな文字がレジスタ２０２を介して辞書
・データバッファ２０４に登録されるとともに、トップ
バッファ５０およびチェーンバッファ５２の更新処理が
行われる。

【００９５】次に、圧縮制御部３００の制御により、辞
書・データバッファ２０４のデータ領域の先頭部分に位
置する１文字が読み出され、レジスタ２０８および２１
０に一時保持される。このレジスタ２１０に保持された
１文字分のデータは、マルチプレクサ２０６を介してト
ップアドレス演算部２０７に入力され、トップバッファ
５０およびチェーンバッファ５２によりこの１文字に対
応する辞書・データバッファ２０４の辞書領域のアドレ
ス計算が行われる。計算されたアドレスは、レジスタ２
１２に一時保持された後、マルチプレクサ２１４を介し
て辞書・データバッファ２０４に入力される。圧縮制御
部３００は、このアドレスによって指定される辞書内の
１文字分のデータを読出し、この読み出されたデータが
コンパレータ（ＣＭＰ）２１６に入力される。

【００９６】コンパレータ２１６は、先にレジスタ２０
８に保持されたデータ領域の先頭に位置する１文字分の
データと、辞書領域の特定のアドレスから読み出された
１文字分のデータを比較し、一致した場合にはカウンタ
２１８の計数値を１だけ増加させる。コンパレータ２１
６によって一致が検出されると、圧縮制御部３００は、
辞書・データバッファ２０４のデータ領域および辞書領
域のアドレスをそれぞれ１ずつずらしていってコンパレ
ータ２１６によって不一致を検出するまで同様の処理を
繰り返す。したがって、コンパレータ２１６によって不
一致が検出された後カウンタ２１８の計数値を見ること
により辞書・データバッファ２０４のデータ領域に格納
された文字列の先頭から何文字までが一致しているかを
知ることができる。

【００９７】コンパレータ２１６によって一旦位置が検
出された後、不一致を検出した場合には、圧縮制御部３
００の制御によりレジスタ２１２の値によってチェーン
バッファ５２のアドレス指定を行い、次に候補となる文
字の辞書領域のアドレスが読み出され、この値が再度レ
ジスタ２１２に保持される。このようにして、データ領
域の先頭に位置する文字と同一の文字が格納されている
辞書領域の各アドレスについて何文字目まで一致するか
の判定が行われ、カウンタ２１８にはその最大値が保持
されるようになっている。

【００９８】また、このようにして最大一致長を求める
動作と並行して、対応する辞書領域内のアドレスの計算
が行われる。すなわち、チェーンバッファ５２から出力
される値と１つ前にこのチェーンバッファ５２から出力
されレジスタ２１２に保持された値との両方が減算器２
２０に入力されており、その差分を加算器２２２および
レジスタ２２４によって累積している。また、カウンタ
２１８は最大値を検出した際にその旨の信号を出力する
機能を有しており、この信号が出力された場合にレジス
タ２２６にレジスタ２２４の内容を転送するようになっ
ている。したがって、レジスタ２２６には最大一致長を
有する文字列の辞書領域の先頭アドレスのみが保持され
る。

【００９９】このようにして、カウンタ２１８から一致
した文字列の一致長が出力されるとともに、レジスタ２
２６から辞書・データバッファ２０４の辞書領域内にお
ける位置（アドレス）が出力される。

【０１００】次に、一致長符号化部２２８は、一致長符
号テーブル１８に基づいて、カウンタ２１８から出力さ
れた一致長に対応する一致長符号を読出して出力する。
また、位置符号化部２３０は、位置復号テーブル２２に
基づいて、レジスタ２２６から出力された位置データに
対応する位置符号を読出して出力する。この出力はマル
チプレクサ２３２を介してバイト変換部２３４に入力さ
れており、バイト変換部２３４ではそれぞれが可変長符
号である一致長符号と、位置符号とをバイト単位でまと
めて出力する。この出力が、出力ＦＩＦＯ２３６に一旦
保持された後圧縮データ列として外部に出力される。

【０１０１】上述したデータ圧縮動作は、コンパレータ
２１６によって一旦一致が検出された後、不一致を検出
した場合の動作であるが、一度も一致を検出しなかった
場合には以下に示す処理が行われる。

【０１０２】コンパレータ２１６によって一致が検出さ
れない場合には、カウンタ２１８による計数動作が行わ
れないため、カウンタ２１８から計数値「０」が出力さ
れる。このとき、一致長符号化部２２８からはこの計数
値「０」に対応する一致長符号“00”が出力され、バイ
ト変換部２３４に入力される。

【０１０３】また、この動作と並行して辞書内に存在し
ない先頭文字の符号化処理が行われる。すなわち、辞書
・データバッファ２０４のデータ領域の先頭に位置する
文字が出力されたときに、レジスタ２３８はこの１文字
を保持する。そして、この保持された文字データがマル
チプレクサ２４０を介して順位メモリ６２にアドレスと
して入力される。順位メモリ６２は、図１２に示したよ
うに、この入力された文字データをアドレスとして、こ
の文字の出現頻度を出力する。この順位メモリ６２の出
力は、レジスタ２４２に一旦保持された後、順位符号化
部２５２に入力される。

【０１０４】順位符号化部２５２は、順位符号テーブル
２６に基づいて、順位メモリ６２から出力された出現頻
度に対応する順位符号を読出して、マルチプレクサ２３
２を介してバイト変換部２３４に向け出力する。バイト
変換部２３４は、一致長符号化部２２８から出力される
一致長符号“00”と順位符号化部２５２から出力される
順位符号とをバイト単位で出力し、この出力が出力ＦＩ
ＦＯ２３６を介して圧縮データ列として外部に出力され
る。

【０１０５】また、順位メモリ６２の内容は、順位メモ
リ６２がアクセスされる毎に更新される。具体的には、
図１２に示した〜の手順に従って更新が行われる。
そのために、データメモリ６４およびレジスタ２２４が
設けられている。すなわち、順位メモリ６２から順位
を読み出すと同時に、この読み出した順位から１だけ
減算した値を再度順位メモリ６２に書き込む。次に、
順位メモリ６２に書き込まれた更新後の順位をアドレス
としてデータメモリ６４をアクセスし、レジスタ２３８
に保持されている文字データの書き込みを行う。次
に、更新前の順位をアドレスとしてデータメモリ６４を
再度アクセスし、更新後の順位に対応して格納されてい
たデータをこのアドレスに書き込む。最後に、この書
き込んだ文字データをレジスタ２２４に一旦保持した
後、この文字データによって順位メモリ６２を再度アク
セスし、該当する領域に更新前の順位の書込みを行う。
このようにして、順位メモリ６２とてデータメモリ６４
の内容の変更が行われる。

【０１０６】図１５は、辞書・データバッファ２０４の
辞書領域の詳細な構成を示す図である。同図に示す構成
は、図１１に示した複数のＲＡＭからの文字の同時読出
しを可能とするための詳細な構成である。

【０１０７】同図において、書込信号制御部２６２は、
４つのＲＡＭ２５４，２５６，２５８，２６０に対して
択一的な書込信号ＷＥ0 〜ＷＥ3 を入力するためのもの
である。書込信号制御部２６２にはＮビットの書込アド
レスＷＡの内の下位２ビットが入力されており、アドレ
スが１更新される毎に、書込信号ＷＥ０〜ＷＥ３が入力
されるＲＡＭが１つずつ巡回するようになっている。ま
た、４つのＲＡＭ２５４〜２６０のそれぞれには、Ｎビ
ットの書込アドレスＷＡの内の上位Ｎ−２ビットが入力
されており、書込信号制御部２６２から書込信号が入力
されたもののみに対する書込みが許可されるようになっ
ている。

【０１０８】また、読出アドレス制御部２６４は、入力
される読出アドレスＲＡに基づいて、４つのＲＡＭ２５
４〜２６０を同時にアクセスして、４つの文字データを
同時に読み出すものである。例えば、入力される読出ア
ドレスＲＡが３番目のＲＡＭ２５８のあるアドレスに対
応しているものとすれば、ＲＡＭ２５８，２６０に対し
て読出アドレスｉが入力されると同時に、ＲＡＭ２５
４，２５６に対して読出アドレスｉ＋１が入力される。
このようにしてアドレス指定が行われた４つのＲＡＭ２
５４〜２６０に対して読出信号ＳＩＧＲＤが入力され、
４文字分のデータが同時に読み出される。読出データ並
替部２６６は、このようにして読み出された４文字デー
タを、適宜並び替える動作を行う。上述した例では、Ｒ
ＡＭ２５８，２６０，２５４，２５６の順に並べ替えを
行い、４文字分の読出データＲＤ0〜ＲＤ3 として出力
する。

【０１０９】なお、このようにして辞書・データバッフ
ァ２０４から４文字分のデータを読出した場合には、４
文字同時に比較動作が行えるコンパレータ２１６を用い
るとともに、このコンパレータ出力を累積して加算する
機能をカウンタ２１８にもたせるようにすればよい。そ
して、コンパレータ２１６によって４文字の全てにおい
て一致検出を行った場合には、次に４文字についてこの
文字データの読出しおよび比較動作を継続すればよい。
このようにして、コンパレータ２１６によって４文字の
いずれかが一致しなくなるまで比較処理が繰り返され、
それまでの一致長が累積された後カウンタ２１８から出
力される。

【０１１０】このように、４文字同時にデータの読出し
を行って比較することにより、１文字毎に読出して比較
する場合に比べると約４倍の高速処理が可能となる。

【０１１１】次に、上述したデータ圧縮装置に対応する
動作を行うデータ伸張装置の詳細について説明する。

【０１１２】図１６は、データ伸張装置の詳細な構成を
示す図である。同図に示す伸長制御部４００は、このデ
ータ伸長装置の全体を制御するものである。

【０１１３】入力ＦＩＦＯ５００は、入力された圧縮デ
ータ列を一旦保持した後、ビット列変換部５０２に向け
出力する。このビット列変換部５０２は、入力される１
バイトあるいは数バイトのデータから可変長符号である
一致長符号を抽出するとともに、この一致長符号に続く
位置符号あるいは順位符号を抽出する。分離された一致
長符号は一致長復号化部５０４に、位置符号は位置復号
化部５０６に、順位符号は順位復号化部５０８にそれぞ
れ入力される。

【０１１４】一致長が「０」でない場合には、アドレス
制御部５１０は、一致長復号化部５０４から出力される
一致長と、位置復号化部５０６から出力される位置デー
タとに基づいて辞書バッファ５１２から必要な文字デー
タの読出しを行う。すなわち、位置復号化部５０６から
出力される位置データによって先頭アドレスが指定さ
れ、このアドレス以降に格納された一致長分の文字デー
タが読み出される。読み出された一連の文字データは、
マルチプレクサ５１４を介して出力ＦＩＦＯ５１６に入
力され、一旦保持された後非圧縮データ列として出力さ
れる。

【０１１５】一方、一致長が「０」の場合には、順位復
号化部５０８から出力される順位データに基づいて文字
データの復元が行われる。具体的には、この順位データ
がマルチプレクサ５１８を介してデータメモリ５２０に
アドレスとして入力される。データメモリ５２０は、順
位データに対応する文字データを出力し、この文字デー
タがレジスタ５２２に一旦保持された後、マルチプレク
サ５１４および出力ＦＩＦＯ５１６を介して非圧縮デー
タ列として出力される。

【０１１６】また、このデータメモリ５２０を更新する
ために順位メモリ５２４およびレジスタ５２６が設けら
れている。レジスタ５２２に一旦保持した文字データを
アドレスとして順位メモリ５２４がアクセスされ、対応
する順位データの更新が行われる。この更新された順位
データは、レジスタ５２６に一旦保持された後、マルチ
プレクサ５１８を介して再度データメモリ５２０にアド
レスとして入力され、今度は更新後の順位に対応して格
納されていたデータメモリ５２０の内容が読み出されて
レジスタ５２２に保持されるとともに、この内容が、デ
ータメモリ５２０から先に読み出した文字データによっ
て更新される。その後、再度レジスタ５２２に保持され
た文字データをアドレスとして順位メモリ５２４がアク
セスされ、順位が下がった文字データの正しい順位デー
タが書き込まれる。このようにして、順位メモリ５２４
およびデータメモリ５２０の内容変更が行われる。

【０１１７】このようにして非圧縮データの伸長が行わ
れると、伸長されたデータがレジスタ５２８に一旦保持
された後、辞書バッファ５１２に入力され、伸長制御部
４００による辞書バッファ５１２の更新が行われる。

【０１１８】なお、本発明は上記実施例に限定されるも
のではなく、本発明の要旨の範囲内で種々の変形実施が
可能である。

【０１１９】例えば、上述した実施例においては、辞書
内に存在しない文字に対する符号化処理を行った場合
に、その出現頻度の順位を１だけ更新する場合を例にと
り説明したが、２あるいは３順位をあげるようにしても
よい。

【０１２０】また、上述した実施例では、１ワードに１
文字を対応させて説明したが１ワードを２文字以上で構
成する場合や、文字とは直接関連のないビットデータを
対応させる場合等が考えられ、データの内容は特に限定
されるものではない。

【０１２１】

【発明の効果】上述したように、請求項１の発明によれ
ば、順次入力されるデータによって辞書が作成されるた
め、リアルタイムのデータ圧縮処理が可能となる。ま
た、辞書内に該当するデータが存在しない場合であって
も、出現確率の高いものほど短い符号を割り当てた圧縮
処理が行われるため、元データよりも短いビット長で符
号化処理を行うことができ、全入力データに対して常に
高い圧縮率を維持したデータ圧縮を行うことが可能とな
る。

【０１２２】また、請求項２の発明によれば、一致長符
号化手段をトップバッファとチェーンバッファとを含ん
で構成しており、データバッファ内の各ワードを辞書内
で検索する場合に、これらのトップバッファとチェーン
バッファをアクセスすることにより、辞書の該当アドレ
スを速やかに知ることができ、処理の高速化が可能とな
る。

【０１２３】また、請求項３の発明によれば、辞書バッ
ファを複数のメモリ素子によって構成しており、これら
メモリ素子から同時にデータの読出しを行っているた
め、メモリ素子の個数分のワード長を同時に比較するこ
とができ、一致長が長い場合の一致長判定を高速に処理
することができる。

【０１２４】また、請求項４の発明によれば、入力され
る圧縮データの先頭部分に位置する一致長符号が一致を
示している場合には、その次に位置する位置符号を復号
化することにより、辞書内の格納アドレスが得られ、こ
のアドレスを先頭アドレスとして一致長の分だけ辞書の
データの読出しを行うことにより伸張が行われる。ま
た、上述した一致長符号が不一致を示している場合に
は、順位テーブルを検索することによりデータの伸張が
行われる。このように、上述した請求項１〜３のデータ
圧縮装置によって圧縮されたデータをリアルタイムで伸
張処理することができる。

【図面の簡単な説明】

【図１】本発明を適用した一実施例のデータ圧縮装置の
概略構成を示す図である。

【図２】データバッファおよび辞書バッファと入力デー
タ列との関係を概略的に示す図である。

【図３】一致長符号テーブルの具体例を示す図である。

【図４】位置符号テーブルの具体例を示す図である。

【図５】順位符号テーブルの具体例を示す図である。

【図６】順位テーブルの更新を説明するための図であ
る。

【図７】データバッファと辞書バッファの更新を説明す
るための図である。

【図８】一実施例のデータ伸張装置の概略構成を示す図
である。

【図９】辞書バッファの内容の一例を示す図である。

【図１０】トップバッファおよびチェーンバッファの内
容およびその使い方を説明するための図である。

【図１１】４文字同時に一致判定を行う場合の辞書バッ
ファの概略構成を示す図である。

【図１２】順位テーブルの更新を具体的に説明するため
の図である。

【図１３】一実施例のデータ圧縮装置の詳細な構成を示
す図である。

【図１４】一実施例のデータ圧縮装置の詳細な構成を示
す図である。

【図１５】一実施例の辞書・データバッファ内のデータ
領域の詳細な構成を示す図である。

【図１６】一実施例のデータ伸張装置の詳細な構成を示
す図である。

【図１７】従来例の説明図である。

【図１８】従来例の説明図である。

【符号の説明】

１０データバッファ１２辞書バッファ１４バッファ更新部１６一致長符号化部１８一致長符号テーブル２０位置符号化部２２位置符号テーブル２４順位符号化部２６順位符号テーブル２７順位テーブル２８テーブル更新部

Claims

【特許請求の範囲】

【請求項１】順次入力される非圧縮データの中の最後
尾に位置する所定ワード長のデータ列を処理データとし
て、およびその前に位置する所定ワード長のデータ列を
辞書としてそれぞれ格納するデータバッファおよび辞書
バッファと、前記データバッファ内の処理データを構成する各ワード
について、前記辞書を構成する各ワードと一致するもの
があるか否かを検索し、その最も長い一致長を符号化し
た一致長符号を出力する一致長符号化手段と、前記一致長符号化手段によって一致の判定が行われた場
合に、一致したワード列の中で最もワード長が長いもの
の前記辞書内の位置を符号化した位置符号を出力する位
置符号化手段と、非圧縮データの各ワードについて存在確率の高い順にビ
ット長が短い順位符号を対応させた順位テーブルを有し
ており、前記一致長符号化手段によって不一致の判定が
行われた場合に、前記順位テーブルを検索することによ
り前記データバッファ内の処理データの先頭ワードに対
応する順位符号を出力する順位符号化手段と、前記順位符号化手段による符号化処理が行われた場合
に、符号化の対象となった前記処理データの先頭ワード
を考慮して前記順位テーブルを更新するテーブル更新手
段と、前記位置符号化手段あるいは前記順位符号化手段による
符号化が行われたときに、符号化が終了した前記処理デ
ータの一部あるいは全部を前記辞書バッファ内の辞書に
移すとともに、この移した分の非圧縮データを前記デー
タバッファに追加して格納する処理を行うバッファ更新
手段と、を備え、前記辞書内に処理データの各ワードと一致した
ワードがある場合には一致長とその位置とをそれぞれ符
号化し、一致したワードがない場合にはその旨を示す一
致長と処理データの先頭ワードとをそれぞれ符号化する
ことにより圧縮データを得ることを特徴とするデータ圧
縮装置。
【請求項２】請求項１において、前記一致長符号化手段は、前記辞書バッファ内の辞書の各ワードを先頭から順に見
ていった場合に、異なるワード毎に先頭アドレスを格納
するトップバッファと、前記辞書バッファ内の辞書の各ワードを先頭から順に見
ていった場合に、同じワードが次に前記辞書内のどのア
ドレスに格納されているかを示すデータを格納するチェ
ーンバッファと、を含み、前記データバッファ内の処理データの先頭ワー
ドに基づいて前記トップバッファおよび前記チェーンバ
ッファを検索することにより、該当する前記辞書内のア
ドレスを特定することを特徴とするデータ圧縮装置。
【請求項３】請求項１において、前記辞書バッファおよびデータバッファは、各アドレス
が互いに連続している複数のメモリ素子により構成され
ており、前記バッファ更新手段は、符号化が終了した前記処理デ
ータの一部あるいは全部を構成する各ワードを、前記複
数のメモリ素子のそれぞれに分散して格納し、前記一致長符号化手段は、前記複数のメモリ素子のそれ
ぞれから同時にデータを読み出すことにより、前記一致
検索を行うことを特徴とするデータ圧縮装置。
【請求項４】圧縮データを伸張して得られる非圧縮デ
ータの中の最後尾に位置する所定ワード長のデータ列を
辞書として格納する辞書バッファと、順次入力される圧縮データの先頭部分に位置する一致長
符号を復号化して具体的な一致長データを出力する一致
長復号化手段と、前記圧縮データの先頭部分に位置する一致長符号が一致
を示している場合に、その次に位置する位置符号を復号
化して、前記辞書内の格納位置を示すデータを出力する
位置復号化手段と、前記圧縮データの先頭部分に位置する一致長符号が一致
を示している場合に、前記位置復号化手段から出力され
るデータに基づいて前記辞書内の格納位置を特定し、こ
の格納位置を先頭アドレスとして前記一致長データの分
だけ前記辞書からデータの読出しを行って、非圧縮デー
タを出力する辞書読出し制御手段と、前記非圧縮データの各ワードについて存在確率の高い順
に短い順位符号を対応させた順位テーブルを有してお
り、前記圧縮データの先頭部分に位置する一致長符号が
不一致を示している場合に、その次に位置する順位符号
に基づいて前記順位テーブルを検索することにより前記
非圧縮データの復号化を行う順位復号化を行う順位復号
化手段と、前記順位復号化手段により復号化処理が行われたとき
に、復号化された非圧縮データを考慮して前記順位テー
ブルを更新するテーブル更新手段と、前記位置復号化手段あるいは前記順位復号化手段による
復号化が行われたときに、復号化が終了した非圧縮デー
タを含ませるように前記辞書の更新を行う辞書更新手段
と、を備え、一致長符号と位置符号および順位符号のいずれ
か一方とを組み合わせた圧縮データを復号化することに
より伸張データを得ることを特徴とするデータ伸張装
置。