JPH0954781A

JPH0954781A - 文書検索システム

Info

Publication number: JPH0954781A
Application number: JP7231915A
Authority: JP
Inventors: Kumiko Wada; 久美子和田; Emi Ikeda; 恵美池田
Original assignee: Oki Electric Industry Co Ltd
Current assignee: Oki Electric Industry Co Ltd
Priority date: 1995-08-17
Filing date: 1995-08-17
Publication date: 1997-02-25

Abstract

(57)【要約】【解決手段】文書の全体検索のために、その文書の形
態素解析等により、意味のある語句のみを抽出して索引
ファイルを生成する。また、あるいは、文書の句切りや
文字種に着目して文書を区切る。そして、索引語を抽出
する。【効果】検索対象になり得る意味のある語句のみによ
り索引ファイルを構成すれば、索引ファイルの容量が十
分小さくなり、メモリが節約でき、しかも、検索速度が
速くなる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、大量の電子化文書
から指定された文字列を高速に検索するための文書検索
システムに関するものである。

【０００２】

【従来の技術】電子メディアの著しい普及に伴い、報
道、出版、特許出願等様々な分野で大量の文書の電子化
が進んでいる。これらの大量の文書を、必要に応じて簡
単かつ高速に検索するための検索方式として、以下のよ
うな技術が紹介されている。そのひとつは、キーワード
検索方式である。これは、文書を登録する際に予めキー
ワードを付与しておき、それを用いて文書を検索する方
式である。この方式では、キーワードから該当文書を引
く転置ファイルを用いて文書を高速に検索できる。ま
た、キーワード付与時にある程度の言語解析あるいは主
題解析をするため、検索精度も良い。しかし、人手によ
るキーワード付与には専門的知識や労力が必要である
上、付与基準が作業者毎に異なるので質が一定しない
し、保守にも手間がかかる等の問題がある。キーワード
の自動抽出も試みられているが、高品質のものを得るに
は高品質な言語解析用の辞書が必要である等の問題があ
る。

【０００３】そこで、キーワード検索方式に代わって全
文検索方式が注目されるに至った。全文検索方式とは、
書誌情報やキーワード等の、文書の本文データをもとに
加工作成されたデータ（二次情報という）でなく、本文
全体（一次情報という）を直接参照して、検索者が自由
に指定するキーワードをもとに検索する方式である。し
かし、全文検索方式では本文全体を走査することによっ
て検索するため、小規模文書に対しては有効だが、大規
模文書に対しては検索時間が問題となる。そこで、専用
ハードウェアが開発されているが、二次記憶上に格納さ
れた文書をメモリに転送するのに時間がかかってしまい
ハードウェアの性能を十分に出すことが困難であった
り、機種依存性が高く、ハードウェア自身が高価で簡単
に導入することが困難である等の問題がある。

【０００４】そこで、より廉価でハードウェアの機種に
依存しない、ソフトウェアによる高速な全文検索方式が
注目されている。これらの方式では、検索を高速化する
ために索引ファイルを予め自動生成するものが多く、本
文中に出現する各文字に対してその出現位置情報を格納
する等、様々な手法が開発されている。

【０００５】

【発明が解決しようとする課題】ところで、上記のよう
な従来の全文検索方法では、ユーザが指定した任意の文
字列を高速に検索可能とするために、索引ファイルの容
量が本文の大きさに比べて著しく大きくなる傾向があ
る。検索対象となる文書は飛躍的に増加し大容量化しつ
つあり、索引ファイルの容量が本文に比べてあまりに巨
大だと対応することができない。

【０００６】一方、索引ファイルの容量を小さく抑える
と、検索速度が不十分になったり、検索洩れが起こる等
の危険がある。本発明では、より小さい容量の索引ファ
イルに、より意味のある情報を格納し、一般にユーザが
検索対象とする文字列を十分にカバーして、それを高速
に検索できるようにすることを目的とする。

【０００７】

【課題を解決するための手段】本発明は以上の点を解決
するため次の構成を採用する。（構成１）検索対象となる電子化された文書を受け入れ
て、その文書を構成する語句に関する情報を得る形態素
解析部と、この形態素解析部の出力から、検索対象とな
り得る意味のある語句のみを主索引語として抽出する主
索引語抽出部と、各主索引語と文書中の出現位置情報と
を対応付けた索引ファイルを生成する索引ファイル生成
部とを備える。（説明）電子化された文書とは、文字コード化されて、
情報処理装置によって演算処理できるような形式の文書
をいう。形態素解析部は、解析により語句の品詞を含む
情報を得る。意味のある語句とは、助詞単独といった、
それのみでは意味のない、通常では検索対象となり得な
い語句を除外した語句のことである。これにより、現実
に使用される可能性のある語句以外の索引ファイル登録
を防止して、索引ファイルの縮小化を図る。出現位置情
報とは、索引語の文書中の位置を表すデータである。

