(57)【特許請求の範囲】
【請求項１】
電子装置が文書を記憶する方法であって、
前記文書のコンテンツストリーム表現を記憶するステップであって、前記コンテンツストリーム表現は前記文書のプリミティブ要素のコード表現の順序付けられたストリームを含み、プリミティブ要素の各コード表現は当該プリミティブ要素の表現の前記コンテンツストリームにおける順序を示すインデックスを有する、ステップと、
前記文書の１以上のオブジェクト表現を記憶するステップであって、各オブジェクト表現は前記文書の階層構造を表す階層的ツリー構造に配置されたオブジェクトノードのセットを含み、各オブジェクトノードは前記コンテンツストリームにおけるインデックスの範囲を参照し、前記階層的ツリー構造は前記文書の前記プリミティブ要素のインデックスの完全な範囲を参照するルートオブジェクトノードを含む、ステップと、
を備え、
第１の文書処理操作は、当該第１の文書処理操作を効率的に実行するために前記文書の（ｉ）特定のオブジェクト表現及び（ｉｉ）前記コンテンツストリーム表現の組み合わせにアクセスし、前記第１の文書処理操作とは異なる第２の文書処理操作は、当該第２の文書処理操作を効率的に実行するために前記文書の（ｉ）前記特定のオブジェクト表現及び（ｉｉ）前記コンテンツストリーム表現のうちの一方にのみアクセスすることを特徴とする方法。
【請求項２】
前記コンテンツストリーム表現及び前記１以上のオブジェクト表現のうちの少なくとも一方は、前記文書のメモリ内表現である
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記コンテンツストリーム表現及び前記１以上のオブジェクト表現のうちの少なくとも一方は、前記文書のファイル形式表現である
ことを特徴とする請求項１に記載の方法。
【請求項４】
前記プリミティブ要素の前記コード表現は、前記文書における前記プリミティブ要素の読み取り順序に基づいて順序付けられている
ことを特徴とする請求項１に記載の方法。
【請求項５】
前記ツリー構造において任意のオブジェクトノードによって参照されるインデックスの範囲は、単一の連続する範囲である
ことを特徴とする請求項１に記載の方法。
【請求項６】
前記オブジェクトノードは、前記階層的ツリー構造の中に配置されており、親のオブジェクトノードを持たない前記ルートオブジェクトノードがあり、その他の各オブジェクトノードは単一の親のオブジェクトノードを持つ
ことを特徴とする請求項１に記載の方法。
【請求項７】
任意の親のオブジェクトノードのインデックスの範囲は、当該オブジェクトノードが持つ子のオブジェクトノードのインデックスの範囲の和集合である
ことを特徴とする請求項６に記載の方法。
【請求項８】
任意の親のオブジェクトノードのインデックスの範囲は、当該オブジェクトノードが持つ子のオブジェクトノードのインデックスの範囲の和集合を含む
ことを特徴とする請求項６に記載の方法。
【請求項９】
任意の２つの兄弟のオブジェクトノードのインデックスの範囲は、離れている
ことを特徴とする請求項６に記載の方法。
【請求項１０】
第１のオブジェクトノードが第２のオブジェクトノードの兄である場合、前記第１のオブジェクトノードのインデックスの範囲の開始インデックスは、前記第２のオブジェクトノードのインデックスの範囲の開始インデックスよりも小さいか又は等しい
ことを特徴とする請求項６に記載の方法。
【請求項１１】
電子装置が文書を記憶する方法であって、
前記文書のコンテンツストリーム表現を記憶するステップであって、前記コンテンツストリーム表現は前記文書のプリミティブ要素のコード表現の順序付けられたストリームを含み、プリミティブ要素の各コード表現は当該プリミティブ要素の表現の前記コンテンツストリームにおける順序を示すインデックスを有する、ステップと、
前記文書の第１のオブジェクト表現を記憶するステップであって、前記オブジェクト表現はツリー構造に配置されたオブジェクトノードのセットを含み、各オブジェクトノードは前記コンテンツストリームにおけるインデックスの範囲を参照する、ステップと、
前記文書の異なる第２のオブジェクト表現を記憶するステップであって、前記第２のオブジェクト表現は第２のツリー構造に配置されたオブジェクトノードの第２のセットを含み、前記第２のオブジェクト表現における各オブジェクトノードも前記コンテンツストリームにおけるインデックスの範囲を参照し、前記第１及び第２のツリー構造の各々は前記文書の前記プリミティブ要素のインデックスの完全な範囲を共に参照するルートオブジェクトノードを含む、ステップと、
を備え、
第１の文書処理操作は、当該第１の文書処理操作を効率的に実行するために前記文書の前記第１のオブジェクト表現にのみアクセスし、前記第１の文書処理操作とは異なる第２の文書処理操作は、当該第２の文書処理操作を効率的に実行するために前記文書の前記第２のオブジェクト表現にのみアクセスすることを特徴とする方法。
【請求項１２】
前記第１のオブジェクト表現は、前記オブジェクトノードが階層的文書構造を表す文書構造表現であり、
前記第２のオブジェクト表現は、前記オブジェクトノードがスタイル属性を表すスタイル属性表現である
ことを特徴とする請求項１１に記載の方法。
【請求項１３】
任意のツリー構造において任意のオブジェクトノードによって参照されるインデックスの範囲は、前記文書の前記コンテンツストリーム表現内の単一の連続する範囲である
ことを特徴とする請求項１１に記載の方法。
【請求項１４】
少なくとも１つのプロセッサユニットが実行するためのプログラムを記録したコンピュータが読み取り可能な記録媒体であって、前記プログラムは、請求項１１乃至１３のいずれか１項に記載の方法を実施するための命令セットを含む
ことを特徴とするコンピュータが読み取り可能な記録媒体。
【請求項１５】
少なくとも１つのプロセッサユニットにより実行されると文書を記憶するプログラムを記録したコンピュータが読み取り可能な記録媒体であって、前記プログラムは、
前記文書のコンテンツストリーム表現を記憶する命令セットであって、前記コンテンツストリーム表現は前記文書のプリミティブ要素のコード表現の順序付けられたストリームを含み、プリミティブ要素の各コード表現は当該プリミティブ要素の表現の前記コンテンツストリームにおける順序を示すインデックスを有する、命令セットと、
前記文書の１以上のオブジェクト表現を記憶する命令セットであって、各オブジェクト表現は前記文書の階層構造を表す階層的ツリー構造に配置されたオブジェクトノードのセットを含み、各オブジェクトノードは前記コンテンツストリームにおけるインデックスの範囲を参照し、前記階層的ツリー構造は前記文書の前記プリミティブ要素のインデックスの完全な範囲を参照するルートオブジェクトノードを含む、命令セットと、
を含み、
第１の文書処理操作は、当該第１の文書処理操作を効率的に実行するために、異なるタイプの情報を求めて前記コンテンツストリーム表現及び特定のオブジェクト表現の組み合わせにアクセスし、第２の文書処理操作は、当該第２の文書処理操作を効率的に実行するために、情報を求めて前記コンテンツストリーム表現にのみアクセスし、第３の文書処理操作は、当該第３の文書処理操作を効率的に実行するために、情報を求めて前記特定のオブジェクト表現にのみアクセスする
ことを特徴とするコンピュータが読み取り可能な記録媒体。
【請求項１６】
前記コンテンツストリーム表現及び前記１以上のオブジェクト表現のうちの少なくとも一方は、前記文書のメモリ内表現である
ことを特徴とする請求項１５に記載のコンピュータが読み取り可能な記録媒体。
【請求項１７】
前記コンテンツストリーム表現及び前記１以上のオブジェクト表現のうちの少なくとも一方は、前記文書のファイル形式表現である
ことを特徴とする請求項１５に記載のコンピュータが読み取り可能な記録媒体。
【請求項１８】
前記プリミティブ要素の前記コード表現は、前記文書における前記プリミティブ要素の読み取り順序に基づいて順序付けられている
ことを特徴とする請求項１５に記載のコンピュータが読み取り可能な記録媒体。
【請求項１９】
前記ツリー構造において任意のオブジェクトノードによって参照されるインデックスの範囲は、単一の連続する範囲である
ことを特徴とする請求項１５に記載のコンピュータが読み取り可能な記録媒体。
【請求項２０】
前記オブジェクトノードは、前記階層的ツリー構造の中に配置されており、親のオブジェクトノードを持たない前記ルートオブジェクトノードがあり、その他の各オブジェクトノードは単一の親のオブジェクトノードを持つ
ことを特徴とする請求項１５に記載のコンピュータが読み取り可能な記録媒体。
【発明の詳細な説明】
【背景技術】
【０００１】
電子文書のファイル形式（ファイルフォーマット）と、電子文書を処理するソフトウェアによって用いられるメモリ内の表現とは、一般に、ストリーム表現であるかまたはオブジェクト表現であろう。ストリーム表現は、一般に、一連の文字コードやその他の基本データ要素で構成されており、その中に、特殊な、文字以外の値や、状態または文脈（例えば、テキストのスタイル、変換または描画属性、あるいは、構文解析モードの開始または終了）の変化を信号で伝える一連の値が点在している。そのようなストリームの中のデータを処理するソフトウェアは、所与のデータ要素において達成される状態を判定するために、先頭から開始して各要素に順番にアクセスしなければならない。なぜなら、この状態は、そのポイントまでに生じたすべての変化の正味の結果だからである。
【０００２】
他方、オブジェクト表現は、文書の構成部分を表すオブジェクトの集合で構成される。これらのオブジェクトは、オブジェクト属性、他の関連オブジェクトへのポインタまたは参照、および、文書の内容の一部を含んでいることがある。例えば、パラグラフのオブジェクトは、行間隔属性やパラグラフのテキストを含んでいることがあるだろうし、節のオブジェクトは、その節を構成するすべてのパラグラフオブジェクトおよび説明図オブジェクトへのポインタの順序付けられた集合を含んでいることがあるだろう。
【０００３】
多くの場合、オブジェクト表現は主に階層的であり、オブジェクト参照の図式（グラフ）は、ツリー構造となっている（例えば、文書にはページが含まれ、ページにはゾーンが含まれ、ゾーンには他のゾーンとレイアウトエリアとが含まれることがあり、それらには欄（カラム）が含まれ、欄にはパラグラフが含まれる）。しかし、階層モデルの場合であっても、ツリー図式とは別に、追加のオブジェクト参照がありうる（例えば、ゾーンには、それらの境界線および他のゾーンとの境界線が生じうる、共有されるグラフィックオブジェクトへの参照が含まれ、他方、パラグラフには、共有されるテキストスタイルオブジェクトへの参照が含まれることがある）。
【０００４】
アプリケーションは、多くの場合、それらのファイル形式に、それらのメモリ内の表現とは異なる表現を選択する。個々のファイル形式は、一定の操作については効率が良いが、別の操作については効率が悪いこともある。例えば、ストリーム表現は、文字列検索や、オブジェクト属性の詳細な知識に依存しないその他の処理には有益だが、特定のオブジェクトにアクセスするのには有益ではないだろう。
【発明の概要】
【０００５】
本発明の一部の実施形態は、文書を記憶するための新規の方法を提供するものであり、この方法は、文書の少なくとも２つの異なる表現を記憶する。一部の実施形態では、方法は、文書のストリーム表現と、１つ以上のオブジェクト表現とを記憶する。これらの表現は、文書のファイルとして記憶されてもよいし、文書のメモリ内表現として記憶されてもよい。
【０００６】
一部の実施形態では、ストリーム表現は、規則的に配置された純粋のコンテンツ（例えば、文書のテキストについての一連の文字コード）だけを含んでいる。オブジェクト表現は、コンテンツのグループ分けと、グループ分けについての関連情報（例えば文書の構造、スタイル等）とを表す、各ノードのツリーとして記憶される。ノードの中にコンテンツを記憶するのではなく、各ノードは、ストリーム表現の中のインデックス位置に対する参照を含んでいる。
【０００７】
一部の実施形態は、２つのオブジェクト表現を含んでおり、１つは構造ツリーで１つはスタイリングツリーである。構造ツリーは、文書構造、すなわち、節、ページ、レイアウト、欄、パラグラフ、テキスト行、単語等を記憶するものである。この情報は、（例えば、リッチテキストワープロ文書における）文書内の符号化された情報から導出されてもよいし、そのような情報を符号化していない文書（例えば、ＰＤＦファイルのようなベクタグラフィックス文書）の再構成から導出されてもよい。ツリーの中の各構造ノードは、その構造についてのコンテンツが見つかる、ストリームの中のインデックスの範囲を参照する。そのようなツリーでは、親ノードの表す構造は、子ノードによって表される構造を含んでいる。
【０００８】
一部の実施形態のスタイリングツリーは、文書内の文字の形式についての情報を記憶する。一部の実施形態は、形式特性の階層を記憶しており、オブジェクトツリーの中の各ノードは、形式のスタイルと、ストリームの中のインデックスの範囲とを表す。例えば、下線部のセクションが、それより広い太字体のセクションの範囲内にある場合、全体的に太字セクションの範囲を持つ太字ノードによって表されるであろう。太字ノードは、太字セクションの範囲内に下線セクションの範囲を持つ、子である下線ノードを有するであろう。そのようなツリーにおいては、親ノードは、子ノードによって継承されるスタイル属性を表す。
【０００９】
構造ツリーおよびスタイリングツリーに加えて、一部の実施形態は、文書についてのその他のさまざまなタイプのオブジェクト表現を記憶してもよい。例えば、多様な実施形態によって、文書を作成するためのクリップパスのオブジェクトツリーや、多様な著者／編集者による文書の変更を追跡記録する校正ツリーや、意味(semantic)文書ツリー等が記憶されるであろう。
【００１０】
このような複数表現の手法によって、各種の共通の文書動作についての効率が良くなる。構造ツリーをナビゲートして所望の構造を見つけ、次いで、インデックスを用いてストリーム内で選択すべきコンテンツを識別することによって、構造（例えば、単語、行、パラグラフ等）の選択を効率良く行うことができる。他にも効率良く行われる動作の例として、一定のナビゲーション動作（例えば、章の見出しの中の検索用語を見つけること）や、（例えば、アプリケーション間で切り換えるために）或る形式から別の形式への文書の変換等がある。
【００１１】
前述した「発明の概要」は、本発明の一部の実施形態の簡単な紹介として役立てることを意図している。本明細書の中で開示される、全ての発明の主題の紹介または概要を意図しているのではない。以下に記す「発明を実施するための形態」、および「発明を実施するための形態」の中で言及される「図面」では、「発明の概要」の中で説明した実施形態についてだけでなく、他の実施形態についてもさらに説明しよう。従って、本明細書によって説明するすべての実施形態を理解するためには、「発明の概要」、「発明を実施するための形態」、「図面」の全部を検討することが必要である。また、請求される主題は、主題の精神から逸脱することなく他の特定の形態として実施されうることから、請求される主題は、「発明の概要」、「発明を実施するための形態」、「図面」の中の例示的な詳細によって限定されるのではなく、添付の請求項によって定義されるべきである。
【図面の簡単な説明】
【００１２】
本発明の新規の特徴を、添付の請求項に記述する。しかし、説明の目的で、本発明のいくつかの実施形態を以下の図面の中で記述する。
【図１】一部の実施形態による、複数の異なる表現が作成されて記憶される文書を示す図である。
【図２】文書のページの例を示す図である。
【図３】図２のページについて、一部の実施形態のストリーム表現を示す図である。
【図４】図２のページについて、オブジェクト表現を示す図である。
【図５】一部の実施形態の欄オブジェクトを概念的に示す図である。
【図６】一頁ものの文書を示す図である。
【図７】図６の文書について２つの別個のオブジェクトモデルを示す図である。
【図８】階層の各レベルが特定のスタイリング属性についての情報を記憶しているようなスタイリングオブジェクトツリーの一例を示す図である。
【図９】一部の実施形態の単語選択プロセスを示す図である。
【図１０】単語を強調表示して図２のページを示す図である。
【図１１】ユーザがナビゲートしたい文書の構造を表す文書構造ツリーにおいて所望のオブジェクトを識別するための、一部の実施形態のプロセスを概念的に示す図である。
【図１２】電子ブックの中の特定の章のタイトルを検索することを示す図である。
【図１３】文書の一部分の選択を別の形式に変換するために二重表現データモデルを用いるためのプロセスを概念的に示す図である。
【図１４】例示的な文書ページにおける選択を示す図である。
【図１５】図１４の文書ページについての例示的なオブジェクトツリーと、そのオブジェクトツリーを用いた変換プロセスによって生成された新たな形式の例示的な出力ストリームとを示す図である。
【図１６ａ】図１３のプロセスの一部として行われうる例示的な再帰プロセスを概念的に示す図である。
【図１６ｂ】図１３のプロセスの一部として行われうる例示的な再帰プロセスを概念的に示す図である。
【図１７】本発明の一部の実施形態が実装される電子システムを概念的に示す図である。
【発明を実施するための形態】
【００１３】
以下の記述において、説明を目的として多くの詳細を記述する。しかし、当業者であれば理解するであろうが、本発明は、これらの特定の詳細を使用しなくても実施されうる。他の例では、本発明の記述を不要な詳細であいまいにしないように、公知の構造およびデバイスはブロック図形式で示している。
【００１４】
本発明の一部の実施形態は、文書を記憶するための新規の方法を提供するものであり、この方法は、文書の少なくとも２つの異なる表現を記憶する。一部の実施形態では、方法は、文書のストリーム表現と、１つ以上のオブジェクト表現とを記憶する。これらの表現は、文書のファイルとして記憶されてもよいし、文書のメモリ内表現として記憶されてもよい。
【００１５】
図１は、一部の実施形態による、複数の異なる表現が作成されて記憶される文書１００を示す図である。図示するように、この例では、３つの異なる表現がこの文書について記憶される。第１の表現は、ストリーム表現１０５である。一部の実施形態では、ストリーム表現は、規則的に配置された純粋のコンテンツ（例えば、文書のテキストについての一連の文字コード）だけを含んでいる。ストリーム表現１０５は、つながっている一連の文字コードとして示すが、一部の実施形態では、ストリームは、実際には、１６進数の文字コードを表すバイトのシーケンス（すなわち、０と１）として記憶される。
【００１６】
文書１００についての第２および第３の表現は、オブジェクト表現１１０および１１５である。一部の実施形態では、オブジェクト表現は、コンテンツのグループ分けと、グループ分けについての関連情報（例えば文書の構造、スタイル等）とを表す、各ノードのツリーとして記憶される。ノードの中にコンテンツを記憶するのではなく、各ノードは、ストリーム表現の中のインデックス位置に対する参照を含んでいる。
【００１７】
図１に示すように、一部の実施形態は、２つ（またはそれ以上）のオブジェクト表現（例えば、構造ツリーとスタイリングツリー）を含んでいる。一部の実施形態の構造ツリーは、文書構造、すなわち、節、ページ、レイアウト、欄、パラグラフ、テキスト行、単語等を記憶している。この情報は、（例えば、リッチテキストワープロ文書における）文書内の符号化された情報から導出されてもよいし、そのような情報を符号化していない文書（例えば、ＰＤＦファイルのようなベクタグラフィックス文書）の再構成から導出されてもよい。ツリーの中の各構造ノードは、その構造についてのコンテンツが見つかる、ストリームの中のインデックスの範囲を参照する。そのようなツリーでは、親ノードの表す構造は、子ノードによって表される構造を含んでいる。
【００１８】
一部の実施形態のスタイリングツリーは、文書内の文字の形式についての情報を記憶する。一部の実施形態は、形式特性の階層を記憶しており、オブジェクトツリーの中の各ノードは、形式のスタイルと、ストリームの中のインデックスの範囲とを表す。例えば、下線部のセクションが、それより広い太字体のセクションの範囲内にある場合、全体的に太字セクションの範囲を持つ太字ノードによって表されるであろう。太字ノードは、太字セクションの範囲内に下線セクションを持つ、子である下線ノードを有するであろう。そのようなツリーにおいては、親ノードは、子ノードによって継承されるスタイル属性を表す。
【００１９】
構造ツリーおよびスタイリングツリーに加えて、一部の実施形態は、文書についてのその他のさまざまなタイプのオブジェクト表現を記憶してもよい。例えば、多様な実施形態によって、文書を作成するためのクリップパスのオブジェクトツリーや、多様な著者／編集者による文書の変更を追跡記録する校正ツリーや、意味文書ツリー等が記憶されるであろう。
【００２０】
このような複数表現の手法によって、各種の共通の文書動作についての効率が良くなる。構造ツリーをナビゲートして所望の構造を見つけ、次いで、インデックスを用いてストリーム内で選択すべきコンテンツを識別することによって、構造（例えば、単語、行、パラグラフ等）の選択を効率良く行うことができる。他にも効率よく行われる動作の例として、一定のナビゲーション動作（例えば、章の見出しの中に検索用語を見つけること）や、（例えば、アプリケーション間で切り換えるために）或る形式から別の形式への文書の変換等がある。
【００２１】
操作によっては、構造オブジェクトツリーを用いる（例えば、或るページに関してユーザが選択した開始点および終点座標を特定する）と非常に効率良く行える。別の操作は、スタイルツリーを用いる（例えば、所与の文字に適用可能な純粋なスタイル属性を判定する）方が効率良く行えるが、さらに別の操作は、ストリーム表現を用いる（例えば、全文検索用に文書にインデックスを付ける）かまたは、その文書用に記憶された別のオブジェクトツリーを用いると、非常に効率良く行える。
【００２２】
本発明のさらなるいくつかの詳細な実施形態について以下に記述する。セクションＩは、コンテンツストリームと文書構造ツリーとを含んでいる文書のデータモデルについて記述する。次いで、セクションＩＩは、文書のデータモデルに対する、スタイル属性ツリーおよびその他のオブジェクトツリーの追加について記述する。セクションＩＩＩは、データモデルのさまざまな用途について記述する。最後に、セクションＶは、本発明の一部の実施形態が実装される電子システムについて記述する。
【００２３】
Ｉ．文書の複数の表現
上記のように、一部の実施形態は、文書の複数の表現を記憶するものである。一部の実施形態では、アプリケーションが、（ｉ）ストリーム表現と、（ｉｉ）１つ以上のオブジェクト表現とを記憶する。複数の表現は、両者に同時にアクセスすることができ、かつ、文書処理の効率化のために一緒に使用されうる別のタイプの情報を提供するという点で、補完的である。一部の実施形態では、オブジェクト表現は、文書構造（例えば、ページ、レイアウト、欄、パラグラフ、テキスト行、単語等）についての情報を記憶する構造オブジェクトツリーを含んでいる。一部の実施形態では、この構造ツリーは、「Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ｏｆ  Ｌａｙｏｕｔ  ａｎｄ  Ｃｏｎｔｅｎｔ  Ｆｌｏｗ  ｏｆ  ａｎ  Ｕｎｓｔｒｕｃｔｕｒｅｄ  Ｄｏｃｕｍｅｎｔ」と題された米国特許公開公報第２０１０／０１７４９８５号の中に記述されたものと同様のやり方で導出される。
【００２４】
図２は、一例としてページ２００を示す図である。ページ２００は、一頁ものの文書であってもよいし、複数頁の文書からの１ページであってもよいだろう。図に示すように、ページ２００は、３つのパラグラフ２０５−２１５を持つ１つの欄を含んでいる。第１パラグラフ２０５は、５つのテキスト行を含んでおり、第２パラグラフ２１０は、６つのテキスト行を含んでおり、第３パラグラフは、５つのテキスト行を含んでいる。各テキスト行は、さまざまな数の単語を含んでいる。
【００２５】
図３は、ページ２００についての一部の実施形態のストリーム表現３００を示す図である。図示するように、ストリーム表現３００は、ページ２００のコンテンツを表す１６進文字コードの列である。文書内の各文字は、文字を表すのに用いられる１６進コード（例えば、「Ｂ」を表す１６進数である４２）に変換される。この例では、スペースと改行もストリームの中に含まれているが、一部の実施形態では、これらの余白文字は、厳密に必要ではなく、ページのオブジェクト表現（例えば構造ツリー）から推論することができる。
【００２６】
図示するストリームは、ＡＳＣＩＩ文字表現（２つの１６進数）を用いているが、一部の実施形態は、ユニコード表現（４つの１６進数）を用いる。例示するページ２００には含まれていないが、一部の実施形態は、プレースホルダ文字（例えば、１６進コードＦＦＦＣを持つユニコードの「オブジェクト置換文字」）を使って、文字以外の基本コンテンツ（例えば画像、形状等）を表す。文字は１６進コードとして示されているが、一部の実施形態は、ページ内の文字について、１６進コードを表すビット列（すなわち０と１）として文字列を記憶するか、または、異なるコードを用いる。
【００２７】
図４は、ページ２００についての一部の実施形態の例示的なオブジェクト表現４００を示す図である。具体的には、オブジェクト表現４００は、文書内の各構造についてオブジェクトを記憶している、構造ツリーの一部分である。図４は、ページ２００についての文書構造ツリーの一部分を示している。一部の実施形態では、文書についての１つの親ノードは、文書内の各ページについて、そのような部分を１つ含むであろう。
【００２８】
文書の構造ツリー４００の中の各ノードを、数の範囲として示す。これらの数は、コンテンツのストリーム表現３００の中のインデックスへの参照を表す。図示するように、文書のオブジェクトツリー４００の図示する部分は、ページノード４０５と、１つの欄ノード４１０と、３つのパラグラフノード４１５−４２５と、１６個のテキスト行ノード４３１−４４６とを含んでいる。この図では、単語ノード４５０および４５５を２つだけ示しているが、当業者であれば、オブジェクトツリーには（図に示すことができないほど）多くの単語ノードが記憶されていることは理解できるであろう。加えて、単語ノードの下には、基本文字ノード（例えばグリフ）が存在していてもよく、それらはそれぞれ、ストリーム内の１つの文字を参照する。
【００２９】
一部の実施形態では、この構造情報は、文書内に符号化された情報が含まれている場合（例えば、Ａｐｐｌｅ  Ｐａｇｅｓ（登録商標）またはＭｉｃｒｏｓｏｆｔ  Ｗｏｒｄ（登録商標）によって作成される文書のような、リッチテキストワープロ文書）、そのような情報から抽出される。文書内にそのような符号化された構造情報が含まれていない場合（例えば、典型的なＰＤＦ文書）、一部の実施形態では、文書再構成プロセスを用いて、文書内のプリミティブ要素（基本要素）（例えばグリフ）に基づく構造情報を導出する。一部の実施形態の文書再構成プロセスは、テキスト行、欄、パラグラフ、文書要素を読む順序等を識別する。
【００３０】
構造ツリー４００では、特定の構造の範囲は、その構造が対応しているコンテンツストリームにおける範囲を示す。従って、例えば、第１パラグラフ４１５は、１６進コード文字１−３３８に対応する。一部の実施形態では、この情報は、数のペアとして記憶される。一部の実施形態では、開始インデックスと、その範囲内のその後の連続するインデックスの総数とを記憶し、他の実施形態では、開始インデックスと終点インデックスとを記憶する。図４では、話を簡単にするために、開始インデックスと終点インデックスとを用いて範囲を示す。
【００３１】
一部の実施形態では、上記のように、コンテンツストリームは、区切り文字（例えば、スペース、改行等）を含んでいるが、これらはオブジェクトツリーから（例えば、単語間のスペース、パラグラフ間の改行等）導出することができるものである。一部の実施形態では、構造ツリー内のオブジェクトのインデックス範囲内にこれらの区切り文字を含んでいる。例えば、パラグラフ４１５の範囲は、第１パラグラフの終点の改行についての１６進コードを含んでいる。
【００３２】
図に示す範囲に加えて、一部の実施形態では、各構造ノード（すなわち構造オブジェクト）は、構造についての追加情報を含んでいる。図５は、一部の実施形態の欄オブジェクト５００を概念的に示す図である。このオブジェクトは、オブジェクトによって定義された欄についての情報を記憶している。一部の実施形態では、欄オブジェクト５００は、欄クラス内のオブジェクトであり、図示する各種のデータは、オブジェクトの変数である。図のように、欄オブジェクト５００は、欄を識別するのに用いられる一意の欄ＩＤと、欄を含んでいる文書のコンテンツストリームを指し示すインデックスの範囲を記憶するインデックス範囲と、欄属性５０５の集合とを含んでいる。加えて、一部の実施形態では、オブジェクトの子たちへの参照（この場合、複数のパラグラフ）だけでなく、オブジェクトの親への参照（この場合、１つのページ）も含んでいる。一部の実施形態では、構造ツリー内のすべてのオブジェクトについて一方向の参照だけ（すなわち、オブジェクトの親か、オブジェクトの子たちか、いずれか一方への参照）を記憶する。
【００３３】
欄属性５０５は、構造としての欄についての各種の情報、すなわち、ページ内の欄の境界線と、欄の回転角（すなわち、欄がページ上で水平向きか垂直向きか、あるいはその中間のどこかに向いているのか）と、文書を読む際の前および後の欄への参照と、それ以外の欄属性とを記憶している。一部の実施形態では、多様な構造オブジェクトが、多様な属性を含んでいる。例えば、パラグラフオブジェクトが、欄オブジェクト５００と同様の属性（境界線、回転角、次および前のパラグラフ）を含んでいてもよいだろうが、行間隔情報、アラインメント情報等も含むこともできるだろう。
【００３４】
一部の実施形態では、異なる表現間の適切な調整を保証するために、ストリームツリーおよびオブジェクトツリーに５つの条件が課される。第１に、ストリームは、効率的なストリーム処理のために自然な順序で配置される。関連のストリーム処理にテキスト検索および選択が含まれる電子文書の場合、自然な順序とは、読む順序のことである。読む順序は、文書内の符号化された情報から（例えば、ワープロアプリケーションによって）導出されてもよいし、上での参照により本願に援用する米国特許公開公報第２０１０／０１７４９８５号の中に記述されているように文書の分析から得られてもよい。
【００３５】
第２に、各ノードが参照するインデックス位置は、単一の連続する範囲であるＲ＝｛ｉ，ｉ＋１，．．．，ｉ＋ｎ−１｝の中にある。すなわち、各オブジェクトは、コンテンツストリーム内にすき間のないようなインデックス範囲を参照する。従って、その範囲は自然数のペア（ｉ，ｎ）として記憶されてもよく、ここでｉは、開始インデックスであり、ｎは、その範囲内の連続するインデックスの総数である。図４に示すように、範囲は、開始インデックスおよび終点インデックスを用いて、（ｉ，ｉ＋ｎ−１）として記憶されてもよいだろう。
【００３６】
第３に、親ノードの範囲は、それが持つノードの範囲の和集合である。これによって、文書モデルの或るレベルにおけるすき間が防止される。例えば、或るページ上のレイアウトは、そのページの基本要素をすべて含んでいなければならない。或るレイアウトの中の欄は、そのレイアウトの基本要素をすべて含んでいなければならないし、或る欄の中のパラグラフは、その欄の基本要素をすべて含んでいなければならない等々である。しかし、一部の実施形態では、親ノードの範囲は、単に、その子ノードの和集合を含んでいるだけである。すなわち、子ノードは、その親ノードの中にないコンテンツを含むことはできないが、親ノードは、そのいずれの子ノードの中にもないコンテンツを含んでいてもよい。そのような実施形態では、子ノード間にすき間が（例えばスペース用などとして）ありうる。完全な和集合を必要とするプロセスならば、それらが動作する際に、すき間が欠けているノードを効果的に推定することができる。従って、データモデルにまったく情報を追加しないノードは、これらの実施形態においては記憶される必要がなく、それによって記憶スペースが解放される。
【００３７】
第４に、いずれかの２つの兄弟ノードの範囲は、離される。これは、２つの兄弟ノードの間には重なりがないことを意味する。従って、或る文字が、２つの異なる単語、行、パラグラフ等に存在することはできない。最後に、第１のノードが第２のノードの兄である場合には、第１のノードの開始インデックスは、第２のノードの開始インデックスより小さいかまたは等しい。これによって、兄弟ノードは規則的に配置されることが必須となる。従って、図示するように、第１のテキスト行のノード４３１は、パラグラフノード４１５の下の第１のノードである。明らかに、文書構造ツリー４００およびストリーム３００は、これらの５つの属性を満たしている。結果として、文書構造ツリー４００について、階層の各レベルは、ページ２００上のコンテンツをすべて含んでいる。
【００３８】
ＩＩ．追加のオブジェクト表現
文書構造ツリーは、文書を表現するためにコンテンツストリームと併せて一部の実施形態によって用いられうるオブジェクト表現の１つのタイプである。文書構造ツリーに加えて（またはその代わりに）、一部の実施形態は、文書についての追加のオブジェクト表現を含んでいる。そのようなオブジェクト表現の１つは、文書構造ツリーと同じコンテンツストリームに関して、コンテンツスタイリングを実装する。文書を作成することを目的として、ソフトウェアアプリケーションは、それを使ってコンテンツを作成するための承継されるスタイルを決定するため、スタイルツリーのノードを通って再帰的に降下する。各文字についてスタイル属性を設定するのではなく、スタイルオブジェクトツリーを用いることによって、ツリーの中の各ノードがその各子孫によって再利用されることが可能になる。
【００３９】
例えばＸＳＬ（ｅＸｔｅｎｓｉｂｌｅ  Ｓｔｙｌｅｓｈｅｅｔ  Ｌａｎｇｕａｇｅ）のような一定のプロフェッショナル・スタイル・モデルは、テキストを読む順序とは異なる順序でテキストをレイアウトする能力を有している。例えば、表の見出しは、読む順序の規則に基づけば、読む順序では表より先に来ると考えられるであろうが、表の下に書かれている。ＸＳＬでは、これを、構造ツリーを、形式オブジェクトがレイアウトおよびスタイル情報を含んでいるような「形式オブジェクト」ツリーに変換することとみなす。複数の表現という文脈でそのようなツリーを実装するため、一部の実施形態では、前のセクションで述べた第５の条件を取り除き、かつ、兄弟の順序が乱れてもよいようにすることが必要となる。
【００４０】
形式ノードの順序が乱れている場合であっても、形式ノードと構造ノード（例えば、構造ツリー４００の中のノード）とはいずれも、共通のコンテンツストリームの中の範囲を保持している。従って、アプリケーションは、どの構造オブジェクトが各形式オブジェクトを生じさせるかを迅速に判定することができる。形式オブジェクトが、ｉからｊまでの範囲を有する場合には、その範囲と交差する範囲を持つ構造オブジェクトはいずれも、形式オブジェクトによって影響を受ける。
【００４１】
図６は、１ページの文書６００を示す図である。文書６００は、３つのパラグラフを含んでおり、その各々が多数の単語を含んでいる。加えて、各種の形式特性が、第１のパラグラフの各部に適用されている。第１行の一部分は、斜体字にされ、第２行のテキストの各部には、斜体、太字、下線が施されている。また、第３行および第４行には、スタイリングの変更が適用されている。文書６００のテキストはページ２００のテキストと同じだから、コンテンツストリーム３００は、文書６００を正確に表現している。
【００４２】
図７は、文書６００の２つの別個のオブジェクトモデルを概念的に示す図である。第１のオブジェクトモデル７０５は、文書構造ツリー４００と同様の文書構造ツリーである。この図およびそれに続く各図では、話を簡単にするために、コンテンツストリームの１６進コードのインデックスではなく、文字範囲（すなわち、文書内の文字の総数）が用いられている。当業者であれば、これらの範囲は、コンテンツストリームインデックスに容易に変換できることは理解するであろう。また、話を簡単にするために、文書構造モデルは、ページと、パラグラフと、単語ノードとだけを示している。当業者であれば、多様な実施形態が、多様なレベルの階層構造オブジェクトを用いて文書構造を表現するということを理解するであろう。例えば、図４の構造ツリー４００に示すように、テキスト行がパラグラフと単語との間に含まれてもよいし、欄がパラグラフとページとの間に含まれてもよいし、以下同様である。
【００４３】
第２のオブジェクトモデル７１０は、スタイル属性ツリーである。コンテンツオブジェクトを体系化するのではなく、スタイル属性ツリーは、コンテンツが属する構造には関係なく、コンテンツの形式属性を体系化する。上記のセクションＩで論じた文書構造ツリーに適用されるのと同じデータモデル属性が、スタイル属性ツリー７１０にも適用される。すなわち、（ｉ）各ノードによって参照されるインデックス位置は、連続する範囲であり、（ｉｉ）親ノードの範囲は、その子ノードの範囲の和集合であり、（ｉｉｉ）いずれかの２つの兄弟ノードの範囲は、離れており、（ｉｖ）兄弟ノードの開始インデックスは順序付けられている。
【００４４】
すべての文字は、同じフォント書体（例えば、Ｈｅｌｖｅｔｉｃａ、Ｔｉｍｅｓ  Ｎｅｗ  Ｒｏｍａｎ等）とサイズ（例えば１２ポイント）とを有しており、従って、ルートノード７１５は、これらの属性を含んでおり、その範囲は全部で６７４文字である。一部の実施形態は、図７に示すような複数のツリー構造を、そのページについてのより高レベルのルートノードと共に、含んでいるだろう。加えて、文書全体は特定のフォントであるが、異なるセクションが異なるサイズを有している場合、フォント書体およびサイズは、異なるオブジェクトレベルとして定義されてもよい。ルートノード７１５の子（および孫等）は、各種の形式属性を、参照される文字集合に適用する。例えば、文書の斜体字の開始部分は、ノード７２０によって指示され、ノード７２０は、文書の最初の２８文字の斜体字化を指示する。これらの文字には追加の形式が適用されないため、このノードは子ノードを有しない。
【００４５】
他方、斜体字ノード７２５は、下線部を下線のない部分と区別するための追加の子ノードを有する。図示するように、斜体の文字４２−６１のうち、これらの文字のうちの３つ４２−４４は下線がないのに対し、残りの文字４５−６１は下線が引かれている。加えて、下線が引かれた文字のうちで、文字４５−５４は太字であり、文字５５−６１は、通常の重みである（すなわち、太字でない）。従って、文字５３を描くには、アプリケーションは、ツリー７１０を通過して、文字５３は、文書全体に適用されているフォント書体とサイズとを有しており、斜体字であり（ノード７２５）、下線を引いてあり（ノード７３０）、太字である（ノード７３５）と判定する。このようにして、各ノードは、その親の形式属性を継承する。
【００４６】
オブジェクトモデルの継続性属性を維持するため、一部の実施形態は、例えばノード７４０または７４５のような、無変化ノードを含んでいる。ノード７４０は、文字２９−４１には、ルートノードの形式以外の形式が適用されないことを示す。このノードは、斜体字ノード７２０と斜体字ノード７２５との間のすき間を埋める働きをする。ノード７４５は、文字５５−６１が太字でないことを示す。それにも関わらず、これらの文字は、ノード７３０から継承した下線属性およびノード７２５から継承した斜体字属性、ならびにノード７１５からのフォント書体とサイズとを保持している。
【００４７】
一部の実施形態は、太字、斜体字、下線のようなすべての適用属性がツリーの中で同じレベルである可能性を持つスタイル形式ツリーではなく、特定の属性については特定のレベルを含んでいる。例えば、ツリーは、フォント書体を示す第１のレベルと、フォントサイズを示す第２のレベルと、重み（例えば、太字か太字でないか、諧調と共に）を示す第３のレベルと、傾斜（例えば、斜体字かまっすぐか、諧調と共に）を示す第４のレベルと、下線属性（例えば、下線なし、一重の下線、二重の下線等）を示す第５のレベルと、さらには、その他の文字形式属性についてのレベルも有していてよいだろう。
【００４８】
図８は、そのようなスタイリングオブジェクトツリー８００の一例を示す図であり、この中で、階層の各レベルは、特定のスタイリング属性についての情報を記憶している。オブジェクトツリー８００は、フォント書体と、フォントサイズと、傾斜と、フォント重みと、下線とについての階層レベルを含んでいる。スタイルオブジェクトは、同じ文書６００を参照しており、従って、スタイリングツリー７１０と同じ情報を伝達する。オブジェクトツリー８００の場合、階層の各レベルは、コンテンツストリームの中のインデックスの全範囲を参照し、オブジェクトは、上記のセクションＩで述べたデータモデル属性を満たしている。
【００４９】
上位２つのレベルにおけるオブジェクト、すなわちフォント書体オブジェクト８０５およびフォントサイズオブジェクト８１０によって伝達されるように、フォント書体（Ｈｅｌｖｅｔｉｃａ）およびフォントサイズ（１４ポイント）は、文書全体を通じて同じである。次の階層レベルは、傾斜であり、この場合、傾斜がないかまたは斜体字かのいずれかを示す。傾斜オブジェクトの下には、フォント重みオブジェクトがあり、次いで下線オブジェクトがある。多様な実施形態において、フォントスタイリング属性には、構造についてそのような順序が存在するという点で、当然の階層というものは存在しないのだから、多様な属性が階層内の多様な順序で配置されてもよい。一部の実施形態では、ツリーをより単純にすることに基づいて決められた、動的な順序が用いられる（例えば、間欠的に斜体字にされる大きな太字のセクションがある場合、傾斜オブジェクトをフォント重みオブジェクトの子とする）。
【００５０】
形式オブジェクトツリーをコンテンツツリーと離しておく理由の１つは、形式のあるテキストの連続的な広がり（例えば、１つの欄から次の欄へと続く斜体字セクション）は、スタイリングを適用する限り、複数のオブジェクト間で分割される必要がないようにするということである。この場合、単一の斜体字スタイルのオブジェクトは、ツリー構造規則を侵害せずに両方の欄の子となることはできないであろうから、別個のスタイルツリーは有益である。図６に示す例では、第１行の終点から第２行の中間まで続く斜体字は、階層構造を保持するために２つの別個のオブジェクトによって表現される必要があるであろう。
【００５１】
構造ツリーノードと形式オブジェクトツリーノードとはいずれも、共通のコンテンツストリームの中の範囲を保持しているため、アプリケーションは、どの構造オブジェクトが各形式オブジェクトを生じさせるか（その範囲が形式オブジェクトの範囲と重なるような構造ツリーオブジェクト）を容易に判定することができる。従って、別個のスタイルオブジェクトツリーを用いることは、許可された形式に対して制約が課されるような、制約に基づくスタイリングを実装するのに特に有益である可能性がある。そのような制約の例として、ページ上に存在しなければならないテキストの最小限の分量や、コンテンツの集合が固定サイズのボックスに適合（フィット）することという要件や、図面は、それを参照する記事から最小距離内にある必要があること等がある。形式が完了するまで、アプリケーションは、そのような制約が侵害されているかどうかを識別できない（例えば、テキストは、太字であれば大きくなるため、固定サイズのボックスの中に完全に適合しない可能性があるだろう）。どの構造オブジェクトが、侵害の原因となった形式オブジェクトを生じさせたかをアプリケーションが知っている場合、アプリケーションは、制約が満足されるまで、これらの構造のスタイリングを自動的に調整することができる。例えば、スタイル属性ツリーを用いて形式が適用された後、必要に応じて、結果としてのオブジェクトが適合するまで、関連のテキストが圧縮されるかまたは画像のサイズが縮小されてもよい。
【００５２】
ＸＳＬの例では、２つのツリーの間で変換を行う場合、第２のツリーの中で新たに作成されたオブジェクトが、第１のツリーの中の古いオブジェクトにどのように関係するのかについて保存された情報は何もなく、代わりに、単純に、古いオブジェクトを新たなオブジェクトに合致(match)させる手順があるだけである。本明細書で記述したデータ構造を使って変換を行う場合、一部の実施形態では、オブジェクトのインデックス範囲を追跡するための別のネームスペースに追加の属性を定義する。次いでフォーマッタが、オブジェクトのインデックスを知り、同じネームスペースを用いてＸＳＬ形式オブジェクトの中にインデックスを出力してもよい（または、すべての情報をメモリ内に単に記憶する）。一部の実施形態では、変換は、ＸＳＬＴ（ＸＳＬ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ  Ｌａｎｇｕａｇｅ）を用いて行われる。
【００５３】
上記のセクションは、２つの特定のタイプのオブジェクトツリー（文書構造ツリーおよびスタイル属性ツリー）について記述したが、当業者であれば、これらのモデルは、コンテンツストリームを指し示す各ノードを使って記憶されうる、多くの異なるタイプのオブジェクトツリーのうちの２つの例でしかないことを理解するであろう。そのようなオブジェクトツリーの一例としてクリップパスツリーがあり、これは、文書を作成するためのクリップパスの集合を記憶するものである。クリップパスとは、パスの内側のコンテンツは作成されるが、パスの外側のコンテンツは無視される（すなわち除外される）ように定義されたパスのことである。例えば、ページは、クリップパスを持っているであろう（それによって、ページの外側で実行されるコンテンツが描画されるのを防ぐ）。ページ内では、テキストボックスが、クリップパスを持っていてもよいだろうし、テキストボックスの内側のフレーム内の画像等もそうであろう。これらの（動的に変化しうる）クリップパスは、クリップパスの内側に描画されるコンテンツを参照するツリー構造として配置することができる。
【００５４】
もう１つの例として、レイアウトを定義する（例えば、オブジェクトの境界線を与える）オブジェクト構造ツリーと比べると、レイアウトに関係のない、高レベル意味文書ツリーがある。そのような文書ツリーは、例えば、（複数のページに及びうる）記事オブジェクトや、章の見出しノードや、（タイトルノード、著者ノード等を含みうる）図書目録登録ノードのような各ノードを含んでいる可能性もあるだろう。そのような意味ツリーでは、パラグラフオブジェクトは、複数の欄またはページに及ぶこともあるだろう（そして、欄オブジェクトまたはページオブジェクトは、意味構成体というよりレイアウト構成体であるため、それらは存在しないこともあるだろう）。次いで、コンテンツを、ユーザ、デバイス、またはアプリケーションの設定に基づいて、各種の異なるレイアウトとして（例えば、すべてを１ページにしたり、複数のページに渡って広げたり、さまざまな数の欄を用いたり、多様なフォントや別のスタイルを用いたりして）レイアウトすることができる。ＤｏｃＢｏｏｋは、同様の構造を持つＸＭＬ形式の一例である。意味文書ツリーの各ノードは、コンテンツ構造ツリーの各ノードと同様に、コンテンツストリームを指し示してもよいだろう。
【００５５】
他にも、そのようなオブジェクトツリーは存在しうる。例えば、さまざまな著者による文書の校正を追跡記録する校正ツリー、同様に注釈を追跡記録する注釈ツリー、文書のさまざまな部分についての著者および著者のグループを追跡記録する著者ツリー、入れ子になった検索結果を追跡記録する検索結果ツリー（すなわち、ツリーのルートが最初の検索で、各子ノードがドリルダウン検索である）等は、すべて、本明細書に記述された複数の表現のデータモデルを用いてできるさまざまなタイプのオブジェクトツリーの例である。
【００５６】
ＩＩＩ．複数の表現の例示的な用途
上記のセクションでは、一部の実施形態によって用いられる、文書の複数の表現の例を記述した。セクションＩおよびＩＩで記述したように、一部の実施形態では、文書を表現するためのコンテンツストリームと、１つ以上のオブジェクトツリーとを（ファイルまたはメモリ内表現として）記憶する。これらのオブジェクトツリーは、セクションＩで記述したように、文書構造ツリーを含んでいてもよいし、セクションＩＩで記述したように、スタイル属性ツリーを含んでいてもよいし、その他のオブジェクトツリーを含んでいてもよい。これらの多様な表現は、補完的に用いられてもよい。以下のサブセクションでは、さまざまな表現の３つの異なる用途、すなわち、コンテンツオブジェクトを選択すること、文書をナビゲートすること、および文書の形式を変換することについて記述しよう。
【００５７】
Ａ．選択
コンテンツオブジェクト（例えば、単語、テキスト行、パラグラフ等）を選択することは、文書ツリーとコンテンツストリームとの組み合わせを用いて非常に効率的に行われうるプロセスである。本質的に、文書のユーザが、コンテンツオブジェクト（例えば、単語、パラグラフ等）を選択するための入力を行う時、文書を表示するアプリケーションは、ユーザ入力を特定のページの特定のｘ−ｙ座標に関連付け、次いで、そのページおよび座標に対応する文書構造ツリーの中の適切なレベルのノードを識別してもよい。このノードは、コンテンツが位置しているコンテンツストリームの中の或る範囲を示す。
【００５８】
図９は、一部の実施形態のそのような単語選択プロセスを示す図である。この図は、ページ２００を示しており、従って、上記のセクションＩに記述したように、文書構造ツリー４００を、この文書用に生成されたコンテンツストリーム３００と共に示している。図９の左側に示すように、今、カーソル９０５が、文書２００の中の単語「ｐｉｌｏｗｅｓｔａｎ」の上に位置している。この単語を選択するために、ユーザは、単語選択動作（例えば、カーソルコントローラをダブルクリック、または、単語の表示上のタッチスクリーンをダブルタップ、あるいは、その他の単語選択入力動作）を行う。
【００５９】
ユーザがこの選択入力を行うと、アプリケーションは、入力を特定のｘ−ｙ座標に変化させて、ユーザが選択したいコンテンツ構造のタイプを決める。上記のように、ここに示した事例では、ユーザは、単語を選択するための入力を行った。一部の事例では、ユーザは、テキスト行またはパラグラフを（例えば、トリプルクリックまたはトリプルタップ、パラグラフ選択用の一般的な入力を用いて）選択するであろう。また、ユーザは、カーソルを保持したままドラッグしても（または、タッチスクリーンに沿って指で触れても）よいだろうし、その場合、選択の開始点を、特定の文字に変化させる必要があるだろう。
【００６０】
図９の中央に示すように、この選択をすると、アプリケーションは、オブジェクトツリー４００をナビゲートし、選択された座標において単語を識別する。オブジェクトツリーを、ページレベルから欄レベルまで通過し（その各々は１つのノードだけを含む）、次いで、識別された座標をその境界線が含むようなパラグラフが見つかるまで、各パラグラフノードが順番に検索される。識別されたパラグラフノードの範囲内で、識別された座標をその境界線が含むようなテキスト行が見つかるまで、各テキスト行ノードが検索される。このプロセスは、選択される単語の境界線を見つけるために、識別されたテキスト行（テキスト行の中の単語）のすべての子を検索することによって、単語レベルで繰り返される。
【００６１】
図示するように、この場合、単語ノード９１０が、選択されたノードとして識別される。この単語オブジェクトは、コンテンツストリーム３００を参照すると、７８０−８００のインデックス範囲を記憶している。これを、図９に、ノード９１０からコンテンツストリーム３００を指し示す矢印で示している。次いで、これらのインデックスにおける１６進コード文字が、ストリームの中で識別される。インデックスは知られているのだから、ストリームの最初から読む必要はなく、従って、文字を迅速に識別することができる。
【００６２】
次いで、文書を表示するアプリケーションは、選択を示すために、選択された単語の中の文字を強調表示してもよい。図１０は、ページ２００を、単語１００５を強調表示した状態で示す図である。一部の実施形態は、画像フィルタを文字の表示に適用することによって、または、文字のスタイル属性を修正することによって、この強調表示を行う。
【００６３】
ここから、ユーザは、挿入マーカ（例えば、カーソル、タッチスクリーン上の指、等々）をドラッグするかまたはキーストローク（例えばシフト＋矢印）を用いることによって、この選択を拡張してもよい。ストリーム表現は順序付けられているのだから、選択範囲が追加の文字を含む時、範囲の開始インデックスを減少（または、終点インデックスを増加）させて、これらの追加文字を含むようにさせ、文字の表示を適切に修正してもよい。
【００６４】
選択されたテキストに対してユーザが追加の操作を行う場合、アプリケーションは、オブジェクト表現のうちの１つまたは両方を用いるように切り換えてもよい。例えば、選択されたテキストをユーザが仮想クリップボードにコピーする場合には、アプリケーションは、以下のサブセクションＩＩＩ．Ｃに詳述するように、オブジェクト表現を用いて、選択された部分の形式を変換してもよい。ユーザが、スタイル属性をテキストに適用する（例えば、テキストに下線を引く）場合には、スタイル属性オブジェクトツリーが修正されるであろう。
【００６５】
アプリケーションがどのツリー（すなわち、階層的に関連付けられたオブジェクトの集合）にアクセスした場合でも、アプリケーションは、必要なオブジェクトを容易に見つけることができる。なぜなら、オブジェクト（コンテンツオブジェクトかスタイルオブジェクトか、いずれか一方）のインデックス範囲は既知であり、かつ、オブジェクトツリーに関する制約によって、隣接する文字は隣接する葉ノードの中に存在する（ツリーの縦型順序付けにおいて隣接する）ことが保証されているからである。例えば、開始インデックスが、２だけ減少された場合には、選択は、「ｐｉｌｏｗｅｓｔａｎ」単語ノードの親ノードの兄の最後の子孫である、「ｔａｇｅｎｅｕｔｉａｎ」の中の文字を含むように増加するであろう。すなわち、アプリケーションは、（それはテキスト行の最初の単語なのだから）単語ノード９１０の兄は存在しないと判断するであろうし、従って、テキスト行ノード４３９の兄まで移動するであろう。これは、テキスト行ノード４３８（ストリームインデックス６７９−７７８）であり、アプリケーションは、次いで、このノードの最後の子孫を見つけるであろう。
【００６６】
Ｂ．ナビゲーション
状況によっては、ユーザが文書をナビゲートする場合、文書についてのコンテンツストリーム表現とオブジェクトツリー表現との組み合わせが用いられて、より効率的な処理が行われてもよい。２つの表現の組み合わせは、ユーザが文書の特定の部分をナビゲートして、その後、隣接する部分へと移動することを選択する場合に、特に有益となる。これらのプロセスは、ユーザが文書をスクロールしながらナビゲートすることを望みそうもない、画面が小さいデバイス（例えばスマートフォン）に特に適用可能でありうるが、いかなる電子デバイス上で動作するアプリケーションにも、同様に適用可能である。
【００６７】
図１１は、ユーザがナビゲートすることを望む文書内の構造を表す文書構造ツリーの中の所望のオブジェクトを識別するための、一部の実施形態のプロセス１１００を概念的に示す図である。プロセス１１００について、そのようなプロセスの具体的な一例を示す図１２を一部参照することにより記述しよう。図１２では、ユーザが電子ブック１２００の中の特定の章のタイトルを検索し、アプリケーションは、電子ブックについての文書構造ツリー１２０５を用いて、その電子ブックについてのコンテンツストリーム１２１０の中のインデックス範囲を識別する。一部の実施形態では、プロセス１１００は、例えばＰＤＦビューワや、ワープロアプリケーションや、電子ブックリーダ等のような、文書（例えば電子ブック）を表示するためのアプリケーションによって行われる。
【００６８】
図示するように、図１２は、電子ブック１２００のために２つの表現が記憶されることを示す図である。第１の表現は、章のタイトルを含めて、電子ブックの中のすべての文字の表現を（例えば、１６進コードで）含んでいるコンテンツストリーム表現１２１０である。第２の表現は、文書構造ツリー１２０５（すなわち、階層的に構成されたオブジェクトの集合）である。文書構造ツリーの中の各オブジェクトは、電子ブックを章に分けており、その第１の子は、常に、タイトルオブジェクトである。タイトルに続いて、特定の章のパラグラフがある。一部の実施形態では、タイトルオブジェクトは、特定のタイプのパラグラフオブジェクト（例えば、それがタイトルであることを示す変数を持つパラグラフオブジェクト）である。
【００６９】
これらのノードの多くは、子ノード（テキスト行、基本的な文字等）を有しているだろう。当業者であれば、そのような文書については、その他の文書構造モデルが可能であることを理解するであろう。例えば、章ノードの子ノードは、ページノードであってもよいし、その結果、タイトルが、各章の第１ページノードの第１子ノードであってもよいだろう。しかし、電子ブックは、各種のデバイスのうちのいずれかに多様な解像度で表示されるように作られるであろうから、ページは、その表現についての有益な構成体ではないかもしれない。代わりに、アプリケーションは、（章とその子オブジェクトについてのストリームインデックスを用いて）章の中のコンテンツを識別し、次いで、表示の制約に従ってそのコンテンツを表示するであろう。
【００７０】
図１１では、図示するように、プロセス１１００は、目標ノードのレベルの仕様を（１１０５で）受け取ることによって始まる。図１２の場合、この目標は、タイトルノードである。アプリケーションは、タイトルを検索するためにアプリケーションの中で提示された選択肢を（例えば、検索ボックスのタイトル選択肢を選択することによって）ユーザが選択した場合に、目標の仕様を受け取ってもよいだろう。より一般的には、ユーザによる直接の指示、または、文脈から得られるヒントから、目標のレベルが識別されてもよい。例によって示すように、検索されるオブジェクトの仕様は、構造の階層の中のオブジェクトのレベルだけでなく、順序付けの中のその場所（例えば、この場合、そのレベルの第１の兄弟）も含んでいてよい。また、プロセスは（１１１０において）、目標ノードの記述も受け取る。一部の実施形態では、この記述は、ユーザが見つけたいテキスト（例えば「第２章のタイトル」）であってもよい。例えば、ユーザが具体的なテキストを検索ボックスに入力し、次いで、「検索」というユーザインタフェース項目を押してもよいだろう。
【００７１】
次いで、プロセス１１００は、（１１１５において）仕様に合致するオブジェクトツリーのノードからインデックス範囲を取り出す。一部の実施形態では、プロセスは、そのような第１のノードを見つける目的でツリーを通過する。上記のように、これらの仕様は、求められているオブジェクトの階層レベルだけでなく（例えば、そのオブジェクトは、指定されたレベルにおける第１の兄であるという）追加の記述子も含んでいてよいだろう。例えば、図１２の場合、取り出される第１のノードは、パラグラフレベルの第１のノードであって第１の兄であることから、第１章のタイトルのノードである１２１５であるだろう。次いで、プロセスは（１１２０において）、取り出されたインデックス範囲を用いてストリームからコンテンツを取り出す。すなわち、プロセスは、識別されたノードによって指定されたインデックスにおいて、ストリームからコンテンツを取り出す。この場合、取り出されたコンテンツは、第１章のタイトルである。
【００７２】
プロセスは、ストリームから取り出されたコンテンツが、１１１０において受け取られた目標の記述と合致するかどうか（１１２５において）判定する。一部の実施形態では、取り出されたコンテンツの文字値を、所望のコンテンツの文字値と比較して、それら２つが合致しているかどうか判定する。図１２の例では、第１章のタイトルは、（当然ながら、第１章と第２章とが同じタイトルを持つのでない限り）検索されたコンテンツと合致しないであろう。
【００７３】
２つの文字値が合致しない場合、プロセスは、（１１３０において）仕様に合致するオブジェクトツリーの別のノードから別のインデックス範囲を取り出し、次いで１１２０に戻る。このように、プロセスは、オブジェクトツリーを用いて、ユーザによって指示された仕様に合致するオブジェクトだけのコンテンツを、順番に、迅速に検索する。例示する状況においては、プロセスは、第２章オブジェクトの第１の子（ノード１２２０）へと移動して、第２章のタイトルについてのインデックス範囲を取り出すであろう。この場合、プロセスは、検索されたタイトルの用語と、第２章の章のタイトルとの間の合致を見つけるであろう。
【００７４】
合致が見つかった場合、プロセスは、（１１３５において）目標ノードの位置を報告する。次いで、アプリケーションは、識別された目標オブジェクトを用いて、必要ならどのような動作であろうと実行することができる。章のタイトルを検索する例では、アプリケーションは、一般に、単にタイトルを表示する以上のことをしようとするであろう。アプリケーションは、第２章全体のインデックス範囲を用いてストリームにアクセスし、ユーザによって選択されたフォントサイズとスタイルとを所与として、電子ブックの表示エリアに適合する最大の取り出されたコンテンツを表示してもよい。その他の実施形態（例えば、他の用途についての）は、識別された目標ノードの両側に（例えば、目標ノードのコンテンツをディスプレイの中央において）コンテンツを表示し、場合によっては、ディスプレイの中で目標自体を強調表示するであろう。加えて、一部の実施形態は、非表示機能、例えば、目標オブジェクトのコンテンツを仮想クリップボードにコピーすることや、目標オブジェクトを参照するマーカを記憶すること等を行ってもよい。
【００７５】
Ｃ．形式変換
文書処理アプリケーションが、ペーストボード（クリップボードと呼ばれることが多い）に選択をコピーする場合、あるいはその他のやり方で文書の一部分を別のアプリケーションに渡す場合、両方のアプリケーションによって理解される共通形式に文書を変換する必要があることが多い。例えば、ＰＤＦ文書に対する意味再構成によって、（例えば、上での参照により本願に援用する米国特許公開公報第２０１０／０１７４９８５号の中に記述されているように）そのタスクのために作られたオブジェクトツリーが生成されるであろうが、選択をペーストボードにコピーする場合、選択は、各種の他のアプリケーションがその情報を確実に使用できるようにするため、ＨＴＭＬ、ＲＴＦおよび／またはプレーンテキストに変換される。ユーザが選択した形式への文書のエクスポートは、変換するために選択するのが文書全体であるような、この変換手順の特殊な場合にすぎない。
【００７６】
複数の表現のデータモデルの一部の実施形態では、選択は、開始インデックスによって順序付けられた、コンテンツストリームへの一連の重ならないインデックス範囲として表される。選択は、テキスト検索またはその他のクエリの結果であるかもしれないし、（例えば、上記のセクションＩ．Ａで述べたように）ユーザが画面上の領域を指示した結果であるかもしれない。選択を別の形式に変換するには、選択に参加しているノードを識別し、それらを適切な順序で通過し、各ノードについて適切な出力を追加することが必要である。ノードの変換は、一般にそのタイプに依存しており、最初の出力が含まれていて、続いてその選択に含まれているその子たちの変換が行われ、続いて最後の出力が行われてもよい。
【００７７】
図１３は、２つの表現のデータモデルを用いて文書の一部分の選択を別の形式に変換するためのプロセス１３００を概念的に示す図である。図１３は、図１４乃至図１５に示す例を参照することによって記述しよう。図１４は、例示的な文書ページ１４００における選択を示す図である。図１５は、文書ページ１４００についての例示的なオブジェクトツリー１５１０を示す図である。オブジェクトツリー１５１０は、ページレベルのルートノード１５２０と、パラグラフレベルの子ノード１５３０−１５３２と、単語レベルの孫ノード１５４１−１５４８とを含んでいる。上記のように、多様な実施形態において、文書構造オブジェクトツリーの多様なレベルのノード（例えば、欄ノード、テキスト行ノード等）が用いられる。
【００７８】
また、図１５には、オブジェクトツリー１５１０を用いて変換プロセスによって作られた新たな形式で、例示的な出力ストリーム１５５０を示す。出力ストリーム１５５０は、オブジェクトツリー１５１０の各ノードに対応するセクション１５５１−１５６３を含んでいる。選択範囲１４０５は、コンテンツストリームの中のインデックス１８５−４６８をカバーしており、それらは、オブジェクトツリー１５１０の中の強調表示されたノード（ノード１５２０、１５３０、１５３２、１５３４、および１５４３−１５４７）によって参照される。選択範囲と重なる各ノードによって、１つ以上のデータセクションが、出力ストリーム１５５０に追加される（例えば、ノード１５３２によって、セクション１５５５および１５５８が、出力ストリームに追加される）。
【００７９】
図示するように、図１３のプロセス１３００が、（１３０１において）文書の一部分の選択と、その選択が変換される必要があるという指示（例えば、ユーザによって入力されたコピー操作や、文書をエクスポートする命令等）とを受け取った時点で、開始される。図１４の例に示すように、ユーザが、文書ページ１４００の選択１４０５（強調表示された部分）を、第１パラグラフの最後の単語「ｃｏｍｐｔｏｒｙ」から第３パラグラフの２番目の単語「ｓｔｒｕｌｅ」まで選択し、この選択を（例えば、キーボードの「Ｃｔｒｌ−Ｃ」または「Ｃｍｄ−Ｃ」、メニュー選択等を使って）コピーした。また、選択は、ユーザが文書をエクスポートすることを選ぶ場合、文書全体であってもよいだろう。加えて、各種のその他の操作によって、文書の一部分または全部の変換が行われることもあるだろう。
【００８０】
一部の実施形態では、そのような選択は、重なり合わない一連の選択範囲Ｒ１、Ｒ２、…ＲＫとして表され、この場合、いかなるＲｉの範囲もコンテンツストリーム内のＲｉ＋１の範囲の前にある。一度の選択には、選択が離れている場合（例えば、選択が、特定の句を含むパラグラフを求める検索結果の集合である場合）、複数の重なり合わない選択範囲が含まれていることがある。これらの選択範囲は、選択を含んでいる文書についてのオブジェクトツリーの各ノードに記憶されているインデックスの範囲との比較に用いられる。比較はそれぞれ、現選択範囲Ｒｉと現ノードＮとの間で行われる。一部の実施形態では、現選択範囲Ｒｉへのポインタと、オブジェクトツリーの中の現ノードＮへのポインタとを、プロセス１３００の動作全体を通して、維持して更新する。
【００８１】
次に、プロセス１３００は、（１３０２において）オブジェクトツリーのルートノードを現ノードＮとする。図１５に示す例では、オブジェクトツリー１５１０の中のノード１５１５は、ルートノードである。このノードは、文書ページ全体１４００をカバーするインデックス範囲を保持している。プロセス１３００は、（１３０４において）一連の選択範囲の中の第１の選択範囲Ｒ１を現選択範囲とする。
【００８２】
ルートノードを現ノードとし、そして、第１の選択範囲を現選択範囲とした後、プロセスは、（１３０６において）一連の選択範囲を新たな形式に変換する。一部の実施形態では、この操作は、最初にルートノードを現ノードとし、そして、第１の選択範囲を現選択範囲として開始した後、データモデルのオブジェクトツリーの各ノードを再帰的に通過する。変換が完了した後、プロセス１３００は終了する。図１６ａ−１６ｂは、そのような再帰的な変換動作を行う一部の実施形態の例示的なプロセス１６００を概念的に示す図である。一部の実施形態では、プロセス１６００は、プロセス１３００の動作１３０６で行われてもよい。また、図１６ａ−１６ｂは、図１４−１５に示す例を参照しながら記述しよう。
【００８３】
プロセス１６００は、一連の選択範囲を変換するためにオブジェクトツリーの各ノードを再帰的に通過する再帰的プロセスである。プロセス１６００は、プロセス１６００自体を実行する操作を含んでいるため、再帰的である。プロセス１６００は、（例えば、操作１３００のような操作によって、あるいは、プロセス１６００の現インスタンスを再帰的に呼び出す、プロセス１６００の以前のインスタンスによって）以前に設定されていた現ノードおよび現選択範囲を継承する。また、プロセス１６００は、そのプロセスの以前のインスタンスから保存された値またはポインタ、例えば、保存されたノードあるいは変換プロセスの完了を示すフラグも継承する。
【００８４】
プロセス１６００は、（１６１０において）現選択範囲を現ノードの範囲と比較することによって開始される。現在選択されているノードの中のインデックス範囲が、現選択範囲と重なる（すなわち、現在選択されているノードによって参照されるコンテンツが、現選択範囲の中の選択されたコンテンツの一部である）場合には、プロセス１６００は１６１２へと進み、新たな形式での出力にデータが追加される。現在の選択ノードＮの中のインデックス範囲が、現選択範囲Ｒｉと重ならない場合、プロセス１６００は１６２０へと進む。
【００８５】
１６２０では、プロセスは、現選択範囲Ｒｉは現ノードＮの中に記憶されたインデックス範囲の前なのかどうかを判定する。選択範囲のシーケンスＲ１、…ＲＮは昇順に配置されているのだから、プロセスは、シーケンス内の次の選択範囲Ｒｉ＋１に行き、選択範囲と現ノードとの間の重なりを探すであろう。しかし、現選択範囲が、現ノードのインデックス範囲の後にある場合には、プロセスは、選択範囲との重なりを探すためにオブジェクトツリーの中の次のノードを待たなければならない。現選択範囲Ｒｉが現ノードＮの中の範囲の前にある場合、プロセス１６００は、次の選択範囲Ｒｉ＋１へ移動するために１６３０へと進む。現選択範囲Ｒｉが、現ノードの範囲の前にない（すなわち、現選択範囲が、現ノードの範囲の後にある）場合には、プロセスは、戻って、以前のレベルの再帰操作を再開する。
【００８６】
１６３０において、プロセスは、現選択範囲Ｒｉは最後の選択範囲ＲＫなのかどうかを判定する。一部の実施形態では、現選択範囲へのポインタを調べて、これが最後の範囲を指し示しているかどうかを判定することによって、この判定を行う。現選択範囲がシーケンス内の最後の選択範囲である場合には、プロセスは、現ノードが、すべての選択範囲を追ってコンテンツを参照するところまでオブジェクトツリーを通過してきたのだから、選択範囲は完全に変換されたことになる。この判定の確実性は、上記のセクションＩで記述した、オブジェクトツリーに課された順序付けおよび完全性の条件によって可能となる。この場合、プロセス１６００は１６３５まで進み、選択範囲の変換が完了したことを報告する。他方、現選択範囲が最後の選択範囲ではない場合、プロセスは１６４０へと進む。
【００８７】
プロセスが、すべての選択範囲を変換した時、プロセスは、選択範囲の変換が完了したことを（１６３５において）報告する。一部の実施形態では、これは、「完了」フラグを設定することによって達成される。このフラグが設定されると、プロセス１６００は、選択全体が変換されたことと、オブジェクトツリー内のいかなるノードもこれ以上通過する必要がないこととを理解する。選択範囲の変換が完了したことを報告した後、プロセスは、戻って、以前のレベルの再帰操作を再開する（すなわち、プロセス１６００の各種のインスタンスが終了工程を始めることができる）。
【００８８】
さらに変換されるべき選択範囲が残っている場合、プロセスは（１６４０において）次の選択範囲Ｒｉ＋１を現選択範囲とする。一部の実施形態では、これは、現選択範囲のポイントを更新して、ＲｉではなくＲｉ＋１を参照することによって達成される。現選択範囲を更新した後、プロセスは、新たな現選択範囲が、現ノードの中の範囲と重なるかどうかを判定するために、１６１０へと進む。
【００８９】
プロセス１６００は、現選択範囲が現ノードによって参照される範囲と確かに重なると判定すると、プロセスは（１６１２において）新たな形式（すなわち、選択が変換されている形式）に従って出力ストリームに最初の出力を追加する。この最初の出力は、プロセスが、現ノードの子孫ノードへと通過する前に出力ストリームに追加するデータである。一部の実施形態では、この最初の出力は、ノードのタイプに合った所望の出力形式によって決められる。例えば、新たな形式では、すべてのパラグラフの先頭にタブ文字が含まれることが必要である場合には、選択範囲と重なるパラグラフレベルのノードは、出力ストリームにタブ文字を追加しなければならないだろう。多くの場合、最初の出力は、タグを含むであろう。例えば、出力がＨＴＭＬである場合には、各パラグラフは、パラグラフを開始するためのＨＴＭＬタグ（すなわち、「＜ｐ＞」および設定される必要があるパラグラフのいずれかの属性）を使って開始されるであろう。図１５に示す例では、パラグラフがタブ文字を使って開始されることを必要とする形式の場合にプロセス１６００がパラグラフレベルのノード１５３２に最初に出会った時、プロセス１６００は、出力ストリーム１５５０にタブ文字をセクション１５５５の一部として追加するであろう。
【００９０】
最初の出力を追加した後、プロセスは、（１６１４において）現ノードを保存する。プロセス１６００は、オブジェクトツリーの中の現ノードの子孫ノードを再帰的に通過するプロセスであるため、一部の実施形態では、（例えば、現ノードへのポインタを、後入先出スタックデータ構造へと「プッシュ」することによって）現ノードを保存し、従って、現ノードを、その子孫ノードの通過が完了した後、復元することができる。現ノードを保存した後、プロセスは１６５０へと進む。
【００９１】
プロセスは、次いで、（１６５０において）現ノードが子ノードを有するかどうかを判定する。一部の実施形態では、子ノードを有しないノードは、ツリー構造の中の葉ノードである。現ノードが、子ノードを有しない葉ノードである場合、プロセスは１６５５へと進み、その葉ノードに関連するコンテンツを取り出して出力する。他方、現ノードが、少なくとも１つの子ノードを有する場合、プロセスは１６６０へと進み、現ノードの各子ノードを通過する。
【００９２】
次に、プロセスは、（１６５７において）現ノードに関連するコンテンツを、文書についての順序付けられたコンテンツストリームから取り出す。一部の実施形態では、プロセスは、現ノードの中に記憶されたインデックスを用いて、対応するデータをストリーム表現から取り出す。図１５の例では、プロセスは、単語レベルの葉ノード１５４５の中に記憶されたインデックス範囲４５１−４５８を用いて、文書ページ１４００のストリーム表現から「ｔｗｉｇｈｔ」という単語を取り出す。ストリーム表現からコンテンツを取り出した後、プロセスは、１６５７へと進む。
【００９３】
次いでプロセスは、ストリーム表現から取り出されたコンテンツを（１６５７において）出力ストリームに追加する。図１５の例では、プロセスは、取り出された「ｔｗｉｇｈｔ」という単語を、１６５７において出力ストリームに追加する。一部の実施形態では、プロセス１６００は、この取り出されたコンテンツを、（１６１２で追加される）ノードについての最初の出力の後に、かつ、（１６８０で追加される）ノードについての最後の出力の前に、出力ストリームに追加する。子ノードのない葉だけのノードが操作１６５０および１６５７を行うのだから、プロセス１６００は、ストリーム表現からコンテンツを取り出して、葉ノードについての出力ストリームだけにコンテンツを追加する。コンテンツを出力ストリームに追加した後、プロセスは１６８０へと進む。
【００９４】
一部の実施形態では、プロセスは、葉ノードと葉以外のノードとの両方についてコンテンツをストリーム表現から取り出す。葉以外のノードについて出力を生成する過程で、一部の実施形態では、葉以外のノードの子ノードのインデックス範囲間にすき間があるかどうかを判定する。上記のセクションＩで論じたように、一部の実施形態では、親ノードのインデックス範囲は、その各子ノードの範囲の和集合に等しくなければならない（すなわち、各子ノードのインデックス範囲の中にはすき間が存在しない）という厳密な規則が適用される。しかし、他の実施形態では、この条件は、親ノードのインデックス範囲は、単にその子ノードの範囲の和集合を含んでいるのであって、各子ノード間にはインデックス範囲の中にすき間が存在してもよいというように緩和される。一部のそのような実施形態では、プロセス１６００は、コンテンツが（例えば１６５５または１６５７において）取り出された前のインデックス範囲と次のノードとの間にすき間があるかどうか、そして、このすき間は、（変換されるべきコンテンツの中のすき間とは対照的に）親ノードの範囲内のすき間なのかどうかを判定する。そのようなすき間が存在する場合には、プロセスは、コンテンツストリームからのすき間のインデックス範囲に対応するコンテンツを取り出して、取り出されたコンテンツを出力ストリームに追加する。
【００９５】
コンテンツを出力ストリームに追加する場合、ストリーム表現から取り出されたコンテンツを出力ストリームに直接追加する代わりに、一部の実施形態では、指定された出力形式に従って、追加のコンテンツを追加するかたまはコンテンツを変換する。例えば、以前にセクションＩＩで論じたようなスタイルツリーを含んでいる一部の実施形態では、プロセスは、出力ストリームに追加することになるコンテンツを、スタイルツリーの各ノードに従って変換する。一部のこのような実施形態では、プロセスは、現ノードの範囲と交差するスタイルツリーの中のノードを見つけて、そのスタイルを、これらの重なり合うスタイルツリーノードの中で指定された範囲に従って、現ノードのコンテンツに適用する。親ノードの中のインデックス範囲が子ノードの中のインデックス範囲の和集合であるような一部の実施形態では、プロセスは、スタイルツリーの中のすべての葉ノードを検討して、追加することになるコンテンツのスタイルを判定する。葉ノードがインデックス範囲全体を包含することはなく、代わりに、以前にセクションＩＩで論じたようにインデックス範囲間に「すき間」を残すようなその他の一部の実施形態では、プロセスは、スタイルツリーの中の親ノードのスタイルを検討することによって、「すき間」に入るコンテンツのスタイルを推定する。
【００９６】
現ノードの少なくとも１つの子ノードが存在する場合、プロセスは、（１６５０において）現ノードの第１の子ノードを、新たな現ノードとして設定する。第１の子ノードは、その兄弟のインデックス範囲のうちの最小範囲を含む子ノードである。一部の実施形態では、各子ノードは、開始インデックスによって順序付けられるアレイとして配置され、第１の子ノードは、アレイの中の第１のノードとして識別することができる。一部の実施形態では、プロセスは、第１の子ノードを指し示すように現ノードのポインタを更新する。
【００９７】
次に、プロセス１６００は、（１６７０において）或る子ノードを、その子ノード（すなわち、新たな現ノード）についても同じ選択変換プロセスを再帰的に実行することによって通過して、１６１０へと進む。これは、プロセス１６００の新たなレベルの再帰操作を開始する再帰呼び出しである（本質的に、プロセス１６００のインスタンス化を再始動することであり、それが完了すると、プロセスの現在のインスタンス化（すなわち１６７２）へ戻るであろう）。この新たなレベルの再帰的操作は、子ノードについて選択変換プロセスが完了した後、現在のレベルで操作１６７２へ戻るであろう。当業者であれば理解するであろうが、新たに呼び出されるプロセスは、通過される子ノードがそれ自身の子ノードを有する場合、別のレベルのプロセスを呼び出すことがあり、そしてまた、これらの各子ノードも、別のレベルのプロセスを呼び出すことがあり、選択範囲にある現ノードの各葉ノードを通過してしまわない限り、以下同様である。
【００９８】
プロセス１６００の特定のインスタンス化が、（再帰呼び出しから子ノードを通過するインスタンス化へ）戻る場合、プロセスは、（１６７２において）選択範囲の変換が完了したかどうか判定する。上述のように、プロセス１６００は、選択が完全に変換された場合に完了する。最後の選択範囲が変換された後、プロセス１６００は、これらのインスタンスの中に、選択の変換は完了したためプロセスは別の子ノードをこれ以上通過しないということを示すための指標を（例えば、１６３５において「完了」フラグを設定することによって）記憶する。選択範囲の変換が完了する（すなわち、「完了」フラグが設定される）と、プロセスは１６８０へ進む。そうでない場合、プロセスは１６７４へ進む。
【００９９】
選択範囲が完全に変換されていない場合、プロセスは（１６７４において）現ノードの下で通過されるべき追加の子ノードがあるかどうかを判定する。一部の実施形態では、プロセスは、現ノードのポインタが、最後の子ノード（例えば、子ノードのアレイの中の最後のノード）を現時点で参照している時、通過すべき子ノードがもう存在しないと判定する。現ノードのすべての子ノードを通過したら、プロセスは１６８０へと進む。
【０１００】
他方、通過すべき追加の子ノードが残っている場合、プロセスは、（１６７６において）次の子ノードを現ノードとして設定する。前記のように、一部の実施形態では、一組の兄弟ノード（例えば、現ノードの各子ノード）をアレイの中に配置して、次の子ノードが、アレイの中の次のノードとして識別されうるようにする。次の子ノードを現ノードとして更新すると、プロセスは、１６７０へと進み、同じ選択変換プロセスを再帰的に実行することによって、次の子ノードを通過する。
【０１０１】
プロセス１６００は、選択範囲の変換は完了したかまたは通過することになる子ノードはこれ以上存在しないという指標を受け取ると、プロセス１６００は、（１６８０において）所望の新たな形式に従って出力ストリームに最後の出力を追加する。この最後の出力は、現ノードの子孫ノードがすべて通過された後に（または、選択範囲が完全に変換された時に）現ノードについての出力ストリームに追加されることになるデータである。一部の実施形態では、この最後の出力は、ノードのタイプに合った所望の出力形式によって決められる。例えば、新たな形式では、すべてのパラグラフの終わりに復帰改行が含まれることが必要である場合には、選択範囲と重なるパラグラフレベルのノードは、出力ストリームに復帰改行文字を追加する必要があるであろう。図１５に示す例では、プロセス１６００が、復帰改行文字を使ってパラグラフが終了することを必要とする形式について、パラグラフレベルのノード１５３２のすべての子孫ノードを通過し終えた場合、プロセス１６００は、出力ストリーム１５５０に復帰改行文字をセクション１５５８の一部として追加するであろう。
【０１０２】
次に、プロセスは、（１６９０において）直近に保存したノードを（例えば、後入先出スタックデータ構造から保存されたポインタを「ポップすること」によって）現ノードとして復元する。現ノードを以前に保存されたノードに復元した後、プロセスは、戻って、以前のレベルの再帰操作を再開する。この以前のレベルの再帰操作とは、新たな現ノード（スタックからポップされたばかりのノード）が現ノードであって、そこから現在のレベルの再帰操作が呼び出された、インスタンスであろう。
【０１０３】
方々に、プロセス１６００は、戻って、以前のレベルの再帰操作を再開すると記述されている。一部の実施形態では、プロセス１６００は、再帰操作の直後に行われる操作へ進むことによって、以前のレベルの再帰操作を再開する。例えば、操作１６７０は、プロセス１６００を再帰的に実行する操作である。操作１６７０が完了した時点で、プロセス１６００は、次の操作１６７２を再開する。操作１６００が、図１３の１３０６から始められた場合には、以前のレベルの再帰操作とは、プロセス１３００のことであり、これは１３０６の後で終了する。
【０１０４】
プロセス１３００および１６００についての記述は、あるストリーム上のオブジェクトモデルからのデータの選択を、新たなストリーム（例えば、ＨＴＭＬファイル）に変換することについて記述している。一部の実施形態は、同様のプロセスを用いて、文字ストリーム上の１つのオブジェクトモデルと、同じストリーム上の別のオブジェクトモデルとの間の変換を行う。一部の実施形態では、そのような変換プロセスは、最初の出力と最後の出力とを用いて、ツリーの各ノードを（例えば、ＸＭＬで）定義する。最初の出力と最後の出力との間に文字ストリームからのコンテンツを追加するのではなく、（最初のオブジェクトモデルと同じ範囲の集合か、あるいは異なる範囲の集合かのいずれかの）範囲を、新たなオブジェクトモデルの各ノードの中に記憶される情報として用いてもよい。
【０１０５】
一部の実施形態は、ＸＳＬＴプログラミング言語を用いて、そのような変換を行うが、それは、どのようなオブジェクトモデルのペアの間の変換であろうと、この言語ならほぼ可能だからである。例えば、前述の変換プロセスの変形形態を用いて、テーブルに関するクエリを（例えば、所与の基準に従って順序付けをやり直した行をテーブルに提示して）行うこともできるだろう。第２の例として、オブジェクトツリーを選んで、そのツリーをグラフィックス（例えば、ＳＶＧオブジェクトツリー）に変換することがあげられよう。
【０１０６】
ＩＶ．電子システム
上記の特徴および応用例の多くは、コンピュータ可読記憶媒体（コンピュータ可読媒体とも言う）上に記録された一組の命令として指定された、ソフトウェアプロセスとして実装される。これらの命令が、１つ以上の演算ユニットまたは処理ユニット（例えば、１つ以上のプロセッサ、プロセッサのコア、または他の処理ユニット）によって実行された場合、それらは、命令の中に指示された動作を処理ユニットに行わせる。コンピュータ可読媒体の例には、ＣＤ−ＲＯＭ、フラッシュドライブ、ＲＡＭ（Ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）チップ、ハードドライブ、ＥＰＲＯＭ（ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｉｅｓ）、ＥＥＰＲＯＭ（ｅｌｅｃｔｒｉｃａｌｌｙ  ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｉｅｓ）等が含まれるが、それらに限定されない。コンピュータ可読媒体には、搬送波と、無線で通過するかまたは有線接続を介した電子信号とは含まれない。
【０１０７】
本明細書では、「ソフトウェア」という用語は、プロセッサによって処理されるためにメモリに読み込まれうる、磁気記憶装置の中に記憶された読取専用メモリまたはアプリケーションの中に常駐するファームウェアを含むことが意図されている。また、一部の実施形態では、複数のソフトウェア発明が、別個のソフトウェア発明のままでありながら、より大きなプログラムの下位区分として実行されてもよい。また、一部の実施形態では、複数のソフトウェア発明が、別々のプログラムとして実装されてもよい。最後に、本明細書に記述したソフトウェア発明を一緒になって実装するような別個のプログラムのいずれかの組み合わせは、本発明の範囲内にある。一部の実施形態では、ソフトウェアプログラムは、１つ以上の電子システム上で動作するようにインストールされた場合、ソフトウェアプログラムの動作を実行する１つ以上の特定のマシン実装を定義する。
【０１０８】
図１７は、本発明の一部の実施形態が実装される電子システム１７００を概念的に示す図である。電子システム１７００は、コンピュータ（例えば、デスクトップコンピュータ、パーソナルコンピュータ、タブレットコンピュータ等）、電話、ＰＤＡ，あるいはいずれかの他の種類の電子デバイスであってもよい。そのような電子システムは、各種のコンピュータ可読媒体、および、各種の他のタイプのコンピュータ可読媒体用のインタフェースを含んでいる。電子システム１７００は、バス１７０５と、処理ユニット１７１０と、グラフィックス処理ユニット（ＧＰＵ）１７１５と、システムメモリ１７２０と、ネットワーク１７２５と、読取専用メモリ１７３０と、永久記憶デバイス１７３５と、入力デバイス１７４０と、出力デバイス１７４５とを含んでいる。
【０１０９】
バス１７０５は、電子システム１７００の多数の内部デバイスを通信で接続するすべてのシステムバス、周辺バス、およびチップセットバスを集合的に表している。例えば、バス１７０５は、処理ユニット１７１０を、読取専用メモリ１７３０、ＧＰＵ１７１５、システムメモリ１７２０、および永久記憶デバイス１７３５に通信で接続している。
【０１１０】
これらの各種のメモリユニットから、処理ユニット１７１０は、本発明のプロセスを実行するために、実行すべき命令と処理すべきデータとを取り出す。処理ユニットは、シングルプロセッサであってもよいし、異なる実施形態においてはマルチコアプロセッサであってもよい。一部の命令は、ＧＰＵ１７１５へ渡されて、ＧＰＵ１７１５によって実行される。ＧＰＵ１７１５は、各種の演算をオフロードすることや、処理ユニット１７１０によって提供される画像処理を補完することができる。一部の実施形態では、そのような機能性を、ＣｏｒｅＩｍａｇｅのカーネルシェーディング言語を用いて提供することができる。
【０１１１】
読取専用メモリ（ＲＯＭ）１７３０は、処理ユニット１７１０および電子システムの他のモジュールが必要とする静的データおよび命令を記憶している。他方、永久記憶デバイス１７３５は、読取書込メモリデバイスである。このデバイスは、電子システム１７００が停止している時でも命令およびデータを記憶している不揮発性メモリユニットである。本発明の一部の実施形態は、大容量記憶デバイス（例えば、磁気ディスクや光ディスク、およびそれに対応するディスクドライブ）を永久記憶デバイス１７３５として用いる。
【０１１２】
他の実施形態は、取り外し可能記憶デバイス（例えばフロッピィディスク、フラッシュメモリデバイス等およびそれに対応するドライブ）を永久記憶デバイスとして用いる。永久記憶デバイス１７３５と同様に、システムメモリ１７２０は読取書込メモリデバイスである。しかし、永久記憶デバイス１７３５とは異なり、システムメモリ１７２０は、ランダムアクセスメモリのような、揮発性の読取書込メモリである。システムメモリ１７２０は、プロセッサがランタイム時に必要とする一部の命令とデータとを記憶している。一部の実施形態では、本発明のプロセスは、システムメモリ１７２０、永久記憶デバイス１７３５、および／または読取専用メモリ１７３０の中に記憶される。例えば、各種のメモリユニットは、一部の実施形態に従ってマルチメディアクリップを処理するための命令を含んでいる。これらの各種のメモリユニットから、処理ユニット１７１０は、一部の実施形態のプロセスを実行するために、実行するための命令と処理するためのデータとを取り出す。
【０１１３】
また、バス１７０５は、入力デバイス１７４０と出力デバイス１７４５とを接続する。入力デバイス１７４０は、ユーザが電子システムと情報通信を行って、コマンドを選択できるようにする。入力デバイス１７４０には、英数字キーボードとポインタデバイス（「カーソル制御デバイス」とも言う）と、カメラ（例えばｗｅｂｃａｍｓ）と、音声コマンドを受け取るためのマイクロフォンまたは同様のデバイス等が含まれる。出力デバイス１７４５は、電子システムによって生成される画像または他のやり方で出力されるデータを表示する。出力デバイス１７４５には、プリンタおよび表示デバイス、例えば、ＣＲＴ（ｃａｔｈｏｄｅ  ｒａｙ  ｔｕｂｅ）またはＬＣＤ（ｌｉｑｕｉｄ  ｃｒｙｓｔａｌ  ｄｉｓｐｌａｙ）、および、スピーカまたは同様の音声出力デバイスが含まれる。一部の実施形態は、例えば、入力デバイスと出力デバイスとの両方として機能するタッチスクリーンのようなデバイスを備えている。
【０１１４】
最後に、図１７に示すように、バス１７０５は、ネットワークアダプタ（図示せず）を介して電子システム１７００をネットワーク１７２５に接続する。このように、コンピュータは、コンピュータネットワーク（例えば、ローカルエリアネットワーク（「ＬＡＮ」）、ワイドエリアネットワーク（「ＷＡＮ」）、イントラネット、あるいは、ネットワークのネットワーク、例えばインターネット）の一部であってもよい。電子システム１７００のいずれかの、またはすべてのコンポーネントが、本発明に関連して用いられてもよい。
【０１１５】
一部の実施形態は、電子コンポーネント、例えば、マイクロプロセッサや、機械可読媒体すなわちコンピュータ可読媒体（あるいは、コンピュータ可読記憶媒体、機械可読媒体、あるいは機械可読記憶媒体とも呼ばれる）の中にコンピュータプログラム命令を記憶する記憶装置およびメモリを含んでいる。そのようなコンピュータ可読媒体の一部の例には、ＲＡＭ、ＲＯＭ、読取専用コンパクトディスク（ＣＤ−ＲＯＭ）、追記型コンパクトディスク（ＣＤ−Ｒ）、書換可能コンパクトディスク（ＣＤ−ＲＷ）、読取専用デジタル多用途ディスク（例えば、ＤＶＤ−ＲＯＭ、デュアルレイヤＤＶＤ−ＲＯＭ）、各種の追記型／書換可能ＤＶＤ（例えば、ＤＶＤ−ＲＡＭ、ＤＶＤ−ＲＷ、ＤＶＤ＋ＲＷ等）、フラッシュメモリ（例えば、ＳＤカード、ミニＳＤカード、マイクロＳＤカード等）、磁気および／または固体ハードドライブ、読取専用および追記型Ｂｌｕ−Ｒａｙ（登録商標）ディスク、ウルトラデンシティーオプティカルディスク、その他のいずれかの光または磁気媒体、およびフロッピィディスクが含まれる。コンピュータ可読媒体は、少なくとも１つの処理ユニットによって実行可能であって、各種の操作を行うための命令の集合を含んでいるようなコンピュータプログラムを記憶していてもよい。コンピュータプログラムまたはコンピュータコードの例には、例えばコンパイラによって生成されるようなマシンコードと、コンピュータ、電子コンポーネントまたはマイクロプロセッサによってインタープリタを用いて実行される上位レベルコードを含むファイルとが含まれる。
【０１１６】
上記の議論は主として、ソフトウェアを実行するマイクロプロセッサまたはマルチコアプロセッサについて触れているが、一部の実施形態は、例えば、ＡＳＩＣ（特定用途向け集積回路）またはＦＰＧＡ（フィールド・プログラマブル・ゲート・アレイ）のような、１つ以上の集積回路によって行われる。一部の実施形態では、そのような集積回路は、回路自体に記憶されている命令を実行する。加えて、一部の実施形態は、ＰＬＤ（ｐｒｏｇｒａｍｍａｂｌｅ  ｌｏｇｉｃ  ｄｅｖｉｃｅｓ：プログラム可能論理回路）、ＲＯＭデバイスまたはＲＡＭデバイスの中に記憶されているソフトウェアを実行する。
【０１１７】
本明細書および本願のいずれかの請求項では、「コンピュータ」、「サーバ」、「プロセッサ」および「メモリ」という用語はすべて、電子デバイスまたはその他の技術的デバイスのことを言う。これらの用語は、人間または人間のグループを除外する。本明細書では、「表示（ｄｉｓｐｌａｙ）」または「表示する（ｄｉｓｐｌａｙｉｎｇ）」という用語は、電子デバイス上に表示することを意味する。本明細書および本願のいずれかの請求項では、「コンピュータ可読媒体」、「コンピュータ可読媒体（複数）」および「マシン可読媒体」という用語は、コンピュータによって読み取られうる形で情報を記憶している有形の物理的物体に完全に限定される。これらの用語は、いずれかの無線信号、有線のダウンロード信号、およびいずれかの他の一過性の信号を除外する。
【０１１８】
本発明について、多数の具体的詳細を参照しながら記述してきたが、本発明は、本発明の精神から逸脱することなくその他の特定の形態で実施されうることを、当業者であれば理解するであろう。加えて、（図１１、１３、１６を含めて）多くの図が、プロセスを概念的に示している。これらのプロセスの特定の操作は、図示および記述する正確な順序で行われないことがある。特定の操作が、１つの連続的な操作としては行われないことがあり、別の実施形態では、別の特定の操作が行われることがある。さらに、プロセスは、複数のサブプロセスを用いて、あるいは、より大きなマクロプロセスの一部として実装することもできるだろう。従って、当業者であれば理解するであろうが、本発明は、前述の例示的な詳細によって限定されるのではなく、添付の請求項によって定義されるべきである。
【図１】
0005612227.tif 000002
【図２】
0005612227.tif 000003
【図３】
0005612227.tif 000004
【図４】
0005612227.tif 000005
【図５】
0005612227.tif 000006
【図６】
0005612227.tif 000007
【図７】
0005612227.tif 000008
【図８】
0005612227.tif 000009
【図９】
0005612227.tif 000010
【図１０】
0005612227.tif 000011
【図１１】
0005612227.tif 000012
【図１２】
0005612227.tif 000013
【図１３】
0005612227.tif 000014
【図１４】
0005612227.tif 000015
【図１５】
0005612227.tif 000016
【図１６ａ】
0005612227.tif 000017
【図１６ｂ】
0005612227.tif 000018
【図１７】
0005612227.tif 000019