JP3132774B2 - データ圧縮・復元装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はデータ圧縮・復元装置に
関し、特にユニバーサル符号化及び復号化によるデータ
の圧縮及び復元を行うデータ圧縮・復元装置に関する。

【０００２】近年、著しい技術開発によって、コンピュ
ータの処理速度及び記憶容量等は飛躍的な発展を遂げつ
つある。しかし、コンピュータでベクトル情報及び画像
情報等のデータを扱うようになってからは、従来以上に
取り扱うデータ量が増加しつつある。このようなデータ
量の大幅な増加に対処するため、データの内容を損なわ
ずにデータ量を減らす種々のデータ圧縮方式が提案され
ている。

【０００３】これらのデータ圧縮方式は、データに含ま
れる冗長な部分を省いて符号化することによって、デー
タを圧縮する方式である。データ圧縮方式によって、デ
ータ量を減らすことができ、結果的に記憶容量を減らす
ことができる。また、通信では圧縮したデータを伝送す
ることによって、同一内容の情報を速く伝送することが
できる。

【０００４】なお、「文字（Character ）」及び「文字
列（Character String）」の定義はＪＩＳ−Ｃ６２３０
に従うほか、情報理論で用いられている呼称を踏襲し、
１ワード単位で構成されるデータを「文字」と呼び、任
意のワード単位で構成されるデータを「文字列」と呼ぶ
ことにする。

【０００５】

【従来の技術】従来、上記のようなデータを圧縮する一
例として、ユニバーサル符号化方式が提案されている。
ユニバーサル符号化方式の代表的な例として、ＬＺ（Le
mpel-Ziv）符号化法と算術符号化法とがある。また、Ｌ
Ｚ符号化法には、ユニバーサル型と増分分解型（Increm
ental persing ）のアルゴリズムが提案されている。さ
らに、これらのアルゴリズムを改良した符号化法とし
て、ユニバーサル型に属するＬＺＳＳ符号化法と、増分
分解型に属するＬＺＷ（Lempel-Ziv-Welch）符号化法と
がある。

【０００６】なお、ＬＺ符号化法は、例えば、宗像清治
著「Lempel-Zivデータ圧縮法」、情報処理、pp.2〜6, V
ol.26, No.1, 1985 に詳しく掲載されている。また、Ｌ
ＺＳＳ符号化法は、T.C. Bell, "Better OPM/L Text Co
mpression", IEEE Trans.onCommu., Vol.COM-34, No.1
2, Dec.1986 に詳しく掲載されている。さらに、ＬＺＷ
符号化法は、T.A. Welch, "A Technique for High-Perf
ormance Data Compression", Computer, Jun.1984 に詳
しく掲載されている。そして、増分分解型の符号化法及
びＬＺＷ符号化法は、特開昭59−231683号、米国特許Ｎ
o. 4,558,302号において開示されている。

【０００７】これらの符号化法のうち、高速処理がで
き、アルゴリズムが簡単であるという利点から、一般的
にＬＺＷ符号化法が使用されてきた。ＬＺＷ符号化法
は、書き換え可能な辞書をもち、以下に示す処理によっ
て符号化を行う方法である。まず、新規の入力文字列を
相異なる部分文字列に分割し、この部分文字列が辞書に
登録されてなければ、出現した順に識別番号を付して全
て辞書に登録する。同時に、現在入力している部分文字
列のうち、最長の部分文字列と一致する部分文字列を辞
書から選択し、選択した部分文字列に付されている識別
番号で符号化する。

【０００８】以下、ＬＺＷ符号化法を使用したデータ圧
縮回路及びデータ復元回路の詳細について説明する。図
１５は、従来のデータ圧縮回路を示す図である。図にお
いて、従来のデータ圧縮回路は、辞書検索手段１２１、
辞書登録手段１２２、ユニバーサル符号化手段１２３及
び辞書Ｄ１２から構成される。

【０００９】辞書検索手段１２１は、辞書Ｄ１２に登録
されている登録文字列のうち、入力された入力文字列と
一致する登録文字列を検索する。辞書登録手段１２２
は、辞書検索手段１２１によって検索できなかった入力
文字列に識別番号を付して辞書１２２に登録する。ユニ
バーサル符号化手段１２３は、辞書検索手段１２１によ
って検索された登録文字列に付された識別番号、あるい
は辞書登録手段１２２によって入力文字列に新たに付さ
れた識別番号を出力符号に符号化する。

【００１０】辞書検索手段１２１、辞書登録手段１２２
及びユニバーサル符号化手段１２３の符号化処理は、シ
ーケンシャルに行われる。この符号化処理手順の一例を
図１６に示す。

【００１１】図１６は、従来のデータ圧縮回路による処
理手順を示す図である。図には、処理文字数欄１２５、
辞書検索欄１２６、辞書登録欄１２７及び符号化欄１２
８からなる表を示す。

【００１２】処理文字数欄１２５には、入力文字列が符
号化される際に処理される先頭からの文字順位を示す。
辞書検索欄１２６は、図１５の辞書検索手段１２１が処
理する内容を示す。辞書登録欄１２７は、辞書登録手段
１２２が処理する内容を示す。符号化欄１２８は、ユニ
バーサル符号化手段１２３が処理する内容を示す。な
お、円内の数字は処理手順の順番を示す。以下、「円内
の数字Ｘ」を「サイクルＸ」と表記する。

【００１３】まず、サイクル１〜サイクル３では、入力
された入力文字列の最初の１文字について、辞書登録手
段１２２が辞書Ｄ１２を検索する過程を示す。具体的に
は、辞書検索の結果、入力文字列と登録文字列がサイク
ル１及びサイクル２では一致せず、サイクル３で一致し
たことを示す。

【００１４】次に、サイクル４〜サイクル６では、入力
された入力文字列の２文字目について、辞書登録手段１
２２が辞書Ｄ１２を検索する過程を示す。具体的には、
入力文字列と登録文字列がサイクル４及びサイクル５で
は一致せず、サイクル６では辞書に登録されている文字
が無いことを示す。

【００１５】このとき、辞書登録手段１２２が入力文字
列に識別番号を付して辞書Ｄ１２に登録する。これがサ
イクル７に示す「登録」である。また、符号化するため
に、ユニバーサル符号化手段１２３が辞書登録の際に付
した識別番号を符号化する。これがサイクル８に示す
「符号化」である。以下、同様に符号化処理が行われ
る。

【００１６】また、図１７は、従来のデータ復元回路を
示す図である。図において、従来のデータ復元回路は、
ユニバーサル復号化手段１３１、辞書検索手段１３２、
スタック蓄積手段１３３、辞書登録手段１３４及び辞書
Ｄ１３から構成される。

【００１７】ユニバーサル復号化手段１３１は、入力さ
れた入力符号を復号化する。辞書検索手段１２１は、辞
書Ｄ１３に登録されている登録文字符号のうち、復号化
された文字符号と一致する文字符号を検索する。スタッ
ク蓄積手段１３３は、辞書検索手段１２１によって検索
された文字をスタックに蓄積し、検索が終了した時点で
蓄積した文字を全て出力する。辞書登録手段１３４は、
スタック蓄積手段１３３によって出力された復元文字列
が辞書Ｄ１３に登録されていない場合に、この復元文字
列に新たな符号を付して辞書Ｄ１３に登録する。

【００１８】これら、ユニバーサル復号化手段１３１、
辞書検索手段１３２、スタック蓄積手段１３３及び辞書
登録手段１３４の復号化処理は、シーケンシャルに行わ
れる。この復号化処理手順の一例を図１８に示す。

【００１９】図１８は、従来のデータ復元回路による処
理手順を示す図である。図には、処理符号数欄１３６、
復号化欄１３７、検索・蓄積欄１３８、文字列出力欄１
３９及び辞書登録欄１４０からなる表を示す。

【００２０】処理符号数欄１３６は、入力符号が復号化
される際に処理される符号数を示す。復号化欄１３７
は、図１７のユニバーサル復号化手段１３１が処理する
内容を示す。検索・蓄積欄１３８は、辞書検索手段１３
２が検索し、スタック蓄積手段１３３が検索された文字
を蓄積する処理を示す。文字列出力欄１３９は、スタッ
ク蓄積手段１３３が蓄積した文字を全て出力する処理を
示す。なお、円内の数字は処理手順の順番を示す。以
下、図１６と同様に、「円内の数字Ｘ」を「サイクル
Ｘ」と表記する。

