情報検索装置、情報検索方法及び情報検索プログラム
【課題】検索条件により文書集合が限定された場合でも、スコア算出時に高速にこれら値を取得し、検索語に対する各文書のスコアの出力を行うこと。
【解決手段】本発明における情報検索装置は、1以上の検索語と分類キーとを含む検索条件を入力する検索条件入力手段と、分類キー毎に検索対象の文書の母集団が対応付けられるとともに、母集団内の文書格納数値と文書の平均文書長値と、複数の検索対象の文書内のワード毎に当該ワードを含む文書頻度値とが算出され格納された索引情報を記憶した記憶手段と、分類キーに対応付けされた母集団の文書格納数値及び平均文書長値と、分類キーに対応付けられた母集団内の文書のうち、検索語と一致するワードを含む当該母集団の文書頻度値とを取得し、取得した値に基づいて当該母集団内の文書毎の適合度を算出し文書を検索する検索手段と、文書に適合度を付して出力する検索結果出力手段とを有する。
【解決手段】本発明における情報検索装置は、1以上の検索語と分類キーとを含む検索条件を入力する検索条件入力手段と、分類キー毎に検索対象の文書の母集団が対応付けられるとともに、母集団内の文書格納数値と文書の平均文書長値と、複数の検索対象の文書内のワード毎に当該ワードを含む文書頻度値とが算出され格納された索引情報を記憶した記憶手段と、分類キーに対応付けされた母集団の文書格納数値及び平均文書長値と、分類キーに対応付けられた母集団内の文書のうち、検索語と一致するワードを含む当該母集団の文書頻度値とを取得し、取得した値に基づいて当該母集団内の文書毎の適合度を算出し文書を検索する検索手段と、文書に適合度を付して出力する検索結果出力手段とを有する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、情報検索装置、情報検索方法及び情報検索プログラムに関する。
【背景技術】
【0002】
近年、電子データに対する検索技術あるいは検索結果のランキング検索技術は、検索対象の情報量の増大による検索結果数の増大のため、ますます重要な技術となっている。求める情報が大量の検索結果に埋もれてしまい、見つけることが困難になっているからである。
【0003】
検索システムで用いられるランキング検索は、検索条件を満たす検索結果集合をある評価方法で順序付けて出力する機能である。検索条件と評価方法が適切であれば、ランキング上位には利用者が求めるデータが出力される可能性が高くなる。またランキングの上位に利用者が求めるデータと近いデータが存在しなければ、早い段階で検索条件の見直しも可能になる。このようにランキング検索は利用者の検索負担を小さくするための必須機能となっている。
【0004】
ランキング検索の精度を左右する評価方法には、Webページ検索でよく用いられているページへの被参照数を利用した方法や検索条件に含まれる検索語のデータベースにおける出現頻度を利用した方法などがあり、特に後者においては上述したWebページのハイパーリンクや学術論文の引用のような、他のデータへの参照・被参照が存在しないデータに対しても有効であり、用途が広い。
【0005】
さて、この検索語のデータベースにおける出現頻度を利用した検索結果集合の評価方法は、必ずしも適切でないことがある。具体的に、出現頻度を利用した検索語の重要度の評価方法は、ある検索語を含むデータが、データベース中に少ないほど、検索語の重要度を高く評価している。そして、そのような重要度の高い検索語を多く含み、かつ、それぞれの検索語がデータ内で頻出する文書ほど、スコアが高くなる評価手法を使っている。即ち検索語の重要度は、データベースの検索対象となる情報の母集団に依存し、この母集団の範囲がスコアに影響を与えることになる。
【0006】
これに関する技術として、例えば特許文献1において特許文献を検索する場合、文献中に含まれる文言の指定に加えて、IPC(International Patent Classification)やFI(File Index)等の分類情報が設定されている場合等である。このように分類情報が設定されている場合、検索語(キーワード)による検索は指定された分類情報の範囲内において、即ち限定された母集団の範囲内において行われる。
【0007】
このように検索条件において、検索語のみならず、検索対象とする文書が指定されている場合(つまり検索対象となる情報の母集団が限定されている場合)、検索語の重要度を決める母集団を、検索条件で指定された文書集合に変更してから、検索語の重要度の評価を行うことができる。
【発明の概要】
【発明が解決しようとする課題】
【0008】
しかしながら、上述のような評価に用いる文書母集団を限定された集合に変更する方法は、限定された文書集合の範囲内に対し検索語の重要度を評価できるため、より適切なスコアを算出できることがあるものの、その一方で従来の索引構造ではこの評価を高速に実行できないという問題があった。
【0009】
従来一般の全文索引では、ある索引語がどの文書に含まれているかを高速に検索するために、少なくとも索引語とその索引語を含む文書に対応した文書IDのリストとの組を格納している。またさらにランキング検索を行なう場合には、索引語の単語頻度(tf値:対象の文書における対象の索引語数)、索引語の文書頻度(df値:対象の文書集合における対象の索引語を含む文書数)、文書格納数、対象の文書の文書長、対象の文書集合の平均文書長などの値を全文索引で格納している。
【0010】
いずれの値もスコア算出時に用いられるパラメータでありランキング検索の精度に関わる重要な値であるが、このうち索引語の文書頻度や平均文書長、文書格納数のような値は、検索条件に分類情報のような検索対象を絞り込む条件があった場合、分類情報によって文書母集団は限定された集合に変更されるため、これら値は全文索引に格納されたものをそのまま利用できず、そのため検索の度にあらためて計算される必要があった。これは検索精度と速度とにトレードオフの関係が生じていることになる。
【0011】
本発明は、上記の点に鑑みてなされたものであって、検索精度と速度とにトレードオフの関係を回避すべく、検索条件により文書集合が限定された場合でも、限定された文書集合に対応する索引語の文書頻度、平均文書長及び文書格納数を高速に取得可能な索引を備え、スコア算出時に高速にこれら値を取得し、検索語に対する各文書のスコアの出力を行う情報検索装置、情報検索方法及び情報検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【0012】
上記の目的を達成するために、本発明に係る情報検索装置は、複数の検索対象の文書を表示する順序を指定された検索条件に対する適合度に基づいて決定する情報検索装置であって、1以上の検索語と、前記複数の検索対象の文書のうち前記順序の決定を行う対象となる検索対象文書の母集団を限定する分類キーとを含む検索条件を入力する検索条件入力手段と、前記分類キー毎に前記検索対象の文書の母集団が対応付けられるとともに、前記母集団内の文書格納数値と、前記母集団内の文書の平均文書長値と、前記複数の検索対象の文書内のワード毎に当該ワードを含む前記母集団内の文書数である文書頻度値とが少なくとも算出され格納された索引情報を記憶した記憶手段と、前記検索条件が入力されたとき、入力分類キーに対応付けされた前記母集団内の文書の文書格納数値及び平均文書長値と、入力分類キーに対応付けられた前記母集団内の文書のうち、入力検索語と一致するワードを含む当該母集団内の文書数である文書頻度値とを前記記憶手段の検索情報から取得し、取得された文書格納数値、平均文書長値、及び文書頻度値を含む適合度を算出するためのパラメータ値に基づいて当該母集団内の文書毎の適合度を算出することにより、文書を検索する検索手段と、検索された文書に適合度を付して検索結果として出力する検索結果出力手段とを有することを特徴とする。
【0013】
また、上記の目的を達成するために、上記情報検索装置において、前記記憶手段の索引情報は、前記分類キー毎に前記ワードが対応付けされて索引が作成され、前記検索手段は、入力分類キー、入力検索語の順で前記索引を辿ることにより前記文書頻度値が取得されることを特徴とする。
【0014】
また、上記の目的を達成するために、上記情報検索装置において、前記記憶手段の索引情報は、前記ワード毎に前記分類キーが対応付けされて索引が作成され、前記検索手段は、入力検索語、入力分類キーの順で前記索引を辿ることにより前記文書頻度値が取得されることを特徴とする。
【0015】
なお、本発明の構成要素、表現または構成要素の任意の組合せを、方法、装置、システム、コンピュータプログラム、記録媒体、などに適用したものも本発明の態様として有効である。
【発明の効果】
【0016】
本発明によれば、検索条件により文書集合が限定された場合でも、限定された文書集合に対応する索引語の文書頻度、平均文書長及び文書格納数を高速に取得可能な索引を備え、スコア算出時に高速にこれら値を取得し、検索語に対する各文書のスコアの出力を行う情報検索装置、情報検索方法及び情報検索プログラムを提供することができる。
【図面の簡単な説明】
【0017】
【図1】本実施の形態に係る情報検索システム例を示す図である。
【図2】検索条件指定画面例を示す。
【図3】本実施形態に係る情報検索装置1のハードウェア構成を示すブロック図である。
【図4】従来の索引情報(全文索引と非全文表)の構成例を示す。
【図5】従来の索引情報(全文索引と非全文表)への文書データ挿入フロー例を示す。
【図6】従来の索引情報(全文索引と非全文表)を使った検索フロー例を示す。
【図7】本実施形態に係る全文と非全文データの複合索引141の構成例を示す。
【図8】本実施形態に係る全文と非全文データの複合索引141への文書データ挿入フロー例を示す。
【図9】本実施形態に係る複合索引141を使った検索フロー例を示す。
【図10】本実施形態に係る複合索引141を使った検索フロー例を示す。
【図11】本実施形態に係る全文と非全文データの複合索引142への文書データ挿入フロー例を示す。
【図12】本実施形態に係る複合索引142を使った検索フロー例を示す。
【発明を実施するための形態】
【0018】
以下、本発明を実施するための最良の形態について図面を参照して説明する。本実施形態においては、文書を検索する情報検索装置を含む情報検索システムを例として説明する。
【0019】
[システム構成]
図1は、本実施の形態に係る情報検索システム例を示す図である。図1に示すように、本実施形態に係る情報検索システムは、情報検索装置1、クライアント装置2及び検索対象情報データベース(DB)150を含む。クライアント装置2は、PC(Personal Computer)等の一般的な情報処理装置によって構成される。情報検索装置1は、ネットワークを介してクライアント装置2と接続されており、クライアント装置2からの検索要求を受けて検索対象情報DB200に格納されている文書情報を検索するサーバとして運用される。
【0020】
検索対象情報DB200(以下単にDBという)は、検索対象の情報としての文書や文献を記憶している。即ち、本実施形態に係る検索対象情報は、DB200に格納されている文書情報(文書ファイル)である。尚、図1に示すように、本実施形態においては、DB200が情報検索装置1とは別に設けられている例を説明するが、DB200を情報検索装置1内部に構成することも可能である。DB200は、HDD等の不揮発性記憶媒体によって構成される。
【0021】
また図に示されるように、本実施形態に係る情報検索装置1は、条件入力部110、検索部120、検索結果出力部130及び索引DB140を有する。
【0022】
条件入力部110は、ユーザのクライアント装置2から検索条件を入力する。図3に示すI/F50によって実現される。なお情報検索装置1の備える操作部70からも検索条件を入力できる。
【0023】
検索部120は、入力された検索条件に基づいて、索引DB140の検索情報を利用して対象となる文書を検索する。検索結果には、検索条件の適合度(スコア)に応じたランキング形式の文書一覧表示等も含まれる。
【0024】
検索結果出力部130は、検索された検索結果を出力する。ユーザのクライアント装置2から検索条件が入力されたときには、クライアント装置2に対して検索された検索結果を出力する。
【0025】
索引DB140は、DB200に格納されている文書の索引情報(索引データ)を記憶しているDB記憶部であり、例えば図3に示すHDD40やRAM20によって実現される。検索対象となる文書数が膨大な場合、検索にかかる時間も長くなっていってしまうが、予め検索対象となるDB200の文書群を走査しておき、高速な検索が可能になるような索引情報を準備しておくことで検索時のパフォーマンスを向上させる。検索情報はインデックスともいい文字列が検索キーとなっている。索引の具体例について図を参照して後述する。
【0026】
ここで、条件入力部110に入力される検索条件は、例えばクライアント装置2(又は操作部70)から入力できる。図2は、検索条件指定画面例を示す。ユーザは当該画面の「普通文指定(又はキーワード指定)」及び「分類情報指定」に検索条件を入力する。「普通文指定(又はキーワード指定)」には、文章形式又はワード形式で検索語を入力する。「分類情報指定」には、検索対象となる文書の母集団を指定するための所定の分類キーや分類コードを入力する。例えば検索対象の文書が特許文献である場合には、「G06F 17/30」などがここに入力される。このように本実施形態に係る情報検索装置1は、入力された少なくとも1以上の検索語及び1以上の所定の分類キーに基づいて検索処理を行うものである。
【0027】
次に、本実施形態に係る情報検索装置1のハードウェア構成について説明する。図3は、本実施形態に係る情報検索装置1のハードウェア構成を示すブロック図である。図3に示すように、本実施形態に係る情報検索装置1は、一般的なサーバやPC(Personal Computer)等の情報処理端末と同様の構成を有する。即ち、本実施形態に係る情報検索装置1は、CPU(Central Processing Unit)10、RAM(Random Access Memory)20、ROM(Read Only Memory)30、HDD(Hard Disk Drive)40及びI/F50がバス80を介して接続されている。また、I/F50にはLCD(Liquid Crystal Display)60及び操作部70が接続されている。
【0028】
CPU10は演算手段であり、情報検索装置1全体の動作を制御する。RAM20は、情報の高速な読み書きが可能な揮発性の記憶媒体であり、CPU10が情報を処理する際の作業領域として用いられる。ROM30は、読み出し専用の不揮発性記憶媒体であり、ファームウェア等のプログラムが格納されている。HDD40は、情報の読み書きが可能な不揮発性の記憶媒体であり、OS(Operating System)や各種の制御プログラム、アプリケーション・プログラム等が格納される。I/F50は、バス80と各種のハードウェアやネットワーク等を接続し制御する。LCD60は、ユーザが情報検索装置1の状態を確認するための視覚的ユーザインタフェースである。操作部70は、キーボードやマウス等、ユーザが情報検索装置1に情報(例えば検索条件)を入力するためのユーザインタフェースである。尚、図1において説明したように、本実施形態に係る情報検索装置1は、クライアント装置2に対するサーバとして運用される。従って、LCD60及び操作部70等のユーザインタフェースは省略することも可能である。
【0029】
このようなハードウェア構成において、ROM30やHDD40若しくは図示しない光学ディスク等の記憶媒体に格納されたプログラムがRAM20に読み出され、CPU10の制御に従って動作することにより、ソフトウェア制御部(図1)が構成される。このようにして構成されたソフトウェア制御部と、ハードウェアとの組み合わせによって、本実施形態に係る情報検索装置1の機能を実現する機能ブロックが構成される。
【0030】
[従来例]
さてここで、まず従来の全文索引の構成及び動作について説明してから、その後本実施形態に係る全文及び非全文の複合索引の構成及び動作を説明する。なおシステム構成については、従来例においても上述と概ね同等の構成でよい。但し索引DB140の索引情報(索引データ)及び検索部120による索引情報を利用した検索動作の点では差異がある。
【0031】
図4は、従来の索引情報(全文索引と非全文表)の構成例を示す。全文索引は、索引語(図中indexkey=A、indexkey=Bなど)から、その索引語を含む文書の文書ID(各文書に付けられた一意の値で図中docID)等を格納したエントリを素早く取得できるデータ構造を持っている。またランキング検索をするのであれば、指定された検索条件に含まれる検索語等が夫々の文書において出現する回数である索引語の単語頻度(図中tf:Term Frequency)や、検索語等を含む文書の数である索引語の文書頻度(図中df:Document Frequency)などもエントリに含まれる。他にも文書長表において、各文書の文書長(図中len)や、文書集合の平均文書長(図中aveLen)や、格納文書数(図中N)なども含まれる。全文索引は、検索対象となるDB200の文書群中のワードが抽出され上述の各値(td,tf,len,aveLen等)が計算されて予めインデックス化される。
【0032】
非全文表に関し、DB200の文書は予めカテゴライズされており予め分類キー(図中key=#1、key=#2など)が指定されている。非全文表は、分類キー毎にその分類キーに属する文書ID(図中docID)がインデックス化されており、入力された分類キーから、検索対象文書の母集団の文書IDを素早く取得できるデータ構造を持っている。また文書IDからその逆引きが必要な場合は逆引きで分類キーを取得できる。
【0033】
なお本図では、あくまで一例として、索引語に対応するエントリを取得するための構造は木(ツリー)構造を想定した図を用い、文書長等を格納する構造や非全文表には配列を想定した図を用いているが、いうまでもなく個々のデータ構造の実装には他にも様々な方法がありうる。
【0034】
図5は、従来の索引情報(全文索引と非全文表)への文書データ挿入フロー例を示す。つまりDB200に文書が追加されたとき、この追加文書を索引情報DB140の索引に追加更新するものである。索引への入力は、追加文書の文書IDと追加文書の全文データと非全文データ(例えば追加文書の分類キーという)とから構成されているとする。また、全文データは解析済みで、追加文書内の全文データに含まれるワード:索引語(indexkey)とその単語頻度(tf)の組が計算を経て得られているものとする。
【0035】
まず、非全文表にアクセスする(S101)。非全文表に、非全文データをキーとし非全文キーに対応する値を文書IDとしたデータを追加する(S102)。
【0036】
次に、全文索引にアクセスする(S103)。追加文書内の1のワードを全文索引のキーとして、全文索引の値である索引語(indexkey)のエントリを取得する(S104)。そのエントリに文書ID(docID)と単語頻度(tf)の組を一行追加する(S105)。文書ID(docID)と単語頻度(tf)の組を1件追加したので文書頻度(df)を1インクリメントする(S106)。
【0037】
次いで追加文書内の新たな1のワードを全文索引のキーとして、同様の処理を繰り返す(S107→S104)。新たなワードがもうない場合は、次のステップに移動する(S107→S108)。
【0038】
次に、文書長表にアクセスする(S108)。文書長表に、文書IDをキーとし、文書IDに対する値を文書長(len)としたデータを一行追加する(S109)。文書IDを1件追加したので、文書長表の格納件数(N)を1インクリメントし、また追加した文書の文書長の増加分に合わせて平均文書長(aveLen)を更新する(S110)。
【0039】
図6は、従来の索引情報(全文索引と非全文表)を使った検索フロー例を示す。検索に際し、ユーザから入力された検索条件は、検索語と分類キーであり(例えば図2)、検索語(全文条件ともいう)によるマッチングと、分類キー(非全文条件ともいう)よるマッチングとの両方が満たされるものを検索結果とする。なお、全文条件は例えば図2のように「普通文指定」で入力された場合、「AのBでCされたD」という文章を「A/の/B/で/C/された/D」というようにワードに区切り、このうち意味のあるワードを抽出し検索語(A、B、C、D)とすればよい。これを検索語リストに入れておく。
【0040】
まず、非全文表にアクセスする(S201)。非全文条件の分類キーをキーとして、条件を満たす文書IDを全て取得する(S202)。また取得された文書IDの数をカウントし絞り込み文書格納数(N)として取得する。絞り込み文書格納数(N)は、分類キーによって絞り込まれて限定された分類集合文書数である。なおここで文書IDが大量だった場合、その取得に計算やメモリ領域確保のコストがかかる。
【0041】
次に、全文索引にアクセスする(S203)。索引語を全文索引のキーとして、全文索引の値である索引語のエントリを取得する(S204)。そして取得されたエントリに含まれる文書ID(docID)と単語頻度(tf)の組のうち、非全文表で取得された文書IDと合致する組のみメモリに保持する(S205)。ここで合致するかどうかを確認しながら保持する組を決定するので取得コストがかかる。そして保持した文書ID(docID)と単語頻度(tf)の組の個数から、分類キーによって限定された文書の母集団における絞り込み文書頻度(df)が得られる(S206)。
【0042】
次に、文書長表にアクセスする(S207)。エントリから取得した文書IDと合致する組の文書長だけでなく、非全文表で得られた文書IDと合致する文書IDの文書長を全て取得する。ここで非全文表で得られた文書IDの数は、エントリから取得された文書IDの数より多いため文書長の取得コストがかかる。取得された文書長から、分類キーによって限定された文書の母集団における絞り込み平均文書長(aveLen)を計算する(S209)。
【0043】
次に、索引語毎に各文書との適合度を、これまでに取得された単語頻度(tf)、絞り込み文書頻度(df)、絞り込み文書格納数(N)、文書長(len)、絞り込み平均文書長(aveLen)を使って計算する(S210)。なお入力された索引語に対する文書の適合度(スコア)の具体的計算については、公知のものを適用できるが例えば本発明者による特開2009−271659号(段落番号0055−0057、0085等)を参考にできる。ここでの文書頻度、平均文書長及び文書格納数は、非全文条件である分類キーによって絞り込まれ限定された文書の母集団から取得された値なので適合度の精度は高い。
【0044】
次に、全文条件の索引語リストに検索語の残りがあれば、全文索引へのアクセスから繰り返し(S211→S204)、残りがなければ次のステップに進む(S211→S212)。
【0045】
次に、複数の検索語が入力されている場合には、検索語毎対して文献の適合度が計算されているので、文書毎に適合度を合成する(S212)。検索結果としてランキング形式で文書を表示するため、適合度の高い順に文書ID等をクライアント装置2などの呼び出し側に返す(S213)。
【0046】
[実施形態1]
さて次に、実施形態1に係る全文及び非全文の複合索引の構成及び動作を説明する。
【0047】
図7は、本実施形態に係る全文と非全文データの複合索引141の構成例を示す。従来例の図4と比較し図に示される複合索引141は、図4の全文索引と非全文表とを統合し、また全文索引の索引構造と文書長表とを、非全文表の非全文データ(図中key=#1,key=#2など)の値で分割したものである。非全文データは例えば分類コードであるので、文書の分類カテゴリ数に応じた数に分割されている。
【0048】
この複合索引141の特徴は、索引を非全文データの値で分割しインデックス化しておくことで、非全文データの値によって変わる索引語の絞り込み文書頻度(df)や絞り込み平均文書長(aveLen)、絞り込み文書格納数(N)は予め計算し索引に登録しておくことができるので、これら値を少ないコストで取得できる。この点、検索の動作において後述する。
【0049】
このように分割された各索引構造においては、複合索引のルートノード(Root)から非全文データの値(図中#1,#2など)への分岐によって、全文索引の検索語のルートノードへ辿ることができる構造になっている。また、非全文データの値によって分割された複数ある文書長表も、非全文データの値(図中#1,#2など)によって一意に選択できる構造を持っている。
【0050】
図8は、本実施形態に係る全文と非全文データの複合索引141への文書データ挿入フロー例を示す。つまりDB200に文書が追加されたとき、この追加文書を索引情報DB140の複合索引141に追加更新するものである。索引への入力は、追加文書の文書IDと追加文書の全文データと非全文データ(例えば追加文書の分類コード)とから構成されているとする。また、追加文書内の全文データは解析済みで、全文データに含まれるワード:索引語(indexkey)とその単語頻度(tf)の組が計算を経て得られているものとする。
【0051】
まず、複合索引141にアクセスし、非全文データ(追加文書の分類コード)が示す索引構造(木構造)にアクセスする(S301)。追加文書内の全文データに含まれる1のワードを全文索引のキーとして、全文索引の値である索引語のエントリを取得する(S302)。そのエントリに文書ID(docID)と単語頻度(tf)の組を一行追加する(S303)。文書ID(docID)と単語頻度(tf)の組を1件追加したので絞り込み文書頻度(df)を1インクリメントする(S304)。
【0052】
次いで追加文書内の新たな1のワードを全文索引のキーとして、同様の処理を繰り返す(S305→S302)。新たなワードがもうない場合は、次のステップに移動する(S305→S306)。
【0053】
次に、非全文データが示す文書長表にアクセスする(S306)。文書長表に、文書IDをキーとし、文書IDに対する値を文書長(len)としたデータを一行追加する(S307)。文書IDを1件追加したので、文書長表の絞り込み格納件数(N)を1インクリメントし、また追加した文書の文書長の増加分に合わせて絞り込み平均文書長(aveLen)を更新する(S308)。なお絞り込み格納件数(N)は分類キーによって分類される文書母集団内の文書数を示す。絞り込み平均文書長(aveLen)は、分類キーによって分類される文書母集団内の文書の平均文書長を示す。
【0054】
以上で示したように、従来例の図6と比較しても、複合索引化による文書データ挿入コストの上昇はほとんどない。
【0055】
図9は、本実施形態に係る複合索引141を使った検索フロー例を示す。検索に際し、入力された検索条件は、検索語と分類コードであり(例えば図2)、検索語によるマッチング(全文条件という)と、分類コードよるマッチング(非全文条件という)との両方が満たされる条件とする。なお、全文条件は例えば図2のように「普通文指定」で入力された場合、上述した通り、文章をワードに区切り、意味のあるワードを抽出し検索語とすればよい。これを検索語リストに入れておく。
【0056】
まず、複合索引141にアクセスし、入力された非全文条件の分類コードをキーとして、非全文データが示す索引構造(木構造)にアクセスする(S401)。例えば「key=#1」のツリーにアクセスする(図7)。入力された索引語を全文索引のキーとして、全文索引の値である索引語のエントリを取得する(S402)。例えば入力された索引語が「A」ならば、「indexkey=A」の子ツリーにアクセスし、「indexkey=A」のエントリを取得する。取得されたそのエントリに含まれる文書ID(docID)と単語頻度(tf)の組を全て取得する(S403)。例えば組(docID,tf)とするならば、(1,3)、(3,1)・・などとなる。またそのエントリから絞り込み文書頻度(df)を取得する(S404)。例えばdf=10が取得される。
【0057】
次に、非全文データが示す文書長表にアクセスする(S405)。例えば「key=#1」の文書長表にアクセスする(図7)。その文書長表から、S403で取得した文書IDと合致する文書IDの文書長(len)を全て取得する(S406)。例えば文書ID「1」の文書長「500」、文書ID「3」の文書長「1500」・・などとなる。また絞り込み平均文書長(aveLen)及び絞り込み文書格納数(N)を取得する(S407)。例えばaveLen=900が取得され、N=50が取得される。なおここで、絞り込み文書頻度(df)や絞り込み平均文書長(aveLen)、絞り込み文書格納数(N)は既に複合索引141に登録されているため単にこれら値は取得されればよく、特段の計算等は不要である。
【0058】
次に、索引語毎に各文書との適合度を、これまでに取得された単語頻度(tf)、絞り込み文書頻度(df)、絞り込み文書格納数(N)、文書長(len)、絞り込み平均文書長(aveLen)を使って計算する(S408)。なお入力された索引語に対する文書の適合度(スコア)の具体的計算については、上述した通り、公知のものを適用できる(例えば特開2009−271659号)。ここでの絞り込み文書頻度、絞り込み平均文書長及び絞り込み文書格納数は、非全文条件である分類コードによって限定された文書の母集団から絞り込まれて取得された値なので適合度の精度は高い。
【0059】
次に、全文条件の索引語リストに検索語の残りがあれば、全文索引へのアクセスから繰り返し(S409→S402)、残りがなければ次のステップに進む(S409→S410)。
【0060】
次に、複数の検索語が入力されている場合には、検索語毎対して文献の適合度が計算されているので、文書毎に適合度を合成する(S410)。検索結果としてランキング形式で文書を表示するため、適合度の高い順に文書ID等をクライアント装置2などの呼び出し側に返す(S410)。
【0061】
以上のように、索引語毎に各文書との適合度を算出するに際し、単語頻度(tf)、文書頻度(df)、文書格納数(N)、文書長(len)、平均文書長(aveLen)などの値が必要であるが、このうち文書頻度、平均文書長及び文書格納数の値には、非全文条件である分類コードによって限定された文書の母集団に基づく絞り込み文書頻度、絞り込み平均文書長及び絞り込み文書格納数を用いるため、適合度を高いものとすることができる。そしてここで本実施形態に係る複合索引141は、上述のような索引構造を有するため、絞り込み文書頻度(df)や絞り込み平均文書長(aveLen)、絞り込み文書格納数(N)は予め複合索引141に登録しておくことが可能であり、検索部120が検索を行なうとき、単にこれら値は取得されればよいので(特段の計算等は不要)、検索速度の向上を図ることができる。
【0062】
即ち従来の全文索引を拡張して、全文要素と非全文要素との複合索引を作成し、複合索引において、母集団を限定する条件によって分割された各集合に対応づけて索引を分割しておくことで、各集合における各索引語の文書頻度や各集合における平均文書長及び文書格納数を、分割された各索引にあらかじめ格納しておくことができるため、検索結果の評価時(適合度算出時)にこれらの値を計算なしで使うことができる。
【0063】
[実施形態2]
続いて、実施形態2に係る全文及び非全文の複合索引の構成及び動作を説明する。
【0064】
図10は、本実施形態に係る複合索引141を使った検索フロー例を示す。図に示される複合索引142は、上述の実施形態に係る複合索引141と概ね同様である。図4の全文索引と非全文表とを統合し、また全文索引の索引構造と文書長表とを、非全文表の非全文データ(図中key=#1,key=#2など)の値で分割したものである。
【0065】
但し、実施形態2に係る複合索引141を比較し、本実施形態に係る複合索引142は、文書IDと文書頻度とを取得するためのエントリまでの到達ルートの点で異なっている。ここで分割された各索引構造へは、複合索引のルートノード(Root)から全文データの値(図中indexkey=A, indexkey=Bなど)への分岐によって、非全文データのルートノードへ辿ることができる構造になっている。
【0066】
いずれにしてもこの複合索引142もまた、索引を非全文データの値で分割しインデックス化しておくことで、非全文データの値によって変わる索引語の文書頻度(df)や平均文書長(aveLen)を少ないコストで取得できる。
【0067】
図11は、本実施形態に係る全文と非全文データの複合索引142への文書データ挿入フロー例を示す。但し図8と比較し、その差異はS501及びS502である。
【0068】
まず、複合索引142にアクセスし追加文書内の全文データに含まれる1のワードを全文索引のキーとして、ルートノードから索引構造(木構造)にアクセスする(S501)。次に非全文データ(追加文書の分類コード)をキーとして、全文索引の値である索引語のエントリを取得する(S502)。要するに図8と比較し、複合索引142にアクセスしてから、新エントリとして文書IDと単語頻度との組を格納するためのエントリポイントまで到達するまでに、先に非全文データ(追加文書の分類コード)で引くか、追加文書の全文データ内のワードで引くかの違いであり、いずれにしても最終的には、エントリポイントにおいて追加文書の文書ID(docID)と単語頻度(tf)との組からなる新エントリが追加される。また絞り込み文書頻度(df)も1インクリメントされ更新される。なお、これ以降のステップは図8と同様であるためその説明は省略する。
【0069】
図12は、本実施形態に係る複合索引142を使った検索フロー例を示す。但し図9と比較し、その差異はS601及びS602である。
【0070】
まず、複合索引142にアクセスし、入力された索引語を全文索引のキーとして、ルートノードから全文データが示す索引構造(木構造)にアクセスする(S601)。次に入力された非全文条件の分類コードをキーとして、全文索引の値である索引語のエントリを取得する(S602)。要するに図9と比較し、複合索引142にアクセスしてから、文書IDと単語頻度との組を取得するためのエントリまで到達するまでに、先に非全文データ(追加文書の分類コード)で引くか、追加文書の全文データ内のワードで引くかの違いであり、いずれにしても最終的には、追加文書の文書ID(docID)及び単語頻度(tf)の組のエントリが取得される。また絞り込み文書頻度(df)も取得される。なお、これ以降のステップは図9と同様であるためその説明は省略する。
【0071】
[総括]
以上本実施形態に係る情報検索装置1は、索引語毎に各文書との適合度を算出するに際し、単語頻度(tf)、文書頻度(df)、文書格納数(N)、文書長(len)、平均文書長(aveLen)などの値が必要であるが、このうち文書頻度、平均文書長及び文書格納数の値には、非全文条件である分類コードによって限定された文書の母集団に基づく絞り込み文書頻度、絞り込み平均文書長及び絞り込み文書格納数を複合索引から取得して用いるため、適合度を高いものとすることができる。そしてここで本実施形態に係る複合索引は、上述のような索引構造を有するため、絞り込み文書頻度(df)や絞り込み平均文書長(aveLen)、絞り込み文書格納数(N)は予め複合索引に登録しておくことが可能であり、情報検索装置1が検索を行なうとき、単にこれら値は取得されればよいので(特段の計算等は不要)、検索速度の向上を図ることができる。
【0072】
即ち上述の本実施形態によれば、検索条件により文書集合が限定された場合でも、限定された文書集合に対応する索引語の文書頻度、平均文書長及び文書格納数を高速に取得可能な索引を備え、スコア算出時に高速にこれら値を取得し、検索語に対する各文書のスコアの出力を行う情報検索装置等を提供することが可能となる。
【0073】
各実施形態に基づき本発明の説明を行ってきたが、上記各実施形態にあげたその他の要素との組み合わせなど、ここで示した要件に本発明が限定されるものではない。これらの点に関しては、本発明の主旨をそこなわない範囲で変更することが可能であり、その応用形態に応じて適切に定めることができる。また、本発明の構成要素、表現または構成要素の任意の組合せを、方法、装置、システム、コンピュータプログラム、記録媒体、などに適用したものも本発明の態様として有効である。
【符号の説明】
【0074】
1 情報検索装置
2 クライアント装置
10 CPU
20 RAM
30 ROM
40 HDD
50 I/F
60 LCD
70 操作部
80 バス
110 条件入力部
120 検索部
130 検索結果出力部
140 索引DB
200 検索対象情報DB
【先行技術文献】
【特許文献】
【0075】
【特許文献1】特開2009−271659号
【技術分野】
【0001】
本発明は、情報検索装置、情報検索方法及び情報検索プログラムに関する。
【背景技術】
【0002】
近年、電子データに対する検索技術あるいは検索結果のランキング検索技術は、検索対象の情報量の増大による検索結果数の増大のため、ますます重要な技術となっている。求める情報が大量の検索結果に埋もれてしまい、見つけることが困難になっているからである。
【0003】
検索システムで用いられるランキング検索は、検索条件を満たす検索結果集合をある評価方法で順序付けて出力する機能である。検索条件と評価方法が適切であれば、ランキング上位には利用者が求めるデータが出力される可能性が高くなる。またランキングの上位に利用者が求めるデータと近いデータが存在しなければ、早い段階で検索条件の見直しも可能になる。このようにランキング検索は利用者の検索負担を小さくするための必須機能となっている。
【0004】
ランキング検索の精度を左右する評価方法には、Webページ検索でよく用いられているページへの被参照数を利用した方法や検索条件に含まれる検索語のデータベースにおける出現頻度を利用した方法などがあり、特に後者においては上述したWebページのハイパーリンクや学術論文の引用のような、他のデータへの参照・被参照が存在しないデータに対しても有効であり、用途が広い。
【0005】
さて、この検索語のデータベースにおける出現頻度を利用した検索結果集合の評価方法は、必ずしも適切でないことがある。具体的に、出現頻度を利用した検索語の重要度の評価方法は、ある検索語を含むデータが、データベース中に少ないほど、検索語の重要度を高く評価している。そして、そのような重要度の高い検索語を多く含み、かつ、それぞれの検索語がデータ内で頻出する文書ほど、スコアが高くなる評価手法を使っている。即ち検索語の重要度は、データベースの検索対象となる情報の母集団に依存し、この母集団の範囲がスコアに影響を与えることになる。
【0006】
これに関する技術として、例えば特許文献1において特許文献を検索する場合、文献中に含まれる文言の指定に加えて、IPC(International Patent Classification)やFI(File Index)等の分類情報が設定されている場合等である。このように分類情報が設定されている場合、検索語(キーワード)による検索は指定された分類情報の範囲内において、即ち限定された母集団の範囲内において行われる。
【0007】
このように検索条件において、検索語のみならず、検索対象とする文書が指定されている場合(つまり検索対象となる情報の母集団が限定されている場合)、検索語の重要度を決める母集団を、検索条件で指定された文書集合に変更してから、検索語の重要度の評価を行うことができる。
【発明の概要】
【発明が解決しようとする課題】
【0008】
しかしながら、上述のような評価に用いる文書母集団を限定された集合に変更する方法は、限定された文書集合の範囲内に対し検索語の重要度を評価できるため、より適切なスコアを算出できることがあるものの、その一方で従来の索引構造ではこの評価を高速に実行できないという問題があった。
【0009】
従来一般の全文索引では、ある索引語がどの文書に含まれているかを高速に検索するために、少なくとも索引語とその索引語を含む文書に対応した文書IDのリストとの組を格納している。またさらにランキング検索を行なう場合には、索引語の単語頻度(tf値:対象の文書における対象の索引語数)、索引語の文書頻度(df値:対象の文書集合における対象の索引語を含む文書数)、文書格納数、対象の文書の文書長、対象の文書集合の平均文書長などの値を全文索引で格納している。
【0010】
いずれの値もスコア算出時に用いられるパラメータでありランキング検索の精度に関わる重要な値であるが、このうち索引語の文書頻度や平均文書長、文書格納数のような値は、検索条件に分類情報のような検索対象を絞り込む条件があった場合、分類情報によって文書母集団は限定された集合に変更されるため、これら値は全文索引に格納されたものをそのまま利用できず、そのため検索の度にあらためて計算される必要があった。これは検索精度と速度とにトレードオフの関係が生じていることになる。
【0011】
本発明は、上記の点に鑑みてなされたものであって、検索精度と速度とにトレードオフの関係を回避すべく、検索条件により文書集合が限定された場合でも、限定された文書集合に対応する索引語の文書頻度、平均文書長及び文書格納数を高速に取得可能な索引を備え、スコア算出時に高速にこれら値を取得し、検索語に対する各文書のスコアの出力を行う情報検索装置、情報検索方法及び情報検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【0012】
上記の目的を達成するために、本発明に係る情報検索装置は、複数の検索対象の文書を表示する順序を指定された検索条件に対する適合度に基づいて決定する情報検索装置であって、1以上の検索語と、前記複数の検索対象の文書のうち前記順序の決定を行う対象となる検索対象文書の母集団を限定する分類キーとを含む検索条件を入力する検索条件入力手段と、前記分類キー毎に前記検索対象の文書の母集団が対応付けられるとともに、前記母集団内の文書格納数値と、前記母集団内の文書の平均文書長値と、前記複数の検索対象の文書内のワード毎に当該ワードを含む前記母集団内の文書数である文書頻度値とが少なくとも算出され格納された索引情報を記憶した記憶手段と、前記検索条件が入力されたとき、入力分類キーに対応付けされた前記母集団内の文書の文書格納数値及び平均文書長値と、入力分類キーに対応付けられた前記母集団内の文書のうち、入力検索語と一致するワードを含む当該母集団内の文書数である文書頻度値とを前記記憶手段の検索情報から取得し、取得された文書格納数値、平均文書長値、及び文書頻度値を含む適合度を算出するためのパラメータ値に基づいて当該母集団内の文書毎の適合度を算出することにより、文書を検索する検索手段と、検索された文書に適合度を付して検索結果として出力する検索結果出力手段とを有することを特徴とする。
【0013】
また、上記の目的を達成するために、上記情報検索装置において、前記記憶手段の索引情報は、前記分類キー毎に前記ワードが対応付けされて索引が作成され、前記検索手段は、入力分類キー、入力検索語の順で前記索引を辿ることにより前記文書頻度値が取得されることを特徴とする。
【0014】
また、上記の目的を達成するために、上記情報検索装置において、前記記憶手段の索引情報は、前記ワード毎に前記分類キーが対応付けされて索引が作成され、前記検索手段は、入力検索語、入力分類キーの順で前記索引を辿ることにより前記文書頻度値が取得されることを特徴とする。
【0015】
なお、本発明の構成要素、表現または構成要素の任意の組合せを、方法、装置、システム、コンピュータプログラム、記録媒体、などに適用したものも本発明の態様として有効である。
【発明の効果】
【0016】
本発明によれば、検索条件により文書集合が限定された場合でも、限定された文書集合に対応する索引語の文書頻度、平均文書長及び文書格納数を高速に取得可能な索引を備え、スコア算出時に高速にこれら値を取得し、検索語に対する各文書のスコアの出力を行う情報検索装置、情報検索方法及び情報検索プログラムを提供することができる。
【図面の簡単な説明】
【0017】
【図1】本実施の形態に係る情報検索システム例を示す図である。
【図2】検索条件指定画面例を示す。
【図3】本実施形態に係る情報検索装置1のハードウェア構成を示すブロック図である。
【図4】従来の索引情報(全文索引と非全文表)の構成例を示す。
【図5】従来の索引情報(全文索引と非全文表)への文書データ挿入フロー例を示す。
【図6】従来の索引情報(全文索引と非全文表)を使った検索フロー例を示す。
【図7】本実施形態に係る全文と非全文データの複合索引141の構成例を示す。
【図8】本実施形態に係る全文と非全文データの複合索引141への文書データ挿入フロー例を示す。
【図9】本実施形態に係る複合索引141を使った検索フロー例を示す。
【図10】本実施形態に係る複合索引141を使った検索フロー例を示す。
【図11】本実施形態に係る全文と非全文データの複合索引142への文書データ挿入フロー例を示す。
【図12】本実施形態に係る複合索引142を使った検索フロー例を示す。
【発明を実施するための形態】
【0018】
以下、本発明を実施するための最良の形態について図面を参照して説明する。本実施形態においては、文書を検索する情報検索装置を含む情報検索システムを例として説明する。
【0019】
[システム構成]
図1は、本実施の形態に係る情報検索システム例を示す図である。図1に示すように、本実施形態に係る情報検索システムは、情報検索装置1、クライアント装置2及び検索対象情報データベース(DB)150を含む。クライアント装置2は、PC(Personal Computer)等の一般的な情報処理装置によって構成される。情報検索装置1は、ネットワークを介してクライアント装置2と接続されており、クライアント装置2からの検索要求を受けて検索対象情報DB200に格納されている文書情報を検索するサーバとして運用される。
【0020】
検索対象情報DB200(以下単にDBという)は、検索対象の情報としての文書や文献を記憶している。即ち、本実施形態に係る検索対象情報は、DB200に格納されている文書情報(文書ファイル)である。尚、図1に示すように、本実施形態においては、DB200が情報検索装置1とは別に設けられている例を説明するが、DB200を情報検索装置1内部に構成することも可能である。DB200は、HDD等の不揮発性記憶媒体によって構成される。
【0021】
また図に示されるように、本実施形態に係る情報検索装置1は、条件入力部110、検索部120、検索結果出力部130及び索引DB140を有する。
【0022】
条件入力部110は、ユーザのクライアント装置2から検索条件を入力する。図3に示すI/F50によって実現される。なお情報検索装置1の備える操作部70からも検索条件を入力できる。
【0023】
検索部120は、入力された検索条件に基づいて、索引DB140の検索情報を利用して対象となる文書を検索する。検索結果には、検索条件の適合度(スコア)に応じたランキング形式の文書一覧表示等も含まれる。
【0024】
検索結果出力部130は、検索された検索結果を出力する。ユーザのクライアント装置2から検索条件が入力されたときには、クライアント装置2に対して検索された検索結果を出力する。
【0025】
索引DB140は、DB200に格納されている文書の索引情報(索引データ)を記憶しているDB記憶部であり、例えば図3に示すHDD40やRAM20によって実現される。検索対象となる文書数が膨大な場合、検索にかかる時間も長くなっていってしまうが、予め検索対象となるDB200の文書群を走査しておき、高速な検索が可能になるような索引情報を準備しておくことで検索時のパフォーマンスを向上させる。検索情報はインデックスともいい文字列が検索キーとなっている。索引の具体例について図を参照して後述する。
【0026】
ここで、条件入力部110に入力される検索条件は、例えばクライアント装置2(又は操作部70)から入力できる。図2は、検索条件指定画面例を示す。ユーザは当該画面の「普通文指定(又はキーワード指定)」及び「分類情報指定」に検索条件を入力する。「普通文指定(又はキーワード指定)」には、文章形式又はワード形式で検索語を入力する。「分類情報指定」には、検索対象となる文書の母集団を指定するための所定の分類キーや分類コードを入力する。例えば検索対象の文書が特許文献である場合には、「G06F 17/30」などがここに入力される。このように本実施形態に係る情報検索装置1は、入力された少なくとも1以上の検索語及び1以上の所定の分類キーに基づいて検索処理を行うものである。
【0027】
次に、本実施形態に係る情報検索装置1のハードウェア構成について説明する。図3は、本実施形態に係る情報検索装置1のハードウェア構成を示すブロック図である。図3に示すように、本実施形態に係る情報検索装置1は、一般的なサーバやPC(Personal Computer)等の情報処理端末と同様の構成を有する。即ち、本実施形態に係る情報検索装置1は、CPU(Central Processing Unit)10、RAM(Random Access Memory)20、ROM(Read Only Memory)30、HDD(Hard Disk Drive)40及びI/F50がバス80を介して接続されている。また、I/F50にはLCD(Liquid Crystal Display)60及び操作部70が接続されている。
【0028】
CPU10は演算手段であり、情報検索装置1全体の動作を制御する。RAM20は、情報の高速な読み書きが可能な揮発性の記憶媒体であり、CPU10が情報を処理する際の作業領域として用いられる。ROM30は、読み出し専用の不揮発性記憶媒体であり、ファームウェア等のプログラムが格納されている。HDD40は、情報の読み書きが可能な不揮発性の記憶媒体であり、OS(Operating System)や各種の制御プログラム、アプリケーション・プログラム等が格納される。I/F50は、バス80と各種のハードウェアやネットワーク等を接続し制御する。LCD60は、ユーザが情報検索装置1の状態を確認するための視覚的ユーザインタフェースである。操作部70は、キーボードやマウス等、ユーザが情報検索装置1に情報(例えば検索条件)を入力するためのユーザインタフェースである。尚、図1において説明したように、本実施形態に係る情報検索装置1は、クライアント装置2に対するサーバとして運用される。従って、LCD60及び操作部70等のユーザインタフェースは省略することも可能である。
【0029】
このようなハードウェア構成において、ROM30やHDD40若しくは図示しない光学ディスク等の記憶媒体に格納されたプログラムがRAM20に読み出され、CPU10の制御に従って動作することにより、ソフトウェア制御部(図1)が構成される。このようにして構成されたソフトウェア制御部と、ハードウェアとの組み合わせによって、本実施形態に係る情報検索装置1の機能を実現する機能ブロックが構成される。
【0030】
[従来例]
さてここで、まず従来の全文索引の構成及び動作について説明してから、その後本実施形態に係る全文及び非全文の複合索引の構成及び動作を説明する。なおシステム構成については、従来例においても上述と概ね同等の構成でよい。但し索引DB140の索引情報(索引データ)及び検索部120による索引情報を利用した検索動作の点では差異がある。
【0031】
図4は、従来の索引情報(全文索引と非全文表)の構成例を示す。全文索引は、索引語(図中indexkey=A、indexkey=Bなど)から、その索引語を含む文書の文書ID(各文書に付けられた一意の値で図中docID)等を格納したエントリを素早く取得できるデータ構造を持っている。またランキング検索をするのであれば、指定された検索条件に含まれる検索語等が夫々の文書において出現する回数である索引語の単語頻度(図中tf:Term Frequency)や、検索語等を含む文書の数である索引語の文書頻度(図中df:Document Frequency)などもエントリに含まれる。他にも文書長表において、各文書の文書長(図中len)や、文書集合の平均文書長(図中aveLen)や、格納文書数(図中N)なども含まれる。全文索引は、検索対象となるDB200の文書群中のワードが抽出され上述の各値(td,tf,len,aveLen等)が計算されて予めインデックス化される。
【0032】
非全文表に関し、DB200の文書は予めカテゴライズされており予め分類キー(図中key=#1、key=#2など)が指定されている。非全文表は、分類キー毎にその分類キーに属する文書ID(図中docID)がインデックス化されており、入力された分類キーから、検索対象文書の母集団の文書IDを素早く取得できるデータ構造を持っている。また文書IDからその逆引きが必要な場合は逆引きで分類キーを取得できる。
【0033】
なお本図では、あくまで一例として、索引語に対応するエントリを取得するための構造は木(ツリー)構造を想定した図を用い、文書長等を格納する構造や非全文表には配列を想定した図を用いているが、いうまでもなく個々のデータ構造の実装には他にも様々な方法がありうる。
【0034】
図5は、従来の索引情報(全文索引と非全文表)への文書データ挿入フロー例を示す。つまりDB200に文書が追加されたとき、この追加文書を索引情報DB140の索引に追加更新するものである。索引への入力は、追加文書の文書IDと追加文書の全文データと非全文データ(例えば追加文書の分類キーという)とから構成されているとする。また、全文データは解析済みで、追加文書内の全文データに含まれるワード:索引語(indexkey)とその単語頻度(tf)の組が計算を経て得られているものとする。
【0035】
まず、非全文表にアクセスする(S101)。非全文表に、非全文データをキーとし非全文キーに対応する値を文書IDとしたデータを追加する(S102)。
【0036】
次に、全文索引にアクセスする(S103)。追加文書内の1のワードを全文索引のキーとして、全文索引の値である索引語(indexkey)のエントリを取得する(S104)。そのエントリに文書ID(docID)と単語頻度(tf)の組を一行追加する(S105)。文書ID(docID)と単語頻度(tf)の組を1件追加したので文書頻度(df)を1インクリメントする(S106)。
【0037】
次いで追加文書内の新たな1のワードを全文索引のキーとして、同様の処理を繰り返す(S107→S104)。新たなワードがもうない場合は、次のステップに移動する(S107→S108)。
【0038】
次に、文書長表にアクセスする(S108)。文書長表に、文書IDをキーとし、文書IDに対する値を文書長(len)としたデータを一行追加する(S109)。文書IDを1件追加したので、文書長表の格納件数(N)を1インクリメントし、また追加した文書の文書長の増加分に合わせて平均文書長(aveLen)を更新する(S110)。
【0039】
図6は、従来の索引情報(全文索引と非全文表)を使った検索フロー例を示す。検索に際し、ユーザから入力された検索条件は、検索語と分類キーであり(例えば図2)、検索語(全文条件ともいう)によるマッチングと、分類キー(非全文条件ともいう)よるマッチングとの両方が満たされるものを検索結果とする。なお、全文条件は例えば図2のように「普通文指定」で入力された場合、「AのBでCされたD」という文章を「A/の/B/で/C/された/D」というようにワードに区切り、このうち意味のあるワードを抽出し検索語(A、B、C、D)とすればよい。これを検索語リストに入れておく。
【0040】
まず、非全文表にアクセスする(S201)。非全文条件の分類キーをキーとして、条件を満たす文書IDを全て取得する(S202)。また取得された文書IDの数をカウントし絞り込み文書格納数(N)として取得する。絞り込み文書格納数(N)は、分類キーによって絞り込まれて限定された分類集合文書数である。なおここで文書IDが大量だった場合、その取得に計算やメモリ領域確保のコストがかかる。
【0041】
次に、全文索引にアクセスする(S203)。索引語を全文索引のキーとして、全文索引の値である索引語のエントリを取得する(S204)。そして取得されたエントリに含まれる文書ID(docID)と単語頻度(tf)の組のうち、非全文表で取得された文書IDと合致する組のみメモリに保持する(S205)。ここで合致するかどうかを確認しながら保持する組を決定するので取得コストがかかる。そして保持した文書ID(docID)と単語頻度(tf)の組の個数から、分類キーによって限定された文書の母集団における絞り込み文書頻度(df)が得られる(S206)。
【0042】
次に、文書長表にアクセスする(S207)。エントリから取得した文書IDと合致する組の文書長だけでなく、非全文表で得られた文書IDと合致する文書IDの文書長を全て取得する。ここで非全文表で得られた文書IDの数は、エントリから取得された文書IDの数より多いため文書長の取得コストがかかる。取得された文書長から、分類キーによって限定された文書の母集団における絞り込み平均文書長(aveLen)を計算する(S209)。
【0043】
次に、索引語毎に各文書との適合度を、これまでに取得された単語頻度(tf)、絞り込み文書頻度(df)、絞り込み文書格納数(N)、文書長(len)、絞り込み平均文書長(aveLen)を使って計算する(S210)。なお入力された索引語に対する文書の適合度(スコア)の具体的計算については、公知のものを適用できるが例えば本発明者による特開2009−271659号(段落番号0055−0057、0085等)を参考にできる。ここでの文書頻度、平均文書長及び文書格納数は、非全文条件である分類キーによって絞り込まれ限定された文書の母集団から取得された値なので適合度の精度は高い。
【0044】
次に、全文条件の索引語リストに検索語の残りがあれば、全文索引へのアクセスから繰り返し(S211→S204)、残りがなければ次のステップに進む(S211→S212)。
【0045】
次に、複数の検索語が入力されている場合には、検索語毎対して文献の適合度が計算されているので、文書毎に適合度を合成する(S212)。検索結果としてランキング形式で文書を表示するため、適合度の高い順に文書ID等をクライアント装置2などの呼び出し側に返す(S213)。
【0046】
[実施形態1]
さて次に、実施形態1に係る全文及び非全文の複合索引の構成及び動作を説明する。
【0047】
図7は、本実施形態に係る全文と非全文データの複合索引141の構成例を示す。従来例の図4と比較し図に示される複合索引141は、図4の全文索引と非全文表とを統合し、また全文索引の索引構造と文書長表とを、非全文表の非全文データ(図中key=#1,key=#2など)の値で分割したものである。非全文データは例えば分類コードであるので、文書の分類カテゴリ数に応じた数に分割されている。
【0048】
この複合索引141の特徴は、索引を非全文データの値で分割しインデックス化しておくことで、非全文データの値によって変わる索引語の絞り込み文書頻度(df)や絞り込み平均文書長(aveLen)、絞り込み文書格納数(N)は予め計算し索引に登録しておくことができるので、これら値を少ないコストで取得できる。この点、検索の動作において後述する。
【0049】
このように分割された各索引構造においては、複合索引のルートノード(Root)から非全文データの値(図中#1,#2など)への分岐によって、全文索引の検索語のルートノードへ辿ることができる構造になっている。また、非全文データの値によって分割された複数ある文書長表も、非全文データの値(図中#1,#2など)によって一意に選択できる構造を持っている。
【0050】
図8は、本実施形態に係る全文と非全文データの複合索引141への文書データ挿入フロー例を示す。つまりDB200に文書が追加されたとき、この追加文書を索引情報DB140の複合索引141に追加更新するものである。索引への入力は、追加文書の文書IDと追加文書の全文データと非全文データ(例えば追加文書の分類コード)とから構成されているとする。また、追加文書内の全文データは解析済みで、全文データに含まれるワード:索引語(indexkey)とその単語頻度(tf)の組が計算を経て得られているものとする。
【0051】
まず、複合索引141にアクセスし、非全文データ(追加文書の分類コード)が示す索引構造(木構造)にアクセスする(S301)。追加文書内の全文データに含まれる1のワードを全文索引のキーとして、全文索引の値である索引語のエントリを取得する(S302)。そのエントリに文書ID(docID)と単語頻度(tf)の組を一行追加する(S303)。文書ID(docID)と単語頻度(tf)の組を1件追加したので絞り込み文書頻度(df)を1インクリメントする(S304)。
【0052】
次いで追加文書内の新たな1のワードを全文索引のキーとして、同様の処理を繰り返す(S305→S302)。新たなワードがもうない場合は、次のステップに移動する(S305→S306)。
【0053】
次に、非全文データが示す文書長表にアクセスする(S306)。文書長表に、文書IDをキーとし、文書IDに対する値を文書長(len)としたデータを一行追加する(S307)。文書IDを1件追加したので、文書長表の絞り込み格納件数(N)を1インクリメントし、また追加した文書の文書長の増加分に合わせて絞り込み平均文書長(aveLen)を更新する(S308)。なお絞り込み格納件数(N)は分類キーによって分類される文書母集団内の文書数を示す。絞り込み平均文書長(aveLen)は、分類キーによって分類される文書母集団内の文書の平均文書長を示す。
【0054】
以上で示したように、従来例の図6と比較しても、複合索引化による文書データ挿入コストの上昇はほとんどない。
【0055】
図9は、本実施形態に係る複合索引141を使った検索フロー例を示す。検索に際し、入力された検索条件は、検索語と分類コードであり(例えば図2)、検索語によるマッチング(全文条件という)と、分類コードよるマッチング(非全文条件という)との両方が満たされる条件とする。なお、全文条件は例えば図2のように「普通文指定」で入力された場合、上述した通り、文章をワードに区切り、意味のあるワードを抽出し検索語とすればよい。これを検索語リストに入れておく。
【0056】
まず、複合索引141にアクセスし、入力された非全文条件の分類コードをキーとして、非全文データが示す索引構造(木構造)にアクセスする(S401)。例えば「key=#1」のツリーにアクセスする(図7)。入力された索引語を全文索引のキーとして、全文索引の値である索引語のエントリを取得する(S402)。例えば入力された索引語が「A」ならば、「indexkey=A」の子ツリーにアクセスし、「indexkey=A」のエントリを取得する。取得されたそのエントリに含まれる文書ID(docID)と単語頻度(tf)の組を全て取得する(S403)。例えば組(docID,tf)とするならば、(1,3)、(3,1)・・などとなる。またそのエントリから絞り込み文書頻度(df)を取得する(S404)。例えばdf=10が取得される。
【0057】
次に、非全文データが示す文書長表にアクセスする(S405)。例えば「key=#1」の文書長表にアクセスする(図7)。その文書長表から、S403で取得した文書IDと合致する文書IDの文書長(len)を全て取得する(S406)。例えば文書ID「1」の文書長「500」、文書ID「3」の文書長「1500」・・などとなる。また絞り込み平均文書長(aveLen)及び絞り込み文書格納数(N)を取得する(S407)。例えばaveLen=900が取得され、N=50が取得される。なおここで、絞り込み文書頻度(df)や絞り込み平均文書長(aveLen)、絞り込み文書格納数(N)は既に複合索引141に登録されているため単にこれら値は取得されればよく、特段の計算等は不要である。
【0058】
次に、索引語毎に各文書との適合度を、これまでに取得された単語頻度(tf)、絞り込み文書頻度(df)、絞り込み文書格納数(N)、文書長(len)、絞り込み平均文書長(aveLen)を使って計算する(S408)。なお入力された索引語に対する文書の適合度(スコア)の具体的計算については、上述した通り、公知のものを適用できる(例えば特開2009−271659号)。ここでの絞り込み文書頻度、絞り込み平均文書長及び絞り込み文書格納数は、非全文条件である分類コードによって限定された文書の母集団から絞り込まれて取得された値なので適合度の精度は高い。
【0059】
次に、全文条件の索引語リストに検索語の残りがあれば、全文索引へのアクセスから繰り返し(S409→S402)、残りがなければ次のステップに進む(S409→S410)。
【0060】
次に、複数の検索語が入力されている場合には、検索語毎対して文献の適合度が計算されているので、文書毎に適合度を合成する(S410)。検索結果としてランキング形式で文書を表示するため、適合度の高い順に文書ID等をクライアント装置2などの呼び出し側に返す(S410)。
【0061】
以上のように、索引語毎に各文書との適合度を算出するに際し、単語頻度(tf)、文書頻度(df)、文書格納数(N)、文書長(len)、平均文書長(aveLen)などの値が必要であるが、このうち文書頻度、平均文書長及び文書格納数の値には、非全文条件である分類コードによって限定された文書の母集団に基づく絞り込み文書頻度、絞り込み平均文書長及び絞り込み文書格納数を用いるため、適合度を高いものとすることができる。そしてここで本実施形態に係る複合索引141は、上述のような索引構造を有するため、絞り込み文書頻度(df)や絞り込み平均文書長(aveLen)、絞り込み文書格納数(N)は予め複合索引141に登録しておくことが可能であり、検索部120が検索を行なうとき、単にこれら値は取得されればよいので(特段の計算等は不要)、検索速度の向上を図ることができる。
【0062】
即ち従来の全文索引を拡張して、全文要素と非全文要素との複合索引を作成し、複合索引において、母集団を限定する条件によって分割された各集合に対応づけて索引を分割しておくことで、各集合における各索引語の文書頻度や各集合における平均文書長及び文書格納数を、分割された各索引にあらかじめ格納しておくことができるため、検索結果の評価時(適合度算出時)にこれらの値を計算なしで使うことができる。
【0063】
[実施形態2]
続いて、実施形態2に係る全文及び非全文の複合索引の構成及び動作を説明する。
【0064】
図10は、本実施形態に係る複合索引141を使った検索フロー例を示す。図に示される複合索引142は、上述の実施形態に係る複合索引141と概ね同様である。図4の全文索引と非全文表とを統合し、また全文索引の索引構造と文書長表とを、非全文表の非全文データ(図中key=#1,key=#2など)の値で分割したものである。
【0065】
但し、実施形態2に係る複合索引141を比較し、本実施形態に係る複合索引142は、文書IDと文書頻度とを取得するためのエントリまでの到達ルートの点で異なっている。ここで分割された各索引構造へは、複合索引のルートノード(Root)から全文データの値(図中indexkey=A, indexkey=Bなど)への分岐によって、非全文データのルートノードへ辿ることができる構造になっている。
【0066】
いずれにしてもこの複合索引142もまた、索引を非全文データの値で分割しインデックス化しておくことで、非全文データの値によって変わる索引語の文書頻度(df)や平均文書長(aveLen)を少ないコストで取得できる。
【0067】
図11は、本実施形態に係る全文と非全文データの複合索引142への文書データ挿入フロー例を示す。但し図8と比較し、その差異はS501及びS502である。
【0068】
まず、複合索引142にアクセスし追加文書内の全文データに含まれる1のワードを全文索引のキーとして、ルートノードから索引構造(木構造)にアクセスする(S501)。次に非全文データ(追加文書の分類コード)をキーとして、全文索引の値である索引語のエントリを取得する(S502)。要するに図8と比較し、複合索引142にアクセスしてから、新エントリとして文書IDと単語頻度との組を格納するためのエントリポイントまで到達するまでに、先に非全文データ(追加文書の分類コード)で引くか、追加文書の全文データ内のワードで引くかの違いであり、いずれにしても最終的には、エントリポイントにおいて追加文書の文書ID(docID)と単語頻度(tf)との組からなる新エントリが追加される。また絞り込み文書頻度(df)も1インクリメントされ更新される。なお、これ以降のステップは図8と同様であるためその説明は省略する。
【0069】
図12は、本実施形態に係る複合索引142を使った検索フロー例を示す。但し図9と比較し、その差異はS601及びS602である。
【0070】
まず、複合索引142にアクセスし、入力された索引語を全文索引のキーとして、ルートノードから全文データが示す索引構造(木構造)にアクセスする(S601)。次に入力された非全文条件の分類コードをキーとして、全文索引の値である索引語のエントリを取得する(S602)。要するに図9と比較し、複合索引142にアクセスしてから、文書IDと単語頻度との組を取得するためのエントリまで到達するまでに、先に非全文データ(追加文書の分類コード)で引くか、追加文書の全文データ内のワードで引くかの違いであり、いずれにしても最終的には、追加文書の文書ID(docID)及び単語頻度(tf)の組のエントリが取得される。また絞り込み文書頻度(df)も取得される。なお、これ以降のステップは図9と同様であるためその説明は省略する。
【0071】
[総括]
以上本実施形態に係る情報検索装置1は、索引語毎に各文書との適合度を算出するに際し、単語頻度(tf)、文書頻度(df)、文書格納数(N)、文書長(len)、平均文書長(aveLen)などの値が必要であるが、このうち文書頻度、平均文書長及び文書格納数の値には、非全文条件である分類コードによって限定された文書の母集団に基づく絞り込み文書頻度、絞り込み平均文書長及び絞り込み文書格納数を複合索引から取得して用いるため、適合度を高いものとすることができる。そしてここで本実施形態に係る複合索引は、上述のような索引構造を有するため、絞り込み文書頻度(df)や絞り込み平均文書長(aveLen)、絞り込み文書格納数(N)は予め複合索引に登録しておくことが可能であり、情報検索装置1が検索を行なうとき、単にこれら値は取得されればよいので(特段の計算等は不要)、検索速度の向上を図ることができる。
【0072】
即ち上述の本実施形態によれば、検索条件により文書集合が限定された場合でも、限定された文書集合に対応する索引語の文書頻度、平均文書長及び文書格納数を高速に取得可能な索引を備え、スコア算出時に高速にこれら値を取得し、検索語に対する各文書のスコアの出力を行う情報検索装置等を提供することが可能となる。
【0073】
各実施形態に基づき本発明の説明を行ってきたが、上記各実施形態にあげたその他の要素との組み合わせなど、ここで示した要件に本発明が限定されるものではない。これらの点に関しては、本発明の主旨をそこなわない範囲で変更することが可能であり、その応用形態に応じて適切に定めることができる。また、本発明の構成要素、表現または構成要素の任意の組合せを、方法、装置、システム、コンピュータプログラム、記録媒体、などに適用したものも本発明の態様として有効である。
【符号の説明】
【0074】
1 情報検索装置
2 クライアント装置
10 CPU
20 RAM
30 ROM
40 HDD
50 I/F
60 LCD
70 操作部
80 バス
110 条件入力部
120 検索部
130 検索結果出力部
140 索引DB
200 検索対象情報DB
【先行技術文献】
【特許文献】
【0075】
【特許文献1】特開2009−271659号
【特許請求の範囲】
【請求項1】
複数の検索対象の文書を表示する順序を指定された検索条件に対する適合度に基づいて決定する情報検索装置であって、
1以上の検索語と、前記複数の検索対象の文書のうち前記順序の決定を行う対象となる検索対象文書の母集団を限定する分類キーとを含む検索条件を入力する検索条件入力手段と、
前記分類キー毎に前記検索対象の文書の母集団が対応付けられるとともに、前記母集団内の文書格納数値と、前記母集団内の文書の平均文書長値と、前記複数の検索対象の文書内のワード毎に当該ワードを含む前記母集団内の文書数である文書頻度値とが少なくとも算出され格納された索引情報を記憶した記憶手段と、
前記検索条件が入力されたとき、入力分類キーに対応付けされた前記母集団内の文書の文書格納数値及び平均文書長値と、入力分類キーに対応付けられた前記母集団内の文書のうち、入力検索語と一致するワードを含む当該母集団内の文書数である文書頻度値とを前記記憶手段の検索情報から取得し、取得された文書格納数値、平均文書長値、及び文書頻度値を含む適合度を算出するためのパラメータ値に基づいて当該母集団内の文書毎の適合度を算出することにより、文書を検索する検索手段と、
検索された文書に適合度を付して検索結果として出力する検索結果出力手段と、
を有することを特徴とする情報検索装置。
【請求項2】
前記記憶手段の索引情報は、前記分類キー毎に前記ワードが対応付けされて索引が作成され、
前記検索手段は、入力分類キー、入力検索語の順で前記索引を辿ることにより前記文書頻度値が取得されること、
を特徴とする請求項1記載の情報検索装置。
【請求項3】
前記記憶手段の索引情報は、前記ワード毎に前記分類キーが対応付けされて索引が作成され、
前記検索手段は、入力検索語、入力分類キーの順で前記索引を辿ることにより前記文書頻度値が取得されること、
を特徴とする請求項1記載の情報検索装置。
【請求項4】
複数の検索対象の文書を表示する順序を指定された検索条件に対する適合度に基づいて決定する情報検索装置における情報検索方法であって、
前記複数の検索対象の文書のうち前記順序の決定を行う対象となる検索対象文書の母集団を限定する分類キー毎に前記検索対象の文書の母集団が対応付けられるとともに、前記母集団内の文書格納数値と、前記母集団内の文書の平均文書長値と、前記複数の検索対象の文書内のワード毎に当該ワードを含む前記母集団内の文書数である文書頻度値とが少なくとも算出され格納された索引情報を記憶する記憶手順と、
1以上の検索語と、前記分類キーとを含む検索条件を入力する検索条件入力手順と、
前記検索条件が入力されたとき、入力分類キーに対応付けされた前記母集団内の文書の文書格納数値及び平均文書長値と、入力分類キーに対応付けられた前記母集団内の文書のうち、入力検索語と一致するワードを含む当該母集団内の文書数である文書頻度値とを前記記憶手段の検索情報から取得し、取得された文書格納数値、平均文書長値、及び文書頻度値を含む適合度を算出するためのパラメータ値に基づいて当該母集団内の文書毎の適合度を算出することにより、文書を検索する検索手順と、
検索された文書に適合度を付して検索結果として出力する検索結果出力手順と、
を有することを特徴とする情報検索方法。
【請求項5】
請求項4記載の情報検索方法をコンピュータに実行させるための情報検索プログラム。
【請求項1】
複数の検索対象の文書を表示する順序を指定された検索条件に対する適合度に基づいて決定する情報検索装置であって、
1以上の検索語と、前記複数の検索対象の文書のうち前記順序の決定を行う対象となる検索対象文書の母集団を限定する分類キーとを含む検索条件を入力する検索条件入力手段と、
前記分類キー毎に前記検索対象の文書の母集団が対応付けられるとともに、前記母集団内の文書格納数値と、前記母集団内の文書の平均文書長値と、前記複数の検索対象の文書内のワード毎に当該ワードを含む前記母集団内の文書数である文書頻度値とが少なくとも算出され格納された索引情報を記憶した記憶手段と、
前記検索条件が入力されたとき、入力分類キーに対応付けされた前記母集団内の文書の文書格納数値及び平均文書長値と、入力分類キーに対応付けられた前記母集団内の文書のうち、入力検索語と一致するワードを含む当該母集団内の文書数である文書頻度値とを前記記憶手段の検索情報から取得し、取得された文書格納数値、平均文書長値、及び文書頻度値を含む適合度を算出するためのパラメータ値に基づいて当該母集団内の文書毎の適合度を算出することにより、文書を検索する検索手段と、
検索された文書に適合度を付して検索結果として出力する検索結果出力手段と、
を有することを特徴とする情報検索装置。
【請求項2】
前記記憶手段の索引情報は、前記分類キー毎に前記ワードが対応付けされて索引が作成され、
前記検索手段は、入力分類キー、入力検索語の順で前記索引を辿ることにより前記文書頻度値が取得されること、
を特徴とする請求項1記載の情報検索装置。
【請求項3】
前記記憶手段の索引情報は、前記ワード毎に前記分類キーが対応付けされて索引が作成され、
前記検索手段は、入力検索語、入力分類キーの順で前記索引を辿ることにより前記文書頻度値が取得されること、
を特徴とする請求項1記載の情報検索装置。
【請求項4】
複数の検索対象の文書を表示する順序を指定された検索条件に対する適合度に基づいて決定する情報検索装置における情報検索方法であって、
前記複数の検索対象の文書のうち前記順序の決定を行う対象となる検索対象文書の母集団を限定する分類キー毎に前記検索対象の文書の母集団が対応付けられるとともに、前記母集団内の文書格納数値と、前記母集団内の文書の平均文書長値と、前記複数の検索対象の文書内のワード毎に当該ワードを含む前記母集団内の文書数である文書頻度値とが少なくとも算出され格納された索引情報を記憶する記憶手順と、
1以上の検索語と、前記分類キーとを含む検索条件を入力する検索条件入力手順と、
前記検索条件が入力されたとき、入力分類キーに対応付けされた前記母集団内の文書の文書格納数値及び平均文書長値と、入力分類キーに対応付けられた前記母集団内の文書のうち、入力検索語と一致するワードを含む当該母集団内の文書数である文書頻度値とを前記記憶手段の検索情報から取得し、取得された文書格納数値、平均文書長値、及び文書頻度値を含む適合度を算出するためのパラメータ値に基づいて当該母集団内の文書毎の適合度を算出することにより、文書を検索する検索手順と、
検索された文書に適合度を付して検索結果として出力する検索結果出力手順と、
を有することを特徴とする情報検索方法。
【請求項5】
請求項4記載の情報検索方法をコンピュータに実行させるための情報検索プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2012−53605(P2012−53605A)
【公開日】平成24年3月15日(2012.3.15)
【国際特許分類】
【出願番号】特願2010−194819(P2010−194819)
【出願日】平成22年8月31日(2010.8.31)
【出願人】(000006747)株式会社リコー (37,907)
【Fターム(参考)】
【公開日】平成24年3月15日(2012.3.15)
【国際特許分類】
【出願日】平成22年8月31日(2010.8.31)
【出願人】(000006747)株式会社リコー (37,907)
【Fターム(参考)】
[ Back to top ]