JP2002099428A - ハッシュコンパクトｘｍｌパーサ - Google Patents

Abstract

(57)【要約】 （修正有） 【課題】ハードウェア制約のある装置でのメモリとの競
合および処理負担を改善する構文要素を含むマークアッ
プ言語文書の解析方法を提供する。 【解決手段】構文要素の１つに対し、その要素のタイプ
を識別し３１０、前記タイプが第１タイプの場合はハッ
シュ表現を決定することによってその要素を処理し３１
８、前記タイプが前記第１タイプの場合は、ハッシュ表
現を用いたその文書の少なくとも部分的な構造表現を強
める３１４、という手続きを含む。

Description

【発明の詳細な説明】

【０００１】

【著作権についての注意】この特許明細書は、著作権保
護の対象となる素材を含む。その著作権者は、特許庁の
ファイルから閲覧する目的で、本特許明細書、或は、関
連素材を複製することに対しては、なんらの異論もない
が、そうでなければ、全てのいかなる著作権もこれを保
有する。

【０００２】

【発明の属する技術分野】本発明は、一般的にマルチメ
ディア文書の処理、特に、マークアップ言語で記述され
た文書に関する。本発明は、マークアップ言語文書を構
文解析する方法及び装置に関するものである。本発明は
また、マークアップ言語で記述された文書を構文解析す
るための処理をコンピュータに実行させるために作成さ
れたコンピュータプログラムに関し、更に、このコンピ
ュータプログラムが記録されたコンピュータ可読媒体を
含むコンピュータプログラム製品に関する。

【０００３】

【技術的背景】構文解析（パーシング）とは、文書から
情報を抽出する処理である。この処理には、通常、文書
の構文に対する最低限のチェックが少なくとも含まれ
る。そして、一般的に、その文書のツリー構造での記
述、又は、イベントの論理的なつながり（logical chai
n）を得ることができる。そのイベントの論理的なつな
がりに基づいた構造表現は、一般的に、文頭から文末ま
で、文書を順番に構文解析することによって生成され
る。

【０００４】ツリー型のパーサは、例えば、ＸＭＬ文書
を内部ツリー構造にコンパイルし、アプリケーションが
扱うことのできる階層モデルを与える。Ｗ３Ｃの文書オ
ブジェクトモデル（ＤＯＭ）作業グループは、拡張可能
なマークアップ言語（ＸＭＬ）文書に用いる標準ツリー
型アプリケーションプログラムインターフェース（ＡＰ
Ｉ）を現在開発している。他方、イベント型のパーサは
各要素の開始や終了等の解析イベントを、アプリケーシ
ョン−このアプリケーションのために解析が行われてい
る−に直接報告する。この報告は典型的にはコールバッ
クを用いて実行され、内部ツリー構造を必要としない。
解析が必要なアプリケーションは、様々なイベントを処
理するためにハンドラを実行する。これはグラフィカル
ユーザインターフェースにおけるイベントのハンドリン
グによく似ている。

【０００５】ツリー型のパーサは、広範囲のアプリケー
ションに有用だが、一般的に、システムリソースに負担
がかかり、特に、解析対象となっている文書が大きな場
合には負担となる。さらに、アプリケーションは、その
アプリケーション独自のツリー構造の構築を必要とする
場合があるが、ツリー表現を、異なる表現と照らし合わ
せるためだけに、構築するのは非効率である。イベント
型のパーサによれば、ＸＭＬ文書に対し、より単純で、
より低いレベルでのアクセスが可能となり、使用可能な
システムメモリよりも大きなメモリを要する文書の解析
を容易にする。“Ｓｉｍｐｌｅ ＡＰＩ ｆｏｒ ＸＭ
Ｌ”（ＳＡＸパーサと称す）は、ＸＭＬ文書を解析する
ためのイベント駆動型インターフェースである。ＳＡＸ
パーサは、図２Ａ、図２Ｂ、図３Ａ、図３Ｂ、図３Ｃに
おいて、更に詳細に議論する。

【０００６】図１Ａ、図１Ｂは、パーサシステムのブロ
ック図を示したものである。ここでは、以下のＸＭＬ文
書部分１０６について考察する。

【０００７】 105 <Shakespeare> 110 <!--This is a comment--> 115 <div class="preface"Name1="value1"name2="value2"> 120 <mult list=&lt;></mult> 125 <banquo> 130 Say ［１］ 135 <quote> 140 goodnight</quote>, 145 Hamlet.</banquo> 150 <Hamlet><quote>Goodnight,Hamlet.</quote></Hamlet> 155 </Shakespeare>

【０００８】図１Ｂにおいて、ＸＭＬ文書１０６は、こ
の例では、イベント型のパーサである、パーサ１１２へ
入力される。点線枠１０８で示されるように、文書型定
義（ＤＴＤ）又はＸＭＬスキーマもまた、パーサ１１２
へオプションとして入力される。パーサ１１２は、矢印
１１４で示されるように、簡単なリストから成る文書１
０６の部分的な構造表現を出力する。図１Ａにおいて、
カスケードスタイルシート（ＣＳＳ）又は拡張スタイル
シート（ＸＳＬ）１０４は、ＣＳＳ又はＸＳＬパーサ１
１０へ入力される。ＤＴＤ１０２もまたこのパーサ１１
０へ入力される。本図において、ＸＭＬパーサ１１２及
びＣＳＳ／ＸＳＬパーサ１１０は共に、イベント駆動型
パーサである。

【０００９】ＸＭＬのようなマークアップ言語の利点の
１つは、タグを使用して文書の様々な部分を定義できる
ことにより、文書を、容易に、よりスマートで、よりポ
ータブルで、よりパワフルにできることにある。この機
能は、ＸＭＬの記述上の性質からきている。ＸＭＬ文書
はサブジェクト単位でカスタマイズされる。そして、そ
れにより、カスタマイズされたタグは、人間が文書を構
造的に理解できるようにするために用いられる。しか
し、この特性によって、ＸＭＬ文書が冗長で大きなもの
になることがよくあり、場合によっては問題となる。例
えば、ＸＭＬ文書がプリンタのように、ハードウェア制
約のある装置で解析されなければならない場合、メモリ
をたくさん使用する性質のある従来型の解析は、そのよ
うな装置に格納できる限られたメモリと競合してしま
う。さらに、ハードウェア制約のある装置によって文書
が処理される場合には、人間のＸＭＬ文書の読みやすさ
は、一般的に、余り利点にはならない。さらに、ＸＭＬ
文書の解析において、タグ文字列のマッチング操作が多
く必要とされ、許容できないほどの処理要求の負担がか
かり、ひいては、許容できない数のプロセッササイクル
を引き起す。これらの問題は、図１Ａ及び図１Ｂに示さ
れる両方のパーサ例に当てはまる。

【００１０】

【本発明の開示】本発明の目的は、既存の機器の一つ以
上の欠点をほぼ無くし、或は、少なくとも改善すること
にある。

【００１１】本発明の第１の態様では、構文要素を含む
マークアップ言語文書を解析する解析方法であって、前
記構文要素の内の一要素に対し、前記一要素のタイプを
識別する識別ステップと、前記タイプが第１タイプであ
れば、そのハッシュ表現を決定することによってその要
素を処理する処理ステップと、前記タイプが前記第１タ
イプであれば、前記ハッシュ表現を用いて、前記文書の
少なくとも部分的な構造表現を増大させる増大ステップ
と、を含むことを特徴とする解析方法が提供される。

【００１２】本発明の他の態様では、ＶＲＤに照らして
マークアップ言語文書の妥当性検査を行う検査方法であ
って、（ａ）マークアップ言語文書を、そこで識別され
るドキュメントタグごとに、該ドキュメントタグが、対
応するマークアップ言語のドキュメントタグ階層におけ
る第１ドキュメントタグでなければ、処理するステップ
を有し、該処理は、（ｉ）前記ドキュメントタグの階層
位置を決定するステップと、（ｉｉ）前記ドキュメント
タグ階層における前のドキュメントタグのハッシュ表現
に連結された、前記ドキュメントタグの拡張ハッシュ表
現を決定するステップと、（ｉｉｉ）前記ドキュメント
タグが前のドキュメントタグよりも深くネストにされる
場合に、前記ドキュメントタグの前記拡張ハッシュ表現
を格納するステップと、を含み、前記検査方法は更に、
（ｂ）ＶＲＤを、そこで識別されるタグごとに、該タグ
が対応タグ階層の第１タグでない場合に、処理するステ
ップを有し、該処理は、（ｉ）前記タグの階層位置を決
定するステップと、（ｉｉ）対応するタグ階層における
前のタグのハッシュ表現に連結される前記タグの拡張ハ
ッシュ表現を決定するステップと、（ｉｉｉ）前記タグ
の前記拡張ハッシュ表現をリストに格納するステップ
と、を含み、前記検査方法は更に、（ｃ）前記ドキュメ
ントタグの前記拡張ハッシュ表現が、前記リスト内にあ
るか、或は、前記リストのメンバの妥当なサブセットで
ある場合には、前記マークアップ言語文書の妥当性を検
査するステップを有することを特徴とする検査方法が提
供される。

【００１３】本発明の他の態様では、ＶＲＤに照らして
マークアップ言語文書の妥当性を検査する検査方法であ
って、（ａ）前記ＶＲＤを、そのなかで識別された構造
要素ごとに、処理する処理ステップを含み、該処理ステ
ップは、（ｉ）前記構造要素の構文属性を決定するステ
ップと、（ｉｉ）前記構造要素のハッシュ表現を決定す
るステップと、（ｉｉｉ）前記ＶＲＤの構造表現におけ
る、前記構造要素の前記ハッシュ表現及び構文属性を格
納するステップと、を含み、前記検査方法は更に、
（ｂ）マークアップ言語文書を、そのなかで識別された
ドキュメント構造要素ごとに、処理する処理ステップを
含み、該処理ステップは、（ｉ）前記文書構造要素の構
文属性を決定するステップと、（ｉｉ）前記文書構造要
素のハッシュ表現を決定するステップと、（ｉｉｉ）前
記文書の構造表現における、前記文書構造要素の前記ハ
ッシュ表現と構文属性を格納するステップと、を含み、
前記検査方法は更に、（ｃ）前記文書の前記構造表現に
おける前記各文書構造要素の構文属性及びハッシュ表現
が、前記ＶＲＤの前記構造表現における対応構文属性及
びハッシュ表現に一致する場合に、前記マークアップ言
語文書の妥当性を検査するステップを有することを特徴
とする検査方法が提供される。

【００１４】本発明の他の態様では、構文要素を含むマ
ークアップ言語文書を符号化する符号化方法であって、
前記構文要素の一つについて、構文要素のタイプを識別
するステップと、（ｉ）前記タイプが第１タイプであれ
ば、前記構文要素のハッシュ表現を決定すること、（ｉ
ｉ）前記タイプが第１タイプでなければ、前記構文要素
の圧縮表現を決定すること、（ｉｉｉ）前記構文要素を
保持すること、のいずれかによって、前記構文要素を処
理するステップと、を含むことを特徴とする符号化方法
が提供される。

【００１５】本発明の他の態様では、符号化構文要素を
含むマークアップ言語文書を復号する復号方法であっ
て、前記符号化構文要素の一つについて、前記符号化構
文要素のタイプを識別するステップと、（ｉ）前記タイ
プが第１タイプであれば、前記符号化構文要素の逆ハッ
シュ表現を決定すること、（ｉｉ）前記タイプが第１タ
イプでなければ、前記符号化構文要素の解凍表現を決定
すること、（ｉｉｉ）前記符号化構文要素を保持するこ
と、の少なくとも一つで、前記符号化構文要素を処理す
るステップと、を含むことを特徴とする復号方法が提供
される。

【００１６】本発明の他の態様では、構文要素を含むマ
ークアップ言語文書を解析する解析装置であって、前記
構文要素のタイプを識別する識別手段と、前記タイプが
第１タイプである場合に、前記構文要素を、そのハッシ
ュ表現を決定することによって、処理する処理手段と、
前記タイプが第１タイプである場合に前記ハッシュ表現
を用いて、前記文書の少なくとも部分的構造表現を増大
する増大手段と、を含むことを特徴とする解析装置が提
供される。

【００１７】本発明の他の態様では、ＶＲＤに照らして
マークアップ言語文書の妥当性を検査する検査装置であ
って、（ａ）マークアップ言語文書を、そこで識別され
るドキュメントタグごとに、該ドキュメントタグが、対
応するマークアップ言語のドキュメントタグ階層におけ
る第１ドキュメントタグでなければ、処理する手段を有
し、該手段は、（ｉ）前記ドキュメントタグの階層位置
を決定する手段と、（ｉｉ）前記ドキュメントタグ階層
における前のドキュメントタグのハッシュ表現に連結さ
れた、前記ドキュメントタグの拡張ハッシュ表現を決定
する手段と、（ｉｉｉ）前記ドキュメントタグが前のド
キュメントタグよりも深くネストにされる場合に、前記
ドキュメントタグの前記拡張ハッシュ表現を格納する手
段と、を含み、前記検査装置は更に、（ｂ）ＶＲＤを、
そこで識別されるタグごとに、該タグが対応タグ階層の
第１タグでない場合に、処理する手段を有し、該手段
は、（ｉ）前記タグの階層位置を決定する手段と、（ｉ
ｉ）対応するタグ階層における前のタグのハッシュ表現
に連結される前記タグの拡張ハッシュ表現を決定する手
段と、（ｉｉｉ）前記タグの前記拡張ハッシュ表現をリ
ストに格納する手段と、を含み、前記検査装置は更に、
（ｃ）前記ドキュメントタグの前記拡張ハッシュ表現
が、前記リスト内にあるか、或は、前記リストのメンバ
の妥当なサブセットであるかのどちらかであることを立
証し、それによって、前記マークアップ言語文書の妥当
性を検査する手段を有することを特徴とする検査装置が
提供される。

【００１８】本発明の他の態様では、ＶＲＤに照らして
マークアップ言語文書の妥当性を検査する検査装置であ
って、（ａ）前記ＶＲＤを、そのなかで識別された構造
要素ごとに、処理する手段を含み、該手段は、（ｉ）前
記構造要素の構文属性を決定する手段と、（ｉｉ）前記
構造要素のハッシュ表現を決定する手段と、（ｉｉｉ）
前記ＶＲＤの構造表現における、前記構造要素の前記ハ
ッシュ表現及び構文属性を格納する手段と、を含み、前
記検査装置は更に、（ｂ）マークアップ言語文書を、そ
のなかで識別されたドキュメント構造要素ごとに、処理
する手段を含み、該手段は、（ｉ）前記文書構造要素の
構文属性を決定する手段と、（ｉｉ）前記文書構造要素
のハッシュ表現を決定する手段と、（ｉｉｉ）前記文書
の構造表現における、前記文書構造要素の前記ハッシュ
表現と構文属性を格納する手段と、を含み、前記検査装
置は更に、（ｃ）前記文書の前記構造表現における前記
各文書構造要素の構文属性及びハッシュ表現と、前記Ｖ
ＲＤの前記構造表現における対応構文属性及びハッシュ
表現とを比較し、それにより、前記マークアップ言語文
書の妥当性を検査する手段を有することを特徴とする検
査装置が提供される。

【００１９】本発明の他の態様では、構文要素を含むマ
ークアップ言語文書を符号化し、前記文書の少なくとも
部分的構造表現を形成する符号化装置であって、構文要
素のタイプを識別する手段と、（ｉ）前記タイプが第１
タイプであれば、前記構文要素のハッシュ表現を決定す
ること、（ｉｉ）前記タイプが第１タイプでなければ、
前記構文要素の圧縮表現を決定すること、（ｉｉｉ）前
記構文要素を保持すること、のいずれかによって、前記
構文要素を処理する手段と、を含むことを特徴とする符
号化装置が提供される。

