JP3115066B2

JP3115066B2 - 辞書検索方法

Info

Publication number: JP3115066B2
Application number: JP03324706A
Authority: JP
Inventors: 佳之岡田; 茂吉田; 泰彦中野; 広隆千葉
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1991-12-09
Filing date: 1991-12-09
Publication date: 2000-12-04
Anticipated expiration: 2015-12-04
Also published as: JPH05158987A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はデータ圧縮における辞書
検索方法に係わり、特に既に符号化済みの文字列を相異
なる部分文字列に分け、該部分文字列を辞書に登録して
おき、入力文字列と最長に一致する部分文字列を辞書か
ら検索し、該最長一致文字列の番号を指定して符号化す
るデータ圧縮における辞書検索方法に関する。

【０００２】近年、文字コード、ベクトル情報、画像な
どの様々な種類のデータがコンピュータで扱われるよう
になっており、扱われるデータ量も急速に増加してきて
いる。大量のデータを扱う時は、データの中の冗長な部
分を省いてデータ量を圧縮することで、記憶容量を減ら
したり、速く伝送したりできるようになる。様々なデー
タを１つの方式でデータ圧縮できる方法としてユニバー
サル符号化が提案されている。

【０００３】

【従来の技術】このユニバーサル符号は、情報保存型の
データ圧縮方法であり、データ圧縮時に情報源の統計的
な性質を予め仮定しないため、種々のタイプ（文字コー
ド、オブジェクトコードなど）のデータに適用すること
ができる。文書画像では、文字の輪郭等や文字間隔に類
似性があり、又、網点画像は網点周期性、網点形状の同
一性等が類似している。この類似性の持つ冗長性をユニ
バーサル符号により削減し、有効な圧縮を行うことがで
きる。尚、以下では、情報理論で用いられている呼称を
踏襲し、データの１ワード単位を文字と呼び、データが
任意ワードつながったものを文字列と呼ぶことにする。

