(57)【要約】コンテンツの旧バージョンおよびコンテンツの新バージョンの間のコンパクトな更新パッケージを生成するシステム。このシステムは、旧バージョンおよび新バージョンに関連付けられる変換子を生成する変換子生成部と、旧バージョンに変換子を適用して変更バージョンを発生する変更バージョン生成部と、コンパクトな更新パッケージを生成する更新パッケージ生成部と、を含む。コンパクトな更新パッケージは、変換子、ならびに変更バージョンおよび新バージョンに基づく変更デルタを含む。
2007521555.tif 000002
【特許請求の範囲】
【請求項１】
コンテンツの旧バージョンおよび前記コンテンツの新バージョンの間のコンパクトな更新パッケージを生成する方法であって、
（ｉ）前記旧バージョンおよび前記新バージョンに関連付けられる変換子を生成するステップと、
（ｉｉ）前記バージョンの一方に前記変換子を適用して変更バージョンを生成するステップと、
（ｉｉｉ）前記変換子、ならびに少なくとも前記変更バージョンおよび（ｉｉ）に定められた前記一方のバージョン以外の前記バージョンに基づく変更デルタを含む、前記コンパクトな更新パッケージを生成するステップと、を有する方法。
【請求項２】
前記変更デルタは、前記変更バージョンおよび前記（ｉｉ）に定められた前記一方のバージョン以外のバージョンの間にｄｉｆｆユーティリティを用いることによって得られる、請求項１記載の方法。
【請求項３】
（ｉｖ）前記コンパクトな更新パッケージを提供するステップを更に有する請求項１または請求項２記載の方法。
【請求項４】
（ｉｉ）に定められた前記一方のバージョンは、前記コンテンツの旧バージョンであり、（ｉｉｉ）に定められた前記一方のバージョン以外の前記バージョンは、前記コンテンツの新バージョンである、請求項１から請求項３のいずれかに記載の方法。
【請求項５】
（ｉｉ）に定められた前記一方のバージョンは、前記コンテンツの新バージョンであり、（ｉｉｉ）に定められた前記一方のバージョン以外の前記バージョンは、前記コンテンツの旧バージョンである、請求項１から請求項３のいずれかに記載の方法。
【請求項６】
前記変換子は、少なくとも１つのシフト規則を含む、請求項１から請求項５のいずれかに記載の方法。
【請求項７】
前記シフト規則は数値シフト規則である、請求項６記載の方法。
【請求項８】
前記数値シフト規則は整数シフト規則である、請求項７記載の方法。
【請求項９】
前記シフト規則は参照シフト規則である、請求項６から請求項８のいずれかに記載の方法。
【請求項１０】
前記少なくとも１つの参照シフト規則は差分テーブルと関連付けられる、請求項９記載の方法。
【請求項１１】
前記差分テーブルは、コンテンツの前記一方のバージョンおよびコンテンツの前記他方のバージョンに関連付けられるメタデータに少なくとも基づく、請求項１０記載の方法。
【請求項１２】
前記メタデータはコンテンツ記述データである、請求項１１記載の方法。
【請求項１３】
前記コンテンツ記述データは、マップファイル、シンボルテーブル、デバッグテーブルよりなる群のいずれかである、請求項１２記載の方法。
【請求項１４】
前記コンテンツはコンピュータプログラムを含む、請求項１から請求項１３のいずれかに記載の方法。
【請求項１５】
前記プログラムは実行可能なプログラムである、請求項１４記載の方法。
【請求項１６】
前記コンテンツはデータを含む、請求項１から請求項１５のいずれかに記載の方法。
【請求項１７】
繰り返しに適用される、請求項１から請求項１６のいずれかに記載の方法であって、
ａ）前の繰り返しにおいて得られた変更バージョンおよび前記他方のバージョンと関連付けられる変換子を生成するステップと、
ｂ）（ａ）で得られた前記変換子を前記前の繰り返しにおいて得られた前記変更バージョンに適用して変更バージョンを生成するステップと、
ｃ）前の全ての繰り返しで生成された変換子、ならびに少なくとも（ｂ）に定められた前記変更バージョンおよび前記他方のバージョンに基づく変更デルタを含む、複合変換子を有するコンパクトな更新パッケージを生成するステップと、
ｄ）停止基準が満たされない場合には次の繰り返しに進み、さもなければ、繰り返し中に生成された前記コンパクトな更新パッケージのうち最小サイズを有するコンパクトな更新パッケージを選択するステップと、を含む、請求項１から請求項１６のいずれかに記載の方法。
【請求項１８】
前記停止基準は、コンパクトな更新パッケージが前記前の繰り返しにおいて生成されたコンパクトな更新パッケージよりも大きい場合に満たされる、請求項１７記載の方法。
【請求項１９】
記憶装置に記憶されたコンテンツの更新に用いられる、請求項１から請求項１８のいずれかに記載の方法。
【請求項２０】
前記記憶装置は組み込み機器と関連付けられる、請求項１９記載の方法。
【請求項２１】
前記組み込み機器は、セルラー電話機、家庭用電化製品よりなる群のいずれかである、請求項２０記載の方法。
【請求項２２】
前記記憶装置はコンピュータと関連付けられる、請求項１９記載の方法。
【請求項２３】
コンテンツの旧バージョンを更新してコンテンツの新バージョンを生じさせる方法であって、
（ｉ）前記旧バージョンおよび前記新バージョンに関連付けられる変換子、変更デルタ、ならびに順方向更新または逆方向更新の表示を含む、コンパクトな更新パッケージを取得するステップと、
（ｉｉ）前記順方向更新表示の場合に、
ａ．前記旧バージョンに前記変換子を適用して変更バージョンを生成するステップと、
ｂ．前記変更バージョンに前記変更デルタを適用して前記新バージョンを生成するステップと、
（ｉｉｉ）前記逆方向更新表示の場合に、
ａ．前記旧バージョンに前記変更デルタを適用して変更バージョンを生成するステップと、
ｂ．（ｉｉｉ）（ａ）に定められた前記変更バージョンに前記変換子を適用して前記新バージョンを生成するステップと、を有する方法。
【請求項２４】
前記変換子は複合変換子である、請求項２３記載の方法。
【請求項２５】
前記（ｉ）は、前記コンパクトな更新パッケージを受け取るステップを含む、請求項２３記載の方法。
【請求項２６】
前記変換子は少なくとも１つのシフト規則を含む、請求項２３から請求項２５のいずれかに記載の方法。
【請求項２７】
前記シフト規則は数値シフト規則である、請求項２６記載の方法。
【請求項２８】
前記数値シフト規則は整数シフト規則である、請求項２７記載の方法。
【請求項２９】
前記シフト規則は参照シフト規則である、請求項２６から請求項２８のいずれかに記載の方法。
【請求項３０】
前記少なくとも１つの参照シフト規則は差分テーブルと関連付けられる、請求項２９記載の方法。
【請求項３１】
前記差分テーブルは、コンテンツの前記一方のバージョンおよびコンテンツの前記他方のバージョンに関連付けられるメタデータに少なくとも基づく、請求項３０記載の方法。
【請求項３２】
前記メタデータはコンテンツ記述データである、請求項３０記載の方法。
【請求項３３】
前記コンテンツ記述データは、マップファイル、シンボルテーブル、デバッグテーブルよりなる群のいずれかである、請求項３２記載の方法。
【請求項３４】
前記コンテンツはコンピュータプログラムを含む、請求項２３から請求項３３のいずれかに記載の方法。
【請求項３５】
前記プログラムは実行可能なプログラムである、請求項３４記載の方法。
【請求項３６】
前記コンテンツはデータを含む、請求項２３から請求項３５のいずれかに記載の方法。
【請求項３７】
記憶装置に記憶されているコンテンツの更新に用いられる、請求項２３から請求項３６のいずれかに記載の方法。
【請求項３８】
前記記憶装置は組み込み機器と関連付けられる、請求項３７記載の方法。
【請求項３９】
前記組み込み機器は、セルラー電話機、家庭用電化製品よりなる群のいずれかである、請求項３８記載の方法。
【請求項４０】
前記記憶装置はコンピュータと関連付けられる、請求項３７記載の方法。
【請求項４１】
記憶装置に記憶されているコンテンツの旧バージョンを新バージョンに更新させて前記コンテンツのバージョンを更新させる更新パッケージを生成する方法であって、
前記旧バージョンの参照項目において参照される項目のアドレスを示す値を決定するステップと、
前記旧バージョンにおいて参照される項目に対する変更シフトを決定するステップと、
前記変更シフトに従って前記参照項目を変更させる整数シフト規則を設定するステップと、を有する方法。
【請求項４２】
コンテンツの旧バージョンおよび前記コンテンツの新バージョンの間のコンパクトな更新パッケージを生成するための方法ステップを実行する機械によって実行可能な命令のプログラムを明白に具現化する、機械読み取り可能なプログラム記憶装置であって、前記方法は、
（ｉ）前記旧バージョンおよび前記新バージョンに関連付けられる変換子を生成するステップと、
（ｉｉ）前記バージョンの一方に前記変換子を適用して変更バージョンを生成するステップと、
（ｉｉｉ）前記変換子、ならびに少なくとも前記変更バージョンおよび（ｉｉ）に定められた前記一方のバージョン以外の前記バージョンに基づく変更デルタを含む、前記コンパクトな更新パッケージを生成するステップと、を有する、プログラム記憶装置。
【請求項４３】
コンテンツの旧バージョンおよび前記コンテンツの新バージョンの間のコンパクトな更新パッケージを生成するための方法ステップを実行する機械によって実行可能な命令のプログラムを明白に具現化する、機械読み取り可能なプログラム記憶装置であって、前記方法は、
（ｉ）前記旧バージョンおよび前記新バージョンに関連付けられる変換子、変更デルタ、ならびに順方向更新または逆方向更新の表示を含む、コンパクトな更新パッケージを取得するステップと、
（ｉｉ）前記順方向更新表示の場合に、
ａ）前記旧バージョンに前記変換子を適用して変更バージョンを生成するステップと、
ｂ）前記変更バージョンに前記変更デルタを適用して前記新バージョンを生成するステップと、
（ｉｉｉ）前記逆方向更新表示の場合に、
ａ）前記旧バージョンに前記変更デルタを適用して変更バージョンを生成するステップと、
ｂ）（ｉｉｉ）（ａ）に定められた前記変更バージョンに前記変換子を適用して前記新バージョンを生成するステップと、を有する、プログラム記憶装置。
【請求項４４】
コンテンツの旧バージョンおよび前記コンテンツの新バージョンの間のコンパクトな更新パッケージを生成するシステムであって、
前記旧バージョンおよび前記新バージョンに関連付けられる変換子を生成する変換子生成部と、
前記バージョンの一方に前記変換子を適用して変更バージョンを生成する変更バージョン生成部と、
前記変換子、ならびに少なくとも前記変更バージョンおよび前記一方のバージョン以外の前記バージョンに基づく変更デルタを含む、前記コンパクトな更新パッケージを生成する更新パッケージ生成部と、を有するシステム。
【請求項４５】
コンテンツの旧バージョンを更新してコンテンツの新バージョンを生じさせるシステムであって、
前記旧バージョンおよび前記新バージョンに関連付けられる変換子、変更デルタ、ならびに順方向更新または逆方向更新の表示を含む、コンパクトな更新パッケージを取得するよう構成された入力モジュールと、
前記順方向更新表示の場合に、
ａ）前記旧バージョンに前記変換子を適用して変更バージョンを生成し、
ｂ）前記変更バージョンに前記変更デルタを適用して前記新バージョンを生成し、
前記逆方向更新表示の場合に、
ａ）前記旧バージョンに前記変更デルタを適用して変更バージョンを生成し、
ｂ）前記変更バージョンに前記変換子を適用して前記新バージョンを生成する、
よう構成されたプロセッサと、を有するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶装置に記憶されたコンテンツのコンパクトな更新バージョンの作成に関する。
【背景技術】
【０００２】
特許文献１には、旧プログラムと新プログラムとの間のコンパクトな差分結果を生成する方法が開示されている。
【０００３】
各プログラムは、プログラム中の他のエントリーを参照する参照を含むエントリーを有する。この方法は、旧プログラムを走査するステップを含み、参照エントリー毎に、独自のラベルマークによってエントリーの参照を置き換えるステップを実行し、これにより、変更された旧プログラムが生成される。更に、この方法は、新プログラムを走査するステップを含み、参照エントリー毎に、独自のラベルマークによってエントリーの参照を置き換えるステップを実行し、これにより、変更された新プログラムが生成される。更に、変更後の旧プログラムおよび変更後の新プログラムを直接的にまたは間接的に利用して特定の差分結果を生成するステップも行われる。
【０００４】
この技術分野においては、記憶装置に記憶されたコンテンツのバージョンを更新する新しい方法およびシステムが、求められている。
【特許文献１】米国特許第６，５４６，５５２号明細書
【発明の開示】
【０００５】
本発明は、コンテンツの旧バージョンと当該コンテンツの新バージョンとの間でコンパクトな更新パッケージを生成する方法であって、
（ｉ）当該旧バージョンおよび新バージョンに関連付けられる変換子を生成するステップと、
（ｉｉ）上記バージョンの一方に上記変換子を適用して変更バージョンを生成するステップと、
（ｉｉｉ）上記変換子、ならびに少なくとも上記変更バージョンおよび（ｉｉ）に定められた上記一方のバージョン以外の上記バージョンに基づく変更デルタを含む、コンパクトな更新パッケージを生成するステップと、を有する方法を、提供する。
【０００６】
本発明は、コンテンツの旧バージョンを更新してコンテンツの新バージョンを生じさせる方法であって、
（ｉ）上記旧バージョンおよび上記新バージョンに関連付けられる変換子、変更デルタ、ならびに順方向更新または逆方向更新の表示を含む、コンパクトな更新パッケージを取得するステップと、
（ｉｉ）順方向更新表示の場合に、
ａ）上記旧バージョンに上記変換子を適用して変更バージョンを生成するステップと、
ｂ）上記変更バージョンに上記変更デルタを適用して上記新バージョンを生成するステップと、
（ｉｉｉ）逆方向更新表示の場合に、
ａ）上記旧バージョンに上記変更デルタを適用して変更バージョンを生成するステップと、
（ｉｉｉ）（ａ）に定められた上記変更バージョンに上記変換子を適用して上記新バージョンを生成するステップと、を有する方法を更に提供する。
【０００７】
本発明は、更に、記憶装置に記憶されている旧バージョンを新バージョンに更新させて上記コンテンツのバージョンを更新させる更新パッケージを生成する方法であって、
上記旧バージョンの参照項目において参照される項目のアドレスを示す値を決定するステップと、
上記旧バージョンにおいて参照される項目に対する変更シフトを決定するステップと、
上記変更シフトに従って上記参照項目を変更させる整数シフト規則を設定するステップと、を有する方法を提供する。
【０００８】
本発明は、更に、コンテンツの旧バージョンおよびコンテンツの新バージョンの間のコンパクトな更新パッケージを生成する方法ステップを実行する機械実行可能な命令のプログラムを明白に具現化する、機械読み取り可能なプログラム記憶装置であって、上記方法は、
（ｉ）上記旧バージョンおよび上記新バージョンに関連付けられる変換子を生成するステップと、
（ｉｉ）上記バージョンの一方に上記変換子を適用して変更バージョンを生成するステップと、
（ｉｉｉ）上記変換子、ならびに少なくとも上記変更バージョンおよび（ｉｉ）に定められた上記バージョンの一方以外の上記バージョンに基づく変更デルタを含む、コンパクトな更新パッケージを生成するステップと、を有する、プログラム記憶装置を提供する。
【０００９】
本発明は、更に、コンテンツの旧バージョンおよびコンテンツの新バージョンの間のコンパクトな更新パッケージを生成する方法ステップを実行する機械実行可能な命令のプログラムを明白に具現化する、機械読み取り可能なプログラム記憶装置であって、上記方法は、
（ｉ）上記旧バージョンおよび上記新バージョンに関連付けられる変換子、変更デルタ、ならびに順方向更新または逆方向更新の表示を含むコンパクトな更新パッケージを生成するステップと、
（ｉｉ）順方向更新表示の場合に、
ａ）上記旧バージョンに上記変換子を適用して変更バージョンを生成し、
ｂ）上記変更バージョンに上記変更デルタを適用して上記新バージョンを生成するステップと、
（ｉｉｉ）逆方向更新表示の場合に、
ａ）上記旧バージョンに上記変更デルタを適用して変更バージョンを生成し、
ｂ）（ｉｉｉ）（ａ）に定められた上記変更バージョンに上記変換子を適用して上記新バージョンを生成するステップと、を有する、プログラム記憶装置を提供する。
【００１０】
本発明の別の態様によると、コンテンツの旧バージョンおよびコンテンツの新バージョンの間のコンパクトな更新パッケージを生成するシステムであって、
上記旧バージョンおよび上記新バージョンに関連付けられる変換子を生成する変換子生成部と、
上記バージョンの一方に上記変換子を適用して変更バージョンを生成する変更バージョン生成部と、
上記変換子、ならびに少なくとも上記変更バージョンおよび上記一方のバージョン以外の上記バージョンに基づく変更デルタを含む、コンパクトな更新パッケージを生成する更新パッケージ生成部と、を備えるシステムを提供する。
【００１１】
本発明は、更に、コンテンツの旧バージョンを更新してコンテンツの新バージョンを生じさせるシステムであって、
上記旧バージョンおよび新バージョンに関連付けられる変換子、変更デルタ、ならびに順方向更新または逆方向更新の表示を含む、コンパクトな更新パッケージを取得するよう構成された入力モジュールと、
順方向更新表示の場合に、
ａ）上記旧バージョンに上記変換子を適用して変更バージョンを生成し、
ｂ）上記変更バージョンに上記変更デルタを適用して上記新バージョンを生成し、逆方向更新表示の場合に、
ａ）上記旧バージョンに上記変更デルタを適用して変更バージョンを生成し、
ｂ）（ｉｉｉ）（ａ）に定められた上記変更バージョンに上記変換子を適用して上記新バージョンを生成するよう構成されたプロセッサと、を具備するシステムを提供する。
【発明を実施するための最良の形態】
【００１２】
以下に、本発明を理解し、本発明をどのように実施するかを知るために、添付の図面を参照し非限定的な例を用いて好ましい実施の形態を説明する。
【００１３】
図１は、本発明の一実施の形態による、セルラーネットワークにおいてバージョンの更新を提供するシステム１０１を示す概略図である。メモリ装置に接続されているセルラー電話機１０２は、その動作を有効にするプログラムを実行する。以降、セルラー電話機で現在実行されているプログラムのバージョンを「旧バージョン」と称する。電話機１０２がその新バージョンを実行するために、プログラムを更新する必要が時々ある。新バージョンは、パーソナルコンピュータ（ＰＣ）のようなバージョン生成部１０５で生成される。新バージョンは、サーバ１０３に記憶され、送信部１０４を介してセルラー電話機１０２に送信される。
【００１４】
図１に示されるシステム１０１は、非限定的な例であり、本発明がセルラーネットワークまたはプログラムの更新に限定されないことに注意されたい。他の多種のコンテンツ、例えば、記憶装置に記憶されているデータは、更新を必要とする。例えば、パーソナルコンピュータ（ＰＣ）または全ての他のコンピュータは、その動作または実行されるプログラムの動作に必要なデータを含むファイル（例えば、当該技術分野において知られている「情報ファイル（info file）」）を記憶する。このデータをインターネット等の通信線を介して更新することが時として必要である。
【００１５】
従って、以降「コンテンツ」なる用語を「プログラム」の代わりに用いる。同様に、「記憶装置」なる用語を、図１のセルラー電話機のメモリ装置の代わりに用いる。
【００１６】
記憶装置に記憶されたコンテンツを更新するために、更新パッケージが生成され、サーバに記憶され、記憶装置またはそれに接続されている他の装置に送信される。
【００１７】
記憶装置は、組み込み機器（embedded device）と関連付けることができることに注意されたい。組み込み機器は、例えば、セルラー電話機および／または家庭用電化製品よりなる群のいずれかとすることができる。あるいは、記憶装置は、コンピュータと関連付けることができる。
【００１８】
図２は、コンテンツ２０２の旧バージョンを新バージョン２０３に更新するよう構成された更新パッケージ２０１の概略図である。コンテンツの旧バージョン（例えば、旧バージョン２０２）は、単に「旧バージョン」とも称される。同様に、コンテンツの新バージョン（例えば、新バージョン２０３）は、単に「新バージョン」とも称される。
【００１９】
更新パッケージ２０１は、当業者に知られた方法自体に従って生成できることに注意されたい。同様に、旧バージョン２０２を新バージョン２０３に更新する際にこの更新パッケージを適用する方法も、既知である。
【００２０】
更新パッケージは、「デルタファイル」、「差分ファイル」、または単に「デルタ」、「差分」と称される。「デルタ」とは、旧バージョンから新バージョンへの更新の際に発生する変更の集合である。従って、更新パッケージがデルタファイルであること、あるいは更新パッケージがデルタファイルおよび追加情報を含み得ることは、当業者には明らかである。
【００２１】
旧バージョン２０２は、５項目よりなるブロック２０４を含み、各項目は少なくとも１ワードのサイズ、１バイト以上のサイズ、または他の適用可能な寸法を用いてもよい。ブロック２０４の後に、例えば５００項目よりなる第２のブロック２０５が続く。次に、旧バージョン２０２は、第２のブロック２０５中のある項目２０７に対する参照（例えば、ポインタ）を少なくとも含む項目２０６を有する。以降、少なくとも１つの参照を含む項目を「参照項目」と称する。例えば、参照項目２０６は、項目２０７に対する絶対参照と関連付けられる命令（例えば、「項目２０７の絶対アドレスにジャンプする」）を含むことができる。
【００２２】
例えば、旧および新バージョン（例えば、２０２および２０３）によって表されるコンテンツがコンピュータプログラムである場合、ブロックは、当業者に知られているように、プログラム機能を表すことは理解されるであろう。
【００２３】
参照項目２０６の後に、第２のブロック２０５中の異なる項目２０９に対する参照を含む別の参照項目２０８が続く。参照項目２０８の後に、他の参照項目が続き、これらの項目はそれぞれ第２のブロック２０５内の項目への参照を含み、最後が参照項目２１０となる。図示されないが、一例によると、例えば、１００個の参照項目が参照項目２０６と参照項目２１０との間に存在する。
【００２４】
旧バージョン２０２が非参照項目、即ち参照を含まない項目も含み得ることは理解されるであろう。項目２１１は、非参照項目の例である。以降、別段の記載のない限り、「項目」なる語は、参照項目および非参照項目の両方を意味する。
【００２５】
更に、旧バージョン２０２は、旧バージョン２０２に含まれていない他の項目への参照項目、即ち、コンテンツの外部にある項目への参照も含む。例えば、旧バージョンが、その実行中にコンピュータのＲＡＭ（ランダムアクセスメモリ）にロードされたコンピュータプログラムを表す場合、このような参照項目は、当該プログラムを記憶するために使用される領域の外のＲＡＭ領域に記憶された他の項目を参照する。
【００２６】
以降、コンテンツに含まれる項目に対する参照を少なくとも含む参照項目を「明示参照項目」と称し、コンテンツの外部にある項目に対する参照を少なくとも含む参照項目を「暗示参照項目」と称する。
【００２７】
図２を再び参照するに、図示されていないが、最後の参照項目２１０に続いて７０項目が存在する。便宜上、これら７０項目（項目２１１を含む）を以降「末端項目」２１２と称する。当該７０項目は、非参照項目（例えば、項目２１１）および／または暗示参照項目（例えば、項目２１３）を含む。本例に従って更新される全てのコンテンツのサイズが非限定的であり、従って、このコンテンツのブロックのサイズも非限定的であることは明らかである。
【００２８】
図２に図示されないが、非参照項目は、参照項目間に存在してもよく、参照項目は必ずしも連続である必要はない。例えば、参照項目２０６、２０８、・・・、２１０間のどこかに非参照項目が１つ以上存在してもよい。
【００２９】
更新パッケージ２０１は、コンテンツの旧バージョン２０２を変更して、コンテンツの新バージョン２０３を生成するよう構成される。更新処理は、この新バージョン２０３を生成するよう更新パッケージ２０１に従って動作する。
【００３０】
本例における旧バージョン２０２と新バージョン２０３との間の１つの差分は、新バージョン２０３からブロック２０４が欠如している点であり、第２のブロック２０５は後方にシフトし、記憶装置内のブロック２０４を占有する。本例によると、ブロック２０４は、５項目を含むため、第２のブロック２０５は５ブロック分後方にシフトする。従って、ブロック２０５の後方へのシフトに引き続き、そこに含まれる全ての項目がこれに応じて（５項目分）シフトされることは明らかである。これは、例えば、項目２０７および２０９（および新バージョンにおけるそれぞれの対応項目２０７’および２０９’）の場合も同様である。ここで、項目２０６が項目２０７への参照を含むことに注意されたい。項目２０６を後方にシフトして項目２０６’を生成した後にも、当該項目はまだ項目２０７を参照している、即ち、旧バージョンにおける項目２０７のアドレスを参照している。新バージョン内の新しい場所の項目２０７’を参照するよう項目２０６’のコンテンツを置換する必要がある。
【００３１】
参照を含まない非参照項目２１１のコンテンツと暗示参照項目２１３のコンテンツとが、それぞれの場所が５項目分上方にシフトされているにも関わらず、変更を要しないことに注意されたい。本明細書中、別段の記載のない限り、明示参照項目に適用される例は暗示参照項目にも適用可能であることに注意されたい。
【００３２】
ここで更新パッケージ２０１に戻ると、更新パッケージ２０１は、旧バージョン２０２を新バージョン２０３に更新するコマンドを含む。本例では、コマンドは、旧コンテンツを更新することで実行される１つ以上の動作を表す文字列（例えば、「コピー（copy）」、「置換（replace）」等）として例示される。しかし、例えばオペレーションコード（単に「オペコード（op-code）」とも称する）を用いた他のコマンド表現方法も可能であり、コマンド毎に所定のオペコードが割り当てられる。更に、コマンドは更新パッケージ２０１に示されるものに代わる方法でしばしば表される。例えば、「置換（replace）」コマンドは、既存コンテンツを置換する挿入コマンドによって表すことができる。
【００３３】
図示するように、パッケージ２０１に含まれる第１のコマンドは、５項目を削除（delete）することであり、これにより、旧バージョン２０２における最初の５項目（すなわちブロック２０４）が削除される。次に、更新パッケージは、５００項目を新バージョンの始めにコピーしブロック２０５を後方に５項目分シフトしブロック２０５’を生じさせるコマンドを含む。
【００３４】
ブロック２０５のコピー後、一見したところでは、項目２０６、２０８、・・・、２１０の位置を５ブロック分シフトしつつこれらの項目をコピーして、対応する項目２０６’、２０８’、・・・、２１０’を生じさせることが必要のようである。しかし、前述のように、項目２０６’、２０８’、・・・、２１０’に含まれる参照は、項目２０７、２０９、・・・ではなく、参照項目２０７’、２０９’、・・・に更新される必要がある。つまり、これらの参照項目または少なくともその一部は置き換える必要がある。参照項目をコピーし、そして、シフトされた参照で置換する代わりに、コピー動作を省略して、項目を直接置換することも可能である。従って、更新パッケージ２０１は、対応するシフトされた項目（２０６’、２０８’、・・・、２１０’）への参照で参照項目２０６、２０８、・・・、２１０を置換するための１００個の置換コマンドを、各参照項目２０６、２０８、・・・、２１０に対して１つずつ含む。
【００３５】
１００個の置換コマンドに続いて、更新パッケージ２０１は、コピーコマンドを含む。コピーコマンドは、新バージョン２０３内の置換された１００個の参照項目に後続するよう７０個の末端項目２１２、即ち、新バージョン２０３において後方に５項目分シフトされた７０項目（項目２１１’および２１３’を生じさせる項目２１１および２１３を含む）をコピーするものである。
【００３６】
当業者には、上述の例における更新パッケージ２０１がとりわけ１００個の置換コマンドを含み各置換コマンドが置換項目を含むということは明らかである。つまり、更新パッケージ２０１は、１００個の置換項目を含む。更新パッケージがインターネットまたはモバイル（セルラー）ネットワークのような限られた帯域幅の通信回線上で伝送され得ることを考慮して、更新パッケージのサイズを減少することは有益である。
【００３７】
従って、本発明は、更新パッケージを生成し適用するための既知の方法とは異なる、以降「コンパクトな更新パッケージ」と称する効率的な更新パッケージを生成することができる方法を開示する。このような効率的な更新パッケージを生成する一実施の形態を、以降「整数表記形態（integer notation embodiment）」と称し、当該実施の形態は「整数シフト規則」を生成する。整数シフト規則を説明するための背景を、図２および図３を参照して以下に説明する。
【００３８】
本発明の幾つかの実施の形態によれば、旧および新バージョン（それぞれ２０２および２０３）における項目を表すために整数値を用いることができることは明らかである。項目は、ディスクまたはメモリのような記憶装置に記憶されたデータであることは明らかである。１項目のサイズが４バイトである場合、４バイトを使用する整数として１項目に記憶されたデータを視覚化することが可能である。図３は、本発明の一実施の形態による、４バイトの項目３０１の整数表示の概略図である。最上位バイト（最も左のバイト）３０２は、２進値００００１０１１（１６進数では０ｘ０Ｂ）によって占有され、第２のバイト３０３は、２進値１００１１１０１（１６進数では０ｘ９Ｄ）によって占有され、第３のバイト３０４は１１１１０１１１（１６進数では０ｘＦ７）によって占有され、最下位バイト３０５は、値１００００１０１（１６進数では０ｘ８５）によって占有される。従って、４バイトは、０ｘ０Ｂ９ＤＦ７８５の１６進数を有する１つの整数として解釈することができる。つまり、整数０ｘ０Ｂ９ＤＦ７８５は、項目３０１の整数表示であり、以降ｉｎｔ（３０１）と表記される。「ｉｎｔ」は、「整数」を意味する。
【００３９】
非参照項目を含む全ての項目が同様に整数で表すことができる。従って、例えば、ｉｎｔ（２１１）は項目２１１の整数表示である。
【００４０】
図２を再び参照するに、例えば、明示参照項目２０６は、「項目２０７の絶対アドレスにジャンプする」なるプログラム命令を含む。項目２０７の絶対アドレスが０ｘ９ＤＦ７８５である場合、項目２０６に含まれる命令は、「０ｘ９ＤＦ７８５にジャンプする」に相当する。プログラム命令を、所定のオペコードによって表してもよい。従って、「〜にジャンプする」ためのオペコードは、例えば、１０進整数「１１」（または１６進数では０ｘＢ）である。図３を参照して説明したように、本例による項目２０６の整数表示は０ｘ０Ｂ９ＤＦ７８５である。この場合のオペコードは、バイト３０２によって表され、バイト３０３、３０４および３０５は、参照される項目を表示する。つまり、バイト３０３、３０４および３０５は、参照される項目を一緒に示し、以降ｉｎｄ（２０７）と称される。「ｉｎｄ」は、「表示」を意味する。
【００４１】
または、整数全体を、参照される項目を示すものとしてみることも可能である。本例では、項目２０６が命令「項目２０７にジャンプする」を含む場合、０ｘ９ＤＦ７８５のみを表示値とした前の実施の形態とは異なり、整数０ｘ０Ｂ９ＤＦ７８５をｉｎｄ（２０７）として考えることができる。「項目２０７を呼び出す」のような命令を含む別の参照項目（図２には図示せず）が存在してもよいことは明らかである。呼び出し命令に対するオペコードは１０進整数２７（または１６進数では０ｘ１Ｂ）である。本例では、ｉｎｔ（参照項目）は０ｘ１Ｂ９ＤＦ７８５である。なお、０ｘ１Ｂ９ＤＦ７８５は、この場合、ｉｎｄ（参照される項目）またはｉｎｄ（２０７）として参照可能である。つまり、本実施の形態では、参照される項目のアドレスに対して表示値が１つ以上存在してもよい。
【００４２】
また、表示値が項目の整数表示のどの部分（全体でもよい）でもよいことは明らかである。また、本例は４バイトのサイズの項目に言及する。このサイズは、ここでは単に例として使用され（以下で再び使用される）、他の項目サイズを用いてもよい。数値を整数として表すことは非限定的な例に過ぎず、他の既知の数値表示を用いてもよい。
【００４３】
項目（参照項目および／または非参照項目を含む）を整数値で表すことができることを考慮しつつ、図２を再び参照するに、更新パッケージ２０１における置換コマンドを整数で表すことが可能である。例えば、「ｉｎｔ（２０６）、ｉｎｔ（２０６’）を置換する」は、更新パッケージ２０１の一部である「Ｒｅｐｌａｃｅ  ２０６、２０６’」と等価である。
【００４４】
図４は、本発明の一実施の形態に従って、整数表記を用いて図２の更新パッケージの一部分を示すものである。部分４０１は、置換コマンドを含む更新パッケージ２０１の部分である。部分４０１は従来技術に従っていることが分かる。本例における全ての置換コマンドが、１つが旧バージョン内のものであり１つが新バージョン内のものである２つの参照項目と関連付けられることに注意されたい。以降、この２つの参照項目を「置換対」として称する。
【００４５】
当業者には、部分４０２が部分４０１と等価であることは明らかであり、置換コマンドは、本発明の一実施の形態に従って、整数表記を用いて表される。整数表記が用いられるとき、各置換コマンドと関連付けられる２つの整数が存在する。以降、この２つの整数を「整数置換対」と称する。整数置換対における一方の整数を「変更前整数」（旧バージョンにおける項目を表す）と称し、他方を「変更後整数」（新バージョンにおける項目を表す）と称する。
【００４６】
旧バージョン２０２における明示参照項目に対する整数置換対を見ると、即ち部分４０２における整数置換対を見ると、整数値が参照される項目のシフトを反映していることが分かる。例えば、項目２０８および項目２０８’がそれぞれ項目２０９および２０９’を参照する場合、整数置換対を＜ｉｎｔ（２０８）、ｉｎｔ（２０８’）＞と見ることができる。項目２０９がアドレス０ｘ９ＤＦ７８５に元々位置し、項目のサイズが４バイトである場合、項目２０９のコンテンツを後方に５項目分（即ち、後方に２０バイト分）シフトして項目２０９’を得た後の項目２０９’はアドレス０ｘ９ＤＦ７７１に位置する。参照項目の最下位バイトが、参照される項目のアドレスを示す値を含むことを考えると、参照項目２０８を表す整数の最下位バイトは０ｘ９ＤＦ７８５（つまり、項目２０８が項目２０９を参照する）であり、参照項目２０８’の最下位バイトは０ｘ９ＤＦ７７１（即ち、項目２０８’が項目２０９’を参照する）であることが理解できる。従って、整数置換対を一緒に有する２つの整数の間の差分は、旧バージョン２０２を新バージョン２０３に更新する間に実行されるシフトを反映する。以降、この差分を「変更差分」と称する。変更差分は、例えば、ｄｉｆｆ（２０８）のように、変更された整数と共にｄｉｆｆによって表される。
【００４７】
従って、変更前整数と変更後整数とを関連付けて整数置換対とする代わりに、変更前整数または変更後整数を変更差分と関連付けることが可能である。変更前整数を変更差分に関連付けてなる対を、以降「整数シフト対」と称する。
【００４８】
図４において、部分４０３は、整数シフト対の表記を用いた、部分４０１および４０２と等価の部分である。
【００４９】
図３および図４を参照した説明は、整数表記を利用する本発明の実施の形態を理解するための背景であり、以降「整数表記形態」と称する。
【００５０】
図５は、整数表記形態を例示し説明するために、旧および新バージョンのより複雑な例（図２に示す旧バージョンおよび新バージョンと比較して）を示すものである。図中、旧バージョン５０１は、新バージョン５０２を生じさせるよう更新される。よって、旧バージョン５０１は、新しいバージョン５０２の生成の際に削除されるブロック５０３を含む。削除されたブロックのサイズを、以降ｓｉｚｅ（５０３）と称する。図２の例に従って、ブロック５０３の削除に引き続き、新バージョン中の項目がｓｉｚｅ（５０３）の項目分だけ後方にシフトされることとなることは理解されるであろう。
【００５１】
旧バージョンでは、ブロック５０４はブロック５０３に後続する。６個の項目（５０５、５０６、５０７、５０８、５０９および５１０）がブロック５０４内でマーキングされている。項目の開始アドレスは、例えば、ａｄｄｒ（５０５）、ａｄｄｒ（５０６）およびａｄｄｒ（５０７）等のように、以降、ａｄｄｒ（項目）としてマーキングされる。ブロック５０８、５０９および５１０は明示参照項目である。項目５０９は項目５０７を参照し、項目５０８、５１０はそれぞれ項目５１１および５１２を参照する。項目５１１および５１２は旧バージョンの一部であり、ブロック５０４の前方に位置することが分かる。従って、明示参照項目５０８、５０９および５１０は、それぞれａｄｄｒ（５１１）、ａｄｄｒ（５０７）およびａｄｄｒ（５１２）を示す値を含む。
【００５２】
新バージョン５０２では、ブロック５０４’はブロック５０４に対応する。予想される通り、ブロック５０４’は、ｓｉｚｅ（５０３）だけ後方にシフトされている。項目５０５’、５０６’、５０７’、５０８’、５０９’および５１０’は、それぞれ項目５０５、５０６、５０７、５０８、５０９および５１０に対応する。ブロック５０４’と同様に、項目５０５’、５０６’、５０７’、５０８’、５０９’および５１０’は、ｓｉｚｅ（５０３）分だけ後方にシフトされる。
【００５３】
ブロック５０４に続いて、旧バージョン５０１は、マーキングされた１つの項目５１４を有するブロック５１３を含む。項目５１４は、項目５０６を参照する明示参照項目であり、即ち、参照項目５１４は、アドレスａｄｄｒ（５０６）を示す値を含む。新バージョンでは、ブロック５１３’はブロック５１３に対応し、項目５１４’は項目５１４に対応する。しかしながら、１つ以上の項目よりなる新しいブロック５１５が、ブロック５１３’の項目５１４’の前に挿入される。つまり、ｓｉｚｅ（５１３’）＞ｓｉｚｅ（５１３）である。本例においては、ｓｉｚｅ（５１５）がｓｉｚｅ（５０３）よりも小さいため、項目５１４’は（ｓｉｚｅ（５０３）−ｓｉｚｅ（５１５））だけ後方にシフトされる。
【００５４】
旧バージョン５０１を参照するに、ブロック５１３に続く第３のブロック５１６が存在する。このブロック内では、５項目がマーキングされている。具体的には、項目５１７、５１８、５１９、５１１および５１２がある。項目５１７および５１８はそれぞれ項目５１９および５０５を参照する明示参照項目であり、つまり、項目５１７および５１８は、参照される項目５１９および５０５を示す、換言すれば、それぞれａｄｄｒ（５１９）およびａｄｄｒ（５０５）を示す値を含む。
【００５５】
新バージョンでは、ブロック５１６’はブロック５１６に対応する。同様に、項目５１７’、５１８’、５１９’、５１１’および５１２’は、それぞれ項目５１７、５１８、５１９、５１１および５１２に対応する。ブロック５１３’へのブロック５１５の挿入に続いて、ブロック５１６’中の項目が（ｓｉｚｅ（５０３）−ｓｉｚｅ（５１５））項目分だけ後方にシフトされることは明らかである。
【００５６】
図５の例も、旧バージョンにおける末端ブロック５１７の存在を示しており、これは新バージョンにおけるブロック５１７’に対応する。更新処理は、１つ以上の項目よりなる新しいブロック５２０をブロック５１７’に挿入する。本例によると、新しいブロック５２０のサイズが（ｓｉｚｅ（５０３）−ｓｉｚｅ（５１５））であるため、新バージョン５０２の全体的なサイズは、旧バージョン５０１と略同じになる。
【００５７】
図５を参照して提供される例は、如何なる制限も設けられるものではない。この例に適用できるように、如何なるコンテンツの旧または新バージョンも、任意の数の項目をそれぞれ含む任意の数のブロックを有することができる。同様に、旧バージョンを新バージョンに更新する際、更新処理は、特定用途に依存して、項目またはブロックのサイズを変更させつつ、必要に応じて何回でも、挿入、削除、置換および／または全ての所要の動作を実行することができる。
【００５８】
項目のサイズも非限定的であるが、以降、図５に示すコンテンツの１項目のサイズを４バイトとして示す。
【００５９】
本発明の一実施の形態によれば、旧バージョン５０１を新バージョン５０２に更新するために、ブロック５０４とブロック５１３の第１の部分とを新バージョンにコピーし、新しいブロック５１５を挿入し、ブロック５１６および５１７と共にブロック５１３の第２の部分を新バージョンにコピーしてもよいことは、当業者に明らかである。しかしながら、図２を参照して説明したように、そのようにすると、新バージョンにおける明示参照項目は、旧バージョンにそうであってように、元のアドレスの項目を参照する。例えば、旧バージョンでは、明示参照項目５０８は項目５１１を参照するため、項目５０８の最下位バイトはａｄｄｒ（５１１）を示す値を含む。旧バージョンでは、項目５０８は、ａｄｄｒ（５０８）に位置する。本例では、ブロック５０４を新バージョンにコピーした後、ａｄｄｒ（５０８）の後方のａｄｄｒ（５０８’）に項目５０８が配置されることが分かる。しかしながら、項目５０８は依然として項目５１１に対する参照を含む、即ち、ａｄｄｒ（５１１）を示す値を含む。そこで、ａｄｄｒ（５１１’）を示す値を含むことによって項目５１１’に対する参照を含むとなる。従って、本実施の形態では、旧バージョンから新しいバージョンにコンテンツをコピーした後、且つ、新しいブロック（例えば、ブロック５１５）を挿入した後、更新パッケージは、「項目５０８’において、ａｄｄｒ（５１１）を示す値を、ａｄｄｒ（５１１’）を示す値で置き換える」、または簡単に、「ｒｅｐｌａｃｅ  ５０８、５０８’」のような、参照項目を置き換えるためのコマンドを含む。
【００６０】
整数表記形態（上述の図３および図４を参照した）ならびに旧バージョンおよび新バージョン（図５を参照した）の例についての背景を説明した。以下では、整数表記形態に従って、更新パッケージの一部分をどのように得るかを、従来技術より得られる更新パッケージの等価部分と比較して例示する（図６を参照する）。説明から明らかとなるように、本実施の形態に従って得られる部分は、従来技術において既知の方法に従って得られるものよりも大幅に小さい。
【００６１】
図６を参照するに、部分６０１は、図５に例示する明示参照項目を更新する置換命令を含む。部分６０１は、図５の旧および新バージョンに対して従来のｄｉｆｆ法を適用することによって生成されることが分かる。また、部分６０１は、旧バージョン５０１を新バージョン５０２に更新するために使用される完全な更新パッケージの一部であることが分かる（完全な更新パッケーは図示せず）。この部分は、置換コマンドのみを含み、挿入および／または削除等の他のコマンドは省略されている。図５の例においては６個の参照項目があるため、部分６０１には６個の置換コマンドがあることに注意されたい。部分６０２は、整数置換対で表現された、部分６０１の対応部分であり、図３および図４の説明を鑑みると、参照項目に対して、「ｉｎｔ（項目）」なる用語がアドレス参照を反映していることが理解される。
【００６２】
更に、整数置換対の表記を用いる代わりに整数シフト対を用いて置換コマンドを表わすことが可能であることが図４を参照して説明された。つまり、参照項目を置換する代わりに、参照される項目の位置のシフトを反映するために、オペコードのような一緒に記憶されている他の情報とは無関係に、含まれている参照を変更することができる。
【００６３】
図５より、この例における幾つかの項目の変更差分がｓｉｚｅ（５０３）であり、他の項目が（ｓｉｚｅ（５０３）−ｓｉｚｅ（５１５））の変更差分によって特徴付けられていることが分かる。従って、部分６０２を変更することが可能であり、また、置換コマンドを用いる代わりに、６０３に示されるような変更前整数シフト対表記を用いる変更コマンドを用いてもよい。
【００６４】
整数シフト対における変更差分が、参照項目のシフトではなく参照される項目のシフトを示すことに注意されたい。
【００６５】
部分６０４では、更新パッケージの同じ部分が示され、変更コマンドは、変更差分に従ってソートされている。ソートされた部分６０４は２つのグループを含むことに注意されたい。一方のグループは、ｉｎｔ（５０９）、ｉｎｔ（５１４）およびｉｎｔ（５１８）を変更するコマンドを含み、変更差分はｓｉｚｅ（５０３）である。第２のグループは、ｉｎｔ（５０８）、ｉｎｔ（５１０）およびｉｎｔ（５１７）を変更するコマンドを含み、変更差分は（ｓｉｚｅ（５０３）−ｓｉｚｅ（５１５））である。
【００６６】
整数またはその一部が、参照される項目のアドレスを示すことを思い出すべきである。また、項目が更新される間、これに関連付けられるオペコードまたは他の情報に関わらず、参照は変更される必要があることに注意されたい。従って、整数シフト対では、整数を引用する代わりに、参照される項目を示す値、または「ｉｎｄ（参照される項目）」を引用することができる。以降、ｉｎｄ（参照される項目）およびこれに関連付けられる変更差分の対を、「表示シフト対」と称する。
【００６７】
図５および図６には図示されないが、同じ項目を参照する参照項目が２つ以上存在する場合もある。参照される項目の表示値が参照する項目の整数表示の一部である場合、時として、全ての参照する項目を同様の表示値によって表すことができる。整数全体が、参照される項目の表示値として使用される場合、参照する項目を表す表示値が２つ以上存在してもよい。
【００６８】
例えば、参照される項目のアドレスを０ｘ５Ｆ８Ｂ２３とする。アドレスを指定することによって、４個の参照項目がこの項目を参照する。第１の参照項目はオペコード０ｘＡ２を有し、第２の参照項目はオペコード０ｘ０Ｆを有し、第３の参照項目は０ｘ１Ｂを有する。第４の参照項目は、第１の参照項目と同様のオペコード（即ち、０ｘＡ２）を有する。表示値が３つの最下位バイトによって表される場合、４個の参照項目は全てｉｎｄ（０ｘ５Ｆ８Ｂ２３）として表される。一方、整数全体が、表示値として使用される場合、４個の参照項目を表す３つの異なる表示値が存在する。第１および第４の参照項目はｉｎｄ（０ｘＡ２５Ｆ８Ｂ２３）として表わされ、第２の参照項目はｉｎｄ（０ｘ０Ｆ５Ｆ８Ｂ２３）として表され、第３の参照項目はｉｎｄ（０ｘ１Ｂ５Ｆ８Ｂ２３）として表わされる。
【００６９】
図６を再び参照するに、部分６０５には、表示シフト対表記を用いて、部分６０４と等価であるソートされた部分が例示される。部分６０５は、ブロック５０４における項目を参照する参照項目をシフトするときにその中の表示値がｓｉｚｅ（５０３）分のシフトを反映するように変更されるべきであることを示している。ブロック５１６における項目を参照する参照項目をシフトするとき、その中の表示値は、（ｓｉｚｅ（５０３）−ｓｉｚｅ（５１５））分のシフトを反映するように変更されるべきである。
【００７０】
部分６０５に二つのグループが存在することが分かれば、ｉｎｄ（参照項目）に従って各グループを内部的にソートすることができ、その結果、６０６が生成される。ブロック５０４中の項目を示す値を有する参照項目を変更する３つの変更コマンドを有する代わりに、１つの合成変更コマンドを生成してｓｉｚｅ（５０３）分のシフトを反映するようブロック５０４中の項目を示す全ての値を更新するようにしてもよい。つまり、参照項目が項目５０５および５０７を含みそれらの間にある項目を示す値を有する場合、この値はｓｉｚｅ（５０３）分のシフトを反映するよう変更されるべきである。同様に、ブロック５１６中の項目を示す値を有する参照項目を変更するために３つの変更コマンドを有する代わりに、（ｓｉｚｅ（５０３）−ｓｉｚｅ（５１５））分のシフトを反映するようブロック５１６中の項目を示す全ての値を更新するために１つの合成変更コマンドを生成することができる。つまり、参照項目が項目５１１および５１９を含みそれらの間にある項目を示す値を有する場合、この値は部分６０７に示されるように（ｓｉｚｅ（５０３）−ｓｉｚｅ（５１５））分のシフトを反映するよう変更されるべきである。以降、このような合成変更コマンドを「整数シフト規則」と称する。つまり、部分６０７は、図５の例における明示参照項目を更新するために適用することができる２つの整数シフト規則を示す。
【００７１】
従って、整数シフト規則を用いた部分６０７が置換コマンドを用いた部分６０１と等価であることは理解されるであろう。部分６０７は、部分６０１に含まれる６個の置換コマンドの代わりに２個の整数シフト規則だけを含む。従って、部分６０７を含む更新パッケージは、部分６０１を含む更新パッケージと等価である。整数シフト規則を記憶するために必要な空間が、等価の置換コマンドを記憶するために必要な空間よりも小さい場合、等価の整数シフト規則を用いることによって更新パッケージのサイズを削減することができる。
【００７２】
更新パッケージのサイズは大幅に減少してもよい。例えば、セルラー電話機のソフトウェアのバージョンを更新する非限定的なアプリケーションを考えると、整数シフト規則は、時として、何万もの置換コマンドを節約することができる。
【００７３】
整数シフト規則を用いる代わりに、任意の数値シフト規則を同様に適用することができるため、以降「数値シフト規則」なる語を用いる。
【００７４】
図７は、本発明の一実施の形態による、更新パッケージにおける数値シフト規則の生成を詳細に説明するフローチャートである。更新パッケージおよび数値シフト規則を作成する場合、新旧２つのバージョン間の差分を検出するために、新旧バージョン間においてｄｉｆｆが利用される（７０１、既知の方法で）。ＵＮＩＸ（登録商標）のｄｉｆｆプログラムのように、バージョン間の差分を検出する利用可能なツールが現在多数ある。ｄｉｆｆは、新旧バージョン間の差分の対を生成し、これには置換対も含まれ得る。ｄｉｆｆが置換対を含む（７０２）場合、その幾つかがグループ化されて（７０３）ｄｉｆｆの一部分が形成され、これにより、例えば図６の部分６０１のような部分が形成される。次に（７０４）、置換対は、図４および図６（部分４０２および６０２を参照）を参照して前述した整数表記を用いて変換され、整数置換対が形成される。
【００７５】
置換対が整数置換対に変換された後、整数置換対は、変更前整数をその変更差分と関連付けることによって整数シフト対に変換（７０５）され、これは、図４（部分４０３）および図６（６０３）を参照して先に示したステージである。整数シフト対は、図６の部分６０４のように、変更差分に従ってソート（７０６）される。
【００７６】
ソート後、整数シフト対における変更前整数は、それぞれの参照される項目の表示値で置換（７０７）され、表示シフト対が形成され、これは、図６（部分６０５）を参照して先に例示したステージである。これらの場合において、同じ変更差分を有する表示シフト対が複数存在する場合（７０８）、これらの表示シフト対は、それぞれの表示値に応じてソートされる（７０９）ことに注意されたい。これらの場合において、整数全体を参照される項目の表示値として考える場合、ブロック７０７が冗長でありこれをスキップすることができ、一方、ｉｎｔ値を規則生成処理にわたってｉｎｄの代わりに用いることができる。図６のブロック６０６は、本図におけるブロック７０９の一例である。
【００７７】
同じ変更差分を有する表示シフト対を２つ以上含むグループが存在する場合、１グループにおける表示シフト対を結合して、図６（部分６０７を参照）を参照して先に説明したように、当該グループにおける最初および最後の参照される項目の表示値ならびにこれらを特徴付ける変更差分を示す数値シフト規則が形成される（７１０）。
【００７８】
時として、更なる最適化も適用可能である。例えば、同じ変更差分を有する２つの数値シフト規則が存在し、第１の規則の最後の参照される項目の表示値および第２の規則の最初の参照される項目の表示値が十分に近い場合、２つの規則を結合して１つの合成数値シフト規則が形成される。合成数値シフト規則は、第１の数値シフト規則の最初の参照される項目の表示値および第２の数値シフト規則の最後の参照される項目の表示値を、これらを特徴付ける変更差分と共に示す。２つの非調整数値シフト規則を結合した場合、それらの間の数値シフト規則（または表示シフト対）は結合された規則に吸収されるため、その変更前参照項目は誤った更新を起こしやすい（つまり、誤ったシフトを反映して更新される）ことに注意されたい。
【００７９】
本発明は、図７に説明される整数シフト規則を得るための特定のシーケンスの動作および方法、または図６の部分６０７で使用される整数シフト規則の語に制限されないことに注意されたい。
【００８０】
なお、これまで例示した実施の形態によると、数値シフト規則を用いることによって更新パッケージのサイズが低減され、コンパクトな更新パッケージが生成される。「ｄｉｆｆ」の「デルタ」または「差分」等の、更新パッケージの説明に異なる語が用いられる場合、コンパクトな更新パッケージは、例えば、「コンパクトな差分結果」と称してよい。
【００８１】
別の実施の形態では、時として、コンテンツは、以降「メタデータ」と称する、関連付けられた記述データを伴うことがある。一般に、メタデータは、コンピュータプログラムの記述に使用されるシンボルテーブル、デバッグテーブルおよびリンカーマップの形態で与えられる。しかし、メタデータは、コンピュータプログラムに制限されず、他のタイプのコンテンツもメタデータを有することができる。例えば、異なるファイルあるいはデータベースに記憶することで、関連するメタデータをコンテンツから分離できることに注意されたい。あるいは、この場合のように、メタデータをコンテンツの一部として記憶してもよい。
【００８２】
図８に、コンテンツの例およびこれに関連するメタデータを示す。コンテンツ８０１は、４個のブロック８０２、８０３、８０４および８０５を含む。ブロック８０３は、アドレスａｄｄｒ（８０３）から始まり、ブロック８０４は、ａｄｄｒ（８０４）から始まり、ブロック８０５は、ａｄｄｒ（８０５）から始まる。関連するメタデータ８０６は、コンテンツおよびそのブロックを記述し、メタデータ８０６は各ブロックに対し、ブロックの開始アドレス（start address）およびブロックの長さ（length）を提供する。しかし、これは非限定的な例であり、メタデータは、各ブロックの開始アドレスおよび長さの代わりに、他のデータを含んでもよい。
【００８３】
コンテンツの旧バージョンをその新バージョンに更新するための更新パッケージを生成する際に、メタデータがコンテンツと関連付けられている場合、図９および図１０を参照して以下に説明するように、参照に対する変更を符号化するためにメタデータを使用することができる。
【００８４】
旧バージョン９０１およびその更新から得られる新バージョン９０２の概略図である図９を参照するとともに、本発明の一実施の形態による図９の新旧バージョンに関連付けられるメタデータおよび差分テーブル（それぞれ９Ａ０３、９Ａ０４および１０００）の概略図である図９Ａを参照して、更に詳細に説明するように、図８の例および説明は、本発明の別の実施の形態によるいわゆる「参照シフト規則」をどのように得るかを理解するための基礎となる。
【００８５】
旧バージョン９０１は、４個のブロック（９０５、９０６、９０７および９０８）を含み、それぞれのアドレスはａｄｄｒ（９０５）、ａｄｄｒ（９０６）、ａｄｄｒ（９０７）およびａｄｄｒ（９０８）である。新バージョンでは、少なくとも１つの項目よりなる新しいブロック９０９がブロック９０５に追加され、対応するブロック９０５’が生成される。ブロック９０５’のサイズは、ｓｉｚｅ（９０９）だけブロック９０５のサイズより大きいことが分かる。なお、更新処理中にコンテンツへの項目の追加的な挿入またはコンテンツからの項目の削除が更に行われることのない限り、新しいブロック９０９の前方にある項目は、サイズ（９０９）分だけ前方にシフトされることとなる。
【００８６】
ブロック９０５’の前方では、ブロック９０６’がブロック９０６に対応し、ブロック９０７’がブロック９０７に対応し、ブロック９０８’がブロック９０８に対応する。１つ以上の項目よりなる新しいブロック９１０もブロック９０７’に挿入される。この新しいブロックのサイズはｓｉｚｅ（９１０）である。従って、新しい項目９１０の前方にある項目は、（ｓｉｚｅ（９０９）＋ｓｉｚｅ（９１０））分だけ前方にシフトされる。
【００８７】
旧バージョンでは、ブロック９０６は、項目９１４、９１５および９１６を参照する少なくとも３つの明示参照項目９１１、９１２および９１３を含む。参照される項目９１４はブロック９０８内にあり、参照される項目９１５はブロック９０７内にあり、参照される項目９１６はブロック９０６内にある。なお、ブロック９０８は、項目９１８を参照する少なくとも１つの明示参照項目９１７を含む。参照される項目９１５と同様に、参照される項目９１８もブロック９０７内にある。
【００８８】
旧バージョン９０１と関連付けられるメタデータ９Ａ０３は、４個のブロック、つまりそれぞれの開始アドレスおよび長さを記述する。新バージョン９０２と関連付けられるメタデータ９Ａ０４は、その中に含まれるブロックを記述する。メタデータ９Ａ０３とメタデータ９Ａ０４とを比較すると、この場合のブロック９０５’の開始アドレスが旧バージョンのブロック９０５のものと同様であることが分かる。しかしながら、ブロック９０６’の開始アドレスは（ａｄｄｒ（９０６）＋ｓｉｚｅ（９０９））に等しい。同様に、旧バージョンのブロック９０７の開始アドレスと比較されたとき、ブロック９０７’の開始アドレスもｓｉｚｅ（９０９）分のシフトを反映している、即ち、ａｄｄｒ（９０７’）＝ａｄｄｒ（９０７）＋ｓｉｚｅ（９０９）である。他方で、ブロック９０８’の開始アドレスは、（ｓｉｚｅ（９０９）＋ｓｉｚｅ（９１０））分のシフトを反映している、即ち、ａｄｄｒ（９０８’）＝ａｄｄｒ（９０８）＋ｓｉｚｅ（９０９）＋ｓｉｚｅ（９１０）である。
【００８９】
図９の具体的な例について参照シフト規則をどのように得るかを以下に説明するが、図９、図９Ａおよび図１０の例は非限定的であることに注意されたい。新旧バージョンは、任意の数のブロックを有することができ、旧バージョンから新バージョンへの更新の際に新たなブロックおよび項目が任意の場所に挿入されてもよいし、削除されてもよい。旧バージョンにおけるアドレスを用いるとともに、適用可能であれば、挿入されたブロックのサイズを追加することによって、新バージョンのメタデータ９Ａ０４を示すことができることが分かる。変更差分（つまり、旧バージョンにおける各ブロックおよび新バージョンにおける対応ブロックの開始アドレスを特徴付けるシフト）と共に、結果は「差分テーブル」として称される。これは、メタデータ９Ａ０３および９Ａ０４に対応する差分テーブルである１０００（図１０参照）に示される。
【００９０】
参照シフト規則が差分テーブル１０００に従って生成されることが分かる。例えば、参照項目がブロック９０６’中の別の項目を参照する場合、差分テーブルの情報に従って、新バージョンでは、その対応する参照項目が、参照される項目の場所におけるｓｉｚｅ（９０９）分のシフトを反映するよう変更されるべきであることが理解できる。同様に、第２の参照項目がブロック９０８’中の別の項目を参照する場合、新バージョンでは、その対応する参照項目が、参照される項目の場所におけるｓｉｚｅ（９０９）＋ｓｉｚｅ（９１０）分のシフトを反映するよう変更されるべきであることが理解できる。
【００９１】
従って、概して言えば、差分テーブルは、参照シフト規則を反映する。例えば、ブロック９０６’中の各参照される項目について、特徴的シフトはｓｉｚｅ（９０９）である。同様に、ブロック９０７’中の各参照される項目について、特徴的シフトはｓｉｚｅ（９０９）であり、ブロック９０８’中の各参照される項目について、特徴的シフトはｓｉｚｅ（９０９）＋ｓｉｚｅ（９１０）である。
【００９２】
差分テーブルに示されるブロックの開始アドレスおよび長さに従って、参照項目が他のブロックにおける別項目を参照するか否かを判定することができる。従って、参照シフト規則は、例示的な表記「ｍｏｄｉｆｙ  ＜ａｄｄｒ（参照されるブロック），ｓｉｚｅ（参照されるブロック）＞，シフト」によって表すことができる。
【００９３】
図９Ａの例では、ブロック９０６’および９０７’の両方が同じシフトによって特徴付けられていることが分かる。ブロック９０６’および９０７’が連続的であることが分かると、それぞれの２つの参照シフト規則を結合して、「ｍｏｄｉｆｙ  ＜ａｄｄｒ（９０６’），ｓｉｚｅ（９０６’）＋ｓｉｚｅ（９０７’）＞，ｓｉｚｅ（９０９）」と述べる１つの参照シフト規則を形成することができる。
【００９４】
図１０では、ブロック１００１は、差分テーブル１０００に基づく参照シフト規則を例示する。この場合、３つの参照シフト規則（１００２、１００３および１００４）が例示される。既知のとおり、メタデータがコンテンツの１つ以上のブロックを記述しない場合がある。例えば図９および図１１を参照する。図１１では、図９の旧バージョン９０１のメタデータ１１０１および図９の新バージョン９０２のメタデータ１１０２が例示される。メタデータ１１０１および１１０２は部分的であり、つまり、ブロック９０７およびその対応するブロック９０７’が記述されていないことが分かる。従って、図１２の差分テーブルにおいて、ブロック９０７’についての差分は示されない。これにより、１２０２に示される参照シフト規則の生成が影響を受ける。図９および図１０の例のように、本例において、３つの参照シフト規則１２０３、１２０４および１２０５が存在する。しかしながら、ブロック９０７’が示されていないため、第２の規則１２０４は、前の例の第２の規則１００３と比べてより小さいブロックに対応する。従って、ブロック９０７’中の別の項目を参照する参照項目は、この場合の参照シフト規則に従って変更することができない。
【００９５】
それでもなお、上述の図５、図６および図７を参照した数値シフト規則の記述に従って、当業者は、参照シフト規則を適用できない場所であればどこでも数値シフト規則を試して適用できることを理解することができる。数値シフト規則を利用する方法はメタデータを必要としないため、この場合は数値シフト規則が使用可能となる。
【００９６】
図１３は、本発明の一実施の形態による、更新パッケージにおける参照シフト規則の生成を詳細に説明するフローチャートである。新旧バージョンそれぞれのメタデータを受け取った（１３０１）後、差分テーブル（例えば、図１０の差分テーブル１０００）が形成される（１３０２）。差分テーブルは、新バージョンにおける対応ブロックに関する情報（例えば、開始アドレス）と関連付けられる、旧バージョンにおけるブロックに関する情報（例えば、開始アドレス）を少なくとも含む。または、差分テーブルは、それぞれの変更差分に関する情報（即ち、それぞれのシフト値）と関連付けられる、旧バージョンにおけるブロックに関する情報を少なくとも含む。他の例、例えば、それぞれの変更差分に関する情報と関連付けられる、新バージョンにおけるブロックに関する情報を少なくとも含むことも可能であることに注意されたい。
【００９７】
差分テーブルで記述される各ブロックについて、参照シフト規則が作成されている（１３０４）。次に、隣接するブロックに言及する参照シフト規則が結合される（１３０５）。本発明が図１３に説明されるような参照シフト規則を得るための特定のシーケンスの動作および方法に限定されないことに注意されたい。
【００９８】
また、参照シフト規則の記述に用いる表記も非限定的であり、他の表記も適用可能であることに注意されたい。例えば、規則の対象となるブロックあるいは複数のブロック（換言すれば「セクション」）の最初の項目および長さを指定する代わりに、セクションにおける最初および最後の項目を指定してもよい。後者は、必要な変更を加えて、図７を参照して説明された数値シフト規則にも当てはまることに注意されたい。
【００９９】
上の説明は、旧バージョンから新バージョンへの更新の際に参照項目における参照を更新する数値シフト規則および参照シフト規則を生成するための実施の形態を説明している。本発明は、上述の特定の数値シフト規則および参照シフト規則によって制限されないことに注意すべきである。より一般的には、「シフト規則」なる語は、新バージョンにおける参照項目のシフトを反映するよう参照項目を更新するものを意味する。
【０１００】
以降、「変換子」なる語が、更新パッケージと関連付けられるシフト規則の集合に言及するのに用いられる。つまり、変換子は、少なくとも１つの数値シフト規則および／または少なくとも１つの参照シフト規則ならびに／もしくは旧バージョンから新バージョンへの更新の際に適用できる他のシフト規則を含むことができる。従って、上述の説明によると、当業者には、少なくとも１つの変換子を含む更新パッケージがコンパクトな更新パッケージであることは明らかである。
【０１０１】
旧バージョンに変換子を適用した場合、参照項目が誤って更新されることがある。例えば、挿入された項目９１０が項目９１５’の後方のブロック９０７に挿入された、図９に示す例を考える。この例における変化は、差分テーブル１０００に影響を与えず、参照シフト規則は図１０に説明されたものと同様である（ブロック１００１を参照）。しかしながら、項目９１５’および９１８’が、差分テーブル１０００から予想されるように、ｓｉｚｅ（９０９）ではなく、（ｓｉｚｅ（９０９）＋ｓｉｚｅ（９１０）分だけ前方にシフトされることが分かる。従って、ブロック１００１の参照シフト規則によって示されるものとは違って、参照項目９１２’および９１７’は、ｓｉｚｅ（９０９）ではなく（ｓｉｚｅ（９０９）＋ｓｉｚｅ（９１０）分のシフトを反映するように変更される必要がある。
【０１０２】
以降「変更された」実施の形態と称する本発明の一実施の形態によると、図１０のブロック１００１の参照シフト規則を含む変換子を適用でき、それにより変更バージョンが生成され、その後、変更バージョンおよび新バージョンの間にｄｉｆｆユーティリティを適用することによってこの変換子によって影響を受けた誤った参照項目の改善方法が提供される。このｄｉｆｆ処理は、時として単に「ｄｉｆｆ」と称されるが、変更バージョンと新バージョンとを比較するものであり、「変更ｄｉｆｆ」と称される。変換子の生成に利用される第１のｄｉｆｆ（旧バージョンと新バージョンとを比較する）は「完全ｄｉｆｆ」と称される。完全ｄｉｆｆの出力を「完全デルタ」と称し、変更ｄｉｆｆの出力を「変更デルタ」と称する。
【０１０３】
概して言えば、完全ｄｉｆｆは、例えば、置換対（即ち、上述のようにシフトされた明示参照項目）ならびに挿入された項目および削除された項目等の変動を含み新旧バージョン間に存在する全ての変動を検出する一方で、変更ｄｉｆｆは、誤っている可能性のある置換対および他の変動とともに、実質的により少ない置換を検出する。従って、変更デルタは、完全なデルタよりもサイズが小さい。
【０１０４】
変換子を有する変更デルタは、旧バージョンを更新しその新バージョンを作成することができる更新パッケージを構成する。少なくとも１つの変換子および変更デルタよりなる出力パッケージを、以降「合成更新パッケージ」と称する。これは、完全なデルタを含み変換子を含まない「単純な更新パッケージ」とは異なる。変換子がその対応する置換コマンドと比べてサイズが小さいことを念頭におくと、結果として生ずる合成更新パッケージは、既知の単純な更新パッケージと比べて通常、サイズが小さい。従って、合成更新パッケージは、以降コンパクトな更新パッケージとみなされる。本発明の実施の形態によると、コンパクトな更新パッケージは、少なくとも変換子およびそれと関連付けられる変更デルタを含む。
【０１０５】
コンパクトな更新パッケージにおいて、変更子を適用し、その後これに関連付けられる変更ｄｉｆｆを適用すること（「順変換順序（forward conversion order）」、換言すれば「順方向更新表示（forward update indicator）」）によって、新バージョンが生成されることが分かる。新バージョンにおいては、変換子によって誤って変更された項目は、変更デルタによって置換され、新バージョンにおける正しいコンテンツが受け取られるように補正される（更新パッケージを適用する手順は以下に詳細に説明する）。しかしながら、時として、変更ｄｉｆｆは、変更子の前に適用されるべきであり、これを以降「逆変換順序（backward conversion order）」と称する。逆変換順序を以下に詳細に説明する。
【０１０６】
コンパクトな更新パッケージを形成するために変更デルタを変換子に結合する代わりに、変更デルタから追加の変換子を抜き出すことができ、これにより、前の変換子に寄与することができ、または、前の変更子およびデルタに関連付けられる追加的な変換子を生成してよりコンパクトな更新パッケージを形成することができる。以下、「繰り返し形態（iterations embodiment）」と称する本発明の別の実施の形態を、図１４を参照して説明する。
【０１０７】
図１４は、本発明の繰り返し形態による、コンテンツのバージョンを更新するための繰り返しの例示的な概略図である。バージョン１４０１は旧バージョンであり、バージョン１４０２は新バージョンである。同図は、本発明の繰り返し形態による、旧バージョン１４０１を新バージョン１４０２に更新するコンパクトな更新パッケージの生成を示す。旧バージョン１４０１は、ブロック１４０３を含む。ブロック１４０３に続いて、少なくとも幾らかの明示参照項目１４０５、１４０６、１４０７、１４０８、１４０９、１４１０、１４１１、１４１２、１４１３および１４１４を含む別のブロック１４０４が存在する。ブロック１４０４は、非参照項目１４１５も含む。
【０１０８】
新バージョン１４０２において、ブロック１４０３’および１４０４’は、ブロック１４０３および１４０４に対応し、項目１４０５’、１４０６’、１４０７’、１４０８’、１４０９’、１４１０’、１４１１’、１４１２’、１４１３’、１４１４’および１４１５’はそれぞれ項目１４０５、１４０６、１４０７、１４０８、１４０９、１４１０、１４１１、１４１２、１４１３、１４１４および１４１５に対応する。少なくとも１つの項目１４１６がブロック１４０３’に挿入され、これによりｓｉｚｅ（１４１６）分だけサイズが拡大され、ｓｉｚｅ（１４１７）の少なくとも１つの項目１４１７が項目１４０５’の後方でブロック１４０４’に挿入される。
【０１０９】
参照項目１４０５、１４１１および１４１４のコンテンツが略同一であるため、対応する参照項目１４０５’、１４１１’および１４１４’のコンテンツも略同一であることに注意する。同様に、項目１４０６、１４１２および１４１４のコンテンツが略同一であるため、対応する参照項目１４０６’、１４１２’および１４１４’のコンテンツも略同一である。
【０１１０】
項目１４０５’、１４０６’、・・・、１４１０’は、明示参照項目であり、そのコンテンツは旧バージョンと比べて、新バージョンにおいて変更される（即ち、参照される項目がシフトされる）。同じことが明示参照項目１４１１’、１４１２’、１４１３’および１４１４’にもいえる。既知のｄｉｆｆユーティリティは、項目１４１７が新バージョン１４０２に挿入された新しい項目で、項目１４０５’、１４０６’、・・・、１４１０’がシフトされた項目であることを認識することができないため、ｄｉｆｆユーティリティは、項目１４１７が項目１４０５を置換したものであると誤検出する。更に、ｄｉｆｆユーティリティは、項目１４１５’が項目１４１５と同一（従って、そのコピー）であると識別し、項目１４１１’が項目１４１１を置換する等と（今回は正しく）検出するよう同期化する。
【０１１１】
従って、完全ｄｉｆｆに続いて、次のことを（部分的に誤って）示す完全なデルタが生成される：
項目１４１７は項目１４０５の置き換え；
項目１４０５’は項目１４０６の置き換え；
項目１４０６’は項目１４０７の置き換え；
項目１４０７’は項目１４０８の置き換え；
項目１４０８’は項目１４０９の置き換え；
項目１４０９’は項目１４１０の置き換え；
項目１４１５’は項目１４１５のコピー；
項目１４１１’は項目１４１１の置き換え；
項目１４１２’は項目１４１２の置き換え；
項目１４１３’は項目１４１３の置き換え；および
項目１４１４’は項目１４１４の置き換え。
【０１１２】
変換子は、完全なデルタに基づいて、例えば、図７および図１３に示される方法に従って生成される。
【０１１３】
項目１４０５、１４１１および１４１４が略同一（従ってその対応する項目も同一）であること、更に、項目１４０６、１４１２および１４１４も略同一（従ってその対応する項目も同一）であることを考慮すると、項目１４１１’が項目１４１１の置き換えであり項目１４１３’が項目１４１３の置き換えであることを検出した時に、変換子は、項目１４０５が項目１４０５’によって置き換えられるべきと推定することができる。同様に、項目１４１２’が項目１４１２の置き換えであり項目１４１４’が項目１４１４の置き換えであることを検出した時、変換子は、項目１４０６が項目１４０６’によって置き換えられるべきと推定することができる。
【０１１４】
この変換子は、旧バージョン１４０１に適用され、変更バージョン１４１８が生成される。旧バージョン１４０１における複数の項目が変換子によって変更（または変換）されているが、項目の削除および／または挿入等の全ての変動を扱うことに注意されたい。従って、変更バージョン１４１８は、旧バージョン１４０１に対してシフトされたものではない。
【０１１５】
本発明の変更された実施の形態によれば、変更バージョン１４１８と新バージョン１４０２とを比較する変更ｄｉｆｆが利用される。結果として生じる変更デルタは、追加的な変換子の挿入、他の変換子の削除、および残り（中でも変換子によって扱われない項目１４０７、１４０８、１４０９および１４１０）の置換を認識する。この変更デルタは、変換子と共に、コンパクトな更新パッケージを生成するための基礎をなす。
【０１１６】
あるいは、本発明の繰り返し形態によると、変更デルタは、コンパクトな更新パッケージを生成する代わりに、例えば、図７および図１３に示される方法に従って、追加的な新しい変換子を生成するための基礎をなす。この新しい変換子は、前の繰り返しにおいて生成された変換子と共に複合変換子を構成する。新しい変換子は、変更バージョン１４１８に適用され、変更ｄｉｆｆによって新バージョン１４０２に対して比較されるべき別の変更バージョン（図示せず）が生成される。繰り返しを停止させるための終了条件の一例は、繰り返しによって生成された変更デルタのサイズを、新しい変換子のサイズと合わせたときに、前の変更デルタのサイズを前の複合変換子のサイズと合わせたもの以上であることである。繰り返しが停止されると、コンパクトな更新パッケージが、複合変換子および変更デルタに基づいて生成される。
【０１１７】
繰り返し形態を、全般的に、図１５のフローチャートに関して以下に説明するが、図１４の例は非限定的であることに注意されたい。新旧バージョンは、任意の適用可能な数のブロックを有することができ、旧バージョンから新バージョンへの更新の際、新たなブロックおよび項目を任意の場所に挿入することができ、または削除することができる。繰り返しは任意の回数実行することができ、任意の適用可能な終了条件（または「停止基準」）を繰り返しを停止するのに用いてよい。つまり、この処理は、停止基準が満たされなければ次の繰り返しに進む。
【０１１８】
図１５は、本発明の繰り返し形態を詳細に説明するフローチャートである。このフローチャートに従って生成された更新パッケージは順変換順序であることに注意する。
【０１１９】
開始時、記載された方法は、更新されるべきコンテンツの少なくとも新旧のバージョンと、可能であればメタデータと、を受け取る。これら２つのバージョンとメタデータとは、変換子の生成（１５０１）および初期デルタのサイズの決定（１５０２）の基礎をなすものである。ここで、最初は、複合変換子は１５０１において生成された変換子と同一（１５０３）であることが分かる。変換子は、旧バージョンに適用（１５０４）され、これにより変更バージョンが生成される。次に、変更バージョンと新バージョンとに対して変更ｄｉｆｆを利用しつつ変更デルタが生成（１５０５）され、変更デルタは、新しい変換子を生成（１５０６）するための基礎をなす。この新しい変換子のサイズが決定（１５０７）される。
【０１２０】
新しい変換子は、統合され複合変換子となる（１５０８）。新しい変換子のサイズが決定（１５０９）され、変更デルタのサイズが決定（１５１０）される。
【０１２１】
複合変換子のサイズをデルタのサイズと合わせたものが新しい変換子のサイズを変更デルタのサイズと合わせたものよりも小さい場合（１５１１）、新しい変換子が変換子となり（１５１２）、デルタのサイズが新しいデルタのサイズとなり（１５１３）、新しい変換子が変更バージョンに適用され（１５１４）、これにより新しい変更バージョンが生成される。１５０５に戻り、新しい変更デルタが作成される。
【０１２２】
しかしながら、１５１１において、変更子のサイズを変更デルタのサイズと合わせたものが複合変換子のサイズをデルタのサイズと合わせたもの以上であると判定された場合、更新パッケージは、複合変換子と変更デルタとに基づいて生成される（１５１５）。あるいは、１５１１において、コンパクトな更新パッケージが前の繰り返しにおいて生成されたコンパクトな更新パッケージより大きい場合、停止基準が満たされる。
【０１２３】
繰り返し形態は、逆変換順序で動作させることもできる。即ち、初期の変換子を生成するために完全ｄｉｆｆを旧バージョンと新バージョンとの間に適用し、変換子を新バージョンに適用して、変更バージョンを生成してもよい。次に、新しい変換子を生成する等のために変更デルタが旧バージョンと新バージョンとの間に生成される。
【０１２４】
更新パッケージは、生成された更新パッケージに従って変換順序を示すためにマーキングされる。
【０１２５】
本発明は、図１５に説明された更新パッケージを生成する特定のシーケンスの動作および方法に限定されないことに注意されたい。
【０１２６】
本発明の様々な非限定的な実施の形態による更新パッケージの生成を説明したが、新バージョンを生じさせるよう旧バージョンを更新する更新パッケージを以下に説明する。非限定的な例として、更新パッケージは、無線通信媒体を介して送信され、セルラー電話装置によって受信される。セルラー電話装置は、プロセッサを有し、このプロセッサは、受信した更新パッケージを処理し、プログラムの旧バージョンおよび／またはそこに記憶されているデータを更新して、セルラー電話装置に記憶され動作可能である新バージョンを生じさせるよう構成される。
【０１２７】
これを念頭において、本発明の一実施の形態による、コンテンツの新バージョンを生じさせる、コンテンツの旧バージョンの更新について説明するフローチャートを示す図１６を参照する。本実施の形態による更新パッケージは、変換子および変更デルタを含む。更新パッケージが順方向更新表示または逆方向更新表示のいずれかを含むことに注意されたい。
【０１２８】
コンパクトな更新パッケージを取得（１６０１）した後、そこに含まれる変換子が抽出される（１６０２）。
【０１２９】
更新パッケージが、１６０３で検出されるように、順方向更新表示を含む場合、変換子が旧バージョンに適用（１６０４）され、変更バージョンが生成される。そして、変更デルタが、更新パッケージから抽出（１６０５）され、変更バージョンに適用（１６０６）される。一方、１６０３および１６０７において、更新パッケージが逆方向更新表示を含むと判断された場合、変更デルタが、最初に抽出され（１６０５）、旧バージョンに適用（１６０６）され、そして、変更バージョンを生成した旧バージョンに変換子が適用（１６０８）される。いずれの場合も、新バージョンが結果として生成される。
【０１３０】
図１７は、本発明の一実施の形態による、コンテンツの旧バージョンおよびコンテンツの新バージョンの間のコンパクトな更新パッケージを生成するシステム１７０１を例示する。システム１７０１は、旧バージョンおよび新バージョンに関連付けられる変換子を生成する変換子生成部１７０２と、旧バージョンに変換子を適用して変更バージョンを生成する変更バージョン生成部１７０３と、コンパクトな更新パッケージを生成する更新パッケージ生成部１７０４と、を含む。コンパクトな更新パッケージは、変換子、ならびに変更バージョンおよび新バージョンに基づく変更デルタを含む。
【０１３１】
図１８は、本発明の一実施の形態による、コンテンツの旧バージョンを更新してコンテンツの新バージョンを生じさせるシステム１８０１を例示する。システム１８０１は、入力モジュール１８０２およびプロセッサ１８０３を含む。
【０１３２】
入力モジュール１８０２は、上記旧バージョンおよび新バージョンと関連付けられる変換子、変更デルタ、ならびに順方向更新または逆方向更新の表示を含む、コンパクトな更新パッケージを得るよう構成される。順方向更新表示の場合、プロセッサ１８０３は、旧バージョンに変換子を適用して変更バージョンを生成するよう構成される。また、プロセッサ１８０３は、変更バージョンに変更デルタを適用して新バージョンを生成するよう構成される。逆方向更新表示の場合、プロセッサ１８０３は、旧バージョンに変更デルタを適用して変更バージョンを生成するよう構成される。また、プロセッサ１８０３は、変更バージョンに変換子を適用して新バージョンを生成するよう構成される。
【０１３３】
本発明によるシステムは適切にプログラムされたコンピュータでもよいことが分かるであろう。同様に、本発明は、本発明の方法を実行するコンピュータによって読み取り可能なコンピュータプログラムを考慮したものである。更に、本発明は、本発明の方法を実行する機械によって実行可能な命令のプログラムを明白に具現化する機械読み取り可能なメモリを考慮したものである。
【０１３４】
本発明は、ある程度の具体性をもって説明されたが、当業者には、後続の特許請求の範囲から逸脱することなく様々な変化および変更を行えることが容易に理解されるであろう。
【図面の簡単な説明】
【０１３５】
【図１】本発明の一実施の形態による、セルラーネットワークにおいてバージョンの更新を行うシステムの概略図である。
【図２】コンテンツの旧バージョンを新バージョンに更新するよう構成された更新パッケージの概略図である。
【図３】本発明の一実施の形態による、項目を表す整数値の概略図である。
【図４】本発明の一実施の形態による、整数表記法を用いた図２の更新パッケージの一部分を示す図である。
【図５】本発明の一実施の形態による、旧バージョンおよびその更新より得られる新バージョンの概略図である。
【図６】図５の旧バージョンを新バージョンに更新するために使用される更新パッケージの一部分を示す。
【図７】本発明の一実施の形態による、更新パッケージにおける数値シフト規則の生成を詳細に説明するフローチャートである。
【図８】本発明の一実施の形態による、例示的なコンテンツおよび関連するメタデータを示す。
【図９】本発明の一実施の形態による、旧バージョンおよびその更新から得られる新バージョンの概略図である。
【図９Ａ】本発明の一実施の形態による、図９の旧バージョンおよび新バージョンと関連付けられるメタデータの概略図である。
【図１０】本発明の一実施の形態による、図９の例に応じた差分テーブルおよびその対応する参照シフト規則を示す。
【図１１】本発明の一実施の形態による、図９の新旧バージョンと関連付けられる部分的なメタデータの概略図である。
【図１２】本発明の一実施の形態による、図９および図１１の例に応じた差分テーブルおよびその対応する参照シフト規則を示す。
【図１３】本発明の一実施の形態による、更新パッケージにおける参照シフト規則の生成を詳細に説明するフローチャートである。
【図１４】本発明の繰り返し形態による、コンテンツのバージョンを更新する繰り返しの概略図である。
【図１５】本発明の繰り返し形態を詳細に説明するフローチャートである。
【図１６】コンテンツの新バージョンを生じさせる、コンテンツの旧バージョンの更新を説明するフローチャートである。
【図１７】本発明の一実施の形態による、コンテンツの旧バージョンとコンテンツの新バージョンとの間のコンパクトな更新パッケージを生成するシステムを示す。
【図１８】本発明の一実施の形態による、コンテンツの旧バージョンを更新してコンテンツの新バージョンを生成するシステムを示す。
【図１】
2007521555.tif 000003
【図２】
2007521555.tif 000004
【図３】
2007521555.tif 000005
【図４】
2007521555.tif 000006
【図５】
2007521555.tif 000007
【図６】
2007521555.tif 000008
【図７】
2007521555.tif 000009
【図８】
2007521555.tif 000010
【図９】
2007521555.tif 000011
【図９Ａ】
2007521555.tif 000012
【図１０】
2007521555.tif 000013
【図１１】
2007521555.tif 000014
【図１２】
2007521555.tif 000015
【図１３】
2007521555.tif 000016
【図１４】
2007521555.tif 000017
【図１５】
2007521555.tif 000018
【図１６】
2007521555.tif 000019
【図１７】
2007521555.tif 000020
【図１８】
2007521555.tif 000021
【国際調査報告】
2007521555.tif 000022
2007521555.tif 000023
2007521555.tif 000024