【００２０】本発明の他の態様では、符号化構文要素を
含むマークアップ言語文書を復号する復号装置であっ
て、前記符号化構文要素のタイプを識別する手段と、
（ｉ）前記タイプが第１タイプであれば、前記符号化構
文要素の逆ハッシュ表現を決定すること、（ｉｉ）前記
タイプが第１タイプでなければ、前記符号化構文要素の
解凍表現を決定すること、（ｉｉｉ）符号化構文要素を
保持すること、の少なくとも一つによって、前記符号化
構文要素を処理する手段と、を含むことを特徴とする復
号装置が提供される。

【００２１】本発明の他の態様では、コンピュータに構
文要素を含むマークアップ言語文書を解析する手続を実
行させるコンピュータプログラムであって、前記構文要
素のタイプを識別するコードと、前記タイプが第１タイ
プである場合に、前記構文要素を、そのハッシュ表現を
決定することによって、処理するコードと、前記タイプ
が第１タイプである場合に前記ハッシュ表現を用いて、
前記文書の少なくとも部分的構造表現を増大するコード
と、を含むことを特徴とするコンピュータプログラムが
提供される。

【００２２】本発明の他の態様では、コンピュータにＶ
ＲＤに照らしてマークアップ言語文書の妥当性を検査す
る手続を実行させるコンピュータプログラムであって、
（ａ）マークアップ言語文書を、そこで識別されるドキ
ュメントタグごとに、該ドキュメントタグが、対応する
マークアップ言語のドキュメントタグ階層における第１
ドキュメントタグでなければ、処理するコードを有し、
該コードは、（ｉ）前記ドキュメントタグの階層位置を
決定するコードと、（ｉｉ）前記ドキュメントタグ階層
における前のドキュメントタグのハッシュ表現に連結さ
れた、前記ドキュメントタグの拡張ハッシュ表現を決定
するコードと、（ｉｉｉ）前記ドキュメントタグが前の
ドキュメントタグよりも深くネストにされる場合に、前
記ドキュメントタグの前記拡張ハッシュ表現を格納する
コードと、を含み、前記コンピュータプログラムは更
に、（ｂ）ＶＲＤを、そこで識別されるタグごとに、該
タグが対応タグ階層の第１タグでない場合に、処理する
コードを有し、該コードは、（ｉ）前記タグの階層位置
を決定するコードと、（ｉｉ）対応するタグ階層におけ
る前のタグのハッシュ表現に連結される前記タグの拡張
ハッシュ表現を決定するコードと、（ｉｉｉ）前記タグ
の前記拡張ハッシュ表現をリストに格納するコードと、
を含み、前記コンピュータプログラムは更に、（ｃ）前
記ドキュメントタグの前記拡張ハッシュ表現が、前記リ
スト内にあるか、或は、前記リストのメンバの妥当なサ
ブセットである場合には、前記マークアップ言語文書の
妥当性を検査するコードを含むことを特徴とするコンピ
ュータプログラムが提供される。

【００２３】本発明の他の態様では、コンピュータにＶ
ＲＤに照らしてマークアップ言語文書の妥当性を検査す
る手続を実行させるコンピュータプログラムであって、
（ａ）前記ＶＲＤを、そのなかで識別された構造要素ご
とに、処理するコードを含み、該コードは、（ｉ）前記
構造要素の構文属性を決定するコードと、（ｉｉ）前記
構造要素のハッシュ表現を決定するコードと、（ｉｉ
ｉ）前記ＶＲＤの構造表現における、前記構造要素の前
記ハッシュ表現及び構文属性を格納するコードと、を含
み、前記プログラムは更に、（ｂ）マークアップ言語文
書を、そのなかで識別されたドキュメント構造要素ごと
に、処理するコードを含み、該コードは、（ｉ）前記文
書構造要素の構文属性を決定するコードと、（ｉｉ）前
記文書構造要素のハッシュ表現を決定するコードと、
（ｉｉｉ）前記文書の構造表現における、前記文書構造
要素の前記ハッシュ表現と構文属性を格納するコード
と、を含み、前記プログラムは更に、（ｃ）前記文書の
前記構造表現における前記各文書構造要素の構文属性及
びハッシュ表現が、前記ＶＲＤの前記構造表現における
対応構文属性及びハッシュ表現に一致する場合に、前記
マークアップ言語文書の妥当性を検査するコードを含む
ことを特徴とするコンピュータプログラムが提供され
る。

【００２４】本発明の他の態様では、コンピュータに構
文要素を含むマークアップ言語文書を符号化する手続を
実行させるコンピュータプログラムであって、構文要素
のタイプを識別するコードと、（ｉ）前記タイプが第１
タイプであれば、前記構文要素のハッシュ表現を決定す
ること、（ｉｉ）前記タイプが第１タイプでなければ、
前記構文要素の圧縮表現を決定すること、（ｉｉｉ）前
記構文要素を保持すること、のいずれかによって、前記
構文要素を処理するコードと、を含むことを特徴とする
コンピュータプログラムが提供される。

【００２５】本発明の他の態様では、コンピュータに符
号化構文要素を含むマークアップ言語文書を復号する手
続を実行させるコンピュータプログラムであって、前記
符号化構文要素のタイプを識別するコードと、（ｉ）前
記タイプが第１タイプであれば、前記符号化構文要素の
逆ハッシュ表現を決定すること、（ｉｉ）前記タイプが
第１タイプでなければ、前記符号化構文要素の解凍表現
を決定すること、（ｉｉｉ）符号化構文要素を保持する
こと、の少なくとも一つで、前記符号化構文要素を処理
するコードと、を含むことを特徴とするコンピュータプ
ログラムが提供される。

【００２６】本発明の他の態様では、コンピュータに構
文要素を含むマークアップ言語文書を解析する手続を実
行させるコンピュータプログラムを、格納したコンピュ
ータ可読媒体を含むコンピュータプログラム製品であっ
て、前記コンピュータプログラムは、前記構文要素のタ
イプを識別するコードと、前記タイプが第１タイプであ
る場合に、前記構文要素を、そのハッシュ表現を決定す
ることによって、処理するコードと、前記タイプが第１
タイプである場合に前記ハッシュ表現を用いて、前記文
書の少なくとも部分的構造表現を増大するコードと、を
含むことを特徴とするコンピュータプログラム製品が提
供される。

【００２７】本発明の他の態様では、コンピュータにＶ
ＲＤに照らしてマークアップ言語文書の妥当性を検査す
る手続を実行させるコンピュータプログラムを、格納し
たコンピュータ可読媒体を含むコンピュータプログラム
製品であって、前記コンピュータプログラムは、（ａ）
マークアップ言語文書を、そこで識別されるドキュメン
トタグごとに、該ドキュメントタグが、対応するマーク
アップ言語のドキュメントタグ階層における第１ドキュ
メントタグでなければ、処理するコードを有し、該コー
ドは、（ｉ）前記ドキュメントタグの階層位置を決定す
るコードと、（ｉｉ）前記ドキュメントタグ階層におけ
る前のドキュメントタグのハッシュ表現に連結された、
前記ドキュメントタグの拡張ハッシュ表現を決定するコ
ードと、（ｉｉｉ）前記ドキュメントタグが前のドキュ
メントタグよりも深くネストにされる場合に、前記ドキ
ュメントタグの前記拡張ハッシュ表現を格納するコード
と、を含み、前記コンピュータプログラムは更に、
（ｂ）ＶＲＤを、そこで識別されるタグごとに、該タグ
が対応タグ階層の第１タグでない場合に、処理するコー
ドを有し、該コードは、（ｉ）前記タグの階層位置を決
定するコードと、（ｉｉ）対応するタグ階層における前
のタグのハッシュ表現に連結される前記タグの拡張ハッ
シュ表現を決定するコードと、（ｉｉｉ）前記タグの前
記拡張ハッシュ表現をリストに格納するコードと、を含
み、前記コンピュータプログラムは更に、（ｃ）前記ド
キュメントタグの前記拡張ハッシュ表現が、前記リスト
内にあるか、或は、前記リストのメンバの妥当なサブセ
ットである場合に、前記マークアップ言語文書の妥当性
を検査するコードを含むことを特徴とするコンピュータ
プログラム製品が提供される。

【００２８】本発明の他の態様では、コンピュータにＶ
ＲＤに照らしてマークアップ言語文書の妥当性を検査す
る手続を実行させるコンピュータプログラムを、格納し
たコンピュータ可読媒体を含むコンピュータプログラム
製品であって、前記プログラムは、（ａ）前記ＶＲＤ
を、そのなかで識別された構造要素ごとに、処理するコ
ードを含み、該コードは、（ｉ）前記構造要素の構文属
性を決定するコードと、（ｉｉ）前記構造要素のハッシ
ュ表現を決定するコードと、（ｉｉｉ）前記ＶＲＤの構
造表現における、前記構造要素の前記ハッシュ表現及び
構文属性を格納するコードと、を含み、前記プログラム
は更に、（ｂ）マークアップ言語文書を、そのなかで識
別されたドキュメント構造要素ごとに、処理するコード
を含み、該コードは、（ｉ）前記文書構造要素の構文属
性を決定するコードと、（ｉｉ）前記文書構造要素のハ
ッシュ表現を決定するコードと、（ｉｉｉ）前記文書の
構造表現における、前記文書構造要素の前記ハッシュ表
現と構文属性を格納するコードと、を含み、前記プログ
ラムは更に、（ｃ）前記文書の前記構造表現における前
記各文書構造要素の構文属性及びハッシュ表現が、前記
ＶＲＤの前記構造表現における対応構文属性及びハッシ
ュ表現に一致する場合に、前記マークアップ言語文書の
妥当性を検査するコードを含むことを特徴とするコンピ
ュータプログラム製品が提供される。

【００２９】本発明の他の態様では、構文要素を含むマ
ークアップ言語文書の少なくとも部分的な構造表現であ
って、前記構文要素の内の一要素に対し、前記一要素の
タイプを識別する識別ステップと、前記タイプが第１タ
イプであれば、そのハッシュ表現を決定することによっ
てその要素を処理する処理ステップと、前記タイプが前
記第１タイプであれば、前記ハッシュ表現を用いて、前
記文書の少なくとも部分的な構造表現を増大させる増大
ステップと、を行う解析方法によって生成されることを
特徴とする構造表現が提供される。

【００３０】本発明の他の態様では、構文要素を含むマ
ークアップ言語文書を解析する解析装置であって、プロ
セッサと、（ｉ）前記文書と、（ｉｉ）前記文書を解析
する手続を前記プロセッサに実行させるプログラムを格
納したプログラムと、格納するメモリを含み、該プログ
ラムは、（ｉ）前記構文要素のタイプを識別するコード
と、（ｉｉ）前記タイプが第１タイプである場合に、前
記構文要素を、そのハッシュ表現を決定することによっ
て、処理するコードと、（ｉｉｉ）前記タイプが第１タ
イプである場合に前記ハッシュ表現を用いて、前記文書
の少なくとも部分的構造表現を増大するコードと、を含
むことを特徴とする解析装置が提供される。

【００３１】本発明の他の態様では、構文要素を含むＶ
ＲＤに照らして構文要素を含むマークアップ言語文書の
妥当性を検査する検査装置であって、（ａ）プロセッサ
と、（ｂ）（ｉ）前記文書と、（ｉｉ）前記ＶＲＤと、
（ｉｉｉ）文書の妥当性を検査する手順を前記プロセッ
サに実行させるプログラムと、を格納するメモリを有
し、（ｃ）前記プログラムは、（ｃａ）マークアップ言
語文書を、そこで識別されるドキュメントタグごとに、
該ドキュメントタグが、対応するマークアップ言語のド
キュメントタグ階層における第１ドキュメントタグでな
ければ、処理するコードを有し、該コードは、（ｃａ
ａ）前記ドキュメントタグの階層位置を決定するコード
と、（ｃａｂ）前記ドキュメントタグ階層における前の
ドキュメントタグのハッシュ表現に連結された、前記ド
キュメントタグの拡張ハッシュ表現を決定するコード
と、（ｃａｃ）前記ドキュメントタグが前のドキュメン
トタグよりも深くネストにされる場合に、前記ドキュメ
ントタグの前記拡張ハッシュ表現を格納するコードと、
を含み、前記プログラムは更に、（ｃｂ）ＶＲＤを、そ
こで識別されるタグごとに、該タグが対応タグ階層の第
１タグでない場合に、処理するコードを有し、該コード
は、（ｃｂａ）前記タグの階層位置を決定するコード
と、（ｃｂｂ）対応するタグ階層における前のタグのハ
ッシュ表現に連結される前記タグの拡張ハッシュ表現を
決定するコードと、（ｃｂｃ）前記タグの前記拡張ハッ
シュ表現をリストに格納するコードと、を含み、前記プ
ログラムは更に、（ｃｃ）前記ドキュメントタグの前記
拡張ハッシュ表現が、前記リスト内にあるか、或は、前
記リストのメンバの妥当なサブセットであるかのいずれ
かであることを立証し、それにより前記マークアップ言
語文書の妥当性を検査するコードを含むことを特徴とす
る検査装置が提供される。

【００３２】本発明の他の態様では、構文要素を含むＶ
ＲＤに照らして構文要素を含むマークアップ言語文書の
妥当性を検査する検査装置であって、（ａ）プロセッサ
と、（ｂ）（ｉ）前記文書と、（ｉｉ）前記ＶＲＤと、
（ｉｉｉ）文書の妥当性を検査する手順を前記プロセッ
サに実行させるプログラムと、を格納するためのメモリ
を有し、（ｃ）前記プログラムは、（ｃａ）前記ＶＲＤ
を、そのなかで識別された構造要素ごとに、処理するコ
ードを含み、該コードは、（ｃａａ）前記構造要素の構
文属性を決定するコードと、（ｃａｂ）前記構造要素の
ハッシュ表現を決定するコードと、（ｃａｃ）前記ＶＲ
Ｄの構造表現における、前記構造要素の前記ハッシュ表
現及び構文属性を格納するコードと、を含み、前記プロ
グラムは更に、（ｃｂ）マークアップ言語文書を、その
なかで識別されたドキュメント構造要素ごとに、処理す
るコードを含み、該コードは、（ｃｂａ）前記文書構造
要素の構文属性を決定するコードと、（ｃｂｂ）前記文
書構造要素のハッシュ表現を決定するコードと、（ｃｂ
ｃ）前記文書の構造表現における、前記文書構造要素の
前記ハッシュ表現と構文属性を格納するコードと、を含
み、前記プログラムは更に、（ｃｃ）前記文書の前記構
造表現における前記各文書構造要素の構文属性及びハッ
シュ表現を、前記ＶＲＤの前記構造表現における対応構
文属性及びハッシュ表現と比較し、それにより前記マー
クアップ言語文書の妥当性を検査するコードを含むこと
を特徴とする検査装置が提供される。

【００３３】本発明の他の態様では、ＶＲＤに照らして
マークアップ言語文書の妥当性検査を行う検査方法であ
って、前記ＶＲＤにおける第１タイプの最も深くネスト
された構文要素についての第１拡張ハッシュ表現を決定
するステップと、ＶＲＤリストに前記第１拡張ハッシュ
表現を格納するステップと、マークアップ言語文書にお
ける第１タイプの最も深くネストされた構文要素につい
て、第２拡張ハッシュ表現を決定するステップと、前記
第２拡張ハッシュ表現が前記ＶＲＤリストに存在する場
合に、前記マークアップ言語文書は妥当でないことを宣
言するステップと、を含むことを特徴とする検査方法が
提供される。