【０００４】ユニバーサル符号の代表的な方法として、
ジブ−レンペル(Ziv-Lempel)符号がある。例えば、宗像
「Ziv-Lempelのデータ圧縮法」、情報処理、Vol.26,No.
1,1985年参照。このZiv-Lempel符号では、ユニバーサ
ル型と、増分分解型(Incremental parsing) の2つの
アルゴリズムが提案されており、ユニバーサル型アルゴ
リズムを用いた実用的な方法として、ＬＺＳＳ符号(T.
C. Bell,"Better OMP/LText Compression", IEEE Tran
s. on Commun., Vol. COM-34, No.12, Dec.1986)があ
り、又、増分分解型アルゴリズムを用いた実用的な方法
として、ＬＺＷ（Lempel- Ziv- Welch)符号がある(T.A.
Welch, " A Technique for High-Performance Data Co
mpression" , Computer, June 1984)。これらの符号の
内、高速処理できることと、アルゴリズムの簡単さから
ＬＺＷ符号が記憶装置のファイル圧縮などで使われるよ
うになっている。

【０００５】ＬＺＷ符号化ＬＺＷ符号化においては、書き換え可能な辞書を設け、
入力文字列を相異なる文字列に分け、この文字列を出現
した順に番号を付けて辞書に登録すると共に、現在入力
している文字列を辞書に登録してある最長一致文字列の
辞書番号だけで表して符号化する。

【０００６】図８はＬＺＷ符号化説明図、図９は辞書構
成の説明図、図１０はＬＺＷ符号化処理の流れ図であ
る。尚、説明を簡単にするために、ａ，ｂ，ｃ３文字か
らなる文字列をＬＺＷ符号化してデータ圧縮するものと
する。予め、全文字につき一文字からなる文字列（ａ，
ｂ，ｃ）に登録番号を付して辞書に初期登録すると共
に、辞書の登録数Ｎを文字種数Ｍとする（Ｍ→Ｎ）。・
・ステップ１０１

【０００７】かかる状態で、最初の文字Ｋを入力し、該
文字の登録番号を参照番号ωとし、これを語頭文字列(p
refix string)とする（ステップ１０２）。ついで、入
力データの次の文字Ｋを読み込み（ステップ１０３）、
ステップ１０２で求めた語等文字列ωにステップ１０３
で読み込んだ文字Ｋを加えた文字列（ωＫ）が現在の辞
書にあるか否かを検索する（ステップ１０４）。

【０００８】文字列（ωＫ）が辞書に存在すれば、文字
列（ωＫ）をωに置き換え（ステップ１０５）、しかる
後、入力データが終了したか判断し（ステップ１０
６）、データが終了してなければステップ１０３に戻り
以降の処理を繰返し、文字列（ωＫ）が辞書から捜せな
くなるまで最大一致長文字列の検索を続ける。一方、ス
テップ１０６において、入力データが終了していれば、
参照番号ωを符号語 code（ω）として出力して（ステ
ップ１０７）、符号化処理を終了する。

【０００９】最長一致文字列の検索が続行して、ステッ
プ１０４において、文字列（ωＫ）が辞書に存在しなく
なれば、参照番号ωを符号語 code（ω）として出力
し、又、文字列（ωＫ）を辞書アドレスＮに登録し、更
にステップ１０３で読み込んだ文字Ｋを参照番号ωに置
き換えると共に、辞書アドレスＮを１インクリメントす
る（ステップ１０８）。次いで、ステップ１０６により
入力データが終了したか判断し、判断結果に応じて以降
の処理を繰り返す。

【００１０】図８及び図９を参照してＬＺＷ符号化を具
体的に説明すると、以下のようになる。すなわち、図８
の入力データを左から右に向けて１文字づつ読み込む。
最初の文字ａを読み込んだ時、辞書にはａの他に一致す
る文字列はないから、ａの登録番号「１」（参照番号ω
＝１）を符号語（code（ω））として出力する。そし
て、拡張した文字列ａｂに登録番号４を付けて辞書に登
録する。実際の登録は文字列「１ｂ」の形となる。続い
て、２番目の文字ｂが入力文字列の先頭になる。辞書に
はｂの他に一致する文字列がないので、ｂの登録番号
（参照番号）２を符号語として出力し、拡張した文字列
ｂａを実際には２ａの形で登録番号５を付けて辞書に登
録する。

【００１１】以上により、３番目の文字ａが入力文字列
の先頭になる。辞書には先頭文字ａが存在するから、該
文字の登録番号１に次の文字ｂを付した文字列「１ｂ」
が存在するか調べる。文字列「１ｂ」が存在するから、
該文字列の登録番号４に次の文字ｃを付した文字列「４
ｃ」が存在するか調べる。文字列「４ｃ」は存在しない
から、最長一致文字列「１ｂ」の登録番号「４」を符号
語として出力し、拡張した文字列「４ｃ」を登録番号６
に辞書登録し、以後同様に符号化と辞書登録を繰り返し
て全入力文字のＬＺＷ符号化処理を実行する。

【００１２】図１１はＬＺＷ復号化処理の流れ図であ
り、復号化処理では、符号化の逆の操作が行われる。す
なわち、復号化に際しては、符号化と同様に、全文字に
つき一文字からなる文字列（ａ，ｂ，ｃ）に登録番号を
付して辞書に初期登録すると共に、辞書の登録数Ｎを文
字種数Ｍとする（Ｍ→Ｎ）。・・ステップ２０１ついで、最初の符号CODEを読み込み、該符号CODEをOLDc
odeとする。又、最初の符号は既に辞書に登録された一
文字の登録番号のいずれかに該当することから、入力符
号CODE(＝登録番号)が示す文字Ｋを出力する。又、出力
した文字Ｋは後の例外処理のためにcharとして設定す
る。・・以上ステップ２０２

【００１３】しかる後、次の符号CODEを読み込んでNEWc
odeとしてセットすると共に(ステップ２０３）、符号CO
DE(＝登録番号)が辞書に定義(登録)されているか否かを
チェックする(ステップ２０４）。通常、入力した符号C
ODE(＝登録番号)は前回までの処理で辞書に登録されて
いるから、ステップ２０４において「ＮＯ」となるか
ら、次に、符号CODE(＝登録番号)が指示する辞書の登録
文字列が（ωＫ）か判断する。すなわち、符号CODEが指
示する辞書の登録文字列が（ωＫ）のように、参照番号
ωと文字Ｋの結合文字列であるか判断する（ステップ２
０５）。

【００１４】参照番号ωと文字Ｋの結合文字列であれ
ば、文字Ｋを一時的にスタックし、参照番号ωの符号語
code（ω）（実際にはcode（ω）＝ω）を新たなCODEと
し、かつ文字数Ｃを１カウントアップし（ステップ２０
６）、ステップ２０５に戻る。以後、ステップ２０５、
２０６の処理をCODEが示す登録文字列が一文字に至るま
で再帰的に繰り返す。

【００１５】ステップ２０５において、CODEが示す文字
列が一文字の場合には、すなわち、符号CODEが指示する
辞書の登録文字列が（Ｋ）の場合には、Ｋを出力し、し
かる後、スタックしたＣ個の文字列をＬＩＦＯ（Last i
n Fast Out)形式でポップアップして出力する。又、前
回の復号化において使用した符号OLDcodeに、今回復号
した文字列の先頭文字Ｋを付加した文字列（OLDcode，
Ｋ）を登録番号Ｎとして辞書に登録し、次にＮを１イン
クリメントする（Ｎ＋１→Ｎ）。更に、復号文字列の先
頭文字Ｋをcharとし、かつNEWcodeをOLDcodeとする。・
・以上ステップ２０７

【００１６】以後、符号入力が終了したか判断し（ステ
ップ２０８）、終了してなければステップ２０３に戻り
次の符号を読み込んで復号処理を繰り返す。ところで、
符号化処理においては、ある文字列の符号化と、該文字
列に次の先頭文字を付加した文字列の辞書登録とを同時
に行うため、次の符号化処理において直前に符号化した
文字列の符号語を使用できる。しかし、復号化処理にお
いては、直前に復号した文字列に、今回復号した文字列
の先頭文字列を付加した文字列を辞書登録するため、辞
書登録が符号化処理に比べて１回遅れる。このため、符
号化処理において、直前に符号化した文字列の符号語を
使用すると、復号化処理において、該符号語が登録（定
義）されていない場合を生じる。この場合がステップ２
０４においてCODEが定義されていない状態になり、「Ｙ
ＥＳ」となる。

【００１７】例えば、図１２に示すように符号化に際し
て、文字列「ａ・・・ｚ」に対してOLDcodeを出力する
と共に、文字列「ａ・・・ｚａ」をNEWcodeとして辞書
登録し、次の文字列「ａ・・・ｚａ」をNEWcodeで出力
し、文字列「ａ・・・ｚａｂ」を辞書登録する。さて、
復号側で符号語NEWcodeを読み込んだ時、該符号語は復
号側で辞書登録されていないので、復号ができない。し
かし、NEWcodeとOLDcodeを比較すると、以下の関係 NEWcodeの文字列＝OLDcodeの文字列＋OLDcodeの文字列
の先頭文字（char) がある。このため、ステップ２０４で「ＮＯ」となれ
ば、セットされているcharをスタックすると共に、OLDc
odeをCODEとみなし、かつ、OLDcodeにcharを付加した文
字列をNEWcodeとし(ステップ２０９）、以後CODEを用い
てステップ２０５以降の処理を行う。

【００１８】図１３を参照して復号化処理を具体的に説
明すると以下のようになる。最初の入力符号は「１」で
あり、一文字ａ，ｂ，ｃについては既に登録番号１、
２、３として辞書登録されているから（図９と同様）、
辞書の参照により符号「１」に一致する登録番号の文字
列ａに置き換えて出力する。次に、符号「２」について
も同様にして文字ｂに置き換えて出力する。この時、前
回処理した符号「１」と今回復号した最初の一文字ｂと
を組み合わせた「１ｂ」を新たな登録番号４に辞書登録
する。

【００１９】３番目の符号「４」は辞書の検索により、
「１ｂ」から「ａｂ」と置き換えて文字列「ａｂ」を出
力する。同時に、前回処理した符号「２」と今回復号し
た１番目の文字ａとを組み合わせた文字列「２ａ（＝ａ
ｂ）」を新たな登録番号５に辞書登録する。以下、同様
に、復号処理を繰り返す。尚、図１１のステップ２０９
の例外処理は、第６番目の入力符号「８」の復号で生じ
る。符号「８」は復号時に辞書に定義されておらず、復
号できない。この場合には、前回処理した符号「５」に
前回復号した文字列「ｂａ」の最初の一文字ｂを加えた
文字列「５ｂ」を求め、更に「２ａｂ」、「ｂａｂ」と
置き換えられて出力される。そして、前回の符号語
「５」に今回復号した文字列の文字ｂを加えた文字列
「５ｂ」に登録番号「８」を付加して辞書登録する。

【００２０】以上のように、ユニバーサル符号は、符号
化対象の性質が未知でも、それを学習しながら符号化し
てゆく圧縮法であり、既出のデータ列を辞書に登録して
行き、同じデータ列が表れた時には、その登録番号を符
号化データ（符号語）として送出するというシンプルな
ものである。しかし、図１０の流れ図に従って符号化す
ると、１つの文字列を辞書検索する際、最悪、辞書全体
をサーチしなければならず、このため、符号化処理に時
間がかかる問題があった。そこで、従来は、辞書検索に
外部ハッシュ法（open hashingまたはchaining)を用い
て処理速度を上げている(例えば、オーム社刊、情報処
理学会編、情報処理ハンドブック参照)。

【００２１】外部ハッシュ法文字列からなる集合Ｓを考えた時、集合Ｓにおける文字
列ｘの格納位置のアドレスを文字列ｘより直接計算でき
る仕組になっていると高速の検索ができる。これを実現
するのがハッシュ法である。記憶場所（ハッシュ表）に
０〜（m-1)までのアドレスが付加されているとすると、
ハッシュ法では、関数ｈ：Ｓ→［０，１，２，・・・(m-1)］を１つ定めて、Ｓの文字列ｘのアドレスをh(x)で求め
る。関数ｈをハッシュ関数、値ｈ(x)をｘのハッシュ・
アドレスといっている。ハッシュ法は、通常、文字列の
集合Ｓの大きさがアドレス数ｍに比べて遥かに大きい場
合に用いられる。そこで、ハッシュ関数ｈをどのように
選んだとしても、集合Ｓにおける相異なる文字列ｘ₁，
ｘ₂に対してｈ(x₁)＝ｈ(x₂)となる場合が起こり得る。
これを衝突と呼び、衝突に対する対策の一つとして外部
ハッシュ法が用いられる。外部ハッシュ法は、図１４に
示すように、ハッシュアドレスｉ毎に連結リスト(name
next)ＬＳＴを用意し、ｈ(x)＝ｉとなるｘはその連結リ
ストの先頭から順に格納する。尚、同じハッシュアドレ
スを有するそれぞれのリストはバケット(bucket)と呼ば
れる。

【００２２】図１５はＬＺＷ符号の辞書作成及び辞書検
索に外部ハッシュ法を採用した時のハッシュ表（辞書）
のデータ構造であり、ある文字列ｘにより指定されるハ
ッシュアドレスｉに、文字列ｘに続く文字Ｋ（イクステ
ンションextension)と、文字列ｘに続く文字Ｋ以外の文
字を格納するアドレス（nextアドレス)と、文字Ｋに更
に続く文字の格納アドレス（firstアドレス）が記憶さ
れるようになっている。尚、firstアドレスは図１４の
索引dictionaryに対応し、nextアドレスは連結リスト(n
ame next) に対応する。

