JP2004152136A - データ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラム - Google Patents
データ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラム Download PDFInfo
- Publication number
- JP2004152136A JP2004152136A JP2002318391A JP2002318391A JP2004152136A JP 2004152136 A JP2004152136 A JP 2004152136A JP 2002318391 A JP2002318391 A JP 2002318391A JP 2002318391 A JP2002318391 A JP 2002318391A JP 2004152136 A JP2004152136 A JP 2004152136A
- Authority
- JP
- Japan
- Prior art keywords
- data
- move
- address
- file
- update
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F8/00—Arrangements for software engineering
- G06F8/60—Software deployment
- G06F8/65—Updates
- G06F8/658—Incremental updates; Differential updates
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F40/00—Handling natural language data
- G06F40/10—Text processing
- G06F40/194—Calculation of difference between files
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Software Systems (AREA)
- Computational Linguistics (AREA)
- General Health & Medical Sciences (AREA)
- Health & Medical Sciences (AREA)
- Audiology, Speech & Language Pathology (AREA)
- Artificial Intelligence (AREA)
- Computer Security & Cryptography (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Information Transfer Between Computers (AREA)
- Stored Programmes (AREA)
Abstract
【課題】データ更新システムにおいて、データ更新に用いる差分データのデータ量を削減する。
【解決手段】差分データの生成時に、Move/Add決定手段35によって、更新前ファイルから更新後ファイルへ移動してコピーするMove命令を表すMoveデータと、データを追加してコピーするAdd命令を表すAddデータとのいずれを生成するかを決定する。この際、一致データ列検索手段34で更新前ファイルと更新後ファイルとで一致するデータを検索し、コピーすべきデータ列の長さが5バイト以上の場合はMoveデータ出力手段36よりMoveデータとして出力し、4バイト以下の場合はAddデータ出力手段37よりAddデータとして出力して、これらのMoveデータとAddデータとを組み合わせた差分データを生成する。また、MoveデータのMoveサイズ及びMoveアドレスは可変長ビットにより表現する。これにより、差分データのデータ量を小さくする。
【選択図】 図10
【解決手段】差分データの生成時に、Move/Add決定手段35によって、更新前ファイルから更新後ファイルへ移動してコピーするMove命令を表すMoveデータと、データを追加してコピーするAdd命令を表すAddデータとのいずれを生成するかを決定する。この際、一致データ列検索手段34で更新前ファイルと更新後ファイルとで一致するデータを検索し、コピーすべきデータ列の長さが5バイト以上の場合はMoveデータ出力手段36よりMoveデータとして出力し、4バイト以下の場合はAddデータ出力手段37よりAddデータとして出力して、これらのMoveデータとAddデータとを組み合わせた差分データを生成する。また、MoveデータのMoveサイズ及びMoveアドレスは可変長ビットにより表現する。これにより、差分データのデータ量を小さくする。
【選択図】 図10
Description
【0001】
【発明の属する技術分野】
本発明は、一つのバージョンのデータを別のバージョンのデータに更新するためのデータ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラムに関する。
【0002】
【従来の技術】
パーソナルコンピュータ、携帯情報端末(PDA)、携帯電話機など、所定のプログラムに基づくプロセッサの動作によって装置動作の少なくとも一部を実行する端末装置では、プログラムの改良などのために、対象のプログラムを含むデータのバージョンを更新する、いわゆるバージョンアップが行われることがある。このようなデータのバージョン更新時には、フラッシュROM、ハードディスクなどの書換可能な記録媒体に記録された更新前のソフトウェア等のデータ(以下、更新前ファイルと称する)が、他のバージョン(一般には新しいバージョン)のソフトウェア等のデータ(以下、更新後ファイルと称する)に書き換えられる。この場合、単純に更新前ファイルを更新後ファイルに置き換えることもできるが、更新前ファイルと更新後ファイルとの差分データを生成し、この差分データをを基に更新前ファイルから更新後ファイルを生成して書き換えることも従来より多く行われている。
【0003】
従来の差分データ生成方法の一例を図24及び図25を参照して説明する。図24は従来の差分データ生成部の機能構成を示すブロック図、図25は従来の差分データ生成手順を示すフローチャートである。ここでは、Walter F. Tichy が提案したBlock−Moveアルゴリズムを用いた差分データ生成方法を示す。この方法は、更新前ファイルのデータと更新後ファイルのデータとを比較して一致するデータ列を検索し、一致するデータ列はそのまま更新前ファイルから更新後ファイルへMoveデータとして移動するようにしてコピーし、一致しないデータ列は新たなデータ列をAddデータとして追加して書き込むことで、差分データを生成するものである(非特許文献1参照)。
【0004】
差分データ生成部は、差分データを生成する各手順の制御を司る差分データ生成制御手段501、更新前ファイルのデータを記憶する更新前データ記憶手段502、更新後ファイルのデータを記憶する更新後データ記憶手段503、更新前ファイルと更新後ファイルとで一致するデータ列を検索する一致データ列検索手段504を備えている。また、更新前後で一致するデータ列をMoveデータとして出力するMoveデータ出力手段505、更新前後で一致しないデータ列をAddデータとして出力するAddデータ出力手段506、MoveデータとAddデータとを組み合わせた差分データを記憶する差分データ記憶手段507を備えている。Moveデータ出力手段505は、AddデータとMoveデータとの区切りを示す区切り子(デリミタ)を出力するデリミタ出力手段511、Moveデータのサイズを出力するMoveサイズ出力手段512、Moveデータが位置する更新前ファイル及び更新後ファイル上のアドレスを出力するMoveアドレス出力手段513を備えている。
【0005】
この従来例では、まず一致データ列検索手段504によって、更新前データ記憶手段502に記憶された更新前ファイルと更新後データ記憶手段503に記憶された更新後ファイルのデータ列を参照し、更新前ファイルの中から更新後ファイルのデータ列と一致するデータ列を先頭から検索する(ステップS501)。そして、一致するデータ列があるか否かによって処理手順を分岐し(ステップS502)、一致するデータ列がある場合はMoveデータ出力手段505によって以降のMoveデータ出力手順を実行する。
【0006】
Moveデータとしては、まずデリミタ出力手段511によって、以降のデータがMoveデータであることを示す所定のデータからなるデリミタを出力し(ステップS503)、次にMoveサイズ出力手段512によって、Moveデータのサイズとして一致するデータ列のサイズを出力し(ステップS504)、続いてMoveアドレス出力手段513によって、Moveデータのアドレスとして一致するデータ列の更新前ファイル及び更新後ファイル上でのアドレスを出力する(ステップS505)。このように一致するデータ列のサイズとアドレスとを用いることによって、更新前ファイルから更新後ファイルへコピーするデータ列を指定することができる。
【0007】
ステップS502において一致するデータ列が無い場合は、Addデータ出力手段506によってそのデータ列をAddデータとして出力する(ステップS506)。そして、全データについて処理が終了したかを判断し(ステップS507)、終了していない場合はステップS501に戻り、更新後ファイルの終端まで全データ分の処理が終了するまでステップS501〜S506の処理を繰り返す。以上の手順により、更新前ファイルと更新後ファイルとの差分を表す差分データが生成され、差分データ記憶手段507に記憶される。
【0008】
【非特許文献1】
Walter F. Tichy, 「The String−to−String Correction Probrem with Block Moves」, ACM Transactions on Computer Systems, ACM (Association for Computing Machinery), 1984年11月,第2巻,第4号,p.309−321
【0009】
【発明が解決しようとする課題】
プログラム等を含むファイルのデータを更新するために、更新前ファイルと更新後ファイルとの差分データを用いることによって、更新のために必要なデータ容量を削減することができる。このとき、差分データを更新対象の端末装置に転送し、この端末装置において更新前ファイルと差分データとから更新後ファイルを復元することによって、更新の際に転送するデータ量を小さくできる。この差分データは上記従来例のような方法によって生成することが可能である。
【0010】
しかしながら、大がかりなプログラム変更等によって多量のデータ変更が発生した場合は、差分データであってもデータサイズが巨大化し、差分データをネットワーク等の通信回線を介して転送する場合に通信回線における負荷(トラフィック)が増大したり、端末装置の演算回路等における負荷が増大してしまう。これにより、差分データの転送や更新後データへの書き換えに長い時間がかかったり、通信回線のコストが増加するなどの問題点が生じることがあった。特に無線通信による移動体通信システムを用いてデータの更新を行う場合などは、通信回線の容量や端末装置のメモリの容量などに制約が多いため、差分データについてさらなるデータ量の削減が求められている。
【0011】
本発明は、上記課題を解決するためになされたもので、その目的は、データ更新に用いる差分データのデータ量を削減することが可能なデータ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラムを提供することにある。
【0012】
【課題を解決するための手段】
本発明は、第1に、複数のバージョンのデータを持ち、1つのバージョンのデータである更新前ファイルと他のもう1つのバージョンのデータである更新後ファイルとの差を示す差分データを生成する差分データ生成手段と、前記差分データを転送する通信手段と、前記差分データを受信し、すでに保持している更新前ファイルと受信した前記差分データとを元に更新後ファイルを復元する更新後ファイル復元手段とを有するデータ更新システムであって、前記差分データとして、前記更新前ファイルの一部、あるいは全部からデータを移動してコピーすることを意味する0個、1個、あるいは複数のMove命令を表すMoveデータと、当該差分データ中のデータを追加してコピーすることを意味する0個、1個、あるいは複数のAdd命令を表すAddデータとを有して構成される差分データを用いたデータ更新システムを提供する。
【0013】
また、第2に、前記第1の構成において、前記差分データにおいて、前記Moveデータの長さが所定の閾値未満となる場合はMoveデータではなくAddデータによって構成したものとする。
【0014】
また、第3に、前記第1の構成において、前記差分データにおいて、前記Moveデータは、コピーを行うデータ列の長さを表すデータ長情報と、コピーを行うデータ列の位置を表すアドレス情報とを有し、前記データ長情報と前記アドレス情報の少なくとも一方を可変ビット長で構成したものとする。
【0015】
また、第4に、前記第1の構成において、前記差分データにおいて、前記Moveデータは、コピーを行うデータ列の長さを表すデータ長情報と、コピーを行うデータ列の位置を表すアドレス情報とを有し、前記アドレス情報として前記データ列の移動のための相対アドレスを用い、同一の相対アドレス値が複数のMoveデータにおいて現れる場合に該当する1つまたは複数の相対アドレス値を1つまたは複数のビットで表現するように構成したものとする。
【0016】
本発明は、第5に、1つのバージョンのデータである更新前ファイルと他のもう1つのバージョンのデータである更新後ファイルとの差を示す差分データを生成し、前記差分データを通信手段を介して他所へ転送し、転送先で保持している更新前ファイルと前記差分データとを元に更新後ファイルを復元するデータ更新システムにおける差分データ生成装置であって、前記更新後ファイル中のデータ列と一致するデータ列を前記更新前ファイルから検索する一致データ列検索手段と、前記検索結果に基づき、前記差分データとして、前記更新前ファイルの一部、あるいは全部から一致するデータ列を前記更新後ファイルへ移動してコピーすることを意味するMove命令を表すMoveデータと、当該差分データ中のデータ列を前記更新後ファイルへ追加してコピーすることを意味するAdd命令を表すAddデータとのいずれを生成するかを決定するMove/Add決定手段と、前記Moveデータを出力するMoveデータ出力手段と、前記Addデータを出力するAddデータ出力手段とを備え、0個、1個、あるいは複数の前記Moveデータと0個、1個、あるいは複数の前記Addデータとを有して構成される差分データを生成する差分データ生成装置を提供する。
【0017】
また、第6に、前記第5の構成において、前記Moveデータ出力手段は、前記Moveデータの開始を示す特定のデータからなる区切り子を出力する区切り子出力手段を備え、前記区切り子の後に前記Move命令を表現するデータを出力するものとする。
【0018】
また、第7に、前記第5の構成において、前記Addデータ出力手段は、前記Addデータ中に前記区切り子として用いられる特定のデータが存在する場合に、このデータに続けて区切り子ではないことを示す特定のデータを出力するものとする。
【0019】
また、第8に、前記第5の構成において、前記Move/Add決定手段は、前記一致するデータ列の長さが所定の閾値以上となる場合は前記Moveデータ出力手段よりMoveデータとして出力し、前記一致するデータ列の長さが所定の閾値未満となる場合は前記Addデータ出力手段よりAddデータとして出力するように決定するものとする。
【0020】
また、第9に、前記第8の構成において、前記Move/Add決定手段における閾値として、32ビットCPUを用いた計算システムにおけるプログラム及びデータを転送するデータ更新システムに用いる場合に、閾値を5バイトとするものとする。
【0021】
また、第10に、前記第8の構成において、前記Move/Add決定手段における閾値として、1つのバージョンの更新前ファイルと1つのバージョンの更新後ファイルとの間の差分データを生成する際に、異なる複数の閾値を用いて差分データ生成を実行し、大きさが最小となった場合の差分データを採用するものとする。
【0022】
また、第11に、前記第5の構成において、前記Move/Add決定手段は、前記一致するデータ列について、前記Moveデータで表現した場合と前記Addデータで表現した場合とにおける差分データの大きさを比較し、より小さくなる方に決定するものとする。
【0023】
また、第12に、前記第5の構成において、前記Moveデータ出力手段は、前記Moveデータの先頭バイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを設け、前記データ長継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報のみによって前記更新前ファイルよりコピーを行うデータ列の長さを表現し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記データ列の長さを表現する情報が継続することとしたデータ長情報を出力するものとする。
【0024】
また、第13に、前記第12の構成において、前記Moveデータ出力手段は、前記Moveデータの2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを設け、前記データ長継続フラグが所定の状態1を取っている場合は前記Moveデータの先頭バイトまたはワードから当該バイトまたはワードまでにおける情報によって前記更新前ファイルよりコピーを行うデータ列の長さを表現し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記データ列の長さを表現する情報が継続することとしたデータ長情報を出力するものとする。
【0025】
また、第14に、前記第5の構成において、前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルと前記更新後ファイルの少なくとも一方における絶対アドレスを用いたアドレス情報を出力するものとする。
【0026】
また、第15に、前記第5の構成において、前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差を示す相対アドレスを用いたアドレス情報を出力するものとする。
【0027】
また、第16に、前記第5の構成において、前記Moveデータ出力手段及び前記Addデータ出力手段は、前記更新後ファイルにおけるデータ列の順番に沿ってMoveデータ及びAddデータを生成出力するものとし、前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルにおける当該データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いたアドレス情報を出力するものとする。
【0028】
また、第17に、前記第15または16の構成において、前記Moveデータ出力手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の先頭バイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを設け、前記アドレス継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報のみによって前記相対アドレスを表現し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記相対アドレスを表現する情報が継続することとしたアドレス情報を出力するものとする。
【0029】
また、第18に、前記第17の構成において、前記Moveデータ出力手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを設け、前記アドレス継続フラグが所定の状態1を取っている場合は前記アドレス情報のデータ列の先頭バイトまたはワードから当該バイトまたはワードまでにおける情報によって前記相対アドレスを表現し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記相対アドレスを表現する情報が継続することとしたアドレス情報を出力するものとする。
【0030】
また、第19に、前記第15または16の構成において、前記Moveデータ出力手段は、前記Moveデータのアドレス情報において、同一の相対アドレス値が複数のMoveデータにおいて現れる場合に、該当する1つまたは複数の相対アドレス値については前記Moveデータの先頭バイトまたはワードにおいて1つあるいは複数のビットで表現することとする。
【0031】
また、第20に、前記第5の構成において、前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の位置を表す情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差、または前記更新前ファイルにおける前記データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いたアドレス情報を出力するものとし、前記Moveデータ中において1つあるいは複数のビットからなるアドレス変化フラグを設け、前記アドレス変化フラグが所定の状態1を取っている場合は前記データ列の長さを表現するデータ長情報の後に前記相対アドレスによるアドレス情報を出力し、前記アドレス変化フラグが前記状態1とは異なる所定の状態2を取っている場合は前回のMoveデータにおける相対アドレスと今回のMoveデータにおける相対アドレスとが同一であるとして前記相対アドレスを表現する情報を省略するものとする。
【0032】
また、第21に、前記第15,16,20のいずれかの構成において、前記Moveデータ出力手段は、前記Moveデータのアドレス情報における相対アドレスを、前回のMoveデータにおける相対アドレスからの変化量により表現することとする。
【0033】
本発明は、第22に、前記第5〜21のいずれかの構成のデータ更新システムの差分データ生成装置における各手段の機能をコンピュータにより実現するための差分データ生成プログラムを提供する。
【0034】
本発明は、第23に、1つのバージョンのデータである更新前ファイルと他のもう1つのバージョンのデータである更新後ファイルとの差を示す差分データを受信し、自装置で保持している更新前ファイルと前記差分データとを元に更新後ファイルを復元するデータ更新システムにおける更新後ファイル復元装置であって、前記差分データが、前記更新前ファイルの一部、あるいは全部から一致するデータ列を前記更新後ファイルへ移動してコピーすることを意味するMove命令を表すMoveデータと、当該差分データ中のデータ列を前記更新後ファイルへ追加してコピーすることを意味するAdd命令を表すAddデータとのいずれであるかを判定するMove/Add判定手段と、前記Moveデータに対応するデータ列を出力するMoveデータ復元手段と、前記Addデータに対応するデータ列を出力するAddデータ復元手段とを備え、前記差分データより更新後ファイルを生成する更新後ファイル復元装置を提供する。
【0035】
また、第24に、前記第23の構成において、前記Move/Add判定手段は、前記差分データにおいて、特定のデータからなる区切り子の後に設けられたMove命令を表現するデータをMoveデータとし、前記差分データの先頭または前回のMoveデータの終端から前記区切り子が出現するまでに設けられたAdd命令を表現するデータをAddデータとして区別するものとする。
【0036】
また、第25に、前記第24の構成において、前記Move/Add判定手段は、前記差分データにおいて、前記区切り子がデータ列中に現れ、かつ前記区切り子に続くデータが特定のものである場合は、前記区切り子ではなく、前記Addデータ中に存在する区切り子として用いられたデータそのものであるとする。
【0037】
また、第26に、前記第23の構成において、前記Moveデータ復元手段は、前記Moveデータに設けられるデータ長情報を判別して前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の長さを決定するものであり、前記Moveデータの先頭バイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを検出し、前記データ長継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報よりデータ長情報を判別して前記コピーを行うデータ列の長さを決定し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記データ長情報が継続するものと判定することとする。
【0038】
また、第27に、前記第26の構成において、前記Moveデータ復元手段は、前記Moveデータの2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを検出し、前記データ長継続フラグが所定の状態1を取っている場合は前記Moveデータの先頭バイトまたはワードから当該バイトまたはワードまでにおける情報よりデータ長情報を判別して前記コピーを行うデータ列の長さを決定し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記データ長情報が継続するものと判定することとする。
【0039】
また、第28に、前記第23の構成において、前記Moveデータ復元手段は、前記Moveデータに設けられるアドレス情報を判別して前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を決定するものであり、前記アドレス情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差、または前記更新前ファイルにおける前記データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスにより表現されたアドレス情報を判別するものとする。
【0040】
また、第29に、前記第28の構成において、前記Moveデータ復元手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の先頭バイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを検出し、前記アドレス継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報より前記相対アドレスのアドレス情報を判別して前記コピーを行うデータ列の位置を決定し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記アドレス情報が継続するものと判定することとする。
【0041】
また、第30に、前記第29の構成において、前記Moveデータ復元手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを検出し、前記アドレス継続フラグが所定の状態1を取っている場合は前記アドレス情報のデータ列の先頭バイトまたはワードから当該バイトまたはワードにおける情報より前記相対アドレスのアドレス情報を判別して前記コピーを行うデータ列の位置を決定し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記アドレス情報が継続するものと判定することとする。
【0042】
また、第31に、前記第28の構成において、前記Moveデータ復元手段は、前記Moveデータ中において1つあるいは複数のビットで表現されたアドレス情報を判別し、このアドレス情報に該当する1つまたは複数の相対アドレス値については同一の相対アドレス値として前記コピーを行うデータ列の位置を決定するものとする。
【0043】
また、第32に、前記第28の構成において、前記Moveデータ復元手段は、前記Moveデータ中において1つあるいは複数のビットからなるアドレス変化フラグを検出し、前記アドレス変化フラグが所定の状態1を取っている場合は前記コピーを行うデータ列の長さを表すデータ長情報の後に設けられる前記相対アドレスによるアドレス情報を判別し、前記アドレス変化フラグが前記状態1とは異なる所定の状態2を取っている場合は前回のMoveデータにおける相対アドレスと同一の相対アドレスを用いて前記コピーを行うデータ列の位置を決定するものとする。
【0044】
本発明は、第33に、前記第23〜32のいずれかの構成のデータ更新システムの更新後ファイル復元装置における各手段の機能をコンピュータにより実現するための更新後ファイル復元プログラムを提供する。
【0045】
上記構成によれば、差分データ生成時のMoveデータとAddデータのいずれを生成するかの閾値の設定、Moveデータにおけるサイズとアドレスの可変ビット長表現、Moveデータにおいて同一のアドレスが存在する場合のアドレス情報の省略などによって、差分データのデータ量を削減することが可能となる。これにより、データを転送する通信手段における負荷、及びデータを処理する装置の演算回路等における負荷やメモリ消費量などを軽減することが可能となる。
【0046】
【発明の実施の形態】
以下、図面を参照して本発明の実施形態を説明する。
本実施形態では、データ更新システムの一例として、携帯電話機等の携帯端末装置に格納されている動作プログラム等を含むデータのバージョンを更新する場合の構成及び動作の例を説明する。本実施形態は、差分データを移動体通信システムの無線通信網を介して携帯端末装置へ転送することによって、通信回線経由で容易に携帯端末装置内のデータを更新可能にしたものである。
【0047】
図1は本発明の一実施形態に係るデータ更新システムの機能構成を示すブロック図である。データ更新システムは、更新前ファイル及び更新後ファイルから差分データを生成する差分データ生成手段の機能を有する差分データ生成装置11と、差分データを転送するサーバ12と、サーバ12と無線通信網13を介して接続され前記差分データ及び更新前ファイルから更新後ファイルを復元する更新後ファイル復元手段の機能を有する携帯端末装置14とを備えて構成される。なお本実施形態では、サーバ12及び無線通信網13等によって通信手段が構成される。
【0048】
差分データ生成装置11は、更新前ファイル及び更新後ファイルとなる複数のバージョンのデータを格納したデータベース15と、データベース15に格納された更新前ファイルと更新後ファイルとから後述する手順により差分データを生成する差分データ生成部16とを有して構成される。サーバ12は、移動体通信システムにおいて各種データの配信などを行うために設けられるもので、対象となる携帯端末装置14へ差分データを送信するようになっている。
【0049】
携帯端末装置14は、無線通信により各種データや音声信号等の送受信を行う無線通信部17と、各部の動作制御を行う制御部18と、転送された差分データと更新前ファイルとから後述する手順により更新後ファイルを復元して生成する更新後ファイル復元部19と、更新後ファイルを格納するフラッシュROM等からなるデータ格納部20とを有して構成される。
【0050】
上記構成のデータ更新システムにおいて、差分データ生成装置11により更新前ファイルと更新後ファイルとから差分データを生成し、この差分データをサーバ12より無線通信網13を介して携帯端末装置14に転送する。携帯端末装置14では、更新後ファイル復元部19によってサーバ12より転送された差分データと現在格納している更新前ファイルとから更新後ファイルを復元し、この更新後ファイルをデータ格納部20に格納する。これにより、携帯端末装置14を使用者が使用している状態であっても、適当なタイミングで無線通信網13を介して差分データを転送することによって、容易に動作プログラム等のバージョンを更新することが可能となる。
【0051】
ここで、本実施形態における差分データの生成、及び更新後ファイルの復元についての概要を説明する。図2は本実施形態における差分データの生成方法の概略を示す説明図である。差分データの生成時には、図2(A)に示す更新前ファイルと図2(B)に示す更新後ファイルとから差分抽出を行って図2(C)に示す差分データを生成する。この場合、更新後ファイルのデータ列において更新前ファイルのデータ列と一致する部分を検索し、一致するデータ列については、更新前ファイルからコピーするための一致部分のサイズ(データ長情報)とアドレス(アドレス情報)により示されるMoveデータを生成する。また、一致しないデータ列については、そのデータ列を書き込むためのAddデータを生成する。
【0052】
本実施形態では、更新前ファイル内のデータ列の一部を移動(コピー)してきて更新後ファイルの一部を生成する操作をMove操作と呼び、このMove操作の内容を記述したデータをMoveデータと呼ぶ。また、更新前ファイルを参照せずにデータ列を追加することで更新後ファイルの一部を生成する操作をAdd操作と呼び、このAdd操作の内容を記述したデータをAddデータと呼ぶ。差分データは、MoveデータとAddデータとの組み合わせによって構成され、更新後ファイルを復元する際のMove命令及びAdd命令として用いられる。すなわち、差分データは、0個、1個、あるいは複数のMove命令を表すMoveデータと、0個、1個、あるいは複数のAdd命令を表すAddデータとを有して構成される。
【0053】
図2の例では、更新前ファイルのアドレスq3から更新後ファイルのアドレスp1へ4バイトコピー(「a,b,c,d」をコピー)するためのMoveデータ、次に「e,f,g,h」を書き込むためのAddデータ、次に更新前ファイルのアドレスq2から更新後ファイルのアドレスp2へ3バイトコピー(「x,y,z」をコピー)するためのMoveデータ、次に「i,j,k,l,m」を書き込むためのAddデータが生成される。
【0054】
図3は本実施形態における更新後ファイルの復元方法の概略を示す説明図である。更新後ファイルの復元時には、図3(A)に示す差分データと図3(B)に示す更新前ファイルとから図3(C)に示す更新後ファイルを生成する。この場合、差分データにおけるMoveデータによるMove命令とAddデータによるAdd命令とに基づいて、更新前ファイルから一致するデータ列がコピーされて移動され、一致しない新たなデータ列が書き込まれて追加される。
【0055】
図3の例では、まず▲1▼でMove命令により更新前ファイルのアドレスq3から更新後ファイルのアドレスp1へ4バイトコピー(「a,b,c,d」がコピー)され、次に▲2▼でAdd命令により「e,f,g,h」が書き込まれ、次に▲3▼でMove命令により更新前ファイルのアドレスq2から更新後ファイルのアドレスp2へ3バイトコピー(「x,y,z」がコピー)され、次に▲4▼でAdd命令により「i,j,k,l,m」が書き込まれる。以上のようにして、Moveデータ及びAddデータからなる差分データを用いて更新前ファイルから更新後ファイルが復元生成される。
【0056】
本実施形態では、差分データにおいて以下に述べる特徴を持たせることによって、差分データのデータ量を削減している。
【0057】
(1)一致するデータ列が所定長未満の場合、MoveデータではなくAddデータにする。Moveデータにおいてサイズとアドレスを何バイトで表現するかにも関係するが、小さいデータ列の移動に関するMoveデータは、データそのものが示されるAddデータよりもデータ量が大きくなってしまう場合がある。本実施形態では、例えば閾値を5バイトとし、この閾値未満、すなわち一致する部分が4バイト以下のデータ列についてはAddデータとして差分データを生成してデータ量を小さくする。
【0058】
(2)Moveデータにおいて、サイズとアドレスをそれぞれ可変ビット長で表現する。可変ビット長とすることにより、小さい値の場合は小さいデータ量で表現することが可能である。なお、サイズとアドレスの少なくとも一方のみを可変ビット長で表現してもよい。本実施形態では、アドレスについては相対アドレスを使用し、更新前ファイル上でのアドレスを基準として更新後ファイルにおけるアドレスの変化量(相対移動距離)を表すこととする。
【0059】
(3)Moveデータにおいて、アドレスに相対アドレスを用いた場合、当該アドレスが直前のMoveデータにおけるアドレス(相対移動距離)と同じ場合はアドレスを省略する。本実施形態では、更新後ファイルのデータ列を先頭から順に復元するように差分データを形成するものとする。このため、直前のMoveデータのアドレスと同じ場合、すなわちコピーするデータ列の相対移動距離が同じで平行移動状態でコピーする場合は、直前のデータ列の後に続けてコピーすれば良いことになる。この場合、同一のアドレスを省略することによってデータ量を小さくする。
【0060】
なお、同一のアドレスが複数出現する場合、フラグ等によって前回と同一のアドレスであることを示したり、出現頻度の高い1つまたは複数のアドレスを1つまたは複数のビットで表現するようにしてデータ量を削減することも可能である。
【0061】
前記相対アドレスとしては、更新前ファイルにおけるコピーすべきデータ列の位置(先頭及び/または終端)と更新後ファイルにおける当該データ列の位置(先頭及び/または終端)との差を示す相対アドレスを用いることができる。この場合、複数のMoveデータについて更新後ファイルにおけるデータ列の位置が前後したりランダムに並んでいても対応可能である。また、更新後ファイルのデータ列を先頭から順に復元するように、更新後ファイルにおけるデータ列の順番に沿ってMoveデータ及びAddデータを生成して差分データを構成する場合は、更新前ファイルにおけるコピーすべきデータ列の先頭位置と更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いることができる。本実施形態ではこの相対アドレスを採用する。この場合、上記の同一アドレスの省略についても対応可能である。さらに、相対アドレスは、前回のMoveデータにおける相対アドレスからの変化量により表現することも可能である。
【0062】
次に、差分データのフォーマットの一例を示す。図4に示すように、差分データにおけるMoveデータは、Moveデータの開始を示す区切り子であるデリミタ101と、コピーすべきデータ列のサイズを示すデータ長情報が格納されるサイズフィールド102と、コピーすべきデータ列の相対アドレスを示すアドレス情報が格納されるアドレスフィールド103との3つの要素から構成される。
【0063】
デリミタ101は、サイズは1バイトで0x0F(2進表記で00001111)を用いることとする。本明細書では、0x**は16進表記を示すものとする。なお、デリミタは複数バイトで表現したり、1ないし複数のビットやワードで表現することも可能である。
【0064】
サイズフィールド102は、コピーすべきデータ列のサイズ(以下、Moveサイズと称する場合もある)を格納する可変長のフィールドであり、1〜3バイトで構成される。このサイズフィールド102について、図5(A)に示すように3バイトを順にA,B,Cとし、各バイトを図5(B),(C),(D)に示すように表して詳細を説明する。
【0065】
図5(B)に示す1バイト目のバイトAにおいて、1番目のビットA8はデータ長継続フラグに相当するフィールド長フラグ111、2番目のビットA7はアドレス変化フラグ112となっている。以降のビットA6〜A1にはMoveサイズの最下位6ビットが入る。ビットA8のフィールド長フラグ111の値により、次のバイトもサイズフィールドであるかが示される。ビットA8が「1(フラグが立っている状態、以下同様)」であれば次のバイトもサイズフィールドであり、「0(フラグが寝ている状態、以下同様)」であればサイズフィールドはバイトAのみとなる。また、ビットA7のアドレス変化フラグ112の値により、サイズフィールドの次にアドレスフィールドが続くかどうかが示される。ビットA7が「1」であればサイズフィールドの次にアドレスフィールドが続き、「0」であればアドレスフィールドが無く、直前のMove操作時と同じアドレスであるものとする。
【0066】
図5(C)に示す2バイト目のバイトBにおいて、1番目のビットB8はバイトAと同様にデータ長継続フラグに相当するフィールド長フラグ111となっている。以降のビットB7〜B1にはMoveサイズの第13ビット〜第7ビットが入る。また、図5(D)に示す3バイト目のバイトCについても同様に、1番目のビットC8はフィールド長フラグ111となっており、以降のビットC7〜C1にはMoveサイズの第20ビット〜第14ビットが入る。ビットB8,C8のフィールド長フラグ111の値により、次のバイトもサイズフィールドであるかが示され、値が「1」であれば次のバイトもサイズフィールドであり、「0」であればサイズフィールドはそのバイトまでとなる。
【0067】
このサイズフィールド102の具体例を図6に示す。この図6の例は、Moveサイズが3バイトで表され、そのサイズの値は33826バイトであり、2番目のビットのアドレス変化フラグ112が「0」であるためアドレスフィールドが後に続かないことが示されている。なお、フィールド長フラグ111やアドレス変化フラグ112は、複数のビットで表現してもよい。また、フラグの「0」「1」は反対の状態を表現するようにしてもよい。
【0068】
アドレスフィールド103は、コピーすべきデータ列の相対アドレス(以下、Moveアドレスと称する場合もある)を格納する可変長のフィールドであり、1〜3バイトで構成される。このアドレスフィールド103は前記サイズフィールド102のアドレス変化フラグ112が「1」の場合に設けられる。このアドレスフィールド103について、図7(A)に示すように3バイトを順にX,Y,Zとし、各バイトを図7(B),(C),(D)に示すように表して詳細を説明する。
【0069】
図7(B)に示す1バイト目のバイトXにおいて、1番目のビットX8はアドレス継続フラグに相当するフィールド長フラグ121、2番目のビットX7はアドレス符号ビット122となっている。以降のビットX6〜X1にはMoveアドレスの絶対値の最下位6ビットが入る。ビットX8のフィールド長フラグ121の値により、次のバイトもアドレスフィールドであるかが示される。ビットX8が「1」であれば次のバイトもアドレスフィールドであり、「0」であればアドレスフィールドはバイトXのみとなる。また、ビットX7のアドレス符号ビット122の値により、相対アドレスの正負が表現される。ビットX7が「1」であればアドレスは負、「0」であればアドレスは正である。
【0070】
図7(C)に示す2バイト目のバイトYにおいて、1番目のビットY8はバイトXと同様にアドレス継続フラグに相当するフィールド長フラグ121となっている。以降のビットY7〜Y1にはMoveアドレスの絶対値の第13ビット〜第7ビットが入る。また、図7(D)に示す3バイト目のバイトZについても同様に、1番目のビットZ8はフィールド長フラグ121となっており、以降のビットZ7〜Z1にはMoveアドレスの絶対値の第20ビット〜第14ビットが入る。ビットY8,Z8のフィールド長フラグ121の値により、次のバイトもアドレスフィールドであるかが示され、値が「1」であれば次のバイトもアドレスフィールドであり、「0」であればアドレスフィールドはそのバイトまでとなる。
【0071】
このアドレスフィールド103の具体例を図8に示す。この図8の例は、Moveアドレスが2バイトで表され、2番目のビットのアドレス符号ビット122が「1」であるため相対アドレスの符号が負であり、そのアドレスの値は−4100バイトであることが示されている。なお、フィールド長フラグ121は、複数のビットで表現してもよい。また、フラグの「0」「1」は反対の状態を表現するようにしてもよい。
【0072】
一方、差分データにおけるAddデータは、原則として、追加すべきデータ列がそのままAddデータとなる。ただし、もとのデータ列においてMoveデータのデリミタと同じ0x0Fが存在する場合は、デリミタと区別するため、これに対応するAddデータは0x0F 0x00 と2バイトのデータとする。
【0073】
上述したコピーすべきデータ列をMoveデータで表現するかAddデータで表現するかの閾値は、プロセッサとして32ビットCPUを用いた計算システムにおけるプログラム及びデータを転送する場合などでは、サンプルデータで演算を行った結果、閾値を5バイトとすると差分データのデータ量を最小にできることがわかった。図9は本実施形態に係る差分データ生成手順によってサンプルデータの差分データを生成した結果を示すグラフである。この図9は、閾値を3バイトから8バイトまで変化させたときの差分データのデータ量の変化を示したものであり、閾値が5バイトのときにデータ量が最小となっている。また、上記フォーマットのように、Moveデータにおいて、デリミタを1バイト、Moveサイズを1〜3バイト、Moveアドレスを1〜3バイトで表現する場合、Moveサイズの期待値を2バイト、Moveアドレスの期待値を2バイトとすると、閾値は同様に5バイトにするのが差分データのデータ量削減のためには好ましい。
【0074】
次に、差分データ生成部と更新後ファイル復元部の機能構成について説明する。図10は図1の差分データ生成装置11における差分データ生成部16の機能構成を示すブロック図である。この差分データ生成部16は、プロセッサ及びメモリを含む演算処理回路、及びこの演算処理回路において動作するソフトウェアプログラムによって、各部の機能が実現される。
【0075】
差分データ生成部16は、差分データを生成する各手順の制御を司る差分データ生成制御手段31、更新前ファイルのデータを記憶する更新前データ記憶手段32、更新後ファイルのデータを記憶する更新後データ記憶手段33、更新前ファイルと更新後ファイルとで一致するデータ列を検索する一致データ列検索手段34、一致データ列の検索結果により差分データとしてMoveデータとAddデータのいずれを生成するかを決定するMove/Add決定手段35を備えている。また、Move/Add決定手段35の結果に基づき、Moveデータを生成して出力するMoveデータ出力手段36と、Addデータを生成して出力するAddデータ出力手段37と、MoveデータとAddデータとを組み合わせた差分データを記憶する差分データ記憶手段38とを備えている。
【0076】
さらに、Moveデータを生成出力した場合に今回のMoveアドレスを記憶するMoveアドレス記憶手段39を備えている。Moveデータ出力手段36は、AddデータとMoveデータとの区切りを示すためにMoveデータの先頭に設けられるデリミタを出力するデリミタ出力手段(区切り子出力手段)40、コピーするMoveデータのサイズを出力するMoveサイズ出力手段41、Moveデータをコピーする更新後ファイル上での相対アドレスを出力するMoveアドレス出力手段42、Moveアドレス記憶手段39に記憶されているアドレスとMoveアドレス出力手段42より出力されるアドレスとからMoveアドレスが変化したかを判定するアドレス変化判定手段43、アドレス変化判定手段43の結果に基づきアドレス変化フラグを設定するアドレスフラグ設定手段44を備えている。これらの差分データ生成部16の機能については、後述する差分データ生成の動作手順の説明において詳しく述べる。
【0077】
図11は図1の携帯端末装置14における更新後ファイル復元部19の機能構成を示すブロック図である。この更新後ファイル復元部19は、プロセッサ及びメモリを含む演算処理回路、及びこの演算処理回路において動作するソフトウェアプログラムによって、各部の機能が実現される。
【0078】
更新後ファイル復元部19は、更新後ファイルを復元する各手順の制御を司る更新後ファイル復元制御手段51、転送された差分データを記憶する差分データ記憶手段52、更新前ファイルのデータを記憶する更新前データ記憶手段53、差分データの対象部分がMoveデータとAddデータのいずれであるかを判定するMove/Add判定手段54を備えている。また、Move/Add判定手段54の結果に基づき、Moveデータに対応するデータ列を更新前ファイルよりコピーして出力するMoveデータ復元手段55と、Addデータに対応するデータ列を出力するAddデータ復元手段56と、Moveデータ及びAddデータにより復元された更新後ファイルのデータを記憶する更新後データ記憶手段57とを備えている。
【0079】
さらに、Move操作により更新後ファイルのデータを復元した場合に今回のMoveアドレスを記憶するMoveアドレス記憶手段58を備えている。Moveデータ復元手段55は、コピーするMoveデータのサイズを判定するMoveサイズ判定手段59、コピーする更新後ファイル上での相対アドレスを判定するMoveアドレス判定手段60、Moveデータ中のアドレス変化フラグに基づきMoveアドレスに変化があるかを判定するアドレス変化判定手段61を備えている。これらの更新後ファイル復元部19の機能については、後述する更新後ファイル復元の動作手順の説明において詳しく述べる。
【0080】
次に、本実施形態の差分データ生成部16における差分データ生成の動作手順を説明する。初めに、差分データ生成の概要を図12を参照して説明する。図12は本実施形態に係る差分データ生成手順の概要を示すフローチャートである。差分データの生成は、例えば、携帯端末装置14において更新前ファイル及び更新後ファイルを格納するフラッシュROM等の消去、書き込み単位に合わせて、所定サイズのブロックごとに行うようにする。
【0081】
差分データ生成部16は、まず一致データ列検索手段34によって、更新前データ記憶手段32に記憶された更新前ファイルと更新後データ記憶手段33に記憶された更新後ファイルのデータ列を参照し、更新前ファイルの中から更新後ファイルのデータ列と一致するデータ列を先頭から検索する(ステップS101)。そして、一致データ列検索手段34での検索結果に基づき、Move/Add決定手段35によってMoveデータとAddデータのいずれを生成するかを決定する。ここでは、まず一致するデータ列があるか否かを判定し(ステップS102)、一致するデータ列がある場合はさらに一致するデータ列のデータ長が所定の閾値以上であるか否かを判定する(ステップS103)。本実施形態では、例えば、一致するデータ列のデータ長が5以上の場合はMoveデータとして出力し、4以下の場合はAddデータとして出力する。
【0082】
ステップS102において一致するデータ列が無い場合、及びステップS103で閾値未満である場合は、Addデータ出力手段37によってそのデータ列をAddデータとして出力する(ステップS104)。
【0083】
一方、ステップS103で閾値以上である場合は、Moveデータ出力手段36によって以降のMoveデータ出力手順を実行する。この場合、まずデリミタ出力手段40によって、以降のデータがMoveデータであることを示す所定のデータ(0x0F)からなるデリミタを出力し(ステップS105)、次にアドレス変化判定手段43によってMoveアドレス記憶手段39に記憶されているアドレスを参照してMoveアドレスが前回と同じか否かを判定する(ステップS106)。Moveアドレスが前回と同じ場合は、アドレスフラグ設定手段44によりアドレス変化フラグを「0」に設定し(ステップS107)、Moveサイズ出力手段41により一致するデータ列のサイズをMoveサイズとして出力する(ステップS108)。
【0084】
また、ステップS106でMoveアドレスが前回と異なる場合は、アドレスフラグ設定手段44によりアドレス変化フラグを「1」に設定し(ステップS109)、Moveサイズ出力手段41により一致するデータ列のサイズをMoveサイズとして出力する(ステップS110)。次いで、Moveアドレス出力手段42によりMoveデータをコピーする更新後ファイル上での相対アドレスを出力する(ステップS111)。そしてこのとき、Moveアドレス記憶手段39に今回のMoveアドレスを記憶する(ステップS112)。
【0085】
その後、全データについて処理が終了したかを判断し(ステップS113)、終了していない場合はステップS101に戻り、更新後ファイルの終端まで全データ分の処理が終了するまで前記と同様にステップS101〜S112の処理を繰り返す。以上の手順により、更新前ファイルとの差分を表すデータとして、MoveデータとAddデータとを組み合わせた差分データが生成され、差分データ記憶手段38に記憶される。
【0086】
次に、上記差分データの生成手順をより詳細に説明する。本実施形態では、図4〜図8において例示したフォーマットで構成される差分データを生成する場合の手順を示す。
【0087】
図13は本実施形態に係る差分データ生成手順の全体を示すフローチャートである。まず、更新後ファイルにおいて更新前ファイルと一致するデータ列を検索するために、更新前ファイルのデータ列と更新後ファイルのデータ列のそれぞれについてハッシュテーブルを作成する(ステップS121)。そして、ハッシュテーブルを用いて、更新後ファイルのデータ列において、更新前ファイルの中から一致するデータ列を検索する(ステップS122)。ここでは、一致データ列検索手段34において、公知のハッシュ値によるインデックスを利用したデータ列の検索を行い、更新前と更新後のデータ列を比較する。この検索処理により、一致するデータ列の位置及び長さが求められる。このようにハッシュ値を利用した一致データ列の検索を行うことによって、検索処理を高速化できる。
【0088】
次に、一致するデータ列のデータ長を参照し、このデータ長を閾値である5と比較することによって、Moveデータとして出力する方がデータサイズが小さいか否かを判定する(ステップS123)。データ長が5バイト以上である場合はMoveデータとして出力する方がデータサイズが小さいと推定し、Moveデータとして出力する処理手順を実行し(ステップS124)、今回のMoveアドレスを記憶する(ステップS125)。一方、データ長が4バイト以下である場合はMoveデータとして出力する方がデータサイズが大きくなってしまうと推定し、Addデータとして出力する処理手順を実行する(ステップS126)。そして、全データについて処理が終了したかを判断し(ステップS127)、終了していない場合はステップS122に戻り、全データ分の処理が終了するまでステップS122〜S126の処理を繰り返す。
【0089】
図14は図13のステップS124におけるMoveデータとして出力する処理手順を示すフローチャートである。この手順では、まず以降のデータ列がMoveデータであることを示すデリミタ(0x0F)を出力する(ステップS131)。次に、一致するデータ列についてMoveサイズの1バイト目を出力する処理手順を実行する(ステップS132)。続いて、Moveサイズの表現に次のバイトも使用するかを判定し(ステップS133)、使用する場合はMoveサイズの2バイト目以降を出力する処理手順を実行する(ステップS134)。そして、このステップS133及びS134の処理を繰り返す。
【0090】
ステップS133でMoveサイズの表現に次のバイトを使用しない場合は、Moveアドレスが前回と同じか否かを判定する(ステップS135)。ここでMoveアドレスが前回と異なる場合は、一致するデータ列についてMoveアドレスの1バイト目を出力する処理手順を実行する(ステップS136)。続いて、Moveアドレスの表現に次のバイトも使用するかを判定し(ステップS137)、使用する場合はMoveアドレスの2バイト目以降を出力する処理手順を実行する(ステップS138)。そして、このステップS137及びS138の処理を繰り返す。
【0091】
ステップS135でMoveアドレスが前回と同じ場合、及びステップS137でMoveアドレスの表現に次のバイトを使用しない場合は、このMoveデータ出力処理を抜けて図13のステップS125に進む。
【0092】
図15は図14のステップS132におけるMoveサイズの1バイト目を出力する処理手順を示すフローチャートである。この手順では、まずMoveサイズが6ビット以下で表現可能か否かを判定する(ステップS141)。6ビット以下で表現可能な場合は、最上位ビット、すなわちサイズフィールドの1バイト目のフィールド長フラグを「0」にする(ステップS142)。また、6ビット以下で表現できない場合は、最上位ビットを「1」にする(ステップS143)。次に、Moveアドレスが前回と同じか否かを判定する(ステップS144)。Moveアドレスが前回と同じ場合は、上から2番目のビット、すなわちサイズフィールドのアドレス変化フラグを「0」にする(ステップS145)。また、Moveアドレスが前回と異なる場合は、上から2番目のビットを「1」にする(ステップS146)。次いで、Moveサイズの最下位6ビットを出力する(ステップS147)。そして、このMoveサイズ1バイト目出力処理を抜けて図14のステップS133に進む。
【0093】
図16は図14のステップS134におけるMoveサイズの2バイト目以降を出力する処理手順を示すフローチャートである。この手順では、まずMoveサイズの未出力ビット数が7以下か否かを判定する(ステップS151)。未出力ビット数が7以下の場合は、最上位ビット、すなわちサイズフィールドの当該バイトのフィールド長フラグを「0」にする(ステップS152)。また、未出力ビット数が7より大きい場合は、最上位ビットを「1」にする(ステップS153)。次に、Moveサイズの未出力ビットのうち、最下位7ビットを出力する(ステップS154)。そして、このMoveサイズ2バイト目以降出力処理を抜けて図14のステップS133に進む。
【0094】
図17は図14のステップS136におけるMoveアドレスの1バイト目を出力する処理手順を示すフローチャートである。この手順では、まずMoveアドレスの絶対値が6ビット以下で表現可能か否かを判定する(ステップS161)。6ビット以下で表現可能な場合は、最上位ビット、すなわちアドレスフィールドの1バイト目のフィールド長フラグを「0」にする(ステップS162)。また、6ビット以下で表現できない場合は、最上位ビットを「1」にする(ステップS163)。次に、相対アドレスの符号が正か否かを判定する(ステップS164)。相対アドレスの符号が正の場合は、上から2番目のビット、すなわちアドレスフィールドのアドレス符号ビットを「0」にする(ステップS165)。また、相対アドレスの符号が負の場合は、上から2番目のビットを「1」にする(ステップS166)。次いで、Moveアドレスの絶対値の最下位6ビットを出力する(ステップS167)。そして、このMoveアドレス1バイト目出力処理を抜けて図14のステップS137に進む。
【0095】
図18は図14のステップS138におけるMoveアドレスの2バイト目以降を出力する処理手順を示すフローチャートである。この手順では、まずMoveアドレスの絶対値の未出力ビット数が7以下か否かを判定する(ステップS171)。未出力ビット数が7以下の場合は、最上位ビット、すなわちアドレスフィールドの当該バイトのフィールド長フラグを「0」にする(ステップS172)。また、未出力ビット数が7より大きい場合は、最上位ビットを「1」にする(ステップS173)。次に、Moveアドレスの未出力ビットのうち、最下位7ビットを出力する(ステップS174)。そして、このMoveアドレス2バイト目以降出力処理を抜けて図14のステップS137に進む。
【0096】
図19は図13のステップS126におけるAddデータとして出力する処理手順を示すフローチャートである。この手順では、更新後ファイルにおいて更新前ファイルと一致しないデータ列、及び4バイト以下の一致データ列について、そのバイナリデータを出力する(ステップS181)。そして、出力するデータがデリミタと同じ0x0Fであるか否かを判定する(ステップS182)。出力するデータが0x0Fでない場合は、このAddデータ出力処理を終了する。一方、出力するデータが0x0Fの場合は、続いて0x00を出力し(ステップS183)、その後Addデータ出力処理を終了する。このAddデータ出力処理を終了すると、図13のステップS127に進む。
【0097】
上記のようにして生成されたMoveデータとAddデータとを組み合わせた差分データは、差分データ記憶手段38に一旦記憶される。その後、差分データにヘッダやCRC等が付加され、必要に応じて圧縮処理が施されて差分ファイルが生成され、差分データ生成装置11からサーバ12に転送される。そして、この差分ファイルは、サーバ12から無線通信網13を介して携帯端末装置14に転送され、携帯端末装置14の更新後ファイル復元部19において更新前ファイルと差分データとから更新後ファイルを生成することでデータの更新が行われる。
【0098】
このように本実施形態の差分データ生成装置及び方法によれば、差分データ生成時のMoveデータとAddデータのいずれを生成するかの閾値の設定、Moveデータにおけるサイズとアドレスの可変ビット長表現などによって、差分データのデータ量をより小さくすることができる。これにより、データを転送する通信回線における負荷、及びデータを処理する装置の演算回路等における負荷やメモリ消費量を軽減することができる。
【0099】
次に、本実施形態の携帯端末装置14における更新後ファイル復元の動作手順を説明する。図20は本実施形態に係る更新後ファイル復元手順の全体を示すフローチャートである。
【0100】
更新後ファイル復元部19は、まずMove/Add判定手段54によって差分データ記憶手段52に記憶された差分データの先頭の1バイトを読み込み(ステップS201)、読み込んだバイトがデリミタと同一の0x0Fであるか否かを判定する(ステップS202)。そのバイトが0x0Fでない場合は、Addデータの一部であると判定されるため、当該バイトを更新後ファイルのデータとしてAddデータ復元手段56より出力する(ステップS203)。
【0101】
ステップS202で読み込んだバイトが0x0Fである場合は、さらに次の1バイトを読み込み(ステップS204)、読み込んだバイトが0x00であるかを判定する(ステップS205)。そのバイトが0x00である場合は、直前のバイトの0x0FがデリミタではなくてAddデータの一部であると判定されるため、0x0Fを更新後ファイルのデータとしてAddデータ復元手段56より出力する(ステップS206)。一方、ステップS204で読み込んだバイトが0x00でない場合は、直前のバイトの0x0FがMoveデータの開始を示すデリミタであると判定されるため、Moveデータ復元手段55により以降のデータについてMove操作による復元処理手順を実行する(ステップS207)。
【0102】
そして、差分データの終端まで読み込んだか否かを判定し(ステップS208)、差分データの終端まで読み込みが終了していない場合は、次の1バイトを読み込み(ステップS209)、ステップS202に戻って差分データの終端まで全データ分の処理が終了するまで前記と同様にステップS202〜S208の処理を繰り返す。以上の手順により、差分データと更新前ファイルのデータとからMove操作及びAdd操作により更新後ファイルが復元生成され、更新後データ記憶手段57に記憶される。
【0103】
図21は図20のステップS207におけるMove操作による復元処理手順を示すフローチャートである。この手順では、まずMoveデータ復元手段55のアドレス変化判定手段61によりMoveデータの上から2番目のビット、すなわちサイズフィールドのアドレス変化フラグが「0」であるか否かを判定する(ステップS211)。このアドレス変化フラグが「0」である場合は、Moveアドレス判定手段60によりMoveアドレス記憶手段58に記憶されているMoveアドレスを読み出し、Moveアドレスを前回と同じ値に決定する(ステップS212)。次いで、Moveサイズ判定手段59によりMoveサイズの判定処理手順を実行する(ステップ213)。一方、アドレス変化フラグが「1」である場合は、Moveアドレスを決定せずにステップ213のMoveサイズ判定処理手順に進む。
【0104】
次に、Moveアドレス判定手段60によってMoveアドレスをすでに決定したか否かを判定し(ステップS214)、まだMoveアドレスを決定していない場合は、次のバイトを読み込み(ステップS215)、Moveアドレス判定手段60によりMoveアドレスの判定処理手順を実行する(ステップ216)。
【0105】
ステップS214ですでにMoveアドレスが決定されている場合、及びステップ216でのMoveアドレス判定処理手順の後に、決定したMoveサイズ及びMoveアドレスに基づいて、更新前ファイルのデータ列をコピーし、更新後ファイルのデータとしてMoveデータ復元手段55より出力する(ステップS217)。そして、今回のMoveアドレスをMoveアドレス記憶手段58に記憶する(ステップS218)。そして、このMove操作復元処理を抜けて図20のステップS208に進む。
【0106】
図22は図21のステップS213におけるMoveサイズ判定処理手順を示すフローチャートである。この手順では、まずMoveデータの1バイト目について、下位6ビットをMoveサイズの下位6ビットとする(ステップS221)。次いで、このバイトの最上位ビット、すなわちサイズフィールドの1バイト目のフィールド長フラグが「1」であるか否かを判定する(ステップS222)。フィールド長フラグが「1」である場合は、次のバイトを読み込み(ステップS223)、そのバイトの下位7ビットをMoveサイズの上位7ビットに追加する(ステップS224)。
【0107】
そして、ステップS222に戻り、2バイト目以降についてもこのバイトの最上位ビット、すなわちサイズフィールドの当該バイトのフィールド長フラグが「1」であるか否かを判定し、フィールド長フラグが「1」である場合は前記と同様にステップS223〜S224の処理を行う。
【0108】
一方、当該バイトの最上位ビットが「0」である場合は、以降のバイトにサイズフィールドが継続しないため、ここまでのMoveデータによりMoveサイズが決定する(ステップS225)。そして、このMoveサイズ判定処理を抜けて図21のステップS214に進む。
【0109】
図23は図21のステップS216におけるMoveアドレス判定処理手順を示すフローチャートである。この手順では、まずMoveデータのアドレスフィールドの1バイト目について、上から2番目のビット、すなわちアドレスフィールドのアドレス符号ビットが「0」であるか否かを判定する(ステップS231)。アドレス符号ビットが「0」である場合は、Moveアドレスの符号を正に設定する(ステップS232)。一方、アドレス符号ビットが「1」である場合は、Moveアドレスの符号を負に設定する(ステップS233)。そして、このバイトの下位6ビットをMoveアドレスの絶対値の下位6ビットとする(ステップS234)。
【0110】
次に、このバイトの最上位ビット、すなわちアドレスフィールドの1バイト目のフィールド長フラグが「1」であるか否かを判定する(ステップS235)。フィールド長フラグが「1」である場合は、次のバイトを読み込み(ステップS236)、そのバイトの下位7ビットをMoveアドレスの絶対値の上位7ビットに追加する(ステップS237)。
【0111】
そして、ステップS235に戻り、2バイト目以降についてもこのバイトの最上位ビット、すなわちアドレスフィールドの当該バイトのフィールド長フラグが「1」であるか否かを判定し、フィールド長フラグが「1」である場合は前記と同様にステップS236〜S237の処理を行う。
【0112】
一方、当該バイトの最上位ビットが「0」である場合は、以降のバイトにアドレスフィールドが継続しないため、ここまでのMoveデータによりMoveアドレスが決定する(ステップS238)。そして、このMoveアドレス判定処理を抜けて図21のステップS217に進む。
【0113】
上記のように復元された生成された更新後ファイルのデータは、更新後データ記憶手段57に一旦記憶される。その後、フラッシュROM等からなるデータ格納部20に更新後ファイルが書き込まれて格納され、更新前ファイルと置き換えられる。
【0114】
このように本実施形態の更新後ファイル復元装置及び方法によれば、データ量を削減して生成された差分データと自装置が保持している更新前ファイルとから更新後ファイルを生成でき、少量の更新用の差分データを転送するだけで簡便にデータの更新が可能である。また、データを処理する装置の演算回路等における負荷やメモリ消費量を軽減することができる。
【0115】
なお、本発明は上述した実施形態に何ら限定されるものではなく、その要旨を逸脱しない範囲において種々の態様で実施し得るものである。上記実施形態では、コピーすべきデータ列をMoveデータで表現するかAddデータで表現するかの閾値は、予め5バイトに設定して差分データを生成するようにしたが、これに限らず、1つのバージョンの更新前ファイルと1つのバージョンの更新後ファイルとの間の差分データを生成する際に、異なる複数の閾値を用いて差分データ生成処理を実行し、大きさが最小となった場合の差分データを採用するようにしてもよい。
【0116】
また、コピーすべきデータ列をMoveデータで表現するかAddデータで表現するかを決定する際に、更新前ファイルと更新後ファイルとで一致するデータ列について、Moveデータで表現した場合とAddデータで表現した場合とにおける差分データの大きさを比較し、より小さくなる方に決定することも可能である。
【0117】
また、差分データのMoveデータにおけるMoveアドレスのアドレス情報は、相対アドレスを用いて表現したが、更新前ファイルと更新後ファイルの少なくとも一方の絶対アドレスを用いてもよい。
【0118】
また、Moveデータなどのデータはバイトで表現したが、ワードで表現する場合にも同様に適用可能である。
【0119】
【発明の効果】
以上説明したように本発明によれば、一つのバージョンのデータを別のバージョンのデータに更新するためのデータ更新システムにおいて、データ更新に用いる差分データのデータ量を削減することが可能となる。
【図面の簡単な説明】
【図1】本発明の一実施形態に係るデータ更新システムの機能構成を示すブロック図
【図2】本発明の一実施形態における差分データの生成方法の概略を示す説明図
【図3】本発明の一実施形態における更新後ファイルの復元方法の概略を示す説明図
【図4】本実施形態において用いる差分データにおけるMoveデータのフォーマットの一例を示す説明図
【図5】図4のMoveデータにおけるサイズフィールドのフォーマットの一例を示す説明図
【図6】図4のMoveデータにおけるサイズフィールドの具体例を示す説明図
【図7】図4のMoveデータにおけるアドレスフィールドのフォーマットの一例を示す説明図
【図8】図4のMoveデータにおけるアドレスフィールドの具体例を示す説明図
【図9】本実施形態に係る差分データ生成手順によってサンプルデータの差分データを生成した結果を示すグラフ
【図10】本発明の一実施形態に係る差分データ生成装置における差分データ生成部の機能構成を示すブロック図
【図11】本発明の一実施形態に係る携帯端末装置における更新後ファイル復元部の機能構成を示すブロック図
【図12】本実施形態に係る差分データ生成手順の概要を示すフローチャート
【図13】本実施形態に係る差分データ生成手順の全体を示すフローチャート
【図14】図13の差分データ生成処理におけるMoveデータとして出力する処理手順を示すフローチャート
【図15】図14のMoveデータ出力処理におけるMoveサイズの1バイト目を出力する処理手順を示すフローチャート
【図16】図14のMoveデータ出力処理におけるMoveサイズの2バイト目以降を出力する処理手順を示すフローチャート
【図17】図14のMoveデータ出力処理におけるMoveアドレスの1バイト目を出力する処理手順を示すフローチャート
【図18】図14のMoveデータ出力処理におけるMoveアドレスの2バイト目以降を出力する処理手順を示すフローチャート
【図19】図13の差分データ生成におけるAddデータとして出力する処理手順を示すフローチャート
【図20】本実施形態に係る更新後ファイル復元手順の全体を示すフローチャート
【図21】図20の更新後ファイル復元処理におけるMove操作による復元処理手順を示すフローチャート
【図22】図21のMove操作による復元処理におけるMoveサイズ判定処理手順を示すフローチャート
【図23】図21のMove操作による復元処理におけるMoveアドレス判定処理手順を示すフローチャート
【図24】従来の差分データ生成部の機能構成を示すブロック図
【図25】従来の差分データ生成手順を示すフローチャート
【符号の説明】
11 差分データ生成装置
12 サーバ
13 無線通信網
14 携帯端末装置
15 データベース
16 差分データ生成部
17 無線通信部
18 制御部
19 更新後ファイル復元部
20 データ格納部
31 差分データ生成制御手段
32 更新前データ記憶手段
33 更新後データ記憶手段
34 一致データ列検索手段
35 Move/Add決定手段
36 Moveデータ出力手段
37 Addデータ出力手段
38 差分データ記憶手段
39 Moveアドレス記憶手段
40 デリミタ出力手段
41 Moveサイズ出力手段
42 Moveアドレス出力手段
43 アドレス変化判定手段
44 アドレスフラグ設定手段
51 更新後ファイル復元制御手段
52 差分データ記憶手段
53 更新前データ記憶手段
54 Move/Add判定手段
55 Moveデータ復元手段
56 Addデータ復元手段
57 更新後データ記憶手段
58 Moveアドレス記憶手段
59 Moveサイズ判定手段
60 Moveアドレス判定手段
61 アドレス変化判定手段
【発明の属する技術分野】
本発明は、一つのバージョンのデータを別のバージョンのデータに更新するためのデータ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラムに関する。
【0002】
【従来の技術】
パーソナルコンピュータ、携帯情報端末(PDA)、携帯電話機など、所定のプログラムに基づくプロセッサの動作によって装置動作の少なくとも一部を実行する端末装置では、プログラムの改良などのために、対象のプログラムを含むデータのバージョンを更新する、いわゆるバージョンアップが行われることがある。このようなデータのバージョン更新時には、フラッシュROM、ハードディスクなどの書換可能な記録媒体に記録された更新前のソフトウェア等のデータ(以下、更新前ファイルと称する)が、他のバージョン(一般には新しいバージョン)のソフトウェア等のデータ(以下、更新後ファイルと称する)に書き換えられる。この場合、単純に更新前ファイルを更新後ファイルに置き換えることもできるが、更新前ファイルと更新後ファイルとの差分データを生成し、この差分データをを基に更新前ファイルから更新後ファイルを生成して書き換えることも従来より多く行われている。
【0003】
従来の差分データ生成方法の一例を図24及び図25を参照して説明する。図24は従来の差分データ生成部の機能構成を示すブロック図、図25は従来の差分データ生成手順を示すフローチャートである。ここでは、Walter F. Tichy が提案したBlock−Moveアルゴリズムを用いた差分データ生成方法を示す。この方法は、更新前ファイルのデータと更新後ファイルのデータとを比較して一致するデータ列を検索し、一致するデータ列はそのまま更新前ファイルから更新後ファイルへMoveデータとして移動するようにしてコピーし、一致しないデータ列は新たなデータ列をAddデータとして追加して書き込むことで、差分データを生成するものである(非特許文献1参照)。
【0004】
差分データ生成部は、差分データを生成する各手順の制御を司る差分データ生成制御手段501、更新前ファイルのデータを記憶する更新前データ記憶手段502、更新後ファイルのデータを記憶する更新後データ記憶手段503、更新前ファイルと更新後ファイルとで一致するデータ列を検索する一致データ列検索手段504を備えている。また、更新前後で一致するデータ列をMoveデータとして出力するMoveデータ出力手段505、更新前後で一致しないデータ列をAddデータとして出力するAddデータ出力手段506、MoveデータとAddデータとを組み合わせた差分データを記憶する差分データ記憶手段507を備えている。Moveデータ出力手段505は、AddデータとMoveデータとの区切りを示す区切り子(デリミタ)を出力するデリミタ出力手段511、Moveデータのサイズを出力するMoveサイズ出力手段512、Moveデータが位置する更新前ファイル及び更新後ファイル上のアドレスを出力するMoveアドレス出力手段513を備えている。
【0005】
この従来例では、まず一致データ列検索手段504によって、更新前データ記憶手段502に記憶された更新前ファイルと更新後データ記憶手段503に記憶された更新後ファイルのデータ列を参照し、更新前ファイルの中から更新後ファイルのデータ列と一致するデータ列を先頭から検索する(ステップS501)。そして、一致するデータ列があるか否かによって処理手順を分岐し(ステップS502)、一致するデータ列がある場合はMoveデータ出力手段505によって以降のMoveデータ出力手順を実行する。
【0006】
Moveデータとしては、まずデリミタ出力手段511によって、以降のデータがMoveデータであることを示す所定のデータからなるデリミタを出力し(ステップS503)、次にMoveサイズ出力手段512によって、Moveデータのサイズとして一致するデータ列のサイズを出力し(ステップS504)、続いてMoveアドレス出力手段513によって、Moveデータのアドレスとして一致するデータ列の更新前ファイル及び更新後ファイル上でのアドレスを出力する(ステップS505)。このように一致するデータ列のサイズとアドレスとを用いることによって、更新前ファイルから更新後ファイルへコピーするデータ列を指定することができる。
【0007】
ステップS502において一致するデータ列が無い場合は、Addデータ出力手段506によってそのデータ列をAddデータとして出力する(ステップS506)。そして、全データについて処理が終了したかを判断し(ステップS507)、終了していない場合はステップS501に戻り、更新後ファイルの終端まで全データ分の処理が終了するまでステップS501〜S506の処理を繰り返す。以上の手順により、更新前ファイルと更新後ファイルとの差分を表す差分データが生成され、差分データ記憶手段507に記憶される。
【0008】
【非特許文献1】
Walter F. Tichy, 「The String−to−String Correction Probrem with Block Moves」, ACM Transactions on Computer Systems, ACM (Association for Computing Machinery), 1984年11月,第2巻,第4号,p.309−321
【0009】
【発明が解決しようとする課題】
プログラム等を含むファイルのデータを更新するために、更新前ファイルと更新後ファイルとの差分データを用いることによって、更新のために必要なデータ容量を削減することができる。このとき、差分データを更新対象の端末装置に転送し、この端末装置において更新前ファイルと差分データとから更新後ファイルを復元することによって、更新の際に転送するデータ量を小さくできる。この差分データは上記従来例のような方法によって生成することが可能である。
【0010】
しかしながら、大がかりなプログラム変更等によって多量のデータ変更が発生した場合は、差分データであってもデータサイズが巨大化し、差分データをネットワーク等の通信回線を介して転送する場合に通信回線における負荷(トラフィック)が増大したり、端末装置の演算回路等における負荷が増大してしまう。これにより、差分データの転送や更新後データへの書き換えに長い時間がかかったり、通信回線のコストが増加するなどの問題点が生じることがあった。特に無線通信による移動体通信システムを用いてデータの更新を行う場合などは、通信回線の容量や端末装置のメモリの容量などに制約が多いため、差分データについてさらなるデータ量の削減が求められている。
【0011】
本発明は、上記課題を解決するためになされたもので、その目的は、データ更新に用いる差分データのデータ量を削減することが可能なデータ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラムを提供することにある。
【0012】
【課題を解決するための手段】
本発明は、第1に、複数のバージョンのデータを持ち、1つのバージョンのデータである更新前ファイルと他のもう1つのバージョンのデータである更新後ファイルとの差を示す差分データを生成する差分データ生成手段と、前記差分データを転送する通信手段と、前記差分データを受信し、すでに保持している更新前ファイルと受信した前記差分データとを元に更新後ファイルを復元する更新後ファイル復元手段とを有するデータ更新システムであって、前記差分データとして、前記更新前ファイルの一部、あるいは全部からデータを移動してコピーすることを意味する0個、1個、あるいは複数のMove命令を表すMoveデータと、当該差分データ中のデータを追加してコピーすることを意味する0個、1個、あるいは複数のAdd命令を表すAddデータとを有して構成される差分データを用いたデータ更新システムを提供する。
【0013】
また、第2に、前記第1の構成において、前記差分データにおいて、前記Moveデータの長さが所定の閾値未満となる場合はMoveデータではなくAddデータによって構成したものとする。
【0014】
また、第3に、前記第1の構成において、前記差分データにおいて、前記Moveデータは、コピーを行うデータ列の長さを表すデータ長情報と、コピーを行うデータ列の位置を表すアドレス情報とを有し、前記データ長情報と前記アドレス情報の少なくとも一方を可変ビット長で構成したものとする。
【0015】
また、第4に、前記第1の構成において、前記差分データにおいて、前記Moveデータは、コピーを行うデータ列の長さを表すデータ長情報と、コピーを行うデータ列の位置を表すアドレス情報とを有し、前記アドレス情報として前記データ列の移動のための相対アドレスを用い、同一の相対アドレス値が複数のMoveデータにおいて現れる場合に該当する1つまたは複数の相対アドレス値を1つまたは複数のビットで表現するように構成したものとする。
【0016】
本発明は、第5に、1つのバージョンのデータである更新前ファイルと他のもう1つのバージョンのデータである更新後ファイルとの差を示す差分データを生成し、前記差分データを通信手段を介して他所へ転送し、転送先で保持している更新前ファイルと前記差分データとを元に更新後ファイルを復元するデータ更新システムにおける差分データ生成装置であって、前記更新後ファイル中のデータ列と一致するデータ列を前記更新前ファイルから検索する一致データ列検索手段と、前記検索結果に基づき、前記差分データとして、前記更新前ファイルの一部、あるいは全部から一致するデータ列を前記更新後ファイルへ移動してコピーすることを意味するMove命令を表すMoveデータと、当該差分データ中のデータ列を前記更新後ファイルへ追加してコピーすることを意味するAdd命令を表すAddデータとのいずれを生成するかを決定するMove/Add決定手段と、前記Moveデータを出力するMoveデータ出力手段と、前記Addデータを出力するAddデータ出力手段とを備え、0個、1個、あるいは複数の前記Moveデータと0個、1個、あるいは複数の前記Addデータとを有して構成される差分データを生成する差分データ生成装置を提供する。
【0017】
また、第6に、前記第5の構成において、前記Moveデータ出力手段は、前記Moveデータの開始を示す特定のデータからなる区切り子を出力する区切り子出力手段を備え、前記区切り子の後に前記Move命令を表現するデータを出力するものとする。
【0018】
また、第7に、前記第5の構成において、前記Addデータ出力手段は、前記Addデータ中に前記区切り子として用いられる特定のデータが存在する場合に、このデータに続けて区切り子ではないことを示す特定のデータを出力するものとする。
【0019】
また、第8に、前記第5の構成において、前記Move/Add決定手段は、前記一致するデータ列の長さが所定の閾値以上となる場合は前記Moveデータ出力手段よりMoveデータとして出力し、前記一致するデータ列の長さが所定の閾値未満となる場合は前記Addデータ出力手段よりAddデータとして出力するように決定するものとする。
【0020】
また、第9に、前記第8の構成において、前記Move/Add決定手段における閾値として、32ビットCPUを用いた計算システムにおけるプログラム及びデータを転送するデータ更新システムに用いる場合に、閾値を5バイトとするものとする。
【0021】
また、第10に、前記第8の構成において、前記Move/Add決定手段における閾値として、1つのバージョンの更新前ファイルと1つのバージョンの更新後ファイルとの間の差分データを生成する際に、異なる複数の閾値を用いて差分データ生成を実行し、大きさが最小となった場合の差分データを採用するものとする。
【0022】
また、第11に、前記第5の構成において、前記Move/Add決定手段は、前記一致するデータ列について、前記Moveデータで表現した場合と前記Addデータで表現した場合とにおける差分データの大きさを比較し、より小さくなる方に決定するものとする。
【0023】
また、第12に、前記第5の構成において、前記Moveデータ出力手段は、前記Moveデータの先頭バイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを設け、前記データ長継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報のみによって前記更新前ファイルよりコピーを行うデータ列の長さを表現し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記データ列の長さを表現する情報が継続することとしたデータ長情報を出力するものとする。
【0024】
また、第13に、前記第12の構成において、前記Moveデータ出力手段は、前記Moveデータの2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを設け、前記データ長継続フラグが所定の状態1を取っている場合は前記Moveデータの先頭バイトまたはワードから当該バイトまたはワードまでにおける情報によって前記更新前ファイルよりコピーを行うデータ列の長さを表現し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記データ列の長さを表現する情報が継続することとしたデータ長情報を出力するものとする。
【0025】
また、第14に、前記第5の構成において、前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルと前記更新後ファイルの少なくとも一方における絶対アドレスを用いたアドレス情報を出力するものとする。
【0026】
また、第15に、前記第5の構成において、前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差を示す相対アドレスを用いたアドレス情報を出力するものとする。
【0027】
また、第16に、前記第5の構成において、前記Moveデータ出力手段及び前記Addデータ出力手段は、前記更新後ファイルにおけるデータ列の順番に沿ってMoveデータ及びAddデータを生成出力するものとし、前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルにおける当該データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いたアドレス情報を出力するものとする。
【0028】
また、第17に、前記第15または16の構成において、前記Moveデータ出力手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の先頭バイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを設け、前記アドレス継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報のみによって前記相対アドレスを表現し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記相対アドレスを表現する情報が継続することとしたアドレス情報を出力するものとする。
【0029】
また、第18に、前記第17の構成において、前記Moveデータ出力手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを設け、前記アドレス継続フラグが所定の状態1を取っている場合は前記アドレス情報のデータ列の先頭バイトまたはワードから当該バイトまたはワードまでにおける情報によって前記相対アドレスを表現し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記相対アドレスを表現する情報が継続することとしたアドレス情報を出力するものとする。
【0030】
また、第19に、前記第15または16の構成において、前記Moveデータ出力手段は、前記Moveデータのアドレス情報において、同一の相対アドレス値が複数のMoveデータにおいて現れる場合に、該当する1つまたは複数の相対アドレス値については前記Moveデータの先頭バイトまたはワードにおいて1つあるいは複数のビットで表現することとする。
【0031】
また、第20に、前記第5の構成において、前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の位置を表す情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差、または前記更新前ファイルにおける前記データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いたアドレス情報を出力するものとし、前記Moveデータ中において1つあるいは複数のビットからなるアドレス変化フラグを設け、前記アドレス変化フラグが所定の状態1を取っている場合は前記データ列の長さを表現するデータ長情報の後に前記相対アドレスによるアドレス情報を出力し、前記アドレス変化フラグが前記状態1とは異なる所定の状態2を取っている場合は前回のMoveデータにおける相対アドレスと今回のMoveデータにおける相対アドレスとが同一であるとして前記相対アドレスを表現する情報を省略するものとする。
【0032】
また、第21に、前記第15,16,20のいずれかの構成において、前記Moveデータ出力手段は、前記Moveデータのアドレス情報における相対アドレスを、前回のMoveデータにおける相対アドレスからの変化量により表現することとする。
【0033】
本発明は、第22に、前記第5〜21のいずれかの構成のデータ更新システムの差分データ生成装置における各手段の機能をコンピュータにより実現するための差分データ生成プログラムを提供する。
【0034】
本発明は、第23に、1つのバージョンのデータである更新前ファイルと他のもう1つのバージョンのデータである更新後ファイルとの差を示す差分データを受信し、自装置で保持している更新前ファイルと前記差分データとを元に更新後ファイルを復元するデータ更新システムにおける更新後ファイル復元装置であって、前記差分データが、前記更新前ファイルの一部、あるいは全部から一致するデータ列を前記更新後ファイルへ移動してコピーすることを意味するMove命令を表すMoveデータと、当該差分データ中のデータ列を前記更新後ファイルへ追加してコピーすることを意味するAdd命令を表すAddデータとのいずれであるかを判定するMove/Add判定手段と、前記Moveデータに対応するデータ列を出力するMoveデータ復元手段と、前記Addデータに対応するデータ列を出力するAddデータ復元手段とを備え、前記差分データより更新後ファイルを生成する更新後ファイル復元装置を提供する。
【0035】
また、第24に、前記第23の構成において、前記Move/Add判定手段は、前記差分データにおいて、特定のデータからなる区切り子の後に設けられたMove命令を表現するデータをMoveデータとし、前記差分データの先頭または前回のMoveデータの終端から前記区切り子が出現するまでに設けられたAdd命令を表現するデータをAddデータとして区別するものとする。
【0036】
また、第25に、前記第24の構成において、前記Move/Add判定手段は、前記差分データにおいて、前記区切り子がデータ列中に現れ、かつ前記区切り子に続くデータが特定のものである場合は、前記区切り子ではなく、前記Addデータ中に存在する区切り子として用いられたデータそのものであるとする。
【0037】
また、第26に、前記第23の構成において、前記Moveデータ復元手段は、前記Moveデータに設けられるデータ長情報を判別して前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の長さを決定するものであり、前記Moveデータの先頭バイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを検出し、前記データ長継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報よりデータ長情報を判別して前記コピーを行うデータ列の長さを決定し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記データ長情報が継続するものと判定することとする。
【0038】
また、第27に、前記第26の構成において、前記Moveデータ復元手段は、前記Moveデータの2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを検出し、前記データ長継続フラグが所定の状態1を取っている場合は前記Moveデータの先頭バイトまたはワードから当該バイトまたはワードまでにおける情報よりデータ長情報を判別して前記コピーを行うデータ列の長さを決定し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記データ長情報が継続するものと判定することとする。
【0039】
また、第28に、前記第23の構成において、前記Moveデータ復元手段は、前記Moveデータに設けられるアドレス情報を判別して前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を決定するものであり、前記アドレス情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差、または前記更新前ファイルにおける前記データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスにより表現されたアドレス情報を判別するものとする。
【0040】
また、第29に、前記第28の構成において、前記Moveデータ復元手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の先頭バイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを検出し、前記アドレス継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報より前記相対アドレスのアドレス情報を判別して前記コピーを行うデータ列の位置を決定し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記アドレス情報が継続するものと判定することとする。
【0041】
また、第30に、前記第29の構成において、前記Moveデータ復元手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを検出し、前記アドレス継続フラグが所定の状態1を取っている場合は前記アドレス情報のデータ列の先頭バイトまたはワードから当該バイトまたはワードにおける情報より前記相対アドレスのアドレス情報を判別して前記コピーを行うデータ列の位置を決定し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記アドレス情報が継続するものと判定することとする。
【0042】
また、第31に、前記第28の構成において、前記Moveデータ復元手段は、前記Moveデータ中において1つあるいは複数のビットで表現されたアドレス情報を判別し、このアドレス情報に該当する1つまたは複数の相対アドレス値については同一の相対アドレス値として前記コピーを行うデータ列の位置を決定するものとする。
【0043】
また、第32に、前記第28の構成において、前記Moveデータ復元手段は、前記Moveデータ中において1つあるいは複数のビットからなるアドレス変化フラグを検出し、前記アドレス変化フラグが所定の状態1を取っている場合は前記コピーを行うデータ列の長さを表すデータ長情報の後に設けられる前記相対アドレスによるアドレス情報を判別し、前記アドレス変化フラグが前記状態1とは異なる所定の状態2を取っている場合は前回のMoveデータにおける相対アドレスと同一の相対アドレスを用いて前記コピーを行うデータ列の位置を決定するものとする。
【0044】
本発明は、第33に、前記第23〜32のいずれかの構成のデータ更新システムの更新後ファイル復元装置における各手段の機能をコンピュータにより実現するための更新後ファイル復元プログラムを提供する。
【0045】
上記構成によれば、差分データ生成時のMoveデータとAddデータのいずれを生成するかの閾値の設定、Moveデータにおけるサイズとアドレスの可変ビット長表現、Moveデータにおいて同一のアドレスが存在する場合のアドレス情報の省略などによって、差分データのデータ量を削減することが可能となる。これにより、データを転送する通信手段における負荷、及びデータを処理する装置の演算回路等における負荷やメモリ消費量などを軽減することが可能となる。
【0046】
【発明の実施の形態】
以下、図面を参照して本発明の実施形態を説明する。
本実施形態では、データ更新システムの一例として、携帯電話機等の携帯端末装置に格納されている動作プログラム等を含むデータのバージョンを更新する場合の構成及び動作の例を説明する。本実施形態は、差分データを移動体通信システムの無線通信網を介して携帯端末装置へ転送することによって、通信回線経由で容易に携帯端末装置内のデータを更新可能にしたものである。
【0047】
図1は本発明の一実施形態に係るデータ更新システムの機能構成を示すブロック図である。データ更新システムは、更新前ファイル及び更新後ファイルから差分データを生成する差分データ生成手段の機能を有する差分データ生成装置11と、差分データを転送するサーバ12と、サーバ12と無線通信網13を介して接続され前記差分データ及び更新前ファイルから更新後ファイルを復元する更新後ファイル復元手段の機能を有する携帯端末装置14とを備えて構成される。なお本実施形態では、サーバ12及び無線通信網13等によって通信手段が構成される。
【0048】
差分データ生成装置11は、更新前ファイル及び更新後ファイルとなる複数のバージョンのデータを格納したデータベース15と、データベース15に格納された更新前ファイルと更新後ファイルとから後述する手順により差分データを生成する差分データ生成部16とを有して構成される。サーバ12は、移動体通信システムにおいて各種データの配信などを行うために設けられるもので、対象となる携帯端末装置14へ差分データを送信するようになっている。
【0049】
携帯端末装置14は、無線通信により各種データや音声信号等の送受信を行う無線通信部17と、各部の動作制御を行う制御部18と、転送された差分データと更新前ファイルとから後述する手順により更新後ファイルを復元して生成する更新後ファイル復元部19と、更新後ファイルを格納するフラッシュROM等からなるデータ格納部20とを有して構成される。
【0050】
上記構成のデータ更新システムにおいて、差分データ生成装置11により更新前ファイルと更新後ファイルとから差分データを生成し、この差分データをサーバ12より無線通信網13を介して携帯端末装置14に転送する。携帯端末装置14では、更新後ファイル復元部19によってサーバ12より転送された差分データと現在格納している更新前ファイルとから更新後ファイルを復元し、この更新後ファイルをデータ格納部20に格納する。これにより、携帯端末装置14を使用者が使用している状態であっても、適当なタイミングで無線通信網13を介して差分データを転送することによって、容易に動作プログラム等のバージョンを更新することが可能となる。
【0051】
ここで、本実施形態における差分データの生成、及び更新後ファイルの復元についての概要を説明する。図2は本実施形態における差分データの生成方法の概略を示す説明図である。差分データの生成時には、図2(A)に示す更新前ファイルと図2(B)に示す更新後ファイルとから差分抽出を行って図2(C)に示す差分データを生成する。この場合、更新後ファイルのデータ列において更新前ファイルのデータ列と一致する部分を検索し、一致するデータ列については、更新前ファイルからコピーするための一致部分のサイズ(データ長情報)とアドレス(アドレス情報)により示されるMoveデータを生成する。また、一致しないデータ列については、そのデータ列を書き込むためのAddデータを生成する。
【0052】
本実施形態では、更新前ファイル内のデータ列の一部を移動(コピー)してきて更新後ファイルの一部を生成する操作をMove操作と呼び、このMove操作の内容を記述したデータをMoveデータと呼ぶ。また、更新前ファイルを参照せずにデータ列を追加することで更新後ファイルの一部を生成する操作をAdd操作と呼び、このAdd操作の内容を記述したデータをAddデータと呼ぶ。差分データは、MoveデータとAddデータとの組み合わせによって構成され、更新後ファイルを復元する際のMove命令及びAdd命令として用いられる。すなわち、差分データは、0個、1個、あるいは複数のMove命令を表すMoveデータと、0個、1個、あるいは複数のAdd命令を表すAddデータとを有して構成される。
【0053】
図2の例では、更新前ファイルのアドレスq3から更新後ファイルのアドレスp1へ4バイトコピー(「a,b,c,d」をコピー)するためのMoveデータ、次に「e,f,g,h」を書き込むためのAddデータ、次に更新前ファイルのアドレスq2から更新後ファイルのアドレスp2へ3バイトコピー(「x,y,z」をコピー)するためのMoveデータ、次に「i,j,k,l,m」を書き込むためのAddデータが生成される。
【0054】
図3は本実施形態における更新後ファイルの復元方法の概略を示す説明図である。更新後ファイルの復元時には、図3(A)に示す差分データと図3(B)に示す更新前ファイルとから図3(C)に示す更新後ファイルを生成する。この場合、差分データにおけるMoveデータによるMove命令とAddデータによるAdd命令とに基づいて、更新前ファイルから一致するデータ列がコピーされて移動され、一致しない新たなデータ列が書き込まれて追加される。
【0055】
図3の例では、まず▲1▼でMove命令により更新前ファイルのアドレスq3から更新後ファイルのアドレスp1へ4バイトコピー(「a,b,c,d」がコピー)され、次に▲2▼でAdd命令により「e,f,g,h」が書き込まれ、次に▲3▼でMove命令により更新前ファイルのアドレスq2から更新後ファイルのアドレスp2へ3バイトコピー(「x,y,z」がコピー)され、次に▲4▼でAdd命令により「i,j,k,l,m」が書き込まれる。以上のようにして、Moveデータ及びAddデータからなる差分データを用いて更新前ファイルから更新後ファイルが復元生成される。
【0056】
本実施形態では、差分データにおいて以下に述べる特徴を持たせることによって、差分データのデータ量を削減している。
【0057】
(1)一致するデータ列が所定長未満の場合、MoveデータではなくAddデータにする。Moveデータにおいてサイズとアドレスを何バイトで表現するかにも関係するが、小さいデータ列の移動に関するMoveデータは、データそのものが示されるAddデータよりもデータ量が大きくなってしまう場合がある。本実施形態では、例えば閾値を5バイトとし、この閾値未満、すなわち一致する部分が4バイト以下のデータ列についてはAddデータとして差分データを生成してデータ量を小さくする。
【0058】
(2)Moveデータにおいて、サイズとアドレスをそれぞれ可変ビット長で表現する。可変ビット長とすることにより、小さい値の場合は小さいデータ量で表現することが可能である。なお、サイズとアドレスの少なくとも一方のみを可変ビット長で表現してもよい。本実施形態では、アドレスについては相対アドレスを使用し、更新前ファイル上でのアドレスを基準として更新後ファイルにおけるアドレスの変化量(相対移動距離)を表すこととする。
【0059】
(3)Moveデータにおいて、アドレスに相対アドレスを用いた場合、当該アドレスが直前のMoveデータにおけるアドレス(相対移動距離)と同じ場合はアドレスを省略する。本実施形態では、更新後ファイルのデータ列を先頭から順に復元するように差分データを形成するものとする。このため、直前のMoveデータのアドレスと同じ場合、すなわちコピーするデータ列の相対移動距離が同じで平行移動状態でコピーする場合は、直前のデータ列の後に続けてコピーすれば良いことになる。この場合、同一のアドレスを省略することによってデータ量を小さくする。
【0060】
なお、同一のアドレスが複数出現する場合、フラグ等によって前回と同一のアドレスであることを示したり、出現頻度の高い1つまたは複数のアドレスを1つまたは複数のビットで表現するようにしてデータ量を削減することも可能である。
【0061】
前記相対アドレスとしては、更新前ファイルにおけるコピーすべきデータ列の位置(先頭及び/または終端)と更新後ファイルにおける当該データ列の位置(先頭及び/または終端)との差を示す相対アドレスを用いることができる。この場合、複数のMoveデータについて更新後ファイルにおけるデータ列の位置が前後したりランダムに並んでいても対応可能である。また、更新後ファイルのデータ列を先頭から順に復元するように、更新後ファイルにおけるデータ列の順番に沿ってMoveデータ及びAddデータを生成して差分データを構成する場合は、更新前ファイルにおけるコピーすべきデータ列の先頭位置と更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いることができる。本実施形態ではこの相対アドレスを採用する。この場合、上記の同一アドレスの省略についても対応可能である。さらに、相対アドレスは、前回のMoveデータにおける相対アドレスからの変化量により表現することも可能である。
【0062】
次に、差分データのフォーマットの一例を示す。図4に示すように、差分データにおけるMoveデータは、Moveデータの開始を示す区切り子であるデリミタ101と、コピーすべきデータ列のサイズを示すデータ長情報が格納されるサイズフィールド102と、コピーすべきデータ列の相対アドレスを示すアドレス情報が格納されるアドレスフィールド103との3つの要素から構成される。
【0063】
デリミタ101は、サイズは1バイトで0x0F(2進表記で00001111)を用いることとする。本明細書では、0x**は16進表記を示すものとする。なお、デリミタは複数バイトで表現したり、1ないし複数のビットやワードで表現することも可能である。
【0064】
サイズフィールド102は、コピーすべきデータ列のサイズ(以下、Moveサイズと称する場合もある)を格納する可変長のフィールドであり、1〜3バイトで構成される。このサイズフィールド102について、図5(A)に示すように3バイトを順にA,B,Cとし、各バイトを図5(B),(C),(D)に示すように表して詳細を説明する。
【0065】
図5(B)に示す1バイト目のバイトAにおいて、1番目のビットA8はデータ長継続フラグに相当するフィールド長フラグ111、2番目のビットA7はアドレス変化フラグ112となっている。以降のビットA6〜A1にはMoveサイズの最下位6ビットが入る。ビットA8のフィールド長フラグ111の値により、次のバイトもサイズフィールドであるかが示される。ビットA8が「1(フラグが立っている状態、以下同様)」であれば次のバイトもサイズフィールドであり、「0(フラグが寝ている状態、以下同様)」であればサイズフィールドはバイトAのみとなる。また、ビットA7のアドレス変化フラグ112の値により、サイズフィールドの次にアドレスフィールドが続くかどうかが示される。ビットA7が「1」であればサイズフィールドの次にアドレスフィールドが続き、「0」であればアドレスフィールドが無く、直前のMove操作時と同じアドレスであるものとする。
【0066】
図5(C)に示す2バイト目のバイトBにおいて、1番目のビットB8はバイトAと同様にデータ長継続フラグに相当するフィールド長フラグ111となっている。以降のビットB7〜B1にはMoveサイズの第13ビット〜第7ビットが入る。また、図5(D)に示す3バイト目のバイトCについても同様に、1番目のビットC8はフィールド長フラグ111となっており、以降のビットC7〜C1にはMoveサイズの第20ビット〜第14ビットが入る。ビットB8,C8のフィールド長フラグ111の値により、次のバイトもサイズフィールドであるかが示され、値が「1」であれば次のバイトもサイズフィールドであり、「0」であればサイズフィールドはそのバイトまでとなる。
【0067】
このサイズフィールド102の具体例を図6に示す。この図6の例は、Moveサイズが3バイトで表され、そのサイズの値は33826バイトであり、2番目のビットのアドレス変化フラグ112が「0」であるためアドレスフィールドが後に続かないことが示されている。なお、フィールド長フラグ111やアドレス変化フラグ112は、複数のビットで表現してもよい。また、フラグの「0」「1」は反対の状態を表現するようにしてもよい。
【0068】
アドレスフィールド103は、コピーすべきデータ列の相対アドレス(以下、Moveアドレスと称する場合もある)を格納する可変長のフィールドであり、1〜3バイトで構成される。このアドレスフィールド103は前記サイズフィールド102のアドレス変化フラグ112が「1」の場合に設けられる。このアドレスフィールド103について、図7(A)に示すように3バイトを順にX,Y,Zとし、各バイトを図7(B),(C),(D)に示すように表して詳細を説明する。
【0069】
図7(B)に示す1バイト目のバイトXにおいて、1番目のビットX8はアドレス継続フラグに相当するフィールド長フラグ121、2番目のビットX7はアドレス符号ビット122となっている。以降のビットX6〜X1にはMoveアドレスの絶対値の最下位6ビットが入る。ビットX8のフィールド長フラグ121の値により、次のバイトもアドレスフィールドであるかが示される。ビットX8が「1」であれば次のバイトもアドレスフィールドであり、「0」であればアドレスフィールドはバイトXのみとなる。また、ビットX7のアドレス符号ビット122の値により、相対アドレスの正負が表現される。ビットX7が「1」であればアドレスは負、「0」であればアドレスは正である。
【0070】
図7(C)に示す2バイト目のバイトYにおいて、1番目のビットY8はバイトXと同様にアドレス継続フラグに相当するフィールド長フラグ121となっている。以降のビットY7〜Y1にはMoveアドレスの絶対値の第13ビット〜第7ビットが入る。また、図7(D)に示す3バイト目のバイトZについても同様に、1番目のビットZ8はフィールド長フラグ121となっており、以降のビットZ7〜Z1にはMoveアドレスの絶対値の第20ビット〜第14ビットが入る。ビットY8,Z8のフィールド長フラグ121の値により、次のバイトもアドレスフィールドであるかが示され、値が「1」であれば次のバイトもアドレスフィールドであり、「0」であればアドレスフィールドはそのバイトまでとなる。
【0071】
このアドレスフィールド103の具体例を図8に示す。この図8の例は、Moveアドレスが2バイトで表され、2番目のビットのアドレス符号ビット122が「1」であるため相対アドレスの符号が負であり、そのアドレスの値は−4100バイトであることが示されている。なお、フィールド長フラグ121は、複数のビットで表現してもよい。また、フラグの「0」「1」は反対の状態を表現するようにしてもよい。
【0072】
一方、差分データにおけるAddデータは、原則として、追加すべきデータ列がそのままAddデータとなる。ただし、もとのデータ列においてMoveデータのデリミタと同じ0x0Fが存在する場合は、デリミタと区別するため、これに対応するAddデータは0x0F 0x00 と2バイトのデータとする。
【0073】
上述したコピーすべきデータ列をMoveデータで表現するかAddデータで表現するかの閾値は、プロセッサとして32ビットCPUを用いた計算システムにおけるプログラム及びデータを転送する場合などでは、サンプルデータで演算を行った結果、閾値を5バイトとすると差分データのデータ量を最小にできることがわかった。図9は本実施形態に係る差分データ生成手順によってサンプルデータの差分データを生成した結果を示すグラフである。この図9は、閾値を3バイトから8バイトまで変化させたときの差分データのデータ量の変化を示したものであり、閾値が5バイトのときにデータ量が最小となっている。また、上記フォーマットのように、Moveデータにおいて、デリミタを1バイト、Moveサイズを1〜3バイト、Moveアドレスを1〜3バイトで表現する場合、Moveサイズの期待値を2バイト、Moveアドレスの期待値を2バイトとすると、閾値は同様に5バイトにするのが差分データのデータ量削減のためには好ましい。
【0074】
次に、差分データ生成部と更新後ファイル復元部の機能構成について説明する。図10は図1の差分データ生成装置11における差分データ生成部16の機能構成を示すブロック図である。この差分データ生成部16は、プロセッサ及びメモリを含む演算処理回路、及びこの演算処理回路において動作するソフトウェアプログラムによって、各部の機能が実現される。
【0075】
差分データ生成部16は、差分データを生成する各手順の制御を司る差分データ生成制御手段31、更新前ファイルのデータを記憶する更新前データ記憶手段32、更新後ファイルのデータを記憶する更新後データ記憶手段33、更新前ファイルと更新後ファイルとで一致するデータ列を検索する一致データ列検索手段34、一致データ列の検索結果により差分データとしてMoveデータとAddデータのいずれを生成するかを決定するMove/Add決定手段35を備えている。また、Move/Add決定手段35の結果に基づき、Moveデータを生成して出力するMoveデータ出力手段36と、Addデータを生成して出力するAddデータ出力手段37と、MoveデータとAddデータとを組み合わせた差分データを記憶する差分データ記憶手段38とを備えている。
【0076】
さらに、Moveデータを生成出力した場合に今回のMoveアドレスを記憶するMoveアドレス記憶手段39を備えている。Moveデータ出力手段36は、AddデータとMoveデータとの区切りを示すためにMoveデータの先頭に設けられるデリミタを出力するデリミタ出力手段(区切り子出力手段)40、コピーするMoveデータのサイズを出力するMoveサイズ出力手段41、Moveデータをコピーする更新後ファイル上での相対アドレスを出力するMoveアドレス出力手段42、Moveアドレス記憶手段39に記憶されているアドレスとMoveアドレス出力手段42より出力されるアドレスとからMoveアドレスが変化したかを判定するアドレス変化判定手段43、アドレス変化判定手段43の結果に基づきアドレス変化フラグを設定するアドレスフラグ設定手段44を備えている。これらの差分データ生成部16の機能については、後述する差分データ生成の動作手順の説明において詳しく述べる。
【0077】
図11は図1の携帯端末装置14における更新後ファイル復元部19の機能構成を示すブロック図である。この更新後ファイル復元部19は、プロセッサ及びメモリを含む演算処理回路、及びこの演算処理回路において動作するソフトウェアプログラムによって、各部の機能が実現される。
【0078】
更新後ファイル復元部19は、更新後ファイルを復元する各手順の制御を司る更新後ファイル復元制御手段51、転送された差分データを記憶する差分データ記憶手段52、更新前ファイルのデータを記憶する更新前データ記憶手段53、差分データの対象部分がMoveデータとAddデータのいずれであるかを判定するMove/Add判定手段54を備えている。また、Move/Add判定手段54の結果に基づき、Moveデータに対応するデータ列を更新前ファイルよりコピーして出力するMoveデータ復元手段55と、Addデータに対応するデータ列を出力するAddデータ復元手段56と、Moveデータ及びAddデータにより復元された更新後ファイルのデータを記憶する更新後データ記憶手段57とを備えている。
【0079】
さらに、Move操作により更新後ファイルのデータを復元した場合に今回のMoveアドレスを記憶するMoveアドレス記憶手段58を備えている。Moveデータ復元手段55は、コピーするMoveデータのサイズを判定するMoveサイズ判定手段59、コピーする更新後ファイル上での相対アドレスを判定するMoveアドレス判定手段60、Moveデータ中のアドレス変化フラグに基づきMoveアドレスに変化があるかを判定するアドレス変化判定手段61を備えている。これらの更新後ファイル復元部19の機能については、後述する更新後ファイル復元の動作手順の説明において詳しく述べる。
【0080】
次に、本実施形態の差分データ生成部16における差分データ生成の動作手順を説明する。初めに、差分データ生成の概要を図12を参照して説明する。図12は本実施形態に係る差分データ生成手順の概要を示すフローチャートである。差分データの生成は、例えば、携帯端末装置14において更新前ファイル及び更新後ファイルを格納するフラッシュROM等の消去、書き込み単位に合わせて、所定サイズのブロックごとに行うようにする。
【0081】
差分データ生成部16は、まず一致データ列検索手段34によって、更新前データ記憶手段32に記憶された更新前ファイルと更新後データ記憶手段33に記憶された更新後ファイルのデータ列を参照し、更新前ファイルの中から更新後ファイルのデータ列と一致するデータ列を先頭から検索する(ステップS101)。そして、一致データ列検索手段34での検索結果に基づき、Move/Add決定手段35によってMoveデータとAddデータのいずれを生成するかを決定する。ここでは、まず一致するデータ列があるか否かを判定し(ステップS102)、一致するデータ列がある場合はさらに一致するデータ列のデータ長が所定の閾値以上であるか否かを判定する(ステップS103)。本実施形態では、例えば、一致するデータ列のデータ長が5以上の場合はMoveデータとして出力し、4以下の場合はAddデータとして出力する。
【0082】
ステップS102において一致するデータ列が無い場合、及びステップS103で閾値未満である場合は、Addデータ出力手段37によってそのデータ列をAddデータとして出力する(ステップS104)。
【0083】
一方、ステップS103で閾値以上である場合は、Moveデータ出力手段36によって以降のMoveデータ出力手順を実行する。この場合、まずデリミタ出力手段40によって、以降のデータがMoveデータであることを示す所定のデータ(0x0F)からなるデリミタを出力し(ステップS105)、次にアドレス変化判定手段43によってMoveアドレス記憶手段39に記憶されているアドレスを参照してMoveアドレスが前回と同じか否かを判定する(ステップS106)。Moveアドレスが前回と同じ場合は、アドレスフラグ設定手段44によりアドレス変化フラグを「0」に設定し(ステップS107)、Moveサイズ出力手段41により一致するデータ列のサイズをMoveサイズとして出力する(ステップS108)。
【0084】
また、ステップS106でMoveアドレスが前回と異なる場合は、アドレスフラグ設定手段44によりアドレス変化フラグを「1」に設定し(ステップS109)、Moveサイズ出力手段41により一致するデータ列のサイズをMoveサイズとして出力する(ステップS110)。次いで、Moveアドレス出力手段42によりMoveデータをコピーする更新後ファイル上での相対アドレスを出力する(ステップS111)。そしてこのとき、Moveアドレス記憶手段39に今回のMoveアドレスを記憶する(ステップS112)。
【0085】
その後、全データについて処理が終了したかを判断し(ステップS113)、終了していない場合はステップS101に戻り、更新後ファイルの終端まで全データ分の処理が終了するまで前記と同様にステップS101〜S112の処理を繰り返す。以上の手順により、更新前ファイルとの差分を表すデータとして、MoveデータとAddデータとを組み合わせた差分データが生成され、差分データ記憶手段38に記憶される。
【0086】
次に、上記差分データの生成手順をより詳細に説明する。本実施形態では、図4〜図8において例示したフォーマットで構成される差分データを生成する場合の手順を示す。
【0087】
図13は本実施形態に係る差分データ生成手順の全体を示すフローチャートである。まず、更新後ファイルにおいて更新前ファイルと一致するデータ列を検索するために、更新前ファイルのデータ列と更新後ファイルのデータ列のそれぞれについてハッシュテーブルを作成する(ステップS121)。そして、ハッシュテーブルを用いて、更新後ファイルのデータ列において、更新前ファイルの中から一致するデータ列を検索する(ステップS122)。ここでは、一致データ列検索手段34において、公知のハッシュ値によるインデックスを利用したデータ列の検索を行い、更新前と更新後のデータ列を比較する。この検索処理により、一致するデータ列の位置及び長さが求められる。このようにハッシュ値を利用した一致データ列の検索を行うことによって、検索処理を高速化できる。
【0088】
次に、一致するデータ列のデータ長を参照し、このデータ長を閾値である5と比較することによって、Moveデータとして出力する方がデータサイズが小さいか否かを判定する(ステップS123)。データ長が5バイト以上である場合はMoveデータとして出力する方がデータサイズが小さいと推定し、Moveデータとして出力する処理手順を実行し(ステップS124)、今回のMoveアドレスを記憶する(ステップS125)。一方、データ長が4バイト以下である場合はMoveデータとして出力する方がデータサイズが大きくなってしまうと推定し、Addデータとして出力する処理手順を実行する(ステップS126)。そして、全データについて処理が終了したかを判断し(ステップS127)、終了していない場合はステップS122に戻り、全データ分の処理が終了するまでステップS122〜S126の処理を繰り返す。
【0089】
図14は図13のステップS124におけるMoveデータとして出力する処理手順を示すフローチャートである。この手順では、まず以降のデータ列がMoveデータであることを示すデリミタ(0x0F)を出力する(ステップS131)。次に、一致するデータ列についてMoveサイズの1バイト目を出力する処理手順を実行する(ステップS132)。続いて、Moveサイズの表現に次のバイトも使用するかを判定し(ステップS133)、使用する場合はMoveサイズの2バイト目以降を出力する処理手順を実行する(ステップS134)。そして、このステップS133及びS134の処理を繰り返す。
【0090】
ステップS133でMoveサイズの表現に次のバイトを使用しない場合は、Moveアドレスが前回と同じか否かを判定する(ステップS135)。ここでMoveアドレスが前回と異なる場合は、一致するデータ列についてMoveアドレスの1バイト目を出力する処理手順を実行する(ステップS136)。続いて、Moveアドレスの表現に次のバイトも使用するかを判定し(ステップS137)、使用する場合はMoveアドレスの2バイト目以降を出力する処理手順を実行する(ステップS138)。そして、このステップS137及びS138の処理を繰り返す。
【0091】
ステップS135でMoveアドレスが前回と同じ場合、及びステップS137でMoveアドレスの表現に次のバイトを使用しない場合は、このMoveデータ出力処理を抜けて図13のステップS125に進む。
【0092】
図15は図14のステップS132におけるMoveサイズの1バイト目を出力する処理手順を示すフローチャートである。この手順では、まずMoveサイズが6ビット以下で表現可能か否かを判定する(ステップS141)。6ビット以下で表現可能な場合は、最上位ビット、すなわちサイズフィールドの1バイト目のフィールド長フラグを「0」にする(ステップS142)。また、6ビット以下で表現できない場合は、最上位ビットを「1」にする(ステップS143)。次に、Moveアドレスが前回と同じか否かを判定する(ステップS144)。Moveアドレスが前回と同じ場合は、上から2番目のビット、すなわちサイズフィールドのアドレス変化フラグを「0」にする(ステップS145)。また、Moveアドレスが前回と異なる場合は、上から2番目のビットを「1」にする(ステップS146)。次いで、Moveサイズの最下位6ビットを出力する(ステップS147)。そして、このMoveサイズ1バイト目出力処理を抜けて図14のステップS133に進む。
【0093】
図16は図14のステップS134におけるMoveサイズの2バイト目以降を出力する処理手順を示すフローチャートである。この手順では、まずMoveサイズの未出力ビット数が7以下か否かを判定する(ステップS151)。未出力ビット数が7以下の場合は、最上位ビット、すなわちサイズフィールドの当該バイトのフィールド長フラグを「0」にする(ステップS152)。また、未出力ビット数が7より大きい場合は、最上位ビットを「1」にする(ステップS153)。次に、Moveサイズの未出力ビットのうち、最下位7ビットを出力する(ステップS154)。そして、このMoveサイズ2バイト目以降出力処理を抜けて図14のステップS133に進む。
【0094】
図17は図14のステップS136におけるMoveアドレスの1バイト目を出力する処理手順を示すフローチャートである。この手順では、まずMoveアドレスの絶対値が6ビット以下で表現可能か否かを判定する(ステップS161)。6ビット以下で表現可能な場合は、最上位ビット、すなわちアドレスフィールドの1バイト目のフィールド長フラグを「0」にする(ステップS162)。また、6ビット以下で表現できない場合は、最上位ビットを「1」にする(ステップS163)。次に、相対アドレスの符号が正か否かを判定する(ステップS164)。相対アドレスの符号が正の場合は、上から2番目のビット、すなわちアドレスフィールドのアドレス符号ビットを「0」にする(ステップS165)。また、相対アドレスの符号が負の場合は、上から2番目のビットを「1」にする(ステップS166)。次いで、Moveアドレスの絶対値の最下位6ビットを出力する(ステップS167)。そして、このMoveアドレス1バイト目出力処理を抜けて図14のステップS137に進む。
【0095】
図18は図14のステップS138におけるMoveアドレスの2バイト目以降を出力する処理手順を示すフローチャートである。この手順では、まずMoveアドレスの絶対値の未出力ビット数が7以下か否かを判定する(ステップS171)。未出力ビット数が7以下の場合は、最上位ビット、すなわちアドレスフィールドの当該バイトのフィールド長フラグを「0」にする(ステップS172)。また、未出力ビット数が7より大きい場合は、最上位ビットを「1」にする(ステップS173)。次に、Moveアドレスの未出力ビットのうち、最下位7ビットを出力する(ステップS174)。そして、このMoveアドレス2バイト目以降出力処理を抜けて図14のステップS137に進む。
【0096】
図19は図13のステップS126におけるAddデータとして出力する処理手順を示すフローチャートである。この手順では、更新後ファイルにおいて更新前ファイルと一致しないデータ列、及び4バイト以下の一致データ列について、そのバイナリデータを出力する(ステップS181)。そして、出力するデータがデリミタと同じ0x0Fであるか否かを判定する(ステップS182)。出力するデータが0x0Fでない場合は、このAddデータ出力処理を終了する。一方、出力するデータが0x0Fの場合は、続いて0x00を出力し(ステップS183)、その後Addデータ出力処理を終了する。このAddデータ出力処理を終了すると、図13のステップS127に進む。
【0097】
上記のようにして生成されたMoveデータとAddデータとを組み合わせた差分データは、差分データ記憶手段38に一旦記憶される。その後、差分データにヘッダやCRC等が付加され、必要に応じて圧縮処理が施されて差分ファイルが生成され、差分データ生成装置11からサーバ12に転送される。そして、この差分ファイルは、サーバ12から無線通信網13を介して携帯端末装置14に転送され、携帯端末装置14の更新後ファイル復元部19において更新前ファイルと差分データとから更新後ファイルを生成することでデータの更新が行われる。
【0098】
このように本実施形態の差分データ生成装置及び方法によれば、差分データ生成時のMoveデータとAddデータのいずれを生成するかの閾値の設定、Moveデータにおけるサイズとアドレスの可変ビット長表現などによって、差分データのデータ量をより小さくすることができる。これにより、データを転送する通信回線における負荷、及びデータを処理する装置の演算回路等における負荷やメモリ消費量を軽減することができる。
【0099】
次に、本実施形態の携帯端末装置14における更新後ファイル復元の動作手順を説明する。図20は本実施形態に係る更新後ファイル復元手順の全体を示すフローチャートである。
【0100】
更新後ファイル復元部19は、まずMove/Add判定手段54によって差分データ記憶手段52に記憶された差分データの先頭の1バイトを読み込み(ステップS201)、読み込んだバイトがデリミタと同一の0x0Fであるか否かを判定する(ステップS202)。そのバイトが0x0Fでない場合は、Addデータの一部であると判定されるため、当該バイトを更新後ファイルのデータとしてAddデータ復元手段56より出力する(ステップS203)。
【0101】
ステップS202で読み込んだバイトが0x0Fである場合は、さらに次の1バイトを読み込み(ステップS204)、読み込んだバイトが0x00であるかを判定する(ステップS205)。そのバイトが0x00である場合は、直前のバイトの0x0FがデリミタではなくてAddデータの一部であると判定されるため、0x0Fを更新後ファイルのデータとしてAddデータ復元手段56より出力する(ステップS206)。一方、ステップS204で読み込んだバイトが0x00でない場合は、直前のバイトの0x0FがMoveデータの開始を示すデリミタであると判定されるため、Moveデータ復元手段55により以降のデータについてMove操作による復元処理手順を実行する(ステップS207)。
【0102】
そして、差分データの終端まで読み込んだか否かを判定し(ステップS208)、差分データの終端まで読み込みが終了していない場合は、次の1バイトを読み込み(ステップS209)、ステップS202に戻って差分データの終端まで全データ分の処理が終了するまで前記と同様にステップS202〜S208の処理を繰り返す。以上の手順により、差分データと更新前ファイルのデータとからMove操作及びAdd操作により更新後ファイルが復元生成され、更新後データ記憶手段57に記憶される。
【0103】
図21は図20のステップS207におけるMove操作による復元処理手順を示すフローチャートである。この手順では、まずMoveデータ復元手段55のアドレス変化判定手段61によりMoveデータの上から2番目のビット、すなわちサイズフィールドのアドレス変化フラグが「0」であるか否かを判定する(ステップS211)。このアドレス変化フラグが「0」である場合は、Moveアドレス判定手段60によりMoveアドレス記憶手段58に記憶されているMoveアドレスを読み出し、Moveアドレスを前回と同じ値に決定する(ステップS212)。次いで、Moveサイズ判定手段59によりMoveサイズの判定処理手順を実行する(ステップ213)。一方、アドレス変化フラグが「1」である場合は、Moveアドレスを決定せずにステップ213のMoveサイズ判定処理手順に進む。
【0104】
次に、Moveアドレス判定手段60によってMoveアドレスをすでに決定したか否かを判定し(ステップS214)、まだMoveアドレスを決定していない場合は、次のバイトを読み込み(ステップS215)、Moveアドレス判定手段60によりMoveアドレスの判定処理手順を実行する(ステップ216)。
【0105】
ステップS214ですでにMoveアドレスが決定されている場合、及びステップ216でのMoveアドレス判定処理手順の後に、決定したMoveサイズ及びMoveアドレスに基づいて、更新前ファイルのデータ列をコピーし、更新後ファイルのデータとしてMoveデータ復元手段55より出力する(ステップS217)。そして、今回のMoveアドレスをMoveアドレス記憶手段58に記憶する(ステップS218)。そして、このMove操作復元処理を抜けて図20のステップS208に進む。
【0106】
図22は図21のステップS213におけるMoveサイズ判定処理手順を示すフローチャートである。この手順では、まずMoveデータの1バイト目について、下位6ビットをMoveサイズの下位6ビットとする(ステップS221)。次いで、このバイトの最上位ビット、すなわちサイズフィールドの1バイト目のフィールド長フラグが「1」であるか否かを判定する(ステップS222)。フィールド長フラグが「1」である場合は、次のバイトを読み込み(ステップS223)、そのバイトの下位7ビットをMoveサイズの上位7ビットに追加する(ステップS224)。
【0107】
そして、ステップS222に戻り、2バイト目以降についてもこのバイトの最上位ビット、すなわちサイズフィールドの当該バイトのフィールド長フラグが「1」であるか否かを判定し、フィールド長フラグが「1」である場合は前記と同様にステップS223〜S224の処理を行う。
【0108】
一方、当該バイトの最上位ビットが「0」である場合は、以降のバイトにサイズフィールドが継続しないため、ここまでのMoveデータによりMoveサイズが決定する(ステップS225)。そして、このMoveサイズ判定処理を抜けて図21のステップS214に進む。
【0109】
図23は図21のステップS216におけるMoveアドレス判定処理手順を示すフローチャートである。この手順では、まずMoveデータのアドレスフィールドの1バイト目について、上から2番目のビット、すなわちアドレスフィールドのアドレス符号ビットが「0」であるか否かを判定する(ステップS231)。アドレス符号ビットが「0」である場合は、Moveアドレスの符号を正に設定する(ステップS232)。一方、アドレス符号ビットが「1」である場合は、Moveアドレスの符号を負に設定する(ステップS233)。そして、このバイトの下位6ビットをMoveアドレスの絶対値の下位6ビットとする(ステップS234)。
【0110】
次に、このバイトの最上位ビット、すなわちアドレスフィールドの1バイト目のフィールド長フラグが「1」であるか否かを判定する(ステップS235)。フィールド長フラグが「1」である場合は、次のバイトを読み込み(ステップS236)、そのバイトの下位7ビットをMoveアドレスの絶対値の上位7ビットに追加する(ステップS237)。
【0111】
そして、ステップS235に戻り、2バイト目以降についてもこのバイトの最上位ビット、すなわちアドレスフィールドの当該バイトのフィールド長フラグが「1」であるか否かを判定し、フィールド長フラグが「1」である場合は前記と同様にステップS236〜S237の処理を行う。
【0112】
一方、当該バイトの最上位ビットが「0」である場合は、以降のバイトにアドレスフィールドが継続しないため、ここまでのMoveデータによりMoveアドレスが決定する(ステップS238)。そして、このMoveアドレス判定処理を抜けて図21のステップS217に進む。
【0113】
上記のように復元された生成された更新後ファイルのデータは、更新後データ記憶手段57に一旦記憶される。その後、フラッシュROM等からなるデータ格納部20に更新後ファイルが書き込まれて格納され、更新前ファイルと置き換えられる。
【0114】
このように本実施形態の更新後ファイル復元装置及び方法によれば、データ量を削減して生成された差分データと自装置が保持している更新前ファイルとから更新後ファイルを生成でき、少量の更新用の差分データを転送するだけで簡便にデータの更新が可能である。また、データを処理する装置の演算回路等における負荷やメモリ消費量を軽減することができる。
【0115】
なお、本発明は上述した実施形態に何ら限定されるものではなく、その要旨を逸脱しない範囲において種々の態様で実施し得るものである。上記実施形態では、コピーすべきデータ列をMoveデータで表現するかAddデータで表現するかの閾値は、予め5バイトに設定して差分データを生成するようにしたが、これに限らず、1つのバージョンの更新前ファイルと1つのバージョンの更新後ファイルとの間の差分データを生成する際に、異なる複数の閾値を用いて差分データ生成処理を実行し、大きさが最小となった場合の差分データを採用するようにしてもよい。
【0116】
また、コピーすべきデータ列をMoveデータで表現するかAddデータで表現するかを決定する際に、更新前ファイルと更新後ファイルとで一致するデータ列について、Moveデータで表現した場合とAddデータで表現した場合とにおける差分データの大きさを比較し、より小さくなる方に決定することも可能である。
【0117】
また、差分データのMoveデータにおけるMoveアドレスのアドレス情報は、相対アドレスを用いて表現したが、更新前ファイルと更新後ファイルの少なくとも一方の絶対アドレスを用いてもよい。
【0118】
また、Moveデータなどのデータはバイトで表現したが、ワードで表現する場合にも同様に適用可能である。
【0119】
【発明の効果】
以上説明したように本発明によれば、一つのバージョンのデータを別のバージョンのデータに更新するためのデータ更新システムにおいて、データ更新に用いる差分データのデータ量を削減することが可能となる。
【図面の簡単な説明】
【図1】本発明の一実施形態に係るデータ更新システムの機能構成を示すブロック図
【図2】本発明の一実施形態における差分データの生成方法の概略を示す説明図
【図3】本発明の一実施形態における更新後ファイルの復元方法の概略を示す説明図
【図4】本実施形態において用いる差分データにおけるMoveデータのフォーマットの一例を示す説明図
【図5】図4のMoveデータにおけるサイズフィールドのフォーマットの一例を示す説明図
【図6】図4のMoveデータにおけるサイズフィールドの具体例を示す説明図
【図7】図4のMoveデータにおけるアドレスフィールドのフォーマットの一例を示す説明図
【図8】図4のMoveデータにおけるアドレスフィールドの具体例を示す説明図
【図9】本実施形態に係る差分データ生成手順によってサンプルデータの差分データを生成した結果を示すグラフ
【図10】本発明の一実施形態に係る差分データ生成装置における差分データ生成部の機能構成を示すブロック図
【図11】本発明の一実施形態に係る携帯端末装置における更新後ファイル復元部の機能構成を示すブロック図
【図12】本実施形態に係る差分データ生成手順の概要を示すフローチャート
【図13】本実施形態に係る差分データ生成手順の全体を示すフローチャート
【図14】図13の差分データ生成処理におけるMoveデータとして出力する処理手順を示すフローチャート
【図15】図14のMoveデータ出力処理におけるMoveサイズの1バイト目を出力する処理手順を示すフローチャート
【図16】図14のMoveデータ出力処理におけるMoveサイズの2バイト目以降を出力する処理手順を示すフローチャート
【図17】図14のMoveデータ出力処理におけるMoveアドレスの1バイト目を出力する処理手順を示すフローチャート
【図18】図14のMoveデータ出力処理におけるMoveアドレスの2バイト目以降を出力する処理手順を示すフローチャート
【図19】図13の差分データ生成におけるAddデータとして出力する処理手順を示すフローチャート
【図20】本実施形態に係る更新後ファイル復元手順の全体を示すフローチャート
【図21】図20の更新後ファイル復元処理におけるMove操作による復元処理手順を示すフローチャート
【図22】図21のMove操作による復元処理におけるMoveサイズ判定処理手順を示すフローチャート
【図23】図21のMove操作による復元処理におけるMoveアドレス判定処理手順を示すフローチャート
【図24】従来の差分データ生成部の機能構成を示すブロック図
【図25】従来の差分データ生成手順を示すフローチャート
【符号の説明】
11 差分データ生成装置
12 サーバ
13 無線通信網
14 携帯端末装置
15 データベース
16 差分データ生成部
17 無線通信部
18 制御部
19 更新後ファイル復元部
20 データ格納部
31 差分データ生成制御手段
32 更新前データ記憶手段
33 更新後データ記憶手段
34 一致データ列検索手段
35 Move/Add決定手段
36 Moveデータ出力手段
37 Addデータ出力手段
38 差分データ記憶手段
39 Moveアドレス記憶手段
40 デリミタ出力手段
41 Moveサイズ出力手段
42 Moveアドレス出力手段
43 アドレス変化判定手段
44 アドレスフラグ設定手段
51 更新後ファイル復元制御手段
52 差分データ記憶手段
53 更新前データ記憶手段
54 Move/Add判定手段
55 Moveデータ復元手段
56 Addデータ復元手段
57 更新後データ記憶手段
58 Moveアドレス記憶手段
59 Moveサイズ判定手段
60 Moveアドレス判定手段
61 アドレス変化判定手段
Claims (33)
- 複数のバージョンのデータを持ち、1つのバージョンのデータである更新前ファイルと他のもう1つのバージョンのデータである更新後ファイルとの差を示す差分データを生成する差分データ生成手段と、
前記差分データを転送する通信手段と、
前記差分データを受信し、すでに保持している更新前ファイルと受信した前記差分データとを元に更新後ファイルを復元する更新後ファイル復元手段とを有するデータ更新システムであって、
前記差分データとして、前記更新前ファイルの一部、あるいは全部からデータを移動してコピーすることを意味する0個、1個、あるいは複数のMove命令を表すMoveデータと、当該差分データ中のデータを追加してコピーすることを意味する0個、1個、あるいは複数のAdd命令を表すAddデータとを有して構成される差分データを用いたデータ更新システム。 - 前記差分データにおいて、前記Moveデータの長さが所定の閾値未満となる場合はMoveデータではなくAddデータによって構成した請求項1に記載のデータ更新システム。
- 前記差分データにおいて、前記Moveデータは、コピーを行うデータ列の長さを表すデータ長情報と、コピーを行うデータ列の位置を表すアドレス情報とを有し、前記データ長情報と前記アドレス情報の少なくとも一方を可変ビット長で構成した請求項1に記載のデータ更新システム。
- 前記差分データにおいて、前記Moveデータは、コピーを行うデータ列の長さを表すデータ長情報と、コピーを行うデータ列の位置を表すアドレス情報とを有し、前記アドレス情報として前記データ列の移動のための相対アドレスを用い、同一の相対アドレス値が複数のMoveデータにおいて現れる場合に該当する1つまたは複数の相対アドレス値を1つまたは複数のビットで表現するように構成した請求項1に記載のデータ更新システム。
- 1つのバージョンのデータである更新前ファイルと他のもう1つのバージョンのデータである更新後ファイルとの差を示す差分データを生成し、前記差分データを通信手段を介して他所へ転送し、転送先で保持している更新前ファイルと前記差分データとを元に更新後ファイルを復元するデータ更新システムにおける差分データ生成装置であって、
前記更新後ファイル中のデータ列と一致するデータ列を前記更新前ファイルから検索する一致データ列検索手段と、
前記検索結果に基づき、前記差分データとして、前記更新前ファイルの一部、あるいは全部から一致するデータ列を前記更新後ファイルへ移動してコピーすることを意味するMove命令を表すMoveデータと、当該差分データ中のデータ列を前記更新後ファイルへ追加してコピーすることを意味するAdd命令を表すAddデータとのいずれを生成するかを決定するMove/Add決定手段と、
前記Moveデータを出力するMoveデータ出力手段と、
前記Addデータを出力するAddデータ出力手段とを備え、
0個、1個、あるいは複数の前記Moveデータと0個、1個、あるいは複数の前記Addデータとを有して構成される差分データを生成する差分データ生成装置。 - 前記Moveデータ出力手段は、前記Moveデータの開始を示す特定のデータからなる区切り子を出力する区切り子出力手段を備え、前記区切り子の後に前記Move命令を表現するデータを出力する請求項5に記載の差分データ生成装置。
- 前記Addデータ出力手段は、前記Addデータ中に前記区切り子として用いられる特定のデータが存在する場合に、このデータに続けて区切り子ではないことを示す特定のデータを出力する請求項5に記載の差分データ生成装置。
- 前記Move/Add決定手段は、前記一致するデータ列の長さが所定の閾値以上となる場合は前記Moveデータ出力手段よりMoveデータとして出力し、前記一致するデータ列の長さが所定の閾値未満となる場合は前記Addデータ出力手段よりAddデータとして出力するように決定する請求項5に記載の差分データ生成装置。
- 前記Move/Add決定手段における閾値として、32ビットCPUを用いた計算システムにおけるプログラム及びデータを転送するデータ更新システムに用いる場合に、閾値を5バイトとする請求項8に記載の差分データ生成装置。
- 前記Move/Add決定手段における閾値として、1つのバージョンの更新前ファイルと1つのバージョンの更新後ファイルとの間の差分データを生成する際に、異なる複数の閾値を用いて差分データ生成を実行し、大きさが最小となった場合の差分データを採用する請求項8に記載の差分データ生成装置。
- 前記Move/Add決定手段は、前記一致するデータ列について、前記Moveデータで表現した場合と前記Addデータで表現した場合とにおける差分データの大きさを比較し、より小さくなる方に決定する請求項5に記載の差分データ生成装置。
- 前記Moveデータ出力手段は、前記Moveデータの先頭バイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを設け、
前記データ長継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報のみによって前記更新前ファイルよりコピーを行うデータ列の長さを表現し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記データ列の長さを表現する情報が継続することとしたデータ長情報を出力する請求項5に記載の差分データ生成装置。 - 前記Moveデータ出力手段は、前記Moveデータの2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを設け、
前記データ長継続フラグが所定の状態1を取っている場合は前記Moveデータの先頭バイトまたはワードから当該バイトまたはワードまでにおける情報によって前記更新前ファイルよりコピーを行うデータ列の長さを表現し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記データ列の長さを表現する情報が継続することとしたデータ長情報を出力する請求項12に記載の差分データ生成装置。 - 前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルと前記更新後ファイルの少なくとも一方における絶対アドレスを用いたアドレス情報を出力する請求項5に記載の差分データ生成装置。
- 前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差を示す相対アドレスを用いたアドレス情報を出力する請求項5に記載の差分データ生成装置。
- 前記Moveデータ出力手段及び前記Addデータ出力手段は、前記更新後ファイルにおけるデータ列の順番に沿ってMoveデータ及びAddデータを生成出力するものとし、
前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を表す情報として、前記更新前ファイルにおける当該データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いたアドレス情報を出力する請求項5に記載の差分データ生成装置。 - 前記Moveデータ出力手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の先頭バイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを設け、
前記アドレス継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報のみによって前記相対アドレスを表現し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記相対アドレスを表現する情報が継続することとしたアドレス情報を出力する請求項15または16に記載の差分データ生成装置。 - 前記Moveデータ出力手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを設け、
前記アドレス継続フラグが所定の状態1を取っている場合は前記アドレス情報のデータ列の先頭バイトまたはワードから当該バイトまたはワードまでにおける情報によって前記相対アドレスを表現し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいて前記相対アドレスを表現する情報が継続することとしたアドレス情報を出力する請求項17に記載の差分データ生成装置。 - 前記Moveデータ出力手段は、前記Moveデータのアドレス情報において、同一の相対アドレス値が複数のMoveデータにおいて現れる場合に、該当する1つまたは複数の相対アドレス値については前記Moveデータの先頭バイトまたはワードにおいて1つあるいは複数のビットで表現することとした請求項15または16に記載の差分データ生成装置。
- 前記Moveデータ出力手段は、前記Moveデータにおいて、前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の位置を表す情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差、または前記更新前ファイルにおける前記データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスを用いたアドレス情報を出力するものとし、
前記Moveデータ中において1つあるいは複数のビットからなるアドレス変化フラグを設け、
前記アドレス変化フラグが所定の状態1を取っている場合は前記データ列の長さを表現するデータ長情報の後に前記相対アドレスによるアドレス情報を出力し、前記アドレス変化フラグが前記状態1とは異なる所定の状態2を取っている場合は前回のMoveデータにおける相対アドレスと今回のMoveデータにおける相対アドレスとが同一であるとして前記相対アドレスを表現する情報を省略する請求項5に記載の差分データ生成装置。 - 前記Moveデータ出力手段は、前記Moveデータのアドレス情報における相対アドレスを、前回のMoveデータにおける相対アドレスからの変化量により表現することとした請求項15,16,20のいずれかに記載の差分データ生成装置。
- 請求項5〜21のいずれかに記載のデータ更新システムの差分データ生成装置における各手段の機能をコンピュータにより実現するための差分データ生成プログラム。
- 1つのバージョンのデータである更新前ファイルと他のもう1つのバージョンのデータである更新後ファイルとの差を示す差分データを受信し、自装置で保持している更新前ファイルと前記差分データとを元に更新後ファイルを復元するデータ更新システムにおける更新後ファイル復元装置であって、
前記差分データが、前記更新前ファイルの一部、あるいは全部から一致するデータ列を前記更新後ファイルへ移動してコピーすることを意味するMove命令を表すMoveデータと、当該差分データ中のデータ列を前記更新後ファイルへ追加してコピーすることを意味するAdd命令を表すAddデータとのいずれであるかを判定するMove/Add判定手段と、
前記Moveデータに対応するデータ列を出力するMoveデータ復元手段と、
前記Addデータに対応するデータ列を出力するAddデータ復元手段とを備え、
前記差分データより更新後ファイルを生成する更新後ファイル復元装置。 - 前記Move/Add判定手段は、前記差分データにおいて、特定のデータからなる区切り子の後に設けられたMove命令を表現するデータをMoveデータとし、前記差分データの先頭または前回のMoveデータの終端から前記区切り子が出現するまでに設けられたAdd命令を表現するデータをAddデータとして区別する請求項23に記載の更新後ファイル復元装置。
- 前記Move/Add判定手段は、前記差分データにおいて、前記区切り子がデータ列中に現れ、かつ前記区切り子に続くデータが特定のものである場合は、前記区切り子ではなく、前記Addデータ中に存在する区切り子として用いられたデータそのものであるとする請求項24に記載の更新後ファイル復元装置。
- 前記Moveデータ復元手段は、前記Moveデータに設けられるデータ長情報を判別して前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の長さを決定するものであり、
前記Moveデータの先頭バイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを検出し、
前記データ長継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報よりデータ長情報を判別して前記コピーを行うデータ列の長さを決定し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記データ長情報が継続するものと判定する請求項23に記載の更新後ファイル復元装置。 - 前記Moveデータ復元手段は、前記Moveデータの2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるデータ長継続フラグを検出し、
前記データ長継続フラグが所定の状態1を取っている場合は前記Moveデータの先頭バイトまたはワードから当該バイトまたはワードまでにおける情報よりデータ長情報を判別して前記コピーを行うデータ列の長さを決定し、前記データ長継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記データ長情報が継続するものと判定する請求項26に記載の更新後ファイル復元装置。 - 前記Moveデータ復元手段は、前記Moveデータに設けられるアドレス情報を判別して前記更新前ファイルより前記更新後ファイルへコピーを行うデータ列の移動のための位置を決定するものであり、
前記アドレス情報として、前記更新前ファイルにおける前記データ列の位置と前記更新後ファイルにおける前記データ列の位置との差、または前記更新前ファイルにおける前記データ列の先頭位置と前記更新後ファイルにおける復元済みのデータのサイズとの差を示す相対アドレスにより表現されたアドレス情報を判別する請求項23に記載の更新後ファイル復元装置。 - 前記Moveデータ復元手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の先頭バイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを検出し、
前記アドレス継続フラグが所定の状態1を取っている場合は当該バイトまたはワードにおける情報より前記相対アドレスのアドレス情報を判別して前記コピーを行うデータ列の位置を決定し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記アドレス情報が継続するものと判定する請求項28に記載の更新後ファイル復元装置。 - 前記Moveデータ復元手段は、前記Moveデータ中の前記相対アドレスによるアドレス情報のデータ列の2番目以降のバイトまたはワードにおいて1つあるいは複数のビットからなるアドレス継続フラグを検出し、
前記アドレス継続フラグが所定の状態1を取っている場合は前記アドレス情報のデータ列の先頭バイトまたはワードから当該バイトまたはワードにおける情報より前記相対アドレスのアドレス情報を判別して前記コピーを行うデータ列の位置を決定し、前記アドレス継続フラグが前記状態1とは異なる所定の状態2を取っている場合は当該バイトまたはワード以降にある1つまたは複数のバイトまたはワードにおいても前記アドレス情報が継続するものと判定する請求項29に記載の更新後ファイル復元装置。 - 前記Moveデータ復元手段は、前記Moveデータ中において1つあるいは複数のビットで表現されたアドレス情報を判別し、このアドレス情報に該当する1つまたは複数の相対アドレス値については同一の相対アドレス値として前記コピーを行うデータ列の位置を決定する請求項28に記載の更新後ファイル復元装置。
- 前記Moveデータ復元手段は、前記Moveデータ中において1つあるいは複数のビットからなるアドレス変化フラグを検出し、
前記アドレス変化フラグが所定の状態1を取っている場合は前記コピーを行うデータ列の長さを表すデータ長情報の後に設けられる前記相対アドレスによるアドレス情報を判別し、前記アドレス変化フラグが前記状態1とは異なる所定の状態2を取っている場合は前回のMoveデータにおける相対アドレスと同一の相対アドレスを用いて前記コピーを行うデータ列の位置を決定する請求項28に記載の更新後ファイル復元装置。 - 請求項23〜32のいずれかに記載のデータ更新システムの更新後ファイル復元装置における各手段の機能をコンピュータにより実現するための更新後ファイル復元プログラム。
Priority Applications (7)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2002318391A JP2004152136A (ja) | 2002-10-31 | 2002-10-31 | データ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラム |
EP03759008A EP1557761A1 (en) | 2002-10-31 | 2003-10-28 | Data update system, differential data creating device and program for data update system, updated file restoring device and program |
AU2003275718A AU2003275718A1 (en) | 2002-10-31 | 2003-10-28 | Data update system, differential data creating device and program for data update system, updated file restoring device and program |
PCT/JP2003/013793 WO2004040452A1 (ja) | 2002-10-31 | 2003-10-28 | データ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラム |
US10/533,484 US20060106888A1 (en) | 2002-10-31 | 2003-10-28 | Data update system, differential data creating device and program for data update system, updated file restoring device and program |
KR1020057007483A KR20050065642A (ko) | 2002-10-31 | 2003-10-28 | 데이터 갱신 시스템, 데이터 갱신 시스템의 차분 데이터생성장치 및 프로그램, 및 갱신 후 파일 복원장치 및프로그램 |
CNA2003801061981A CN1726476A (zh) | 2002-10-31 | 2003-10-28 | 数据更新系统、用于数据更新系统的差分数据创建设备和程序、更新后文件恢复设备和程序 |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2002318391A JP2004152136A (ja) | 2002-10-31 | 2002-10-31 | データ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラム |
Publications (1)
Publication Number | Publication Date |
---|---|
JP2004152136A true JP2004152136A (ja) | 2004-05-27 |
Family
ID=32211768
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP2002318391A Pending JP2004152136A (ja) | 2002-10-31 | 2002-10-31 | データ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラム |
Country Status (7)
Country | Link |
---|---|
US (1) | US20060106888A1 (ja) |
EP (1) | EP1557761A1 (ja) |
JP (1) | JP2004152136A (ja) |
KR (1) | KR20050065642A (ja) |
CN (1) | CN1726476A (ja) |
AU (1) | AU2003275718A1 (ja) |
WO (1) | WO2004040452A1 (ja) |
Cited By (8)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
WO2007001073A1 (ja) * | 2005-06-28 | 2007-01-04 | Movell Software, Inc. | データバックアップシステムおよびデータバックアップ方法 |
JP2007219768A (ja) * | 2006-02-15 | 2007-08-30 | Mitsubishi Electric Corp | 差分生成装置及び差分適用装置及び差分生成プログラム及び差分適用プログラム |
JP2008204287A (ja) * | 2007-02-21 | 2008-09-04 | Access Co Ltd | データ生成方法、データ復元方法、データ生成装置およびデータ復元装置 |
CN100464334C (zh) * | 2007-06-06 | 2009-02-25 | 中国工商银行股份有限公司 | 应用于数据仓库的数据增量备份与恢复的方法 |
US7624021B2 (en) * | 2004-07-02 | 2009-11-24 | Apple Inc. | Universal container for audio data |
JP2012069131A (ja) * | 2006-06-19 | 2012-04-05 | Samsung Electronics Co Ltd | OTA(Over−the−air)が可能な携帯装置のためのプログラムアップグレード方法およびシステム |
US9900026B2 (en) | 2014-07-28 | 2018-02-20 | Mitsubishi Electric Corporation | Differential data creating apparatus, data updating apparatus, and differential data creating method |
JP2020052852A (ja) * | 2018-09-28 | 2020-04-02 | 日本電気株式会社 | ストレージ及び情報処理システム。 |
Families Citing this family (39)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US7747994B1 (en) * | 2003-06-04 | 2010-06-29 | Hewlett-Packard Development Company, L.P. | Generator based on multiple instruction streams and minimum size instruction set for generating updates to mobile handset |
US7904895B1 (en) | 2004-04-21 | 2011-03-08 | Hewlett-Packard Develpment Company, L.P. | Firmware update in electronic devices employing update agent in a flash memory card |
US8526940B1 (en) | 2004-08-17 | 2013-09-03 | Palm, Inc. | Centralized rules repository for smart phone customer care |
CN1327342C (zh) * | 2004-09-13 | 2007-07-18 | 联发科技股份有限公司 | 移动电话的软件更新方法及其系统 |
US8193096B2 (en) * | 2004-12-13 | 2012-06-05 | Novellus Systems, Inc. | High dose implantation strip (HDIS) in H2 base chemistry |
US7401255B1 (en) * | 2005-03-16 | 2008-07-15 | Symantec Corporation | Mechanisms for recovering data from a backup by comparing transformed data to identify altered memory blocks |
US20060218200A1 (en) * | 2005-03-24 | 2006-09-28 | International Business Machines Corporation | Application of log records by storage servers |
US9407608B2 (en) | 2005-05-26 | 2016-08-02 | Citrix Systems, Inc. | Systems and methods for enhanced client side policy |
US8943304B2 (en) | 2006-08-03 | 2015-01-27 | Citrix Systems, Inc. | Systems and methods for using an HTTP-aware client agent |
US7756826B2 (en) * | 2006-06-30 | 2010-07-13 | Citrix Systems, Inc. | Method and systems for efficient delivery of previously stored content |
US9621666B2 (en) | 2005-05-26 | 2017-04-11 | Citrix Systems, Inc. | Systems and methods for enhanced delta compression |
US9692725B2 (en) | 2005-05-26 | 2017-06-27 | Citrix Systems, Inc. | Systems and methods for using an HTTP-aware client agent |
JP4891902B2 (ja) * | 2005-06-01 | 2012-03-07 | パナソニック株式会社 | 電子機器、更新サーバ装置、鍵更新装置 |
EP1934729B1 (en) * | 2005-10-06 | 2021-06-23 | Red Bend Ltd. | Methods and systems for updating content including a compressed version |
CN1949761B (zh) * | 2005-10-13 | 2010-09-15 | 腾讯科技(深圳)有限公司 | 一种数据同步方法及其差分编码方法 |
US8209676B2 (en) | 2006-06-08 | 2012-06-26 | Hewlett-Packard Development Company, L.P. | Device management in a network |
JP5103807B2 (ja) * | 2006-06-30 | 2012-12-19 | 富士通株式会社 | 制御プログラム、制御方法、情報処理装置及び情報処理システム |
EP2047420A4 (en) | 2006-07-27 | 2009-11-18 | Hewlett Packard Development Co | USER EXPERIENCE AND DEPENDENCE MANAGEMENT IN A MOBILE DEVICE |
US8435895B2 (en) * | 2007-04-04 | 2013-05-07 | Novellus Systems, Inc. | Methods for stripping photoresist and/or cleaning metal regions |
CN101546318B (zh) * | 2008-03-27 | 2013-01-16 | 北京兴宇中科科技开发股份有限公司 | 一种基于版本的数据存储方法 |
WO2011072061A2 (en) * | 2009-12-11 | 2011-06-16 | Novellus Systems, Inc. | Enhanced passivation process to protect silicon prior to high dose implant strip |
US20110143548A1 (en) * | 2009-12-11 | 2011-06-16 | David Cheung | Ultra low silicon loss high dose implant strip |
US8666997B2 (en) | 2010-12-08 | 2014-03-04 | Microsoft Corporation | Placeholders returned for data representation items |
US8983907B2 (en) * | 2010-12-08 | 2015-03-17 | Microsoft Technology Licensing, Llc | Change notifications from an updated data representation |
US9069829B2 (en) | 2011-01-21 | 2015-06-30 | Microsoft Technology Licensing, Llc | Data items manager |
US8838533B2 (en) | 2011-05-20 | 2014-09-16 | Microsoft Corporation | Optimistic application of data edits |
CN102955816B (zh) | 2011-08-30 | 2016-04-20 | 国际商业机器公司 | 利用串匹配进行数据同步的方法和系统 |
CN102750305A (zh) * | 2012-02-28 | 2012-10-24 | 新奥特(北京)视频技术有限公司 | 一种现场成绩处理系统的数据更新方法 |
KR101970712B1 (ko) | 2012-08-23 | 2019-04-22 | 삼성전자주식회사 | 단말기의 데이터 이동장치 및 방법 |
US10387372B2 (en) | 2012-11-09 | 2019-08-20 | o9 Solutions, Inc. | Value-based differential data |
CN103440304B (zh) * | 2013-08-22 | 2017-04-05 | 宇龙计算机通信科技(深圳)有限公司 | 一种图片存储方法及存储装置 |
EP2881903A1 (en) * | 2013-12-03 | 2015-06-10 | Siemens Aktiengesellschaft | Managing design updates in a manufacturing execution system |
JP2018067248A (ja) * | 2016-10-21 | 2018-04-26 | 富士通株式会社 | 制御プログラム、制御方法、及び情報処理装置 |
CN107797820B (zh) * | 2017-11-13 | 2021-03-23 | 北京百度网讯科技有限公司 | 用于生成补丁的方法和装置 |
CN107992323A (zh) * | 2017-12-27 | 2018-05-04 | 深圳市科陆电子科技股份有限公司 | 一种集中器升级方法和系统 |
EP3803573B1 (en) * | 2018-05-29 | 2024-06-26 | Nordic Semiconductor ASA | Delta file with reversing data |
CN111104149A (zh) * | 2018-10-25 | 2020-05-05 | 华为技术有限公司 | 一种固件升级方法、装置及终端 |
WO2021168840A1 (zh) * | 2020-02-28 | 2021-09-02 | 华为技术有限公司 | 一种软件版本回滚方法、装置及系统 |
CN118568052B (zh) * | 2024-07-31 | 2024-10-01 | 北京科杰科技有限公司 | 一种基于Iceberg的数据治理实施系统 |
Family Cites Families (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
AU651321B2 (en) * | 1989-09-08 | 1994-07-21 | Network Appliance, Inc. | Multiple facility operating system architecture |
TW313643B (ja) * | 1994-12-14 | 1997-08-21 | At & T Corp | |
US5832520A (en) * | 1996-07-03 | 1998-11-03 | Miller, Call, Plauck And Miller | Automatic file differencing and updating system |
GB2343768A (en) * | 1998-08-17 | 2000-05-17 | Connected Place Limited | Merging a sequence of delta files |
JP2002132561A (ja) * | 2000-10-20 | 2002-05-10 | Fuji Xerox Co Ltd | 差分バックアップ方法および装置 |
JP4205350B2 (ja) * | 2002-02-28 | 2009-01-07 | 富士通株式会社 | 差分データ生成方法、プログラム、記録媒体及び装置 |
-
2002
- 2002-10-31 JP JP2002318391A patent/JP2004152136A/ja active Pending
-
2003
- 2003-10-28 KR KR1020057007483A patent/KR20050065642A/ko not_active Application Discontinuation
- 2003-10-28 AU AU2003275718A patent/AU2003275718A1/en not_active Abandoned
- 2003-10-28 US US10/533,484 patent/US20060106888A1/en not_active Abandoned
- 2003-10-28 WO PCT/JP2003/013793 patent/WO2004040452A1/ja not_active Application Discontinuation
- 2003-10-28 CN CNA2003801061981A patent/CN1726476A/zh active Pending
- 2003-10-28 EP EP03759008A patent/EP1557761A1/en not_active Withdrawn
Cited By (11)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US7624021B2 (en) * | 2004-07-02 | 2009-11-24 | Apple Inc. | Universal container for audio data |
US8095375B2 (en) | 2004-07-02 | 2012-01-10 | Apple Inc. | Universal container for audio data |
US8117038B2 (en) | 2004-07-02 | 2012-02-14 | Apple Inc. | Universal container for audio data |
WO2007001073A1 (ja) * | 2005-06-28 | 2007-01-04 | Movell Software, Inc. | データバックアップシステムおよびデータバックアップ方法 |
JP2007219768A (ja) * | 2006-02-15 | 2007-08-30 | Mitsubishi Electric Corp | 差分生成装置及び差分適用装置及び差分生成プログラム及び差分適用プログラム |
JP2012069131A (ja) * | 2006-06-19 | 2012-04-05 | Samsung Electronics Co Ltd | OTA(Over−the−air)が可能な携帯装置のためのプログラムアップグレード方法およびシステム |
JP2008204287A (ja) * | 2007-02-21 | 2008-09-04 | Access Co Ltd | データ生成方法、データ復元方法、データ生成装置およびデータ復元装置 |
CN100464334C (zh) * | 2007-06-06 | 2009-02-25 | 中国工商银行股份有限公司 | 应用于数据仓库的数据增量备份与恢复的方法 |
US9900026B2 (en) | 2014-07-28 | 2018-02-20 | Mitsubishi Electric Corporation | Differential data creating apparatus, data updating apparatus, and differential data creating method |
JP2020052852A (ja) * | 2018-09-28 | 2020-04-02 | 日本電気株式会社 | ストレージ及び情報処理システム。 |
JP7310110B2 (ja) | 2018-09-28 | 2023-07-19 | 日本電気株式会社 | ストレージ及び情報処理システム。 |
Also Published As
Publication number | Publication date |
---|---|
WO2004040452A1 (ja) | 2004-05-13 |
AU2003275718A1 (en) | 2004-05-25 |
US20060106888A1 (en) | 2006-05-18 |
EP1557761A1 (en) | 2005-07-27 |
CN1726476A (zh) | 2006-01-25 |
KR20050065642A (ko) | 2005-06-29 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
JP2004152136A (ja) | データ更新システム、データ更新システムの差分データ生成装置及びプログラム、並びに更新後ファイル復元装置及びプログラム | |
JP5173427B2 (ja) | 圧縮リード・オンリ・メモリ・ファイル・システム(crmfs)イメージの更新 | |
JP4364790B2 (ja) | バイト・レベルのファイル相違検出および更新アルゴリズム | |
Kohonen et al. | LVQ PAK: The learning vector quantization program package | |
US7031972B2 (en) | Algorithms for block-level code alignment of software binary files | |
JP4150060B2 (ja) | コンピュータ・システムにおいてリソース・モジュールをロードする方法 | |
CN104462668B (zh) | 计算机实施的用于设计用二叉树来建模的工业产品的方法 | |
US20130080485A1 (en) | Quick filename lookup using name hash | |
CN109710185B (zh) | 数据处理方法及装置 | |
EP1808764A1 (en) | Generating incremental program updates | |
JP2005044360A (ja) | データのパッケージ内デルタ圧縮(intra−packetdeltacompression)のためのシステムおよび方法 | |
EP1211601A1 (en) | File processing method, data processing device and storage medium | |
CN111522574B (zh) | 差分包生成方法及相关设备 | |
CN111831785A (zh) | 敏感词检测方法、装置、计算机设备及存储介质 | |
US20130054522A1 (en) | Data synchronization using string matching | |
JP2013214832A (ja) | 圧縮及び伸長システム、圧縮装置、伸長装置、圧縮及び伸長方法、圧縮プログラム及び伸長プログラム | |
JPH06309204A (ja) | データ処理方法及びその装置 | |
US11789708B2 (en) | Compression of firmware updates | |
JP2023057546A (ja) | コンピュータに実装された方法、コンピュータプログラム又はコンピュータシステム | |
JP4036852B2 (ja) | 差分データ生成装置、差分データ生成方法および差分データ生成プログラム | |
JP4477947B2 (ja) | 差分適用組込み機器システム及び格納データ変更方法 | |
CN114547038B (zh) | 优先级数据库的数据处理方法及装置 | |
US20230342466A1 (en) | System and method for computer security augmented data set algorithm training | |
TWI857684B (zh) | 模型專用化方法及非暫時性機器可讀介質 | |
CN114514569B (zh) | 秘密多重迭代计算装置、方法以及记录介质 |