説明

文書検索方法、文書検索装置および文書検索プログラム

【課題】階層構造化された文書セットの中から、適切な要素を短時間で検索すること。
【解決手段】取得部201は、XML文書を取得する。生成部202は、位置情報を含むノードリストを生成する。入力部203は、検索条件の入力を受け付ける。算出部204は、検索条件の合致度を示すスコアを算出する。特定部205は、位置情報を参照して、ノードが属する親ノードを特定する。加算部206は、ノードのスコアに基づく加算値を、特定部205によって特定された親ノードのスコアに加算する。選択部207は、加算部206による加算後のスコアに基づいて、ノードリストに示されたノードの中から、検索結果として出力するノードを選択する。出力部208は、選択部207によって選択されたノードを出力する。

【発明の詳細な説明】
【技術分野】
【0001】
この発明は、階層構造化された文書セットから、任意の検索条件に合致するノードを検索する文書検索方法、文書検索装置および文書検索プログラムに関する。
【背景技術】
【0002】
従来より、一連の文書を、章や節などの適切な単位の部分文書に分割し、階層構造化することによって、出版の多様性、情報検索の的確性、分割/結合の容易性など、多くのメリットを得ることができるものとされている。たとえば、階層構造化された文書の代表的なものとしては、XML文書が挙げられる。XML文書は、タグによって文書要素や文書テキストがマークアップされているため、部分文書の検索を容易におこなうことができるものとされている(たとえば、下記特許文献1参照。)。
【0003】
【特許文献1】特開平08−044766号公報
【発明の開示】
【発明が解決しようとする課題】
【0004】
しかしながら、上記特許文献1に記載の従来技術にあっては、検索条件に合致する最小単位の要素が断片的に複数検索されてしまうといった問題が生じていた。たとえば、検索条件に合致する複数の要素が、上位の要素によって包括されている場合、ユーザにとっては、この上位の要素が検索結果として検索されるほうが好ましい。
【0005】
この発明は、上述した従来技術による問題点を解消するため、階層構造化された文書セットの中から、適切な要素を短時間で検索することができる文書検索方法、文書検索装置および文書検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【0006】
上述した課題を解決し、目的を達成するため、この発明にかかる文書検索方法は、階層構造化された文書セットを取得する取得工程と、前記取得工程によって取得された文書セットから、当該文書セットに含まれたノードごとに当該ノードが属する親ノードの位置を示す位置情報を含む、ノードリストを生成する生成工程と、任意の検索条件の入力を受け付ける入力工程と、前記ノードリストに示されたノードごとに、前記検索条件の合致度を示すスコアを算出する算出工程と、前記ノードリストに示されたノードごとに、前記位置情報を参照して、前記ノードリストに示されているノードの中から、当該ノードが属する親ノードを特定する特定工程と、前記ノードリストに示されたノードごとに、当該ノードのスコアに基づく加算値を、前記特定工程によって特定された親ノードのスコアに加算する加算工程と、前記加算工程による加算後のスコアに基づいて、前記ノードリストに示されたノードの中から、検索結果として出力するノードを選択する選択工程と、前記選択工程によって選択されたノードを出力する出力工程と、を含んだことを特徴とする。
【0007】
この発明によれば、検索条件の合致度が高いノードの親ノード、または検索条件に合致するノードを多く含む親ノードを、検索条件の合致度が高いノードとして扱うことができる。
【0008】
また、上記に記載の発明において、前記生成工程は、前記ノードリストに示されたノードごとに、当該ノードのインデックスと当該ノードが属する親ノードのインデックスとの差分値を、前記位置情報として前記ノードリストに含めることを特徴とする。
【0009】
この発明によれば、少ない情報量で、親ノードの位置を表現できる。
【0010】
また、上記に記載の発明において、前記加算工程は、前記ノードリストに示された下位のノードから順に、前記ノードのスコアに基づく加算値を、前記親ノードのスコアに加算することを特徴とする。
【0011】
この発明によれば、それぞれのノードについての加算処理を1回で済ませることができる。
【0012】
また、上記に記載の発明において、前記算出工程は、TF−IDF法を用いて、前記ノードリストに示されたノードごとに、前記検索条件の合致度を示すスコアを算出することを特徴とする。
【0013】
この発明によれば、TF−IDF法を用いてスコアを算出することにより、単に検索条件に含まれるキーワードが多く出現するノードではなく、そのキーワードをノードの特徴的なものとするノードを、検索条件の合致度が高いノードとして扱うことができる。
【0014】
また、上記に記載の発明において、前記加算工程は、前記ノードリストに示されたノードごとに、当該ノードのスコアを、前記親ノードのスコアに加算することを特徴とする。
【0015】
この発明によれば、検索条件の合致度に応じたスコアを親ノードに加算することができる。
【0016】
また、上記に記載の発明において、前記加算工程は、前記ノードリストに示されたノードごとに、当該ノードのスコアと当該ノードの位置情報とに基づく加算値を、前記親ノードのスコアに加算することを特徴とする。
【0017】
この発明によれば、検索条件の合致度および親ノードとの距離を考慮したスコアを親ノードに加算することができる。
【0018】
また、上記に記載の発明において、前記加算工程は、前記ノードリストに示されたノードごとに、当該ノードのスコアと当該ノードの大きさとに基づく加算値を、前記親ノードのスコアに加算することを特徴とする。
【0019】
この発明によれば、検索条件の合致度およびノードの大きさを考慮したスコアを親ノードに加算することができる。
【0020】
また、上記に記載の発明において、前記加算工程は、前記ノードリストに示されたノードごとに、当該ノードのスコアと当該ノードの位置情報と当該ノードの大きさとに基づく加算値を、前記親ノードのスコアに加算することを特徴とする。
【0021】
この発明によれば、検索条件の合致度、親ノードとの距離、およびノードの大きさを考慮したスコアを親ノードに加算することができる。
【0022】
また、この発明にかかる文書検索装置は、階層構造化された文書セットを取得する取得手段と、前記取得手段によって取得された文書セットから、当該文書セットに含まれたノードごとに当該ノードが属する親ノードの位置を示す位置情報を含む、ノードリストを生成する生成手段と、任意の検索条件の入力を受け付ける入力手段と、前記ノードリストに示されたノードごとに、前記検索条件の合致度を示すスコアを算出する算出手段と、前記ノードリストに示されたノードごとに、前記位置情報を参照して、前記ノードリストに示されているノードの中から、当該ノードが属する親ノードを特定する特定手段と、前記ノードリストに示されたノードごとに、当該ノードのスコアに基づく加算値を、前記特定手段によって特定された親ノードのスコアに加算する加算手段と、前記加算手段による加算後のスコアに基づいて、前記ノードリストに示されたノードの中から、検索結果として出力するノードを選択する選択手段と、前記選択手段によって選択されたノードを出力する出力手段と、を備えたことを特徴とする。
【0023】
この発明によれば、検索条件の合致度が高いノードの親ノード、または検索条件に合致するノードを多く含む親ノードを、検索条件の合致度が高いノードとして扱うことができる。
【0024】
また、この発明にかかる文書検索プログラムは、階層構造化された文書セットを取得する取得工程と、前記取得工程によって取得された文書セットから、当該文書セットに含まれたノードごとに当該ノードが属する親ノードの位置を示す位置情報を含む、ノードリストを生成する生成工程と、任意の検索条件の入力を受け付ける入力工程と、前記ノードリストに示されたノードごとに、前記検索条件の合致度を示すスコアを算出する算出工程と、前記ノードリストに示されたノードごとに、前記位置情報を参照して、前記ノードリストに示されているノードの中から、当該ノードが属する親ノードを特定する特定工程と、前記ノードリストに示されたノードごとに、当該ノードのスコアに基づく加算値を、前記特定工程によって特定された親ノードのスコアに加算する加算工程と、前記加算工程による加算後のスコアに基づいて、前記ノードリストに示されたノードの中から、検索結果として出力するノードを選択する選択工程と、前記選択工程によって選択されたノードを出力する出力工程と、をコンピュータに実行させることを特徴とする。
【0025】
この発明によれば、検索条件の合致度が高いノードの親ノード、または検索条件に合致するノードを多く含む親ノードを、検索条件の合致度が高いノードとしてコンピュータに扱わせることができる。
【発明の効果】
【0026】
本発明にかかる文書検索方法、文書検索装置および文書検索プログラムによれば、階層構造化された文書セットの中から、適切な要素を短時間で検索することができるという効果を奏する。
【発明を実施するための最良の形態】
【0027】
以下に添付図面を参照して、この発明にかかる文書検索方法、文書検索装置および文書検索プログラムの好適な実施の形態を、階層構造化された文書セットの一例としてXML文書を用いて詳細に説明する。
【0028】
(文書検索装置100のハードウェア構成)
まず、この実施の形態にかかる文書検索装置のハードウェア構成について説明する。図1は、この実施の形態にかかる文書検索装置のハードウェア構成の一例を示すブロック図である。
【0029】
図1において、文書検索装置100は、CPU(Central Processing Unit)101と、ROM(Read Only Memory)102と、RAM(Random Access Memory)103と、HDD(Hard Disc Drive)104と、HD(Hard Disc)105と、FDD(Flexible Disc Drive)106と、FD(Flexible Disc)107と、CD−RW(Compact Disc ReWritable)ドライブ108と、CD−RW109と、ディスプレイ110と、キーボード111と、マウス112と、ネットワークI/F(インタフェース)113と、通信ケーブル114と、バス120とを備えて構成されている。
【0030】
CPU101は、文書検索装置100全体を制御する。ROM102は、各種制御プログラムなどを格納する。RAM103は、可変的なデータを書き換え自在に記憶し、CPU101のワークエリアとして機能する。HDD104は、CPU101の制御にしたがってHD105に対するデータのリード/ライトを制御する。HD105は、HDD104の制御にしたがって書き込まれたデータを記憶する。
【0031】
FDD106は、CPU101の制御にしたがってFD107に対するデータのリード/ライトを制御する。FD107は、着脱自在であり、FDD106の制御にしたがって書き込まれたデータを記憶する。CD−RWドライブ108は、CPU101の制御にしたがってCD−RW(または、CD−R、CD−ROM)109に対するデータのリード/ライトを制御する。CD−RW109は、着脱自在であり、CD−RWドライブ108の制御にしたがって書き込まれたデータを記憶する。
【0032】
ディスプレイ110は、カーソル、メニュー、ウィンドウ、あるいは文字や画像などの各種データを表示する。キーボード111は、文字、数値、各種指示などの入力のための複数のキーを備える。マウス112は、各種指示の選択や実行、処理対象の選択、マウスポインタの移動などを行う。ネットワークI/F113は、通信ケーブル114を介してLAN、WAN、インターネットなどのネットワークに接続され、当該ネットワークとCPU101とのインタフェースとして機能する。バス120は上記各部を接続する。
【0033】
(文書検索装置100の機能的構成)
つぎに、この実施の形態にかかる文書検索装置100の機能的構成について説明する。図2は、この実施の形態にかかる文書検索装置100の機能的構成を示すブロック図である。
【0034】
図2に示すように、文書検索装置100は、取得部201と、生成部202と、入力部203と、算出部204と、特定部205と、加算部206と、選択部207と、出力部208と、を備えて構成されている。
【0035】
取得部201は、XML文書を取得する。たとえば取得部201は、ユーザによって指定されたXML文書ファイルを読み取ることによってXML文書を取得する。この場合、XML文書ファイルは、文書検索装置100内部に記憶されているものに限らず、たとえば、文書検索装置100と接続された他の装置に記憶されているものであってもよい。また、取得部201は、複数のXML文書を取得してもよい。この場合、たとえば、所定の格納場所から、複数のXML文書を取得してもよい。また、ユーザによって指定された格納場所から、複数のXML文書を取得してもよい。取得部201は、具体的には、たとえば図1に示したネットワークI/F113によってその機能を実現する。
【0036】
生成部202は、取得部201によって取得されたXML文書から、当該文書セットに含まれたノードごとに当該ノードが属する親ノードの位置を示す位置情報を含む、ノードリストを生成する。ここでいうノードリストとは、木構造にモデル化されたXML文書に基づいてXML文書内に存在する全ての要素ノードをリスト化したものである。ノードリストでは、要素ノードごとに、インデックス、パスなどの情報を含む。要素ノードにテキストノードが属している場合は、そのテキストノードの、インデックス、テキストなどの情報が関連付けられる。
【0037】
生成部202は、ノードリストに示されたノードごとに、当該ノードのインデックスと当該ノードが属する親ノードとの相対位置を示す位置情報をノードリストに含めてもよい。たとえば、生成部202は、ノードリストに示されたノードごとに、当該ノードのインデックスと当該ノードが属する親ノードのインデックスとの差分値を、位置情報としてノードリストに含めてもよい。具体的に説明すると、インデックス「1006」が付与されたノードの親ノードのインデックスが「1002」である場合、生成部202は、インデックス「1006」が付与されたノードの位置情報を「4」とする。生成部202は、生成したノードリストを、メモリ上に一時的に記憶させる。
【0038】
生成部202は、XML文書に存在する全てのノードに関するノードリストを生成するだけでなく、所定の範囲内のノードに関するノードリストや、ユーザによって指定された範囲内のノードに関するノードリストを生成するようにしてもよい。また、生成部202は、ノードリストに示されたノードごとに、当該ノードのインデックスと当該ノードが属する親ノードの絶対位置を示す位置情報(たとえば、親ノードのインデックス)をノードリストに含めてもよい。なお、ノードリストの具体的な生成手順については、図4を用いて後述する。生成部202は、具体的には、たとえば図1に示したROM102、RAM103、HD105、FD107に記憶されたプログラムをCPU101が実行することによってその機能を実現する。
【0039】
入力部203は、任意の検索条件の入力を受け付ける。ここで、検索条件とは、任意の自然文(検索クエリ文)、任意のデータなどである。たとえば、検索条件は「J社 I太郎」や「(J社 I太郎)」のように入力され、前者は、「J社」および「I太郎」の両方を含む、を意味し、後者は、「J社」または「I太郎」のいずれかを含む、を意味する。ここで、検索条件は、ユーザが文書検索装置100に直接入力したものに限らず、たとえば、文書検索装置100と接続された他の装置から送信されたものであってもよい。入力部203は、具体的には、たとえば図1に示したキーボード111、マウス112、ネットワークI/F113によってその機能を実現する。
【0040】
算出部204は、ノードリストに示されているノードごとに、入力部203によって入力された検索条件の合致度を示すスコアを算出する。たとえば、スコア(TF−IDF)は、以下算出式(1)により求めることができる。
【0041】
TFIDF=TF×log(N/DF)・・・(1)
【0042】
上記算出式(1)において、TFは、テキストノード内における検索文字列の出現数を示す。また、Nは、全テキストノード数を示す。そして、DFは、検索文字列を含むテキストノード数を示す。
【0043】
なお、本実施の形態においては、TF−IDF法を用いてスコアを算出しているが、これに限らず、他の方法を用いて、スコアを算出するようにしてもよい。算出部204は、具体的には、たとえば図1に示したROM102、RAM103、HD105、FD107に記憶されたプログラムをCPU101が実行することによってその機能を実現する。
【0044】
特定部205は、ノードリストに示されたノードごとに、位置情報を参照して、ノードリストに示されているノードの中から、当該ノードが属する親ノードを特定する。たとえば、ノードのインデックスと親ノードのインデックスとの差分値が位置情報とされた場合、ノードのインデックスと位置情報とから、親ノードのインデックスを特定する。たとえば、インデックス「1006」が付与されたノードの位置情報が「4」である場合、特定部205は、インデックス「1002」が付与されたノードを、インデックス「1006」が付与されたノードの親ノードとして特定する。特定部205は、具体的には、たとえば図1に示したROM102、RAM103、HD105、FD107に記憶されたプログラムをCPU101が実行することによってその機能を実現する。
【0045】
加算部206は、ノードリストに示されたノードごとに、当該ノードのスコアに基づく加算値を、特定部205によって特定された親ノードのスコアに加算する。加算部206は、ノードリストに示された下位のノードから順に、すなわち、インデックス値の逆順に、ノードのスコアに基づく加算値を、親ノードのスコアに加算する。特に、加算部206は、ノードリストの最後尾(XML構造の最右端)から、順に親ノードに向かってスコアまたは加算値を加算することが好ましい。この処理はワンパスで走査が可能であり、メモリ領域に収まるサイズならば、非常に高速に処理できる。
【0046】
たとえば、パス「A/B/D」によって特定されるノードのスコアが「5」であり、このノードが属する親ノード「A/B」のスコアが「5」であった場合、加算部206による加算処理によって、ノード「A/B」のスコアは「10」となる。
【0047】
なお、加算部206は、ノードリストに示されたノードごとに、当該ノードのスコアと当該ノードの位置情報とを用いて加算値を算出し、算出した加算値を特定部205によって特定された親ノードのスコアに加算してもよい。たとえば、加算値(ADD)は、以下算出式(2)により求めるようにしてもよい。
【0048】
ADD=SCORE/log(OFFSET+1.1)・・・(2)
【0049】
上記算出式(2)において、SCOREは、ノードのスコアを示す。また、OFFSETは、位置情報を示す。上記算出式(2)によって算出された値を加算値とすることにより、親ノードとの距離が離れたノードほど、親ノードとの関連度が低いノードとして扱い、スコアを減じることができる。
【0050】
なお、加算部206は、上記以外の算出式を用いて加算値を算出してもよい。たとえば、加算部206は、ノードのスコアとノードの大きさとを用いて加算値を算出し、算出した加算値を特定部205によって特定された親ノードのスコアに加算してもよい。また、加算部206は、ノードのスコアとノードの大きさとノードの位置情報とを用いて加算値を算出し、算出した加算値を特定部205によって特定された親ノードのスコアに加算してもよい。
【0051】
加算部206は、具体的には、たとえば図1に示したROM102、RAM103、HD105、FD107に記憶されたプログラムをCPU101が実行することによってその機能を実現する。
【0052】
選択部207は、加算部206による加算後のスコアに基づいて、ノードリストに示されたノードの中から、検索結果として出力するノードを選択する。たとえば、選択部207は、加算部206による加算後のスコアに基づいて、ノードリストに示されたノードを検索条件の合致度順にソートする。そして、選択部207は、スコアの高いノードから順に、ソート後のノードリストの中から、合致度の高いノードを所定数選択する。
【0053】
なお、選択部207によって選択されるノードの数は、あらかじめ設定されていてもよく、ユーザによって指定されたものであってもよい。選択部207は、具体的には、たとえば図1に示したROM102、RAM103、HD105、FD107に記憶されたプログラムをCPU101が実行することによってその機能を実現する。
【0054】
出力部208は、選択部207によって選択されたノードを出力する。たとえば、出力部208は、選択部207によって選択されたノードを、検索条件の合致度が高い順に表示する。なお、出力部208は、選択部207によって選択されたノードを表示するだけでなく、たとえば、ファイルに出力したり、文書検索装置100と接続された他の装置へ送信してもよい。たとえば、検索条件が他の装置から送信された場合、検索条件の送信元の装置へ送信してもよい。出力部208は、具体的には、たとえば図1に示したディスプレイ110、ネットワークI/F113によってその機能を実現する。
【0055】
(XML文書の一例)
つぎに、この発明の実施の形態にかかる文書検索装置100に用いられるXML文書の一例について説明する。図3は、この発明の実施の形態にかかる文書検索装置100に用いられるXML文書の一例を示す説明図である。
【0056】
図3は、木構造にモデル化されたXML文書「c:¥documents¥0123.xml」を示したものである。図3において、「1001」〜「1013」は要素ノードを示し、各数字はそのインデックスを示す。また、「A」〜「E」はテキストノードを示し、各英字はそのインデックスを示す。
【0057】
図3において、たとえば、インデックス「1004」が付与された要素ノードには、インデックス「A」が付与されたテキストノードが属している。また、インデックス「A」が付与されたテキストノードは、テキスト「XML,scheme」を持つ。たとえば、このテキストノードをタグを用いて示した場合、「<article><body><sec><p1>XML,scheme</p1></sec></body></article>」と示すことができる。
【0058】
(ノードリストの生成手順)
つぎに、生成部202によるノードリストの生成手順について説明する。図4は、生成部202によるノードリストの生成手順の一例を示すフローチャートである。
【0059】
まず、木構造にモデル化されたXML文書の中から、ルートの要素ノードを選択する(ステップS401)。たとえば、図3に示したXML文書の場合、インデックス「1001」が付与された要素ノードが選択される。
【0060】
つぎに、ステップS401で選択された要素ノードをノードリストに追加する(ステップS402)。ここで、ノードリストに追加される情報は、要素ノードのインデックスやパスなどである。たとえば、図3に示したXML文書におけるインデックス「1001」が付与された要素ノードの場合は、インデックス「1001」やパス「/article」などがノードリストに追加される。
【0061】
つぎに、位置情報をノードリストに追加する(ステップS403)。たとえば、位置情報は、選択されたノードのインデックスから親ノードのインデックスを減算することによって求めることができる。たとえば、図3に示したXML文書におけるインデックス「1001」が付与された要素ノードの場合は、親ノードが存在しないことから、位置情報として「0」が求められる。また、図3に示したXML文書におけるインデックス「1006」が付与された要素ノードの場合は、親ノードのインデックスが「1002」であることから、位置情報として「4」が求められる。
【0062】
つぎに、選択された要素ノードにテキストノードが属しているか否かを判断する(ステップS404)。たとえば、図3に示したXML文書におけるインデックス「1001」が付与された要素ノードの場合は、テキストノードが属していないと判断され、インデックス「1004」が付与された要素ノードの場合は、テキストノードが属していると判断される。
【0063】
ステップS404において、テキストノードが属していると判断した場合(ステップS404:Yes)は、選択された要素ノードと、この要素ノードに属しているテキストノードとの関連付けをおこなって(ステップS405)、ステップS406へ進む。
【0064】
ここで、要素ノードに関連付けられる情報は、テキストノードのインデックスやテキストなどである。たとえば、図3に示したXML文書におけるインデックス「1004」が付与された要素ノードには、テキストノードのインデックス「A」やテキスト「XML,scheme」などが関連付けられる。ステップS404において、テキストノードが属していないと判断した場合(ステップS404:No)は、ステップS405を飛ばして、ステップS406へ進む。
【0065】
つぎに、XML文書に含まれる全ての要素ノードが選択されたか否かを判断する(ステップS406)。ステップS406において、全ての要素ノードが選択されたと判断した場合(ステップS406:Yes)は、一連の処理を終了する。一方、ステップS406において、全ての要素ノードが選択されていないと判断した場合(ステップS406:No)は、XML文書の中から、次の要素ノードを選択する(ステップS407)。このとき、より上位ノードを優先する。たとえば、図3に示したXML文書において、要素ノードが選択される順番は、インデックス値の順番とおりとなる。
【0066】
そして、ステップS402に戻り、ステップS406で全てのノードが選択されたと判断されるまで、ステップS402〜ステップS407を繰り返しおこなう。これにより、XML文書に含まれる全ての要素ノードを、上位のノードから順に、ノードリストに追加することができる。また、XML文書に含まれる全てのテキストノードを、それぞれ、ノードリストに示された要素ノードのいずれかと関連付けることができる。また、XML文書に含まれる全ての要素ノードについての親ノードの位置情報を、ノードリストに追加することができる。
【0067】
(ノードリストの一例)
つぎに、ノードリストの一例について説明する。図5は、ノードリストの一例を示す説明図である。
【0068】
図5に示すノードリスト500は、図4を用いて上述した手順によって、図3に示したXML文書から生成されたノードリストであり、列「index1」,「path」,「index2」,「text」,「parent」によって構成されている。
【0069】
このうち、列「index1」には、要素ノードのインデックスが設定される。また、列「path」には、要素ノードのパスが設定される。そして、列「index2」には、要素ノードと関連付けられているテキストノードのインデックスが設定される。さらに、列「text」には、要素ノードと関連付けられているテキストノードのテキストが設定される。また、列「parent」には、要素ノードが属する親ノードの位置情報が設定される。
【0070】
たとえば、図5に示すノードリスト500から、インデックス「1004」が付与されたパス「/article/body/sec/p1」によって示される要素ノードには、インデックス「A」が付与され、かつテキスト「XML,scheme」を含むテキストノードが関連付けられていると判断することができる。また、インデックス「1006」が付与されたパス「/article/body/footer」によって示される要素ノードについての親ノードの位置情報は、「4」であると判断することができる。
【0071】
このように、ノードリスト500は、要素ノードのインデックス順でソートされているため、元のXML構造を再構成でき、親ノードの情報に容易にアクセスすることが可能である。また、ノードリスト500を参照することにより、各ノードの持つ情報を、親子関係や祖先子孫関係、兄弟関係などを考慮しながら高速に処理を行うことができる。
【0072】
(文書検索装置100による文書検索処理の手順)
つぎに、この発明の実施の形態にかかる文書検索装置100による文書検索処理の手順について説明する。図6は、この発明の実施の形態にかかる文書検索装置100による文書検索処理の手順の一例を示すフローチャートである。
【0073】
まず、取得部201によって、XML文書を取得して(ステップS601)、生成部202によって、ステップS601で取得されたXML文書からノードリスト(ノード数N)を生成する(ステップS602)。ノードリストの具体的な生成手順については図4を用いて上述したとおりである。
【0074】
つぎに、入力部203によって、検索条件の入力を受け付けて(ステップS603)、算出部204によって、ステップS602で生成されたノードリストに示されている全てのノードに対し、ステップS603で入力された検索条件に基づいた、検索条件の合致度を示すスコアを算出する(ステップS604)。
【0075】
続いて、特定部205によって、ステップS602で生成されたノードリストに示されている上位からi番目(i=N...1)のノードを選択して(ステップS605)、ステップS605で選択されたノードについて、親ノードを特定する(ステップS606)。
【0076】
そして、加算部206によって、ステップS605で選択されたノードのスコアを、ステップS606で特定された親ノードのスコアに加算して(ステップS607)、ステップS608へ進む。
【0077】
続いて、ステップS602で生成されたノードリストに示されているノードが全て選択されたか否かを判断する(ステップS608)。ステップS608において、ノードが全て選択されていないと判断した場合(ステップS608:No)は、ステップS608においてノードが全て選択されたと判断されるまで、ステップS605〜ステップS608を繰り返しおこなう。
【0078】
一方、ステップS608において、ノードが全て選択されたと判断した場合(ステップS608:Yes)は、選択部207によって、ステップS607による加算後のスコアに基づいて、ノードリストに示されたノードを検索条件の合致度順にソートして(ステップS609)、ソートされたノードの中から、合致度の高いノードを所定のノード数選択する(ステップS610)。
【0079】
そして、出力部208によって、ステップS610で選択されたノードを出力して(ステップS611)、一連の処理を終了する。
【0080】
(算出部204によって算出されたスコアの一例)
つぎに、算出部204によって算出されたスコアの一例について説明する。図7は、算出部204によって算出されたスコアの一例を示す説明図である。
【0081】
図7は、図5に示したノードリスト500と、算出部204によって算出された各要素ノードのスコアを示すスコアリスト700との関連付けを示したものである。図7に示すスコアリスト700において、列「score1」には、算出部204によって算出されたスコアが設定されている。このときの、算出処理に用いられた検索文字列は「XML,tag,scheme」である。
【0082】
たとえば、ノードリスト500およびスコアリスト700から、インデックス「1004」が付与されたパス「/article/body/sec/p1」によって示される要素ノードには、算出部204によって算出されたスコア「38」が関連付けられていると判断することができる。ここで、このスコア「38」は以下のTF−IDF算出式(3)によって算出されたものである。
【0083】
38(TFIDF:スコア)=1(TF:テキストノード内における検索文字列「XML」の出現数)×20(IDF:log(全テキストノード数/検索文字列「XML」を含むテキストノード数))+1(TF:テキストノード内における検索文字列「scheme」の出現数)×18(IDF:log(全テキストノード数/検索文字列「scheme」を含むテキストノード数))・・・(3)
【0084】
また、ノードリスト500、スコアリスト700から、インデックス「1005」が付与されたパス「/article/body/sec/p2」によって示される要素ノードには、算出部204によって算出されたスコア「80」が関連付けられていると判断することができる。ここで、このスコア「80」は以下のTF−IDF算出式(4)によって算出されたものである。
【0085】
80(TFIDF:スコア)=2(TF:テキストノード内における検索文字列「tag」の出現数)×40(IDF:log(全テキストノード数/検索文字列「tag」を含むテキストノード数))・・・(4)
【0086】
(加算部206によって加算されたスコアの一例)
つぎに、加算部206によって加算されたスコアの一例について説明する。図8は、加算部206によって加算されたスコアの一例を示す説明図である。
【0087】
図8は、図5に示したノードリスト500と、図7に示したスコアリスト700と、加算部206による加算後のスコアを示すスコアリスト800と、の関連付けを示したものである。図8に示すスコアリスト800において、列「score2」には、加算部206によって加算されたスコアが設定されている。
【0088】
たとえば、スコアリスト800から、インデックス「1011」が付与されたパス「/article/body/sec/title/name」によって示される要素ノードには、加算部206によって加算されたスコア「66」が関連付けられていると判断することができる。ここで、このスコア「66」は、この要素ノードに属する、インデックス「1012」が付与された要素ノードのスコア「22」と、インデックス「1013」が付与された要素ノードのスコア「44」とが加算されたものである。
【0089】
(加算部206によって加算されたスコアの他の一例)
つぎに、加算部206によって加算されたスコアの他の一例について説明する。図9は、加算部206によって加算されたスコアの他の一例を示す説明図である。
【0090】
図9は、図5に示したノードリスト500と、図7に示したスコアリスト700と、加算部206による加算後のスコアを示すスコアリスト900と、の関連付けを示したものである。図9に示すスコアリスト900において、列「score2」には、加算部206によって加算されたスコアが設定されている。
【0091】
たとえば、スコアリスト900から、インデックス「1011」が付与されたパス「/article/body/sec/title/name」によって示される要素ノードには、加算部204によって加算されたスコア「44」が関連付けられていると判断することができる。ここで、このスコア「44」は、この要素ノードに属する、インデックス「1012」が付与された要素ノードのスコア「22」から図2を用いて説明した算出式(2)により算出された加算値「20」と、インデックス「1013」が付与された要素ノードのスコア「44」から上記算出式(2)により差出された加算値「24」とが加算されたものである。
【0092】
(出力部208によって出力された検索結果の一例)
つぎに、出力部208によって出力された検索結果の一例について説明する。図10は、出力部208によって出力された検索結果の一例を示す説明図である。
【0093】
図10は、図3に示したXML文書に対して、図6を用いて上述した手順による文書検索処理がおこなわれた結果、出力部208によって出力された検索結果を示すものである。図10に示すように、文書検索処理をおこなうにあたり、検索対象文書「c:¥documents¥0123.xml」、検索条件「XML,tag,scheme」、検索数「3(件)」がユーザによって指定されている。
【0094】
そして、「検索」ボタンが押下されたことにより、検索対象文書「c:¥documents¥0123.xml」に対する文書検索処理がおこなわれ、その結果として、検索対象文書「c:¥documents¥0123.xml」の中から選択された、検索条件の合致度が高い上位3件のノードが検索結果として出力されている。
【0095】
以上説明したように、本実施の形態にかかる文書検索装置100によれば、ノードリストに示されたノードごとに、当該ノードのスコアに基づく加算値を、親ノードのスコアに加算し、加算後のスコアに基づいて、ノードリストに示されたノードの中から、検索結果として出力するノードを選択する構成とした。このため、階層構造化された文書セットの中から、適切な要素を検索することができる。
【0096】
また、本実施の形態にかかる文書検索装置100によれば、ノードリストに示された下位のノードから順に、ノードのスコアに基づく加算値を、親ノードのスコアに加算する構成とした。特に、位置情報を参照して、親ノードを特定する構成とした。このため、階層構造化された文書セットの中から、適切な要素を短時間で検索することができる。
【0097】
なお、この発明にかかる文書検索方法、文書検索装置および文書検索プログラムは、階層構造化された文書セットであれば、XML文書以外の文書に対する文書検索にも適用することができる。また、ファイル化された文書に限らず、たとえば、データベース化された文書に対する文書検索にも適用することができる。さらに、単独のファイルにファイル化された文書や単独のデータベースにデータベース化された文書に限らず、複数のファイルにファイル化された文書や、複数のデータベースにデータベース化された文書に対する文書検索にも適用することができる。
【0098】
なお、本実施の形態で説明した文書検索方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、CD−ROM、MO、DVD等のコンピュータで読み取り可能な記憶媒体に記録され、コンピュータによって記憶媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な伝送媒体であってもよい。
【産業上の利用可能性】
【0099】
以上のように、本発明にかかる文書検索方法、文書検索装置および文書検索プログラムは、階層構造化された文書セットから、任意の検索条件に合致するノードを検索するパーソナル・コンピュータ、ドキュメントサーバ、文書検索ソフトウェアなどへの利用に適している。
【図面の簡単な説明】
【0100】
【図1】この実施の形態にかかる文書検索装置のハードウェア構成の一例を示すブロック図である。
【図2】この実施の形態にかかる文書検索装置の機能的構成を示すブロック図である。
【図3】この発明の実施の形態にかかる文書検索装置に用いられるXML文書の一例を示す説明図である。
【図4】生成部によるノードリストの生成手順の一例を示すフローチャートである。
【図5】ノードリストの一例を示す説明図である。
【図6】この発明の実施の形態にかかる文書検索装置による文書検索処理の手順の一例を示すフローチャートである。
【図7】算出部によって算出されたスコアの一例を示す説明図である。
【図8】加算部によって加算されたスコアの一例を示す説明図である。
【図9】加算部によって加算されたスコアの他の一例を示す説明図である。
【図10】出力部によって出力された検索結果の一例を示す説明図である。
【符号の説明】
【0101】
100 文書検索装置
101 CPU
102 ROM
103 RAM
104 HDD
105 HD
106 FDD
107 FD
108 CD−RWドライブ
109 CD−RW
110 ディスプレイ
111 キーボード
112 マウス
113 ネットワークI/F
114 通信ケーブル
120 バス
201 取得部
202 生成部
203 入力部
204 算出部
205 特定部
206 加算部
207 選択部
208 出力部
500 ノードリスト
700 スコアリスト
800 スコアリスト
900 スコアリスト