【００２３】図１６は外部ハッシュ法による辞書構造説
明図で、(a)は従来のＬＺＷ符号化による辞書、(b)は外
部ハッシュ法による辞書、(c)は外部ハッシュ法を用い
た辞書の木構造図であり、それぞれ図８に示す順序で、
ａ，ｂ，ｃの３文字よりなる入力文字列が発生した場合
である。図１６(b)のアドレスｉにはfirst欄、next欄、
extension欄が対応付けされており、図１５で示した構
造でデータを記憶するようになっている。すなわち、ア
ドレスｉのextension欄にはアドレスｉを指示する文字
列ｘに連結する文字Ｋが書き込まれ、next欄には文字列
ｘに連結する文字Ｋ以外の文字を格納するアドレスが書
き込まれ、first欄には文字Ｋに更に連結する文字の格
納アドレス（firstアドレス）が記憶されるようになっ
ている。例えば、アドレス４の文字ｂに着目すると、該
アドレス４はアドレス１の文字（１文字からなる文字
列）ａのfirstアドレスにより指示され、アドレス４のe
xtension欄には文字列ａに連結する文字ｂが書き込ま
れ、next欄には文字列ａに連結する別の文字ａを格納す
るアドレス１０が書き込まれ、first欄には文字ｂに更
に続く文字ｃのアドレス６が書き込まれている。

【００２４】初期時、アドレス１、２、３のextension
欄には全１文字列ａ，ｂ，ｃが初期登録され、その他の
欄は「空（＝０）」になっており、以後、後述する外部ハ
ッシュ法による符号処理が行われ、図１６(c)に示す木
構造状に辞書(図１６(b))が作成される。尚、(c)におい
て、□で囲んだ番号はアドレスである。以上により、例
えば、アドレス１の文字ａを参照すると、該文字ａに
は、アドレス４の文字ｂがfirst方向に連結し、該文字
ｂにはfirst方向に更にアドレス６の文字ｃが連結し、
更に、前記文字ａにはアドレス１０の文字ａが連結し、
アドレス１０の文字ａには順次アドレス１１、１２の文
字ａが連結していることが示される。また、アドレス２
の文字ｂに着目すると、該文字ｂにはアドレス５の文字
ａがfirst方向に連結し、以後、アドレス８、９の文字
ｂ，ａが順次連結していることが示される。更に、アド
レス３の文字ｃに着目すると、該文字ｃにはアドレス７
の文字ｂがfirst方向に連結していることが示される。

【００２５】外部ハッシュ法による符号化処理図１７は外部ハッシュ法によるＬＺＷ符号化処理の流れ
図である。この符号化処理においては、外部ハッシュ法
により参照番号ｉの文字列に一文字を付加した文字列の
アドレスをハッシュアドレス（索引）として引く。連結
リストには、参照番号ｉの文字列に付加される文字を格
納するfirst,nextアドレスが格納してあり、該文字と入
力文字Ｋの一致を検査し、不一致ならば逐次連結リスト
を手繰ることによって、これまで出現した全ての一文字
付加文字列を検索することができる。もし、バケット中
に付加した文字列が存在しない場合には、最終的にリス
トの連結アドレスから０が得られ、該当する文字列が登
録されていないことを知ることができる。

【００２６】予め、全文字につき一文字からなる文字列
(a,b,c,・・・)を、辞書アドレス１〜Ｍのextension欄に初
期登録すると共に（Ｍは文字種数）、辞書の先頭アドレ
スｎを文字種数Ｍ＋１とする（Ｍ＋１→ｎ）。また、最
初の文字Ｋを入力して該文字を記憶するアドレス（該文
字の参照番号）をｉとし、これを語頭文字列(prefix st
ring)とする。更に、辞書における全アドレスのfirst欄
の内容first[1,NMAX]、next欄の内容next[1,NMAX]及び
アドレスＭ＋１〜ＮＭＡＸのextension欄の内容を全て
０に初期化する。・・ステップ３０１

【００２７】かかる状態で、次の文字Ｋを入力し（ステ
ップ３０２）、ωにｉを代入すると共に（ｉ→ω、Ｋの
直前までの文字列の参照番号をωとする）、ｊ＝０とす
る（ステップ３０３）。また、現アドレスｉの候補文字
ext(i)にfirst方向に連結する候補文字を格納するアド
レスを示すデータfirst(i)をｉとする（ステップ３０
４）。尚、現アドレスｉの候補文字ext(i)にfirst方向
に連結する文字がなければfirst(i)＝０であり、ｉ＝０
となる。

