JP2000207404A - 文書検索方法及び装置並びに記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】 任意の文書に類似する類似文書の検索に用い
るＮ−gramの数を有効に削減でき、類似文書の検索処理
を高速に行える文書検索方法及び装置、並びに、その検
索方法を実施するためのプログラムを記録した記録媒体
を提供する。 【解決手段】 検索対象文書に含まれる単語を抽出し
（Ｓ２〜Ｓ６）、その単語のＮ−gramを生成して（Ｓ７
〜Ｓ９）、検索対象文書と含まれるＮ−gramとの関係を
示す転置ベクトル表を準備しておく（Ｓ10，Ｓ11）。任
意の検索キー文書に含まれる単語を抽出して、その単語
のＮ−gramを生成する。転置ベクトル表と、その検索キ
ー文書におけるＮ−gramとに基づき、検索キー文書に類
似する類似文書を検索する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、任意の文書に類似
する類似文書を複数の検索対象文書から検索する方法及
び装置、並びに、その検索方法を実施するためのプログ
ラムを記録した記録媒体に関する。

【０００２】

【従来の技術及び発明が解決しようとする課題】ワード
プロセッサなどによって作成される電子文書はその量が
増大しており、ユーザが指定した質問文書に類似する類
似文書を検索する対象である検索対象文書のデータ量も
膨大であり、その類似文書を検索する処理の高速化が困
難な状況である。このような質問文書に対する類似文書
を検索対象文書から検索する方法として、以下のような
３種の方法、特開平２−2458号公報に開示の方法（以下
従来例１という）、特開平６−110948号公報に開示の方
法（以下従来例２という）、特開平９−153051号公報に
開示の方法（以下従来例３という）が公知である。

【０００３】従来例１は、質問文書及び検索対象文書か
らキーワードを抽出し、抽出したキーワードを比較して
類似度を判定し、類似度が高い文書を類似文書として出
力する。この従来例１では、キーワードの抽出の仕方に
よって検索できない単語が発生する。また、検索漏れが
生じる。例えば、検索対象文書１で「開発作業」、検索
対象文書２で「開発」というキーワードが抽出されてい
る場合に、質問文書で「開発」とキーワード抽出がなさ
れると、検索対象文書１が検索されないことになる。

【０００４】従来例２は、複数の検索対象文書に対して
Ｎ−gram参照列を生成し、その各Ｎ−gramに重み付けを
行い、複数の参照列間の共通性を除去し、質問文書をＮ
−gramに分解し、分解した各Ｎ−gramに重み付けを行
い、質問文書のＮ−gramと検索対象文書の参照列のＮ−
gramとを比較し、質問文書と検索対象文書との類似度を
表す点数を求め、その点数に応じて類似文書を検索す
る。この従来例２では、検索対象文書の共通性を求め
て、類似度の判断に利用するので、検索対象文書に追
加，削除などの変化が起こった場合、共通性を再度求め
なくてはならず、検索対象文書の変化に柔軟に対応でき
ない。また、検索対象文書の集合が変化した場合、それ
らの共通性も変化するので、同一の質問文書であっても
類似度を表す点数が変化し、類似度の評価判断が逆転す
る可能性がある。また、検索対象文書に偏りがある場
合、それらの共通性を取り除くと、その分野の特定に有
効な情報が取り除かれることになって、正しい類似度を
判断できない。更に、文書に含まれるすべてのＮ−gram
を対象として類似度を判断するので、文字種が多い日本
語の場合、その類似度計算に膨大な時間がかかる。日本
語の場合、ＪＩＳ第一水準の漢字だけでも1024種存在
し、例えば２−gramの種類数はその２乗の1048576 種に
達する。これにカタカナ，ひらがななども加えると、２
−gramの種類は莫大な数となり、類似度計算に長時間を
要する。

【０００５】従来例３は、検索対象文書から所定の部分
文字列とその出現頻度とを求め、出現頻度に基づいて部
分文字列の重要度を求め、質問文書から所定の部分文字
列とその出現頻度とを求め、その出現頻度及び上記重要
度に基づいて類似度を求め、その類似度に応じて類似文
書を検索する。この従来例３では、一度にすべての部分
文字列を抽出するので、重要度の算出処理に長時間を要
する。出現頻度で重要度を求めても、例えば数字などを
考えると、出現頻度が重要度に直結しているとは考えら
れない場合もあり、正確な検索を行えない。

【０００６】本発明は斯かる事情に鑑みてなされたもの
であり、検索に用いるＮ−gramの数を有効に削減でき、
類似文書の検索処理を高速に行える文書検索方法及び装
置、並びに、その検索方法を実施するためのプログラム
を記録した記録媒体を提供することを目的とする。

【０００７】

