(57)【要約】  差分データのサイズ削減効果を高めることが可能な技術を提供することを目的とする。ビットシフト部４ａは、旧データ及び新データの一方のデータを、そのビット列の順方向及び逆方向に、０，１，２，…，ｎビットのそれぞれでシフトすることによって、複数のデータを生成する。コピービット列抽出部４ｂは、複数のデータと、シフトされていない他方のデータとに基づいて、コピービット列情報を抽出する。追加ビット列抽出部４ｃは、新データからコピービット列を除いた追加ビット列情報を抽出する。差分データ生成部６は、コピービット列情報及び追加ビット列情報に基づいて、差分データを作成する。
2016016923.tif 000002
【特許請求の範囲】
【請求項１】
旧データから新データと同じデータを生成するための差分データを作成する差分データ作成システムであって、
前記旧データ及び前記新データの一方のデータを、そのビット列の順方向及び逆方向に、０，１，２，…，ｎビットのそれぞれでシフトすることによって、複数のデータを生成するビットシフト部と、
前記ビットシフト部で生成された前記複数のデータと、前記ビットシフト部でシフトされていない他方のデータとに基づいて、前記旧データと前記新データとに共通するビット列の情報を、コピービット列の情報として抽出するコピービット列抽出部と、
前記新データのうち前記コピービット列以外のビット列の情報を、追加ビット列の情報として抽出する追加ビット列抽出部と、
前記コピービット列の情報と、前記追加ビット列の情報とに基づいて、前記差分データを作成する差分データ作成部と
を備える、差分データ作成システム。
【請求項２】
請求項１に記載の差分データ作成システムであって、
前記コピービット列抽出部は、
前記ビットシフト部で生成された前記複数のデータの一のデータごとに、当該一のデータと、前記ビットシフト部でシフトされていない前記他方のデータとに共通するビット列の情報を、中間コピービット列の情報として抽出する中間コピービット列抽出部と、
前記中間コピービット列抽出部で抽出された複数の前記中間コピービット列の情報に基づいて、前記複数の中間コピービット列のうち互いに重複しない中間コピービット列と、前記複数の中間コピービット列のうち互いに重複する中間コピービット列同士を結合して得られるビット列と、の少なくともいずれか１つを含むビット列の情報を、前記コピービット列の情報として抽出する最終コピービット列抽出部と
を備える、差分データ作成システム。
【請求項３】
請求項２に記載の差分データ作成システムであって、
前記ｎは７であり、
前記中間コピービット列抽出部は、
前記ビットシフト部で生成された前記複数のデータの一のデータごとに、当該一のデータと、前記ビットシフト部でシフトされていない前記他方のデータとに共通するバイト列を抽出し、
前記一のデータのうち抽出された前記バイト列の直前の１バイトに含まれるビットと、前記他方のデータのうち抽出された前記バイト列の直前の１バイトに含まれるビットとが一致するか否かを前記ビット列の前記逆方向の順に判定し、最後に一致する前記一のデータのビットの第１アドレス及び前記他方のデータのビットの第２アドレスを求め、
前記一のデータのうち抽出された前記バイト列の直後の１バイトに含まれるビットと、前記他方のデータのうち抽出された前記バイト列の直後の１バイトに含まれるビットとが一致するか否かを前記ビット列の前記順方向の順に判定し、最後に一致する前記一のデータのビットの第３アドレス及び前記他方のデータのビットの第４アドレスを求め、
前記第１及び第３アドレスの少なくともいずれか１つを、前記ビットシフト部がシフトを行う前のアドレスに補正し、
前記第２及び第４アドレスと、補正された前記第１及び第３アドレスの少なくともいずれか１つとに基づいて、前記中間コピービット列の情報を生成する、差分データ作成システム。
【請求項４】
請求項１に記載の差分データ作成システムであって、
前記差分データ作成部により作成される前記差分データは、
前記旧データに含まれる前記コピービット列のアドレス及び長さを示す情報と、前記新データに含まれる前記追加ビット列及び前記追加ビット列の長さを示す情報とを、前記新データに含まれる前記コピービット列及び前記追加ビット列の、当該新データにおけるアドレス順に並べたデータである、差分データ作成システム。
【請求項５】
請求項１に記載の差分データ作成システムで作成された前記差分データと、前記旧データとに基づいて前記新データと同じ前記データを生成する、データ更新システム。
【請求項６】
旧データから新データと同じデータを生成するための差分データを作成する差分データ作成方法であって、
前記旧データ及び前記新データの一方のデータを、そのビット列の順方向及び逆方向に、０，１，２，…，ｎビットのそれぞれでシフトすることによって複数のデータを生成し、
生成された前記複数のデータと、シフトされていない他方のデータとに基づいて、前記旧データと前記新データとに共通するビット列の情報を、コピービット列の情報として抽出し、
前記新データのうち前記コピービット列以外のビット列の情報を、追加ビット列の情報として抽出し、
前記コピービット列の情報と、前記追加ビット列の情報とに基づいて、前記差分データを作成する、差分データ作成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、旧データから新データと同じデータを生成するための差分データを作成する差分データ作成システム及びその方法、並びに、当該差分データを用いるデータ更新システムに関する。
【背景技術】
【０００２】
旧データから新データと同じデータを生成するための差分データの抽出（作成）について様々な技術が提案されている。【０００３】
例えば、特許文献１に示される技術では、旧データ及び新データをバイト単位で比較し、両者に一致しているバイト列をコピーデータ（Ｍｏｖｅデータ）として抽出するとともに、新データだけに存在するバイト列を追加データとして抽出する。そして、抽出したコピーデータを示すコピーコマンド（Ｍｏｖｅコマンド）と、抽出した追加データを示す追加コマンドとを含む差分データを作成する。【０００４】
コピーコマンドは、コピーデータそのものを含まず、旧データにおけるコピーデータの格納位置及びサイズを示す。通常、コピーデータそのものよりも、コピーデータの格納位置及びサイズの方がデータサイズは小さいので、このようなコピーデータが多くなるほど、差分データのサイズ削減効果が高まることになる。【０００５】
例えば、３２バイトの旧データＡの先頭に、１バイトの挿入データＢが挿入されたデータを、新データＣとする。つまり、３３バイトのデータ｛Ｂ，Ａ｝が、新データＣであったとする。このような場合に、特許文献１に示される技術により抽出される差分データは、下記の追加コマンド及びコピーコマンドを含むことになる。【０００６】
追加コマンド（１バイト）：挿入データＢを示す１バイトの追加データからなる。ただし、デリミタ（０ｘ０Ｆ）以外の値をとるものとする。なお、（０ｘ＊＊）は１６進表記を示すものとする。【０００７】
コピーコマンド（２バイト）：コピーコマンドであることを示す１バイトのデリミタ（０ｘ０Ｆ）と、コピーデータのサイズ（３２バイト）を示す１バイトのデータ（０ｘ２０）とからなる。ここでは旧データＡにおけるコピーデータの先頭アドレスは０であるため、アドレスフィールドは不要である。【０００８】
結果として、旧データＡから新データＣと同じデータを生成するための差分データは、３３バイトのデータではなく３バイトのデータとなるので、差分データのサイズが低減される。このような差分データのサイズ削減効果は、差分データにおいて、コピーデータが増加し、追加データが減少するほど顕著となる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００４−１５２１３６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
さて、データがバイト単位で表され、新データが、旧データのバイト単位の変更（例えば挿入や削除など）によって生成される限りにおいては、特許文献１に示される技術のように、旧データ及び新データの差分をバイト単位で抽出する技術で対応することが可能である。しかしながら、データ削減の観点から、データが必要最低限度のビット数で表され、新データが、旧データのビット単位の変更によって生成される技術も提案されている。【００１１】
当該提案された技術では、例えば、１バイトの挿入データのうち１ビットのみが有効である場合には、旧データに１ビットの挿入データｂが挿入されたデータが、新データとなる。具体例として、旧データＡが、３２バイトつまり２５６ビットのビット列データＡであり、新データＤが、ビット列データＡの先頭に１ビットの挿入データｂが挿入された２５７ビットのビット列データＤである場合を考える。【００１２】
ビット列データＡ（旧データＡ）、ビット列データＤ（新データＤ）は、それぞれ記憶媒体に先頭のビットから順にバイト単位で下記のように格納される。【００１３】
Ａ：ａ１，ａ２，…，ａ３２
Ｄ：ｄ１，ｄ２，…，ｄ３２，ｄ３３【００１４】
新データＤにおいて旧データＡに相当するビット列は、挿入データｂの挿入により、旧データＡを１ビットずれたものとなるため、ｄｉ≠ａｉ（ｉ＝１，２，…，３２）となる。【００１５】
この場合に、バイト単位で格納された旧データＡと新データＤとの差分を、特許文献１の技術のようにバイト単位で抽出すると、ｄｉ≠ａｉ（ｉ＝１，２，…，３２）であることから、コピーデータは抽出されずに、ｄ１〜ｄ３３からなる３３バイトの追加データが抽出されると考えられる。この結果、旧データＡから新データＤと同じデータを生成するための差分データは、３３バイトのデータとなり、差分データのサイズ削減効果が低下してしまう。【００１６】
以上のように、新データが、旧データにビット単位の挿入データを挿入したデータである場合には、特許文献１に示された技術では、差分データにおいて、コピーデータが減少し、かつ追加データが増加するので、差分データのサイズ削減効果が低下するという問題があった。【００１７】
そこで、本発明は、上記のような問題点を鑑みてなされたものであり、差分データのサイズ削減効果を高めることが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明に係る差分データ作成システムは、旧データから新データと同じデータを生成するための差分データを作成する差分データ作成システムであって、旧データ及び新データの一方のデータを、そのビット列の順方向及び逆方向に、０，１，２，…，ｎビットのそれぞれでシフトすることによって、複数のデータを生成するビットシフト部と、ビットシフト部で生成された複数のデータと、ビットシフト部でシフトされていない他方のデータとに基づいて、旧データと新データとに共通するビット列の情報を、コピービット列の情報として抽出するコピービット列抽出部と、新データのうちコピービット列以外のビット列の情報を、追加ビット列の情報として抽出する追加ビット列抽出部と、コピービット列の情報と、追加ビット列の情報とに基づいて、差分データを作成する差分データ作成部とを備える。【００１９】
本発明に係る差分データ作成方法は、旧データから新データと同じデータを生成するための差分データを作成する差分データ作成方法であって、旧データ及び新データの一方のデータを、そのビット列の順方向及び逆方向に、０，１，２，…，ｎビットのそれぞれでシフトすることによって複数のデータを生成し、生成された複数のデータと、シフトされていない他方のデータとに基づいて、旧データと新データとに共通するビット列の情報を、コピービット列の情報として抽出し、新データのうちコピービット列以外のビット列の情報を、追加ビット列の情報として抽出し、コピービット列の情報と、追加ビット列の情報とに基づいて、差分データを作成する。
【発明の効果】
【００２０】
本発明によれば、旧データ及び新データのうち、ビット列の順方向及び逆方向に０，１，２，…，ｎビットの範囲でシフトした一方のデータと、シフトされていない他方のデータとに基づいて、コピービット列の情報及び追加ビット列の情報を求める。このため、旧データと新データとの間にビット単位のずれが発生していても、差分データにおいて、コピービット列を増加させることができ、追加ビット列を減少させることができる。この結果、差分データのサイズ削減効果を高めることができる。【００２１】
本発明の目的、特徴、態様および利点は、以下の詳細な説明と添付図面とによって、より明白となる。
【図面の簡単な説明】
【００２２】
【図１】実施の形態１に係る差分データ作成装置及びデータ更新装置を示すブロック図である。
【図２】実施の形態１に係る差分データ作成装置の構成例を示すブロック図である。
【図３】実施の形態１に係るデータ更新装置の構成例を示すブロック図である。
【図４】実施の形態１に係る情報処理装置の構成例を示すブロック図である。
【図５】実施の形態１に係る旧データ及び新データの構成例を示す図である。
【図６】実施の形態１に係る旧データ及び新データの関係を示す図である。
【図７】実施の形態１に係る旧データから新データへの変更例を示す図である。
【図８】実施の形態１に係る旧データから新データへの変更例を示す図である。
【図９】実施の形態１に係る旧データから新データへの変更例を示す図である。
【図１０】実施の形態１に係る旧データから新データへの変更例を示す図である。
【図１１】実施の形態１に係る旧データから新データへの変更例を示す図である。
【図１２】実施の形態１に係る旧データ及び新データの構成例を示す図である。
【図１３】実施の形態１に係る旧データ及び新データの構成例を示す図である。
【図１４】実施の形態１に係る差分データ作成装置の処理の一例を示す図である。
【図１５】実施の形態１に係る差分抽出部及び差分データ生成部の構成例を示すブロック図である。
【図１６】実施の形態１に係る差分抽出部の動作の一例を示すフローチャートである。
【図１７】実施の形態１に係る中間コピービット列情報の構成例を示す図である。
【図１８】実施の形態１に係るコピービット列情報の構成例を示す図である。
【図１９】実施の形態１に係る追加ビット列情報の構成例を示す図である。
【図２０】実施の形態１に係るビットシフト処理の一例を示すフローチャートである。
【図２１】実施の形態１に係る中間コピービット列情報の抽出処理の一例を示すフローチャートである。
【図２２】実施の形態１に係るバイト差分データの構成例を示す図である。
【図２３】実施の形態１に係る追加コマンドの構成例を示す図である。
【図２４】実施の形態１に係るコピーコマンドの構成例を示す図である。
【図２５】実施の形態１に係る終了コマンドの構成例を示す図である。
【図２６】実施の形態１に係るコピービット列情報の抽出処理の一例を示すフローチャートである。
【図２７】実施の形態１に係る結合コピー範囲の一例を示す図である。
【図２８】実施の形態１に係る追加ビット列情報の抽出処理の一例を示すフローチャートである。
【図２９】実施の形態１に係る追加ビット列情報の抽出処理の一例を示す図である。
【図３０】実施の形態１に係る差分データの構成例を示す図である。
【図３１】実施の形態１に係る追加ビットコマンドの構成例を示す図である。
【図３２】実施の形態１に係るコピービットコマンドの構成例を示す図である。
【図３３】実施の形態１に係る終了コマンドの構成例を示す図である。
【図３４】実施の形態１に係る差分データ生成部の動作の一例を示すフローチャートである。
【図３５】実施の形態１に係るマージ情報の構成例を示す図である。
【図３６】実施の形態１に係るデータ更新動作の一例を示すフローチャートである。
【図３７】実施の形態１に係るデータ更新部の処理の一例を示す図である。
【図３８】実施の形態１に係るデータ更新部の処理の一例を示す図である。
【図３９】実施の形態２に係る差分抽出部及び差分データ生成部の構成例を示すブロック図である。
【図４０】実施の形態２に係る差分データ作成装置の処理の一例を示す図である。
【発明を実施するための形態】
【００２３】
＜実施の形態１＞
以下の説明では、本発明に係る差分データ作成システムが、差分データ作成装置単体に適用され、本発明に係るデータ更新システムが、データ更新装置単体に適用された場合を例にして説明する。
【００２４】
図１は、本発明の実施の形態１に係る差分データ作成装置１の主要な構成と、本発明の実施の形態１に係るデータ更新装置１１とを示すブロック図である。差分データ作成装置１は、旧データから新データと同じデータを生成するための差分データを作成する。旧データ及び新データはビット列データであり、新データは、旧データをビット単位で変更（例えば挿入や削除など）したデータである。
【００２５】
図１の差分データ作成装置１は、ビットシフト部４ａと、コピービット列抽出部４ｂと、追加ビット列抽出部４ｃと、差分データ作成部である差分データ生成部６とを備えている。
【００２６】
ビットシフト部４ａは、旧データ及び新データの一方のデータを、そのビット列の順方向及び逆方向に、０，１，２，…，ｎ（ｎ：自然数）ビットのそれぞれでシフトすることによって、複数のデータを生成する。
【００２７】
ここで、ビット列の順方向には、例えば、データのビットストリームの方向、または、シフトされるデータの最上位ビットから最下位ビットに向かう方向などが適用される。ビット列の逆方向とは、ビット列の順方向と逆の方向である。
【００２８】
本実施の形態１では、上述のｎは７であり、シフトされる一方のデータは新データであるものとする。すなわち、ビットシフト部４ａは、新データを、そのビット列の順方向及び逆方向に、０，１，２，…，７ビットのそれぞれでシフトすることによって、複数のデータ（ここでは１５のデータ）を生成するものとする。
【００２９】
コピービット列抽出部４ｂは、ビットシフト部４ａで生成された複数のデータと、ビットシフト部４ａでシフトされていない他方のデータとに基づいて、旧データと新データとに共通するビット列の情報を、コピービット列情報（コピービット列の情報）として抽出する。本実施の形態１では、一方のデータは新データであることから、ここでいう他方のデータは旧データである。
【００３０】
追加ビット列抽出部４ｃは、新データのうちコピービット列以外のビット列の情報を、追加ビット列情報（追加ビット列の情報）として抽出する。
【００３１】
差分データ生成部６は、コピービット列情報と、追加ビット列情報とに基づいて、差分データを生成（作成）する。
【００３２】
図１のデータ更新装置１１は、差分データ作成装置１で生成された差分データを、差分データ作成装置１から取得する。そして、データ更新装置１１は、当該差分データと旧データとに基づいて、新データと同じデータを生成する。
【００３３】
＜差分データ作成装置＞
ここでは、差分データ作成装置１の主要な構成要素だけでなく、付加的な構成要素についても説明する。
【００３４】
図２は、本実施の形態１に係る差分データ作成装置１の主要な構成及び付加的な構成例を示すブロック図である。図２の差分データ作成装置１は、データ入力部２と、データ記憶部３と、差分抽出部４と、中間データ記憶部５と、差分データ生成部６と、差分データ記憶部７と、差分データ出力部８とを備えている。
【００３５】
データ入力部２には、例えば図示しないデータ作成装置などの外部が作成した旧データ及び新データ、または、例えば図示しない半導体メモリ、Digital Versatile Disk（ＤＶＤ）などの記憶媒体に格納された旧データ及び新データが入力される。
【００３６】
データ記憶部３は、データ入力部２に入力された旧データ及び新データを格納する。
【００３７】
差分抽出部４は、図１のビットシフト部４ａ、コピービット列抽出部４ｂ及び追加ビット列抽出部４ｃを備えている。このため、差分抽出部４は、新データをシフトしたり、コピービット列情報を抽出したり、追加ビット列情報を抽出したりする。ここでは、差分抽出部４は、データ記憶部３に格納された旧データ及び新データから、コピービット列情報及び追加ビット列情報を抽出する。
【００３８】
中間データ記憶部５は、コピービット列情報の抽出における途中段階の結果を格納する。ここで、途中段階の結果は、後述する中間コピービット列情報（中間コピービット列の情報）に相当する。
【００３９】
差分データ生成部６は、図１の差分データ生成部６と同じであり、差分抽出部４の抽出結果（コピービット列情報及び追加ビット列情報）に基づいて差分データを生成する。
【００４０】
差分データ記憶部７は、差分データ生成部６で生成された差分データを格納する。
【００４１】
差分データ出力部８は、差分データ記憶部７に格納された差分データを、図示しない半導体メモリ、ＤＶＤなどの記憶媒体に格納することによって図３のデータ更新装置１１または図４の情報処理装置２１に提供するか、図示しない通信網を介して図３のデータ更新装置１１または図４の情報処理装置２１に提供する。
【００４２】
なお、データ記憶部３、中間データ記憶部５及び差分データ記憶部７には、例えば図示しないハードディスクドライブ（ＨＤＤ）や半導体メモリなどの記憶装置から構成される。差分抽出部４及び差分データ生成部６は、例えば差分データ作成装置１の図示しない一または複数のCentral Processing Unit（ＣＰＵ）が、図示しない内部メモリなどの記憶装置に格納されたプログラムを実行することにより、当該ＣＰＵの機能として実現される。
【００４３】
＜データ更新装置＞
図３は、本実施の形態１に係るデータ更新装置１１の構成例を示すブロック図である。図３のデータ更新装置１１は、差分データ入力部１２と、差分データ記憶部１３と、データ記憶部１４と、データ更新部１５とを備えている。
【００４４】
差分データ入力部１２には、差分データ作成装置１により記憶媒体に格納された差分データが入力されるか、差分データ作成装置１から通信網を介して差分データが入力される。なお、差分データ入力部１２には、外部から旧データも入力されてもよい。
【００４５】
差分データ記憶部１３は、差分データ入力部１２に入力された差分データを格納する。
【００４６】
データ記憶部１４は、予め旧データを格納する。なお、差分データ入力部１２に旧データが入力された場合には、データ記憶部１４は当該旧データを格納してもよい。
【００４７】
データ更新部１５は、データ記憶部１４に格納された旧データと、差分データ記憶部１３に格納された差分データとに基づいて、新データと同じデータを生成する。
【００４８】
新データはデータ記憶部１４に格納される。新データは、半導体メモリ、ＤＶＤなどの記憶媒体または通信網を介して外部に出力されてもよい。
【００４９】
なお、差分データ記憶部１３及びデータ記憶部１４には、例えば図示しないＨＤＤや半導体メモリなどの記憶装置から構成される。データ更新部１５は、例えばデータ更新装置１１の図示しないＣＰＵが、図示しない内部メモリなどの記憶装置に格納されたプログラムを実行することにより、当該ＣＰＵの機能として実現される。
【００５０】
＜情報処理装置＞
図４は、本実施の形態１に係る情報処理装置２１の構成例を示すブロック図である。図４の情報処理装置２１は、差分データ入力部２２と、差分データ記憶部２３と、データ記憶部２４と、データ更新部２５と、位置検出部２６と、操作入力部２７と、情報処理部２８と、表示部２９とを備えている。この情報処理装置２１は、内部に図３のデータ更新装置１１の構成（差分データ入力部１２、差分データ記憶部１３、データ記憶部１４、データ更新部１５）と同様の構成を備えており、当該構成により得られる新データを用いて各種情報処理を行う。
【００５１】
データ記憶部２４は、古い地図情報（旧データ）を格納する。また、データ記憶部２４は、上述の更新により得られる新しい地図情報（新データ）を格納する。
【００５２】
位置検出部２６は、情報処理装置２１を搭載した移動体や通信端末（例えば携帯電話、スマートフォン、及びタブレットなどの携帯端末）の位置を検出する。位置検出部２６は、例えば、ＧＰＳ（Global Positioning System）衛星からのＧＰＳ信号を受信するＧＰＳ受信機などから構成される。
【００５３】
操作入力部２７は、目的地の指定操作など、情報処理装置２１に対する各種操作を、使用者などから受け付ける。
【００５４】
情報処理部２８は、操作入力部２７で受け付けた使用者の操作の従い、位置検出部２６で検出した位置を元にデータ記憶部２４から所要の地図情報を取得し、当該地図情報が示す地図と、位置検出部２６で検出した位置とを表示部２９に表示させる。また、情報処理部２８は、現在地（位置検出部２６で検出した位置）から目的地までの経路の探索、及び、経路誘導、その他のナビゲーション処理も行う。
【００５５】
地図情報は、交差点を表すノードと交差点間を結ぶ道路を表すリンクとを用いて道路網を表す情報と、地形の形状を表す情報とを含んでいる。ノード、リンクの数は地域によって異なり、それらを識別するために付与する識別番号の最大値は地域によって異なる。また、道路形状、地形は、形状の変化分を用いて表され、道路、地形の特性により形状変化分がばらつく。このため、地図情報では、各要素を表すために必要な最小限のフィールド長さのばらつきが比較的大きく、各要素をバイト単位またはワード単位の長さのフィールドで表すと、必要以上にデータサイズが増大することになる。そこで、地図情報のデータサイズを削減する方式として、各要素を表すフィールドはビット単位の可変長であるとし、フィールド長さは必要最低限の長さに変更可能とする方式が望ましい。
【００５６】
本実施の形態１に係る差分データ作成装置１では、このような地図情報などのように、ビット単位で変更されるデータについて、上述の差分データのサイズを抑制することが可能となっている。
【００５７】
＜旧データ及び新データ＞
地図情報などに適用される旧データ及び新データは、複数のビットを並べたビット列からなるデータ、すなわちビット列データであるとする。ビット列の各ビットは、ビットアドレスを用いて特定される。ここでは、ビットアドレスは、一のビットがビット列データの先頭のビットから何番目に位置するかを表し、先頭のビットから順に０，１，２，…の番号が付与される。
【００５８】
図５は、本実施の形態１に係る旧データ及び新データの構成例を示す図である。
【００５９】
図５に示される旧データのビット列（旧ビット列ＢＳ０）では、０か１の値が付与されたビットが、下記のように先頭（最上位ビット）から末尾（最下位ビット）に向かって順に並べられている。
【００６０】
e(0),e(1),e(2),…,e(lngBS0-1)
e(p)：ビットアドレスがpのビット(p=0,1,2,…,lngBS0-1)
lngBS0：旧ビット列BS0のビット列長
【００６１】
図５に示される新データのビット列（新ビット列ＢＳ１）は、旧ビット列ＢＳ０にビット単位のデータの削除、挿入、置き換え、追加などの変更が行われたビット列である。この新ビット列ＢＳ１でも、０か１の値が付与されたビットが、下記のように先頭（最上位ビット）から末尾（最下位ビット）に向かって順に並べられている。
【００６２】
a(0),a(1),a(2),…,a(lngBS1-1)
a(p)：ビットアドレスがpのビット(p=0,1,2，…，lngBS1-1)
lngBS1：新ビット列BS1のビット列長
【００６３】
図６は、実施の形態１に係る旧データ及び新データの関係を示す図である。
【００６４】
新ビット列ＢＳ１は、旧ビット列ＢＳ０と共通する部分ビット列（以下「コピービット列」と記す）Ｅ（ｉ）と、変更により新規に生じた旧ビット列ＢＳ０と共通しない部分ビット列（以下「追加ビット列」と記す）Ａ（ｉ）とを含んでいる。新ビット列ＢＳ１は、例えば下記のようなコピービット列Ｅ（ｉ）及び追加ビット列Ａ（ｉ）の並びとして表すことができる。
【００６５】
A(0),E(0),A(1),E(1),…,A(numE-1),E(numE-1),A(numE)
A(i)：変更により新規に発生した追加ビット列(i=0,1,…,numE)
なお、A(i)のビット長は０であってもよい
E(i)：新ビット列BS1，旧ビット列BS0に共通するコピービット列(i=0,1,…,numE-1)
numE：コピービット列の数
【００６６】
各コピービット列Ｅ（ｉ）の各ビットの並びは下記となる。下記では、旧ビット列ＢＳ０における、コピービット列Ｅ（ｉ）の先頭のビットアドレスａｄｒＥ（ｉ）が記載されている。新ビット列ＢＳ１における、コピービット列Ｅ（ｉ）の先頭のビットアドレスについては、また後ほど説明する。
【００６７】
e(adrE(i)),e(adrE(i)+1),e(adrE(i)+2),…,e(adrE(i)+lngE(i)-1)
e(p)：旧ビット列BS0におけるビットアドレスがpのビット
(adrE(i)≦p≦adrE(i)+lngE(i)-1)
adrE(i)：旧ビット列BS0における、コピービット列E(i)の先頭のビットアドレス
lngE(i)：コピービット列E(i)のビット列長（＞０）
【００６８】
各追加ビット列Ａ（ｉ）の各ビットの並びは下記となる。なお、コピービット列Ｅ（ｉ）は、旧ビット列ＢＳ０及び新ビット列ＢＳ１に存在するが、追加ビット列Ａ（ｉ）は、新ビット列ＢＳ１のみに存在する。
【００６９】
a(adrA(i)),a(adrA(i)+1),a(adrA(i)+２),…,a(adrA(i)+lngA(i)-1)
a(p)：新ビット列BS1におけるビットアドレスがpのビット
（adrA(i)≦ｐ≦adrA(i)＋lngA(i)−１）
adrA(i)：新ビット列BS1における、追加ビット列A(i)の先頭のビットアドレス
lngA(i)：追加ビット列A(i)のビット列長（≧０）
【００７０】
旧ビット列ＢＳ０（旧データ）のコピービット列Ｅ（ｉ）をコピーしつつ、追加ビット列Ａ（ｉ）を追加すれば、新ビット列ＢＳ１（新データ）が得られる。このことに鑑みて、差分データは、コピービット列Ｅ（ｉ）及び追加ビット列Ａ（ｉ）に関する情報を含むように生成される。
【００７１】
なお、旧データから新データへの変更として、削除、挿入、置き換え及び追加の少なくとも１つが想定される。このような変更の例を図７から図１１に示す。
【００７２】
図７は、旧ビット列ＢＳ０のコピービット列Ｅ（ｉ），Ｅ（ｉ＋１）の間にある部分ビット列Ｘ１を削除した例を示す図である。ただし、新ビット列ＢＳ１において追加ビット列Ａ（ｉ＋１）のビット長は０とする。
【００７３】
図８は、旧ビット列ＢＳ０のコピービット列Ｅ（ｉ），Ｅ（ｉ＋１）の間に追加ビット列Ａ（ｉ＋１）を追加した例を示す図である。
【００７４】
図９は、旧ビット列ＢＳ０のコピービット列Ｅ（ｉ），Ｅ（ｉ＋１）の間にある部分ビット列Ｘ２を追加ビット列Ａ（ｉ＋１）に置き換えた例を示す図である。
【００７５】
図１０は、旧ビット列ＢＳ０の末尾を含む部分ビット列Ｘ３を追加ビット列Ａ（ｎｕｍＥ）に置き換えた例を示す図である。
【００７６】
図１１は、旧ビット列ＢＳ０の末尾に追加ビット列Ａ（ｎｕｍＥ）を追加した例を示す図である。
【００７７】
以上のような変更を行うと、多くの場合において、コピービット列Ｅ（ｉ）の新ビット列ＢＳ１のビットアドレスは、旧ビット列ＢＳ０のビットアドレスからずれることになる。コピービット列Ｅ（ｉ）の先頭のビットアドレスは、旧ビット列ＢＳ０においては上述したビットアドレスａｄｒＥ（ｉ）であるが、新ビット列ＢＳ１においては次式（１）に示されるビットアドレスａｄｒ１Ｅ（ｉ）となる。
【００７８】
【数１】
2016016923.tif 000003
【００７９】
図６には、ビットアドレスａｄｒ１Ｅ（ｉ）の一例として、新ビット列ＢＳ１における、コピービット列Ｅ（２）の先頭のビットアドレスａｄｒ１Ｅ（２）が示されている。
【００８０】
＜ビット列データのファイル＞
旧ビット列ＢＳ０及び新ビット列ＢＳ１は、例えばファイルＦ０及びファイルＦ１としてデータ記憶部３にそれぞれ格納される。
【００８１】
図１２は、旧ビット列ＢＳ０及び新ビット列ＢＳ１が、ファイルＦ０及びファイルＦ１として格納されている例を示す図である。
【００８２】
ファイルＦ０の先頭には、旧ビット列ＢＳ０のビット列の長さを示すビット列長ｌｎｇＢＳ０が３２ビットの非負整数として格納され、その直後に旧ビット列ＢＳ０に対応するデータＤ０がマトリクス状に格納される。旧ビット列ＢＳ０は、先頭のビットから順に８ビットごとにｂｙｌｎｇＤ０（＝ｌｎｇＢＳ０／８，ただし余りは切り上げ）バイトのデータとして格納される。なお、最後の１バイトの余りのビットには０を格納する。
【００８３】
上述と同様に、新ビット列ＢＳ１もファイルＦ１として格納される。つまり、新ビット列ＢＳ１のビット列長ｌｎｇＢＳ１が３２ビットの非負整数として格納され、その直後に新ビット列ＢＳ１に対応するデータＤ１がマトリクス状に格納される。新ビット列ＢＳ１は、先頭のビットから順に８ビットごとにｂｙｌｎｇＤ１（＝ｌｎｇＢＳ１／８，ただし余りは切り上げ）バイトのデータとして格納される。なお、最後の１バイトの余りのビットには０を格納する。
【００８４】
データＤ０，Ｄ１の各バイトはオフセットを用いて特定される。ここで、オフセットとは、着目するバイトが、データＤ０またはデータＤ１の先頭のバイトから何番目に位置するかを表す。オフセットは、例えば先頭のバイトから順に０，１，２，…の番号が付与される。
【００８５】
データＤ０，Ｄ１の各バイトの各ビットはビット番号を用いて特定される。ここで、ビット番号とは、着目するビットが、一のバイトをなす８つのビットのうち何番目に位置するかを表す。ビット番号は、例えば、最上位から最下位のビットに向かって（ビット列の順方向に向かって）順に７，６，５，４，３，２，１，０の番号が付与される。
【００８６】
図１３は、データＤ０，Ｄ１における一のコピービット列Ｅ（ｉ）（図６）の一例を示す図である。図１３において砂地ハッチングが付された個所が、コピービット列に対応し、斜線ハッチングが付された個所が、追加ビット列に対応する。
【００８７】
上述したように、コピービット列Ｅ（ｉ）が旧ビット列ＢＳ０に占めるビットアドレスは、ａｄｒＥ（ｉ）〜ａｄｒＥ（ｉ）＋ｌｎｇＥ（ｉ）−１であるため、旧ビット列ＢＳ０におけるコピービット列Ｅ（ｉ）の先頭及び末尾のビットのオフセット及びビット番号は下記となる。なお、以下においては、”／”は除算の商、”％”は除算の剰余を算出する演算を示すものとする。
【００８８】
コピービット列E(i)の先頭ビットのオフセット：ofsEs(i)=adrE(i)/8
コピービット列E(i)の先頭ビットのビット番号：bitnEs(i)=7-adrE(i)%8
コピービット列E(i)の末尾ビットのオフセット：ofsEe(i)=(adrE(i)+lngE(i)-1)/8
コピービット列E(i)の末尾ビットのビット番号：bitnEe(i)=7-(adrE(i)+lngE(i)-1)%8
【００８９】
上述したように、コピービット列Ｅ（ｉ）が新ビット列ＢＳ１に占めるビットアドレスは、ａｄｒ１Ｅ（ｉ）〜ａｄｒ１Ｅ（ｉ）＋ｌｎｇＥ（ｉ）−１であるため、新ビット列ＢＳ１におけるコピービット列Ｅ（ｉ）の先頭及び末尾のビットのオフセット及びビット番号は下記となる。
【００９０】
コピービット列E(i)の先頭ビットのオフセット：ofsAs(i)=adr1E(i)/8
コピービット列E(i)の先頭ビットのビット番号：bitnAs(i)=7-adr1E(i)%8
コピービット列E(i)の末尾ビットのオフセット：ofsAe(i)=(adr1E(i)+lngE(i)-1)/8
コピービット列E(i)の末尾ビットのビット番号：bitnAe(i)=7-(adr1E(i)+lngE(i)-1)%8
【００９１】
データＤ１に含まれるコピービット列Ｅ（ｉ）のビットアドレスは、データＤ０に含まれるコピービット列Ｅ（ｉ）のビットアドレスに対して、オフセットの違いを除くと、下記のＳ（ｉ）のビットだけずれている。
【００９２】
S(i)=bitnAs(i)-bitnEs(i)
【００９３】
Ｓ（ｉ）＞０である場合には、新ビット列ＢＳ１のコピービット列Ｅ（ｉ）は、旧ビット列ＢＳ０のコピービット列Ｅ（ｉ）よりも、新ビット列ＢＳ１の末尾（ビット列の順方向）にずれていることを意味する。Ｓ（ｉ）＜０である場合には、新ビット列ＢＳ１のコピービット列Ｅ（ｉ）は、旧ビット列ＢＳ０のコピービット列Ｅ（ｉ）よりも、新ビット列ＢＳ１の先頭（ビット列の逆方向）にずれていることを意味する。Ｓ（ｉ）＝０である場合には、ずれがないことを意味する。
【００９４】
また、０≦ｂｉｔｎＡｓ（ｉ）＜８、０≦ｂｉｔｎＥｓ（ｉ）＜８であるから、０≦｜Ｓ（ｉ）｜＜８となる。つまり、オフセットの違いを無視すれば、データＤ１におけるコピービット列Ｅ（ｉ）のビットアドレスは、データＤ０におけるコピービット列Ｅ（ｉ）のビットアドレスに対して、ビット単位のずれがないか、末尾方向（ビット列の順方向）に１〜７ビットだけずれているか、先頭方向（ビット列の逆方向）に１〜７ビットだけずれているかのいずれかとなる。
【００９５】
なお、図１３の例ではＳ（ｉ）＝２、つまり、新ビット列ＢＳ１のコピービット列Ｅ（ｉ）が、旧ビット列ＢＳ０のコピービット列Ｅ（ｉ）よりも、新ビット列ＢＳ１の末尾（ビット列の順方向）に２ビットだけずれている。
【００９６】
さて、Ｓ（ｉ）＝０の場合や、同じ値が連続するなどの特殊な場合には、データＤ０のうちオフセット範囲がｏｆｓＥｓ（ｉ）〜ｏｆｓＥｅ（ｉ）のバイト列と、データＤ１のうちオフセット範囲がｏｆｓＡｓ（ｉ）〜ｏｆｓＡｅ（ｉ）のバイト列とは一致する。しかしながら、通常は、上述のようなビット単位のずれが存在するので、これらバイト列は多くの場合において一致しない。
【００９７】
それにも関わらず、従来の技術では、データＤ０のコピービット列Ｅ（ｉ）と、データＤ１のコピービット列Ｅ（ｉ）とがビット単位でずれたままの状態で、バイト単位の差分を求める。このため、オフセット範囲がｏｆｓＥｓ（ｉ）〜ｏｆｓＥｅ（ｉ）内のコピービット列Ｅ（ｉ）を抽出することができず、差分データにおいて、コピービット列が減少し、追加ビット列が増加することが多かった。その結果、差分データのサイズ削減効果が低下するという問題があった。
【００９８】
これに対して、本実施の形態１に係る差分データ作成装置１によれば、以下の説明で明らかとなるように、差分データにおいて、コピービット列を増加させることができ、及び、追加ビット列を減少させることができるので、差分データのサイズ削減効果を高めることが可能となっている。
【００９９】
＜コピービット列及び追加ビット列の抽出の概要＞
図１４は、差分データ作成装置１によって図６の一のコピービット列Ｅ（ｉ）を抽出する処理の一例を示す図である。データＤ１＿ｓは、データＤ１の各ビットを、−Ｓ（ｉ）（＝−２）のビットだけビット列の順方向にシフトしたデータ、つまり、２ビットだけビット列の逆方向にシフトしたデータである。なお、データＤ１をシフトすべき適切なシフト量（ここでは−Ｓ（ｉ））は未知数であるが、これに対する手当については後で詳細に説明するものとし、ここでは、適切なシフト量が既知であったとして説明する。
【０１００】
図１４に示されるように、当該シフトにより、データＤ０のうちオフセット範囲がｏｆｓＥｓ（ｉ）〜ｏｆｓＥｅ（ｉ）のバイト列と、データＤ１＿ｓのうちオフセット範囲がｏｆｓＡｓ（ｉ）〜ｏｆｓＡｅ（ｉ）のバイト列との間のずれが解消される。
【０１０１】
データＤ０と、ビット単位のずれが解消されたデータＤ１＿ｓとを、従来の方法と同様にバイト単位で比較して差分を求めると、データＤ０のうちオフセット範囲がｏｆｓＥｓ（ｉ）＋１〜ｏｆｓＥｅ（ｉ）−１であるバイト列が、少なくともコピービット列として抽出される。以下の説明では、このオフセット範囲のバイト列を形成するビット列をビット列ＭＩとする。
【０１０２】
図１４に示すように、データＤ１（新データ）のうち、オフセットがｏｆｓＡｓ（ｉ）である一のバイト列、つまりコピービット列Ｅ（ｉ）の先頭部分のビット列を含む一のバイト列は、斜線ハッチングが付された追加ビット列を含むことがある。このため、データＤ０のうちオフセットがｏｆｓＥｓ（ｉ）である一のバイト列全体と、データＤ１＿ｓのうちオフセットがｏｆｓＡｓ（ｉ）である一のバイト列全体とは、バイト単位では一致しないことがある。この結果、バイト単位の比較及び差分では、コピービット列Ｅ（ｉ）の先頭部分のビット列、つまり図１４の太線で囲まれるビット列ＳＴが抽出されないことがあると考えられる。
【０１０３】
このことはコピービット列Ｅ（ｉ）の末尾部分のビット列においても同様である。つまり、データＤ０のうちオフセットがｏｆｓＥｅ（ｉ）である一のバイト列全体と、データＤ１＿ｓのうちオフセットがｏｆｓＡｅ（ｉ）である一のバイト列全体とは、バイト単位では一致しないことがある。この結果、バイト単位の比較及び差分では、コピービット列Ｅ（ｉ）の末尾部分のビット列、つまり図１４の太線で囲まれるビット列ＥＮが抽出されないと考えられる。
【０１０４】
そこで、本実施の形態１では、差分抽出部４は、データＤ０のうちオフセットがｏｆｓＥｓ（ｉ）である一のバイト列と、データＤ１＿ｓのうちオフセットがｏｆｓＡｓ（ｉ）である一のバイト列については、バイト単位ではなくビット単位で比較して差分を求める。これにより、バイト単位の比較及び差分では抽出できなかった、図１４の太線で囲まれるビット列ＳＴを抽出することができる。
【０１０５】
同様に、差分抽出部４は、データＤ０のうちオフセットがｏｆｓＥｅ（ｉ）である一のバイト列と、データＤ１＿ｓのうちオフセットがｏｆｓＡｅ（ｉ）である一のバイト列についても、バイト単位ではなくビット単位で比較して差分を求める。これにより、バイト単位の比較及び差分では抽出できなかった、図１４の太線で囲まれるビット列ＥＮを抽出することができる。
【０１０６】
上述のビット列ＭＩ、ビット列ＳＴ及びビット列ＥＮを合わせることにより、図６の一のコピービット列Ｅ（ｉ）が抽出される。
【０１０７】
さて、上述したように、データＤ１をシフトすべき適切なシフト量は未知であるが、０≦｜Ｓ（ｉ）｜＜８である。このことに鑑みて、差分抽出部４のビットシフト部４ａは、データＤ１を−７ビットから７ビットまでの各ビットでシフトさせることにより複数（ここでは１５）のデータＤ１＿ｓ（ｓ＝−７〜７）を生成する。このように生成された複数のデータＤ１＿ｓのうちのいずれかと、データＤ０との間では、コピービット列Ｅ（ｉ）同士のずれが解消されることになる。
【０１０８】
ここで、データＤ０と、データＤ１＿ｓ（ｓ＝−７〜７）とにおいて、共通するビット列は、下記のビット列であったとする。
【０１０９】
CopyBS_s_0,CopyBS_s_1,…,CopyBS_s_Z(s)
Z(s):データD0に対するデータD1_sのコピービット列の数から１減じた数
【０１１０】
ビットシフト量ｓ＝−７〜７のいずれかにおいて、ＣｏｐｙＢＳ＿ｓ＿ｚ（ｚ＝０，１，…，Ｚ（ｓ））は、コピービット列Ｅ（ｉ）にほぼ一致する。
【０１１１】
ただし、特殊な場合として、コピービット列Ｅ（ｉ）の一部で同じ値が連続している場合には、コピービット列Ｅ（ｉ）と完全に一致するＣｏｐｙＢＳ＿ｓ＿ｚだけが求まるだけでなく、コピービット列Ｅ（ｉ）と一部一致するＣｏｐｙＢＳ＿ｓ＿ｚも求まることがある。また、データＤ１＿ｓでのコピービット列Ｅ（ｉ）の前後の値によっては、ビット列ＳＴまたはビット列ＥＮ（図１４）が、コピービット列Ｅ（ｉ）以外のビットを含む場合があり、この場合にはコピービット列Ｅ（ｉ）より大きいＣｏｐｙＢＳ＿ｓ＿ｚが求まることがある。
【０１１２】
これらの場合、ビットシフト量ｓ＝−７〜７全体で、ＣｏｐｙＢＳ＿ｓ＿ｚ同士が重複部分を有することがある。
【０１１３】
そこで、本実施の形態１に係る差分抽出部４は、以上のように抽出されたＣｏｐｙＢＳ＿ｓ＿ｚを、コピービット列Ｅ（ｉ）として抽出するのではなく、コピービット列Ｅ（ｉ）を生成（抽出）するための中間コピービット列として生成（抽出）する。ただし、ＣｏｐｙＢＳ＿ｓ＿ｚはデータＤ１＿ｓのビット列であり、ビットシフト部４ａによってビットがシフトされたままとなっている。このため、以下では、当該シフトの分だけ逆方向にシフトされたＣｏｐｙＢＳ＿ｓ＿ｚ、つまりデータＤ１でのビット列に戻す補正が行われたＣｏｐｙＢＳ＿ｓ＿ｚを、中間コピービット列として説明する。
【０１１４】
以上により複数の中間コピービット列が生成された後、差分抽出部４は、複数の中間コピービット列のうち互いに重複しない中間コピービット列と、複数の中間コピービット列のうち互いに重複する中間コピービット列同士を結合して得られるビット列と、の少なくともいずれか１つを含むビット列情報を、最終のコピービット列情報として生成（抽出）する。
【０１１５】
その後、差分抽出部４は、データＤ１（新データ）から、コピービット列を除いて得られるビット列を追加ビット列として抽出する。図６の新ビット列ＢＳ１（データＤ１）において、Ｅ（ｉ）（ｉ＝１，２，…）がコピービット列として得られた場合には、Ａ（ｉ）（ｉ＝１，２，…）が追加ビット列として抽出される。
【０１１６】
＜差分抽出部及び差分データ生成部の詳細構成＞
図１５は、本実施の形態１に係る差分抽出部４及び差分データ生成部６の詳細な構成の一例を示すブロック図である。
【０１１７】
図１５の差分抽出部４は、−７ビットシフト部４ａ１，−６ビットシフト部４ａ２，…，７ビットシフト部４ａ１５と、ビット差分抽出部４ｂ１，４ｂ２，…，４ｂ１５と、コピービット列データ生成部４ｂ３０と、追加ビット列データ生成部４ｃ１とを備えている。図１５の差分データ生成部６は、差分コマンド生成部６ａを備えている。
【０１１８】
なお、図２のビットシフト部４ａは、図１５の−７ビットシフト部４ａ１〜７ビットシフト部４ａ１５を含む。図２のコピービット列抽出部４ｂは、図１５のビット差分抽出部４ｂ１〜４ｂ１５（中間コピービット列抽出部）と、コピービット列データ生成部４ｂ３０（最終コピービット列抽出部）とを含む。図２の追加ビット列抽出部４ｃは、図１５の追加ビット列データ生成部４ｃ１を含む。
【０１１９】
−７ビットシフト部４ａ１〜７ビットシフト部４ａ１５は、新データ（ファイルＦ１のデータＤ１）を−７〜７ビットでシフトする。すなわち、−７ビットシフト部４ａ１〜７ビットシフト部４ａ１５は、新データを、そのビット列の順方向及び逆方向に、０，１，２，…，７ビットのそれぞれでシフトすることによって、複数（ここでは１５）のデータＤ１＿−７〜Ｄ１＿７を生成する。複数のデータＤ１＿−７〜Ｄ１＿７は、図示しない内部メモリに格納される。
【０１２０】
ビット差分抽出部４ｂ１は、データＤ１＿−７と、シフトされていない旧データ（ファイルＦ０のデータＤ０）とをビット単位及びバイト単位で比較する。そして、ビット差分抽出部４ｂ１は、当該比較により、データＤ１＿−７と旧データとに共通するビット列の情報を、中間コピービット列情報として抽出する。ビット差分抽出部４ｂ１は、抽出した中間コピービット列情報を、中間差分ファイルＭＤＦ＿−７として中間データ記憶部５（図２）に格納する。
【０１２１】
同様に、ビット差分抽出部４ｂ２〜４ｂ１５は、複数のデータＤ１＿−６〜Ｄ１＿７と、シフトされていない旧データ（ファイルＦ０のデータＤ０）とをビット単位及びバイト単位で比較する。そして、ビット差分抽出部４ｂ２〜４ｂ１５は、当該比較により、複数のデータＤ１＿−６〜Ｄ１＿７と旧データとに共通するビット列の情報を、複数の中間コピービット列情報として抽出する。そして、ビット差分抽出部４ｂ２〜４ｂ１５は、抽出した複数の中間コピービット列情報を、それぞれ中間差分ファイルＭＤＦ＿−６〜ＭＤＦ＿７として中間データ記憶部５（図２）に格納する。
【０１２２】
コピービット列データ生成部４ｂ３０は、ビット差分抽出部４ｂ１〜４ｂ１５で抽出された中間差分ファイルＭＤＦ＿−７〜ＭＤＦ＿７に基づいて、これらの中間コピービット列のうち互いに重複しない中間コピービット列と、これらファイルの中間コピービット列のうち互いに重複する中間コピービット列同士を結合して得られるビット列と、の少なくともいずれか１つを含むビット列の情報を、コピービット列情報として求める。コピービット列データ生成部４ｂ３０は、求めたコピービット列の情報を図示しない内部メモリに格納する。
【０１２３】
追加ビット列データ生成部４ｃ１は、ファイルＦ１のデータＤ１（新データ）から、コピービット列を取り除き、残ったビット列の情報を、追加ビット列情報として求める。追加ビット列データ生成部４ｃ１は、求めた追加ビット列情報を図示しない内部メモリに格納する。
【０１２４】
差分コマンド生成部６ａは、追加ビット列情報とコピービット列情報とに基づいて差分データを生成する。生成された差分データは、差分データ記憶部７（図２）に格納される。
【０１２５】
なお、差分データ作成装置１の図示しない一のＣＰＵによって、−７ビットシフト部４ａ１〜７ビットシフト部４ａ１５、及び、ビット差分抽出部４ｂ１〜４ｂ１５の各々の処理が順（シーケンシャル）に行われてもよい。または、差分データ作成装置１の図示しない複数のＣＰＵが、−７ビットシフト部４ａ１〜７ビットシフト部４ａ１５、及び、ビット差分抽出部４ｂ１〜４ｂ１５の各々に割り当てられることによって、各々の処理が並行して行われてもよい。また、例えば、シフト量が−７〜７ビットのそれぞれについて１ずつＣＰＵを割り当てることによって、各シフト量に対するビットシフト部及びビット差分抽出部の処理が並行して行われてもよい。
【０１２６】
＜差分抽出部の動作＞
図１６は、差分抽出部４の動作の一例を示すフローチャートである。ここでは、−７ビットシフト部４ａ１〜７ビットシフト部４ａ１５、及び、ビット差分抽出部４ｂ１〜４ｂ１５の各々の処理が順（シーケンシャル）に行われる動作例を説明する。つまり、差分抽出部４のビットシフト部４ａ（図２）が、図１５の−７ビットシフト部４ａ１〜７ビットシフト部４ａ１５の各々の処理を順に行い、差分抽出部４のコピービット列抽出部４ｂ（図２）が、図１５のビット差分抽出部４ｂ１〜４ｂ１５の各々の処理を順に行う動作例を説明する。
【０１２７】
まず、ステップＳ１にて、差分抽出部４は、データ記憶部３からファイルＦ０のビット列長ｌｎｇＢＳ０及びデータＤ０（図１２）を読み取り、内部メモリに格納する。
【０１２８】
ステップＳ２にて、差分抽出部４は、データ記憶部３からファイルＦ１のビット列長ｌｎｇＢＳ１及びデータＤ１（図１２）を読み取り、内部メモリに格納する。
【０１２９】
ステップＳ３にて、差分抽出部４は、内部メモリ内に設けたビットシフト量ｓを−７に設定して、初期化する。
【０１３０】
ステップＳ４にて、ビットシフト部４ａ（−７ビットシフト部４ａ１〜７ビットシフト部４ａ１５）は、ビットシフト量ｓだけデータＤ１をビットシフトし、それによって得られたデータＤ１＿ｓを内部メモリに格納する。なお、ｓ＝０の場合のデータＤ１＿０は、シフトされていないデータＤ１となる。
【０１３１】
ステップＳ５にて、コピービット列抽出部４ｂ（ビット差分抽出部４ｂ１〜４ｂ１５）は、データＤ０とデータＤ１＿ｓとに基づいて、ビット単位及びバイト単位で比較して中間コピービット列情報を抽出する。コピービット列抽出部４ｂは、当該中間コピービット列情報を、中間差分ファイルＭＤＦ＿ｓとして中間データ記憶部５に格納する。
【０１３２】
図１７は、中間コピービット列情報（中間差分ファイルＭＤＦ＿ｓ）の構成例を示す図である。
【０１３３】
中間コピービット列情報は、中間コピービット列レコード数と、当該中間コピービット列レコード数が示す数だけの中間コピービット列レコードとを含む。中間コピービット列レコードの各々は、中間コピー先ビットアドレス、中間コピー元ビットアドレス及び中間コピービット列長のフィールドを含む。ここで、中間コピー先ビットアドレスは、データＤ１（新データ）における中間コピービット列のビットアドレスを表し、中間コピー元ビットアドレスは、データＤ０（旧データ）における中間コピービット列のビットアドレスを表し、中間コピービット列長は、中間コピービット列のビット長を表す。
【０１３４】
図１６のステップＳ６にて、差分抽出部４は、ビットシフト量ｓが７であるか否かを判定する。ビットシフト量ｓが７であると判定した場合には、ビットシフト処理が終了したと判定してステップＳ８に進み、そうでない場合にはステップＳ７に進む。
【０１３５】
ステップＳ７にて、差分抽出部４は、ビットシフト量ｓの値に１を加算して、ビットシフト量ｓを更新する。その後、ステップＳ４に戻る。
【０１３６】
ステップＳ６からステップＳ８に進んだ場合、コピービット列抽出部４ｂ（コピービット列データ生成部４ｂ３０）は、中間差分ファイルＭＤＦ＿ｓ（ｓ＝−７〜７）に基づいて、最終のコピービット列情報を抽出し、当該コピービット列情報を内部メモリに格納する。
【０１３７】
図１８は、最終のコピービット列情報の構成例を示す図である。
【０１３８】
コピービット列情報は、コピービット列レコード数と、当該コピービット列レコード数が示す数だけのコピービット列レコードとを含む。コピービット列レコードの各々は、レコード識別子、コピー先ビットアドレス、コピー元ビットアドレス及びコピービット列長のフィールドを含む。ここで、レコード識別子は、当該レコードがコピービット列レコードであることを示すためのフィールドであり、１の値が格納されている。コピー先ビットアドレスは、データＤ１（新データ）におけるコピービット列の先頭ビットのビットアドレスを表す。コピー元ビットアドレスは、データＤ０（旧データ）におけるコピービット列の先頭ビットのビットアドレスを表す。コピービット列長は、コピービット列のビット長を表す。
【０１３９】
図１６のステップＳ９にて、追加ビット列抽出部４ｃ（追加ビット列データ生成部４ｃ１）は、データＤ１から、コピービット列情報に基づいてコピービット列を取り除くことによって追加ビット列情報を抽出し、当該追加ビット列情報を内部メモリに格納する。その後、図１６の差分抽出部４の動作を終了する。
【０１４０】
図１９は、追加ビット列情報の構成例を示す図である。
【０１４１】
追加ビット列情報は、追加ビット列レコード数と、当該追加ビット列レコード数が示す数だけの追加ビット列レコードとを含む。追加ビット列レコードの各々は、レコード識別子、追加先ビットアドレス、追加ビット列長及び追加ビット列のフィールドを含む。ここで、レコード識別子は、当該レコードが追加ビット列レコードであることを示すためのフィールドであり、２の値が格納されている。追加先ビットアドレスは、データＤ１（新データ）における追加ビット列の先頭ビットのビットアドレスを表す。追加ビット列長は、追加ビット列のビット長を表す。追加ビット列は、追加ビット列そのものを表す。
【０１４２】
以上のように、差分抽出部４は、データＤ０と、−７〜＋７ビットの範囲でシフトしたデータＤ１とを比較して、コピービット列及び追加ビット列を求める。このため、旧データと新データとの間にビット単位のずれが発生していても、コピービット列を増加させることができ、追加ビット列を減少させることができる。この結果、差分データのサイズ削減効果を高めることが可能となっている。
【０１４３】
なお、以上では、１つのＣＰＵを用いることによって、各シフト量に対するステップＳ４及びステップＳ５の処理を順（シーケンシャル）に行う場合について説明した。しかし、上述したように、複数のＣＰＵを用いることによって、各シフト量に対するステップＳ４及びステップＳ５の処理を並行に行ってもよい。
【０１４４】
次に図１６の処理のうち主要なものについて詳細に説明する。
【０１４５】
＜ビットシフト処理（ステップＳ４）＞
図２０は、図１６のステップＳ４、つまりビットシフト処理の一例を詳細に示すフローチャートである。
【０１４６】
まず、ステップＳ１１にて、差分抽出部４は、ビットシフト量ｓの値を調べる。ｓ＝０である場合は、ビットシフトは不要として図２０のビットシフト処理を終了する。ｓ＜０である場合は、ビット列の逆方向（ビット列の先頭に向かう方向）に、ビットシフト量ｓの絶対値だけシフトすべきと判定してステップＳ１２に進む。ｓ＞０である場合は、ビット列の順方向（ビット列の末尾に向かう方向）に、ビットシフト量ｓだけシフトすべきと判定してステップＳ１５に進む。
【０１４７】
ステップＳ１２にて、図２のビットシフト部４ａは、データＤ１をそのまま、データＤ１＿ｓとして内部メモリに格納する。
【０１４８】
ステップＳ１３にて、ビットシフト部４ａは、当該データＤ１＿ｓの先頭に、１バイトのデータ（値は０）を挿入する。
【０１４９】
ステップＳ１４にて、ビットシフト部４ａは、当該データＤ１＿ｓをビットシフト量ｓの絶対値だけ先頭に向けてシフトする。その後、図２０のビットシフト処理を終了する。
【０１５０】
ステップＳ１１からステップＳ１５に進んだ場合、ビットシフト部４ａは、データＤ１をそのまま、データＤ１＿ｓとして内部メモリに格納する。
【０１５１】
ステップＳ１６にて、ビットシフト部４ａは、当該データＤ１＿ｓの末尾に、１バイトのデータ（値は０）を挿入する。
【０１５２】
ステップＳ１７にて、ビットシフト部４ａは、当該データＤ１＿ｓをビットシフト量ｓだけ末尾に向けてシフトする。その後、図２０のビットシフト処理を終了する。
【０１５３】
＜中間コピービット列情報の抽出処理（ステップＳ５）＞
図２１は、図１６のステップＳ５、つまり中間コピービット列情報の抽出処理（生成処理）の一例を詳細に示すフローチャートである。
【０１５４】
まず、ステップＳ２１にて、図２のコピービット列抽出部４ｂは、データＤ０（シフトされていない旧データ）と、データＤ１＿ｓ（シフトされた新データ）とをバイト単位で比較することにより、それらの差分を抽出する。ここでは、コピービット列抽出部４ｂは、データＤ１＿ｓと、シフトされてないデータＤ０とに基づいて、データＤ１＿ｓのうちデータＤ０にも含まれるバイト列をコピーバイト列として抽出し、データＤ１＿ｓのうちデータＤ０に含まれてないバイト列を追加バイト列として抽出する。抽出した差分は、バイト差分データとして内部メモリに格納される。
【０１５５】
図２２は、バイト差分データの構成例を示す図である。
【０１５６】
バイト差分データは、所要数のバイト差分コマンドを含む。バイト差分コマンドには、追加バイト列に関する追加コマンドと、コピーバイト列に関するコピーコマンドと、終了コマンドとのいずれかが割り当てられる。
【０１５７】
図２３は、追加コマンドの構成例を示す図である。
【０１５８】
追加コマンドは、コマンドコード、追加バイト列長及び追加バイト列のフィールドを含む。コマンドコードは、当該バイト差分コマンドが追加コマンドであることを示す１バイトのデータであり、値は２４８であるものとする。追加バイト列長は、追加バイト列のバイト数を３２ビットの整数で表す。追加バイト列は、追加バイト列そのものを表す。
【０１５９】
図２４は、コピーコマンドの構成例を示す図である。
【０１６０】
コピーコマンドは、コマンドコード、コピー元オフセット及びコピーバイト列長を含む。コマンドコードは、当該バイト差分コマンドがコピーコマンドであることを示す１バイトのデータであり、値は２５４であるものとする。コピー元オフセットは、データＤ０におけるコピーバイト列の先頭バイト列のオフセットを３２ビットの整数で表す。コピーバイト列長は、コピーバイト列のバイト数を３２ビットの整数で表す。
【０１６１】
図２５は、終了コマンドの構成例を示す図である。
【０１６２】
終了コマンドは、１バイトのデータ（値は０）である。終了コマンドは、バイト差分データの末尾にのみ設けられ、バイト差分データの終了を示す。
【０１６３】
図２１のステップＳ２２にて、コピービット列抽出部４ｂは、内部メモリに設けたオフセットＯＦＳ１及びコピーコマンド数ＣＣＮをともに０に初期化する。なお、図２１の動作においてオフセットＯＦＳ１は、データＤ１＿ｓにおけるコピーバイト列または追加バイト列の先頭バイト列のオフセットを示すことになる。
【０１６４】
ステップＳ２３を行う度に、コピービット列抽出部４ｂは、バイト差分データのうちバイト差分コマンド（図２２）を先頭から１つずつ順に取得する。つまり、最初にステップＳ２３を行う場合には、バイト差分データのうち先頭のバイト差分コマンド（図２２）が取得され、２回目以降にステップＳ２３を行う場合には、前回取得したバイト差分コマンドに対して次のバイト差分コマンドが取得されることになる。
【０１６５】
ステップＳ２４にて、コピービット列抽出部４ｂは、ステップＳ２３で取得したバイト差分コマンドのコマンドコードの値が０か否かを調べ、当該バイト差分コマンドが終了コマンドか否かを調べる。当該バイト差分コマンドが終了コマンドである場合には、バイト差分コマンドについての処理が終了したと判定してステップＳ３４に進み、そうでない場合にはステップＳ２５に進む。
【０１６６】
ステップＳ２５にて、コピービット列抽出部４ｂは、ステップＳ２３で取得したバイト差分コマンドのコマンドコードの値が２５４か否かを調べ、当該バイト差分コマンドがコピーコマンドか否かを調べる。当該バイト差分コマンドがコピーコマンドである場合にはステップＳ２６に進み、そうでない場合には当該バイト差分コマンドが追加コマンドであるとしてステップＳ３３に進む。
【０１６７】
ステップＳ２６に進んだ場合、つまりバイト差分コマンドがコピーコマンドであった場合、コピービット列抽出部４ｂは、当該コピーコマンドのコピー元オフセット及びコピーバイト列長をそれぞれＯＦＳ０及びＣＢＹＴＬに設定する。
【０１６８】
ここで、上記コピーコマンドは、データＤ０のＯＦＳ０（コピー元オフセット）からＣＢＹＴＬ（コピーバイト列長）進んだオフセットまでのバイト列と、データＤ１＿ｓのオフセットＯＦＳ１からＣＢＹＴＬ（コピーバイト列長）進んだオフセットまでのバイト列とが同一であることを示す。データＤ０及びデータＤ１＿ｓにおいて同一であるこれらのバイト列、つまりコピーバイト列を形成するビット列は、図１４に示すビット列ＭＩに対応するので、以下ビット列ＭＩと記して説明する。
【０１６９】
ビット列ＭＩの直前または直後の１バイト内には、ビット列ＭＩに連続し、かつデータＤ０及びデータＤ１＿ｓにおいて同一であるビット列が含まれている可能性がある。ビット列ＭＩの直前の１バイトに含まれ、データＤ０及びデータＤ１＿ｓにおいて同一であるビット列は、図１４に示すビット列ＳＴに対応するので、以下ビット列ＳＴと記して説明する。ビット列ＭＩの直後の１バイトに含まれ、データＤ０及びデータＤ１＿ｓにおいて同一であるビット列は、図１４に示すビット列ＥＮに対応するので、以下ビット列ＥＮと記して説明する。
【０１７０】
ビット列ＭＩは、ステップＳ２１で求まっていることから、ビット列ＳＴ及びビット列ＥＮが求まれば、中間コピービット列を求めることが可能となる。
【０１７１】
そこで、ステップＳ２６では、上述のＯＦＳ０及びＣＢＹＴＬの設定後、コピービット列抽出部４ｂはビット列ＳＴを求める。例えば、コピービット列抽出部４ｂは、データＤ０におけるオフセットが「ＯＦＳ０−１」の１バイトと、データＤ１＿ｓにおけるオフセットが「ＯＦＳ１−１」の１バイトとを、ビット列の逆方向の順（最下位ビットから最上位ビットに向かう順）に比較し、一致しなくなる前までのビットの数（ＸＢＮ）を求める。
【０１７２】
そして、先頭のデータＤ０における中間コピービット列の先頭のビットアドレスａｄｒ０Ｉｓ（以下「ａｄｒ０Ｉｓ」とのみ記す）と、データＤ１＿ｓにおける中間コピービット列の先頭のビットアドレスａｄｒ１Ｉｓ（以下「ａｄｒ１Ｉｓ」とのみ記す）とを下記により求める。
【０１７３】
adr0Is＝OFS0*8-XBN
adr1Is＝OFS1*8-XBN
【０１７４】
つまり、ステップＳ２６では、コピービット列抽出部４ｂは、データＤ１＿ｓのうちバイト単位で抽出されたバイト列（ビット列ＭＩ）の直前の１バイトに含まれるビットと、データＤ０のうちバイト単位で抽出されたバイト列（ビット列ＭＩ）の直前の１バイトに含まれるビットとが一致するか否かをビット列の逆方向の順に判定し、最後に一致するデータＤ１＿ｓのａｄｒ１Ｉｓ（第１アドレス）及びデータＤ０のａｄｒ０Ｉｓ（第２アドレス）を求める。
【０１７５】
ステップＳ２７では、コピービット列抽出部４ｂはビット列ＥＮを求める。例えば、コピービット列抽出部４ｂは、データＤ０におけるオフセットが「ＯＦＳ０＋ＣＢＹＴＬ」の１バイトと、データＤ１＿ｓにおけるオフセットが「ＯＦＳ１＋ＣＢＹＴＬ」の１バイトとを、ビット列の順方向の順（最上位ビットから最下位ビットに向かう順）に比較し、一致しなくなる前までのビットの数（ＹＢＮ）を求める。
【０１７６】
そして、データＤ０における中間コピービット列の末尾のビットアドレスａｄｒ０Ｉｅ（以下「ａｄｒ０Ｉｅ」とのみ記す）と、データＤ１＿ｓにおける中間コピービット列の末尾のビットアドレスａｄｒ１Ｉｅ（以下「ａｄｒ１Ｉｅ」とのみ記す）とを下記により求める。
【０１７７】
adr0Ie＝(OFS0+CBYTL)*8+YBN-1
adr1Ie＝(OFS1+CBYTL)*8+YBN-1
【０１７８】
つまり、ステップＳ２７では、コピービット列抽出部４ｂは、データＤ１＿ｓのうちバイト単位で抽出されたバイト列（ビット列ＭＩ）の直後の１バイトに含まれるビットと、データＤ０のうちバイト単位で抽出されたバイト列（ビット列ＭＩ）の直後の１バイトに含まれるビットとが一致するか否かをビット列の順方向の順に判定し、最後に一致するデータＤ１＿ｓのａｄｒ１Ｉｅ（第３アドレス）及びデータＤ０のａｄｒ０Ｉｅ（第４アドレス）を求める。
【０１７９】
ここで、ステップＳ２６，Ｓ２７で求めたａｄｒ１Ｉｓ，ａｄｒ１Ｉｅは、シフト後のデータＤ１＿ｓにおける中間コピービット列のビットアドレスである。
【０１８０】
このことを鑑みてステップＳ２８にて、コピービット列抽出部４ｂは、ａｄｒ１Ｉｓ，ａｄｒ１Ｉｅを、ビットシフト部４ａがシフトを行う前のアドレスに補正する。つまり、コピービット列抽出部４ｂは、ビットシフト部４ａのシフト（ステップＳ４）と逆方向にａｄｒ１Ｉｓ，ａｄｒ１Ｉｅの値をシフトさせる。
【０１８１】
ステップＳ２９にて、コピービット列抽出部４ｂは、中間コピービット列のビット列長ＩＣＢＬを下記により求める。
【０１８２】
ICBL=adr0Ie-adr0Is+1
【０１８３】
ステップＳ３０にて、コピービット列抽出部４ｂは、補正後のａｄｒ１Ｉｓ、ａｄｒ０Ｉｓ、及び、ＩＣＢＬを、中間コピービット列レコード（図１７）の中間コピー先ビットアドレス、中間コピー元ビットアドレス、及び、中間コピービット列長にそれぞれ設定する。これにより、中間コピービット列レコード（図１７）が生成される。
【０１８４】
以上のステップＳ２８〜Ｓ３０により、コピービット列抽出部４ｂは、ａｄｒ１Ｉｅ及びａｄｒ１Ｉｓを補正し、ａｄｒ０Ｉｅ及びａｄｒ０Ｉｓと、補正されたａｄｒ１Ｉｅ及びａｄｒ１Ｉｓとに基づいて、中間コピービット列情報を生成する。
【０１８５】
ただし、ａｄｒ０Ｉｅ，ａｄｒ０Ｉｓ同士の差と、ａｄｒ１Ｉｅ，ａｄｒ１Ｉｓ同士の差は等しいので、ａｄｒ１Ｉｅ，ａｄｒ１Ｉｓの一方が確定すれば他方も確定することになる。このことに鑑みて、コピービット列抽出部４ｂは、ａｄｒ１Ｉｅまたはａｄｒ１Ｉｓを補正し、ａｄｒ０Ｉｅ及びａｄｒ０Ｉｓと、補正されたａｄｒ１Ｉｅまたはａｄｒ１Ｉｓとに基づいて、中間コピービット列情報を生成してもよい。
【０１８６】
ステップＳ３１にて、コピービット列抽出部４ｂは、コピーコマンド数ＣＣＮに１を加算して、コピーコマンド数ＣＣＮを更新する。
【０１８７】
ステップＳ３２にて、コピービット列抽出部４ｂは、ステップＳ２３で直近に取得したコピーコマンドに含まれるコピーバイト列長（図１８）を、オフセットＯＦＳ１に加算して、オフセットＯＦＳ１を更新する。これにより、オフセットＯＦＳ１は、次の追加コマンドが示す、データＤ１＿ｓにおける追加バイト列の先頭バイト列のオフセット、または、次のコピーコマンドが示す、データＤ１＿ｓにおけるコピーバイト列の先頭バイト列のオフセットを示すことになる。その後、ステップＳ２３に戻る。
【０１８８】
ステップＳ２５からステップＳ３３に進んだ場合、コピービット列抽出部４ｂは、ステップＳ２３で直近に取得した追加コマンドに含まれる追加バイト列長（図１９）を、オフセットＯＦＳ１に加算して、オフセットＯＦＳ１を更新する。これにより、オフセットＯＦＳ１は、次の追加コマンドが示す、データＤ１＿ｓにおける追加バイト列の先頭バイト列のオフセット、または、次のコピーコマンドが示す、データＤ１＿ｓにおけるコピーバイト列の先頭バイト列のオフセットを示すことになる。その後、ステップＳ２３に戻る。
【０１８９】
ステップＳ２４からステップＳ３４に進んだ場合、コピービット列抽出部４ｂは、コピーコマンド数ＣＣＮを、中間コピービット列レコード数に設定する。
【０１９０】
ステップＳ３５にて、コピービット列抽出部４ｂは、ステップＳ３０で生成した中間コピービット列レコードと、ステップＳ３４で設定した中間コピービット列レコード数とを含む図１７の中間コピービット列情報を生成し、それを中間差分ファイルＭＤＦ＿ｓとして中間データ記憶部５に格納する。その後、図２１の中間コピービット列の抽出処理（生成処理）を終了する。
【０１９１】
ここで、図１４を例にして図２１の処理を説明する。図１４では、データＤ１をシフトすべきビットシフト量ｓ＝−Ｓ（ｉ）＝−２である。
【０１９２】
ステップＳ２１にて、コピービット列抽出部４ｂは、データＤ０と、データＤ１＿ｓ（−２ビットだけシフトされたデータＤ１）とからバイト差分データを求める。ここで求まるバイト差分データは、図１４のビット列ＭＩに関するデータであり、下記のフィールドを持つコピーコマンドを含む。なお、下記のコピーコマンドの表記には、図１４のｏｆｓＥｓ（ｉ）及びｂｙｌｎｇＣｏｐｙＥ（ｉ）が用いられている。
【０１９３】
コピー元オフセット=ofsEs(i)+1
コピーバイト列長=bylngCopyE(i)
【０１９４】
ステップＳ２２にて、コピービット列抽出部４ｂは、上記コピーコマンドを取得する。ステップＳ２３〜Ｓ２５を経てステップＳ２６にて、コピービット列抽出部４ｂは、コピー元オフセット（データＤ０のｏｆｓＥｓ（ｉ）＋１）をＯＦＳ０に設定し、コピーバイト列長（ｂｙｌｎｇＣｏｐｙＥ（ｉ））をＣＢＹＴＬに設定する。なお、ＯＦＳ１は、データＤ１＿ｓにおける追加バイト列またはコピーバイト列の先頭バイト列のオフセットを示しており、ここでは図１４のデータＤ１＿ｓのｏｆｓＡｓ（ｉ）＋１に相当する。
【０１９５】
ステップＳ２６にて、コピービット列抽出部４ｂは、データＤ０のオフセットがＯＦＳ０−１＝ｏｆｓＥｓ（ｉ）である１バイトと、データＤ１＿ｓのオフセットがＯＦＳ１−１＝ｏｆｓＡｓ（ｉ）である１バイトとを、最下位ビットから順に比較する。これにより、ビット列ＳＴが得られ、ＸＢＮ＝６が得られる。この結果、データＤ０における中間コピービット列の先頭のａｄｒ０Ｉｓ（＝ｂｉｔｎＥｓ（ｉ））と、データＤ１＿ｓにおける中間コピービット列の先頭のａｄｒ１Ｉｓ（＝ｂｉｔｎＡｓ＿ｓ（ｉ））とが得られる。
【０１９６】
ステップＳ２７にて、コピービット列抽出部４ｂは、データＤ０のオフセットがＯＦＳ０＋ＣＢＹＴＬ＝ｏｆｓＥｅ（ｉ）である１バイトと、データＤ１＿ｓのオフセットがＯＦＳ１＋ＣＢＹＴＬ＝ｏｆｓＡｅ（ｉ）である１バイトとを、最上位ビットから順に比較する。これにより、ビット列ＥＮが得られ、ＹＢＮ＝４が得られる。この結果、データＤ０における中間コピービット列の末尾のａｄｒ０Ｉｅ（＝ｂｉｔｎＥｅ（ｉ））と、データＤ１＿ｓにおける中間コピービット列の末尾のａｄｒ１Ｉｅ（＝ｂｉｔｎＡｅ＿ｓ（ｉ））とが得られる。
【０１９７】
ステップＳ２８にて、コピービット列抽出部４ｂは、データＤ１＿ｓにおけるａｄｒ１Ｉｓ（＝ｂｉｔｎＡｓ＿ｓ（ｉ））、及び、ａｄｒ１Ｉｅ（＝ｂｉｔｎＡｅ＿ｓ（ｉ））を、ビットシフト部４ａのシフト（ステップＳ４）と逆方向にシフトする。これにより、データＤ１におけるｂｉｔｎＡｓ（ｉ），ｂｉｔｎＡｅ（ｉ）が得られる。
【０１９８】
以上のような動作により、ビットシフト量ｓ（ｓ＝−７〜７）の各々に対して、データＤ０とデータＤ１＿ｓとに共通するビット列に、ビットシフトの補正を行った中間コピービット列が得られる。この結果、図１５に示されるように、複数の中間差分ファイルＭＤＦ＿ｓ（図１７）が得られる。
【０１９９】
＜コピービット列情報の抽出処理（ステップＳ８）＞
図２６は、図１６のステップＳ８、つまりコピービット列情報の抽出処理（生成処理）の一例を詳細に示すフローチャートである。
【０２００】
まず、ステップＳ４１にて、コピービット列抽出部４ｂは、中間差分ファイルＭＤＦ＿−７を読み取り、当該中間差分ファイルＭＤＦ＿−７を、中間ビット列マージ情報ＩＭＥＲＧＥとして内部メモリに格納する。これにより、図１７に示した中間コピービット列情報が、中間ビット列マージ情報ＩＭＥＲＧＥとして内部メモリに格納される。
【０２０１】
ステップＳ４２にて、コピービット列抽出部４ｂは、ファイル指定ｆｓ（ｆｓ＝−６〜７）に−６を設定することによって、ファイル指定ｆｓを初期化する。なお、ファイル指定ｆｓは、ステップＳ４１とは別に読み取るべき中間差分ファイルＭＤＦ＿ｆｓを指定する。
【０２０２】
ステップＳ４３にて、コピービット列抽出部４ｂは、ファイル指定ｆｓで指定された中間差分ファイルＭＤＦ＿ｆｓを読み取り、当該中間差分ファイルＭＤＦ＿ｆｓを、一時的中間コピービット列情報ＴＥＭＰとして内部メモリに格納する。これにより、図１７に示した中間コピービット列情報が、一時的中間コピービット列情報ＴＥＭＰとして内部メモリに格納される。
【０２０３】
ステップＳ４４にて、コピービット列抽出部４ｂは、一時的中間コピービット列情報ＴＥＭＰの中間コピービット列レコード数を、内部メモリに設けたカウンタに設定することによって、カウンタを初期化する。
【０２０４】
ステップＳ４５を行う度に、コピービット列抽出部４ｂは、一時的中間コピービット列情報ＴＥＭＰのうち一の中間コピービット列レコードを先頭から順に取得する。つまり、最初にステップＳ４５を行う場合には、先頭の一の中間コピービット列レコードが取得され、２回目以降にステップＳ４５を行う場合には、前回取得した一の中間コピービット列レコードに対して次の一の中間コピービット列レコードが取得される。
【０２０５】
ステップＳ４６にて、コピービット列抽出部４ｂは、中間ビット列マージ情報ＩＭＥＲＧＥの各中間コピービット列レコードと、一時的中間コピービット列情報ＴＥＭＰの一の中間コピービット列レコードとについて、中間コピービット列のコピー範囲を求める。ここで、中間コピービット列のコピー範囲とは、中間コピービット列レコード（図１７）の中間コピー元ビットアドレス及び中間コピービット列長に基づいて規定される、データＤ０における中間コピービット列のビットアドレスの範囲である。ここでは、コピー範囲は、「中間コピー元ビットアドレス」から「中間コピー元ビットアドレス＋中間コピービット列長−１」までのデータＤ０のビットアドレスの範囲とする。
【０２０６】
そして、コピービット列抽出部４ｂは、中間ビット列マージ情報ＩＭＥＲＧＥの各中間コピービット列レコードのコピー範囲と、一時的中間コピービット列情報ＴＥＭＰの一の中間コピービット列レコードのコピー範囲とが一部でも重複するか否かを判定する。重複する場合にはステップＳ４９に進み、重複しない場合にはステップＳ４７に進む。
【０２０７】
ステップＳ４７にて、コピービット列抽出部４ｂは、ステップＳ４５で取得した一の中間コピービット列レコードを、中間ビット列マージ情報ＩＭＥＲＧＥに挿入または中間ビット列マージ情報ＩＭＥＲＧＥの末尾に追加する。ただし、一時的中間コピービット列情報ＴＥＭＰの一の中間コピービット列レコードと、中間ビット列マージ情報ＩＭＥＲＧＥの各中間コピービット列レコードとが、中間コピー元ビットアドレスの昇順に並ぶように、上述の挿入及び追加は行われるものとする。
【０２０８】
ステップＳ４８にて、コピービット列抽出部４ｂは、中間ビット列マージ情報ＩＭＥＲＧＥの中間コピービット列レコード数に１を加算して、中間コピービット列レコード数を更新する。その後、ステップＳ５２に進む。
【０２０９】
ステップＳ４６からステップＳ４９に進んだ場合、コピービット列抽出部４ｂは、重複するコピー範囲に関して、中間ビット列マージ情報ＩＭＥＲＧＥの中間コピービット列レコードと、一時的中間コピービット列情報ＴＥＭＰの一の中間コピービット列レコードとを結合する。
【０２１０】
これにより、これら中間コピービット列レコードのコピー範囲を結合した結合コピー範囲が得られるとともに、当該結合コピー範囲を有する結合ビット列が得られる。結合コピー範囲は、重複する全てのコピー範囲を含む最小の範囲とする。結合コピー範囲の最小のビットアドレスをａｄｒＣＡｍｉｎと記し、結合コピー範囲の最大のビットアドレスをａｄｒＣＡｍａｘと記して、以下、具体的に説明する。
【０２１１】
図２７は、結合コピー範囲の一例を示す図である。
【０２１２】
図２７の例では、一時的中間コピービット列情報ＴＥＭＰの一の中間コピービット列レコード＃ｔのコピー範囲に、中間ビット列マージ情報ＩＭＥＲＧＥの各中間コピービット列レコード＃ｕ，＃ｖ，＃ｗのコピー範囲が重複している。このため、これら全てのコピー範囲を含む最小の範囲が、結合コピー範囲となる。
【０２１３】
図２６のステップＳ５０にて、コピービット列抽出部４ｂは、中間ビット列マージ情報ＩＭＥＲＧＥの結合対象となる中間コピービット列レコードのうち、先頭の中間コピービット列レコードのみを残し、他のレコードは削除する。残した先頭の中間コピービット列レコード（図１７）の中間コピー先ビットアドレス、中間コピー元ビットアドレス、中間コピービット列長を下記のように変更及び設定する。
【０２１４】
（１）残した先頭の中間コピー先ビットアドレス（データＤ１におけるビットアドレス）を、「中間コピー元ビットアドレス−ａｄｒＣＡｍｉｎ」だけ減じる。ただし、中間コピー元ビットアドレスは下記（２）の設定前の値とする。これにより、コピー範囲を結合した分だけ、中間コピー先ビットアドレスが変化する。（２）残した先頭の中間コピー元ビットアドレス（データＤ０におけるビットアドレス）に、ａｄｒＣＡｍｉｎを設定する。（３）残した先頭の中間コピー元ビット列長に、「ａｄｒＣＡｍａｘ−ａｄｒＣＡｍｉｎ＋１」を設定する。
【０２１５】
図２７の例では、中間ビット列マージ情報ＩＭＥＲＧＥの中間コピービット列レコード＃ｕ，＃ｖ，＃ｗとのうち、先頭の中間コピービット列レコード＃ｕが残り、他の中間コピービット列レコード＃ｖ，＃ｗが削除される。残った先頭の中間コピービット列レコード＃ｕの各フィールドは、上記のように変更される。
【０２１６】
ステップＳ５１にて、コピービット列抽出部４ｂは、ステップＳ５０で中間ビット列マージ情報ＩＭＥＲＧＥの中間コピービット列レコードが削減された数だけ、中間ビット列マージ情報ＩＭＥＲＧＥの中間コピービット列レコード数を減して、中間コピービット列レコード数を更新する。その後、ステップＳ５２に進む。
【０２１７】
ステップＳ５２にて、コピービット列抽出部４ｂは、カウンタを１だけ減して、カウンタを更新する。
【０２１８】
ステップＳ５３にて、コピービット列抽出部４ｂは、カウンタが０であるか否かを判定する。０であると判定した場合には、一時的中間コピービット列情報ＴＥＭＰの全ての中間コピービット列レコードに対する処理が終了したと判定してステップＳ５４に進む。そうでない場合にはステップＳ４５に戻る。
【０２１９】
ステップＳ５４にて、コピービット列抽出部４ｂは、ファイル指定ｆｓに１を加算して、ファイル指定ｆｓを更新する。
【０２２０】
ステップＳ５５にて、コピービット列抽出部４ｂは、ファイル指定ｆｓが７より大きいか否かを判定する。大きいと判定した場合には、中間差分ファイルＭＤＦ＿ｆｓ（ｆｓ＝−６〜７）について処理が終了したとしてステップＳ５６に進む。そうでない場合にはステップＳ４３に戻る。
【０２２１】
ステップＳ５６にて、コピービット列抽出部４ｂは、中間ビット列マージ情報ＩＭＥＲＧＥの中間コピービット列レコード数を、コピービット列情報（図１８）のコピービット列レコード数に設定する。また、コピービット列抽出部４ｂは、中間ビット列マージ情報ＩＭＥＲＧＥの中間コピービット列レコードに、レコード識別子（＝１）を追加したものを、コピービット列情報（図１８）のコピービット列レコードに設定する。これにより、コピービット列情報（図１８）が生成される。その後、図２６のコピービット列の抽出処理（生成処理）を終了する。
【０２２２】
以上により、中間差分ファイルＭＤＦ＿−７〜ＭＤＦ＿７の各中間コピービット列のコピー範囲のうち、コピー範囲が他と重複しない中間コピービット列と、重複するコピー範囲を結合した結合コピー範囲を有する結合ビット列との少なくともいずれか１つを含むビット列の情報が、最終のコピービット列情報として得られる。
【０２２３】
したがって、最終のコピービット列のコピー範囲は、可能な限り大きくなっている。これにより、複数のコピービット列レコードを、一のコピービット列レコードにまとめることができるので、コピービット列レコードに要するデータサイズ、ひいては差分データのサイズを小さくすることができる。
【０２２４】
＜追加ビット列情報の抽出処理（ステップＳ９）＞
図２８は、図１６のステップＳ９、つまり追加ビット列情報の抽出処理（生成処理）の一例を詳細に示すフローチャートである。図２９は、追加ビット列情報の抽出処理（生成処理）の一例を示す図である。
【０２２５】
まず、図２８のステップＳ６１にて、追加ビット列抽出部４ｃは、内部メモリに設けた追加ビットアドレスＡＢＡ（以下「ＡＢＡ」とのみ記す）、コピーカウンタＣＣＮＴ（以下「ＣＣＮＴ」とのみ記す）、追加カウンタＡＣＮＴ（以下「ＡＣＮＴ」とのみ記す）を初期化する。ここでは、初期化として、ＡＢＡに０を設定し、ＣＣＮＴにコピービット列情報（図１８）のコピービット列レコード数を設定し、ＡＣＮＴに０を設定する。なお、図２８の動作においてＡＢＡは、データＤ１において追加ビット列の先頭のビットアドレスを概ね示すことになる。
【０２２６】
ステップＳ６２を行う度に、追加ビット列抽出部４ｃは、コピービット列情報（図１８）のうち一のコピービット列レコードを先頭から順に取得する。つまり、最初にステップＳ６２を行う場合には、先頭の一のコピービット列レコードが取得され、２回目以降にステップＳ６２を行う場合には、前回取得した一のコピービット列レコードに対して次の一のコピービット列レコードが取得される。
【０２２７】
ステップＳ６２で取得したコピービット列レコードに関して、コピー先ビットアドレスをＣＢＡ１に設定し、コピー元ビットアドレスをＣＢＡ０に設定し、コピービット列長をＣＢＬに設定する。
【０２２８】
図２９の例では、最初にステップＳ６２を行う場合に、コピー先ビットアドレスであるｃｂａ１＿０をＣＢＡ１に設定し、コピー元ビットアドレスであるｃｂａ０＿０をＣＢＡ０に設定し、コピービット列長であるｃｂｌ＿０をＣＢＬに設定する。
【０２２９】
ステップＳ６３にて、追加ビット列抽出部４ｃは、ステップＳ６２で取得したコピービット列レコードのＣＢＡ１と、ＡＢＡとを比較する。一致する場合にはステップＳ６８に進み、一致しない場合にはステップＳ６４に進む。
【０２３０】
ここで、ＣＢＡ１とＡＢＡとが一致する場合、データＤ１において、ＡＢＡ（＝ＣＢＡ１）が示すビットから、上記コピービット列レコードのコピービット列長ＣＢＬまで、コピービット列が存在することを示す。ＣＢＡ１とＡＢＡとが一致しない場合、データＤ１において、ＡＢＡ（＜ＣＢＡ１）が示すビットから、「ＣＢＡ１−１」が示すビットまで、追加ビット列が存在することを示す。
【０２３１】
例えば、図２９のようにデータＤ１の先頭に追加ビット列が存在する場合には、最初のステップＳ６３にて、コピービット列レコード＃０に関してＣＢＡ１（＝ｃｂａ１＿０≠０）とＡＢＡ（＝０）とが一致しない。この場合、データＤ１のＡＢＡ（＝０）から「ＣＢＡ−１（＝ｃｂａ１＿０−１）」まで追加ビット列が存在する。
【０２３２】
一方、図示しないがデータＤ１の先頭にコピービット列が存在する場合には、最初のステップＳ６３にて、コピービット列レコード＃０に関してＣＢＡ１（＝ｃｂａ１＿０＝０）とＡＢＡ（＝０）とが一致する。この場合、データＤ１のＡＢＡ（＝０）から「ＣＢＡ−１（＝ｃｂａ１＿０−１）」までコピービット列が存在する。
【０２３３】
図２８のステップＳ６３からステップＳ６４に進んだ場合、つまり図２９のような場合に、追加ビット列抽出部４ｃは、データＤ１のビットアドレスＡＢＡから「ＣＢＡ−１」までのビット列を、追加ビット列ＡＢＳとして求める。
【０２３４】
例えば、図２９の状態において最初にステップＳ６４を行う場合には、追加ビット列ＡＢＳとしてデータＤ１の追加ビット列Ａ０が求まる。
【０２３５】
図２８のステップＳ６５にて、追加ビット列抽出部４ｃは、ＡＢＡ、「ＣＢＡ１−１」及び追加ビット列ＡＢＳを、追加ビット列レコード（図１９）の追加先ビットアドレス、追加ビット列長及び追加ビット列にそれぞれ設定し、それにより得られたデータにレコード識別子（＝２）を追加する。これにより、追加ビット列レコード（図１９）が生成される。
【０２３６】
例えば、図２９の状態において最初にステップＳ６５を行う場合には、追加ビット列Ａ０について追加ビット列レコード＃０が生成される。
【０２３７】
ステップＳ６６にて、追加ビット列抽出部４ｃは、ステップＳ６５で生成した追加ビット列レコードを、それまでに格納されていた追加ビット列レコードの後に格納する。ただし、最初の追加ビット列レコードは、追加ビット列レコード数が格納される領域の直後に格納する。
【０２３８】
例えば、図２９の状態において最初にステップＳ６６を行う場合には、最初の追加ビット列レコード＃０は、追加ビット列レコード数の直後に格納される。
【０２３９】
図２８のステップＳ６７にて、追加ビット列抽出部４ｃは、ＡＣＮＴに１を加算し、これまでに格納されている追加ビット列レコードの数を計数する。
【０２４０】
ステップＳ６８にて、追加ビット列抽出部４ｃは、ステップＳ６２で取得したコピービット列レコードのＣＢＡ１に、当該コピービット列レコードのＣＢＬを加算した値を、ＡＢＡに設定する。この結果、ＡＢＡは、次の追加ビット列の先頭のビットアドレスを示すことになる。
【０２４１】
例えば、図２９の状態において最初にステップＳ６８を行う場合には、ステップＳ６２で取得されたコピービット列レコード＃０に基づいて、「ｃｂａ１＿０＋ｃｂ１＿０」が２回目のＡＢＡとして設定されることになる。ここで、「ｃｂａ１＿０＋ｃｂ１＿０」は、追加ビット列Ａ１の先頭のビットアドレスを示すことになる。
【０２４２】
図２８のステップＳ６９にて、追加ビット列抽出部４ｃは、ＣＣＮＴを１だけ減して、ＣＣＮＴを更新する。
【０２４３】
ステップＳ７０にて、追加ビット列抽出部４ｃは、ＣＣＮＴが０か否かを判定する。０であると判定した場合には、全てのコピービット列レコードに対する処理が終了したとして、ステップＳ７１に進む。そうでない場合には、ステップＳ６２に戻る。
【０２４４】
図２９の例にて、２回目にステップＳ６３を行う場合にはコピービット列レコード＃１に関してＣＢＡ１（＝ｃｂａ１＿１）とＡＢＡ（＝ｃｂａ１＿０＋ｃｂ１＿０）とは一致しない。この場合、ステップＳ６４に進んで、追加ビット列抽出部４ｃは、データＤ１のＡＢＡ（＝ｃｂａ１＿０＋ｃｂ１＿０）から「ＣＢＡ１−１（＝ｃｂａ１＿１−１）」までのビット列を追加ビット列Ａ１として求める。
【０２４５】
その後、ステップＳ６５にて、追加ビット列Ａ１について追加ビット列レコード＃１が生成される。ステップＳ６６にて、追加ビット列レコード＃１は、追加ビット列レコード＃０の後に格納される。ステップＳ６７を経てステップＳ６８にて、ステップＳ６２で取得されたコピービット列レコード＃１に基づいて、「ｃｂａ１＿１＋ｃｂ１＿１」が３回目のＡＢＡとして設定されることになる。ここで、「ｃｂａ１＿１＋ｃｂ１＿１」は、追加ビット列Ａ２の先頭のビットアドレスを示すことになる。
【０２４６】
さて、図２８のステップＳ７０からステップＳ７１に進んだ場合、追加ビット列抽出部４ｃは、ＡＣＮＴを、追加ビット列情報（図１９）の追加ビット列レコード数に設定する。これにより、追加ビット列情報（図１９）が生成される。その後、図２８の追加ビット列情報の抽出処理（生成処理）を終了する。
【０２４７】
＜差分データ生成部の動作＞
これまで、図２及び図１５に示される差分抽出部４の動作について説明した。次に、図２及び図１５に示される差分データ生成部６（差分コマンド生成部６ａ）の動作について説明する。なお、差分データ生成部６の動作について説明する前に、差分データ生成部６の動作によって生成される差分データについて説明する。
【０２４８】
図３０は、差分データ生成部６で生成される差分データの構成例を示す図である。
【０２４９】
差分データは、所要数のビット差分コマンドを含む。ビット差分コマンドには、追加ビット列に関する追加ビットコマンドと、コピービット列に関するコピービットコマンドと、終了コマンドのいずれかが割り当てられる。以下、ビット差分コマンドの構成例について説明するが、ビット差分コマンドの構成は、下記の構成に限ったものではない。
【０２５０】
図３１は、追加ビットコマンドの構成例を示す図である。
【０２５１】
追加ビットコマンドは、コマンドコード、追加ビット列長及び追加ビット列のフィールドを含む。
【０２５２】
コマンドコードは、当該ビット差分コマンドが追加ビットコマンドであることを示す２ビット長のデータであり、値は１であるとする。
【０２５３】
追加ビット列長は、追加ビット列のビット長（ビット数）を表す。ここでは、追加ビット列長は、追加ビット列長ヘッダと、追加ビット列長商部と、追加ビット列長剰余部とを含む。
【０２５４】
追加ビット列長ヘッダは、追加ビット列長商部に使用可能なバイト数を２ビットで表す。例えば、０，１，２，３は、それぞれ追加ビット列長商部に使用可能なバイト数が１，２，３，４バイトであることを表す。
【０２５５】
追加ビット列商部は、追加ビット列長を２５６で除したときの商を表す。追加ビット列商部に使用可能なバイト数は、追加ビット列長ヘッダにより定まる。
【０２５６】
追加ビット列長剰余部は、追加ビット列長を２５６で除したときの剰余を１バイトで表す。
【０２５７】
追加ビット列は、データＤ１における追加ビット列そのものを表す。
【０２５８】
図３２は、コピービットコマンドの構成例を示す図である。
【０２５９】
コピービットコマンドは、コマンドコード、コピー元ビットアドレス及びコピービット列長のフィールドを含む。
【０２６０】
コマンドコードは、当該ビット差分コマンドがコピービットコマンドであることを示す２ビット長のデータであり、値は２であるものとする。
【０２６１】
コピー元ビットアドレスは、データＤ０からデータＤ１にコピーすべきコピービット列について、データＤ０における当該コピービット列の先頭のビットアドレスを表す。ここでは、コピー元ビットアドレスは、コピー元ビットアドレスヘッダと、コピー元ビットアドレス商部と、コピー元ビットアドレス剰余部とを含む。
【０２６２】
コピー元ビットアドレスヘッダは、コピー元ビットアドレス商部に使用可能なバイト数を２ビットで表す。例えば、０，１，２，３は、それぞれコピー元ビットアドレス商部に使用可能なバイト数が１，２，３，４バイトであることを表す。
【０２６３】
コピー元ビットアドレス商部は、コピー元ビットアドレスを２５６で除した時の商を表す。コピー元ビットアドレス商部に使用可能なバイト数は、コピー元ビットアドレスヘッダにより定まる。
【０２６４】
コピー元ビットアドレス剰余部は、コピー元ビットアドレスを２５６で除したときの剰余を１バイトで表す。
【０２６５】
コピービット列長は、データＤ０からデータＤ１にコピーすべきコピービット列のビット長（ビット数）を表す。ここでは、コピービット列長は、コピービット列長ヘッダと、コピービット列長商部と、コピービット列長剰余部とを含む。
【０２６６】
コピービット列長ヘッダは、コピービット列長商部に使用可能なバイト数を２ビットで表す。例えば、０，１，２，３は、それぞれコピービット列長商部に使用可能なバイト数が１，２，３，４バイトであることを表す。
【０２６７】
コピービット列長商部は、コピービット列長を２５６で除した時の商を表す。コピービット列長商部に使用可能なバイト数は、コピービット列長ヘッダにより定まる。
【０２６８】
コピービット列長剰余部は、コピービット列長を２５６で除したときの剰余を１バイトで表す。
【０２６９】
図３３は、終了コマンドの構成例を示す図である。
【０２７０】
終了コマンドは、コマンドコードのみからなる。コマンドコードは、２ビット長のフィールドで値は０とする。終了コマンドは、差分データの末尾にのみ設けられ、差分データの終了を示す。
【０２７１】
図３４は、差分データ生成部６（差分コマンド生成部６ａ）の動作の一例を示すフローチャートである。なお、前提としてコピービット列情報（図１８）及び追加ビット列情報（図１９）は、内部メモリにすでに格納されているものとする。
【０２７２】
まず、ステップＳ８１にて、差分データ生成部６は、コピービット列情報（図１８）のコピービット列レコード数と、追加ビット列情報（図１９）の追加ビット列レコード数とを合算した値ｇを、内部メモリに設けた生成レコード数に設定する。
【０２７３】
ステップＳ８２にて、差分データ生成部６は、コピービット列情報（図１８）のコピービット列レコードと、追加ビット列情報（図１９）の追加ビット列レコードとをマージし、それによって得られた情報をマージ情報として内部メモリに格納する。なお、マージ情報において、コピービット列レコード及び追加ビット列レコードは、各レコードの第２フィールド（コピー先ビットアドレス及び追加先ビットアドレス）の昇順となるようにマージする。
【０２７４】
図３５は、マージ情報の構成例を示す図である。
【０２７５】
マージ情報では、コピービット列レコードと追加ビット列レコードとが、それらの第２フィールドの昇順に格納されている。格納されるコピービット列レコード及び追加ビット列レコードの合計は、生成レコード数の値ｇと同じである。なお、図３５において、ＳＥＣＦ（ｉ）（ｉ＝０，１，…，ｇ−１）は、各レコード内の第２フィールドの値を示す。
【０２７６】
図３４のステップＳ８３にて、差分データ生成部６は、内部メモリに設けたレコードカウンタを０に設定して初期化する。
【０２７７】
ステップＳ８４を行う度に、差分データ生成部６は、マージ情報のうち、コピービット列レコード及び追加ビット列レコードのいずれかであるレコードを先頭から１つずつ順に取得する。つまり、最初にステップＳ８４を行う場合には、マージ情報のうち先頭のレコード＃０が取得され、２回目以降にステップＳ８４を行う場合には、前回取得したレコード＃０に対して次のレコード＃１が取得されることになる。
【０２７８】
そして、差分データ生成部６は、取得したレコードのレコード識別子が、コピービット列レコードを示す識別子（＝１）か否かを判定する。識別子が１である場合には、取得したレコードはコピービット列レコードであると判定してステップＳ８５に進む。そうでない場合には、取得したレコードは追加ビット列レコードであると判定してステップＳ８６に進む。
【０２７９】
ステップＳ８５にて、差分データ生成部６は、ステップＳ８４で取得したコピービット列レコードに基づいて、下記のように設定したコピービットコマンド（図３２）を生成し、当該コピービットコマンドを生成中の差分データの末尾に追加する。その後、ステップＳ８７に進む。
【０２８０】
コマンドコード：
コピービットコマンドを示す２を設定する
コピー元ビットアドレス：
当該コピービット列レコードのコピー元ビットアドレスを設定する
コピービット列長：
当該コピービット列レコードのコピービット列長を設定する
【０２８１】
ステップＳ８６にて、差分データ生成部６は、ステップＳ８４で取得した追加ビット列レコードに基づいて、下記のように設定した追加ビットコマンド（図３１）を生成し、当該追加ビットコマンドを生成中の差分データの末尾に追加する。その後、ステップＳ８７に進む。
【０２８２】
コマンドコード：
追加ビットコマンドを示す１を設定する
追加ビット列長：
当該追加ビット列レコードの追加ビット列長を設定する
追加ビット列：
当該追加ビット列レコードの追加ビット列を設定する
【０２８３】
ステップＳ８７にて、差分データ生成部６は、レコードカウンタの値に１を加算して、レコードカウンタを更新する。
【０２８４】
ステップＳ８８にて、差分データ生成部６は、レコードカウンタの値が、生成レコード数の値ｇに一致するか否かを判定する。一致すると判定した場合には、ビット差分コマンドの生成が終了したと判定してステップＳ８９に進む。一致しないと判定した場合にはステップＳ８４に戻る。
【０２８５】
ステップＳ８９にて、差分データ生成部６は、終了コマンド（図３３）を生成し、生成中の差分データの末尾に追加する。これにより、図３０の差分データが生成される。
【０２８６】
ステップＳ９０にて、差分データ生成部６は、生成した差分データを差分データ記憶部７（図２）に格納する。その後、図３４の差分データ生成部６の動作を終了する。
【０２８７】
以上により生成される差分データは、コピービットコマンド（データＤ０に含まれるコピービット列のアドレス及び長さを示す情報）と、追加ビットコマンド（データＤ１に含まれる追加ビット列及び追加ビット列の長さを示す情報）とを含んでいる。そして、差分データにおいて、コピービットコマンド及び追加ビットコマンドが、データＤ１に含まれるコピービット列及び追加ビット列の、当該データＤ１におけるアドレス順に並べられている。これにより、差分データのサイズを可及的に低減することが可能となっている。
【０２８８】
＜データ更新部の動作＞
以上、図２の差分データ作成装置１における主要な構成要素の動作について説明した。次に、図３のデータ更新装置１１におけるデータ更新部１５の動作について説明する。なお、図４の情報処理装置２１におけるデータ更新部２５の動作は、以下に説明するデータ更新部１５の動作と同様である。
【０２８９】
図３６は、データ更新部１５のデータ更新動作の一例を示すフローチャートである。以下の説明から明らかとなるように、この更新動作によって新データ（データＤ１）と同じデータＤ２が生成される。
【０２９０】
まず、図３６のステップＳ１０１にて、データ更新部１５は、データ記憶部１４（図３）から、旧データであるファイルＦ０（図１２）のｌｎｇＢＳ０とデータＤ０とを読み取り、これらを内部メモリに格納する。
【０２９１】
ステップＳ１０２にて、データ更新部１５は、差分データ記憶部１３（図３）から差分データを読み取り、当該差分データを内部メモリに格納する。
【０２９２】
ステップＳ１０３にて、データ更新部１５は、内部メモリに設けた格納ビットアドレスＳＢＡを０に設定して初期化する。ここで、図３６の動作において格納ビットアドレスＳＢＡは、データＤ２における、追加ビット列またはコピービット列の先頭のビットアドレスを示すことになる。
【０２９３】
ステップＳ１０４を行う度に、データ更新部１５は、内部メモリに格納した差分データのうちビット差分コマンドを先頭から１つずつ順に取得する。つまり、最初にステップＳ１０４を行う場合には、差分データのうち先頭のビット差分コマンドが取得され、２回目以降にステップＳ１０４を行う場合には、前回取得したビット差分コマンドに対して次のビット差分コマンドが取得されることになる。
【０２９４】
ステップＳ１０５にて、データ更新部１５は、ステップＳ１０４で取得したビット差分コマンドのコマンドコードが、追加ビットコマンドを示すコマンドコード（＝１）か否かを判定する。コマンドコードが１である場合には、取得したビット差分コマンドは追加ビットコマンドであると判定してステップＳ１０８に進む。そうでない場合にはステップＳ１０６に進む。
【０２９５】
ステップＳ１０６にて、データ更新部１５は、ステップＳ１０４で取得したビット差分コマンドのコマンドコードが、コピービットコマンドを示すコマンドコード（＝２）か否かを判定する。コマンドコードが２である場合には、取得したビット差分コマンドはコピービットコマンドであると判定してステップＳ１１０に進む。そうでない場合にはステップＳ１０７に進む。
【０２９６】
ステップＳ１０７にて、データ更新部１５は、ステップＳ１０４で取得したビット差分コマンドのコマンドコードが、終了コマンドを示すコマンドコード（＝０）か否かを判定する。コマンドコードが０である場合には、取得したビット差分コマンドは終了コピービットコマンドであると判定してステップＳ１１３に進む。そうでない場合には、取得したビット差分コマンドは無効コマンドであると判定してステップＳ１０４に戻る。
【０２９７】
ステップＳ１０５からステップＳ１０８に進んだ場合、データ更新部１５は、ステップＳ１０４で取得した追加ビットコマンド（図３１）の追加ビット列を、データＤ２に格納する。
【０２９８】
図３７は、ステップＳ１０８及びＳ１０９におけるデータ更新部１５の処理の一例を示す図である。図３７の例でステップＳ１０８を行う場合には、データ更新部１５は、追加ビットコマンドの追加ビット列ＡｄｄＢＳの先頭を、データＤ２の格納ビットアドレスＳＢＡの位置に合わせて、追加ビット列ＡｄｄＢＳをデータＤ２に格納する。
【０２９９】
図３６のステップＳ１０９にて、データ更新部１５は、格納ビットアドレスＳＢＡに、ステップＳ１０４で取得した追加ビットコマンド（図３１）の追加ビット列長を加算して、格納ビットアドレスＳＢＡを更新する。図３７の例でステップＳ１０９を行う場合には、格納ビットアドレスＳＢＡに、追加ビットコマンドの追加ビット列長ｌｎｇＡｄｄＢＳを加算する。これにより、格納ビットアドレスＳＢＡは、ステップＳ１０８で格納した追加ビット列ＡｄｄＢＳ直後のビットアドレスを示すことになる。ステップＳ１０９の後、ステップＳ１０４に戻る。
【０３００】
ステップＳ１０６からステップＳ１１０に進んだ場合、データ更新部１５は、ステップＳ１０４で取得したコピービットコマンド（図３２）のコピー元ビットアドレス及びコピービット列長に基づいて、データＤ０からコピービット列を取得する。
【０３０１】
図３８は、ステップＳ１１０〜Ｓ１１２におけるデータ更新部１５の処理の一例を示す図である。図３８の例でステップＳ１１０を行う場合には、データ更新部１５は、データＤ０においてコピー元ビッドアドレスａｄｒＣｏｐｙＢＳが示すアドレスから、コピービット列長ｌｎｇＣｏｐｙＢＳまでのコピービット列ＣｏｐｙＢＳを取得する。
【０３０２】
図３６のステップＳ１１１にて、データ更新部１５は、ステップＳ１１０で取得したコピービット列を、データＤ２に格納する。図３８の例でステップＳ１１１を行う場合には、データ更新部１５は、コピービット列ＣｏｐｙＢＳの先頭を、データＤ２の格納ビットアドレスＳＢＡの位置に合わせて、コピービット列ＣｏｐｙＢＳをデータＤ２に格納する。
【０３０３】
図３６のステップＳ１１２にて、データ更新部１５は、格納ビットアドレスＳＢＡに、ステップＳ１０４で取得したコピービットコマンド（図３２）のコピービット列長を加算して、格納ビットアドレスＳＢＡを更新する。図３８の例でステップＳ１１２を行う場合には、格納ビットアドレスＳＢＡに、コピービットコマンドのコピービット列長ｌｎｇＣｏｐｙＢＳを加算する。これにより、格納ビットアドレスＳＢＡは、ステップＳ１１１で格納したコピービット列ＣｏｐｙＢＳ直後のビットアドレスを示すことになる。ステップＳ１１２の後、ステップＳ１０４に戻る。
【０３０４】
ステップＳ１０７からステップＳ１１３に進んだ場合には、新データ（データＤ１）と同じデータＤ２が生成されている。そこで、データ更新部１５は、格納ビットアドレスＳＢＡを、データＤ２のビット列長ｌｎｇＢＳ２として格納する。
【０３０５】
ステップＳ１１４にて、データ更新部１５は、新データと同じデータＤ２をデータ記憶部１４（図３）に格納する。その後、図３６のデータ更新動作を終了する。なお、このとき、旧データを、新データと同じデータＤ２に書き換えてもよく、旧データをデータ記憶部１４から削除してもよい。
【０３０６】
＜実施の形態１のまとめ＞
以上のような本実施の形態１に係る差分データ作成装置１によれば、旧データと、ビット列の順方向及び逆方向に０，１，２，…，ｎビットの範囲でシフトした新データとに基づいて、コピービット列及び追加ビット列を求める。このため、旧データと新データとの間にビット単位のずれが発生していても、差分データにおいて、コピービット列を増加させることができ、追加ビット列を減少させることができる。この結果、差分データのサイズ削減効果を高めることができる。
【０３０７】
また、本実施の形態１では、中間コピービット列情報に基づいて、複数の中間コピービット列のうち互いに重複しない中間コピービット列と、結合ビット列との少なくともいずれか１つを含むビット列の情報を、最終のコピービット列情報として抽出する。これにより、複数のコピービット列情報を、一のコピービット列情報にまとめることができるので、差分データのサイズをより小さくすることができる。
【０３０８】
また、本実施の形態１では、複数のデータＤ１＿ｓと、シフトされていない旧データ（データＤ０）とを、ビット単位で比較することにより、中間コピービット列情報を抽出する。これにより、コピービット列の先頭部分及び末尾部分を抽出することができる。
【０３０９】
また、本実施の形態１では、差分データは、コピービットコマンド（データＤ０に含まれるコピービット列のアドレス及び長さを示す情報）と、追加ビットコマンド（データＤ１に含まれる追加ビット列及び追加ビット列の長さを示す情報）とが、データＤ１（新データ）に含まれるコピービット列及び追加ビット列の、当該データＤ１におけるアドレス順に並べられている。これにより、差分データのサイズを可及的に低減することができる。
【０３１０】
また、本実施の形態１に係るデータ更新装置１１及び情報処理装置２１によれば、差分データ作成装置１で作成された差分データと、旧データとに基づいて新データと同じデータを生成する。したがって、比較的少ない差分データを用いてデータの更新を行うことができる。
【０３１１】
＜実施の形態２＞
実施の形態１に係る差分データ作成装置１は、旧データ（ファイルＦ０のデータＤ０）をシフトさせずに、新データ（ファイルＦ１のデータＤ１）を−７〜７ビットでシフトした。これに対して、本発明の実施の形態２に係る差分データ作成装置１は、新データ（ファイルＦ１のデータＤ１）をシフトさせずに、旧データ（ファイルＦ０のデータＤ０）を−７〜７ビットでシフトする。以下、なお、本実施の形態２に係る差分データ作成装置１において、以上で説明した構成要素と同一または類似するものについては同じ参照符号を付し、異なる部分について主に説明する。
【０３１２】
図３９は、本実施の形態２に係る差分抽出部４及び差分データ生成部６の詳細な構成の一例を示すブロック図である。図３９の構成は、図１５の構成においてファイルＦ１とファイルＦ０とを互いに置き換えたものである。図３９の構成では、−７ビットシフト部４ａ１〜７ビットシフト部４ａ１５は、旧データ（ファイルＦ０のデータＤ０）を−７〜７ビットでシフトする。すなわち、−７ビットシフト部４ａ１〜７ビットシフト部４ａ１５は、旧データを、そのビット列の順方向及び逆方向に、０，１，２，…，７ビットのそれぞれでシフトすることによって、複数のデータＤ０＿−７〜Ｄ０＿７を生成する。生成された複数のデータＤ０＿−７〜Ｄ０＿７は、図示しない内部メモリに格納される。
【０３１３】
ビット差分抽出部４ｂ１〜４ｂ１５は、データＤ０＿−７〜Ｄ０＿７と、シフトされていない新データ（ファイルＦ１のデータＤ１）とをビット単位及びバイト単位で比較することにより、これらデータに共通するビット列の情報を、中間コピービット列情報として抽出する。そして、ビット差分抽出部４ｂ１〜４ｂ１５は、抽出した情報を、中間差分ファイルＭＤＦ＿−７〜ＭＤＦ＿７として中間データ記憶部５に格納する。
【０３１４】
また、実施の形態１で説明した図１６，２０，２１は、本実施の形態２では下記のように変更される。
【０３１５】
図１６のステップＳ４にて、ビットシフト部４ａ（−７ビットシフト部４ａ１〜７ビットシフト部４ａ１５）は、ビットシフト量ｓだけデータＤ０をビットシフトし、それによって得られたデータＤ０＿ｓを内部メモリに格納する。なお、ｓ＝０の場合のデータＤ０＿０は、シフトされていないデータＤ０となる。
【０３１６】
なお、当該ステップＳ４を詳細に示す図２０の各ステップの処理のうち、実施の形態１のデータＤ０，Ｄ１，Ｄ１＿ｓに対する処理を、本実施の形態２のデータＤ１，Ｄ０，Ｄ０＿ｓに対してそれぞれ行う。
【０３１７】
図１６のステップＳ５にて、コピービット列抽出部４ｂ（ビット差分抽出部４ｂ１〜４ｂ１５）は、データＤ０＿ｓとデータＤ１とに基づいて、ビット単位及びバイト単位で比較して中間コピービット列を抽出する。コピービット列抽出部４ｂは、当該中間コピービット列情報を、中間差分ファイルＭＤＦ＿ｓとして中間データ記憶部５に格納する。
【０３１８】
なお、当該ステップＳ５を詳細に示す図２１の各ステップの処理のうち、実施の形態１のデータＤ０，Ｄ１＿ｓに対する処理を、本実施の形態２のデータＤ０＿ｓ，Ｄ１に対してそれぞれ行う。
【０３１９】
ただし、実施の形態１の図２１のステップＳ２８では、ａｄｒ１Ｉｓ，ａｄｒ１Ｉｅが、シフト後のデータＤ１＿ｓでの中間コピービット列の先頭のビットアドレス及び末尾のビットアドレスであることを鑑みて、ａｄｒ１Ｉｓ，ａｄｒ１Ｉｅを補正した。
【０３２０】
これに対して、本実施の形態２では、ａｄｒ１Ｉｓ，ａｄｒ１Ｉｅは、シフトされていないデータＤ１での中間コピービット列の先頭のビットアドレス及び末尾のビットアドレスであるので、コピービット列抽出部４ｂは、ａｄｒ１Ｉｓ，ａｄｒ１Ｉｅを補正しない。一方、本実施の形態２では、ａｄｒ０Ｉｓ，ａｄｒ０Ｉｅは、シフト後のデータＤ０＿ｓでの中間コピービット列の先頭のビットアドレス及び末尾のビットアドレスであるので、コピービット列抽出部４ｂは、ａｄｒ０Ｉｓ，ａｄｒ０Ｉｅを、ビットシフト部４ａがシフトを行う前のアドレスに補正する。
【０３２１】
図４０は、本実施の形態２に係る差分データ作成装置１によって図６のコピービット列Ｅ（ｉ）を抽出する処理の一例を示す図である。以下、図４０を例にして、本実施の形態２に係るステップＳ５の処理を説明する。図４０では、データＤ０をシフトすべきビットシフト量ｓ＝Ｓ（ｉ）＝２である。
【０３２２】
ステップＳ２１にて、コピービット列抽出部４ｂは、データＤ０＿ｓ（データＤ０を２ビットだけシフトされたデータＤ０）と、データＤ１とからバイト差分データを求める。ここで求まるバイト差分データは、図４０のビット列ＭＩに関するデータであり、下記のフィールドを持つコピーコマンドを含む。なお、下記のコピーコマンドの表記には、図４０のｏｆｓＥｓ（ｉ）及びｂｙｌｎｇＣｏｐｙＥ（ｉ）が用いられている。
【０３２３】
コピー元オフセット=ofsEs(i)+1  （データD0_sにおけるオフセット）
コピーバイト列長=bylngCopyE(i)
【０３２４】
ステップＳ２２にて、コピービット列抽出部４ｂは、上記コピーコマンドを取得する。ステップＳ２３〜Ｓ２５を経てステップＳ２６にて、コピービット列抽出部４ｂは、コピー元オフセット（データＤ０＿ｓのｏｆｓＥｓ（ｉ）＋１）をＯＦＳ０に設定し、コピーバイト列長（ｂｙｌｎｇＣｏｐｙＥ（ｉ））をＣＢＹＴＬに設定する。なお、ＯＦＳ１は、データＤ１における追加バイト列またはコピーバイト列の先頭バイト列のオフセットを示しており、ここでは図４０のデータＤ１のｏｆｓＡｓ（ｉ）＋１に相当する。
【０３２５】
ステップＳ２６にて、コピービット列抽出部４ｂは、データＤ０＿ｓのオフセットがＯＦＳ０−１＝ｏｆｓＥｓ（ｉ）である１バイトと、データＤ１のオフセットがＯＦＳ１−１＝ｏｆｓＡｓ（ｉ）である１バイトとを、最下位ビットから順に比較する。これにより、ビット列ＳＴが得られ、ＸＢＮ＝４が得られる。この結果、データＤ０＿ｓにおける中間コピービット列の先頭のａｄｒ０Ｉｓ（＝ｂｉｔｎＥｓ＿ｓ（ｉ））と、データＤ１における中間コピービット列の先頭のａｄｒ１Ｉｓ（＝ｂｉｔｎＡｓ（ｉ））とが得られる。
【０３２６】
ステップＳ２７にて、コピービット列抽出部４ｂは、データＤ０＿ｓのオフセットがＯＦＳ０＋ＣＢＹＴＬ＝ｏｆｓＥｅ（ｉ）である１バイトと、データＤ１のオフセットがＯＦＳ１＋ＣＢＹＴＬ＝ｏｆｓＡｅ（ｉ）である１バイトとを、最上位ビットから順に比較する。これにより、ビット列ＥＮが得られ、ＹＢＮ＝６が得られる。この結果、データＤ０＿ｓにおける中間コピービット列の末尾のａｄｒ０Ｉｅ（＝ｂｉｔｎＥｅ＿ｓ（ｉ））と、データＤ１における中間コピービット列の末尾のａｄｒ１Ｉｅ（＝ｂｉｔｎＡｅ（ｉ））とが得られる。
【０３２７】
ステップＳ２８にて、コピービット列抽出部４ｂは、データＤ０＿ｓにおけるａｄｒ０Ｉｓ（＝ｂｉｔｎＥｓ＿ｓ（ｉ））、及び、ａｄｒ０Ｉｅ（＝ｂｉｔｎＥｅ＿ｓ（ｉ））を、ビットシフト部４ａのシフト（ステップＳ４）と逆方向にシフトする。これにより、データＤ０におけるｂｉｔｎＥｓ（ｉ），ｂｉｔｎＥｅ（ｉ）が得られる。
【０３２８】
＜実施の形態２のまとめ＞
以上のような本実施の形態２に係る差分データ作成装置１によれば、実施の形態１と同様の効果（例えば、差分データのサイズ削減効果の向上化など）が得られる。
【０３２９】
＜実施の形態１及び実施の形態２の変形例＞
以上に説明した構成では、データ全体がビット列の場合について説明した。しかしこれに限ったものではなく、バイト単位のデータとビット列データ（ビット単位のデータ）とが混在していてもよい。
【０３３０】
また、以上の説明では、ステップＳ８（図１６）でコピービット列情報を先に求め、ステップＳ９で新データからコピービット列を除くことにより追加ビット列情報を求めた。しかしこれに限ったものではなく、先に追加ビット列情報を求め、新データから追加ビット列を除くことによりコピービット列情報を求めてもよい。
【０３３１】
さらに、以上に説明した差分データにおいて、コピービットコマンドと、追加ビットコマンドとは、データＤ１に含まれるコピービット列及び追加ビット列の、当該データＤ１におけるアドレスの昇順に並べられていた。しかしこれらは昇順に並べられなくてもよく、例えば降順に並べられてもよい。これらを概括すると、コピービットコマンドと、追加ビットコマンドとは、データＤ１に含まれるコピービット列及び追加ビット列の、当該データＤ１におけるアドレス順にソートされていればよい。
【０３３２】
また、以上に説明した構成では、図２１のステップＳ２３，Ｓ２４，Ｓ２５，Ｓ２６，Ｓ２７にて、コピービット列抽出部４ｂは、複数のデータＤ１＿ｓと、シフトされていない旧データとを、ビット単位及びバイト単位の両方で比較することにより、中間差分ファイルＭＤＦ＿ｓを抽出した。しかしこれに限ったものではなく、コピービット列抽出部４ｂは、複数のデータＤ１＿ｓと、シフトされていない旧データとを、ビット単位だけで比較することにより、中間差分ファイルＭＤＦ＿ｓを抽出してもよい。
【０３３３】
さらに、差分データ作成装置１は、車両に搭載可能なナビゲーション装置、Portable Navigation Device、通信端末（例えば携帯電話、スマートフォン、及びタブレットなどの携帯端末）、及びこれらにインストールされるアプリケーションの機能、並びにサーバなどを適宜に組み合わせてシステムとして構築される差分データ作成システムにも適用することができる。この場合、以上で説明した差分データ作成装置１の各機能あるいは各構成要素は、前記システムを構築する各機器に分散して配置されてもよいし、いずれかの機器に集中して配置されてもよい。
【０３３４】
なお、本発明は、その発明の範囲内において、各実施の形態及び各変形例を自由に組み合わせたり、各実施の形態及び各変形例を適宜、変形、省略したりすることが可能である。
【０３３５】
本発明は詳細に説明されたが、上記した説明は、すべての態様において、例示であって、本発明がそれに限定されるものではない。例示されていない無数の変形例が、本発明の範囲から外れることなく想定され得るものと解される。
【符号の説明】
【０３３６】
１  差分データ作成装置、４ａ  ビットシフト部、４ｂ  コピービット列抽出部、４ｃ  追加ビット列抽出部、６  差分データ生成部、１１  データ更新装置、２１  情報処理装置。
【図１】
2016016923.tif 000004
【図２】
2016016923.tif 000005
【図３】
2016016923.tif 000006
【図４】
2016016923.tif 000007
【図５】
2016016923.tif 000008
【図６】
2016016923.tif 000009
【図７】
2016016923.tif 000010
【図８】
2016016923.tif 000011
【図９】
2016016923.tif 000012
【図１０】
2016016923.tif 000013
【図１１】
2016016923.tif 000014
【図１２】
2016016923.tif 000015
【図１３】
2016016923.tif 000016
【図１４】
2016016923.tif 000017
【図１５】
2016016923.tif 000018
【図１６】
2016016923.tif 000019
【図１７】
2016016923.tif 000020
【図１８】
2016016923.tif 000021
【図１９】
2016016923.tif 000022
【図２０】
2016016923.tif 000023
【図２１】
2016016923.tif 000024
【図２２】
2016016923.tif 000025
【図２３】
2016016923.tif 000026
【図２４】
2016016923.tif 000027
【図２５】
2016016923.tif 000028
【図２６】
2016016923.tif 000029
【図２７】
2016016923.tif 000030
【図２８】
2016016923.tif 000031
【図２９】
2016016923.tif 000032
【図３０】
2016016923.tif 000033
【図３１】
2016016923.tif 000034
【図３２】
2016016923.tif 000035
【図３３】
2016016923.tif 000036
【図３４】
2016016923.tif 000037
【図３５】
2016016923.tif 000038
【図３６】
2016016923.tif 000039
【図３７】
2016016923.tif 000040
【図３８】
2016016923.tif 000041
【図３９】
2016016923.tif 000042
【図４０】
2016016923.tif 000043
【手続補正書】
【提出日】平成28年10月31日(2016.10.31)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項５
【補正方法】変更
【補正の内容】
【請求項５】
請求項１に記載の差分データ作成システムで作成された前記差分データと、前記旧データとに基づいて前記新データと同じ前記データを生成し、前記データの生成において、前記差分データに基づく前記コピービット列のビット列長と、前記差分データに基づく前記追加ビット列のビット列長とを用いる、データ更新システム。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項６
【補正方法】変更
【補正の内容】
【請求項６】
旧データから新データと同じデータを生成するための差分データを作成する差分データ作成方法であって、
ビットシフト部が、前記旧データ及び前記新データの一方のデータを、そのビット列の順方向及び逆方向に、０，１，２，…，ｎビットのそれぞれでシフトすることによって複数のデータを生成し、
コピービット列抽出部が、生成された前記複数のデータと、シフトされていない他方のデータとに基づいて、前記旧データと前記新データとに共通するビット列の情報を、コピービット列の情報として抽出し、
追加ビット列抽出部が、前記新データのうち前記コピービット列以外のビット列の情報を、追加ビット列の情報として抽出し、
差分データ作成部が、前記コピービット列の情報と、前記追加ビット列の情報とに基づいて、前記差分データを作成する、差分データ作成方法。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
本発明に係る差分データ作成方法は、旧データから新データと同じデータを生成するための差分データを作成する差分データ作成方法であって、ビットシフト部が、旧データ及び新データの一方のデータを、そのビット列の順方向及び逆方向に、０，１，２，…，ｎビットのそれぞれでシフトすることによって複数のデータを生成し、コピービット列抽出部が、生成された複数のデータと、シフトされていない他方のデータとに基づいて、旧データと新データとに共通するビット列の情報を、コピービット列の情報として抽出し、追加ビット列抽出部が、新データのうちコピービット列以外のビット列の情報を、追加ビット列の情報として抽出し、差分データ作成部が、コピービット列の情報と、追加ビット列の情報とに基づいて、差分データを作成する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０３０１
【補正方法】変更
【補正の内容】
【０３０１】
図３８は、ステップＳ１１０〜Ｓ１１２におけるデータ更新部１５の処理の一例を示す図である。図３８の例でステップＳ１１０を行う場合には、データ更新部１５は、データＤ０においてコピー元ビットアドレスａｄｒＣｏｐｙＢＳが示すアドレスから、コピービット列長ｌｎｇＣｏｐｙＢＳまでのコピービット列ＣｏｐｙＢＳを取得する。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０３２２
【補正方法】変更
【補正の内容】
【０３２２】
ステップＳ２１にて、コピービット列抽出部４ｂは、データＤ０＿ｓ（データＤ０を２ビットだけシフトされたデータ）と、データＤ１とからバイト差分データを求める。ここで求まるバイト差分データは、図４０のビット列ＭＩに関するデータであり、下記のフィールドを持つコピーコマンドを含む。なお、下記のコピーコマンドの表記には、図４０のｏｆｓＥｓ（ｉ）及びｂｙｌｎｇＣｏｐｙＥ（ｉ）が用いられている。
【国際調査報告】
2016016923.tif 000044
2016016923.tif 000045
2016016923.tif 000046
2016016923.tif 000047