JPH08147328A - 文書検索方法及び装置 - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】 文書データベースへの登録時に行われるイン
デックスの追加処理を高速化することにより、文書デー
タベースへの登録処理を高速に行う。 【構成】 文書から抽出したキーワードに基づき作成す
るインデックスが格納される二次記憶装置、例えば、磁
気ディスク上のファイルを所定数のブロックに分割して
おき、各ブロックに格納されるキーワードに対応するイ
ンデックスのサイズがほぼ均等になるようにキーワード
をブロックに割り付ける。文書の登録時に、ブロックに
追加又は更新が生じたインデックスの個数が所定数以上
のときは、該ブロックを磁気ディスクから主メモリへ読
込み、インデックス追加処理を主記憶上で行い、これを
磁気ディスクに格納し、所定数未満のときは追加が生じ
たインデックスのみを磁気ディスクから主メモリへ読込
み、インデックス追加処理をメモリ上で行い、これを磁
気ディスクに格納する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、インデックスを使用し
た文書検索方法及び装置に係り、データベース、文書フ
ァイリングシステムおよびＤＴＰ（Ｄｅｓｋ Ｔｏｐ
Ｐｕｂｌｉｓｈｉｎｇ）システムなどに適用されるもの
である。

【０００２】

【従来の技術】情報処理システムでは、データベースに
格納されている文字列データの集まりからなる文書の中
から、検索者の探したいある特定の言葉、すなわち質問
語、を含む全ての文書を探し出すことが一つの重要な処
理となっている。このような文書を検索するための方法
として、インデックスを使用したインデックス検索方式
が良く知られている。この方式は“情報検索”（中原
著、電子通信情報学会出版、１９７４）ｐｐ.２０３−
２０７（以下、公知例１と呼ぶ）や“ＤＯＣＵＭＥＮＴ
ＤＡＴＡＢＡＳＥ”（Ｇ．Ｊａｍｅｓ著、Ｖａｎ Ｎ
ｏｓｔｒａｎｄ Ｒｅｉｎｈｏｌｄ Ｃｏ．、１９８
５）ｐｐ.８７−９４に具体的に記載されている。ここ
で取り上げられているインデックスは、キーワードが出
現する文書の文書番号で構成されている。これらのイン
デックス検索方式では、質問語と一致するキーワードの
インデックスを参照するだけで、そのキーワードを含む
文書が分かるため高速な検索が可能である。

【０００３】上記公知例１に記載されているインデック
スの例を図２に示す。インデックスは、文書から抽出さ
れたキーワードに対応して、キーワード番号とキーワー
ドが出現する文書の文書番号が格納される構成となって
いる。本例では、キーワード“コア”、“ディスク”、
“コンピュータ”および“ＩＲ”に対応するインデック
スが作成され、磁気ディスク上のファイルに格納されて
いることを想定している。検索の際には、質問語として
“コア”、“ディスク”、“コンピュータ”および“Ｉ
Ｒ”が指定されたときのみ、このインデックスの中のそ
れぞれのキーワードが出現する文書の文書番号がインデ
ックスが格納されているファイル（以後、インデックス
ファイルと呼ぶ）から読み出される。すなわち、質問語
が“コア”の場合には文書番号１，４，質問語が“ディ
スク”の場合には文書番号４、質問語が“コンピュー
タ”の場合には文書番号１，２，４，質問語が“ＩＲ”
の場合には文書番号２のように検索結果として文書番号
が出力される。新たな文書をデータベースへ登録する際
には、その文書に出現したキーワードが抽出され、この
キーワードが出現した文書の文書番号が、そのキーワー
ドに対応するインデックスに追加登録される。このよう
に文書からキーワードを抽出する技術は、“自動索引付
け研究の動向”（諸橋著、情報処理学会誌、Ｖｏｌ.２
５、Ｎｏ.９、１９８４）や“ＤＯＣＵＭＥＮＴ ＤＡ
ＴＡＢＡＳＥ”（Ｇ．Ｊａｍｅｓ、Ｖａｎ Ｎｏｓｔｒ
ａｎｄＲｅｉｎｈｏｌｄ Ｃｏ．、１９８５）ｐｐ．８
７−９４に記載されている。これらのキーワード抽出技
術を用いて抽出されたキーワードに対応するインデック
スの追加処理例を図３に示す。本例では、登録対象の文
書の文書番号は５であり、この文書から“コア”、“コ
ンピュータ”および“ＩＲ”が抽出されたことを想定す
る。このインデックスでは“コア”、“コンピュータ”
および“ＩＲ”に対応するインデックスにそれぞれ文書
番号５が追加されている。このようにして、抽出された
キーワードに対応するインデックスの追加処理が行われ
ることにより、文書の登録処理が実現される。

【０００４】

【発明が解決しようとする課題】“情報検索”（中原
著、電子通信情報学会出版、１９７４）ｐｐ.１２０−
１２８によれば、インデックスが格納される記憶装置と
しては、ランダムアクセスを行うことができ、大容量で
安価な磁気ディスクなどの二次記憶装置の使用が一般的
とされている。磁気ディスクに格納されているインデッ
クスの追加処理では、追加の対象となったキーワードに
対応するインデックスが独立にアクセスされる。すなわ
ち、インデックスの追加処理は、磁気ディスク上の複数
のインデックスが飛び飛びにアクセス（以下、ランダム
アクセスと呼ぶ）されることになる。ワークステーショ
ンの一般的なオペレーティングシステムにおいては、磁
気ディスクへのアクセスが論理ブロックと呼ばれる単位
で行われる。ここでは論理ブロックのサイズとして、上
記オペレーティングシステムで使われている８、１９２
バイト（以後、８ＫＢと省略する）を想定する。ただ
し、磁気ディスクへの書き込みは、８ＫＢ単位で行われ
ない場合もある。例えば、インデックスの追加処理で書
き込む文書番号のサイズを一文書番号当たり４バイトと
想定すると、一文書を登録する場合には論理ブロックよ
り少ない８ＫＢ未満のデータの書き込みとなる。このよ
うな場合、上記オペレーティングシステムでは、書き込
み対象となっている論理ブロックを磁気ディスクから上
記オペレーティングシステムの主記憶上のバッファエリ
アに一旦読み込む。次に、書き込む対象のデータをバッ
ファエリア内の論理ブロックの所定の場所に書き込むこ
とにより論理ブロックを更新する。その後で、この論理
ブロックを再び磁気ディスクに書き込む。このようにし
て、論理ブロックより少ないデータの磁気ディスクへの
書き込みを実現している。

