JP4865449B2 - 差分生成装置及び差分適用装置及び差分生成プログラム及び差分適用プログラム及び差分生成適用システム及び差分生成適用方法 - Google Patents

Description

本発明は、差分生成装置及び差分適用装置及び差分生成プログラム及び差分適用プログラム及び差分生成適用システム及び差分生成適用方法に関するものである。本発明は、特に、ソフトウエアの差分生成装置及び差分適用装置からなる差分生成適用システムに関するものである。

ソフトウエアのバージョンアップや不具合の修正のために、ソフトウエアの新版と旧版の差分を抽出し、その差分を送ることにより、通信データ量を少なくしようとする手法がある。このような手法において、差分情報（「差分」、「差分データ」ともいう）を小さくするための各種手法が提案、開示されている（例えば、特許文献１〜３参照）。
特表２００５−５２５６４１号公報 特開２００４−１５２１３６号公報 特開２００６−４８６４０号公報

例えば、特許文献１では、バイナリファイルを比較して差分を小さく表現するための手法に関して開示されている。しかし、ファイルをそのまま比較しており、ファイルの特性によって方式を変更した方がよいようなケースに関してはなんら開示も示唆もされていない。

例えば、特許文献２では、差分表現方法の工夫のみで差分データを小さくする手法が示されている。しかし、対象データの特性に応じて処理をするような工夫はなんら開示も示唆もされていない。

このように差分を小さくする手法として様々なものが開示されているものの、これらの手法はあらゆる場合に有効なわけではない。そのため、データの特性に応じて各手法を使い分ける必要がある。しかしながら、ソフトウエアのデータは、プログラム部分とデータ部分が交互に配置されたり、異なるＣＰＵ（中央処理演算装置）で実行するためのコードがフラッシュＲＯＭ（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）やハードディスク上に一緒に置かれていたりする場合などもあり、特性の異なるデータが連続して配置されているケースが少なくない。そのため、従来のいずれかの手法をそのまま適用したり、様々な手法を適用してみて、差分が小さくなるものを採用したりしても、最小の差分情報が得られるとは言い難い。

特許文献３では、発明者によるソフトウエアの差分抽出及び差分適用の手法が開示されているが、差分の特性が異なる領域ごとにその差分の特性に応じた変換ルールを設定し、変換ルールに基づいて変換したデータに対して差分抽出及び差分適用を行うものではない。

本発明は、例えば、プログラムとデータが混じったようなバイナリデータの差分を示す差分情報のデータサイズを抑えることを目的とする。

本発明の一の態様に係る差分生成装置は、
処理装置を用いて、旧版データと新版データとを比較し、当該２つのデータ間の差分を抽出する比較部と、
前記処理装置を用いて、前記比較部により抽出された差分の特性を分析する分析部と、
前記処理装置を用いて、前記分析部により分析された差分の特性が異なる領域ごとに、前記２つのデータをそれぞれ分割するデータ分割部と、
前記データ分割部により分割された領域ごとに、前記分析部により分析された差分の特性に応じた変換ルールを記憶装置に設定し、当該変換ルールに基づいて、前記２つのデータをそれぞれ変換するデータ変換部と、
前記データ変換部により変換された２つのデータ同士を比較し、当該２つのデータ間の差分を示す差分情報を生成して出力装置から出力する差分生成部と、
前記データ変換部により設定された変換ルールを、前記差分生成部により生成された差分情報に対応付けて前記出力装置から出力する変換ルール出力部とを備えることを特徴とする。

本発明の一の態様によれば、データ分割部が、旧版データと新版データとの間の差分の特性が異なる領域ごとに当該２つのデータをそれぞれ分割し、データ変換部が、分割された領域ごとに差分の特性に応じた変換ルールを設定し、当該変換ルールに基づいて前記２つのデータをそれぞれ変換し、差分生成部が、変換された２つのデータ同士を比較し、当該２つのデータ間の差分を示す差分情報を生成して出力し、変換ルール出力部が、前記変換ルールを前記差分情報に対応付けて出力することにより、例えば、プログラムとデータが混じったようなバイナリデータの差分を示す差分情報のデータサイズを抑えることが可能となる。

以下、本発明の実施の形態について、図を用いて説明する。

下記の各実施の形態では、携帯電話、カーナビゲーションシステム、あるいは各種制御機器などの組み込みソフトウエア搭載の機器や、パーソナルコンピュータなど、ソフトウエアを搭載する機器全般に対して、ソフトウエアの不具合の修正や、ソフトウエアのバージョンアップに伴うソフトウエアの書き換えに関するものであって、実際に書き換えるソフトウエアに比べて少ない情報量を転送することにより、ソフトウエアの転送時間を短くし、通信コストの削減を狙ったソフトウエアの差分生成装置及び差分適用装置からなるソフトウエア差分適用生成システムについて説明する。

実施の形態１．
図１は、本実施の形態に係る差分生成適用システム１００の構成を示すブロック図である。

図１において、差分生成適用システム１００は、差分生成装置１０１と差分適用装置１０２からなる。

差分生成装置１０１は、一度、差分を抽出したあと、差分の発生部分がどこにあるかを分析し、その分散具合を分析し、分散傾向に合ったデータの変換処理を行うことにより、差分の発生部分を分散させずに集中させる。これにより、差分を小さく表現する。

差分は、例えば、旧版と同じ部分であって旧版から複製すればよい部分をＣＯＰＹ命令で表し、新たにデータを追加する部分をＤＡＴＡ（ＡＤＤ）命令で表す。つまり、差分データは、ＤＡＴＡとＣＯＰＹの命令の繰り返しで表される。本質的に変わったデータ（ＤＡＴＡ命令で表す部分）に関しては新たに送らなければならないが、旧版と同じデータや同じであっても位置がずれているデータ（ＣＯＰＹ命令で表す部分）は、命令だけを送ればよい。したがって、差分情報には、本質的に変わったデータ以外にも、命令ごとに数バイトのコマンドにあたるデータが入ることになる。即ち、このコマンドが少なければ少ないほど差分は小さく表現できることになる。差分を表す方法としては、ここで説明した方法以外にも、例えば、差分を、同一の領域、位置ずれを起こして移動した領域、新たにデータを追加する領域に分けて、それぞれＳＫＩＰ命令、ＣＯＰＹ命令、ＡＤＤ命令で表すものを用いることができる。

