JPH11306203A - インデックス作成方法及び文書検索処理方法 - Google Patents

Abstract

(57)【要約】 【課題】 インデックスサイズの縮小化、及び対話的文
書検索処理における検索時間の短縮化。 【解決手段】 所与のキーワードを含んでいる文書を示
す文書ＩＤ配列リスト１を作成し、文書ＩＤ配列リスト
１の文書ＩＤ間の増分差分値を数値配列とした増分差分
値リスト２を含んでなる文書ＩＤ配列圧縮インデックス
４を作成する。文書検索処理方法において、複数の項目
の検索式の入力を対話的処理で行うのと並行してこの入
力された項目毎に所与の検索式を実行してその結果を項
目別ビットマップとして中間保存しておき、全ての項目
の入力と全ての項目毎のビットマップの中間保存が終了
したあと、項目別ビットマップを用いた集合演算を行
う。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、キーワードに基づ
いた文書検索のためのインデックス作成方法、及び対話
的な検索処理による文書検索処理方法に関する。

【０００２】

【従来の技術】従来より、データファイルに登録されて
いる大量の文書を対象としてキーワードを用いて文書検
索を行う場合、データファイル中の全ての文書のうちで
抽出したキーワードが含まれている文書のリストを、文
書の識別子（ＩＤ）のリストで表現したインデックスが
用いられている。

【０００３】また、キーワードの位置情報を用いて文書
を検索する場合、データファイル中のそれぞれの文書に
おけるキーワードの出現位置を、文書中のオフセット数
値の配列であるキーワードの位置情報を含めた形で表現
したインデックスが用いられている。この検索は、キー
ワードの位置情報を用いた近接演算、すなわち、検索式
で指定される複数のキーワードについて、これらキーワ
ード間の順番や語数等を指定した検索演算によって検索
するものである。

【０００４】さらに、文書の識別子（ＩＤ）のリストを
ビットマップで表現したインデックスも用いられてい
る。

【０００５】

【発明が解決しようとする課題】しかし、キーワード対
象文書のリストを文書の識別子（ＩＤ）のリストで表現
したインデックスでは、インデックスが文書ＩＤのリス
トの数値配列となるため、該当キーワードを含む文書が
データファイル中に大量に存在すると、その文書数に応
じてインデックスのサイズが大きくなってしまうという
問題があった。

【０００６】また、キーワードの出現位置の情報を含め
たインデックスの場合でも、キーワードの出現位置が文
書中のオフセット数値の配列とされるため、これをイン
デックスとするとインデックスのサイズが大きくなって
しまうという問題があった。

【０００７】さらに、文書の識別子（ＩＤ）のリストを
ビットマップで表現したインデックスでも、抽出したキ
ーワード毎に文書数分のビット数を必要とするため、キ
ーワードの存在する該当文書数が全文書数と比較してた
とえば１／１０程度と少ない場合でも、インデックスの
サイズが大きくなってしまうという問題があった。

【０００８】ところで、キーワードに基づくインデック
スを参照し、複数の検索対象項目（たとえばＡ，Ｂ，
Ｃ）について対話的な文書検索を行う方法では、各項目
の検索とこれら検索結果の集合演算（たとえば（Ａ and
Ｂ）or Ｃ）とを行う必要があるため、多くの処理時
間を要することとなり、検索者にとっては一連の処理が
完了するまでの待ち時間が長く感じられるという問題が
あった。

【０００９】本発明の目的は、したがって、従来技術に
おける上述の問題点を解決することができる、インデッ
クス作成方法及び文書検索処理方法を提供することにあ
る。

【００１０】

【課題を解決するための手段】上記課題を解決するた
め、請求項１の発明によれば、データファイルに格納さ
れている複数の文書から対象文書をキーワード検索する
ためのインデックスを作成するための方法であって、前
記複数の文書のうち所与のキーワードを含んでいる文書
を示す文書ＩＤ配列リストを作成するステップと、該文
書ＩＤ配列リストの文書ＩＤ間の増分差分値を数値配列
とした増分差分値リストからなる文書ＩＤ配列圧縮イン
デックスを作成するステップとを備えたインデックス作
成方法が提案される。

