Microsoft Word - NTTDoCoMo_Takeshi_Kato_final.doc

Size: px

Start display at page:

Download "Microsoft Word - NTTDoCoMo_Takeshi_Kato_final.doc"

たけなりありはら
5 years ago
Views:

1 WS 差分 XSLT スタイルシート生成法の提案と実装加藤剛志上野英俊石川憲洋高橋修 ( 株 )NTT ドコモマルチメディア研究所横須賀市光の丘 35 NTT oomo R& センター mail: {t_kato, ueno, ishikawa, osamu}@mml.yrp.nttdocomo.co.jp あらまし我々は更新前後の XML 文書の差分を抽出しその差分情報を XSLT スタイルシートにより表現する方式を提案する本論文では OM ツリーを利用した差分抽出アルゴリズムと XML の差分表現方式及び差分情報を付加する差分 XSLT スタイルシートの生成方法について述べる更新前後の XML 文書の差分情報から差分 XSLT スタイルシートを生成し更新前 XML 文書にそのスタイルシートを適用することにより更新後の XML 文書を得ることができるこれにより更新後の XML 文書そのものを送信するよりも少ないデータ転送量での XML 文書の更新が可能となるまた提案方式に基づいて実装した差分 XSLT スタイルシート生成ソフトウェアについて述べ基本評価によりその有効性を示すキーワード XML(eXtensible Markup Language),OM(ocument Object Model),XPath,XSLT(eXtensible Stylesheet Language Transformation),XML 差分符号化 Proposal and Implementation of ifferential XSLT Stylesheet Generation Method Takeshi KTO Hidetoshi UNO Norihiro ISHIKW and Osamu TKHSHI Multimedia Laboratories NTT oomo, Inc. 35 Hikarinooka, Yokosuka, Kanagawa, Japan mail: {t_kato, ueno, ishikawa, osamu}@mml.yrp.nttdocomo.co.jp bstract We propose the method to extract difference between the original XML document and its revision and to depict this differential data in XSLT stylesheets. This paper describes deltaextraction algorithm using OM trees, XML deltaexpression method and differential XSLT stylesheet file creation method. onsequently, it is possible to obtain the revised XML document by supplying the XSLT stylesheet with the differential data to the original XML document. omparing with sending whole revised XML document, the original XML document can be updated by sending less information, the differential data. We also introduce prototype software implemented based on proposed method and evaluation result that shows the effectiveness of our method. Keyword XML(eXtensible Markup Language),OM(ocument Object Model),XPath,XSLT(eXtensible Stylesheet Language Transformation),XML delta encoding. はじめに World Wide Web (WWW) は SGML のアプリケーションであるマークアップ言語 HTML( Hyper Text Markup Language) の普及により急速に発展してきたこれにより特定の計算機システムに依存や制約のされないインターネットを使った世界的な文書閲覧システムが実現されたしかし HTML は文書を表示することが主な目的であることから拡張性がなくまた終了タグの省略属性の真偽値の省略なども許されているさらに多くの HTML ブラウザは不正な HTML 文書であってもユーザの利便性を考慮してある程度の補正を行いレンダリングする設計となっているそのためインターネット上の多くの HTML 文書が妥当性検証されていないのが現状であるそこで W3 はインターネット上で効率的に構造化文書を扱うマークアップ言語として SGML のサブセットである XML( extensible Markup Language) [] を開発した XML はデータをネットワーク経由で送受信するための汎用マークアップ言語でありユーザが独自のタグを拡張できるメタ言語の一種であるマークアップ言語とは文書の内容である文字列や文字コード以外のメタ情報 ( 文字列の制御情報意味情報構造情報など ) を別に定義する予約語を利用して文書中に記述していく方式の言語であり様々な計算機処理の対象とすることを目的として開発されてきた XML ベースのマークアップ言語としては HTML を XML の仕様に準拠するように再定義した XHTML や通信プロトコルの SOP Web 上でベクター画像の表現を行なう

