JP4435096B2 - データ送信方法、データ等化方法及び装置 - Google Patents

Description

本発明は、一般的にはコンピュータ通信に関するものであり、特別にはリモートコンピュータに位置するファイルの更新に要する時間を短縮するための方法及び装置に関するものである。

コンピュータ通信技術においては、コンピュータと他の周辺装置との間のデータ通信の速度が大変重要である。携帯用コンピュータの利用が増加している中で、２つのパーソナルコンピュータ間の早くそして正確なデータ転送が特に興味を持たれている。しばしば携帯用コンピュータに入力されたデータが、結局はユーザーの自宅或いはオフィスのパーソナルコンピュータに転送される。コンピュータの専門家は、送信するデータの信頼性を損なわずにデータを転送するために要する時間を短縮する通信プロトコルをいつでも捜し求めている。

コンピュータ、特にパーソナルコンピュータ間でデータを運ぶ従来の方法は、送信側コンピュータのデータバスと受信側コンピュータのデータバスとの相互接続によるものである。これは、各コンピュータのシリアル、パラレル又は同様の通信ポートをケーブルのようなインターフェースリンクを通して、又はモデムを用いるデータパスを介して結合することによって行われる。シリアル通信においては、データは一時に１ビット転送される。シリアル通信は、長い距離を越えてデータを転送する場合、特にモデムを装着し電話線を用いて２つのコンピュータを結んでデータを転送する場合に適している。

しかしながら、シリアル通信を用いてデータを転送するために必要な時間は、特に大きなファイルの場合にはかなりのものになる。比較的近くにある２つの装置間での通信にはパラレル通信がしばしば用いられる。パラレル通信は、データの多数のビット、例えば８ビットがマルチビットデータパスを用いて並列に同時に転送される。

コンピュータソフトウェア会社は、データ転送時間を減らすために更に有効なデータ転送方法を絶えず研究している。中心となる２つの優勢な分野は、データ転送レートを上げること及びデータ圧縮を行って送るべきデータの総量を減らすことである。データ転送レートを上げることは、シリアル通信においてはモデムの速度を上げることによって進められ、パラレル通信においては同時に転送することができるビット数を増すことによって進められて来た。

後者の技術に関する技術の例は本出願人の米国特許第5,261,060 号「８ビットパラレル通信方法及び装置」に記載された技術である。データ圧縮方法は、種々の方法により情報を密にして転送すべきファイルのサイズを小さくする。例えば、通常の圧縮技術の１つはキーワード符号化と呼ばれるもので、例えば「the 」のように頻繁に出て来る語をそれぞれ２バイトのトークン表示に置き換える方法である。圧縮されたデータはリモートコンピュータによって受信された後で圧縮解除され、ファイルの元の内容の表現に戻される。

ファイル転送に要する時間を減らすための最近のアプローチでは、しばしば受信側コンピュータがファイル即ち転送されるべきソースファイルと類似の或いは時には同一のリファレンスファイルを持つようになっている。例えば、ソースファイルが、リファレンスファイルと単に数ワード又は数センテンスだけ変わっているに過ぎないテキストを含むこともある。このアプローチを用いたファイル転送方法は、元の全体のソースファイル又は全体の圧縮されたソースファイルを送ることはせず、２つのファイル間の差異を識別し、その差異のみを受信側コンピュータに送る。これを受信すると、受信側コンピュータにおけるリファレンスファイルがこの差異情報によって更新され、それにより、ソースファイルの正確なコピーが再生される。

本発明は、リモートコンピュータにおいてソースファイルの正確なコピーを作るため、ソースファイルとリファレンスファイルとの間で変更内容を識別し転送する方法の改良を目指すものである。

本発明は、送信側コンピュータに位置するソースファイルと、受信側コンピュータに位置し、このソースファイルを構成するデータと同様のデータを持つリファレンスファイルとの間の差異を識別してこれを分離するファイル転送方法である。両コンピュータはコンピュータデータインターフェースを通して接続される。この方法は、 (a)リファレンスファイルを複数のデータブロックに分割し、各データブロックがｎバイトの長さを持ち、各データブロックをそのブロックにおけるデータによりキーを定めるキー決定方法に従って決定したリファレンスキー値に対応させるステップ、及び (b)ソースファイルからの長さｎバイトのデータのブロックを識別し、該キー決定方法に従ってソースキー値を決定し、且つソースキー値及びリファレンスキー値を用いて、リファレンスファイルからのデータのブロックとソースファイルからのデータのブロックとを比較し、それぞれのファイルからのデータのブロックの間に一致が得られた場合は、受信側コンピュータに一致した旨の表示を送信し、これにより一致した旨を表示されたデータのブロックを受信側コンピュータに送信することを不要にするステップを含む。

本発明の他の観点によれば、データの初期のブロックをソースファイルから識別し、初期のブロックからソースキーを決定し、初期のブロックについて一致が得られない場合は、更に(i) 初期のブロックからの部分集合を受信側コンピュータに送信するステップ、及び(ii)送信された部分集合を除き、ソースファイルからの付加データを加え、ソースファイルからのデータの初期のブロックを含む長さｎバイトの引き続くデータのブロックを識別するステップを含む。

本発明の更に他の観点によれば、リファレンスファイルにおけるデータブロックと対応したリファレンスキー値を送信側コンピュータに送信するステップを更に含む。更に、データのブロックについてのキー値の少なくとも一部分を、そのブロックのバイトと、その値が所定のバイトのそのブロック中における位置に依って決まる１又は複数の乗数とを乗算し、この乗算操作の結果を加算して計算する。