【０００５】このときの磁気ディスクの動作の一例を図
４を用いて説明する。まず、磁気ディスクのヘッドを、
読み出し対象の論理ブロックの先頭位置に位置決めする
ためのヘッドのシーク処理と回転待ち処理が行われ、次
に読み出し対象となる論理ブロックの読み出し処理が行
われる。その後、前記論理ブロックの更新（文書番号の
追加処理）が行われ、再び磁気ディスクのヘッドを読み
出し対象となった論理ブロックの位置に位置決めするた
めのヘッドのシーク処理と回転待ち処理が行われ、その
後、論理ブロックの磁気ディスクへの書き込み処理が行
われる。

【０００６】本図の各処理時間の値は一般的な３.５イ
ンチの磁気ディスクのものであり、平均的なシーク時間
（以後、平均シーク時間と呼ぶ）としては約１４ｍｓ、
平均的な回転待ち時間（以後、平均回転待ち時間と呼
ぶ）としては約１７ｍｓ、一論理ブロック当たりの読み
出し時間および書き込み時間としては約４ｍｓを想定し
ている。また、バッファエリア上の論理ブロックに４バ
イトの文書番号を書き込む時間としては０.００１ｍｓ
を想定している。本例では、論理ブロックより少ないデ
ータの磁気ディスクへの書き込み処理に合計７０ｍｓ掛
かる。本図のタイムチャートより磁気ディスクからの読
み出し処理および書き込み処理に費やされる時間が８ｍ
ｓであるのに対して、ヘッドを位置決めするためのシー
ク処理および回転待ち処理に費される時間は６２ｍｓと
８倍程度長く掛かっていることが分かる。すなわち、磁
気ディスクへの読み出しや書き込みの処理速度は２ＭＢ
／ｓなのに対し、シーク処理や回転待ち処理の時間を含
めた全体の実効的な処理速度は約０.１３ＭＢ／ｓとな
り、磁気ディスクの読み出しおよび書き込み性能が引き
出せない状況となっている。

【０００７】このため、文書の登録時に行われるインデ
ックスの追加処理において、追加処理が発生したキーワ
ードの個数分磁気ディスクのランダムアクセスが発生す
ることにより磁気ディスクの実効的な処理速度が低下
し、インデックスの追加に時間が掛かることになる。つ
まり、インデックスを用いた文書検索方式では、文書の
登録に時間が掛かるという問題がある。本発明の目的
は、登録時に行われるインデックスの追加処理を高速化
し、登録時間を短縮することにある。

【０００８】

【課題を解決するための手段】上記課題を解決するた
め、本発明は、文書からキーワードを抽出し、これに基
づいてインデックスを作成し、検索時に質問語と一致し
たキーワードに対応するインデックスを参照して検索を
行う文書検索方法において、前記インデックスを二次記
憶装置上のファイルに格納するとともに、該ファイルを
所定数のブロックに分割しておき、各ブロックに格納さ
れるインデックスのサイズがほぼ均等になるようにキー
ワードを該ブロックに割り付け、文書の登録時に、前記
ブロックに追加または更新が発生したインデックスの個
数が所定数以上の場合には、該ブロックを二次記憶装置
から主記憶上へ読み込むとともに、該ブロック内のイン
デックスに対応するキーワードについて、インデックス
の追加処理を主記憶上で行い、追加処理された該ブロッ
クを二次記憶装置へ格納し、所定数未満の場合には、該
インデックスを二次記憶装置から主記憶上へ読み込むと
ともに、該インデックスに対応するキーワードについ
て、インデックスの追加処理を主記憶上で行い、追加処
理された該インデックスを二次記憶装置へ格納するよう
にしている。また、キーワードのブロック割り付けに際
して、ブロックに割り付けられたキーワードについて、
インデックスが作成される全ての文書の内、該キーワー
ドの出現文書数を算出し、各キーワード毎に算出した出
現文書数の総和をブロック毎に算出し、各ブロックにお
ける出現文書数の総和が各ブロックにおいてほぼ均等に
なるようにキーワードのブロック割り付けを行うように
している。さらに、文書からキーワードを抽出し、これ
に基づいてインデックスを作成し、検索時に質問語と一
致したキーワードに対応するインデックスを参照して検
索を行う文書検索装置において、前記インデックスを二
次記憶装置上のファイルに格納するとともに、該ファイ
ルを所定数のブロックに分割する手段と、各ブロックに
格納されるインデックスのサイズがほぼ均等になるよう
にキーワードを該ブロックに割り付ける割り付け手段
と、文書の登録時に、前記ブロックに追加または更新が
発生したインデックスの個数が所定数以上か否か判定す
る手段と、判定結果が所定数以上のとき該ブロックを二
次記憶装置から主記憶上へ読み込み、該ブロック内のイ
ンデックスに対応するキーワードについてインデックス
の追加処理を主記憶上で行い、追加処理された該ブロッ
クを二次記憶装置へ格納する手段と、所定数未満のとき
該インデックスを二次記憶装置から主記憶上へ読み込
み、該インデックスに対応するキーワードについて、イ
ンデックスの追加処理を主記憶上で行い、追加処理され
た該インデックスを二次記憶装置へ格納する手段を備え
るようにしている。また、前記割り付け手段は、ブロッ
クに割り付けられたキーワードについて、インデックス
が作成される全ての文書の内、該キーワードの出現文書
数を算出し、各キーワード毎に算出した出現文書数の総
和をブロック毎に算出し、各ブロックにおける出現文書
数の総和が各ブロックにおいてほぼ均等になるようにキ
ーワードのブロック割り付けを行うようにしている。

