JPH04129429A - データ圧縮装置の辞書検索方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 【概要】

ユバ−サル符号化の一種である増分分解型の改良として
のＬＺＷ符号化によるデータ圧縮装置の辞書検索方式に
関し、 外部ハツシュ法のリスト構造を利用した辞書メモリの高
速読出を可能にして辞書検索時間を短縮することを目的
とし、 辞書メモリをファーストメモリ（索引メモリ）、ネクス
トメモリ（連結メモリ）及び候補文字を格納した拡張メ
モリでなる外部ハツシュ法に従ったリスト構造とし、ネ
クスメモリの索引アドレスを連続アドレスに構成し、入
力文字に基づく最初の検索に続いて連続アドレスによる
検索を行って高速化するように構成する。

【産業上の利用分野】

本発明は、ユバ−サル符号化の一種である増分分解型の
改良としてのＬＺＷ符号化によるデータ圧縮装置の辞書
検索方式に関する。 近年、文字コード、ベクトル情報、画像など様々な種類
のデータがコンピュータで扱われるようになっており、
扱われるデータ量も急速に増加してきている。大量のデ
ータを扱うときは、データの中の冗長な部分を省いてデ
ータ量を圧縮することで、記憶容量を減らしたり、速く
伝送したりできるようになる。 このような様々なデータを１つの方式でデータ圧縮でき
る方法としてユニバーサル符号化が提案されている。 ここで、本発明の分野は、文字コードの圧縮に限らず、
様々なデータに適用できるが、以下では、情報理論で用
いられている呼称を踏襲し、データの１ワ一ド単位を文
字と呼び、データが複数ワードッなかったものを文字列
と呼ぶことにする。 ユニバーサル符号の代表的な方法として、ジブーレンペ
ル（ｚｉｖ−Ｌｅｍｐｅｌ）符号がある（詳しくは、例
えば、宗像１”　ｚｉｖ−Ｌｅｍｐｅｌのデータ圧縮法
」、情報処理、Ｖｏｌ、２６．　Ｎｏ、　１．１９ｆ１
５年を参照のこと）。 ジフーレンペル符号では、 ■ユニバーサル型 ■増分分解型（Ｉｎｃｒｅｍｅｎｔａｌ　ｐａｒｓｉｎ
ｇ　）の２っのアルゴリズムが提案されている。 更に、ユニバーサル型アルゴリズムの改良として、ＬＺ
ＳＳ符号がある（Ｔ、　Ｃ，Ｂｅ１ｌ、　　”ＢｅＮｅ
ｒ　ＯＰＭ／Ｌ　Ｔｅｘｔ　Ｃｏｍｐｒｅｓｓｉｏｎ　
　、　ＩＥＥＥ　Ｔｒａｎｓ、　ｏｎ　Ｃｏｍｍｕｎ、
　、　ＶＯｌ、　Ｃ０Ｍ−３４，ＮＯ，１２，Ｉ！ＥＣ
，１９８６参照）。 また、増分分解型アルゴリズムの改良としては、Ｌ　Ｚ
Ｗ　（Ｌｅｍｐｅｌ−２ｉｖ−Ｗｅｌｃｈ）符号がある
（Ｔ、　Ａ、　ＷｅＩｃｈ、　”Ａ　Ｔｅｃｈｎｉｑｕ
ｅ　ｔａｒＨｉｇｈ−Ｐｅｒｆｏｒｍａｎｃｅ　Ｄａｔ
ａＣｏｍｐｔｅｓｓｉｏｎ　　、　Ｃｏｍｐｕｔｅｒ、
　Ｊｕｎｅ　１９８４参照）。 これらの符号の内、高速処理ができることと、アルゴリ
ズムの簡単さからＬＺＷ符号が記憶装置のファイル圧縮
などで使われるようになっている。

【従来の技術】