【課題を解決するための手段】請求項１に係る文書検索
方法は、任意の文書に類似する類似文書を、複数の文書
から検索する文書検索方法において、前記複数の文書に
含まれる単語を抽出するステップと、抽出した単語のＮ
−gramを生成するステップと、前記任意の文書に含まれ
る単語を抽出するステップと、抽出した単語のＮ−gram
を生成するステップと、前記任意の文書について生成し
たＮ−gramと前記複数の文書について生成したＮ−gram
とを比較し、その比較結果に基づいて類似文書を検索す
るステップとを有することを特徴とする。

【０００８】請求項２に係る文書検索方法は、請求項１
において、単語を抽出する際に、字面情報を用いて単語
を抽出することとし、抽出した単語の中から不要な単語
を除去することを特徴とする。

【０００９】請求項３に係る文書検索方法は、請求項１
または２において、生成したＮ−gramの中から不要なＮ
−gramを除去することを特徴とする。

【００１０】請求項４に係る文書検索方法は、請求項１
において、前記任意の文書について生成したＮ−gramと
前記複数の文書について生成したＮ−gramとに基づい
て、前記任意の文書と前記複数の文書夫々との類似度を
計算し、その類似度に応じて類似文書を検索することと
し、類似文書の候補を選定し、選定した類似文書の候補
について前記類似度を計算することを特徴とする。

【００１１】請求項５に係る文書検索方法は、請求項１
において、前記複数の文書について生成したＮ−gramの
存在情報をベクトルの形式で記憶手段に格納することと
し、前記ベクトルの各行を複数の要素を単位としてブロ
ック分けし、不要なブロックは除去して前記ベクトルを
圧縮することを特徴とする。

【００１２】請求項６に係る文書検索方法は、請求項１
において、前記複数の文書について生成したＮ−gramの
存在情報をベクトルの形式で、読み出し速度が異なる複
数の記憶手段に分けて格納することを特徴とする。

【００１３】請求項７に係る文書検索装置は、任意の文
書に類似する類似文書を、複数の文書から検索する文書
検索装置において、前記複数の文書に含まれる単語を抽
出する第１単語抽出手段と、抽出した単語のＮ−gramを
生成する第１Ｎ−gram生成手段と、前記任意の文書に含
まれる単語を抽出する第２単語抽出手段と、抽出した単
語のＮ−gramを生成する第２Ｎ−gram生成手段と、前記
任意の文書について生成したＮ−gramと前記複数の文書
について生成したＮ−gramとを比較し、その比較結果に
基づいて類似文書を検索する類似文書検索手段とを備え
ることを特徴とする。

【００１４】請求項８に係る文書検索装置は、請求項７
において、前記第１単語抽出手段及び第２単語抽出手段
は、文書の字面情報を用いて単語を抽出する手段と、抽
出した単語の中から不要な単語を除去する手段とを有す
ることを特徴とする。

【００１５】請求項９に係る文書検索装置は、請求項７
または８において、前記第１Ｎ−gram生成手段及び第２
Ｎ−gram生成手段は、生成したＮ−gramの中から不要な
Ｎ−gramを除去する手段を有することを特徴とする。

【００１６】請求項10に係る文書検索装置は、請求項７
において、前記類似文書検索手段は、前記任意の文書に
ついて生成したＮ−gramと前記複数の文書について生成
したＮ−gramとに基づいて、前記複数の文書から類似文
書の候補を選定する手段と、前記任意の文書と選定した
類似文書の候補夫々との類似度を計算する手段と、その
類似度に応じて類似文書を検索する手段とを有すること
を特徴とする。

【００１７】請求項11に係る文書検索装置は、請求項７
において、前記複数の文書について生成したＮ−gramの
存在情報をベクトルの形式で格納する格納手段を更に備
え、前記ベクトルの各行を複数の要素を単位としてブロ
ック分けし、不要なブロックは除去して前記ベクトルを
圧縮するようにして前記格納手段に格納するようにした
ことを特徴とする。

【００１８】請求項12に係る文書検索装置は、請求項７
において、前記複数の文書について生成したＮ−gramの
存在情報の一部を格納する第１格納手段と、前記複数の
文書について生成したＮ−gramの存在情報の残りの部分
を格納する、前記第１格納手段とは読み出し速度が異な
る第２格納手段とを更に備えることを特徴とする。

【００１９】請求項13に係る記録媒体は、任意の文書に
類似する類似文書を、複数の文書から検索するためのプ
ログラムを記録してあるコンピュータでの読み取り可能
な記録媒体において、前記複数の文書に含まれる単語を
抽出することを前記コンピュータにさせるプログラムコ
ード手段と、抽出した単語のＮ−gramを生成することを
前記コンピュータにさせるプログラムコード手段と、前
記任意の文書に含まれる単語を抽出することを前記コン
ピュータにさせるプログラムコード手段と、抽出した単
語のＮ−gramを生成することを前記コンピュータにさせ
るプログラムコード手段と、前記任意の文書について生
成したＮ−gramと前記複数の文書について生成したＮ−
gramとを比較し、その比較結果に基づいて類似文書を検
索することを前記コンピュータにさせるプログラムコー
ド手段とを有することを特徴とする。