【０００９】

【作用】上記手段により、全ての文書からキーワードを
抽出し、二次記憶装置上の所定数のブロックの各ブロッ
クのインデックスサイズがほぼ均等になるように、キー
ワードをブロックに割り付けることができ、文書の登録
時に、インデックスを格納するブロック毎に、該当する
抽出キーワードが所定数以上の場合には、そのブロック
を磁気ディスクからメモリ上に読み込むとともに該当す
る抽出キーワードに対するインデックスの追加処理メモ
リ上で一括して行い、これを磁気ディスクへ書き込むこ
とにより、磁気ディスクへのアクセス回数を低減し、所
定数未満の場合には該当する抽出キーワードに対応する
インデックスのみメモリ上に読み込むとともにそのイン
デックスの追加処理を行い、これを磁気ディスクへ書き
込むことにより、磁気ディスクへのアクセスデータ量を
最小化することができるため、非常に高速なインデック
ス追加処理が可能となり、文書データベースへの高速な
登録処理を実現することができる。

【００１０】

【実施例】まず、本発明の原理を以下に説明する。初期
設定として、インデックスを格納するインデックスファ
イルのエリアとして所定サイズ分を磁気ディスク上に確
保するとともに、これを所定数のブロック（論理ブロッ
クではない）に分割する。次に、各ブロックに格納され
るインデックスの容量（インデックスのサイズ）がほぼ
均等になるように、インデックスに対応するキーワード
を各ブロックに割り付ける。文書の登録時には、まず、
登録文書からキーワードを抽出し、そのキーワードとそ
れが出現した文書の文書番号を主記憶へ格納する。次に
上記ブロック毎に、そこに割り付けられているキーワー
ドが、いくつ抽出されているかを調べる。所定数未満の
場合には、従来と同様に、各ブロック毎に抽出されたキ
ーワードに対応するインデックスを磁気ディスクから主
記憶へ読み込む。次に、主記憶に読み込まれているイン
デックスの末尾に、そのキーワードが出現した文書の文
書番号を追加し、磁気ディスクに再び格納する。所定数
以上の場合には、まず、該当ブロックを磁気ディスクか
ら主記憶へ読み込む。次に、抽出されたキーワードの中
で該ブロックに割り付けられているものについてのみ、
主記憶に読み込まれている該ブロック内の該キーワード
に対応するインデックスの末尾に、そのキーワードが出
現した文書の文書番号を追加する。その後、このブロッ
クを磁気ディスクに再び格納する。この一連の処理を、
抽出されたキーワードが割り付けられている全てのブロ
ックに対して行うことにより、登録文書から抽出された
キーワードのインデックスへの追加処理を行う。

【００１１】以上のように、抽出されたキーワードが所
定数以上含まれるブロックに関しては、磁気ディスク上
のブロックを１度だけ主記憶に読み込み、新たなキーワ
ードに対する追加処理を行った後に、これを磁気ディス
クに書き込むだけで複数のインデックスの追加処理を実
現できるため、従来のようにキーワード毎に磁気ディス
クから該当するインデックスを読み込み、そのキーワー
ドに対する追加処理を行った後に、これを磁気ディスク
へ書き込む場合に比べ大幅にインデックスの追加処理に
掛かる時間を削減することができる。

【００１２】以上説明した原理を、さらに具体例を用い
て説明する。本例で用いるインデックスファイルの例を
図５に示す。本インデックスファイルは、図２に示すイ
ンデックスファイルをブロック１とブロック２の二つに
分割し、磁気ディスクに格納したものである。さらに、
ブロックに含まれるインデックスのサイズがほぼ均等に
なるように、ブロック１にはキーワード“コア”、“デ
ィスク”および“ＩＲ”を、ブロック２にはキーワード
“コンピュータ”を割り付け、対応するブロックにイン
デックスを格納している。

【００１３】このインデックスは、検索の際には、ブロ
ックを意識することなく従来と同様に検索処理が行われ
る。質問語として“コア”、“ディスク”、“コンピュ
ータ”および“ＩＲ”が指定されたときのみ、それぞれ
のキーワードが出現する文書の文書番号がインデックス
ファイルから読み出される。すなわち、質問語が“コ
ア”の場合には文書番号１，４，質問語が“ディスク”
の場合には文書番号４、質問語が“コンピュータ”の場
合には文書番号１，２，４，質問語が“ＩＲ”の場合に
は文書番号２のように検索結果として文書番号が出力さ
れる。

【００１４】新たな文書をデータベースへ登録する際に
は、図６に示すように上記ブロックを意識した処理を行
う。以下、詳細にその手順を説明する。まず、登録対象
の文書からキーワードとして、“コア”、“ディスク”
および“ＩＲ”が抽出されたものとし、さらにこの文書
の文書番号として文書番号５を想定する。抽出されたキ
ーワードのブロックの割り付けとしては、ブロック１に
はキーワード“コア”、“ディスク”および“ＩＲ”
が、ブロック２には“コンピュータ”が割り付けられて
いる。これらのキーワードの中で文書５から抽出された
キーワードとしては、ブロック１にキーワード“コ
ア”、“ディスク”および“ＩＲ”の三つが該当する。
このため、まず、ブロック１を主記憶上に読み込む。次
にブロック１に格納されているキーワード“コア”、
“ディスク”および“ＩＲ”に対応するインデックスの
末尾にこれらのキーワードが出現する文書の文書番号で
ある５をそれぞれ追加する。その後、主記憶上に格納さ
れているブロック１を磁気ディスク上のインデックスフ
ァイルに書き込む。ブロック２についてはこの中に割り
付けられたキーワードに該当するものが文書５から抽出
されていないためインデックスの追加処理は行わない。
このようにして、文書の登録処理が行われる。