差分生成装置１０１は、比較部１１１、データ分割部１１２、データ変換部１１３、差分生成部１１４、変換ルール出力部１１５、分析部１１６からなる。差分生成装置１０１は、旧版データ１２１、新版データ１２２、分析結果１２３、変換後旧版データ１２４、変換後新版データ１２５、差分情報１２６を、それぞれ、例えばデータファイルとして記憶装置１２０に記憶する。差分生成装置１０１は、記憶装置１２０のほかに、処理装置、入力装置、出力装置などのハードウエア装置を備える（又はこれらのハードウエア装置が差分生成装置１０１に接続される）。ハードウエア装置は差分生成装置１０１の各部によって利用される。例えば、処理装置は、差分生成装置１０１の各部でデータや情報の演算、加工、読み取り、書き込みなどを行うために利用される。記憶装置１２０は、そのデータや情報を記憶するために利用される。また、入力装置は、そのデータや情報を入力するために、出力装置は、そのデータや情報を出力するために利用される。

比較部１１１は、処理装置を用いて、旧版データ１２１と新版データ１２２とを比較し、当該２つのデータ間の差分を抽出する。分析部１１６は、処理装置を用いて、比較部１１１により抽出された差分の特性を分析する。データ分割部１１２は、処理装置を用いて、分析部１１６により分析された差分の特性（分析結果１２３）が異なる領域ごとに、上記２つのデータをそれぞれ分割する。データ変換部１１３は、データ分割部１１２により分割された領域ごとに、分析部１１６により分析された差分の特性に応じた変換ルールを記憶装置１２０に設定し、当該変換ルールに基づいて、上記２つのデータをそれぞれ変換する。差分生成部１１４は、データ変換部１１３により変換された２つのデータ（変換後旧版データ１２４と変換後新版データ１２５）同士を比較し、当該２つのデータ間の差分を示す差分情報１２６を生成して出力装置から出力する。変換ルール出力部１１５は、データ変換部１１３により設定された変換ルールを、差分生成部１１４により生成された差分情報１２６に対応付けて（例えば、変換ルールを差分情報１２６に挿入する）出力装置から出力する。

本実施の形態では、分析部１１６は、比較部１１１により抽出された差分の特性として、当該差分が発生しているアドレスの傾向を分析する。

本実施の形態では、分析部１１６は、データ特性判定部１１７を含む。データ特性判定部１１７は、比較部１１１により抽出された差分が発生しているアドレスの傾向を、任意の大きさの領域ごとに、当該アドレスを所定の整数で割り算したときの余りが所定の値になる比率が高いかどうかで判定する。

本実施の形態では、分析部１１６は、さらに、データ分割点設定部１１８を含む。データ分割点設定部１１８は、データ特性判定部１１７により比率が高いと判定された領域と比率が高くないと判定された領域との境目を分割点として記憶装置１２０に設定する。データ分割部１１２は、データ分割点設定部１１８により設定された分割点で上記２つのデータ（旧版データ１２１と新版データ１２２）をそれぞれ分割する。

本実施の形態では、分析部１１６は、データ特性判定部１１７により比率が高いと判定される領域がより大きくなるように調整する。また、分析部１１６は、データ特性判定部１１７により比率が高くないと判定される領域がより小さくなるように調整する。そして、調整した領域同士の境目を分割点としてデータ分割点設定部１１８に設定させる。これにより、差分情報１２６を最適化することができる。

本実施の形態では、データ変換部１１３は、データ分割部１１２により分割された領域ごとに、比較部１１１により抽出された差分が発生しているアドレスを所定の整数で割り算したときの余りの順番で、上記２つのデータをそれぞれソートする。そのため、データ変換部１１３は、変換ルールとして、上記所定の整数の値を示すものを設定する。設定される変換ルールは、さらに、データ分割部１１２により分割された領域の大きさや位置などを示すものであってもよい。また、どのような順番でデータをソートするかを示すものであってもよい。

差分適用装置１０２は、変換部１４１、差分適用部１４２、逆変換部１４３からなる。差分適用装置１０２は、旧版データ１５１、変換後旧版データ１５２、変換後新版データ１５３、新版データ１５４を、それぞれ、例えば実行モジュールのファイルやバイナリイメージとして記憶装置１５０に記憶する。差分適用装置１０２は、記憶装置１５０のほかに、処理装置、入力装置、出力装置などのハードウエア装置を備える（又はこれらのハードウエア装置が差分適用装置１０２に接続される）。ハードウエア装置は差分適用装置１０２の各部によって利用される。例えば、処理装置は、差分適用装置１０２の各部でデータや情報の演算、加工、読み取り、書き込みなどを行うために利用される。記憶装置１５０は、そのデータや情報を記憶するために利用される。また、入力装置は、そのデータや情報を入力するために、出力装置は、そのデータや情報を出力するために利用される。

変換部１４１は、差分生成装置１０１の変換ルール出力部１１５により出力された変換ルールを入力装置から入力し、入力した変換ルールを記憶装置１５０に記憶する。そして、この変換ルールに基づいて、旧版データ１５１を変換する。差分適用部１４２は、差分生成装置１０１の差分生成部１１４により出力された差分情報１２６であって変換ルールと対応するもの（例えば、変換ルールが挿入されている差分情報１２６）を入力装置から入力し、入力した差分情報１２６を記憶装置１５０に記憶する。そして、この差分情報１２６に基づいて、変換部１４１により変換されたデータ（変換後旧版データ１５２）に当該差分（差分情報１２６に示された差分）を適用する。逆変換部１４３は、処理装置を用いて、上記変換ルールに基づき、差分適用部１４２により差分情報１２６が示す差分が適用されたデータ（変換後新版データ１５３）を逆変換し、新版データ１５４を再生する。