【００２０】請求項14に係る記録媒体は、請求項13にお
いて、単語を抽出することを前記コンピュータにさせる
前記プログラムコード手段は、字面情報を用いて単語を
抽出することを前記コンピュータにさせるプログラムコ
ード手段と、抽出した単語の中から不要な単語を除去す
ることを前記コンピュータにさせるプログラムコード手
段とを含むことを特徴とする。

【００２１】請求項15に係る記録媒体は、請求項13また
は14において、抽出した単語のＮ−gramを生成すること
を前記コンピュータにさせるプログラムコード手段は、
生成したＮ−gramの中から不要なＮ−gramを除去するこ
とを前記コンピュータにさせるプログラムコード手段を
含むことを特徴とする。

【００２２】請求項16に係る記録媒体は、請求項13にお
いて、類似文書を検索することを前記コンピュータにさ
せる前記プログラムコード手段は、前記任意の文書につ
いて生成したＮ−gramと前記複数の文書について生成し
たＮ−gramとに基づいて、前記複数の文書から類似文書
の候補を選定することを前記コンピュータにさせるプロ
グラムコード手段と、前記任意の文書と選定した類似文
書の候補夫々との類似度を計算することを前記コンピュ
ータにさせるプログラムコード手段と、その類似度に応
じて類似文書を検索することを前記コンピュータにさせ
るプログラムコード手段とを含むことを特徴とする。

【００２３】請求項17に係る記録媒体は、請求項13にお
いて、前記複数の文書について生成したＮ−gramの存在
情報をベクトルの形式で格納手段に格納することを前記
コンピュータにさせるプログラムコード手段と、前記ベ
クトルの各行を複数の要素を単位としてブロック分け
し、不要なブロックは除去して前記ベクトルを圧縮する
ことを前記コンピュータにさせるプログラムコード手段
とを更に有することを特徴とする。

【００２４】請求項18に係る記録媒体は、請求項13にお
いて、前記複数の文書について生成したＮ−gramの存在
情報をベクトルの形式で、読み出し速度が異なる複数の
記憶手段に分けて格納することを前記コンピュータにさ
せるプログラムコード手段を更に有することを特徴とす
る。

【００２５】請求項１，７，13による第１発明では、検
索対象文書から単語を抽出し、その単語のＮ−gramを生
成すると共に、質問文書から単語を抽出し、その単語の
Ｎ−gramを生成する。そして、検索対象文書におけるＮ
−gramと質問文書におけるＮ−gramとを比較して、検索
対象文書と質問文書との類似度を求め、その類似度に応
じて類似文書を検索する。

【００２６】このように、単語抽出を行った後に、Ｎ−
gram生成を行うので、すべてのＮ−gramを生成する方法
に比べて、Ｎ−gram生成に要する時間を短縮できる。ま
た、検索処理で重要とならない語（助詞など）が単語抽
出によって取り除かれているので、検索時に考慮を必要
とするＮ−gramの数を削減できて、文書検索処理を高速
化できる。

【００２７】請求項２，８，14による第２発明では、字
面情報により単語を抽出する。よって、極めて短時間に
単語抽出を行える。また、抽出した単語の中の不要な単
語を除去した後、Ｎ−gram生成を行う。よって、類似度
を求めるＮ−gramの数を削減でき、検索処理の高速化を
図れる。

【００２８】請求項３，９，15による第３発明では、例
えばＮ−gram辞書を参照して、生成したＮ−gramの中の
不要なＮ−gramは除去する。よって、類似度を求めるＮ
−gramの数を大幅に削減でき、検索処理の高速化を図れ
る。

【００２９】請求項４，10，16による第４発明では、簡
単な演算処理によって類似文書候補を選定し、その選定
した類似文書候補についてのみ類似度を求める。よっ
て、転置ベクトル表に登録されているすべての検索対象
文書について類似度を求める方法と比べて、少ない回数
の計算処理にて類似度を求めることができ、検索処理の
高速化を図れる。

【００３０】請求項５，11，17による第５発明では、検
索対象文書におけるＮ−gramの情報を示すベクトルの各
行を複数の要素毎にブロック化し、検索処理において意
味がないブロックは除外してベクトルを圧縮する。よっ
て、そのベクトルの読み出しの回数を低減でき、検索時
間の短縮化を図れる。

【００３１】請求項６，12，18による第６発明では、ベ
クトルの中で頻繁に利用するものは、高速読み出し可能
な主記憶に格納しておく。よって、検索処理の高速化を
図れる。

【００３２】

【発明の実施の形態】以下、本発明をその実施の形態を
示す図面を参照して具体的に説明する。