【００１５】上記ブロック１のインデックス追加処理の
タイムチャートを図７に示す。本例では、磁気ディスク
として一般的な３.５インチの磁気ディスクを使用し、
論理ブロックのサイズとしてワークステーションの一般
的なオペレーティングシステムで使われている８ＫＢを
使用し、インデックスを格納するブロックのサイズとし
て８論理ブロックを使用すること想定する。また、磁気
ディスクのシーク時間および回転待ち時間としては、平
均シーク時間および平均回転待ち時間を想定する。さら
に、磁気ディスクにおける平均シーク時間、平均回転待
ち時間、一論理ブロックの読み出し時間および一論理ブ
ロックの書き込み時間には、それぞれ、約１４ｍｓ、約
１７ｍｓ、約４ｍｓおよび約４ｍｓを想定する。上記の
値を用いて、本図のタイムチャートの流れを説明する。
本例では、まず、ブロック１をバッファエリアへ読み出
すときに磁気ディスクへのアクセスが発生し、シーク処
理と回転待ち処理により磁気ディスクのヘッドがブロッ
ク１の先頭に位置決めされる。この間、平均シーク時間
１４ｍｓと平均回転待ち時間１７ｍｓが費やされる。次
に、ブロック１を構成する論理ブロック、この場合八つ
の論理ブロックとする、がバッファエリアに読み込まれ
る。この際、１論理ブロック分の読み出し時間の８倍の
３２ｍｓが費やされる。ここで、バッファエリアに読み
出されたブロック１に格納されているキーワード“コ
ア”、“ディスク”および“ＩＲ”に対応するインデッ
クスの末尾にこれらのキーワードが出現する文書の文書
番号である５がそれぞれ追加される。したがって、ブロ
ック１に３回の文書番号の追加が発生する。このときの
バッファエリア上の一つのインデックスに４バイトの文
書番号を書き込む時間として０.００１ｍｓを想定す
る。ここでは、３回の文書番号の追加が発生するため３
倍の０.００３ｍｓを要するが、他の処理時間に比べ無
視できるほど小さい。その後、インデックスの追加処理
が行われたブロック１を、磁気ディスクに書き込む。こ
のとき、シーク処理と回転待ち処理により磁気ディスク
のヘッドが所定の位置に位置決めされる。その間、平均
シーク時間１４ｍｓと平均回転待ち時間１７ｍｓが費や
される。この後に、ブロック１を構成する八つの論理ブ
ロックが磁気ディスクに書き込まれ、１ブロック分の書
き込み時間の８倍の３２ｍｓが費やされる。以上の処理
により、本例のインデックスの追加に合計１２６ｍｓが
費やされることになる。これは、一キーワード当たり平
均４２ｍｓとなる。従来のように、キーワード毎に磁気
ディスク上のインデックスへの追加処理を行ったときに
は、前述した図４のように、一キーワード当たり７０ｍ
ｓ掛かったものが、本発明のようにブロック単位にまと
めてインデックスの追加処理を行うことにより４０％程
度文書の登録時間を短縮することが可能となる。一般の
文書を登録する際には、登録キーワードの個数が本例の
数十倍にもなるため、本発明のブロック単位でのインデ
ックスの追加処理の効果は更に大きくなる。

【００１６】以上説明したように、本発明によれば、所
定数以上の追加登録キーワードが含まれるブロックにお
けるインデックスの追加処理を一括して行うことによ
り、磁気ディスク上のブロックを１度主記憶に読み込む
だけで複数のインデックスの追加処理が実行できるた
め、文書データベースへの高速な登録処理を実現するこ
とができる。

【００１７】以下、本発明の実施例を説明する。本発明
が適用された文書検索システムの構成について図１を用
いて説明する。本システムは、ディスプレイ１０１、キ
ーボード１０２、ＣＰＵ１０３、メモリ１０４、磁気デ
ィスク１０５およびフロッピーディスクドライブ（ＦＤ
Ｄ）１０６から構成される。ディスプレイ１０１、キー
ボード１０２、メモリ１０４、磁気ディスク１０５およ
びＦＤＤ１０６は、ＣＰＵ１０３よりバスを介してアク
セスされる。磁気ディスク１０５には、インデックスフ
ァイル８０００が格納される。メモリ１０４には、シス
テム制御プログラム５０００、検索インタフェースプロ
グラム６０００、登録制御プログラム２０００、検索制
御プログラム３０００、キーワード割り付けプログラム
２１００、インデックス作成登録プログラム２２００お
よびインデックス検索プログラム３１００がロードさ
れ、ワークエリア４０００が確保される。本文書検索シ
ステムの文書データベースに登録される文書は、フロッ
ピーディスク１０７に格納され、ＦＤＤ１０６を介して
ＣＰＵ１０３よりアクセスされる。

【００１８】本システムでは、電源投入時ＣＰＵ１０３
によりシステム制御プログラム５０００が起動され、シ
ステム制御プログラム５０００の制御のもとに登録制御
プログラム２０００および検索制御プログラム３０００
が起動される。まず、このような構成の本システムにお
ける文書の登録処理の概略について説明する。ユーザが
キーボード１０２から入力した指示に従って、システム
制御プログラム５０００が登録制御プログラム２０００
を起動する。登録制御プログラム２０００では、最初、
文書を登録する前に、ユーザがキーボード１０２から入
力した指示に従い、キーワード割り付けプログラム２１
００を起動し、インデックスファイルの初期設定を行
う。まず、ユーザがキーボード１０２から入力した指示
に従い、インデックスを格納するインデックスファイル
８０００を所定ブロック数分磁気ディスク１０５上に確
保するとともに、これを指定された数のブロックに分割
する。そして、各ブロックにキーワードを割り付けるた
めの所定数の文書（以後、種文書と呼ぶ）がＦＤＤ１０
６を介してフロッピーディスク１０７からメモリ１０４
のワークエリア４０００に読み込まれる。種文書として
は、例えば１０万件の新聞記事ＤＢを作成する場合に
は、同じ種類の文書、すなわち新聞記事を数百件〜数千
件程度登録する。次に、ワークエリア４０００に読み込
まれた種文書から検索に必要な言葉をキーワードとして
抽出し、そのキーワードの出現文書数を算出する。この
キーワードの出現文書数の総和が、各ブロック間でほぼ
均等になるようにキーワードを各ブロックに割り付け
る。その後、登録制御プログラム２０００では、インデ
ックス作成登録プログラム２２００を起動する。

