JP2772124B2

JP2772124B2 - 辞書検索方式

Info

Publication number: JP2772124B2
Application number: JP2209566A
Authority: JP
Inventors: 茂吉田; 泰彦中野; 佳之岡田; 広隆千葉
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1990-08-06
Filing date: 1990-08-06
Publication date: 1998-07-02
Anticipated expiration: 2013-07-02
Also published as: JPH0495161A

Description

【発明の詳細な説明】〔目次〕概要産業上の利用分野従来の技術発明が解決しようとする課題課題を解決するための手段作用実施例発明の効果〔概要〕例えば増分分離型のZiv−Lempel符号化の際などに用
いられる辞書検索方式に関し、高速に辞書を検索することを目的とし、それぞれに与えられた参照番号に対応して辞書に登録
された相異なる文字列の中から、入力された参照番号と
文字とで表される文字列を検索する辞書検索方式におい
て、辞書は、参照番号に対応して、当該参照番号が与え
られた文字列に１文字を付加して得られる文字列のいず
れかに与えられた参照番号とこの文字列に付加された文
字とを格納する索引と、参照番号に対応して、当該参照
番号が与えられた文字列と最後の１文字が異なる文字列
のいずれかに与えられた参照番号とこの文字列に付加さ
れた文字とを格納するリストとを有し、最初は、入力さ
れた参照番号を指定して索引からの読出動作を行い、以
後は、辞書から読み出した参照番号を指定して、リスト
からの読出動作を行う読出手段と、辞書から読み出され
る文字の中から入力文字と一致する文字を検出する検出
手段と、辞書からの出力に参照番号が含まれているか否
かを判定する判定手段とを備え、読出手段と検出手段と
判定手段とがそれぞれ独立に動作するように構成する。

〔産業上の利用分野〕

本発明は、ユニバーサル符号の一種である増分分解型
のZiv−Lempel符号化の際などに用いられる辞書検索方
式に関する。

近年、文字コード，ベクトル情報，画像情報など様々
な種類のデータがコンピュータによって扱われるように
なっており、また、扱われるデータ量も急速に増大して
いる。

このような膨大なデータを蓄積したり伝送したりする
際には、データの中に含まれている冗長な部分を省いて
データ量を圧縮することが望ましい。このため、データ
の種類にかかわらず、効率よくデータを圧縮する方法が
望まれている。

ユニバーサル符号化方式は、予め符号表を定めておく
必要がないため、上述した様々なデータの圧縮に適用す
ることができるという特徴を有している。

ここで、本明細書においては、データの１語単位を
『文字』と称し、連続した複数語のデータを『文字列』
と称する。

ジブ−レンペル（Ziv−Lempel）符号は、上述したユ
ニバーサル符号の代表的な方法であり（宗像著「Ziv−L
empelのデータ圧縮法」，情報処理,Vol.20,No.1,1985参
照）、ユニバーサル型のアルゴリズムと増分分解型のア
ルゴリズムとが提案されている。更に、ユニバーサル型
アルゴリズムの改良として、LZSS符号（T.C.Bell,“Bet
ter OPM/L Text Compression",IEEE Trans.on Commun.,
Vol.COM−34,No.12,Dec.1986参照）があり、増分分解型
アルゴリズムの改良として、LZW符号（T.A.Welch,“A T
echnique for High−Performance Data Compression",C
omputer,June 1984）がある。

これらの符号化方式のうち、高速処理が可能であるこ
ととアルゴリズムが簡単であることから、LZW符号が記
憶装置のファイル圧縮などで使われるようになってい
る。

〔従来の技術〕

増分分解型アルゴリズムは、入力された文字列を、既
に辞書に登録された部分列に１文字を増分として付加し
て形成される成分の系列に分解し、この成分の系列を登
録された部分列に対応する参照番号と増分とで表すこと
により、入力文字列を符号化するものである。また、上
述した成分は、新しい部分列として辞書に登録され、以
降の符号化処理に用いられるようになっている。

更に、LZW符号においては、上述した増分を次の部分
列に組み込むようになっている。

以下、簡単のために、入力文字列として、“a",“b",
“c"の３文字からなる文字列“ababcbababaaaaa・・
・”（第４図（ａ）参照）が入力された場合について、
このLZW符号化方式について説明する。

