JP3038234B2

JP3038234B2 - データ圧縮装置の辞書検索方式

Info

Publication number: JP3038234B2
Application number: JP2251499A
Authority: JP
Inventors: 佳之岡田; 広隆千葉; 茂吉田; 泰彦中野
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1990-09-20
Filing date: 1990-09-20
Publication date: 2000-05-08
Anticipated expiration: 2015-05-08
Also published as: JPH04129429A

Description

【発明の詳細な説明】

【概要】

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

【産業上の利用分野】

本発明は、ユバーサル符号化の一種である増分分解型
の改良としてのLZW符号化によるデ−タ圧縮装置の辞書
検索方式に関する。近年、文字コ−ド、ベクトル情報、画像など様々な種
類のデ−タがコンピュ−タで扱われるようになってお
り、扱われるデ−タ量も急速に増加してきている。大量
のデ−タを扱うときは、デ−タの中の冗長な部分を省い
てデ−タ量を圧縮することで、記憶容量を減らしたり、
速く伝送したりできるようになる。このような様々なデ−タを１つの方式でデ−タ圧縮で
きる方法としてユニバ−サル符号化が提案されている。ここで、本発明の分野は、文字コ−ドの圧縮に限ら
ず、様々なデ−タに適用できるが、以下では、情報理論
で用いられている呼称を踏襲し、デ−タの１ワード単位
を文字と呼び、デ−タが複数ワードツながったものを文
字列と呼ぶことにする。ユニバ−サル符号の代表的な方法として、ジブーレン
ペル（Ziv−Lempel）符号がある（詳しくは、例えば、
宗像「Ziv−Lempelのデ−タ圧縮法」、情報処理、Vol.2
6,No.1,1985年を参照のこと）。ジフーレンペル符号では、ユニバ−サル型増分分解型（Incremental parsing）の２つのアルゴリズムが提案されている。更に、ユニバ−サル型アルゴリズムの改良として、LZ
SS符号がある（T.C.Bell,“Better OPM/L Text Compres
sion",IEEE Trans.on Commun.,Vol.COM−34,No.12,DEC.
1986参照）。また、増分分解型アルゴリズムの改良としては、LZW
（Lempel−Ziv−Welch）符号がある（T.A.Welch,“A Te
chnique for High−Performance Data Compression",Co
mputer,June 1984参照）。これらの符号の内、高速処理ができることと、アルゴ
リズムの簡単さからLZW符号が記憶装置のファイル圧縮
などで使われるようになっている。