【００２１】まず、サイクル１〜サイクル８では、入力
された最初入力符号列について、復号化及び出力文字列
として出力するまでの過程を示す。具体的に、各処理手
順は次のようになっている。サイクル１では、ユニバー
サル復号化手段１３１が入力符号を復号化する。サイク
ル２〜サイクル４では、辞書検索手段１３２がサイクル
１で復号化された文字符号を再帰的に検索して、スタッ
ク蓄積手段１３３が検索された文字をスタックに蓄積す
る。サイクル５〜サイクル７では、スタック蓄積手段１
３３が蓄積した文字を全て出力する。サイクル８では、
辞書登録手段１３４がスタック蓄積手段１３３によって
出力された出力文字列に新たな符号を付して辞書Ｄ１３
に登録する。以下、同様に復号化処理が行われる。

【００２２】

【発明が解決しようとする課題】しかし、従来のデータ
圧縮回路では、ある文字列に対して辞書検索、辞書登録
及び符号化を行なった後に、次の文字列を符号化する、
というようなバッチ・シリアル処理で圧縮処理を行なっ
ていた。また、データ復元回路でも同様に、ある符号に
対して復号化、辞書検索、スタック蓄積、辞書登録を行
なった後に、次の符号を復号化する、というようなバッ
チ・シリアル処理で復元処理を行なっていた。

【００２３】したがって、このようなバッチ・シリアル
処理では、符号化及び復号化処理の高速化が困難である
という問題点があった。本発明はこのような点に鑑みて
なされたものであり、入力データの圧縮処理を並列処理
により高速化するデータ圧縮回路を提供することを目的
とする。

【００２４】また、本発明の他の目的は、入力符号の復
元処理を並列処理により高速化するデータ復元回路を提
供することである。さらに、本発明の他の目的は、入力
データの圧縮処理及び入力符号の復元処理を、並列処理
により高速化するデータ圧縮・復元装置を提供すること
である。

【００２５】

【課題を解決するための手段】本発明では上記目的を達
成するために、図１に示すように、データ圧縮回路は第
１の辞書検索手段１、第１の辞書登録手段２、符号化手
段３、初期辞書アクセス手段４、通常辞書アクセス手段
５、初期辞書Ｄ１及び通常辞書Ｄ２から構成する。第１
の辞書検索手段１は、初期辞書アクセス手段４を介して
初期辞書Ｄ１に登録されている登録文字列のうち、入力
された入力文字列と一致する最長の登録文字列を検索す
る。初期辞書Ｄ１で検索できなかった場合は検索を終了
する。また、検索できた場合には通常辞書アクセス手段
５を介して通常辞書Ｄ２に登録されている登録文字列か
ら検索する。第１の辞書登録手段２は、第１の辞書検索
手段１によって検索された最長の登録文字列に一文字を
加えた文字列に識別番号を付し、通常辞書アクセス手段
５を介して通常辞書Ｄ２に登録する。符号化手段３は、
最長の登録文字列に付された識別番号を、出力符号とし
て符号化する。

【００２６】また、初期辞書Ｄ１及び通常辞書Ｄ２は、
外部ハッシュによるデータ検索及びデータ登録を行うよ
うに構成する。さらに、初期辞書Ｄ１には第２文字まで
の文字列についてデータ検索及びデータ登録を行い、通
常辞書Ｄ２には第３文字以降の文字列についてデータ検
索及びデータ登録を行うように構成する。

【００２７】そして、初期辞書Ｄ１及び通常辞書Ｄ２
は、完全ハッシュによるデータ検索及びデータ登録を行
うように構成する。それから、第１の辞書検索手段１、
第１の辞書登録手段２及び符号化手段３は、パイプライ
ンで接続され並列処理される。

【００２８】そのうえ、図３に示すように、データ復元
回路は、復号化手段１１、第２の辞書検索手段１２、第
１の蓄積手段１３、第２の蓄積手段１４、出力選択手段
１５、第２の辞書登録手段１６、辞書アクセス手段１７
及び辞書Ｄ３から構成する。復号化手段１１は、入力さ
れた入力符号を復号化する。第２の辞書検索手段１２
は、辞書アクセス手段１７を介して辞書Ｄ３に登録され
ている登録文字列のうち、復号化によって復元された文
字列と一致する文字列を検索する。第１の蓄積手段１３
及び第２の蓄積手段１４は、この検索によって復元され
た文字列を蓄積する。出力選択手段１５は、蓄積された
文字列のうち、出力する復元文字列を選択する。第２の
辞書登録手段１６は、選択された復元文字列のうち、辞
書Ｄ３に登録されていない文字列に、新たな符号を付し
て登録する。

【００２９】また、復号化手段１１、第２の辞書検索手
段１２、出力選択手段１５及び第２の辞書登録手段１６
は、パイプラインで接続され並列処理される。そして、
図５に示すように、データ圧縮・復元装置は、データ圧
縮回路及びデータ復元回路から構成する。データ圧縮回
路は第１の辞書検索手段１、第１の辞書登録手段２、符
号化手段３、初期辞書アクセス手段４、通常辞書アクセ
ス手段５、初期辞書Ｄ１及び通常辞書Ｄ２から構成す
る。また、データ復元回路は、復号化手段１１、第２の
辞書検索手段１２、第１の蓄積手段１３、第２の蓄積手
段１４、出力選択手段１５、第２の辞書登録手段１６、
辞書アクセス手段１７及び辞書Ｄ３から構成する。

【００３０】

【作用】データ圧縮回路において、第１の辞書検索手段
１が初期辞書アクセス手段４を介して、入力された入力
文字列を初期辞書Ｄ１から検索する。初期辞書Ｄ１から
検索されなかった場合は、同様に通常辞書アクセス手段
５を介して通常辞書Ｄ２から検索する。そして、第１の
辞書登録手段２が検索された最長の登録文字列に一文字
を加えた文字列に識別番号を付し、通常辞書アクセス手
段５を介して通常辞書Ｄ２に登録する。符号化手段３は
検索された最長の登録文字列に付された識別番号を出力
符号に符号化する。

【００３１】また、初期辞書Ｄ１及び通常辞書Ｄ２は、
外部ハッシュによるデータ検索及びデータ登録を行う。
さらに、初期辞書Ｄ１には第２文字までの文字列につい
てデータ検索及びデータ登録を行い、通常辞書Ｄ２には
第３文字以降の文字列についてデータ検索及びデータ登
録を行う。

【００３２】そして、初期辞書Ｄ１及び通常辞書Ｄ２
は、完全ハッシュによるデータ検索及びデータ登録を行
う。それから、第１の辞書検索手段１、第１の辞書登録
手段２及び符号化手段３は、パイプラインで接続して並
列処理する。

【００３３】そのうえ、データ復元回路において、復号
化手段１１が入力された入力符号を復号化し、第２の辞
書検索手段１２が辞書アクセス手段１７を介して辞書Ｄ
３のうち、復号化によって復元された文字列と一致する
文字列を検索し、第１の蓄積手段１３及び第２の蓄積手
段１４に復元された文字列を出力する。出力選択手段１
５は出力する復元文字列を選択し、第２の辞書登録手段
１６が未登録の復元文字列に新たな符号を付し、辞書ア
クセス手段１７を介して辞書Ｄ３に登録する。

【００３４】また、復号化手段１１、第２の辞書検索手
段１２、出力選択手段１５及び第２の辞書登録手段１６
は、パイプラインで接続して並列処理する。そして、デ
ータ圧縮・復元装置において、データ圧縮回路では第１
の辞書検索手段１が初期辞書アクセス手段４を介して、
入力された入力文字列を初期辞書Ｄ１から検索する。初
期辞書Ｄ１から検索されなかった場合は、同様に通常辞
書アクセス手段５を介して通常辞書Ｄ２から検索する。
そして、第１の辞書登録手段２が検索された最長の登録
文字列に一文字を加えた文字列に識別番号を付し、通常
辞書アクセス手段５を介して通常辞書Ｄ２に登録する。
符号化手段３は検索された最長の登録文字列に付された
識別番号を出力符号に符号化する。また、データ復元回
路では復号化手段１１が入力された入力符号を復号化
し、第２の辞書検索手段１２が辞書アクセス手段１７を
介して辞書Ｄ３のうち、復号化によって復元された文字
列と一致する文字列を検索し、第１の蓄積手段１３及び
第２の蓄積手段１４に復元された文字列を出力する。出
力選択手段１５は出力する復元文字列を選択し、第２の
辞書登録手段１６が未登録の復元文字列に新たな符号を
付し、辞書アクセス手段１７を介して辞書Ｄ３に登録す
る。

【００３５】

