JP6116185B2 - 圧縮ナビゲーション地図データ - Google Patents

Description

本発明は、非圧縮ナビゲーション地図データから圧縮ナビゲーション地図データを生成するための方法、圧縮ナビゲーション地図データを生成するように構成された圧縮モジュール、ユーザにナビゲーション情報を与えるための方法、およびユーザにナビゲーション情報を与えるナビゲーションシステムに関するものである。

２位置間の経路探索などの機能を実行するナビゲーションシステムが周知となっている。最新のナビゲーションシステムは、要求に応じて関心のある地点に関する情報を出力する旅行ガイド等として機能するものなどのような追加の機能なども備える場合がある。いくつかのナビゲーションシステムは、 テキストおよび／またはマルチメディア形式で詳細な説明を出力する旅行ガイド機能さえも含む場合がある。

さらに、道路、建物などに加えて、車両周囲の三次元視野を三次元形態で表示することが一般的になってきた。三次元表示により、当然ながら、正しい進路の認識が容易になる。

ユーザに与えられる様々な種類の情報は全て、ＣＤ ＲＯＭまたはＤＶＤなどのリムーバブルデータ記憶装置に保存され、またはこの情報はハードディスクに提供される。

この状況において、必要な情報をユーザに通知するのに用いられる、種々の情報を含むナビゲーション地図データに必要な記憶スペースの最小化に対する要求がある。

従って、ナビゲーション地図データの保存に必要な記憶スペースを効率的に低減可能な方法の提供に対する要求がある。

この要求は独立クレームの特徴によって満たされる。従属クレームでは、さらなる実施形態が記述される。

本発明の第１の態様に従い、非圧縮ナビゲーション地図データから圧縮ナビゲーション地図データベースを生成するための方法を提供する。非圧縮ナビゲーションデータはナビゲーションデータの種々のビルディングブロックを含み、各ビルディングブロックはナビゲーションデータの特定の機能態様に対応し、各ビルディングブロックはバイト列またはデータ文字列を含む。非圧縮ナビゲーション地図データの種々のビルディングブロックにおいて、ビルディングブロックに含まれる最も頻出するサブストリングを決定する。さらに、ビルディングブロックにおいて、そのビルディングブロックにおける決定された最も頻出するサブストリングを少なくとも１つのシードブロックに保存する。さらに、ビルディングブロックにおいて、前記少なくとも１つのシードブロックに保存されている決定された最も頻出するサブストリングを、前記少なくとも１つのシードブロックへの参照と、文字列において置換することにより、圧縮ブロックを生成する。さらに、圧縮ナビゲーション地図データベースを生成するために、圧縮ブロックおよび前記少なくとも１つのシードブロックを保存する。

全てのナビゲーションデータは、ナビゲーションデータの所定の機能態様を表現する各ビルディングブロックの１つに属するものと見なされる。例えば、機能ブロックは、経路ビルディングブロック、名称ビルディングブロックである。ナビゲーション地図データが種々の地理的地域にさらに分割され、データが種々の詳細レベルにさらに区分されてもよいことが理解されるべきである。しかしながら、本発明との関連では、機能ブロックへの分離が考察され、各機能ビルディングブロックは、ユーザに出力を提供する運転アドバイスなどの、ナビゲーションシステムにおいて用いられる種々の態様を表現する。例証として、経路ビルディングブロックは経路計算に関する機能を有し、名称ビルディングブロックは地図に示される街路名を含む。各ビルディングブロックにおいて、データは文字列で保存され、ブロックの内容に応じて、文字列は街路名であってもよく、画像に関する色情報を与えてもよい。ビルディングブロックにおいて、各ブロックに存在する最も頻出するサブストリングを決定することにより、前記少なくとも１つのシードブロックにおいて最も頻出するサブストリングを結合し、ビルディングブロックにおいて、最も頻出するサブストリングの代わりに、前記少なくとも１つのシードブロックへの参照を含むことが可能になる。このようにして、非圧縮ナビゲーション地図データよりも少ないストレージ容量を要する圧縮ブロックを得ることができる。前述の記載から、圧縮度が、圧縮ブロックにそれ以上含まれないが、シードブロックへの参照と置換される、シードブロックに保存されている最も頻出するサブストリングの数に応じて決まることが明らかである。