【００２８】ついで、ｉ＝０であるか判断し、換言すれ
ば、first方向に連結する候補文字が存在するかチェッ
クし(ステップ３０５）、存在しなければステップ３０
３で保存した参照番号（アドレス）ωを符号語 code
（ω）として出力する（ステップ３０６）。

【００２９】しかる後、ｉ＝ｎとすると共に、ｎを1イ
ンクリメントし（ｎ＋１→ｎ）、更にステップ３０２で
入力した文字Ｋをアドレスｉのexstension欄に書き込む
(Ｋ→ext(i))。すなわち、続き文字Ｋを辞書登録する
（ステップ３０７）。次いで、ｊ＝０であるかチェック
し（ステップ３０８）、ｊ＝０であれば、ｉ→first
(ω)とする（ステップ３０９）。これにより、Ｋの直前
に入力した文字を記憶するアドレス(＝Ｋの直前に入力
した文字迄の参照番号ωが指示するアドレス)のfirst欄
にｉ（今回の文字Ｋを格納するアドレス）が書き込まれ
ることになる。

【００３０】以後、ステップ３０２で入力した文字Ｋの
アドレスをｉとし（ステップ３１０）、データが終了し
たかチェックし（ステップ３１１）、終了していればｉ
→ωとした後、ωを符号語 code（ω）として出力して
（ステップ３１２）、符号化処理を終了し、データが終
了してなければステップ３０２に戻り以降の処理を繰り
返す。

【００３１】一方、ステップ３０５においてｉ≠０であ
れば、換言すればfirst方向に連結する候補文字が存在
すれば、該文字（アドレスｉのextension欄に書き込ま
れている文字ext(i)）がステップ３０２で入力した文字
Ｋと一致するか調べる（ステップ３１３）。一致してい
ればステップ３１１に飛び、データ終了していれば、ｉ
→ωとした後、ωを符号語 code（ω）として出力して
（ステップ３１２）、符号化処理を終了し、データが終
了してなければステップ３０２に戻り、更に次の文字を
入力して以降の最長一致文字列の検索処理を繰り返す。

【００３２】ステップ３１３において、first方向に連
結する候補文字がステップ３０２で入力した文字Ｋと一
致してなければ、ｊにｉを代入すると共に、アドレスｉ
のnext欄に書き込まれているアドレスデータnext(i)を
新たなｉとし（ステップ３１４）、ステップ３０５に戻
る。尚、next方向に連結する文字がなければアドレスｉ
のnext欄には０が書き込まれており、ｉ＝０となる。

【００３３】以後、ｉ≠０であればステップ３１３に移
行し同様の最長一致文字列の検索処理が繰り返えされ、
最早一致文字が存在しなくなるとステップ３０５におい
てｉ＝０となり、ステップ３０３で保存した参照番号
（アドレス）ωを符号語 code（ω）として出力し、前
述の処理を繰り返す。尚、ステップ３１４の処理の直後
のステップ３０５でｉ＝０が判断されると、ステップ３
０８においてｊ≠０となり、ｉ→next(ω)とされる（ス
テップ３１５）。これにより、Ｋの直前に入力した文字
迄の参照番号ωが指示するアドレスのnext欄にｉ（今回
の文字Ｋを格納するアドレス）が書き込まれることにな
る。

【００３４】以上要約すれば、新たな文字Ｋを入力した
時、それ迄の文字列に連結する候補文字をfirst方向に
求め、見つかればfirst方向に同様に求めて行き、見つ
からなくなればnext方向に調べ、見つかれば、再びfirs
t方向に調べて行き、以後同様な処理を繰り返して見つ
からなくなった時の参照番号ｉをωとして最長一致文字
列の符号語code(ω)を出力すると共に、アドレスｉに最
新の入力文字についてのfirst, next, extension等を登
録するものである。以上の流れ図に従って、図８の最上
段に示す文字列を符号化出力してゆくと、最下段の如く
文字列が辞書登録されて行き、図１８、図１９、図２０
の斜線で示すように辞書登録量が増加して行く。尚、図
１８(a)は初期化された後の状態である。

【００３５】図２１は従来の外部ハッシュ法による辞書
検索回路の構成図である。ＭＰＵ（マイクロ・プロセッ
サ・ユニット）１は入力文字Ｋを読み込んで一致検査部
２のレジスタ２ａに格納すると共に、辞書メモリ３より
候補文字Ｋ′とそれに繋がるfirstアドレスｆωとnext
アドレスｎωを読み出し、それぞれ読み込み部４のレジ
スタ４ａ，４ｂ，４ｃにラッチする。一致検査部２の比
較回路２ｂは入力文字Ｋとレジスタ４ａにラッチされた
候補文字Ｋ′が一致するか比較検査を行う。一致しない
場合には、コントローラ５をしてマルチプレクサ（ＭＰ
Ｘ）４ｄにより、レジスタ４ｃにラッチされているnext
アドレスｎωを選択させる。これにより、ＭＰＵ１はne
xtアドレスｎωで辞書検索を行い、新たな候補文字Ｋ′
とそれに繋がるfirstアドレスｆωとnextアドレスｎω
を読み出し、それぞれ読み込み部４のレジスタ４ａ，４
ｂ，４ｃにラッチして比較検査を行う。

【００３６】一方、比較回路２ｂにおいて、入力文字Ｋ
と候補Ｋ′が一致した場合には、コントローラ５をして
マルチプレクサ４ｄにより、レジスタ４ｂにラッチされ
ているfirstアドレスｆω選択させる。これにより、Ｍ
ＰＵ１はfirstアドレスｆωで辞書検索を行い、新たな
候補文字Ｋ′とそれに繋がるfirstアドレスｆωとnext
アドレスｎωを読み出し、それぞれ読み込み部４のレジ
スタ４ａ，４ｂ，４ｃにラッチすると共に、次の入力文
字Ｋを読み取ってレジスタ２ａに格納し、以後上記の比
較検査を行う。

【００３７】以後、上記処理が行われ、比較回路２ｂで
一致が取れず、しかも、マルチプレクサ４ｄの出力が０
となれば、換言すれば連結検出部６において検索すべき
firstアドレスｆωとnextアドレスｎωがもうないと確
認されると、最長一致文字列の検索が終了し、この時点
で辞書検索をストップし、以後次の入力文字に対して最
長一致文字列の検索を行う。

【００３８】

【発明が解決しようとする課題】以上のように、外部ハ
ッシュ法によるＬＺＷ符号化処理においては、ある文字
列の末尾に連結する候補文字Ｋ′のアドレスが指定さ
れ、該アドレスに候補文字Ｋ′とfirstアドレスとnext
アドレスが格納されているため、従来の外部ハッシュ法
によらないＬＺＷ符号化に比べて辞書検索を高速に行え
る利点がある。しかし、上記外部ハッシュ法による辞書
検索では、１度の辞書アクセスに対して１つの候補文字
Ｋ′と１組のfirstアドレスとnextアドレスしか読み出
すことができないため、候補文字が多い場合検索一致に
時間が掛かる問題がある。

【００３９】以上から本発明の目的は、外部ハッシュ法
による辞書検索を高速に行える辞書検索方法を提供する
ことである。本発明の別の目的は、外部ハッシュ法によ
るＬＺＷ符号化の辞書検索において、一度の辞書検索に
より複数の候補文字を読み出し、複数の候補文字と１つ
の入力文字とを一度に照合して辞書検索を高速に行える
辞書検索方法を提供することである。

【００４０】本発明の更に別の目的は、一度の辞書検索
により複数の候補文字と共に、複数のアドレスを読み出
し、複数の候補文字と１つの入力文字との比較照合結果
（第１候補と一致、第２候補と一致、いずれの候補とも
一致せず等）に基づいて次に参照すべき複数の候補文字
を直ちに前記所定アドレスから読み出して比較照合して
辞書検索を高速に行える辞書検索方法を提供することで
ある。

【００４１】

【課題を解決するための手段】図１は本発明の原理説明
図である。１１は検索済文字列に連結する複数の候補文
字が検索可能となるように複数のデータ要素を前記検索
済文字列が指定するアドレスに格納して符号化済みの部
分文字列を記憶する辞書メモリ、１２は入力文字を読み
込んだり、辞書メモリより候補文字、アドレス等を読み
出したり、新規文字列を辞書メモリに登録するＭＰＵ
（プロセッサ）、１３は辞書メモリより同時に読み出し
た複数のデータを記憶するレジスタ部、１４は１つの入
力文字と複数の候補文字との一致照合を行う比較照合
部、１５は比較結果に基づいて次の複数の候補文字のア
ドレスを選択するアドレス選択部（マルチプレクサＭＰ
Ｘ）である。前記複数のデータ要素は、例えば、 (1) 検索済文字列に連結する第１文字(ext₁)と、(2) 第
１文字迄の文字列の番号（ω₁）と、(3) 前記検索済文
字列に連結する文字であって第１文字とは別の第２文字
（ext ₂)と、 (4) 第２文字までの文字列の番号（ω₂）
と、(5) 前記検索済文字列に連結する第１、第２文字と
は別の第３文字の格納アドレス(next₂)と、(6) 第１文
字に連結する第４文字の格納アドレス(first₁)と、(7)
第２文字に連結する第５文字の格納アドレス(first₂)
と、(8) 第１、第２文字のうち幾つ記憶されているかを
示すフラグ(flag)を有している。

【００４２】

【作用】検索済文字列に連結する複数の候補文字が検索
可能となるように複数のデータ要素を前記検索済文字列
が指定する辞書メモリ１１のアドレスに記憶して辞書を
作成し、最長一致文字列の検索に際して、ＭＰＵ１２は
検索済文字列の次の１つの入力文字を読み込むと共に、
該検索済文字列に連結する複数の候補文字及び次の候補
文字の位置を指定するアドレスデータを含むデータ要素
を辞書メモリ１１より一括して読み出してレジスタ部１
３に格納する。比較照合部１４は、複数個の候補文字と
１つの入力文字とを比較して一致照合を行い、一致する
候補文字が存在する場合には、アドレスデータに基づい
て次の複数の候補文字を含むデータ要素を辞書メモリか
ら読み出してレジスタ部１３に格納し、以後次の入力文
字と次の複数の候補文字とを比較して最長一致検索処理
を続行する。このように、一度の辞書検索により複数の
候補文字を読み出し、複数の候補文字と１つの入力文字
とを一度に照合して辞書検索を行うようにしたから、辞
書検索を高速に行うことができる。又、一度の辞書検索
により複数の候補文字と共に、複数のアドレスを読み出
し、複数の候補文字と１つの入力文字との比較照合結果
（第１候補と一致、第２候補と一致、いずれの候補とも
一致せず等）に基づいて次に参照すべき複数の候補文字
を直ちに前記所定アドレスから読み出して比較照合して
辞書検索を高速に行うことができる。