【００１１】請求項２の発明によれば、請求項１の発明
において、前記所与のキーワードを含んでいる文書の各
々について、前記所与のキーワードの出現位置のオフセ
ットを示すオフセットリストを作成するステップと、該
オフセットリストにおけるオフセット値間増分差分値を
数値配列としたオフセット増分差分値リストから成るオ
フセット配列圧縮インデックスを作成するステップとを
備えたインデックス作成方法が提案される。

【００１２】請求項３の発明によれば、データファイル
に格納されている複数の文書のうちから所与の複数の項
目に跨った検索式に基づいて対話的な検索処理によって
文書検索を行うための文書検索処理方法であって、前記
複数の項目の検索式の入力を対話的処理で行うのと並行
してこの入力された項目毎に所与の検索式を実行してそ
の結果を項目別ビットマップとして中間保存しておき、
全ての項目の入力と全ての項目毎のビットマップの中間
保存が終了したあと、最終的な検索式の評価を中間保存
された前記項目別ビットマップを用いた集合演算により
行うようにした文書検索処理方法が提案される。

【００１３】請求項１の発明によれば、該当するキーワ
ードを含んでいる文書の文書ＩＤ配列リストに基づい
て、文書ＩＤ内の増分差分値を数値配列とした増分差分
値リストがデータ圧縮化されたインデックスとされるた
め、インデックスのサイズを小さくすることができる。
また、検索処理で検索するときの処理時間を増大させる
ことがない。

【００１４】請求項２の発明によれば、キーワードの出
現位置のオフセットのリストも、同様にして圧縮して作
成することができ、キーワードの有無とキーワードの出
現位置とを利用することができる。

【００１５】請求項３の発明によれば、項目毎の検索式
の入力と並行してこの入力された項目毎の検索式に基づ
く検索処理が実行され、その検索結果が項目別ビットマ
ップとして中間保存される。全ての項目の検索式の入力
と全ての項目別ビットマップの中間保存が終了した後、
中間保存された項目別ビットマップを用いて集合演算が
行われ、最終的な検索結果が例えばビットマップとして
得られる。このように、対話的入力処理と並行して検索
に必要な処理が適宜に実行されるから、最終的な検索結
果が得られるまでの処理の時間を操作者は短く感じるこ
ととなる。

【００１６】

【発明の実施の形態】以下、図面を参照して本発明の実
施の形態の一例につき詳細に説明する。図１乃至図３
は、本発明によるインデックス作成方法の実施形態の一
例を説明するためのものであり、図１はデータファイル
の構造を示す図、図２は、文書ＩＤ配列圧縮インデック
スを示す図、図３は、キーワード一次インデックス及び
キーワードオフセット一次インデックスを示す図であ
る。

【００１７】図１を参照すると、データファイルには、
文書１〜文書Ｎが格納されており、文書１〜文書Ｎはそ
れぞれ項目１〜項目Ｎを有する構造とされている。ここ
で、項目１〜項目Ｎは、たとえば書名、著者名、発行日
などの内容によって分けられた項目とすることができ
る。

【００１８】次に、これらの項目１〜項目Ｎのうち項目
ｉに対応させたインデックスを本発明に従って作成する
方法につき、図２を参照して説明する。

【００１９】まず、図２の（ａ）に示されるように、図
１に示された文書１〜文書Ｎまでのうち、所与のキーワ
ードを含む文書の識別子（ＩＤ）の数値配列（１０５
６，１３２９，・・・，２０２０００１）で表現された
文書ＩＤ配列リスト１を先ず作成し、この文書ＩＤ配列
リスト１から、前後の文書の文書ＩＤの増分差分値とし
ての増分差分値２７３，６７２，・・・，３２１２を順
次求める。

【００２０】このようにして、所与のキーワードを含む
文書の文書ＩＤの増分差分値を求めた後、図２の（ｂ）
に示すように、増分差分値の数値配列（１０５６，２７
３，・・・，３２１２）からなる増分差分値リスト２
と、これらの増分差分値の各ビットシフト量（データサ
イズ：１１，９，・・・，１２）を示すビットシフト量
リスト３とを対応させて作成することで、データ圧縮さ
れた対象の文書ＩＤを示すインデックスが、文書ＩＤ配
列圧縮インデックス４として作成される。

