(57)【要約】【課題】値のみが異なる共通の構造を持つＸＭＬ文書に対するＤＯＭ木に対する使用メモリ量を削減する。【解決手段】構造化文書処理装置１０１は、共通部分認識部１０３により、ＸＭＬ文書１０２に指定された構造情報を解析し、複数回出現する可能性のある構造を認識する。次に、木データ作成部１０４は、共通部分認識部１０３が特定した構造を認識しながら、ＸＭＬ文書１０２のデータ部分に対する木データを作成し、オブジェクト管理部１０５に保持する。オブジェクト管理部１０５は、データを、木データ１０６、値管理表１０７、共通木管理表１０８の３つのデータ構造で保持する。木データ操作部１０９では、ユーザアプリケーション１１１に対して、ＤＯＭ ＡＰＩを提供する。【選択図】図１
2008140157.tif 000002
【特許請求の範囲】
【請求項１】
構造化文書を入力して、この構造化文書に含まれる複数回出現する可能性のある構造を認識する共通部分認識部と、
前記構造化文書と前記共通部分認識部の認識結果とを入力して、前記構造化文書中に共通構造を検出したとき、前記共通構造に対する木データを生成し、この木データの共通構造に一致する部分に参照ノードを生成する木データ作成部と、
前記木データ作成部が生成したオブジェクトを格納するオブジェクト管理部と、
ユーザアプリケーションからの指示に従って、前記オブジェクトを処理する木データ操作部とを備え、
前記木データ操作部は、共通構造を参照するノードを参照する際は、共通構造を展開することを特徴する構造化文書処理装置。
【請求項２】
請求項１に記載の構造化文書処理装置であって、
前記共通部分認識部は、前記構造化文書を定義する構造定義を解析することを特徴とする構造化文書処理装置。
【請求項３】
請求項１に記載の構造化文書処理装置であって、
前記共通部分認識部は、前記構造化文書を定義する構造定義に記載された内容に従って、前記構造化文書の構造を特定することを特徴とする構造化文書処理装置。
【請求項４】
請求項１に記載の構造化文書処理装置であって、
前記共通部分認識部は、前記構造化文書を解析することで共通構造を特定することを特徴とする構造化文書処理装置。
【請求項５】
請求項１に記載の構造化文書処理装置であって、
共通部分認識手段では、特定の大きさ以下の構造は認識を省くことを特徴とする構造化文書処理装置。
【請求項６】
請求項１に記載の構造化文書処理装置であって、
前記構造化文書の構造に対する変更がないと判定できるときは、前記木データ操作部において、共通構造を展開する処理を省くことを特徴とする構造化文書処理装置。
【請求項７】
コンピュータを、構造化文書を入力して、この構造化文書に含まれる複数回出現する可能性のある構造を認識する共通部分認識部と、前記構造化文書と前記共通部分認識部の認識結果とを入力して、前記構造化文書中に共通構造を検出したとき、前記共通構造に対する木データを生成し、この木データの共通構造に一致する部分に参照ノードを生成するオブジェクト生成部と、ユーザアプリケーションからの指示に従って、オブジェクトを処理する木データ操作部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、構造化文書の処理方法に関し、特に、ＸＭＬ（eXtensible Markup Language）等で記述された構造化文書の処理において、メモリ使用量を削減する方式に関する。
【背景技術】
【０００２】
従来、プログラム間のデータ交換には固定形式のデータが利用されていた。このような固定的データ形式は柔軟性が低く、データ形式やプログラムの更新、ネットワークを介したデータのやり取りで問題を生じることが多々あった。そこで、データ交換のための標準的な形式として、ＸＭＬが提案され、広く利用されている。
【０００３】
ＸＭＬは固定的な構造を持たない半構造データであり、タグおよびデータから構成されたテキストデータによって表現される。半構造データは、タグによってデータの内容を識別することが可能となるため、従来の固定的なフォーマットに比べてデータ表現の柔軟性が高い。また、半構造データは、タグのネストによって階層的なデータ構造を表現することも可能である。このような特徴から、ＸＭＬは様々な分野で広く応用されている。
【０００４】
ＸＭＬで表現されたデータはテキスト形式で表現されるため、ＸＭＬ形式で記述されたデータを処理するためには、タグとデータを分離し、ＸＭＬ文書の構造を解析する必要がある。このような処理を行うソフトウェアをＸＭＬパーサと呼ぶ。ＸＭＬ文書の構造解析手法としては、ＤＯＭ（Document Object Model）による手法と、ＳＡＸ（Simple API for XML）による手法が標準的に利用されている。
【０００５】
ＤＯＭは入力したＸＭＬ文書をそれに対応した木構造データ（以下ＤＯＭ木と呼ぶ）へ変換してメモリ上に展開し、それに対して操作を行うモデルを採用している。ＤＯＭ木のノードは、ＸＭＬの要素や内容等を表す要素ノード、内容を表すテキストノードなどで構成される。ＤＯＭでは入力ＸＭＬ文書に含まれるすべての要素に対するノードをあらかじめ作成する。そのため、ＤＯＭ木で必要となるメモリ量は、対象ＸＭＬ文書の大きさの数倍から十数倍が必要となる。このため、巨大なＸＭＬ文書ではメモリが不足するため取り扱えない、または、構造化文書を処理するシステムのメモリを圧迫するという問題がある。そのためＤＯＭが使用するメモリ量を削減するための技術がいくつか開発されている。
【０００６】
非特許文献１は、木構造を独自の内部表現により仮想的に保持し、ＤＯＭ ＡＰＩによりノードがアクセスされた際に必要に応じて実際にノードを作成する方法を提案している。この方法では、アプリケーションがＸＭＬ文書中の一部の要素のみしかアクセスしない場合、その他の多くのノードはメモリ使用量の少ない内部構造で保持されるため、メモリ使用量を削減できる。
【０００７】
非特許文献２および特許文献１は、また実アプリケーションではＸＭＬ文書の一部のみがアクセスされることが多いことに注目し、あらかじめアプリケーションが指定した部分のみの木構造データを作成することでメモリ使用量を削減する技術が記載されている。
非特許文献３には、共通構造の認識方法であるＳＥＱＵＩＴＵＲアルゴリズムの記載がある。
【０００８】
【特許文献１】特開２００３−１７８０４９号公報
【非特許文献１】Markus L. Noga et.all, "Lazy XML Processing" ACM DocEng'02, ACM Press, Nov, 2002
【非特許文献２】中島他、”ＸＭＬ高速処理技術ＳＰｌｉｔＤＯＭの機能拡張と評価”、DBSJ Letters、Vol3 No.1 pp121-124 June 2004
【非特許文献３】C.G. Nevill-Manning and I.H. Witten "Identifying Hierarchical Structure in Sequences: A linear-time algorithm" Journal of Artificial Intelligence Research, pp67-82, 1997
【発明の開示】
【発明が解決しようとする課題】
【０００９】
電子商取引などで使用されるＸＭＬ文書では、タグの構造が同じで値のみが異なるＸＭＬ文書が使用される場合が多い。この場合、ＤＯＭ木には、末端のテキストノードの値のみが異なり、要素ノードの構成が同じ部分木が多く含まれることになる。非特許文献１、非特許文献２の技術ではアプリケーションで使用されない要素に対するノードは作成されないが、検索などすべての要素が参照される場合、すべてのノードが展開されるため、最終的に同様のＤＯＭ木が作成される。
本発明の目的は、このようなＸＭＬ文書の処理に必要となるメモリ使用量の削減を図った構造化文書処理装置を提供することである。
【課題を解決するための手段】
【００１０】
本発明では、次の２つのステップにより上記の問題を解決する。まず、構造化文書の解析前に、ＸＭＬＳｃｈｅｍａなどのスキーマ定義を解析して、解析対象のＸＭＬ文書に複数回表れ得る構造を認識する。次に、認識した構造がＤＯＭ木作成対象のＸＭＬ文書中に現れた場合に、共通に使用する部分木を一つ作成し、ＤＯＭ木にはその部分木を参照するノードを接続する。また、ＤＯＭ木のノードを参照する際、参照対象が部分木を参照するノードである場合でも、ＤＯＭ木に対する構造の変更がないと分かる場合は、部分木を参照するノードから通常のノードを構築してその参照を返す（以下、展開とよぶ）ことを行わない。
【００１１】
上述した課題は、構造化文書を入力して、この構造化文書に含まれる複数回出現する可能性のある構造を認識する共通部分認識部と、構造化文書と共通部分認識部の認識結果とを入力して、構造化文書中に共通構造を検出したとき、共通構造に対する木データを生成し、この木データの共通構造に一致する部分に参照ノードを生成する木データ作成部と、木データ作成部が生成したオブジェクトを格納するオブジェクト管理部と、ユーザアプリケーションからの指示に従って、オブジェクトを処理する木データ操作部とを備え、木データ操作部は、共通構造を参照するノードを参照する際は、共通構造を展開する構造化文書処理装置により、達成可能である。
【００１２】
上述した課題は、また、コンピュータを、構造化文書を入力して、この構造化文書に含まれる複数回出現する可能性のある構造を認識する共通部分認識部と、構造化文書と共通部分認識部の認識結果とを入力して、構造化文書中に共通構造を検出したとき、共通構造に対する木データを生成し、この木データの共通構造に一致する部分に参照ノードを生成するオブジェクト生成部と、ユーザアプリケーションからの指示に従って、オブジェクトを処理する木データ操作部として機能させるためのプログラムにより、達成可能である。
【発明の効果】
【００１３】
本発明によれば、参照を表すノードに対するアクセスが起こった場合でも、ノードの展開を行わないため、メモリ使用量が少ない構造化文書処理装置を提供できる。
【発明を実施するための最良の形態】
【００１４】
以下本発明の実施の形態について、実施例を用い図面を参照しながら説明する。なお、同一部位には同じ参照番号を振り、説明は繰り返さない。なお、以下の実施例の説明により、本発明の適用範囲が限定されるものではない。
【実施例１】
【００１５】
実施例１を図１ないし図１３を参照して説明する。
図１は、ＸＭＬパーサ（XML Parser：構造化文書処理装置）の全体構成を説明するブロック図である。ＸＭＬパーサ１０１は、共通部分認識部１０３、木データ作成部１０４、オブジェクト管理部１０５、木データ操作部１０９で構成される。ＸＭＬパーサ１０１における文書処理の手順では、まず、共通部分認識部１０３により、ＸＭＬ文書１０２に指定されたＸＭＬ Ｓｃｈｅｍａなどの構造情報１１２を解析し、複数回出現する可能性のある構造を認識する。次に、木データ作成部１０４は、共通部分認識部１０３が特定した構造を認識しながら、ＸＭＬ文書１０２のデータ部分１１３に対する木データを作成し、オブジェクト管理部１０５に保持する。オブジェクト管理部１０５では、ＸＭＬデータを、木データ１０６、値管理表１０７、共通木管理表１０８の３つのデータ構造で保持する。木データ操作部１０９は、ユーザアプリケーション１１１に対して、ＤＯＭ ＡＰＩを提供する。このとき、木データ操作部１０９は必要に応じて、展開部１１０より、オブジェクト管理部１０５に保持されているデータの構造を変更する。
【００１６】
図２はＸＭＬパーサが動作する計算機システムのハードウェアブロック図である。計算機システムは、バス２０４によって接続されたＣＰＵ２０１、主記憶２０２、ディスク装置２０３で構成される。ＸＭＬパーサ１０１は、主記憶２０２またはディスク装置２０３に格納されており、ＣＰＵ２０１上で実行される。なお、図２の計算機システムは、図示しない入力装置、出力装置等を含んでもよい。
【００１７】
図３はＸＭＬ文書のデータ部を説明する図である。また、図４は図３のＸＭＬ文書のデータ部の構造情報であるＸＭＬＳｃｈｅｍａを説明する図である。
図３に示すＸＭＬ文書は、全体がｉｎｖｏｉｃｅ要素で構成されており、ｉｎｖｏｉｃｅ要素は、ｈｅａｄｅｒ要素と２つのＬｉｎｅＩｔｅｍ要素を含んでいる。ｈｅａｄｅｒ要素は、ｓｅｌｌｅｒ要素とｂｕｙｅｒ要素で構成されており、これら２つの要素は、ａｄｒｅｓｓ要素とｎａｍｅ要素で構成される同一の構造を持っている。
【００１８】
図４において、ＸＭＬＳｃｈｅｍａ４０１では、ｘｓｄ：ｓｃｈｅｍａ要素によって、ＸＭＬ文書の構造を定義する。例えば、２行目のｘｓｄ：ｅｌｅｍｅｎｔ要素では、名前がｉｎｖｏｉｃｅであり、構造が、ｉｎｖｏｉｃｅＴｙｐｅ型で示される要素を定義している。ｉｎｖｏｉｃｅＴｙｐｅ型は、３行目から１５行目のｘｓｄ:ｃｏｍｐｌｅｘＴｙｐｅ要素で定義される。この型は、４行目のｘｓｄ:ｓｅｑｕｅｎｃｅ要素により、その要素の下位要素として定義されるｈｅａｄｅｒ要素（５行目）と、ＬｉｎｅＩｔｅｍ要素（１３行目）がその順序で出現することが規定されている。以下、詳細は省略するが、ｈｅａｄｅｒ要素の型は６行目から始まるｘｓｄ:ｃｏｍｐｌｅｘＴｙｐｅ要素で、ｓｅｌｌｅｒ要素とｂｕｙｅｒ要素の型であるｃｏｍｐｌａｙＴｙｐｅ型は、１６行目から始まるｘｓｄ:ｃｏｍｐｌｅｘＴｙｐｅ要奏で、ＬｉｎｅＩｔｅｍ要素の型であるＬｉｎｅＩｔｅｍＴｙｐｅ型は、２２行目からそれぞれ定義されている。
【００１９】
図３に示すＸＭＬ文書のデータ部と、図４に示すＸＭＬＳｃｈｅｍａとを、図１のデータ１１３と構造情報１１２として、ＸＭＬパーサ１０１に入力として与えたとき、オブジェクト管理部１０５に記録される木データ１０６、値管理表１０７、共通木管理表１０８を、図５に示す。ここで、図５は、木データ、値管理表および共通木管理表を説明する図である。
【００２０】
図５（ａ）において、木データ１０６は、参照番号１１０１から１１１２で示すノードで構成される。ノード間の矢印は参照関係を示す。縦方向の矢印は親子関係を示し、横方向の矢印は兄弟関係を示す。木データのノードのうち、四角で表現しているノード（１１０１、１１０２など）は一つの要素、値などを表現する。楕円で示されるノード（１１０４、１１０８など）は共通木として認識された構造への参照を表す（共通木参照ノードと呼ぶ）。
【００２１】
この場合、図３に示すＸＭＬ文書３０１のａｄｄｒｅｓｓ要素部分３０２と３０３、および、ＬｉｎｅＩｔｅｍ要素部分３０４と３０５が同じ構造として認識されている。ａｄｄｒｅｓｓ要素部分３０２に対しては、共通木参照ノード１１０４が対応し、ａｄｄｒｅｓｓ要素部分３０３に対しては、共通木参照ノード１１０８が対応している。
ＬｉｎｅＩｔｅｍ要素部分３０４には、共通木参照ノード１１１１が対応し、ＬｉｎｅＩｔｅｍ要素部分３０５には共通木参照ノード１１１２が対応している。
【００２２】
共通木参照ノードは、内部で部分木に含まれるノードの数分の参照ノードを保持する。共通木参照ノード１１０８の場合、対応するａｄｄｒｅｓｓ要素部分３０３は、ａｄｒｅｓｓ、ｃｉｔｙ、ｓｔｒｅｅｔ要素の３つノードがあり、それぞれが、ノード１１１３から１１１５に対応する。共通木参照ノードは、共通木番号、値番号、インデックスをもつ。共通木番号は、このノードが表している共通木に対する共通木管理表の要素番号である。
【００２３】
インデックスは、共通木の内部でノードを一意に識別する識別子である。インデックスは、０から始まり、部分木を深さ優先探索で辿った順にノードに割り振った番号である。値番号は、値管理表の要素番号である。値番号も０から始まる値である。
【００２４】
図５（ｂ）に示す値管理表は、配列構造であり、各配列要素は、共通木で表現される要素ノードがもつテキストノードへの参照の配列を保持している。この配列の要素番号と、インデックス番号は対応している。そのため、ある共通木ノードに対するテキストノードは、共通木に対応する値管理表のエントリを取り出し、そのエントリの共通木ノードのインデックス番目の要素の内容より取得できる。例えば、参照ノード１１１５に対するテキストノードは、値番号が１、インデックスが２のため、値管理表の添字が１のエントリが保持する配列の添字が２のエントリであるノード１１３２となる。なお、値管理表で管理されるテキストノードの親ノード情報としては、対応する共通木のノードを保持する。
図５（ｃ）に示す共通木管理表は、配列構造であり、各要素は共通木の先頭ノードへの参照を保持している。
【００２５】
以下では、上記のオブジェクト管理部１０５が保持するデータを作成する処理である共通部分認識部１０３、木データ作成部分１０４、および、ＤＯＭ ＡＰＩを提供する木データ操作部１０９について詳細に説明する。
【００２６】
共通部分認識部１０３は、ＸＭＬ文書のＸＭＬＳｃｈｅｍａを解析し、複数回利用される可能性のある構造を認識し、結果を位置管理表の形式で出力する。位置管理表の構成について図６を用いて説明する。ここで、図６は位置管理表を説明する図である。
【００２７】
図６において、位置管理表７０１は、共通木が入力ＸＭＬ文書中で現れる位置を表す位置情報７０２、共通木番号７０３、木先頭ノードポインタ７０４で構成される。共通部分認識部１０３では、位置情報欄７０２のみを利用する。残りの欄は、後述する木データ生成処理１０４で利用する。位置情報欄７０２には、例えば、ＸＰａｔｈの形式で情報を記録する。ＸＭＬＳｃｈｅｍａの解析処理では、（１）要素宣言のｍａｘｏｃｃｕｒｓ属性、（２）型の参照回数を手がかりに複数回現れ得る構造を見つけ、位置管理表に追加する。
【００２８】
要素宣言のｍａｘｏｃｃｕｒｓ属性を手がかりとした場合の手順を図７を参照して説明する。ここで、図７はｍａｘｏｃｃｕｒｓ属性による解析処理を説明するフロチャートである。
【００２９】
図７において、ステップ５０１から５０４により、Ｓｃｈｅｍａ要素の開始タグから終了タグの間に現れるｍａｘｏｃｃｕｒｓ属性の値が２以上の要素宣言のそれぞれに対して、処理５０５を適用することで、対象要素、もしくは、その要素の下位に含まれる、最大の固定な構成の共通部分を特定する。具体的には、共通部分認識部１０３は、Ｓｃｈｅｍａ要素の開始タグを初期位置とし（Ｓ５０１）、次のタグＥを取得する（Ｓ５０２）。共通部分認識部１０３は、ＥがＳｃｈｅｍａ要素の終了タグか判定し（Ｓ５０３）、ＹＥＳなら終了する。ステップ５０３がＮＯなら、Ｅがｅｌｅｍｅｎｔ要素で、ｍａｘｏｃｃｕｒｓ属性の値が２以上か判定し（Ｓ５０４）、ＹＥＳなら処理５０５に遷移する。ステップ５０４がＮＯのとき、共通部分認識部１０３は、処理をステップ５０２に遷移する。
【００３０】
処理５０５では、共通部分認識部１０３は、まずスタックＳに型名が、含まれるか判定する（Ｓ５０６）。共通部分認識部１０３は、ステップ５０６がＹＥＳなら終了し、ＮＯなら複合型か判定する（Ｓ５０７）。共通部分認識部１０３は、ステップ５０７がＮＯなら終了し、ＹＥＳなら共通構造をもつ要素か否かを判定する（Ｓ５０８）。
【００３１】
共通部分認識部１０３は、ステップ５０８がＹＥＳなら、要素の位置情報を求め、位置管理表７０１に追加する。ステップ５０８は、下位構造にｃｈｏｉｃｅ要素、ａｌｌ要素、繰り返し回数が１でない要素宣言などが出現するか否か、再帰構造であるか否かを調べることで判定できる。位置情報は、現在処理中の要素から、その要素定義を含む要素定義、あるいは、型定義を特定し、特定した要素あるいは型を参照する要素を見つけることを、参照する要素、型がなくなるまで繰り返し、その径路を記録することで、ＸＰａｔｈ形式（階層形式）で取得できる。
【００３２】
次に、現在処理対象の要素が共通部分木となる前記条件を満たさない場合でも（ステップ５０８：ＮＯ）、その下位に含まれる構造で条件を満たす可能性がある。そのため、ステップ５０９から５１１により、子要素宣言に対して再帰的に、処理５０５を適用する。具体的には、子要素の一覧を取得する（Ｓ５０９）。未処理の子要素Ｃがあるか判定し（Ｓ５１０）、ＮＯなら終了し、ＹＥＳなら、スタックＳに子要素Ｃの型名をプッシュし、子要素Ｃに処理５０５を適用し、スタックＳの先頭をポップし（Ｓ５１１）、ステップ５１０に遷移する。
【００３３】
ステップ５０９で子要素を取得する際は、必要に応じて継承している型宣言の情報を取得し、インスタンス文書に含まれる要素を特定する。処理５０５の再帰的な適用では、適用対象の要素の構成が再帰的になっている場合に対応するため、ステップ５０６および、ステップ５１１のスタック操作により、再帰構造を特定し、再帰の場合は処理を終了させる。
【００３４】
次に、型の参照回数を手がかりに共通部分を見つける手順を、図８を参照して説明する。ここで、図８は参照番号による解析処理を説明する図である。
図８において、共通部分認識部１０３は、まずＳｃｈｅｍａ定義中で複数回参照される複合型一覧を求める（Ｓ６０１）。共通部分認識部１０３は、その一覧に含まれる型の子要素に対して、処理５０５を適用する（ステップ６０２から６０５）。具体的には、共通部分認識部１０３は、Ｌに未処理の型Ｔがあるか判定する（Ｓ６０２）。共通部分認識部１０３は、子要素一覧を取得し（Ｓ６０３）、未処理の子要素があるか判定する（Ｓ６０４）。ＮＯならステップ６０２に遷移する。ステップ６０４でＹＥＳなら、Ｃに対して、処理５０５を適用し（Ｓ６０５）、ステップ６０４に遷移する。
【００３５】
なお、ステップ６０３における子要素の取得は、ステップ５０９と同様の処理で行う。ステップ６０１は、ｓｃｈｅｍａ要素の直下の要素宣言、型宣言に対して、処理５０５と同様に子要素のデータ構造を再帰的に辿り、出現した型参照を記録することで実現できる。
【００３６】
図４のＸＭＬＳｃｈｅｍａ４０１に、上記の手順を適用した様子を説明する。図７に示した手順を適用すると、ｍａｘｏｃｃｕｒｓ属性が２以上のｅｌｅｍｅｎｔ要素として、ＬｉｎｅＩｔｅｍ要素宣言４０７が見つかる。ＬｉｎｅＩｔｅｍ要素の型であるＬｉｎｅＩｔｅｍＴｙｐｅ型４１０は複合型であり、また、固定構造を持つ。そのため、次に、位置情報を求める。ＬｉｎｅＩｔｅｍ要素宣言４０７は、ｉｎｖｏｉｃｅＴｙｐｅ型宣言４０３に含まれる。ｉｎｖｏｃｅＴｙｐｅ型宣言４０３内部での位置指定は/ＬｉｎｅＩｔｅｍとなる。次に、ｉｎｖｏｉｃｅＴｙｐｅ型の出現箇所を求める。この場合、ｉｎｖｏｉｃｅ要素宣言４０２が見つかる。ｉｎｖｏｉｃｅ要素を参照する要素、型がないため、ここまでで構成される位置情報/ｉｎｖｏｉｃｅ/ＬｉｎｅＩｔｅｍを位置管理表７０１に追加する（欄７０５）。
【００３７】
次に図８に示した手順を適用すると、ｓｅｌｌｅｒ要素宣言４０５とｂｕｙｅｒ要素宣言４０６でｃｏｍｐａｎｙＴｙｐｅ型が使われていることがわかる。ｃｏｍｐａｎｙＴｙｐｅ型宣言４０８の子ノードに対して処理５０５を適用すると、ａｄｄｒｅｓｓ要素４０９が複合型であり、固定構造をもつことが判定され、ステップ５１２が適用される。ｃｏｍｐａｎｙＴｙｐｅ型内部でのａｄｄｒｅｓｓ要素の位置と、ｃｏｍｐａｎｙＴｙｐｅ型が使用されている要素宣言４０５、４０６の位置情報より、位置情報/ｉｎｖｏｉｃｅ/ｈｅａｄｅｒ/ｓｅｌｌｅｒ/ａｄｄｒｅｓｓ、/ｉｎｖｏｉｃｅ/ｈｅａｄｅｒ/ｂｕｙｅｒ/ａｄｄｒｅｓｓが求まり、位置管理表７０１の欄７０６に追加される。
【００３８】
次に、木データ作成部１０４の詳細について説明する。木データ作成部１０４は、ＸＭＬ文書に対して木データを作成する。木データ作成処理は、ＳＡＸパーサ（ＳＡＸを用いたＸＭＬパーサ）の木データ作成部１０４におけるイベントハンドラとして実現する。ＳＡＸパーサでは、ＸＭＬ文書を解析し、あらかじめ要素の開始などの決まったイベントに応じて、ハンドラを呼び出すことでＸＭＬ文書を処理する。以下では、図３、図４の例を処理するために必要な、ｓｔａｒｔＥｌｅｍｅｎｔ（要素の開始）イベント、ｅｎｄＥｌｅｍｅｎｔ（要素の終了）イベント、ｃｈａｒａｃｔｅｒｓ（タグ以外の文字列）イベントに対するハンドラについて説明する。なお、その他のイベントのハンドラの処理を以下の説明から実現することは、当業者にとって容易である。また、木データ作成処理について、ＳＡＸパーサにおけるイベントハンドラとして実現することは、既存ＸＭＬパーサであるｘｅｒｃｅｓにおけるＤＯＭ木生成処理と同様である。
【００３９】
各イベントハンドラの説明の前に、木データ作成部１０４のアルゴリズムについて説明する。木データ作成部１０４は、共通部分と一致しない要素に関しては、通常のノードを作成し、木データに追加する。木データ作成部１０４は、共通部分に関しては、最初の共通部分との一致ではその他に同じ構造が現れるか否かが不明のため、その要素の下位要素に対して通常のＤＯＭ木を生成する。木データ作成部１０４は、２回目の一致では、まず、１回目に作成したＤＯＭ木から共通木と、１回目に対応する値管理表のエントリ、共通木参照ノードを作成する。次に、木データ作成部１０４は、３回目以降の一致時に共通木参照ノードと値管理表のエントリを作成する。木データ作成部１０４は、共通構造一致中、要素ノードについては、共通構造と一致するか否かの確認を、テキストノードについては値管理表のエントリにノードを登録する。
【００４０】
ｓｔａｒｔＥｌｅｍｅｎｔイベントの処理手順について、図９を参照して説明する。また、ｃｈａｒａｃｔｅｒｓイベントの処理手順について、図１０を参照して説明する。ｅｎｄＥｌｅｍｅｎｔイベントの処理手順について、図１１を参照して説明する。ここで、図９はｓｔａｒｔＥｌｅｍｅｎｔイベントに対するイベントハンドラの処理フロー図である。図１０はｃｈａｒａｃｔｅｒｓイベントに対するイベントハンドラの処理フロー図である。図１１はｅｎｄＥｌｅｍｅｎｔイベントに対するイベントハンドラの処理フロー図である。
【００４１】
図９において、ｓｔａｒｔＥｌｅｍｅｎｔイベントハンドラは、まず、現在パス情報Ｐの情報を更新する（Ｓ８０１）。変数Ｐの情報は、位置管理表７０１の位置情報のいずれかのエントリと一致するか否かを判定するために使用される。次に、イベントハンドラは、フラグＦの値により処理をわける。フラグＦは、値が０の場合は共通構造の処理中ではないことを、１である場合は初回の一致処理中であることを、２である場合は２回目以降の一致の処理中であることを示す。なお、フラグＦの初期値は０となる。
【００４２】
ステップ８０２からステップ８１０、および、ステップ８１６は、共通構造と一致していない場合に適用される。ステップ８０２で、Ｆ＝０のとき、イベントハンドラは、まず、現在のパスＰが位置管理表のエントリと一致するかを調べる（Ｓ８０３）。ＮＯのとき、イベントハンドラは、要素のノードを作成し木データに追加し（Ｓ８０８）、終了する。
【００４３】
ステップ８０３でＹＥＳのとき、イベントハンドラは、その要素が共通木の先頭要素となる。エントリＥの木先頭ポインタが登録されているか判定し（Ｓ８０４）、木先頭ポインタが空、つまり、初回の一致の場合（Ｓ８０４：ＮＯ）、要素に対するノードの作成、木データへの追加、木先頭ノードポインタへの登録したのち、フラグＦを１とし状態を初回一致中に変更する（Ｓ８０５）。また、共通構造の先頭のため、イベントハンドラは、ｉｎｄｅｘを０にクリアし、ＧＰに現在のパス情報を設定し（Ｓ８１０）、終了する。ここで、ｉｎｄｅｘの値は後述するｃｈａｒａｃｔｅｒｓイベントハンドラの処理において、テキストノードを記録する位置情報として利用する。また、ＧＰは、後述するｅｎｄＥｌｅｍｅｎｔイベントハンドラの処理において、共通構造の先頭位置を認識するために利用する。
【００４４】
ステップ８０４で木先頭ポインタが空でない場合（Ｓ８０４：ＹＥＳ）、つまり、２回目以降の共通構造の先頭の場合、イベントハンドラは、ステップ８０６へ進む。ステップ８０６において、エントリＥの共通木番号が登録されていない、つまり、２回目の一致の場合（Ｓ８０６：ＮＯ）、イベントハンドラは、ステップ８０７により、木先頭ノードポインタが示す部分木に対して、共通木、値管理表のエントリ、共通木参照ノードを作成し、木先頭ノードポインタが示すノードと共通木参照ノードを置換する。次に、ステップ８１６、８０９、８１０により、イベントハンドラは、今回の一致に対する共通木参照ノードの作成、値管理表のエントリの追加を行い、フラグＦを２つまり、２回目以降の一致中に変更する。
【００４５】
ステップ８０６でエントリＥの共通木番号が登録されている場合、つまり、３回目以降の一致の場合は（Ｓ８０６：ＹＥＳ）、イベントハンドラは、２回目に一致した場合の後半のステップと同じ処理により、各種データの作成とフラグＦの状態の切り替えを行う。
【００４６】
次に、フラグＦの値が１の場合処理を述べる。この場合（Ｓ８１１）、初回の共通構造の一致中であり、通常のＤＯＭ木を生成するため、共通構造処理中でない場合と同様、イベントハンドラは、ステップ８０８を適用する。
フラグＦの値が２の場合（Ｓ８１２）、ステップ８１３から８１５が適用される。すなわち、イベントハンドラは、ｉｎｄｅｘの値を更新し（Ｓ８１３）、要素の内容が共通木の対応するノードと一致するかを確認する（Ｓ８１４）。異なっている場合（Ｓ８１４：ＮＯ）、イベントハンドラは、共通木とそれまでに作成した値管理表のエントリの情報から、新たな部分木を作成し、共通木参照ノードと置換した後、フラグＦを０にすることで状態をリセットして（Ｓ８１５）、終了する。ステップ８１４でＹＥＳならば、イベントハンドラは、終了する。
【００４７】
図１０において、ｃｈａｒａｃｔｅｒｓイベントハンドラは、まず、イベントに対応するテキストノードを作成する（Ｓ９０１）。作成したテキストノードのフラグＦの値が２、つまり２回目以降の一致中か判定する（Ｓ９０２）、ＹＥＳの場合、イベントハンドラは、値管理テーブルのエントリのｉｎｄｅｘ番目の要素に記録し（Ｓ９０３）、終了する。ステップ９０２でＮＯの場合、イベントハンドラは、木データにノードを追加し（Ｓ９０４））、終了する。
【００４８】
図１１において、ｅｎｄＥｌｅｍｅｎｔイベントハンドラは、まず、フラグＦが０以外か判定する（Ｓ１０３）。ＹＥＳの場合、つまり、共通構造と一致中の場合、共通構造の先頭を示すＧＰと現在のパス情報Ｐが等しいかを調べる（Ｓ１０４）。ＹＥＳ場合、共通構造の最後となるので、フラグＦを０にすることで共通構造と一致中の状態から抜ける（Ｓ１０５）。次に、現在パス情報Ｐから要素の情報を削除して、パス情報Ｐを更新し（Ｓ１０６）、終了する。ステップ１０３でＮＯのとき、およびステップ１０４でＮＯのとき、ステップ１０６に遷移する。
【００４９】
図３のＸＭＬ文書に対して木データ作成処理が適用される様子を図１２を用いて説明する。ここで、図１２は木データを説明する図である。また、木データ作成部１０４に渡される位置情報表７０１は図６のものである。
【００５０】
図１２において、処理の開始時点ではフラグＦの値は０であり、図３のタグ３０６からタグ３０８の処理では位置情報に一致しないため、図１２のノード１１０１からノード１１０３が作成される。次に、図３のタグ３０９の処理では、位置情報と一致するが、木先頭ノードポインタが登録されていないため、図１２の新たにノード１４０１を作成する。ノード１４０１を木先頭ノードポインタとして記録し、フラグＦを１に設定する。図３のタグ３１０からタグ３１２の処理では、フラグが１のため、ノード１４０２から１４０５が作成される。図３のタグ３１２の処理では、図１１のステップ１００５によりフラグＦの値が０となる。その後、タグ３１５までが処理されると図１２（ａ）に示す木データが作成される。
【００５１】
図３のタグ３１６の処理では位置情報と一致する。この場合、一致する位置情報表のエントリに木先頭ノードポインタとして、ノード１４０１が登録されており、共通木番号は登録されていない。そのため、図９のステップ８０７の処理が適用される。まず、ノード１４０１を先頭とする部分木から共通木１１５５と値管理表のエントリ１１３４が作成される。次に、共通木参照ノード１１０４が作成され、ノード１４０１を先頭とする部分木と置換される。次に、図９のステップ８１６で、共通木参照ノード１１０８が作成される。これにより、図１２（ｂ）に示す木データが作成される。
以下同様に、図９から図１１に示す処理を適用すると、図５に示す木データ、共通木管理表、値管理表が作成される。
【００５２】
木データ操作部１０９の詳細を、以下説明する。木データ操作部１０９は、ＤＯＭ ＡＰＩをアプリケーションに提供し、ＤＯＭ木が木データ、共通木管理表、値管理表で構成されていることをアプリケーションに対して隠蔽する。木データ操作部１０９は、アプリケーションが共通木として表現されるノードに対する参照を要求した場合、展開部１１０により、共通木と値管理テーブルのエントリから共通木参照ノードがあらわすもとの部分木を構築（展開）し、展開後のノードを返す。これは、構造の変更があった場合に、木データ中では共通木として表現できなくなるが、そのときに、アプリケーションが同一の共通木の別の部分を参照していると、ノードの整合性がとれなくなるためである。
【００５３】
しかし、これは、構造の変更が起こらない場合は、問題とはならない。そのため、ユーザ指示などにより、木データの構成に対する変更がないと分かっている場合は、展開を行わず、木データ、共通木管理表、値管理表により、情報を取得してアプリケーションに返す。ユーザ指示の方法としては、ＸＭＬ文書解析まえにあらかじめ、ＸＭＬパーサに対する動作オプションとして指定することが考えられる。動作オプションの実現方法については、既存ＸＭＬパーサであるｘｅｒｃｅｓで実現されているため、ここでは詳細には説明しない。ここでは、子ノードの参照を返すｇｅｔｃｈｉｌｄメソッドの処理のみについて、図１３を参照して説明する。ここで、図１３は、ｇｅｔｃｈｉｌｄメソッドの処理フロー図である。なお、その他のメソッドは、ここで述べるｇｅｔｃｈｉｌｄメソッドの説明から当業者は容易に実現できる。
【００５４】
図１３のｇｅｔｃｈｉｌｄメソッドの処理手順において、木データ操作部１０９は、まず、はじめに、メソッドのターゲットオブジェクトが参照ノードか通常のノードかを判定する（Ｓ１２０１）。参照ノードで、その参照ノードが共通木の末端のノードに対応している場合（Ｓ１２０１：ＹＥＳ）、値管理表に子ノードが登録されている。そのため、ノードの値番号、インデックスにより値管理表を検索する（Ｓ１２０２）。もし、ノードが見つかれば（Ｓ１２０３：ＮＯ）、見つかったノードを返す（Ｓ１２０４）。値管理表を検索して子ノードが見つからなかった場合（Ｓ１２０３：ＹＥＳ）、共通木番号、インデックスにより共通木を検索し、対応する共通木中のノードの子ノードを取得する。次に、その子ノードに対応する参照ノードを共通木参照ノードから検索し、そのノードを返し（Ｓ１２０５）、終了する。
【００５５】
もし、ｇｅｔｃｈｉｌｄメソッドを呼び出しているオブジェクトが通常のＤＯＭノードであった場合（Ｓ１２０１：ＮＯ）、親子関係を表すリンクをたどり、子ノードを取得する（Ｓ１２０６）。次に、取得した子ノードが共通木参照ノードであるか判定する（Ｓ１２０７）。取得した子ノードが共通木参照ノードであった場合（Ｓ１２０７：ＹＥＳ）、最初の参照ノードを返し（Ｓ１２０９）、終了する。ステップ１２０７で共通木参照ノードでなかった場合（ＮＯ）、取得したノードを返し（Ｓ１２０８）、終了する。
【００５６】
図５（ａ）をも参照して、さらに具体例を説明する。ノード１１０７に示すノードに対してｇｅｔｃｈｉｌｄメソッドが呼び出された場合、ノード１１０７は通常のノードであるため、ステップ１２０６により、子ノード１１０８が取得される。子ノード１１０８は共通木参照ノードであるため、ステップ１２０９により、最初のノードであるノード１１１３が結果として返される。
【００５７】
一方、ノード１１１３に対してｇｅｔｃｈｉｌｄメソッドが呼び出された場合、参照ノードのため、ステップ１２０２により値管理表が検索される。値管理表の値番号１、インデックス０の項目１１３３は空のため、ステップ１２０５へ進む。共通木番号０、インデックス０により、ノード１１５２が取得され、その子ノード１１５３が特定される。子ノード１１５３のインデックスは１であるため、共通木参照ノード１１０８中のインデックス１の参照ノード１１１４が取得され結果として返される。
【００５８】
次に、本実施例におけるメモリ量削減の効果を説明する。まず、図３のＸＭＬ文書に対して、通常のＤＯＭ木を生成した場合、ＸＭＬ要素に対応する要素ノードが１９個、コンテンツに対応するテキストノードが１０個生成される。本方式では要素ノードに対してのみ共通木を生成するため、テキストノードの保持に必要なメモリ量は通常のＤＯＭ木の場合と同じとなる。要素ノードに関しては、例えば、既存のＸＭＬパーサであるｘｅｒｃｅｓで処理を行い、ポインタサイズが４バイト必要であるとすると、要素名などのテキスト領域を除いて、４０バイトの領域が必要となる。そのため、要素ノードで、７６０（＝１９ｘ４０）バイトの領域が必要となる。
【００５９】
これに対して、本実施例でのデータ構造で必要となるメモリ量を求めると次となる。まず、木データは、要素ノード６個、および、参照ノード３個をもつ共通木参照ノードが４個で構成されている。参照ノードは、インデックスを３つ持つので、各インデックスを１バイトで表現すると、合計４バイト（通常の３２ビット計算機でのアライメントを考慮）必要となる。また、共通木参照ノードは３つの参照ノードへの参照と親子、兄弟への接続情報が必要となり、２８（＝７ｘ４バイト）バイト必要となる。よって、共通木参照ノード全体では、１６８（＝６ｘ２８）バイト必要になる。つまり、木データ全体で、４０８（＝６ｘ４０+１６８）バイト必要になる。値管理表１１３０では参照が１６個あるので、６４（＝１６ｘ４）バイト必要となる。次に、共通木管理表１１５０では、参照２つと要素ノード６個の合計、２４８（＝２ｘ４+６ｘ４０）バイト必要となる。つまり、合計で、７２０バイト必要となり、通常のＤＯＭ木の場合の７６０バイトと比較して少ないメモリ使用量で表現することができる。本実施例の場合、１つの共通木に対する参照が２回ずつと少ないため効果が少ないが、共通木の参照の回数が増えるにしたがって、メモリ量削減の効果は増大する。
【００６０】
以上の処理により、入力ＸＭＬ文書に含まれる共通構造を特定し、共通構造をもつ部分木を、同一の共通木で表現したデータ構造で保持し、ユーザアプリケーションに対してＤＯＭ ＡＰＩを提供することができる。共通に利用できるノードを表現するために作成される共通木ノード参照ノードは、元のノードに対して少ないメモリ量しか必要としないため、ＤＯＭ木が必要とするメモリ量を削減することが可能となる。
【００６１】
なお、上記の実施例では、共通部分認識部１０３が認識する構造の大きさに対する基準はない。認識する構造が小さいと、適用できる箇所は増えるが、処理時間のオーバーヘッドが多くなる可能性がある。そのため、共通構造として認識する構造の大きさをユーザ指定などにより受け取り、その大きさより小さい構造は候補としないようにすることが考えられる。
【００６２】
本実施例では、解析対象のＸＭＬ文書中に複数回現れる構造に対する部分木は１つだけ作成され、ＤＯＭ木にはその部分木に対する参照を表すノードが追加される。参照を表すノードはＤＯＭ木のノードに対して少ないメモリ量で実現されるため、ＤＯＭ木全体におけるメモリ使用量を削減することができる。また、ＤＯＭ木に対する構造の変更がないことが分かる場合は、参照を表すノードに対するアクセスが起こった場合でも、ノードの展開を行わないため、メモリ使用量が少ない構造を保持できる。
本実施例に拠れば、構造化文書の構造定義を解析して、共通構造を特定することができる。
【実施例２】
【００６３】
実施例１では、複数回現れ得る構造は、ＸＭＬＳｃｈｅｍａを解析することにより認識した。実施例２では、ＸＭＬＳｃｈｅｍａを解析せず、ユーザ指示により共通構造と認識する要素を特定する。ユーザ指示を受け取る方法としては、（１）ＸＭＬＳｃｈｅｍａの注釈として受け取る、（２）ＸＭＬＳｃｈｅｍａのコメントとして受け取る、（３）別の指示ファイルとして受け取る、（４）コマンドラインオプションとして受け取るなどの方式が考えられる。ここでは、ＸＭＬＳｃｈｅｍａの注釈として受け取る方法を、図１４を参照して説明する。ここで、図１４はＸＭＬＳｃｈｅｍａの一部を説明する図である。図１４において、スキーマは、図４の４０８行から始まる６行に注釈（ａｎｎｏｔａｔｉｏｎ要素）１３０１を挿入した形式である。ここでは、ユーザ指示として、ａｎｎｏｔａｔｉｏｎ要素の子要素のａｐｐｉｎｆｏ要素の内容に「ａｐｐｌｙ ｃｏｍｐｒｅｓｓｉｏｎ」と記述することとする。
【００６４】
本実施例の処理では、このようにユーザ指示により指定された構造を対象として、図８に示す参照番号による解析処理の処理フローのステップ６０２から６０５を適用することで認識することができる。
本実施例に拠れば、構造化文書の構造定義に記載されたユーザ指示の基づいて、共通構造を特定することができる。
【実施例３】
【００６５】
実施例３では、複数回現れる構造は、入力ＸＭＬ文書を解析することにより認識する方法を採用する。共通構造の認識は、入力ＸＭＬ文書に対して、ＳＥＱＵＩＴＵＲアルゴリズム（非特許文献３）を適用することで得ることができる。ＸＭＬ文書に対するＳＥＱＵＩＴＵＲアルゴリズムの適用では、入力をＳＡＸのイベントに対応するトークンとし、ｃｈａｒａｃｔｅｒｓイベントに対応する入力トークンに対しては、任意文字列を表す記号（ここでは＃）とすることで可能となる。ＳＥＱＵＩＴＥＲアルゴリズムでは、入力ＸＭＬ文書に対する文法を構成する。このとき構成される文法は、入力文書の階層的な構造を保持し、かつ、開始記号以外の非終端記号は複数の参照があるという特徴がある。そのため、構成された文法の開始記号以外の非終端記号のそれぞれに対して、その参照箇所の位置を求めることで、位置情報表を作成することができる。
【００６６】
図３のＸＭＬ文書に対するＳＥＱＵＩＴＥＲアルゴリズム適用の結果について、図１５を参照して説明する。ここで、図１５はＸＭＬ文書に対するＳＥＱＵＩＴＥＲアルゴリズム適用の結果を説明する図である。Ｓ １５０１は、図３の全体であり、タグとタグとに挟まれた＃は、タグ以外の文字列を置き換えた記号である。また、Ｓ １５０１には、Ｎで表される複数箇所で現れる部分を示す。非終端記号としては、Ｎ１ １５０２、Ｎ２ １５０３、Ｎ３ １５０４が認識される。共通認識処理では、次に、この結果から、構造を持たない非終端記号を候補から除外する。この例では、構造を持たない非終端記号は、Ｎ２ １５０３が相当する。
【００６７】
次に、残りのＮ１ １５０２、Ｎ３ １５０４に対して、参照箇所から、Ｓ １５０１の先頭までの要素を辿ることで、それぞれの位置情報を取得することができる。Ｎ１ １５０２に関して、開始記号Ｓまで辿ると、＜ｉｎｖｏｉｃｅ＞＃＜ｈｅａｄｅｒ＞＃＜ｓｅｌｌｅｒ＞ が取得される。この情報から、ｃｈａｒａｃｔｅｒｓイベントに対応する＃を取り除き、終了タグのない開始タグのみを取り出すことで、位置情報 /ｉｎｖｏｉｃｅ/ｈｅａｄｅｒ/ｓｅｌｌｅｒを特定することができる。
なお、Ｎ３ １５０４に対しても、同様である。
本実施例に拠れば、構造化文書を解析することによって、共通構造を特定することができる。
【図面の簡単な説明】
【００６８】
【図１】ＸＭＬパーサの全体構成を説明するブロック図である。
【図２】ＸＭＬパーサが動作する計算機システムのハードウェアブロック図である。
【図３】ＸＭＬ文書のデータ部を説明する図である。
【図４】図３のＸＭＬ文書のデータ部の構造情報であるＸＭＬＳｃｈｅｍａを説明する図である。
【図５】ＤＯＭ木（木データ、値管理表および共通木管理表）を説明する図である。
【図６】位置管理表を説明する図である。
【図７】ｍａｘｏｃｃｕｒｓ属性による解析処理を説明するフロー図である。
【図８】参照番号による解析処理を説明する図である。
【図９】ｓｔａｒｔＥｌｅｍｅｎｔイベントに対するイベントハンドラの処理フロー図である。
【図１０】ｃｈａｒａｃｔｅｒｓイベントに対するイベントハンドラの処理フロー図である。
【図１１】ｅｎｄＥｌｅｍｅｎｔイベントに対するイベントハンドラの処理フロー図である。
【図１２】木データを説明する図である。
【図１３】ｇｅｔｃｈｉｌｄメソッドの処理フロー図である。
【図１４】スキーマの一部を説明する図である。
【図１５】ＸＭＬ文書に対するＳＥＱＵＩＴＥＲアルゴリズム適用の結果を説明する図である。
【符号の説明】
【００６９】
１０１…ＸＭＬパーサ（構造化文書処理装置）、１０２…ＸＭＬ文書、１０３…共通部分認識部、１０４…木データ作成部、１０５…オブジェクト管理部、１０６…木データ、１０７…値管理表、１０８…共通木管理表、１０９…木データ操作部、１１０…展開部、１１１…ユーザアプリケーション、１１２…構造情報、１１３…データ、２０１…ＣＰＵ、２０２…主記憶、２０３…ディスク装置、２０４…バス。
【図１】
2008140157.tif 000003
【図２】
2008140157.tif 000004
【図３】
2008140157.tif 000005
【図４】
2008140157.tif 000006
【図５】
2008140157.tif 000007
【図６】
2008140157.tif 000008
【図７】
2008140157.tif 000009
【図８】
2008140157.tif 000010
【図９】
2008140157.tif 000011
【図１０】
2008140157.tif 000012
【図１１】
2008140157.tif 000013
【図１２】
2008140157.tif 000014
【図１３】
2008140157.tif 000015
【図１４】
2008140157.tif 000016
【図１５】
2008140157.tif 000017