この場合は、上述した３文字“a",“b",“c"に参照番
号『１』，『２』，『３』を与えて辞書に登録して、符
号化処理を開始する。

まず、入力文字列の先頭の文字（例えば文字“a"）を
読み込み、辞書からこの文字を検索し、この文字に対応
する参照番号（例えば『１』）を着目している文字列に
対応する符号ωとする。

その後、入力文字列の２番目以降の各文字を順次に読
み込んで、この文字を上述した増分に相当する拡張文字
Ｋとし、上述した符号ωとこの拡張文字Ｋとの組合せ
（ωＫ）で表される部分列（ωＫ）（以下、組合せ（ω
Ｋ）を部分列の表現と称する）を辞書から検索する。該
当する部分列（ωＫ）が検索された場合は、上述した部
分列（ωＫ）に対応する参照番号を新しい符号ωとし
て、更に、入力文字列の次の文字を読み込んで、上述し
た処理を繰り返す。

このようにして、符号化しようとする文字列を順次に
１文字ずつ延ばしていき、辞書からこの文字列を順次に
検索することにより、辞書に登録された部分列の中か
ら、入力文字列の注目している部分と最も長く一致する
部分列が検索され、この部分列に対応する参照番号が、
該当する符号ωとして出力される。また、このとき、参
照番号ωに対応する部分列（ω）に拡張文字Ｋを継ぎ足
した部分列が、参照番号ωと拡張文字Ｋとの組合せ（ω
Ｋ）で表され、参照番号が与えられ、新しい部分列とし
て辞書に登録される。

このようにして、第４図（ａ）に示した文字列は、図
において下線に付して示した部分列に分解され、第４図
（ｂ）に示すように、各部分列に対応する符号『１』，
『２』，『４』，…が出力される。また、第４図（ｃ）
に入力文字列と辞書に登録された部分列との対応関係
を、第１表に作成された辞書の例を示す。

また、上述したLZW符号化処理の際に作成された辞書
は、第５図に示すように、、樹状の構成を持っており、
辞書の要素のそれぞれは、辞書の樹の各節点に対応して
いる。第５図において、各節点に括弧を付して示した数
字は、対応する辞書の要素の参照番号を示している。

ここで、上述した符号化処理における部分列の検索の
際に、辞書に登録された要素を順次に検索するのでは、
処理に要する時間が長くなるので、辞書の検索処理にハ
ッシュ法を適用して高速化を図っている。

ハッシュ法は、文字列からなる集合Ｓの要素ｘからこ
の要素ｘの格納場所のアドレスを求める関数（ハッシュ
関数）を定義し、このハッシュ関数によって求められた
アドレスに要素ｘを格納するようにしたものである。ま
た、上述したハッシュ関数によって求められるアドレス
をハッシュアドレスと称する。

例えば、上述した参照番号ωと拡張文字Ｋとを２進数
で表し、これを組合せ（ωＫ）のハッシュアドレスとす
ればよい。しかしながら、この場合は、辞書に膨大な容
量を割り当てる必要がある。

このため、ハッシュアドレスの一部を用い、このハッ
シュアドレスの部分が同じ値を有する要素を格納するリ
ストを設けるようにした外部ハッシュ法が用いられてい
る。この外部ハッシュ法においては、第６図に示すよう
に、索引部をハッシュアドレスで検索することにより、
該当するリストが示されるようになっている。また、各
リストには、各要素に対応する識別情報と次の要素の格
納場所を示すポインタとが格納されており、順次に探索
できるようになっている。

例えば、上述した参照番号ωをハッシュアドレスと
し、このハッシュアドレスに、参照番号ωに対応する部
分列に１文字を付加した部分列を格納するリストの先頭
アドレスを格納し、該当するリストに、上述した参照番
号ωに対応する節点の『子』に相当する節点に対応する
部分列を順次に格納すればよい。この場合は、各要素の
拡大文字Ｋを対応する識別情報としてリストに格納すれ
ばよい。

第７図に、辞書の検索に外部ハッシュ法を用いた場合
の符号化動作を表す流れ図を示す。