2 SVG など様々な応用が考えられている一方携帯電話などのモバイル環境向けアプリケーションでも ompact HTML や WML などの独自の HTML 仕様が開発されてきたこうした中で WP (Wireless pplication Protocol) フォーラム ( 現 OM (Open Mobile lliance)) では記述言語の標準仕様として XHTML asic[] を採用するなど XML 技術の移動体通信への応用が進められている XHTML asic は携帯電話 P テレビ情報家電などの多様な端末での利用を想定しそれらで共通して使えるマークアップ言語の基盤となるものでありモジュール化された XHTML から必要最小限のモジュール群だけを抽出し構成されているしかし XML はこれまでの HTML やテキストファイルバイナリファイルと比較してコンテンツサイズが大きくなる場合が多い例えば XHTML では HTML と比較して XML 宣言や名前空間宣言要素の終了を明示的に記す必要があるなど一般的にそのファイルサイズが大きくなる傾向にあるまた移動通信網においても第三世代 (3G) 携帯電話方式の登場によりネットワークの高速化が行われてきたが利用者の急増やコンテンツサイズの増加などに対処するため限られた無線資源の利用効率の向上 Web サービス品質の向上は非常に重要な課題であるそこで筆者らは携帯電話のプル型やプッシュ型配信において XML コンテンツの差分情報を生成しその差分情報のみを送信することで転送データサイズの削減をする方式の検討を行ってきた [5][6] ネットワークを流れる転送データサイズを減らすための工夫としては様々な方式が存在する例えば HTTP(Hypertext Transfer Protocol) ではクライアントのキャッシュを有効活用するためキャッシュが無効の場合のみデータを転送する仕組みを備えるさらに HTTP デルタエンコーディング [3] では旧コンテンツからの差分情報のみを転送するための機能が提供されている XML 文書においてもその差分情報を抽出し HTTP デルタエンコーディング等を用いて差分情報のみを転送すればネットワークを流れるデータ量の削減を図ることが可能である本論文では XML のツリー構造に注目して任意のつの XML 文書から差分情報を抽出しその差分情報を転送する方式を提案しその性能評価について述べる節ではモバイル向け XML の差分情報生成法の課題と提案する解決法について述べる 3 節では提案方式の詳細について説明し 4 節で試作ソフトウェアの紹介とその性能評価について述べる 5 節では提案方式に関する考察を述べ最後に 6 節でまとめを行う. モバイル向け XML 差分生成の課題任意のつの XML 文書からその差分情報を生成するには )XML 差分情報の抽出方法 )XML 差分情報の表現フォーマット 3) 差分情報による変更後 XML 文書の生成方法という 3 つの課題がある本研究ではこれらの課題の解決法として XSLT (extensible Stylesheet Language Transformations)[4] を用いることを試みた XSLT は XML 対応のスタイルシート言語である XSL (XML Stylesheet Language) から派生した言語であり XSL は XML 文書を構造変換するための言語とテキストをフォーマット化するための言語から構成されているこのうち構造変換用の言語の部分を独立させたものが XSLT であり XHTML 文書をテキスト形式に変換することや XML 文書の構成要素の並び替えを行うことが可能であるこの XSLT を応用すると XML の差分情報を XSLT による変換ルールとして記述することが可能となりそれを変換前 XML 文書に適用することで自動的に変換後 XML 文書が生成できる XSLT の採用により上記 3) の課題が解決できるため本研究では課題 ) と ) の解決法を検討する既存の差分生成法 [8][9] と比較して提案する XSLT を用いた差分生成の利点としては XML として展開されているデータへの適用が容易また既存の XSLT エンジンの利用が可能な点が上げられる一方 XML のナビゲーションツリーをメモリ上に展開する必要があるなど携帯端末にとっては処理が重くなるという問題点も存在するしかし近年 TinyTree[0] や TM(ocument Table Model)[] など携帯端末等に適した超軽量 XML エンジンも開発が進められており特にその場合 XML 文書は木構造や配列でメモリに展開されているため XML 処理系で差分を処理した方が効率が良いまた提案方式では携帯端末側には XSLT 処理のモジュールだけあればよく [9] の UL(elta Update Language) ように特別な差分言語処理モジュールを追加実装しなくて良いという利点がある 3. 差分 XSLT スタイルシート生成法任意のつの XML 文書の差分情報を XSLT の文書変換ルールとして記述した XSLT スタイルシートについて本研究では差分 XSLT スタイルシートと呼ぶ差分 XSLT スタイルシートの生成法は図のように XML の差分を検出する ) 差分検出プロセス差分情報を変換ルールとして整理する ) 差分抽出プロセス差分 XSLT スタイルシートを生成する 3) 差分表現プロセスからなるこれらのプロセスに分けることで ) のプロセスは XSLT に依存しない汎用的な XML 差分抽出アルゴリズムとして検討が可能となるまた差分生成方式としては編集する XML 文書に対してユーザが行った編集操作の履歴を元に差分

