JPH09114856A - 検索用索引生成装置 - Google Patents

Abstract

(57)【要約】 【課題】 文字数（バイト数）で表現される部分文書の
位置情報を同一の語について重複して記述することを回
避して、従来に比してデータ量を大幅に減少させた索引
を生成する。 【解決手段】 パラグラフ取出し手段３によって入力さ
れた文書を複数の部分文書に分割するとともにこれら部
分文書に一意の識別子を付与し、第１テーブル４に部分
文書の識別子と当該部分文書の文書中における位置情報
とを対応付けて格納する。一方、単語抽出手段６によっ
て部分文書から抽出された語を、当該語を抽出した部分
文書の識別子と対応付けて第２テーブル７に格納する。
そして、索引生成手段８が第１テーブル４と第２テーブ
ル７との格納情報を部分文書の識別子によって関連付け
て、語をキーとした索引を生成する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、電子文書データベ
ースを検索するに際して用いられる索引を生成する装置
に関し、特に、全文データベースの索引を生成するに適
した装置に関する。

【０００２】

【従来の技術】学術文献、書籍、新聞等の電子文書に関
するデータベースには、著者や標題等の書誌的事項だけ
を収録した索引型データベース、書誌的事項に抄録を加
えた抄録型データベース、本文自体を収録した全文デー
タベース等、種々の形式があるが、近年では、情報量の
豊富な全文データベースが広く利用させている（「情報
処理」１９９２年４月（Ｖｏｌ．３３，Ｎｏ．４）第４
１３頁〜第４２０頁、「情報処理」１９９２年１０月
（Ｖｏｌ．３３，Ｎｏ．１０）第１１４４頁〜第１１５
３頁）。

【０００３】データベースに収録されている情報を検索
するに際して、当該情報に含まれる語をキーとした索引
を利用することにより、検索処理を迅速に行うことがで
きる。特に、全文データベースにおいては、実用的な処
理時間で検索を実現するために、索引を用いて検索する
ことが必須とも言える。一般的に、索引には、文書中に
出現する語（文字列）と、文書を構成している部分文書
の当該語を含むものの文書中における位置が記述されて
おり、この部分文書の位置として、１つの文書を対象と
する場合には文書の先頭文字から当該部分文書の先頭文
字までの文字数（バイト数）、複数の文書を対象とする
場合にはこれら文書識別子と文書の先頭文字から当該部
分文書の先頭文字までの文字数（バイト数）との組が用
いられている。なお、部分文書とは、文書を句点、段落
等で区切った文書の構成部分をいう。

【０００４】図５には、従来の索引の一例を示してあ
る。この索引は、同図（Ａ）に示すテーブルと同図
（Ｂ）に示すテーブルとから成っている。（Ａ）に示す
テーブルには、或る文書から抽出した語５０（出現する
語）と、当該語５０を（Ｂ）のテーブルに関連付けるポ
インタ５１とが含まれており、（Ｂ）に示すテーブルに
は前記語５０を含む部分文書の文書中における位置５２
が含まれている。語の位置５２には各語毎の文書中にお
ける出現位置をまとめて記述してあり、これら位置５２
は文書の先頭文字からこれら語の先頭文字までの文字数
（バイト数）でそれぞれ表現されている。例えば、”
春”という語は、文書中の５６バイト目から始まる部分
文書、文書中の１２０バイト目から始まる部分文書、・
・・・に位置していることが記述されている。

【０００５】

【発明が解決しようとする課題】上記したように、従来
の索引にあっては、文書中から抽出された多数の語に対
してそれぞれ部分文書の位置を記述し、これら部分文書
の位置を文書の先頭からの文字数（バイト数）で表現し
ていた。すなわち、同一の部分文書中に含まれる互いに
異なる語についてもそれぞれ同一の部分文書の位置情報
が格納され、これらの位置情報が文字数（バイト数）で
表現されていた。このため、索引全体ががかなり大きな
データ量のものとなってしまい、索引を格納するための
メモリの大型化によるコスト増大を招くばかりか、索引
に基づく検索処理の遅延化も招くという問題があった。