図２は、差分生成装置１０１及び差分適用装置１０２それぞれの外観の一例を示す図である。

図２において、差分生成装置１０１及び差分適用装置１０２は、システムユニット９１０、ＣＲＴ（Ｃａｔｈｏｄｅ・Ｒａｙ・Ｔｕｂｅ）やＬＣＤ（液晶ディスプレイ）の表示画面を有する表示装置９０１、キーボード９０２（Ｋ／Ｂ）、マウス９０３、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ・Ｄｉｓｋ・Ｄｒｉｖｅ）、ＣＤＤ９０５（Ｃｏｍｐａｃｔ・Ｄｉｓｃ・Ｄｒｉｖｅ）、プリンタ装置９０６などのハードウエア資源を備え、これらはケーブルや信号線で接続されている。システムユニット９１０は、コンピュータであり、ＬＡＮ９４２（ローカルエリアネットワーク）、ゲートウェイ９４１を介してインターネット９４０に接続されている。

図３は、差分生成装置１０１及び差分適用装置１０２それぞれのハードウエア資源の一例を示す図である。

図３において、差分生成装置１０１及び差分適用装置１０２は、プログラムを実行するＣＰＵ９１１（「演算装置」、「マイクロプロセッサ」、「マイクロコンピュータ」、「プロセッサ」ともいう）を備えている。ＣＰＵ９１１は、処理装置の一例である。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、ＦＤＤ９０４、ＣＤＤ９０５、プリンタ装置９０６、磁気ディスク装置９２０と接続され、これらのハードウエアデバイスを制御する。磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカードリーダライタなどの記憶媒体が用いられてもよい。

ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置１２０，１５０の一例である。通信ボード９１５、キーボード９０２、ＦＤＤ９０４などは、入力装置の一例である。また、通信ボード９１５、表示装置９０１、プリンタ装置９０６などは、出力装置の一例である。

通信ボード９１５は、ＬＡＮ９４２などに接続されている。通信ボード９１５は、ＬＡＮ９４２に限らず、インターネット９４０、あるいは、ＩＰ−ＶＰＮ（Ｉｎｔｅｒｎｅｔ・Ｐｒｏｔｏｃｏｌ・Ｖｉｒｔｕａｌ・Ｐｒｉｖａｔｅ・Ｎｅｔｗｏｒｋ）、広域ＬＡＮ、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ・Ｔｒａｎｓｆｅｒ・Ｍｏｄｅ）などのＷＡＮ（ワイドエリアネットワーク）などに接続されていても構わない。インターネット９４０あるいはＷＡＮなどに接続されている場合、ゲートウェイ９４１は不要となる。

磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。プログラム群９２３には、本実施の形態の説明において「〜部」、「〜手段」として説明する機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。また、ファイル群９２４には、本実施の形態の説明において、「〜データ」、「〜情報」、「〜ＩＤ（ＩＤｅｎｔｉｆｉｅｒ）」、「〜フラグ」、「〜結果」として説明するデータや情報や信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」や「〜テーブル」の各項目として記憶されている。「〜ファイル」や「〜データベース」や「〜テーブル」は、ディスクやメモリなどの記憶媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶されたデータや情報や信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・制御・出力・印刷・表示などのＣＰＵ９１１の処理（動作）に用いられる。抽出・検索・参照・比較・演算・計算・制御・出力・印刷・表示などのＣＰＵ９１１の処理中、データや情報や信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。

また、本実施の形態の説明において説明するブロック図やフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号は、ＲＡＭ９１４などのメモリ、ＦＤＤ９０４のフレキシブルディスク（ＦＤ）、ＣＤＤ９０５のコンパクトディスク（ＣＤ）、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク（ＭＤ）、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｃ）などの記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。

また、本実施の形態の説明において「〜部」、「〜手段」として説明するものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜工程」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」、「〜手段」として説明するものは、ＲＯＭ９１３に記憶されたファームウエアで実現されていても構わない。あるいは、ソフトウエアのみ、あるいは、素子・デバイス・基板・配線などのハードウエアのみ、あるいは、ソフトウエアとハードウエアとの組み合わせ、さらには、ファームウエアとの組み合わせで実現されていても構わない。ファームウエアとソフトウエアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤなどの記録媒体に記憶される。このプログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。即ち、プログラムは、本実施の形態の説明で述べる「〜部」、「〜手段」としてコンピュータを機能させるものである。あるいは、本実施の形態の説明で述べる「〜部」、「〜手段」の手順や方法をコンピュータに実行させるものである。

図４は、本実施の形態に係る差分生成方法（差分生成装置１０１の動作、差分生成装置１０１で実行される差分生成プログラムの処理手順に相当する）を示すフローチャートである。

図４において、ステップＳ２０１（比較処理）では、差分生成装置１０１の比較部１１１が、ＣＰＵ９１１（差分生成装置１０１の処理装置の一例）を用いて、旧版と新版のファイル情報（旧版データ１２１と新版データ１２２）を読み込み比較をする。この比較により、旧版データ１２１と新版データ１２２との差分を抽出する。この抽出処理は、従来からＵＮＩＸ（登録商標）オペレーティングシステムで用いられているｄｉｆｆのアルゴリズムなどを利用することにより実装できる。

ステップＳ２０２（分析処理）では、差分生成装置１０１の分析部１１６が、ＣＰＵ９１１を用いて、ステップＳ２０１の出力結果である差分を分析する。差分の分析の具体的な処理については、図８、図９を用いて後述する。ステップＳ２０３（データ分割処理）では、差分生成装置１０１のデータ分割部１１２が、ＣＰＵ９１１を用いて、ステップＳ２０２の分析結果１２３を利用してデータ（旧版データ１２１と新版データ１２２）を複数の部分に分割する。データの分割の具体的な処理に関しては、図６を用いて後述する。