【００３４】本発明の他の態様では、ＶＲＤに照らして
マークアップ言語文書の妥当性を検査する検査装置であ
って、前記ＶＲＤの第１タイプの最も深くネストされた
構文要素について第１拡張ハッシュ表現を決定する手段
と、ＶＲＤリストの前記第１拡張ハッシュ表現を格納す
る手段と、前記マークアップ言語文書における第１タイ
プの最も深くネストされた構文要素について、第２拡張
ハッシュ表現を決定する手段と、前記第２拡張ハッシュ
表現が前記ＶＲＤリストに存在する場合に、前記マーク
アップ言語文書は妥当でないと宣言する手段と、を有す
ることを特徴とする検査装置が提供される。

【００３５】本発明の他の態様では、ＶＲＤに照らして
マークアップ言語文書の妥当性を検査する手続をコンピ
ュータに実行させるコンピュータプログラムであって、
前記ＶＲＤの第１タイプの最も深くネストされた構文要
素について第１拡張ハッシュ表現を決定するコードと、
ＶＲＤリストの前記第１拡張ハッシュ表現を格納するコ
ードと、前記マークアップ言語文書における第１タイプ
の最も深くネストされた構文要素について、第２拡張ハ
ッシュ表現を決定するコードと、前記第２拡張ハッシュ
表現が前記ＶＲＤリストに存在する場合に、前記マーク
アップ言語文書は妥当でないと宣言するコードと、を含
むことを特徴とするコンピュータプログラムが提供され
る。

【００３６】本発明の他の態様では、ＶＲＤに照らして
マークアップ言語文書の妥当性を検査する手続をコンピ
ュータに実行させるコンピュータプログラムを格納した
コンピュータに含まれるコンピュータプログラム製品で
あって、該プログラムは、前記ＶＲＤの第１タイプの最
も深くネストされた構文要素について第１拡張ハッシュ
表現を決定するコードと、ＶＲＤリストに前記第１拡張
ハッシュ表現を格納するコードと、前記マークアップ言
語文書における前記第１タイプの最も深くネストされた
構文要素について第２拡張ハッシュ表現を決定するコー
ドと、前記第２拡張ハッシュ表現が前記ＶＲＤリストに
存在する場合に、前記マークアップ言語文書が妥当でな
いと宣言するコードと、を含むことを特徴とするコンピ
ュータプログラム製品が提供される。

【００３７】

【ベストモードを含む詳細な説明】以下、添付の図面を
参照して説明するが、ここでは、同じ符号を付したステ
ップ及び／又は特徴は、逆の意図が表されない限り、同
じ機能或は動作を有するものとする。

【００３８】本明細書に記載の発明の概念は、ＸＭＬタ
グについて、及び、可能ならばＸＭＬファイル中の他の
要素について、”完全な”ハッシュを実行することによ
って、ＸＭＬパーサのメモリ必要量を減少させ、様々な
性能値を向上させることができる、という考えに基づい
ている。ハッシュ関数とは、数学的であってもなくても
よいが、入力文字列を取得し、ハッシュ値と呼ばれる出
力コード番号に変換する関数である。完全なハッシュ関
数は、予めセットされた領域内のユニークな入力文字列
に対して、ユニークなコード番号を作る関数である。入
力文字列は、例えば、Ｗ３Ｃで許可された英数字や他の
文字で構成され、ハッシュ処理の仕様に記されている特
定の長さよりも短くなければならない。それに代えて、
又は、それに加えて、入力文字列は、例えば、入力内容
に基づいたコード番号の衝突が起こる可能性があるとい
う点から、別の方法で制約を加えることができる。この
アイディアによって、任意のＸＭＬタグを、数やコード
として扱うことができる。そして、メモリ内に数字の形
で格納することができる。パーサは、通常、構造が解析
されるときに、メモリ内のＸＭＬ構造の一部分を保存す
るので、ＸＭＬタグをユニークな数字に変換することに
よってメモリ必要量を減少させることができ、更に、文
字列と文字列の比較を、同様の、しかしより高速の数値
の比較に置き換えることができる。

【００３９】ここで記載する装置の原理は、非常に様々
なマークアップ言語を用いた文書の解析にも、普通に応
用することができる。説明を簡潔にするため、ここで開
示される装置は、ＸＭＬ言語を参照して、説明すること
とする。しかし、これは発明の技術的範囲を制限しよう
とするものではない。例えば、ここに記載された機構は
また、UTF-16転送フォーマットに応用することができる
（UTF-16の詳細は、国際規格ISO/IEC 10646-1を参照の
こと）。

【００４０】図２Ａ及び図２Ｂは、従来技術のＳＡＸパ
ーサ処理２３６を示したものである。これは、随意、整
形性、及び／又は、妥当性をチェックするサブ処理をサ
ポートする。

【００４１】図２Ａにおいて、マークアップ文書（本実
施形態においては、ＸＭＬドキュメント）は、初期ステ
ップ２００で開かれる。その後、決定ステップ２０２
は、文書が未処理の（すなわち解析されていない）文字
を含んでいるかどうかをテストし、決定ステップ２０２
の条件に合ったなら、以下のステップ２０４で文字を読
み込み、文字列に格納する。しかし、テストステップ２
０２において、更に文字が検出されなければ、解析処理
２３６はステップ２３４で終了する。

【００４２】ステップ２０４に続いて、テストステップ
２０６において、チェックが行われ、完全な構文要素が
組み立てられているかどうかを判断する。もし完全な構
文要素が組み立てられているのであれば、パーサ処理２
３６は”構文タイプ”識別ステップ２１０へ進む。反対
に、完全な構文要素が組み立てられていなければ、パー
サ処理２３６は文書中に使用できる文字が更に存在する
かを判断する判断ブロック２０８へ向かう。さらに文字
の使用が可能であれば、パーサ処理２３６は”はい”矢
印に応じてステップ２０４へ戻る。一方、これ以上文字
が使用できない場合は、処理２３６は”いいえ”矢印に
応じて、構文要素タイプ識別ステップ２１０へ向かう。

【００４３】"タイプ識別"ステップ２１０は、組み立て
られた構文要素に対して"タイプ"を識別し、その後、ス
テップ２１２で、要素文字列が文書構造のメモリ表現の
中に置かれ、それによりこの時点で組み立てられていた
ように表現を増やす。その文章構造のメモリ表現は、一
般的に、イベント駆動型パーサの場合、文書の部分構造
表現であり、単純なリストとなり得る。

【００４４】ステップ２１２の後、処理２３６は整形性
チェックを実行すべきかどうかを判断するテストステッ
プ２４２へ向かう。整形性チェックは、文章が、インタ
ーネット上の http://www.w3.org/tr/2000/rec-XML-200
01006.html で入手できる『拡張可能なマークアップ言
語（ＸＭＬ）1.0（第２版）W３Ｃ勧告、2000年10月６
日』の５ページに定義されているような、適切な"整形
式制約"を満たすことをチェックする。整形性チェック
は、文章が一般的な構造ルールに準拠しているかどうか
をテストする、特に、文書中のタグが適切にネストにな
っているかどうかをテストする。そのようなチェックが
実行されると、処理２３６は”ＹＥＳ”矢印に応じて、
点線で示された境界線２４６上の”ａ”に向かう。参照
文字”ａ”から”ｄ”に沿った点線２４６は、図２Ｂの
対応する境界線に映されており、そこで処理２３６がさ
らに示されている。整形性チェックが実行されなかった
場合、処理２３６は”いいえ”矢印に応じて、テストス
テップ２４２から”妥当性チェック”を実行すべきかど
うかを判断するテストステップ２４４へ向かう。妥当性
チェックは、前記Ｗ３Ｃ勧告５．１節に示される文書型
定義（ＤＴＤ）のような、妥当性参照文書（簡単のため
ＶＲＤと称す）に定義される妥当性の制約に照らして、
文書中の構文要素の比較を伴う。ＤＴＤとＸＭＬスキー
マは妥当性チェックが実行されるＶＲＤの例であるが、
ここで述べれらている妥当性チェックは他のタイプのＶ
ＲＤに対して実行される。この比較処理は、単なる整形
性チェックに比し、より広範囲に渡って、要素の正しい
構文配置を検証する。

【００４５】妥当性チェックが実行されると、処理２３
６は”ＹＥＳ”矢印に応じて、点線で示された境界線２
４６上の”ｂ”に向かう。他方、妥当性チェックが実行
されなかった場合、処理２３６は”ＮＯ”矢印に応じ
て、点線で示された境界線２４６上の”ｃ”に向かう。
整形性チェックが選択された場合、処理２３６は境界線
２４６上の”ａ”からオプションサブ処理２３８、特に
その中の整形性チェックステップ２１４へ向かう。処理
２３８のオプションとしての性質は、点線で囲まれた長
方形で示される。

【００４６】妥当性チェックが選択された場合、処理２
３６は境界線２４６上の”ｂ”からオプションサブ処理
２４０、特にその中に見られる妥当性チェックステップ
２２０へ向かう。処理２４０の選択的な性質は点線で囲
まれた長方形で示される。妥当性チェックが選択されな
い場合、処理２３６は境界線２４６上の”ｃ”からアク
ション選択ステップ２２６へ向かう。整形性チェックが
選択されて、整形性ステップ２１４の後、次の誤りチェ
ックステップ２１６で誤りが検出された場合、矢印２１
８で示されるように修正動作及び／または誤り指示が行
われる。他方、誤りが検出されなければ、パーサ処理２
３６はステップ２１６からサブ処理２４０へ向かい、そ
こでは妥当性チェックがステップ２２０で実行される。
前述のように、解析処理２３６は、誤りチェックステッ
プ２１６から、もしくは整形性チェックサブ処理２３８
をバイパスして、妥当性チェックステップ２２０に向か
い、処理２３６は境界線２４６上の“ｂ”から妥当性チ
ェックステップ２２０に直接向かう。オプションの整形
性サブ処理２３８は、適切な判断がテストステップ２４
２，２４４で下された場合にバイパスすることができる
（図２Ａ参照）。

【００４７】前述のように、妥当性チェックステップ２
２０は、文書型定義（ＤＴＤ）に対して考慮されるマー
クアップ文書中の識別された構文要素の比較を含む。こ
の比較処理は、サブ処理２３８に示されている単なる整
形性チェックよりも広範囲に渡って、要素の正しい構文
配置を検証する。

【００４８】妥当性チェックステップ２２０に続いて、
誤りチェックステップ２２２で誤りが検出されると、修
正動作が実行され、矢印２２４で示されるようにはい／
いいえ誤り指示が実行される。一方、誤りが検出されな
い場合は、パーサ処理２３６はアクション選択処理２２
６へ進み、そこでは考慮されている構文要素のタイプに
基づいてアクションが選択される。図２Ａのステップ２
４２及び２４４の決定において適切な判断が下される
と、選択的サブ処理２３８及び２４０の両方をバイパス
することができる。両方の上記サブ処理がバイパスされ
ると、前述のようにパース処理２３６は境界線２４６上
の“ｃ”から直接アクション選択ステップ２２６へ向か
う。

【００４９】構文要素がタグであった場合、矢印２２８
で示されるように、タグ値や対応する文字列は、解析処
理が実行されているアプリケーションに送られ、タグの
メモリ表現が保存される。他方、要素タイプがタグのタ
イプでない場合、矢印２３０で示されるように、要素値
文字列は関連アプリケーションに送られ、要素のメモリ
表現は削除される。最終的に、パース処理２３６は、矢
印２３２で示されるように、図２Ｂの点線で示された境
界線上の“ｄ”へ向かい、図２Ａの対応する点線で示さ
れた境界線２４６上の“ｄ”から文字テストステップ２
０２へ向かう。

【００５０】ＸＭＬ文書の冗長性により、多くのメモリ
必要量が生じ、それに対応して、元の文字列形式中の文
書構造を格納するために大量のメモリ必要量を要するこ
とになる。この文書構造はステップ２１２において参照
される。さらに、可変長の英数字文字列間での文字列比
較のパフォーマンスに関し、かなりの処理負荷が整形性
チェックステップ２１４及び妥当性チェックステップ２
２０の両方で生じる。

【００５１】次に示す２つのステップの両方に関連し
て、一般的に、文書の部分メモリ表現は格納されなけれ
ばならず、文字列のチェックは実行されなければならな
い。つまり、（ｉ）階層分岐が閉じているかどうかのチ
ェック、すなわち終了タグと開始タグのマッチング、ま
た、分岐の重複がないかどうかのチェックについてのス
テップ２１４と、（ｉｉ）ＤＴＤに対する構造の一致性
やタグ名のチェックに加えて、（ｉ）と同様の処理が必
要となるステップ２２０と、である。パーサは、通常、
ＸＭＬ構造が解析される場合、メモリ中にＸＭＬ構造の
一部分を保存しなければならない。ＳＡＸパーサの場合
でも、正しく動作するために、ＸＭＬ構造の局所的な部
分がメモリ中に格納されなければならない。しかし、各
ＸＭＬタグがハッシュ関数を用いてユニークな数字に変
換される場合、ハッシュ演算で生じる数字は、関連する
任意の長さのＸＭＬタグ文字列よりも小さいので、メモ
リ必要量は一般的に減少する。さらに、開始＆終了タグ
のマッチングに必要な文字列間の比較は、より高速な数
値の比較で置き換えることができるため、処理負荷が減
少する。

【００５２】代表的ハッシュアルゴリズムは、（ｉ）巡
回冗長符号化アルゴリズム（ＣＲＣ）（通例、データ転
送や格納において、署名分析又は誤り検出／訂正に用い
られる）と、（ｉｉ）完全ロスレス符号化アルゴリズム
と、（ｉｉｉ）ホフマン符号化アルゴリズムと、を含
む。

【００５３】一般的に、適切なハッシュアルゴリズム
は、静的な演算でなければならない。言い換えれば、要
求されたデータセットに対し、同一の入力条件において
は常に同じハッシュ結果を出力しなければならない。し
かし、要求されたデータセットはその環境によって変化
しうる。そして、そのようなデータセットは、通常、少
なくとも一つの全マークアップ文書を含むことができ、
また、関連ＤＴＤ或いはＸＭＬスキーマや、リンクされ
たマークアップ文書や、ＸＭＬ文書で参照されたＣＳＳ
文書のような、異なった言語における関連の又はリンク
されたマークアップ文書を含むこともできる。一方、タ
グ構文に遭遇した場合には、例えば、ＸＭＬ 文書に非
リテラル‘<’文字を見つけた場合には、常に、そのア
ルゴリズムをリセットすることによって、必要に応じて
静的ハッシュアルゴリズムを使用することができる。ま
た、ＸＭＬ ＤＴＤ文書に<!ELEMENT文字列を見つけた場
合に、又は、ＣＳＳ文書中であって有効なタグセレクタ
が許される全ての場合に、ハッシュアルゴリズムをリセ
ットすることができる。

【００５４】入力されたマークアップ文書中のリファレ
ンスは、適切なハッシュアルゴリズムに信号を送るか又
はそれを選択するために用いられる。これは他のマーク
アップ文書や、ＤＴＤや、スタイルシートや、文字エン
コーディングや、名前空間などを参照できるのとちょう
ど同じように実行されうる。例えば、特定のハッシュア
ルゴリズムは特定の名前空間と同じものとして扱うこと
ができる。これにより、文書中の名前空間のリファレン
スを介したハッシュアルゴリズムへの間接的なリファレ
ンスが可能となる。ハッシュアルゴリズムの実行は、関
連するパラメータ化と共に、全体的に又は部分的にマー
クアップ言語に含まれる。このような、ハッシュアルゴ
リズムを参照したり含めたりする方法は、最適化に有効
である。つまり、特定のマークアップ文書に関して様々
なハッシュ方法が最適化される場合である。それによ
り、宛先装置やシステム中の性能とメモリ使用量が改善
される。一方、前述の参照方法がマッチングに有用な場
合がある。それは１つ以上のマークアップ文書を伴うア
プリケーションであり、そのアプリケーションで、誤り
のチェック又は解析又は他の機能の完了が必要で、１つ
以上の他の文書（例えば、ＤＴＤ）が既に同じアルゴリ
ズムでハッシュ化されている場合である。