【００２１】公知のように、キーワードに基づいて文書
検索する場合、キーワードを含む文書において、そのキ
ーワードの出現位置データを参照することは検索の精度
を向上させるのに極めて有効である。キーワードの出現
位置に関する情報も必要であるならば、これもまた、図
２において説明した文書ＩＤ配列圧縮インデックス４と
同様にして圧縮データとして作成することができる。

【００２２】すなわち、着目した文書におけるキーワー
ドの出現位置の数値配列で表現された位置配列リスト
（文書ＩＤ配列リスト１に相当）から、前後のキーワー
ドの出現位置増分差分値としての増分差分値を求めた
後、図２の（ｂ）に示す増分差分値リスト２及びビット
シフト量リスト３の場合と同様に、求められた増分差分
値の数値配列からなる増分差分値リストと、それぞれの
ビットシフト量（データサイズ）を示すビットシフト量
リストとを作成することで、データ圧縮されたキーワー
ドの出現位置に関するキーワード出現位置配列圧縮イン
デックスを作成することができる。

【００２３】以上の説明から判るように、キーワードの
出現位置に関するキーワード出現位置配列圧縮インデッ
クスは、文書ＩＤ配列圧縮インデックスの作成と全く同
様にして作成できるので、これを図示して同様の説明を
繰り返すのを省略する。

【００２４】以上のようにして作成されたキーワード出
現位置配列圧縮インデックスと文書ＩＤ配列圧縮インデ
ックス４とに基づき作成された、文書１〜文書Ｎについ
ての項目別インデックスにつき図３を参照して説明す
る。

【００２５】項目別インデックスは、図３の（ａ）に示
すキーワード一次インデックス５と、図３の（ｂ）に示
すキーワードオフセット一次インデックス６とから成っ
ている。

【００２６】図３の（ａ）は、図１のデータファイルの
項目ｉに対応させたキーワード１〜キーワードＮまでに
関するキーワード一次インデックスであり、これはＲＯ
Ｍ又はＲＡＭ等のメモリ７内における各キーワード毎の
文書ＩＤ配列圧縮インデックス（二次インデックス）の
存在場所を示すインデックスである。すなわち、このキ
ーワード一次インデックスは、キーワード１〜キーワー
ドＮ毎に図２で説明した方法で作成された各文書ＩＤ配
列圧縮インデックス（二次インデックス）が、メモリ７
内のどこに格納されているかを示すものであって、各キ
ーワード毎に、その文書ＩＤ配列圧縮インデックスの先
頭オフセット５Ａ、文書ＩＤ配列圧縮インデックスのデ
ータサイズ５Ｂ、文書ＩＤ数５Ｃの各項目を含む構造と
されている。

【００２７】ここで、文書ＩＤ配列圧縮インデックスの
先頭オフセット５Ａ、文書ＩＤ配列圧縮インデックスの
データサイズ５Ｂ、文書ＩＤ数５Ｃは、図２の（ｂ）に
示す例でいえば、それぞれ、増分差分値リスト２の先頭
に位置する１０５６、ビットシフト量リスト３の１１
（ビット）、増分差分値リスト２に示される数値の個数
を意味する。

【００２８】一方、図３の（ｂ）は、キーワード１〜キ
ーワードＮまでの各キーワードの出現位置を示すキーワ
ードオフセット一次インデックスであり、これはＲＯＭ
又はＲＡＭ等のメモリ８内における各キーワード毎のキ
ーワード出現位置配列圧縮インデックスのデータ（キー
ワードの出現位置の二次インデックス）の存在場所を示
すインデックスである。各キーワードの文書中の出現位
置を示すキーワードオフセット一次インデックスは、キ
ーワード一次インデックス５（図３の（ａ））の各キー
ワード１〜キーワードＮに一対一に対応してＮ組設けら
れている。各組は、オフセット配列圧縮インデックスの
先頭オフセット６Ａ、オフセット配列圧縮インデックス
のデータサイズ６Ｂ、オフセット数６Ｃの各項目を含む
構造とされている。

【００２９】ここで、オフセット配列圧縮インデックス
の先頭オフセット６Ａは、図２の（ｂ）の増分差分値リ
スト２の先頭に位置する１０５６と同様に、キーワード
の先頭の出現位置を意味する。オフセット配列圧縮イン
デックスのデータサイズ６Ｂは、図２の（ｂ）のビット
シフト量リスト３の１１（ビット）と同様に、キーワー
ドの出現位置の増分差分値のデータサイズを意味する。
オフセット数６Ｃは、キーワードの増分差分値の個数を
意味する。