【００３３】図１は、本発明の文書検索方法を実施する
ためのシステム構成を示す概念図である。類似文書検索
が行えるように、検索対象文書をインデックスに登録す
る文書登録装置１と、ユーザが指定または入力した検索
キー文書（質問文書）に対する類似文書をインデックス
から検索する類似文書検索装置２とを設けている。

【００３４】図２は、文書登録装置１の機能ブロック図
である。文書登録装置１は、文書データベースから検索
対象文書を選択する文書選択装置11と、選択された文書
から単語（キーワード）を抽出するキーワード抽出装置
12と、単語のＮ−gram（Ｎ文字連鎖）を生成するＮ−gr
am生成装置13と、インデックス（転置ベクトル表）を生
成するインデックス生成装置14とを有する。

【００３５】図３は、キーワード抽出装置12の機能ブロ
ック図である。キーワード抽出装置12は、字面解析によ
って単語を抽出する字面解析装置121 と、類似文書検索
においてノイズとなる文字を除去する不要文字除去装置
122 と、不要語辞書を参照して不要な文字列を除去する
不要文字列除去装置123 と、同義語辞書を参照して同義
語を加える同義語展開装置124 と、抽出された単語の出
現頻度を集計する頻度集計装置125 とを有する。

【００３６】図４は、Ｎ−gram生成装置13の機能ブロッ
ク図である。Ｎ−gram生成装置13は、文字列（単語）を
Ｎ−gramに分解するＮ−gram分解装置131 と、Ｎ−gram
辞書を参照して登録されているＮ−gramを抽出するＮ−
gram辞書参照装置132 と、不要なＮ−gramを除去する不
要Ｎ−gram除去装置133 とを有する。

【００３７】図５は、インデックス生成装置14の機能ブ
ロック図である。インデックス生成装置14は、生成され
たＮ−gramに応じて文書特徴ベクトルを生成する文書特
徴ベクトル生成装置141 と、文書特徴ベクトルを転置し
た転置ベクトルを生成し、転置ベクトル表に登録する転
置ベクトル表登録装置142 とを有する。

【００３８】次に、文書登録処理について説明する。図
６は、その処理手順を示すフローチャートである。文書
データベースから文書（キーワード，入力文，文章全体
またはその一部分などの何らかの意味がある文字列）を
文書選択装置11にて選択して、キーワード抽出装置12へ
送る（Ｓ１）。

【００３９】入力された文書の中から、字面解析装置12
1 にて、同じ文字種（ひらがな，カタカナ，漢字，英
字，記号など）が２文字以上連続する文字列を単語とし
て抽出する（Ｓ２）。類似文書検索において誤検索の原
因となる文字（漢数字，アラビア数字など）を、不要文
字除去装置122 にて文字列から除去する（Ｓ３）。除去
対象の不要文字の例としては、漢数字（一，二，三）、
単位記号（円）、日付（年，月，日）などがある。不要
文字列除去装置123 にて、文字列の不要／必要を判定し
て不要な文字列を除去する（Ｓ４）。文字列が不要語辞
書に登録されているか否かを判定し、登録されている場
合にはその文字列を不要文字列として除去し、登録され
ていない場合にはその文字列を必要な文字列と判定して
残す。除去対象の不要文字列の例としては、金額（一億
円）、日付（一九九五年十一月）などがある。また、同
義語展開装置124 にて、同義語辞書を検索し、登録され
ている同義語も抽出単語に加える（Ｓ５）。頻度集計装
置125 にて、以上のようにして抽出された文字列（単
語）の出現頻度を集計し、抽出された文字列を出現頻度
順に並べて文字列表を作成する（Ｓ６）。作成した文字
列表をＮ−gram生成装置13へ送る。

【００４０】Ｎ−gram分解装置131 にて、文字列表に含
まれる文字列をＮ−gramに分解する（Ｓ７）。Ｎ−gram
辞書参照装置132 にて、分解したＮ−gramの中から、Ｎ
−gram辞書に登録されているものを抽出する（Ｓ８）。
また、次のような処理により、不要Ｎ−gram除去装置13
3 にて、不要と判断されるＮ−gramを除去する（Ｓ
９）。Ｓ８で抽出したＮ−gramを出現頻度順に並べて、
Ｎ−gramリストを作成し、そのＮ−gramリストに含まれ
るＮ−gramについて、その出現頻度などに基づいて重要
度を算出する。算出した重要度が所定値を下回るＮ−gr
amは不要なＮ−gramと判定して、Ｎ−gramリストから削
除する。このようにして生成したＮ−gramを、インデッ
クス生成装置14へ送る。このようにＮ−gramの数を減ら
すので、類似文書の検索速度の向上を図れる。

【００４１】文書特徴ベクトル生成装置141 にて、生成
されたＮ−gramの登録番号に対応したビットを“１”に
して、文書特徴ベクトルを生成する（Ｓ10）。図７に、
文書特徴ベクトルの一例を示す。図７に示す例では、４
種の検索対象文書１〜検索対象文書４のそれぞれに４種
のＮ−gram１〜Ｎ−gram４が含まれているか否かを表し
ており、例えば、文書２では、Ｎ−gram２及びＮ−gram
４を含み、Ｎ−gram１及びＮ−gram３を含まない。