【００５５】上記アプローチでは、更なる改善が可能で
あり、例えば、ＤＴＤハッシュを任意的に含むことが挙
げられる。これは、（より低速な）文字列の比較に代え
て、数値の比較を可能とすることにより、ＤＴＤを格納
するための読み出し専用メモリ（ＲＯＭ）の必要量を減
少させ、ＸＭＬ文書の妥当性処理を高速化することがで
きる。

【００５６】図３Ａ、３Ｂ及び３Ｃは、改良されたＳＡ
Ｘパーサ処理３４４のアレンジの１つを示したものであ
る。図３Ａにおいて、ステップ３００からステップ３１
０は、図２Ａに関して説明してきたステップ２００から
ステップ２１０に対応するものである。ステップ３１０
の後、テストステップ３１２において、組み立てられた
構文要素の性質がタグであるか、別の要素タイプである
か確かめるためにテストされる。要素がタグの場合は、
パース処理３４４は矢印３１６に従って、ハッシュステ
ップ３１８へ向かう。ハッシュステップ３１８は、それ
ぞれ図５及び６のプロセッサ４１４及び５０５を用い
て、構文要素の単一数値表現を決定する。これによっ
て、要素の表現を効率良くメモリ上に実現され、また、
英数字領域よりも、単純で高速な数値での比較演算がで
きる。構文要素を示す要素文字列とそのハッシュ値の両
方が、処理３４４の時点で保持されるが、ステップ３１
８で、各々のメモリ４１８及び５０６（図５及び６を参
照）を用いて文書構造のメモリ表現へ挿入されるのは、
文字列の値ではなくハッシュ値である。ここまではこれ
のほうがよい。

【００５７】図３Ａ、図３Ｂ及び図３Ｃで示されるよう
なパース処理３４４を、より正確に理解するため、ま
ず、図２で示したパース処理２３６との関係で、ＸＭＬ
部の例［１］を解析する場合について説明する。この場
合、サブ処理２１２において、ＸＭＬ部［１］から、以
下のような解析されたマークアップタグの階層表現が生
成される。

【００５８】 205 Shakespeare 215 div 220 mult 221 /mult 225 banquo 235 quote 240 quote ［２］ 245 /banquo 250 Hamlet 251 quote 252 /quote 253 /Hamlet 255 /Shakespeare

【００５９】逆に、図３Ａに示されるような、パース処
理３４４において、タグ要素と非タグ要素とに対して異
なる処理が行われた結果、ステップ３１８で同等な階層
表現が生成される。その同等階層表現は［３］に示され
る。［３］の階層表現は、解析されハッシュにされたマ
ークアップタグから成る。これを例示するために、タグ
名の領域は、以下の表１に示されるように制約され、ハ
ッシュマッピング（機能的にはハッシュ“関数”の適用
と同等である）は次の表で示される。

【００６０】

【表１】

【００６１】上記ハッシュマッピングに基づき、［１］
で示されたＸＭＬ文書は、以下のような階層表現とな
る。

【００６２】 205 133 215 326 222 371 223 /371 225 787 235 629 240 /629 ［３］ 245 /787 254 411 255 629 256 /629 257 /411 255 /133

【００６３】図３Ａに戻ると、パース処理３４４は、ス
テップ３１４から点線で示された境界線３５６上の
“ａ”へ向かう。参照文字“ａ”及び“ｂ”に沿った点
線３５６は、図３Ｂの対応する境界線に映されており、
それに関連して処理３４４が更に示されている。

【００６４】図３Ｂに移り、処理３４４は、点線で示さ
れた境界線３５６上の“ａ”から、整形性チェックが実
行されるかどうかを判断するテストステップ３５０へ続
く。そのチェックが実行されると、処理３４４は「ＹＥ
Ｓ」矢印に応じて、境界線３５８上の“ｃ”へ向かう。
参照文字“ｃ”及び“ｆ”に沿って点線で示された境界
線３５８は、図３Ｃの対応する境界線に映されており、
それに関連して処理３４４が更に示されている。整形性
チェックが実行されなかった場合、処理３４４は、「Ｎ
Ｏ」矢印に応じて、妥当性チェックが実行されるかどう
かを判断するテストステップ３５２へ向かう。妥当性チ
ェックが実行されると、処理３４４は「ＹＥＳ」矢印に
応じて、境界線５８上の“ｅ”へ向かう。一方、妥当性
チェックが実行されなかった場合は、処理３４４は境界
線３５８上の“ｄ”へ向かう。

【００６５】図３Ｃに向かうと、整形性チェックが実行
された場合、処理３４４は、点線で示された境界線３５
８上の“ｃ”から、整形性チェックステップ３２０へ向
かう。一方、整形性チェックが選択されなかった場合、
処理３４４は、点線で示された境界線３５８上の“ｅ”
から、妥当性チェックステップ３２６へ進む。整形性チ
ェックと妥当性チェックのどちらも選択されなかった場
合、処理３４４は、点線で示された境界線３５８上の
“ｄ”から、アクション選択ステップ３３４へ進む。

【００６６】整形性チェックステップ３２０は、対応す
るプロセッサ４１４及び５０５を用いて、整形性チェッ
クを実行し、選択的処理３４６の一部分を形成してい
る。処理３４６の選択的性質は点線を用いて示される。
同様に、妥当性ステップ３２６はサブ処理３４８の一部
分を形成し、その選択的性質は点線で示されている。

【００６７】［３］に表される階層表現により、文字列
の比較がより高速でより効率的な数値の比較に置き換え
られることは明らかである。それに従って関連する計算
の負荷が軽減される。さらに、［３］で示される階層表
現は、［１］で示される階層表現よりもメモリ効率に優
れており、それに対応して［３］で示される表現は、前
述したようなメモリ制約のあるアプリケーションにより
適している。

【００６８】図３Ｃに戻り、整形性チェックが選択さ
れ、ステップ３２０で整形性チェックが実行された後、
パース処理３４４は誤りチェックステップ３２２へ向か
う。ここでは、誤りが検出されると、矢印３２４で示さ
れるように、修正動作が実行され、及び/又は、誤りが
指示される。整形性チェックは、文書中のタグが適切に
ネストになっているかどうかを一般的に考慮する。従っ
て、例えば、［２］を参照すると、“Hamlet”と“/Ham
let”のタグペアは“Shakespeare”と“/Shakespeare”
のタグペア内に適切にネストになっている。なぜなら、
“Hamlet”タグペアは、完全に“Shakespeare”タグペ
ア内にネストになっており、そのタグペア同士は、例え
ば、互いに重なり合っていないからである。

【００６９】一方、誤りが検出されなかった場合、パー
ス処理３４４はオプションの処理３４８へ向かう。ここ
において、ＤＴＤ及びＸＭＬスキーマに関して、対応す
るプロセッサ４１４及び５０５を用いた、妥当性チェッ
クステップ３２６が実行される。前述のように、妥当性
チェックは整形性チェックよりも詳細にチェックを行う
ものである。従って、例えば、整形性チェックは、“Ha
mlet”のタグのペアが“Shakespeare”のタグペアの間
に正しくネストになっているとみなすのに対し、妥当性
チェックは、これとは異なり、“Hamlet”のタグペアが
“Shakespeare”のタグペアの間に完全にネストになっ
ているという正しいネストのチェックだけでなく、“Ha
mlet”のタグペアがこの方法で、正当なネストになって
いるかどうかのチェックも行う。例えば、実際、“Shak
espeare”のタグペアが“Hamlet”のタグのペアの間に
ネストにならなければならず、この逆のネストではだめ
な場合もある。従って、妥当性チェック処理は、この場
合、ネストが適切であるかどうか、すなわち完全に実行
されるかどうかに加え、“Hamlet”タグペアが“Shakes
peare”のタグペアの間にネストになり得るかどうか、
というタグの階層表現もチェックする。

【００７０】妥当性ステップ３２６を実行するため、Ｄ
ＴＤ／ＸＭＬスキーマのメモリ表現を、ハッシュステッ
プ３１８で生成されたマークアップ文書のハッシュの性
質に一致するように、ＤＴＤ又はＸＭＬスキーマタグ
は、ハッシュステップ３２８で最初にハッシュにしてお
く。妥当性チェックステップ３２６は、ステップ３１８
で生成された文書の構造表現と、ステップ３２８で生成
されたＤＴＤ／ＸＭＬスキーマの構造表現とを比較す
る。そして、マークアップ文書の構文要素の正しい構文
配置を検証する。なお、図２のステップ２２０で用いら
れるように、この比較で必要な文字列の比較は、ステッ
プ３２８及び３１８のハッシュ演算の結果、ここで、図
３Ｃにおいて、より高速でより効率的な数値の比較に置
き換えられる。

【００７１】妥当性チェックの後、処理３４４は誤りチ
ェックステップ３３０へ向かう。ここでは、矢印３３２
で示されるように、修正動作及び/または誤り指示が実
行される。誤りがなかった場合、パース処理３４４は、
アクションステップ３３４へ進む。ここにおいて、構文
要素のタイプがタグの場合、パース処理が実行されてい
るアプリケーションに、対応するタグの文字列が送ら
れ、タグの文字列自体は、図５及び６にある４１８又は
５１２のメモリから消去される。しかし、関連するハッ
シュで表されたタグのメモリ表現は保持される。従っ
て、現在解析されているタグの文字列のコピーを除け
ば、タグの文字型のメモリ表現は保持されない。タグの
メモリ表現は、これによりハッシュの形式だけとなる。
要素の構文タイプが非タグタイプの場合、又は非タグ名
タイプの場合、矢印３３８で示されるように、要素の値
又は文字列の表現は、関連のアプリケーションへ送ら
れ、関連のメモリ表現は消去される。パース処理３４４
は今、矢印３４０で示されるように、点線で示された境
界線３５８上の“ｆ”へと折り返し、その後図３Ｂの点
線で示された境界線３５８上の対応する“ｆ”へ向か
い、その後点線で示された境界線３５８上の“ｂ”へ向
かい、その後図３Ａの点線で示された境界線３５６上の
対応する“ｂ”へ向かい、最後に文字テストステップ３
０２へと向かう。これ以上文字が検出されなければ、パ
ース処理３４４はステップ３４２で終了する。

【００７２】ＸＭＬ文書部［１］は、ハッシュ形式のタ
グを持つようになり、以下のような形式で示される。

【００７３】 505 <133> 110 <!--This is a comment--> 515 <326 class="preface"Name1="value1"name2="value2"> 520 <371 list=&lt;> </371> 525 <787> 130 Say ［４］ 535 <629> 540 goodnight</629>, 545 Hamlet. </787> 550 <411><629>Goodnight,Hamlet.</629></411> 555 </133>

【００７４】終了タグの表現は（一般的には、開始タグ
に<section>という書式を用いるのに対し、</section>
という書式を用いる）、様々な方法で定義することがで
き、それによってＸＭＬ標準仕様との互換性が高くなっ
たり、低くなったりする。開始タグと終了タグは、現在
の記述において、“同等のタイプ”だとみなされる点に
注意しなければならない。さらに、開始タグと終了タグ
は一まとめにして機能する、すなわち文書内容の部分を
区切ることは、２つのタグに関連性があることを意味す
る。さらに、開始タグと終了タグの前記書式は、終了タ
グが開始タグを修飾していることを意味し、識別文字、
すなわち“/”といったものは、対応する終了タグを作
り出すために開始タグに組み込まれている点に注意しな
ければならない。ＸＭＬ標準仕様との互換性は、場合に
よっては重要となることがある。好適な実施形態におい
て、現在のタグ文字列の‘/'文字は、開始タグと終了タ
グの名前がハッシュ関数から同じ数値が返されるため
に、次のタグの名前をハッシュにする前に、一般的には
取り除かれる。ＸＭＬタグの例は、インターネット上の
http://www.w3.org/tr/2000/rec-XML-20001006.html
で入手できる『拡張可能なマークアップ言語（ＸＭＬ）
1.0（第２版）W３Ｃ勧告、2000年10月６日』の3.1節に
見られるように、</Name Attribute>によって示され
る。現在の記述では、“タグ”は、文脈によって、考慮
している特定のタグの一部分又は全体のいずれかを参照
する。一方、メモリ中では‘/’文字（終了タグを識別
する）に相当する表現を保持することが必要となる場合
もありうる。これは、以下のさまざまな方法で行われ
る。例えば、（ｉ）終了タグであることを示すために、
終了タグのハッシュ数字の近傍で、‘/’文字又はそれ
に相当する文字をメモリに「再挿入」すること、又は
（ｉｉ）ハッシュタグの始まりか終わりの状態を示すブ
ール値を用いること、又は、（ｉｉｉ）完全にマッチン
グした場合、開始タグと終了タグの単純な和がゼロとな
るように、終了タグのハッシュ値を負にすること、等が
挙げられる。（ｉｉｉ）の場合、開始タグのハッシュ
は、本実施形態において、必要な終了タグのハッシュを
作り出すために、単純な否定演算子によって変更され
る。（ｉｉｉ）は、符号ビットがハッシュアルゴリズム
に影響を受けないという保証が必要である。事実上、
（ｉｉｉ）はブールフラグオプション（ｉｉ）とほとん
ど同じである。

【００７５】さらに、構造化されたハッシュ番号が作ら
れ、そこではネストになったタグ用のハッシュ番号は、
第１のタグがネストになっているところではより高レベ
ルのＸＭＬタグであることを明示できる。従って、例え
ば、タグ123がタグ987の内部にネストになっているとこ
ろでは、ネストになったタグ123のように示す代わり
に、987.123のように示すことができる。この構造化さ
れたハッシュ又は“拡張された”ハッシュにより、また
がった構造の演算が減少する。すなわち、タグのペアの
終了点を検索している間にメモリに保持しなければなら
ないＸＭＬ文書の量を減らすことによって解析の性能を
さらに向上することができる。

【００７６】拡張された表現は、ハッシュに基づく必要
はなく、文字列や“数え上げ法”に基づくことができる
という点にも注意しなければならない。数え上げ法は、
タグの名前と数字の間で配置が定義され、目録表や索引
が作られる処理である。数え上げ法の簡単な形式は、全
てのタグの名前を単にリストにし、列記されたタグに番
号を付けたものである。従って、例えば、"Shakespear
e.banquo.quote"の形式の連結文字列は、３つの連結タ
グの文字型拡張表現を表す。

【００７７】ＸＭＬ部［３］に対する構造化された同等
のハッシュにされたマークアップの例は、負の終了タグ
のハッシュを用いた、以下の［５］で示される。

【００７８】 133 133.326 133.371 133.-371 133.787 133.787.629 -＞013307870629 133.787.-629 -＞-013307870629 133.787 ［５］ 133.411 133.411.629 133.411.-629 133.-411 -133

【００７９】［５］において、ネストになったタグの構
造は、［３］で示される形式から、一連の連結ハッシュ
タグに変換される。ここでは、各々の後続の低レベルの
（すなわち、より深くネストされた）ハッシュタグの階
層レベルは、前の上段の階層レベルに関連付けられる。
これはハッシュで表されたＤＴＤから、同様に解析され
た構造を用いて、簡単な数の比較を実行することができ
る。実際、［５］の各々の行は、［５］の行４及び行５
で示されるように、出くわした一連のハッシュタグを連
結して組み合わさった１つの数字で表される。この１つ
の数字は、元の入力タグの識別と関係を非常に圧縮され
た形で表し、それによって同様にハッシュで表されたＤ
ＴＤと非常に効率のよい比較ができる。数字のタグセッ
トは、文書構造を表すために、非常に圧縮された形で用
いることができることがわかる。妥当性チェックは、単
にハッシュで表された開始タグのセットを用いるだけで
実行でき、各々のこのセットは、文書構造の各々の枝の
最も深い、全体の、構造を表す点に注意が必要である。
例えば、［５］の構造を最小限に表したものは、以下の
［６］のように示される。

