(57)【要約】【課題】新データと旧データ間の差分の検出速度と精度を両立させることができる。【解決手段】本発明にかかる差分検出装置は、旧データと新データの間で一致するデータ部分を検索することで、新データと旧データの差分を検出する差分検出装置である。差分検出装置は、新データと旧データとで大まかに一致するデータ部分を検索する第１の検索部と、その検索結果に基づいて検索条件を決定する検索条件決定部と、決定された検索条件に基づいて、新データと旧データとで詳細に一致するデータ部分を検索して差分を検出する第２の検索部を備える。第１の検索部は、一致するデータ部分を旧データの検索範囲を徐々に広げて検索し、最終的な検索範囲を記録する。検索条件決定部は、検索条件として、新データを分割した複数の区間のそれぞれについて、当該区間における旧データの検索範囲を、当該区間における検索範囲の代表値により近い検索範囲となるように決定する。【選択図】図１
2015141602.tif 000002
【特許請求の範囲】
【請求項１】
旧データと、前記旧データを更新した新データとの間で相互に一致するデータ部分を検索することで、前記新データと前記旧データの差分を検出する差分検出装置であって、
前記新データにおける第１の間隔毎のデータ部分のそれぞれと一致するデータ部分を前記旧データから検索する第１の検索を実施する第１の検索部と、
前記第１の検索部による検索結果に基づいて検索条件を決定する検索条件決定部と、
前記検索条件決定部によって決定された検索条件に基づいて、前記新データにおける前記第１の間隔以下の第２の間隔毎のデータ部分のそれぞれと一致するデータ部分を前記旧データから検索して、前記新データと前記旧データの差分を検出する第２の検索を実施する第２の検索部と、を備え、
前記第１の検索部は、前記第１の検索において、前記新データのデータ部分と一致するデータ部分を前記旧データから検出するまで、前記旧データの検索範囲を徐々に広げて検索するとともに、最終的な検索範囲を記録し、
前記検索条件決定部は、前記検索条件として、前記新データを分割した複数の区間のそれぞれについて、当該区間について前記第１の検索で記録された検索範囲の代表値が前記検索範囲の最大範囲未満である場合には、当該区間における前記旧データの検索範囲を、当該区間における検索範囲の代表値により近い検索範囲となるように決定する、
差分検出装置。
【請求項２】
前記検索条件決定部は、前記検索条件として、前記新データを分割した複数の区間のそれぞれについて、当該区間における前記第２の間隔を、当該区間における検索範囲の代表値が狭くなるほど狭くなるように決定する、
請求項１に記載の差分検出装置。
【請求項３】
前記第１の検索部は、前記第１の検索において、前記新データにおけるデータ部分と、当該データ部分と一致する前記旧データにおけるデータ部分とのズレ量を記録し、
前記検索条件決定部は、前記検索条件として、さらに、前記新データを分割した複数の区間のそれぞれについて、当該区間における前記新データの検索開始位置に対する、前記旧データの検索開始位置のズレ量を、当該区間について前記第１の検索部により記録されたズレ量の代表値の所定誤差範囲内の量として決定する、
請求項１に記載の差分検出装置。
【請求項４】
前記検索条件決定部は、前記検索条件として、前記新データを分割した複数の区間のそれぞれについて、当該区間における前記旧データの検索範囲を、当該区間における検索範囲の代表値として決定する、
請求項１に記載の差分検出装置。
【請求項５】
前記検索条件決定部は、前記複数の区間のそれぞれとして、前記第１の検索部により記録された検索範囲のばらつきが所定の範囲内となる区間を決定する、
請求項１、２、又は４に記載の差分検出装置。
【請求項６】
前記検索条件決定部は、前記複数の区間のそれぞれとして、前記第１の検索部により記録されたズレ量のばらつきが所定の範囲内となる区間を決定する、
請求項３に記載の差分検出装置。
【請求項７】
前記第２の検索部は、前記新データにおけるデータ部分と一致する前記旧データにおけるデータ部分を検出した場合、当該旧データにおけるデータ部分を中心として追込検索を実施し、当該追込検索により特定した連続一致データ部分の末尾を前記第２の間隔の起点とする、
請求項１乃至６のいずれか１項に記載の差分検出装置。
【請求項８】
旧データと、前記旧データを更新した新データとの間で相互に一致するデータ部分を検索することで、前記新データと前記旧データの差分を検出する差分検出方法であって、
前記新データにおける第１の間隔毎のデータ部分のそれぞれと一致するデータ部分を前記旧データから検索する第１の検索を実施するステップと、
前記第１の検索の検索結果に基づいて検索条件を決定するステップと、
前記決定された検索条件に基づいて、前記新データにおける前記第１の間隔以下の第２の間隔毎のデータ部分のそれぞれと一致するデータ部分を前記旧データから検索して、前記新データと前記旧データの差分を検出する第２の検索を実施するステップと、を備え、
前記第１の検索では、前記新データのデータ部分と一致するデータ部分を前記旧データから検出するまで、前記旧データの検索範囲を徐々に広げて検索するとともに、最終的な検索範囲を記録し、
前記検索条件の決定では、前記検索条件として、前記新データを分割した複数の区間のそれぞれについて、当該区間について前記第１の検索で記録された検索範囲の代表値が前記検索範囲の最大範囲未満である場合には、当該区間における前記旧データの検索範囲を、当該区間における検索範囲の代表値により近い検索範囲となるように決定する、
差分検出方法。
【請求項９】
旧データと、前記旧データを更新した新データとの間で相互に一致するデータ部分を検索することで、前記新データと前記旧データの差分を検出するための差分検出プログラムであって、
前記新データにおける第１の間隔毎のデータ部分のそれぞれと一致するデータ部分を前記旧データから検索する第１の検索を実施する処理と、
前記第１の検索の検索結果に基づいて検索条件を決定する処理と、
前記決定された検索条件に基づいて、前記新データにおける前記第１の間隔以下の第２の間隔毎のデータ部分のそれぞれと一致するデータ部分を前記旧データから検索して、前記新データと前記旧データの差分を検出する第２の検索を実施する処理と、をコンピュータに実行させ、
前記第１の検索では、前記新データのデータ部分と一致するデータ部分を前記旧データから検出するまで、前記旧データの検索範囲を徐々に広げて検索するとともに、最終的な検索範囲を記録し、
前記検索条件の決定では、前記検索条件として、前記新データを分割した複数の区間のそれぞれについて、当該区間について前記第１の検索で記録された検索範囲の代表値が前記検索範囲の最大範囲未満である場合には、当該区間における前記旧データの検索範囲を、当該区間における検索範囲の代表値により近い検索範囲となるように決定する、
差分検出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ処理、具体的には、例えば新旧データ間の差分を検出する技術に関する。
【背景技術】
【０００２】
コンピュータシステムにおいて、新データと旧データ間の差分を検出する処理が様々な場面で行われており、種々の手法が提案されている。
【０００３】
例えば、記憶装置に格納されたデータをバックアップする際に、データの一貫性を保証するために、データの更新を一時的に禁止して、格納中のデータをバックアップ用の別の記憶装置に書き出すことがなされている。しかし、データの巨大化に伴い、バックアップ用の時間が長くなるため、バックアップ作業中にデータへのアクセスが禁止されるのでは、業務に支障を来たしてしまう問題がある。
【０００４】
この問題を解消するために、差分バックアップの手法が提案された。差分バックアップの一例として、特許文献１に開示された手法を説明する。
【０００５】
該手法が適用された計算機システムは、記憶装置と、世代記録手段と、バックアップ装置と、差分バックアップ手段を備える。
【０００６】
記憶装置は、バックアップの対象となるデータが格納されており、所定サイズの複数のブロックに区分され、該ブロック単位でアクセスされる。バックアップ装置は、後述するバックアップデータを格納する。
【０００７】
世代記録手段は、上記記憶装置のブロック毎に差分マップ情報を記憶している。該差分マップ情報は、該ブロック内のデータを更新した最新のバックアップ世代が記録されている。世代記録手段は、各ブロックについて、該ブロック内のデータが更新されたときに、該ブロックに対応する差分マップ情報に最新のバックアップ世代を記録する。
【０００８】
差分バックアップ手段は、指定されたバックアップ世代に更新された上記記憶装置のブロックのデータを上記差分マップ情報に基づいて入力し、該ブロックのデータ、該ブロックの上記記憶装置における位置、及び、該ブロックが更新された上記バックアップ世代を、バックアップデータとしてバックアップ装置に格納する。
【０００９】
すなわち、特許文献１に開示された所謂差分バックアップ技術は、記憶装置の更新されたブロックのみを複数世代にわたりバックアップする手法である。
【００１０】
また、新旧データ間の差分を検出する手法は、例えば、新データの先頭からある程度の長さのデータと一致する部分を旧データから検索し、それが旧データに存在しない場合には長さを短くして再検索したり、一致する長さと場所を記憶しておき、一致する長さが最大となる場所を検出した後に、その部分を除外して他の部分を再検索する、という処理を繰り返す手法が知られている。以下、この手法を第１の手法という。
【００１１】
また、新旧データ間の差分を高速に検出するアルゴリズムとしては、例えばＢＭ法（ＢＭ：Ｂｏｙｅｒ−Ｍｏｏｒｅ）が知られている。
【００１２】
また、検索を行う範囲を限定することで検索を高速化する手法も考案されている。以下、この手法を第２の手法という。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開平０９−１０１９１２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
特許文献１の手法は、記憶装置のアクセス単位（例えば２Ｋバイト）と同サイズのブロック単位で新旧データの差分をバックアップするため、例えば大きなサイズのデータの小規模な更新がランダムな場所で多発する場合において、バックアップデータのサイズが大きく、必要なバックアップ装置の容量も大きいという問題がある。
【００１５】
新旧データの差分について、上述した第１の手法は、確実に差分を抽出することができるものの、データのサイズが大きくなるに従って、累乗的に処理時間がかかるという問題があった。
【００１６】
ＢＭ法により代表される高速検索アルゴリズムは、通常の方法より高速化を図ることができるが、データが巨大になると検索に膨大な処理時間がかかることに変わりはなく、実用性を上げるための障害となっていた。
【００１７】
検索範囲を限定する第２の手法は、高速化には効果的である一方、検索範囲以外の場所に目的とするデータがあった場合にはそれを見つけることができなくなるため、作成した差分データが巨大なものになってしまいやすいという欠点がある。
【００１８】
本発明は、上記事情を鑑みてなされたものであり、新データと旧データ間の差分を高速に検出すると共に、検出精度を高めることにより差分データの容量を抑制できる技術を提供する。
【課題を解決するための手段】
【００１９】
本発明の１つの態様にかかる差分検出装置は、旧データと、前記旧データを更新した新データとの間で相互に一致するデータ部分を検索することで、前記新データと前記旧データの差分を検出する差分検出装置であって、前記新データにおける第１の間隔毎のデータ部分のそれぞれと一致するデータ部分を前記旧データから検索する第１の検索を実施する第１の検索部と、前記第１の検索部による検索結果に基づいて検索条件を決定する検索条件決定部と、前記検索条件決定部によって決定された検索条件に基づいて、前記新データにおける前記第１の間隔以下の第２の間隔毎のデータ部分のそれぞれと一致するデータ部分を前記旧データから検索して、前記新データと前記旧データの差分を検出する第２の検索を実施する第２の検索部と、を備え、前記第１の検索部は、前記第１の検索において、前記新データのデータ部分と一致するデータ部分を前記旧データから検出するまで、前記旧データの検索範囲を徐々に広げて検索するとともに、最終的な検索範囲を記録し、前記検索条件決定部は、前記検索条件として、前記新データを分割した複数の区間のそれぞれについて、当該区間について前記第１の検索で記録された検索範囲の代表値が前記検索範囲の最大範囲未満である場合には、当該区間における前記旧データの検索範囲を、当該区間における検索範囲の代表値により近い検索範囲となるように決定するものである。
【００２０】
本発明の２つの態様にかかる差分検出方法は、旧データと、前記旧データを更新した新データとの間で相互に一致するデータ部分を検索することで、前記新データと前記旧データの差分を検出する差分検出方法であって、前記新データにおける第１の間隔毎のデータ部分のそれぞれと一致するデータ部分を前記旧データから検索する第１の検索を実施するステップと、前記第１の検索の検索結果に基づいて検索条件を決定するステップと、前記決定された検索条件に基づいて、前記新データにおける前記第１の間隔以下の第２の間隔毎のデータ部分のそれぞれと一致するデータ部分を前記旧データから検索して、前記新データと前記旧データの差分を検出する第２の検索を実施するステップと、を備え、前記第１の検索では、前記新データのデータ部分と一致するデータ部分を前記旧データから検出するまで、前記旧データの検索範囲を徐々に広げて検索するとともに、最終的な検索範囲を記録し、前記検索条件の決定では、前記検索条件として、前記新データを分割した複数の区間のそれぞれについて、当該区間について前記第１の検索で記録された検索範囲の代表値が前記検索範囲の最大範囲未満である場合には、当該区間における前記旧データの検索範囲を、当該区間における検索範囲の代表値により近い検索範囲となるように決定するものである。
【００２１】
なお、上記態様の装置をシステムや方法に置き換えて表現したもの、該方法をコンピュータに実行せしめるプログラム、該プログラムを記録した記録媒体、該装置が含まれるバックアップ装置等も、本発明の態様としては有効である。
【発明の効果】
【００２２】
本発明の技術によれば、新データと旧データ間の差分の検出速度と精度を両立させることができる。
【図面の簡単な説明】
【００２３】
【図１】第１の実施の形態にかかるデータ処理装置を示す図である。
【図２】図１に示すデータ処理装置における第２の検索部の検索結果の例を示す図である。
【図３】図２に示す検索結果の場合において差分データ生成部が作成した差分データの例を示す図である。
【図４】図１に示すデータ処理装置における第１の検索部を詳細に説明するための図である（その１）。
【図５】図１に示すデータ処理装置における第１の検索部を詳細に説明するための図である（その２）。
【図６】図１に示すデータ処理装置における第１の検索部を詳細に説明するための図である（その３）。
【図７】図１に示すデータ処理装置における検索条件設定部の原理を説明するための図である。
【図８】図１に示すデータ処理装置における第２の検索部による追込検索を説明するための図である。
【図９】第１の実施の形態にかかるデータ処理装置の処理を示すフローチャートである。
【図１０】図９に示すデータ処理装置の処理における第１の検索処理を詳細に示すフローチャートである。
【図１１】図９に示すデータ処理装置の処理における第２の検索処理を詳細に示すフローチャートである。
【図１２】図９に示すデータ処理装置の処理における検索条件決定処理を詳細に示すフローチャートである。
【発明を実施するための形態】
【００２４】
以下、図面を参照して本発明の実施の形態について説明する。説明の明確化のため、以下の記載及び図面は、適宜、省略、及び簡略化がなされている。また、様々な処理を行う機能ブロックとして図面に記載される各要素は、ハードウェアとソフトウェア（プログラム）の組合せによっていろいろな形で実現できることは当業者には理解されるところであり、ハードウェアとソフトウェアのいずれかに限定されるものではない。なお、各図面において、同一の要素には同一の符号が付されており、必要に応じて重複説明は省略されている。
【００２５】
また、上述したプログラムは、様々なタイプの非一時的なコンピュータ可読媒体（ｎｏｎ−ｔｒａｎｓｉｔｏｒｙ  ｃｏｍｐｕｔｅｒ  ｒｅａｄａｂｌｅ  ｍｅｄｉｕｍ）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（ｔａｎｇｉｂｌｅ  ｓｔｏｒａｇｅ  ｍｅｄｉｕｍ）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、ＣＤ−ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Ｐｒｏｇｒａｍｍａｂｌｅ  ＲＯＭ）、ＥＰＲＯＭ（Ｅｒａｓａｂｌｅ  ＰＲＯＭ）、フラッシュＲＯＭ、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（ｔｒａｎｓｉｔｏｒｙ  ｃｏｍｐｕｔｅｒ  ｒｅａｄａｂｌｅ  ｍｅｄｉｕｍ）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【００２６】
＜第１の実施の形態＞
図１は、第１の実施の形態にかかるデータ処理装置１００を示す。データ処理装置１００は、旧データＤ１と新データＤ２間の差分を検出して差分データを生成して保存するためのものであり、第１の検索部１１０、検索条件決定部１２０、第２の検索部１３０、差分データ生成部１４０を備える。旧データＤ１と新データＤ２は、例えば夫々のためのメモリに格納されている。
【００２７】
第１の検索部１１０は、新データＤ２の先頭から末尾まで離散的に検索対象ブロックを選択し、夫々の検索対象ブロックについて、旧データＤ１における検索範囲を段階的に広げながら、該検索対象ブロックが旧データＤ１にあるか否かの検索を行う。以下において、検索対象ブロックのサイズを「検索単位」ともいう。なお、後に詳細に説明するが、第１の検索部１１０の検索条件は、予め定められたものである。
【００２８】
検索条件決定部１２０は、第１の検索部１１０の検索結果に基づいて第２の検索部１３０の検索条件を決定する。
【００２９】
第２の検索部１３０は、検索条件決定部１２０により決められた検索条件を用いて、新データＤ２と旧データＤ１間で連続して互いに一致する領域（連続一致領域）を検出する。
【００３０】
差分データ生成部１４０は、第２の検索部１３０の検索結果に基づいて差分データを生成する。
【００３１】
ここで、まず、図２、図３を参照して、第２の検索部１３０の検索結果と差分データ生成部１４０の概要を説明する。
【００３２】
以降の図において、斜線により示される領域［Ｗ］は、第２の検索部１３０により検出した連続一致領域を示し、Ｗの後の２つの数字は、旧データＤ１と新データＤ２のいずれにおける連続一致領域か、何番目の連続一致領域かを示す。
【００３３】
すなわち、「Ｗ１ｉ」は、旧データＤ１で検出したｉ番目の連続一致領域を示し、「Ｗ２ｉ」は、新データＤ２で検出したｉ番目の連続一致領域を示し、「Ｗ１ｉ」と「Ｗ２ｉ」は、同様のデータブロックである。
【００３４】
また、「Ｐ１Ｌｉ」と「Ｐ１Ｒｉ」は第２の検索部１３０が旧データＤ１で検出したｉ番目の連続一致領域（Ｗ１ｉ）の先頭と末尾のアドレス位置であり、「Ｐ２Ｌｉ」と「Ｐ２Ｒｉ」は、第２の検索部１３０が新データＤ２で検出したｉ番目の連続一致領域（Ｗ２ｉ）の先頭と末尾のアドレス位置である。
【００３５】
図２は、第２の検索部１３０が旧データＤ１と新データＤ２間で検出した２つの連続一致領域を示している。図示のように、これらの連続一致領域は、旧データＤ１においては「Ｗ１１」と「Ｗ１２」であり、新データＤ２においては「Ｗ２１」と「Ｗ２２」である。「Ｗ１１」と「Ｗ２１」が同様のデータであり、「Ｗ１２」と「Ｗ２２」は同様のデータである。
【００３６】
差分データ生成部１４０は、第２の検索部１３０の検索結果から差分データを生成する。図３は、図２に示す検索結果に対して、差分データ生成部１４０が生成した差分データの例である。
【００３７】
図３に示すように、差分データは、「挿入」と「参照」の２種類から構成される。「挿入」コードに対応して、挿入（更新）されたデータ、のサイズと、挿入されたデータ（新データＤ２における実データ）が記録されており、「参照」コードに対応して、参照されるデータのサイズと、旧データＤ１における参照アドレス（旧データＤ１の先頭からのアドレス位置）とが記録されている。
【００３８】
図３の１行目に示すように、まず、新データＤ２の先頭から、第２の検索部１３０が新データＤ２において検出した１つ目の連続一致領域（ここでは領域Ｗ２１）の先頭のアドレス位置（Ｐ２Ｌ１）までのデータとサイズが記録されている。
【００３９】
続いて、図３の２行目に示すように、「参照」コードに対応して、旧データＤ１における１つ目の連続一致領域（Ｗ１１）の先頭のアドレス（Ｐ１Ｌ１）とサイズが記録されている。
【００４０】
また、３行目に示すように、続いて、新データＤ２における連続一致領域Ｗ２１の末尾（Ｐ２Ｒ１）から、連続一致領域Ｗ２２の先頭（Ｐ２Ｌ２）までのデータとサイズが記録されている。
【００４１】
続いて、４行目に示すように、旧データＤ１における２つ目の連続一致領域Ｗ１２の先頭のアドレス（Ｐ１Ｌ２）とサイズが記録されている。
【００４２】
差分データ生成部１４０は、このようにして差分データを作成し、作成された差分データは、旧データＤ１と共に保存される。そのため、新データＤ２が必要な場合には、差分データと旧データＤ１から、新データＤ２を復元することができる。
【００４３】
図３から分かるように、差分データは、挿入されたデータが差分データの主な容量を占める。そのため、挿入データの量が少ないほど、差分データのサイズが小さくなる。
【００４４】
旧データＤ１と新データＤ２間の連続一致領域を多く検出するほど、差分データに含まれる挿入データの量が少なくなるため、差分データの小サイズ化を図るためには、できるだけ多くの連続一致領域を検出する必要がある。
【００４５】
以上を踏まえて、データ処理装置１００の各機能ブロックを詳細に説明する。
＜＜第１の検索＞＞
まず、図４〜図６を参照して、第１の検索部１１０を説明する。
【００４６】
これらの図において、横方向の位置は、当該データの先頭からのアドレス位置を示す。また、点線により囲まれた各小さな矩形のサイズは、検索単位と同サイズである。例として、１検索単位が１Ｋバイトであるとする。また、例として、検索範囲は、「小範囲」（２５６Ｋバイト）、「中範囲」（２Ｍバイト）、「大範囲」（８Ｍバイト）、「全範囲」の４つの段階に分けられているとする。
【００４７】
図４に示すように、第１の検索部１１０は、まず、新データＤ２の先頭のデータブロック（ブロックＸ）を検索対象ブロックとして選択し、ブロックＸと同様のデータブロックが旧データＤ１にあるか否かを検索する。図４は、ブロックＸと同様のデータブロックが旧データＤ１から検出されなかった場合を示す。
【００４８】
具体的には、第１の検索部１１０は、まず、旧データＤ１の先頭からの小範囲（２５６Ｋバイト）の領域にブロックＸがあるか否かを検索する。該小範囲の領域にブロックＸが見つからないため、第１の検索部１１０は、さらに、検索範囲を旧データＤ１の先頭からの中範囲（２Ｍバイト）の領域に広げ、該中範囲の領域にブロックＸがあるか否かを検索する。該中範囲の領域にブロックＸが見つからないため、第１の検索部１１０は、さらに、検索範囲を旧データＤ１の先頭からの大範囲（８Ｍバイト）の領域に広げ、該大範囲の領域にブロックＸがあるか否かを検索する。該大範囲の領域にもブロックＸが見つからないため、第１の検索部１１０は、さらに、検索範囲を旧データＤ１の全範囲に広げ、旧データＤ１の全範囲にブロックＸがあるか否かを検索する。
【００４９】
旧データＤ１の全範囲においてもブロックＸが見つからないため、第１の検索部１１０は、新データＤ２から次の検索対象ブロックを選択する。
【００５０】
従来の検索手法では、次の検索対象ブロックとして、新データＤ２におけるブロックＸの次のデータブロック（図４ではブロックＸの右隣のブロック）が選択される。対して、本実施の形態において、第１の検索部１１０は、離散的に検索対象ブロックを選択する。具体的には、第１の検索部１１０は、ブロックＸから、所定のサイズをスキップしてスキップ先の１検索単位（１Ｋバイト）のデータブロックを次の検索対象ブロックに選択する。以下において、第１の検索部１１０が検索対象ブロックを選択する際にスキップするデータの量をスキップサイズという。本実施の形態において、例として、第１の検索部１１０のスキップサイズは、検索単位の１６倍すなわち１６Ｋバイトであるとする。
【００５１】
図５に示すように、第１の検索部１１０は、新データＤ２において、ブロックＸの先頭から１６Ｋバイトをスキップし、スキップ先の１Ｋバイトのデータブロック（ブロックＹ）について、旧データＤ１に同様のデータブロックがあるか否かを検索する。具体的な検索の手順は、ブロックＸのときと同様である。図５の例では、ブロックＹについて、旧データＤ１において同様のデータブロックが検出されている。
【００５２】
この場合、第１の検索部１１０は、新データＤ２におけるブロックＹと、旧データＤ１におけるブロックＹとのアドレス位置のズレ量αを算出する。図５に示すように、このズレ量αは、新データＤ２と旧データＤ１間で互いに対応するデータブロックの先頭のアドレス位置の差である。勿論、新旧データ間に相対応する２つのデータブロックの末尾のアドレス位置の差も同値となる。
【００５３】
第１の検索部１１０は、ズレ量αと、検索範囲の広さとを対応付けて記録する。
【００５４】
図５に示す例の場合、検索範囲の広さとして、ブロックＹを旧データＤ１から検出したときの検索範囲の広さ（小範囲、中範囲、大範囲、全範囲のいずれか１つ）とが対応付けて記録される。
【００５５】
次に、第１の検索部１１０は、新データＤ２におけるブロックＹの先頭からスキップサイズ分（ここでは１６Ｋバイト）をスキップして、スキップ先のデータブロック（ブロックＺ）について、旧データＤ１における検索範囲を段階的に広げながら、旧データＤ１において、ブロックＺと同様のデータブロックがあるか否かの検索をする。
【００５６】
この場合、旧データＤ１における検索範囲の開始位置（検索開始位置）は、旧データＤ１におけるブロックＹの先頭から１６Ｋバイトをスキップした先としてもよい。また、検索精度を高めるために、例えば、図６に示すように、旧データＤ１におけるブロックＹの先頭から１６Ｋバイトをスキップした先から少し（例えば１検索単位分）を戻した位置としてもよい。なお、このサイズは、１検索単位に限られず、予め任意に定めたサイズとしてよい。
【００５７】
旧データＤ１における検索開始位置から旧データＤ１の末尾までの全範囲に検索範囲を広げてもブロックＺと同様のデータブロックが見つからなければ、第１の検索部１１０は、ブロックＺの先頭からさらに１６Ｋバイトをスキップし、スキップ先のデータブロックを次の検索対象ブロックとして検索する。
【００５８】
一方、旧データＤ１における検索開始位置からのいずれかの検索範囲でブロックＺと同様のデータブロックが見つかれば、第１の検索部１１０は、ブロックＹのときと同様に、ブロックＺに対応するズレ量αと、旧データＤ１からブロックＺを検出したときの検索範囲の広さとを対応付けて記録する。
【００５９】
第１の検索部１１０は、このようにして、新データＤ２からの検索対象ブロックの選択、選択した検索対象ブロックが旧データＤ１にあるか否かの検索を繰り返し、複数のズレ量αと、検索範囲の広さを得る。
【００６０】
＜＜検索条件の決定＞＞
検索条件決定部１２０は、第１の検索部１１０の検索結果に基づいて第２の検索部１３０の検索条件を決定する。検索条件決定部１２０により第２の検索部１３０の検索条件を決定する原理を説明する。検索条件決定部１２０は、第２の検索部１３０の検索条件として、「検索開始位置ズレ量」、「検索範囲」、及び「スキップサイズ」を決定する。
【００６１】
＜検索開始位置ズレ量＞
第１の検索部１１０では、現在の検索対象ブロックについての旧データＤ１における検索開始位置が、基本的に、新データＤ２における検索開始位置（検索対象ブロックの先頭）と同一位置となる。対して、第２の検索部１３０では、現在の検索対象ブロックについての旧データＤ１における検索開始位置が、新データＤ２における検索開始位置に対して相対的に、検索条件決定部１２０により決定され、位置によって異なり得る。
【００６２】
＜検索範囲＞
第１の検索部１１０は、検索対象ブロックと同様のデータブロックが旧データＤ１にあるか否かの検索をする際に、段階的に検索範囲を広げながら検索を行う。対して、第２の検索部１３０は、その検索範囲が検索条件決定部１２０により決定され、位置によって異なり得る。第２の検索部１３０は、検索条件決定部１２０により決定された検索範囲内でのみ検索を行う。
【００６３】
＜スキップサイズ＞
前述したように、第１の検索部１１０のスキップサイズは、固定値である。対して、第２の検索部１３０は、検索対象ブロックを選択する際のスキップサイズが検索条件決定部１２０により決定され、位置によって異なり得る。
【００６４】
以下、ここでは内容の明確化のため、新データと旧データの関係が図７に例示する関係を有する場合について説明する。図７は、旧データＤ１と新データＤ２の関係の一例を示す図である。図７では、横軸は、旧データＤ１の先頭からのアドレス位置を示す。図７の上部の縦軸は、同様のデータが新データＤ２と旧データＤ１で出現した位置のズレ量を示す。図７の下部の縦軸は、新データＤ２と旧データＤ１において、同様のデータが出現する確率（出現率）を示す。すなわち、図７は、同様のデータが新データＤ２と旧データＤ１で出現した位置のズレ量の分布と、新データＤ２と旧データＤ１において、同様のデータの出現率の分布である。
【００６５】
図７の例では、先頭から約２００Ｍバイトの位置Ａにおいて、旧データＤ１に対する新データＤ２のズレ量が−１０Ｍバイトである。これは、新データＤ２では、位置Ａにおいて旧データＤ１から１０Ｍバイト分削除されていることを表している。すなわち、図７の例では、先頭から約２００Ｍバイトの位置Ａ以降では、新データＤ２の検索対象ブロックに対する、旧データＤ１のそれと同一のデータブロックのズレ量αは、概ね「１０Ｍバイト」となる。
【００６６】
先頭から約４２０Ｍバイト離れた位置Ｂにおいて、新旧データ間で同様のデータの出現率が高めであり、４０％以下の出現率のデータが無い。一方、先頭から約７００Ｍバイト離れた位置Ｃにおいて、１０％〜６０％の低い出現率のデータが多い。
【００６７】
ここで、旧データＤ１と新データＤ２の差分を検出するとき、新データＤ２と旧データＤ１の検索開始位置を同一位置に固定し、検索範囲の広さを一定に固定した場合を考える。
【００６８】
検索範囲が広いほど検索に時間がかかるため、検索時間を短くするために検索範囲の広さを例えば５Ｍバイトに固定した場合に、位置Ａにおいて１０Ｍバイトのズレがあったため、位置Ａを過ぎると、新旧データ間で一致するデータが見つからない状態になり、位置Ａ以降の新データＤ２のデータを挿入データとして記録することになる。また、例えば位置Ｂでは、４０％以上のデータに一致する場所があるにもかかわらず、それを見つけられずに、それ以降のデータを全て新データＤ２のデータを挿入することになる。これでは、差分データのサイズが大きくなってしまう。
【００６９】
逆に、位置Ａにおけるズレ量（１０Ｍバイト）よりも広く検索範囲を固定した場合、位置Ｂでは検索がヒットするので早めに検索が終わる。一方、位置Ｃでは、一致率が概ね１０％〜６０％なので、すなわち、４０％〜９０％は全ての範囲を検索しても、最後まで一致するデータが出現しない無駄な検索を行うことになってしまう。もし、ここで検索範囲を狭めれば、４０％〜９０％の検索が失敗するデータについて、早い段階で諦めが付くために動作としては高速になる。
【００７０】
そのため、新旧データ間で同一のデータが出現する場所のズレ量が小さい場所に対して、検索範囲を狭めても、新旧データ間で連続一致領域の検出漏れが少ないことが分かる。そのため、このような場所について、検索範囲を狭めることで検索の高速化を図ることができる。
【００７１】
そこで、検索条件決定部１２０は、まず、第１の検索部１１０の検索結果におけるズレ量αに基づいて、新データＤ２を複数の区間に分ける。同一の区間内において第１の検索部１１０が記録した各ズレ量αが、ほぼ同様であり、例えば、その区間の最初のズレ量と、他の全てのズレ量のそれぞれとの互いの差が全てズレ量差閾値以下である。また、隣接する２つの区間同士では、前の区間に対して第１の検索部１１０が記録した最初のズレ量αと、次の区間に対して第１の検索部１１０が記録した最初のズレ量αとの差が大きく、例えば、ズレ量差閾値より大きい。ここで、上記のズレ量差閾値は、任意の値を予め定めるようにしてよい。
【００７２】
例えば、図７の位置Ａまでの範囲内で見られるように、新データＤ２と旧データＤ１との間で同一のデータブロックのズレ量αがほぼ同一で続く範囲については、１つの区間とされる。
【００７３】
そして、検索条件決定部１２０は、新データＤ２の各区間について、該区間内から選択された検索対象ブロックについての新データＤ２における検索開始位置に対する旧データＤ１における検索開始位置のズレ量（検索開始位置ズレ量）を、該区間の代表ズレ量として決定する。代表ズレ量とは、当該区間内の各ズレ量αを示す指標であり、例えば、該区間内の各ズレ量αの平均値、最大値、最小値、最も多く検出した値などとすることができる。
【００７４】
具体的には、第２の検索では、旧データＤ１における、新データＤ２から選択された検索対象ブロックの先頭位置と同様の位置を基準位置とした場合に、当該検索対象ブロックについての旧データＤ１における検索開始位置を、上記基準位置から、該検索対象ブロックが属する区間の検索開始位置ズレ量（代表ズレ量）の分ずらした位置に決定する。
【００７５】
例えば、図７の位置Ａまでで主に見られるように、代表ズレ量が０バイトとなる区間では、検索開始位置ズレ量を０バイトとすることで、旧データＤ１の検索開始位置を、新データＤ２の検索対象ブロックの先頭位置と同様の位置として決定する。それに対して、例えば、図７の位置Ａ以降で主に見られるように、代表ズレ量が１０Ｍバイトとなる区間では、検索開始位置ズレ量を１０Ｍバイトとすることで、旧データＤ１の検索開始位置を、新データＤ２の検索開始位置に１０Ｍバイトが加算された位置となるように決定する。
【００７６】
このようにすることで、第２の検索において、旧データＤ１の検索開始位置を、新データＤ２の検索対象ブロックと同一のデータブロックにより近い位置とすることができるため、検索を高速化することができる。
【００７７】
ここで、検索開始位置ズレ量は、上記のように代表ズレ量そのものとする例に限られない。例えば、検索開始位置ズレ量は、代表ズレ量とは所定誤差範囲内で異なる量（例えば同一データブロックのズレ量のばらつきを考慮して検出精度を上げるために代表ズレ量を数〜数十パーセント減少させた量）としてもよい。このようにしても、旧データＤ１における検索開始位置は、新データＤ２における検索開始位置と同一とする場合と比較して、同一のデータブロックにより近い位置とされるため、上述の検索を高速化するという効果が得られるからである。
【００７８】
また、検索条件決定部１２０は、第１の検索部１１０の検索結果における検索範囲の広さに基づいて、新データＤ２を複数の区間に分ける。同一の区間内において第１の検索部１１０が記録した各検索範囲が、ほぼ同様の広さであり、例えば、その区間の最初の検索範囲と、他の全ての検索範囲のそれぞれとの互いの差が全て検索範囲差閾値以下である。また、隣接する２つの区間同士では、前の区間に対して第１の検索部１１０が記録した最初の検索範囲αと、次の区間に対して第１の検索部１１０が記録した最初の検索範囲との差が大きく、例えば、検索範囲差閾値以上より大きい。ここで、上記の検索範囲差閾値は、任意の値を予め定めるようにしてよい。
【００７９】
検索条件決定部１２０は、新データＤ２の各区間について、該区間内において検索対象ブロックを選択する際のスキップサイズを、該区間の代表検索範囲に基づいて決定する。代表検索範囲とは、第１の検索部１１０が当該区間に対して記録した各検索範囲の広さを示す指標であり、例えば、該区間内の各検索範囲の平均値、最大値、最小値、最も多く検出した値などとすることができる
【００８０】
具体的には、例えば、新データＤ２の各区間について、該区間内から検索対象ブロックを選択する際のスキップサイズを、代表検索範囲の広さが狭いほど小さくなるように決定する。
【００８１】
例えば、検索条件決定部１２０は、第１の検索部１１０の検索の結果、２５６Ｋバイト以内にデータが見つかる区間ではスキップなし（１倍検索）、２５６Ｋを超えるが２Ｍバイト以内なら２倍検索（２Ｋバイトスキップ）、２Ｍバイトを超えるが８Ｍバイト以内なら４倍検索（４Ｋバイトスキップ）、全体を検索する必要がある領域では１６倍検索（１６Ｋバイトスキップ）になるように、第２の検索部１３０に対してスキップサイズを決定する。
【００８２】
ここで、代表検索範囲が広い場合には、その区間において、新データＤ２と旧データＤ１との間で同一のデータブロックの位置がばらついている（出現率が悪い）ことになる。言い換えると、代表検索範囲が狭い場合には、その区間において、新データＤ２と旧データＤ１との間で同一のデータブロックの位置がばらついていない（出現率が良い）ことになる。よって、スキップサイズを、第１の検索の代表検索範囲が狭いほど小さくなり、広いほど大きくなるように決定することで、効率の悪い（同一のデータブロックが大きくばらついている、出現率が悪い）検索を省き、検索を高速化することができる。効率の悪い場合のみ検索が省略されることになるため、検索精度を低下させることがなく、検索を高速化して検索精度を高めることができる。
【００８３】
なお、スキップサイズは、代表検索範囲が狭いほど小さくなり、広いほど大きくなるように決定されるのであれば、上記の例には限られない。スキップサイズがそのように決定されるのであれば、検索対象ブロックと同一のデータブロックが大きくばらついている（出現率の悪い）場合のみに検索が省略され、検索対象ブロックと同一のデータブロックがあまりばらついていない（出現率の良い）場合には細かく検索が行われることになるため、上述の検索を高速化して検索精度を高めることができるという効果が得られるからである。
【００８４】
また、検索条件決定部１２０は、新データＤ２の各区間について、該区間内についての第２の検索での旧データＤ１の検索範囲を決定する。
【００８５】
検索条件決定部１２０は、各区間の代表検索範囲を、そのまま各区間の第２の検索における検索範囲として決定する。
【００８６】
ここで、代表検索範囲は、その区間において、検索範囲をその広さとすることで概ね新データＤ２と旧データＤ１との間で同一のデータブロックを検出することが第１の検索によって立証された広さとなる。よって、第２の検索の検索範囲を、第１の検索の代表検索範囲とすることで、常に最大範囲を検索する場合と比較して検索範囲を低減することができ、同一のデータブロックも検出することもできるため、検索を高速化して検索精度を高めることができる。
【００８７】
なお、第２の検索における検索範囲は、代表検索範囲が検索範囲の最大範囲未満である場合に、代表検索範囲により近い検索範囲となるように決定されるのであれば、上記のように第１の検索の代表検索範囲そのものとする例に限られない。そのようにしても、常に最大範囲を検索する場合と比較して検索範囲を低減することができ、同一のデータブロックも検出することもできるため、検索を高速化して検索精度を高めることができる。しかしながら、好ましくは、上述したように第２の検索における検索範囲を代表検索範囲そのものとすることで、第１の検索で丁度同一のデータブロックを検出することが立証された広さとなるため、より無駄な検索範囲を省いて検索を行うことができ、より検索を高速化することができる。
【００８８】
このように、検索条件決定部１２０は、第１の検索部１１０が記録したズレ量αと検索範囲の広さとに基づいて、第２の検索部１３０に対して検索条件を決定する。
【００８９】
以上のように、ズレ量αと検索範囲の広さに基づいて、第１の検索結果をグループ分けすれば、各グループのアドレス範囲で一定のズレ量及び検索範囲の広さとスキップサイズを用いて効率の良い第２の検索を行うことが可能となる。常に最大範囲を検索する場合と比較して検索範囲を低減することができ、同一のデータブロックも検出することもできるため、上述の検索を高速化して検索精度を高めることができるという効果を得られるからである。
【００９０】
＜＜第２の検索＞＞
第２の検索部１３０は、検索条件決定部１２０が決定した検索条件で検索を行い、旧データＤ１と新データＤ２とで一致するデータを検出してそれらを示す情報を差分データ生成部１４０に出力する。
【００９１】
例えば、位置Ａよりも前の代表ズレ量が０であるところで、代表検索範囲が小範囲（２５６Ｋバイト）である区間では、第２の検索部１３０は、検索開始位置ズレ量を０とし、検索範囲を小範囲とし、スキップサイズを０（スキップなし）として第２の検索を行う。
【００９２】
また、例えば、位置Ｂ付近の代表ズレ量が１０Ｍバイトであるところで、代表検索範囲が中範囲（２Ｍバイト）である区間では、第２の検索部１３０は、検索開始位置ズレ量を１０Ｍバイトとし、検索範囲を中範囲とし、スキップサイズを２Ｋバイトとして第２の検索を行う。
【００９３】
また、例えば、位置Ｃ付近の代表ズレ量が１０Ｍバイトであるところで、代表検索範囲が全範囲である区間では、第２の検索部１３０は、検索開始位置ズレ量を１０Ｍバイトとし、検索範囲を全範囲とし、スキップサイズを１６Ｋバイトとして第２の検索を行う。
【００９４】
また、第２の検索では、第２の検索部１３０は、追込検索も実施する。図８を参照して、追込検索を説明する。説明に際して、第２の検索部１３０が、図５に示すように、新データＤ２におけるブロックＹと同様のデータブロックを旧データＤ１で検出した場合を例にする。
【００９５】
図８に示すように、この場合、第２の検索部１３０は、まず、旧データＤ１におけるブロックＹの左隣の１バイトと、新データＤ２におけるブロックＹの直前（左隣）の１バイトとを比較する。以下において、第２の検索部１３０が連続一致領域を検出するために比較する旧データＤ１の１バイトと新データＤ２の１バイトとを「バイトペア」という。
【００９６】
上記比較の結果、該バイトペアが一致するならば、第２の検索部１３０は、さらに、該バイトペアの左隣のバイトペアの比較を行う。
【００９７】
第２の検索部１３０は、このような比較を、バイトペアが一致しない結果が出るまで行う。図８に示す例において、ブロックＹの左隣において、同様の内容である部分ＷＬが検出されている。以下、この部分ＷＬを「左隣連続一致領域」という。
【００９８】
次に、第２の検索部１３０は、ブロックＹの直後（右隣）のバイトペアを比較する。該バイトペアが一致するならば、第２の検索部１３０は、さらに、該バイトペアの右隣のバイトペアの比較を行う。
【００９９】
第２の検索部１３０は、このような比較を、バイトペアが一致しない結果が出るまで行う。図８に示す例において、ブロックＹの右隣において、同様の内容である部分ＷＲが検出されている。以下、この部分ＷＲを「右隣連続一致領域ＷＲ」という。左隣連続一致領域ＷＬと、ブロックＹと、右隣連続一致領域ＷＲとの総和は、連続一致領域となる。
【０１００】
当然ながら、第２の検索部１３０がこのような動作にすると、例えばブロックＸとブロックＹの間に不連続な一致領域が存在する場合には、該部分が検出されないという制約が発生する。しかし、図８で説明したバイトペアの検索により、スキップした領域の一致データも救済されるため、制約の影響は少ない。また、検索範囲が狭かった場合は第２の検索により、スキップサイズを小さくした検索が行われるので制約の影響はさらに少なくなる。
【０１０１】
図９〜図１１は、これらの処理を示したフローチャートである。続いて、図９〜図１１を参照して、第１の実施の形態にかかるデータ処理装置１００の処理について説明する。図９は、第１の実施の形態にかかるデータ処理装置１００の差分データ保存処理を示すフローチャートである。図１０は、差分データ保存処理における第１の検索処理を示すフローチャートである。図１１は、差分データ保存処理における第２の検索処理を示すフローチャートである。
【０１０２】
まず、図９を参照して、第１の実施の形態にかかるデータ処理装置１００の差分データ保存処理について説明する。
【０１０３】
データ処理装置１００のメモリに対して新データＤ２が書き込まれた場合、データ処理装置１００の記憶装置（例えばハードディスク又は不揮発性メモリ等）に保存されている、その新データＤ２の更新前の旧データＤ１を取得する。そして、第１の検索部１１０は、新データＤ２と旧データＤ１について第１の検索処理を実施する（Ｓ１）。
【０１０４】
検索条件決定部１２０は、第１の検索結果に基づいて、上述したように第２の検索における検索条件を決定する（Ｓ２）。第２の検索部１３０は、検索条件決定部１２０によって決定された検索条件で、新データＤ２と旧データＤ１について第２の検索処理を実施する（Ｓ３）。差分データ生成部１４０は、第２の検索結果に基づいて差分データを作成し、旧データＤ１と共に記憶装置に保存する（Ｓ４）。
【０１０５】
続いて、図１０を参照して、図９のＳ１にかかる第１の検索処理について説明する。
【０１０６】
まず、第１の検索では、検索単位として１Ｋバイトが予め定められており、スキップサイズとして１６倍離散（１６Ｋバイト）が予め定められているものとする（Ｓ１０、Ｓ１１）。第１の検索開始時には、第１の検索部１１０は、新データＤ２と旧データＤ１のそれぞれで検索開始位置を、それぞれのデータの先頭に設定する（Ｓ１２）。第１の検索部１１０は、検索範囲を最小範囲（小範囲：２５６Ｋバイト）に設定して、新データＤ２における検索対象ブロックについて検索を開始する（Ｓ１３）。すなわち、第１の検索部１１０は、旧データＤ１の検索範囲において新データＤ２の検索対象ブロックと一致するデータブロックを検索する。
【０１０７】
旧データＤ１の検索範囲において検索対象ブロックと一致するデータブロックを検出できず（Ｓ１４：Ｎｏ）、かつ検索範囲が最大範囲（全範囲）とされていない場合（Ｓ１５：Ｎｏ）、第１の検索部１１０は、検索範囲を１段階広げる（Ｓ１６）。そして、第１の検索部１１０は、Ｓ１４に戻り、広げた検索範囲で再度検索を行う。
【０１０８】
旧データＤ１の検索範囲において検索対象ブロックと一致するデータブロックを検出できた場合（Ｓ１４：Ｙｅｓ）、もしくは、検索範囲が最大範囲（全範囲）となっている場合（Ｓ１５：Ｙｅｓ）、第１の検索部１１０は、新データＤ１における検索対象ブロックの先頭アドレス位置と、旧データＤ２におけるそのデータブロックの先頭アドレス位置とのズレ量、及び、最終的な検索範囲とを記憶装置に記録する（Ｓ１７）。なお、検索範囲が最大範囲（全範囲）となっている場合（Ｓ１５：Ｙｅｓ）には、第１の検索部１１０は、ズレ量を記録しなくてもよく、ズレ量として所定の無効値などを記録するようにしてもよい。
【０１０９】
そのズレ量が１つ前の検索対象ブロックの検索時のズレ量と異なる場合（Ｓ１８：Ｎｏ）、第１の検索部１１０は、Ｓ１５に進み、次の検索対象ブロックの検索を開始する。第１の検索部１１０は、新データＤ２の検索開始位置をスキップサイズだけスキップし、旧データＤ１の検索開始位置もそれと同一位置とする（Ｓ１９）。そのズレ量が１つ前の検索対象ブロックの検索時のズレ量と同一である場合（Ｓ１８：Ｙｅｓ）、第１の検索部１１０は、新データＤ２の検索開始位置をスキップサイズだけスキップし、旧データＤ１の検索開始位置をその新データＤ２のスキップした検索開始位置にそのズレ量を加算した位置とする（Ｓ２０）。なお、検索範囲が最大範囲（全範囲）となっていた場合（Ｓ１５：Ｙｅｓ）には、検索対象ブロックと一致するデータブロックを検出できておらず、ズレ量を検出できてないため、無条件にＳ１７に進むようにすればよい。そして、第１の検索部１１０は、Ｓ２１に進み、スキップした位置にデータが存在するか否かを判定する。
【０１１０】
スキップした位置にデータが存在する場合（Ｓ２１：Ｎｏ）、第１の検索部１１０は、Ｓ１３に戻り、新たな検索開始位置について検索を開始する。スキップした位置にデータが存在しない場合（Ｓ２１：Ｙｅｓ）、新データＤ２の最後まで一致するデータの検索が終了したことになるため、第１の検索部１１０は、第１の検索処理を終了する。
【０１１１】
続いて、図１１を参照して、図９のＳ３にかかる第２の検索処理について説明する。
【０１１２】
第２の検索では、検索単位として１Ｋバイトが予め定められているものとする（Ｓ３０）。第２の検索開始時には、第２の検索部１３０は、新データＤ２の検索開始位置として新データＤ２の先頭を設定し、旧データＤ１の検索開始位置として新データＤ２の検索開始位置に最初の区間における検索開始位置ズレ量を加算した位置を設定する（Ｓ３１）。また、第２の検索部１３０は、検索範囲として、その区間における検索範囲を設定する（Ｓ３２）。
【０１１３】
旧データＤ１の検索範囲において検索対象ブロックと一致するデータを検出できなかった場合（Ｓ３３：Ｎｏ）、第２の検索部１３０は、新データＤ２の検索開始位置をその検索対象ブロックが含まれる区間におけるスキップサイズだけスキップし、旧データＤ１の検索開始位置をその新データＤ２のスキップ後の検索開始位置にその新データＤ２のスキップ後の区間における検索開始位置ズレ量を加算した位置とする（Ｓ３４）。そして、第２の検索部１３０は、Ｓ３９に進み、スキップした位置にデータが存在するか否かを判定する。
【０１１４】
旧データＤ１の検索範囲において検索対象ブロックと一致するデータを検出できた場合（Ｓ３３：Ｙｅｓ）、第２の検索部１３０は、前後の連続した領域について追込検索を行う（Ｓ３５）。第２の検索部１３０は、新データＤ２において、１つ前に検出した連続一致領域の末尾から、追込検索によって認識した連続一致領域の先頭までの連続不一致領域を挿入データとして差分データ生成部１４０に出力する（Ｓ３６）。また、第２の検索部１３０は、その旧データＤ１の連続一致領域の参照アドレスを示す参照アドレス情報を差分データ生成部１４０に出力する（Ｓ３７）。そして、第２の検索部１３０は、次の連続不一致領域（連続一致部分の末尾）まで、新データＤ２及び旧データＤ１における検索開始位置を進める（Ｓ３８）。そして、第２の検索部１３０は、Ｓ３４及びＳ３９に進み、そこから更にスキップした位置にデータが存在するか否かを判定する。
【０１１５】
スキップした位置にデータが存在する場合（Ｓ３９：Ｎｏ）、第２の検索部１３０は、Ｓ３２に戻り、新たな検索開始位置について検索を開始する。スキップした位置にデータが存在しない場合（Ｓ３９：Ｙｅｓ）、新データＤ２の最後まで一致するデータの検索が終了したことになるため、第２の検索部１３０は、第２の検索処理を終了する。このとき、新データＤ２においてスキップ前の位置以降からスキップした位置までの間にデータが存在する場合には、第２の検索部１３０は、挿入データとして差分データ生成部１４０に出力するようにすればよい。
【０１１６】
本実施のデータ処理装置１００は、第１の検索で粗い検索を行い、どこからどこの範囲では、どの程度ずらして、どのスキップサイズで、どの範囲内で検索行うか、という情報を得て、第２の検索の検索条件を最適に決定する。さらに、第２の検索では、追込検索を実施することにより、検出漏れを軽減することができる。結果的に、新データと旧データ間の差分の検出速度と精度を両立させる効果を得ることができる。
【０１１７】
続いて、図１２を参照して、図９のＳ２にかかる検索条件決定部１２０の処理について説明する。
【０１１８】
検索条件決定部１２０は、次に説明する処理により、第１の検索部１１０の検索結果を参照して新データＤ２を複数の区間に分ける。検索条件決定部１２０は、第１の検索部１１０の検索結果を参照し、その検索結果の先頭のズレ量αと検索範囲を取得し、区間における最初のズレ量α及び検索範囲として記憶装置に記憶する（Ｓ４０）。続いて、検索条件決定部１２０は、次の検索結果（ズレ量αと検索範囲）の記録が記憶装置にある場合（Ｓ４１：Ｙｅｓ）、次のズレ量αと検索範囲を取得する（Ｓ４２）。
【０１１９】
検索条件決定部１２０は、区間の最初のズレ量αとして記憶したズレ量αと、Ｓ４２で取得したズレ量とを比較する（Ｓ４３）。比較したズレ量αの差がズレ量差閾値以下である場合（Ｓ４４：Ｎｏ）、検索条件決定部１２０は、区間の最初の検索範囲として記憶した検索範囲と、Ｓ４２で取得した検索範囲とを比較する（Ｓ４５）。比較した検索範囲の差が検索範囲差閾値以下である場合（Ｓ４６：Ｎｏ）、検索条件決定部１２０は、Ｓ４１に戻り、次のズレ量及び検索範囲についての比較を行う。
【０１２０】
比較したズレ量αの差がズレ量差閾値よりも大きい場合（Ｓ４４：Ｙｅｓ）、及び、比較した検索範囲の差が検索範囲差閾値よりも大きい場合（Ｓ４６：Ｙｅｓ）、検索条件決定部１２０は、Ｓ４２で取得した検索結果（ズレ量又は検索範囲）と、その１つ前の検索結果との間が、第２の検索における区間の切れ目であると確定し、その検索結果にマークを付けておく（Ｓ４７）。ここで、このマークの付与の仕方は、任意の方法を採用してよい。例えば、上述のように区間の最初となる検索結果（ズレ量又は検索範囲）に、そのことを示す情報をマークとして付与して記憶装置に記憶するようにしてもよく、区間の最後となる検索結果（ズレ量又は検索範囲）に、そのことを示す情報をマークとして付与して記憶装置に記憶するようにしてもよい。
【０１２１】
なお、ここでの動作は、ズレ量又は検索範囲の測定にノイズが混入した場合にそれを取り除く効果を与えるものである。すなわち、比較したズレ量又は検索範囲の差が、一致するか否かではなく、閾値を超えたか否かによって区間の切れ目を検出することで、ノイズによって一致しないと判定され、区間数が検索結果（ズレ量又は検索範囲）の数とほぼ同数にまで増大することを防止している。よって、例えば、所定数単位毎に検索結果（ズレ量及び検索範囲）の平均を取って、その平均値を比較することで、その単位をズレ量又は検索範囲の変化による区間の切れ目を検出する単位とするようにしてもよい。
【０１２２】
また、検索条件決定部１２０は、これにより決定した区間（Ｓ４２で取得した検索結果の１つ前の検索結果までの区間）について、その区間における代表ズレ量と代表検索範囲とを算出し、記憶装置に記憶する（Ｓ４８）。なお、代表ズレ量及び代表検索範囲として、その最大値又は最小値を採用する場合には、Ｓ４２で新たに取得したズレ量と検索範囲を取得する毎に、その時点で最大値又は最小値として記憶しているズレ量と検索範囲と比較し、Ｓ４２で新たに取得したズレ量と検索範囲の方が大きい又は小さいときに、そのＳ４２で新たに取得したズレ量と検索範囲を最大値又は最小値として更新していくようにしてもよい。
【０１２３】
また、このように区間が決定したら、Ｓ４２で取得したズレ量及び検索範囲を、次の区間における最初のズレ量及び検索範囲として決定し、次の区間のズレ量及び検索範囲の比較に備える（Ｓ４９）。
【０１２４】
なお、以上の説明では、ズレ量の変化による区間分けがなされなかった場合に、検索範囲の広さの変化に基づいて区間分けをする処理となっているが、これに限られない。例えば、検索範囲の広さの変化による区間分けがなされなかった場合に、ズレ量の変化に基づいて区間分けをするようにしてもよい。
【０１２５】
以上に説明したように、本実施の形態では、第１の検索部１１０は、第１の検索において、新データＤ２のデータ部分（検索対象ブロック）と一致するデータ部分（データブロック）を旧データＤ１から検出するまで、旧データＤ１の検索範囲を徐々に広げて検索するとともに、最終的な検索範囲を記録するようにしている。そして、検索条件決定部１２０は、第２の検索部１３０による第２の検索の検索条件として、新データＤ２を分割した複数の区間のそれぞれについて、当該区間について第１の検索で記録された検索範囲の代表値（代表検索範囲）が検索範囲の最大範囲未満である場合には、当該区間における旧データＤ１の検索範囲を、検索範囲の代表値により近い検索範囲となるように決定するようにしている（上記の例では当該区間に対する旧データＤ１の検索範囲を、当該区間における検索範囲の代表値として決定するようにしている）。
【０１２６】
以上、実施の形態をもとに本発明を説明した。実施の形態は例示であり、本発明の主旨から逸脱しない限り、上述した各実施の形態に対してさまざまな変更、増減、組合せを行ってもよい。これらの変更、増減、組合せが行われた変形例も本発明の範囲にあることは、当業者に理解されるところである。
【０１２７】
例えば、データ処理装置１００において、第１の検索部１１０も追込検索を行うようにしてもよい。この場合、追込検索の時間が増えるが、第１の検索部１１０と第２の検索部１３０が同様の検索エンジンを使用することができるため、データ処理装置の構成が簡単になる。
【符号の説明】
【０１２８】
１００  データ処理装置
１１０  第１の検索部
１２０  検索条件決定部
１３０  第２の検索部
１４０  差分データ生成部
【図１】
2015141602.tif 000003
【図２】
2015141602.tif 000004
【図３】
2015141602.tif 000005
【図４】
2015141602.tif 000006
【図５】
2015141602.tif 000007
【図６】
2015141602.tif 000008
【図７】
2015141602.tif 000009
【図８】
2015141602.tif 000010
【図９】
2015141602.tif 000011
【図１０】
2015141602.tif 000012
【図１１】
2015141602.tif 000013
【図１２】
2015141602.tif 000014