ステップＳ２０４（データ変換処理）では、差分生成装置１０１のデータ変換部１１３が、ＣＰＵ９１１を用いて、ステップＳ２０３で分割された部分ごとにデータの変換処理を行って、変換後旧版データ１２４と変換後新版データ１２５を生成し、記憶装置１２０に記憶する。例えば、ＣＰＵのアーキテクチャなどに依存しないで差分の発生部分が分散しているようなデータなら、無変換（変換しないという処理）もデータ変換の一種と考える。また、例えば、データ変換には、アドレスを特定の基数で割った余りを利用する方式がある。これは、例えば、０、１、２、３、４、５、６、７、８、９、１０、１１、１２番地のデータは、４を基数にした場合は、０、４、８、１２、１、５、９、２、６、１０、３、７、１１という並びに変換されることを意味する（即ち、この例ではアドレスを基数で割った余りの順番にソートしている）。あるいは、差分のある部分に、一定の数字を足すと差分がなくなるというような変換もある。これは、リンク先アドレスが一定の割合でずれているような場合に、一定の数字を足せば良いような場合に有効な手段となる（即ち、この例ではアドレスに位置ずれを補正するための定数を加えている）。

ステップＳ２０４でデータ変換が行われた後、ステップＳ２０５（差分生成処理）では、差分生成装置１０１の差分生成部１１４が、ＣＰＵ９１１を用いて、変換単位ごとに差分抽出処理を行い、その結果を基に差分情報１２６を生成する。ステップＳ２０６（変換ルール出力処理）では、差分生成装置１０１の変換ルール出力部１１５が、ＣＰＵ９１１を用いて、ステップＳ２０５で生成された差分情報１２６に変換ルールの情報を加えて出力する。

図５は、本実施の形態に係る差分適用方法（差分適用装置１０２の動作、差分適用装置１０２で実行される差分適用プログラムの処理手順に相当する）を示すフローチャートである。

図５において、ステップＳ２１１（変換ルール抽出処理）では、差分適用装置１０２の変換部１４１が、ＣＰＵ９１１（差分適用装置１０２の処理装置の一例）を用いて、図４のステップＳ２０６で差分生成装置１０１により出力された差分情報１２６から、分割されたデータ単位ごとの変換ルールの情報を抽出する。そして、ステップＳ２１２（変換処理）では、ＣＰＵ９１１を用いて、元の旧版データ１５１に対し、ステップＳ２１１で抽出した変換ルールに基づいて、分割されたデータ単位ごとに変換処理を行う。

ステップＳ２１３（差分適用処理）では、差分適用装置１０２の差分適用部１４２が、ＣＰＵ９１１を用いて、ステップＳ２１２で変換されたデータ（変換後旧版データ１５２）に対し、差分情報１２６を用いて差分適用処理を行う。

ステップＳ２１４（逆変換処理）では、差分適用装置１０２の逆変換部１４３が、ＣＰＵ９１１を用いて、ステップＳ２１３で差分適用後のイメージ（変換後新版データ１５３）を逆変換処理することにより元に戻す。これによって新版データ１５４を得る。

次に、図６、図７を用いて、差分生成装置１０１の分析部１１６に含まれるデータ特性判定部１１７とデータ分割点設定部１１８の処理フローを示す。その後、実際のファイルを例にして、差分を抽出する処理に関して図８、図９を利用して説明する。

まず、図６において、ステップＳ３０１では、差分生成装置１０１のデータ特性判定部１１７が、ＣＰＵ９１１（差分生成装置１０１の処理装置の一例）を用いて、図４のステップＳ２０２で抽出された差分の現れているアドレスの一覧表を作成する。そして、ステップＳ３０２では、ＣＰＵ９１１を用いて、一定の基数、即ち、２、４、８、１６といった数値（１以上の整数であればよい）でそのアドレスを割り算し、その余りで、差分の現れたアドレスを分類する。例えば、３、３５、３８、３９、４０番地に差分が現れている場合は、それぞれのアドレスを２で割れば、余りが１のところに３つ（３、３５、３９番地）が分類され、余りが０のところには２つ（３８、４０番地）が分類される。４で割れば、余りが３のところに３つ（３、３５、３９番地）が分類され、余りが２のところに１つ（３８番地）が分類され、余りが０のところに１つ（４０番地）が分類される。８で割れば、余りが３のところに２つ（３、３５番地）が分類され、余りが７のところに１つ（３９番地）が分類され、余りが６のところに１つ（３８番地）が分類され、余りが０のところに１つ（４０番地）が分類される。

ステップＳ３０３では、データ特性判定部１１７が、ＣＰＵ９１１を用いて、上記のように分類した項目（上記の例では、余り）ごとの差分の分散状況を見る。上記の例において、データ特性判定部１１７は、０〜３６番地では、アドレスを８で割ったときの余りが３になる部分にのみ差分が現れていることを認識する。また、３７番地以降は、差分がランダムに現れていることを認識する。

ステップＳ３０４では、データ特性判定部１１７が、ＣＰＵ９１１を用いて、ステップＳ３０３で認識した差分の分散状況に基づいて、０〜３６番地の領域と３７番地以降の領域のそれぞれにおいて（任意の大きさの領域ごとに）、差分の分散の割合が一定の指標より上か下かで、各領域の差分の特性を判断する。例えば、上記指標を１００％とした場合、０〜３６番地の領域において、差分が発生しているアドレスを８で割り算したときの余りが３になる比率は１００％であるから、この領域は当該比率が高いものと判定される。同様に、３７番地以降の領域において、差分が発生しているアドレスを８で割り算したときの余りが３になる比率は０％であるから、この領域は当該比率が高くないものと判定される。データ特性判定部１１７は、このように差分が発生しているアドレスの傾向の分かれ目を３６番地と３７番地の間であると判断し、その結果を分析結果１２３として記憶装置１２０に記憶する。

