(57)【特許請求の範囲】
【請求項１】
第１のファイルと第２のファイルの差分データの生成方法であって、
コンピュータが、
前記第１のファイルおよび第２のファイルについてそれぞれ先頭を初期値とするポインタ位置から所定データ単位にデータを比較し、データが一致するか否かを判定する比較ステップと、
前記比較ステップによりデータが一致すると判定した場合、前記第１のファイルの位置とデータ長を表した転送情報を出力する転送情報生成ステップと、
前記比較ステップによりデータが一致しないと判定した場合、前記第２のファイルの前記所定の長さのデータに一致する部分があるか、前記第１のファイルについて前記所定の位置から該第１のファイルのデータを前後両方向に探索する探索ステップと、
前記探索ステップで探索した結果、一致部分を探索できた場合は、前記第１のファイルにおける、前記所定の位置から一致部分までの移動情報を出力し、該第１のファイルのポインタ位置を該一致部分に移動する移動情報生成ステップと、
前記探索ステップで探索した結果、一致部分を探索できなかった場合は、前記第２のファイルにおける前記ポインタ位置から前記所定データ単位分のデータを、新規に生成されたものと判別して、該所定データ単位のデータ長を表した転送置換情報に該新規に生成されたものと判別したデータを付加して出力すると共に該第２のファイルにおける該ポインタ位置を該所定データ単位分後ろへ進める置換情報生成ステップと、を
前記第２のファイルのポインタ位置が該ファイルの最後に達するまで実行することを特徴とする差分データの生成方法。
【請求項２】
請求項１記載の差分データ生成方法に於いて、前記置換情報生成ステップは、旧データと新データとの差分データが過去に生成された置換情報の差分データに一致する場合、新データを付加せずに過去の差分パターン又は更新パターンと同じことを表す転送置換情報（転送増加情報）を出力することを特徴とする差分データ生成方法。
【請求項３】
第１のファイルと第２のファイルの差分データの生成方法のためのプログラムであって、
コンピュータに、
前記第１のファイルおよび第２のファイルについてそれぞれ先頭を初期値とするポインタ位置から所定データ単位にデータを比較し、データが一致するか否かを判定する比較ステップと、
前記比較ステップによりデータが一致すると判定した場合、前記第１のファイルの位置とデータ長を表した転送情報を出力する転送情報生成ステップと、
前記比較ステップによりデータが一致しないと判定した場合、前記第２のファイルの前記所定の長さのデータに一致する部分があるか、前記第１のファイルについて前記所定の位置から該第１のファイルのデータを前後両方向に探索する探索ステップと、
前記探索ステップで探索した結果、一致部分を探索できた場合は、前記第１のファイルにおける、前記所定の位置から一致部分までの移動情報を出力し、該第１のファイルのポインタ位置を該一致部分に移動する移動情報生成ステップと、
前記探索ステップで探索した結果、一致部分を探索できなかった場合は、前記第２のファイルにおける前記ポインタ位置から前記所定データ単位分のデータを、新規に生成されたものと判別して、該所定データ単位のデータ長を表した転送置換情報に該新規に生成されたものと判別したデータを付加して出力すると共に該第２のファイルにおける該ポインタ位置を該所定データ単位分後ろへ進める置換情報生成ステップと、を
前記第２のファイルのポインタ位置が該ファイルの最後に達するまで実行させることを特徴とする差分データ生成のためのプログラム。
【請求項４】
第１のファイルと第２のファイルの差分データの生成を実行させるプログラムを格納したコンピュータ読取可能な記録媒体であって、
コンピュータに、
前記第１のファイルおよび第２のファイルについてそれぞれ先頭を初期値とするポインタ位置から所定データ単位にデータを比較し、データが一致するか否かを判定する比較ステップと、
前記比較ステップによりデータが一致すると判定した場合、前記第１のファイルの位置とデータ長を表した転送情報を出力する転送情報生成ステップと、
前記比較ステップによりデータが一致しないと判定した場合、前記第２のファイルの前記所定の長さのデータに一致する部分があるか、前記第１のファイルについて前記所定の位置から該第１のファイルのデータを前後両方向に探索する探索ステップと、
前記探索ステップで探索した結果、一致部分を探索できた場合は、前記第１のファイルにおける、前記所定の位置から一致部分までの移動情報を出力し、該第１のファイルのポインタ位置を該一致部分に移動する移動情報生成ステップと、
前記探索ステップで探索した結果、一致部分を探索できなかった場合は、前記第２のファイルにおける前記ポインタ位置から前記所定データ単位分のデータを、新規に生成されたものと判別して、該所定データ単位のデータ長を表した転送置換情報に該新規に生成されたものと判別したデータを付加して出力すると共に該第２のファイルにおける該ポインタ位置を該所定データ単位分後ろへ進める置換情報生成ステップと、を
前記第２のファイルのポインタ位置が該ファイルの最後に達するまで実行させるプログラムを格納したコンピュータ読取可能な記録媒体。
【請求項５】
第１のファイルと第２のファイルの差分データを生成する差分データ生成装置であって、
前記第１のファイルおよび第２のファイルについてそれぞれ先頭を初期値とするポインタ位置から所定データ単位にデータを比較し、データが一致するか否かを判定する比較部と、
前記比較部によりデータが一致すると判定した場合、前記第１のファイルの位置とデータ長を表した転送情報を出力する転送情報生成部と、
前記比較部によりデータが一致しないと判定した場合、前記第２のファイルの前記所定の長さのデータに一致する部分があるか、前記第１のファイルについて前記所定の位置から該第１のファイルのデータを前後両方向に探索する探索部と、
前記探索部で探索した結果、一致部分を探索できた場合は、前記第１のファイルにおける、前記所定の位置から一致部分までの移動情報を出力し、該第１のファイルのポインタ位置を該一致部分に移動する移動情報生成部と、
前記探索部で探索した結果、一致部分を探索できなかった場合は、前記第２のファイルにおける前記ポインタ位置から前記所定データ単位分のデータを、新規に生成されたものと判別して、該所定データ単位のデータ長を表した転送置換情報に該新規に生成されたものと判別したデータを付加して出力すると共に該第２のファイルにおける該ポインタ位置を該所定データ単位分後ろへ進める置換情報生成部と、を備え
前記第２のファイルのポインタ位置が該ファイルの最後に達するまで前記比較部、前記転送情報生成部、前記探索部、前記移動情報生成部および前記置換情報生成部による処理を実行することを特徴とする差分データの生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、新旧２つのファイルを比較して差分データを生成する差分データ生成方法、プログラム、記録媒体および装置に関し、特に、旧ファイルから新ファイルへと更新を行うために使用するための差分データを生成する差分データ生成方法、プログラム、記録媒体および装置に関する。
【０００２】
【０００３】
【従来の技術】
コンピュータ上のソフトウェアや機器のファームウェアのバージョンアップ・バックアップなどで更新が必要な場合には、新旧２つのファイルを比較して生成した差分データを用いることにより、低速な通信環境でも低コストでアップロードやダウンロードが望まれる。
従来、プログラムやデータなどのファイルを新しいファイルへと更新する場合、新しいファイルを全部置き換える方法と、ファイルの更新情報のみの差分データを与えて更新する方法がある。差分データによる更新方法は、ファイルを全部置き換える方法よりも少ない情報量で更新を行うことが可能であるという利点があり、更新情報を旧ファイルの存在する場所へ転送する場合に情報量が小さいほどコスト面で有利となる。
【０００４】
従来の差分データ生成は、図２６、図２７のフローチャートのように、新旧２つのファイルを先頭から比較し、一致しない部分を更新された部分として置換、挿入及び削除の３つのカテゴリに分類し、差分データとして
（１）更新のカテゴリ
（２）置換または挿入のカテゴリによる更新後の値
を記述する方法がある（特開平４-１６３６２６号）。
【０００５】
ここで図２６、図２７の処理ステップは次のようになる。
Ｓ１：旧ファイルと新ファイルをディスク等から読み込む。
Ｓ２：データ比較対象ポインタを新ファイルの先頭に設定し、データ参照ポインタを旧ファイルの先頭に設定する。
Ｓ３：比較対象ポインタの指す値と、データ参照ポインタの指す値を比較する。
Ｓ４：Ｓ３の比較結果が同一であればＳ５へ、異なっていればＳ７へ進む。
Ｓ５：比較対象ポインタの指す値は旧ファイルのコピーであると判断する。
Ｓ６：コピーする長さを記憶する。Ｓ１４へ進む。
Ｓ７：データ参照ポインタよりも後方のデータから、データ比較対象ポインタの指す値と一致するデータを探索する。
Ｓ８：探索の結果、一致するデータが見つかったならＳ１１へ進み、見つからなければＳ９へ進む。
Ｓ９：比較対象のデータは新規に生成されたデータであると判断する。
Ｓ１０：データ比較対象ポインタを一つ後ろへ移動させる。Ｓ７へ進む。
Ｓ１１：新規データの挿入もしくは旧ファイルのデータの削除によって一致箇所のずれが起こったと判断する。
Ｓ１２：転送コードを書き出した後、ずれの形に従って置換コード、挿入コード又は削除コードのいずれかを書き出す。
Ｓ１３：データ参照ポインタをずれの分だけ移動させる。
Ｓ１４：データ比較対象ポインタ及びデータ参照ポインタをそれぞれ１つ後ろへ移動させる。
Ｓ１５：データ比較対象ポインタが新ファイルの最後に達していなければＳ３へ戻る。最後に達していれば終了する。
【０００６】
図２８は従来のデータ生成方法における置換処理である。図２８（Ａ）の旧ファイル２００は、データＡ，Ｂ，Ｃで構成されており、新ファイル２０２はデータＡ，Ｂ'，Ｃで構成されており、データＡ，Ｃは一致部分２０４，２０８であり、データＢ，Ｂ'が置換部分２０６となる。
【０００７】
図２８（Ｂ）は図２５、図２６のフローチャートにより生成された差分データファイル２１０である。まずデータＡの一致部分２０４については、転送コード番号とコピー元データ長（ａバイト）をもつ転送コード２１２を書き出す。次のデータＢ，Ｂ'の置換データ２０６については、置換コード番号と置換データ長（ｂバイト）をもつ置換コード２１４を書き出すと共に、（Ｂ−Ｂ'）の差分データ２１６を付加する。更にデータＣの一致部分２０８については、転送コード番号とコピー元データ長（ｃバイト）をもつ転送コード２１８を書き出す。
【０００８】
図２９は従来のデータ生成方法における挿入処理である。図２９（Ａ）の旧ファイル２００は、データＡ，Ｂで構成されており、新ファイル２０２はデータＡ，Ｂの間に新データＣを挿入しており、データＡ，Ｂは一致部分２０４，２０８であり、データＣが挿入部分２０６となる。
【０００９】
図２９（Ｂ）は図２５、図２６のフローチャートにより生成された差分データファイル２１０である。データＡ，Ｂの一致部分２０４，２０８については、図２９（Ｂ）と同様に、転送コード番号とコピー元データ長をもつ転送コード２１２，２１８を書き出す。データＣの挿入部分２２０については、挿入コード番号と挿入データ長（ｃバイト）をもつ挿入コード２２２を書き出すと共に、挿入データ２２４を付加する。
【００１０】
図３０は従来のデータ生成方法における削除処理である。図３０（Ａ）の旧ファイル２００は、データＡ，Ｂ，Ｃで構成されており、新ファイル２０２はデータＣを削除したデータＡ，Ｂで構成され、データＡ，Ｃは一致部分２０４，２０８であり、データＢが削除部分２２６となる。
【００１１】
図３０（Ｂ）は図２５、図２６のフローチャートにより生成された差分データファイル２１０である。データＡ，Ｃの一致部分２０４，２０８については、図２８（Ｂ）と同様に、転送コード番号とコピー元データ長をもつ転送コード２１２，２１８を書き出す。データＢの削除部分２２６については、削除コード番号と削除データ長（ｂバイト）をもつ削除コード２２８を書き出す。
【００１２】
【発明が解決しようとする課題】
しかしながら、このような従来の差分データ生成方法にあっては、新旧ファイルの一致部分を探索する際に、常に正しい一致箇所を発見できるという前提のもとに、置換、挿入及び削除という３つのカテゴリで更新情報を表すものであったため、次の問題がある。
【００１３】
図３１は挿入処理の例であり、旧ファイル２００はデータＡ，Ｂで構成されており、新ファイル２０２はデータＡ，Ｂの間にデータＡを挿入しており、旧ファイル２００のデータＡに対し新ファイル２０２は２つの一致部分２０４，２３０を持っている。
【００１４】
しかし、従来の差分データ生成方法では、２つめの一致部分２３０については、置換、挿入又は削除のいずれのカテゴリにも該当しないため、新たなデータＡの挿入に対し、それ以降の新旧ファイルは全て不一致部分と判定し、置換のカテゴリのみで書き出してしまい、差分データ量が増加する問題がある。
【００１５】
図３２は、新旧ファイルについて対応付けが誤っていた場合である。ここで旧ファイルはデータＡ，Ｂ，Ｃ，Ｂで構成されており、新ファイルは最後のデータＢを削除したデータＡ，Ｂ，Ｃで構成されていたとする。しかし、差分生成処理において、旧ファイル２００のデータＢと新ファイル２０２のデータＢの比較において、新ファイルをデータＢ'として誤って不一致と判定した場合、即ち更新部分と誤判定した場合、置換のカテゴリとして置換コードと新データＢ'が誤って生成されてしまう。
【００１６】
この場合、誤判定を起こした位置の後ろとなる旧ファイル上に、誤判定したのと同じデータＢが存在していたとしても、このデータＢを活用する余地はなく、旧ファイルの更新の際に、誤判定されたデータＢ'への誤った書き替えが行われてしまう。
【００１７】
更に、プログラムファイルにあっては、特定のプログラムコードを書き換えることにより、置換情報に付加される差分値として同じ値が繰り替えし出現する場合が考えられるが、従来の差分データ生成方法では、この点に対する考慮はみられない。
【００１８】
本発明の目的は、新旧ファイルの比較による置換、挿入及び削除以外のパターンにも対応可能として差分データ量を低減し、新旧ファイルの比較判定を誤っても後続する処理により訂正可能として信頼性を高める差分データ生成方法、プログラム、記録媒体及び装置を提供することにある。
【００１９】
【課題を解決するための手段】
図１は本発明の原理説明図である。本発明は、差分データ生成方法を提供するものであり、この方法は、図１（Ａ）のように、
新旧２つのファイルに対してファイル先頭から所定データ単位に順次比較する比較ステップと、
順次比較でデータ一致を判定した場合、旧ファイルの位置とデータ長を表した転送情報（転送コード）を出力する転送情報生成ステップと、
順次比較でデータ不一致を判定した場合、旧ファイルの不一致と判定されたデータ位置から前後両方向に探索を行って新ファイルのデータに一致する部分を探索する探索ステップと、
探索ステップで一致部分を探索できた場合は、旧ファイル上での一致部分までの移動情報（移動コード）を出力する移動情報生成ステップと、
探索ステップで一致部分を探索できなかった場合は、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換情報（転送置換コード）に新データを付加して出力する置換情報生成ステップと、
を備えたことを特徴とする。
【００２０】
このように本発明は、新旧ファイルの順次比較で不一致となった場合には、旧ファイルを前後両方向に探索して一度参照した旧ファイル中のデータを再度参照することができ、従来の置換、挿入及び削除というカテゴリを超えて、それ以外の図１（Ｂ）のようなパターンにも対応でき、冗長な差分データの生成を低減し、差分データのサイズを小さくする。
【００２１】
また図１（Ｃ）のように、更新部分の対応付けを誤った場合でも、それ以降の差分抽出処理において、一度参照した旧ファイル中のデータを再度参照することにより、その影響を最小限に抑え、冗長な差分データの生成を低減し、差分データのサイズを小さくする。
【００２２】
ここで探索ステップは、旧ファイルの新ファイルのデータに一致する部分と、この一致部分に続く所定データ数ｎ以上の連続一致部分を探索した場合に、データが一致したと判定する。これは新旧ファイルの特定部分に一致個所が集中している場合に対応した一致判定である。
【００２３】
このように本発明は、例えば比較対照となる新ファイルの１バイトデータと参照した旧ファイルの１バイトデータが一致した場合、更に後続するｎバイト以上が一致して初めて更新されない一致部分とする２段階の一致判定を行い、更新されない一致部分と更新される不一致部分を正しく判定する。
【００２４】
この２段階の一致判定は、同時に、更新対象となる不一致部分を判定する機会を可能な限り多くし、不一致部分についての置換処理により差分データの冗長性を低減させ、差分データのサイズを小さくする。
【００２５】
探索ステップは、２段階の別の一致判定として、旧ファイルの新ファイルのデータに一致する部分と、この一致部分に続く所定データ数ｘの中に分散している所定データ数ｙ以上の一致部分を探索した場合に、データが一致したと判定してもよい。これは新旧ファイルの中に一致部分が分散していた場合の一致判定である。
【００２６】
移動情報生成ステップは、移動情報として、旧ファイル上の前方を負方向とし後方を正方向とする移動方向と、旧ファイル上で一致部分までのデータ長を表す移動長を出力する。
【００２７】
探索ステップは、ファイルの構造がｎビットコードで書かれたプログラムファイルである場合、旧ファイルの不一致と判定されたデータ位置から前後両方向にｎビット置きに探索を行って新ファイルのデータに一致する部分を探索する。これにより旧ファイルに対する一致部分の探索を高速に行うことができる。
【００２８】
置換情報生成ステップは、旧データと新データとの差分データが過去に生成された置換情報の差分データに一致する場合、新データを付加せずに過去の差分パターンまたは更新パターンと同じことを表す置換情報（転送増加コード）を出力する。
【００２９】
例えば特定のプログラムコードを変更したような場合、新旧ファイルの不一致判定に基づく置換処理で、同じ差の値をもつ差分パターンが出てくる度に、同じ値の新データが生成されるが、本発明によれば、同じ値の新データは最初だけが必要であり、残りの置換処理では新データを不要とすることで、冗長な差分データの生成を低減し、差分データのサイズを小さくする。このような本発明の置換処理による差分データ量の低減は、新旧ファイルの比較処理で可能な限りデータ不一致による置換処理の機会を増やすことにより、より一層、高められる。
【００３０】
置換情報生成ステップは、新ファイルにおける新規データの挿入により探索ステップで一致部分を探索できなかった場合は、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換情報に新規データを付加して出力する。即ち、従来の挿入処理は、本発明にあっては置換処理のひとつの形態に含まれる。
【００３１】
移動情報生成ステップは、旧ファイルにおけるデータの削除により探索ステップで新ファイルのデータとの一致部分を探索できなかった場合は、旧ファイル上の後方の一致部分までの移動方向と移動量を表す移動情報を生成する。即ち、従来の削除処理は、本発明にあっては移動処理のひとつの形態に含まれる。
【００３２】
本発明は、差分データを生成するためのプログラムを提供するものであり、このプログラムは、コンピュータに、
新旧２つのファイルに対してファイル先頭から所定データ単位に順次比較する比較ステップと、
順次比較でデータ一致を判定した場合、旧ファイルの位置とデータ長を表した転送情報を出力する転送情報生成ステップと、
順次比較でデータ不一致を判定した場合、旧ファイルの不一致と判定されたデータ位置から前後両方向に探索を行って新ファイルのデータに一致する部分を探索する探索ステップと、
探索ステップで一致部分を探索できた場合は、旧ファイル上での一致部分までの移動情報を出力する移動情報生成ステップと、
探索ステップで一致部分を探索できなかった場合は、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換情報に新データを付加して出力する置換情報生成ステップと、
を実行させることを特徴とする。
【００３３】
本発明は、差分データを生成するためのプログラムを格納したコンピュータ読取可能な記録媒体を提供するものであり、この記録媒体に格納されたプログラムは、コンピュータに、
新旧２つのファイルに対してファイル先頭から所定データ単位に順次比較する比較ステップと、
順次比較でデータ一致を判定した場合、旧ファイルの位置とデータ長を表した転送情報を出力する転送情報生成ステップと、
順次比較でデータ不一致を判定した場合、旧ファイルの不一致と判定されたデータ位置から前後両方向に探索を行って新ファイルのデータに一致する部分を探索する探索ステップと、
探索ステップで一致部分を探索できた場合は、旧ファイル上での一致部分までの移動情報を出力する移動情報生成ステップと、
探索ステップで一致部分を探索できなかった場合は、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換情報に新データを付加して出力する置換情報生成ステップと、
を実行させる。
【００３４】
本発明は、差分データ生成装置を提供するものであり、新旧２つのファイルに対してファイル先頭から所定データ単位に順次比較するデータ比較部と、データ比較部でデータ一致を判定した場合、旧ファイルの位置とデータ長を表した転送情報を出力する転送情報生成部と、データ比較部でデータ不一致を判定した場合、旧ファイルの不一致と判定されたデータ位置から前後両方向に探索を行って新ファイルのデータに一致する部分を探索する一致部分探索部と、一致部分探索部で一致部分を探索できた場合は、旧ファイル上での一致部分までの移動情報を出力する移動情報生成部と、一致部分探索部で一致部分を探索できなかった場合は、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換情報に新データを付加して出力する置換情報生成部とを備えたことを特徴とする。
【００３５】
なお、本発明におけるプログラム、記録媒体および差分データ生成装置の詳細は、差分データ生成方法の場合と基本的に同じになる。
【００３６】
【発明の実施の形態】
図２は、本発明による差分データ生成装置の機能構成のブロック図である。図２において、差分データ生成装置に対しては、入力ファイルとして旧ファイル１０と新ファイル１２が準備され、データ読み取り部１４によって両方のファイルデータが差分データ抽出部１５に読み込まれる。
【００３７】
この実施形態にあっては、旧ファイル１０及び新ファイル１２として、例えば３２ビットコード（４バイトコード）で記述されたプログラムファイルを扱うものとする。
【００３８】
差分データ抽出部１５には、データ比較部１６、転送情報生成部１８、一致部分探索部２０、移動情報生成部２２及び置換情報生成部２４が設けられている。データ比較部１６は、旧ファイル１０及び新ファイル１２からデータ読み取り部１４で読み込んだ新旧２つのファイルに対し、ファイル先頭から所定データ単位、この実施形態にあっては１バイト単位にデータを順次比較する。
【００３９】
転送情報生成部１８は、データ比較部１６によるバイト単位のデータ比較で新旧ファイルデータの一致を判定した場合、一致している旧ファイルの位置とデータ長を表した転送コードを生成して出力する。転送情報生成部１８で生成される転送コードは図３（Ａ）のフォーマット構成を持つ。
【００４０】
図３（Ａ）の転送コード３６は２バイトのコードであり、１バイト目の先頭３ビットに転送コード３６であることを示すコード番号「０１０」を格納しており、１バイト目の残り５ビット及び２バイト目の８ビットを使用して転送データ長を格納している。
【００４１】
再び図２を参照するに、一致部分探索部２０はデータ比較部１６でバイト単位に比較している新旧２つのファイルのデータ不一致を判定した場合、旧ファイルの不一致と判定されたデータ位置から前後両方向に探索を行って、新ファイルのデータに一致する部分を探索する。
【００４２】
この場合、旧ファイルの前後方向の探索は、１バイト単位とすると処理に時間がかかることから、例えば４バイトおきに旧ファイルのデータと比較する。また旧ファイルの４バイトおきの探索で一致するバイト部分が見つかった場合には、次のいずれかの条件を満足する２段階の一致判定により一致部分が探索できたと判定する。
（１）旧ファイルの新ファイル１バイトデータに一致する部分に続く所定バイト数ｎ以上、例えばｎ＝１６バイト以上、連続して一致する部分を探索した
場合に、データが一致したと判定する。
（２）旧ファイルの新ファイルの１バイトデータに一致する部分に続く所定データ数ｘ、例えばｘ＝６４バイト中に分散している他の所定バイト数ｙ、例えばｙ＝３２バイト以上、一致部分を探索した場合に、データが一致したと判定する。
【００４３】
このように旧ファイルを不一致位置から前後方向に探索して１バイト部分の一致が得られた後に、前記（１）または（２）のいずれかの条件で２段階に一致部分を判定する理由は、新旧ファイルの差分データ抽出処理において一致判断を確実にするためと同時に、差分データ抽出処理において可能な限り置換処理の機会を増加させることで差分データの冗長性を低減してデータ量を少なくするためである。
【００４４】
移動情報生成部２２は、一致部分探索部２０で旧ファイルの不一致部分からの前後方向の探索で一致部分を探索できた場合に、旧ファイル上での不一致部分から一致部分までの移動情報を示す移動コードを生成して出力する。この移動コードは、旧ファイル上の前方を負方向とし後方を正方向とする移動方向と、旧ファイル上での不一致部分から一致部分までのデータ長を表わす移動長を持つ。
【００４５】
具体的には、図３（Ｄ）の負移動コード４２または図３（Ｅ）の正移動コード４４を生成して出力する。負移動コード４２及び正移動コード４４は、図３（Ａ）の転送コード３６と同様、２バイトのコード情報であり、１バイト目の先頭２ビットにつき、負移動コード４２はコード番号「１０」を格納しており、その後ろに旧ファイル上の移動長を１バイト目の６ビット及び２バイト目の８ビットを使用して格納している。
【００４６】
図３（Ｅ）の正移動コード４４も同様に、１バイト目の先頭２ビットに正制御コードであることを示すコード番号「１１」を格納し、これに続いて移動長を１バイト目の残り６ビット及び２バイト目の８ビットを使用して格納している。
【００４７】
再び図２を参照するに、置換情報生成部２４は一致部分探索部２０で一致部分を探索できなかった場合に、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換コードに、不一致部分における新データを付加して出力する。
【００４８】
この置換情報生成部２４で生成出力される転送置換コードは、図３（Ｂ）のように２バイトの制御コードであり、１バイト目の２ビットに転送置換コード３８であることを示すコード番号「００」を格納し、これに続く６ビットに置換データ長を、２バイト目の８ビットに転送データ長（置換が起こるまでの転送データ長）を格納している。
【００４９】
本発明の置換情報生成部２４にあっては、置換情報を生成する際に、それまでの差分データ抽出処理で同じ値の差を持つ置換情報が生成されているか否かチェックし、もし同じ値の差を持つ置換情報が生成されている場合には、新データを生成せずに既存の差分パターンの存在を示す置換情報として図３（Ｃ）の転送増加コード４０を生成して出力する。
【００５０】
この転送増加コード４０は２バイトの制御コードであり、１バイト目の先頭３ビットに転送増加コードであることを示すコード番号「０１１」を格納し、これに続く５ビット及び２バイト目の８ビットを使用して転送データ長を格納している。
【００５１】
即ち本発明の置換情報生成部２４にあっては、置換処理の差の値が過去に存在していない最初の値であった場合には図３（Ｂ）の転送置換コード３８を発生し、これに新データを付加して出力するが、差の値が過去に同じ値を持つ２回目以降の場合には図３（Ｃ）の転送増加コード４０を生成して出力し、この場合に新データを付加する必要がなく、このため同じ差を持つ差分パターンが複数出る場合には１回目だけの新データの付加で済み、それ以降は必要ないことから、これによって差分データの冗長性を低減し、差分データ量を少なくできる。
【００５２】
図２の差分データ抽出部１５で生成された転送情報、移動情報及び置換情報のそれぞれにおける制御コードは、制御コード書き出し部２６で制御コード３０として書き出され、差分データ書き出し部３４によって差分データファイル３５に書き込まれる。
【００５３】
また置換情報生成部２４における図３（Ｂ）の転送置換コード３８の生成に伴って書き出された新データ、即ち更新データについては、更新データ書き出し部２８で更新データ３２として書き出され、差分データ書き出し部３４を介して差分データファイル３５に書き込まれる。
【００５４】
図４は、図２の差分データ処理装置に対応した本発明による差分データ生成処理の概略フローチャートである。図４において、ステップＳ１で新旧ファイルを読み込んで例えば１バイト単位に比較する。新旧ファイルの１バイトデータの一致がステップＳ２で判別されると、ステップＳ３で転送情報（転送コード）の生成処理を行う。
【００５５】
ステップＳ２でデータ一致が得られなかった場合、即ち不一致の場合には、ステップＳ５で新ファイルの１バイトデータに対応する旧ファイルの不一致部分の前後を探索して一致部分を探索する。
【００５６】
この一致部分は、旧ファイルにおける前後探索で１の一致が得られた後、一致した１バイトデータに続くｎ＝１６バイト以上の連続一致、あるいは１バイトに続くｘ＝６４バイト中の３２バイト以上の一致をもってデータ一致と判断している。
【００５７】
ステップＳ６で一致部分探索結果につき一致部分が得られれば、ステップＳ７で移動情報（正移動コード又は負移動コード）を生成する。一致部分がなかった場合には、ステップＳ８で置換情報生成処理を行う。
【００５８】
この置換情報生成処理は、差の値が最初に得られた値である場合には、図３（Ｂ）の転送置換コード３８を発生し、これに更新後の新データを付加して出力する。これに対し同じ差の値となる２回目以降の置換にあっては、図３（Ｃ）の転送増加コード４０を生成して出力することで、新データの付加は不要となる。このような処理をステップＳ４でファイル終了位置まで繰り返す。
【００５９】
図５は本発明の差分データ生成処理に固有な従来方法では処理できない新旧ファイルパターンの一例である。この新旧ファイルパターンは、旧ファイル１０にはデータＡ，Ｂであり、これが新ファイル１２ではデータＡ，Ａ，Ｂに更新されており、新ファイル１２にあってはデータＡの一致部分５０について新たにデータＡの一致部分５２を追加し、最後にデータＢの一致部分５４となっている。
【００６０】
図６は、図５の新旧ファイルパターンを対象とした本発明による差分データ生成処理の具体的な処理手順を示している。本発明の差分データ生成処理にあっては、新ファイル１２に対してはデータ比較対象ポインタＰを設定し、これに対し旧ファイル１０に対してはデータ参照ポインタＱを設定し、これらのポインタＰ，Ｑの位置の制御により差分データ生成処理を行う。
【００６１】
なお以下の説明にあっては、データ比較対象ポインタＰとデータ参照ポインタＱを単にポインタと言い、またポインタの制御順にＰ１，Ｐ２，Ｐ３あるいはＱ１，Ｑ２，Ｑ３というように番号を付して示している。更に、データＡ，Ｂ，Ｃのデータ長をａバイト、ｂバイト、ｃバイトとする。
【００６２】
図６において、まず新ファイル１２及び旧ファイル１０の先頭にそれぞれポインタＰ１，Ｑ１をセットし、点線で示す１バイトデータを比較する。この場合、データＡが一致部分５０となっていることから、最初の１バイト比較で１バイトデータは一致するので、一致したらポインタＰ１，Ｑ１を次の１バイトずらした位置に移動して１バイトデータを比較する。
【００６３】
この結果、Ｐ２，Ｑ２まで新ファイル１２と旧ファイル１０のデータＡはバイト一致の結果が得られる。続いて新ファイル１２及び旧ファイル１０につき、ポインタＰ３，Ｑ３に移動して次の１バイトを比較すると、この場合、データＡとデータＢの先頭バイトであり、１バイトデータは不一致となる。
【００６４】
このように１バイトデータの比較で不一致になると、本発明にあっては、旧ファイル１０における不一致位置のポインタＱ３の前後にポインタを移動して、新ファイル１２におけるポインタＰ３の１バイトデータとの一致部分の探索を行う。
【００６５】
旧ファイル１０における不一致部分のポインタＱ３の前後における一致部分の探索にあっては、例えば４バイトおきに旧ファイル１０の１バイトデータを抽出して比較する。この探索により旧ファイル１０の前方のデータＡにおける先頭１バイトが、新ファイル１２のポインタＰ３の1バイトに一致する。
【００６６】
この不一致部分の前後の探索で旧ファイル１０から一致部分が判別されたならば、ポインタＱ３を一致部分のポインタＱ３'に移動する。そして新ファイル１２のポインタＰ３の1バイトデータと、探索により移動した旧ファイル１０のＱ３'の１バイトから、順番にバイト単位の比較を行う。
【００６７】
この場合には共にデータＡであることから、ポインタＰ４，Ｑ４までバイト単位のデータ一致が得られる。続いてポインタをＰ５，Ｑ５に移動してデータＢの先頭バイトを比較すると、この場合にもデータ一致となり、このデータ一致は最後のポインタＰ６，Ｑ６まで続くことになる。
【００６８】
このような図６におけるポインタの制御による差分データの抽出処理により、図７の差分データファイル３５に示すような転送コード５６、負移動コード５８及び転送コード６０が生成されて出力される。まず図６の新旧ファイルにおける先頭のデータＡにあっては、コード内容にデータＡのデータ長であるａバイトをもつ転送コード５６が生成される。
【００６９】
続いて、ポインタＰ３とポインタＱ３の１バイトデータの不一致部分による旧ファイル１０の前後探索でデータＡの先頭バイトとの一致が得られたときのポインタＱ３からＱ３'への移動を示す負移動コード５８が生成される。この負移動コード５８は、ポインタＱ３が前方のＱ３'に移動する負方向の移動であることから、負移動コード５８を生成し、移動長はポインタのずれ量を示す−ａバイトを格納している。
【００７０】
そして最後に、新ファイル１２における２番目のデータＡと最後のデータＢに対する旧ファイル１０のデータＡ，Ｂとの一致を示す転送コード６０を生成して出力しており、この場合の転送データ長はデータａとデータｂのバイト長ａ，ｂを加算した（ａ＋ｂ）バイトとなっている。
【００７１】
図８は、図６のポインタＰ３，Ｑ３で１バイトデータが不一致となり、旧ファイル１０について前後方向に探索して前方のデータＡの先頭の１バイトデータと一致したときに、続いて行われる２段目の一致判断の具体例を示している。
【００７２】
図８にあっては、新ファイル１２の１バイトデータ６２と旧ファイル１０の１バイトデータ６４の不一致で後方に探索して１バイトデータ６６との一致を探索した場合である。この場合、探索した１バイトデータ６６に続くデータ部分７０としてｎ＝１６バイト以上、新ファイル１２のデータ部分６８と一致する場合に、一致部分を探索できたものと判定する。
【００７３】
図９は一致探索における他の２段階の一致部分判定処理の説明図である。この場合には、新ファイル１２の１バイトデータ６２の後方の探索で１バイトデータ６６との一致が判別されると、これに続くｘ＝６４バイト中のｙ＝３２バイト以上が一致した場合、即ち一致する１バイトデータ６２，６６に続く新旧ファイル１２，１０においてデータ部分７２−１〜７２−５と７４−１〜７４−５の一致部分の合計バイト数がｙ＝３２バイト以上であった場合に、一致部分を探索できたと判定する。
【００７４】
このように図８または図９のいずれかの一致条件が得られたときには、新ファイル１２と旧ファイル１０の間において一致箇所にずれが発生したものと判定し、図３（Ｄ）の負移動コード４２または図３（Ｅ）の正移動コード４４をずれの方向に応じて発生させる。
【００７５】
このずれの発生を示す負移動コード４２または正移動コード４４の発生により、旧ファイル１０上でポインタをずれ量だけ移動した後の処理は、再びずらしたポインタ位置からのバイト単位の比較による差分データ抽出処理となる。
【００７６】
図１０は、更新部分を誤判定した場合の本発明で処理可能な新旧ファイルパターンの説明図である。
【００７７】
図１０において、旧ファイル１０はデータＡ，Ｂ，Ｃ，Ｂで構成されている。これに対し更新後の新ファイル１２は、データＡ，Ｂ，Ｃで構成されている。もし正常に差分データ生成処理が行われれば、データＡ，Ｂ，Ｃの全てが一致部分であることから、転送データ長（ａ＋ｂ＋ｃ）バイトの転送コードを生成して出力すればよい。
【００７８】
しかしながら、２番目のデータＢの処理において誤判定が行われ、旧ファイル１０のデータＢに対し新ファイル１２のデータがＢ'と誤って判定されたとする。このようなデータＢをデータＢ'と誤った誤判定につき、従来方法にあってはデータが相違することから、置換処理により差分データを生成し、このため誤判定の結果がその後の旧ファイル１０の更新に誤ったデータとして承継されることになっている。
【００７９】
しかしながら、本発明にあっては、データＢをＢ'と誤判定した場合にはデータ不一致であることから、旧ファイル１０における不一致部分となるデータＢに対し前後方向に探索を行う。この場合には後方の探索で一致するデータＢを一致部分として探索し、ポインタを旧ファイル１０の後ろのデータＢの先頭に移動して差分抽出処理を行うことで、旧ファイル１０の終端のデータＢを転送する転送コードが生成される。これによって最初に誤判定した部分７８のデータが正しいデータに更新されることになる。
【００８０】
誤判定部分７８から旧ファイル１０の後ろのデータＢに移動したポインタは、データＢの差分抽出処理が済むと、逆に負方向のポインタ移動８２によりデータＣの先頭に戻り、データＣを一致部分８０とする転送コードの生成出力が行われる。
【００８１】
図１１は、図１０の誤判定部分７８を含んだ場合の新旧ファイルに対する本発明の差分データ生成処理のポインタ制御による説明図である。
【００８２】
新旧ファイル１２，１０におけるデータＡに対応したポインタＰ１〜Ｐ２およびＱ１〜Ｑ２の処理は、図６の場合と同じであるが（転送コード８２を発生）、ポインタＰ３の移動でデータＢ'の先頭の１バイトをポインタＱの旧ファイル１０のデータＢと比較した際に、不一致と誤判定しており、この誤判定により本発明にあっては、不一致部分のポインタＱ３に対し前後方向に探索を行う。
【００８３】
この場合、旧ファイル１０の誤判定したデータＢ'は本来正しくはデータＢであることから、旧ファイル１０の最後のデータＢの先頭の１バイトの探索でデータ一致となり、このとき図８または図９に示した２段階目の一致条件を満足していたとすると、データＢとの一致部分が判定され、旧ファイル１０のポインタＱ３をＱ３'に移動し、これに伴ってポインタＱ３からのずれ＋（ｃ＋ｂ）バイトを格納した図１２の差分データファイル３５に示す正移動コード８４を発生する。
【００８４】
続いて新ファイル１２のポインタＰ３〜Ｐ４と旧ファイル１０の移動済みのポインタＱ３'〜Ｑ４の移動でデータＢの一致が判別され、図１２の転送データ長ｂバイトの転送コード８６が生成される。
【００８５】
続いて、新ファイル１２のポインタＰ５と旧ファイル１０の末尾のポインタＱ５を比較してもデータ一致にはならないことから、ポインタＱ５に対し前後方向、この場合には前方にしかデータがないことから前方方向に探索し、データＣの先頭バイトとの一致を判別する。
【００８６】
この１バイトデータの一致につき、続いて図８または図９の一致条件が得られると、一致部分と判定され、ポインタＱ５をＱ５'に移動し、このポインタの移動を示すため−（ｃ＋ｂ）バイトの移動長を格納した図１２の負移動コード８８を生成する。
【００８７】
そして新ファイル１２のポインタＰ５〜Ｐ６と旧ファイル１０の移動済みのポインタＱ５'〜Ｑ６の動きによるデータＣの一致により、図１２の転送データ長ｃバイトの転送コード９０を発生する。
【００８８】
このように本発明の差分データ生成処理にあっては、従来の差分データ生成方法における置換、削除または挿入のカテゴリでは対応できない新旧ファイルのパターンに対し適切に対応でき、また置換位置を誤判定したような場合にも、後続する処理によって、一度参照した旧ファイルの部分を再度参照することにより、誤った判定部分の差分データを修正することができる。
【００８９】
図１３は更新部分を持つ新旧ファイルパターンである。この新旧ファイルパターンにあっては、旧ファイル１０はデータＡ，Ｂ，Ｃで構成されており、これに対し新ファイル１２はデータＡ，Ｂ'，Ｃで構成されており、データＡ，Ｃの一致部分に対しデータＢ，Ｂ'の部分が置換データ９６となっている。
【００９０】
図１４は、図１３の新旧ファイルパターンに対する本発明の差分データ生成処理のポインタ制御による具体例である。図１４において、新旧ファイルの先頭のデータＡにあっては、ポインタＰ１〜Ｐ２及びＱ１〜Ｑ２の制御によりデータＡの一致判別が行われる。
【００９１】
続いて新ファイル１２のポインタＰ３及び旧ファイル１０のポインタＱ３への移動によりデータＢ，Ｂ'の先頭１バイトを比較するが、この場合には更新によりデータ不一致となる。この１バイトデータの不一致に対し、旧ファイル１０について前後方向を探索しても一致部分は得られないことから、ポインタＰ３，Ｑ３を後方に１バイトずつ移動し、これをポインタＰ４，Ｑ４まで繰り返す。
【００９２】
更にポインタＰ５，Ｑ５に移動すると、次のデータＣの先頭１バイトの比較となり、一致部分と判別され、同時に図８または図９の２段階目の一致条件が満足されることで一致部分と判定される。したがって、この時点で置換部分となるデータＢとＢ'につき、図５の置換データ長ｃバイトと転送データ長ａバイトの転送置換コード１０２を発生する。
【００９３】
このとき差の値（Ｂ−Ｂ'）を求めており、この差の値（Ｂ−Ｂ'）は過去の置換コードの差分データの値と一致しない初めて出た値であることから、転送置換コード１０２を生成し、これにＢ'の値を持つ新データ１０４を付加して出力する。
【００９４】
そして図１４において、新ファイル１２のポインタＰ５〜Ｐ６の移動と、これに同期した旧ファイル１０におけるポインタＱ５〜Ｑ６の移動により、データＣの一致部分が判別され、図１５の転送データ長ｃバイトの転送コード１０６が生成される。
【００９５】
図１６は、図１３のような置換データ９６を持つ置換処理において、置換部分の差分パターンとして同一の差の値が繰り返される場合の処理説明図である。
【００９６】
図１６の旧ファイル１０及び新ファイル１２は、４ビットのバイトコードを１６進の数値で表わしている。この新旧ファイルを比較すると、一致部分１０８，１１０，１１２，１１４，１１６の間に不一致部分１１８，１２０，１２２，１２４がそれぞれ存在している。
【００９７】
ここで、不一致部分１１８〜１２４における旧ファイル１０に対する新ファイル１２の２バイトデータの差が、共に同じ１６進値「１１」となっている。このような場合、本発明の差分データ生成処理にあっては、先頭の不一致部分１１８におけるデータバイトの差が最初に得られた値であることから、図３（Ｂ）の転送置換コード３８を発生し、これに新データ「１６」を付加する。
【００９８】
これに対し２番目以降の不一致部分１２０，１２２，１２４については、データバイトの差が同じ１６進値「１１」であることから、この場合には図３（Ｃ）の転送増加コード４０を生成し、新データは付加しない。これによって置換処理で生成する差分データの冗長性を低減し、差分データ量を大きく低減することができる。
【００９９】
この場合、差分データの復元側では、転送置換コード３８に付加している新データ「１６」から旧データとの差「１１」を求め、その後に転送増加コード４０を受けると、対応する旧データに差「１１」を加算することで新データが復元できる。
【０１００】
図１７は、本発明によりデータ削除の移動処理を行う新旧ファイルパターンの説明図である。この新旧ファイルパターンにあっては、旧ファイル１０のデータＡ，Ｂ，ＣからデータＢを削除データ１３０とすることで新ファイル１２のデータＡ，Ｃを得ており、新ファイル１２におけるデータＡ，Ｃに対応する部分が一致部分１２６，１２８となる。
【０１０１】
図１８は、図１７の新旧ファイルパターンを対象としたポインタ制御による本発明の差分データ生成処理である。この場合、新ファイル１２のポインタＰ３の位置で旧ファイル１０のポインタＱ３の１バイトデータ、即ちデータＣの先頭バイトとの不一致が判別され、不一致部分に対し前後方向に探索すると、後方に＋ｃバイトずれたＢデータの先頭バイトでデータ一致が得られる。
【０１０２】
このため旧ファイル１０のポインタＱ３をポインタＱ３'に移動し、このポインタＱ３'の移動により、図１９の差分データファイル３５における２番目の移動長＋ｃバイトの正移動コード１３４を発生している。その前の一致部分のデータＡ，Ｂにおける制御コードは転送コード１３２及び転送コード１３６である。
【０１０３】
図２０は、本発明でデータ挿入の移動処理を行う新旧ファイルパターンの説明図である。この場合、旧ファイル１０のデータＡ，Ｂの間に新ファイル１２のようにデータＣを挿入し、挿入データ１４０としている。
【０１０４】
図２１は、図２０の新旧ファイルパターンに対する本発明のポインタ制御による差分抽出処理である。この場合、新ファイル１２のポインタＰ３及び旧ファイル１０のポインタＱ３の位置でデータＣとデータＢの先頭１バイトが不一致となり、旧ファイル１０において不一致部分の前後方向に探索しても一致部分は得られないことから、新ファイル１２及び旧ファイル１０について順次後方にポインタを移動し、ポインタＰ４，Ｑ４までの移動でそれぞれ不一致となる。
【０１０５】
次にポインタＰ５，Ｑ５に移動して、１バイトデータの不一致になり、これに伴って旧ファイル１０上で不一致部分の前後方向に探索を行うと、データＢの先頭１バイトとの一致部分が判別される。このような一致部分の判別により、新ファイル１２におけるポインタＰ３〜Ｐ４のデータＣは、新規データ即ち挿入部分となるデータであることが判別できる。
【０１０６】
このため図２２の差分データファイル３５において、置換処理により転送置換コード１４６を発生し、これにＣの値を持つ新データ１４８を付加して出力する。
【０１０７】
続いて図２１において、旧ファイル１０においてポインタＱ５を前方となる負方向に−ｃバイトずらしてポインタＱ５'としたことを示す負移動コード１５０を生成して出力する。最後に、ポインタＰ５〜Ｐ６とポインタＱ５'〜Ｑ６'の同期移動によりデータＢの一致部分を判別し、図２２の転送コード１５２を生成して出力する。
【０１０８】
図２３、図２４及び図２５は、図５〜図２２に示した本発明による差分データ生成処理を具体的に実現するためのプログラムを実現するフローチャートである。図２３において、まずステップＳ１で旧ファイルと新ファイルを読み込む。次のステップＳ２でデータ比較対象ポインタＰ、データ参照ポインタＱを、それぞれファイルの先頭にセットする。ステップＳ３では比較対象ポインタＰと参照ポインタＱの値を比較し、ステップＳ４で、比較したデータ即ち１バイトデータが同じ値であれば、ステップＳ５に進み、その１バイトデータは旧ファイルのデータのコピーであると判定する。
【０１０９】
そしてステップＳ６でコピー元の位置と長さを記憶する。次にステップＳ７で、データ比較対象ポインタＰ、データ参照ポインタＱをそれぞれ１バイト後ろに移動させる。ステップＳ８でデータ比較対象ポインタＰが新ファイルの最後でなければ、ステップＳ３に戻り、同様の処理を繰り返す。
【０１１０】
ステップＳ８でデータ比較対象ポインタＰが新ファイルの最後であれば、ステップＳ２２に進み、未処理のコピー元の記憶があれば、ステップＳ２３で転送コードの書き出しを行った後、一連の処理を終了する。
【０１１１】
一方、ステップＳ４で比較データが不一致であった場合には、図２４のステップＳ９に進む。ステップＳ９では、データ比較位置の前後で新ファイルのデータと値が一致する位置を４バイトおきに旧ファイルから探索する。
【０１１２】
ステップＳ１０で一致箇所が見つからなかった場合には、ステップＳ１１で、比較されたデータは新規に生成されたものであると判断し、ステップＳ１２でデータ比較対象ポインタＰを１バイト後ろに移動させる。挿入データが新ファイルにあった場合には、このステップＳ９〜Ｓ１２の処理を挿入データの最後の１バイトデータまで繰り返す。
【０１１３】
ステップＳ１０で一致箇所を見つけられた場合には、ステップＳ１３に進み、図８に示したように一致部分の後ろｎバイトデータが連続して一致しているか否か判定する。この条件を満たしていない場合にはステップＳ１４に進み、図９に示したように一致部分の後ろのｘバイト中のｙバイトのデータが一致しているか否か判別する。
【０１１４】
ステップＳ１３，Ｓ１４の条件のいずれかが満足された場合には、図２５のステップＳ１５に進み、一致箇所のずれが起こったと判定する。続いてステップＳ１６で、データ比較対象ポインタＰとデータ参照ポインタＱのずれは同じか否かチェックする。
【０１１５】
異なっていればデータ参照ポインタＱがずらされていることから、ステップＳ１７で、図２３のステップＳ６で記憶されている情報に基づく転送コードを書き出した後、ポインタの移動を示す移動コードの書き出しを行う。この移動コードの書き出しは、前方となる負方向の移動であれば負移動コードを発生し、後方となる正方向の移動であれば正移動コードを発生する。そしてステップＳ１８でデータ参照ポインタＱをずれ分だけ移動させる。
【０１１６】
ステップＳ１６でデータ比較対象ポインタＰとデータ参照ポインタＱのずれが同じである場合には置換処理と判断し、ステップＳ１９に進む。ステップＳ１９では旧ファイルのデータとの差が以前のものと一致しているか否か判断する。
【０１１７】
差分データが以前のものと不一致であった場合には、ステップＳ２１に進み、図２３のステップＳ６で記憶している情報に基づき転送コードを書き出した後、置換を示す転送置換コードを書き出し、更に旧ファイルのデータとの差の値を記憶する。
【０１１８】
一方、ステップＳ１９において以前の差の値に一致している場合には、ステップＳ２０に進み、図２３のステップＳ６の記憶内容に応じた転送コードを書き出した後、新データを付加する必要のない転送増加コードを書き出す。以上の処理を図２３のステップＳ８でデータ比較対照ポインタＰが新ファイルの最後に達するまで繰り返す。
【０１１９】
次に本発明の差分データ生成処理を実現するプログラムを格納したコンピュータ読取可能な記録媒体の実施形態を説明する。
【０１２０】
本発明の差分データ生成処理を行うためのプログラムが実行されるコンピュータシステムは、ＣＰＵ、ＲＡＭ、ＲＯＭ、ハードディスクドライブ、ＣＤ−ＲＯＭドライブ、ＦＤドライブ、キーボード、マウス、ディスプレイ、入出力インタフェース、ＬＡＮインタフェース、モデムなどを備えている。
【０１２１】
本発明の差分データ生成プログラムは、記録媒体として例えばＣＤ−ＲＯＭ、フロッピィディスク（Ｒ）、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの可搬型記憶媒体、モデムやＬＡＮインタフェースを利用して回線を介して接続されたデータベース、あるいは他のコンピュータシステムのデータベースに格納され、本発明を実現するコンピュータにインストールされた後に実行される。
【０１２２】
なお本発明は上記の実施形態に限定されず、その目的と利点を達成することのできる適宜の変形を含む。また本発明は上記の実施形態に示した数値による限定は受けない。
【０１２３】
（付記）
（付記１）
新旧２つのファイルに対してファイル先頭から所定データ単位に順次比較する比較ステップと、
前記順次比較でデータ一致を判定した場合、旧ファイルの位置とデータ長を表した転送情報を出力する転送情報生成ステップと、
前記順次比較でデータ不一致を判定した場合、旧ファイルの不一致と判定されたデータ位置から前後両方向に探索を行って新ファイルのデータに一致する部分を探索する探索ステップと、
前記探索ステップで一致部分を探索できた場合は、旧ファイル上での一致部分までの移動情報を出力する移動情報生成ステップと、
前記探索ステップで一致部分を探索できなかった場合は、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換情報に新データを付加して出力する置換情報生成ステップと、
を備えたことを特徴とする差分データ生成方法。（１）
【０１２４】
（付記２）
付記１記載の差分データ生成方法に於いて、前記探索ステップは、旧ファイルの新ファイルのデータに一致する部分と、該一致部分に続く所定データ数ｎ以上の連続一致部分を探索した場合に、データが一致したと判定することを特徴とする差分データ生成方法。
【０１２５】
（付記３）
付記１記載の差分データ生成方法に於いて、前記探索ステップは、旧ファイルの新ファイルのデータに一致する部分と、該一致部分に続く所定データ数ｘの中に分散している所定データ数ｙ以上の一致部分を探索した場合に、データが一致したと判定することを特徴とする差分データ生成方法。
【０１２６】
（付記４）
付記１記載の差分データ生成方法に於いて、前記移動情報生成ステップは、前記移動情報として、旧ファイル上の前方を負方向とし後方を正方向とする移動方向と、旧ファイル上で一致部分までのデータ長を表す移動長を出力することを特徴とする差分データ生成方法。
【０１２７】
（付記５）
付記１記載の差分データ生成方法に於いて、前記探索ステップは、ファイルの構造がｎビットコードで書かれたプログラムファイルである場合、旧ファイルの不一致と判定されたデータ位置から前後両方向にｎビット置きに探索を行って新ファイルのデータに一致する部分を探索すること輪特徴とする差分データ生成方法。
【０１２８】
（付記６）
付記１記載の差分データ生成方法に於いて、前記置換情報生成ステップは、旧データと新データとの差分データが過去に生成された置換情報の差分データに一致する場合、新データを付加せずに過去の差分パターン又は更新パターンと同じことを表す転送置換情報（転送増加情報）を出力することを特徴とする差分データ生成方法。（２）
【０１２９】
（付記７）
付記１記載の差分データ生成方法に於いて、前記置換情報生成ステップは、新ファイルにおける新規データの挿入により前記探索ステップで一致部分を探索できなかった場合は、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換情報に前記新規データを付加して出力することを特徴とする差分データ生成方法。
【０１３０】
（付記８）
付記１記載の差分データ生成方法に於いて、前記移動情報生成ステップは、旧ファイルにおけるデータの削除により前記探索ステップで新ファイルのデータとの一致部分を探索できなかった場合は、旧ファイル上の後方の一致部分までの移動方向と移動量を表す移動情報を生成することを特徴とする差分データ生成方法。
【０１３１】
（付記９）
コンピュータに、
新旧２つのファイルに対してファイル先頭から所定データ単位に順次比較する比較ステップと、
前記順次比較でデータ一致を判定した場合、旧ファイルの位置とデータ長を表した転送情報を出力する転送情報生成ステップと、
前記順次比較でデータ不一致を判定した場合、旧ファイルの不一致と判定されたデータ位置から前後両方向に探索を行って新ファイルのデータに一致する部分を探索する探索ステップと、
前記探索ステップで一致部分を探索できた場合は、旧ファイル上での一致部分までの移動情報を出力する移動情報生成ステップと、
前記探索ステップで一致部分を探索できなかった場合は、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換情報に新データを付加して出力する置換情報生成ステップと、
を実行させることを特徴とする差分データ生成のためのプログラム。（３）
【０１３２】
（付記１０）
付記９記載のプログラムに於いて、前記探索ステップは、旧ファイルの新ファイルのデータに一致する部分と、該一致部分に続く所定データ数ｎ以上の連続一致部分を探索した場合に、データが一致したと判定することを特徴とするプログラム。
【０１３３】
（付記１１）
付記９記載の差分データ生成方法に於いて、前記探索ステップは、旧ファイルの新ファイルのデータに一致する部分と、該一致部分に続く所定データ数ｘの中に分散している所定データ数ｙ以上の一致部分を探索した場合に、データが一致したと判定することを特徴とするプログラム。
【０１３４】
（付記１２）
付記９記載のプログラムに於いて、前記移動情報生成ステップは、前記移動情報として、旧ファイル上の前方を負方向とし後方を正方向とする移動方向と、旧ファイル上で一致部分までのデータ長を表す移動長を出力することを特徴とするプログラム。
【０１３５】
（付記１３）
付記９記載のプログラムに於いて、前記探索ステップは、ファイルの構造がｎビットコードで書かれたプログラムファイルである場合、旧ファイルの不一致と判定されたデータ位置から前後両方向にｎビット置きに探索を行って新ファイルのデータに一致する部分を探索すること輪特徴とするプログラム。
【０１３６】
（付記１４）
付記９記載のプログラムに於いて、前記置換情報生成ステップは、旧データと新データとの差分データが過去に生成された置換情報の差分データに一致する場合、新データを付加せずに過去の差分パターン又は更新パターンと同じことを表す転送置換情報（転送増加情報）を出力することを特徴とするプログラム。
【０１３７】
（付記１５）
付記９記載のプログラムに於いて、前記置換情報生成ステップは、
新ファイルにおける新規データの挿入により前記探索ステップで一致部分を探索できなかった場合は、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換情報に前記新規データを付加して出力することを特徴とするプログラム。
【０１３８】
（付記１６）
付記１記載のプログラムに於いて、前記移動情報生成ステップは、旧ファイルにおけるデータの削除により前記探索ステップで新ファイルのデータとの一致部分を探索できなかった場合は、旧ファイル上の後方の一致部分までの移動方向と移動量を表す移動情報を生成することを特徴とするプログラム。
【０１３９】
（付記１７）
コンピュータに、
新旧２つのファイルに対してファイル先頭から所定データ単位に順次比較する比較ステップと、
前記順次比較でデータ一致を判定した場合、旧ファイルの位置とデータ長を表した転送情報を出力する転送情報生成ステップと、
前記順次比較でデータ不一致を判定した場合、旧ファイルの不一致と判定されたデータ位置から前後両方向に探索を行って新ファイルのデータに一致する部分を探索する探索ステップと、
前記探索ステップで一致部分を探索できた場合は、旧ファイル上での一致部分までの移動情報を出力する移動情報生成ステップと、
前記探索ステップで一致部分を探索できなかった場合は、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換情報に新データを付加して出力する置換情報生成ステップと、
を実行させるプログラムを格納したコンピュータ読取可能な記録媒体。（４）
【０１４０】
（付記１８）
新旧２つのファイルに対してファイル先頭から所定データ単位に順次比較するデータ比較部と、
前記データ比較部でデータ一致を判定した場合、旧ファイルの位置とデータ長を表した転送情報を出力する転送情報生成部と、
前記データ比較部でデータ不一致を判定した場合、旧ファイルの不一致と判定されたデータ位置から前後両方向に探索を行って新ファイルのデータに一致する部分を探索する一致部分探索部と、
前記一致部分探索部で一致部分を探索できた場合は、旧ファイル上での一致部分までの移動情報を出力する移動情報生成部と、
前記一致部分探索部で一致部分を探索できなかった場合は、一致部分を探索できるまでの旧ファイルの不一致部分のデータ長を表した転送置換情報に新データを付加して出力する置換情報生成部と、
を備えたことを特徴とする差分データ生成装置。（５）
【０１４１】
【発明の効果】
以上説明してきたように本発明によれば、新旧ファイルの順次比較で不一致となった場合に、旧ファイルの前後両方向に探索して、一度参照した旧ファイル中のデータを再度参照することができ、これにより従来の置換、挿入及び削除というカテゴリを超えて、それ以外のパターンにも対応でき、冗長な差分データの生成を低減し、差分データのサイズを小さくすることができる。
【０１４２】
また新旧ファイルの順次比較により、更新部分の対応付けを誤った場合でも、それ以降の処理において、一度参照した旧ファイル中のデータを再度参照することにより、誤った生成部分を修正することができ、対応付けの誤りによる影響を最小限に抑え、差分データによる更新の信頼性を向上できる。
【０１４３】
また本発明の更新処理にあっては、同じ差をもつパターンが複数生成される場合には、最初は更新後の新データを必要とするが、２番目以降については過去のパターンを使用することを表わす置換情報を生成することで、新データの付加を不要とし、置換処理が増えても差分データの冗長性を低減させ、差分データのサイズを小さくすることができる。
【０１４４】
また本発明にあっては、新旧ファイルの例えばバイトデータの不一致を判定した場合の旧ファイルにおける不一致部分の前後の探索でバイトデータの一致が得られた場合、それに後続する所定バイト数以上のデータ一致あるいは後続する所定バイト中の他の所定数以上のデータ一致が得られたときに、一致部分と判定して、データのずれを示す移動情報を出力しており、旧ファイル上での制御位置即ちポインタのずれを示す移動情報の発生を確実にすると共に、ある程度まとまった一致部分が得られない場合は置換処理とすることで置換情報を生成する機会を増やし、置換情報を生成する機会が増えれば、同じパターンについて２回目以降については新データの付加を必要としない置換情報の生成ができるため、トータル的に差分データ量の冗長性を低減してサイズを小さくすることができる。
【図面の簡単な説明】
【図１】本発明の原理説明図
【図２】本発明の装置構成における機能ブロック図
【図３】本発明で生成する差分制御コードの説明図
【図４】本発明の差分データ生成処理の概略フローチャート
【図５】本発明で処理可能な新旧ファイルパターンの説明図
【図６】図５の新旧ファイルを対象とした本発明のポインタ制御による差分生成処理の説明図
【図７】図６の処理で生成された差分データファイルの説明図
【図８】本発明における一致部分２段階判定の説明図
【図９】本発明における他の一致部分２段階判定の説明図
【図１０】本発明で処理する更新部分を誤判定した場合の新旧ファイルパターンの説明図
【図１１】図１０の新旧ファイルを対象とした本発明のポインタ制御による差分生成処理の説明図
【図１２】図１１の処理で生成された差分データファイルの説明図
【図１３】本発明で置換処理を行う新旧ファイルパターンの説明図
【図１４】図１３の新旧ファイルパターンを対象とした本発明のポインタ制御による差分データ生成処理の説明図
【図１５】図１４の処理で生成された差分データファイルの説明図
【図１６】同じ値を持つ差分データに対する本発明の置換処理の説明図
【図１７】本発明でデータ削除の移動処理を行う新旧ファイルパターンの説明図
【図１８】図１７の新旧ファイルを対象とした本発明のポインタ制御による差分生成処理の説明図
【図１９】図１７の処理で生成された差分データファイルの説明図
【図２０】本発明でデータ挿入の移動処理を行う新旧ファイルパターンの説明図
【図２１】図２０の新旧ファイルを対象とした本発明のポインタ制御による差分生成処理の説明図
【図２２】図２１の処理で生成された差分データファイルの説明図
【図２３】本発明による差分データ生成処理のフローチャート
【図２４】図２３に続くフローチャート
【図２５】図２４に続くフローチャート
【図２６】従来の差分データ生成処理のフローチャート
【図２７】図２６に続くフローチャート
【図２８】従来の置換処理の説明図
【図２９】従来の挿入処理の説明図
【図３０】従来の削除処理の説明図
【図３１】従来の置換、挿入及び削除のカテゴリには属さない新旧ファイルパターンの説明図
【図３２】更新部分の対応付けを誤った従来方法では解消できない新旧ファイルパターンの説明図
【図１】
0004205350.tif 000002
【図２】
0004205350.tif 000003
【図３】
0004205350.tif 000004
【図４】
0004205350.tif 000005
【図５】
0004205350.tif 000006
【図６】
0004205350.tif 000007
【図７】
0004205350.tif 000008
【図８】
0004205350.tif 000009
【図９】
0004205350.tif 000010
【図１０】
0004205350.tif 000011
【図１１】
0004205350.tif 000012
【図１２】
0004205350.tif 000013
【図１３】
0004205350.tif 000014
【図１４】
0004205350.tif 000015
【図１５】
0004205350.tif 000016
【図１６】
0004205350.tif 000017
【図１７】
0004205350.tif 000018
【図１８】
0004205350.tif 000019
【図１９】
0004205350.tif 000020
【図２０】
0004205350.tif 000021
【図２１】
0004205350.tif 000022
【図２２】
0004205350.tif 000023
【図２３】
0004205350.tif 000024
【図２４】
0004205350.tif 000025
【図２５】
0004205350.tif 000026
【図２６】
0004205350.tif 000027
【図２７】
0004205350.tif 000028
【図２８】
0004205350.tif 000029
【図２９】
0004205350.tif 000030
【図３０】
0004205350.tif 000031
【図３１】
0004205350.tif 000032
【図３２】
0004205350.tif 000033