従来のＬＺＷ符号による符号化処理フローを第７図に示
し、復号化処理フローを第８図に示す。 まずＬＺＷ符号化処理は、書き替え可能な辞書を持ち、
入力文字列の中を相異なる文字列（部分列）に分け、こ
の文字列を出現した順に参照番号を付けて辞書に登録す
ると共に、現在入力している文字列を、辞書に登録しで
ある最長−散文字列の参照番号で表して符号化するもの
である。 第９図にＬＺＷ符号化の説明図を示すと共に第１０図に
ＬＺＷ復号化の説明図を示し、更に第１１図に復号化時
に作成される辞書構成例を示す。 尚、第９．１０．１１図では説明を簡単にするため、ａ
ｂｃの３文字の組合せからなるデータを圧縮、復元する
場合の例を取り上げている。 第７図のＬＺＷ符号化処理では、まずステップ８１、（
以下「ステップ」は省略）で予め辞書に全文字につき一
文字からなる文字列を初期値として登録してから符号化
を始める。 Ｓｌの符号化は入力した最初の文字Ｋにより辞書を検索
して参照番号ωを求め、これを語頭文字列とする。 次にＳ２で入力データの次の文字Ｋを読込み、Ｓ３で文
字入力が終了したか否かチエツクした後、Ｓ４に進んで
Ｓｌで求めた語頭文字列ωに８２で読込んだ文字Ｋを加
えた拡張文字列（ωＫ）が辞書にあるか否か探す。 Ｓ４で文字列（ωＫ）が辞書になければ、Ｓ６に進んで
Ｓｌで求めた文字にの参照番号ωを符号語ｃｏｄｅ　（
ω）として出力し、また文字列（ωＫ）に新たな参照番
号を付加して辞書に登録し、更にＳ２の入力文字Ｋを参
照番号ωに置き換えると共に辞書アドレスｎをインクリ
メントしてＳ２に戻って次の文字Ｋを読み込む。 一方、Ｓ４で文字列（ωＫ）が辞書にあればＳ５で文字
列（ωＫ）を参照番号ωに置き換え、再びＳ２に戻って
Ｓ４で文字列（ωＫ）が辞書から探せなくなるまで最大
一致長の検索を続ける。 第９，１０図を参照してＬＺＷ符号化を具体的に説明す
ると次のようになる。 まず第９図の入力データ１ｎｐｕｔは左から右へと読む
。最初の文字ａを入力した時、辞書には文字ａの他に一
致する文字列がないので、０ＵＴＰＵＴ　Ｃ０ＤＥｌ（
参照番号ω）を符号語して出力する。そして文字ａを語
頭文字列ωとする。 次に２番目の文字すを入力したとすると、この入力文字
を語頭文字列ωに加えた拡張文字列ωＫａｂは辞書にな
いことから、文字すの０ＵＴＰＵＴ　Ｃ０ＤＥ　２を符
号語として出力する。そして、拡張文字列ωに＝ａｂに
参照番号４を付けて辞書に登録する。実際の辞書登録は
第１０図の右側に示すように文字列１ｂとして登録され
る。そして文字すが語頭文字列ωとなる。 続いて３番目の文字ａを入力したとすると、文字すに語
頭文字列ωを加えた拡張文字列ωに＝ｂａ＝２ａは辞書
にないことから、文字ａの０ＵＴＰＵＴＣＯＩ）Ｅ　１
を符号語として出力した後、拡張文字列ωに＝ｂａを２
ａで表わし、参照番号５を付けて辞書に登録する。そし
て文字ａが新たな語頭文字列ωとなる。 ４番目の入力文字すについては拡張文字列ωに＝ａｂは
１ｂの符号語４として既に辞書に登録されているので、
文字列ωＫを新たな語頭文字列ωとし、５番目の文字Ｃ
を入力して拡張文字列ωに＝４　ｃ＝ａ　ｂ　ｃを作る
。この拡張文字列ωに＝ａｂｃは辞書に登録されていな
いことから、文字列ａ　ｂ＝１　ｂの０ＵＴＰＵＴ　Ｃ
０ＤＥ　４を符号語として出力し、拡張文字列ωに＝ａ
ｂｃを辞書に４０の形で符号語６として登録する。以下
同様に、この処理を続ける。 第８図の復号化処理は第７図の符号化の逆の操作を行う
。 第８図のＬＺＷ復号化では、符号化時と同様に予め辞書
に全文字につき一文字からなる文字列を初期値として登
録してから復号化を始める。 まずＳｌで最初の符号（参照番号）を読込み、現在のＣ
０ＤＥを０ＬＤｃｏｄｅとし、最初の符号は既に辞書に
登録された一文字の参照番号いずれかに該当することか
ら、入力符号Ｃ０ＤＨに一致する文字ｃｏｄｅ（Ｋ）を
探し出し、文字Ｋを出力する。 尚、出力した文字には後の例外処理のためＦＩＮｃｈａ
ｒにセットしておく。 次に８２に進んで次の符号を読込んでＣ０ＤＥにＩＮｃ
ｏｄｅとしてセットする。Ｓ３で新たな符号があるか否
か、即ち符号入力の終了の有無をチエツクしてＳ４に進
み、Ｓ３で入力された符号Ｃ０ＤＥが辞書に定義（登録
）されているか否かチエツクする。 通常、入力した符号語は前回までの処理で辞書に登録さ
れているため、Ｓ５に進んで符号Ｃ０ＤＨに対応する文
字列ｃｏｄｅ　（ωＫ）を辞書から読出し、Ｓ６で文字
Ｋを一時的にスタックし、参照番号Ｃ０ＤＥ（ω）を新
な符号Ｃ０ＤＥとして再度Ｓ５に戻り、このＳ５．Ｓ６
の手順を再帰的に参照番号ωが一文字Ｋに至るまで繰り
返し、最後に８７に進んでＳ６でスタックした文字をＬ
　Ｉ　ＦＯ（Ｌａｓｔ　Ｉｎ　ＦａｒｔＯｕｊ）形式で
ポツプアップして出力する。同時に８７において、前回
使った符号ωと今回復元した文字列の最初の１文字Ｋを
組（ωＫ）と表した文字列に、新たな参照番号を付加し
て辞書に登録する。 第１１図を参照してＬＺＷ復号化処理を具体的に説明す
ると次のようになる。 まず第１１図で最初の入力符号語（ＩＮＰＵＴ　Ｃ０Ｄ
Ｅ）は１であり、−文字ａ、ｂ、ｃについては既に参照
番号１．　２．　３として第１０図に示すように辞書に
登録されているため、辞書の参照により符号語１に一致
する参照番号の文字列ａに置き換えて出力する。 次の符号語２についても同様にして文字すに置き換えて
出力する。このとき前回処理した符号語１と今回復号し
た文字列の１番目の文字すとを組合わせた文字列ωに＝
１ｂに新たな参照番号４を付加して辞書に登録する。 ３番目の符号語４は辞書の検索により求めた文字列１ｂ
から文字列ａｂと置き換えて文字列ａｂを出力する。同
時に前回処理した符号語２と今回復号した文字列の１番
目の文字ａとの組合せた文字列ωに＝２ａ　（＝ｂａ）
に新たな参照番号５を付加して辞書に登録する。 以下同様に、この処理を繰り返す。 第１１図のＬＺＷ復号化では次の例外処理がある。 この例外処理は、第６番目の入力符号語８の復号で生ず
る。符号語８は復号時に辞書に定義されておらず、復号
できない。この場合には、前回処理した符号語５に前回
復号した文字列ｂａの最初の一文字すを加えた文字列５
ｂを求め、更に５　ｂ＝２　ａ　ｂ＝ｂ　ａ　ｂ と置き換えて出力する例外処理を行う。そして、文字列
の出力後に前回の符号語５に今回復号した文字列の１番
目の文字すを加えた文字列５ｂに参照番号８を付加して
辞書に登録する。 この例外処理は、第６図の復号化処理フローの８４、Ｓ
８の処理を通じて行われ、最終的に８７で文字列の出力
と新たな文字列に参照番号を付加した辞書への登録が８
７で行われる。 尚、第８．１１図のＬＺＷ復号化は、復号側で符号を解
読しながら辞書をリアルタイムで作り出す場合を説明し
たが、符号化の際に作られた辞書をそのまま復号化側に
コピーとして使用することで符号化しても良い。この場
合に復号化側での例外処理は不要になる。 このように第７図の処理フロー図に示す手順でＬＺＷ符
号化を行うと、１つの文字列を辞書検索するたびに、最
悪、辞書全体をサーチしなければならならず、辞書検索
に時間がかかる問題があった。 そこで従来の辞書検索方式にあっては、外部／１ツシユ
法（ｏｐｅｎ　ｈａｓｈｉｎｇ　　又は　ｃｈａｉｎｉ
ｎｇ）を用いて処理速度を上げている。 まず−膜内なハツシュ法による辞書検索にあっては、複
数の文字列からなる集合Ｓを考えたとき、集合Ｓの文字
列Ｘの格納位置を、文字列Ｘそのものから格納位置を示
すアドレスを直接計算できる仕組みになっており、高速
の辞書検索ができる。 文字列の記憶場所、即ちハツシュ表に０から田−１まで
のアドレスが付されているとすると、ハツシュ法では、
関数 ｈ：ｓ→（０，１，・・・、　ｍ−１）を一つ定めて、
集合Ｓの文字列Ｘのアドレスをｈ（ｘ）として求める。 この関数りをハツシュ関数、値ｈ　（ｘ）を文字列Ｘの
ハツシュアドレスという。 ハツシュ法は、通常、集合Ｓの大きさがアドレス数ｍに
比べてはるかに大きい場合に用いられる。 しかしながら、ハツシュ関数りをどのように選んだとし
ても、集合Ｓの相異なる文字列ｘｉ、ｘ２に対して ｈ　　（ｘｉ）＝ｈ　　（ｘ２） ハツシュアドレスが一致してしまう場合が起こり得る。 これを衝突と呼び、衝突に対する対策の一つとして外部
ハツシュ法（ｏｐｅｎ　ｈａｓｈｉｎｇ、　　またはｃ
ｈａｉｎｉｎｇ）が用いられる。 外部ハツシュ法は第１２図に示すように、索引（ディレ
クトリ）で示されるハツシュアドレスｉ毎に連結リスト
を用意し、衝突を起こしたハツシュアドレスｈ（ｘ）＝
ｉの文字列Ｘは、連結リストの先頭から順番に格納する
。同じハツシュアドレスｈ　（ｘ）をもつそれぞれの連
結リストはパケット（ｂｕｃｋｅｔ）と呼ばれる。 辞書検索に外部ハツシュ法のリスト構造を利用したＬＺ
Ｗ符号化の処理フロー図を第１３図に示す。また第１４
図は外部ハツシュ法に従った辞書メモリの構成を示した
もので、第１５図に示す符号化文字列のツリー構造を例
にとってＬＺＷ符号化の検索手順と登録手順を具体的に
示している。 まず第１４図において、辞書メモリは、ファーストメモ
リ（Ｆｉｒｓｔ　Ｍｅｍｏｒｙ）　１００、ネクストメ
モリ　（Ｎｅｘｔ　Ｍｅｍｏｓ）　２００及びネクスト
メモリ２００の拡張メモリ（Ｅｘｔｅｎｌｉｏｎ　Ｍｅ
ｍｏｒｙ）　３００で構成される。ここでファーストメ
モリ１００が第１２図に示した外部ハツシュ法の索引（
ディレクトリ）に対応し、ネクストメモリ２００が第１
２図の連結リストのｒｎｅｘｔｊに対応し、更に拡張メ
モリ３００が第１２図のｒｎａｍｅＪに対応する。 また第１５図のツリー構造は、文字に、。、　Ｋ２．。 Ｋ２゜２、・・・、に４．が既に登録され、破線で示す
に４２は新たに登録される場合を示している。このツリ
ー構造における階層は、第１３図の処理において、ｉカ
ウンタで示され、同じ階層における文字の数はｊカウン
タで表される。 従って、各文字の登録アドレスはω、とじて表わされる
。 いま第１５図の登録済みのツリー構造に含まれる文字列 「Ｋ１０・Ｋ２２．　Ｋ３２・Ｋ４２」が入力した時の
第１３図の処理フローに従った辞書検索によるＬＺＷ符
号化及び登録を説明すると次のようになる。 第１３図において、まずＳｌで次の初期化処理を行う。 ■第１番目の文字を含むように辞書を初期化する。 例えばアルファベット２６文字であれば、文字コードを
そのままハツシュアドレスとして第１４図のファースト
メモリに登録する。第１５図の場合、ツリートップにあ
る文字ＫＩＯがアドレスω、０に登録された状態を意味
する。 ■辞書への現在文字登録数ｎを前記■で登録した文字数
にセットする。アルファベット２６文字の場合には、ｎ
＝２６となる。 ■入力した最初の文字Ｋを語頭文字列ｉとする。 第１５図の場合、最初の入力文字はに、。であることか
ら語頭文字列ｉ＝１とする。尚、以下の処理フロー中で
は語頭文字列ｉをｊカウンタとして説明する。 ■辞書検索用配列を０に初期化する。即ち、ファースト
、ネクスト及び拡張のメモリの検索用配列はＩｉ＋ｓｌ
［１，Ｎｍａｘ］、ｎｅｘｔ　［１，Ｎｍａｘ］　、Ｅ
ＸＴ　　［１，Ｎｍａｘ］で表わされるので、これを０
に初期化する。 Ｓｌの初期化処理が済んだならば、Ｓ２に進んで次の文
字「Ｋ２□」を読込む。次に８３で未処理の文字がある
か否かチエツクする。全ての処理が終ればＳ１６に進ん
で符号語ｃｏｄｅ　（ω）を出力して処理を終了する。 このとき未処理文字があるので８５〜Ｓ９に示す辞書検
索ステップに進む。 辞書検索ステップは、まずＳ５でアドレスω。 にそのときの語頭文字列ｉ＝１の値をセットし、且つｊ
カウンタをｊ＝０にセットする。これによりファースト
メモリのアドレスω１．＝ω、０が生成される。 次に８６でファーストメモリ１００のアドレスω、。の
内容を読むとアドレスω１．＝ω２１が得られるので、
ｉカウンタをｉ＝２にセットする。 続いてＳ７に進み、ｉ＝０か否かチエツクし、このとき
ｉ＝２であることがらＳ８に進み、Ｓ６のファーストメ
モリ１００から得られたアドレスω２．の拡張メモリ３
００を参照して文字ｒＫ２＋Ｊを読出し、Ｓ２で得てい
る入力文字「Ｋ２２」との一致を判別する。この場合、
両者は不一致であることから８９に進み、このときのｉ
カウンタの値ｉ＝２をｊカウンタにセットしてｊ＝２と
し、またネクストメモリ２００のアドレスω２．に格納
されているアドレスω、＝ω２□のｊをｊカウンタにｉ
＝２としてセットする。このため新たなアドレスω、＝
ω２□が作り出される。 続いてＳ７に戻り、ｉ＝０をチエツクし、このときｉ＝
２であることから再びＳ８に進んでアドレスω２□の拡
張メモリ３００の登録文字「Ｋ２□」を読出して入力文
字「Ｋ２２」との一致を判別する。 このとき両者は一致することから８２に戻り、次の文字
「Ｋ３□」を読込む。以下同様にして８５〜Ｓ９の処理
の繰り返しにより、第１４図の実線の矢印で示す順番に
辞書検索が行なわれ、既に登録済みの文字ｒＫ４＋Ｊま
での検索処理が行われる。 登録文字「Ｋ４□」の検索が終了してＳ８で最後の入力
文字１に４□」で不一致が判別された場合には、Ｓ９で
ｉ＝２にセットすると共に、アドレスω４．のネクスト
メモリ２００の内容が０であることから、ｉ＝０にセッ
トする。このためＳ７に戻った時にｉ＝０が判別され、
辞書検索ステップを抜は出してＳＩＯに進み、それまで
の文字列「Ｋ、。、に２□、に３゜Ｊを示すアドレスω
３□を符号語Ｃ０ｄｅ　（ω）として出力し、ＳＬ１〜
１４の辞書登録ステップに進む。 辞書登録ステップにあっては、まずＳｌｌで現在登録文
字列ｎをｎ＝ｉ、即ちｎ＝４にセットし、更にｎを１つ
インクリメントする。そして文字「Ｋ４□」を拡張メモ
リ３００のアドレスω、＝ω４２に登録する。 次に８１２でｊ＝０か否かをチエツクし、このときｊ＝
２であることから８１４に進み、ネクストメモリ２００
のアドレスω４．に文字「Ｋ４２」を登録したアドレス
ω４□を書込む。一方、Ｓ１２でｊ＝０であれば、即ち
、ファーストメモリ１００への登録に移行した状態であ
れば、第１４図のファーストメモリ１００のアドレスω
０１．ω２□、ω３２に示すように、拡張メモリ３００
の文字登録アドレスを格納する。 この文字登録ステップにおける文字「Ｋ４２」の登録に
より、第１４図のネクストメモリ２００及び拡張メモリ
３００は、下部に破線で仕切って示すアドレスω４１．
ω４２の登録状態となり、第１５図に示すツリー構造に
新たな文字「Ｋ４２」のアドレスω４２が追加されたこ
とになる。尚、第１４図では、アドレスω４．について
は説明の都合上、検索と登録で重複して示している。 ＳＬｌ〜Ｓ１４の辞書登録ステップが終了すると、Ｓ１
５で登録した文字「Ｋ４□」を新たな語頭文字列１１即
ち、ｉカウンタの値にセットし、再びＳ２に戻って文字
ｒＫ、ｓ２Ｊをツリートップとして、その後に続く文字
列の辞書検索に移行する。

