(57)【要約】【課題】　広幅アレイ状の出力ドキュメントを提供しながら、容易な（即ち、自動化された）カスタムドキュメント作成処理を可能にする。【解決手段】　本願発明に係る方法及びシステムは、既存の制約解決アルゴリズムを用いて特定ドキュメントを作成するために制約充足問題（ＣＳＰ）としてカスタムドキュメントを特定する。ドキュメント、そのコンテンツコンポーネント、及びそのレイアウト要件は、組を成すコンテンツコンポーネントのための自動化済みドキュメントレイアウトを解決時にもたらす、制約充足問題の要素として表現される。【選択図】　図１
2004054955.tif 000002
【特許請求の範囲】
【請求項１】
　（a）変更可能である少なくとも１つのドキュメントパラメータを識別することによって問題変数を特定するステップと、
　（b）関係するドキュメントパラメータのための有効範囲を識別することによって各変数のための価値ドメインを特定するステップと、
　（c）関係するドキュメントパラメータ変数の価値ドメインをより制約する１つ以上のレイアウト制約を特定するステップと、
　（d）複数の既存の制約充足アルゴリズムの中の１つに従って、ドキュメントパラメータのために選択された価値が特定済み制約の総てを通るように、ドキュメントのためのレイアウトを決定するステップと、
　を含むことを特徴とするドキュメント構成方法。
【請求項２】
　問題変数は、コンテンツで満たされるべきドキュメント領域を含むことを特徴とする請求項１記載の方法。
【請求項３】
　問題制約は、関係するドキュメント領域変数の価値ドメインを制約するコンテンツ制約を含むことを特徴とする請求項１記載の方法。
【請求項４】
　組を成す制約は、問題解決中に付加／除去される少なくとも１つの動的な制約を含むことを特徴とする請求項３記載の方法。
【請求項５】
　（a）変更可能である少なくとも１つのドキュメントパラメータを識別することによって問題変数を特定する手段と、
　（b）関係するドキュメントパラメータのための有効範囲を識別することによって各変数のための価値ドメインを特定する手段と、
　（c）関係するドキュメントパラメータ変数の価値ドメインをより制約する１つ以上のレイアウト制約を特定する手段と、
　（d）複数の既存の制約充足アルゴリズムの中の１つに従って、ドキュメントパラメータのために選択された価値が特定済み制約の総てを通るように、ドキュメントのためのレイアウトを決定する手段と、
　を含むことを特徴とするドキュメント構成システム。
【請求項６】
　問題変数は、コンテンツで満たされるべきドキュメント領域を含むことを特徴とする請求項５記載のシステム。
【請求項７】
　問題制約は、関係するドキュメント領域変数の価値ドメインを制約するコンテンツ制約を含むことを特徴とする請求項５記載のシステム。
【請求項８】
　組を成す制約は、問題解決中に付加／除去される少なくとも１つの動的な制約を含むことを特徴とする請求項７記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明は、ドキュメント構成要素を見つけて、それらを組み立てて可変データドキュメントのようなカスタムドキュメントを作り出すための方法及びシステムに関し、これらの方法及びシステムは、制約ベースのアプローチ（constraint based approaches）を使用しており、ドキュメント、そのコンテンツ、コンポーネント、及び、その要件は、制約充足問題（a constraint satisfaction problem）の要素として表現される。
【背景技術】
【０００２】
　カスタムドキュメントは、何らかの方法によってドキュメントの特別なユーザに合うように調整されるか又は手作りされるドキュメントである。ドキュメントの高まりつつある２つのアプリケーションは、可変データ印刷のドメインにおけるものと、ウェブパーソナリゼーション（web personalization）におけるものとである。
【０００３】
　伝統的な可変データのアプリケーションにおいて、カスタムドキュメントの作成は、グラフィックアート、データベース、レイアウト、ドキュメントデザイン等におけるエキスパートによって達成されている。このエキスパートのドキュメント作成者は、可変データ用のスロット（slots）を含むドキュメントのための全体レイアウトを構築する。また、この作成者は、適当なコンテンツピース（content pieces）を発見又は作成し、何の様にこのコンテンツを可変スロットに満たすかについてのルールを特定し、或いは、コンテンツをデータベースに置いてデータベースの特定フィールドにスロットをリンクさせる。次いで、可変データアプリケーションは、カスタマー用データをリンク済みスロットに挿入することによって各カスタマー用のドキュメントを作成する。これらのタイプのテンプレートは、『リック・アンド・スティック（lick and stick）』と典型的に呼ばれる。というのは、該テンプレートが、ドキュメント作成者によって画成される『アート・ホール（art hole）』を有し、可変データが、ドキュメントの異なったインスタンス（instances）を形成するためにアート・ホールに置かれるからである。派生する一組のドキュメントは、典型的には極めて似ている。各可変スロットは、略同一サイズのコンテンツの１ピースを有し、全体レイアウトは、可変コンテンツピースに拘わらず、全インスタンスに関して同一である。従って、伝統的な『可変データテンプレート』は、ドキュメント作成者に多大な時間及び専門的知識を要求するだけでなく、変わる量又はタイプのコンテンツピースに動的に（dynamically）応答しないか或いは可変コンテンツによって強要される限定事項に動的に応答しない。
【０００４】
　ウェブパーソナリゼーション及びウェブドキュメントのドメインにおいて、焦点は、動的ドキュメントレイアウト（a dynamic document layout）に合わせられるのではなく、寧ろ本質的には動的データに合わせられる。前提として、ドキュメントテンプレートは、事前決定され、課題は、適切な時に適切なデータを見い出すことである。例えば、動的ウェブドキュメントは、『スクリプト（scripts）』（例えば、プログラム）をＨＴＭＬページに組み込むことによって典型的に形成される。次いで、これらのスクリプトはウェブサーバーによって翻訳される。これによって、ドキュメントの所定エレメント（例えば、気象読取り）をドキュメント表示時に挿入又は作成することができる。このアプローチは、基礎プログラムに従ってドキュメントを形成することのみが可能である。異なった結果を達成するために、プログラムは変更されねばならず、従って、このアプローチは真の意味で動的（ダイナミック）ではない。ウェブパーソナリゼーションのアプリケーションにおいて、ｅコマース・カスタマーがオンラインで行うユーザ・プロファイリング及びアンダスタンディング（user profiling and understanding）に非常に焦点が合わせられ、これにより、適切な情報を提供することができる。再言すると、適切な情報を見つけることに重点が置かれ、見つけられるものとは違うものに基づいて展開することに重点は置かれない。動的ウェブページを作成するのに使用する技術は、ウェブページに埋め込むことができ且つウェブサーバーによって翻訳され得る特定のスクリプト又はプログラムをしばしば必要とする。このアプローチは、一般性を欠き、限定的なプラットフォーム依存（restrictive platform dependencies）を導き、極めて困難であり且つ維持に費用がかかることになり得る。
【０００５】
　可変データドキュメントのようなカスタムドキュメントの伝統的な作成は、データベース及びグラフィックアートのような多くの領域の専門家を必要とし、時間のかかる処理である。デジタル世界における絶えず増大している量の情報や素人の作る或る量のドキュメントのために、古い出版ツールは、しばしば注文の多い厄介なものになり、他方、現在の動的デジタル状況は、パーソナルニーズに自動的に合わせられるレイアウト及びコンテンツの双方を再生でき且つ初心者が其のようなドキュメントを作成できるようにするツールを要求している。
【０００６】
　カスタムドキュメント作成の領域において、技術的に必要とされることは、エキスパートのグラフィックアーティストに頼ることなく、或いは、ＨＴＭＬファイルに埋められる専門的なスクリプトを用いることなく、ドキュメントコンテンツを自動選別してそれをファイナルドキュメントの中に展開することである。
【特許文献１】米国特許第６１７３２８６号明細書
【非特許文献１】デングラー、イー．（DENGLER, E.）、フリーデル、エム．（Friedell, M）、マークス、ジェイ．（Marks, J.）の『Constraint-Driven Diagram Layout』視覚言語についての1993年IEEEシンポジウム議事録、330〜335頁、ノルウェー国ベルゲン（図解）
【非特許文献２】ルソー、エフ．（ROUSSEAU, F.）、ガルシア−マシアス、エー．（Garcia-Macias, A.）、バルデニ　デ　リマ、ジェイ．（Valdeni de Lima, J.）、デューダ、エー．（Duda, A.）の『User Adaptable Multimedia Presentations for the WWW』第８回国際ワールドワイドウエブ会議（1999年）からの電子議事録（マルチメディアプレゼンテーション）
【非特許文献３】グラフ、ダブリュー．エイチ．（GRAF, W. H.）の『The Constraint-Based Layout Framework LayLab and Applications』マルチメディアにおける効果的な抽出についての1995年ACMワークショップの電子議事録（フローチャート及びイエローページ）
【非特許文献４】クレーナー、エイ．（KROENER, A.）の『The Design Composer: Context-Based Automated Layout for the Internet』AAAI学会秋シンポジウムシリーズ：ドキュメントの作成、理解、又は検索のためのドキュメントレイアウト（1999年）
【非特許文献５】バドロス、ジー．（Badros G.）、ボーニング、エー．（Borning A.）の『The Cassowary Linear Arithmetic Constraint Solving Algorithm: Interface and Implementation』ワシントン大学技術レポート（98-06-04）1998年
【非特許文献６】パビス、リサ（PURVIS, Lisa）の『Document Assembly and Transformation: A survey』XR&T/DITC/CADISYS/DI（2001年3月）
【発明の開示】
【発明が解決しようとする課題】
【０００７】
　技術的に必要とされることは、ドキュメントコンポーネントの柔軟且つ効率的な組み立てをサポートする方法論を提供して真に動的且つ専門的なドキュメントをもたらすことによって、カスタムドキュメント作成における伝統的な幾つかの制限を除去するための策である。
【課題を解決するための手段】
【０００８】
　本明細書で開示されるものは、既存の制約解決アルゴリズムを用いる特定のドキュメントを作成するために、制約充足問題（ＣＳＰ）としてカスタムドキュメントを特定するための方法及びシステムである。ドキュメント、そのコンポーネント、及び、そのレイアウト要件は、解決時に一組のコンテンツコンポーネントのための自動化済みドキュメントレイアウトをもたらす制約充足問題の要素として表現される。このプロセスによって、今日可能である幅広のアウトプットドキュメントのアレイを提供しながらも、より簡単な（即ち、自動化された）カスタムドキュメント作成プロセスが可能になる。
【０００９】
　ドキュメントは、変数、価値、及び、制約から構成されるテンプレートとして表現される。このテンプレートのインスタンスが作成され、一組の公知の制約充足アルゴリズムの１つを用いることによって、一組のコンテンツと、このコンテンツのレイアウトとがもたらされる。本明細書に記載される本発明は、制約充足問題としてドキュメント作成を構築すること、並びに、所望の出力ドキュメントを自動作成するために既存の制約充足アルゴリズムを適用することであり、それらの組み合わせは今までのところ技術的に知られていない。ドキュメント構成に関する本願方法は、関係する制約を有するゼロからnのドキュメント領域を識別し、変更可能である少なくとも１つのドキュメントパラメータを識別することによって問題変数を特定するステップと、関係するドキュメント領域に適するコンテンツピースを識別するか又は関係するドキュメントパラメータのための有効範囲を識別することによって各変数のための価値ドメインを特定するステップと、ドキュメント領域変数及び／又はドキュメントパラメータの有効価値をより制約するコンテンツ制約及び／又はレイアウトを特定するステップと、問題解決時に付加／取り去りさられるべき動的制約を追加的に特定するステップと、複数の既存の制約充足アルゴリズムの中の１つに従って、ドキュメントパラメータ及びドキュメント領域のために選択された価値が特定済み制約の総てを通るように、ドキュメントのためのレイアウトを決定するステップと、を含む。
【００１０】
　ドキュメントは、変数、価値、及び、制約から構成されるテンプレートとして表現される。このテンプレートのインスタンスが作成され、一組の公知の制約充足アルゴリズムの１つを用いることによって、一組のコンテンツと、このコンテンツのレイアウトとがもたらされる。本明細書に記載される本発明は、制約充足問題としてドキュメント作成を構築すること、並びに、所望の出力ドキュメントを自動作成するために既存の制約充足アルゴリズムを適用することであり、それらの組み合わせは今までのところ技術的に知られていない。ドキュメント構成に関する本願方法は、変更可能である少なくとも１つのドキュメントパラメータと、関係する制約を有するゼロからnのドキュメント領域を識別することによって問題変数を特定するステップと、関係するドキュメント領域に適するコンテンツピースを識別するか又は関係するドキュメントパラメータのための有効範囲を識別することによって各変数のための価値ドメインを特定するステップと、ドキュメント領域変数及び／又はドキュメントパラメータの有効価値をより制約するコンテンツ制約及び／又はレイアウトを特定するステップと、問題解決時に付加／取り去りさられるべき動的制約を追加的に特定するステップと、複数の既存の制約充足アルゴリズムの中の１つに従って、ドキュメントパラメータ及びドキュメント領域のために選択された価値が特定済み制約の総てを通るように、ドキュメントのためのレイアウトを決定するステップと、を含む。
【００１１】
　以下、解決手段を構成し得る実施態様を詳細に説明する。
（第１実施態様）
　（a）変更可能である少なくとも１つのドキュメントパラメータを識別することによって問題変数を特定するステップと、
　（b）関係するドキュメントパラメータのための有効範囲を識別することによって各変数のための価値ドメインを特定するステップと、
　（c）関係するドキュメントパラメータ変数の価値ドメインをより制約する１つ以上のレイアウト制約を特定するステップと、
　（d）複数の既存の制約充足アルゴリズムの中の１つに従って、ドキュメントパラメータのために選択された価値が特定済み制約の総てを通るように、ドキュメントのためのレイアウトを決定するステップと、
　を含むことを特徴とするドキュメント構成方法。
（第２実施態様）
　問題変数は、コンテンツで満たされるべきドキュメント領域を含むことを特徴とする第１実施態様記載の方法。
（第３実施態様）
　問題制約は、関係するドキュメント領域変数の価値ドメインを制約するコンテンツ制約を含むことを特徴とする第１実施態様記載の方法。
（第４実施態様）
　組を成す制約は、問題解決中に付加／除去される少なくとも１つの動的な制約を含むことを特徴とする第３実施態様記載の方法。
（第５実施態様）
　（a）変更可能である少なくとも１つのドキュメントパラメータを識別することによって問題変数を特定する手段と、
　（b）関係するドキュメントパラメータのための有効範囲を識別することによって各変数のための価値ドメインを特定する手段と、
　（c）関係するドキュメントパラメータ変数の価値ドメインをより制約する１つ以上のレイアウト制約を特定する手段と、
　（d）複数の既存の制約充足アルゴリズムの中の１つに従って、ドキュメントパラメータのために選択された価値が特定済み制約の総てを通るように、ドキュメントのためのレイアウトを決定する手段と、
　を含むことを特徴とするドキュメント構成システム。
（第６実施態様）
　問題変数は、コンテンツで満たされるべきドキュメント領域を含むことを特徴とする第５実施態様記載のシステム。
（第７実施態様）
　問題制約は、関係するドキュメント領域変数の価値ドメインを制約するコンテンツ制約を含むことを特徴とする第５実施態様記載のシステム。
（第８実施態様）
　組を成す制約は、問題解決中に付加／除去される少なくとも１つの動的な制約を含むことを特徴とする第７実施態様記載のシステム。
（第９実施態様）
　第４実施態様において、制約解決アルゴリズムは動的制約解決アルゴリズムである。
（第１０実施態様）
　第１実施態様において、選択済みコンテンツは、ドキュメントコンポーネントの保管部から提供される。
（第１１実施態様）
　第５実施態様において、少なくとも１つの保管部は、ドキュメントコンポーネントに関係する情報を含む。
（第１２実施態様）
　第１実施態様において、コンポーネントは、ドキュメント受取り部に適合するように選択される。
（第１３実施態様）
　第７実施態様において、ドキュメント受取り部に関係する情報の保管部が少なくとも１つ存在する。
（第１４実施態様）
　第１実施態様において、ドキュメント領域は、少なくとも１つの領域変数の中で特定される。
（第１５実施態様）
　第１実施態様において、レイアウト制約の仕様は、少なくとも１つのレイアウト変数の中で特定される。
（第１６実施態様）
　第６実施態様において、ドキュメントコンポーネントに関係する情報は、レイアウト制約を含む。
（第１７実施態様）
　第１実施態様において、コンテンツ制約は、構成済み最終ドキュメントの意図した受容部に特有の情報を含む。
（第１８実施態様）
　第１実施態様において、候補コンテンツの選択は、コンテンツ制約の充足によって実施される。
（第１９実施態様）
　第１３実施態様において、レイアウト制約の合計は、候補コンテンツ選択のコンテンツアイテムに関係するレイアウト制約と一般的レイアウト制約とを含む。
（第２０実施態様）
　第１４実施態様において、ドキュメントレイアウトは、レイアウト制約の合計を充足するドキュメント領域変数価値を有する。
【発明の効果】
【００１２】
　本発明は、多くの利点を有し、例えば、ドキュメントが何のように見えるかを特定するが、其のようなレイアウトが何のように達成されるかまでの厳密な特定が不要であり（ドキュメント作成者が別の潜在レイアウトを評価することを不要にする）、各々が或るドキュメント要件を充足するか否かを特定する能力である。また、ドキュメント作成者は、ドキュメント作成の正に開始時にドキュメントコンテンツの予備知識を有していることを要求されず、これにより、より動的な出力ドキュメントの作成が可能になる。
【００１３】
　また、本願システム及び方法は、有益なことに、（典型的にはドキュメントレイアウト処理の一部ではない、即ち、ドキュメント制約の残部を充足するコンテンツピースが選別され、これにより、ドキュメントに含めるコンテンツについての自動決定を行うことができるような）コンテンツ選別を自動化するための能力を提供する。これは、レイアウト開始前に包含されるコンテンツ全部を選び出すことをドキュメント作成者に強いる典型的なアプローチとは大違いである。また、本発明は、有益なことに、他の形態のドキュメントへの制約（例えば、ともかく其の領域にある制約が、寸法８〜１２の間のタイムズ・ロマン（Times Roman）フォント形式にすべきであるか又はテキストの異なる形式の間の行間隔の制約であるべきか）を画成するのを可能にする。更に、動的な制約充足モデルへの表象展開によって、より複雑なドキュメントの表示及び自動作成が可能になる。有益なことに、コンテンツアイテム自体に対する制約（コンテンツを50%以上の倍率にすべきでないという制約や、或る宣伝と同じページにコンテンツがあることができないという制約）を特定する能力が提供される。
【００１４】
　本発明は特定の実施態様を参照して記載されたが、この特定の実施態様は、図示を意図したものであって、制限的なものではない。添付した請求の範囲に記載の本発明の範囲から逸脱することなく様々の変更が可能である。本明細書を読解した際には変更及び改変が想到されよう。従って、其のような変更及び改変の総ては添付請求の範囲の範囲内ないし等価な範囲内にある限り包含される。
【発明を実施するための最良の形態】
【００１５】
　本願明細書で開示されるものは、（ドキュメント、そのコンポーネント、及び、そのレイアウト要件が解決時に一組のコンテンツコンポーネントのための自動化されたドキュメントレイアウトをもたらす）制約充足問題の要素として表現される既存の制約解決アルゴリズムを用いる特定のドキュメントを作成するために、制約充足問題（ＣＳＰ）としてカスタムドキュメントを特定するための方法及びシステムである。このプロセスによって、今日可能である幅広いアウトプットドキュメントのアレイを提供しながらも、より簡単な（即ち、自動化された）カスタムドキュメント作成プロセスが可能になる。
【００１６】
　ドキュメントは、変数（variables）、価値（values）、及び制約（constraints）から構成されるテンプレートとして表現される。其のようなテンプレートのインスタンス（instance）は、ネーデル（Nadel）の『Tree Search and Arc Consistency in Constraint Satisfaction Algorithms, Search in Artificial Intelligence』1988年287〜342頁（シュプリンガー出版）に教示されているように、バックトラッキング（backtracking）やフォワードチェッキング（forward checking）等の一連の公知の制約充足アルゴリズムの１つを用いることによって、一組のコンテンツ及びそのコンテンツのレイアウトをもたらすように、作成される。本明細書に記載の本願発明は、制約充足問題としてドキュメント作成を構築すること、及び、所望のアウトプットドキュメントを自動作成するために既存の制約充足アルゴリズムを応用することであり、それらの組み合わせは、今まで技術的に知られていないことである。
【００１７】
　特に、ドキュメントテンプレートは、制約充足問題（ＣＳＰ）として代表され、従って、一連の変数、各変数のための価値ドメイン（value domain）、及び、これらの変数及び価値に対する一連の制約を包含する。
【００１８】
　本願発明において、コンテンツで満たされるべきドキュメントの領域（areas）は、変更され得るドキュメントの任意のパラメータのような問題変数（problem variables）としてモデル化される。一例として、図１に示すようなドキュメントテンプレートを考える。テンプレートは、コンテンツで満たされるべき２つの領域、即ち、領域A（areaA）と領域B（areaB）があることを規定する。また、テンプレートは、領域A及び領域Bのサイズ及びポジションが変更可能であることを規定する。従って、この例に関する問題変数は、領域A、領域B、領域A-トップレフトX（areaA-topLeftX）、領域A-トップレフトY、領域B-トップレフトX、領域B-トップレフトY、領域A-幅、領域A-高さ、領域B-幅、領域B-高さである。
【００１９】
　制約充足問題の形成は、問題変数の各々が、該変数に支援するために可能価値（possible values）から成る価値ドメインを有する、ということを更に規定する。本願発明は、コンテンツで満たされるべきドキュメント領域（例えば、図１の領域A及び領域B）である変数に関して価値ドメインが各領域に適用可能であるコンテンツピースであるということを教示している。ドキュメントパラメータである変数に関して、価値ドメインは、それらのパラメータに関する打ち切り範囲（discretized ranges）であり、従って、パラメータに関する潜在価値（potential value）の各々が価値ドメインの中に出てくる。最初の価値ドメインは、或るデフォルト範囲（例えば、［1..MAXINT］）で設定される。その価値ドメインがコンテンツピースであるような変数に関して、デフォルトドメインは、ドキュメントテンプレートの中で特定される関連するコンテンツデータベースの総ての可能なコンテンツピースになるように設定される。
【００２０】
　制約は、派生するドキュメントを有効にするために保持しなければならない価値及び／又は変数の間における関係を特定する。制約は、（１変数に適用される）単項（unary）、（２変数／価値に適用される）二項（binary）、（n変数／価値に適用される）n項（n-ary）であることができ、本発明にあっては、ドキュメントテンプレートの一部としてユーザによって入力される。ドキュメントドメイン内の単項制約（unary constraint）の一例は、領域Aがキャッスル（castle）のイメージを包含しなければならないということである。二項制約（binary constraint）の一例は、領域A-トップレフトY + 領域A-高さ < 領域B-トップレフトYである。別の変数（領域C）を持った場合、三項制約（3-ary constraint）の一例は、領域A-幅 + 領域B-幅 < 領域C-幅である。本発明の変更可能データの応用（多くの可能な応用の一つ）において、制約は、カスタマー属性を参照し、例えば、領域Aは、カスタマー１．年齢（customer1.age）に適しているイメージを包含しなければならない。
【００２１】
　離散型（discrete）制約充足問題のための既存公知の制約解決アルゴリズムの任意の１つは、最終出力ドキュメントを作成するために適用される。其のような１の既存アルゴリズムを用いて我が例を遂行するために、簡単なバックトラッキング・アルゴリズムを検討する。我が例における問題変数及び価値ドメインは：
領域A｛スキーヤー１．jpg，スキーヤー２．jpg，ゴルフ．jpg，シュノーケル．jpg，シュノーケル．txt，スキー．txt，ゴルフ．txt｝
領域B｛スキーヤー１．jpg，スキーヤー２．jpg，ゴルフ．jpg，シュノーケル．jpg，シュノーケル．txt，スキー．txt，ゴルフ．txt｝
領域A-トップレフトX｛０．．５００｝
領域A-トップレフトY｛０．．７５０｝
領域B-トップレフトX｛０．．５００｝
領域B-トップレフトY｛０．．５００｝
領域A-幅　｛１．．５００｝
領域A-高さ｛１．．７５０｝
領域B-幅　｛１．．５００｝
領域B-高さ｛１．．７５０｝
　我が例の問題に関する単項制約は：
C１：領域Aはスキーヤーのイメージを包含しなければならないこと、
C２：領域Bはスキーについてのテキストを包含しなければならないことである。
【００２２】
　また、次の１つの二項制約を持つ：
C３： 領域A-トップレフトY + 領域A-高さ < 領域B-トップレフトY
　先ず、制約解法（solver）は、各変数の価値ドメインに対して単項制約C１及びC２を実行させて単項制約を充足しない価値を除去するノード一貫性（node-consistency）を実現する。ノード一貫性の後で、我が問題変数及び価値ドメインは、次のようになる（この時点で、領域A及び領域Bのための価値ドメインが単項制約を充足するコンテンツピースのみを有する、ということに留意）：
領域A｛スキーヤー１．jpg，スキーヤー２．Jpg｝
領域B｛スキー．txt｝
領域A-トップレフトX｛０．．５００｝
領域A-トップレフトY｛０．．７５０｝
領域B-トップレフトX｛０．．５００｝
領域B-トップレフトY｛０．．５００｝
領域A-幅　｛１．．５００｝
領域A-高さ｛１．．７５０｝
領域B-幅　｛１．．５００｝
領域B-高さ｛１．．７５０｝
　次いで、制約解法は、次々に各変数の価値を繰り返し試みて各割当て後の二項（及び任意のn項）制約をチェックし、割当てが任意の制約に違反してる場合に異なった価値までバックトラックする。制約の任意のコンポーネント価値（component values）が未だ裏付けられない場合には、制約が僅かしか充足されていないと考えられるということに留意されたい。従って、領域A-トップレフト Y 、領域A-高さ、及び、領域B-トップレフト Y の総てが価値を有するようになって初めて、C３が違反される可能性がある。
【００２３】
　従って、バックトラッキング・アルゴリズムは繰り返し次のように割当てる：
領域A = スキーヤー１．jpg
領域Ｂ = スキー．txt
領域A-トップレフトX = ０
領域A-トップレフトY = ０
領域B-トップレフトX = ０
領域B-トップレフトY = ０
領域A-幅 = １
領域A-高さ = １
　制約C３がチェックされるポイントにおいて、領域A-トップレフトY（０）+ 領域A-高さ（１）が領域B-トップレフトY（０）以上であることが判明し、従って、領域A-高さに関する次の可能な価値を選択するためにバックトラッキングが為される。結局、Ｃ３が違反されていないポイントまでバックトラッキングが為され、従って、有効な解決策に到達する。実現可能に見える出力ドキュメント（例えば、コンテンツ領域などのための最小幅）を確保するために問題に付加できる更に多くの制約を想像することができる。本発明の新規性は、制約充足問題としてドキュメントテンプレートのモデリングにあり、従って、ドキュメント作成者は任意の組の変数／価値／制約を特定でき、制約解決アルゴリズムは最終出力ドキュメントを自動作成できる。
【００２４】
　本文で教示される、制約充足問題としてドキュメントテンプレートを代表する方法並びに制約解決アルゴリズムを適用することによって最終ドキュメントを作成する方法の更なる展開は、公知の動的制約充足モデル及びMittal（ミッタル）及びFalkenhainer（ファルケンハイナー）の『Dynamic Constraint Satisfaction Problems』ＡＡＡＩ学会会報（1990年25〜32頁）に教示されているような解決アルゴリズムを用いることによって、より複雑なドキュメントを網羅するようにモデルを更に拡大できるということである。動的制約充足にあっては、組を成す変数、価値、及び制約は問題解決進行時に変更できる。即ち、現状の価値の選択を考えると、他の制約も対象になることができ、及び／又は、或る変数及び／又は価値を問題に付加又はそれから除去できる。自動化されたドキュメント作成の背景において、この展開によって、ドキュメントコンテンツコンポーネントは、それ自体の組の制約を特定できる（即ち、『私はイメージであり、私の幅は350ピクセル未満にできない』又は『私は煙草の宣伝のイメージであり、心臓病協会からの任意コンテンツと同じページに私を配置することができない』）。同様に、動的制約は他の問題変数の使用を特定する問題に付加できる（例えば、『その幅 > 300ピクセルである領域Aのためのコンテンツを選択する場合、問題から領域Cを削除しなければならない』）。これらの例は、説明するためのものであることを意味し、総ての可能な動的ドキュメント制約を包括するものを意味しない。一般に、ドキュメント領域の付加／削除を伴うか或いは制約解決中に為されるコンテンツ選択の結果として付加／削除される任意の制約は、我々のドキュメント制約解決モデルに対する動的展開（dynamic extension）の一部と考えられるものである。
【００２５】
　この動的ドキュメント制約解決モデルの（多くの可能な遂行の１つである）特定の遂行が行われ、本文に記載された。問題解決中に制約及び問題変数の動的な付加／削除を可能にするために、Badros G（バドロスジー）、Borning A（ボーニングエー）の『The Cassowary Linear Arithmetic Constraint Solving Algorithm: Interface and Implementation』ワシントン大学技術レポート（98-06-04）1998年に教示されているような線形の制約解法を公知のバックトラッキングアルゴリズムに組み合わせてみた。
【００２６】
　バックトラッキングアルゴリズムのための変数としてドキュメント領域変数（領域A、領域B）をモデル化し、更に、ドキュメント領域変数に対する補助変数（sub-variables）としてレイアウト関連変数（領域A-トップレフトX、領域A-トップレフトY、領域A-幅、領域A-高さ、など）をモデル化した。トップ-レベル変数の各々が価値で裏付けられるので、その補助変数が線形制約解法に付加され、また、選択済みコンテンツ価値に関連する任意の制約が線形制約解法に付加された。我が例を継続させるために、領域Aに関する価値スキーヤー１．jpgを選択する場合に、スキーヤー１．jpgは、スケール化できないと言われて幅及び高さが元の幅及び高さであるような関連する制約を有する。従って、次の制約が線形制約解法に追加される。
【００２７】
C４：領域A-幅 = １７５
C５：領域A-高さ = ２５５
　さて、我々の特定の遂行にあっては、これらの新たな追加のレイアウト制約を考えて選択済み価値の有効性を決定するために線形制約解法に救いを求めた。線形制約解法は、この及び他の任意の既存のレイアウト制約を考えて他の補助変数（即ち、領域B-トップレフトX、領域B-トップレフトY、領域B-幅、領域B-高さ）の総てに関して価値を見つけることができるか否かを調べるために、これらの新たな制約を処理する。そうである場合、我々のバックトラッキングが続行される。そうでない場合、線形制約解法から制約Ｃ４及びＣ５が取り去られる。制約解法は、このように継続するものであって、候補コンテンツ（candidate content）を試み、制約を付加／除去し、全ドキュメント領域がコンテンツで満たされて派生するドキュメントが能動的制約（active constraint）の総てを充足するまで能動的制約をチェックする。
【図面の簡単な説明】
【００２８】
【図１】領域A及び領域Bというコンテンツで満たされるべき２つの領域があることを特定すると共に領域A及び領域Bのポジション及び寸法が変更可能であることを特定するドキュメントテンプレートを示す図である。
【図１】
2004054955.tif 000003