(57)【特許請求の範囲】
【請求項１】
情報の単位であるノードとノード間のリンクによって構成されたハイパードキュメントシステムを対象にして情報を検索する情報検索装置において、
リンクによる結合と内容の類似性に基づいてノード群を構成するノード群構成手段と、
前記ノード群を構成する個々のノードを記憶する構成ノード記憶手段と、
所定の検索要求に対応して前記ハイパードキュメントシステムから情報を検索する情報検索手段と、
前記情報検索手段の検索結果として得られた複数のノード群の相互の包含関係を、前記構成ノード記憶手段に記憶されている情報に基づいて解析する包含関係解析手段と、
前記包含関係解析手段の解析結果に応じて、他のノード群に包含されているノード群を排除するノード群排除手段と、
排除されずに残ったノード群を検索結果として出力する検索結果出力手段と、
を有することを特徴とする情報検索装置。
【請求項２】
検索要求として、リンクによる結合と内容の類似性に基づいて構成されたノード群が与えられた場合に、前記ノード群を構成する個々のノードを記憶する検索要求構成ノード記憶手段と、
検索結果の候補として得られたノード群と、前記検索要求のノード群との包含関係を、前記検索要求構成ノード記憶手段に記憶されている情報を参照して解析する対検索要求包含関係解析手段と、
前記検索要求のノード群に包含されるノード群を排除する対検索要求ノード群排除手段とを更に有することを特徴とする請求項１記載の情報検索装置。
【請求項３】
情報の単位であるノードとノード間のリンクによって構成されたハイパードキュメントシステムを対象にして情報を検索する情報検索方法において、
リンクによる結合と内容の類似性に基づいてノード群を構成するノード群構成ステップと、
前記ノード群を構成する個々のノードを記憶する構成ノード記憶ステップと、
所定の検索要求に対応して前記ハイパードキュメントシステムから情報を検索する情報検索ステップと、
前記情報検索ステップの検索結果として得られた複数のノード群の相互の包含関係を、前記構成ノード記憶ステップに記憶されている情報に基づいて解析する包含関係解析ステップと、
前記包含関係解析ステップの解析結果に応じて、他のノード群に包含されているノード群を排除するノード群排除ステップと、
排除されずに残ったノード群を検索結果として出力する検索結果出力ステップと、
を有することを特徴とする情報検索方法。
【請求項４】
情報の単位であるノードとノード間のリンクによって構成されたハイパードキュメントシステムの情報をコンピュータに検索させるための情報検索プログラムを記録したコンピュータ読み取り可能な記録媒体において、
リンクによる結合と内容の類似性に基づいてノード群を構成するノード群構成手段、
前記ノード群を構成する個々のノードを記憶する構成ノード記憶手段、
所定の検索要求に対応して前記ハイパードキュメントシステムから情報を検索する情報検索手段、
前記情報検索手段の検索結果として得られた複数のノード群の相互の包含関係を、前記構成ノード記憶手段に記憶されている情報に基づいて解析する包含関係解析手段、
前記包含関係解析手段の解析結果に応じて、他のノード群に包含されているノード群を排除するノード群排除手段、
排除されずに残ったノード群を検索結果として出力する検索結果出力手段、
としてコンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項５】
情報の単位であるノードとノード間のリンクによって構成されたハイパードキュメントシステムを対象にして情報を検索する情報検索装置において、
リンクによる結合と内容の類似性に基づいて検索の対象となるノード群を構成するノード群構成手段と、
前記ノード群構成手段によって構成されたノード群のそれぞれに属する個々のノードを記憶する構成ノード記憶手段と、
前記ノード群の相互の包含関係を、前記構成ノード記憶手段に記憶されている情報に基づいて解析する包含関係解析手段と、
前記包含関係解析手段によって包含関係が認められた１組のノード群の間の類似度を算定する類似度算定手段と、
前記類似度算定手段によって算定された類似度が所定の閾値以上である場合には、包含される方のノード群を排除し、排除されずに残ったノード群を検索の対象として絞り込む検索対象絞り込み手段と、
を有することを特徴とする情報検索装置。
【請求項６】
情報の単位であるノードとノード間のリンクによって構成されたハイパードキュメントシステムを対象にして情報を検索する情報検索方法において、
リンクによる結合と内容の類似性に基づいて検索の対象となるノード群を構成するノード群構成ステップと、
前記ノード群構成ステップによって構成されたノード群のそれぞれに属する個々のノードを記憶する構成ノード記憶ステップと、
前記ノード群の相互の包含関係を、前記構成ノード記憶ステップに記憶されている情報に基づいて解析する包含関係解析ステップと、
前記包含関係解析ステップによって包含関係が認められた１組のノード群の間の類似度を算定する類似度算定ステップと、
前記類似度算定ステップによって算定された類似度が所定の閾値以上である場合には、包含される方のノード群を排除し、排除されずに残ったノード群を検索の対象として絞り込む検索対象絞り込みステップと、
を有することを特徴とする情報検索方法。
【請求項７】
情報の単位であるノードとノード間のリンクによって構成されたハイパードキュメントシステムの情報をコンピュータに検索させる情報検索プログラムを記録したコンピュータ読み取り可能な記録媒体において、
リンクによる結合と内容の類似性に基づいて検索の対象となるノード群を構成するノード群構成手段、
前記ノード群構成手段によって構成されたノード群のそれぞれに属する個々のノードを記憶する構成ノード記憶手段、
前記ノード群の相互の包含関係を、前記構成ノード記憶手段に記憶されている情報に基づいて解析する包含関係解析手段、
前記包含関係解析手段によって包含関係が認められた１組のノード群の間の類似度を算定する類似度算定手段、
前記類似度算定手段によって算定された類似度が所定の閾値以上である場合には、包含される方のノード群を排除し、排除されずに残ったノード群を検索の対象として絞り込む検索対象絞り込み手段、
としてコンピュータを機能させるための検索プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は情報検索装置、情報検索方法および記録媒体に関し、特に、情報の単位であるノードとノード間のリンクによって構成されたハイパードキュメントシステムを対象にして情報を検索する情報検索装置、情報検索方法および記録媒体に関する。
【０００２】
【従来の技術】
ハイパードキュメントシステムでは、取り扱われる情報をいくつかの小さな単位（ノード）に分割し、それらを関連付けて整理している（このような関連付けを示す情報を、リンクと呼ぶ）。例えば、インターネット上では、ＷＷＷ(World Wide Web)により、ハイパードキュメントシステムが構築されている。ＷＷＷの情報は、ＨＴＭＬ(Hyper Text Markup Language)で記述されている。このＨＴＭＬは、ノード間のリンクに意味的制約がない。このようにノード間のリンクに意味的制約を持たないシステムには、ドキュメントオーサ（作者）が意のままにコンテンツとリンク構造を決めることができるという利点がある。そして、このようなハイパードキュメントシステムにより、ドキュメントリーダ（読者）は、ドキュメントオーサの構築したリンク構造をたどり、そのドキュメントオーサが提供する全ての情報に対してアクセスできる。
【０００３】
ところで、インターネットなどのハイパードキュメントシステムの情報量は膨大である。そのため、ドキュメントリーダが必要な情報を見つけ出すには、情報検索を支援するシステムが必要である。そのような検索を支援する従来技術としては、以下の２つがある。
【０００４】
第１の従来技術は、予めできるだけ大量のノードを（ランダムに）スキャンして各ノードの検索インデックスを用意しておき、ドキュメントリーダからのクエリー（キーワードの組み合わせ）に対してマッチするものを提示するものである。なお、検索インデックス作成およびクエリーとのマッチングに間する要素技術として、統計的言語処理手法であるベクタースペースモデル（G. Salton & J. Allan, Text Retrieval Using the Vector Processing Model, in Proc. of SDAIR94 ）が考案されている。
【０００５】
第２の従来技術は、予めできるだけ大量のノードを（ランダムに）スキャンして、それらをトピックにより分類した木構造のディレクトリに割り当てておくものである。ドキュメントリーダは、欲する情報が含まれると考えられるトピックをディレクトリ上から探し、そこから目指す情報にアクセスする。なお、この技術を実現するための要素技術として、自然言語処理を応用した自動文書分類手法（例えば、P. Jacobs, Joining Statistics with NLP for Text Categorization, in Proc. of Applied-ACL92 ）が提案されている。さらに、メディアを画像に拡張した自動文書分類手法（United States Patent: 5526443, T. Nakayama (FXPAL), Method and apparatus for highlighting and categorizing documents using coded word tokens, issue date:1996.6.11）も考案されている。
【０００６】
【発明が解決しようとする課題】
しかし、これらの従来技術では、１つのノード（例えば、１つのＨＴＭＬ文書）を１つの検索対象単位とするため、ノードとリンクによる構造で概念を表現するというハイパードキュメントシステムの本質を捉えることができず、以下に示すような問題が生じている。
【０００７】
ある情報をいくつのノードに分割してどのように構造化するかは、ドキュメントオーサの嗜好によるものであるにもかかわらず、ノードを一単位とするような検索では、ハイパーネットワーク上に構造化されたノード群を、大局的にある１つの意味的まとまりを持つ情報として捉えることができない。つまり、従来技術による検索では、意味的に不完全な情報断片だけを検索対象とすることになり、コンテキストが検索に反映されない。
【０００８】
例えば、一人のドキュメントオーサが作成した１つの意味的まとまりをもった情報が、複数のＨＴＭＬ文書に分割されて表現されている場合、従来技術で文書検索を行うと、各ＨＴＭＬ文書が個別の検索対象となる。ここで、ドキュメントリーダが「概念Ａ」に類似する情報を検索すると、当該ドキュメントオーサが作成した情報が全体として「概念Ａ」に類似していても、分割された個々のノードが「概念Ａ」に類似していなければ、この情報（若しくは一部のノード）が検出されることはない。
【０００９】
しかも、１つのノードを検索対象単位とすると、検索要求を表す概念をハイパーネットワーク上の構造で表現することができないという問題点もある。
さらには、ドキュメントオーサが、ある１つの意味的まとまりを持つ情報を複数のノードに分割して構造化した場合、従来の検索ではそれぞれのノードが個別に出力され、冗長性が生じるという問題点もある。一人のドキュメントオーサが１つの意味的まとまりを持つ情報として作成した一連のＨＴＭＬ文書が個別に出力されると、検索結果の量が膨れ上がってしまい、目的に合致した文書を探し出すためのドキュメントリーダの労力が増加してしまう。
【００１０】
そこで、あるノードを起点として、そのノードにリンクされているＮ次のノード（Ｎ＝２，３，・・・）の特徴を比較してその類似性を判定し、類似であると判定されたＮ次ノードを、起点となるノードと合成することによって、意味的まとまりを持つ情報を１単位とする検索が考えられる。
【００１１】
しかしながら、このような方法によれば、ハイパードキュメントシステムの本質を捉えた情報検索が可能となる一方で、「意味的なまとまり」の間に包含関係が発生する場合があるため、検索結果が冗長になるという問題がある。
【００１２】
そのような場合の一例を図１０に示す。この図において、平行四辺形は、それぞれノードを示しており、また、矢印はリンクを示している。この例では、ノードＡを起点とする意味的まとまり（実線で囲繞された部分）は、ノードＢを起点とする意味的まとまり（点線で囲繞された部分）を包含している。従って、ある検索要求に対して、双方が検索結果として与えられた場合、前者を先に読んだ（ブラウジングした）ドキュメントリーダにとって、後者を読みにいく行為は冗長なものとなる。しかしながら、実際にアクセスしてみないと、冗長であるか否かは判定できないという問題点もあった。
【００１３】
本発明はこのような点に鑑みてなされたものであり、意味的まとまりを持つ情報を一単位として効率よく情報を検索できる情報検索装置を提供することを目的とする。
【００１４】
更に、本発明の別の目的は、意味的まとまりを持つ情報を一単位として効率よく情報を検索できる情報検索方法を提供することである。
更にまた、本発明の他の目的は、意味的まとまりを持つ情報を一単位として効率よく情報を検索するための情報検索プログラムを記録した記録媒体を提供することである。
【００１５】
【課題を解決するための手段】
本発明では上記課題を解決するために、情報の単位であるノードとノード間のリンクによって構成されたハイパードキュメントシステムを対象にして情報を検索する情報検索装置において、リンクによる結合と内容の類似性に基づいてノード群を構成するノード群構成手段と、前記ノード群を構成する個々のノードを記憶する構成ノード記憶手段と、所定の検索要求に対応して前記ハイパードキュメントシステムから情報を検索する情報検索手段と、前記情報検索手段の検索結果として得られた複数のノード群の相互の包含関係を、前記構成ノード記憶手段に記憶されている情報に基づいて解析する包含関係解析手段と、前記包含関係解析手段の解析結果に応じて、他のノード群に包含されているノード群を排除するノード群排除手段と、排除されずに残ったノード群を検索結果として出力する検索結果出力手段と、を有することを特徴とする情報検索装置が提供される。
【００１６】
ここで、ノード群構成手段は、リンクによる結合と内容の類似性に基づいてノード群を構成する。構成ノード記憶手段は、ノード群を構成する個々のノードを記憶する。情報検索手段は、所定の検索要求に対応してハイパードキュメントシステムから情報を検索する。包含関係解析手段は、情報検索手段の検索結果として得られた複数のノード群の相互の包含関係を、構成ノード記憶手段に記憶されている情報に基づいて解析する。ノード群排除手段は、包含関係解析手段の解析結果に応じて、他のノード群に包含されているノード群を排除する。検索結果出力手段は、排除されずに残ったノード群を検索結果として出力する。
【００１７】
また、情報の単位であるノードとノード間のリンクによって構成されたハイパードキュメントシステムを対象にして情報を検索する情報検索装置において、リンクによる結合と内容の類似性に基づいて検索の対象となるノード群を構成するノード群構成手段と、前記ノード群構成手段によって構成されたノード群のそれぞれに属する個々のノードを記憶する構成ノード記憶手段と、前記ノード群の相互の包含関係を、前記構成ノード記憶手段に記憶されている情報に基づいて解析する包含関係解析手段と、前記包含関係解析手段によって包含関係が認められた１組のノード群の間の類似度を算定する類似度算定手段と、前記類似度算定手段によって算定された類似度が所定の閾値以上である場合には、包含される方のノード群を排除し、排除されずに残ったノード群を検索の対象として絞り込む検索対象絞り込み手段と、を有することを特徴とする情報検索装置が提供される。
【００１８】
ここで、ノード群構成手段は、リンクによる結合と内容の類似性に基づいて検索の対象となるノード群を構成する。構成ノード記憶手段は、ノード群構成手段によって構成されたノード群のそれぞれに属する個々のノードを記憶する。包含関係解析手段は、ノード群の相互の包含関係を、構成ノード記憶手段に記憶されている情報に基づいて解析する。類似度算定手段は、包含関係解析手段によって包含関係が認められた１組のノード群の間の類似度を算定する。検索対象絞り込み手段は、類似度算定手段によって算定された類似度が所定の閾値以上である場合には、包含される方のノード群を排除し、排除されずに残ったノード群を検索の対象として絞り込む。
【００１９】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。
図１は、本発明の情報検索装置の実施の形態の構成例を示す図である。この図において、ノード群構成手段１は、ハイパードキュメントシステム１０に分散して配置されている情報から、内容の類似性に応じてノード群（例えば、図１０のノードＡまたはＢを起点とするノード群）を構成する。
【００２０】
構成ノード記憶手段２は、ノード群構成手段１によって構成されたノード群に属する（異なり）ノードのパス名を記憶する。なお、ここで使用するパス名とは、ノードに対してユニークに与えられる絶対アドレスのことで、例えば、ＷＷＷ（World Wide Web）であればＵＲＬ（Uniform Resource Locator）を指す。
【００２１】
情報検索手段３は、ハイパードキュメントシステム１０に配置されているノードから、検索要求に対応するノードを取得し、検索結果の候補として出力する。包含関係解析手段４は、情報検索の結果として得られたノードを入力し、そのノードを起点とするノード群を構成ノード記憶手段２から取得し、得られたノード群の相互の包含関係を解析する。
【００２２】
ノード群排除手段５は、包含関係解析手段４による解析の結果に応じて、他のノード群に包含されているノード群を排除する。
検索結果出力手段６は、ノード群排除手段５によって排除されずに残ったノード群を、最終検索結果として出力する。
【００２３】
次に、図２を参照してノード群構成手段１の構成例について説明する。図２に示すように、ノード群構成手段１は、起点ノード特徴抽出部１ａ、関連ノード取得部１ｂ、関連ノード特徴抽出部１ｃ、類似性判定部１ｄ、ノード合成部１ｅにより構成されている。
【００２４】
起点ノード特徴抽出部１ａは、起点ノードが入力されると、起点ノードの内容を解析し、その特徴を抽出する。抽出した特徴は、起点ノード特徴プロファイルとして類似性判定部１ｄに渡される。ここで、ノードの特徴に関する情報とは、そのノードの内容を特徴付ける単語とその重要度を示す値の対の集合を指す。例えば、起点ノードに出現する各単語に関する出現頻度、出現位置及び品詞の情報に基づいて重み付けすることにより、起点ノード特徴プロファイルを作成する。
【００２５】
関連ノード取得部１ｂは、起点ノードが入力された際に、そのノードからリンクが張られている２次ノードを取得するとともに、取得したノードからさらにリンクが張られているノード（関連ノード）を順次取得する。そして、他のノードへのリンクがなくなるまで同様の処理を行う。この時に取得される２次ノード以降の各ノードを、Ｎ次ノードとする（Ｎ＝２，３，４，・・・）。
【００２６】
関連ノード特徴抽出部１ｃは、関連ノード取得部１ｂが抽出したＮ次の各ノードの特徴を抽出し、関連ノード特徴プロファイルを作成する。作成した関連ノード特徴プロファイルは、類似性判定部１ｄに渡される。
【００２７】
類似性判定部１ｄは、関連ノード特徴抽出部１ｃが作成した関連ノード特徴プロファイルに基づいて、起点ノードからリンクを辿ることによりアクセス可能な全てのノードの起点ノードに対する類似性の判断処理を行う。そして、類似しているノードの内容を、ノード合成部１ｅに渡す。ノード合成部１ｅは、類似性判定部１ｄによって抽出された全てのノードを起点ノードに合成し、合成ノード（ノード群）を出力する。その結果、ノード群構成手段１からは、同一の概念により包括される合成ノード（ノード群）に対応する複数のパス名が出力される。
【００２８】
次に、図１に示す実施の形態の動作について説明する。
ノード群構成手段１は、ハイパードキュメントシステム１０に配置されている情報からノード群を生成して出力する。即ち、ノード群構成手段１は、ハイパードキュメントシステム１０に配置されているノードをランダムにスキャンし、取得したノードを起点ノードとして以下の処理を実行する。
【００２９】
関連ノード取得部１ｂは、与えられた起点ノードに関連する（リンクされている）Ｎ次のノードを順次取得する。そして、起点ノード特徴抽出部１ａと関連ノード特徴抽出部１ｃは、図３に示す処理に従って、特徴抽出処理を行う。なお、起点ノード特徴抽出部１ａと関連ノード特徴抽出部１ｃで行われる処理は同様であるので、以下の説明では起点ノード特徴抽出部１ａで行われる処理についてのみ言及する。
〔Ｓ１〕起点ノードが与えられ、その情報ソースが起点ノード特徴抽出部１ａに入力される。
〔Ｓ２〕情報ソースから、ハイパードキュメントシステム記述言語（例えば、ＨＴＭＬ）で定義されたタグを除去する。
〔Ｓ３〕既知の形態素解析技術を用いて、残されたテキストから単語を抽出する。
〔Ｓ４〕ステップＳ３で得られた単語の集合から重要単語だけを抽出する。ここで、重要単語とは情報ソースの内容を特徴付けている単語のことであり、例えば、名詞だけを重要単語とするといった方法で抽出する。
〔Ｓ５〕ステップＳ４で得られた重要単語に対して、出現頻度や出現位置を考慮して、重み付けをする。すなわち、出現頻度の高い単語ほど重要度を高くする。また、出現位置が文書の先頭に近いほど重要度を高くする。
〔Ｓ６〕最後に、重要単語とその重みとの組からなるリストを作成し、これを起点ノード特徴プロファイルとする。
【００３０】
このようにして得られた、起点ノードの特徴プロファイル（単数）は、類似性判定部１ｄに渡される。
また、前述のように、起点ノードは、関連ノード取得部１ｂにも渡されており、関連ノード取得部１ｂは、受け取ったノードの情報ソースに含まれるリンク情報を検索し、そのリンク先のノードを２次ノードとして取得する。例えば、起点ノードがＨＴＭＬで作成されていれば、アンカータグ（＜Ａ＞・・・＜／Ａ＞）で囲まれた領域内のＵＲＬ(Uniform Resource Locator)を抽出し、そのＵＲＬで指定された文書（２次ノード）を取得する。
【００３１】
そして、同様の処理を繰り返すことにより、Ｎ次のノード（関連ノード）を順次取得していき、関連ノードの集合として、関連ノード特徴抽出部１ｃに渡す。関連ノード特徴抽出部１ｃは、前述の場合と同様の処理を実行することにより、各関連ノードに対する関連ノード特徴プロファイルを作成する。その関連ノードの特徴プロファイル（一般に複数）は、類似性判定部１ｄに渡される。これにより、類似性判定部１ｄには、起点ノード特徴プロファイルと複数の関連ノード特徴プロファイルとが渡されることになる
類似性判定部１ｄでは、図４に示す処理が実行されることになる。
〔Ｓ２１〕Ｎ＝２という初期化を行う。
〔Ｓ２２〕Ｎ次ノードが存在するか否かが判定される。存在すればステップＳ２３に進み、そうでなければ処理を終了する。
〔Ｓ２３〕ｐ＝１という初期化を行う。また、Ｎ次ノードの個数をｍとする。
〔Ｓ２４〕ｐとｍの大小を比較して、ｐ＞ｍであればステップＳ２９に進み、そうでなければステップＳ２５に進む。
〔Ｓ２５〕起点ノードとｐ番目のＮ次ノードの類似度を前述の方法（既知のベクター内積演算手法）で計算する。
〔Ｓ２６〕ステップＳ２５で得られた類似度の値と閾値を比較して、類似度＞閾値であれば、ステップＳ２７に進み、そうでなければ、ステップＳ２８に進む。ここで、閾値は予め設定された値であり、その大小で類似性の許容範囲を調整する。
〔Ｓ２７〕ｐ番目のＮ次ノードを、起点ノードに合成するノードの候補として記憶する。
〔Ｓ２８〕ｐの値に１を加算して、ステップＳ２４に進む。
〔Ｓ２９〕Ｎの値に１を加算して、ステップＳ２２に進む。
【００３２】
これにより、起点ノードからリンクを辿ることによりアクセス可能な全てのノードの中から、起点ノードに類似した内容を有するものが抽出される。
ここで、ノード１１を起点ノードとして入力する場合を考える（図２参照）。なお、ノード１１からは、２つのノード１２，１３へリンクが張られている。これらのノード１２，１３が２次ノードとなる。ノード１２，１３からも他のノードへリンクが張られており、最終的にノード１４〜１６までリンクが張られている。
【００３３】
ノード１１がノード群構成手段１に入力されると、起点ノード特徴抽出部１ａによって、その内容が解析され、ノード１１の特徴が起点ノード特徴プロファイルとして類似性判定部１ｄに渡される。また、関連ノード取得部１ｂによって、ノード１１からリンクが張られているノード１２，１３のノードパス名を抽出し、ノード１２，１３を取得する。
【００３４】
さらに、ノード１２，１３からリンクを辿ることによりアクセスできるノードをＮ次のノード１４〜１６までを全て取得する。取得したノードは、関連ノード特徴抽出部１ｃに渡される。そして、関連ノード特徴抽出部１ｃによって各ノードの内容の特徴が抽出され、関連ノード特徴プロファイルが作成される。すると、類似性判定部１ｄにより、ノード１１に類似する内容を有している関連ノードが全て抽出される。そして、抽出された全てのノードが、ノード合成部１ｅにより起点ノードに合成され、合成ノードが生成される。
【００３５】
以上の処理は、異なるノードを起点として繰り返され、その結果として、類似性を有する複数のノードから構成される合成ノード（ノード群）が複数生成されて出力される。
【００３６】
以上のようにして生成された合成ノードは、構成ノード記憶手段２に供給される。
構成ノード記憶手段２は、以上のようにして生成された合成ノードを構成する各ノードに対応するパス名を記憶する。
【００３７】
情報検索手段３は、ハイパードキュメントシステム１０から、入力された検索要求に対応するノードを検索する。この検索方法としては、例えば、ハイパードキュメントシステム１０からできるだけ大量のノードをスキャンして、各ノードの検索インデックスを用意しておき、入力された検索要求（キーワードの組み合わせ）に該当するものを出力するようにすればよい。
【００３８】
包含関係解析手段４は、情報検索手段３から供給された検索結果の候補であるノードを入力し、そのノードを起点とする合成ノード｛Ｇ1 ，Ｇ2 ，Ｇ3 ，・・・，ＧN ｝を構成ノード記憶手段２から検索する。そして、得られた合成ノードの包含関係を図５に示すフローチャートに従って解析する。なお、以下の処理はすべて包含関係解析手段４によって実行される。
［Ｓ４１］情報検索手段３から供給されたノードを含む合成ノードを、構成ノード記憶手段２から検索し、得られた合成ノードのノード群列｛Ｇ1 ，Ｇ2 ，Ｇ3 ，・・・，ＧN ｝を入力する。
［Ｓ４２］変数ｉを値“１”に初期設定し、また、排除ノード群リストの内容を空（＝ＮＵＬＬ）の状態に初期設定する。
［Ｓ４３］第ｉ番目のノード群（合成ノード）が、排除ノード群リストに含まれているか否かを判定し、含まれている場合にはステップＳ４９に進み、含まれていない場合にはステップＳ４４に進む。
［Ｓ４４］変数ｋに値（ｉ＋１）を代入する。
［Ｓ４５］第ｉ番目の合成ノードＧi を構成する全てのノードが、第ｋ（＝ｉ＋１）番目の合成ノードＧk を構成する全てのノードに包含されているか否かを判定し、包含されている場合にはステップＳ４７に進み、包含されていないか、または、Ｇi とＧk が等しい場合にはステップＳ４６に進む。
［Ｓ４６］第ｉ番目の合成ノードＧi を構成する全てのノードが、第ｋ（＝ｉ＋１）番目の合成ノードＧk を構成する全てのノードを包含しているか、または、これらが等しいか否かを判定し、包含しているか、または、等しい場合にはステップＳ４８に進み、包含していない場合にはステップＳ５０に進む。
［Ｓ４７］Ｇi を排除ノード群リストに追加する。
［Ｓ４８］Ｇk を排除ノード群リストに追加する。
［Ｓ４９］変数ｉの値を１だけインクリメントする。
［Ｓ５０］変数ｋの値を１だけインクリメントする。
［Ｓ５１］変数ｉの値が（Ｎ−１）の値と等しいか否かを判定し、これらが等しい場合にはステップＳ５３に進み、また、等しくない場合にはステップＳ４３に戻る。
［Ｓ５２］変数ｋの値がＮの値よりも大きいか否かを判定し、大きいと判定した場合にはステップＳ４９に進み、また、そうでない場合にはステップＳ４５に戻る。
［Ｓ５３］排除ノード群リストを出力する。
【００３９】
以上の処理により、他のノードに包含されている合成ノードが排除の対象として出力される。
ノード群排除手段５は、包含関係解析手段４から出力された排除ノード群リストを参照して、検索結果の合成ノードから不要なものを排除する。
【００４０】
検索結果出力手段６は、不要なノードが排除されたノード群を検索結果として出力する。
以上の実施の形態によれば、検索結果として、他のノードに包含されていない合成ノード（ノード群）だけを得ることができる。例えば、図１０に示すノードＡとノードＢとが検索の結果として得られた場合には、ノードＡを起点とするノード群のみが選択されて出力されることになる。
【００４１】
なお、以上の実施の形態においては、情報検索手段３は、ハイパードキュメントシステム１０から情報を検索するようにしたが、構成ノード記憶手段２に対してノード名とともに検索に必要な情報（例えば、各ノードの検索インデックス）を記憶させることにより、構成ノード記憶手段２から検索するようにすることも可能である。
【００４２】
次に、図６を参照して本発明の情報検索装置の第２の実施の形態について説明する。
図６に示す第２の実施の形態は、検索要求がリンクによる結合と内容の類似性をもとに構成されたノード群である場合について、検索要求に包含されるノード群を検索結果から排除する機能を付加した１実施例を示すものである。
【００４３】
同図において、図１の場合と対応する部分には同一の符号を付してあるのでその部分の説明は省略する。
検索要求構成ノード記憶手段２１は、検索要求を構成するノードのパス名を記憶して保持する。対検索要求包含関係解析手段２２は、検索結果の候補（ノード群）から検索要求のノード群に包含されるものを排除する。即ち、対検索要求包含関係解析手段２２は、検索要求構成ノード記憶手段に２１に保持される情報と、構成ノード記憶手段２に保持される情報と、情報検索手段３の検索結果とを参照して、検索要求と検索結果の候補の相互の包含関係を解析する。対検索要求ノード群排除手段２３は、対検索要求包含関係解析手段２２の解析結果を参照して、検索結果の候補の中から、検索要求に含まれているノード群を排除する。
【００４４】
検索結果出力手段２５は、対検索要求ノード群排除手段２３とノード群排除手段５のいずれによっても排除されなかったノード群を最終検索結果として出力する。
【００４５】
次に、以上の実施の形態の動作について説明する。なお、ノード群構成手段１、構成ノード記憶手段２、包含関係解析手段４、および、ノード群排除手段５の動作は、図１の場合と同様であるので、その説明は省略する。
【００４６】
ドキュメントリーダが検索要求を入力すると、検索要求構成ノード記憶手段２１は、検索要求を構成する個々のノードのパス名を記憶する。対検索要求包含関係解析手段２２は、図７に示す処理に従って、検索結果の候補の中から、検索要求に包含されるものを解析により抽出する。
［Ｓ７１］情報検索手段３によって得られたノードを起点とする合成ノードを、構成ノード記憶手段２から取得することによって得られたノード群列｛Ｇ1 ，Ｇ2 ，Ｇ3 ，・・・，ＧN ｝と、検索要求のノード群ＧQ とを入力する。
［Ｓ７２］変数ｉを値“１”に初期設定し、排除ノード群リストの内容を空（ＮＵＬＬ）にする。
［Ｓ７３］第ｉ番目のノード群Ｇi を構成する全ての（異なり）ノードが、ＧQ を構成するノードの集合に含まれるか否かを判定し、含まれる場合にはステップＳ７４に進み、含まれない場合にはステップＳ７５に進む。
［Ｓ７４］ノード群列Ｇi を排除ノード群リストに加える。
［Ｓ７５］変数ｉの値を“１”だけインクリメントする。
［Ｓ７６］変数ｉの値がＮと等しいか否かを判定し、等しい場合にはステップＳ７７に進み、等しくない場合にはステップＳ７３に戻る。
［Ｓ７７］排除ノード群リストを出力する。
【００４７】
以上の処理によれば、検索結果の候補であるノード群列｛Ｇ1 ，Ｇ2 ，Ｇ3 ，・・・，ＧN ｝のうち、検索要求ＧQ に包含されているものが選択され、排除ノード群リストとして出力される。
【００４８】
対検索要求ノード群排除手段２３は、検索結果の候補から、排除ノード群リストに含まれているものを排除し、その結果を出力する。
検索結果出力手段２５は、対検索要求ノード群排除手段２３から出力されたノード群（検索要求のノード群に包含されていないノード群）と、ノード群排除手段５から出力されたノード群（他のノード群に包含されていないノード群）とを比較し、双方に含まれているノード群を検索結果として出力する。
【００４９】
以上のような実施の形態によれば、複数のノード群からなる検索要求が入力された場合に、得られた検索結果の候補の中から、他のノード群に包含されているノード群と、検索要求に包含されているノード群とが排除され、最終的な検索結果として出力されることになる。従って、入力されたノード群自体が検索結果として出力されることを防止するとともに、相互に重複した情報が検索結果として出力されることを防止することができるので、効率的な情報の検索を行うことが可能となる。
【００５０】
なお、以上の実施の形態においては、検索要求に包含されるノード群の排除と、他のノード群に包含されるノード群の排除とを並行して行うようにしたが、これらを順次実行するようにしてもよい。例えば、検索要求に含まれているノード群を排除した後、他のノード群に含まれているノード群を排除するといった具合である。
【００５１】
次に、図８を参照して本発明の第３の実施の形態の構成例について説明する。この実施の形態は、ドキュメントリーダから検索要求が入力される以前に、予め、検索対象となるノード群の包含関係を解析しておき、他のノード群に包含されるノード群を検索対象から排除することで、検索要求入力後の動作時間（ランタイム）を減少させるものである。
【００５２】
この図において、ノード群構成手段１は、ハイパードキュメントシステム１０に配置されているノードから、その内容の類似性とリンクに基づいて、検索の単位となるノード群を生成する。
【００５３】
構成ノード記憶手段２は、ノード群構成手段１によって構成されたノード群に含まれている個々のノードに対応するパス名を記憶する。
包含関係解析手段３は、構成ノード記憶手段２に記憶されているノード群の相互の包含関係を解析する。
【００５４】
類似度算定手段４１は、包含関係にある２組のノード群の内容の類似度を算定し、その結果を包含関係解析手段３に対して出力する。
検索対象絞り込み手段４２は、他のノード群に包含されるとともに、類似度が閾値を超えるノード群を排除して出力する。
【００５５】
次に、以上の実施の形態の動作について説明する。
ノード群構成手段１によって構成されたノード群は、構成ノード記憶手段２に記憶される。包含関係解析手段３と類似度算定手段４１は、図９を参照して後述する処理を連携して実行し、他のノード群に包含されるとともに、相互の類似度が高いノード群を排除するための排除ノード群リストを生成する。
【００５６】
即ち、単純に包含関係だけを解析したのでは、本来、検索結果として返されるべきノード群であっても、それが他の（検索結果として返されない）ノード群に包含されている場合には検索結果として出力されないという不都合が生じてしまう。そこで、類似度算定手段４１において、包含関係にあるノード群間の内容の類似度を算定して、内容が類似であると判定された場合にのみ排除の対象とする。
【００５７】
図９に示すフローチャートが開始されると、以下のような処理が実行されることになる。
［Ｓ９１］包含関係解析手段３は、構成ノード記憶手段２に記憶されているノード群列｛Ｇ1 ，Ｇ2 ，Ｇ3 ，・・・，ＧN ｝を入力する。
［Ｓ９２］変数ｉを値“１”に初期設定し、また、排除ノード群リストの内容を空（＝ＮＵＬＬ）の状態に初期設定する。
［Ｓ９３］第ｉ番目のノード群（合成ノード）Ｇi が、排除ノード群リストに含まれている（Ｇi が排除ノード群リストの要素である）か否かを判定し、含まれている場合にはステップＳ１０１に進み、含まれていない場合にはステップＳ９４に進む。
［Ｓ９４］変数ｋに値（ｉ＋１）を代入する。
［Ｓ９５］第ｉ番目の合成ノードＧi を構成する全てのノードが、第ｋ（＝ｉ＋１）番目の合成ノードＧk を構成する全てのノードに包含されているか否かを判定し、包含されている場合にはステップＳ９７に進み、包含されていないか、または、Ｇi とＧk が等しい場合にはステップＳ９６に進む。
［Ｓ９６］第ｉ番目の合成ノードＧi を構成する全てのノードが、第ｋ（＝ｉ＋１）番目の合成ノードＧk を構成する全てのノードを包含しているか、または、これらが等しいか否かを判定し、包含しているか、または、等しい場合にはステップＳ９８に進み、包含していない場合にはステップＳ１０２に進む。
［Ｓ９７］類似度算定手段４１は、Ｇi とＧk の類似度を算定する。ここでの類似度の算定方法としては、まず、Ｇi とＧk を構成する全てのノードをそれぞれ合成する。次に、図３に示す処理を実行し、各合成ノードの内容の特徴を表すプロファイルを作成してそれらの類似度を算定する。そして、包含関係解析手段３は、類似度が予め定められた閾値より大であれば類似であると判定し、ステップＳ９９に進み、また、小であれば類似でないと判定してステップＳ１０１に進む。
［Ｓ９８］ステップＳ９７と同様の処理により、Ｇk とＧi の類似度を算定し、これらが類似であると判定した場合には、ステップＳ１００に進み、また、類似ではないと判定した場合にはステップ１０２に進む。
［Ｓ９９］Ｇi を排除ノード群リストに追加する。
［Ｓ１００］Ｇk を排除ノード群リストに追加する。
［Ｓ１０１］変数ｉの値を１だけインクリメントする。
［Ｓ１０２］変数ｋの値を１だけインクリメントする。
［Ｓ１０３］変数ｉの値が（Ｎ−１）と等しいか否かを判定し、これらが等しい場合にはステップＳ１０５に進み、また、等しくない場合にはステップＳ９３に戻る。
［Ｓ１０４］変数ｋの値がＮの値よりも大きいか否かを判定し、大きいと判定した場合にはステップＳ１０１に進み、また、そうでない場合にはステップＳ９５に戻る。
［Ｓ１０５］排除ノード群リストを出力する。
【００５８】
以上の処理により、検索対象となるノード群のうち、他のノードに包含されるとともに、類似度が閾値を超えるノード群が排除ノード群リストとして出力される。
【００５９】
このようにして、他のノード群に包含されるとともに、類似度が所定の閾値を超えるノード群は、検索対象絞り込み手段４２によって排除される。そして、排除されなかったノード群が新たな検索対象となる。
【００６０】
以上の実施の形態によれば、ドキュメントリーダは、排除されなかったノード群を対象とすることにより、効率的な検索を行うことが可能となる。
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、情報検索装置が有すべき機能の処理内容は、コンピュータで読み取り可能な記録媒体に記録されたプログラムに記述されており、このプログラムをコンピュータで実行することにより、上記処理がコンピュータで実現される。
【００６１】
コンピュータで読み取り可能な記録媒体としては、磁気記録装置や半導体メモリ等がある。市場に流通させる場合には、ＣＤ−ＲＯＭ(Compact Disk Read Only Memory) やフロッピーディスク等の可搬型記録媒体にプログラムを格納して流通させたり、ネットワークを介して接続されたコンピュータの記憶装置に格納しておき、ネットワークを通じて他のコンピュータに転送することもできる。コンピュータで実行する際には、コンピュータ内のハードディスク装置等にプログラムを格納しておき、メインメモリにロードして実行する。
【００６２】
【発明の効果】
以上説明したように本発明に係わる情報検索装置では、リンクによる結合と内容の類似性に応じてノード群を構成し、所定の検索要求があった場合には、該当するノード群を取得し、取得されたノード群の中から他のノード群に包含されているものを排除して出力するようにしたので、重複した情報を閲覧することを避けることができる。
【００６３】
また、本発明に係わる情報検索装置では、リンクによる結合と内容の類似性に応じてノード群を構成し、構成されたノード群から包含関係を有するノード群を抽出するとともに、それぞれの類似度を算定し、類似度が所定の閾値よりも大きいノード群に対しては、包含される側のノード群を排除するようにしたので、情報の検索を行う場合にランタイムを短縮することが可能となる。
【図面の簡単な説明】
【図１】本発明の実施の形態の構成例である。
【図２】図１に示すノード群構成手段の構成例を示す図である。
【図３】図２に示す起点ノード特徴抽出部および関連ノード特徴抽出部において実行される処理の一例を説明するフローチャートである。
【図４】図２に示す類似性判定部において実行される処理の１例を説明するフローチャートである。
【図５】図１に示す包含関係解析手段において実行される処理の１例を説明するフローチャートである。
【図６】本発明の第２の実施の形態の構成例を示す図である。
【図７】図６に示す対検索要求包含関係解析手段において実行される処理の１例を説明する図である。
【図８】本発明の第３の実施の形態の構成例を示す図である。
【図９】図８に示す包含関係解析手段と類似度算定手段によって実行される処理の１例を説明するフローチャートである。
【図１０】包含関係にあるノード群を説明する図である。
【符号の説明】
１  ノード群構成手段
２  構成ノード記憶手段
３  情報検索手段
４  包含関係解析手段
５  ノード群排除手段
６  検索結果出力手段
２１  検索要求構成ノード記憶手段
２２  対検索要求包含関係解析手段
２３  対検索要求ノード群排除手段
２５  検索結果出力手段
４１  類似度算定手段
４２  検索対象絞り込み手段
【図１】
0003637756.tif 000002
【図２】
0003637756.tif 000003
【図３】
0003637756.tif 000004
【図４】
0003637756.tif 000005
【図５】
0003637756.tif 000006
【図６】
0003637756.tif 000007
【図７】
0003637756.tif 000008
【図８】
0003637756.tif 000009
【図９】
0003637756.tif 000010
【図１０】
0003637756.tif 000011