【００３０】次に、以上のようにして作成されたインデ
ックスの使用方法を簡単に説明する。

【００３１】まず、キーワードを用いて文書を検索する
場合、所定のキーワードが入力されると、図３の（ａ）
のキーワード一次インデックス５の文書ＩＤ配列圧縮イ
ンデックスをバイナリサーチにより検索し、該当するキ
ーワードの配列中の範囲を求め、この配列の各キーワー
ドについての先頭オフセット５Ａが参照され、次いで、
図２の（ｂ）の増分差分値リスト２が参照されること
で、キーワードを用いての文書検索が行える。

【００３２】次に、キーワードの位置情報を用いた近接
演算によって文書を検索する場合、図３の（ｂ）のキー
ワードの出現位置を示すキーワードオフセット一次イン
デックス６のオフセット配列圧縮インデックスの先頭オ
フセット６Ａが参照され、次いで、増分差分値リストが
参照されることで、キーワードの位置情報が検索され、
これら検索されたキーワードの位置情報に基づく検索演
算により、キーワードの位置情報を用いた文書の検索が
行われる。

【００３３】このように、文書検索のためのインデック
スを、単に文書ＩＤの数値配列とせず、文書ＩＤの数値
配列から求めた前後の増分差分値の数値配列としたの
で、大幅なデータの圧縮が可能となり、文書ＩＤのイン
デックスのサイズを小さくすることができる。

【００３４】また、キーワードの出現位置を示すインデ
ックスも同様に、キーワードの出現位置の数値から求め
た前後の増分差分値を数値配列のインデックスとしたの
で、大幅なデータの圧縮が可能となり、キーワードの出
現位置を示すインデックスのサイズも小さくすることが
できる。

【００３５】さらに、従来のように、ビットマップによ
るインデックスの作成方法を用いないため、キーワード
の存在する該当文書数とキーワードの存在しない文書数
とによる影響を受けないことから、インデックスのサイ
ズが大きくならない。

【００３６】次に、図４乃至図６を参照して本発明によ
る文書検索処理方法の実施の形態の一例について説明す
る。図４は、本発明による文書検索処理方法に用いられ
る対話的検索を行うための文書検索システムの概略構成
を示す構成図、図５は、図４に示した文書検索システム
での処理を説明するためのフローチャート、図６は、本
文書検索処理システムで採用されているスレッド別処理
を説明するための説明図である。

【００３７】図４において、対話的文書検索システム１
０は、対話的処理のための入力装置１１と表示装置１２
とが接続されている検索処理部１３を備え、検索処理部
１３は外部記憶装置１４と内部記憶装置１５とに接続さ
れている。１６はインデックス作成処理部である。

【００３８】検索対象となる文書は、外部記憶装置１４
内にデータファイルとして格納されており（図１参
照）、インデックス作成処理部１６において、これらの
文書のうちから対象文書を検索するためのキーワードを
用いたインデックスが作成される。作成されたインデッ
クスはビットマップデータとして内部記憶装置１５内に
格納される。

【００３９】対話的文書検索システム１０においては、
ＣＲＴなどの表示装置１２に表示された検索項目入力欄
へキーボードなどの入力装置１１から検索項目別に検索
式を入力するのと並行して、検索処理部１３が内部記憶
装置１５に格納されているビットマップ形式のインデッ
クスを読み出し、入力された項目の検索式に従う文書検
索処理が行われる。

【００４０】次に、図５及び図６を参照して対話的文書
検索システム１０で実行される対話的検索による文書検
索処理について説明する。

【００４１】図５に示すフローチャートは、入力処理部
２０、この入力処理部２０と並行して処理を行う検索処
理部３０、及び集合演算処理部４０に分けられている。
また符号５０は項目別ビットマップである。本実施の形
態では、検索項目は、図６に示すようにＡ，Ｂ，Ｃとな
っており、各検索項目の検索式により得られた検索結果
の集合演算のための式は、（Ａ and Ｂ）or Ｃとして
いる。

