(57)【要約】  文書内に表示されるコンテンツのタイプ、および表示される文書のサイズ／寸法が与えられると、見栄えのよい文書である高品質文書を作成するために使用されるアーキテクチャ。このアーキテクチャは、コンテンツを、多種多様なフォーマットの多種多様なコンテンツを伴う複数のサイズおよび寸法に適応させるレイアウト制約を広く定義する高水準のテンプレートを使用することができる。さらに、高品質文書の高水準の記述を、ＡＧＤＢＬシステムで使用するための低水準の制約に変換することができ、そのシステムによって必要とされるテンプレートの数が劇的に減少し、それと同時にテンプレートの機能性、およびテンプレートを作成して維持することができる容易さが向上する。
2009510650.tif 000002
【特許請求の範囲】
【請求項１】
多種多様なコンテンツを伴い複数のサイズおよび寸法で表示することができる文書レイアウトの適応を容易にするシステムであって、
文書レイアウトについての制約の高水準記述であるテンプレート（１０４）を受け取るインタフェース（１０２）と、
高品質レイアウト（１１０）を自動的に作成するために、前記テンプレートを解釈し、コンテンツ（１０８）をどこに置くか決定するレイアウトエンジン（１０６）と
を備えることを特徴とするシステム。
【請求項２】
高水準制約パラメータによって前記テンプレートのデザインおよび／または修正を容易にし、前記テンプレートのストレージを提供するユーザインタフェースをさらに備えることを特徴とする請求項１に記載のシステム。
【請求項３】
前記ユーザインタフェースは、グラフィカルユーザインタフェース（ＧＵＩ）であることを特徴とする請求項２に記載のシステム。
【請求項４】
前記レイアウトエンジンは、意味の流れ、ブランドアイデンティティ、イメージとテキストの相関性、および広告テーマの少なくとも１つに基づいて前記高品質レイアウトを作成することを特徴とする請求項１に記載のシステム。
【請求項５】
前記レイアウトエンジンは、前記テンプレート、前記高品質レイアウトで使用されるべきコンテンツのタイプ、および前記高品質レイアウトの表示寸法に基づいて前記高品質レイアウトを作成することを特徴とする請求項１に記載のシステム。
【請求項６】
前記高品質レイアウトを表示する出力装置をさらに備え、前記高品質レイアウトの前記表示寸法は、前記出力装置に基づくことを特徴とする請求項５に記載のシステム。
【請求項７】
前記高品質レイアウトの前記表示寸法は、前記テンプレートが作成されるときは知られていないことを特徴とする請求項５に記載のシステム。
【請求項８】
前記高品質レイアウトで使用されるべき前記コンテンツのタイプは、前記テンプレートが作成されるときは知られていないことを特徴とする請求項５に記載のシステム。
【請求項９】
低水準の制約に基づいて前記コンテンツを適応グリッドベースのレイアウトに適用する低水準エンジンをさらに備え、前記レイアウトエンジンは、前記高品質レイアウトのために前記コンテンツをどこに置くか決定し、前記高品質レイアウトを作成するのに前記低水準エンジンに必要な前記低水準制約を生成することを特徴とする請求項１に記載のシステム。
【請求項１０】
前記レイアウトエンジンは、前記コンテンツに適した位置に基づいてコンテンツをどこに置くか決定することを特徴とする請求項１に記載のシステム。
【請求項１１】
前記文書レイアウトは、最上位レベルおよび最下位レベルを有するマルチレベル文書レイアウトであり、前記レイアウトエンジンは、前記最上位レベルに置かれたコンテンツの位置に基づいて前記最下位レベルでコンテンツをどこに置くか決定することを特徴とする請求項１に記載のシステム。
【請求項１２】
前記高品質レイアウトで使用される前記コンテンツは、複数のソースから集約されることを特徴とする請求項１に記載のシステム。
【請求項１３】
前記レイアウトエンジンは、拡張可能スタイルシート言語変換（ＸＳＬＴ）を使用して、前記コンテンツが受け取られるソースフォーマットから前記コンテンツを変換することを特徴とする請求項１に記載のシステム。
【請求項１４】
高品質レイアウトを作成するようにコンテンツを配置するためのコンピュータ実施される方法であって、
高水準言語で定義される文書レイアウト用のテンプレートを選択すること（８０２）と、
文書の表示サイズを決定すること（８０４）と、
前記文書のコンテンツを受け取ること（８０６）と、
前記コンテンツに使用可能な位置を決定するために前記テンプレートおよび前記表示サイズを使用すること（８０８）と、
前記使用可能な位置から前記コンテンツの高品質位置を選択すること（８１０）と、
前記コンテンツを前記高品質位置に配置することによって前記文書の高品質レイアウトを作成すること（８１２）と
を含むことを特徴とするコンピュータ実施される方法。
【請求項１５】
文書用のテンプレートを高水準言語で定義することをさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
前記文書の前記表示サイズおよび前記コンテンツの前記タイプは、前記テンプレートが定義されるときは知られていないことを特徴とする請求項１５に記載の方法。
【請求項１７】
前記コンテンツに使用可能な位置を前記決定することは、前記文書内に以前に置かれた他のコンテンツの位置に少なくとも部分的に基づくことを特徴とする請求項１４に記載の方法。
【請求項１８】
高品質位置を前記選択することは、ベストフィットアルゴリズム、ファーストフィットアルゴリズム、ファーストフィットグッドアルゴリズムの少なくとも１つであるアルゴリズムに基づくことを特徴とする請求項１４に記載の方法。
【請求項１９】
高品質位置を前記選択することは、意味の流れ、ブランドアイデンティティ、イメージとテキストの相関性、および広告テーマの少なくとも１つに基づくことを特徴とする請求項１４に記載の方法。
【請求項２０】
多種多様なコンテンツを伴い複数のサイズおよび寸法で表示することができる高品質レイアウトを作成するようにコンテンツを配置するコンピュータ実装されるシステムであって、
文書レイアウト用のテンプレート（１０４）の制約を高水準言語で記述する手段と、
文書表示装置サイズを決定する手段（１０６）と、
前記文書のコンテンツを受け取る手段（１０８）と、
前記テンプレートおよび前記表示サイズに基づいて前記コンテンツに使用可能な位置を決定する手段（１０６）と、
前記使用可能な位置から前記コンテンツの高品質位置を選択する手段（１０６）と、
前記コンテンツを前記高品質位置に置くことによって前記文書の高品質レイアウト（１１０）を作成する手段（１０６）と
を備えることを特徴とするコンピュータ実装されるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、動的に集約された文書のための調和構成を備えたマルチフォームデザインに関する。
【背景技術】
【０００２】
新聞および雑誌などの市販の刊行物は、グリッドベースのページレイアウトおよびデザインを大いに使用する。１９２０年代および１９４０年代に、デザイナーのモンドリアン（Mondrian）およびル・コルビュジエ（Le Corbusier）は、様々なタイプの文書コンテンツを印刷するための整然としたグリッドベースデザインシステムを作成した。これらのグリッドベースデザインシステムは、第二次世界大戦後にスイスでさらに改良され、１９５０年代および１９６０年代に、市販刊行物の規格として世界中に急速に普及した。今日、グリッドベースデザインシステムは、様々な出版システムで広く一般に、いまだ実践されている。
【０００３】
グリッドベースのページデザインをサポートするいくつかの成功したソフトウェアシステムが存在する。ワシントン州レッドモンドのマイクロソフト社によって売り出されたＭＩＣＲＯＳＯＦＴ  ＰＵＢＬＩＳＨＥＲ、コロラド州デンバーのＱｕａｒｋ社によって売り出されたＱＵＡＲＫＸＰＲＥＳＳ（登録商標）、およびカリフォルニア州サンノゼのＡｄｏｂｅ  Ｓｙｓｔｅｍｓ  Ｉｎｃｏｒｐｏｒａｔｅｄ社によって提供されたＡＤＯＢＥ  ＰＡＧＥＭＡＫＥＲ（登録商標）などの製品は、商業出版およびデスクトップパブリッシングの業界標準となっている。これらのソフトウェアシステムは、その意図された目的には適しているが、テキスト、イメージ、およびサイドバーなどのページエレメントを文書レイアウト内のグリッド位置に実際にマッピングすることは、手動のプロセスのままである。典型的に、グリッドベースの文書レイアウトは、８．５インチ（２１．６ｃｍ）×１１インチ（２７．９ｃｍ）の用紙など、ある特定のページサイズに合わせてカスタマイズされる。しかし、これらのカスタマイズされたレイアウトをページサイズの範囲および他の表示条件（viewing condition）に体裁よく適応させる明白な方法（すなわち、本明細書では「文書リフロー（document-reflow）」とも呼ばれる）はない。
【０００４】
グリッドベースの文書レイアウトは静的な固定サイズと手動のプロセスの両方から成るので、グリッドベースのデザインシステムは一般に、「文書リフロー」をサポートしない。Ｍｉｃｒｏｓｏｆｔ  ＷｏｒｄおよびＨＴＭＬ（hypertext mark-up language）などの文書コンテンツのリフローをサポートするシステムは典型的に、文書コンテンツを、あるページから次のページにくねって進む（snake）単一の一次元のフロー（one-dimensional flow）と見なす。したがって、これらのタイプのシステムは、元のグリッドベース文書レイアウトを失う可能性がある。このような困難性は、異なるフォームファクタ（form factor）で複数の方向性を使用するシステムでも同様に生じる可能性がある。
【０００５】
グリッドベースのデザインを一般化することの困難性から、類似の印刷レイアウトと比べて画面上のレイアウトの性質が一般的に劣っていることが分かる。ディスプレイ装置の画面解像度が印刷ページの解像度品質に一致し始めるにつれて、グリッドベース文書デザインを任意のサイズの電子ディスプレイに、容易かつ自動的に適応させる必要性が生じる。「調和構成（harmonic composition）」を使用して、動的に集約された文書にとって最適な表示と読みやすさ（readability）のためにエレメントの関係と比率を維持するように、グリッドベースのシステム内の（限定ではないが）テキストおよびイメージなどのオブジェクトの配置に適用される１組の規則および制約を定義することができる。これは、効果的な高品質の適応レイアウト（adaptive layout）の開発および設計に特有の要因である可能性がある。この問題は恐らく、紙に書かれたものを読むことに劣らないオンライン上で読むという体験をもたらすことにおいて、残ったままの最大の障害の１つである。コンピュータにより、カスタマイズおよびスタイルのための多くの機会、ならびにアニメーションおよびインタラクティビティなどの性能が提供されるので、画面上で読むという体験は最終的に、紙の上で読むという体験を超える可能性がある。
【０００６】
適応グリッドベース（adaptive grid-based document）の文書レイアウトは、文書コンテンツを１組の個別のページにマッピングするための柔軟なページネーション（pagination）を必要とする。個別のページには、テキストのストリーム内の単語（word）のシーケンス順序付け、ページの有限容量、および文書内のコンテンツ間の依存性（例えば、図または表へのテキスト参照）などの、様々な制約を受けることがある。図や表などの、１つまたは複数の追加的なタイプのコンテンツが含まれる場合、望ましいページネーションを見つけることは難しいことが多い。
【０００７】
最適なページネーションを得るには、個別ページの適切なセットのそれぞれについて、成功の尺度（measure of success）を定義しなければならない。ページネーションは「最適なサブプロブレム（optimal subproblem）」プロパティを有しており、したがって、動的プログラミングによって解決可能である。ｎページの任意の最適解（optimal solution）は本質的に、ｎ−１ページの最適解を含むであろう。一般には、動的プログラミングページネータ（dynamic programming paginator）は、空の解集合（empty solution set）で開始し、サブプロブレム（例えば、個別のページのサブセット）を増分的に追加して解決し、適切な１組の個別ページを見つける。さらに、動的プログラミングページネータは、各サブプロブレムのスコア（例えば、所定のメトリック（metric）に基づく成功の尺度）のテーブル、および最適解の前のサブプロブレムに戻るポインタを保持する。新しいサブプロブレムは、新しいサブプロブレムに適切に先行し得る最良スコアを有する前のサブプロブレムのテーブルをスキャンすることによって、評価される。したがって、動的プログラミングページネータは、新しい各サブプロブレムのあり得る先行サブプロブレムのそれぞれを評価する。残念なことに、評価すべき新しい各サブプロブレムについてかなりの数の先行サブプロブレムが存在することがあり、大部分は新しいサブプロブレムの有効な先行サブプロブレムとして適してもいない。それゆえ、動的プログラミングページネータは、使用不可能な先行サブプロブレムの評価を非効率的に行い、したがって、ページネーションの速度を低下させる。
【０００８】
さらに、今日のコンピュータ環境では、装置およびディスプレイは、フォーム（form）と縦横比の両方において急速に発展している。コンテンツおよび情報は、小さなリストディスプレイ（wrist display）、ポータブルハンドヘルドデバイス、デジタルファブリック、ワークステーション、さらには大型の壁掛け式ディスプレイなどに入れられる。この傾向の一環として、パーソナルコンピュータが、重要な読み取り媒体（reading medium）として現れた。実際、画面上で読むことは、今日の社会における情報収集の重要な形となっている。
【０００９】
しかし、ウェブ用の文書をデザインする現在の方法、または劇的に異なるディスプレイサイズおよび形状を有するこれらの装置の多くは、多くの種類の表示によって提供される新しい動的なリアルエステート（real estate）を効率的に使用するには至っていない。ほとんどのウェブフォーマットは、複数のディスプレイにわたってはうまく働かない。これは一つには、画面の読みやすさに対する静的な印刷ベースのデザイン媒体の影響のためである。非常に多くの情報が印刷の形式で入手可能であり、良い文書デザインの利点および重要性は、印刷の世界では、それが見る者の注意を引き付けて保つので、コミュニケーション、読みやすさ、市場性を助けるものとしてよく知られている。良質のグリッドベースのデザインは、印刷では一般的なものであるが、オンライン文書においては普及していない。したがって、画面サイズ、比率および方向についてのディスプレイ特性を考慮する新しいマルチレベルデザインの概念（multi-level design concept）を探求する必要がある。
【００１０】
インターネットによって、多くの異なるソースからの情報から文書を組み立て、単一画面上にそれを一緒に表示することが非常に容易になる。検索エンジンおよびニュースアグリゲータ（news aggregator）は、これを行い、その結果をＨＴＭＬウェブページとして表示する。しかし、それよりむしろ、印刷で一般に見られる高品質のデザインに劣らないよくデザインされた魅力的な方法でこれらの結果を表示することが好ましい。以前の取組み（earlier work）により、異なる表示条件に適応するグリッドベースのデザインを表示することが可能となったが、そのデザインが、異なるコンテンツに必ずしもうまく移るとは限らず、また作成することはひどく困難であった。
【００１１】
したがって、以前の取組みにより、ユーザが、異なるウィンドウ寸法に適応するグリッドベースの文書レイアウトをデザインすることが可能となったが、文書レイアウトは、作成して維持するのが難しい低水準言語で指定されていた。例えば、「スタイル（style）」は、それぞれが特定のコンテンツの集合を指定された画面サイズの範囲で表示することができる、制約ベースのテンプレートの集合となるようにデザインされ得る。文書ウィンドウがサイズ変更された場合、テンプレートの制約システムは、別のテンプレートが使用された時点で閾値と交差するまで、各表示エレメント（display element）をサイズ変更する。しかし、以前のシステムの目的は、文書スタイルが複数の文書に再使用可能なものとすることであった。これはある程度は正しかったが、実際には、図の寸法が元のデザインで使用されたものと著しく異なる場合は、多くのレイアウトの見栄えがよくないことが分かっていた。視覚的エレメントのどんな組合せも処理することができる強固なスタイル（robust style）をデザインすることには、エレメントの可能な組合せ、およびエレメントの変形体のそれぞれについて１つ、非常に多くのテンプレートをデザインすることが必要であった。
【００１２】
【非特許文献１】"Adaptive Grid-Based Document Layout" (AGBDL), Jacobs, et al. 2003
【発明の開示】
【発明が解決しようとする課題】
【００１３】
したがって、以前の適応文書システムにより、デザイナーが、異なる画面サイズおよびフォーマットに適応する文書を構築することが可能となったが、２つの重大な問題があった。第１に、新しいデザインを作成することと既存のデザインを修正することの両方を行うように、実際の文書レイアウトで作業することは、非常に難しいことであった。第２に、文書レイアウトは、出版の前にデザイナーまたは編集者によって修正されなければ、異なるコンテンツ選択にあまりうまく適応していなかった。
【００１４】
印刷媒体のレイアウトは、デザイナーおよび編集者がレイアウトとコンテンツの両方を変更することによって最終製品をカスタマイズするという利点を有する。単一の静的なデザインテンプレートは、ページ上のデザインエレメントのほとんどが同じものであっても、タイトルまたは見出しが異なる長さでグラフィックスが異なる寸法である様々なタイプのコンテンツにとって、見栄えが非常によい可能性は低い。この性質のマルチレベルデザインの主な課題の１つは、レイアウト内のあらゆるものの見栄えがよいことを確かめて必要に応じてカスタマイズする編集者がいないので、品質のレイアウトを維持することであり、デザインは、コンテンツを表示する複数の方法に対処し、任意の時点においてどの方法が最良か区別できなければならない。
【課題を解決するための手段】
【００１５】
以下に、特許請求された主題のいくつかの態様についての基本的な理解を提供するために、特許請求された主題の簡略化された要約を提示する。この要約は、本発明を広範な概観ではない。本発明の重要な／重大なエレメントを識別すること、本発明の範囲を定めることを意図するものではない。その唯一の目的は、後に提示されるより詳細な説明の序文として、特許請求された主題のいくつかの概念を簡略化された形で提示することである。
【００１６】
本明細書で開示され請求される、特許請求された主題は、その一態様では、多くの異なる表示条件およびコンテンツ選択に適応する豊富なグリッドベースのデザインおよび／または高品質レイアウトを簡単にデザインし表示することを容易にすることができるアーキテクチャを含む。上記内容を達成するために、レイアウトの制約を高水準で記述するテンプレートを使用することができる。これらのテンプレートは、レイアウトの柔軟性を向上させ、レイアウトが異なるコンテンツによりよく適応することを可能にする一方、作成し維持するのが遥かに容易なものとすることができる。同様に、表示することができるコンテンツのタイプを広げ、特にインターネット上の様々なソースから集約されたコンテンツに焦点を当てることによって、このアーキテクチャの適用性を、以前のシステム（例えば非特許文献１）よりも向上させることができる。
【００１７】
特許請求された主題の一態様によると、テンプレートを、理解し使用するのが容易な高水準構成体（high level construct）で定義することができる。したがって、テンプレートをデザインおよび／または維持するタスクは、広範な技術的背景をもたないグラフィックデザイナーにとって実用的である可能性がある。さらに、結果として生じるデザインは、他のデザイナー、テンプレートの作成を手伝わなかった者でも容易に理解し維持することができる。作成されたテンプレートは、様々なウェブベースのソースから得られる静的な文書と動的な文書の両方に使用することができる。テンプレートは、例えば複数層のコンテンツを有する文書を作成することができるマルチレベルデザインレイアウトにも同様に使用することができる。
【００１８】
別の態様によると、結果として生じる文書レイアウトは、高品質レイアウト（例えば「見栄えがよい」レイアウト）とすることができ、異種タイプのコンテンツを使用しながら、その見た目（visual appeal）を異なる表示サイズに保つことができる。高品質レイアウトを、意味の流れ（semantic flow）、ブランドアイデンティティ（brand identity）、イメージとテキストの相関性（item and text correlation）、および広告テーマなどを損なわないようにデザインすることができる。
【００１９】
特許請求された主題の別の態様によると、テンプレートは、多くのテンプレートをデザインし維持する必要なしに、集約された文書内で見られる多種多様のコンテンツを処理できるほどに柔軟なものとすることができる。より正確に述べると、単一のテンプレートが、エレメントおよび／またはコンテンツについての複数の可能な構成を定義して、柔軟なデザインを提供するのに必要なテンプレートの数を大幅に減らすことができる。さらに、高水準で記述されたテンプレートを、他のシステムによって使用される低水準の制約に変換することができる。アーキテクチャは、適応文書内の共通の振舞い（behavior）を実装する制約システムを、各デザイナーにそれを手作業でコーディングするように求めるのではなく、自動的に提供することができる。
【００２０】
さらに、アーキテクチャは、表示されるべき正確なコンテンツが知られていない場合でも、異なる画面サイズに適応する高品質文書レイアウトをグラフィックデザイナーが容易にデザインすることを可能にすることができる。さらに、文書の概念を拡張し、統一フォーマット（uniform format）ではない可能性が高い外部ソースへの参照を含めることができる。したがって、このアーキテクチャは、複数のソースから集約され、またデザイン時には知られていない可能性があるコンテンツを処理できるほどの柔軟性を有する高品質のグリッドベース適応デザインに基づいてマルチレベルのデザインアーキテクチャを作成することを、容易にすることができる。
【００２１】
上記内容および関連の目的を達成するために、特許請求された主題の特定の例示的な態様について、以下の説明および添付の図面に関連して本明細書に述べる。しかし、これらの態様は、本発明の原理を使用することができる様々な方法のほんのいくつか示すものであり、特許請求された主題は、このような態様およびその等価物すべてを含むことが意図されている。本発明の他の利点および新規な特徴は、図面と併せて考慮されるときに、本発明についての以下の詳細な説明から明らかになる。
【発明を実施するための最良の形態】
【００２２】
特許請求された主題について図面を参照して述べるが、図面では、同じ参照符号を使用して、全体を通して同様のエレメントを指す。以下の記載では、説明の目的のため、多くの特定の詳細を、本発明の完全な理解を提供するために説明する。しかし、特許請求された主題を、これらの特定の詳細なしに実施することができることは明らかである。他の場合では、特許請求された主題の説明を容易にするためによく知られている構造および装置をブロック図の形式で示す。
【００２３】
本出願で用いられる際、「コンポーネント」および「システム」という用語は、ハードウェア、ハードウェアとソフトウェアの組合せ、ソフトウェア、または実行中のソフトウェアのいずれかのコンピュータ関連のエンティティを指すことが意図されている。例えば、コンポーネントは、限定されるものではないが、プロセッサ上で実行するプロセス、プロセッサ、オブジェクト、実行可能ファイル、実行スレッド、プログラム、および／またはコンピュータとすることができる。例として、サーバ上で稼動しているアプリケーションとサーバの両方ともコンポーネントとすることができる。１つまたは複数のコンポーネントは、プロセスおよび／または実行スレッド内に存在することができ、コンポーネントを、１つのコンピュータに局所化すること、および／または２つまたはそれ以上のコンピュータ間で分散することができる。
【００２４】
本出願で用いられる際、「デザイン」または「レイアウト」という用語は一般に、コンテンツが文書内にどのように配置されるかを指す。本明細書で使用される場合、デザインとレイアウトは、実質的に置き換え可能なもの（interchangeable）とすることができる。例えば、文書デザインと文書レイアウトの両方とも、コンテンツが文書内にどのように配置されるかを指すことができる。
【００２５】
本出願で用いられる際、「高水準（high level）」というフレーズは一般に、低水準言語または構成体よりもよりユーザフレンドリであり、いくらかプラットフォーム非依存のものとすることができるプログラミング言語またはプログラミング構成体を指す。高水準構成体は、別のやり方では操作の実装に必要である複雑性を回避するために低水準操作への抽象化を提供することができる。一般にアセンブリ言語、ならびに純粋なＨＴＭＬ（Hyper Text Markup Language）および他の「緩い（loose）」コーディングフォーマットは、低水準と見なされ、拡張可能スタイルシート言語変換（ＸＳＬＴ：Extensible Stylesheet Language Transformation）を適用した後の出力フォーマットは、高水準と見なされる。
【００２６】
本明細書で用いられる際、「高品質（high quality）」という用語は、現在のディスプレイ寸法および現在のコンテンツが与えられて、結果として生じる出力が見栄えがよいと判断されることを意味する。高品質とは、レイアウト、デザイン、または特定のコンテンツが挿入されるレイアウト内の特定の位置について言及することができる。例えば、高品質レイアウトは、現在のコンテンツを有する現在の表示寸法で見栄えがよいと判断されるレイアウトであり、高品質位置は、全体的なレイアウトまたはデザインの高品質の特徴（character）を維持しながら、特定のコンテンツを取り入れることができる位置である。レイアウトまたは位置の高品質の特徴は、意味の流れ、ブランドアイデンティティ、イメージとテキストの相関性、広告テーマなどを損なわないことなど、追加の条件も同様に満たすことを必要とすることがあることを理解されたい。これらの追加の条件は、非矩形（non-rectangular）のテンプレートおよびエレメント、カラムのバランス調整（column balancing）、分割不可能な段落およびアトミックサブ文書（atomic sub-document）、ならびにインタラクティビティなど、後述の検討に基づくことができることも理解されたい。
【００２７】
本明細書で説明される実施形態は、ウェブベースの集約データの適応表示のためのシステム、および適応グリッドベースの文書レイアウトシステム（ＡＧＢＤＬ：Adaptive Grid-Based Document Layout）のテンプレート改良に関する。インターネットコンテンツを集約し、ＡＧＢＤＬを使用してそれを表示するためのシステムを提供し、このシステムにより、異なるディスプレイサイズに自動的に適応することができる広範囲の高品質な視覚フォーマットでデータを表示することが可能になる。このシステムは、限定ではないがＲＳＳニュースフィード、インターネット検索エンジンの結果、ＭＳＮ  Ｎｅｗｓｂｏｔなどのインターネットニュースアグリゲータバックエンド、新聞や雑誌などのコンテンツウェブサイトから直接「スクラップされた」コンテンツを含む、複数のコンテンツソースのいずれかを使用することができる。これを、以下でも詳述される元のＡＧＢＤＬの作業（work）で説明されるように、文書の概念を拡張することによって行うことができる。
【００２８】
本アーキテクチャは、複数の別個の文書からなり、かつ親文書（parent-document）と組み込みサブ文書（embedded sub-document）のマルチレベル階層に配置され得る文書を、サポートすることができる。それぞれのコンポーネント文書を、固有ソースと外部ソースの組合せで構成することができ、この外部ソースをロード時に、個々の各ソースについて指定することができるＸＳＬＴ変換を通じて、あるいはウェブスクレーパー（web-scraper）または他の何らかのデータ収集もしくは処理エージェントとすることができるヘルパープログラムのいずれかを通じて、システムの固有文書フォーマットに変換することができる。外部ソースを、文書の複数のレベルで指定することができる。外部ソースを、文書全体（最上位レベルまたはサブ文書）として、文書内の特定のコンテンツストリームとして、または特定のコンテンツストリーム内の単一のコンテンツアイテムとしてロードすることができる。さらに、外部ソースを、文書内に完全に、または部分的に含むこともできる。例えば、単一のコンテンツストリームを、変換後に所与のソースから選択的にロードすることができる。
【００２９】
このサポートでは、文書スキーマは、ＡＧＢＤＬ文書が上述の方法で外部ソースを参照することが可能となるように拡張されている。文書が解析されロードされると、指定された任意のサブ文書または他の外部コンテンツを（必要であれば）変換し、次いで再帰的に解析し、ロードすることもできる。サブ文書は、それ自体で完全なＡＧＢＤＬ文書として定義され、同封文書内のサブテンプレートとして使用される自己の表示テンプレートのセットを参照する。表示時に、サブ文書は、文書がレンダリングされるべき画面領域に渡される。サブ文書は、再帰的にページネートし、次いで、所与のウィンドウ内で最上位レベルの文書であるかのように、所与の領域にそれ自体をレイアウトする。サブ文書を、任意の他のコンテンツと同様に親文書のテンプレートを使用して親文書内に表示することができるので、サブ文書を、同封文書内のデータとしてロードされる他の外部コンテンツとは異なるものとすることができる。
【００３０】
（以下で詳述される）ＡＧＢＤＬシステム内の適応テンプレートに関して、下記の内容に関連する拡張が提供される。すなわち、高水準のテンプレートデザイン、拡張テンプレート適応性（コンテンツに適応するテンプレート）、ならびにテンプレートパラメータおよび出力に関連する拡張である。これらのカテゴリの３つすべてが、「文書スタイル」を作成することおよび維持することを容易にすることができる。スタイルを、文書をレンダリングすることができるレイアウトの範囲をともにカバーするテンプレートの集合として定義することができる。
【００３１】
高水準のテンプレートデザインは、各表示エレメントの寸法および位置、ならびにエレメントの表示特徴、他の表示エレメントとの関係、および適応型の振舞い（adaptive behavior）を制御する個々の制約を含めて、低水準の詳細を生成するシステムによって解釈される高水準構成体を使用して、制約ベースのテンプレートを指定することを可能にすることができる。
【００３２】
従来的に、ＡＧＢＤＬシステムなどでは、テンプレートを、各テンプレートに生じる各表示エレメント、制約、および属性を記述するＸＭＬコードを書くことによって指定する必要があった。テンプレート作成ツール（template authoring tool）は、ＧＵＩインタフェースを介してテンプレートを書くことおよび修正することを（恐らく）より容易にしたが、作成者には、この他の方法を介して同じ詳細のすべてを指定することが依然として求められていた。
【００３３】
本革新技術により、適応カラムグリッドおよびエレメント間の相対的関係などの、高水準構成体を使用する文書仕様（document specification）を可能にすることができる。カラムグリッドを、比例カラム幅と絶対カラム幅の組合せを使用して定義することができ、どのカラムが任意の所与のページ幅でインスタンス化されるかを制御する規則を指定することができる。次いで、表示エレメントを、１つまたは複数のこれらのカラム、あるいはこれらのカラムの部分にまたがって配置することができ、例えば「ｏｖｅｒ」および「ｕｎｄｅｒ」割当てを通じて他のエレメントに関連付けることができる。単一のステートメントは、ロード時に多くの低水準制約が自動的に生成されるパラメータの集合を指定または示唆することができる。追加の制約を生成するために使用されるマージンおよびパディングなどのエレメントの属性を確立する他のパラメータを指定することができる。
【００３４】
文書またはページは、多くのパラメータ値を共有するテキストの複数のカラムなど、類似の表示エレメントの集合を含むことが多い。特許請求された主題の態様は、エレメントを一回記述し、次いで複数回インスタンス化することを可能にすることができる。それぞれのインスタンスは、位置情報など、その詳細のサブセットをオーバーライドさせることができる。さらに、記述言語は、特定のエレメントに関するすべての制約を、ユーザがテンプレートを理解し維持するのを容易にするエレメントの記述内に含むことができるように、再編成される。
【００３５】
拡張テンプレートの適応性（extended template adaptability）は、個々のテンプレートそれぞれが広範囲の表示寸法および文書コンテンツをカバーすることを可能にすることができる。以前は、それぞれのテンプレートは、表示エレメントの固定のセットを有しており、コンテンツの特定のセットを必要とし、エレメントは、制約システムを通じてページ寸法の範囲をカバーするように構成されていた。ページ上の図の数などの異なるコンテンツの組み合わせ（assortment）のそれぞれは、異なるテンプレートを必要としていた。横長の縦横比を有する図は、縦長の縦横比を有する図とは異なるテンプレートを使用していた。潜在的に異なる縦横比または解像度を有するページで複数の図に対処するには、コンテンツストリーム内に様々な順序で現れる図のタイプのあり得る組合せに対処するためのさらなる数のテンプレートが必要であった。単一のテンプレートも、元のシステムでは固定数のカラムを有し、ページが保有する可能性がある各カラム数について、図のタイプのあり得る順列（possible permutation）のすべてを対処する新しいテンプレートを必要としていた。柔軟な「スタイル」に必要なテンプレートの総数は、テンプレートが適応するあり得る寸法が増加するにつれて急激に増加し、広く適用可能なスタイルの生成を扱いにくいものとし、そのメンテナンスを非常に難しくしていた。
【００３６】
このテンプレート定義は、これらの問題に対応する複数の新しい特徴を有する。オプションのエレメントは、異なるコンテンツ選択を単一のテンプレートによって対処することを可能にすることができる。エレメントは「Ｏｒ」グループへと組み合わせることができ、この「Ｏｒ」グループは、テンプレートが、そのテンプレートが使用される度に１組の可能性のある選択肢から１つのエレメントだけをインスタンス化することを可能にすることができる。Ｏｒグループは、最良適合（Best-Fit）、第一適合（First-Fit）、第一良好適合（First-Good-Fit）および類似のアルゴリズムを含め、所与のレイアウトでどのエレメントを選択するか決定するためのいくつかののアルゴリズムの１つを使用することができる。
【００３７】
さらに、新しいテンプレートは、可変数のカラムを有することができる。上述のカラム定義は、特定のページ閾値に基づいて適応カラムを包含するための規則を含むことができ、あるいは閾値は、最小のカラム幅に基づいてアーキテクチャのコンポーネントによって計算することができる。どのカラムを特定のページサイズでインスタンス化するかを制御するカラム優先度（column priority）を指定することができる。特定のページ幅で使用されないカラムは、制約システムによってゼロ幅に縮小する（collapse）ことができ、その結果、それらにまたがるエレメントは、幅を減少されるか、またはそのページサイズでは完全に除去される。同時に、オプションのエレメントおよび適応カラムグリッドは、テンプレートの数、および関連するメンテナンスを劇的に減らすことができる。
【００３８】
テンプレートシステムへの別の拡張は、親テンプレートと、その内部にレイアウトされたサブテンプレート（sub-template）との間で前後にパラメータを渡すことを可能にすることができる。パラメータ、および戻り値を、任意の他の制約値（constraint value）と同様にエレメントによって参照できるように、受信テンプレートの制約キャッシュ内に置くことができる。これらのパラメータを用いて、例えば、サブテンプレート内のカラム数を設定し、オプションのエレメントの包含または除外のフラグを立て、あるいは図を子の中に表示する方法を制御することができる。サブテンプレートに渡されたパラメータは、即時値（immediate value）とすることができ、あるいは呼出し時に評価することができる親テンプレートのシステム内の制約とすることができる。
【００３９】
親文書は、子の中で使用される活字組み（typesetting）の詳細の多くを直接に制御することができるので、同様に、スタイルシートを、パラメータとしてサブテンプレートに渡すことができる。返されたパラメータは、図の最上部および下部がどこに位置するか、または見出しまたはタイトルがどこで終了するかなど、子のレイアウトについてのほかの隠れた詳細を、親テンプレートに知らせることができる。次いで、親は、他の表示エレメントをサブテンプレートの特徴に位置合わせすることができ、または別個のサブテンプレート内の２つの無関係な図を隣り合わせに置かないことを保証することができる。
【００４０】
当業者であれば理解されるように、特に、上述されるような階層複合文書（hierarchal compound document）を表示するためのテンプレートの能力を増す他の改良物がある。例えば、「Ａｎｄ」グループは、エレメントの集合が、単一のコンテンツアトム（content atom）から取り込む（consume）ことを可能にし、文書のレイアウトおよび編成にさらなる柔軟性をもたらす。これによって、例えば、写真特集を個々のニュース記事から取り出し、記事の残りとは別のエレメント内の新聞の第１面に表示することを可能にすることができる。別の特徴は、以前のシステムによって渡される矩形の境界ボックス（bounding box）ではなく、ホスト側のエレメントのＧＤＩ（Graphical Display Interface）領域を、エレメント内で使用されているサブテンプレートに渡すことができる。この態様は、サブテンプレートが、親テンプレート内のオーバーラップするエレメントの周りにそのテキストを流し、またはピクチャを表示するためにＯＲグループから、遮断されていないエレメントを選ぶことを可能にすることができる。
【００４１】
上述されるように、他の実施形態は、固定サイズ選択肢の集合を含め、各カラムに望ましいサイズの特定の範囲など、カラムグリッドの望ましい振舞いを記述するためのより強力な方法を容易にするテンプレート指定のための高水準構成体を提供することができる。さらに、例えば自動的に生成されたマージンを使用して、過剰制約（over-constrained）および過小制約（under-constrained）状況を解決するために、優先度を指定することができる。実施形態は、異なる規則およびヒューリスティック（heuristics）に従うがカラムに類似する自動生成される垂直グリッド、個々のグリッドカラムを分割する適応サブグリッド、および異なるグリッドによって制御されるエレメントの異なる集合を有するレイアウトを可能にする追加的な最上位レベルのグリッドをサポートすることができる。個々のエレメントを、複数回インスタンス化することができ、すべてを一緒に複数回インスタンス化することができるエレメントのグループを構築できることが意図されている。
【００４２】
オプションエレメント（およびエレメントのＯＲグループ）の存在下で一貫した制約システムを指定することは急速に、非常に複雑で厄介なものとなる可能性があり、正確なシステムを作り出すための構成体を開発し、所望の結果についての記述が与えられたテンプレートにそれを自動的に構築することも企図されている。
【００４３】
さらに、エンドユーザがコンテンツを見るときに個々の表示エレメントをサイズ変更することを可能にすることによって、適応表示レイアウト（ＡＤＬ：Adaptive Display Layout）文書にさらなるインタラクティビティを追加すること、またはエレメント内に新しいデータを追加すること、ならびに存在するコンテンツに基づいて、より高度化した方法を使用して所与のサイズでいずれのカラムを含むか選択するように適応カラムカウントの振舞い（adaptive-column-count behavior）を拡張することも意図されている。これは、カラムに関するあり得る選択のそれぞれをレンダリングし、レイアウトスコアに基づいて最良のものを選択することを含む可能性がある。
【００４４】
簡潔に上述されるように、一態様によると、特許請求された主題は、従来のＡＧＢＤＬ文書システムを３つの一般的な方法で拡張することができる。第１に、テンプレートシステムが改良され、テンプレートをより強力にし、さらに広範なコンテンツ範囲をカバーするのにはるかに少ないテンプレートのみを必要とし、それと同時に、テンプレートを書き維持することが容易になった。さらに、文書定義は、文書が複数の位置からコンテンツを収集し、また個々の文書について親および子文書の階層に組み立てられることを可能にするように、拡張された。最後に、レイアウトエンジン（例えば、ＡＧＢＤＬシステム内の低水準エンジン）は、新しい領域にしばしば特有の新しい特徴についてのサポートを提供するように更新された。次に、これらの拡張、および特許請求された主題の他の態様について述べる。
【００４５】
（テンプレート）
テンプレートについて３つの主要な態様がある。第１に、テンプレートを作成し、理解し、維持することを容易にする高水準言語を使用して、テンプレートを指定することができる。第２に、テンプレートは、全てのあり得る変形体、および単一レイアウト内のコンテンツの変形体の組合せについて別個のテンプレートを必要とするのではなく、使用可能なテンプレートに適応可能なものとすることができる。第３に、テンプレートは、より大きい範囲の画面寸法に拡張し、書かれ維持されるべき類似のテンプレートの数を減少させる能力を有することができる。
【００４６】
ＡＧＢＤＬシステム内のテンプレートは、非常に低水準な言語で書かれていたので、書くことや理解することが非常に難しかった。個々の制約それぞれが明示的に指定され、ページ上の全てのエレメントについて多くの制約が必要とされていた。可変数のカラムなど高度化した適応（sophisticated adaptation）のための制約システムは、書くことが極めて難しく、また、別の作成者のテンプレートを解読することは、あまりにも難しいことであった。テンプレートデザインツールは、テンプレートデザイン用のＧＵＩを提供したが、それはたいてい低水準のサポートを提供したにすぎず、ほとんどの制約が独立に設定されることを依然として必要としていた。さらに、その出力は理解することや編集することが非常に難しく、ツールの能力を超えてデザインをカスタマイズすることを難しくしていた。
【００４７】
一実施形態によると、特許請求された主題は、高水準構成体の固有の長所（native strength）を利用するテンプレートを使用し、したがってより強力なビルディングブロックをテンプレート言語自体に含む。新しい言語の高水準のプリミティブ（primitive）を、テンプレートをシステムによってロードするときに基本構造（basic structure）にコンパイルすることができ、あるいは更新されたレイアウトエンジンによって直接読むことができる。制約システムの多くの部分は、新しいプリミティブから推測することができ、自動的に生成される。このシステムは、よく知られている有用なタスクのために、複雑な制約システムを自動的に生成することもできる。
【００４８】
（高水準テンプレート記述）
元のＡＧＢＤＬシステムと、特許請求された主題の両方は、ＸＭＬ文書として定義することができる。元のシステムでは、テンプレート記述は、セクションに編成されていた。すべてのエレメントは、親の＜ｅｌｅｍｅｎｔｓ＞ノード内の＜ｅｌｅｍｅｎｔ＞ノードによって記述され、すべての制約は、親の＜ｃｏｎｓｔｒａｉｎｔｓ＞ノード内の＜ｃｏｎｓｔｒａｉｎｔ＞ノードによって記述されていた。高水準テンプレートは、２つのセクションを保持することができ、作成者が任意のエレメントノード内に制約を代替的に定義することを可能にすることもできる。この柔軟性により、テンプレートが、特定のエレメントをそのエレメントで直接に記述する制約をグループ化し、一般セクション内にグローバル制約（global constraint）を置くことが可能になる。
【００４９】
作成者にそれぞれの制約を個々に指定することを求めるのではなく、親に適用するいくつかの個々の制約を暗黙的に定義するためにエレメントノードの下に置くことができる複数の子ノードを定義することがでる。例えば、マージンおよびパディングを、以下の例に示される属性の一部を含む単一ノードを有するエレメントについて指定することができる。
【００５０】
【表１】
2009510650.tif 000003
【００５１】
特定の割当ては典型的に、より一般的な割当てを常にオーバーライドする。属性によって定義されない値はいずれも、ゼロと見なすことができる。作成者は、属性を、即時値、または他の制約を参照する表現に割り当てることができる。エレメントのサイズ調整および配置を制御する制約は、あり得る属性のサブセットを再び使用して、単一の位置ノード（location node）で指定することができる。位置ノードの解析後にノードが過小制約を受ける場合、通常エラーが生成される。
【００５２】
以下の例に示されるように、「ｏｖｅｒ」および「ｕｎｄｅｒ」属性を使用して、他のエレメントの位置に基づいてエレメントを割り当てることができる。例えば、「ｏｖｅｒ」属性は、現在のエレメントの最上部を名前付きエレメントの最下部と位置合わせし、「ｕｎｄｅｒ」属性は、エレメントの最下部を名前付きエレメントの最上部と位置合わせする。
【００５３】
【表２】
2009510650.tif 000004
【００５４】
文書を粗いカラムグリッドに分割することは一般的である。文書の幅が変化する際に、ほとんどのカラムが適応するために使用する可能性の高い振舞いは、ほんのわずかしかない。例えば、カラムは、ページが広がるにつれてすべて等しく大きくなり、ページが狭まるにつれて等しく小さくなる。カラムは、ある固定の比率に従って大きくまたは小さくなることもある。代替的にまたは追加的に、いくつかのカラムは固定幅のままで、一方他のカラムはサイズ変更するか、あるいは、余分な幅がガターおよびカラムの周りのマージンに吸収されることがある。テンプレート言語は、上記に列挙された振舞いの組合せ、さらには他の可能性ある振舞いまたは所望の振舞いの組合せを使用して適応するグリッドを定義するツールを含むことができることを理解されたい。特許請求された主題の態様は、カラムについて定義された振舞いを実装するのに必要な制約システムを自動的に生成することができる。例えば、テンプレートデザイナーは、以下の例のように、メンバカラムの数およびデフォルトの振舞いを定義する＜ｇｒｉｄ＞ノードを作成することができ、次いで、任意の数のカラムノードを、個々のカラムについて代替の振舞いを定義することができるグリッドノードの下で作成することができる。
【００５５】
【表３】
2009510650.tif 000005
【００５６】
上記のグリッドノードは、４カラムのカラムグリッドを定義することができる。最初の３つのカラムは、ページに比例して増加するように定義され、第２のカラムは、他の２つの各カラムの３倍の幅であり、第４のカラムは、２００ピクセル幅に常に固定された（fixed）ままである。グリッドノードが解析されると、例えば「ｍａｉｎｇｒｉｄ．ｇｒｉｄ０」から「ｍａｉｎｇｒｉｄ．ｇｒｉｄ４」までの名前が付けられたグリッド線を定義する制約を作成することができる。ページ幅が変化するとグリッド線のそれぞれを配置する制約システムを、自動的に生成することができる。例えば「ｍａｉｎｇｒｉｄ．ｃｏｌｕｍｎｌ．ｒｉｇｈｔ」、「ｍａｉｎｇｒｉｄ．ｃｏｌｕｍｎｌ．ｌｅｆｔ」などの名前が付けられたグリッド線に関連してカラムを定義することによって、さらなる制約を作ることができる。テンプレート作成者は、エレメントを定義する制約の中でこれらの名前を直接参照することができ、そうでない場合は、「カラム」属性を、以下の例の後者の２つで行われるように、左右の制約を示唆する位置ノード内に置くことができる。
【００５７】
【表４】
2009510650.tif 000006
【００５８】
第２の位置カラム（location column）の例の中のダッシュ（「−」）はここでは、エレメントがカラム２とカラム３の両方にまたがることを示す。１つのグリッドだけが定義されている場合、上記の第２の例で行われるように、名前プレフィックス（name prefix）は、カラム名およびグリッド名から省くことができ、それらは、単一のグリッドを指すと見なされることとなる。個々のカラムに加え、カラムのスパン（span）を使用することができる。追加的な制約を、エレメントを位置決めするのに使用することができる各カラムについて作成することができる。これらの制約には、限定ではないが、「ｃｏｌｕｍｎ．ｗｉｄｔｈ」および「ｃｏｌｕｍｎ．ｃｅｎｔｅｒ」、ならびに分数のカラム線「ｃｏｌｕｍｎ．１ｔｈｉｒｄ」、「ｃｏｌｕｍｎ．２ｔｈｉｒｄ」、「ｃｏｌｕｍｎ．ｌｑｕａｒｔｅｒ」などが含まれる。
【００５９】
マルチカラムページ上のテキストカラム、ディバイダのグラフィックス（divider graphics）および図エレメントなど、ほとんどのプロパティではなくとも多くのプロパティを共通に共有する多くの類似のエレメントをページ上に有することは、一般的である。単一の＜ｅｌｅｍｅｎｔ＞ノードの下に複数の＜ｌｏｃａｔｉｏｎ＞ノードを置くことによって、エレメント定義を再使用することができる。それぞれの位置ノードは、追加ノードの属性でサイズ調整されて位置決めされる親エレメントの新しいインスタンスを作成することができる。エレメント名は、位置ノードが現れる順序で割り当てられ、インスタンスを制約表現内で区別することができるように名前を付加される、１−ベースのインデックス（1-based index）を有することができる。
【００６０】
制約が、複数のインスタンス化を伴うエレメント内で定義されると、それぞれのインスタンスが各制約について一意の名前を使用することが必要となることが多い。マクロを利用可能にし、複数のインスタンス化を容易にすることができる。制約の名前または表現内に現れる文字列「！ＴＨＩＳ！」は、その時に処理されているインスタンスの名前を評価することができる。「！ＬＡＳＴ！」は、前のエレメントを評価することができ、それにより、エレメントをつなぎ、または積み重ねることが容易になる。名前をピリオド（「．」）で開始することは一般に、現在のインスタンスの名前がピリオドの前にあると見なす。
【００６１】
複数の位置ノードを使用することは、複製エレメント（duplicate elements）を作成する簡潔で効率的な方法であり得るが、いくつかのインスタンスの変形を可能にすることにも有用であり得る。例えば、いくつかの別の同一エレメントは、異なるｚ層（後述）の要件を有するか、あるいは異なるコンテンツストリームから取り込むことがある。この理由のため、エレメントノードに定義される任意のプロパティを、位置ノード内でオーバーライドすることができる。位置ノード上に属性を設定することによって、層またはスタイルＩＤなどの単一の値からなるプロパティを、オーバーライドすることができる。位置ノードの下に事前条件ノード（precondition node）を置くことによって、事前条件などのより複雑なプロパティを上書きすることができる。以下の例は、３回インスタンス化されたエレメントを示しており、プロパティは第２の２で上書きされている。
【００６２】
【表５】
2009510650.tif 000007
【００６３】
ＡＧＢＤＬシステムでは、単一のページ上にサポートされたカラムカウントのそれぞれについてテンプレートの新しいファミリーを作成することは一般的であった。テンプレートのファミリーは、ページ幅の範囲によって選択されていた。テンプレートの１つのカラムファミリーを、狭いページに使用することができ、ページ幅が所与の閾値を超えて増加すると、システムは、２つのカラムファミリーに切り換わる。それぞれのファミリーは、ページ上のコンテンツについての異なる組合せおよびその位置をカバーする複数のテンプレートを含む。これらのファミリー内のほとんどの視覚エレメントは、カラム数を除いては、同じであることが多い。
【００６４】
ファミリー間のこの類似は、ページ幅が変化するとカラムをサイズ変更するだけでなくページ上のカラムの数を変更することもできる適応グリッドを定義することによって、活用することができる。これは、＜ａｄａｐｔｉｖｅ＞ノードを、テンプレート内でグリッド定義ノードの下に置くことによって達成することができる。適応ノードが存在する場合、グリッドノード内のカラムカウントは、最大カラム数として機能することができる。適応ノード内に規則を置き、どのくらいのカラムが任意の所与のページ幅でアクティブ化されるかを判定することができる。規則は、例えば、ｍｉｎＣｏｌｕｍｎＷｉｄｔｈまたはｍａｘＣｏｌｕｍｎＷｉｄｔｈのいずれかを指定することができる。ｍｉｎＣｏｌｕｍｎＷｉｄｔｈ規則は、テンプレートに最大カラム数を使用するように指示することができ、典型的にこのカラムはすべて少なくとも所与の閾値の標準幅を有する。カラムは、異なる比例サイズを有することがあるので、それぞれのカラムの実際のサイズを、最小および／または最大の幅をチェックするときにカラムの比例値で割ることができる。
【００６５】
作成者は、任意のまたは全てのカラムに、ページ幅がすべてのカラムを含むほど十分に広くない場合にカラムが除去される順序を制御する優先度を与えることができる。優先度が指定されない場合は、デフォルト優先度を適用することができる。例えば、デフォルト優先度を設定し、カラムを右から左に除去することができる。異なる優先度を割り当てるために、作成者は、グリッド定義ノードに、カラムの左から右へと割り当てる優先度値のカンマ区切りリスト（comma-delimited list）と共に優先度属性を含めることができる。あるいは、作成者は、グリッド定義のカラム定義ノードに優先度属性を含めることができる。優先度は典型的に、整数値である。所与のページレイアウトでは一般に、アクティブなカラムの数以下の優先度値を有するカラムのみが含まれる。
【００６６】
適応カラムがテンプレートのインスタンス化から除去されると、制約システムは一般に、カラムをゼロ幅に縮小する。レイアウト時にゼロ幅を有するエレメントは典型的に、コンンテンツを取り込まず、またはテンプレートスコアに寄与しない。エレメントが複数カラムにまたがる場合、そのエレメントは、任意の所与のレイアウト内でアクティブなカラムまたがるように見えるだけの可能性が非常に高いであろう。
【００６７】
デザイナーは、適応カラムを有するページの左端または右端のカラムにエレメントを置きたいことがあるであろう。これを容易にするために、位置ノードは、カラム属性内で特別なキーワード、例えば「ｌｅｆｔｍｏｓｔ」および「ｒｉｇｈｔｍｏｓｔ」を認識することができる。
【００６８】
（コンテンツへのテンプレート適応）
テンプレートは、それぞれ異なるコンテンツ構成に複数の方法で適応することができる。ＡＧＢＤＬテンプレートは、その上に配置された複数の事前条件を有することがあり、この事前条件は、それぞれのテンプレートが使用され得る厳密なコンテンツ要件（precise content requirement）を含む事情（circumstance）を示す。対照的に、特許請求された主題の態様は、テンプレート全体に加えて、テンプレート内の個々のエレメント上に事前条件を配置することを可能にすることができる。これらのエレメント事前条件は、使用可能なコンテンツ、表示条件、またはシステム内の任意の他の制約に応じて、エレメントを、条件付きでレイアウト内に含めることを可能にすることができる。オプションのエレメントが使用されないときに、テンプレートの客観的スコア（objective score）にペナルティを課す（penalize）ことが有用なことがある。例えば「ｅｌｅｍｅｎｔ−ｎａｍｅ．ａｃｔｉｖｅ」という名前の特別な制約値を、あらゆるエレメントについて、テンプレートの制約システムに自動的に追加することができる。ｅｌｅｍｅｎｔ−ｎａｍｅ．ａｃｔｉｖｅの値は、例えば、エレメントがレイアウト内に含まれるときには１に、エレメントが含まれないときには０に設定することができる。この制約値をテストして、テンプレートの客観的スコアの判定において任意のエレメントの存在を考慮することができる。エレメントノード上に設定された事前条件は一般に、エレメントのすべてのインスタンスに適用する。事前条件ノードを位置ノード内に配置して、さらなる事前条件を追加するか、またはエレメントノード上に設定されたいずれかをオーバーライドすることができる。
【００６９】
エレメント事前条件は、複数のエレメントを個々に制御することを可能にすることができるが、エレメントの制御を結び付けることにも有用であることが多く、複数のエレメントを一緒に、いくつかの構成体にグループ化することができる。ＡＮＤグループは、いくつかのエレメントを単一の事前条件のセットによって制御することを可能にすることができる。同様に、ＯＲグループは、複数のレイアウトエレメントを定義することを可能にすることができ、その１つのみがテンプレートの任意のインスタンスに含まれることとなる。いくつかのオプションおよび／またはアルゴリズムをサポートして、複数のオプションがあり得る場合に、使用するインスタンスを決定することができる。第一適合のアルゴリズムは、すべての特定の事前条件が満たされるグループ内で第１のエレメントを使用することができる。最良適合アルゴリズムは、各グループメンバを評価することができ、最良の客観的レイアウトスコアを返すエレメントを使用する。第一良好適合アルゴリズムは、所与の閾値を超えたレイアウトスコアを返すグループ内の第１のエレメントを使用することができる。
【００７０】
作成者は、オプションのエレメントを有するテンプレートをデザインする場合に、エレメント間の制約関係が、有効なままであり、テンプレートの所与のインスタンス化に個々のエレメントのいずれかが存在するかどうかにかかわらず所望の結果をもたらすように注意すべきであることを理解されたい。固定サイズのエレメントは、インスタンス化されない場合はその寸法を保持することができるが、可変の高さエレメント、ｒｅｃｏｍｐｕｔｅＨｅｉｇｈｔ＝“ｔｒｕｅ”で定義されるエレメントは一般に、ゼロの高さにサイズ変更される。ＯＲグループの境界を定義する制約を、各レイアウトについて選択されるいずれのメンバエレメントの境界とも同じとなるように自動的に指定することができる。
【００７１】
別の態様によると、テンプレートをコンテンツに適応させる方法を提供することができる。この方法は、字体およびサイズのようなスタイル特性を特定のコンテンツに適応することに対応する。テンプレートがデザインされると、テキストのブロックのスタイルを表示エレメントに割り当てることができる。これは典型的には問題ではないが、新聞のページ上に見出しを表示することなどのいくつかの適用例では、テキストの外観はその有効性には極めて重要である。印刷される新聞では、ページ編集者は、改行およびバランスを調整して使用可能なスペースを埋めるように見出しを書く。異なるサイズのカラムを横切って配置されたランダムな見出しは、上手く改行されず、および／または行を埋めることができないことが多く、低品質のレイアウトをもたらすこととなる。
【００７２】
特許請求された主題の別の態様によると、この困難性は、表示時にテンプレート内のスタイルを、使用可能なコンテンツに適応させることを可能にすることによって緩和することができる。デザイナーは、所与のエレメントで使用する可能性あるスタイルのリストを指定することができ、レイアウトエンジンは、それぞれについての客観的スコアを、それぞれ１つ生成しようと試みることができる。最良スコアをもたらすスタイルが、実際のレイアウトで使用されることがほとんどであろう。しかし、同じテキストとテンプレートの組合せでは、異なるページ寸法で異なるスタイルが選択される可能性が高い。テキストレイアウトを評価するための方法を使用して、最良のスタイルを判定することができる。例えば、特定のスタイルのフォントサイズによってスケーリングされた、最適改行のスコアリング関数（optimal line-breaker's scoring function）の結果を用いることができる。最適改行（optimal line-breaker）は、複数の文字幅として表現された、各行内に残る空白を測定する。文字幅は通常フォントサイズに依拠するので、スケーリングなしでは、より大きいフォントは、より小さい（よりよい）スコアをもたらす傾向がある。
【００７３】
（文書表現）
文書表示は、多種多様のソースから取り出されたデータを高品質な方法で表示することを可能にするように拡張されてきた。文書は典型的に、追加された能力は有するが、元のＡＧＢＤＬシステム（以下で論じる）と完全に同じように構築される。
【００７４】
インターネット上にはデータの標準フォーマットがないので、データソースのオンザフライ変換のサポートは、例えばＸＳＬＴを通じて得る。ＸＳＬＴは、変換ファイルによって指定された一連の規則を適用することによってソース文書（一般にＸＭＬ文書）を新しい結果文書に変換するシステムである。任意のＸＭＬデータのいずれも、文書に変換することができ、結果として生じる文書によって参照することができる適切な１組のテンプレートが与えられると、この文書を表示することができる。このように、任意のＸＭＬデータ、適格な（well-formed）ＸＭＬソースを有するウェブページ、または自動変換可能な他のタイプのデータを、ＸＳＬＴ変換が存在する場合にはインターネットから直接ロードすることができる。
【００７５】
ユーザは、変換ファイルを、文書パス（path）またはＵＲＬ（Universal Resource Locator）とともにこのビューア（viewer）のパラメータとして指定することができる。あるいは、ユーザは、オペレーティングシステムレジストリなどのレジストリにエントリを配置することによって、パスまたはＵＲＬプレフィックスを変換ファイルに関連付けることができる。この関連付けにより、プレフィックスから始まる名前付きパスまたはＵＲＬがロードされるときはいつでも、入力文書に適用されるＸＳＬＴ変換を自動的に促進することができる。
【００７６】
従来、ＸＳＬＴ変換の１つの制限は、多くのＨＴＭＬウェブページが存在しない適格なＸＭＬ上でしかＸＳＬＴ変換が動作しないことである。したがって、ユーザは、ウェブスクレーパーなどの代替の変換プログラムを指定することができ、この変換プログラムは、指定されたデータを、解析する前に前処理することができる。一部の例示的な適用例では、専用のウェブスクレーパーと、スクレーパーの出力に作用するＸＳＬＴ変換との両方を使用して、最終文書を作成する。
【００７７】
文書の基本構造は通常、コンテンツを、順序付けされたデータシーケンスを定義することができるコンテンツストリームの集合に編成する。コンテンツは、テキスト、イメージ、あるいはサブテンプレートを使用して再帰的にレイアウトされるそれら自体のサブストリームの集合を含むことができる複合アイテム（compound item）とすることができる。複合エレメント（compound element）を表示するテンプレートは一般に、複合エレメントの個々のストリームをレイアウトするのに使用することができるテンプレートのリストを提供しなければならない。
【００７８】
外部コンテンツを文書内に含める手法に柔軟性をもたせることは、多くの場合、有用である。文書内のほとんどの任意のコンテンツストリームは、提供されたパスまたはＵＲＬからロードすることができる外部ストリームとすることができる。追加的にまたは代替的に、単一のコンテンツストリーム内の個々のコンテンツアイテムについて、外部参照を指定することができる。実質的にはすべての外部参照は、関連するＸＳＬＴ変換、またはリンクで指定された他の前処理エージェント（pre-processing agent）を有することができる。参照された任意のほとんどの文書を、複合アイテムとして全体でロードすることができ、さもなければ、個々のストリームを文書から抽出することができる。例えば、ニュースアグリゲータでは、個々のソースからロードされた個々の新しいニュース記事を含むストリームの集合、および目次を構築するためにその見出しのそれぞれを抽出する単一のストリームを有することがある。
【００７９】
ＡＧＢＤＬシステムに提供されないが、特許請求された主題の態様は、それ自体の表示テンプレートリストを含む複合エレメントとして定義することができるサブ文書の概念を導入することがでる。サブ文書は、レンダリングされるときに、親テンプレート内で指定されたテンプレートではなく、それ自体のテンプレートを使用することができる。サブ文書が含まれることにより、実質的にはいずれの文書もここでは、親および子の文書の階層と見なすことができる。
【００８０】
文書ツリー内の各ノードでは、デザイナーは、親または子の文書が、テンプレートを供給することによりレイアウトを制御するかどうかを選択することができる。これを二者択一（all or nothing）の選択にすることは、常に望ましいとは限らない。むしろ、親テンプレートからのサブ文書のレイアウトに影響を及ぼすための一般的な方法がある。１つの方法は、親が、子テンプレートのスタイルシートをオーバーライドすることである。典型的な新聞にならってモデル化された、集約された文書では、見出しが並んで現れるときにそれが容易に区別されるように見出しのスタイルを変化させることが通常望ましい。親テンプレートは、記事が現れるエレメントに、異なるスタイルシートを渡すことによってこれを保証することができる。
【００８１】
子文書のレイアウトに影響を及ぼすための別の方法は、パラメータを渡すことによるものである。子テンプレートに渡されたパラメータを、テンプレートがインスタンス化される前に、子の制約システム内に入力することができる。パラメータ値を、親の制約システムから派生させることができ、または直接指定することができる。渡されたこれらの制約値を、子文書によって、任意の数の方法で使用することができる。それらを、サブテンプレート内の個々のエレメントの事前条件に含めることができ、またはエレメントの位置およびサイズ調整を制御する他の制約によって参照することができる。他の例では、重要ではないサブ文書（non-featured sub-document）内の大きいグラフィックスの表示を抑制するが、それが最上位レベルの文書として、または重要な役割のサブ文書として表示される場合には大きいグラフィックスの表示を含むように、パラメータを使用する。サブ文書内の特徴を、親ページ上または別のサブ文書内の特徴と位置合わせするように、パラメータを使用することもできる。デザイナーは、サブテンプレートが評価された後、親テンプレートの制約システムに入力することができるサブテンプレートからの戻り値を同様に指定することができる。
【００８２】
サブ文書および複合エレメントの特徴は、ここではそれらが独立にページネーションされ得ることである。サブ文書の連続ページには、適所（in place）でサブ文書のページをめくることによりアクセスすることができ、またはサブ文書の連続ページを、親文書の連続ページにレイアウトすることができる。第１の方法は、ユーザが、親の第１面上のサブ文書化されたニュース記事全体を、内部のページにジャンプせずに読むことを可能にすることができる。それによって、インデックスは、そのページに割り当てられたスペースよりも大きいものとすることができるが、そのデータのすべてを依然としてアクセス可能にすることもできる。他の使用法は、例えば、親の単一ページ上に存在する複数ページ広告またはサイドバーを含むことができる。
【００８３】
（非矩形テンプレートおよびエレメント）
元のＡＧＢＤＬシステムおよび本革新の両方のテンプレートは一般に、原点、幅および高さを有する矩形として定義される。しかし、非矩形エレメントが望まれる多くの場合がある。このような機能を、エレメントをｚ順に階層化することによって単一のテンプレートで達成することができ、その場合、より高位層のエレメントのセクションは、オーバーラップする下位層のエレメントと区別される。エレメントを、層の降順に評価することができる。それぞれのエレメントがレイアウトされる前に、以前にレイアウトされたすべてのエレメントのＧＤＩ領域を、現在のエレメントのＧＤＩ領域から取り去ることができる。完了したエレメントの領域が、例えば各エレメントを完了すると単一の領域に完了したエレメントを配置する結合操作（union operation）によって累積される場合には、これを単一の操作で行うことができる。この操作によって、イメージは典型的には遮断されたままであるが、後のエレメント内の任意のテキストを、他のオーバーラップするエレメントの周りを流すことを可能にすることができる。しかし、通常、エレメント領域を、サブテンプレート内の領域から直接は取り去ることはない。代わりに、エレメントの領域の累積された結合を、より下位層内のサブテンプレートに渡すことができ、この親領域は、それらのサブテンプレート内の累積された領域をシードする（seed）ことができる。この手法で、テキストは、より高水準のテンプレート内で、オーバーラップするエレメントの周りを流れることができる。
【００８４】
親領域を取り去ることによって、テキストのリフローによってサブテンプレートをオーバーラップさせることの困難性の一部に対処することができるが、子の中のイメージまたはサブテンプレートの遮断を回避することも望ましい。したがって、邪魔にならないようにイメージを流す容易な方法は存在せず、したがって、代わりにエレメントが（部分的にまたは完全に）遮断されるかどうかを決定し、エレメントの客観的スコア内にそれを反映する。テンプレートの作成者が、エレメントのスコアを完全なテンプレートのスコアに含めることを選択する場合、遮断されたエレメントを有しない別のテンプレートが使用可能であれば、そのテンプレートを無視することができる。代替としてまたは追加として、遮断されたエレメントのいくつかの位置を、最良適合  ＯＲグループ内の１つのテンプレートに含むことができ、この場合、遮断されていない位置が、使用可能であれば選択されるのが一般的である。
【００８５】
親領域をエレメントのＧＤＩ領域と区別して、結果として生じる領域を元の領域と比較することによって、遮断されたエレメントは検出される。テンプレート作成者は、エレメントがレイアウトされるときにオーバーラップが生じる場合に、エレメントの客観的スコアに適用されるべきペナルティを指定する、任意のエレメントの属性を含めることができる。
【００８６】
別の態様では、親領域を使用して、文書にさらなる柔軟性を提供することができる。親領域は、オペレーティングシステムのアプリケーションウィンドウのシステムクリッピング領域（application window's system clipping region）の最上位レベルのテンプレートを初期化することができる。これによって、システムが、デスクトップ上の他のアプリケーションのオーバーラップしたウィンドウの周りに文書を流し、遮断されたイメージを邪魔にならないように潜在的に移動させることを可能にすることができる。最良の結果を、リフローされた任意のテキストの隣にマージンを提供するように任意のオーバーラップした領域をわずかに膨張させることによって取得することができる。
【００８７】
上述された手順は、サブ文書が非矩形エレメントを占有することを可能にすることができるが、これもやはり、高品質レイアウトをもたらすのに必ずしも十分であるとは限らない。新聞の第１面では、例えば、トップ記事からの写真を目立つように載せたいと望むことがあり、写真と記事の残り部分との結合は、都合のよい矩形を形成しないことがある。境界となる矩形（bouding rectangle）を、エレメントの周りに常に描くことができるが、大きいまたは不規則な領域を取り去り、意図されるように依然として見栄えのよいテンプレートをデザインすることは、難しいことが多い。この困難性を、いくつかのエレメントのＡＮＤグループを形成することによってより容易に解決することができ、この場合、エレメントのすべては、コンテンツを、単一の複合コンテンツアイテムまたはサブ文書から取り込む。これによって、いずれかの任意の形状の領域内のサブ文書を効果的にレイアウトすることが可能になり得る。新聞ページの特集記事の例では、あるエレメントが写真ストリームから取り込み、もう一方のエレメントがその他すべて取り込むことが望まれていた。この一般的な場合では、ｃｏｎｓｕｍｅＲｅｍａｉｎｄｅｒ属性を、認識し、使用することができる。デザイナーは、この属性をＡＮＤグループ内のエレメント上に置くことができ、そのエレメントのグループの他のメンバによって取り込まれなかったそのエレメント内のコンテンツのすべてを使用するようにシステムに伝える。
【００８８】
（領域特有の課題）
このセクションでは、コンテンツの集約をレイアウトすることに特有の困難性の一部、ならびにこれらの困難性に対応するために開発された技術の一部について述べる。
【００８９】
（カラムのバランス調整）
マルチカラムレイアウト上に複数の記事または論説をレイアウトするとき、記事を互いに対してどのように配列するかについて多くのオプションがあり得る。２つ記事の間でページ（またはページの一部）を分割する１つの一般的なやり方は、ページを水平に分けて、第２の記事を第１の記事の最下部の下に置くことである。このタイプのレイアウトを使用する場合、各カラムが同じ垂直位置で終わるように、そのために割り当てられたカラム間でコンテンツを等しく分配しなければならない。
【００９０】
この実装形態では、ページ上のカラムを表すエレメントのグループ（およびＡＮＤグループ）がｂａｌａｎｃｅＣｏｌｕｍｎｓプロパティでタグ付けされるときにトリガされる簡単な反復レイアウトアルゴリズム（iterative layout algorithm）を介して、これを達成することができる。下記に、単一の記事をレイアウトし、その最下部をできるだけ平らに保つためにこの反復アルゴリズムがどのように働くかについて述べる。
【００９１】
第１に、ページは、例えば標準の欲張りレイアウト法（greedy layout method）を使用してレイアウトされる。コンテンツが完全にページを埋める場合は、カラムは、バランス調整され、このレイアウトを、最終結果として使用することができる。そうでない場合は、バランス調整されるべきエレメント内に残っている未使用の総垂直空間が測定される。余分な空間のこの総量を、カラム数で割り、バランス調整された結果の各カラムがアンダーフィル（underfill）される量についての最初の推測を与えることができる。次いで、この垂直アンダーフィル（vertical underfill）の測定量を、エレメントの最下部から取り去り、バランス調整されたテキストの最下部となると思われるカットオフ位置をもたらすことができる。次いで、エレメントそれぞれの新しい最下部を、レイアウトを再び実行するために、計算されたこのカットオフ位置に設定することができる。すべてのテキストが取り去られ、テキストがバランス調整される（最後のカラムは、カラム数より最大１行未満だけアンダーフィルされ、依然として「バランス調整された」と見なされることが認められる）場合、このレイアウトを使用することができる。しかし、カラムが適切にバランス調整されない場合は、レイアウト手順を再び実行することによって、カットオフ位置を調整する−最後のカラムがあまりにまばらである場合はカットオフ位置を上げ、すべてのコンテンツにとって十分な余地がない場合はカットオフ位置を下げる−ことができる。この手順を、バランスの取れたレイアウトに収束するまで繰り返すことができる。
【００９２】
最後に、エレメントの新しい最下部を、そのエレメント内にレイアウトされた任意のコンテンツの真下に設定することができる。これは、反復が収束する正確なカットオフ値に基づいて、エレメントが予測不可能な高さを有することを防ぐことができる。
【００９３】
（分割不可能な段落およびアトミックなサブ文書）
状況によっては、ページ境界の上でコンテンツの一部分を割ることが意味をなさないことがある。例えば、コンテンツが、２行または３行にまたがる１文の要約にすぎない場合、コンテンツ全体を次のページに単に移動させることが好ましいことがある。新聞のような第１面についての特定の場合は、新聞の内部または他のセクションの強調部分（highlight）として機能する多くの小さいボックスが存在することがある。これらの小さいボックスのコンテンツは典型的に、上述されるように個々の記事の短い要約である。これらの短い要約がページ境界を越えて分かれることを避けることにより、通常はるかに見栄えがよくなる。したがって、これを達成するために、コンテンツチャンク（content chunk）に、「コンテンツのこの部分を、ページまたはエレメント境界を越えて分割しない」ことを意味するプロパティでタグ付けすることができ、あるいはエレメントに、「ここに完全に表示することができるコンテンツアイテムだけを受け付ける」ことを意味する別のプロパティでタグ付けすることができる。問題になっているコンテンツは、個々の段落、あるいは、写真およびキャプションまたはサイドバーを恐らく表す複数のデータストリームを含む複合アイテム、とすることができる。
【００９４】
（インタラクティビティ）
電子文書は、紙の文書を模倣することに制限される必要はない。異なる画面寸法に自動的に適応することは、紙の文書では不可能なことであるが、文書は、表示サイズが固定された後でも、紙文書のすべてのプロパティを前提とする必要があるとは限らない。例えば、コンテンツ加入者（content subscriber）は、オンライン文書のハイパーリンクを使用することに長い間慣れ親しんできたが、読者が同様に電子文書と対話することができる他の方法がある。
【００９５】
インタラクティビティの一環として、ハイパーリンクを文書内でサポートすることができ、リンクは他の文書をターゲットにすることができる。これは、固有文書、および上記の「文書表現」のセクションで説明されたようにロード時に変換することができる文書を含む。ハイパーリンクは、ターゲットコンテンツのパスまたはＵＲＬに加えて、ＸＳＬＴ変換または別のヘルパープログラムへの参照を含むことができる。ハイパーリンクは、読取り不可能なＵＲＬを参照することもでき、その場合、ウェブブラウザを立ち上げて、リンクがアクティブ化されるときにコンテンツを表示することができる。最後に、ハイパーリンクは、文書の内部のコンテンツを指すこともでき、その場合、参照を含むページを表示することができる。
【００９６】
複合文書（例えば、サブ文書を含む文書）内のハイパーリンクをアクティブ化するとき、可能性のある振舞いがいくつかある。リンクが最上位レベルの文書内にある場合は、文書全体を、参照された文書で置き換えることができる。リンクがサブ文書内にある場合は、サブ文書のみを参照された文書で置き換えることが望ましいことがある。これは典型的に、システムのデフォルトの振舞いであるが、デザイナーは、任意のサブ文書エレメントを「ランチャー（launcher）」エレメントとして指定することができ、このランチャーエレメントにより、そのエレメント内のアクティブ化されたリンクは、最上位レベルの文書、または代わりに別の示されたサブ文書を置き換えることができることとなる。この特徴は、インデックスまたは目次を実装するサブ文書とって有用であり得る。作成者は、いずれかのエレメントまたは位置ノード内で「ｌａｕｎｃｈｅｒ」属性を真（true）に設定することによって、エレメントをランチャーにする。ランチャーエレメントは、エレメント上に「ｔａｒｇｅｔ」属性も設定されない限り、リンクされた文書が最上位レベル文書を置き換えることを容易にすることができる。「ｔａｒｇｅｔ」属性に、テンプレート内の別のエレメントの名前を設定することができ、次いで、リンクされた文書は、名前付きのエレメント内に現在表示されているサブ文書を置き換えることができる。
【００９７】
リンクをアクティブ化する別の方法は、リンクをページのサブ文書エレメントにドラッグアンドドロップすることである。例えば新聞のように複数のサブ文書の集合を含むページ上で、ユーザはそれにより、インデックスから記事を取り出し、ページ上の記事位置の１つに記事をドロップすることができる。
【００９８】
（結果）
本革新の範囲および能力を示す複数の文書／適応例について述べた。適応例には、オンラインマガジンＳｌａｔｅの適応バージョン、Ｎｅｗ  Ｙｏｒｋ  Ｔｉｍｅｓ  ＲＳＳフィードから記事を取り、そのウェブサイトから完全なコンテンツをスクラップし、大判の新聞のフォーマットで記事を表示するニュースリーダ、ならびにインターネットを介してデータベース要求を行って、何千ものウェブソースから現在のニュース速報最新版を取り出し、個々の適応サブ文書を集約するための適応第１面ゲートウェイとして動作することができるインターネットニュースアグレゲータＭＳＮ  ＮｅｗｓＢｏｔのフロントエンドが含まれる。他の実装形態は、例えば、検索結果を高品質の適応表示で提示するＭＳＮ  Ｓｅａｒｃｈフロントエンドを含むことができる。
【００９９】
Ｓｌａｔｅマガジン実装のデモンストレーションは、ＡＧＢＤＬテンプレートシステムを使用して構築されていた。それは、１個から３個のカラムレイアウトをカバーするページを実装するのに、７４個のテンプレートを必要とした。Ｎｅｗ  Ｙｏｒｋ  Ｔｉｍｅｓのデモは、新しいテンプレートシステムを使用し、１個から６個のカラムのレイアウトを実装するが、５個のテンプレートしか必要としない。５つのテンプレートはそれぞれ、Ｓｌａｔｅデモ用に作成されたテンプレートのサイズの約４分の１である。
【０１００】
次に、図１を参照すると、多種多様なコンテンツを伴い複数のサイズおよび寸法で表示することができる文書レイアウトの適応を容易にするシステム１００が示されている。一般に、システム１００は、テンプレート１０４を受け取るインタフェース１０２を含むことができる。テンプレート１０４は、文書レイアウトに関する制約の高水準の記述とすることができる。レイアウトエンジン１０６は、テンプレート１０４を解釈することができ、テンプレート１０４の高水準の制約に基づいて、高品質文書１１０を作成するために文書内のどこにコンテンツ１０８を置くか決定することができる。
【０１０１】
上述したように、高品質文書は、現在の表示寸法およびコンテンツが与えられて、表示された出力が見栄えがよいと判断される文書である。表示された出力が見栄えよいかどうかの判断は、全体的な視覚的効果、ならびに以下で図３および図６に関してより詳細に論じられる他の属性に基づくことができる。したがって、レイアウトエンジン１０６は典型的に、高品質レイアウト１１０を作成する前に、配置されるべきコンテンツのタイプおよび配置の表示寸法を事前に知ることを必要とする。しかし、テンプレート１０４は事前に知っている必要はなく、典型的には、テンプレート１０４が作成されるとき、またはテンプレート１０４がレイアウトエンジン１０６によって受け取られるとき、コンテンツのタイプまたは表示寸法について事前には知らないことを理解されたい。
【０１０２】
次に図２に進むと、ユーザインタフェース２０２、テンプレート１０４、およびテンプレートストア２０４を一般に備えるシステム２００が図示されている。ユーザインタフェース２０２は、テンプレート１０４などのテンプレートの作成、デザイン、および／または修正を容易にすることができる。同様に、テンプレートストア２０４は、テンプレート１０４などのテンプレートを格納することができる。ユーザインタフェース２０２は、テキストベース、あるいは、高水準の制約パラメータを介してテンプレート１０４を構成して、例えばテンプレートストア２０４を介してテンプレート１０４にストレージを提供するために使用することができるＧＵＩのいずれかとすることができることを理解されたい。図２には単一のテンプレート１０４だけが示されているが、インタフェース１０２を使用して、任意の数のテンプレート１０４を作成し、デザインし、および／または修正することができることも理解されたい。同様に、テンプレートストア２０４は、修正および／またはレイアウトエンジン１０６（図１）またはページネータ６０２（図６）に供給されるべきユーザインタフェース２０２によって取り出すことができる複数のテンプレート１０４を格納することができる。
【０１０３】
テンプレート１０４は、レイアウト用の画面エレメントの定義パラメータなど、複数のパラメータ（例えば、エレメントを記述し、それらのエレメントをどのタイプのコンテンツに使用することができるかを提供する高水準構成体）、ならびにエレメントが互いに対してどのように配置されるかを制御することができる制約システム（例えば、上述されるｏｖｅｒおよびｕｎｄｅｒコマンド）で構成することができる。したがって、テンプレート１０４は、レイアウトの多くの異なる態様を指定するために使用することができる高水準言語を提供する。同様に、この高水準言語は、より自然な記述言語であり、作成しやすく、それと同時に、より少ないステートメントでより広い概念を表現することができる。さらに、この高水準言語を、以下で図５に関してより詳細に説明されるように、低水準の記述に変換することができる。
【０１０４】
次に図３を参照すると、高品質レイアウト１１０を作成することができるレイアウトエンジン１０６を一般に含むシステム３００が示されている。上述したように、レイアウトエンジン１０６は、高品質レイアウト１１０の作成時に順守されるべき高水準制約を提供するテンプレート（図示せず）を受け取ることができる。しかし、レイアウトエンジン１０６は実際には、配置がテンプレートの最も重要な制約、ならびに出力が高品質レイアウト１１０となるのに必要な条件を順守するように、コンテンツ１０８を配置しなければならない。
【０１０５】
典型的には、レイアウトエンジン１０６は、コンテンツ１０８をどのように配置するかを決定する前に、コンテンツ１０８のあるタイプおよび／または複数のタイプ、ならびに高品質レイアウト１１０のための表示寸法を調べることとなる。いくつかの場合では（例えば、コンテンツのタイプ、あるいは他の要因に応じて）、レイアウトエンジン１０６は、意味の流れ３０２、ブランドアイデンティティ３０４、アイテムとテキストの相関性３０６、および広告テーマ３０８などの他の考慮事項を使用することができる。いくつかの場合では、意味の流れ３０２、ブランドアイデンティティ３０４、アイテムとテキストの相関性３０６、および広告テーマ３０８の少なくとも１つが考慮されない限り、レイアウトは、高品質レイアウト１１０とはならないであろう。
【０１０６】
意味の流れ３０２は、一般的に単語の実際の意味を指すことができ、したがって、典型的には他の単語に関連した単語の意味に依拠する。したがって、新聞見出しなど、コンテンツ１０８エレメントまたはタイプのいくつかは、たとえ異なる位置に単語を配置するようにそれらを分割することによって、レイアウト配置に関するより単純な解決策をもたらすことができるとしても、曖昧さを防ぐために単語を一緒に保つことの強力な意味的根拠（strong semantic rationale）を有する。例えば、否定的な接頭辞（prefix）または単語の直後に改行を置くことを避けるのに有効な意味の流れ３０２の根拠が存在し得る。
【０１０７】
レイアウトエンジン１０６は、高品質レイアウト１１０を生成するときに、ブランドアイデンティティ３０４を考慮することもできる。例えば、コンテンツ１０８は、よく知られたパターンでオーバーラップする２つの関連イメージからなる商標（trademark）とすることができ、ブランドは、十分に説明するものとなるように、他のコンテンツ１０８（例えば、グラフィックの渦巻き、「Ｉｎｔｅｌ  Ｉｎｓｉｄｅ」という文字、および４つの音声トーンを含むＩｎｔｅｌ社のよく知られた商標）を必要とする。それぞれのイメージおよび／または他のコンテンツが適切に配置されない場合、レイアウトは、デザインエディタを有する他のデザイン媒体が別のやり方で達成することができる効果および／または意味の一部を失うことがある。
【０１０８】
さらに、レイアウトエンジン１０６は、高品質レイアウト１１０を作成するときにアイテムとテキストの相関性を考慮することもできる。例えば、新聞は一般に、アイテムを説明する小さいキャプションを提供する。同様にイメージ（例えば、アイテム）は、写真の特徴、または写真の中の人物によって話されるテキストを示すための吹き出し（callout）を含むことがある。それらの場合、特定のテキストの位置をアイテムに関して考慮することが重要である。
【０１０９】
同様に、レイアウトエンジン１０６は、高品質レイアウト１１０を作成する際に広告テーマ３０８を考慮することができる。広告テーマ３０８は、アイテム３０２〜３０６に関して上記で与えられた複数の例のいずれかに依拠することがあり、また同様の理由により、レイアウトエンジン１０６による追加の解析を必要とすることがある。しかし、広告テーマ３０８は、別のやり方では他の考慮事項と矛盾する可能性がある条件を必要とする可能性があることを理解されたい。上記の例は例示的なものにすぎず、限定することは意図されていないことも理解されたい。本発明の範囲および精神から逸脱せずに、他の適応例を使用することができる。
【０１１０】
図４を簡単に参照すると、多種多様なコンテンツを伴い複数のサイズおよび寸法で表示することができる文書レイアウトの適応を容易にするシステム４００が示されている。システム４００は一般に、レイアウトエンジン１０６、コンテンツ１０８、高品質レイアウト１１０、出力装置４０２を含む。出力装置４０２は実質的には、小さいリストディスプレイ、ポータブルハンドヘルドデバイス、デジタルファブリック、ワークステーション、壁掛け式ディスプレイ、さらに沿道の広告版および建物用の非常に大きいディスプレイからのデジタルコンテンツを表示することができる任意の装置とすることができる。典型的にレイアウトエンジン１０６は、出力装置４０２に基づいて、高品質レイアウト１１０のサイズおよび寸法を決定することとなる。
【０１１１】
次に図５を参照すると、一般にテンプレート１０４、レイアウトエンジン１０６、コンテンツ１０８、高品質レイアウト１１０、および低水準エンジン５０２を含むシステム５００が示されている。低水準エンジン５０２は、低水準の制約に基づいてコンテンツ１０８を適応グリッドベースのレイアウトに適用することができる。しかし、低水準エンジン５０２は、高水準テンプレート１０４を受け入れる能力をもたないが、十分な詳細および抽象化が（例えばレイアウトエンジン１０６によって）提供された場合は、高品質レイアウト１１０を作成することができる。低水準エンジン５０２について、ＡＧＢＤＬシステムで以下に詳細に述べる。上述したように、レイアウトエンジン１０６は、高品質レイアウト１１０を作成するために、テンプレート１０４に提供された高水準の制約に基づいて（ならびに、もしあれば追加の条件に基づいて）コンテンツ１０８をどのように配置するか決定することができる。高品質レイアウト１１０を作成する正確なレイアウトが分かると、レイアウトエンジン１０６は、低水準エンジン５０２が高品質レイアウト１１０を作成することができるように、この情報を低水準の制約に変換することもできる。
【０１１２】
図６は、多種多様なコンテンツを伴い複数のサイズおよび寸法で表示することができる文書レイアウトの適応を容易にするシステム６００を示している。システム６００は一般に、インタフェース１０２、テンプレート１０４、レイアウトエンジン１０６、コンテンツ１０８、高品質レイアウト１１０、およびページネータ６０２を含む。ページネータ６０２については、ＡＧＢＤＬのセクションで以下に詳細に述べる。しかし、この文脈では、ページネータ６０２は、レイアウトエンジン１０６のための抽象化のレベルを提供する。例えば、ページネータ６０２は、コンテンツ１０８を受け取り、また、所与のコンテンツ１０８に使用されるテンプレート１０４を選択するためにインタフェース１０２と通信する。ページネータ６０２は、代替的に、テンプレート１０４を、例えば図２のテンプレートストア２０２から直接に取り出すことができることを理解されたい。レイアウトエンジン１０６は、テンプレート１０４およびコンテンツ１０８を受け取り、高品質レイアウト１１０を作成するためにコンテンツ１０８を配置する。要するに、ページネータ６０２は、各文書および／または文書の各ページにどのテンプレート１０４を使用するか決定することができ、レイアウトエンジン１０６は、実際のコンテンツ１０８を高品質レイアウト１１０と整合性が取れた手法でどのように配置するか決定することができる。
【０１１３】
次に図７に進むと、高品質レイアウト１１０を作成するためのシステム７００が示されている。一般にシステム７００は、コンテンツ１０８を受け取るレイアウトエンジン１０６を含む。例示的な一実施形態によると、コンテンツ１０８は、複数のソースから集約される異なるタイプとすることができる。例えば、コンテンツ１０８を、データストアなどのコンテンツストア７０２、ハードウェア装置などからのストリーミングメディア７０４、および多種多様なコンテンツタイプとすることができるウェブコンテンツ７０６から取り出すことができる。したがって、コンテンツ１０８は様々なソースから供給され得るので、コンテンツ１０８のソースフォーマット７０８は恐らく、非常に多様であろう。したがって、レイアウトエンジン１０６は、ソースフォーマット７０８でフォーマットされたコンテンツ１０８を受け取ることができ、ソースフォーマットを、レイアウトエンジン１０６が高品質レイアウト１１０を作成するのに使用することができるフォーマットに変換することができる。例えばＸＬＳＴによるソースフォーマット７０８および変換を、上述されるように自動的に実行することができる。
【０１１４】
図８は、特許請求された主題による方法８００を示す。説明を簡単にするために、この方法は一連の行為として示され、説明されているが、特許請求された主題は、いくつかの行為は本明細書に示され説明されるものとは、異なる順序および／または他の行為と同時に生じることがあるので、行為の順序によって限定されないことを理解し、認識されたい。例えば、方法は代替的に、状態図など、一連の相関した状態またはイベントとして表すことができることを当業者は理解されよう。さらに、図示されたすべての行為が、特許請求された主題に従って方法を実装するのに必ずしも必要とされるとは限らない。さらに、下記また本明細書を通して開示される方法を、生成物（article of manufacture）に格納し、このような方法をコンピュータに移送し、転送することを容易にすることができることを理解されたい。本明細書で用いられる際、生成物という用語は、任意のコンピュータ読み取り可能装置、搬送波、または媒体からアクセス可能なコンピュータプログラムを包含することが意図されている。
【０１１５】
次に図８を参照すると、高品質レイアウトを作成するようにコンテンツを配置するための例示的なコンピュータ実装方法８００が示されている。８０２で、文書レイアウト用のテンプレートを選択することができる。典型的に、テンプレートを、高水準言語で定義し、インタフェース、ページネータ、およびレイアウトエンジンの１つによって、テンプレートストアから選択することができる。８０４で、文書の表示サイズを決定することができる。この決定を、出力装置の画面サイズおよび／またはその中の領域に基づいて行うことができることを理解されたい。８０６で、文書のコンテンツを受け取ることができる。上述したように、コンテンツは、コンテンツストア、ストリーミングメディア、インターネットなどの広範囲のソースから生じることがあり、また高品質レイアウトのフォーマットと整合性が取れないことがある多種多様なフォーマットで存在し、したがって適切な変換を必要とすることがある。
【０１１６】
８０８で、特定のコンテンツに使用可能な位置を、例えばテンプレートにより供給される高水準制約、ならびに最高品質レイアウトの表示サイズを使用することによって、決定することができる。特定のコンテンツに使用可能な多くの位置が存在し得ることを理解されたい。８１０で、高品質位置を、８０８で決定される使用可能な位置から選択することができる。上述されるように、高品質位置は、レイアウト全体の高品質の特徴を維持しながら特定のコンテンツを取り入れることができる位置である。高品質位置を選択することは、複数の基準に依拠し得ることを理解されたい。例えば、高品質位置は、最良適合、第一適合、第一良好適合などの一連のアルゴリズムの少なくとも１つに基づいて決定することができる。このような決定も、意味の流れ、ブランドアイデンティティ、アイテムとテキストの相関性、広告テーマなどの他の条件に依拠し得る。ステップ８１２では、高品質レイアウトを作成することができる。
【０１１７】
（ＡＧＢＤＬシステム）
図９は、特許請求された主題の例示的な一実施形態による適応グリッドベース文書レイアウト環境９００のブロック図を示す。適応グリッドベース文書レイアウト環境９００は、適応グリッドベースの文書システム９０２、スタイルシートストレージユニット９０６、テンプレートストレージユニット９０８を備える。適応グリッドベース文書レイアウト環境９００は、図１０に関して以下でより十分に説明されるよく知られたコンピューティングシステム、環境、および／または構成で見られるものと同様のハードウェアおよびソフトウェアコンポーネントによってサポートされる。適応グリッドベース文書システム９０２は、ページネータ６０２、低水準エンジン５０２、テンプレート作成ツール９１０、およびユーザインタフェース９１２を備える。
【０１１８】
スタイルシートストレージユニット９０６は、低水準エンジン５０２を介して適応グリッドベース文書システム９０２に通信可能に接続する。スタイルシートストレージユニット９０６は、文書コンテンツ９０４内のテキストのスタイルを指定するのに使用されるスタイルシートデータを記憶する。スタイルシートストレージユニット９０６は、限定ではないがＲＡＭ、フラッシュメモリ、磁気メモリ装置、光メモリ装置、ハードディスクドライブ、リムーバブルな揮発性または不揮発性メモリ装置、光学記憶媒体、磁気記憶媒体、またはＲＡＭメモリカードを含む、データを格納し取り出すことができるメモリ装置を備える。あるいは、スタイルシートストレージユニット９０６は、有線および／または無線ネットワークシステムを通じてアクセス可能なリモートストレージ機能を備えることができる。さらに、スタイルシートストレージユニット９０６は、上述されるように、一次および二次のメモリ装置の多段階システムを含むメモリシステムを備えることができる。一次メモリ装置および二次メモリ装置は、お互いに対してキャッシュとして動作することができ、または二次メモリ装置は、一次メモリ装置のバックアップとして機能することができる。さらに別の配置では、スタイルシートストレージユニット９０６は、簡単なデータベースファイルとして、またはＳＱＬなどのクエリ言語を使用する探索可能なリレーショナルデータベースとして構成されるメモリ装置を備えることができる。
【０１１９】
テンプレートストレージユニット９０８は、ページネータ６０２とテンプレート作成ツール９１０を介して、適応グリッドベース文書システム９０２に通信可能に接続する。テンプレートストレージユニット９０８は、複数のテンプレート１１０６を記憶し、それぞれのテンプレート１１０６を使用して文書コンテンツ９０４の単一のページのレイアウトを定義することができる。文書コンテンツのレイアウトは、１つまたは複数のテンプレート１１０６によってレイアウトされるページを含むことができる。テンプレートストレージユニット９０８は、スタイルシートストレージユニット９０６に関して上記で説明されたメモリ装置と同様のメモリ装置を備える。
【０１２０】
ページネータ６０２は、低水準エンジン５０２およびテンプレートストレージユニット９０８に通信可能に接続する。ページネータ６０２は、本明細書で説明されるように、タスクを実行して、能力および機能を提供するのに適したハードウェアおよびソフトウェア（図１０参照）で構成される。さらに、ページネータ６０２は、適応グリッドベースのレイアウトへと処理するために文書コンテンツ９０４を受け取ることができる。文書コンテンツ９０４を、限定ではないが本文、イメージ、インライン図、サイドバー、キャプション、媒体、および他の適切な文書コンテンツ９０４などの様々なコンテンツタイプを識別する様々なコンテンツストリーム１３０３によって表すことができる。一般に、ページネータ６０２は、文書コンテンツ９０４の個々のテンプレート１１０６へのマッピングを決定し、限定ではないが、文書コンテンツ９０４をテンプレート１１０６と大域的に最適な対にすることを含むことができる。
【０１２１】
低水準エンジン５０２は、ページネータ６０２およびスタイルシートストレージユニット９０６に通信可能に接続する。低水準エンジン５０２は、本明細書で説明されるようにタスクを実行し、能力および機能性を提供するのに適したハードウェアおよびソフトウェア（図１０参照）で構成される。低水準エンジン５０２は、処理するために、ページネータ６０２から文書コンテンツ９０４およびテンプレート１１０６を受け取ることができる。典型的に、低水準エンジン５０２は、テンプレート１１０６の使用によって文書コンテンツ９０４を自動的にフォーマットし（例えば、文書コンテンツ９０４にテンプレート１１０６を適用し）、それによって適応グリッドベース文書９１４を作成する。さらに、低水準エンジン５０２を使用して、文書コンテンツ９０４へのテンプレート１１０６の適用から作成された適応グリッドベース文書９１４の各部分（例えば各ページ）の品質スコアを決定することができる。
【０１２２】
操作において、適応グリッドベース文書システム９０２はページネータ６０２を介して、処理されるべき文書コンテンツ９０４をテンプレートストレージユニット９０８から受け取る。ページネータ６０２は、実際のページレイアウトのレンダリングのために、文書コンテンツ９０４およびテンプレート１１０６を低水準エンジン５０２に提供する。特許請求された主題の代替の一実施形態では、低水準エンジン５０２は、テンプレートストレージユニット９０８に通信可能に接続され、したがって、低水準エンジン５０２は、テンプレート１１０６をテンプレートストレージユニット９０８から直接受け取る。低水準エンジン５０２は、スタイルシートストレージユニット９０６およびテンプレート１１０６からのスタイルシートを文書コンテンツ９０４に適用し、結果に基づいて品質スコアを決定する。低水準エンジン５０２は、すべての有効なテンプレート１１０６のシーケンス（例えば、うまく完全に文書コンテンツ９０４をグリッドベース文書レイアウトに適用させるすべてのテンプレート１１０６のシーケンス）、および対応する品質スコアをページネータ６０２に提供する。ページネータ６０２は、低水準エンジン５０２によって提供された品質スコアに基づいて、テンプレート１１０６の所望のシーケンスのいくつか、またはテンプレート１１０６の大域的に最適なシーケンスのいずれかを計算する。コンテンツとテンプレート１１０６のシーケンスをペアにすることを決定した後、ページネータ６０２は、文書コンテンツ１０９とテンプレート１１０６の最適なシーケンスとを、低水準エンジン５０２に提供する。低水準エンジン５０２は、テンプレート１１０６の最適なシーケンスに従って文書コンテンツ９０４を自動的にフォーマットする。次いで、結果として生じる適応グリッドベース文書９１４は、適応グリッドベース文書システム９０２によって、適切な宛先に提供される（例えば、ユーザに表示され、別のプログラムモジュールに提供され、またはファイルに保存される）。
【０１２３】
テンプレート作成ツール９１０は、テンプレートストレージユニット９０８およびユーザインタフェース９１２に通信可能に接続する。テンプレート作成ツール９１０は、本明細書で説明されるようにタスクを実行し、能力および機能性を提供するのに適したハードウェアおよびソフトウェア（図１０参照）で構成される。ユーザインタフェース９１２は、ユーザに、テンプレートストレージユニット９０８内のテンプレート１１０６を作成または修正するための１組のウィンドウ、アイコン、コマンド、および／またはメニューを提供する。テンプレート作成ツール９１０およびユーザインタフェース９１２の使用によって、ユーザは、レイアウトエレメントを描画し、配置し、エレメントが異なるページサイズにどのように適応するかを指定し、適応インタラクティビティをプレビューし、テンプレート１１０６の事前条件１１０９、および制約ベースの関係（constraint-based relationship）１１１５を設定することができる。
【０１２４】
操作において、ユーザインタフェース９１２は、インタラクティブにサイズ変更することができるテンプレート１１０６の略図を提示する。テンプレート１１０６内に新しいレイアウトエレメント１１１２を作成することは一般に、ユーザが、ユーザインタフェース９１２のディスプレイ上に領域を描画し、次いで、領域を所望のサイズ、位置、および層へと操作することを必要とする。適応テンプレート１１０６の保全性（integrity）を維持するために、テンプレート１１０６のほとんどのエレメント１１１２は、制約ベースの関係１１１５を必要とする。
【０１２５】
テンプレートを作成または編集する間、ユーザは、水平または垂直ガイドを描画すること、およびスナップドラッグインタフェースを使用することによってページグリッドを定義することで、ページレベルの制約を指定して、グリッドに対してエレメントを制約することができる。水平または垂直ガイドは、ページに対してスケーリングし、または一定のオフセットを維持するように、デザインされることがある。ガイドは、他のガイドに依存して、ユーザが階層的グリッドを定義することを可能にすることもできる。特に、ユーザインタフェース９１２は、異なるタイプのユーザ操作をサポートする。上記ユーザ操作には、（１）ユーザが他のガイドをいずれも選択せずに、新しいガイドを追加する場合は、新しいガイドの位置は、全体のページに対して定義される、（２）ユーザが新しいガイドを作成する前に既存の単一のガイドを選択する場合は、新しいガイドの位置は、選択されたガイドからの一定のオフセットとして定義される、（３）ユーザが新しいガイドを作成する前に既存の２つのガイドを選択する場合は、新しいガイドの位置は、選択された２つのガイドに対して定義される、ことが含まれるが、これらに限定されるものではない。ユーザインタフェース９１２は、ユーザがガイドなしにエレメント間で制約を直接に指定することを可能にするユーザ操作を提供することもできる。限定ではなく例として、ユーザは、あるエレメントの最下部を別のエレメントの最上部に一致するように制約することができる。エレメントのサイズが、（ページの形状のみならず）そのエレメント内に流されるコンテンツによって決定される状況に対処するために、ユーザは、テンプレート作成ツール９１０を使用して、エレメントの寸法の１つを制約し、次いで文書コンテンツ９０４から決定される他の寸法を指定することができる。
【０１２６】
カスタムテンプレート１１０６を作成した後、ユーザは、制約システム内の任意の変数の値に基づいて、追加の事前条件を指定することができる。文書コンテンツ９０４に対するテンプレート１１０６の適合性は、事前条件およびスコアリング関数の使用に依存する。ユーザが、テンプレート１１０６のエレメント１１１２のコンテンツソースを設定すると、テンプレート１１０６に関するコンテンツ事前条件を自動的に計算することができる。さらに、ユーザは、文書コンテンツ９０４の所与の選択についてページテンプレート１１０６が受け取る品質スコアに影響を及ぼすエレメント１１１２に、属性プリファレンスを追加することができる。ユーザは、エレメント１１１２の２つ以上の属性を指定する場合、ユーザインタフェース９１２を介して属性を重要度の順にランク付けすることができる。
【０１２７】
次いで、テンプレート作成ツール９１０は、低水準エンジン５０２が、エレメントに流される可能性のある文書コンテンツ９０４の異なる選択を評価するスコアリング関数を、自動的に構築することができる。ユーザ指定の重要度順の属性のランク付けが与えられると、テンプレート作成ツール９１０は、各属性を、より上位の桁（digit）がより重要な属性に対応するスコアの桁に関連付けることができる。低水準エンジン５０２がコンテンツ選択を評価するとき、一致するすべての属性に「１」を、一致しないすべての属性に「０」を関連付けることによって、スコアを計算することができる。より具体的には、「ａ１」から「ａＮ」が、重要度順のＮ個のユーザ指定の属性プリファレンスである場合、スコアリング関数は、作成システム（authoring system）によって以下のように構築される。Ｓ＝ｍａｔｃｈ（ａ１，ｂ１）＊（１０＾（Ｎ−１））＋ｍａｔｃｈ（ａ２，ｂ２）＊（１０＾（Ｎ−２））．．．＋ｍａｔｃｈ（ａＮ，ｂＮ）＊（１０＾０）  ただしＳは、評価されているコンテンツの特定の選択の品質スコアであり、ｂ１からｂＮは、コンテンツの選択に関連付けられる実際の属性値であり、ｍａｔｃｈ（ａ，ｂ）は、「ａ」が「ｂ」に等しいときは「１」を、そうでない場合は「０」を返す関数である。したがって、このスコアリング関数は、コンテンツがユーザによって指定された属性にどの程度よく一致するかに応じて、より良いまたは悪いスコアを返す。スコアリング関数は、より重要な属性には、あまり重要でない属性よりも厳密な優先度が与えられることを保証する。限定ではなく例として、特定の属性「Ａ」に一致するコンテンツの選択では、属性「Ａ」には一致しないが、それほど重要でない属性に潜在的に一致する他のコンテンツ選択よりも良いスコアがもたらされる。
【０１２８】
スコアリング関数を、様々な方法で実装することができることは、当業者には認識されよう。限定ではなく例として、エレメントの各属性を、最終スコアの桁に関連付けることができる。属性の重要度により、対応する桁が決定され、最も重要な属性が最上位桁に関連付けられる。したがって、第ｋの最も重要な属性である属性は、最終スコアの第ｋ最上位桁に対応する。特定のコンテンツ選択について、スコアリング関数は、一致する属性に対応する桁には「１」を、一致しない属性に対応する桁には「０」を関連付けることができる。したがって、スコアリング関数は、最も重要な属性に一致するコンテンツの部分が、最も重要な属性に一致しない他のコンテンツの選択よりも高い（すなわち、より良い）スコアを有することを保証する。
【０１２９】
レイアウトスタイル１１０３内の異なるテンプレート１１０６は、共通の特性（例えば、エレメント、事前条件、および制約）を含むことが多い。したがって、テンプレート作成ツール９１０は、実際には各テンプレート１１０６を個々に変更することなく複数のテンプレート１１０６にわたる共通の特性の修正を単純化するテンプレート１１０６継承（inheritance）のシステムまたはモデルを、サポートすることができる。限定ではなく例として、ユーザは、予め存在するテンプレート１１０６（例えば、親テンプレート１１０６）の特性を継承する新しいテンプレート１１０６（例えば、子テンプレート１１０６）を作成することができる。子テンプレート１１０６は、親テンプレート１１０６のエレメント、事前条件、および制約のすべてを自動的に含む。次いで、ユーザは、所望のカスタムテンプレート１１０６を作成するために、追加のエレメント、事前条件、および制約を子テンプレート１１０６に追加することができる。ユーザは、親と子のテンプレート１１０６間で共通のプロパティの１つを変更したい場合、修正が継承を介して親テンプレート１１０６のすべての子テンプレート１１０６に広がるので、ユーザは、親テンプレート１１０６のプロパティのみを修正する必要がある。継承モデルは、多数のテンプレート１１０６の管理を簡単にし、テンプレート１１０６間の整合性を維持するのに役立つ。
【０１３０】
通信可能に接続することは、限定ではないがアナログ、デジタル、無線および有線通信チャネルを含む任意の適切なタイプの接続を含むことができることが当業者には認識されよう。このような通信チャネルには、限定ではないが、銅線、光ファイバ、無線周波数、赤外線、衛星、または他の媒体が含まれる。
【０１３１】
図１０は、特許請求された主題の例示的な一実施形態に従って、特許請求された主題が使用することができるコンピューティング環境１０００、およびそのコンピュータシステム１０１０、１０８０を表すブロック図を示す。コンピューティング環境１０００、およびそのコンピュータシステム１０１０、１０８０は、特許請求された主題を実施するための適切なコンピューティング環境およびコンピュータシステムの一例を表すものにすぎず、本発明の使用または機能性の範囲についての限定を提示することは意図されていない。また、コンピュータシステム１０１０および１０８０は、例示的なコンピューティング環境１０００内に図示される任意のコンポーネントの１つまたはその組合せに関していかなる依存性または要件を有するものとして解釈されるべきでもない。
【０１３２】
したがって、本発明は、多くの他の汎用または専用のコンピューティングシステム環境または構成で動作可能であることを理解されたい。特許請求された主題で使用するのに適した、または適切な可能性のある、よく知られたコンピューティングシステム、環境、および／または構成の例には、限定ではないが、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップ装置、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能な家庭用電化製品、ネットワークパーソナルコンピュータ、ミニコンピュータ、メインフレームコンピュータ、上記システムまたは装置のいずれかを含む分散コンピューティング環境などが含まれる。
【０１３３】
特許請求された主題の態様を、プログラムモジュールなどの、コンピュータシステムによって実行されるコンピュータ実行可能命令を含む一般的な文脈で述べることができる。一般に、プログラムモジュールは、特定のタスクを実行し、または特定の抽象データ型を実装するルーチン、プログラム、プログラミング、オブジェクト、コンポーネント、データ、データ構造などを含む。本発明の特徴を、通信ネットワークを通じてリンクされるリモート処理装置よってタスクが実行される分散コンピューティング環境で実践することができる。分散コンピューティング環境では、プログラムモジュールを、限定ではないがメモリストレージ装置を含め、ローカルとリモートの両方のコンピュータストレージ媒体に配置することができる。
【０１３４】
図１０を参照すると、特許請求された主題の例示的なコンピュータ環境１０００は、コンピュータシステム１０１０の形式の汎用コンピューティング装置を含む。コンピュータシステム１０１０のコンポーネントは、限定ではないが、処理ユニット１０２０、システムメモリ１０３０、ならびに、データおよび／または命令の双方向通信のためにシステムメモリ１０３０を含む様々なシステムコンポーネントを処理装置１０２０に結合するシステムバス１０２１を含むことができる。システムバス１０２１は、メモリバスまたはメモリコントローラ、周辺バス、ならびに様々なバスアーキテクチャのいずれかを使用するローカルバスを含め、複数のタイプのバス構造のいずれかとすることができる。限定ではなく例として、このようなアーキテクチャには、ＩＳＡバス、ＭＣＡバス、ＥＩＳＡバス、ＶＥＳＡローカルバス、およびＰＣＩバス（すなわち、「メザニンバス」としても知られる）が含まれる。
【０１３５】
コンピュータシステム１０１０は典型的に、様々なコンピュータ読取り可能媒体を含む。コンピュータ読取り可能媒体は、コンピュータシステム１０１０がアクセスし、読み取り、書き込むことができる任意の使用可能な媒体を備えることができ、揮発性と不揮発性、およびリムーバブルと非リムーバブルの両方の媒体を含む。限定ではなく例として、コンピュータ読取り可能媒体は、コンピュータストレージ媒体および通信媒体を備えることができる。コンピュータストレージ媒体は、コンピュータ読取り可能命令、データ、データ構造、プログラムモジュール、プログラム、プログラミング、またはルーチンなどの情報を記憶するための任意の方法または技術で実装される揮発性と不揮発性、リムーバブルと非リムーバブルの両方の媒体を含む。コンピュータストレージ媒体には、限定ではないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他の光ディスクストレージ、磁気カセット、磁気テープ、磁気光学ストレージ装置、磁気ディスクストレージまたは他の磁気ストレージ装置、あるいは所望の情報を記憶するのに使用することができ、コンピュータシステム１０１０によってアクセスすることができる他の任意の媒体が含まれる。通信媒体は典型的に、コンピュータ読取り可能命令、データ、データ構造体、プログラムモジュール、プログラム、プログラミングまたはルーチンを、搬送波や他の移送機構などの変調データ信号で具現化し、任意の情報送達媒体を含む。「変調データ信号」という用語は、信号内の情報を符号化するような手法で設定または変更された１つまたは複数のその特性を有する信号を意味する。限定ではなく例として、通信媒体には、有線ネットワークや直接有線接続などの有線媒体、ならびに音響、ＲＦ、赤外線、および他の無線媒体などの無線媒体が含まれる。上記の任意のものの組合せも、コンピュータ読取り可能媒体の範囲内に含まれる。
【０１３６】
システムメモリ１０３０は、ＲＯＭ１０３１およびＲＡＭ１０３２などの揮発性および／または不揮発性メモリの形態のコンピュータストレージ媒体を含む。起動時などにコンピュータ１０１０内のエレメント間の情報の転送を命令する基本ルーチンを含む基本入出力システム（ＢＩＯＳ）１０３３は典型的に、ＲＯＭ１０３１に格納される。ＲＡＭ１３２は典型的に、処理ユニット１０２０によって直ちにアクセス可能で、および／または現在操作されているデータおよび／またはプログラム命令を格納する。限定ではなく例として、図１０は、全体または一部が時々ＲＡＭ１０３２に存在することができるオペレーティングシステム１０３４、アプリケーションプログラム１０３５、他のプログラムモジュール１０３６、およびプログラムデータ１０３７を図示する。
【０１３７】
コンピュータ１０１０は、他のリムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータストレージ媒体を含むこともできる。単に例として、図１０は、非リムーバブルな不揮発性の磁気媒体と読み書きするハードディスクドライブ１０４１、リムーバブルな不揮発性の磁気ディスク１０５２と読み書きする磁気ディスクドライブ１０５１、およびＣＤ−ＲＯＭや他の光学媒体などのリムーバブルな不揮発性の光ディスク１０５６と読み書きする光ディスクドライブ１０５５を図示する。例示的なコンピューティング環境１０００内に含むことができる他のリムーバブル／非リムーバブル、揮発性／不揮発性のコンピュータストレージ媒体には、限定ではないが、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどが含まれる。ハードディスクドライブ１０４１は典型的に、インタフェース１０４０などの非リムーバブルメモリインタフェースを通じてシステムバス１０２１に接続され、磁気ディスクドライブ１０５１および光ディスクドライブ１０５５は典型的に、インタフェース１０５０などのリムーバブルメモリインタフェースによってシステムバス１０２１に接続される。
【０１３８】
上記で説明され、図１０に図示されるドライブ１０４１、１０５１、１０５５およびこれらと関連するコンピュータストレージ媒体は、コンピュータシステム１０１０のためのコンピュータ読取り可能命令、データ、データ構造、プログラムモジュール、プログラム、プログラミング、またはルーチンのストレージを提供する。図１０では、例えばハードディスクドライブ１０４１は、オペレーティングシステム１０４４、アプリケーションプログラム１０４５、他のプログラムモジュール１０４６、およびプログラムデータ１０４７を格納するものとして図示されている。これらのコンポーネントは、オペレーティングシステム１０３４、アプリケーションプログラム１０３５、他のプログラムモジュール１０３６、およびプログラムデータ１０３７と同じであっても、異なっていてもよいことを留意されたい。オペレーティングシステム１０４４、アプリケーションプログラム１０４５、他のプログラムモジュール１０４６、およびプログラムデータ１０４７は、少なくともそれらがオペレーティングシステム１０３４、アプリケーションプログラム１０３５、他のプログラムモジュール１０３６、およびプログラムデータ１０３７の異なるコピーであることを示すために異なる番号が与えられている。ユーザは、キーボード１０６２、および一般にマウス、トラックボールまたはタッチパッドと呼ばれるポインティング装置１０６１などの接続された入力装置を通じて、コンピュータシステム１０１０にコマンドおよび情報を入力することができる。接続された他の入力装置（図示せず）は、マイクロホン、ジョイスティック、ゲームパッド、衛星放送アンテナ、またはスキャナーなどを含むことができる。これらおよび他の入力装置は、システムバス１０２１に結合されたユーザ入力インタフェース１０６０を通じて処理ユニット１０２０に接続されることが多いが、パラレルポート、ゲームポートまたはＵＳＢなどの他のインタフェースおよびバス構造体によって接続されることもある。モニタ１０９１または他のタイプのディスプレイ装置も、ビデオインタフェース１０９０などのインタフェースを介してシステムバス１０２１に接続される。モニタ１０９１に加えて、コンピュータシステム１０１０は、出力周辺インタフェース１０９５を介して接続することができるスピーカ１０９７およびプリンタ１０９６などの他の周辺出力装置を含むこともできる。
【０１３９】
コンピュータシステム１０１０は、ネットワーク化された環境で、リモートコンピュータシステム１０８０などの１つまたは複数のリモートコンピュータシステムへの双方向通信接続リンクを使用して動作することができる。リモートコンピュータシステム１０８０は、パーソナルコンピュータ、ラップトップコンピュータ、サーバコンピュータ、ルータ、ネットワークＰＣ、ピアデバイス、または他の一般的なネットワークノードとすることができ、図１０ではリモートコンピュータシステム１０８０のメモリストレージ装置１０８１だけが図示されているが、典型的には、コンピュータシステム１０１０に関して上述したエレメントの多くまたはすべてを含む。図１０に示された双方向通信接続リンクは、ＬＡＮ１０７１およびＷＡＮ１０７３を含むが、他のネットワークを含むこともできる。そのようなネットワークは、オフィス、企業規模のコンピュータネットワーク、イントラネットおよびインターネットでは一般的である。
【０１４０】
ＬＡＮ１０７１に通信可能に接続される場合は、コンピュータシステム１０１０は、ネットワークインタフェースまたはアダプタ１０７０を通じてＬＡＮ１０７１に接続する。ＷＡＮ１０７３に通信可能に接続される場合は、コンピュータシステム１０１０は典型的に、モデム１０７２、またはインターネットなどのＷＡＮ１０７３を介して通信リンクを確立するための他の手段を含む。内蔵または外付けとすることができるモデム１０７２を、ユーザ入力インタフェース１０６０または他の適切な機構を介してシステムバス１０２１に接続することができる。ネットワーク化された環境では、コンピュータシステム１０１０に関して示したプログラムモジュール、またはその一部を、リモートメモリストレージ装置１０８１に格納することができる。限定ではなく例として、図１０は、リモートアプリケーションプログラム１０８５をメモリ記憶装置１０８１に存在するものとして図示している。示されたネットワーク接続は例示的なものであり、コンピュータ間の双方向通信リンクを確立する他の手段を使用することができることは理解されよう。
【０１４１】
図１１は、特許請求された主題の例示的な一実施形態による、適応レイアウトスタイル１１０３およびテンプレート１１０６を含む文書レイアウトを表すブロック図を示す。文書コンテンツ９０４は、テンプレートストレージユニット９０８に格納されたテンプレート１１０６（例えば、本明細書では「適応テンプレート１１０６」と呼ばれることもある）の使用によって、特定の文書レイアウトにフォーマットされる。それぞれのテンプレート１１０６は、ページ寸法の範囲にわたるコンテンツの単一ページのレイアウトの定義に関与する。特許請求された主題の例示的な実施形態では、テンプレート１１０６は、代替の文書コンテンツ（例えば、より広いバージョンのイメージ、または最適な描画）が文書のページレイアウト全体を改善させる場合には、代替の文書コンテンツを自動的に選択できるようにするプロトコルをサポートする。また、それぞれのテンプレート１１０６は、表示寸法の範囲、ならびにフォントサイズの増加などの他のタイプの表示条件に適応するようにデザインされる。
【０１４２】
それぞれのテンプレート１１０６はさらに、レイアウトエレメント１１１２、制約ベース関係１１１５、および事前条件１１０９を含むことができる。レイアウトエレメント１１１２は、コンテンツを配置することができるテンプレート１１０６のページ内の特定の領域を表す。テンプレート１１０６の制約ベース関係１１１５は、エレメント１１１２間の関係を定義するのに役立つ。テンプレート１１０６の事前条件１１０９は、文書の特定のコンテンツまたはページの特性に対するテンプレート１１０６の適合性を特徴付ける。レイアウトエレメント１１１２、制約ベース関係１１１５、および事前条件１１０９について、以下で図１２に関してより十分に説明する。
【０１４３】
特許請求された主題の一実施形態では、文書レイアウトは、１組のテンプレート１１０６を使用して記述される。文書コンテンツ９０４がテンプレート１１０６に適用されるとき、適応グリッドベース文書９１４は、最適なフォーマットで作成される。例えば、本システムは、Ｎｅｗ  Ｙｏｒｋ  Ｔｉｍｅｓ、Ｎｅｗ  Ｙｏｒｋｅｒ、Ｗａｓｈｉｎｇｔｏｎ  Ｐｏｓｔ、Ｎｅｗｓｗｅｅｋ、またはＴｉｍｅマガジンに使用されるデザインなど、広範囲の現代的なグリッドベースレイアウトスタイルをサポートすることができる。レイアウトスタイル１１０３（例えば、本明細書では「適応レイアウトスタイル１１０３」呼ばれることもある）はそれぞれ、特定のレイアウトスタイル１１０３の特定の特性を実装するテンプレート１１０６の集合によって定義される。
【０１４４】
図１１に図示されるように、適応レイアウトスタイル１１０３Ａは、１組のテンプレート１１０６Ａ1、１１０６ＡNによって表される。適応テンプレート「Ａ1」１１０６Ａ1と適応テンプレート「ＡN」１１０６ＡNの間の省略記号は、適応レイアウトスタイル「Ａ」１１０３Ａ内に複数の適応テンプレート１１０６が存在することができ、したがって、適応レイアウトスタイル「Ａ」１１０３Ａは、図１１に示されるような２つの適応テンプレート１１０６Ａ1、１１０６ＡNには限定されないことを示す。同様に、適応テンプレート「Ｚ1」１１０６Ｚ1と適応テンプレート「ＺN」１１０６ＺNの間の省略記号は、適応レイアウトスタイル「Ｚ」１１０３Ｚ内に複数の適応テンプレート１１０６が存在することができ、したがって、図１１に示されるような２つの適応テンプレート１１０６Ｚ1、１１０６ＺNには限定されないことを示す。さらに、ある適応レイアウトスタイル１１０３Ａは、別の適応レイアウトスタイル１１０３Ｚとは異なる数の適応テンプレート１１０６を備えることができる。
【０１４５】
適応レイアウトスタイル１１０３は、テンプレートストレージユニット９０８に格納される。それぞれの適応レイアウト１１０３は、それに関連付けられる１組のテンプレート１１０６を識別する。適応レイアウトスタイル「Ａ」１１０３Ａと適応レイアウトスタイル「Ｚ」１１０３Ｚの間の省略記号は、テンプレートストレージユニット９０８内に複数の適応レイアウトスタイル１１０３が存在することができ、したがって、図１１に示されるような２つの適応レイアウトスタイル１１０３Ａ、１１０３Ｚに限定されないことを示す。限定ではなく例として、適応レイアウトスタイル１１０３および適応テンプレート１１０６を、ＸＭＬによって、特許請求された主題内に表すことができる。
【０１４６】
図１２は、特許請求された主題の例示的な一実施形態による適応テンプレート１１０６を表すブロック図を示す。テンプレートストレージユニット９０８内の各適応テンプレート１１０６は、レイアウトエレメント１１１２、エレメント１１１２間の関係を定義するための制約ベース関係１１１５、および文書の特定のコンテンツについてのテンプレート１１０６の適合性を特徴付ける事前条件１１０９を備えることができる。
【０１４７】
レイアウトエレメント１１１２は、コンテンツを置くことができるテンプレート１１０６のページ内の特定の領域を表す。典型的に、グリッドベースの文書レイアウト内のエレメント１１１２は、テンプレート１１０６のページの矩形の領域である。各レイアウトエレメント１１１２は、指定ソースストリーム変数（specified source stream variable）１２０９、エレメントｚ順配置変数（element z-order placement variable）１２１２、レイアウトテンプレート変数（layout templates variable）１２１５を備える。指定ソースストリーム変数１２０９は、エレメント１１１２内でどのコンテンツを使用することができるかを指定する。限定ではなく例として、指定ソースストリーム変数１２０９は、イメージだけをテンプレート１１０６のエレメント１１１２内に置くことができることを指定することがある。特許請求された主題の代替の一実施形態では、複数のエレメント１１１２は、同じコンテンツストリーム１３０３（図１３に関して以下で述べる）からのコンテンツを使用する。このような配置では、フローが確立され、コンテンツストリーム１３０３のコンテンツは、あるエレメント１１１２Ａ1から次のエレメント１１１２Ａ2に分配される。
【０１４８】
エレメント１１１２のエレメントｚ順配置変数１２１２は、各エレメント１１１２がその位置をエレメント１１１２のｚ順で指定することを可能にする。一般に、ｚ順の上位のエレメント１１１２は、文書レイアウト内の下位のエレメント１１１２の上に位置し、したがって、上位のエレメント１１１２の面積領域は、その下にあるエレメント１１１２の面積領域から取り去られる。実際に、エレメントｚ順配置変数１２１２は、グリッドベースのページデザインが、オーバーラップしたエレメント１１１２、または他のエレメント１１１２の領域を切り取るように見える領域を有することを可能にする。例えば、文書レイアウト内のテキストは、図の周りを流れることができる。図は、テキストより高いｚ順にあり、したがって、図は、テキスト用にリザーブされた領域の一部を切り取るように見える。図またはイメージの周りをテキストで包むことは、グリッドベース文書レイアウト内で使用される技術である。
【０１４９】
レイアウトテンプレート変数１２１５は、各エレメント１１１２が、コンテンツアトム（content atom）をレイアウトするのに使用することができるレイアウトテンプレート１１０６（またはレイアウトテンプレート１１０６の集合）を指定することを可能にする。コンテンツアトムは、複数のコンテンツストリーム１３０３（例えば、テキスト、図、またはイメージ）で構成されるコンテンツアイテム１３０６を備える。より具体的には、コンテンツアトムは、１つまたは複数のエレメント１１１２、あるいは１つまたは複数のコンテンツタイプのコンテンツストリーム１３０３を含むコンテンツの論理グループを備え、それはすべて、ある親コンテンツアイテム１３０６内の単一アイテムと見なされる。限定ではなく例として、エレメント１１１２は、テキスト、図、およびイメージを含むサイドバーを表すことができる。レイアウトテンプレート変数１２１５を通じて、テンプレート１１０６は、再帰的なレイアウトを十分にサポートすることができ、したがって、図／キャプションの組合せからコンテンツの再帰的な組込み（recursive embedding）まで、すべてをサポートすることができる。
【０１５０】
テンプレート１１０６の制約ベース関係１１１５（例えば、本明細書では「制約１１１５」と呼ばれることもある）を使用して、少なくとも部分的にエレメント１１１２間の関係を定義することができる。テンプレート１１０６内のエレメント１１１２それぞれのサイズおよび配置は、一緒に考慮される場合に有向非巡回グラフ（directed acyclic graph）を形成する１組の相互依存型の（interdependent）制約ベース関係１１１５を評価することによって決定される。制約ベース関係１１１５は、その値が他の制約変数（constraint variable）１２１８、１２２１に関する数式によって決定される制約入力変数（constraint input variable）１２１８、および制約出力変数（constraint output variable）１２２１を備える。さらに、制約ベースの関係１１１５は、制約出力変数１２２１の値を計算するときにその値を使用することができる制約内部変数（constraint internal variable）１２２４を備える。このタイプの構成は、「一方向の制約システム」として知られることが、当業者には認識されよう。しかし、特許請求された主題の例示的な実施形態では、それぞれのテンプレート１１０６は、レイアウトエレメント１１１２の中の二次元の関係を、特定のレイアウトを評価するために解決しなければならない制約１１１５として符号化する。
【０１５１】
制約入力変数１２１８は、テンプレート１１０６が使用されるコンテキストについてテンプレート１１０６に指示する。限定ではなく例として、制約入力変数１２１８は、テンプレート１１０６の、またはテンプレート１１０６内のエレメント１１１２の幅および高さの寸法を示すことができる。さらに、制約入力変数１２１８は、文書コンテンツに関するカスタム属性（例えば、テンプレート作成ツール９１０を通じてユーザによって定義される属性）を含むことができる。特許請求された主題の態様では、制約システム（図示せず）を、制約入力変数１２１８および制約出力変数１２２１として使用することができる制約のプールによって表すことができる。カスタム属性が文書コンテンツ９０４内に存在する場合は、カスタム属性を制約システム内の追加の変数として追加することができる。制約出力変数１２２１は、限定ではないが各エレメント１１１２の矩形境界、およびテンプレート１１０６のスコアを含む様々な文書出力属性を表し、このテンプレート１１０６のスコアは、テンプレート１１０６が、テンプレート１１０６内に挿入されるべきコンテンツに関してその適合性を表すことを可能にする（図１０に関して以下でより詳細に述べる）。
【０１５２】
テンプレート１１０６の事前条件１１０９は、少なくとも部分的に文書の特定のコンテンツに対するテンプレート１１０６の適合性を特徴付ける。各テンプレート１１０６は、文書コンテンツに適用される場合にテンプレート１１０６が、いつ有効であるかを表すために事前条件１１０９を使用する。例えば、テンプレート１１０６を文書コンテンツにうまく適用することができる場合、テンプレート１１０６は有効となり得る。どのテンプレート１１０６が有効であり、どのテンプレート１１０６が無効であるかを決定するために、異なる事前条件を使用することができることを、当業者は認識されよう。適応グリッドベース文書レイアウトシステム９０２は、ページネーション（図１９に関して以下でより詳細に述べる）の間、事前条件１１０９を使用する。事前条件１１０９は、１つまたは複数のコンテンツ事前条件変数（content preconditions variable）１２０３および／または１つまたは複数の値事前条件変数（value preconditions variable）１２０６を備えることができる。コンテンツ事前条件変数１２０３は、テンプレート１１０６またはテンプレート１１０６内のエレメント１１１２を適切に埋めるために存在しなければならない所与のコンテンツストリーム１３０３からのコンテンツの量を示す。値事前条件変数１２０６は、所与の制約変数１２１８、１２２１が収まらなければならない値の範囲を示す。限定ではなく例として、コンテンツ事前条件変数１２０３および値事前条件変数１２０６は、文書コンテンツがディスプレイに使用可能なちょうど２つの図を含む場合、および文書コンテンツのページ寸法が標準文字（standard letter）とＡ４ページ寸法の間のどこかに収まる場合に、特定のテンプレート１１０６が有効であることを示すことができる。
【０１５３】
図１３は、特許請求された主題の例示的な一実施形態によるコンテンツストリーム１３０３を含む文書コンテンツ９０４のブロック図を示す。文書コンテンツ９０４を、順次レイアウトされるコンテンツをそれぞれが含む個々のコンテンツストリーム１３０３のセットとして、本発明内に表す。コンテンツストリーム１３０３は、限定ではないが本文、サイドバー、図、引用（pull quote）、およびフォトクレジット（photo credit）を含め、文書の論理的に独立した異なる部分を表す。コンテンツストリーム１３０３は、図１４に関して以下でより十分に説明されるコンテンツアイテム１３０６を備える。省略記号によって図示されるように、文書コンテンツ９０４は、図１３に示されるコンテンツストリーム１３０３Ａ、１３０３Ｂ、１３０３Ｚの数に限定されない。同様に、省略記号は、コンテンツストリーム１３０３Ａが、図１３に示されるコンテンツアイテム１３０６Ａ1、１３０６Ａ2、１３０６ＡNの数に限定されないことを示す。
【０１５４】
図１４は、特許請求された主題の例示的な一実施形態による、コンテンツアイテム１３０６を含むコンテンツストリーム１３０３のブロック図を示す。図１３に関して上述したように、コンテンツストリーム１３０３は、コンテンツアイテム１３０６を備える。コンテンツアイテム１３０６は、限定ではないが、テキスト、イメージ、オーディオ、ビデオ、および他の適切なコンテンツタイプを含む。それぞれのコンテンツアイテム１３０６は、構造を示す標準のマークアップ（例えばＸＭＬ）に関連付けられる。標準のマークアップに加えて、それぞれのコンテンツアイテム１３０６に、コンテンツアイテム１３０６が低水準エンジン５０２およびテンプレート１１０６によって処理される方法を変更するカスタム属性１４０９で、注釈付けすることができる。限定ではなく例として、イメージを表すコンテンツアイテム１３０６は、文書レイアウト内のイメージの重要性を表す属性１４０９を有することができる。したがって、テンプレート１１０６内のコンテンツアイテム１３０６を使用する低水準エンジン５０２は、最終レイアウトでイメージをどの程度大きくするかを決定するために属性１４０９の値をチェックすることができる。属性「Ａ1A」１４０９Ａ1Aと属性「Ａ1Z」１４０９Ａ1Z間の省略記号は、複数の属性１４０９がコンテンツアイテム「Ａ1」１３０６Ａ1内に存在することができ、したがって、コンテンツアイテム「Ａ1」１３０６Ａ1は、図１４に示されるような２つの属性１４０９Ａ1A、１４０９Ａ1Zには限定されないことを示す。同様に、属性「ＡNA」１４０９ＡNAと属性「ＡNZ」１４０９ＡNZ間の省略記号は、複数の属性１４０９がコンテンツアイテム「ＡN」１３０６ＡN内に存在することができ、したがって、コンテンツストリーム「ＡN」１３０６ＡNは、図１４に示されるような２つの属性１４０９ＡNA、１４０９ＡNZに限定されないことを示す。
【０１５５】
特許請求された主題の例示的な実施形態では、テキストコンテンツアイテム１３０６Ａ1は、文書コンテンツ９０４内のテキストのスタイルを指定するスタイル識別子１４１２1A、Ａ１４１２Ａ1Zを含むことができる。スタイル識別子１４１２は典型的に、限定するではないがカスケードスタイルシート（ＣＳＳ：cascading style sheet）または拡張可能スタイル言語（ＸＳＬ：extensible style language）などの、スタイルシート言語によって表される。スタイルシート言語は、異なるテキストが文書内でどのように現れるか（例えば、フォント、フォントスタイル、およびフォントサイズ）をユーザが定義することを可能にすることが、当業者には認識されよう。したがって、スタイル識別子１４１２を、スタイルシートストレージユニット９０６に格納される別個のスタイルシートファイル内のフォーマット規則（formatting rule）に関連付けることができる。スタイル識別子「ＡlA」１４１２Ａ1Aとスタイル識別子「Ａ1Z」１４１２Ａ1Zの間の省略記号は、複数のスタイル識別子１４１２がコンテンツアイテム「Ａ1」１３０６Ａ1内に存在することができ、したがってコンテンツアイテム「Ａ1」１３０６Ａ1は、図１４に示されるような２つのスタイル識別子１４１２Ａ1A、１４１２Ａ1Zには限定されないことを示す。同様に、スタイル識別子「ＡNA」１４１２ＡNAとスタイル識別子「ＡNZ」１４１２ＡNZの間の省略記号は、複数のスタイル識別子１４１２がコンテンツアイテム「ＡN」１３０６ＡN内に存在することができ、したがって、コンテンツアイテム「ＡN」１３０６ＡNは、図１４に示されるような２つのスタイル識別子１４１２ＡNA、１４１２ＡNZには限定されないことを示す。
【０１５６】
コンテンツアイテム１３０６を、任意の１つのコンテンツの複数のバージョン１３０６Ａ2A、１３０６Ａ2B、１３０６Ａ2Zを含むように符号化することもできる。異なるコンテンツアイテムのバージョン１３０６Ａ2A、１３０６Ａ2B、１３０６Ａ2Zはそれぞれ、＜ｍｕｌｔｉ＞タグ１４０６内でパッケージ化される。文書をレイアウトする間、適応グリッドベース文書レイアウトシステム９０２は、ページをテンプレート１１０６でフォーマットするときに使用するバージョンの１つを選択する。適応グリッドベース文書レイアウトシステム９０２に役立つように、異なるコンテンツアイテムのバージョン１３０６Ａ2A、１３０６Ａ2B、１３０６Ａ2Zはそれぞれ、特定の各コンテンツアイテムバージョン１３０６Ａ2A、１３０６Ａ2B、１３０６Ａ2Zの最も適切な使用について提示する属性１４０９を含むことができる。限定ではなく例として、コンテンツアイテムの第１のバージョン「Ａ2」１３０６Ａ2Aは、「ｓｕｍｍａｒｙ」セクションで最も使用されるコンテンツアイテム１３０６Ａ2Aの第１のバージョンであることを示すことができ、コンテンツアイテムの第２のバージョン「Ａ2」１３０６Ａ2Bは、サイドバーで最も使用されるコンテンツアイテム１３０６Ａ2Bの第２のバージョンであることを示すことができる。テンプレート１１０６は、テンプレート１１０６が文書コンテンツをどのようにフォーマットすることを意図しているかに基づいて、適切なコンテンツアイテムバージョン１３０６Ａ2A、１３０６Ａ2B、１３０６Ａ2Zを選択することができる。コンテンツアイテム１３０６の異なるバージョンを定義するための属性１４０９が存在しない場合は、適応グリッドベース文書レイアウトシステム９０２は、現在のページまたは文書のフォーマットに最もよく機能するバージョンを自由に選択することができる。コンテンツアイテムの第２のバージョン「Ａ2」１３０６Ａ2Bとコンテンツアイテムの第ｎのバージョン「Ａ2」１３０６Ａ2Zの間の省略記号は、複数のコンテンツアイテム１３０６バージョンが＜ｍｕｌｔｉ＞タグ１４０６内に存在することができ、したがって、＜ｍｕｌｔｉ＞タグ１４０６は、図１４に示されるような３つのコンテンツアイテムのバージョン１３０６Ａ2A、１３０６Ａ2B、１３０６Ａ2Zには限定されないことを示す。
【０１５７】
コンテンツストリーム１３０３Ａ3A、１３０３Ａ3B、１３０３Ａ3Zを、＜ａｔｏｍ＞タグを使用して親コンテンツアイテム１３０６Ａ3内に階層的にネストすることもでき、この＜ａｔｏｍ＞タグは、コンテンツストリーム１３０３Ａ3A、１３０３Ａ3B、１３０３Ａ3Zの集合を一緒に、親コンテンツアイテム１３０６Ａ3内のコンテンツアトムとしてグループ化する。次いで、コンテンツストリーム１３０３Ａ3A、１３０３Ａ3B、１３０３Ａ3Zの集合は、単一のコンテンツアイテム１３０６Ａ3として扱われる。サイドバーなどの文書エレメントは本質的に、複数の文書エレメント（例えば、テキスト、図、キャプション、およびフッター）によって表される。＜ａｔｏｍ＞タグは、文書レイアウトの目的で、複数のコンテンツストリーム１３０３をコンテンツの１つの単一アイテムとして扱うことを可能にする。限定ではなく例として、＜ａｔｏｍ＞タグは、親「サイドバー」コンテンツアイテム１３０６内の「タイトル」コンテンツストリーム１３０３、「図」コンテンツストリーム１３０３、「図キャプション」コンテンツストリーム１３０３、「説明文」コンテンツストリーム１３０３、および「フッター」コンテンツストリーム１３０３をグループ化することができる。コンテンツストリーム１３０３Ａ3Bとコンテンツストリーム１３０３Ａ3Zの間の省略記号は、複数のコンテンツストリーム１３０３が親コンテンツアイテム１３０６Ａ3内に存在することができ、したがって、親コンテンツアイテム１３０６Ａ3は、図１４に示されるような３つのコンテンツストリーム１３０３Ａ3A、１３０３Ａ3B、１３０３Ａ3Zには限定されないことを示す。
【０１５８】
図１５Ａ〜図１５Ｂは、特許請求された主題の例示的な一実施形態により、文書コンテンツ９０４をテンプレート１１０６に適用する方法１５００のフローチャートを示す。低水準エンジン５０２は、ページネータ６０２から受け取られた文書コンテンツ９０４と、テンプレートストレージユニット９０８からのテンプレート１１０６、およびスタイルシートストレージユニット９０６からのスタイルシートを結合する。その結果、文書のレイアウトスタイルを定義する潜在的なページレイアウトの集合がもたらされる。
【０１５９】
ステップ１５０１で開始した後、低水準エンジン５０２は、ステップ１５０３に進み、文書コンテンツ９０４を使用してさらなるテンプレート１１０６を評価する必要があるかどうかを判断する。最初は、テンプレートストレージユニット９０８内のテンプレート１１０６のいずれも評価されない。しかし、ステップ１５０３が繰り返されると、低水準エンジン５０２は、すべてのテンプレート１１０６が考慮されるまで、テンプレートストレージユニット９０８内の使用可能な他のテンプレート１１０６を考慮する。あるいは、低水準エンジン５０２は、テンプレートストレージユニット９０８内のすべてのテンプレート１１０６を評価する代わりに、ステップ１５０３の前（図示せず）にページネータ６０２によって提供されるデータ構造（例えば、配列、またはベクトル）内のすべてのテンプレート１１０６を評価する。低水準エンジン５０２は、ステップ１５０３でさらなるテンプレート１１０６を評価する必要はないと判断する場合、後述されるステップ１５２７に進む。しかし、低水準エンジン５０２は、ステップ１５０３でさらなるテンプレート１１０６を評価する必要があると判断する場合は、ステップ１５０６に進み、現在考慮されているテンプレート１１０６（例えば、本明細書では「現在のテンプレート１１０６」とも呼ばれる）の事前条件１１０９が、現在の文書コンテンツ９０４に対して評価される。次に、低水準エンジン５０２は、ステップ１５０９で現在のテンプレート１１０６は考慮されている文書コンテンツ９０４に有効であるかどうか判断する。
【０１６０】
低水準エンジン５０２は、ステップ１５０９で現在のテンプレート１１０６は考慮されている文書コンテンツ９０４に有効でないと判断する場合は、上述のステップ１５０３に進む。しかし、低水準エンジン５０２は、ステップ１５０９で現在のテンプレート１１０６は考慮されている文書コンテンツ９０４に有効であると判断する場合は、ステップ１５１２に進み、現在のテンプレートの入力変数１２１８を設定すること、ならびに単純な欲張りローカル伝搬（greedy local propagation）を使用して現在のテンプレートの制約グラフを通じてこれらの値を前方に伝搬することによって、テンプレート１１０６の各エレメント１１１２のサイズおよび位置を決定する。
【０１６１】
次いで、低水準エンジン５０２は、ステップ１５１５でテンプレート１１０６によって生成されるべきレイアウトページの二次元の領域を計算し、この二次元領域内に文書コンテンツ９０４が流されることとなる。さらに、低水準エンジン５０２は、エレメント１１１２間の任意のオーバーラップに従って、またはエレメントｚ順配置変数１２１２に基づいて、領域を縮小する。次に、低水準エンジン５０２は、ステップ１５１８で、決定された各領域に文書コンテンツ９０４を流す。次いで、低水準エンジン５０２は、ステップ１５２１に進み、文書コンテンツ９０４がどの程度よくテンプレート１１０６に適合するかに基づいて、テンプレート１１０６のテンプレートスコア（図１０に関して以下により詳細に述べる）を計算する。次に、低水準エンジン５０２は、ステップ１５２４でテンプレート１１０６を有効なテンプレート１１０６のセットまたはシーケンスに追加する。次いで、低水準エンジン５０２は、上述のステップ１５０３に進む。
【０１６２】
上述されるように、低水準エンジン５０２は、ステップ１５０３でさらなるテンプレート１１０６を評価する必要がないと判断する場合は、ステップ１５２７に進み、有効なテンプレート１１０６のセットが空かどうか判断する。低水準エンジン５０２は、ステップ１５２７で有効なテンプレート１１０６のセットは空であると判断する場合は、低水準エンジン５０２は、ステップ１５３６に進み、文書コンテンツ９０４に有効なテンプレート１１０６のセットが存在しないことのエラーを生成する。次いで、低水準エンジン５０２は、ステップ１５３３で方法１５００による操作を終了する。しかし、低水準エンジン５０２は、ステップ１５２７で有効なテンプレート１１０６のセットが存在すると判断する場合は、ステップ１５３０に進み、有効なテンプレート１１０６のセット、および対応するスコアをページネータ６０２に送る。次いで、低水準エンジン５０２は、ステップ１５３３で方法１５００による操作を終了する。
【０１６３】
図１６Ａ〜図１６Ｃは、特許請求された主題の例示的な一実施形態による、文書レイアウト内のエレメント１１１２にコンテンツを流す方法１６００のフローチャートを示す。低水準エンジン５０２は、コンテンツタイプに従ってエレメント領域へのコンテンツの流れを制御する。一般に、コンテンツタイプには、限定ではないが、イメージ、テキスト、インライン図、およびメディアが含まれる。
【０１６４】
ステップ１６０１で開始した後、低水準エンジン５０２は、ステップ１６０３に進み、コンテンツタイプがイメージかどうか判断する。低水準エンジン５０２は、ステップ１６０３でコンテンツタイプがイメージであると判断する場合は、ステップ１６０６に進み、イメージを適切なエレメント１１１２の境界領域に適合するようにスケーリングする。次に、低水準エンジン５０２は、ステップ１６０９でエレメント１１１２のコンテンツ領域によって切り取られた（crop）イメージを表示する。次いで、低水準エンジン５０２は、ステップ１６１８で方法１６００による操作を終了する。
【０１６５】
しかし、低水準エンジン５０２は、ステップ１６０３でコンテンツタイプがイメージでないと判断する場合、ステップ１６１２に進み、コンテンツタイプがテキストかどうか判断する。低水準エンジン５０２は、、ステップ１６１２でコンテンツタイプがテキストであると判断する場合、ステップ１６１５に進み、限定ではないがＫｎｕｔｈおよびＰｌａｓｓの最適改行アルゴリズムなどの、改行アルゴリズムを使用して、テキストがエレメント１１１２の境界領域に流れることを可能にする。次いで、低水準エンジン５０２は、ステップ１６１８で方法１６００による操作を終了する。
【０１６６】
しかし、低水準エンジン５０２は、ステップ１６１２でコンテンツタイプがテキストでないと判断する場合は、ステップ１６２１に進み、コンテンツタイプがインライン図（例えば、テキストの流れの中に生じる図）かどうか判断する。低水準エンジン５０２は、ステップ１６２１でコンテンツタイプがインライン図であると判断する場合は、ステップ１６２４に進み、エレメント１１１２の境界領域内に図を表示する余地があるかどうか判断する。低水準エンジン５０２は、ステップ６２４でエレメント１１１２の境界領域内に図を表示する余地があると判断する場合は、ステップ１６３０に進み、指定された参照位置に図を置き、エレメント１１１２のカラム全体を埋めるように図をサイズ変更する。次いで、低水準エンジン５０２は、ステップ１６３３で方法１６００による操作を終了する。一方、低水準エンジン５０２は、ステップ１６２４でエレメント１１１２の境界域が図を表示するには十分なサイズではないと判断する場合は、ステップ１６２７に進み、フローの次のエレメント１１１２内の図を表示し、次のエレメント１１１２のカラム全体を埋めるように図をサイズ変更する。次いで、低水準エンジン５０２は、ステップ１６３３で方法１６００による操作を終了する。
【０１６７】
しかし、低水準エンジン５０２は、ステップ１６２１でコンテンツタイプがインライン図でないと判断する場合は、ステップ１６３６に進み、コンテンツタイプがメディアかどうか判断する。低水準エンジン５０２は、ステップ１６３６で、コンテンツタイプがメディアであると判断する場合は、ステップ１６４２に進み、指定された参照位置にメディアタイプを組み込む。次いで、低水準エンジン５０２は、ステップ１６４５で方法１６００による操作を終了する。一方、低水準エンジン５０２は、ステップ１６３６でコンテンツタイプがメディアでないと判断する場合は、ステップ１６３９に進み、無効なコンテンツタイプを示すエラーを生成する。次いで、低水準エンジン５０２は、ステップ１６４５で方法１６００による操作を終了する。
【０１６８】
図１７Ａ〜図１７Ｃは、特許請求された主題の例示的な一実施形態による、文書レイアウト内でエレメント１１１２を自己サイズ調整する（self-sizing）方法１７００のフローチャートを示す。低水準エンジン５０２は、その高さを文書コンテンツ９０４に適合するように自動的に調整するエレメント１１１２をサポートする。エレメント１１１２の自動なサイズ変更は、コンテンツタイプに依存する。
【０１６９】
ステップ１７０１で開始した後、低水準エンジン５０２は、ステップ１７０３に進み、エレメント１１１２がイメージエレメントかどうか判断する。低水準エンジン５０２は、ステップ１７０３でエレメント１１１２がイメージエレメントであると判断する場合は、ステップ１７０６に進み、エレメント１１１２にイメージのピクセル寸法を提供するために、エレメント１１１２に関連付けられる制約変数１２１８、１２２１を設定する。次に、低水準エンジン５０２は、ステップ１７０９で、エレメント１１１２の適切な高さおよび幅を決定するために、ピクセル寸法からイメージの縦横比を計算する。次いで、低水準エンジン５０２は、ステップ１７１２で方法１７００による操作を終了する。
【０１７０】
しかし、低水準エンジン５０２は、ステップ１７０３でエレメント１１１２がイメージエレメントでないと判断する場合は、ステップ１７１５に進み、エレメント１１１２がテキストエレメントかどうか判断する。低水準エンジン５０２は、ステップ１７１５でエレメント１１１２がテキストエレメントであると判断する場合は、ステップ１７１８に進み、低水準エンジン５０２は、エレメント１１１２が、限定ではないが「ｒｅｓｉｚｅ−ｔｏ−ｃｏｎｔｅｎｔ」タグなどの所定のマークまたは属性を備えるかどうかを判断する。低水準エンジン５０２は、ステップ１７１８でエレメント１１１２が「ｒｅｓｉｚｅ−ｔｏ−ｃｏｎｔｅｎｔ」タグでマーク付けされないと判断する場合は、エレメント１１１２のサイズ変更が必要ではないため、ステップ１７１２で方法１７００による操作を終了する。
【０１７１】
低水準エンジン５０２は、ステップ１７１８でエレメント１１１２が「ｒｅｓｉｚｅ−ｔｏ−ｃｏｎｔｅｎｔ」タグでマーク付けされると判断する場合は、ステップ１７２１に進み、エレメント１１１２の高さ変数（height variable）を許容可能な最大値に設定する。次に、低水準エンジン５０２は、ステップ１７２４で、エレメント１１１２がテキストで完全に埋められるかどうか判断する。低水準エンジン５０２は、ステップ１７２４でエレメント１１１２がテキストで完全に埋められると判断する場合は、エレメント１１１２のサイズ変更が必要ではないため、ステップ１７３０で方法１７００による操作を終了する。しかし、低水準エンジン５０２は、ステップ１７２４でエレメント１１１２がテキストで完全には埋められないと判断する場合は、ステップ１７２７に進み、エレメント１１１２の高さをテキストの実際の高さに再設定する。次いで、低水準エンジン５０２は、ステップ１７３０で方法１７００による操作を終了する。
【０１７２】
しかし、低水準エンジン５０２は、ステップ１７１５でエレメント１１１２がテキストエレメントでないと判断する場合は、ステップ１７２７に進み、エレメント１１１２がレイアウト用のテンプレート１１０６を必要とする複合エレメントかどうか判断する。コンテンツアトムは、まとめると原子単位（atomic unit）と見なされる、２つまたはそれ以上のコンテンツの部分を表す。限定ではなく例として、ピクチャおよび対応するキャプションは一緒に、単一の「キャプション付きの図（captioned figure）」として概念的にグループ化される。したがって、複合エレメントは、コンテンツアトムを受け入れることができるテンプレート内のエレメントである。コンテンツアトムの内部の別個のサブコンテンツの部分をレイアウトするために、複合エレメントは、レイアウトページ上のコンテンツアトムの別個のサブパート（subpart）を配置するために使用することができる別個のサブテンプレートを指定する。ステップ１７２７で、低水準エンジン５０２は、エレメント１１１２が、レイアウト用のテンプレート１１０６を必要とする複合エレメントでないと判断する場合は、サイズ変更が必要とされないため、ステップ１７３０で方法１７００による操作を終了する。
【０１７３】
しかし、低水準エンジン５０２は、ステップ１７２７でエレメント１１１２がレイアウト用のテンプレート１１０６を必要とする複合エレメントであると判断する場合は、ステップ１７３３に進み、必要なテンプレート１１０６を使用して、エレメント１１１２をレイアウトする。複合エレメントは、限定ではないがコンテンツアトム１３０６Ａ3などの、複数のコンテンツアイテム１３０６または複数のコンテンツストリーム１３０３を含むことができる。次いで、低水準エンジン５０２は、ステップ１７３６に進み、特別な出力変数１２２１を使用して、テンプレート１１０６内のエレメント１１１２の最終的な高さを設定する。次いで、低水準エンジン５０２は、ステップ１７３９で方法１７００による操作を終了する。
【０１７４】
図１８は、特許請求された主題の例示的な一実施形態による、文書コンテンツ９０４がテンプレート１１０６にどの程度よく適合するかに基づいてテンプレート１１０６をスコアリングする方法１８００のフローチャートを示す。低水準エンジン５０２は、文書コンテンツ９０４をレイアウトするために使用される各テンプレート１１０６について、コンテンツがテンプレート１１０６にどの程度適合するかに基づいて、スコアを計算する。低水準エンジン５０２は、潜在的なテンプレート１１０６のすべてのスコアを計算すると、ページネータ６０２にスコアを報告し、ページネータ６０２は、そのスコアをコンテンツの前後のページのテンプレートスコアとともに使用して、すべての文書コンテンツ９０４をページネーションするのに使用するテンプレート１１０６の最適なシーケンスを計算する。
【０１７５】
ステップ１８０１で開始した後、低水準エンジン５０２は、ステップ１８０３に進み、テンプレート１１０６のテンプレートスコアを備える制約出力変数１２２１を評価する。次いで、低水準エンジン５０２は、ステップ１８０６に進み、テンプレート１１０６を適用した後のページレイアウト内のウイドウおよびオーファンの数を決定する。次いで、低水準エンジン５０２は、ステップ１８０９で、コンテンツがテンプレート１１０６にどの程度よく適合するかのスコアを計算し、それによって、品質スコアは、テンプレートスコア変数（ｔｅｍｐｌａｔｅ．ｓｃｏｒｅ  ｖａｒｉａｂｌｅ）、ならびにページレイアウト内のウイドウおよびオーファンの数に基づく。低水準エンジン５０２は、ステップ１８１２に進み、ページネータ６０２にテンプレート１１０６の計算されたスコアを提供し、ページネータ６０２は、このスコアをテンプレート１１０６の最終シーケンスの計算に使用する。次いで、ページネータ６０２は、ステップ１８１５で方法１８００による操作を終了する。
【０１７６】
ページネータ６０２は、テンプレート１１０６のシーケンス、およびシーケンスの各テンプレート１１０６への文書コンテンツ９０４のマッピングを作成し、低水準エンジン５０２は、このマッピングを、文書全体を表示するために使用することができる。特許請求された主題の一実施形態では、適応グリッドベース文書システム９０２は、異なるアプリケーションのための複数のページネーションアルゴリズムを使用する。したがって、適応グリッドベース文書システム９０２は、インタラクティブなアプリケーションに有効なページネーションを迅速に生成する第１のページネータ６０２と、最適なページネーションをもたらすが操作により多くの時間を要する第２のページネータ６０２とを備えることができる。第１のページネータ６０２は、文書内の現在の位置にコンテンツを受け入れる各ページについて第１のテンプレート１１０６を常に使用する「欲張り（greedy）」アルゴリズムを使用することがあり、あるいは選択の大域的な結論（global consequence）（例えば、グローバルスコアリング）を評価せずにシーケンス内の各場所で単一の最良テンプレート１１０６を選択することがある。第２のページネータ６０２は、限定ではないが、文書コンテンツ９０４のより小さい部分（例えば、「ウィンドウ」）上で一連のより小さい最適化プロセスを実行することによって、最適であることは保証されないが「欲張り」ページネーションよりも優れた近似最適ページネーション（approximate optimal pagination）を作成することを含む技術を使用することがある。
【０１７７】
図１９Ａ〜図１９Ｄは、特許請求された主題の例示的な一実施形態による、文書コンテンツ９０４を適応グリッドベース文書レイアウトに最適にページネーションする方法１９００のフローチャートを示す。最適なページネーションを見つけるために、ページネータ６０２は、有効なテンプレート１１０６の各シーケンスの有効性を測定しなければならず、それによって測定（measure）は、システマティックまたはヒューリスティックな検索、あるいは制約最適化により最大化される。最適化ページネータ６０２は、テンプレート１１０６のシーケンス、および各テンプレート１１０６へのコンテンツのマッピングを作成し、それによって、ある品質の測定を最大化する。限定ではないが例として、１つのこのような測定は、「ページめくり総数（total page turns）」メトリックを含み、この「ページめくり総数」メトリックは、テキストを読み通すことと、テキストが参照する任意の追加のコンテンツに移ることの両方に必要なページめくり総数をカウントする。特許請求された主題の例示的な実施形態では、有効なテンプレート１１０６の各シーケンスの有効性をスコアリングするのに使用されるメトリックは、ページめくり総数の値を、ページの外観の品質（例えば、空間、美的外観、作業性、または読みやすさ）を反映する他の測定と共に使用することを含む。
【０１７８】
サブプロブレム（例えば、一連の新しいテンプレート１１０６）を評価するために使用される基本の動的プログラミングアルゴリズムは、あとからの判断（hindsight）に依拠してサブプロブレムシーケンスをスコアリングするので、特許請求された主題の一態様は、現在のサブプロブレムのすべての可能性あるエンドポイントを計算することによって、評価が有効なページに対してのみ実行されるように（例えば、前向きに（forward-looking））、アルゴリズムを再構成する。特許請求された主題の一態様は、新しいサブプロブレムが考慮されるとき、解の中で恐らくそれに先行し得るすべてのサブプロブレムが既に解決され、最適な先行サブプロブレムを指すエントリがデータテーブルに存在するであろうことを保証する。したがって、サブプロブレムに到達するときにサブプロブレムについてのエントリがデータテーブル内に存在しない場合、そのサブプロブレムは、計算されずにパスされることがある。
【０１７９】
さらに、特許請求された主題の一実施形態は、データテーブルに余次元（extra dimension）を加えること、およびアルゴリズムに追加のネストされたループ（additional nested loop）を加えることによって、追加のコンテンツストリーム１３０３に対処するように容易に修正され得る。オプションのコンテンツストリーム１３０３からのコンテンツを表示するテンプレート１１０６を使用可能にすることによって、追加プログラミングなしで、オプションのコンテンツストリーム１３０３を処理することもできる。ページネータ６０２は、オプションのコンテンツストリーム１３０３からのコンテンツアイテム１３０６が最適ページネーションを向上させるときはいつでも、そのコンテンツアイテム１３０６を含む。このようなオプションのコンテンツストリーム１３０３、およびオプションのコンテンツストリーム１３０３を使用するテンプレート１１０６は、ページネーションの品質を非常に向上させることができる。
【０１８０】
特許請求された主題の様々な態様のパフォーマンスは、その品質スコアがある閾値（例えば、本明細書では「プルーニング閾値（pruning threshold）」と呼ばれることもある）より悪い部分解（partial solution）（例えば、受入れ可能であると既に検証されたサブプロブレム）をデータテーブルからプルーニングすることによってさらに向上される。存在する受入れ可能な解は比較的少ないので、このプルーニングは、サブプロブレムシーケンスのリストを最適に絞り込むのに役立つ。限定ではなく例として、従来のプルーニングの方針（pruning strategy）は、「第一適合」解（例えば、「欲張り」解）から生じる品質スコアをプルーニング閾値として使用することを含む。このような従来のプルーニングの方針を使用は、典型的に、ページネーションプロセスの大幅なスピードアップをもたらし、解が常に見つかることを保証する。あるいは、楽観的プルーニング（optimistic pruning）の方針は、おおよそのほぼ完全な閾値を選択し、解が見つからない場合には閾値を繰返し変更する。かなりの数のテンプレート１１０６がテンプレートストレージユニット９０８に存在する場合、ほぼ完全な解が存在する可能性は高く、したがって楽観的プルーニングの方針は、より効果的になる。
【０１８１】
データテーブル内のエントリは、文書内の位置（例えば、現在処理されているページのエンドポイント）を表す。さらに、データテーブル内のエントリは、テーブル内のエントリの指標値によって決定することができる文書の様々なコンテンツストリーム１３０３内の所与の位置で終わる、これまでに発見された最良のページネーションを表す。テーブルエントリは、限定ではないが、その位置で終わる最適な部分解の中の先行するページのテーブル内の位置（したがって、文書内の位置）と、最後のページをレンダリングするのに使用されるテンプレート１１０６（例えば、直前のテーブルエントリと、現在処理されているテーブルエントリの間のページ）とを含む。
【０１８２】
特許請求された主題の実施形態によって使用されるプロセスの最も外側のループは、テーブルを越えて、それが進むにつれてますます増加する（部分）解またはサブプロブレムを評価する。ループの各反復は、考慮されている現在のエンドポイントに続く可能性がある次の１組のページ（例えば、ページはコンテンツのテンプレート１１０６およびコンテンツ選択であり、異なるテキスト量、異なるイメージバージョンなどを有する単一のテンプレート１１０６について複数の結果が存在し得る）を見つけるために、低水準エンジン５０２が呼び出す。結果として生じる１組のページは、次のページの１組のエンドポイントをもたらし、このエンドポイントは、ページネータ６０２によって、データテーブルの方に伝搬される（例えば、新しいエントリがよりよいグローバルスコアを有する場合、既存のエントリを置き換える）。
【０１８３】
限定ではなく例として、図１９Ａ〜図１９Ｄに示される方法１９００は、表１に与えられる擬似コード（pseudo-code）によって表されることがある。
【０１８４】
【表６】
2009510650.tif 000008
【０１８５】
【表７】
2009510650.tif 000009
【０１８６】
ステップ１９０１から開始した後、ページネータ６０２は、ステップ１９０３に進み、最適ページネーションのプルーニング閾値を設定する。閾値は、上述の技術を含め様々な方法で決定することができることが当業者には認識されよう。
【０１８７】
次に、ステップ１９０６で、ページネータ６０２は、文書の第１のページの開始を表す単一のエンドポイントで、空のデータテーブルを初期化する（例えば、あるエントリを、文書の始まりを表す位置（０，０）に置く）。次いで、ページネータ６０２は、ステップ１９０９に進み、テーブル内のいずれかの位置を評価する必要があるかどうか判断する。ページネータ６０２は、ステップ１９０９でテーブル内の位置を評価する必要がないと判断する場合、ステップ１９２１に進み、最適テンプレート１１０６のシーケンスおよびコンテンツマッピングを取得するために最後のテーブルエントリからバックポインタをトレースする。次いで、ページネータ６０２は、ステップ１９０１で方法１９００による操作を終了する。
【０１８８】
しかし、ページネータ６０２は、ステップ１９０９でテーブル内の位置を評価する必要があると判断する場合、ステップ１９１２に進み、現在のテーブル位置が有効なエントリを有するかどうか判断する。現在のエントリは、ページネータによって、テーブル内の現在のエントリに先行するすべてのエントリは評価済みである未評価のテーブルエントリのセットから選択される。ページネータ６０２は、ステップ１９１２で現在のテーブルエントリが有効なエントリを有しないと判断する場合は、エントリを評価済みとしてマーク付けし、上述のステップ１９０９に進む。一方、ページネータ６０２は、ステップ１９１２で現在のテーブルエントリが有効なエントリ（例えば、文書コンテンツにうまく適用することができるテンプレートを表す、受入れ可能なエントリ）を有すると判断する場合は、ステップ１９１５に進み、低水準エンジン５０２を呼び出して、現在のテーブル位置で開始するページについてエンドポイントのリストを生成する。
【０１８９】
一般に、低水準エンジン５０２は、プログラムモジュールの呼出しを通じて、テンプレートストレージユニット９０８内の各テンプレート１１０６を文書コンテンツ９０４の未処理部分に適用し、どのテンプレート１１０６が有効なテンプレート１１０６か判断する。使用することができるテンプレート１１０６がない場合は、現在のテーブル位置に続くテンプレート１１０６がなく、したがって、現在のテーブルエントリは、それ以上考慮されるべきではない。低水準エンジン５０２は、テンプレート１１０６を現在の位置に適用することができる（例えば、それが、現在のテーブル位置で始まるコンテンツを収容する）と判断する場合は、低水準エンジン５０２は、テンプレートをコンテンツに適用して、結果として生じるページのエンドポイントおよびスコアを決定し、ページネータ６０２に返されたエンドポイントのリスト内にそのエンドポイントを含み、ページネータ６０２は、テンプレート１１０６の新しいシーケンスに関連付けられる適切なグローバルスコアを決定することができる。
【０１９０】
次いで、ページネータ６０２は、ステップ１９１８に進み、ステップ１９１５で返されたいずれかのエンドポイントを評価する必要があるかどうか（エンドポイントについて計算されたグローバルスコアがあるかどうか）を判断する。ページネータ６０２は、ステップ１９１８でエンドポイントを評価する必要がないと判断する場合は、上述のステップ１９０９に進む。しかし、ページネータ６０２は、ステップ１９１８でエンドポイントを評価する必要があると判断する場合は、ステップ１９２７に進み、新しいエンドポイントで終わるシーケンスのグローバルスコアを計算する。次いで、ページネータ６０２は、ステップ１９３０に進み、計算されたグローバルスコアが所定のプルーニング閾値より良いかどうか判断する。ページネータ６０２は、ステップ１９３０で、計算されたグローバルスコアが所定のプルーニング閾値よりも良くないと判断する場合は、上述のステップ１９１８に進む。
【０１９１】
しかし、ページネータ６０２は、ステップ１９３０で、計算されたグローバルスコアが所定のプルーニング閾値よりも良い（例えば、大きい）と判断する場合は、ステップ１９３３に進み、新しいエンドポイントがデータテーブル内にエントリを有するかどうか判断する。ページネータ６０２は、ステップ１９３３で新しいエンドポイントがデータテーブル内にエントリを有しないと判断する場合は、ステップ１９３６に進み、ページネータ６０２は、新しいエンドポイントについて、計算されたグローバルスコア、現在のテンプレート１１０６、および現在の位置へのバックポインタを含むエントリをテーブルに追加する。次いで、ページネータ６０２は、上述のステップ１９１８に進む。
【０１９２】
一方、ページネータ６０２は、ステップ１９３３で、新しいエンドポイントがデータテーブル内にエントリを有すると判断する場合は、ステップ１９３９に進み、計算されたグローバルスコアが、データテーブルに格納されたスコアよりも良いかどうか判断する。ページネータ６０２は、ステップ１９３９で計算されたグローバルスコアが、データテーブルに格納されたスコアより良くないと判断する場合は、上述のステップ１９１８に進む。
【０１９３】
しかし、ページネータ６０２は、ステップ１９３９で計算されたグローバルスコアが、データテーブルに格納されたスコアよりも良いと判断する場合は、ステップ１９４２に進み、データテーブルに格納されたエントリを新しいエンドポイント、計算されたグローバルスコア、現在のテンプレート１１０６、および現在の位置へのバックポインタで置き換える。次いで、ページネータ６０２は、上述のステップ１９１８に進む。
【０１９４】
次に図２０を参照すると、開示されたアーキテクチャを実行するように動作可能な例示的なコンピュータコンパイルシステムのブロック図が図示されている。システム２０００は、１つまたは複数のクライアント２００２を含む。クライアント２００２は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティング装置）とすることができる。クライアント２００２は、例えば、特許請求された主題の特徴を使用することによって、クッキーおよび／または関連コンテキスト情報を収容することができる。
【０１９５】
システム２０００は、１つまたは複数のサーバ２００４も含む。サーバ２００４は、ハードウェアおよび／またはソフトウェア（例えば、スレッド、プロセス、コンピューティング装置）とすることもできる。サーバ２００４は、例えば、特許請求された主題の特徴を使用することによって、変換を実行するスレッドを収容することができる。クライアント２００２とサーバ２００４の間の可能な通信の１つは、２つまたはそれ以上のコンピュータプロセス間で伝送されるように適応されたデータパケットの形式とすることができる。データパケットは、例えば、クッキーおよび／または関連コンテキスト情報を含むことができる。システム２０００は、クライアントとサーバ２００４の間の通信を容易にするのに使用することができる通信フレームワーク２００６（例えば、インターネットなどのグローバル通信ネットワーク）を含む。
【０１９６】
通信は、有線（光ファイバを含む）および／または無線技術を介して容易にすることができる。クライアント２００２は、クライアント２００２にローカルの情報（例えば、クッキーおよび／または関連コンテキスト情報）を格納するのに使用することができる１つまたは複数のクライアントデータストア２００８に動作可能に接続される。同様に、サーバ２００４は、サーバ２００４にローカルの情報を格納するために使用することができる１つまたは複数のサーバデータストア２０１０に動作可能に接続される。
【０１９７】
上記で述べた内容は、特許請求された主題の実施例を含む。当然、特許請求された主題を説明するために、コンポーネントまたは方法の考えられるあらゆる組合せを述べることは不可能であるが、特許請求された主題について多くのさらなる組合せおよび置換が可能であることが当業者には認識されよう。したがって、特許請求された主題は、添付の特許請求の範囲の精神および範囲に含まれる、すべてのこのような変更形態、修正形態、および変形形態を包含することが意図されている。さらに、「含む（include）」という用語が詳細な説明または請求項において使用される範囲では、このような用語は、「備える（comprising）」という用語が、請求項において移行語（transitional word）として使用される場合に解釈されるように、用語「備える（comprising）」と同様に包含的なものであることが意図されている。
【図面の簡単な説明】
【０１９８】
【図１】様々なコンテンツを有し、複数のサイズおよび寸法で表示することができる文書レイアウトを適応させることを容易にするシステムを示す図である。
【図２】テンプレートの作成、修正および／または記憶を容易にするシステムのブロック図である。
【図３】意味の流れ、ブランドアイデンティティ、イメージとテキストの相関性、および／または広告テーマに少なくとも部分的に基づく高品質レイアウトを生成するレイアウトエンジンを示す図である。
【図４】出力装置の寸法に基づいて表示することができる文書レイアウトを適応させることを容易にするシステムを示す図である。
【図５】高水準構成体で指定されたテンプレートに基づいて高品質レイアウトを作成し、レイアウトを、低水準エンジンが高品質レイアウトを作成するのに使用することができる低水準制約に変換するシステムを示す図である。
【図６】高品質レイアウトを作成するために、テンプレートを選択し、および／またはレイアウト上にコンテンツを配置するシステムを示す図である。
【図７】ソースフォーマットから変換するために拡張可能スタイルシート言語変換（ＸＳＬＴ）を使用するレイアウトエンジンを示す図である。
【図８】高品質レイアウトを作成するコンテンツ配置を容易にする手順の例示的なフローチャートである。
【図９】適応グリッドベース文書のレイアウト環境を表すブロック図である。
【図１０】本発明が使用することができるコンピューティング環境およびそのコンピュータシステムを表すブロック図である。
【図１１】適応レイアウトスタイルおよびテンプレートを含む文書レイアウトを表すブロック図である。
【図１２】適応テンプレートを表すブロック図である。
【図１３】コンテンツストリームを含む文書コンテンツを表すブロック図である。
【図１４】コンテンツアイテムを含むコンテンツストリームを表すブロック図である。
【図１５Ａ】文書コンテンツをテンプレートに適用する方法を表すフローチャートである。
【図１５Ｂ】文書コンテンツをテンプレートに適用する方法を表すフローチャートである。
【図１６Ａ】コンテンツを文書レイアウト内のエレメントに流す方法を表すフローチャートである。
【図１６Ｂ】コンテンツを文書レイアウト内のエレメントに流す方法を表すフローチャートである。
【図１６Ｃ】コンテンツを文書レイアウト内のエレメントに流す方法を表すフローチャートである。
【図１７Ａ】文書レイアウト内のエレメントを自己サイズ調整する方法を表すフローチャートである。
【図１７Ｂ】文書レイアウト内のエレメントを自己サイズ調整する方法を表すフローチャートである。
【図１７Ｃ】文書レイアウト内のエレメントを自己サイズ調整する方法を表すフローチャートである。
【図１８】文書コンテンツがテンプレートにどの程度よく適合するかに基づいてテンプレートをスコアリングする方法を表すフローチャートである。
【図１９Ａ】文書コンテンツを適応グリッドベース文書レイアウトに最適にページネーションする方法を表すフローチャートである。
【図１９Ｂ】文書コンテンツを適応グリッドベース文書レイアウトに最適にページネーションする方法を表すフローチャートである。
【図１９Ｃ】文書コンテンツを適応グリッドベース文書レイアウトに最適にページネーションする方法を表すフローチャートである。
【図１９Ｄ】文書コンテンツを適応グリッドベース文書レイアウトに最適にページネーションする方法を表すフローチャートである。
【図２０】例示的なコンピューティング環境の概略ブロック図である。
【図１】
2009510650.tif 000010
【図２】
2009510650.tif 000011
【図３】
2009510650.tif 000012
【図４】
2009510650.tif 000013
【図５】
2009510650.tif 000014
【図６】
2009510650.tif 000015
【図７】
2009510650.tif 000016
【図８】
2009510650.tif 000017
【図９】
2009510650.tif 000018
【図１０】
2009510650.tif 000019
【図１１】
2009510650.tif 000020
【図１２】
2009510650.tif 000021
【図１３】
2009510650.tif 000022
【図１４】
2009510650.tif 000023
【図１５Ａ】
2009510650.tif 000024
【図１５Ｂ】
2009510650.tif 000025
【図１６Ａ】
2009510650.tif 000026
【図１６Ｂ】
2009510650.tif 000027
【図１６Ｃ】
2009510650.tif 000028
【図１７Ａ】
2009510650.tif 000029
【図１７Ｂ】
2009510650.tif 000030
【図１７Ｃ】
2009510650.tif 000031
【図１８】
2009510650.tif 000032
【図１９Ａ】
2009510650.tif 000033
【図１９Ｂ】
2009510650.tif 000034
【図１９Ｃ】
2009510650.tif 000035
【図１９Ｄ】
2009510650.tif 000036
【図２０】
2009510650.tif 000037
【国際調査報告】
2009510650.tif 000038
2009510650.tif 000039