【従来の技術】従来のLZW符号による符号化処理フローを第７図に示
し、復号化処理フローを第８図に示す。まずLZW符号化処理は、書き替え可能な辞書を持ち、
入力文字列の中を相異なる文字列（部分列）に分け、こ
の文字列を出現した順に参照番号を付けて辞書に登録す
ると共に、現在入力している文字列を、辞書に登録して
ある最長一致文字列の参照番号で表して符号化するもの
である。第９図にLZW符号化の説明図を示すと共に第10図にLZW
復号化の説明図を示し、更に第11図に復号化時に作成さ
れる辞書構成例を示す。尚、第9,10,11図では説明を簡単にするため、abcの３
文字の組合せからなるデ−タを圧縮、復元する場合の例
を取り上げている。第７図のLZW符号化処理では、まずステップS1（以下
「ステップ」は省略）で予め辞書に全文字につき一文字
からなる文字列を初期値として登録してから符号化を始
める。 S1の符号化は入力した最初の文字Ｋにより辞書を検索
して参照番号ωを求め、これを語頭文字列とする。次にS2で入力データの次の文字Ｋを読込み、S3で文字
入力が終了したか否かチェックした後、S4に進んでS1で
求めた語頭文字列ωにS2で読込んだ文字Ｋを加えた拡張
文字列（ωＫ）が辞書にあるか否か探す。 S4で文字列（ωＫ）が辞書になければ、S6に進んでS1
で求めた文字Ｋの参照番号ωを符号語code（ω）として
出力し、また文字列（ωＫ）に新たな参照番号を付加し
て辞書に登録し、更にS2の入力文字Ｋを参照番号ωに置
き換えると共に辞書アドレスｎをインクリメントしてS2
に戻って次の文字Ｋを読み込む。一方、S4で文字列（ωＫ）が辞書にあればS5で文字列
（ωＫ）を参照番号ωに置き換え、再びS2に戻ってS4で
文字列（ωＫ）が辞書から探せなくなるまで最大一致長
の検索を続ける。第9,10図を参照してLZW符号化を具体的に説明すると
次のようになる。まず第９図の入力データinputは左から右へと読む。
最初の文字ａを入力した時、辞書には文字ａの他に一致
する文字列がないので、OUTPUT CODE 1（参照番号ω）
を符号語して出力する。そして文字ａを語頭文字列ωと
する。次に２番目の文字ｂを入力したとすると、この入力文
字を語頭文字列ωに加えた拡張文字列ωＫ＝abは辞書に
ないことから、文字ｂのOUTPUT CODE 2を符号語として
出力する。そして、拡張文字列ωＫ＝abに参照番号４を
付けて辞書に登録する。実際の辞書登録は第10図の右側
に示すように文字列1bとして登録される。そして文字ｂ
が語頭文字列ωとなる。続いて３番目の文字ａを入力したとすると、文字ｂに
語頭文字列ωを加えた拡張文字列ωＫ＝ba＝2aは辞書に
ないことから、文字ａのOUTPUT CODE 1を符号語として
出力した後、拡張文字列ωＫ＝baを2aで表わし、参照番
号５を付けて辞書に登録する。そして文字ａが新たな語
頭文字列ωとなる。４番目の入力文字ｂについては拡張文字列ωＫ＝abは
1bの符号語４として既に辞書に登録されているので、文
字列ωＫを新たな語頭文字列ωとし、５番目の文字ｃを
入力して拡張文字列ωＫ＝4c＝abcを作る。この拡張文
字列ωＫ＝abcは辞書に登録されていないことから、文
字列ab＝1bのOUTPUT CODE 4を符号語として出力し、拡
張文字列ωＫ＝abcを辞書に4cの形で符号語６として登
録する。以下同様に、この処理を続ける。第８図の復号化処理は第７図の符号化の逆の操作を行
う。第８図のLZW復号化では、符号化時と同様に予め辞書
に全文字につき一文字からなる文字列を初期値として登
録してから復号化を始める。まずS1で最初の符号（参照番号）を読込み、現在のCO
DEをOLDcodeとし、最初の符号は既に辞書に登録された
一文字の参照番号いずれかに該当することから、入力符
号CODEに一致する文字code（Ｋ）を探し出し、文字Ｋを
出力する。尚、出力した文字Ｋは後の例外処理のためFINcharに
セットしておく。次にS2に進んで次の符号を読込んでCODEにINcodeとし
てセットする。S3で新たな符号があるか否か、即ち符号
入力の終了の有無をチェックしてS4に進み、S3で入力さ
れた符号CODEが辞書に定義（登録）されているか否かチ
ェックする。通常、入力した符号語は前回までの処理で
辞書に登録されているため、S5に進んで符号CODEに対応
する文字列code（ωＫ）を辞書から読出し、S6で文字Ｋ
を一時的にスタックし、参照番号CODE（ω）を新な符号
CODEとして再度S5に戻り、このS5,S6の手順を再帰的に
参照番号ωが一文字Ｋに至るまで繰り返し、最後にS7に
進んでS6でスタックした文字をLIFO（Last In Fast Ou
t）形式でポップアップして出力する。同時にS7におい
て、前回使った符号ωと今回復元した文字列の最初の１
文字Ｋを組（ωＫ）と表した文字列に、新たな参照番号
を付加して辞書に登録する。第11図を参照してLZW復号化処理を具体的に説明する
と次のようになる。まず第11図で最初の入力符号語（INPUT CODE）は１で
あり、一文字a,b,cについては既に参照番号1,2,3として
第10図に示すように辞書に登録されているため、辞書の
参照により符号語１に一致する参照番号の文字列ａに置
き換えて出力する。次の符号語２についても同様にして文字ｂに置き換え
て出力する。このとき前回処理した符号語１と今回復号
した文字列の１番目の文字ｂとを組合わせた文字列ωＫ
＝1bに新たな参照番号４を付加して辞書に登録する。３番目の符号語４は辞書の検索により求めた文字列1b
から文字列abと置き換えて文字列abを出力する。同時に
前回処理した符号語２と今回復号した文字列の１番目の
文字ａとの組合せた文字列ωＫ＝2a（＝ba）に新たな参
照番号５を付加して辞書に登録する。以下同様に、この処理を繰り返す。第11図のLZW復号化では次の例外処理がある。この例外処理は、第６番目の入力符号語８の復号で生
ずる。符号語８は復号時に辞書に定義されておらず、復
号できない。この場合には、前回処理した符号語５に前
回復号した文字列baの最初の一文字ｂを加えた文字列5b
を求め、更に 5b＝2ab＝bab と置き換えて出力する例外処理を行う。そして、文字列
の出力後に前回の符号語５に今回復号した文字列の１番
目の文字ｂを加えた文字列5bに参照番号８を付加して辞
書に登録する。この例外処理は、第６図の復号化処理フローのS4,S8
の処理を通じて行われ、最終的にS7で文字列の出力と新
たな文字列に参照番号を付加した辞書への登録がS7で行
われる。尚、第8,11図のLZW復号化は、復号側で符号を解読し
ながら辞書をリアルタイムで作り出す場合を説明した
が、符号化の際に作られた辞書をそのまま復号化側にコ
ピーとして使用することで符号化しても良い。この場合
に復号化側での例外処理は不要になる。このように第７図の処理フロー図に示す手順でLZW符
号化を行うと、１つの文字列を辞書検索するたびに、最
悪、辞書全体をサーチしなければならならず、辞書検索
に時間がかかる問題があった。そこで従来の辞書検索方式にあっては、外部ハッシュ
法（open hashing又はchaining）を用いて処理速度を上
げている。まず一般的なハッシュ法による辞書検索にあっては、
複数の文字列からなる集合Ｓを考えたとき、集合Ｓの文
字列ｘの格納位置を、文字列ｘそのものから格納位置を
示すアドレスを直接計算できる仕組みになっており、高
速の辞書検索ができる。文字列の記憶場所、即ちハッシュ表に０からｍ−１ま
でのアドレスが付されているとすると、ハッシュ法で
は、関数 h:S→〔0,1,・・・,m−１〕を一つ定めて、集合Ｓの文字列ｘのアドレスをｈ（ｘ）
として求める。この関数ｈをハッシュ関数、値ｈ（ｘ）
を文字列ｘのハッシュアドレスという。ハッシュ法は、通常、集合Ｓの大きさがアドレス数ｍ
に比べてはるかに大きい場合に用いられる。しかしながら、ハッシュ関数ｈをどのように選んだと
しても、集合Ｓの相異なる文字列x1,x2に対してｈ（x1）＝ｈ（x2）ハッシュアドレスが一致してしまう場合が起こり得る。
これを衝突と呼び、衝突に対する対策の一つとして外部
ハッシュ法（open hashing,またはchaining）が用いら
れる。外部ハッシュ法は第12図に示すように、索引（ディレ
クトリ）で示されるハッシュアドレスｉ毎に連結リスト
を用意し、衝突を起こしたハッシュアドレスｈ（ｘ）＝
ｉの文字列ｘは、連結リストの先頭から順番に格納す
る。同じハッシュアドレスｈ（ｘ）をもつそれぞれの連
結リストはバケット（bucket）と呼ばれる。辞書検索に外部ハッシュ法のリスト構造を利用したLZ
W符号化の処理フロー図を第13図に示す。また第14図は
外部ハッシュ法に従った辞書メモリの構成を示したもの
で、第15図に示す符号化文字列のツリー構造を例にとっ
てLZW符号化の検索手順と登録手順を具体的に示してい
る。まず第14図において、辞書メモリは、ファーストメモ
リ（First Memory）100、ネクストメモリ（Next Memor
y）200及びネクストメモリ200の拡張メモリ（Extention
Memory）300で構成される。ここでファーストメモリ10
0が第12図に示した外部ハッシュ法の索引（ディレクト
リ）に対応し、ネクストメモリ200が第12図の連結リス
トの「next」に対応し、更に拡張メモリ300が第12図の
「name」に対応する。また第15図のツリー構造は、文字K₁₀,K₂₁,K₂₂,、・・
・,K₄₁が既に登録され、破線で示すK₄₂は新たに登録さ
れる場合を示している。このツリー構造における階層
は、第13図の処理において、ｉカウンタで示され、同じ
階層における文字の数はｊカウンタで表される。従って、各文字の登録アドレスはω_ijとして表わされ
る。いま第15図の登録済みのツリー構造に含まれる文字列「K₁₀,K₂₂,K₃₂,K₄₂」が入力した時の第13図の処理フローに従った辞書検索に
よるLZW符号化及び登録を説明すると次のようになる。第13図において、まずS1で次の初期化処理を行う。第１番目の文字を含むように辞書を初期化する。例えばアルファベット26文字であれば、文字コードを
そのままハッシュアドレスとして第14図のファーストメ
モリに登録する。第15図の場合、ツリートップにある文
字K₁₀がアドレスω₁₀に登録された状態を意味する。辞書への現在文字登録数ｎを前記で登録した文字数
にセットする。アルファベット26文字の場合には、ｎ＝
26となる。入力した最初の文字Ｋを語頭文字列ｉとする。第15図
の場合、最初の入力文字はK₁₀であることから語頭文字
列ｉ＝１とする。尚、以下の処理フロー中では語頭文字
列ｉをｉカウンタとして説明する。辞書検索用配列を０に初期化する。即ち、ファース
ト、ネクスト及び拡張のメモリの検索用配列はfirst
［1,Nmax］,next［1,Nmax］、EXT［1,Nmax］で表わされ
るので、これを０に初期化する。 S1の初期化処理が済んだならば、S2に進んで次の文字
「K₂₂」を読込む。次にS3で未処理の文字があるか否か
チェックする。全ての処理が終ればS16に進んで符号語c
ode（ω）を出力して処理を終了する。このとき未処理
文字があるのでS5〜S9に示す辞書検索ステップに進む。辞書検索ステップは、まずS5でアドレスω_ijにそのと
きの語頭文字列ｉ＝１の値をセットし、且つｊカウンタ
をｊ＝０にセットする。これによりファーストメモリの
アドレスω_ij＝ω₁₀が生成される。次にS6でファーストメモリ100のアドレスω₁₀の内容
を読むとアドレスω_ij＝ω₂₁が得られるので、ｉカウン
タをｉ＝２にセットする。続いてS7に進み、ｉ＝０か否かチェックし、このとき
ｉ＝２であることからS8に進み、S6のファーストメモリ
100から得られたアドレスω₂₁の拡張メモリ300を参照し
て文字「K₂₁」を読出し、S2で得ている入力文字「K₂₂」
との一致を判別する。この場合、両者は不一致であるこ
とからS9に進み、このときのｉカウンタの値ｉ＝２をｊ
カウンタにセットしてｊ＝２とし、またネクストメモリ
200のアドレスω₂₁に格納されているアドレスω_ij＝ω
₂₂のｉをｉカウンタにｉ＝２としてセットする。このた
め新たなアドレスω_ij＝ω₂₂が作り出される。続いてS7に戻り、ｉ＝０をチェックし、このときｉ＝
２であることから再びS8に進んでアドレスω₂₂の拡張メ
モリ300の登録文字「K₂₂」を読出して入力文字「K₂₂」
との一致を判別する。このとき両者は一致することから
S2に戻り、次の文字「K₃₂」を読込む。以下同様にしてS
5〜S9の処理の繰り返しにより、第14図の実線の矢印で
示す順番に辞書検索が行なわれ、既に登録済みの文字
「K₄₁」までの検索処理が行われる。登録文字「K₄₁」の検索が終了してS8で最後の入力文
字「K₄₂」で不一致が判別された場合には、S9でｉ＝２
にセットすると共に、アドレスω₄₁のネクストメモリ20
0の内容が０であることから、ｉ＝０にセットする。こ
のためS7に戻った時にｉ＝０が判別され、辞書検索ステ
ップを抜け出してS10に進み、それまでの文字列「K₁₀,K
₂₂,K₃₂」を示すアドレスω₃₂を符号語code（ω）として
出力し、S11〜14の辞書登録ステップに進む。辞書登録ステップにあっては、まずS11で現在登録文
字列ｎをｎ＝ｉ、即ちｎ＝４にセットし、更にｎを１つ
インクリメントする。そして文字「K₄₂」を拡張メモリ3
00のアドレスω_ij＝ω₄₂に登録する。次にS12でｊ＝０か否かをチェックし、このときｊ＝
２であることからS14に進み、ネクストメモリ200のアド
レスω₄₁に文字「K₄₂」を登録したアドレスω₄₂を書込
む。一方、S12でｊ＝０であれば、即ち、ファーストメ
モリ100への登録に移行した状態であれば、第14図のフ
ァーストメモリ100のアドレスω₁₁,ω₂₂,ω₃₂に示すよ
うに、拡張メモリ300の文字登録アドレスを格納する。この文字登録ステップにおける文字「K₄₂」の登録に
より、第14図のネクストメモリ200及び拡張メモリ300
は、下部に破線で仕切って示すアドレスω₄₁,ω₄₂の登
録状態となり、第15図に示すツリー構造に新たな文字
「K₄₂」のアドレスω₄₂が追加されたことになる。尚、
第14図では、アドレスω₄₁については説明の都合上、検
索と登録で重複して示している。 S11〜S14の辞書登録ステップが終了すると、S15で登
録した文字「K₄₂」を新たな語頭文字列ｉ、即ち、ｉカ
ウンタの値にセットし、再びS2に戻って文字「K₄₂」を
ツリートップとして、その後に続く文字列の辞書検索に
移行する。

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