【００４２】そして、まず検索項目のうち、項目Ａにつ
いてステップ２１で対話的検索式が入力され、ステップ
２２でその入力済が確認されると、ステップ２２の判別
結果はＹＥＳとなり、ステップ３１で項目Ａについての
項目別検索処理が所与の検索式に従って行われる。ここ
では、入力された項目Ａに関連する文書が内部記憶装置
１５に格納されているインデックスを用いて検索される
ものであり、項目Ａの対象となる文書の存在の有無が項
目Ａについての項目別ビットマップとして内部記憶装置
１５に中間保存される（ステップ３２）。

【００４３】このように、検索結果を項目別に、対象と
される文書ＩＤ１〜文書ＩＤＮに該当の有無を「１」、
「０」のデータ別としたビットマップとして作成する方
法それ自体は公知であるから、ステップ３１の処理の詳
細説明は省略し、その結果の一例を項目別ビットマップ
５０として図示する。

【００４４】ステップ２２の判別結果がＹＥＳとなった
場合、検索処理部３０でステップ３１が実行されるのと
並行して、入力処理部２０では全ての項目について検索
式を入力したか否かが判別される（ステップ２３）。ま
だ入力されていない検索式があるとステップ２３の判別
結果はＮＯとなり、ステップ２４に入る。ステップ２４
では入力項目を変更し、例えば項目Ｂの入力を待つ状態
となる。

【００４５】次に、ステップ２１で項目Ｂの検索式が入
力されると、項目Ｂについての項目別検索処理が行われ
る（ステップ３１）。この場合、入力された項目Ｂの対
象となる文書が検索され、入力された項目Ｂの対象とな
る文書の存在の有無が項目Ｂについての項目別ビットマ
ップとして内部記憶装置１５に中間保存される（ステッ
プ３２）。

【００４６】次に、ステップ２１で項目Ｃの検索式が入
力されると、同様にして項目Ｃについての項目別検索処
理が行われる（ステップ３２）。ここでは、入力された
項目Ｃの対象となる文書が検索され、その検索結果が項
目Ｃについての項目別ビットマップとして内部記憶装置
１５に中間保存される（ステップ３２）。

【００４７】そして、項目Ａ〜項目Ｃの検索式入力を終
えた場合、ステップ２３の判別結果はＹＥＳとなり、ス
テップ４１において項目間集合演算が実行される。この
項目間集合演算は中間保存されている項目別ビットマッ
プ５０を用いて行われる。本実施の形態の場合、項目Ａ
〜項目Ｃ間で（Ａ and Ｂ）or Ｃの集合演算を行うこ
とにより、最終検索結果ビットマップが得られる（ステ
ップ４２）。

【００４８】図６は、図５の入力処理部２０の処理と検
索処理部３０の処理とが並行して実行されるスレッド別
処理を説明するための図である。項目Ａの検索式が入力
されると、検索処理部３０では入力された項目Ａの検索
式に従う項目Ａの検索処理が実行されるのと並行して項
目Ｂの検索式の入力処理が入力処理部２０で実行され
る。そして、項目Ｂの検索式に従う項目Ｂの検索処理が
検索処理部３０で実行されるのと並行して、入力処理部
２０では項目Ｃの検索式の入力処理が実行され、検索処
理部３０で項目Ｃの検索式に従う項目Ｃの検索処理が実
行される。

【００４９】このようにして、入力処理部２０における
処理と検索処理部３０における処理とが並行して同時的
に行われ、これにより項目Ａ〜項目Ｃについての各中間
結果が順次検索処理部３０において得られることにな
る。

【００５０】このように、対話的文書検索システム１０
における文書検索処理では、各項目の検索式の入力と並
行して先に入力されている他の項目についての検索処理
が行われ、項目毎のビットマップが順次中間保存され
る。全ての項目の入力と全ての項目毎の中間保存が終了
した後、中間保存されたビットマップを用いて集合演算
を行い、最終的な検索結果をビットマップとして得る。
したがって、現時点で入力対象となっている項目以外の
既に入力済の項目については、項目毎の検索式の入力と
並行して予備的な処理が行われることから、全体として
効率よく処理が行われ、操作者は最終的な検索結果が得
られるまでの検索処理の時間を短く感じることになる。