本発明の前記の観点及びこれらに付随する本発明の多くの利点は、図面を用いた以下の詳細な説明によって、更に容易に認識され同時により良い理解が得られる筈である。

実際にリモートファイルを転送する場合、しばしば、受信側コンピュータが既に転送されるべきファイルと類似の、或いは時には同一のファイルを持っている場合がある。例えば、転送されるべきファイルが、テキストファイルをただ数ワード又は数センテンス変更しただけの改訂版であることもある。本発明は２つのファイルの間の差異を識別してこれを分離し、これらの差異のみを受信側コンピュータに転送するファイル転送方法である。類似のファイルについては、このファイル転送方法は、従来のデータ圧縮方法によって得られる圧縮比を遥に上回る圧縮比を得ることができる。

図１は、本発明が利用される典型的な動作環境を説明する図である。送信側コンピュータ20が通信リンク24を通して受信側コンピュータ22と接続される。これらのコンピュータは、パーソナルコンピュータ或いはラップトップコンピュータのような一般的によく知られた型のものである。通信リンクは、例えば本発明の出願人であるTraveling Software社で作られ販売されているファイル転送ツールＬＡＰＬＩＮＫシリーズのような２つのコンピュータ間でデータを転送するための既知の手段であってもよい。

送信側コンピュータ20は一般的にプロセッシングユニット26、メモリー28及び多数の通信ポート30を具える。メモリーはランダムアクセスメモリー（ＲＡＭ）、リードオンリーメモリー（ＲＯＭ）及び外部メモリーを含み、データ／アドレスバス32によってプロセッシングユニット26に接続される。通信ポート30はデータバス34によってプロセッシングユニット26に接続される。通信ポート30はパラレルポート及びシリアルポートを含み、更に、送信側コンピュータがデータの送受信をできるようになるＰＣＭＣＩＡカード技術を含む他の入力／出力技術を含む。受信側コンピュータ22は送信側コンピュータと同様であり、プロセッシングユニット36、メモリー38、通信ポート40及びデータバス44を含む。記載を簡易化するために一方を送信側コンピュータと呼び他方を受信側コンピュータと呼ぶが、コンピュータは一般的に互換性を有する。

データ転送を行うため、送信側及び受信側のコンピュータは、コンピュータプログラム制御を含む。コンピュータプログラムは例えばＲＡＭに格納され、各コンピュータのプロセッシングユニットによって実行される。本発明の１つの実施例においては、送信側及び受信側のコンピュータ制御は、単独のファイル転送プログラム45に組み込まれている。このような方法では、各コンピュータが送信側コンピュータ及び受信側コンピュータとして動作する。ハンドシェイクの必要性から、各コンピュータに位置するファイル転送プログラム45のコピーは同時に実行されることが望ましい。これにより、全二重転送、即ち各方向の同時通信が可能になる。本発明は、効率的ではないにしても半二重通信にも利用できる。

説明を明確にするため、本明細書を通して、送信側コンピュータに位置するソースファイル46が受信側コンピュータ22に送信されるものと仮定する。更に、受信側コンピュータが、ソースファイルと少なくとも若干の類似性を持つリファレンスファイル48を含むものと仮定する。ユーザーがソースファイルを転送することを指示すると、ソースファイルに類似のデータを持つリファレンスファイルが、例えばソースファイルと同一或いは類似のファイル名を持つことによって識別される。本発明は、ここでは一般的にリファレンスファイルは既に識別されたものと仮定する。

ファイル転送プログラムによって実現される基本的なステップは次の通りである。
(1) 受信側コンピュータにおいて、ソースファイルを含むデータと類似のデータを有するリファレンスファイルを識別するステップ、(2) リファレンスファイルを構成するデータを、１ブロック当たりｎバイトを持つように複数のデータブロックに分割し、各データブロックを１つのキー値に対応させるステップ、(3) キー値を受信側コンピュータから送信側コンピュータに送信するステップ、(4) ソースファイルからのデータのｎバイトのカレントブロックを識別し、データのカレントブロックに対応するソースキーの値を計算するステップ、(5) ソースキーの値をそれぞれのリファレンスファイルからのキー値と比較し、一致が得られると、 (i)一致した旨の通知を受信側コンピュータに送信し、(ii)ステップ(4) を繰り返すステップ、及び(6) 一致が得られないと、データのカレントブロックからデータの１バイトを受信側コンピュータに送信し、ソースファイルからのデータの付加バイトをデータのカレントブロックに付加し、ソースキー値を再計算し、ステップ (5)を繰り返すステップ。

一般的に、ステップ(5) 及び(6) によって作られるループは、ソースファイルの全てのデータが処理されるまで繰り返される。受信側コンピュータにおいては、一致の通知及びバイトの送信からデスティネーションファイルが作られる。送信が完結すると、このデスティネーションファイルはソースファイルの写しになる。

図２は、ステップ(2) を説明する図であり、リファレンスファイルを構成するデータを複数のデータブロック50ａ、50ｂ、50ｃ、．．．50ｙ、50ｚに分割し、各データブロックをキー値52ａ、52ｂ、52ｃ、．．．52ｙ、52ｚに対応させる。データの最後のブロックはｎバイトより少ないこともあり得るので、図ではｘバイトと表示している。

リファレンスファイルがデータブロック50に分割されると、各ブロックのキー値52は種々の方法で計算される。第１の実施例では、各キーがそのブロックのデータの各バイトの値を加算し、そのブロックの全てのバイトの総計を出すことによって計算される。ちなみに、それぞれの所定のブロックにおける各８ビットのキャラクタは、０乃至２５５即ち２⁸ −１の範囲にあるＡＳＣＩＩ値で表現されている。