【０００８】ユーザが実際に検索を行うとき、検索対象
文書中の全ての語句が等しい確率で検索対象とされるわ
けではない。文書中にはユーザに検索されやすいものと
そうでないものが存在する。例えば、助詞や接続詞等の
付属語のみをキーとした検索が行われることはまれであ
る。そこで、ユーザの検索対象となるような語句を適当
な処理によって本文から切り出し、それらの出現位置情
報を格納した索引ファイルを生成し、これらの語句につ
いて高速に検索できるようにする。

【０００９】また、文字を単位として出現位置情報を格
納するのでなく、語句を単位として格納することによ
り、多くの情報を格納しながら索引ファイルの容量を小
さく保つ。各語句から発生する部分語を索引ファイルに
格納すると、索引ファイルの容量が大きくなりがちだ
が、語句の切り出し時に形態素解析を用いて不要語を削
除する。

【００１０】（構成２）検索対象となる電子化された文
書を受け入れて、その文書を構成する文字の文字種に着
目して、文書を構成する語句を主索引語として切り出す
語句切り出し部と、主索引語と文書中の出現位置情報と
を対応付けた索引ファイルを生成する索引ファイル生成
部とを備える。（説明）文字種に着目するとは、文書中の区切りとなる
「、」や「。」、「→」等の特殊な文字種を検出する処
理を含む。また、例えば平仮名の直後に出現する漢字を
区切り文字として語句を切り出すような処理を含む、例
えば「コンピュータの技術における、……」では「コン
ピュータの」、「技術における」が切り出される。この
ような区切り文字を検出する処理は形態素解析処理と比
べて簡便で高速化でき、多量の文書から迅速に索引ファ
イルを生成できる。主索引語を切り出すのは、区切り文
字を境にして切り出すのであって、助詞等も含めた索引
語が生成されてよい。

【００１１】（構成３）主索引語の第２番目以上の文字
から始まる、主索引語の一部による部分文字列を補助索
引語として、その補助索引語とその文中の出現位置情報
とを対応付けて、索引ファイルに格納することが好まし
い。（説明）主索引語の一部による部分文字列を検索可能に
すれば、主索引語が接頭語等を含む複合語の場合に、そ
の部分に対する検索も高速にできる効果がある。

【００１２】（構成４）主索引語及び補助索引語が非平
仮名と平仮名文字列により構成されるとき、語尾の平仮
名文字列を、前記主索引語または補助索引語の語長が縮
小されるように圧縮することが好ましい。（説明）検索の際に重要度の低い平仮名部分の語尾を圧
縮することによって、検索語の語長を制限し、索引ファ
イルを小容量で実現できる。

【００１３】

【発明の実施の形態】以下、本発明の実施の形態を具体
例を用いて説明する。〈具体例１〉図１は、本発明の文書検索システムの索引
ファイル生成／追加処理装置のブロック図である。ここ
で、具体例１として、索引ファイル生成の際の索引語の
抽出に形態素解析を用いる場合の処理について説明す
る。図１の装置は、検索対象文書入力部１と、形態素解
析部２と、主索引語抽出部３と、補助索引語生成部４
と、先頭文字ハッシュ表生成／追加部５と、索引項目表
生成／追加部６とから構成されている。検索対象文書入
力部１では、電子化された文書が入力される。ここには
図示しないメモリ等が設けられ、検索対象となる文書が
一時記憶される。形態素解析部２は、文書を文字単位で
区切って予め用意した辞書と照合し、文書で使用されて
いる単語や文書の構文等を解析し各単語のかかり具合い
等もデータとして得る部分である。これは、従来より文
書の自動的な構文解析のために使用されていた装置と全
く同様の構成をしている。即ち、検索対象文書入力部１
から入力された対象文書に対し形態素解析部２は所定の
形態素解析を施し、その結果を主索引語抽出部３に向け
て出力する。

【００１４】主索引語抽出部３は、形態素解析の結果得
られた語情報をもとにして、検索に用いられやすい品詞
の語だけを抽出する部分である。付属語や句読点等は、
独自でユーザの検索対象となることは少ないので、不要
語として切り捨て、索引生成の対象から除外する。ここ
では例えば、自立語と未知語、英数字を索引生成対象と
する。ここで索引生成対象として抽出された語を便宜上
「主索引語」と呼ぶことにする。

【００１５】補助索引語生成部４は、全ての主索引語に
対して補助索引語を生成する部分である。補助索引語と
は、与えられた主索引語Ｗ（語長Ｌ）に対して、Ｗの第
ｉ番目から最後までの文字から成る部分文字列をいう
（０＜ｉ＜Ｌ）。あるひとつの主索引語に対して、その
語長がＬのとき、高々Ｌ−１個の補助索引語が生成され
る。以下、便宜上、主索引語と補助索引語を合わせて索
引語と呼ぶ。その説明は図３を用いて行う。先頭文字ハ
ッシュ表生成／追加部５と索引項目表生成／追加部６と
は、主索引語抽出部３で抽出した主索引語及び、補助索
引語生成部４で生成した補助索引語をもとに索引ファイ
ル２１を生成する部分である。

