説明

圧縮ナビゲーション地図データ

【課題】圧縮ナビゲーション地図データベース生成方法の提供。
【解決手段】非圧縮ナビゲーション地図データはナビゲーションデータの種々のビルディングブロックを含み、各ビルディングブロックはナビゲーションデータの特定の機能態様に対応し、各ブロックはデータ文字列を含む。この方法は、非圧縮ナビゲーション地図データのブロックごとに最も頻出するブロックのサブストリングを決定するステップと、ブロックごとに決定した最も頻出するブロックのサブストリングをシードブロックに保存するステップと、ブロックごとに文字列におけるシードブロックに保存されている決定された最も頻出するサブストリングと、シードブロックへの参照とを置換することによりブロックごとに圧縮ブロックを生成するステップと、圧縮ナビゲーション地図データベースを生成するためにブロックごとに圧縮ブロックおよびシードブロックを保存するステップと、を含む。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、非圧縮ナビゲーション地図データから圧縮ナビゲーション地図データを生成するための方法、圧縮ナビゲーション地図データを生成するように構成された圧縮モジュール、ユーザにナビゲーション情報を与えるための方法、およびユーザにナビゲーション情報を与えるナビゲーションシステムに関するものである。
【背景技術】
【0002】
2位置間の経路探索などの機能を実行するナビゲーションシステムが周知となっている。最新のナビゲーションシステムは、要求に応じて関心のある地点に関する情報を出力する旅行ガイド等として機能するものなどのような追加の機能なども備える場合がある。いくつかのナビゲーションシステムは、 テキストおよび/またはマルチメディア形式で詳細な説明を出力する旅行ガイド機能さえも含む場合がある。
【0003】
さらに、道路、建物などに加えて、車両周囲の三次元視野を三次元形態で表示することが一般的になってきた。三次元表示により、当然ながら、正しい進路の認識が容易になる。
【0004】
ユーザに与えられる様々な種類の情報は全て、CD ROMまたはDVDなどのリムーバブルデータ記憶装置に保存され、またはこの情報はハードディスクに提供される。
【0005】
この状況において、必要な情報をユーザに通知するのに用いられる、種々の情報を含むナビゲーション地図データに必要な記憶スペースの最小化に対する要求がある。
【発明の概要】
【発明が解決しようとする課題】
【0006】
従って、ナビゲーション地図データの保存に必要な記憶スペースを効率的に低減可能な方法の提供に対する要求がある。
【課題を解決するための手段】
【0007】
この要求は独立クレームの特徴によって満たされる。従属クレームでは、さらなる実施形態が記述される。
【0008】
本発明の第1の態様に従い、非圧縮ナビゲーション地図データから圧縮ナビゲーション地図データベースを生成するための方法を提供する。非圧縮ナビゲーションデータはナビゲーションデータの種々のビルディングブロックを含み、各ビルディングブロックはナビゲーションデータの特定の機能態様に対応し、各ビルディングブロックはバイト列またはデータ文字列を含む。非圧縮ナビゲーション地図データの種々のビルディングブロックにおいて、ビルディングブロックに含まれる最も頻出するサブストリングを決定する。さらに、ビルディングブロックにおいて、そのビルディングブロックにおける決定された最も頻出するサブストリングを少なくとも1つのシードブロックに保存する。さらに、ビルディングブロックにおいて、前記少なくとも1つのシードブロックに保存されている決定された最も頻出するサブストリングを、前記少なくとも1つのシードブロックへの参照と、文字列において置換することにより、圧縮ブロックを生成する。さらに、圧縮ナビゲーション地図データベースを生成するために、圧縮ブロックおよび前記少なくとも1つのシードブロックを保存する。
【0009】
全てのナビゲーションデータは、ナビゲーションデータの所定の機能態様を表現する各ビルディングブロックの1つに属するものと見なされる。例えば、機能ブロックは、経路ビルディングブロック、名称ビルディングブロックである。ナビゲーション地図データが種々の地理的地域にさらに分割され、データが種々の詳細レベルにさらに区分されてもよいことが理解されるべきである。しかしながら、本発明との関連では、機能ブロックへの分離が考察され、各機能ビルディングブロックは、ユーザに出力を提供する運転アドバイスなどの、ナビゲーションシステムにおいて用いられる種々の態様を表現する。例証として、経路ビルディングブロックは経路計算に関する機能を有し、名称ビルディングブロックは地図に示される街路名を含む。各ビルディングブロックにおいて、データは文字列で保存され、ブロックの内容に応じて、文字列は街路名であってもよく、画像に関する色情報を与えてもよい。ビルディングブロックにおいて、各ブロックに存在する最も頻出するサブストリングを決定することにより、前記少なくとも1つのシードブロックにおいて最も頻出するサブストリングを結合し、ビルディングブロックにおいて、最も頻出するサブストリングの代わりに、前記少なくとも1つのシードブロックへの参照を含むことが可能になる。このようにして、非圧縮ナビゲーション地図データよりも少ないストレージ容量を要する圧縮ブロックを得ることができる。前述の記載から、圧縮度が、圧縮ブロックにそれ以上含まれないが、シードブロックへの参照と置換される、シードブロックに保存されている最も頻出するサブストリングの数に応じて決まることが明らかである。
【0010】
一実施形態では、複数のビルディングブロックの最も頻出するサブストリングを1つのシードブロックに保存することが可能である。これは、1つのシードブロックに、2以上のビルディングブロックの最も頻出するサブストリングが含まれてもよいことを意味する。しかしながら、別の実施形態では、最も頻出するサブストリングを含むシードブロックを、ビルディングブロックごとに決定することも可能である。この実施形態では、ビルディングブロックごとにシードブロックおよび圧縮ブロックが存在するが、この実施形態では、ビルディングブロックごとに圧縮ブロックが存在しても、圧縮ブロックごとに1つのシードブロックが必ずしも存在しなくてもよい。
【0011】
さらに、各ビルディングブロックを圧縮前にいくつかの部分に分離し、ビルディングブロックの部分ごとに最も頻出するサブストリングを決定することも可能である。その後、ビルディングブロックの種々の部分の最も頻出するサブストリングを単一シードブロックに保存することができる。
【0012】
好ましくは、置換された参照は、オフセット情報および長さ情報を含み、このオフセット情報は、置換された最も頻出するサブストリングが位置する、シードブロック内の位置を示す。長さ情報は、置換された最も頻出するサブストリングの長さに関する情報を与える。オフセット情報および長さ情報を含む参照は、圧縮ナビゲーション地図データをナビゲーションシステムに再度用いられる時に必要となることがある。完全情報の生成において、参照は、シードブロックに保存されている最も頻出するサブストリングと再度置換される。この置換では、この情報は、対応する置換された最も頻出するサブストリングがシードブロックのどこに保存されたかに用いられる。さらに、この情報は、置換された最も頻出するサブストリングがどれぐらいの長さかにも用いられる。
【0013】
ブロックの最も頻出するサブストリングの決定するための1つの可能性は、ブロックに含まれる文字列のプレフィックスツリーを生成し、そのプレフィックスツリーにおける最も頻出するサブストリングを決定することである。プレフィックスツリーでは、ツリー内の文字列の位置に応じて、それに関連する文字列が規定される。ノードの全てのディセンデントは、そのノードに関連する文字列の共通プレフィックスを有する。各ノードに頻出度値が関連する場合には、ブロックの最も頻出するサブストリングを容易に決定できる。
【0014】
非圧縮ナビゲーション地図データは、種々のブロック、経路ビルディングブロック、名称ビルディングブロック、交通情報ビルディングブロック、三次元物体ビルディングブロック、接合画像ビルディングブロック、またはデジタル地形ビルディングブロックを含むことができる。
【0015】
本発明は、圧縮ナビゲーション地図データを生成するように構成された圧縮モジュールにもさらに関する。このモジュールは、非圧縮ナビゲーション地図データを含む第1のデータベースを備え、非圧縮ナビゲーション地図データはナビゲーションデータの種々のビルディングブロックを含み、各ビルディングブロックはナビゲーション地図データの特定の機能態様に対応し、各ブロックはデータ文字列を含む。さらに、前述するように、圧縮ブロックおよび前記少なくとも1つのシードブロックを決定するように構成された圧縮モジュールおよび処理装置内に、第2のデータベースが提供される。
【0016】
本発明は、ユーザにナビゲーション情報を与えるナビゲーションシステムにもさらに関する。ナビゲーションシステムは圧縮ナビゲーション地図データを含む記憶装置を備え、圧縮ナビゲーション地図データはナビゲーション地図データの種々のビルディングブロックを含み、各ビルディングブロックはナビゲーション地図データの特定の機能態様に対応する。圧縮ナビゲーションデータは少なくとも1つのシードブロックおよび圧縮ブロックを含み、前記少なくとも1つのシードブロックは圧縮ブロックの最も頻出するサブストリングを含む。圧縮ブロックにおいて、前記少なくとも1つのシードブロックに保存されている決定された最も頻出するサブストリングと、前記少なくとも1つのシードブロックへの参照とを置換する。さらに、ナビゲーションシステムは、ユーザにナビゲーション情報を与える情報ユニットを備えている。例証として、ナビゲーション情報は、二次元または三次元の視覚出力でもよい。ナビゲーションシステムは、圧縮ナビゲーション地図データから非圧縮ナビゲーション地図データを生成するように構成された復元ユニットをさらに備えている。復元ユニットは、ビルディングブロックごとに、圧縮ブロックおよび前記少なくとも1つのシードブロックにアクセスし、非圧縮ナビゲーション地図データを生成するために、圧縮ブロックに含まれる参照と前記少なくとも1つのシードブロックの対応する最も頻出するサブストリングとを置換する。復元ユニットは、非圧縮ナビゲーション地図データに基づいてナビゲーション情報を生成するようにさらに構成され、情報ユニットは非圧縮ナビゲーション地図データを用いて、ユーザにナビゲーション情報を与える。
【0017】
一実施形態では、復元において、圧縮および復元に関する仮想プレフィックスとしてシードブロックを用いることにより、圧縮および復元アルゴリズム簡素化する。通常では、各ブロックのシードブロック無しでは復元はできない。これはさらに、シードブロックが圧縮ブロックとは別に保存されている場合、圧縮ブロックにシードブロックが提供されないときはナビゲーション地図データを使用できないので、ナビゲーション地図データの低負荷の暗号化を提供する。本発明は、ユーザにナビゲーション情報を与える方法をさらに提供する。圧縮ナビゲーションデータから非圧縮ナビゲーション地図データを生成し、ブロックごとに、圧縮ブロックおよび前記少なくとも1つのシードブロックにアクセスし、圧縮ブロックに含まれる参照と前記少なくとも1つのシードブロックに保存されている対応する最も頻出するサブストリングとを置換することにより、非圧縮ナビゲーションデータを生成する。その後、非圧縮ナビゲーション地図データに基づいてユーザに関するナビゲーション情報を生成し、非圧縮ナビゲーション地図データに基づいてユーザにナビゲーション情報を与える。
【0018】
例えば、本願発明は以下の項目を提供する。
(項目1)
非圧縮ナビゲーション地図データから圧縮ナビゲーション地図データベースを生成するための方法であって、
上記非圧縮ナビゲーション地図データはナビゲーションデータの種々のビルディングブロック(111)を含み、各ビルディングブロックは上記ナビゲーションデータの特定の機能態様に対応し、各ブロックはデータ文字列を含み、上記方法は、
上記非圧縮ナビゲーション地図データの上記ビルディングブロックに対して、上記ビルディングブロックに含まれる最も頻出するサブストリングを決定するステップと、
上記ビルディングブロックに対して、上記決定された最も頻出するサブストリングを少なくとも1つのシードブロック(121)に保存するステップと、
上記ビルディングブロックにおいて、上記文字列における、上記少なくとも1つのシードブロック(121)に保存されている上記決定された最も頻出するサブストリングと、上記少なくとも1つのシードブロックへの参照とを置換することにより、ビルディングブロックごとに圧縮ブロック(122)を生成するステップと、
上記圧縮ナビゲーション地図データベースを生成するために、上記圧縮ブロック(122)および上記少なくとも1つのシードブロック(121)を保存するステップと、を含む、方法。
(項目2)
上記置換された参照はオフセット情報および長さ情報を含み、上記オフセット情報は、上記置換された最も頻出するサブストリングが位置する、上記シードブロック内の位置を示し、上記長さ情報は上記置換された最も頻出するサブストリングの長さを示す、上記項目に記載の方法。
(項目3)
上記ブロックのプレフィックスツリーを決定し、上記プレフィックスツリーにおける最も頻出するサブストリングを決定することにより、上記ブロックの最も頻出するサブストリングを生成する、上記項目のいずれか1つに記載の方法。
(項目4)
上記非圧縮ナビゲーション地図データは、経路指定ビルディングブロック、名称ビルディングブロック、交通情報ビルディングブロック、三次元物体ビルディングブロック、接合画像ビルディングブロック、デジタル地形ビルディングブロックの少なくとも1つを含む、上記項目のいずれか1つに記載の方法。
(項目5)
上記複数のビルディングブロックの最も頻出するサブストリングを1つのシードブロックに保存する、上記項目のいずれか1つに記載の方法。
(項目6)
上記最も頻出するサブストリングを含むシードブロックをビルディングブロックごとに決定する、上記項目のいずれか1つに記載の方法。
(項目7)
各ビルディングブロックを圧縮前にいくつかの部分に分離し、ビルディングブロックの一部ごとに上記最も頻出するサブストリングを決定し、上記ビルディングブロックの種々の部分の上記最も頻出するサブストリングを1つのシードブロックに保存する、上記項目のいずれか1つに記載の方法。
(項目8)
上記圧縮ナビゲーション地図データベースを生成するように構成された圧縮モジュールであって、
非圧縮ナビゲーション地図データを含む第1のデータベース(110)であって、上記非圧縮ナビゲーション地図データがナビゲーションデータの種々のビルディングブロック(111)を含み、各ビルディングブロックが上記ナビゲーション地図データの特定の機能態様に対応し、各ビルディングブロックがデータ文字列を含む、第1のデータベース(110)と、
第2のデータベース(120)と、上記非圧縮ナビゲーション地図データの上記ビルディングブロック(111)に対して、上記ビルディングブロックの最も頻出するサブストリングを決定するように構成され、上記ビルディングブロックに対して、上記ビルディングブロックの上記決定された最も頻出するサブストリングを少なくとも1つのシードブロック(121)に保存するように構成され、上記ビルディングブロックに対して、上記文字列における、上記少なくとも1つのシードブロックに保存されている上記決定された最も頻出するサブストリングと、上記少なくとも1つのシードブロック(121)への参照を置換することにより、ビルディングブロックごとに圧縮ブロック(122)を生成するように構成され、上記圧縮ナビゲーション地図データベースを生成するために、上記圧縮ブロック(122)および上記少なくとも1つのシードブロック(121)を上記第2のデータベース(122)に保存するように構成された処理装置(100)と、を備えている、圧縮モジュール。
(項目9)
上記処理装置(100)は、上記置換された参照にオフセット情報および長さ情報を含むように構成されており、上記オフセット情報は、上記置換された最も頻出するサブストリングが位置する、上記シードブロック内の位置を示し、上記長さ情報は上記置換された最も頻出するサブストリングの長さを示す、上記項目に記載の圧縮モジュール。
(項目10)
上記処理装置(100)は、ブロックのプレフィックスツリーを生成し、上記プレフィックスツリーにおける最も頻出するサブストリングを決定することにより、上記ブロックの最も頻出するサブストリングを決定するように構成されている、上記項目のいずれか1つに記載の圧縮モジュール。
(項目11)
ユーザにナビゲーション情報を与えるナビゲーションシステム(300)であって、
圧縮ナビゲーション地図データのナビゲーション地図データベースを含む記憶装置(310)であって、上記圧縮ナビゲーションデータがナビゲーションデータの種々のビルディングブロックを含み、各ビルディングブロックが上記ナビゲーションデータの特定の機能態様に対応し、各ビルディングブロックがデータ文字列を含み、上記地図データベースが少なくとも1つのシードブロック(121)および圧縮ブロック(122)を含み、上記シードブロック(121)が上記少なくとも1つのビルディングブロックの最も頻出するサブストリングを含み、上記圧縮ブロック(122)において、上記少なくとも1つのシードブロック(121)に保存されている上記決定された最も頻出するサブストリングと、上記少なくとも1つのシードブロックへの参照とを置換する、記憶装置(310)と、
上記ユーザに上記ナビゲーション情報を与える情報ユニット(340)と、
上記圧縮ナビゲーション地図データから非圧縮ナビゲーション地図データを生成するように構成された復元ユニット(350)であって、上記圧縮ブロック(122)および上記少なくとも1つのシードブロック(121)にアクセスし、上記非圧縮ナビゲーション地図データを生成するために、上記圧縮ブロック(122)に含まれる上記参照と、上記少なくとも1つのシードブロック(121)に保存されている対応する上記最も頻出するサブストリングとを置換し、上記非圧縮ナビゲーション地図データに基づいて上記ナビゲーション情報を生成するように構成され、上記情報ユニット(340)が、上記非圧縮ナビゲーション地図データを利用して上記ユーザに上記ナビゲーション情報を与える復元ユニット(350)と、を含むナビゲーションシステム(300)。
(項目12)
ユーザにナビゲーション情報を与えるための方法であって、
圧縮ナビゲーション地図データから非圧縮ナビゲーション地図データを生成するステップであって、上記圧縮ナビゲーション地図データがナビゲーション地図データの種々のビルディングブロックを含み、各ビルディングブロックが上記ナビゲーション地図データの特定の機能態様に対応し、各ビルディングブロックがデータ文字列を含み、上記圧縮ナビゲーションデータが少なくとも1つのシードブロック(121)および圧縮ブロック(122)を含み、上記少なくとも1つのシードブロック(121)が上記ビルディングブロックの最も頻出するサブストリングを含み、上記圧縮ブロック(122)において、上記少なくとも1つのシードブロックに保存されている上記決定された最も頻出するサブストリングと、上記少なくとも1つのシードブロックへの参照(121)とを置換し、上記圧縮ブロック(122)および上記少なくとも1つのシードブロック(121)にアクセスし、上記非圧縮ナビゲーション地図データを生成するために、上記圧縮ブロックに含まれる上記参照と、上記少なくとも1つのシードブロックに保存されている上記対応する最も頻出するサブストリングとを置換する、ステップと、
上記非圧縮ナビゲーション地図データに基づいて上記ナビゲーション情報を生成し、上記非圧縮ナビゲーション地図データに基づいて上記ユーザに上記ナビゲーション情報を与えるステップと、を含む、方法。
【0019】
(摘要)
本発明は、非圧縮ナビゲーション地図データから圧縮ナビゲーション地図データベースを生成するための方法に関する。非圧縮ナビゲーション地図データはナビゲーションデータの種々のビルディングブロックを含み、各ビルディングブロックはナビゲーションデータの特定の機能態様に対応し、各ブロックはデータ文字列を含む。この方法は、非圧縮ナビゲーション地図データのブロックごとに、最も頻出するブロックのサブストリングを決定するステップと、ブロックごとに、決定した最も頻出するブロックのサブストリングをシードブロックに保存するステップと、ブロックごとに、文字列における、シードブロックに保存されている決定された最も頻出するサブストリングと、シードブロックへの参照とを置換することにより、ブロックごとに圧縮ブロックを生成するステップと、圧縮ナビゲーション地図データベースを生成するために、ブロックごとに、圧縮ブロックおよびシードブロックを保存するステップと、を含む。
【0020】
前述および他の特徴並びに実施形態は、以下の添付図面を参照して読解される以下の発明を実施するための形態からより明らかとなる。
【図面の簡単な説明】
【0021】
【図1】圧縮ナビゲーション地図データを生成するように構成された圧縮モジュールを示す概略図である。
【図2】圧縮地図ナビゲーションデータを生成するために実行されるステップを含むフローチャートである。
【図3】図1に示すシステムを用いて生成された圧縮ナビゲーション地図データを利用するナビゲーションシステムを示す概略図である。
【図4】使用前に圧縮ナビゲーション地図データを復元するために実行されるステップを含むフローチャートである。
【発明を実施するための形態】
【0022】
図1に、非圧縮ナビゲーション地図データから圧縮ナビゲーション地図データを生成可能な圧縮モジュールの概略図を示す。圧縮モジュールは、データの種々のブロック111を保存する第1のデータベース110を備えている。データベース110に保存されている地図データは、特定の地理的領域を包含する。さらに、ナビゲーション地図データは、例えば、地理的領域をタイルに分割することにより、種々の地理的地域に分割されてもよい。図1に示す実施形態では、種々の地理的地域への分離は示された実施形態を反映しない。示された実施形態では、ナビゲーション地図データの分離は、地図データの機能態様を考慮して実行される。例証として、図1に示す第1のブロックは、経路指定アプリケーションに用いられる地図データの機能を利用してグループ分けされる経路指定ビルディングブロックでもよい。経路指定ビルディングブロックは、経路の計算に用いられる道路網の表示を含んでもよい。図1に示す第2のビルディングブロックは、とりわけ、地図上に示す種々の物体の名称を与える名称ビルディングブロックでもよい。図1に示すビルディングブロック3は、地図表示アプリケーションにおける機能を利用してグループ分けされる地図表示ビルディングブロックでもよい。これは、それらの幾何学的データと共に二次元マップを提供するのに必要な機能を含んでもよい。より多くのビルディングブロックがデータベース110に備えられてもよいことが理解されるべきである。例えば、交通情報ビルディングブロック、PoI(興味のある地点)ビルディングブロック、音声ビルディングブロック、三次元物体ビルディングブロックなどが備えられてもよい。処理装置100は、第1のデータベースにアクセスし、各ブロックに含まれる最も頻出するサブストリングを事前に計算するような方法によりブロック111各々を処理する。ブロックに保存されている情報の一部は文字列である。処理装置は、各ブロックにおけるある数の最も頻出するサブストリングを特定する。ブロックの最も頻出するサブストリングの数は、各ブロックに含まれる文字列の数に応じてもよく、データ型は、例えば、100〜約5000の間で変化してもよい。最も頻出するサブストリングは、ブロックごとにプレフィックスツリーを生成し、このプレフィックスツリーにおける最も頻出するサブストリングを特定することにより決定されてもよい。この状況では、サブストリングは文字列の部分要素である。名称ビルディングブロックでは、最も頻出するサブストリングは、種々の名称の中に発生する最も頻出する文字の並びを含むことができる。
【0023】
より多くのサブストリングが、代用される最も頻出するサブストリングとして特定されると、圧縮率はより高くなるであろう。処理装置100は、ここで、種々のブロック111において生じた決定された最も頻出するサブストリングと、決定された最も頻出するサブストリングが保存されているシードブロックと名称が付いたブロックへの参照とを置換する。最も頻出するサブストリングを含むこのシードブロックは、圧縮されるデータの(仮想)プレフィックスの役割を果たすことができる。処理装置は第2のデータベースに圧縮データを保存する。図1に示すように、ブロック111に関する、ブロック1の最も頻出するサブストリングを備えているシードブロック121aが生成され、さらに、シードブロック121aに含まれる最も頻出するサブストリングがシードブロック121aへの参照と置換された圧縮ブロック122aが生成される。参照は、除外されたサブストリングが保存されている、シードブロック内の位置を示すオフセット情報をさらに含む。さらに、参照は、置換したサブストリングの長さを示す長さ情報を含む。さらに、データベース110のブロック2に関して、シードブロック121bおよび圧縮ブロック122bが生成される。シードブロック121cは、ブロック3の最も頻出するサブストリングを備えており、圧縮ブロック122cは、シードブロックへの参照と共に、他の置換されていない文字列を備えている。
【0024】
提示の実施形態では、第1の記憶装置110に含まれるビルディングブロックごとに圧縮ナビゲーション地図データが生成される。しかしながら、圧縮ブロックおよびシードブロックが、データベース110に含まれるブロックごとに生成されなくてもよいことが理解されるべきである。例証として、データベース110のブロック111の1つのサイズが他のブロックと比較してはるかに小さい場合には、このようなブロックの圧縮は省略されてもよい。
【0025】
図1に示す実施形態では、ビルディングブロックごとに1つのシードブロックを生成する。しかしながら、2つ以上のビルディングブロックの最も頻出するサブストリングを単一シードブロックに保存することも可能である。この実施形態では、シードブロック121aなどの1つのシードブロックは、圧縮ブロック1および圧縮ブロック2の最も頻出するサブストリングを備えることになる。
【0026】
さらに、ブロック111を圧縮前に種々の部分に分離し、ビルディングブロックの種々の部分ごとに最も頻出するサブストリングを決定することにより、圧縮ブロックごとに、図1に示す部分125、126および127などの圧縮部を生成することが可能である。この実施形態では、種々の圧縮部125〜127の最も頻出するサブストリングを1つのシードブロックに保存する。種々の圧縮部における圧縮ブロックの分離は、2つ以上のビルディングブロックの最も頻出するサブストリングを単一シードブロックに保存する実施形態と組み合わせられてもよい。それ故、この実施形態では、圧縮ブロック1の圧縮部と、例えば、圧縮ブロック2の圧縮部とを単一シードブロックに保存することになる。ただし、圧縮部を含む圧縮ブロックごとにシードブロックを生成することも可能である。
【0027】
図2に、圧縮ナビゲーション地図データを生成するために実行されるステップを要約して示す。この方法は、ステップ20で開始され、ステップ21において、ブロックに含まれる文字列に対して最も頻出するサブストリングを決定する。次のステップ22において、ステップ21で決定された最も頻出するサブストリングをシードブロックに保存し、共にグループ化する。さらに、シードブロックに保存されているサブストリングの数を決定する場合には、ブロックにおけるこれらのサブストリングとシードブロックへの参照とを置換する(ステップ23)。次に、ステップ24において、シードブロックおよび圧縮ブロックを保存する。この方法はステップ25で終了する。
【0028】
図1に示す実施形態では、第1のデータベース110と第2のデータベース120とを別々の構成要素として示した。しかしながら、第1のデータベースと第2のデータベースとは単一物理記憶装置として示されてもよいことが理解されるべきである。これにより、非圧縮ブロック111を、対応する圧縮データとして同じ物理記憶装置に保存してもよい。
【0029】
記憶装置120に保存されている圧縮ナビゲーション地図データを、図3に示すナビゲーションシステムによって用いることができる。図3に示すナビゲーションシステム300は記憶装置310を備えており、シードブロック121および対応する圧縮ブロック122を含む、圧縮ナビゲーション地図データが保存されている。データベース310に保存されているデータは、図1に示すデータベース120に保存されているデータと対応することができる。データベース310は、ランダムアクセスメモリ、フラッシュメモリ、またはハードドライブなどの種々のストレージまたは記憶媒体に加えて、コンパクトディスク、DVD、メモリカードなどのリムーバブルメモリの任意のものまたは任意の組み合わせを含んでもよい。ナビゲーションシステムは、第1の位置から第2の位置までの最速または最短経路を計算するように構成されている経路計算ユニット320をさらに含む。ユーザは、入力ユニット330を介してナビゲーションシステムの機能を制御することができる。入力ユニットは、押圧または回転することができるボタンなどの触覚デバイスを含んでもよい。入力ユニットは、音声コマンドを利用してナビゲーションシステムの機能を制御可能な音声認識モジュールをさらに含むことができる。経路計算ユニットが計算した情報は、表示部340に表示することができる。さらに、運転アドバイスもボイスコマンドを利用して出力されてもよい。また、信号を受け取った場所がナビゲーションシステムの位置計算に用いられる衛星信号を受信するアンテナ350を備えることができる。ナビゲーションシステムが規定位置から所望の位置までの経路を計算する方法は当業界で既知であり、詳細は説明しない。明確さのために、本発明の理解に役立つナビゲーションシステムの構成要素のみを示す。ナビゲーションシステムが異なるモジュール、および図3に示す概略図に限定されないさらなる特徴を含んでもよいことが理解されるべきである。
【0030】
さらに、種々のモジュールが、ソフトウェア、ハードウェア、またはそれらの組み合わせにより組み込まれてもよい。
【0031】
ナビゲーションシステムは、データベース310に保存されているナビゲーションデータを、経路計算ユニットに用いることが可能になる前、または表示部340に表示されることが可能になる前に復元する復元ユニットをさらに備えている。復元ユニットは、圧縮ブロック122a,122bにおける参照と、対応するシードブロック121a,121bに保存されているサブストリングとを置換する。
【0032】
換言すれば、復元において、それを仮想プレフィックスとしてシードブロックに保存する場合には、シードブロックまたはサブストリングブロックを圧縮データブロックの仮想プレフィックスとして用いる。前述の記載からさらに理解することができるように、シードブロック無しでは、ナビゲーション地図データの復元は不可能である。これは、種々の機能ブロックに対する、シードブロックおよび圧縮ブロックの使用が、対応するシードブロック無しでは使用することができない、ナビゲーションデータとしてのデータの暗号化を提供することを意味する。復元ユニット350が全てへの参照と対応するサブストリングとを置換することによりブロックを復元した場合には、その結果、経路計算ユニットおよびナビゲーションシステムの他のモジュールによって、非圧縮ナビゲーション地図データを用いることができる。
【0033】
シードブロックを圧縮ブロックとは別に保存された場合には、第1の暗号化が得られる。さらに、圧縮ブロックを含むシードブロック(複数可)を保存し、AES(Advanced Encryption Standard)またはRSA(Rivest Shamir and Adleman Encryption)などの既知の暗号方式を利用したシードブロックを暗号化することが可能である。
【0034】
図4に、復元に関する種々のステップを要約して示す。この方法はステップ40で開始し、ステップ41においてシードブロックにアクセスし、ステップ42において圧縮ブロックにアクセスする。各圧縮ブロックにおいて、参照と置換されたサブストリングが対応するシードブロックにおいて特定され、非圧縮ブロックを生成するために、置換されたサブストリングを圧縮ブロックに再度取り込む(ステップ43)。ステップ44において、非圧縮ナビゲーション地図データに基づいて、ユーザに出力されるナビゲーション情報を生成することができる。この方法はステップ45で終了する。
【0035】
前述の記載から、本発明がナビゲーション地図データの効率的な圧縮を提供することが理解される。同時に、圧縮方法は、対応するシードブロック無しでは、ナビゲーション地図データとして用いることができないデータの暗号化を提供する。暗号化を改善するために、シードブロックに提供される情報は、既知の暗号方式を用いてさらに暗号化されてもよい。