このように従来のLZW符号化にあっては、ソフトウェ
アにより第７図に示した処理フローを実行して符号化す
る場合、辞書検索処理に多くの時間を要するとこから、
外部ハッシュ法を利用して第13図の処理フローにより辞
書検索の高速化を図っている。しかしながら、外部ハッシュ法を利用した辞書検索に
あっては、候補文字の読出、候補文字と入力文字との照
合、一致不一致の判定がシ−ケルシャルに行なわれるた
めに、辞書検索時間が全体時間の約80％を占め、より一
層の高速化が必要とされている。また、候補文字の読出しに外部ハッシュ法を利用した
リスト構造を採用しているため、現在の候補文字の格納
アドレスと次の候補文字の格納アドレスとの間にはあま
り関連性がなく、随時読み出すしかなく、アドレスの先
だしが出来ず、辞書メモリを構成する素子の性能を最大
限に活かすことができなかった。例えば、辞書メモリとしてDRAMを用いる場合、アドレ
スに連続性が無いため、例えば列アドレス（Row Adres
s）を固定して行アドレス（（Colum Adress）のみを変
化させるページモード等の高速読出が困難であった。例えば第14図の場合では、ネクストメモリ200のアド
レスω₃₂,ω₃₃にはアドレスの連続性が無いので、第16
図に示すように列アドレスと行アドレスを個別にその都
度指定する普通のリ−ドモ−ドとなり、高速化が図れな
い問題があった。本発明は、このような従来の問題点に鑑みてなされた
もので、外部ハッシュ法のリスト構造を利用した辞書メ
モリの高速読出を可能にして辞書検索時間を短縮できる
データ圧縮装置の辞書検索方式を提供することを目的と
する。