【００５１】

【発明の効果】本発明のインデックス作成方法によれ
ば、単に文書ＩＤの数値配列とせず、文書ＩＤの数値配
列から求めた前後の増分差分値の数値配列としたので、
大幅なデータ圧縮が可能となり、インデックスのサイズ
を小さくすることができる。例えば、これまでの数値配
列において、数値の範囲が約２０億の場合にシフトビッ
ト数を５にすることで、数値配列のインデックスサイズ
を概ね１／３〜１／２程度に圧縮することができる。

【００５２】また、この圧縮方法によると、圧縮率が、
文書ＩＤ及びオフセットの数値のばらつきや偏りによっ
てあまり影響を受けないという利点を有している。

【００５３】さらに、この圧縮方法によると、検索処理
で複号する時の処理時間について、数値配列のインデッ
クスの読み出しと比較してほとんど時間は変わらない特
徴を有している。

【００５４】本発明の文書検索処理方法によれば、現時
点で入力対象となっている項目以外の既に入力済の項目
については、別プロセス又は別スレッドの単位で項目入
力と並行して予備的な処理を行い、最終的な検索結果が
得られるまでの処理の簡素化を図るようにしたので、検
索者が感じる検索時間を大幅に低減させることができ
る。

【図面の簡単な説明】

【図１】本発明によるインデックス作成方法の実施形態
の一例を説明するためのデータファイルの構造を示す
図。

【図２】本発明によるインデックス作成方法の実施形態
の一例を説明するための文書ＩＤ配列圧縮インデックス
を示す図。

【図３】本発明によるインデックス作成方法の実施形態
の一例を説明するためのキーワード一次インデックス及
びキーワードオフセット一次インデックスを示す図。

【図４】本発明による文書検索処理方法に用いられる対
話的検索を行うための文書検索システムの概略構成を示
す構成図。

【図５】図４に示した文書検索システムでの処理を説明
するためのフローチャート。

【図６】図５に示した文書検索処理におけるスレッド別
処理を説明するための説明図。

【符号の説明】

１ 文書ＩＤ配列リスト ２ 増分差分値リスト ３ ビットシフト量リスト ４ 文書ＩＤ配列圧縮インデックス ５ キーワード一次インデックス ６ キーワードオフセット一次インデックス １０ 対話的文書検索システム １１ 入力装置 １２ 表示装置 １３ 検索処理部 １４ 外部記憶装置 １５ 内部記憶装置 １６ インデックス作成処理部 ２０ 入力処理部 ３０ 検索処理部 ４０ 集合演算処理部 ５０ 項目別ビットマップ

Claims (3)

【特許請求の範囲】
1. 【請求項１】 データファイルに格納されている複数の
   文書から対象文書をキーワード検索するためのインデッ
   クスを作成するための方法であって、前記複数の文書の
   うち所与のキーワードを含んでいる文書を示す文書ＩＤ
   配列リストを作成するステップと、該文書ＩＤ配列リス
   トの文書ＩＤ間の増分差分値を数値配列とした増分差分
   値リストからなる文書ＩＤ配列圧縮インデックスを作成
   するステップとを備えたことを特徴とするインデックス
   作成方法。
2. 【請求項２】 前記所与のキーワードを含んでいる文書
   の各々について、前記所与のキーワードの出現位置のオ
   フセットを示すオフセットリストを作成するステップ
   と、該オフセットリストにおけるオフセット値間増分差
   分値を数値配列としたオフセット増分差分値リストから
   成るオフセット配列圧縮インデックスを作成するステッ
   プとを備えた請求項１記載のインデックス作成方法。
3. 【請求項３】 データファイルに格納されている複数の
   文書のうちから所与の複数の項目に跨った検索式に基づ
   いて対話的な検索処理によって文書検索を行うための文
   書検索処理方法であって、前記複数の項目の検索式の入
   力を対話的処理で行うのと並行してこの入力された項目
   毎に所与の検索式を実行してその結果を項目別ビットマ
   ップとして中間保存しておき、全ての項目の入力と全て
   の項目毎のビットマップの中間保存が終了したあと、最
   終的な検索式の評価を中間保存された前記項目別ビット
   マップを用いた集合演算により行うようにしたことを特
   徴とする文書検索処理方法。