3 情報を抽出する方法が考えられるしかしこの方式では XML 文書そのものとその編集履歴を持つ必要があるため利便性に欠ける本研究では任意に与えられたつの XML 文書の差分生成法を提案するこれにより編集履歴を保持する必要の無い汎用的な差分検出が可能となる以下これらのプロセスについて詳細を述べる efore XML efore ocument XML ocument fter XML fter ocument XML ocument Parsing XML (a) (a) ifference etection Process efore OM Tree efore OM Tree fter OM Tree 3.. 差分検出プロセス fter OM Tree (b) (b) ifference xtraction Process ifferential Information 図差分 XSLT 生成手順 (c) (c) ifference Representation Process ifferential XSLT Stylesheet 提案方式では XML データ構造をツリー ( 木 ) 構造で処理することが可能な OM (ocument Object Model)[5] を用いて処理を行う任意のつの XML 文書の OM ツリーをルート ( 根 ) から走査して比較することで差分情報の検出が可能であるこのプロセスではつの OM ツリーの差分情報として一致ノード ( 変換前後で共通に存在する要素 ) 削除ノード( 変換後に存在しない要素 ) 追加ノード( 変換後に出現する要素 ) の検出を行う任意のつのツリーから差分情報を抽出する方法としては簡易的な差分情報の検出法 ( 既存方式であり 3.. 節で説明する ) と最適化された差分を検出する方法 ( 提案方式であり 3.. 節で説明する ) が存在する 3... 簡易差分検出法 ( 既存方式 ) 簡易差分検出法はつの任意のツリーのルートから変更前ツリーの各ノードを基準に変更後のツリーの対応ノードを順次比較し変更前ツリーを走査し比較を進める過程でノードの不一致があったノード以下のサブツリー ( 部分木 ) を全て差分とみなす方式であるこの場合ブランチ ( 分岐枝 ) へのノードの挿入や削除を正確には検出できない図の例で説明するとノード "" の上位にノード "" が挿入されているが簡易差分検出法ではノード "" 以下は全て差分とみなされる文献 [][3] は任意の XML 文書の差分生成について説明しているがいずれも簡易差分検出法と同様に最適な差分情報の検出が不可能であるまた文献 [4] ではつの有向順序木の頂点数を n a n b とした場合の最大共通グラフ問題 ( 連結グラフのうち辺の数が最大であるものを求める ) が O(n a n b ) 時間で計算できることを示しているがその場合も同様に変更や削除されたノード以下のサブツリーの正確な差分検出は不可能である <> < <> = X > </> < = X > </> </> </> </> </> </> </> </> </> efore XML ocument <> < <> = X > </> < = X > </> </> <> </> </> <> </> </> </> </> </> </> </> fter XML ocument 図 XML 文書の例 3... 最適化差分検出法 ( 提案方式 ) 最適化差分検出法はつの XML の差分情報を生成するために初めに一致ノード不一致ノードの検出を行う検出アルゴリズムとして OM ツリー構造を変化させながら一致ノードの最も多い形状を見つけて残りを差分とする方法を提案するアルゴリズムの前提条件は以下の通りである i) 実際上のルートノードの上位に仮想ノードを設定しそれをルートノードとするルートノードは必ず一致するとして扱う ii) 変更前後の OM ツリーにおいて検出した一致ノードが最大となった状態を最適とする iii) 一致とは変更前後の各ノードにおいて要素名や属性名が一致することとするまたノードとして属性要素テキストを同列で扱う場合属性ノードと要素ノードは比較する必要がないそこで比較の効率化のため各ノード種別で比較を行う以下において図を用いて最適化差分検出の方式について説明する ) OM ツリーの要素比較を行い一致する可能性のある最大ノードの組合せを調べるまず OM ツリーの要素比較を行い一致する可能性があるノードのみで組合せの作成を行うこれにより組合せの比較回数を減少させる ( 図 3(a)) ) ノードの組合せの作成及びその比較を繰り返す順次組合せを構成するノード数が多いものから比較を行うまた一致ノードが最大となる組合せが複数存在する場合は変更後 OM ツリーにおいてルートに近い方ツリーの右側に近い方を一致ノードとするルートに近い部分を変更する場合ツリーのリーフに近い部分を変更する場合よりも XML 文書がツリー構成である性質上により大きな影響を与えると考えられる ( 図 3(b)) 3) 得られた一致ノードから出現ノード消失ノードを洗い出す一致ノードが最大数存在する OM ツリーを構成するノードが最終的な一致ノードとなるまたそれを変更前変更後 OM ツリーに当てはめたとき一致ノードに合わないノードが不一致ノードとなる次に一致ノード出現ノード消失ノードの区別を行う