上述したように、入力文字列の少なくとも最初の文字
を含むように辞書を初期化し、変数ｎに次に登録される
部分列に与えられる参照番号をセットする。例えば、文
字“a",“b",“c"に与えた参照番号『１』，『２』，
『３』をハッシュアドレスとして辞書に格納し、変数ｎ
に数値『４』をセットすればよい。ここで、辞書に登録
できる部分列の最大数をN_maxとし、それぞれN_max個の成
分からなる配列First,配列Next,配列Extを定義し、これ
らの配列の全ての成分に初期値『０』を設定する。この
配列Firstは、第６図に示した索引部に相当し、配列Nex
tおよび配列Extはリストに相当している。従って、配列
Firstのｉ番目の成分First［ｉ］には、参照番号ｉの節
点に対応するリストの先頭となる配列Nextの成分を示す
番号が設定される。また、配列Extのｉ番目の成分Ext
［ｉ］には、参照番号ｉで示される辞書の要素の拡張文
字Ｋが設定される。また、配列Nextのｉ番目の成分Next
［ｉ］には、参照番号ｉの要素の『兄弟』に相当する要
素を示すポインタが設定される。

次に、最初の文字Ｋを読み込んで、この文字Ｋに対応
する参照番号を変数ｉに設定して、符号化処理を開始す
る。

まず、拡張文字Ｋとして、入力文字列の次の文字を読
み込んで（ステップ701）、その次に読み込むべき文字
があれば、ステップ702における肯定判定となり、辞書
の検索処理を開始する。

この場合は、変数ｉを別の変数ωに退避し、変数ｊに
初期値『０』を設定してから（ステップ703）、変数ｉ
に対応する成分First［ｉ］の値で示される配列Nextの
成分の番号を設定する（ステップ704）。

ステップ705において、変数ｉが数値『０』でないと
判定された場合（否定判定）は、該当するリストに含ま
れる要素を候補として、このリストにおける探索処理を
開始する。

この場合は、該当する要素の拡張文字を示す成分Ext
［ｉ］と拡張文字Ｋとを比較し（ステップ706）、この
ステップ706における否定判定の場合は、ステップ707に
おいて、成分Next［ｉ］に設定された次の要素のポイン
タを新しい変数ｉとして、ステップ705に戻る。このよ
うにして、ステップ705〜ステップ707を繰り返して、該
当するリストを探索する。

ステップ706において、成分Ext［ｉ］＝Ｋとなった場
合（肯定判定）は、入力された文字列と一致する部分列
が辞書に登録されていると判断し、ステップ701に戻っ
て次の文字を読み込み、この文字を付加した文字列の符
号化を行う。

一方、変数ｉに対応する成分First［ｉ］あるいは成
分Next［ｉ］の値が『０』であった場合は、ステップ70
5における肯定判定となる。

ここで、成分First［ｉ］の値が『０』である場合
は、変数ｉの節点の『子』に相当する要素がまだ登録さ
れていないため、該当するリストが定義されていないこ
とを示している。一方、成分Next［ｉ］の値が『０』で
ある場合は、該当するリストの中に求める部分列が格納
されていないことを示している。

いずれの場合においても、ステップ703において変数
ωに退避された参照番号が、入力された文字列に最も長
く一致する登録された部分列を示しており、この参照番
号ωに対応する符号を出力して（ステップ708）、新し
い部分列の登録処理を行う。

まず、変数ｎの値を変数ｉに設定するとともに、変数
ｎをインクリメントし、また、変数ｉに対応する成分Ex
t［ｉ］に拡張文字Ｋを設定する（ステップ709）。

次に、変数ｊの値が『０』であるか否かを判定し（ス
テップ710）、肯定判定の場合は、成分First［ω］に変
数ｉを設定して（ステップ711）、参照番号ωに対応す
るリストを定義する。一方、ステップ710における否定
判定の場合は、成分Next［ｊ］に変数ｉを設定して（ス
テップ712）、該当するリストに新しい『兄弟』を付け
加える。

このようにして、登録処理が終了した後に、拡張文字
Ｋに対応する参照番号を変数ｉとして（ステップ71
3）、ステップ701に戻って上述した処理を繰り返し、読
み込むべき文字がなくなったときに、ステップ702にお
ける否定判定となり、そのときの変数ωに対応する符号
を出力して（ステップ714）処理を終了する。

〔発明が解決しようとする課題〕