【発明が解決しようとする課題】

このように従来のＬＺＷ符号化にあっては、ソフトウェ
アにより第７図に示した処理フローを実行して符号化す
る場合、辞書検索処理に多くの時間を要するとこから、
外部ハツシュ法を利用して第１３図の処理フローにより
辞書検索の高速化を図っている。 しかしながら、外部ハツシュ法を利用した辞書検索にあ
っては、候補文字の続出、候補文字と入力文字との照合
、一致不一致の判定がシーケルシャルに行なわれるため
に、辞書検索時間が全体時間の約８０％を占め、より一
層の高速化が必要とされている。 また、候補文字の読出しに外部ハツシュ法を利用したリ
スト構造を採用しているため、現在の候補文字の格納ア
ドレスと次の候補文字の格納アドレスとの間にはあまり
関連性がなく、随時読み出すしかなく、アドレスの先だ
しが出来ず、辞書メモリを構成する素子の性能を最大限
に活かすことができなかった。 例えば、辞書メモリとしてＤＲＡＭを用いる場合、アド
レスに連続性が無いため、例えば列アドレス（Ｒｏｗ　
Ａｄｒｅｓｓ）を固定して行アドレス（（Ｃｏｔｕｍ　
ＡｄｒｅｓｓＪのみを変化させるページモード等の高速
読出が困難であった。 例えば第１４図の場合では、ネクストメモリ２００のア
ドレスω３□、ω３３にはアドレスの連続性が無いので
、第１６図に示すように列アドレスと行アドレスを個別
にその都度指定する普通のり一ドモードとなり、高速化
が図れない問題があった。 本発明は、このような従来の問題点に鑑みてなされたも
ので、外部ハツシュ法のリスト構造を利用した辞書メモ
リの高速読出を可能にして辞書検索時間を短縮できるデ
ータ圧縮装置の辞書検索方式を提供することを目的とす
る。