4 出現ノードは変更後に存在する不一致ノードである消失ノードは変更前に存在する不一致ノードであるそれぞれのノードの情報を図 3(c) の表にまとめる ttribute efore XML fter XML (a) inding maximum combination with the potentiality of accord tree ccordance node table dded node table (b) omparing before and after OM tree fragments eleted node table Value X Value Value ccordance Reference / // // ///@ //* [] ///* [] //* [] efore / // // bsolute bsolute Position //* [3] ///* [] ///@ fter / //*[] // //*[]/ ///@ ppearance ///*[] //* []/* [] isappearance //n* [3] ///* [] (c) etecting accord and disaccord nodes information 図 3 差分検出プロセス一致ノードテーブルにおいて一致ノードテーブルは一致 OM ツリー上での位置を示す変更前位置は変更前 OM ツリーでの位置を示し変更後位置は同様に変更後のノードの位置を示す出現ノードテーブルにおいて出現位置は変更後 OM ツリーでの位置を表す消失ノードテーブルでも同様に消失位置は変更前 OM ツリーでの該当ノードの位置を示すそれぞれ一致ノード以外の追加や変更された要素ノードは *[n] で表しを付けて表している n は OM ツリーでの一番兄となるノードを基準とした順番である以上により最適な差分情報が検出される 3.. 差分抽出プロセス 3. で述べたプロセスより得られた一致ノード出現ノード消失ノードリストよりより正確な差分情報を抽出する変更前のノードが消失する理由として消去された場合移動した場合内容を変更された場合が考えられるまた変更後に新たに出現したノードは移動してきたか変更されたか追加されたかのどれかに当てはまる提案する方式では出現ノード及び消失ノードをさらに以下に示したノードに分類する i) 変更ノード出現ノードテーブルと消失ノードテーブルを比較して同じ絶対位置と同じノードタイプであるノードを変更ノードとみなす図 3(c) において出現ノードテーブルのノード "" と消失ノードテーブルのノード "" が変更ノードの対象となる ii) 追加ノード出現ノードテーブルにおいて変更ノードとみなされたノード以外が追加ノードとなる図 3(c) において出現ノードテーブルのノード "" とノード "" が追加ノードである iii) 削除ノード消失ノードにおいて変更ノードとみなされたノード以外が削除ノードとなる図 3(c) において消失ノードテーブルのノード "" が削除ノードである最終的に差分情報は表のように表される表は図の例を用いた場合の差分情報テーブルの例である表差分情報テーブル Reference Position lassification dditional ata of difference NodeValue ///*[] hange //*[] ddition //*[]/*[] ddition //*[3] 3.3. 差分表現プロセスこのプロセスでは前項の差分抽出プロセスで得た差分情報を XSLT テンプレートへマッピングを行うさらにそれらを用いて差分 XSLT スタイルシートを生成するまた OM と XSLT が持つデータモデルにはいくつかの相違点がある [7] これは XSLT が利用する XPath[6] は OM と異なり Tsection や Referencentity がテキストノードとして扱われたり属性ノードは属する要素ノードを親とするが当該ノードの子ではない等の相違点に起因するそのためこのプロセスではその相違点に関しても補正を行う必要がある以下において提案する差分表現方式の仕組みについて述べる差分表現プロセスは XSLT テンプレートルール作成のための ) 写像位置の決定 ) 同一の写像情報を利用する差分ノードの決定 3)XSLT テンプレートへの適用最終的に 4) 差分 XSLT スタイルシートの生成という 4 つの手順となる ) XSLT テンプレートマッチのための写像位置決定 XSLT による XML データの構造変換の記述は以下のつを指定することである