ところで、上述した従来方式にあっては、リストの検
索処理において、該当するリストがあるか否かおよび次
の要素がリストにあるか否かを判定する連結判定処理、
入力された拡張文字と一致する候補文字を検出する一致
検出処理、次のポインタを設定して辞書から読み出す読
出処理、の３つの処理が順次に行われている。このよう
に、ソフトウェアで順次にリストを手操る処理を行う
と、部分列の検索処理に時間がかかるため、符号化処理
速度は数10KB/s程度となる。このため、磁気テープ装置
や磁気ディスク装置などへの転送速度（数100KB/s〜数M
B/s）と合わせて実時間で符号化処理をができないとい
う問題点があった。

一方、上述した符号化処理の各ステップをそれぞれ独
立な素子を用いてデータ圧縮装置を構成すれば、符号化
処理の高速化を図ることが可能であるが、回路規模が大
きくなり、コストが高くなるという欠点がある。

ここで、上述した従来例においては、簡単のために３
文字からなる文字列を符号化する場合について説明した
が、実際の文字列は多くの文字から構成されている。従
って、通常、辞書の検索処理においては、ある参照番号
に対応するリストを手操って、『兄弟』に相当する要素
を順次に検索して一致あるいは連結する要素がないこと
を検出する処理に最も長い時間を要している。

本発明は、このような点にかんがみて創作されたもの
であり、高速に辞書の検索を行うようにした辞書検索方
式を提供することを目的とする。

〔課題を解決するための手段〕

第１図は、本発明の原理ブロック図である。

（ｉ）請求項１の発明図において、それぞれに与えられた参照番号に対応し
て辞書110に登録された相異なる文字列の中から、入力
された参照番号と文字とで表される文字列を検索する辞
書検索方式における辞書110は、参照番号に対応して、
該当参照番号が与えられた文字列に１文字を付加して得
られる文字列のいずれかに与えられた参照番号とこの文
字列に付加された文字とを格納する索引111と、参照番
号に対応して、当該参照番号が与えられた文字列と最後
の１文字が異なる文字列のいずれかに与えられた参照番
号とこの文字列に付加された文字とを格納するリスト11
2とを有している。

読出手段121は、最初は、入力された参照番号を指定
して索引111からの読出動作を行い、以後は、辞書110か
ら読み出した参照番号を指定して、リスト112からの読
出動作を行う。

検出手段122は、辞書110から読み出される文字の中か
ら入力文字と一致する文字を検出し、この検出結果を検
索結果として出力する。

判定手段123は、辞書110からの出力に参照番号が含ま
れているか否かを判定し、この判定結果を検索結果とし
て出力する。

全体として、読出手段121と検出手段122と判定手段12
3とがそれぞれ独立に動作するように構成されている。

（ii）請求項２の発明請求項２の発明における読出手段121は、所定の時間
間隔で辞書110に対する読出動作を起動し、請求項１の
発明による辞書検索方式において、検出手段122による
検出動作と判定手段123による判定動作とを読出手段121
による読出動作と並行して行うように構成されている。

〔作用〕

（ｉ）請求項１の発明辞書110の索引111には、参照番号に対応して、この参
照番号に対応する文字列に１文字を付加した文字列のい
ずれか、即ち、上述した参照番号に対応する辞書の樹の
節点に『子』として接続されている節点のいずれかに対
応する文字列に与えられた参照番号とこの文字列に付加
された文字とが格納されている。また、リスト112に
は、参照番号に対応して、この参照番号が与えられた文
字列と最後の１文字が異なる文字列のいずれか、即ち、
上述した参照番号に対応する辞書の樹の節点の『兄弟』
に相当する節点に対応する文字列のいずれかに与えられ
た参照番号とこの文字列に付加された文字とが格納され
ている。

最初は、読出手段121により、入力された参照番号が
指定され、索引111からの読出動作が行われ、以後は、
この読出手段121により、辞書110から読み出した参照番
号が指定され、リスト112からの読出動作が行われる。
従って、読み出された参照番号に基づいて、次々にリス
ト112からの読出動作が行われ、導入された参照番号に
対応する節点に『子』として接続された節点のそれぞれ
が順次に検索される。

ここで、上述した参照番号としては、入力された文字
列の最後の１文字を除いた部分に与えられた参照番号を
導入し、上述した最後の１文字を検出手段122に入力す
ればよい。

上述したようにして、辞書110から読み出される文字
の中から、検出手段122により、入力された文字と一致
する文字が検出された場合は、該当する文字列を検出し
た旨が検索結果として通知される。