【０００６】本発明は上記従来の事情に鑑みなされたも
ので、文字数（バイト数）で表現される部分文書の位置
情報を同一の語について重複して記述することを回避し
て、従来に比してデータ量を大幅に減少させた索引を生
成する装置を提供することを目的とする。また、これに
よって索引を小型化し、コスト低減及び検索処理の迅速
化を実現する索引生成装置を提供することを目的とす
る。

【０００７】

【課題を解決するための手段】上記目的を達成するた
め、本発明の検索用索引生成装置では、文字数（バイト
数）で表現される位置情報に比べて小さなデータ量とな
る識別子で部分文書を記述し、文書から抽出した各語に
はそれぞれ部分文書の識別子を対応付ける。そして、こ
れら部分文書の識別子には文字数（バイト数）で表現さ
れる部分文書の位置情報を対応付け、これによって、部
分文書の位置情報を同一の語に対して重複して記述する
ことを回避する。そして、各識別子は各部分文書に一意
に対応していることから、各識別子に部分文書の位置情
報が重複して対応付けられることもなく、結果として、
索引のデータ量が従来に比して大幅に減少する。

【０００８】すなわち、分割手段によって文書を複数の
部分文書に分割して、識別子付与手段によって分割され
た部分文書に一意の識別子を付与し、第１記憶手段に部
分文書の識別子と当該部分文書の文書中における位置情
報とを対応付けて格納する。一方、抽出手段によって部
分文書から抽出された語を、当該語を抽出した部分文書
の識別子と対応付けて第２記憶手段に格納する。そし
て、索引生成手段が第１記憶手段と第２記憶手段との格
納情報を部分文書の識別子によって関連付けて、語をキ
ーとした索引を生成する。

【０００９】なお、文書を部分文書に分割する位置は、
構造化文書におけるタグのように文書中に明示的に記し
ておいてもよいが、そういった記号がなくても、文書の
パラグラフ（節、段落等）を単位とする、文字列の或る
長さ（Ｎバイト）以内のもっとも長い文章の切れ目（句
点）を単位とする、文字列の或る長さ（Ｎバイト）以上
の最も短い文章の切れ目を単位とする、といったように
種々設定することができる。

【００１０】

【発明の実施の形態】本発明に係る検索用索引生成装置
を実施する場合の一形態を図面を参照して説明する。図
１に示すように、検索用索引生成装置は、索引化する文
書データを入力するための文書入力手段１と、入力され
た文書データを一時記憶する入力文書バッファ２と、一
時記憶された文書データをパラグラフ毎の部分文書デー
タに分割するとともに各部分文書データに一意のパラグ
ラフ番号（識別子）を付与するパラグラフ取出し手段３
と、付与されたパラグラフ番号と当該部分文書データの
位置情報とを対応付けて格納する第１テーブル４と、分
割された部分文書データを一時記憶するパラグラフバッ
ファ５と、一時記憶された部分文書データからキーとな
る語を抽出する単語抽出手段６と、抽出された語と当該
語を抽出した部分文書データのパラグラフ番号とを対応
付けて格納する第２テーブル７と、第１テーブル４と第
２テーブル７との格納情報から抽出された語をキーとし
た索引を生成する索引生成手段８と、生成された索引を
二次記憶装置等に出力して格納する索引出力手段９と、
を備えている。

【００１１】文字列入力手段１は全文データベースに収
録する文書を検索用索引生成装置に読み込むための手段
であり、通常テキストデータとして与えられる文書デー
タを入力文書バッファ２内に格納する。本実施例では部
分文書の単位を１パラグラフとしており、パラグラフ取
出し手段３は入力文書バッファ２内に記憶された文書デ
ータをパラグラフ毎の部分文書データに分割し、各部分
文書データを順次パラグラフバッファ５に格納する。