5 i) XML 文書のどの位置を変換するのか ( パターン ( 写像位置 ) の決定 ) ii) 変換先の XML 文書にどのような処理を行うのか ( 差分情報の表現 ) この指定を行うことを XSLT ではテンプレートルールで表現し xsl:template 要素で表す XSLT テンプレートルールにおいてパターン ( 写像位置 ) は変更前 OM ツリーでのノード位置の XPath 表現となる XSLT で差分表現を実現するにはパターンとなりうる写像位置となるノードを指定する必要があるつまり例えば追加ノードであれば変更後 XML 内にある新たに出現したノードの位置情報をあるノードの絶対位置からの相対位置というつの情報に分離しあるノードの絶対位置をテンプレートルールのパターンに XPath として表現する ( 図 4) ccordance Node efore XML ddition Node fter XML X bsolute // <xsl:template match= Pattern > <xsl:template match= > Transformational description Node X is <X/> a child of Node Relative 図 4 XSLT テンプレートルール提案方式ではノードのテンプレートのパターン ( 写像位置ノード ) 決定は変更後 OM ツリーの上方向から下方向 ( 親から子へ ) 且つ左方向から右方向 ( 兄から弟へ ) の順で行う事とする XML 文書は完全なツリー構造のため親から子に向かって分岐していくパターンとなりうるノードは差分ノードよりもルートに近いノードであるため深さ優先でパターンの探索を行うパターンは差分情報が変更である要素ノードまたは一致する要素ノードとなる次に図 5 を参照してテンプレートルールのパターン ( 写像位置ノード ) 決定方法について詳細を述べる一致ノードと変更ノードは自身の位置が写像位置となる追加ノードの場合以下に記述する順で処理を行い写像位置を決定する i) 子ノード方向図 5(a) のように当該ノードの子孫ノード方向に対してパターンを検出する検出した最も近いノードの位置をパターンとするノードが検出できない場合一意に定まらない場合ツリーが分岐している場合は次の処理へ移行する ii) 兄ノード方向図 5(b) のように当該ノードの兄ノード方向に対してパターンを検出する検出した最も近い兄ノードの位置をパターンとするノードが検出できない場合は次の処理へ移行する iii) 弟ノード方向図 5(c) のように当該ノードの弟ノード方向に対してパターンを検出する検出した最も近い弟ノードの位置をパターンとするノードが検出できない場合は次の処理へ移行する iv) 親ノード方向図 5(d) のように当該ノードの先祖ノード方向に対してパターンを検出する検出した最も近い親ノードの位置をパターンとするノードが検出できない場合は上位ノードで決定されたパターンを当該ノードのパターンとする potential pattern node (ccordance node / change node) Node is a both Node and (a) Searching pattern toward descendant nodes ddition node Node is a Node Node is a both Node and 3. Node is a Node 4 3 Node is a patter of both Node and Node is a patter of Node 3 (b) Searching pattern toward elder brother nodes Node is a both Node and 3 (c) Searching pattern toward younger brother nodes Node is a patter of Node (d) Searching pattern toward ancestor nodes <xsl:template match= / > </> <xsl:template match= // > </> ancestor nodes first search 図 5 パターン探索 potential pattern node (ccordance node / change node) template Node is a both Node and Node is a both Node and <xsl:template match= // > <> </> </> template descendant nodes first search ddition node 図 6 祖先優先探索と子孫優先探索何故子ノード方向を初めに処理を行い親ノード方向が最後であるかは図 6 に示した例のように親ノード方向にパターンを生成するとテンプレート数が大きくなり最終的な XSLT スタイルシートが大き