【００４２】転置ベクトル表登録装置142 にて、文書特
徴ベクトルを転置して転置ベクトルを生成し、転置ベク
トル表にその転置ベクトルを登録する（Ｓ11）。図８
に、図７の文書特徴ベクトルに対応した転置ベクトル表
を示す。例えば、Ｎ−gram２が文書２及び文書４に含ま
れていることを表している。本発明では、Ｎ−gramが含
まれている場合にはビット“１”、含まれていない場合
にはビット“０”を割り当てるのみであり、きわめて簡
易に転置ベクトル表を作成することができる。

【００４３】そして、登録終了の指示がなされた否かを
判断し（Ｓ12）、なされた場合には（Ｓ12：YES)登録処
理を終了し、なされていない場合には（Ｓ12：NO）Ｓ１
に戻って別の検索対象文書における登録処理を繰り返
す。

【００４４】次に、効率が良い転置ベクトル表作成につ
いて説明する。図９は、転置ベクトル表登録装置142 の
機能ブロック図である。転置ベクトル表登録装置142
は、転置ベクトル表を生成する転置ベクトル表生成装置
1421と、転置ベクトル表の各行の要素をブロック化する
ブロック分解装置1422と、転置ベクトル表を圧縮するベ
クトル圧縮装置1423とを有する。

【００４５】転置ベクトル表生成装置1421で生成した転
置ベクトル表に対して、ブロック分解装置1422にて、各
行の要素を長さＬ毎に区切る。ベクトル圧縮装置1423に
て、長さＬに区切られたブロック内に“０”要素のみが
含まれるブロックは保持せず、少なくとも１つの“１”
要素を含むブロックを位置情報と共に保持する。このよ
うに圧縮化しておいても、転置ベクトル表を再構成しよ
うとする場合、位置情報を基に“１”要素を含むブロッ
クを復元して、ブロックが存在しない部分をすべて
“０”要素で埋めることにより再構成が可能である。こ
のように転置ベクトル表を圧縮することにより、計算機
資源の有効利用、転置ベクトル表へのアクセス回数の低
減を実現でき、検索速度の向上を図れる。

【００４６】図10は、類似文書検索装置２の機能ブロッ
ク図である。類似文書検索装置２は、検索キー文書（質
問文書）を入力する検索キー文書入力装置21と、入力さ
れた検索キー文書からキーワード（単語）を抽出するキ
ーワード抽出装置22と、単語のＮ−gramを生成するＮ−
gram生成装置23と、生成したＮ−gramに対応する転置ベ
クトルを取り出すインデックス参照装置24と、検索キー
文書に対する類似文書を判定する類似文書判定装置25と
を有する。

【００４７】なお、キーワード抽出装置22の構成は、前
述したキーワード抽出装置12の構成と同じであり、Ｎ−
gram生成装置23の構成は、前述したＮ−gram生成装置13
の構成と同じである。

【００４８】図11は、インデックス参照装置24の機能ブ
ロック図である。インデックス参照装置24は、使用頻度
が高い転置ベクトル表を主記憶から読み出す転置ベクト
ル表先読み装置241 と、インデックスファイルから転置
ベクトル表を読み出す転置ベクトル表読み出し装置242
とを有する。

【００４９】図12は、類似文書判定装置25の機能ブロッ
ク図である。類似文書判定装置25は、転置ベクトルに基
づいて類似文書候補を選定する類似文書候補選定装置25
1 と、類似文書候補について類似度を計算する類似度計
算装置252 と、類似度順に検索結果をソートする検索結
果ソート装置253 と、類似度順にソートされた検索結果
を出力する検索結果出力装置254 とを有する。

【００５０】次に、類似文書検索処理について説明す
る。図13は、その処理手順を示すフローチャートであ
る。検索キー文書入力装置21にて、文書（キーワード，
入力文，文章全体またはその一部分などの何らかの意味
がある文字列）を入力して、キーワード抽出装置22へ送
る（Ｓ21）。

【００５１】キーワード抽出装置22における動作は、前
述したキーワード抽出装置12における動作と同様であ
る。即ち、入力された文書の中から、同じ文字種が２文
字以上連続する文字列を単語として抽出し（Ｓ22）、不
要な文字を文字列から除去し（Ｓ23）、不要語辞書を参
照して文字列の不要／必要を判定して不要な文字列を除
去し（Ｓ24）、同義語辞書を検索して同義語も抽出単語
に加え（Ｓ25）、抽出された文字列（単語）の出現頻度
を集計して文字列表を作成し（Ｓ26）、作成した文字列
表をＮ−gram生成装置23へ送る。

