(57)【要約】【課題】  更新後ファイルを構築する際に、更新後ファイルが存在する送信側装置と更新前ファイルが存在する受信側装置との間で送受信されるデータの量を少なくする。【解決手段】  ファイル構築プログラムであって、コンピュータに、更新前ファイルから更新前ファイル符号を生成する手順、更新後ファイル符号と更新前ファイル符号とを比較し、更新後ファイル符号と一致する更新前ファイル符号を探索する手順、更新後ファイル符号と一致する更新前ファイル符号を発見できた場合は、更新前ファイル符号に対応する更新前ファイルのデータブロックを構築中ファイルの最後尾に付加する手順、更新後ファイル符号と一致する更新前ファイル符号を発見できなかった場合は、当該更新後ファイル符号に対応する更新後ファイルのデータブロックの送信を外部へ要求し、外部から受信した更新後ファイルのデータブロックを構築中ファイルの最後尾に付加する手順、を実行させる。【選択図】      図４
2005251011.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに
更新前ファイルから更新前ファイル符号を生成する手順、
更新後ファイルから生成された更新後ファイル符号のセットを外部から受信する手順、
前記更新後ファイル符号と前記更新前ファイル符号とを比較し、前記更新後ファイル符号と一致する前記更新前ファイル符号を探索する手順、
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できた場合は、当該更新前ファイル符号に対応する前記更新前ファイルのデータブロックを構築中ファイルの最後尾に付加する手順、
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できなかった場合は、当該更新後ファイル符号に対応する更新後ファイルのデータブロックの送信を前記外部へ要求し、前記外部から受信した前記更新後ファイルの前記データブロックを前記構築中ファイルの最後尾に付加する手順、
を実行させるためのファイル構築プログラム。
【請求項２】
前記セット内に同一の前記更新後ファイル符号が２以上含まれているかを調べる手順、
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できなかった場合に、当該更新後ファイル符号に対応する更新後ファイルのデータブロックを既に受信しているかを調べ、既に受信している場合は当該データブロックを構築中ファイルの最後尾に付加する手順、をさらに含む請求項１記載のファイル構築プログラム。
【請求項３】
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できなかった場合に、前記更新前ファイルの全ての開始位置について更新前ファイル符号を生成したかを調べ、全ての開始位置について更新前ファイル符号を生成していない場合は、更新前ファイル符号を生成していない開始位置について更新前ファイル符号を生成する手順、をさらに含む請求項１又は２記載のファイル構築プログラム。
【請求項４】
コンピュータが
更新前ファイルから更新前ファイル符号を生成する手順、
更新後ファイルから生成された更新後ファイル符号のセットを外部から受信する手順、
前記更新後ファイル符号と前記更新前ファイル符号とを比較し、前記更新後ファイル符号と一致する前記更新前ファイル符号を探索する手順、
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できた場合は、当該更新前ファイル符号に対応する前記更新前ファイルのデータブロックを構築中ファイルの最後尾に付加する手順、
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できなかった場合は、当該更新後ファイル符号に対応する更新後ファイルのデータブロックの送信を前記外部へ要求し、前記外部から受信した前記更新後ファイルの前記データブロックを前記構築中ファイルの最後尾に付加する手順、
からなるファイル構築方法。
【請求項５】
前記セット内に同一の前記更新後ファイル符号が２以上含まれているかを調べる手順、
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できなかった場合に、当該更新後ファイル符号に対応する更新後ファイルのデータブロックを既に受信しているかを調べ、既に受信している場合は当該データブロックを構築中ファイルの最後尾に付加する手順、をさらに含む請求項４記載のファイル構築方法。
【請求項６】
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できなかった場合に、前記更新前ファイルの全ての開始位置について更新前ファイル符号を生成したかを調べ、全ての開始位置について更新前ファイル符号を生成していない場合は、更新前ファイル符号を生成していない開始位置について更新前ファイル符号を生成する手順、をさらに含む請求項４又は５記載のファイル構築方法。
【請求項７】
第１コンピュータに、
更新後ファイルを複数のブロックに分割し、各ブロックから生成された複数の更新後ファイル符号からなる更新後ファイル符号セットを送信する手順を実行させ、
第２コンピュータに、
前記更新後ファイル符号セットを前記第１コンピュータから受信する手順、
更新前ファイルから更新前ファイル符号を生成する手順、
前記更新後ファイル符号と前記更新前ファイル符号とを比較し、前記更新後ファイル符号と一致する前記更新前ファイル符号を探索する手順、
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できた場合は、当該更新前ファイル符号に対応する前記更新前ファイルのデータブロックを構築中ファイルの最後尾に付加する手順、
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できなかった場合は、当該更新後ファイル符号に対応する更新後ファイルのデータブロックの送信を前記第１コンピュータへ要求し、前記第１コンピュータから受信した前記更新後ファイルの前記データブロックを前記構築中ファイルの最後尾に付加する手順、を実行させるファイル構築プログラム。
【請求項８】
更新後ファイルを複数のブロックに分割し、各ブロックから生成された複数の更新後ファイル符号からなる更新後ファイル符号セットを送信する第１コンピュータと、
前記更新後ファイル符号セットを前記第１コンピュータから受信し、
更新前ファイルから更新前ファイル符号を生成し、
前記更新後ファイル符号と前記更新前ファイル符号とを比較し、前記更新後ファイル符号と一致する前記更新前ファイル符号を探索し、
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できた場合は、当該更新前ファイル符号に対応する前記更新前ファイルのデータブロックを構築中ファイルの最後尾に付加し、
前記更新後ファイル符号と一致する前記更新前ファイル符号を発見できなかった場合は、当該更新後ファイル符号に対応する更新後ファイルのデータブロックの送信を前記第１コンピュータへ要求し、前記第１コンピュータから受信した前記更新後ファイルの前記データブロックを前記構築中ファイルの最後尾に付加する、第２コンピュータとからなるファイル構築システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、更新前ファイルをできるだけ利用して、更新後ファイルを構築するファイル構築プログラム、方法及びシステムに関する。
【背景技術】
【０００２】
２つのサーバ間でデータの同期をとるために、一方のサーバから他方のサーバへデータを転送する際にＷＢＸＭＬなどのデータ圧縮が行われている（例えば、非特許文献１参照）。
【非特許文献１】Microsoft Mobile Information Server ActiveSync Edition 製品情報  Ｑ and Ａ、[online][平成１６年２月２０日検索]、インターネット<URL:http://www.microsoft.com/japan/windowsserversystem/miserver/evaluation/QandA.asp>
【発明の開示】
【発明が解決しようとする課題】
【０００３】
近年ＰＤＡ(Personal Digital Assistant)や小型ノートＰＣ等のモバイル端末の普及に伴い、外出先で更新したデータを社内や自宅のＰＣに反映したいというニーズは高い。しかし、据え置き型コンピュータに比べてリソースが貧弱なモバイル端末では、送信側に負担のかかるアルゴリズムを動かすことは難しい。
【０００４】
そこで、本発明は、差分抽出処理をすべて受信側で行うことで送信側に負担をかけないファイル構築プログラム、方法及びシステムを提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の第１の特徴は、ファイル構築プログラムであって、コンピュータに（１）更新前ファイルから更新前ファイル符号を生成する手順、（２）更新後ファイルから生成された更新後ファイル符号のセットを外部から受信する手順、（３）更新後ファイル符号と更新前ファイル符号とを比較し、更新後ファイル符号と一致する更新前ファイル符号を探索する手順、（４）更新後ファイル符号と一致する更新前ファイル符号を発見できた場合は、当該更新前ファイル符号に対応する更新前ファイルのデータブロックを構築中ファイルの最後尾に付加する手順、（５）更新後ファイル符号と一致する更新前ファイル符号を発見できなかった場合は、当該更新後ファイル符号に対応する更新後ファイルのデータブロックの送信を外部へ要求し、外部から受信した更新後ファイルのデータブロックを構築中ファイルの最後尾に付加する手順、を実行させることにある。
【０００６】
本発明の第２の特徴は、（１）更新後ファイル符号セット内に同一の更新後ファイル符号が２以上含まれているかを調べる手順、（２）更新後ファイル符号と一致する更新前ファイル符号を発見できなかった場合に、当該更新後ファイル符号に対応する更新後ファイルのデータブロックを既に受信しているかを調べ、既に受信している場合は当該データブロックを構築中ファイルの最後尾に付加する手順、をさらに含むことにある。
【０００７】
本発明の第３の特徴は、（１）更新後ファイル符号と一致する更新前ファイル符号を発見できなかった場合に、更新前ファイルの全ての開始位置について更新前ファイル符号を生成したかを調べ、全ての開始位置について更新前ファイル符号を生成していない場合は、更新前ファイル符号を生成していない開始位置について、更新前ファイル符号を生成する手順、をさらに含むことにある。
【発明の効果】
【０００８】
本発明の第１の特徴によれば、更新前ファイルと同じ部分については、更新前ファイルを使用して更新後ファイルを構築し、更新前ファイル中に同じ部分を見つけ出せない部分についてのみ、更新後ファイルの送信を要求することによって、ファイル同期のために送受信するデータ量を低減することができる。
【０００９】
本発明の第２の特徴によれば、更新後ファイル符号セット中に同一内容の第１符号と第２符号が存在する場合であって、これら符号は更新前ファイルから生成された符号とは一致しない場合に、第２符号に対応するデータブロックの送信を要求することなく、既に受信している第１符号に対応するデータブロックを再利用することによって、ファイル同期のために送受信するデータ量をより一層低減することができる。
【００１０】
本発明の第３の特徴によれば、更新前ファイルの所定範囲の開始位置について符号を生成し、既に生成された符号中に更新後ファイル符号と一致するものが存在しない場合に、残りの開始位置についても符号を生成することによって、更新前ファイル中の更新後ファイルの構築には必要ではない部分については符号生成を省略することができる。
【発明を実施するための最良の形態】
【００１１】
以下に詳述するよう、本発明の実施例においては、まず送信側において更新後ファイルの符号セットが生成され、この符号セットが更新前ファイルを利用して更新後ファイルを構築する受信側に送信される。そして、受信側では、（１）利用可能な部分に関しては更新前ファイルを利用し、（２）更新前ファイルを利用することができない部分に関しては送信側に当該部分のデータを送信させ、（３）受信側に存在する更新前ファイルの一部と、送信側から送信される更新後ファイルの一部とを組み合わせて、更新後ファイルを構築する。
【実施例１】
【００１２】
図１は、実施例１の送信側装置の外観及び受信側装置の内部構成を示す。図１に示すように、受信側装置３ａは、送受信部１０と、演算処理装置（ＣＰＵ）２０と、記憶部３０とを備える。
【００１３】
送信部１０は、ＵＳＢケーブルなどのケーブルを介して、若しくはインターネット等の通信網を介して、又は赤外線などを用いてワイヤレスに送信側装置１と通信を行う。ＣＰＵ２０は、Detector, Constructorなどの各プロセスに従って更新前ファイルと更新後ファイル符号セットとから更新後ファイルを生成する。また、ＣＰＵ２０は、必要に応じて送信側装置１にデータブロックの送信を要求し、送信側装置１から送信されてきたデータブロックも更新後ファイルの生成に使用する。
【００１４】
記憶部３０は、更新前ファイル、更新前ファイルから生成されるハッシュテーブル、送信側装置１から送信されてくる更新後ファイル符号セット、Detector及びConstructorなどを記憶する。また、更新後ファイル符号セット中のどの符号に注目しているかを記憶する注目符号一時記憶ファイル３６などを有する。また、図示しない、ＢＩＯＳ、オペレーティングシステム（ＯＳ）、更新後ファイル符号セットやデータブロックを受信するための受信プログラム、データブロック送信要求を送信するための送信プログラムなども記憶する。
【００１５】
記憶部３０は、リードオンリーメモリー（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ハードディスクドライブ（ＨＤＤ）などから構成される。また、記憶部３０は、超小型のリムーバブルＨＤＤやフラッシュメモリなどであっても良い。
【００１６】
図２は、実施例１における送信側装置と受信側装置との間で送受信される情報の概要を示す。図２に示すように、更新後ファイルを有する送信側のSender（送信プロセス）から「更新後ファイル符号セット」が受信側へ送られる。受信側のDetector（差分検出プロセス）は、更新されているデータブロックの送信をSenderへ要求する。Detectorは、更新前ファイル中の一致ブロックの位置を、受信側のConstructor（ファイル構築プロセス）へ通知する。Constructorは、更新前ファイル中における一致ブロックと、受信した更新ブロックとから更新後ファイルを構築する。
【００１７】
各プロセスの役割は以下のとおりである。
【００１８】
Sender（送信プロセス）：
同期処理開始時に更新後ファイルから更新後ファイルの符号セットを生成し、この更新後ファイル符号セットをDetectorに送信し、
Detectorから要求があれば、要求されたデータブロックをConstructorに送信する。
【００１９】
Detector（差分検出プロセス）：
Senderから受信したファイル符号セット中の符号と更新前ファイルから生成された符号とのマッチングを順次行い、
符号が一致すれば、その符号に対応する更新前ファイル中の位置をConstructorに通知し、
符号が一致しなければ、その符号に対応するデータブロックの送信をSenderに要求する。
【００２０】
Constructor（ファイル構築プロセス）：
Detectorから一致符号に対応する更新前ファイル中における位置が通知された場合は、更新前ファイルからその符号に対応する部分を切り出して構築中のファイルの最後尾に付加し、
Senderからデータブロックを受信した場合は、そのデータブロックを構築中のファイルの最後尾に付加する。
【００２１】
図３は、実施例１における更新後ファイル、更新後ファイルから生成される符号セット、更新前ファイル、更新前ファイルから生成される符号等の概要を示す。まず、Senderが更新後ファイルを固定長ブロックに区切り、各ブロックをハッシュ関数で符号化して複数の符号を生成し、これら複数の更新後ファイル符号からなる更新後ファイル符号セットを生成し、この更新後ファイル符号セットをDetectorへ送信する。
【００２２】
Detectorは、更新前ファイルのウインドウ内データをハッシュ関数で符号化し、得られた符号をハッシュテーブルに追加し、ウインドウを１バイトずらして再びウインドウ内データをハッシュ関数で符号化し、得られた符号をハッシュテーブルに追加するという処理を繰り返してハッシュテーブルを生成する。
【００２３】
仮に、更新後ファイルが１２０バイト、固定長ブロックのサイズが１０バイトであるなら、更新後ファイルは１２個のブロックに分割される。そして、更新後ファイルセットは、１２個のブロックのそれぞれを符号化して得られた１２個の符号から構成される。
【００２４】
一方、更新前ファイルも１２０バイトだとしても、ハッシュテーブルに蓄積される符号の数は１２個ではない。なぜなら、１バイト目から１０バイト目を符号化して得られた第１符号をハッシュテーブルに追加した後、ウインドウを１バイトずらして２バイト目から１１バイト目を符号化して得られた第２符号をハッシュテーブルに追加し、さらにウインドウを１バイトずらして３バイト目から１２バイト目を符号化して得られた第３符号をハッシュテーブルに追加しという処理が繰り返えされ、全ての開始位置について符号化した場合、約１１０個の符号がハッシュテーブルに蓄積される。なお、固定長ブロックのサイズ、ウインドウのサイズは１０バイトに限定されるものではない。また、ウインドウをずらす単位も必ずしも１バイトでなくても良い。２バイトずつ、または３バイト以上ずつずらすとしても良い。
【００２５】
図４は、実施例１における差分検出プロセス（Detector）による差分検出処理フローを示す。図４に示すように、
ステップＳ３０１で、更新前ファイルの符号をハッシュテーブルへ追加し、
ステップＳ３０５で、符号セットの先頭符号に注目し（つまり、先頭符号を注目符号とし）、
ステップＳ３０７で、注目符号をハッシュテーブル内で探索し、
ステップＳ３０９で、一致した符号が発見できた場合は、
ステップＳ３１１で、一致した更新前符号の更新前ファイル上での位置をConstructorに通知する。
【００２６】
ステップＳ３０９で、一致した符号が発見できない場合は、
ステップＳ３１９で、Senderにデータブロックの送信を要求する。
【００２７】
ステップＳ３２３で、注目符号が符号セットの最後と判断されたら処理を終了し、
ステップＳ３２３で、注目符号が符号セットの最後と判断されなかったら、
ステップＳ３２５で、符号セット中の次の符号を注目符号として、ステップＳ３０７へ戻る。
【００２８】
図５は、更新前ファイルの符号をハッシュテーブルへ追加する処理フローを示す。図５に示すように、
ステップＳ４０１で、ウインドウを符号が未計算の領域の先頭位置に設定し、
ステップＳ４０３で、ウインドウ内のデータをハッシュ関数で符号化し、
ステップＳ４０５で、求めた符号をハッシュテーブルに追加し、
ステップＳ４０７で、ウインドウを１バイトずらし、
という一連の処理を繰り返す。実施例１では、ウインドウが更新前ファイルの最終バイトに到達するまでこれら一連の処理を繰り返すものとする。
【００２９】
図６に示すサンプルデータを用いて差分抽出アルゴリズムをトレースする。あるバイト列（更新前データ）に対して、データの追加、更新、削除の操作を行った各ケースについて同期処理のトレースを行い、本アルゴリズムの効果を検証する。
【００３０】
前提条件は以下のとおりとする。
【００３１】
・データは１６進数で表現する。よって、１６進数が２桁で１バイトを表す。
【００３２】
・ハッシュ関数で符号化するブロックの単位は４バイトとする。
【００３３】
・符号セットの通信量は無視する。ハッシュ値を求める場合に多く用いられるＭＤ４符号化の場合、入力バイト列を数百バイトとすると、十数バイトの符号を作成する。このように符号は、入力バイト列に対して十分小さくなるためここでは符号セットの通信量を考慮しない。
【００３４】
Senderの処理について：
図６（ａ）から（ｅ）に更新前データの一例を示す。また、図６（ｆ）に更新後データの一例を示す。Senderは、４バイト単位で更新後データを符号化し、生成された符号２０１〜２０７から成る符号セットを受信側装置３へ送信する。
【００３５】
図６（ｆ）に示す更新後データは、図６（ａ）に示す更新前データに新たなデータを追加したものである。図６（ｆ）に示す更新後データの
先頭から８バイト目の”6A”、
先頭から９バイト目の”92”、及び
先頭から１０バイト目の”4B”が追加されたデータである。
【００３６】
Detectorの処理について：
Detectorは、符号２０１〜２０７から成る符号セット３３を受信し、記憶部３０に記憶する。また、Detectorは、記憶部３０に記憶されている更新前ファイル３１を４バイト単位で符号化し、生成された符号をハッシュテーブル３２へ追加する。
【００３７】
図６（ａ）に示す更新前データから得られる符号をハッシュテーブルへ追加する処理について説明する。ブロックの単位は４バイトとする。
【００３８】
まず、図６（ａ）に示すように、先頭１バイト目から４バイト目まで、すなわち6F A2 50 83をハッシュ関数で符号化して（Ｓ４０３）、得られた符号１０１をハッシュテーブル３２へ追加し（Ｓ４０５）、ウインドウを１バイトずらし（Ｓ４０７）、
次いで、図６（ｂ）に示すように、先頭２バイト目から５バイト目まで、すなわちA2 50 83 D1をハッシュ関数で符号化して（Ｓ４０３）、得られた符号１０２をハッシュテーブル３２へ追加し（Ｓ４０５）、ウインドウを１バイトずらし（Ｓ４０７）、
さらに、図６（ｃ）に示すように、先頭３バイト目から６バイト目まで、すなわち50 83 D1 BAをハッシュ関数で符号化して（Ｓ４０３）、得られた符号１０３をハッシュテーブル３２へ追加し（Ｓ４０５）、ウインドウを１バイトずらし（Ｓ４０７）、
という処理を繰り返す。
【００３９】
Detectorは、
更新前ファイルの符号をハッシュテーブルへ追加した後（Ｓ３０１）、
符号セット３３の先頭符号２０１に注目し（Ｓ３０５）、
注目符号２０１をハッシュテーブル３２内で探索し（Ｓ３０７）、
注目符号２０１と一致するものとして、更新前ファイル３１の１〜４バイト目に対応する符号１０１を発見し（Ｓ３０９、ＹＥＳ）、
一致した更新前符号１０１の更新前ファイル３１上での位置をConstructorに通知すし（Ｓ３１１）、
注目符号２０１は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２０２に注目する（Ｓ３２５）。
【００４０】
次に、Detectorは、
注目符号２０２をハッシュテーブル３２内で探索するが（Ｓ３０７）、
注目符号２０２に一致する符号を発見できず（Ｓ３０９、ＮＯ）、
Senderに、符号２０２に対応するデータブロック”D1 BA 26 6A”（図６（ｆ））の送信を要求し（Ｓ３１９）、
注目符号２０２は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２０３に注目する（Ｓ３２５）。
【００４１】
次に、Detectorは、
注目符号２０３をハッシュテーブル３２内で探索するが（Ｓ３０７）、
注目符号２０３に一致する符号を発見できず（Ｓ３０９、ＮＯ）、
Senderに、符号２０３に対応するデータブロック”92 4B A3 09”（図６（ｆ））の送信を要求し（Ｓ３１９）、
注目符号２０３は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２０４に注目する（Ｓ３２５）。
【００４２】
次に、Detectorは、
注目符号２０４をハッシュテーブル３２内で探索し（Ｓ３０７）、
注目符号２０４と一致するものとして、更新前ファイル３１の１０〜１３バイト目に対応する符号１１０を発見し（Ｓ３０９、ＹＥＳ）、
一致した更新前符号１１０の更新前ファイル３１上での位置をConstructorに通知し（Ｓ３１１）、
注目符号２０４は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２０５に注目する（Ｓ３２５）。
【００４３】
同様にして、Detectorは、
符号２０５と一致する符号に対応する更新前ファイル３１の１４〜１７バイト目、
符号２０６と一致する符号に対応する更新前ファイル３１の１８〜２１バイト目、
符号２０７と一致する符号に対応する更新前ファイル３１の２２〜２５バイト目
をConstructorに通知し（Ｓ３１１）、
符号２０７が符号セット３３の最後であるから（Ｓ３２３、ＹＥＳ）、処理を終了する。
【００４４】
Constructorの処理について：
Constructorは、
Detectorから更新後ファイルの１〜４バイト目の符号と、更新前ファイルの１〜４バイト目の符号とが一致することを通知されたら、更新前ファイルから１〜４バイト目を切り出して構築中のファイルに付け加え、
Senderから更新後ファイルの５〜８バイト目を受信したら、その受信データを構築中のファイルの最後尾に付け加え、
Senderから更新後ファイルの９〜１２バイト目を受信したら、その受信データを構築中のファイルの最後尾に付け加え、
Detectorから更新後ファイルの１３〜１６バイト目の符号と、更新前ファイルの１０〜１３バイト目の符号とが一致することを通知されたら、更新前ファイルから１０〜１３バイト目を切り出して構築中のファイルの最後尾に付け加え、
Detectorから更新後ファイルの１７〜２０バイト目の符号と、更新前ファイルの１４〜１７バイト目の符号とが一致することを通知されたら、更新前ファイルから１４〜１７バイト目を切り出して構築中のファイルの最後尾に付加し、
Detectorから更新後ファイルの２１〜２４バイト目の符号と、更新前ファイルの１８〜２１バイト目の符号とが一致することを通知されたら、更新前ファイルから１８〜２１バイト目を切り出して構築中のファイルの最後尾に付け加え、
Detectorから更新後ファイルの２５〜２８バイト目の符号と、更新前ファイルの２２〜２５バイト目の符号とが一致することを通知されたら、更新前ファイルから２２〜２５バイト目を切り出して構築中のファイルの最後尾に付け加える、ことによって更新後ファイルを構築する。
【００４５】
実施例１によれば、符号が一致しないためにSenderから送信されるデータブロックは、合計8バイトである。すべてのデータを送信する場合に発生するトラフィックは28バイトであるから、通信量を79％削減できる。
【実施例２】
【００４６】
図７は、実施例２の送信側装置の外観及び受信側装置の内部構成を示す。図７の受信側装置３ｂは、記憶部３０に重複符号一時記憶ファイル３７を記憶するという点で、図１の受信側装置３ａと相違する。
【００４７】
図８は、実施例２におけるDetectorによる差分検出処理フローを示す。図８に示すように、
ステップＳ３０１で、更新前ファイルの符号をハッシュテーブルへ追加し、
ステップＳ３０３で、受信した符号セットの重複をチェックし、
ステップＳ３０５で、符号セットの先頭符号に注目し、
ステップＳ３０７で、注目符号をハッシュテーブル内で探索し、
ステップＳ３０９で、一致した符号が発見できた場合は、
ステップＳ３１１で、一致した更新前符号の更新前ファイル上での位置をConstructorに通知する。
【００４８】
ステップＳ３０９で、一致した符号が発見できず、
ステップＳ３１３で、注目符号と重複した符号が以前あったと判断された場合は、
ステップＳ３１５で、以前受信したデータブロックのうち、どのブロックと一致しているかをConstructorに通知する。
【００４９】
ステップＳ３１３で、注目符号と重複した符号が以前なかったと判断された場合は、
ステップＳ３１９で、Senderにデータブロックの送信を要求する。
【００５０】
ステップＳ３２３で、注目符号が符号セットの最後と判断されたら処理を終了し、
ステップＳ３２３で、注目符号が符号セットの最後と判断されなかったら、
ステップＳ３２５で、符号セット中の次の符号を注目符号として、ステップＳ３０７へ戻る。
【００５１】
図６（ｇ）に示す更新後データは、図６（ａ）に示す更新前データの５〜７バイト目、１９バイト目及び２０バイト目を上書き更新したものである。図６（ｆ）に示す更新後データの
先頭から５バイト目の”6A”、
先頭から６バイト目の”92”、
先頭から７バイト目の”4B”、 
先頭から８バイト目の”4B”、及び
先頭から８バイト目の”A3”が上書きされたデータである。
【００５２】
Detectorの処理について：
Detectorは、
更新前ファイルの符号をハッシュテーブルへ追加し（Ｓ３０１）、
受信した符号セット３３の重複をチェックし（Ｓ３０３）、
符号セット３３の先頭符号２１１に注目し（Ｓ３０５）、
注目符号２１１をハッシュテーブル３２内で探索し（Ｓ３０７）、
注目符号２１１と一致するものとして、更新前ファイル３１の１〜４バイト目に対応する符号１０１を発見し（Ｓ３０９、ＹＥＳ）、
一致した更新前符号１０１の更新前ファイル３１上での位置をConstructorに通知すし（Ｓ３１１）、
注目符号２１１は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２１２に注目する（Ｓ３２５）。
【００５３】
ステップＳ３０３における「受信した符号セット３３の重複をチェック」とは、受信した符号セット内における重複の有無をチェックすることである。例えば、符号２１１〜２１７内における重複の有無を調べた場合、符号２１２と符号２１５とが重複するというチェック結果を、重複符号一時記憶ファイル３７に記憶する。
【００５４】
次に、Detectorは、
注目符号２１２をハッシュテーブル３２内で探索するが（Ｓ３０７）、
注目符号２１２に一致する符号を発見できず（Ｓ３０９、ＮＯ）、
注目符号２１２と重複した符号が、符号２１２より前に存在しないので（Ｓ３１３、ＮＯ）、
Senderに、符号２１２に対応するデータブロック”6A 92 CA 02”（図６（ｇ））の送信を要求し（Ｓ３１９）、
注目符号２１２は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２１３に注目する（Ｓ３２５）。
【００５５】
次に、Detectorは、
注目符号２１３をハッシュテーブル３２内で探索し（Ｓ３０７）、
注目符号２１３と一致するものとして、更新前ファイル３１の９〜１２バイト目に対応する符号１０９を発見し（Ｓ３０９、ＹＥＳ）、
一致した更新前符号１０９の更新前ファイル３１上での位置をConstructorに通知し（Ｓ３１１）、
注目符号２１３は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２１４に注目する（Ｓ３２５）。
【００５６】
同様にして、Detectorは、
符号２１４と一致する符号に対応する更新前ファイル３１内の位置（１３〜１５バイト目）をConstructorに通知し（Ｓ３１１）、
注目符号２１４は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２１５に注目する（Ｓ３２５）。
【００５７】
次に、Detectorは、
注目符号２１５をハッシュテーブル３２内で探索し（Ｓ３０７）、
注目符号２１５に一致する符号を発見できないが（Ｓ３０９、ＮＯ）、
注目符号２１５と重複する符号２１２が、符号２１５より前に存在するので（Ｓ３１３、ＹＥＳ）、
以前受信した符号２１２に対応するデータブロックと一致している旨をConstructorに通知する（Ｓ３１５）。
【００５８】
注目符号２１５と重複する符号を既に受信しているかは、重複符号一時記憶ファイル３７の記憶内容に基づいて判断する。重複符号一時記憶ファイル３７の記憶内容から、符号２１５は符号２１２と一致すると判断される。
【００５９】
注目符号２１５は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２１６に注目する（Ｓ３２５）。
【００６０】
その後Detectorは、
符号２１６と一致する符号として、更新前ファイル３１の２１〜２４バイト目をConstructorに通知し（Ｓ３１１）、
符号２１７と一致する符号を発見できずに、Senderにデータブロックの送信を要求して（Ｓ３１９）、処理を終了する。
【００６１】
Constructorの処理について：
Constructorは、
Detectorから更新後ファイルの１〜４バイト目の符号と、更新前ファイルの１〜４バイト目の符号とが一致することを通知されたら、更新前ファイルから１〜４バイト目を切り出して構築中のファイルに付け加え、
Senderから更新後ファイルの５〜８バイト目を受信したら、その受信データを構築中のファイルの最後尾に付け加え、
Detectorから更新後ファイルの９〜１２バイト目の符号と、更新前ファイルの９〜１２バイト目の符号とが一致することを通知されたら、更新前ファイルから９〜１２バイト目を切り出して構築中のファイルの最後尾に付け加え、
Detectorから更新後ファイルの１３〜１６バイト目の符号と、更新前ファイルの１３〜１６バイト目の符号とが一致することを通知されたら、更新前ファイルから１３〜１６バイト目を切り出して構築中のファイルの最後尾に付け加え、
Detectorから更新後ファイルの１７〜２０バイト目の符号２１５と、更新後ファイルの５〜８バイト目の符号２１２とが一致することを通知されたら、構築中ファイルの５〜８バイト目をコピーし、構築中ファイルの最後尾に貼り付け、
Detectorから更新後ファイルの２１〜２４バイト目の符号と、更新前ファイルの２１〜２４バイト目の符号とが一致することを通知されたら、更新前ファイルから２１〜２４バイト目を切り出して構築中のファイルの最後尾に付け加え、
Detectorから更新後ファイルの２５〜２８バイト目の符号と、更新前ファイルの２５〜２８バイト目の符号とが一致することを通知されたら、更新前ファイルから２５〜２８バイト目を切り出して構築中のファイルの最後尾に付け加える、ことによって更新後ファイルを構築する。
【００６２】
実施例２によれば、符号が一致しないためにSenderから送信されるデータブロックは、合計４バイトである。すべてのデータを送信する場合に発生するトラフィックは２５バイトであるから、通信量は８４％削減できる。
【００６３】
実施例２では、同一内容のデータブロックを複数回、送信要求する必要がないため、通信量のより一層の削減が可能となる。
【実施例３】
【００６４】
図９は、実施例３におけるDetectorによる差分検出処理フローを示す。図９に示すように、
ステップＳ３０１で、更新前ファイルの符号をハッシュテーブルへ追加し、
ステップＳ３０５で、符号セットの先頭符号に注目し、
ステップＳ３０７で、注目符号をハッシュテーブル内で探索し、
ステップＳ３０９で、一致した符号が発見できた場合は、
ステップＳ３１１で、一致した更新前符号の更新前ファイル上での位置をConstructorに通知する。
【００６５】
ステップＳ３０９で、一致した符号が発見できず、
ステップＳ３１７で、更新前ファイルのすべての開始位置における符号がハッシュテーブルに追加済みと判断された場合は、
ステップＳ３１９で、Senderにデータブロックの送信を要求する。
【００６６】
ステップＳ３１７で、更新前ファイルのすべての開始位置における符号がハッシュテーブルに追加済みと判断されなかった場合は、
ステップＳ３２１で、更新前ファイルの符号をハッシュテーブルへ追加し、ステップＳ３０７へ戻る。
【００６７】
ステップＳ３２３で、注目符号が符号セットの最後と判断されたら処理を終了し、
ステップＳ３２３で、注目符号が符号セットの最後と判断されなかったら、
ステップＳ３２５で、符号セット中の次の符号を注目符号として、ステップＳ３０７へ戻る。
【００６８】
図５に示すように、更新前ファイルの符号をハッシュテーブルへ追加する処理は、一定範囲で繰り返される。「一定範囲で繰り返す」とは、ステップＳ４０７においてウインドウを所定バイト数ずらす処理を所定回数繰り返すという意味である。
【００６９】
例えば、ステップＳ３０１において、
更新前ファイルの１〜４バイト目を符号化して、ハッシュテーブルに追加し、
２〜５バイト目を符号化して、ハッシュテーブルに追加し、
３〜６バイト目を符号化して、ハッシュテーブルに追加し、
４〜７バイト目を符号化して、ハッシュテーブルに追加し、
５〜８バイト目を符号化して、ハッシュテーブルに追加してループを終了し、
ステップＳ３２１において、
更新前ファイルの６〜９バイト目を符号化して、ハッシュテーブルに追加し、
７〜１０バイト目を符号化して、ハッシュテーブルに追加し、
８〜１１バイト目を符号化して、ハッシュテーブルに追加し、
９〜１２バイト目を符号化して、ハッシュテーブルに追加し、
１０〜１３バイト目を符号化して、ハッシュテーブルに追加してループを終了する。
【００７０】
なお、ステップＳ３０１においてループを繰り返す回数と、Ｓ３２１においてループを繰り返す回数は、同じでなくても良い。ステップＳ３０１におけるループ繰り返し回数が、ステップＳ３２１におけるループ繰り返し回数より多くても良い。また、ステップＳ３０１におけるループ繰り返し回数が、ステップＳ３２１におけるループ繰り返し回数より少なくても良い。
【００７１】
図６（ｈ）に示す更新後データは、図６（ａ）に示す更新前データの５〜６バイト目及び２３〜２５バイト目を削除したものである。
【００７２】
Detectorの処理について：
更新前ファイルの符号を１０個ずつハッシュテーブルに追加する場合、Detectorは、
更新前ファイルの１〜４バイト目に対応する符号、２〜５バイト目に対応する符号、
３〜６バイト目に対応する符号、４〜７バイト目に対応する符号、
５〜８バイト目に対応する符号、６〜９バイト目に対応する符号、
７〜１０バイト目に対応する符号、８〜１１バイト目に対応する符号、
９〜１２バイト目に対応する符号、１０〜１３バイト目に対応する符号のそれぞれをハッシュテーブルへ追加し（Ｓ３０１）、
符号セット３３の先頭符号２２１に注目し（Ｓ３０５）、
注目符号２２１をハッシュテーブル３２内で探索し（Ｓ３０７）、
注目符号２２１と一致するものとして、更新前ファイル３１の１〜４バイト目に対応する符号１０１を発見し（Ｓ３０９、ＹＥＳ）、
一致した更新前符号１０１の更新前ファイル３１上での位置をConstructorに通知し（Ｓ３１１）、
注目符号２２１は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２２２に注目する（Ｓ３２５）。
【００７３】
次に、Detectorは、
注目符号２２２をハッシュテーブル３２内で探索し（Ｓ３０７）、
注目符号２２２と一致するものとして、更新前ファイル３１の７〜１０バイト目に対応する符号を発見し（Ｓ３０９、ＹＥＳ）、
一致した更新前符号の更新前ファイル３１上での位置をConstructorに通知し（Ｓ３１１）、
注目符号２２２は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２２３に注目する（Ｓ３２５）。
【００７４】
次に、Detectorは、
注目符号２２３をハッシュテーブル３２内で探索するが（Ｓ３０７）、
この時点でのハッシュテーブル内には、注目符号２２３に一致する符号を発見できず（Ｓ３０９、ＮＯ）、
更新前ファイルのすべての開始位置における符号がハッシュテーブルに追加済みではないから（ステップＳ３１７、ＮＯ）、
更新前ファイルの１１〜１４バイト目に対応する符号、１２〜１５バイト目に対応する符号、
１３〜１６バイト目に対応する符号、１４〜１７バイト目に対応する符号、
１５〜１８バイト目に対応する符号、１６〜１９バイト目に対応する符号、
１７〜２０バイト目に対応する符号、１８〜２１バイト目に対応する符号、
１９〜２２バイト目に対応する符号、２０〜２３バイト目に対応する符号のそれぞれをハッシュテーブルに追加し（Ｓ３２１）、
注目符号２２３を新たなハッシュテーブル３２内で探索し（Ｓ３０７）、
注目符号２２３と一致するものとして、更新前ファイル３１の１１〜１４バイト目に対応する符号を発見し（Ｓ３０９、ＹＥＳ）、
一致した更新前符号の更新前ファイル３１上での位置をConstructorに通知し（Ｓ３１１）、
注目符号２２３は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２２４に注目する（Ｓ３２５）。
【００７５】
次に、Detectorは、
注目符号２２４をハッシュテーブル３２内で探索し（Ｓ３０７）、
注目符号２２４と一致するものとして、更新前ファイル３１の１５〜１８バイト目に対応する符号を発見し（Ｓ３０９、ＹＥＳ）、
一致した更新前符号の更新前ファイル３１上での位置をConstructorに通知し（Ｓ３１１）、
注目符号２２４は、符号セット３３の最後ではないので（Ｓ３２３、ＮＯ）、
符号セット３３中の次の符号２２５に注目する（Ｓ３２５）。
【００７６】
次に、Detectorは、
注目符号２２５をハッシュテーブル３２内で探索し（Ｓ３０７）、
注目符号２２５と一致するものとして、更新前ファイル３１の１９〜２２バイト目に対応する符号を発見し（Ｓ３０９、ＹＥＳ）、
一致した更新前符号の更新前ファイル３１上での位置をConstructorに通知し（Ｓ３１１）、
注目符号２２５は、符号セット３３の最後であるから（Ｓ３２３、ＹＥＳ）、処理を終了する。
【００７７】
Constructorの処理について：
Constructorは、
Detectorから更新後ファイルの１〜４バイト目の符号と、更新前ファイルの１〜４バイト目の符号とが一致することを通知されたら、更新前ファイルから１〜４バイト目を切り出して構築中のファイルに付け加え、
Detectorから更新後ファイルの５〜８バイト目の符号と、更新前ファイルの７〜１０バイト目の符号とが一致することを通知されたら、更新前ファイルから７〜１０バイト目を切り出して構築中のファイルの最後尾に付け加え、
Detectorから更新後ファイルの９〜１２バイト目の符号と、更新前ファイルの１１〜１４バイト目の符号とが一致することを通知されたら、更新前ファイルから１１〜１４バイト目を切り出して構築中のファイルの最後尾に付け加え、
Detectorから更新後ファイルの１３〜１６バイト目の符号と、更新前ファイルの１５〜１８バイト目の符号２１２とが一致することを通知されたら、更新後ファイルから１５〜１８バイト目を切り出して構築中のファイルの最後尾に付け加え、
Detectorから更新後ファイルの１７〜２０バイト目の符号と、更新前ファイルの１９〜２２バイト目の符号とが一致することを通知されたら、更新前ファイルから１９〜２２バイト目を切り出して構築中のファイルの最後尾に付け加える、ことによって更新後ファイルを構築する。
【００７８】
実施例３によれば、Senderから送信されるデータブロックは、合計０バイトであるから、全てのデータを送信する場合に比べて、通信量を１００％削減できる。
【００７９】
また、実施例３では、更新前ファイルの２１バイト目以降を開始位置とする符号をハッシュテーブルに追加しなくても良い。つまり、すべての開始位置における符号をハッシュテーブルへ追加しなくても処理が完了する場合がある。
【００８０】
実施例２は、Senderから既に送信されたデータブロックを再利用することによって通信量を削減するものである。また、実施例３は、更新前ファイルのすべての開始位置における符号をハッシュテーブルへ追加しなくても済む場合は、その処理を省略するものである。これら実施例２及び実施例３は、組み合わせても良いことは言うまでもない。つまり、図１０に示すように、
ステップＳ３０１で、更新前ファイルの符号をハッシュテーブルへ追加し、
ステップＳ３０３で、受信した符号セットの重複をチェックし、
ステップＳ３０５で、符号セットの先頭符号に注目し、
ステップＳ３０７で、注目符号をハッシュテーブル内で探索し、
ステップＳ３０９で、一致した符号が発見できた場合は、
ステップＳ３１１で、一致した更新前符号の更新前ファイル上での位置をConstructorに通知し、
ステップＳ３０９で、一致した符号が発見できず、
ステップＳ３１３で、注目符号と重複した符号が以前あったと判断された場合は、
ステップＳ３１５で、以前受信したデータブロックのうち、どのブロックと一致しているかをConstructorに通知し、
ステップＳ３０９で、一致した符号が発見できず、
ステップＳ３１３で、注目符号と重複した符号が以前なかったと判断され、
ステップＳ３１７で、更新前ファイルのすべての開始位置における符号がハッシュテーブルに追加済みと判断された場合は、
ステップＳ３１９で、Senderにデータブロックの送信を要求し、
ステップＳ３１７で、更新前ファイルのすべての開始位置における符号がハッシュテーブルに追加済みと判断されなかった場合は、
ステップＳ３２１で、更新前ファイルの符号をハッシュテーブルへ追加し、ステップＳ３０７へ戻り、
ステップＳ３２３で、注目符号が符号セットの最後と判断されたら処理を終了し、
ステップＳ３２３で、注目符号が符号セットの最後と判断されなかったら、
ステップＳ３２５で、符号セット中の次の符号を注目符号として、ステップＳ３０７へ戻る、としても良い。
【００８１】
実施例では、ハッシュ値の突き合わせを行うためにハッシュテーブルを用いたが、突き合わせを高速に行うためにＢ木（Ｂ-tree）やトライ（Trie：根付き木をベースとしたデータ構造）をハッシュテーブルの代わりに利用することも可能である。
【図面の簡単な説明】
【００８２】
【図１】実施例１の送信側装置の外観及び受信側装置の内部構成を示すブロック図である。
【図２】実施例１における送信側装置と受信側装置との間で送受信される情報の概要を示す図である。
【図３】実施例１における更新後ファイル、更新後ファイルから生成される符号セット、更新前ファイル、更新前ファイルから生成される符号等の概要を示す図である。
【図４】実施例１における差分検出プロセス（Detector）による処理内容を示すフローチャートである。
【図５】更新前ファイルの符号をハッシュテーブルへ追加する処理の内容を示すフローチャートである。
【図６】（ａ）〜（ｅ）は更新前ファイルの一例を示し、（ｆ）〜（ｈ）は更新後ファイルの一例を示す図である。
【図７】実施例２の送信側装置の外観及び受信側装置の内部構成を示すブロック図である。
【図８】実施例２における差分検出プロセス（Detector）による処理内容を示すフローチャートである。
【図９】実施例３における差分検出プロセス（Detector）による処理内容を示すフローチャートである。
【図１０】実施例２及び３における差分検出プロセス（Detector）の組み合わせ例の処理内容を示すフローチャートである。
【符号の説明】
【００８３】
１…送信側装置、  ３…受信側装置、
１０…送信部、  ２０…演算処理装置（ＣＰＵ）、
３０…記憶部、
３１…更新前ファイル、  ３２…ハッシュテーブル、
３３…更新後ファイル符号セット、  ３４…差分検出プロセス（Detector）、
３５…ファイル構築プロセス（Constructor）、３６…注目符号一時記憶ファイル
【図１】
2005251011.tif 000003
【図２】
2005251011.tif 000004
【図３】
2005251011.tif 000005
【図４】
2005251011.tif 000006
【図５】
2005251011.tif 000007
【図６】
2005251011.tif 000008
【図７】
2005251011.tif 000009
【図８】
2005251011.tif 000010
【図９】
2005251011.tif 000011
【図１０】
2005251011.tif 000012