【実施例】以下、本発明の一実施例を図面に基づいて説
明する。図１は、本発明のデータ圧縮回路の実施例を示
す図である。図において、データ圧縮回路は第１の辞書
検索手段１、第１の辞書登録手段２、符号化手段３、初
期辞書アクセス手段４、通常辞書アクセス手段５、初期
辞書Ｄ１及び通常辞書Ｄ２から構成される。

【００３６】第１の辞書検索手段１は、初期辞書アクセ
ス手段４を介して初期辞書Ｄ１に登録されている登録文
字列のうち、あるいは通常辞書アクセス手段５を介して
通常辞書Ｄ２に登録されている登録文字列のうち、情報
源から入力された入力文字列と一致する最長の登録文字
列を検索する。第１の辞書登録手段２は、検索された最
長の登録文字列に一文字を加えた文字列に、識別番号を
付して初期辞書アクセス手段４を介して初期辞書Ｄ１
に、あるいは通常辞書アクセス手段５を介して通常辞書
Ｄ２に登録する。初期辞書アクセス手段４は、初期辞書
Ｄ１とのアクセスを行うための手段であり、例えば第１
の辞書検索手段１及び第１の辞書登録手段２から指令さ
れた論理アドレスを物理アドレスに変換して、初期辞書
Ｄ１とのデータの入出力を行う。通常辞書アクセス手段
５は、通常辞書Ｄ２とのアクセスを行うための手段であ
り、例えば第１の辞書検索手段１及び第１の辞書登録手
段２から指令された論理アドレスを物理アドレスに変換
して、通常辞書Ｄ２とのデータの入出力を行う。符号化
手段３は、例えばＬＺＷ符号化手段が使用され、検索さ
れた最長の登録文字列に付された識別番号を出力符号と
して符号化する。

【００３７】ここで、通常辞書Ｄ２に登録される「最長
の登録文字列に一文字を加えた文字列」は、次のような
文字列である。例えば、入力文字列が「ａｂｃｄ」であ
り、既に通常辞書Ｄ２に登録されている最長の登録文字
列が「ａｂ」であるならば、入力文字列のうち最長の登
録文字列と一致している「ａｂ」の次の一文字「ｃ」を
加えた文字列「ａｂｃ」である。

【００３８】なお、初期辞書アクセス手段４から初期辞
書Ｄ１へのアクセス、及び通常辞書アクセス手段５から
通常辞書Ｄ２へのアクセスは、後述する完全ハッシュ法
又は外部ハッシュ法によって行われる。

【００３９】また、第１の辞書検索手段１、第１の辞書
登録手段２及び符号化手段３の各手段は、いずれも図示
されていないパイプラインで接続されており、並列に処
理することができる。このパイプライン並列処理によ
り、複数の手段での符号化処理が可能となり、高速に符
号化処理を行うことができる。

【００４０】このような並列処理において、例外となる
のは、第１の辞書検索手段１及び第１の辞書登録手段２
が同時に初期辞書Ｄ１又は通常辞書Ｄ２へのアクセスを
要求する場合である。例えば、第１の辞書検索手段１と
第１の辞書登録手段２とが同時に初期辞書Ｄ１にアクセ
スを要求する場合である。このように、二以上の手段か
ら同時にアクセス要求がある状態を「衝突」という。衝
突が起きた場合には、例えば第１の辞書登録手段２が初
期辞書アクセス手段４を介して初期辞書Ｄ１とアクセス
した後、第１の辞書検索手段１が同様に初期辞書Ｄ１と
アクセスする、というようにシーケンシャルに辞書とア
クセスすることになる。しかしながら、このような衝突
は全体の符号化処理から見れば、極めて稀な現象であ
る。したがって、全体の処理時間から見れば無視できる
程の処理時間に過ぎないので、シーケンシャルに辞書と
アクセス処理を行なっても問題はない。以下、この符号
化処理手順の一例を図２に示す。

【００４１】図２は、本発明のデータ圧縮回路による処
理手順を示す図である。図には、処理文字数欄６、辞書
検索欄７、辞書登録欄８及び符号化欄９からなる表を示
す。処理文字数欄６には、入力文字列が符号化される際
に処理される先頭からの文字順位を示す。辞書検索欄７
は、図１の第１の辞書検索手段１が処理する内容を示
す。辞書登録欄８は、第１の辞書登録手段２が処理する
内容を示す。符号化欄９は、符号化手段３が処理する内
容を示す。

【００４２】なお、円内の数字は処理手順の順番を示
す。以下、「円内の数字Ｘ」を「サイクルＸ」と表記す
る。また、同じ円内の数字がある場合には、同時に並列
して処理が行われることを示す。そして、初期辞書Ｄ１
とのアクセスは初期辞書アクセス手段４を介して行わ
れ、また、通常辞書Ｄ２とのアクセスは通常辞書アクセ
ス手段５を介して行われるものとして、この過程の表記
を省略する。

【００４３】まず、サイクル１では、情報源から入力さ
れた入力文字列の最初の第１文字に続く第２文字につい
て、第１の辞書検索手段１が初期辞書Ｄ１を検索する。
サイクル２は、入力文字列の第３文字について、第１の
辞書検索手段１が通常辞書Ｄ２を検索する。サイクル３
は、入力文字列の第４文字について、第１の辞書検索手
段１が通常辞書Ｄ２を検索する。このとき、サイクル３
では、入力文字列の第４文字が通常辞書Ｄ２に登録され
ていない場合を示す。これらのサイクル１〜サイクル３
の過程は、シーケンシャルに各処理が行われる。

【００４４】次に、辞書検索欄７のサイクル４では、入
力文字列の第４文字に続く第５文字について、第１の辞
書検索手段１が初期辞書Ｄ１を検索する。同時に、辞書
登録欄８のサイクル４では、辞書検索欄７のサイクル３
で通常辞書Ｄ２に登録されていなかった入力文字列の第
１文字〜第４文字の文字列に識別番号を付して、第１の
辞書登録手段２が通常辞書Ｄ２に登録する。

【００４５】そして、辞書検索欄７のサイクル５では、
入力文字列の第５文字に続く第６文字について、第１の
辞書検索手段１が通常辞書Ｄ２を検索する。同時に、符
号化欄９のサイクル５では、辞書登録欄８のサイクル４
で行なった登録文字列に付された識別番号を符号化す
る。以下、同様な処理が続けられる。

【００４６】このように、辞書検索欄７において初期辞
書Ｄ１又は通常辞書Ｄ２を検索した結果、入力文字列が
登録されていなかった場合には、辞書登録欄８における
文字列の登録、及び符号化欄９における符号化を、辞書
検索と並列して行う。このため、符号化処理を高速に行
うことができる。

【００４７】図３は、本発明のデータ復元回路の実施例
を示す図である。図において、データ復元回路は、復号
化手段１１、第２の辞書検索手段１２、第１の蓄積手段
１３、第２の蓄積手段１４、出力選択手段１５、第２の
辞書登録手段１６、辞書アクセス手段１７及び辞書Ｄ３
から構成される。

【００４８】復号化手段１１は、例えばＬＺＷ復号化手
段が使用され、情報源から入力された入力符号を復号化
する。第２の辞書検索手段１２は、辞書アクセス手段１
７を介して辞書Ｄ３に登録されている登録文字列のう
ち、復号化によって復元された文字列と一致する文字列
を検索する。第１の蓄積手段１３及び第２の蓄積手段１
４は、検索によって復元された文字列を蓄積する。出力
選択手段１５は、蓄積された文字列のうち、出力する復
元文字列を選択する。第２の辞書登録手段１６は、選択
された復元文字列のうち、辞書Ｄ３に登録されていない
文字列に、新たな符号を付して登録する。辞書アクセス
手段１７は、辞書Ｄ３とのアクセスを行うための手段で
あり、例えば第２の辞書検索手段１２及び第２の辞書登
録手段１６から指令された論理アドレスを物理アドレス
に変換して、辞書Ｄ３とのデータの入出力を行う。

【００４９】なお、辞書アクセス手段１７から辞書Ｄ３
へのアクセスは、後述する完全ハッシュ法又は外部ハッ
シュ法によって行うこともできる。また、図１のデータ
圧縮回路で説明した「衝突」は、このデータ復元回路で
も発生する。例えば、第２の辞書検索手段１２が検索要
求を、第２の辞書登録手段１６が登録要求を同時にする
場合である。この場合、例えば第２の辞書登録手段１６
の登録処理後に、第２の辞書検索手段１２の検索処理を
行うようにシーケンシャルに行われる。データ圧縮回路
の場合と同様に、衝突は全体の復号化処理から見れば極
めて稀な現象であるため、全体の処理時間から見れば無
視できる程の処理時間に過ぎないので、シーケンシャル
に辞書とアクセス処理を行なっても問題はない。

