(57)【要約】  本明細書では、高品位ディジタル・バーサタイル・ディスク（ＨＤ−ＤＶＤ）のタイミング・マークアップの実行を最適化するシステム、方法、および／または技法（「ツール」）について記載する。ツールは、ＨＤ−ＤＶＤディスクから読み取ったタイミング・マークアップを受け取り、本明細書に記載する最適化方策の１つ以上を用いて、タイミング・マークアップの処理を最適化することができる。【選択図】図１
2010516011.tif 000002
【特許請求の範囲】
【請求項１】
機械読み取り可能命令（１２２、１３０）を含む１つ以上の機械読み取り可能記憶媒体（１２０）であって、前記機械読み取り可能命令が機械（１１４）によって実行されると、
高品位ディジタル・バーサタイル・ディスク（ＨＤ−ＤＶＤ）（１０４）から読み取ったタイミング・マークアップ（１１２）を受け取るステップと、
前記タイミング・マークアップの処理を最適化するステップ（３０８、３１０、３１２、３１４、３１６、３１８）と、
を備えた方法を前記機械に実行させる、機械読み取り可能記憶媒体。
【請求項２】
請求項１記載の機械読み取り可能記憶媒体において、前記タイミング・マークアップの処理を最適化する前記命令は、前記タイミング・マークアップに含まれる少なくとも１つのXPATH表現を予め計算することによって、前記タイミング・マークアップの処理を最適化する命令を含む、機械読み取り可能記憶媒体。
【請求項３】
請求項２記載の機械読み取り可能記憶媒体において、前記タイミング・マークアップの処理を最適化する前記命令は、前記XPATH表現内において少なくとも１つの中間表現を識別する命令を含む、機械読み取り可能記憶媒体。
【請求項４】
請求項２記載の機械読み取り可能記憶媒体において、前記タイミング・マークアップの処理を最適化する前記命令は、前記XPATH表現内において識別した少なくとも１つの中間表現をキャッシュする命令を含む、機械読み取り可能記憶媒体。
【請求項５】
請求項２記載の機械読み取り可能記憶媒体において、前記タイミング・マークアップの処理を最適化する前記命令は、前記XPATH表現内において識別した少なくとも１つの中間表現を評価する命令を含む、機械読み取り可能記憶媒体。
【請求項６】
請求項２記載の機械読み取り可能記憶媒体において、前記タイミング・マークアップの処理を最適化する前記命令は、前記XPATH表現内において複数の中間表現を識別する命令と、前記中間表現を文書オブジェクト・モデルにおけるそれぞれのノードと関連付ける命令とを含む、機械読み取り可能記憶媒体。
【請求項７】
請求項１記載の機械読み取り可能記憶媒体において、前記タイミング・マークアップの処理を最適化する前記命令は、前記タイミング・マークアップにおける表現を識別することによって前記タイミング・マークアップの処理を最適化する命令と、前記表現の値が既定のイベントの発生に依存するか否か判定する命令とを含む、機械読み取り可能記憶媒体。
【請求項８】
請求項７記載の機械読み取り可能記憶媒体であって、更に、前記既定のイベントをイベント識別子と関連付ける命令を含み、前記イベントはユーザー入力と関連付けられる、機械読み取り可能記憶媒体。
【請求項９】
請求項８記載の機械読み取り可能記憶媒体であって、更に、前記イベント識別子を前記表現の少なくとも１つと関連付ける命令を含み、前記少なくとも１つの表現は、前記既定のイベントの少なくとも１つの発生に依存する、機械読み取り可能記憶媒体。
【請求項１０】
請求項１記載の機械読み取り可能記憶媒体であって、更に、タイミング・チックが発生したことの指示を受け取る命令を含む、機械読み取り可能記憶媒体。
【請求項１１】
請求項１０記載の機械読み取り可能記憶媒体であって、更に、前記チックの指示を受け取ったことに応答して、少なくとも１つのXPATH表現を受け取ることを含む、機械読み取り可能記憶媒体。
【請求項１２】
請求項１１記載の機械読み取り可能記憶媒体であって、更に、ユーザー入力が発生したことの指示を受け取り、該ユーザー入力を少なくとも１つの既定のイベントと関連付ける命令を含む、機械読み取り可能記憶媒体。
【請求項１３】
請求項１２記載の機械読み取り可能記憶媒体であって、更に、前記XPATH表現が前記既定のイベントの発生に依存するか否か判定する命令を含む、機械読み取り可能記憶媒体。
【請求項１４】
請求項１３記載の機械読み取り可能記憶媒体であって、更に、前記XPATH表現が前記既定のイベントの発生に依存している場合、前記XPATH表現を再評価する命令を含む、機械読み取り可能記憶媒体。
【請求項１５】
請求項１３記載の機械読み取り可能記憶媒体であって、更に、前記XPATH表現の以前の値が前記既定のイベントの発生に独立している場合、前記XPATH表現の以前の値を取り出す命令を含む、機械読み取り可能記憶媒体。
【請求項１６】
請求項１記載の機械読み取り可能記憶媒体において、前記タイミング・マークアップの処理を最適化する前記命令は、有限状態機械を用いて前記処理を最適化する命令を含む、機械読み取り可能記憶媒体。
【請求項１７】
請求項１記載の機械読み取り可能記憶媒体において、前記タイミング・マークアップの処理を最適化する前記命令は、前記タイミング・マークアップ内において発生する複数の表現を識別することによって前記処理を最適化し、前記表現の内少なくとも２つが互いに相補的であることを認識する命令を含む、機械読み取り可能記憶媒体。
【請求項１８】
請求項１記載の機械読み取り可能記憶媒体において、前記タイミング・マークアップの処理を最適化する前記命令は、共有メモリー・プールを用いることによって、前記処理を最適化する命令を含む、機械読み取り可能記憶媒体。
【請求項１９】
請求項１記載の機械読み取り可能記憶媒体において、前記タイミング・マークアップの処理を最適化する前記命令は、スケジューラーを用いることによって、前記処理を最適化する命令を含む、機械読み取り可能記憶媒体。
【請求項２０】
請求項１記載の機械読み取り可能記憶媒体を含むＨＤ−ＤＶＤプレーヤー・デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
高品位ディジタル・バーサタイル・ディスク（ＨＤ−ＤＶＤ）媒体および関係するプレーヤーは、増々普及し広く用いられつつある。この市場に算入する製造業者が増加するに連れて、競争が激化し、ドライブ価格を下落させる結果に繋がる。この価格環境において、ＨＤ−ＤＶＤプレーヤー内部で走るソフトウェアは、比較的安価な消費者向けハードウェア上で走るのが通例である。
【発明の概要】
【発明が解決しようとする課題】
【０００２】
ＨＤ−ＤＶＤコンテンツおよびスタイル・マークアップ(style markup)を表示のために有形形態(tangible form)に変換するのは、計算処理上コスト高となる。通例、ＨＤ−ＤＶＤマークアップのレンダリング・レートに対する正当な目標は、容認可能なユーザー体験(experience)に合わせると、毎秒約２４フレームである。ＨＤ−ＤＶＤマークアップを変換しレンダリングする従来の技法では、このレンダリング・レートの目標に到達しようとすると、低コストの消費者向けハードウェア上で計算処理上コスト高のタスクを実行することにより、困難に直面することもある。
【課題を解決するための手段】
【０００３】
本明細書では、高品位ディジタル・バーサタイル・ディスク（ＨＤ−ＤＶＤ）タイミング・マークアップの実行を最適化するシステム、方法、および／または技法（「ツール」）について記載する。ツールは、ＨＤ−ＤＶＤディスクから読み出すタイミング・マークアップを受け取り、本明細書において記載する最適化方策(strategy)の１つ以上を用いて、タイミング・マークアップの処理を最適化することができる。
【０００４】
この摘要は、詳細な説明において以下で更に説明する概念から選択したものを、簡略化した形態で導入するために設けられている。この摘要は、特許請求する主題の鍵となる特徴や必須の特徴を特定することを意図するのではなく、特許請求する主題の範囲を判断するために用いられることを意図するのでもない。例えば、「ツール」という用語は、前述の文脈で許容されるのであれば本文書全体を通じて、システム、方法、コンピューター読み取り可能命令、および／または技法を意味することもできる。
【図面の簡単な説明】
【０００５】
ＨＤ−ＤＶＤタイミング・マークアップの実行の最適化に関するツールについて、以下の図面と関連付けて説明する。本開示および図全体を通じて、同様の構成要素および機構を引用する際には、同じ番号を用いることとする。参照番号の内最初の桁は、その参照番号が導入される図面を示す。
【０００６】
【図１】図１は、ＨＤ−ＤＶＤタイミング・マークアップの実行を最適化する動作環境のブロック図である。
【図２】図２は、プレゼンテーション・エンジンおよびタイミング・マークアップのその他の形態のブロック図である。
【図３】図３は、タイミング・マークアップの処理を最適化するＸＰＡＴＨ表現マネージャーおよび方策の形態のブロック図である。
【図４】図４は、タイミング・マークアップを処理するためのデーターおよびプロセス・フローのブロック図である。
【図５】図５は、図４に示すデーターおよびプロセス・フローの別の形態のブロック図である。
【図６】図６は、ある種のXPATH表現を予め解析し予め計算することを含む最適化方策に関するコンポーネントおよびプロセス・フローのブロック図である。
【図７】図７は、イベント・ドリブン表現の最適化に関するコンポーネントおよびフローのブロック図である。
【図８】図８は、イベント依存表現の処理を最適化するプロセス・フローのブロック図である。
【図９】図９は、有限状態機械を用いた最適化技法のブロック図である。
【図１０】図１０は、共有メモリー・プールを用いたタイミング・マークアップの処理最適化に関するコンポーネントおよびフローのブロック図である。
【図１１】図１１は、タイミング・ツリー横断を減少するためのスケジューラーの使用に関する最適化技法のブロック図である。
【発明を実施するための形態】
【０００７】
全体像
以下の文書は、多くの技法およびプロセスの実行および／または支援が可能なツールについて説明する。以下の論述は、これらのツールがＨＤ−ＤＶＤタイミング・マークアップの実行を最適化することができる方法の例について説明する。また、この論述は、ツールが実行することができるその他の技法および／またはプロセスについても説明する。
【０００８】
図１は、ＨＤ−ＤＶＤタイミング・マークアップの実行を最適化する動作環境１００を示す。動作環境１００は、一人以上のユーザー１０２が１つ以上のＨＤ−ＤＶＤディスク１０４を再生することを可能にするとよい。これらのＨＤ−ＤＶＤディスク１０４は、１つ以上の機械読み取り可能ソフトウェア・コンポーネントを含むことができる。これらのコンポーネントは、例えば、１つ以上のマークアップ・ファイル１０６を含むことができる。マークアップ・ファイル１０６は、宣言型ＸＭＬベース言語(declarative XML-based language)として実現することができ、異なるボキャブラリ即ちマークアップ・コンテンツを含むことができる。
【０００９】
マークアップ・ファイルの例は、少なくともコンテンツ・マークアップ１０８、スタイル・マークアップ１１０、およびタイミング・マークアップ１１２を収容することができる。コンテンツ・マークアップ１０８は、所与のマークアップ文書の主要<body>セクションに収容され、そのマークアップの中で定義されるオブジェクトまたはエレメントのレイアウト構造全体を記述する。以下に示す表１は、ＨＤ−ＤＶＤコンテンツ・マークアップのエレメントのツリーを示す。
【表１】
2010516011.tif 000003
【００１０】
スタイル・マークアップ１１０は、オブジェクトまたはエレメントをどのようにフォーマットすることができるかを記述するボキャブラリである。スタイル・マークアップ部分１１０は、コンテンツ・マークアップ部分１０８に含まれるエレメントをユーザーに呈示するときに、どのように出現するのかを記述するＸＭＬボキャブラリを含むことができる。言い方を変えると、コンテンツ・マークアップ部分は、どのエレメントをユーザーにレンダリングするか指定することができ、スタイル・マークアップ部分は、これらのエレメントをどのようにしてユーザーにレンダリングするかを指定することができる。
【００１１】
タイミング・マークアップ１１２は、経時的にそしてユーザーとの対話を通じてコンテンツをどのように修正することができるかを記述するボキャブラリである。ＨＤ−ＤＶＤタイミング・マークアップとは、本明細書において記載する場合、業界標準のＳＭＩＬ言語の部分集合であるが、ＳＭＩＬ言語をマークアップ文書の<body>セクションの外側に含むことを可能にする拡張を追加する。例えば、ここに記載するタイミング・マークアップは、「キュー」と呼ばれる特殊タイミング・コンテナを追加する。これは、ＳＭＩＬでは定義されておらず、アニメーション・プロパティを摘要するマークアップ文書におけるエレメントを定義する。
【００１２】
コンテンツ・マークアップ部分、スタイル・マークアップ部分、およびタイミング・マークアップ部分は、宣言型プログラミング言語で実現することができる。しかしながら、スクリプト部分１１３は、経時的にスタイル・マークアップに非決定論的変化を生ずる命令型プログラミング・ボキャブラリで実現することもできる。
【００１３】
全体的に捕らえて、コンテンツ・マークアップ１０８、スタイル・マークアップ１１０、およびタイミング・マークアップ１１２は文書オブジェクト・モデル（ＤＯＭ:document object model）１１５を定義する。ＤＯＭ１１５は、ＸＭＬボキャブラリを用いたツリー・データー構造として実現することができる。ＤＯＭは、複数の個別マークアップ・エレメントを含むことができ、図２ではこれらを全体的に１１７で示す。前述の表１は、適法の親−子エレメントの組み合わせの集合を図示し、ＤＯＭ状態１１５の具体的な例を提示する。
【００１４】
図１は、マークアップ・エレメントの内２つの例を１１７ａおよび１１７ｎで示す。しかしながら、ＤＯＭの実現例は任意の数のエレメント２０４を含むことができ、ＤＯＭツリーは適して形態であればいずれを取ることもできる。スクリプト１１３は、ＤＯＭを非決定論的に変化させる命令型プログラミング言語であってもよい。
【００１５】
ＨＤ−ＤＶＤは、対話レイヤ(interactivity layer)を含む。これは、とりわけ、ＨＤ−ＤＶＤ高度アプリケーションがユーザーおよびオーディオ／ビデオ再生システムと対話することができる方法を定める。このような対話レイヤの一例が、ＨＤｉ（商標）の商品名でMicrosoft Corporation（マイクロソフト社）から入手可能である。ＨＤｉ（商標）対話層は、高度アプリケーション・コンテンツとして定められたデーター・フォーマットの集合体としてエンコードされている。これらのフォーマットは、コンテンツの宣言型記述を規定し、ＸＭＬから導き出すことができる。
【００１６】
動作環境１００は、破線１１６で表すように、ユーザー１０２が再生のためにＨＤ−ＤＶＤディスク１０４をＨＤ−ＤＶＤプレーヤー１１４に挿入させることができる。ＨＤ−ＤＶＤプレーヤー１１４は、１１８で示す１つ以上のプロセッサーを含む、コンピューターベースのシステムとするとよい。これらのプロセッサー１１８は、所与の形式またはアーキテクチャを有するもの毎に分類するまたは特徴付けることもできるが、同一の形式またはアーキテクチャを有しても有さなくてもよい。可能な実現例では、プロセッサーは１つ以上の対話型コマンド・プロセッサー（ＩＣＰ）を含むことができる。
【００１７】
また、ＨＤ−ＤＶＤプレーヤーは、機械読み取り可能記憶媒体またはコンピューター読み取り可能記憶媒体の１つ以上のインスタンスも含むことができる。これを全体的に１２０で示す。コンピューター読み取り可能媒体１２０は、命令を収容することができ、プロセッサー１１８によっての命令を実行すると、本明細書において記載するツールまたは関係する機能のいずれもが、ＨＤ−ＤＶＤプレーヤー内部のいずれかのコンポーネントによって実行するように、実行する。プロセッサーは、コンピューター読み取り可能媒体上に埋め込まれたまたはエンコードされた命令にアクセスすることおよび／または実行することができ、および／またはコンピューター読み取り可能媒体に格納されているデーターにアクセスすることもできる。
【００１８】
コンピューター読み取り可能媒体１２０についての更なる詳細に移ると、これはＨＤ−ＤＶＤプレゼンテーション・エンジン１２の１つ以上のインスタンスを含むことができる。ＨＤ−ＤＶＤプレゼンテーション・エンジン１２２は、例えば、１つ以上のソフトウェア・モジュールを含むことができ、これらをプロセッサーにロードして実行すると、ＨＤ−ＤＶＤプレーヤーに、タイミング・マークアップ１０６を含むマークアップおよびその他のエレメントをＨＤ−ＤＶＤディスク１０４からロードさせる。プレゼンテーション・エンジン１２２は、ＨＤ−ＤＶＤディスクから読み取ったマークアップをフォーマットし、ユーザーに表示するのに適した描出コンテンツにマップすることができる。図１は、この描出コンテンツを全体的に１２４で示す。
【００１９】
図１に示すように、ＨＤ−ＤＶＤプレーヤー１１４はユーザー・インターフェース１２６を備えており、これを通じて、ユーザー１０２はＨＤ−ＤＶＤプレーヤーと対話することができる。ユーザー・インターフェース１２６は、ＨＤ−ＤＶＤプレーヤーによって備えられるハードウェアを含むことができ、あるいはＨＤ−ＤＶＤを接続または結合する他のデバイス、例えば、テレビジョン受像機または表示画面によって設けられるハードウェアを含むことができる。一般に、ユーザー・インターフェース１２６は、ユーザーがＨＤ−ＤＶＤプレーヤーと対話することを可能にするのに適したハードウェアおよび／またはソフトウェア・コンポーネントであればいずれでも表すことができる。図１は、概略的に、ユーザー１０２とＨＤ−ＤＶＤプレーヤー１０８との間の対話を１２８で表している。
【００２０】
描出コンテンツ１２４は、プレゼンテーション・エンジン１２２が生成するメニュー、プロンプト、またはユーザーからの応答または入力を引き出すその他の項目を含むことができる。この応答または入力は、例えば、口頭即ち発話コマンド、デバイス（例えば、ユーザー・インターフェース１２６および／またはＨＤ−ＤＶＤプレーヤー１１４と関連のあるリモコン）を通じて入力したコマンド、ＨＤ−ＤＶＤプレーヤーに設けられているボタンを通じて入力されたコマンド、または適した形態であればその他のいずれでも含むことができる。
【００２１】
コンピューター読み取り可能媒体１２０に戻り、タイミング・マークアップ１１２の処理を最適化するために、プレゼンテーション・エンジン１２２と協同するタイミング最適化エンジン１３０を含むことができる。本明細書全体を通じて述べるように、タイミング最適化エンジン１３０は、プレゼンテーション・エンジン１２２がＨＤ−ＤＶＤからのコンテンツをユーザーに、容認可能なユーザー体験を提供するのに十分なフレーム・レートでレンダリングすることを可能にする１つ以上の方策を採用することができる。
【００２２】
図１を用いて動作環境１００について説明したので、これよりプレゼンテーション・エンジン１２２およびタイミング・マークアップ１１２の更に詳細な説明に論述を移すこととし、図２を用いて提案する。
【００２３】
図２は、プレゼンテーション・エンジン１２２およびタイミング・マークアップ１１２の別の形態２００を示す。便宜上、以前に説明したエレメントの一部を図２にも引き継ぎ、同じ参照番号で示すこととするが、これは限定ではない。
【００２４】
プレゼンテーション・エンジン１２２は、総合的に２０２で示す、フレーム・レンダリング・レートで動作することができる。このフレーム・レート２０２は、ＨＤ−ＤＶＤ１０４の著作者によって設定することができる。更に具体的には、著作者は目標のフレーム・レートをマークアップの中で指定することができる。例えば、著作者は「プレーリスト」と呼ばれるファイルの中で所望のフレーム・レートを宣言することができる。別の例では、著作者はタイミングセクション毎にクロック分周器を宣言することができる。しかしながら、ＨＤ−ＤＶＤ仕様は、タイミング・マークアップを処理したときにこれらの目標フレーム・レートを達成することは保証していない。著作者は、セクション当たり６０フレームの目標フレーム・レートを宣言することができるが、システムが走っているハードウェア・プラットフォームと結合するＨＤ−ＤＶＤソフトウェアの実現例の詳細によって、目標フレーム・レートを達成できるか否かが決まる。したがって、本明細書において記載する、タイミング・マークアップ処理の最適化は、目標フレーム・レートを達成する公算を高めることができる。
【００２５】
プレゼンテーション・エンジン１１６は、全体的に２０４で示す、タイミング・クロック・パルス即ちチックを受け取る。チックは、ＨＤ−ＤＶＤから読み取ったマークアップの処理、フォーマット、およびレンダリングを規制または同期する。ＨＤ−ＤＶＤプレーヤー１０８は、ＨＤ−ＤＶＤタイミング・モデルに準拠するようにチックを発生するのであれば、適した技術のいずれを用いてチック２０４を発生してもよい。
【００２６】
ＨＤ−ＤＶＤディスク１０４から読み取ったタイミング・マークアップ１０６の更なる詳細に移ると、このマークアップはタイミング・コンテナ２０６の１つ以上のインスタンスを定義することができる。図２は、２０６ａおよび２０６ｎで示す、タイミング・コンテナの例を２つ提示する。しかしながら、タイミング・マークアップ１０６のインスタンスは、任意の数のタイミング・コンテナ２０６を定義できることを注記しておく。
【００２７】
タイミング・コンテナ２０６は、異なる形式または形態をなすことができる。図２に示す例では、タイミング・コンテナは順次タイミング・コンテナ２０８、省略すると<seqs>を含むことができる。タイミング・コンテナは、並列タイミング・コンテナ２１０、省略すると<pars>を含むことができる。タイミング・コンテナは、キュー・タイミング・コンテナ２１２、省略すると<cues>を含むことができる。
【００２８】
<Par>および<Seq>タイム・コンテナは、子タイミング・コンテナの１つ以上のインスタンスを収容することができる（即ち、<seqs>２０８ａ、<pars>２１０ａ、および<cues>２１２ａ）。<Par>および<Seq>タイミング・コンテナは、これらの子をそれぞれいつそしてどのように評価するのか制御する。<par>タイミング・コンテナの子は並列に処理され、一方<seq>タイミング・コンテナの子は順次処理される。<Cues>は他のタイム・コンテナを収容しないが、マークアップ・コンテンツに関係がある１つ以上のプロパティ２１４を収容することができ、あるいはリスナー(listener)２１８に通知することができる０個以上のイベント２１６を収容することができる。リスナー２１８は、ＨＤ−ＤＶＤアプリケーションの著作者によって書かれたJavaScriptコードとして実現することができる。
【００２９】
<Cue>タイミング・コンテナ２１２ａは、特定のイベント２１６を収容することができる。更に具体的には、タイミング・コンテナは、当該タイミング・コンテナがいつアクティブおよびインアクティブになるか、そしてどの特定のノードに個々のアニメーション・アクションを摘要するのか定める１つ以上の属性を収容することができる。アニメーション・アクションの例には、<animate>、<set>、および<event>が含まれる。図２は、開始時刻属性２２０、終了時刻属性２２２、および持続期間属性２２４として示す、タイミング関係属性の３つの例を示す。
【００３０】
これらの属性の更なる詳細に移ると、開始時刻属性２２０は、いつ特定の時間間隔が開始するのかを指定することができ、終了時刻属性２２２は、いつ特定の時間間隔が終了するのかを指定することができる。持続時間属性２２４は、開始時刻属性２２０および終了時刻属性２２２から導き出すことができ、あるいは属性２２０および２２２の代用として、別個に指定することもできる。
【００３１】
以上の論述から、タイミング・コンテナは<par>、<seq>、または<cue>であればよいことが思い出されるであろう。タイミング・コンテナは、コンテナがいつインアクティブまたはインアクティブになるか（例えば、開始、終了、最中）を定める属性を含む。また、<cue>は「選択」属性を含むことができ、この選択属性はアニメーション・アクションを適用する、ＤＯＭにおけるノードを定める。「開始」、「終了」、および「選択」の属性は、時間表現を用いることができる。時間表現は、明確な時間間隔、またはXPATH表現（例えば、"id('myButton')[state:focused()=true()]"）を含むことができる。
【００３２】
持続期間属性の更なる詳細に移ると、タイミング・コンテナは、一部のインスタンスでは、特定の時間オフセットに関する持続期間属性を指定することができる。これらのインスタンスでは、このような特定の時間オフセットによって定められる間隔は、図２の２２６において表されるように、「明確な」間隔と見なすことができる。明確な間隔の例には、１０秒、２０ミリ秒等というような、指定の持続期間を含むこともできる。
【００３３】
ＤＯＭに対するユーザーの対話およびその他の変更は、時間間隔の持続期間に影響を及ぼすことがある。例えば、いずれのタイミング・コンテナの「終了」属性もXPATH表現として定義することができる。XPATH表現は、ユーザー入力のため、または著作者によって行われたスクリプトの変更（例えば、１１３）のために変化する１つ以上のプロパティに対する特定の変化を生じさせるために、ＤＯＭに問い合わせることができる。一方、これらの変化はタイム・コンテナの持続期間に影響を及ぼすことがある。これらのインスタンスでは、このような特定の時間オフセットによって定められる間隔は、図２の２２８において表されるように、「不明確な」間隔と見なすことができる。実現例によっては、タイミング・コンテナがこれらの不明確な間隔をＸＭＬパス表現またはXPATH表現で指定することができる。図２は、２３０ａおよび２３０ｎで示す（全体では２３０）、XPATH表現の例を２つ提示する。しかしながら、タイミング・コンテナの実現例は、適した数のXPATH表現２３０であればいくつでも含むことができる。
【００３４】
以下に、タイミング・マークアップの一例を示す。
【表２】
2010516011.tif 000004
【００３５】
以上の例は、単一ｐａｒタイム・コンテナ(single par time container)（例えば、２１０）を定義し、その持続期間は２秒の明確な間隔であり、その関係コンテンツ・ノードセット(related nodeset)は、識別子id='mybutton'を有するエレメントである。このｐａｒタイム・コンテナは、１つのｓｅｑタイム・コンテナ（例えば、２０８）を収容し、ｓｅｑタイム・コンテナはその親ｐａｒコンテナから２秒の持続期間を引き継ぐ。
【００３６】
ｐａｒタイム・コンテナは、２つのｃｕｅタイミング・コンテナを収容する。第１のｃｕｅタイム・コンテナは、１秒間実行し、マークアップ・エレメント'mybutton'の背景色を赤に設定する。第１のｃｕｅによって設定された背景色は、プレゼンテーション値を保持することができるプロパティの一例である（例えば、２１４）。また、第１のｃｕｅがアクティブになったとき、第１のｃｕｅは"myevent"と命名したイベント（例えば、２１６）を発火する。
【００３７】
第２のｃｕｅは、第１のｃｕｅが完了した後に活性化される。何故なら、第１および第２のｃｕｅの親コンテナがｓｅｑであるからである。第２のｃｕｅは１秒間実行する。第２のｃｕｅがアクティブである間、マークアップ・エレメント'mybutton'のｘ位置を０画素から１００画素動かし、更にマークアップ・エレメント'mybutton'の背景色を青に変化させる。これらのｃｕｅがインアクティブになると、背景色の元のプロパティ値が復元する。
【００３８】
タイミング・コンテナの実現例によっては、１つのXPATH表現を別のXPATH表現の中にネストすることもできる。別の実現例では、XPATH表現によって定められる２つ以上の間隔を親−子関係に構成することもできる。このような場合では、タイミング間隔を「保持」することもできる。これが意味するのは、子間隔が、親またはその他の先祖間隔の持続期間だけ、計算したプロパティ値のその最後の集合を保持するということである。
【００３９】
以上図２を用いてプレゼンテーション・エンジンおよびタイミング・マークアップについて説明したので、これより論述はXPATH表現マネージャーおよびタイミング・マークアップの処理を最適化する方策の説明に移る。ここでは、図３を用いて提案する。
【００４０】
図３は、XPATH表現マネージャー、およびタイミング・マークアップの処理を最適化する方策の形態３００を示す。便宜上、以前に説明したエレメントの一部を図３にも引き継ぎ、同じ参照番号で示すこととするが、これは限定ではない。
【００４１】
プレゼンテーション・エンジン１２２が、チック２０４に応答して、ＨＤ−ＤＶＤ１０４から読み出したエレメントを処理していくと、タイミング・マークアップ１１２において１つ以上のXPATH表現２１８ａに遭遇する場合がある。プレゼンテーション・エンジンがマークアップにおいてXPATH表現を突き止めると、プレゼンテーション・エンジンはこれらのXPATH表現を、XPATH表現マネージャー・コンポーネント３０２に、処理および評価のために転送することができる。図３は、XPATH表現マネージャーに転送されたXPATH表現を、２１８ｂで示す。
【００４２】
加えて、XPATH表現マネージャーは、タイミング・マークアップ１２を処理していくに連れて生ずるデーター表現スタイルおよび状態の変化も受けることができる。図３は、これらのスタイルおよび状態変化を３０３で示す。ある時間間隔がアクティブになると、この間隔がアクティブの間に適用する１つ以上のアニメーション・アクション、およびこれらのアニメーション・アクションを適用する特定の目標ノード・セットのリストを収容する。アニメーション・アクションは、例えば、<set>、<animate>、<event> 、および<link>を含む。以下の例は、説明を容易にするために紹介するのであり、可能な実現例を限定するためではない。
【表３】
2010516011.tif 000005
【００４３】
上の例は、マークアップ・ファイルの一例のタイミング・セクションおよび本体セクション双方を示す。タイミング・セクションは２つのタイミング・コンテナ、即ち、<par>および<cue>を含む。<par>は未定義であるが<cue>を収容し、「選択」属性によって関連付けられるノード−セットを動かす。「選択」属性は、一定のXPATH表現＝id('div2')として定義されており、id=div2であるエレメントを意味する。この<cue>の「開始」属性は、不明確なXPATH表現として定義されており、id='animate1'であるエレメントの活動化状態(actioned state)が真になったときに<cue>がアクティブになることを意味する。一旦この条件が満たされると、時間間隔（この場合、<cue>）がアクティブになり、時間間隔が、それが収容するアニメーション・アクションに適用される。この例では、アニメーション・アクションは以下を含む。
１）<animate>：間隔の持続期間中、ある範囲の値においてstyle:x positionを目標ノード−セット（この場合、'div2')に内挿補間する。
２）<set>：値'blue'を、目標ノード−セット'div2'に対するstyle:backgroundColorプロパティに適用する。
３）<event>：間隔がアクティブにある時点でのみ、名称が'myEvent'であるイベントを目標ノード−セット'div2'に発火する(fire)。著作者によってスクリプトの中に定義されているリスナー関数（例えば、２１８）が、この通知を受けることができ、この通知を受けたときに、スクリプトにおけるいずれの数の動作でもコールすることができる。
【００４４】
XPATH表現マネージャー・コンポーネントは、XPATH表現を評価する命令を収容した１つ以上のソフトウェア・モジュールを含むことができる。加えて、XPATH表現マネージャー３０２は、XPATH表現２１８を最適化エンジン１３０に転送して、XPATH表現２１８の処理を最適化できるか否か判断することができる。図３は、２１８ｃにおいて、最適化エンジンに転送されたXPATH表現を示す。
【００４５】
場合によっては、最適化エンジンは、本明細書において記載する方策の１つ以上を用いて、XPATH表現の処理を最適化することができることもある。これらの場合、最適化エンジンは、XPATH表現の最適化評価から得られる結果３０４を返すことができる。図３が示す例では、最適化エンジンは結果３０４をXPATH表現マネージャー３０２に、またはこれを通じて戻している。
【００４６】
場合によっては、XPATH表現２１８は、本明細書に記載する方策のいずれを用いても、処理の最適化に向いていないこともあり得る。これらの場合、XPATH表現マネージャー３０２自体がこれらのXPATH表現を評価し、値３０６をプレゼンテーション・エンジンに返すことができる。値３０６は、最適でない評価の結果を表す。
【００４７】
最適化エンジン１２４は、タイミング・マークアップ１０６の処理を最適化する１つ以上の方策を実現するソフトウェア・モジュールを含むことができる。図３は、これらの方策をブロック形態で示し、以後の図面においてこれらの方策について詳細に示す。
【００４８】
ブロック３０８において表すように、１つの方策は、ＨＤ−ＤＶＤから読み取ったマークアップの中に定義されているXPATH表現の少なくとも一部を予め解析し、予め計算することを含むことができる。ブロック３１０で表す方策は、合焦状態(focus state)に依存する表現について処理を最適化することを含むことができる。ブロック３１２で表す方策は、有限状態機械を用いることによって、処理を最適化することを含むことができる。ブロック３１４で表す方策は、相補表現を認識し評価することによって、タイミング・コンテナの処理を最適化することを含むことができる。ブロック３１６で表す方策は、タイミング関係データー構造を格納するために共有メモリー・プールを用いることによって、タイミング・コンテナの処理を最適化することを含むことができる。ブロック３１８で表す方策は、スケジューラーを用いることによって処理を最適化することを含むことができる。
【００４９】
以下ではこれら種々の方策３０８〜３１８について更に詳細に説明するが、本明細書における記載の実現例は、これらの方策の内１つ、いくつか、または全てを適宜含んでもよいことを注記しておく。また、これらの方策は、別個のソフトウェア・モジュールで実現してもよく、あるいは１つ以上の共通モジュールに一体化してもよい。したがって、図３はこれらの方策を説明および参照を容易にするためにのみ別個のブロックで示すが、これら可能な実現例を限定するためではないことを注記しておく。
【００５０】
最適化エンジン１３０は、XPATH評価エンジン３２０と協同して、最適化方策３０８〜３１８のいずれかを用いて、最適化されていないいずれのXPATH表現でも再評価することができる。XPATH評価エンジン３２０は、W3C XPATH 2.0の派生であるＨＤ−ＤＶＤ  XPATHシンタックスに準拠することができる。XPATH表現マネージャー３０２は、直接XPATH評価エンジン３２０をコールして、所与のXPATH表現を再評価することができる。図３における破線２１８ｄは、このコールを表し、XPATH表現はXPATH評価エンジン３２０への入力として供給される。一方、XPATH評価エンジン３２０は評価結果３２２を生成し、これらの結果を最適化エンジンに供給する。
【００５１】
XPATH表現マネージャーおよびタイミング・マークアップの処理を最適化する様々な方策について、図３を用いて説明したので、これよりタイミング・マークアップを処理するためのデーターおよびプロセスの説明に移る。ここでは、図４を用いて提案する。
【００５２】
図４は、タイミング・マークアップを処理するためのデーターおよびプロセス・フロー４００を示す。便宜上、以前に説明したエレメントの一部を図４にも引き継ぎ、同じ参照番号で示すこととするが、これは限定ではない。加えて、図４はデーターおよびプロセス・フロー４００の一部の形態を、ある種のコンポーネントによって実行するように示すが、これは説明を容易にするためであり、限定ではない。
【００５３】
ブロック４０２は、クロック・パルス即ちチック（例えば、２０４）の受信に応答してクロック・タプル(clock tuple)を発生することを表す。クロック・タプルは、タイトル・クロック、ページ・クロック、およびアプリケーション・クロック値を収容することができる。チックが発生すると、ブロック４０２は対応するクロック・タプルを発生する。これらのクロック・タプルは、同じクロック基準と同期が取られている。図４に示すように、プロセッサー（例えば、ＩＣＰ１１２）がブロック４０２を実行することができる。実現例によっては、プロセッサー・ボード上にある発振器または同様のタイミング・エレメントがブロック４０２を実行してもよい。他の実施形態では、発振器またはタイミング・エレメントはプロセッサーの外部であってもよい。
【００５４】
ブロック４０４は、クロック・パルスに応答してオンチック・メッセージを作成して送ることを含むことを表す。このオンチック・メッセージは、図４に示すプロセス・エレメントの残りの部分に対する通知メカニズムを備え、クロック・パルスが発生したことを示す。
【００５５】
ブロック４０６は、ブロック４０２において作成したクロック・タプルを、例えば、プレゼンテーション・エンジン（例えば、１１６）に送ることを表す。図４は、クロック・タプルをプレゼンテーション・エンジンに４０８において送るように示している。クロック・タプル４０８は、４１０で示す、オンチック・メッセージを含むことができる。オンチック・メッセージ４１０は、例えば、現ページ・クロック値４１２、タイトル・クロック値４１４、およびアプリケーション・クロック値４１６の内１つ以上を含むことができる。
【００５６】
プレゼンテーション・エンジンにおいて、ブロック４１８はクロック・タプル４０８を受け取ることを表す。ブロック４２０は、入力クロック・タプルにおいて表されるチックについて時間解明(time resolution)を実行する。ブロック４２０を実行する際、プレゼンテーション・エンジンは、文書オブジェクト・モデル（ＤＯＭ）４２２のようなデーター構造に照会する。ＤＯＭ４２２は、例えば、ＨＤ−ＤＶＤ（例えば、１０４）上にエンコードされここから読み取り可能な、コンテンツ・マークアップ、スタイル・マークアップ、スクリプト、およびタイミング・マークアップ１０６を収容することができる。ＤＯＭは、ＸＭＬボキャブラリを用いたツリー・データー構造として実現することができる。
【００５７】
ＤＯＭ４２２は、チック２０４が発生すると関連が生ずる１つ以上のXPATH表現（例えば、２１８）を処理のために格納することができる。ＤＯＭは、これらの ＸＰＡＴＨ表現２１８を、プレゼンテーション・エンジンからの照会に応答して供給することができる。これは、図４においてブロック４２２および４２０を結ぶ破線によって示されている。
【００５８】
ブロック４２４は、クロック・タプルに応答して、アクティブ・アニメーション・リストを更新することを表す。更に具体的には、ブロック４２４は、新たなクロック・タプルに合わせてアクティブ間隔リストを更新することを含むことができる。総合的な処理オーバーヘッドを低減するために、以前の結果をキャッシュしておくとよく、新たなクロック・タプルによって生ずる変化のみを、アクティブ間隔リストにおいて反映させる。タイミング間隔がアクティブになると、これらをアクティブ間隔リストに追加する。逆に、タイミング間隔がインアクティブになると、これらをアクティブ間隔リストから取り除く。
【００５９】
アクティブ間隔リストは、どの間隔がアクティブであるかを示す。言い方を変えると、ブロック４２４は、XPATH表現において指定されているタイミング間隔のどれが、所与のチックにおいてアクティブであるか、またはアクティブになるかを判定することを含むことができる。所与の時点においてアクティブであるタイミング間隔を「アクティブ間隔」と呼ぶ。
【００６０】
ブロック４２６は、アニメーション処理を実行することを表す。これは、アクティブ間隔を評価し、アクティブ間隔に対して新たなプレゼンテーション値を計算することを含むことができる。これらの間隔の値を積層し、種々の方法で層を組み合わせたりまたは覆い隠せるようにしてもよい。「プレゼンテーション値」という用語は、所与の時点に対する正味の値即ち有効値を意味する。プレゼンテーション値は、所与の間隔中ユーザーに接触可能にするが、他の値は、この値と関連付けること、積層の中に隠すこと、および／またはこの総合的なプレゼンテーション値に寄与するように組み合わせることもできる。ブロック４２６は、全体的に４２８で示す、サンドウィッチ・モデルに基づいて、これら新たなプレゼンテーション値を計算することを含むこともできる。サンドウィッチ・モデルは、所与のチックに対してプレゼンテーション値を指定することができ、更にＤＯＭのレイアウト・セクションにおいて念頭においているノードと関連のある動的プロパティを指定することができる。
【００６１】
ブロック４３０は、ブロック４２６から得られたプレゼンテーション値に対するフォーマット処理およびレイアウト動作を表す。ブロック４３０は、拡張可能スタイルシート言語（ＸＳＬ）を用いたフォーマット処理およびレイアウトを指定することを含むことができる。
【００６２】
以上、図４を用いて、タイミング・マークアップを処理するためのデーターおよびプロセス・フローについて説明したので、これより、これらのデーターおよびプロセス・フローの一部の形態に関する更なる詳細の説明に移る。ここでは、図５を用いて提案する。
【００６３】
図５は、図４に示したデーターおよびプロセス・フローの別の形態５００を示す。便宜上、以前に説明したエレメントの一部を図５にも引き継ぎ、同じ参照番号で示すこととするが、これは限定ではない。
【００６４】
図５に示すように、ＤＯＭ４２２は、複数の個別マークアップ・エレメントを含むことができる。図５では、これらを全体的に５０２で示す。図５は、マークアップ・エレメントの内３つの例を５０２ａ、５０２ｂ、および５０２ｎで示す。しかしながら、ＤＯＭの実現例は、任意の数のエレメント５０２を含むことができ、ＤＯＭツリーは適した形態であればいずれでも取ることができる。これらのマークアップ・エレメントは、ユーザーに画面上で描出するものについての場面記述を定めることができる。
【００６５】
図４に示すように、ブロック４２４は、アクティブ・アニメーション・リストを生成することを表す。アクティブ・アニメーション・リストは、複数のタイミング・コンテナを含むことができる。ブロック４２４は、アクティブ・アニメーション・リストの中にあるタイミング・コンテナを開始時刻属性（例えば、図２における２０８）でソートすることを含むことができる。これをブロック５０４で表す。また、ブロック４２４は、ブロック５０６で表すように、アクティブ・アニメーション・リストの中にあるタイミング・コンテナを字句単位でソートすることも含むことができる。
【００６６】
タイミング間隔のソート処理または整列は、しかるべきデーター構造を用いて「現場」で(in-place)で行うこともできる。本明細書において説明する技法を用いると、クロック・チック毎に全てのアクティブなタイミング間隔をソートし直す、または整列し直す必要はない。例えば、データー構造は、最終時刻、およびアクティブ間隔リストに追加されたタイミング間隔を追跡することができる。データー構造は、デフォルトで、最新のタイミング間隔をアクティブ間隔リストの終端に追加するように、プロセス４００および５００を駆動した統計的証拠を収容することができる。例外的な場合にのみ、新たなタイミング間隔に適した挿入点を突き止めるために、プロセスがアクティブ間隔リストを遡って調べることもある。通例、適した挿入点は、最後に追加した間隔に近接している。しかしながら、この挿入点を突き止めるには、ＨＤ−ＤＶＤタイミング・マークアップの本体の以前の統計的分析に基づくとよい。
【００６７】
ブロック４２６に移り、このブロックは、更に、アクティブ・アニメーション・リストに含まれるアクティブ間隔の処理も表すことができる。これをブロック５０８で表す。また、ブロック４２６は、ブロック５１０で表すように、現在のチックに対する新たなプレゼンテーション値を計算することも含むことができる。ブロック４２６は、ブロック５１２で現すように、マークアップ特定イベントを生成することを含むことができる。最後に、ブロック４２８は、ブロック５１４で現すように、いずれのインアクティブなタイミング間隔も復元することを含むことができる。
【００６８】
本明細書において示すツールおよび技法を用いると、プロセス４００および５００はXPATH表現の処理を最適化することができる。本明細書に記載するようにXPATH表現の処理を最適化すると、フレーム・レートの高速化を達成し、ＨＤ−ＤＶＤコンテンツと対話するときに、ユーザーまたはビューアにより良い操作性(experience)を提供することができる。
【００６９】
以上、図５を用いて、これらのデーターおよびプロセス・フローの別の形態について説明したので、これより、図６から開始する、最適化方策の更に詳細な説明に移る。
【００７０】
図６は、ある種のXPATH表現を予め解析し予め計算することを含む最適化方策に関するコンポーネントおよびプロセス・フロー６００を示す。便宜上、以前に説明したエレメントの一部を図６にも引き継ぎ、同じ参照番号で示すこととするが、これは限定ではない。
【００７１】
図６に示すように、最適化エンジン（例えば、１２４）は、ある種のXPATH表現を予め解析し予め計算するのに適したソフトウェア・コンポーネントを含むことができる。図３は、このようなソフトウェア・コンポーネントの例を、図３における３０８で示し、ブロック３０８を図６にも引き継いでいる。最適化エンジンは、XPATH表現マネージャー（例えば、３０２）と協同することもできる。
【００７２】
図６は、予備解析および予備計算によるXPATH表現を最適化するプロセス・フロー６００を示す。ブロック６０２は、XPATH表現マネージャーが受け取った、入力XPATH表現の解析を現す。図６は、２１８のXPATH表現の例を引き継いでいる。
【００７３】
ブロック６０４は、入力XPATH表現２１８の中で発生した１つ以上の中間XPATH表現を識別することを表す。図６は、これら中間表現の例を２つ、６０６ａおよび６０６ｎで示す。しかしながら、所与のXPATH表現２１８の中には、いずれの数の中間表現６０６が発生してもよい。
【００７４】
ブロック６０８は、中間表現６０６をキャッシュし、これらをＤＯＭツリー内部の対応するエレメントまたはノードと関連付けることを表す。ＤＯＭツリー４２２および関係するノード５０２を図６に引き継ぐ。キャッシュ６１０は、ＤＯＭツリーおよび関係するノードを格納することができる。
【００７５】
ブロック６１２は、XPATH表現全体についての結果を計算することを表すことができる。これは、XPATH表現全体を構成することができる中間表現に対して計算した結果とは別個である。以下で更に詳細に説明するが、あるクロック・チック上では、中間XPATH表現のいずれも値が変化せず、したがってXPATH表現全体の値が一定のままとなっている場合もある。
【００７６】
ブロック６１４は、XPATH表現全体についての値をキャッシュすることを表す。所与のチックの後XPATH表現全体の値が一定のままである例では、XPATH表現全体の直前値をキャッシュから読み出せばよい。
【００７７】
尚、ブロック６０２〜６０８は、ブロック６１２〜６１４と並列に実行してもよいことを注記しておく。このように、XPATH表現全体を解析して中間表現（例えば、６０６ａおよび６０６ｎ）を得て、種々の中間表現に対して値を計算しキャッシュすることができる。その間に、XPATH表現全体に対する値を、ブロック６１６で表すように、計算しキャッシュすることができる。
【００７８】
ブロック６１８は、チックまたはその他のタイミング・イベントを受信することを表す。チックに応答して、ブロック６２０は、予め解析し予め計算してあり、キャッシュに格納されている中間表現（例えば、６０６）を評価することを表す。また、ブロック６２０は、予め計算し、キャッシュに格納されている全体表現（例えば、６１６）の評価も含むことができる。ブロック６２２は、ブロック６２０において行った評価から得られる値を返送することを表す。その後、プロセス・フロー６００はブロック６１８に戻り次のチックを待つことができる。  
【００７９】
図６に示す技法では、中間表現は、ノード−セットの二進表現、演算子の二進リスト、および予測フィルタの二進表現を含むことができる正準形(canonical form)に対する各XPATH軸を完全に解明する。予測フィルタ以外の全ては、完全に解明することができる。これが意味するのは、中間表現が完全に解析されており、軸ノードセット(axis node-sets)が、当該軸におけるＤＯＭノードのリストを表す参照用データー構造を参照し、予測フィルタはその宣言型形態になっている元のストリング・データーを、再解釈を必要とせずに効率的に評価することができる一層単純な二進形態に変換したということである。
【００８０】
これらの表現をキャッシュするには、異なるメカニズムによって行うこともでき、時間間隔ノードをカプセル化するデーター構造／オブジェクト上に、解析した表現に対する参照を格納することを含む。ロードの時点、または連続オンチック／レイアウト動作以前であればいずれの時点でも、XPATH表現を解析し、予め計算し、二進正準形に変換することができる。尚、この動作は所与のＤＯＭに対して１回だけ行われ、ＤＯＭが突然変異した場合にのみ再度行われることを注記しておく。一旦XPATH表現を解析し、少なくとも部分的に解明（場合によっては、完全に解明）したなら、表現マネージャーは、予測フィルタ上のみで表現を評価することができる。予測フィルタも簡略化されている。
【００８１】
以下の例について考える。
【表４】
2010516011.tif 000006
【００８２】
XPATH表現'//button[style:backgroundColor()='red']'は、エレメント名が"button"である、ＸＭＬ  ＤＯＭにおけるエレメントの全てに問い合わせ、その集合から、style:backgoundColorプロパティの現計算値が値'red"に等しいのであれば、いずれでも返すことを意味する。
【００８３】
典型的な環境では、この表現を最初に解析し、その後評価することができる。解析フェーズでは、元のストリングを一連の１つ以上のトークンに変換し、これらを参照データー構造に格納する。この参照データー構造は、元のストリング表現を簡略化した効率的な形態で記述する。通例、表現を解析するには、回帰下降解析アルゴリズムを用いればよい。しかしながら、他の解析アルゴリズムおよび手法も用いることができる。
【００８４】
解析フェーズの間に実行することができるプロセスの１つに、軸解明がある。軸解明とは、予測フィルタの０個以上が動作する１つ以上のノード・セットを作成するプロセスのことを言う。各時間間隔がその不明確なXPATH表現を解析するにつれて、間隔は、解析し部分的に解明した表現に対する参照を維持する。通例、この参照は、基礎のＤＯＭが突然変異しない限り（ＨＤ−ＤＶＤアプリケーションでは通常希である）、この解析フェーズを再度実行するいずれの必要性も排除する。
【００８５】
一旦解析フェーズが完了したなら、表現評価である第２フェーズには一層簡略化し効率的な二進データー構造が用いられる。表現評価は、簡略化したデーター構造に対して行われ、０個以上の予測フィルタに基づいて、結果を解明し生成することのみを含む。予測フィルタも二進正準形で表されているので、表現評価に関する処理オーバーヘッドが低減する。
【００８６】
図６に示す方式の下では、XPATH表現を解析するという時間がかかり処理集約的なタスクは１回だけ行えばよく、中間表現は部分的に（または、場合によっては完全に）解明される。これらの最適化は、XPATH表現の処理および評価に関連する処理オーバーヘッドを大幅に低減することができる。
【００８７】
以上、図６を用いて、表現の予備計算を含む最適化方策について説明したので、これより、イベント・ドリブン表現を含む最適化方策の更に詳細な説明に移る。
【００８８】
イベント・ドリブン表現を含む最適化方策の更なる詳細に移り、図３は、最適化エンジン１２４によって供給することができる、イベント・ドリブン表現を３１０において含む最適化方策を示す。これらの最適化方策は、不明確な表現を、イベントの発生によって駆動される、またはイベントの発生に依存する表現に分離することを含むことができる。これらの表現は、基礎の値をポーリングで決定することができる表現とは区別する。例えば、タイミング・コンテナ（例えば、ｐａｒ、ｓｅｑ、およびｃｕｅ）は、ＨＤ−ＤＶＤ状態名称空間を用いて、いつそれらのそれぞれの間隔がアクティブまたはインアクティブになるか定めることができる。対話状態（例えば、state:foreground、state:focused、state:pointer、state:actioned、state:value、およびstate:enabled）は、主に、ユーザーがコントローラを通じて  始動するイベントから駆動することができる。これらのイベント・ドリブン・イベントは、タイミング・マークアップの処理からは、帯域外で扱うことができる。これらのイベントまたは状態遷移は、イベント・ドリブン・メカニズムを誘起するために用いることができ、チック毎に実行する表現評価を不要にするか、またはその回数を減らすことができる。
【００８９】
ＨＤ−ＤＶＤ仕様では、コントローラ・イベント、即ち、「ジェスチャー」をどのようにしてプレゼンテーション・エンジンに伝搬するかについてのモデルを定める。これらのイベントは、「チック」処理からは帯域外で送ることができ、マークアップＤＯＭの「状態」名称空間に影響を及ぼす可能性がある。ＨＤ−ＤＶＤ仕様では、サンドイッチ・モデルの観点から、「状態」への変化が直ちにＤＯＭにおける基礎属性の変化に至るため、「状態」名称空間を「スタイル」名称空間とは別個に定めている。
【００９０】
状態値は、チックおよびレイアウト処理からは帯域外で扱われるので、ジェスチャー・イベントを扱うプロセスは、後にオンチック処理の間に扱われるアニメーション・リストを管理するデーター構造に関係付けることもできる。状態値を変化させると、この状態変化の解明を待っているいずれのXPATH表現にも直接結び付けることができる。
【００９１】
begin XPATH表現を収容する次のｃｕｅについて考える。
【表５】
2010516011.tif 000007
【００９２】
このｃｕｅは、state:focused属性が、一意の名称が'myButton1'であるエレメントに対して「１」に設定されたときに開始することを宣言する。プレゼンテーション・エンジン内におけるジェスチャー処理ロジックが、ユーザー入力およびその後の状態管理を管理することができる。この表現が真になるときを求めてXPATHエンジンを継続的にポールする代わりに、ジェスチャー処理ロジックは、XPATH表現を評価することなく、XPATH表現を解明することを可能にする所定の知識を有することができ、これによってXPATH表現を評価する際のオーバーヘッドを回避する。
【００９３】
以上、イベント・ドリブン表現の最適化に関する予備処理について説明したので、これより、イベントが発生するときに実行することができる処理の説明に移る。これを、図７を用いて提案する。
【００９４】
図７は、イベント・ドリブン表現の最適化に関するコンポーネントおよびフロー７００を示す。便宜上、以前に説明したエレメントの一部を図７にも引き継ぎ、同じ参照番号で示すこととするが、これは限定ではない。
【００９５】
「イベント」または「複数のイベント」という用語は、本明細書において用いる場合、ユーザー入力によって生ずるスタイルおよび状態に対する変化、ならびにアニメーションおよび／またはスクリプトから生ずるスタイルおよび状態に対する変化のことを言う。更に具体的には、XPATH表現マネージャー（例えば、３０２）はプレゼンテーション・エンジン（例えば、１２２）との関係を確立し、その下において、XPATH表現マネージャーは、前述のように、著作者が定めるスクリプト・コード、ユーザー入力、またはアニメーションから生ずる、状態およびスタイル・プロパティへの変化を受け入れる。言い換えると、スクリプト・コードは０個以上のプロパティ値（状態およびスタイル双方）を修正する可能性があり、ユーザー入力はいずれの対話エレメントの状態でも変化させる可能性があり、アニメーション（即ち、タイミング・エレメントの処理）はエレメントの状態およびスタイルの変化を生じさせる可能性がある。XPATH表現マネージャーは、これらの入力を受け入れ、それに応じてXPATH表現のその内部キャッシュを管理し更新する。
【００９６】
既に説明したように、ユーザー（例えば、１０２）は入力をＨＤ−ＤＶＤプレーヤー（例えば、図１における１０８）に供給することができる。例えば、ユーザーはコマンドを入力し、プレゼンテーション・エンジン（例えば、１１６）が表示するプロンプトまたはメニューに応答することができる。図７は、このようなユーザー入力を全体的に７０２で示し、発話コマンド、遠隔制御デバイスによって入力したコマンド、またはＨＤ−ＤＶＤプレーヤー上のボタンを通じて入力したコマンドなどを含むことができる。プレゼンテーション・エンジンは、ユーザー入力７０２を受け取って処理するジェスチャー処理ロジック７０４を含む、またはこれと協同することができる。
【００９７】
ジェスチャー処理ロジック７０４は、ユーザー入力７０２に応答して発生する個々のイベントを認識することができ、これらのイベントに対応する識別子を用いて、キャッシュ７０６に問い合わせることができる。図７は、このような識別子の例を７０８において提示する。図７は、これらの照会を７１０で示す。一方、キャッシュ７０６は、入力イベント識別子７０８と一致するいずれのフィールドでも戻すことができる。入力イベント識別子がキャッシュ内のいずれかのフィールドまたはレコードと一致した場合、キャッシュは一致したフィールドまたはレコードと関連のある、いずれの評価済みの表現７１２でも返すことができる。表現７１２は、ユーザー入力７０２から生ずるイベントに応答して値が変化する可能性がある表現を含む。
【００９８】
プレゼンテーション・エンジンに移り、チック２０４が発生すると、プレゼンテーション・エンジン１１６は、これらのチックに応答して、ＤＯＭ４２２からXPATH表現２１８を受け取ることができる。プレゼンテーション・エンジン１１６は、XPATH表現２１８を、キャッシュ７０６から返されたいずれのイベント・ドリブン表現７１２またはイベント依存表現７１２とでも比較することができる。この比較によって、評価がユーザー入力７０２から生ずるイベントには依存しないXPATH表現を識別し、更に、評価がこのようなイベントのために変化する可能性があるXPATH表現を識別する。前者をイベント独立表現と称することができ、２１８ａで示す。後者をイベント・ドリブンまたはイベント依存表現と称することができ、２１８ｂで示す。
【００９９】
これより、イベント独立表現２１８ａに移ると、これらの表現の値または評価は、ユーザー・イベントのために変化することはない。つまり、このような表現の以前の値が既にキャッシュされている場合（例えば、キャッシュ７１４に）、これら以前の値は不変であり、最新であり、正しいままである。したがって、プレゼンテーション・エンジン１１６はこれらのイベント独立表現２１８ａを、３０２ａで示す、XPATH表現マネージャーのインスタンスに転送することができる。XPATH表現マネージャー３０２ａは、これらイベント独立表現の以前の値をキャッシュ７１４から読み出すことができる。XPATH表現マネージャー３０２ａは、次に、これら評価済みの表現（７１６で示す）についての値を、使用のためにプレゼンテーション・エンジンに転送することができる。
【０１００】
これより、イベント依存XPATH表現２１８ｂに移ると、これらの表現は、ユーザー入力７０２のために値または評価が変化する可能性がある。これらの場合、プレゼンテーション・エンジン１１６は、いずれのイベント依存表現２１８ｂも、３０２ｂで示す、XPATH表現マネージャーのインスタンスに転送することができ、イベント依存表現２１８ｂを再評価し、７１８で示す、これら再評価した表現の更新値を返す。
【０１０１】
図７は、XPATH表現マネージャーの異なるインスタンスを示すが、これは図示および参照を容易にするためであり、可能な実現例を限定するためではない。更に具体的には、実現例によっては、１つのXPATH表現マネージャー３０２がイベント独立表現２１８ａおよびイベント依存表現２１８ｂ双方を処理する場合もある。
【０１０２】
図８は、イベント依存表現またはイベント・ドリブン表現の処理を最適化するプロセス・フロー８００を示す。図８は、フローチャート形式で、図７と関連付けて例示し説明した処理を示す。便宜上、以前に説明したエレメントの一部を図８にも引き継ぎ、同じ参照番号で示すこととするが、これは限定ではない。
【０１０３】
加えて、図８は、プレゼンテーション・エンジン（例えば、１１６）および最適化エンジン（例えば、１２４）に対応する列毎に処理エレメントの一部を並べているが、これも説明を容易にするためであり、限定ではない。最適化エンジンは、イベント・ドリブン表現（例えば、３１０）の処理の最適化に関するソフトウェア・コンポーネントを含むことができる。
【０１０４】
ブロック８０２は、ユーザーからの入力を受信することを表す。図７は、ユーザーの一例を１０２で示し、ユーザーから受け取る入力の一例を８０２で示す。
【０１０５】
ブロック８０４は、ブロック８０２において受け取ったユーザー入力から生ずるあらゆる変化またはイベントを識別することを表す。ブロック８０４は、既定のイベント識別子（例えば、図７における７０８）に対応する可能性があるイベントであればいずれでも識別することを含むことができる。これらの既定イベント識別子は、これらのイベントの結果値が変化する可能性があるいずれのXPATH表現の識別も可能にすることができる。
【０１０６】
ブロック８０６は、イベント・ドリブンまたはイベント依存表現を識別することを表す。ブロック８０６は、対応するXPATH表現の内、１つ以上の基礎イベントが発生したときに値が変化する可能性があるものに関係するイベント識別子のキャッシュに問い合わせることを含むことができる。図７は、イベント識別子７０８およびイベント依存表現７１２と共に、このようなキャッシュの例を７０６で提示する。
【０１０７】
ブロック８０８は、チックまたはその他のタイミング入力が生じたことの指示を受け取ることを表す。図７および本明細書におけるその他の図面では、チックの例を２０４で示す。
【０１０８】
ブロック８１０は、ブロック８０８において受け取ったチックに応答して、１つ以上のXPATH表現を受け取ることを表す。図７およびその他の図面では、XPATH表現の例を２１８で示し、ブロック８１０は、これらのXPATH表現をＤＯＭ（例えば、図７における４２２）から受け取ることを含むことができる。
【０１０９】
尚、ブロック８０２〜８０６において表す処理は、ブロック８０８および８１０において表す処理と並列に進めてもよいことを注記しておく。このように、プロセス・フロー８００は、入力タイミング・チックも処理しつつ、入来するユーザー・イベントを処理することができる。
【０１１０】
ブロック８１２は、ブロック８１０において受け取ったXPATH表現が、ブロック８０２において受け取ったユーザー入力から生ずるいずれかのイベントに依存するか否かを評価することを表す。XPATH表現がイベント・ドリブンである、即ち、イベント依存である場合、これらの表現の値は、ブロック８０２において受け取ったユーザー入力に関係するイベントのために変化している可能性がある。したがって、プロセス・フロー８００はＹｅｓ分岐８１４を取りブロック８１６に進む。ブロック８１６は、ユーザー・イベントの発生に照らし合わせて、いずれのイベント・ドリブンXPATH表現も再評価することの要求を表す。ブロック８１６は、XPATH表現マネージャー（例えば、３０２）に表現を再評価することを要求することを含むとよい。図８は、この要求を８１８で表す。
【０１１１】
XPATH表現マネージャー３０２に移り、ブロック８２０はXPATH表現の評価要求を受け取ることを表す。ブロック８２０は、イベント依存即ちイベント・ドリブンであるXPATH表現の再評価要求を受け取ることを含むことができる。
【０１１２】
ブロック８２２は、要求８１８に応答して１つ以上のXPATH表現を評価することを表す。ブロック８２２は、１つ以上のイベントの発生に応答して、１つ以上のイベント・ドリブンXPATH表現を再評価することを含むことができる。
【０１１３】
ブロック８２４は、ブロック８２２において表現を再評価したことによって得られる値を送ることを表す。言い方を変えると、ブロック８２４は、表現が依存するいずれのイベントの発生をも考慮するように、表現の値を更新することを表す。図８は、８２６における表現の再評価の結果を示す。
【０１１４】
ブロック８２８は、ブロック８２４における表現を再評価した結果を受け取ることを表す。図８に示す例では、プレゼンテーション・エンジンがブロック８２８を実行することができる。
【０１１５】
評価ブロック８１２に戻って、入力XPATH表現がユーザー・イベントに依存しない場合、プロセス・フロー８００はＮｏ分岐８３０を取りブロック８３２に進むことができる。ブロック８３２は、この表現の以前の値を読み出すことを表す。例えば、ブロック８３２は、以前に表現を評価して、キャッシュ（例えば、７１４）に格納されている結果を読み出すことを含むことができる。このようにして、プロセス・フロー８００は、基礎のユーザー・イベントの発生に値が依存しないいずれのXPATH表現についてもブロック８１６〜８２８において表す処理を回避することができる。
【０１１６】
以上、図８においてイベント・ドリブン表現の処理を最適化するプロセス・フロー８００について説明したので、論述は有限状態機械を用いた最適化技法の説明を表す。ここでは、図９を用いて提案する。
【０１１７】
図９は、有限状態機械を用いた最適化技法９００を示す。便宜上、以前に説明したエレメントの一部を図９にも引き継ぎ、同じ参照番号で示すこととするが、これは限定ではない。
【０１１８】
図９では、全体的に３１２で表す、有限状態機械を含む最適化技法に関する処理の更に詳しい説明を行う。最適化エンジン１２４は、これらの最適化技法を備えることができる。
【０１１９】
本明細書において記載するような有限状態機械は、種々のタイミング間隔およびそれらに関係する先祖を効率的に処理するために、アニメーション・エンジンに埋め込むことができるメカニズムを設ける。基本的な状態は、インアクティブ、アクティブ、およびホールドである。所与のタイミング間隔の間における中間状態変数は、再起動可能、未決、および解決済みを含むことができる。また、状態変数はいずれの指定された開始、終了、および持続期間属性でも含むことができる（該当する場合）。図２は、このような属性の例を２２０、２２２、および２２４で示す。
【０１２０】
アニメーション・エンジン内においてこの状態機械メカニズムを採用すると、特定のタイム・シート(time sheet)内における時間間隔の効率的な処理が可能になる。何故なら、タイミング間隔のサブツリー(sub-tree)を丸ごと飛び越し易くなるからである。可能な実現例を限定することなく、「タイム・シート」という用語は、ここで用いる場合、同じ時間基準に全て同期が取られているタイミング・エレメントのコンテナのことを言う。加えて、所与の親時間間隔がインアクティブになると、その子の全てもインアクティブおよび再起動可能となる。また、状態機械は所与の時間間隔の再起動可能状態を追跡することもできる。
【０１２１】
図９に示すように、ブロック９０２は、少なくとも１つのチック、タイミング・パルス、またはその他のクロック関係イベントの指示を受け取ることを表す。ブロック９０４は、所与のXPATH表現の中にある親タイミング・コンテナがアクティブであるか否か評価することを表す。アクティブでない場合、ブロック９０６はこの親タイミング・コンテナのいずれの子の処理も省略することを表す。逆に、親タイミング・コンテナがアクティブである場合、ブロック９０８はその親の内１つの子タイミング・コンテナを処理のために選択することを表す。
【０１２２】
ブロック９１０は、子タイミング・コンテナにおいて指定されているいずれかの開始条件が満たされているか否か評価することを表す。満たされている場合、ブロック９１２は子タイミング・コンテナにおいて指定されているいずれの表現も評価することを表す。満たされていない場合、ブロック９１４は、親タイミング・コンテナが評価すべき別の子を未だ有しているか否か評価することを表す。有している場合、ブロック９１６は次の子タイミング・コンテナを処理のために選択することを表す。その後、プロセス９００はブロック９１０の前に戻り、この次の子を用いてプロセスを繰り返す。
【０１２３】
ブロック９１４から、親タイミング・コンテナが他に子を有していない場合、ブロック９１８は、他に評価すべきいずれかの親タイミング・コンテナが未だ残っていないか評価することを表す。残っている場合、ブロック９２０は次の親タイミング・コンテナを処理のために選択することを表す。その後、プロセス９００はブロック９０４の前に戻り、この次の親を用いてプロセスを繰り返す。
【０１２４】
ブロック９１８から、他に親タイミング・コンテナがない場合、プロセス９００は終了状態９２２に達することができる。
【０１２５】
以上のプロセス９００は、本明細書において例示し説明した機能を実行する１つ以上の有限状態機械として実現することができる。
【０１２６】
図３において全体的に３１４で表す別の最適化技法では、重複表現を評価することを回避するために、相補表現を認識し、代わりに一意のXPATH表現を評価することに照準を当てる。「相補」表現は、ブール・ロジックに関して定められる。例えば、表現「Ａ」が真である場合、表現「ｎｏｔＡ」に言及するケースは全て偽となる。
・    
【０１２７】
ＨＤ−ＤＶＤの著作者は、所与の「秘匿」入力エレメント上でstate:valueを用いて、タイミング・コンテナの挙動を制御することができる。同じ表現が複数回用いられているが、異なるタイム・コンテナにおける場合、表現の評価は１回だけで十分とすることができる。その表現に対するその他の参照は、１つの評価の状態を反映するように更新すればよい。
【０１２８】
同様に、これらの表現に対して相補的である（即ち、反対のブール演算子を用いる）表現も飛ばすことができる。何故なら、いずれの後続の相補表現が真または偽であるかの判断も、１回の評価で十分であるからである。以下のｃｕｅを検討する。
【表６】
2010516011.tif 000008
【０１２９】
タイミング・エンジンが最初のｃｕｅを評価し、これがアクティブ（即ち、真）であると判断したと仮定する。この場合、タイミング・エンジンは２番目のキューの評価を飛ばすことができる。何故なら、２番目のキューは最初のｃｕｅの評価の逆の結果となるからである。また、タイミング・エンジンは３番目のｃｕｅの評価を飛ばすこともできる。何故なら、最初のｃｕｅが真であれば、３番目のｃｕｅも真となることはできないからである。
【０１３０】
この最適化は、ロード時間中に関係する表現および相補表現を結び付けるように修正することができる参照データー構造を用いて実現することができる。これらの参照データー構造は、オン・チック処理の間でもアクセスすることができるので、評価が行われつつあるときに、表現の解明(resolution)を更新することもできる。
【０１３１】
図１０は、共有メモリー・プールを用いてタイミング・マークアップの処理を最適化することに関するコンポーネントおよびフロー１０００を示す。便宜上、以前に説明したエレメントの一部を図１０にも引き継ぎ、同じ参照番号で示すこととするが、これは限定ではない。
【０１３２】
図１０は、図３において全体的にブロック３１６で表した、共有メモリーの使用を含む最適化技法に関する更なる詳細を提示する。最適化エンジン（例えば、１２４）はこれらの最適化技法３１６を実現することができる。
【０１３３】
キャッシュ１００２を共有メモリー・プール１００４として実装することができる。共有メモリー・プールは、複数の小さな固定サイズの参照データー構造（例えば、１００６ａおよび１００６ｎ）を格納することができる。これらの参照データー構造は、ＤＯＭタイミング・ツリー（例えば、タイミング・ノード５０２を有する４２２）を効率的に横断するための情報をカプセル化する。
【０１３４】
このデーター構造は、複数のソート・リンクに対処し、ノードの状態に基づいて、タイミング・ノードのグループ単位で飛び越すことにも対処する。図１０は、このようなリンクの例を１００８ａ（構造１００６ａをノード５０２ａに結び付ける）および１００８ｎ（構造１００８ｎをノード５０２ｎに結び付ける）を示す。
【０１３５】
共有メモリー・プール１００４は、ＤＯＭツリーの素早い横断を促進する。何故なら、メモリーはＬ１データー・キャッシュをサポートするＣＰＵのために容易に局在的にキャッシュされるからである。データー構造１００６の参照的本質(referential nature)は、マークアップ・タイミングにおける複数のノード状態に基づいて、複数のノードを飛び越す能力をサポートする。加えて、このデーター構造は、インデックス増分またはポインタ追加動作を用いて、ＤＯＭツリー全体を素早く横断する能力を備えている。これらの技法と合わせて、関係する共有メモリー・プールを用いると、XPATH表現、ソート・インデックス、および参照キーの関係において補助することができ、タイミングおよびXPATH関係データー構造の高速で空間効率的な参照がやり易くなる。
【０１３６】
以上、図１０における共有メモリー・プールの使用に関する最適化技法について説明したので、論述はスケジューラーの使用に関する最適化技法の説明に移る。ここでは、図１１を用いて提案する。
【０１３７】
図１１は、完全なタイミング・ツリーの横断を実行することを回避するためのスケジューラー１１０２の使用に関する最適化技法を示す。スケジューラー１１０２は、タイミング・マークアップ１０６からのタイミング・ノード５０２をワーク・キュー１１０４の中に置く。更に具体的には、スケジューラー１１０２は、いずれの所与のチックにおいても評価に関連があると思われるタイミング・ノードのみを置く。スケジューラーによって処理されるワーク・キュー・ワーク(work queue work)における各項目即ちタイミング・ノードは、タイミング間隔（例えば、１１０６ａおよび１１０６ｎ）およびそれと関連のある子（例えば、１１０８ａおよび１１０８ｎ）に対する参照を収容することができる。
【０１３８】
ワーク・キューは、開始時刻によって整列し、次いでマークアップＤＯＭの中に現れるときに、字句単位で後から整列することができる。この整列によって、評価すべきまたは処理すべきタイミング間隔のみがワーク・キューに置かれる確率が高くなり、このため余分なタイミング・ツリーの処理をいずれも排除する。加えて、このメカニズムは、潜在的に帯域外で行われる可能性がある動作（例えば、ジェスチャ処理）のシリアル化改良も可能にすることができる。この手法は、ワーク項目および関連データーのキャッシュ局在性(cache locality)改良を可能にするために前述のメモリー・プール手法と合わせて用いることができる。
結論
【０１３９】
以上の説明は、ＨＤ−ＤＶＤタイミング・マークアップの最適化処理という文脈で紹介したが、本明細書において記載したツールや技法は、他の種類の媒体を処理する際にも適しており、あるいは本明細書において記載した形式以外の形式のマークアップを処理する際にも適していると言えることを注記しておく。
【０１４０】
以上、構造的特徴および／または方法論的行為に特定したことばで本システムおよび方法について説明したが、添付した特許請求の範囲に定めるシステムおよび方法は、記載した特定の特徴や行為に必ずしも限定されないことは言うまでもない。逆に、特定の特徴および行為は、特許請求するシステムおよび方法を実現する形態の例として開示したのである。
【０１４１】
加えて、本明細書において説明し図示したある種のデーターおよびプロセス・フローの図に関して、この中で図示したプロセスおよびサブプロセスは、本明細書の記載の主旨および範囲から逸脱することなく、図示した順序とは別の順序で実行してもよいことを注記しておく。また、これらのデーターおよびプロセス・フローは、本明細書におけるある種のコンポーネントと関連付けて説明したが、これらのデーターおよびプロセス・フローは、本明細書における説明の主旨および範囲から逸脱することなく、他のコンポーネントとでも実行できることを注記しておく。
【図１】
2010516011.tif 000009
【図２】
2010516011.tif 000010
【図３】
2010516011.tif 000011
【図４】
2010516011.tif 000012
【図５】
2010516011.tif 000013
【図６】
2010516011.tif 000014
【図７】
2010516011.tif 000015
【図８】
2010516011.tif 000016
【図９】
2010516011.tif 000017
【図１０】
2010516011.tif 000018
【図１１】
2010516011.tif 000019
【国際調査報告】
2010516011.tif 000020
2010516011.tif 000021