(57)【特許請求の範囲】
【請求項１】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成装置において、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する類似ブロック抽出部と、
前記類似ブロック抽出部が生成した前記類似ブロック情報に含まれる前記類似パターンを、変換ルールとしてブロックソート法の符号化方法を用いて変換することにより変換後類似パターンを生成し、生成された前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成する類似パターン変換部と、
前記類似パターン変換部が生成した前記変換後類似ブロック情報を使用して、前記ブロック差分情報を生成する差分情報生成部と
を備えたことを特徴とする差分生成装置。
【請求項２】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成装置において、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する類似ブロック抽出部と、
前記類似ブロック抽出部が生成した前記類似ブロック情報に含まれる前記類似パターンを、変換ルールとしてブロックソート法の符号化方法を用いて変換することにより前記類似パターンから変換後類似パターンを生成し、生成された前記変換後類似パターンと前記類似パターンとのうちのいずれを用いた場合が前記ブロック差分情報のデータサイズが小さくなるかを判断して前記ブロック差分情報のデータサイズを小さくする方を選択パターンとして選択し、前記選択パターンが前記変換後類似パターンである場合には前記選択パターンである前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記類似ブロック情報から前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成して出力し、前記選択パターンが前記類似パターンである場合には前記類似ブロック情報を出力する類似パターン変換部と、
前記類似パターン変換部が前記変換後類似ブロック情報を出力した場合には前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報を使用して前記ブロック差分情報を生成し、前記類似パターン変換部が前記類似ブロック情報を出力した場合には前記類似ブロック情報を入力し、入力した前記類似ブロック情報を使用して前記ブロック差分情報を生成する差分情報生成部と
を備えたことを特徴とする差分生成装置。
【請求項３】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成装置において、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する類似ブロック抽出部と、
前記類似ブロック抽出部が生成した前記類似ブロック情報に含まれる前記類似パターンを、ブロックソート法の符号化方法による第１変換ルールと、ブロックソート法の符号化方法により符号化された二値データ列をＭＴＦ（Ｍｏｖｅ  Ｔｏ  Ｆｒｏｎｔ）法で符号化する方法による第２変換ルールとのそれぞれを用いて変換することにより前記類似パターンから変換後類似パターンをそれぞれの前記変換ルールごとに生成し、それぞれの前記変換ルールごとに生成された前記変換後類似パターンのそれぞれと前記類似パターンとのうちのいずれを用いた場合が前記ブロック差分情報のデータサイズが最小になるかを判断して前記ブロック差分情報のデータサイズを最小にするものを選択パターンとして選択し、前記選択パターンがそれぞれの前記変換ルールごとに生成された前記変換後類似パターンのいずれかである場合には前記選択パターンである前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記類似ブロック情報から前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成して出力し、前記選択パターンが前記類似パターンである場合には前記類似ブロック情報を出力する類似パターン変換部と、
前記類似パターン変換部が前記変換後類似ブロック情報を出力した場合には前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報を使用して前記ブロック差分情報を生成し、前記類似パターン変換部が前記類似ブロック情報を出力した場合には前記類似ブロック情報を入力し、入力した前記類似ブロック情報を使用して前記ブロック差分情報を生成する差分情報生成部と
を備えたことを特徴とする差分生成装置。
【請求項４】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成装置であって、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する類似ブロック抽出部と、
前記類似ブロック抽出部が生成した前記類似ブロック情報に含まれる前記類似パターンを、変換ルールとしてブロックソート法の符号化方法を用いて変換することにより変換後類似パターンを生成し、生成された前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成する類似パターン変換部と、
前記類似パターン変換部が生成した前記変換後類似ブロック情報を使用して、前記ブロック差分情報を生成する差分情報生成部と
を備えた差分生成装置
が生成した前記ブロック差分情報を入力し、入力した前記ブロック差分情報から前記変換後類似ブロック情報を生成する差分情報解析部と、
前記差分情報解析部が生成した前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報に含まれる前記変換後類似パターンを前記差分生成装置の前記類似パターン変換部による変換の逆変換をすることにより前記変換後類似パターンから前記類似パターンを生成し、生成した前記類似パターンを前記変換後類似ブロック情報に含まれる前記変換後類似パターンと置き換えることにより前記類似ブロック情報を生成する類似パターン逆変換部と、
前記類似パターン逆変換部が生成した前記類似ブロック情報に基づいて旧版データを更新した新版データを生成する差分情報適用部と
を備えたことを特徴とする差分適用装置。
【請求項５】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成装置であって、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する類似ブロック抽出部と、
前記類似ブロック抽出部が生成した前記類似ブロック情報に含まれる前記類似パターンを、変換ルールとしてブロックソート法の符号化方法を用いて変換することにより前記類似パターンから変換後類似パターンを生成し、生成された前記変換後類似パターンと前記類似パターンとのうちのいずれを用いた場合が前記ブロック差分情報のデータサイズが小さくなるかを判断して前記ブロック差分情報のデータサイズを小さくする方を選択パターンとして選択し、前記選択パターンが前記変換後類似パターンである場合には前記選択パターンである前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記類似ブロック情報から前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成して出力し、前記選択パターンが前記類似パターンである場合には前記類似ブロック情報を出力する類似パターン変換部と、
前記類似パターン変換部が前記変換後類似ブロック情報を出力した場合には前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報を使用して前記ブロック差分情報を生成し、前記類似パターン変換部が前記類似ブロック情報を出力した場合には前記類似ブロック情報を入力し、入力した前記類似ブロック情報を使用して前記ブロック差分情報を生成する差分情報生成部と
を備えた差分生成装置
の前記差分情報生成部が前記変換後類似ブロック情報を使用して生成した前記ブロック差分情報を入力した場合に、入力した前記ブロック差分情報から前記変換後類似ブロック情報を生成する差分情報解析部と、
前記差分情報解析部が生成した前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報に含まれる前記変換後類似パターンを前記差分生成装置の前記類似パターン変換部による変換の逆変換をすることにより前記変換後類似パターンから前記類似パターンを生成し、生成した前記類似パターンを前記変換後類似ブロック情報に含まれる前記変換後類似パターンと置き換えることにより前記類似ブロック情報を生成する類似パターン逆変換部と、
前記類似パターン逆変換部が生成した前記類似ブロック情報に基づいて旧版データを更新した新版データを生成する差分情報適用部とを備えたことを特徴とする差分適用装置。
【請求項６】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成装置であって、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する類似ブロック抽出部と、
前記類似ブロック抽出部が生成した前記類似ブロック情報に含まれる前記類似パターンを、ブロックソート法の符号化方法による第１変換ルールと、ブロックソート法の符号化方法により符号化された二値データ列をＭＴＦ（Ｍｏｖｅ  Ｔｏ  Ｆｒｏｎｔ）法で符号化する方法による第２変換ルールとのそれぞれを用いて変換することにより前記類似パターンから変換後類似パターンをそれぞれの前記変換ルールごとに生成し、それぞれの前記変換ルールごとに生成された前記変換後類似パターンのそれぞれと前記類似パターンとのうちのいずれを用いた場合が前記ブロック差分情報のデータサイズが最小になるかを判断して前記ブロック差分情報のデータサイズを最小にするものを選択パターンとして選択し、前記選択パターンがそれぞれの前記変換ルールごとに生成された前記変換後類似パターンのいずれかである場合には前記選択パターンである前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記類似ブロック情報から前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成して出力し、前記選択パターンが前記類似パターンである場合には前記類似ブロック情報を出力する類似パターン変換部と、
前記類似パターン変換部が前記変換後類似ブロック情報を出力した場合には前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報を使用して前記ブロック差分情報を生成し、前記類似パターン変換部が前記類似ブロック情報を出力した場合には前記類似ブロック情報を入力し、入力した前記類似ブロック情報を使用して前記ブロック差分情報を生成する差分情報生成部と
を備えた差分生成装置
の前記差分情報生成部が前記変換後類似ブロック情報を使用して生成した前記ブロック差分情報を入力した場合に、入力した前記ブロック差分情報から前記変換後類似ブロック情報を生成する差分情報解析部と、
前記差分情報解析部が生成した前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報に含まれる前記変換後類似パターンを前記差分生成装置の前記類似パターン変換部による変換の逆変換をすることにより前記変換後類似パターンから前記類似パターンを生成し、生成した前記類似パターンを前記変換後類似ブロック情報に含まれる前記変換後類似パターンと置き換えることにより前記類似ブロック情報を生成する類似パターン逆変換部と、
前記類似パターン逆変換部が生成した前記類似ブロック情報に基づいて旧版データを更新した新版データを生成する差分情報適用部と
を備えたことを特徴とする差分適用装置。
【請求項７】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成プログラムにおいて、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する処理と、
生成された前記類似ブロック情報に含まれる前記類似パターンを、変換ルールとしてブロックソート法の符号化方法を用いて変換することにより変換後類似パターンを生成し、生成された前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成する処理と、
生成された前記変換後類似ブロック情報を使用して、前記ブロック差分情報を生成する処理と
をコンピュータに実行させるための差分生成プログラム。
【請求項８】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成プログラムにおいて、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する処理と、
生成された前記類似ブロック情報に含まれる前記類似パターンを、変換ルールとしてブロックソート法の符号化方法を用いて変換することにより前記類似パターンから変換後類似パターンを生成し、生成された前記変換後類似パターンと前記類似パターンとのうちのいずれを用いた場合が前記ブロック差分情報のデータサイズが小さくなるかを判断して前記ブロック差分情報のデータサイズを小さくする方を選択パターンとして選択し、前記選択パターンが前記変換後類似パターンである場合には前記選択パターンである前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記類似ブロック情報から前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成して出力し、前記選択パターンが前記類似パターンである場合には前記類似ブロック情報を出力する処理と、
前記変換後類似ブロック情報が出力された場合には前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報を使用して前記ブロック差分情報を生成し、前記類似ブロック情報が出力された場合には前記類似ブロック情報を入力し、入力した前記類似ブロック情報を使用して前記ブロック差分情報を生成する処理と
をコンピュータに実行させるための差分生成プログラム。
【請求項９】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成プログラムにおいて、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する処理と、
生成された前記類似ブロック情報に含まれる前記類似パターンを、ブロックソート法の符号化方法による第１変換ルールと、ブロックソート法の符号化方法により符号化された二値データ列をＭＴＦ（Ｍｏｖｅ  Ｔｏ  Ｆｒｏｎｔ）法で符号化する方法による第２変換ルールとのそれぞれを用いて変換することにより前記類似パターンから変換後類似パターンをそれぞれの前記変換ルールごとに生成し、それぞれの前記変換ルールごとに生成された前記変換後類似パターンのそれぞれと前記類似パターンとのうちのいずれを用いた場合が前記ブロック差分情報のデータサイズが最小になるかを判断して前記ブロック差分情報のデータサイズを最小にするものを選択パターンとして選択し、前記選択パターンがそれぞれの前記変換ルールごとに生成された前記変換後類似パターンのいずれかである場合には前記選択パターンである前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記類似ブロック情報から前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成して出力し、前記選択パターンが前記類似パターンである場合には前記類似ブロック情報を出力する処理と、
前記変換後類似ブロック情報が出力された場合には前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報を使用して前記ブロック差分情報を生成し、前記類似ブロック情報が出力された場合には前記類似ブロック情報を入力し、入力した前記類似ブロック情報を使用して前記ブロック差分情報を生成する処理と
をコンピュータに実行させるための差分生成プログラム。
【請求項１０】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成装置であって、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する類似ブロック抽出部と、
前記類似ブロック抽出部が生成した前記類似ブロック情報に含まれる前記類似パターンを、変換ルールとしてブロックソート法の符号化方法を用いて変換することにより変換後類似パターンを生成し、生成された前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成する類似パターン変換部と、
前記類似パターン変換部が生成した前記変換後類似ブロック情報を使用して、前記ブロック差分情報を生成する差分情報生成部と
を備えた差分生成装置
が生成した前記ブロック差分情報を入力し、入力した前記ブロック差分情報から前記変換後類似ブロック情報を生成する第１処理と、
前記第１処理により生成された前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報に含まれる前記変換後類似パターンを前記差分生成装置の前記類似パターン変換部による変換の逆変換をすることにより前記変換後類似パターンから前記類似パターンを生成し、生成した前記類似パターンを前記変換後類似ブロック情報に含まれる前記変換後類似パターンと置き換えることにより前記類似ブロック情報を生成する第２処理と、
前記第２処理により生成された前記類似ブロック情報に基づいて旧版データを更新した新版データを生成する第３処理と
をコンピュータに実行させるための差分適用プログラム。
【請求項１１】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成装置であって、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する類似ブロック抽出部と、
前記類似ブロック抽出部が生成した前記類似ブロック情報に含まれる前記類似パターンを、変換ルールとしてブロックソート法の符号化方法を用いて変換することにより前記類似パターンから変換後類似パターンを生成し、生成された前記変換後類似パターンと前記類似パターンとのうちのいずれを用いた場合が前記ブロック差分情報のデータサイズが小さくなるかを判断して前記ブロック差分情報のデータサイズを小さくする方を選択パターンとして選択し、前記選択パターンが前記変換後類似パターンである場合には前記選択パターンである前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記類似ブロック情報から前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成して出力し、前記選択パターンが前記類似パターンである場合には前記類似ブロック情報を出力する類似パターン変換部と、
前記類似パターン変換部が前記変換後類似ブロック情報を出力した場合には前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報を使用して前記ブロック差分情報を生成し、前記類似パターン変換部が前記類似ブロック情報を出力した場合には前記類似ブロック情報を入力し、入力した前記類似ブロック情報を使用して前記ブロック差分情報を生成する差分情報生成部と
を備えた差分生成装置
の前記差分情報生成部によって前記変換後類似ブロック情報を使用して生成された前記ブロック差分情報を入力した場合に、入力した前記ブロック差分情報から前記変換後類似ブロック情報を生成する第１処理と、
前記第１処理により生成された前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報に含まれる前記変換後類似パターンを前記差分生成装置の前記類似パターン変換部による変換の逆変換をすることにより前記変換後類似パターンから前記類似パターンを生成し、生成した前記類似パターンを前記変換後類似ブロック情報に含まれる前記変換後類似パターンと置き換えることにより前記類似ブロック情報を生成する第２処理と、
前記第２処理により生成された前記類似ブロック情報に基づいて旧版データを更新した新版データを生成する第３処理と
をコンピュータに実行させるための差分適用プログラム。
【請求項１２】
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成装置であって、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンと、前記類似パターンによって不一致が示される場合に、前記類似ブロックである前記データ列における不一致箇所のデータを示す差異箇所データ情報とを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する類似ブロック抽出部と、
前記類似ブロック抽出部が生成した前記類似ブロック情報に含まれる前記類似パターンを、ブロックソート法の符号化方法による第１変換ルールと、ブロックソート法の符号化方法により符号化された二値データ列をＭＴＦ（Ｍｏｖｅ  Ｔｏ  Ｆｒｏｎｔ）法で符号化する方法による第２変換ルールとのそれぞれを用いて変換することにより前記類似パターンから変換後類似パターンをそれぞれの前記変換ルールごとに生成し、それぞれの前記変換ルールごとに生成された前記変換後類似パターンのそれぞれと前記類似パターンとのうちのいずれを用いた場合が前記ブロック差分情報のデータサイズが最小になるかを判断して前記ブロック差分情報のデータサイズを最小にするものを選択パターンとして選択し、前記選択パターンがそれぞれの前記変換ルールごとに生成された前記変換後類似パターンのいずれかである場合には前記選択パターンである前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記類似ブロック情報から前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成して出力し、前記選択パターンが前記類似パターンである場合には前記類似ブロック情報を出力する類似パターン変換部と、
前記類似パターン変換部が前記変換後類似ブロック情報を出力した場合には前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報を使用して前記ブロック差分情報を生成し、前記類似パターン変換部が前記類似ブロック情報を出力した場合には前記類似ブロック情報を入力し、入力した前記類似ブロック情報を使用して前記ブロック差分情報を生成する差分情報生成部と
を備えた差分生成装置
の前記差分情報生成部によって前記変換後類似ブロック情報を使用して生成された前記ブロック差分情報を入力した場合に、入力した前記ブロック差分情報から前記変換後類似ブロック情報を生成する第１処理と、
前記第１処理により生成された前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報に含まれる前記変換後類似パターンを前記差分生成装置の前記類似パターン変換部による変換の逆変換をすることにより前記変換後類似パターンから前記類似パターンを生成し、生成した前記類似パターンを前記変換後類似ブロック情報に含まれる前記変換後類似パターンと置き換えることにより前記類似ブロック情報を生成する第２処理と、
前記第２処理により生成された前記類似ブロック情報に基づいて旧版データを更新した新版データを生成する第３処理と
をコンピュータに実行させるための差分適用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各種データについて新旧バージョン間の差分を抽出して差分情報を生成する差分生成装置、および旧版データに差分情報を適用して新版データを再生する差分適用装置に関する。
【背景技術】
【０００２】
パーソナルコンピュータや組込み機器（携帯電話、カーナビゲーションシステムなど）などの装置では、プロセッサによって扱われるプログラムなどのデータを更新（バージョンアップ）することがある。バージョンアップの際には、「記憶媒体や通信網を介して旧版（更新前）データと新版（更新後）データの差分情報を装置に送り、装置内で差分情報を旧版データに適用して新版データを生成する」という方法が一般的である。なお、旧版データと新版データとの差分情報は、バージョンアップ対象の装置（差分適用装置）とは別の装置（差分生成装置）においてあらかじめ生成される。
【０００３】
通信帯域の狭い無線網などを使用して差分情報を装置に送付するようなシステムにおいては特に、差分情報のサイズは小さいことが望ましい。そして、差分情報の表現方法、抽出方法を工夫することによって、差分情報のサイズを小さくすることが可能である。
【０００４】
図２３は旧版データ９０１と新版データ９０２の一部を示す図である。各種データ、特に組込み機器向けプログラムデータなどのバージョンアップに際しては、図２３に示すように旧版データ中のブロック９０３が新版データでは別の位置９０４に移動して、且つ、移動した先では飛び飛びでデータの内容が変更になっている、というパターンが多く見られる。このパターンの多くは、「データ内参照を行っている箇所が位置ずれによって変更になっている」という場合である。図２３では変更箇所９１１、９１２、９１３、９１４がデータ内容が変更になっている。
【０００５】
図２４は従来例による差分情報９５１，９５２を示す図である。図２３に示す旧版データ９０１と新版データ９０２とに対する差分情報として、一般的な差分データ表現方法による差分情報を図２４に基づいて説明する。一般的な差分情報表現方法としては、例えばＷａｌｔｅｒ  Ｆ．Ｔｉｃｈｙの論文「Ｔｈｅ  Ｓｔｒｉｎｇ−ｔｏ−Ｓｔｒｉｎｇ  Ｃｏｒｒｅｃｔｉｏｎ  Ｐｒｏｂｌｅｍ  ｗｉｔｈ  Ｂｌｏｃｋ  Ｍｏｖｅｓ」がある。この表現方法は、旧版データの一部、あるいは全部からデータを移動して新版データにコピーすることを意味するＭｏｖｅ命令と、新版データに当該差分情報中に記述したデータを追加することを意味するＡｄｄ命令とを差分情報表現に用いる方法である。
【０００６】
図２３の例に適用すると（ただし図示するブロックの範囲に限定）、図２４に示すような差分情報９５１で旧版データと新版データの間の差分を表現できる。詳細には、変更箇所９１１〜９１４に対するＡｄｄ命令と、これらの変更箇所の間の部分を示すＭｏｖｅ命令の繰り返しで表現することができる。Ｍｏｖｅ命令には旧版データにおける位置情報が必要となるため、図２４のようにＭｏｖｅ命令とＡｄｄ命令が交互に現れるようなケースではＭｏｖｅ命令の位置情報（０ｘ３００等）が差分データサイズ増加の要因の一つとなってしまう。
【０００７】
特許文献１では、Ｍｏｖｅ命令の位置情報により差分データサイズが増加することに対して、Ｍｏｖｅ命令には新版データと旧版データのオフセット情報を用い、Ｍｏｖｅ命令を表現する際には直前のＭｏｖｅ命令のオフセット情報を参照し、オフセットが同じ場合は１ビットのフラグを立てて直前のＭｏｖｅ命令とオフセットが同じであることを示すことで、Ｍｏｖｅ命令のオフセット情報を省略するという方法が開示されている。本方法によれば、Ｍｏｖｅ命令を表現するために必要なデータ量を小さくすることが出来る。図２４の差分情報９５２は、この方法による場合を示している。
【０００８】
しかしながら、特許文献１の方法でも変更箇所の数だけＡｄｄ命令とＭｏｖｅ命令が必要となること自体は変わらないため、飛び飛びで変更になるデータの箇所数が非常に多い場合には差分情報のサイズは大きくなってしまうという課題が残る。
【０００９】
特許文献２では、プログラム等に代表されるようなデータ内参照を有しているデータに対して、前記のＡｄｄ命令とＭｏｖｅ命令の繰り返しを回避する方法が開示されている。特許文献２の方法における差分情報を抽出する側では、データ内参照に相当する箇所をマークしてから新版データと旧版データの比較を行うことで、データ内参照に相当する箇所を差分情報に含まないようにする。差分情報を適用する側ではデータ内参照に相当する箇所を検出し、位置移動の情報からデータ内参照に相当する箇所の差分を自動的に再生することで新版データを生成する。こうすることによって、データ内参照に起因する前記の図２３のような変更パターンに対して、Ａｄｄ命令とＭｏｖｅ命令の繰り返しを回避することが可能となる。
【００１０】
しかしながら、特許文献２の方法では、更新対象とするデータの中でどの箇所がデータ内参照であるかという知識、つまり更新対象データの構造的知識を前提としているため、汎用的ではないと言う課題がある。
【特許文献１】特開２００４−１５２１３６号公報
【特許文献２】米国特許６，５４６，５５２号
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、従来の技術では差分情報を小さいサイズで表現できないあるいは、更新対象データの構造的知識を前提としてのみ差分情報を小さいサイズで表現できるような更新パターンにおいて、更新対象データの構造的知識を前提とせずに差分情報を小さく表現できるようにすることを目的とする。
【課題を解決するための手段】
【００１２】
この発明の差分生成装置は、
旧版データと前記旧版データを更新した新版データとの差分を示す差分情報を生成する差分生成装置において、
前記旧版データの一部分のデータ列に類似するとともに前記新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、
抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する類似ブロック抽出部と、
前記類似ブロック抽出部が生成した前記類似ブロック情報に含まれる前記類似パターンを所定の変換ルールを用いて変換することにより変換後類似パターンを生成し、
生成された前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成する類似パターン変換部と、
前記類似パターン変換部が生成した前記変換後類似ブロック情報を使用して、前記ブロック差分情報を生成する差分情報生成部と
を備えたことを特徴とする。
【発明の効果】
【００１３】
本発明によれば、従来の技術では差分データを小さいデータサイズで表現できなかったような更新パターンに対して、小さいデータサイズで差分情報を表現できる。
【発明を実施するための最良の形態】
【００１４】
実施の形態１．
図１〜図１６を用いて実施の形態１を説明する。旧版データから新版データに移動する（更新される）ブロックにおいて、差異箇所が分散していることが差分情報のデータサイズ増加の原因である。そこで、本実施の形態１では、ブロック内の差異箇所の表現を工夫することによって、差分情報のデータサイズを小さくする。
【００１５】
図１は、この実施の形態１における差分抽出適用システム１０００のシステム構成図である。差分抽出適用システム１０００は、各種データについて新旧バージョン間の差分を抽出して差分情報を生成する差分生成装置の一例であるサーバ装置１００ａと、サーバ装置１００ａが生成した差分情報を旧版データに適用して新版データを再生する差分適用装置の一例である携帯電話２００ａ、ユーザ端末装置２００ｂを備える。サーバ装置１００ａが生成した差分情報は、インターネットなどのネットワークを介して携帯電話２００ａやユーザ端末装置２００ｂの差分適用装置に送られる。あるいは、サーバ装置１００ａが生成した差分情報は、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ）などの記録媒体により携帯電話２００ａやユーザ端末装置２００ｂのユーザに配布されてもよい。
【００１６】
図２は、コンピュータであるサーバ装置１００ａ（差分生成装置）の外観の一例を示す図である。なお、ユーザ端末装置２００ｂ（差分適用装置）もコンピュータであり、図２のサーバ装置１００ａと同様の構成である。携帯電話２００ａ（差分適用装置）は図２とは外観は異なるものの、処理装置（ＣＰＵ：Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）、入出力装置、記憶装置を備えたコンピュータであることはもちろんである。
【００１７】
図２において、サーバ装置１００ａは、システムユニット８３０、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）やＬＣＤ（液晶）の表示画面を有する表示装置８１３、キーボード８１４（Ｋｅｙ・Ｂｏａｒｄ：Ｋ／Ｂ）、マウス８１５、ＦＤＤ８１７（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、コンパクトディスク装置８１８（ＣＤＤ：Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｄｒｉｖｅ）、プリンタ装置８１９などのハードウェア資源を備え、これらはケーブルや信号線で接続されている。
【００１８】
システムユニット８３０は、コンピュータであり、また、ローカルエリアネットワーク（ＬＡＮ）、を介してインターネットに接続されている。サーバ装置１００ａは、インターネットを介して携帯電話２００ａ，ユーザ端末装置２００ｂと通信可能である。
【００１９】
図３は、実施の形態１におけるサーバ装置１００ａのハードウェア資源の一例を示す図である。図３において、サーバ装置１００ａは、プログラムを実行するＣＰＵ８１０（中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ８１０は、バス８２５を介してＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）８１１、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）８１２、表示装置８１３、キーボード８１４、マウス８１５、通信ボード８１６、ＦＤＤ８１７、ＣＤＤ８１８、プリンタ装置８１９、磁気ディスク装置８２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置８２０の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。
【００２０】
ＲＡＭ８１２は、揮発性メモリの一例である。ＲＯＭ８１１、ＦＤＤ８１７、ＣＤＤ８１８、磁気ディスク装置８２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。通信ボード８１６、キーボード８１４、ＦＤＤ８１７などは、入力部、入力装置の一例である。また、通信ボード８１６、表示装置８１３、プリンタ装置８１９などは、出力部、出力装置の一例である。
【００２１】
通信ボード８１６は、ＬＡＮ等に接続されている。通信ボード８１６は、ＬＡＮに限らず、インターネット、ＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）などに接続されていても構わない。
【００２２】
磁気ディスク装置８２０には、オペレーティングシステム８２１（ＯＳ）、ウィンドウシステム８２２、プログラム群８２３、ファイル群８２４が記憶されている。プログラム群８２３のプログラムは、ＣＰＵ８１０、オペレーティングシステム８２１、ウィンドウシステム８２２により実行される。
【００２３】
上記プログラム群８２３には、以下に述べる実施の形態の説明において「〜部」、「〜手段」として説明する機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ８１０により読み出され実行される。
【００２４】
ファイル群８２４には、以下に述べる実施の形態の説明において、「〜の判定結果」、「〜の計算結果」、「〜の処理結果」として説明する情報や、データや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。また、差分生成装置の場合には、旧版データ、新版データ、類似ブロック情報、相違ブロック情報、変換後ブロック情報、あるいは変換ルールなどのデータ、情報が「〜ファイル」や「〜データベース」の各項目として記憶されている。また、差分適用装置の場合には、差分生成装置に対して新版データを除く、旧版データ、類似ブロック情報、相違ブロック情報、変換後ブロック情報、あるいは逆変換のルールなどのデータ、情報が「〜ファイル」や「〜データベース」の各項目として記憶されている。「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ８１０によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵの動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示・抽出のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【００２５】
また、以下に述べる実施の形態の説明においては、主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ８１２のメモリ、ＦＤＤ８１７のフレキシブルディスク、ＣＤＤ８１８のコンパクトディスク、磁気ディスク装置８２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｋ）等の記録媒体に記録される。また、データや信号は、バス８２５や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００２６】
また、以下に述べる実施の形態の説明において「〜部」、「〜手段」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「手段」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」、「〜手段」として説明するものは、ＲＯＭ８１１に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ８１０により読み出され、ＣＰＵ８１０により実行される。すなわち、プログラムは、以下に述べる「〜部」、「〜手段」としてコンピュータを機能させるものである。あるいは、以下に述べる「〜部」、「〜手段」の手順や方法をコンピュータに実行させるものである。
【００２７】
図４は、差分生成装置１００と差分適用装置２００との構成を示すブロック図である。差分生成装置１００は、類似ブロック抽出部１１０と、類似パターン変換部１２０と、差分情報生成部１３０とを備える。差分適用装置２００は、差分情報解析部２１０と、類似パターン逆変換部２２０と、差分情報適用部２３０とを備える。これら要素の動作は後述する。
【００２８】
図４に示すように、差分生成装置１００は、旧版データ１０１と新版データ１０２とから、最終的に差分情報１０９を生成する。また、差分適用装置２００は、差分情報１５１と旧版データ１５８とから、新版データ１６０を再生する。ここで、差分適用装置２００の差分情報１５１は、差分生成装置１００の生成した差分情報１０９と同一であることを前提としている。
【００２９】
図５は、差分生成装置１００の動作の概要を示すフローチャートである。差分生成装置１００では、Ｓ１００において、類似ブロック抽出部１１０が、予め定められた所定の規則に基づいて、新版データ全体を「類似ブロック」と「相違ブロック」とに分割する。「類似ブロック」、「相違ブロック」については後述する。Ｓ２００において、類似パターン変換部１２０が、「類似パターン」を変換して「変換後類似パターン」を生成する。「類似パターン」、「変換後類似パターン」については後述する。Ｓ３００において、差分情報生成部１３０が、差分情報を生成する。
【００３０】
図６は、類似ブロック抽出部１１０の動作を説明するフローチャートである。このフローチャートを用いて類似ブロック抽出部１１０の動作を説明する。
【００３１】
差分生成装置１００による差分抽出に当たっては、図４に示すように、類似ブロック抽出部１１０が旧版データ１０１と新版データ１０２とを比較する。類似ブロック抽出部１１０は、比較によって、新版データ１０２全体を旧版データに類似ブロックの存在する類似ブロックと、旧版に類似ブロックが存在しない相違ブロックに分割する（Ｓ１０１）。ここで「ブロック」とは、任意長の部分データ列を意味する。また、以下では類似ブロック、相違ブロックという場合は、新版データ側のブロックを意味する。
【００３２】
（類似ブロック抽出の具体的説明）
図７を用いて、類似ブロック抽出部１１０の動作を具体的に説明する。図７は、旧版データ３０１と新版データ３５１との具体例を示す図である。
【００３３】
類似ブロック抽出部１１０は、図７に示す旧版データ３０１と新版データ３５１とを比較し、新版データ３５１を類似ブロック３６２、３６４、３６６と、相違ブロック３６１、３６３、３６５とに分割する（Ｓ１０１）。例えば、類似ブロック３６２は旧版データ３０１のブロック３１１と比較すると１６バイトうち１３バイトが一致するので、類似ブロック抽出部１１０は、類似とみなしている。類似ブロックには類似ブロック３６６のように旧版データのブロック（類似ブロック３６６に対してはブロック３１４）と完全に一致する場合も含まれる。一方、相違ブロックは旧版に類似ブロックが見つからないブロックであり、言い換えると、相違ブロックとは、新版データ３５１の内、類似ブロックに含まれない部分である。
【００３４】
（類似ブロックの抽出方法）
類似ブロックを抽出する方法は様々考えられるが、本実施の形態１では類似ブロック抽出部１１０が、次に示すような手順で類似ブロックを抽出する。
【００３５】
類似ブロック抽出部１１０は、新版データの先頭から順に、旧版データから３バイト以上連続して一致する部分データ列を検索する。図７の例では、最初に見つかるのは新版データ３５１の９バイト目と旧版データ３０１の１バイト目にある“ＦＦ  ＥＥ  ＤＤ”である。類似ブロック抽出部１１０は、一致箇所を見つけると、次は、その一致箇所を後方に延長していって類似ブロックを決定する。途中で不一致箇所が見つかった場合、例えば、３バイト以上の不一致箇所が連続すると、その不一致箇所の直前までを類似ブロックとする。そして、２バイト以下であれば引き続き後方に類似ブロックを延長する。前記“ＦＦ  ＥＥ  ＤＤ”の例では、後方に延長していくと新版データ３５１の１７バイト目で新版“ＢＢ”と旧版“７７”のように不一致箇所が見つかる。この場合、類似ブロック抽出部１１０は、不一致箇所は連続して１バイトのみなので、後方に類似ブロックを延長していく。最終的には新版データ３５１の２５バイト目からの新版“１２  ３４  ５６”と旧版データ３０１の“０１  ２３  ４５”で３バイト連続する不一致箇所が見つかり、類似ブロックはその直前までとなり、すなわち類似ブロック抽出部１１０は、このブロックを類似ブロックと判定する。以降も同様の方法によって類似ブロック抽出部１１０は、類似ブロック３６４、３６６を抽出することができる。
【００３６】
（類似ブロック抽出の別の方法）
以上、類似ブロック抽出部１１０が新版データから類似ブロックを抽出する方法（Ｓ１０１）の例を示した。類似ブロック抽出部１１０による類似ブロックを抽出する方法は、上記の方法に限定されるものではない。上記の方法以外にも例えば、Ｗａｌｔｅｒ  Ｆ．Ｔｉｃｈｙの論文「Ｔｈｅ  Ｓｔｒｉｎｇ−ｔｏ−Ｓｔｒｉｎｇ  Ｃｏｒｒｅｃｔｉｏｎ  Ｐｒｏｂｌｅｍ  ｗｉｔｈ  Ｂｌｏｃｋ  Ｍｏｖｅｓ」に記載の方法を用いて、次のように抽出できる。すなわち、Ａｄｄ命令とＭｏｖｅ命令からなる差分情報を生成し、Ａｄｄ命令を挟んで隣接するＭｏｖｅ命令の内、同一オフセットからの移動であるＭｏｖｅ命令対象領域を統合して類似ブロックとみなす、と言った方法も考えられる。図３（従来の図）に示す差分情報２５１の場合、５つあるＭｏｖｅ命令は全て同一オフセットからの移動であり、５つのＭｏｖｅ命令の示す領域プラスそれらに挟まれるＡｄｄ命令の領域を統合して類似ブロックとみなす。
【００３７】
（ブロック情報の説明）
以上のようにして、類似ブロック抽出部１１０は、図４に示すように新版データ１０２を類似ブロックと相違ブロックとに分割する。類似ブロック抽出部１１０は、さらに、それぞれの類似ブロックからそれぞれの類似ブロック情報１０４を生成するとともに、それぞれの相違ブロックからそれぞれの相違ブロック情報１０５を生成する（Ｓ１０２）。これを説明する。
【００３８】
図４に示す類似ブロック情報１０４は、例えば、
（１）類似ブロックの新版データ１０２内での先頭アドレス、
（２）サイズ、
（３）旧版データ１０１内での先頭アドレス、
（４）ブロック内の差異箇所の情報（類似パターン）、
（５）差異箇所のデータ情報
を含む。
【００３９】
図４に示す相違ブロック情報１０５は、
（１）相違ブロックの新版データ１０２内での先頭アドレス
（２）サイズ、
（３）ブロック内のデータ情報
を含む。
【００４０】
（類似ブロック情報の具体例）
図８は、図７における「類似ブロック情報」と「相違ブロック情報」の具体例を示す図である。図８の（ａ）〜（ｃ）が類似ブロック情報であり、（ｄ）〜（ｆ）が相違ブロック情報である。類似ブロック情報３６２ａ、３６４ａ、３６６ａは、図７の類似ブロック３６２、３６４、３６６にそれぞれ対応し、相違ブロック情報３６１ａ、３６３ａ、３６５ａは図７の相違ブロック３６１，３６３，３６５にそれぞれ対応する。図８（ａ）の類似ブロック情報３６２ａを例にとり説明する。（ａ）おいて、“０ｘ８、１６、０ｘ１０”は、それぞれ新版データ内での開始アドレス、サイズ、旧版データ内での開始アドレスを示している。また、“００００００００１００１００１０”は、「類似パターン」を表しており、“０”が一致箇所、“１”が差異箇所を示している。“ＢＢ  ＡＡ  ００”は、差異箇所に相当する類似ブロック３６２内のデータ情報である。類似ブロック情報３６４ａも同様である。なお、類似ブロック情報３６６ａの場合、対応する類似ブロック３６６では差異箇所がないため、類似ブロック情報３６６ａ内に「類似パターン」と差異箇所相当のデータ情報は記載されていない。
【００４１】
（相違ブロック情報の具体例）
相違ブロック情報３６１ａを例にとり相違ブロック情報を説明する。相違ブロック情報３６１ａの“０ｘ０、８”は、それぞれ新版データ内の開始アドレス、サイズを示している。また、“ＦＦ  ・・・  ＦＦ”は、相違ブロック内の全データ情報を示している。相違ブロック情報３６３ａ、相違ブロック情報３６５ａも同様である。
【００４２】
（類似パターン変換部１２０の動作）
図９は類似パターン変換部１２０の動作を示すフローチャートである。このフローチャートを参照して類似パターン変換部１２０の動作を説明する。類似ブロック抽出部１１０による処理が完了すると、次は類似パターン変換部１２０が処理を行う。
（１）まず、類似パターン変換部１２０は、類似ブロック情報内に類似パターンが存在しない、つまり旧版と新版とで全く同一な類似ブロック情報に対しては、処理を行わない（Ｓ２０１のＮｏ）。その場合、処理を行なうことなく出力する。
（２）Ｓ２０１がＹｅｓの場合、つまり類似ブロック情報内に類似パターンが存在する場合、類似パターン変換部１２０は、それぞれの類似ブロック情報１０４に含まれる類似パターンの変換処理を行う（Ｓ２０２）。変換後の類似パターンを「変換後類似パターン」と呼ぶこととする。詳細は後述する。
（３）類似パターン変換部１２０は、類似パターンの変換処理によって生成した「変換後類似パターン」が、変換前の「類似パターン」を用いる場合よりも小さいデータサイズの差分情報（ブロック差分情報）を生成するかどうかを判断する（Ｓ２０３）。そして、小さくするほうのパターンを選択（決定）し「選択パターン」とする。類似パターン変換部１２０は「変換後類似パターン」を用いる方が、「類似パターン」を用いる場合よりも小さい差分情報（ブロック差分情報）を生成すると判断した場合（Ｓ２０３のＹｅｓ）、
「変換後類似パターン」を選択パターンとして選択し、類似ブロック情報１０４内の「類似パターン」を選択パターンである「変換後類似パターン」に置き換えた「変換後類似ブロック情報１０７」を生成し（Ｓ２０４）、この変換後類似ブロック情報１０７を差分情報生成部１３０に渡す（Ｓ２０５）。
（４）一方、類似パターン変換部１２０は、判断の結果、「変換後類似パターン」が「類似パターン」より小さいデータサイズの差分情報を生成できないと判断した場合（Ｓ２０３のＮｏ）には「類似パターン」を選択パターンとして選択して、「変換後類似ブロック情報１０７」を生成することなく、その「類似ブロック情報」を差分情報生成部１３０に出力する（Ｓ２０６）。
【００４３】
（類似パターンの変換の具体例）
以下、図１０〜図１４を用いて、類似パターン変換部１２０による処理の具体例を説明する。説明の前に、本実施の形態１では「類似パターン」として二値のデータ列（以下、二値データ列という）を前提とする。類似パターン変換部１２０は、二値データ列の類似パターンに対してブロックソート法の符号化手法を適用し、（１）「類似パターンと同じ長さの整列後二値データ列」と、（２）「インデックス値」とから構成される「変換後類似パターン」を生成する。
【００４４】
図１０は、図８（ａ）の「類似パターン３６２ａ−１」と、（ｂ）の「類似パターン３６４ａ−１」とを変換した「変換後類似パターン３６２ｂ−１」、「変換後類似パターン３６４ｂ−１」を示している。「類似パターン３６２ａ−１」は類似ブロック３６２の類似パターンであり、これにブロックソート法を適用すると、「二値データ列３６２ｂ−２」と「インデックス値３６２ｂ−３」とを得る。「二値データ列３６２ｂ−２」と「インデックス値３６２ｂ−３」とが、「変換後類似パターン３６２ｂ−１」を構成する。「変換後類似パターン３６４ｂ−１」についても同様である。
【００４５】
ここで「ブロックソート法」は公知の技術なので符号化手法についてはここでは説明しないが、ブロックソート法によって符号化されたデータ列では、一般的に同じ値のデータが近くに集まる傾向があることが知られている。前記のように、「二値データ列３６２ｂ−２」と「インデックス値３６２ｂ−３」とを併せたものが「変換後類似パターン３６２ｂ−１」となる。
【００４６】
同様にして、図１０に示すように、類似ブロック３６４の「類似パターン３６４ａ−１」に対しては、「ブロックソート法」による符号化という変換ルールを適用することにより、「二値データ列３６４ｂ−２」と「インデックス値３６４ｂ−３」とを得ることができる。「二値データ列３６４ｂ−２」と「インデックス値３６４ｂ−３」とが「変換後類似パターン３６４ｂ−１」を構成する。なお、ブロックソート法の復号化手法を用いると「変換後類似パターン」から一意に「類似パターン」を復元できることが知られている。
【００４７】
類似パターン変換部１２０は、引き続き類似パターンと変換後類似パターンとを比較して、どちらがより小さい差分情報（ブロック差分情報）を生成できるかを判定する。本実施の形態１では、以下に示す命令群によって差分情報が表現されることを前提として差分情報のサイズを判定する。差分情報を表現するための命令として、図２４の差分情報９５２で用いているようなＭｏｖｅ命令（オフセットまたはフラグを使用）とＡｄｄ命令に加え、Ｂｓｏｒｔ命令を使用するものとする。Ｂｓｏｒｔ命令は「変換後類似パターン」を差分情報として表現するために用いる命令である。パラメータとして類似ブロックに対応する旧版データ内ブロックとのオフセット（Ｍｏｖｅ命令のオフセットと同じ意味）と、類似ブロックのサイズと、類似パターンに適用したブロックソート符号化の結果として出力されるインデックス値を持つ。Ｂｓｏｒｔ命令の後には、ブロックソート符号化の結果として出力される二値データ列を類似パターンとみなしてＡｄｄ命令とフラグ付きＭｏｖｅ命令とを交互に出力する。一方、類似パターンに対する差分情報を表現する方法としては、オフセット付きＭｏｖｅ命令の後にフラグ付きＭｏｖｅ命令とＡｄｄ命令を類似パターンに従って交互に出力する方法を用いる。
【００４８】
図１１〜図１３を用いて図７、図８の例に対する類似パターン変換部１２０による類似パターンと変換後類似パターンとの比較処理を説明する。なお簡単のため、本実施の形態１での比較、判定には厳密な差分情報のサイズではなく、差分情報の命令数を基準に用いる。
【００４９】
（変換後類似パターンを選択する場合）
図１１の差分情報３６２Ａ、差分情報３６２Ｂは、図７の類似ブロック３６２をそれぞれ「類似パターン３６２ａ−１」、「変換後類似パターン３６２ｂ−１」を用いて表現した場合の、類似ブロック３６２に対応する差分情報（ブロック差分情報）である。図１０の二値データ列である「類似パターン３６２ａ−１」と、「二値データ列３６２ｂ−２」との比較から分かるように、ブロックソート符号化によって差異箇所が３箇所に分散していたものが２箇所に集まっている。それによってＡｄｄ命令とＭｏｖｅ命令の数がそれぞれ一つずつ減少している。命令数を削減できていることから、この場合、類似パターン変換部１２０は「変換後類似パターン３６２ｂ−１」（選択パターン）を採用（選択）すると判断し（Ｓ２０３のＹｅｓ）、図８（ａ）の類似ブロック情報３６２ａの「類似パターン３６２ａ−１」を「変換後類似パターン３６２ｂ−１」で置き換えた図１２の変換後類似ブロック情報３６２ｂを生成して（Ｓ２０４）、差分情報生成部１３０に渡す（Ｓ２０５）。
【００５０】
（変換後類似パターンを選択しない場合）
図１３の差分情報３６４Ａ、差分情報３６４Ｂは、類似ブロック３６４をそれぞれ図１０に示した「類似パターン３６４ａ−１」、「変換後類似パターン３６４ｂ−１」を用いて表現した場合の差分情報（類似ブロック３６４に対応するブロック差分情報）である。図１０の二値データ列である「類似パターン３６４ａ−１」、「二値データ列３６４ｂ−２」から分かるように、ブロックソート符号化によって差異箇所の分散数は変わっていない（４箇所に変化なし）ことから、差分情報３６４Ａと差分情報３６４Ｂとで命令数は同じである。差分情報３６４ＢではＢｓｏｒｔ命令を用いている。Ｂｓｏｒｔ命令はＭｏｖｅ命令と比較してパラメータを一つ多く持っていることから、変換後類似パターンを用いた差分情報３６４Ｂの方がデータサイズが大きいと考えられる。よって、この場合には類似パターン変換部１２０は、「変換後類似パターン３６４ｂ−１」を採用しないと判断して類似パターンを選択パターンとして選択し、変換後類似ブロック情報３６４ｂは生成しない。このように、変換後類似パターンを用いた差分情報の命令数が類似パターンを用いた差分情報の命令数と同じか、それ以上の場合は変換後類似ブロック情報は生成しない。
【００５１】
なお、本実施の形態１では差分情報を表す命令としてＭｏｖｅ命令とＡｄｄ命令、Ｂｓｏｒｔ命令を用いたが、他の形態であっても構わない。例えばＢｓｏｒｔ命令の後は必ずＡｄｄ命令とフラグ付きＭｏｖｅ命令であることが分かっているので、これらの命令を表すデータを省略した表現方法を用いることができる。
【００５２】
（差分情報の生成）
図１４は、差分情報生成部１３０の動作を示すフローチャートである。類似パターン変換部１２０の処理が完了すると、最後に差分情報生成部１３０が変換後類似ブロック情報１０７と、類似パターン変換部１２０によって変換されなかった類似ブロック情報１０４と、および相違ブロック情報１０５とを入力し（Ｓ３０１）、入力したこれらを用いて差分情報１０９を生成する（Ｓ３０２）。
【００５３】
（差分情報生成の具体例）
図１５を用いて差分情報生成部１３０が差分情報を生成する具体例を示す。差分情報生成部１３０が使用する情報は、
「変換後類似ブロック情報３６２ｂ」、
「類似ブロック情報３６４ａ」、
「類似ブロック情報３６６ａ」、
「相違ブロック情報３６１ａ、３６３ａ、３６５ａ」
である。以下、新版データ内でのアドレス順に差分情報４００を生成する。
【００５４】
最初に相違ブロック情報３６１ａからＡｄｄ命令を生成する。次に変換後類似ブロック情報３６２ｂから差分情報３６２Ｂで示した命令集合を追加する。その後、相違ブロック情報３６３ａ、類似ブロック情報３６４ａ、相違ブロック情報３６５ａ、類似ブロック情報３６６ａから逐次命令を出力し差分情報４００を得る。
【００５５】
以上が差分生成装置１００に対する本実施の形態の説明である。次に差分適用装置２００に対する本実施の形態を説明する。
【００５６】
（差分適用装置２００側）
図１６は差分適用装置２００の動作を示すフローチャートである。このフローチャートを参照して差分情報解析部２１０の動作を説明する。
【００５７】
（差分情報解析部２１０の動作）
差分適用に当たっては、まず差分情報解析部２１０が差分情報１５１から、変換後類似ブロック情報１５３と類似ブロック情報１５４、および相違ブロック情報１５５を抽出する（Ｓ１０００）。
【００５８】
（差分情報解析部２１０の動作の具体例）
図１５を参照して差分情報解析部２１０の動作を具体的に説明する。
（１）最初に差分情報４００の一つ目の命令であるＡｄｄ命令を読み込んで「相違ブロック情報３６１ａ」を生成する。
（２）次の命令はＢｓｏｒｔ命令であるので、それ以降が変換後類似ブロックであることが分かる。Ｂｓｏｒｔ命令には類似ブロックのサイズが含まれているので、類似ブロックの終端に到達するまでそれ以降の命令を順次読み込み、「変換後類似ブロック情報３６２ｂ」を生成する。ここでは６番目にあるＭｏｖｅ命令までが変換後類似ブロックに含まれる。
（３）次の命令はＡｄｄ命令であるので、「相違ブロック情報３６３ａ」を生成する。
（４）その次の命令はオフセット付きＭｏｖｅ命令なので、類似ブロックに相当することが分かる。ここでは類似ブロックのサイズは分からないので、以降の命令を次のオフセット付きＭｏｖｅ命令に到達するまで、もしくは差分情報の終端に到達するまで順次読み込む（フラグ付きＭｏｖｅ命令は類似ブロックに含まれる）。差分情報４００では、１８番目の命令が次のオフセット付きＭｏｖｅ命令になっているので、その２つ前の１６番目のフラグ付きＭｏｖｅ命令までが類似ブロックであることが分かり、８番目から１６番目までの命令文の情報から「類似ブロック情報３６４ａ」を生成する。
（５）その後、１７番目のＡｄｄ命令から「相違ブロック情報３６５ａ」を生成する。
（６）最後に１８番目のオフセット付きＭｏｖｅ命令から類似ブロックに相当すると判断し、差分情報の終端に到達しているので１８番目のオフセット付きＭｏｖｅ命令から「類似ブロック情報３６６ａ」を生成する。
【００５９】
（類似パターン逆変換部２２０の動作）
差分情報解析部２１０の処理が完了すると、次は類似パターン逆変換部２２０が処理を行う。類似パターン逆変換部２２０は、差分情報解析部２１０の生成した変換後類似ブロック情報１５３を入力とし、変換後類似ブロック情報１５３に含まれる変換後類似パターンを逆変換して類似パターンを得て、変換後類似パターンと置き換えて類似ブロック情報１５７を生成して差分情報適用部２３０に渡す（Ｓ２０００）。
【００６０】
（類似パターン逆変換部２２０の動作の具体例）
図１０〜図１３を用いて類似パターン逆変換部２２０の動作例を説明する。類似パターン逆変換部２２０は、変換後類似ブロック情報３６２ｂから「二値データ列３６２ｂ−２」と「インデックス値３６２ｂ−３」からなる「変換後類似パターン３６２ｂ−１」を読み込む。読み込んだ「変換後類似パターン３６２ｂ−１」に対してブロックソート法の復号化手法を適用し、二値データ列３６２ａ−１（類似パターン）を得る。この二値データ列３６２ａ−１を類似パターンとして類似ブロック情報３６２ａを生成し、差分情報適用部２３０に渡す。
【００６１】
（差分情報適用部２３０の動作）
最後に、差分情報適用部２３０が類似ブロック情報１５４、１５７、相違ブロック情報１５５と差分適用装置２００の保持する旧版データ１５８とから新版データ１６０を再生する（Ｓ３０００）。
【００６２】
（差分情報適用部２３０の動作の具体例）
図７、図８を用いて差分情報適用部２３０の動作の具体例を説明する。差分情報適用部２３０への入力は類似ブロック情報３６２ａ、３６４ａ、３６６ａ、相違ブロック情報３６１ａ、３６３ａ、３６５ａ、旧版データ３０１である。これらから新版データ３５１を再生する。
（１）最初に新版データ内でのアドレスが一番最初である相違ブロック情報３６１ａから新版データの相違ブロック３６１を再生する。
（２）次は類似ブロック情報３６２ａであり、旧版のアドレス０ｘ１０から１６バイトを新版データに追加した後、類似パターンと差異箇所データ情報とからブロック内の９バイト目、１２バイト目、１５バイト目をそれぞれ“０ｘＢＢ”“０ｘＡＡ”“０ｘ００”で置き換えて類似ブロック３６２を再生する。
（３）以下同様に、相違ブロック情報３６３ａから相違ブロック３６３を、類似ブロック情報３６４ａから類似ブロック３６４を、相違ブロック情報３６５ａから相違ブロック３６５を、類似ブロック情報３６６ａから類似ブロック３６６をそれぞれ再生し新版データ３５１を得る。
【００６３】
以上のように実施の形態１の差分抽出適用システム１０００は、各種データについて新旧バージョン間の差分を抽出する差分生成装置、及び旧版に差分を適用して新版を作り出す差分適用装置に係り、ブロックソート法を用いて差分情報を小さくすることを特徴とするものである。
【００６４】
本実施の形態１では、差分情報のデータサイズが小さくなる効果があるとともに、また対象となるデータの構造的知識によらないため汎用的であるという効果がある。
【００６５】
実施の形態１の差分生成装置１００は、類似パターン変換部１２０が、類似パターンを変換後類似パターンに変換して変換後ブロック情報を生成するので、データサイズのより小さい差分情報を生成することができる。
【００６６】
実施の形態１の差分生成装置１００は、類似パターン変換部１２０が類似パターンと変換後類似パターンとを比較して差分情報が小さくなる方を選択し、差分情報生成部１３０が類似パターン変換部１２０の選択に基づいた差分情報を生成するので、データサイズのより小さい差分情報を確実に生成することができる。即ち、従来技術では差分情報を小さいデータサイズで表現できないような場合にも差分情報のデータサイズを小さく表現でき、また、更新対象データの構造的知識を前提としてのみ差分情報を小さいサイズで表現できるような更新パターンについても更新対象データの構造的知識を前提とせずに差分情報のデータサイズを小さく表現することができる。
【００６７】
実施の形態１の差分適用装置２００は、類似パターン逆変換部２２０が変換後類似パターンを逆変換するので差分生成装置１００の生成した差分情報から新版データの生成が可能となる。これにより、より小さいデータサイズの差分情報から新版データを生成することができる。
【００６８】
実施の形態２．
実施の形態２では、差分生成装置１００の類似パターン変換部１２０、および差分適用装置２００の類似パターン逆変換部２２０が、複数種類（２種類）の変換ルール、逆変換ルールを持つ場合について説明する。
【００６９】
変換ルールの一つ目は実施の形態１で説明したブロックソート法の符号化とし、二つ目の変換ルールをブロックソート法で符号化された二値データ列をＭＴＦ（Ｍｏｖｅ−Ｔｏ−Ｆｒｏｎｔ）法で符号化する、というルールとする。
【００７０】
以下、図１７〜１９を用いてブロックソート法とＭＴＦ法を組み合わせた変換ルールの説明を行う。図１７の「二値データ列３６２ｂ−２」は、類似ブロック３６２に対する「類似パターン３６２ａ−１」をブロックソート法で符号化した結果の二値データ列である。これをＭＴＦ法を用いて変換すると「二値データ列３６２ｃ−１」が生成される。ここで、ＭＴＦ法における出現表の初期状態は［０、１］としている。このケースでは符号“１”の分散数が変化していないため、類似パターン変換部１２０は、ブロックソート法とＭＴＦ法の組合せには効果がないと判断する。
【００７１】
図１８の「二値データ列３６４ｂ−２」は、類似ブロック３６４に対する「類似パターン３６４ａ−１」をブロックソート法で符号化した結果の二値データ列である。これをＭＴＦ法を用いて変換すると「二値データ列３６４ｃ−１」が生成される。このケースでは符号“１”の分散数が減少しており、同様に元となる「類似パターン３６４ａ−１」における符号“１”の分散数からも減少している。よって類似パターン変換部１２０は、ブロックソート法とＭＴＦ法の組合せには効果があると判断し、図１９に示す「変換後類似ブロック情報３６４ｂ」を出力する。「変換後類似ブロック情報３６４ｂ」中にある“ＭＴＦ”が、ＭＴＦ法を用いたことを示している。
【００７２】
次に、図２０を用いてブロックソート法とＭＴＦ法との組合せによる変換後類似パターンから生成される差分情報の例を示す。図２０の差分情報５００は、この例を示している。差分情報生成部１３０は、ＭＴＦ法を用いたことを示すため「のＭｔｆ命令」を新たに追加し、パラメータはオフセットとブロックのサイズ、ブロックソート法で出力されるインデックス値とする。Ｍｔｆ命令の後はそれぞれ符号“１”の長さと符号“０”の長さを交互に出力する。ここで、最初に現れる符号が必ず“１”であることは自明である。ブロック文の長さの出力が完了すると、最後に類似ブロックでの相違箇所データ情報である“０ｘ００  ０ｘＡＡ  ０ｘ００  ０ｘ９９”を出力する。
【００７３】
（差分適用装置２００側）
以下、図７、図８、図１０、図１９、図２０等を用いて、ブロックソート法とＭＴＦ法の組合せによって生成された変換後類似ブロック情報から類似ブロック３６４を再生する手順を説明する。
【００７４】
差分適用装置２００の差分情報解析部２１０は、差分情報５００の一部から変換後類似ブロック情報３６４ｂを生成する。類似パターン逆変換部２２０は、変換後類似ブロック情報３６４ｂの“ＭＴＦ”という記述からブロックソート法とＭＴＦ法の組合せで生成された変換後類似パターンであることを判断し、ＭＴＦ法の復号化とブロックソート法の復号化を順次適用して「類似パターン３６４ａ−１」および「類似ブロック情報３６４ａ」を得る。以降の処理は実施の形態１と同一である。
【００７５】
本実施の形態２では、差分情報のデータサイズが小さくなる効果があるとともに、また対象となるデータの構造的知識によらないため汎用的であるという効果がある。また、実施の形態１と比較すると、より差分情報のデータサイズを小さく出来る可能性が高い。
【００７６】
実施の形態２の差分生成装置１００は、複数の変換ルールのうち差分情報のデータサイズが一番小さくなる変換ルールを採用するので、データの種類に対応して、よりデータサイズの小さい差分情報を生成することができる。
【００７７】
実施の形態２の差分適用装置２００は、類似パターン逆変換部２２０が変換後類似パターンを複数の変換ルールに応じて逆変換するので、差分生成装置１００の生成した差分情報から新版データの生成が可能となる。これにより、より小さいデータサイズの差分情報から新版データを生成することができる。
【００７８】
実施の形態３．
実施の形態３は、実施の形態１、実施の形態２で説明した差分生成装置１００、差分適用装置２００をコンピュータで実現するための差分生成プログラム、差分適用プログラムに関する。
【００７９】
前記の実施の形態１、実施の形態２においては、差分生成装置１００における「〜部」として示した各構成要素の動作は互いに関連しており、動作の関連を考慮しながら、コンピュータに実施させる一連の処理（プログラム）に置き換えることができる。各構成要素の動作を一連の処理に置き換えることにより、差分生成プログラムの実施形態とすることができる。また、この差分生成プログラムを、コンピュータ読み取り可能な記録媒体に記録させることで、プログラムを記録したコンピュータ読み取り可能な記録媒体の実施の形態とすることができる。
【００８０】
同様に、実施の形態１、実施の形態２においては、差分適用装置２００における「〜部」として示した各構成要素の動作は互いに関連しており、動作の関連を考慮しながら、コンピュータに実施させる一連の処理（プログラム）に置き換えることができる。各構成要素の動作を一連の処理に置き換えることにより、差分適用プログラムの実施形態とすることができる。また、この差分適用プログラムを、コンピュータ読み取り可能な記録媒体に記録させることで、プログラムを記録したコンピュータ読み取り可能な記録媒体の実施の形態とすることができる。
【００８１】
図２１は、差分生成プログラムの処理を示すフローチャートである。
（１）ステップＳ１１は、旧版データの一部分のデータ列に類似するとともに新版データの一部分をなすデータ列を前記新版データから類似ブロックとして抽出し、抽出した前記類似ブロックと前記旧版データの前記データ列との一致不一致を二値データ列で表現した類似パターンを含むとともに前記旧版データの前記データ列に対する前記類似ブロックの差分を示すブロック差分情報の生成に使用可能な類似ブロック情報を生成する処理である。
（２）Ｓ１２は、生成された前記類似ブロック情報に含まれる前記類似パターンを所定の変換ルールを用いて変換することにより変換後類似パターンを生成し、生成された前記変換後類似パターンを前記類似ブロック情報に含まれる前記類似パターンと置き換えることにより前記ブロック差分情報の生成に使用可能な変換後類似ブロック情報を生成する処理である。
（３）Ｓ１３は、生成された前記変換後類似ブロック情報を使用して、前記ブロック差分情報を生成する処理である。
【００８２】
図２２は、差分適用プログラムの処理を示すフローチャートである。
（１）Ｓ２１は、差分生成装置１００が生成した前記ブロック差分情報を入力し、入力した前記ブロック差分情報から前記変換後類似ブロック情報を生成する第１処理である。
（２）Ｓ２２は、前記第１処理により生成された前記変換後類似ブロック情報を入力し、入力した前記変換後類似ブロック情報に含まれる前記変換後類似パターンを類似パターン変換部１２０による変換の逆変換をすることにより前記変換後類似パターンから前記類似パターンを生成し、生成した前記類似パターンを前記変換後類似ブロック情報に含まれる前記変換後類似パターンと置き換えることにより前記類似ブロック情報を生成する第２処理である。
（３）Ｓ２３は、前記第２処理により生成された前記類似ブロック情報に基づいて旧版データを更新した新版データを生成する第３処理である。
【００８３】
以上、説明したように、この実施の形態１〜３では、ソフトウェアプログラムが差分情報のデータサイズを小さくするように処理し（差分生成側）、またソフトウェアプログラムが小さくされた差分情報をもとに新版データ再生処理をするので、差分生成装置、差分適用装置を実現する場合に、ハードウェアたる新たな専用装置等を創作しなくとも、汎用のコンピュータや既存のネットワーク・システムとそのソフトウェアとを用いて、差分生成装置、差分適用装置を実現する専用装置を創作したのと同様な結果が得られるのであるから、この実施の形態のソフトウェアの開発は、自然法則を利用した技術的創作である。すなわち、この実施の形態の差分生成装置、差分適用装置の実現は、経済法則ではないし、人為的取決めでもないし、人間の精神活動でもなく、自然法則を利用した技術的創作である。
【００８４】
前述した実施の形態１〜３の差分生成装置、差分適用装置は、ＣＰＵ及びＲＯＭ、ＲＡＭ、磁気ディスク装置などの記憶装置というハードウェアが用いられており、ソフトウェアによる情報処理がハードウェアを用いて具体的に実現されたものである。すなわち、前述した実施の形態の差分生成装置、差分適用装置は、自然法則を利用したハードウェアの動作により差分生成装置、差分適用装置の実現を図っているものであり、自然法則を利用した技術的創作に該当するものである。
【００８５】
前述した実施の形態１〜３は、単体のコンピュータプログラムを含んで実現できるものであるが、このコンピュータプログラムにより実現されるものは、コンピュータプログラムによって制御されるサーバコンピュータ、クライアントコンピュータ、端末コンピュータ、制御方法などである。このコンピュータプログラムは、ビジネス、経済分野などで使用されるためにプログラムされるものであるが、プログラムされたコンピュータシステムは、物理的な製品として具現化された装置の特徴を有しており、自然法則を利用した技術的創作に該当するものである。
【００８６】
以上の実施の形態では、旧版データと新版データを比較して差分情報を抽出する差分抽出装置と、差分情報を旧版データに適用して新版データを再生する差分適用装置とからなる差分抽出適用システムであって、
差分抽出装置は、少なくとも
（１）旧版データと新版データを比較して、新版データから旧版データとの間で内容が類似するブロックの情報と、旧版データとの間で内容が類似しないブロックの情報とを抽出する類似ブロック抽出部と、
（２）前記類似するブロックにおいて、新版データと旧版データの一致箇所と差異箇所を二値データ列で表現した類似パターン情報を、一定のルールに従って変換した変換後類似パターン情報を生成する類似パターン変換部と、
（３）変換後類似パターン情報と類似するブロックの情報と類似しないブロックの情報から、旧版データから新版データを生成するための情報である差分情報を生成する差分情報生成部とを有し、
差分適用装置は、少なくとも
（４）旧版データと差分情報から、変換後類似パターン情報と類似するブロックの部分情報と類似しないブロックの情報とを生成する差分情報解析部と、
（５）変換後類似パターン情報を逆変換して類似パターン情報を取得する類似パターン逆変換部と、
（６）類似パターン情報と類似するブロックの部分情報と類似しないブロックの情報とから新版データを再生する差分情報適用部とを有することを特徴とする差分抽出適用システムについて説明した。
【００８７】
以上の実施の形態では、差分抽出装置の類似パターン変換部が、変換に使用するルールを１種類以上持ち、各ルールによって生成される変換後類似パターン情報と類似パターン情報とを比較し、差分情報として表現する際に最も効果的である情報を差分情報生成部に渡し、差分抽出装置の差分情報生成部が、各類似するブロックの類似パターン情報に対してどの変換ルールを使用したか、もしくは変換ルールを使用しなかったかの情報を差分情報に付加し、差分適用装置の差分解析部が差分情報から変換後類似ブロック情報と、類似ブロック情報と、相違ブロック情報とを生成し、差分適用装置の類似パターン逆変換部が、
変換後類似パターンを逆変換して類似パターンを生成し、この類似パターンから類似ブロック情報を生成することを特徴とする差分抽出適用システムについて説明した。
【００８８】
以上の実施の形態では、差分抽出装置の類似パターン変換部の使用する変換ルールの内一つがブロックソート法の符号化に基づく変換ルールであり、差分適用装置の類似パターン逆変換部が使用する逆変換ルールの内一つが、ブロックソート法の復号化に基づく逆変換ルールであることを特徴とする差分抽出適用システムについて説明した。
【００８９】
以上の実施の形態では、差分抽出装置の類似パターン変換部の使用する変換ルールの内一つがブロックソート法の符号化とＭＴＦ法の符号化の組合せに基づく変換ルールであり、差分適用装置の類似パターン逆変換部が使用する逆変換ルールの内一つが、ＭＴＦ法の復号化とブロックソート法の復号化の組合せに基づく逆変換ルールであることを特徴とする差分抽出適用システムについて説明した。
【図面の簡単な説明】
【００９０】
【図１】実施の形態１における差分抽出適用システムのシステム構成を示す図。
【図２】実施の形態１におけるサーバ装置の外観の一例を示す図。
【図３】実施の形態１におけるサーバ装置のハードウェア構成を示す図。
【図４】実施の形態１における差分生成装置、差分適用装置のブロック図。
【図５】実施の形態１における差分生成装置の動作を示すフローチャート。
【図６】実施の形態１における類似ブロック抽出部の動作を示すフローチャート。
【図７】実施の形態１における類似ブロックの抽出を説明する図。
【図８】実施の形態１における類似ブロック情報、相違ブロック情報の例を示す図。
【図９】実施の形態１における類似パターン変換部の動作を示すフローチャート。
【図１０】実施の形態１における変換後類似パターンを説明する図。
【図１１】実施の形態１における類似パターン変換部の比較動作を説明する図。
【図１２】実施の形態１における変換後類似ブロック情報を説明する図。
【図１３】実施の形態１における差分情報（ブロック差分情報）を説明する図。
【図１４】実施の形態１における差分情報生成部の動作を示すフローチャート。
【図１５】実施の形態１における差分情報を説明する図。
【図１６】実施の形態１における差分適用装置の動作を示すフローチャート。
【図１７】実施の形態２における第２の変換ルールを説明する図。
【図１８】実施の形態２における第２の変換ルールを説明する図。
【図１９】実施の形態２における第２の変換ルールによる変換後ブロック情報を説明する図。
【図２０】実施の形態２における第２の変換ルールによる差分情報を説明する図。
【図２１】実施の形態３における差分生成プログラムの処理を示すフローチャート。
【図２２】実施の形態２における差分適用プログラムの処理を示すフローチャート。
【図２３】従来の例を示す図。
【図２４】従来の例を示す図。
【符号の説明】
【００９１】
１０００  差分抽出適用システム、１００  差分生成装置、１００ａ  サーバ装置、１１０  類似ブロック抽出部、１２０  類似パターン変換部、１３０  差分情報生成部、１０１  旧版データ、１０２  新版データ、１０４  類似ブロック情報、１０５  相違ブロック情報、１０７  変換後類似ブロック情報、１０９  差分情報、１５１  差分情報、１５３  変換後類似ブロック情報、１５４  類似ブロック情報、１５５  相違ブロック情報、１５７  類似ブロック情報、１５８  旧版データ、１６０  新版データ、２００  差分適用装置、２００ａ  携帯電話、２００ｂ  ユーザ端末装置、２１０  差分情報解析部、２２０  類似パターン逆変換部、２３０  差分情報適用部、３１１〜３１４  旧版データのブロック、３６１，３６３，３６５  相違ブロック、３６２，３６４，３６６  類似ブロック、３６１ａ，３６３ａ，３６５ａ  相違ブロック情報、３６２ａ，３６４ａ，３６６ａ  類似ブロック情報、３６２ａ−１  類似パターン、３６２ｂ  変換後類似ブロック情報、３６２ｂ−１  変換後類似パターン、３６２ｂ−２  二値データ列、３６２ｂ−３  インデックス値、３６２ｃ−２  二値データ列、３６４ａ−１  類似パターン、３６４ｂ  変換後類似ブロック情報、３６４ｂ−１  変換後類似パターン、３６４ｂ−２  二値データ列、３６４ｂ−３  インデックス値、３６４ｃ−２  二値データ列、３６２Ａ  差分情報、３６２Ｂ  差分情報、３６４Ａ  差分情報、３６４Ｂ  差分情報、４００  差分情報、５００  差分情報、８１０  ＣＰＵ、８１１  ＲＯＭ、８１２  ＲＡＭ、８１３  表示装置、８１４  キーボード、８１５  マウス、８１６  通信ボード、８１７  ＦＤＤ、８１８  ＣＤＤ、８１９  プリンタ装置、８２０  磁気ディスク装置、８２１  ＯＳ、８２２  ウィンドウシステム、８２３  プログラム群、８２４  ファイル群、８２５  バス、８３０  システムユニット、９０１  旧版データ、９０２  新版データ、９０３  ブロック、９５１，９５２  差分情報。
【図１】
0004791205.tif 000002
【図２】
0004791205.tif 000003
【図３】
0004791205.tif 000004
【図４】
0004791205.tif 000005
【図５】
0004791205.tif 000006
【図６】
0004791205.tif 000007
【図７】
0004791205.tif 000008
【図８】
0004791205.tif 000009
【図９】
0004791205.tif 000010
【図１０】
0004791205.tif 000011
【図１１】
0004791205.tif 000012
【図１２】
0004791205.tif 000013
【図１３】
0004791205.tif 000014
【図１４】
0004791205.tif 000015
【図１５】
0004791205.tif 000016
【図１６】
0004791205.tif 000017
【図１７】
0004791205.tif 000018
【図１８】
0004791205.tif 000019
【図１９】
0004791205.tif 000020
【図２０】
0004791205.tif 000021
【図２１】
0004791205.tif 000022
【図２２】
0004791205.tif 000023
【図２３】
0004791205.tif 000024
【図２４】
0004791205.tif 000025