【００５０】そして、復号化手段１１、第２の辞書検索
手段１２、第１の蓄積手段１３、第２の蓄積手段１４、
出力選択手段１５及び第２の辞書登録手段１６の各手段
は、いずれも図示されていないパイプラインで接続され
ており、並列に処理することができる。このパイプライ
ン並列処理により、複数の手段での符号化処理が可能と
なり、高速に符号化処理を行うことができる。以下、こ
の復号化処理手順の一例を図４に示す。

【００５１】図４は、本発明のデータ復元回路による処
理手順を示す図である。図には、処理符号数欄２１、復
号化欄２２、検索・蓄積欄２３、文字列出力欄２４及び
辞書登録欄２５からなる表を示す。

【００５２】処理符号数欄２１は、入力符号が復号化さ
れる際に処理される符号数を示す。復号化欄２２は、図
３の復号化手段１１が処理する内容を示す。検索・蓄積
欄２３は、第２の辞書検索手段１２が検索し、スタック
蓄積手段１３，１４が検索された文字を蓄積する処理を
示す。文字列出力欄２４は、出力選択手段１５がスタッ
ク蓄積手段１３，１４に蓄積した文字を全て出力する処
理を示す。辞書登録欄２５は、第２の辞書登録手段１６
が処理する内容を示す。

【００５３】なお、円内の数字は処理手順の順番を示
す。以下、図２と同様に、「円内の数字Ｘ」を「サイク
ルＸ」と表記する。また、同じ円内の数字がある場合に
は、同時に並列して処理が行われることを示す。そし
て、初期辞書Ｄ３とのアクセスは辞書アクセス手段１７
を介して行われるものとして、この過程の表記を省略す
る。

【００５４】まず、サイクル１では、情報源から入力さ
れた最初の入力符号について、復号化手段１１が復号化
する。復号化欄２２のサイクル２は、２番目の入力符号
について、復号化手段１１が復号化する。同時に、検索
・蓄積欄２３のサイクル２は、第２の辞書検索手段１２
が復号化した符号文字を辞書Ｄ３から検索する。また、
検索された復元文字は、スタック蓄積手段１３によって
スタックに蓄積される。これらのサイクル２は、並列し
て処理が行われる。

【００５５】次に、サイクル３及びサイクル４では、後
述する再帰的な復号により、第２の辞書検索手段１２が
復号化した符号文字を辞書Ｄ３から検索し、スタック蓄
積手段１３が検索された復元文字をスタックに蓄積す
る。

【００５６】そして、復号化欄２２のサイクル５では、
３番目の入力符号について、復号化手段１１が復号化す
る。同時に、検索・蓄積欄２３のサイクル５は、第２の
辞書検索手段１２が復号化した符号文字を辞書Ｄ３から
検索し、スタック蓄積手段１４が検索された復元文字を
スタックに蓄積する。さらに同時に、文字列出力欄２４
のサイクル５では、サイクル３〜サイクル４で蓄積した
文字列の１文字目を出力する。これらのサイクル５は、
並列して処理が行われる。

【００５７】それから、検索・蓄積欄２３のサイクル６
は、第２の辞書検索手段１２が復号化した符号文字を辞
書Ｄ３から検索し、スタック蓄積手段１４が検索された
復元文字をスタックに蓄積する。同時に、文字列出力欄
２４のサイクル６では、サイクル３〜サイクル４で蓄積
した文字列の２文字目を出力する。これらのサイクル６
も、並列して処理が行われる。以下、同様な処理が続け
られる。

【００５８】このように、復号化欄２２で行う復号化と
並列して、一方のスタック蓄積手段が検索した文字を蓄
積し、他方のスタック蓄積手段が蓄積した文字列を復元
文字列として出力する処理を行うことができる。このた
め、復号化処理を高速に行うことができる。

【００５９】図５は、本発明のデータ圧縮・復元装置の
実施例を示す図である。図において、データ圧縮・復元
装置はデータ圧縮回路及びデータ復元回路から構成され
る。データ圧縮回路は第１の辞書検索手段１、第１の辞
書登録手段２、符号化手段３、初期辞書アクセス手段
４、通常辞書アクセス手段５、初期辞書Ｄ１及び通常辞
書Ｄ２から構成される。また、データ復元回路は、デー
タ復元回路は、復号化手段１１、第２の辞書検索手段１
２、第１の蓄積手段１３、第２の蓄積手段１４、出力選
択手段１５、第２の辞書登録手段１６、辞書アクセス手
段１７及び辞書Ｄ３から構成される。

【００６０】なお、図１及び図３と同一の要素には同一
の番号を付し、説明を省略する。また、データ圧縮回路
及びデータ復元回路の作動は、それぞれ図１及び図３と
同じであるので説明を省略する。

【００６１】この装置により、データの圧縮処理及び復
元処理の処理速度が向上する。なお、図２及び図４で示
した処理手順のように、複数の手段が並列して処理を行
うことができるので、より装置全体の処理速度を向上さ
せることができる。

【００６２】次に、上記の各実施例における辞書検索手
順及び辞書登録手順について、まずハッシュ法について
説明する。ハッシュ法は、ハッシュ表（hash table）と
呼ばれる表を用いてデータの格納及びデータの検索を行
う方法の一つであり、データを登録するために検索キー
の内部コードωを用いて格納アドレスを決定する方法で
ある。このために、検索キーの内部コードωからアドレ
スを求める関数が必要となり、この関数は「ハッシュ関
数（hash function ）」と呼ばれている。また、ハッシ
ュ関数Ｈによって得られたアドレスＨ（ω）は「ハッシ
ュアドレス（hash address）」と呼ばれている。なお、
検索も登録の場合と同様に、ハッシュ関数によりハッシ
ュアドレスを求めて目的のアドレスのデータを検索す
る。

【００６３】このようなハッシュ法を使用した辞書検索
及び辞書登録では、ハッシュ関数Ｈをどのように選んで
も、相異なる検索キーの内部コードω₁ ，ω₂ に対し
て、ハッシュアドレスが Ｈ（ω₁ ）＝Ｈ（ω₂ ） となる場合が起こり得る。このような状態を「衝突」と
呼び、この衝突を回避するために外部ハッシュ法（「オ
ープンハッシュ法」又は「連鎖法」とも呼ばれている）
が用いられる。また、衝突が起こらないように、予め表
に検索キーの内部コードωにとり得る全ての値を用意す
る方法が完全ハッシュ法である。以下、外部ハッシュ法
による場合と完全ハッシュ法による場合とに分けて説明
する。

【００６４】図６は、外部ハッシュ法のデータ構造を示
す図である。外部ハッシュ法では、まずハッシュ関数Ｈ
によって得られるアドレスに対応する表、すなわちバケ
ットヘッダ（Bucket Headder）ＢＨと呼ばれる配列が用
意される。図では、このバケットヘッダＢＨにはハッシ
ュアドレスが０から（ｂ−１）までのｂ個のリストヘッ
ダ（list headder）が用意されている。そして、リスト
ヘッダの一つと、同一のハッシュアドレスを有する一以
上のデータ要素、すなわちリストＬ、との間はリスト構
造によって結合される。ここで、一つのリストは、デー
タを格納するデータ格納域と、次のリストへのポインタ
を格納するポインタ格納域とから構成される。

【００６５】例えば、図６に示すように、ハッシュアド
レス「０」に示すリストヘッダにはリストＬ０１へのポ
インタの設定によって、リストヘッダとリストＬ０１と
が結合される。この関係を矢印Ａ１で示す。また、リス
トＬ０１にはリストＬ０２へのポインタの設定によっ
て、リストＬ０１とリストＬ０２とが結合される。この
関係を矢印Ａ２で示す。なお、リストＬ０２以降がポイ
ンタによってリスト間が結合されない場合は、終端記号
「０」が設定される。以下、ハッシュアドレスが１から
（ｂ−１）までのリストヘッダも同様に、リストＬとは
リスト構造によって結合される。

【００６６】なお、データの検索は次の手順で処理が行
われる。なお、ここではハッシュ関数Ｈにより求められ
るハッシュアドレスが「３」である場合を例に説明す
る。求められたハッシュアドレス「３」に対応するバケ
ットヘッダＢＨのリストヘッダから、最初のリストＬ３
１へのポインタを取得する。そして、最初のリストＬ３
１内のデータと照合する。もし、データが一致しなけれ
ば、次のリストＬ３２へのポインタを取得し、次のリス
トＬ３２のデータと照合する。もし、データが一致しな
ければ、所望のデータが見つからなかったことを示す。
なお、リストＬ３２に次のリストへのポインタが設定さ
れているならば、同様の検索処理を経て、目的のデータ
を検索する。

