(57)【要約】【課題】データ更新システムにおいて、データ更新に用いる差分データのデータ量を削減する。【解決手段】差分データの生成時に、Ｍｏｖｅ／Ａｄｄ決定手段３５によって、更新前ファイルから更新後ファイルへ移動してコピーするＭｏｖｅ命令を表すＭｏｖｅデータと、データを追加してコピーするＡｄｄ命令を表すＡｄｄデータとのいずれを生成するかを決定する。この際、一致データ列検索手段３４で更新前ファイルと更新後ファイルとで一致するデータを検索し、コピーすべきデータ列の長さが５バイト以上の場合はＭｏｖｅデータ出力手段３６よりＭｏｖｅデータとして出力し、４バイト以下の場合はＡｄｄデータ出力手段３７よりＡｄｄデータとして出力して、これらのＭｏｖｅデータとＡｄｄデータとを組み合わせた差分データを生成する。また、ＭｏｖｅデータのＭｏｖｅサイズ及びＭｏｖｅアドレスは可変長ビットにより表現する。これにより、差分データのデータ量を小さくする。【選択図】  図１０
2004152136.tif 000002
【特許請求の範囲】
【請求項１】
複数のバージョンのデータを持ち、１つのバージョンのデータである更新前ファイルと他のもう１つのバージョンのデータである更新後ファイルとの差を示す差分データを生成する差分データ生成手段と、
前記差分データを転送する通信手段と、
前記差分データを受信し、すでに保持している更新前ファイルと受信した前記差分データとを元に更新後ファイルを復元する更新後ファイル復元手段とを有するデータ更新システムであって、
前記差分データとして、前記更新前ファイルの一部、あるいは全部からデータを移動してコピーすることを意味する０個、１個、あるいは複数のＭｏｖｅ命令を表すＭｏｖｅデータと、当該差分データ中のデータを追加してコピーすることを意味する０個、１個、あるいは複数のＡｄｄ命令を表すＡｄｄデータとを有して構成される差分データを用いたデータ更新システム。
【請求項２】
前記差分データにおいて、前記Ｍｏｖｅデータの長さが所定の閾値未満となる場合はＭｏｖｅデータではなくＡｄｄデータによって構成した請求項１に記載のデータ更新システム。
【請求項３】
前記差分データにおいて、前記Ｍｏｖｅデータは、コピーを行うデータ列の長さを表すデータ長情報と、コピーを行うデータ列の位置を表すアドレス情報とを有し、前記データ長情報と前記アドレス情報の少なくとも一方を可変ビット長で構成した請求項１に記載のデータ更新システム。
【請求項４】
前記差分データにおいて、前記Ｍｏｖｅデータは、コピーを行うデータ列の長さを表すデータ長情報と、コピーを行うデータ列の位置を表すアドレス情報とを有し、前記アドレス情報として前記データ列の移動のための相対アドレスを用い、同一の相対アドレス値が複数のＭｏｖｅデータにおいて現れる場合に該当する１つまたは複数の相対アドレス値を１つまたは複数のビットで表現するように構成した請求項１に記載のデータ更新システム。
【請求項５】
１つのバージョンのデータである更新前ファイルと他のもう１つのバージョンのデータである更新後ファイルとの差を示す差分データを生成し、前記差分データを通信手段を介して他所へ転送し、転送先で保持している更新前ファイルと前記差分データとを元に更新後ファイルを復元するデータ更新システムにおける差分データ生成装置であって、
前記更新後ファイル中のデータ列と一致するデータ列を前記更新前ファイルから検索する一致データ列検索手段と、
前記検索結果に基づき、前記差分データとして、前記更新前ファイルの一部、あるいは全部から一致するデータ列を前記更新後ファイルへ移動してコピーすることを意味するＭｏｖｅ命令を表すＭｏｖｅデータと、当該差分データ中のデータ列を前記更新後ファイルへ追加してコピーすることを意味するＡｄｄ命令を表すＡｄｄデータとのいずれを生成するかを決定するＭｏｖｅ／Ａｄｄ決定手段と、
前記Ｍｏｖｅデータを出力するＭｏｖｅデータ出力手段と、
前記Ａｄｄデータを出力するＡｄｄデータ出力手段とを備え、
０個、１個、あるいは複数の前記Ｍｏｖｅデータと０個、１個、あるいは複数の前記Ａｄｄデータとを有して構成される差分データを生成する差分データ生成装置。
【請求項６】
前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータの開始を示す特定のデータからなる区切り子を出力する区切り子出力手段を備え、前記区切り子の後に前記Ｍｏｖｅ命令を表現するデータを出力する請求項５に記載の差分データ生成装置。
【請求項７】
前記Ａｄｄデータ出力手段は、前記Ａｄｄデータ中に前記区切り子として用いられる特定のデータが存在する場合に、このデータに続けて区切り子ではないことを示す特定のデータを出力する請求項５に記載の差分データ生成装置。
【請求項８】
前記Ｍｏｖｅ／Ａｄｄ決定手段は、前記一致するデータ列の長さが所定の閾値以上となる場合は前記Ｍｏｖｅデータ出力手段よりＭｏｖｅデータとして出力し、前記一致するデータ列の長さが所定の閾値未満となる場合は前記Ａｄｄデータ出力手段よりＡｄｄデータとして出力するように決定する請求項５に記載の差分データ生成装置。
【請求項９】
前記Ｍｏｖｅ／Ａｄｄ決定手段における閾値として、３２ビットＣＰＵを用いた計算システムにおけるプログラム及びデータを転送するデータ更新システムに用いる場合に、閾値を５バイトとする請求項８に記載の差分データ生成装置。
【請求項１０】
前記Ｍｏｖｅ／Ａｄｄ決定手段における閾値として、１つのバージョンの更新前ファイルと１つのバージョンの更新後ファイルとの間の差分データを生成する際に、異なる複数の閾値を用いて差分データ生成を実行し、大きさが最小となった場合の差分データを採用する請求項８に記載の差分データ生成装置。
【請求項１１】
前記Ｍｏｖｅ／Ａｄｄ決定手段は、前記一致するデータ列について、前記Ｍｏｖｅデータで表現した場合と前記Ａｄｄデータで表現した場合とにおける差分データの大きさを比較し、より小さくなる方に決定する請求項５に記載の差分データ生成装置。
【請求項１２】
前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータの先頭バイトまたはワードにおいて１つあるいは複数のビットからなるデータ長継続フラグを設け、
前記データ長継続フラグが所定の状態１を取っている場合は当該バイトまたはワードにおける情報のみによって前記更新前ファイルよりコピーを行うデータ列の長さを表現し、前記データ長継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいて前記データ列の長さを表現する情報が継続することとしたデータ長情報を出力する請求項５に記載の差分データ生成装置。
【請求項１３】
前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータの２番目以降のバイトまたはワードにおいて１つあるいは複数のビットからなるデータ長継続フラグを設け、
前記データ長継続フラグが所定の状態１を取っている場合は前記Ｍｏｖｅデータの先頭バイトまたはワードから当該バイトまたはワードまでにおける情報によって前記更新前ファイルよりコピーを行うデータ列の長さを表現し、前記データ長継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいて前記データ列の長さを表現する情報が継続することとしたデータ長情報を出力する請求項１２に記載の差分データ生成装置。
【請求項１４】
前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルと前記更新後ファイルの少なくとも一方における絶対アドレスを用いたアドレス情報を出力する請求項５に記載の差分データ生成装置。
【請求項１５】
前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差を示す相対アドレスを用いたアドレス情報を出力する請求項５に記載の差分データ生成装置。
【請求項１６】
前記Ｍｏｖｅデータ出力手段及び前記Ａｄｄデータ出力手段は、前記更新後ファイルにおけるデータ列の順番に沿ってＭｏｖｅデータ及びＡｄｄデータを生成出力するものとし、
前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルにおける当該データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いたアドレス情報を出力する請求項５に記載の差分データ生成装置。
【請求項１７】
前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータ中の前記相対アドレスによるアドレス情報のデータ列の先頭バイトまたはワードにおいて１つあるいは複数のビットからなるアドレス継続フラグを設け、
前記アドレス継続フラグが所定の状態１を取っている場合は当該バイトまたはワードにおける情報のみによって前記相対アドレスを表現し、前記アドレス継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいて前記相対アドレスを表現する情報が継続することとしたアドレス情報を出力する請求項１５または１６に記載の差分データ生成装置。
【請求項１８】
前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータ中の前記相対アドレスによるアドレス情報のデータ列の２番目以降のバイトまたはワードにおいて１つあるいは複数のビットからなるアドレス継続フラグを設け、
前記アドレス継続フラグが所定の状態１を取っている場合は前記アドレス情報のデータ列の先頭バイトまたはワードから当該バイトまたはワードまでにおける情報によって前記相対アドレスを表現し、前記アドレス継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいて前記相対アドレスを表現する情報が継続することとしたアドレス情報を出力する請求項１７に記載の差分データ生成装置。
【請求項１９】
前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータのアドレス情報において、同一の相対アドレス値が複数のＭｏｖｅデータにおいて現れる場合に、該当する１つまたは複数の相対アドレス値については前記Ｍｏｖｅデータの先頭バイトまたはワードにおいて１つあるいは複数のビットで表現することとした請求項１５または１６に記載の差分データ生成装置。
【請求項２０】
前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の位置を表す情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差、または前記更新前ファイルにおける前記データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いたアドレス情報を出力するものとし、
前記Ｍｏｖｅデータ中において１つあるいは複数のビットからなるアドレス変化フラグを設け、
前記アドレス変化フラグが所定の状態１を取っている場合は前記データ列の長さを表現するデータ長情報の後に前記相対アドレスによるアドレス情報を出力し、前記アドレス変化フラグが前記状態１とは異なる所定の状態２を取っている場合は前回のＭｏｖｅデータにおける相対アドレスと今回のＭｏｖｅデータにおける相対アドレスとが同一であるとして前記相対アドレスを表現する情報を省略する請求項５に記載の差分データ生成装置。
【請求項２１】
前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータのアドレス情報における相対アドレスを、前回のＭｏｖｅデータにおける相対アドレスからの変化量により表現することとした請求項１５，１６，２０のいずれかに記載の差分データ生成装置。
【請求項２２】
請求項５〜２１のいずれかに記載のデータ更新システムの差分データ生成装置における各手段の機能をコンピュータにより実現するための差分データ生成プログラム。
【請求項２３】
１つのバージョンのデータである更新前ファイルと他のもう１つのバージョンのデータである更新後ファイルとの差を示す差分データを受信し、自装置で保持している更新前ファイルと前記差分データとを元に更新後ファイルを復元するデータ更新システムにおける更新後ファイル復元装置であって、
前記差分データが、前記更新前ファイルの一部、あるいは全部から一致するデータ列を前記更新後ファイルへ移動してコピーすることを意味するＭｏｖｅ命令を表すＭｏｖｅデータと、当該差分データ中のデータ列を前記更新後ファイルへ追加してコピーすることを意味するＡｄｄ命令を表すＡｄｄデータとのいずれであるかを判定するＭｏｖｅ／Ａｄｄ判定手段と、
前記Ｍｏｖｅデータに対応するデータ列を出力するＭｏｖｅデータ復元手段と、
前記Ａｄｄデータに対応するデータ列を出力するＡｄｄデータ復元手段とを備え、
前記差分データより更新後ファイルを生成する更新後ファイル復元装置。
【請求項２４】
前記Ｍｏｖｅ／Ａｄｄ判定手段は、前記差分データにおいて、特定のデータからなる区切り子の後に設けられたＭｏｖｅ命令を表現するデータをＭｏｖｅデータとし、前記差分データの先頭または前回のＭｏｖｅデータの終端から前記区切り子が出現するまでに設けられたＡｄｄ命令を表現するデータをＡｄｄデータとして区別する請求項２３に記載の更新後ファイル復元装置。
【請求項２５】
前記Ｍｏｖｅ／Ａｄｄ判定手段は、前記差分データにおいて、前記区切り子がデータ列中に現れ、かつ前記区切り子に続くデータが特定のものである場合は、前記区切り子ではなく、前記Ａｄｄデータ中に存在する区切り子として用いられたデータそのものであるとする請求項２４に記載の更新後ファイル復元装置。
【請求項２６】
前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータに設けられるデータ長情報を判別して前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の長さを決定するものであり、
前記Ｍｏｖｅデータの先頭バイトまたはワードにおいて１つあるいは複数のビットからなるデータ長継続フラグを検出し、
前記データ長継続フラグが所定の状態１を取っている場合は当該バイトまたはワードにおける情報よりデータ長情報を判別して前記コピーを行うデータ列の長さを決定し、前記データ長継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいても前記データ長情報が継続するものと判定する請求項２３に記載の更新後ファイル復元装置。
【請求項２７】
前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータの２番目以降のバイトまたはワードにおいて１つあるいは複数のビットからなるデータ長継続フラグを検出し、
前記データ長継続フラグが所定の状態１を取っている場合は前記Ｍｏｖｅデータの先頭バイトまたはワードから当該バイトまたはワードまでにおける情報よりデータ長情報を判別して前記コピーを行うデータ列の長さを決定し、前記データ長継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいても前記データ長情報が継続するものと判定する請求項２６に記載の更新後ファイル復元装置。
【請求項２８】
前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータに設けられるアドレス情報を判別して前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を決定するものであり、
前記アドレス情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差、または前記更新前ファイルにおける前記データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスにより表現されたアドレス情報を判別する請求項２３に記載の更新後ファイル復元装置。
【請求項２９】
前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータ中の前記相対アドレスによるアドレス情報のデータ列の先頭バイトまたはワードにおいて１つあるいは複数のビットからなるアドレス継続フラグを検出し、
前記アドレス継続フラグが所定の状態１を取っている場合は当該バイトまたはワードにおける情報より前記相対アドレスのアドレス情報を判別して前記コピーを行うデータ列の位置を決定し、前記アドレス継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいても前記アドレス情報が継続するものと判定する請求項２８に記載の更新後ファイル復元装置。
【請求項３０】
前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータ中の前記相対アドレスによるアドレス情報のデータ列の２番目以降のバイトまたはワードにおいて１つあるいは複数のビットからなるアドレス継続フラグを検出し、
前記アドレス継続フラグが所定の状態１を取っている場合は前記アドレス情報のデータ列の先頭バイトまたはワードから当該バイトまたはワードにおける情報より前記相対アドレスのアドレス情報を判別して前記コピーを行うデータ列の位置を決定し、前記アドレス継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいても前記アドレス情報が継続するものと判定する請求項２９に記載の更新後ファイル復元装置。
【請求項３１】
前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータ中において１つあるいは複数のビットで表現されたアドレス情報を判別し、このアドレス情報に該当する１つまたは複数の相対アドレス値については同一の相対アドレス値として前記コピーを行うデータ列の位置を決定する請求項２８に記載の更新後ファイル復元装置。
【請求項３２】
前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータ中において１つあるいは複数のビットからなるアドレス変化フラグを検出し、
前記アドレス変化フラグが所定の状態１を取っている場合は前記コピーを行うデータ列の長さを表すデータ長情報の後に設けられる前記相対アドレスによるアドレス情報を判別し、前記アドレス変化フラグが前記状態１とは異なる所定の状態２を取っている場合は前回のＭｏｖｅデータにおける相対アドレスと同一の相対アドレスを用いて前記コピーを行うデータ列の位置を決定する請求項２８に記載の更新後ファイル復元装置。
【請求項３３】
請求項２３〜３２のいずれかに記載のデータ更新システムの更新後ファイル復元装置における各手段の機能をコンピュータにより実現するための更新後ファイル復元プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一つのバージョンのデータを別のバージョンのデータに更新するためのデータ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラムに関する。
【０００２】
【従来の技術】
パーソナルコンピュータ、携帯情報端末（ＰＤＡ）、携帯電話機など、所定のプログラムに基づくプロセッサの動作によって装置動作の少なくとも一部を実行する端末装置では、プログラムの改良などのために、対象のプログラムを含むデータのバージョンを更新する、いわゆるバージョンアップが行われることがある。このようなデータのバージョン更新時には、フラッシュＲＯＭ、ハードディスクなどの書換可能な記録媒体に記録された更新前のソフトウェア等のデータ（以下、更新前ファイルと称する）が、他のバージョン（一般には新しいバージョン）のソフトウェア等のデータ（以下、更新後ファイルと称する）に書き換えられる。この場合、単純に更新前ファイルを更新後ファイルに置き換えることもできるが、更新前ファイルと更新後ファイルとの差分データを生成し、この差分データをを基に更新前ファイルから更新後ファイルを生成して書き換えることも従来より多く行われている。
【０００３】
従来の差分データ生成方法の一例を図２４及び図２５を参照して説明する。図２４は従来の差分データ生成部の機能構成を示すブロック図、図２５は従来の差分データ生成手順を示すフローチャートである。ここでは、Ｗａｌｔｅｒ  Ｆ．  Ｔｉｃｈｙ  が提案したＢｌｏｃｋ−Ｍｏｖｅアルゴリズムを用いた差分データ生成方法を示す。この方法は、更新前ファイルのデータと更新後ファイルのデータとを比較して一致するデータ列を検索し、一致するデータ列はそのまま更新前ファイルから更新後ファイルへＭｏｖｅデータとして移動するようにしてコピーし、一致しないデータ列は新たなデータ列をＡｄｄデータとして追加して書き込むことで、差分データを生成するものである（非特許文献１参照）。
【０００４】
差分データ生成部は、差分データを生成する各手順の制御を司る差分データ生成制御手段５０１、更新前ファイルのデータを記憶する更新前データ記憶手段５０２、更新後ファイルのデータを記憶する更新後データ記憶手段５０３、更新前ファイルと更新後ファイルとで一致するデータ列を検索する一致データ列検索手段５０４を備えている。また、更新前後で一致するデータ列をＭｏｖｅデータとして出力するＭｏｖｅデータ出力手段５０５、更新前後で一致しないデータ列をＡｄｄデータとして出力するＡｄｄデータ出力手段５０６、ＭｏｖｅデータとＡｄｄデータとを組み合わせた差分データを記憶する差分データ記憶手段５０７を備えている。Ｍｏｖｅデータ出力手段５０５は、ＡｄｄデータとＭｏｖｅデータとの区切りを示す区切り子（デリミタ）を出力するデリミタ出力手段５１１、Ｍｏｖｅデータのサイズを出力するＭｏｖｅサイズ出力手段５１２、Ｍｏｖｅデータが位置する更新前ファイル及び更新後ファイル上のアドレスを出力するＭｏｖｅアドレス出力手段５１３を備えている。
【０００５】
この従来例では、まず一致データ列検索手段５０４によって、更新前データ記憶手段５０２に記憶された更新前ファイルと更新後データ記憶手段５０３に記憶された更新後ファイルのデータ列を参照し、更新前ファイルの中から更新後ファイルのデータ列と一致するデータ列を先頭から検索する（ステップＳ５０１）。そして、一致するデータ列があるか否かによって処理手順を分岐し（ステップＳ５０２）、一致するデータ列がある場合はＭｏｖｅデータ出力手段５０５によって以降のＭｏｖｅデータ出力手順を実行する。
【０００６】
Ｍｏｖｅデータとしては、まずデリミタ出力手段５１１によって、以降のデータがＭｏｖｅデータであることを示す所定のデータからなるデリミタを出力し（ステップＳ５０３）、次にＭｏｖｅサイズ出力手段５１２によって、Ｍｏｖｅデータのサイズとして一致するデータ列のサイズを出力し（ステップＳ５０４）、続いてＭｏｖｅアドレス出力手段５１３によって、Ｍｏｖｅデータのアドレスとして一致するデータ列の更新前ファイル及び更新後ファイル上でのアドレスを出力する（ステップＳ５０５）。このように一致するデータ列のサイズとアドレスとを用いることによって、更新前ファイルから更新後ファイルへコピーするデータ列を指定することができる。
【０００７】
ステップＳ５０２において一致するデータ列が無い場合は、Ａｄｄデータ出力手段５０６によってそのデータ列をＡｄｄデータとして出力する（ステップＳ５０６）。そして、全データについて処理が終了したかを判断し（ステップＳ５０７）、終了していない場合はステップＳ５０１に戻り、更新後ファイルの終端まで全データ分の処理が終了するまでステップＳ５０１〜Ｓ５０６の処理を繰り返す。以上の手順により、更新前ファイルと更新後ファイルとの差分を表す差分データが生成され、差分データ記憶手段５０７に記憶される。
【０００８】
【非特許文献１】
Ｗａｌｔｅｒ  Ｆ．  Ｔｉｃｈｙ，  「Ｔｈｅ  Ｓｔｒｉｎｇ−ｔｏ−Ｓｔｒｉｎｇ  Ｃｏｒｒｅｃｔｉｏｎ  Ｐｒｏｂｒｅｍ  ｗｉｔｈ  Ｂｌｏｃｋ  Ｍｏｖｅｓ」，  ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍｓ，  ＡＣＭ  （Ａｓｓｏｃｉａｔｉｏｎ  ｆｏｒ  Ｃｏｍｐｕｔｉｎｇ  Ｍａｃｈｉｎｅｒｙ），  １９８４年１１月，第２巻，第４号，ｐ．３０９−３２１
【０００９】
【発明が解決しようとする課題】
プログラム等を含むファイルのデータを更新するために、更新前ファイルと更新後ファイルとの差分データを用いることによって、更新のために必要なデータ容量を削減することができる。このとき、差分データを更新対象の端末装置に転送し、この端末装置において更新前ファイルと差分データとから更新後ファイルを復元することによって、更新の際に転送するデータ量を小さくできる。この差分データは上記従来例のような方法によって生成することが可能である。
【００１０】
しかしながら、大がかりなプログラム変更等によって多量のデータ変更が発生した場合は、差分データであってもデータサイズが巨大化し、差分データをネットワーク等の通信回線を介して転送する場合に通信回線における負荷（トラフィック）が増大したり、端末装置の演算回路等における負荷が増大してしまう。これにより、差分データの転送や更新後データへの書き換えに長い時間がかかったり、通信回線のコストが増加するなどの問題点が生じることがあった。特に無線通信による移動体通信システムを用いてデータの更新を行う場合などは、通信回線の容量や端末装置のメモリの容量などに制約が多いため、差分データについてさらなるデータ量の削減が求められている。
【００１１】
本発明は、上記課題を解決するためになされたもので、その目的は、データ更新に用いる差分データのデータ量を削減することが可能なデータ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラムを提供することにある。
【００１２】
【課題を解決するための手段】
本発明は、第１に、複数のバージョンのデータを持ち、１つのバージョンのデータである更新前ファイルと他のもう１つのバージョンのデータである更新後ファイルとの差を示す差分データを生成する差分データ生成手段と、前記差分データを転送する通信手段と、前記差分データを受信し、すでに保持している更新前ファイルと受信した前記差分データとを元に更新後ファイルを復元する更新後ファイル復元手段とを有するデータ更新システムであって、前記差分データとして、前記更新前ファイルの一部、あるいは全部からデータを移動してコピーすることを意味する０個、１個、あるいは複数のＭｏｖｅ命令を表すＭｏｖｅデータと、当該差分データ中のデータを追加してコピーすることを意味する０個、１個、あるいは複数のＡｄｄ命令を表すＡｄｄデータとを有して構成される差分データを用いたデータ更新システムを提供する。
【００１３】
また、第２に、前記第１の構成において、前記差分データにおいて、前記Ｍｏｖｅデータの長さが所定の閾値未満となる場合はＭｏｖｅデータではなくＡｄｄデータによって構成したものとする。
【００１４】
また、第３に、前記第１の構成において、前記差分データにおいて、前記Ｍｏｖｅデータは、コピーを行うデータ列の長さを表すデータ長情報と、コピーを行うデータ列の位置を表すアドレス情報とを有し、前記データ長情報と前記アドレス情報の少なくとも一方を可変ビット長で構成したものとする。
【００１５】
また、第４に、前記第１の構成において、前記差分データにおいて、前記Ｍｏｖｅデータは、コピーを行うデータ列の長さを表すデータ長情報と、コピーを行うデータ列の位置を表すアドレス情報とを有し、前記アドレス情報として前記データ列の移動のための相対アドレスを用い、同一の相対アドレス値が複数のＭｏｖｅデータにおいて現れる場合に該当する１つまたは複数の相対アドレス値を１つまたは複数のビットで表現するように構成したものとする。
【００１６】
本発明は、第５に、１つのバージョンのデータである更新前ファイルと他のもう１つのバージョンのデータである更新後ファイルとの差を示す差分データを生成し、前記差分データを通信手段を介して他所へ転送し、転送先で保持している更新前ファイルと前記差分データとを元に更新後ファイルを復元するデータ更新システムにおける差分データ生成装置であって、前記更新後ファイル中のデータ列と一致するデータ列を前記更新前ファイルから検索する一致データ列検索手段と、前記検索結果に基づき、前記差分データとして、前記更新前ファイルの一部、あるいは全部から一致するデータ列を前記更新後ファイルへ移動してコピーすることを意味するＭｏｖｅ命令を表すＭｏｖｅデータと、当該差分データ中のデータ列を前記更新後ファイルへ追加してコピーすることを意味するＡｄｄ命令を表すＡｄｄデータとのいずれを生成するかを決定するＭｏｖｅ／Ａｄｄ決定手段と、前記Ｍｏｖｅデータを出力するＭｏｖｅデータ出力手段と、前記Ａｄｄデータを出力するＡｄｄデータ出力手段とを備え、０個、１個、あるいは複数の前記Ｍｏｖｅデータと０個、１個、あるいは複数の前記Ａｄｄデータとを有して構成される差分データを生成する差分データ生成装置を提供する。
【００１７】
また、第６に、前記第５の構成において、前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータの開始を示す特定のデータからなる区切り子を出力する区切り子出力手段を備え、前記区切り子の後に前記Ｍｏｖｅ命令を表現するデータを出力するものとする。
【００１８】
また、第７に、前記第５の構成において、前記Ａｄｄデータ出力手段は、前記Ａｄｄデータ中に前記区切り子として用いられる特定のデータが存在する場合に、このデータに続けて区切り子ではないことを示す特定のデータを出力するものとする。
【００１９】
また、第８に、前記第５の構成において、前記Ｍｏｖｅ／Ａｄｄ決定手段は、前記一致するデータ列の長さが所定の閾値以上となる場合は前記Ｍｏｖｅデータ出力手段よりＭｏｖｅデータとして出力し、前記一致するデータ列の長さが所定の閾値未満となる場合は前記Ａｄｄデータ出力手段よりＡｄｄデータとして出力するように決定するものとする。
【００２０】
また、第９に、前記第８の構成において、前記Ｍｏｖｅ／Ａｄｄ決定手段における閾値として、３２ビットＣＰＵを用いた計算システムにおけるプログラム及びデータを転送するデータ更新システムに用いる場合に、閾値を５バイトとするものとする。
【００２１】
また、第１０に、前記第８の構成において、前記Ｍｏｖｅ／Ａｄｄ決定手段における閾値として、１つのバージョンの更新前ファイルと１つのバージョンの更新後ファイルとの間の差分データを生成する際に、異なる複数の閾値を用いて差分データ生成を実行し、大きさが最小となった場合の差分データを採用するものとする。
【００２２】
また、第１１に、前記第５の構成において、前記Ｍｏｖｅ／Ａｄｄ決定手段は、前記一致するデータ列について、前記Ｍｏｖｅデータで表現した場合と前記Ａｄｄデータで表現した場合とにおける差分データの大きさを比較し、より小さくなる方に決定するものとする。
【００２３】
また、第１２に、前記第５の構成において、前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータの先頭バイトまたはワードにおいて１つあるいは複数のビットからなるデータ長継続フラグを設け、前記データ長継続フラグが所定の状態１を取っている場合は当該バイトまたはワードにおける情報のみによって前記更新前ファイルよりコピーを行うデータ列の長さを表現し、前記データ長継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいて前記データ列の長さを表現する情報が継続することとしたデータ長情報を出力するものとする。
【００２４】
また、第１３に、前記第１２の構成において、前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータの２番目以降のバイトまたはワードにおいて１つあるいは複数のビットからなるデータ長継続フラグを設け、前記データ長継続フラグが所定の状態１を取っている場合は前記Ｍｏｖｅデータの先頭バイトまたはワードから当該バイトまたはワードまでにおける情報によって前記更新前ファイルよりコピーを行うデータ列の長さを表現し、前記データ長継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいて前記データ列の長さを表現する情報が継続することとしたデータ長情報を出力するものとする。
【００２５】
また、第１４に、前記第５の構成において、前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルと前記更新後ファイルの少なくとも一方における絶対アドレスを用いたアドレス情報を出力するものとする。
【００２６】
また、第１５に、前記第５の構成において、前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差を示す相対アドレスを用いたアドレス情報を出力するものとする。
【００２７】
また、第１６に、前記第５の構成において、前記Ｍｏｖｅデータ出力手段及び前記Ａｄｄデータ出力手段は、前記更新後ファイルにおけるデータ列の順番に沿ってＭｏｖｅデータ及びＡｄｄデータを生成出力するものとし、前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルにおける当該データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いたアドレス情報を出力するものとする。
【００２８】
また、第１７に、前記第１５または１６の構成において、前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータ中の前記相対アドレスによるアドレス情報のデータ列の先頭バイトまたはワードにおいて１つあるいは複数のビットからなるアドレス継続フラグを設け、前記アドレス継続フラグが所定の状態１を取っている場合は当該バイトまたはワードにおける情報のみによって前記相対アドレスを表現し、前記アドレス継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいて前記相対アドレスを表現する情報が継続することとしたアドレス情報を出力するものとする。
【００２９】
また、第１８に、前記第１７の構成において、前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータ中の前記相対アドレスによるアドレス情報のデータ列の２番目以降のバイトまたはワードにおいて１つあるいは複数のビットからなるアドレス継続フラグを設け、前記アドレス継続フラグが所定の状態１を取っている場合は前記アドレス情報のデータ列の先頭バイトまたはワードから当該バイトまたはワードまでにおける情報によって前記相対アドレスを表現し、前記アドレス継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいて前記相対アドレスを表現する情報が継続することとしたアドレス情報を出力するものとする。
【００３０】
また、第１９に、前記第１５または１６の構成において、前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータのアドレス情報において、同一の相対アドレス値が複数のＭｏｖｅデータにおいて現れる場合に、該当する１つまたは複数の相対アドレス値については前記Ｍｏｖｅデータの先頭バイトまたはワードにおいて１つあるいは複数のビットで表現することとする。
【００３１】
また、第２０に、前記第５の構成において、前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の位置を表す情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差、または前記更新前ファイルにおける前記データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いたアドレス情報を出力するものとし、前記Ｍｏｖｅデータ中において１つあるいは複数のビットからなるアドレス変化フラグを設け、前記アドレス変化フラグが所定の状態１を取っている場合は前記データ列の長さを表現するデータ長情報の後に前記相対アドレスによるアドレス情報を出力し、前記アドレス変化フラグが前記状態１とは異なる所定の状態２を取っている場合は前回のＭｏｖｅデータにおける相対アドレスと今回のＭｏｖｅデータにおける相対アドレスとが同一であるとして前記相対アドレスを表現する情報を省略するものとする。
【００３２】
また、第２１に、前記第１５，１６，２０のいずれかの構成において、前記Ｍｏｖｅデータ出力手段は、前記Ｍｏｖｅデータのアドレス情報における相対アドレスを、前回のＭｏｖｅデータにおける相対アドレスからの変化量により表現することとする。
【００３３】
本発明は、第２２に、前記第５〜２１のいずれかの構成のデータ更新システムの差分データ生成装置における各手段の機能をコンピュータにより実現するための差分データ生成プログラムを提供する。
【００３４】
本発明は、第２３に、１つのバージョンのデータである更新前ファイルと他のもう１つのバージョンのデータである更新後ファイルとの差を示す差分データを受信し、自装置で保持している更新前ファイルと前記差分データとを元に更新後ファイルを復元するデータ更新システムにおける更新後ファイル復元装置であって、前記差分データが、前記更新前ファイルの一部、あるいは全部から一致するデータ列を前記更新後ファイルへ移動してコピーすることを意味するＭｏｖｅ命令を表すＭｏｖｅデータと、当該差分データ中のデータ列を前記更新後ファイルへ追加してコピーすることを意味するＡｄｄ命令を表すＡｄｄデータとのいずれであるかを判定するＭｏｖｅ／Ａｄｄ判定手段と、前記Ｍｏｖｅデータに対応するデータ列を出力するＭｏｖｅデータ復元手段と、前記Ａｄｄデータに対応するデータ列を出力するＡｄｄデータ復元手段とを備え、前記差分データより更新後ファイルを生成する更新後ファイル復元装置を提供する。
【００３５】
また、第２４に、前記第２３の構成において、前記Ｍｏｖｅ／Ａｄｄ判定手段は、前記差分データにおいて、特定のデータからなる区切り子の後に設けられたＭｏｖｅ命令を表現するデータをＭｏｖｅデータとし、前記差分データの先頭または前回のＭｏｖｅデータの終端から前記区切り子が出現するまでに設けられたＡｄｄ命令を表現するデータをＡｄｄデータとして区別するものとする。
【００３６】
また、第２５に、前記第２４の構成において、前記Ｍｏｖｅ／Ａｄｄ判定手段は、前記差分データにおいて、前記区切り子がデータ列中に現れ、かつ前記区切り子に続くデータが特定のものである場合は、前記区切り子ではなく、前記Ａｄｄデータ中に存在する区切り子として用いられたデータそのものであるとする。
【００３７】
また、第２６に、前記第２３の構成において、前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータに設けられるデータ長情報を判別して前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の長さを決定するものであり、前記Ｍｏｖｅデータの先頭バイトまたはワードにおいて１つあるいは複数のビットからなるデータ長継続フラグを検出し、前記データ長継続フラグが所定の状態１を取っている場合は当該バイトまたはワードにおける情報よりデータ長情報を判別して前記コピーを行うデータ列の長さを決定し、前記データ長継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいても前記データ長情報が継続するものと判定することとする。
【００３８】
また、第２７に、前記第２６の構成において、前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータの２番目以降のバイトまたはワードにおいて１つあるいは複数のビットからなるデータ長継続フラグを検出し、前記データ長継続フラグが所定の状態１を取っている場合は前記Ｍｏｖｅデータの先頭バイトまたはワードから当該バイトまたはワードまでにおける情報よりデータ長情報を判別して前記コピーを行うデータ列の長さを決定し、前記データ長継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいても前記データ長情報が継続するものと判定することとする。
【００３９】
また、第２８に、前記第２３の構成において、前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータに設けられるアドレス情報を判別して前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を決定するものであり、前記アドレス情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差、または前記更新前ファイルにおける前記データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスにより表現されたアドレス情報を判別するものとする。
【００４０】
また、第２９に、前記第２８の構成において、前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータ中の前記相対アドレスによるアドレス情報のデータ列の先頭バイトまたはワードにおいて１つあるいは複数のビットからなるアドレス継続フラグを検出し、前記アドレス継続フラグが所定の状態１を取っている場合は当該バイトまたはワードにおける情報より前記相対アドレスのアドレス情報を判別して前記コピーを行うデータ列の位置を決定し、前記アドレス継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいても前記アドレス情報が継続するものと判定することとする。
【００４１】
また、第３０に、前記第２９の構成において、前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータ中の前記相対アドレスによるアドレス情報のデータ列の２番目以降のバイトまたはワードにおいて１つあるいは複数のビットからなるアドレス継続フラグを検出し、前記アドレス継続フラグが所定の状態１を取っている場合は前記アドレス情報のデータ列の先頭バイトまたはワードから当該バイトまたはワードにおける情報より前記相対アドレスのアドレス情報を判別して前記コピーを行うデータ列の位置を決定し、前記アドレス継続フラグが前記状態１とは異なる所定の状態２を取っている場合は当該バイトまたはワード以降にある１つまたは複数のバイトまたはワードにおいても前記アドレス情報が継続するものと判定することとする。
【００４２】
また、第３１に、前記第２８の構成において、前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータ中において１つあるいは複数のビットで表現されたアドレス情報を判別し、このアドレス情報に該当する１つまたは複数の相対アドレス値については同一の相対アドレス値として前記コピーを行うデータ列の位置を決定するものとする。
【００４３】
また、第３２に、前記第２８の構成において、前記Ｍｏｖｅデータ復元手段は、前記Ｍｏｖｅデータ中において１つあるいは複数のビットからなるアドレス変化フラグを検出し、前記アドレス変化フラグが所定の状態１を取っている場合は前記コピーを行うデータ列の長さを表すデータ長情報の後に設けられる前記相対アドレスによるアドレス情報を判別し、前記アドレス変化フラグが前記状態１とは異なる所定の状態２を取っている場合は前回のＭｏｖｅデータにおける相対アドレスと同一の相対アドレスを用いて前記コピーを行うデータ列の位置を決定するものとする。
【００４４】
本発明は、第３３に、前記第２３〜３２のいずれかの構成のデータ更新システムの更新後ファイル復元装置における各手段の機能をコンピュータにより実現するための更新後ファイル復元プログラムを提供する。
【００４５】
上記構成によれば、差分データ生成時のＭｏｖｅデータとＡｄｄデータのいずれを生成するかの閾値の設定、Ｍｏｖｅデータにおけるサイズとアドレスの可変ビット長表現、Ｍｏｖｅデータにおいて同一のアドレスが存在する場合のアドレス情報の省略などによって、差分データのデータ量を削減することが可能となる。これにより、データを転送する通信手段における負荷、及びデータを処理する装置の演算回路等における負荷やメモリ消費量などを軽減することが可能となる。
【００４６】
【発明の実施の形態】
以下、図面を参照して本発明の実施形態を説明する。
本実施形態では、データ更新システムの一例として、携帯電話機等の携帯端末装置に格納されている動作プログラム等を含むデータのバージョンを更新する場合の構成及び動作の例を説明する。本実施形態は、差分データを移動体通信システムの無線通信網を介して携帯端末装置へ転送することによって、通信回線経由で容易に携帯端末装置内のデータを更新可能にしたものである。
【００４７】
図１は本発明の一実施形態に係るデータ更新システムの機能構成を示すブロック図である。データ更新システムは、更新前ファイル及び更新後ファイルから差分データを生成する差分データ生成手段の機能を有する差分データ生成装置１１と、差分データを転送するサーバ１２と、サーバ１２と無線通信網１３を介して接続され前記差分データ及び更新前ファイルから更新後ファイルを復元する更新後ファイル復元手段の機能を有する携帯端末装置１４とを備えて構成される。なお本実施形態では、サーバ１２及び無線通信網１３等によって通信手段が構成される。
【００４８】
差分データ生成装置１１は、更新前ファイル及び更新後ファイルとなる複数のバージョンのデータを格納したデータベース１５と、データベース１５に格納された更新前ファイルと更新後ファイルとから後述する手順により差分データを生成する差分データ生成部１６とを有して構成される。サーバ１２は、移動体通信システムにおいて各種データの配信などを行うために設けられるもので、対象となる携帯端末装置１４へ差分データを送信するようになっている。
【００４９】
携帯端末装置１４は、無線通信により各種データや音声信号等の送受信を行う無線通信部１７と、各部の動作制御を行う制御部１８と、転送された差分データと更新前ファイルとから後述する手順により更新後ファイルを復元して生成する更新後ファイル復元部１９と、更新後ファイルを格納するフラッシュＲＯＭ等からなるデータ格納部２０とを有して構成される。
【００５０】
上記構成のデータ更新システムにおいて、差分データ生成装置１１により更新前ファイルと更新後ファイルとから差分データを生成し、この差分データをサーバ１２より無線通信網１３を介して携帯端末装置１４に転送する。携帯端末装置１４では、更新後ファイル復元部１９によってサーバ１２より転送された差分データと現在格納している更新前ファイルとから更新後ファイルを復元し、この更新後ファイルをデータ格納部２０に格納する。これにより、携帯端末装置１４を使用者が使用している状態であっても、適当なタイミングで無線通信網１３を介して差分データを転送することによって、容易に動作プログラム等のバージョンを更新することが可能となる。
【００５１】
ここで、本実施形態における差分データの生成、及び更新後ファイルの復元についての概要を説明する。図２は本実施形態における差分データの生成方法の概略を示す説明図である。差分データの生成時には、図２（Ａ）に示す更新前ファイルと図２（Ｂ）に示す更新後ファイルとから差分抽出を行って図２（Ｃ）に示す差分データを生成する。この場合、更新後ファイルのデータ列において更新前ファイルのデータ列と一致する部分を検索し、一致するデータ列については、更新前ファイルからコピーするための一致部分のサイズ（データ長情報）とアドレス（アドレス情報）により示されるＭｏｖｅデータを生成する。また、一致しないデータ列については、そのデータ列を書き込むためのＡｄｄデータを生成する。
【００５２】
本実施形態では、更新前ファイル内のデータ列の一部を移動（コピー）してきて更新後ファイルの一部を生成する操作をＭｏｖｅ操作と呼び、このＭｏｖｅ操作の内容を記述したデータをＭｏｖｅデータと呼ぶ。また、更新前ファイルを参照せずにデータ列を追加することで更新後ファイルの一部を生成する操作をＡｄｄ操作と呼び、このＡｄｄ操作の内容を記述したデータをＡｄｄデータと呼ぶ。差分データは、ＭｏｖｅデータとＡｄｄデータとの組み合わせによって構成され、更新後ファイルを復元する際のＭｏｖｅ命令及びＡｄｄ命令として用いられる。すなわち、差分データは、０個、１個、あるいは複数のＭｏｖｅ命令を表すＭｏｖｅデータと、０個、１個、あるいは複数のＡｄｄ命令を表すＡｄｄデータとを有して構成される。
【００５３】
図２の例では、更新前ファイルのアドレスｑ３から更新後ファイルのアドレスｐ１へ４バイトコピー（「ａ，ｂ，ｃ，ｄ」をコピー）するためのＭｏｖｅデータ、次に「ｅ，ｆ，ｇ，ｈ」を書き込むためのＡｄｄデータ、次に更新前ファイルのアドレスｑ２から更新後ファイルのアドレスｐ２へ３バイトコピー（「ｘ，ｙ，ｚ」をコピー）するためのＭｏｖｅデータ、次に「ｉ，ｊ，ｋ，ｌ，ｍ」を書き込むためのＡｄｄデータが生成される。
【００５４】
図３は本実施形態における更新後ファイルの復元方法の概略を示す説明図である。更新後ファイルの復元時には、図３（Ａ）に示す差分データと図３（Ｂ）に示す更新前ファイルとから図３（Ｃ）に示す更新後ファイルを生成する。この場合、差分データにおけるＭｏｖｅデータによるＭｏｖｅ命令とＡｄｄデータによるＡｄｄ命令とに基づいて、更新前ファイルから一致するデータ列がコピーされて移動され、一致しない新たなデータ列が書き込まれて追加される。
【００５５】
図３の例では、まず▲１▼でＭｏｖｅ命令により更新前ファイルのアドレスｑ３から更新後ファイルのアドレスｐ１へ４バイトコピー（「ａ，ｂ，ｃ，ｄ」がコピー）され、次に▲２▼でＡｄｄ命令により「ｅ，ｆ，ｇ，ｈ」が書き込まれ、次に▲３▼でＭｏｖｅ命令により更新前ファイルのアドレスｑ２から更新後ファイルのアドレスｐ２へ３バイトコピー（「ｘ，ｙ，ｚ」がコピー）され、次に▲４▼でＡｄｄ命令により「ｉ，ｊ，ｋ，ｌ，ｍ」が書き込まれる。以上のようにして、Ｍｏｖｅデータ及びＡｄｄデータからなる差分データを用いて更新前ファイルから更新後ファイルが復元生成される。
【００５６】
本実施形態では、差分データにおいて以下に述べる特徴を持たせることによって、差分データのデータ量を削減している。
【００５７】
（１）一致するデータ列が所定長未満の場合、ＭｏｖｅデータではなくＡｄｄデータにする。Ｍｏｖｅデータにおいてサイズとアドレスを何バイトで表現するかにも関係するが、小さいデータ列の移動に関するＭｏｖｅデータは、データそのものが示されるＡｄｄデータよりもデータ量が大きくなってしまう場合がある。本実施形態では、例えば閾値を５バイトとし、この閾値未満、すなわち一致する部分が４バイト以下のデータ列についてはＡｄｄデータとして差分データを生成してデータ量を小さくする。
【００５８】
（２）Ｍｏｖｅデータにおいて、サイズとアドレスをそれぞれ可変ビット長で表現する。可変ビット長とすることにより、小さい値の場合は小さいデータ量で表現することが可能である。なお、サイズとアドレスの少なくとも一方のみを可変ビット長で表現してもよい。本実施形態では、アドレスについては相対アドレスを使用し、更新前ファイル上でのアドレスを基準として更新後ファイルにおけるアドレスの変化量（相対移動距離）を表すこととする。
【００５９】
（３）Ｍｏｖｅデータにおいて、アドレスに相対アドレスを用いた場合、当該アドレスが直前のＭｏｖｅデータにおけるアドレス（相対移動距離）と同じ場合はアドレスを省略する。本実施形態では、更新後ファイルのデータ列を先頭から順に復元するように差分データを形成するものとする。このため、直前のＭｏｖｅデータのアドレスと同じ場合、すなわちコピーするデータ列の相対移動距離が同じで平行移動状態でコピーする場合は、直前のデータ列の後に続けてコピーすれば良いことになる。この場合、同一のアドレスを省略することによってデータ量を小さくする。
【００６０】
なお、同一のアドレスが複数出現する場合、フラグ等によって前回と同一のアドレスであることを示したり、出現頻度の高い１つまたは複数のアドレスを１つまたは複数のビットで表現するようにしてデータ量を削減することも可能である。
【００６１】
前記相対アドレスとしては、更新前ファイルにおけるコピーすべきデータ列の位置（先頭及び／または終端）と更新後ファイルにおける当該データ列の位置（先頭及び／または終端）との差を示す相対アドレスを用いることができる。この場合、複数のＭｏｖｅデータについて更新後ファイルにおけるデータ列の位置が前後したりランダムに並んでいても対応可能である。また、更新後ファイルのデータ列を先頭から順に復元するように、更新後ファイルにおけるデータ列の順番に沿ってＭｏｖｅデータ及びＡｄｄデータを生成して差分データを構成する場合は、更新前ファイルにおけるコピーすべきデータ列の先頭位置と更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いることができる。本実施形態ではこの相対アドレスを採用する。この場合、上記の同一アドレスの省略についても対応可能である。さらに、相対アドレスは、前回のＭｏｖｅデータにおける相対アドレスからの変化量により表現することも可能である。
【００６２】
次に、差分データのフォーマットの一例を示す。図４に示すように、差分データにおけるＭｏｖｅデータは、Ｍｏｖｅデータの開始を示す区切り子であるデリミタ１０１と、コピーすべきデータ列のサイズを示すデータ長情報が格納されるサイズフィールド１０２と、コピーすべきデータ列の相対アドレスを示すアドレス情報が格納されるアドレスフィールド１０３との３つの要素から構成される。
【００６３】
デリミタ１０１は、サイズは１バイトで０ｘ０Ｆ（２進表記で００００１１１１）を用いることとする。本明細書では、０ｘ＊＊は１６進表記を示すものとする。なお、デリミタは複数バイトで表現したり、１ないし複数のビットやワードで表現することも可能である。
【００６４】
サイズフィールド１０２は、コピーすべきデータ列のサイズ（以下、Ｍｏｖｅサイズと称する場合もある）を格納する可変長のフィールドであり、１〜３バイトで構成される。このサイズフィールド１０２について、図５（Ａ）に示すように３バイトを順にＡ，Ｂ，Ｃとし、各バイトを図５（Ｂ），（Ｃ），（Ｄ）に示すように表して詳細を説明する。
【００６５】
図５（Ｂ）に示す１バイト目のバイトＡにおいて、１番目のビットＡ８はデータ長継続フラグに相当するフィールド長フラグ１１１、２番目のビットＡ７はアドレス変化フラグ１１２となっている。以降のビットＡ６〜Ａ１にはＭｏｖｅサイズの最下位６ビットが入る。ビットＡ８のフィールド長フラグ１１１の値により、次のバイトもサイズフィールドであるかが示される。ビットＡ８が「１（フラグが立っている状態、以下同様）」であれば次のバイトもサイズフィールドであり、「０（フラグが寝ている状態、以下同様）」であればサイズフィールドはバイトＡのみとなる。また、ビットＡ７のアドレス変化フラグ１１２の値により、サイズフィールドの次にアドレスフィールドが続くかどうかが示される。ビットＡ７が「１」であればサイズフィールドの次にアドレスフィールドが続き、「０」であればアドレスフィールドが無く、直前のＭｏｖｅ操作時と同じアドレスであるものとする。
【００６６】
図５（Ｃ）に示す２バイト目のバイトＢにおいて、１番目のビットＢ８はバイトＡと同様にデータ長継続フラグに相当するフィールド長フラグ１１１となっている。以降のビットＢ７〜Ｂ１にはＭｏｖｅサイズの第１３ビット〜第７ビットが入る。また、図５（Ｄ）に示す３バイト目のバイトＣについても同様に、１番目のビットＣ８はフィールド長フラグ１１１となっており、以降のビットＣ７〜Ｃ１にはＭｏｖｅサイズの第２０ビット〜第１４ビットが入る。ビットＢ８，Ｃ８のフィールド長フラグ１１１の値により、次のバイトもサイズフィールドであるかが示され、値が「１」であれば次のバイトもサイズフィールドであり、「０」であればサイズフィールドはそのバイトまでとなる。
【００６７】
このサイズフィールド１０２の具体例を図６に示す。この図６の例は、Ｍｏｖｅサイズが３バイトで表され、そのサイズの値は３３８２６バイトであり、２番目のビットのアドレス変化フラグ１１２が「０」であるためアドレスフィールドが後に続かないことが示されている。なお、フィールド長フラグ１１１やアドレス変化フラグ１１２は、複数のビットで表現してもよい。また、フラグの「０」「１」は反対の状態を表現するようにしてもよい。
【００６８】
アドレスフィールド１０３は、コピーすべきデータ列の相対アドレス（以下、Ｍｏｖｅアドレスと称する場合もある）を格納する可変長のフィールドであり、１〜３バイトで構成される。このアドレスフィールド１０３は前記サイズフィールド１０２のアドレス変化フラグ１１２が「１」の場合に設けられる。このアドレスフィールド１０３について、図７（Ａ）に示すように３バイトを順にＸ，Ｙ，Ｚとし、各バイトを図７（Ｂ），（Ｃ），（Ｄ）に示すように表して詳細を説明する。
【００６９】
図７（Ｂ）に示す１バイト目のバイトＸにおいて、１番目のビットＸ８はアドレス継続フラグに相当するフィールド長フラグ１２１、２番目のビットＸ７はアドレス符号ビット１２２となっている。以降のビットＸ６〜Ｘ１にはＭｏｖｅアドレスの絶対値の最下位６ビットが入る。ビットＸ８のフィールド長フラグ１２１の値により、次のバイトもアドレスフィールドであるかが示される。ビットＸ８が「１」であれば次のバイトもアドレスフィールドであり、「０」であればアドレスフィールドはバイトＸのみとなる。また、ビットＸ７のアドレス符号ビット１２２の値により、相対アドレスの正負が表現される。ビットＸ７が「１」であればアドレスは負、「０」であればアドレスは正である。
【００７０】
図７（Ｃ）に示す２バイト目のバイトＹにおいて、１番目のビットＹ８はバイトＸと同様にアドレス継続フラグに相当するフィールド長フラグ１２１となっている。以降のビットＹ７〜Ｙ１にはＭｏｖｅアドレスの絶対値の第１３ビット〜第７ビットが入る。また、図７（Ｄ）に示す３バイト目のバイトＺについても同様に、１番目のビットＺ８はフィールド長フラグ１２１となっており、以降のビットＺ７〜Ｚ１にはＭｏｖｅアドレスの絶対値の第２０ビット〜第１４ビットが入る。ビットＹ８，Ｚ８のフィールド長フラグ１２１の値により、次のバイトもアドレスフィールドであるかが示され、値が「１」であれば次のバイトもアドレスフィールドであり、「０」であればアドレスフィールドはそのバイトまでとなる。
【００７１】
このアドレスフィールド１０３の具体例を図８に示す。この図８の例は、Ｍｏｖｅアドレスが２バイトで表され、２番目のビットのアドレス符号ビット１２２が「１」であるため相対アドレスの符号が負であり、そのアドレスの値は−４１００バイトであることが示されている。なお、フィールド長フラグ１２１は、複数のビットで表現してもよい。また、フラグの「０」「１」は反対の状態を表現するようにしてもよい。
【００７２】
一方、差分データにおけるＡｄｄデータは、原則として、追加すべきデータ列がそのままＡｄｄデータとなる。ただし、もとのデータ列においてＭｏｖｅデータのデリミタと同じ０ｘ０Ｆが存在する場合は、デリミタと区別するため、これに対応するＡｄｄデータは０ｘ０Ｆ  ０ｘ００  と２バイトのデータとする。
【００７３】
上述したコピーすべきデータ列をＭｏｖｅデータで表現するかＡｄｄデータで表現するかの閾値は、プロセッサとして３２ビットＣＰＵを用いた計算システムにおけるプログラム及びデータを転送する場合などでは、サンプルデータで演算を行った結果、閾値を５バイトとすると差分データのデータ量を最小にできることがわかった。図９は本実施形態に係る差分データ生成手順によってサンプルデータの差分データを生成した結果を示すグラフである。この図９は、閾値を３バイトから８バイトまで変化させたときの差分データのデータ量の変化を示したものであり、閾値が５バイトのときにデータ量が最小となっている。また、上記フォーマットのように、Ｍｏｖｅデータにおいて、デリミタを１バイト、Ｍｏｖｅサイズを１〜３バイト、Ｍｏｖｅアドレスを１〜３バイトで表現する場合、Ｍｏｖｅサイズの期待値を２バイト、Ｍｏｖｅアドレスの期待値を２バイトとすると、閾値は同様に５バイトにするのが差分データのデータ量削減のためには好ましい。
【００７４】
次に、差分データ生成部と更新後ファイル復元部の機能構成について説明する。図１０は図１の差分データ生成装置１１における差分データ生成部１６の機能構成を示すブロック図である。この差分データ生成部１６は、プロセッサ及びメモリを含む演算処理回路、及びこの演算処理回路において動作するソフトウェアプログラムによって、各部の機能が実現される。
【００７５】
差分データ生成部１６は、差分データを生成する各手順の制御を司る差分データ生成制御手段３１、更新前ファイルのデータを記憶する更新前データ記憶手段３２、更新後ファイルのデータを記憶する更新後データ記憶手段３３、更新前ファイルと更新後ファイルとで一致するデータ列を検索する一致データ列検索手段３４、一致データ列の検索結果により差分データとしてＭｏｖｅデータとＡｄｄデータのいずれを生成するかを決定するＭｏｖｅ／Ａｄｄ決定手段３５を備えている。また、Ｍｏｖｅ／Ａｄｄ決定手段３５の結果に基づき、Ｍｏｖｅデータを生成して出力するＭｏｖｅデータ出力手段３６と、Ａｄｄデータを生成して出力するＡｄｄデータ出力手段３７と、ＭｏｖｅデータとＡｄｄデータとを組み合わせた差分データを記憶する差分データ記憶手段３８とを備えている。
【００７６】
さらに、Ｍｏｖｅデータを生成出力した場合に今回のＭｏｖｅアドレスを記憶するＭｏｖｅアドレス記憶手段３９を備えている。Ｍｏｖｅデータ出力手段３６は、ＡｄｄデータとＭｏｖｅデータとの区切りを示すためにＭｏｖｅデータの先頭に設けられるデリミタを出力するデリミタ出力手段（区切り子出力手段）４０、コピーするＭｏｖｅデータのサイズを出力するＭｏｖｅサイズ出力手段４１、Ｍｏｖｅデータをコピーする更新後ファイル上での相対アドレスを出力するＭｏｖｅアドレス出力手段４２、Ｍｏｖｅアドレス記憶手段３９に記憶されているアドレスとＭｏｖｅアドレス出力手段４２より出力されるアドレスとからＭｏｖｅアドレスが変化したかを判定するアドレス変化判定手段４３、アドレス変化判定手段４３の結果に基づきアドレス変化フラグを設定するアドレスフラグ設定手段４４を備えている。これらの差分データ生成部１６の機能については、後述する差分データ生成の動作手順の説明において詳しく述べる。
【００７７】
図１１は図１の携帯端末装置１４における更新後ファイル復元部１９の機能構成を示すブロック図である。この更新後ファイル復元部１９は、プロセッサ及びメモリを含む演算処理回路、及びこの演算処理回路において動作するソフトウェアプログラムによって、各部の機能が実現される。
【００７８】
更新後ファイル復元部１９は、更新後ファイルを復元する各手順の制御を司る更新後ファイル復元制御手段５１、転送された差分データを記憶する差分データ記憶手段５２、更新前ファイルのデータを記憶する更新前データ記憶手段５３、差分データの対象部分がＭｏｖｅデータとＡｄｄデータのいずれであるかを判定するＭｏｖｅ／Ａｄｄ判定手段５４を備えている。また、Ｍｏｖｅ／Ａｄｄ判定手段５４の結果に基づき、Ｍｏｖｅデータに対応するデータ列を更新前ファイルよりコピーして出力するＭｏｖｅデータ復元手段５５と、Ａｄｄデータに対応するデータ列を出力するＡｄｄデータ復元手段５６と、Ｍｏｖｅデータ及びＡｄｄデータにより復元された更新後ファイルのデータを記憶する更新後データ記憶手段５７とを備えている。
【００７９】
さらに、Ｍｏｖｅ操作により更新後ファイルのデータを復元した場合に今回のＭｏｖｅアドレスを記憶するＭｏｖｅアドレス記憶手段５８を備えている。Ｍｏｖｅデータ復元手段５５は、コピーするＭｏｖｅデータのサイズを判定するＭｏｖｅサイズ判定手段５９、コピーする更新後ファイル上での相対アドレスを判定するＭｏｖｅアドレス判定手段６０、Ｍｏｖｅデータ中のアドレス変化フラグに基づきＭｏｖｅアドレスに変化があるかを判定するアドレス変化判定手段６１を備えている。これらの更新後ファイル復元部１９の機能については、後述する更新後ファイル復元の動作手順の説明において詳しく述べる。
【００８０】
次に、本実施形態の差分データ生成部１６における差分データ生成の動作手順を説明する。初めに、差分データ生成の概要を図１２を参照して説明する。図１２は本実施形態に係る差分データ生成手順の概要を示すフローチャートである。差分データの生成は、例えば、携帯端末装置１４において更新前ファイル及び更新後ファイルを格納するフラッシュＲＯＭ等の消去、書き込み単位に合わせて、所定サイズのブロックごとに行うようにする。
【００８１】
差分データ生成部１６は、まず一致データ列検索手段３４によって、更新前データ記憶手段３２に記憶された更新前ファイルと更新後データ記憶手段３３に記憶された更新後ファイルのデータ列を参照し、更新前ファイルの中から更新後ファイルのデータ列と一致するデータ列を先頭から検索する（ステップＳ１０１）。そして、一致データ列検索手段３４での検索結果に基づき、Ｍｏｖｅ／Ａｄｄ決定手段３５によってＭｏｖｅデータとＡｄｄデータのいずれを生成するかを決定する。ここでは、まず一致するデータ列があるか否かを判定し（ステップＳ１０２）、一致するデータ列がある場合はさらに一致するデータ列のデータ長が所定の閾値以上であるか否かを判定する（ステップＳ１０３）。本実施形態では、例えば、一致するデータ列のデータ長が５以上の場合はＭｏｖｅデータとして出力し、４以下の場合はＡｄｄデータとして出力する。
【００８２】
ステップＳ１０２において一致するデータ列が無い場合、及びステップＳ１０３で閾値未満である場合は、Ａｄｄデータ出力手段３７によってそのデータ列をＡｄｄデータとして出力する（ステップＳ１０４）。
【００８３】
一方、ステップＳ１０３で閾値以上である場合は、Ｍｏｖｅデータ出力手段３６によって以降のＭｏｖｅデータ出力手順を実行する。この場合、まずデリミタ出力手段４０によって、以降のデータがＭｏｖｅデータであることを示す所定のデータ（０ｘ０Ｆ）からなるデリミタを出力し（ステップＳ１０５）、次にアドレス変化判定手段４３によってＭｏｖｅアドレス記憶手段３９に記憶されているアドレスを参照してＭｏｖｅアドレスが前回と同じか否かを判定する（ステップＳ１０６）。Ｍｏｖｅアドレスが前回と同じ場合は、アドレスフラグ設定手段４４によりアドレス変化フラグを「０」に設定し（ステップＳ１０７）、Ｍｏｖｅサイズ出力手段４１により一致するデータ列のサイズをＭｏｖｅサイズとして出力する（ステップＳ１０８）。
【００８４】
また、ステップＳ１０６でＭｏｖｅアドレスが前回と異なる場合は、アドレスフラグ設定手段４４によりアドレス変化フラグを「１」に設定し（ステップＳ１０９）、Ｍｏｖｅサイズ出力手段４１により一致するデータ列のサイズをＭｏｖｅサイズとして出力する（ステップＳ１１０）。次いで、Ｍｏｖｅアドレス出力手段４２によりＭｏｖｅデータをコピーする更新後ファイル上での相対アドレスを出力する（ステップＳ１１１）。そしてこのとき、Ｍｏｖｅアドレス記憶手段３９に今回のＭｏｖｅアドレスを記憶する（ステップＳ１１２）。
【００８５】
その後、全データについて処理が終了したかを判断し（ステップＳ１１３）、終了していない場合はステップＳ１０１に戻り、更新後ファイルの終端まで全データ分の処理が終了するまで前記と同様にステップＳ１０１〜Ｓ１１２の処理を繰り返す。以上の手順により、更新前ファイルとの差分を表すデータとして、ＭｏｖｅデータとＡｄｄデータとを組み合わせた差分データが生成され、差分データ記憶手段３８に記憶される。
【００８６】
次に、上記差分データの生成手順をより詳細に説明する。本実施形態では、図４〜図８において例示したフォーマットで構成される差分データを生成する場合の手順を示す。
【００８７】
図１３は本実施形態に係る差分データ生成手順の全体を示すフローチャートである。まず、更新後ファイルにおいて更新前ファイルと一致するデータ列を検索するために、更新前ファイルのデータ列と更新後ファイルのデータ列のそれぞれについてハッシュテーブルを作成する（ステップＳ１２１）。そして、ハッシュテーブルを用いて、更新後ファイルのデータ列において、更新前ファイルの中から一致するデータ列を検索する（ステップＳ１２２）。ここでは、一致データ列検索手段３４において、公知のハッシュ値によるインデックスを利用したデータ列の検索を行い、更新前と更新後のデータ列を比較する。この検索処理により、一致するデータ列の位置及び長さが求められる。このようにハッシュ値を利用した一致データ列の検索を行うことによって、検索処理を高速化できる。
【００８８】
次に、一致するデータ列のデータ長を参照し、このデータ長を閾値である５と比較することによって、Ｍｏｖｅデータとして出力する方がデータサイズが小さいか否かを判定する（ステップＳ１２３）。データ長が５バイト以上である場合はＭｏｖｅデータとして出力する方がデータサイズが小さいと推定し、Ｍｏｖｅデータとして出力する処理手順を実行し（ステップＳ１２４）、今回のＭｏｖｅアドレスを記憶する（ステップＳ１２５）。一方、データ長が４バイト以下である場合はＭｏｖｅデータとして出力する方がデータサイズが大きくなってしまうと推定し、Ａｄｄデータとして出力する処理手順を実行する（ステップＳ１２６）。そして、全データについて処理が終了したかを判断し（ステップＳ１２７）、終了していない場合はステップＳ１２２に戻り、全データ分の処理が終了するまでステップＳ１２２〜Ｓ１２６の処理を繰り返す。
【００８９】
図１４は図１３のステップＳ１２４におけるＭｏｖｅデータとして出力する処理手順を示すフローチャートである。この手順では、まず以降のデータ列がＭｏｖｅデータであることを示すデリミタ（０ｘ０Ｆ）を出力する（ステップＳ１３１）。次に、一致するデータ列についてＭｏｖｅサイズの１バイト目を出力する処理手順を実行する（ステップＳ１３２）。続いて、Ｍｏｖｅサイズの表現に次のバイトも使用するかを判定し（ステップＳ１３３）、使用する場合はＭｏｖｅサイズの２バイト目以降を出力する処理手順を実行する（ステップＳ１３４）。そして、このステップＳ１３３及びＳ１３４の処理を繰り返す。
【００９０】
ステップＳ１３３でＭｏｖｅサイズの表現に次のバイトを使用しない場合は、Ｍｏｖｅアドレスが前回と同じか否かを判定する（ステップＳ１３５）。ここでＭｏｖｅアドレスが前回と異なる場合は、一致するデータ列についてＭｏｖｅアドレスの１バイト目を出力する処理手順を実行する（ステップＳ１３６）。続いて、Ｍｏｖｅアドレスの表現に次のバイトも使用するかを判定し（ステップＳ１３７）、使用する場合はＭｏｖｅアドレスの２バイト目以降を出力する処理手順を実行する（ステップＳ１３８）。そして、このステップＳ１３７及びＳ１３８の処理を繰り返す。
【００９１】
ステップＳ１３５でＭｏｖｅアドレスが前回と同じ場合、及びステップＳ１３７でＭｏｖｅアドレスの表現に次のバイトを使用しない場合は、このＭｏｖｅデータ出力処理を抜けて図１３のステップＳ１２５に進む。
【００９２】
図１５は図１４のステップＳ１３２におけるＭｏｖｅサイズの１バイト目を出力する処理手順を示すフローチャートである。この手順では、まずＭｏｖｅサイズが６ビット以下で表現可能か否かを判定する（ステップＳ１４１）。６ビット以下で表現可能な場合は、最上位ビット、すなわちサイズフィールドの１バイト目のフィールド長フラグを「０」にする（ステップＳ１４２）。また、６ビット以下で表現できない場合は、最上位ビットを「１」にする（ステップＳ１４３）。次に、Ｍｏｖｅアドレスが前回と同じか否かを判定する（ステップＳ１４４）。Ｍｏｖｅアドレスが前回と同じ場合は、上から２番目のビット、すなわちサイズフィールドのアドレス変化フラグを「０」にする（ステップＳ１４５）。また、Ｍｏｖｅアドレスが前回と異なる場合は、上から２番目のビットを「１」にする（ステップＳ１４６）。次いで、Ｍｏｖｅサイズの最下位６ビットを出力する（ステップＳ１４７）。そして、このＭｏｖｅサイズ１バイト目出力処理を抜けて図１４のステップＳ１３３に進む。
【００９３】
図１６は図１４のステップＳ１３４におけるＭｏｖｅサイズの２バイト目以降を出力する処理手順を示すフローチャートである。この手順では、まずＭｏｖｅサイズの未出力ビット数が７以下か否かを判定する（ステップＳ１５１）。未出力ビット数が７以下の場合は、最上位ビット、すなわちサイズフィールドの当該バイトのフィールド長フラグを「０」にする（ステップＳ１５２）。また、未出力ビット数が７より大きい場合は、最上位ビットを「１」にする（ステップＳ１５３）。次に、Ｍｏｖｅサイズの未出力ビットのうち、最下位７ビットを出力する（ステップＳ１５４）。そして、このＭｏｖｅサイズ２バイト目以降出力処理を抜けて図１４のステップＳ１３３に進む。
【００９４】
図１７は図１４のステップＳ１３６におけるＭｏｖｅアドレスの１バイト目を出力する処理手順を示すフローチャートである。この手順では、まずＭｏｖｅアドレスの絶対値が６ビット以下で表現可能か否かを判定する（ステップＳ１６１）。６ビット以下で表現可能な場合は、最上位ビット、すなわちアドレスフィールドの１バイト目のフィールド長フラグを「０」にする（ステップＳ１６２）。また、６ビット以下で表現できない場合は、最上位ビットを「１」にする（ステップＳ１６３）。次に、相対アドレスの符号が正か否かを判定する（ステップＳ１６４）。相対アドレスの符号が正の場合は、上から２番目のビット、すなわちアドレスフィールドのアドレス符号ビットを「０」にする（ステップＳ１６５）。また、相対アドレスの符号が負の場合は、上から２番目のビットを「１」にする（ステップＳ１６６）。次いで、Ｍｏｖｅアドレスの絶対値の最下位６ビットを出力する（ステップＳ１６７）。そして、このＭｏｖｅアドレス１バイト目出力処理を抜けて図１４のステップＳ１３７に進む。
【００９５】
図１８は図１４のステップＳ１３８におけるＭｏｖｅアドレスの２バイト目以降を出力する処理手順を示すフローチャートである。この手順では、まずＭｏｖｅアドレスの絶対値の未出力ビット数が７以下か否かを判定する（ステップＳ１７１）。未出力ビット数が７以下の場合は、最上位ビット、すなわちアドレスフィールドの当該バイトのフィールド長フラグを「０」にする（ステップＳ１７２）。また、未出力ビット数が７より大きい場合は、最上位ビットを「１」にする（ステップＳ１７３）。次に、Ｍｏｖｅアドレスの未出力ビットのうち、最下位７ビットを出力する（ステップＳ１７４）。そして、このＭｏｖｅアドレス２バイト目以降出力処理を抜けて図１４のステップＳ１３７に進む。
【００９６】
図１９は図１３のステップＳ１２６におけるＡｄｄデータとして出力する処理手順を示すフローチャートである。この手順では、更新後ファイルにおいて更新前ファイルと一致しないデータ列、及び４バイト以下の一致データ列について、そのバイナリデータを出力する（ステップＳ１８１）。そして、出力するデータがデリミタと同じ０ｘ０Ｆであるか否かを判定する（ステップＳ１８２）。出力するデータが０ｘ０Ｆでない場合は、このＡｄｄデータ出力処理を終了する。一方、出力するデータが０ｘ０Ｆの場合は、続いて０ｘ００を出力し（ステップＳ１８３）、その後Ａｄｄデータ出力処理を終了する。このＡｄｄデータ出力処理を終了すると、図１３のステップＳ１２７に進む。
【００９７】
上記のようにして生成されたＭｏｖｅデータとＡｄｄデータとを組み合わせた差分データは、差分データ記憶手段３８に一旦記憶される。その後、差分データにヘッダやＣＲＣ等が付加され、必要に応じて圧縮処理が施されて差分ファイルが生成され、差分データ生成装置１１からサーバ１２に転送される。そして、この差分ファイルは、サーバ１２から無線通信網１３を介して携帯端末装置１４に転送され、携帯端末装置１４の更新後ファイル復元部１９において更新前ファイルと差分データとから更新後ファイルを生成することでデータの更新が行われる。
【００９８】
このように本実施形態の差分データ生成装置及び方法によれば、差分データ生成時のＭｏｖｅデータとＡｄｄデータのいずれを生成するかの閾値の設定、Ｍｏｖｅデータにおけるサイズとアドレスの可変ビット長表現などによって、差分データのデータ量をより小さくすることができる。これにより、データを転送する通信回線における負荷、及びデータを処理する装置の演算回路等における負荷やメモリ消費量を軽減することができる。
【００９９】
次に、本実施形態の携帯端末装置１４における更新後ファイル復元の動作手順を説明する。図２０は本実施形態に係る更新後ファイル復元手順の全体を示すフローチャートである。
【０１００】
更新後ファイル復元部１９は、まずＭｏｖｅ／Ａｄｄ判定手段５４によって差分データ記憶手段５２に記憶された差分データの先頭の１バイトを読み込み（ステップＳ２０１）、読み込んだバイトがデリミタと同一の０ｘ０Ｆであるか否かを判定する（ステップＳ２０２）。そのバイトが０ｘ０Ｆでない場合は、Ａｄｄデータの一部であると判定されるため、当該バイトを更新後ファイルのデータとしてＡｄｄデータ復元手段５６より出力する（ステップＳ２０３）。
【０１０１】
ステップＳ２０２で読み込んだバイトが０ｘ０Ｆである場合は、さらに次の１バイトを読み込み（ステップＳ２０４）、読み込んだバイトが０ｘ００であるかを判定する（ステップＳ２０５）。そのバイトが０ｘ００である場合は、直前のバイトの０ｘ０ＦがデリミタではなくてＡｄｄデータの一部であると判定されるため、０ｘ０Ｆを更新後ファイルのデータとしてＡｄｄデータ復元手段５６より出力する（ステップＳ２０６）。一方、ステップＳ２０４で読み込んだバイトが０ｘ００でない場合は、直前のバイトの０ｘ０ＦがＭｏｖｅデータの開始を示すデリミタであると判定されるため、Ｍｏｖｅデータ復元手段５５により以降のデータについてＭｏｖｅ操作による復元処理手順を実行する（ステップＳ２０７）。
【０１０２】
そして、差分データの終端まで読み込んだか否かを判定し（ステップＳ２０８）、差分データの終端まで読み込みが終了していない場合は、次の１バイトを読み込み（ステップＳ２０９）、ステップＳ２０２に戻って差分データの終端まで全データ分の処理が終了するまで前記と同様にステップＳ２０２〜Ｓ２０８の処理を繰り返す。以上の手順により、差分データと更新前ファイルのデータとからＭｏｖｅ操作及びＡｄｄ操作により更新後ファイルが復元生成され、更新後データ記憶手段５７に記憶される。
【０１０３】
図２１は図２０のステップＳ２０７におけるＭｏｖｅ操作による復元処理手順を示すフローチャートである。この手順では、まずＭｏｖｅデータ復元手段５５のアドレス変化判定手段６１によりＭｏｖｅデータの上から２番目のビット、すなわちサイズフィールドのアドレス変化フラグが「０」であるか否かを判定する（ステップＳ２１１）。このアドレス変化フラグが「０」である場合は、Ｍｏｖｅアドレス判定手段６０によりＭｏｖｅアドレス記憶手段５８に記憶されているＭｏｖｅアドレスを読み出し、Ｍｏｖｅアドレスを前回と同じ値に決定する（ステップＳ２１２）。次いで、Ｍｏｖｅサイズ判定手段５９によりＭｏｖｅサイズの判定処理手順を実行する（ステップ２１３）。一方、アドレス変化フラグが「１」である場合は、Ｍｏｖｅアドレスを決定せずにステップ２１３のＭｏｖｅサイズ判定処理手順に進む。
【０１０４】
次に、Ｍｏｖｅアドレス判定手段６０によってＭｏｖｅアドレスをすでに決定したか否かを判定し（ステップＳ２１４）、まだＭｏｖｅアドレスを決定していない場合は、次のバイトを読み込み（ステップＳ２１５）、Ｍｏｖｅアドレス判定手段６０によりＭｏｖｅアドレスの判定処理手順を実行する（ステップ２１６）。
【０１０５】
ステップＳ２１４ですでにＭｏｖｅアドレスが決定されている場合、及びステップ２１６でのＭｏｖｅアドレス判定処理手順の後に、決定したＭｏｖｅサイズ及びＭｏｖｅアドレスに基づいて、更新前ファイルのデータ列をコピーし、更新後ファイルのデータとしてＭｏｖｅデータ復元手段５５より出力する（ステップＳ２１７）。そして、今回のＭｏｖｅアドレスをＭｏｖｅアドレス記憶手段５８に記憶する（ステップＳ２１８）。そして、このＭｏｖｅ操作復元処理を抜けて図２０のステップＳ２０８に進む。
【０１０６】
図２２は図２１のステップＳ２１３におけるＭｏｖｅサイズ判定処理手順を示すフローチャートである。この手順では、まずＭｏｖｅデータの１バイト目について、下位６ビットをＭｏｖｅサイズの下位６ビットとする（ステップＳ２２１）。次いで、このバイトの最上位ビット、すなわちサイズフィールドの１バイト目のフィールド長フラグが「１」であるか否かを判定する（ステップＳ２２２）。フィールド長フラグが「１」である場合は、次のバイトを読み込み（ステップＳ２２３）、そのバイトの下位７ビットをＭｏｖｅサイズの上位７ビットに追加する（ステップＳ２２４）。
【０１０７】
そして、ステップＳ２２２に戻り、２バイト目以降についてもこのバイトの最上位ビット、すなわちサイズフィールドの当該バイトのフィールド長フラグが「１」であるか否かを判定し、フィールド長フラグが「１」である場合は前記と同様にステップＳ２２３〜Ｓ２２４の処理を行う。
【０１０８】
一方、当該バイトの最上位ビットが「０」である場合は、以降のバイトにサイズフィールドが継続しないため、ここまでのＭｏｖｅデータによりＭｏｖｅサイズが決定する（ステップＳ２２５）。そして、このＭｏｖｅサイズ判定処理を抜けて図２１のステップＳ２１４に進む。
【０１０９】
図２３は図２１のステップＳ２１６におけるＭｏｖｅアドレス判定処理手順を示すフローチャートである。この手順では、まずＭｏｖｅデータのアドレスフィールドの１バイト目について、上から２番目のビット、すなわちアドレスフィールドのアドレス符号ビットが「０」であるか否かを判定する（ステップＳ２３１）。アドレス符号ビットが「０」である場合は、Ｍｏｖｅアドレスの符号を正に設定する（ステップＳ２３２）。一方、アドレス符号ビットが「１」である場合は、Ｍｏｖｅアドレスの符号を負に設定する（ステップＳ２３３）。そして、このバイトの下位６ビットをＭｏｖｅアドレスの絶対値の下位６ビットとする（ステップＳ２３４）。
【０１１０】
次に、このバイトの最上位ビット、すなわちアドレスフィールドの１バイト目のフィールド長フラグが「１」であるか否かを判定する（ステップＳ２３５）。フィールド長フラグが「１」である場合は、次のバイトを読み込み（ステップＳ２３６）、そのバイトの下位７ビットをＭｏｖｅアドレスの絶対値の上位７ビットに追加する（ステップＳ２３７）。
【０１１１】
そして、ステップＳ２３５に戻り、２バイト目以降についてもこのバイトの最上位ビット、すなわちアドレスフィールドの当該バイトのフィールド長フラグが「１」であるか否かを判定し、フィールド長フラグが「１」である場合は前記と同様にステップＳ２３６〜Ｓ２３７の処理を行う。
【０１１２】
一方、当該バイトの最上位ビットが「０」である場合は、以降のバイトにアドレスフィールドが継続しないため、ここまでのＭｏｖｅデータによりＭｏｖｅアドレスが決定する（ステップＳ２３８）。そして、このＭｏｖｅアドレス判定処理を抜けて図２１のステップＳ２１７に進む。
【０１１３】
上記のように復元された生成された更新後ファイルのデータは、更新後データ記憶手段５７に一旦記憶される。その後、フラッシュＲＯＭ等からなるデータ格納部２０に更新後ファイルが書き込まれて格納され、更新前ファイルと置き換えられる。
【０１１４】
このように本実施形態の更新後ファイル復元装置及び方法によれば、データ量を削減して生成された差分データと自装置が保持している更新前ファイルとから更新後ファイルを生成でき、少量の更新用の差分データを転送するだけで簡便にデータの更新が可能である。また、データを処理する装置の演算回路等における負荷やメモリ消費量を軽減することができる。
【０１１５】
なお、本発明は上述した実施形態に何ら限定されるものではなく、その要旨を逸脱しない範囲において種々の態様で実施し得るものである。上記実施形態では、コピーすべきデータ列をＭｏｖｅデータで表現するかＡｄｄデータで表現するかの閾値は、予め５バイトに設定して差分データを生成するようにしたが、これに限らず、１つのバージョンの更新前ファイルと１つのバージョンの更新後ファイルとの間の差分データを生成する際に、異なる複数の閾値を用いて差分データ生成処理を実行し、大きさが最小となった場合の差分データを採用するようにしてもよい。
【０１１６】
また、コピーすべきデータ列をＭｏｖｅデータで表現するかＡｄｄデータで表現するかを決定する際に、更新前ファイルと更新後ファイルとで一致するデータ列について、Ｍｏｖｅデータで表現した場合とＡｄｄデータで表現した場合とにおける差分データの大きさを比較し、より小さくなる方に決定することも可能である。
【０１１７】
また、差分データのＭｏｖｅデータにおけるＭｏｖｅアドレスのアドレス情報は、相対アドレスを用いて表現したが、更新前ファイルと更新後ファイルの少なくとも一方の絶対アドレスを用いてもよい。
【０１１８】
また、Ｍｏｖｅデータなどのデータはバイトで表現したが、ワードで表現する場合にも同様に適用可能である。
【０１１９】
【発明の効果】
以上説明したように本発明によれば、一つのバージョンのデータを別のバージョンのデータに更新するためのデータ更新システムにおいて、データ更新に用いる差分データのデータ量を削減することが可能となる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係るデータ更新システムの機能構成を示すブロック図
【図２】本発明の一実施形態における差分データの生成方法の概略を示す説明図
【図３】本発明の一実施形態における更新後ファイルの復元方法の概略を示す説明図
【図４】本実施形態において用いる差分データにおけるＭｏｖｅデータのフォーマットの一例を示す説明図
【図５】図４のＭｏｖｅデータにおけるサイズフィールドのフォーマットの一例を示す説明図
【図６】図４のＭｏｖｅデータにおけるサイズフィールドの具体例を示す説明図
【図７】図４のＭｏｖｅデータにおけるアドレスフィールドのフォーマットの一例を示す説明図
【図８】図４のＭｏｖｅデータにおけるアドレスフィールドの具体例を示す説明図
【図９】本実施形態に係る差分データ生成手順によってサンプルデータの差分データを生成した結果を示すグラフ
【図１０】本発明の一実施形態に係る差分データ生成装置における差分データ生成部の機能構成を示すブロック図
【図１１】本発明の一実施形態に係る携帯端末装置における更新後ファイル復元部の機能構成を示すブロック図
【図１２】本実施形態に係る差分データ生成手順の概要を示すフローチャート
【図１３】本実施形態に係る差分データ生成手順の全体を示すフローチャート
【図１４】図１３の差分データ生成処理におけるＭｏｖｅデータとして出力する処理手順を示すフローチャート
【図１５】図１４のＭｏｖｅデータ出力処理におけるＭｏｖｅサイズの１バイト目を出力する処理手順を示すフローチャート
【図１６】図１４のＭｏｖｅデータ出力処理におけるＭｏｖｅサイズの２バイト目以降を出力する処理手順を示すフローチャート
【図１７】図１４のＭｏｖｅデータ出力処理におけるＭｏｖｅアドレスの１バイト目を出力する処理手順を示すフローチャート
【図１８】図１４のＭｏｖｅデータ出力処理におけるＭｏｖｅアドレスの２バイト目以降を出力する処理手順を示すフローチャート
【図１９】図１３の差分データ生成におけるＡｄｄデータとして出力する処理手順を示すフローチャート
【図２０】本実施形態に係る更新後ファイル復元手順の全体を示すフローチャート
【図２１】図２０の更新後ファイル復元処理におけるＭｏｖｅ操作による復元処理手順を示すフローチャート
【図２２】図２１のＭｏｖｅ操作による復元処理におけるＭｏｖｅサイズ判定処理手順を示すフローチャート
【図２３】図２１のＭｏｖｅ操作による復元処理におけるＭｏｖｅアドレス判定処理手順を示すフローチャート
【図２４】従来の差分データ生成部の機能構成を示すブロック図
【図２５】従来の差分データ生成手順を示すフローチャート
【符号の説明】
１１  差分データ生成装置
１２  サーバ
１３  無線通信網
１４  携帯端末装置
１５  データベース
１６  差分データ生成部
１７  無線通信部
１８  制御部
１９  更新後ファイル復元部
２０  データ格納部
３１  差分データ生成制御手段
３２  更新前データ記憶手段
３３  更新後データ記憶手段
３４  一致データ列検索手段
３５  Ｍｏｖｅ／Ａｄｄ決定手段
３６  Ｍｏｖｅデータ出力手段
３７  Ａｄｄデータ出力手段
３８  差分データ記憶手段
３９  Ｍｏｖｅアドレス記憶手段
４０  デリミタ出力手段
４１  Ｍｏｖｅサイズ出力手段
４２  Ｍｏｖｅアドレス出力手段
４３  アドレス変化判定手段
４４  アドレスフラグ設定手段
５１  更新後ファイル復元制御手段
５２  差分データ記憶手段
５３  更新前データ記憶手段
５４  Ｍｏｖｅ／Ａｄｄ判定手段
５５  Ｍｏｖｅデータ復元手段
５６  Ａｄｄデータ復元手段
５７  更新後データ記憶手段
５８  Ｍｏｖｅアドレス記憶手段
５９  Ｍｏｖｅサイズ判定手段
６０  Ｍｏｖｅアドレス判定手段
６１  アドレス変化判定手段
【図１】
2004152136.tif 000003
【図２】
2004152136.tif 000004
【図３】
2004152136.tif 000005
【図４】
2004152136.tif 000006
【図５】
2004152136.tif 000007
【図６】
2004152136.tif 000008
【図７】
2004152136.tif 000009
【図８】
2004152136.tif 000010
【図９】
2004152136.tif 000011
【図１０】
2004152136.tif 000012
【図１１】
2004152136.tif 000013
【図１２】
2004152136.tif 000014
【図１３】
2004152136.tif 000015
【図１４】
2004152136.tif 000016
【図１５】
2004152136.tif 000017
【図１６】
2004152136.tif 000018
【図１７】
2004152136.tif 000019
【図１８】
2004152136.tif 000020
【図１９】
2004152136.tif 000021
【図２０】
2004152136.tif 000022
【図２１】
2004152136.tif 000023
【図２２】
2004152136.tif 000024
【図２３】
2004152136.tif 000025
【図２４】
2004152136.tif 000026
【図２５】
2004152136.tif 000027