JPS6142032A - 情報検索装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、データ処理装置と外部記憶装置とで構成され
る情報検索装置において、大量のデータの検索・登録等
を行なう情報検索装置に関するものである。

従来例の構成とその問題点 従来例を図を用いて説明を行なう。第１図は、ハツシン
グ関数を用いた情報検索装置の構成方式の１例であり、
１ａ、１ｂは検索キーワード、２ａ。

２ｂはハツシングテーブル上のアドレス、３ａ。

３ｂはデータアドレス記憶部内の該当キーワードのアド
レス、４ａ、４ｂはデータ記憶部の該当キ−ワードのア
ドレス群、６は求めるデータのデータ記憶部内のアドレ
ス、６は求めるデータ、７はデータ記憶部の該当キーワ
ードのアドレス群の取出し、８は求めるデータの取出し
を表す。更にＡはハツシング処理手段を実現したハツシ
ング処理部、Ｂはハツシング処理を実現するためのキー
ワード情報を格納するハツシングテーブル部、Ｃはハツ
シングテーブル本体、Ｄはキーワードが該当する区画内
のハツシングテーブル本体のパケット内に入りきらない
時のためのオーバーフローエリア、Ｆはキーワードのデ
ータが格納されているアドレスを記憶しているデータア
ドレス記憶部、Ｅはハツシング処理により取出された該
当キーワードのデータアドレス記憶部のアドレスを用い
てデータアドレス記憶部Ｆから取り出したいデータのア
ドレス情報を取出すデータアドレス取出部、Ｇは複数の
キーワードに対して取出されたデーイアドレス群に対し
論理演算を行い取出すべきデータの絞り込みを行なうデ
ータアドレス演算部、■は求めるデータが格納されてい
るデータ記憶部、Ｈはデータ記憶部工のアドレス情報５
を用いて実際に求めるデータを取出すデータ取出部であ
る。第２図ａは、第１図のハツシングテーブル部Ｂの実
現方法の一例であり、ハツシングテーブル１１オーバー
フローエリアＫがそれぞれ第１図のＣ，Ｄに対応してい
る。Ｌｌはハツシング処理部で生成されるアドレス表示
、Ｍｌはキーワード情報格納エリア、Ｎ１は該当するキ
ーワードのデータアドレス記憶部のアドレス情報格納エ
リア、０１は該当スるハツシングテーブルのパケットが
総て使用された場合に用いるオーバーフローエリアにの
格納位置を示すエリア、Ｌ２はオーバーフローエリアに
のアドレス表示、Ｍ２はオーツ５−フロー二リアにのキ
ーワード情報格納エリア、Ｎ２はオーバーフローエリア
にの該当するキーワードのデータアドレス記憶部のアド
レス情報格納エリア、０２は次に用いるオーバーフロー
エリアにの格納位置を示すエリアである。第３図は第１
図のデータアドレス記憶部Ｆの実現方法の一例であり固
定長のセルに求めるデータのアドレス情報を複数個格納
している。Ｐは該当するデータアドレス情報を取出すた
めのアドレス表示、Ｑはデータ記憶部のアドレス情報を
格納するエリア、Ｒはそのエリア内のアドレス情報を入
れる場所が総て使用された場合の次格納エリアを示すエ
リアである。

第１図のように構成されたハツシング関数を用いた検索
装置において、成るハツシングアルゴリズムによって第
２図す、ｃのようなキーワードが登録されテイテ、！−
’７−）’ＮＩ　ＳＨＩＭＯＴＯとＫＡＴＯＨに関する
データを取出す場合を考える。このとき第１図において
＆をＮＩＳＨＩＭＯＴＯｌｂをＫＡＴＯＨとする。キー
ワード１ａと１ｂがハツシング処理部Ａで処理されハツ
シングテーブルアドレス２ａと２ｂ（具体的には第２図
で示したように０６とＯＡになる）となり、これらをハ
ツシングテーブル部Ｂに入れデータアドレス記憶部Ｆの
アドレス情報３ａと３ｂ（具体的には第２図で示したよ
うに３６と３４になる）を得る。

その際、キーワードＫＡＴＯＨの方は該当する区画にシ
ノニムがないためすぐに求めるアドレス情報を得ること
ができるが、キーワードＮＩＳＨＩＭＯＴＯの方は該当
区画内にシノニムが多数二芋在するためハツシングテー
ブル内の該当する区画内だけでなくオーバーフローエリ
アに内の該当区画内まで検索しているキーワードを探す
ことによって求めるアドレス情報を得ている。このよう
に従来のハツシング処理方式では該当区画内に発生する
シノニムの処理においてオーバーフローエリアの管理・
該当区画内で求めるキーワードを検索する処理等を避け
ることが不可能であり、簡単で高速な処理が可能なハツ
シング処理において問題となっている。