【００６７】また、データの登録は次の手順で処理が行
われる。データの検索と同様に、ハッシュ関数Ｈにより
求められるハッシュアドレスが「３」である場合を例に
説明する。求められたハッシュアドレス「３」に対応す
るバケットヘッダＢＨのリストヘッダから最初のリスト
Ｌ３１へのポインタを取得する。そして、次のリストへ
のポインタが「０」になるまでリストをたどる。図６の
例ではリストＬ３２が最後のリストであるから、ここで
新たなデータのリストを生成し、生成したリストへのポ
インタをリストＬ３２内のポインタ格納域に設定する。

【００６８】このようなデータ構造を有する辞書におい
て、データの検索及び登録処理は次のように行われる。
図７は、外部ハッシュ法による辞書検索手順及び辞書登
録手順の一例を示す図である。図において、辞書は検索
及び登録処理を速くするために firstメモリＦＭ、next
メモリＮＭ及び extentionメモリＥＭの３つの物理的な
メモリから構成されている。また、これらの３つのメモ
リは登録するデータの内容に応じて初期辞書と、通常辞
書とに分けられる。

【００６９】まず、この辞書を使用したデータの検索
は、次の手順で処理が行われる。なお、ここでは検索す
る文字列が「Ｋ₂₂Ｋ₃₂Ｋ₄₂」であり、この文字列のハッ
シュ関数Ｈにより求められるハッシュアドレスが
「ω₁ 」である場合を例に説明する。

【００７０】まず、ハッシュ関数Ｈによって得られるア
ドレスω₁ から、初期辞書の firstメモリＦＭのアドレ
スω₁ に格納されている次のリストへのポインタω₂₁を
取得する。そして、次のリストへのポインタω₂₁から、
extentionメモリＥＭのアドレスω₂₁に格納されている
データＫ₂₁と照合する。この場合、文字列Ｋ₂₂Ｋ₃₂Ｋ ₄₂
の最初の文字Ｋ₂₂とは一致しないため、nextメモリＮＭ
のアドレスω₂₁から次のリストへのポインタω₂₂を取得
する。

【００７１】次に、次のリストへのポインタω₂₂から、
通常辞書の firstメモリＦＭのアドレスω₂₂に格納され
ている次のリストへのポインタω₃₁を取得する。以下、
初期辞書の場合と同様な検索が行われる。そして、最後
は extentionメモリＥＭのアドレスω₄₁に格納されてい
るデータＫ₂₁と照合したが、一致する文字列が検索でき
ずに終了した。この過程を図７では矢印で示す。

【００７２】また、この辞書を使用したデータの登録
は、次の手順で処理が行われる。なお、ここでは上記に
おいて検索できなかった文字列「Ｋ₂₂Ｋ₃₂Ｋ₄₂」を登録
する場合を例に説明する。上記のデータの検索と同様の
処理によって、次のリストへのポインタが「０」になる
までリストをたどる。この場合、nextメモリＮＭのアド
レスがω₄₁になる。ここで、文字Ｋ₄₂を extentionメモ
リＥＭの他のアドレスに生成する。図７では、このアド
レスがω₄₂であり、同じアドレスのnextメモリＮＭには
「０」が設定される。また、リストを連結するため、ne
xtメモリＮＭのアドレスω₄₁には、新たに生成したリス
トへのポインタであるω₄₂を登録する。こうして、新た
な文字列の登録が行われる。

【００７３】なお、上記のデータ検索及びデータ登録を
行う初期辞書には第２文字までの文字列について行い、
通常辞書には第３文字以降の文字列について行う。こう
することにより、入力文字列が最適に分散されるため、
データ検索及びデータ登録を行う際の処理時間を抑える
ことができる。

【００７４】また、初期辞書には第２文字までの文字
列、通常辞書は第３文字以降の文字列に限ることなく、
例えば初期辞書には第３文字までの文字列、通常辞書に
は第４文字以降の文字列というように、入力文字列の性
質に応じて変更してもよい。こうすることにより、様々
な入力文字列の性質に対応して最適な辞書を構成するこ
とができる。

【００７５】図８は、完全ハッシュ法による辞書検索手
順及び辞書登録手順の一例を示す図である。完全ハッシ
ュ法は、全く衝突が起こらないようなハッシュ関数によ
るキー検索法である。この完全ハッシュ法で構築される
辞書は、例えば後述する図１４に示す木構造であって、
各「ノード」ごとに２５６本の「枝」を持つような構造
を有する。

【００７６】図において、辞書は完全ハッシュメモリＰ
Ｍのみの物理的なメモリから構成され、登録するデータ
の内容に応じて初期辞書と、通常辞書とに分けられる。
また、完全ハッシュメモリＰＭのアドレスは、各文字列
のデータと一対一に対応させるため、ハッシュアドレス
ωとデータアドレスＫとから構成される。

【００７７】例えば、ハッシュアドレスωが２０ビット
で表現されるアドレスであり、データアドレスＫが８ビ
ットで表現されるアドレスならば、これらを合わせた２
８ビットのアドレスが完全ハッシュメモリＰＭのアドレ
スとして用いられる。すなわち、各ハッシュアドレスω
は、２５６個のデータアドレスＫのブロックごとの先頭
アドレスを示す。なお、図８では完全ハッシュメモリＰ
Ｍのアドレスを「ω_nn・Ｋ_xx」で表す。

【００７８】そして、この辞書を使用したデータの検索
は、次の手順で処理が行われる。なお、ここでは検索す
る文字列が「Ｋ₂ Ｋ₃ Ｋ₄ Ｋ₅ 」であり、この文字列の
ハッシュ関数Ｈにより求められるハッシュアドレスが
「ω₁ 」である場合を例に説明する。

【００７９】まず、ハッシュ関数Ｈによって得られるア
ドレスω₁ と、文字列の第１文字Ｋ ₂ のデータから、初
期辞書のアドレスω₁ ・Ｋ₂ に格納されているフラグＦ
Ｌを取得する。フラグＦＬは、このアドレスが有効か無
効かを「１」又は「０」で示す。この場合、フラグＦＬ
には「１」が設定されているので、文字Ｋ₂ は有効であ
る。したがって、検索する文字列の第１文字が辞書と一
致したことを示す。

【００８０】次に、文字列の第２文字Ｋ₃ が有効か否か
を検査するため、アドレスω₁ ・Ｋ ₂ に格納されている
次へのポインタω₂₁を取得する。そして、アドレスω₂₁
と、文字列の第２文字Ｋ₃ のデータから、初期辞書のア
ドレスω₂₁・Ｋ₃ に格納されているフラグＦＬを取得す
る。以下、同様の処理によって検索が行われる。そし
て、最後はアドレスω₄₁・Ｋ₅ に格納されているフラグ
ＦＬと照合して、一致する文字列が検索できずに終了し
ている。この過程を図８では矢印で示す。

【００８１】また、この辞書を使用したデータの登録
は、次の手順で処理が行われる。なお、ここでは上記に
おいて検索できなかった文字列「Ｋ₂ Ｋ₃ Ｋ₄ Ｋ₅ 」を
登録する場合を例に説明する。上記のデータの検索と同
様の処理によって、次のリストへのポインタが「０」に
なるまでリストをたどる。この場合、完全ハッシュメモ
リＰＭのアドレスがω₄₁・Ｋ₅ になる。ここで、フラグ
ＦＬを「１」に設定する。こうして、新たな文字列の登
録が行われる。

【００８２】次に、上記の実施例で示したＬＺＷ符号化
手段及びＬＺＷ復号化手段について説明する。図９は、
入力文字列をＬＺＷ符号の符号化アルゴリズムによって
符号化する場合の具体例を示す図である。この入力文字
列は、ａ，ｂ，ｃの３文字だけの組み合わせからなる文
字列である。まず、予め辞書に、１文字のａ，ｂ，ｃだ
けをそれぞれ符号１，２，３に対応づけて登録する初期
化を行う。

【００８３】まず、入力文字列７１を左から右へ一字ず
つ読み込む。最初の文字ａを読み込み、このａを語頭文
字（列）(prefix string) とする。次に、２番目の文字
ｂを読み込み、先の語頭文字ａにこのｂを加えたａｂを
辞書の登録文字列と照合する。このとき、ａｂに一致す
る文字列が辞書にないので、先の語頭文字ａの対応符号
１を符号化出力として出力する。この出力される符号
を、出力符号欄７２に示す。同時に、文字列ａｂを符号
４に対応させて辞書に登録する。この辞書に登録される
内容を、登録内容欄７３に示す。ここで、改めて２番目
の入力文字ｂを語頭文字とする。

