(57)【要約】【課題】１つの構造化データを並列解析できるように、構造化データを符号化する。【解決手段】構造化データを、上位−下位関係を有する１以上の要素で構成される、複数の部分データに分割する。部分データのそれぞれについて、部分データに含まれる要素の解釈に用いられる補助情報を、構造化データから抽出する。部分データのそれぞれについて、部分データの最上位要素が接続している他の部分データ中の要素を特定する位置情報を、構造化データから抽出する。複数の部分データを含む構造化データを符号化する。符号化された構造化データと、補助情報と、位置情報とを出力する。【選択図】図３
2013145472.tif 000002
【特許請求の範囲】
【請求項１】
木構造を構成する複数の要素を含む構造化データを符号化する情報処理装置であって、
前記構造化データを、上位−下位関係を有する１以上の要素で構成される、複数の部分データに分割する分割手段と、
前記部分データのそれぞれについて、該部分データに含まれる要素の解釈に用いられる補助情報を、前記構造化データから抽出する第１の抽出手段と、
前記部分データのそれぞれについて、該部分データの最上位要素が接続している他の部分データ中の要素を特定する位置情報を、前記構造化データから抽出する第２の抽出手段と、
前記複数の部分データを含む前記構造化データを符号化する符号化手段と、
前記符号化された構造化データと、前記補助情報と、前記位置情報とを出力する出力手段と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記複数の要素のそれぞれについて処理負荷を算出する算出手段をさらに有し、
前記分割手段は、それぞれの前記部分データを構成する要素についての前記処理負荷の合計が所定の上限値を超えないように、前記構造化データを前記複数の部分データに分割することを特徴とする、請求項１に記載の情報処理装置。
【請求項３】
前記要素が含む値の数若しくはデータ量と、前記要素が含む属性の数若しくはデータ量とのうちの少なくとも一方に従って前記処理負荷が算出されることを特徴とする、請求項２に記載の情報処理装置。
【請求項４】
前記符号化手段は、符号化規則を学習しながら前記構造化データを符号化し、
前記部分データを符号化する際に符号化規則の学習が発生しないと判定した場合に、該部分データを共通の符号化規則に従って符号化する第１の符号化手段と、
前記部分データを符号化する際に符号化規則の学習が発生すると判定した場合に、該部分データを前記共通の符号化規則とは独立した符号化規則に従って符号化する第２の符号化手段と、
を備えることを特徴とする、請求項１乃至３の何れか１項に記載の情報処理装置。
【請求項５】
前記符号化手段は、符号化規則を学習しながら前記構造化データを符号化し、前記要素を符号化する際に符号化規則の学習が発生すると判定した場合に、該要素を符号化する際に用いた符号化規則を該要素と関連付けて記録し、
前記出力手段はさらに前記要素と関連付けて記録された符号化規則を出力することを特徴とする、請求項１乃至３の何れか１項に記載の情報処理装置。
【請求項６】
前記出力手段がさらに、前記部分データのそれぞれについて、前記符号化された構造化データ中におけるデータ位置を特定する情報を出力することを特徴とする、請求項１乃至５の何れか１項に記載の情報処理装置。
【請求項７】
前記部分データについての前記補助情報は、前記構造化データにおいて当該部分データに含まれる要素よりも上位の要素によって規定された名前空間宣言を含むことを特徴とする、請求項１乃至６の何れか１項に記載の情報処理装置。
【請求項８】
前記構造化データはＸＭＬデータであって前記符号化手段はＥＸＩ符号化を行い、
前記部分データについての前記補助情報は、当該部分データに適用されるgrammer IDを含むことを特徴とする、請求項１乃至７の何れか１項に記載の情報処理装置。
【請求項９】
木構造を構成する複数の要素を含む構造化データを符号化することによって得られた符号化データを復号及び解析して前記木構造を再現する情報処理装置であって、
前記構造化データは、上位−下位関係を有する１以上の要素で構成される複数の部分データによって構成され、
前記符号化データは、前記複数の部分データのそれぞれに対応する符号化部分データを含み、
前記情報処理装置は、
前記複数の符号化部分データを含む前記符号化データを取得する第１の取得手段と、
前記部分データのそれぞれについて、前記構造化データにおいて該部分データに含まれる要素よりも上位の要素によって規定され、該部分データに含まれる要素の解釈に用いられる補助情報を取得する第２の取得手段と、
前記部分データのそれぞれについて、最上位要素が接続している他の部分データ中の要素を特定する位置情報を取得する第３の取得手段と、
前記符号化部分データと、当該符号化部分データに対応する前記補助情報とを用いて、前記符号化部分データの復号及び前記上位−下位関係の再現を行う複数の解析手段と、
前記符号化部分データのそれぞれを前記複数の解析手段のうち何れかに解析させ、前記位置情報に従って当該解析の結果から前記木構造を再現する制御手段と、
を有することを特徴とする情報処理装置。
【請求項１０】
木構造を構成する複数の要素を含む構造化データを符号化する情報処理装置が行う情報処理方法であって、
分割手段が、前記構造化データを、上位−下位関係を有する１以上の要素で構成される、複数の部分データに分割する分割工程と、
第１の抽出手段が、前記部分データのそれぞれについて、前記構造化データにおいて該部分データに含まれる要素よりも上位の要素によって規定され、該部分データに含まれる要素の解釈に用いられる補助情報を、前記構造化データから抽出する第１の抽出工程と、
第２の抽出手段が、前記部分データのそれぞれについて、該部分データの最上位要素が接続している他の部分データ中の要素を特定する位置情報を、前記構造化データから抽出する第２の抽出工程と、
符号化手段が、前記複数の部分データを含む前記構造化データを符号化する符号化工程と、
出力手段が、前記符号化された構造化データと、前記補助情報と、前記位置情報とを出力する出力工程と、
を含むことを特徴とする情報処理方法。
【請求項１１】
コンピュータを、請求項１乃至９の何れか１項に記載の情報処理装置の各手段として機能させるための、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、符号化文書を生成するための情報処理技術に関する。
【背景技術】
【０００２】
従来、コンピュータシステムにおける代表的なデータ表現形式の一つとして、Ｗ３Ｃで標準化されたＸＭＬのような構造化データがある。ＸＭＬのような構造化データにおいては、データ間の関係は、要素や属性といった構造情報を用いて記述される。よって、構造化データを処理するには、まず構造情報を解析しなければならない。この構造情報の解析には一般的に時間がかかるため、高速化することが求められている。
【０００３】
高速化技術の一つとして、Ｗ３Ｃで標準化中のＥＸＩ（非特許文献１参照）という仕様がある。ＥＸＩでは、従来のＸＭＬデータを文字ではなくビット列で表現する。また、繰り返し現れるデータをより短い符号で置き換えることにより、冗長性の低下及び処理の高速化を実現している。
【０００４】
さらに、データベースの分野においては分散処理技術を使った高速化が行われている。具体的には、ＸＭＬデータの検索要求又はＸＭＬデータの更新要求が、複数のマシンへと分散される。ＸＭＬデータファイル単位で要求を並列処理することにより、高速化が実現される。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Efficient XML Interchange (EXI) Format 1.0, W3C Recommendation 10 March 2011. Ｗ３Ｃ、２０１１年３月１０日 (http://www.w3.org/TR/exi)
【発明の概要】
【発明が解決しようとする課題】
【０００６】
アドレス帳のような大量のデータが記述されたＸＭＬデータを処理する場合や、画像データなどのサイズの大きなデータを含むＸＭＬデータを処理する場合、ＥＸＩによる高速化だけでは十分な処理速度が得られないことがありうる。
【０００７】
また、従来の方法によれば、ＸＭＬデータのような構造化データの解析のためには、データの先頭から順番に情報を処理する必要があった。このため、上述のようにＸＭＬデータを並列処理する場合には、データファイル単位での並列処理が行われていた。しかしながら従来のデータファイル単位の並列処理技術では、１つの大きい構造化データの解析を高速化することはできなかった。
【０００８】
本発明は、１つの構造化データを並列解析できるように、構造化データを符号化することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の目的を達成するために、例えば、本発明の情報処理装置は以下の構成を備える。すなわち、
木構造を構成する複数の要素を含む構造化データを符号化する情報処理装置であって、
前記構造化データを、上位−下位関係を有する１以上の要素で構成される、複数の部分データに分割する分割手段と、
前記部分データのそれぞれについて、該部分データに含まれる要素の解釈に用いられる補助情報を、前記構造化データから抽出する第１の抽出手段と、
前記部分データのそれぞれについて、該部分データの最上位要素が接続している他の部分データ中の要素を特定する位置情報を、前記構造化データから抽出する第２の抽出手段と、
前記複数の部分データを含む前記構造化データを符号化する符号化手段と、
前記符号化された構造化データと、前記補助情報と、前記位置情報とを出力する出力手段と、
を備えることを特徴とする情報処理装置。
【発明の効果】
【００１０】
本発明は、１つの構造化データを並列解析できるように、構造化データを符号化できる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施例に係る情報処理装置の構成を示すブロック図。
【図２】実施例１で処理される構造化データを示す図。
【図３】実施例１に係る処理のフローチャート。
【図４】実施例１で算出される処理負荷を示す図。
【図５】実施例１に係るステップＳ３０２のフローチャート。
【図６】実施例１に係るステップＳ３０３のフローチャート。
【図７】実施例１に係るステップＳ６０３のフローチャート。
【図８】実施例１に係る木構造のグループ化を説明する図。
【図９】実施例１に係る処理識別子の保存を示す図。
【図１０】名前空間宣言を説明する図。
【図１１】実施例１に係るステップＳ３０４のフローチャート。
【図１２】実施例１に係る処理制御情報を示す図。
【図１３】実施例２に係る符号化を説明する図。
【図１４】実施例２に係るステップＳ３０４のフローチャート。
【図１５】実施例２に係る処理制御情報を示す図。
【図１６】実施例２に係る処理制御情報の格納例を示す図。
【図１７】実施例３に係る符号化を説明する図。
【図１８】実施例３に係るステップＳ３０４のフローチャート。
【図１９】実施例３に係る処理制御情報を示す図。
【図２０】実施例４に係る情報処理装置の機能構成を示すブロック図。
【図２１】実施例４に係る処理制御情報を示す図。
【図２２】実施例４に係る処理のフローチャート。
【図２３】実施例４に係る処理のフローチャート。
【図２４】本発明の実施例に係る情報処理装置の機能構成を示すブロック図。
【図２５】実施例４に係る情報処理装置の構成を示すブロック図。
【発明を実施するための形態】
【００１２】
以下、本発明の実施例を図面に基づいて説明する。ただし、本発明の範囲は以下の実施例に限定されるものではない。
【実施例１】
【００１３】
実施例１に係る情報処理装置１００は、構造化データ（構造化文書）を符号化する装置である。本実施例においては特に、木構造を構成する複数の要素を含む構造化データが符号化される。特に情報処理装置１００は、復号時に並列解析処理が可能となるように、図２に示すＸＭＬデータ（構造化データ）を符号化する。本実施例の方法によれば、１つの構造化データ（例えば、木構造を有する複数の要素で構成されるデータ）を並列に解析することが可能となる。
【００１４】
情報処理装置１００について、図１のブロック図を参照して説明する。本実施例に係る情報処理装置は、図１に示されるコンピュータを用いて実現される。情報処理装置１００は単一のコンピュータ装置で実現されてもよいし、機能の一部をそれぞれ割り当てられた複数のコンピュータ装置によって実現されてもよい。複数のコンピュータ装置を用いて情報処理装置１００を実現する場合、これらのコンピュータ装置は、例えばローカルエリアネットワーク（ＬＡＮ）などを介して情報をやりとりする。
【００１５】
図１に示すように、情報処理装置１００は、ＣＰＵ１０１と、ＲＯＭ１０２と、ＲＡＭ１０３と、外部記憶装置１０４と、入力インタフェース１０５と、ネットワークインタフェース１０６と、システムバス１０７とを備える。ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１０１は、情報処理装置１００全体を制御する。ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１０２は、変更を必要としないプログラムやパラメタなどを格納する。ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１０３は、外部装置などから供給されるプログラムやデータなどを一時的に記憶する。外部記憶装置１０４は、データを記憶可能な装置であって、ハードディスクなどでありうる。また外部記憶装置１０４は、メモリカード、フレキシブルディスク（ＦＤ）、コンパクトディスク（ＣＤ）などの光ディスク、磁気カード、光カード、ＩＣカード、などへのアクセスを可能とするインタフェースであってもよい。
【００１６】
入力インタフェース１０５は、ポインティングデバイスやキーボードなどの入力デバイスとのインタフェースである。ネットワークインタフェース１０６は、インターネットなどのネットワーク回線とのインタフェースである。システムバス１０７は、各ユニット１０１〜１０６間の通信を可能とする。本実施例に係る処理は、以下のようにして実現できる。すなわち、処理手順を示すコンピュータプログラムを記録している記録媒体（例えばＲＯＭ１０２又は外部記憶装置１０４）から、このプログラムをＲＡＭ１０３へと読み出し、このプログラムに従ってＣＰＵ１０１が制御を行う。
【００１７】
図２４は、本実施例に係る情報処理装置１００の機能ブロック図である。本実施例に係る情報処理装置１００は、設定部２４１０と、負荷算出部２４２０と、分割部２４３０と、抽出部２４４０とを有する。これらの各部の機能は、上述のようにプログラムに従ってＣＰＵ１０１が制御を行うことによって実現できる。もっとも、各機能２４１０〜２４４０のうちの少なくとも１つは、専用のハードウェアによって実現されてもよい。
【００１８】
以下では一例として、図２に示すＸＭＬデータを、情報処理装置１００によって符号化する場合について説明する。図２にはアドレス帳のデータが示されている。このデータには８人のアドレスが含まれており、１つのエントリは１人のアドレスに対応する。説明のために図２のデータには８人のアドレスのみが含まれているが、実際のデータにはより多くのアドレスが含まれていることが多い。多くのアドレスが含まれている場合、このＸＭＬデータを構文解析することには多くの処理を要する。一方でこのようなＸＭＬデータを並列解析することにより、より短い時間で解析を行うことができる。
【００１９】
ステップＳ３０１において設定部２４１０は、構文解析の負荷を算出するための基礎負荷値を設定する。本実施例においては、ＸＭＬデータが含むそれぞれの構成要素に対して基礎負荷値が割り当てられ、割り当てられた基礎負荷値を合計することによって負荷が算出される。本実施例においては、要素の基礎負荷値を１つあたり１００、属性の基礎負荷値を１つあたり５０、属性値の基礎負荷値を１バイトあたり１０、名前空間宣言の基礎負荷値を１つあたり１００、値の基礎負荷値を１バイトあたり１０とする。これらの基礎負荷値にしたがって、ＸＭＬデータの構文解析の処理負荷を算出する。このような初期負荷値は、設定部２４１０がメモリ（不図示）から読み出してもよいし、設定部２４１０が入力インタフェース１０５を介してユーザから取得してもよい。これらの初期負荷値は、経験に基づいて予め設定されたものであってもよいし、構文解析を行う装置の処理能力に応じて設定されたものであってもよい。
【００２０】
本実施例においては以上のように要素の数、属性の数、名前空間宣言の数、及び値のデータ量に応じて負荷が算出される。しかしながら、負荷の算出方法はこの方法に限られない。例えば、要素と属性との組み合わせに対して基礎負荷値が割り当てられてもよい。また、要素名及び属性名の長さに応じた基礎負荷値が割り当てられてもよい。さらに、属性の有無に応じて基礎負荷値が割り当てられてもよい。
【００２１】
ステップＳ３０２において負荷算出部２４２０は、ステップＳ３０１で設定された基礎負荷値に応じて、ＸＭＬデータの各構造についての処理負荷を算出する。負荷算出部２４２０は、算出した処理負荷を図４のような木構造として保存する。図４の木構造は、図２に示すＸＭＬデータの構造に準じている。すなわち、木構造の各ノードはＸＭＬデータの各要素に対応し、ノードの親子関係はＸＭＬデータにおける要素の親子関係に対応している。ステップＳ３０２で作成される木構造は図４のものには限られず、例えばＸＭＬデータ内の属性又は値を１つのノードとしてもよい。
【００２２】
負荷算出部２４２０は、要素のそれぞれについて処理負荷を算出する。それぞれの要素についての処理負荷の算出方法の具体例を以下に挙げる。例えば、要素が含む値の数若しくはデータ量と、要素が含む属性の数若しくはデータ量とのうちの少なくとも一方に従って処理負荷を算出する方法が挙げられる。以下では一例として、要素が含む値のデータ量と、要素が含む属性の数及びデータ量とに従って、処理負荷を算出する。例えば"mail1@example.org"を値として有する＜addr＞要素は、１７バイトの値を持つ。したがって、この＜addr＞要素の処理負荷は、１（要素の数）×１００（要素の基礎負荷値）＋１７（値のバイト数）×１０（値の基礎負荷値）＝２７０となる。
【００２３】
また、値として"name1"を有し、属性として"development"属性値を有する＜name＞要素の処理負荷は以下のようになる。すなわち、１（要素の数）×１００（要素の基礎負荷値）＋１（属性の数）×５０（属性の基礎負荷値）＋１１（属性値のバイト数）×１０（属性値の基礎負荷値）＋５（値のバイト数）×１０（値の基礎負荷値）＝３１０である。
【００２４】
さらに、値として"name2"を有し、属性として"sales"属性値を有する＜name＞要素の処理負荷は以下のようになる。すなわち、１（要素の数）×１００（要素の基礎負荷値）＋１（属性の数）×５０（属性の基礎負荷値）＋５（属性値のバイト数）×１０（属性値の基礎負荷値）＋５（値のバイト数）×１０（値の基礎負荷値）＝２５０である。
【００２５】
また、子要素を有する親要素の処理負荷は、親要素についての処理負荷と、子要素についての処理負荷を合計することによって求められる。例えば、図２のＸＭＬデータのうち最初の＜entry＞要素の処理負荷は、以下のように求められる。｛１（要素の数）×１００（要素の基礎負荷値）｝（親要素についての処理負荷）＋３１０（＜name＞子要素の処理負荷）＋２７０（＜addr＞子要素の処理負荷）＝６８０
【００２６】
図４の木構造が属性又は値に対応するノードを有する場合には、要素、属性、及び値についての処理負荷を別々に計算してもよい。こうして算出された処理負荷は、図４に示した木構造の各ノードに保存する。
【００２７】
ステップＳ３０２における処理について、図５のフローチャートを参照してより詳しく説明する。図５のフローチャートを開始する際には、最上位要素が処理対象として選択されている。図２のＸＭＬデータを処理する場合、＜import＞要素が処理対象として選択されている。なお、最上位要素が２つ以上存在する場合は、それぞれの最上位要素を処理対象として図５に示される処理を繰り返せばよい。
【００２８】
ステップＳ５０１において負荷算出部２４２０は、未処理の下位要素、すなわち処理負荷が算出されていない下位要素が存在するか否かを判定する。存在する場合、処理はステップＳ５０２に進む。存在しない場合、処理はステップＳ５０３に進む。ステップＳ５０２において負荷算出部２４２０は、未処理の下位要素のうち１つを処理対象として選択する。その後処理はステップＳ５０１に戻る。
【００２９】
ステップＳ５０３において負荷算出部２４２０は、上述のように、処理対象の要素についての処理負荷を算出する。ステップＳ５０４において負荷算出部２４２０は、処理対象の要素が最上位要素であるか否かを判定する。最上位要素である場合、図５の処理は終了する。最上位要素ではない場合、処理はステップＳ５０５に進む。ステップＳ５０５において負荷算出部２４２０は、処理対象の要素の上位要素を処理対象として選択する。
【００３０】
ステップＳ３０２において木構造が作成された後、ステップＳ３０３において分割部２４３０は、作成された木構造を参照してＸＭＬデータを複数のＸＭＬデータに分割する。例えば分割部２４３０は、ＸＭＬデータを、上位−下位関係を有する１以上の要素で構成される、複数の部分データに分割することができる。以下に、ステップＳ３０３における分割処理について、図６のフローチャートを参照して説明する。
【００３１】
ステップＳ６００において分割部２４３０は、閾値Ａを決定する。閾値Ａは処理負荷の上限値であり、ある要素についての処理負荷が閾値Ａを超えている場合に木構造を分割する。このように分割部２４３０は、それぞれの部分データを構成する要素についての処理負荷の合計が所定の上限値を超えないように分割を行う。閾値Ａは、分割部２４３０がメモリ（不図示）から読み出してもよいし、分割部２４３０が入力インタフェース１０５を介してユーザから取得してもよい。閾値Ａは、経験に基づいて予め設定されたものであってもよいし、構文解析を行う装置の処理能力に応じて設定されたものであってもよい。一般的には閾値Ａは、並列処理を行う際に発生するタスクの割り当てや、同期処理などの、オーバヘッドを考慮して決定される。本実施例においては、閾値Ａは２０００であるものとする。
【００３２】
ステップＳ６０１において分割部２４３０は、ステップＳ３０２で作成された木構造のルートノード（最上位ノード）について、処理負荷が閾値Ａを超えているかどうかを判定する。もしルートノードが２つ以上ある場合は、それぞれのルートノードについての処理負荷の合計が閾値Ａを超えているかどうかを判定する。閾値Ａを超えていない場合、ステップＳ３０３の処理は終了する。閾値Ａを超えている場合、処理はステップＳ６０２に進む。
【００３３】
ステップＳ６０２において分割部２４３０は、木構造を２つのグループへと分割できるかどうかを判定する。分割できる場合、処理はステップＳ６０３に進む。分割できない場合、ステップＳ３０３の処理は終了する。
【００３４】
以下で、ステップＳ６０２の判定についてより詳しく説明する。例えば、ステップＳ６０１で処理負荷が判定されたノードが、複数の子ノードを持つ場合、木構造を２つのグループへと分割することができる。本実施例では、木構造の各ノードはＸＭＬデータの各要素に対応するため、ノードが複数の子ノードを持つことは、要素が複数の子要素を持つことに相当する。また、２つ以上のルートノードについての合計の処理負荷が閾値Ａを超えている場合にも、ルートノードごとに木構造を分割することができる。さらに、ルートノードＮ１は１つの子ノードＮ１１を持つが、この子ノードＮ１１が複数の子ノードＮ１１１，Ｎ１１２を持つ場合がある。このような場合には、Ｎ１、Ｎ１１、及びＮ１１１を含む木構造と、Ｎ１１２を含む木構造とに、木構造を分割することができる。
【００３５】
ステップＳ６０３において分割部２４３０は、木構造を２つのグループへと分割する。分割方法は任意であり、どのような方法で分割したとしても、それぞれのグループの処理負荷は小さくなる。分割方法は、構文解析を行う装置が行う構文解析方法に応じて切り替えることもできる。以下では分割方法のいくつかの例を挙げる。
【００３６】
第１の方法を、図７のフローチャートを参照して説明する。第１の方法により、図４の木構造は、図８（ｂ）のようにグループ化される。第１の方法によれば、グループ間の処理負荷の差を小さくすることができる。
【００３７】
以下では、ルートノードの処理負荷の半分の値を処理負荷Ｃとする。ステップＳ７０１において木構造は、図８（ａ）に示されるように、ルートノード(import)と、その子ノード(entry)のそれぞれとに分割される。また、ルートノードと、その子ノードのそれぞれとについて、図８（ａ）に示されるように処理負荷が算出される。この算出は、ステップＳ３０２において算出された処理負荷を参照して容易に行うことができる。ここで、ルートノード(import)と、その子ノード(entry)のそれぞれは、グループ１に所属しているものとする。
【００３８】
ステップＳ７０２において分割部２４３０は、ステップＳ７０１で分割されたそれぞれのノードについて、処理負荷Ｃを超えないものが存在するか否かを判定する。存在する場合、処理はステップＳ７０３に進む。存在しない場合、ステップＳ６０３の処理は終了する。
【００３９】
ステップＳ７０３において分割部２４３０は、グループ１に含まれる分割されたノードのうち、最大の処理負荷を有するものを、グループ１からグループ２に移動する。そして分割部２４３０は、移動したノードの処理負荷を処理負荷Ｃから差し引く。その後処理はステップＳ７０２に戻る。
【００４０】
以上の処理により、分割されたそれぞれのノードをグループ１とグループ２とに区分することができる。ステップＳ７０１において、木構造はルートノードとその子ノードのそれぞれとに分割された。しかしながら、分割方法はこれに限られない。例えば、別の階層において上位ノードと下位ノードとに分割してもよい。ルートノードＮ１が１つの子ノードＮ１１を持ち、この子ノードＮ１１が複数の子ノードＮ１１１，Ｎ１１２を持つ場合について、具体的な例を説明する。このような場合には、Ｎ１とＮ１１とを含む木構造と、Ｎ１１１を含む木構造と、Ｎ１１２を含む木構造とに、木構造を分割することができる。また、問題がない場合には、階層に関係なく分割を行ってもよい。
【００４１】
分割の第２の方法として、木構造が複数のルートノードを含んでいる場合は、それぞれのルートノードを含む複数の木構造へと、木構造を分割することができる。例えば、図８（ｂ）のグループ１は、図８（ｃ）のグループ１１及びグループ１２へと分割することができる。また、図８（ｂ）のグループ２は、図８（ｃ）のグループ２１及びグループ２２へと分割することができる。
【００４２】
また、第３の方法として、文書順に、すなわちＸＭＬデータ中に要素が出現する順番にしたがって、木構造を分割することもできる。より具体的には、ＸＭＬデータ中でデータの先頭から所定の位置範囲内に出現する要素が同じグループに入るように、グループ化を行うことができる。ＸＭＬデータを構文解析する場合は、文書順に処理することが多い。したがって、文書順にしたがって分割が行われている方が効率的に処理できることが考えられる。第３の方法を用いる場合、第１の方法のステップＳ７０１と同様に木構造をルートノードとその子ノードとに分割した後、グループ１の処理負荷が半分以下になるまで、文書順に分割単位をグループ２へ移していけばよい。
【００４３】
ステップＳ６０３における分割の後、分割部２４３０はステップＳ６０４において、分割された各グループの処理負荷が、閾値Ｂを超えているか否かを判定する。ここで各グループの処理負荷とは、各グループに含まれる分割された木構造のそれぞれについての処理負荷の合計を指す。閾値Ｂは、あらかじめ設定された処理負荷の下限値であり、各グループの処理負荷が閾値Ｂを超えない場合には、分割部２４３０は分割は必要ないと判定する。閾値Ｂは閾値Ａと同様に決定することができ、一般的には並列処理を行う際に発生するタスクの割り当てや、同期処理などの、オーバヘッドを考慮して決定される。閾値Ｂは閾値Ａと同じ値であってもよい。本実施例では閾値Ｂを１０００とする。もっとも、ステップＳ６０４の処理を行わず、ステップＳ６０３の後に、処理が直接ステップＳ６０５に進んでもよい。
【００４４】
各グループの処理負荷が閾値Ｂを超えていない場合、ステップＳ３０３の処理は終了し、処理はステップＳ３０４へ進む。この場合、ステップＳ６０３で行われたグループ化に従う木構造の分割は行われない。いずれかのグループの処理負荷が閾値Ｂを超えている場合、処理はステップＳ６０５に進む。
【００４５】
ステップＳ６０５において分割部２４３０は、各グループを一つの処理単位とみなし、それぞれのグループに対して処理識別子を割り当てる。この処理識別子は、１つのＸＭＬデータから得られたそれぞれのグループについて一意となるように割り当てられる。この処理識別子を参照して、構文解析時には並列処理が行われる。割り当てられた処理識別子は、各グループのルートノードに保存される。
【００４６】
以上のように、各ノードは上位−下位関係を有する１以上のノードの組み合わせへと分割される。以上のノード分割結果に従って構造化データの各要素が分割されるため、構造化データは上位−下位関係を有する１以上の要素で構成される複数の部分データに分割される。しかしながら図８（ｂ）及び（ｃ）に示すように、各グループにはルートノードが２つ以上含まれていてもよい。各グループは、並列構文解析においてそれぞれが独立実行される処理単位に相当する。すなわち、上位−下位関係を有する１以上の要素で構成される２以上の部分データが、１つの処理単位に含まれていてもよい。
【００４７】
各グループにはルートノードが２つ以上含まれている場合、この場合、処理識別子はそれぞれのルートノードに保存される。例えば、図８（ｃ）のように木構造が分割された場合は、グループ１１、グループ１２、グループ１３、及びグループ１４のそれぞれに対して、処理識別子proc1, proc2, proc3, proc4を割り当てることができる。この場合、処理識別子proc1〜proc4は、図９に示されるように特定のノードに保存される。もっとも、処理識別子の保存方法はこの方法に限定されず、どのノードがどのグループに属するのかが確認できればよい。例えば、それぞれのグループに含まれる全てのノードに処理識別子を保存してもよい。
【００４８】
そして、ステップＳ６０５によって区別されたそれぞれの処理単位に対して、ステップＳ６０１〜ステップＳ６０５の処理が繰り返される。例えば、ステップＳ６０１〜ステップＳ６０５の処理によって図８（ａ）の木構造は図８（ｂ）に示されるようにグループ１及びグループ２の２つの処理単位に分割される。また、グループ１及びグループ２に対してステップＳ６０１〜ステップＳ６０５の処理を行うことにより、グループ１１及びグループ１２、並びにグループ２１及びグループ２２が、それぞれ決定される。
【００４９】
ステップＳ３０３における分割後、ステップＳ３０４において抽出部２４４０は、ＸＭＬデータを符号化する。このとき抽出部２４４０は、ＸＭＬデータから処理制御情報を作成する。処理制御情報は、分割されたＸＭＬデータを並列処理するために用いられる。以下に、処理制御情報について詳しく説明する。
【００５０】
ＸＭＬにおいては、名前空間を設定することができる。名前空間は、要素や属性などの名前のスコープを示す。例えば、図１０のＸＭＬデータについて、最初の要素elem1と次の要素elem1とは同じ名前を有する。しかしながら、最初の要素elem1は名前空間ns1.example.orgに属し、次の要素elem1は名前空間ns2.example.orgに属するため、これらは違う要素名を持つものとして認識される。すなわち、ＸＭＬデータを構文解析する際には、要素や属性がどの名前空間に属するのかを知る必要がある。
【００５１】
ところが、名前空間宣言xmlns:b="ns2.example.org"は、要素b:elem1より上位の要素a:elem1で行われている。ここで、図１０に示されるＸＭＬデータが、親要素＜a:elem1 xmlns:a="ns1.example.org" xmlns:b="ns2.example.org"＞＜/a:elem1＞と子要素＜b:elem1/＞とに分割されたとする。すると、それぞれの要素を並列に解析する場合には問題が生じうる。すなわち、子要素＜b:elem1/＞を処理するプロセッサは、xmlns:b="ns2.example.org"という名前空間宣言が親要素で行われていることを知ることができない。このため、子要素b:elem1を処理するプロセッサは、子要素b:elem1が属する名前空間を知ることができず、正しく構文解析を行えない可能性がある。
【００５２】
そこで本実施例においては、子要素を処理するプロセッサが親要素においてなされた名前空間宣言を知ることができるように、図１２（ａ）に示すような処理制御情報が抽出され、この処理制御情報が構文解析時に用いられる。以下、図１１のフローチャートを参照して、ステップＳ３０４における処理制御情報の抽出処理について詳しく説明する。
【００５３】
図１１の処理においては、ＸＭＬデータの最上位要素が最初の処理対象の処理対象とされる。以下の処理を行うことにより、最上位要素から文書順に符号化が行われる。すなわち、複数の部分データを含む構造化データが符号化される。また、符号化を行いながら、処理制御情報が更新され、最終的に図１２（ａ）に示されるような処理制御情報が生成される。以下では、ステップＳ３０３において作成された木構造を単に木構造と呼ぶ。また、ある要素に対応する木構造内のノードを、単に要素に対応するノードと呼ぶ。
【００５４】
図９において、処理識別子proc1を有するノードは、下位に処理識別子proc2、proc3、又はproc4を有するノードを有する。このような場合、処理識別子proc2、proc3、及びproc4は、処理識別子proc1のスコープ内にあるものとする。また、処理識別子proc1を有するノードの下位に存在するノード（又は対応する要素）は、処理識別子proc1のスコープ内にあるものとする。同様に、また、処理識別子proc2, proc3, proc4を有するそれぞれのノードの下位に存在するノード（又は対応する要素）は、それぞれ処理識別子proc2, proc3, proc4のスコープ内にあるものとする。
【００５５】
本実施例において処理制御情報は、処理識別子単位で、データオフセットと、参照処理識別子と、構造の型と、名前空間宣言とを示す。データオフセット（位置情報）は、処理識別子のスコープ内にある要素が格納されている、符号化されたデータ中のデータ位置を示す。例えば図１２（ｂ）は、図２のＸＭＬデータ１２１０を符号化することによって得られた符号化データ１２２０における、データオフセットと位置１２３０との関係を示している。本実施例においては、データオフセットを参照することにより、処理識別子proc2, proc3, proc4は処理識別子proc1のスコープ内にあることを知ることができる。すなわち、proc2, proc3, proc4を有するノードに対応する要素（部分データの最上位要素）が、proc1を有するノードに対応する要素（他の部分データ中の要素）に接続していることを、データオフセットは特定する。参照処理識別子には、自身のスコープ内にある処理識別子を示す。構造の型は、処理識別子が保存されているノードに対応する要素の型を示す。図９の例においては全てのノードは要素に対応するから、「構造の型」は「要素」を示す。名前空間宣言（補助情報）には、処理識別子のスコープ内にある要素（部分データ内の要素）を解析する際に参照される名前空間宣言が示される。具体的にはこの名前空間宣言は、処理識別子のスコープ内にある要素（部分データ内の要素）よりも上位の要素によって規定された名前空間宣言を含みうる。
【００５６】
まずステップＳ１１０１において抽出部２４４０は、処理対象の要素に対応するノードに処理識別子が保存されているか否かを判定する。含まれている場合、処理はステップＳ１１０２に進む。含まれていない場合、処理はステップＳ１１０６に進む。
【００５７】
ステップＳ１１０２において抽出部２４４０は、処理制御情報を更新する。具体的には抽出部２４４０は、符号化データ中で処理対象の要素が格納される位置を示すオフセットと、処理対象の構造の型とを、処理制御情報に追加する。この処理は、抽出部２４４０が有する第２の抽出部２４４４が行うことができる。ステップＳ１１０２においては特に、オフセットとして、処理対象の要素の開始要素が格納される位置が登録される。処理制御情報は、処理識別子単位で保存される。さらに抽出部２４４０は、処理対象の要素に名前空間宣言が含まれている場合、名前空間宣言を名前空間管理テーブルに格納する。名前空間管理テーブルは、符号化中に、処理対象の要素に適用される名前空間宣言を確認するために用いられる。
【００５８】
ステップＳ１１０３において抽出部２４４０は、処理対象の要素が他の処理識別子のスコープ内にあるか否かを判定する。具体的には抽出部２４４０は、識別子管理テーブルに登録されている処理識別子を確認する。識別子管理テーブルは、処理中の要素がどの処理識別子のスコープ内にあるのかを示し、後述のように更新される。処理対象の要素についての識別子が、識別子管理テーブルに登録されている処理識別子とは異なる場合、抽出部２４４０は、処理対象の要素が他の処理識別子のスコープ内にあるものと判定する。処理対象の要素が他の処理識別子のスコープ内にある場合、処理はステップＳ１１０４に進む。処理対象の要素が他の処理識別子のスコープ内にない場合、処理はステップＳ１１０５に進む。
【００５９】
ステップＳ１１０４において抽出部２４４０は、処理制御情報を更新する。具体的には抽出部２４４０は、ステップＳ１１０３で判定された他の処理識別子についてのエントリに、「参照処理識別子」として、処理対象の要素についての処理識別子を登録する。
【００６０】
ステップＳ１１０５において抽出部２４４０は、処理対象の要素についての処理識別子を識別子管理テーブルに登録する。ステップＳ１１０６において抽出部２４４０は、処理中の要素について、開始要素とその値を符号化する。この処理は、抽出部２４４０が有する符号化部２４４６が行うことができる。ステップＳ１１０７において抽出部２４４０は、処理対象の要素に名前空間宣言が含まれているかどうか判定する。含まれていない場合、処理はＳ１１０９へ進む。含まれている場合、処理はステップＳ１１０８に進む。ステップＳ１１０８において抽出部２４４０は、名前空間管理テーブルに、処理対象の要素に含まれる名前空間宣言を登録する。この処理は、抽出部２４４０が有する第１の抽出部２４４２が行うことができる。
【００６１】
ステップＳ１１０９において抽出部２４４０は、処理対象の要素が、まだ符号化が終わっていない子要素を有するか否かを判定する。有する場合、処理はステップＳ１１１１に進む。有さない場合、処理はステップＳ１１１０に進む。ステップＳ１１１０において抽出部２４４０は、処理対象の要素が有する、まだ符号化が終わっていない子要素のうち１つを新しい処理対象の要素として選択し、その後処理はステップＳ１１０１に戻る。
【００６２】
ステップＳ１１１１において抽出部２４４０は、処理対象の要素についての終了要素を符号化する。この処理は、抽出部２４４０が有する符号化部２４４６が行うことができる。ステップＳ１１１２において抽出部２４４０は、要素が終了することでスコープ外となる名前空間があるか否かを判定する。例えば抽出部２４４０は、名前空間管理テーブルに、処理対象の要素が含む名前空間宣言が登録されているか否かを判定すればよい。名前空間管理テーブルに、処理対象の要素が含む名前空間宣言が登録されている場合、要素が終了することでスコープ外となる名前空間があると判定できる。要素が終了することでスコープ外となる名前空間がある場合、処理はステップＳ１１１３に進む。要素が終了することでスコープ外となる名前空間がない場合、処理はステップＳ１１１４に進む。
【００６３】
ステップＳ１１１３において抽出部２４４０は、スコープ外となる名前空間を名前空間管理テーブルから削除する。例えば抽出部２４４０は、処理対象の要素が含む名前空間宣言を名前空間管理テーブルから削除すればよい。
【００６４】
ステップＳ１１１４において抽出部２４４０は、処理対象の要素に対応するノードが処理識別子を含んでいるか否かを判定する。含まれている場合、処理はステップＳ１１１５に進む。含まれていない場合、処理はステップＳ１１１７に進む。
【００６５】
ステップＳ１１１５において抽出部２４４０は、オフセットとして、処理対象の要素の終了要素が格納される位置を、処理制御情報に記録する。ステップＳ１１１６において抽出部２４４０は、スコープ外となる処理識別子を識別子管理テーブルから削除する。例えば抽出部２４４０は、処理対象の要素に対応するノードが含んでいる処理識別子を識別子管理テーブルから削除すればよい。
【００６６】
ステップＳ１１１７において抽出部２４４０は、処理対象の要素について、親要素が存在するか否かを判定する。存在する場合、処理はステップＳ１１１８に進む。ステップＳ１１１８において抽出部２４４０は、処理対象の要素についての親要素を新たな処理対象として選択し、その後処理はステップＳ１１１９に戻る。
【００６７】
ステップＳ１１１７において親要素が存在しない場合、符号化処理は終了する。この際抽出部２４４０は、作成された処理制御情報を保存する。抽出部２４４０は、例えば処理制御情報を符号化データの先頭又は末尾に付加することができる。また抽出部２４４０は、処理制御情報を符号化データとは別のファイルとして保存してもよい。こうして生成された符号化データ（符号化された構造化データ）と処理制御情報（補助情報及び位置情報）とは、構文解析を行う装置へと出力される。符号化データと処理制御情報とは、互いに異なる通信手段を介して送られてもよい。
【００６８】
次に、こうして生成された符号化データと処理制御情報とを用いて構文解析を行う場合について説明する。図２５は、構文解析を行う情報処理装置２５００の構成例を示す。情報処理装置２５００は、４つのプロセッサ２５１０〜２５４０を有する。もっとも、情報処理装置２５００が有するプロセッサの数は異なっていてもよい。情報処理装置２５００が２つ以上のプロセッサを有することにより、符号化データを並列に構文解析することができる。情報処理装置２５００としては、並列処理が可能なプロセッサを複数有する、ＧＰＵのような装置を用いることもできる。
【００６９】
各プロセッサ２５１０〜２５４０は、ＸＭＬデータの構文解析を行う能力を有するものとする。プロセッサ１は、処理制御情報を元に各プロセッサへタスクを割り当てる。具体的にはプロセッサ１は、処理制御情報の最初のエントリ(proc1)を読み込む。そしてプロセッサ１は、最初のエントリ(proc1)についてデータオフセット範囲から、他のエントリ(proc2,proc3,proc4)についてのデータオフセット範囲を除いた部分を、プロセッサ１が構文解析する符号化データとして特定する。この処理は、例えば処理制御情報の参照処理識別子に従って行うことができる。
【００７０】
またプロセッサ１は、他のエントリ(proc2,proc3,proc4)を読み込み、それぞれのエントリのデータオフセット範囲が示す部分を、プロセッサ２，３，４がそれぞれ処理する符号化データとして特定する。例えばプロセッサ２は、符号化データのうち、エントリproc2のデータオフセット範囲が示す部分を構文解析する。すなわちプロセッサ１は、プロセッサ２に対して、特定された部分の符号化データを解析するように命令する。この際プロセッサ１は、エントリproc2の構造の型と、名前空間宣言とをプロセッサ２に通知する。プロセッサ１は、プロセッサ３及び４に対しても同様の命令及び通知を行う。
【００７１】
プロセッサ２は、通知に従って名前空間宣言を設定し、通知された構造の型（今回はＸＭＬの要素）に従って、命令された部分を構文解析する。具体的にはプロセッサ２は、命令された部分を復号してＸＭＬデータの一部分を生成し、生成されたＸＭＬデータを解析する。そしてプロセッサ２は、解析結果をプロセッサ１へ通知する。プロセッサ２は例えば、構文解析結果をツリー構造としてプロセッサ１へ通知すればよい。プロセッサ３及び４も同様に動作できる。
【００７２】
プロセッサ１は、プロセッサ２〜４から通知された構文解析結果、及びプロセッサ１自身による構文解析結果を統合する。この統合は、例えば処理制御情報の参照処理識別子に従って行うことができる。こうして、符号化データの構文解析結果であるツリー構造が得られる。本実施例においてはプロセッサ１はスケジューリングと構文解析との双方を行った。しかしながら、スケジューリングを行うプロセッサと構文解析を行うプロセッサとは別のものであってもよい。
【００７３】
以上のように、処理制御情報（特にデータオフセット）を参照することにより、符号化データのうちどの部分を別々のプロセッサに割り当てればよいのかが分かる。また、処理制御情報（特に名前空間宣言）を参照することにより、それぞれの部分を解析するプロセッサが参照すべき名前空間宣言が分かる。このため、スケジューリングを行うプロセッサは、それぞれのプロセッサに対して、処理すべき部分を命令し、名前空間宣言を通知することができる。こうしてそれぞれのプロセッサは、符号化データの命令された部分に参照すべき名前空間宣言が含まれていない場合であっても、命令された部分を、通知された名前空間宣言に従って正しく構文解析することができる。
【００７４】
本実施例においては、構造化データを文書順に符号化した。そして処理制御情報として、符号化データのうちどの部分を別々のプロセッサに割り当てればよいのか（データオフセット）を特定した。この方法によれば、並列構文解析に対応していない情報処理装置であっても、並列処理を用いずに符号化データを復号及び構文解析できるという利点がある。しかしながら、構造化データを文書順に符号化することは必須ではない。例えば、それぞれの処理識別子ごとに別々に、処理識別子のスコープ内の要素を符号化してもよい。この場合にも、並列な構文解析は可能となる。この場合、符号化データのうちどの部分を別々のプロセッサに割り当てればよいのかを特定する必要はない。
【実施例２】
【００７５】
実施例２では、実施例１と同様の方法を用いて、並列に構文解析可能なようにＸＭＬデータをＥＸＩ符号化することについて説明する。本実施例では、図１３（ａ）に示すＸＭＬデータをＥＸＩ符号化するものとする。ＥＸＩは、Ｗ３Ｃで仕様策定中のＸＭＬ符号化方式の１つである。ＥＸＩによれば文字形式ではなくバイナリ形式で符号化することができるため、符号化データサイズの縮小が可能となり、構文解析を高速化することができる。しかしながらＥＸＩは、ＸＭＬデータの情報量を減らすものではない。
【００７６】
実施例２における処理は、実施例１と同様に行うことができる。例えば本実施例に係る符号化処理は、図２４に示す情報処理装置１００を用いて行うことができる。以下で本実施例に係る処理を、図３のフローチャートを参照して説明する。ステップＳ３０１において設定部２４１０は、実施例１と同様に、基礎負荷値を設定する。本実施例において設定部２４１０は、ＥＸＩの構文解析に必要な処理負荷を考慮してこの設定を行う。ステップＳ３０２において負荷算出部２４２０は、図１３（ａ）に示すＸＭＬデータについて、実施例１と同様に処理負荷を算出する。ステップＳ３０３において分割部２４３０は、実施例１と同様に、ステップＳ３０２で生成された木構造を分割する。ステップＳ３０４において抽出部２４４０は、処理制御情報の抽出、及びＸＭＬデータの符号化を行う。
【００７７】
以下で、ステップＳ３０４における処理について詳しく説明する。ＥＸＩ符号化においては、grammarと文字列テーブルというものを使用する。grammarは、ＸＭＬデータ内のある構造に対し、どのような符号を割り当てればよいかを決めたものである。符号は、他の構造との位置関係により変化しうる。また文字列テーブルは、ＸＭＬデータ中に現れる文字列と識別子との対応関係を示す。繰り返し現れる文字列には、文字列の代わりに識別子が符号化される。
【００７８】
ＥＸＩ符号化中には、より効率の良い符号化を行うために符号化規則を学習しながら符号化が行われるため、grammarや文字列テーブルが更新されうる。このため、ＥＸＩで符号化されたデータの構文解析を行うためには、それぞれの部分を符号化した際に用いられた符号化規則を知る必要がある。一方でＥＸＩ符号の復号は、符号化中に行われた符号化規則の学習を再現しながら行われる。このため、通常はＥＸＩ符号の復号はデータの先頭から行われる。
【００７９】
本実施例において抽出部２４４０は、ＥＸＩ符号の並列解析処理を可能とするために、図１５（ｂ）に示すような処理制御情報を作成する。以下に、ステップＳ３０４の処理を図１４のフローチャートを参照して説明する。図１４に示される処理は図１１に示される実施例１に係る処理と類似しており、同様の処理については説明を省略する。
【００８０】
本実施例では、ＥＸＩのschema informed grammarを用いる場合について説明する。schema informed grammer１３２０は、図１３（ｂ）に示すように、符号化の最初にＸＭＬのスキーマ情報１３１０から生成される。本実施例では、各grammarに識別子が割り当てられる。ＥＸＩ符号化を行う場合、名前空間情報は要素名や属性名とともに符号化される。よって、実施例１のように処理制御情報が名前空間情報を含む必要はない。
【００８１】
ステップＳ１４０１において抽出部２４４０は、処理対象の要素に対応するノードに処理識別子が含まれているか否かを判定する。含まれている場合、処理はステップＳ１４０２に進む。含まれていない場合、処理はステップＳ１４０８に進む。
【００８２】
ステップＳ１４０２において抽出部２４４０は、処理対象の要素より後で符号化規則の学習が発生するか否かを判定する。schema informed grammerを用いる場合、スキーマに記述されている情報については、予め符号化規則が作られる。しかしながら値データについてはスキーマには記述されていないため、値データについての学習が行われることがある。したがって、このような値データが存在するか否かを判定することにより、符号化規則の学習が発生するか否かを判定することができる。例えば図１５（ａ）は、符号化中に学習が発生する要素と、符号化中に学習が発生しない要素とを示す。学習が発生すると判定した場合、処理はステップＳ１４０３に進む。学習が発生しないと判定した場合、処理はステップＳ１４０４に進む。
【００８３】
ステップＳ１４０３において抽出部２４４０は、現在使われている符号化規則を待避する。そして抽出部２４４０は、self contained要素としての符号化規則を用いるように処理を切り替える。self contained要素として指定された部分は、ＥＸＩの仕様において、その他の部分と独立して符号化される。すなわちself contained要素として指定された部分は、共通の符号化規則とは独立した符号化規則に従って符号化が行われる（第２の符号化）。よって、self contained要素として指定された部分は、互いに符号化規則の学習の影響を受けないため、別々のプロセッサで処理することができる。一方でステップＳ１２０４において学習が発生しないと判定された場合には、共通の符号化規則に従って符号化が行われる（第１の符号化）。
【００８４】
ステップＳ１４０４において抽出部２４４０は、ステップＳ１１０２と同様に処理制御情報を更新する。本実施例において処理制御情報には、名前空間宣言の代わりにgrammer idが記録される。grammer idは、符号化された要素について適用されるgrammerの識別子である。self contained要素として指定された部分については、grammer idの代わりにself containedであることを示す情報が記録される。
【００８５】
ステップＳ１４０５〜ステップＳ１４０８の処理は、実施例１のステップＳ１１０３〜ステップＳ１１０６と同様である。ステップＳ１４０８においては、上述のようにＥＸＩ符号化が行われ、必要に応じて学習が行われる。ステップＳ１４０９〜ステップＳ１４１１の処理は、実施例１のステップＳ１１０９〜ステップＳ１１１１と同様である。
【００８６】
ステップＳ１４１２において抽出部２４４０は、処理対象の要素に処理識別子が含まれているか否かを判定する。含まれている場合、処理はステップＳ１４１３に進む。含まれていない場合、処理はステップＳ１４１７に進む。ステップＳ１４１３において抽出部２４４０は、処理対象の要素がself contained要素として指定されたか否かを判定する。指定されていた場合、処理はステップＳ１４１４に進む。指定されていない場合、処理はステップＳ１４１５に進む。
【００８７】
ステップＳ１４１４において抽出部２４４０は、処理対象の要素の処理中にステップＳ１４０３で退避された符号化規則を読み出す。以降ではこの符号化規則が符号化のために用いられる。
【００８８】
ステップＳ１４１５〜ステップＳ１４１６の処理は、実施例１のステップＳ１１１５〜ステップＳ１１１６と同様に行われる。また、ステップＳ１４１７〜ステップＳ１４１８の処理は、実施例１のステップＳ１１１７〜ステップＳ１１１８と同様に行われる。
【００８９】
実施例１と同様に抽出部２４４０は、こうして生成した処理制御情報を、符号化データに付加してもよいし、符号化データとは別のファイルとして保存してもよい。例えばＥＸＩでは、ヘッダ部分にオプション情報を付加することができる。そこで本実施例では、図１５（ｂ）に示される処理制御情報をＥＸＩヘッダに付加する。
【００９０】
ＥＸＩヘッダには、ＸＭＬ形式でオプションデータを追加することができる。本実施例においては図１６に示すように、１つの処理識別子を１つのＸＭＬの要素として格納する。図１６の例において、参照処理識別子として示される情報識別子の参照関係は、ＸＭＬの要素の親子関係として表現されている。また、オフセット、構造の型、及びgrammar IDは、要素の属性として格納される。図１６に示される形式を用いることにより、ＥＸＩに準拠したデータ形式で、構文解析を行う情報処理装置に対して処理制御情報を通知することができる。また、図１６に示される形式を用いることにより、処理制御情報を簡潔に記述することができる。
【００９１】
こうして生成されたＥＸＩ符号化データと処理制御情報とを用いた並列構文解析は、実施例１と同様に行うことができる。本実施例によればＥＸＩ符号化データのそれぞれの部分について使用されるgrammer idを知ることができる。また、符号化規則の学習が発生しうる部分についてはself contained要素として符号化が行われる。このため、ＥＸＩ符号化データの一部について並列構文解析を行うそれぞれのプロセッサは、正しく構文解析を行うことができる。
【実施例３】
【００９２】
実施例３では、実施例１と同様の方法を用いて、並列に構文解析可能なようにＸＭＬデータをＥＸＩ符号化することについて説明する。本実施例では、実施例２とは別の方法を用いて符号化を行う。本実施例では、図１７（ａ）に示すＸＭＬデータをＥＸＩ符号化する場合について説明する。
【００９３】
実施例２では、符号化規則の学習が発生する可能性を有する要素を、self contained要素として符号化した。しかしながら一般的に、要素をself contained要素として符号化する場合は、self contained要素としない場合と比べて、得られる符号化データのサイズが大きくなる。そこで本実施例においては、self contained要素を使用しない。
【００９４】
本実施例では、schema informedではない符号化を行う場合について説明する。この場合、図１７（ｂ）に示すように、ＸＭＬデータ中に出現する要素、属性、値などに応じて符号化規則を学習しながら符号化が行われる。本実施例の方法はschema informed grammerを用いる場合にも適用できる。しかしながら、schema informedではない符号化を行う場合には、あらかじめgrammarを作成しないので、符号化規則の学習はより多く発生する。このため、本実施例の方法をschema informedではない符号化に適用することは有利である。
【００９５】
実施例３における処理は、実施例２と同様に行うことができる。例えば本実施例に係る符号化処理は、図２４に示す情報処理装置１００を用いて行うことができる。以下で本実施例に係る処理を、図３のフローチャートを参照して説明する。ステップＳ３０１〜ステップＳ３０３の処理は、実施例２と同様に行うことができる。ステップＳ３０４において抽出部２４４０は、self contained要素を使用しなくても並列構文解析が可能となるように、図１９（ｂ）に示すような処理制御情報を生成する。
【００９６】
以下に、ステップＳ３０４における処理について図１８のフローチャートを参照して説明する。図１８に示される処理は図１４に示される実施例１に係る処理と類似しており、同様の処理については説明を省略する。
【００９７】
ステップＳ１８０１において抽出部２４４０は、処理対象の要素に対応するノードに処理識別子が含まれているか否かを判定する。含まれている場合、処理はステップＳ１８０２に進む。含まれていない場合、処理はステップＳ１８０６に進む。ステップＳ１８０２において抽出部２４４０は、処理識別子、構造の型、及び符号化するノードに適用するgrammar識別子を、図１９（ｂ）のような処理制御情報として記録する。これらの情報は、処理識別子単位で保存される。さらに抽出部２４４０は、開始要素のオフセット位置までの符号化規則の学習操作を、処理制御情報として記録する。
【００９８】
オフセット位置までの符号化規則の学習操作とは、ＥＸＩの仕様に従い、オフセット位置までのＸＭＬデータを符号化する際に、grammar及び文字列テーブルへ加えられた変更操作のことである。ＸＭＬデータの先頭からオフセット位置までに行われた変更操作を、それぞれのオフセット位置について記録してもよい。また、前のオフセット位置から現在のオフセット位置までの間に行われた変更操作を、それぞれのオフセット位置について記録してもよい。図１９（ｂ）の例では、オフセット間の変更操作のみが記録されている。このように、それぞれのオフセット位置に関連付けて（すなわち要素に関連付けて）、要素を符号化する際に用いた符号か規則が記録される。
【００９９】
ステップＳ１８０３〜ステップＳ１８０５の処理は、実施例２のステップＳ１４０５〜ステップＳ１４０７と同様である。またステップＳ１８０６の処理は、ステップＳ１４０８と同様である。本実施例においてステップＳ１８０６では、schema informedでない符号化が使用される。
【０１００】
ステップＳ１８０７において抽出部２４４０は、ステップＳ１８０６における符号化で、符号化規則の学習が発生したか否かを判定する。例えば図１９（ａ）は、符号化中に学習が発生する要素と、符号化中に学習が発生しない要素とを示す。学習は発生していない場合、処理はステップＳ１８０９に進む。学習が発生した場合、処理はステップＳ１８０８に進む。ステップＳ１８０８において抽出部２４４０は、ステップＳ１８０６における符号化規則の学習操作をメモリ（非図示）に記録する。ステップＳ１８０８において記録された学習操作は、ステップＳ１８０２及びステップＳ１８１３において抽出部２４４０がオフセット位置までの符号化規則の学習操作を処理制御情報として記録する際に参照される。
【０１０１】
ステップＳ１８０９〜ステップＳ１８１１の処理は、実施例２のステップＳ１４０９〜ステップＳ１８１１と同様である。ステップＳ１８１２において抽出部２４４０は、処理対象の要素に処理識別子が含まれているか否かを判定する。含まれている場合、処理はステップＳ１８１３に進む。含まれていない場合、処理はステップＳ１８１５に進む。ステップＳ１８１３において抽出部２４４０は、オフセットとして、処理対象の要素の終了要素が格納される位置を、処理制御情報に記録する。さらに抽出部２４４０は、終了要素のオフセット位置までの符号化規則の学習操作を、処理制御情報として記録する。ステップＳ１８１４の処理は、実施例２のステップＳ１４１６と同様である。
【０１０２】
ステップＳ１８１５〜ステップＳ１８１６の処理は、実施例２のステップＳ１４１７〜ステップＳ１４１８と同様である。
【０１０３】
こうして生成されたＥＸＩ符号化データと処理制御情報とを用いた並列構文解析は、実施例２と同様に行うことができる。本実施例によればＥＸＩ符号化データのそれぞれの部分について使用されるgrammer idを知ることができる。また、ＥＸＩ符号化データのそれぞれの部分について使用される符号化規則も、処理制御情報から知ることができる。このため、符号化データの途中からでも正しく符号化規則を再現し構文解析を行うことができる。
【実施例４】
【０１０４】
実施例４では、符号化された構造化データの並列構文解析について詳しく説明する。図２０は、本実施例に係る構文解析を行う装置の一例である、情報処理装置２０００を示す。情報処理装置２０００は、並列実行制御部２００１と、制御情報解釈部２００２と、構文解析実行部２００３とを有する。
【０１０５】
並列実行制御部２００１は、構文解析実行部２００３を制御して構文解析を行わせる。具体的には並列実行制御部２００１は、符号化された構造化データと処理制御情報とを受け取る（第１の取得、第２の取得、第３の取得）。そして並列実行制御部２００１は、処理制御情報を制御情報解釈部２００２に送る。制御情報解釈部２００２は送られた処理制御情報を解釈し、解釈結果を並列実行制御部２００１に送る。並列実行制御部２００１はこの解釈結果に従って、構文解析実行部２００３を制御して構文解析を行わせる。
【０１０６】
構文解析実行部２００３は、符号化された構造化データの復号化及び構文解析を行う。構文解析実行部２００３は、複数の構文解析処理を並行して実行することができる。それぞれの構文解析処理は、スレッドとして実行されてもよいしプロセスとして実行されてもよい。構文解析実行部２００３は、複数のプロセッサを含んでいてもよい。また構文解析実行部２００３は、複数のスレッド又はプロセスを並列に実行可能な１つ以上のプロセッサにより構成されていてもよい。それぞれの構文解析処理は、異なるハードウェア上で実行されてもよい。
【０１０７】
本実施例で情報処理装置２０００が取得する処理制御情報の一例を、図２１（ａ）に示す。図２１（ａ）に示す処理制御情報は、実施例１に係る図１２（ａ）の処理制御情報と類似している。図２１（ａ）の処理制御情報は、符号化データを４つのデータ範囲に区分することが可能であって、それぞれが並列に処理されうることを示す。それぞれの処理について、１つのエントリが設けられている。図２１（ａ）に示す処理制御情報のそれぞれのエントリは、図２１（ｂ）に示すＸＭＬデータのうち破線で示された部分に対応する。
【０１０８】
データ範囲は、符号化データ中における、それぞれのデータ（符号化部分データ）の位置を示す。実施例１の処理制御情報においては、データオフセットと参照処理識別子とを用いて、それぞれのデータの位置が示される。しかしながら本実施例の処理制御情報においては、データ範囲を用いてそれぞれのデータの位置が示される。符号化データが数多くのデータに分割されない場合には、データの位置を取得するために計算を行う必要がないため、本実施例のようにデータ範囲を用いることは有利である。一方で、符号化データが数多くのデータに分割される場合は、実施例１のようにデータオフセットと参照処理識別子とを用いることが、処理制御情報のデータ量を削減できる点で有利である。
【０１０９】
タイプは、それぞれのデータの種類を示す。本実施例のタイプは、実施例１の構造の型よりもより細かくデータの種類を示している。タイプを参照することにより、構文解析処理の制御をより正確に行うことができる。タイプの例としては、ルート要素、要素、及び要素セットがある。ルート要素は、データが構造化データ全体の最上位要素であることを示す。要素は、データはルート要素ではないが、一つの入れ子構造になった要素であることを示す。要素セットは、データが入れ子構造にならない要素の集合であることを示している。
【０１１０】
名前空間宣言は、実施例１と同様に、それぞれのデータについて適用される名前空間を示す。それぞれのデータ範囲の外で名前空間宣言が行われている場合に、この名前空間を記録すればよい。また本実施例の処理制御情報は、さらに構造の位置という情報（位置情報）を付加している。この構造の位置は、それぞれのデータの構造化データ中における位置を示している。この構造の位置によって、それぞれのデータ（部分データ）の最上位要素が接続している他の部分データ中の要素が特定されうる。この情報を参照することにより、それぞれの構文解析処理によって得られた処理結果を集約することが容易となる。また、この情報を参照してそれぞれの構文解析処理を割り当てる構文解析実行部２００３を決定することもできる。
【０１１１】
本実施例に係る処理制御情報は、実施例１で説明したように、図１１に示すフローチャートに従って作成することができる。例えばデータ範囲及びタイプは、ステップＳ１１０２において処理制御情報に登録できる。また、構造の位置は以下のように作成することができる。まず、構造化データにおける各要素の階層の深さ（最上位要素からの距離）をカウントするためのカウンタと、ある深さの階層にある要素の数をカウントするためのカウンタとを用意しておく。そして、ステップＳ１１１０において子要素を選択する際に、抽出部２４４０は、階層の深さを示すカウンタをカウントアップする。また、ステップＳ１１１８において親要素を選択する際に、抽出部２４４０は、階層の深さを示すカウンタをカウントダウンする。また、ステップＳ１１０６において要素を符号化する際に、抽出部２４４０は、この要素が属する階層の要素の数を示すカウンタをカウントアップする。
【０１１２】
そしてステップＳ１１０２において抽出部２４４０は、これらのカウンタを参照して、処理対象の要素の階層の深さと、その階層における処理対象の要素の順序を、処理制御情報に登録する。これらの情報の記録方法は任意である。例えば図２１の例では、最上位要素の１番目の子要素についての構造の位置は「／１」と表現される。また、最上位要素の１番目の子要素の２番目の子要素の構造の位置は「／１／２」と表現される。
【０１１３】
次に本実施例における構文解析処理について、図２２及び２３のフローチャートを参照して説明する。ステップＳ２２０１において並列実行制御部２００１は入力された処理制御情報を制御情報解釈部２００２に送る。そして、制御情報解釈部２００２は送られた制御情報を解釈する。具体的には制御情報解釈部２００２は、図２１（ａ）に示す制御情報から各エントリ（各行）を抽出する。上述のように各エントリは並列処理されるデータの範囲と、それぞれのデータを構文解釈するために参照される名前空間宣言を含んでいる。さらに制御情報解釈部２００２は、抽出したエントリを並列実行制御部２００１へと送る。
【０１１４】
ステップＳ２２０２において並列実行制御部２００１は、未処理のエントリがあるかどうかを判定する。未処理のエントリとは、ステップＳ２２０９において構文解析処理が開始されていないデータ範囲についてのエントリを指す。未処理のエントリがある場合、処理はステップＳ２２０３へ進む。未処理のエントリがない場合、図２２の処理は終了し、図２３のステップＳ２３０１が実行される。
【０１１５】
ステップＳ２２０３において並列実行制御部２００１は、未処理のエントリから１つを選択する。さらに並列実行制御部２００１は、選択されたエントリに名前空間宣言が含まれているか否かを判定する。含まれている場合、処理はステップＳ２２０４に進む。含まれていない場合、処理はステップＳ２２０５に進む。ステップＳ２２０４において並列実行制御部２００１は、選択されたエントリに含まれている名前空間宣言を初期設定情報に記録する。
【０１１６】
ステップＳ２２０５において並列実行制御部２００１は、選択されたエントリのタイプが要素セットであるか否かを判定する。要素セットである場合、処理はステップＳ２２０６に進む。要素セットではない場合、処理はステップＳＳ２２０９に進む。
【０１１７】
ステップＳ２２０６において並列実行制御部２００１は、構文解析実行部２００３が要素セットを直接構文解析可能か否かを判定する。可能である場合、処理はステップＳ２２０７へ進む。可能でない場合、処理はステップＳ２２０８へ進む。一般的に、ＸＭＬの構文解析処理が可能であるプロセッサの中でも、要素セットを直接構文解析できるプロセッサとできないプロセッサとが存在する。並列実行制御部２００１は、選択されたエントリについて構文解析を行う構文解析実行部２００３の仕様に従って、ステップＳ２２０６における判定を行う。
【０１１８】
ステップＳ２２０７において並列実行制御部２００１は、選択されたエントリのタイプが要素セットであることを初期設定情報に登録する。ステップＳ２２０８において並列実行制御部２００１は、ステップＳ２２０８において並列実行制御部２００１は、選択されたエントリのタイプが要素セットであることを示すフラグを設定する。このフラグはステップＳ２２０９において用いられる。
【０１１９】
ステップＳ２２０９において並列実行制御部２００１は、選択されたエントリにより示されるデータ範囲内の符号化データと、初期設定情報とを、構文解析実行部２００３のうちの１つへと渡す。並列実行制御部２００１は、データが渡される構文解析実行部２００３を、処理を行っていない構文解析実行部２００３の中から選択することができる。また、選択されたエントリのタイプが要素セットであることを示すフラグが設定されている場合、並列実行制御部２００１は、選択されたエントリにより示されるデータ範囲内の符号化データを適当な要素（タグ）で囲む。具体的には、開始要素に対応する符号を符号化データの先頭に付加し、終了要素に対応する符号を符号化データの末尾に付加すればよい。このような処理を行うことにより、要素セットを直接構文解析できない構文解析実行部２００３であっても、付加された要素の子要素として要素セットを解析することができる。その後並列実行制御部２００１は、初期設定情報及びフラグを初期化し、処理はステップＳ２２０２に戻る。
【０１２０】
ステップＳ２２０９において符号化データと初期設定情報とを渡された構文解析実行部２００３は、初期設定情報を参照して、渡されたデータを復号化及び構文解析する。例えば構文解析実行部２００３は、データを復号して要素を取得し、さらに要素間の上位−下位関係を再現する。構文解析結果は、木構造のノードセットとして並列実行制御部２００１へと渡される。
【０１２１】
ステップＳ２３０１において並列実行制御部２００１は、それぞれの構文解析実行部２００３から構文解析結果を受け取る。本実施例において並列実行制御部２００１は、構文解析結果をいずれかの構文解析実行部２００３から受け取るたびにステップＳ２３０２の処理を開始する。しかしながら並列実行制御部２００１は、構文解析実行部２００３から全ての構文解析結果を受け取ってからステップＳ２３０２の処理を開始してもよい。本実施例において並列実行制御部２００１は、全てのエントリについて構文解析を開始してからステップＳ２３０１の処理を開始する。しかしながら並列実行制御部２００１は、図２２の処理と図２３の処理とを並行して行ってもよい。すなわち並列実行制御部２００１は、全てのエントリについて構文解析を開始する前に、ステップＳ２３０１の処理を開始してもよい。
【０１２２】
ステップＳ２３０２において並列実行制御部２００１は、受け取った構文解析結果を集約する。例えば図２１（ａ）に示す処理制御情報のタイプを参照することにより、構文解析実行部２００３から受け取った木構造のうちルート要素を含むものを特定することができる。また、図２１（ａ）に示す処理制御情報の構造の位置を参照することにより、ルート要素を含む木構造に、他の木構造を適切に連結することができる。特に、本実施例における構造の位置は、それぞれの要素の順序を示す。したがって、構造の位置を参照することにより、木構造を正しい順序で連結することができる。本実施例では、／１／１、／１／２、／１／３、／１／４の順に木構造が連結される。このようにして、符号化前の構造化データにおける木構造が再現される。
【０１２３】
木構造がステップＳ２２０９において一時的に要素で囲まれた符号化データから得られている場合、得られた木構造は符号化データには含まれない要素をルート要素として含んでいる。このような場合、並列実行制御部２００１はこの一時的な要素を木構造から取り除いてから連結を行う。
【０１２４】
ステップＳ２３０３において並列実行制御部２００１は、全ての処理結果を構文解析実行部２００３から受け取ったかどうかを判定する。受け取っている場合、処理を終了する。受け取っていない場合、処理はＳ２３０１へ戻り、上述の処理が繰り返される。以上のようにして、並列実行制御部２００１はそれぞれの構文解析実行部２００３に対して並列に構文解析を行わせ、構文解析の結果を連結する。こうして、符号化データの並列な構文解析処理が達成される。
【０１２５】
（他の実施形態）
上述の各実施例においては、構造化データを、並列な構文解析が可能となるように符号化した。しかしながら符号化は必須ではない。例えば、構造化データから上述の処理制御情報を生成し、構造化データと処理制御情報とを他の情報処理装置に提供してもよい。他の情報処理装置は、構造化データと処理制御情報とを用いて、構造化データを並列に構文解析することができる。
【０１２６】
実施例４において構文解析実行部２００３は、符号化データの復号化及び構文解析を行った。しかしながら構文解析実行部２００３は構文解析のみを行ってもよい。この場合、復号化は並列実行制御部２００１、又は他の処理部によって行われうる。この場合、処理制御情報に含まれるデータオフセットは、符号化前の構造化データにおける各データの位置を示していてもよい。
【０１２７】
本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）をネットワーク又は各種記憶媒体を介してシステム或いは装置に供給する。そして、そのシステム或いは装置のコンピュータ（又はＣＰＵやＭＰＵ等）がプログラムコードを読み出して実行する。この場合、そのプログラム、及び該プログラムを記憶した記憶媒体は本発明を構成することになる。
【図１】
2013145472.tif 000003
【図２】
2013145472.tif 000004
【図３】
2013145472.tif 000005
【図４】
2013145472.tif 000006
【図５】
2013145472.tif 000007
【図６】
2013145472.tif 000008
【図７】
2013145472.tif 000009
【図８】
2013145472.tif 000010
【図９】
2013145472.tif 000011
【図１０】
2013145472.tif 000012
【図１１】
2013145472.tif 000013
【図１２】
2013145472.tif 000014
【図１３】
2013145472.tif 000015
【図１４】
2013145472.tif 000016
【図１５】
2013145472.tif 000017
【図１６】
2013145472.tif 000018
【図１７】
2013145472.tif 000019
【図１８】
2013145472.tif 000020
【図１９】
2013145472.tif 000021
【図２０】
2013145472.tif 000022
【図２１】
2013145472.tif 000023
【図２２】
2013145472.tif 000024
【図２３】
2013145472.tif 000025
【図２４】
2013145472.tif 000026
【図２５】
2013145472.tif 000027