【００１９】インデックス作成登録プログラム２２００
では、ユーザがキーボード１０２から入力した指示に従
い、フロッピーディスク１０７に格納された登録対象の
文書を、ＦＤＤ１０６を介してメモリ１０４のワークエ
リア４０００に読み込む。この登録文書から検索に必要
な言葉がキーワードとして抽出され、インデックスファ
イル８０００の該当ブロックにキーワードと文書番号、
あるいは文書番号が登録される。

【００２０】次に、本システムにおける文書の検索動作
の概略について説明する。ユーザがキーボード１０２か
ら入力した指示に従い、システム制御プログラム５００
０は検索制御プログラム３０００と検索インタフェース
プログラム６０００を起動する。その後、ユーザがキー
ボード１０２から入力した質問語は、検索インタフェー
スプログラム６０００に入力され、検索制御プログラム
３０００に送られる。検索制御プログラム３０００で
は、インデックス検索プログラム３１００を起動すると
ともに本プログラムへ前記質問語を送る。インデックス
検索プログラム３１００では、受け取った質問語に対応
するインデックスから文書番号を読み出し、検索結果と
して検索制御プログラム３０００へ送出する。本検索結
果は、検索インタフェースプログラム６０００へと送ら
れ、検索結果文書番号としてディスプレイ１０１に表示
される。

【００２１】次に、キーワード割り付けプログラム２１
００の構成とキーワード割り付け処理について図８を用
いて説明する。キーワード割り付けプログラム２１００
は、インデックス分割ステップ２１０５、種文書数分繰
返しステップ２１１０、種文書読み込みステップ２１２
０、キーワード抽出ステップ２１３０、出現文書数カウ
ントステップ２１４０およびキーワード割り付けステッ
プ２１５０から構成される。まず、インデックス分割ス
テップ２１０５では、ユーザから指定されたブロック数
をキーボード１０２から読み込む。次にインデックスフ
ァイル８０００として、指定のブロック数分のエリアを
確保するとともに、これを指定ブロック数に均等分割す
る。次に、種文書読み込みステップ２１２０では、ＦＤ
Ｄ１０６を介して種文書を１文書分読み込みワークエリ
ア４０００に格納する。さらに、キーワード抽出ステッ
プ２１３０では、読み込まれた種文書からキーワードと
なる言葉を抽出し、この抽出されたキーワードをワーク
エリア４０００に格納する。この文書からキーワードを
抽出する技術は、日本語文書については“自動索引付け
研究の動向”（諸橋著、情報処理学会誌、Ｖｏｌ.２
５、Ｎｏ.９、１９８４）に記載されており、英語文書
については“ＤＯＣＵＭＥＮＴ ＤＡＴＡＢＡＳＥ”
（Ｇ．Ｊａｍｅｓ、Ｖａｎ Ｎｏｓｔｒａｎｄ Ｒｅｉ
ｎｈｏｌｄ Ｃｏ．、１９８５）ｐｐ．８７−９４に記
載されている。本実施例では、これらのキーワード抽出
技術をそのまま利用する。出現文書数カウントステップ
２１４０では、抽出されたキーワードが出現する文書数
をカウントし、キーワードに対応させて、ワークエリア
４０００に格納する。種文書数分繰返しステップ２１１
０では、全ての種文書についてステップ２１２０からス
テップ２１４０までの一連の処理を繰り返す。全ての種
文書が処理された後、キーワード割り付けステップ２１
５０では、出現文書数の和がほぼ均等になるように、抽
出したキーワードを各ブロックに割り付け、そのブロッ
ク番号をキーワードに対応する形でワークエリア４００
０に格納する。

【００２２】このように、種文書から抽出したキーワー
ドの出現文書数を算出することにより、文書データベー
スのインデックスサイズが予測できる。つまり、種文書
から抽出したキーワードに対応するインデックスのサイ
ズは、種文書から抽出したキーワードの出現文書数と文
書番号サイズの積により算出でき、これに文書データベ
ースの登録件数と種文書数（サンプリングされた種文書
数である）の比を掛けることにより、文書データベース
におけるインデックスサイズが予測できるからである。
また、文書データベースに登録する文書数が増加しブロ
ックに割り付けられた全てのインデックスのサイズの和
が、ブロック間でほぼ均等でなくなった場合には、この
文書データベースに登録した全ての文書の中から種文書
の候補を乱数抽出などの手法を使い、全文書数の数％程
度抽出する。この種文書を基に、再度、ブロックへのキ
ーワードの割り付けを行う。このキーワードの割り付け
に基づき、文書データベースに登録されている全ての文
書を再登録することにより、ブロックに割り付けたイン
デックスのサイズの和をブロック間でほぼ均等にするこ
とが可能となる。他の方法として、ブロックに割り付け
られているインデックスのサイズの和が他のブロックに
比べ多いブロックについて、これに割り付けられている
キーワードを、サイズの小さいブロックに割り付け直す
ことにより、インデックスのサイズの和をブロック間で
ほぼ均等にすることも可能である。ブロックへキーワー
ドを割り付ける際の指標として、キーワードの文書出現
数の他に、キーワードそのものの出現数を使用したり、
キーワードの種類数を使用することも可能である。以上
の処理を行うことにより、全ての種文書からキーワード
を抽出し、各ブロックのインデックスサイズがほぼ均等
になるように、キーワードをブロックに割り付けること
ができる。