【００８０】 01330326 01330371 ［６］ 013307870629 013304110629

【００８１】また、ＤＴＤ又はＸＭＬスキーマ構造も同
じ方法によって表すことができる。

【００６６】解析とハッシュが行われた入力文書からの
タグセットと、解析とハッシュが行われたＤＴＤの間の
１つ又は複数の数値の比較は、ＸＭＬパーサの妥当性に
通常必要とされる一連の文字列及び構造の比較を置き換
える。ＤＴＤ又はＸＭＬスキーマによって定義されたど
んな代替構造も、入力ＸＭＬ文書から生じたハッシュタ
グセット数字と後で比較するために用いる単一ハッシュ
タグセット数字にコード化できることがわかる。

【００８２】図４は、例えば、ＤＴＤ又はＸＭＬスキー
マのようなＶＲＤに対して、マークアップ文書を検証す
るための処理６００を示したものである。処理６００
は、検証されるマークアップ文書が開かれるステップ６
０２から始まる。その後、ステップ６０４で、現在の拡
張タグは、図５又は図６の各々のプロセッサ４１４又は
５０５によってリセットされる。図４の説明において、
“タグ”、“拡張タグ”、“テンポラリータグ”等は、
各々のタグのハッシュ表現を指す。以下のステップ６０
６では、テンポラリータグのルートは、各々のプロセッ
サ４１４又は５０５の１つによってリセットされ、その
後、マークアップ文書中の次のタグが、ステップ６０８
で識別される。その後、テストステップ６１０は、ステ
ップ６０８で識別されたタグが開始タグであるかどうか
判断する。テストステップ６１０のイベントでは、処理
６００は「ＹＥＳ」矢印に応じてステップ６１２へ向か
う。ステップ６１２では、ステップ６０８で識別された
タグを、各々のプロセッサ４１４又は５０５のうち１つ
を用いた拡張タグに加える。次に、処理６００はステッ
プ６１２からステップ６０８へ戻る。

【００８３】テストステップ６１０が、次のタグは開始
タグではないと判断した場合、処理６００は「ＮＯ」矢
印に応じて、拡張タグが“０”かどうかを判断し文書の
ルートレベルを表すテストステップ６１４へ向かう。
“０”の値が検出された場合、処理６００は「ＹＥＳ」
矢印に応じて、文書の終わりに到達したかどうかを判断
するテストステップ６２４へ向かう。もしそうでない場
合には、処理６００は「ＮＯ」矢印に応じてステップ６
０６へ向かう。なお、ステップ６１４で“０"の値が検
出されるのは、開始タグと終了タグの数が合わない構造
等のように、整形性のない文書構造だからかもしれな
い。

【００８４】テストステップ６１４が、拡張タグの値が
“０”でないことを判断した場合、処理は「ＮＯ」矢印
に応じて、拡張タグがテンポラリータグのルート値と等
しいかどうかを判断するテストステップ６１６へ向か
う。そうでない場合には、処理６００は「ＮＯ」矢印に
応じて、各々のメモリ４１８及び５０６中に文書リスト
中の拡張タグを格納するステップ６１８へ進む。一方、
テストステップ６１６が、拡張タグがテンポラリータグ
のルートに等しいことを判断した場合、処理６００は各
々のプロセッサ４１４と５０５を用いて、「ＹＥＳ」矢
印に応じて拡張タグから最も低い（すなわち最も深いネ
ストである）タグを取り除くステップ６２０へ向かう。
その後、処理６００は、ステップ６２２で拡張タグをテ
ンポラリータグのルートにコピーし、処理はステップ６
０８へ戻る。

【００８５】テストステップ６２４に戻る前に、これま
で記述されていたように、処理６００は正当性がチェッ
クされるマークアップ文書へ向かう点に注意しなければ
ならない。しかし、明確には記述されていないが、妥当
性参照文書（ＶＲＤ)に適用される同一の処理も存在
し、この処理によって処理６００により作り出される文
書リストをテストできるＶＲＤリストが作り出される。
処理６００及びＶＲＤに向かうそれに相当する処理は、
異なる時間に通常発生する。処理６００は、検証される
全ての文書に対して発生し、各々の特定の文書を検証す
るために拡張したハッシュ表現のリストを作り出す。Ｖ
ＲＤリストがステップ６２６の前に完成される場合、Ｖ
ＲＤリストは処理６００と実質的には同時に作り出すこ
とができる。一方、ＶＲＤ処理はオフラインで実行する
ことができ、結果のリストはステップ６２６の前に処理
６００に与えられる。

【００８６】ステップ６２６に戻ると、前述のようにＶ
ＲＤリストが入手できるので、ステップ６２６は文書リ
スト中の全ての入力がＶＲＤリストに見つかるかどうか
を判断する。もしそうである場合には、処理６００は
「ＹＥＳ」矢印に応じて、文書は妥当であると宣言する
ステップ６２８に向かう。一方、文書リストがＶＲＤリ
ストには見られない入力を持つ場合、処理６００は「Ｎ
Ｏ」矢印に応じて、文書が無効であると宣言するステッ
プ６３０に向かう。

【００８７】ステップ６２６でさらに詳しく述べられて
いるように、前記記述では、文書リストの全ての入力と
ＶＲＤリストの全ての入力を比較する。もう１つの処理
は、ステップ６１６の後に、ステップ６２６と同様のス
テップでの完全なＶＲＤリストに対して、各々の拡張タ
グをテストすることである。この処理のイベントでは、
文書拡張タグがＶＲＤリストに見つからなかった場合、
これ以上不要なテストを行わずに、処理６００がステッ
プ６３０に直接進むことができる。しかし、拡張タグが
見つかった場合、処理６００はステップ６２０等に向か
うことができる。この処理によって誤りを早く認識し、
ただちに妥当性処理を終了することができる。ＶＲＤリ
ストが短ければさらに効率がアップする。完全な妥当性
チェックが、前記方法で実行される場合、ステップ６２
８は考慮している文書が妥当であることを示す。

【００８８】前述の妥当性の方法をさらに説明するため
に、以下の構造部（ここでは開始タグが“01"から“05"
であり、対応する終了タグはそれぞれ“-01"から“-05"
である）を考える。

【００８９】 01 02 03 -03 04 ［７］ -04 -02 05 -05 -01

【００９０】機能面から言えば、処理６００はマークア
ップ文書の階層構造の最も深い枝の部分に降りる。すな
わち［７］の第１行にある“01”から［７］の第３行に
ある“03”へ向う。そして、その特定の枝の最も深い部
分を表す拡張ハッシュ表現、すなわち“010203”を格納
する。次に、この処理は、新たに探索すべき枝を示す別
の開始タグ（この例の場合、［７］の５行目にある“0
4”）を見つけるまで、終了タグを捨て、枝を横切る。
処理が新しい枝に降りる場合、その処理は、階層のより
高いレベルにある拡張ハッシュ表現を保存する。これら
のハッシュ表現は、処理がこれらのレベルに戻るまで保
存される。文書構造中の誤り（無効の文書、又は整形性
されていない文書）は、これらのＶＲＤにマッチングし
ない拡張ハッシュ表現を通常返す。ステップ６２０は、
前の開始タグに対して検索された終了タグの整形性チェ
ックを任意的に含んでもよく、その結果、文書に整形性
があれば整形性マッチを提供する。前出の開始タグは、
拡張ハッシュ表現の中で最低のタグである点に注意すべ
きである。例えば、ＤＴＤ/ＸＭＬスキーマは、ステッ
プ６１０で、ステップ６２０の拡張ハッシュ表現にある
最低の開始タグにマッチングしない終了タグを返し、そ
れによって整形性チェックにひっかかることになるかも
しれない。

【００９１】ステップ６２６でのテストは、一般的に、
その文書のＤＴＤ用にリストになったハッシュ表現に対
して、マークアップ文書構造の拡張ハッシュ表現をマッ
チングさせようとする。文書構造のハッシュ表現は、一
般的にＤＴＤリストにある最も深い構造表現のサブセッ
トである。従って、妥当なＸＭＬ文書は、対応するＶＲ
Ｄ又はＤＴＤ中に定義されている、あらゆる正当な構造
的ネストのサブセットを含んでよい。従って、ステップ
６２６における一般的なテストでは、ＤＴＤのより深い
ハッシュ表現と、文書のより浅いハッシュ構造表現との
比較を含む。従って、例えば、ＸＭＬ文書からの拡張ハ
ッシュ表現“0123"は、対応するＤＴＤからのハッシュ
表現“01230456"と比較した場合、「妥当性がある」と
評価される。

【００９２】図４に示される妥当性処理６００は、高速
だが不完全な妥当性チェックを用いて、最も深くネスト
になった部分等の、文書構造中のより複雑な部分をチェ
ックするように、最適化されうる。従って、任意の性能
特性を有する特定の妥当なパーサを実行するために、速
度と妥当性の感度の最適な組み合わせを選択できる。

【００９３】また、妥当性方法６００を変更して「標準
的な」整形性チェックの少なくとも一部分を実行するこ
ともできる。従って、例えばステップ６２０において、
拡張タグ表現の中で、最も低い階層にあるタグ表現のハ
ッシュに対して、終了タグのハッシュ表現をチェックす
ることができる。前記表現が、同じオリジナルのタグで
あると適切に識別されなかった場合、その文書は整形性
がなく、回復や誤り処理が実行される。

【００９４】前記方法は、構造チェックとは別にまたは
一緒に、構造内で定義された属性のハッシュ表現を含む
ように拡張できる。

【００９５】この妥当性及び整形性チェックの方法を、
別々の処理における入力文書や、文書構造及び内容を解
析する処理に対して、適用できることは明らかである。
従って、例えば、方法６００は、中央演算処理装置(Ｃ
ＰＵ)サイクル及びメモリサイズが特に大きな制約を受
けていない環境においても、妥当性及び整形性チェック
を、効率良く、高速に実行できるようにするために、最
適化することができる。そのようなシステムで別々のチ
ェックを実行する利点として、高度に最適化されたチェ
ックを用いて、「妥当性のない」文書を直ちに廃棄する
ことができるという事実が挙げられる。これは、少なく
とも妥当でない文書の一部分にかける時間と処理を大幅
に節約することができる。それによって、例えば、(i)
文章が妥当でないことを見つけるためだけに、文章を解
析して完全なＤＯＭツリー表現にし、妥当性チェックを
実行すること、又は(ii)妥当でない文書の第２の部分を
検出する前に、文書の第１の（妥当な）部分の処理を更
に開始すること（文書の第１部分の処理がそれによって
無駄になっている）を防ぐことができる。もう１つの利
点は、高速な妥当性チェックを用いて文書に妥当性がな
いとわかった後、次のジョブの処理を直ちに始められる
点である。

【００９６】「不完全な」ハッシュ処理、すなわち、各
々の英数字の入力文字列に対して単一の数字を作りだす
保証がないハッシュ処理にも、適した場合があり、特
に、ＸＭＬタグ文字列の最大長が制限されている、又は
ある確率で少なくとも制限されている場合に適してい
る。さらに、ＸＭＬタグ文字列セットが限られた数の文
字順列に制限されるか、又は限られた数の文字順列に制
限される可能性がある場合、適切に動作するために不完
全なハッシュ処理が設計され、選択される。

【００９７】文書構造の数的表現のための通信規格、又
は、代替の公用及び私的フォーマットは、ハッシュアル
ゴリズムの使用に基づいて、定義され、記述される。こ
の技術によって、冗長性のために大量のデータ伝送を通
常伴う、ＸＭＬデータの伝送にメリットとなる圧縮形式
及び人間が読み易いASCII形式が可能となる。人間の読
み易さを保持するか、しないかに対して、様々な選択肢
が存在する。例えば、（完全な）ハッシュを、他の圧縮
形式と組合わせることが挙げられる。これは、ＸＭＬフ
ァイル中の様々な要素タイプにそれぞれ適用される例え
ば、ＸＭＬ文字列タグを、完全なハッシュアルゴリズム
から得られる、ユニークで、人間が読みやすい数字に、
置き換えることができる。また、ハッシュではない構文
要素及び他の要素は、処理又は装置間で、伝送用の非損
失圧縮技術によって圧縮することができ、それによっ
て、伝送データ量が減少する。

【００９８】前段落で述べたように、必要なところに、
逆ハッシュアルゴリズム又は可逆ハッシュアルゴリズム
を参照したり、含んだりすることができる。これは、例
えば、ハッシュされる前の、伝送された、マークアップ
文書から、表示したり、ラベリングしたりする目的で、
１つ以上のマークアップタグを人間が読み易い文字列に
デコード、又は解読するために、そのようなアルゴリズ
ムが必要とされる場合に用いられる。ここでは、別に、
解析や誤りチェックのためにそのようなことを行う必要
はない。可逆ハッシュアルゴリズム、又は逆ハッシュア
ルゴリズムのもう１つ利用法は、マークアップタグ又は
他のデータを解読することによって、伝送されたマーク
アップ文書について制限された機能や特徴が使用できる
ようになることである。可逆アルゴリズム、又は逆アル
ゴリズムは、マークアップ文書の送信部と受信部のマッ
チングに使用することができる。可逆ハッシュアルゴリ
ズム、又は逆ハッシュアルゴリズムは、受信部に既に含
まれているので伝送はされないが、マークアップ文書で
参照される場合もある。可逆ハッシュアルゴリズム、又
は可逆ハッシュアルゴリズムには、(i) 完全非損失アル
ゴリズム、及び(ii)ハフマン符号化、が例として挙げら
れる。

【００９９】上記機構は、以下の条件の１つ以上が当て
はまる場合には、あらゆるマークアップ言語に対して、
非常に有利な立場で適用することができる。その条件と
は、すなわち、(i) マークアップ言語はタグ名の定義
（例えば、ＸＭＬ、ＤＴＤ、ＣＳＳ、ＸＳＬ等）を許
す、(ii)タグ名は大きな文字コードテーブル（例えば、
UTF-16）を使用し、及び/又は、タグ名の長さは一般的
にそのハッシュ表現よりも短くない、(iii)マークアッ
プ文書を用いる又は受け取る使用アプリケーションは、
マークアップ文書、ＸＭＬスキーマ又はＤＴＤの中に最
低でも１つのネストの階層レベルを持った、複雑な構造
表現を通常必要とする、(iv)入力マークアップ文書は、
何らかチェック形式、通常は整形性又は妥当性チェック
が必要である、(v) マークアップパーサ、及び/又は、
アプリケーションは、メモリ容量（例えば、組み込み式
又は低価格ＣＰＵシステム）又はメモリ管理（例えば、
仮想メモリがないシステム、又はダイナミックメモリが
割り当てられていないシステム）に厳しい制限がある、
(vi)複雑で、高度にネストなる可能性があるマークアッ
プ文書上で素早く動作する必要があるマークアップパー
サ及び/又は、アプリケーションである。

【０１００】本明細書で示されたマークアップ言語文書
の解析方法は、マークアップ言語文書の解析用関数、又
はサブ関数を実行する、１つ以上の集積回路等の専用ハ
ードウェアで実行できる。そのような専用ハードウェア
は、画像プロセッサ、ディジタル信号プロセッサ、又は
１つ以上のマイクロプロセッサ及び関連メモリを有して
いてもよい。マークアップ言語文書の解析方法は、一
方、専用組込みコンピュータシステム４００を用いて、
実行することができる。そのようなシステムは図５で示
される。このシステムにおいて、図３Ａ、図３Ｂ、図３
Ｃ、及び図４の処理は、組込みコンピュータシステム４
００中で実行されるアプリケーションプログラム等のソ
フトウェアとして実行されてもよい。コンピュータシス
テム４００は、典型的には、プリンタ（図には示されて
いない）等のエンドシステムに組み込まれ、プリンタ中
のプリンタエンジン４０２を動作させる。特に、組込み
コンピュータによって実行されるソフトウェアの命令に
よって、マークアップ言語の解析方法のステップが行わ
れる。そのソフトウェアは、読み出し専用メモリ（ＲＯ
Ｍ）４１８、ランダムアクセスムモリ（ＲＡＭ）４１
８、又は他のタイプのメモリ（示されていない）を含ん
だコンピュータ可読媒体に収納されてもよい。そのソフ
トウェアは、製造時に組込みコンピュータにロードされ
るか、或は、その場でソフトウェアのアップグレードが
行われる。