【課題を解決するための手段】

第１図は本発明の原理説明図である。まず本発明は、符号化済みデータを相異なる部分列に
分けて各部分列毎に異なる参照番号を付加して辞書に登
録しておき、入力デ−タを該辞書中の部分列の内、最大
長一致する部分列の参照番号で指定して符号化するデ−
タ圧縮装置、例えばLZW符号化を行なうデータ圧縮装置
を対象とする。このようなデータ圧縮装置の辞書検索方式として本発
明にあっては、外部ハッシュ法のリスト構造に従ったフ
ァーストメモリ100及び拡張メモリ300を有するネクスト
メモリ200を備え、入力データに基づく外部ハッシュア
ドレスの連結アドレスを、部分的にネクストメモリ200
の連続アドレスで構成した辞書メモリ20と、入力データ
に基づいてネクストメモリ200のアドレスを連続的に発
生して入力データに一致する拡張メモリ300の候補デー
タを検索する辞書検索手段16と設けたことを特徴とす
る。ここで辞書検索手段16は、入力データと候補データの
一致検査、候補データの有無、次の候補データの読出し
を平行して行うパイプライン制御手段26を備える。また
辞書メモリ20のアクセスモードとして高速ページモード
を使用する。

【作用】

このような構成を備えた本発明によるデータ圧縮装置
の辞書検索方式によれば、LZW符号化の辞書検索におい
て外部ハッシュ法に基づくリスト構造をもつ辞書メモリ
の索引アドレスを連続アドレスで構成することで、１つ
のハッシュアドレスが決まれば次のアドレスが予測でき
るので、候補文字の検索アクセスをより高速化し、辞書
メモリの高速読出による符号化ができ、符号化処理時間
を短縮することができる。