一実施形態では、複数のビルディングブロックの最も頻出するサブストリングを１つのシードブロックに保存することが可能である。これは、１つのシードブロックに、２以上のビルディングブロックの最も頻出するサブストリングが含まれてもよいことを意味する。しかしながら、別の実施形態では、最も頻出するサブストリングを含むシードブロックを、ビルディングブロックごとに決定することも可能である。この実施形態では、ビルディングブロックごとにシードブロックおよび圧縮ブロックが存在するが、この実施形態では、ビルディングブロックごとに圧縮ブロックが存在しても、圧縮ブロックごとに１つのシードブロックが必ずしも存在しなくてもよい。

さらに、各ビルディングブロックを圧縮前にいくつかの部分に分離し、ビルディングブロックの部分ごとに最も頻出するサブストリングを決定することも可能である。その後、ビルディングブロックの種々の部分の最も頻出するサブストリングを単一シードブロックに保存することができる。

好ましくは、置換された参照は、オフセット情報および長さ情報を含み、このオフセット情報は、置換された最も頻出するサブストリングが位置する、シードブロック内の位置を示す。長さ情報は、置換された最も頻出するサブストリングの長さに関する情報を与える。オフセット情報および長さ情報を含む参照は、圧縮ナビゲーション地図データをナビゲーションシステムに再度用いられる時に必要となることがある。完全情報の生成において、参照は、シードブロックに保存されている最も頻出するサブストリングと再度置換される。この置換では、この情報は、対応する置換された最も頻出するサブストリングがシードブロックのどこに保存されたかに用いられる。さらに、この情報は、置換された最も頻出するサブストリングがどれぐらいの長さかにも用いられる。

ブロックの最も頻出するサブストリングの決定するための１つの可能性は、ブロックに含まれる文字列のプレフィックスツリーを生成し、そのプレフィックスツリーにおける最も頻出するサブストリングを決定することである。プレフィックスツリーでは、ツリー内の文字列の位置に応じて、それに関連する文字列が規定される。ノードの全てのディセンデントは、そのノードに関連する文字列の共通プレフィックスを有する。各ノードに頻出度値が関連する場合には、ブロックの最も頻出するサブストリングを容易に決定できる。

非圧縮ナビゲーション地図データは、種々のブロック、経路ビルディングブロック、名称ビルディングブロック、交通情報ビルディングブロック、三次元物体ビルディングブロック、接合画像ビルディングブロック、またはデジタル地形ビルディングブロックを含むことができる。

本発明は、圧縮ナビゲーション地図データを生成するように構成された圧縮モジュールにもさらに関する。このモジュールは、非圧縮ナビゲーション地図データを含む第１のデータベースを備え、非圧縮ナビゲーション地図データはナビゲーションデータの種々のビルディングブロックを含み、各ビルディングブロックはナビゲーション地図データの特定の機能態様に対応し、各ブロックはデータ文字列を含む。さらに、前述するように、圧縮ブロックおよび前記少なくとも１つのシードブロックを決定するように構成された圧縮モジュールおよび処理装置内に、第２のデータベースが提供される。

本発明は、ユーザにナビゲーション情報を与えるナビゲーションシステムにもさらに関する。ナビゲーションシステムは圧縮ナビゲーション地図データを含む記憶装置を備え、圧縮ナビゲーション地図データはナビゲーション地図データの種々のビルディングブロックを含み、各ビルディングブロックはナビゲーション地図データの特定の機能態様に対応する。圧縮ナビゲーションデータは少なくとも１つのシードブロックおよび圧縮ブロックを含み、前記少なくとも１つのシードブロックは圧縮ブロックの最も頻出するサブストリングを含む。圧縮ブロックにおいて、前記少なくとも１つのシードブロックに保存されている決定された最も頻出するサブストリングと、前記少なくとも１つのシードブロックへの参照とを置換する。さらに、ナビゲーションシステムは、ユーザにナビゲーション情報を与える情報ユニットを備えている。例証として、ナビゲーション情報は、二次元または三次元の視覚出力でもよい。ナビゲーションシステムは、圧縮ナビゲーション地図データから非圧縮ナビゲーション地図データを生成するように構成された復元ユニットをさらに備えている。復元ユニットは、ビルディングブロックごとに、圧縮ブロックおよび前記少なくとも１つのシードブロックにアクセスし、非圧縮ナビゲーション地図データを生成するために、圧縮ブロックに含まれる参照と前記少なくとも１つのシードブロックの対応する最も頻出するサブストリングとを置換する。復元ユニットは、非圧縮ナビゲーション地図データに基づいてナビゲーション情報を生成するようにさらに構成され、情報ユニットは非圧縮ナビゲーション地図データを用いて、ユーザにナビゲーション情報を与える。

