文書検索装置、文書検索方法および文書検索プログラム
【課題】不完全な経路式に基づいて構造化文書ファイル中から所望のデータを効率的に検索する。
【解決手段】構造化文書ファイルから所望のデータを検索するための文書検索装置に関する。この装置は、構造化文書ファイルにおいて階層的に上下関係にあるタグセットと、経路式の一部にそのタグセットを含む１以上の位置とを対応づけたインデックス情報を保持する。この装置は、部分経路式の入力を受け付けると、インデックス情報を参照して、部分経路式に含まれるタグセットが経路式の一部としてあらわれる位置を検索対象位置の候補位置として特定する。
【解決手段】構造化文書ファイルから所望のデータを検索するための文書検索装置に関する。この装置は、構造化文書ファイルにおいて階層的に上下関係にあるタグセットと、経路式の一部にそのタグセットを含む１以上の位置とを対応づけたインデックス情報を保持する。この装置は、部分経路式の入力を受け付けると、インデックス情報を参照して、部分経路式に含まれるタグセットが経路式の一部としてあらわれる位置を検索対象位置の候補位置として特定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書処理技術に関し、特に、構造化文書ファイルを対象とした情報検索技術、に関する。
【背景技術】
【０００２】
コンピュータの普及とネットワーク技術の進展にともない、ネットワークを介した電子情報の交換が盛んになっている。これにより、従来においては紙ベースで行われていた事務処理の多くが、ネットワークベースの処理に置き換えられつつある。デジタル化とネットワーク技術の進展は、情報取得コストを急激に低下させている。このような状況において、大量の文書ファイルの中から所望のデータを検索する技術の重要性が高まっている。
【特許文献１】特開２００６−０４８５３６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ところで、近年では、多くの文書ファイルが、ＨＴＭＬ（Hyper Text Markup Language）やＸＨＴＭＬ（eXtensible HyperText Markup Language）、ＸＭＬ（eXtensible Markup Language）などによる構造化文書ファイルとして作成されるようになってきている。構造化文書ファイルはタグによって階層化されるため、文書中のデータをタグのパス表記によって指定できる。このように、構造化文書ファイルには、データの位置を特定しやすいという優れた特性がある。中でも、ＸＭＬは、ネットワークを介して他者とデータを共有するのに適した形式として注目されている。ＸＭＬ文書であれば、ＸＰａｔｈ（XML Path Language）に基づく構文であるＸＰａｔｈ式によりデータを特定できる。
【０００４】
ＸＰａｔｈは、省略記号にも対応できる表記法となっている。たとえば、「/提案//集約処理」というＸＰａｔｈ式は、「＜提案＞タグの下位の階層に＜集約処理＞タグが出現する全てのパス」という条件を意味する。以下、このようなタグの経路に関する条件のことを「経路条件」とよぶことにする。また、ＸＰａｔｈ式のように、タグの階層構造に基づいてタグのパスを示す構文のことを「経路式」とよぶことにする。上記経路条件に対しては、「/提案/集約処理」、「/提案/内容/集約処理」、「/提案/内容/基本処理/集約処理」として指定されるいずれの経路式も適合する。
一方「/提案/*/集約処理」というＸＰａｔｈ式は、「＜提案＞タグから２階層下位の階層に＜集約処理＞タグが出現する全てのパス」という経路条件を意味する。上記した３つの経路式のうちでは「/提案/内容/集約処理」だけがこの経路条件に適合する。
【０００５】
ユーザが省略記号のないＸＰａｔｈ式を指定できれば、構造化文書ファイルから所望のデータを取り出すことができる。しかし、常に正確に経路式がわかるとは限らない。たとえば、検索対象となるデータが＜提案＞タグの下の＜集約処理＞タグにあることがわかっていても、＜提案＞タグと＜集約処理＞タグの間に、どのようなタグが何階層あるか、そもそも、どの文書に求めるデータがあるかわからないことがある。
上記したような省略記号を含む不完全な経路式が入力されたとき、その経路式によって示される経路条件に適合するデータを検索できれば便利である。以下、省略記号を含むなどの理由により、検索対象となるデータの位置を一意に特定するには不充分な経路式のことを「部分経路式」とよび、省略記号を含まない経路式のことを「完全経路式」とよぶ。
【０００６】
部分経路式に基づくデータ検索方法として、構造化文書ファイルのタグ構造を解析し、タグの経路情報をメモリに展開した上で、経路条件に適合する位置のデータを検出するという方法が一般的である。しかし、このような方法は、メモリの使用量が大きく、処理時間も長くなるという問題点がある。特に、多数の構造化文書ファイルや、タグの階層構造が複雑な構造化文書ファイルの中から所望のデータを探す場合には、このような問題点が顕在化しやすい。
【０００７】
本発明はこうした状況に鑑みてなされたものであり、その目的は、不完全な経路式に基づいて構造化文書ファイル中から所望のデータを効率的に検索するための技術、を提供することある。
【課題を解決するための手段】
【０００８】
本発明のある態様は、構造化文書ファイルから所望のデータを検索するための文書検索装置に関する。
この装置は、構造化文書ファイルにおいて階層的に上下関係にあるタグセットと、経路式の一部にそのタグセットを含む１以上の位置とを対応づけたインデックス情報を保持する。この装置は、部分経路式の入力を受け付けると、インデックス情報を参照して、部分経路式に含まれるタグセットが経路式の一部としてあらわれる位置を検索対象位置の候補位置として特定する。
【０００９】
インデックス情報としてタグセットごとの位置を登録しておくことにより、検索実行時に文書ファイルにアクセスしてタグの階層構造を精査しなくても、検索対象となるデータを特定できる。このため、不完全な部分経路式が入力されたときにも、検索対象となるデータを効率的に検出できる。
【００１０】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、システム、プログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１１】
本発明によれば、不完全な経路式に基づいて構造化文書ファイル中から所望のデータを効率的に検索することができる。
【発明を実施するための最良の形態】
【００１２】
図１は、文書検索装置１００による処理の概要を説明するための模式図である。
ユーザが文書検索装置１００に対して経路式を入力すると、文書検索装置１００は経路式に適合するデータを文書データベース２００から検索する。文書データベース２００の文書ファイルは、ＸＭＬ文書やＸＨＴＭＬ文書のようにタグによって構造化された構造化文書ファイルである。本実施例においては、検索対象となる文書ファイルはＸＭＬファイルであるとして説明する。
【００１３】
文書検索装置１００のインデックス保持部１３０は、各文書ファイルを検索するためのインデックス情報を保持する。インデックス情報は、完全経路インデックス２１４と部分経路インデックス２３０の２種類があるが、それぞれについては図３から図５に関連して後に詳述する。文書検索装置１００は、入力された経路式とインデックス情報に基づいて、文書データベース２００から検索対象となるデータがどの文書のどの位置にあるかを検索する。文書検索装置１００は、検出された文書ファイルの文書ＩＤと、その文書ファイルにおける検索対象データとを画面表示させる。こうして、文書検索装置１００のユーザは、任意の経路式に対して、検索対象データ、または、検索対象データの候補を文書データベース２００から探し出す。
【００１４】
図２は、本実施例におけるＸＭＬ文書２１０を示す図である。
同図に示すＸＭＬ文書２１０を対象として本実施例を説明する。文書データベース２００の各文書ファイルには文書ＩＤが付与される。同図に示すＸＭＬ文書２１０の文書ＩＤは「１」であるとする。文書ＩＤとは、文書データベース２００において文書ファイルを一意に識別するためのＩＤである。このＸＭＬ文書２１０は、アイディア提案書に関するＸＭＬ文書であり、＜提案＞や＜発案者＞など複数のタグを含む。文書位置欄２１２は、ＸＭＬ文書２１０に含まれるさまざまなデータの位置を示す。たとえば、＜提案＞タグのこの文書における文書位置は「１」であり、＜／集約処理＞タグの文書位置は「１６」である。また、＜発案者＞タグの内容データである文字列”竹内真教”の文書位置は「３」である。文書位置は、タグ、属性、コメント、タグの内容となるデータごとに割り当てられ、文書ごとに一意の値となる。
以下においては説明を簡単にするため、タグに対する文書位置を中心として説明する。
【００１５】
図３は、完全経路インデックス２１４のデータ構造図である。
完全経路インデックス２１４は、インデックス保持部１３０に格納される。経路欄２１６は、文書データベース２００に含まれる経路式の一覧である。経路欄２１６には図２に示した文書ＩＤ＝１の文書に含まれる経路式だけでなく、その他の文書に含まれる経路式も含まれる。経路ＩＤ欄２１８は、経路欄２１６に示す経路の経路ＩＤを示す。経路ＩＤは、経路式を示す文字列を所定規則により変換した数値列である。ハッシュ関数により変換してもよいし、所定のテーブルによって変換してもよいが、いずれにしても、各経路式が実用上差し支えない程度に一意に識別される値であればよい。
【００１６】
同図において、経路式「/提案」のＸＭＬ文書２１０における経路ＩＤ＝１となっている。経路式「/提案/発案者」の場合、経路ＩＤ＝２である。同様に、「/提案/内容/処理/前処理/集約処理」については経路ＩＤ＝８となる。
【００１７】
範囲欄２２２は、経路式によって示されるデータ範囲を［文書ＩＤ、開始位置、終了位置］の形式により範囲を示す。図２に示したＸＭＬ文書２１０の場合、＜集約処理＞タグの文書位置は「１４」であり、＜／集約処理＞タグの文書位置「１６」であるから、「/提案/内容/処理/前処理/集約処理」のデータは、文書ＩＤ＝１の文書において文書位置＝（１４、１６）の範囲のデータである。したがって、範囲欄２２２に示される範囲データは、［１、１４、１６］となる。
【００１８】
同様に、経路式「/論文/内容/課題」の範囲データは［２、２２、２８］である。これは文書ＩＤ＝２の文書において、文書位置＝（２２、２８）の範囲のデータがこの経路式によって特定されるデータの範囲であることを示す。経路式「/提案/課題」の範囲データは［１、５、７］と［４、８、１６］の２つである。これは文書ＩＤ＝１と文書ＩＤ＝４の２つのＸＭＬ文書のどちらにも経路式「/提案/課題」という経路式が含まれることを意味する。
【００１９】
完全経路インデックス２１４において経路式として表されるノードは＜発案者＞のようなタグに限られない。たとえば、図２の＜発案者＞タグの要素データである文字列”竹内真教”についても経路式として登録できる。この場合、経路式は「/提案/発案者/”竹内真教”」、経路ＩＤ＝２０１４、範囲［１、３、３］となる。経路ＩＤ＝２０１４は、「/提案/発案者/”竹内真教”」という文字列を所定規則に基づいて変換することにより得られる数値である。
【００２０】
図４は、図３の経路欄２１６の詳細を示すデータ構造図である。
経路欄２１６には、実際には経路式を示す文字列がそのまま格納されるのではなく、経路式を数値表現したデータ（以下、特に区別するときには「数値経路式」とよぶ）が格納される。数値経路式は、実際の経路とは逆順に経路を示す。
【００２１】
先述した経路式「/提案/発案者/”竹内真教”」を例として説明する。
数値経路式においては、まず、末端ノードである文字列”竹内真教”を示す４バイトの数値「４８５７」が先頭にくる。「４８５７」は所定の変換規則により文字列”竹内真教”を変換することにより得られる数値である。
次の１バイトは、末端ノードの種別を示す。種別は、要素：１、属性：２、テキスト：３、処理命令（PI:Processing Instruction）：７、コメント：８のいずれかである。文字列”竹内真教”は、「/提案/発案者/」の内容を示すテキストなので、種別は「３」となる。
次に、＜発案者＞を示す４バイトの数値「０１０２」が続く。「０１０２」も所定の変換規則により文字列”発案者”を変換することにより得られる数値である。＜提案＞を示す数値は「０８８１」となる。数値経路式に含まれる各数値は、経路式の構成要素となる「提案」や「竹内真教」などの文字列を一意に識別できる数値であればよい。
以上により、「/提案/発案者/”竹内真教”」という経路式は、経路欄２１６においては「４８５７３０１０２０８８１」という１３バイトの数値経路式として表される。
【００２２】
Ａ：完全経路式が入力された場合
完全経路式として「/提案/内容/処理/前処理/集約処理」が入力されたとする。文書検索装置１００は、まず、この完全経路式を上述した方法により、数値経路式に変換する。この数値経路式と完全経路インデックス２１４の経路欄２１６における数値経路式を比較することにより、経路ＩＤ＝８、範囲データ［１、１４、１６］を検出する。数値経路式同士のマッチングにより検出するため、文字列表現の経路式を比較するよりも高速な検索処理が可能である。
【００２３】
Ｂ：部分経路式が入力される場合
部分経路式として「//構成」が入力されたとする。完全な経路がわからないので、文書検索装置１００は、末端ノードの「構成」を数値表現に変換する。このとき、文書検索装置１００は、「構成」を示す４バイトの数値と経路欄２１６の数値経路式の先頭４バイトを比較することにより、経路ＩＤ＝５、範囲データ［１、９、１１］を検出する。部分経路式においては、末端ノードがわかるがその上位ノードがわからないことが多い。本来の経路式の逆順となるように数値経路式を構成することにより、部分経路式の末端ノードだけである程度、検索対象データの候補を絞り込むことができる。
【００２４】
ただし、「//内容/処理/*/集約処理」や「//内容/処理//集約処理」、「//内容/処理/*」のような部分経路式が与えられた場合、完全経路インデックス２１４から検索対象データを特定するためのアルゴリズムは複雑になる。タグの階層が深くなるといっそう処理は複雑化する。そこで、本実施例においては、完全経路インデックス２１４に加えて部分経路インデックス２３０により、検索対象データが存在する可能性がある位置（以下、「候補位置」とよぶ）を効率的に絞り込むための処理を実行している。
【００２５】
図５は、部分経路インデックス２３０のデータ構造図である。
インデックス保持部１３０は、完全経路インデックス２１４に加えて部分経路インデックス２３０も格納している。キー欄２２６は、部分経路インデックス２３０において検索のキー（Key）となる２つのタグ（以下、「キータグセット」とよぶ）か、１つのタグ（以下、「キータグ」とよぶ）を示す。キータグセットとキータグを併せていうときには単に「キー」とよぶ。キータグセットとは、文書中のタグの階層として直接の上下関係にあるタグの組み合わせを示す。たとえば、ＸＭＬ文書２１０では＜構成＞タグの直接の親タグは＜内容＞なので、「内容/構成」はキータグセットとなる。しかし、＜提案＞タグや＜課題＞タグは＜構成＞タグの直接の親タグではないので「提案/構成」や「課題/構成」はキータグセットとはならない。これに対し、文書に含まれる全てのタグがキータグとなることができる。部分経路インデックス２３０は、文書データベース２００に含まれる全ての文書に含まれるキーを対象としたデータである。
【００２６】
位置インデックス欄２２８は、キーの出現する位置を［経路ＩＤ、出現階層］の形式で示す。このような形式の位置データのことを「位置インデックス」とよぶ。「内容/処理」というキータグセットは「/提案/内容/処理」という文書ＩＤ＝１のＸＭＬ文書２１０の第２階層からあらわれる。ルートノードを０階層とし、第１階層をルートノード直下の階層として数えている。以下、文書ＩＤ＝ｎ（ｎは自然数）のＸＭＬ文書のことを文書（ＩＤ：ｎ）のように表記することにする。位置インデックスには文書ＩＤに関する情報が存在しないため、部分経路インデックス２３０だけでは、「内容/処理」が文書（ＩＤ：ｎ）に存在することはわからない。
【００２７】
経路式「/提案/内容/処理」の経路ＩＤ＝６より、「内容/処理」の位置インデックスは［６、２］となる。同様にして、このキータグセットは「/提案/内容/処理/前処理」という文書（ＩＤ：１）、経路ＩＤ＝７の経路式の第２階層にもあらわれる。このときの「内容/処理」の位置インデックスは［７、２］となる。
【００２８】
先ほど例に挙げた「//内容/処理/*/集約処理」という部分経路式の場合、この部分経路式が示す経路条件は以下の通りである。
１．経路式に「内容/処理」、「集約処理」を含む。
２．「内容/処理」と「集約処理」の間には何らかの１階層がある、いいかえれば、＜内容＞から３階層下位に＜集約処理＞が出現する。
まず、部分経路式から、タグセット「内容/処理」、タグ「集約処理」を抽出する。
【００２９】
キータグセット「内容/処理」の位置インデックスは、「６、２」、「７、２」、「８、２」、「１１、２」、「１２、２」の５つである。すなわち、キータグセット「内容/処理」を経路式に含む位置インデックスとして５箇所の候補が特定される。以下、このような候補となる位置インデックスのことを「候補位置」とよぶ。
キータグ「集約処理」の位置インデックスは、「８、５」、「１２、４」の２つである。すなわち、キータグ「集約処理」に関する候補位置は２箇所である。
【００３０】
ここで、「内容/処理」の位置インデックス「６、２」について、経路式ＩＤ＝６であるが、「集約処理」の位置インデックスには経路ＩＤ＝６となるものがない。これは、経路ＩＤ＝６の経路式には、「集約処理」が含まれ得ないことを意味する。こうして、位置インデックス「６、２」は、上記経路条件から外れる。同様の理由から、「７、２」、「１１、２」も候補から外れる。残るのは、「８、２」、「１２、２」と「８、５」、「１２、４」となる。
【００３１】
「８、２」と「８、５」は、共に経路ＩＤ＝８という経路式の一部を示し、「内容/処理」が第２階層、「集約処理」が第５階層にあらわれることを示している。すなわち、経路ＩＤ＝８の経路式は「/*/内容/処理/*/集約処理」という経路式を含むことになるが、これは部分経路式に示された経路条件と整合している。完全経路インデックス２１４の経路ＩＤ＝８のデータを参照することにより、範囲データ［１、１４、１６］を特定できる。すなわち、経路式「/提案/内容/処理/前処理/集約処理」が文書（ＩＤ：１）に特定される。
【００３２】
一方、「１２、２」と「１２、４」は、共に、経路ＩＤ＝１２という経路式の一部を示し、「内容/処理」が第２階層、「集約処理」が第４階層にあらわれることを示している。すなわち、経路ＩＤ＝１２の「/*/内容/処理/集約処理」という経路式を含むことになるが、これは部分経路式に示された経路条件と整合していない。したがって、文書（ＩＤ：１）において、文書位置＝（１４、１６）の範囲のデータだけが求めるデータである。
【００３３】
同様にして、部分検索式「//内容/処理//集約処理」が与えられたときには、「内容/処理」と「集約処理」の間の階層数が不定なので、経路ＩＤ＝８と１２の両方の経路式が候補となる。部分検索式「//前処理//集約処理」が与えられたときには、タグ「前処理」について［７、４］、［８、４］、［１５、３］が候補位置となり、キータグ「集約処理」について［８、５］、［１２、４］となる。完全経路インデックス２１４も参照すると、文書ＩＤ＝１、経路式ＩＤ＝８の経路式のみが該当する。部分検索式「//提案/内容/*/前処理/集約処理」であれば、キータグセット「提案/内容」の位置インデックスとキータグセット「前処理/集約処理」についての位置インデックスと完全経路インデックス２１４から文書（ＩＤ：１）の経路ＩＤ＝８の経路式が特定される。
このように、部分経路インデックス２３０によれば、不完全な部分検索式が入力されたときに文書データベース２００のＸＭＬ文書自体を経路解析する必要がなくなる。また、完全経路インデックス２１４の経路欄２１６から経路条件に整合する経路式を直接探すよりも、候補位置を効率的に絞り込むことができる。部分経路インデックス２３０を使った検索は、ＸＭＬ文書のタグ階層が深くなるときや検索対象となる文書数が多いときには特に有効な検索方法である。
【００３４】
キー欄２２６のキーは、キーＩＤとよばれる所定長の数値列として格納される。キーＩＤは、キータグセットやキータグを一意に識別できる数値であればよい。キー欄２２６におけるキーを数値表現形式で格納することにより、キー名を示す文字列をそのまま格納するよりも検索処理をいっそう高速化することができる。キーＩＤも、キーを示す文字列を所定のハッシュ関数によって変換することにより生成してもよい。あるいは、キーとキーＩＤを一意に対応づける変換テーブルにより、互いを対応づけてもよい。
【００３５】
図６は、文書検索装置１００の機能ブロック図である。
ここに示す各ブロックは、ハードウェア的には、コンピュータのＣＰＵをはじめとする素子や機械装置で実現でき、ソフトウェア的にはコンピュータプログラム等によって実現されるが、ここでは、それらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックはハードウェア、ソフトウェアの組み合わせによっていろいろなかたちで実現できることは、当業者には理解されるところである。
【００３６】
文書検索装置１００は、ユーザインタフェース処理部１１０、データ処理部１２０およびインデックス保持部１３０を含む。
ユーザインタフェース処理部１１０は、ユーザからの入力処理やユーザに対する情報表示のようなユーザインタフェース全般に関する処理を担当する。本実施例においては、ユーザインタフェース処理部１１０により文書検索装置１００のユーザインタフェースサービスが提供されるものとして説明する。別例として、ユーザはインターネットを介して文書検索装置１００を操作してもよい。この場合、図示しない通信部が、ユーザ端末からの操作指示情報を受信し、またその操作指示に基づいて実行された処理結果情報をユーザ端末に送信することになる。
【００３７】
データ処理部１２０は、ユーザインタフェース処理部１１０や文書データベース２００から取得されたデータを元にして各種のデータ処理を実行する。データ処理部１２０は、ユーザインタフェース処理部１１０とインデックス保持部１３０の間のインタフェースの役割も果たす。
【００３８】
ユーザインタフェース処理部１１０は、入力部１１２と表示部１１４を含む。入力部１１２は、ユーザからの入力操作を受け付ける。検索用の経路式は、入力部１１２を介して取得される。表示部１１４は、ユーザに対して各種情報を表示する。
【００３９】
データ処理部１２０は、経路分解部１２２と検索部１２４、登録部１２６を含む。
経路分解部１２２は、部分経路式やＸＭＬ文書の経路情報を解析する。部分抽出部１２８は、部分経路式やＸＭＬ文書からタグやタグセットを抽出する。ＩＤ変換部１３２は、経路式やキーを数値表現に変換する。また、ＩＤ変換部１３２は、経路式から経路ＩＤを生成する。登録部１２６は、新たなＸＭＬ文書が文書データベース２００に追加されるとき、その文書についてのデータを完全経路インデックス２１４と部分経路インデックス２３０に登録する。
【００４０】
ＸＭＬ文書が文書データベース２００に追加されるとき、ＩＤ変換部１３２は文書中の経路式を数値経路式に変換する。そして、登録部１２６が完全経路インデックス２１４に数値経路式とその範囲データを登録する。また、部分抽出部１２８は文書からキーを抽出し、ＩＤ変換部１３２がキーを数値表現形式のキーＩＤに変換する。登録部１２６は部分経路インデックス２３０に数値表現形式のキーＩＤと位置インデックスを登録する。文書データベース２００のＸＭＬ文書が編集、削除されたときにも、同様の処理方法により、完全経路インデックス２１４と部分経路インデックス２３０が更新される。
【００４１】
検索部１２４は、入力された経路式に基づいて、文書および該当箇所を検出する。検索部１２４は、位置特定部１３４と範囲特定部１３６を含む。位置特定部１３４は、部分経路インデックス２３０を参照して、キーから位置インデックスを特定する。範囲特定部１３６は、経路式から範囲データを特定する。
部分経路式による検索に際しては、部分抽出部１２８が部分経路式からキーを抽出し、ＩＤ変換部１３２がキーを数値表現形式のキーＩＤに変換する。位置特定部１３４は、このキーＩＤに基づいて部分経路インデックス２３０から候補位置を特定する。範囲特定部１３６は、位置特定部１３４が特定した候補位置から、範囲データを特定する。結果は、表示部１１４により画面表示される。
【００４２】
図７は、部分経路式に基づく検索処理の過程を示すフローチャートである。
まず、入力部１１２が部分経路式の入力を受け付ける（Ｓ１０）。部分抽出部１２８は、部分検索式から１以上のキーとなるタグセットやタグを抽出する（Ｓ１２）。ここでは、先ほどの「//内容/処理/*/集約処理」という部分検索式が入力され、キータグセット「内容/処理」とキータグ「集約処理」が抽出されたとする。抽出されたキーは、ＩＤ変換部１３２によってキーＩＤに変換される。位置特定部１３４は、部分経路インデックス２３０を参照して、キーＩＤから候補位置を特定する（Ｓ１４）。キータグセット「内容/処理」の位置インデックスであれば、「６、２」、「７、２」、「８、２」、「１１、２」、「１２、２」の５つの位置インデックスが特定される。
【００４３】
更に、別のキーが抽出されていれば（Ｓ１６のＮ）、Ｓ１４に戻って次のキーについての候補位置が特定される。先ほどの例の場合、キータグ「集約処理」について「８、５」、「１２、４」の２つの位置インデックスが特定される。
【００４４】
全てのキーについて候補位置が特定されると（Ｓ１６のＹ）、位置特定部１３４は各キーについて特定された候補位置の間で整合する位置を特定する（Ｓ１８）。こうして、候補位置の数が絞り込まれる。部分検索式「//内容/処理/*/集約処理」については、「８、２」と「８、５」のペアが特定される。範囲特定部１３６は、この位置インデックスに示される経路ＩＤ＝８に基づいて、完全経路インデックス２１４から範囲データ［１、１４、１６］を特定する（Ｓ２０）。表示部１１４は、文書（ＩＤ：１）の経路ＩＤ＝８の経路式について該当データ、すなわち、文書位置１４から文書位置１６までのデータを画面表示させる（Ｓ２２）。
【００４５】
以上のアルゴリズムに基づいて、更に、複合的なデータ検索も可能である。たとえば、部分検索式「//発案者」と文字列「”竹内真教”」が入力されたとする。位置特定部１３４は、キータグ「発案者」について、部分経路インデックス２３０から位置インデックス「２、２」を特定する。完全経路インデックス２１４によると、「//発案者」に該当する範囲データは、文書（ＩＤ：１）、文書位置＝（２、４）にある。経路式は「/提案/発案者」である。
【００４６】
検索部１２４の図示しない文字列検索部は、文字列「”竹内真教”」について、完全経路インデックス２１４から該当する範囲データを検索する。範囲データとして［１、３、３］と特定されたとする。この場合、文字列「”竹内真教”」のデータの範囲は、「/提案/発案者」のデータの範囲におさまっている。検索部１２４は、部分検索式「//発案者」と文字列「”竹内真教”」のそれぞれについて特定された範囲データが整合したので、「/提案/発案者/”竹内真教”」を該当データとして特定する。
【００４７】
なお、本実施例におけるキータグセットとは、階層的に直接の上下関係にある２つのタグの組み合わせであるとして説明したが、キータグセットはこのような条件に制約される必要はない。たとえば、階層的に直接の上下関係にある３つのタグの組み合わせであってもよい。もちろん、３個以上のタグの組み合わせをキータグセットとしてもよい。
【００４８】
また、キータグセットに含まれるタグは、必ずしも直接の上下関係になくてもよい。たとえば、「/提案/内容/処理/前処理/集約処理」という経路式において、「内容-前処理」というタグの組み合わせではタグ間に２階層の差がある。また、「内容-集約処理」というタグの組み合わせであれば、階層差は３となる。部分経路インデックス２３０においては、キータグセットと、そのキータグセットを構成するタグ間の階層差が記録されてもよい。そして、位置特定部１３４は、部分経路式から抽出したタグセットの階層差と、キータグセットにおける階層差を参照して、候補位置を特定してもよい。
【００４９】
本実施例ではＸＭＬ文書を対象として説明したが、文書検索装置１００は、ＸＨＴＭＬやＨＴＭＬ、ＳＧＭＬなど、タグの階層構造に基づく経路式によってデータの位置が特定されるタイプの文書ファイルであれば、いずれを対象としても応用可能である。
【００５０】
以上、本実施例に示す文書検索装置１００によると、部分経路式に基づくデータ検索を効率的に実行できる。部分経路インデックス２３０に「キータグ」や「キータグセット」についての位置インデックスを登録しておくことにより、部分経路式に含まれるタグセットやタグに基づいて、候補位置を絞り込むことができる。そして、完全経路インデックス２１４により、より具体的にデータの位置を特定できる。検索時に文書ファイルを調べて、経路情報をメモリに展開する必要がないため、効率的な検索が可能となる。
【００５１】
部分経路式によるデータ検索の処理負荷が大きくなると、部分経路式に基づくデータ検索がユーザにとって使いにくいものとなってしまう。本実施例に示した文書検索装置１００は、完全経路インデックス２１４と部分経路インデックス２３０という２種類のインデックスデータを参照することにより、求めるデータの位置を高速かつ軽い計算機負荷にて特定できることになる。
【００５２】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００５３】
請求項に記載の「インデックス情報」は、本実施例における部分経路インデックス２３０により表現されている。請求項に記載の「タグセットＩＤ」は、本実施例においては、キータグセットについてのキーＩＤとして表現されている。
これら請求項に記載の各構成要件が果たすべき機能は、本実施例において示された各機能ブロックの単体もしくはそれらの連係によって実現されることも当業者には理解されるところである。
【図面の簡単な説明】
【００５４】
【図１】文書検索装置による処理の概要を説明するための模式図である。
【図２】本実施例におけるＸＭＬ文書を示す図である。
【図３】完全経路インデックスのデータ構造図である。
【図４】図３の経路欄の詳細を示すデータ構造図である。
【図５】部分経路インデックスのデータ構造図である。
【図６】文書検索装置の機能ブロック図である。
【図７】部分経路式に基づく検索処理の過程を示すフローチャートである。
【符号の説明】
【００５５】
１００ 文書検索装置、 １１０ ユーザインタフェース処理部、 １１２ 入力部、 １１４ 表示部、 １２０ データ処理部、 １２２ 経路分解部、 １２４ 検索部、 １２６ 登録部、 １２８ 部分抽出部、 １３０ インデックス保持部、 １３２ ＩＤ変換部、 １３４ 位置特定部、 １３６ 範囲特定部、 ２００ 文書データベース、 ２１２ 文書位置欄、 ２１４ 完全経路インデックス、 ２１６ 経路欄、 ２１８ 経路ＩＤ欄、 ２２２ 範囲欄、 ２２６ キー欄、 ２２８ 位置インデックス欄、 ２３０ 部分経路インデックス。
【技術分野】
【０００１】
本発明は、文書処理技術に関し、特に、構造化文書ファイルを対象とした情報検索技術、に関する。
【背景技術】
【０００２】
コンピュータの普及とネットワーク技術の進展にともない、ネットワークを介した電子情報の交換が盛んになっている。これにより、従来においては紙ベースで行われていた事務処理の多くが、ネットワークベースの処理に置き換えられつつある。デジタル化とネットワーク技術の進展は、情報取得コストを急激に低下させている。このような状況において、大量の文書ファイルの中から所望のデータを検索する技術の重要性が高まっている。
【特許文献１】特開２００６−０４８５３６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
ところで、近年では、多くの文書ファイルが、ＨＴＭＬ（Hyper Text Markup Language）やＸＨＴＭＬ（eXtensible HyperText Markup Language）、ＸＭＬ（eXtensible Markup Language）などによる構造化文書ファイルとして作成されるようになってきている。構造化文書ファイルはタグによって階層化されるため、文書中のデータをタグのパス表記によって指定できる。このように、構造化文書ファイルには、データの位置を特定しやすいという優れた特性がある。中でも、ＸＭＬは、ネットワークを介して他者とデータを共有するのに適した形式として注目されている。ＸＭＬ文書であれば、ＸＰａｔｈ（XML Path Language）に基づく構文であるＸＰａｔｈ式によりデータを特定できる。
【０００４】
ＸＰａｔｈは、省略記号にも対応できる表記法となっている。たとえば、「/提案//集約処理」というＸＰａｔｈ式は、「＜提案＞タグの下位の階層に＜集約処理＞タグが出現する全てのパス」という条件を意味する。以下、このようなタグの経路に関する条件のことを「経路条件」とよぶことにする。また、ＸＰａｔｈ式のように、タグの階層構造に基づいてタグのパスを示す構文のことを「経路式」とよぶことにする。上記経路条件に対しては、「/提案/集約処理」、「/提案/内容/集約処理」、「/提案/内容/基本処理/集約処理」として指定されるいずれの経路式も適合する。
一方「/提案/*/集約処理」というＸＰａｔｈ式は、「＜提案＞タグから２階層下位の階層に＜集約処理＞タグが出現する全てのパス」という経路条件を意味する。上記した３つの経路式のうちでは「/提案/内容/集約処理」だけがこの経路条件に適合する。
【０００５】
ユーザが省略記号のないＸＰａｔｈ式を指定できれば、構造化文書ファイルから所望のデータを取り出すことができる。しかし、常に正確に経路式がわかるとは限らない。たとえば、検索対象となるデータが＜提案＞タグの下の＜集約処理＞タグにあることがわかっていても、＜提案＞タグと＜集約処理＞タグの間に、どのようなタグが何階層あるか、そもそも、どの文書に求めるデータがあるかわからないことがある。
上記したような省略記号を含む不完全な経路式が入力されたとき、その経路式によって示される経路条件に適合するデータを検索できれば便利である。以下、省略記号を含むなどの理由により、検索対象となるデータの位置を一意に特定するには不充分な経路式のことを「部分経路式」とよび、省略記号を含まない経路式のことを「完全経路式」とよぶ。
【０００６】
部分経路式に基づくデータ検索方法として、構造化文書ファイルのタグ構造を解析し、タグの経路情報をメモリに展開した上で、経路条件に適合する位置のデータを検出するという方法が一般的である。しかし、このような方法は、メモリの使用量が大きく、処理時間も長くなるという問題点がある。特に、多数の構造化文書ファイルや、タグの階層構造が複雑な構造化文書ファイルの中から所望のデータを探す場合には、このような問題点が顕在化しやすい。
【０００７】
本発明はこうした状況に鑑みてなされたものであり、その目的は、不完全な経路式に基づいて構造化文書ファイル中から所望のデータを効率的に検索するための技術、を提供することある。
【課題を解決するための手段】
【０００８】
本発明のある態様は、構造化文書ファイルから所望のデータを検索するための文書検索装置に関する。
この装置は、構造化文書ファイルにおいて階層的に上下関係にあるタグセットと、経路式の一部にそのタグセットを含む１以上の位置とを対応づけたインデックス情報を保持する。この装置は、部分経路式の入力を受け付けると、インデックス情報を参照して、部分経路式に含まれるタグセットが経路式の一部としてあらわれる位置を検索対象位置の候補位置として特定する。
【０００９】
インデックス情報としてタグセットごとの位置を登録しておくことにより、検索実行時に文書ファイルにアクセスしてタグの階層構造を精査しなくても、検索対象となるデータを特定できる。このため、不完全な部分経路式が入力されたときにも、検索対象となるデータを効率的に検出できる。
【００１０】
なお、以上の構成要素の任意の組み合わせ、本発明の表現を方法、システム、プログラム、記録媒体などの間で変換したものもまた、本発明の態様として有効である。
【発明の効果】
【００１１】
本発明によれば、不完全な経路式に基づいて構造化文書ファイル中から所望のデータを効率的に検索することができる。
【発明を実施するための最良の形態】
【００１２】
図１は、文書検索装置１００による処理の概要を説明するための模式図である。
ユーザが文書検索装置１００に対して経路式を入力すると、文書検索装置１００は経路式に適合するデータを文書データベース２００から検索する。文書データベース２００の文書ファイルは、ＸＭＬ文書やＸＨＴＭＬ文書のようにタグによって構造化された構造化文書ファイルである。本実施例においては、検索対象となる文書ファイルはＸＭＬファイルであるとして説明する。
【００１３】
文書検索装置１００のインデックス保持部１３０は、各文書ファイルを検索するためのインデックス情報を保持する。インデックス情報は、完全経路インデックス２１４と部分経路インデックス２３０の２種類があるが、それぞれについては図３から図５に関連して後に詳述する。文書検索装置１００は、入力された経路式とインデックス情報に基づいて、文書データベース２００から検索対象となるデータがどの文書のどの位置にあるかを検索する。文書検索装置１００は、検出された文書ファイルの文書ＩＤと、その文書ファイルにおける検索対象データとを画面表示させる。こうして、文書検索装置１００のユーザは、任意の経路式に対して、検索対象データ、または、検索対象データの候補を文書データベース２００から探し出す。
【００１４】
図２は、本実施例におけるＸＭＬ文書２１０を示す図である。
同図に示すＸＭＬ文書２１０を対象として本実施例を説明する。文書データベース２００の各文書ファイルには文書ＩＤが付与される。同図に示すＸＭＬ文書２１０の文書ＩＤは「１」であるとする。文書ＩＤとは、文書データベース２００において文書ファイルを一意に識別するためのＩＤである。このＸＭＬ文書２１０は、アイディア提案書に関するＸＭＬ文書であり、＜提案＞や＜発案者＞など複数のタグを含む。文書位置欄２１２は、ＸＭＬ文書２１０に含まれるさまざまなデータの位置を示す。たとえば、＜提案＞タグのこの文書における文書位置は「１」であり、＜／集約処理＞タグの文書位置は「１６」である。また、＜発案者＞タグの内容データである文字列”竹内真教”の文書位置は「３」である。文書位置は、タグ、属性、コメント、タグの内容となるデータごとに割り当てられ、文書ごとに一意の値となる。
以下においては説明を簡単にするため、タグに対する文書位置を中心として説明する。
【００１５】
図３は、完全経路インデックス２１４のデータ構造図である。
完全経路インデックス２１４は、インデックス保持部１３０に格納される。経路欄２１６は、文書データベース２００に含まれる経路式の一覧である。経路欄２１６には図２に示した文書ＩＤ＝１の文書に含まれる経路式だけでなく、その他の文書に含まれる経路式も含まれる。経路ＩＤ欄２１８は、経路欄２１６に示す経路の経路ＩＤを示す。経路ＩＤは、経路式を示す文字列を所定規則により変換した数値列である。ハッシュ関数により変換してもよいし、所定のテーブルによって変換してもよいが、いずれにしても、各経路式が実用上差し支えない程度に一意に識別される値であればよい。
【００１６】
同図において、経路式「/提案」のＸＭＬ文書２１０における経路ＩＤ＝１となっている。経路式「/提案/発案者」の場合、経路ＩＤ＝２である。同様に、「/提案/内容/処理/前処理/集約処理」については経路ＩＤ＝８となる。
【００１７】
範囲欄２２２は、経路式によって示されるデータ範囲を［文書ＩＤ、開始位置、終了位置］の形式により範囲を示す。図２に示したＸＭＬ文書２１０の場合、＜集約処理＞タグの文書位置は「１４」であり、＜／集約処理＞タグの文書位置「１６」であるから、「/提案/内容/処理/前処理/集約処理」のデータは、文書ＩＤ＝１の文書において文書位置＝（１４、１６）の範囲のデータである。したがって、範囲欄２２２に示される範囲データは、［１、１４、１６］となる。
【００１８】
同様に、経路式「/論文/内容/課題」の範囲データは［２、２２、２８］である。これは文書ＩＤ＝２の文書において、文書位置＝（２２、２８）の範囲のデータがこの経路式によって特定されるデータの範囲であることを示す。経路式「/提案/課題」の範囲データは［１、５、７］と［４、８、１６］の２つである。これは文書ＩＤ＝１と文書ＩＤ＝４の２つのＸＭＬ文書のどちらにも経路式「/提案/課題」という経路式が含まれることを意味する。
【００１９】
完全経路インデックス２１４において経路式として表されるノードは＜発案者＞のようなタグに限られない。たとえば、図２の＜発案者＞タグの要素データである文字列”竹内真教”についても経路式として登録できる。この場合、経路式は「/提案/発案者/”竹内真教”」、経路ＩＤ＝２０１４、範囲［１、３、３］となる。経路ＩＤ＝２０１４は、「/提案/発案者/”竹内真教”」という文字列を所定規則に基づいて変換することにより得られる数値である。
【００２０】
図４は、図３の経路欄２１６の詳細を示すデータ構造図である。
経路欄２１６には、実際には経路式を示す文字列がそのまま格納されるのではなく、経路式を数値表現したデータ（以下、特に区別するときには「数値経路式」とよぶ）が格納される。数値経路式は、実際の経路とは逆順に経路を示す。
【００２１】
先述した経路式「/提案/発案者/”竹内真教”」を例として説明する。
数値経路式においては、まず、末端ノードである文字列”竹内真教”を示す４バイトの数値「４８５７」が先頭にくる。「４８５７」は所定の変換規則により文字列”竹内真教”を変換することにより得られる数値である。
次の１バイトは、末端ノードの種別を示す。種別は、要素：１、属性：２、テキスト：３、処理命令（PI:Processing Instruction）：７、コメント：８のいずれかである。文字列”竹内真教”は、「/提案/発案者/」の内容を示すテキストなので、種別は「３」となる。
次に、＜発案者＞を示す４バイトの数値「０１０２」が続く。「０１０２」も所定の変換規則により文字列”発案者”を変換することにより得られる数値である。＜提案＞を示す数値は「０８８１」となる。数値経路式に含まれる各数値は、経路式の構成要素となる「提案」や「竹内真教」などの文字列を一意に識別できる数値であればよい。
以上により、「/提案/発案者/”竹内真教”」という経路式は、経路欄２１６においては「４８５７３０１０２０８８１」という１３バイトの数値経路式として表される。
【００２２】
Ａ：完全経路式が入力された場合
完全経路式として「/提案/内容/処理/前処理/集約処理」が入力されたとする。文書検索装置１００は、まず、この完全経路式を上述した方法により、数値経路式に変換する。この数値経路式と完全経路インデックス２１４の経路欄２１６における数値経路式を比較することにより、経路ＩＤ＝８、範囲データ［１、１４、１６］を検出する。数値経路式同士のマッチングにより検出するため、文字列表現の経路式を比較するよりも高速な検索処理が可能である。
【００２３】
Ｂ：部分経路式が入力される場合
部分経路式として「//構成」が入力されたとする。完全な経路がわからないので、文書検索装置１００は、末端ノードの「構成」を数値表現に変換する。このとき、文書検索装置１００は、「構成」を示す４バイトの数値と経路欄２１６の数値経路式の先頭４バイトを比較することにより、経路ＩＤ＝５、範囲データ［１、９、１１］を検出する。部分経路式においては、末端ノードがわかるがその上位ノードがわからないことが多い。本来の経路式の逆順となるように数値経路式を構成することにより、部分経路式の末端ノードだけである程度、検索対象データの候補を絞り込むことができる。
【００２４】
ただし、「//内容/処理/*/集約処理」や「//内容/処理//集約処理」、「//内容/処理/*」のような部分経路式が与えられた場合、完全経路インデックス２１４から検索対象データを特定するためのアルゴリズムは複雑になる。タグの階層が深くなるといっそう処理は複雑化する。そこで、本実施例においては、完全経路インデックス２１４に加えて部分経路インデックス２３０により、検索対象データが存在する可能性がある位置（以下、「候補位置」とよぶ）を効率的に絞り込むための処理を実行している。
【００２５】
図５は、部分経路インデックス２３０のデータ構造図である。
インデックス保持部１３０は、完全経路インデックス２１４に加えて部分経路インデックス２３０も格納している。キー欄２２６は、部分経路インデックス２３０において検索のキー（Key）となる２つのタグ（以下、「キータグセット」とよぶ）か、１つのタグ（以下、「キータグ」とよぶ）を示す。キータグセットとキータグを併せていうときには単に「キー」とよぶ。キータグセットとは、文書中のタグの階層として直接の上下関係にあるタグの組み合わせを示す。たとえば、ＸＭＬ文書２１０では＜構成＞タグの直接の親タグは＜内容＞なので、「内容/構成」はキータグセットとなる。しかし、＜提案＞タグや＜課題＞タグは＜構成＞タグの直接の親タグではないので「提案/構成」や「課題/構成」はキータグセットとはならない。これに対し、文書に含まれる全てのタグがキータグとなることができる。部分経路インデックス２３０は、文書データベース２００に含まれる全ての文書に含まれるキーを対象としたデータである。
【００２６】
位置インデックス欄２２８は、キーの出現する位置を［経路ＩＤ、出現階層］の形式で示す。このような形式の位置データのことを「位置インデックス」とよぶ。「内容/処理」というキータグセットは「/提案/内容/処理」という文書ＩＤ＝１のＸＭＬ文書２１０の第２階層からあらわれる。ルートノードを０階層とし、第１階層をルートノード直下の階層として数えている。以下、文書ＩＤ＝ｎ（ｎは自然数）のＸＭＬ文書のことを文書（ＩＤ：ｎ）のように表記することにする。位置インデックスには文書ＩＤに関する情報が存在しないため、部分経路インデックス２３０だけでは、「内容/処理」が文書（ＩＤ：ｎ）に存在することはわからない。
【００２７】
経路式「/提案/内容/処理」の経路ＩＤ＝６より、「内容/処理」の位置インデックスは［６、２］となる。同様にして、このキータグセットは「/提案/内容/処理/前処理」という文書（ＩＤ：１）、経路ＩＤ＝７の経路式の第２階層にもあらわれる。このときの「内容/処理」の位置インデックスは［７、２］となる。
【００２８】
先ほど例に挙げた「//内容/処理/*/集約処理」という部分経路式の場合、この部分経路式が示す経路条件は以下の通りである。
１．経路式に「内容/処理」、「集約処理」を含む。
２．「内容/処理」と「集約処理」の間には何らかの１階層がある、いいかえれば、＜内容＞から３階層下位に＜集約処理＞が出現する。
まず、部分経路式から、タグセット「内容/処理」、タグ「集約処理」を抽出する。
【００２９】
キータグセット「内容/処理」の位置インデックスは、「６、２」、「７、２」、「８、２」、「１１、２」、「１２、２」の５つである。すなわち、キータグセット「内容/処理」を経路式に含む位置インデックスとして５箇所の候補が特定される。以下、このような候補となる位置インデックスのことを「候補位置」とよぶ。
キータグ「集約処理」の位置インデックスは、「８、５」、「１２、４」の２つである。すなわち、キータグ「集約処理」に関する候補位置は２箇所である。
【００３０】
ここで、「内容/処理」の位置インデックス「６、２」について、経路式ＩＤ＝６であるが、「集約処理」の位置インデックスには経路ＩＤ＝６となるものがない。これは、経路ＩＤ＝６の経路式には、「集約処理」が含まれ得ないことを意味する。こうして、位置インデックス「６、２」は、上記経路条件から外れる。同様の理由から、「７、２」、「１１、２」も候補から外れる。残るのは、「８、２」、「１２、２」と「８、５」、「１２、４」となる。
【００３１】
「８、２」と「８、５」は、共に経路ＩＤ＝８という経路式の一部を示し、「内容/処理」が第２階層、「集約処理」が第５階層にあらわれることを示している。すなわち、経路ＩＤ＝８の経路式は「/*/内容/処理/*/集約処理」という経路式を含むことになるが、これは部分経路式に示された経路条件と整合している。完全経路インデックス２１４の経路ＩＤ＝８のデータを参照することにより、範囲データ［１、１４、１６］を特定できる。すなわち、経路式「/提案/内容/処理/前処理/集約処理」が文書（ＩＤ：１）に特定される。
【００３２】
一方、「１２、２」と「１２、４」は、共に、経路ＩＤ＝１２という経路式の一部を示し、「内容/処理」が第２階層、「集約処理」が第４階層にあらわれることを示している。すなわち、経路ＩＤ＝１２の「/*/内容/処理/集約処理」という経路式を含むことになるが、これは部分経路式に示された経路条件と整合していない。したがって、文書（ＩＤ：１）において、文書位置＝（１４、１６）の範囲のデータだけが求めるデータである。
【００３３】
同様にして、部分検索式「//内容/処理//集約処理」が与えられたときには、「内容/処理」と「集約処理」の間の階層数が不定なので、経路ＩＤ＝８と１２の両方の経路式が候補となる。部分検索式「//前処理//集約処理」が与えられたときには、タグ「前処理」について［７、４］、［８、４］、［１５、３］が候補位置となり、キータグ「集約処理」について［８、５］、［１２、４］となる。完全経路インデックス２１４も参照すると、文書ＩＤ＝１、経路式ＩＤ＝８の経路式のみが該当する。部分検索式「//提案/内容/*/前処理/集約処理」であれば、キータグセット「提案/内容」の位置インデックスとキータグセット「前処理/集約処理」についての位置インデックスと完全経路インデックス２１４から文書（ＩＤ：１）の経路ＩＤ＝８の経路式が特定される。
このように、部分経路インデックス２３０によれば、不完全な部分検索式が入力されたときに文書データベース２００のＸＭＬ文書自体を経路解析する必要がなくなる。また、完全経路インデックス２１４の経路欄２１６から経路条件に整合する経路式を直接探すよりも、候補位置を効率的に絞り込むことができる。部分経路インデックス２３０を使った検索は、ＸＭＬ文書のタグ階層が深くなるときや検索対象となる文書数が多いときには特に有効な検索方法である。
【００３４】
キー欄２２６のキーは、キーＩＤとよばれる所定長の数値列として格納される。キーＩＤは、キータグセットやキータグを一意に識別できる数値であればよい。キー欄２２６におけるキーを数値表現形式で格納することにより、キー名を示す文字列をそのまま格納するよりも検索処理をいっそう高速化することができる。キーＩＤも、キーを示す文字列を所定のハッシュ関数によって変換することにより生成してもよい。あるいは、キーとキーＩＤを一意に対応づける変換テーブルにより、互いを対応づけてもよい。
【００３５】
図６は、文書検索装置１００の機能ブロック図である。
ここに示す各ブロックは、ハードウェア的には、コンピュータのＣＰＵをはじめとする素子や機械装置で実現でき、ソフトウェア的にはコンピュータプログラム等によって実現されるが、ここでは、それらの連携によって実現される機能ブロックを描いている。したがって、これらの機能ブロックはハードウェア、ソフトウェアの組み合わせによっていろいろなかたちで実現できることは、当業者には理解されるところである。
【００３６】
文書検索装置１００は、ユーザインタフェース処理部１１０、データ処理部１２０およびインデックス保持部１３０を含む。
ユーザインタフェース処理部１１０は、ユーザからの入力処理やユーザに対する情報表示のようなユーザインタフェース全般に関する処理を担当する。本実施例においては、ユーザインタフェース処理部１１０により文書検索装置１００のユーザインタフェースサービスが提供されるものとして説明する。別例として、ユーザはインターネットを介して文書検索装置１００を操作してもよい。この場合、図示しない通信部が、ユーザ端末からの操作指示情報を受信し、またその操作指示に基づいて実行された処理結果情報をユーザ端末に送信することになる。
【００３７】
データ処理部１２０は、ユーザインタフェース処理部１１０や文書データベース２００から取得されたデータを元にして各種のデータ処理を実行する。データ処理部１２０は、ユーザインタフェース処理部１１０とインデックス保持部１３０の間のインタフェースの役割も果たす。
【００３８】
ユーザインタフェース処理部１１０は、入力部１１２と表示部１１４を含む。入力部１１２は、ユーザからの入力操作を受け付ける。検索用の経路式は、入力部１１２を介して取得される。表示部１１４は、ユーザに対して各種情報を表示する。
【００３９】
データ処理部１２０は、経路分解部１２２と検索部１２４、登録部１２６を含む。
経路分解部１２２は、部分経路式やＸＭＬ文書の経路情報を解析する。部分抽出部１２８は、部分経路式やＸＭＬ文書からタグやタグセットを抽出する。ＩＤ変換部１３２は、経路式やキーを数値表現に変換する。また、ＩＤ変換部１３２は、経路式から経路ＩＤを生成する。登録部１２６は、新たなＸＭＬ文書が文書データベース２００に追加されるとき、その文書についてのデータを完全経路インデックス２１４と部分経路インデックス２３０に登録する。
【００４０】
ＸＭＬ文書が文書データベース２００に追加されるとき、ＩＤ変換部１３２は文書中の経路式を数値経路式に変換する。そして、登録部１２６が完全経路インデックス２１４に数値経路式とその範囲データを登録する。また、部分抽出部１２８は文書からキーを抽出し、ＩＤ変換部１３２がキーを数値表現形式のキーＩＤに変換する。登録部１２６は部分経路インデックス２３０に数値表現形式のキーＩＤと位置インデックスを登録する。文書データベース２００のＸＭＬ文書が編集、削除されたときにも、同様の処理方法により、完全経路インデックス２１４と部分経路インデックス２３０が更新される。
【００４１】
検索部１２４は、入力された経路式に基づいて、文書および該当箇所を検出する。検索部１２４は、位置特定部１３４と範囲特定部１３６を含む。位置特定部１３４は、部分経路インデックス２３０を参照して、キーから位置インデックスを特定する。範囲特定部１３６は、経路式から範囲データを特定する。
部分経路式による検索に際しては、部分抽出部１２８が部分経路式からキーを抽出し、ＩＤ変換部１３２がキーを数値表現形式のキーＩＤに変換する。位置特定部１３４は、このキーＩＤに基づいて部分経路インデックス２３０から候補位置を特定する。範囲特定部１３６は、位置特定部１３４が特定した候補位置から、範囲データを特定する。結果は、表示部１１４により画面表示される。
【００４２】
図７は、部分経路式に基づく検索処理の過程を示すフローチャートである。
まず、入力部１１２が部分経路式の入力を受け付ける（Ｓ１０）。部分抽出部１２８は、部分検索式から１以上のキーとなるタグセットやタグを抽出する（Ｓ１２）。ここでは、先ほどの「//内容/処理/*/集約処理」という部分検索式が入力され、キータグセット「内容/処理」とキータグ「集約処理」が抽出されたとする。抽出されたキーは、ＩＤ変換部１３２によってキーＩＤに変換される。位置特定部１３４は、部分経路インデックス２３０を参照して、キーＩＤから候補位置を特定する（Ｓ１４）。キータグセット「内容/処理」の位置インデックスであれば、「６、２」、「７、２」、「８、２」、「１１、２」、「１２、２」の５つの位置インデックスが特定される。
【００４３】
更に、別のキーが抽出されていれば（Ｓ１６のＮ）、Ｓ１４に戻って次のキーについての候補位置が特定される。先ほどの例の場合、キータグ「集約処理」について「８、５」、「１２、４」の２つの位置インデックスが特定される。
【００４４】
全てのキーについて候補位置が特定されると（Ｓ１６のＹ）、位置特定部１３４は各キーについて特定された候補位置の間で整合する位置を特定する（Ｓ１８）。こうして、候補位置の数が絞り込まれる。部分検索式「//内容/処理/*/集約処理」については、「８、２」と「８、５」のペアが特定される。範囲特定部１３６は、この位置インデックスに示される経路ＩＤ＝８に基づいて、完全経路インデックス２１４から範囲データ［１、１４、１６］を特定する（Ｓ２０）。表示部１１４は、文書（ＩＤ：１）の経路ＩＤ＝８の経路式について該当データ、すなわち、文書位置１４から文書位置１６までのデータを画面表示させる（Ｓ２２）。
【００４５】
以上のアルゴリズムに基づいて、更に、複合的なデータ検索も可能である。たとえば、部分検索式「//発案者」と文字列「”竹内真教”」が入力されたとする。位置特定部１３４は、キータグ「発案者」について、部分経路インデックス２３０から位置インデックス「２、２」を特定する。完全経路インデックス２１４によると、「//発案者」に該当する範囲データは、文書（ＩＤ：１）、文書位置＝（２、４）にある。経路式は「/提案/発案者」である。
【００４６】
検索部１２４の図示しない文字列検索部は、文字列「”竹内真教”」について、完全経路インデックス２１４から該当する範囲データを検索する。範囲データとして［１、３、３］と特定されたとする。この場合、文字列「”竹内真教”」のデータの範囲は、「/提案/発案者」のデータの範囲におさまっている。検索部１２４は、部分検索式「//発案者」と文字列「”竹内真教”」のそれぞれについて特定された範囲データが整合したので、「/提案/発案者/”竹内真教”」を該当データとして特定する。
【００４７】
なお、本実施例におけるキータグセットとは、階層的に直接の上下関係にある２つのタグの組み合わせであるとして説明したが、キータグセットはこのような条件に制約される必要はない。たとえば、階層的に直接の上下関係にある３つのタグの組み合わせであってもよい。もちろん、３個以上のタグの組み合わせをキータグセットとしてもよい。
【００４８】
また、キータグセットに含まれるタグは、必ずしも直接の上下関係になくてもよい。たとえば、「/提案/内容/処理/前処理/集約処理」という経路式において、「内容-前処理」というタグの組み合わせではタグ間に２階層の差がある。また、「内容-集約処理」というタグの組み合わせであれば、階層差は３となる。部分経路インデックス２３０においては、キータグセットと、そのキータグセットを構成するタグ間の階層差が記録されてもよい。そして、位置特定部１３４は、部分経路式から抽出したタグセットの階層差と、キータグセットにおける階層差を参照して、候補位置を特定してもよい。
【００４９】
本実施例ではＸＭＬ文書を対象として説明したが、文書検索装置１００は、ＸＨＴＭＬやＨＴＭＬ、ＳＧＭＬなど、タグの階層構造に基づく経路式によってデータの位置が特定されるタイプの文書ファイルであれば、いずれを対象としても応用可能である。
【００５０】
以上、本実施例に示す文書検索装置１００によると、部分経路式に基づくデータ検索を効率的に実行できる。部分経路インデックス２３０に「キータグ」や「キータグセット」についての位置インデックスを登録しておくことにより、部分経路式に含まれるタグセットやタグに基づいて、候補位置を絞り込むことができる。そして、完全経路インデックス２１４により、より具体的にデータの位置を特定できる。検索時に文書ファイルを調べて、経路情報をメモリに展開する必要がないため、効率的な検索が可能となる。
【００５１】
部分経路式によるデータ検索の処理負荷が大きくなると、部分経路式に基づくデータ検索がユーザにとって使いにくいものとなってしまう。本実施例に示した文書検索装置１００は、完全経路インデックス２１４と部分経路インデックス２３０という２種類のインデックスデータを参照することにより、求めるデータの位置を高速かつ軽い計算機負荷にて特定できることになる。
【００５２】
以上、本発明を実施の形態をもとに説明した。この実施の形態は例示であり、それらの各構成要素や各処理プロセスの組み合わせにいろいろな変形例が可能なこと、またそうした変形例も本発明の範囲にあることは当業者に理解されるところである。
【００５３】
請求項に記載の「インデックス情報」は、本実施例における部分経路インデックス２３０により表現されている。請求項に記載の「タグセットＩＤ」は、本実施例においては、キータグセットについてのキーＩＤとして表現されている。
これら請求項に記載の各構成要件が果たすべき機能は、本実施例において示された各機能ブロックの単体もしくはそれらの連係によって実現されることも当業者には理解されるところである。
【図面の簡単な説明】
【００５４】
【図１】文書検索装置による処理の概要を説明するための模式図である。
【図２】本実施例におけるＸＭＬ文書を示す図である。
【図３】完全経路インデックスのデータ構造図である。
【図４】図３の経路欄の詳細を示すデータ構造図である。
【図５】部分経路インデックスのデータ構造図である。
【図６】文書検索装置の機能ブロック図である。
【図７】部分経路式に基づく検索処理の過程を示すフローチャートである。
【符号の説明】
【００５５】
１００ 文書検索装置、 １１０ ユーザインタフェース処理部、 １１２ 入力部、 １１４ 表示部、 １２０ データ処理部、 １２２ 経路分解部、 １２４ 検索部、 １２６ 登録部、 １２８ 部分抽出部、 １３０ インデックス保持部、 １３２ ＩＤ変換部、 １３４ 位置特定部、 １３６ 範囲特定部、 ２００ 文書データベース、 ２１２ 文書位置欄、 ２１４ 完全経路インデックス、 ２１６ 経路欄、 ２１８ 経路ＩＤ欄、 ２２２ 範囲欄、 ２２６ キー欄、 ２２８ 位置インデックス欄、 ２３０ 部分経路インデックス。
【特許請求の範囲】
【請求項１】
タグの階層構造に基づく経路式によってデータの位置が特定される構造化文書ファイルにおいて、階層的に上下関係にあるタグの組み合わせであるタグセットと、経路式の一部にそのタグセットを含む１以上の位置とを対応づけたインデックス情報を保持するインデックス保持部と、
前記構造化文書ファイルにおける検索対象位置への経路式の一部を示す部分経路式の入力を受け付ける経路式入力部と、
前記部分経路式から階層的に上下関係にあるタグセットを抽出するタグセット抽出部と、
前記インデックス情報を参照して、前記部分経路式から抽出されたタグセットが経路式の一部としてあらわれる位置を前記検索対象位置の候補位置として特定する候補位置特定部と、
を備えることを特徴とする文書検索装置。
【請求項２】
タグセットとは、階層的に直接の上下関係にある２つのタグの組み合わせであることを特徴とする請求項１に記載の文書検索装置。
【請求項３】
前記タグセット抽出部が、前記部分経路式から第１のタグセットと第２のタグセットを抽出したとき、
前記候補位置特定部は、前記第１のタグセットについての候補位置と前記第２のタグセットについての候補位置を比較して互いに整合する位置を、前記検索対象位置の候補位置として特定することを特徴とする請求項１または２に記載の文書検索装置。
【請求項４】
前記タグセット抽出部が、前記第１のタグセットを前記第２のタグセットよりも階層的に上位のタグセットとして検出したとき、
前記候補位置特定部は、前記第１のタグセットと前記第２のタグセットの前記部分経路式における階層上の距離と、前記第１のタグセットについての候補位置と前記第２のタグセットについての候補位置との距離が整合する位置を、前記検索対象位置の候補位置として特定することを特徴とする請求項３に記載の文書検索装置。
【請求項５】
前記インデックス保持部は、更に、前記構造化文書ファイルに含まれるタグと、経路式の一部にそのタグを含む１以上の位置とをインデックス情報の一部として対応づけて保持し、
前記タグセット抽出部は、前記部分経路式から特定タグを抽出し、
前記候補位置特定部は、前記インデックス情報を参照して、前記部分経路式から抽出された特定タグが経路式の一部としてあらわれる位置を前記特定タグについての候補位置として検出すると共に、前記部分経路式から抽出されたタグセットの候補位置と前記特定タグについての候補位置を比較して互いに整合する位置を、前記検索対象位置の候補位置として特定することを特徴とする請求項１から４のいずれかに記載の文書検索装置。
【請求項６】
前記インデックス保持部は、タグセットを所定規則にしたがって所定長の文字列に変換したタグセットＩＤと、経路式の一部にそのタグセットを含む１以上の位置を対応づけてインデックス情報として保持し、
前記候補位置特定部は、前記部分経路式から抽出されたタグセットを前記所定規則にしたがってタグセットＩＤに変換した上で、候補位置を特定することを特徴とする請求項１から５のいずれかに記載の文書検索装置。
【請求項７】
タグの階層構造に基づく経路式によってデータの位置が特定される構造化文書ファイルにおいて、階層的に上下関係にあるタグの組み合わせであるタグセットと、経路式の一部にそのタグセットを含む１以上の位置とを対応づけたインデックス情報を取得するステップと、
前記構造化文書ファイルにおける検索対象位置への経路式の一部を示す部分経路式の入力を受け付けるステップと、
前記部分経路式から階層的に上下関係にあるタグセットを抽出するステップと、
前記インデックス情報を参照して、前記部分経路式から抽出されたタグセットが経路式の一部としてあらわれる位置を前記検索対象位置の候補位置として特定するステップと、
を備えることを特徴とする文書検索方法。
【請求項８】
タグの階層構造に基づく経路式によってデータの位置が特定される構造化文書ファイルにおいて、階層的に上下関係にあるタグの組み合わせであるタグセットと、経路式の一部にそのタグセットを含む１以上の位置とを対応づけたインデックス情報を保持する機能と、
前記構造化文書ファイルにおける検索対象位置への経路式の一部を示す部分経路式の入力を受け付ける機能と、
前記部分経路式から階層的に上下関係にあるタグセットを抽出する機能と、
前記インデックス情報を参照して、前記部分経路式から抽出されたタグセットが経路式の一部としてあらわれる位置を前記検索対象位置の候補位置として特定する機能と、
をコンピュータに発揮させることを特徴とする文書検索プログラム。
【請求項１】
タグの階層構造に基づく経路式によってデータの位置が特定される構造化文書ファイルにおいて、階層的に上下関係にあるタグの組み合わせであるタグセットと、経路式の一部にそのタグセットを含む１以上の位置とを対応づけたインデックス情報を保持するインデックス保持部と、
前記構造化文書ファイルにおける検索対象位置への経路式の一部を示す部分経路式の入力を受け付ける経路式入力部と、
前記部分経路式から階層的に上下関係にあるタグセットを抽出するタグセット抽出部と、
前記インデックス情報を参照して、前記部分経路式から抽出されたタグセットが経路式の一部としてあらわれる位置を前記検索対象位置の候補位置として特定する候補位置特定部と、
を備えることを特徴とする文書検索装置。
【請求項２】
タグセットとは、階層的に直接の上下関係にある２つのタグの組み合わせであることを特徴とする請求項１に記載の文書検索装置。
【請求項３】
前記タグセット抽出部が、前記部分経路式から第１のタグセットと第２のタグセットを抽出したとき、
前記候補位置特定部は、前記第１のタグセットについての候補位置と前記第２のタグセットについての候補位置を比較して互いに整合する位置を、前記検索対象位置の候補位置として特定することを特徴とする請求項１または２に記載の文書検索装置。
【請求項４】
前記タグセット抽出部が、前記第１のタグセットを前記第２のタグセットよりも階層的に上位のタグセットとして検出したとき、
前記候補位置特定部は、前記第１のタグセットと前記第２のタグセットの前記部分経路式における階層上の距離と、前記第１のタグセットについての候補位置と前記第２のタグセットについての候補位置との距離が整合する位置を、前記検索対象位置の候補位置として特定することを特徴とする請求項３に記載の文書検索装置。
【請求項５】
前記インデックス保持部は、更に、前記構造化文書ファイルに含まれるタグと、経路式の一部にそのタグを含む１以上の位置とをインデックス情報の一部として対応づけて保持し、
前記タグセット抽出部は、前記部分経路式から特定タグを抽出し、
前記候補位置特定部は、前記インデックス情報を参照して、前記部分経路式から抽出された特定タグが経路式の一部としてあらわれる位置を前記特定タグについての候補位置として検出すると共に、前記部分経路式から抽出されたタグセットの候補位置と前記特定タグについての候補位置を比較して互いに整合する位置を、前記検索対象位置の候補位置として特定することを特徴とする請求項１から４のいずれかに記載の文書検索装置。
【請求項６】
前記インデックス保持部は、タグセットを所定規則にしたがって所定長の文字列に変換したタグセットＩＤと、経路式の一部にそのタグセットを含む１以上の位置を対応づけてインデックス情報として保持し、
前記候補位置特定部は、前記部分経路式から抽出されたタグセットを前記所定規則にしたがってタグセットＩＤに変換した上で、候補位置を特定することを特徴とする請求項１から５のいずれかに記載の文書検索装置。
【請求項７】
タグの階層構造に基づく経路式によってデータの位置が特定される構造化文書ファイルにおいて、階層的に上下関係にあるタグの組み合わせであるタグセットと、経路式の一部にそのタグセットを含む１以上の位置とを対応づけたインデックス情報を取得するステップと、
前記構造化文書ファイルにおける検索対象位置への経路式の一部を示す部分経路式の入力を受け付けるステップと、
前記部分経路式から階層的に上下関係にあるタグセットを抽出するステップと、
前記インデックス情報を参照して、前記部分経路式から抽出されたタグセットが経路式の一部としてあらわれる位置を前記検索対象位置の候補位置として特定するステップと、
を備えることを特徴とする文書検索方法。
【請求項８】
タグの階層構造に基づく経路式によってデータの位置が特定される構造化文書ファイルにおいて、階層的に上下関係にあるタグの組み合わせであるタグセットと、経路式の一部にそのタグセットを含む１以上の位置とを対応づけたインデックス情報を保持する機能と、
前記構造化文書ファイルにおける検索対象位置への経路式の一部を示す部分経路式の入力を受け付ける機能と、
前記部分経路式から階層的に上下関係にあるタグセットを抽出する機能と、
前記インデックス情報を参照して、前記部分経路式から抽出されたタグセットが経路式の一部としてあらわれる位置を前記検索対象位置の候補位置として特定する機能と、
をコンピュータに発揮させることを特徴とする文書検索プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００８−９０４０３（Ｐ２００８−９０４０３Ａ）
【公開日】平成２０年４月１７日（２００８．４．１７）
【国際特許分類】
【出願番号】特願２００６−２６７８８８（Ｐ２００６−２６７８８８）
【出願日】平成１８年９月２９日（２００６．９．２９）
【出願人】（３９００２４３５０）株式会社ジャストシステム (123)
【Ｆターム（参考）】
【公開日】平成２０年４月１７日（２００８．４．１７）
【国際特許分類】
【出願日】平成１８年９月２９日（２００６．９．２９）
【出願人】（３９００２４３５０）株式会社ジャストシステム (123)
【Ｆターム（参考）】
[ Back to top ]