【００８４】次に、入力文字列７１の３番目の文字ａを
読み込み、語頭文字ｂにこのａを加えたｂａを辞書の登
録文字列と照合する。このとき、ｂａに一致する文字列
が辞書にはないので、語頭文字ｂの対応符号２を符号化
出力として出力するとともに、文字列ｂａを符号５に対
応させて辞書に登録する。また、改めて３番目の入力文
字ａを語頭文字とする。

【００８５】さらに、４番目の文字ｂを読み込み、語頭
文字ａにこのｂを加えたａｂを辞書の登録文字列と照合
する。このとき、辞書にはａｂに一致する文字列が登録
されているので、このときはａｂを語頭文字列とする。
さらに、５番目の入力文字ｃを読み込み、語頭文字列ａ
ｂにこのｃを加えたａｂｃを辞書の登録文字列と照合す
る。このとき、ａｂｃに一致する文字列が辞書にないの
で、語頭文字列ａｂの対応符号４を符号化出力として出
力するとともに、文字列ａｂｃを符号６に対応させて辞
書に登録する。そして、改めて５番目の入力文字ｃを語
頭文字とする。

【００８６】以下、同様のアルゴリズムにより、符号化
と辞書登録を続ける。このアルゴリズムで入力文字列
ａ，ｂ，ａ，ｂ，ｃ，・・・に対して符号化が行われ、
図９の出力符号欄７２に示すような符号１，２，４，
３，・・・が符号化出力として出力される。そして、図
１１（Ａ）に示すような登録文字列９１と対応符号９２
との対応関係が辞書に登録される。

【００８７】図１０は、以上に例示した符号化の処理手
順を示すフローチャートである。図において、Ｓに続く
数字はステップ番号を示す。 〔Ｓ１０１〕予め初期化によって、入力される可能性の
ある全一文字に対しそれぞれ符号を対応させて辞書に登
録する。また、辞書において次に登録すべきアドレスｎ
を、例えば２５６に設定する。ここで、ｎは辞書に登録
される文字列に対応して符号を０，１，２，・・・と付
した場合、登録文字列の総数に相当する。さらに、入力
文字列を読み込み、入力した最初の文字を語頭文字列
（prefix string ）ωとする。

【００８８】〔Ｓ１０２〕次の入力文字Ｋを読み込む。 〔Ｓ１０３〕ステップＳ１０２において、入力文字デー
タが存在したか否かを判別する。もし、入力文字データ
が存在すればステップＳ１０５へ進み、存在しなければ
ステップＳ１０４へ進む。

【００８９】〔Ｓ１０４〕語頭文字列ωを辞書と照合
し、対応する符号code（ω）を読み出し、符号化出力と
して出力する。このとき、符号code（ω）のビット数が
〔log₂ｎ〕の２進数符号に変換して出力する。ここで、
記号〔ｘ〕は、数値ｘ以上の整数のうち、最小の整数を
表す。以下、この意味で記号〔ｘ〕を用いることにす
る。なお、このステップでは処理すべき文字列がないた
め、本ステップを実行後、本処理手順を終了する。

【００９０】〔Ｓ１０５〕語頭文字列ωに、ステップＳ
１０２で読み込んだ文字Ｋを加えた文字列ωＫを辞書と
照合し、文字列ωＫが辞書に登録されているか否かを判
別する。もし、登録されていればステップＳ１０６に進
み、登録されていなければステップＳ１０７に進む。

【００９１】〔Ｓ１０６〕文字列ωＫを改めて語頭文字
列ωとする。そして、再びステップＳ１０２に戻る。こ
のように、ステップＳ１０２〜ステップＳ１０６を繰り
返すことにより、入力文字列と一致する文字列として、
辞書に登録された文字列のうちの最大長の文字列が検索
される。

【００９２】〔Ｓ１０７〕語頭文字列ωを辞書と照合
し、対応する符号code（ω）を読み出し、符号化出力と
して出力する。このときの符号code（ω）のビット数
は、〔log₂ｎ〕となる。また、文字列ωＫにｎの値を対
応させて辞書に登録する。すなわち、辞書のアドレスｎ
に文字列ωＫを記憶する。さらに、ステップＳ１０２で
読み込んだ文字Ｋを語頭文字列ωとするとともに、辞書
アドレスｎをインクリメントして、つぎの新たな入力文
字列に対するステップＳ１０２以降の実行に備える。

【００９３】図１２は、図９に示した符号化出力を復元
する場合の具体例を示す図である。予め復元側の辞書
に、初期化によって、符号１，２，３だけがそれぞれ文
字ａ，ｂ，ｃに対応づけられて登録されている。

【００９４】まず、入力符号８１を左から右へ一つずつ
読み込む。最初の符号１を読み、辞書を参照して文字列
ａを復元する。このとき復元された文字列を、復元文字
列欄８２１に示す。最初の符号は、初期化によって必ず
辞書に登録されている。そして、２番目の符号２を読
み、辞書を参照して文字列ｂを復元する。このとき、前
回の入力符号１と今回復号した文字列の最初の一文字ｂ
とを組み合わせた「１ｂ」に符号４を対応させて辞書に
登録する。このときの登録された内容を、登録内容欄８
３に示す。

【００９５】次に、入力文字列８１の３番目の符号４を
読み、辞書を参照して対応する「１ｂ」を読み出す。さ
らに、「１ｂ」の符号１を、辞書を参照して対応する文
字ａを読み出す。このような一連の読み出し繰り返し動
作を「再帰的な復号」と呼ぶ。これを、再帰的復号欄８
２に示す。これによって、文字列ａｂが復元され、復元
文字列として出力する。出力される文字列を、復元文字
列欄８３１に示す。同時に、前回の入力符号２と今回復
元した文字列の最初の一文字ａとを組み合わせた「２
ａ」に、符号５を対応させて辞書に登録する。

【００９６】以下、同様のアルゴリズムにより文字列の
復元と辞書登録を続ける。このようにして入力符号１，
２，４，３，５，・・・に対して復元が行われ、図１２
の復元文字列欄８２１に示すような文字列ａ，ｂ，ａ
ｂ，ｃ，ｂａ，・・・が復元文字列として出力される。
そして、図１１（Ｂ）に示すような登録符号９３と対応
文字列９４との対応関係が辞書に登録される。

【００９７】図１３は、以上に例示した復号化の処理手
順を示すフローチャートである。図において、Ｓに続く
数字はステップ番号を示す。 〔Ｓ１１１〕予め初期化によって、入力される可能性の
ある符号に対しそれぞれ文字を対応させて辞書に登録す
る。また、辞書において次に登録すべきアドレスｎを、
例えば２５６に設定する。ここで、ｎは辞書に登録され
る文字列に対応して符号を０，１，２，・・・と付した
場合、登録文字列の総数に相当する。次に、入力符号を
読み込み、最初の入力符号CODE（バイナリコード）を１
０進数の入力符号ωに変換する。この場合、図１０の符
号化ではωは入力文字列であったが、この復号化ではω
は入力符号である点に注意されたい。そして、このωを
OLD ωとする。同時に、最初に入力する符号は既に辞書
に登録されているため、入力符号ωに対応する文字Ｄ
（ω）を辞書から検索し、復元された文字として出力す
る。なお、出力した文字を後述するステップＳ１１６の
例外処理のためにFINchar にセットしておく。

【００９８】〔Ｓ１１２〕次の入力符号CODEを読み込
む。 〔Ｓ１１３〕ステップＳ１１２において入力符号データ
が存在したか否かを判別する。もし、存在すればステッ
プＳ１１５へ進み、存在しなければ本処理手順を終了す
る。

【００９９】〔Ｓ１１４〕読み込んだ入力符号CODEから
入力符号ωに変換するとともに、この入力符号ωをINω
にセットする。 〔Ｓ１１５〕入力符号ωをｎと比較する。すなわち、入
力符号が辞書に登録されているか否か（ω≧ｎ）を判別
する。もし、ωがｎより小さいときにはステップＳ１１
７へ進み、ωがｎ以上のときにはステップＳ１１６へ進
む。なお、ωがｎ以上になるのは、例えば図１２の入力
符号欄８１が「８」のときである。

【０１００】〔Ｓ１１６〕ステップＳ１１１または前回
にステップＳ１１９で設定されたOLD ωおよびFINchar
の組（OLD ω，FINchar ）をωＫと置き換える。すなわ
ち、OLD ωにセットされた値をωに、FINchar にセット
された値をＫにセットする。そして、Ｋをスタックにプ
ッシュ（ＰＵＳＨ）する。なお、ωはステップＳ１１７
で復号化される。