一実施形態では、復元において、圧縮および復元に関する仮想プレフィックスとしてシードブロックを用いることにより、圧縮および復元アルゴリズム簡素化する。通常では、各ブロックのシードブロック無しでは復元はできない。これはさらに、シードブロックが圧縮ブロックとは別に保存されている場合、圧縮ブロックにシードブロックが提供されないときはナビゲーション地図データを使用できないので、ナビゲーション地図データの低負荷の暗号化を提供する。本発明は、ユーザにナビゲーション情報を与える方法をさらに提供する。圧縮ナビゲーションデータから非圧縮ナビゲーション地図データを生成し、ブロックごとに、圧縮ブロックおよび前記少なくとも１つのシードブロックにアクセスし、圧縮ブロックに含まれる参照と前記少なくとも１つのシードブロックに保存されている対応する最も頻出するサブストリングとを置換することにより、非圧縮ナビゲーションデータを生成する。その後、非圧縮ナビゲーション地図データに基づいてユーザに関するナビゲーション情報を生成し、非圧縮ナビゲーション地図データに基づいてユーザにナビゲーション情報を与える。

例えば、本願発明は以下の項目を提供する。
（項目１）
非圧縮ナビゲーション地図データから圧縮ナビゲーション地図データベースを生成するための方法であって、
上記非圧縮ナビゲーション地図データはナビゲーションデータの種々のビルディングブロック（１１１）を含み、各ビルディングブロックは上記ナビゲーションデータの特定の機能態様に対応し、各ブロックはデータ文字列を含み、上記方法は、
上記非圧縮ナビゲーション地図データの上記ビルディングブロックに対して、上記ビルディングブロックに含まれる最も頻出するサブストリングを決定するステップと、
上記ビルディングブロックに対して、上記決定された最も頻出するサブストリングを少なくとも１つのシードブロック（１２１）に保存するステップと、
上記ビルディングブロックにおいて、上記文字列における、上記少なくとも１つのシードブロック（１２１）に保存されている上記決定された最も頻出するサブストリングと、上記少なくとも１つのシードブロックへの参照とを置換することにより、ビルディングブロックごとに圧縮ブロック（１２２）を生成するステップと、
上記圧縮ナビゲーション地図データベースを生成するために、上記圧縮ブロック（１２２）および上記少なくとも１つのシードブロック（１２１）を保存するステップと、を含む、方法。
（項目２）
上記置換された参照はオフセット情報および長さ情報を含み、上記オフセット情報は、上記置換された最も頻出するサブストリングが位置する、上記シードブロック内の位置を示し、上記長さ情報は上記置換された最も頻出するサブストリングの長さを示す、上記項目に記載の方法。
（項目３）
上記ブロックのプレフィックスツリーを決定し、上記プレフィックスツリーにおける最も頻出するサブストリングを決定することにより、上記ブロックの最も頻出するサブストリングを生成する、上記項目のいずれか１つに記載の方法。
（項目４）
上記非圧縮ナビゲーション地図データは、経路指定ビルディングブロック、名称ビルディングブロック、交通情報ビルディングブロック、三次元物体ビルディングブロック、接合画像ビルディングブロック、デジタル地形ビルディングブロックの少なくとも１つを含む、上記項目のいずれか１つに記載の方法。
（項目５）
上記複数のビルディングブロックの最も頻出するサブストリングを１つのシードブロックに保存する、上記項目のいずれか１つに記載の方法。
（項目６）
上記最も頻出するサブストリングを含むシードブロックをビルディングブロックごとに決定する、上記項目のいずれか１つに記載の方法。
（項目７）
各ビルディングブロックを圧縮前にいくつかの部分に分離し、ビルディングブロックの一部ごとに上記最も頻出するサブストリングを決定し、上記ビルディングブロックの種々の部分の上記最も頻出するサブストリングを１つのシードブロックに保存する、上記項目のいずれか１つに記載の方法。
（項目８）
上記圧縮ナビゲーション地図データベースを生成するように構成された圧縮モジュールであって、
非圧縮ナビゲーション地図データを含む第１のデータベース（１１０）であって、上記非圧縮ナビゲーション地図データがナビゲーションデータの種々のビルディングブロック（１１１）を含み、各ビルディングブロックが上記ナビゲーション地図データの特定の機能態様に対応し、各ビルディングブロックがデータ文字列を含む、第１のデータベース（１１０）と、
第２のデータベース（１２０）と、上記非圧縮ナビゲーション地図データの上記ビルディングブロック（１１１）に対して、上記ビルディングブロックの最も頻出するサブストリングを決定するように構成され、上記ビルディングブロックに対して、上記ビルディングブロックの上記決定された最も頻出するサブストリングを少なくとも１つのシードブロック（１２１）に保存するように構成され、上記ビルディングブロックに対して、上記文字列における、上記少なくとも１つのシードブロックに保存されている上記決定された最も頻出するサブストリングと、上記少なくとも１つのシードブロック（１２１）への参照を置換することにより、ビルディングブロックごとに圧縮ブロック（１２２）を生成するように構成され、上記圧縮ナビゲーション地図データベースを生成するために、上記圧縮ブロック（１２２）および上記少なくとも１つのシードブロック（１２１）を上記第２のデータベース（１２２）に保存するように構成された処理装置（１００）と、を備えている、圧縮モジュール。
（項目９）
上記処理装置（１００）は、上記置換された参照にオフセット情報および長さ情報を含むように構成されており、上記オフセット情報は、上記置換された最も頻出するサブストリングが位置する、上記シードブロック内の位置を示し、上記長さ情報は上記置換された最も頻出するサブストリングの長さを示す、上記項目に記載の圧縮モジュール。
（項目１０）
上記処理装置（１００）は、ブロックのプレフィックスツリーを生成し、上記プレフィックスツリーにおける最も頻出するサブストリングを決定することにより、上記ブロックの最も頻出するサブストリングを決定するように構成されている、上記項目のいずれか１つに記載の圧縮モジュール。
（項目１１）
ユーザにナビゲーション情報を与えるナビゲーションシステム（３００）であって、
圧縮ナビゲーション地図データのナビゲーション地図データベースを含む記憶装置（３１０）であって、上記圧縮ナビゲーションデータがナビゲーションデータの種々のビルディングブロックを含み、各ビルディングブロックが上記ナビゲーションデータの特定の機能態様に対応し、各ビルディングブロックがデータ文字列を含み、上記地図データベースが少なくとも１つのシードブロック（１２１）および圧縮ブロック（１２２）を含み、上記シードブロック（１２１）が上記少なくとも１つのビルディングブロックの最も頻出するサブストリングを含み、上記圧縮ブロック（１２２）において、上記少なくとも１つのシードブロック（１２１）に保存されている上記決定された最も頻出するサブストリングと、上記少なくとも１つのシードブロックへの参照とを置換する、記憶装置（３１０）と、
上記ユーザに上記ナビゲーション情報を与える情報ユニット（３４０）と、
上記圧縮ナビゲーション地図データから非圧縮ナビゲーション地図データを生成するように構成された復元ユニット（３５０）であって、上記圧縮ブロック（１２２）および上記少なくとも１つのシードブロック（１２１）にアクセスし、上記非圧縮ナビゲーション地図データを生成するために、上記圧縮ブロック（１２２）に含まれる上記参照と、上記少なくとも１つのシードブロック（１２１）に保存されている対応する上記最も頻出するサブストリングとを置換し、上記非圧縮ナビゲーション地図データに基づいて上記ナビゲーション情報を生成するように構成され、上記情報ユニット（３４０）が、上記非圧縮ナビゲーション地図データを利用して上記ユーザに上記ナビゲーション情報を与える復元ユニット（３５０）と、を含むナビゲーションシステム（３００）。
（項目１２）
ユーザにナビゲーション情報を与えるための方法であって、
圧縮ナビゲーション地図データから非圧縮ナビゲーション地図データを生成するステップであって、上記圧縮ナビゲーション地図データがナビゲーション地図データの種々のビルディングブロックを含み、各ビルディングブロックが上記ナビゲーション地図データの特定の機能態様に対応し、各ビルディングブロックがデータ文字列を含み、上記圧縮ナビゲーションデータが少なくとも１つのシードブロック（１２１）および圧縮ブロック（１２２）を含み、上記少なくとも１つのシードブロック（１２１）が上記ビルディングブロックの最も頻出するサブストリングを含み、上記圧縮ブロック（１２２）において、上記少なくとも１つのシードブロックに保存されている上記決定された最も頻出するサブストリングと、上記少なくとも１つのシードブロックへの参照（１２１）とを置換し、上記圧縮ブロック（１２２）および上記少なくとも１つのシードブロック（１２１）にアクセスし、上記非圧縮ナビゲーション地図データを生成するために、上記圧縮ブロックに含まれる上記参照と、上記少なくとも１つのシードブロックに保存されている上記対応する最も頻出するサブストリングとを置換する、ステップと、
上記非圧縮ナビゲーション地図データに基づいて上記ナビゲーション情報を生成し、上記非圧縮ナビゲーション地図データに基づいて上記ユーザに上記ナビゲーション情報を与えるステップと、を含む、方法。

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

