(57)【特許請求の範囲】
【請求項１】
規定単位で管理される可変長ビットデータの新旧データを入力として、これら新旧データそれぞれのデータを１ビットが１バイトの表現となるよう変換するビット・バイト変換部と、
前記ビット・バイト変換部で変換されたバイト単位の新旧データの差分データを生成する差分データ生成部と、
前記差分データ生成部で生成された差分データを、規定単位差分データとして出力する差分データ出力部とを備えた差分データ生成装置。
【請求項２】
規定単位は地図のメッシュ単位であることを特徴とする請求項１記載の差分データ生成装置。
【請求項３】
規定単位は地図上の行政区域単位であることを特徴とする請求項１記載の差分データ生成装置。
【請求項４】
前記新旧データの差分の有無を判定する差分有無判定部を備え、
前記ビット・バイト変換部と前記差分データ生成部は、前記差分有無判定部で差分が無いと判定された規定単位のデータ以外について処理を行うことを特徴とする請求項１から請求項３のうちのいずれか１項記載の差分データ生成装置。
【請求項５】
規定単位で管理される可変長ビットデータの新旧データにおける差分の有無を判定する差分有無判定部と、
前記差分有無判定部で差分があると判定された規定単位のデータを統合する規定単位データ統合部と、
前記規定単位データ統合部で統合されたデータについて、新旧データそれぞれのデータを１ビットが１バイトの表現となるよう変換するビット・バイト変換部と、
前記ビット・バイト変換部で変換されたバイト単位の新旧データの差分データを生成する差分データ生成部と、
前記差分データ生成部で生成された差分データを、複数の規定単位のデータを統合した統合規定単位差分データとして出力する統合規定単位データ管理部とを備えた差分データ生成装置。
【請求項６】
請求項１から請求項５のうちのいずれかに記載の差分データ生成装置で生成された規定単位で管理される差分データと、規定単位で管理される可変長ビットデータの旧データを入力として、前記規定単位で管理される可変長ビットデータの旧データを統合する規定単位データ統合部と、
前記規定単位で管理される差分データを前記規定単位データ統合部によって統合された旧データに適用して、統合された規定単位の新データを生成する差分データ適用部と、
前記差分データ適用部によって取得される統合された規定単位の新データを複数の規定単位のデータに分割する統合規定単位データ分割部と、
前記統合規定単位データ分割部によって生成されたデータによって、前記旧データ内で管理されている規定単位データを更新する更新データ出力部とを備えた情報処理装置。
【請求項７】
前記統合された旧データを１ビットが１バイトの表現となるよう変換し、かつ、前記統合された規定単位の新データを１バイトが１ビットの表現となるように変換するビット・バイト変換部を備え、
前記差分データ適用部は、前記ビット・バイト変換部で変換された統合された旧データに対して、１ビットが１バイトの表現となるよう変換した規定単位で管理される可変長ビットデータの新旧データに対して差分を抽出した差分データを適用し、１ビットが１バイトの表現となるよう変換した規定単位で管理される可変長ビットデータの統合された新データを生成することを特徴とする請求項６記載の情報処理装置。
【請求項８】
請求項１から請求項５のうちのいずれかに記載の差分データ生成装置で生成された規定単位で管理される差分データと、規定単位で管理される可変長ビットデータの旧データを入力として、前記規定単位で管理される可変長ビットデータの旧データを統合する規定単位データ統合部と、
前記規定単位で管理される差分データを前記規定単位データ統合部によって統合された旧データに適用して、統合された規定単位の新データを生成する差分データ適用部と、
前記差分データ適用部によって取得される統合された規定単位の新データを複数の規定単位のデータに分割する統合規定単位データ分割部と、
前記統合規定単位データ分割部によって生成されたデータによって、前記旧データ内で管理されている規定単位データを更新する更新データ出力部とを備え、
前記旧データおよび前記差分データを地図データとすることを特徴とする移動体ナビゲーション装置。
【請求項９】
前記統合された旧データを１ビットが１バイトの表現となるよう変換し、かつ、前記統合された規定単位の新データを１バイトが１ビットの表現となるように変換するビット・バイト変換部を備え、
前記差分データ適用部は、前記ビット・バイト変換部で変換された統合された旧データに対して、１ビットが１バイトの表現となるよう変換した規定単位で管理される可変長ビットデータの新旧データに対して差分を抽出した差分データを適用し、１ビットが１バイトの表現となるよう変換した規定単位で管理される可変長ビットデータの統合された新データを生成することを特徴とする請求項８記載の移動体ナビゲーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、主に、規定の単位で管理されたバイナリ形式のデータでビット単位のデータ伸張がある可変長ビットデータに対する、データ更新のための差分データ生成装置及びこれを用いた情報処理装置と移動体ナビゲーション装置に関するものである。
【背景技術】
【０００２】
データの更新のために、データの新版と旧版の差分を抽出し、その差分を配布することによって、通信データを少なくしようとする手法がある。このような手法において差分データを小さくするための方法があった（例えば、特許文献１〜３参照）。
例えば、特許文献１においては、データの比較を行う際に、１６進数で表現したデータに関して比較を行いバイトレベルでの差分抽出を実施する手法が示されている。また、特許文献２についても、バイトレベルの差分検出方法が取られており、特許文献３での差分抽出手法では、従来からのＵＮＩＸ（登録商標、以下記載を省略する）オペレーティングシステムで用いられているdiffのアルゴリズムを利用すると記載されているが、diffもバイトレベルの差分抽出手法である。
ソフトウェアで扱われるデータの多くは、バイト単位による演算、読み書きが一般的であり、処理速度の面からも従来の手法ではバイトレベルの差分抽出を適用しており、十分な効果が得られていた。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００４−２２７５２０号公報
【特許文献２】特開２００５−５２５６４１号公報
【特許文献３】特開２００８−４６９１４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、例えば地図データやプローブデータのように、なるべくデータサイズを小さくしたいデータ形式には、ビット単位のデータ伸張がある可変長ビットデータが存在する。この可変長ビットデータに対してバイトレベルでの比較を行っても、正しく一致箇所が判定できず、データサイズを抑えることができないという問題があった。
【０００５】
この発明は上記のような課題を解決するためになされたもので、差分データのデータサイズを抑えることのできる差分データ生成装置及びこれを用いた情報処理装置と移動体ナビゲーション装置を得ることを目的とする。
【課題を解決するための手段】
【０００６】
この発明に係る差分データ生成装置は、規定単位で管理される可変長ビットデータの新旧データを入力として、これら新旧データそれぞれのデータを１ビットが１バイトの表現となるよう変換するビット・バイト変換部と、ビット・バイト変換部で変換されたバイト単位の新旧データの差分データを生成する差分データ生成部と、差分データ生成部で生成された差分データを、規定単位差分データとして出力する差分データ出力部とを備えたものである。
【発明の効果】
【０００７】
この発明の差分データ生成装置は、新旧データそれぞれのデータを１ビットが１バイトの表現となるよう変換して、バイト単位の新旧データの差分データを生成するようにしたので、差分データのデータサイズを抑えることができる。
【図面の簡単な説明】
【０００８】
【図１】この発明の実施の形態１による差分データ生成装置を示す構成図である。
【図２】この発明の実施の形態１による差分データ生成装置の動作を示すフローチャートである。
【図３】この発明の実施の形態１による差分データ生成装置のビットレベルの伸張があったデータに対するバイトレベルの比較を示す説明図である。
【図４】この発明の実施の形態２による差分データ生成装置を示す構成図である。
【図５】この発明の実施の形態２による差分データ生成装置の動作を示すフローチャートである。
【図６】この発明の実施の形態３による差分データ生成装置を示す構成図である。
【図７】この発明の実施の形態３による差分データ生成装置の動作を示すフローチャートである。
【図８】この発明の実施の形態４による情報処理装置を示す構成図である。
【図９】この発明の実施の形態４による情報処理装置の動作を示すフローチャート（その１）である。
【図１０】この発明の実施の形態４による情報処理装置の動作を示すフローチャート（その２）である。
【図１１】この発明の実施の形態５による移動体ナビゲーション装置を示す構成図である。
【発明を実施するための形態】
【０００９】
実施の形態１．
図１は、この発明の実施の形態１による差分データ生成装置を示す構成図である。
図１に示す差分データ生成装置は、可変長バイナリ規定単位データ入力部１とバイナリ差分データ生成部２と差分データ出力部３が動作する演算処理手段４と、入力データ５となる新データ６と旧データ７、出力データとなる差分データ８を格納する記憶手段９を含み構成される。
【００１０】
可変長バイナリ規定単位データ入力部１は、入力データから規定単位でデータを取得する処理部であり、規定単位データ取得部１０とビット・バイト変換部１１を備えている。
また、バイナリ差分データ生成部２は、ビット・バイト変換部１１で変換されたバイト単位の新旧データの差分データを生成する処理部であり、データ圧縮部１２とバイト単位共通箇所判定部１３を備えている。
入力データ５は、規定単位で管理されたバイナリ形式のデータで、各データを識別するデータＩＤとバイナリ形式データが関連付けられて格納されている。バイナリ形式のデータは、ビット単位のデータ伸張がある可変長ビットデータとする。規定単位で管理されたバイナリ形式のデータとは、地図データやプローブデータであれば、メッシュと呼ばれる長方形単位や市町村、都道府県、州、国単位等が挙げられる。新データ６は、新版のデータであり、旧データ７は旧版のデータである。また、差分データ８はこれら新データ６と旧データ７との差分示す差分データである。
【００１１】
可変長バイナリ規定単位データ入力部１における規定単位データ取得部１０は、可変長バイナリ規定単位データ入力部１として、入力データ５を読み込み規定単位でデータを取得する処理部であり、ビット・バイト変換部１１は、規定単位の新旧データそれぞれのデータを１ビットが１バイトの表現となるよう変換する演算部である。また、バイナリ差分データ生成部２におけるデータ圧縮部１２は、一般的なデータ圧縮を行う処理部であり、バイト単位共通箇所判定部１３は、既知のアルゴリズムを用いて差分抽出を行う処理部である。
【００１２】
なお、演算処理手段４はコンピュータを用いて構成され、可変長バイナリ規定単位データ入力部１、バイナリ差分データ生成部２および差分データ出力部３は、それぞれの機能に対応したソフトウェアとこれを実行するためのＣＰＵやメモリといったハードウェアから実現されている。
【００１３】
次に、このように構成された差分データ生成装置の動作について説明する。
図２は、実施の形態１に係るバイナリ差分データ生成処理を示すフローチャートである。
先ず、可変長バイナリ規定単位データ入力部１の規定単位データ取得部１０は、記憶手段９より新データ６と旧データ７を取得し、それぞれのデータにおける全データのデータＩＤを取得する（ステップＳＴ１０１）。そして、ステップＳＴ１０２の処理として、新旧に存在する各データＩＤについてステップＳＴ１０３〜ステップＳＴ１１１の処理を実施する。
次に、規定単位データ取得部１０では、新旧データに同データＩＤが存在するかどうかを調査する（ステップＳＴ１０３）。存在する場合には、同データＩＤのバイナリデータを取得する（ステップＳＴ１０４）。これらのデータを新データ６Ａ、旧データ７Ａと呼ぶものとする。次に、ビット・バイト変換部１１を用いて１ビット→１バイト変換を行う（ステップＳＴ１０５）。
【００１４】
１ビット→１バイト変換とは、例えば００１０００１１のような１バイトのデータの場合では、００００００００  ００００００００  ０００００００１  ００００００００  ００００００００  ００００００００  ０００００００１  ０００００００１  のように１ビットを１バイトで表現して、８バイトのデータとする変換である。ここで、１ビット→１バイト変換後の新旧データを、新データ６Ｂ、旧データ７Ｂと呼ぶものとする。
【００１５】
次に、バイナリ差分データ生成部２を用いて、新データ６Ｂ、旧データ７Ｂを入力とし、差分データを生成する（ステップＳＴ１０６）。バイナリ差分データ生成部２には、バイト単位共通箇所判定部１３を備えた従来のツールのアルゴリズムを適用する。例えば、ＵＮＩＸオペレーティングシステムで用いられているdiffやxdelta、vcdiff、zdelta、bsdiff等が挙げられる。データ圧縮部１２においても、従来のbzip2やzlib、7zip等のアルゴリズムを適用する。
【００１６】
最後に、差分データ出力部３を用いて、同データＩＤ、生成された差分データ、更新フラグで１セットの規定単位データとして差分データ８に格納する（ステップＳＴ１０７）。
更新フラグとは、更新、削除、追加を示す符号である。例えば、１：追加、２：削除、３：更新のように割り当て、更新フラグとして数値を格納しても良い。ステップＳＴ１０７での更新フラグは、３：更新となる。
【００１７】
一方、ステップＳＴ１０３において、新旧に同データＩＤが存在せず、新データ６にしか存在しないデータＩＤだった場合には（ステップＳＴ１０８）、新データ６より該当規定単位データを取得し（ステップＳＴ１０９）、追加データとなる。追加データは、データＩＤ、規定単位データ、更新フラグで１セットのデータとして、差分データ出力部３を用いて差分データ８に格納する（ステップＳＴ１１０）。更新フラグには、追加を表す値を格納する。
【００１８】
また、ステップＳＴ１０３において、新旧に同データＩＤが存在せず、旧データ７にしか存在しないデータＩＤだった場合（ステップＳＴ１０８）には削除データとなる。削除データは、データＩＤ、更新フラグで１セットのデータとして、差分データ出力部３を用いて差分データ８に格納する（ステップＳＴ１１１）。更新フラグには、削除を表す値を格納する。削除データの場合は、データＩＤ、格納する規定単位データがないことを示すNULL文字等、更新フラグで１セットのデータとして格納してもよい。
【００１９】
差分データ８内には、旧データと差分データを用いてどのような操作を行えば、新データを作成できるのかという情報が格納されている。一般的に、操作は２種類あり、旧データからデータをコピーする処理と、差分データ内からデータをコピーする処理である。旧データからデータをコピーする処理を旧データコピー、差分データ８内からデータをコピーする処理を差分データコピーと呼ぶものとする。旧データCOPY命令の場合は、差分データ８内に、どこからコピーするという位置情報のみが格納されている。一方で、差分データCOPY命令の場合は、差分データ８内に、コピーするデータそのものが格納されているため、サイズが大きくなる。差分データサイズを小さくするためには、操作の回数が最小手順で、かつ旧データCOPY命令が多くなればよい。旧データCOPY命令は、バイト単位共通箇所判定部１３によって、旧データと新データの共通判定箇所が対象となる。
つまり、バイト単位共通箇所判定部１３によってより長い共通箇所が見つかることが、差分データサイズを小さくすることにつながる。
【００２０】
本発明によれば、入力対象としている可変長ビットデータに対して、従来から適用されているバイト単位共通箇所判定部１３を用いて共通箇所を見つける場合に、ビット単位の挿入や削除が発生してもビット・バイト変換部１１を備えられているため、共通箇所を発見することができる。図３はこれを示すもので、ビット・バイト変換部１１による変換が行われない場合（図の上側）、バイト単位では共通箇所が見つからないのに対し、ビット・バイト変換部１１による変換が行われた場合（図の下側）は、共通箇所を見つけることができる。
【００２１】
このような構成により、例えば、新旧データサイズが１９．４ＭＢの可変長ビットデータに対して、ビット・バイト変換部１１を用いずに差分データを作成した場合には、１１．３ＭＢとなる。一方で、本発明によるビット・バイト変換部１１を適用した場合には、５．５ＭＢと大幅に差分データサイズを削減することができる。
【００２２】
以上説明したように、実施の形態１の差分データ生成装置によれば、規定単位で管理される可変長ビットデータの新旧データを入力として、これら新旧データそれぞれのデータを１ビットが１バイトの表現となるよう変換するビット・バイト変換部と、ビット・バイト変換部で変換されたバイト単位の新旧データの差分データを生成する差分データ生成部と、差分データ生成部で生成された差分データを、規定単位差分データとして出力する差分データ出力部とを備えたので、差分データのデータサイズを抑えることができる。
【００２３】
また、実施の形態１の差分データ生成装置によれば、規定単位を地図のメッシュ単位としたので、地図のようにメッシュ単位で管理されたデータに対して、ビット単位の挿入や削除が発生しても、サイズを小さく抑えた差分データを生成することができる。
【００２４】
また、実施の形態１の差分データ生成装置によれば、規定単位を地図上の行政区域単位としたので、国、州、都道府県、市町村のような行政区域単位で管理されたデータに対して、ビット単位の挿入や削除が発生しても、サイズを小さく抑えた差分データを生成することができる。
【００２５】
実施の形態２．
図４は実施の形態２に係る差分データ生成装置の構成を示すブロック図である。実施の形態１との違いは、可変長バイナリ規定単位データ入力部１ａが差分有無判定部１４を備えた構造となっている点である。その他の構成は図１に示した実施の形態１と同様であるため、対応する部分に同一符号を付してその説明を省略する。
【００２６】
差分有無判定部１４は、規定単位データ取得部１０で取得された新旧データの差分の有無を判定するものであり、データサイズ比較部１５と誤り検出符号比較部１６を含み構成される。データサイズ比較部１５は、新旧データのデータサイズの比較を行う処理部であり、誤り検出符号比較部１６は、新旧データの誤り検出符号の比較を行う処理部である。
【００２７】
図５は、実施の形態２に係るバイナリ差分データ生成処理を示すフローチャートである。
実施の形態２では、ステップＳＴ１０４の規定単位データの取得後、ステップＳＴ１０５の１ビット→１バイト変換前に差分有無判定部１４を用いてステップＳＴ２０１とステップＳＴ２０２の差分有無判定を実施する。差分有無判定では、まずデータサイズ比較部１５を用いて、新データ６Ａと旧データ７Ａのデータサイズを比較する（ステップＳＴ２０１）。データサイズが異なる場合には新データ６Ａと旧データ７Ａに違いがあることが明白となるので、ステップＳＴ１０５の処理に移行する。一方で、データサイズが同じ場合は、ステップＳＴ２０２の誤り検出符合の検査に移行する。
【００２８】
ステップＳＴ２０２では、誤り検出符号比較部１６を用いて、従来の技術であるＭＤ５ハッシュチェックサム等を用いて、誤り検出符号を算出する。誤り検出符号が一致する場合には、新データ６Ａと旧データ７Ａには差分がないことがわかるので、次のデータＩＤの処理（ステップＳＴ１０２）に移行する。誤り検出符号が異なる場合には、差分があるということなので、ステップＳＴ１０５の処理に移行する。これ以降のステップＳＴ１０５〜ＳＴ１１１については実施の形態１と同様である。
【００２９】
バイナリ差分データ生成部２は、例え新データ６Ａと旧データ７Ａがまったく同じデータであったとしても、何らかのサイズをもった差分データを生成する。差分データ内には、旧データCOPY命令によって旧データの全情報をコピーするという命令が記載されるためである。
【００３０】
このように実施の形態２では、差分データを生成する前に差分の有無を判定し、更新のない規定単位データについては差分データが生成されないためデータサイズを小さくすることができる。また、更新のない規定単位データはステップＳＴ１０５〜ステップＳＴ１０７の時間を要する処理を省略することができるため、処理の高速化が可能となる。
【００３１】
以上説明したように、実施の形態２の差分データ生成装置によれば、新旧データの差分の有無を判定する差分有無判定部を備え、ビット・バイト変換部と差分データ生成部は、差分有無判定部で差分が無いと判定された規定単位のデータ以外について処理を行うようにしたので、差分のない規定単位データは差分データを生成しないことで、処理速度が向上し、かつサイズを小さく抑えた差分データを生成することができる。
【００３２】
実施の形態３．
図６は、実施の形態３に係る差分データ生成装置の構成を示すブロック図である。実施の形態２との違いは、可変長バイナリ規定単位データ入力部１ｂが規定単位データ統合部１７を備え、演算処理手段４において統合規定単位データ管理部１８が動作する構造となっている点である。その他の構成は、図４に示した実施の形態２の構成と同様であるため、対応する部分に同一符号を付してその説明を省略する。
【００３３】
図７は、実施の形態３に係る差分データ生成の処理を示すフローチャートである。
実施の形態３では、ステップＳＴ１０２に代わってステップＳＴ３００を行う。ステップＳＴ１０２では、データＩＤを処理する順を規定する必要はないが、ステップＳＴ３００では処理順序を規定する。ここでは、データＩＤを小さい順に処理するとしているが、大きい順でもよく、処理順序にルールがあればよいものとする。
【００３４】
実施の形態３では、ステップＳＴ２０２において、差分があると確定した規定単位データについて、規定単位データ統合部１７を用いてデータを統合する（ステップＳＴ３０１）。データの統合とは、新旧データ別々にデータを結合していく処理である。規定単位データ統合部１７には、新データ用統合バッファと旧データ用統合バッファが用意されており、ステップＳＴ３０１の処理を実行するデータＩＤの新データ６Ａと旧データ７Ａをそれぞれの統合バッファの一番後ろに結合していく。
【００３５】
ステップＳＴ３０２において、新データ用統合バッファと旧データ用統合バッファに格納された統合データのサイズが閾値を超えたら、ステップＳＴ１０５〜ＳＴ１０７、ＳＴ３０３の処理を行う。閾値となるデータサイズは大きければ大きいほどよい。しかし、本発明による差分データ生成装置または本発明による差分データ生成装置によって生成された差分データを適用してデータ更新を実施する装置に搭載されたメモリ量が小さい方の１／３程度にすることが望ましい。
【００３６】
ステップＳＴ１０５〜ＳＴ１０７については、新データ用統合バッファと旧データ用統合バッファのデータを入力として実施する。ステップＳＴ１０７においては、差分データ出力部３を用いて統合データＩＤ、生成された差分データ、更新フラグを登録する。統合データＩＤとは統合したデータＩＤの中で最小値や最大値のような代表値をつける。または、一意に識別するためのＩＤを割り当ててもよい。
【００３７】
ステップＳＴ３０３の統合データ格納では、統合規定単位データ管理部１８を用いる。
統合規定単位データ管理部１８は統合したデータＩＤと新データ６Ａのサイズを管理しており、ステップＳＴ１０７で割り当てた統合データＩＤ、データＩＤ、新データのサイズで１セットの統合規定単位差分データとして差分データ８に格納する。格納が完了したら、新データ用統合バッファと旧データ用統合バッファをクリアする。
【００３８】
入力データ５には１０Ｂ〜１００Ｂ程度の大変小さなサイズの規定単位データが多数含まれている場合がある。このような小さなサイズのデータに対してデータ圧縮部１２を備えたバイナリ差分データ生成部２を用いて個別に差分データを生成しても、圧縮の効果が少なくデータサイズを小さくすることができない。そこで、複数の差分のある規定単位データを結合してから適用することで、データサイズを小さくすることが可能である。
【００３９】
入力データ５が地図データであった場合には、メッシュと呼ばれる長方形矩形単位でデータは管理されるが、どのメッシュにも地物の種別のような属性情報が格納されており、より長い共通箇所が同メッシュ以外に見つかることがあるため、より差分データサイズが小さくなる。
例えば、新旧データサイズが１９．４ＭＢの可変長ビットデータである地図データに対して、ビット・バイト変換部１１や規定単位データ統合部１７を用いずに差分データを作成した場合には、１１．３ＭＢとなる。一方で、実施の形態１〜３によるビット・バイト変換部１１や規定単位データ統合部１７を適用した場合には、３ＭＢと大幅に差分データサイズを削減することができる。
【００４０】
以上説明したように、実施の形態３の差分データ生成装置によれば、規定単位で管理される可変長ビットデータの新旧データにおける差分の有無を判定する差分有無判定部と、差分有無判定部で差分があると判定された規定単位のデータを統合する規定単位データ統合部と、規定単位データ統合部で統合されたデータについて、新旧データそれぞれのデータを１ビットが１バイトの表現となるよう変換するビット・バイト変換部と、ビット・バイト変換部で変換されたバイト単位の新旧データの差分データを生成する差分データ生成部と、差分データ生成部で生成された差分データを、複数の規定単位のデータを統合した統合規定単位差分データとして出力する統合規定単位データ管理部とを備えたので、データサイズが小さい規定単位データについても、規定単位データには同様の情報が含まれている可能性があるため、規定単位データ以外の範囲により長い共通箇所が見つけられる可能性があり、その結果、更に圧縮による高い効果が得られるため、更にサイズを小さく抑えた差分データを生成することができる。
【００４１】
実施の形態４．
図８は実施の形態４に係る情報処理装置の構成を示すブロック図である。情報処理装置１９は、データを管理するデータベース（ＤＢ）２０と差分データ適用処理部２１と通信装置２２と更新データ出力部２８を含み構成される。
【００４２】
差分データ適用処理部２１は、ＤＢ２０に管理されているデータから規定単位でデータを取得する規定単位データ取得部１０、ビット・バイト変換部１１、規定単位データ統合部１７、差分データ８を旧データ７に適用して更新データ２９を生成する差分データ適用部２６、統合規定単位データを分割する統合規定単位データ分割部２７を含み構成される。なお、規定単位データ取得部１０、ビット・バイト変換部１１、規定単位データ統合部１７については、図６に示した実施の形態３の構成と同様であるため、対応する部分に同一符号を付してその説明を省略する。
【００４３】
差分データ適用装置１９は、通信装置２２を介して、差分データ配信サーバ２３と通信を行う。差分データ配信サーバ２３は、実施の形態３の差分データ生成装置によって生成された差分データ８を管理する差分データベース（差分ＤＢ）２４と通信装置２５を含み構成される。
差分データ配信サーバ２３は、情報処理装置１９の要求に従い、通信装置２５を介して差分ＤＢ２４にて管理している差分データ８を送信する。情報処理装置１９は、通信装置２２を介してＤＢ２０に差分データ８を取得する。旧データ７と差分データ８を入力とし差分データ適用処理部２１を用いて更新処理を実施し、更新データ出力部２８を用いて更新データ２９にデータを格納する。更新データ２９と新データ６は中身が同一のデータとなる。
【００４４】
図９及び図１０は差分データ適用処理部２１によるバイナリ差分更新の処理フローを示している。実施の形態３の差分データ生成装置によって生成された差分データ８には、データを管理するテーブルが２つ存在し、１つは統合データＩＤ、差分データ、更新フラグを１つのレコードとするテーブル（メイン差分テーブルと呼ぶものとする）、もう１つは統合データＩＤ、データＩＤ、新データのサイズを１つのレコードとするテーブル（統合規定単位差分テーブルと呼ぶものとする）である。
【００４５】
ステップＳＴ３０１では、ＤＢ２０に取得した差分データ８に格納されているメイン差分テーブルの全統合データＩＤを取得する。ステップＳＴ３０２では、ステップＳＴ３０１で取得した統合データＩＤについて１つずつステップＳＴ３０３〜ＳＴ３１３の処理を適用する。ステップＳＴ３０３では、当該統合データＩＤに関連付けられた更新フラグを確認する。更新フラグが更新を示す時はステップＳＴ３０４の当該統合データＩＤに関連付けられた差分データを取得する。これを差分統合データと呼ぶものとする。
【００４６】
次に、ステップＳＴ３０５では統合規定単位差分テーブルから当該統合データＩＤと一致する全レコード（レコードＡと呼ぶものとする）を取得し、レコードＡの全データＩＤに対して、バイナリ差分データ生成装置を用いて格納する時に用いた同規定の順序にステップＳＴ３０６とＳＴ３０７の処理を行う。まず、ステップＳＴ３０６とＳＴ３０７を実行する前に、空の旧データ用統合バッファを用意しておく。旧データ７から当該規定単位データを規定単位データ取得部１０により取得する（ステップＳＴ３０６）。これを旧データ７Ａとする。ステップＳＴ３０７では規定単位データ統合部１７を用いてデータを統合する。旧データ用統合バッファの一番後ろにステップＳＴ３０６で取得した旧データ７Ａを結合していく。この旧データ用統合バッファ内のデータを旧統合データと呼ぶものとする。
【００４７】
旧統合データに対して、ビット・バイト変換部１１を用いて１ビット→１バイト変換を行う（ステップＳＴ３０８）。ステップＳＴ３０９では、差分データ適用部２６を用いて旧統合データに対して、差分統合データを適用し、更新統合データを取得する。差分データ適用部２６には、差分データ８を生成する時に用いたバイナリ差分生成アルゴリズムに対応した差分データ適用アルゴリズムを採用する。
【００４８】
生成された更新統合データに対して、ビット・バイト変換部１１を用いて１バイト→１ビット変換を行う（ステップＳＴ３１０）。１バイト→１ビット変換とは、００００００００か０００００００１によって表現されている更新統合データに対して、００００００００→０、０００００００１→１の１ビットで表現する処理のことである。つまり、８バイトが１バイトとなり、例えば００００００００  ００００００００  ０００００００１  ００００００００  ００００００００  ００００００００  ０００００００１  ０００００００１であれば００１０００１１となる。更新統合データは必ず８ｎ（ｎは自然数）バイトとなるため、ビットの余りが出ることはない。
【００４９】
上記のステップＳＴ３０９の差分適用部２６を用いた差分適用処理では、１ビットが１バイトの表現となった新旧データから生成した差分データ８を用いて、１ビットが１バイトの表現となった旧データに対してバイトレベルの読み書きを行う従来の差分データ適用アルゴリズムを採用する方法について述べたが、１ビットが１バイトの表現となる変換を実施していない旧データに対して、ビットレベルの読み書きを行う差分適用処理を採用してもよい。その場合には、ステップＳＴ３０８とステップＳＴ３１０の処理は不要となり、より高速化が可能である。
【００５０】
ステップＳＴ３１１ではレコードＡの全データＩＤを規定の順序にステップＳＴ３１２、ＳＴ３１３の処理を実施する。統合データから当該データＩＤに関連付けられているデータサイズを取得し、更新統合データの前から取得したデータサイズ分切り取り、更新データとする。最後にステップＳＴ３１３にて当該データＩＤと生成された差分データを１セットのデータとして更新データ２９に更新データ出力部２８を用いて格納する。
【００５１】
一方、ステップＳＴ３０３において、更新フラグが追加を示す場合には（ステップＳＴ３１４）、当該統合データＩＤに関連付けられた規定単位データを取得する。取得したデータは、ステップＳＴ３１５にて当該統合データＩＤに関連づくデータＩＤと１セットのデータとして更新データ２９に更新データ出力部２８を用いて格納する。また、ステップＳＴ３０３において、更新フラグが追加ではない場合は（ステップＳＴ３１４）、削除を示す。この場合は、ステップＳＴ３１６において、当該統合データＩＤに関連づくデータＩＤのレコードを更新データ２９から更新データ出力部２８を用いて削除する。
【００５２】
以上説明したように、実施の形態４の情報処理装置によれば、実施の形態１から実施の形態３のうちのいずれかに記載の差分データ生成装置で生成された規定単位で管理される差分データと、規定単位で管理される可変長ビットデータの旧データを入力として、規定単位で管理される可変長ビットデータの旧データを統合する規定単位データ統合部と、規定単位で管理される差分データを規定単位データ統合部によって統合された旧データに適用して、統合された規定単位の新データを生成する差分データ適用部と、差分データ適用部によって取得される統合された規定単位の新データを複数の規定単位のデータに分割する統合規定単位データ分割部と、統合規定単位データ分割部によって生成されたデータによって、旧データ内で管理されている規定単位データを更新する更新データ出力部とを備えたので、情報処理装置として差分データのサイズを小さく抑えることができる。
【００５３】
また、実施の形態４の情報処理装置によれば、統合された旧データを１ビットが１バイトの表現となるよう変換し、かつ、統合された規定単位の新データを１バイトが１ビットの表現となるように変換するビット・バイト変換部を備え、差分データ適用部は、ビット・バイト変換部で変換された統合された旧データに対して、１ビットが１バイトの表現となるよう変換した規定単位で管理される可変長ビットデータの新旧データに対して差分を抽出した差分データを適用し、１ビットが１バイトの表現となるよう変換した規定単位で管理される可変長ビットデータの統合された新データを生成するようにしたので、さらに差分データのサイズを小さく抑えることができる。
【００５４】
実施の形態５．
実施の形態４の差分データ適用処理部２１は、地図情報を利用するナビゲーション装置に組み込んでもよく、これを実施の形態５として説明する。
図１１は、実施の形態５に係る移動体ナビゲーション装置の構成を示すブロック図である。実施の形態５の移動体ナビゲーション装置３０は、地図を表示する地図表示部３１、指定された目的地までの経路を計算し案内を行う経路案内処理部３２、ＧＰＳ受信機３３、ロケータやジャイロセンサ等の各種センサ３４、地図データを管理しておく地図データベース（地図ＤＢ）３５を伴い構成されている。これらは、通常のカーナビゲーションに代表される移動体ナビゲーション装置と同様のシステム構成であるため、各部の詳細については省略する。また、その他の構成については、図８に示した実施の形態４の構成と同様であるため、対応する部分に同一符号を付してその説明を省略する。
【００５５】
実施の形態５における旧データ７や差分データ８は地図データであり、移動体ナビゲーション装置３０内で、差分データ適用処理部２１を利用することによって、地図の差分更新が可能となる。
【００５６】
以上説明したように、実施の形態５の移動体ナビゲーション装置によれば、実施の形態１から実施の形態３のうちのいずれかに記載の差分データ生成装置で生成された規定単位で管理される差分データと、規定単位で管理される可変長ビットデータの旧データを入力として、規定単位で管理される可変長ビットデータの旧データを統合する規定単位データ統合部と、規定単位で管理される差分データを規定単位データ統合部によって統合された旧データに適用して、統合された規定単位の新データを生成する差分データ適用部と、差分データ適用部によって取得される統合された規定単位の新データを複数の規定単位のデータに分割する統合規定単位データ分割部と、統合規定単位データ分割部によって生成されたデータによって、旧データ内で管理されている規定単位データを更新する更新データ出力部とを備え、旧データおよび差分データを地図データとするようにしたので、移動体ナビゲーション装置として地図データのサイズを小さく抑えることができる。
【００５７】
また、実施の形態５の移動体ナビゲーション装置によれば、統合された旧データを１ビットが１バイトの表現となるよう変換し、かつ、統合された規定単位の新データを１バイトが１ビットの表現となるように変換するビット・バイト変換部を備え、差分データ適用部は、ビット・バイト変換部で変換された統合された旧データに対して、１ビットが１バイトの表現となるよう変換した規定単位で管理される可変長ビットデータの新旧データに対して差分を抽出した差分データを適用し、１ビットが１バイトの表現となるよう変換した規定単位で管理される可変長ビットデータの統合された新データを生成するようにしたので、さらに地図データのサイズを小さく抑えることができる。
【００５８】
また、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【符号の説明】
【００５９】
１，１ａ，１ｂ  可変長バイナリ規定単位データ入力部、２  バイナリ差分データ生成部、３  差分データ出力部、４  演算処理手段、５  入力データ、６  新データ、７  旧データ、８  差分データ、９  記憶手段、１０  規定単位データ取得部、１１  ビット・バイト変換部、１２  データ圧縮部、１３  バイト単位共通箇所判定部、１４  差分有無判定部、１５  データサイズ比較部、１６  誤り検出符号比較部、１７  規定単位データ統合部、１８  統合規定単位データ管理部、１９  情報処理装置、２０  ＤＢ、２１  差分データ適用処理部、２２  通信装置、２３  差分データ配信サーバ、２４  差分ＤＢ、２５  通信装置、２６  差分データ適用部、２７  統合規定単位データ分割部、２８  更新データ出力部、２９  更新データ、３０  移動体ナビゲーション装置、３１  地図表示部、３２  経路案内処理部、３３  ＧＰＳ受信機、３４  センサ、３５  地図ＤＢ。
【図１】
0006005079.tif 000002
【図２】
0006005079.tif 000003
【図３】
0006005079.tif 000004
【図４】
0006005079.tif 000005
【図５】
0006005079.tif 000006
【図６】
0006005079.tif 000007
【図７】
0006005079.tif 000008
【図８】
0006005079.tif 000009
【図９】
0006005079.tif 000010
【図１０】
0006005079.tif 000011
【図１１】
0006005079.tif 000012