一方、索引111と該当する参照番号が格納されいない
場合と、リスト112に該当する参照番号が格納されてい
なかった場合は、上述した判定手段123により、参照番
号が含まれていないと判定され、該当する文字列が登録
されていない旨が検索結果として通知される。

請求項１の発明においては、読出手段121と検出手段1
22と判定手段123とが、それぞれ独立に動作し、辞書110
からの読出動作と一致検出動作と連結判定動作とが、そ
れぞれ独立に行われる。従って、従来方式のように、読
出動作と一致検出動作と連結判定動作とを順次に行う場
合のように、前の処理の終了を待つ必要がないので、辞
書の検索処理を高速化することが可能となる。

（ii）請求項２の発明請求項２の発明において、読出手段121は、所定の時
間間隔で辞書110に対する読出動作を行い、また、検出
手段122による検出動作と判定手段123による判定動作と
が、読出手段121による読出動作と並行して行われる。

例えば、上述した読出手段121は、辞書110からの読出
動作に要する時間ごとに読出動作を行うようにすればよ
い。通常は、読出動作に要する時間に比べて、検出手段
122による検出動作および判定手段123による判定動作は
短い時間で終了すると考えられ、読出動作と検出動作お
よび判定動作とを並行して行うことにより、検索処理を
パイプライン化して処理することができる。

従って、請求項２の発明にあっては、読出動作と検出
動作および判定動作とをパイプライン化して処理するこ
とにより、辞書110からの文字列の検索処理を高速化す
ることが可能となる。

〔実施例〕

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

第２図は、本発明の一実施例による辞書検索方式を適
用したデータ圧縮装置の構成を示す。

ここで、第１図と実施例との対応関係について説明し
ておく。

辞書110は、辞書230に相当する。

索引111は、索引部231に相当する。

リスト112は、リスト部232に相当する。

読出手段121は、アドレスレジスタ241と文字レジスタ
242aとフリップフロップ245とタイミング制御回路246と
に相当する。

検出手段122は、文字レジスタ242bと比較回路243とに
相当する。

判定手段123は、否定論理和（NOR）回路244に相当す
る。

以上のような対応関係があるものとして、以下実施例
の構成および動作を説明する。

第２図において、201はマイクロプロセッサ（MPU）
を、202は入力ポート部を、230は辞書を、240は辞書検
索回路を、205は出力ポート部をそれぞれ示している。
また、上述したMPU201と、入力ポート部202と辞書230と
辞書検索回路240と出力ポート部205とは、バス206を介
して相互に接続されている。

また、入力ポート部202を介して入力された文字列
は、MPU201によりLZW符号化され、出力ポート部205を介
して、磁気ディスク装置（図示せず）などに転送されて
蓄積されるようになっており、このとき、辞書検索回路
240によって、辞書230に対する検索処理が行われるよう
になっている。

上述した辞書230は、2N_max個の領域から構成されてお
り、これらの領域のそれぞれには、『１』〜『2N_max』
のアドレスが付けられている。このうち、アドレスの最
上位ビットが『０』の領域は索引部231に割り当てられ
ており、最上位ビットが『１』の領域はリスト部232に
割り当てられている。また、索引部231およびリスト部2
32の各領域は、アドレスの最上位ビットを除く下位部分
で表される参照番号に対応している。また、この索引部
231およびリスト部232の各領域は、第３図に示すよう
に、ポインタ部と文字部とで形成されており、このポイ
ンタ部と文字部とが同時に読み出されるようになってい
る。例えば、各領域が２ワードの容量を有している場合
は、上位の１ワードをポインタ部とし、下位の１ワード
を文字部とすればよい。

索引部231の各領域のポインタ部には、対応する参照
番号が与えられた部分列に１文字を付加した部分列の中
で最初に現れた部分列に対応する参照番号が格納されて
おり、文字部には、ポインタ部に格納された参照番号に
対応する部分列に増分として付加された文字が格納され
ている。

リスト部232の各領域のポインタ部には、対応する参
照番号が与えられた部分列と最後の１文字が異なってい
る部分列の中で次に現れた部分列に対応する参照番号が
格納されており、文字部には、ポインタ部に格納された
参照番号に対応する部分列に増分として付加された文字
が格納されている。

上述した索引部231およびリスト部232の各領域の内容
には、符号化処理を開始する際に、初期値『０』が設定
されるようになっている。