前述および他の特徴並びに実施形態は、以下の添付図面を参照して読解される以下の発明を実施するための形態からより明らかとなる。

圧縮ナビゲーション地図データを生成するように構成された圧縮モジュールを示す概略図である。 圧縮地図ナビゲーションデータを生成するために実行されるステップを含むフローチャートである。 図１に示すシステムを用いて生成された圧縮ナビゲーション地図データを利用するナビゲーションシステムを示す概略図である。 使用前に圧縮ナビゲーション地図データを復元するために実行されるステップを含むフローチャートである。

図１に、非圧縮ナビゲーション地図データから圧縮ナビゲーション地図データを生成可能な圧縮モジュールの概略図を示す。圧縮モジュールは、データの種々のブロック１１１を保存する第１のデータベース１１０を備えている。データベース１１０に保存されている地図データは、特定の地理的領域を包含する。さらに、ナビゲーション地図データは、例えば、地理的領域をタイルに分割することにより、種々の地理的地域に分割されてもよい。図１に示す実施形態では、種々の地理的地域への分離は示された実施形態を反映しない。示された実施形態では、ナビゲーション地図データの分離は、地図データの機能態様を考慮して実行される。例証として、図１に示す第１のブロックは、経路指定アプリケーションに用いられる地図データの機能を利用してグループ分けされる経路指定ビルディングブロックでもよい。経路指定ビルディングブロックは、経路の計算に用いられる道路網の表示を含んでもよい。図１に示す第２のビルディングブロックは、とりわけ、地図上に示す種々の物体の名称を与える名称ビルディングブロックでもよい。図１に示すビルディングブロック３は、地図表示アプリケーションにおける機能を利用してグループ分けされる地図表示ビルディングブロックでもよい。これは、それらの幾何学的データと共に二次元マップを提供するのに必要な機能を含んでもよい。より多くのビルディングブロックがデータベース１１０に備えられてもよいことが理解されるべきである。例えば、交通情報ビルディングブロック、ＰｏＩ（興味のある地点）ビルディングブロック、音声ビルディングブロック、三次元物体ビルディングブロックなどが備えられてもよい。処理装置１００は、第１のデータベースにアクセスし、各ブロックに含まれる最も頻出するサブストリングを事前に計算するような方法によりブロック１１１各々を処理する。ブロックに保存されている情報の一部は文字列である。処理装置は、各ブロックにおけるある数の最も頻出するサブストリングを特定する。ブロックの最も頻出するサブストリングの数は、各ブロックに含まれる文字列の数に応じてもよく、データ型は、例えば、１００〜約５０００の間で変化してもよい。最も頻出するサブストリングは、ブロックごとにプレフィックスツリーを生成し、このプレフィックスツリーにおける最も頻出するサブストリングを特定することにより決定されてもよい。この状況では、サブストリングは文字列の部分要素である。名称ビルディングブロックでは、最も頻出するサブストリングは、種々の名称の中に発生する最も頻出する文字の並びを含むことができる。