このように、差分の発生しているアドレスを様々な数値で割り算して、そのときの余りと差分との相関を分析することにより、差分の偏り（集中）を発見することができる。これは、差分が少なくとも見かけ上は一定の法則に従って発生しているとみなせる場合に、その法則を発見することに相当する。上記の例では、０〜３６番地の領域において、差分が発生しているアドレスを８で割り算したときの余りが３になるという法則を発見している。この法則は、そのまま変換ルールの設定に用いることができるものである。

データ特性判定部１１７は、ステップＳ３０２で、差分が発生しているアドレスを８で割り算したときの余りによって差分の特性を分析する処理を省略してもよい。この場合、ステップＳ３０３では、０〜３９番地では、アドレスを４で割ったときの余りが３になる部分に多くの差分が現れていることがわかる。ステップＳ３０４では、例えば、上記指標を５０％とした場合、０〜３９番地の領域において、差分が発生しているアドレスを４で割り算したときの余りが３になる比率は７５％であるから、この領域は当該比率が高いものと判定される。同様に、４０番地以降の領域において、差分が発生しているアドレスを４で割り算したときの余りが３になる比率は０％であるから、この領域は当該比率が高くないものと判定される。データ特性判定部１１７は、このように差分が発生しているアドレスの傾向の分かれ目を３９番地と４０番地の間であると判断し、その結果を分析結果１２３として記憶装置１２０に記憶する。

差分情報１２６のデータサイズを抑えるためには、最適な変換ルールを設定する必要がある。そのためには、ステップＳ３０２〜Ｓ３０４を繰り返すことにより、より細かな単位でのデータの傾向を分析し、上記一定の法則を最適化することが有効である。例えば、上記のように、データ特性判定部１１７は、１回目のステップＳ３０２では、差分が発生しているアドレスを４で割り算したときの余りによって差分の特性を分析する処理のみを行い、２回目のステップＳ３０２では、差分が発生しているアドレスを８で割り算したときの余りによって差分の特性を分析する処理を行うことができる。このように、データ特性判定部１１７は、ステップＳ３０２〜Ｓ３０４を複数回繰り返すことで、各回の処理結果を比較して最適なものを選択することが可能となる。

次に、図７において、ステップＳ４０１では、差分生成装置１０１のデータ分割点設定部１１８が、ＣＰＵ９１１を用いて、図６のステップＳ３０４の分析結果１２３を参照して、差分が発生しているアドレスの傾向の分かれ目を分割点として設定し、記憶装置１２０に記憶する。そして、ステップＳ４０２では、ステップＳ４０１で設定した分割点で、データ分割部１１２にデータ（旧版データ１２１と新版データ１２２）を複数の部分（領域）に分割（分離）させる。

以下、実際のファイルを例にして、差分を抽出する処理に関して説明する。

図８は、本実施の形態における旧版データ５０１、新版データ５０２、変換後旧版データ５０３、変換後新版データ５０４の一例を示す図である。図９は、本実施の形態における差分情報６０２の一例を示す図である。

図８において、旧版データ５０１と新版データ５０２との差分としては、３番地（１行目の１列目が０番地、２列目が１番地、３列目が２番地、・・・、２行目の１列目が８番地、２列目が９番地、３列目が１０番地、・・・とする）が４から５になり、１１番地が５から６になり、１９番地が６から７になり、２７番地が７から８になっている。また、３２〜５５番地は全てデータ値（旧版、新版のデータは１つのアドレスに１つのデータ値をもつものとする）が変わり、５９番地は８から９になり、６７番地は９から０になっている。

このような差分は、マシン命令のアドレス部分やレジスタの指定部分が変わった場合、画像などのデータが変わった場合とが区別なく入っている場合などに起こるパターンである。

８を基数にしてアドレスを割ると、余りが０、１、２、４、５、６、７の部分ではそれぞれ３箇所、余りが３の部分では９箇所に差分が発生していることがわかる。つまり、余りが３の部分に差分が多数あるという特徴があることがわかる。

さらに、この余りの発生するアドレスを分析すると、余りが３のところ以外は全て、３２〜５５番地に入り、それ以外にはないことがわかる。そこで、データを３１番地と５５番地で３つの部分に分割して、さらに同じ傾向分析を行う。

０〜３１番地では、余りが３のところにのみ４つの差分があり、他の余りのところには差分はないことがわかる。３２〜５５番地では、全て均等に３つの差分があることがわかる。５６〜７１番地では、余りが３のところに２つの差分があり、他の余りのところには差分はないことがわかる。そこで、この分析を終了し、分割点を３１番地、５５番地とする。

次に、８を基数とする変換を０〜３１番地及び５５番地以降の部分にかけて、旧版データ５０１、新版データ５０２を、それぞれ変換後旧版データ５０３、変換後新版データ５０４に変換する。

変換後旧版データ５０３と変換後新版データ５０４との差分は、１２〜１５番地、３２〜５５番地、及び６２〜６３番地の３つにかたまっていることがわかる。

これを、前述したように、ＣＯＰＹ命令とＤＡＴＡ命令の列である差分情報６０２として表すことにより、差分を小さく表現できる。

図９において、差分情報６０２には、変換後のデータを元に戻すために、アドレスを８で割った余りの順にソートをしていることを示す変換ルールの情報を加えるだけで、ＣＯＰＹ命令とＤＡＴＡ命令の列の数が従来の差分情報６０１よりも格段に少なくなっていることがわかる。

ＣＯＰＹ命令は、どの番地から、何番地分のデータ値をコピーするかを示している。例えば、“ＣＯＰＹ ０， １２”は、旧版の０番地から１２個のデータ値を新版にコピーすることを示すものである。また、ＤＡＴＡ命令は、何番地分のデータ値を新たに追加するかを示している。例えば、“ＤＡＴＡ ４， ５６７８”は、新版の次の番地に４個のデータ値である“５６７８”を追加することを示すものである。さらに、Ｒｕｌｅは、差分適用時に利用するための変換ルールである。例えば、“Ｒｕｌｅ ８， ３２”は、旧版の次の番地から３２個のデータ値が、８を基数として変換されている（アドレスを８で割った余りの順にソートされている）ことを示すものである。例えば、“Ｒｕｌｅ ０， ２４”は、旧版の次の番地から２４個のデータ値は変換されていないことを示すものである。