ＡＳＣＩＩは情報交換のための米国の標準コードの頭文字からできた語である。ＡＳＣＩＩのコード構成は、文字、数字、記号及び他のキャラクタに数値を割当てるものである。このようなキャラクタについて用いられる値の標準化を通して、ＡＳＣＩＩはコンピュータ及びコンピュータプログラムを用いて情報交換を行うことを可能にした。前記のようなキーの計算は、それぞれの所定のブロックに含まれるデータを表す０とｎ² との間の全ての数を生成する。

リファレンスファイル中のデータの各ブロックについてのキーが計算されると、そのキー値は１つのアレイとして、ソースファイルとの比較のために送信側コンピュータに送られる。

図３は、ステップ(3) 乃至(5) を説明する図である。ステップ(3) においては、ソースファイルからのデータのｎバイトのカレントブロックが識別され、データのカレントブロックに対応するソースキーについての値が計算される。このように、最初の比較においては、バイト０からバイトｎ−１までがデータのカレントブロックとして識別される。従って、データのカレントブロックのキー値は、リファレンスファイルのキーを計算するのに用いられた方法と同一の方法を用いて計算される。データのカレントブロックのキー値はKEY1とする。

ステップ(4) においては、KEY1の値がリファレンスファイルのそれぞれのキーと比較され、一致するか否かが決定され、それによりデータのカレントブロックがリファレンスファイルのデータの１つのブロックと同一であるか否かが表示される。一致が得られたならば、この表示は受信側コンピュータに送られる。一致が得られないと、ステップ(5) によってカレントブロックの第１のバイト（バイト０）が受信側コンピュータに送られる。

データのカレントブロックの続きは、次にカレントブロックからデータの第１のバイト（バイト０）を差引いて数値化され、データの次に続くバイト（バイトｎ）がカレントブロックに加えられ、次のカレントブロックのキー値が再計算される。データのこのブロックについてのキー値をKEY2とする。このように、KEY2はバイト１乃至ｎの値を含む。KEY2の値は次にリファレンスファイルについてのキーアレイのそれぞれのキーと比較される。

一致が得られない場合は、カレントブロックの第１バイト（バイト１）が受信側コンピュータに送られる。次に、データのカレントブロックを表す第３のキーであるKEY3が、データのカレントブロックを右に１バイトずらすことによって計算され、KEY3はバイト２からバイト（ｎ＋１）までの値を含む。これは、ソースファイルにおけるデータブロックから計算されたキー値とリファレンスファイルについてのキーアレイにおけるキーとの間に一致が得られるか、又はソースファイル中の全てのデータが送信されてしまうまで続けられる。一致が得られると、その旨の通知が受信側コンピュータに送られ、次のデータのカレントブロックがソースファイルから計算される。

一致が得られない場合においてファイルを転送するために必要な付加的な時間は、ウィンドウをずらせ、キーを計算するにも拘わらず、従来の方法に較べて無視できる。これは、部分的にはプロセッサがデータを送るよりもずっと早く計算することができるという事実による。更に、好適な実施例においては、受信側コンピュータは、受信されるバイトがデータバイトであり、２つのデータブロック間の一致の表示ではないことを期待するように構成される。後者の場合、一致が生じたことを示す付加的な「一致の表示」のバイトが複数のバイトの先頭に送られる。このように、一致が得られない場合に送られるバイトの数は、一般的には本発明による一致のチェックを行わずに単に送信するときとほぼ等しくなる。

前記の説明はファイル転送プログラム45の実施例の概観である。ソフトウェアによるファイル転送プログラムを実行するためのルーチンの実施例が図４乃至６に示されている。図４は、リファレンスファイルの内容からキーアレイを計算するためのルーチンのフローチャートである。データの各ブロックのサイズが手順100 でセットされる。一例では、各ブロックが２５６バイトを含む。

手順102 では、このルーチンで処理されるデータのカレントブロックを表示する変数nBLOCKが０にセットされる。データのカレントブロックについてのキー値が手順104 で計算される。キー値を計算するのに適したルーチンを図５に示す。手順106 では、アレイBLOCKKEY[nBLOCK]がカレントブロックについて計算されたキー値と等しくされる。変数「nBLOCK」は次に手順108 で増やされる。

手順110 では、リファレンスファイルの終りに達したか否かを決定するためのテストが行われる。まだファイルの終りに達していない場合は、ルーチンは手順104 に戻る。ファイルの終りに達している場合は、手順112 でアレイBLOCKKEYが送信側コンピュータに送られ、このルーチンが終了する。

図５は、図４（手順104 ）でデータの所定のブロックに対応するキー値を計算するために用いるのに適した第１の実施例てあるサブルーチンのフローチャートを示す。このサブルーチンは、リファレンスファイルにおける各データブロックについて呼び出される。

手順120 で、バイト計数値を表す変数「ｎ」が０にセットされる。手順122 では、変数「KEY 」が０にセットされる。手順124 では、リファレンスファイルからデータの１バイトが読み取られる。手順126 では変数「ｎ」が増やされる。手順128 では、変数「KEY 」が、前の値に手順124 で読み取られたデータのカレントバイトの値を加えた値に等しくされる。