【０１０１】〔Ｓ１１７〕通常、入力符号ωは前回まで
の処理で辞書に登録されているため、入力符号ωに対応
する文字列Ｄ（ω）を辞書から読み出す。読み出した文
字列Ｄ（ω）をω_i Ｋに分解する。ω_i は符号、Ｋは復
号化文字である。そして、文字列Ｄ（ω）が、ω_i Ｋに
分解できない１文字であるか否かを判別する。Ｄ（ω）
がω_i Ｋに分解できるならばステップＳ１１８に進み、
Ｄ（ω）が１文字であるならばステップＳ１１９へ進
む。

【０１０２】〔Ｓ１１８〕文字Ｋを一時的にスタックに
プッシュし、また符号ω_i を新たなωとし、再度ステッ
プＳ１１７に戻る。このステップＳ１１７およびステッ
プＳ１１８の実行を、Ｄ（ω）が１文字に至るまで繰り
返す。

【０１０３】〔Ｓ１１９〕ステップＳ１１８でスタック
にプッシュした各文字をＬＩＦＯ（Last In Fast Out）
形式でポップ（ＰＯＰ）して復元文字列を出力する。例
えば、図１２の入力符号欄８１が「５」の場合ならば、
ａ，ｂの順でスタックにプッシュされ、ｂａという復元
文字列が出力される。同時に、今回復元した文字列の最
初の一文字をFINchar とし、前回セットされた OLDωと
FINchar との組（ OLDω，FINchar ）からなる文字列
を、ｎの値に対応させて辞書に登録する。すなわち、こ
の文字列を辞書のアドレスｎに記憶する。さらに、ｎを
インクリメントし、ステップＳ１１４でセットされたIN
ωをOLD ωにセットして、次のステップＳ１１２以降の
実行に備える。

【０１０４】上述のように復号化処理では、図１３のス
テップＳ１１７〜ステップＳ１１９を繰り返し行うこと
によって符号化前のデータに復元する。すなわち、入力
符号ωは前回までの処理で辞書に登録されているため、
入力符号ωに対応する文字列Ｄ（ω）を辞書から読み出
す。また、読み出した文字列Ｄ（ω）をω_i Ｋに分解
し、この文字Ｋを一時的にスタックに退避させる。そし
て、符号ω_i を新たな入力符号ωとして、再度入力符号
ωに対応する文字列Ｄ（ω）を辞書から読み出す。これ
らの手順を、新たな入力符号ωが一文字になるまで再帰
的に繰り返す。そして、スタックに退避させた文字をＬ
ＩＦＯ形式でポップして出力するという方式である。

【０１０５】図１４は、上記処理手順等に使用した辞書
の木構造の一例を示す図である。この辞書の木構造は、
ＬＺＷ符号化手段及びＬＺＷ復号化手段において実現さ
れるアルゴリズムによる符号化及び復号化の際に用いら
れる辞書の内部構造を図示したものである。図１４にお
いて、円内の数字は識別番号を示し、この円内の数字が
付されている箇所を「ノード（node；節）」と呼ぶ。

【０１０６】辞書５０は、ルート（root；根）５１を起
点とする。このルート５１には、文字は割り当てられな
い。そして、ルート５１の一階層下、すなわち第１階層
５２には一文字目の文字が登録される。この一文字目の
文字の登録は、相異なる文字が登録され、主に辞書５０
の初期化の時に行われる。図には「ａ」，「ｂ」及び
「ｃ」の３文字が登録されているが、実際には８ビット
のデータで表現可能な２５６文字が登録される。

【０１０７】そして、第２階層５３から下の階層は、情
報源から入力された文字列を学習することによって登録
される文字である。なお、一つ下の階層を有するノード
を「枝（branch）」と呼び、一つ下の階層を有するノー
ドを「葉（leaf）」と呼ぶ。したがって、図では円内の
数字の２５，２６，１３，１４，２７，２８，１６，
６，・・・，２２，２３，２４のノードが「葉」であ
り、その他のノードは「枝」である。

【０１０８】なお、あるノードが現在は「葉」であって
も、学習により「枝」となる可能性がある。例えば、
「ａｃｄ」という文字列を辞書５０に登録する場合、文
字列「ａｃ」は第１階層５２が「ａ」（円内の数字
１）、第２階層５３が「ｃ」（円内の数字６）として登
録されているので、第２階層５３の「ｃ」の下の第３階
層５４に、新たに「ｄ」を登録することになる。このと
き、円内の数字６のノードは「葉」から「枝」に変わ
る。

【０１０９】上記の実施例の説明では、データ圧縮回路
において、符号はlog₂ｎ以上の最小の整数のビット数か
らなる出力符号で出力したが、本出願人が特願平3-1306
23号において開示したように、ビット端数補償、Phasin
g in Binary Codes 、あるいは多値算術符号からなる出
力符号で出力してもよい。

【０１１０】また、初期辞書Ｄ１、通常辞書Ｄ２及び辞
書Ｄ３は外部ハッシュ又は完全ハッシュに基づき構築
し、辞書５０は木構造に基づき構築したが、他の構築法
に基づき辞書を構築してもよい。例えば、二進分木（バ
イナリ・ツリー）法によって辞書を構築し、辞書に登録
された文字列等のデータを二進検索（バイナリ・サー
チ）により検索するようにしてもよい。

【０１１１】なお、上記の各実施例は、ワークステーシ
ョン等における文字コード、ベクトル情報、画像データ
などの圧縮及び復元に応用され、必要な記憶容量を大幅
に削減することができる。

【０１１２】また、通信回線を利用したデータ送受信に
おいても応用でき、通信時間の短縮を図ることができ
る。例えば、モデム、ファクシミリ等の通信機器に応用
することができる。

【０１１３】

【発明の効果】以上説明したように本発明では、データ
圧縮回路において、第１の辞書検索手段が初期辞書又は
通常辞書から、入力文字列と一致する最長の登録文字列
を検索し、同時に第１の辞書検索手段が最長の登録文字
列に一文字を加えた文字列に識別番号を付して通常辞書
に登録し、符号化手段が最長の登録文字列に付された識
別番号を出力符号に符号化するので、符号化処理を速く
行うことができる。

【０１１４】また、データ圧縮回路において、初期辞書
及び通常辞書は外部ハッシュによるデータ検索及びデー
タ登録を行うように構成したので、データ検索及びデー
タ登録が速くなり、符号化処理をより速く行うことがで
きる。

【０１１５】さらに、データ圧縮回路において、初期辞
書には第２文字までの文字列についてデータ検索及びデ
ータ登録を行い、通常辞書には第３文字以降の文字列に
ついてデータ検索及びデータ登録を行うように構成した
ので、データ検索及びデータ登録に係る処理時間を抑え
ることができる。

【０１１６】そして、データ圧縮回路において、初期辞
書及び通常辞書は完全ハッシュによるデータ検索及びデ
ータ登録を行うように構成したので、データ検索及びデ
ータ登録が速くなり、符号化処理をより速く行うことが
できる。

【０１１７】それから、第１の辞書検索手段、第１の辞
書登録手段及び符号化手段は、パイプラインにより並列
処理するので、高速に符号化処理を行うことができる。
そのうえ、データ復元回路において、復号化手段が入力
符号を復号化し、同時に第２の辞書検索手段が辞書から
復号化によって復元された文字列を検索し、第１の蓄積
手段及び第２の蓄積手段が復元された文字列を蓄積し、
出力選択手段が出力する復元文字列を選択し、第２の辞
書登録手段が未登録の復元文字列に新たな符号を付して
辞書に登録するので、復号化処理を速く行うことができ
る。

【０１１８】また、復号化手段、第２の辞書検索手段、
出力選択手段及び第２の辞書登録手段は、パイプライン
により並列処理するので、高速に復号化処理を行うこと
ができる。

【０１１９】そして、データ圧縮・復元装置において、
データ圧縮回路では第１の辞書検索手段が初期辞書又は
通常辞書から、入力文字列と一致する最長の登録文字列
を検索し、同時に第１の辞書検索手段が最長の登録文字
列に一文字を加えた文字列に識別番号を付して通常辞書
に登録し、符号化手段が最長の登録文字列に付された識
別番号を出力符号に符号化する。また、データ復元回路
では復号化手段が入力符号を復号化し、同時に第２の辞
書検索手段が辞書から復号化によって復元された文字列
を検索し、第１の蓄積手段及び第２の蓄積手段が復元さ
れた文字列を蓄積し、出力選択手段が出力する復元文字
列を選択し、第２の辞書登録手段が未登録の復元文字列
に新たな符号を付して辞書に登録するので、符号化処理
及び復号化処理を速く行うことができる。