この例では、従来の差分情報６０１はコマンド数が１５であるのに対して、本実施の形態における差分情報６０２はコマンド数が１０（従来の２／３）になっていることがわかる。このように、本実施の形態によれば、差分情報のデータを小さくすることができる。本実施の形態には、特に、プログラムとデータが混じったようなバイナリデータの差分に関しては、効率よく差分を抽出し、差分情報のデータを小さくするという効果がある。

図４を用いて説明した差分生成方法を、さらに具体的に、図８及び図９に示した例により説明する。

ステップＳ２０１では、差分生成装置１０１の比較部１１１が動作して、旧版データ５０１と新版データ５０２を比較する。この比較は、一致する部分が最も長くなるところをまず見つけることにより、全体としてコピーされている部分と新たに追加されたデータである部分を見つけていく手順で実行できる。一般にバイナリ差分技術といわれる公知の技術を使うことにより実現できる。

ステップＳ２０２では、差分生成装置１０１の分析部１１６が動作し、ステップＳ２０１で抽出した差分を分析する。分析の手順は、追加データとして発生する部分は旧版データ５０１のどの部分に発生したかを見ることに始まる。

基数の例として、２、４、８などを利用して、差分が発生したアドレスの割り算し、その特性を見つける。旧版データ５０１と新版データ５０２との間では、８で割り算したときの余りが３の部分の違いが、９箇所ある。残りの部分は均等に、３箇所ずつ違うことがわかる。よって、分析の結果、８を基数として計算した場合に余りが３の部分に偏って違いがあることがわかる。

さらに分析範囲を限定することにより、分析を進めると、３１番地までは余りが３のところに差分が集中し、５６番地以降も余りが３のところに差分が集中していることがわかる。また、３２〜５５番地は全てのデータが違うということがわかる。この分析は単純なケースでは、はっきりするが、単純でないケースも考えると、一定のパラメタ（指標）より集中度が大きいか小さいかという点がわかればよい。例えば、３１番地までで余りが３のところの違いは１００％、それ以外は０％である。４０番地まで考えると、余りが３のところは１００％、それ以外の部分は２０％となる。範囲をずらすことにより、この割合が変わる。この閾値（指標）を決めておけば、最適な分割点を見つけることができる。

ステップＳ２０３では、差分生成装置１０１のデータ変換部１１３が動作し、上記ステップＳ２０２の分析結果１２３に基づいて、分割点でデータを分割する。図８の例では、３つの部分（０〜３１番地、３２〜５５番地、５６番地以降の３つの領域）に分割する。

ステップＳ２０４では、ステップＳ２０３で分割されたデータの領域ごとに、差分生成装置１０１のデータ変換部１１３が動作してデータを変換する。０〜３１番地、５６番地以降の領域に関しては、アドレスを８で割ったときの余りが同じものが連続するように、変換処理を行う。これによって、違いのある部分が集中することになる。３２〜５５番地の領域は無変換とする。その結果、変換後旧版データ５０３と変換後新版データ５０４が生成される。

ステップＳ２０５では、差分生成装置１０１の差分生成部１１４が動作して、変換後旧版データ５０３と変換後新版データ５０４の差分を再度抽出する。

ステップＳ２０６では、差分生成装置１０１の変換ルール出力部１１５が動作して、ステップＳ２０５で抽出された差分と領域ごとの変換方法を指定する変換ルールとを含む差分情報６０２を出力する。

次に、図５を用いて説明した差分適用方法を、さらに具体的に、図８及び図９に示した例により説明する。

ステップＳ２１１、Ｓ２１２では、差分適用装置１０２の変換部１４１が動作して、差分情報６０２から変換ルールの部分を抜き出し、変換ルールに従って、旧版データ５０１の領域ごとに変換処理をかけて変換後旧版データ５０３を作る。

ステップＳ２１３では、差分適用装置１０２の差分適用部１４２が動作して、変換後旧版データ５０３に差分適用処理を行い、変換後新版データ５０４を作る。

ステップＳ２１４では、差分適用装置１０２の逆変換部１４３が動作して、変換後新版データ５０４の領域ごとに逆変換処理を行い、新版データ５０２を作成する。

上記のように、本実施の形態で説明した差分生成適用システムは、新版のデータと旧版のデータを比較し、その差分を抽出し、旧版に適用すれば新版を生成可能な差分データとして差分情報を出力できる差分生成システムにおいて、新版と旧版の比較部と、比較結果の分析部と、分析結果からデータを分割するデータ分割部と、データ変換を行うデータ変換部と、変換した結果に基づき差分を生成する差分生成部と、変換ルールの出力部とを備えた差分生成装置と、差分生成装置で出力された差分情報に基づいて、旧版のデータを変換ルールに基づき変換する変換部と、差分を適用する差分適用部と、元のデータに戻す逆変換部とを保持することを特徴とする差分適用装置とからなることを特徴とする。

上記比較結果の分析部は、データ特性判定部とデータ分割点設定部からなることを特徴とする。

上記データ特性判定部は、差分の発生するアドレスは、決まった整数で割り算した余りが同じであるアドレスに発生する確率が高いかどうかで判定することを特徴とする。

上記の発生する確率が高いかどうかの判定は、一定の領域の大きさごとに確率を計算することにより、その値が一定の値より高いかどうかで判定することを特徴とする。

上記の一定の領域は、この領域の大きさより小さな単位で開始アドレスをずらしたものを一定の領域とすることを特徴とする。

上記データ分割点設定部は、前記データ特性判定部において、決まった整数で割り算した余りが同じであるアドレスに発生する確率が高いと判定された部分とそうでない部分との境目を分割点とすることを特徴とする。

実施の形態２．
本実施の形態に係る差分生成適用システムは、実施の形態１で説明したものと同様である。

図１０は、本実施の形態における旧版データ５１１、新版データ５１２、変換後旧版データ５１３、変換後新版データ５１４の一例を示す図である。