【００２３】さらに、上記キーワード割り付けステップ
２１５０におけるキーワード割り付け処理について、図
９を用いて詳細に説明する。キーワード割り付けステッ
プ２１５０は、抽出キーワードソートステップ２１５
２、ブロック番号初期設定ステップ２１５３、抽出キー
ワード繰返しステップ２１５４、ブロック繰返しステッ
プ２１５５、ブロックサイズ判定ステップ２１５６、キ
ーワード設定ステップ２１５７、ブロック番号カウント
ステップ２１５８およびジャンプステップ２１５９から
構成されている。まず、抽出キーワードソートステップ
２１５２で、ワークエリア４０００に格納されている抽
出キーワードを、抽出キーワードに対応して格納されて
いる抽出キーワードの出現文書数を降順にソートする。
次に、ブロック番号初期設定ステップ２１５３では、最
初に処理するブロック番号として最初のブロック番号で
ある１を設定する。さらに、ブロックサイズ判定ステッ
プ２１５６では、抽出キーワードをブロックに割り付け
る場合を想定し、本ブロックに割り付けられるインデッ
クスのサイズの和を算出し、所定のブロックサイズを越
えるかどうか判定する。越えない場合のみ、まず、キー
ワード設定ステップ２１５７を実行し、本ブロックに抽
出キーワードを割り付ける。次に、ブロック番号カウン
トステップ２１５８を実行し、処理対象となっているブ
ロックのブロック番号に１を加え、次に処理するブロッ
クのブロック番号を設定する。このカウントアップにお
いて、ブロック番号が最終番号までカウントアップされ
た場合には、最初のブロック番号の１に戻ることにす
る。さらに、ジャンプステップ２１５９によりブロック
繰返しステップ２１５５における繰返し処理を打ち切
り、Ｌ１以降のステップを実行する。ここでは、抽出キ
ーワード繰返しステップ２１５４を実行する。ブロック
繰返しステップ２１５５では、ステップ２１５６からス
テップ２１５９までの処理をブロック番号から順に全て
のブロックについて繰返し行う。抽出キーワード繰返し
ステップ２１５４では、ステップ２１５５からステップ
２１５９までの処理を、全ての抽出キーワードについて
繰返し行う。以上の一連の処理により、出現文書数の最
も多い抽出キーワードから順に、各ブロックへ割り付け
ることができるため、各ブロックにインデックスサイズ
をほぼ均等に割り付けることが可能となる。

【００２４】次に、インデックス作成登録プログラム２
２００の構成と文書登録処理について図１０を用いて説
明する。インデックス作成登録プログラム２２００は、
文書番号取得ステップ２２０５、文書数分繰返しステッ
プ２２１０、登録文書数読み込みステップ２２２０、キ
ーワード抽出ステップ２２３０、ブロック番号対応ステ
ップ２２４０、文書番号カウントステップ２２４５、ブ
ロック数分繰返しステップ２２５０、抽出キーワード数
判定ステップ２２６０、ブロック単位インデックス追加
ステップ２２７０、キーワード数分繰返しステップ２２
８０およびキーワード単位インデックス追加ステップ２
２９０から構成される。まず、文書番号取得ステップ２
２０５では、ユーザがキーボード１０２から入力した登
録文書の最初の文書番号と登録文書数を読み込む。次
に、登録文書読み込みステップ２２２０で、登録対象の
文書をＦＤＤ１０６を介して、１文書分読み込みワーク
エリア４０００に格納する。その後、キーワード抽出ス
テップ２２３０で、キーワード割り付けプログラム２１
００におけるキーワード抽出ステップ２１３０と同様
に、読み込まれた登録文書からキーワードとなる言葉を
抽出する。この抽出キーワードをワークエリア４０００
に格納する。ブロック番号対応ステップ２２４０では、
キーワード割り付けステップ２１５０でキーワードに対
応する形でワークエリア４０００に格納したブロック番
号を調べることにより、抽出キーワードが割り付けられ
たブロックのブロック番号を取得し、そのブロック番号
を抽出キーワードに対応させ、ワークエリア４０００に
格納する。もし、抽出キーワードがどのブロックにも割
り付けられていない場合には、格納されているインデッ
クスのサイズの和が最も小さいブロックにそのキーワー
ドを割り付け、このブロック番号を抽出キーワードに対
応した形でワークエリア４０００に格納する。その後、
文書番号カウントステップ２２４５で、文書番号をイン
クリメントし、次の登録文書の処理に備える。文書数分
繰返しステップ２２１０では、登録文書数回分、ステッ
プ２２２０からステップ２２４５のキーワード抽出処理
を繰り返す。その後、抽出キーワード数判定ステップ２
２６０では、最初のブロック番号であるブロック１につ
いて、抽出されたキーワードのうちブロック１に割り付
けられている数をカウントし、所定数Ｎ以上か否かを調
べる。この所定数Ｎは、使用磁気ディスク、使用計算機
等の性能等を考慮して最適となる値をユーザが指定す
る。カウント数が所定数Ｎ以上であれば、次のブロック
単位インデックス追加処理２２７０を実行する。ブロッ
ク単位インデックス追加処理２２７０では、ブロック１
をワークエリア４０００に読み込み、ブロック１に割り
付けられている全ての抽出キーワードについて一括して
インデックスの追加処理を行う。所定数Ｎに達しない場
合は、キーワード単位インデックス追加ステップ２２９
０を実行する。キーワード単位インデックス追加ステッ
プ２２９０では、インデックスファイル８０００に格納
されているブロック１の中に存在する上記抽出キーワー
ドに対応するインデックスのみをワークエリア４０００
に読み込み、そのインデックスに対応する抽出キーワー
ドが出現する文書の文書番号を上記インデックスに追加
するとともに再びインデックスファイル８０００に書き
込む。さらに、キーワード数分繰返しステップ２２８０
では、抽出キーワードの中でブロック１に割り付けられ
ているもの全てについてインデックスの追加処理が終了
するまで、キーワード単位インデックス追加ステップ２
２９０を繰返し実行する。ブロック数分繰返しステップ
２２５０では、全てのブロックについてステップ２２６
０からステップ２２９０を繰返し実行し、インデックス
の追加処理を行う。本実施例では、このようにして新た
な文書の追加登録を実現する。