6 くなってしまうからであるなぜなら XML はツリー構造であるため子要素の方がより多くのノードと接する確率が高くなりより多くの不一致ノードのパターンとして利用できるからである次に削除ノードのパターン探索を説明する削除ノードの場合基本的には親ノード方向にパターンを探す図 7 のように子孫ノードが全て削除ノードであれば一番上位のノードをパターンとして全てのノードが削除できるそのため子孫ノードに削除ノード以外を含まない先祖ノードを探してそれをパターンとするノードが検出できない場合は自身の位置をパターンとするまた属性ノードは基本的に親ノードのみを持つため追加ノードの (iv) と同様の処理を行う bsolute / // // // // /// bsolute // // Node 3 has only deletion node as its own descendant node <xsl:template match= ////3 > <xsl:template> Template rule for deleting Node 3,5 and 6 Pattern of template rule ttribute Parent potential pattern node (ccordance node / change node) Node Name Node Node Node 3 Node 4 Node 5 Node 6 node Pattern Node Node Node 3 Node 4 Node 3 Node 3 図 7 削除ノードのパターン探索 Relative lder brother lassification of difference ccordance ccordance ccordance ccordance hange Transformationa No Yes Yes Yes No Yes Transformational description of template rule lassification of difference ddition ddition Pattern node table // /// /// // ddition ata lassification of difference ddition hange ddition NodeNme Pattern // /// // // NodeValue 同じパターンを持つノードをまとめてつのテンプレートに記述していく付録で示すようなテンプレートへマッピングを行う ii) 追加ノードのテンプレート化同じパターンを持つノードをまとめてつのテンプレートに記述していく付録のようにパターンとなるノードに対して親ノード子ノード兄ノード弟ノードを記述し各追加ノードは付録に示したように記述する図 9 は図で示したサンプル XML の差分情報の例を示す of Node opy of Node <xsl:template match="/node()[]"> <xsl:applytemplates select="/node()[]/node()[]" /> </xsl:copy xsl:copy> </xsl:template xsl:template> <xsl:template match="/node()[]/node()[3]"> hange of Node to Node efore XML <xsl:template match="/node()[]/node()[]/node()[]"> <Node> </Node ode> opy of Node and addition of Node <xsl:template match="/node()[]/node()[]"> <xsl:applytemplates /> <Node> <xsl:applytemplates select="/node()[]/node()[]" /> </Node ode> fter XML opy of Node and addition of Node <xsl:template match="/node()[]/node()[]"> <> </> 図 9 XSLT テンプレート例 4) 差分 XSLT スタイルシートの生成最終的に作成されたテンプレートを図 0 のように並べて差分 XSLT スタイルシートを生成するヘッダ部分は生成するスタイルシートの XML 宣言及び各種設定値を表すフッタ部分は差分表現のテンプレートに現れなかったその他一致ノードのコピーするテンプレートである Header <?xml version=.0 encoding= Shift_JIS?> <xsl:stylesheet version=.0 xmlns:xsl= <xsl:output method= xml omitxmldeclaration= no no version=.0 encoding= Shift_JIS indent= no no doctypesystem= ixhtml0.dtd doctypepublic= //NTT public= //NTT oomo//xhtml T ixhtml i.0//n /> /> ifference ata XSLT template XSLT template /// itself hange // itself 図 8 パターンで整理した差分情報 ) 写像位置を基準とした差分情報の生成前項で説明したパターンにより差分情報を図 8 のように整理する XSLT テンプレートを生成する場合同じパターンを持つ差分ノードは同じテンプレートに記述できるしたがってパターンとなっている一致ノード毎に差分ノードを整理する図 8 は図で示したサンプル XML 文書の差分情報である 3) テンプレートへのマッピングパターンとなるノード毎の情報に従って以下の手順で XSLT テンプレートへのマッピングを行う i) パターンとなりうるノードのテンプレート化 ( 一致ノード変更ノード削除ノード ) ooter <xsl:template node() > <xsl:applytemplates node() /> </xsl:stylesheet> 4. 実験 4.. 試作ソフトウェア図 0 差分 XSLT スタイルシート本研究では提案方式に基づいたソフトウェアを Java( JS.3.) を用いて実装した XML パーサーとして IM XML Parser for Java を用い作成した差分 XSLT スタイルシートの妥当性チェックのための XSLT エンジンとして pache XalanJava.4.0 を用いた本ソフトウェアは任意のつの XML 文書から差分 XSLT スタイルシートを生成しさらに差分情報をグ