【０１２０】したがって、各回路及び装置全体の処理速
度を向上させることができる。

【図面の簡単な説明】

【図１】本発明のデータ圧縮回路の原理説明図である。

【図２】本発明のデータ圧縮回路による処理手順を示す
図である。

【図３】本発明のデータ復元回路の原理説明図である。

【図４】本発明のデータ復元回路による処理手順を示す
図である。

【図５】本発明のデータ圧縮・復元装置の原理説明図で
ある。

【図６】外部ハッシュ法のデータ構造を示す図である。

【図７】外部ハッシュ法による辞書検索手順及び辞書登
録手順の一例を示す図である。

【図８】完全ハッシュ法による辞書検索手順及び辞書登
録手順の一例を示す図である。

【図９】符号化の具体例を示す図である。

【図１０】符号化の処理手順を示す図である。

【図１１】文字列と符号との対応関係図である。

【図１２】復号化の具体例を示す図である。

【図１３】復号化の処理手順を示す図である。

【図１４】辞書の木構造の一例を示す図である。

【図１５】従来のデータ圧縮回路を示す図である。

【図１６】従来のデータ圧縮回路による処理手順を示す
図である。

【図１７】従来のデータ復元回路を示す図である。

【図１８】従来のデータ復元回路による処理手順を示す
図である。

【符号の説明】 １ 辞書検索手段 ２ 辞書登録手段 ３ 符号化手段 ４ 初期辞書 ５ 通常辞書 １１ 復号化手段 １２ 辞書検索手段 １３ 第１の蓄積手段 １４ 第２の蓄積手段 １５ 出力選択手段 １６ 辞書登録手段 １７ 辞書

───────────────────────────────────────────────────── フロントページの続き (72)発明者 千葉 広隆 神奈川県川崎市中原区上小田中1015番地 富士通株式会社内 (56)参考文献 特開 平３−247167（ＪＰ，Ａ) 特開 昭62−263529（ＪＰ，Ａ) 特開 平４−267630（ＪＰ，Ａ) 特開 平４−129429（ＪＰ，Ａ) 特開 平４−123619（ＪＰ，Ａ) 特開 平４−76727（ＪＰ，Ａ) 特開 平３−262331（ＪＰ，Ａ) 特開 昭61−13340（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06F 5/00 H03M 7/30 - 7/46

Claims (8)

(57)【特許請求の範囲】
1. 【請求項１】 情報源から入力された入力文字列を、符
   号化することにより圧縮するデータ圧縮回路において、文字列を登録する初期辞書（Ｄ１）と、 前記初期辞書に登録された文字列及び前記初期辞書に含
   まれる文字列よりも長い文字列を登録する通常辞書（Ｄ
   ２）と、 前記 初期辞書（Ｄ１）又は前記通常辞書（Ｄ２）に登録
   されている登録文字列のうち、入力された入力文字列と
   一致する最長の登録文字列を検索する第１の辞書検索手
   段（１）と、 前記初期辞書（Ｄ１）とのアクセスを行う初期辞書アク
   セス手段（４）と、 前記通常辞書（Ｄ２）とのアクセスを行う通常辞書アク
   セス手段（５）と、 前記最長の登録文字列に一文字を加えた文字列に、識別
   番号を付して前記通常辞書（Ｄ２）に登録する第１の辞
   書登録手段（２）と、 前記最長の登録文字列に付された識別番号を、出力符号
   に符号化する符号化手段（３）と、を有し、 前記第１の辞書検索手段（１）の前記初期辞書（Ｄ１）
   への検索と、前記第１の辞書登録手段（２）の前記通常
   辞書（Ｄ２）への登録は同時に行うように構成した こと
   を特徴とするデータ圧縮回路。
2. 【請求項２】 前記初期辞書（Ｄ１）及び前記通常辞書
   （Ｄ２）は、外部ハッシュによるデータ検索及びデータ
   登録を行うように構成したことを特徴とする請求項１記
   載のデータ圧縮回路。
3. 【請求項３】 前記初期辞書（Ｄ１）及び前記通常辞書
   （Ｄ２）は、完全ハッシュによるデータ検索及びデータ
   登録を行うように構成したことを特徴とする請求項１記
   載のデータ圧縮回路。
4. 【請求項４】 前記初期辞書（Ｄ１）には第２文字まで
   の文字列についてデータ検索及びデータ登録を行い、前
   記通常辞書（Ｄ２）には第３文字以降の文字列について
   データ検索及びデータ登録を行うように構成したことを
   特徴とする請求項１記載のデータ圧縮回路。
5. 【請求項５】 前記第１の辞書検索手段（１）、前記第
   １の辞書登録手段（２）及び前記符号化手段（３）は、
   パイプラインにより並列処理されることを特徴とする請
   求項１，２，３又は４記載のデータ圧縮回路。
6. 【請求項６】 情報源から入力された入力符号を、復号
   化することにより復元するデータ復元回路において、 入力された入力符号を復号化する復号化手段（１１）
   と、 辞書（Ｄ３）に登録されている登録文字列のうち、前記
   復号化によって復元された文字列と一致する登録文字列
   を検索する第２の辞書検索手段（１２）と、 前記登録文字列を蓄積する第１の蓄積手段（１３）と、 前記登録文字列を蓄積する第２の蓄積手段（１４）と、 前記第１の蓄積手段（１３）又は前記第２の蓄積手段
   （１４）に蓄積された登録文字列のうち、いずれかの蓄
   積された登録文字列を選択し、復元文字列として出力す
   る出力選択手段（１５）と、 前記辞書（Ｄ３）に登録されている登録文字列のうち、
   前記復元文字列と一致する登録文字列を検索し、登録さ
   れていない前記復元文字列に新たな符号を付して前記辞
   書（Ｄ３）に登録する第２の辞書登録手段（１６）と、 前記辞書（Ｄ３）とのアクセスを行う辞書アクセス手段
   （１７）と、 を有することを特徴とするデータ復元回路。
7. 【請求項７】 前記復号化手段（１１）、前記第２の辞
   書検索手段（１２）、前記出力選択手段（１５）及び前
   記第２の辞書登録手段（１６）は、パイプラインにより
   並列処理されることを特徴とする請求項６記載のデータ
   復元回路。
8. 【請求項８】 情報源から入力された入力文字列又は入
   力符号を、符号化又は復号化することにより圧縮及び復
   元を行うデータ圧縮・復元装置において、文字列を登録する初期辞書（Ｄ１）と、 前記初期辞書に登録された文字列及び前記初期辞書に含
   まれる文字列よりも長い文字列を登録する通常辞書（Ｄ
   ２）と、 前記 初期辞書（Ｄ１）又は前記通常辞書（Ｄ２）に登録
   されている登録文字列のうち、入力された入力文字列と
   一致する最長の登録文字列を検索する第１の辞書検索手
   段（１）と、前記初期辞書（Ｄ１）とのアクセスを行う
   初期辞書アクセス手段（４）と、前記通常辞書（Ｄ２）
   とのアクセスを行う通常辞書アクセス手段（５）と、前
   記最長の登録文字列に一文字を加えた文字列に、識別番
   号を付して前記通常辞書（Ｄ２）に登録する第１の辞書
   登録手段（２）と、前記最長の登録文字列に付された識
   別番号を、出力符号に符号化する符号化手段（３）とか
   らなり、前記第１の辞書検索手段（１）の前記初期辞書
   （Ｄ１）への検索と、前記第１の辞書登録手段（２）の
   前記通常辞書（Ｄ２）への登録は同時に行うように構成
   したデータ圧縮回路と、 入力された入力符号を復号化する復号化手段（１１）
   と、辞書（Ｄ３）に登録されている登録文字列のうち、
   前記復号化によって復元された文字列と一致する登録文
   字列を検索する第２の辞書検索手段（１２）と、前記登
   録文字列を蓄積する第１の蓄積手段（１３）と、前記登
   録文字列を蓄積する第２の蓄積手段（１４）と、前記第
   １の蓄積手段（１３）又は前記第２の蓄積手段（１４）
   に蓄積された登録文字列のうち、いずれかの蓄積された
   登録文字列を選択し、復元文字列として出力する出力選
   択手段（１５）と、前記辞書（Ｄ３）に登録されている
   登録文字列のうち、前記復元文字列と一致する登録文字
   列を検索し、登録されていない前記復元文字列に新たな
   符号を付して前記辞書（Ｄ３）に登録する第２の辞書登
   録手段（１６）と、前記辞書（Ｄ３）とのアクセスを行
   う辞書アクセス手段（１７）とからなるデータ復元回路
   と、 を有することを特徴とするデータ圧縮・復元装置。