【０１０１】組込みコンピュータシステム４００は、コ
ンピュータモジュール４１０、パラメタ設定用のスイッ
チモジュール４２２等の入力装置、ジョブ状態を示す液
晶表示器（ＬＣＤ）等の出力装置、プリンタエンジン４
０２で構成される。組込みコンピュータ４００は、通
常、物理的にプリンタ（示されていない）に組み込まれ
る。コンピュータネットワーク４０４に接続された他の
コンピュータ（示されていない）で起こった印刷ジョブ
は、入出力（Ｉ／Ｏ）インターフェース４０８への接続
４０４によって、組み込みコンピュータ４００に送られ
る。

【０１０２】組込みコンピュータモジュール４１０は、
プロセッサユニット４１４及びメモリユニット４１８、
更に、例えば、半導体ランダムアクセスメモリ（ＲＡ
Ｍ）、読み込み専用メモリ（ＲＯＭ）、スイッチモジュ
ールとＬＣＤインターフェース４１６を含む入出力（Ｉ
／Ｏ）インターフェース、プリンタエンジン４０２とネ
ットワーク４０６用の入出力インターフェース４０８で
構成される。組込みコンピュータ４１０の構成要素４０
８及び構成要素４１４〜４１８は、通常相互接続された
バス４１２を介して交信しており、これは関連技術で知
られる組込みコンピュータシステム４１０の従来動作モ
ードのようになる。一般的に、この機構に関するプログ
ラムは、メモリ４１８に格納され、プログラム動作時に
プロセッサ４１４がプログラムを読み込んで制御する。

【０１０３】また、マークアップ言語文書の解析方法
は、図６で示されるような、従来型汎用コンピュータシ
ステム５００を用いて実行することができる。このシス
テムにおいて、図３Ａ、図３Ｂ、図３Ｃ、及び図４の処
理は、コンピュータシステム５００中で動作するアプリ
ケーションプログラム等のソフトウェアとして実行され
てもよい。このアプリケーションは、例えば、ハッシュ
が、ネットワークを介したコンピュータ間の通信規格と
して用いられる場合に役立つ。図６は、現在考慮してい
る通信コンピュータの一例を示したものである。

【０１０４】特に、マークアップ言語文書の解析方法の
ステップは、コンピュータによって実行されるソフトウ
ェアの命令によって行われる。そのソフトウェアは２つ
の分離部品に分けられてもよい。すなわち、１つは解析
方法を実行する部分で、もう１つは後者とユーザの間の
ユーザーインターフェースを管理する部分である。例え
ば、そのソフトウェアは、以下に示す記憶装置を有する
コンピュータ可読媒体に格納されてもよい。そのソフト
ウェアはコンピュータ可読媒体からコンピュータにロー
ドされ、次にコンピュータにより実行される。そのよう
なソフトウェアを有するコンピュータ可読媒体、又は前
記媒体に記録されたコンピュータプログラムは、コンピ
ュータプログラム製品である。このコンピュータプログ
ラム製品のコンピュータでの使用は、本発明の実施形態
に応じて、マークアップ言語文書を解析に有利な装置で
実行されるのが望ましい。

【０１０５】コンピュータシステム５００は、コンピュ
ータモジュール５０１、キーボード５０２及びマウス５
０３等の入力装置、プリンタ５１５及びディスプレイ装
置５１４を含む出力装置で構成される。変調・復調（モ
デム）送受信装置５１６は、例えば、電話線５２１又は
他の機能媒体を介して接続可能な通信ネットワーク５２
０へ双方向で通信するために、コンピュータモジュール
５０１で用いられる。モデム５１６は、インターネット
や他のネットワークシステム、例えば、ローカルエリア
ネットワーク（ＬＡＮ）又はワイドエリアネットワーク
（ＷＡＮ）、コンピュータ５００と通信している他のパ
ーソナルコンピュータ（ＰＣ）５２２等へアクセスでき
るようにするために用いられる。

【０１０６】コンピュータモジュール５０１は、典型的
には、少なくとも１つのプロセッサユニット５０５、メ
モリユニット５０６を含み、例えば、半導体ランダムア
クセスメモリ（ＲＡＭ）、読み込み専用メモリ（ＲＯ
Ｍ）、ビデオインターフェース５０７を含んだ入力・出
力（Ｉ／Ｏ）インターフェース、キーボード５０２及び
マウス５０３用の入力・出力インターフェース５１３、
及びオプションとしてのジョイスティック（図で示され
ていない）、モデム５１６のためのインターフェース５
０８で構成される。

【０１０７】記憶装置５０９が設けられており、通常、
ハードディスクドライブ５１０及びフロッピー（登録商
標）ディスクドライブ５１１を含む。また、磁気テープ
ドライブ（不図示）を用いてもよい。ＣＤ−ＲＯＭドラ
イブ５１２は、非揮発性のデータ源として通常備えられ
る。コンピュータモジュール５０１の構成要素５０５〜
５１３は、相互接続されたバス５０４を介して通常交信
し、これは関連技術で知られるコンピュータシステム５
００の従来動作モードのようになる。本実施形態におい
て実行できるコンピュータには、IBM PC、IBM PC互換
機、及びSun Sparcstations又はそこから発展した同様
のシステムが例に挙げられる。

【０１０８】典型的には、本実施形態におけるアプリケ
ーションプログラムは、ハードディスクドライブ５１０
上に格納され、プログラム動作時にプロセッサ５０５が
プログラムを読み込んで制御する。ネットワーク５２０
から取り出されたプログラム及びあらゆるデータの中間
記憶装置は、場合によってはハードディスクドライブ５
１０と連動して、半導体メモリ５０６を用いて実現して
もよい。場合によっては、アプリケーションプログラム
は、ＣＤ−ＲＯＭ又はフロッピーディスクにエンコード
してユーザに供給されてもよく、対応するドライブ５１
２又は５１１を介して読み込まれるか、代わりに、モデ
ム装置５１６を介してネットワーク５２０上でＰＣ５２
２からユーザによって読まれてもよい。

【０１０９】さらに、磁気テープ、ＲＯＭ、集積回路、
磁気光ディスク、ラジオ又はコンピュータモジュール５
０１及び別の装置間の赤外線トランスミッションチャン
ネル、ＰＣＭＣＩＡカード等のコンピュータ可読カー
ド、電子メールの送信及びウエブサイトやそれと同様の
ものを有するインターネット及びイントラネットを含む
他のコンピュータ可読媒体から、コンピュータシステム
５００にソフトウェアをロードすることもできる。上記
は、コンピュータ可読媒体に関連した例に過ぎない。発
明の範疇や技術的思想から外れない限り、他のコンピュ
ータ可読媒体は、実行してもよい。

【０１１０】（産業上の利用分野）以上から、本発明の
実施形態は、コンピュータ及びデータ処理産業に適用で
きることは明らかである。上記は、本発明の実施形態の
いくつかを示したに過ぎず、発明の範囲や意図から外れ
ない限り、修正及び/又は変更を行うことができる。上
記実施形態は、例に過ぎず、限定的なものではない。

【図面の簡単な説明】

【図１Ａ】本発明の好適な実施形態に係るＸＭＬパーサ
システムのブロック図である。

【図１Ｂ】本発明の好適な実施形態に係るＸＭＬパーサ
システムのブロック図である。

【図２Ａ】選択的な整形性チェック及び/又は妥当性チ
ェックを含む、従来技術におけるＳＡＸパーサの方法ス
テップを示すフローチャートである。

【図２Ｂ】選択的な整形性チェック及び/又は妥当性チ
ェックを含む、従来技術におけるＳＡＸパーサの方法ス
テップを示すフローチャートである。

【図３Ａ】図２Ａ及び図２ＢのＳＡＸパーサを改良した
機構を示す図である。

【図３Ｂ】図２Ａ及び図２ＢのＳＡＸパーサを改良した
機構を示す図である。

【図３Ｃ】図２Ａ及び図２ＢのＳＡＸパーサを改良した
機構を示す図である。

【図４】ＤＴＤ又はＸＭＬスキーマ等の参照文書に対す
る、文書の妥当性の処理について示す図である。

【図５】改良されたＳＡＸパーサの機構を実行できる専
用組込みコンピュータのブロック図である。

【図６】改良されたＳＡＸパーサの機構を実行できる汎
用コンピュータを示す図である。

Claims (58)

【特許請求の範囲】
1. 【請求項１】構文要素を含むマークアップ言語文書を解
   析する解析方法であって、前記構文要素の内の一要素に
   対し、 前記一要素のタイプを識別する識別ステップと、 前記タイプが第１タイプであれば、そのハッシュ表現を
   決定することによってその要素を処理する処理ステップ
   と、 前記タイプが前記第１タイプであれば、前記ハッシュ表
   現を用いて、前記文書の少なくとも部分的な構造表現を
   増大させる増大ステップと、 を含むことを特徴とする解析方法。
2. 【請求項２】イベント駆動型であることを特徴とする請
   求項１に記載の解析方法。
3. 【請求項３】ハッシュアルゴリズム、 関連ユニバーサルリファレンスインディケータに依存す
   る前記ハッシュアルゴリズムへの第１リファレンス、 関連名前空間に依存する前記ハッシュアルゴリズムへの
   第２リファレンス、 及び、関連エクステンドマークアップ言語宣言に依存す
   る前記ハッシュアルゴリズムへの第３リファレンス、 のいずれかを用いて前記ハッシュ表現を決定することを
   特徴とする請求項１に記載の解析方法。
4. 【請求項４】前記第１タイプは、 構造要素或はその一部、 前記構造要素の定義、 前記構造要素の宣言、及び前記構造要素のマッチ、 のいずれかであることを特徴とする請求項２に記載の解
   析方法。
5. 【請求項５】前記構造要素はタグであることを特徴とす
   る請求項４に記載の解析方法。
6. 【請求項６】前記ハッシュ表現は、前記一つの構文要素
   ごとのユニークなコードであり、前記一構文要素は第１
   文字数以下であることを特徴とする請求項２に記載の解
   析方法。
7. 【請求項７】前記ハッシュ表現は、前記一つの構文要素
   ごとにユニークなコードではなく、前記一構文要素は、
   （i）前記要素の文字数、及び(ii)前記要素の文字の順
   列の許容数、のうちの少なくとも一つの観点から、ある
   可能性レベルまで制約を受けることを特徴とする請求項
   ２に記載の解析方法。
8. 【請求項８】前記コードは、英数字を含むことを特徴と
   する請求項６に記載の解析方法。
9. 【請求項９】前記処理ステップは、（ｉ）前記第１タイ
   プの第１インスタンスである前記一構文要素と（ｉｉ）
   前記第１タイプの第２インスタンスである他方の構文要
   素と、の両方の拡張ハッシュ表現を決定するサブステッ
   プを含み、 前記第１インスタンス内に、前記第２インスタンスがネ
   ストになっていることを特徴とする請求項２に記載の解
   析方法。
10. 【請求項１０】前記構文要素の内の他要素について、更
    に、 前記他要素のタイプを識別するステップと、 前記他要素のタイプが前記第１タイプと同等である場合
    に、 （ｉ）前記他要素を処理し、それによってその第２ハッ
    シュ表現を決定する第２処理ステップと、 （ｉｉ）前記第２ハッシュ表現を用いて、前記文書の少
    なくとも部分的な構造表現を増大させる増大ステップ
    と、を有し、 前記処理ステップ及び前記第２処理ステップは、前記一
    要素と前記他要素の間に第１の関係が存在する場合に、
    第１の関係に対応する第２の関係が、前記一要素のハッ
    シュ表現と、前記他要素のハッシュ表現との間に存在す
    ることを特徴とする請求項１に記載の解析方法。
11. 【請求項１１】前記一要素は、開始タグであり、 前記他要素は、終了タグであり、 前記一要素のハッシュ表現は、対応ハッシュ開始タグで
    あり、 前記他要素の第２ハッシュ表現は、対応ハッシュ終了タ
    グであることを特徴とする請求項１０に記載の解析方
    法。
12. 【請求項１２】前記終了タグは、前記開始タグの第１変
    形であり、 前記ハッシュ終了タグは、前記ハッシュ開始タグの第２
    変形であり、 前記第２変形は、前記第１変形に対応することを特徴と
    する請求項１１に記載の解析方法。
13. 【請求項１３】前記終了タグは、そこに識別文字が組込
    まれること以外は、前記開始タグと同一であり、 前記ハッシュ終了タグは、 前記ハッシュ開始タグと同一のもの、 そこに識別文字が組込まれること以外は前記ハッシュ開
    始タグと同一のもの、及び オペレータによって処理されたハッシュ開始タグと同一
    のもの、 の内の少なくとの一つであることを特徴とする請求項１
    ２に記載の解析方法。
14. 【請求項１４】前記一要素及び前記他要素は、それぞ
    れ、開始タグ及び終了タグを含み、第１タグペアをな
    し、 前記第１タグペアの為の対応ハッシュ開始タグ及び対応
    ハッシュ終了タグは、前記文書の前記部分的構造表現に
    組込まれ、 前記文書は、更に、開始タグと終了タグをそれぞれ含む
    第２タグペアを含み、該第２タグペアは、前記文書の前
    記第１タグペア内にネストされ、 前記解析方法は、更に、 前記第２タグペアを処理し、対応第２ハッシュ開始／終
    了タグを形成するステップと、 前記第２ハッシュ開始／終了タグが、前記第１タグペア
    の為の前記ハッシュ開始／終了タグとの関係で、前記第
    １タグペア内での前記第２タグペアのネストと同等のネ
    ストを示すため、前記対応第２ハッシュ開始／終了タグ
    を用いて、前記文書の前記少なくとも部分的構造表現を
    増大する増大ステップと、 を有することを特徴とする請求項１２に記載の解析方
    法。
15. 【請求項１５】前記増大ステップの前に、更に、 第１ハッシュ開始タグを第２ハッシュ開始タグと連結
    し、第１ハッシュ終了タグを第２ハッシュ終了タグと連
    結し、それにより、前記第２タグペアについてのそれぞ
    れの拡張ハッシュ開始／終了タグを形成し、 前記増大ステップは、前記第２タグペアについての前記
    それぞれの拡張ハッシュ開始／終了タグを用いて実行さ
    れ、 前記拡張ハッシュ開始／終了タグは、前記第１タグペア
    の前記ハッシュ開始／終了タグとの関係で、前記第１タ
    グペア内での前記第２タグペアのネストと同等のネスト
    を示すことを特徴とする請求項１４に記載の解析方法。
16. 【請求項１６】前記増大ステップに続いて、構文規則に
    対する整形性チェックステップが行われ、 該整形性チェックは、前記マークアップ言語文書の前記
    少なくとも部分的な構造表現における要素の対応ハッシ
    ュ表現を数的に比較することによって、前記マークアッ
    プ言語文書の前記少なくとも部分的な構造表現を構文規
    則に照らしてチェックするステップを含むことを特徴と
    する請求項１に記載の解析方法。
17. 【請求項１７】前記数的な比較のステップに続いて、更
    に、 前記構文規則に従い、前記第１タイプではない要素の対
    応非ハッシュ表現を、文字列比較するステップを行うこ
    とを特徴とする請求項１６に記載の解析方法。