【００１２】また、この分割処理に際して、パラグラフ
取出し手段３は各部分文書データに一意の識別子を付与
するものであり、本実施例では部分文書が文書中の先頭
から数えて何パラグラフ目かを示すパラグラフ番号を各
部分文書データに付与する。更に、この分割処理に際し
て、パラグラフ取出し手段３は各部分文書の先頭の文字
が文書の先頭の文字から数えて何文字目かをカウント
し、カウントされた文字数（バイト数）で表現される各
部分文書の位置情報を検出する。

【００１３】第１テーブル４は読み出し書き込み自在な
メモリから構成されており、パラグラフ取出し手段３に
よって得られた各部分文書毎のパラグラフ番号と位置情
報（バイト数）とを対応付けて記憶する。例えば、図３
の（Ａ）に示すように、パラグラフ番号”１”の部分文
書はバイト数”０”の位置から始まり、パラグラフ番
号”２”の部分文書はバイト数”５６”の位置から始ま
り、パラグラフ番号”１０２”の部分文書はバイト数”
８６０２０”の位置から始まるといったように、各部分
文書毎のパラグラフ番号と位置情報とを対応付けて記憶
する。

【００１４】単語抽出手段６は、パラグラフバッファ５
に一時記憶された部分文書データを形態素解析してキー
となる語（例えば、自立語）を抽出し、抽出した語と当
該部分文書データのパラグラフ番号とを対応付けて第２
テーブル７に格納する。なお、部分文書データから語を
抽出するためには、形態素解析以外（例えば、ＤＰマッ
チング法等）の手法を用いることもできる。第２テーブ
ル７は読み出し書き込み自在なメモリから構成されてお
り、抽出された語とパラグラフ番号とを対応付けて記憶
する。例えば、図３の（Ｂ）に示すように、パラグラフ
番号”１”の部分文書から”古来”、”日本人”、”四
季”、”変化”、”生活”、”一部”、”ある”という
語が抽出された場合には、これらの語をパラグラフ番
号”１”で示されるメモリ領域にまとめて格納する。な
お、第２テーブル７は第１テーブル４と別途のメモリ装
置から構成してもよいが、同一のメモリ装置に領域を分
割して第１テーブル４とともに構成してもよい。

【００１５】索引生成手段８は、上記のように第１テー
ブル４と第２テーブル７とに格納されら情報をパラグラ
フ番号によって互いに関連付け、これによって、単語抽
出手段６によって抽出された語をキーとした索引を生成
する。すなわち、索引生成手段８は、第２テーブル７の
格納情報に基づいて、図４の（Ａ）に示すように抽出さ
れた語４０毎にまとめたテーブル１１を作成するととも
に、同図の（Ｂ）に示すように各語４０に対応している
パラグラフ番号４２を各語毎にまとめたテーブル１２を
作成し、テーブル１１の各エントリ４０（各語）をそれ
ぞれポインタ４１でテーブル１２の各エントリ４２（パ
ラグラフ番号群）に対応付け、更に、テーブル１２のパ
ラグラフ番号群４２を第１テーブル４の格納情報（同図
の（Ｃ））に対応付ける。

【００１６】上記構成の検索用索引生成装置によると、
従来に比してデータ量が大幅に減少した索引が以下のよ
うにして生成される。まず、図２に示すテキスト文書が
文書入力手段１から入力されると、この文書データがバ
ッファ２に格納される。そして、バッファ２に格納され
た文書データに対して、パラグラフ取出し手段３が分割
処理を行って、部分文書データを順次取り出し、更に、
各部分文書データにパラグラフ番号を付与するとともに
各部分文書データの位置情報（バイト数）をカウントす
る。

【００１７】これら各部分文書データのパラグラフ番号
と位置情報（バイト数）は第１テーブル４に格納される
一方、各部分文書データはパラグラフバッファ５に一時
記憶されて、当該部分文書データから単語抽出手段６に
よってキーとなる語が抽出される。そして、これら抽出
された語は当該語を抽出した部分文書のパラグラフ番号
とともに第２テーブル７に格納され、第１テーブル４と
第２テーブル７との格納情報に基づいて索引生成手段８
によって図４に示す索引が生成される。