【００５２】Ｎ−gram生成装置23における動作は、前述
したＮ−gram生成装置13における動作と同様である。即
ち、文字列表に含まれる文字列（単語）をＮ−gramに分
解し（Ｓ27）、分解したＮ−gramの中から、Ｎ−gram辞
書に登録されているものを抽出し（Ｓ28）、不要と判断
されるＮ−gramを除去し（Ｓ29）、残ったＮ−gramをイ
ンデックス参照装置24へ送る。

【００５３】転置ベクトル表を読み出す場合に、まず主
記憶に書き込まれているか否かを判断する（Ｓ30）。主
記憶に書き込まれている場合には（Ｓ30：YES)、そこか
ら転置ベクトル表先読み装置241 にて転置ベクトル表を
読み出す（Ｓ31）。主記憶に書き込まれていない場合に
は（Ｓ30：NO）、転置ベクトル表読み出し装置242 に
て、インデックスファイルから転置ベクトル表を読み出
す（Ｓ32）。読み出した転置ベクトル表を類似文書判定
装置25へ送る。頻繁に必要となる転置ベクトル表を、高
速にアクセスできる主記憶上に書き込むようにしたの
で、検索処理の高速化を図れる。

【００５４】類似文書候補選定装置251 にて、次のよう
にして類似文書候補を選定する（Ｓ33）。検索キー文書
から取り出されたＮ−gramに対応する転置ベクトルを、
入力された転置ベクトル表から取り出す。取り出した転
置ベクトルを足し合わせる。そして、この加算結果（重
なり語数）が１以上となる検索対象文書を類似文書候補
とする。類似文書候補となった文書について、類似度計
算装置252 にて、類似度を後述する所定の計算式に従っ
て計算する（Ｓ34）。そして、検索結果ソート装置253
にて、類似度順に検索結果をソートし、類似度順にソー
トされた検索結果を検索結果出力装置254 から出力する
（Ｓ35）。

【００５５】ここで、類似度計算の具体例について説明
する。検索対象文書及び転置ベクトル表は、前述した図
８に示すものとする。また、検索キー文書には、Ｎ−gr
am１とＮ−gram３とが含まれているとする。まず、これ
らのＮ−gram１及びＮ−gram３に対応する転置ベクトル
を図８から取り出して、それらを各文書１〜文書４につ
いて足し合わせる。具体的にその加算値は、文書１：
２，文書２：０，文書３：２，文書４：１となる。その
加算値が１以上である文書１，文書３，文書４を類似文
書候補とする。文書２は加算値が０であるので類似文書
候補としない。次に、これらの類似文書候補（文書１，
文書３，文書４）それぞれについて、以下の式（１）に
従って類似度Ｄを計算する。 Ｄ＝γ／（α・β）^1/2 但し、 α：検索対象文書（文書１，文書３，文書４）のＮ−gr
amの総数 β：検索キー文書（質問文書）のＮ−gramの総数 γ：対応する転置ベクトルの加算値（上記例では、文書
１：２，文書文書３：２，文書４：１）

【００５６】なお、上述の式（１）に示す類似度Ｄの計
算式は一例であり、他の式に従って類似度Ｄを求めるよ
うにしても良いことは言うまでもない。

【００５７】本発明では、このように、転置ベクトル表
に登録されているすべての検索対象文書について類似度
を計算するのではなく、最初に類似文書候補を選定し、
それらの類似文書候補についてのみ類似度を計算するよ
うにしているので、少ない回数の計算で類似度を求める
ことができ、検索処理の高速化を図れる。

【００５８】図14は、本発明の記録媒体の実施の形態の
構成を示すブロック図である。ここに例示するプログラ
ムは、図６及び図13に示すＳ１〜Ｓ12及びＳ21〜Ｓ35を
含んでおり、以下に説明する記録媒体に記録されてい
る。

【００５９】図14において、コンピュータ30とオンライ
ン接続する記録媒体31は、コンピュータ30の設置場所か
ら隔たって設置される例えばＷＷＷ(World Wide Web)の
サーバコンピュータを用いてなり、記録媒体31には前述
の如きプログラム31a が記録されている。記録媒体31か
ら読み出されたプログラム31a がコンピュータ30を制御
することにより、コンピュータ30が文書登録処理及び類
似文書検索処理を実行する。

【００６０】コンピュータ30の内部に設けられた記録媒
体32は、内蔵設置される例えばハードディスクドライブ
またはＲＯＭなどを用いてなり、記録媒体32には前述の
如きプログラム32a が記録されている。記録媒体32から
読み出されたプログラム32aがコンピュータ30を制御す
ることにより、コンピュータ30が文書登録処理及び類似
文書検索処理を実行する。