手順130 では、リファレンスファイルの終りに達したか否かを決定するためのテストが行われる。まだファイルの終りに達していない場合は、手順132 で、データの全てのブロックが処理されたか否か、即ちｎがブロックサイズに等しいか否かを決定するためのテストが行われる。ｎがブロックサイズに等しくない場合は、サブルーチンは手順124 に戻る。ｎがブロックサイズに等しい場合又は手順130 でファイルの終りに達したと決定された場合は、このサブルーチンは終了し、図４のルーチンに復帰する。

図６は、ソースファイルからのｎバイトブロックに対応するキーと、リファレンスファイルから計算されたキー及びアレイBLOCKKEYに含まれたキーとの比較を行うためのルーチンのフローチャートである。手順150 では変数「CURRENTKEY」が０にセットされる。手順152 では、少なくともｎバイトのまだ比較されていないソースファイルのデータがあるか否かを決定するテストが行われる。少なくともｎバイトのまだ比較されていないソースファイルのデータがある場合は、手順154 でソースファイルからデータのｎバイトブロックが読み取られる。

手順156 では、データのカレントブロックを表示するカレントキー値が、図５で用いられた方法と同じ方法、即ちデータのカレントブロックの各バイトの重み付けされた値を加算する方法を用いて計算される。次に手順158 で、アレイBLOCKKEYにおけるキー値のいずれかがカレントキーに一致するか否かを決定するためにアレイBLOCKKEYがサーチされる。一致が得られたか否かのテストは手順160 で行われる。

手順160 で一致が得られた場合は、手順162 で受信側コンピュータにメッセージが送られ、一致したブロックがデスティネーションファイルに送信される。このルーチンは手順154 に戻る。一致が得られない場合は、手順164 で、カレントブロックのデータの第１バイトが受信側コンピュータに送られる。手順166 では、受信側コンピュータに送られたデータのバイトがデータのカレントブロックから削除される。

手順168 では、ソースファイルにまだ処理されていない残りのデータがあるか否かを決定するテストが行われる。ソースファイルに残りのデータがある場合は、手順170 でデータの新しいバイトがソースファイルから読み取られ、手順172でデータのカレントブロックに加えられる。このルーチンは手順156 に戻り、データのカレントブロックについてのキーが計算される。

手順172 から戻った後で手順156 においてカレントキーを計算する際、カレントブロックのそれぞれのキャラクタを加算することによってキー計算を行うよりは、（手順166 において）カレントブロックから削除されたバイトの値を前に計算されたカレントキーから減算し、次に（手順172 において）カレントブロックに加算されたバイトの値を加算することによってカレントブロックについてのキー値を得るのがより効率的であることは明らかである。

ソースファイルに残っている全てのデータが処理されると、又は手順152 のテストの結果ソースファイルの残りのデータがｎバイトより少なくなると、手順174 で、ソースファイルの残りのデータが受信側コンピュータに送られる。受信側コンピュータにおいては、送信されたデータがデスティネーションファイルに加えられ、ファイル転送が完了する。

他の実施例においては、手順174 に示されるように、単に残りのデータを送るのではなく、残りのデータのキー値がリファレンスファイルのデータの最後のブロックのキー値と一致するか否かのテストが行われる。一致が存在すると、一致の表示が受信側コンピュータに送られ、データ自身の送信は不要とされる。そうでない場合は、実際のデータが送信される。これは、リファレンスファイルの終り部分がソースファイルの終り部分と同一のデータを含む場合に、転送を更に有利にする。

ソースファイルの全てのデータがデスティネーションファイルに加えられると、即ち手順162 、164 及び174 によって殆どの場合にデスティネーションファイルがソースファイルの完全なコピーになる。しかしながら、デスティネーションファイルがソースファイルの正確な複製であることを確認するためのチェックが行われることが望ましい。手順176 では、デスティネーションファイルの完全性が、既知の手段を用いてチェックされる。

このファイルの完全性をチェックする１つの方法は、M. Nelson 著「データ圧縮ブック」（The Data Compression Book ）の446-448 頁（Ｍ＆Ｔ Books 1991）に記載されたようなサイクリック冗長検査（ＣＲＣ）である。デスティネーションファイルの完全性が得られない場合は、通常の送信方法を用いて、ソースファイルからデスティネーションファイルへデータが再送信される。これは、手順178 に示されている。デスティネーションファイルについて又はソースファイルの送信について完全性が得られた場合はこのルーチンが完了する。

デスティネーションファイルがソースファイルの正確なコピーではない場合の１つの例は、データの２以上の異なるブロックが同一のキー値を生ずる場合である。データの各ブロックが２５６バイトと仮定すると、図５に示したキー計算方法では、可能なキー値の範囲は０から65,280までである。この後者の値は、ブロックの各バイトが数値２５５をとった場合にのみに起きる。

この場合、 (1)可能なキー値の範囲が比較的大きく、及び／又は (2)キー計算値がこの範囲の広い部分に分布する可能性が増すと、同じキー値を持つ確率が減少する。この点については、データを送信するための本発明によるデータファイル転送方法の正確性は、２つの異なるデータのブロックが同一のキー値を持つ確率が極めて小さい場合に最も効果的に動作する。

有利なキー値計算方法の他の望ましい例は、ソースデータのブロックについてのカレントキー値がウィンドウをずらすことによって導出され、素早く確定される場合である。これを達成する１つの方法は、差し引かれるべきデータのバイトに対応するキー値をデータのカレントブロックから減算し（手順166 ）、加えられるべきデータのバイトに対応するキー値をカレントブロックに加算する（手順172 ）ことによって、カレントキー値が更新されるキー計算方法を持つことである。