【００２５】さらに、前述のブロック単位インデックス
追加処理ステップ２２７０について、図１１を用いて詳
細に説明する。ブロック単位インデックス追加処理ステ
ップ２２７０は、ブロック読み出しステップ２２７２、
キーワード数繰返しステップ２２７４、ブロック内イン
デックス追加ステップ２２７６およびブロック格納ステ
ップ２２７８から構成される。まず、ブロック読み出し
ステップ２２７２で、前記ブロック数分繰返しステップ
２２５０により指定されたブロックを、インデックスフ
ァイル８０００から読み出し、ワークエリア４０００に
格納する。次に、ブロック内インデックス追加ステップ
２２７６では、抽出キーワードの中で前記ブロック読み
出しステップ２２７２でワークエリア４０００に読み出
された更新対象ブロックに割り付けられているキーワー
ドに対応するインデックスの末尾に、該当キーワードが
出現した文書の文書番号を追加する。さらに、キーワー
ド数繰返しステップ２２７４では、上記読み出されたブ
ロックにおける該当キーワードの全てについてステップ
２２７６のインデックス追加処理を繰返し行う。その
後、ブロック格納ステップ２２７８では、インデックス
追加処理が終了した上記ブロックを再びインデックスフ
ァイル８０００に格納する。以上のように、ブロック単
位インデックス追加処理ステップ２２７０では、ブロッ
ク単位にインデックスの追加処理を行う。このように、
ブロック単位に一括してキーワードのインデックス追加
処理を行うことにより、追加キーワード数が多い場合で
も、短時間にインデックスの追加処理を行うことができ
る。

【００２６】上述のキーワード割り付けプログラム２１
００でワークエリアに格納するキーワードに関する情報
の格納例について図１２を用いて説明する。キーワード
抽出ステップ２１３０では、種文書からキーワードとな
る言葉が抽出されるとともにワークエリア４０００に格
納される。本図に示すように、キーワードに対応してそ
のキーワード番号を一緒に格納している。本例では、抽
出されたキーワードとして“コア”、“ディスク”、
“コンピュータ”および“ＩＲ”が種文書から抽出され
たことを想定している。本ステップでは、これらの抽出
キーワードの抽出された順番にシリアルな番号をそのキ
ーワード番号として割り振り、本例のような形でワーク
エリア４０００に格納する。本例では、キーワード“コ
ア”、“ディスク”、“コンピュータ”および“ＩＲ”
にはキーワード番号として、それぞれ１、２、３および
４が割り振られている。次に、出現文書数カウントステ
ップ２１４０で、キーワード毎に種文書における文書出
現数がカウントされる。このとき、本図に示すようにキ
ーワードに対応した形で出現文書数を格納する。本例で
は、キーワード“コア”、“ディスク”、“コンピュー
タ”および“ＩＲ”における出現文書数は、それぞれ
２、１、３および２となっている。その後、キーワード
割り付けステップ２１５０で、上記出現文書数をもと
に、インデックスを格納するブロックへのキーワードの
割り付けが行われる。ここで割り付けられたブロック番
号を、本図に示すようにキーワードに対応付け、ワーク
エリア４０００に格納する。本例では、キーワード“コ
ア”、“ディスク”、“コンピュータ”および“ＩＲ”
が割り付けられたブロックのブロック番号は、それぞれ
１、１、２および１となっている。このような形式で、
キーワードに関する情報をワークエリア４０００に格納
することにより、種文書から抽出されたキーワードに関
する情報を管理することができるため、ブロックへのキ
ーワード割り付け処理が実現できる。

【００２７】上述のインデックス作成登録プログラム２
２００でワークエリアに格納するキーワードに関する情
報の格納例について図１３を用いて説明する。本例で
は、文書番号５の登録文書からキーワードとして“コ
ア”、“ディスク”および“ＩＲ”が抽出されたことを
想定している。キーワード抽出ステップ２２３０では、
登録文書からキーワードとなる言葉が抽出されるととも
にワークエリア４０００に格納される。このとき、図１
２に示すキーワード情報から、抽出キーワードに対応す
るキーワード番号と割り付けられたブロックのブロック
番号を取得する。このとき、本図に示すように、キーワ
ードに対応して、取得した割り付けブロックの番号とそ
の出現文書である登録文書の番号を格納する。本例で
は、キーワード“コア”、“ディスク”、“コンピュー
タ”および“ＩＲ”には、キーワード番号として、それ
ぞれ１、２、３および４を格納し、割り付けブロック番
号と登録文書番号としては、それぞれブロック番号１と
文書番号５を格納する。この情報を基に、ステップ２２
５０からステップ２２９０でインデックスの追加処理を
行う。このような形式で、キーワードに関する情報をワ
ークエリア４０００に格納することにより、登録文書か
ら抽出されたキーワードに関する情報を管理することが
できるため、これに対応するインデックスの追加処理が
実現できる。

【００２８】以上説明したように、本発明によれば、イ
ンデックスを格納するブロック毎に、該当する抽出キー
ワードが所定数以上の場合には、そのブロックを磁気デ
ィスクからメモリ上に読み込むとともに該当する抽出キ
ーワードに対するインデックスの追加処理メモリ上で一
括して行い、これを磁気ディスクへ書き込むことによ
り、磁気ディスクへのアクセス回数を低減し、所定数未
満の場合には該当する抽出キーワードに対応するインデ
ックスのみメモリ上に読み込むとともにそのインデック
スの追加処理を行い、これを磁気ディスクへ書き込むこ
とにより、磁気ディスクへのアクセスデータ量を最小化
することができるため、非常に高速なインデックス追加
処理が可能となり、文書データベースへの高速な登録処
理を実現することができる。