【００１６】図２は、生成された索引ファイルを用い
て、ユーザに指定された検索パターン文字列を検索する
ための検索処理装置のブロック図である。この装置は、
検索パターン文字列入力部１１と、形態素解析部１２、
索引語抽出部１３、自立索引語検索部１４、未知語検索
部１５、本文照合部１６及び結果出力部１７から構成さ
れている。検索パターン文字列は、文書検索のためにオ
ペレータ等によってキーボード等を用いて入力される。
検索パターン文字列入力部１１は、このようなキーボー
ド、その他の入力装置から構成される。形態素解析部１
２は、図１で用いた形態素解析部２と全く同様の構成の
もので、同一部分を索引ファイルの生成にもまた検索処
理のためにも使用することができる。この形態素解析部
１２は、文書データ検索のために入力された検索パター
ン文字列の形態素解析を行う。

【００１７】索引語抽出部１３は、形態素解析の結果と
して得られた語リストのうち、不要語を取り除いて、実
際に索引の対象となる索引語を抽出する。自立索引語検
索部１４と、未知語検索部１５と、本文照合部１６は、
実際の検索を行う部分である。まず、自立索引語検索部
１４は、索引語抽出部１３で抽出された索引語のうち、
品詞が自立語、英数字であるもの全てについて索引ファ
イルを検索し、出現位置情報の候補を得る。次に、未知
語検索部１５は、索引語抽出部１３の索引語で未知語と
判定されたものがあれば、それらについても索引ファイ
ルを検索し、出現位置の候補を得る。なお、未知語と言
うのは形態素解析部１２の用いる単語辞書に無い単語の
ことをいう。最後に、本文照合部１６は、検索パターン
文字列が不要語を含むならば、それらについて本文を用
いて照合し、結果出力部１７は、得られた検索結果を出
力する。即ち、例えば「コンピュータの技術」という検
索パターン文字列を入力したとすれば、「コンピュー
タ」と「技術」とが索引ファイル中で検索される。この
とき、「の」は不要語である。従って、「コンピュー
タ」の出現位置と「技術」の出現位置の付近で「コンピ
ュータの技術」という文字列が無いかを今度は直接対象
文書本文を見ながら照合して検索結果を得る。

【００１８】図３は、索引ファイルの構成説明図を示
す。図１の索引ファイル２１は、ひとつの先頭文字ハッ
シュ表２２と、Ｎ個の索引項目表２３から成る。Ｎは、
全ての索引語の先頭に出現する文字種の総数である。索
引項目表２３は、索引語の先頭文字毎に存在する。各索
引項目表は、ある文字で始まる全ての索引語に関する出
現位置情報を格納したもので、索引語をキーとして、そ
の出現位置情報を検索できる構成になっている。

【００１９】図４は、先頭文字ハッシュ表２２の格納デ
ータ形式である。先頭文字ハッシュ表２２は、索引語の
先頭文字をキーとして、対応する索引項目表を検索する
ためのハッシュ表である。先頭文字ハッシュ表２２の各
データは３つのデータ項目の組で表される。図４に示し
た項目３１は索引語の先頭に出現する１文字、項目３２
はそれぞれ対応する索引項目表へのポインタである。項
目３３は、先頭文字ハッシュ表の次のバケットへのポイ
ンタである。次のバケットがない場合はｎｕｌｌ（無効
データ）である。

【００２０】図５は、索引項目表の格納データ形式であ
る。各データは４つのデータ項目の組で表される。項目
４１は索引語を表す固定長文字列、項目４２は項目４１
に索引語が格納しきれない場合、その残余文字列へのポ
インタである。残余文字列がない場合はｎｕｌｌであ
る。項目４３はこの索引語に対応する出現位置情報の総
数を表す。出現位置情報には２種類の表現形式がある。
ひとつは本文中の具体的な出現位置を示す値となってい
る場合で、もうひとつは索引項目表中の別の索引項目へ
のポインタとなっている場合である。ある索引語に対応
する出現位置情報が後者の形式でのみ格納されている場
合は、項目４３の総数を負数で表す。そうでない場合は
正数で表す。項目４４は出現位置情報のリストへのポイ
ンタである。

【００２１】〈動作〉以下、本発明の文字検索システム
の具体的な動作をフローチャートを用いて説明する。ま
ず、予め索引ファイルを生成する。図６と図７は、索引
ファイルの生成処理を示すフローチャートである。ま
ず、ステップＳ１で検索対象文書を入力し、ステップＳ
２で形態素解析を行う。次に、形態素解析の結果得られ
た語のうち、不要語を削除して主索引語を抽出する（ス
テップＳ３）。抽出された各主索引語について、ステッ
プＳ４以降の処理を繰り返す。