【００６１】コンピュータ30に設けられたディスクドラ
イブ30a に装填して使用される記録媒体33は、運搬可能
な例えば光磁気ディスク，ＣＤ−ＲＯＭまたはフレキシ
ブルディスクなどを用いてなり、記録媒体33には前述の
如きプログラム33a が記録されている。記録媒体33から
読み出されたプログラム33a がコンピュータ30を制御す
ることにより、コンピュータ30が文書登録処理及び類似
文書検索処理を実行する。

【００６２】

【発明の効果】以上のように本発明では、検索対象文書
及び質問文書からその中に含まれる単語を特徴量として
抽出し、その抽出した単語からＮ−gramを生成し、検索
対象文書におけるＮ−gramと質問文書におけるＮ−gram
とを比較して類似度を求めて、類似文書を検索するよう
にしたので、検索処理に必要なＮ−gramを短時間で得る
ことができ、検索処理の高速化を図れる。

【図面の簡単な説明】

【図１】本発明の文書検索方法を実施するためのシステ
ム構成を示す概念図である。

【図２】文書登録装置の機能ブロック図である。

【図３】キーワード抽出装置の機能ブロック図である。

【図４】Ｎ−gram生成装置の機能ブロック図である。

【図５】インデックス生成装置の機能ブロック図であ
る。

【図６】文書登録処理の手順を示すフローチャートであ
る。

【図７】文書特徴ベクトルの一例を示す図である。

【図８】図７に対応する転置ベクトル表を示す図であ
る。

【図９】転置ベクトル表登録装置の機能ブロック図であ
る。

【図１０】類似文書検索装置の機能ブロック図である。

【図１１】インデックス参照装置の機能ブロック図であ
る。

【図１２】類似文書判定装置の機能ブロック図である。

【図１３】類似文書検索処理の手順を示すフローチャー
トである。

【図１４】本発明の記録媒体の実施の形態の構成を示す
ブロック図である。

【符号の説明】

１ 文書登録装置 ２ 類似文書検索装置 12，22 キーワード抽出装置 13，23 Ｎ−gram生成装置 14 インデックス生成装置 24 インデックス参照装置 25 類似文書判定装置 30 コンピュータ 31，32，33 記録媒体 121 字面解析装置 122 不要文字除去装置 123 不要文字列除去装置 131 Ｎ−gram分解装置 132 Ｎ−gram辞書参照装置 133 不要Ｎ−gram除去装置 141 文書特徴ベクトル生成装置 142 転置ベクトル表登録装置 241 転置ベクトル表先読み装置 242 転置ベクトル表読み出し装置 251 類似文書候補選定装置 252 類似度計算装置 1421 転置ベクトル表生成装置 1422 ブロック分解装置 1423 ベクトル圧縮装置

Claims (18)

【特許請求の範囲】
1. 【請求項１】 任意の文書に類似する類似文書を、複数
   の文書から検索する文書検索方法において、前記複数の
   文書に含まれる単語を抽出するステップと、抽出した単
   語のＮ−gramを生成するステップと、前記任意の文書に
   含まれる単語を抽出するステップと、抽出した単語のＮ
   −gramを生成するステップと、前記任意の文書について
   生成したＮ−gramと前記複数の文書について生成したＮ
   −gramとを比較し、その比較結果に基づいて類似文書を
   検索するステップとを有することを特徴とする文書検索
   方法。
2. 【請求項２】 単語を抽出する際に、字面情報を用いて
   単語を抽出することとし、抽出した単語の中から不要な
   単語を除去する請求項１記載の文書検索方法。
3. 【請求項３】 生成したＮ−gramの中から不要なＮ−gr
   amを除去する請求項１または２記載の文書検索方法。
4. 【請求項４】 前記任意の文書について生成したＮ−gr
   amと前記複数の文書について生成したＮ−gramとに基づ
   いて、前記任意の文書と前記複数の文書夫々との類似度
   を計算し、その類似度に応じて類似文書を検索すること
   とし、類似文書の候補を選定し、選定した類似文書の候
   補について前記類似度を計算する請求項１記載の文書検
   索方法。
5. 【請求項５】 前記複数の文書について生成したＮ−gr
   amの存在情報をベクトルの形式で記憶手段に格納するこ
   ととし、前記ベクトルの各行を複数の要素を単位として
   ブロック分けし、不要なブロックは除去して前記ベクト
   ルを圧縮する請求項１記載の文書検索方法。
6. 【請求項６】 前記複数の文書について生成したＮ−gr
   amの存在情報をベクトルの形式で、読み出し速度が異な
   る複数の記憶手段に分けて格納する請求項１記載の文書
   検索方法。
7. 【請求項７】 任意の文書に類似する類似文書を、複数
   の文書から検索する文書検索装置において、前記複数の
   文書に含まれる単語を抽出する第１単語抽出手段と、抽
   出した単語のＮ−gramを生成する第１Ｎ−gram生成手段
   と、前記任意の文書に含まれる単語を抽出する第２単語
   抽出手段と、抽出した単語のＮ−gramを生成する第２Ｎ
   −gram生成手段と、前記任意の文書について生成したＮ
   −gramと前記複数の文書について生成したＮ−gramとを
   比較し、その比較結果に基づいて類似文書を検索する類
   似文書検索手段とを備えることを特徴とする文書検索装
   置。
