(57)【特許請求の範囲】
【請求項１】
自動車ナビゲーションシステムにおいて用いられる地理データベースを形成する方法であって、
前記地理データベースは、前記自動車ナビゲーションシステムを用いる自動車が進行する道路網を形成する個々の道路セグメントを表すデータエンティティを含んでおり、
前記道路網を形成する道路セグメントを表すデータエンティティの最初のコレクションを提供するステップと、
データエンティティの前記最初のコレクションを複数のグルーピングに分離するステップであって、前記グルーピングの各々が別個の矩形領域に位置する道路セグメントを表すデータエンティティを含み、前記データエンティティの全てが前記地理データベースを用いるときにグループとして共にアクセスされ、さらに、前記グルーピングの各々が所定のターゲットサイズより大きなデータサイズを有する、前記分離するステップと、
前記グルーピングの各々が前記所定のターゲットサイズより大きくないデータサイズを有し、前記グルーピングの全てが実質的に同一のデータサイズを有するように前記グルーピングの各々に対して圧縮方法を適用するステップと、
前記地理データベースを形成するために前記グルーピングを格納するステップとを備えた方法。
【請求項２】
前記圧縮方法は、
前記グルーピングの各々を通って前進するステップと、
各々の前記グルーピング内で一致するデータのサブストリングを識別するステップと、
先行するサブストリングと一致するデータのサブストリングを上記部分内に見出すと、上記サブストリングを置換コードで置換するステップと、
を備え、
上記置換コードは、上記サブストリングを上記置換コードで上記先行するサブストリングに置換した上記位置からの逆向きのオフセットを含む
ことを特徴とする請求項１に記載の方法。
【請求項３】
上記置換コードは、上記一致するサブストリングの長さを指示するデータ成分を更に含む請求項２に記載の方法。
【請求項４】
各々の前記グルーピング内のリテラル文字を、ハフマンコードで置換するステップを更に備えている請求項２に記載の方法。
【請求項５】
上記逆向きのオフセットを、ハフマンコードで置換するステップを更に備えている請求項２に記載の方法。
【請求項６】
上記一致するサブストリングの長さを指示するデータ成分を、ハフマンコードで置換するステップを更に備えている請求項２に記載の方法。
【請求項７】
各々の前記グルーピング内の文字を、その圧縮表現でコード化するステップと、
サブストリングが置換コードによって置換された各々の前記グルーピングとは別に、データベースの別の部分内に索引を格納するステップと、
を更に備え、
上記索引は、上記コード化された各文字と、上記圧縮表現とを関連付ける
請求項２に記載の方法。
【請求項８】
データエンティティの前記最初のコレクションを前記複数のグルーピングに分離する前に、分離した複数のデータエンティティを各々が含む分離した型のデータエンティティを形成するステップと、
各々の型内の上記複数のデータエンティティを、グループとして一緒にアクセスされる所与の型の分離した複数のデータエンティティを各々が含む複数のグルーピングに分離するステップとを更に備えている請求項１に記載の方法。
【請求項９】
前記索引を格納するステップは、上記索引を、上記地理データベースのグローバル部分内に格納することを備えている請求項７に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は圧縮システムに関し、詳しく述べれば、本発明はエンドユーザにナビゲーティング特色及び機能を提供するナビゲーション応用プログラムが使用する地理データベースと共に使用できる圧縮方法に関する。
【０００２】
【従来の技術】
エンドユーザ（例えば、ナビゲーションシステムが設置されているビークルの運転手）にいろいろなナビゲーティング機能及び特色を提供する、コンピュータをベースとするナビゲーション応用プログラムを使用することができる。例えば、若干のナビゲーション応用プログラムは、地理領域内の複数の位置の間の道路を走行するための最適ルートを決定することができる。エンドユーザからの入力、及びオプションとしてユーザの物理的位置を決定できる機器（例えば、ＧＰＳシステム）からの入力を使用して、ナビゲーション応用プログラムは地理領域内の２つの位置の間のいろいろなルートを調べ、出発点から目的地まで走行するのに最適なルートを決定することができる。次いでナビゲーション応用プログラムは、出発点から目的地までエンドユーザが走行するのに必要な運転を識別する命令の形状で、最適ルートに関する情報をエンドユーザに提供することができる。もしナビゲーションシステムが自動車に設置されているのであれば、命令は、エンドユーザがルートを走行中に供給されるオーディオ命令の形状をとることができる。若干のナビゲーション応用プログラムは、目的地までのルートを示す詳細地図、ルートに沿ういろいろな位置においてとるべき運転の型、若干の型の特色の位置、等々をコンピュータディスプレイ上に表示することができる。
【０００３】
これらの、及び他のナビゲーティング機能を提供するために、ナビゲーション応用プログラムは、地理領域内の物理的特色を表すデータを含む１つまたはそれ以上の詳細なデータベースを使用する。この／これらの詳細なデータベースは、地理領域内の道路及び交差点を表すデータを含むことができ、また交差点における転回禁止、道路の速度制限、さまざまな道路の街路名、いろいろな道路に沿う番地範囲、等々のような、表された地理領域内の道路及び交差点に関する情報を含むこともできる。
【０００４】
ナビゲーション応用プログラムが使用するための地理データを供給する上での問題の１つは、ナビゲーション応用プログラムを走らせているナビゲーションシステムの使用可能なコンピュータ資源の効率的な利用に関係がある。コンピュータをベースとするナビゲーション応用プログラムは、比較的制限されたコンピュータ資源を有するものを含むさまざまなプラットフォーム上に供給される。例えば、ナビゲーションシステムは、ビークルに搭載することも、または手持ちであることもできる。これらの型のナビゲーションシステムのコンピュータ資源はメモリが制限されていたり、またはＩ／Ｏが比較的遅いというように、比較的制限されている。これらのシステムに高レベルの機能を与えるためには、使用可能なコンピュータ資源を効率的に使用することが要求される。
【０００５】
若干のナビゲーションシステムの制限された資源は、特に比較的高レベルの詳細地図を含む比較的大きい地理データベースを使用する場合、所望のナビゲーション機能を提供するこれらの型のナビゲーションシステムの能力に影響を与える。地理データベース内に含まれる大量のデータを処理することは、制限された資源を有するナビゲーションシステムの性能に悪影響を及ぼし得る。
【０００６】
ナビゲーションシステムによる地理データの使用に関係する別の課題は、エンドユーザに所望レベルの機能を提供するのに必要な比較的大きいサイズの地理データベースが与えられた場合、地理領域全体の全てのデータレコードを同時にナビゲーションシステムのメモリ内にロードできないことである。これは、ビークル搭載のシステム、または手持ちシステムのように、資源が制限されているナビゲーションシステムプラットフォームの場合に特に然りである。これらのナビゲーションシステムのメモリ資源が制限されているので、ナビゲーション応用プログラムが使用するために、必要に応じてＣＤ−ＲＯＭディスクのような記憶媒体からナビゲーションシステムのメモリ内へ地理データをロードする必要がある。不幸にも、これらの型のシステムにおいては、記憶媒体からのＩ／Ｏアクセスは比較的遅いことがあり得る。従って、若干の型のナビゲーションシステムの比較的制限されたメモリ資源と、比較的遅いＩ／Ｏとを組合せると性能が制限されることがあり、それによってレスポンスが遅くなり得る。ナビゲーションシステムにおける遅いレスポンスは望ましくないだけではなく、若干の環境では意図した目的にとってシステムが無用になりかねない。例えば、もしナビゲーションシステムがビークルに搭載されていれば、運転手は運転中に情報を利用するために、１−２秒程度で所望ルートに関する情報をナビゲーションシステムから得たいであろう。もしナビゲーションシステムがルートを計算するのに数秒より多くを要すれば、運転手は既にナビゲーションシステムが提供するルーティング情報が関連している点を過ぎて移動してしまっていよう。従って、ナビゲーティング情報を比較的迅速に提供するためには、ナビゲーションシステムが効率的に動作することが重要である。
【０００７】
ナビゲーション応用プログラムは、パーソナルコンピュータまたはネットワークのような一般的により大きいメモリ資源とより速いＩ／Ｏとを有するコンピュータプラットフォーム上で走らせることもできる。これらのシステムはより多くの、そしてより速い資源を有しているかも知れないが、それでも地理データの効率的使用について、より大きいスケールで考えなければならない。これらの型のシステムでは、もしメモリサイズ及びＩ／Ｏによって賦課される制限が最小になれば、より大きい機能さえも得ることができる。
【０００８】
一般的に言えば、そして特定的には、ハードウェア資源が制限されている若干のナビゲーションシステムプラットフォームの制限を補償するために、特別な方法で地理データベース、または地理データベース内のデータを編成し、構成し、または配列することによって、ナビゲーションシステムの性能を改善する技術が考案され、または実現されている。ナビゲーションシステムは、既知の機能を遂行するために若干の既知の、及び予測される方法で地理データを使用するから、地理データは、ナビゲーションシステムがこれらの既知の方法で使用するのを容易にする方法で編成し、構成し、または配列することができる。
【０００９】
ナビゲーションシステムによる地理データの使用を容易にするために使用できる技術の１つは、少なくとも若干の地理データを空間的に編成することである。地理データを空間的に編成した場合、その地理領域内で物理的に近接している地理特色は、一般的に、データベース内で及び／または媒体上で近接したデータレコードによって表される。この種の編成は若干のナビゲーション機能を遂行する場合に、地理データベース内の探索の量を最小にすることができる。
【００１０】
ナビゲーションシステム内のある応用によるアクセスを容易にするために使用できる別の技術は、地理データベースの少なくとも若干をグルーピング（またはパーセル）に編成することである。地理データをパーセルに編成する場合、一緒になって地理データベースを構成している複数のデータレコードが分離したグルーピング（またはパーセル）に分離される。各パーセル内に含まれるべきデータレコードの選択は、特定のナビゲーション機能を遂行するために必要な全てのデータレコードが比較的僅かなパーセル内に含まれるという見込みに基づく。例えば、パーセルは、地理データの若干または全てを空間的に編成するために使用することができる。地理データを空間的に編成するためにパーセル化を行うと、地理領域内で物理的に近接して位置している地理特色は同一パーセル内に含まれるデータレコードによって表される。地理データをパーセルに編成するための基礎として、行政地域、アルファベット順の名前、等によるのような非空間的ファクタを含むいろいろな基準を使用することができる。
【００１１】
ナビゲーションシステムの動作を強化するために地理データベース内に実現することができる別の技術は、ルート計算に重要ではない、または補助的な道路の検討を最小にすることである。重要でない、または補助的な道路の検討を抑圧する１つの方法は、地理領域内の道路をランク付けして、地理データの若干または全てを層に編成することである。これらのランキングは、道路の機能的な分類に関係付けることができる。走行が一般に高速で行われる主要道路には高いランキングを割当て、走行が一般に遅い重要ではない道路には低いランキングを割当てる。これらのランキングを使用して、より高くランク付けされた道路を表すデータレコードを、地理データベース内の分離した層内に格納することができる。ナビゲーション応用プログラムは、可能な場合には、これらのより高い層を使用する。より高い層は遅い補助道路を省いているから、ルートを計算するためにこれらのより高い層を使用する場合、これらの一般に遅い道路は検討されず、それによって検討を要する可能道路セグメントが最小になる。この種のデータベース配列は、ルート計算ナビゲーション機能を容易にすることができ、それによってナビゲーションシステムの性能が改善される。
【００１２】
空間編成、パーセル化、及び層化に加えて、地理データベース内に実現して地理データベースを使用するナビゲーションシステムのナビゲーション応用の性能を強化することができる他の技術も存在している。これらの技術の若干、または全てを地理データベース内で一緒に使用し、地理データベースを使用するナビゲーション応用の動作を強化することができる。
【００１３】
ナビゲーションシステムが地理データベースを使用する手法に影響を与える１つのファクタは、地理データベースのカバレッジエリアのサイズが関係するものである。地理データベースのカバレッジエリアとは、地理データベース内のデータによって表される地理領域のサイズのことである。カバレッジエリアは、ニューヨークとその近郊、シカゴとその近郊、またはロスアンジェルスとその近郊のような、大都市圏全体を含むことができる。カバレッジエリアは、ドイツのような国全体を含むこともできる。一般的に言えば、カバレッジエリアは可能な限り大きくすることが好ましい。
【００１４】
地理データベースのカバレッジエリアのサイズに影響を与え得るファクタは、地理データベースを格納している媒体の型、及び地理データベースの詳細地図のレベルを含む。ナビゲーションシステムのエンドユーザが望むナビゲーション特色を提供するために、地理データベースは、対応する高レベルの詳細地図に伴う比較的大量のデータを含む。ナビゲーションシステムの地理データベースを格納するために、さまざまな種類の媒体を使用することができる。これらの異なる種類の媒体は、例えばＣＤ−ＲＯＭディスク、ＰＣＭＣＩＡカード、ハードディスク、ＤＶＤディスク、等々を含む。これらの異なる種類の各媒体は、長所と欠点とを有している。使用する媒体の種類には関係なく、可能な限り多くのデータを媒体上に格納して可能な限り大きいカバレッジエリア、または可能な限り多くの詳細地図、またはカバレッジエリアと詳細地図との最大の組合せを提供できるようにすることが望ましい。従って地理データは、効率的に媒体上に格納されるべきである。
【００１５】
従来から、媒体上に格納することができるデータの量を増加させるデータ圧縮技術が存在している。従来の若干のデータ圧縮技術は、媒体上に格納されている圧縮された形状のデータから、それを圧縮解除するためのかなりの付加的な処理を必要とする欠陥を有している。この付加的な処理は、若干のナビゲーションシステムの性能に悪影響を与える。更に、若干の従来のデータ圧縮技術は、データの一部を再配列すること、またはデータの元の集まり部分を他のデータで置換することを含んでいる。これらのデータ圧縮技術は、若干のナビゲーション機能を強化する上述した技術と両立できないかも知れない。もしこれらの従来のデータ圧縮技術が、上述したナビゲーション強化技術と完全に両立できなければ、ナビゲーション強化技術に伴う長所は相殺されてしまう。
【００１６】
従って、１つの目的は、地理データを媒体上に効率的に格納する手段を提供することである。別の目的は、ナビゲーション応用プログラムによるその使用を容易にする手法で編成された、地理データベースにおける１つまたはそれ以上のデータ圧縮技術を提供することである。いろいろな種類のデータ、特に地理データのために使用できるデータ圧縮技術を提供することも別の目的である。
【００１７】
【発明の概要】
上述した諸問題に対処するために、本発明の一面によれば、データ圧縮システム及び方法が提供される。このデータ圧縮システム及び方法は、いろいろな種類のデータを圧縮するために使用することができ、特に物理的データ記憶媒体上に格納される地理データを圧縮するために使用することができる。このデータ圧縮方法は、入力ストリームのデータ文字の先行部分内を、第１の部分における複数のデータ文字のシーケンスと一致する複数のデータ文字のシーケンスに関して、第１の部分から探索するステップを含む。複数のデータ文字のシーケンスと一致することがが見出されると、入力ストリームの先行部分内に一致する複数のデータ文字のシーケンスが見出された複数のデータ文字のシーケンスは、入力ストリームの先行部分内の一致する複数のデータ文字のシーケンスへの参照に置換される。この参照は、第１の位置から、一致する複数のデータ文字のシーケンスが位置する入力ストリームの先行部分内の位置までの逆向きのオフセットと、一致するシーケンスのサイズとからなる。
【００１８】
さらなる面によれば、逆向きのオフセット、一致するシーケンスのサイズを表すデータ、非置換コード文字の長さを表すデータ、及びリテラル文字自体は、ハフマンコード化することができる。ナビゲーション応用プログラムによるアクセス及び使用を容易にするように編成された地理データに対するデータ圧縮方法の応用においては、ハフマンコードを復号するための１つまたはそれ以上のハフマン木は、ハフマンコード化を使用して圧縮されたデータレコードを含むデータベースの部分とは別の部分内に格納される。
【００１９】
本発明の更に別の面によれば、圧縮解除方法及びプログラムが提供される。圧縮解除方法は、圧縮プロセスを逆にしたものである。圧縮されたデータストリームの一方の端から開始して、圧縮されたデータストリームを通って他方の端まで進み、置換コードに出会うと、それらの置換コードはデータストリームの先行部分内に位置するサブストリングと置換される。各置換コードは、逆向きのオフセットと、置換サブストリングの長さの指示とを含む。圧縮解除中、圧縮されたデータストリームを通って前進中に各置換コードに出会うと、指示された置換サブストリング長さの、そして逆向きのオフセットによって指示されたデータストリームの先行部分内の位置に位置するサブストリングが、データストリームの部分へ挿入される。
【００２０】
【実施例】
Ｉ．ナビゲーションシステム−概要
図１に、ナビゲーションシステム１０をブロック図で示す。ナビゲーションシステム１０は、乗用車またはトラックのようなビークル１１内に設置されているが、代替実施例では、ナビゲーションシステム１０は、後述するように、ビークル外に位置することも、または他のいろいろなプラットフォームまたは環境内に実現することもできる。
【００２１】
図１に示す実施例では、ナビゲーションシステム１０はハードウェア及びソフトウェア成分の組合せである。一実施例では、ナビゲーションシステム１０はプロセッサ１２、プロセッサ１２に接続されているドライブ１４、及びナビゲーション応用ソフトウェアプログラム１８及び多分他の情報を格納している不揮発性メモリ記憶装置１６を含んでいる。プロセッサ１２は、日立ＳＨ１、インテル 80386、インテル 960、モトローラ 68020（または、類似の、またはより大きいアドレス空間を有する他のプロセッサ）のようなフラットアドレス空間を使用する 32 ビットプロセッサのような、ナビゲーションシステム内に使用されるどのような型であることもできる。これら以外の型のプロセッサ、及び将来開発されるかも知れないプロセッサも適当であり得る。
【００２２】
ナビゲーションシステム１０は、測位システム２４を含むこともできる。測位システム２４は、当分野においては公知の、ＧＰＳ型技術、推測型システム、またはこれらの組合せ、または他のシステムを利用することができる。測位システム２４は、ビークルの走行距離、速度、方向、等々を測定する適当な感知デバイス２５を含むことができる。測位システム２４は、当分野においては公知の手法でＧＰＳ信号を入手する適切な技術を含むこともできる。測位システム２４は、信号２６をプロセッサ１２へ出力する。プロセッサ１２上で走るナビゲーション応用ソフトウェア１８はこの信号２６を使用して、ナビゲーションシステム１０の位置、方向、速度、等々を決定することができる。
【００２３】
ナビゲーションシステム１０は、ユーザインタフェース３１も含んでいる。ユーザインタフェース３１は、エンドユーザがナビゲーションシステム内へ情報を入力できるようにする適切な機器を含む。この入力情報は、ナビゲーションシステムのナビゲーション特色の使用の要求を含む。例えば、入力情報は、所望の目的地までのルートに関する要求を含むことができる。入力情報は、他の種類の情報を含むこともできる。ナビゲーションシステム内へ情報を入力するために使用される機器は、キーパッド、キーボード、マイクロホン、等々、並びに音声認識プログラムのような適切なソフトウェアを含むことができる。ユーザインタフェース３１は、エンドユーザへ情報を戻す適当な機器も含む。この機器は、ディスプレイ２７、スピーカ２９、または他の手段を含むことができる。
【００２４】
ナビゲーションシステム１０は、記憶媒体３２上に格納されている地図データベース４０を使用する。ナビゲーションシステムが地図データベース４０を読み出して使用することができるように、記憶媒体３２はドライブ１４内に設置されている。記憶媒体３２は取り外し可能であり、置換可能であるので、ビークルが走行している地理領域のための適切な地図データベース４０を有する記憶媒体を使用することができる。更に、記憶媒体３２は置換可能であるので、その上の地図データベース４０は容易に更新することができる。一実施例では、地理データはカリフォルニア州サニービルの Navigation Technologiesから出版されているものであることができる。
【００２５】
一実施例においては、記憶媒体３２はＣＤ−ＲＯＭディスクである。代替実施例においては、記憶媒体３２はＰＣＭＣＩＡカードであることができ、この場合ドライブ１４はＰＣＭＣＩＡスロットに置換される。固定またはハードディスク、ＤＶＤ（ディジタルビデオディスク）、または現在市販されている他の記憶媒体、並びに将来開発されるかも知れない記憶媒体を含む他のさまざまな記憶媒体を使用することができる。記憶媒体３２及び地理データベース４０は、物理的にナビゲーションシステムの位置に設ける必要はない。代替実施例においては、地理データベース４０の若干、または全てを格納している記憶媒体３２はナビゲーションシステムの残余から離して配置することができ、地理データの一部は必要に応じて通信リンクを介して供給される。
【００２６】
ナビゲーション応用ソフトウェアプログラム１８は、ナビゲーションシステムを動作させるために不揮発性メモリ１６からプロセッサ１２に組合されているＲＡＭ  ２０内へロードされる。ナビゲーションシステム１０は、記憶媒体３２上に格納されている地図データベースを、多分測位システム２４からの出力２６と共に使用して、さまざまなナビゲーション特色及び機能を提供する。ナビゲーション応用ソフトウェアプログラム１８は、これらのさまざまなナビゲーション特色及び機能を提供する分離した応用（または、サブプログラム）を含むことができる。これらの機能及び特色は、ルート計算機能４１、ルート案内機能４２（所望の目的地へ到達するための詳細な指令が供給される）、地図表示機能４３、ビークル位置決め機能４４（例えば、マップマッチング）、及び他の機能４５を含むことができる。
II. 地理データベース
Ａ．概要
一実施例では、ナビゲーションシステムの速度及び／または機能は、地理データを使用するシステム内のナビゲーション応用プログラム内の若干の機能によるデータの使用を容易にするために、システムが使用する地理データの格納、配列、及び／または構成の改良を含む組合せによって強化することができる。地理データを格納、配列、及び／または構成する手法に基づいて、データにアクセスしてそれを使用するナビゲーション応用プログラム内の機能は、地理データ内に組み込まれた改良を活用するルーチンを実現することができる。この組合せによって、ナビゲーションシステムの性能が総合的に改善される。
【００２７】
地図データベース４０は、地理領域内の道路網に関する情報を含む。一実施例では、地図データベース４０は、ノードデータ及びセグメントデータを含む。これらのデータは、物理的な道路網の成分を表している。ノードデータは地理領域内の物理的位置（例えば、道路の交差点、及び他の位置）を表し、セグメントデータはノードによって表される物理的位置の間の道路の部分を表す。地理領域内の各道路セグメントは、地図データベース４０内の道路セグメントデータエンティティ（即ち、レコード）によって表される。地図データベース４０内の各道路セグメントデータレコードは、道路セグメントデータレコードによって表される道路セグメントの各端における座標位置を表す２つのノードに関連している。ノード及びセグメントデータベースエンティティ内に含まれる情報を、図２及び３に関連して以下に説明する。（用語「ノード」及び「セグメント」は、これらの物理的な地理特色を記述する唯一の用語であり、これらの特色を記述する他の用語もこれらの概念の範囲内に包含されることを意図している。）
図２は、地理領域１１２を示す地図１１０である。複数の位置１１４が、地理領域１１２内に位置しているように示されている。各位置１１４は、地理データベース内に情報が含まれていることが望まれる特色が位置する地理領域１１２内の場所、または点を表している。これらの各位置１１４は個々の物理的位置（緯度、経度、及びオプションとして絶対または相対高度）を有し、各位置１１４はその二次元（または、三次元）地理座標（即ち、緯度、経度、及びオプションとして高度）によって個々に識別することができる。位置１１４は、２つまたはそれ以上の道路が出会う交差点、速度制限が変化する道路セグメントに沿う点、道路が行き止まりになる点、等々に対応させることができる。位置１１４は、ホテルまたは市民会館のような関心点の位置、湖のような自然特色の境界、または鉄道軌道またはフェリーに沿う位置に対応させることができる。位置１１４は、地理領域１１２内に物理的に位置する何かに対応させることができる。
【００２８】
図３は、地図１１０の一部分１１６の拡大図である。図３の部分１１６は、地理領域１１２内の道路網１２０の部分を示している。道路網１２０は、特に、地理領域１１１２内に位置する道路及び交差点を含んでいる。図３に地図１１０の部分１１６として示すように、地理領域１１２内の各道路は１つまたはそれ以上のセグメント１２２（１）、１２２（２）・・・１２２（ｎ）からなる。一実施例では、道路セグメントは、道路の一部分を表す。図３では、各道路セグメント１２２は、それに２つのノード１２３が関連付けられている。即ち、１つのノードが道路セグメントの一方の端における点を表し、他方のノードがその道路セグメントの他方の端における点を表している。道路セグメントの何れかの端におけるノードは、例えば交差点のようにその道路が別の道路と出会う位置、または道路の行き止まりの位置に対応させることができる。
【００２９】
地理データベースの１つの型においては、地理領域内に表されている各道路セグメント毎に、少なくとも１つのデータベースエンティティ（「エンティティ」とも「レコード」とも呼ぶ）が存在する。この道路セグメントデータレコードは、道路セグメントに関連するノード、及び／または２つのノードの地理的位置（例えば、緯度及び経度座標）を識別可能にする情報（「属性」、「フィールド」等のような）を、それに関連付けることができる。更に、道路セグメントレコードは、道路セグメントレコードによって表される道路の部分の走行速度、道路セグメントレコードによって表される道路部分上で許される走行方向、道路セグメントレコードによって表される道路部分の両端における交差点に対応する各ノードにどの転回禁止が存在するのか、道路セグメントレコードによって表される道路部分の街路番地範囲、道路名、等々を指定する情報（例えば、より多くの「属性」、「フィールド」等）をそれに関連付けることもできる。道路セグメントに関連するいろいろな属性は、単一の道路セグメントレコード内に含ませることができ、または好ましくは、互いに相互参照し合う１つの型より多い道路セグメントレコード内に含ませる。
【００３０】
地理領域１１２を表す地理データベースにおいては、地理領域内の各ノード毎にデータベースエントリ（エンティティまたはレコード）も存在することができる。ノードデータレコードは、それに接続されている１つまたは複数の道路セグメント、及び／またはその地理的位置（例えば、その緯度及び経度座標）を識別可能にする情報（「属性」、「フィールド」等のような）を、それに関連付けることができる。
【００３１】
Ｂ．地理データの分離したサブセット
いろいろなナビゲーション機能を遂行するために地理データのアクセスを強化することを可能にする１つの方法は、ナビゲーション応用プログラム１８内の各分離した機能（例えば、４１−４５）によって使用される地理データの分離した集まり、即ちサブセットを供給することである。これらの分離した各サブセットは、特に特定の１つまたはそれ以上の機能によって使用するように合わされる。例えば、ルート計算機能４１（図１）は、通常は、ある道路のあるセグメントに関連する地理データベース内の全ての情報の一部分しか使用しない。ルート計算機能４１が走っている時には、道路セグメントに沿う速度、１つの道路セグメントから別の道路セグメントへの転回禁止、等々のような情報を要求するかも知れない。しかしながら、ルート計算機能４１は、ルートを計算するためには必ずしも道路名は必要としない。同様に、地図表示機能４３を使用する場合、速度制限または転回禁止のような道路セグメントに関連する情報の若干は必要ない。代わりに、地図表示機能４３が走っている時には、道路の形状及び位置、及び多分道路名のような道路セグメントに関連する情報の一部分だけを使用する。また更に、ルート案内機能４２が走り始めても、速度及び転回禁止のような道路のセグメントに関連する若干の情報は要求しない。代わりに、ルート案内機能４２が走り始めると、この機能は、道路セグメントによって表される道路名、その道路セグメントに沿う番地範囲、その道路セグメントに沿う交通標識、等々を含む情報を使用する。さまざまなナビゲーション機能が使用する情報の型に関しては若干の重なりが存在し得るが、これらのナビゲーション機能の何れか１つが使用するデータの若干は、別の機能は使用しない。もし各道路セグメントに関する全ての情報が単一のデータベース内の単一のデータエントリに関連していれば、各データエンティティは比較的大きくなる。従って、ナビゲーション機能の何れか１つがエンティティレコードにアクセスすると、その機能は、殆どはそのナビゲーション機能が必要としないかなりな量の情報を、メモリ内に読み込まなければならない。更に、ディスクからデータエンティティを読み込む場合、各データエンティティが比較的大きいことから、一時に比較的僅かなデータエンティティしか読み込むことができない。
【００３２】
各ナビゲーション機能が使用するのにより効率的なフォーマットで地理データベース内の情報を提供するために、ナビゲーション応用プログラム１８内に供給される異なる型の各ナビゲーション機能毎に、所与の地理領域の地理データベース全体の分離したサブセットが供給される。
【００３３】
図４に、分離したルーティングデータ１３６、地図作成データ１３７（地図表示用）、運転データ１３８（ルート案内用）、関心点データ１３９（ホテル、レストラン、博物館、スタジアム、空港、等のような特定の関心点識別用）、及び合流点データ１４０（名前付き交差点識別用）からなる地理データベース４０を示す。これらの型のデータの他に、地理データベース４０は、ナビゲーション特色データ１４１、及び地図作成特色データ１４２を含むことができる。データのこれらのサブセットは、それぞれ、ナビゲーション特色（例えば、道路及び交差点）の名前、及び湖等のような走行できない特色を含む。地理データベースは、場所１４４（例えば、市、州、国）及び郵便番号１４３を含むこともできる。地理データベースは、これらより少ない、または多いサブセットを用いて限定することができ、他の型のデータ１４６を限定し、含ませることができる。
【００３４】
データの各サブセットは、特定のナビゲーション機能が使用するために要求するデータだけを含んでいる。これらの各サブセット間には若干の重なりが存在しており、その結果、情報の若干の部分が１つより多くのサブセット内に含まれることがあり得る。例えば、ルーティングデータサブセット１３６内の道路セグメントデータエンティティ、並びに地図作成データサブセット１３７内の道路セグメントデータエンティティが共に、セグメントの両端に位置するノードを識別する属性を含むことがあり得る。この重複によりデータ記憶要求は大きくなり得るが、より少量のデータを処理するという結果的な効率によって各ナビゲーション機能に利益がもたらされる。
【００３５】
各ナビゲーション機能毎に地理データの分離したサブセットを準備する場合、これらの各ナビゲーション機能の使用が他のナビゲーション機能に予測できるように関係することをも考えておく。例えば、エンドユーザは、先ず現在の位置を見たいと思い、次に目的地を入力し、次に目的地に向かってどのように出発するかの命令を受け、次にルートの始めの部分を示す地図を見て、さらなる命令を受け、ルートの次の部分を示す地図を表示させたいと思う、等々であろう。使用がこのように予測されるので、データをサブセットに分割すると、分離された各機能を使用する場合にデータの使用が効率的になる。
【００３６】
地理データをサブセットに分割すると、異なる各ナビゲーション機能によるデータの使用は効率的になるが、データベースのこれらの異なるサブセットを使用する異なるナビゲーティング機能を一緒に動作させることが必要になる。例えば上述した例では、計算されたルートをエンドユーザが入手した後に、計算されたルートをハイライトさせた地図をコンピュータディスプレイ上に表示させることが望ましいであろう。これを達成するために、先ず地理ディスプレイのルーティングサブセット１３６にアクセスして最適ルートのためのルーティング道路セグメントデータエンティティを入手し、次に地理データベースの地図作成サブセット１３７にアクセスしてそのルーティングデータエンティティに対応する地図作成道路セグメントデータエンティティを入手する。これらのデータサブセットを一緒に動作させることができるように、相互参照、探索木、または他のデータ見出し技術を提供する索引が含まれ得る。索引は、何れかのデータのサブセットの中に配置することも、または何れかのサブセットの外部に配置することもできる。図４には、外部索引１４７が示されている。索引されるデータの外部に索引を格納することは、いろいろなデータのサブセットの中のどのデータを次にロードする必要があるのかを決定するために、その索引をロードして使用することができるので有利である。
【００３７】
Ｃ．地理データの層化
地理データを編成してそれらの使用を強化することができる別の方策は、データを層で供給することである。地図表示機能及びルート計算機能のような若干のナビゲーション機能は、レベルが異なる細部のデータを使用することができる。例えば、地図表示機能を使用する場合、パンニングまたはズーミングを行うことが望ましい場合がある。ズーミングは、もしデータが層に編成され、低い層がより詳細に、高い層はそれ程詳細ではないようになっていれば、より効率的に行うことができる。同様に、ルート計算機能を使用する場合、レベルが異なる細部のデータを使用することも有利である。例えば、２つの位置間のルートを計算する時に、そのルートに沿う各交差点から分れる補助街路及び小道を含む全ての可能道路セグメントを調べることは非効率的である。その代わりとして、あるルートが主要道路または高速道路「上」に決定された場合には、一般に、目的地が近づいて補助道路へ出る必要を生ずるまでは主要道路または高速道路上に留まることが好ましい。もしルーティングデータが層になっていれば、可能ならば、ルートを計算する時に補助道路が省かれている高い層を使用し、検査すべき可能道路セグメントを最小にすることができる。従って、若干のデータ型のサブセット内では、地理データは分離した層に対応する分離した集まり、またはグループで供給される。
【００３８】
層化を実現するために、地図データベース４０内の各道路セグメントデータレコードは、それが表している道路の対応する部分のランクをも識別する。道路セグメントのランクは、その機能クラスに対応させることができる。ランク「４」の道路セグメントは、高速道路及びフリーウェイのような高ボリュームの、アクセスが制御されている道路を含むことができる。ランク「３」の道路セグメントは、少しの速度変化はあるが、必ずしもアクセスが制御されていない高ボリュームの道路であることができる。低くランク付けされた道路は対応する低ボリュームを取扱い、一般的に、より多くの速度変化またはより遅い速度を有している。ランク「０」の道路は、最低のボリュームを取り扱うことができる。例えば、これらの最低にランク付けされた道路は、横路、小道、等を含むことができる。
【００３９】
道路セグメントデータエンティティのランクは、道路セグメントエンティティが含まれている最高データ層をも指定する。例えば、図５に示すように、ルーティング型データ１３６は５つの分離したデータの層Ｒ０、Ｒ１、Ｒ２、Ｒ３、及びＲ４を含むことができる。各層は、ルート計算機能が使用できる異なるレベルの細部を有するルーティングデータの分離した集まりからなる。地理データベースのルーティングデータ型では、層０（“Ｒ０”）は「０」またはそれより高いランクを有する道路セグメントデータエンティティ（及びそれらの対応するルーティングデータ属性の若干、または全て）を含む。従って、層０は、地理領域内の全ての道路の全ての部分に対応する道路セグメントデータエンティティを含んでいる。ルーティングデータ１３６の層１は、ルーティングデータの分離したサブセット（即ち、集まり）からなり、「１」またはそれより高いランクを有するルーティングセグメントデータエンティティ（及びそれらの対応するルーティングデータ属性の若干、または全て）だけを含んでいる。ルーティングデータの層２は、ルーティングデータの分離したサブセット（即ち、集まり）からなり、レベル「２」またはそれより高いランクを有するルーティングセグメントデータエンティティ（及びそれらの対応するナビゲーションデータ属性の若干、または全て）だけを含んでいる、等々である。最高層（層ｎ）は、ｎのランクを有するレコードだけを含む。この実施例ではｎは４に等しく、他の実施例ではｎは０より大きいどのような数であることもできる。層が高い程含まれるレコードは少なくなるが、これらのレコードは一般的に高速で走行する道路を表している。
【００４０】
同様に、他の型のデータは、分離したデータの層を含むことができる。各層は異なるレベルの細部を含んでいる。例えば、地図表示機能４３によって使用される地図作成データ型１３７は、複数の層に供給することができる。異なる層の地図作成データを使用すると、地図表示機能４３は迅速なパンニング及びズーミングを提供することができる。
【００４１】
若干のデータを層に編成するとデータに若干の重複をもたらすことになるが、層化によって得られる効率の増加が、一般的に何等かの欠陥を相殺する。上述した分離した型のデータを使用する場合のように、これらの層を一緒に動作可能にする要望が生まれる。索引１４９を、この目的のために設けることができる。図５には内部索引１４９が示されている。内部索引１４９は、種々の型のデータの中に含まれている。外部索引も、この目的のために使用することができる。
【００４２】
Ｄ．地理データへの空間アクセス
データをサブセットまたは型に編成すると、ナビゲーション応用プログラム内の各ナビゲーション機能２９によってより管理可能なサイズの分離したデータの集まりが得られる。若干のサブセットの型については、空間アクセスを容易ならしめるようにデータを更に編成することができる。
【００４３】
ナビゲーション応用１８内のナビゲーション機能の若干（例えば、図１の４１、４２、４３、及び４４）は、地理データの空間的アクセス、または使用を生じ得る。これが発生する１つの場合は、ナビゲーション応用プログラム１８内のある機能が、地理領域内のデータエンティティによって表される物理的位置が与られている地理データベース４０内のデータエンティティレコードを見出すように要求する場合である。データエンティティは地理領域内の道路の一部分を表す道路セグメントレコードであることができ、機能は、道路セグメントレコードによって表される道路の部分の地理領域内の物理的位置に基づいて、道路セグメントレコードを見出すように要求することができる。データエンティティは、ナビゲーションシステムを搭載したビークルの現在位置に最も近いホテルを表す関心点レコードであることができる。空間アクセスが発生する別の場合は、ナビゲーション応用プログラム内のある機能が、地理領域内のある位置に近接して位置するか、またはその地理領域内のある限定された領域内の、ある型のデータレコードの若干、または全てを要求した時である。例えば、ある機能は緯度（ｘ，ｘ＋ｎ）及び経度（ｙ，ｙ＋ｍ）の地理座標によって限定される矩形内に含まれる全てのレストラン関心点レコードを要求することができる。
【００４４】
図４に戻って、地理データの主体の若干は空間的に編成されており、他のデータのサブセットは空間的以外の手法で編成されている。空間的に編成されたデータは、地理的に近接する特色を表すデータが、データセット４０内で、及び／または媒体３２上で、論理的に、及び／または物理的に近接して位置するように配列される。若干のナビゲーション応用機能の場合、それらのそれぞれのデータの空間編成は、密に関係している地理データをより迅速に媒体から読み出し、関係している地理データをメモリ内のそれらを使用することができる場所にロードできるようにする。この種類の編成は、記憶媒体３２のアクセスを最小にし、これらのナビゲーション機能の動作をスピードアップする。
【００４５】
空間的に編成された地理データ４０のサブセットは、ルート計算データ１３６、地図作成データ（地図表示）１３７、及び関心点データ１３９を含む。他の種類のデータも、空間的に編成することができる。空間的編成は、異なる手法でデータに適用することができる。例えば、空間的編成は、データの各レコードに適用することも、または複数のデータレコードのグルーピング（例えば、以下に説明するように、データのパーセル）に適用することもできる。
【００４６】
データのサブセットの若干は、空間的以外の手法で編成され、アクセスされる。例えばデータのサブセットの若干は、アルファベット順に、または市（シティー）、州（ステート）、及び国（カントリー）によって、等々で編成することができる。非空間的に編成されたデータは、合流点データ１４０、ナビゲーション特色データ１４１、地図作成特色データ１４２、郵便番号データ１４３、及び場所データ１４４を含む。他の型のデータも非空間的に編成することができる。
【００４７】
Ｅ．地理データのパーセル化
地理データを使用する時のナビゲーション応用プログラムの動作及び性能に影響し得る幾つかのファクタが存在する。合理的に高レベルの機能を得るために、比較的大きいデータベースを設けることができる。ＣＤ−ＲＯＭディスク、またはＰＣＭＣＩＡカードのような記憶媒体は、適当な機能を提供するのに充分なサイズ及び複雑さのデータベースを取扱うことができる。しかしながら、これらの型の媒体へのアクセスは、比較的遅くなり得る。ナビゲーションシステムはビークル内に設置することも、または手持ちであることもできるから、ナビゲーションシステムのハードウェア資源は制限され得る。ビークルに搭載されたナビゲーションシステム、または手持ちのユニットはメモリ資源が制限され、また媒体アクセスレートが比較的遅くなり得る。ナビゲーション応用が、より大きいメモリ及びハードウェア資源を有するプラットフォーム上に設けられている場合であっても、同じような、しかし異なるスケールで考察が適用される。
【００４８】
ナビゲーション応用プログラムが走っているナビゲーションシステムのメモリ資源が制限されているために、所与の地理領域全体のための全てのデータレコードをナビゲーションシステムのメモリ内に同時にロードできないものとすれば、所望の機能を遂行するのに必要なデータだけをロードすることが望ましい。これを達成するために、地理データベース４０内のデータはパーセルに編成される。データのパーセルは、媒体への１回のアクセスで一緒に入手されるデータレコードを含むように確立されている。これは、１回のディスクアクセスでアクセスできるデータの量に関係するが、他のあるファクタに関係付けることもできる。ＣＤ−ＲＯＭディスクのような若干の型の媒体の場合には、パーセルは 16 キロバイトのデータ量であるように確立することができる。（１Ｋ、２Ｋ、４Ｋ、８Ｋ、32Ｋ等を含む他のデータサイズも使用可能である。）
図６に示すように、データのパーセル２２０は、各パーセル２２０内のデータが論理的に、及び／または物理的に一緒にグループ化されてデータベース４０を形成するように格納される。データのパーセルがアクセスされる時、そのデータレコードの全てが同時に媒体からナビゲーションシステムのメモリ内に読み込まれる。データをパーセルに形成する前に、データは先ず異なる型（例えば、図４に示すように、ルーティング、地図作成、運転、等々）に別々に編成される。更に、層（例えば、ルーティング、地図作成）によって編成されているデータの型の場合、これらの型のデータは、パーセルに形成される前に層に別々に編成される（図５に示すように）。
【００４９】
（１）空間的に編成されたデータのパーセル化
データをパーセル化する場合、一般的には、ナビゲーション機能を遂行するためにアクセスして読み出さなければならないパーセルの数を最小にする手法で、データのパーセルを形成することが好ましい。前述したように、地理特色を表すデータを、特色の物理的接近を基として格納することが望ましい場合がある。空間的に編成されたデータについては、一般的に、特色（そのデータが表すか、またはそのデータが表す特色に地理的に接近している）の物理的な地理的位置を基として、データをメモリ内にロードする手段を設けることが有利である。これは、データを空間的にパーセル化することによって行われる。空間的にパーセル化されたデータは、地理的に近接している特色を表すデータが、データベース４０内で、及び／または媒体３２上で、論理的に、及び／または物理的に近接するように配列されている。若干のナビゲーション応用機能の場合、それらのそれぞれのデータの空間パーセル化は、密に関係している地理データをより迅速に媒体から読み出し、関係している地理データをメモリ内のそれらを使用することができる場所にロードできるようにする。この種類の編成は、記憶媒体３２のアクセスを最小にし、これらのナビゲーション機能の動作をスピードアップすることを可能にする。
【００５０】
地理データを空間的にパーセル化するために使用できる多くの異なる手順が存在している。例えば、簡単なパーセル化方法では、データが複数のパーセルに分離される。各パーセル内のデータは、一緒になって地理領域上に規則的な矩形格子を形成する複数の規則的なサイズの矩形の分離した１つの中に含まれる特色を表す。別の空間パーセル化方法は、パーセルサイズが最大しきい値以下になるまで、地理領域の部分を包含する矩形を等分して行くことによって各矩形を形成するように、データを矩形領域内に含まれるパーセルに分離する。更に、パーセル化手順が 1996 年10月25日付同時出願第 08/740,295 号に開示され、その全文が参照として本明細書に採り入れられており、またパーセル化手順が 1997 年９月５日付同時出願第 08/935,809 号に開示され、その全文が参照として本明細書に採り入れられている。本願に適用できる更に他のパーセル化方法は、米国特許第 4,888,698号及び第 4,937,572号に開示されている。
【００５１】
空間的に編成されたデータのパーセル化を、図７を参照して説明する。図７は先に図２に示した地理領域１１２の地図１１０を示している。複数の位置１１４（ドットまたは点によって表されている）が、地図１１０上に位置するように示されている。各位置１１４は地理領域１１２内の場所または点を表しており、この場所または点には、図１の地理データベース４０内に含まれる情報に関する特色が位置している。例えば、位置１１４は、地理データベース４０内のデータによって表される道路セグメントの端点、道路セグメントに沿う点、関心点（ホテル、市民会館等）等々の物理的位置に対応させることができる。これらの各位置１１４は独特の物理的位置（緯度、経度、及びオプションとして絶対、または相対高度）を有し、各位置１１４はその二次元（または、三次元）地理座標（即ち、緯度、経度、及びオプションとして絶対、または相対高度）によって独特に識別することができる。
【００５２】
図７では、地図１１０によって表されている地理領域１１２に格子２１７がオーバーレイされている。格子２１７は、地理領域１１２を複数の矩形領域２１９に分割している。格子２１７の格子線は、矩形領域２１９の境界を表す。これらの矩形領域２１９は、パーセル化のために使用する手順に依存して、同一のサイズであることも、または異なるサイズであることもできる。同様に、境界の位置は、使用するパーセル化手順に依存することもできる。一般的に言えば、空間パーセル化にどのような手順を使用しても、各矩形領域２１９内に含まれる特色を表す特定のデータの型のデータレコードは、分離したデータのパーセル内に一緒にグループ化される。再度図６を参照する。地理データベース４０のルーティングサブセット１３６を構成している道路セグメントレコード及びノードレコードのような複数のデータレコードは、グルーピング（即ち、パーセル２２０）に分離される。空間的に編成されたデータの場合には、図６のルーティングデータの各パーセル２２０は、図７に示す複数の矩形２１９の分離した１つ内に含まれる地理特色を表すデータレコードを含む。
【００５３】
図６に示すように、パーセル２２０は、各パーセル２２０内のデータが論理的に、及び／または物理的に一緒にグループ化されてデータベース４０を形成するように格納される。パーセルはナビゲーションシステムによって同時にアクセスされるデータベースレコードの量を表しているから、データのパーセルがアクセスされた時、そのデータレコードの全てが同時にナビゲーションシステムのメモリ内に読み込まれる。図７の地図１１０について言えば、これは各矩形２１９内に含まれる地理特色を表す空間的に編成されたデータの型の、セグメントレコードまたはノードレコードのような全てのデータレコードがグループとして一緒にアクセスされることを意味している。若干の種類のナビゲーション機能の場合には、地理領域内で互いに物理的に密接している特色を表している全てのデータレコードを同時にメモリ内に有することが望ましいことは理解できよう。
【００５４】
パーセル２２０がこれらのデータの型のために形成される際に、パーセルは順序付けされる。いろいろな型の順序付けを使用することができる。一般的に言えば、データの探索を最小にするような手法でパーセルを順序付けすることが好ましい。空間的に編成されたパーセルを順序付けする１方法は、各データの型内のｋｄ木から深さ優先順序付けを使用することである。これはペアノ( Peano ) キー順序付けに類似した順序付けである。パーセルは、この近似ペアノキー順序でディスク（即ち、図１の媒体３２）上に格納することができる。ｋｄ木のような１つまたはそれ以上の索引を使用して、空間的にパーセルをアクセスすることとができる。この索引は、ナビゲーションシステム内のプログラムが始めに現在のビークル位置に対応する地図データを探知する時のように、任意位置の初期探知にとって有用である。パーセル２２０を順序付した後に、各パーセルに独特のパーセル識別子（例えば、「パーセルＩＤ」）を割当てることもできる。パーセルＩＤは、パーセル及び／または媒体上のその位置を識別するために使用することができる。
【００５５】
（２）空間的に編成されていないデータのパーセル化
若干の種類のデータは、空間的に編成されていない。パーセル化は、これらの種類のデータにとっても利点を与えることができる。空間的に編成されていないデータの各パーセルは、必ずしも図７の矩形領域２１９の何れにも対応しない。例えば、街路及び交差点のような走行可能な特色の名前を表すナビゲーション特色データ１４１は、空間的にではなく、アルファベット順に編成することができる。また場所データ１４４は、空間的に編成されていないデータの種類の中にある。場所データ１４４は、行政階層によって編成されている。場所データ１４４は、政府または行政領域（例えば、国、市、州、郡（カウンティ）、郵便区（ゾーン）、居留地（セツルメント）、等々）を表すために使用される場所データレコードを含む。場所データ１４４は、データによって表される場所の行政レベルを斟酌した階層に編成されている。場所データレコードをこのような階層に編成した後に、それらはパーセル２２０（図６）に形成され、地理データベースを形成するように格納される。（場所データエンティティは空間的に編成されていないから、場所データの各パーセルは必ずしも図７の何れかの矩形領域２１９に対応しない。）
一実施例によれば、場所データは、行政階層に対応するレベルによって配列されている。レベル１場所データレコード（即ち、地理特色が地理データベース４０によって表される「国」に対応するデータレコード）は、場所データ１４４内の第１のものに含まれる。もし地理データベースによって１つより多い国（例えば、カナダと合衆国）を表すのであれば、「レベル１」レコードはアルファベット順に順序付けられている。
【００５６】
次に、地理特色が地理データベース４０によって表される全ての「レベル２」場所データレコード（即ち、合衆国における「州」、またはカナダにおける「プロビンス」に対応するデータレコード）が配列される。これらの場所レコードは、先ず、それらがその一部をなしている「レベル１」レコードによって表される国に従って順序付けされ、次いで、国による分類の後に、アルファベット順に分類される。従って、もし地理データベースがカナダ及び合衆国を含んでいれば、カナダのプロビンスを表す全ての場所データレコードが先ずアルファベット順に順序付けされ、次いで合衆国の州を表す全ての場所データレコードがアルファベット順に順序付けされている。（地理データベースが必ずしも全ての州または全てのプロビンスを含むことはないことに注目されたい。地理データベースによって表されるものだけが含まれているのである。）
次に、地理特色が地理データベース４０によって表される全ての「レベル３」場所データレコード（即ち、合衆国及びカナダにおける「郡」に対応するデータレコード）が配列される。これらの場所レコードは、先ず、それらがその一部をなしている「レベル２」レコードによって表される州（または、プロビンス）に従って順序付けされ、次いで、アルファベット順に順序付けされている。従って、もし地理データベースがイリノイ及びアイオワを含んでいれば、イリノイの郡を表す全ての場所データレコードが先ずアルファベット順に順序付けされ、次いでアイオワの郡を表す全ての場所データレコードがアルファベット順に順序付けされている。
【００５７】
最後に、地理特色が地理データベース４０によって表される全ての「レベル４」場所データレコード（即ち、合衆国及びカナダにおける「市」に対応するデータレコード）が配列される。これらの場所レコードは、先ず、それらがその一部をなしている「レベル２」レコードによって表される州（または、プロビンス）に従って順序付けされ、次いで、アルファベット順に順序付けされる。従って、もし地理データベースがイリノイ及びアイオワを含んでいれば、イリノイの市を表す全ての場所データレコードが先ずアルファベット順に順序付けされ、次いでアイオワの市を表す全ての場所データレコードがアルファベット順に順序付けされている。
【００５８】
上述した場所データのパーセル化は、これらのデータレコードを編成することができる１つの方法を示している。他の種類の編成も使用することができる。例えば、他の種類の階層的編成を、場所データのために使用することができる。代替として、場所データレコードは、関心点データのように空間的に編成することもできる。
【００５９】
Ｆ．パーセルの順序付け
全ての型のデータのために、及び各型の層の全てのためにパーセルが形成されると、それらのパーセルは順序付けされる。さまざまな型の順序付けを使用することができる。一般的に言えば、パーセルは、データの探索を最小にする手法で順序付けることが好ましい。ナビゲーション応用プログラム内の若干の機能においては、時には、地理領域の一部を横切るルートまたは経路に沿う特色を表すデータへのアクセス要求が存在する。これは、地理領域を横切るルートを計算する時に、またはその地理領域を横切ってパンニングする時に発生し得る。時には、これらのルートまたは経路は、１つより多い矩形（それらから場所データが形成される）にわたって伸びることがある。従って、１つのパーセルから出発して、そのパーセルを形成している矩形に隣接して位置する矩形から形成される別のパーセル内のデータにアクセスする必要がある。各矩形は、幾つかの他の矩形がそれに隣接しているから、探索を最小にするためには、これらの矩形によって形成されるパーセルを順序付けする必要がある。
【００６０】
パーセルを順序付けする１方法は、各パーセル型及び層内のｋｄ木索引から深さ優先順序付けを使用することである。これは、ペアノキー順序付けに類似した順序付けである。代替として、ペアノキー順序付けを使用することができる。このようにパーセルを順序付けすることにより、一般的に言えば、１つの矩形から隣接する矩形へ行く場合、その１つの矩形に対応するパーセルから隣接する矩形に対応するパーセルへ行く時に記憶媒体からデータを読み出す時のヘッドの移動距離が最小になる。一般的に言えば、これは、その地理領域内の隣接矩形に対応するパーセル内のデータを見出すためのシーク時間が最小になるという結果を有している。他のパーセル化手順によって形成されるパーセルも、同様に順序付けすることができる。
【００６１】
本質的に、パーセルは、それらが形成される順番に順序付けされる。これは、パーセルが作られる矩形を形成するために使用される分割を行う順番とは逆である。（ある実施例では、矩形を形成する時になされる分割の分割線毎に、分割線の東または北のデータの前に、分割線の西または南の全てのデータがパーセルに形成される。）
このように定義された各パーセルには、「パーセルＩＤ」が割当てられる。パーセルＩＤは、それによってパーセルを識別することができる識別（例えば、番号）であり、パーセル、またはその中に含まれている何等かのデータを検索する必要を生じた時に、そのパーセルを参照するために使用することができる。一実施例では、パーセルＩＤは、それらのパーセルが形成される順番と同一の順番で、及びそれらのパーセルのデータベース内の順番付けと同一の順番でパーセルに割当てられる。これは、媒体上のパーセルの位置を探知するために、データベースファイルの始まりのアドレスからのオフセットとして使用されるように、パーセルのサイズを知ってパーセルＩＤを選択できる長所を有している。
【００６２】
Ｇ．地理データベースの特色の使用
上述した特色の若干または全てを地理データベース内に実現し、その地理データベースを使用するナビゲーション応用プログラムの性能を改善することができる。これらの特色は、若干のナビゲーション機能を遂行するために、地理データベース内のデータへのアクセス、またはそのデータの使用を容易にするように地理データの部分を配列する、及び／または編成することによって、改善された性能を提供する。ナビゲーション応用プログラムが、地理データベースによって提供される性能強化用特色の若干、または全てから利益を得るようにするために、地理データベースを使用する、またはそれにアクセスするナビゲーション応用プログラム内のナビゲーション応用機能は、これらの機能を活用するように書かれている必要がある。
【００６３】
例えば、ルート計算機能４１（図１）は出発点と目的地位置との間の各交差点からの潜在的なルートを調べることによって、解ルートを計算することができる。ルート計算サブプログラムは、もし潜在的なルートの調査を、一般的により速い速度制限、及び／または最大容量を有する道路セグメントに制限することができれば、より早く解ルートを決定することができる。この種の制限された調査を提供するために、図５に関連して説明したように、地理データベースは層に編成することができる。ルーティングデータを層に編成する時に、より高くランク付けされた（そして一般的に言えば、より速い）道路は物理的に分離した集まり（即ち、層）に編成される。しかしながらより高い層は、一般的にはより高速であるが、一般的にはそれ程詳しくもなく、ルートの始まり部分、または終わり部分のようなルート計算プロセス全体を通して使用するには適切ではないかも知れない。
【００６４】
地理データベース４０内のルーティングデータ１３６のこの層化配列特色を利用するために、ルート計算サブプログラム４１は、ルート計算プロセスの種々の段においてルーティングデータ１３６のどの層を使用すべきかを決定する適切な命令、またはルーチンを含むことができる。ルート計算機能４１は、いろいろなファクタに基づいてルート計算プロセスのどの段においてどの層を使用すべきかを決定する適当な論理、またはアルゴリズムであることができる。次いで、適切な層の決定に依存して、ルート計算機能４１（または、ルート計算プログラム内の別のサブプログラム）は適切な機能を呼出し、または命令して、どの層からルーティングデータを検索すべきかを指示する。従って、ルート計算サブプログラム内の論理、またはアルゴリズムに、ルーティングデータ１３６の層化の利点を利用させるために、ルーティングデータ内の異なる層の数、及び各層内の細部のレベルを考える必要があり得る。
【００６５】
ナビゲーション応用内の他のサブプログラムも、考慮中の地理データの特色と共に準備する必要があり得る。例えば、地理領域の特定の区分をディスプレイ画面上に表示するためには、ナビゲーション応用プログラム内の機能は、表示することが望まれたその地理領域の地理座標を、その地理領域を表すために必要な地図作成データを含むパーセルの識別に変換できる必要がある。地図作成データを含む媒体上のパーセルの識別は、地理データベースの一部として設けられる索引を使用して、空間座標をパーセルの識別に変換するのを容易ならしめるインタフェース層機能のライブラリによって供給することができる。
【００６６】
III.  地理データベースのデータ圧縮
Ａ．概要
一実施例によれば、データ圧縮方法が開示される。データ圧縮方法は、データの集まり、即ちストリームを圧縮するために使用することができる。以下に開示するデータ圧縮方法は、いろいろな種類のデータに使用することができる。
【００６７】
この開示の一面によれば、データ圧縮方法は、地理データベースの圧縮されたバージョンを形成するために、地理データベースに適用される。地理データベースのこの圧縮されたバージョンは、物理的媒体上に格納することができる。このようなデータ圧縮を使用すると、ＣＤ−ＲＯＭディスク、ＤＶＤディスク、または将来開発される別の型の媒体のような媒体は、圧縮せずに含むことができるよりも大きいカバレッジエリアを表す地理データベースを含むことができる。代替として、このようなデータ圧縮を使用すると、記憶媒体は、所与のカバレッジエリアに対してより多くの細部（即ち、より多くのデータ）を含むことができる。別の代替では、以下に開示するデータ圧縮を使用すると、データ記憶媒体は、地理データベースを補足する付加的な種類のデータを含むことができる。これらの付加的な種類のデータは、レストラン案内、グラフィックデータ、オーディオデータ等を含むことができる。データ圧縮を使用すると、ナビゲーション機能を遂行するのに必要な全てのデータを入手するために要求される媒体アクセスの数が減少するので、ナビゲーションシステムの性能も改善される。
【００６８】
以下に説明する実施例によれば、データ圧縮は、地理データベース内に組み入れることができ、またナビゲーション応用機能の性能を強化する上述した特色と矛盾しない手法で、地理データベースを格納するために使用される。即ち、以下に説明するデータ圧縮例を使用すると、より多くの地理データを媒体上に格納することができながら、地理データベース内のデータを使用するナビゲーション応用プログラム内の機能によるデータへのアクセス及びデータの使用を容易ならしめる地理データベース内の特色の若干、または全てを実現し続ける。例えば、データ圧縮を地理データベース内に使用しても、型による地理データの編成は維持される。またデータ圧縮を使用しても、若干の型の層への地理データの編成は維持される。更にデータ圧縮を使用しても、比較的高い充填率を有する地理データのパーセルへの編成が維持される。一実施例によれば、データ圧縮は、ナビゲーション機能のために地理データベースへのアクセス、及び地理データベースの使用を強化するために地理データベース内に組み込まれている他の特色、及び技術の何れか、または全てと共に使用される。
【００６９】
一つの好ましい実施例によれば、地理データの圧縮、及び圧縮解除は、地理データへアクセスし、使用するナビゲーション応用プログラム機能（例えば、図１のルート計算機能４１、ルート案内機能４２、地図表示機能４３、ビークル測位機能４４、及び他の何等かのナビゲーション機能４５）には透過である。この長所を得る一つの方法は、地理データの圧縮解除を遂行する分離した圧縮解除機能を含ませることである。圧縮解除機能は、分離した機能としてナビゲーション応用プログラム内に含ませ、地理データベースへアクセスし、使用するナビゲーション応用プログラム内の残余の機能から独立して動作させるることができる。圧縮解除機能は、地理データベースが媒体から読み出される時点に動作し、地理データをそれらが物理的媒体内に格納されている圧縮されたフォーマットから圧縮解除する。次いで、圧縮解除機能は、地理データを圧縮解除された形状で他の機能（これらの機能は、もし地理データが圧縮解除されていれば、地理データを操作する）へ供給する。このような手法でデータの圧縮を実現する利点は、地理データに対してデータ圧縮が適用されていることを考慮するための何等の変更も施さずに、地理データベースを使用し続けることができることである。この種の実現のさらなる利点は、それが必要になった時に限って実行されるように圧縮解除機能を構成できることである。若干のナビゲーションシステムは、地理データベースが格納されている媒体を変化させることができる（例えば、更新したり、異なるカバレッジエリアのための地理データベースを設置したりする目的で）から、初期化時に、圧縮解除機能は媒体上の地理データベース内のデータの若干、または全てが圧縮さていることを検出した時に限って実行される。
【００７０】
圧縮解除機能は、物理的媒体から地理データを検索し、地理データを使用するナビゲーション応用機能へその地理データを戻すために使用されるデータアクセス機能のライブラリの中に含ませることができる。これらのデータアクセス機能のライブラリの例は 1996 年10月25日付で同時出願された第 08/740,298 号に開示されており、本明細書にはその全開示が参照として採り入れられている。このようにして実現すると、圧縮解除機能が、地理データを使用するナビゲーション機能（例えば、図１の４１、４２、４３、４４、４５）から分離される。圧縮解除機能を、地理データを使用するナビゲーション機能から分離することはできるが、圧縮解除機能は、媒体からの地理データへアクセスする他の機能と共に、そのデータを使用するナビゲーション機能とリンクさせて、単一の実行可能プログラムを形成することができる。
【００７１】
Ｂ．圧縮された地理データの型
一実施例によれば、地理データベース内の全てのデータは、以下に説明する１つまたはそれ以上の圧縮技術を使用して圧縮される。代替実施例においては、若干の型の地理データだけが圧縮され、残余の型の地理データは圧縮されない。例えば、図４をにおいて、ルーティングデータ１３６及び地図作成データ３７は圧縮された形状で媒体上に格納することができ、関心点データ１３９及び場所データ１４４は圧縮されない形状で媒体上に格納することができる。更に別の代替によれば、若干の型のデータは、以下に説明する全ての圧縮技術を使用して圧縮された形状で格納することができ、他の型のデータは若干の圧縮技術だけを使用して圧縮された形状で格納することができる。更に別の代替によれば、若干の型の地理データは以下に説明する圧縮技術の若干または全てを使用して圧縮され、他の型の地理データは、従来の圧縮技術を含む異なる型の圧縮技術を使用して圧縮される。
【００７２】
Ｃ．データ圧縮例
圧縮された地理データベースの一実施例では、従来からのハフマン及びＬＺ型置換圧縮に似た圧縮技術が使用されている。しかしながら、地理データベースをこれらの従来の技術とは異なる手法で圧縮される。これらの差は、以下の説明から理解されるであろう。
【００７３】
従来のハフマン圧縮では、最も頻繁に出現するのはどの記号（例えば、バイト）かを決定するために、圧縮されるデータの集まり（または、ストリーム）を調べる。次いで、元のデータストリーム内の記号が可変長のコードによって置換される。最も頻繁に出現する記号を表すために、最短コードが使用される。
【００７４】
ＬＺデータ圧縮は、置換圧縮の型である。ＬＺデータ圧縮は、幾つかのバリエーションを有している。１つの種類のＬＺ圧縮では、ストリーム内で一致するデータ記号のサブストリングを見出すために、データの集まり（または、ストリーム）を調べる。データ記号のサブストリングと、データ記号の先行サブストリングとが一致すると、そのサブストリングは先行ストリングの位置を指示するコード、及び先行ストリングの長さの指示に置換される。
【００７５】
Ｄ．置換（ＬＺ型）コード化実施例
限定するものではないが、上述した方法に従って形成された地理データベースのような圧縮されていない地理データベースの実施例では、一致するデータのサブストリングが比較的屡々出現することを発見した。更に、圧縮されていない地理データベースの実施例では、これらの一致するサブストリングが主として局所的に出現することも発見した。例えば、ルーティングデータ１３６（図４）においては、セグメントデータレコード内のデータのサブストリングは、比較的近くに位置している他のセグメントデータレコードと一致することが見出される。何故このようになるのかの理由の一部は、地理データの若干、または全ての特性に関係があるかも知れない。または、何故このようになるのかの理由の一部は、ナビゲーション応用プログラムによる使用及びアクセスを容易にするための、地理データの若干、または全ての編成方法に関係があるかも知れない。例えば、空間的にパーセル化されたデータの各パーセルは、地理領域内に分離して限定された矩形領域の境界内に包含される物理的特色を表すデータレコードを含んでいる。互いに密接して位置する物理的特色は、類似の属性を有することができる。そこで、互いに比較的密接する物理的特色を表すデータレコードは、類似のデータのサブストリングを有することができると言える。他のファクタもこれらの特性に貢献し得る。
【００７６】
例えば、南北に走る道路の連続するセグメントを表している４つのセグメントデータレコードを考えよう。これらの各セグメントレコードは、表される道路セグメントの端点の地理座標を含むデータフィールド（または、類似のデータ構造）を含むことができる。これらの各道路セグメントの端点を含むこれらの道路セグメントに沿う全ての点は同一の経度を有しているから、これらの各セグメントレコード内の端点のデータフィールドは同一のデータのストリングを含む。同様に、もしこれら４つの道路セグメントに沿う速度制限が同一であれば、これらの速度制限を表す４つの各道路セグメントレコード内のデータフィールドは全て、同一のデータのストリングを含むことになる。これらの道路セグメントは地理領域内で互いに隣接しているから、これら４つの道路セグメントを表す空間的にパーセル化されたルーティングデータは、データ記憶媒体上の地理データベース内の同一パーセル内に位置し（但し、あるパーセル境界が４つの道路セグメントを横切る場合を除く）、それによってこれら４つのデータレコードは地理データベース内で互いに比較的密接することになる。
【００７７】
別の例では、運転データ１３８（図４）において、道路の連続するセグメントを表すデータレコードは、同一の街路名を有することができる。たとえ、道路セグメントの名前の実際のテキストストリングを含むデータが地理データベースの別の部分に（例えば、ナビゲーション特色型のデータ１４１内に）位置していようとも、運転データ１３８内の各セグメントデータレコードは、表されている道路セグメントの名前のテキストストリングを含む走行可能な特色データ型１４１内のデータレコードへの参照（または、そのパーセル内のアレイへのポインタ
0004394763.tif 000002
【００７８】
ポインタ自体が参照になる）を含むことができる。運転データ１３８は空間的にパーセル化されるから、運転データ１３８内のこれら４つの道路セグメントレコード（これらは全て同一街路名を参照するデータを含む）も地理データベース内で互いに比較的密接することになる。
【００７９】
以上の説明で示唆したように、ナビゲーション特色の若干の性能を強化するために使用される技術の若干は、その地理領域内で互いに物理的に密接している地理的特色を表すデータレコードと地理データベース内で接近させられる傾向がある。地理領域内で互いに物理的に比較的密接している地理的特色は、地理データベース内のデータベースのサブストリングによって表される若干の属性を共有することができるるので、これらの性能強化技術を使用して形成される地理データベースは、互いに比較的密接する同一のデータのサブストリングを有することができる。
【００８０】
圧縮されていない地理データベース内の地理データの中では一致するサブストリングが比較的頻繁に出現し得るから、ある型の置換圧縮が使用される。地理データ内の第１の位置の地理データのサブストリングと、別の先行サブストリングとが一致する場合には、第１の位置のサブストリングは置換コードで置換することができる。置換コードは、地理データ内の先行サブストリングの位置の指示を含んでいる。一実施例によれば、置換コードに使用された指示は、置換を行った位置（即ち、サブストリングが置換コードによって置換された位置）から、一致する先行サブストリングが出現した位置までの逆向きのオフセットである。置換コードは、一致するサブストリングのサイズをも含んでいる。この置換を、図８に示してある。
【００８１】
（この説明の目的から、地理データベースを形成する圧縮されていないデータは、それらが型及び層によって順序付けらるにつれて、地理データの圧縮されていないストリームまたは集まりを構成して行く。データが位置している地理データストリーム内の任意の位置を表すために、データストリーム内の第１の（即ち、現在の）位置を用いる。第１の位置からのデータストリーム内の位置を表すために、第１の位置のデータに現在アクセスしている何等かの手段が、それより先にアクセスしたデータの位置を「先行」位置という。）
置換コード内のオフセットは、ある範囲内の値に定義される数である。この範囲は、そのオフセットを表すためにどれ程多くのビットが使用されるかによって決定される。あるオフセットのための値の許容範囲は、一致するサブストリングを探知できるまでに現在位置からどれだけ戻るのかを決定する。一実施例では、オフセットのために８ビット数を使用しているので、オフセットのための値の範囲は１−256 である。もしオフセットのために８ビット数が使用されれば（そして、もし“１”までの小さいオフセットが許容されれば）、一致するサブストリングは現在位置から 256文字より多く戻って探知することはできない。これは、一致するサブストリングを探索する時に、現在の位置の直前の 256文字だけしか一致を調べないことを暗示している。（これは、“１”までの小さいオフセットが許容されるものとしている。代替実施例では、“１”までの小さいオフセットが許容されないことが好ましいかも知れない。例えば、もし最小の一致するサブストリング長さを４文字であると定義すれば、“４”より小さいオフセットは存在せず、従ってオフセットの８ビットは４− 260の範囲を定義するのに使用することができる。）
オフセットは、より大きい、またはより小さい範囲の値を有するように定義することができる。より大きい範囲の値であれば、現在の位置の文字のサブストリングと一致するサブストリングを見出すために、より多くの先行文字ストリングを調べることができる。例えば、もしオフセットのために９ビット数を使用すれば、一致するサブストリングを見出すために 512の直前の文字を調べることができる（オフセットを“１”まで小さくすることができるものとする）。異なる範囲の値のオフセットを、地理データベース内の異なるデータ型に対して使用することができる。例えば、８ビット数をルーティングデータのオフセットのために使用し、９ビット数を運転データのオフセットのために使用することができる。一実施例では、オフセットは異なる型のデータのために構成可能であることができる。一実施例では、オフセットは 12 ビット（即ち、 4096 ）までにすることができる。代替実施例では、より大きい数を使用することができる。
【００８２】
前述したように、一致するストリングのための最小長さを確立しておくことが好ましいかも知れない。例えば、あるデータストリーム内のある位置における置換に関して評価されるサブストリングは、長さが少なくとも３、４、５、またはそれ以上の文字であることを確認した後に、それを、先に出現した一致するサブストリングを参照する置換コードによって置換するための潜在的候補であると考えるようにする。比較的短いサブストリング（例えば、長さが１または２文字しかないサブストリング）を置換コードで置換することを回避するために、一致するサブストリングの最小長さが設けられる。比較的短いサブストリングを置換しても、総合データ圧縮便益（もしあるとしても）に殆ど利することはない。好ましい実施例では、マッチングサブストリングの最小長さは、異なるデータ型に対して異なる値に構成することができる。例えば、ルーティングデータは１つの値の最小サブストリング長さを有し、地図作成データは別の値の最小サブストリング長さを有することができる。最小サブストリングは、データを圧縮するプログラムによって自動的に決定することができる。
【００８３】
Ｅ．ランレングスカウント
置換コードを使用して文字のストリングを置換すると、データの集まり、特に地理データベース上に格納される地理データをかなり圧縮することができる。置換コードをデータの集まり内に挿入してデータのストリングを置換する場合、置換コードである圧縮されたデータ内の文字と、置換コードによって置換されていない残余のデータとを区別するためにある方法が使用される。圧縮されたデータの集まり内の各文字に近接して（その前に、または代替として、その後に）あるコードを挿入し、その近接する文字が置換コードであるのか、または置換されない（即ち、「リテラル」）データであるのかを指示させることができる。例えば、単一のビット（以下に、「ＬＺ／リテラルフラグ」という）をこの目的のために使用することができる。この例によれば、もしデータの集まり内のある文字に先行するＬＺ／リテラルフラグが“０”であれば、このデータ文字は非置換（即ち「リテラル」）データである。一方、もしデータの集まり内の文字に先行するＬＺ／リテラルフラグが“１”であれば、このデータ実施例は置換コードの一部である。（勿論、０及び１を逆に使用することもできる。）
文字を置換コードであるのか、または非置換（即ち、「リテラル」）データであるのかを理解するように指示するために、圧縮されたデータの集まり内の各文字に関連付けられたコードを使用する代わりに、ランレングスカウントを使用することができる。ランレングスカウントを使用すると、その文字が置換コードであるのか、または非置換（「リテラル」）データであるのかを指示するコードをデータの集まり内の各文字に先行させる必要はなくなる。ランレングスカウントは、潜在的に総合データ記憶要求をも減少させる。ランレングスカウントを使用するために、ランレングスカウントコードが非置換コードの各ストリングの始まりに挿入される。ランレングスカウントコードは、そのランレングスコードが位置する位置から始まるリテラル文字、即ち置換コードではないデータの集まり内の連続文字の数に対応する数である。一実施例では、隣接する文字がリテラルであることを指示するＬＺ／リテラルコード（即ち、“０”にセットされている１ビット）がランレングスカウントに関連付けられているが、そのランレングスカウントに続くその後のリテラル文字からは省かれている。
【００８４】
ランレングスカウントは、ある範囲の値を有するように定義されている。一実施例では、ランレングスカウントは７ビットである。これにより、ランレングスカウントを、１乃至 128のその後の連続リテラル文字の数に定義することができる。この範囲は、一致するサブストリングが互いに比較的密接して現れることが予測されるようなデータの集まりにとって充分である。もしランレングスカウントの値をより大きい範囲にすることを望むのであれば、ランレングスカウントにより大きいビット数を使用することができる。また、もし長さが 128文字よりも大きい連続リテラルのストリングが出現すれば、１つより大きいランレングスカウントを使用することができる。例えば、200 連続リテラルのストリングが見込まれる場合には、128 の長さを有するリテラルのストリングが後続することを指示する第１のランレングスカウントをストリングの始まりに挿入し、 72 の長さを有するリテラルのストリングが後続することを指示する第２のランレングスカウントを 128番目のリテラル文字の後に挿入することができる。
【００８５】
代替実施例では、ランレングスカウントは、より小さい範囲の値（即ち、７ビットより少ない）であるように定義することができる。
【００８６】
Ｆ．置換コード及びランレングスのコード化
一実施例では、各置換コード毎に２バイト（直後のデータが置換コードであることを指示するＬＺ／リテラル１ビットフラグを含む）が使用され、リテラルランレングスカウントのために１バイト（データが置換コードではないことを指示するＬＺ／リテラル１ビットフラグを含む）が使用される。図９Ａ及び９Ｂに、これらのコードの成分を示す。図９Ａに示すリテラルランレングスカウントのために使用される１バイトは、１ビットのＬＺ／リテラルフラグを含む（これがセットされていると、リテラルが後続することを指示する）。このバイトの残余の７ビットが、ランレングスカウント自体のために使用される。図９Ｂに示す置換コードのために使用される２バイトは、１ビットのＬＺ／リテラルフラグを含む（これがセットされていると、置換コードが後続することを指示する）。これらのバイトの残余の 15 ビットは置換コードのオフセット及び一致の長さのために使用される。これらの 15 ビットは、オフセット及び一致の長さの間に割当てるように構成可能である。もし８ビットをオフセットのために使用すれば、残りの７ビットを一致の長さのために使用することができる。
【００８７】
オフセットを構成するビットは、置換コードのために使用される２バイトの間に分割することができる。オフセットの７つの上位ビットは、ＬＺ／リテラルフラグのために使用される１ビットと共に第１のバイト内に含まれる。オフセットの残余の（下位）ビット（もしあるならば）は、一致の長さのために使用されるビットと共に第２のバイト内に含まれる。もしオフセットのために８ビットが使用されていれば、これらのビットの上位７ビットは図９Ｂの第１のバイト内に含まれ、オフセットの下位１ビットは、一致の長さのために使用される７ビットと共に第２のバイト内に含まれる。前述したように、７ビットの一致の長さはルーティングデータに使用され、６ビットの一致の長さは運転データに使用される。一致の長さとオフセットとの間のビットの割当ては、ある型のデータに最良圧縮を与える割当てを決定するように変化させることができる。
【００８８】
Ｇ．ハフマンコード化
連続リテラル（非置換コード）文字の長さを指示するために、一致する先行サブストリング及びランレングスカウントを参照するように地理データベース内の複数の位置に挿入される置換コードの使用に加えて、ハフマンコード化によって地理データベースが占める格納の量を更に減少させることができる。一実施例では、地理データベース内の置換コード、ランレングスカウント、及び非置換データはハフマンコード化される。
【００８９】
ハフマンコード化は、コード化されるデータが最小ランダムである場合、即ち若干のデータアイテムが他のデータアイテムよりもかなり高い頻度で出現する場合に最良の圧縮を呈する。従って、最小ランダムネスを呈するデータの全体の集まりの部分を識別し、次いで、これらの部分を他の部分とは分離してコード化することによってより良い圧縮を得ることができる。一実施例では、地理データベース内の置換コード（特に、オフセット及び一致の長さ）、ランレングスカウント、及び非置換データベースの圧縮は、最も屡々出現する値について別々に解析される。次いで、別々のハフマン木を使用してこれらの各成分を別々にコード化する。
【００９０】
前述したように、各置換コードは２つの成分、即ちオフセット部分及び一致の長さ（即ち、一致するサブストリングの長さ）部分を含んでいる。オフセット部分に関して言えば、一致するデータのサブストリングが地理データベース内で互いに比較的密接し易いことも説明した。この傾向は、特に、例えば図４のルーティング１３６、地図作成１３７、運転１３８、等々のような各型のデータ内で発生することが予測される。従って、置換コード内のオフセットは、それらのそれぞれの置換コードが位置する位置に比較的密接する位置を指し示している傾向があることが予測される。オフセットのために定義された値の範囲を与えれば、そのオフセットがそれらの値範囲の下端付近にクラスタ化することが予測される。多くのオフセットがその範囲内で比較的小さい数であることが予測されるので、このことからも出現が予測される。従って、その範囲内の小さい数が、大きい数よりも屡々出現することが見込まれ、同じ小さい数が繰り返し出現することが見込まれる。
【００９１】
オフセット（特に、それらの上側の最上位ビット）が、定義された範囲の値内でランダム分布を呈することは予測されないので、オフセット値に対してデータ圧縮を使用し、それによってオフセットに関する総合データ格納サイズ要求を減少させることができる。ハフマンコード化をこの目的のために使用することができる。オフセットは圧縮されるデータの各型毎に決定されるので、どのオフセットが最も屡々出現するかを決定するためにオフセットが調べられる。前述したように、一致するサブストリングは互いに比較的密接して位置していることが予測されるので、小さい数のオフセットが大きい数のオフセットよりも屡々出現することが予測される。
【００９２】
（オフセットのハフマンコード化を再度参照する。ハフマン型のコード化をオフセットに使用することができる幾つかの代替方法が存在する。例えば、オフセットの値全体を統計的に解析し、ハフマンコード化することができる。代替として、最上位ビットだけのように、オフセットの一部分だけを統計的に解析し、ハフマンコード化することができる。更に、異なる型の地理データのためのオフセットを別々にハフマンコード化することができる。例えば、ルーティングデータにおいてはオフセットの最上位ビットだけをハフマンコード化し、地図作成データにおいてはオフセットの全てのビットをハフマンコード化することができる。同様に、ある型のデータの部分を、別々にハフマンコード化することができる。例えば、ルーティングデータの若干のパーセルに関してはオフセットの最上位ビットだけをハフマンコード化し、ルーティングデータの他のパーセルにおいてはオフセットの全てのビットをハフマンコード化することができる。オフセットの一部分だけが統計的に解析され、ハフマンコード化されるような一実施例では、コード化されていないオフセットの残余の部分を、オフセットの最上位ビットのためのハフマンコードの後のビットストリーム内に、圧縮されていない形状で挿入することができる。）
置換コードの他の成分は、一致の長さ部分である。この成分は、置換コードの位置において元の文字ストリングを置換した一致するサブストリングのサイズ（即ち、長さ）を識別する。また一致するサブストリングのサイズの値が、置換コードのこの成分に関して定義された値の範囲内、特にある型のデータ内でランダム分布を呈するとは考えられない。従って、置換コードの一致の長さ成分は、ハフマンコード化を使用して一致の長さの値をコード化することによって圧縮することができる。ハフマン統計アナライザを使用すると、一致の長さの全ての値が解析され、どの一致の長さがより屡々出現し、どの一致の長さの出現が少ないかが決定される。
【００９３】
同様に、ランレングスカウントを圧縮することができる。ランレングスカウントは、その後のリテラル文字の数を識別する。置換コードの成分と同様、これらのコードはハフマン統計アナライザを使用してそれらをコード化することによって圧縮することができる。ランレングスカウントのサイズの全ての値が解析され、どのランレングスカウント値がより屡々出現し、どのランレングスカウント値の出現が少ないかが決定される。
【００９４】
最後に、リテラル文字自体は、ハフマン統計アナライザを使用してそれらをコード化することによって圧縮することができる。リテラル文字は、典型的には、値があるクラスタ化を呈する。各型のデータ内に出現する全てのリテラル文字が解析され、どのリテラル文字ががより屡々出現し、どのリテラル文字の出現が少ないかが決定される。（オフセットの一部だけを統計的に解析し、ハフマンコード化する上述した実施例では、コード化されないオフセットの残余の部分は、オフセットの最上位ビットのためのハフマンコードと、一致の長さのためのハフマンコードとの間のビットストリーム内に圧縮されていない形状で挿入することができる。）
Ｈ．ハフマン木の構築
一実施例では、置換コード内のオフセット長さ（上述したように、その全て、またはその最上位ビットだけのようにその一部分だけ）及び一致の長さ、ランレングスカウント、及びリテラル文字自体は別々にコード化される。データのこれらの成分は、３つのハフマン木を使用してコード化される。地理データベースのこれらの面をコード化するための１つの特定例を以下に説明する。
【００９５】
先ず、地理データベース内の非置換データ（即ち、「リテラル」）が統計的に解析され、最も屡々出現する文字が決定された後に、最も屡々出現するリテラル文字と最短ハフマンコードとを関連付けるハフマン木が構築される。この木を使用し、リテラル文字は、それらに関連付けられたハフマンコードを使用して置換される。この木は圧縮されたデータベースと共に格納することができるので、ナビゲーション応用がデータベースを必要とする時に、このハフマン木を使用してハフマンコードから元のデータ文字を復元することができる。例えば、ルーティング１３６、地図作成１３７、運転１３８、等々のような各型のデータ内のリテラル文字は別々にコード化することができる。
【００９６】
次に、前述したように、ランレングスカウントを統計的に解析し、最も頻繁に出現するランレングスカウントの値を決定することができる。詳しく述べると、図９Ａに示すＬＺ／リテラルビットフラグを含むランレングスカウントが解析され、ＬＺ／リテラルビットフラグ及びランレングスカウントのこの組合せについて最も屡々出現する値が決定される。ランレングスカウントは、リテラル文字が呈するクラスタ化とは異なる値のクラスタ化を呈することが予測されるので、ランレングスカウントのための統計的解析は、リテラル文字の統計的解析とは別に遂行される。また、各型のデータは明確に値のクラスタ化を呈するので、ランレングスカウントのための統計的解析は各型のデータ毎に別々に行うことができる。各型のデータを別々に解析することによって、より良い圧縮を得ることができる。
【００９７】
最も屡々出現するランレングスカウント値と、最短ハフマンコードとを関連付ける別のハフマン木が構築される。この木を使用し、ランレングスカウント（ＬＺ／リテラルビットフラグを含む）は、それらに関連付けられたハフマンコードを使用して置換される。この第２の木はデータベースと共に格納することができるので、データベースを使用することが要求された時、元のランレングス値をハフマンコードから復元することができる。
【００９８】
これもまた前述したように、置換コードのオフセット部分は統計的に解析されて最も頻繁に出現するオフセットの値が決定される。詳しく述べると、図９Ｂに示すＬＺ／リテラルビットフラグ、及びオフセットの上位ビットを含む置換コードの第１バイトが解析され、この組合せについて最も屡々出現する値が決定される。オフセットコードは、リテラル文字及びランレングスカウントが呈するクラスタ化とは異なる値のクラスタ化を呈することが予測されるので、オフセットコード（即ち、ＬＺ／リテラルビットフラグ、及びオフセットの上位ビット）のための統計的解析は、リテラル文字またはランレングスカウントの統計的解析とは別に遂行される。
【００９９】
ランレングスカウント（より詳しく言えば、ＬＺ／リテラルビットフラグを含むランレングスカウント）のために使用した同じハフマン木が、オフセットコード（より詳しく言えば、ＬＺ／リテラルビットフラグ、及びオフセットの上位ビット）のために使用される。オフセットコード（より詳しく言えば、ＬＺ／リテラルビットフラグ、及びオフセットの上位ビット）の最も屡々出現する値は、最短ハフマンコードに関連付けられる。次いで、この木を使用し、オフセットコード（より詳しく言えば、ＬＺ／リテラルビットフラグ、及びオフセットの上位ビット）がそれらに関連付けられたハフマンコードを使用して置換される。この木は圧縮されたデータベースと共に格納され、ナビゲーション応用がデータの使用を要求した時に、オフセットコードを復元するために使用される。
【０１００】
最後に、前述したように置換コードの一致の長さ部分が統計的に解析され、最も屡々出現する一致の長さの値が決定される。詳述すれば、図９Ｂに示すようにオフセットの下位ビット、及び一致の長さを含む置換コードの第２バイトが解析され、コードのこの組合せについて最も屡々出現する値が決定される。一致の長さコードはデータの他の成分とは異なる値のクラスタ化を呈し得るので、一致の長さコード（より詳しく言えば、オフセットの下位ビット、及び一致の長さ）の統計的解析がリテラル文字、ランレングスカウント、またはＬＺ／リテラルビットフラグ及びオフセットの上位ビットの統計的解析とは別に遂行される。
【０１０１】
置換コード（より詳しく言えば、一致の長さ、及びオフセットの下位ビット）の一致の長さ部分の最も屡々出現する値と、最短ハフマンコードとを関連付ける第３のハフマン木が構築される。この木を使用し、置換コード（より詳しく言えば、オフセットの下位ビット、及び一致の長さ）の一致の長さ部分が、それらを関連付けたハフマンコードを使用して置換される。この第３の木はデータベースと共に格納されるので、一致の長さ値をハフマンコードから復元することができる。
【０１０２】
前述したように、各型のデータ（即ち、ルーティング１３６、地図作成１３７、運転１３８、等々）は、上述した３つのハフマン木によってコード化された４つの種類のデータに対して値が明確なクラスタ化を呈し得る。換言すれば、ハフマン統計アナライザが走ってどの値を最短ハフマンコードでコード化すべきかを見出す時に、ルーティングデータ、地図作成データ、運転データ、等々のために別々の統計的解析が遂行される。次いで３つのハフマン木の別々のセットがこれらの異なる各データの型毎に準備される。例えば、ルーティングデータのために３つのハフマン木が存在する。即ち、リテラルのための１つと、ＬＺ／リテラルビットフラグ、及びランレングスカウントまたはオフセットの上位ビットの何れかのための第２の木と、一致の長さ及びオフセットの下位ビットのための第３の木である。同様に、地図作成データのこれらの面をコード化する３つの別々のハフマン木、運転データのこれらの面をコード化する３つの別々のハフマン木、等々が存在する。３つのハフマン木の別々のセットは、異なる種類の各データ毎に準備することができる。
【０１０３】
地理データベースの若干の実施例では、若干のこれらの異なる型のデータは、これらのデータ成分の若干、または全てについて値が似たようなクラスタ化を呈し得る。例えば、一実施例では、地理データ内の置換コードオフセットは、ルーティングデータ内の置換コードオフセットと類似したクラスタ化を呈し得る。これらの状態の下では、オフセットのための同じハフマン木を、ルーティングデータ及び地図作成データの両方に使用することができる。同様に、他の型のデータも、もしこれらの他の型のデータ内のデータが類似したクラスタ化特性を呈するならば、同じ（１つまたは複数の）ハフマン木を共用することができる。同様に、他のハフマン木（例えば、リテラル、一致の長さ、ランレングス）を、１つより多くの型のデータが共用することもできる。
【０１０４】
更に他の実施例では、同一の型の地理データに対して付加的なハフマン木を使用することができる。例えば、ルーティングのような１つの型の地理データの統計的解析は、ルーティングデータの若干のパーセルを、ルーティングデータの他のパーセルとは異なる１つまたはそれ以上のハフマン木でハフマンコード化すべきことを指示することができる。これらの状態の下では、異なるハフマン木を形成し、ルーティングデータの異なるパーセルのために使用することができる。
【０１０５】
データサイズ要求を更に減少させるために、各型のデータ毎のハフマン木のセットは、圧縮されたデータのパーセルの中に格納されない。代わりに、あるデータ型の全てのパーセルが同一ハフマン木を使用することが予測されるから、各型のデータ毎のハフマン木は圧縮されたデータとは別のデータベースの一部分内に維持される。例えば、各型の地理データ毎のハフマン木は、グローバルデータの一部分内に格納することができる。各データ型毎のハフマン木を、ハフマンコード化されている圧縮されたデータとは別のデータのグローバル部分内に格納すると、幾つかの長所が得られる。ハフマン木をデータの各パーセル内に格納することに伴う格納要求の減少の他に、そのデータ型をナビゲーション応用内の特定機能が使用する時にそれらをメモリ内にロードすることができ、またそれが関係している型の全てのパーセルのために使用することができる。これは、ハフマン木を使用することに伴う処理を減少させ、性能の改善をもたらす。例えば、データの各型毎のハフマン木は、そのデータ型を使用する機能が動作している間メモリ内に維持することができる。
【０１０６】
例
開示したデータ圧縮プロセスを、図１０に基づいて説明する。この例には、圧縮されていないデータストリーム“ xztjxihgppcbscbagppcbacbs … "が示されている。このデータストリームは、データの隣接する部分を表している。一実施例ではこのデータストリームは地理データベースの一部分であるが、別の実施例ではこのデータベースストリームは他の何等かの種類のデータの一部分であることができる。
【０１０７】
図１０には、表も示されている。元のデータストリーム内の各文字は表の第２列内の対応エントリ内に含まれ、表の各行はエントリに対応している。表の第３列は、ＬＺ／リテラルビットフラグは追加されてはいるが、ハフマンコード化される前のランレングスカウントを、置換コードを用いて圧縮するプロセス中のデータストリームの中間段階を示している。第４列は、ハフマンコード化を使用して、第２列内の各エントリをコード化するために呼出される関数の適用を示している。（第１列は、第２列内に示す圧縮されていないデータストリーム内の各エントリの相対位置、及び第３列に示す圧縮されたデータストリームの表現を識別する連続的に割当てられた番号を含んでいる。第１列内の番号は単なる例示に過ぎず、圧縮されたデータストリームまたは圧縮されていないデータストリームの何れかの部分を形成するものではない。）
圧縮されたデータストリームは、各々がハフマンコードである複数のエントリからなっている。ハフマンコード自体は、図１０には示されていない。代わりに図１０の第４列は、ハフマンコードを形成するために関数に受渡される引き数と共に呼出される関数（ “huff1( )" 、“huff2( )"、“huff3( )"）を示している。関数に受渡される引き数は、図１０の表内の第３列に示されている圧縮の中間段階に形成されるリテラル文字データ、置換コード、及びランレングスカウント（ＬＺ／リテラルビットフラグを含む）を含んでいる。リテラル文字データ、置換コード、及びランレングスカウントをコード化するために呼出される関数は、第３列内の各エントリ（即ち、バイト）を対応ハフマンコードで置換する。ハフマンコードは、この目的のためにこれらの各データ成分の統計的解析によって構築されたそれぞれのハフマン木から入手される。この例では、これらの各データ成分（即ち、リテラル文字データ、置換コード、及びランレングスカウント）毎の統計的解析が既に入手済みであり、各成分毎の木が構築済みであることを理解されたい。従って、圧縮されたデータストリームを形成するエントリをコード化するために、これら３つのハフマン木が参照される。同様に、圧縮されたデータストリーム内の各エントリを復号して元の圧縮されていないデータストリームを復元するために、これらの同一の３つのハフマン木が参照される。一実施例では３つのハフマン木が存在しているが、代替実施例ではより多くの、またはより少ないハフマン木が存在することができる。
【０１０８】
簡易化のために、一致の長さは８ビットであるものとしている。これは、第２の木内のオフセットの下位ビットを考える必要をなくしている。
【０１０９】
列３内の最初のエントリ（ “lit, 13"）を参照する。このエントリはＬＺ／リテラルビットフラグ、及びランレングス、またはオフセットの上位ビットの何れかを含む。前述したように、このエントリ内のＬＺ／リテラルビットフラグ（“ＬＺ”）は、後続データがリテラルであることを指示している。これは、このエントリ内のデータの残余が、リテラルのランレングスのための値を表していることを意味している。（フラグ及びランレングスは、図９Ａに示すビットに対応している。）より詳しく述べると、このエントリは、後続データがリテラルであることを指示する１ビット（例えば、“０”）と、圧縮されたデータストリーム内の次の 13 エントリがリテラルのためのハフマンコードであることを指示するランレングスカウントのビット（例えば、“0001101" ）とを含んでいる。この第１のエントリは、表の第４列内の第１のエントリに示すように、第３のハフマン木を使用してコード化される。（このハフマン木は、任意に「第３の」木と呼んでいるだけである。）
値“０”プラス“ 13 ”のためのハフマンコードは、統計的解析によって導出されている。「リテラル」を表す各ハフマンコードは、元のデータストリーム内の１つの文字だけを表している。これは、圧縮されたデータストリーム内のこれらの次の各 13 エントリが、元のデータストリームの個々の文字を表すハフマンコードとして取られることを意味している。これらの次の 13 エントリはリテラルを表すハフマンコードであるから、これらの 13 エントリは何れも、データストリーム内の一致するサブストリングのための置換コードを表してはいない。
【０１１０】
図１０の第４列内の第２乃至 14 番目のエントリ内に示すように、リテラルのためのハフマンコードである圧縮されたデータストリーム内のこれらの 13 エントリは、元の文字（ “xztjxihgppcbs"）をハフマンコードで置換することによって形成される。これらのハフマンコードは、データストリーム内の個々の文字の全てにハフマン統計解析を使用して決定される。（前述したように、圧縮方法を地理データベースに適用する一実施例では、各特定型のデータベースは別々にハフマン統計解析を受ける。従って、ルーティングデータはそれ自体の第１のハフマン木を有することができ、地図作成データはそれ自体の第１のハフマン木を有することができる、等々である。）これらの 13 ハフマンコードによって表される元の文字は、別のハフマン木（任意に「第１」の木を呼んだ）内に見出すことができるので、これらのコードによって表された元の圧縮されていないデータ文字を復元するために、第１のハフマン木が使用される。
【０１１１】
第４列内のこれらの 13 エントリの第１のエントリ（ “huff1( x )" ）を参照する。圧縮されたデータストリーム内のこのエントリは、文字“ｘ”のためのハフマンコードである。このエントリをコード化するために第１のハフマン木が使用され、次いで初期ハフマンコードの後に付加されて圧縮データストリームが形成される。同様に、圧縮されたデータストリーム内の次のエントリは、文字“ｚ”のためのハフマンコードである。この場合も、この位置におけるエントリをコード化するために第１のハフマン木が使用され、次いで最初の２つのハフマンコードの後に付加されて圧縮データストリームが形成される。同様に、圧縮されたデータストリーム内の次の 11 のハフマンコードが第１のハフマン木を使用してコード化され、次いで他のハフマンコードの後に付加されてこれらの最初の 13 文字に対応する圧縮データストリームが形成される。
【０１１２】
元のデータストリーム内の 14 番目及び 15 番目の文字（ “cb" ）は、元のデータストリーム内の 11 番目及び 12 番目の文字と一致し、圧縮されたデータストリーム内に置換コードが挿入されてデータストリームの先行部分からのサブストリングの置換がこの位置に現れていることを指示する。この置換コードは、ハフマンコード化を使用して別々に圧縮されている２バイトからなる。置換コードの第１のバイトは、１ビットのＬＺ／リテラルフラグと、オフセットの７つの上位ビットとからなる。（この第１の部分は、図９Ｂの置換コードの第１バイトに対応する。）図１０に戻って、この置換コードの第１の部分は、第３列の 15 番目の位置のエントリに示す “ lz,−3 " によって表されている。即ち、置換コードの部分は、ＬＺ／リテラルフラグ（例えば、“１”にセットされていれば置換コードを指示する）と、一致する後続ストリングの開始位置が３文字戻ることを指示するオフセットのビット（例えば、“0000011" ＝３）とを含む。このエントリは第３のハフマン木 “huff3( lz,−3 )"を使用してコード化される。これにより、圧縮されたデータストリームは “ lz,−3 " に対応する第３のハフマン木からのハフマンコードを含むことになる。
【０１１３】
次のエントリは、２バイト置換コードの第２の部分（即ち、バイト）である。置換コードのこの部分は、第３列内の 16 番目のエントリの“２”によって表されている。置換コードのこの第２の部分は、置換コードの一致の長さ部分、及びもしあれば、オフセットの下位ビットを含む。この第２の部分は、図９Ｂの置換コードの第２バイトに対応する。詳しく述べると、置換コードのこの部分は、データをその元の形状に復元する時に、この位置に挿入された３文字分戻った位置における文字数を指示するビット（ “00000010" ）を含む。このコード（ “huff2( 2 )" 、及び先行コード（ “huff3( lz,−3 )"）内の値（ “−3 " ）を使用すると、元のデータストリーム内の文字のサブストリングが一致するものとして識別される。元のデータストリームの 14 番目及び 15 番目の２つの文字は、圧縮されたデータストリーム内にリテラルで存在してはいない。代わりに、これらの文字は、置換コードを形成している２つのハフマンコード化されたエントリによって形成された置換コードによって表されている。詳しく述べると、これら２つのハフマンコード化されたエントリは、先に出現したデータストリーム内の２文字長（置換ストリング長＝ huff2( 2 ) から“２”）である３文字分戻った（ “huff3( lz,−3 )"からオフセット＝“−３”）位置から開始される文字のサブストリングを参照する。
【０１１４】
このエントリに続くのは、別のハフマンコード（ “huff2( 2 )" ）である。このハフマンコードは、第２のハフマン木を使用してコード化されている。このハフマンコードは、置換コードの残余を、詳しく言えば先行コード内に含まれていないオフセットの下位ビット（もしあれば）及び一致の長さを表す。このコードの値（ “−３" ）は、一致するサブストリングの開始位置まで達するには、その位置からどれ程多くの文字分を戻るのかを指示している。
【０１１５】
このハフマンコードに続く圧縮データストリーム内の次のエントリは、ハフマンコード（ “huff3( lit, 1 )"）である。このコードも、ハフマン木を使用して入手される。このコードは、次のエントリが、リテラル文字を表すハフマンコードであることを意味している。
【０１１６】
圧縮データストリーム内の次のエントリ（ “huff1( a )" ）は、第１のハフマン木を使用してコード化されたリテラル文字“ａ”を表しているハフマンコードである。
【０１１７】
圧縮データストリーム内の次のエントリ（ “huff3( lz, 5 )" ）は、第３のハフマン木を使用してコード化された長さ“５”の置換を表すハフマンコードである。
【０１１８】
圧縮データストリーム内の次のエントリ（ “huff2(−9 )"）は、９文字分戻るのを開始する前に、上述した長さ“５”の置換を表すハフマンコードである（ここに、値“９”は第２のハフマン木を使用してコード化されている）。
【０１１９】
データストリームの残余は、上述したようにコード化される。
【０１２０】
圧縮されたデータストリームを復号するためには、コード化プロセスとは逆の順番にこれらの木が使用される。
【０１２１】
Ｉ．圧縮された地理データベースの形成
層化され、パーセル化されたデータを含む地理データベースを形成するプロセスは、出願番号第 08/924,328 号、第 08/935,809 号、及び 08/740,295 号に開示されており、本明細書にはその全文が参照として採り入れられている。一プロセス例を、図１１Ａ−１１Ｃを参照して以下に説明する。汎用データフォーマットで供給される地理データベース９００から始まって、各データ型及び層毎の分離した中間フォーマットファイルが形成される（ステップＡ）。汎用データフォーマット地理データベース９００は、所有権を主張できる（プロプラエタリ）フォーマットであることも、所有権を主張できないフォーマットであることもできる。汎用データフォーマットデータベースファイル９００は、図４に示すルーティング１３６、地図作成１３７、関心点１３９、運転１３８、等々のような異なる各型のデータを導出するために、並びに図５に示すこれらの型の若干の各層を導出するために作成される。
【０１２２】
これらの中間フォーマットファイル９０２が形成されると、臨時参照番号が割当てられる（ステップＢ）。最終フォーマットファイルでは、１つの型のデータが別の型のデータを参照するか、または１つの層内のデータが別の層内のデータを参照するような、いろいろな事例が存在する。同様に、異なる型のデータレコードを互いに関係付ける、図４及び５の索引１４７及び１４９のような、いろいろな索引が存在する。これらのデータ参照は、データベースのパーセル化を斟酌して後段において分解されよう。しかしながら、この段においては、データの異なる型、層、及び索引内にいろいろな参照を構築するために、臨時参照番号が使用される。
【０１２３】
各型のデータ（例えば、ルーティング、地図作成、等）の形成に続いて、分離した各型は圧縮段へ導かれる。圧縮段を、図１１Ｂに示す。本明細書の目的のために、ルーティングデータの圧縮だけを説明する。他の種類のデータも同じように圧縮できることを理解されたい。
【０１２４】
中間ルーティングデータ９０２（ルーティング）の全ては、ハフマンコード化統計データ集めルーチン９１６へ入力される（ステップＣ）。ハフマンコードの第１の集まり９２０が作られる（ステップＤ）。この第１の集まり９２０は、各リテラル文字の出現の相対頻度に基づいて、ルーティングデータ内の各リテラル文字をハフマンコードに関係付ける。最も屡々出現する文字に、最短のコードが割当てられる。
【０１２５】
中間ルーティングデータ９０２の全ては、一致するデータストリングへの逆向きの参照を識別するルート計算データを走査する圧縮ルーチンへ入力される（ステップＥ）。所定の値（例えば、ｘバイト）より大きいオフセットは無視される。非置換（即ち、「リテラル」）のランレングスが決定される。リテラル／ＬＺフラグとオフセットの最上７ビット、及びリテラルランレングスの８ビット組合せが組合され、フラグ／オフセット及びリテラルランレングス値のための作業域を使用してハフマンコード化統計データ集めルーチン９１６内へ供給される（ステップＦ）。同様に、オフセットの残りの下位ビット、及び一致の長さが組合され、下位ビットオフセット／一致の値のための作業域を使用してハフマンコード化統計データ集めルーチン９１６内へ供給される（ステップＧ）。
【０１２６】
ルーティングデータ９０２（ルーティング）のこれらの統計的解析に続いて、３つのハフマン木が形成される（ステップＨ）。第１のハフマン木 “huff1"は、リテラルバイト値をコード化する。第２のハフマン木 “huff2"は、一致の長さ、及びオフセットの下位ビットをコード化する。第３のハフマン木 “huff3"は、ＬＺ／リテラルフラグ、及びオフセットの上位ビットまたはリテラルランレングスをコード化する。
【０１２７】
図１１Ｃを参照する。近似圧縮されたパーセルサイズが、エスティメータルーチン９６０によって推定される（ステップＩ）。次いで、パーセルの推定された最終サイズが与えられて、パーセルＩＤが割当てられる。パーセルＩＤが割当てられると、ステップＢにおいて中間ルーティングデータ９０２全体に割当てられた臨時参照ＩＤを、新しいパーセルＩＤに置換できる（ステップＪ）。
【０１２８】
この段において、中間データ９０２を圧縮することができる。各型のデータ（例えば、ルーティング、地図作成、運転、等々）が圧縮される（ステップＫ）。圧縮する時、ステップＨにおいて形成されたハフマン木９５０が使用される。圧縮ステップ中に、２つのプロセスが遂行される。第１に、先行サブストリングと一致するサブストリングが置換コードによって置換され、次いで、リテラル、オフセット、及びリテラル／置換長さがそれらの対応するハフマンコードで置換される。リテラル、オフセット、及びストリング長さの置換に使用されたハフマン木は、地理データベースのグローバルデータ部分内に格納され、適切に識別される（ステップＬ）。
【０１２９】
データが圧縮されると、それらはパーセルに形成される（ステップＭ）。パーセルは、上述した方法を使用して形成することができる。異なる種類のパーセル化プロセスを使用することができる。データがパーセルに形成されると、各パーセルを形成した結果的なデータのサイズが調べられる。あるパーセルとして指定されたデータが圧縮された後、そのデータに必要な格納の量は最大パーセルサイズを超えるべきではない。例えば、もし各パーセルのサイズが 16 Ｋを超えないようにパーセルが形成されれば、地理データが圧縮された後の、そのパーセルに対応するものとして指定された結果的なデータのサイズは、圧縮後、 16 Ｋ限度を超えることはない。結果的な圧縮されたデータサイズが最大パーセルサイズ限度に足りない場合には、圧縮データにパッディングが付加される。従って、各パーセルは、全部が圧縮されたデータか、または圧縮されたデータ＋最大パーセルサイズに等しくするためのパッディングの何れかを含むようにされる。
【０１３０】
各分離した型及び層毎にパーセルが形成されると、各層及び型毎のパーセルは、単一のファイル９１２に連結される（ステップＮ）。単一のファイル９１２を形成する際に、ハフマン木９５０は（図６に示すように）データベースファイルのグローバル部分内に格納することができる。
【０１３１】
Ｊ．圧縮解除段
前述したように、圧縮されたフォーマットで媒体上に格納された地理データを圧縮解除するために圧縮解除ルーチンが使用される。一実施例では、圧縮解除ルーチンは、ナビゲーション応用プログラム１８の一部として含まれている。一実施例によれば、圧縮解除ルーチンは、ナビゲーション機能へのインタフェースを提供するデータアクセス機能のライブラリの一部である。
【０１３２】
一実施例においては、圧縮解除ルーチンは構成可能である。圧縮解除ルーチンを構成可能にする一方法は、必要な場合に限ってそれを使用することである。前述したように、若干のナビゲーションシステムでは、地理データベースを格納している媒体は取り外し可能である。これにより古い地理データベースを新しい、更新されたバージョンと置換することができるか、または、これによりもしエンドユーザが異なるカバレッジエリアを望めば媒体を交換することができる。媒体上の地理データのデータ圧縮が常に必要であるとは限らない。従って、若干のカバレッジエリアのための地理データベースの若干のコピーまたはバージョンは、媒体上の地理データを圧縮することを要求しないかも知れない。この構成可能性を支援するために、ナビゲーション応用は初期化ルーチンを含んでいる。初期化ルーチンは、特に、ナビゲーションシステム内に設置されている媒体上に格納された地理データベースが、圧縮されているか否かを検査する。データフラグまたは他の指示手段のようなセットアップパラメータを、媒体の初期部分またはグローバル部分内に含ませることができる。媒体のこの部分は圧縮されないので、これは圧縮解除ルーチンがロードされる前に読み取ることができる。媒体の初期部分上のこれらのセットアップパラメータは、媒体上の地理データが圧縮されているか否かを指示する。これらのパラメータは、どの種類の圧縮が使用されているのか、及び媒体上の全ての異なる型のデータが同一種類の圧縮法で圧縮されているのか否かをも指示する。セットアップパラメータは、異なる種類のデータに対して異なる種類の圧縮が使用されているか否かをも指示することができる。この初期化ルーチンは、ナビゲーションシステムに電源が投入された時に、この検査プロセスを遂行する。もし地理データが圧縮されていなければ、初期化ルーチンは圧縮解除ルーチンのローディングを省くことができ、地理データは圧縮解除する必要なく媒体から読み出される。
【０１３３】
一方、もし媒体上の地理データが圧縮されていることをセットアップパラメータが指示していれば、圧縮解除ルーチンがロードされる。圧縮解除ルーチンは、必要に応じてデータの圧縮解除を遂行するために、ナビゲーション応用の動作中メモリ内に維持することができる。もし媒体上の地理データの全てが圧縮されているのではないのであれば、圧縮解除ルーチンは必要な場合だけ使用される。
【０１３４】
前述したように、媒体上のデータの圧縮は、ナビゲーションシステムの動作を強化するために、データの配列と矛盾しないように実現することが好ましい。同様に、圧縮解除ルーチンはこれらのナビゲーション強化特色と共に、及びそれらを実現する手順、機能、及び／またはルーチンと共に動作する。例えば、ナビゲーション応用機能の１つが地理データを要求した時に、データアクセスライブラリの中の機能は、媒体上のどのパーセル（１つ、または複数の）が所望のデータを含んでいるのかを識別する。媒体上の索引は、この目的のために使用することができる。次いで、他の機能が、媒体から読み出される適切な位置（１つ、または複数の）を識別することができる。
【０１３５】
この点までのナビゲーション応用プログラム機能、及びデータアクセス機能の動作は、媒体上のデータがあたかも圧縮されていないかのように動作する。データが実際に媒体から読み出される時点に、圧縮解除機能が動作する。
【０１３６】
圧縮されたデータを有するパーセルが媒体から読み出された後に、それはナビゲーションシステムのメモリ（例えば、図１のＲＡＭ  ２０）内の適切な位置に格納される。例えばパーセルは、媒体から読み出された、そしてそれらの全てがナビゲーション応用へ戻されるデータを含んでいる幾つかのパーセルのキャッシュ内に配置することができる。
【０１３７】
パーセルを復号するために、ビットポインタがそのパーセルのトップを指し示す。パーセル内の初期コードは、ハフマンコードであろう。一実施例では、パーセルは置換コードから始まることはなく、従って初期ハフマンコードは、復号されると、この初期コードに後続する幾つかのハフマンコードが、第１のハフマン木を使用して復号されるリテラルのためのハフマンコードであることを指示するランレングスカウントを含む。リテラルのためのランレングスカウントは、第３のハフマン木内でＬＺ／リテラルビットフラグと共に復号されるので、初期ハフマンコードは第３のハフマン木を使用して復号される。あるパーセル内のこの初期ハフマンコードは、第３のハフマン木を使用して復号されると、ＬＺ／リテラルフラグ（セットされていると、このビットに後続するデータがリテラルのためのランレングスカウントであることを指示する）と、それに続くランレングスカウントとを含むことに注目されたい。あるパーセルが置換コードから始まらず、従って初期コード内のＬＺ／リテラルフラグが冗長であり、不要であると想定することはできるが、この初期ランレングスカウントに同じハフマン木を使用すると総合的な効率が向上する。
【０１３８】
パーセルがリテラルから始まり、置換コードから始まらない理由は、一般に、あるパーセルが開始される前には、どのデータが読み出されたかを知る方法がないからである。前述したように、パーセルは、媒体から常に一緒にアクセスされるデータの集まりを表している。しかしながら、一般的にはパーセルにアクセスする所定の順番は存在しない、即ち１つのパーセルが必ずしも常に別のパーセルの後に読み出される訳ではない。従って、どの先行データが既に読み出されているのかを確かめる方法が存在しないので、データのパーセルは一致する先行サブストリングまでの逆向きオフセットを含む置換コードから始まることはないのである。（パーセルはリテラルから始まるので、「リテラル」を指示するために第１のビットを使用することは冗長であり得る。従って、代替実施例ではこの第１のビットを省くことができる。）
第３のハフマン木を使用する初期ハフマンコードの復号に続いて、初期ランレングスカウントによって指示されているその後のハフマンコードの数が、第１のハフマン木を使用して復号される。これらのコードは、ハフマンコードをリテラル文字に関連付ける第１のハフマン木を使用して復号される。
【０１３９】
リテラルのためのこれらのハフマンコードの復号に続いて、次のハフマンコードが復号される。その後のデータがリテラルデータであるのか、または置換コードであるのかを知る必要があるので、このコードはＬＺ／リテラルフラグを含むことになろう。第３のハフマン木はＬＺ／リテラルフラグ、及びランレングスカウントまたは置換コードのオフセットの上位ビットの何れかを含んでいるので、このハフマンコードは第３のハフマン木を使用して復号される。第３のハフマン木を使用して復号された時、復号されたバイト内の第１ビットは、直後のデータがリテラルのランレングスを参照するのか、または置換コードを参照するのかを指示する。後続するデータが置換コードであることをこのビットが指示するようにセットされているものとすれば、この復号されたバイトの残余はオフセットの上位ビットであり、その直後のハフマンコードは復号された時に、オフセットの下位ビット、及び一致の長さを含む置換コードの残余を含むことになる。この直後のハフマンコードは、第２のハフマン木を使用して復号される。置換コードの両部分がこれら２つのハフマンコードから入手されると、オフセットの位置から始まり、一致の長さに等しい長さを有する先に復号されたリテラルのサブストリングのコピーがこの点に挿入され、元の圧縮されていないデータストリームが復元される。
【０１４０】
このプロセスは、全パーセルが圧縮解除されるまで続行される。
【０１４１】
パーセル内のデータが圧縮解除されると、それらは、媒体上のデータがあたかも圧縮されていないかのように取扱われる。即ち、ナビゲーション応用へ戻すことが要求されているパーセル内のデータが識別され、戻される。従って、圧縮解除ルーチンの動作はナビゲーション応用機能、及びデータにアクセスし、探知する機能に対して透過である。
【０１４２】
ＩＶ．代替実施例
上述した実施例では、地理データベースがパーセル化されるものとして説明した。代替実施例では、地理データベースはパーセル以外に編成することが可能である。
【０１４３】
上記実施例の若干では、地理データベースが圧縮形状で媒体上に格納されるものとした。代替実施例では、開示した圧縮技術を地理データベースに、またはその部分に適用し、それらを、例えば中央サービスからビークルまで無線伝送によって伝送することができる。
【０１４４】
上述した実施例では、ナビゲーションの目的のためのデータの使用を強化するいろいろな特色及び／または配列を有するように形成されている地理データにデータ圧縮を適用するものとした。説明したデータ圧縮実施例は、特定の種類のナビゲーション強化特色を有する地理データベースと共に使用することに制限する意図はない。例えば、開示したデータ圧縮技術は、分離した型に編成されないか、または層に編成されないか、またはパーセル化されない地理データベースにも適用することができる。
【０１４５】
上述した実施例では、３つの種類のハフマン木を地理データベース内の各型のデータ毎に使用している。代替実施例では、３つより少ないか、または多いハフマン木を使用することができる。
【０１４６】
地理データベースを形成するための上述した一般的なステップは、地理データベースを形成できる方法の１つの例に過ぎない。地理データベースを形成する他の方法が存在すること、及び開示した圧縮技術が他のプロセスに従って形成される地理データベースと共に使用できることが理解されよう。
【０１４７】
上述した実施例では、ナビゲーションシステム内のナビゲーション応用によって使用される地理データベース内の地理データの圧縮を説明した。代替実施例では、ハードウェアプラットフォームまたはアーキテクチャには無関係に、エンドユーザにナビゲーション機能を提供する何等かのコンピュータをベースとするシステムを含むものと理解すべきである。例えば、ナビゲーションシステムは、手持ちシステム、またはパーソナルディジタル支援またはパーソナルコンピュータ上に設置されたシステムのような、どのような種類のポータブルシステムも含むことができる。代替実施例では、ナビゲーションシステムは、デスクトップコンピュータのようなパーソナルコンピュータ上に設置されたナビゲーション応用ソフトウェアを含むことができる。更に、ナビゲーションシステムは、ネットワークにされた環境、及びクライアント・サーバプラットフォーム環境を含むいろいろな異なる環境内で実現することができる。ナビゲーション応用プログラム及び地理データベースは同一位置に配置する必要はないが、ネットワークを通して接続することができる。地理データベースをエンドユーザから遠隔位置に配置し、無線ネットワークを通してデータをエンドユーザに伝送することができる。更にソフトウェアの全て、または一部を遠隔位置に配置することができる。
【０１４８】
物理的特色を参照するために、または物理的特色を表すデータを参照するために、他の技術を使用することができる。上述した内容が、類似の概念を表現する特定の用語に制限されるものではないことを理解されたい。
【０１４９】
上述した若干の実施例では、圧縮システム及び方法は、データを使用するナビゲーション応用プログラムの動作を強化する手法で格納される地理データが特定の値を有しているものとした。圧縮技術は、他の種類のデータ、特に特定の応用によるデータの使用を容易にする手法で配列された種類のデータと共に使用することもできる。これらの種類のデータ配列の例は、ディジタル辞典、ディジタルカタログ、ディジタルアーカイブ等を含む。
【０１５０】
以上の詳細な説明は、単なる例示であって本発明を制限するものではなく、本発明は特許請求の範囲によってのみ限定されるものであること理解されたい。
【図面の簡単な説明】
【図１】ナビゲーションシステムを示すブロック図である。
【図２】図１の地図データベースによって表される地理領域を示す地図である。
【図３】図２の地図の一部分の拡大図である。
【図４】種々のナビゲーション応用機能と共に使用される図１の地理データベース内に含まれる異なる型のデータを示す図である。
【図５】図４に示すルーティングデータ内のデータの分離した層を示す図である。
【図６】図１の地理データベース内のデータのパーセルの配列を示す図である。
【図７】空間的に編成された地理データへのパーセル化方法の適用を示す図２の地理領域の地図を示す図である。
【図８】元のデータストリーム内の第１の位置のサブストリングを、圧縮されたデータストリーム内に先に出現した一致するサブストリングを参照する置換コードで置換することを示す図である。
【図９Ａ】ランレングスカウントの実施例を示す図である。
【図９Ｂ】置換コードの実施例を示す図である。
【図１０】開示した圧縮システムの実施例の使用を示す例に従って、データストリング、オフセット、及びデータストリング長さのハフマンコード化の使用を示す表を含む図である。
【図１１Ａ】開示した圧縮方法の実施例を使用して圧縮された地理データベースを形成するプロセスを示す図である。
【図１１Ｂ】開示した圧縮方法の実施例を使用して圧縮された地理データベースを形成するプロセスを示す図である。
【図１１Ｃ】開示した圧縮方法の実施例を使用して圧縮された地理データベースを形成するプロセスを示す図である。
【符号の説明】
１０  ナビゲーションシステム
１１  ビークル
１２  プロセッサ
１４  ドライブ
１６  不揮発性メモリ記憶装置
１８  ナビゲーション応用ソフトウェアプログラム
２０  ＲＡＭ
２４  測位システム
２５  感知デバイス
２６  測位信号
２７  ディスプレイ
２９  スピーカ
３１  ユーザインタフェース
３２  記憶媒体
４０  データベース
４１  ルート計算機能
４２  ルート案内機能
４３  地図表示機能
４４  ビークル位置決め機能
４５  他の機能
１１０  地図
１１２  地理領域
１１４  位置
１１６  地図の一部
１２０  道路網
１３６  ルーティングデータ
１３７  地図作成データ
１３８  運転データ
１３９  関心点データ
１４０  合流点データ
１４１  ナビゲーション特色データ
１４２  地図作成データ
１４３  郵便番号データ
１４４  場所データ
１４６  他の型のデータ
１４７  外部相互参照索引
１４９  内部相互参照索引
２１７  格子
２１９  矩形領域
２２０  パーセル
９００  地理データベース
９０２  中間フォーマットファイル
９１６  ハフマンコード化統計データ集めルーチン
９２０  リテラルのためのハフマンコード
９５０  ハフマン木
９６０  エスティメータルーチン
【図１】
0004394763.tif 000003
【図２】
0004394763.tif 000004
【図３】
0004394763.tif 000005
【図４】
0004394763.tif 000006
【図５】
0004394763.tif 000007
【図６】
0004394763.tif 000008
【図７】
0004394763.tif 000009
【図８】
0004394763.tif 000010
【図９Ａ】
0004394763.tif 000011
【図９Ｂ】
0004394763.tif 000012
【図１０】
0004394763.tif 000013
【図１１Ａ】
0004394763.tif 000014
【図１１Ｂ】
0004394763.tif 000015
【図１１Ｃ】
0004394763.tif 000016