(57)【特許請求の範囲】
【請求項１】
コンピュータの処理により、ウェプ・ページをブラウザで閲覧する際のロード時間を減少させるようにウェプ・ページを再構成する方法であって、
前記コンピュータの記憶装置に保存されたウェブ・ページのページ、ファイル及びコンポーネント間の依存関係を抽出するステップと、
ネットワーク遅延値、転送効率値、及びコンポーネントサイズを測定するステップと、
前記ネットワーク遅延値、前記転送効率値、前記依存関係及び前記コンポーネントサイズの情報を用いて、ファイル候補のロード時間を推定するステップと、
前記ウェブ・ページを解析して、依存関係、包含関係、及び読み込み関係を、0-1の表として作成することにより、前記ウェプ・ページのロード時間をあらわす目的関数を最小にする整数計画問題を生成するステップと、
前記整数計画問題をソルバに解かせるステップと、
前記ソルバから得られた解から、ライブラリ・ファイルを再構成して作成するステップと、
各ページのライブラリ・ファイルへのリンクを、新しくできたライブラリ・ファイルへのリンクに書き換えることにより、再構成されたウェブ・ページを得るステップを有する、
方法。
【請求項２】
前記抽出された依存関係の組み合わせを用いて、同質のコンポーネントを連結するステップを更に有する、請求項１に記載の方法。
【請求項３】
前記ファイルが前記コンポーネントを含む包含関係に情報を用いて、前記整数計画問題が一次整数計画問題になるように前記ファイルを結合するステップをさらに有する、請求項１に記載の方法。
【請求項４】
連続してアクセスされるページの集合を決定するステップをさらに有する、請求項１に記載の方法。
【請求項５】
同じファイルのコストを一回だけ加算するというブラウザ・キャッシュの効果を整数計画問題の制約条件に加える、請求項４に記載の方法。
【請求項６】
前記ソルバが、線形計画問題を解くことで緩和解を見つけてファイル候補をみつけるステップと、みつけたファイル候補を加えて整数計画問題を解くステップを有する、請求項１に記載の方法。
【請求項７】
コンピュータの処理により、ウェプ・ページをブラウザで閲覧する際のロード時間を減少させるようにウェプ・ページを再構成するプログラムであって、
前記コンピュータに、
前記コンピュータの記憶装置に保存されたウェブ・ページのページ、ファイル及びコンポーネント間の依存関係を抽出するステップと、
ネットワーク遅延値、転送効率値、及びコンポーネントサイズを測定するステップと、
前記ネットワーク遅延値、前記転送効率値、前記依存関係及び前記コンポーネントサイズの情報を用いて、ファイル候補のロード時間を推定するステップと、
前記ウェブ・ページを解析して、依存関係、包含関係、及び読み込み関係を、0-1の表として作成することにより、前記ウェプ・ページのロード時間をあらわす目的関数を最小にする整数計画問題を生成するステップと、
前記整数計画問題をソルバに解かせるステップと、
前記ソルバから得られた解から、ライブラリ・ファイルを再構成して作成するステップと、
各ページのライブラリ・ファイルへのリンクを、新しくできたライブラリ・ファイルへのリンクに書き換えることにより、再構成されたウェブ・ページを得るステップを実行させる、
プログラム。
【請求項８】
前記抽出された依存関係の組み合わせを用いて、同質のコンポーネントを連結するステップを更に有する、請求項７に記載のプログラム。
【請求項９】
前記ファイルが前記コンポーネントを含む包含関係に情報を用いて、前記整数計画問題が一次整数計画問題になるように前記ファイルを結合するステップをさらに有する、請求項７に記載のプログラム。
【請求項１０】
連続してアクセスされるページの集合を決定するステップをさらに有する、請求項７に記載のプログラム。
【請求項１１】
同じファイルのコストを一回だけ加算するというブラウザ・キャッシュの効果を整数計画問題の制約条件に加える、請求項１０に記載のプログラム。
【請求項１２】
前記ソルバが、線形計画問題を解くことで緩和解を見つけてファイル候補をみつけるステップと、みつけたファイル候補を加えて整数計画問題を解くステップを有する、請求項７に記載のプログラム。
【請求項１３】
コンピュータの処理により、ウェプ・ページをブラウザで閲覧する際のロード時間を減少させるようにウェプ・ページを再構成するシステムであって、
ウェブ・ページのページ、ファイル及びコンポーネントを記憶する記憶装置と、
前記記憶装置に保存されたウェブ・ページのページ、ファイル及びコンポーネント間の依存関係を抽出する手段と、
ネットワーク遅延値、転送効率値、及びコンポーネントサイズを測定する手段と、
前記ネットワーク遅延値、前記転送効率値、前記依存関係及び前記コンポーネントサイズの情報を用いて、ファイル候補のロード時間を推定する手段と、
前記ウェブ・ページを解析して、依存関係、包含関係、及び読み込み関係を、0-1の表として作成することにより、前記ウェプ・ページのロード時間をあらわす目的関数を最小にする整数計画問題を生成する手段と、
前記整数計画問題を解く機能をもつソルバと、
前記ソルバから得られた解から、ライブラリ・ファイルを再構成して作成する手段と、
各ページのライブラリ・ファイルへのリンクを、新しくできたライブラリ・ファイルへのリンクに書き換えることにより、再構成されたウェブ・ページを得る手段を有する、
システム。
【請求項１４】
前記抽出された依存関係の組み合わせを用いて、同質のコンポーネントを連結する手段を更に有する、請求項１３に記載のシステム。
【請求項１５】
前記ファイルが前記コンポーネントを含む包含関係に情報を用いて、前記整数計画問題が一次整数計画問題になるように前記ファイルを結合する手段をさらに有する、請求項１３に記載のシステム。
【請求項１６】
連続してアクセスされるページの集合を決定する手段をさらに有する、請求項１３に記載のシステム。
【請求項１７】
同じファイルのコストを一回だけ加算するというブラウザ・キャッシュの効果を整数計画問題の制約条件に加える、請求項１６に記載のシステム。
【請求項１８】
前記ソルバが、線形計画問題を解くことで緩和解を見つけてファイル候補をみつける機能と、みつけたファイル候補を加えて整数計画問題を解くを有する、請求項１３に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、インターネットのブラウザで閲覧されるウェブ・ページを作成するための技法に関し、より詳しくは、閲覧される際のロード時間を短縮する技法に関する。
【背景技術】
【０００２】
インターネット上で閲覧されるウェブ・ページは、情報発信手段、広告手段、あるいは情報収集手段として、極めて一般的に使われているが、最近になって、単に閲覧するだけではなく、JavaScript(R)を使った動的機能を含む多くのページや画像を駆使した、高度な機能をもつ複雑なウェブ・ページが現れてきている。
【０００３】
このような複雑で多くのコンテンツを含むウェブ・ページは、ブラウザでトップ・ページをロードするのに時間がかかる。ある統計によると、ユーザーは、ページのロードに８秒以上かかると、そのページから立ち去るという。
【０００４】
そこで、ページのロード時間を短縮するために従来行われている試みとして、実行時に動的に必要なファイルをクラアイントに要求させ、サーバ側で結合して転送する技術が知られている。この技術は、各クライアントで個別に最適化させるという利点があるが、ウェブ・ページを作成する際に特殊な作法に従わなくてはならないということと、実行時にサーバ側にオーバーヘッドが生じるという問題点がある。
【０００５】
他の従来の技法として、ページでロードされるファイルを事前に結合しておくことがあるが、全部を結合するとか、特定のページに関連するファイルだけを結合する等の粗い最適化しかできないという問題がある。
【０００６】
図１は、応答時間を改善するために、複数のファイルを１つに結合する単純な処理の従来技術の例を示している。すなわち、ＨＴＭＬファイル１０２が、JavaScript(R)のファイル１０４、１０６及び１０８を参照している場合に、既存のツールを使って、ファイル１０４、１０６及び１０８をファイル１１０に結合し、ＨＴＭＬファイル１１２を、結合したファイル１１０を参照するように変更することによって、応答時間が改善される。このような機能をもつ既存のツールとして、Dojo custom build、Scriptalizerなどが知られている。
【０００７】
図２は、各ページにフォーカスした応答時間改善の例を示す。図２において、クライアント１は、ＨＴＭＬファイル２０２と、ＨＴＭＬファイル２０６を順次ブラウズし、それに伴って、JavaScript(R)を含むファイル２０４とファイル２０８が順次ロードされる。
【０００８】
一方、クライアント２は、必要な function C()とfunction D()だけを含むファイルをダウンロードすればよいので、高速である。
【０００９】
この場合、クライアント１はもともと、ＨＴＭＬファイル２０２だけをブラウズする意図なので、function D()は無駄にロードしたことになる。また、function C()が、ファイル２０４とファイル２０６の両方に含まれているので、ソースコードの管理が複雑になる。例えば、ファイル２０４におけるfunction C()を変更したら、ファイル２０６におけるfunction C()も併せて変更しなくてはならない、等である。
【００１０】
図３は、ＨＴＭＬファイル３０２にフォーカスした応答時間改善の例を示す。図３において、クライアント１は、ＨＴＭＬファイル３０２と、ＨＴＭＫファイル３０６を順次ブラウズし、それに伴って、JavaScript(R)を含むファイル３０４とファイル３０８が順次ロードされる。
【００１１】
一方、クライアント２は、クライアント１がロードしてキャッシュされたファイル３０６を利用するが、ＨＴＭＬファイル３０６から、不要なfunction A()とB()もダウンロードしてしまう。
【００１２】
図４は、アクセスをバランスさせた例を示す。この例では、ＨＴＭＬファイル４０２がファイル４０４とファイル４０８を参照し、ＨＴＭＬファイル４０６がファイル４０８とファイル４１０を参照する。ＨＴＭＬファイル４０２は頻繁にアクセスされ、一方、ＨＴＭＬファイル４０６は中程度にアクセスされる。function C()は、ファイル４０８に含まれていなくてはならない。
【００１３】
このようなアプローチをとることで、ページ間のアクセスをバランスさせ、ロードする速度を改善することができる。
【００１４】
しかし、図５に示すような、実際のウェブ・アプリケーションのページの場合は、多数のページをもち、そのうちのあるものはJavaScript(R)を含み、あるページのJavaScript(R)結合を最適化すると、他のページの性能低下につながることがある。
【００１５】
すると、上記のような応答改善策のアプローチを採ろうとすると、ＨＴＭＬファイル、JavaScript(R)ファイル、及びJavaScript(R)関数の間の指数関数的組み合わせを考慮しなくてはならなくなり、計算量的に許容できなくなる。
【００１６】
そこで、次のような従来技術が知られている。先ず、特開２００１−３４５２７号公報は、フレーム配置とコンテンツの組合せパターンを複数記述して１つのファイルとして定義したフレーム管理シートを、初期表示情報としてＷＷＷブラウザで保持し、フレーム表示定義ファイルを読み込み、それに記述されているコンテンツを表示し、操作者によりコンテンツの変更要求があったときには、フレーム管理シートを参照することで、変更要求の場合に配置が同じフレームがあるか否かを判別し、配置を変更するコンテンツのみをＷＷＷサーバに要求し、ＷＷＷサーバから変更するコンテンツを受取ったならば、変更後のコンテンツを表示するようにすることにより、変更後の画面表示を高速化することを開示する。
【００１７】
特開２００１−３５６９５７号公報は、画面上への情報表示を行うブラウザ手段と、その情報表示のために必要なページデータを記憶しておくサーバ手段と、記憶されたページデータの一部を保持して前記ブラウザ手段による情報表示を高速化させるキャッシュ手段とを備えた情報表示端末装置において、外部装置からの前記サーバ手段内のページデータの更新にあたって、更新後のデータ内容を前記外部装置から前記キャッシュ手段内に直接書き込むようにすることを開示する。
【００１８】
特開２００２−２２２１６５号公報は、表示領域内に複数の画像を含むＨＴＭＬ文書の表示（閲覧）において、表示可能領域（閲覧領域）に含まれる画像を、ＨＴＭＬ文書内における配列順（出現順）等に関係なく、他の画像よりも優先して受信して高速に表示出力することで、画像表示を伴うＨＴＭＬ文書の表示を高速化し、画像表示の待ち時間を短縮して閲覧の操作性を向上させることを開示する。
【００１９】
特開２００９−１１０２１６号公報は、頻繁に閲覧するＵＲＬは重要度を高くしてＵＲＬ重要度テーブルに指定しておけば、指定したＵＲＬの重要度に対応して画面キャッシュ優先度テーブルの優先度を変化させると共に、描画データを描画データのキャッシュメモリに格納する。Ｗｅｂブラウザの実行の際に、クライアント装置は、頻繁に閲覧する優先度の高いＵＲＬの描画データについては描画データのキャッシュメモリから読み出して表示することを開示する。
【００２０】
特開２０１０−１７０１８号公報は、データ蓄積装置とネットワークを介して接続され、データ蓄積装置に蓄積された表示対象データを表示するブラウザ機能手段３０を備えたデータ表示装置において、ユーザが要求する表示対象のデータをブラウザ機能手段内のブラウザキャッシュ判定部がブラウザキャッシュエリア内に格納の有無を判定し、無のとき、データ蓄積装置内のアプリケーションサーバから取得することでデータ表示の高速化を図ることを開示する。
【００２１】
しかし、上記どの従来技術も、ブラウザにおけるページの表示速度向上には何ほどか貢献するものの、多くのページ、スクリプト、関数、画像などを含む複雑なウェブ・ページの応答時間改善に適用しようとすると、組み合わせ爆発が生じて処理が困難になる。
【先行技術文献】
【特許文献】
【００２２】
【特許文献１】特開２００１−３４５２７号公報
【特許文献２】特開２００１−３５６９５７号公報
【特許文献３】特開２００２−２２２１６５号公報
【特許文献４】特開２００９−１１０２１６号公報
【特許文献５】特開２０１０−１７０１８号公報
【発明の概要】
【発明が解決しようとする課題】
【００２３】
従って、本発明の目的は、多数のページや、スクリプト、関数、画像などを含む複雑なウェブ・ページにも適用可能な応答時間改善技法を提供することにある。
【課題を解決するための手段】
【００２４】
本発明は、大量のページと大量のファイルの関係を考慮して、ウェブ・ページを閲覧する際の応答時間を改善するようにウェブ・ページを構成する技法を提供するものである。ここで、ページとは典型的には、クライアントがアクセスするウェブ単位であり、一般的に、いくつかのコンポーネントに依存する。ページはまた、従属するコンポーネントを使用するために、いくつかのファイルを含む。ここで、コンポーネントとは、ウェブ・コンテンツの単位であり、例えば、JavaScript(R)の関数、JavaScript(R)コードの集まり、ｃｓｓ行の集まり、画像などである。また、ファイルとは典型的には、JavaScript(R)ファイル、ｃｓｓファイル、ｃｓｓスプライト(複数の画像をひとつの画像に格納し、ＨＴＭＬの側で領域を切り出して表示する技術）などである。
【００２５】
本発明に従う処理プログラムはまず、応答時間を改善しようとするウェブ・ページのページ・コンポーネント間の依存関係を抽出する。
【００２６】
次のステップは、ネットワーク遅延値、転送効率値、ページサイズ、コンポーネントサイズを測定することである。この処理も、原則として、処理プログラムが自動的に行う。
【００２７】
次のステップは、ページ遷移パターンとその優先度、各ページの応答時間の上限値を設定することである。この処理は、原則として、ウェブ・ページの応答時間改善処理を行うオペレータによって行われる。
【００２８】
次のステップは、処理プログラムが、抽出された依存関係の組み合わせを用いて、同質のコンポーネントを連結することである。このとき、連結したコンポーネントを、新しくコンポーネントとみなして、コンポーネント・サイズなどの情報を更新する。
【００２９】
次のステップは、処理プログラムが、探索するファイルの候補を生成することである。そして、処理プログラムは、生成されたファイル候補の推定ロード時間を算出する。
【００３０】
次のステップでは、処理プログラムが、整数計画問題を生成する。具体的には、ウェブ・ページを解析して、依存関係(depend)、包含関係(include)を、0-1の表として作成する。また、読み込み関係(x)を0-1の表として作成する。
【００３１】
その際、整数計画問題には、「ページiが読み込むいくつかのファイルは、依存関係のあるコンポーネントを全てページiに提供しなくてはならない」という制約条件を用いる。そうして、ページとファイルのダウンロード時間の和を最小化するように整数計画問題を定式化し、ソルバに解かせる。
【００３２】
処理プログラムは、得られた解から、ライブラリ・ファイルを再構成して作成する。そして、各ページのライブラリ・ファイルへのリンクを、新しくできたライブラリ・ファイルへのリンクに書き換える。
【発明の効果】
【００３３】
本発明によれば、ウェブ・ページの応答時間改善が、整数計画問題に帰着されて、複雑なウェブ・ページでも、合理的な計算量で、応答時間を改善するように再構成することが可能となる。
【図面の簡単な説明】
【００３４】
【図１】従来における応答時間改善の例を示す図である。
【図２】可能な応答時間改善技術の例を示す図である。
【図３】可能な応答時間改善技術の例を示す図である。
【図４】可能な応答時間改善技術の例を示す図である。
【図５】実際のウェブ・アプリケーションの複雑さを模式的に示す図である。
【図６】本発明を実施するためのハードウェアの一例のブロック図である。
【図７】本発明を実施するための一例の機能論理ブロック図である。
【図８】ページ／ファイル／コンポーネントの結合関係を整数計画問題として記述する図である。
【図９】ブラウザ・キャッシュの効果を説明するための図である。
【図１０】クライアント／ページ／ファイルの結合関係を示す図である。
【図１１】２次計画から１次計画への変換を説明するための図である。
【図１２】依存関係の組み合わせを用いて、同質のコンポーネントを連結し、コンポーネントの数を減らす様子を示す図である。
【図１３】ページ遷移、依存関係、投機的ロードを許容するかどうかの値から探索するファイルの候補を生成する様子を示す図である。
【図１４】ページ遷移、依存関係、投機的ロードを許容するかどうかの値から探索するファイルの候補を生成する様子を示す図である。
【図１５】典型的なクライアントとその重要度を用い、特定の遷移パターンを優先することを説明するための図である。
【図１６】整数計画問題を緩和した線形計画問題を解く処理のフローチャートを示す図である。
【図１７】本発明の全体の処理の概要フローチャートを示す図である。
【図１８】ネットワーク遅延値を格納する処理のフローチャートを示す図である。
【図１９】転送効率値を格納する処理のフローチャートを示す図である。
【図２０】ページサイズを double[] page_size に格納する処理のフローチャートを示す図である。
【図２１】コンポーネントサイズを double[] component_size に格納する処理のフローチャートを示す図である。
【図２２】依存関係を抽出し、int[][] depend に格納する処理のフローチャートを示す図である。
【図２３】ページ遷移をint[][] access に格納する処理のフローチャートを示す図である。
【図２４】ページ遷移の優先度を double[] priority に格納する処理のフローチャートを示す図である。
【図２５】ページがほかのページの先読みを受け入れるかどうかを  double[] receptor に格納する処理のフローチャートを示す図である。
【図２６】応答時間の上限値を double[] upper_time に格納する処理のフローチャートを示す図である。
【図２７】依存関係の組み合わせを用いて、同質のコンポーネントを連結し、コンポーネントの数を減らす処理のフローチャートを示す図である。
【図２８】依存関係の組み合わせを用いて、同質のコンポーネントを連結し、コンポーネントの数を減らす処理のフローチャートを示す図である。
【図２９】依存関係の組み合わせを用いて、同質のコンポーネントを連結し、コンポーネントの数を減らす処理の様子を示す模式図である。
【図３０】探索するファイルの候補を生成し、int[][] includeに格納する処理のフローチャートを示す図である。
【図３１】探索するファイルの候補を生成し、int[][] includeに格納する処理のフローチャートを示す図である。
【図３２】生成されたファイル候補のロード時間を推定し、double[] file_costに格納する処理のフローチャートを示す図である。
【図３３】ソルバの入力と出力を模式的に示す図である。
【図３４】出力x*からライブラリ・ファイルを再構成して作成する処理のフローチャートを示す図である。
【図３５】出力x*からライブラリ・ファイルを再構成して作成する処理を模式的に示す図である。
【図３６】ページのライブラリファイルへのリンクを、新しくできたライブラリファイルのリンクに書き換える処理のフローチャートを示す図である。
【図３７】ページのライブラリファイルへのリンクを、新しくできたライブラリファイルのリンクに書き換える処理を模式的に示す図である。
【発明を実施するための形態】
【００３５】
以下、図面に従って、本発明の実施例を説明する。これらの実施例は、本発明の好適な態様を説明するためのものであり、発明の範囲をここで示すものに限定する意図はないことを理解されたい。また、以下の図を通して、特に断わらない限り、同一符号は、同一の対象を指すものとする。
【００３６】
図６を参照すると、本発明の一実施例に係るシステム構成及び処理を実現するためのコンピュータ・ハードウェアのブロック図が示されている。図６において、システム・バス６０２には、ＣＰＵ６０４と、主記憶（ＲＡＭ）６０６と、ハードディスク・ドライブ（ＨＤＤ）６０８と、キーボード１６０と、マウス６１２と、ディスプレイ６１４が接続されている。ＣＰＵ６０４は、好適には、３２ビットまたは６４ビットのアーキテクチャに基づくものであり、例えば、インテル社のPentium(商標)4、インテル社のCore(商標) 2 DUO、AMD社のAthlon(商標)などを使用することができる。主記憶６０６は、好適には、１ＧＢ以上の容量、より好ましくは、２ＧＢ以上の容量をもつものである。
【００３７】
ハードディスク・ドライブ６０８には、オペレーティング・システムが、格納されている。オペレーティング・システムは、Linux（商標）、マイクロソフト社のWindows(商標) 7、Windows XP(商標)、Windows(商標)2003サーバ、アップルコンピュータのMac OS(商標)などの、ＣＰＵ６０４に適合する任意のものでよい。
【００３８】
ハードディスク・ドライブ６０８にはまた、Apacheなどの、Ｗｅｂサーバとしてシステムを動作させるためのプログラムが保存され、システムの起動時に、主記憶６０６にロードされる。
【００３９】
ハードディスク・ドライブ６０８にはさらに、ブラウザで閲覧する際の応答時間を改善することを意図するウェブ・ページとその関連コンテンツが保存されている。ここで、ウェブ・ページとは典型的には、クライアントがアクセスするウェブ単位であり、一般的に、いくつかのコンポーネントに依存する。ページはまた、従属するコンポーネントを使用するために、いくつかのファイルを含む。ここで、コンポーネントとは、ウェブ・コンテンツの単位であり、例えば、JavaScript(R)の関数、JavaScript(R)コードの集まり、ｃｓｓ行の集まり、画像などである。また、ファイルとは典型的には、JavaScript(R)ファイル、ｃｓｓファイル、ｃｓｓスプライトなどである。
【００４０】
さらにハードディスク・ドライブ６０８には、ウェブ・ページの依存関係を抽出するためのモジュール、コンポーネントを連結するためのモジュール、ファイル探索モジュール、整数計画問題生成モジュール、整数計画ソルバなどが含まれている。これらのモジュールは、オペレーティング・システムの働きで適宜、主記憶６０６にロードされて、ＣＰＵ６０４などの働きにより実行される。これらのモジュールについては、図７を参照してより詳細に説明する。
【００４１】
キーボード６１０及びマウス６１２は、オペレーティング・システムが提供するグラフィック・ユーザ・インターフェースに従い、ディスプレイ６１４に表示されたアイコン、タスクバー、ウインドウなどのグラフィック・オブジェクトを操作するために使用される。
【００４２】
ディスプレイ６１４は、これには限定されないが、好適には、１０２４×７６８以上の解像度をもち、３２ビットtrue colorのＬＣＤモニタである。
【００４３】
通信インターフェース６１６は、好適には、イーサネット(R)プロトコルにより、ネットワークと接続されている。通信インターフェース６１６は、クライアント・コンピュータ（図示しない）からApacheが提供する機能により、ＴＣＰ／ＩＰなどの通信プロトコルに従い、処理リクエストを受け取り、あるいは処理結果を、クライアント・コンピュータ（図示しない）に返す。
【００４４】
次に、図７を参照して、本発明に関連して、ハードディスク・ドライブ６０８に保存されたファイル及び機能モジュールの働きを説明する。コンテンツ７０２は、応答時間を改善することを意図するウェブ・ページのコンテンツ、すなわち前述したページ、ファイル及びコンポーネントの集まりを含む。
【００４５】
依存関係抽出モジュール７０４は、コンテンツ７０２のページ及びファイルを読み取って、それらの間の依存関係を抽出する。ここでいう依存関係とは、<a href="xyz/abc.html">〜</a>のようなリンクや、<script src="xyz/abc.js" type="text/javascript"></script>、<img src="xyz/abc.gif">のような呼び出しを通じて、そのファイル内のコンテンツをページ内で利用している関係を指す。例えば、後述する、コンポーネントがJavascript関数、ファイルがJavascriptファイルの場合の例におけるサンプルのＨＴＭＬファイルは、ファイルtest03.jsを通じて、コンポーネント function012(a,b,c)に依存している。
【００４６】
コンポーネント連結モジュール７０６は、依存関係抽出モジュール７０４から得た情報に基づき、コンテンツ７０２に含まれているコンポーネントを連結し、後で使うために中間ファイル７０８として、ハードディスク・ドライブ６０８に書き出す。コンポーネント連結モジュールについては、後で説明する。
【００４７】
パラメータ設定モジュール７１０は、オペレータに、好適にはディスプレイ６１４にパネルを表示して、ページ遷移パターンとその優先度及び、各パターンの応答時間の上限値を設定させる機能をもつ。
【００４８】
探索ファイル候補生成モジュール７１２は、適宜、パラメータ設定モジュール７１０の設定情報を参照しつつ、コンテンツ７０２及び中間ファイル７０８を参照して、探索ファイル候補を生成し、後で使うために中間ファイル７０８として、ハードディスク・ドライブ６０８に書き出す。探索ファイルについても、後で説明する。
【００４９】
測定モジュール７１４は、必要に応じて通信インターフェース６１６を利用して、ネットワーク遅延値、転送効率値、ページサイズ、コンポーネント・サイズを測定する。
【００５０】
推定ロード時間算出モジュール７１６は、測定モジュール７１４の測定結果を利用し、場合によってパラメータ設定モジュール７１０の設計内容も参照して、推定ロード時間を算出する。算出した結果は、主記憶６０６に格納してもよいし、一旦ハードディスク・ドライブ６０８に保存してもよい。
【００５１】
整数計画問題生成モジュール７１８は、推定ロード時間算出モジュール７１６の出力結果に基づき、整数計画問題の式を生成する。生成される整数計画問題の具体的な式については、後述する。
【００５２】
ソルバ７２０は、整数計画問題生成モジュール７１８によって生成された整数計画問題の式を解く。
【００５３】
再構成モジュール７２２は、ソルバ７２０の出力結果を利用して、元のコンテンツ７０２及び中間ファイル７０８に基づき、更新されたコンテンツ７２４を生成する。この更新されたコンテンツ７２４は、コンテンツ７０２に対して、クライアントのコンピュータのブラウザでブラウズする際に、ロード時間が最適化されたウェブ・ページとなっている。
【００５４】
次に、本発明で利用されるいくつかの特徴を順次説明する。先ず最初の特徴は、最適化問題に変換し、最適化問題のソルバに解かせることである。すなわち、既存のツールを使う場合、図８(a)に示すように、どのページをどのコンポーネントに結合すればよいか、開発者に自明ではない。あるいは、開発者は、すべてのコンポーネントを１つのページに結合しようとする。
【００５５】
一方、本発明に従う工夫が、図８(b)に示されている。すなわち、図示されているように、選択可能な部分にすべて、最適化変数(x,y)を用いてモデルや式を作成し、それらの変数に0-1を代入することによって、読み込むかどうかを設定する。さらに、x,yによって変化するコスト関数を用いて、ページ遷移に必要な時間を定義し、その関数が最小になるようなx,yを導出する。
【００５６】
次の工夫は、ブラウザキャッシュの効果の導入である。特に工夫をしないと、図９(a)に示すように、コスト関数（応答時間の総和）に、同じファイルのコストが複数回、加算される。その点を工夫したのが図９(a)に示すやり方で、すなわち、ブラウザキャッシュの効果により、同じファイルのコストを１回だけ加算する。これにより、重複加算が避けられる。
【００５７】
この方法の難しいところは、ORの計算を要することである。ところが、0-1の整数計画問題は、ORの計算を表現できない。そこで解決策として、典型的なクライアントを導入し、連続してアクセスされるページの集合を定義し、変数Yを以下のように定義する。
・Y = 1:ページ遷移全体で、一回以上ファイルを読み込む
・Y = 0:ページ遷移全体で、一回もファイルを読み込まない
【００５８】
そこで、変数YをORとして機能させるために、以下の二つの制約式を導入する。
【数１】
0005511609.tif 000002
ここで、Kはクラアイントの数、Lはページの数、Mはファイルの数である。
また、access(k,l)は、クラアイントkがページlにアクセスするとき1、そうでないなら0である。
【００５９】
上記数式で、上の方の式は、access() * xの中に1があったら、yは1以上でなくてはならない。式の例で示すと、以下のとおりである。
Y (c1, file2) >= 1/3( access(c1, page1) * x(page1, file2) 
+access(c1, page2) * x(page2, file2)
+access(c1, page3) * x(page3, file2))
>= 1/3 (1 + 1 + 0)
>= 2/3  つまり、Yは0-1変数なので1にならなければならない。
【００６０】
一方、下の式で、すべて0だったとき、Ｙは0と1のどちらでも良いことになる（上の式）が、これを0に限定する
Y (c1, file3) <= 1/3( access(c1, page1) * x(page1, file3) 
+access(c1, page2) * x(page2, file3)
+access(c1, page3) * x(page3, file3)) + 1 - 1/3
<= 1/3 (0 + 0 + 0) + 2/3
<= 2/3 つまり、Yは0-1変数なので0にならなければならない。
【００６１】
次の工夫は、整数計画問題において、２次計画から１次計画に簡易化することである。すなわち、素朴に整数計画問題を組み立てると、ページがファイルを含む(include)かどうかのX、ファイルがコンポーネントを含む(include)かどうかのYを用いて、コスト関数は、定数*X*Yの和の形となり、２次計画問題となる。その様子を図１１(a)に示す。それだと、計算時間が大きい。
【００６２】
そこで、ファイルからコンポーネントへのincludeを定数とし、その代わり、図１１(b)に示すように、全ての組み合わせのファイルを用意する。このとき、N個のコンポーネントなら、ファイルの数は、2N - 1個となる。これにより、ページがファイルをincludeするかどうかのXだけで問題を表現可能となる。
【００６３】
尚、ここでのファイルの結合は、具体的には、次のようにして行われる。コンポーネントがJavascript関数、ファイルがJavascriptファイルの場合を例に説明する。
<html>
<head>
<script src="test01.js" type="text/javascript"></script>
<script src="test02.js" type="text/javascript"></script>
</head>
<body>
<script src="test03.js" type="text/javascript">
function012(a, b, c);
</script>
</body>
</html>
そこで、test01.jsは以下のようであり、
function function011(a, b, c) {
….
}
function function012(a, b, c) {
….
}
test02.jsは、以下のようであり、
function function021(a, b, c) {
….
}
test03.jsは、以下のようであったとする。
function function031(a, b, c) {
….
}
【００６４】
するとまず、test01.js, test02.js, test03.jsがマージされて、以下のopt01.jsが作成される。
function function011(a, b, c) {
….
}
function function012(a, b, c) {
….
}
function function021(a, b, c) {
….
}
function function031(a, b, c) {
….
}
【００６５】
そして、このopt01.jsを以って、ＨＴＭＬファイルは、以下のように最適化される。
<html>
<head>
<script src=“opt01.js" type="text/javascript"></script>
<script src=“opt01.js" type="text/javascript"></script>
</head>
<body>
<script src=“opt01.js" type="text/javascript">
function012(a, b, c);
</script>
</body>
</html>
【００６６】
次の工夫は、依存関係の組み合わせを用いて、同質のコンポーネントを連結し、コンポーネントの数を減らすことである。すなわち、コンポーネントの数が減れば、探索するファイルの数が少なくて済む。このとき利用されるのは、同じページの組み合わせから呼ばれているコンポーネントは、どのような最適化結果になろうとも、必ず同じファイルに含まれる結果になるという知見である。この知見を活かし、図１２(a)に示すように、同じページの組み合わせから呼ばれているコンポーネントは結合し、図１２(b)に示すように、結合されたコンポーネントとして再定義される。
【００６７】
次の工夫は、ページ遷移、依存関係、投機的ロードを許容するかどうかの値から探索するファイルの候補を生成することである。
【００６８】
問題意識としてあるのは、素朴にファイルの候補を考えると、2N - 1通りの候補が生成される（Nはコンポーネントの数）ということである。従って、探索するファイルの候補が減ると、計算時間が短くなる。
【００６９】
組み合わせの分類として、次のものが考えられる。すなわち：
（Ａ）ある一つのページiが利用しているX個のコンポーネントについて、2X - 1通りの組み合わせを考えれば、そのページにとって必要なコンポーネントの組み合わせはすべて用意される。
（Ｂ）ある一つのページiは利用していないが、同じページ遷移内の別のページが利用しているY個のコンポーネントを加え、2(X+Y) - 1通りの組み合わせを考えた場合、ページiに関して投機的なダウンロードを行うために必要なコンポーネントの組み合わせがすべて用意される。ページIに関して投機的なダウンロードとは、(別のページで必要になるページiにとって必要ないコンポーネントをページiであらかじめロードし、ブラウザキャッシュに格納する)。
（Ｃ）二つのページ遷移から利用されるコンポーネントのうち、どちらか片方のページ遷移からしか利用されないコンポーネント同士の組み合わせは、用意したとしても最適解にはなりえない。このことを模式的に示すのが、図１３である。また、図１４は、ページ１に着目したときの、コンポーネントの組み合わせの仕分けを示す図である。
【００７０】
次の工夫は、典型的なクライアントとその重要度を用い、特定の遷移パターンを優先することである。すなわち、使用人数が多いページやページ遷移を使用人数に比例して重点的に高速化したい、あるいは、ビジネス上重要なページやページ遷移を重点的に高速化したいという要望がある。
【００７１】
そこで、以下のような方法で典型的なページ遷移とその重要度を定義する。すなわち、先ず、ウェブコンテンツを配置し、実際の顧客に使ってもらい、アクセスログを解析し生成する。その使用人数に応じて重要度を決める。また、開発者やビジネスオーナーが典型的なページ遷移を定義する。さらには、コスト関数に、ページ遷移のコストを重要度で重み付けした加算を追加する。そのような優先順位付けの例を図１５に示す。この図に従えば、コストは次のように計算される。
コスト = 10 * cost(ページ1) + 10 * cost(ページ2) + 5 * cost(ページ2) + 5 * cost(ページ3) + 2 * cost(ページ3)
【００７２】
次の工夫は、各ページに最悪許容応答時間を設定することである。ビジネス上重要なページは、特定の秒数以上クライアントを待たせたくないという要望を満たす事は有用であるため、その要望を満たすための工夫を説明する。それは、下記のような式で表される。この式でLは、ページの数を表す。また、Mはページの数である。
【数２】
0005511609.tif 000003
この式によって、ブラウザ・キャッシュなしでアクセスしてきたときの時間を指定した数値T以下に収めるように制約をかけることができる。さらに、最悪許容応答時間を設定したいページに対してこれを行う。
【００７３】
別の工夫として、全ページ遷移における全ページに許容応答時間を設定することも可能である。ただ、このフィーチャは、根本的なところから定式化のやり直しを必要とし、実行時間が遅くなる可能性があるので、状況に応じて採用される。
【００７４】
次に、ファイル候補を減らすためのほかの工夫を説明する。一般に最適化変数xというとき、それがとり得る値によって、問題の分類が変わる。最適化変数 x のとりうる値によって問題の分類が変わる。すなわち、xが0-1変数ならば、0-1整数計画問題、実数変数ならば線形計画問題である。
【００７５】
一方で、本発明の整数計画問題は、コンポーネントの数Nに対して指数的に変数（ファイル候補）の数が増大するため、Nが大きな場合を扱うには、ファイル候補の数を抑えるための工夫が必要となる。そこで、当該フィーチャでは、適用するのが妥当な場合に、いくつかのファイル候補を用いて線形計画問題として解くことを繰り返すことで0-1整数計画問題で最適解に使用される可能性が高いと推測されるファイル候補を選び出すことを行う。
【００７６】
先ず、本発明の整数計画問題は、次のように定式化される。ここで、pkは、ページkの優先順位である。すなわち、
【数３】
0005511609.tif 000004
という式を目的関数として、下記の制約の下でソルバによって解く。
【数４】
0005511609.tif 000005
【００７７】
より詳しいアルゴリズムを、図１６のフローチャートを参照して説明する。まず、ステップ１６０２では、整数計画問題生成モジュール７１８が、少数のファイル候補を用いて整数計画問題を生成する。その整数計画問題はソルバ７２０に渡されるが、ステップ１６０４ではソルバ７２０は、渡された整数計画問題の0,1の制約を緩和し、線形計画問題として解く。
【００７８】
ここで、中間変数制約の添え字集合をNl := {n|depend(l,n) = 1}とし、双対最適解の情報を用いて、最適性を判定する。すなわち、中間変数制約の双対変数をβln(但し、n∈Nlのペアのみ用意する)とする。そこで、双対最適解をβ*lnとして、各l∈{1,...,L}に対して、
N'l := {n|β*ln - ql・r・component_size(n) > 0}において、下記の式によるチェックを行う。
【数５】
0005511609.tif 000006
但し、ここで、qlは、次のように与えられる。
【数６】
0005511609.tif 000007
ネットワーク遅延時間dは、日本国内であれば、10ms - 50msぐらいの値である。クライアントとサーバーをパケットが往復するのにかかる時間である。転送効率値rはバンド幅の逆数×8で、バンド幅が 1Mbps ならば、r= 8 / (1M)となる。
【００７９】
k∈ページlを含むパターンkとは、ページlに対してaccesskl = 1 となるようなkを全部見つけてきて、そのkを順番に選んでΣを適用するという意味である。また、pkは、図１５に示すような優先順位である。
【００８０】
ステップ１６０６で、数５において、l ∈ {1,...,L}のうち１つでもtrueとなる場合があると、最適でないとして、ステップ１６０８に進み、そこで、整数計画問題生成モジュール７１８は、緩和解を改善するファイル候補としてNを問題に加える。そして、ステップ１６０４に戻り、再度線形計画問題を解く。
【００８１】
一方、ステップ１６０６で、もし、l ∈ {1,...,L}の全てに対してこの式がfalseであると判定されると、最適として、ステップ１６１０に進み、ソルバ７２０は、得られたファイル候補を元に生成される、整数計画問題を解いて、処理を終る。
【００８２】
次に、本発明の全体の処理を、図１７以下のフローチャートを参照して説明する。図１７において、ステップ１７０２では、測定モジュール７１４が、ネットワーク遅延値をdouble d に格納する。
ステップ１７０４では、測定モジュール７１４が、転送効率値をdouble rに格納する。
ステップ１７０６では、測定モジュール７１４が、ページサイズを double[] page_size に格納する。
ステップ１７０８では、測定モジュール７１４が、コンポーネントサイズを double[] component_size に格納する。
ステップ１７１０では、依存関係抽出モジュール７０４が、依存関係を抽出し、int[][] depend に格納する。
ステップ１７１２では、依存関係抽出モジュール７０４が、ページ遷移をint[][] access に格納する。
ステップ１７１４では、依存関係抽出モジュール７０４が、ページ遷移の優先度を double[] priority に格納する。
ステップ１７１６では、依存関係抽出モジュール７０４が、ページがほかのページの先読みを受け入れるかどうかを  double[] receptor に格納する。
ステップ１７１８では、パラメータ設定モジュール７１０が、応答時間の上限値を double[] upper_time に格納する。
ステップ１７２０では、コンポーネント連結モジュール７０６が、依存関係の組み合わせを用いて、同質のコンポーネントを連結し、コンポーネントの数を減らす。
ステップ１７２２では、探索ファイル候補生成モジュール７１２が、探索するファイルの候補を生成し、int[][] includeに格納する。
ステップ１７２４では、推定ロード時間算出モジュール７１６が、生成されたファイル候補のロード時間を推定し、double[] file_costに格納する。
ステップ１７２６では、整数計画問題生成モジュール７１８が、最適化問題のソルバーに変数の数値を入力し、解x*を得る。
ステップ１７２８では、再構成モジュール７２２が、出力x*からライブラリ・ファイルを再構成して作成する。
ステップ１７３０では、再構成モジュール７２２が、ページのライブラリファイルへのリンクを、新しくできたライブラリファイルのリンクに書き換える。
【００８３】
次に、図１８のフローチャートを参照して、測定モジュール７１４が、ネットワーク遅延値をdouble dに格納する処理を説明する。すなわち、ステップ１８０２で、測定モジュール７１４は、適宜通信インターフェース６１６にアクセスしながら、ネットワーク遅延（秒）の値を取得して、変数dに格納する。
【００８４】
次に、図１９のフローチャートを参照して、測定モジュール７１４が、転送効率値をdouble rに格納する処理を説明する。すなわち、ステップ１９０２で、測定モジュール７１４は、適宜通信インターフェース６１６にアクセスしながら、バンド幅(bps)の値を取得して、その値で8を割った結果を、変数rに格納する。
【００８５】
次に、図２０のフローチャートを参照して、測定モジュール７１４が、ページサイズを double[] page_size に格納する処理を説明する。図２０において、ステップ２００２では、測定モジュール７１４は、配列page_sizeにページ数Lの長さの配列を確保する。
【００８６】
ステップ２００４からステップ２０１０までは、i = 1からLまでの、iについての繰り返しである。ステップ２００６では、測定モジュール７１４は、ページiのサイズ(byte)を計測する。ページiのサイズは、例えば、オペレーティング・システムの所定のＡＰＩ関数を呼び出して、ページのＨＴＭＬファイルのサイズを取得することで、得られる。ステップ２００８では、測定モジュール７１４は、page_size[i] = ページiのサイズとして、page_size[i]に値を格納する。この処理の結果、page_size[]に、各ページのサイズがバイト数で格納される。
【００８７】
次に、図２１のフローチャートを参照して、測定モジュール７１４が、コンポーネントサイズを double[] component_size に格納する処理を説明する。図２１において、ステップ２１０２では、測定モジュール７１４は、配列component_sizeに長さの配列を確保する。そして、ステップ２１０４で、index = 0とおく。
【００８８】
ステップ２１０６から、ステップ２１２０までは、i = 1番目のライブラリファイルから始まって、全てのライブラリファイルまでの順次の繰り返しである。
【００８９】
ステップ２１０８では、測定モジュール７１４は、ライブラリファイルiを解析し、コンポーネント単位に分割する。
【００９０】
そこで、ステップ２１１０から、ステップ２１１８までは、j = 1番目のコンポーネントから始まって、全てのコンポーネントまでの順次の繰り返しである。
【００９１】
ステップ２１１２では、測定モジュール７１４は、コンポーネントjのサイズ(byte)を計測する。ステップ２１１４では、component_size[index] = コンポーネントjのサイズ、と値を格納する。ステップ２１１６では、index = index + 1と、indexが増分される。この処理の結果、component_size[]に、各コンポーネントのサイズがバイト数で格納される。
【００９２】
次に、図２２のフローチャートを参照して、依存関係抽出モジュール７０４が、依存関係を抽出し、int[][] depend に格納する処理を説明する。。ステップ２２０２では、依存関係抽出モジュール７０４は、２次元配列dependに、ページの数L * コンポーネントの数Nの配列を確保する。
【００９３】
ステップ２２０４から、ステップ２２１８までは、ページiについて、i = 1からLまでのループである。
【００９４】
ステップ２２０６では、依存関係抽出モジュール７０４は、ページiを読み、どのコンポーネントを利用しているかを解析する。
【００９５】
ステップ２２０８からステップ２２１６までは、コンポーネントjについて、j = 1からNまでのループである。ステップ２２１０で、依存関係抽出モジュール７０４は、ページiがコンポーネントjを利用しているかどうかを判断し、もしそうなら、ステップ２２１２でdepend[i][j] = 1と置き、そうでなければ、ステップ２２１４でdepend[i][j] = 0と置く。ステップ２２０８からステップ２２１６のループがNまで終ると、ステップ２２１８に行ってjを1だけ進め、ステップ２２０４に戻る。ステップ２２０４から、ステップ２２１８のループがLを超えると、処理は終了する。この処理の結果、depend[][]に、各ページとコンポーネントの間の依存関係が格納される。
【００９６】
次に、図２３のフローチャートを参照して、依存関係抽出モジュール７０４が、ページ遷移を抽出し、int[][] accessに格納する処理を説明する。ステップ２３０２では、依存関係抽出モジュール７０４は、２次元配列accessに、ページ遷移の数K * ページの数Lの配列を確保する。
【００９７】
ステップ２３０４から、ステップ２２１６までは、ページ遷移iについて、i = 1からKまでのループである。
【００９８】
ステップ２３０６からステップ２３１４までは、ページjについて、j = 1からLまでのループである。ステップ２３０８で、依存関係抽出モジュール７０４は、ページjがページ遷移iに含まれるどうかを判断し、もしそうなら、ステップ２３１０でaccess[i][j] = 1と置き、そうでなければ、ステップ２３１２でaccess[i][j] = 0と置く。ステップ２３０４から、ステップ２２１６のループがKまで完了した結果、access[][]に、ページ遷移の情報が格納される。
【００９９】
次に、図２４のフローチャートを参照して、依存関係抽出モジュール７０４が、ページ遷移の優先度を double[] priority に格納する処理について説明する。ステップ２４０２では、依存関係抽出モジュール７０４は、配列priorityに、ページ遷移の数Kの長さの配列を確保する。
【０１００】
ステップ２４０４から、ステップ２４０８までは、ページ遷移iについて、i = 1からKまでのループである。ステップ２４０６では、依存関係抽出モジュール７０４は、priority[i]に、ページ遷移iの優先度を入力する。この処理の結果、priority[]に、ページ遷移の優先度が格納される。
【０１０１】
次に、図２５のフローチャートを参照して、依存関係抽出モジュール７０４が、ページがほかのページの先読みを受け入れるかどうかをint[] receptorに格納する処理について説明する。ステップ２５０２では、依存関係抽出モジュール７０４は、配列receptorに、ページの数Lの長さの配列を確保する。
【０１０２】
ステップ２５０４からステップ２５１２までは、ページiについて、i = 1からLまでのループである。ステップ２５０６で、依存関係抽出モジュール７０４は、ページiが先読みを受け入れるかどうかを判断し、もしそうなら、ステップ２５０８でreceptor[i] = 1と置き、そうでなければ、ステップ２５１０でreceptor[i] = 0と置く。この処理の結果、receptor[]に、ページが他のページの先読みを受け入れるかどうかの情報が格納される。
【０１０３】
次に、図２６のフローチャートを参照して、パラメータ設定モジュール７１０が、応答時間の上限値を double[] upper_time に格納する処理について説明する。ステップ２６０２では、パラメータ設定モジュール７１０は、配列upper_timeに、ページの数Lの長さの配列を確保する。
【０１０４】
ステップ２６０４から、ステップ２６０８までは、ページiについて、i = 1からLまでのループである。ステップ２６０６では、パラメータ設定モジュール７１０は、upper_time[i]に、ページiの応答時間の限界値を入力する。この処理の結果、upper_time[]に、ページの応答時間の限界値が格納される。
【０１０５】
次に、図２７及び図２８のフローチャートを参照して、コンポーネント連結モジュール７０６が、依存関係の組み合わせを用いて、同質のコンポーネントを連結し、コンポーネントの数を減らす処理について説明する。ステップ２７０２では、コンポーネント連結モジュール７０６は、長さNのフラグ配列int[] flagを確保する。
【０１０６】
コンポーネント連結モジュール７０６は、ステップ２７０４で、十分な長さのセット型変数の配列set[] Sを確保し、ステップ２７０６で、i = 1とおく。
【０１０７】
ステップ２７０８で、コンポーネント連結モジュール７０６は、S[1]に、ciからcNまでのN個を格納する。
【０１０８】
次のステップ２７１０からステップ２７３４までは、j = 1からLまでの繰り返しである。また、ステップ２７１２からステップ２７２０までは、k = 1からNまでの繰り返しである。ステップ２７１４では、コンポーネント連結モジュール７０６は、depend[j][k] == 1かどうかを判断し、もしそうなら、ステップ２７１６でflag[k] = 1と代入し、そうでないなら、ステップ２７１８でflag[k] = 1と代入する。
【０１０９】
ステップ２７１２からステップ２７２０までのループがNまで終ると、次のステップ２７２２からステップ２７３４までは、k = 1からiまでの繰り返しである。ステップ２７２４では、コンポーネント連結モジュール７０６は、S[k]内のすべてのコンポーネントの対応するフラグがiかどうか判断し、もしそうなら、単にkの次のループに進む。もしそうでないなら、コンポーネント連結モジュール７０６は、ステップ２７２６で、S[k]内のすべてのコンポーネントの対応するフラグが0かどうか判断し、もしそうなら、単にkの次のループに進む。もしそうでないなら、ステップ２７２８で、S[k]内のflag == 0のcをすべて、S[k+1]に移動する。
【０１１０】
ステップ２７２２からステップ２７３０までのループがKまで終ると、ステップ２７３２でコンポーネント連結モジュール７０６は、iを1つ増やし、ステップ２７３４でjの次のループに進む。ステップ２７１０からステップ２７３４までのループがLまで終ると、処理は、図２８のフローチャートに進む。
【０１１１】
図２８において、ステップ２８０２では、コンポーネント連結モジュール７０６は、コンポーネントサイズNに、ステップ２７２８で計算されたiを上書きする。
【０１１２】
次のステップ２８０４から２８０８までは、j = 1からNまでのループである。ステップ２８０６では、コンポーネント連結モジュール７０６は、component_size[j]に、s[j]内のコンポーネントのサイズの和を格納する。
【０１１３】
こうして、ステップ２８０４から２８０８までのループがNまで終ると、ステップ２８１０では、コンポーネント連結モジュール７０６は、２次元配列dependに、ページの数L * コンポーネントの数Nの配列を確保する。
【０１１４】
次のステップ２８１２からステップ２８２４までは、i = 1からLまでのループであり、ステップ２８１４からステップ２８２２までは、j = 1からNまでのループである。
【０１１５】
コンポーネント連結モジュール７０６は、ステップ２８１６で、ページiがS[j]内のコンポーネントを利用しているかどうか判断し、もしそうなら、ステップ２８１８でdepend[i][j] = 1とし、そうでなければ、ステップ２８２０でdepend[i][j] = 0とする。この処理を、、i = 1からLまでのループと、その内側のj = 1からNまでのループについて完了すると、この処理は終る。図２９は、図２７及び図２８の処理の様子を模式的に示す図である。
【０１１６】
次に、図３０及び図３１のフローチャートを参照して、探索ファイル候補生成モジュール７１２が、探索するファイルの候補を生成し、int[][] includeに格納する処理を説明する。
【０１１７】
ステップ３００２では、探索ファイル候補生成モジュール７１２が、集合型変数Candidatesを用意する。次のステップ３００４からステップ３０２０までは、k = 1からKまでのループである。
【０１１８】
ステップ３００６で、探索ファイル候補生成モジュール７１２は、ページ遷移k内のすべてのページのreceptorが0かどうか判断し、もしそうなら、ページ遷移kのすべてのpage_についてのループである、ステップ３００８からステップ３０１４までを実行する。
【０１１９】
ステップ３００８からステップ３０１４までの間で、探索ファイル候補生成モジュール７１２は、ステップ３０１０でpage_1が存在しているコンポーネントの数を数えて、Numに格納し、ステップ３０１２で、2Num - 1通りのすべてのコンポーネントの組み合わせをCandidatesに追加し、ステップ３０２０に行って、kを一つ進める。
【０１２０】
ページ遷移k内のすべてのページのreceptorが0ではないと判断されたなら、探索ファイル候補生成モジュール７１２は、ステップ３０１６で、ページ遷移k内のページが依存しているコンポーネントの数を数えてNumに追加し、ステップ３０１８で、2Num - 1通りのすべてのコンポーネントの組み合わせをCandidatesに追加し、ステップ３０２０に行って、kを一つ進める。
【０１２１】
こうして、ステップ３００４からステップ３０２０までのループがKまで終了すると、処理は、図３１のフローチャートに進む。探索ファイル候補生成モジュール７１２は、ステップ３０１２で、i = 0とセットして、Candidatesのすべての組み合わせについて、ステップ３１０４から３１０８までのループを実行する。すなわち、そのループには、i = i + 1を実行するステップ３１０６が含まれているので、ステップ３１０４から３１０８までのループを完了すると、iにCandidatesのすべての組み合わせの個数が格納されている。そこで、探索ファイル候補生成モジュール７１２は、ステップ３１１０で、ファイル候補の数Mにiを格納する。
【０１２２】
ステップ３１１２では、探索ファイル候補生成モジュール７１２は、長さM×Nの配列int[][] includeを確保し、ステップ３１１４で、m = 1とおく。
【０１２３】
ステップ３１１６からステップ３１３０までは、Candidatesのすべての組み合わせについてのループである。また、その内側のステップ３１１８からステップ３１２６までは、n = 1からNまでのループである。
【０１２４】
ステップ３１２０では、探索ファイル候補生成モジュール７１２は、コンポーネントnを組み合わせが含んでいるかどうかを判断し、もしそうなら、ステップ３１２２でinclude[m][n] = 1とし、そうでなければステップ３１２４でinclude[m][n] = 0とする。
【０１２５】
こうして、ステップ３１１８からステップ３１２６までのループがNまで終ると、ステップ３１２８でm = m + 1として、ステップ３１３０で、Candidatesの次の組み合わせに進む。
【０１２６】
こうして、ステップ３１１６からステップ３１３０までのループが終ると、探索するファイルの候補を生成する処理は完了となる。
【０１２７】
次に、図３２のフローチャートを参照して、推定ロード時間算出モジュール７１６が、生成されたファイル候補のロード時間を推定し、double[] file_costに格納する処理を説明する。
【０１２８】
ステップ３２０２では、推定ロード時間算出モジュール７１６は、長さMの配列double [] file_costを確保する。
【０１２９】
次のステップ３２０４からステップ３２１６までは、m = 1からMまでのループである。推定ロード時間算出モジュール７１６は、ステップ３２０６で、file_size = 0とおく。
【０１３０】
ステップ３２０８からステップ３２１２までは、n = 1からNまでのループである。そのループ内のステップ３２１０で、推定ロード時間算出モジュール７１６は、file_size += include[m][n] * component_size[n]の計算をする。
【０１３１】
ステップ３２０８からステップ３２１２までのループがNまで終ると、ステップ３２１４で、推定ロード時間算出モジュール７１６は、file_cost[m] = d + r * file_sizeを計算する。ここで、dの値は、図１８のフローチャートの処理で得られたものであり、rの値は、図１９のフローチャートの処理で得られたものである。
【０１３２】
こうして、ステップ３２０４からステップ３２１６までのループがMまで終ると、file_cost[]の値が揃っている。
【０１３３】
図３３は、今まで計算した値をソルバ７２０に入力して、最適化された値を得る様子を模式的に示す図である。これは、図１７のステップ１７２６に対応する。すなわち、d, r, receptor[], file_cost[], page_size[], component_size[], Upper_time[], include[][], access[][], priority[], x[][], y[][]. depend[][]をソルバ７２０に入力して、X*[][], Y*[][]を得る。
このとき、ソルバ７２０は、既に示した式であるが、
【数７】
0005511609.tif 000008
という式の値を最小化することを、
【数８】
0005511609.tif 000009
という制約条件で解くものである。
【０１３４】
次に、図３４のフローチャートを参照して、再構成モジュール７２２が、出力x*からライブラリ・ファイルを再構成して作成する処理について説明する。
【０１３５】
ステップ３４０２において、再構成モジュール７２２は、ステップ３４０２からステップ３４２０までのループを、l = 1からLまで実行する。
【０１３６】
ステップ３４０２からステップ３４２０までのループの内部で、再構成モジュール７２２は、ステップ３４０４からステップ３４１８までのループを、m = 1からMまで実行する。
【０１３７】
ステップ３４０４からステップ３４１８までのループの内部のステップ３４０６で、再構成モジュール７２２は、x[l][m] == 1かどうか判断する。ここで、x[][]とは、図３３で、X*と示されているものである。
【０１３８】
再構成モジュール７２２は、もしx[l][m] == 1なら、ステップ３４０６で、ファイル候補mのファイルを作成し、次に、ステップ３４１０からステップ３４１６までのループを、n = 1からNまで実行する。
【０１３９】
ステップ３４１０からステップ３４１６までのループの内部で、再構成モジュール７２２は、ステップ３４１２で、include[m][n] == 1かどうか判断し、もしそうならステップ３４１６で、ファイルにコンポーネントnを追加して、ステップ３４１６でnを1進め、そうでなければ、単にステップ３４１６でnを1進める。
【０１４０】
ステップ３４１０からステップ３４１６までのループがNまで終ると、ステップ３４１８で、mを1進める。
【０１４１】
ステップ３４０６に戻って、もしx[l][m] == 1でないなら、単にステップ３４１８で、mを1進めて、ステップ３４０４に戻る。
【０１４２】
こうして、ステップ３４０４からステップ３４１８までのループがMまで終ると、ステップ３４２０でlを1進め、ステップ３４０２に戻る。
【０１４３】
こうして、ステップ３４０２からステップ３４２０までのループがLまで終ると、処理は終る。図３５は、このような処理を模式的に示す図である。
【０１４４】
次に、図３６のフローチャートを参照して、再構成モジュール７２２が、ページのライブラリファイルへのリンクを、新しくできたライブラリファイルのリンクに書き換える処理を説明する。
【０１４５】
再構成モジュール７２２は、ステップ３６０２からステップ３６１２までのループを、l = 1からLまで実行する。
【０１４６】
ステップ３６０２からステップ３６１２までのループの内部で、再構成モジュール７２２は、ステップ３６０４からステップ３６１０までのループを、page[l]におけるライブラリファイルへのリンクすべてのそれぞれについて辿る。
【０１４７】
ステップ３６０４からステップ３６１２までのループの内部で、再構成モジュール７２２は、ステップ３６０６で、リンクしているライブラリファイルのコンポーネントの集合を包含する最小のライブラリファイルを探す。
【０１４８】
そして、ステップ３６０８で、再構成モジュール７２２は、リンクをその新しいライブラリファイルに書き換える。
【０１４９】
こうして、page[l]におけるライブラリファイルへのリンクすべてについて、ステップ３６０４からステップ３６１０までの処理を完了すると、処理はステップ３６１２に進んで、lを1つ進める。こうしてステップ３６０２に戻り、ステップ３６０４から処理が再開される。
【０１５０】
ステップ３６０２でlがLを超えた時点で、処理が完了する。図３７は、このような処理を模式的に示す図である。
【０１５１】
以上、特定の実施例に基づき、本発明を説明してきたが、本発明は、任意のコンピュータのハードウェア及びプラットフォームで実施可能であることを理解されたい。また、本発明の処理システムは、ローカルのクラアイント上にあっても、サーバ上にあっても、同様に使用することができる。
【符号の説明】
【０１５２】
６０２  システム・バス
６０４  ＣＰＵ
６０６  主記憶
６０８  ハードディスク・ドライブ
６０８  一旦ハードディスク・ドライブ
６１０  キーボード
６１２  マウス
６１４  ディスプレイ
６１６  通信インターフェース
７０２  コンテンツ
７０４  依存関係抽出モジュール
７０６  コンポーネント連結モジュール
７０８  中間ファイル
７１０  パラメータ設定モジュール
７１２  探索ファイル候補生成モジュール
７１４  測定モジュール
７１６  推定ロード時間算出モジュール
７１８  整数計画問題生成モジュール
７２０  ソルバ
７２２  再構成モジュール
７２４  コンテンツ
【図１】
0005511609.tif 000010
【図２】
0005511609.tif 000011
【図３】
0005511609.tif 000012
【図４】
0005511609.tif 000013
【図５】
0005511609.tif 000014
【図６】
0005511609.tif 000015
【図７】
0005511609.tif 000016
【図８】
0005511609.tif 000017
【図９】
0005511609.tif 000018
【図１０】
0005511609.tif 000019
【図１１】
0005511609.tif 000020
【図１２】
0005511609.tif 000021
【図１３】
0005511609.tif 000022
【図１４】
0005511609.tif 000023
【図１５】
0005511609.tif 000024
【図１６】
0005511609.tif 000025
【図１７】
0005511609.tif 000026
【図１８】
0005511609.tif 000027
【図１９】
0005511609.tif 000028
【図２０】
0005511609.tif 000029
【図２１】
0005511609.tif 000030
【図２２】
0005511609.tif 000031
【図２３】
0005511609.tif 000032
【図２４】
0005511609.tif 000033
【図２５】
0005511609.tif 000034
【図２６】
0005511609.tif 000035
【図２７】
0005511609.tif 000036
【図２８】
0005511609.tif 000037
【図２９】
0005511609.tif 000038
【図３０】
0005511609.tif 000039
【図３１】
0005511609.tif 000040
【図３２】
0005511609.tif 000041
【図３３】
0005511609.tif 000042
【図３４】
0005511609.tif 000043
【図３５】
0005511609.tif 000044
【図３６】
0005511609.tif 000045
【図３７】
0005511609.tif 000046