8. 【請求項８】 前記第１単語抽出手段及び第２単語抽出
   手段は、文書の字面情報を用いて単語を抽出する手段
   と、抽出した単語の中から不要な単語を除去する手段と
   を有する請求項７記載の文書検索装置。
9. 【請求項９】 前記第１Ｎ−gram生成手段及び第２Ｎ−
   gram生成手段は、生成したＮ−gramの中から不要なＮ−
   gramを除去する手段を有する請求項７または８記載の文
   書検索装置。
10. 【請求項１０】 前記類似文書検索手段は、前記任意の
    文書について生成したＮ−gramと前記複数の文書につい
    て生成したＮ−gramとに基づいて、前記複数の文書から
    類似文書の候補を選定する手段と、前記任意の文書と選
    定した類似文書の候補夫々との類似度を計算する手段
    と、その類似度に応じて類似文書を検索する手段とを有
    する請求項７記載の文書検索装置。
11. 【請求項１１】 前記複数の文書について生成したＮ−
    gramの存在情報をベクトルの形式で格納する格納手段を
    更に備え、前記ベクトルの各行を複数の要素を単位とし
    てブロック分けし、不要なブロックは除去して前記ベク
    トルを圧縮するようにして前記格納手段に格納するよう
    にした請求項７記載の文書検索装置。
12. 【請求項１２】 前記複数の文書について生成したＮ−
    gramの存在情報の一部を格納する第１格納手段と、前記
    複数の文書について生成したＮ−gramの存在情報の残り
    の部分を格納する、前記第１格納手段とは読み出し速度
    が異なる第２格納手段とを更に備える請求項７記載の文
    書検索装置。
13. 【請求項１３】 任意の文書に類似する類似文書を、複
    数の文書から検索するためのプログラムを記録してある
    コンピュータでの読み取り可能な記録媒体において、前
    記複数の文書に含まれる単語を抽出することを前記コン
    ピュータにさせるプログラムコード手段と、抽出した単
    語のＮ−gramを生成することを前記コンピュータにさせ
    るプログラムコード手段と、前記任意の文書に含まれる
    単語を抽出することを前記コンピュータにさせるプログ
    ラムコード手段と、抽出した単語のＮ−gramを生成する
    ことを前記コンピュータにさせるプログラムコード手段
    と、前記任意の文書について生成したＮ−gramと前記複
    数の文書について生成したＮ−gramとを比較し、その比
    較結果に基づいて類似文書を検索することを前記コンピ
    ュータにさせるプログラムコード手段とを有することを
    特徴とする記録媒体。
14. 【請求項１４】 単語を抽出することを前記コンピュー
    タにさせる前記プログラムコード手段は、字面情報を用
    いて単語を抽出することを前記コンピュータにさせるプ
    ログラムコード手段と、抽出した単語の中から不要な単
    語を除去することを前記コンピュータにさせるプログラ
    ムコード手段とを含む請求項１３記載の記録媒体。
15. 【請求項１５】 抽出した単語のＮ−gramを生成するこ
    とを前記コンピュータにさせるプログラムコード手段
    は、生成したＮ−gramの中から不要なＮ−gramを除去す
    ることを前記コンピュータにさせるプログラムコード手
    段を含む請求項１３または１４記載の記録媒体。
16. 【請求項１６】 類似文書を検索することを前記コンピ
    ュータにさせる前記プログラムコード手段は、前記任意
    の文書について生成したＮ−gramと前記複数の文書につ
    いて生成したＮ−gramとに基づいて、前記複数の文書か
    ら類似文書の候補を選定することを前記コンピュータに
    させるプログラムコード手段と、前記任意の文書と選定
    した類似文書の候補夫々との類似度を計算することを前
    記コンピュータにさせるプログラムコード手段と、その
    類似度に応じて類似文書を検索することを前記コンピュ
    ータにさせるプログラムコード手段とを含む請求項１３
    記載の記録媒体。
17. 【請求項１７】 前記複数の文書について生成したＮ−
    gramの存在情報をベクトルの形式で格納手段に格納する
    ことを前記コンピュータにさせるプログラムコード手段
    と、前記ベクトルの各行を複数の要素を単位としてブロ
    ック分けし、不要なブロックは除去して前記ベクトルを
    圧縮することを前記コンピュータにさせるプログラムコ
    ード手段とを更に有する請求項１３記載の記録媒体。
18. 【請求項１８】 前記複数の文書について生成したＮ−
    gramの存在情報をベクトルの形式で、読み出し速度が異
    なる複数の記憶手段に分けて格納することを前記コンピ
    ュータにさせるプログラムコード手段を更に有する請求
    項１３記載の記録媒体。