次に求めたデータアドレス記憶部Ｑのアドレス情報３ａ
と３ｂをデータアドレス取出部ＥＫ入れ各キーワードの
データ記憶部のアドレス情報４ａと４ｂ（具体的には第
３図す、ｃで示したように（５１，６５，６６，５９，
６０，８５，８７）と（５１，５２，６３，５４，５５
，５６，５７）になる）を求める。この時も、第３図の
ように求めるアドレス情報が複数個存在する場合は可変
長個数のデータを管理する機構が必要になり、そのデー
タの登録・取出処理の実現方法が問題となってくる。さ
らに求めた各キーワードのデータ記憶部のアドレス情報
４ａと４ｂをデータアドレス演算部Ｇに入れ、絞り込ん
だデータ記憶部のアドレス情報５（具体的には第３図ｄ
で示したように〔ｓｌ、ｔｓｔｓ、６ｅ〕ｆなる）を求
める。この時も、第３図のように求めるアドレス情報が
多数個存在する場合はその論理演算処理の実現方法が問
題となってくる。最後にこのアドレス情報６をデータ取
出部Ｈに入れ求めるデータをデータ記憶部工から取出す
。

以上のように第１図のような情報検索装置においてはハ
ツシングテーブル部のシノニムの処理、データアドレス
記憶部での複数データの管理、データアドレス演算部で
の大量データの演算という困難な問題が存在していた。

発明の目的 本発明は、従来ハッシング関数を用いる情報検索方式に
おいてはハツシングテーブル部のシノニムの処理、デー
タアドレス記憶部での複数データの管理、データアドレ
ス演算部での大量データの演算という困難な処理の問題
を解決するものである。

発明の構成 本発明は、ハツシングテーブルの内容を直接データ記憶
部のアドレス情報を表せるビットマツプテーブルに変更
することと、データ取出部の代わりにデータ記憶部から
求めるデータを取出す際にただ単にデータを取出すので
はなく、求めるデータか判断しながら取出すデータ判別
取出部を用いることにより、従来の欠点を除去するもの
である。

実施例の説明 第４図は、本発明の情報検索装置の一実施例を示す構成
図であり、２０ａ　、２０ｂは検索キーワード、２１ａ
、２１ｂはハツシングテーブル上のアドレス、２２ａ　
、２２ｂは該当するキーワードが格納されている区画内
の総てのシノニムのデータ記憶部のアドレス情報を表す
ビットマツプ情報、２３は各キーワードごとのビットマ
ツプに論理演算を加え情報の絞り込みを行なった殆ど求
めるデータのアドレス情報を表すと考えられるビットマ
ツプ情報、２４は２３のビットマツプ情報をデータ記憶
部のアドレス情報に変換したアドレス情報群、２６は求
めるデータ、２６は２４のアドレス情報を用いたデータ
記憶部からのデータの取出しを表す。更に１０はハツシ
ング処理手段を実現したハツシング処理部、１１はハツ
シング処理を実現するための情報を格納するハッシング
テーブル部、１２は各区画内のシノニムのデータ記憶部
のアドレス情報を表すビットマツプで構成されたノ・ッ
シングテーブル、１３は各キーワードの区画内のビット
マツプ同志の論理演算を行うことによりデータ記憶部の
アドレス情報の絞り込みを行なうピットマッグ演Ｎ部、
１４ｒｉ絞り込み７行なったビットマツプをデータ記憶
部のアドレス情報に変換するデータアドレス変換部、１
６は求めるデータが格納されているデータ記憶部、１５
はデータ記憶部１６のアドレス情報２４を用いて実際に
データを取出しその取り出されたデータが検索したキー
ワードのものかシノニムのものか取出されたデータをも
とにして判別し求めるデータであれば取出すデータ判別
取出部である。

第６図は、第４図のハツシングテーブル１２の実現方法
の一例であり、ビットマツプテーブルを持ったハツシン
グテーブルを示し、テーブル内のデータは従来例と全く
同じものを用いている。

Ｔはハツシング処理部で生成される７ドレス表示、Ｓは
該当するキーワードが格納されている区画内の総てのシ
ノニムのデータ記憶部の７ドレス情報を表すビットマツ
プ格納エリア、Ｕは各ビットマツプのどのビットがどの
データ記憶部のアドレスに対応するか示すアドレス表示
である。

第４図のように構成された本発明の検索装置において、
従来例と同じ成るハツシングアルゴリズムによって同じ
キーワード・データが登録されている場合の例が第５図
ａのビットマツプテーブルで構成されたハッシングテー
ブルであり、従来例と同様に第６図す、ｃに示すキーワ
ードＮ　Ｉ　Ｓ　ＨＩＭ：）Ｔ。

