(57)【要約】【課題】  XML文書のようなシリアライズされた木構造データの字句・構文解析処理を高速化する文書処理装置を提供する。【解決手段】  木構造データをテキスト形式で表現された文書の文字列データを入力し、入力された文字列からトークン情報を生成する字句解析手段と、字句解析手段から出力されるトークン情報を入力とし、入力されたトークン情報から木構造データを構成するノードを生成する構文解析手段と、字句解析手段と構文解析手段とを１つの組として複数の組から出力されるそれぞれの木構造部分データの結合順序を判断する結合指示手段と、結合指示手段から指示される順に従って複数の木構造部分データを結合する結合手段と、を備える。【選択図】図１
2011165160.tif 000002
【特許請求の範囲】
【請求項１】
木構造データをテキスト形式で表現された文書の文字列データを入力し、入力された文字列からトークン情報を生成する字句解析手段と、
前記字句解析手段から出力されるトークン情報を入力とし、入力された前記トークン情報から木構造データを構成するノードを生成する構文解析手段と、
前記字句解析手段と前記構文解析手段とを１つの組として、複数の組から出力されるそれぞれの木構造部分データの結合順序を判断する結合指示手段と、
前記結合指示手段から指示される順に従って複数の木構造部分データを結合する結合手段と、を具備することを特徴とする文書処理装置。
【請求項２】
請求項１記載の文書処理装置において、
前記字句解析手段は、
前記文書処理装置が処理対象とする文書の一部であり、かつ他部が後半に連続しているデータを入力する入力手段と、
入力データを当該文書の記述規則に則り字句解析し、一定の意味を持つトークン情報を生成するトークン生成手段と、
入力データの最後の部分データを、不完全なままトークンとして出力する一時トークン生成手段と、を具備することを特徴とする文書処理装置。
【請求項３】
請求項１記載の文書処理装置において、
前記字句解析手段は、
前記文書処理装置が処理対象とする文書の一部であり、かつ他部が前半に連続しているデータを入力する入力手段と、
入力データを当該文書の記述規則に則り字句解析し、一定の意味を持つトークン情報を生成するトークン生成手段と、
入力データの最初の部分データを、不完全なままトークンとして出力する一時トークン生成手段と、を具備することを特徴とする文書処理装置。
【請求項４】
請求項３記載の文書処理装置において、
前記字句解析手段は、
解析している最中の認知様相を保持する認知様相記憶手段と、
入力データが認知様相開始を意味する区切り子である場合に、前記認知様相記憶手段に当該区切り子が指定する認知様相を格納する認知様相格納手段と、
入力データが認知様相終了を意味する区切り子であり、前記認知様相記憶手段に保持される認知様相と異なる区切り子である場合に、当該区切り子から生成されるトークン情報を不完全なトークンとして出力する一時トークン生成手段と、を具備することを特徴とする文書処理装置。
【請求項５】
請求項３記載の文書処理装置において、
前記字句解析手段は、
解析している最中の認知様相を保持する認知様相記憶手段と、
入力データが認知様相開始を意味する区切り子である場合に、前記認知様相記憶手段に当該区切り子が指定する認知様相を格納する認知様相格納手段を具備し、
不完全なトークンを出力した後に入力されるデータが認知様相終了を意味する区切り子であり、前記認知様相記憶手段に保持される認知様相と異なる区切り子である場合に、不完全なトークン以降から当該区切り子から生成されるトークン情報までを破棄する手段と、を具備することを特徴とする文書処理装置。
【請求項６】
請求項１記載の文書処理装置において、
前記構文解析手段は、
前記文書処理装置が処理対象とする文書の一部であり、かつ他部が後半に連続しているデータを入力する入力手段を具備し、組となる字句解析手段から出力されるトークン情報を入力する入力手段と、
入力トークン情報の種別を判定し、対応するノードを作成するノード作成手段と、
入力される不完全なトークン情報から不完全なノードを作成する一時ノード作成手段と、を具備することを特徴とする文書処理装置。
【請求項７】
請求項１記載の文書処理装置において、
前記構文解析手段は、
前記文書処理装置が処理対象とする文書の一部であり、かつ他部が前半に連続しているデータを入力する入力手段を具備し、組となる字句解析手段から出力されるトークン情報を入力する入力手段と、
入力トークン情報の種別を判定し、対応するノードを作成するノード作成手段と、
入力される不完全なトークン情報から不完全なノードを作成する一時ノード作成手段と、を具備することを特徴とする文書処理装置。
【請求項８】
請求項７記載の文書処理装置において、
前記構文解析手段は、
仮想的にノードを作成する仮想ノード作成手段と、
組となる字句解析手段から出力されるトークンから生成するノードを仮想ノード作成手段が生成するノードの子ノードとして木構造データを構成する手段と、
前記仮想ノード作成手段が生成する仮想ノードを子ノードとした木構造データを構成する手段と、を具備することを特徴とする文書処理装置。
【請求項９】
請求項１に記載の文書処理装置において、
前記結合手段は、
2つの組が出力した木構造部分データを結合する際に、上位となる木構造データの不完全ノードと下位となる木構造データの複数の不完全ノードに含まれる、もしくは上位となる木構造データの不完全ノードと下位となる木構造データの複数の不完全ノードが指し示す文字列のみを字句解析または構文解析し、正しいトークン情報を生成するトークン修復手段と、
上位となる木構造データの末端に存在するノードの種別に応じて下位となる木構造データとの結合場所を変更する手段と、を具備することを特徴とする文書処理装置。
【請求項１０】
請求項９に記載の文書処理装置において、
前記結合手段は、
2つの組が出力した木構造部分データを結合する際に、上位となる木構造データの末端に存在するノードが、組となる字句解析手段において開始区切り子を意味する文字を契機に作成されたトークンから生成されたノードである場合、上位となる木構造データの末端ノードと下位となる木構造データにおいて、最初に作成した仮想ノードを対応付け、
上位となる木構造データの末端に存在するノードが、組となる字句解析手段において終了区切り子を意味する文字を契機に作成されたトークンから生成されたノードである場合、上位となる木構造データの末端ノードの親ノードと下位となる木構造データにおいて、最初に作成した仮想ノードを対応付け、
上位となる木構造データの末端に存在するノードが、組となる字句解析手段において開始区切り子を意味する文字でなく、終了区切り子を意味する文字でもない文字を契機に作成されたトークンから生成されたノードである場合、上位となる木構造データの末端ノードの親ノードと下位となる木構造データにおいて、最初に作成した仮想ノードを対応付け、
下位となる木構造データにおいて、前述の対応づけされた仮想ノードの親として仮想ノードがある限り、上位となる木構造データにおいて前述の対応付けられたノードの親に対応付けする手段と、を具備することを特徴とする文書処理装置。
【請求項１１】
木構造データをテキスト形式で表現された文書の文字列を入力し、入力された文字列からトークンを生成するとき、前記文書を分割したことにより発生する不完全なトークンを含むトークン情報を生成する字句解析手段と、
前記字句解析手段が生成するトークン情報から部分木構造データを構成するノードを生成するとき、前記不完全なトークンから不完全なノードを生成する構文解析手段と、
前記字句解析手段と前記構文解析手段とを１つの組として、前記組によって生成される部分木構造データを結合して前記文書に対応する木構造データを生成するとき、互いに前後する部分木構造データに含まれる前記不完全なトークンを修復して、前記前後する部分木構造データを結合する結合手段と、を具備することを特徴とする文書処理装置。
【請求項１２】
請求項１１記載の文書処理装置において、
前記文書は、前記文書処理装置が接続するネットワークを経由して取得された文書である
ことを特徴とする文書処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書処理装置に関し、特に、XMLのような構造化データを処理する技術に関する。
【背景技術】
【０００２】
近年のシステム開発ではシステムが複雑化していることを背景に、従来では第一に求められた高性能性でなく保守性や拡張性が求められている。それゆえ、システムで利用する構造化データのフォーマットはRDB （Relational Data Base)におけるテーブル形式や独自の形式から、保守性や拡張性に優れるXML （Extensible Markup Language)に変わりつつある。
【０００３】
XMLはルートとなるノードを頂点に複数のノードが連結され、連結ノードの上下関係によりノード間の親子関係を表現する木構造を持つデータであり、末端でない非終端ノードはデータの意味や構造を記述するために利用され、末端である終端ノードはデータそのものが格納される。XMLの保守性が優れている理由は、XML記述言語が木構造データを人間が読めるテキスト形式に等価に変換できる文書フォーマット定義言語であるからである。また、XMLの拡張性が優れている理由は、XMLにアクセスするためのAPI（Application Program Interface）が標準仕様として用意されており、データの追加や削除、修正が容易に行えるためである。
【０００４】
コンピュータシステム（以下コンピュータ)がXML文書をデータとして利用する場合、テキスト形式で表現されるXML文書をコンピュータが解析可能なフォーマットであるバイナリ形式に変換する必要がある。前述の変換処理は大きくXML文書の字句解析、および構文解析の2つから構成される。XML文書の字句解析処理は次の処理を意味する。XML文書を1文字ずつ読み込みトークンと呼ばれる一定の意味を持つ集合体を生成することである。"＜a b＝c＞XXX＜／a＞"というXML文書の一部は、属性名および属性値を含む開始要素トークンである"a （b＝c)"、文字トークンである"XXX"、終了要素トークンである”a”となる。
【０００５】
続けて、XML文書の構文解析処理は次の処理を意味する。生成したトークンからツリーデータを構成するノードを作成し、それらノードの集合としてツリーデータを生成する。具体的には、ツリーデータ生成とはトークン間の関係性をツリーデータ構造で表現することであり、ツリー構造の構成要素であるノードの作成とノード間の接続を行う。今後システムで利用するデータの主流がXML形式になると必然にXML文書の字句・構文解析処理に時間がかかることになり、現在と比較してシステム性能が低くなる可能性がある。この問題を解決すべく複数の手法が提案されている。
【０００６】
第一の従来手法として、特許文献1のようにテキスト形式のXML文書の全てもしくはその一部を事前にバイナリフォーマットとして用意しておき、その用意したバイナリデータを利用して構文解析を実行することで、字句解析にかかる時間を短縮する手法がある。
【０００７】
第二の従来手法として、非特許文献1のようにXML文書の字句解析処理が複数の処理ステージに分割できることに着目し、各ステージをパイプライン化し並列処理することでXML文書の字句解析を高速にする手法である。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００９−１６３６９０号公報
【非特許文献】
【０００９】
【非特許文献１】Hybrid Parallelism for XML SAX Parsing. Yinfei Pan, Kenneth Chiu, IEEE International Conference on Web Services, 2008, IEEE Conference Proceeding,  pages 505-512.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、特許文献1記載の技術では、テキスト形式のXML文書の全てもしくは一部に対応するバイナリデータを事前に用意しておく必要があり、未知のXML文書では高速化が困難である課題がある。
【００１１】
また、非特許文献1記載の技術では、処理の数でしか分割することができないため、分割できる処理ステージ数は高々数個であり、並列化にも限界があり、ひいては高速化効果の上限が低いという課題がある。
【００１２】
本発明は、上述の課題を考慮してなされたものであり、XML文書の字句・構文解析処理を高速化する手段を提供することである。
【課題を解決するための手段】
【００１３】
上述の課題を解決するために、本発明の文書処理装置は以下の構成を備える。即ち、木構造データをテキスト形式で表現された文書の文字列データを入力し、入力された文字列からトークン情報を生成する字句解析手段と、字句解析手段から出力されるトークン情報を入力とし、入力されたトークン情報から木構造データを構成するノードを生成する構文解析手段と、字句解析手段と構文解析手段とを１つの組として複数の組から出力されるそれぞれの木構造部分データの結合順序を判断する結合指示手段と、結合指示手段から指示される順に従って複数の木構造部分データを結合する結合手段と、を備える。
また、本発明の文書処理装置は以下の構成を備える。即ち、木構造データをテキスト形式で表現された文書の文字列を入力し、入力された文字列からトークンを生成するとき、前記文書を分割したことにより発生する不完全なトークンを含むトークン情報を生成する字句解析手段と、前記字句解析手段が生成するトークン情報から部分木構造データを構成するノードを生成するとき、前記不完全なトークンから不完全なノードを生成する構文解析手段と、前記字句解析手段と前記構文解析手段とを１つの組として、前記組によって生成される部分木構造データを結合して前記文書に対応する木構造データを生成するとき、着目する部分木構造データと前後する部分木構造データに含まれる前記不完全なトークンを結合する結合手段と、を備える。
本発明の文書処理装置は、特許文献１に示す技術とは異なり、XML文書が既知であれ未知であれ処理することができる。また、特許文献２に示す技術とは異なり、分割するのは処理ステージ数ではなく、文書の文字列であるので、分割の回数制限は極めて弱いものであり、処理の並列化に対する限度はほとんど無い。
【発明の効果】
【００１４】
本発明によれば、XML文書の解析処理を高速化することが可能となる。
【図面の簡単な説明】
【００１５】
【図１】本発明の第一の実施形態を示すブロック図である。
【図２】字句処理部の詳細を示す図である。
【図３】構文解析部の詳細を示す図である。
【図４】字句解析部の実施処理フローを示す図である。
【図５】字句解析部の第2の実施処理フローを示す図である。
【図６】構文解析部の実施処理フローを示す図である。
【図７】構文解析部の第2の実施処理フローにおける事前処理を示す図である。
【図８】構文解析部の第2の実施処理フローを示す図である。
【図９】結合部の実施処理フローを示す図である。
【図１０】本発明の第二の実施形態を例示するブロック図である。
【図１１】文書処理装置制御部の実施処理フローを例示する図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について説明する。
【００１７】
≪第一の実施形態≫
まず、図面を用いて本発明の第一の実施形態を詳細に説明する。なお、全図に示す同一の番号は同一の機能を持つため説明を省略する。
【００１８】
図1は本発明の一実施形態に係るXML文書処理装置を示す構成図である。図1はCPU 100とXML文書処理装置101と第一記憶装置102で構成され、CPU 100とXML文書処理装置102と第一記憶装置102は内部バス103で接続されている。
【００１９】
CPU 100はXML文書を外部ネットワークや第二記憶装置であるハードディスクドライブなどから取得し第一記憶装置102に格納するといった処理を行うソフトウェアの実行を担当する。
【００２０】
XML文書処理装置101はI／O 200と字句解析部0 201と構文解析部0 202と字句解析部1 203と構文解析部1 204と字句解析部N 205と構文解析部N 206と、結合指示部207と結合部208で構成される。
【００２１】
I／O 200は字句解析部0 201〜字句解析部N 205、構文解析部0 202〜構文解析部N 206、結合部208と、内部バス103間を接続しデータ転送処理を制御する。
【００２２】
字句解析部0 201〜字句解析部N 205はI／O 200から転送されるXML文書の文字列を入力とし、トークンを出力する。字句解析部0 201〜字句解析部N 205の詳細は別途図2を、詳細な処理フローを図4および図5を用いて行う。
【００２３】
構文解析部0 202、構文解析部1 204、構文解析部N 206はそれぞれ字句解析部0 201、字句解析部1 203、構文解析部N 205から出力されるトークン情報を入力とし、I／O 200へ生成したノード情報を出力する。構文解析部0 202〜構文解析部N 206の詳細は別途図3を、詳細な処理フローを図6〜図8を用いて行う。
【００２４】
結合指示部207は構文解析部0 202〜構文解析部N 206それぞれから出力される処理完了通知を入力とし、結合部208に処理依頼を発行する。具体的には、XML文書の先頭からN-1分割したデータ（以下XMLチャンクデータとする）が字句解析部0 201、字句解析部1 203から字句解析部N 205の順に割り振られる時、構文解析部0 202と構文解析部1 204が処理を終了した際に初めて、結合部208が処理する上で必要な情報を結合部208に転送すると共に、結合部208に処理依頼通知を発行する。続けて、構文解析部0 202と構文解析部1 204、構文解析部2が処理を完了した時点で、次の処理依頼を結合部208に発行する。つまり、構文解析部に振られている番号が若い順に結合指示を発行し、例えば、構文解析部1 204と構文解析部N 206から処理完了通知が入力され、構文解析部0 202から処理完了通知が発行されていなければ、結合指示部207は結合部208に処理依頼を発行しない。
【００２５】
結合部208は結合指示部207の処理依頼を受け、I／O 200から2つのノード群データ（ツリーデータ）を入力し、2ツリーデータの結合を行う。結合部の詳細な説明は別途図9を用いて行う。
【００２６】
第一記憶装置102はCPU 100やXML文書処理装置101で利用するデータを格納する。本実施形態では、XML文書処理装置101のI／O 200を経由して字句解析部0 201に入力される字句解析部0用XMLテキスト250と、XML文書処理装置101のI／O 200を経由して字句解析部1 203に入力される字句解析部1用XMLテキスト251と、XML文書処理装置101のI／O 200を経由して字句解析部N 205に入力される字句解析部N用XMLテキスト252が第一記憶装置102に格納されている。また、XML文書処理装置101のI／O 200を経由して構文解析部0 202より出力される構文解析部0用部分ツリーデータ253と、XML文書処理装置101のI／O 200を経由して構文解析部1 204より出力される構文解析部1用部分ツリーデータ254と、XML文書処理装置101のI／O 200を経由して構文解析部N 206より出力される構文解析部N用部分ツリーデータ255を格納するための領域が確保されている。
【００２７】
続けて、図2を用いて字句解析部0 201および字句解析部1 203から字句解析部N 205の内部の説明を行う。図2は字句解析オートマトン300と認知モデルスタック301とトークンバッファ302で構成される。なお、本実施形態では説明を明確にするために、字句解析部0 201の字句解析オートマトン300と、字句解析部1 203から字句解析部N 205の字句解析オートマトン300の内容が異なる。これは、本実施形態においては、字句解析部0 201を文書の先頭から一定サイズの文字列を処理する手段としており、字句解析部1 203から字句解析部N 205をそれぞれm-1（mは1からNまでの任意の数）番目のXML文書の一部の文字列を処理する手段としているためであり、XML文書の順を問わず処理可能な、具体的には、字句解析部0 201の字句解析オートマトン300と、字句解析部1 203から字句解析部N 205までの字句解析オートマトン300の組合せを字句解析部0 201から字句解析部N 205全てに実装しても良い。
【００２８】
字句解析オートマトン300は、入力される文字データおよび認知モデルスタック301に保持される認知モデルを引数にトークンを生成し、トークンバッファ302に生成したトークンを格納し、外部に対して生成したトークンを出力する制御部となる。
認知モデルスタック301は、XML文書の解析の状態を保持しておくバッファであり、”＜a＞XXX＜／a＞”といったXML文書の一部データにおいて先頭から解析する場合、開始タグ内、テキスト内、終了タグ内の順で認知モデルが変化する。なお、説明を明確にするために名称をスタックとしているが、データ構造上のスタック（FILO）でなくても構わない。
【００２９】
トークンバッファ302は字句解析オートマトン300が生成するトークン情報を一時格納する手段であり、字句解析オートマトン300より当該トークンバッファ302に保持されるトークン情報が出力される際にクリアされる。
【００３０】
続けて、図3を用いて構文解析部0 202および構文解析部1 204から構文解析部N 206の内部の説明を行う。図3は構文解析オートマトン310と親ノードスタック311とノードバッファ312で構成される。なお、本実施形態では説明を明確にするために、構文解析部0 202の構文解析オートマトン310と、構文解析部1 204から構文解析部N 206の構文解析オートマトン310の内容が異なる。これは、本実施形態においては、構文解析部0 202を文書の先頭から一定サイズの文字列から生成されるトークンを処理する手段としており、構文解析部1 204から構文解析部N 206をそれぞれm-1（mは1からNまでの任意の数）番目のXML文書の一部の文字列から生成されるトークンを処理する手段としているためであり、XML文書の順を問わず処理可能な、具体的には、構文解析部0 202の構文解析オートマトン310と、構文解析部1 204から構文解析部N 206までの構文解析オートマトン310の組合せを構文解析部0 202から構文解析部N 206全てに実装しても良い。
【００３１】
構文解析オートマトン310は、入力されるトークンデータおよび親ノードスタック311に保持される親ノード情報を引数にノードおよびノード間の接続情報を生成し、ノードバッファ312に生成したノードを格納し、外部に対して生成したノードを出力する制御部となる。
【００３２】
親ノードスタック311は、現在解析中のノードがどのノードの配下に接続されるかといった情報を保持しておくバッファである。なお、説明を明確にするために名称をスタックとしているが、データ構造上のスタック（FILO）でなくても構わない。
【００３３】
ノードバッファ312は構文解析オートマトン310が生成するノード情報を一時格納する手段であり、構文解析オートマトン310より当該ノードバッファ312に保持されるノード情報が出力される際にクリアされる。
【００３４】
続けて、図4を用いて字句解析部0 201の処理フローを説明する。字句解析部0 201は第一記憶装置102に格納される字句解析部0用XMLテキスト250をトークン化するに当たり、字句解析部0用XMLテキスト250が格納されるアドレスや字句解析部0用XMLテキスト250のサイズ、文字コードなど解析に必要な情報が与えられ処理を開始する（400）。なお、字句解析部0 201が入力するデータである字句解析部0用XMLテキスト250を第一記憶装置102上に配置しているが、字句解析部0用XMLテキスト250の格納場所を限定する物ではない。
【００３５】
まず、認知モデルスタックSの0番目であるS[0]に認知モデルPCDATAを設定する（401）。ここでPCDATAとは解析可能な文字列であることを意味する認知モデルとしている。さらに、認知モデルスタックの1要素を示すポインタpSを0番目の要素を指すよう設定する（402）。続けて、400にて設定される字句解析部0用XMLテキスト250の文字列サイズを全て処理したかどうか確認し（403）、全て処理していなければ1文字だけ字句解析部0用XMLテキスト250からデータを読み込む（404）。なお、説明を明確にするため、第一記憶装置102から1文字ずつ読み込むように記載しているが、複数文字をまとめて読み込み、XML文書処理装置101内でバッファしても良い。404にて読み込まれた文字が開始文字に該当すれば（405）、トークンバッファが空であるかどうかをチェックし（406）、空でなければ、トークンバッファに格納されるトークン情報を構文解析部0 202に出力する（407）。その後以前に設定された認知モデルを削除する（408）。ここで406にてトークンバッファが空であれば407および408は実行されない。なお、開始文字とは、認知モデルの開始を指示する区切り子であり、XMLではタグの開始を意味する”＜”、処理命令の開始を意味する"＜!"、コメントの開始を意味する"＜−−"などが開始文字に該当する。続けて、pSに当該開始文字の認知モデルをバッファし（409）、これから作成する予定のトークンの種別を識別するために使用されるトークン種別に、pSが指すSの要素の値を設定する。その後、次の文字を読み込む処理（403）に戻る。
【００３６】
入力される文字が開始文字でなく終了文字である場合（411）、先の407と同様にトークンバッファに格納されるトークン情報を構文解析部0 202に出力し、以前に設定された認知モデルを削除する（408）。ここで終了文字とは、認知モデルの終了を指示する区切り子であり、XMLではタグの終了を意味する"＞"、マーク宣言の終了を意味する"]]"、コメントの終了を意味する"−−＞"などが終了文字に該当する。
【００３７】
入力文字が開始文字でも終了文字でもない場合、トークンバッファ302に保持されているトークン情報を更新すべく、トークンを構成する文字列情報に入力文字を追加する（412）。
【００３８】
403にて用意された文字列を全て処理したのであれば、トークンバッファ302が空であるかを確認し、空でなければ、現在pSに設定されている認知モデルが完了していないことを意味するため、トークンに終端不完全フラグを付加し（413）、407と同様にトークンを出力し、処理を完了する。
【００３９】
続けて、図5を用いてXML文書の先頭でないチャンクデータを処理する字句解析部1 203から字句解析部N 205の処理フローを説明する。字句解析部1 203から字句解析部N 205は第一記憶装置102に格納される字句解析部1用XMLテキスト251から字句解析部1用XMLテキスト252をトークン化するに当たり、字句解析部1用XMLテキスト251から字句解析部N用XMLテキスト252が格納されるそれぞれのアドレスや字句解析部1用XMLテキスト251から字句解析部N用XMLテキスト252のそれぞれのサイズ、文字コードなど解析に必要な情報が与えられ処理を開始する（450）。なお、字句解析部1 203から字句解析部N 205が入力するデータである字句解析部1用XMLテキスト251から字句解析部N用XMLテキスト252を第一記憶装置102上に配置しているが、字句解析部1用XMLテキスト251から字句解析部N用XMLテキスト252の格納場所を限定する物ではない。
【００４０】
以後、字句解析部1 203から字句解析部N 205は同じ処理フローとなるため、字句解析部N 205を代表に説明する。
【００４１】
まず、字句解析部N 205はS[0]に仮想認知モデルを設定する（451）。ここで仮想認知モデルは、字句解析部N 205に入力される文字列である字句解析部N用XMLテキスト252の1つ前のチャンクデータを解析する字句解析部N-1が最後に出力するトークンの認知モデルが不明であるため、仮の認知モデルとして用意するものであり、本実施形態ではPCDATAと同様の認知モデルとしている。続けて402の設定、403の字句解析部N用XMLテキスト252のサイズ確認を行い、404にて1文字読み込む。読み込んだデータが開始文字である場合は図4と同様であり省略する。
【００４２】
読み込んだ文字がpSの指す認知モデルに対応する終了文字である場合（452）、例えば、直前に読み込んだ開始文字がコメントの開始を意味する区切り子"＜−−"であった場合、対応する終了文字とはコメントの終了を意味する区切り子"−−＞"となる。なお、図5において404では1文字読み込み、複数文字で構成される開始・終了文字を判定しているが、これはトークンバッファ302に保持している文字列を使用しているからに過ぎない。452が真であれば図4における411が真である場合と同様に407と408を実行する。
【００４３】
続けて、pSの指す認知モデルに対応しない終了文字である場合（453）、例えば、字句解析部N-1が処理する字句解析部N用XMLテキスト252の一つ前のチャンクデータから、字句解析部Nが処理する字句解析部N用XMLテキスト252にまたがり"＜−−  open angle brackets is ＜ −−＞"のようなコメントが配置され、字句解析部N用XMLテキスト252の先頭が前述の例の"is"の直前であったとすると、字句解析部N 205は、字句解析部N-1の最後のトークンの認知モデルが不明であるため、その後続く"＜"を誤って開始文字として認識してしまい、その後に続く"−−＞"で453のケースが発生する。この時、認知モデルスタック301が空でなければ、つまり、451にて設定された仮想認知モデルが有効であれば、現在解析中のトークンは先端が不完全であるため、先端不完全フラグをトークンに付加し（413）、407と同様にトークンを出力する。その後、pSがS[0]を指しているのであれば、何も指さないポインタとなり、pSがS[0]でなくその他の要素を指している、つまり認知モデルスタック301に過去に有効となった認知モデルが入っていればpSをデクリメントする（456）。なお、pSの指す認知モデルに対応しない終了文字である場合（453）、認知モデルスタックが空である、例えば、字句解析部N-1が処理する字句解析部N用XMLテキスト252の一つ前のチャンクデータから、字句解析部Nが処理する字句解析部N用XMLテキスト252にまたがり"＜−−  close angle brackets is ＞ −−＞"のようなコメントが配置され、字句解析部N用XMLテキスト252の先頭が前述の例の"is"の直前であったとすると、まず"＞"が読み込まれた時点で451にて設定した仮想認知モデルが利用され、その後続く" −−＞"はどの認知モデルにも対応しない状態となる。この状態を回避するために、認知モデルスタック301が空であるかを確認し（454）、454が真であれば451および402を実施し、続く407にて出力する予定のトークンのトークン種別をpSの指すSの要素の値に設定する（410）。
【００４４】
前述の認知モデルのない文字列が発生してしまう問題は読み込んだ文字が開始・終了文字のいずれでもない場合も発生するため、454、451、402、410を行い、その後413、412を実行する。
【００４５】
続けて、図6を用いて構文解析部0 202の処理フローを説明する。
【００４６】
構文解析部0 202の前段である字句解析部0 201からトークンが入力されると（500）、親ノードスタックNの0番目の要素であるN[0]を指すようポインタpNを設定する（501）。
続けて、入力されるトークンが開始トークンか（502）、終了トークンか（508）、それ以外かを判断する。なお、開始トークンは開始区切り子を契機に生成されたトークンを意味しており、同様に終了トークンは終了区切り子を契機に生成されたトークンを意味している。
【００４７】
入力されるトークンが開始トークンである場合、構文解析部0 202は入力されるトークンからノードを生成し、構文解析部0部分ツリーデータ253の指すアドレス空間に配置していく（503）。ここでノードはトークン種別情報から生成されるノード種別情報、ノードが要素を含むノードであればノード名情報、および属性情報、自ノードの配下にぶら下がる子ノードへのブランチ（ポインタ)情報などにより構成される。
【００４８】
503にてノードを生成した後、親ノードスタック311が空であるか確認し（504）、空であれば最初に生成されるノードであり現在解析中のXML文書のルートノードとなる。一方、親ノードスタック311が空でなければ、先ほど生成したノードの親ノードが格納されている場所を指すpN - 1にポインタpを設定し（505）、pにより指定される親ノードに、先ほど作成したノードを子ノードとするためにブランチ（ポインタ)を設定する（506）。なお、本実施形態では説明の簡略化のため、親ノードの設定の度に親ノードを第一記憶装置102より読み出し、編集後第一記憶装置102に書き出すようにしているが、データアクセス方法は上記に限らない。最後に、503にて生成したノードを以降に続くノードの親とすべく、親ノードスタック311に格納する（507）。なお、本実施形態では説明の簡略化のため、親ノードスタック311にノードをそのまま格納しているが、低コスト化に向け必要な情報のみ格納しても良い。
【００４９】
入力されるトークンが終了トークンである場合、503、505、506を実施し、対応する開始ノードを親としておく必要がなくなったため、対応する開始ノードが格納されている親ノードスタック311から削除する（509）。
【００５０】
入力されるトークンが開始・終了トークンのいずれでもない場合、まず、先端不完全フラグが付加されたトークンかを確認し（510）、510が真であればノードにも先端不完全フラグを付加する（511）。その後、503、505、506を実施する。
【００５１】
続けて、図7および図8を使用して、XML文書の先頭でないチャンクデータから生成されたトークン群を処理する構文解析部1 204から構文解析部N 206の処理フローを説明する。
【００５２】
以後、構文解析部1 204から構文解析部N 206は同じ処理フローとなるため、構文解析部N 206を代表に説明する。
【００５３】
図7は、構文解析部N 206の初期化フローをさしており、この処理は構文解析部N 206に字句解析部N 205からトークンが入力されるより先に行われる。
【００５４】
まず、501にてpNを親ノードスタックNの0番目の要素に設定した後、仮想ノードを生成し、第一記憶装置102の構文解析部N部分ツリーデータが示すアドレス空間に出力する（551）。ここで仮想ノードとは、構文解析部N-1の担当する字句解析部N用XMLテキスト252の一つ前のチャンクデータの最後に生成されるノードを想定して配置される仮想的なノードである。
【００５５】
続けて、構文解析部N 206はまず551にて生成した仮想ノードを親ノードとしてノードを生成していくため、551にて生成したノードをpNに格納する（552）。
図7に続き、構文解析部N 206は字句解析部N 205の出力するトークンを入力し図8に示す処理を行う。
【００５６】
開始トークンであれば（502）、図6と同様の処理を行うため説明を省略する。
【００５７】
終了トークンであれば（508）、503、505、506まで図6と同様の処理を行い、その後親ノードスタック311の仮想ノードが有効であるかを確認し（561）、親ノードスタック311に現在親としているノードのみが入っていれば、新規に仮想ノードを作成し（562）、作成した新規仮想ノードnにｐN、つまり現在親としている仮想ノードを子ノードとするためにnにpNへのブランチ（ポインタ)を追加し、第一記憶装置102の構文解析部N部分ツリーデータが指すアドレス空間に出力する（563）。その後、現在親としている仮想ノードを親ノードスタック311から削除し（509）、先ほど新規に作成したnを親ノードスタック311に挿入する（507）。これは、構文解析部N 206に、開始トークンを間に挟まずに終了トークンが複数回入力される時に、現在親としているノードのさらに1つ上位の親ノードを仮想的に参照する必要があるために行われる。
【００５８】
入力されるトークンが開始・終了トークンのいずれでもない場合は図6と同様であり説明を省略する。
【００５９】
図9を用いて結合部208の処理フローを説明する。
【００６０】
結合指示部207からの指示を受け、結合部208は2種のツリーデータに関する情報を受け取る（600）。2種のツリーデータはXML文書処理装置101が処理するXML文書の連続したチャンクデータから生成されたツリーデータ、もしくは結合部208により既に結合されたツリーデータとそのツリーデータの元となったチャンクデータ群と連続しているチャンクデータから生成されたツリーデータに関する。
【００６１】
以下では、連続するツリーデータのうち、上位に位置するツリーデータを上位ツリーデータ、下位に位置するツリーデータを下位ツリーデータとする。
【００６２】
結合部208は、上位ツリーデータの末端ノード、つまり上位ツリーデータを生成した構文解析部が出力した最後のノードに終端不完全フラグが付加されているかを確認し（601）、601が真であればその不完全フラグのついたノードを修復する（602）。具体的には、下位ツリーデータに必ず含まれる先端不完全フラグの付加されたノード群に含まれる文字列を使い、不完全フラグの付加されたノードに関して再度字句・構文解析を実施し完全なノードを作成する（602）。なお、不完全フラグの付加されたノードに関して二重に字句・構文解析を行うことになるが、字句・構文解析部（字句解析部と構文解析部を組合せたときの名称）の並列数N+1-1であるN個のノードに関して二重に字句・構文解析を行うだけであり、さらに、通常のXML文書は1ノードに含まれる文字数は長くても30文字程度でありたいした負荷にはならない。さらに、上記にて「下位ツリーデータに必ず含まれる先端不完全フラグの付加されたノード群」と記載したのは、例えば、XML文書の連続したチャンクデータにおいて"＜−−  close angle brackets is ＞, not round bracket. −−＞"のようなコメントがまたがり配置され、後半のチャンクデータの先頭が"is"の直前であったとすると、続く"＞"までの文字列を含むノードと、"＞"から"−−＞"までの文字列を含むノードが2つ不完全フラグの付加されたノードとなるからである。
【００６３】
続けて、不要となった下位ツリーデータに含まれる不完全フラグの付加されたノードを子に持つ親ノードの該当ブランチ（ポインタ)を削除する（603）。なお、前述の親ノードの探索方法は限定しない。
【００６４】
以後、上位ツリーデータの末端ノードが開始ノードか（604）、終了ノードか（610）、それ以外かを判定し、開始ノードであれば上位ツリーデータの1ノードを指すポインタupperを上位ツリーデータの末端ノードに設定し、下位ツリーデータの1ノードを指すポインタlowerを下位ツリーデータの先頭ノードの親ノードに設定する（605、606）。同様に、終了ノードであればupperを上位ツリーデータの末端ノードの2つ上の親ノードに、lowerを下位ツリーデータの先頭ノードの親ノードに設定し（611、612）、開始・終了ノードのいずれでもない場合、upperを上位ツリーデータの末端ノードの親ノードに、lowerを下位ツリーデータの先頭ノードの親ノードに設定する（613、614）。これは、上位ツリーデータの末端ノードが開始ノードか、終了ノードか、それ以外かにより、下位ツリーデータに含まれる仮想ノードをマップする先の上位ツリーデータのノードが異なるからである。
【００６５】
続けて、upperが指すノードにlowerの子ノードを追加し（607）、lowerを子に持つ親（仮想）ノードが存在するか確認し（608）、608が真であればupperに現在のノードの親ノードを設定し、lowerに現在のノードの親ノードを設定し607を実行する（609）。607〜609を繰り返し全ての仮想ノードのマッピングが終了すれば、結合部208に入力される2つのツリーデータの結合は完了する（615）。
【００６６】
上述の構成により、XML文書処理装置101は内部に有する字句・構文解析部の組合せの数だけXML文書を並列に字句・構文解析することが可能になる。
【００６７】
以上のように、上述した実施形態によれば、未知のXML文書を含めてXML文書の字句・構文解析を高速に処理でき、またXML文書のサイズひいてはXML文書を構成する文字集合内の文字数以外の制約なしにXML文書の字句・構文解析処理を並列化することで、XML文書の字句・構文解析処理を高速化することが可能となる。
【００６８】
≪第二の実施形態≫
以下、図面を用いて本発明の第二の実施形態を説明する。なお、全図に示す同一の番号は同一の機能を持つため説明を省略する。また、本実施形態の説明は第一の実施形態の差分の説明とする。
【００６９】
本実施形態では、ネットワークを経由してネットワーク装置104が受信したXML文書を文書処理装置制御部700が受信し、文書処理装置701がXML文書の字句解析および構文解析を実行することを想定している。通常、インターネットへの接続で使用されているTCP（Transmission Control Protocol）プロトコルを用いてネットワークを経由してデータを送受信する際、送受信されるデータは複数のパケットに分割され送信されるが、パケットデータの送信順とパケットの受信順が同一であることは保障されない。つまり、XML文書をTCPプロトコルでネットワークを経由して受信する場合、XML文書は複数に分割されており、さらにそのXML文書の分割データ受信順はXML文書の内容順であるとは限らない。
【００７０】
図10は本発明の第二の実施形態に係る文書処理装置を示す構成図である。図1と異なり、XML文書処理装置101が文書処理装置701に置換され、CPU100で動作するソフトウェアとして文書処理装置制御部700を、ネットワークとの接続を制御するネットワーク装置104を追加した。また、第一記憶装置102に格納されるデータである、木構造データ文書部分データ0 720は、図1の字句解析部0用XMLテキスト250と同等であり、同様に、木構造データ文書部分データ1 721は、図1の字句解析部1用XMLテキスト251と同等、木構造データ文書部分データN 722は、図1の字句解析部N用XMLテキスト252と同等、木構造データ部分データ0 723は、図1の構文解析部0部分ツリーデータ253と同等、木構造データ部分データ1 724は、図1の構文解析部1部分ツリーデータ254と同等、木構造データ部分データN 725は、図1の構文解析部N部分ツリーデータ255と同等である。また、説明を容易にするために、CPU100、第一記憶装置102、ネットワーク装置104および文書処理装置701を含むコンピュータを、文書処理システム10の一部装置群として記載した。
【００７１】
文書処理装置701は、I/O部702と、字句解析部703と、構文解析部704と、結合部705で構成される。なお、I/O部702は図1のI/O200と、字句解析部703は図1の字句解析部201 0、203 1、・・・205 N（のうち一つ）と、構文解析部704は図1の構文解析部202 0、204 1、・・・206 N（のうち一つ）と、結合部705は図1の結合部208と同等である。
【００７２】
図11を用いて、文書処理装置制御部700のフローを説明する。文書処理装置制御部700は、処理を開始後(S10)、ネットワーク装置104を経由して、XML文書の全データを受信したかを判断し(S11)、全データ未受信であればXML文書の（部分）データを受信し、木構造データ文書部分データ720〜722のいずれかに格納する(S12)。その後、S12で受信したXML文書の部分データに関して、文書処理装置701に木構造データ文書部分データの字句・構文解析を依頼する(S13)。
【００７３】
図11では、文書処理装置701が字句・構文解析を完了すると、文書処理装置制御部700は、文書処理装置701から処理終了通知を受信し(S14)、S14で生成した（文書処理装置701の字句・構文解析により生成した）木構造データ部分データ723〜725に直接に前後する木構造データ部分データが既に生成済みかを確認する(S15)。直接に前後する木構造データ部分データが既に生成済みであれば、文書処理装置701にS14で生成した木構造データ部分データと前後する木構造データ部分データの結合を文書処理装置701に依頼する(S16)。文書処理装置701では結合部705により、木構造データ部分データの結合が実行され、その実行結果は木構造データ部分データ723〜725として格納される。木構造データ部分データの結合において、不完全なトークンが含まれているときは、着目する木構造データ部分データと前後する木構造データ部分データとを、第一の実施形態に示した処理により結合する。
【００７４】
その後、S11に戻りXML文書全データを受信したら処理を終了する(S17)。その結果、すべての木構造データ部分データが結合した木構造データが生成する。なお、図11では、S13終了後S14の処理終了通知を待つフローとしているが、S13終了後S11に戻る処理と、S14の通知を割込みなど通知手段により検知しS15とS16の処理を並行に実行しても良い。
【００７５】
また、本実施形態は文書処理装置701にハードウェアを想定しているが、ソフトウェアとして実装しても良い。この実装は、第一の実施形態についても同様である。
【００７６】
本実施形態により、XML文書全データの受信が完了し、XML文書の内容順にXML文書を整形し、XML文書の字句・構文解析を実施する従来手法に対して、XML文書の受信順に依存せず、XML文書の受信順にXML文書の字句・構文解析を実行でき、XML文書の整形にかかる処理時間およびXML文書の受信にかかる待ち時間を削減できる。
【００７７】
なお、前記した実施形態は、本発明を実施するための好適なものであるが、その実施形式はこれらに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形することが可能である。
【００７８】
例えば、本実施形態では、木構造データを構成する文書としてXML文書を採り上げたが、HTML（Hyper Text Markup Language）文書であっても良い。
【００７９】
また、本実施形態では、文書を分割してXMLチャンクデータを作成するとき、その分割の方法に特に決まりを定める必要は無いものとして説明した。特に決まりを定めてはいないので、分割の方法に関するアルゴリズムを作成し、XML文書処理装置101に具備させる必要も無い分、文書を分割の処理に関するXML文書処理装置101の負荷を軽減することができたり、そのアルゴリズムの開発コストを削減したりすることができる。しかし、文書の特性（例：タグの位置、タグの階層性、一文の長さ）を割り出し、その特性に応じた最適な分割を実行するアルゴリズムを開発して、XML文書処理装置101に具備することにより、字句・構造解析の更なる高速化を実現することができる。
【００８０】
その他ハードウェア、ソフトウェア、等の具体的な構成について、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【００８１】
１００  CPU
１０１  XML文書処理装置
１０２  第一記憶装置
１０３  バスなどの内部信号線（内部バス）
１０４  ネットワーク装置
２００  （XML文書処理装置内）I／O
２０１  （XML文書処理装置内）字句解析部0
２０２  （XML文書処理装置内）構文解析部0
２０３  （XML文書処理装置内）字句解析部1
２０４  （XML文書処理装置内）構文解析部1
２０５  （XML文書処理装置内）字句解析部N
２０６  （XML文書処理装置内）構文解析部N
２５０  （第一記憶装置内）字句解析部0用XMLテキスト
２５１  （第一記憶装置内）字句解析部1用XMLテキスト
２５２  （第一記憶装置内）字句解析部N用XMLテキスト
２５３  （第一記憶装置内）構文解析部0部分ツリーデータ
２５４  （第一記憶装置内）構文解析部1部分ツリーデータ
２５５  （第一記憶装置内）構文解析部N部分ツリーデータ
３００  （字句解析部内）字句解析オートマトン
３０１  （字句解析部内）認知モデルスタック
３０２  （字句解析部内）トークンバッファ
３１０  （構文解析部内）構文解析オートマトン
３１１  （構文解析部内）親ノードスタック
３１２  （構文解析部内）ノードバッファ
７００  文書処理装置制御部
７０１  文書処理装置
７０２  （文書処理装置内）I/O
７０３  字句解析部
７０４  構文解析部
７０５  結合部
７２０  木構造データ文書部分データ0
７２１  木構造データ文書部分データ1
７２２  木構造データ文書部分データN
７２３  木構造データ部分データ0
７２４  木構造データ部分データ1
７２５  木構造データ部分データN
【図１】
2011165160.tif 000003
【図２】
2011165160.tif 000004
【図３】
2011165160.tif 000005
【図４】
2011165160.tif 000006
【図５】
2011165160.tif 000007
【図６】
2011165160.tif 000008
【図７】
2011165160.tif 000009
【図８】
2011165160.tif 000010
【図９】
2011165160.tif 000011
【図１０】
2011165160.tif 000012
【図１１】
2011165160.tif 000013