辞書検索回路240において、241はアドレスレジスタ
を、242a,242bは文字レジスタを、243は比較回路を、24
4は否定論理和（NOR）回路を、245はフリップフロップ
（FF）を、246はタイミング制御回路をそれぞれ示して
いる。

上述したアドレスレジスタ241には、バス206を介して
導入されるデータのうち上位の１ワード、即ち、辞書23
0の索引部231あるいはリスト部232の各領域のポインタ
部から読み出された参照番号が導入されるようになって
いる。また、文字レジスタ242aには、下位の１ワード、
即ち、索引部231あるいはリスト部232の文字部から読み
出された文字が導入されるようになっている。一方、文
字レジスタ242bには、MPU201により、入力ポート部202
を介して入力された文字列の中の１文字が順次にセット
されるようになっている。

また、アドレスレジスタ241の出力は、辞書230にアド
レスの下位部分として導入され、FF245の出力は辞書230
にアドレスの最上位ビットとして導入されるようになっ
ている。

比較回路243は、上述した２つの文字レジスタ242a,24
2bのそれぞれに格納された文字を比較し、２つの文字が
一致したときに、論理“1"を出力してMPU201に通知する
ように構成されている。

また、NOR回路244には、上述したアドレスレジスタ24
1の出力が導入されており、このアドレスレジスタ241に
格納された参照番号が初期値『０』であったときに、論
理“1"を出力してMPU201に通知するように構成されてい
る。

タイミング制御回路246は、MPU201の指示に応じて、
辞書230からの読出動作を指示する読出信号を出力する
とともに、ロード信号を出力して、アドレスレジスタ24
1および文字レジスタ242aにデータを格納するタイミン
グの制御を行うようになっている。

以下、辞書検索回路240による辞書230の検索動作につ
いて説明する。

まず、MPU201は、入力ポート部202を介して新たに入
力された１文字を辞書検索回路240の文字レジスタ242b
に入力するとともに、上述した１文字を付加して符号化
しようとしている文字列に対応する参照番号ωをアドレ
スレジスタ241に入力して、タイミング制御回路246に検
索動作の開始を指示する。

例えば、第４図（ａ）に示した文字列が順次に入力さ
れる場合は、まず、MPU201は、最初の文字“a"に対応す
るハッシュアドレス（例えば『１』）を求め、このハッ
シュアドレスをアドレスレジスタ241に入力する。ま
た、次の文字“b"を読み込んで、この文字“b"を文字レ
ジスタ242bに入力し、辞書検索回路240のタイミング制
御回路246に検索動作の開始を指示すればよい。

上述した検索開始指示に応じて、タイミング制御回路
246は、まず、FF245の出力を論理“0"にリセットし、そ
の後、辞書230に読出信号を導入して読出動作を起動す
る。

これに応じて、辞書230の索引部231の参照番号に対応
する領域から、該当する参照番号と文字とが読み出さ
れ、バス206を介して辞書検索回路240に導入され、参照
番号はアドレスレジスタ241に、文字は文字レジスタ242
aにそれぞれ導入される。

タイミング制御回路246は、上述した読出信号を出力
してから辞書230からのデータの読出動作に要する時間
（読出サイクル時間）τだけ経過した後に、アドレスレ
ジスタ241と文字レジスタ242aとにロード信号を導入す
る。

このロード信号に応じて、アドレスレジスタ241によ
り、上述した参照番号が格納され、文字レジスタ242aに
より、上述した文字が格納される。

その後、タイミング制御回路246は、FF245に論理“1"
をセットするとともに読出信号を出力し、上述した読出
サイクル時間τの経過後にロード信号を出力する。以
後、タイミング制御回路246は、MPU201からの指示がな
い限り、上述した動作を繰り返して、読出サイクル時間
τごとに読出動作を繰り返す。但し、FF245に論理“1"
をセットする動作は、繰り返す必要はない。

上述したようにして、FF245に論理“1"をセットする
ことにより、アドレスの最上位ビットが『０』から
『１』に切り換えられ、以後は、上述した読出サイクル
時間τごとに、リスト部232に対する読出動作が行われ
る。

このように、辞書230から読み出された参照番号を次
の読出アドレスとして指定するすることにより、辞書の
樹において、上述した参照番号ωに対応する部分列の
『子』として接続された部分列に増分として付加された
文字が順次に読み出され、文字レジスタ242aに格納され
る。このことは、参照番号ωに対応する部分列の『子』
に相当する部分列に順次読み出すことに相当している。