【実施例】

第２図の本発明の辞書検索方式を備えたデータフ圧縮
装置（符号化装置）の一実施例を示した実施例構成図で
ある。第２図において、処理対象となる原デ−タ10はDMA（D
irect Memory Access）制御回路12を介して入力され
る。制御手段としてのMPU14は入力された原データ10
を、１文字と今までの文字列の参照番号を辞書検索回路
16の複数文字読込み回路18にセットした後、辞書検索回
路16を起動する。辞書検索回路16は以後、辞書メモリ20より１文字伸ば
した文字列の候補文字を読込み、一致検査回路22で入力
文字と候補文字との一致検査（照合）を行ない、連結検
出回路24で候補文字の有無の検出を行なう。パイプライン制御回路26は、一致検査回路22による入
力文字と候補文字の照合と連結検出回路24による候補文
字の有無の検出とに並行して辞書メモリ20に次の候補文
字の読出しをかける。このようにパイプライン制御回路
26でパイプライン処理を行なうことで、候補文字の複数
個ごとの探索と照合処理が辞書メモリ20のサイクル・タ
イムで実行することができる。更に辞書検索回路16には連続アドレス回路28が設けら
れ、連続アドレス回路28は連続アドレスを発生し、複数
文字読込み回路18に辞書メモリ20の連続アドレスに登録
されているハッシュアドレス及び候補文字を読出すよう
にする。 LZW符号の符号化では、辞書メモリ20中の最大長一致
する文字列を求める。従って、入力文字を付加して文字
列を逐次一文字すつ伸ばしていき、候補文字がなくなっ
たところで最大一致長の文字列であることが分かる。こ
のとき、最大一致長文字列まではアドレスωを使用した
参照番号で表わされており、その参照番号ωを入出力ポ
−ト30から外部に圧縮された符号語code（ω）として出
力する。第３図は第２図に示した本発明の辞書検索回路16の詳
細な構成を辞書メモリ20と共に示した実施例構成図であ
る。第３図において、アドレスレジスタ18−1,レジスタ18
−２及びレジスタ18−３が第２図の複数文字読込み回路
18に対応し、レジスタ22−1,比較器22−２が第２図の一
致検査回路22に対応し、NOR回路24−１が第２図の連結
検出回路24に対応し、更にカウンタ28−１が第２図の連
続アドレス回路28に対応する。次に第３図の実施例による辞書検索を、第４図の検索
手順と登録手順の説明図及び第５図の辞書メモリ20の登
録状態を示すツリー構造説明図をを参照して説明する。
尚、以下の説明でメモリアドレスωは、上位アドレス
ｉ、下位アドレスｊによりω_ijとして表されるものとす
る。いま原データ10として第５図のツリー構造に含まれる
文字列「K₁₀,K₂₂,K₃₂,K₄₂」が入力したとする。まずMPU14は最初に入力した文字列の１番目の文字K₁₀
の１文字分の参照番号ω₁₀を上位アドレスを指定するア
ドレスレジスタ18−１にセットすると共に、入力した２
番目の文字K₂₂をレジスタ18−２にセットする。次にパイプライン制御回路26に辞書検索回路16の起動
を指令する。パイプライン制御回路26は、まず連続アド
レスを発生するカウンタ28−１を０にセットしてから辞
書メモリ20に読出をかける。カウンタ28−１の内容は辞
書メモリ20のアドレスの最下位２ビット（LSB）を指定
する。従って、アドレスレジスタ18−１の内容ω_ij＝ω
₁₀によるが辞書メモリ20の上位アドレスの指定と、カウ
ンタ28−１の内容ｊ＝０による辞書メモリ20の下位アド
レスの指定でなるアドレス（ω₁₀＋０）により第４図の
ファーストメモリ100をアクセスしてω₂₁を読出し、ア
ドレスレジスタ18−１にセットする。次にアドレスレジスタ18−１の内容ω₂₁を上位アドレ
ス、カウンタ28−１の内容を下位アドレスとしたアドレ
ス（ω₂₁＋０）により辞書メモリ20のネクストメモリ20
0及び拡張メモリ300をアクセスし、第１番目の候補文字
K₂₁及び第２番目の候補文字K₂₂の連結アドレスω₂₂を読
出す。読出した第１番目の候補文字K₂₁はレジスタ18−
２にセットし、第２番目の候補文字K₂₂の連結アドレス
ω₂₂はレジスタ18−３にセットする。そして、レジスタ
22−１にセットされている入力文字K₂₂とレジスタ18−
２にセットされた第１番目の候補文字K₂₁を比較器22−
２で比較して一致、不一致の判定を行なう。両者は一致しないことから、不一致の判定が出され、
次の候補文字K₂₂を読出すが、このときカウンタ28−１
の値を１つインクリメントして辞書メモリ20の下位アド
レスのみを変えたネクストメモリ200のアドレス（ω₂₁
＋１）を発生し、ネクストメモリ200のアクセスで次の
候補文字K₂₂をレジスタ18−２に読出す。このとき上位
アドレスを指定しているアドレスレジスタ18−１の内容
ω₂₂はそのままである。以下同様に、この動作を繰りの返すが、カウンタ28−
１を使用して無闇に連続アドレスを発生させることは、
辞書メモリ20を大きくするので、この実施例にあって
は、４回の連続アドレスを発生させることを考えてい
る。例えば文字コードが８ビットの場合、９ビットを越
えるアドレスは意味がないからである。従って、検索の４回に１回はネクストメモリ200の連
続アドレスではなく、ファーストメモリ100のアクセス
で得られた連結アドレスω_ijを使用する。即ち、上位ア
ドレスを固定したままカンウタ28−１で連続する下位ア
ドレス「00,01,10,11」を４回発生すると、次の連続ア
ドレス「00」への切替えと同時に、レジスタ18−３に４
回目のアクセスでレジスタス18−３で格納されているフ
ァーストメモリ100の連結アドレスをアドレスレジスタ1
8−１にセットする。例えば第４図のネクストメモリ200の上位アドレスω
₃₁を例にとると、カウンタ28−１による下位アドレスの
インクリメントで、 ω₃₁＋０（＝ω₃₁） ω₃₁＋１（＝ω₃₂） ω₃₁＋２（＝ω₃₃） ω₃₁＋３（＝ω₃₄）が連続アドレスとして発生され、５回目はネクストメモ
リ200に格納された次の連続アドレスへの連結アドレス
ω₃₅を読出して上位アドレスとして再び連続アドレスの
発生を最初から繰り返す。このような辞書検索により比較器22−２で入力文字と
候補文字の照合が一致したときは、同時にNOR回路24−
１でレジスタ18−３の内容（ネクストメモリ200の連結
アドレス）がオ−ル０であるか否かを検査し、オール０
となるまで辞書検索を繰り返す。もしレジスタ18−３が
オ−ル０であれば、検索すべき候補文字がなくなったこ
とが検出される。この場合には、MPU14及びパイプライ
ン制御回路26は、辞書検索回路16の検索処理を終了さ
せ、それまでの辞書検索により最後に一致した候補文字
のアドレスを符号語code（ω）として出力する。第４図の場合、入力文字「K₄₁」でネクストメモリ200
の内容がオール０となることから、この段階で辞書検索
を終了し、最後に一致した候補文字「K₄₁」のアドレス
（ω₄₁＋０）を符号語code（ω）として出力する。続いてMPU14は、最後に残った入力文字「K₄₂」につき
アドレス（ω₄₂＋１）の拡張メモリ300への登録と、ネ
クストメモリ200のアドレス（ω₄₁＋０）への連結アド
レスω₄₂の登録を行った後、入力文字「K₄₂」を語頭文
字列ｉとして新たな辞書検索に移行する。このように本発明では、連続的にアドレスを発生して
候補文字及び連結アドレスを検索できるので、辞書メモ
リ20として第６図に示すような列アドレスを固定した状
態で行アドレスをのみを変化させる連続アドレスによる
高速ページモードが使用でき、候補文字及びその連結ア
ドレスが高速で読出せるので、辞書探索の高速実行が実
現できる。