【特許請求の範囲】
【請求項1】
階層構造化された文書セットを取得する取得工程と、
前記取得工程によって取得された文書セットから、当該文書セットに含まれたノードごとに当該ノードが属する親ノードの位置を示す位置情報を含む、ノードリストを生成する生成工程と、
任意の検索条件の入力を受け付ける入力工程と、
前記ノードリストに示されたノードごとに、前記検索条件の合致度を示すスコアを算出する算出工程と、
前記ノードリストに示されたノードごとに、前記位置情報を参照して、前記ノードリストに示されているノードの中から、当該ノードが属する親ノードを特定する特定工程と、
前記ノードリストに示されたノードごとに、当該ノードのスコアに基づく加算値を、前記特定工程によって特定された親ノードのスコアに加算する加算工程と、
前記加算工程による加算後のスコアに基づいて、前記ノードリストに示されたノードの中から、検索結果として出力するノードを選択する選択工程と、
前記選択工程によって選択されたノードを出力する出力工程と、
を含んだことを特徴とする文書検索方法。
【請求項2】
前記生成工程は、
前記ノードリストに示されたノードごとに、当該ノードのインデックスと当該ノードが属する親ノードのインデックスとの差分値を、前記位置情報として前記ノードリストに含めることを特徴とする請求項1に記載の文書検索方法。
【請求項3】
前記加算工程は、
前記ノードリストに示された下位のノードから順に、前記ノードのスコアに基づく加算値を、前記親ノードのスコアに加算することを特徴とする請求項1または2に記載の文書検索方法。
【請求項4】
前記算出工程は、TF−IDF法を用いて、前記ノードリストに示されたノードごとに、前記検索条件の合致度を示すスコアを算出することを特徴とする請求項1〜3のいずれか一つに記載の文書検索方法。
【請求項5】
前記加算工程は、前記ノードリストに示されたノードごとに、当該ノードのスコアを、前記親ノードのスコアに加算することを特徴とする請求項1〜4のいずれか一つに記載の文書検索方法。
【請求項6】
前記加算工程は、前記ノードリストに示されたノードごとに、当該ノードのスコアと当該ノードの位置情報とに基づく加算値を、前記親ノードのスコアに加算することを特徴とする請求項1〜4のいずれか一つに記載の文書検索方法。
【請求項7】
前記加算工程は、前記ノードリストに示されたノードごとに、当該ノードのスコアと当該ノードの大きさとに基づく加算値を、前記親ノードのスコアに加算することを特徴とする請求項1〜4のいずれか一つに記載の文書検索方法。
【請求項8】
前記加算工程は、前記ノードリストに示されたノードごとに、当該ノードのスコアと当該ノードの位置情報と当該ノードの大きさとに基づく加算値を、前記親ノードのスコアに加算することを特徴とする請求項1〜4のいずれか一つに記載の文書検索方法。
【請求項9】
階層構造化された文書セットを取得する取得手段と、
前記取得手段によって取得された文書セットから、当該文書セットに含まれたノードごとに当該ノードが属する親ノードの位置を示す位置情報を含む、ノードリストを生成する生成手段と、
任意の検索条件の入力を受け付ける入力手段と、
前記ノードリストに示されたノードごとに、前記検索条件の合致度を示すスコアを算出する算出手段と、
前記ノードリストに示されたノードごとに、前記位置情報を参照して、前記ノードリストに示されているノードの中から、当該ノードが属する親ノードを特定する特定手段と、
前記ノードリストに示されたノードごとに、当該ノードのスコアに基づく加算値を、前記特定手段によって特定された親ノードのスコアに加算する加算手段と、
前記加算手段による加算後のスコアに基づいて、前記ノードリストに示されたノードの中から、検索結果として出力するノードを選択する選択手段と、
前記選択手段によって選択されたノードを出力する出力手段と、
を備えたことを特徴とする文書検索装置。
【請求項10】
階層構造化された文書セットを取得する取得工程と、
前記取得工程によって取得された文書セットから、当該文書セットに含まれたノードごとに当該ノードが属する親ノードの位置を示す位置情報を含む、ノードリストを生成する生成工程と、
任意の検索条件の入力を受け付ける入力工程と、
前記ノードリストに示されたノードごとに、前記検索条件の合致度を示すスコアを算出する算出工程と、
前記ノードリストに示されたノードごとに、前記位置情報を参照して、前記ノードリストに示されているノードの中から、当該ノードが属する親ノードを特定する特定工程と、
前記ノードリストに示されたノードごとに、当該ノードのスコアに基づく加算値を、前記特定工程によって特定された親ノードのスコアに加算する加算工程と、
前記加算工程による加算後のスコアに基づいて、前記ノードリストに示されたノードの中から、検索結果として出力するノードを選択する選択工程と、
前記選択工程によって選択されたノードを出力する出力工程と、
をコンピュータに実行させることを特徴とする文書検索プログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate


【公開番号】特開2009−129013(P2009−129013A)
【公開日】平成21年6月11日(2009.6.11)
【国際特許分類】
【出願番号】特願2007−300750(P2007−300750)
【出願日】平成19年11月20日(2007.11.20)
【出願人】(390024350)株式会社ジャストシステム (123)
【Fターム(参考)】