図１０において、旧版データ５１１は、実施の形態１で図８に示した旧版データ５０１の７行目を省いたものである。新版データ５１２は、実施の形態１で図８に示した新版データ５０２と同じものである。

この例では、実施の形態１と同様に、８を基数とする変換を０〜３１番地及び４８番地以降の部分にかけて、旧版データ５１１を、変換後旧版データ５１３に変換する。新版データ５１２は、実施の形態１と同様に、変換後新版データ５１４に変換される。

図１１は、上記の例における差分情報６１２を示す図である。

実施の形態１と同様に、この例でも、従来の差分情報６１１はコマンド数が１５であるのに対して、本実施の形態における差分情報６０２はコマンド数が１０（従来の２／３）になっていることがわかる。

実施の形態３．
本実施の形態に係る差分生成適用システムは、実施の形態１で説明したものと同様である。

図１２は、本実施の形態における旧版データ５２１、新版データ５２２、変換後旧版データ５２３、変換後新版データ５２４の一例を示す図である。

図１２において、旧版データ５２１は、実施の形態１で図８に示した旧版データ５０１と同じものである。新版データ５２２は、実施の形態１で図８に示した新版データ５０２の７行目を省いたものである。

この例では、旧版データ５２１は、実施の形態１と同様に、変換後旧版データ５２３に変換される。そして、実施の形態１と同様に、８を基数とする変換を０〜３１番地及び４８番地以降の部分にかけて、新版データ５２２を、変換後新版データ５２４に変換する。

図１３は、上記の例における差分情報６２２を示す図である。

実施の形態１と同様に、この例でも、従来の差分情報６１１はコマンド数が１５であるのに対して、本実施の形態における差分情報６０２はコマンド数が１０（従来の２／３）になっていることがわかる。

実施の形態１に係る差分生成適用システムの構成を示すブロック図である。 実施の形態１における差分生成装置及び差分適用装置の外観の一例を示す図である。 実施の形態１における差分生成装置及び差分適用装置のハードウエア資源の一例を示す図である。 実施の形態１に係る差分生成方法を示すフローチャートである。 実施の形態１に係る差分適用方法を示すフローチャートである。 実施の形態１に係るデータ特性判定処理を示すフローチャートである。 実施の形態１に係るデータ分割点設定処理を示すフローチャートである。 実施の形態１における旧版データ及び新版データの一例を示す図である。 実施の形態１における差分情報の一例を示す図である。 実施の形態２における旧版データ及び新版データの一例を示す図である。 実施の形態２における差分情報の一例を示す図である。 実施の形態３における旧版データ及び新版データの一例を示す図である。 実施の形態３における差分情報の一例を示す図である。

符号の説明

１００ 差分生成適用システム、１０１ 差分生成装置、１０２ 差分適用装置、１１１ 比較部、１１２ データ分割部、１１３ データ変換部、１１４ 差分生成部、１１５ 変換ルール出力部、１１６ 分析部、１１７ データ特性判定部、１１８ データ分割点設定部、１２０，１５０ 記憶装置、１２１，１５１，５０１，５１１，５２１ 旧版データ、１２２，１５４，５０２，５１２，５２２ 新版データ、１２３ 分析結果、１２４，１５２，５０３，５１３，５２３ 変換後旧版データ、１２５，１５３，５０４，５１４，５２４ 変換後新版データ、１２６，６０１，６０２，６１１，６１２，６２１，６２２ 差分情報、１４１ 変換部、１４２ 差分適用部、１４３ 逆変換部、９０１ 表示装置、９０２ キーボード、９０３ マウス、９０４ ＦＤＤ、９０５ ＣＤＤ、９０６ プリンタ装置、９１０ システムユニット、９１１ ＣＰＵ、９１２ バス、９１３ ＲＯＭ、９１４ ＲＡＭ、９１５ 通信ボード、９２０ 磁気ディスク装置、９２１ オペレーティングシステム、９２２ ウィンドウシステム、９２３ プログラム群、９２４ ファイル群、９４０ インターネット、９４１ ゲートウェイ、９４２ ＬＡＮ。

Claims (11)

1. 処理装置を用いて、旧版データと新版データとを比較し、当該２つのデータ間の差分を抽出する比較部と、
   前記処理装置を用いて、前記比較部により抽出された差分の特性を分析する分析部と、
   前記処理装置を用いて、前記分析部により分析された差分の特性が異なる領域ごとに、前記２つのデータをそれぞれ分割するデータ分割部と、
   前記データ分割部により分割された領域ごとに、前記分析部により分析された差分の特性に応じた変換ルールを記憶装置に設定し、当該変換ルールに基づいて、前記２つのデータをそれぞれ変換するデータ変換部と、
   前記データ変換部により変換された２つのデータ同士を比較し、当該２つのデータ間の差分を示す差分情報を生成して出力装置から出力する差分生成部と、
   前記データ変換部により設定された変換ルールを、前記差分生成部により生成された差分情報に対応付けて前記出力装置から出力する変換ルール出力部とを備えることを特徴とする差分生成装置。
2. 前記分析部は、前記比較部により抽出された差分の特性として、当該差分が発生しているアドレスの傾向を分析することを特徴とする請求項１に記載の差分生成装置。
3. 前記分析部は、前記比較部により抽出された差分が発生しているアドレスの傾向を、任意の大きさの領域ごとに、当該アドレスを所定の整数で割り算したときの余りが所定の値になる比率が高いかどうかで判定するデータ特性判定部を含むことを特徴とする請求項２に記載の差分生成装置。
4. 前記分析部は、さらに、前記データ特性判定部により前記比率が高いと判定された領域と前記比率が高くないと判定された領域との境目を分割点として前記記憶装置に設定するデータ分割点設定部を含み、
   前記データ分割部は、前記データ分割点設定部により設定された分割点で前記２つのデータをそれぞれ分割することを特徴とする請求項３に記載の差分生成装置。