【００４３】更に、前記データ要素は、検索済文字列に
連結する第１文字(ext₁)と、前記検索文字に連結する文
字であって第１文字とは別の第２文字（ext₂)と、前記
検索文字列に連結する第１、第２文字とは別の第３文字
の格納アドレス(next₂)と、第１文字に連結する第４文
字の格納アドレス(first₁)と、第２文字に連結する第５
文字の格納アドレス(first₂)と、第１、第２文字のうち
幾つ記憶されているかを示すフラグ(flag)を少なくとも
有し、(1)１つの入力文字と複数の候補文字である前記
第１、第２文字の一致照合に際して、入力文字と第１、
第２文字が共に異なる場合にはアドレス（next₂)に基づ
き次のデータ要素を読み出して該データ要素が指示する
複数の候補文字と入力文字との一致照合を行い、(2)入
力文字と第１文字が一致する場合には、アドレス（firs
t₁)に基づいて次の入力文字に対するデータ要素を読み
出し、該データ要素が指示する複数の候補文字と次の入
力文字との一致照合を行い、(3)入力文字と第２文字が
一致する場合には、アドレス(first₂)に基づいて次の入
力文字に対するデータ要素を読み出し、該データ要素が
指示する複数の候補文字と次の入力文字との一致照合を
行って最長一致検索処理を続行する。このようにすれ
ば、一度の辞書検索により複数の候補文字と共に、複数
のアドレスを読み出し、複数の候補文字と１つの入力文
字との比較照合結果（第１候補と一致、第２候補と一
致、いずれの候補とも一致せず等）に基づいて次に参照
すべき複数の候補文字を直ちに前記所定アドレスから読
み出して比較照合を連続的に行え、辞書検索を高速に行
うことができる。

【００４４】

【実施例】図２は本発明に係わる辞書メモリの１つのア
ドレスに格納されるデータの構造説明図である。ある文
字列ｘにより指定されるアドレスｉ（＝ω₁）には、 (1) 文字列ｘの最終文字に連結する第１文字(ext₁)と、
(2) 第１文字迄の文字列の番号（ω₁）と、(3) 前記最
終文字に連結する文字であって第１文字とは別の第２文
字（ext₂)と、 (4) 第２文字までの文字列の番号
（ω₂）と、(5) 前記最終文字に連結する第１、第２文
字とは別の第３文字の格納アドレス(next₂)と、(6) 第
１文字に連結する第４文字の格納アドレス(first₁)と、
(7) 第２文字に連結する第５文字の格納アドレス(first
₂)と、(8) 第１、第２文字のうち幾つ記憶されているか
を示すフラグ(flag)が記憶されて、辞書が作成される。

【００４５】図３は本発明による辞書メモリの内容説明
図であり、(a)は符号化説明図、(b)は本発明の辞書であ
り、辞書メモリの各アドレスにはにはflag欄、first
₁欄、first₂欄、next₂欄、ext₁欄、ext₂欄、ω₁欄、ω₂
欄が設けられている。図３(a)の上段に示す順序でａ，
ｂ，ｃの３文字よりなる入力文字列が発生すると、後述
する符号化処理により符号語が中段に示すように出力さ
れ、又、下段に示すように文字列が辞書登録される。こ
の辞書登録において、文字列は図２のデータ構造で辞書
メモリの各アドレスに登録され、その内容は図３(b)に
示すようになり、図２の表記法により表現すると図３
(c)に示す木構造状になる。

【００４６】例えば、アドレス１の第１文字ａ（ext₁)
を参照すると、該第１文字ａはfirst ₁方向にアドレス４
（first₁アドレス）のext₁欄、ext₂欄に格納された文字
等に連結し、該第１文字ａまでの文字列（１文字列ａ）
の参照番号（＝１）がω₁欄に格納されていることが示
される。

【００４７】又、アドレス１のfirst₁欄で指示された第
４アドレスのext₁欄には、アドレス１のext₁欄の文字ａ
（１文字列ａの最終文字）に連結する第１文字ｂが書き
込まれ、第４アドレスのext₂欄には、アドレス１のext₁
欄の文字ａに連結する第２文字ａが書き込まれ、第１文
字ｂにはfirst₁方向にアドレス６（first₁アドレス）の
ext₁欄に格納された文字が連結し、第２文字ａにはfirs
t₂方向にアドレス１１（first₂アドレス）のext₁欄に格
納された文字が連結し、第１文字ｂまでの文字列（２文
字列ａｂ）の参照番号（＝４）がω₁欄に格納され、第
２文字ａ迄の文字列（２文字列ａａ）の参照番号（＝１
０）がω₂欄に格納されていることが示される。尚、第
４アドレスのnext₂欄は「空(=0)」であるから、アドレス
１の文字ａ（ext₁)には第１、第２文字ｂ，ａ以外に連
結する文字列は存在しないことがわかる。

【００４８】アドレス４のfirst₁欄で指示された第６ア
ドレスのext₁欄には、アドレス４のext₁欄の文字ｂ（２
文字列ａｂの最終文字）に連結する第１文字ｃが書き込
まれ、該第１文字ｃまでの文字列（３文字列ａｂｃ）の
参照番号（＝６）がω₁欄に格納されていることが示さ
れる。尚、第６アドレスのflag欄の内容は1-0であるか
ら、アドレス４の第１文字ｂ（ext₁)には文字ｃ以外に
連結する文字は存在しないことがわかる。又、第６アド
レスのfirst₁欄は「空(=0)」であるから、３文字列ａｂｃ
に連結する文字がないことがわかる。

【００４９】アドレス４のfirst₂欄で指示された第１１
アドレスのext₁欄には、アドレス４のext₂欄の文字ａ
（２文字列ａａの最終文字）に連結する第１文字ａが書
き込まれ、該第１文字ａにはfirst₁方向にアドレス１２
（first₁アドレス）のext₁欄に格納された文字が連結
し、該第１文字ａまでの文字列（３文字列ａａａ）の参
照番号（＝１１）がω₁欄に格納されていることが示さ
れる。尚、第６アドレスのflag欄の内容は1-0であるか
ら、アドレス４の第２文字ａ（ext₂)には他に連結する
文字は存在しないことがわかる。

【００５０】アドレス１１のfirst₁欄で指示された第１
２アドレスのext₁欄には、アドレス１１のext₁欄の文字
ａ（３文字列ａａａの最終文字）に連結する第１文字ａ
が書き込まれ、第１文字ａまでの文字列（４文字列ａａ
ａａ）の参照番号（＝１２）がω₁欄に格納されている
ことが示される。尚、第１２アドレスのflag欄の内容は
1-0であるから、アドレス１１の第１文字ａ（ext₁)には
他に連結する文字は存在しないことがわかる。又、第１
２アドレスのfirst₁欄は「空(=0)」であるから、４文字列
ａａａａに連結する文字がないことがわかる。以下同様
に、アドレス２の文字ｂ，アドレス３の文字ｃに連結す
る文字列が辞書登録されている。

【００５１】図４及び図５は本発明による符号化処理
（辞書検索、辞書登録）の流れ図である。予め、辞書メ
モリのアドレス１〜Ｍのext₁欄（ext₁[1,M]）に文字コ
ード(a,b,c,・・・)を初期登録すると共に（Ｍは文字種
数）、ω₁欄（ω₁[1,M]）に文字コードに対応するアド
レス（参照番号）を初期登録し、更に、flag欄（flag
[1,M]）に1-0(ext₁欄のみに文字が登録されいることを
示す)を初期登録する。