【００２２】始めに、Ｗを主索引語とし（ステップＳ
５）、Ｗの先頭文字ａで先頭文字ハッシュ表を検索する
（ステップＳ６）。文字ａに対応する索引項目表がある
ならば（ステップＳ７）、Ｗの出現位置情報を索引項目
表に登録する（ステップＳ９）。このステップＳ９で
は、索引項目表をキーＷで検索し、Ｗのデータがないな
らば、Ｗをキーとして新たにＷの出現位置情報を格納す
る。既にＷのデータがあるならば、Ｗの出現位置情報
を、出現位置情報リストの先頭に追加する。ステップＳ
７で索引項目表がないならば、ステップＳ８で新たに文
字ａに対応する索引項目表を生成してからステップＳ９
を行う。

【００２３】次に、補助索引語の登録処理を行う。まず
ステップＳ１０でＬをＷの語長から１引いた値とし、Ｘ
０をＷとする（ステップＳ１１）。さらに、ＬがＬ＞０
を満たす間（ステップＳ１２）、ステップＳ１３以下の
処理を繰り返す。ステップＳ１３では、Ｗの最後からＬ
文字をとって部分文字列Ｘを生成し、これを補助索引語
とする。次に、Ｘに関する情報を索引ファイルに格納す
る。まず、Ｘの先頭文字ａで先頭文字ハッシュ表を検索
し（ステップＳ１４）、文字ａに対応する項目表がある
ならば（ステップＳ１５）、Ｘで索引項目表を検索する
（ステップＳ１６）。該当するデータがあるならば（ス
テップＳ１７）、Ｘに対応する出現位置情報リストの最
後にＸ０へのポインタを追加登録する（ステップＳ１
８）。これ以降の補助索引語は既に索引ファイルに登録
されているので、主索引語Ｗに対応する補助索引語の登
録はここで打ち切り、次の主索引語の登録処理を行う
（ステップＳ４）。

【００２４】ステップＳ１７でＸのデータがないなら
ば、ＸをキーとしてＸ０へのポインタを出現位置情報リ
ストに格納する（ステップＳ２０）。即ち、Ｘ０：＝Ｘ
（ステップＳ２１）、Ｌ：＝Ｌ−１（ステップＳ２２）
としてステップＳ１２へ戻る。

【００２５】ステップＳ１５でａに対応する索引項目表
がないならば、文字ａに対応する索引項目表を新たに生
成し（ステップＳ１９）、Ｘに対応するデータを新たに
生成してその出現位置情報としてＸ０へのポインタを格
納する（ステップＳ２０）。更にＸ０：＝Ｘ（ステップ
Ｓ２１）、Ｌ：＝Ｌ−１（ステップＳ２２）としてステ
ップＳ１２以降の補助索引語の生成、登録処理を繰り返
す。以上のようにして、全ての主索引語や補助索引語に
対する登録処理が終ると、処理が終了する（ステップＳ
４）。

【００２６】図８と図９は、生成された索引ファイルを
用いて検索を行う場合の検索処理を示すフローチャート
である。まず、検索パターン文字列を入力し（ステップ
Ｓ１）、その文字列の形態素解析を行う（ステップＳ
２）。次に、ステップＳ３で形態素解析の結果得られた
語のリストから索引語Ｗｉ（０≦ｉ＜ｎ）を抽出する。
このとき、不要語として切り捨てられる語が存在する場
合は（ステップＳ４）、ステップＳ５でｆｌａｇ：＝
１、そうでない場合は、ステップＳ６でｆｌａｇ：＝０
とする。次に、得られた索引語に対して索引ファイルを
検索する。まず、最初に出現位置情報の候補集合Ｈを空
に設定する（ステップＳ７）。

【００２７】Ｗｉのうち自立語及び英数字のみを取り出
してＸｊ（０≦ｊ＜ｍ）とし、（ステップＳ８）、Ｘｊ
間の距離ｄｊを算出する（ステップＳ９）。例えば、
「コンピュータの技術」という検索パターン文字列の場
合には、「コンピュータ」と「技術」とは自立語で、両
者の間には「の」が存在する。この場合、両者の距離は
「の」の文字コードのバイト数即ち２バイトとなる。
尚、出現位置情報をその語の文字列の第１文字目が出現
する場所とすることもできる。このとき、「コンピュー
タの技術」の「コンピュータ」の出現位置情報が例えば
３０１（バイト目）とすれば「技術」の出現位置情報は
これに７文字分の１４バイトを加算した３１５となる。
即ち、「コンピュータ」と「技術」の距離は１４バイト
というように表すこともできる。次に、ステップＳ１０
〜１７でこれらの索引語について検索する。処理は以下
のように行う。ステップＳ１０で、ｊ：＝０として、ｊ
＜ｍの間（ステップＳ１１）以下の処理を繰り返す。Ｘ
ｊで索引ファイルを検索するために処理Ａを実行する
（ステップＳ１２）。処理Ａは図１０で後述する。該当
するデータがあれば（ステップＳ１３）、Ｘｊの出現位
置情報をＨ０の要素として登録し（ステップＳ１４）、
ＨとＨ０の要素を参照して、距離ｄｊを満たすもののみ
を新たにＨの要素とする（ステップＳ１５）。例えば
「コンピュータの技術」という検索パターン文字列の場
合に、「コンピュータ」と「技術」という語句の間の距
離が２バイト以上の物を除外するためにこの処理を行
う。ステップＳ１６では、ｊ：＝ｊ＋１として、ステッ
プＳ１１へ戻る。