【発明の効果】

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

【図面の簡単な説明】

第１図は本発明の原理説明図；第２図は本発明の実施例構成図；第３図は本発明の辞書検索回路の詳細を示た実施例構成
説明図；第４図は本発明のLZW符号の検索手順と登録手順の説明
図；第５図は本発明の辞書登録内容を示すツリー構造図；第
６図は本発明の高速ページモードを使用した場合のDRAM
リードモードのタイミングチャート；第７図は従来のLZW符号化処理フロー図；第８図は従来のLZW復号化処理フロー図；第９図はLZW符号化説明図；第10図は辞書構成例の説明図；第11図はLZW符号化説明図；第12図は外部ハッシュ法のリスト構造説明図；第13図は外部ハッシュ法を利用した従来のLZW符号化処
理フロー図；第14図は第13図のLZW符号の検索手順と登録手順の説明
図；第15図は第14図の辞書登録内容を示たツリー構造図；第16図は高速ページモードが使用出来ないDRAMリードモ
ードのタイミングチャートである。図中、 10:原データ 12:DMA制御回路 14:MPU 16:辞書検索手段（辞書検索回路） 18:複数文字読込み回路 18−1:アドレスレバスタ 18−2,18−3:レジスタ 20:辞書メモリ 22:一致検査回路 22−1:レジスタ 22−2:比較器 24:連結検出回路 24−1:NOR回路 26:パイプライン制御回路 28:連続アドレス回路 28−1:カウンタ 30:入出力回路 100:ファーストメモリ 200:ネクストメモリ 300:拡張メモリ

───────────────────────────────────────────────────── フロントページの続き (72)発明者中野泰彦神奈川県川崎市中原区上小田中1015番地富士通株式会社内 (56)参考文献特開昭59−231683（ＪＰ，Ａ) 特開昭60−116228（ＪＰ，Ａ) 特開昭64−7230（ＪＰ，Ａ) 特開昭61−13340（ＪＰ，Ａ) 特開昭58−155589（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) H03M 7/42

Claims

(57)【特許請求の範囲】

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