JPS62194535A - 記号処理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は情報処理装置において記号データをマツチン
グ処理する記号処理装置に関する。

〔従来の技術〕

従来、記号データのマツチング処理は、汎用の情報処理
装置において、プログラムによって行なわれていた。次
のような２つの方法が一喰的であった。

（１）主記憶あるいは外部記憶上に要素の長さが一定の
配列を取り、被マツチング記号データを格納し、マツチ
ング要求が出された時、被マツチング記号データのキー
部を逐次取出し、マツチング記号データと比較し、一致
した場合、その被マツチング記号データの付加部を取り
出す。

（２）主記憶あるいは外部記憶上に要素の長さが一定の
配列を取り、被マツチング記号データのキー部のハツシ
ュ値を計算し、そのハツシュ値で示される配列上の位置
に被マツチング記号データを格納し、マツチング要求が
出された時、マツチング記号データのハツシュ値を計算
し、そのハフンユ値で示される配列上の位置に格納され
た被マツチング記号データのキー部とマツチング記号デ
ータとを比較し、一致した場合、その被マツチング記号
データの付加部を取り出す。

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

上述した従来の記号データのマツチング処理は、被マツ
チング記号データの量が膨大になると、処理時間が非常
に長くかかることと、可変長の記号データを扱いにくい
こととの２つの欠点があった。

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

この発明の記号処理装置は、キー部と付加部とから成る
被マツチング記号データ又はマツチング記号データを入
力緩衝記憶回路に受取って一時的に記憶し、その入力緩
衝記憶回路の被マツチング記号データのキー部又はマツ
チング記号データをハツシュ関数演算回路である一定の
幅に切取って数値化し、ある一定の成算規則によって３
１算し、その計算により得られたハツシュ値とその被マ
ツチング記号データとを主記憶回路に記憶しておき、そ
の主記憶回路に格納された前記被マツチング記号データ
のハツシュ値と入力緩衝記憶回路のマツチング記号デー
タのハツシュ値とをハツシュ値比較回路で比較し、その
両ハツシュ値が一致したとＪｕｌ明した場合に、主記憶
回路に格納されたその被マツチング記号データのキー部
と入力緩衝記憶回路のマツチング記号データとを記号デ
ータ比較回路で比較し、その両記号データが一致したと
判明した場合に主記憶回路上に格納されているその一致
した被マツチング記号データの付加部を抽出して出力緩
衝記憶回路に一時的に記憶する。

〔実施例〕

次にこの発明を図面を参照して説明する。

第１図はこの発明の一実施例を示す。入力緩衝記憶回路
１は、ハツシュ関数演算回路２と、記号データロ込み回
路３と、記号データ比較回路７とに接続され、ハツシュ
関数演算回路２は記号データ書込み回路３とハツシュ値
比較回路６とに接続され、記号データ書込み回路３は主
記憶回路４に接続され、主記憶回路上 ５に接続され、記号データ読出し回路５はハツシュ値比
較回路６と、記号データ比較回路７と、出力緩衝記憶回
路８とに接続され、ハツシュ値比較回路６は記号データ
比較回路７に接続され、記号データ比較回路７は出力緩
衝記憶回路８に接続され、制ｊ１１回路９はハツシュ関
数演算回路２と、記号データ３込み回路３と、記号デー
タあ”Ｃ出し回路５と、ハツシュ値比較回路６と記号デ
ータ比較回路７に凄Ｘ４こされている。

次にこの発明の動作について説明する。

まず制御回路９に、被マツチング記号データを入力する
１旨示が入ると、被マツチング記号データが入力緩衝記
憶回路１に記憶される。被マツチング記号データはハツ
シュ関数演算回路２でキー部がある一定の幅で切取られ
て数値化され、ある一定の演算規則で計算される。

第２図はハツシュ関数演算回路２におけるハツシュ値の
計算過程例を示す。第２図において入力された被マツチ
ング記号データのキー部１０はＪＩＳコードの場合、ビ
ット構成１１で表わされ、これを７ビノト単位でハツシ
ュすると（切取ると）、ハツシュ後のビット構成１２と
なり、これを１０進化すると１０進化後の数値１３とな
り、これらを加算するとハノソユ値１４が求められる。

計１γされたハノンユ値及び記号データは記号データ書
込み回路３によって主記憶回路４に書込まれ、蓄えられ
る。この一連の動作は被マツチング記号データがなくな
るまで続けられる。