【特許請求の範囲】
【請求項1】
非圧縮ナビゲーション地図データから圧縮ナビゲーション地図データベースを生成するための方法であって、
前記非圧縮ナビゲーション地図データはナビゲーションデータの種々のビルディングブロック(111)を含み、各ビルディングブロックは前記ナビゲーションデータの特定の機能態様に対応し、各ブロックはデータ文字列を含み、前記方法は、
前記非圧縮ナビゲーション地図データの前記ビルディングブロックに対して、前記ビルディングブロックに含まれる最も頻出するサブストリングを決定するステップと、
前記ビルディングブロックに対して、前記決定された最も頻出するサブストリングを少なくとも1つのシードブロック(121)に保存するステップと、
前記ビルディングブロックにおいて、前記文字列における、前記少なくとも1つのシードブロック(121)に保存されている前記決定された最も頻出するサブストリングと、前記少なくとも1つのシードブロックへの参照とを置換することにより、ビルディングブロックごとに圧縮ブロック(122)を生成するステップと、
前記圧縮ナビゲーション地図データベースを生成するために、前記圧縮ブロック(122)および前記少なくとも1つのシードブロック(121)を保存するステップと、を含む、方法。
【請求項2】
前記置換された参照はオフセット情報および長さ情報を含み、前記オフセット情報は、前記置換された最も頻出するサブストリングが位置する、前記シードブロック内の位置を示し、前記長さ情報は前記置換された最も頻出するサブストリングの長さを示す、請求項1に記載の方法。
【請求項3】
前記ブロックのプレフィックスツリーを決定し、前記プレフィックスツリーにおける最も頻出するサブストリングを決定することにより、前記ブロックの最も頻出するサブストリングを生成する、請求項1または2に記載の方法。
【請求項4】
前記非圧縮ナビゲーション地図データは、経路指定ビルディングブロック、名称ビルディングブロック、交通情報ビルディングブロック、三次元物体ビルディングブロック、接合画像ビルディングブロック、デジタル地形ビルディングブロックの少なくとも1つを含む、請求項1〜3のいずれか1項に記載の方法。
【請求項5】
前記複数のビルディングブロックの最も頻出するサブストリングを1つのシードブロックに保存する、前記請求項1〜4のいずれか1項に記載の方法。
【請求項6】
前記最も頻出するサブストリングを含むシードブロックをビルディングブロックごとに決定する、請求項1〜4のいずれか1項に記載の方法。
【請求項7】
各ビルディングブロックを圧縮前にいくつかの部分に分離し、ビルディングブロックの一部ごとに前記最も頻出するサブストリングを決定し、前記ビルディングブロックの種々の部分の前記最も頻出するサブストリングを1つのシードブロックに保存する、前記請求項1〜6のいずれか1項に記載の方法。
【請求項8】
前記圧縮ナビゲーション地図データベースを生成するように構成された圧縮モジュールであって、
非圧縮ナビゲーション地図データを含む第1のデータベース(110)であって、前記非圧縮ナビゲーション地図データがナビゲーションデータの種々のビルディングブロック(111)を含み、各ビルディングブロックが前記ナビゲーション地図データの特定の機能態様に対応し、各ビルディングブロックがデータ文字列を含む、第1のデータベース(110)と、
第2のデータベース(120)と、前記非圧縮ナビゲーション地図データの前記ビルディングブロック(111)に対して、前記ビルディングブロックの最も頻出するサブストリングを決定するように構成され、前記ビルディングブロックに対して、前記ビルディングブロックの前記決定された最も頻出するサブストリングを少なくとも1つのシードブロック(121)に保存するように構成され、前記ビルディングブロックに対して、前記文字列における、前記少なくとも1つのシードブロックに保存されている前記決定された最も頻出するサブストリングと、前記少なくとも1つのシードブロック(121)への参照を置換することにより、ビルディングブロックごとに圧縮ブロック(122)を生成するように構成され、前記圧縮ナビゲーション地図データベースを生成するために、前記圧縮ブロック(122)および前記少なくとも1つのシードブロック(121)を前記第2のデータベース(122)に保存するように構成された処理装置(100)と、を備えている、圧縮モジュール。
【請求項9】
前記処理装置(100)は、前記置換された参照にオフセット情報および長さ情報を含むように構成されており、前記オフセット情報は、前記置換された最も頻出するサブストリングが位置する、前記シードブロック内の位置を示し、前記長さ情報は前記置換された最も頻出するサブストリングの長さを示す、請求項8に記載の圧縮モジュール。
【請求項10】
前記処理装置(100)は、ブロックのプレフィックスツリーを生成し、前記プレフィックスツリーにおける最も頻出するサブストリングを決定することにより、前記ブロックの最も頻出するサブストリングを決定するように構成されている、請求項8または9に記載の圧縮モジュール。
【請求項11】
ユーザにナビゲーション情報を与えるナビゲーションシステム(300)であって、
圧縮ナビゲーション地図データのナビゲーション地図データベースを含む記憶装置(310)であって、前記圧縮ナビゲーションデータがナビゲーションデータの種々のビルディングブロックを含み、各ビルディングブロックが前記ナビゲーションデータの特定の機能態様に対応し、各ビルディングブロックがデータ文字列を含み、前記地図データベースが少なくとも1つのシードブロック(121)および圧縮ブロック(122)を含み、前記シードブロック(121)が前記少なくとも1つのビルディングブロックの最も頻出するサブストリングを含み、前記圧縮ブロック(122)において、前記少なくとも1つのシードブロック(121)に保存されている前記決定された最も頻出するサブストリングと、前記少なくとも1つのシードブロックへの参照とを置換する、記憶装置(310)と、
前記ユーザに前記ナビゲーション情報を与える情報ユニット(340)と、
前記圧縮ナビゲーション地図データから非圧縮ナビゲーション地図データを生成するように構成された復元ユニット(350)であって、前記圧縮ブロック(122)および前記少なくとも1つのシードブロック(121)にアクセスし、前記非圧縮ナビゲーション地図データを生成するために、前記圧縮ブロック(122)に含まれる前記参照と、前記少なくとも1つのシードブロック(121)に保存されている対応する前記最も頻出するサブストリングとを置換し、前記非圧縮ナビゲーション地図データに基づいて前記ナビゲーション情報を生成するように構成され、前記情報ユニット(340)が、前記非圧縮ナビゲーション地図データを利用して前記ユーザに前記ナビゲーション情報を与える復元ユニット(350)と、を含むナビゲーションシステム(300)。
【請求項12】
ユーザにナビゲーション情報を与えるための方法であって、
圧縮ナビゲーション地図データから非圧縮ナビゲーション地図データを生成するステップであって、前記圧縮ナビゲーション地図データがナビゲーション地図データの種々のビルディングブロックを含み、各ビルディングブロックが前記ナビゲーション地図データの特定の機能態様に対応し、各ビルディングブロックがデータ文字列を含み、前記圧縮ナビゲーションデータが少なくとも1つのシードブロック(121)および圧縮ブロック(122)を含み、前記少なくとも1つのシードブロック(121)が前記ビルディングブロックの最も頻出するサブストリングを含み、前記圧縮ブロック(122)において、前記少なくとも1つのシードブロックに保存されている前記決定された最も頻出するサブストリングと、前記少なくとも1つのシードブロックへの参照(121)とを置換し、前記圧縮ブロック(122)および前記少なくとも1つのシードブロック(121)にアクセスし、前記非圧縮ナビゲーション地図データを生成するために、前記圧縮ブロックに含まれる前記参照と、前記少なくとも1つのシードブロックに保存されている前記対応する最も頻出するサブストリングとを置換する、ステップと、
前記非圧縮ナビゲーション地図データに基づいて前記ナビゲーション情報を生成し、前記非圧縮ナビゲーション地図データに基づいて前記ユーザに前記ナビゲーション情報を与えるステップと、を含む、方法。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate


【公開番号】特開2013−88815(P2013−88815A)
【公開日】平成25年5月13日(2013.5.13)
【国際特許分類】
【出願番号】特願2012−228051(P2012−228051)
【出願日】平成24年10月15日(2012.10.15)
【出願人】(504147933)ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【Fターム(参考)】