図５に示されたキー計算方法はここに説明した例であるが、この例は可能なキー値の範囲が限定されており、この範囲に値が分布するようになっているため、ずっと大きなファイルについては良好に動作しない。

図７乃至９は、本発明によるキー計算のための第２の実施例を説明する図であり、可能なキー値の範囲が図５の場合より拡張され、これにより、どのキー値もデータの１つのブロック以外のブロックを表示する可能性を減らした例である。更に、この計算方法においては、図９で説明するようにカレントキーが極めて高速で更新される。図７乃至９の例は、３２ビットキーを示しているが、他のキーサイズであってもよいことは勿論である。

図７によれば、３２ビットキーが下部２４ビットのセグメントと上部８ビットのセグメントとに分割されている。２４ビットのセグメントは、式 Ｃ₁(n)＋Ｃ₂(n-1)＋Ｃ₃(n-2)＋……＋Ｃ_n-1(2)＋Ｃ_n （１）
によって計算される。ここでＣ₁ はカレントブロックのｉ番目のキャラクタであり、ｎは各ブロックのバイト数である。３２ビットキーの上部８ビットは、各キャラクタについてエクスクルーシブオア（ＸＯＲ）操作を行うことによって計算される。これは、式 Ｃ₁ ＸＯＲ Ｃ₂ ＸＯＲ Ｃ₃ ……Ｃ_n-1 ＸＯＲ Ｃ_n （２）
によって示される。

下部及び上部のキー値が計算されると、このビットが結合され、それぞれ３２ビットキーを形成する。図８には、図７で説明されたキー計算を実行するために適したサブルーチンを示す。このサブルーチンは図４R>４のルーチンで図５のサブルーチンを呼ぶ代わりに呼び出される。

手順200 では、いずれのブロックについてもバイト計数を表示する変数「ｎ」が０にセットされる。手順202 では、キーの下部分及び上部分、即ちKEY24 及びKEY8が０にセットされる。手順204 では変数「SUM 」が０にセットされる。手順206 ではデータの１バイトがリファレンスファイルから読み取られる。

手順208 ではカレントバイトの値が変数SUM に加えられる。次に手順210 で変数KEY24 がSUM の値だけ増される。手順208 及び210 は、乗算操作を除いて計算式（１）の変形方法であることは明らかである。手順212 では、変数KEY8がKEY8の前の値とカレントバイトとでＸＯＲ操作を行った値に等しくされる。

手順214 ではリファレンスファイルの終りに到達したか否かを決定するテストが行われる。まだリファレンスファイルの終りに到達していない場合は、手順216 でｎがブロックサイズに等しいか否かを決定するテストが行われる。ｎがブロックサイズに等しくない場合は、このルーチンは手順206 に戻る。ｎがブロックサイズに等しい場合又はファイルの終りに到達した場合は、手順210 で計算された下部２４ビット値（KEY24 ）と手順212 で計算された上部８ビット値（KEY8）とが結合されて変数「KEY 」がセットされる。このサブルーチンはここで完了し、プログラムは図４の手順106 に復帰する。

図９には、データのカレントブロックについてのカレントキー値を計算するために図６の手順156 から呼び出されるのに適したサブルーチンが示されている。このサブルーチンは、ウィンドウをずらすことによって識別され、従って既に計算されたキーに類似のキー値を持つソースデータのブロックについてのキー計算の最適化を示すものである。

手順220 では、カレントブロックがウィンドウをずらす方法によって識別されたか否か、即ち前のブロックとの一致が得られなかったためにこのサブルーチンが呼び出されたか否かを決定するテストが行われる。データのカレントブロックがこの方法によって識別されたのではない場合は、カレントキー値を計算するために図８のサブルーチンが呼び出される。これはソースファイルのデータの第１ブロックで又は一致が得られた後で起きる。

データのカレントブロックが前の一致しないデータのブロックに基づいて識別された場合は、前のブロックからの第１バイト（手順166 の操作で削除されたバイト）が、手順224 でSUM から減算される。手順226 では、KEY24 が、削除されたバイトの値とブロックサイズとの積を前の値から減じた値に等しくセットされる。手順228 では、新しいバイト（手順172 でカレントブロックに加えられたもの）がSUM に加算される。次に手順230 で変数KEY24 がSUM の値だけ増やされる。

手順232 では、変数KEY8がKEY8の前の値と削除されたバイトとのＸＯＲの値に等しくセットされる。次に手順234 でKEY8と新しいバイトとの間でエクスクルーシブオア操作が行われる。手順236 では、手順230 で計算された下部２４ビット値（KEY24 ）と手順234 で計算された上部８ビット値（KEY8 ）とが結合されて変数「KEY 」がセットされる。次にこのサブルーチンが完了し、制御は図６の手順158 に復帰する。上記のように、図９のサブルーチンによればキー値を高速で計算でき、従って、ソースファイルからのブロックとリファレンスファイルからのブロックとの間の一致を捜す際に、ファイル転送プログラムがより高速で動作することができる。

当業者にとって明らかなように、本発明においては、数多くの異なったキー計算方法を用いることができる。従って、本発明はここで説明されたキー計算の例に限定されるものではない。不必要に時間を浪費せず、比較的広い範囲の結果を提供する方法ならば、どのようなキー計算であっても有益であり得る。更に、それぞれの実施例で用いられたキー計算の型においては、最適の結果を得るためにはブロックサイズに依存することもある。

利用することができる他のキー計算は、ブロック中の各キャラクタとそのブロック中における位置との積を計算してこれを総計した値を用いるである。実行できる他のキー計算は、前記のＣＲＣファイル完全性チェックである。この方法は極めて正確であるが、多くの用途においてかなり遅いことがある。