【００２８】ステップＳ１３で該当するデータがないな
らば、検索パターン文字列は見つからないことになるの
で、ステップＳ１７でＨを空にして、処理Ｄへ進む。全
てのＸｊについて以上の処理を終了したら、次に、Ｗｉ
のうち未知語があれば、それらについて検索を行う。図
９のステップＳ１８で、Ｗｉのうち未知語をＵｊ（０≦
ｊ＜ｒ）とし、ステップＳ１９でＵｊに隣接するＷとの
距離ｄｊを算出する。ステップＳ２０でｊ：＝０とし
て、ステップＳ２１によりｊ＜ｒの間以下の処理を繰り
返す。Ｕｊで索引ファイルを検索するために処理Ｃを実
行する（ステップＳ２２）。処理Ｃは、例えば、処理Ａ
と同様にしてＵｊで索引ファイルを検索すればよいこれ
も図１０により詳述する。該当するデータがあれば（ス
テップＳ２３）、Ｕｊの出現位置情報をＨ０の要素とし
て登録し（ステップＳ２４）、ＨとＨ０の要素を参照し
て、距離ｄｊを満たすもののみを新たにＨの要素とする
（ステップＳ２５）。

【００２９】ステップＳ２６では、ｊ：＝ｊ＋１とし
て、ステップＳ２１へ戻る。ステップＳ２３で該当する
データがないならば、検索パターン文字列は見つからな
いことになるので、ステップＳ２７でＨを空にして、処
理Ｄへ進む。全てのＵｊについて以上の処理を終了した
ら、最後に、Ｗｉの抽出時に不要語があった場合、それ
らを含めた本文照合を行う。ステップＳ２８でｆｌａｇ
が１ならば不要語があったことを意味するので、Ｈの各
要素について本文照合し、照合するもののみをＨの要素
とする（ステップＳ２９）。そうでなければ、本文照合
はしなくてよい。最後にステップＳ３０でＨを出力し
て、終了する（ステップＳ３１）。

【００３０】図１０は、索引語が自立語である場合の、
索引ファイルの検索処理（処理Ａ）について示したフロ
ーチャートである。まずＷを索引語とし（ステップＳ
１）、出現位置の候補集合Ｍを空に設定する（ステップ
Ｓ２）。次に、Ｗの先頭文字ａで先頭文字ハッシュ表を
検索し（ステップＳ３）、文字ａに対応する索引項目表
があるならば（ステップＳ４）、索引項目表をＷに対す
る前方一致で検索する（ステップＳ５）。該当データが
あるならば（ステップＳ６）、以下の処理を行う。

【００３１】前方一致で照合したならば（ステップＳ
７）、Ｗの後続の索引語を用いて更に照合するかどうか
検査し、照合するならば（ステップＳ８）、Ｍにその出
現位置情報を追加して（ステップＳ９）、ステップＳ５
へ戻る。このようにして、索引項目表で満足するものを
全て取り出して処理を繰り返す。全ての該当するデータ
を取り出したら、Ｍを出力して（ステップＳ１１）終
了。なお、ステップＳ４で、文字ａに対応する索引項目
表がない場合は、Ｍを空にして検索を終了する。

【００３２】〈具体例１の効果〉以上の具体例１では、
対象となる文書データから形態素解析を用いて主索引語
を抽出する。このとき品詞情報を用いて、自立語等のユ
ーザが検索対象としやすい語を積極的に抽出し、単体で
は検索対象となり得ないと思われる語を積極的に除外す
ることができる。これによって、確実に意味のある文字
並びのみを索引生成対象とし、それ以外の文字並びに関
する出現位置情報を索引ファイルに格納しないようにす
ることができるので、索引ファイルの容量を大幅に縮小
し、しかも多くの意味ある情報を索引ファイルに含める
ことができる。また、ユーザの検索が名詞句について行
われることが多いとすれば、具体例１では、これらの検
索に対して特に、極めて高速に解が得られる。複合語や
未知語の検索では、上記の場合の検索より速度的には幾
分劣るものの、補助索引語に関する情報を格納すること
によって十分実用的な検索が可能である。