【００１８】すなわち、パラグラフ取出し手段３によっ
て、入力文書の１番目のパラグラフ「古来より日本人に
とって四季の変化は生活の一部であった。」が取り出さ
れて、バッファ５に格納されるとともに、このパラグラ
フ番号”１”の部分文書の先頭位置は文書中の０バイト
目なので、図３の（Ａ）に示すように、第１テーブル４
のパラグラフ番号”１”のエントリには０が書き込まれ
る。そして、単語抽出手段６によって、バッファ５に格
納された部分文書から「古来」、「日本人」、「四
季」、「変化」、「生活」、「一部」、「ある」の自立
語が抽出され、これらの語が第２テーブル７にパラグラ
フ番号”１”の部分文書に出現する語として登録され
る。

【００１９】上記と同様にして、入力文書中の２番目の
パラグラフ「春はあけぼの。夏は・・・・・」が取り出
され、パラグラフ番号”２”の部分文書の先頭位置は文
書の先頭から５６バイト目なので、第１テーブル４の２
番目のエントリには５６が書き込まれる。このように、
第１テーブル４のＮ番目のエントリの値はＮ番目のパラ
グラフの文書の先頭からのバイト数を表している。そし
て、２番目のパラグラフから「春」、「あけぼの」、
「夏」、「夜」・・・・といった語が抽出され、パラグ
ラフ番号”２”の部分文書における出現語として第２テ
ーブル７に登録される。入力文書中の３番目以降の各部
分文書についても同様な処理が繰り返しなされ、第１テ
ーブル４及び第２テーブル７に所定の情報か登録され
る。

【００２０】このようにして第１テーブル４と第２テー
ブル７とが作成された後、索引生成手段８が第２テーブ
ル７の語を重複を排して文字コード順に並べ換え、図４
の（Ａ）に示す形式のテーブル１１を生成する。また、
テーブル１１の各語を抽出した部分文書のパラグラフ番
号を各語毎にまとめて図４の（Ｂ）に示すテーブル１２
を生成し、テーブル１１の各語をポインタ４１で関連付
けるとともに、テーブル１２の各パラグラフ番号を第１
テーブル４のパラグラフ番号に対応付ける。すなわち、
索引生成手段８によって図４の（Ａ）、（Ｂ）、（Ｃ）
に示す各テーブル１１、１２、４がパラグラフ番号で関
連付けられ、語をキーとした１つの索引が生成される。

【００２１】このように生成された索引は、図５に示し
た従来の索引に比べて、データ量（バイト数）の多くな
る部分文書の位置情報５３が重複していない形式となっ
ており、従来に比してデータ量の少ないコンパクトなも
のとなっている。更に、同一パラグラフ内にある同じ語
（例えば、パラグラフ番号”２”の部分文書中にある
「春」）は、パラグラフ番号を１つテーブル１２に記憶
すればよいので、テーブル１２のエントリ数を削減する
ことができ、更に索引のデータ量が少なくて済むように
なっている。

【００２２】上記のようにして生成された索引を用いて
検索を行うときには、与えられた検索語によってテーブ
ル１１を検索して該当する語を探し、該当する語のエン
トリのポインタ４１が示すテーブル１２のエントリを参
照して、その検索語が現れる部分文書（パラグラフ）の
先頭文字の文書中における位置（なお、次のエントリの
値との差から部分文書の長さも）を得ることができる。
そして、検索結果として、該当する部分文書の先頭部分
等をディスプレイ装置等に表示する。

【００２３】なお、検索語はの分書中における出現位置
は部分文書の位置として得られ、検索語の詳しい位置が
わからないので、語と語の位置関係（例えば、”特許”
と”出願”が隣り合って現れる、”特許”の後２０文字
以内に”出願”が現れる等）といった検索は索引を用い
た処理だけでは行うことができない。しかしながら、索
引から検索語の有無及びその検索語が含まれる部分文書
が特定できるので、その部分文書のテキストそのものを
参照して検索語と検索語との位置関係を確認すれば、所
期の目的を容易に達成することができる。また、部分文
書を１パラグラフや１ページといったような小さな単位
に設定すれば、そのテキストを参照して検索語同士の位
置関係を確認する作業は、あまり時間をとらずに容易に
行うことができる。