より多くのサブストリングが、代用される最も頻出するサブストリングとして特定されると、圧縮率はより高くなるであろう。処理装置１００は、ここで、種々のブロック１１１において生じた決定された最も頻出するサブストリングと、決定された最も頻出するサブストリングが保存されているシードブロックと名称が付いたブロックへの参照とを置換する。最も頻出するサブストリングを含むこのシードブロックは、圧縮されるデータの（仮想）プレフィックスの役割を果たすことができる。処理装置は第２のデータベースに圧縮データを保存する。図１に示すように、ブロック１１１に関する、ブロック１の最も頻出するサブストリングを備えているシードブロック１２１ａが生成され、さらに、シードブロック１２１ａに含まれる最も頻出するサブストリングがシードブロック１２１ａへの参照と置換された圧縮ブロック１２２ａが生成される。参照は、除外されたサブストリングが保存されている、シードブロック内の位置を示すオフセット情報をさらに含む。さらに、参照は、置換したサブストリングの長さを示す長さ情報を含む。さらに、データベース１１０のブロック２に関して、シードブロック１２１ｂおよび圧縮ブロック１２２ｂが生成される。シードブロック１２１ｃは、ブロック３の最も頻出するサブストリングを備えており、圧縮ブロック１２２ｃは、シードブロックへの参照と共に、他の置換されていない文字列を備えている。