【００５２】又、辞書の先頭アドレスｎをＭ＋１とする
（Ｍ＋１→ｎ）。更に、辞書における全アドレスの (1)first₁欄の内容first₁[1,NMAX]、(2)first₂欄の内容
first₂[1,NMAX]、(3)next₂欄の内容next₂[1,NMAX]、(4)
ext₂欄の内容ext₂[1,NMAX]、(5)ω₂欄の内容ω₂[1,NMA
X]を全て０に初期化すると共に、アドレスＭ+1〜ＮＭＡ
Ｘの(6)ext₁欄の内容ext₁[M+1,NMAX]、(7)ω₁欄の内容
ω₁[N+1,NMAX]を全て０に初期化し、又、(8)flag欄flag
[N+1,NMAX]を全て0-0(ext₁欄、ext₂欄に文字が登録され
いないことを示す)に初期化する。

【００５３】更に、検索切り替えパラメータＴ及び登録
切り替えパラメータＵをそれぞれ０にし、又、最初の入
力文字Ｋを入力して該文字の参照番号をｉとし、これを
語頭文字列(prefix string)とする。尚、Ｔ＝０は、fir
st₁欄のアドレスデータが示すアドレスから次の複数の
候補文字を読み出すこと及び符号語出力に際して第１候
補文字の参照番号を出力することを意味し、Ｔ＝１は、
first₂欄のアドレスデータが示すアドレスから次の複数
の候補文字を読み出すこと及び符号語出力に際して第１
候補文字の参照番号を出力することを意味する。また、
Ｕ＝０は、辞書登録時に文字をext₁欄に登録すること
を、Ｕ＝１は、ext₂欄に登録することを意味する。・・
以上ステップ４０１

【００５４】かかる状態で、次の入力文字Ｋを入力し
（ステップ４０２）、ついで、ｉをωに代入すると共に
（ｉ→ω、入力文字Ｋの直前の文字迄の参照番号をωと
する）、ｊ＝０とする（ステップ４０３）。ついで、Ｔ
＝０かチェックし（ステップ４０４）、Ｔ＝０であれ
ば、直前の文字を格納するアドレスｉにおけるfirst₁ア
ドレス(first₁(i))を新たなｉとし（ステップ４０
５）、Ｔ＝１であれば、直前の文字を格納するアドレス
ｉにおけるfirst₂アドレス(first₂(i))を新たにｉとす
る（ステップ４０６）。

【００５５】しかる後、ｉ＝０であるかチェックする
（ステップ４０７）。ｉ≠０であれば、第ｉアドレスの
ext₁欄の第１候補文字ext₁(i)が入力文字Ｋと一致する
かチェックし（ステップ４０８）、一致すればＴ＝０と
し（ステップ４０９）、ステップ４１０に飛ぶ。尚、一
致しない場合には後述するステップ４２１に飛び、入力
文字と第２候補文字との比較照合を行う。

【００５６】ステップ４０９でＴ＝０とした後、ｉをω
に代入する（ステップ４１０）。すなわち、入力文字と
一致する第１候補文字を記憶するアドレスｉをωとす
る。ついで、データが終了したチェックする（ステップ
４１１）。データが終了してなければステップ４０２に
戻り、次の文字Ｋを入力して以降の処理を繰り返し、最
長一致文字列の検索を行う。一方、データが終了してい
れば、Ｔ＝０かチェックし（ステップ４１２）、Ｔ＝０
であればステップ４１０で保持した第１候補文字の参照
番号ωを符号語 code（ω）として出力し（ステップ４
１３）、符号化処理を終了する。