再度図６に言及すれば、アレイBLOCKKEYがサーチされるとき（手順158 ）にバイナリーサーチを用いると更に高度の最適化が達成される。バイナリーサーチはサーチの１つの型であり、順序付けされたリストの中に存在する筈のアイテムをサーチする場合、その順序付けされたリストを繰り返し２つの等しい部分に分割し、そのアイテムが含まれるであろう半分をサーチする方法である。バイナリーサーチでは、例えば昇順のように既知の順序になっているサーチリストが必要であるため、アレイBLOCKKEYはサーチが実行できるような順序に従って配置されることが必要である。適切で標準的なバイナリーサーチは、H. Schildt著「完全性（リファレンス）」（The Complete(Reference) ）の487-488 頁（Osborn McGraw-Hill,1987 ）に記載されている。

本発明の好ましい実施例が記載され説明されたが、本発明の精神及び範囲を逸脱せずに種々の変更が可能であることは明らかである。

本発明によりファイルを更新するために用いられるファイル転送プログラムが走る送信側コンピュータ及び受信側コンピュータを含む通信網のブロック図である。 リファレンスファイルのデータのブロックに対応する複数のキーを用いて送信されるべきソースファイルと類似性を有するリファレンスファイルを表すブロック図である。 ウィンドウをずらす方法によってソースファイルのデータのブロックを選択する方法を説明するブロック図である。 本発明によるファイル転送プログラムを実行するルーチンの例のフローチャートである。 リファレンスファイルのデータの各ブロックについてのキー値を定めるサブルーチンの第１の例のフローチャートである。 ソースファイルとリファレンスファイルとの差異を決定しこの差異を受信側コンピュータに送信しこれによりデスティネーションファイルを作成する本発明の方法に用いるルーチンの例のフローチャートである。 リファレンスファイルのデータの各ブロックについてのキー値を定める第２の例を説明する図である。 図７に示されたキー値を定める方法を実行するサブルーチンのフローチャートである。 ソースファイルのデータのカレントブロックに対応するキー値を決定するサブルーチンのフローチャートである。

符号の説明

２０ 送信側コンピュータ
２２ 受信側コンピュータ
２４ 通信リンク
２６、３６ プロセッシングユニット
２８、３８ メモリー
３０、４０ 通信ポート
３２、４２ データ／アドレスバス
３４、４４ データバス
４５ ファイル転送プログラム
４６ ソースファイル
４８ リファレンスファイル
５０ データブロック
５２ キー値
１００〜２３６ フローチャートの手順

Claims (15)

1. 送信側コンピュータに位置するソースファイルからデータを受信側コンピュータに送信する方法であって、前記送信側コンピュータと前記受信側コンピュータとはコンピュータデータインタフェースを介して接続される方法において、
   （ａ）前記受信側コンピュータにおいて、前記受信側コンピュータに位置するリファレンスファイルを各々がｎバイト長を有する複数のデータブロックに分割し、各々のデータブロックに、そのブロックにおけるデータによりキー規定方法にしたがって決定されるリファレンスキー値を関係付けるステップと、
   （ｂ）前記リファレンスキー値を前記受信側コンピュータから前記送信側コンピュータに送信するステップと、
   (ｃ)前記送信側コンピュータにおいて、前記ソースファイルからのｎバイト長の第１のデータブロックを識別し、前記キー規定方法によって前記第１のデータブロックのソースキー値を決定し、前記ソースキー値及び前記リファレンスキー値を使用して前記リファレンスファイルからの前記複数のデータブロックのそれぞれと前記ソースファイルからの第１のデータブロックとを比較するステップと、
   （ｄ）前記ステップ（ｃ）において各々のファイルからの前記データブロック間で一致が見つかった場合、この一致の表示を前記送信側コンピュータから前記受信側コンピュータに送信し、前記一致によって示された前記データブロックが前記受信側コンピュータに送信される必要がないようにするステップと、
   （ｅ）前記ステップ（ｃ）において各々のファイルからの前記データブロック間で一致が見つからなかった場合、前記送信側コンピュータにおいて、前記第１のデータブロックのうちのｎバイトよりも少ないバイト数のデータを前記受信側コンピュータへ送信し、送信された前記データを除き且つｎバイトの第２のデータブロックのソースキー値を計算し、この第２のデータブロックのソースキー値と前記リファレンスキー値を使用して前記リファレンスファイルからのデータブロックと前記ソースファイルからの第２のデータブロックとを比較するステップと、
   （f）前記受信側コンピュータにおけるデータが前記ソースファイルと同じになるまで、前記ソースファイルの残りのデータブロックに関してステップ（ｃ）、（ｄ）及び（ｅ）を繰り返すステップと
   を含むことを特徴とする方法。