18. 【請求項１８】前記第１タイプは、 構造要素或はその一部、 前記構造要素の定義、 前記構造要素の宣言、及び前記構造要素のマッチ、 のいずれかであることを特徴とする請求項１に記載の解
    析方法。
19. 【請求項１９】前記構造要素はタグであることを特徴と
    する請求項１８に記載の解析方法。
20. 【請求項２０】前記文書の前記少なくとも部分的な構造
    表現の整形性を、構文規則に照らしてチェックするチェ
    ックステップを更に含むことを特徴とする請求項１４に
    記載の解析方法。
21. 【請求項２１】前記構文規則は、タグの適正なネストに
    関するものであり、 前記チェックステップは、 前記文書の前記少なくとも部分的な構造表現におけるハ
    ッシュタグに亘る数的比較を行い、それにより、前記第
    １ハッシュ開始／終了タグと、前記第２ハッシュ開始／
    終了タグを識別するサブステップと、 前記第２ハッシュ開始／終了タグが前記第１ハッシュ開
    始／終了タグとの関係で適正なネストを示すことを確認
    するサブステップと、 を含むことを特徴とする請求項２０に記載の解析方法。
22. 【請求項２２】前記数的比較に続いて、 前記構文規則に従い、前記文書の前記少なくとも部分的
    な構造表現におけるそれぞれのタグの非ハッシュ部分に
    亘り、文字列比較を行うステップを更に含むことを特徴
    とする請求項２１に記載の解析方法。
23. 【請求項２３】構文規則に照らして、前記文書の前記少
    なくとも部分的な構文表現の整形性をチェックするステ
    ップを更に有することを特徴とする請求項１５に記載の
    解析方法。
24. 【請求項２４】前記構文規則は、タグの適正なネストに
    関するものであり、 前記チェックステップは、 前記文書の前記少なくとも部分的な構造表現におけるハ
    ッシュタグに亘り数的比較を行い、それにより、前記第
    １ハッシュ開始／終了タグと、前記第２ハッシュ開始／
    終了タグを識別するサブステップと、 前記拡張ハッシュ開始／終了タグが、前記第１ハッシュ
    開始／終了タグとの関係で適正なネストを示すことを確
    認するサブステップと、 を含むことを特徴とする請求項２３に記載の解析方法。
25. 【請求項２５】前記数的比較に続いて、 前記文書の前記少なくとも部分的な構造表現におけるそ
    れぞれのタグの非ハッシュ部分にわたり、文字列比較を
    行うステップを更に含むことを特徴とする請求項２４に
    記載の解析方法。
26. 【請求項２６】前記整形性チェックステップは、妥当性
    参照文書ＶＲＤに照らす妥当性検査ステップによって、
    （ａ）続けられ、（ｂ）含まれ、又は（ｃ）置き換えら
    れ、 前記妥当性検査ステップは、 （ａ）前記ＶＲＤを処理する処理サブステップを含み、
    該処理サブステップは、ＶＲＤにおけるの構文要素ごと
    に、 （ｉ）ＶＲＤの前記構文要素のタイプを識別するサブサ
    ブステップと、 （ｉｉ）前記タイプが、前記第１タイプの場合に、前記
    構文要素を、そのハッシュ表現を決定することによって
    処理するサブサブステップと、を含み、 前記妥当性検査ステップは、更に、 （ｂ）処理されたＶＲＤに照らして前記マークアップ言
    語文書の前記少なくとも部分的な構造表現をチェックす
    るチェックサブステップを含み、該チェックサブステッ
    プは、要素の対応ハッシュ表現を数的に比較するサブサ
    ブステップを含むことを特徴とする請求項１６に記載の
    解析方法。
27. 【請求項２７】ＶＲＤに照らしてマークアップ言語文書
    の妥当性検査を行う検査方法であって、 （ａ）マークアップ言語文書を、そこで識別されるドキ
    ュメントタグごとに、該ドキュメントタグが、対応する
    マークアップ言語のドキュメントタグ階層における第１
    ドキュメントタグでなければ、処理するステップを有
    し、該処理は、 （ｉ）前記ドキュメントタグの階層位置を決定するステ
    ップと、 （ｉｉ）前記ドキュメントタグ階層における前のドキュ
    メントタグのハッシュ表現に連結された、前記ドキュメ
    ントタグの拡張ハッシュ表現を決定するステップと、 （ｉｉｉ）前記ドキュメントタグが前のドキュメントタ
    グよりも深くネストにされる場合に、前記ドキュメント
    タグの前記拡張ハッシュ表現を格納するステップと、を
    含み、 前記検査方法は更に、 （ｂ）ＶＲＤを、そこで識別されるタグごとに、該タグ
    が対応タグ階層の第１タグでない場合に、処理するステ
    ップを有し、該処理は、 （ｉ）前記タグの階層位置を決定するステップと、 （ｉｉ）対応するタグ階層における前のタグのハッシュ
    表現に連結される前記タグの拡張ハッシュ表現を決定す
    るステップと、 （ｉｉｉ）前記タグの前記拡張ハッシュ表現をリストに
    格納するステップと、を含み、 前記検査方法は更に、 （ｃ）前記ドキュメントタグの前記拡張ハッシュ表現
    が、前記リスト内にあるか、或は、前記リストのメンバ
    の妥当なサブセットである場合には、前記マークアップ
    言語文書の妥当性を検査するステップを有することを特
    徴とする検査方法。
28. 【請求項２８】ＶＲＤに照らしてマークアップ言語文書
    の妥当性を検査する検査方法であって、 （ａ）前記ＶＲＤを、そのなかで識別された構造要素ご
    とに、処理する処理ステップを含み、該処理ステップ
    は、 （ｉ）前記構造要素の構文属性を決定するステップと、 （ｉｉ）前記構造要素のハッシュ表現を決定するステッ
    プと、 （ｉｉｉ）前記ＶＲＤの構造表現における、前記構造要
    素の前記ハッシュ表現及び構文属性を格納するステップ
    と、を含み、 前記検査方法は更に、 （ｂ）マークアップ言語文書を、そのなかで識別された
    ドキュメント構造要素ごとに、処理する処理ステップを
    含み、該処理ステップは、 （ｉ）前記文書構造要素の構文属性を決定するステップ
    と、 （ｉｉ）前記文書構造要素のハッシュ表現を決定するス
    テップと、 （ｉｉｉ）前記文書の構造表現における、前記文書構造
    要素の前記ハッシュ表現と構文属性を格納するステップ
    と、を含み、 前記検査方法は更に、 （ｃ）前記文書の前記構造表現における前記各文書構造
    要素の構文属性及びハッシュ表現が、前記ＶＲＤの前記
    構造表現における対応構文属性及びハッシュ表現に一致
    する場合に、前記マークアップ言語文書の妥当性を検査
    するステップを有することを特徴とする検査方法。
29. 【請求項２９】前記数的比較ステップに続いて、更に、
    前記第１タイプでない要素の対応非ハッシュ表現の文字
    列比較ステップを行うことを特徴とする請求項２６に記
    載の解析方法。
30. 【請求項３０】前記第１タイプは、 構造要素或はその一部、 前記構造要素の定義、 前記構造要素の宣言、 前記構造要素のマッチ、 のいずれかであることを特徴とする請求項２６に記載の
    解析方法。
31. 【請求項３１】前記構造要素はタグであることを特徴と
    する請求項３０に記載の解析方法。
32. 【請求項３２】構文要素を含むマークアップ言語文書を
    符号化する符号化方法であって、 前記構文要素の一つについて、 構文要素のタイプを識別するステップと、 （ｉ）前記タイプが第１タイプであれば、前記構文要素
    のハッシュ表現を決定すること、 （ｉｉ）前記タイプが第１タイプでなければ、前記構文
    要素の圧縮表現を決定すること、 （ｉｉｉ）前記構文要素を保持すること、 のいずれかによって、前記構文要素を処理するステップ
    と、 を含むことを特徴とする符号化方法。
33. 【請求項３３】符号化構文要素を含むマークアップ言語
    文書を復号する復号方法であって、 前記符号化構文要素の一つについて、 前記符号化構文要素のタイプを識別するステップと、 （ｉ）前記タイプが第１タイプであれば、前記符号化構
    文要素の逆ハッシュ表現を決定すること、 （ｉｉ）前記タイプが第１タイプでなければ、前記符号
    化構文要素の解凍表現を決定すること、 （ｉｉｉ）前記符号化構文要素を保持すること、 の少なくとも一つで、前記符号化構文要素を処理するス
    テップと、 を含むことを特徴とする復号方法。
34. 【請求項３４】構文要素を含むマークアップ言語文書を
    解析する解析装置であって、 前記構文要素のタイプを識別する識別手段と、 前記タイプが第１タイプである場合に、前記構文要素
    を、そのハッシュ表現を決定することによって、処理す
    る処理手段と、 前記タイプが第１タイプである場合に前記ハッシュ表現
    を用いて、前記文書の少なくとも部分的構造表現を増大
    する増大手段と、 を含むことを特徴とする解析装置。
35. 【請求項３５】ＶＲＤに照らしてマークアップ言語文書
    の妥当性を検査する検査装置であって、 （ａ）マークアップ言語文書を、そこで識別されるドキ
    ュメントタグごとに、該ドキュメントタグが、対応する
    マークアップ言語のドキュメントタグ階層における第１
    ドキュメントタグでなければ、処理する手段を有し、該
    手段は、 （ｉ）前記ドキュメントタグの階層位置を決定する手段
    と、 （ｉｉ）前記ドキュメントタグ階層における前のドキュ
    メントタグのハッシュ表現に連結された、前記ドキュメ
    ントタグの拡張ハッシュ表現を決定する手段と、 （ｉｉｉ）前記ドキュメントタグが前のドキュメントタ
    グよりも深くネストにされる場合に、前記ドキュメント
    タグの前記拡張ハッシュ表現を格納する手段と、を含
    み、 前記検査装置は更に、 （ｂ）ＶＲＤを、そこで識別されるタグごとに、該タグ
    が対応タグ階層の第１タグでない場合に、処理する手段
    を有し、該手段は、 （ｉ）前記タグの階層位置を決定する手段と、 （ｉｉ）対応するタグ階層における前のタグのハッシュ
    表現に連結される前記タグの拡張ハッシュ表現を決定す
    る手段と、 （ｉｉｉ）前記タグの前記拡張ハッシュ表現をリストに
    格納する手段と、を含み、 前記検査装置は更に、 （ｃ）前記ドキュメントタグの前記拡張ハッシュ表現
    が、前記リスト内にあるか、或は、前記リストのメンバ
    の妥当なサブセットであるかのどちらかであることを立
    証し、それによって、前記マークアップ言語文書の妥当
    性を検査する手段を有することを特徴とする検査装置。
36. 【請求項３６】ＶＲＤに照らしてマークアップ言語文書
    の妥当性を検査する検査装置であって、 （ａ）前記ＶＲＤを、そのなかで識別された構造要素ご
    とに、処理する手段を含み、該手段は、 （ｉ）前記構造要素の構文属性を決定する手段と、 （ｉｉ）前記構造要素のハッシュ表現を決定する手段
    と、 （ｉｉｉ）前記ＶＲＤの構造表現における、前記構造要
    素の前記ハッシュ表現及び構文属性を格納する手段と、
    を含み、 前記検査装置は更に、 （ｂ）マークアップ言語文書を、そのなかで識別された
    ドキュメント構造要素ごとに、処理する手段を含み、該
    手段は、 （ｉ）前記文書構造要素の構文属性を決定する手段と、 （ｉｉ）前記文書構造要素のハッシュ表現を決定する手
    段と、 （ｉｉｉ）前記文書の構造表現における、前記文書構造
    要素の前記ハッシュ表現と構文属性を格納する手段と、
    を含み、 前記検査装置は更に、 （ｃ）前記文書の前記構造表現における前記各文書構造
    要素の構文属性及びハッシュ表現と、前記ＶＲＤの前記
    構造表現における対応構文属性及びハッシュ表現とを比
    較し、それにより、前記マークアップ言語文書の妥当性
    を検査する手段を有することを特徴とする検査装置。
37. 【請求項３７】構文要素を含むマークアップ言語文書を
    符号化し、前記文書の少なくとも部分的構造表現を形成
    する符号化装置であって、 構文要素のタイプを識別する手段と、 （ｉ）前記タイプが第１タイプであれば、前記構文要素
    のハッシュ表現を決定すること、 （ｉｉ）前記タイプが第１タイプでなければ、前記構文
    要素の圧縮表現を決定すること、 （ｉｉｉ）前記構文要素を保持すること、 のいずれかによって、前記構文要素を処理する手段と、 を含むことを特徴とする符号化装置。
38. 【請求項３８】符号化構文要素を含むマークアップ言語
    文書を復号する復号装置であって、 前記符号化構文要素のタイプを識別する手段と、 （ｉ）前記タイプが第１タイプであれば、前記符号化構
    文要素の逆ハッシュ表現を決定すること、 （ｉｉ）前記タイプが第１タイプでなければ、前記符号
    化構文要素の解凍表現を決定すること、 （ｉｉｉ）符号化構文要素を保持すること、 の少なくとも一つによって、前記符号化構文要素を処理
    する手段と、 を含むことを特徴とする復号装置。
39. 【請求項３９】コンピュータに構文要素を含むマークア
    ップ言語文書を解析する手続を実行させるコンピュータ
    プログラムであって、 前記構文要素のタイプを識別するコードと、 前記タイプが第１タイプである場合に、前記構文要素
    を、そのハッシュ表現を決定することによって、処理す
    るコードと、 前記タイプが第１タイプである場合に前記ハッシュ表現
    を用いて、前記文書の少なくとも部分的構造表現を増大
    するコードと、 を含むことを特徴とするコンピュータプログラム。
40. 【請求項４０】コンピュータにＶＲＤに照らしてマーク
    アップ言語文書の妥当性を検査する手続を実行させるコ
    ンピュータプログラムであって、 （ａ）マークアップ言語文書を、そこで識別されるドキ
    ュメントタグごとに、該ドキュメントタグが、対応する
    マークアップ言語のドキュメントタグ階層における第１
    ドキュメントタグでなければ、処理するコードを有し、
    該コードは、 （ｉ）前記ドキュメントタグの階層位置を決定するコー
    ドと、 （ｉｉ）前記ドキュメントタグ階層における前のドキュ
    メントタグのハッシュ表現に連結された、前記ドキュメ
    ントタグの拡張ハッシュ表現を決定するコードと、 （ｉｉｉ）前記ドキュメントタグが前のドキュメントタ
    グよりも深くネストにされる場合に、前記ドキュメント
    タグの前記拡張ハッシュ表現を格納するコードと、を含
    み、 前記コンピュータプログラムは更に、 （ｂ）ＶＲＤを、そこで識別されるタグごとに、該タグ
    が対応タグ階層の第１タグでない場合に、処理するコー
    ドを有し、該コードは、 （ｉ）前記タグの階層位置を決定するコードと、 （ｉｉ）対応するタグ階層における前のタグのハッシュ
    表現に連結される前記タグの拡張ハッシュ表現を決定す
    るコードと、 （ｉｉｉ）前記タグの前記拡張ハッシュ表現をリストに
    格納するコードと、を含み、 前記コンピュータプログラムは更に、 （ｃ）前記ドキュメントタグの前記拡張ハッシュ表現
    が、前記リスト内にあるか、或は、前記リストのメンバ
    の妥当なサブセットである場合には、前記マークアップ
    言語文書の妥当性を検査するコードを含むことを特徴と
    するコンピュータプログラム。