【００５７】一方、ステップ４０８で、第ｉアドレスの
ext₁欄の第１候補文字ext₁(i)が入力文字Ｋと一致しな
ければ、第ｉアドレスのflag(i)が1-0か、すなわち、第
２候補文字が存在するかチェックする(ステップ４２
１）。第２候補文字が存在すれば、第ｉアドレスのext₂
欄の第２候補文字ext₂(i)が入力文字Ｋと一致するかチ
ェックし（ステップ４２２）、一致すればＴ＝１とし
（ステップ４２３）、ステップ４１０に飛ぶ。尚、一致
しない場合には後述するステップ４２５に飛び、入力文
字と更に別の候補文字との比較照合を行う。

【００５８】ステップ４２３でＴ＝１とした後、ｉをω
に代入する（ステップ４１０）。すなわち、入力文字と
一致する第２候補文字を記憶するアドレスｉをωとす
る。ついで、データが終了したチェックする（ステップ
４１１）。データが終了してなければステップ４０２に
戻り、次の文字Ｋを入力して以降の処理を繰り返し、最
長一致文字列の検索を行う。一方、データが終了してい
れば、Ｔ＝０かチェックし（ステップ４１２）、Ｔ＝１
であれば第２候補文字の参照番号ω₂（ω）を符号語cod
e（ω₂(ω)）として出力し（ステップ４１４）、符号化
処理を終了する。

【００５９】又、ステップ４２１で、第ｉアドレスのfl
ag(i)が1-0であれば、換言すれば、第２候補文字が存在
しなければ、入力文字と一致する候補文字は存在しない
ことになり、Ｕ＝１とし（ステップ４２４）、以後、ス
テップ４２６以降の符号語の出力及び辞書登録処理を行
う。一方、ステップ４２２で第ｉアドレスのext₂欄の第
２候補文字ext₂(i)が入力文字Ｋと一致しなければ、換
言すれば、第１、第２候補文字が入力文字と一致しなけ
れば、ｉをｊに代入すると共に、Ｕ＝０とし、かつ、第
１、第２候補文字以外の候補文字の格納アドレスnext
₂(i)を新たなｉとする（next₂(i)→ｉ）。尚、別の候補
文字（next₂方向に連結する候補文字）が存在しない場
合にはnext₂(i)＝０となり、ｉ＝０となる。・・ステッ
プ４２５

【００６０】以後、ステップ４０７に戻って、ｉ＝０か
チェックし、ｉ≠０であれば、別の候補文字が存在する
から前述のステップ４０８以降の処理を繰り返す。しか
し、別の候補文字が存在しなければ、ｉ＝０となり、以
後、ステップ４２６以降の符号語の出力及び辞書登録処
理を行う。入力文字と一致する候補文字が存在しなくな
れば、ステップ４２６でＴ＝０かチェックする。Ｔ＝０
であれば、ステップ４０３で保持した第１候補文字の参
照番号ωを符号語 code（ω）として出力し（ステップ
４２７）、Ｔ＝１であれば第２候補文字の参照番号ω₂
（ω）を符号語 code（ω₂(ω)）として出力する（ステ
ップ４２８）。

【００６１】符号語を出力後、ｉをｐに代入し、又、ｎ
をｉに代入し、更にｎを1インクリメントし（ステップ
４２９）、Ｕ＝０であるかチェックする（ステップ４３
０）。尚、flagが1-0で、第１候補文字のみが対象アド
レスに記憶されている場合のみ、Ｕ＝１となる。ステッ
プ４３０でＵ＝１であれば、入力文字Ｋを第ｐアドレス
(直前の入力文字が記憶されていたアドレス）のext₂欄
に書き込み(Ｋ→ext₂(p))、そのflag欄に1-1を書き込む
(1-1→flag(ｐ))。これにより、直前の文字に入力文字
Ｋが連結していることが登録される。・・・ステップ４
３１

【００６２】ついで、ｉを第ｐアドレス(直前の文字が
記憶されていたアドレス）のω₂欄に書き込む(ｉ→ω
₂(ｐ))。これにより、今回の入力文字Ｋ迄の文字列の参
照番号がω₂欄に登録されたことになる（ステップ４３
２）。以後、今回の文字Ｋの参照番号をｉにし、又、ｉ
をωに代入し、更に、Ｔ，Ｕを０にし（ステップ４３
３）、しかる後、データが終了したチェックする（ステ
ップ４１１）。データが終了してなければステップ４０
２に戻り、次の入力文字を読み込んで以降の処理を繰り
返す。一方、データが終了していれば、Ｔ＝０かチェッ
クし（ステップ４１２）、Ｔ＝０であるからステップ４
３３で保持した最終文字のωを符号語 code（ω）とし
て出力して（ステップ４１３）、符号化処理を終了す
る。

【００６３】一方、ステップ４３０でＵ＝０であれば、
今回の入力文字Ｋを第ｉアドレス(何も記憶されていな
い新たなアドレス）のext₁欄に書き込み(Ｋ→ext
₁(i))、そのflag欄に1-０を書き込む(1-0→flag(i))。
これにより、それ迄の文字列の最終文字（直前の入力文
字）に今回の入力文字Ｋを連結した文字列が登録され
る。・・・ステップ４４１ついで、ｊ＝０かチェックする（ステップ４４２）。
尚、ステップ４２５の処理後にｉ＝０となれば、すなわ
ち、第１、第２候補が存在し、いずれとも一致せず、ne
xt₂欄が０の場合にｊ≠０となり、それ以外はｊ＝０と
なる。

【００６４】ｊ≠０の場合には、ｉ（今回の文字の格納
アドレス）を、アドレスｊのnext₂欄に書き込み(ｉ→ne
xt₂(j)、ステップ４４３)、以後ステップ４３３以降の
処理を繰り返す。ｊ＝０であれば、すなわち、第１候補
文字が存在しない場合、又は第１又は第２候補文字と一
致し、これら一致候補文字に連結する文字が存在しない
場合には、Ｔ＝０かチェックし（ステップ４４４）、Ｔ
＝０であれば、ｉ（今回の文字の格納アドレス）を直前
の入力文字の格納アドレスωのfirst₁欄に書き込み（ｉ
→fitst₁(ω)、ステップ４４５)、Ｔ＝１であれば、ｉ
（今回の文字の格納アドレス）を直前の入力文字の格納
アドレスωのfirst₂欄に書き込み（ｉ→fitst₂(ω)、ス
テップ４４６)、以後ステップ４３３以降の処理を繰り
返す。

【００６５】以上要約すれば、一度の辞書検索により第
１、第２候補文字ext₁、ext₂と共に、複数の次に参照す
べき候補文字が格納されているアドレスnext₂,first₁,f
irst ₂を読み出しておき、(1) 入力文字が第１候補文字
と一致した場合にはfirst₁アドレスより次に参照すべき
複数の候補文字とアドレスを直ちに読み出して次の入力
文字との比較照合を行い、又、(2)入力文字が第２候補
文字と一致した場合にはfirst₂アドレスより次に参照す
べき複数の候補文字とアドレスを直ちに読み出して次の
入力文字との比較照合を行い、更に、(3)入力文字が第
１、第２候補文字の両方と一致しない場合には、next₂
アドレスより次に参照すべき複数候補文字とアドレスを
直ちに読み出して今回の入力文字との比較照合を行い、
first,next方向に一致文字が見つからなくなると、辞書
検索を終了して最長一致文字列の符号語を出力し、つい
で辞書登録し、しかる後、次の入力文字から再び辞書検
索を開始する。以上の流れ図に従って、図３(a)の最上
段に示す文字列を符号化出力してゆくと図３(b)の辞書
が作成される。

【００６６】図６は本発明に係わる辞書検索回路の第１
の実施例である。ＭＰＵ（マイクロ・プロセッサ・ユニ
ット）１２は図示しないＤＭＡ回路を介して入力文字Ｋ
を読み込んで比較照合部１４の第１レジスタ１４ａに格
納すると共に、直前の入力文字の参照番号をアドレスと
して辞書メモリ１１をアクセスし、以下のデータ (1) 所定文字に連結する第１文字(ext₁)と、(2) 第１文
字迄の文字列の番号（ω₁）と、(3) 前記所定文字に連
結する文字であって第１文字とは別の第２文字（ext₂)
と、 (4) 第２文字までの文字列の番号（ω₂）と、(5)
前記所定文字に連結する第１、第２文字とは別の第３文
字の格納アドレス(next₂)と、(6) 第１文字に連結する
第４文字の格納アドレス(first₁)と、(7) 第２文字に連
結する第５文字の格納アドレス(first₂)と、(8) 第１、
第２文字のうち幾つ記憶されているかを示すフラグ(fla
g)を取り込むと共にコントローラ１６に辞書検索の命令
を出す。これにより、コントローラ１６は、上記データ
のうち所定のデータをレジスタ部１３に一括して格納す
る。すなわち、flagデータをレジスタ１３ａに、first₁
アドレスをレジスタ１３ｂに、first₂アドレスをレジス
タ１３ｃに、next₂アドレスをレジスタ１３ｄに、第１
候補文字ext₁（＝Ｋ₁）をレジスタ１３ｅに、第２候補
文字ext₂（＝Ｋ₂）をレジスタ１３ｆに一度にラッチす
る。

【００６７】ついで、コントローラ１６の制御で、比較
照合部１４の第１、第２比較回路１４ｂ，１４ｃは、第
１、第２の候補文字Ｋ₁，Ｋ₂とレジスタ１４ａにラッチ
してある入力文字Ｋを同時に比較照合する。尚、比較回
路１４ｂ，１４ｃは、flagデータが入力されており、
(1)第１、第２候補文字の両方が共に存在するか、(2)第
１候補文字のみが存在するか、(3)第１、第２候補文字
の両方共存在しないかを認識している。

【００６８】比較照合の結果、入力文字と第１候補文字
が一致する場合には、コントローラ１６はアドレス選択
部（マルチプレクサ）１５により、レジスタ１３ｂに記
憶されているfirst₁アドレスを選択・出力させる。

【００６９】連結検出部１７はfirst₁アドレスが０であ
るかどうかを判断し、０であれば最早first₁方向に候補
文字は存在しないから、候補文字無しをＭＰＵ１２に通
知し、first₁アドレスが０でなければ、該アドレスをＭ
ＰＵ１２に通知する。ＭＰＵ１２はfirst₁アドレスが通
知されれば、次の入力文字を読み取ってレジスタ１４ａ
に格納すると共に、前記first₁アドレスを用いて辞書メ
モリ１１をアクセスし、読み取ったデータをコントロー
ラ１６の制御でレジスタ部１３に格納し、以後前述の比
較照合動作を繰り返す。

【００７０】一方、ＭＰＵ１２は連結検出部１７より、
候補文字無しを受信すれば、コントローラ１６に最長一
致文字列の検索が終了した旨を通知すると共に、符号語
を作成して図示しないＩ／Ｏポートより出力し、又、辞
書メモリ１１に辞書登録を行う。しかる後、入力データ
が終了してなければ、コントローラ１６に辞書検索を指
令して次の入力文字列に対して同様の動作を繰り返す。

【００７１】以上は、比較照合部１４による比較動作に
おいて、入力文字と第１候補文字が一致した場合である
が、入力文字と第２候補文字が一致した場合には、コン
トローラ１６はアドレス選択部１５をしてレジスタ１３
ｃに記憶されているfirst₂アドレスを選択・出力させ
る。連結検出部１７はfirst₂アドレスが０であるかどう
かを判断し、０であれば最早first₂方向に候補文字は存
在しないから、候補文字無しをＭＰＵ１２に通知し、fi
rst₂アドレスが０でなければ、該アドレスをＭＰＵ１２
に通知する。ＭＰＵ１２はfirst₂アドレスが通知されれ
ば、次の入力文字を読み取ってレジスタ１４ａに格納す
ると共に、前記first₂アドレスを用いて辞書メモリ１１
をアクセスし、読み取ったデータをコントローラ１６の
制御でレジスタ部１３に格納し、以後前述の比較照合動
作を繰り返す。

【００７２】一方、ＭＰＵ１２は連結検出部１７より、
候補文字無しを受信すれば、コントローラ１６に最長一
致文字列の検索が終了した旨を通知すると共に、符号語
を作成して図示しないＩ／Ｏポートより出力し、又、辞
書メモリ１１に辞書登録を行う。しかる後、入力データ
が終了してなければ、コントローラ１６に辞書検索を指
令して次の入力文字列に対して同様の動作を繰り返す。

【００７３】又、比較照合の結果、入力文字が第１、第
２候補文字の両方に一致しない場合には、コントローラ
１６はアドレス選択部１５をしてレジスタ１３ｄに記憶
されているnext₂アドレスを選択・出力させる。連結検
出部１７はnext₂アドレスが０であるかどうかを判断
し、０であれば最早next₂方向に候補文字は存在しない
から、候補文字無しをＭＰＵ１２に通知し、next₂アド
レスが０でなければ、該next₂アドレスをＭＰＵ１２に
通知する。ＭＰＵ１２はnext₂アドレスが通知されれ
ば、該アドレスを用いて辞書メモリ１１をアクセスし、
読み取ったデータをコントローラ１６の制御でレジスタ
部１３に格納し、以後前述の照合動作を繰り返す。

【００７４】一方、ＭＰＵ１２は連結検出部１７より、
候補文字無しを受信すれば、コントローラ１６に最長一
致文字列の検索が終了した旨を通知すると共に、符号語
を作成・出力し、又、辞書メモリ１１に辞書登録を行
う。しかる後、入力データが終了してなければ、コント
ローラ１６に辞書検索を指令して以上の動作を繰り返
す。

【００７５】図７は本発明に係わる辞書検索回路の別の
実施例で、図６と同一部分には同一符号を付している。
図６の構成と異なる点は、(1) 辞書メモリ１１に第１候
補文字、第２候補文字の参照番号ω₁，ω₂を記憶しない
点、(2) firstアドレスから参照番号(アドレス)への変
換メモリ２１が設けられている点、(3) ＭＰＵ１２の符
号語出力処理が楽になっている点である。first₁欄に書
き込まれているアドレスデータ（first₁(i))と、該アド
レスデータで指定される第１候補文字の参照番号
（ω₁）は一致し、又、first₂欄に書き込まれているア
ドレスデータ（first₂(i))と、該アドレスデータで指定
される第２候補文字の参照番号（ω₂）は一致してい
る。従って、辞書メモリ１１に第１候補文字、第２候補
文字の参照番号ω₁，ω₂を記憶しなくてもアドレスデー
タfirst₁(i)，first₂(i)より求めることができる。