7 ラフィカルに表現する機能を持つこのソフトウェアを用いて提案方式の有効性を評価した 4.. 実験及び結果まず以下の株価情報ファイルを利用して XML 文書の圧縮率と更新前後の XML 文書の差分割合の関係について測定を行った図に示す株価日足チャートは毎分更新され一番古い価格情報が消去され新しい価格情報が追加されるこのコンテンツを用いてコンテンツ全体のサイズと差分割合を変化させたときに XML 文書の圧縮率を測定した <?xml version=".0" encoding="ut6"?> <Stockata> <ompany id=""> <Name></Name> <Price> <T0900>0000</T0900> <T090>000</T090> <T090>0000</T090> <T357>004</T357> <T358>005</T358> <T359>006</T359> </Price> </ompany> </Stockata Stockata> efore XML ata addition <?xml version=".0" encoding="ut6"?> <Stockata> <ompany id=""> <Name></Name> <Price> <T090>000</T090> <T090>0000</T090> <T357>004</T357> <T358>005</T358> <T359>006</T359> <T400>006</T400> </Price> </ompany> </Stockata Stockata> fter XML ata 図株価日足チャートここで圧縮率は更新前文書に対する差分 XSLT スタイルシートの大きさの割合を表す ( 式 ()) また差分割合は XML 文書を構成するノードに対する差分ノード数の割合を表す ( 式 ()) Size of Generated XSLT Stylesheet () ompressib ility ratio = 00 (%) Size of before XML data Number of discordance nodes () ifference ratio = 00 (%) Number of all nodes in before XML data 40 機能することが分かる efore News ontent addition fter News ontent 図 3 ニュースフラッシュコンテンツ次に図 3 のようなニュースフラッシュコンテンツを用いて提案方式の性能評価を行った図に示すコンテンツでは更新の際に新しいニュース項目が追加され一番古いニュース項目が削除されるこれを用いて実際の差分 XSLT スタイルシートのサイズ ( XSLT ) 及びそれを gzip で圧縮したもの ( XSLT+gzip) さらに同じコンテンツ( 但し要素毎に改行したもの ) を iff で差分をとり gzip で圧縮したもの (iff+gzip) と差分割合の関係をそれぞれ測定したまた変更後コンテンツを送信する場合との比較として変更後コンテンツを gzip で圧縮したもの ( HTML+gzip) も測定した Size of original XML document (89byte) ompressibility Ratio (%) K K 5K 0K 50K 00K ontent Size (yte) XSLT XSLT+gzip iff+gzip HTML+gzip ifference Ratio (%) ifference Ratio (%) 図圧縮率と差分割合の関係図に結果を示す XML 文書全体のサイズを Kbyte から 00Kbyte まで変化させ差分割合を 4% から 50% まで変化させた図に示したように XML 文書サイズが大きくなると圧縮率も高くなるこれはコンテンツサイズが大きくなると差分 XSLT スタイルシートのヘッダ部分とフッタ部分のオーバーヘッドが無視できるくらい小さくなっていくからであるしかし Kbyte 程度の小さな XML 文書でも差分割合が 5% 程度までは提案方式が有効に機能していることが分かる提案方式はモバイル向けのような小さな XML 文書でも変更箇所がある程度小さければ有効に図 4 差分ファイルのサイズと差分割合の関係図 4 はその結果を示す差分割合を 0% から 45% まで変化させたときの差分 XSLT スタイルシートのサイズを示す結果に示すように差分 XSLT スタイルシートを gzip で圧縮したものは変更後コンテンツを圧縮したものより平均で 63% の大きさに圧縮されているまた iff を用いた差分ファイルを圧縮したものと比較すると約 37% サイズ増となったこれにより iff には及ばないが比較的効率良く差分圧縮が実現されることが分かる以上試作ソフトウェアの評価により提案方式による差分 XSLT スタイルシートの生成及び更新前

