(57)【要約】【課題】本発明は、大容量ファイルでも処理時間を短縮し、コリジョン判定の信頼性が高いファイル管理装置を提供する。【解決手段】ファイル管理装置１は、元ファイルを記憶する記憶手段１１と、修正された元ファイルが入力されるファイル入力手段１２と、元ファイルから選択データを選択するデータ選択手段１３と、選択データを圧縮してからダイジェスト値を算出するダイジェスト値演算手段１４ａ〜１４ｍと、ダイジェスト値出力手段１５ａ〜１５ｍと、比較データのダイジェスト値を取得するダイジェスト値取得手段１６と、選択データのダイジェスト値と比較データのダイジェスト値が一致するか否かを判定すると共に、階層的なコリジョン判定を行うダイジェスト値判定手段１７ａ〜１７ｍと、差分データ出力手段１８とを備える。【選択図】図２
2010272038.tif 000002
【特許請求の範囲】
【請求項１】
修正対象の元ファイルと、当該元ファイルを複製した複製ファイルとが一致するか否かを判定するファイル管理装置であって、
前記元ファイルをブロック化すると共に、前記元ファイルのブロック内で異なる位置の選択データを選択するように予め設定された規則に基づいて、前記元ファイルから前記選択データを選択し、当該選択データを予め設定された並列数で並列に出力するデータ選択手段と、
前記選択データが入力され、当該選択データを圧縮すると共に、圧縮した前記選択データのダイジェスト値を算出し、当該選択データのダイジェスト値と、前記元ファイル内で当該選択データが含まれる前記ブロックの位置を示す選択データ位置情報とを出力する複数のダイジェスト値演算手段と、
少なくとも前記規則を用いて予め生成された、前記複製ファイルのブロック内で異なる位置の比較データのダイジェスト値と、前記複製ファイル内で当該比較データが含まれるブロックの位置を示す比較データ位置情報とを取得するダイジェスト値取得手段と、
前記ブロック毎に、互いに対応する位置で前記比較データのダイジェスト値と前記選択データのダイジェスト値とが一致するか否かを判定する複数のダイジェスト値判定手段と、を備え、
前記ダイジェスト値判定手段は、全ての前記ダイジェスト値判定手段によって前記比較データのダイジェスト値と前記選択データのダイジェスト値とが一致すると判定された場合、前記元ファイルと前記複製ファイルとの前記ブロックが一致すると判定し、何れかの前記ダイジェスト値判定手段によって前記比較データのダイジェスト値と前記選択データのダイジェスト値とが一致しないと判定された場合、前記元ファイルと前記複製ファイルとの前記ブロックが一致しないと判定することを特徴とするファイル管理装置。
【請求項２】
前記複数のダイジェスト値演算手段は、前記選択データをチェックサムにより圧縮すると共に、圧縮した前記選択データのダイジェスト値をハッシュ関数により算出することを特徴とする請求項１に記載のファイル管理装置。
【請求項３】
前記何れかのダイジェスト値判定手段によって前記元ファイルと前記複製ファイルとの前記ブロックが一致しないと判定された場合、前記選択データ位置情報に基づいて、一致しないと判定された前記ブロックを差分データとして前記元ファイルから読み出して、当該差分データを出力する差分データ出力手段を備えることを特徴とする請求項１又は請求項２に記載のファイル管理装置。
【請求項４】
前記元ファイルを記憶する記憶手段を備え、
前記ダイジェスト値演算手段は、
前記選択データをチェックサムすると共に、前記チェックサムした選択データを予め前記記憶手段に書き込むチェックサム部と、
前記記憶手段に書き込まれた前記選択データを参照し、ＳＨＡ−１、ＳＨＡ−２、ＭＤ１、ＭＤ２、ＭＤ３、ＭＤ４又はＭＤ５の何れかである前記ハッシュ関数によって、前記選択データのダイジェスト値を算出するダイジェスト値演算部と、を備えることを特徴とする請求項２又は請求項３に記載のファイル管理装置。
【請求項５】
修正対象の元ファイルと、当該元ファイルを複製した複製ファイルとが一致するために、コンピュータを、
前記元ファイルをブロック化すると共に、前記元ファイルのブロック内で異なる位置の選択データを選択するように予め設定された規則に基づいて、前記元ファイルから前記選択データを選択し、当該選択データを予め設定された並列数で並列に出力するデータ選択手段、
前記選択データが入力され、当該選択データを圧縮すると共に、圧縮した前記選択データのダイジェスト値を算出し、当該選択データのダイジェスト値と、前記元ファイル内で当該選択データが含まれる前記ブロックの位置を示す選択データ位置情報とを出力する複数のダイジェスト値演算手段、
少なくとも前記規則を用いて予め生成された、前記複製ファイルのブロック内で異なる位置の比較データのダイジェスト値と、前記複製ファイル内で当該比較データが含まれるブロックの位置を示す比較データ位置情報とを取得するダイジェスト値取得手段、
前記ブロック毎に、互いに対応する位置で前記比較データのダイジェスト値と前記選択データのダイジェスト値とが一致するか否かを判定する複数のダイジェスト値判定手段、として機能させ、
前記ダイジェスト値判定手段は、全ての前記ダイジェスト値判定手段によって前記比較データのダイジェスト値と前記選択データのダイジェスト値とが一致すると判定された場合、前記元ファイルと前記複製ファイルとの前記ブロックが一致すると判定し、何れかの前記ダイジェスト値判定手段によって前記比較データのダイジェスト値と前記選択データのダイジェスト値とが一致しないと判定された場合、前記元ファイルと前記複製ファイルとの前記ブロックが一致しないと判定することを特徴とするファイル管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、修正対象の元ファイルと、元ファイルを複製した複製ファイルとが一致するか否かを判定するファイル管理装置及びそのプログラムに関する。
【背景技術】
【０００２】
従来から、例えば、ファイルをバックアップするために、ネットワークを介して接続された２個の装置でそれぞれファイルを記憶し、一方の装置でファイルが修正されたときは、他方の装置が記憶するファイルを同期させることが行われている。近年、処理速度の高速化及び記憶容量の増加にともない、ファイルの容量が増加し続けている。特に、ＨＤＴＶ(High Definition TeleVision)等の大容量のファイルを扱う際、複数の装置間で大容量のファイルを同期するため、及び、送信結果を確認するため、小さなダイジェスト値が用いられることがある。なお、ファイルが同期しているとは、複数のファイルのデータが一致している状態を指す。
【０００３】
従来から、このダイジェスト値の生成には、ＳＨＡ（Secure Hash Algorithm）−１、ＭＤ（Message Digest Algorithm）５等のハッシュ関数が用いられている。ハッシュ関数を用いる理由としては、別々のデータから同じダイジェスト値が生成されるコリジョンの発生率が低いこと、固定長のダイジェスト値にデータを圧縮できること、ダイジェスト値の分布が一様であること、及び、処理が比較的高速であることがあげられる。
【０００４】
ここで、大容量のファイルにハッシュ関数を適用すると、ハッシュ演算に要する時間が、ダイジェスト値を用いないでファイルを送信する時間、及び、ファイルを記録する時間よりも大きくなることがある。例えば、約１時間のＨＤＴＶの番組に相当する５０Ｇバイトのファイルを、１Ｇビット／秒のネットワークで接続された２個の装置間で同期する場合を考える。この場合、ダイジェスト値を用いないでファイルを送信し、その差分を書き換える方法では、ファイルの送信が、５０Ｇバイト×８ビット／（１Ｇビット／秒）＝４００秒かかる。一方で、パーソナルコンピュータ（Ｐｅｎｔｉｕｍ（登録商標）プロセッサ、クロック周波数：３ＧＨｚ）で５０ＧバイトのファイルをＳＨＡ−１でハッシュ演算した場合、約１０００秒かかる。このように、ハッシュ演算が、ファイルの送信時間以上となり、ダイジェスト値を用いる利点が無くなってしまう。さらに、比較処理の時間、及び、装置への記録時間を考慮すると、従来に比べて、ハッシュ演算を１０倍以上、高速化する必要がある。そこで、ハッシュ演算を高速化するために、並列処理（非特許文献１参照）、アセンブラ化（非特許文献２参照）、事前処理（特許文献１参照）、及び、ハードウェア化（非特許文献３参照）といった技術が提案されている。
【０００５】
また、ハッシュ演算の際、ダイジェスト値のコリジョンの発生確率をゼロにすることはできない。従って、高い信頼性が要求される用途、例えば、番組の内容を比較する用途では、エラーを許容できないため、コリジョンを低減することも重要である。この場合、ダイジェスト値と元データとを記録しておき、コリジョン発生時には、ダイジェスト値を用いずに、ファイルをそのまま用いる技術が提案されている（非特許文献４参照）。
【０００６】
［従来のファイル同期システムの概要］
以下、図９を参照し、従来のファイル同期システム９００について、具体例をあげて説明する。図９に示すように、ファイル同期システム９００は、送信ノード９Ａが記憶する元ファイルと、受信ノード９Ｂが記憶する複製ファイルとを同期させるものであり、送信ノード９Ａと、受信ノード９Ｂとを備える。
【０００７】
まず、ファイル同期システム９００は、送信ノード９Ａが記憶する元ファイルを、受信ノード９Ｂに複製しておく。つまり、送信ノード９Ａが記憶する元ファイルと、受信ノード９Ｂが記憶する複製ファイルとが同期した状態となっている。このとき、送信ノード９Ａが記憶する元ファイルの一部に誤りがあることに気が付いて、ユーザが、この元ファイルを修正したとする。このため、ファイル同期システム９００は、修正した元ファイルに、受信ノード９Ｂが記憶する複製ファイルを同期させる。このような状況を例に、従来の送信ノード９Ａと、受信ノード９Ｂとの構成をそれぞれ、説明する。
【０００８】
＜送信ノードの構成＞
送信ノード９Ａは、元ファイルを記憶すると共に、元ファイルで修正されたデータを含むブロックを差分データとして受信ノード９Ｂに出力するものである。図９に示すように、送信ノード９Ａは、記憶手段９１と、ファイル修正手段９２と、データ入力手段９３と、ダイジェスト値演算手段９４と、ダイジェスト値判定手段９５と、差分データ出力手段９６とを備える。
【０００９】
記憶手段９１は、修正対象の元ファイルを記憶するハードディスク、メモリ等の記憶手段である。
ファイル修正手段９２は、ユーザからマウス、キーボード等の入力手段（不図示）を介して入力された修正指令（例えば、元ファイルの修正内容を含む）に基づいて、記憶手段９１が記憶する元ファイルを修正するものである。
【００１０】
データ入力手段９３は、修正された元ファイルを記憶手段９１から読み出すと共に、この元ファイルをブロック化するものである。また、データ入力手段９３は、元ファイルをブロック化したデータをダイジェスト値演算手段９４に出力し、ブロックの位置を示す位置情報（例えば、ファイルの先頭を基準としたブロックの位置を示すポインタ）をダイジェスト値判定手段９５に出力する。
【００１１】
ダイジェスト値演算手段９４は、データ入力手段９３がブロック化したデータに対して、ＳＨＡ−１、ＭＤ５等のハッシュ演算を行い、そのデータのダイジェスト値を算出するものである。また、ダイジェスト値演算手段９４は、算出したダイジェスト値をダイジェスト値判定手段９５に出力する。
【００１２】
以下、図１０を参照し、従来のファイル同期システム９００における、ブロック化及びハッシュ演算を説明する（適宜図９参照）。図１０（ａ）に示すように、データ入力手段９３は、ファイルを、例えば、コンピュータの標準的なファイルシステムのブロックサイズである４０９６バイト毎にブロック化する。そして、図１０（ｂ）に示すように、ダイジェスト値演算手段９４は、例えば、この４０９６バイトのブロック毎にＳＨＡ−１等のハッシュ演算を行い、１６０ビットのダイジェスト値（ハッシュ値）を求める（図１０（ｃ）参照）。
【００１３】
図９のダイジェスト値判定手段９５は、ダイジェスト値演算手段９４から出力されたダイジェスト値と、ダイジェスト値取得手段９８からのダイジェスト値とを、それらの位置情報に基づいて比較し、両ダイジェスト値が一致するか否かを判定するものである。また、ダイジェスト値判定手段９５は、記憶手段９１が記憶する元ファイルについての不一致部分を含むブロックの位置を示す位置情報と、不一致部分のダイジェスト値とを、受信ノード９Ｂに出力する。そして、ダイジェスト値判定手段９５は、この不一致部分の位置情報を差分データ出力手段９６に出力する。
【００１４】
差分データ出力手段９６は、ダイジェスト値判定手段９５からの不一致部分の位置情報に基づいて、記憶手段９１が記憶する元ファイルのブロックを読み出して、読み出したブロックを差分データとして受信ノード９Ｂに出力するものである。
【００１５】
＜受信ノードの構成＞
受信ノード９Ｂは、複製ファイルを記憶すると共に、元ファイルで修正されたデータを含む差分データで複製ファイルを更新するものである。言い換えると、受信ノード９Ｂは、ファイルのバックアップ装置である。ここで、図９に示すように、受信ノード９Ｂは、記憶手段９７と、ダイジェスト値取得手段９８と、差分データ書込手段９９とを備える。
【００１６】
記憶手段９７は、複製ファイルと、複製ファイルにおけるダイジェスト値を算出したブロックの位置を示す位置情報と、複製ファイルのダイジェスト値（ダイジェスト値）とを記憶するハードディスク、メモリ等の記憶手段である。ここで、記憶手段９７は、複製ファイルの位置情報と複製ファイルのダイジェスト値とが、例えば、システム管理者によって、予め記憶させられる。
【００１７】
ここで、複製ファイルの位置情報は、例えば、複製ファイルの先頭を基準とした、ブロックの位置を示すポインタである。また、複製ファイルのダイジェスト値は、例えば、複製ファイルをブロック化したデータ毎に、前記したファイルと同じハッシュ演算（ＳＨＡ−１やＭＤ−５）を行って算出したダイジェスト値である。
【００１８】
ダイジェスト値取得手段９８は、記憶手段９７から複製ファイルのダイジェスト値と、複製ファイルにおけるダイジェスト値を算出したブロックの位置を示す位置情報とを読み出して、ダイジェスト値判定手段９５に出力するものである。
【００１９】
差分データ書込手段９９は、ダイジェスト値判定手段９５からの不一致部分の位置情報が示す位置において、差分データ出力手段９６からの差分データを、記憶手段９７が記憶する複製ファイルに上書きするものである。
【００２０】
このように、ファイル同期システム９００は、送信ノード９Ａと受信ノード９Ｂとの間で、ダイジェスト値と、位置情報と、不一致部分のデータのみを送受信するだけで良く、ファイルを同期するためのデータ送信時間、及び、データ書き込み時間を短縮することができる。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開２００５−２０８４００号公報
【非特許文献】
【００２２】
【非特許文献１】http://www.soi.wide.ad.jp/class/20060031/slides/41/index_1.html：スライド48
【非特許文献２】http ://www.soi.wide.ad.jp/class/20060031/slides/41/index_1.html：スライド47
【非特許文献３】http://www.cosic.esat.kuleuven.be/publications/article-1031.pdf “Design Methodology for Throughput Optimum Architectures of Hash Algorithms of the MD4-class”Yong Ki Lee et.al. UCLA
【非特許文献４】http://www.kel.co.jp/products/storage/protectier.asp
【発明の概要】
【発明が解決しようとする課題】
【００２３】
しかし、前記した従来技術には、以下のような問題がある。
非特許文献２（アセンブラ化）及び非特許文献３（ハードウェア化）に記載の技術では、ＣＰＵ（Central Processing Unit）、ドライバーソフトウェア、オペレーティングシステム等のシステム環境に依存することになり、汎用性が低くなる。
【００２４】
また、非特許文献１に記載の技術（並列処理）及び特許文献１に記載の発明（事前処理）では、２〜５倍程度しか高速化できず、数十Ｇバイトにも及ぶ大容量のファイルを処理するには不十分である。さらに、図９のファイル同期システム９００では、ダイジェスト値を用いた差分検出にかかる時間が、ファイルを直接上書きする時間よりも長くなり、この技術を用いる意味がない。
【００２５】
非特許文献４に記載の技術（コリジョンの判定）では、同一装置内のファイルやデータだけしか考慮しておらず、複数の装置が記憶するファイル間でコリジョンが発生した場合、元ファイルを伝送する必要があり、送信時間が長く、送信負荷が高くなる。このため、番組制作等の分野では、コリジョン判定処理の高い信頼性を実現してほしいとの強い要望がされている。
【００２６】
そこで、本発明は、大容量ファイルでも処理時間を短縮し、コリジョン判定処理の信頼性が高いファイル管理装置及びそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２７】
前記した課題を解決するため、本願第１発明に係るファイル管理装置は、修正対象の元ファイルと、元ファイルを複製した複製ファイルとが一致するか否かを判定するファイル管理装置であって、データ選択手段と、複数のダイジェスト値演算手段と、ダイジェスト値取得手段と、複数のダイジェスト値判定手段と、を備えることを特徴とする。
【００２８】
かかる構成によれば、ファイル管理装置は、データ選択手段によって、元ファイルをブロック化すると共に、元ファイルのブロック内で異なる位置の選択データを選択するように予め設定された規則に基づいて、元ファイルから選択データを選択し、選択データを予め設定された並列数で並列に出力する。
【００２９】
また、ファイル管理装置は、複数のダイジェスト値演算手段によって、選択データが入力され、選択データを圧縮すると共に、圧縮した選択データのダイジェスト値を算出し、選択データのダイジェスト値と、元ファイル内で選択データが含まれるブロックの位置を示す選択データ位置情報とを出力する。つまり、ファイル管理装置は、ダイジェスト値演算手段によって、高速な関数を用いて選択データを圧縮してから、コリジョンの発生が少ない関数を用いて選択データのダイジェスト値を算出するため、ファイル又はファイルの一部データからそのままダイジェスト値を算出する場合に比べ、演算処理を高速化できる。さらに、ファイル管理装置は、複数のダイジェスト値演算手段によって、選択データのダイジェスト値を並列に算出するため、さらに演算処理を高速化できる。
【００３０】
また、ファイル管理装置は、ダイジェスト値取得手段によって、少なくとも規則（選択データを選択する規則）を用いて予め生成された、複製ファイルのブロック内で異なる位置の比較データのダイジェスト値と、複製ファイル内で比較データが含まれるブロックの位置を示す比較データ位置情報とを取得する。つまり、ファイル管理装置は、ダイジェスト値取得手段によって、選択データのダイジェスト値と同一手順で算出された比較データのダイジェスト値を取得する。そして、ファイル管理装置は、複数のダイジェスト値判定手段によって、ブロック毎に、互いに対応する位置で比較データのダイジェスト値と選択データのダイジェスト値とが一致するか否かを判定する。
【００３１】
また、ファイル管理装置は、ダイジェスト値判定手段によって、全てのダイジェスト値判定手段によって比較データのダイジェスト値と選択データのダイジェスト値とが一致すると判定された場合、元ファイルと複製ファイルとのブロックが一致すると判定し、何れかのダイジェスト値判定手段によって比較データのダイジェスト値と選択データのダイジェスト値とが一致しないと判定された場合、元ファイルと複製ファイルとのブロックが一致しないと判定する。原則として、互いに対応する位置で、修正された元ファイルから生成したダイジェスト値と、修正が反映されていない複製ファイルから生成したダイジェスト値とは、異なる値となり、不一致と正常に判定することができる。しかし、これらダイジェスト値同士が一致するコリジョンが、極めて低い確率で発生する。このため、ファイル管理装置は、全てのダイジェスト値判定手段によって比較データのダイジェスト値と選択データのダイジェスト値とが一致すると判定された場合、元ファイルと複製ファイルとのブロックが一致すると判定し、コリジョンの発生を見逃す事態を防止している（階層的なコリジョン判定処理）。
【００３２】
また、本願第２発明に係るファイル管理装置は、複数のダイジェスト値演算手段が、選択データをチェックサムにより圧縮すると共に、圧縮した選択データのダイジェスト値をハッシュ関数により算出することを特徴とする。
【００３３】
また、本願第３発明に係るファイル管理装置は、何れかのダイジェスト値判定手段によって元ファイルと複製ファイルとのブロックが一致しないと判定された場合、選択データ位置情報に基づいて、一致しないと判定されたブロックを差分データとして元ファイルから読み出して、差分データを出力する差分データ出力手段を備えることを特徴とする。
【００３４】
かかる構成によれば、ファイル管理装置は、差分データ出力手段によって、ファイルよりも小さい容量の差分データを受信ノードに出力する。これによって、ファイル管理装置は、データを送信する時間を短縮できる。
【００３５】
また、本願第４発明に係るファイル管理装置は、元ファイルを記憶する記憶手段を備え、ダイジェスト値演算手段は、選択データをチェックサムすると共に、チェックサムした選択データを予め記憶手段に書き込むチェックサム部と、記憶手段に書き込まれた選択データを参照し、ＳＨＡ−１、ＳＨＡ−２、ＭＤ１、ＭＤ２、ＭＤ３、ＭＤ４又はＭＤ５の何れかであるハッシュ関数によって、選択データのダイジェスト値を算出するダイジェスト値演算部と、を備えることを特徴とする。かかる構成によれば、ファイル管理装置は、ダイジェスト値演算手段によって、選択データを事前に作成する。
【００３６】
また、前記した課題を解決するため、本願第５発明に係るファイル管理プログラムは、修正対象の元ファイルと、元ファイルを複製した複製ファイルとが一致するか否かを判定するために、コンピュータを、データ選択手段、複数のダイジェスト値演算手段、ダイジェスト値取得手段、複数のダイジェスト値判定手段、として機能させることを特徴とする。
【００３７】
かかる構成によれば、ファイル管理プログラムは、データ選択手段によって、元ファイルをブロック化すると共に、元ファイルのブロック内で異なる位置の選択データを選択するように予め設定された規則に基づいて、元ファイルから選択データを選択し、選択データを予め設定された並列数で並列に出力する。
【００３８】
また、ファイル管理プログラムは、複数のダイジェスト値演算手段によって、選択データが入力され、選択データを圧縮すると共に、圧縮した選択データのダイジェスト値を算出し、選択データのダイジェスト値と、元ファイル内で選択データが含まれるブロックの位置を示す選択データ位置情報とを出力する。つまり、ファイル管理プログラムは、ダイジェスト値演算手段によって、高速な関数を用いて選択データを圧縮してから、コリジョンの発生が少ない関数を用いて選択データのダイジェスト値を算出するため、ファイル又はファイルの一部データからそのままダイジェスト値を算出する場合に比べ、演算処理を高速化できる。さらに、ファイル管理プログラムは、複数のダイジェスト値演算手段によって、選択データのダイジェスト値を並列に算出するため、さらに演算処理を高速化できる。
【００３９】
また、ファイル管理プログラムは、ダイジェスト値取得手段によって、少なくとも規則（比較データを選択する規則）を用いて予め生成された、複製ファイルのブロック内で異なる位置の比較データのダイジェスト値と、複製ファイル内で比較データが含まれるブロックの位置を示す比較データ位置情報とを取得する。つまり、ファイル管理プログラムは、ダイジェスト値取得手段によって、選択データのダイジェスト値と同一手順で算出された比較データのダイジェスト値と、比較データ位置情報とを取得する。そして、ファイル管理プログラムは、複数のダイジェスト値判定手段によって、選択ブロック毎に、互いに対応する位置で比較データのダイジェスト値と選択データのダイジェスト値とが一致するか否かを判定する。
【００４０】
また、ファイル管理プログラムは、ダイジェスト値判定手段によって、全てのダイジェスト値判定手段によって比較データのダイジェスト値と選択データのダイジェスト値とが一致すると判定された場合、元ファイルと複製ファイルとのブロックが一致すると判定し、何れかのダイジェスト値判定手段によって比較データのダイジェスト値と選択データのダイジェスト値とが一致しないと判定された場合、元ファイルと複製ファイルとのブロックが一致しないと判定する。原則として、互いに対応する位置で、修正された元ファイルから生成したダイジェスト値と、修正が反映されていない複製ファイルから生成したダイジェスト値とは、異なる値となり、不一致と正常に判定することができる。しかし、これらダイジェスト値同士が一致するコリジョンが、極めて低い確率で発生する。このため、ファイル管理プログラムは、全てのダイジェスト値判定手段によって比較データのダイジェスト値と選択データのダイジェスト値とが一致すると判定された場合、元ファイルと複製ファイルとのブロックが一致すると判定し、コリジョンの発生を見逃す事態を防止している。
【発明の効果】
【００４１】
本発明によれば、以下のような優れた効果を奏する。
本願第１，５に係る発明によれば、高速な関数を用いて選択データを圧縮してからコリジョンの発生が少ない関数を用いて選択データのダイジェスト値を算出する処理を並列に行うため、大容量ファイルでも処理時間を短縮できる。また、本願第１，５に係る発明によれば、全てのダイジェスト値判定手段によって比較データのダイジェスト値と選択データのダイジェスト値とが一致すると判定された場合、元ファイルと複製ファイルとのブロックが一致すると判定するので、コリジョンの発生を見逃す事態を防止でき、コリジョン判定の信頼性が高い。
【００４２】
本願第２に係る発明によれば、高速なチェックサムで圧縮してから選択データのダイジェスト値を算出するため、演算処理をより高速化でき、ファイルをすばやく同期させることができる。
本願第３に係る発明によれば、データを送信する時間を短縮できるため、ファイルをすばやく同期させることができる。
本願第４に係る発明によれば、選択データを事前に作成するので、ダイジェスト値の判定処理を行うときに選択データをチェックサムする必要がなく、処理時間をより短縮できる。
【図面の簡単な説明】
【００４３】
【図１】本発明の第１実施形態に係るファイル管理装置を用いた番組送出システムの概略図である。
【図２】本発明の第１実施形態に係るファイル管理装置の構成を示すブロック図である。
【図３】本発明の第１実施形態において、データのブロック化及びダイジェスト値を説明する図である。
【図４】図２のダイジェスト値演算手段の構成を示すブロック図である。
【図５】本発明の第１実施形態において、元ファイルと複製ファイルとの比較を説明する図である。
【図６】図２のファイル管理装置の動作を示すフローチャートである。
【図７】本発明の変形例２に係るファイル管理装置の構成を示すブロック図である。
【図８】本発明の参考例１に係るファイル管理装置の構成を示すブロック図である。
【図９】従来のファイル同期システムの構成を示すブロック図である。
【図１０】従来のファイル同期システムにおいて、データのブロック化及びダイジェスト値を説明する図である。
【発明を実施するための形態】
【００４４】
以下、本発明の実施形態について、適宜図面を参照しながら詳細に説明する。なお、同一の機能を有する手段には同一の符号を付し、説明を省略した。
【００４５】
［番組送出システムの概略］
以下、図１を参照し、本発明の第１実施形態に係るファイル管理装置１を用いた番組送出システム１００の概略について説明する。番組送出システム（ファイル同期システム）１００は、放送番組を内容とする番組ファイルを記憶・管理すると共に、放送の際、この番組ファイルを送出するものである。図１に示すように、番組送出システム１００は、編集機Ｃと、登録端末（ファイル管理装置）１と、登録サーバ（受信ノード）２とを備える。
【００４６】
編集機Ｃは、オペレータの操作によって番組ファイルの編集（修正）を行うものであり、例えば、マウス、キーボード等の入力手段と、ディスプレイ等の表示手段とを備え、番組編集ソフトウェアがインストールされたコンピュータである。そして、編集された番組ファイルは、リムーバブルメディアＭを介して、登録端末１に登録（記憶）される。
【００４７】
登録端末１は、番組ファイル（元ファイル）を、登録サーバ２に登録（記憶）するための端末装置である。ここで、登録端末１は、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）、インターネット等のネットワークを介して、登録サーバ２に接続されている。なお、登録端末１が、図２のファイル管理装置１に対応する。
【００４８】
登録サーバ２は、番組ファイル（複製ファイル）を記憶・管理すると共に、放送の際、この番組ファイルを送出するものである。そして、登録サーバ２は、放送時間になると、登録された番組ファイルを送出する。なお、登録サーバ２が、図２の受信ノード２に対応する。
【００４９】
以下、番組送出システム１００においる番組ファイルの登録手順について説明する。
まず、オペレータは、編集機Ｃで編集した番組ファイルを、登録端末１に記憶させる。そして、オペレータは、登録端末１を操作し、登録端末１に記憶させた番組ファイルを、登録サーバ２に送信する。このとき、登録端末１は、登録サーバ２に送信する番組ファイルをそのまま記憶しておく。言い換えると、登録端末１が記憶する番組ファイルと、登録サーバ２が記憶する番組ファイルとが同期した状態となっている。そして、放送時間になると、登録サーバ２は、登録された番組ファイルを送出する。
【００５０】
ここで、オペレータが、編集機Ｃにおいて、放送時間の直前に番組ファイルに字幕を追加した状況を考える。この番組ファイルは、例えば、５０Ｇバイト程度の容量があり、登録端末１から登録サーバ２までの送信時間が非常に長くなる。このため、放送時間の直前に、修正後の番組ファイル全体を登録端末１から登録サーバ２まで送信することは現実的でない。従って、従来技術のように、ハッシュ関数を用いて、登録端末１の修正後の番組ファイルと、登録サーバ２の登録済み番組ファイルとの差分データ（つまり、修正箇所）を検出し、この差分データを登録サーバ２の登録済み番組ファイルに反映させる。このとき、番組送出システム１００では、コリジョンによって差分データを検出できずに、修正が反映されていない番組ファイルが送出される事態を防止しなければならない。そこで、登録端末（ファイル管理装置）１を、以下の構成とした。
【００５１】
（第１実施形態）
［ファイル管理装置の構成］
ファイル管理装置１は、修正対象の元ファイルと、元ファイルを複製した複製ファイルとが一致するか否かを判定するものである。図２に示すように、ファイル管理装置１は、記憶手段１１と、ファイル入力手段１２と、データ選択手段１３と、ｍ個のダイジェスト値演算手段１４ａ〜１４ｍと、ｍ個のダイジェスト値出力手段１５ａ〜１５ｍと、ダイジェスト値取得手段１６と、ｍ個のダイジェスト値判定手段１７ａ〜１７ｍと、差分データ出力手段１８とを備える。
【００５２】
なお、ｍは後記する並列数であり、第１実施形態では、並列数ｍを４として説明する。また、図２では、ダイジェスト値演算手段１４ａ〜１４ｍ、ダイジェスト値出力手段１５ａ〜１５ｍ、及び、ダイジェスト値判定手段１７ａ〜１７ｍの一部の図示を省略した。
【００５３】
記憶手段１１は、修正対象の元ファイルを記憶するハードディスク、メモリ等の記憶手段である。この元ファイルは、その内容及び容量が、特に制限されない。例えば、この元ファイルは、ＨＤＴＶ番組を収録した５０Ｇバイト以上のものである。
【００５４】
ファイル入力手段１２は、元ファイルが入力されるものである。そして、ファイル入力手段１２は、入力された元ファイルを記憶手段１１に記憶する。
【００５５】
データ選択手段１３は、記憶手段１１が記憶する元ファイルをブロック化すると共に、元ファイルから異なる位置の選択データを選択するように予め設定された規則に基づいて、記憶手段１１が記憶するファイルから選択データを選択し、選択データを予め設定された並列数ｍで並列にダイジェスト値演算手段１４ａ〜１４ｍに出力するものである。ここで、データ選択手段１３は、図３（ａ）に示すように、例えば、元ファイルを４Ｋバイト×４＝１６Ｋバイト（コンピュータのファイルシステムのブロックサイズ×並列数ｍ）毎にブロック化する。
【００５６】
＜規則の詳細＞
以下、本発明における規則の詳細を説明する。この規則（サンプリングルールデータ）とは、各ブロックから、選択データをサンプリングする方法を定義するものである。この規則は、例えば、サンプリングの周期であり並列数であるｍ及びその位相０，１，２，・・・，ｍ−１、式、数列、乱数等で任意に定義することができる。例えば、この規則は、ダイジェスト値演算手段１４ａに出力する選択データを、並列数ｍ個毎に選択するものである（例えば、図３（ｂ）参照）。また、例えば、この規則は、並列数ｍが２の場合、奇数番目の選択データをダイジェスト値演算手段１４ａに出力し、偶数番目の選択データをダイジェスト値演算手段１４ｂに出力するものである。さらに、例えば、この規則としては、周期的なサンプリングの他、選択データをランダムにサンプリングするものがある。この場合、乱数の種類と初期値とでサンプリングルールを定義し、又は、乱数のテーブルを用いてサンプリングルールを定義する。なお、位相とは、並列数ｍ個毎に選択するときの選択データ同士の位置のずれを意味する。
【００５７】
ここで、ダイジェスト値を演算するときのコリジョンの発生率は、演算対象となる選択データの分布に依存する。特に、後記するチェックサム等の処理においては、選択データの分布依存性が大きいことが知られている。このため、本発明では、選択データの分布特性が維持されている必要がある。そこで、本発明では、ランダムサンプリング理論に則ってダイジェスト演算に用いる選択データを選択することとした。具体的には、ランダムサンプリング理論では、母数Ｎと信頼度εとを与えると、下記式（１）によって、サンプル数ｎの下限を算出することができる。
【００５８】
ｎ≧Ｎ／（（ε／ｋ）２×（Ｎ−１）／Ｐ（１−Ｐ）＋１）・・・式（１）
なお、式（１）では、ｎがサンプル数を示し、Ｎが母数を示し、εが信頼度を示し、ｋ，Ｐが係数を示す。
【００５９】
例えば、母数Ｎを４０９６（コンピュータのファイルシステムのブロックサイズ）、信頼度εを０．０５，係数ｋを１．９６、及び、係数Ｐを０．５とした場合、サンプル数ｎは３５１以上となる。そして、母数Ｎ４０９６／サンプル数ｎ３５１より、約１１．６となり、最大１２個中の１個データを選択しても、選択データの分布特性を維持できることになる。
【００６０】
このため、選択データの一意性を保証するために、前記した規則を導入した。つまり、この規則は、このランダムサンプリングにおけるサンプリングパターンを定義している。例えば、並列数ｍが４の場合、この規則は、ファイルの先頭を基準とし、１番目，５番目，・・・，αｍ＋１番目の選択データを１番目のダイジェスト値演算手段１４ａに出力すると定義できる（αはファイルのサイズを選択データのサイズで除算した商）。また、例えば、この規則は、ファイルの先頭を基準とし、２番目，６番目，・・・，αｍ＋２番目の選択データを２番目のダイジェスト値演算手段１４ｂに出力すると定義できる。そして、例えば、この規則は、ファイルの先頭を基準とし、３番目，７番目，・・・，αｍ＋３番目の選択データを３番目のダイジェスト値演算手段（不図示）に出力すると定義できる。さらに、例えば、この規則は、ファイルの先頭を基準とし、４番目，８番目，・・・，αｍ＋４番目の選択データを４番目のダイジェスト値演算手段１４ｍに出力すると定義できる。
【００６１】
言い換えると、データ選択手段１３は、この規則に従って、図３（ｃ）に示すように、ブロック毎に、インデックスが１の選択データをダイジェスト値演算手段１４ａに出力し、インデックスが２の選択データをダイジェスト値演算手段１４ｂに出力する。また、同様に、データ選択手段１３は、この規則に従って、インデックスが３の選択データを３番目のダイジェスト値演算手段１４ｂに出力し、インデックスが４の選択データをダイジェスト値演算手段１４ｍに出力する。
【００６２】
ダイジェスト値演算手段１４ａは、図３（ｃ）に示すように、データ選択手段１３からインデックスが１の選択データが入力され、この選択データをチェックサムすると共に、チェックサムした選択データのダイジェスト値をハッシュ関数により算出し、選択データのダイジェスト値と、元ファイル内で選択データが含まれるブロックの位置を示す選択データ位置情報（例えば、元ファイルでのブロック♯１）とをダイジェスト値出力手段１５ａに出力するものである。
【００６３】
＜ダイジェスト値演算手段の詳細＞
以下、図４を参照し、ダイジェスト値演算手段１４ａの詳細について、説明する（適宜図２，３参照）。ここで、ダイジェスト値演算手段１４ａは、図２に示すように、データ入力部１４１と、データ削除入力部１４２と、データ圧縮部１４３と、ダイジェスト値入力部１４４と、ダイジェスト値演算部１４５とを備える。なお、データ圧縮部１４３が、請求項に記載のチェックサム部に相当する。
【００６４】
データ入力部１４１は、インデックスが１の選択データを、例えば、同期化処理の最小単位で再度ブロック化するものである（図３（ｃ）では、１Ｋバイトのブロックを４個）。また、データ入力部１４１は、元ファイル内で選択データが含まれるブロックの位置を示す選択データ位置情報（例えば、ファイルの先頭を基準としたこのブロックの位置を示すポインタ）を生成する。そして、データ入力部１４１は、この選択データをデータ削除入力部１４２に出力し、選択データ位置情報をダイジェスト値出力手段１５ａに出力する。
【００６５】
データ削除入力部１４２は、データ入力部１４１からの選択データを、ダイジェスト値を演算する単位で再度ブロック化するものである。ここで、データ削除入力部１４２は、例えば、コンピュータのファイルシステムのブロックサイズを、ダイジェスト値を算出するブロック個数で割った値でブロック化する（図３（ｃ）では、２５６バイトのブロックを４×４＝１６個）。そして、データ削除入力部１４２は、この選択データをデータ圧縮部１４３に出力する。
【００６６】
データ圧縮部１４３は、データ削除入力部１４２からの選択データを、チェックサムするものである。例えば、データ圧縮部１４３は、チェックサムとして、選択データを２バイト毎に区切ると共に、この２バイトのデータが示す数値（１６進数）の総和を算出する。また、例えば、データ圧縮部１４３は、チェックサムとして、選択データの各ビットに対して、ＯＲ（論理和）又はＥＯＲ（排他的論理和）の演算を行っても良い。ここで、図３（ｄ）に示すように、データ圧縮部１４３は、チェックサムによって、２５６バイトの各選択データを３２ビットとする。そして、データ圧縮部１４３は、チェックサムした選択データをダイジェスト値入力部１４４に出力する。
【００６７】
ダイジェスト値入力部１４４は、データ圧縮部１４３からの選択データを、ハッシュ演算の単位で再度ブロック化するものである。例えば、図３（ｅ）に示すように、ダイジェスト値入力部１４４は、３２ビットの選択データを１６個連結させた５１２ビットのブロックにブロック化する。そして、ダイジェスト値入力部１４４は、この選択データを、ダイジェスト値演算部１４５に出力する。
【００６８】
ダイジェスト値演算部１４５は、ハッシュ関数（例えば、ＳＨＡ−１）によって、ダイジェスト値入力部１４４から選択データのダイジェスト値を算出するものである。例えば、図３（ｆ）に示すように、ダイジェスト値演算部１４５は、５１２ビットの選択データから、１６０ビットのダイジェスト値を算出する。そして、ダイジェスト値演算部１４５は、選択データのダイジェスト値をダイジェスト値出力手段１５ａに出力する。
【００６９】
以下、図２に戻り、説明を続ける。
図２のダイジェスト値演算手段１４ｂは、インデックスが２の選択データのダイジェスト値を、ダイジェスト値演算手段１４ａと同様に算出する。また、ダイジェスト値演算手段１４ｍは、インデックスが４の選択データのダイジェスト値を、ダイジェスト値演算手段１４ａと同様に算出する。つまり、ファイル管理装置１は、１個のブロックから、ダイジェスト値演算手段１４ａがインデックス１の選択データのダイジェスト値を算出し、ダイジェスト値演算手段１４ｂがインデックス２の選択データのダイジェスト値を算出し、ダイジェスト値演算手段１４ｍがインデックス４の選択データのダイジェスト値を算出する（合計４個）。なお、選択データをブロック化するサイズは、図３に制限されないことは言うまでもない。
【００７０】
ダイジェスト値出力手段１５ａは、ダイジェスト値演算手段１４ａからの選択データのダイジェスト値と、ダイジェスト値演算手段１４ａからの選択データ位置情報とを、ダイジェスト値判定手段１７ａに出力する。
【００７１】
また、ダイジェスト値出力手段１５ｂは、ダイジェスト値出力手段１５ａと同様に、ダイジェスト値演算手段１４ｂからの選択データのダイジェスト値と選択データ位置情報とを、ダイジェスト値判定手段１７ｂに出力する。さらに、ダイジェスト値出力手段１５ｍは、ダイジェスト値出力手段１５ａと同様に、ダイジェスト値演算手段１４ｍからの選択データのダイジェスト値と選択データ位置情報とを、ダイジェスト値判定手段１７ｍに出力する。
【００７２】
ダイジェスト値取得手段１６は、受信ノード２の記憶手段２１を参照し、複製ファイルのブロック内で異なる位置の比較データのダイジェスト値と、複製ファイル内で比較データが含まれるブロックの位置を示す比較データ位置情報とを取得するものである。なお、受信ノード２は、ファイル管理装置１と同一の規則、チェックサム及びハッシュ関数を用いて予め生成された比較データのダイジェスト値と比較データ位置情報とを記憶手段２１に記憶している。
【００７３】
また、ダイジェスト値取得手段１６は、取得した比較データのダイジェスト値と比較データ位置情報とを、ダイジェスト値判定手段１７ａ〜１７ｍに出力する。例えば、ダイジェスト値取得手段１６は、インデックスが１の比較データのダイジェスト値と、複製ファイルでブロック♯１を示す比較データ位置情報とを、ダイジェスト値判定手段１７ａに出力する。また、例えば、ダイジェスト値取得手段１６は、インデックスが２の比較データのダイジェスト値と、複製ファイルでブロック♯１を示す比較データ位置情報とを、ダイジェスト値判定手段１７ｂに出力する。そして、例えば、ダイジェスト値取得手段１６は、インデックスが３の比較データのダイジェスト値と、複製ファイルでブロック♯１を示す比較データ位置情報とを、３番目のダイジェスト値判定手段（不図示）に出力する。さらに、例えば、ダイジェスト値取得手段１６は、インデックスが４の比較データのダイジェスト値と、複製ファイルでブロック♯１を示す比較データ位置情報とを、ダイジェスト値判定手段１７ｍに出力する。
【００７４】
以下、図５を参照し、ダイジェスト値判定手段１７ａ〜１７ｍ及び差分データ出力手段１８の構成について、説明する（適宜図２参照）。なお、図５では、ＳＤ１１〜１４が、それぞれ、元ファイルのブロック＃１において、インデックスが１〜４の選択データのダイジェスト値を示す。また、ＳＤ２１〜２４が、それぞれ、元ファイルのブロック＃２において、インデックスが１〜４の選択データのダイジェスト値を示す。そして、ＣＤ１１〜１４が、それぞれ、複製ファイルのブロック＃１において、インデックスが１〜４の選択データのダイジェスト値を示す。また、ＣＤ２１〜２４が、それぞれ、複製ファイルのブロック＃２において、インデックスが１〜４の選択データのダイジェスト値を示す。また、図５の例では、元ファイルのブロック＃１において、修正された部分を斜線のハッチングで図示した。
【００７５】
ダイジェスト値判定手段１７ａは、ブロック毎（ここでは、ブロック＃１）に、互いに対応する位置（ここでは、インデックスが１）の比較データのダイジェスト値ＣＤ１１と、選択データのダイジェスト値ＳＤ１１とが一致するか否かを判定するものである。そして、ダイジェスト値判定手段１７ａは、比較データのダイジェスト値ＣＤ１１と、選択データのダイジェスト値ＳＤ１１とが一致しない場合、元ファイルのブロック＃１と複製ファイルのブロック＃１とが一致しないと判定する。この場合、元ファイルのブロック＃１が修正されていることから、比較データのダイジェスト値ＣＤ１１と選択データのダイジェスト値ＳＤ１１とが一致しないので、ダイジェスト値判定手段１７ａは、入力された選択データ位置情報（ここでは、ブロック＃１）と、選択データのダイジェスト値ＳＤ１１とを、差分データ出力手段１８に出力する。
【００７６】
ダイジェスト値判定手段１７ｂは、ダイジェスト値判定手段１７ａと同様に、インデックスが２の選択データのダイジェスト値ＳＤ１２と、インデックスが２の比較データのダイジェスト値ＣＤ１２とが一致するか否かを判定する。また、ダイジェスト値判定手段１７ｍは、ダイジェスト値判定手段１７ａと同様に、インデックスが４の選択データのダイジェスト値ＳＤ１４と、インデックスが４の比較データのダイジェスト値ＣＤ１４とが一致するか否かを判定する。ここで、元ファイルのブロック＃１が修正されているので、比較データのダイジェスト値ＣＤ１１〜ＣＤ１４と選択データのダイジェスト値ＳＤ１１〜ＳＤ１４とが一致しない。つまり、ダイジェスト値判定手段１７ｂ、１７ｍは、ダイジェスト値判定手段１７ａと同様に、ブロック＃１を示す選択データ位置情報と選択データのダイジェスト値ＳＤ１２，ＳＤ１４とを差分データ出力手段１８に出力する。
【００７７】
差分データ出力手段１８は、ダイジェスト値判定手段１７ａ〜１７ｍの何れかによって元ファイルと複製ファイルとのブロックが一致しないと判定された場合、ダイジェスト値判定手段１７ａ〜１７ｍからの選択データ位置情報に基づいて、一致しないと判定されたブロックを差分データとして、記憶手段１１が記憶する元ファイルから読み出して、差分データを出力するものである。つまり、差分データ出力手段１８は、ダイジェスト値判定手段１７ａ〜１７ｍの何れかから選択データ位置情報が入力された場合、この選択データ位置情報が示す位置のブロックを、記憶手段１１が記憶するファイルから差分データとして読み出して、受信ノード２に出力する。この例では、ブロック＃１を示す選択データ位置情報が全てのダイジェスト値判定手段１７ａ〜１７ｍから入力されるので、差分データ出力手段１８は、元ファイルのブロック＃１を差分データとして受信ノード２に出力する。このように、差分データを受信ノード２に出力することで、差分データ出力手段１８は、データを送信する時間を短縮できるため、元ファイルと複製ファイルとをすばやく同期させることができる。なお、差分データ出力手段１８は、差分データと共に、その差分データに対応するブロックの全選択データのダイジェスト値を受信ノード２に出力しても良い。
【００７８】
また、ブロック＃１を終了したら、ファイル管理装置１は、ブロック＃２についても、前記と同様の処理を行う。元ファイルのブロック＃２が修正されていないので、比較データのダイジェスト値ＣＤ２１と選択データのダイジェスト値ＳＤ２１とが一致するので、ダイジェスト値判定手段１７ａは、入力された選択データ位置情報（ここでは、ブロック＃２）を、ダイジェスト値出力手段１５ｂに出力する。なお、ダイジェスト値出力手段１５ｂは、ダイジェスト値判定手段１７ａからの選択データ位置情報を、ダイジェスト値判定手段１７ｂに出力する。
【００７９】
また、ダイジェスト値判定手段１７ｂは、ブロック＃２において、比較データのダイジェスト値ＣＤ２２と、選択データのダイジェスト値ＳＤ２２とが一致するか否かを判定するものである。この場合も、比較データのダイジェスト値ＣＤ２２と選択データのダイジェスト値ＳＤ２２とが一致するので、ダイジェスト値判定手段１７ｂは、選択データ位置情報を、３番目のダイジェスト値出力手段に出力する。なお、３番目のダイジェスト値出力手段は、ダイジェスト値判定手段１７ｂからの選択データ位置情報を、３番目のダイジェスト値判定手段に出力する。以後、３番目のダイジェスト値判定手段及びダイジェスト値判定手段１７ｍは、ダイジェスト値判定手段１７ａと同様の処理を行う。
【００８０】
ここで、一致したブロックを示す選択データ位置情報がダイジェスト値判定手段１７ｍに入力されない場合、ダイジェスト値判定手段１７ａ等の何れかが、選択データのダイジェスト値と比較データのダイジェスト値とが一致しないと判定している。従って、並列数ｍの最後に位置するダイジェスト値判定手段１７ｍは、一致したブロックを示す選択データ位置情報が入力され、かつ、比較データのダイジェスト値ＣＤ２４と、選択データのダイジェスト値ＳＤ２４とが一致した場合、ブロック＃２が一致したと判定する。なお、ファイル管理装置１は、全ブロックが終了するまで前記した処理を継続することは言うまでもない。なお、図２では、ダイジェスト値判定手段１７ｍは、各ブロックが一致したか否かを判定することとしたが、他のダイジェスト値判定手段１７ａ等がこの判定を行っても良いことは言うまでもない。
【００８１】
＜階層的なコリジョン判定処理＞
以下、ダイジェスト値判定手段１７ａ〜１７ｍによる階層的なコリジョン判定処理について、説明する。図５に示すように、元ファイルのブロック＃１が修正された場合、比較データのダイジェスト値ＣＤ１１〜ＣＤ１４と、選択データのダイジェスト値ＳＤ１１〜ＳＤ１４とは、通常、異なる値となる。このとき、コリジョンが発生し、選択データのダイジェスト値ＳＤ１１と、比較データのダイジェスト値ＣＤ１１とが同じ値になった場合を考える。
【００８２】
この場合、ダイジェスト値判定手段１７ａは、選択データのダイジェスト値ＳＤ１１と、比較データのダイジェスト値ＣＤ１１とが一致すると判定し、一致するブロックを示す選択データ位置情報を出力してしまう。しかし、前記したように、ダイジェスト値判定手段１７ｂが、選択データのダイジェスト値ＳＤ１２と、比較データのダイジェスト値ＣＤ１２とが一致しないと判定する。このため、ファイル管理装置１は、前記と同様に、ブロック＃１を差分データとして受信ノード２に出力し、複製ファイルのブロック＃１を更新する。つまり、ファイル管理装置１は、コリジョンが発生した場合でも、全てのダイジェスト値判定手段１７ａ〜１７ｍによって選択データのダイジェスト値ＳＤ１１〜ＳＤ１４と、比較データのダイジェスト値ＣＤ１１〜ＣＤ１４とが一致しないと判定しない限り、差分データを更新する。このため、ファイル管理装置１は、修正されたデータが複製ファイルに反映されない事態を防止し、コリジョン判定処理の信頼性を高めている。
【００８３】
［ファイル管理装置の動作］
以下、図６を参照し、図２のファイル管理装置１の動作について説明する（適宜図２参照）。なお、図６では、記憶手段１１が、修正された元ファイルを記憶していることとして説明する。
【００８４】
まず、ファイル管理装置１は、データ選択手段１３によって、記憶手段１１が記憶する元ファイルをブロック化すると共に、元ファイルから異なる位置の選択データを選択するように予め設定された規則に基づいて、記憶手段１１が記憶するファイルの該当ブロック（ここでは、ブロック＃１）から選択データを選択する。（ステップＳ１１）。
【００８５】
ステップＳ１１の処理に続いて、ファイル管理装置１は、データ選択手段１３によって、ステップＳ１１で選択した選択データを並列数ｍで並列にダイジェスト値演算手段１４ａ〜１４ｍにそれぞれ出力する（ステップＳ１２）。なお、ステップＳ１２では、ファイル管理装置１は、データ選択手段１３によって、選択データ位置情報をダイジェスト値判定手段１７ａ〜１７ｍにそれぞれ出力しても良い。
【００８６】
ステップＳ１２の処理に続いて、ファイル管理装置１は、ダイジェスト値演算手段１４ａ〜１４ｍによって、ステップＳ１２で出力した選択データをチェックサムする（ステップＳ１３）。また、ファイル管理装置１は、ダイジェスト値演算手段１４ａ〜１４ｍによって、ステップＳ１３でチェックサムした選択データのダイジェスト値をハッシュ関数により算出する（ステップＳ１４）。
【００８７】
ステップＳ１４の処理に続いて、ファイル管理装置１は、ダイジェスト値取得手段１６によって、受信ノード２の記憶手段２１を参照し、複製ファイルのブロック内で異なる位置の比較データのダイジェスト値と、複製ファイル内で比較データが含まれるブロックの位置を示す比較データ位置情報とを取得する（ステップＳ１５）。
【００８８】
ステップＳ１５の処理に続いて、ファイル管理装置１は、ダイジェスト値判定手段１７ａ〜１７ｍのそれぞれが、ブロック毎に、ステップＳ１５で出力した比較データのダイジェスト値と、ステップＳ１４で出力した選択データのダイジェスト値とが一致するか否かを判定する。そして、ファイル管理装置１は、全てのダイジェスト値判定手段１７ａ〜１７ｍによって比較データのダイジェスト値と選択データのダイジェスト値とが一致すると判定された場合、元ファイルと複製ファイルとのブロックが一致すると判定する。一方、ファイル管理装置１は、何れかのダイジェスト値判定手段１７ａ〜１７ｍによって比較データのダイジェスト値と選択データのダイジェスト値とが一致しないと判定された場合、元ファイルと複製ファイルとのブロックが一致しないと判定する（ステップＳ１６）。
【００８９】
ブロックが一致しないと判定された場合（ステップＳ１６で不一致）、ファイル管理装置１は、ダイジェスト値判定手段１７ａ〜１７ｍからの選択データ位置情報に基づいて、元ファイルで修正されたデータを含むブロックを差分データとして、記憶手段１１が記憶する元ファイルから読み出して、差分データを出力する（ステップＳ１７）。
【００９０】
一方、ブロックが一致したと判定された場合（ステップＳ１６で一致）、ファイル管理装置１は、ステップＳ１８の処理に進む。そして、ステップＳ１８の処理では、ファイル管理装置１は、元ファイルの全ブロックの判定処理を終了したか否かを判定する。ここで、例えば、ファイル管理装置１は、元ファイルの全ブロック数と、判定済のブロック数とを求める。そして、例えば、ファイル管理装置１は、これら数値が一致しらとき、全ブロックを終了したと判定する（ステップＳ１８）。
【００９１】
全ブロックを終了したと判定された場合（ステップＳ１８でＹｅｓ）、ファイル管理装置１は、処理を終了する。一方、全ブロックを終了していないと判定された場合（ステップＳ１８でＮｏ）、ファイル管理装置１は、次のブロック（例えば、ブロック＃２）を処理するため、ステップＳ１１の処理に戻る。
【００９２】
以上のように、本発明の第１実施形態に係るファイル管理装置１によれば、高速な関数（チェックサム）とコリジョンの発生が少ない関数（ハッシュ関数）とを組み合わせることで、ダイジェスト演算の精度を低下させずに高速化を可能としている。さらに、本発明の第１実施形態に係るファイル管理装置１によれば、規則によって選択データの分布特性を維持しつつ、高速な選択データの圧縮と並列処理とを組み合わせて行うので、さらなる高速化を可能としている。具体的には、本発明の第１実施形態に係るファイル管理装置１によれば、並列数ｍとチェックサムの圧縮率とを乗じた値だけ高速化が可能となる。例えば、本発明の第１実施形態に係るファイル管理装置１によれば、並列数ｍが４で、圧縮率が２０倍となる３２ビットチェックサムの場合、４×２０＝８０倍の高速化が可能となる。本発明の第１実施形態に係るファイル管理装置１によれば、小容量のファイルでも前記した効果を奏するが、例えば、１０Ｇバイト以上の大容量のファイルでは、その効果が顕著なものとなる。
【００９３】
さらに、本発明の第１実施形態に係るファイル管理装置１によれば、全てのダイジェスト値判定手段１７ａ〜１７ｍによって比較データのダイジェスト値と選択データのダイジェスト値とが一致すると判定された場合、元ファイルと複製ファイルとのブロックが一致すると判定する。このように、ダイジェスト値判定手段１７ａ〜１７ｍの何れか１個だけでは見逃すコリジョンを検出できるので、本発明の第１実施形態に係るファイル管理装置１は、コリジョン判定の信頼性が高い。このため、本発明の第１実施形態に係るファイル管理装置１によれば、番組制作等で要求される高い信頼性を実現できる。
【００９４】
なお、本発明の第１実施形態に係るファイル管理装置１を独立した装置として説明したが、これに限定されない。本発明では、一般的なコンピュータの演算装置、記憶装置等のハードウェア資源を、図２の各手段として協調動作させるプログラムによって実現できる。このプログラムは、ネットワークを介して配布しても良く、ＣＤ−ＲＯＭやフラッシュメモリ等の記録媒体に書き込んで配布しても良い。
【００９５】
なお、本発明の第１実施形態では、並列数ｍを４として説明したが、これに限定されない。例えば、本発明では、並列数ｍは、２以上８以下の値にできる。また、本発明の第１実施形態では、図１の番組送出システム１００を例に説明したが、本発明は、これに限定されない。例えば、本発明の第１実施形態に係るファイル管理装置１は、一般的なデータのバックアップ装置として用いることができる。
【００９６】
なお、本発明の第１実施形態では、ダイジェスト値演算手段１４ａ〜１４ｍが、選択データをチェックサムにより圧縮し、選択データのダイジェスト値をハッシュ関数により算出する例を説明したが、これに限定されない。ここで、ダイジェスト値演算手段１４ａ〜１４ｍは、選択データの圧縮に用いる関数がダイジェスト値の算出に用いる関数よりも高速で、ダイジェスト値の算出に用いる関数がコリジョンの発生が少なければ良い。例えば、ダイジェスト値演算手段１４ａ〜１４ｍは、ＭＤ１〜５、ＳＨＡ−１等の高速なハッシュ関数を用いて選択データを圧縮し、ＳＨＡ−２５６、ＳＨＡ−５１２等のハッシュ関数を用いて選択データのダイジェスト値を算出することもできる。
【００９７】
（変形例１：チェックサムの事前演算）
以下、図２，図４を参照し、ファイル管理装置１の変形例１について、第１実施形態に係るファイル管理装置１と異なる点を主に説明する。本変形例に係るファイル管理装置１は、事前に選択データをチェックサムすることが、第１実施形態に係るファイル管理装置１と相違する。
【００９８】
具体的には、図４のデータ圧縮部１４３は、データ削除入力部１４２から選択データをチェックサムする。そして、データ圧縮部１４３は、チェックサムした選択データを、チェックサムファイルとして記憶手段１１に書き込む。このとき、データ圧縮部１４３は、チェックサムファイルが一意となる命名規格に従って、チェックサムファイルを記憶手段１１に書き込むことが好ましい。この命名規格は、例えば、「元ファイル名＋選択データが元ファイルの先頭から何番目に位置するかを示す数値」である。
【００９９】
ダイジェスト値入力部１４４は、記憶手段１１に記憶されたチェックサムファイルを読出し、このチェックサムファイルに含まれる圧縮した選択データを、ハッシュ演算の単位で再度ブロック化する。このとき、ダイジェスト値入力部１４４は、前記した命名規格に基づいて、記憶手段１１から読み出すチェックサムファイルを一意に特定できる。
【０１００】
本変形例に係るファイル管理装置１は、選択データを事前に作成するので、元ファイルと複製ファイルとの一致判定処理を行うときに選択データをチェックサムする必要がなく、処理時間をより短縮できる。なお、本変形例に係るファイル管理装置１は、記憶手段１１に元ファイルが書き込まれたときに、選択データをチェックサムすることが好ましい。また、本変形例に係るファイル管理装置１は、元ファイルが修正されたとき、ファイル管理装置１のＣＰＵ負荷率、インターフェース負荷率等の負荷率が低いとき、又は、一定時間毎といった任意のタイミングで、選択データを事前にチェックサムしても良い。
【０１０１】
（変形例２：階層的なコリジョン判定処理の第２例）
以下、図７を参照し、本発明の変形例２に係るファイル管理装置１の構成について、第１実施形態に係るファイル管理装置１と異なる点を主に説明する。本発明の変形例２では、図２のダイジェスト値判定手段１７ａ〜１７ｍの動作が、第１実施形態に係るファイル管理装置１と相違する。
【０１０２】
ダイジェスト値判定手段１７ａは、ブロック毎に、比較データのダイジェスト値と選択データのダイジェスト値とが一致しないと判定したときに、一致したブロックを示す選択データ位置情報をダイジェスト値判定手段１７ｂに出力する。
【０１０３】
ダイジェスト値判定手段１７ｂは、一致したブロックを示す選択データ位置情報示す位置がダイジェスト値判定手段１７ａから入力された場合、比較データのダイジェスト値と選択データのダイジェスト値とが一致するか否かを判定する。また、ダイジェスト値判定手段１７ｂは、ダイジェスト値判定手段１７ａから選択データ位置情報が入力されない場合、比較データのダイジェスト値と選択データのダイジェスト値とが一致するか否かを判定しない。これによって、本発明の変形例２に係るファイル管理装置１は、後段に配置されたダイジェスト値判定手段１７ｍ等において、無駄な判定処理を削減できる。
【０１０４】
（参考例１：階層的なコリジョン判定処理の第３例）
以下、図８を参照し、本発明の参考例１に係るファイル管理装置１の構成について、第１実施形態に係るファイル管理装置１と異なる点を主に説明する。本発明の参考例１では、選択データと比較データとを一括判定することが、第１実施形態に係るファイル管理装置１と相違する。具体的には、本発明の参考例１に係るファイル管理装置１は、ダイジェスト値判定手段１７ａ〜１７ｍの代わりに、不一致検出・コリジョン排除手段１９を備える。
【０１０５】
不一致検出・コリジョン排除手段１９は、ブロック毎に、全ての選択データのダイジェスト値と比較データのダイジェスト値とが一致するか否かを一括判定するものである。まず、不一致検出・コリジョン排除手段１９は、ダイジェスト値出力手段１５ａ〜１５ｍから、互いに異なる位置の選択データのダイジェスト値と選択データ位置情報とが入力される。また、不一致検出・コリジョン排除手段１９は、ダイジェスト値取得手段１６から、互いに異なる位置の比較データのダイジェスト値と比較データ位置情報とが入力される。
【０１０６】
また、不一致検出・コリジョン排除手段１９は、互いに対応する位置において、選択データのダイジェスト値と比較データのダイジェスト値とが一致するか否かを一括判定する。具体的には、インデックスが１の選択データのダイジェスト値と比較データのダイジェスト値とを比較する。また、不一致検出・コリジョン排除手段１９は、インデックス２〜４の選択データと比較データとについても同様に判定する。
【０１０７】
そして、不一致検出・コリジョン排除手段１９は、全ての選択データのダイジェスト値と比較データのダイジェスト値とが一致する場合、元ファイルと複製ファイルとのブロックが一致すると判定する。一方、何れかの選択データのダイジェスト値と比較データのダイジェスト値とが一致しない場合、元ファイルと複製ファイルとのブロックが一致しないと判定する。この場合、不一致ブロックを示す選択データ位置情報を差分データ出力手段１８に出力する。このように、本発明の参考例１に係るファイル管理装置１は、不一致検出・コリジョン排除手段１９を備えることで、信号の入出力を低減できる。
【０１０８】
（参考例２：チェックサムを行わないファイル管理装置）
以下、図２を参照し、本発明の参考例２に係るファイル管理装置１の構成について、第１実施形態に係るファイル管理装置１と異なる点を主に説明する（適宜図１参照）。本発明の参考例２に係るファイル管理装置１は、チェックサムを行わないことが、第１実施形態に係るファイル管理装置１と相違する。
【０１０９】
具体的には、図２のダイジェスト値演算手段１４ａは、データ圧縮部１４３を備えない構成となる。このため、データ削除入力部１４２は、再度ブロック化した選択データをダイジェスト値入力部１４４に出力する。そして、ダイジェスト値入力部１４４は、データ削除入力部１４２からの選択データを、ハッシュ演算の単位で再度ブロック化し、この選択データを、ダイジェスト値演算部１４５に出力する。
【０１１０】
言い換えると、本発明の参考例２に係るファイル管理装置１は、選択データをそのままハッシュ演算している。このように、本発明の参考例２に係るファイル管理装置１は、高速化の要求がさほど厳しくない場合、信頼性を確保しつつ、簡易な構成となるメリットがある。
【０１１１】
（参考例３：並列処理を行わないファイル管理装置）
以下、図２を参照し、本発明の参考例３に係るファイル管理装置１の構成について、第１実施形態に係るファイル管理装置１と異なる点を主に説明する。本発明の参考例３に係るファイル管理装置１は、並列処理を行わないことが、第１実施形態に係るファイル管理装置１と相違する。
【０１１２】
具体的には、ファイル管理装置１は、各一個のダイジェスト値演算手段１４ａ、ダイジェスト値出力手段１５ａ、及び、ダイジェスト値判定手段１７ａを備える。このため、データ選択手段１３は、元ファイルの各ブロックの先頭から選択データを選択し、この選択データを順次ダイジェスト値判定手段１７ａに出力する。また、ダイジェスト値判定手段１７ａは、階層的なコリジョン判定処理を行わない。このように、本発明の参考例３に係るファイル管理装置１は、信頼性の要求がさほど厳しくない場合、処理速度を高速にしつつ、簡易な構成となるメリットがある。
【０１１３】
（参考例４：受信ノードで判定処理）
以下、図２を参照し、本発明の参考例４に係るファイル管理装置１の構成について、第１実施形態に係るファイル管理装置１と異なる点を主に説明する。本発明の参考例４に係るファイル管理装置１がダイジェスト値の判定処理及び階層的なコリジョン判定処理を行わず、受信ノード２がこれら判定処理行うことが、第１実施形態に係るファイル管理装置１と相違する。
【０１１４】
具体的には、受信ノード２が、ファイル管理装置１の代わりに、ダイジェスト値出力手段１５ａ〜１５ｍ、及び、ダイジェスト値判定手段１７ａ〜１７ｍを備える。これによって、ファイル管理装置１は、ダイジェスト値を演算するだけで判定処理を行う必要がなく、ファイル管理装置１の処理負荷を軽減できるメリットがある。
【０１１５】
（参考例５：受信ノード）
［受信ノードの構成］
以下、参考例５として、受信ノード２の構成について説明する。受信ノード２は、複製ファイルを記憶すると共に、ファイルに含まれる、修正されたデータを含む差分データで複製ファイルを更新するものである。言い換えると、受信ノード２は、ファイル管理装置１のバックアップ装置である。ここで、図２に示すように、受信ノード２は、記憶手段２１と、差分データ書込手段２２とを備える
【０１１６】
記憶手段２１は、複製ファイルと、比較データ位置情報（位置情報）と、比較データのダイジェスト値（ダイジェスト値）とを記憶するハードディスク、メモリ等の記憶手段である。ここで、選択データ及び選択データ位置情報にそれぞれ対応するように、比較データのダイジェスト値と、比較データ位置情報とが、ファイル管理装置１と同一の規則、チェックサム及びハッシュ関数を用いて、予め生成される。そして、記憶手段２１は、これら比較データのダイジェスト値と、比較データ位置情報とを記憶する。
【０１１７】
差分データ書込手段２２は、ファイル管理装置１からの差分データ位置情報において、ファイル管理装置１からの差分データで、記憶手段２１が記憶する複製ファイルを上書きするものである。つまり、差分データ書込手段２２は、ブロック単位で複製ファイルを上書きする。このとき、差分データ書込手段２２は、その差分データに対応するブロックの全選択データのダイジェスト値が入力された場合、比較データのダイジェスト値を選択データのダイジェスト値で上書きしても良い。
【０１１８】
このように、受信ノード２は、差分データがファイル管理装置１から入力されるので、差分データを用いて、記憶手段２１が記憶する複製ファイルを上書きする。これによって、ファイル同期システム１００は、ファイル管理装置１の元ファイルと、受信ノード２の複製ファイルとを同期させることができる。
【符号の説明】
【０１１９】
１  ファイル管理装置
１１  記憶手段
１２  ファイル入力手段
１３  データ選択手段
１４ａ〜１４ｍ  ダイジェスト値演算手段
１５ａ〜１５ｍ  ダイジェスト値出力手段
１６  ダイジェスト値取得手段
１７ａ〜１７ｍ  ダイジェスト値判定手段
１８  差分データ出力手段
１４１  データ入力部
１４２  データ削除入力部
１４３  データ圧縮部（チェックサム部）
１４４  ダイジェスト値入力部
１４５  ダイジェスト値演算部
【図１】
2010272038.tif 000003
【図２】
2010272038.tif 000004
【図３】
2010272038.tif 000005
【図４】
2010272038.tif 000006
【図５】
2010272038.tif 000007
【図６】
2010272038.tif 000008
【図７】
2010272038.tif 000009
【図８】
2010272038.tif 000010
【図９】
2010272038.tif 000011
【図１０】
2010272038.tif 000012