5. 前記分析部は、前記データ特性判定部により前記比率が高いと判定される領域がより大きくなるように調整するとともに、前記データ特性判定部により前記比率が高くないと判定される領域がより小さくなるように調整し、調整した領域同士の境目を前記分割点として前記データ分割点設定部に設定させることを特徴とする請求項４に記載の差分生成装置。
6. 前記データ変換部は、前記データ分割部により分割された領域ごとに、前記比較部により抽出された差分が発生しているアドレスを前記所定の整数で割り算したときの余りの順番で、前記２つのデータをそれぞれソートすることを特徴とする請求項３に記載の差分生成装置。
7. 旧版データと新版データとの間の差分が発生している領域であって当該差分の特性が異なる領域ごとに、当該差分の特性に応じた変換ルールを入力装置から入力し、入力した変換ルールに基づいて、前記旧版データを変換する変換部と、
   前記旧版データと前記新版データとの間の差分を示す差分情報であって前記変換ルールと対応する差分情報を前記入力装置から入力し、当該差分情報に基づいて、前記変換部により変換されたデータに当該差分を適用する差分適用部と、
   処理装置を用いて、前記変換ルールに基づいて、前記差分適用部により前記差分情報が示す差分が適用されたデータを逆変換し、前記新版データを再生する逆変換部とを備えることを特徴とする差分適用装置。
8. 差分生成装置が備える比較部が、旧版データと新版データとを比較し、当該２つのデータ間の差分を抽出する比較処理と、
   前記差分生成装置が備える分析部が、前記比較処理により抽出された差分の特性を分析する分析処理と、
   前記差分生成装置が備えるデータ分割部が、前記分析処理により分析された差分の特性が異なる領域ごとに、前記２つのデータをそれぞれ分割するデータ分割処理と、
   前記差分生成装置が備えるデータ変換部が、前記データ分割処理により分割された領域ごとに、前記分析処理により分析された差分の特性に応じた変換ルールを設定し、当該変換ルールに基づいて、前記２つのデータをそれぞれ変換するデータ変換処理と、
   前記差分生成装置が備える差分生成部が、前記データ変換処理により変換された２つのデータ同士を比較し、当該２つのデータ間の差分を示す差分情報を生成して出力する差分生成処理と、
   前記差分生成装置が備える変換ルール出力部が、前記データ変換処理により設定された変換ルールを、前記差分生成処理により生成された差分情報に対応付けて出力する変換ルール出力処理とをコンピュータに実行させることを特徴とする差分生成プログラム。
9. 差分適用装置が備える変換部が、旧版データと新版データとの間の差分が発生している領域であって当該差分の特性が異なる領域ごとに、当該差分の特性に応じた変換ルールに基づいて、前記旧版データを変換する変換処理と、
   前記差分適用装置が備える差分適用部が、前記旧版データと前記新版データとの間の差分を示す差分情報に基づいて、前記変換処理により変換されたデータに当該差分を適用する差分適用処理と、
   前記差分適用装置が備える逆変換部が、前記変換ルールに基づいて、前記差分適用処理により前記差分情報が示す差分が適用されたデータを逆変換し、前記新版データを再生する逆変換処理とをコンピュータに実行させることを特徴とする差分適用プログラム。
10. 処理装置を用いて、旧版データと新版データとを比較し、当該２つのデータ間の差分を抽出する比較部と、
    前記処理装置を用いて、前記比較部により抽出された差分の特性を分析する分析部と、
    前記処理装置を用いて、前記分析部により分析された差分の特性が異なる領域ごとに、前記２つのデータをそれぞれ分割するデータ分割部と、
    前記データ分割部により分割された領域ごとに、前記分析部により分析された差分の特性に応じた変換ルールを記憶装置に設定し、当該変換ルールに基づいて、前記２つのデータをそれぞれ変換するデータ変換部と、
    前記データ変換部により変換された２つのデータ同士を比較し、当該２つのデータ間の差分を示す差分情報を生成して出力装置から出力する差分生成部と、
    前記データ変換部により設定された変換ルールを、前記差分生成部により生成された差分情報に対応付けて前記出力装置から出力する変換ルール出力部とを備える差分生成装置と、
    前記変換ルール出力部により出力された変換ルールを入力装置から入力し、入力した変換ルールに基づいて、前記旧版データを変換する変換部と、
    前記差分生成部により出力された差分情報であって前記変換ルールと対応する差分情報を前記入力装置から入力し、当該差分情報に基づいて、前記変換部により変換されたデータに当該差分を適用する差分適用部と、
    処理装置を用いて、前記変換ルールに基づいて、前記差分適用部により前記差分情報が示す差分が適用されたデータを逆変換し、前記新版データを再生する逆変換部とを備える差分適用装置とを備えることを特徴とする差分生成適用システム。
11. 差分生成装置が備える比較部が、旧版データと新版データとを比較し、当該２つのデータ間の差分を抽出し、
    前記差分生成装置が備える分析部が、抽出された差分の特性を分析し、
    前記差分生成装置が備えるデータ分割部が、分析された差分の特性が異なる領域ごとに、前記２つのデータをそれぞれ分割し、
    前記差分生成装置が備えるデータ変換部が、分割された領域ごとに、分析された差分の特性に応じた変換ルールを設定し、当該変換ルールに基づいて、前記２つのデータをそれぞれ変換し、
    前記差分生成装置が備える差分生成部が、変換された２つのデータ同士を比較し、当該２つのデータ間の差分を示す差分情報を生成して出力し、
    前記差分生成装置が備える変換ルール出力部が、設定された変換ルールを、生成された差分情報に対応付けて出力し、
    差分適用装置が備える変換部が、出力された変換ルールに基づいて、前記旧版データを変換し、
    前記差分適用装置が備える差分適用部が、出力された差分情報であって前記変換ルールと対応する差分情報に基づいて、変換されたデータに当該差分を適用し、
    前記差分適用装置が備える逆変換部が、前記変換ルールに基づいて、前記差分情報が示す差分が適用されたデータを逆変換し、前記新版データを再生することを特徴とする差分生成適用方法。

Images