(57)【特許請求の範囲】
【請求項１】
構造化文書を分散して格納する複数の文書管理装置と、前記複数の文書管理装置とネットワークで接続され、前記複数の文書管理装置から構造化文書を検索する検索装置と、前記複数の文書管理装置と前記検索装置とにネットワークで接続され、構造化文書の検索要求を前記検索装置に送信するクライアント装置と、を備えた構造化文書検索システムであって、
前記文書管理装置は、
構造化文書の論理的な構造の単位である構造要素のうち予め定められた前記構造要素に対応する構造化文書の部分文字列を格納する文書記憶手段と、
前記検索装置または他の文書管理装置から前記部分文字列の取得要求を受信する要求受信手段と、
前記要求受信手段が受信した前記取得要求に基づき、前記文書記憶手段から前記部分文字列を取得し、取得した前記部分文字列に含まれる情報であって、前記取得した前記部分文字列の一部が他の文書管理装置に格納されていることを示す情報に基づき、前記取得した前記部分文字列の一部が他の文書管理装置に格納されているか否かを判断する第１の結果データ取得手段と、
前記第１の結果データ取得手段が前記部分文字列の一部が他の文書管理装置に格納されていると判断した場合に、前記部分文字列の一部についての前記取得要求を、前記部分文字列の一部を格納していると判断された他の文書管理装置に送信する第１の要求送信手段と、
前記取得した前記部分文字列を前記検索装置に送信する第１の結果送信手段と、を備え、
前記検索装置は、
前記構造要素を一意に識別する構造ＩＤと、前記構造要素に対応する前記部分文字列を格納する前記文書管理装置を一意に識別する装置ＩＤとを対応づけて記憶する構造情報記憶手段と、
前記クライアント装置から前記検索要求を受信する検索要求受信手段と、
前記検索要求受信手段が受信した前記検索要求を満たす前記構造要素の前記構造ＩＤを前記構造情報記憶手段から取得する検索手段と、
前記検索手段が取得した前記構造ＩＤに対応する前記文書管理装置の前記装置ＩＤを前記構造情報記憶手段から取得する第２の結果データ取得手段と、
前記第２の結果データ取得手段が取得した前記装置ＩＤで識別される前記文書管理装置に、前記取得要求を送信する第２の要求送信手段と、
前記文書管理装置から前記部分文字列を受信する部分文字列受信手段と、
前記部分文字列受信手段が複数の前記文書管理装置のそれぞれから前記部分文字列を受信した場合に、受信した複数の前記部分文字列を相互に結合し、結合した文書を前記クライアント装置に送信する第２の結果送信手段と、
を備えたことを特徴とする構造化文書検索システム。
【請求項２】
前記文書記憶手段は、木構造で表された構造化文書のうち予め定められた部分木である前記部分文字列を格納し、
前記第２の要求送信手段は、前記第２の結果データ取得手段が取得した前記装置ＩＤで識別される前記文書管理装置に、構造化文書全体の木構造のルートノードに対する前記部分文字列のルートノードの階層の深さの情報を含む階層情報と、前記取得要求とを対応づけて送信し、
前記第１の結果送信手段は、前記第１の結果データ取得手段が取得した前記部分文字列と、前記階層情報とを対応づけて前記検索装置に送信し、
前記第２の結果送信手段は、送信された前記部分文字列が複数存在する場合に、前記階層情報に基づき、前記深さが小さい前記部分文字列が前記深さが大きい前記部分文字列より上位階層となるように複数の前記部分文字列を相互に結合して前記クライアント装置に送信することを特徴とする請求項１に記載の構造化文書検索システム。
【請求項３】
前記第１の結果送信手段は、前記第１の結果データ取得手段が取得した前記部分文字列と、取得した順序を示す順序情報を含む前記階層情報とを対応づけて前記検索装置に送信し、
前記第２の結果送信手段は、送信された前記部分文字列が複数存在する場合に、前記順序情報を含む前記階層情報に基づき、前記深さが小さい前記部分文字列が前記深さが大きい前記部分文字列より上位階層となるように複数の前記部分文字列を相互に結合し、同一階層の前記部分文字列に対しては、先に取得した前記部分文字列を後に取得した前記部分文字列より前に結合して前記クライアント装置に送信することを特徴とする請求項２に記載の構造化文書検索システム。
【請求項４】
前記構造情報記憶手段は、前記構造要素を一意に識別する構造ＩＤと、前記構造要素に対応する前記部分文字列を格納する前記文書管理装置を一意に識別する装置ＩＤと、構造化文書内に前記部分文字列が出現する個数を示す頻度情報とを対応づけて記憶し、
前記第２の要求送信手段は、前記構造情報記憶手段に記憶された前記頻度情報に基づき、前記階層情報のサイズを決定することを特徴とする請求項３に記載の構造化文書検索システム。
【請求項５】
前記文書記憶手段は、前記部分文字列の一部が他の文書管理装置に格納されている場合に、前記部分文字列の一部が格納されている前記文書管理装置の前記装置ＩＤと前記部分文字列の一部のルートノードを一意に識別するノードＩＤとを含む情報である接続情報を、前記部分文字列の一部を含む前記部分文字列と対応づけて格納し、
前記第１の要求送信手段は、前記第１の結果データ取得手段が取得した前記部分文字列が前記接続情報と対応づけられている場合に、前記接続情報に含まれる前記装置ＩＤに対応する前記文書管理装置に、前記接続情報に含まれる前記ノードＩＤで識別されるノードをルートノードとする前記部分文字列の取得要求を送信することを特徴とする請求項２に記載の構造化文書検索システム。
【請求項６】
前記文書記憶手段は、前記部分文字列の一部が他の文書管理装置に格納されている場合に、前記部分文字列の一部に対応する前記構造要素の前記構造ＩＤと前記部分文字列の一部のルートノードを一意に識別するノードＩＤとを含む情報である接続情報を、前記部分文字列の一部を含む前記部分文字列と対応づけて格納し、
前記第１の要求送信手段は、前記第１の結果データ取得手段が取得した前記部分文字列が前記接続情報と対応づけられている場合に、前記接続情報に含まれる前記構造ＩＤに対応づけられた前記装置ＩＤを前記構造情報記憶手段から取得し、取得した前記装置ＩＤに対応する前記文書管理装置に、前記接続情報に含まれる前記ノードＩＤで識別されるノードをルートノードとする前記部分文字列の取得要求を送信することを特徴とする請求項２に記載の構造化文書検索システム。
【請求項７】
前記第２の要求送信手段は、前記検索装置に情報を送信する際に用いる情報である送信情報を含む前記取得要求を前記第２の結果データ取得手段が取得した前記装置ＩＤで識別される前記文書管理装置に送信し、
前記第１の結果送信手段は、前記取得要求に含まれる前記送信情報に基づき、取得した前記部分文字列を前記検索装置に送信することを特徴とする請求項１に記載の構造化文書検索システム。
【請求項８】
前記第１の結果送信手段は、前記検索装置に対して単方向に情報を送信する前記ネットワークの通信回線を用いて、前記第１の結果データ取得手段が取得した前記部分文字列を前記検索装置に送信することを特徴とする請求項１に記載の構造化文書検索システム。
【請求項９】
前記文書記憶手段は、ＸＭＬ（Ｅｘｔｅｎｓｉｂｌｅ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）で記述された構造化文書のうち予め定められた部分である部分文字列を格納することを特徴とする請求項１に記載の構造化文書検索システム。
【請求項１０】
構造化文書を分散して格納する複数の文書管理装置と、前記複数の文書管理装置とネットワークで接続され、前記複数の文書管理装置から構造化文書を検索する検索装置と、前記複数の文書管理装置と前記検索装置とにネットワークで接続され、構造化文書の検索要求を前記検索装置に送信するクライアント装置と、を備えた構造化文書検索システムにおける構造化文書検索方法であって、
前記検索装置が、前記クライアント装置から前記検索要求を受信する検索要求受信ステップと、
前記検索装置が、構造化文書の論理的な構造の要素である構造要素を一意に識別する構造ＩＤと、前記構造要素に対応する前記部分文字列を格納する前記文書管理装置を一意に識別する装置ＩＤとを対応づけて記憶する構造情報記憶手段から、前記検索要求受信手段が受信した前記検索要求を満たす前記構造要素の前記構造ＩＤを取得する検索ステップと、
前記検索装置が、前記検索ステップが取得した前記構造ＩＤに対応する前記文書管理装置の前記装置ＩＤを前記構造情報記憶手段から取得する第２の結果データ取得ステップと、
前記検索装置が、前記第２の結果データ取得ステップが取得した前記装置ＩＤで識別される前記文書管理装置に、前記取得要求を送信する第２の要求送信ステップと、
前記文書管理装置が、前記検索装置または他の文書管理装置から前記部分文字列の取得要求を受信する要求受信ステップと、
前記文書管理装置が、前記要求受信ステップが受信した前記取得要求に基づき、前記構造要素のうち予め定められた前記構造要素に対応する構造化文書の部分文字列を格納する文書記憶手段から前記部分文字列を取得し、取得した前記部分文字列に含まれる情報であって、前記取得した前記部分文字列の一部が他の文書管理装置に格納されていることを示す情報に基づき、前記取得した前記部分文字列の一部が他の文書管理装置に格納されているか否かを判断する第１の結果データ取得ステップと、
前記文書管理装置が、前記第１の結果データ取得ステップが前記部分文字列の一部が他の文書管理装置に格納されていると判断した場合に、前記部分文字列の一部についての前記取得要求を、前記部分文字列の一部を格納していると判断された他の文書管理装置に送信する第１の要求送信ステップと、
前記文書管理装置が、前記取得した前記部分文字列を前記検索装置に送信する第１の結果送信ステップと、
前記検索装置が、前記文書管理装置から前記部分文字列を受信する部分文字列受信ステップと、
前記検索装置が、前記部分文字列受信ステップが受信した前記部分文字列が複数存在する場合に、複数の前記部分文字列を相互に結合し、結合した文書を前記クライアント装置に送信する第２の結果送信ステップと、
を備えたことを特徴とする構造化文書検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、大量の構造化文書を階層化された論理構造を持つ構造化文書データベース群で分散配置して管理する構造化文書検索システムおよび構造化文書検索方法に関するものである。
【背景技術】
【０００２】
近年、情報技術の進歩により、莫大な量の情報が容易に入手できるようになった。その一方で必要な情報が大量のデータに埋没し、十分に活用できないという弊害も発生している。情報が大量に存在しても、それをうまく活用できなければ意味がない。情報には、１つの書式に統一された情報もあれば、全く書式のない自由書式の情報も数多く存在する。
【０００３】
これらの情報を統一的に扱うための中核技術として期待されている技術がＸＭＬ（Extensible Markup Language）である。ＸＭＬは柔軟な拡張性と連携性を備えた標準のドキュメント記述言語であり、主要ベンダーからのサポートも約束されている。ＸＭＬのような構造化文書は、（１）階層的な構造をもつ、（２）同じパスの構造要素が文書内に繰り返し発生しうる、（３）部分文書の文字列は長大データになりうる、という特徴を持つ。
【０００４】
一方、格納されたデータを取り出す手段として、各種の問合せ言語が存在する。ＲＤＢ（Relational Database）の分野では、問合せ言語としてＳＱＬ（Structured Query Language)が存在する。ＸＭＬの分野では、問合せ言語としてＸＱｕｅｒｙ（XML Query Language)が策定されている。ＸＱｕｅｒｙは、ＸＭＬデータをデータベースのように扱うための問合せ言語である。構造要素の値に関する条件や階層構造に関する条件に合致するデータ集合の取り出しを行うことができる。また、パスの正規表現により、“「文書」タグの子孫のどこかに存在する「コメント」タグ”といった曖昧な階層構造に関する条件も指定できる。
【０００５】
構造化文書では、データを取り出す対象は必ずしも構造化文書全体ではなく、局所的であることが多い。また、書誌情報と本体情報とからなる構造化文書の場合、書誌情報は多数の利用者から読取り専用でアクセスされるが、本体情報は一部の利用者から更新のためにアクセスされるというように、文書内の部分の相違によりアクセスパターンが異なることもある。
【０００６】
一方、一般に文書検索時に特定のディスクへのアクセスが集中するとレスポンスタイムが極端に遅くなることが知られている。このため、構造化文書へのアクセスパターンやアクセス頻度の偏りを考慮して、大量の構造化文書を文書単位だけでなく、文書内の部分木単位で分割配置することで、問合せ処理を効率化する技術が提案されている。
【０００７】
例えば、非特許文献１では、構造化文書を水平分割および垂直分割する方法をＸＰａｔｈと呼ばれる問合せ式で定義し、分割された文書をRepository Guideと呼ばれる索引づけられた構造情報で管理することを前提とし、アクセス頻度を考慮して構造化文書を分割することで検索処理の高速化を実現している。
【０００８】
【非特許文献１】中尾伸章他、「アクセス頻度を考慮したＸＭＬ文書分割方式の提案」（ＤＥＷＳ２００４  ５Ａ−ｉ５）
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、非特許文献１の方法では、問合せの結果データを取得する際、対象となるデータが複数のディスクに分散して格納されている場合に、接続部分のノード群同士の結合処理の負担が大きくなるという問題があった。
【００１０】
具体的には、非特許文献１の方法では、１個以上の部分文書の候補を求めた上で、接続部分にあたるノード群同士について構造結合を行うことで、実際に必要となる部分文書を絞り込む。その後、分割された部分文書同士を結合する。構造化文書は同じパスの構造要素が文書内に繰り返し発生するので、接続部分の上位と下位の部分文書は多数になりうる。このため、上位と下位の組合せの数が膨大になる場合があり、結合処理の負担が大きくなる。
【００１１】
そこで、分割された部分文書の接続部分について、下位ノードへのリンクを表すノードＩＤを上位ノードに保持する技術も提案されている。この技術では、対象となるデータが複数のディスクに分散して格納されている場合であっても、リンクを辿ることで接続部分の上位ノードから下位ノードに直接アクセスして、問合せの結果データを生成することができる。このため、構造結合を行う必要がなく、非特許文献１のような問題が発生しない。
【００１２】
ところが、このようなリンクを辿る方法では、リンク先の装置で検索した部分文書をリンク元の装置に順次転送するため、重複したデータ転送が発生するという問題があった。特に、分割数が多く、リンクの数が多いほど、重複したデータ転送が発生する。
【００１３】
例えば、文書が上位ノード、中位ノード、下位ノードの３つに分割され、２つのリンクが設定されているとする。この場合、下位ノードを格納した装置から転送した検索結果は、中位ノードを格納した装置で検索した結果に結合され、さらに上位ノードを格納した装置に転送される。すなわち、下位ノードを格納した装置から転送した検索結果は、２度データ転送が行われることになる。
【００１４】
本発明は、上記に鑑みてなされたものであって、予め定められた部分構造を分散配置して格納した構造化文書を検索する際のデータ転送量を削減し、高速な検索を実現することができる構造化文書検索システムおよび構造化文書検索方法を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上述した課題を解決し、目的を達成するために、本発明は、構造化文書を分散して格納する複数の文書管理装置と、前記複数の文書管理装置とネットワークで接続され、前記複数の文書管理装置から構造化文書を検索する検索装置と、前記複数の文書管理装置と前記検索装置とにネットワークで接続され、構造化文書の検索要求を前記検索装置に送信するクライアント装置と、を備えた構造化文書検索システムであって、前記文書管理装置は、構造化文書の論理的な構造の単位である構造要素のうち予め定められた前記構造要素に対応する構造化文書の部分文字列を格納する文書記憶手段と、前記検索装置または他の文書管理装置から前記部分文字列の取得要求を受信する要求受信手段と、前記要求受信手段が受信した前記取得要求に基づき、前記文書記憶手段から前記部分文字列を取得し、取得した前記部分文字列に含まれる情報であって、前記取得した前記部分文字列の一部が他の文書管理装置に格納されていることを示す情報に基づき、前記取得した前記部分文字列の一部が他の文書管理装置に格納されているか否かを判断する第１の結果データ取得手段と、前記第１の結果データ取得手段が前記部分文字列の一部が他の文書管理装置に格納されていると判断した場合に、前記部分文字列の一部についての前記取得要求を、前記部分文字列の一部を格納していると判断された他の文書管理装置に送信する第１の要求送信手段と、前記取得した前記部分文字列を前記検索装置に送信する第１の結果送信手段と、を備え、前記検索装置は、前記構造要素を一意に識別する構造ＩＤと、前記構造要素に対応する前記部分文字列を格納する前記文書管理装置を一意に識別する装置ＩＤとを対応づけて記憶する構造情報記憶手段と、前記クライアント装置から前記検索要求を受信する検索要求受信手段と、前記検索要求受信手段が受信した前記検索要求を満たす前記構造要素の前記構造ＩＤを前記構造情報記憶手段から取得する検索手段と、前記検索手段が取得した前記構造ＩＤに対応する前記文書管理装置の前記装置ＩＤを前記構造情報記憶手段から取得する第２の結果データ取得手段と、前記第２の結果データ取得手段が取得した前記装置ＩＤで識別される前記文書管理装置に、前記取得要求を送信する第２の要求送信手段と、前記文書管理装置から前記部分文字列を受信する部分文字列受信手段と、前記部分文字列受信手段が複数の前記文書管理装置のそれぞれから前記部分文字列を受信した場合に、受信した複数の前記部分文字列を相互に結合し、結合した文書を前記クライアント装置に送信する第２の結果送信手段と、を備えたことを特徴とする。
【００１６】
また、本発明は、構造化文書を分散して格納する複数の文書管理装置と、前記複数の文書管理装置とネットワークで接続され、前記複数の文書管理装置から構造化文書を検索する検索装置と、前記複数の文書管理装置と前記検索装置とにネットワークで接続され、構造化文書の検索要求を前記検索装置に送信するクライアント装置と、を備えた構造化文書検索システムにおける構造化文書検索方法であって、前記検索装置が、前記クライアント装置から前記検索要求を受信する検索要求受信ステップと、前記検索装置が、構造化文書の論理的な構造の要素である構造要素を一意に識別する構造ＩＤと、前記構造要素に対応する前記部分文字列を格納する前記文書管理装置を一意に識別する装置ＩＤとを対応づけて記憶する構造情報記憶手段から、前記検索要求受信手段が受信した前記検索要求を満たす前記構造要素の前記構造ＩＤを取得する検索ステップと、前記検索装置が、前記検索ステップが取得した前記構造ＩＤに対応する前記文書管理装置の前記装置ＩＤを前記構造情報記憶手段から取得する第２の結果データ取得ステップと、前記検索装置が、前記第２の結果データ取得ステップが取得した前記装置ＩＤで識別される前記文書管理装置に、前記取得要求を送信する第２の要求送信ステップと、前記文書管理装置が、前記検索装置または他の文書管理装置から前記部分文字列の取得要求を受信する要求受信ステップと、前記文書管理装置が、前記要求受信ステップが受信した前記取得要求に基づき、前記構造要素のうち予め定められた前記構造要素に対応する構造化文書の部分文字列を格納する文書記憶手段から前記部分文字列を取得し、取得した前記部分文字列に含まれる情報であって、前記取得した前記部分文字列の一部が他の文書管理装置に格納されていることを示す情報に基づき、前記取得した前記部分文字列の一部が他の文書管理装置に格納されているか否かを判断する第１の結果データ取得ステップと、前記文書管理装置が、前記第１の結果データ取得ステップが前記部分文字列の一部が他の文書管理装置に格納されていると判断した場合に、前記部分文字列の一部についての前記取得要求を、前記部分文字列の一部を格納していると判断された他の文書管理装置に送信する第１の要求送信ステップと、前記文書管理装置が、前記取得した前記部分文字列を前記検索装置に送信する第１の結果送信ステップと、前記検索装置が、前記文書管理装置から前記部分文字列を受信する部分文字列受信ステップと、前記検索装置が、前記部分文字列受信ステップが受信した前記部分文字列が複数存在する場合に、複数の前記部分文字列を相互に結合し、結合した文書を前記クライアント装置に送信する第２の結果送信ステップと、を備えたことを特徴とする。
【発明の効果】
【００１７】
本発明によれば、分散配置された部分文書の検索結果を、配置された装置から検索要求を行った装置に直接転送することができる。このため、重複したデータ転送の発生を低減し、高速な検索を実現することができる。
【発明を実施するための最良の形態】
【００１８】
以下に添付図面を参照して、この発明にかかる構造化文書検索システムおよび構造化文書検索方法の最良な実施の形態を詳細に説明する。
【００１９】
本実施の形態にかかる構造化文書検索システムは、複数の文書管理装置に分散配置された部分文書の検索結果を、各文書管理装置から検索要求を行う検索装置に直接転送することにより検索処理の高速化を実現するものである。
【００２０】
本実施の形態では、ＸＭＬにより記述された構造化文書を、ＸＱｕｅｒｙにより記述された問合せデータを用いて検索する例について説明する。
【００２１】
図１は、本実施の形態にかかる構造化文書検索システム１０の構成を示すブロック図である。同図に示すように、構造化文書検索システム１０は、検索装置１００と、文書管理装置２００ａ、２００ｂ、２００ｃ（以下、文書管理装置２００という。）と、ネットワーク３００と、クライアント４００とを備えている。
【００２２】
クライアント４００は、構造化文書の検索要求を送信するものであり、通常のＰＣ（Personal Computer）などにより構成される。クライアント４００は、ＸＱｕｅｒｙで記述された検索要求を検索装置１００に送信する。
【００２３】
ネットワーク３００は、検索装置１００と、文書管理装置２００と、クライアント４００とを接続するネットワークであり、インターネットやＶＰＮなどのあらゆるネットワーク形態により構成することができる。
【００２４】
なお、クライアント４００と検索装置１００とを接続するネットワークと、文書管理装置２００と検索装置１００とを接続するネットワークを別のネットワークで構成してもよい。
【００２５】
検索装置１００は、文書管理装置２００から構造化文書を検索するものである。本実施の形態では、検索装置１００内にも構造化文書を分散して格納するため、検索装置１００内から構造化文書を検索する場合もある。
【００２６】
なお、以下では１つの検索装置１００が存在し、当該検索装置１００により構造化文書の検索処理が実行されるものとして説明するが、複数の検索装置１００を備え、各検索装置１００から検索処理を実行可能とするように構成してもよい。以下では、同図に示すように、検索装置１００の名称を装置Ｘ、文書管理装置２００ａ、２００ｂ、２００ｃの名称をそれぞれ装置Ａ、装置Ｂ、装置Ｃと呼ぶ場合がある。
【００２７】
検索装置１００は、格納処理部１１０と、第２検索処理部１２０と、分割配置設定部１３０と、構造情報記憶部１４０と、構造化文書記憶部１５０と、索引情報記憶部１６０とを備えている。
【００２８】
構造情報記憶部１４０は、ＸＭＬ形式の構造化文書から抽出された構造情報を格納するものである。
【００２９】
ここで、本実施の形態で扱われるＸＭＬ形式の構造化文書について説明する。図２は、ＸＭＬ形式の構造化文書の一例を示した説明図である。
【００３０】
同図に示すように、ＸＭＬ形式の構造化文書は、<header>タグ内の書誌情報と、<body>タグ内の本体情報とに分けられる場合が多い。また、同図の<section>タグまたは<comment>タグのように、同一文書内に繰り返し格納される情報も含まれる。
【００３１】
なお、ＸＭＬでは、タグを使って定義したデータの単位をエレメントという。例えば、<document>タグと</document>タグとを含み、両タグで囲まれたデータが１つのエレメントを構成する。
【００３２】
また、エレメントには、省略可能か、繰り返しが可能かなどの付加的な情報を追加するための属性を指定することができる。同図では、commentエレメントの属性としてname属性が指定された例が示されている。
【００３３】
また、エレメントの中の開始タグと終了タグで囲まれた情報の内容を、以下ではテキストという。例えば、同図のdateエレメントのうち、“20050711”がテキストに該当する。
【００３４】
構造情報はこのようなＸＭＬ形式の構造化文書から、各タグの名称や階層関係、繰り返しの個数などを抽出した情報である。なお、本実施の形態では、上述のエレメント、属性、テキストが、構造化文書の構造情報を構成する要素を示す構造要素となる。
【００３５】
図３は、図２に示す構造化文書から抽出された構造情報の一例を示す説明図である。図３は、構造情報を木構造で表したものであり、楕円形のノードはエレメントに対応するノード（以下、エレメントノードという）、四角形のノードは属性に対応するノード（以下、属性ノードという。）、六角形のノードはテキストに対応するノード（以下、テキストノードという）を意味する。
【００３６】
なお、以下では、ノードとは、一般的な木構造における節を表す用語として用いる。したがって、図３のように構造情報を木構造で表した場合には、構造要素がノードとなる。また、後述するように構造化文書を木構造で表した場合には、構造化文書の一部である部分文字列がノードとなる。
【００３７】
図３に示すように、構造要素には構造要素を一意に識別する識別子であるＴＩＤが割当てられる。図３では、例えば、パス「/document」の「document」タグに対応した構造要素にＴＩＤ１、パス「/document/header」の「header」タグに対応した構造要素にＴＩＤ２、パス「/document/header/title」の「title」タグに対応した構造要素にＴＩＤ３が割り当てられている。
【００３８】
パス「/document/body/section」の「section」タグは構造化文書に２つ含まれるが、同一パスの構造要素は１つに縮約されてＴＩＤ１０が割当てられる。また、構造が異なる複数の構造化文書については、構造情報の重ね合わせにより、全ての構造化文書を包含する、汎化した構造情報を形成する。
【００３９】
なお、二重線で囲まれたノードは、分割対象の構造要素であることを示している。図３の例では、パス「/document」、「/document/body」、「/document/body/section/comment」の３つが分割対象の構造要素であり、それぞれ装置Ａ、装置Ｂ、装置Ｃに分散して格納することが示されている。
【００４０】
次に、構造情報記憶部１４０に格納された構造情報について説明する。図４は、構造情報記憶部１４０に格納された構造情報のデータ構造の一例を示す説明図である。同図の例は、図２に示す構造化文書から抽出された構造情報を表している。
【００４１】
図４では、ツリーの親子関係、兄弟関係などの木構造における構造要素間の関係の他に、分割配置に関する情報と、構造化文書内における頻度情報を保持した例が示されている。
【００４２】
図４に示すように、構造情報は、ＴＩＤと、構造要素の名称を表すシンボル名と、長男に相当する構造要素のＴＩＤと、次弟に相当する構造要素のＴＩＤと、配置位置と、フラグメントルートフラグと、最大フラグメント数とを対応づけて格納している。
【００４３】
ここで、フラグメントとは、各装置に分散して配置するために分割した部分木をいい、フラグメントルートとは、当該分割した部分木のルートとなる構造要素をいう。また、フラグメントルートフラグとは、構造要素がフラグメントルートであるか否かを表す情報をいう。すなわち、フラグメントルートフラグが１である構造要素は、構造化文書の分割対象となり、異なる装置に分割して配置されることを意味する。
【００４４】
最大フラグメント数とは、各フラグメント以下に存在するフラグメントの最大数を表す情報である。例えば、図２に示す構造化文書に対しては、後述する図７の装置Ｂにおけるbodyエレメント（ｂ１−１）に示すようにcommentエレメントが３個存在するため（エレメント７０１、７０２、７０３）、構造化文書記憶部１５０に記憶されているほかの構造化文書のbodyエレメント内のcommentエレメントの個数が３以下であれば、最大フラグメント数は３となる。図４では、bodyエレメント以下のcommentエレメントが４である他の構造化文書が存在したため、フラグメント数が４に設定されている例が示されている。
【００４５】
最大フラグメント数は、分割したフラグメントが構造化文書内で出現する頻度を表す情報であるので、構造化文書内の頻度情報という。
【００４６】
図４では、例えば、ＴＩＤ１のノードについては、ツリーの親子、兄弟関係の情報として、シンボル名は「document」、長男としてＴＩＤ２と関係していることが示されている。また、分割配置に関する情報として、配置位置は装置Ａであり、「フラグメントルートフラグが１」であるため、分割対象の構造要素であることが示されている。また、構造化文書内における頻度情報として、最大繰り返し数が１、当該ノード以下の構造化文書あたりのフラグメント数が１であることが示されている。
【００４７】
なお、構造情報は文書情報や索引情報に比べ更新頻度はかなり少ないと考えられる。したがって、オンラインで更新があるようなシステムであっても、構造情報を各装置のメモリ上に格納し、一貫性を保ちながら共有することが可能である。
【００４８】
構造化文書記憶部１５０は、ＸＭＬ形式の構造化文書を格納するものである。図５、図６は、構造化文書記憶部１５０に格納された構造化文書のデータ構造の一例を示す説明図である。
【００４９】
同図に示すように、構造化文書記憶部１５０は、構造化文書を木構造で表し、木構造の各ノードに、当該各ノードを一意に識別するためのＩＤを割り当てて格納している。
【００５０】
なお、図５の構造化文書１は、図２の構造化文書のうち「document」、「header」、「body」、「section」、「comment」タグに対応するノードにＩＤを割当てた木構造を表している。実際には、構造化文書１には、図２に示す構造化文書の他のタグの内容も格納されている。例えば、ＩＤ＝ｈ１−１のノード下には、「title」タグ、「author」タグ、「date」タグも含まれる。
【００５１】
また、図６の構造化文書２は図２の構造化文書とは別の構造化文書に対応する木構造を表している。構造化文書２は、例えば、「body」タグ内に「section」タグが４個含まれる構造化文書であることを示している。
【００５２】
なお、図５および図６では、１つの構造化文書を１つの装置上に格納した場合のデータ構造の例を示している。１つの構造化文書を複数の装置上に分散して格納する場合は、図５および図６のような木構造を分割した部分木であるフラグメントを、各装置上に分散して格納する。
【００５３】
図７は、複数の装置上の構造化文書記憶部１５０に格納された構造化文書のデータ構造の一例を示す説明図である。同図は、構造化文書１と構造化文書２を、図４に示すような構造情報の設定にしたがって、装置Ａ、装置Ｂ、装置Ｃの３台の装置に分散配置した状態を示している。
【００５４】
図４では、ＴＩＤ１〜８までの構造要素を装置Ａに格納することが設定されている。したがって、図７に示すように、構造化文書１のノードＩＤがｄ１−１（documentタグに対応）およびｈ１−１（headerタグに対応）の構造要素と、構造化文書２のノードＩＤがｄ２−１およびｈ２−１の構造要素とが装置Ａに格納される。
【００５５】
また、図４に示すように、ＴＩＤ＝２の構造要素の次弟はＴＩＤ＝９の構造要素（bodyタグに対応）であるが、ＴＩＤ＝９の構造要素の配置位置は装置Ｂであるため、他の装置に格納されていることを示す接続情報であるリンクを設定する。例えば、図７のリンク６０に示すように、装置名とノードＩＤとを対応づけたリンクを、ＴＩＤ＝９の構造要素に対応するノードの変わりに、ノードＩＤがｈ１−１のノードに設定する。
【００５６】
これにより、分散配置された構造要素間の親子関係、兄弟関係を保持することができる。すなわち、ノードＩＤがｈ１−１のノードの次弟が、装置Ｂに存在し、ノードＩＤがｂ１−１であることが分かる。
【００５７】
なお、リンクの形成方法は上記例に限られるものではなく、装置名の代わりに構造情報で管理されているＴＩＤを設定するように構成してもよい。各装置から検索装置１００（装置Ｘ）上の構造情報記憶部１４０を参照可能なので、対象ノードのＴＩＤに対応する配置位置を特定することができる。
【００５８】
索引情報記憶部１６０は、構造化文書の検索を高速化するための索引を格納するものである。図８は、索引情報記憶部１６０に格納された索引のデータ構造の一例を示す説明図である。
【００５９】
同図は、構造化文書内に格納されているテキストの検索を高速化するための索引の例を示している。同図に示すように、索引は、格納されている情報を表す要素値と、格納場所の表すノードＩＤとを対応づけている。
【００６０】
なお、索引のデータ構造はこれに限られるものではなく、構造化文書の検索を高速化するためのものであれば従来から用いられているあらゆる索引を適用することができる。また、構造化文書の構造要素の検索を高速化するための索引を格納するように構成してもよい。
【００６１】
なお、構造情報記憶部１４０、構造化文書記憶部１５０、索引情報記憶部１６０は、ＨＤＤ（Hard Disk Drive）、光ディスク、メモリカード、ＲＡＭ（Random Access Memory）などの一般的に利用されているあらゆる記憶媒体により構成することができる。
【００６２】
格納処理部１１０は、構造化文書の構造化文書記憶部１５０への格納処理を行うものであり、構造抽出部１１１と、文書分割部１１２と、文書送信部１１３と、文書登録部１１４と、索引登録部１１５とを備えている。
【００６３】
構造化文書の格納処理は２つのフェーズに分けられる。第１フェーズでは、入力された構造化文書から文書の構造情報を抽出して構造情報記憶部１４０に記憶するとともに、構造情報を参照して構造化文書を分割し、分割した構造化文書を各文書管理装置２００に送信する処理が実行される。第１フェーズは、構造抽出部１１１と、文書分割部１１２と、文書送信部１１３とにより実行される。
【００６４】
第２フェーズは、原則として各文書管理装置２００上の格納処理部１１０で実行されるものである。第２フェーズでは、分割された構造化文書を構造化文書記憶部１５０に格納するとともに、索引情報を索引情報記憶部１６０に格納する処理が実行される。第２フェーズは、文書登録部１１４と、索引登録部１１５とにより実行される。
【００６５】
構造抽出部１１１は、構造化文書から文書を構成する構造要素を抽出するものであり、ＸＭＬの場合は、例えばＤＯＭ（Document Object Model）にしたがってオブジェクトツリーを作成する方法などの従来から用いられているあらゆる方法を適用することができる。
【００６６】
また、構造抽出部１１１は、構造情報記憶部１４０に既に記憶されている構造情報に含まれない新規の構造情報を抽出した場合は、当該新規構造情報を構造情報記憶部１４０に格納する。
【００６７】
文書分割部１１２は、構造情報記憶部１４０に記憶されている構造情報を参照して入力された構造化文書を分割するものである。構造情報の詳細については後述する。
【００６８】
文書送信部１１３は、文書分割部１１２により分割された構造化文書を、構造情報記憶部１４０に記憶されている構造情報に含まれる配置位置の情報に従い、各文書管理装置２００に送信するものである。なお、分割した構造化文書を検索装置１００内の構造化文書記憶部１５０に記憶する場合、文書送信部１１３は、検索装置１００の文書登録部１１４に対して分割された構造化文書を送信する。
【００６９】
文書登録部１１４は、文書送信部１１３により送信された構造化文書を構造化文書記憶部１５０に格納するものである。
【００７０】
索引登録部１１５は、構造化文書の検索を高速化するための索引を生成し、生成した索引を索引情報記憶部１６０に記憶するものである。上述のように、索引のデータ構造は従来から用いられているあらゆる構造を適用できるため、適用する索引に応じたあらゆる索引の生成方法を利用することができる。
【００７１】
第２検索処理部１２０は、構造化文書記憶部１５０に格納された構造化文書の検索処理を行うものであり、データ通信部１２１と、検索部１２２と、ラベル管理部１２３と、第２結果データ取得部１２４を備えている。
【００７２】
データ通信部１２１は、クライアント４００または外部装置である各文書管理装置２００との間のデータの送受信を行うものであり、検索要求受信部１２１ａと、第２要求送信部１２１ｂと、部分文字列受信部１２１ｃと、第２結果送信部１２１ｄと、要求受信部１２１ｅとを備えている。
【００７３】
検索要求受信部１２１ａは、クライアント４００から送信された問合せデータを受信するものである。
【００７４】
第２要求送信部１２１ｂは、外部の装置上に格納された部分文字列が存在する場合に、当該外部の装置に対して部分文字列を取得するためのコマンドを送信するものである。
【００７５】
部分文字列受信部１２１ｃは、外部装置である各文書管理装置２００から送信された部分文字列を受信するものである。
【００７６】
第２結果送信部１２１ｄは、後述する結果データ生成部１２８が、部分文字列受信部１２１ｃにより受信された各部分文字列を結合して生成した結果データを、問合せ要求元のクライアント４００に対して送信するものである。
【００７７】
要求受信部１２１ｅは、外部の装置から送信された部分文字列を取得するためのコマンドを受信するものである。
【００７８】
検索部１２２は、クライアント４００から受信したＸＱｕｅｒｙ形式の問合せデータに合致する部分文字列のルートノードのノードＩＤの集合を求めるものである。
【００７９】
具体的には、検索部１２２は、まず問合せデータを構文解析して問合せグラフを作成する。次に、問合せグラフから問合せ処理に必要となる構造を抽出し、抽出した構造を利用して構造化文書記憶部１５０および索引情報記憶部１６０を参照し、問合せデータに合致する部分文字列のルートノードのノードＩＤを取得する。
【００８０】
図９は、問合せデータの一例を示す説明図である。同図に示す問合せデータは、“構造化文書ＤＢ「ｄｂ１」の階層木の中に「document」という構造要素以下に存在する「comment」タグの「name」属性の値が「田中」と等しい「document」の一覧を求めよ。”という条件を表している。
【００８１】
このような問合せデータにより、「document」タグの構造要素のノードＩＤが０個以上求められる。また、このような形式の問合せデータを利用すると、構造化文書単位や部分文書単位で結果データを取得すること、および、１個以上の部分文書を寄せ集めて新たな形式の構造化文書を生成することが可能である。
【００８２】
ラベル管理部１２３は、取得対象となる構造要素以下の部分文字列に関する頻度情報に従い、各フラグメントに該当する文字列データを管理するためのラベルのサイズを算出し、算出したサイズのラベルを作成するものである。ラベルサイズの算出方法、ラベルの形式については後述する。
【００８３】
第２結果データ取得部１２４は、構造情報記憶部１４０に格納された構造情報を参照し、ラベル管理部１２３が作成したラベルを使用して検索結果である結果データを取得するものである。具体的には、検索部１２２が取得したノードＩＤ下のノードが、自装置の構造化文書記憶部１５０に存在する場合は、当該構造化文書記憶部１５０から該当するノードを結果データとして取得する。また、第２結果データ取得部１２４は、検索部１２２が取得したノードＩＤ下に外部装置へのリンクが設定されている場合には、当該外部装置に対して結果データの取得を要求する処理を実行する。
【００８４】
分割配置設定部１３０は、利用者の指示により、構造化文書の分割対象となる構造要素、分割されたフラグメントが配置される位置に関する情報を設定し、構造情報記憶部１４０に記憶された構造情報を更新するものである。具体的には、分割配置設定部１３０は、図４に示すような構造情報のうち、配置位置とフラグメントルートフラグとを利用者が設定できるようにする。これにより、分割する構造要素をどのように分割して配置するかを利用者が指定できる。
【００８５】
文書管理装置２００ａ、２００ｂ、２００ｃは、構造化文書を分散して格納し、検索装置１００からの要求に応じて格納した構造化文書の検索処理を実行するものである。
【００８６】
文書管理装置２００ａ、２００ｂ、２００ｃはすべて同じ構成を備えている。以下では、必要がある場合を除いて、文書管理装置２００ａ、２００ｂ、２００ｃをまとめて単に文書管理装置２００という。なお、構造化文書検索システム１０は、少なくとも１つの文書管理装置２００を備えていればよい。また、文書管理装置２００の個数は３つに限られるものではない。
【００８７】
文書管理装置２００は、格納処理部１１０と、第１検索処理部２２０と、構造化文書記憶部１５０と、索引情報記憶部１６０とを備えている。
【００８８】
このように、文書管理装置２００は、分割配置設定部１３０と、構造情報記憶部１４０とを備えていない点が、検索装置１００と異なる。構造情報は各文書管理装置２００に分散配置された構造化文書全体の構造の情報を格納するものであり、検索装置１００内で一元管理しているからである。
【００８９】
また、文書管理装置２００は、第２検索処理部１２０に代わり第１検索処理部２２０が備えられている点が検索装置１００と異なる。
【００９０】
図１０は、第１検索処理部２２０の構成を示すブロック図である。同図に示すように、第１検索処理部２２０は、データ通信部２２１と、ラベル管理部１２３と、第１結果データ取得部２２４を備えている。
【００９１】
データ通信部２２１は、クライアント４００または外部装置である各文書管理装置２００との間のデータの送受信を行うものであり、第１要求送信部２２１ｂと、第１結果送信部２２１ｄと、要求受信部１２１ｅと、を備えている。
【００９２】
第１検索処理部２２０は、検索装置１００の第２検索処理部１２０と異なり、検索要求受信部１２１ａ、および部分文字列受信部１２１ｃを備えていない。これらは、クライアント４００との間のデータ送受信を行うものだからである。また、第１検索処理部２２０は、検索装置１００の第２検索処理部１２０と異なり検索部１２２を備えていない。検索部１２２は、クライアント４００から受信した問合せデータを参照して、各文書管理装置２００に部分文字列の取得を要求する前提となるルートノードのノードＩＤの取得を行うものだからである。
【００９３】
なお、文書管理装置２００がクライアント４００から問合せデータを受付け、検索結果を返すように構成する場合は、第１検索処理部２２０内に検索要求受信部１２１ａ、部分文字列受信部１２１ｃ、および検索部１２２を含むように構成してもよい。
【００９４】
また、第１要求送信部２２１ｂ、要求受信部１２１ｅ、ラベル管理部１２３、および第１結果データ取得部２２４の機能は、それぞれ検索装置１００の第２検索処理部１２０内の第２要求送信部１２１ｂ、要求受信部１２１ｅ、ラベル管理部１２３、および第２結果データ取得部１２４の機能と同様であるのでその説明を省略する。
【００９５】
第１結果送信部２２１ｄは、他の装置から受信した部分文字列取得のためのコマンドに応じて取得した部分文字列を、返信先の装置に送信するものである。返信先の装置は、取得のためのコマンド内で指定される。本実施の形態では、原則として検索装置１００が返信先の装置として指定される。
【００９６】
図１で、文書管理装置２００に含まれる格納処理部１１０、構造化文書記憶部１５０、および索引情報記憶部１６０の構成および機能は、検索装置１００と同様であるので、その説明を省略する。
【００９７】
次に、このように構成された本実施の形態にかかる構造化文書検索システム１０による構造化文書格納処理について説明する。構造化文書格納処理は、後述する構造化文書検索処理の前提として、構造化文書を分散して格納する処理である。
【００９８】
図１１は、本実施の形態における構造化文書格納処理の全体の流れを示すフローチャートである。
【００９９】
まず、構造抽出部１１１が、構造情報記憶部１４０に格納された構造情報を参照して、クライアント４００から入力された構造化文書の入力データから構造要素を抽出する（ステップＳ１１０１）。
【０１００】
この際、構造情報記憶部１４０に格納された構造情報に含まれない新規の構造要素が存在する場合は、当該新規の構造要素の情報を構造情報に追加し、構造情報記憶部１４０を更新する。
【０１０１】
次に、文書分割部１１２が、構造情報記憶部１４０の構造情報を参照し、構造情報のフラグメントルートフラグが１である構造要素を取得する（ステップＳ１１０２）。例えば、図５の構造化文書１を格納する場合、図４に示すような構造情報から、パス「/document」、「/document/body」、「/document/body/section/comment」の３つの構造要素を取得することができる。
【０１０２】
次に、文書分割部１１２は、取得した構造要素をルートとするフラグメントを生成する（ステップＳ１１０３）。次に、文書分割部１１２は、各フラグメントのルートとなる構造要素にユニークなノードＩＤを付与する（ステップＳ１１０４）。
【０１０３】
次に、文書分割部１１２は、ルートとなる構造要素と接続関係にある構造要素とのリンクを設定する（ステップＳ１１０５）。例えば、図５に示すような構造化文書１を格納する場合、装置Ｂに格納するフラグメントのルートノードであるノードＩＤ＝ｂ１−１のノードに対し、装置Ａに格納する構造要素であるノードＩＤ＝ｈ１−１のノードとのリンクを設定する。これにより、図７のリンク６０に示すようなリンクが設定される。
【０１０４】
次に、文書送信部１１３は、構造情報の配置位置で示される装置に各フラグメントを送信する（ステップＳ１１０６）。例えば、図４のような構造情報を前提とすると、ルートノードがノードＩＤ＝ｄ１−１のフラグメントは、装置Ａに送信される。同様に、ルートノードがノードＩＤ＝ｂ１−１のフラグメントは、装置Ｂに送信され、ルートノードがノードＩＤ＝ｃ１−１のフラグメントは、装置Ｃに送信される。
【０１０５】
この後、各文書管理装置２００（装置Ａ、装置Ｂ、装置Ｃ）では、以下の処理により構造化文書の格納処理が実行される。
【０１０６】
まず、文書登録部１１４が、送信されたフラグメントを構造化文書記憶部１５０に格納する（ステップＳ１１０７）。次に、索引登録部１１５が、送信されたフラグメントの索引を作成し、索引情報記憶部１６０に格納し（ステップＳ１１０８）、構造化文書格納処理を終了する。
【０１０７】
次に、このように構成された本実施の形態にかかる構造化文書検索システム１０による構造化文書検索処理について説明する。図１２は、本実施の形態における構造化文書検索処理の全体の流れを示すフローチャートである。
【０１０８】
まず、検索要求受信部１２１ａが、クライアント４００から送信された問合せデータを受信する（ステップＳ１２０１）。次に、検索部１２２が、問合わせデータで示された検索条件を満たすフラグメントのルートノードのノードＩＤ（以下、ルートノードＩＤという。）を取得する（ステップＳ１２０２）。
【０１０９】
例えば、図９に示すような問合せデータを受信した場合、図２に示すような構造化文書が条件を満たすため、図２に対応する図５の構造化文書１のルートノードＩＤ＝ｄ１−１が取得される。
【０１１０】
次に、ラベル管理部１２３が、検索結果のデータを管理するための情報であるラベルのサイズを算出する（ステップＳ１２０３）。ラベルは、原則として以下の（１）式により算出する。
ラベルサイズ（ｂｉｔ)
＝Σレベルｉのフラグメントのラベルサイズ
＝Σｌｏｇ2（ｍａｘ（レベルｉのフラグメントの最大フラグメント数）＋２）  ・・・（１）
【０１１１】
ここで、レベルとは、分割の深さを表す情報をいう。具体的には、レベルとは、取得するフラグメント全体のルートノードから、分割するフラグメントに達するまでの分割の回数を表す情報である。
【０１１２】
例えば、図５の構造化文書１を取得する場合、ノードＩＤ＝ｂ１−１をルートノードとするフラグメントは、構造化文書１を１回分割して生成されるものであるため、レベルは１となる。また、ノードＩＤ＝ｃ１−１をルートノードとするフラグメントは、構造化文書１を２回分割して生成されるものであるため、レベルは２となる。なお、構造化文書１全体のフラグメントのレベルは０である。
【０１１３】
また、ｍａｘとは、同じレベルのフラグメントが複数存在する場合に、算出した値の最大値を求めることを意味する。このように、各レベルで最大のラベルサイズを確保しておくことにより、同じレベルの複数の部分木の取得処理が同一のラベルで処理することができる。
【０１１４】
なお、２を加算するのは、まず起点に対して０を割り当てるために＋１のサイズが必要となり、さらにレベルｉのフラグメントはフラグメント数のレベル（ｉ＋１）のフラグメントで区切られるために、（フラグメント数＋１）のサイズが必要となるからである。
【０１１５】
図１３は、ラベルサイズの算出例を示した説明図である。同図は、図５に示すような構造化文書１の検索結果を管理するためのラベルのサイズを算出した例を示している。
【０１１６】
レベル０のフラグメント、すなわち、構造化文書１全体のフラグメントの最大フラグメント数は、図４に示すように、１である。したがって、レベル０のフラグメントのラベルサイズは、ｌｏｇ2（１＋２）＝２となる。同様に、レベル１および２のフラグメントのラベルサイズは、それぞれ３、１となる。
【０１１７】
ラベルは、このようにして算出されたサイズのｂｉｔデータを有する情報である。ラベルは、さらにレベル単位に分割され、各レベルで、後述する部分文字列取得処理により取得された部分文字列ごとに１つの値が割り当てられる。この際、構造化文書の木構造に従った順序で１を加算した値が割り当てられるため、各文書管理装置２００から部分文字列を受信した検索装置１００は、ラベルの値を参照して適切に部分文字列を並べ替え、結果データである構造化文書を生成することができる。
【０１１８】
ステップＳ１２０３でラベルサイズを算出した後、ラベル管理部１２３は、算出したサイズのラベルを作成し、初期値である０で初期化する（ステップＳ１２０４）。
【０１１９】
次に、第２結果データ取得部１２４は、ステップＳ１２０２で取得した、検索条件を満たすフラグメントのルートノードＩＤの構造要素が存在する文書管理装置２００の装置名を構造情報記憶部１４０から取得する（ステップＳ１２０５）。例えば、ルートノードＩＤ＝ｄ１−１のノードのシンボル名は「document」であるため、構造情報記憶部１４０から配置位置として装置Ａを取得することができる。
【０１２０】
次に、第２要求送信部１２１ｂは、取得した装置に対して、部分文字列取得処理を要求するパラメタを指定したコマンドを送信する（ステップＳ１２０６）。パラメタには、起点ラベル、レベル、取得対象ＩＤ、返信装置名が含まれる。
【０１２１】
起点ラベルとは、部分文字列取得処理で値を加算する基となるラベルをいう。原則として、現在処理しているラベル（以下、カレントラベルという。）が、次の部分文字列取得処理で用いる起点ラベルとなる。
【０１２２】
取得対象ＩＤとは、部分文字列取得処理で取得する部分文字列を表す木構造のルートノードＩＤをいう。
【０１２３】
返信装置名とは、文書管理装置２００が取得した部分文字列を返信する装置の装置名を表す情報である。原則として検索装置１００の名称（装置Ｘ）を設定するが、複数の検索装置１００を備える場合は、部分文字列取得処理を要求した検索装置１００の装置名を設定する。
【０１２４】
例えば、図５の構造化文書１を取得する場合、第２要求送信部１２１ｂは、装置Ａに対し、起点ラベル＝カレントラベル、レベル＝０、取得対象ＩＤ＝ｄ１−１、返信装置名＝装置Ｘが設定されたコマンドを送信する。
【０１２５】
ステップＳ１２０６で部分文字列取得処理を要求するコマンドを送信した後、コマンドを受信した文書管理装置２００で、部分文字列取得処理が実行される（ステップＳ１２０７）。部分文字列取得処理の詳細については後述する。
【０１２６】
部分文字列取得処理を要求するコマンドの送信後、検索装置１００の部分文字列受信部１２１ｃは、すべての部分文字列を受信するまで待機する（ステップＳ１２０８）。
【０１２７】
すべての部分文字列を受信した場合、第２結果データ取得部１２４は、ラベルの値の小さい順に受信した部分文字列を結合し、結果データを生成する（ステップＳ１２０９）。
【０１２８】
次に、第２結果送信部１２１ｄが、生成した結果データを問合せ要求元のクライアント４００に対して送信し（ステップＳ１２１０）、構造化文書検索処理を終了する。
【０１２９】
次に、ステップＳ１２０６の部分文字列取得処理について説明する。図１４は、本実施の形態における部分文字列取得処理の全体の流れを示すフローチャートである。
【０１３０】
まず、要求受信部１２１ｅが、部分文字列取得処理の要求元から、起点ラベル、レベル、取得対象ＩＤ、返信装置名を取得する（ステップＳ１４０１）。
【０１３１】
次に、ラベル管理部１２３が、取得した起点ラベル、レベルを、それぞれカレントラベル、カレントレベルに設定する（ステップＳ１４０２）。カレントレベルとは、現在処理している部分文字列に対応するフラグメントのレベルをいう。
【０１３２】
次に、ラベル管理部１２３が、カレントラベルのうち、カレントレベルに対応する部分のｂｉｔ列に１を加算する（ステップＳ１４０３）。
【０１３３】
次に、第１結果データ取得部２２４が、取得対象ＩＤ以下のノードを順に取得する（ステップＳ１４０４）。例えば、図７のように分散配置された構造化文書のうち、装置Ａに格納されたノードＩＤ＝ｄ１−１が取得対象ＩＤに指定された場合、ノードＩＤ＝ｄ１−１、ノードＩＤ＝ｈ１−１のように木構造の親子関係および兄弟関係を辿ってノードを順に取得する。
【０１３４】
次に、第１結果データ取得部２２４は、別の装置上に存在するノードへのリンクが取得されたか否かを判断する（ステップＳ１４０５）。例えば、図７のノードＩＤ＝ｈ１−１のノードの次のノードとして、同図に示すようなリンク６０が取得された場合、別の装置上に存在するノードへのリンクが取得されたと判断する。
【０１３５】
別の装置上に存在するノードへのリンクが取得された場合（ステップＳ１４０５：ＹＥＳ）、第１結果データ取得部２２４は、ここまでに取得したノードの文字列とカレントラベルとを対応づけ、結果データに追加する（ステップＳ１４０６）。なお、実際には取得した文字列の文字列バッファ内のオフセットの情報を、カレントラベルと対応づけて結果データに追加する。
【０１３６】
次に、第１要求送信部２２１ｂは、リンクで指定された別の装置に対し、部分文字列取得処理を要求するパラメタを指定したコマンドを送信する（ステップＳ１４０７）。ここでは、起点ラベル＝カレントラベル、レベル＝カレントレベル＋１、取得対象ＩＤ＝リンクに指定されたノードＩＤ、返信装置名＝検索装置１００の装置名（装置Ｘ）を指定する。
【０１３７】
部分文字列取得処理の要求を受信した別の装置上では、部分文字列取得処理が再帰的に実行される（ステップＳ１４０８）。
【０１３８】
ステップＳ１４０５で、別の装置上に存在するノードへのリンクが取得されなかった場合は（ステップＳ１４０５：ＮＯ）、第１結果データ取得部２２４は、すべてのノードを処理したか否かを判断し（ステップＳ１４０９）、すべてのノードを処理していない場合は（ステップＳ１４０９：ＮＯ）、カレントレベルに１加算して処理を繰り返す（ステップＳ１４０３）。
【０１３９】
すべてのノードを処理した場合（ステップＳ１４０９：ＹＥＳ）、第１結果データ取得部２２４は、ここまでに取得したノードの文字列とカレントラベルとを対応づけ、結果データに追加する（ステップＳ１４１０）。
【０１４０】
次に、第１結果送信部２２１ｄは、返信装置に対して結果データを送信し（ステップＳ１４１１）、部分文字列取得処理を終了する。
【０１４１】
次に、本実施の形態にかかる構造化文書検索システム１０による構造化文書検索処理の具体例について説明する。図１５、図１６は、構造化文書検索処理において各装置間で送受信されるコマンドの一例を示す説明図である。また、図１７、図１８、図１９は、構造化文書検索処理において各装置で検索される検索結果の一例を示す説明図である。
【０１４２】
以下では、図５および図６に示すような構造化文書１および構造化文書２が、図７に示すように各装置に分散して格納されている状態で、図４の構造情報を用いてノードＩＤ＝ｄ１−１であるノード以下の結果データを取得する場合を例として説明する。
【０１４３】
まず、検索装置１００のラベル管理部１２３では、図１３に示すようなラベルサイズが６ｂｉｔのラベルを作成し、０で初期化する（ステップＳ１２０４）。ノードＩＤ＝ｄ１−１のノードは装置Ａに格納されているため、図１５のコマンド２０に示すようなコマンドを装置Ａに対して送信する（ステップＳ１２０６）。
【０１４４】
装置Ａ上で部分文字列取得処理が実行され（ステップＳ１２０７）、カレントレベルが０であることから、レベル０に対応する部分のｂｉｔ列に１を加算する（ステップＳ１４０３）。これにより、カレントラベルは状態３０に示すような値となる。
【０１４５】
この後、ノードＩＤ＝ｄ１−１のノード以下のノードを順に読出し、図１７に示す文字列４０が取得される（ステップＳ１４０４）。さらにノードを読み出すと、別の装置Ｂに存在するノードＩＤ＝ｂ１−１に対するリンクが取得される（ステップＳ１４０５：ＹＥＳ）。
【０１４６】
このため、図１７に示すように、文字列４０を示すオフセットと、カレントラベルである“０１０００００”とを結果データに追加する（ステップＳ１４０６）。
【０１４７】
なお、結果データは、結果表と文字列バッファとから成る。図１７に示す例では、結果データは２つの文字列から構成され、それぞれ「０１０００００」、「１００００００」というラベルを有する。ラベルと文字列とは、文字列バッファ内のオフセットで対応づけられる。前者のオフセットは「offset0」、後者のオフセットは「offset1」である。
【０１４８】
この後、リンクに指定された別の装置Ｂに対し、図１５に示すようなコマンド２１を送信する（ステップＳ１４０７）。
【０１４９】
すべてのノードを処理していないため（ステップＳ１４０９：ＮＯ）、ｂｉｔ列に１を加算してカレントラベルを状態３１のように更新した後（ステップＳ１４０３）、第１結果データ取得部２２４は、文字列４１を取得する（ステップＳ１４０４）。
【０１５０】
その結果、すべてのノードが処理されたため（ステップＳ１４０９：ＹＥＳ）、結果データに状態３１のカレントラベルと文字列４１とを追加し（ステップＳ１４１０）、返信装置Ｘに対し、結果データを送信する（ステップＳ１４１１）。
【０１５１】
このように、装置Ａ上では、装置Ｂに対して送信するコマンド２１の前後の２つのカレントラベルに対応してそれぞれ図１７に示すような２つの部分文字列が取得される。
【０１５２】
同様の処理で、装置Ｂでは図１６に示すようなコマンド２２、コマンド２３、コマンド２４を装置Ｃに送信するとともに、各コマンドの送信前後に設定される４つのカレントラベルに対応してそれぞれ図１８に示すような４つの部分文字列が取得される。
【０１５３】
また、装置Ｃでは、装置Ｂから送信された３つのコマンドに対応して、それぞれ３回の部分文字列取得処理が実行され、図１９に示すような３つの部分文字列が取得される。
【０１５４】
このようにして取得された図１７、図１８、図１９の各部分文字列をラベルの値の小さい順に並べると、取得結果となるべき図２と同じ文字列が形成される。
【０１５５】
なお、各装置から得られる部分文字列群はラベルの値の小さい順に並んでいるので、全ての部分文字列をラベルの値の小さい順に並べるコストは小さい。また、結果データ取得の起点となる装置Ｘに転送される部分文字列のサイズは従来と変わらない。したがって、装置Ｘの処理負担が過大となることはないと考えられる。
【０１５６】
次に、従来技術と比較した本実施の形態にかかる構造化文書検索システム１０の利点について説明する。図２０は、従来の方法により検索処理を実行した際に送信されるデータの一例を示す説明図である。また、図２１は、図２０と同じ条件の検索処理を実行した際に送信されるデータの一例を示す説明図である。
【０１５７】
ここでは、「body」タグ以下を除いた「document」タグ以下の部分木、「comment」タグ以下を除いた「body」タグ以下の部分木、「comment」タグ部分が、それぞれ1600Byte、4000Byte、160Byteのデータサイズであると仮定する。
【０１５８】
従来の方法では、各装置で取得された部分文字列は、隣接するレベルの装置に転送される。例えば、装置Ｃで取得された「comment」タグの部分文字列は、装置Ｂに転送される。また、装置Ｂは、装置Ｂ上で取得された部分文字列に、装置Ｃから転送された部分文字列を結合し、装置Ａに転送する。このように、各装置で取得された部分文字列が順次結合され、最終的に装置Ｘに検索結果である部分文字列が転送される。
【０１５９】
したがって、図２０に示すように、装置Ｃから装置Ｂへのデータ転送量は（160+480+160)Byte=800Byte、装置Ｂから装置Ａへのデータ転送量は4800Byte、装置Ａから装置Ｘへのデータ転送量は6400Byteとなり、合計12000Byteとなる。
【０１６０】
一方、本実施の形態の方法では、各装置で取得された部分文字列は、部分文字列取得要求元である装置Ｘに直接転送される。したがって、装置Ａから装置Ｘへのデータ転送量は1600Byte、装置Ｂから装置Ｘへのデータ転送量は4000Byte、装置Ｃから装置Ｘへのデータ転送量は800Byteとなり、合計6400Byteとなる。
【０１６１】
したがって、従来の方法に比較すると5600Byteのデータ転送量の削減が実現されている。なお、レベルが大きいフラグメントのデータサイズが大きいほど、データ転送量削減の効果は大きくなる。
【０１６２】
また、各装置上で部分文字列を結合する際に行われる文字列のコピー処理も不要となるため、検索処理全体のスループットが向上する。
【０１６３】
さらに、返信装置を特定の装置に固定化することができる場合は、返信装置に対する返信用のネットワーク回線を、専用回線かつ単方向通信とするように構成してもよい。これにより、双方向通信に比べ、より高速なデータ転送を実現できる。
【０１６４】
このように、本実施の形態にかかる構造化文書検索システムでは、複数の文書管理装置に分散配置された部分文書の検索結果を、各文書管理装置から検索要求を行う検索装置に直接転送することができる。このため、重複したデータ転送の発生を低減し、高速な検索を実現することができる。
【０１６５】
また、各文書管理装置で検索結果の中継を行わないため、必要以上のデータコピーが発生せず、より高速な検索が可能となる。また、結果データを必要とする装置を固定化できる場合には、専用回線と単方向のデータ転送を適用することにより、双方向のデータ転送に比べ高速な転送を実現することができる。この結果、高速な検索が実現可能となる。
【産業上の利用可能性】
【０１６６】
以上のように、本発明にかかる構造化文書検索システムおよび構造化文書検索方法は、ＸＭＬなどの構造化文書を複数の装置に分散配置して管理するシステムに適している。
【図面の簡単な説明】
【０１６７】
【図１】本実施の形態にかかる構造化文書検索システムの構成を示すブロック図である。
【図２】ＸＭＬ形式の構造化文書の一例を示した説明図である。
【図３】構造化文書から抽出された構造情報の一例を示す説明図である。
【図４】構造情報記憶部に格納された構造情報のデータ構造の一例を示す説明図である。
【図５】構造化文書記憶部に格納された構造化文書のデータ構造の一例を示す説明図である。
【図６】構造化文書記憶部に格納された構造化文書のデータ構造の一例を示す説明図である。
【図７】複数の装置上の構造化文書記憶部に格納された構造化文書のデータ構造の一例を示す説明図である。
【図８】索引情報記憶部に格納された索引のデータ構造の一例を示す説明図である。
【図９】問合せデータの一例を示す説明図である。
【図１０】第１検索処理部の構成を示すブロック図である。
【図１１】本実施の形態における構造化文書格納処理の全体の流れを示すフローチャートである。
【図１２】本実施の形態における構造化文書検索処理の全体の流れを示すフローチャートである。
【図１３】ラベルサイズの算出例を示した説明図である。
【図１４】本実施の形態における部分文字列取得処理の全体の流れを示すフローチャートである。
【図１５】構造化文書検索処理において各装置間で送受信されるコマンドの一例を示す説明図である。
【図１６】構造化文書検索処理において各装置間で送受信されるコマンドの一例を示す説明図である。
【図１７】構造化文書検索処理において各装置で検索される検索結果の一例を示す説明図である。
【図１８】構造化文書検索処理において各装置で検索される検索結果の一例を示す説明図である。
【図１９】構造化文書検索処理において各装置で検索される検索結果の一例を示す説明図である。
【図２０】従来の方法により検索処理を実行した際に送信されるデータの一例を示す説明図である。
【図２１】検索処理を実行した際に送信されるデータの一例を示す説明図である。
【符号の説明】
【０１６８】
１０  構造化文書検索システム
１００  検索装置
１１０  格納処理部
１１１  構造抽出部
１１２  文書分割部
１１３  文書送信部
１１４  文書登録部
１１５  索引登録部
１２０  第２検索処理部
１２１  データ通信部
１２１ａ  検索要求受信部
１２１ｂ  第２要求送信部
１２１ｃ  部分文字列受信部
１２１ｄ  第２結果送信部
１２１ｅ  要求受信部
１２２  検索部
１２３  ラベル管理部
１２４  第２結果データ取得部
１３０  分割配置設定部
１４０  構造情報記憶部
１５０  構造化文書記憶部
１６０  索引情報記憶部
２００  文書管理装置
２２０  第１検索処理部
２２１  データ通信部
２２１ｂ  第１要求送信部
２２１ｄ  第１結果送信部
２２４  第１結果データ取得部
３００  ネットワーク
４００  クライアント
７０１、７０２、７０３  エレメント
２０、２１、２２、２３、２４  コマンド
３０、３１  状態
４０、４１  文字列
６０  リンク
【図１】
0004489029.tif 000002
【図２】
0004489029.tif 000003
【図３】
0004489029.tif 000004
【図４】
0004489029.tif 000005
【図５】
0004489029.tif 000006
【図６】
0004489029.tif 000007
【図７】
0004489029.tif 000008
【図８】
0004489029.tif 000009
【図９】
0004489029.tif 000010
【図１０】
0004489029.tif 000011
【図１１】
0004489029.tif 000012
【図１２】
0004489029.tif 000013
【図１３】
0004489029.tif 000014
【図１４】
0004489029.tif 000015
【図１５】
0004489029.tif 000016
【図１６】
0004489029.tif 000017
【図１７】
0004489029.tif 000018
【図１８】
0004489029.tif 000019
【図１９】
0004489029.tif 000020
【図２０】
0004489029.tif 000021
【図２１】
0004489029.tif 000022