【００２４】なお、部分文書の単位の設定に、パラグラ
フ、セクション、節、章といった階層をもたせ、生成さ
れた索引の利用範囲を拡大してもよく、このように部分
文書単位の階層を表現する場合にあっても、索引全体か
ら見れば容量の小さなテーブル１２を拡張するだけであ
るので、従来に比して索引をコンパクトなものに維持す
ることができる。

【００２５】

【実施例】約３２０Ｋｂｙｔｅの入力文書データについ
て、上記した本発明に係る装置で索引を生成したとこ
ろ、パラグラフ数は約１０００、文書中に出現する異な
る語の数は約６７００、図４の（Ｂ）に示すテーブル１
２のエントリ数は約２７０００、１エントリは２ｂｙｔ
ｅであり、同図の（Ｃ）に示すテーブル４のエントリ数
は約１０００、１エントリは３ｂｙｔｅであった。すな
わち、これらテーブル１１、４の容量はそれぞれ、５４
Ｋｂｙｔｅ、３Ｋｂｙｔｅ程度であった。

【００２６】一方、図５に示した従来技術による索引で
は、上記のテーブル１１及び４に該当するテーブル（同
図の右側部分）のエントリ数は約５９０００、１エント
リは３ｂｙｔｅとなり、当該テーブルの容量は約１７７
Ｋであった。したがって、従来と同一なテーブル１１
（図４の（Ａ））を除いて比べると、従来では１７７Ｋ
ｂｙｔｅ必要であったものに対し、本発明によれば約１
／３の５７Ｋｂｙｔｅで済み、索引全体としても大幅に
データ量が削減されたことが確認された。

【００２７】

【発明の効果】以上説明したように、本発明に係る検索
用索引生成装置によると、文書中に含まれる語の位置を
特定するための部分文書を一意に付与した識別子によっ
て識別して、バイト数表現される部分文書の位置情報を
同一の語に対して重複して記録することを回避するよう
にしたため、従来に比してデータ量を大幅に減少させて
索引を生成することができ、索引の小型化によって必要
とするメモリ容量を減少させてコスト低減を達成するこ
とができ、更には、索引を用いた検索処理の迅速化を達
成することができる。

【図面の簡単な説明】

【図１】 本発明の一例に係る検索用索引生成装置を示
す構成図である。

【図２】 索引を生成するための入力文書の一例を示す
図である。

【図３】 第１テーブル及び第２テーブルに格納される
情報を示す概念図である。

【図４】 本発明の検索用索引生成装置で生成される索
引の一例を示す概念図である。

【図５】 従来の検索用索引の一例を示す概念図であ
る。

【符号の説明】

１・・・文書入力手段、 ２・・・入力文書バッファ、
３・・・パラグラフ取出し手段、 ４・・・第１テーブ
ル、５・・・パラグラフバッファ、 ６・・・単語抽出
手段、７・・・第２テーブル、 ８・・・索引生成手
段、 ９・・・出力手段、

Claims (2)

【特許請求の範囲】
1. 【請求項１】 文書中における検索対象の語の位置を、
   当該文書を構成する部分文書の位置により記述した索引
   を生成する装置において、 文書を複数の部分文書に分割する分割手段と、 分割された部分文書に一意の識別子を付与する識別子付
   与手段と、 部分文書の識別子と当該部分文書の文書中における位置
   情報とを対応付けて格納する第１記憶手段と、 部分文書から語を抽出する抽出手段と、 語を抽出した部分文書の識別子と抽出された語とを対応
   付けて格納する第２記憶手段と、 第１記憶手段と第２記憶手段との格納情報を部分文書の
   識別子によって関連付けて語をキーとした索引を生成す
   る索引生成手段と、 を備えたことを特徴とする検索用索引生成装置。
2. 【請求項２】 請求項１に記載の検索用索引生成装置に
   おいて、 分割手段は予め設定された基準に従って文書を分割する
   ことを特徴とする検索用索引生成装置。