【００２９】

【発明の効果】本発明によれば、複数のインデックスの
追加処理をメモリ上で一括して実行することで、磁気デ
ィスクへのアクセス回数を低減することができるため高
速なインデックス追加処理が可能となり、文書データベ
ースへの登録処理を高速に行うことが可能となる。

【図面の簡単な説明】

【図１】本発明が適用された文書検索システムの構成を
示す図である。

【図２】インデックスの構成例を示す図である。

【図３】新たな文書に含まれるキーワードを追加した場
合のインデックスの構成例を示す図である。

【図４】インデックス追加処理時のタイムチャートを示
す図である。

【図５】ブロックに分割されたインデックスの構成例を
示す図である。

【図６】新たな文書に含まれるキーワードを追加した場
合のブロックに分割されたインデックスの構成例を示す
図である。

【図７】論理ブロックの８回連続読み出し処理と８回連
続書き込み処理を行った場合のインデックス追加処理時
のタイムチャートを示す図である。

【図８】キーワード割り付けプログラム２１００の処理
手順を示す図である。

【図９】キーワード割り付けステップ２１５０の処理手
順を示す図である。

【図１０】インデックス作成登録プログラム２２００の
処理手順を示す図である。

【図１１】ブロック単位のインデックス追加処理ステッ
プ２２７０の処理手順を示す図である。

【図１２】キーワード管理デーブルの構成例を示す図で
ある。

【図１３】ワークテーブルの構成例を示す図である。

【符号の説明】

１０１ ディスプレイ １０２ キーボード １０３ ＣＰＵ １０４ メモリ １０５ 磁気ディスク １０６ ＦＤＤ １０７ フロッピーディスク ２０００ 登録制御プログラム ３０００ 検索制御プログラム ４０００ ワークエリア ５０００ システム制御プログラム ６０００ 検索インタフェースプログラム ８０００ インデックスファイル

───────────────────────────────────────────────────── フロントページの続き (72)発明者 多田 勝己 神奈川県川崎市麻生区王禅寺1099番地 株 式会社日立製作所システム開発研究所内 (72)発明者 加藤 寛次 神奈川県川崎市麻生区王禅寺1099番地 株 式会社日立製作所システム開発研究所内 (72)発明者 浅川 悟志 神奈川県横浜市戸塚区戸塚町5030番地 株 式会社日立製作所ソフトウェア開発本部内

Claims (4)

【特許請求の範囲】
1. 【請求項１】 文書からキーワードを抽出し、これに基
   づいてインデックスを作成し、検索時に質問語と一致し
   たキーワードに対応するインデックスを参照して検索を
   行う文書検索方法において、 前記インデックスを二次記憶装置上のファイルに格納す
   るとともに、該ファイルを所定数のブロックに分割して
   おき、各ブロックに格納されるインデックスのサイズが
   ほぼ均等になるようにキーワードを該ブロックに割り付
   け、 文書の登録時に、前記ブロックに追加または更新が発生
   したインデックスの個数が所定数以上の場合には、該ブ
   ロックを二次記憶装置から主記憶上へ読み込むととも
   に、該ブロック内のインデックスに対応するキーワード
   について、インデックスの追加処理を主記憶上で行い、
   追加処理された該ブロックを二次記憶装置へ格納し、所
   定数未満の場合には、該インデックスを二次記憶装置か
   ら主記憶上へ読み込むとともに、該インデックスに対応
   するキーワードについて、インデックスの追加処理を主
   記憶上で行い、追加処理された該インデックスを二次記
   憶装置へ格納することを特徴とした文書検索方法。
2. 【請求項２】 請求項１に記載の文書検索方法におい
   て、 キーワードのブロック割り付けに際して、ブロックに割
   り付けられたキーワードについて、インデックスが作成
   される全ての文書の内、該キーワードの出現文書数を算
   出し、各キーワード毎に算出した出現文書数の総和をブ
   ロック毎に算出し、各ブロックにおける出現文書数の総
   和が各ブロックにおいてほぼ均等になるようにキーワー
   ドのブロック割り付けを行うことを特徴とした文書検索
   方法。
3. 【請求項３】 文書からキーワードを抽出し、これに基
   づいてインデックスを作成し、検索時に質問語と一致し
   たキーワードに対応するインデックスを参照して検索を
   行う文書検索装置において、 前記インデックスを二次記憶装置上のファイルに格納す
   るとともに、該ファイルを所定数のブロックに分割する
   手段と、各ブロックに格納されるインデックスのサイズ
   がほぼ均等になるようにキーワードを該ブロックに割り
   付ける割り付け手段と、 文書の登録時に、前記ブロックに追加または更新が発生
   したインデックスの個数が所定数以上か否か判定する手
   段と、判定結果が所定数以上のとき該ブロックを二次記
   憶装置から主記憶上へ読み込み、該ブロック内のインデ
   ックスに対応するキーワードについてインデックスの追
   加処理を主記憶上で行い、追加処理された該ブロックを
   二次記憶装置へ格納する手段と、所定数未満のとき該イ
   ンデックスを二次記憶装置から主記憶上へ読み込み、該
   インデックスに対応するキーワードについて、インデッ
   クスの追加処理を主記憶上で行い、追加処理された該イ
   ンデックスを二次記憶装置へ格納する手段を備えること
   を特徴とした文書検索装置。
4. 【請求項４】 請求項３に記載の文書検索装置におい
   て、 前記割り付け手段は、ブロックに割り付けられたキーワ
   ードについて、インデックスが作成される全ての文書の
   内、該キーワードの出現文書数を算出し、各キーワード
   毎に算出した出現文書数の総和をブロック毎に算出し、
   各ブロックにおける出現文書数の総和が各ブロックにお
   いてほぼ均等になるようにキーワードのブロック割り付
   けを行うことを特徴とした文書検索装置。