2. 請求項１に記載の方法において、データブロックに関する前記キー値の少なくとも一部は、前記ブロックにおけるデータの各々のバイトの値を加算し、前記ブロックにおけるすべてのバイトの合計を発生することによって計算されることを特徴とする方法。
3. 請求項１に記載の方法において、データブロックに関する前記キー値の少なくとも一部は、前記ブロックにおけるバイトに1つ又はそれ以上の乗数を乗算し、前記乗算の結果を合計することによって計算され、前記乗数の値は、前記ブロックにおける所定のバイトの位置に依存することを特徴とする方法。
4. 請求項１に記載の方法において、前記リファレンスファイルにおけるデータの各々のバイトは、1つより多くないリファレンスキーの決定において使用され、前記ソースファイルにおけるデータのバイトの少なくともいくつかは、複数のソースキーの決定において使用されることを特徴とする方法。
5. 受信ユニットにおけるリファレンスデータを、ソースユニットにおけるソースデータと同じになるまで変更する方法において、
   （ａ）前記受信ユニットにおいて、前記受信ユニットに格納された前記リファレンスデータのグループに対応する複数のリファレンスキーを決定するステップと、
   (ｂ)前記複数のリファレンスキーを前記受信ユニットから前記ソースユニットに送信するステップと、
   (ｃ)前記ソースユニットにおいて、前記ソースユニットにおける前記ソースデータの第１のグループに対応するソースキーを決定するステップと、
   （ｄ）前記ソースユニットにおいて、前記ソースキーを前記複数のリファレンスキーと比較するステップと、
   (ｅ)ステップ（ｄ）において前記ソースキーが前記リファレンスキーのうちの１つと一致する場合、前記ソースユニットから一致の表示を前記受信ユニットに送信するステップであって、前記一致の表示は、前記受信ユニットに、前記一致したリファレンスキーに対応する前記受信ユニットにおけるデータを使用させるステップと、
   （ｆ）ステップ（ｄ）において前記ソースキーが前記リファレンスキーのいずれとも一致しない場合、前記ソースユニットにおいて、前記第１のグループのうちの一部のデータを前記受信ユニットへ送信し、送信された前記一部のデータを除き且つ前記第１のグループと同じ長さの第２のグループのソースキーを計算し、この第２のグループのソースキーと前記複数のリファレンスキーとを使用して前記リファレンスデータからのデータのグループと前記ソースファイルからの第２のグループとを比較するステップと、
   （ｇ）前記受信ユニットにおけるデータが前記ソースデータと同じになるまで、前記ソースデータの残りのグループに関してステップ（ｃ）、（ｄ）、（ｅ）及び（ｆ）を繰り返すステップと
   を含むことを特徴とする方法。
6. 請求項５に記載の方法において、前記受信ユニットにおけるデータの各々のバイトは、１つより多くないリファレンスキーの決定に使用され、前記ソースデータの少なくともいくつかのバイトは、複数のソースキーの決定に使用されることを特徴とする方法。
7. 受信ユニットにおけるデータを、前記受信ユニットにおけるデータがソースユニットにおけるソースデータと同じになるまで変更するのに使用する装置であって、
   前記受信ユニットに格納されたデータのグループに対応する複数のリファレンスキーを決定するリファレンスキー決定手段と、
   前記複数のリファレンスキーを前記ソースユニットに送信するデータ送信手段と、
   前記ソースユニットにおけるソースデータの第１のグループに対応するソースキーを決定するソースキー決定手段と、
   前記ソースキーを前記複数のリファレンスキーと比較するキー比較手段と、
   前記ソースキーが或るリファレンスキーと一致する場合、一致の表示を前記ソースユニットから前記受信ユニットに送信する手段であって、前記一致の表示は、前記受信ユニットに、前記一致するリファレンスキーに対応する前記受信ユニットにおけるデータのグループを使用させる表示送信手段と、
   前記ソースキーが前記リファレンスキーのいずれとも一致しない場合、前記受信ユニットに前記第１のグループのうちの一部のデータを送信するデータ送信手段と、
   を具備し、
   前記ソースキーが前記リファレンスキーのいずれとも一致しない前記の場合、前記ソースキー決定手段が、送信された前記一部のデータを除き且つ前記第１のグループと同じ長さの第２のグループのソースキー値を計算し、前記キー比較手段が前記第２のグループのソースキーを前記複数のリファレンスキーと比較することを特徴とする装置。
8. 請求項７に記載の装置において、前記ソースキー決定手段は、すでに決定されていたソースキーの比較を前記キー比較手段が行った後に、前記ソースデータのグループから新たなソースキーを決定し、その構成は、前記ソースキーが前記リファレンスキーと一致したかどうかによって決定されることを特徴とする装置。
9. 送信側コンピュータにおけるソースファイルと同じ複製ファイルを受信側コンピュータにおいて形成する方法であって、前記複製ファイルは、前記受信側コンピュータに位置するリファレンスファイルにおけるデータと前記送信側コンピュータから送信されたソースファイルにおけるデータとから部分的に形成され、前記受信側コンピュータと前記送信側コンピュータとはコンピュータデータインタフェースを介して接続される方法において、
   （ａ）前記受信側コンピュータにおいて、前記リファレンスファイルを一様な長さの複数のデータブロックに分割し、それぞれの前記データブロックを、キー規定方法にしたがって、それぞれの前記データブロックにおけるデータによって決定されるリファレンスキー値と関連付けるステップと、
   （ｂ）前記送信側コンピュータにおいて、前記ソースファイルからの前記一様な長さの第１のデータブロックを識別し、前記キー規定方法にしたがって、前記第１のデータブロックのソースキー値を決定し、前記ソースキー値及び前記リファレンスキー値を使用して、前記リファレンスファイルからのデータブロックと前記ソースファイルからの第１のデータブロックとを比較するステップと、
   （ｃ）前記比較の結果、前記リファレンスファイルと前記ソースファイルとのデータブロック間に一致が見つかった場合、この一致の表示を前記送信側コンピュータから前記受信側コンピュータに送信し、前記一致によって示されたデータブロックが前記受信側コンピュータに送信される必要がないように、前記受信側コンピュータにおいて前記リファレンスファイルからのデータのブロックを前記複製ファイルに複製するステップと、
   （ｄ）前記比較の結果、前記リファレンスファイルと前記ソースファイルとのデータブロック間に一致が見つからない場合、前記第１のデータブロックのうちの一部のデータを前記送信側コンピュータから前記受信側コンピュータへ送信して、前記受信側コンピュータに、前記の送信された一部のデータを前記複製ファイルに追加させ、送信された前記一部のデータを除き且つ前記第１のデータブロックと同じ長さの第２のデータブロックのソースキー値を計算し、この第２のデータブロックのソースキー値と前記リファレンスキー値を使用して前記リファレンスファイルからのデータブロックと前記ソースファイルからの第２のデータブロックとを比較するステップと、
   （ｅ）前記受信側コンピュータにおけるデータが前記ソースファイルと同じになるまで、前記ソースファイルの残りのデータブロックに関してステップ（ｂ）、（ｃ）及び（ｄ）を繰り返すステップと
   を具備する方法。