【００７６】このため、入力文字が第１候補文字と一致
した場合には変換メモリにfirst₁(i)を第１参照番号Ｗ₁
として格納し、入力文字が第２候補文字と一致した場合
にはfirst₂(i)を第１参照番号Ｗ₁として格納する。そし
て、第１参照番号Ｗ₁で指示された第１又は第２候補文
字が次の入力文字と一致した場合には、第１参照番号Ｗ
₁を第２参照番号Ｗ₂にし（Ｗ₁→Ｗ₂）、しかる後、前述
のやり方で新たな第１参照番号Ｗ₁を求めて記憶する。
しかし、第１参照番号Ｗ₁で指示された第１又は第２候
補文字が次の入力文字と一致しない場合には、それまで
の第２参照番号Ｗ ₂を検索した最長一致文字列の符号語
としてＭＰＵ１２に入力する。このようにすれば、ＭＰ
Ｕ１２が毎回一致した参照番号ωを覚えておかなくて済
み、一致後の次の検索のための文字入力迄の時間を短縮
することができる。

【００７７】以上、本発明を実施例により説明したが、
本発明は請求の範囲に記載した本発明の主旨に従い種々
の変形が可能であり、本発明はこれらを排除するもので
はない。

【００７８】

【発明の効果】以上、本発明によれば、一度の辞書検索
により複数の候補文字を読み出し、複数の候補文字と１
つの入力文字とを一度に照合して辞書検索を行うように
したから、辞書検索を高速に行うことができる。又、本
発明によれば、一度の辞書検索により複数の候補文字と
共に、複数のアドレスを読み出し、複数の候補文字と１
つの入力文字との比較照合結果（第１候補と一致、第２
候補と一致、いずれの候補とも一致せず等）に基づいて
次に参照すべき複数の候補文字を直ちに前記所定アドレ
スから読み出して比較照合するように構成したから、連
続して動作が可能で辞書検索を高速に行うことができ
る。

【図面の簡単な説明】

【図１】本発明の原理説明図である。

【図２】本発明による辞書メモリの構造説明図である。

【図３】本発明による辞書内容説明図である。

【図４】本発明の符号化処理の第１の流れ図である。

【図５】本発明の符号化処理の第２の流れ図である。

【図６】本発明による辞書検索回路の第１の構成図であ
る。

【図７】本発明による辞書検索回路の別の構成図であ
る。

【図８】ＬＺＷ符号化説明図である。

【図９】辞書構成の説明図である。

【図１０】ＬＺＷ符号化のフローチャートである。

【図１１】ＬＺＷ復号化のフローチャートである。

【図１２】ＬＺＷ復号化の例外時における説明図であ
る。

【図１３】ＬＺＷ復号化説明図である。

【図１４】外部ハッシュ法の説明図

【図１５】外部ハッシュ法によるデータ構造説明図であ
る。

【図１６】外部ハッシュ法による辞書構造説明図であ
る。

【図１７】外部ハッシュ法によるＬＺＷ復号化の辞書検
索、辞書登録のフローチャートである。

【図１８】辞書登録の様子を示す第１の説明図表であ
る。

【図１９】辞書登録の様子を示す第２の説明図表であ
る。

【図２０】辞書登録の様子を示す第３の説明図表であ
る。

【図２１】従来の外部ハッシュ法による辞書検索回路の
構成図である。

【符号の説明】

１１辞書メモリ１２ＭＰＵ１３レジスタ部１４比較照合部１５アドレス選択部

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

Claims

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

【請求項１】既に符号化済みの文字列を相異なる部分
文字列に分け、該部分文字列を辞書に登録しておき、入
力文字列と最長に一致する部分文字列を辞書から検索
し、該最長一致文字列の番号を指定して符号化するデー
タ圧縮における辞書検索方法において、検索済文字列に連結する複数の候補文字が検索可能とな
るように複数のデータ要素を前記検索済文字列が指定す
る記憶域に記憶して部分文字列を辞書に登録し、最長一致文字列の検索に際して、検索済文字列に応じた
前記データ要素を辞書より一括して読み出し、前記データ要素に含まれる複数の候補文字と１つの入力
文字とを比較して一致照合を行い、入力文字と一致する候補文字が存在する場合には、該候
補文字が指定する記憶域からデータ要素を読み出し、次
の入力文字と該データ要素に含まれる複数の候補文字と
を比較して最長一致検索処理を続行することを特徴とす
る辞書検索方法。
【請求項２】前記データ要素は、検索済文字列に連結
する第１文字(ext₁)と、前記検索済文字列に連結する文
字であって第１文字とは別の第２文字（ext₂)と、前記
検索済文字列に連結する第１、第２文字とは別の第３文
字の格納アドレス(next₂)と、第１文字に連結する第４
文字の格納アドレス(first₁)と、第２文字に連結する第
５文字の格納アドレス(first₂)と、第１、第２文字のう
ち幾つ記憶されているかを示すフラグ(flag)を有し、１つの入力文字と複数の候補文字となる前記２つの第
１、第２文字の一致照合に際して、入力文字と第１、第
２文字が共に異なる場合にはアドレス（next₂)に基づい
次のデータ要素を読み出して一致照合を行い、入力文字
と第１文字が一致する場合には、アドレス（first₁)に
基づいて次の入力文字に対するデータ要素を読み出して
最長一致検索処理を続行し、入力文字と第２文字が一致
する場合には、アドレス(first₂)に基づいて次の入力文
字に対するデータ要素を読み出して最長一致検索処理を
続行することを特徴とする請求項１記載の辞書検索方
法。