【課題を解決するための手段］ 第１図は本発明の原理説明図である。 まず本発明は、符号化済みデータを相異なる部分列に分
けて各部分列毎に異なる参照番号を付加して辞書に登録
しておき、入力データを該辞書中の部分列の内、最大長
一致する部分列の参照番号で指定して符号化するデータ
圧縮装置、例えばＬｚＷ符号化を行なうデータ圧縮装置
を対象とする。 このようなデータ圧縮装置の辞書検索方式として本発明
にあっては、外部ハツシュ法のリスト構造に従ったファ
ーストメモリ１００及び拡張メモリ３００を有するネク
ストメモリ２００を備え、入力データに基づく外部ハツ
シュアドレスの連結アドレスを、部分的にネクストメモ
リ２００の連続アドレスで構成した辞書メモリ２０と、
入力データに基づいてネクストメモリ２００のアドレス
を連続的に発生して入力データに一致する拡張メモリ３
００の候補データを検索する辞書検索手段１６と設けた
ことを特徴とする。 ここで辞書検索手段１６は、入力データと候補データの
一致検査、候補データの有無、次の候補データの読出し
を平行して行うパイプライン制御手段２６を備える。ま
た辞書メモリ２０のアクセスモードとして高速ページモ
ードを使用する。 【作用】 このような構成を備えた本発明によるデータ圧縮装置の
辞書検索方式によれば、ＬＺＷ符号化の辞書検索におい
て外部ハツシュ法に基づくリスト構造をもつ辞書メモリ
の索引アドレスを連続アドレスで構成することで、１つ
のハツシュアドレスが決まれば次のアドレスが予測でき
るので、候補文字の検索アクセスをより高速化し、辞書
メモリの高速読出による符号化ができ、符号化処理時間
を短縮することができる。