【００３３】〈具体例２〉具体例２として、索引語の抽
出を簡易語句解析によって実現する場合の処理について
示す。図１１は、具体例２の文書検索システムの索引フ
ァイル生成／追加処理装置のブロック図である。図１１
の装置は、検索対象文書入力部５１と、索引語の簡易切
り出し部５２と、補助索引語の圧縮展開部５３と、先頭
文字ハッシュ表生成／追加部５４と、索引項目表生成／
追加部５５とから構成されている。検索対象文書入力部
１には、電子化された文書が入力される。ここには図示
しないメモリ等が設けられ、検索対象となる文書が一時
記憶される。索引語の簡易切り出し部５２は、文書を適
当に簡易的に区切って語句を取り出す部分である。ここ
で切り出した語句を便宜上索引語と呼ぶことにする。

【００３４】日本語文を簡易的に語句に区切る方法とし
ては様々なものがあるが、ここでは、例えば句読点や漢
字、アルファベット、片仮名等の文字種を区切り記号と
した、文字種による簡易切り出しを考える。句読点は単
語の切れ目を表すものである。また、日本語の自立語の
先頭文字は漢字で表記されることが多いことや、ほとん
どの名詞は非平仮名列で表示される、等の経験則を利用
すると、文字種を用いた簡易切り出しで、ある程度正し
く語句の先頭を割り出すことができる。

【００３５】次に、補助索引語の圧縮展開部５３は、簡
易切り出し部５２で切り出した各索引語について、補助
索引語を生成し、索引ファイルへの格納用に圧縮する。
その生成方法は具体例１の場合と同様である。ある索引
語Ｗ（語長Ｌとする）の補助索引語は、高々Ｌ−１個あ
り、それぞれ索引語の第ｉ番目から最後までの文字から
成る部分文字列（０＜ｉ＜Ｌ）である。もとの索引語及
び補助索引語は、圧縮して索引ファイルに格納する。文
字列の圧縮方法としては様々な方法が考えられるが、こ
こでは例えば、以下のような方法を考える。即ち、索引
語及び補助索引語の語尾の部分が平仮名文字から成る場
合、語尾の平仮名文字部分を、ある適当な文字数で折り
たたむことによって圧縮する。例えば、圧縮単位文字数
を４とすると、９文字から成る平仮名部分列は、４文字
ずつ折りたたまれて、圧縮結果は４文字となる。折りた
たみによる圧縮方法は従来より各種のものが知られてい
るが、例えば複数の文字コードの対応するビットの論理
和をとって圧縮データを得る。このようにすると、補助
索引語の語尾を圧縮して索引ファイルの縮小化を図ると
同時にひとつの索引語から生成される補助索引語の個数
も抑えることが可能となり、ファイルを更に小さくする
ことができる。

【００３６】先頭文字ハッシュ表生成／追加部５４と索
引項目表生成／追加部５５とは、主索引語及び補助索引
語をもとに索引ファイルを生成する。索引ファイルの構
成は、実施の形態１とほぼ同様である。ただし、索引項
目表に格納される索引語は、圧縮された形式で格納され
ている。

【００３７】図１２は、生成された索引ファイルを用い
て、ユーザに指定された検索パターン文字列を検索する
ための検索処理装置のブロック図である。この装置は、
検索パターン文字列入力部６１と、索引語の簡易切り出
し部６２、索引語の圧縮部６３、索引ファイル検索部６
４、本文照合部６５及び結果出力部６６から構成されて
いる。検索パターン文字列は、文書検索のためにオペレ
ータ等によってキーボード等を用いて入力される。検索
パターン文字列入力部６１は、このようなキーボード、
その他の入力装置から構成される。索引語の簡易切り出
し部６２は、索引語を切り出す。次に、索引語の圧縮部
６３は、得られた索引語を圧縮する。圧縮方法は、索引
ファイルの生成時と同様の方法で行う。索引ファイル検
索部６４は、圧縮された索引語で索引ファイルを検索す
る。索引語を圧縮して検索しているため、ここで得られ
る解集合には誤った解も含まれる可能性がある。そこ
で、最終的には本文照合部６５によって本文と照合を行
い、結果出力部６６から結果を出力する。

【００３８】〈動作〉まず、予め索引ファイルを生成す
る。図１３は、索引ファイルの生成処理を示すフローチ
ャートである。まずステップＳ１で検索対象文書を入力
し、ステップＳ２で索引語の簡易切り出しを行う。切り
出された各索引語について、ステップＳ３以降の処理を
繰り返す。始めに、Ｗを索引語とし（ステップＳ４）、
Ｗの語長をＬとする（ステップＳ５）。また、Ｗに対す
る文字列の圧縮開始位置をｐとする（ステップＳ６）。
具体的には、例えばＷの最初の数文字が漢字で残りが平
仮名文字の場合、ｐは最初に平仮名文字が出現した位置
である。ｐ＜Ｌならば（ステップＳ７）、Ｗのｐ番目以
降の文字を折りたたみ圧縮したものをＷ１とする（ステ
ップＳ８）。そして、ｐに圧縮単位文字数を加えた値を
ｑとする（ステップＳ９）。