とＫＡＴＯＨをに関するデータを取出す場合を考える。

このとき第４図においてａをＮＩＳＨＩＭ）Ｔｏ　。

ｂをＫＡＴＯＨとする。キーワード２０ａと２０ｂがハ
ツシング処理部１０で処理されハツシングテーブルアド
レス２１ａと２１ｂ（具体的には第５図す、ｃで示した
ようｔｌｃｏｒｓとＯＡになる）となり、これらをハツ
シングテーブル部１１に入れデータ記憶部１６のアドレ
ス情報２２ａと２２ｂ（具体的には第６図す、ｃで示し
たようＫ〔０１α℃１１ｏｏ１００００１ｏ１ｏ１ｏ０
１ｏ１ｏＯｏｏ０１ｏＯ〕と〔になる）を得る。その際
、キーワードＫＡＴＯＨの方は該当する区画にシノニム
がないため求めるアドレス情報であるが、キーワードＮ
ＩＳＨＩＭＯＴＯの方は該当区画内にシノニムが多数存
在するため得られた情報はそのシノニムのデータのアド
レス情報をも含んでいる。しかしシノニムを含んだ情報
を格納することにより従来例で問題になった各種のシノ
ニムの処理用の機構（複数のパケット。

オーバーフローエリア、該当区画内で求めるキーワード
を検索する処理等）が不用となった。

次に求めたデータ記憶部１６のアドレ；（情報２２ａと
２２ｂをビットマツプ演算部１３に入れ殆ど求めるデー
タのアドレス情報を表すと考えられるビットマツプ情報
２３（具体的には第５図ｄで示したように〔ｏｌｏｏｏ
ｌｌｏｏｏｏＯｏｏＯｏｏｏＯｏＯｏｏｏｏｏｏｏｏｏ
ｏｏ）になる）を求める。この時も、第３図の場合は求
めるアドレス情報が多数個存在する場合はその論理演算
処理の実現方法が問題と成ったが、第６図の場合は各ビ
ットマツプの論理演算を繰り返すだけなだめ非常に簡単
な機構で処理を実現できうる。さらに求めた論理演算後
のビットマツプ情報２３をデータアドレス変換部１４に
入れ、ビットマツプ情報をデータ記憶部のアドレスに変
換したアドレス情報２４（具体的には第５図ｅで示した
ように（ａｌ、ｅｓｓ、ｅｓｅ）になる）を求める。最
後にこのアドレス情報２４をデータ判別取出部１６に入
れデータをデータ記憶部１８から取出し、その取り出さ
れたデータが検索したキーワードのものかシノニムのも
のか取出されたデータをもとにして判別し求めるデータ
であれは取出す処理を行い求めるデータ２６を求める。

即ち、本発明の情報検索装置においては、ハツシング処
理に不可欠と考えられていたハツシングテーブル部での
シノニム処理を行なう代わりに、ビットマツプ演算部に
おいて複数のキーワードに対するデータ記憶部のアドレ
スの論理演算を行なうことと論理、演算よっては削除す
ることができなかった若干の誤ったデータ混入を、デー
タ取出の際に取り除く機能を追加することにより、より
簡単な構成で効率的な検索方式を実現している。

これは、検索されるデータに付加されたキーワード間の
関係と同じ区画にはいるシノニムキーワード間の関係が
無相関であるため、あるデータを取出す際に、検索に使
用される複数のキーワードの情報とそのキーワードと同
じ区画に入るシノニムキーワードの情報が混在しても、
検索対象のシノニムキーワード情報は論理演算の際に無
相関であるため、振るい落とされる可能性が高いという
性質を利用している。

発明の効果 以上のように本発明は高速な検索が必要でかつキーワー
ドの追加・削除が多い場合一般的に用いられている、ハ
ツシング関数を用いた情報検索装置において、そのハフ
シングチ−プル内のシノニムキーワードの処理を、検索
されるデータに付加されたキーワード間の関係と同じ区
画にはいるシノニムキーワード間の関係が無相関である
という性質を利用して、ハツシングテーブル内に取り出
したいデータのアドレスを表すビットマツプとそのビッ
トマツプの論理演算を行なう機構を持つことでより、効
率的なハツシング処理を利用した情報検索装置を実現し
ている。また、このことは従来複雑な記憶管理機構や処
理が必要で凌）った・・ッシング処理に不可欠と考えら
れていたシノニムの管理をなくすと同時に、キーワード
が関係するデータのアドレス管理機構をも廃したより簡
単な構成の情報検索装置を実現している。

【図面の簡単な説明】