第３図に主記ｊ１７回路４の状態を示す。すなわち各ワ
ードごとに各被マツチング記号データのハツシュ値１５
を先頭に、記号データのキー部の文字数１６、記号デー
タのキー部１７、記号データの付加部の文字数１８、記
号データの付加部１９が順次記憶されている。

次に制御回路９にマツチング処理を行なう指示が入ると
、新しくマツチング記号データが入出緩衝記憶回路１に
記憶される。入力されたマツチング記号データは、被マ
ツチング記号データと同様にハフシュ関数演算回路２で
ハツシュ値が計算される０次に記号データ読出し回路５
によって、主記憶回路４に格納された被マツチング記号
データのハフシュ値１５が逐次続出されて、ハツシュ値
比較回路６によってマツチング記号データのハツシュ値
と比較される。２個のハフシュ値が一致しない時、この
動作が繰返される。−敗した時、記号データ読出し回路
５によって主記憶に格納された被マツチング記号データ
のキー部１７が読出されて、記号データ比較回路７によ
ってマツチング記号データと比較される。２個の記号デ
ータが一致しない時、被マツチング記号データのハノン
ユ値を読出す動作へ返る。−敗した時、記号データ読出
し回路５によって主記憶回路４に格納された被マツチン
グ記号データの付加部１９が読出されて出力緩衝記憶回
路８に記憶される。一致する記号データが存在しない場
合、制御回路９は、その旨の信号を出力する。

〔発明の効果〕

以上説明したようにこの発明は、被マツチング記号デー
タのキー部のハツシュ値を計算して、被マツチング記号
データとともに主記憶回路に記憶し、マツチング要求が
出された時、マツチング記号データのハツシュ値を計算
し主記憶回路上に格納された被マツチング記憶データと
マツチング記号データのハツシュ値とを比較し、これら
が一致した時、更に被マツチング記号データのキー部と
マツチング記号データとを比較し、これらが一致した時
、被マツチング記号データの付加部を抽出する一連の手
段を電子回路で実現することにより、大量の記号データ
を・高速でマツチング処理することができ、さらに、可
変長の記号データを容易に扱うことができるという効果
がある。

【図面の簡単な説明】

第１図はこの発明の実施例を示すブロック図、第２図は
第１図のハツシュ関数演算回路２におけるハツシュ値の
計算過程の例を示す図、第３図は第１図の上記ｊＩ２回
路４の記憶例を示す図である。 ■・・・入出力緩衝記憶回路、２・・・ハツシュ関数演
算回路、３・・・記号データ１込み回路、４・・・主記
憶回路、５・・・記号データ読出し回路、６・・・ハツ
シュ値比較回路、７・・・記号データ比較回路、８・・
・出カフ１　ｊｊ’ｒ記憶回路、９・・・制御回路、１
０・・・被マツチング記号データのキー部及びマツチン
グ記号データ、１１・・・ＪＩＳコードのビット構成、
１２・・・ハツシュ後のどノド構成、１３・・・１０進
数化後の数値、１４・・・ハツシュ値、１５・・・ハツ
シュ値、１６・・・被マツチング記号データのキー部の
文字数、１７・・・被マツチング記号データのキー部、
１８・・・被マツチング記ぢデータの付加部の文字数、
１９・・・被７７ヂング記号データの（１加部。 陀　２図 第３図

Claims (1)

【特許請求の範囲】
1. （１）キー部と付加部とから成る被マッチング記号デー
   タ、又はマッチング記号データを受取って一時的に記憶
   する入力緩衝記憶回路と、 その入力緩衝記憶回路の前記被マッチング記号データの
   キー部又はマッチング記号データをある一定の幅に切取
   って数値化し、ある一定の演算規則によって計算するハ
   ッシュ関数演算回路と、前記被マッチング記号データと
   その被マッチング記号データに関して前記ハッシュ関数
   演算回路によって得られた値（以下ハッシュ値と呼ぶ）
   とを記憶する主記憶回路と、 その主記憶回路に格納された前記被マッチング記号デー
   タのハッシュ値と前記入力緩衝記憶回路に入力されたマ
   ッチング記号データのハッシュ値とを比較するハッシュ
   値比較回路と、 そのハッシュ値比較回路により前記２個のハッシュ値が
   一致したと判明した場合に、主記憶回路に格納されたそ
   の被マッチング記号データのキー部と前記入力緩衝記憶
   回路のマッチング記号データとを比較する記号データ比
   較回路と、 その記号データ比較回路により両記号データが一致した
   と判明した場合に前記主記憶回路上に格納されている一
   致した被マッチング記号データの付加部を抽出し、一時
   的に記憶する出力緩衝記憶回路とを有する記号処理装置
   。