【００３９】ｑは、補助索引語を生成する際の生成抑止
パラメータとして用いる。理論的には、与えられた語長
Ｌの索引語Ｗに対して、その補助索引語はＬ−１個あ
り、それぞれＷの第ｉ番目から最後までの文字から成る
Ｌ−１個の部分文字列である。しかし、ここでは文字並
びを折り畳んで圧縮する方法をとっているので、ｐ番目
以降の補助索引語については圧縮単位文字数分の補助索
引語を生成してしまえば、残りは生成する必要がない。
ステップＳ７でｐ≧Ｌならば、Ｗの後半部分が非平仮名
なので圧縮を行わない。そこで、ステップＳ１０でＷ
１：＝Ｗとし、ステップＳ１１でｑ：＝Ｌとする。

【００４０】次に、索引語Ｗの圧縮形式Ｗ１を索引ファ
イルに登録する。まずＷ１の先頭文字ａで先頭文字ハッ
シュ表を検索する（ステップＳ１２）。文字ａに対応す
る索引項目表があるならば（ステップＳ１３）、Ｗ１の
データを索引項目表に登録する（ステップＳ１５）。ま
ず索引項目表をキーＷ１で検索し、Ｗ１のデータがない
ならば、Ｗ１をキーとして新たにＷの出現位置情報を格
納する。既にＷ１のデータがあるならば、Ｗの出現位置
情報を、出現位置情報リストの先頭に追加する。ステッ
プＳ１３で索引項目表がないならば、新たに文字ａに対
応する索引項目表を生成してから（ステップＳ１４）ス
テップＳ１５を実行する。

【００４１】次に、索引語Ｗに対応する補助索引語を生
成して索引ファイルに登録する。まず、ステップＳ１６
でＸ０：＝Ｗ１とし、ステップＳ１７でｉ：＝１とす
る。図１４へ移り、ｉ≦ｑの間（ステップＳ１８）、以
下の処理を繰り返す。まず、Ｗの第ｉ番目から最後まで
の文字をとった部分文字列Ｘを生成し（ステップＳ１
９）、Ｘのｐ番目以降の平仮名列を圧縮したものをＸ１
とする（ステップＳ２０）。Ｘ１の先頭文字ａで先頭文
字ハッシュ表を検索し（ステップＳ２１）、文字ａに対
応する索引項目表があるならば（ステップＳ２２）、索
引項目表をキーＸ１で検索する（ステップＳ２３）。既
にＸ１のデータがあるならば（ステップＳ２４）、Ｘ０
へのポインタを出現位置情報リストの最後に追加する
（ステップＳ２５）。これ以降の補助索引語は既に索引
ファイルに登録されているので、索引語Ｗに対応する補
助索引語の生成はここで打ち切り、ステップＳ３に戻っ
て次の索引語の登録処理を行う（ステップＳ３）。

【００４２】ステップＳ２４でＸ１のデータがないなら
ば、Ｘ１をキーとしてＸ０へのポインタを出現位置情報
リストに格納する（ステップＳ２７）。ステップＳ２８
でＸ０：＝Ｘ１とし、ステップＳ２９でｉ：＝ｉ＋１と
してステップＳ１８へ戻る。また、ステップＳ２２で文
字ａに対応する索引項目表がないならば、新たに文字ａ
に対応する索引項目表を生成してから（ステップＳ２
６）、ステップＳ２７以降を実行する。このようにし
て、全ての索引語について索引ファイルへの登録処理が
完了すれば処理を終了する（ステップＳ３０）。

【００４３】図１５は、生成された索引ファイルを用い
て検索を行う場合の処理を示すフローチャートである。
まず、検索パターン文字列を入力し（ステップＳ１）、
索引語の簡易切り出しを行う（ステップＳ２）。最初
に、該当する出現位置情報の候補集合Ｈを空に設定する
（ステップＳ３）。そして、ステップＳ２で切り出され
た全ての索引語に対してステップＳ４以降の検索処理を
繰り返し、解の候補集合を絞り込む。