第１図はハツシング関数を用いた従来例の情報検索装置
の構成を示す図、第２図ａ　−Ｃは第１図の情報検索方
式のハツシングテーブル部の構成を示す図、第３図ａ　
−ｄは第１図の情報検索方式のデータアドレス記憶部の
構成を示す図、第４図は本発明の情報検索装置の一実施
例を示す構成図、第６図ａ　−ｅは同実施例のハツシン
グテーブル部の構成を示す図である。 １　ａ　、　１　ｂ　、　２０ａ　、　２０ｂ−−・・
−キーワード情報、２ａ、２ｂ、２１ａ、２１ｂ・・・
・・・ハツシングテーブル上のアドレス、３ａ、３ｂ・
・・・・・データアドレス記憶部内の該当キーワードの
アドレス、４ａ、４ｂ・・・・・・データ記憶部の該当
キーワードのアドレス群、６・・・・・・求めるデータ
のデータ記憶部内のアドレス、６・・・・・・求めるデ
ータ、７・・・・・・データ記憶部の該当キーワードの
アドレス群の取出し、８・・・・・・求めるデータの取
出し、２２ａ、２２ｂ・・・・・・データ記憶部のアド
レス情報を表すビットマツプ情報、２３・・・・・・論
理演算後のビットマッグ情報、２４・・・・・・データ
記憶部のアドレス情報群、２６・・・・・・求めるデー
タ、２６・・・・・・データ記憶部からのデータの取出
し、Ａ・・・・・・ハツシング処理部、Ｂ・・・・・・
ハツシングテーブル部、Ｃ・・・・・・ハツシングテー
ブル本体、Ｄ・・・・・・オーバーフローエＩＪ７、Ｅ
・・・・・・データアドレス取出部、Ｆ・・・・・・デ
ータアドレス記憶部、Ｇ・・・・・・データアドレス演
算部、Ｈ・・・・・・データ取出部、工・・・・・・デ
ータ記憶部、Ｌｌ・・・・・・ハツシングテーブルのア
ドレス表示、Ｍｌ・・・・・・キーワード情報格納エリ
ア、Ｎ１・・・・・・データアドレス記憶部のアドレス
情報格納エリア、０１・・・・・・オーバーフローエリ
ア内の格納位置を示すエリア、Ｌ２・・・・・・オーバ
ーフローエリアのアドレス表示、Ｎ２・・・・・・キー
ワード情報格納エリア、Ｎ２・・・・・・データアドレ
ス記憶部のアドレス情報格納エリア、０２・・・・・・
次に用いるオーバーフローエリア内の格納位置を示すエ
リア、Ｐ・・・、・・アドレス表示、Ｑ・・・・・・デ
ータ記憶部のアドレス情報格納エリア、Ｒ・・・・・・
次データアドレス情報格納位置表示エリア、Ｓ・・・・
・・区画内のすべてのシノニムのデータ記憶部内のアド
レス情報を表すビットマツプ格納エリア、Ｔ・・・・・
・アドレス表示、Ｕ・・・・・・データ記憶部のどのア
ドレスに対応するかの表示、１０・・・・・・ハツシン
グ処理部、１１・・・・・・ハツシングチープル部、１
２・・・・・・ビア）マツプテーブル状のハツシングテ
ーブル、１３・・・・・・ビットマツプ演算部、１４・
・・・・・データアドレス変換部、１５・・・・・・デ
ータ判別取出部、１６・・・・・・データ記憶部。

Claims (1)

【特許請求の範囲】
1. 検索されるデータと前記検索されるデータを取出すため
   の検索キーワードとを格納した外部記憶装置を有し、前
   記データを外部記憶装置から取出すために、前記検索キ
   ーワードをハッシング関数を用いてハッシングテーブル
   上のアドレスに変換するハッシング処理手段を有し、前
   記ハッシング処理手段で求めたハッシングテーブル上の
   該当位置には前記検索されるデータが格納されたブロッ
   クのアドレスを表すビットマップテーブルが格納されて
   おり、複数の検索キーワードに対しそれぞれのビットマ
   ップテーブルを取出すことができ、前記取出されたビッ
   トマップテーブルの論理演算を行なうことにより前記検
   索されるデータが格納されたブロックのアドレスを絞り
   込む機能を持つビットマップ演算手段を有し、前記ビッ
   トマップ演算手段で作成されたビットマップを前記検索
   されるデータの格納位置アドレスに変換するアドレス変
   換手段を有し、前記アドレス変換手段により生成された
   アドレスにより前記検索されるデータ及び検索キーワー
   ドを取出しそのデータが求める検索キーワードを含むか
   判断し含む場合はそのデータを取出すデータ判別取出手
   段を有することを特徴とする情報検索装置。