8 XML 文書と差分 XSLT スタイルシートからの更新後 XML 文書の生成が全て自動で行えることを確認しさらにその圧縮効率も実用上問題がないことを確認した 5. 考察 XSLT は必ずしも差分情報を表現するのに最適ではないそこで差分 XSLT スタイルシート生成の過程において特に有効であると思われる XSLT 機能として xsl:copyof に関して新しい関数を提案する xsl:copyof はサブツリーを指定するための XSLT 要素であるがこの場合指定したノード以下全てのサブツリーが対象となってしまう提案する generation() ( 図 5) はこの要素にサブツリーを基準ノードから n 世代まで指定するための関数であるこれにより従来の XSLT よりも単純にサブツリー単位のコピーや要素と属性をまとめたコピーの表現が可能となりより効率的な差分情報を表現することができるようになる 6. まとめ efore XML ata fter XML ata <xsl:template match= > <xsl:copyof select= ///node()[generation()=] > XSLT template 図 5 Generation 関数本研究では任意のつの XML 文書から自動的に差分 XSLT スタイルシートを生成する方式について提案した提案方式は差分検出プロセス差分抽出プロセス及び差分表現プロセスからなりそれぞれにおいてアルゴリズムの提案を行ったさらに試作ソフトウェアについて述べその有効性を示したさらに XSLT において差分情報を表現するために有効な新しい関数について提案した今後の研究ではさらに一般的な XML における提案方式の有効性の評価新しい XSLT 関数の有効性評価差分検出アルゴリズムの評価が課題となる TYP ccordance elete hange (No continuing process to descendant of pattern) No template <ata of hanged node/> (ontinuing process to descendant of pattern) <xsl:applytemplates/> <xsl:applytemplates/> <ata of hanged node> <xsl:applytemplates/> </ata of hanged node> 付録一致ノード削除ノード変更ノードの XSLT テンプレートへのマッピング TYP ddition node in Parent ddition node in hild ddition node in elder brother ddition node in younger brother TYP ddition node (No continuing process to descendant of pattern) <Parent addition node> <xsl:copy/> </Parent addition node> <hild addition node/> <lder brother addition node/> <xsl:copy/> <xsl:copy/> <Younger brother addition node/> (ontinuing process to descendant of pattern) <Parent addition node> <xsl:applytemplate> </Parent addition node> Same as left template <lder brother addition node/> <xsl:applytemplates/> <xsl:applytemplates/> <Younger brother addition node/> 付録ブランチへの追加ノードの XSLT テンプレートへのマッピング (No continuing process to descendant of addition node) <ddition node/> (ontinuing process to descendant of addition node) <ddition node> <xsl:applytemplate select= XPath of lower pattern /> </ddition node> 付録ツリーの末端への追加ノードの XSLT テンプレートへのマッピング文献 [] Tim ray, et al., xtensible Markup Language (XML).0 (Second dition), W3 Recommendation, Oct 000. [] Mark aker, et al., XHTML asic, W3 Recommendation, ec 000. [3] Jeffrey. Mogul, et al., elta ncoding in HTTP, R39, Jan 00. [4] James lark, XSL Transformations (XSLT) Version.0, W3 Recommendation, Nov 999. [5] rnaud Le Hors, et al., ocument Object Model (OM) Level ore Specification Version.0, W3 Reccomendation, Nov 000. [6] James lark, et al., XML Path Language (XPath) Version.0, W3 Reccomendation, Nov 999. [7] Ray Whitmer, ocument Object Model (OM) Level 3 XPath Specification Version.0, W3 andidate Recommendation, March 003. [8] iff, [9] XMLiff, [0] TinyTree, [] TM, [] Robin La ontaine, elta ormat for XML: Identifying hanges in XML iles and Representing the hanges in XML, XML urope 00, May 00. [3]. P. urbera,.. pstein, ast ifference and Update of XML ocuments, XTech 99, March 999. [4] 増田澄男他, 二つの木の最大共通部分グラフを求めるアルゴリズム, 電子情報通信学会論文誌 (), vol.j77, no.3, pp , March 994. [5] Norihiro Ishikawa, et al., utomatic Generation of a ifferential XSL Stylesheet rom Two XML ocuments, WWW onference 00, May 00 [6] 上野英俊他, XML コンテンツの差分生成法とプッシュ型配信への応用, 情報処理学会 ML 研究会第 0 回研究報告会, March 00.

XMLとXSLT

XMLとXSLT XML と XSLT 棚橋沙弥香目次現場のシステム構成とXML/XSLの位置づけ XMLとは XSL/XSLTとは XalanのインストールいろいろなXSL XMLマスター試験の紹介現場のシステム構成 HTML 画面上のデータ電文電文外部 WEB サーバー (Java) CORBA 通信認証サーバー (C 言語 ) DB XML 電文 HTML XSL XSLT 変換今回の説明範囲