提示の実施形態では、第１の記憶装置１１０に含まれるビルディングブロックごとに圧縮ナビゲーション地図データが生成される。しかしながら、圧縮ブロックおよびシードブロックが、データベース１１０に含まれるブロックごとに生成されなくてもよいことが理解されるべきである。例証として、データベース１１０のブロック１１１の１つのサイズが他のブロックと比較してはるかに小さい場合には、このようなブロックの圧縮は省略されてもよい。

図１に示す実施形態では、ビルディングブロックごとに１つのシードブロックを生成する。しかしながら、２つ以上のビルディングブロックの最も頻出するサブストリングを単一シードブロックに保存することも可能である。この実施形態では、シードブロック１２１ａなどの１つのシードブロックは、圧縮ブロック１および圧縮ブロック２の最も頻出するサブストリングを備えることになる。

さらに、ブロック１１１を圧縮前に種々の部分に分離し、ビルディングブロックの種々の部分ごとに最も頻出するサブストリングを決定することにより、圧縮ブロックごとに、図１に示す部分１２５、１２６および１２７などの圧縮部を生成することが可能である。この実施形態では、種々の圧縮部１２５〜１２７の最も頻出するサブストリングを１つのシードブロックに保存する。種々の圧縮部における圧縮ブロックの分離は、２つ以上のビルディングブロックの最も頻出するサブストリングを単一シードブロックに保存する実施形態と組み合わせられてもよい。それ故、この実施形態では、圧縮ブロック１の圧縮部と、例えば、圧縮ブロック２の圧縮部とを単一シードブロックに保存することになる。ただし、圧縮部を含む圧縮ブロックごとにシードブロックを生成することも可能である。

図２に、圧縮ナビゲーション地図データを生成するために実行されるステップを要約して示す。この方法は、ステップ２０で開始され、ステップ２１において、ブロックに含まれる文字列に対して最も頻出するサブストリングを決定する。次のステップ２２において、ステップ２１で決定された最も頻出するサブストリングをシードブロックに保存し、共にグループ化する。さらに、シードブロックに保存されているサブストリングの数を決定する場合には、ブロックにおけるこれらのサブストリングとシードブロックへの参照とを置換する（ステップ２３）。次に、ステップ２４において、シードブロックおよび圧縮ブロックを保存する。この方法はステップ２５で終了する。

図１に示す実施形態では、第１のデータベース１１０と第２のデータベース１２０とを別々の構成要素として示した。しかしながら、第１のデータベースと第２のデータベースとは単一物理記憶装置として示されてもよいことが理解されるべきである。これにより、非圧縮ブロック１１１を、対応する圧縮データとして同じ物理記憶装置に保存してもよい。