【実施例】

第２図の本発明の辞書検索方式を備えたデータフ圧縮装
置（符号化装置）の一実施例を示した実施例構成図であ
る。 第２図において、処理対象となる原データ１０はＤＭＡ
　（Ｄｉｒｅｃｔ　Ｍｅｍｏｒ７　Ａｃｃｅｓｓ）制御
回路１２を介して入力される。制御手段としてのＭＰＵ
Ｉ４は入力された原データ１０を、１−文字と今までの
文字列の参照番号を辞書検索回路１６の複数文字読込み
回路１８にセットした後、辞書検索回路１６を起動する
。 辞書検索回路１６は以後、辞書メモリ２０より１文字伸
ばした文字列の候補文字を読込み、一致検査回路２２で
入力文字と候補文字との一致検査（照合）を行ない、連
結検出回路２４で候補文字の有無の検出を行なう。 パイプライン制御回路２６は、一致検査回路２２による
入力文字と候補文字の照合と連結検出回路２４による候
補文字の有無の検出とに並行して辞書メモリ２０に次の
候補文字の読出しをかける。 このようにパイプライン制御回路２６でパイプライン処
理を行なうことで、候補文字の複数個ごとの探索と照合
処理が辞書メモリ２０のサイクル・タイムで実行するこ
とができる。 更に辞書検索回路１６には連続アドレス回路２８が設け
られ、連続アドレス回路２８は連続アドレスを発生し、
複数文字読込み回路１８に辞書メモリ２０の連続アドレ
スに登録されているノ１ツシュアドレス及び候補文字を
読出すようにする。 ＬＺＷ符号の符号化では、辞書メモリ２０中の最大長一
致する文字列を求める。従って、入力文字を付加して文
字列を逐次−文字ずつ伸ばしていき、候補文字がなくな
ったところで最大一致長の文字列であることが分かる。 このとき、最大一致長文字列まではアドレスωを使用し
た参照番号で表わされており、その参照番号ωを入出力
ボート３０から外部に圧縮された符号語ｃｏｄｅ　（ω
）として出力する。 第３図は第２図に示した本発明の辞書検索回路１６の詳
細な構成を辞書メモリ２０と共に示した実施例構成図で
ある。 第３図において、アドレスレジスタ１８−１゜レジスタ
１８−２及びレジスタ１８−３が第２図の複数文字読込
み回路１８に対応し、レジスタ２２−１．比較器２２−
２が第２図の一致検査回路２２に対応し、ＮＯＲ回路２
４−１が第２図の連結検出回路２４に対応し、更にカウ
ンタ２８−１が第２図の連続アドレス回路２８に対応す
る。 次に第３図の実施例による辞書検索を、第４図の検索手
順と登録手順の説明図及び第５図の辞書メモリ２０の登
録状態を示すツリー構造説明図をを参照して説明する。 尚、以下の説明でメモリアドレスωは、上位アドレス１
１下位アドレスｊによりω１．として表されるものとす
る。 いま原データ１０として第５図のツリー構造に含まれる
文字列 「Ｋ、。、に２゜、　　Ｋ３２．　Ｋ４□」が入力した
とする。 まずＭＰＵ１４は最初に入力した文字列の１番目の文字
に１ｏの１文字分の参照番号ω１ｏを上位アドレスを指
定するアドレスレジスタ１８−１にセットすると共に、
入力した２番目の文字に２゜をレジスタ１８−２にセッ
トする。 次にパイプライン制御回路２６に辞書検索回路１６の起
動を指令する。パイプライン制御回路２６は、まず連続
アドレスを発生するカウンタ２８−１を０にセットして
から辞書メモリ２０に続出をかける。カウンタ２８−１
の内容は辞書メモリ２０のアドレスの最下位２ビツト（
Ｌ　Ｓ　Ｂ）を指定する。従って、アドレスレジスタ１
８−１の内容ω１．−ω１ｏによるが辞書メモリ２０の
上位アドレスの指定と、カウンタ２８−１の内容ｊ＝０
による辞書メモリ２０の下位アドレスの指定でなるアド
レス（ω＋ｏ＋０）により第４図のファーストメモリ１
００をアクセスしてω２１を読出し、アドレスレジスタ
１８−１にセットする。 次にアドレスレジスタ１８−１の内容ω２．を上位アド
レス、カウンタ２８−１の内容を下位アドレスとしたア
ドレス（ω２１十〇）により辞書メモリ２０のネクスト
メモリ２００及び拡張メモリ３００をアクセスし、第１
番目の候補文字に２１及び第２番目の候補文字に２２の
連結アドレスω２□を読出す。読出した第１番目の候補
文字に２＋はレジスタ１８−２にセットし、第２番目の
候補文字に２２の連結アドレスω２□はレジスタ１８−
３にセットする。そして、レジスタ２２−１にセットさ
れている入力文字に２□とレジスタ１８−２にセットさ
れた第１番目の候補文字に２１を比較器２２−２で比較
して一致、不一致の判定を行なう。 両者は一致しないことから、不一致の判定が出され、次
の候補文字に２□を読出すが、このときカウンタ２８−
１の値を１つインクリメントして辞書メモリ２０の下位
アドレスのみを変えたネクストメモリ２００のアドレス
（ω２１＋１）を発生し、ネクストメモリ２００のアク
セスで次の候補文字に２２をレジスタ１８−２に読出す
。このとき上位アドレスを指定しているアドレスレジス
タ１８１の内容ω２□はそのままである。 以下同様に、この動作を繰りの返すが、カウンタ２８−
１を使用して無闇に連続アドレスを発生させることは、
辞書メモリ２０を大きくするので、この実施例にあって
は、４回の連続アドレスを発生させることを考えている
。例えば文字コードが８ビツトの場合、９ビツトを越え
るアドレスは意味がないからである。 従って、検索の４回に１回はネクストメモリ２００の連
続アドレスではなく、ファーストメモリ１００のアクセ
スで得られた連結アドレスω１１を使用する。即ち、上
位アドレスを固定したままカンウタ２８−１で連続する
下位アドレス「００゜０１．１０．ＩＩＪを４回発生す
ると、次の連続アドレス「００」への切替えと同時に、
レジスタ１８−３に４回目のアクセスでレジスタス１８
−３で格納されているファーストメモリ１００の連結ア
ドレスをアドレスレジスタ１８−１にセットする。 例えば第４図のネクストメモリ２００の上位アドレスω
９．を例にとると、カウンタ２８−１による下位アドレ
スのインクリメントで、 ω３１十〇（＝ω３．） ω３１＋１　（＝ω３□） ω３１＋２（＝ω３３） ω３１＋３（＝ω３４） が連続アドレスとして発生され、５回目はネクストメモ
リ２００に格納された次の連続アドレスへの連結アドレ
スω３．を続出して上位アドレスとして再び連続アドレ
スの発生を最初から繰り返す。 このような辞書検索により比較器２２−２で入力文字と
候補文字の照合が一致したときは、同時にＮＯＲ回路２
４−１でレジスタ１８−３の内容（ネクストメモリ２０
０の連結アドレス）がオル０であるか否かを検査し、オ
ールＯとなるまで辞書検索を繰り返す。もしレジスタ１
８−３がオール０であれば、検索すべき候補文字がなく
なったことが検出される。この場合には、ＭＰＵ１４及
びパイプライン制御回路２６は、辞書検索回路１６の検
索処理を終了させ、それまでの辞書検索により最後に一
致した候補文字のアドレスを符号語ｃｏｄｅ　（ω）と
して出力する。 第４図の場合、入力文字ｒＫ４＋ｊでネクストメモリ２
００の内容がオール０となることから、この段階で辞書
検索を終了し、最後に一致した候補文字ｒＫ４＋Ｊのア
ドレス（ω４１＋０）を符号語Ｃ０ｄｅ（ω）として出
力する。 続いてＭＰＵ１４は、最後に残った入力文字「Ｋ４□」
につきアドレス（ω４゜＋１）の拡張メモリ３００への
登録と、ネクストメモリ２００のアドレス（ω４１＋０
）への連結アドレスω４□の登録を行った後、入力文字
ｒＫ４２Ｊを語頭文字列ｉとして新たな辞書検索に移行
する。 このように本発明では、連続的にアドレスを発生して候
補文字及び連結アドレスを検索できるので、辞書メモリ
２０として第６図に示すような列アドレスを固定した状
態で行アドレスをのみを変化させる連続アドレスによる
高速ページモードが使用でき、候補文字及びその連結ア
ドレスが高速で読出せるので、辞書探索の高速実行が実
現できる。

