(57)【要約】【課題】受信側が所有しているデータが類似の場合でも転送不要とすることを目的とする。【解決手段】  送信側は、第一のデータの特徴量及び誤り訂正用の復元バイト列を送信する。  受信側は、既に所有するデータの中で、受信した特徴量と類似の範囲の特徴量を有する第二のデータを特定し、受信した復元バイト列で誤り訂正処理を施し、それを第一のデータとして記憶する。  データが数キロバイトであっても、その特徴量及び復元バイト列はいずれも高々数十バイトであり、ネットワーク負荷が小さい。【選択図】  図２
2013190891.tif 000002
【特許請求の範囲】
【請求項１】
第一のデータの特徴量、当該第一のデータの誤り訂正用の復元バイト列及び当該第一のデータのハッシュ値を通信回線に送信するデータ送信装置と、
既に所有するデータの中で前記通信回線を介して受信した前記特徴量と類似の範囲の特徴量を有する第二のデータを特定し、当該第二のデータに前記通信回線を介して受信した前記復元バイト列を付加して誤り訂正処理を施し、当該誤り訂正処理後の第二のデータのハッシュ値を計算して、前記第一のデータのハッシュ値と比較し、一致したときに当該誤り訂正処理後の第二のデータを前記第一のデータとして記憶するデータ受信装置とを有する
ことを特徴とする、データ転送システム。
【請求項２】
請求項１において、
当該データ送信装置は、
前記第一のデータの特徴量を算出する特徴量算出部と、
前記第一のデータの誤り訂正が可能な復元バイト列を計算する復元バイト列算出部と、
前記第一のデータのハッシュ値を計算するハッシュ値算出部と
を有し、
当該データ受信装置は、
既に所有するデータの特徴量と前記通信回線を介して受信した前記特徴量とが類似の範囲として予め決められた数値範囲であるかを照合する特徴量照合部と、
前記復元バイト列を用いて前記第二のデータの誤り訂正処理を施す復元部と、
当該誤り訂正処理後の第二のデータのハッシュ値を計算して、前記第一のデータのハッシュ値と比較するハッシュ値照合部と
を有する
ことを特徴とする、データ転送システム。
【請求項３】
請求項２において、
当該データ受信装置は、既に所有するデータの中で前記通信回線を介して受信した前記特徴量と類似の範囲の特徴量を有するデータがない場合、若しくは、前記第一のデータのハッシュ値と一致しなかった場合は、その旨若しくは前記第一のデータの送信依頼を前記データ送信装置に送信し、
当該データ送信装置は、その旨若しくは前記依頼を受信すると、前記第一のデータを当該データ受信装置に送信する
ことを特徴とする、データ転送システム。
【請求項４】
第一のデータの特徴量及び当該第一のデータの誤り訂正用の復元バイト列を通信回線に送信するデータ送信装置と、
既に所有するデータの中で前記通信回線を介して受信した前記特徴量と類似の範囲の特徴量を有する第二のデータを特定し、当該第二のデータに前記通信回線を介して受信した前記復元バイト列を付加して誤り訂正処理を施し、当該誤り訂正処理後の第二のデータを前記第一のデータとして記憶するデータ受信装置とを有する
ことを特徴とする、データ転送システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ間でデータのやり取りを行うデータ転送システムに関する。
【背景技術】
【０００２】
非特許文献１では、データをクライアント側でチャンクとよばれる数キロバイトの単位に分割し、サーバが所有していない新規チャンクのみを転送する方式を提案している。サーバがチャンクを所有しているかどうかは、チャンクのハッシュ値が一致するかどうかで判断する。ハッシュ値はチャンクよりもデータ量が小さいため（数十バイト）、低帯域ネットワークでも負荷をかけずに送信することができる。クライアントはサーバが所有していないチャンクのみを転送すればよく、通常のデータ転送方式と比較して、より高速に全データをやり取りできるようになる。
【０００３】
非特許文献１の方式を適用した場合、クライアントが転送しようとしているチャンクの中身が、サーバで所有しているチャンクの中身と少しでも異なっている場合、ハッシュ値が一致しないため、クライアントは当該チャンクの中身をすべて転送する必要がある。非特許文献２や特許文献１ではこの無駄を解決すべく、クライアント側でチャンクをさらに分割して、一致していない部分を絞り込んで転送する方式を提案している。
【０００４】
なお、チャンキングについては非特許文献３〜５に、以下で述べる特徴量については非特許文献６および特許文献２に記載されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】A. Muthitacharoen, B. Chen and D. Mazieres: "A low-bandwidth network file system," Proceedings of the 18th SOSP, Banff, Canada, 10-2001.
【非特許文献２】S. Ihm, K. Park and V. S. Pai: "Wide-area Network Acceleration for the Developing World," USENIXATC'10 Proceedings of the 2010 USENIX conference on USENIX annual technical conference, 2010.
【非特許文献３】J. Kornblum: "Identifying almost identical files using context triggered piecewise hashing," Digital investigation 3S pp.91-97, 2006.
【非特許文献４】R. M. Karp and M. O. Rabin: "Pattern-matching algorithms," IBM Journal of Research and Development, 31(2) pp. 249-260, 1987.
【非特許文献５】N. Bjorner, A. Blass, Y. Gurevich: "Content-dependent chunking for differential compression, the local maximum approach," Journal of Computer and System Sciences, 76 (3-4), pp. 154-203, 2010.
【非特許文献６】D. Teodosiu, N. Bjorner, Y. Gurevich, M. Manasse, J. Porkka and A. Wable: "Optimizing File Replication over Limited-Bandwidth Networks using Remote Differential Compression," Technical report, Microsoft Corporation, 2006.
【特許文献】
【０００６】
【特許文献１】米国特許 7,116,249
【特許文献２】国際公開第2012-005016号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１の方式を適用した場合、送信側が転送しようとしているチャンクの中身が、受信側で所有しているチャンクの中身と少しでも異なっている場合、ハッシュ値が一致しないため、送信側は当該チャンクの中身をすべて転送する必要がある。非特許文献２や特許文献１の方式でも、チャンクの中身の不一致部分を転送する必要がある。
【０００８】
そこで、本発明は、受信側が所有しているデータが類似の場合でも転送不要とすることを目的とする。
【課題を解決するための手段】
【０００９】
（請求項の記載とあわせます）
本発明では、第一のデータの特徴量及び当該第一のデータの誤り訂正用の復元バイト列を通信回線に送信するデータ送信装置と、
既に所有するデータの中で前記通信回線を介して受信した前記特徴量と類似の範囲の特徴量を有する第二のデータを特定し、当該第二のデータに前記通信回線を介して受信した前記復元バイト列を付加して誤り訂正処理を施し、当該誤り訂正処理後の第二のデータを前記第一のデータとして記憶するデータ受信装置とを備えたデータ転送システムを提供する。
【発明の効果】
【００１０】
データが数キロバイトであっても、その特徴量及び復元バイト列はいずれも高々数十バイトであり、ネットワーク負荷が小さい。
【図面の簡単な説明】
【００１１】
【図１】差分転送システムの概略を例示する図である。
【図２】主要な処理の概要を示す図である。
【図３】データ送信クライアントの概略構成を例示するブロック図である。
【図４】データベースサーバの概略構成を例示するブロック図である。
【図５】データ送信クライアントとデータベースサーバのデータ転送処理を例示するシーケンス図である。
【図６】データ送信クライアントとデータベースサーバのデータ転送処理を例示するシーケンス図である。
【図７】データ送信クライアントとデータベースサーバのデータ転送処理を例示するシーケンス図である。
【図８】データ送信クライアントとデータベースサーバのデータ転送処理を例示するシーケンス図である。
【図９】データ送信クライアントとデータベースサーバのデータ転送処理を例示するシーケンス図である。
【図１０】データベースサーバが作成する管理テーブルのデータ構成を例示する図である。
【図１１】ファイルをチャンクに分割する手順を例示する図である。
【図１２】チャンクからファジィハッシュを計算する処理およびファジィハッシュから類似度を計算する処理の概要を例示する図である。
【図１３】チャンクからブルームフィルタを計算する処理およびブルームフィルタから類似度を計算する処理の概要を例示する図である。
【図１４】チャンクからトレイトを計算する処理の概要を例示する図である。
【図１５】チャンクから復元バイト列を求める処理の概要を例示する図である。
【図１６】復元バイト列を用いてチャンクを復元する処理の概要を例示する図である。
【図１７】データベースサーバが作成する基礎チャンク管理テーブルのデータ構成を例示する図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。
【００１３】
図１は、差分転送システムの概略を例示する図である。図示するように、差分転送システムは、n台のデータ送信クライアント20-1〜20-nと、データベースサーバ30を備え、これらがネットワーク10を介して相互に情報を送受信できるよう設計されている。データ送信クライアント20-1〜20-nはすべて同じ構成をとる。以下、任意の一つをデータ送信クライアント20と呼ぶ。
なお、本実施形態では、非特許文献１などの公知文献の文言にあわせて、クライアントやサーバといった文言を用いることにする。一般には、データ送信クライアント20はデータを送信するデータ送信装置、データベースサーバ30はデータを受信するデータ受信装置とよぶべきものである。
【００１４】
本実施形態では、データ送信クライアント20は、転送対象となるファイルをまずチャンクに分割して、データベースサーバ30が所有していないチャンク100のみを転送することで、データ転送の高速化を図る。
以下、説明を明確にするために、非特許文献１などの公知文献にあわせて、ファイルを分割して得られるデータをチャンクとよび区別することにする。チャンクの実体はバイト列からなるデータに過ぎないため、以下で説明する実施の形態は、チャンクをデータと読み替えても正しく動作する。
【００１５】
図２を用いて本実施形態における主要な処理の概要を説明する。データ送信クライアント20がファイル200をデータベースサーバ30に転送する場合を想定する。
【００１６】
まずデータ送信クライアント20は、ファイル200をチャンクとよばれる単位で分割する（チャンキング）。チャンキングの具体的な手順については後で図１１を用いて説明する。図２では、チャンキングの結果、ファイル200がチャンク202-1〜202-4の4つのチャンク202に分割された。
【００１７】
次にデータ送信クライアント20は、チャンク202-1〜202-4のそれぞれについて特徴量を計算する。特徴量とはチャンク間の類似度を近似的に求めるための数バイトから数十バイトのバイト列である。詳細については図１２〜図１４を用いて後で説明する。図２では例としてチャンク202-3の特徴量204が求まっている。特徴量204はデータベースサーバ30へ送信される。
【００１８】
データベースサーバ30では、受信した特徴量204と所有している各チャンクの特徴量とを照合して類似度を計算し（特徴量照合処理210）、チャンク202-3と類似したチャンクを特定する。図２ではチャンク212が見つかった。
【００１９】
類似したチャンクが存在した場合、その旨をデータ送信クライアント20に通知する。それを受けてデータ送信クライアント20は、チャンク202-3から復元バイト列206を計算する。復元バイト列は、リードソロモン符号などのブロック符号の検査バイト列に相当する。チャンクの復元は、類似したチャンクに復元バイト列を付加して、誤り訂正処理を施すことでなされる。詳細については後で図１５、１６を用いて説明する。データベースサーバ30はデータ送信クライアント20から復元バイト列206を受け取り、チャンク212に付加してチャンクの復元を試みる（チャンク復元処理220）。
【００２０】
図２では復元に成功し、チャンク222が得られた。データベースサーバ30は、復元に成功した旨をデータ送信クライアント20に通知する。それを受けてデータ送信クライアント20は、チャンク202-3のハッシュ値208を計算して、データベースサーバ30へ送信する。データベースサーバ30は、受信したハッシュ値とチャンク222のハッシュ値とを照合し、一致していた場合はデータ送信クライアント20が所有するチャンク202-3を復元できたものとして、チャンク202-3の送信を取りやめる旨データ送信クライアント20に通知する（ハッシュ照合処理230）。チャンクを復元できなかった場合やハッシュ値が一致しなかった場合は、データ送信クライアント20へチャンク202-3の転送を要求する。
【００２１】
以上の方式によりネットワーク上でやり取りするデータ量が削減され、ファイル200の転送時間の短縮が期待できる。
【００２２】
図３は、データ送信クライアントの概略構成を例示するブロック図である。図示するようにデータ送信クライアント20は、CPU302、メモリ304、記憶装置306、ユーザインターフェース308、通信インターフェース310、データ送信部32、および設定部330を備え、これらが内部バス300を介して相互に情報を送受信できるように設計されている。データ送信部32は、ファイル情報照合部320、チャンキング部322、特徴量算出部324、復元バイト列算出部326、ハッシュ値算出部328を備える。これらの装置は内部ハブ300を介して単体でCPU302などと相互に情報を送受信することができる。
【００２３】
まずは汎用的な構成要素について説明する。CPU302は、様々な数値計算や情報処理、機器制御などを行う中央処理装置である。メモリ304は、CPU302が直接読み書きできるRAMやROMなどの半導体記憶装置である。記憶装置306は、コンピュータ内でデータやプログラムを記憶するハードディスクや磁気テープ、フラッシュメモリなどといった装置である。当該装置はデータベースサーバ30に送信するファイルなどを格納する。
【００２４】
ユーザインターフェース308は、ディスプレイやマウス、キーボードなどといった、ユーザに処理結果を出力し、かつユーザの指示を受け付けてデータ送信クライアント20の各構成要素に反映させるための装置である。
【００２５】
通信インターフェース310は、データ送信クライアント20の各構成要素のネットワーク10を介したデータの送受信を制御するための装置である。相手方と認証して通信路を確立したり、処理が完了した後や、一定時間を経過しても相手方が何の応答しなかった場合などに通信路を切断したりなどの制御をおこなう。
【００２６】
本実施例特有の構成要素は、データ送信部32、これを構成するファイル情報照合部320、チャンキング部322、特徴量算出部324、復元バイト列算出部326、ハッシュ値算出部328である。これらのうち従来のデータ転送装置にはない最も特徴的な構成要素は、特徴量算出部324および復元バイト列算出部326である。
【００２７】
データ送信部32は、記憶装置306に格納されているファイルのデータベースサーバ30への転送指示をユーザインターフェース308を介してユーザから受け取り、ファイル情報照合部320、チャンキング部322、特徴量算出部324、復元バイト列算出部326、ハッシュ値算出部328などを制御して、メモリ304または記憶装置306に格納されているチャンクや特徴量などのデータを、通信インターフェース310を介してデータベースサーバ30と送受信するための装置である。データ転送処理の一連の動作フローについては後で図５〜図９を用いて説明する。
【００２８】
ファイル情報照合部320は、データベースサーバ30にファイルを転送する前に同一のファイルをデータベースサーバ30が所有していないかどうかを確認するための装置である。詳細については図５、６を用いて説明する。
【００２９】
チャンキング部322は、記憶装置306に格納されているファイルを読み取ってチャンクに分割し、メモリ304または記憶装置306に一時的に格納するための装置である。チャンキング処理の詳細については、後で図１１を用いて説明する。
【００３０】
特徴量算出部324は、メモリ304または記憶装置306に一時的に格納されているチャンクを読み取り、特徴量を算出し、メモリ304または記憶装置306に出力する装置である。特徴量の具体的な算出方法については、後で図１２〜図１４を用いて説明する。
【００３１】
復元バイト列算出部326は、メモリ304または記憶装置306に一時的に格納されているチャンクを読み取り、復元バイト列を算出し、メモリ304または記憶装置306に出力する装置である。復元バイト列の具体的な算出方法については、後で図１５を用いて説明する。
【００３２】
ハッシュ値算出部328は、メモリ304または記憶装置306に格納されているファイルやチャンクを読み取り、ハッシュ値を算出し、メモリ304または記憶装置306に出力する装置である。ハッシュ値を導出するハッシュ関数として、例えばMD5やSHA-1などが知られている。
【００３３】
設定部330は、データベースサーバ30からの応答を待つ待機時間の上限や、チャンキング、特徴量算出などの処理に必要なパラメータを設定するための装置である。これらのパラメータはユーザインターフェース308を介してユーザによって設定され、チャンキング部322、特徴量算出部324、復元バイト列算出部326、ハッシュ値算出部328などに反映される。
【００３４】
なお、データ送信部32、これを構成するファイル情報照合部320、チャンキング部322、特徴量算出部324、復元バイト列算出部326、ハッシュ値算出部328、および設定部332については、それぞれの装置が単体で処理を実行してもよいし、それぞれの装置はプログラムのみを具備し、CPU302が当該プログラムをメモリ304に読み込んで実行してもよい。
【００３５】
図４は、データベースサーバ30の概略構成を例示するブロック図である。図示するようにデータベースサーバ30は、CPU402、メモリ404、記憶装置406、ユーザインターフェース408、通信インターフェース410、データ受信部42、テーブル管理部430、および設定部432を備え、これらが内部バス400を介して相互に情報を送受信できるように設計されている。データ受信部42は、ファイル情報照合部420、特徴量照合部422、チャンク復元部424、ハッシュ値照合部426、データ登録部428を備える。これらの装置は内部ハブ400を介して、単体でCPU402などと相互に情報を送受信することができる。
【００３６】
汎用的な構成要素であるCPU402、メモリ404、記憶装置406、ユーザインターフェース408、通信インターフェース410については、図３と同様の機能を有するので説明を割愛する。本実施例特有の構成要素は、データ受信部42、これを構成するファイル情報照合部420、特徴量照合部422、チャンク復元部424、ハッシュ値照合部426、データ登録部428、およびテーブル管理部430である。これらのうち従来のデータ転送装置にはない最も特徴的な構成要素は、特徴量算出部422およびチャンク復元部424である。
【００３７】
データ受信部42は、通信インターフェース410を介してデータ送信クライアント20から特徴量やチャンクなどのデータを受信してメモリ404または記憶装置406に一時的に格納し、ファイル情報照合部420、特徴量照合部422、チャンク復元部424、ハッシュ値照合部428などを制御して、データ送信クライアント20が転送したファイルを受信または復元して、記憶装置406に格納するための装置である。データ転送処理の一連の動作フローについては後で図５〜図９を用いて説明する。
【００３８】
ファイル情報照合部420は、データ送信クライアント20からの要求に応じて記憶装置406に格納されているファイルの一覧（ファイル管理テーブル）を参照し、データ送信クライアント20が転送しようとしているファイルと同一のファイルが記憶装置406に存在するかを確認するための装置である。ファイル管理テーブルの具体例については後で図１０を用いて説明する。もし同一のファイルが存在しているのであれば、データ受信部42はその旨を通信インターフェース310を介してデータ送信クライアント20に通知する。詳細については後で図５、６を用いて説明する。
【００３９】
特徴量照合部422は、データ送信クライアント20から特徴量を受信してメモリ404または記憶装置406に一時的に格納し、記憶装置406に格納されているチャンクの特徴量の一覧（チャンク管理テーブル）を参照して、受信した特徴量と各チャンクの特徴量を照合し、類似するチャンクを特定するための装置である。チャンク管理テーブルの具体例については後で図１０を用いて説明する。また、特徴量の照合処理の詳細については、後で図１２〜図１４を用いて説明する。特定された類似チャンクは、その実データまたはポインタがメモリ404または記憶装置406に一時的に格納される。
【００４０】
チャンク復元部424は、データ送信クライアント20から復元バイト列を受信してメモリ404または記憶装置406に一時的に格納し、特徴量照合部422がメモリ404または記憶装置406に一時的に格納した類似チャンクに付加して誤り訂正を施すことで、チャンクの復元処理を行う装置である。復元処理の詳細については後で図１６を用いて説明する。復元に成功したチャンクはメモリ404または記憶装置406に一時的に格納される。
【００４１】
ハッシュ値照合部426は、データ送信クライアント20からハッシュ値を受信してメモリ404または記憶装置406に一時的に格納し、チャンク復元部424がメモリ404または記憶装置406に一時的に格納したチャンクのハッシュ値を計算し、一致するかどうか照合する装置である。
【００４２】
データ登録部428は、データ送信クライアント20から受信したチャンクや復元したチャンクを記憶装置406に格納し、テーブル管理部430を介してファイル管理テーブルやチャンク管理テーブルなどを更新するための装置である。
【００４３】
テーブル管理部430は、記憶装置406へのファイル操作を監視して、またはデータ受信部42からの呼び出しを受けて、ファイル管理テーブルやチャンク管理テーブルなどを更新するための装置である。これらの管理テーブルの具体例については後で図１０を用いて説明する。なお、これらの管理テーブル自体は、メモリ404または記憶装置406に格納される。
設定部432は、データ送信クライアント20からの応答を待つ待機時間の上限や、特徴量照合、ハッシュ値算出などの処理に必要なパラメータを設定するための装置である。これらのパラメータはユーザインターフェース408を介してユーザによって設定され、ファイル情報照合部420、特徴量照合部422、チャンク復元部424、ハッシュ値照合部426、データ登録部428などに反映される。
【００４４】
なお、データ受信部42、これを構成するファイル情報照合部420、特徴量照合部422、チャンク復元部424、ハッシュ値照合部426、データ登録部428、およびテーブル管理部430、および設定部43については、それぞれの装置が単体で処理を実行してもよいし、それぞれの装置はプログラムのみを具備し、CPU402が当該プログラムをメモリ404に読み込んで実行してもよい。
【００４５】
図５を用いて、データ送信クライアント20とデータベースサーバ30の代表的なデータ転送処理を例示する。図３のデータ送信部32と図４のデータ受信部42とが、以下の手順でネットワーク10を介したデータ転送を行う。
【００４６】
（S500）まずデータ送信クライアント20とデータベースサーバ30の間で通信路を確立する。具体的には、データ送信クライアント20の通信インターフェース310がデータベースサーバ30の通信インターフェース410に接続要求を通知し、通信インターフェース410がそれを許可することで、相互間の通信路を確立する。または、IKE（Internet Key Exchange）といった標準手順によって暗号化方式や暗号鍵などの情報を交換・共有し、より安全な通信路を確立してもよい。
【００４７】
（S502）データ送信クライアント20のファイル情報照合部320は、ユーザがユーザインターフェース308を介して転送を指示したファイルFの情報502を、通信インターフェース310を介してデータベースサーバ30に送信する。ここでファイル情報502とは、ファイルFの名称、サイズ、作成日時、ハッシュ値などである。ファイルFのハッシュ値は、ハッシュ値算出部328が計算する。
【００４８】
（S504）データベースサーバ30のデータ受信部42は、通信インターフェース410を介してファイル情報502を受信し、ファイル情報照合部420に渡す。ファイル情報照合部420は、記憶装置406に格納されているファイルの一覧（ファイル管理テーブル）を参照し、ファイル情報502をもとに、ファイルFと同一のファイルが記憶装置406に存在するかを確認する。ファイル管理テーブルの具体例については後で図１０を用いて説明する。以下、ファイルFと同一のファイルを所有していないと仮定する。所有している場合については次の図６で説明する。
【００４９】
（S506）データベースサーバ30のデータ受信部42は、同一ファイルを所有していない旨506を通信インターフェース410を介してデータ送信クライアント20に通知する。
（S508）データ送信クライアント20のデータ送信部32は、同一ファイルを所有していない旨の通知506を通信インターフェース310を介して受信し、チャンキング部322を起動する。チャンキング部322は、ファイルFを記憶装置306から読み取って、チャンクに分割する。チャンキング処理の詳細については、後で図１１を用いて説明する。以下、転送対象のファイルがk個のチャンクAi（i=1,...,k）に分割されたとする。
【００５０】
（S52）チャンクAiごとに、以下のS520〜S542の処理を行う（i=1,...,k）。すべてのチャンクAiについてS520〜S542の処理が完了したらS560へ飛ぶ。
【００５１】
（S520）データ送信クライアント20の特徴量算出部324は、チャンクAiの特徴量522を算出する。特徴量の具体的な算出方法については、後で図１２〜図１４を用いて説明する。
【００５２】
（S522）データ送信クライアント20のデータ送信部32は、S520で求めた特徴量522を、通信インターフェース310を介してデータベースサーバ30に送信する。
【００５３】
（S524）データベースサーバ30のデータ受信部42は、通信インターフェース410を介して特徴量522を受信し、特徴量照合部422に受け渡す。特徴量照合部422は、チャンクの特徴量の一覧（チャンク管理テーブル）を参照して、特徴量522と各チャンクの特徴量を照合し、チャンクAiに類似するチャンクを特定する。チャンク管理テーブルの具体例については後で図１０を用いて説明する。また、特徴量の照合処理の詳細については、後で図１２〜図１４を用いて説明する。以下、類似チャンクAi'が見つかったと仮定する。見つからなかった場合については図７で説明する。
【００５４】
（S526）データベースサーバ30のデータ受信部42は、類似チャンクAi'を所有している旨526を、通信インターフェース410を介してデータ送信クライアント20に通知する。
（S528）データ送信クライアント20のデータ送信部32は、類似チャンクAi'を所有している旨の通知526を通信インターフェース310を介して受信したとき、復元バイト列算出部326を起動する。復元バイト列算出部326は、チャンクAiの復元バイト列530を算出する。復元バイト列の具体的な算出方法については後で図１５を用いて説明する。
【００５５】
（S530）データ送信クライアント20のデータ送信部32は、S528で求めた復元バイト列530を、通信インターフェース310を介してデータベースサーバ30に送信する。
【００５６】
（S532）データベースサーバ30のデータ受信部42は、通信インターフェース410を介して復元バイト列530を受信し、チャンク復元部424に受け渡す。チャンク復元部424は、復元バイト列530を類似チャンクAi'に付加して、チャンクの復元処理を行う。復元処理の詳細については、後で図１６を用いて説明する。以下、復元に成功し、チャンクBiが得られたと仮定する。復元に失敗した場合については図８で説明する。
【００５７】
（S534）データベースサーバ30のデータ受信部42は、復元に成功した旨534を、通信インターフェース410を介してデータ送信クライアント20に通知する。
【００５８】
（S536）データ送信クライアント20のデータ送信部32は、復元に成功した旨の通知534を通信インターフェース310を介して受信し、ハッシュ値算出部328を起動する。ハッシュ値算出部328は、チャンクAiのハッシュ値528を算出する。
【００５９】
（S538）データ送信クライアント20のデータ送信部32は、S536で求めたハッシュ値528を、通信インターフェース310を介してデータベースサーバ30に送信する。
【００６０】
（S540）データベースサーバ30のデータ受信部42は、通信インターフェース410を介してハッシュ値530を受信し、ハッシュ値照合部426に受け渡す。ハッシュ値照合部426は、チャンクBiのハッシュ値を計算し、ハッシュ値530と一致するか確かめる。以下、一致したと仮定する。一致しなかった場合については図９で説明する。
【００６１】
（S542）データベースサーバ30のデータ登録部428は、データベースサーバ30側で復元したチャンクBi（すなわちデータ送信クライアント20が所有するチャンクAi）を記憶装置406に格納し、テーブル管理部430に格納したチャンクBiの情報をテーブル管理部430に通知する。テーブル管理部430は、当該チャンクの情報をチャンク管理テーブルに追記する。チャンク管理テーブルの具体例については、後で図１０を用いて説明する。
【００６２】
（S560）すべてのチャンクAiについて以上のS520〜S542の処理が完了したら、S500で確立した通信路を切断する。
【００６３】
（S562）データベースサーバ30のデータ受信部42は、テーブル管理部430にファイル転送が完了した旨を通知する。それを受けてテーブル管理部430は、ファイル管理テーブルなどを更新する。以上でデータ転送処理が完了する。
【００６４】
本実施例によって、データ送信クライアント20が転送しようとしているチャンクと類似するチャンクをデータベースサーバ30で所有していた場合、データベースサーバ30側でそれを再現できて転送が不要となるため、非特許文献１、２や特許文献１などの従来方式と比較して、よりデータ転送の総時間を短縮することができる。
【００６５】
なお、本実施例においてはハッシュ値を用いてファイルやチャンクの同一性を確認するが、異なるファイルまたはチャンクであるにもかかわらずハッシュ値が同一となる「衝突」が発生する可能性がわずかながら存在する。衝突が発生した場合、データベースサーバ30側で正しくチャンクを受信または復元できなくなってしまう。衝突を抑える方法として、複数の異なるハッシュ関数を用いる方式が考えられる。複数のハッシュ値が同時に衝突する確率はそれぞれの衝突確率の積で与えられるので非常に小さく、かつ、ハッシュ値は高々数十バイトなので、複数送信したとしてもネットワークにかける負荷は小さい。よって、この方式によってネットワークに負荷をかけずに衝突確率を低減することができる。
【００６６】
また、S425においてチャンクAiに類似するチャンクを一つだけ特定するのではなく、あらかじめ定めた所定の閾値以上の類似度を与える複数のチャンクを特定してもよい。この場合、データ受信部42は、S532の復元処理を当該複数のチャンクについて行うことになる。復元に成功するのは（データ送信クライアント30が転送しようとしているチャンクに一致する）ただ一つのチャンクであるはずなので、復元に成功したらS532の処理を打ち切り、復元したチャンクについてS534以降の処理を行う。当該複数のチャンクすべてについて復元に失敗した場合は、図８で説明する処理を行う。
【００６７】
図５のS504で、データベースサーバ30がデータ送信クライアント20が転送しようとしているファイルFを所有していた場合の処理フローを、図６を用いて説明する。
（S500）〜（S502）図５の説明と同様である。
（S600）データベースサーバ30のデータ受信部42は、通信インターフェース410を介してファイル情報502を受信し、ファイル情報照合部420に渡す。ファイル情報照合部420はファイル管理テーブルを参照し、ファイル情報602をもとに、ファイルFと同一のファイルが記憶装置406に存在するかを確認する。以下、ファイルFと同一のファイルを所有していると仮定する。
【００６８】
（S602）データ受信部42は、同一ファイルを所有している旨602を通信インターフェース410を介してデータ送信クライアント20に通知する。それを受けてデータ送信クライアント20が通信路を切断して（S560）、処理が完了する。
【００６９】
図５のS524において、データベースサーバ30の特徴量照合部422がデータ送信クライアント20が転送しようとしているチャンクに類似したチャンクを見つけられなかった場合の処理フローを、図７を用いて説明する。
（S500）〜（S522）図５の説明と同様である。
（S700）S524と同様、データベースサーバ30の特徴量照合部422は、チャンクの特徴量の一覧（チャンク管理テーブル）を参照して、特徴量522と各チャンクの特徴量を照合し、データ送信クライアント20が転送しようとしているチャンクに類似するチャンクを特定する。以下、類似チャンクが見つからなかったと仮定する。
【００７０】
（S702）データベースサーバ30のデータ受信部42は、類似チャンクを所有していない旨702を、通信インターフェース410を介してデータ送信クライアント20に通知する。
【００７１】
（S704）データ送信クライアント20のデータ送信部32は、データ送信クライアント20が転送しようとしているチャンク704を、通信インターフェース310を介してデータベースサーバ30に転送する。
【００７２】
（S706）データベースサーバ30のデータ受信部42は、通信インターフェース410を介してチャンク704を受信し、データ登録部428に受け渡す。データ登録部428は、チャンク704を記憶装置406に格納し、格納したチャンクの情報をテーブル管理部430に通知する。テーブル管理部430は、当該チャンクの情報をチャンク管理テーブルに追記する。
【００７３】
（S560）〜（S562）図５の説明と同様である。
【００７４】
図５のS532において、データベースサーバ30のチャンク復元部424がデータ送信クライアント20が転送しようとしているチャンクを復元できなかった場合の処理フローについて、図８を用いて説明する。
（S500）〜（S530）図５の説明と同様である。
（S800）データベースサーバ30のデータ受信部42は、通信インターフェース410を介して復元バイト列530を受信し、チャンク復元部424に受け渡す。チャンク復元部424は、復元バイト列530を用いてチャンクの復元処理を行う。以下、復元に失敗したと仮定する。  
【００７５】
（S802）データベースサーバ30のデータ受信部42は、復元に失敗した旨802を、通信インターフェース410を介してデータ送信クライアント20に通知する。
（S704）〜（S706）図７の説明と同様である。
（S560）〜（S564）図５の説明と同様である。
【００７６】
図５のS540において、データベースサーバ30のハッシュ値照合部426が生成した復元チャンクのハッシュ値とデータ送信クライアント20から受信したハッシュ値とが一致しなかった場合について、図９を用いて処理フローを説明する。
（S500）〜（S538）図５の説明と同様である。
（S900）データベースサーバ30のデータ受信部42は、通信インターフェース410を介してハッシュ値530を受信し、ハッシュ値照合部426に受け渡す。ハッシュ値照合部426は、チャンク復元部424が復元したチャンクのハッシュ値を計算し、ハッシュ値530と一致するか確かめる。以下、一致しなかったと仮定する。
【００７７】
（S902）データベースサーバ30のデータ受信部42は、ハッシュ値が一致しない旨902を、通信インターフェース410を介してデータ送信クライアント20に通知する。
（S704）〜（S706）図７の説明と同様である。
（S560）〜（S564）図５の説明と同様である。
【００７８】
なお、図５〜図９において、データ転送処理中に通信路が切断された場合、または、あらかじめ定めた時間を経過しても何の応答もせず、通信インターフェース310、410が通信路を切断した場合、データ受信部42はファイルの受信を打ち切り、ファイル管理テーブル1000やファイル構成チャンク管理テーブル1040を更新しない。その結果、記憶装置406には、どのファイルの構成要素にならないチャンクが蓄積することになる。本実施例はデータベースサーバ30が多くのチャンクを所有しているほどデータ転送の高速化に効果的なので、どのファイルの構成要素にならないチャンクを蓄積しても問題ないという立場をとり、記憶装置406に格納されているチャンクのみを管理するチャンク管理テーブルを設けることにした。
【００７９】
もちろん、記憶装置406の容量が切迫している場合などに、どのファイルにも紐付いていないチャンクを削除することも可能である。その場合、テーブル管理部430を介してチャンク管理テーブルを更新する必要がある。
【００８０】
図１０を用いて、テーブル管理部430が管理する、ファイル管理テーブル1000、チャンク管理テーブル1020、ファイル構成チャンクテーブル1040のデータ構成について説明する。
【００８１】
ファイル管理テーブル1000は、図４、５の説明で述べた、データベースサーバ30の記憶装置406に格納されているファイルの一覧のことである。ファイル管理テーブル1000は、ファイルの一意なIDを格納するファイルIDカラム1002、ファイル名を格納するファイル名カラム1004、ファイルが格納されているフォルダ名を格納するフォルダ名カラム1006、ファイルのバイト長を格納するファイルサイズカラム1008、ファイル作成日時を格納するファイル作成日時カラム1010、ファイルのハッシュ値を格納するハッシュ値カラム1012などで構成される。これらの情報は、データ送信クライアント20が転送するファイルと同一のファイルをデータベースサーバ30が所有しているかどうかを判定するために用いられる。なお、ハッシュ値カラム1012は、図５の説明で述べたように複数のハッシュ値を用いてファイルの同一性を判断する場合には、複数のハッシュ値を格納する。
【００８２】
図１０の例では、ファイルID「1」のファイル「manual.doc」がフォルダ「C:\」に格納されており、そのファイルサイズは133,423バイトで、ファイル作成日時は2007年10月21日、ハッシュ値が16進表記で「0abf016edf」と与えられることがわかる。
【００８３】
ファイル管理テーブル1000は、記憶装置406上でファイルが追加削除などされた場合、または図５などのS562でファイル転送が完了した場合に、テーブル管理部430によって更新される。
【００８４】
チャンク管理テーブル1020は、図４、５の説明で述べた、データベースサーバ30の記憶装置406に格納されているチャンクの一覧のことである。チャンク管理テーブル1020は、チャンクの一意なIDを格納するチャンクIDカラム1022、チャンクの特徴量を格納する特徴量カラム1024、チャンクのハッシュ値を格納するハッシュ値カラム1026、チャンクのバイト長を格納するチャンクサイズカラム1028などで構成される。なお、ハッシュ値カラム1026は、図５の説明で述べたように複数のハッシュ値を用いて同一性を判断する場合には、複数のハッシュ値を格納する。特徴量を用いたチャンクの類似判定の詳細については、後で図１２〜図１４を用いて説明する。
【００８５】
図１０の例では、チャンクID「0x000001」のチャンクの特徴量がBase64表記で「AEHgyXIWET/BAQC7PRcRP8EBAFi」、ハッシュ値が16進表記で「9bac9347ff」与えられ、チャンクサイズが1,423バイトであることが分かる。なお、ファイルIDと区別するため、チャンクIDを「0x」で始まる文字列で記載した。
【００８６】
チャンク管理テーブル1100は、記憶装置406上でチャンクが追加削除などされた場合、または図５のS542、図７〜図９のS706でデータ登録部428が記憶装置406にチャンクを格納した場合に、テーブル管理部430によって更新される。
【００８７】
ファイル構成チャンク管理テーブル1040は、ファイルを構成するチャンクについての情報をまとめた一覧のことである。ファイル構成チャンク管理テーブル1040は、ファイルIDを格納するファイルIDカラム1042、ファイル名を格納するファイル名カラム1044、ファイルが格納されているフォルダ名を格納するフォルダ名カラム1046、ファイルを構成するチャンクのチャンクIDを格納するチャンクIDカラム1048、チャンクがファイルの先頭何バイト目から開始するか、オフセットについての情報を格納するオフセットカラム1050、チャンクのサイズを格納するチャンクサイズカラム1052などで構成される。
【００８８】
図１０の例では、ファイルID「1」のファイル「manual.doc」がフォルダ「C:\」に格納されており、ファイル「manual.doc」の先頭から1,422バイト目までがチャンクID「0x000001」のチャンクで、1,423バイトから2,314バイト目までがチャンクID「0x000002」のチャンクで構成されていることが分かる。
【００８９】
ファイル構成チャンク管理テーブル1040は、記憶装置406上でファイルが追加削除などされた場合、または図５などのS562でファイル転送が完了した場合に、テーブル管理部430によって更新される。
【００９０】
図３のチャンキング部322が行うファイルのチャンキングの具体的な手順について、図１１を用いて説明する。
【００９１】
単純なチャンキングの方法として、あらかじめ定めた固定長でファイルを分割する方式が考えられる。しかしこの方式では、ファイルの先頭に1バイトでも挿入されるとファイルの分割点がずれてしまい、チャンクが一致しなくなってしまう。非特許文献１などの公知技術では、チャンクのハッシュ値の同一性をもとに転送すべきチャンクを決めるので、これは好ましくない。そこで非特許文献１などでは、チャンクの長さを可変にしてファイルを分割する方式を用いている。本実施例では、チャンクの長さが固定長の方式、非特許文献１などで採用されている可変長の方式、どちらのチャンキング方式を採用してもよい。
【００９２】
可変長の方式では、図１１で示すような以下の処理を行ってファイル1100をチャンキングする。
（１）チャンキング部322は、ファイル1100のtバイト目から1バイトずつ走査し、走査点1104の前tバイトの部分バイト列1102を取り出す。tは小さい値で、例えば非特許文献３では7としている。本実施例でも同じ値をとって構わない。走査点1104が先頭からpバイト目にあるとき、部分バイト列1102は、p-t+1バイト目のバイト値1106-1からpバイト目のバイト値1106-tのt個のバイト値で構成される。なお、pバイト目のバイト値1106-tと走査点1104は一致する。
（２）走査点1104がファイル1100をチャンクに分割するための分割点であるかどうか判断するために、t個のバイト値1106-1〜1106-tからラビンフィンガープリント1120を計算する。ラビンフィンガープリント1120とはランダムなバイト値r1〜rtと部分バイト列1102の内積のことである。ラビンフィンガープリントの詳細については非特許文献４を参照のこと。以下、部分バイト列1102に対するラビンフィンガープリントの値をRと書く。
（３）Rをあらかじめ定めた値（以下Dとする）で割った余りが0となったとき、走査点1104をファイル1100をチャンクに分割するための分割点とする（チャンキング条件1140）。
（４）チャンキング部322は、（１）〜（３）の処理をファイル1100のtバイト目から1バイトずつ走査して繰り返し行うことで、ファイル1100を複数のチャンクに分割する。
【００９３】
仮にファイル1100がランダムなバイト値で構成されるのであれば、チャンキング条件1140が満たされる確率は1/Dに等しくなり、チャンクは平均Dの長さとなる。しかし、実際にはファイル1100のバイト値の分布には偏りがあるので、必ずしも長さDのチャンクに分解できるとは限らない。ラビンフィンガープリントはチャンクの長さの偏りが発生しにくく、また高速に計算できることが知られているため、チャンキングで採用されることが多い。チャンクの長さの偏りなど数学的な解析については非特許文献５に詳しい。
【００９４】
本実施例の第一の特徴は、データベースサーバ30がチャンクの特徴量を用いて類似するチャンクを見つけ出す点である。以下、図１２〜図１４を用いて、チャンクの特徴量の算出方法および特徴量を用いたチャンクの類似判定の方法について、具体的に説明する。特徴量の具体例として、類似度の近似精度が高いファジィハッシュ（図１２）、データ量が少ないブルームフィルタ（図１３）、その改良であるトレイト（図１４）をあげる。
【００９５】
図１２は、チャンクからファジィハッシュを計算する処理、およびファジィハッシュから類似度を計算する処理の概要を例示する図である。ファイル1200が、図１１で説明したようなチャンキング処理を経てチャンキングされたとする。チャンキング後のファイル1200内のチャンク1202のファジィハッシュは、以下の手順で求められる。
（１）データ送信クライアント20の特徴量算出部324は、チャンキング部322を呼び出して、チャンク1202をさらに細かくチャンキングする。図１１の説明で述べた通り、チャンキング条件1140におけるDの値を小さくとることで、チャンク1202をさらに細かくチャンキングできる。以下、チャンク1202をさらにチャンキングしたものをサブチャンクとよぶ。サブチャンクの個数をdとかく。図１２ではチャンク1202がd=5個にチャンキングされて、サブチャンク1204（S1,...,S5）が得られた。
（２）サブチャンク（S1,S2,...,Sd）それぞれについてハッシュ値を計算する。サブチャンクSiのハッシュ値をHash(Si)とかく（i=1,...,d）。
（３）計算したハッシュ値{Hash(Si)|i=1,...,d}の配列(Hash(S1),...,Hash(Sd))が、ファジィハッシュである。図１２の例では、チャンク1202のファジィハッシュ1206は、要素がd=5個の配列(Hash(S1),...,Hash(S5))で与えられる。
【００９６】
ファジィハッシュを用いると、どのサブチャンクが一致するかどうか容易に特定することができる。よってチャンクの類似度を、共通するサブチャンクの個数とサブチャンク全体の要素数の比で近似すれば、高速に類似度の近似値を計算できる。具体的は、ファジィハッシュH=(h1,h2,...)とF=(f1,f2,...)が与えられた場合、類似度は、HとFの積集合の要素数とHとFの和集合の要素数の比で近似できる。
【００９７】
図１２の例では、チャンク1202がサブチャンク1204にチャンキングされてファジィハッシュ1206が求まり、チャンク1212がサブチャンク1214にチャンキングされてファジィハッシュ1216が求まっている。サブチャンク1214はサブチャンク1204とS2、S2'が異なり、また、S5に相当するサブチャンクがない。チャンクが異なればハッシュ値も異なるので、ファジィハッシュ1206、1216の積集合は(Hash(S1), Hash(S3), Hash(S4))、和集合は(Hash(S1), Hash(S2), Hash(S2'), Hash(S3), Hash(S4), Hash(S5))で与えられる。従って、チャンク1202と1212の類似度は3/6=1/2で近似的に与えられる。
【００９８】
ファジィハッシュは類似ファイルの検索などに用いられている。詳細については非特許文献３や特許文献２を参照のこと。
【００９９】
ファジィハッシュはサブチャンクのハッシュ値をすべて保持しておく必要があるため、データ量が多い。データ量を大幅に削減した特徴量としてブルームフィルタが知られている。図１３を用いて、ブルームフィルタを計算する処理、およびファジィハッシュから類似度を計算する処理の概要について説明する。図１１と同様、ファイル1300が、図１１で説明したようなチャンキング処理を経てチャンキングされたとする。チャンキング後のファイル1300内のチャンク1302のブルームフィルタは、以下の手順で求められる。
（１）データ送信クライアント20の特徴量算出部324は、チャンキング部322を呼び出して、チャンク1302をさらに細かくチャンキングする。サブチャンクの個数をdとかく。図１３の例ではチャンク1302がd=5個にチャンキングされて、サブチャンク1304（S1,...,S5）が得られた。
（２）サブチャンク1304それぞれについてハッシュ値を計算する。サブチャンクSiのハッシュ値をHash(Si)とかく（i=1,...,d）。
（３）すべてのハッシュ値Hash(Si)（i=1,...,d）の論理和1306をとる。ハッシュ値Hash(S1)とHash(S2)の論理和のkビット目は、Hash(S1)のkビット目、Hash(S2)のkビット目のいずれかが1である場合1となり、両方とも0となる場合に限り0となる。
（４）ハッシュ関数Hashの出力をLビットとすると、（３）で長さLのビット列が得られる。図１３の例では、32ビットのビット列が得られている。これがブルームフィルタである。
【０１００】
もし共通するサブチャンクがあった場合、同じ位置のビットが1となるため、一致するビットの個数を数えればチャンクの類似度を近似的に求めることができる。具体的に説明すると、ブルームフィルタB=(b1,...,bL)とD=(d1,...,dL)が与えれれた場合、類似度は、bi=di（i=1,...,L）となるiの個数をLで割ったもので近似できる。これは、BとDの論理積を取り、0の個数をLで割ったものに一致する。
【０１０１】
前述のファジィハッシュではハッシュ値をすべて特徴量として取っておく必要があるが、このブルームフィルタでは、ハッシュ値の論理和をとっているため、容量を大幅に削減できるというメリットがある。また、論理積の計算は高速であるため、ファジィハッシュよりも高速に類似度を計算できるというメリットもある。しかし、一般に、同じ位置のビットが一致しても、対応するサブチャンクが一致するとは限らない。従って、類似度の精度はファジィハッシュよりも劣る。
【０１０２】
図１２の例では、チャンク1302がサブチャンク1304にチャンキングされてブルームフィルタ1208が求まり、チャンク1312からブルームフィルタ1318が求まっている。ブルームフィルタのビット長は32ビットであり、そのうち一致しないビットが12個あるので（一致しないビットには下線が引いてある）、類似度は近似的に12/32=3/8と求められる。
【０１０３】
ブルームフィルタはデータ量を大幅に削減した特徴量であるが、前述の通り類似度の近似精度が劣る。その精度を向上させたのがトレイトである。チャンクからトレイトを計算する処理の概要を図１４を用いて説明する。図１１と同様、ファイル1400が、図１１で説明したようなチャンキング処理を経てチャンキングされたとする。チャンキング後のファイル1400内のチャンク1402のトレイトは、以下の手順で求められる。
（１）データ送信クライアント20の特徴量算出部324は、チャンキング部322を呼び出して、チャンク1402をさらに細かくチャンキングする。サブチャンクの個数をdとかく。図１４の例ではチャンク1402が5つにチャンキングされて、サブチャンク1404（S1,...,S5）が得られた。
（２）ハッシュ値算出部328は、t種類のハッシュ関数Hash_k（k=1,...,t）を準備しておく。図１４の例ではt=4種類のハッシュ関数Hash_1,...,Hash_4を準備した。特徴量算出部324はハッシュ算出部328を呼び出して、サブチャンクSiそれぞれについてt種類のハッシュ関数を適用してハッシュ値を計算する（i=1,...,d）。図１４の例では、4×5=20個のハッシュ値Hash_1(S1),...,Hash_4(S5)が得られた。
（３）各kについて、d個のハッシュ値Hash_k(Si)（i=1,...,d）の最小値を求める（k=1,...,t）。図１４では、k=1についてHash_1(S2)が最小値1406-1となり、k=4についてHash_4(S4)が最小値1406-4となった。以下求めた最小値を最小ハッシュ値とよぶ。
（４）k個の最小ハッシュ値から先頭bバイトをとる。これを連結した長さk×bのビット列がトレイトである。図１４の例では、最小ハッシュ値1406-1の先頭7ビット1408-1や、最小ハッシュ値1406-4の先頭7ビット1408-4が連結されている。
【０１０４】
類似度の計算は、ブルームフィルタと同様である。すなわち、一致するビットの個数をトレイトのビット長で割ったもので与えられる。
【０１０５】
ハッシュ値の論理和を取る代わりに先頭bビットを抜き出して連結することで、トレイトは、ブルームフィルタよりも精度よく類似度を与えることが知られている。詳細については非特許文献６参照のこと。
【０１０６】
本実施例の第二の特徴は、復元バイト列を用いて、データ送信クライアント20が転送しようとしているチャンクを、データベースサーバ30側で復元する点である。以下、図１５、１６を用いて、チャンクから復元バイト列を求める処理、および復元バイト列を用いてチャンクを復元する処理について説明する。
【０１０７】
まず、上記処理のベースとなる誤り訂正技術の概要について説明する。誤り訂正にはブロック符号、畳込み符号などさまざまな方式が知られているが、本実施例ではブロック符号を用いる。ブロック符号とは、送信しようとする情報から検査バイト列を計算し、これを付加して冗長性を加えることで、受信側でなるべく誤りのない復号を可能にするものである。一般に誤り訂正技術は、検査バイト列を求める誤り訂正符号化処理と、送信した情報に生じた誤りを訂正する誤り訂正処理のペアで構成される。
【０１０８】
ブロック符号の特徴は、送信しようとする情報や検査バイト列が固定長である点である。すなわち、送信しようとする情報をkバイト、検査バイト列をhバイトとすると、kやhの組み合わせは、用いるブロック符号の種類によって固定される。これは畳み込み符号のような誤り訂正方式とは異なる点である。一般に、検査バイト列のバイト長hを増やすほど、訂正可能なバイト数が増大する。ただし、その分送信しなければならない総データ（k+hバイト）も増大し、ネットワーク負荷がかかることになる。
【０１０９】
ブロック符号で最も誤り訂正能力が高いものの一つとして、リードソロモン符号が知られている。リードソロモン符号を用いると、検査バイト列をhバイトとした場合、送信する総データ（k+hバイト）のうち大体h/2バイトを訂正できることが知られている。すなわち、総データ中h/2バイトの値がネットワーク上などで変化したとしても、誤り訂正して元のバイト列を復元することができる。一方、h/2バイト以上変化した場合は、誤り訂正に失敗して何も復元できず、誤り訂正に失敗したという結果が返される。
【０１１０】
本来誤り訂正は、ネットワークなどで生じた誤りを訂正するために考え出された技術であるが、本実施例においては、クライアントが転送しようとするチャンクAとサーバ側で所有する類似チャンクA'の違いを誤りだとみなして、A'からAを復元するために誤り訂正技術を用いる。
【０１１１】
図１５は、チャンクから復元バイト列を求める処理の概要を例示する図である。データ送信クライアント20の復元バイト列算出部326は、チャンク1500から復元バイト列1512を以下の手順で求める。
（１）あらかじめ誤り訂正符号化処理1510のパラメータ等を、設定部330を介して決めておく。当該パラメータ等は自由に変更することができるが、データベースサーバ30のチャンク復元部424が実行する誤り訂正処理と合わせておく必要がある。誤り訂正符号化処理と誤り訂正処理はペアであり、異なるパラメータ設定では誤り訂正処理を正しく実行できないためである。以下、誤り訂正符号化処理1510の入力長をkとする。
（２）チャンク1500をkバイトごとに分割する。チャンク1500のバイト長がkの倍数でない場合、末尾にパディング1504を付加して、長さをkの倍数にする。パディング1504の中身はなんでも良いが、チャンク復元部424と生成方式を共通にし、同一のパディングが得られるようにする必要がある。この分割処理により、分割後チャンク1502が得られる。例えば図１５では、チャンク1500が、パディング1504を付加して6個のkバイト列に分割されている。
（３）分割後チャンク1502内のkバイト列それぞれについて、誤り訂正符号化処理1510を施して検査バイト列を求める。検査バイト列の長さをhとかく。求めた検査バイト列を連結して、復元バイト列1512を得る。図１５の例では、復元バイト列1512の長さは6hとなる。
【０１１２】
上述の通り、復元バイト列の長さの約半分のバイト数だけ中身が異なるチャンクを正しく復元できるようになるため、（１）において、低帯域ネットワーク上の送受信の負担とならない程度にできるだけhを大きくとっておくことが好ましい。
【０１１３】
図１６は、復元バイト列を用いてチャンクを復元する処理の概要を例示する図である。データ送信クライアント20から送信されてきた特徴量をもとにチャンク管理テーブルを探索して、類似チャンク1600が見つかったと仮定する。データベースサーバ30のチャンク復元部424は、類似チャンク1600から以下の手順でチャンクの復元を試みる。
（１）あらかじめ誤り訂正符号化処理1510と同一のパラメータを、設定部432を介して決めておく。以下、誤り訂正符号化処理1510の入力長をk、検査バイト列の長さをhとする。
（２）チャンク1600をkバイトごとに分割する。チャンク1600ののバイト長がkの倍数でない場合、末尾にパディング1604を付加して、長さをkの倍数にする。なお、パディング1604の生成方式はデータ送信クライアント20の復元バイト列算出部326でのパディング生成方式と共通にする必要がある。この分割処理により、分割後類似チャンク1602が得られる。例えば図１６では、チャンク1600が、パディング1604を付加して6個のkバイト列に分割されている。
（３）分割後類似チャンク1602内のkバイト列それぞれについて、データ送信クライアント20から受信した復元バイト列をhバイトごとに切り出して、検査バイト列として付加する。分割後類似チャンク1602内のkバイト列すべてに検査バイト列を付加できない場合は、誤り訂正処理を実行することができないので、復元失敗として処理を終了する。また、検査バイト列が余った場合は、データ送信クライアント20が転送しようとしているチャンクを復元できないことは明らかなので、復元失敗として処理を終了する。例えば図１６では、バイト列1606に検査バイト列1608が付加されている。
（４）検査バイト列を付加した長さk+hのバイト列それぞれについて、誤り訂正処理1610を施す。もしどれかのバイト列について誤り訂正が失敗した場合は、復元失敗として処理を終了する。例えば図１６では、誤り訂正処理1610によって、バイト列1606が1616に、検査バイト列1608が1618に訂正されている。
（５）誤り訂正を施したバイト列それぞれの先頭kバイトを切り出して連結する。
（６）末尾からパディング1604を除去して、復元チャンク1620が得られる。これがデータ送信クライアント20が転送しようとしているチャンクの候補となる。
【０１１４】
復元チャンクの管理方式について補足する。本実施例では、図４で説明したように、データベースサーバ30のチャンク復元部424は、復元したチャンクを記憶装置406に格納した。チャンクそのものと比較して復元バイト列は短いため、復元したチャンクを記憶装置406に格納する代わりに、復元前のチャンクのIDと復元バイト列のペアのみを保管しておくことで、記憶装置406への格納データ量を削減することができる。
【０１１５】
以下、復元前のチャンクと復元バイト列のペアを管理するテーブルのことを基礎チャンク管理テーブルとよぶ。図１７は、基礎チャンク管理テーブル1700のデータ構成を例示する図である。基礎チャンク管理テーブル1700は、復元したチャンクのIDを格納するチャンクIDカラム1702と、復元前のチャンクのIDを格納する基礎チャンクIDカラム1704と、復元に必要な復元バイト列を格納する復元バイト列カラム1706などで構成される。
【０１１６】
データ登録部428は、復元したチャンクを記憶装置406に格納するタイミングで、デーブル管理部430を介して基礎チャンク管理テーブル1700を更新する。復元したチャンクにはチャンクIDを発行してチャンク管理テーブル1020やファイル構成チャンク管理テーブル1040を更新するが、実データは記憶装置406に格納しない。
【０１１７】
ファイル構成チャンク管理テーブル1040を介してファイルを構成するチャンクにアクセスしようとした場合、まずは基礎チャンク管理テーブル1700を走査して当該チャンクのチャンクIDがあるかを確認する。もしあれば、復元バイト列を用いてチャンクを復元する。なければ記憶装置406から当該チャンクを取得する。
【０１１８】
例えば、図１７では、チャンクID「0x000001」のチャンクは、チャンクID「0x003523」のチャンクから復元バイト列「f016ed」を用いて復元できることが分かる。図１０のファイル構成チャンク管理テーブル1040によると、ファイル「manual.doc」はチャンクID「0x000001」のチャンクなどで構成されるので、ファイル「manual.doc」にアクセスする場合には、チャンクID「0x000001」のチャンクを生成するために、チャンクID「0x003523」のチャンクから復元バイト列「f016ed」を用いて復元する必要がある。なお、次のチャンク「0x000002」については、基礎チャンク管理テーブル1700に存在しないため、記憶装置406から取得する。
【０１１９】
なお、チャンクの実データが記憶装置406に格納されているかどうか、ファイル構成チャンク管理テーブル1040は新しいカラムを設けて管理してもよい。この場合、基礎チャンク管理テーブル1700へのアクセスが最小限に絞られ、ファイルアクセスにかかる時間を削減することができる。
【０１２０】
以上、図１〜図１７を用いて、本発明のシステム構成及びデータ転送方式について説明した。本実施例によって、データ送信クライアント20が転送しようとしているチャンクと類似するチャンクをデータベースサーバ30で所有していた場合、データベースサーバ30側でそれを再現できて転送が不要となるため、従来方式と比較してよりデータ転送の総時間を短縮することができる。
【符号の説明】
【０１２１】
10：ネットワーク
20、20-1〜20-n：データ送信クライアント
30：データベースサーバ
100：チャンク
200：ファイル
202、202-1〜202-4、212、222：チャンク
204：特徴量
206：復元バイト列
208：ハッシュ値
210：特徴量照合処理
220：チャンク復元処理
230：ハッシュ照合処理
300：内部バス
302：CPU
304：メモリ
306：記憶装置
308：ユーザインターフェース
310：通信インターフェース
32：データ送信部
320：ファイル情報照合部
322：チャンキング部
324：特徴量算出部
326：復元バイト列算出部
328：ハッシュ値算出部
330：設定部
400：内部バス
402：CPU
404：メモリ
406：記憶装置
408：ユーザインターフェース
410：通信インターフェース
42：データ受信部
420：ファイル情報照合部
422：特徴量算出部
424：チャンク復元部
426：ハッシュ値照合部
428：データ登録部
430：ファイルテーブル管理部
432：設定部
502：ファイル情報
506：同一ファイル未所有の通知
522：特徴量
526：類似チャンク所有の通知
530：復元バイト列
534：復元成功の通知
538：ハッシュ値
602：同一ファイル所有の通知
702：類似チャンク未所有の通知
704：チャンク
802：復元失敗の通知
902：ハッシュ値不一致の通知
1000：ファイル管理テーブル
1002：IDカラム
1004：ファイル名カラム
1006：フォルダ名カラム
1008：ファイルサイズカラム
1010：ファイル作成日時カラム
1012：ハッシュ値カラム
1020：チャンク管理テーブル
1022：チャンクIDカラム
1024：特徴量カラム
1026：ハッシュ値カラム
1028：チャンクサイズカラム
1040：ファイル構成チャンク管理テーブル
1042：ファイルIDカラム
1044：ファイル名カラム
1046：フォルダ名カラム
1048：チャンクIDカラム
1050：オフセットカラム
1052：チャンクサイズカラム
1100：ファイル
1102：部分バイト列
1104：走査点
1106-1〜1106-T：バイト値
1120：ラビンフィンガープリント
1140：チャンキング条件
1200、1300、1400：チャンキング後ファイル
1202、1212、1302、1312、1402：チャンク
1204、1214、1304、1404：サブチャンク
1206、1216：ファジィハッシュ
1306：論理和
1308、1318：ブルームフィルタ
1406-1、1406-4：最小ハッシュ値
1408：トレイト
1408-1、1408-4：最小ハッシュ値の先頭bビット
1500：チャンク
1502：分割後チャンク
1504：パディング
1510：誤り訂正符号化処理
1512：復元バイト列
1600：類似チャンク
1602：分割後類似チャンク
1604：パディング
1606：バイト列
1608：検査バイト列
1610：誤り訂正処理
1616：誤り訂正後のバイト列
1618：誤り訂正後の検査バイト列
1620：復元チャンク
1700：基礎チャンク管理テーブル
1702：チャンクIDカラム
1704：基礎チャンクIDカラム
1706：復元バイト列カラム
【図１】
2013190891.tif 000003
【図２】
2013190891.tif 000004
【図３】
2013190891.tif 000005
【図４】
2013190891.tif 000006
【図５】
2013190891.tif 000007
【図６】
2013190891.tif 000008
【図７】
2013190891.tif 000009
【図８】
2013190891.tif 000010
【図９】
2013190891.tif 000011
【図１０】
2013190891.tif 000012
【図１１】
2013190891.tif 000013
【図１２】
2013190891.tif 000014
【図１３】
2013190891.tif 000015
【図１４】
2013190891.tif 000016
【図１５】
2013190891.tif 000017
【図１６】
2013190891.tif 000018
【図１７】
2013190891.tif 000019