【００４４】まず、Ｗを索引語とし（ステップＳ５）、
Ｗの圧縮文字列をＷ１とする（ステップＳ６）。圧縮方
法は、索引ファイルの生成時と同様の方法で行う。次
に、Ｗ１の先頭文字ａで先頭文字ハッシュ表を検索し
（ステップＳ７）、文字ａに対応する索引項目表がある
ならば（ステップＳ８）、その索引項目表をキーＷ１の
前方一致で検索する（ステップ９）。キーＷ１に前方一
致するデータがあれば（ステップＳ１０）、それらの全
てのデータの出現位置情報リストを取り出してＨ０とし
（ステップＳ１１）、Ｈ：＝Ｈ∩Ｈ０とする（ステップ
Ｓ１２）。ステップＳ１３でｉ：＝ｉ＋１としてステッ
プＳ４へ戻る。このようにして、全ての索引語について
検索処理が完了したら、Ｈに含まれる各出現位置情報に
ついて、本文と照合し（ステップＳ１５）、最終的な解
を出力して（ステップＳ１６）、終了する（ステップＳ
１７）。ステップＳ８で文字ａに対応する索引項目表が
ない場合、あるいはステップＳ１０でキーＷ１に前方一
致するデータがない場合は、Ｈを空にして（ステップＳ
１４）検索を終了する。

【００４５】〈具体例２の効果〉この具体例２では、文
字種を用いた簡易切り出しを用いて検索語を切り出す。
従って、具体例１に比べて非常に軽い処理で索引語を抽
出できるのが特徴のひとつである。それでありながら、
既知の日本語文に関する経験則を用いて切り出しを行う
ため、ある程度高い確率で正しく語の先頭を識別でき
る。このように切り出した語に対して、更に補助索引語
を生成して索引ファイルに格納する。抽出した語をもと
に索引ファイルを生成する従来技術では、しばしば語を
なさない文字並びについて、高速に検索できないという
欠点があったが、この例によれば、このような場合の検
索でも十分高速に検索を実現することができる。

【００４６】具体例２では、本文を適当に分割して生成
される語を単位として対応する出現位置情報を格納し、
更に、これに加えて補助索引語に関する情報を格納す
る。従って、具体例１と比較すると句読点等の特殊な文
字を除き、任意の文字列について均一に高速に検索する
ことが可能である。一方、具体例１と比べると、助動詞
等の付属語はほとんど検索対象にならないにも関わら
ず、これらの情報を省略できない。従って、前方一致操
作によって複数のデータ項目に対するアクセスが必要で
あり、索引ファイル容量も大きくなりがちである。しか
し、この具体例２では、各索引語に対して、語尾の圧縮
等によって補助索引語の生成に抑制効果のある、効率よ
い圧縮方法を採用できるから、結果的には索引ファイル
の容量を小さく抑えることができる。

【図面の簡単な説明】

【図１】索引ファイル生成／追加処理装置のブロック図
である。

【図２】検索処理装置のブロック図である。

【図３】索引ファイルの構成説明図である。

【図４】先頭文字ハッシュ表の格納データ形式説明図で
ある。

【図５】索引項目表の格納データ形式説明図である。

【図６】索引ファイル生成処理動作フローチャート（そ
の１）である。

【図７】索引ファイル生成処理動作フローチャート（そ
の２）である。

【図８】検索処理動作フローチャート（その１）であ
る。

【図９】検索処理動作フローチャート（その２）であ
る。

【図１０】処理Ａの自立語の索引ファイル検索動作フロ
ーチャートである。

【図１１】索引ファイル生成／追加処理装置のブロック
図である。

【図１２】検索処理装置のブロック図である。

【図１３】索引ファイル生成処理動作フローチャート
（その１）である。

【図１４】索引ファイル生成処理動作フローチャート
（その２）である。

【図１５】検索処理動作フローチャートである。

【符号の説明】

１検索対象文書入力部２形態素解析部３主索引語抽出部４補助索引語生成部５先頭文字ハッシュ表生成／追加部６索引項目表生成／追加部

Claims

【特許請求の範囲】

【請求項１】検索対象となる電子化された文書を受け
入れて、その文書を構成する語句に関する情報を得る形
態素解析部と、この形態素解析部の出力から、検索対象となり得る意味
のある語句のみを主索引語として抽出する主索引語抽出
部と、各主索引語と前記文書中の出現位置情報とを対応付けた
索引ファイルを生成する索引ファイル生成部とを備えた
ことを特徴とする文書検索システム。
【請求項２】検索対象となる電子化された文書を受け
入れて、その文書を構成する文字の文字種に着目して、
文書を構成する語句を主索引語として切り出す語句切り
出し部と、前記主索引語と前記文書中の出現位置情報とを対応付け
た索引ファイルを生成する索引ファイル生成部とを備え
たことを特徴とする文書検索システム。
【請求項３】主索引語の第２番目以降の文字から始ま
る、主索引語の一部による部分文字列を補助索引語とし
て、その補助索引語とその文書中の出現位置情報とを対
応つけて、索引ファイルに格納したことを特徴とする請
求項１または２記載の文書検索システム。
【請求項４】主索引語及び補助索引語が非平仮名と平
仮名文字列により構成されるとき、語尾の平仮名文字列
を、前記主索引語または補助索引語の語長が縮小される
ように圧縮することを特徴とする請求項２記載の文書検
索システム。