【発明の効果】

以上説明したように本発明によれば、ＬＺＷ符号化の辞
書探索において外部ハツシュ法を利用した連結リストを
連続アドレスで構成したため、１つのアドレスが決まれ
ばアドレスの予測による先だしができ、辞書メモリとし
て例えばＤＲＡＭを使用した際の高速ページモードの実
現によりメモリ素子の性能をフルに発揮して辞書検索の
高速化を図ることができる。

【図面の簡単な説明】

第１図は本発明の原理説明図； 第２図は本発明の実施例構成図； 第３図は本発明の辞書検索回路の詳細を示た実施例構成
説明図； 第４図は本発明のＬＺＷ符号の検索手順と登録手順の説
明図； 第５図は本発明の辞書登録内容を示すツリー構造図；第
６図は本発明の高速ページモードを使用した場合のＤＲ
ＡＭリードモードのタイミングチャート； 第７図は従来のＬＺＷ符号化処理フロー図；第８図は従
来のＬＺＷ復号化処理フロー図；第９図はＬＺＷ符号化
説明図； 第１０図は辞書構成例の説明図； 第１１図はＬＺＷ符号化説明図； 第１２図は外部ハツシュ法のリスト構造説明図；第１３
図は外部ハツシュ法を利用した従来のＬＺＷ符号化処理
フロー図； 第１４図は第１３図のＬＺＷ符号の検索手順と登録手順
の説明図； 第１５図は第１４図の辞書登録内容を示たツリー構造図
； 第１６図は高速ページモードが使用出来ないＤＲＡＭリ
ードモードのタイミングチャートである。 図中、 １０：原データ １２　：　ＤＭＡ制御回路 １４：ＭＰＵ １６：辞書検索手段（辞書検索回路） １８：複数文字読込み回路 １８−１：アドレスレバスタ １８−２．１８−３：レジスタ ２０：辞書メモリ ２２ニ一致検査回路 ２２−１　：レジスタ ２２−２：比較器 ２４：連結検出回路 ２４−１：ＮＯＲ回路 ２６：パイプライン制御回路 ２８：連続アドレス回路 ２８−１　：カウンタ ３０：入出力回路 １００・ファーストメモリ ２００ネクストメモリ ３００；拡張メモリ