上述した読出動作と並行して、比較回路243により、
その前に読み出されて文字レジスタ242aに格納されてい
る文字と文字レジスタ242bに格納されている拡張文字Ｋ
との比較が行われている。従って、辞書230から新しい
文字が読み出されるごとに、比較回路243により、辞書2
30から読み出された文字が順次に拡張文字Ｋと比較さ
れ、２つの文字が一致したときに、論理“1"が出力され
てMPU201に導入される。

このようにして、比較回路243により、従来方式の一
致検出処理に相当する処理が、読出動作と並行して行わ
れる。

従って、MPU201は、この比較回路243により、論理
“1"が出力されたときに、参照番号ωに対応する部分列
に拡張文字Ｋを付加した部分列が検索されたと判断すれ
ばよい。この場合は、MPU201は、入力された文字列から
次の１文字を読み込んで文字レジスタ242bに格納すると
ともに、タイミング制御回路246に検索動作の開始を指
示すればよい。これにより、同様にして、検索された文
字列に更に１文字を付加して得られる部分列の検索が開
始される。

ここで、上述した場合に、アドレスレジスタ241に格
納されている参照番号は、検索された部分列に対応する
参照番号であるから、MPU201は、アドレスレジスタ241
に該当する参照番号を改めて格納する必要はない。

一方、NOR回路244による論理演算動作もまた、上述し
た読出動作とは独立して行われている。従って、読出動
作と並行して、その前に読み出された参照番号について
の論理演算動作が行われ、辞書230から読み出された参
照番号が初期値『０』であった場合に、このNOR回路244
により、論理“1"が出力されてMPU201に通知される。

ここで、読み出された参照番号が初期値『０』であっ
た場合は、該当する部分列が辞書230に登録されていな
いことを示している。このように、読み出された参照番
号が初期値『０』であるか否かを判定することにより、
NOR回路244により、上述した読出動作と並行して、従来
のステップ705に相当する連結判定処理が行われる。

従って、MPU201は、NOR回路244の出力が論理“1"とな
ったときに、タイミング制御回路246に検索動作の中止
を指示し、最後に検索された部分列に対応する参照番号
ωを符号として出力し、新しい部分列の登録処理を行え
ばよい。

例えば、MPU201は、上述した参照番号ωに辞書検索回
路240のFF245の出力を最上位ビットとして付加したもの
をアドレスとして辞書230に供給し、新しい参照番号と
拡張文字Ｋとを格納すればよい。

従って、FF245が論理“0"にリセットされている場合
は、辞書230の索引部231の該当するアドレスに、新しい
参照番号と拡張文字Ｋとが格納され、上述したレジスタ
に保持された参照番号の要素の『子』に相当する要素と
して登録される。また、FF245に論理“1"がセットされ
ている場合は、リスト部232の該当するアドレスに新し
い参照番号と拡張文字Ｋとが格納され、上述したレジス
タに保持された参照番号の次の『兄弟』に相当する要素
として登録される。

このようにして、入力された文字列を順次に符号化す
るとともに、新しい部分列が辞書230に登録される。

第２表に、第５図に示した辞書に実施例による辞書検
索方式を適用して得られた辞書230の索引部231およびリ
スト部232を示す。

また、第２表の各欄の左側に付した数字は、参照番号
を示している。

上述したように、アドレスレジスタ241と２つの文字
レジスタ242a,242bと比較回路243とNOR回路244とを備え
て辞書検索回路240を構成し、タイミング制御回路246に
より、辞書230からの読出サイクル時間τごとに読出動
作を行うようにする。

ここで、比較回路243およびNOR回路244の動作は、辞
書230からの読出動作とは独立に行われる。従って、タ
イミング制御回路246により、次の部分列の読出動作と
並行して、その前に読み出された部分列について、比較
回路243による比較動作およびNOR回路244による論理演
算動作とが実行される。

このように、上述した従来方式の連結判定処理と一致
検出処理と読出処理とのそれぞれを行う独立した回路
（第２図に示したNOR回路244,比較回路243,タイミング
制御回路246に相当する）を設けることにより、これら
の処理をパイプライン化することが可能となる。従っ
て、この場合は、リストを一回検索するために要する時
間は、上述した辞書230からの読出サイクル時間τとな
る。

