(57)【要約】【課題】  収集された情報を効率的に検索できるインデックスを作成する。【解決手段】  本発明は、収集した情報に基づいて、データベースを検索するためのインデックスを作成する装置である。前記装置は、特定の概念ごとに相互に関連付けられた複数のフレーズを含む辞書と、テキスト文の入力を受け付ける入力インターフェース部、前記テキスト文から複数の語をトークンとして切り出すテキスト処理部と、前記切り出した複数のトークンどうしの接続関係を表現した有向グラフを生成する有向グラフ生成部と、前記辞書を参照しながら前記有向グラフ内を探索し、探索対象フレーズが前記辞書中に発見された場合に、前記有向グラフを展開する有向グラフ探索部と、前記有向グラフ内における複数のトークンに基づいてインデックスを作成するインデックス作成部とを備える。【選択図】  図４
2019153271.tif 000002
【特許請求の範囲】
【請求項１】
テキスト文を含むリソースに基づいて、データベースを検索するためのインデックスを作成する装置であって、
特定の概念ごとに、相互に関連付けられた複数のフレーズを含む辞書と、
前記リソースの入力を受け付ける入力インターフェース部と、
前記受け付けたリソースのテキスト文から複数の語をトークンとして切り出すための処理を行うテキスト処理部と、
前記テキスト文に従って、前記切り出した複数のトークンどうしの接続関係を表現した有向グラフを生成する有向グラフ生成部と、
探索対象フレーズに基づいて前記有向グラフ内を探索し、前記探索対象フレーズが前記辞書中に発見される場合に、前記有向グラフ内における前記探索対象フレーズが顕出した箇所を特定する有向グラフ探索部と、
前記有向グラフ内における複数のトークンに基づいて、前記リソースとの関連付けを示すインデックスを作成するインデックス作成部と、を備え、
前記有向グラフ探索部は、
前記有向グラフ内における少なくとも１つのトークンを前記探索対象フレーズに設定し、前記設定した探索対象フレーズに基づいて前記辞書を参照し、
前記有向グラフ生成部は、
前記辞書に基づいて、前記探索対象フレーズに関連付けられた少なくとも１つのフレーズに基づく新たなトークンを前記有向グラフに追加することによって、前記有向グラフを更新する、
装置。
【請求項２】
前記有向グラフ生成部は、前記複数のトークンのうちの隣接するトークンどうしをノードによって接続した前記有向グラフを生成する、請求項１に記載の装置。
【請求項３】
前記有向グラフ生成部は、前記有向グラフ内における前記顕出した箇所の前後のノードに、前記辞書中に発見された前記探索対象フレーズに関連付けられた前記少なくとも１つのフレーズを接続する、請求項２に記載の装置。
【請求項４】
前記有向グラフ探索部は、前記有向グラフ生成部によって更新された有向グラフを探索する、請求項１に記載の装置。
【請求項５】
前記有向グラフ探索部は、前記更新された有向グラフにおいて既に探索し終えたトークンに対する再探索が回避されるように、前記更新された有向グラフ内を探索する、請求項４に記載の装置。
【請求項６】
前記有向グラフは、前記複数のトークンのうちの隣接するトークンどうしを接続する複数のノードを含み、
前記有向グラフ探索部は、前記探索をし終えたトークンに関連付けられたノードを探索済みノードとして記憶し、前記探索済みノード以外のノードに接続されたトークンに対して再探索する、
請求項５に記載の装置。
【請求項７】
前記装置は、前記辞書に含まれる前記複数のフレーズに基づいて構成される木構造を示すデータ配列をさらに備え、前記木構造は、前記複数のフレーズのそれぞれに対応する順序付きノードを含み、
前記有向グラフ探索部は、前記木構造を参照しながら、前記有向グラフ内を探索する、
請求項１に記載の装置。
【請求項８】
前記有向グラフ探索部は、前記探索対象フレーズが前記木構造における少なくとも１つの前記順序付きノードに対応する少なくとも１つのフレーズと一致する場合に、前記有向グラフ内に前記探索対象フレーズが顕出したと判断する、請求項７に記載の装置。
【請求項９】
前記有向グラフ生成部は、前記一致する探索対象フレーズに関連付けられた、前記辞書における少なくとも１つのフレーズに基づく新たなトークンを前記有向グラフに追加することによって、前記有向グラフを更新する、請求項８に記載の装置。
【請求項１０】
前記インデックス作成部は、更新された前記有向グラフ内における複数のトークンに基づいてＮ−ｇｒａｍを抽出し、前記抽出したＮ−ｇｒａｍに基づいて、前記インデックスを作成する、請求項１に記載の装置。
【請求項１１】
前記インデックス作成部は、前記Ｎ−ｇｒａｍとして、単語ベースのＮ−ｇｒａｍを抽出する、請求項１０に記載の装置。
【請求項１２】
請求項１に記載された装置により作成されたインデックスと、
前記インデックスに関連付けられた前記リソースに関するリソース情報ファイルと、
検索クエリに基づいて前記インデックスを検索し、該検索の結果に基づいて前記リソース情報ファイルから少なくとも１つのリソースを特定し、前記特定した少なくとも１つのリソースを示す検索結果を出力するクエリサーバと、を備える検索装置であって、
前記クエリサーバは、前記特定した少なくとも１つのリソースから得られる、前記少なくとも１つのリソースにおけるフレーズに関連する所定の関連フレーズを含む有向グラフに基づいて、前記少なくとも１つのリソースが特定された根拠となった根拠フレーズ及び前記フレーズに関連付けられた前記少なくとも１つのリソースにおける元フレーズを特定し、
前記検索結果は、前記根拠フレーズ及び前記元フレーズを含む、
検索装置。
【請求項１３】
テキスト文を含むリソースに基づいて、データベースを検索するためのインデックスを作成する装置の作動方法であって、
特定の概念ごとに、相互に関連付けられた複数のフレーズを含む辞書を、前記装置のプロセッサによってアクセスされるメモリに展開することと、
入力インターフェース部を介して、前記リソースの入力を受け付けることと、
前記受け付けたリソースのテキスト文から複数の語をトークンとして切り出すためのテキスト処理を行うことと、
前記テキスト文に従って、前記切り出した複数のトークンどうしの接続関係を表現した有向グラフを生成することと、
探索対象フレーズに基づいて前記有向グラフ内を探索することと、
前記有向グラフ内における複数のトークンに基づいて、前記リソースとの関連付けを示すインデックスを作成することと、を含み、
前記有向グラフ内を探索することは、
前記有向グラフ内における少なくとも１つのトークンを前記探索対象フレーズに設定し、前記設定した探索対象フレーズに基づいて前記辞書を参照し、前記探索対象フレーズが前記辞書中に発見される場合に、前記有向グラフ内における前記探索対象フレーズが顕出した箇所を特定することを含み、
前記有向グラフを生成することは、
前記辞書に基づいて、前記探索対象フレーズに関連付けられた少なくとも１つのフレーズに基づく新たなトークンを前記有向グラフに追加することによって、前記有向グラフを更新することを含む、
装置の作動方法。
【請求項１４】
前記有向グラフを生成することは、前記複数のトークンのうちの隣接するトークンどうしをノードによって接続した前記有向グラフを生成することを含む、請求項１３に記載の方法。
【請求項１５】
前記有向グラフを生成することは、前記有向グラフ内における前記顕出した箇所の前後のノードに、前記辞書中に発見された前記探索対象フレーズに関連付けられた前記少なくとも１つのフレーズを接続する、請求項１４に記載の方法。
【請求項１６】
前記有向グラフを探索することは、前記更新された有向グラフを新たな探索対象の有向グラフとして探索する、請求項１３に記載の方法。
【請求項１７】
前記インデックスを作成することは、更新された前記有向グラフ内における複数の語に基づいてＮ−ｇｒａｍを抽出し、前記抽出したＮ−ｇｒａｍに基づいて、前記インデックスを作成することを含む、請求項１３に記載の方法。
【請求項１８】
前記インデックスを作成することは、前記Ｎ−ｇｒａｍとして、単語ベースのＮ−ｇｒａｍを抽出する、請求項１７に記載の方法。
【請求項１９】
検索クエリに基づいてインデックスを検索し、該検索の結果に基づいてリソース情報ファイルから少なくとも１つのリソースを特定することと、
前記特定した少なくとも１つのリソースから得られる、前記少なくとも１つのリソースにおけるフレーズに関連する所定の関連フレーズを含む有向グラフに基づいて、前記少なくとも１つのリソースが特定された根拠となった根拠フレーズ及び前記フレーズに関連付けられた前記所定のリソースにおける元フレーズを特定することと、
前記少なくとも１つのリソース並びに前記根拠フレーズ及び前記元フレーズを示す情報を検索結果として出力することと、
を含む検索装置の作動方法。
【請求項２０】
コンピューティングデバイスに、請求項１３に記載の方法を実現させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報検索技術に関し、特に、収集された情報に基づいてデータベースを検索するためのインデックスを作成するための装置及び方法、並びに該方法を実行するためのプログラムに関する。
【背景技術】
【０００２】
現在、コンピュータシステムを用いた様々な情報検索サービスが提供されている。例えば、いわゆるインターネット検索は、インターネット上に分散する膨大な情報（リソース）を検索するためのＷｅｂサイト上の情報検索サービスであり、典型的には、サービス提供者における検索エンジンと呼ばれるサーバプログラムが、ユーザから与えられた検索クエリに基づいてインデックス検索を行って、ユーザにその検索の結果を提供する。このような情報検索サービスでは、典型的には、検索エンジンが、予め、クローラと呼ばれるロボットエージェントによりインターネット上のＷｅｂページを巡回訪問させ、訪問したＷｅｂページの情報を収集、解析し、これにより、データベースを検索するためのインデックスを作成する。ユーザは、Ｗｅｂブラウザを介して、検索サイトにアクセスし、検索したいテキスト（検索クエリ）を入力すると、検索エンジンは、検索クエリを解析して、インデックスを検索し、所定のランキングアルゴリズムに基づいて抽出された結果をスコアリングして、これらをスコア順にソートしたものを検索結果として、ユーザに提供する。
【０００３】
このような従来のインデックス型検索エンジンは、予め、クローラによって収集された情報に従ってそのままインデックスを作成しているため、ユーザは、インデックス化された情報のみに基づいた検索結果を得ることになる。このため、例えば下記特許文献１は、インデックス基準に従って１つ又はそれ以上の横断検索にインデックスを付与し、クエリをインデックス基準の１つ又はそれ以上と比較し、クエリをインデックス基準とマッチさせ、クエリに関するインデックス基準と関連付けられた１つ又はそれ以上のインデックス付き横断検索からの結果を提供する技術を提案している。
【０００４】
一方、下記特許文献２は、高精度な翻訳文を得るために、原文をフレーズに分割し、パラフレーズ情報に基づいて１以上の各フレーズと対になるパラフレーズを取得し、１以上のフレーズと１以上のパラフレーズを用いてフレーズの集合を含むパラフレーズラティスを取得する機械翻訳装置を開示している。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１５−１３３１５１号公報
【特許文献２】特開２０１１−１８０８２３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述のような情報検索サービスは、人々のあらゆる社会活動の中に深く浸透しており、例えば、医療分野においても例外ではない。
【０００７】
例えば、新しい治療法や薬の候補が標準治療として認められるためには、臨床試験を実施し、そのような治療法や薬の有効性及び安全性などを確認する必要がある。典型的には、医師などの医療従事者は、自身の専門的知識に基づき、治療の内容や意義、副作用など想定されるあらゆる事柄を考慮して、臨床試験計画を策定する。このため、医療従事者は、臨床試験計画の策定にあたって、被験者の病気に関連する各種の情報（例えば、病名や薬名など）を漏れのないように収集する必要がある。例えば、医療従事者は、関連情報を手掛かりにしてデータベースシステムから他の臨床試験の情報や学術論文などを抽出し、それに基づいて実施手順を決定していく。
【０００８】
しかしながら、実際問題として、一つの特定の概念に、一つの特定の語ないし表現（フレーズ）が一意に定められているわけではなく、通常、一つの特定の概念に対して、複数のフレーズが存在する。特に、医療分野のような専門分野においては、一つの特定の概念に対して、複数のフレーズ、とりわけ、それらの類義語や同義語、関連語、略語、及び外国語、さらには、これらの語に基づく派生語など（以下、それぞれを「関連フレーズ」といい、これらをまとめて「関連フレーズ群」という。）が多く存在している。
【０００９】
したがって、仮に、医療従事者が、偏った関連情報（本人は、通常、該情報が偏っているという認識はない。）に基づいてデータベースシステムを検索した場合、適切な情報がヒットしない可能性があり、これにより、臨床試験計画の策定に影響を及ぼす可能性もある。
【００１０】
しかしながら、既存のインデックス型検索エンジンは、上述したように、収集された情報から直接的に得られる見出し語のみに基づいてインデックスを作成しているため、このような見出し語のみに基づいた検索結果を得ることができるに過ぎないか、或いは、検索クエリとして与えられた特定の語がインデックスに見出し語として存在しない場合、該特定の語に近いと思われる代替語（例えば誤表記に対する正しい表記）を選択して、それに基づいて検索を実行するに過ぎず、検索クエリに基づいて与えられる語の範囲が制限的であった。
【００１１】
また、特許文献１に示される情報検索技術は、与えられた検索語に基づいて、インデックス基準に関連付けられたインデックスを横断的に検索し、その結果を提供するものであるが、与えられた検索クエリにのみ関連する語がインデックス化されるに過ぎず、やはり、検索クエリに基づいて与えられる語の範囲が制限的であった。
【００１２】
さらに、特許文献２に示される機械翻訳装置は、原文のフレーズをパラフレーズすることで、フレーズの集合を得ているものの、該得られるフレーズの集合は、単に、原文のフレーズに直接対応するパラフレーズを用いているに過ぎない。また、特許文献２は、機械翻訳技術に向けられており、検索エンジンに用いられるようなインデックスの作成技術にそのまま応用することはできない。
【００１３】
したがって、医療分野のような専門分野においては、特定のフレーズに基づいて、関連フレーズ群を幅広く効率的に検索する技術が望まれるところ、上記従来の情報検索技術は、十分とはいえなかった。
【００１４】
さらに、ユーザは、検索結果を提供されるにあたり、該検索結果が抽出されることになった根拠が認識できれば、次の検索に利用することができ、便利である。とりわけ、検索結果が検索クエリのフレーズから直接的にヒットしたものでなく、その関連フレーズによってヒットしたものである場合、ユーザは、どのような関連フレーズでヒットしたかを知ることが必要になる。
【００１５】
そこで、本発明は、インデックス型検索エンジンにおいて、収集された情報を効率的に検索することができるインデックスを作成する技術を提供することを目的とする。
【００１６】
具体的には、本発明の目的の一つは、収集されたリソースに含まれる特定のフレーズのみならず、その類義語や同義語、関連語、略語、及び外国語、さらには、これらの語に基づく派生語などにまで拡張したフレーズを見出し語とするインデックスを作成するための技術を提供することである。
【００１７】
また、本発明の目的の一つは、ユーザからの検索クエリが、該インデックス作成の基となった収集された情報に含まれるフレーズ以外のフレーズからなるものであっても、該情報が効果的に検索され、抽出されるようにする技術を提供することである。
【００１８】
さらに、本発明の目的の一つは、該ユーザが、該結果が抽出されることになった根拠を認識できるようにする技術を提供することである。
【課題を解決するための手段】
【００１９】
上記課題を解決するための本発明は、以下に示す発明特定事項乃至は技術的特徴を含んで構成される。
【００２０】
ある観点に従う本発明は、テキスト文を含むリソースに基づいて、データベースを検索するためのインデックスを作成する装置である。前記装置は、例えば、特定の概念ごとに、相互に関連付けられた複数のフレーズを含む辞書と、前記リソースの入力を受け付ける入力インターフェース部と、前記受け付けたリソースのテキスト文から複数のフレーズをトークンとして切り出すための処理を行うテキスト処理部と、前記テキスト文に従って、前記切り出した複数のトークンどうしの接続関係を表現した有向グラフ（ラティス）を生成する有向グラフ生成部と、探索対象フレーズに基づいて前記有向グラフ内を探索し、前記探索対象フレーズが前記辞書中に発見される場合に、前記有向グラフ内における前記探索対象タームが顕出した箇所を特定する有向グラフ探索部と、前記有向グラフ内における複数のトークンに基づいて、前記リソースとの関連付けを示すインデックスを作成するインデックス作成部と、を備え得る。前記有向グラフ探索部は、前記有向グラフ内における少なくとも１つのトークンを前記探索対象フレーズに設定し、前記設定した探索対象フレーズに基づいて前記辞書を参照するように構成され得る。また、前記有向グラフ生成部は、前記辞書に基づいて、前記探索対象フレーズに関連付けられた少なくとも１つのフレーズに基づく新たなトークンを前記有向グラフに追加することによって、前記有向グラフを更新するように構成され得る。
【００２１】
これにより、前記装置は、リソースのテキスト文に含まれるフレーズのみならず、該フレーズに対するパラフレーズを含む関連フレーズ群のそれぞれを該リソースの見出し語とするインデックスを作成することができるようになる。また、前記装置は、テキスト文に基づいて生成した有向グラフを更新しながら探索を進めていくので、該テキスト文に含まれるフレーズに対する直接的なパラフレーズのみならず、更新された時点の有向グラフに含まれるフレーズに対する間接的ないしは派生的なパラフレーズを関連フレーズ群とすることができる。
【００２２】
前記テキスト処理部は、前記テキスト文に基づいて所定の構文解析を行って前記複数の語を前記トークンとして切り出すように構成され得る。これにより、前記テキスト文に基づく有向グラフを生成することができるようになる。
【００２３】
前記有向グラフ生成部は、前記複数のトークンのうちの隣接するトークンどうしをノードによって接続した前記有向グラフを生成するように構成され得る。前記有向グラフは、前記トークンをエッジのラベルとして定義し、前記エッジを前記ノードによって接続することにより表現されるデータ構造であり得る。
【００２４】
前記有向グラフ生成部は、前記有向グラフ内における前記顕出した箇所の前後のノードに、前記辞書中に発見された前記探索対象フレーズに関連付けられた前記少なくとも１つのフレーズを接続するように構成され得る。
【００２５】
前記有向グラフ探索部は、前記有向グラフ生成部によって更新された有向グラフを探索するように構成され得る。これにより、探索される有向グラフは、動的に変化していくため、前記テキスト文に含まれるフレーズのみならず、パラフレーズ化された新たなフレーズについても、さらに、パラフレーズ化されることになる。
【００２６】
また、前記有向グラフ探索部は、前記更新された有向グラフにおいて既に探索し終えたトークンに対する再探索が回避されるように、前記更新された有向グラフ内を探索し得る。
【００２７】
前記有向グラフは、前記複数のトークンのうちの隣接するトークンどうしを接続する複数のノードを含み得る。そして、前記有向グラフ探索部は、前記探索をし終えたトークンに関連付けられたノードを探索済みノードとして記憶し、前記探索済みノード以外のノードに接続されたトークンに対して再探索し得る。
【００２８】
また、前記装置は、前記辞書に含まれる前記複数のフレーズに基づいて構成される木構造を示すデータ配列をさらに備え得る。前記木構造は、前記複数のフレーズのそれぞれに対応する順序付きノードを含むトライ木又はプレフィックス木であり得る。そして、前記有向グラフ探索部は、前記木構造を参照しながら、前記有向グラフ内を探索し得る。
【００２９】
また、前記有向グラフ探索部は、前記探索対象フレーズが前記木構造における少なくとも１つの前記順序付きノードに対応する少なくとも１つのフレーズと一致する場合に、前記有向グラフ内に前記探索対象フレーズが顕出したと判断し得る。
【００３０】
また、前記有向グラフ生成部は、前記一致する探索対象フレーズに関連付けられた、前記辞書における少なくとも１つのフレーズに基づく新たなトークンを前記有向グラフに追加することによって、前記有向グラフを更新し得る。
【００３１】
前記インデックス作成部は、更新された前記有向グラフ内における複数のトークンに基づいてＮ−ｇｒａｍを抽出し、前記抽出したＮ−ｇｒａｍに基づいて、前記インデックスを作成するように構成され得る。これにより、リソースのテキスト文に含まれるフレーズ以外のフレーズをＮ−ｇｒａｍとするインデックスが作成されることになる。
【００３２】
また、前記インデックス作成部は、前記Ｎ−ｇｒａｍとして、単語ベースのＮ−ｇｒａｍ（単語Ｎ−ｇｒａｍ）を抽出するように構成され得る。かかる単語Ｎ−ｇｒａｍは、前記有向グラフ内におけるトークンに基づいているため、関連フレーズ群に基づく検索に適したインデックスが作成されることになる。
【００３３】
また、別の観点に係る本発明は、上記の装置により作成されたインデックスと、前記インデックスに関連付けられた前記リソースに関するリソース情報ファイルと、検索クエリに基づいて前記インデックスを検索し、該検索の結果に基づいて前記リソース情報ファイルから所定のリソースを特定し、前記特定した所定のリソースを示す検索結果を出力するクエリサーバとを備える検索装置ないしは検索エンジンである。前記クエリサーバは、前記特定した所定のリソースから得られる、前記所定のリソースにおけるフレーズに関連する所定の関連フレーズを含む有向グラフに基づいて、前記所定のリソースが特定された根拠となった根拠フレーズ及び前記フレーズに関連付けられた前記所定のリソースにおける元フレーズを特定する。また、前記検索結果は、前記根拠フレーズ及び前記元フレーズを含む。これにより、ユーザは、検索クエリに対する検索結果として、検索されたリソースに加え、該リソースが検索された根拠となった根拠フレーズ及びこれに関連する元フレーズを認識することができるようになる。
【００３４】
さらに別の観点に係る本発明は、テキスト文を含むリソースに基づいて、データベースを検索するためのインデックスを作成する装置の作動方法である。前記方法は、例えば、特定の概念ごとに、相互に関連付けられた複数のフレーズを含む辞書を、前記装置のプロセッサによってアクセスされるメモリに展開することと、入力インターフェース部を介して、前記リソースの入力を受け付けることと、前記受け付けたリソースのテキスト文から複数の語をトークンとして切り出すためのテキスト処理を行うことと、前記テキスト文に従って、前記切り出した複数のトークンどうしの接続関係を表現した有向グラフを生成することと、探索対象フレーズに基づいて前記有向グラフ内を探索することと、前記有向グラフ内における複数のトークンに基づいて、前記リソースとの関連付けを示すインデックスを作成することと、を含み得る。前記有向グラフ内を探索することは、前記有向グラフ内における少なくとも１つのトークンを前記探索対象フレーズに設定し、前記設定した探索対象フレーズに基づいて前記辞書を参照し、前記探索対象フレーズが前記辞書中に発見される場合に、前記有向グラフ内における前記探索対象フレーズが顕出した箇所を特定することを含み得る。また、前記有向グラフを生成することは、前記辞書に基づいて、前記探索対象フレーズに関連付けられた少なくとも１つのフレーズに基づく新たなトークンを前記有向グラフに追加することによって、前記有向グラフを更新することを含み得る。
【００３５】
さらに別の観点に係る本発明は、検索クエリに基づいてインデックスを検索し、該検索の結果に基づいてリソース情報ファイルから少なくとも１つのリソースを特定する検索装置の作動方法である。前記作動方法は、前記特定した少なくとも１つのリソースから得られる、前記少なくとも１つのリソースにおけるフレーズに関連する所定の関連フレーズを含む有向グラフに基づいて、前記少なくとも１つのリソースが特定された根拠となった根拠フレーズ及び前記フレーズに関連付けられた前記少なくとも１つのリソースにおける元フレーズを特定することと、前記所定のリソース並びに前記根拠フレーズ及び前記元フレーズを示す情報を検索結果として出力することと、を含み得る。
【００３６】
さらに別の観点に従う本発明は、コンピューティングデバイスに、各前記方法を実現させるためのコンピュータプログラム又はこれを非一時的に記録したコンピュータ可読記録媒体であり得る。
【００３７】
なお、本明細書等において、手段とは、単に物理的手段を意味するものではなく、その手段が有する機能をソフトウェアによって実現する場合も含む。また、１つの手段が有する機能が２つ以上の物理的手段により実現されても、２つ以上の手段の機能が１つの物理的手段により実現されても良い。
【発明の効果】
【００３８】
本発明によれば、インデックス型検索エンジンにおいて、収集された情報を効率的に検索することができるインデックスが作成される。したがって、インデックス作成の基となった収集された情報に含まれるフレーズ以外のフレーズによっても、該情報を検索することができるようになる。
【００３９】
また、本発明によれば、ユーザは、検索結果の根拠を認識できるようになる。とりわけ、検索クエリに対してヒットしたリソースが、検索クエリのフレーズから直接的にヒットしたリソースではなく、その関連フレーズによってヒットしたリソースである場合であっても、ユーザは、検索によりヒットした根拠となった関連フレーズを認識できるようになる。
【００４０】
本発明の他の技術的特徴、目的、及び作用効果乃至は利点は、添付した図面を参照して説明される以下の実施形態により明らかにされる。
【図面の簡単な説明】
【００４１】
【図１】図１は、本発明の一実施形態に係る情報検索システムの概略構成を示すブロックダイアグラムである。
【図２】図２は、本発明の一実施形態に係る検索エンジンにおけるデータベースの一例を説明するための図である。
【図３】図３は、本発明の一実施形態に係る検索エンジンにおける辞書の一例を説明するための図である。
【図４】図４は、本発明の一実施形態に係る検索エンジンのインデクサの概略的構成を示すブロックダイアグラムである。
【図５】図５は、本発明の一実施形態に係る検索エンジンのテキスト処理部に入力されるテキスト文の一例を示す図である。
【図６】図６は、本発明の一実施形態に係る検索エンジンによるインデックスの作成処理を説明するためのフローチャートである。
【図７】図７は、本発明の一実施形態に係る検索エンジンにより生成された初期有向グラフの一部の例を示している
【図８】図８は、本発明の一実施形態に係る検索エンジンによる有向グラフの探索・更新処理を説明するためのフローチャートである。
【図９】図９は、本発明の一実施形態に係る検索エンジンにより有向グラフの一部が展開される処理過程の一例を示す図である。
【図１０】図１０は、本発明の一実施形態に係る検索エンジンにより有向グラフが展開される処理過程の一例を説明するための図である。
【図１１】図１１は、本発明の一実施形態に係る検索エンジンによる検索処理を説明するためのフローチャートである。
【図１２Ａ】図１２Ａは、本発明の一実施形態に係る検索エンジンにより検索されたリソースの有向グラフから検索根拠を特定するための処理過程の一例を説明するための図である。
【図１２Ｂ】図１２Ｂは、本発明の一実施形態に係る検索エンジンにより検索されたリソースの有向グラフから検索根拠を特定するための処理過程の一例を説明するための図である。
【図１３Ａ】図１３Ａは、本発明の一実施形態に係る情報検索システムにおけるクライアント上に表示される検索結果画面の一例を示す図である。
【図１３Ｂ】図１３Ｂは、本発明の一実施形態に係る情報検索システムにおけるクライアント上に表示される検索結果画面の一例を示す図である。
【図１３Ｃ】図１３Ｃは、本発明の一実施形態に係る情報検索システムにおけるクライアント上に表示される検索結果画面の一例を示す図である。
【図１４】図１４は、本発明の一実施形態に係る検索エンジンにおける辞書の他の例を説明するための図である。
【図１５】図１５は、本発明の一実施形態に係る検索エンジンにおけるトライ木の一例を説明するための図である。
【図１６Ａ】図１６Ａは、本発明の一実施形態に係る検索エンジンによる有向グラフの探索・更新処理の他の例を説明するためのフローチャートである。
【図１６Ｂ】図１６Ｂは、本発明の一実施形態に係る検索エンジンによる有向グラフの探索・更新処理の他の例を説明するためのフローチャートである。
【図１７】図１７は、本発明の一実施形態に係る検索エンジンにより有向グラフの一部が展開される処理過程の他の例を示す図である。
【図１８】図１８は、本発明の一実施形態に係る検索エンジンのハードウェア構成の一例を示すブロックダイアグラムである。
【発明を実施するための形態】
【００４２】
以下、図面を参照して本発明の実施の形態を説明する。ただし、以下に説明する実施形態は、あくまでも例示であり、以下に明示しない種々の変形や技術の適用を排除する意図はない。本発明は、その趣旨を逸脱しない範囲で種々変形（例えば各実施形態を組み合わせる等）して実施することができる。また、以下の図面の記載において、同一又は類似の部分には同一又は類似の符号を付して表している。図面は模式的なものであり、必ずしも実際の寸法や比率等とは一致しない。図面相互間においても互いの寸法の関係や比率が異なる部分が含まれていることがある。
【００４３】
図１は、本発明の一実施形態に係る情報検索システムの概略構成を示すブロックダイアグラムである。同図に示すように、本実施形態の情報検索システム１は、コンピュータネットワーク１０を介して通信可能に接続される、少なくとも１つの検索エンジン２０と少なくとも１つのクライアント３０とを含み構成される。
【００４４】
コンピュータネットワーク１０は、典型的には、ＩＰベースのコンピュータネットワークを含むが、これに限られない。例えば、コンピュータネットワーク１０は、ノード間通信を可能とするあらゆるプロトコルのネットワークを適用することができる。
【００４５】
検索エンジン２０は、クライアント３０に情報検索サービスを提供するコンピュータシステムであり、例えば、１以上の汎用のコンピューティングデバイスにより実現され得る。すなわち、検索エンジン２０は、コンピューティングデバイス上の１つ又は複数のＣＰＵ（プロセッサ）が、例えば、所定のオペレーティングシステム（ＯＳ）上で本実施形態の検索エンジンプログラムを実行することにより、他のハードウェア要素と相俟って、具現化される仮想マシンである。検索エンジン２０は、仮想化技術により実現されても良い。検索エンジン２０が実現されるコンピューティングデバイスのハードウェア構成は、図１８に例示されるが、既知であるため、ここではその詳細を省略する。本実施形態では、検索エンジン２０は、インデックス型検索エンジンであり、例えば、インデックスの作成及び更新の機能と、該インデックスに基づくデータベース検索の機能を有する。図１に示すように、検索エンジン２０は、例えば、クローラ２１と、辞書２２と、インデクサ２３と、データベース２４と、クエリサーバ２５とを含み、構成される。なお、情報検索をしようとするユーザからみると、検索エンジン２０は、インデックスに基づくデータベース検索機能を実現する仮想マシン（検索装置ないしは狭義の検索エンジン）である。
【００４６】
クローラ２１は、Ｗｅｂ上の多種多様なリソース（例えば、Ｗｅｂページ、文書、画像、プログラムなど）を自動的に収集するための自動巡回エージェントプログラムである。具体的には、クローラ２１は、Ｗｅｂページ内のリンクを辿りながら、Ｗｅｂ上のサイトを周期的に訪問して、サイト内にあるリソースを収集する。例示として、クローラ２１は、特定の専門分野に属するサイト内のリソースを収集するものであっても良い。クローラ２１は、例えば、収集したリソースをストレージ（図示せず）に一時的に記憶させても良い。本実施形態の情報検索システム１においては、既知のクローラ２１を適用することができ、したがって、ここではその詳細は省略する。
【００４７】
辞書２２は、ある特定の概念についての複数のフレーズを相互に関連付けて記憶した１つ又は複数のファイルないしはテーブルであるが、これに限られるものではない。例えば、辞書２２は、静的なファイルないしはテーブルとして構成され、メモリ上に常駐するのではなく、所定のアルゴリズムに従って、フレーズ群の関係が構築される辞書モデル（例えばニューラルネットワークモデルなど）として動的に構成されても良い。本開示では、フレーズは、１つの単語及び２つ以上の単語の並びからなる語ないし表現をいうものとする。また、相互に関連付けられる複数のフレーズを、関連フレーズ群と称するものとし、一例として、類義語、同義語、関連語、略語、及び対応外国語、さらには、これらの語に基づく派生語などを含む。辞書２２は、例えば、入手可能な情報ソースに基づいて、手動で、半自動で、又は全自動で構築される。例えば、医療分野であれば、アメリカ国立がん研究所（National Cancer Institute：ＮＣＩ）が提供する様々な辞書は、辞書２２の構築のために用いられる。辞書２２は、後述するインデクサ２３がインデックス２４１を作成する際に参照される。
【００４８】
インデクサ２３は、クローラ２１によって収集されたリソース（例えば、リソースに関する情報）をデータベース２４に登録するとともに、該リソースの内容（典型的には、テキスト文）を解析し、該解析の結果に従ってインデックス２４１を作成し、更新する。本実施形態のインデクサ２３は、概略的には、リソースに含まれるテキスト文をいくつかのトークンに分解し、これらに基づいて有向グラフ（ラティス）を作成し、所定のフレーズに従って、辞書２２を参照しながら有向グラフ内の探索し、所定の条件の下、有向グラフを展開し、更新していく。更新された有向グラフは、新たな探索対象の有向グラフとなる。その後、インデクサ２３は、展開された有向グラフに基づいて、所定の手法（例えばＮ−ｇｒａｍ手法など）で見出し語を切り出して、これを収集したリソースと関連付けて（索引付けて）インデックス２４１を作成及び／又は更新する。また、インデクサ２３は、収集したリソースと作成した有向グラフとを関連付けて、データベース２４に登録する。
【００４９】
データベース２４は、クローラ２１によって収集されたリソースに関する情報を格納し、そのインデックス２４１を含み構成される。また、データベース２４は、インデックス２４１を作成するために用いた有向グラフを格納する。図２は、本発明の一実施形態に係る検索エンジンにおけるデータベースの一例を説明するための図である。図２（ａ）は、リソースに関する情報の一例を示す。リソースに関する情報は、例えば、リソースを識別するリソースＩＤ、リソース名称、ＵＲＬ、及び有向グラフを識別するための有向グラフＩＤなどを含む構造ファイルである。本開示では、リソースに関する情報を格納した構造ファイルをリソース情報ファイルと称するものとする。インデックス２４１は、インデクサ２３によって作成され、更新される索引情報を含む構造ファイルである。図２（ｂ）は、インデックス２４１の一例を示す。典型的には、インデックス２４１は、転置インデックスと呼ばれるデータ構造を有する。索引情報は、例えば、Ｎ−ｇｒａｍ手法により有向グラフ中の語の並びから切り出された見出し語である。インデックス２４１内の見出し語は、リソース（すなわち、リソースＩＤ）と関連付けられ、これにより、データベース２４のリソース情報ファイルの個々のデータセットと関連付けられる。なお、本開示では、インデックス２４１は、データベース２４の一部として構成されているが、これに限られるものではなく、それぞれ別体として構成されても良い。
【００５０】
図１に戻り、クエリサーバ２５は、クライアント３０から与えられる検索クエリを受け付けて、インデックス２４１を検索し、その検索結果に基づいてデータベース２４から該当するリソースに関連する情報を抽出し、これを検索結果としてクライアント３０に提供する。クエリサーバ２５は、例えば、検索クエリと抽出したリソースとの間の適合度を所定の手法により算出し、その算出結果に応じて抽出したリソースを順位付けした検索結果を提供しても良い。本実施形態では、クエリサーバ２５は、クライアント３０からの検索クエリに対する検索結果を、クライアント３０に直接返しているが、これに限られるものではない。例えば、クエリサーバ２５は、検索結果を、所定のＡＰＩ（Application Program Interface）を介して、他のアプリケーションプログラムに渡し、他のアプリケーションプログラムにより該検索結果に対する所定の情報処理を行った結果をクライアント３０に返すようにしても良い。本実施形態の情報検索システム１においては、既知のクエリサーバ２５を適用することができる。
【００５１】
クライアント３０は、典型的には、ユーザが所有するコンピューティングデバイスであり、例えば、パーソナルコンピュータであり得る。クライアント３０は、例えば、コンピュータネットワーク１０を介して、検索エンジン２０にアクセスするための、ユーザインターフェースとして機能するビューワを含む。ビューワは、例えば、Ｗｅｂブラウザであり得るが、これに限られるものではない。クライアント３０は、例えば、ＳＳＬなどのセキュアな通信技術を利用することによって、コンピュータネットワーク１０を介して、検索エンジン２０との通信セッションを構築し得る。クライアント３０は、１つ又は複数のＣＰＵ（プロセッサ）及びメモリなどを含み構成されるが、そのハードウェア構成は既知であるため、ここではその詳細は省略する。
【００５２】
図３は、本発明の一実施形態に係る検索エンジンにおける辞書の一例を説明するための図である。図３に示すように、辞書２２は、特定の概念ごとに、１つ又は複数の語からなる複数のフレーズのそれぞれを相互に関連付けて記憶するテーブルとして構成されている。例示的に、図３においては、フレーズ‘ｐａｒｐ’、フレーズ‘ｐｏｌｙ｜ａｄｐ｜ｒｉｂｏｓｅ｜ｐｏｌｙ｜ｍｅｒａｓｅ’及びフレーズ‘ポリ｜ａｄｐ｜リボース｜ポリメラーゼ’が、それぞれ相互に関連付けられて登録されている。記号‘｜’は、フレーズ中の個々の単語を区切るために追加されたデリミタである。このように、フレーズを構成する単語をデリミタで区切ることにより、後述するように、フレーズを構成する個々の単語を有向グラフ中の個々のトークンとして扱えるようになる。なお、ここでは、３つのフレーズが相互に関連付けられた１つのデータセットとして示されているが、これに限られるものでなく、その数に制限はない。
【００５３】
図４は、本発明の一実施形態に係る検索エンジンのインデクサの概略的構成を示すブロックダイアグラムである。同図に示すように、本実施形態のインデクサ２３は、例えば、入力インターフェース部２３１と、テキスト処理部２３２と、有向グラフ生成部２３３と、有向グラフ探索部２３４と、インデックス作成部２３５とを含み構成される。
【００５４】
入力インターフェース部２３１は、例えば、クローラ２１とテキスト処理部２３２との間のインターフェースとして機能する。入力インターフェース部２３１は、クローラ２１と通信して、クローラ２１が収集したリソースに含まれる例えば図５に示すようなテキスト文をテキスト処理部２３２に入力する。
【００５５】
テキスト処理部２３２は、入力されたテキスト文について例えば形態素解析を行って、複数のトークンを切り出す。テキスト処理部２３２は、典型的には、日本語や英語などの各国の言語に対応した言語解析エンジン（図示せず）を含み得る。言語解析エンジンは、既知のものを用いることができる。
【００５６】
有向グラフ生成部２３３は、テキスト処理部２３２によって切り出された複数のトークンに基づく有向グラフを生成する。具体的には、有向グラフ生成部２３３は、テキスト処理部２３２によって切り出された複数のトークンのそれぞれについて、隣接するトークンをノードによって接続し、これによって、複数のトークンどうしの接続関係を表現した有向グラフ（例えば図７（ａ））を生成する。つまり、一般的に、有向グラフは、エッジ及びノードにより表現されるところ、本実施形態の有向グラフは、個々のトークンをエッジのラベルとして定義し、かかるラベル付きエッジ及びノードにより表現されたものということができる。このように、有向グラフ生成部２３３によってテキスト文から直接生成された有向グラフは、先頭ノードから最終ノードまで１つのパスのみを含む。なお、本開示で図示される有向グラフは、理解容易のために描かれたもので、実際上は、コンピューティングデバイス内部では、典型的には、プロセッサにより解釈可能なある種のデータ構造として扱われる。有向グラフ生成部２３３は、後述する有向グラフ探索部２３４による探索の結果に従って、有向グラフの接続関係を動的に変更することにより、有向グラフを展開し、更新していく。
【００５７】
有向グラフ探索部２３４は、探索の対象となるフレーズ（以下「探索対象フレーズ」という。）を設定し、これに基づいて、辞書２２を参照しながら有向グラフ内を探索する。探索対象フレーズは、有向グラフ中の任意の１つ又は複数のトークンであり、例えば、先頭のトークンから順に選択され、設定される。より具体的には、本実施形態では、有向グラフ探索部２３４は、設定された探索対象フレーズに基づいて、有向グラフ内をエッジ及びノードに従って順番に辿りながら、該探索対象フレーズが辞書２２に登録されているか否かを判定する。有向グラフ探索部２３４は、該探索対象フレーズが辞書２２に登録されていると判定する場合、すなわち、該探索対象フレーズを辞書２２中に発見した場合、有向グラフ探索部２３４は、有向グラフ内における該探索対象フレーズが顕出した箇所を特定し、特定した箇所を有向グラフ生成部２３３に通知する。これを受けて、有向グラフ生成部２３３は、有向グラフ内における特定された箇所の前後のノードに、辞書２２における該探索対象フレーズに関連付けられたフレーズを追加的に接続することにより、有向グラフを更新する。したがって、新たにフレーズが追加され、更新された有向グラフは、例えば図９（ｂ）などに示すように、テキスト文の先頭ノードから最終ノードまでの間に、複数のパスが存在し得ることになる。
【００５８】
インデックス作成部２３５は、有向グラフ探索部２３４が探索を終えることにより得られる最終的な有向グラフに基づいて、収集されたリソースとの関連付けを示すインデックスを作成する。具体的には、インデックス作成部２３５は、更新された最終的な有向グラフに従い、そこから単語（トークン）ベースのＮ−ｇｒａｍ（以下「単語Ｎ−ｇｒａｍ」という。）（すなわち、単語の並び）を抽出し、該抽出した単語Ｎ−ｇｒａｍを見出し語としてリソースに関連付けることにより、インデックス２４１を作成する。本実施形態では、Ｎ≦３（ただし、Ｎは正数）、すなわち、１〜３個の単語の並び（すなわち、１−ｇｒａｍ、２−ｇｒａｍ及び３−ｇｒａｍ）がインデックス２４１の見出し語として用いられる。また、本実施形態は、単語Ｎ−ｇｒａｍを用いているが、これに限られるものではなく、従前のＮ−ｇｒａｍのように、文字単位の並び（すなわち、１文字、２文字、…）を用いることを排除する趣旨ではない。
【００５９】
図６は、本発明の一実施形態に係る検索エンジンによるインデックスの作成処理を説明するためのフローチャートである。かかる処理は、例えば、コンピューティングデバイス上のプロセッサが、本実施形態に係る所定の検索エンジンプログラムを実行することにより、実現される。
【００６０】
図６に示すように、検索エンジン２０は、クローラ２１よって収集されたリソースに含まれるテキスト文を受信する（Ｓ６０１）。例えば、入力インターフェース部２３１は、クローラ２１によって収集されたリソースを受信すると、リソースに含まれるテキスト文をテキスト処理部２３２に入力する。検索エンジン２０は、テキスト文を受信すると、テキスト文に対して形態素解析を行って、テキスト文をトークン化、すなわち、テキスト文から複数のトークンを切り出す（Ｓ６０２）。例えば、テキスト処理部２３２は、テキスト文の言語を判定し、該言語に応じた形態素解析処理により、テキスト文から複数のトークンを切り出す。
【００６１】
次に、検索エンジン２０は、切り出した複数のトークンに基づいて有向グラフを生成する（Ｓ６０３）。例えば、有向グラフ生成部２３３は、テキスト処理部２３２によって切り出された複数のトークンのそれぞれについて、該トークンをエッジのラベルとして、隣接するエッジをノードによって接続し、これによって、複数のトークンどうしの接続関係を表現した有向グラフを生成する。テキスト文から最初に生成された有向グラフを、ここでは、初期有向グラフと呼ぶものとする。図７は、図５に示した入力されたテキスト文から生成された初期有向グラフの一部を示している。すなわち、図７（ａ）に示すように、本実施形態の有向グラフは、個々のトークンをエッジのラベルとして定義し、かかるラベル付きエッジ及びノードにより表現されている。初期有向グラフは、図７に示すように、先頭ノードから続くパスは１つのみである。
【００６２】
なお、本実施形態では、上述したように、個々のトークンを、有向グラフにおけるエッジのラベルとして定義した有向グラフが示されているが、これに限られるものではない。例えば、図７（ｂ）に示すように、トークンもまたノードと定義し（つまり、２種類のノードが存在する。）、これら２種類のノードを単なるエッジで接続した有向グラフであっても良い。なお、このようなグラフは、自然言語処理の分野ではラティスと称されることもあり、本開示では、これを区別するものではない。
【００６３】
図６に戻り、検索エンジン２０は、辞書２２を参照しながら有向グラフを探索し、探索の結果に従って該有向グラフを展開し、更新する（Ｓ６０４）。すなわち、検索エンジン２０は、有向グラフの中から所定の語を探索の対象となる探索対象フレーズとして順番に設定し、これに基づいて、有向グラフ内をエッジ及びノードに従って探索しながら、該探索対象フレーズを辞書２２中に発見するごとに、該発見した探索対象フレーズに関連付けられたフレーズに基づいて、有向グラフを展開し、更新する。なお、有向グラフの探索及び更新処理の詳細は、図８を用いて説明される。
【００６４】
上述した有向グラフの探索及び更新処理の後、検索エンジン２０は、更新された有向グラフに基づいて、収集されたリソースとの関連付けを示すインデックス２４１を作成する（Ｓ６０５）。例えば、インデックス作成部２３５は、更新された最終的な有向グラフに従い、そこから１−ｇｒａｍから３−ｇｒａｍまでの単語の並びをそれぞれ抽出し、該抽出した語の並びを見出し語として、収集されたリソースに関連付けることにより、例えば図２（ｂ）に示したようなインデックス２４１を作成する。インデックス作成部２３５はまた、作成したインデックス２４１に対応するように、例えば図２（ａ）に示したようなリソース情報ファイルをデータベース２４に登録する。これにより、後の検索クエリに対して、検索クエリの関連フレーズの範囲にまで拡張された見出し語からリソースが検索されるようになる。さらに、本実施形態では、インデックス作成部２３５は、インデックス２４１の作成に際し、収集されたリソースに更新された最終的な有向グラフを関連付け、リソースに関連付けた有向グラフをデータベース２４に格納する。リソースに関連付けられた有向グラフは、検索クエリに基づいて検索が実行され、該リソースがヒットし、抽出された場合に、該検索によりヒットした根拠（例えば関連フレーズ）を提示するために用いられる。
【００６５】
図８は、本発明の一実施形態に係る検索エンジンによるインデックスの作成処理を説明するためのフローチャートであり、より具体的には、図６に示した有向グラフの探索及び更新の処理の詳細を説明するためのフローチャートである。
【００６６】
すなわち、図８に示すように、例えば、有向グラフ探索部２３４は、まず、現在の有向グラフを探索対象の有向グラフに設定し（Ｓ８０１）、続いて、有向グラフ中の現時点の探索箇所にある所定のトークンを探索対象フレーズとして設定する（Ｓ８０２）。探索の開始時点では、初期有向グラフが探索対象の有向グラフであり、初期有向グラフの先頭ノードに接続されたトークンが探索対象フレーズとして設定される。また、有向グラフの探索に伴い、有向グラフの中の所定のトークンが順次に設定される。探索対象フレーズは、１つ又はそれ以上のトークンである。
【００６７】
有向グラフ探索部２３４は、次に、設定された探索対象フレーズに基づいて、辞書２２を参照しながら有向グラフ内を探索する（Ｓ８０３）。例えば、有向グラフ探索部２３４は、設定された探索対象フレーズに基づいて、有向グラフ内をエッジ及びノードに従って順番に辿りながら、該探索対象フレーズが辞書２２に登録されているか否かを判定する（Ｓ８０４）。有向グラフ内の探索は、例えば、ＫＭＰ（クヌース−モリス−プラット）法に従って行われ得るが、これに限られるものではない。
【００６８】
有向グラフ探索部２３４は、該探索対象フレーズが辞書２２に登録されていると判定する場合（Ｓ８０４のＹｅｓ）、すなわち、該探索対象フレーズを辞書２２中で発見した場合、有向グラフ探索部２３４は、該有向グラフ内における該探索対象フレーズが顕出した箇所を特定し、該特定した箇所を有向グラフ生成部２３３に通知する（Ｓ８０５）。有向グラフ生成部２３３は、これを受けて、該有向グラフ内における該特定された箇所の前後のノードに、辞書２２における該探索対象フレーズに関連付けられたフレーズを追加的に接続することにより、該有向グラフを更新する（Ｓ８０６）。フレーズは、典型的には、１つ以上のトークンとして切り出されて、有向グラフに接続される。その後、有向グラフ探索部２３４は、探索を続行するため、Ｓ８０１の処理に戻る。すなわち、有向グラフ探索部２３４は、現在の有向グラフを探索対象の有向グラフとして（Ｓ８０１）、その探索箇所を次に進め、そこのトークンを新たな探索対象フレーズに設定して、探索処理を進める（Ｓ８０２）。
【００６９】
一方、有向グラフ探索部２３４は、該探索対象フレーズが辞書２２中で発見されない場合（Ｓ８０４のＮｏ）、有向グラフの終端ノードに到達したか否かを判定する（Ｓ８０７）。有向グラフ探索部２３４は、有向グラフの終端ノードに到達していないと判定する場合（Ｓ８０７のＮｏ）、有向グラフ内の探索を続行するため、Ｓ８０２の処理に戻る。一方、有向グラフ探索部２３４は、有向グラフの最終ノードに到達したと判定する場合（Ｓ８０７のＹｅｓ）、探索処理を終了する。
【００７０】
以上のような処理により、検索エンジン２０は、入力されたテキスト文に基づいて検索のためのインデックスを作成するに際して、相互に関連付けられた複数のフレーズが登録された辞書２２を用いて、元のテキスト文に含まれるフレーズのみならず、関連フレーズ群にまで拡張した個々のフレーズに基づいてインデックスを作成することができるようになる。
【００７１】
次に、検索エンジン２０による有向グラフの展開処理の一例を説明する。図９は、本発明の一実施形態に係る検索エンジンにより有向グラフが展開される処理過程の一例を説明するための図である。本例では、検索エンジン２０は、図４に示した辞書２２に基づいて、図５に示したテキスト文を含むリソースに対してインデックス２４１を作成する際の有向グラフの展開の様子を示している。
【００７２】
まず、検索エンジン２０は、上述したように、入力されたテキスト文に基づいて、例えば図７（ａ）に示したような初期有向グラフを生成する。次に、検索エンジン２０は、有向グラフの探索を開始し、その過程で、設定された探索対象フレーズ‘ｐｏｌｙ｜ａｄｐ｜ｒｉｂｏｓｅ｜ｐｏｌｙｍｅｒａｓｅ’を、辞書２２中に発見したとする。検索エンジン２０は、有向グラフ内における該探索対象フレーズ‘ｐｏｌｙ｜ａｄｐ｜ｒｉｂｏｓｅ｜ｐｏｌｙｍｅｒａｓｅ’の箇所の前後にある始端ノード及び終端ノードに、辞書２２中のフレーズ‘ｐｏｌｙ｜ａｄｐ｜ｒｉｂｏｓｅ｜ｐｏｌｙｍｅｒａｓｅ’に関連付けられたフレーズ‘ｐａｒｐ’及びフレーズ‘ポリ｜ａｄｐ｜リボース｜ポリメラーゼ’のそれぞれを並列に接続することにより、有向グラフを更新する（図９（ａ））。
【００７３】
さらに、検索エンジン２０は、有向グラフの探索を進め、有向グラフ内における‘ａｄｐ｜リボース’が探索対象フレーズとして設定されたときに、これを辞書２２中に発見する。探索対象フレーズ‘ａｄｐ｜リボース’は、上述した探索の過程で、検索エンジン２０によって有向グラフに追加された語である。検索エンジン２０は、同様に、有向グラフ内における該探索対象フレーズ‘ａｄｐ｜リボース’の箇所の前後にある始端ノード及び終端ノードに、辞書２２中のフレーズ‘ａｄｐ｜リボース’に関連付けられたフレーズ‘ａｄｅｎｏｓｉｎｅ｜ｄｉｐｈｏｓｐｈａｔｅ｜ｒｉｂｏｓｅ’を並列に接続することにより、有向グラフを更新する（図９（ｂ））。このように、追加されたフレーズを含むパスについても、さらにパラフレーズが追加され得る。
【００７４】
さらに、検索エンジン２０は、有向グラフの探索を進め、有向グラフ内における‘ｐａｒｐ｜ｉｎｈｉｂｉｔｏｒ’が探索対象フレーズとして設定されたときに、これを辞書２２中に発見する。探索対象フレーズ‘ｐａｒｐ｜ｉｎｈｉｂｉｔｏｒ’は、探索の過程で、検索エンジン２０によって‘ｐａｒｐ’が有向グラフに追加された結果、隣接する語‘ｉｎｈｉｂｉｔｏｒ’との結合により得られた語である。検索エンジン２０は、同様に、有向グラフ内における該探索対象フレーズ‘ｐａｒｐ｜ｉｎｈｉｂｉｔｏｒ’の箇所の前後にある始端ノード及び終端ノードに、辞書２２中のフレーズ‘ｐａｒｐ｜ｉｎｈｉｂｉｔｏｒ’に関連付けられたフレーズ‘ｐａｒｐ｜阻害｜剤’を並列に接続することにより、有向グラフを更新する（図９（ｃ））。すなわち、フレーズ‘ｐａｒｐ｜阻害｜剤’は、初期有向グラフにおける元のパス（ｐｏｌｙ→ａｄｐ→ｒｉｂｏｓｅ→ｐｏｌｙｍｅｒａｓｅ→ｉｎｈｉｂｉｔｏｒ）に並列的に接続されたことになる。
【００７５】
検索エンジン２０は、以上のような、有向グラフに対する探索動作を行うことにより、有向グラフを展開し、更新していく。この結果、更新された有向グラフは、初期有向グラフにおける元のパスに対して、いくつかの並列的なパスが形成されることになる。したがってこのような有向グラフに基づいて見出し語を抽出することにより、元のテキスト文に含まれるフレーズのみならず、関連フレーズ群にまで拡張した個々のフレーズ（パラフレーズ）に基づいてインデックスを作成することができるようになる。
【００７６】
図１０は、本発明の一実施形態に係る検索エンジンによる検索処理を説明するためのフローチャートである。かかる処理は、例えば、コンピューティングデバイス上のプロセッサが、所定の検索エンジンプログラムを実行することにより、実現される。
【００７７】
図１０に示すように、検索エンジン２０は、クライアント３０から検索クエリを受信する（Ｓ１００１）。例えば、クライアント３０は、例えば、ユーザが、ウェブブラウザ（図示せず）上に表示された検索画面に検索クエリを入力することにより、検索エンジン２０に検索クエリを送信する。検索エンジンは、受信した検索クエリに対して所定の解析処理を行う（Ｓ１００２）。例えば、クエリサーバ２５は、クライアント３０から受信した検索クエリに対して、Ｎ−ｇｒａｍの検索式を作成する。本実施形態では、Ｎ＝３を最大値とするが、これに限られない。したがって、検索クエリが４つ以上の単語を含む場合には、クエリサーバ２５は、３−ｇｒａｍの単語を抽出して、これらのＡＮＤ検索を行う。例えば、検索クエリが‘ｐｌａｔｉｎｕｍ  ａｎｄ  ｐａｒｐ  ｉｎｈｉｂｉｔｏｒ’である場合、検索式は、‘（ｐｌａｔｉｎｕｍ  ａｎｄ  ｐａｒｐ）  ＡＮＤ  （ａｎｄ  ｐａｒｐ  ｉｎｈｉｂｉｔｏｒ）’となる。
【００７８】
次に、検索エンジン２０は、作成した検索式に基づいて、インデックス２４１を検索する（Ｓ１００３）。例えば、クエリサーバ２５は、作成した検索式に基づいて、インデックス２４１を検索し、インデックス２４１内の見出し語がヒットするか否かをチェックする。見出し語がヒットした場合、クエリサーバ２５は、該見出し語に従ってデータベース２４を参照し、見出し語に関連付けられたリソースの名称及びその位置情報などの情報を抽出し、該抽出した結果をクライアント３０に返答する。例えば、クエリサーバ２５は、検索式‘（ｐｌａｔｉｎｕｍ  ａｎｄ  ｐａｒｐ）  ＡＮＤ  （ａｎｄ  ｐａｒｐ  ｉｎｈｉｂｉｔｏｒ）’に基づいてインデックス２４１を検索することにより、図５に示したようなテキスト文を含むリソースがヒットし、これを抽出することになる。クエリサーバ２５は、抽出される結果が複数ある場合、これらを所定のスコア計算に基づくそのスコアに従ってランキングしても良い。また、本実施形態では、クエリサーバ２５は、見出し語に関連付けられたリソースを抽出するに際し、該リソースに関連付けられた有向グラフに基づいて、該リソースがヒットした根拠となった関連フレーズ及び該リソースのテキスト文のフレーズを特定する（Ｓ１００４）。検索根拠の特定処理の詳細については、図１１を参照して説明される。
【００７９】
そして、検索エンジン２０は、検索根拠となったフレーズを特定した後、該検索根拠となったフレーズを含む検索結果をクライアントに送信する（Ｓ１００５）。クライアント３０は、これを受けて、検索クエリを入力した検索画面に検索結果を表示する。
【００８０】
従来の検索エンジンは、収集したリソースのテキスト文に含まれるフレーズのみに基づく見出し語をインデックスに登録していたため、検索により該リソースが抽出されるためには、検索クエリが、該リソースに含まれていた見出し語を含む必要がある。例えば、従来の検索エンジンは、図５に示したようなテキスト文を含むリソースに対して、フレーズ‘ｐａｒｐ  ｉｎｈｉｂｉｔｏｒ’を見出し語とするインデクスを作成することはない。したがって、クライアント３０からの検索クエリが‘ｐｌａｔｉｎｕｍ  ａｎｄ  ｐａｒｐ  ｉｎｈｉｂｉｔｏｒ’である場合、‘ｐａｒｐ  ｉｎｈｉｂｉｔｏｒ’を含まないリソースは検索結果として提示されないか、仮に他の要因で提示される場合であっても、ランキングが低いものとして提示されるにすぎない。これに対して、本実施形態の検索エンジン２０は、テキスト文に含まれるフレーズのみならず関連フレーズ群にまで拡張した個々のフレーズに基づく見出し語をインデックス２４１に登録することができる。したがって、クライアント３０からの検索クエリが‘ｐｌａｔｉｎｕｍ  ａｎｄ  ｐａｒｐ  ｉｎｈｉｂｉｔｏｒ’である場合であっても、‘ｐａｒｐ  ｉｎｈｉｂｉｔｏｒ’を含まないリソースが検索結果として提示されるようになる。
【００８１】
図１１は、本発明の一実施形態に係る検索エンジンによる検索処理を説明するためのフローチャートであり、より具体的には、図１０に示した検索根拠の特定処理の詳細を説明するためのフローチャートである。
【００８２】
図１１に示すように、まず、検索エンジン２０は、検索によりヒットしたリソースの有向グラフを特定する（Ｓ１１０１）。例えば、クエリサーバ２５は、図２に示したようなデータベース２４のリソース情報ファイルを参照し、ヒットしたリソースのテキスト文に関連付けられた有向グラフＩＤを特定し、該特定した有向グラフＩＤに基づいて、データベース２４に格納されている有向グラフを読み出す。なお、本実施形態では、検索エンジン２０は、ヒットしたリソースに関連付けられて格納された有向グラフＩＤを用いているが、これに限られず、ヒットしたリソースについて、図８に示した探索及び更新処理に従って、有向グラフを再度生成するようにしても良い。
【００８３】
次に、検索エンジン２０は、検索クエリに基づいて、特定した有向グラフ内を探索し（Ｓ１１０２）、検索クエリが顕出した、有向グラフにおける箇所を特定する（Ｓ１１０３）。例えば、クエリサーバ２５は、有向グラフにおける各パスをエッジ及びノードに従って順番に辿りながら、検索クエリに一致する箇所を特定する。特定される箇所は、１つのパスの全部又は一部であり、したがって、複数のエッジ及びノードを含み得る。探索は、例えば、ＫＭＰ法に従って行われる。或いは、トライ木Ｔを用いて行われる。
【００８４】
検索エンジン２０は、次に、特定された箇所のパスが接続されている、有向グラフにおける元のパス上の分岐ノードを特定するとともに（Ｓ１１０４）、合流ノードを特定する（Ｓ１１０５）。元のパスとは、リソースのテキスト文から直接得られた有向グラフのパスであり、上述した初期有向グラフ（図７（ａ）参照）のパスに等しい。例えば、クエリサーバ２５は、特定された箇所の前端ノードからテキスト文に基づく元のパスのノードに到達するまで、特定された箇所のパスを後ろ向きに（すなわち、エッジの向きとは逆方向に）辿り、到達したノードを分岐ノードとして特定する。また、クエリサーバ２５は、特定された箇所の後端ノードから元のパスのノードに達するまで、特定された箇所のパスを前向きに（すなわち、エッジの向きの方向に）辿り、到達したノードを合流ノードとして特定する。なお、本例では、クエリサーバ２５は、分岐ノードを特定した後に合流ノードを特定しているが、合流ノードを特定した後に分岐ノードを特定しても良いし、或いは、同時並行的にこれらを特定しても良い。
【００８５】
検索エンジン２０は、分岐ノード及び合流ノードを特定すると、特定された箇所のパス上で、分岐ノードから合流ノードまでフレーズを特定する（Ｓ１１０６）。例えば、クエリサーバ２５は、ステップＳ１１０４においてパスを後ろ向きに辿る過程及びステップＳ１１０５において前向きに辿る過程で、エッジのラベルを抽出し、バッファに記憶しておき、該抽出し記憶したラベルに従ってフレーズを特定する。このステップＳ１１０６で特定されたフレーズが、検索によりヒットした根拠となった関連フレーズである。
【００８６】
続いて、検索エンジン２０は、同様に、元のパス上で、分岐ノードから合流ノードまでのフレーズを抽出する（Ｓ１１０６）。例えば、クエリサーバ２５は、分岐ノードからエッジの向きに従って合流ノードまで、エッジのラベルを抽出し、バッファに記憶しておき、該抽出し記憶したラベルに従ってフレーズを特定する。このステップＳ１１０７で特定されたフレーズが、関連フレーズが生成される基となったテキスト文のフレーズである。
【００８７】
なお、検索エンジン２０は、有向グラフにおいて検索クエリが顕出した箇所ごとに、上記の検索根拠の特定処理を行い得る。
【００８８】
以上のような処理により、検索エンジン２０は、検索クエリに対してヒットしたリソースが、検索クエリのフレーズから直接的にヒットしたリソースではなく、その関連フレーズによってヒットしたリソースである場合であっても、検索によりヒットした根拠となった関連フレーズをユーザに提供することができるようになる。
【００８９】
また、例えば複数のフレーズのＯＲ検索を含む検索クエリに基づいて本実施形態のインデックス２４１に対して検索が行われた場合であっても、ユーザに検索根拠が提示されることで、ユーザは、複数のフレーズの中から、リソースのヒットに貢献したフレーズを容易に把握することができるようになる。また、検索クエリからユーザが予期しないリソースがヒットされた場合であっても、検索根拠が提示されるため、ユーザは、検索エンジン２０が正常に機能していることを認識できるようになる。
【００９０】
次に、検索エンジン２０による検索根拠の特定処理の一例を説明する。図１２Ａ及び１２Ｂは、本発明の一実施形態に係る検索エンジンにより検索されたリソースの有向グラフから検索根拠を特定するための処理過程の一例を説明するための図である。本例では、検索エンジン２０は、図９に示した有向グラフに基づいて、検索根拠を特定する様子を示している。
【００９１】
まず、検索エンジン２０は、上述したように、データベース２４のリソース情報ファイルからヒットしたリソースの有向グラフＩＤを特定し、例えば図１２Ａ（ａ）に示すような有向グラフをデータベース２４から読み出して、検索クエリに含まれるフレーズ‘ｄｉｐｈｏｓｐｈａｔｅ  ｒｉｂｏｓｅ’に基づいて、有向グラフ内の探索を開始する。かかる探索過程において、検索エンジン２０は、有向グラフにおけるある１つのパスに、検索クエリのフレーズに一致するフレーズを発見すると、有向グラフにおける該フレーズが顕出した箇所を特定する（図１２Ａ（ｂ））。以下では、特定した箇所の前端のノードを前端ノードＡとし、その後端のノードを後端ノードＢとする。
【００９２】
次に、検索エンジン２０は、前端ノードＡからテキスト文に基づく元のパスのノードに達するまで、特定された箇所のパスを逆方向に辿り、到達したノードを分岐ノードＡ’として特定するとともに、後端ノードＢから元のパスのノードに達するまで、特定された箇所のパスを順方向に辿り、到達したノードを合流ノードＢ’として特定する（図１２Ｂ（ｃ））。
【００９３】
そして、検索エンジン２０は、分岐ノードＡ’から、特定した箇所を含むパスを経由した、合流ノードＢ’までのパスを辿って、フレーズ‘ポリ｜ａｄｅｎｏｓｉｎｅ｜ｄｉｐｈｏｓｐｈａｔｅ｜ｒｉｂｏｓｅ｜ポリメラーゼ’を特定する。該特定した箇所のフレーズが、検索クエリに関連するフレーズとしてリソースがヒットする根拠となった関連フレーズである。また、検索エンジン２０は、リソースのテキスト文に基づく分岐ノードＡ’から合流ノードＢ’までの元のパスを辿って、フレーズ‘ｐｏｌｙ｜ａｄｐ｜ｒｉｂｏｓｅ｜ｐｏｌｙｍｅｒａｓｅ’を特定する（図１２Ｂ（ｄ））。元のパスの該特定したフレーズが、関連フレーズが生成される基となったテキスト文のフレーズである。
【００９４】
以上のようにして、検索エンジン２０は、検索根拠となったフレーズを特定した後、該検索根拠となったフレーズを含む検索結果をクライアントに送信する。クライアント３０は、これを受けて、例えばウェブブラウザ上に検索結果を表示する。
【００９５】
図１３Ａ〜１３Ｃは、本発明の一実施形態に係る情報検索システムにおけるクライアント上に表示される検索結果画面の例を示す図である。
【００９６】
図１３Ａに示す例では、検索結果画面１３００Ａは、例えば、検索クエリ入力フィールド１３０１に入力された検索クエリに基づいて検索エンジン２０によって検索されたリソース名１３０２及びそのリンク１３０３を含む。図１３Ａに示す例では、検索クエリ「“ｄｉｐｈｏｓｐｈａｔｅ  ｒｉｂｏｓｅ”  ＯＲ  “ｐａｒｐ  阻害剤”」に対してヒットしたリソースとして、「がん治療薬」及びそのＵＲＬが表示されている。また、本実施形態では、検索結果画面は、本文表示領域１３０４及び検索根拠表示領域１３０５を含む。本文表示領域１３０４及び検索根拠表示領域１３０５は、例えば、左右に並べて配置される。本文表示領域１３０４は、検索クエリに対してヒットしたリソースにおけるテキスト文の少なくとも一部を表示する領域である。表示されるテキスト文は、例えば、検索クエリのフレーズに関連するテキスト文の少なくとも一部であり得る。検索根拠表示領域１３０５は、検索クエリに対してリソースがヒットした根拠となった関連フレーズを表示する領域である。関連フレーズなどは、ユーザの視認性向上のため、例えば色分け、斜線、太字、斜体、枠付きなどの手法によって強調表示される。図１３Ａに示す例では、検索クエリのフレーズに対してヒットしたリソースにおけるフレーズが、どの関連フレーズに関連付けられているかが示されている。言い換えれば、リソースにおけるテキスト文のどのフレーズがどのような関連フレーズに置き換わってヒットしたかが示されている。
【００９７】
また、図１３Ｂでは、本文表示領域１３０４’に、検索クエリに対してヒットしたリソースにおけるテキスト文の少なくとも一部と、検索クエリに対してリソースがヒットした根拠となった関連フレーズとが表示される検索結果画面１３００Ｂの例が示される。関連フレーズなどは、ユーザの視認性向上のため、例えば、強調表示される。また、本例の検索結果画面１３００Ｂは、検索根拠を表示するか否かをユーザが任意に選択することができるように、チェックボックス１３０６を含む。チェックボックス１３０６にチェックが入れられている場合、検索結果画面１３００Ｂに、検索根拠が表示される。例えば、ユーザは、検索クエリを入力し、検索結果の提示を受けた後、検索根拠を確認したいと考える場合に、チェックボックス１３０６にチェックを入れ、それを表示させるようにすることができる。このようにすることで、ユーザは、検索結果画面１３００Ｂを簡略表示させた後、必要な部分のみの検索根拠を選択的に表示させることができるようになる。
【００９８】
また、図１３Ｃでは、本文表示領域１３０４に、検索クエリに対してヒットしたリソースにおけるテキスト文の少なくとも一部が表示され、ユーザがポインタカーソル１３０７を操作して、ポインタカーソル１３０７を関連フレーズ上に重ねると、検索根拠表示領域１３０５’がポップアップされる検索結果画面１３００Ｃの例が示される。例えば、どのフレーズに関連フレーズが関連付けられているかをユーザが把握できるように、該フレーズが例えば強調表示される。
【００９９】
以上のように、本実施形態の検索結果画面は、検索クエリに対してヒットしたリソースにおけるテキスト文と、該リソースがヒットした根拠となった関連フレーズとを関連付けて表示するため、ユーザは、検索根拠となった関連フレーズを容易に認識できるようになる。
【０１００】
次に、図８に示した有向グラフの探索及び更新の処理の他の例を説明する。本例では、探索は、有向グラフにおいて未だ探索が行われていないエッジ（トークン）に対してのみ、つまり、既に探索されたトークンに対する再度の探索を回避するように行われる。このために、本例では、順序付きノードにより構成される木構造を用いる。このような木構造は、トライ（trie）木又はプレフィックス木として知られる。すなわち、トライ木では、あるノードの配下の全ノードは、自身に対応する文字列（ここではトークン）に共通するプレフィックスを有する。本例では、トライ木におけるノードとノードとの間のエッジに、辞書２２に登録されたフレーズを構成する個々の語が割り当てられる。以下では、理解の容易のため、辞書２２の一部に、図１４に示すようなフレーズが登録されているものとして説明する。
【０１０１】
本例の検索エンジン２０は、辞書２２に基づいて作成されたトライ木を備える。図１５は、図１４に示した辞書２２に登録されたフレーズに基づいて作成されたトライ木の一例を説明するための図である。トライ木Ｔは、典型的には、コンピューティングデバイスのプロセッサにより解釈可能なある種のデータ構造ないしはデータ配列であり、例えば、１つ又は複数のファイルないしはテーブルとして構成されるが、これに限られるものではない。また、例えば、トライ木Ｔは、静的なファイルないしはテーブルとして構成され、その一部又は全部がメモリ上に常駐するのではなく、処理の実行中に、所定のアルゴリズムに従って、動的に構成されても良い。
【０１０２】
図１５に示すように、トライ木Ｔは、ノードｎ０をルートとして、ノード間のエッジに、辞書２２に登録されているフレーズの個々の単語が順番に割り当てられている。各ノードには例えば一意の番号が割り当てられる。ルートノードｎ０は、例えば「０」番が割り当てられる。同図では、便宜上、残りの各ノードに１〜１０の番号が割り当てられているものとする。また、図中、黒色で示されるノードは、フレーズ終端ノードであり、辞書２２に登録されたフレーズを識別するためのフラグとして機能する。言い換えれば、ルートノードｎ０からフレーズ終端ノードまでのパスで示されるフレーズは、辞書２２に登録されたフレーズである。例えば、図１４に示したように、‘栄養’及び‘栄養｜療法’は、それぞれ、辞書２２に登録されているため、図１５に示すトライ木では、ノードｎ３及びｎ９は、それぞれ、フレーズ終端ノードとなる。
【０１０３】
図１６Ａ及び１６Ｂは、本発明の一実施形態に係る検索エンジンによるインデックスの作成処理の他の例を説明するためのフローチャートであり、より具体的には、有向グラフの探索及び更新処理のフローチャートを示している。
【０１０４】
図１６Ａに示すように、まず、有向グラフ生成部２３３は、例えば、初期有向グラフの各ノードに、トライ木Ｔのルートノードｎ０を表す番号（ルート番号）「０」を割り当てる（Ｓ１６０１）。なお、代替的に、初期有向グラフの各ノードへのルート番号の割り当ては、初期有向グラフの生成時に行われるようにしても良い（図６のＳ６０３参照）。
【０１０５】
次に、有向グラフ探索部２３４は、初期有向グラフを探索対象の有向グラフに設定し（Ｓ１６０２）、続いて、有向グラフの先頭ノードを１つ選択し、これを現在の探索ノードとして設定する（Ｓ１６０３）。選択された探索ノードは、探索済みのノードとして記憶される。このとき、有向グラフ探索部２３４は、探索ノードの位置及びフレーズを挿入すべき始端位置（以下「フレーズ挿入始端位置」という。）を図示しないキャッシュ領域にキャッシュする（Ｓ１６０４）。これにより、有向グラフ探索部２３４は、キャッシュされた内容に従って、未探索のノードの位置及び関連フレーズを追加すべき位置を特定することができる。
【０１０６】
有向グラフ探索部２３４は、次に、探索ノードに関連付けられたトークン（フレーズ）が、トライ木Ｔの対応するノードに従って検索（retrieve）されるか否かを判断する（Ｓ１６０５）。より具体的には、有向グラフ探索部２３４は、探索ノードに接続されたエッジのトークンを特定し、該特定したトークンが、該探索ノードに割り当てられた番号に対応するトライ木Ｔのノードに接続されたエッジのトークンと一致するか否かを判断する。有向グラフ探索部２３４は、該特定したトークンがトライ木Ｔにおいて検索された場合（Ｓ１６０５のＹｅｓ）、有向グラフにおける該特定したトークンの下流ノードに、トライ木Ｔにおけるトークンの下流ノードに割り当てられた番号を追加的に割り当てる（図１６ＢのＳ１６０６）。
【０１０７】
例えば、有向グラフにおける探索ノードに接続されたトークンが‘ｔｐｎ’であったとする。この場合、有向グラフ探索部２３４は、トライ木Ｔにおいて、ルートノードｎ０に接続されたエッジのトークン‘ｔｐｎ’を見つけ出し、該エッジに接続された下流ノードの番号「２」を、有向グラフにおけるトークン‘ｔｐｎ’に接続された下流ノードに追加的に割り当てる（図１７（ｂ）参照）。
【０１０８】
次に、有向グラフ探索部２３４は、トライ木Ｔの該下流ノードがフレーズ終端ノードであるか否かを判断する（Ｓ１６０７）。有向グラフ探索部２３４は、該下流ノードが終端であると判断する場合（Ｓ１６０７のＹｅｓ）、該下流ノードにさらに下流ノードがあるか否かを判断する（Ｓ１６０８）。有向グラフ探索部２３４が、さらに下流ノードがないと判断する場合（Ｓ１６０８のＮｏ）、これを受けて、有向グラフ生成部２３３は、辞書２２を参照して、該トークン（フレーズ）の関連フレーズを抽出し（Ｓ１６０９）、該抽出した関連フレーズを有向グラフの対応するノード間に追加的に接続することによって、有向グラフを更新する（Ｓ１６１０）。つまり、有向グラフ生成部２３３は、関連フレーズを含むパスを、キャッシュされたフレーズ挿入始端位置のノードと有向グラフにおけるトークンの下流ノード（挿入後端位置のノード）とに並列的に接続する。有向グラフ生成部２３３による有向グラフの更新後、有向グラフ探索部２３４は、有向グラフにおいて新たに追加された関連フレーズに接続されたノードに、ルートノードｎ０の番号「０」を割り当て（Ｓ１６１１）、Ｓ１６０３（図１６Ａ）の処理に戻る。
【０１０９】
一方、有向グラフ探索部２３４は、トライ木Ｔの該下流ノードがフレーズ終端ノードでないと判断する場合（Ｓ１６０７のＮｏ）、次の探索ノードを設定するため、Ｓ１６０３の処理に戻る。加えて、有向グラフ探索部２３４は、トライ木Ｔの該下流ノードにさらに下流ノードがあると判断する場合もまた（Ｓ１６０８のＹｅｓ）、次の探索ノードを設定するため、Ｓ１６０３の処理に戻る。
【０１１０】
また、Ｓ１６０５において、有向グラフ探索部２３４は、該特定したトークンがトライ木Ｔにおいて検索できなかった場合（Ｓ１６０５のＮｏ）、有向グラフ内のすべてのノードを探索したか否かを判断する（Ｓ１６１２）。有向グラフ探索部２３４は、有向グラフ内のすべてのノードを探索していないと判断する場合（Ｓ１６１２のＮｏ）、有向グラフ内の探索を続行するため、Ｓ１６０３の処理に戻る。一方、有向グラフ探索部２３４は、有向グラフ内のすべてのノードを探索したと判断する場合（Ｓ１６１２のＹｅｓ）、探索処理を終了する。
【０１１１】
次に、上記のトライ木Ｔを用いた、検索エンジン２０による有向グラフの展開処理の一例を説明する。図１７は、本発明の一実施形態に係る検索エンジンにより有向グラフが展開される処理過程の他の例を説明するための図である。なお、同図中、白色で示されるノードは、探索の対象となるノード（未探索ノード）を示し、黒色で示されるノードは、探索済みのノードを示すものとする。
【０１１２】
上述したように、入力されたテキスト文に基づいて、初期有向グラフが生成されたとする。同図（ａ）は、初期有向グラフの一部を示している。初期有向グラフの各ノードには、ルート番号「０」が割り当てられている。有向グラフ探索部２３４は、有向グラフの探索過程で、白抜き矢印で示されるノードを探索ノードとして設定する。また、有向グラフ探索部２３４は、上述したように、探索ノード位置及びフレーズ挿入始端位置をキャッシュ領域にキャッシュする。
【０１１３】
次に、有向グラフ探索部２３４は、探索ノードに接続されたエッジのトークン‘ｔｐｎ’が、該探索ノードに割り当てられた番号「０」に対応するトライ木Ｔのノードに接続されたエッジのトークンと一致するか否かを判断する。本例では、トライ木Ｔにおいて、ルートノードｎ０に接続されたエッジの１つにトークン‘ｔｐｎ’があるため、有向グラフ探索部２３４は、有向グラフの該トークンの下流ノードに、トライ木Ｔの該トークンの下流ノードに割り当てられた番号「２」を追加的に割り当てる（同図（ｂ））。
【０１１４】
次に、有向グラフ探索部２３４は、トライ木Ｔにおける該トークンの下流ノードがフレーズ終端ノードであると判断し、これを受けて、有向グラフ生成部２３３は、辞書２２（図１４）を参照して、該トークン（フレーズ）の関連フレーズ‘ｔｏｔａｌ｜ｐａｒｅｎｔｅｒａｌ｜ｎｕｔｒｉｔｉｏｎ’を、キャッシュされているフレーズ挿入始端位置に従って有向グラフに追加するとともに、新たに追加されたノードに、ルートノードｎ０の番号「０」を割り当てる（同図（ｃ））。
【０１１５】
その後、有向グラフ探索部２３４は、同様にして、探索の処理を進め、同図（ｄ）に示されるように、黒色で示されるノードについて探索が終了し、白抜き矢印で示されるノードを探索ノードとして設定したとする。ここで、有向グラフ探索部２３４は、トライ木Ｔ内の検索において、ノードｎ６からのエッジのトークン‘ｎｕｔｒｉｔｉｏｎ’に従い、下位ノードのノード番号「９」を、有向グラフの下位ノードに割り当てる。なお、有向グラフ探索部２３４は、ノードｎ６がフレーズ終端ノードであることから、辞書２２を参照して、‘ｔｏｔａｌ｜ｐａｒｅｎｔｅｒａｌ｜ｎｕｔｒｉｔｉｏｎ’の関連フレーズ（トークン）‘ｔｐｎ’のパスを接続することになるところ、関連フレーズ‘ｔｐｎ’はフレーズ挿入位置にすでに存在するため、有向グラフ探索部２３４は、このパスの接続処理を行わない。これにより、有向グラフの展開処理において冗長なパスの追加が抑制される。
【０１１６】
続いて、有向グラフ探索部２３４は、同様に探索の処理を進め、トライ木Ｔのノードｎ４がフレーズ終端ノードであるため、辞書２２を参照して、有向グラフにフレーズ挿入位置にトークン‘栄養’のパスを接続する（同図（ｅ））。
【０１１７】
上記のようにして、有向グラフ探索部２３４による有向グラフの探索の結果、有向グラフ生成部２３３は、最終的に、同図（ｆ）に示すような有向グラフを生成する。
【０１１８】
なお、上記の処理において、有向グラフ生成部２３３が行う処理の一部を有向グラフ探索部２３４が行うように構成しても良いし、有向グラフ探索部２３４が行う処理の一部を有向グラフ生成部２３３が行うように構成しても良い。
【０１１９】
以上のように本実施形態によれば、インデックス型検索エンジンにおいて、収集されたリソースを効率的に検索することができるインデックス２４１が作成される。これにより、ユーザは、インデックス２４１の作成の基となった収集されたリソースに含まれるフレーズ以外のフレーズによっても、該リソースにアクセスすることができるようになる。したがって、例えば医療分野のような専門分野において、特定のフレーズに基づいて、類義語などの関連フレーズ群を含むリソースを幅広く効率的に検索することができるようになる。
【０１２０】
また、例えばＯＲ検索を含む検索クエリに基づいて本実施形態のインデックス２４１に対して検索が行われた場合であっても、ユーザに検索の根拠が提示されることで、ユーザは、複数のフレーズの中から、リソースのヒットに貢献したフレーズを容易に把握することができるようになる。また、検索クエリからユーザが予期しないリソースがヒットされた場合であっても、検索の根拠が提示されるため、ユーザは、検索エンジン２０が正常に機能していることを認識できるようになる。
【０１２１】
上記各実施形態は、本発明を説明するための例示であり、本発明をこれらの実施形態にのみ限定する趣旨ではない。本発明は、その要旨を逸脱しない限り、さまざまな形態で実施することができる。
【０１２２】
例えば、本明細書に開示される方法においては、その結果に矛盾が生じない限り、ステップ、動作又は機能を並行して又は異なる順に実施しても良い。説明されたステップ、動作及び機能は、単なる例として提供されており、ステップ、動作及び機能のうちのいくつかは、発明の要旨を逸脱しない範囲で、省略でき、また、互いに結合させることで一つのものとしてもよく、また、他のステップ、動作又は機能を追加しても良い。
【０１２３】
また、本明細書では、さまざまな実施形態が開示されているが、一の実施形態における特定のフィーチャ（技術的事項）を、適宜改良しながら、他の実施形態に追加し、又は該他の実施形態における特定のフィーチャと置換することができ、そのような形態も本発明の要旨に含まれる。
【産業上の利用可能性】
【０１２４】
本発明は、情報検索技術の分野に広く利用することができる。
【符号の説明】
【０１２５】
１…情報検索システム
１０…コンピュータネットワーク
２０…検索エンジン
２１…クローラ
２２…辞書
２３…インデクサ
２３１…入力インターフェース部
２３２…テキスト処理部
２３３…有向グラフ生成部
２３４…有向グラフ探索部
２３５…インデックス作成部
２４…データベース
２４１…インデックス
２５…クエリサーバ
３０…クライアント
【図１】
2019153271.tif 000003
【図２】
2019153271.tif 000004
【図３】
2019153271.tif 000005
【図４】
2019153271.tif 000006
【図５】
2019153271.tif 000007
【図６】
2019153271.tif 000008
【図７】
2019153271.tif 000009
【図８】
2019153271.tif 000010
【図９】
2019153271.tif 000011
【図１０】
2019153271.tif 000012
【図１１】
2019153271.tif 000013
【図１２Ａ】
2019153271.tif 000014
【図１２Ｂ】
2019153271.tif 000015
【図１３Ａ】
2019153271.tif 000016
【図１３Ｂ】
2019153271.tif 000017
【図１３Ｃ】
2019153271.tif 000018
【図１４】
2019153271.tif 000019
【図１５】
2019153271.tif 000020
【図１６Ａ】
2019153271.tif 000021
【図１６Ｂ】
2019153271.tif 000022
【図１７】
2019153271.tif 000023
【図１８】
2019153271.tif 000024