Claims (3)

【特許請求の範囲】
1. （１）符号化済みデータを相異なる部分列に分けて各部
   分列毎に異なる参照番号を付加して辞書に登録しておき
   、入力データを該辞書中の部分列の内、最大長一致する
   部分列の参照番号で指定して符号化するデータ圧縮装置
   に於いて、 外部ハッシュ法のリスト構造に従ったファーストメモリ
   （（１００）及び拡張メモリ（３００）を有するネクス
   トメモリ（２００）を備え、入力データに基づく外部ハ
   ッシュアドレスの連結アドレスを、部分的に前記ネクス
   トメモリ（２００）の連続アドレスで構成した辞書メモ
   リ（２０）と； 前記入力データに基づいて前記ネクストメモリ（２００
   ）のアドレスを連続的に発生して入力データに一致する
   前記拡張メモリ（３００）の候補データを検索する辞書
   検索手段（１６）と； を備えたことを特徴とするデータ圧縮装置の辞書検索方
   式。
2. （２）請求項１記載のデータ圧縮装置の辞書検索方式に
   於いて、 前記辞書検索手段（１６）は、入力データと候補データ
   の一致検査、候補データの有無、次の候補データの読出
   しを平行して行うパイプライン制御手段（２６）を備え
   たことを特徴とするデータ圧縮装置の辞書検索方式。
3. （３）請求項１記載のデータ圧縮装置の辞書検索方式に
   於いて、 前記辞書メモリ（２０）のアクセスモードとして高速ペ
   ージモードを使用することを特徴とするデータ圧縮装置
   の辞書検索方式。