10. 受信ユニットにおけるデータを、前記受信ユニットにおけるデータがソースユニットにおけるソースデータと同じになるように変更するための装置において、
    ｎバイトの一様な長さを有し前記受信ユニットに格納されたデータグループに対応する長さを有する複数のリファレンスキーを、キー規定方法を使用して決定するリファレンスキー決定手段と、
    前記複数のリファレンスキーを前記ソースユニットに送信するデータ送信手段と、
    前記ソースユニットにおけるソースデータのｎバイトの一様な長さの第１のデータグループに対応するソースキーを、前記キー規定方法を使用して決定するソースキー決定手段と、
    前記ソースキーを前記複数のリファレンスキーと比較するキー比較手段と、
    前記ソースキーが前記リファレンスキーのうちの１つと一致する場合、一致の表示を前記ソースユニットから前記受信ユニットに送信する手段であって、前記一致の表示は、前記受信ユニットに、前記一致したリファレンスキーに対応する前記受信ユニットにおけるデータグループを使用させる表示比較手段と、
    前記ソースキーが前記複数のリファレンスキーのいずれとも一致しない場合、前記第１のデータグループのうちの一部のデータを前記受信ユニットへ送信するデータ送信手段と、
    を具備し、
    前記ソースキーが前記複数のリファレンスキーのいずれとも一致しない前記の場合、前記ソースキー決定手段が、送信された一部のデータを除き且つ前記第１のデータグループと同じ長さの第２のデータグループのソースキーを計算し、前記キー比較手段が、前記第２のデータグループのソースキーを前記複数のリファレンスキーと比較することを特徴とする装置。
11. 受信側コンピュータにおいて、送信側コンピュータにおけるソースファイルと同じ複製ファイルを形成する方法であって、前記複製ファイルは、前記受信側コンピュータに位置するリファレンスファイルにおけるデータと前記送信側コンピュータから送信された前記ソースファイルにおけるデータとから部分的に形成され、前記受信者コンピュータと前記送信側コンピュータとはコンピュータデータインタフェースを介して接続される方法において、
    （ａ）前記受信側コンピュータにおいて、前記ソースファイルを構成するデータと同じデータを有するかもしれないリファレンスファイルを識別するステップと、
    （ｂ）前記受信側コンピュータにおいて、前記リファレンスファイルを構成するデータを、それぞれがｎバイトを有する複数のデータブロックに分割し、各々のデータブロックを、キー規定方法によって決定されるリファレンスキー値と関係付けるステップと、
    （ｃ）前記リファレンスキー値を前記受信側コンピュータから前記送信側コンピュータに送信するステップと、
    （ｄ）前記送信側コンピュータにおいて、前記ソースファイルからのｎバイトの第１のデータブロックを識別し、前記キー規定方法を使用して、前記第１のデータブロックに関係付けられたソースキー値を計算するステップと、
    （ｅ）前記送信側コンピュータにおいて、前記ソースキー値を前記リファレンスキー値の各々とを比較するステップと、
    （ｆ）前記ステップ（ｅ）において一致が見つかった場合、この一致の表示を前記送信側コンピュータから前記受信側コンピュータに送信し、前記受信側コンピュータが、前記リファレンスファイルからの一致するデータを前記複製ファイルに加えるステップと、
    （ｇ）前記ステップ（ｅ）において一致が見つからなかった場合、前記送信側コンピュータから前記受信側コンピュータに、前記複製ファイルに加えられるべきｎバイトよりも少ない前記第１のデータブロックのうちのデータを送信し、送信された前記データを除き且つｎバイトの第２のデータブロックの第２のソースキー値を計算するステップと、
    （ｈ）前記受信側コンピュータにおけるデータが前記ソースファイルと同じになるまで、前記ソースファイルの残りのデータブロックに関して、前記ステップ（ｄ）〜（ｇ）を繰り返すステップと、
    を含むことを特徴とする方法。
12. 請求項１１に記載の方法において、前記ステップ（ｅ）において一致が見つかった場合、前記ステップ（ｅ）における前記比較に用いられたデータブロックの直後に続くｎバイトのデータブロックのソースキー値が、前記ステップ（ｅ）での次回の比較において用いられることを特徴とする方法。
13. 請求項１１に記載の方法において、前記リファレンスキーは第１部分及び第２部分を備えることを特徴とする方法。
14. 請求項１１に記載の方法において、前記データブロックの一様な長さは少なくとも２５６バイトであることを特徴とする方法。
15. 請求項１１に記載の方法において、前記キー規定方法は長さにおいて少なくとも３２ビットであるキーを規定することを特徴とする方法。

Images