このようにして、第２図に示したような簡単な回路を
用いて、辞書230からの文字列の検索処理を高速化する
ことが可能となる。これにより、辞書の検索処理に要す
る時間を短縮して、符号化処理の高速化を図り、符号化
処理を磁気ディスク装置への転送速度と同程度とするこ
とができ、符号化したデータを磁気ディスク装置などに
実時間で転送することができる。

また、第２図に示したように、辞書検索回路240は、
簡単な回路で構成されており、データ圧縮装置のハード
ウェア量を増大させることはない。また、MPU201は、比
較回路243およびNOR回路244の出力が論理“1"になった
ときに、これを検出して動作すればよいので、特に高速
に動作する必要はない。

なお、上述した実施例においては、データ圧縮装置に
適用した場合について説明したが、これに限らず、樹状
の構成を有する辞書を外部ハッシュ法を用いて検索する
場合であれば適用できる。

〔発明の効果〕

上述したように、請求項１の発明によれば、読出手段
と検出手段と判定手段とをそれぞれ独立に動作させるこ
とにより、従来方式のように、前の処理の終了を待つ必
要がないので、辞書の検索処理を高速化することが可能
となり、符号化処理の高速化を図ることができる。

請求項２の発明によれば、読出動作と検出動作および
判定動作とをパイプライン化して処理されるので、辞書
からの文字列の検索処理を更に高速化することが可能と
なる。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、第２図は本発明の一実施例によるデータ圧縮装置の構成
図、第３図は実施例による辞書に格納されたデータの構成を
示す図、第４図はLZW符号化方式の説明図、第５図は辞書の構成を示す図、第６図は外部ハッシュ法の説明図、第７図は従来の符号化動作を表す流れ図である。図において、 110は辞書、 111は索引、 112はリスト、 121は読出手段、 122は検出手段、 123は判定手段、 201はマイクロプロセッサ、 202は入力ポート部、 205は出力ポート部、 206はバス、 230は辞書、 231は索引部、 232はリスト部、 240は辞書検索回路、 241はアドレスレジスタ、 242は文字レジスタ、 243は比較回路、 244は否定論理和（NOR）回路、 245はフリップフロップ（FF）、 246はタイミング制御回路である。

フロントページの続き (72)発明者千葉広隆神奈川県川崎市中原区上小田中1015番地富士通株式会社内 (56)参考文献電子情報通信学会論文誌ＡＶｏｌ. 73，Ｎｏ．９，Ｐ．1529−1533，1990 (58)調査した分野(Int.Cl.⁶，ＤＢ名) G06F 17/30 H03M 7/30 ＪＩＣＳＴ科学技術文献ファイル

Claims

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

【請求項１】それぞれに与えられた参照番号に対応して
辞書（110）に登録された相異なる文字列の中から、入
力された参照番号と文字とで表される文字列を検索する
辞書検索方式において、前記辞書（110）は、前記参照番号に対応して、当該参照番号が与えられた文
字列に１文字を付加して得られる文字列のいずれかに与
えられた参照番号とこの文字列に付加された文字とを格
納する索引（111）と、前記参照番号に対応して、当該参照番号が与えられた文
字列と最後の１文字が異なる文字列のいずれかに与えら
れた参照番号とこの文字列に付加された文字とを格納す
るリスト（112）とを有し、最初は、入力された参照番号を指定して前記索引（11
1）からの読出動作を行い、以後は、前記辞書（110）か
ら読み出した参照番号を指定して、前記リスト（112）
からの読出動作を行う読出手段（121）と、前記辞書（110）から読み出される文字の中から入力文
字と一致する文字を検出し、この検出結果を検索結果と
して出力する検出手段（122）と、前記辞書（110）からの出力に参照番号が含まれている
か否かを判定し、この判定結果を検索結果として出力す
る判定手段（123）と、を備え、前記読出手段（121）と前記検出手段（122）と
前記判定手段（123）とがそれぞれ独立に動作するよう
に構成することを特徴とする辞書検索方式。
【請求項２】前記読出手段（121）が、所定の時間間隔
で辞書（110）に対する読出動作を起動し、前記検出手
段（122）による検出動作と前記判定手段（123）による
判定動作とを前記読出手段（121）による読出動作と並
行して行うように構成したことを特徴とする請求項１記
載の辞書検索方式。