41. 【請求項４１】コンピュータにＶＲＤに照らしてマーク
    アップ言語文書の妥当性を検査する手続を実行させるコ
    ンピュータプログラムであって、 （ａ）前記ＶＲＤを、そのなかで識別された構造要素ご
    とに、処理するコードを含み、該コードは、 （ｉ）前記構造要素の構文属性を決定するコードと、 （ｉｉ）前記構造要素のハッシュ表現を決定するコード
    と、 （ｉｉｉ）前記ＶＲＤの構造表現における、前記構造要
    素の前記ハッシュ表現及び構文属性を格納するコード
    と、を含み、 前記プログラムは更に、 （ｂ）マークアップ言語文書を、そのなかで識別された
    ドキュメント構造要素ごとに、処理するコードを含み、
    該コードは、 （ｉ）前記文書構造要素の構文属性を決定するコード
    と、 （ｉｉ）前記文書構造要素のハッシュ表現を決定するコ
    ードと、 （ｉｉｉ）前記文書の構造表現における、前記文書構造
    要素の前記ハッシュ表現と構文属性を格納するコード
    と、を含み、 前記プログラムは更に、 （ｃ）前記文書の前記構造表現における前記各文書構造
    要素の構文属性及びハッシュ表現が、前記ＶＲＤの前記
    構造表現における対応構文属性及びハッシュ表現に一致
    する場合に、前記マークアップ言語文書の妥当性を検査
    するコードを含むことを特徴とするコンピュータプログ
    ラム。
42. 【請求項４２】コンピュータに構文要素を含むマークア
    ップ言語文書を符号化する手続を実行させるコンピュー
    タプログラムであって、 構文要素のタイプを識別するコードと、 （ｉ）前記タイプが第１タイプであれば、前記構文要素
    のハッシュ表現を決定すること、 （ｉｉ）前記タイプが第１タイプでなければ、前記構文
    要素の圧縮表現を決定すること、 （ｉｉｉ）前記構文要素を保持すること、 のいずれかによって、前記構文要素を処理するコード
    と、 を含むことを特徴とするコンピュータプログラム。
43. 【請求項４３】コンピュータに符号化構文要素を含むマ
    ークアップ言語文書を復号する手続を実行させるコンピ
    ュータプログラムであって、 前記符号化構文要素のタイプを識別するコードと、 （ｉ）前記タイプが第１タイプであれば、前記符号化構
    文要素の逆ハッシュ表現を決定すること、 （ｉｉ）前記タイプが第１タイプでなければ、前記符号
    化構文要素の解凍表現を決定すること、 （ｉｉｉ）符号化構文要素を保持すること、 の少なくとも一つで、前記符号化構文要素を処理するコ
    ードと、 を含むことを特徴とするコンピュータプログラム。
44. 【請求項４４】コンピュータに構文要素を含むマークア
    ップ言語文書を解析する手続を実行させるコンピュータ
    プログラムを、格納したコンピュータ可読媒体を含むコ
    ンピュータプログラム製品であって、 前記コンピュータプログラムは、 前記構文要素のタイプを識別するコードと、 前記タイプが第１タイプである場合に、前記構文要素
    を、そのハッシュ表現を決定することによって、処理す
    るコードと、 前記タイプが第１タイプである場合に前記ハッシュ表現
    を用いて、前記文書の少なくとも部分的構造表現を増大
    するコードと、 を含むことを特徴とするコンピュータプログラム製品。
45. 【請求項４５】コンピュータにＶＲＤに照らしてマーク
    アップ言語文書の妥当性を検査する手続を実行させるコ
    ンピュータプログラムを、格納したコンピュータ可読媒
    体を含むコンピュータプログラム製品であって、 前記コンピュータプログラムは、 （ａ）マークアップ言語文書を、そこで識別されるドキ
    ュメントタグごとに、該ドキュメントタグが、対応する
    マークアップ言語のドキュメントタグ階層における第１
    ドキュメントタグでなければ、処理するコードを有し、
    該コードは、 （ｉ）前記ドキュメントタグの階層位置を決定するコー
    ドと、 （ｉｉ）前記ドキュメントタグ階層における前のドキュ
    メントタグのハッシュ表現に連結された、前記ドキュメ
    ントタグの拡張ハッシュ表現を決定するコードと、 （ｉｉｉ）前記ドキュメントタグが前のドキュメントタ
    グよりも深くネストにされる場合に、前記ドキュメント
    タグの前記拡張ハッシュ表現を格納するコードと、を含
    み、 前記コンピュータプログラムは更に、 （ｂ）ＶＲＤを、そこで識別されるタグごとに、該タグ
    が対応タグ階層の第１タグでない場合に、処理するコー
    ドを有し、該コードは、 （ｉ）前記タグの階層位置を決定するコードと、 （ｉｉ）対応するタグ階層における前のタグのハッシュ
    表現に連結される前記タグの拡張ハッシュ表現を決定す
    るコードと、 （ｉｉｉ）前記タグの前記拡張ハッシュ表現をリストに
    格納するコードと、を含み、 前記コンピュータプログラムは更に、 （ｃ）前記ドキュメントタグの前記拡張ハッシュ表現
    が、前記リスト内にあるか、或は、前記リストのメンバ
    の妥当なサブセットである場合に、前記マークアップ言
    語文書の妥当性を検査するコードを含むことを特徴とす
    るコンピュータプログラム製品。
46. 【請求項４６】コンピュータにＶＲＤに照らしてマーク
    アップ言語文書の妥当性を検査する手続を実行させるコ
    ンピュータプログラムを、格納したコンピュータ可読媒
    体を含むコンピュータプログラム製品であって、 前記プログラムは、 （ａ）前記ＶＲＤを、そのなかで識別された構造要素ご
    とに、処理するコードを含み、該コードは、 （ｉ）前記構造要素の構文属性を決定するコードと、 （ｉｉ）前記構造要素のハッシュ表現を決定するコード
    と、 （ｉｉｉ）前記ＶＲＤの構造表現における、前記構造要
    素の前記ハッシュ表現及び構文属性を格納するコード
    と、を含み、 前記プログラムは更に、 （ｂ）マークアップ言語文書を、そのなかで識別された
    ドキュメント構造要素ごとに、処理するコードを含み、
    該コードは、 （ｉ）前記文書構造要素の構文属性を決定するコード
    と、 （ｉｉ）前記文書構造要素のハッシュ表現を決定するコ
    ードと、 （ｉｉｉ）前記文書の構造表現における、前記文書構造
    要素の前記ハッシュ表現と構文属性を格納するコード
    と、を含み、 前記プログラムは更に、 （ｃ）前記文書の前記構造表現における前記各文書構造
    要素の構文属性及びハッシュ表現が、前記ＶＲＤの前記
    構造表現における対応構文属性及びハッシュ表現に一致
    する場合に、前記マークアップ言語文書の妥当性を検査
    するコードを含むことを特徴とするコンピュータプログ
    ラム製品。
47. 【請求項４７】構文要素を含むマークアップ言語文書の
    少なくとも部分的な構造表現であって、 前記構文要素の内の一要素に対し、 前記一要素のタイプを識別する識別ステップと、 前記タイプが第１タイプであれば、そのハッシュ表現を
    決定することによってその要素を処理する処理ステップ
    と、 前記タイプが前記第１タイプであれば、前記ハッシュ表
    現を用いて、前記文書の少なくとも部分的な構造表現を
    増大させる増大ステップと、 を行う解析方法によって生成されることを特徴とする構
    造表現。
48. 【請求項４８】構文要素を含むマークアップ言語文書を
    解析する解析装置であって、 プロセッサと、（ｉ）前記文書と、（ｉｉ）前記文書を
    解析する手続を前記プロセッサに実行させるプログラム
    を格納したプログラムと、格納するメモリを含み、 該プログラムは、 （ｉ）前記構文要素のタイプを識別するコードと、 （ｉｉ）前記タイプが第１タイプである場合に、前記構
    文要素を、そのハッシュ表現を決定することによって、
    処理するコードと、 （ｉｉｉ）前記タイプが第１タイプである場合に前記ハ
    ッシュ表現を用いて、前記文書の少なくとも部分的構造
    表現を増大するコードと、 を含むことを特徴とする解析装置。
49. 【請求項４９】構文要素を含むＶＲＤに照らして構文要
    素を含むマークアップ言語文書の妥当性を検査する検査
    装置であって、 （ａ）プロセッサと、 （ｂ）（ｉ）前記文書と、（ｉｉ）前記ＶＲＤと、（ｉ
    ｉｉ）文書の妥当性を検査する手順を前記プロセッサに
    実行させるプログラムと、を格納するメモリを有し、 （ｃ）前記プログラムは、 （ｃａ）マークアップ言語文書を、そこで識別されるド
    キュメントタグごとに、該ドキュメントタグが、対応す
    るマークアップ言語のドキュメントタグ階層における第
    １ドキュメントタグでなければ、処理するコードを有
    し、該コードは、 （ｃａａ）前記ドキュメントタグの階層位置を決定する
    コードと、 （ｃａｂ）前記ドキュメントタグ階層における前のドキ
    ュメントタグのハッシュ表現に連結された、前記ドキュ
    メントタグの拡張ハッシュ表現を決定するコードと、 （ｃａｃ）前記ドキュメントタグが前のドキュメントタ
    グよりも深くネストにされる場合に、前記ドキュメント
    タグの前記拡張ハッシュ表現を格納するコードと、を含
    み、 前記プログラムは更に、 （ｃｂ）ＶＲＤを、そこで識別されるタグごとに、該タ
    グが対応タグ階層の第１タグでない場合に、処理するコ
    ードを有し、該コードは、 （ｃｂａ）前記タグの階層位置を決定するコードと、 （ｃｂｂ）対応するタグ階層における前のタグのハッシ
    ュ表現に連結される前記タグの拡張ハッシュ表現を決定
    するコードと、 （ｃｂｃ）前記タグの前記拡張ハッシュ表現をリストに
    格納するコードと、を含み、 前記プログラムは更に、 （ｃｃ）前記ドキュメントタグの前記拡張ハッシュ表現
    が、前記リスト内にあるか、或は、前記リストのメンバ
    の妥当なサブセットであるかのいずれかであることを立
    証し、それにより前記マークアップ言語文書の妥当性を
    検査するコードを含むことを特徴とする検査装置。
50. 【請求項５０】構文要素を含むＶＲＤに照らして構文要
    素を含むマークアップ言語文書の妥当性を検査する検査
    装置であって、 （ａ）プロセッサと、 （ｂ）（ｉ）前記文書と、（ｉｉ）前記ＶＲＤと、（ｉ
    ｉｉ）文書の妥当性を検査する手順を前記プロセッサに
    実行させるプログラムと、を格納するためのメモリを有
    し、 （ｃ）前記プログラムは、 （ｃａ）前記ＶＲＤを、そのなかで識別された構造要素
    ごとに、処理するコードを含み、該コードは、 （ｃａａ）前記構造要素の構文属性を決定するコード
    と、 （ｃａｂ）前記構造要素のハッシュ表現を決定するコー
    ドと、 （ｃａｃ）前記ＶＲＤの構造表現における、前記構造要
    素の前記ハッシュ表現及び構文属性を格納するコード
    と、を含み、 前記プログラムは更に、 （ｃｂ）マークアップ言語文書を、そのなかで識別され
    たドキュメント構造要素ごとに、処理するコードを含
    み、該コードは、 （ｃｂａ）前記文書構造要素の構文属性を決定するコー
    ドと、 （ｃｂｂ）前記文書構造要素のハッシュ表現を決定する
    コードと、 （ｃｂｃ）前記文書の構造表現における、前記文書構造
    要素の前記ハッシュ表現と構文属性を格納するコード
    と、を含み、 前記プログラムは更に、 （ｃｃ）前記文書の前記構造表現における前記各文書構
    造要素の構文属性及びハッシュ表現を、前記ＶＲＤの前
    記構造表現における対応構文属性及びハッシュ表現と比
    較し、それにより前記マークアップ言語文書の妥当性を
    検査するコードを含むことを特徴とする検査装置。
51. 【請求項５１】ＶＲＤに照らしてマークアップ言語文書
    の妥当性検査を行う検査方法であって、 前記ＶＲＤにおける第１タイプの最も深くネストされた
    構文要素についての第１拡張ハッシュ表現を決定するス
    テップと、 ＶＲＤリストに前記第１拡張ハッシュ表現を格納するス
    テップと、 マークアップ言語文書における第１タイプの最も深くネ
    ストされた構文要素について、第２拡張ハッシュ表現を
    決定するステップと、 前記第２拡張ハッシュ表現が前記ＶＲＤリストに存在す
    る場合に、前記マークアップ言語文書は妥当でないこと
    を宣言するステップと、 を含むことを特徴とする検査方法。
52. 【請求項５２】前記第１タイプの前記構文要素は、 構造要素及びその一部、 前記構造要素の定義、 前記構造要素の宣言、 前記構造要素のマッチ、 のいずれかであることを特徴とする請求項５１に記載の
    検査方法。
53. 【請求項５３】前記構造要素はタグであることを特徴と
    する請求項５２に記載の検査方法。
54. 【請求項５４】前記ＶＲＤの前記最も深くネストされた
    構文要素は、前記ＶＲＤの広域的構造、或は前記ＶＲＤ
    の局所的サブ構造のいずれかの中に最も深くネストされ
    た構文要素であり、 前記マークアップ言語文書の最も深くネストされた構文
    要素は、前記マークアップ言語文書の広域的構造、或
    は、前記マークアップ言語文書の局所的サブ構造のいず
    れかの中に最も深くネストされた構文要素であることを
    特徴とする請求項５１に記載の検査方法。
55. 【請求項５５】ＶＲＤに照らしてマークアップ言語文書
    の妥当性を検査する検査装置であって、 前記ＶＲＤの第１タイプの最も深くネストされた構文要
    素について第１拡張ハッシュ表現を決定する手段と、 ＶＲＤリストの前記第１拡張ハッシュ表現を格納する手
    段と、 前記マークアップ言語文書における第１タイプの最も深
    くネストされた構文要素について、第２拡張ハッシュ表
    現を決定する手段と、 前記第２拡張ハッシュ表現が前記ＶＲＤリストに存在す
    る場合に、前記マークアップ言語文書は妥当でないと宣
    言する手段と、 を有することを特徴とする検査装置。
56. 【請求項５６】ＶＲＤに照らしてマークアップ言語文書
    の妥当性を検査する手続をコンピュータに実行させるコ
    ンピュータプログラムであって、 前記ＶＲＤの第１タイプの最も深くネストされた構文要
    素について第１拡張ハッシュ表現を決定するコードと、 ＶＲＤリストの前記第１拡張ハッシュ表現を格納するコ
    ードと、 前記マークアップ言語文書における第１タイプの最も深
    くネストされた構文要素について、第２拡張ハッシュ表
    現を決定するコードと、 前記第２拡張ハッシュ表現が前記ＶＲＤリストに存在す
    る場合に、前記マークアップ言語文書は妥当でないと宣
    言するコードと、 を含むことを特徴とするコンピュータプログラム。
57. 【請求項５７】ＶＲＤに照らしてマークアップ言語文書
    の妥当性を検査する手続をコンピュータに実行させるコ
    ンピュータプログラムを格納したコンピュータに含まれ
    るコンピュータプログラム製品であって、該プログラム
    は、 前記ＶＲＤの第１タイプの最も深くネストされた構文要
    素について第１拡張ハッシュ表現を決定するコードと、 ＶＲＤリストに前記第１拡張ハッシュ表現を格納するコ
    ードと、 前記マークアップ言語文書における前記第１タイプの最
    も深くネストされた構文要素について第２拡張ハッシュ
    表現を決定するコードと、 前記第２拡張ハッシュ表現が前記ＶＲＤリストに存在す
    る場合に、前記マークアップ言語文書が妥当でないと宣
    言するコードと、 を含むことを特徴とするコンピュータプログラム製品。
58. 【請求項５８】前記コードは、英数字を含むことを特徴
    とする請求項７に記載の解析方法。