記憶装置１２０に保存されている圧縮ナビゲーション地図データを、図３に示すナビゲーションシステムによって用いることができる。図３に示すナビゲーションシステム３００は記憶装置３１０を備えており、シードブロック１２１および対応する圧縮ブロック１２２を含む、圧縮ナビゲーション地図データが保存されている。データベース３１０に保存されているデータは、図１に示すデータベース１２０に保存されているデータと対応することができる。データベース３１０は、ランダムアクセスメモリ、フラッシュメモリ、またはハードドライブなどの種々のストレージまたは記憶媒体に加えて、コンパクトディスク、ＤＶＤ、メモリカードなどのリムーバブルメモリの任意のものまたは任意の組み合わせを含んでもよい。ナビゲーションシステムは、第１の位置から第２の位置までの最速または最短経路を計算するように構成されている経路計算ユニット３２０をさらに含む。ユーザは、入力ユニット３３０を介してナビゲーションシステムの機能を制御することができる。入力ユニットは、押圧または回転することができるボタンなどの触覚デバイスを含んでもよい。入力ユニットは、音声コマンドを利用してナビゲーションシステムの機能を制御可能な音声認識モジュールをさらに含むことができる。経路計算ユニットが計算した情報は、表示部３４０に表示することができる。さらに、運転アドバイスもボイスコマンドを利用して出力されてもよい。また、信号を受け取った場所がナビゲーションシステムの位置計算に用いられる衛星信号を受信するアンテナ３５０を備えることができる。ナビゲーションシステムが規定位置から所望の位置までの経路を計算する方法は当業界で既知であり、詳細は説明しない。明確さのために、本発明の理解に役立つナビゲーションシステムの構成要素のみを示す。ナビゲーションシステムが異なるモジュール、および図３に示す概略図に限定されないさらなる特徴を含んでもよいことが理解されるべきである。

さらに、種々のモジュールが、ソフトウェア、ハードウェア、またはそれらの組み合わせにより組み込まれてもよい。

ナビゲーションシステムは、データベース３１０に保存されているナビゲーションデータを、経路計算ユニットに用いることが可能になる前、または表示部３４０に表示されることが可能になる前に復元する復元ユニットをさらに備えている。復元ユニットは、圧縮ブロック１２２ａ，１２２ｂにおける参照と、対応するシードブロック１２１ａ，１２１ｂに保存されているサブストリングとを置換する。

換言すれば、復元において、それを仮想プレフィックスとしてシードブロックに保存する場合には、シードブロックまたはサブストリングブロックを圧縮データブロックの仮想プレフィックスとして用いる。前述の記載からさらに理解することができるように、シードブロック無しでは、ナビゲーション地図データの復元は不可能である。これは、種々の機能ブロックに対する、シードブロックおよび圧縮ブロックの使用が、対応するシードブロック無しでは使用することができない、ナビゲーションデータとしてのデータの暗号化を提供することを意味する。復元ユニット３５０が全てへの参照と対応するサブストリングとを置換することによりブロックを復元した場合には、その結果、経路計算ユニットおよびナビゲーションシステムの他のモジュールによって、非圧縮ナビゲーション地図データを用いることができる。

シードブロックを圧縮ブロックとは別に保存された場合には、第１の暗号化が得られる。さらに、圧縮ブロックを含むシードブロック（複数可）を保存し、ＡＥＳ（Ａｄｖａｎｃｅｄ Ｅｎｃｒｙｐｔｉｏｎ Ｓｔａｎｄａｒｄ）またはＲＳＡ（Ｒｉｖｅｓｔ Ｓｈａｍｉｒ ａｎｄ Ａｄｌｅｍａｎ Ｅｎｃｒｙｐｔｉｏｎ）などの既知の暗号方式を利用したシードブロックを暗号化することが可能である。

図４に、復元に関する種々のステップを要約して示す。この方法はステップ４０で開始し、ステップ４１においてシードブロックにアクセスし、ステップ４２において圧縮ブロックにアクセスする。各圧縮ブロックにおいて、参照と置換されたサブストリングが対応するシードブロックにおいて特定され、非圧縮ブロックを生成するために、置換されたサブストリングを圧縮ブロックに再度取り込む（ステップ４３）。ステップ４４において、非圧縮ナビゲーション地図データに基づいて、ユーザに出力されるナビゲーション情報を生成することができる。この方法はステップ４５で終了する。

前述の記載から、本発明がナビゲーション地図データの効率的な圧縮を提供することが理解される。同時に、圧縮方法は、対応するシードブロック無しでは、ナビゲーション地図データとして用いることができないデータの暗号化を提供する。暗号化を改善するために、シードブロックに提供される情報は、既知の暗号方式を用いてさらに暗号化されてもよい。

Claims (11)

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

Images