(57)【特許請求の範囲】
【請求項１】
少なくとも１つの処理装置と、複数の領域に分割される地図データの複数のナビゲート可能なパスの一部を表す複数のナビゲート可能なセグメントと、該地図データの複数の領域内における前記ナビゲート可能なセグメントについての最低コストデータであって、他の領域のそれぞれについて、ナビゲート可能なセグメントが複数の異なるコスト関数の何れかについて該他の領域への最低コストパスの一部であるかどうかを特定する前記最低コストデータとを含む前記地図データを格納したメモリと、を用いて、経路を決定するコンピュータデバイスの方法であって、
前記少なくとも１つの処理装置が、
前記地図データ上の出発地及び目的地を受信するステップと、
前記複数のコスト関数のうちの１つの選択情報とを受信するステップと、
前記地図データを用いて選択された前記コスト関数についての前記出発地から前記目的地への最低コスト経路を決定するステップと、を実行し、
前記最低コスト経路を決定する前記ステップは、
ノードへ接続されるナビゲート可能なセグメントのセットのうち１以上のナビゲート可能なセグメントが前記出発地及び前記目的地を含む複数の領域についての最低コストパスの一部として特定されているかどうかを判定することによって、前記出発地から前記目的地への複数の経路を検索するステップと、
前記セットの１以上のナビゲート可能なセグメントが最低コストパスの一部であるとして特定されている場合に、前記最低コストパスの一部であるとして特定されている前記１以上のナビゲート可能なセグメントのみのセットから探索するステップとを含むことを特徴とする方法。
【請求項２】
前記ナビゲート可能なセグメントについての前記最低コストデータは複数のビットを含むビットベクトルであり、
各ビットは、前記ナビゲート可能なセグメントが前記複数のコスト関数の何れかについて前記他の領域の１つへの最低コストパスの一部であるかどうかを示すことを特徴とする請求項１に記載の方法。
【請求項３】
前記地図データの各領域内の前記複数のナビゲート可能なセグメントについての前記最低コストデータは、前記他の領域のそれぞれについて、かつ、前記複数のコスト関数のぞれぞれについて、ナビゲート可能なセグメントがそれぞれの前記コスト関数について前記他の領域への最低コストパスの一部であるかどうかを特定し、
前記最低コスト経路を決定する前記ステップは、
ノードへ接続されるナビゲート可能なセグメントのセットのうち１以上のナビゲート可能なセグメントが前記出発地及び前記目的地を含む複数の領域についての前記選択したコスト関数における最低コストパスの一部として特定されているかどうかを判定することによって、前記出発地から前記目的地への複数の経路を検索するステップと、
前記セットの１以上の前記ナビゲート可能なセグメントが前記選択したコスト関数における最低コストパスの一部であるとして特定されている場合に、前記最低コストパスの一部であるとして特定されている前記１以上のナビゲート可能なセグメントのみのセットから探索するステップとを含むことを特徴とする請求項１に記載の方法。
【請求項４】
ナビゲート可能なセグメントについての前記最低コストデータは、それぞれのビットベクトルが前記複数のコスト関数の１つに関連する複数のビットベクトルを含み、
各ビットベクトルは、前記ナビゲート可能なセグメントが前記それぞれのコスト関数についての前記他の領域の１つへの最低コストパスの一部であるかどうかを示す複数のビットを含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記複数のコスト関数は、距離、移動時間、環境影響、使用されるガソリン、排出されるＣＯ２、及び、１以上の特定の道路種別若しくは分類についての回避又は優先、の少なくとも１つを含むことを特徴とする請求項１乃至４の何れか１項に記載の方法。
【請求項６】
前記少なくとも１つの処理装置は、前記決定した経路の画像をディスプレイに表示させるステップと、
前記画像を見ながら、ユーザが前記選択されたコスト関数を変更することを許容するステップと、
前記選択されたコスト関数の変更に応じて、新たに前記選択されたコスト関数について決定される新たな経路の画像で前記ディスプレイを更新するステップをさらに含むことを特徴とする請求項１乃至５の何れか１項に記載の方法。
【請求項７】
処理装置が請求項１乃至６の何れか１項に記載の方法を実行するように、該処理装置によって実行される命令を格納した記憶媒体。
【請求項８】
コンピュータデバイスであって、
複数の領域に分割される地図データの複数のナビゲート可能なパスの一部を表す複数のナビゲート可能なセグメントと、該地図データの複数の領域内における前記ナビゲート可能なセグメントについての最低コストデータであって、他の領域のそれぞれについて、ナビゲート可能なセグメントが複数の異なるコスト関数の何れかについて該他の領域への最低コストパスの一部であるかどうかを特定する前記最低コストデータとを含む前記地図データを格納したメモリと、
前記地図データ上の出発地及び目的地を受信するステップと、
前記複数のコスト関数のうちの１つの選択情報とを受信するステップと、
前記地図データを用いて選択された前記コスト関数についての前記出発地から前記目的地への最低コスト経路を決定するステップと、を実行するように構成された少なくとも１つの処理装置と
を備え、
前記最低コスト経路を決定する前記ステップは、
ノードへ接続されるナビゲート可能なセグメントのセットのうち１以上のナビゲート可能なセグメントが前記出発地及び前記目的地を含む複数の領域についての最低コストパスの一部として特定されているかどうかを判定することによって、前記出発地から前記目的地への複数の経路を検索するステップと、
前記セットの１以上のナビゲート可能なセグメントが最低コストパスの一部であるとして特定されている場合に、前記最低コストパスの一部であるとして特定されている前記１以上のナビゲート可能なセグメントのみのセットから探索するステップとを含むことを特徴とするコンピュータデバイス。
【請求項９】
前記ナビゲート可能なセグメントについての前記最低コストデータは複数のビットを含むビットベクトルであり、
各ビットは、前記ナビゲート可能なセグメントが前記複数のコスト関数の何れかについて前記他の領域の１つへの最低コストパスの一部であるかどうかを示すことを特徴とする請求項８に記載のコンピュータデバイス。
【請求項１０】
前記地図データの各領域内の前記複数のナビゲート可能なセグメントについての前記最低コストデータは、前記他の領域のそれぞれについて、かつ、前記複数のコスト関数のぞれぞれについて、ナビゲート可能なセグメントがそれぞれの前記コスト関数について前記他の領域への最低コストパスの一部であるかどうかを特定し、
前記最低コスト経路を決定する前記ステップは、
ノードへ接続されるナビゲート可能なセグメントのセットのうち１以上のナビゲート可能なセグメントが前記出発地及び前記目的地を含む複数の領域についての前記選択したコスト関数における最低コストパスの一部として特定されているかどうかを判定することによって、前記出発地から前記目的地への複数の経路を検索するステップと、
前記セットの１以上の前記ナビゲート可能なセグメントが前記選択したコスト関数における最低コストパスの一部であるとして特定されている場合に、前記最低コストパスの一部であるとして特定されている前記１以上のナビゲート可能なセグメントのみのセットから探索するステップとを含むことを特徴とする請求項８に記載のコンピュータデバイス。
【請求項１１】
ナビゲート可能なセグメントについての前記最低コストデータは、それぞれのビットベクトルが前記複数のコスト関数の１つに関連する複数のビットベクトルを含み、
各ビットベクトルは、前記ナビゲート可能なセグメントが前記それぞれのコスト関数についての前記他の領域の１つへの最低コストパスの一部であるかどうかを示す複数のビットを含むことを特徴とする請求項１０に記載のコンピュータデバイス。
【請求項１２】
前記複数のコスト関数は、距離、移動時間、環境影響、使用されるガソリン、排出されるＣＯ２、及び、１以上の特定の道路種別若しくは分類についての回避又は優先、の少なくとも１つを含むことを特徴とする請求項８乃至１１の何れか１項に記載のコンピュータデバイス。
【請求項１３】
測位システムと、
ディスプレイと、
ユーザインタフェースと、
請求項８乃至１１の何れか１項に記載のコンピュータデバイスと
を備え、
処理装置が、前記ユーザインタフェースにおける入力を介して前記出発地及び前記目的地を導出し、かつ、判定の結果をディスプレイに表示するように構成されることを特徴とするナビゲーション装置。
【請求項１４】
前記ディスプレイは、前記決定した経路の画像を表示するように構成され、
前記ユーザインタフェースは、前記ディスプレイの画像を見ながら、ユーザが前記選択されたコスト関数を変更することを可能にし、
前記ディスプレイは、前記選択されたコスト関数の変更に応じて、新たに選択されたコスト関数に対して決定された新たな経路の画像とともに表示を更新することを特徴とする請求項１３に記載のナビゲーション装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データを使用して経路を決定するコンピュータを使用した方法及び関連するシステムに関する。特に、方法は経路計画を容易にするために使用されるナビゲーション装置において使用されてもよいが、これに限定されない。
【背景技術】
【０００２】
経路計画アルゴリズム（ダイクストラ法、Ａ＊方法又はＭｏｏｒｅ／Ｐａｐｅ方法）は既知である。しかし、これらは多少遅い。そのような経路計画の速度を上昇する方法の一例は、特許文献１で示され、その教示は参考として本明細書に取り入れられている。特許文献１は、地図を領域に分割し且つ地図の各領域までの最短パス（最低コストパス）の木を判定することによる地図データの前処理を説明している。この前処理されたデータは、メモリに格納され且つ経路の算出中に使用される。
【０００３】
より詳細には、出発地が１つの領域内にあり、目的地が別の領域内にある場合、事前に判定された最短パスの木は、経路の一部として使用されるそれらの領域間のパスを迅速に判定するために使用される。そのような方法は、ユーザが経路の判定を要求した後に探索されるパスの数を減少するため、経路を決定するのに必要とされる処理レベルを低減する。
【０００４】
「最短」パスは、必ずしも最短距離のパスを意味せず、最低コストを有するパスを意味することが理解されるだろう。パスのコストは、コスト関数で指定されるように考慮される因子に依存し、最速経路及び使用燃料等の因子を考慮に入れてもよい。
【０００５】
そのような方法は、領域間の最短パスが静的なままである場合に非常にうまくいく。しかし、最低コストデータが判定されたコスト関数以外のコスト関数をユーザが使用したい場合、経路指定はスクラッチから判定される必要があり、これは経路を判定するのにかかる時間を非常に長くする。更にある期間にわたる交通状況の変化により、前処理された木が領域間の真の最短パスを特定しなくなるため、領域間の最短パスであるパスが変更される。この結果、経路は、指定された基準に対する最適な経路でないと判定される。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】米国特許第６，６３６，８００号明細書
【発明の概要】
【０００７】
本発明の第１の態様によると、複数のナビゲート可能パスを含み且つ複数の領域に分割された地図データを使用して経路を決定する方法であり、少なくとも１つの処理装置を使用して、地図データ上の出発地及び目的地並びに複数のコスト関数のうちの１つを選択する選択情報を受信するステップと、地図データの領域間の最低コストのパスを特定する最低コストデータ及び地図データを使用して出発地から目的地までの経路を決定するステップとを実行し、最低コストデータは、種々のコスト関数に対して種々の最低コストパスが一対の領域の間に存在する場合に一対の領域の間の２つ以上の最低コストパスを特定し、経路を決定することは、出発地及び目的地を含む一対の領域に対する最低コストパスから、選択されたコスト関数に対して最低コストを有する最低コストパスを特定することを含むことを特徴とする方法が提供される。
【０００８】
本発明は、プロセッサが複数のコスト関数のうちのいずれか１つに対して出発地から目的地までの経路を決定する速度を上昇する。コスト関数は、最速経路又は最も燃料効率の良い経路等を決定する関数であってもよい。
【０００９】
１つの構成において、最低コストデータは、複数のコスト関数の各々に対して、種々の時間において一対の領域の間に種々の最低コストパスが存在する場合に２つ以上の最低コストパスを含んでもよく、経路を決定することは、目的地及び出発地を含む一対の領域に対する最低コストパスから、選択されたコスト関数及び指定された時間に対して最低コストを有する最低コストパスを特定することを含む。指定された時間は、ユーザにより入力された移動時間であってもよい。
【００１０】
各最低コストパスは、複数のコスト関数のうちの２つ以上に対する最低コストパスであってもよい。各最低コストパスは、ポインタ又はフラグにより複数のコスト関数のうちの１つ以上とリンクされてもよく、選択されたコスト関数にリンクされた最低コストパスのみが経路指定中に考慮される。最低コストパスを特定することは、選択されたコスト関数にリンクされる一対の領域に対する最低コストパスを特定することを含んでもよい。
【００１１】
別の実施形態において、最低コストデータは、どの最低コストパスがどのコスト関数に適用可能であるかを特定しなくてもよい。そのような一実施形態において、最低コストパスを特定することは、一対の領域に対する各最低コストパスの選択されたコスト関数を使用してコストを決定するステップと、最低コストを有する最低コストパスを特定するステップとを含んでもよい。
【００１２】
この構成は、種々の時間において一対の領域の間に種々の最低コストパスが存在する場合に一対の領域の間の２つ以上の最低コストパスを特定しないデータを使用することに対して移動時間における領域間の最低コストパスが特定される尤度を上決定する方法を使用する場合と比較して迅速に経路を決定できる。例えば定期的なラッシュアワー等の交通状況の予測可能な変化により、領域間の最低コストパスが変更されてもよい。種々の時間における領域間の最低コストパスを事前に算出することにより、そのような周期的な変化を考慮に入れることができる。
【００１３】
経路の決定は、時間に関係なく一対の領域の間の最低コストパスを最低コストデータから特定するステップと、移動時間における最低コストパスを決定するために移動時間から導出された１つ以上の関連する時間に対する特定された最低コストパスに対してコスト解析を実行するステップとを含んでもよい。これにより、最低コストパスに関するデータは、それらパスが最低コストパスである時間に対する相互参照を必要としないため、最低コストデータははるかに小さいサイズとなる。ナビゲーション装置等の経路プラナは、関連する時間における最低コストパスである最低コストデータにより特定されたパスの部分集合を決定できる。そのような構成は、追加の処理負担を経路プラナにわずかにシフトするが、その代わり、最低コストデータのサイズが非常に節約される。
【００１４】
しかし、別の一構成において、最低コストデータは、パスが最低コストパスである基準時間を最低コストパス毎に特定し、経路を決定することは、移動時間から導出された１つ以上の関連する時間に対応する基準時間を有する最低コストデータから最低コストパスを選択することを含む。この構成は、最低コスト経路を見つけるためにより少ない潜在的な経路が探索される必要があるという利点を有する。
【００１５】
関連する時間は、最低コストパスにより接続されたノードへの予測到着時間であってもよい。ノードは、ナビゲート可能パスが交差／分岐する地図上の地点又はナビゲート可能パスの終了地点である。従って、コストに基づく解析を介して特定されたか又は経路で使用するために選択された最低コストパスは、全てが単一の時間のためのものではなく、経路に沿うノードへの到着時間に依存して種々の時間に対するためのものである。例えば経路を移動するのに１時間かかると予想される場合、その１時間にわたる時間に対する最低コストパスは、経路に沿うノードへの到着時間に基づいて特定／選択される。更に、最低コストデータを解析／選択すること及び経路を決定することは、経路の一部が決定された時にのみ最低コストデータが選択されるという点で協働して進んでもよい。
【００１６】
移動時間は、出発地からの出発時間、目的地への到着時間又は経路に沿う特定の場所（ノード等）への到着時間であってもよい。
【００１７】
所望のレベルの精度を達成するために、最低コストデータの時間分解能は、秒のオーダ、好ましくは１／１０秒のオーダ、最も好ましくは１／１００秒のオーダであるべきであることが分かっている。より粗なレベルの時間サンプルを有する最低コストデータを使用することは、結果として受け入れられないレベルの精度を与えることが分かっている。更に、１０進法の１／１０秒又は１／１００秒内で動作することにより、６０進法の秒に対する算出を容易にしてもよい。１／１００秒より精細なレベルは、データを格納するのに多くのビット数を必要とする可能性があるため回避するのが望ましいだろう。１／１００秒の時間分解能は３２ビット列として格納され、より高い分解能は６４ビット列を必要とする可能性があることが理解される。
【００１８】
地図データは、種々の時間におけるパスでの予測速度を特定する速度プロファイルデータを含んでもよい。地図データの複数のパスは、複数のナビゲート可能セグメントに分割されてもよく、速度プロファイルデータは、ナビゲート可能セグメント毎に速度プロファイルを特定してもよい。パスのコストは、そのパスを構成するナビゲート可能セグメントの速度プロファイルから少なくとも部分的に判定されてもよい。
【００１９】
一実施形態において、方法は、関連する時間に対するデータ速度を速度プロファイルから判定することを備え、コストは考慮中の経路毎に決定された速度から算出される。
【００２０】
別の実施形態において、方法は、考慮中の経路のナビゲート可能セグメントの速度プロファイルの複数の値（単一の値ではなく）からコストプロファイルを判定することを備える。換言すると、コスト関数は、プロファイル（すなわち、複数の値）を入力として受け取り、種々の時間における経路のコストを表すプロファイルを出力する。このように、ある期間にわたる経路のコストの変動が判定される。
【００２１】
方法は、共通の出発地と目的地との間の種々の移動時間に対する複数の経路を決定するステップをさらに含んでもよい。例えば複数の経路は、種々の移動時間が経路及び／又は出発地と目的地との間の経路に沿って移動する予測時間にどのように影響を及ぼすかを比較するために使用されてもよい。例えばラッシュアワーの間の幹線道路は、領域間の最低コストパスでない可能性があるが、ラッシュアワー以外では最低コストパスとなる可能性がある。これは、種々の移動時間に対して出発地と目的地との間の種々の経路及び移動時間を与える可能性がある。複数の経路を決定することにより、ユーザは決定された経路の比較に基づいて移動時間に関する決定を行える。
【００２２】
複数の経路の決定は、コストプロファイルの作成と組み合わされてもよく、その結果、複数の経路に対する出発地から目的地までのコストプロファイルを与える。
【００２３】
方法は、規定された基準に対して出発地と目的地との間の最適な移動時間を判定するためのプロファイル要求を受信するステップと、それに応答して、各々が異なる移動時間に対するものである複数の経路に対してコストプロファイルを判定し且つ結果をユーザに対して表示するステップとを含んでもよい。
【００２４】
結果の表示は、最適な経路に対する移動時間の表示であってもよい。従って、方法は、例えばコストプロファイルの値を比較することにより結果をフィルタリングすることにより複数の経路のうち規定された基準に対する最適な経路をコストプロファイルから決定することを含んでもよい。このように、処理装置はユーザのために最適な経路を決定し、ユーザによる解析は必要ない。
【００２５】
あるいは、結果の表示はコストプロファイルのグラフ等の表示であってもよい。このように、ユーザは規定された基準の評価及びユーザに最適な時間を選択することに基づいて経路を選択できる。例えば、出発地と目的地との間を移動するのに最も速い時間は夜であるが、ユーザは、最適とは言えない経路が例えば日中の時間であるより便利な移動時間であるためその経路を選択してもよい。複数の経路のうち全て又は少なくとも２つ以上の経路に対する結果を表示することにより、ユーザは移動時間及びそれが経路に与える影響に関して詳細を知った上での決定を行える。
【００２６】
一実施形態において、プロファイル要求は、経路の探索が制限される時間フレームを含む。例えばユーザは、移動時間が例えば午前６時〜午前９時である２つの時間の間、あるいは例えば月曜日である特定の曜日、例えば７月１日である特定の日付、特定の週又は特定の月であるべきであることを指定してもよい。あるいは、処理装置は、例えばユーザの移動時間の前後３０分であるユーザの指定した移動時間のウィンドウ内に入る移動時間を有する経路を自動的に探索し、異なる移動時間を有する経路がユーザの指定した移動時間を有する経路のコストより低いコストで見つけられた場合に別の移動時間をユーザに提案してもよい。
【００２７】
一実施形態において、方法は、ユーザインタフェースを介してユーザから移動時間を受信するステップと、決定した経路の画像をディスプレイに表示させるステップとを備える。方法は、決定した経路を示す地図データの画像を閲覧する一方でユーザが移動時間を変更できるようにすることを備えてもよい。例えば移動時間の変更に応答して、変更された指定移動時間に対して新たな経路が決定されてもよく、表示がその新たな経路の画像で更新されてもよい。あるいは、他の時間に対する最低コストの経路が事前に決定されていてもよい（例えば、上述したようにコストプロファイルの判定を介して）。表示の更新は、「リアルタイム」で、例えば１０００ミリ秒未満及びより好ましくは５００ミリ秒未満であるミリ秒のオーダで行われてもよい。そのような高速な再計算時間は、領域間の最低コストパスを特定するために使用された前処理済み最低コストデータを使用することにより可能である。表示の更新は、画面全体をリフレッシュし、古い経路をフェードアウトし且つ新たな経路及び／又は他の適切なアニメーションをフェードインすることにより実行されてもよい。新たな経路は、種々の時間における最低コストパスにおいて差異があるか否かに依存して古い経路と同一であっても異なってもよいことが理解されるだろう。
【００２８】
一実施形態において、方法は、移動時間を表すスライダの表示を行うステップと、新たな経路を決定し且つスライダでのユーザインタラクションに応答して新たな経路の画像で表示を更新するステップとを備えてもよい。方法は、ユーザが移動時間及び新たな経路の表示を変更した後の遅延がユーザに知覚できないくらいであるように新たな経路を決定し且つ表示することを備えてもよい。例えばユーザがスライダを動かしてから新たな経路の表示までの間に１秒未満及び好ましくは０．５秒未満の遅延がある。
【００２９】
方法は、決定された経路の画像をディスプレイに表示させることを備えてもよく、それによりユーザは、画像を閲覧し且つ新しく選択されたコスト関数に対して決定された経路の画像を表示するように表示を更新する一方で選択されたコスト関数を変更できる。表示の更新は、「リアルタイム」で、例えば１０００ミリ秒未満及びより好ましくは５００ミリ秒未満であるミリ秒のオーダで行われてもよい。そのような高速な再計算時間は、領域間の最低コストパスを識別するために使用された前処理済み最低コストデータを使用することにより可能である。表示の更新は、画面全体をリフレッシュし、古い経路をフェードアウトし且つ新しい経路及び／又は他の適切なアニメーションをフェードインすることにより実行されてもよい。新しい経路は、種々のコスト関数に対する最低コストパスに差分があるか否かに依存して古い経路と同一であっても異なってもよいことが理解されるだろう。
【００３０】
本発明の第２の態様によると、処理装置により実行された時に本発明の第１の態様に係る方法を処理装置に実行させる命令を格納したデータ記憶媒体が提供される。
【００３１】
本発明の第３の態様によると、複数のナビゲート可能パスを含み且つ複数の領域に分割された地図データ及び複数のコスト関数の各々に対して地図データの領域間の最低コストパスを特定する最低コストデータを格納したデータ記憶媒体が提供される。
【００３２】
そのようなデータ記憶媒体は、本発明の第１の態様に従う経路の決定において使用されるため有利である。
【００３３】
本発明の第４の態様によると、複数のナビゲート可能パスを含み且つ複数の領域に分割された地図データ及び地図データの領域間の最低コストパスを特定する最低コストデータを格納したメモリと、地図データ上の出発地及び目的地並びに複数のコスト関数のうちの１つを選択する選択情報を受信し且つ地図データ及び最低コストデータを使用して出発地から目的地までの経路を決定するように構成された処理装置とを備えるコンピュータ装置であって、最低コストデータは、種々のコスト関数に対して一対の領域の間に種々の最低コストパスが存在する場合に一対の領域の間の２つ以上の最低コストパスを特定し、経路を決定することは、出発地及び目的地を含む一対の領域に対する最低コストパスから、選択されたコスト関数に対して最低コストを有する最低コストパスを特定することを含むことを特徴とするコンピュータ装置が提供される。
【００３４】
本発明の更なる態様によると、複数のナビゲート可能パスを含み且つ複数の領域に分割された地図データを使用して経路を決定する方法であり、地図データ上の出発地及び目的地を受信し且つ地図データの領域間の最低コストのパスを特定する最低コストデータ及び地図データを使用して出発地から目的地までの経路を決定するために少なくとも１つの処理装置を使用することを備える方法であって、最低コストデータは、種々の時間において種々の最低コストパスが一対の領域の間に存在する場合に一対の領域の間の２つ以上の最低コストパスを特定し、経路を決定することは、出発地及び目的地を含む一対の領域に対する各最低コストパスが最低コストを有する時期を特定することを含むことを特徴とする方法が提供される。
【００３５】
本発明の別の態様によると、複数のナビゲート可能パスを含み且つ複数の領域に分割された地図データ及び地図データの領域間の最低コストパスを特定する最低コストデータを格納したメモリと、地図データ上の出発地及び目的地を受信し且つ地図データの領域間の最低コストパスを特定する最低コストデータ及び地図データを使用して出発地から目的地までの経路を決定するように構成された処理装置とを備えるコンピュータ装置であって、最低コストデータは、種々の時間において種々の最低コストパスが一対の領域の間に存在する場合に一対の領域の間の２つ以上の最低コストパスを特定し、経路を決定することは、出発地及び目的地を含む一対の領域に対する各最低コストパスが最低コストを有する時期を特定することを含むことを特徴とするコンピュータ装置が提供される。
【００３６】
本発明の更に別の態様によると、電子地図により範囲に含まれたエリアにおいてナビゲート可能な経路のセグメントを表す複数のベクトルを含む電子地図にわたり出発地から目的地までの経路を生成する方法（コンピュータにより実現される）であって、
−以前に電子地図の一部ではなかったベクトルを表すデータを含む電子地図に対して訂正を提供するデータを利用するステップと、
−新たなベクトルが修正された経路指定加速データを形成するために最低コスト経路の一部であることを示すように最低コスト経路の一部である電子地図のベクトルを示す経路指定加速データを修正するステップと、
−修正された経路指定加速データを利用することを含む生成であって、出発地と目的地との間の経路を生成するステップと、
を備える方法が提供される。
【００３７】
そのような方法は、新たなベクトルが経路指定加速データを利用する時に経路指定処理において考慮されることを可能にするため有利である。新たなベクトルがそのように印をつけられなかった場合、新たなベクトルは、経路指定加速データが生成された時に考慮されなかったため経路指定加速データを使用する経路指定方法により考慮されない。経路指定加速データは、目的地までの最低コスト経路の一部を形成する電子地図のベクトルを示す特定の電子地図に対して事前に生成される。
【００３８】
方法は、電子地図に対して訂正を提供するデータをダウンロードすることによりリモートソースからのデータを利用可能にすることを含んでもよい。
【００３９】
本発明の他の態様によると、少なくとも１つの機械に読み出された時に上述の方法のいずれかを機械に実行させる命令を含む機械可読媒体が提供される。
【００４０】
本発明の一態様又は一実施形態に関連して説明されるいずれの特徴も、必要な変更を加えて、必要に応じて本発明のあらゆる他の態様又は実施形態と共に使用されてもよい。
【００４１】
本発明の実施形態は、ソフトウェア、ファームウェア、ハードウェア又はそれらのあらゆる組み合わせで提供されてもよいことが当業者には理解されるだろう。
【図面の簡単な説明】
【００４２】
添付の図面を参照して本発明の実施形態の詳細な説明を一例として次に示す。
【図１】ナビゲーション装置により使用可能な全地球測位システム（ＧＰＳ）の例示的な一部を示す概略図である。
【図２】通信チャネルを介して通信中のサーバ及びナビゲーション装置を示す概略図である。
【図３ａ】ナビゲーション装置を示す概略図である。
【図３ｂ】図３ａのナビゲーション装置により採用されたアーキテクチャスタックの概略表現を示す図である。
【図４】ナビゲーション装置を示す透視図である。
【図５】本発明の実施形態により生成されるような地図の一例の一部を示す図である。
【図６】経路指定に使用されたノードが示される図５の地図を示す図である。
【図７】処理後の図５の地図を示す図である。
【図８】いくつかの実施形態においてノードが図７の地図に割り当てられる方法の一例を示す図である。
【図９】地図が複数のネストされた領域に区分される方法の一例を示す図である。
【図９ａ】図９のセグメントの高度化を示す図である。
【図１０】本発明の実施形態により利用されたビットベクトルの集合の一例を示す図である。
【図１０ａ】時間プロファイル化された情報がネットワークのダイクストラ探索中に利用される方法を示す図である。
【図１１】本発明の一実施形態のファイルに対するファイル形式の一例を示す図である。
【図１２】図１１の領域再マッピングテーブル及び領域ＩＤリストが符号化される方法の一実施形態を示す図である。
【図１３】図３に示したような最も粗なネストされた領域に対するファイル形式の一例を示す図である。
【図１４】最も粗な領域以外のネストされた領域に対するファイル形式の一例を示す図である。
【図１５】符号化方式内のビットの結合を例示的に示す図である。
【図１６ａ】、
【図１６ｂ】ビットを結合する効果を例示的に示す図である。
【図１７】ビットを結合する効果を例示的に更に示す図である。
【図１８】従来の経路指定技術を使用して考えられた経路を強調表示する地図を示す図である。
【図１９】本発明の実施形態により考えられた経路を強調表示する地図を示す図である。
【図２０】Ａ＊探索方法（従来技術）の一例を示す図である。
【図２１】本発明の少なくともいくつかの実施形態により使用された図２０に対する変形例を示す図である。
【図２２】方法のステップを概略的に示すフローチャートである。
【図２３】経路のナビゲート可能セグメントの予測速度を示すナビゲーション装置の表示を示す図である。
【図２４】出発地と目的地との間の１つ以上の経路に対するコストプロファイルを示すナビゲーション装置の表示を示す図である。
【図２５】出発地と目的地との間の１つ以上の経路のコストプロファイルを示すナビゲーション装置の表示を示す図である。
【図２６】特定の移動時間に対する出発地と目的地との間の経路及び移動時間を変更する制御を示すナビゲーション装置の表示を示す図である。
【図２７】ユーザが移動時間を変更した後の図２６の表示に対する更新を示す図である。
【図２８】ユーザが移動時間を更に変更した後の図２７の表示に対する更新を示す図である。
【図２９】移動時間がユーザに提案されるナビゲーション装置の一連の表示を示す図である。
【図３０】交差点ノードにおける２つの競合する経路のコストプロファイルを示すグラフである。
【図３１】図３０に示したコストプロファイルから導出された上限コストプロファイル及び下限コストプロファイルを示すグラフである。
【図３２】コスト関数の選択において使用されるナビゲーション装置に表示されるメニューを示す図である。
【発明を実施するための形態】
【００４３】
以下の説明において、同一の図中符号は同様の部分を特定するために使用される。種々の実施形態の説明において、一連の１９ｘｘの図中符号を有する図１９のフローチャートを参照する。
【００４４】
図１は、連続した位置、速度、時間及びいくつかの例においては無数のユーザに対する方向情報を判定するために利用されてもよい衛星無線を使用したナビゲーションシステムである全地球測位システム（ＧＰＳ）を概略的に示す。以前はＮＡＶＳＴＡＲとして既知であったＧＰＳは、極めて正確な軌道で地球を周回する複数の衛星を含む。これらの正確な軌道に基づいて、ＧＰＳ衛星は自身の場所をＧＰＳデータとしていかなる数の受信ユニットにも中継できる。しかし、ＧＬＯＳＮＡＳＳ、欧州のＧａｌｉｌｅｏ測位システム、ＣＯＭＰＡＳＳ測位システム又はＩＲＮＳＳ（Ｉｎｄｉａｎ  Ｒｅｇｉｏｎａｌ  Ｎａｖｉｇａｔｉｏｎ  Ｓａｔｅｌｌｉｔｅ  Ｓｙｓｔｅｍ）等の全地球測位システムが使用可能であることが理解されるだろう。
【００４５】
特にＧＰＳデータを受信できる装置がＧＰＳ衛星信号に対する無線周波数の走査を開始する場合、ＧＰＳシステムは実現される。ＧＰＳ衛星から無線信号を受信すると、装置は、複数の異なる従来の方法のうちの１つを使用してその衛星の正確な場所を判定する。殆どの例において、装置は、少なくとも３つの異なる衛星信号を取得するまで信号の走査を継続する（尚、位置を判定する標準的な方法ではないが、２つの信号だけでも他の三角測量技術を使用して位置を判定できる）。幾何学的三角測量を実現すると、受信機は、３つの既知の位置を利用して、衛星に対する自身の２次元位置を判定する。これは、既知の方法で行われる。更に、第４の衛星信号を取得することにより、受信装置は、同一の幾何学計算によって既知の方法でその３次元位置を算出できる。位置及び速度データは、無数のユーザにより連続的にリアルタイムで更新可能である。
【００４６】
図１に示すように、ＧＰＳシステム１００は、地球１０４の周囲の軌道上にある複数の衛星１０２を含む。ＧＰＳ受信機１０６は、多くの衛星１０２からスペクトル拡散ＧＰＳ衛星データ信号１０８としてＧＰＳデータを受信する。スペクトル拡散データ信号１０８は、各衛星１０２から連続的に送信され、送信された各スペクトル拡散データ信号１０８は、データストリームの発信元である特定の衛星１０２を特定する情報を含むデータストリームを含む。一般にＧＰＳ受信機１０６は、２次元位置を算出できるように少なくとも３つの衛星１０２からスペクトル拡散データ信号１０８を必要とする。第４のスペクトル拡散データ信号を受信することにより、ＧＰＳ受信機１０６は既知の技術を使用して３次元位置を算出できる。
【００４７】
従って、ＧＰＳシステムにより、ＧＰＳ受信機１０６を有する装置のユーザは数メートル内で地球上の自身の位置を判定できる。この情報を使用するために、ユーザの位置を示すことを可能にする電子地図に依存することが一般的になっている。そのような地図は、ＴｅｌｅＡｔｌａｓ（ｈｔｔｐ：／／ｗｗｗ．ｔｅｌｅａｔｌａｓ．ｃｏｍ）等のプロバイダにより例示される。
【００４８】
そのような電子地図は、ＧＰＳシステム（又は他の手段）を使用してユーザの位置を示すことを可能にするだけでなく、ユーザが移動等（経路指定の目的）のための経路を計画することを可能にする。この経路計画を行うために、電子地図はナビゲーション装置により処理され、これは一般的な演算装置により提供されてもよい。
【００４９】
ナビゲーション装置の特定の例は、ポータブルナビゲーション装置（ＰＮＤ）と呼ぶ便利な衛星ナビゲーション装置（衛星ナビゲーション）を含む。しかし、本発明の教示はＰＮＤに限定されず、一般に経路計画及びナビゲーション機能性を提供するために電子地図を処理するように構成されるいかなる種類の処理装置にも例外なく適用可能である。従って、本出願において、ナビゲーション装置は、ＰＮＤ、自動車等の乗り物、例えば経路計画及びナビゲーションソフトウェアを実行するポータブルパーソナルコンピュータ（ＰＣ）、移動電話又はパーソナルデジタルアシスタント（ＰＤＡ）又はサーバであるポータブル計算リソース、あるいはネットワークを介してそのような機能性を提供する他の演算装置として実装されるか否かにかかわらず、どんな種類の経路計画及びナビゲーション装置も含むことを意図する（それらに限定されない）。
【００５０】
ＰＮＤの形態のそのようなナビゲーション装置の一例を図３ａ及び図４ａに示す。尚、ナビゲーション装置２００のブロック図は、ナビゲーション装置の全ての構成要素を含んでいるわけではなく、多くの構成要素の例を示しているにすぎない。ナビゲーション装置２００は筐体（不図示）内に配置される。ナビゲーション装置２００は、例えば上述したプロセッサ２０２を含む処理回路網を含む。プロセッサ２０２は、入力装置２０４及び例えば表示画面２０６である表示装置に結合される。ここで、入力装置２０４は単数で示されるが、入力装置２０４がキーボード装置、音声入力装置、タッチパネル及び／又は情報を入力するのに利用される他のあらゆる既知の入力装置を含む任意の数の入力装置を表すことは、当業者には理解されるべきである。同様に、表示画面２０６は、例えば液晶ディスプレイ（ＬＣＤ）等のあらゆる種類の表示画面を含むことができる。
【００５１】
ナビゲーション装置２００において、プロセッサ２０２は、接続２１０を介して入力装置２０４に動作可能に接続されて入力装置２０４から入力情報を受信でき、各出力接続２１２を介して表示画面２０６及び出力装置２０８のうち少なくとも一方に動作可能に接続されて情報を出力する。ナビゲーション装置２００は、例えば可聴出力装置（例えば、スピーカ）である出力装置２０８を含んでもよい。出力装置２０８がナビゲーション装置２００のユーザに対して可聴情報を生成できるため、入力装置２０４は入力音声コマンドを受信するためのマイク及びソフトウェアを含むことができると同様に理解されるべきである。また、ナビゲーション装置２００は、例えばオーディオ入出力装置等のあらゆる追加の入力装置２０４及び／又はあらゆる追加の出力装置を更に含むことができる。
【００５２】
プロセッサ２０２は、接続２１６を介してメモリ２１４に動作可能に接続され、更に接続２２０を介して入出力（Ｉ／Ｏ）ポート２１８に対して情報を送受信するように更に構成される。Ｉ／Ｏポート２１８は、ナビゲーション装置２００の外部のＩ／Ｏ装置２２２に接続可能である。外部Ｉ／Ｏ装置２２２は、例えばイヤホン等の外部リスニングデバイスを含んでもよいがこれに限定されない。Ｉ／Ｏ装置２２２への接続は、イヤホン又はヘッドホンへの接続及び／又は例えば移動電話への接続のためのハンズフリー動作及び／又は音声起動動作を行うカーステレオユニット等の他のあらゆる外部装置への有線又は無線接続であってもよい。ここで、例えばナビゲーション装置２００とインターネット又は他のあらゆるネットワークとの間のデータ接続を確立するため、並びに／あるいは例えばインターネット又は他の何らかのネットワークを介してサーバとの接続を確立するために移動電話接続が使用される。
【００５３】
ナビゲーション装置２００のメモリ２１４は、不揮発性メモリ（例えば、プログラムコードを格納する）の一部及び揮発性メモリ（例えば、プログラムコードが実行された時にデータを格納する）の一部を含む。ナビゲーション装置は、接続２３０を介してプロセッサ２０２と通信するポート２２８を更に含み、取外し可能なメモリカード（一般に、カードと呼ばれる）が装置２００に追加されるのを可能にする。説明している実施形態において、ポートは、ＳＤ（セキュアデジタル）カードが追加されるのを可能にするように構成される。他の実施形態において、ポートは他の形態のメモリが接続されるのを可能にしてもよい（コンパクトフラッシュ（登録商標）（ＣＦ）カード、Ｍｅｍｏｒｙ  Ｓｔｉｃｋ（登録商標）、ｘＤメモリカード、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）フラッシュドライブ、ＭＭＣ（マルチメディア）カード、ＳｍａｒｔＭｅｄｉａ（登録商標）カード又はマイクロドライブ等）。
【００５４】
図２は、接続２２６を介するプロセッサ２０２とアンテナ／受信機２２４との間の動作可能接続を示す。ここで、アンテナ／受信機２２４は、例えばＧＰＳアンテナ／受信機であってもよいため、図１のＧＰＳ受信機１０６として機能する。図中符号２２４で指定されたアンテナ及び受信機は図示するために概略的に組み合わされるが、アンテナ及び受信機は別個に配置された構成要素であってもよく、アンテナは例えばＧＰＳパッチアンテナ又はヘリカルアンテナであってもよいことが理解されるべきである。
【００５５】
更に、図３及び図４のポータブル又はハンドヘルドナビゲーション装置２００は、例えば自転車、オートバイ、自動車又は船等の乗り物に既知の方法で接続又は「ドッキング」される。そのようなナビゲーション装置２００は、ポータブル又はハンドヘルドナビゲーションに使用するためにドッキングされた場所から取り外し可能である。実際には、他の実施形態において、装置２００はユーザのナビゲーションを可能にするためにハンドヘルド装置となるように構成されてもよい。
【００５６】
図３ａを参照すると、ナビゲーション装置２００は、内蔵された入力及び表示装置２０６並びに図３ａの他の構成要素（内部ＧＰＳ受信機２２４、プロセッサ２０２、電源（不図示）、メモリシステム２１４等を含むがこれらに限定されない）を含むユニットであってもよい。
【００５７】
ナビゲーション装置２００は、吸着カップ２５４を使用して車両のダッシュボード／窓等に固定されてもよいアーム２５２上に位置してもよい。このアーム２５２は、ナビゲーション装置２００がドッキングされるドッキングステーションの一例である。ナビゲーション装置２００は、例えばナビゲーション装置２００をアーム２５２に嵌合接続することによりドッキングステーションのアーム２５２にドッキングされるか又は接続される。ナビゲーション装置２００は、アーム２５２を中心に回転可能であってもよい。ナビゲーション装置２００とドッキングステーションとの間の接続を解放するために、例えばナビゲーション装置２００上のボタン（不図示）が押下されてもよい。ドッキングステーションに対してナビゲーション装置２００を結合及び分離する同様に適切な他の構成は当業者には既知である。
【００５８】
図３ｂを参照すると、プロセッサ２０２及びメモリ２１４は協働して、ナビゲーション装置２００の機能ハードウェア構成要素２８０と装置により実行されるソフトウェアとの間のインタフェースとして機能するＢＩＯＳ（基本入出力システム）２８２をサポートする。プロセッサ２０２は、メモリ２１４からオペレーティングシステム２８４をロードし、アプリケーションソフトウェア２８６（説明された経路計画及びナビゲーション機能性の一部又は全てを実現する）が実行可能な環境を提供する。アプリケーションソフトウェア２８６は、例えば地図閲覧、経路計画、ナビゲーション機能及び関連する他のあらゆる機能であるナビゲーション装置の中核機能をサポートするグラフィカルユーザインタフェース（ＧＵＩ）を含む動作環境を提供する。この点に関して、アプリケーションソフトウェア２８６の一部はビュー生成モジュール２８８を含む。
【００５９】
説明している実施形態において、ナビゲーション装置のプロセッサ２０２は、アンテナ２２４により受信されたＧＰＳデータを受信し且つＧＰＳデータが受信された時のタイムスタンプと共にＧＰＳデータを時々格納してナビゲーション装置の一連の位置を構築するようにプログラムされる。そのように格納された各データレコードはＧＰＳフィックスと考えられてもよい。すなわち、ナビゲーション装置の場所のフィックスであり、緯度、経度、タイムスタンプ及び精度レポートを含む。この一連の位置は測位データと考えられてもよい。
【００６０】
一実施形態において、データは、ほぼ周期的に、例えば５秒毎に格納される。他の周期も可能であり、データ解像度と記憶容量との間で均衡がとられることが当業者には理解されるだろう。すなわち、データの解像度がより多くのサンプルをとることにより向上されると、データを保持するのに必要なメモリはより多くなる。しかし、他の実施形態において、解像度は、ほぼ１秒毎、１０秒毎、１５秒毎、２０秒毎、３０秒毎、４５秒毎、１分毎、２．５分毎（又は実際にはそれらの周期の間のあらゆる周期）であってもよい。従って、装置のメモリ内では、複数の時点における装置２００の位置のレコードが構築される。
【００６１】
いくつかの実施形態において、取り込まれたデータの品質は、周期が長くなるほど低下し、劣化の程度はナビゲーション装置２００の移動していた速度に少なくとも部分的に依存するが、約１５秒の周期が適切な上限を与える可能性があることが分かるだろう。
【００６２】
更にプロセッサ２０２は、装置２００の位置のレコード（すなわち、ＧＰＳデータ及びタイムスタンプ）をサーバに対して時々アップロードするように構成される。ナビゲーション装置２００が自身をサーバに接続する永続的な又は少なくとも一般的に存在する通信チャネルを有するいくつかの実施形態において、データのアップロードは、２４時間に１回等の周期的に行われる。他の周期も可能であり、ほぼ１５分毎、３０分毎、１時間毎、２時間毎、５時間毎、１２時間毎、２日毎、１週間毎又はそれらの期間の間のあらゆる時間のいずれであってもよいことが当業者には理解されるだろう。実際には、そのような実施形態において、プロセッサ２０２は、ほぼリアルタイムに位置のレコードをアップロードするように構成されてもよい。しかし、これは、データが実際には送信の間に相対的に短い周期で時々送信されることを必然的に意味するため、より正確には擬似リアルタイムであると考えられる。そのような擬似リアルタイムの実施形態において、ナビゲーション装置は、メモリ２１４内及び／又はポート２２８に挿入されたカードにＧＰＳフィックスをバッファリングし且つ所定の数だけ格納された時にそれらを送信するように構成されてもよい。この所定の数は、２０、３６、１００、２００又はそれらの間のどのような数であってもよい。所定の数は、メモリ２１４／ポート２２８内のカードのサイズにより部分的に管理されることが当業者には理解されるだろう。
【００６３】
一般的に存在する通信チャネルを有さない他の実施形態において、プロセッサは、通信チャネルが作成される時にレコードをサーバにアップロードするように構成されてもよい。例えばこれは、ナビゲーション装置２００がユーザのコンピュータに接続される時であってもよい。ここでも、そのような実施形態において、ナビゲーション装置は、メモリ２１４内又はポート２２８に挿入されたカードにＧＰＳフィックスをバッファリングするように構成されてもよい。メモリ２１４又はポート２２８に挿入されたカードがＧＰＳフィックスで一杯になった場合、ナビゲーション装置は、最も古いＧＰＳフィックスを削除するように構成されてもよいため、先入れ先出し（ＦＩＦＯ）バッファと考えられてもよい。
【００６４】
説明している実施形態において、位置のレコードは、それぞれが２４時間以内のナビゲーション装置２００の動きを表す１つ以上のトレースを含む。２４時間の各期間はカレンダーの日付と一致するように構成されるが、他の実施形態においては一致する必要はない。
【００６５】
サーバ１５０は、装置の位置のレコードを受信し且つ処理するために大容量データ記憶装置内にそのレコードを格納するように構成される。従って、時間の経過と共に、大容量データ記憶装置はデータをアップロードした複数のナビゲーション装置２００の位置のレコードを蓄積する。一般に、サーバは複数のナビゲーション装置２００の位置を収集する。
【００６６】
サーバは、各装置の収集した位置から速度データを生成するように構成されてもよい。この速度データは、地図のナビゲート可能セグメントに沿う平均速度が計時変化する様子を示す時間で変動する速度プロファイルを含んでもよい。
【００６７】
図２は、説明している実施形態において、この例ではインターネットであるネットワークを介してナビゲーション装置において閲覧される電子地図の一例を示す。本明細書で説明している実施形態のいずれかにおける第１のステップは、そのような電子地図１９００の生成である。地図は、ｈｔｔｐ：／／ｒｏｕｔｅｓ．ｔｏｍｔｏｍ．ｃｏｍ／？Ｌｉｄ＝１＃／ｍａｐ／？ｃｅｎｔｅｒ＝５５．０１％２Ｃ−３．４４５＆ｚｏｏｍ＝４＆ｍａｐ＝ｂａｓｉｃで閲覧されてもよい。
【００６８】
図７の電子地図が行われる経路指定の目的で使用されるために、電子地図は一般に電子地図のユーザには見えない一連のノードを有する。従って、ノード等は一般に地図データと呼ばれてもよい。しかし、理解しやすいように、ノード３００の一部が図６に示される。これらのノードは、交差点、道路の最終領域等に提供され、経路指定の目的で使用される。ユーザが自身のナビゲーション装置に２つ以上の地点間の経路を計画するように要求する場合、一般にナビゲーション装置は地図の関連するノード間の経路を計画する（ノードのグループまでの経路を計画することも可能であるが）。従って、地図データは、ナビゲーション装置のユーザにより設定された少なくとも１つの基準に従って経路を生成するために使用される。
【００６９】
電子地図は、道路セグメントの形状、建物への入り口の場所等を提供する更なるノードを更に含んでもよい。
【００７０】
従って、各ノード３００は、ユーザが移動してもよいそのノードから出る道路セグメントを少なくとも１つ、一般には複数有する。例えばノード３０２は、４つのそのような道路セグメント３０４ａ、３０４ｂ、３０４ｃ、３０４ｄを有する。他の実施形態において、ナビゲート可能セグメントは、歩道、自転車道路、運河、鉄道線路又は軌道等の道路ではないパスを参照するパスのセグメントを示してもよい。しかし、便宜上、道路セグメントを参照する。従って、図７に示すような地図は、それぞれが地図によってカバーされるエリアのナビゲート可能な経路の一部を表す複数の道路セグメントをユーザに対して示す。
【００７１】
経路計画方法（ダイクストラ法、Ａ＊方法又はＭｏｏｒｅ／Ｐａｐｅ方法）は既知である。しかし、これらは、算出時間に関して非常に遅い。そのような経路計画の速度を向上する方法の一例は、米国特許第６，６３６，８００号公報で示され、その教示は参考として本明細書に取り入れられている。
【００７２】
本明細書で説明している実施形態は、前処理ステップにおいて、電子地図を処理する時に経路の生成を加速するためにナビゲーション装置によって使用される最低コストデータを含むいわゆる副ファイルを生成してもよい。この情報は、ビットベクトルと呼ばれてもよい２値データ、すなわち０及び１の列として保持されてもよい。従って、副ファイルは地図データと考えられてもよいが、電子地図（例えば、図７に示すような）が供給されてもされなくてもよい。従って、本発明のいくつかの実施形態は、副ファイルから分離可能な地図として地図データを提供してもよいが、本発明の他の実施形態は、地図及び副ファイルデータを組み合わせてもよい。
【００７３】
しかし、副ファイルが使用される場合、副ファイルが生成された電子地図と共に使用されるべきであることは、当業者には理解されるだろう。これが行われない場合、不正確な経路（例えば、ユーザにより設定されたコスト関数を最小限にしない経路）が取得されると考えられる。
【００７４】
また、本発明の種々の実施形態は、最低コストデータ（本実施形態においては、一連のビットベクトルである）の生成のための種々のパラメータを指定してもよい。従って、生成された地図データを使用する次の経路計画が最低コストデータを作成するのに使用されたパラメータとは異なるパラメータを使用する場合、最低コストデータはその経路計画に有用ではないと考えられる。
【００７５】
例えばいくつかの実施形態は、自動車による地図上の移動に対して最低コストデータを生成してもよい。次の経路計画が徒歩のための経路を生成するために使用される場合、自動車用の最低コストデータは有用ではないと考えられる。別の例において、いくつかの実施形態は、ユーザが高速自動車道路、有料道路等を喜んで移動すると仮定して最低コストデータを生成してもよい。次の経路計画において、ユーザが高速自動車道路、有料道路等を利用しない経路を要求する場合、最低コストデータは有用ではないと考えられる。
【００７６】
本発明のいくつかの実施形態は、それぞれが所定の基準の異なる集合を有する複数の最低コストデータの集合を生成してもよい。例えば本発明の実施形態は、２つ、３つ、４つ、５つ、６つ、１０個、１５個又はそれ以上の最低コストデータの集合のいずれを生成してもよい。
【００７７】
従って、いくつかの実施形態において、副ファイルを生成するために、地図前処理ステップにおいてノードは複数の領域に分割されるため、あらゆる地図は既知の数の領域、例えばＮ個の領域に分割され、領域間の最低コストパスが判定される。この前処理は、経路計画方法の速度を向上するために地図と共に利用可能なデータを生成する。
【００７８】
一般に前処理は、地図データがウェブサイト上で使用されるか又はＰＮＤ等の装置上で使用されるかに関わらず、地図データが使用される前に実行される。従って、前処理ステップは、サーバ側処理と呼ばれることが多い。
【００７９】
一般的なあらゆる演算装置が前処理を実行するのに適しているが、装置の性能が高い程、前処理は迅速に実行されることが当業者には理解されるだろう。一般に、Ｘ８６アーキテクチャ演算装置が前処理に利用される。一般にそのようなＸ８６アーキテクチャ装置は、Ｍｉｃｒｏｓｏｆｔ（登録商標）Ｗｉｎｄｏｗｓ（登録商標）、ＵＮＩＸ（登録商標）、ＬＩＮＵＸ（登録商標）、ＯＳＸ（登録商標）等のオペレーティングシステム（ＯＳ）を実行する。しかし、他の実施形態はＲＩＳＣアーキテクチャ等の他の演算プラットフォームを使用してもよい。
【００８０】
また、他で説明するように、前処理は並列に実行されてもよいため、複数の演算装置又は少なくとも複数のプロセッサコア（仮想又は実プロセッサコアであってもよい）で実行されてもよい。
【００８１】
次の前処理ステップとして、領域内の各道路セグメント（例えば、３０４ａ〜３０４ｄ）が処理され、それが地図内の領域数（Ｎ）の各々までの最低コストパスの一部であるかを判定し、ビットベクトルが生成される（最低コスト評価）。従って、領域内の道路セグメント毎のビットベクトルは、領域内のナビゲート可能セグメント毎のビットを含む。すなわち、ビットベクトルは、経路がビットで表された領域までの最短経路の一部を形成するかに依存して０又は１に設定されるＮ−１ビット（当該領域を除いた各領域に対して１ビット）を含む。いくつかの実施形態は、ヘッダ及び可視エリア等の更なる情報を提供するために追加のビットを追加してもよい。これらの用語については以下に説明する。
【００８２】
この意味で最低コストパスが複数の種々のコスト基準に対して判定されることは、当業者には理解されるだろう。例えば最低コストは、最短距離、最短移動時間、最安（環境的な影響に関して）、最小の使用燃料、最小の生成ＣＯ２等の基準のうちいずれかに対して判断されてもよい。本実施形態において、最低コストは最短移動時間に対して判断される。
【００８３】
本発明の本実施形態において、最低コストパスは、複数のコスト基準（コスト関数）の各々に対して判定される。それに対応して、結果として得られる副ファイルは、いずれか１つの時間に適用可能な２つ以上の最低コストパスをいずれか２つの領域間で特定してもよい。各最低コストパスは、異なるコスト基準（コスト関数）に対するものである。例えば最速経路に対する最低コストパスは、最も燃料効率の良い経路に対する最低コストパスとは異なる可能性がある。
【００８４】
従って、大きなエリアを範囲に含む地図の場合にＮが大きい可能性が高いことは、当業者には理解されるだろう。そのため、前処理には多くの時間がかかる可能性がある。
【００８５】
例えばヨーロッパ及びロシアを範囲に含む地図の一例において、一般に１００，０００，０００個の道路セグメントを有する４０，０００，０００個のノードが存在する。地図内に１００個の領域が存在すると仮定すると、Ｎは１００であり、１００，０００，０００ｘ１００（Ｎ）ビットが存在する。すなわち、１０ｘ１０９ビットは地図の道路セグメント毎に９９（すなわち、Ｎ−１）ビットを格納する必要がある。以下に説明する本発明の実施形態を使用すると、そのような地図は約５００Ｍｂの追加の記憶容量を使用してもよい。
【００８６】
国際公開第ＷＯ２００９／０５３４１０号は、時間の関数として地図のナビゲート可能セグメントに沿う速度を与える速度プロファイルを割り当てる方法を説明する。この出願の内容は、参考として本明細書に取り入れられている。従って、経路指定の目的で、あるナビゲート可能セグメントが別の領域までの最速経路の一部を構成するか否かは時間の関数として変動する。すなわち、例えばラッシュアワー等で、交通密度が増加するとナビゲート可能セグメントを使用するのが望ましくなくなり、交通密度が減少するとナビゲート可能セグメントを使用するのがより望ましくなる。
【００８７】
いくつかの実施形態は、道路セグメント毎に複数のビットベクトルを格納してもよい。速度が記録される際の解像度が高い程、必要とされるビットベクトル数は増加することが当業者には理解されるだろう。しかし、他の実施形態は、国際公開第ＷＯ２００９／０５３４１０号で説明するように時変関数を多く利用して最速経路の評価を行ってもよい。
【００８８】
電子地図にわたる経路計画の時、約１／１００秒の精度の時間粒度を使用してこれを行える必要があると考えられる。すなわち、最低コストの経路を正確に判定するために、０．０１秒の精度でノードからの出発時間を指定できる必要があると考えられる。
【００８９】
従って、このレベルの精度を考慮する場合、上記で考慮された地図に対して、４０，０００，０００個のノード及び１００，０００，０００個の道路セグメントを有することは１００，０００，０００２個の可能な経路を有することが理解されるだろう。時間次元が更に考慮される場合、可能な経路の数は更に増加する。すなわち、７（すなわち、１週間の日数）ｘ２４（すなわち、１日の時間数）ｘ３６００（すなわち、１時間の秒数）ｘ１００（すなわち、１秒間の１００分のいくつか）ｘ１００，０００，０００２＝６０４，８００，０００，０００，０００，０００，０００，０００（１０２１）個の可能な経路がある。現在の処理レベルで、各セグメントが各時間間隔で探索される単純な方法を使用すると、約１９，１７８，０８２，１９１，７８０，８２１年かかるだろう。出願人が現在販売しているヨーロッパ西部及び中央の地図は１２０，０００，０００個の道路セグメントを有しており、年々さらに大きくなっている。
【００９０】
従って、前処理段階でデータを格納及び処理するために多くのデータ量が必要とされることは理解されるだろう。
【００９１】
本発明の実施形態は、前処理の量を非常に低減するために技術を使用する。これらの技術について次に更に詳細に説明する。本発明のいくつかの実施形態はそれら技術の全てを利用してもよいが、他の実施形態は一部のみを利用してもよい。
【００９２】
本発明の種々の実施形態は、以下に概略を示す特徴の種々の組み合わせを使用してもよい。従って、いくつかの実施形態は、情報量を減少するために説明される技術の全てを利用してもよい。全く逆に、他の実施形態はデータを低減するためにそれら技術のいずれも利用しなくてもよい。
【００９３】
本発明のいくつかの実施形態は、ステップ１９０２として示すように、所定の基準を満たさない道路セグメントに対するビットベクトルを算出しない。例えば、所定の種類の交通機関で道路セグメントを移動できない場合、道路セグメントは自身に対するビットベクトルを算出しなくてもよい。
【００９４】
従って、交通機関のモードの基準が自動車に設定される一例において、以下の道路セグメントは自身に対するビットベクトルを算出しなくてもよい。
【００９５】
・鉄道線路
・道路セグメントに対応しない地図データに存在するセグメント
・間違った（不法な）方向の一方通行道路
・交通機関の形態によりナビゲート不可能な道路セグメント（例えば、自動車による運転性を考慮した時、歩行用ゾーン、歩道）
・非決定地点の道路セグメント（すなわち、道路セグメントから方向転換できない）。
【００９６】
ネットワークの縮小
１つの技術は、道路セグメントが最低コストの経路の一部を形成するかに関する評価に対して考慮されるネットワークのサイズを縮小することである。すなわち、ステップ１９０４で示すように、道路セグメント数を減少することにより算出を行うのにかかる時間が短縮される。
【００９７】
この技術を図示するために、図７に示すような道路ネットワークを図６に示すが、図６では最低コスト評価に有用でない道路セグメントが削除されている。ネットワークの縮小の目的は、最低コスト評価が行われるべき最小のサブネットワークを提供することである。
【００９８】
数学的には、残されたネットワークは、図７に示すように、図７の道路ネットワークの最大の強連結成分の無向表現の最大の２連結成分として記述される。コアネットワークは、右左折制限及びローカルアクセス等の道路交通規制に適応した双方の強い接続性（２連結性としても既知である）に対して一般的な技術を適用することにより判定される。強い接続性は、２つのノード間で双方の方向に移動が可能であること（すなわち、Ａ−＞Ｂ及びＢ−＞Ａ）を示すことが当業者には理解されるだろう。
【００９９】
図５及び図７の双方を参照すると、袋小路２５０、冗長ループ２５２等の行き止まりの道が削除されていることが分かる。しかし、ノード（例えば、図７の４００）は、除去された道路セグメントの出発地に残っていることが分かる。これは以下に説明する理由による。
【０１００】
コアネットワーク（例えば、図７に示す）に縮小後、コアネットワークは、上述した領域を提供するようにセグメントされる。説明している実施形態において、ネットワークは、多方向の円弧状の区切り記号に従ってセグメントされる。そのようなネットワークにおいて、領域境界により二等分される道路セグメント（すなわち、円弧）が除去される場合、いずれか一方の領域に残っている道路セグメントは他方の領域に接続されないことが当業者には理解されるだろう。
【０１０１】
ネットワークのセグメント−ステップ１９０６
しかし、セグメントの実行前に以下のステップが行われる。
【０１０２】
１．島が判定され、個々にセグメントされる。島は、フェリーリンク等の手段によりネットワーク及びリンクの他の部分から物理的に分離される傾向がある。これらは一般的な道路セグメントとは異なる挙動をし（すなわち、平均速度が非常に遅い等）、そのようなリンクがセグメントに含まれる場合、方法は実行されず、予想されてもよい。
【０１０３】
２．ネットワークにおいて２つ以上のノードで表される交差点、ロータリー及び他の分岐点は、同一の交差点等に属するノードが異なる領域で終了しないように短縮される。
【０１０４】
３．全てのナビゲート可能セグメントが同一のプロパティの集合（例えば、フェリーセグメント、運転禁止セグメント、通り抜け禁止セグメント等）を共有する単純なパス（すなわち、方向転換の可能性のない２つのノード間の接続）は、セグメントシステムに渡されるネットワークの入力サイズを縮小するために短縮される。例えば図６を見ると、ノード３０８は、道路３１０にまとめられてもよい。
【０１０５】
説明している本発明の実施形態は、ｈｔｔｐ：／／ｌａｂｒｉ．ｆｒ／ｐｅｒｓｏ／ｐｅｌｅｇｒｉｎ／ｓｃｏｔｃｈで概略を示される分割統治法を採用する。そこで概略を示される方法は、地図のエリアに基づかず領域内に含まれたノード数に基づく多くの領域を含むように地図を分割する。そのように編成されるノードを有することは、同様のローカル探索の直径を有する領域を出力するのを助長するため、領域を使用する経路指定をより効率的にすることを助長できるという利点を有する。
【０１０６】
各ノードは、領域ＩＤを含む関連付けられた特定番号を有するため、同一領域のノードは同一の領域ＩＤ番号を有する。ノードは、Ｌ個の階層レベルの領域に属する。レベル０は、慣例によって、最も粗なレベル（長い距離の経路指定に使用される）である。レベルＬ−１は最も精細なレベルである。
【０１０７】
いずれか１つの領域内に含まれるノードの絶対数を設定するのではなく、ノードの最大数の上限を設定し、これを下回る自由度を可能にすることは便利である。例えば方法は、領域毎に最大１００個のノードを指定してもよく、その結果、一般に６０〜１００個のノードの領域毎のノードの広がりが得られる。設定されたノードの数が結果として不自然な形状の領域を与え、それら領域を使用する場合に次善の経路指定が得られるため、上限は設定された数より有利であると考えられる。
【０１０８】
複数レベル
説明している実施形態において、複数のレベルのネストされた領域を提供するようにセグメントが行われる。これについては、図９に例示的に示す。最も粗なレベル（０）がレベル１を提供するように細分され、レベル１がレベル２に細分される階層性が存在することは図９から明らかである。
【０１０９】
各領域のノード数はレベル間で異なり、より粗なレベル（より広い地理的エリアを範囲に含む傾向がある）はより低いレベルより多くのノードを有する。従って、説明している実施形態におけるより粗なレベル（例えば、レベル０）は一般に長い範囲の経路指定の目的で使用され、より精細なレベル（例えば、レベル２）は短い範囲の経路指定に使用される。
【０１１０】
道路セグメント毎のビットベクトルの一部分はレベル毎にビットを含む。ビット数は、各レベルにおける領域数である。
【０１１１】
符号化するデータ量の概念を与えるために（一般的な一実施形態において、一般にレベル数はＬ＝３である）、以下を示す。
【０１１２】
・一般に、グローバルレベル＝０は１００個の領域を有する
・一般に、中間レベル＝１はレベル０の領域毎に１０個の領域を有する（すなわち、１００ｘ１０）
・一般に、最も詳細なレベル＝２は、レベル１の領域毎に５つの領域を有する（すなわち、１００ｘ１０ｘ５）
階層レベルを使用することは、必要とされる処理量を可能性として非常に減少させるため有利である。説明している本実施形態において、１００ｘ１０ｘ５個の領域（すなわち、５０００個の領域）である。従って、平坦な構造において、同数の領域を有することは５０００個の領域を参照するために本明細書で概略を示された方法を必要とする。しかし、本明細書で説明される実施形態において、これは適切なレベルのノードを参照することにより減少される。
【０１１３】
一般に、種々の因子が地図に対して分かると、レベル数及びレベル毎の領域数は変更される。例えば、地図に割り当て可能な記憶容量及び経路指定が実行されるべき速度である。前処理量が増加すると、データを保持するために地図のサイズが大きくなるが、より速い経路はその地図を使用して算出されるという調和があることが当業者には理解されるだろう。
【０１１４】
一実施形態において、３つのレベルの領域が存在する。しかし、他の実施形態において、レベルがいくつ存在してもよい。例えば、１つ、２つ、４つ、５つ、６つ、７つ、８つ、９つ又は１０個のレベルが存在してもよい。
【０１１５】
従って、上記例を使用して、一般に４０，０００，０００個のノード及び１００，０００，０００個の道路セグメントを有するヨーロッパの西部及び中央の地図において、最も単純な符号化は、各レベルの全てのノードの領域ＩＤに対する固定サイズの符号化及び各レベルの各道路セグメントに対する固定サイズのビットベクトル（ａｒｐフラグ）を使用する。従って、そのような基本的な符号化のサイズは以下のように容易に算出される。
【０１１６】
・レベル０の各ノード領域ＩＤはｌｏｇ＿２（１００）ビット＝７ビットを使用する
・レベル１の各ノード領域ＩＤはｌｏｇ＿２（１０）ビット＝４ビットを使用する
・レベル２の各ノード領域ＩＤはｌｏｇ＿２（５）ビット＝３ビットを使用する
・レベル０の各ビットベクトル（ａｒｐフラグ）は１００ビット（１００個の領域−現在の領域である１つの領域）を使用する
・レベル１の各ビットベクトル（ａｒｐフラグ）は１０ビット（１０個の領域−現在の領域である１つの領域）を使用する
・レベル２の各ビットベクトル（ａｒｐフラグ）は５ビット（５個の領域−現在の領域である１つの領域）を使用する
図９は、最も粗なレベルの領域６００を示す。図中、領域６００は６つの領域１〜６を提供する。これらの領域の各々は、領域６００の粗なレベル内の破線により表されるように、更なる領域、本実施形態では９つのサブ領域に細分される。説明している実施形態において、破線で提供された各領域が更に細分される更なる細分のレベルが使用され、これにより３つのレベルのセグメントを提供するが、これについては参照を分かりやすくするため図９には示さない。当然、他の実施形態はより多くのレベル（例えば、４つ、５つ、６つ、７つ又はそれ以上のレベル）又はより少ないレベル（例えば、１つ又は２つのレベル）を使用してもよい。
【０１１７】
従って、本発明の実施形態は、ステップ１９０８において、より精細なレベルの領域に対していわゆる可視エリアを導入する。ｋ領域の可視エリアは、（ｋ−１）領域の集合であり、領域はフラグセットの自身のビットで区別可能である。当然、可視エリアは所定のｋ領域が属する（ｋ−１）領域を常に含む。更に可視エリアは、近傍の（ｋ−１）領域を含んでもよい。可視エリアは、前処理中に計算され、ビットベクトルと関連付けられて格納される。
【０１１８】
ｋ領域とそれらの（ｋ−１）レベルの可視エリアとの関係は反対側から見られる。各（ｋ−１）領域は近傍にあるｋレベルの領域から構成される限界を認識している。このように考えると、道路セグメントのフラグセットは地図全体にわたり固定長ではない。その代り、各１領域のビットベクトルは、特定の長さＡ＋Ｂ＋Ｃ＋Ｎｏｕｔｓｋｉｒｔｓ０＋Ｎｏｕｔｓｋｉｒｔｓ１を有する。Ａは最も粗なレベルの領域を示し、Ｂは中程度の粒度を示し、Ｃは最も精細な粒度の領域を示す（３つのレベルが存在する一実施形態において）。
【０１１９】
次の前処理は、ビットベクトルを生成するための最短パスの算出前に可視エリアを計算する。可視エリアを見つける方法は以下のように説明される。
【０１２０】
各ｋ領域に関して、領域近傍グラフにおいて幅−第１探索を開始。その後、開始領域に十分に近接する訪問先ｋ領域毎に、含んでいる（ｋ−１）領域を可視エリアに追加する。
【０１２１】
「密接度」の関係は、地理的計測値（例えば、領域中点間の距離）及びグラフ理論距離を考慮に入れるべきである。（従って、領域は、地理的に遠いが高速接続により現在の領域とリンクされる場合に「近い」だろう。同様に、領域は、地理的に近くても領域間を移動するのが困難である場合は「遠い」と考えられるだろう。）
厳密な閾値は、前処理の増加等の上述した悪影響を最も受けやすい首都圏の平均直径のような地図固有のプロパティに依存するため実験的調整を行われてもよい。非常に長い移動時間がかかるナビゲート可能セグメント（フェリー又は運転禁止道路セグメント等）は隣接グラフの横断中隠蔽される。このように、可視エリアは同一領域に属する小さな列島又は単独の島に常に制限される。
【０１２２】
従って、幅優先探索中に訪問される領域はＲの近傍領域を構成する。近傍領域を完全に範囲に含む次に粗なレベルの領域の操作対象最小集合は、Ｒの可視エリアと呼ばれる。逆の関係は近傍と呼ばれる。領域Ｑ（レベルＬの）の近傍リストは、可視エリアにＱを有するレベルＬ＋１の全ての領域から成る。
【０１２３】
特定の例を与えるため、図６を参照すると、可視エリアの例は以下の通りである。
【０１２４】
各１領域とその可視エリアの境界との間の最短距離が少なくとも１であるべきであると判断した場合、いくつかの選択した１領域に対する可視エリアは以下の０領域（自身の０領域は常に存在するため省略される）から成る。
【０１２５】
・１５：
（すなわち、その０レベル領域の中心であるため、レベル１領域ｎｏ．１５は可視エリアを示さない）
・２８：５
（すなわち、レベル１領域ｎｏ．２８は領域（レベル０）ｎｏ．５である単一の可視エリアを含む）
・３７：２、５、６
（すなわち、レベル１領域ｎｏ．３７は３つの領域、すなわちレベル０領域ｎｏ．２、５及び６を有する）。
【０１２６】
レベル１領域のレベル０近傍領域を考慮することに加えて、レベル１近傍領域がレベル０領域毎に判定される。一例として以下を示す。
【０１２７】
・１：２１、２４、２７、２８、４１、４２、４３、５１
（すなわち、レベル０領域ｎｏ．１に対して、レベル１領域は２１、２４、２７、４１、４２、４３、５１である）
従って、この例において、領域２８が領域２の最も左側の列にないにも関わらず一覧表示されていることが分かる。例えばこれは、領域２８が領域１への迅速なリンクを有しているために距離ではなく時間に関して考慮された時に近いからである。密接度は、環境性（最少のＣＯ２等）等の他の計測値に対して判断されてもよい。
【０１２８】
近傍リストの符号化
図９ａは、図９と比較して採用されてもよいレベルの更なる詳細を示す。レベル０は、最も粗なレベルであり、レベルｋ−１と考えられてもよい。簡潔にするために、図６ａにおいて、領域１〜４のみが示される（すなわち、６０２、６０４、６０６、６０８）。ｋ−１領域の各々は、ｋレベル領域すなわちレベル１領域と呼ばれてもよい９つの領域（１〜９）に更に分割される。また、これらのレベル１領域の各々は４つのｋ＋１レベル領域（すなわち、レベル２領域）に分割される。
【０１２９】
ビットベクトルの生成
ネットワークが領域の３つのレベルにセグメントされると、ステップ１９１０において、それら領域の各々までの最低コストの経路を決定するために処理され、ビットベクトルは領域内の道路セグメント毎に作成される。従って、上述したように、いずれか１つの領域内の各道路セグメントは、他の各領域までの最低コストの経路の一部であるかを判定するためにコスト関数に関して解析される。ビットベクトルは、図７に示すように領域の全ての道路セグメントに対して生成される。図７は、理解しやすくするために簡素化されたビットベクトルを示す。
【０１３０】
最低コストの経路は、単一の期間で判定されるのではなく、以下に説明するように複数の期間に対して算出されることが理解されるべきである。
【０１３１】
この算出は、図７に示したネットワーク（すなわち、縮小されたネットワーク）に対して行われる。除去されたネットワークの部分は、出発地となるノードに効果的にまとめられる。例えば図５に示した領域２５０は、図７のノード４００にまとめられる。
【０１３２】
各ビットベクトルは３列含むことが分かる。最も左側の列７００は、考慮中の道路セグメントの開始のノードの特定番号を含む。第２の列７０２は、考慮中の道路セグメントの終了のノードの特定番号を含む。第３の列７０４はその道路セグメントのビットベクトルを含む。従って、各道路セグメントは、それぞれが道路セグメントの端部である２つのノードにより特定されることが分かるだろう。
【０１３３】
道路セグメントが最低コスト経路の一部であるかを判定するためにどのような適切な経路指定方法が使用されてもよい。特定の本実施形態において、既知のダイクストラ法がネットワーク全体を探索するために使用される。
【０１３４】
しかし、処理時間は種々の戦略を採用することにより短縮されてもよい。上述したネットワークを縮小する技術は、処理時間も短縮することが当業者には理解されるだろう。本発明の実施形態は、以下のうちいずれか１つ以上を採用してもよい。
・領域に対応する全てのビットベクトルエントリを１度に算出する。最短のパス木は、各境界ノードに対する逆グラフにおいて計算される。そのような方法は、各領域が並行に処理されることにより処理時間を短縮するため有利である。
・同様の最短のパス部分木の再計算を減少する。
・既に生成されたビットベクトルを再計算しない。
【０１３５】
従って、要約すると、一実施形態はビットベクトルを生成するために以下を実行してもよい。
【０１３６】
準備ステップ
１．当業者には理解されるように、電子地図にわたる探索は有向非周期グラフ（ＤＡＧ）により表される。このグラフ及び隣接するデータ構造（方向転換コスト及び長い範囲テーブル）が逆にされる。
【０１３７】
２．最も精細なレベルに対する単純な道路セグメントは短縮される（すなわち、他で説明するように、終端ノードは一方にまとめられる）。道路セグメントは、所定のレベルの同一の領域にある程度＝２の１つ以上のノードから構成される場合に単純であると言われ、ナビゲート可能セグメントは同一の属性を有する。例えば、「フェリーである」、「ＮｏＴｈｒｏｕｇｈである」及び「ＮｏＤｒｉｖｉｎｇである」である。
【０１３８】
３．道路ネットワークの道路セグメントは、領域毎に、先端（すなわち、ｆｒｏｍ＿ｎｏｄｅ）及び／又は末端（すなわち、ｔｏ＿ｎｏｄｅ）のノードがその領域に属するかに依存して、退出道路セグメント、進入道路セグメント及び内部道路セグメントの３つのグループにソートされる。すなわち、先端及び末端の双方が同一の領域内にある場合、道路セグメントは内部道路セグメントと呼ばれる。先端が領域内にあるが末端が領域内にない場合、道路セグメントは退出道路セグメントと呼ばれる。末端が領域内にあるが先端が領域内にない場合、道路セグメントは進入道路セグメントと呼ばれる。
【０１３９】
４．特別な右左折制限は、ＮｏＴｈｒｏｕｇｈ及びＮｏＤｒｉｖｉｎｇエリアを出る全ての道路セグメントに設けられる。
【０１４０】
前処理ルーチンは、最も精細なセグメントレベル、すなわち説明している実施形態においてはレベル２から開始してボトムアップ方式で進む。領域の各レベルにおいて、以下のステップが領域Ｒ毎に繰り返される。
【０１４１】
１．Ｒの探索エリアを判定する。最上位レベル（例えば、説明している実施形態においては領域０）においてはグラフ全体であり、より精細なレベルにおいてはＲの可視エリアにより制限された部分グラフである（上述したように）。
【０１４２】
従って、中間レベル（すなわち、レベル１）において、以下のステップはレベル１領域が含まれるレベル０領域の可視エリアに対してのみ実行される。レベル０において、長い範囲の経路指定に対して使用されることを注意すべきであり、グラフ全体の道路セグメントが考慮される。
【０１４３】
可視エリアの進入道路セグメント、すなわちエリア外のノードからエリア内に至る道路セグメントを収集する。その後、境界付近の道路セグメント、すなわち進入道路セグメントに続く道路セグメントを収集する。先端（Ｌ１）＝末端（Ｌ２）でありＬ１からＬ２への方向転換が禁止されていない場合、道路セグメントＬ２はＬ１に続くと言われる（且つＬ１はＬ２に先行する）。複雑な交差点は、境界付近の道路セグメントを見つける目的で単一のノードに短縮される。フェリー道路セグメント及び「ＮｏＤｒｉｖｉｎｇ」属性を有する道路セグメントは境界付近の道路セグメントと考えられない。
【０１４４】
このように進入道路セグメントを収集することにより、後述する探索ステップで必要とされる処理量を可能性として非常に減少できる。探索ステップは、進入経路を含む所定の領域までの経路を考慮するためにグラフの探索を減少できる。
【０１４５】
２．Ｒの退出道路セグメント毎に、ルート道路セグメント及び探索ステップ数を見つける。退出道路セグメントがＲ内にある先行道路セグメントの少なくとも１つの唯一の後続道路セグメントである場合、この退出道路セグメントは唯一のルート道路セグメントであり、単一の探索ステップが実行される。あるいは、退出道路セグメントが双方向である場合（すなわち、双方向に運転可能である場合）、道路セグメント自体及びその反対の（進入）道路セグメントは単一の探索ステップのルート道路セグメントとして利用される。あるいは、退出道路セグメントが一方向である場合、先行する各内部道路セグメント（及び存在する場合はその反対の道路セグメント）は別個の探索ステップのルート道路セグメントとして利用される。最後に、退出道路セグメントの種類に関係なく、退出道路セグメントを通る交通範囲パス毎に、範囲の開始道路セグメント（Ｒ内にある場合）は別個の探索ステップのルート道路セグメントとして利用される。
【０１４６】
より精細なレベル（すなわち、レベル０以外の全てのレベル）において、退出フェリー道路セグメントは特別に処理される。上述したように、フェリー道路セグメントは、領域の近傍領域を判定する時に無視される。フェリー道路セグメントの先端領域がＲの可視エリアに属さない場合、フェリー道路セグメントが唯一のルート道路セグメントであり且つ探索エリアが先端領域自体に制限された状態で単一の探索ステップが実行される。
【０１４７】
３．スケジュールされた探索ステップを実行する（以下に説明する）。
【０１４８】
４．探索エリア内の道路セグメントからルート道路セグメントまでの最短パスを辿る。最上位（すなわち、レベル０）以外の全てのレベルにおいて、辿ることを開始する道路セグメントの順序は結果に影響を及ぼす。ＲがレベルＬ領域（Ｌ＞０）であるとすると、レベル（Ｌ−１）領域の退出道路セグメントは最初に処理され、その後、レベルＬの残りの退出道路セグメント等、最も精細なレベルに向かって処理される。すなわち、最も精細なレベルに関して内部にあり（且つまだ除去されていない）道路セグメントが最後に処理される。先に辿った時に既に訪れた道路セグメントに遭遇した場合、２度目にそのパスに従う必要はない。辿っている間、適切な目標ビットベクトルが訪れた道路セグメント毎に設定される。最上位レベル（すなわち、レベル０）以外の全てのレベルにおいて、以下の追加の動作が行われる。
【０１４９】
パスがあるレベルＬ領域の境界を初めて横切った後、その境界道路セグメント及びルート道路セグメントまでの途中にある全ての更なる道路セグメントは通過線フラグにより印がつけられる。
【０１５０】
最短パスがＵターンをするノードは、Ｕターンフラグで印がつけられる。
【０１５１】
最後に、最も精細なレベル以外の全てのレベルにおいて、相関行列エントリが満たされる。
【０１５２】
そのレベルの全ての領域が処理された後、グラフは次のレベルに対して簡素化される。最初に、通過線として印をつけられなかった全ての道路セグメントが除去される。その後、増加する新しい単純なパスは短縮される。Ｕターンノードとして印をつけられたノードは保存される。
【０１５３】
最後に、ビットベクトルは、相関行列に従って、このレベルを処理する前に除去された道路セグメントに伝播される。
【０１５４】
相関行列
本発明のいくつかの実施形態は、道路セグメント上にビットベクトルを設定するのに必要な目標領域の間の関係を格納する相関行列を使用する。最も精細なレベル以外の各レベルＬにおいて、新しい相関行列が作成され且つ使用される。レベルＬにおいて、行列の行は、レベル（Ｌ＋１）領域により指標をつけられ、列はレベルＬ領域により指標をつけられ、各行列エントリは０個以上のレベル（Ｌ＋１）領域の集合である。より低いレベルにおいて、殆どの行列エントリが空の集合と等しい。すなわち、行列は疎である。
【０１５５】
相関行列の目的は、早い段階で削除された道路セグメントにビットベクトルを設定することを助長することである。これらの道路セグメントは、レベルＬの探索ステップの結果として得られた有向非周期グラフに含まれないが、削除されなかった場合は含まれる。より詳細には、相関行列は、あるレベル＞Ｌの算出中に削除されたＳの探索エリアの道路セグメントのあるレベルＬ領域Ｓ（Ｌは最も精細なレベルではない）にビットベクトルを設定するために使用される。Ｓの探索エリアに含まれたレベル（Ｌ＋１）領域Ｒの場合、行列成分Ｍ［Ｒ，Ｓ］は、ＳからＲまでの全ての最短パス（逆グラフにおける）が１つの領域を通過するように、最終的にＲの可視エリアの境界にあるレベル（Ｌ＋１）領域の集合となる。
【０１５６】
行列が作成される場合、全てのエントリは空の集合に初期化される。その後、全てのレベルＬ領域Ｓに対して、以下の２つの動作が行われる。
【０１５７】
１．行列の構築：Ｓのルート道路セグメントｌ及び結果として得られる有向非周期グラフＤを使用する各探索ステップに対して、Ｓの探索エリアに含まれた各レベル（Ｌ＋１）領域Ｒに対して、並びにＲの各進入道路セグメントｌ’に対して、行列成分Ｍ［Ｒ，Ｓ］が以下のように更新される。
【０１５８】
Ｒの探索領域をＡで示す（レベルＬ＋１に対して早い段階で算出されたように）。ｌ’からｌまでのＤにおけるパスを辿り、Ａを出たかを検査する。すなわち、Ｔが依然としてＡに含まれるがＴ’は含まれない状態で、このパス上の道路セグメントがレベル（Ｌ＋１）領域Ｔからレベル（Ｌ＋１）領域Ｔ’まで通っている場合、Ｔは集合Ｍ［Ｒ，Ｓ］に追加され、次のｌ’が処理される。
【０１５９】
２．行列を読み出す：レベルＬ算出が開始する前に削除されたＳの探索エリアの各道路セグメントに対して、Ｒを道路セグメントが終了する（ここでも、逆グラフに対して）レベル（Ｌ＋１）領域とする。ここで、その線上の領域Ｓに対するビットベクトルのビットは領域Ｔのビットベクトルの論理和に設定される。尚、ＴはＭ［Ｒ，Ｓ］の全ての要素に及ぶ。
【０１６０】
尚、Ｔ毎のビットベクトルのビットは、ある有向非周期グラフから直接又はより低いあるレベルにおいて相関行列を含む同様の手順で、より早いレベルで設定される。
【０１６１】
探索
探索ステップは、所定の道路セグメント（対）を根とする最低コストパスの有向非周期グラフを構築することから成る。これは、最低コストパスの計算に対して既知のダイクストラ法の一変形例を使用することにより達成される。実際には、最小にされる目的関数が、例えば移動時間又は推定された燃料消費又は他で説明される他の因子のいずれかとして自由に選択される。
【０１６２】
一実施形態は、移動時間、パスの長さ、並びに望ましくない方向転換及び操作を抑制する他のペナルティ条件の加重和を使用する。
【０１６３】
以下の変形が従来の（ダイクストラ）方法に行われる。
【０１６４】
１．道路セグメントグラフに対して動作する。すなわち、訪れた項目、緩和された項目等がノードではなく道路セグメントである。これは、方法が右左折制限及び／又は交通範囲を考慮することを可能にするのに有用である。
【０１６５】
２．ラベルの目的関数は、ルート道路セグメントにおける到着タイムスロットの固定の集合に対する対（移動時間、コスト）のベクトルである。タイムスロットは、全ての関連交通モードが範囲に含まれるように（自由流れ、平日の朝のラッシュアワー、夕方のラッシュアワー等）選択される。これについては、複数の期間におけるコストの評価に関する説明において以下に更に詳述する。
【０１６６】
３．２つ以上のラベルが所定の道路セグメントに対して格納される。２つのラベルにおける保留中（未完了）の交通範囲の集合が等しくない場合、ラベル自体は独立していると言われ、後続する道路セグメントにわたり伝播し続ける。あるいは、種々の到着タイムスロットに対するコスト関数値の間の関係は交互にならない。すなわち、一方のラベルが他方のラベルより良いのは明確であり、悪い方のラベルは廃棄される。そうでなければ、新しいラベルがタイムスロット毎の良い方の値をマージすることにより作成され、これは元のラベルの代わりに伝播される。先行するマージされたラベルの集合は、先行する元のラベルの集合の結合である。
【０１６７】
４．特別なＵターンラベルは、双方向の各道路セグメントにおいて作成される。それらラベルは、双方向の実際の（逆にされていない）経路を開始する可能性を符号化する。Ｕターンラベルは伝播されず、通常のラベルとマージされなくてもよい。しかし、それらラベルは、ビットベクトルが設定される時に追跡段階に影響を及ぼす。すなわち、開始ラベルが同一道路セグメント上のＵターンラベルより悪くない場合のみ、最短パスはフラグを立てられる。
【０１６８】
５．探索エリアが領域の集合に制限されるより精細なレベルにおいて、上記で規定したような境界付近の道路セグメントは永続的に監視される。全ての境界付近道路セグメントに探索面が到達するとすぐに、監視コームはタイムスロット毎の最大（＝最悪）のコスト関数値から構築される。その後、コスト関数値が少なくとも１つのタイムスロットにおいて現在の監視コームを下回る場合にのみ、探索エリア外の道路セグメントのラベルはヒープを出た時に伝播される。探索エリアがいくつかの島に及ぶ場合、別個の監視コームが島毎に維持される。
【０１６９】
時変関数
本発明のいくつかの実施形態は、単一の時間ではなく複数の期間においてネットワークにわたる最低コストの経路を示すビットベクトルを算出してもよい。道路ネットワークにわたる最低コストの経路は、交通密度の影響等により計時変化する可能性があることが当業者には理解されるだろう。従って、あらゆる１つのノードに対して、それぞれが種々の時間に対するものである２つ以上の最低コストパスが存在してもよい。本実施形態において、ビットベクトルは、最低コストパスが適用可能である場合に対して時間参照により符号化されない。ビットベクトルは、最低コストパスの一部であるとして又は一部でないとしてナビゲート可能セグメントを特定するために単純に設定される。従って、最低コストデータを使用して経路指定する場合、経路指定アルゴリズムはノードからの可能な全ての最低コストパスを考慮する必要がある。この処理については、図１０ａを使用して次に簡単に説明する。
【０１７０】
ネットワークの一般的なダイクストラ探索において、ネットワークが探索されると、方法はネットワークのその地点に到達するために現在までに発生した合計コスト＋まだ発生していない予想されるコストを使用する。
【０１７１】
従って、いくつかの実施形態は、各ノードにおいてコスト評価を行うために別個の値とは対照的に関数を利用する。図１０ａにおいて、探索されているグラフ７５１の各ノード（例えば、７５０）はコスト関数と関連付けられ、これは、探索されているパラメータ（例えば、時間又は消費燃料等）が計時変化する様子を特定する。
【０１７２】
コスト関数は、ノードとは対照的に道路セグメントと関連付けられてもよい。
【０１７３】
方法は費やしたコストを処理し、新しい関数を生成するために現在までに蓄積したコストを有する現在のノードにおいて関数を合計することにより推定されたコストを加算する。図７ａの７５２で示した例は、探索方法によりノード７５０で生成されたコスト関数を示し、移動時間（ｙ軸）が出発時間（ｘ軸）に伴って変化する様子を示す。朝及び夕方のラッシュアワーのために移動時間がポイント７５４及び７５６において増加していることが分かる。
【０１７４】
特定の一実施形態において、コスト関数（例えば、道路セグメントの平均速度）は５分間隔で格納される。すなわち、これは５分間に変化し続ける関数ではなく量子化関数である。
【０１７５】
道路セグメントに対するビットベクトルは、その道路セグメントがどの期間においてもどのコスト関数に対しても最低コスト経路（最低コストパス）の一部である場合に設定される。
【０１７６】
完全なネットワークへのコアデータの投影
セグメント方法により考慮される必要があるノード及び道路セグメントの数を減少するために地図に含まれたネットワークを縮小する方法について上述した。しかし、経路指定方法が削除された道路セグメント及びノードに対する経路を依然として生成できるようにするためには、縮小ステップで削除されたノードも更に考慮されるべきである。
【０１７７】
従って、削除されたノード及び道路セグメントは、それらがコアネットワークにおいて接続されるノードと同一の領域に割り当てられる。
【０１７８】
圧縮
上述したように、生成されたビットベクトルはサイズが大きいため、情報を圧縮するのが望ましい。本発明の実施形態は、これを種々の方法で実行してもよい。しかし、一実施形態は、ビットベクトルを圧縮、結合及び／又は相関し、その後ビットベクトルのハフマン符号化を行う種々の技術を利用する。
【０１７９】
いくつかの実施形態は、ビットベクトルの不均一な分布があることを保証しようとしてもよい。これは、そのような分布がない場合よりハフマン符号化が効率的であることを保証するのを助長できるからである。
【０１８０】
例えばビットベクトルが以下のように分布される場合、
００００．．．．（時間の４９％）
１１１１．．．．（時間の４９％）
？？？？．．．．（時間の２％）
以下のようなより不均一な分布を有するようにハフマン符号化前のビットベクトルを操作するのが望ましい。
【０１８１】
００００．．．．（時間の７９％）
１１１１．．．．（時間の１９％）
？？？？．．．．（時間の２％）。
【０１８２】
生成されたビットベクトルの縮小
生成される必要があるビットベクトルの量を減少するために、本発明の実施形態は、以下の戦略のうちいずれか１つ以上を使用してもよい。
【０１８３】
・領域ＩＤは、全てのノードに対して使用されるわけではなく、ナビゲート可能ノードに対してのみ生成される（例えば、鉄道線路に対応するノードは無視される）。
【０１８４】
・ビットベクトルは、全ての道路セグメントに対して必要とされるわけではなく、決定ノードの周囲の決定道路セグメントに対して使用されてもよい。決定ノード＆決定道路セグメントは道路セグメントデータを見ることにより判定される（本明細書で説明されるように）。
【０１８５】
・可能なビットベクトルが多く存在するが、その一部はその他のビットベクトルよりはるかに頻繁に発生するため、特定の符号化は最も頻度の高いビットベクトル（例えば、０００．．．０００及び１１１．．．１１１）に対して使用される。
【０１８６】
・多くの場合、０００．．．０００でも１１１．．．１１１でもないビットベクトルは、それらの殆どのビットが１に設定されているか又は０に設定されている。従って、部分ブロックのハフマン符号は、それらを非常に効率的に符号化すべきである。
【０１８７】
・ビットベクトルは、多くの場合に互いに近接するノードにおいて同一であるため、デルタ符号化がそれらを効率的に符号化できる。
【０１８８】
・種々の領域は、ソース領域毎に行先領域ＩＤを再順序付けすることにより、より類似するビットベクトルパターンを有するようにされてもよい（概念は本明細書において説明する）。
【０１８９】
・ノードの道路セグメントの周囲の全てのビットベクトルは、常に１１１．．．１１１を与えるべきである。これはビットベクトルを更に効率的に符号化するために適切に使用される。
【０１９０】
これらのうちの一部について、以下に更に詳細に説明する。
【０１９１】
尚、この時点では、本明細書で説明される技術の目的はビットベクトルのサイズを縮小することである。しかし、経路指定の目的で地図データを使用する装置によりデータへのランダムアクセスが必要とされる。しかし、一般に、データの効率的な符号化にはデータへのランダムアクセスを防止する可変サイズが必要とされる。
【０１９２】
従って、本発明の実施形態は、データが指標をつけられる一連のページとして符号化され且つそれらのページ内で可変符号化を利用するというトレードオフの関係を使用してもよい。そのような実施形態において、ランダムアクセスは各ページに対して達成可能である（指標をつけることにより）。ページがアクセスされると、実施形態はページ全体を復号化してもよい。これにより、効率と地図のサイズとの間にはトレードオフの関係が提供される。ページ毎のノード数を増加すると地図のサイズは減少するが、データアクセスは遅くなる。本発明の特定の一実施形態は、ページ毎に１６個のノードを使用する。いずれか１つのノードは、そのノードを出る異なる数の道路セグメントを有してもよいことが理解されるだろう。従って、同数のノードが存在してもよいが、ページ毎の道路セグメントの量は可変であってもよい。更に、各ページに格納されたビットベクトルの各々に対して異なる圧縮が適切に行われてもよい。
【０１９３】
そのような構造により、図１１に示す地図形式が得られる。この図において、Ａｒｐフラグへの参照は、ビットベクトルと同様である。数字「ｎ」は、ヘッダ内に格納され、その地図に対して性能を最適化するために種々の地図に対して変更されてもよい。
【０１９４】
「ｎ」を調整することは、地図データを復号化する時のアクセス速度と地図のサイズにはトレードオフの関係がある。
【０１９５】
・大きな値のｎは多くのノードをグループ化する。これは、地図の圧縮には適切であるが、データへのランダムアクセスの速度には不適切である。
【０１９６】
・小さな値のｎは殆どのノードをグループ化しない。これは、データのランダムアクセスの速度には適切であるが、地図の圧縮には不適切である。
【０１９７】
・「ｎ」は例えば４に設定されてもよい。すなわち、１６個の出発ノード（出発ノードは道路セグメントの開始点あり、すなわち図１０の列７００である）から成るページであるが、各出発ノードはいくつかの到着道路セグメントを有する。平均で３つの到着道路セグメントを有すると仮定すると、各ページが〜４８個の道路セグメントを格納することを意味する。
【０１９８】
この形式において、符号化される領域のレベルに依存してデータに対する異なる形式が存在する。図１２は、レベル０（すなわち、最も粗な領域）に対する形式の一例を示し、図１２は、領域の他のレベルに対する形式の一例を示す。
【０１９９】
ビットベクトル及び関連情報はデータ構造に格納され、その形式を図１１に示す。図１１は、ヘッダ８００、後述するハフマン符号化で使用されるハフマン木８０２、各階層における領域数８０４（レベル毎の領域数が一定の場合は空）、近傍領域８０６（近傍領域がない場合は空）、領域ＩＤ再マッピングテーブル８０８、ビットベクトルページ指標（２ｎ個のノード）８１０、並びに領域ＩＤ及びビットベクトル８１２を含む。ビットベクトルを保持するデータ構造は、単一のファイル内に保持されてもよく、あるいは複数のファイル内に保持されてもよい。
【０２００】
いくつかの実施形態において、地図ヘッダ８００は、以下を示す更なる情報を含むように構成される。
【０２０１】
・レベルの最大数
・最短近傍リストの長さ
・最長近傍リストの長さ
・全ての近傍リストを含むセクションのバイトオフセット。
【０２０２】
情報を保持する各ファイルは、近傍リストを符号化するためにセクションを有してもよい。全てのリストのサイズがまず符号化される。リストの各長さは、最短リストの長さに対して、ＢｉｔｓＲｅｑｕｉｒｅｄ（ｌｏｎｇｅｓｔＬｉｓｔＬｅｎｇｔｈ−ｓｈｏｒｔｅｓｔＬｉｓｔＬｅｎｇｔｈ）により判定された固定のビット数に符号化される。尚、全てのリストが同一の長さを有する場合、長さを符号化するのにビットは必要ない。
【０２０３】
その後、全てのリストの内容に従う。各リストは、近傍領域ＩＤのいくつかのタプル、すなわちレベル０ではいくつかの対、レベル２では３つの要素のいくつかのタプルから成る。
【０２０４】
尚、出発領域タプル（ＡＳＣＩＩファイルの「：」の前の部分）は符号化されない。これらは、リストが全ての領域に対して昇順に格納されるため黙示的である。例えば地図が１００ｘ１０ｘ５（レベル０の１００個の領域、レベル１の１０個の領域、レベル２の５つの領域）を有する３つのレベルを有する場合、以下の通りである。
【０２０５】
・レベル０において、リストは出発領域１、２、３、．．．１００（この順序で１００個のリスト）に対して格納される。これらリスト各々は対を含む。
【０２０６】
・レベル１において、リストは出発領域１．１、１．２、１．３、．．．１．１０、２．１、２．２、．．．２．１０、３．１、．．．１００．９、１００．１０（この順序で１０００個のリスト）に対して格納される。これらのリストの各々は、３つの要素のタプルを含む。
【０２０７】
・レベル２において、これは最後のレベルであり近傍領域が存在しないため、何も格納されない。
【０２０８】
タプルの各成分はｎビットとして格納される。レベル毎のビット数は、対応するレベルの領域数から判定される。従って、リストにランダムにアクセスできる。３つのレベルの１００ｘ１０ｘ５の場合、タプルａ．ｂ．ｃを符号化するには、ａに対しては７ビット（レベル０の領域が１００個存在するため）、ｂに対しては４ビット（レベル１の領域が１０個存在するため）及びｃに対しては３ビット（レベル２の領域が５つ存在するため）を使用する。
【０２０９】
例：１００ｘ１０ｘ５個の領域、すなわち粗レベル０の１００個の領域、中間レベル１の１０個の領域及び詳細レベル２の５つの領域のセグメントを仮定する。
【０２１０】
レベル０のファイルにおいて、近傍リストを含むセクションは以下を含む。
【０２１１】
・レベル０の１００個の領域に対するリストの長さを示す１００個の番号。ビット数は、ＢｉｔｓＲｅｑｕｉｒｅｄ（ｌｏｎｇｅｓｔＬｉｓｔＬｅｎｇｔｈ−ｓｈｏｒｔｅｓｔＬｉｓｔＬｅｎｇｔｈ）から算出される。各番号は、そのレベルの最短リストに相対的である（最短リストはヘッダに格納される）。
【０２１２】
・その後、１００個のリスト（１００対）の内容に従う。各対の第１の要素は７ビット（レベル０の領域が１００個存在するため）に符号化され、各対の第２の要素は４ビット（レベル１の領域が１０個存在するため）に符号化される。
【０２１３】
レベル１のファイルにおいて、近傍リストを含むセクションは以下を含む。
【０２１４】
・・レベル１の１０００個の領域に対するリストの長さを示す１００＊１０＝１０００個の数字。
【０２１５】
・・１０００個のリスト（１０００個の３つの要素のタプル）の内容に従う。各タプルの第１の要素は７ビット（レベル０の領域が１００個存在するため）に符号化され、各タプルの第２の要素は４ビット（各レベル０領域においてレベル１の領域が１０個存在するため）に符号化され、各タプルの第３の要素は３ビット（各レベル１領域においてレベル２の領域が５つ存在するため）に符号化される。
【０２１６】
レベル２のファイルにおいて、これは最後のレベルであるため、何も格納する必要がない。
【０２１７】
符号化入力ファイルに関して、複数のリストのフォームの何れかが適合されてもよい。
【０２１８】
このように、３つのレベルへの分割が実行されると、各ノードは、１つのレベルあたり１つの領域、即ち、３つの領域に割り当てられる。
【０２１９】
ヘッダ８００
一般に、本発明の実施形態で使用されるヘッダは小さく、従ってそのサイズを縮小するためにサイズを最適化する必要はない。一般に、全てが便宜上位置合わせされたバイト又は単語である。
【０２２０】
・（４バイト）符号化バージョン（地図形式が変更される度に増加する）
・（４バイト）地図フラグ（機能をＯＮ又はＯＦＦする。最初は０であるが、オプションの機能を追加する必要がある場合に後で使用される）
・（４バイト）地図中のノードの合計数
・（４バイト）地図中の道路セグメントの合計数
・（４バイト）ハフマン木セクションのバイトオフセット
・（４バイト）領域ブロブセクションのバイトオフセット
・（４バイト）領域ページ情報セクションのバイトオフセット
・（４バイト）ビットベクトルページ情報セクションのバイトオフセット
・（４バイト）可変サイズレコードセクションのバイトオフセット
・（４バイト）ビットベクトル（ａｒｐフラグ）ページの最大ビット数（起動時にビットストリーム復号器に対して悪い例を事前に割り当てるために経路計画方法により使用される）
・（４バイト）平均ビットベクトル（ａｒｐフラグ）ページサイズのビット数（ビットベクトルページ位置を補間するために使用される）
・（４バイト）最小ビットベクトル（ａｒｐフラグ）ページデルタ（全てのデルタを＞＝０にするために使用され、ビットサインを格納することを回避する）
・（２バイト）ビットベクトル（ａｒｐフラグ）履歴の最大サイズ（起動時に履歴バッファを事前に割り当てるために経路計画方法により使用される）
・（２バイト）ページ毎の道路セグメントの最大数（現在使用されていない）
・（１バイト）このファイルのアポロレベル
・（１バイト）ビットベクトル（ａｒｐフラグ）毎のビット
・（１バイト）ビットベクトル（ａｒｐフラグ）ページデルタ毎のビット（ビットベクトル（ａｒｐフラグ）ページの固定サイズレコードのフィールド）
・（１バイト）ブロブ指標毎のビット（領域ページ情報の固定サイズレコードのフィールド）
・（１バイト）領域数毎のビット（領域ページ情報の固定サイズレコードのフィールド）
・（１バイト）非自明なビットベクトル（ａｒｐフラグ）ブロック毎のビット
・（１バイト）領域ノードページサイズのｌｏｇ＿２（）
・（１バイト）ビットベクトル（ａｒｐフラグ）ページサイズのｌｏｇ＿２（）
・（１バイト）ローカル領域ＩＤを符号化するためのハフマン木の数
・（１バイト）ビットベクトル（ａｒｐフラグ）履歴符号を符号化するためのハフマン木の数。
【０２２１】
ハフマン木８０２
・各ノードの周囲の道路セグメント数を符号化するためのハフマン木。小さく、１０個ほどの符号がレベル０のファイルにのみ存在する）
・非自明なビットベクトル（ａｒｐフラグ）のブロックを格納するためのハフマン木。最大のハフマン木であり、大きい程、圧縮に適切であるが、経路計画方法で必要とされるメモリは多くなる（経路計画方法でのメモリの使用量と地図圧縮との間のトレードオフの関係）。
【０２２２】
・履歴サイズが０である場合のビットベクトル（ａｒｐフラグ）デルタ符号のハフマン木。小さく、符号を３つだけ含む。
【０２２３】
・履歴サイズが１である場合のビットベクトル（ａｒｐフラグ）デルタ符号のハフマン木。小さく、符号を４つだけ含む。
【０２２４】
・履歴サイズが＞＝ｎである場合のビットベクトル（ａｒｐフラグ）デルタ符号のハフマン木。小さい（ヘッダに格納されたハフマン木の数）。
【０２２５】
・領域ページに３つの領域が存在する場合の領域ＩＤに対するハフマン木。小さく、符号を３つだけ含む。
【０２２６】
・領域ページに４つの領域が存在する場合の領域ＩＤに対するハフマン木。小さく、符号を４つだけ含む。
【０２２７】
・領域ページに＞＝ｎ個の領域が存在する場合の領域ＩＤ対するハフマン木。小さい（ヘッダに格納されたハフマン木の数）。
【０２２８】
領域再マップテーブル８０４及び領域ＩＤリスト８０６
図８のファイル形式の他の部分より小さいが、領域ＩＤ８０６は、図１１に例示するように圧縮されてもよい。ここで、使用されるデータ量を減少するために、地理的相関が使用されてもよい。
【０２２９】
各領域ページは、その領域ページの別個の領域のリストを格納する。このリストは、殆どの場合に小さいと予想される（実際には、多くのページは少なくともレベル０の領域を１つだけ含む可能性が高い）。領域のリストは可変サイズを有する。ページ内のデータは、ランダムにアクセス可能であるべきであり（すなわち、ランダムアクセス）、固定テーブルサイズはこれを可能にするために使用される。
【０２３０】
別個の領域の各リストは、各領域のノードの頻度により順序付けされる。リストの第１の要素は、ページ中の最大数のノードを含む領域に対応し、リストの再度の要素は、ページ中の最小数のノードを含む領域である。
【０２３１】
領域ページの各ノードにおいて、ローカル領域ＩＤ（ページにローカルな）を使用してその領域ＩＤを符号化できる。このローカルＩＤは、ページ中の領域の指標である（これは小さい整数であり、０は領域ページの最も一般的な領域に対応するため、多くの場合は０である）。
【０２３２】
ノードの領域ＩＤは以下のように格納される。
【０２３３】
・領域ＩＤ’を含む領域配列はページ中の領域の可能な重複リストを全て格納する。領域のリストは、その配列において連続した領域ＩＤである。リストは、重複してもよい（重複する）。配列は各リストの開始及び終了を格納しない（これは、領域ページ情報テーブルにより行われる）。
【０２３４】
・領域ページ情報テーブルは固定サイズレコードテーブルであり（従って、ランダムにアクセス可能である）、各レコードはリストの開始の配列における指標＋リスト中の項目数を含む。
【０２３５】
・各ノードはローカルノードＩＤ（そのページにローカルな）を含む。
【０２３６】
これらの概念の各々については、以下に更に規定する。
【０２３７】
領域配列
領域配列は、ページの全ての可能な領域リストを符号化する。領域ＩＤのリストが重複してもよい領域ＩＤの単純な配列である。そのサイズは、リストが重複するため小さい。領域配列については、領域ページ情報の節で更に説明される。
【０２３８】
領域ページ情報
領域ページテーブルの領域ＩＤのリストを指定するには、領域ページ情報テーブルの固定サイズレコードの２つのフィールドを使用する。
【０２３９】
・領域数（このページの領域数であり、小さいと予想される）
・領域リストの配列へのオフセット（ここで領域のリストが開始する）
一実施形態において、これについては図１２で説明する通りである。
【０２４０】
オフセットフィールドは領域配列を示す。領域ＩＤ毎に１バイトの固定サイズレコードで十分である。例えば、各レベルには２５６個未満の領域が常に存在すると仮定する。これは妥当な仮定である（しかし、レベル毎に２５６ビットというのは制限しすぎであると考えられる場合、８ビットより大きくすることは容易に可能である）。領域ページテーブルレコードの領域数は、指定されたオフセットで配列にあると考えられる領域数を示す。
【０２４１】
いくつかの領域が同一リストを有する場合、それらは同一の場所を示せる。これは、多くのページが同一リストを共有するか又は同一リストの部分を共有することが予想できるためコンパクトであるべきである。
【０２４２】
これについては、図１２を参照して更に詳細に説明する。図１２は、２＾ｎｒ個のノード（例えば、５１２個のノードをグループ化するためにｎｒ＝９）のページを有する一実施形態を示す。
【０２４３】
尚、いくつかのページが配列において同一の場所又は重複する場所（図中、領域ブロブとラベル付された）を示せるため、領域ＩＤの配列９００は非常にコンパクトである。実際には、各ページがより少ない領域と重複し、組み合わせの可能性が低減されるため、ページ数を増加することにより配列のサイズは増加されない。従って、この配列は、生成された地図データがロードされる装置において多くの地図空間も多くのメモリも必要とせずに多くのページを作成することを可能にすべきである。
【０２４４】
方法の目的は、領域ＩＤのリストを含む配列９００を可能な限り小さく維持することである。方法の目的は、領域ＩＤの同一のリストを配列において可能な限り多く再利用することである。方法は、リストの最後の２つの要素がハフマン符号のサイズに影響を及ぼさないためそれらの要素を自由に再順序付けできる。
【０２４５】
例えばリストが２つの領域１０及び３４を含む場合、２つのノードが存在する全ての例においてハフマン木が１ビットのみを使用するため、これはリスト１０、３４又は３４、１０を格納すること（頻度に関係なく）と同等である。換言すると、頻度により再順序付けすることは、最後の２つの領域に対して緩和される。同様に、第１の符号１０（頻度が最も高い）のみが１ビットを使用し、他の符号４０及び３４の双方が２ビットを使用する（順序に関係なく）ため、３つの要素１０、３４、４０のリストは１０、４０、３４として格納されてもよい。
【０２４６】
図９を参照すると、配列９００が２つの値、すなわち長さ及び領域データの開始からのオフセットを格納することが分かる。第１の行（３：０）を考慮すると、これはファイルの開始から０だけオフセットして３つのデータを参照する（すなわち、１０、３４、４０）。更なる例を考慮すると、配列エントリ（１：２）は、ファイルの開始から２だけオフセットした単一の領域（すなわち、長さ１）を参照する（すなわち、領域４０）。
【０２４７】
別の実施形態において、領域ページ情報は、以下の方法に従って符号化される。
【０２４８】
このセクションは、各領域のサブ領域数を符号化する。サブ領域の数はレベル毎に可変であってもよい。しかし、サブ領域数がレベル毎に一定であることが多い。サブ領域数は、ｌｏｇ＿２（ｍａｘ＿ｎｕｍｂｅｒ＿ｏｆ＿ｒｅｇｉｏｎｓ−ｍｉｎ＿ｎｕｍｂｅｒ＿ｏｆ＿ｒｅｇｉｏｎ）ビットを使用して、各レベルの最小領域数に対して相対的に符号化される。従って、領域数が一定である場合、領域数を符号化するために０ビットが使用され、このセクションは空である。最小領域数及び最大領域数は、副ファイルのヘッダに格納される。
近傍領域セクションの符号化（近傍領域についは、図６及び図６ａに関連して説明する）
このセクションは、所定のレベルＬの領域階層毎に、より詳細なレベルＬ＋１の近傍領域のリストを符号化する。例えば、レベルＬ＝１の領域３．９は、レベルＬ＝２において近傍領域のリスト、３．５．４、３．６．３、３．６．４、４．７．１、４．７．３を有してもよい。他で説明するように、近傍領域のリストは、各副ファイルを生成するのに使用される前処理の速度を向上するために使用されてもよい。
【０２４９】
このセクションは２つのサブセクションに分割される。
【０２５０】
・全ての近傍リスト（所定のレベルにある領域と同数）の長さを符号化するサブセクション。長さは、最短リストに対して相対的に符号化され、ビット数はｌｏｇ＿２（ｌｅｎｇｔｈ＿ｌｏｎｇｅｓｔ＿ｌｉｓｔ−ｌｅｎｇｔｈ＿ｓｈｏｒｔｅｓｔ＿ｌｉｓｔ）で計算される。全てのリストが同一の長さを有する場合、長さを符号化するのに０ビットが使用される（従って、セクションは空である）。
【０２５１】
・全ての近傍リスト（所定のレベルにある領域と同数）を符号化するサブセクション。
【０２５２】
領域ＩＤ再マッピングテーブルの符号化
このセクションは、レベル０の副ファイルでのみ符号化される。これは、レベル０の各領域のビットを再順序付けし且つ結合するのに使用される２次元テーブルを符号化する（ビットベクトルを効率的に符号化するために、結合及びビット再順序付けについて本文献において以下に更に説明する）。ビットベクトルのビットの再順序付け及び結合は、ビットベクトルのハフマン符号化を最適化するために行われる。このテーブルは、以下が分かっている場合に復号化するビットベクトルにおけるビット位置を見つけるために経路計画方法により使用される。
【０２５３】
・現在のノードの出発領域ＩＤ
・元の到着ビット指標（すなわち、ビットベクトルのビットを分離した後のビット指標）
２次元テーブルの２つの指標は以下の通りである。
【０２５４】
・出発領域ＩＤ
・行先ビット指標（目的地の領域）
このセクションは２つのサブセクションから成る。
【０２５５】
・レベル０の領域毎に結合ビット数を符号化するセクション。各数を符号化するために使用されるビット数は、ｌｏｇ＿２（ｍａｘ＿ｎｕｍｂｅｒ＿ｏｆ＿ｃｏａｌｅｓｃｅｄ＿ｂｉｔｓ）である。
【０２５６】
・ビット再マッピングテーブルを符号化するセクション。経路指定する場合、行先ビットは変化しないが（経路指定の間、目的地は同一のままである）、出発領域ＩＤは行先ビットの行により格納された行列を変更する（経路指定中に探索されるノードに依存して）。各行において、ビット再順序付け番号は、出発領域毎に格納される。一般に、経路計画方法は、経路指定中、所定の経路指定目的地に対応するメモリの１行のみをロードする。経路計画方法は、２次元行列全体をメモリに格納する必要はない。経路計画方法は、その行にランダムにアクセスできる。各再マッピングエントリを符号化するのに使用されるビット数は、ｌｏｇ＿２（最大結合ビット数）で計算される。
【０２５７】
図１３は、レベル０領域（図９を参照）に対する図１１に示したファイルのビットベクトルセクション８１２を展開する。各ページが道路セグメント数、領域ＩＤ及びビットベクトルを含むことが分かる。
【０２５８】
図１４は、レベル０以外のレベルに対する図１１に示したファイルのビットベクトルセクション８１２を展開する。他の領域に対して、ビットベクトルのみが格納され、レベル０に対して格納される道路セグメント数又は領域ＩＤは格納されない。
【０２５９】
各レベルの領域によってカバーされる領域の差異を考慮して、ページ毎のノードの数がレベル毎に変更されうる。例えば、レベル０内の領域が大きな領域をカバーする場合に、レベル０に対する領域毎、ページ毎のより多くのノードがあってもよい。例えば、いくつかの実施形態は、レベル０に対するページ毎、レベル毎に５１２ノードを格納してもよい。その場合、多くの精細なレベルは、より少ない数のノード、例えば、２５６ノード、１２８ノード、６４ノード、３２ノード、１６ノード等を有してもよい。実際に、いくつかの実施形態は、ページ毎に、１０２４ノード、２０４８ノード、又は４０９６ノードを利用してもよい。
【０２６０】
ビットベクトル８１０、８１２の符号化
テーブル８１０は固定サイズレコードを含む。出発ノードＩＤは２ｎのページにグループ化される。
【０２６１】
ビットベクトルが同一の近傍領域のいくつかの道路セグメントに対して同様のパターンを有すると予想されるため、複数の連続したノードのページにデータをグループ化するのが便利である。ページを使用することにより、いくつかの道路セグメントをデルタに符号化でき、適切な圧縮を達成できる。同様に、ページにおいてデルタにノードの領域ＩＤを符号化できる。一方、これは、１つの道路セグメントのデータにアクセスすることがいくつかの道路セグメントのデータをアンパックすることを必要とすること（直接ランダムアクセスではない）を意味する。１つの道路セグメント又はノードのデータにアクセスするのにいくつかのノード又は道路セグメントをアンパックする必要があることは、以下の理由により受け入れ可能であると考えられる。
【０２６２】
・データは、１つの道路セグメントにアクセスする時に読み出された追加のデータが無用でないことが多いためキャッシュされる。この追加のデータはすぐ後で有用となるだろう（これは、ディスクキャッシングの先読みパラメータに類似する）。
【０２６３】
・ビットベクトルを使用する経路指定は、ダイクストラＡ＊経路指定と比較した時に拡張探索のサイズをある桁だけ減少する。ページ毎にデータをグループ化することにより、地図の小さな部分が依然として復号化される必要がある（実際のパスに沿うページ）。
【０２６４】
・領域ＩＤ＆ビットベクトルのデルタ圧縮のために符号化データサイズが非常に縮小される。
【０２６５】
・上述したようにデータが副ファイルに格納されるため、ページは指標付けのサイズを縮小する。
【０２６６】
テーブル８１０内の各レコードは、「デルタ」フィールドを含み、これは、各ページの可変サイズの開始位置（補間位置に対するデルタ）を見つけるために使用される。デルタ毎のビット数はヘッダに格納される。
【０２６７】
領域ＩＤ及びビットベクトル８１２にアクセスするために、復号器は線形補間を行うことにより開始ページの推定されたオフセットを計算してもよい。
【０２６８】
ｉｎｔｅｒｐｏｌａｔｅｄ＿ｏｆｆｓｅｔ ＝ ｆｒｏｍ＿ｎｏｄｅ＿ｉｄ ＊ ａｖｇ＿ｐａｇｅ＿ｓｉｚｅ
式中、ａｖｇ＿ｐａｇｅ＿ｓｉｚｅはヘッダに格納された平均ページサイズのビット数である（精度を向上するために可能性として固定点における）。データのオフセットは、以下のように計算される。
【０２６９】
オフセット ＝ ｉｎｔｅｒｐｏｌａｔｅｄ＿ｏｆｆｓｅｔ ＋ ｍｉｎ＿ｄｅｌｔａ ＋ デルタ
式中、ｍｉｎ＿ｄｅｌｔａは全てのページ（ヘッダに格納された）に対する全てのデルタフィールドの最小値であり、デルタは、ページに格納された符号なしフィールドである。ｍｉｎ＿ｄｅｌｔａ値は、全てのデルタフィールドが正の値であること（格納するビット符号はない）を保証する。
【０２７０】
可変サイズレコードは、上述したビットベクトルページ情報の「デルタ」フィールドを介してアクセスされる。
【０２７１】
各レコードは、２ｎ個のノードのデータ（全てのレベルにおける出発ノードの領域ＩＤ及びそれらの連結道路セグメントのビットベクトル）を含む。従って、同一の指標付け方式が全てのレベルに対して使用される。
【０２７２】
可変サイズレコードは以下を格納する。
【０２７３】
・ページ符号−そのページ内のノードが同一領域の一部であるか否かを示すページ全体に対する符号。
【０２７４】
・ビットベクトルページの各ノードの周囲の道路セグメント数（全てのレベルに対して同一であるため、レベル０でのみ格納される）。
【０２７５】
・ページの出発ノードの領域ＩＤ。レベル毎に１つのＩＤがある（レベル０でファイルに格納された全てのレベルに対する情報）。
【０２７６】
・レベルｉのみのページのノードの周囲（＞２個の連結道路セグメントを有するノードの周囲のみ）の道路セグメントのビットベクトル。これはデータの最大の部分である。
【０２７７】
・各ノードの周囲の道路セグメント数の符号化。
【０２７８】
ビットベクトルページの２ｎ個のノードの各々に対して、ハフマン符号はノードの周囲の道路セグメント数を符号化する。この情報は、全てのレベルに固有のものではなく、レベル０のファイル（ａｐ＿０＿＊．ｄａｔ）にのみ格納される。
【０２７９】
ノードの周囲の道路セグメント数を認識することは、ビットベクトルを復号化するのに使用される（図１０の１０００を参照）。この情報は、他のファイルに既に存在する情報と冗長するが、他の場所にある情報をルックアップする必要なくページ中のビットベクトルを復号化するのを容易に且つ迅速にする。これにより、サイズの小さな増加が性能を向上する。
【０２８０】
可変サイズレコードの領域ＩＤの符号化
ノードの領域ＩＤ１００２は、各ノードの周囲の道路セグメント数１０００の符号化の直後に可変サイズレコードに符号化される（符号化レイアウトを参照）。前処理において生成されたビットベクトルを使用して経路指定を行うために、一般に所定のノードに対する全てのレベルの領域ＩＤ１００２にアクセスする必要があり、全てのレベルの領域ＩＤは、レベル毎に異なるファイルに分割されるのではなく互いに近接して同一ファイルに格納される。
【０２８１】
３つのアポロレベルを有する２ｎ（例えば、ｎ＝４）個のノードのビットベクトルページは以下のようにノードＩＤを格納する。
【０２８２】
ノード＃０：ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿０  ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿１  ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿２
ノード＃１：ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿０  ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿１  ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿２
ノード＃２：ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿０  ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿１  ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿２
．．．
ノード＃１５：ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿０  ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿１  ｌｏｃａｌ＿ｒｅｇｉｏｎ＿ｉｄ＿ｌｅｖｅｌ＿２
更に、以下の通りである。
【０２８３】
・１つ又は２つの連結道路セグメントを有するノードの周囲で符号化されるものはない（すなわち、連結道路セグメント数として０を格納するノードに対して）。
【０２８４】
・ページ符号のビットが所定のレベルで設定される場合、全てのノードはそのレベルの同一領域ＩＤにあり、そのレベルの領域ＩＤは１度だけ符号化される（＞＝３個の連結道路セグメントを有する第１のノードに対して）。領域ＩＤを符号化するビット数はｌｏｇ＿２（ｒｅｇｉｏｎＣｏｕｎｔ−１）である。
【０２８５】
・領域ＩＤが符号化されるページの第１のノード以外は、各領域ＩＤを符号化する前にビットが符号化される。このビットは、領域ＩＤが同一レベルの先に符号化されたノードＩＤと同一であるかを示す。このビットが設定される場合、そのレベルの先に符号化されたものと同一であるため、領域ＩＤを符号化する必要はない。このビットが０である場合、ｌｏｇ＿２（ｒｅｇｉｏｎＣｏｕｎｔ−１）ビットで領域ＩＤを符号化する。多くの連続したノードが同一の領域にあるため、領域ＩＤを符号化するのに１ビットだけ必要とすることが多い。
【０２８６】
以下の理由のために、ローカル領域指標のハフマン符号化は効率的である。
【０２８７】
・領域は各領域ページにおける頻度によりソートされる（従って、ローカル指標０はローカル指標１、．．．より頻度が高い）。
【０２８８】
・ページの領域数毎に別個の専用のハフマン木が存在する（３つの領域がページにある場合に１つのハフマン、４つの領域がページにある場合に１つのハフマン木等）。ハフマン木は小さいため、メモリを多く使用せずにいくつか格納できる。
【０２８９】
・少なくともレベル０において、３つ以上の領域を有することは極めて珍しい（しかし、他のレベルでは珍しくない）。
【０２９０】
可変サイズレコードのビットベクトルの符号化
各可変サイズレコードは、ページのノードの周囲の全ての道路セグメントに対するビットベクトルを含む。ビットベクトルは、３つ以上の連結された線（道路セグメント）を有するノードの周囲でのみ符号化される。１つ又は２つの連結道路セグメントを有するノードの場合、経路指定方法は、それらのノードにビットベクトル値１１１．．．１１１を黙示的に与えられる。
【０２９１】
到着ノードは符号化されない。
【０２９２】
図１０を参照すると、道路セグメントは、それぞれが道路セグメントの端部にある２つのノードにより指定されてもよい。従って、方向が考慮される場合、方向の開始にあるノードはｆｒｏｍ＿ｎｏｄｅと呼ばれてもよく、方向の終了にあるノードはｔｏ＿ｎｏｄｅと呼ばれてもよい。
【０２９３】
ビットベクトルに関する種々のプロパティは、効率的にするために符号化内で使用される。
【０２９４】
・ビットベクトルの多くは０００．．．０００又は１１１．．．１１１である。
【０２９５】
・ビットベクトルの他の値（すなわち、０００．．．０００でも１１１．．．１１１でもない）に対しては、繰り返しになる可能性が高く、同一の値が繰り返される可能性が高い。
【０２９６】
・また、所定ノード周辺の全てのビットベクトルのＯＲが１１１．．．１１１であるべきである。
【０２９７】
ビットベクトルは、第１のハフマン符号及びオプションの更なるハフマン符号として符号化される。第１のハフマン符号は、ビットベクトルが以下のいずれであるかを示す。
【０２９８】
・自明なビットベクトル０００．．．０００に対する符号０
・自明なビットベクトル１１１．．．１１１に対する符号１
・符号２、すなわちページでまだ遭遇していない非自明なビットベクトルを示す符号。この場合のみ、新たに遭遇したビットベクトルを符号化するために他のハフマン符号が後続する。
【０２９９】
・ビットベクトルが現在のページの先に遭遇したビットベクトルと同一である場合（自明なビットベクトル０００．．．０００及び１１１．．．１１１は無視する）、＞＝２の符号。この符号化は、ページの先に遭遇した符号の履歴を使用する。符号は、実際には先に遭遇した全ての符号の履歴中の指標を与える。
【０３００】
このハフマン符号以外は、履歴中で見つけられなかった非自明なビットベクトルの場合（符号＝２）にのみ、更なる情報が符号化される必要がある。この場合、ハフマン符号＝＝２の直後に以下が符号化される。
【０３０１】
・否定ビット
・Ｎビットのブロックによりｎ個の領域に対するビットベクトルを符号化するためのいくつかのハフマン符号（Ｎ及びｎは地図ヘッダで与えられる）。例えば、１００個の領域（９９ビットのビットベクトル）を１１ビットのブロックを使用して符号化することは、９個のハフマン符号（９ｘ１１＝９９）を符号化することを必要とする。
【０３０２】
殆どのビットベクトルは殆どが０又は殆どが１のベクトルを含むため、否定ビットは、ビットベクトルが否定されて格納されるか否かを示す。これにより、殆どが０のベクトルを多く含むハフマン木への符号の格納を可能にする（これにより、ブロックのハフマン符号化を向上する）。ブロックのサイズが領域数より小さい場合にのみ否定ビットは存在し、これは、実際にはレベル０において当てはまるが、レベル１又は２において、ビットベクトル全体は１つのブロックにのみ符号化されるため否定ビットは必要ない。
【０３０３】
１００個の領域が存在する場合、すなわちＮ＝１００（従って、９９ビットのビットベクトル）の場合、第１のブロックは行先領域１〜１１に対するビットを符号化し、第２のブロックは領域１２〜２２を符号化する。第１のブロックにおいて、ＬＳＢ（０ｘ１）は行先領域１に対応し、次のビット（０ｘ２）は領域２に対応し、次のビット（０ｘ４）は領域３に対応する。
【０３０４】
履歴を使用するビットベクトルの場合、履歴配列の深さはページ中の先に遭遇した別個のビットベクトルの数である（自明なビットベクトル０００．．．０００及び１１１．．．１１１を考慮に入れない）。異なるハフマン木は、履歴ベクトルが０個の要素、１つの要素、２つの要素、３つの要素等を含むかに関わらず使用される。全てのハフマン木が小さいために大きな記憶容量が必要とされないため、ハフマン木を増加することは受け入れられる。
【０３０５】
・履歴が０個の要素を有する場合、ハフマン木は３つの符号、すなわち０００．．．０００に対する０、１１１．．．１１１に対する１、新しいビットベクトルに対する２を有する。
【０３０６】
・履歴が１つの要素を有する場合、ハフマン木は４つの符号、すなわち０００．．．０００に対する０、１１１．．．１１１に対する１、新しいビットベクトルに対する２、履歴の要素＃０と同一のベクトルに対する３を有する。
【０３０７】
・履歴が２つの要素を有する場合、ハフマン木は５つの符号、すなわち０００．．．０００に対する０、１１１．．．１１１に対する１、新しいビットベクトルに対する２、履歴の要素＃０と同一のベクトルに対する３、履歴の要素＃１と同一のベクトルに対する４を有する。
【０３０８】
・その他。
【０３０９】
ビットベクトルページのサイズが小さい（例えば、２ｎ個の出発ノード）と予想されると、ハフマン木の数も小さいと予想される。
【０３１０】
しかし、ハフマン木のサイズを最大値に制限できる。例えば履歴がＨ個より多くの要素を含む場合は必ず、単一のハフマン木が使用される（値Ｈは地図ヘッダに格納される）。
【０３１１】
この符号化は、各ページ中の別個のビットベクトル＋いくつかの符号のみを符号化する。
【０３１２】
経路指定の目的でビットベクトル（ページ中の復号化するより多くのビットベクトル）を使用するために、符号化は、復号化を遅くする代わりに大きな指標のページに対してサイズに関してより効率的である。
【０３１３】
統計
ベネルクスを２５４個の領域（１つのレベル）に符号化する場合のファイル形式に対する詳細な統計を示す。以下の入力パラメータを使用した。
【０３１４】
ビットベクトルブロック毎のビット数：１１
ビットベクトルページ毎のノード数：２＾４＝１６
領域ページ毎のノード数：２＾９＝５１２
統計は、地図のサイズに関して地図形式の概念を与え且つ実データに関する地図形式の記述を示すために提供される。
−−−グローバル統計カウンタ：
ノード数．．．．．．．．．．．．．．．．．．．．．．．１５９８６３２
線の数．．．．．．．．．．．．．．．．．．．．．．．． １５９８６３２（１００．０００％）
１つの線を有するノードの周囲の線をスキップする．．．  ２２０１８０（ １３．７７３％）
２つの線を有するノードの周囲の線をスキップする．．．  ７２７１３８（ ４５．４８５％）
−−−レベル＝［０］の統計：
地図カウンタ．．．．．．．．．．．．．．．．．．．．．．８７４３７７３６（１００．０００％）
符号化された自明なａｒｐフラグ０００．．．０００．．． １３１０９１４（ ３１．６５１％）
符号化された自明なａｒｐフラグ１１１．．．１１１．．．  ９１３３４８（ ２２．０５２％）
履歴中の符号化されたａｒｐフラグ．．．．．．．．．．．  ３６２４３２（  ８．７５１％）
履歴中にない符号化されたａｒｐフラグ．．．．．．．．．  ６０７７１７（ １４．６７３％）
否定ブロック．．．．．．．．．．．．．．．．．．．．  ２３５１７１（  ５．６７８％）
地図のサイズ（ビット）．．．．．．．．．．．．．．．．．８７４３７７３６（１００．０００％）
グローバルヘッダ．．．．．．．．．．．．．．．．．．．     ４９６（  ０．００１％）
ハフマン木．．．．．．．．．．．．．．．．．．．．．．   ２８８０８（  ０．０３３％）
領域ブロブ．．．．．．．．．．．．．．．．．．．．．．   ５２６６４（  ０．０６０％）
領域ページ情報．．．．．．．．．．．．．．．．．．．．   ５６２１６（  ０．０６４％）
ａｒｐフラグページ情報．．．．．．．．．．．．．．．． ２４９７８８０（  ２．８５７％）
可変サイズレコード．．．．．．．．．．．．．．．．．．８４８０１６７２（ ９６．９８５％）
ノードの周囲の線の数．．．．．．．．．．．．．．．． ２８４７８４４（  ３．２５７％）
ノード領域ＩＤ．．．．．．．．．．．．．．．．．．． ２１１２４５１（  ２．４１６％）
ａｒｐフラグ．．．．．．．．．．．．．．．．．．．．７９８４１３７０（ ９１．３１２％）
自明な符号０００．．．０００．．．．．．．．．．． １６８９３２２（  １．９３２％）
自明な符号１１１．．．１１１．．．．．．．．．．． １８２６６９６（  ２．０８９％）
履歴中で見つけられた符号．．．．．．．．．．．．． １６６８０５３（  １．９０８％）
履歴中で見つけられない．．．．．．．．．．．．．．７４６５７２９９（ ８５．３８３％）
履歴中で見つけられない符号．．．．．．．．．．． １４６３１８３（  １．６７３％）
否定ビット．．．．．．．．．．．．．．．．．．．  ６０７７１７（  ０．６９５％）
ブロック．．．．．．．．．．．．．．．．．．．．７２５８６３９９（ ８３．０１５％）
全てのサイズはビット単位である。地図の合計サイズは、８７，４３７，７３６ビット（１０，９２９，７１７バイト）である。
【０３１５】
インデントは階層を反映している。可変サイズレコード情報は、圧倒的に大きい情報（地図のサイズの９６．９７５％）である。可変サイズレコードにおいて、サブ項目（インデントされた）はより詳細を与える。ビットベクトルは、可変サイズレコードに格納する圧倒的に大きな情報（９１．３１２％）である。ビットベクトルにおいて、履歴においてまだ遭遇していない非自明なビットベクトルを格納することは地図の最大部分を構成する（８３．０１５％）。
【０３１６】
ハフマン木に関する統計
このセクションは、ベネルクスを２５５個の領域に符号化する（すなわち、上記で示した地図データに対して）場合のハフマン木に対する統計を与える。
【０３１７】
各ノードの周囲の道路セグメント数のハフマン木
−−−［ハフマン木：Ｎｒ本の線］−−−
ビット：        １      値：    ３      符号                 ０
ビット：        ２      値：    ２      符号               １０
ビット：        ３      値：    １      符号             １１０
ビット：        ４      値：    ４      符号           １１１０
ビット：        ５      値：    ５      符号         １１１１０
ビット：        ６      値：    ６      符号       １１１１１０
ビット：        ７      値：    ７      符号     １１１１１１０
ビット：        ７      値：    ８      符号     １１１１１１１
殆どのノードは３つの連結道路セグメントを有するが、ハフマン木の第２及び第３の位置において、２つ又は１つの連結道路セグメントを有するノード（決定ノードではない）を見つける。
【０３１８】
非自明なビットベクトルブロックのハフマン木
自明なビットベクトルのブロックを格納することが圧倒的に大きな地図のサイズを占める（ベネルクスの２５５個の領域の例において８３．０１５％）ため、これは最大のハフマン木である。
【０３１９】
−−−［ハフマン木：ＮｏｎＴｒｉｖｉａｌＡｒｐＦｌａｇＢｌｏｃｋ］−−−
ビット：        １      値：      ０    符号          ０
ビット：        ６      値：      １    符号     １０００００
ビット：        ６      値：      ２    符号     １００００１
ビット：        ６      値：      ４    符号     １０００１０
ビット：        ６      値：      ８    符号     １０００１１
ビット：        ６      値：    １６    符号     １００１００
ビット：        ６      値：    ３２    符号     １００１０１
ビット：        ６      値：    ６４    符号     １００１１０
ビット：        ６      値：  ５１２    符号     １００１１１
ビット：        ６      値：１０２４    符号     １０１０００
ビット：        ７      値：  １２８    符号    １０１００１０
ビット：        ７      値：  ２５６    符号    １０１００１１
ビット：        ７      値：  ３８４    符号    １０１０１００
ビット：        ８      値：      ５    符号   １０１０１０１０
．．．大きすぎるため中略．．．
ビット：        ２４    値：１５３４    符号   １１１１１１１１１１１１１１１１１１１１１０１１
ビット：        ２４    値：１７１７    符号   １１１１１１１１１１１１１１１１１１１１１１００
ビット：        ２４    値：１７４１    符号   １１１１１１１１１１１１１１１１１１１１１１０１
ビット：        ２４    値：１８３０    符号   １１１１１１１１１１１１１１１１１１１１１１１０
ビット：        ２４    値：１９７３    符号   １１１１１１１１１１１１１１１１１１１１１１１１
全て０から成るブロックを格納することは、頻度が最も高いパターンであり、上記ハフマン木に従って１ビットのみに符号化される（これは、自明なビットベクトル０００．．．０００がブロックにより符号化されないが、ブロックの５０％以上が値０を符号化することを意味する）。これは、殆どの非自明なビットベクトルが以下のいずれかを含むためである。
【０３２０】
・殆どが０（及びいくつかの１）
・殆どが１（及びいくつかの０）
符号化方式は、殆どが１であるビットベクトルに否定演算（〜）をし、最終的にビットベクトルのブロックを符号化することは、主に、０００．．．０００を含むブロックを１ビットにのみ符号化する。次に頻度の高いブロックは、１ビットのみが設定されるブロックである（１、２、４、８、１６、３２、６４．．．）。これらのブロックは同程度の頻度を有するため、同一（又はほぼ同一）のビット数を有する。
【０３２１】
ローカル領域ＩＤのハフマン木
領域のリストが頻度により各ページに格納されるため、ローカル領域ＩＤ０を格納することは他の場所の領域ＩＤより少ないビット数（実際には１ビットのみ）を利用する。種々のハフマン木は、３つの領域、４つの領域、５つの領域等を含むページに対応する。
【０３２２】
−−−［ハフマン木：Ｒｅｇｉｏｎｓ＿０］−−−
ビット：     １     値：     ０     符号              ０
ビット：     ２     値：     １     符号            １０
ビット：     ２     値：     ２     符号            １１
−−−［ハフマン木：Ｒｅｇｉｏｎｓ＿１］−−−
ビット：     １     値：     ０     符号              ０
ビット：     ２     値：     １     符号            １０
ビット：     ３     値：     ２     符号          １１０
ビット：     ３     値：     ３     符号          １１１
−−−［ハフマン木：Ｒｅｇｉｏｎｓ＿２］−−−
ビット：     １     値：     ０     符号              ０
ビット：     ２     値：     １     符号            １０
ビット：     ３     値：     ２     符号          １１０
ビット：     ４     値：     ３     符号        １１１０
ビット：     ４     値：     ４     符号        １１１１
−−−［ハフマン木：Ｒｅｇｉｏｎｓ＿３］−−−
ビット：     １     値：     ０     符号              ０
ビット：     ２     値：     １     符号            １０
ビット：     ３     値：     ２     符号          １１０
ビット：     ４     値：     ３     符号        １１１０
ビット：     ５     値：     ４     符号      １１１１０
ビット：     ５     値：     ５     符号      １１１１１
．．．以下略．．．。
【０３２３】
ビットベクトル履歴符号のハフマン木
符号０（自明なビットベクトル０００．．．０００を意味する）は、頻度が最も高い（且つ殆どの場合、１ビットにのみ符号化される）。符号１（自明なビットベクトル１１１．．．１１１は、次に頻度が高い（且つ１ビットにのみ符号化される）。次に頻度が高い符号（２）は、ブロックにより符号化された非自明なビットベクトルに対するものである。他のコード（＞２）は履歴中に見つけられるビットベクトルに対するものである。
【０３２４】
−−−［ハフマン木：ＡｒｐＦｌａｇ＿０］−−−
ビット：     １     値：     ０     符号             ０
ビット：     ２     値：     １     符号           １０
ビット：     ２     値：     ２     符号           １１
−−−［ハフマン木：ＡｒｐＦｌａｇ＿１］−−−
ビット：     １     値：     ０     符号             ０
ビット：     ２     値：     １     符号           １０
ビット：     ３     値：     ２     符号         １１０
ビット：     ３     値：     ３     符号         １１１
−−−［ハフマン木：ＡｒｐＦｌａｇ＿２］−−−
ビット：     １     値：     ０     符号             ０
ビット：     ２     値：     １     符号           １０
ビット：     ３     値：     ２     符号         １１０
ビット：     ４     値：     ３     符号       １１１０
ビット：     ４     値：     ４     符号       １１１１
−−−［ハフマン木：ＡｒｐＦｌａｇ＿３］−−−
ビット：     １     値：     ０     符号             ０
ビット：     ２     値：     １     符号           １０
ビット：     ３     値：     ２     符号         １１０
ビット：     ４     値：     ３     符号       １１１０
ビット：     ５     値：     ４     符号     １１１１０
ビット：     ５     値：     ５     符号     １１１１１
−−−［ハフマン木：ＡｒｐＦｌａｇ＿４］−−−
ビット：     １     値：     ０     符号             ０
ビット：     ２     値：     １     符号           １０
ビット：     ３     値：     ２     符号         １１０
ビット：     ４     値：     ３     符号       １１１０
ビット：     ５     値：     ４     符号     １１１１０
ビット：     ６     値：     ５     符号   １１１１１０
ビット：     ６     値：     ６     符号   １１１１１１
−−−［ハフマン木：ＡｒｐＦｌａｇ＿５］−−−
ビット：     ２     値：     ０     符号             ０
ビット：     ２     値：     １     符号           ０１
ビット：     ２     値：     ２     符号           １０
ビット：     ４     値：     ３     符号       １１００
ビット：     ４     値：     ４     符号       １１０１
ビット：     ４     値：     ５     符号       １１１０
ビット：     ５     値：     ６     符号     １１１１０
ビット：     ５     値：     ７     符号     １１１１１
．．．以下略．．．。
【０３２５】
地図のサイズに対する入力パラメータの影響
図１１に示したファイル形式を制御し且つ地図のサイズに影響を及ぼす入力パラメータが多く存在する。パラメータを微調整することは、パラメータに依存する伸張の速度又はメモリ使用量と地図のサイズとの間のトレードオフの関係となる。
【０３２６】
本発明の実施形態は、以下の入力パラメータを使用してもよい。
【０３２７】
・領域ページサイズ
・ビットベクトルページサイズ
・ビットベクトルブロックサイズ
・ビットベクトルハフマンコーデック数
・領域ハフマンコーデック数。
【０３２８】
ビットベクトルブロックサイズの影響
値          地図のサイズ（ビット）
４          ３５５４８１９２
５          ３３６４８７９２
６          ３２２９０３４４
７          ３０８５３６１６
８          ３１１０３２００
９          ３０４３６６９６（デフォルト）
１０          ３００５１７９２
１１          ２９２６６７８４
１２          ２８９３４６９６。
【０３２９】
ビットベクトルに対するハフマンブロックサイズを増加することにより、地図圧縮は向上される。ブロックサイズが大きい程、圧縮はより適切になる。しかし、ブロックサイズを増加することは、２＾ｎ個の値のより大きなハフマン木を格納するのにより大きなメモリが必要となる。上記テーブルはこのことを示す。
【０３３０】
ソース領域毎に領域ＩＤを再マッピングするために最適化を導入する場合、このパラメータの影響はより大きくなると予想される。この最適化の結果、大きいビットベクトルブロックサイズを使用する場合に地図のサイズが非常に減少されるのが望ましい。
【０３３１】
ビットベクトルページサイズの影響
値          地図のサイズ（ビット）
２＾１          ５５５６３９４４
２＾２          ４２５０２９３６
２＾３          ３４８９８８４０
２＾４          ３０４３６６９６（デフォルト）
２＾５          ２７３８９９５２
２＾６          ２５１６５０３２
２＾７          ２３６３５９３６
ページサイズを増加することは、地図をより適切に圧縮するのを助長する。しかし、ランダムな道路セグメントのビットベクトルにアクセスするにはページ中の全ての道路セグメントを復号化する必要があるため、大きなページは経路指定方法によりデータをファイル形式に伸張することを遅くする。上記テーブルはこのことを示す。
【０３３２】
ビットベクトルハフマンコーデック数の影響
値          地図のサイズ（ビット）
１          ３０８６６９２０
２          ３０７４８０２４
３          ３０６３４１６８
５          ３０５０４５０４
７          ３０４６７９４４
９          ３０４３６６９６（デフォルト）
１１          ３０４２３６８８
ビットベクトルハフマンコーデックの数を増加することは、圧縮を僅かに向上させるのを助長し、これを上記テーブルに示す。ハフマン木はいずれの場合も小さいため、値を増加することに対する欠点はほぼない。９個（デフォルト値）を上回ってハフマン木を増加しても大きな改善は得られない。このパラメータを増加することは、ビットベクトルページが大きいほど効果的である可能性がある。
【０３３３】
ビットベクトルのビットの結合＆再順序付け
ビットベクトルはパターンを有する。これらのパターンはソース領域（すなわち、ビットベクトルが格納されるノードの領域）毎に大きく異なる。Ｎビットのビットベクトルを格納するためのビット数は、ソース領域毎に小さな変換テーブルを格納することにより減少される。これらのテーブルは、この節で更に説明される２つの関数を実行する。
【０３３４】
・ビットの結合
・ビットの再順序付け
概念は、以下のように直感的に理解される。スペインの場合、スウェーデン（行先領域スウェーデンに対してビット＝１）に通じている道路セグメントは、ノルウェー（すなわち、目的地ノルウェーに対するビットも１）に通じている可能性が高いことは明らかである。別の道路セグメントがスウェーデン（ビット＝０）に通じていない場合、その道路セグメントは殆どの場合においてノルウェーにも通じていない。従って、スペインの場合、行先領域スウェーデン及びノルウェーに対するビットベクトルのビットの値はほぼ常に等しい。実際には、ビットの値は多くの行先領域に対して常に厳密に等しい。どのビットがどのビットに相関しているかは、出発領域に大きく依存する。
【０３３５】
例えばフィンランドの場合、行先領域ノルウェー及びスウェーデンに対するビットは殆ど相関しない。一方、フィンランドにおいて、行先領域スペイン及びポルトガルに対するビットは１００％（又は少なくともほぼ１００％）相関する可能性が高い。
【０３３６】
ビットの結合は、いくつかのビットが常に等しい（完全に相関される）というプロパティを利用する。これらのビットは単一ビットに結合される。ビットを結合することにより、各領域で符号化するビット数が減少される。
【０３３７】
ビットの再順序付けは、ビットベクトルのハフマン符号化を最適化するように（且つ／又はハフマン木のサイズを縮小するように）ビットをシャッフルするために、いくつかのビットが十分適切に相関される（しかし、１００％相関されるわけではない）というプロパティを利用する。
【０３３８】
【表１】
0006030544.tif 000002
【０３３９】
ビットを結合し且つ再順序付けするためのテーブルを計算する前に、全ての出発領域の全てのビット対の相関が算出される。別個の対の数は以下の通りである。
【０３４０】
Ｃ（Ｎ， ２） ＝ Ｎ！／（２！ ＊ （Ｎ − ２）！） ＝ Ｎ ＊ （Ｎ − １）／２
式中、Ｎは領域数である。この数は、領域数が多い場合に大きくなる。全てのビット相関を計算することは、図８に示したファイル形式を生成する方法の最も遅い部分である。方法の複雑さはｎ＊Ｎ＊Ｎであり、ｎはビットベクトル数であり、Ｎは領域数である。各領域のビット対（すなわち、ビットベクトルの個別の列の対）毎に３次元テーブルを計算する。
【０３４１】
ｂｉｔＣｏｒｒｅｌａｔｉｏｎ［ｆｒｏｍＲｅｇｉｏｎＩｄ］［ｂｉｔＩ］［ｂｉｔＪ］
テーブルの各エントリは、以下をカウントする４つのフィールドから成る構造を含む。
【０３４２】
・ｆｒｏｍＲｅｇｉｏｎＩｄの全てのビットベクトルにおけるｂｉｔＩ＝０及びｂｉｔＪ＝０の回数
・ｆｒｏｍＲｅｇｉｏｎＩｄの全てのビットベクトルにおけるｂｉｔＩ＝０及びｂｉｔＪ＝１の回数
・ｆｒｏｍＲｅｇｉｏｎＩｄの全てのビットベクトルにおけるｂｉｔＩ＝１及びｂｉｔＪ＝０の回数
・ｆｒｏｍＲｅｇｉｏｎＩｄの全てのビットベクトルにおけるｂｉｔＩ＝１及びｂｉｔＪ＝１の回数
計算するためのプロセッサの時間に関して高価である（且つ従って遅い）が、出発領域毎にビット相関を計算することは他の出発領域から完全に独立しているため、この処理は容易に並列化できる。
【０３４３】
本発明の実施形態は、マルチスレッディングを使用して、ＳＭＰ（対称型マルチプロセッシング）マシンを効率的に使用するための全てのビットの相関の計算を加速する。１つのシステムにおいて、３００個の領域を含むベネルクスのビット相関を計算する１ＣＰＵのマシンは約８分かかる。しかし、並行処理が適切に釣り合い、スレッドを可能にし且つビット相関を計算する４つのＣＰＵを使用する場合は２分（１／４の時間）かかる。
【０３４４】
ビットの結合
いくつかのビットが完全に相関される場合（すなわち、常に全て０又は全て１）、どの情報も損失することなくそれらのビットを１ビットのみに結合できる。所定の領域において「グループ」として完全に相関されるビットの集合を参照すると、所定の領域のビットベクトルはいくつかのグループから成る。Ｎビットのビットベクトルがｎ個のグループから成る場合、Ｎビットのビットベクトルを符号化することはｎビット＋各領域において等しいビットを示す小さなテーブルを使用する。
【０３４５】
そのようなビットの結合は、結果として得られるファイルのサイズが可逆的に縮小されるという利点を有する。領域数が増加すると、より多くのビットが結合される可能性があるため、領域数の増加に伴いこの利点も大きくなる可能性が高い。従って、地図のサイズは領域数に伴いほぼ線形的に増加する。
【０３４６】
一実施形態において、以下のデータが得られた。
最小グループ数   平均グループ数     最大グループ数
２５５個の領域のベネルクス     １２           ８４               １５２
３００個の領域のベネルクス     １３           ９０．０１７       １６３
従って、２５５個の領域を有するベネルクスの例において、１２個のグループのみを有する少なくとも１つの領域が存在する（すなわち、ハフマン符号化の前であっても（及びハフマン符号化の後であっても）２５５ビットのビットベクトル（すなわち、ビットベクトルが領域数と同一の長さである）を符号化するのに１２ビットだけ必要とされる）。
【０３４７】
平均して、領域は２５５個の領域のベネルクスに対して８４ビット必要とする。この例において、ハフマン符号化の前、最悪な領域でも１５２ビット（１５２個のグループ）を必要とする。
【０３４８】
別の例として、符号化データから得られるような以下の１８個のグループを有する上記２５５個の領域のベネルクスにおいてｒｅｇｉｏｎＩｄ＝３を利用する。
ｒｅｇｉｏｎＩｄ＝［３］は［１８］個のグループを有する。
【０３４９】
【表２】
0006030544.tif 000003
【０３５０】
各行は１つのグループ（ｒｅｇｉｏｎＩｄ＝３に対する１８個のグループ）を表す。小括弧内の数字は、各グループで結合されたビット指標である。＃の後の数字は各グループのビット数である。
【０３５１】
この例において、１つのグループは非常に大きく、１４１個もの領域を含む。これは異例ではない。一般に、地図の境界上の領域は、地図の中央の領域より多くのビットを結合する。
【０３５２】
この例において、ビット数は平均で〜３（〜＝２５５／８４）に減少されている。当然、これは、符号化する残りのビットが元のビットより高いエントロピーを有する（従って、ハフマンブロックにより符号化するのはより困難である）ため、地図のサイズが１／３に縮小されることを意味しない。しかし、ビットの結合により、地図のサイズは可能性として非常に縮小される可能性がある。
【０３５３】
各領域のビットを結合させる場合、各領域のビットベクトルは、図１２に示すように結果として異なるビット数を有する（しかし、所定の出発領域のビットベクトルに対しては同一のビット数を有する）。陰影は、各ビットベクトルの出発領域ＩＤを示す。ｙ軸はセグメントの順序を表す。例えば、最上部のブロックは１０４３本の線を表してもよく、次のブロックは５０７本の線を表してもよい。
【０３５４】
テーブルｂｉｔＣｏｒｒｅｌａｔｉｏｎが計算されると、完全に相関したビットのグループを特定することは非常に容易で且つ迅速である。０１又は１０パターンが見つからない全てのビット対は完全に相関され、１ビットに結合される。
【０３５５】
ビットの結合の更なる一例を与えるために、以下のテーブルは、それぞれが１５ビットから成る６つのビットベクトルの一例を与える。これらは結合されていない。
【０３５６】
【表３】
0006030544.tif 000004
【０３５７】
これらの１５ビットのビットベクトルは、４つのグループ、すなわちハフマン符号化の前のビットベクトル毎に４ビットに結合される。
【０３５８】
【表４】
0006030544.tif 000005
【０３５９】
テーブルの右側部分の見出しは、テーブルの左側部分の４ビットの結合ベクトルのビットを示す。明示するために、４ビットの結合ベクトルの第１のビットは、左側部分の第１列、第３列及び第９列を表す。従って、左側部分（すなわち、１５ビットの元のベクトル）の第１のビット、第３のビット及び第９のビットが上記例において常に同一であるため、それらのビットは上記テーブルの右側部分の第１列により表されてもよい。
【０３６０】
従って、要約すると、左側と右側との間の索引のテーブルは以下の通りである。
元のビット  結合されたビット
０             ０
１             １
２             １
３             ０
４             ０
５             ３
６             ２
７             １
８             ２
９             ２
１０           ３
１１           ０
１２           ３
１３           １
１４           １
ビットを効果的に結合することは、近傍の行先領域及び図１６に示すように出発領域から同一角度の扇形内にある行先領域をグループ化することである。
【０３６１】
図１６の陰影は、結合される領域のグループを示す。２つの図面（すなわち、図１６ａ及び図１６ｂ）は、２つの異なる出発領域の観点から結合された同一領域を示す。結合される領域は、図示するように出発ノードの領域ＩＤに依存する。図中、８つの領域が４つのグループに結合される。ビットの結合は、これらの図の出発領域Ａ又は出発領域Ｂの観点から異なる。尚、垂直の縞模様の領域（１３００）は、出発領域Ａから見た場合に同一方向のあるため結合される。
【０３６２】
これは、図１７において更に例示される。図１７は、ビットの結合が各出発領域の観点から近傍の行先領域及び＋／−の同一角度の扇形内にある行先領域をグループ化することを示す。
【０３６３】
ビットを結合した後、ビットベクトルに対して符号化するビット数は領域毎に異なる。例えば２５５個の領域のベネルクスの場合、領域毎のビットベクトルのビット数は以下の通りである。
出発領域     −＞     結合されたビット
１           −＞     ５７
２           −＞     ９３
３           −＞     １８
４           −＞     １２
５           −＞     ６３
６           −＞     ７５
．．．中略．．．
２５１       −＞     ２１
２５２       −＞     ４６
２５３       −＞     １１７
２５４       −＞     ８０
方法は正確である（ヒューリスティックではない）。従って、理想的なビットのグループ数が分かる。
【０３６４】
いくつかの実施形態において、ビットの結合は可逆的に実現される。すなわち、領域は常に同一ビットを有する場合に結合される。しかし、他の実施形態において、これは不可逆にするように、すなわち元のデータの完全な回復が不可能であるように拡張されてもよい。そのような不可逆の実施形態は閾値（すなわち、密接度の尺度）を導入してもよい。すなわち、ビット対がＸ倍未満だけ異なる場合、一部のビットベクトルの１つ以上の０を１で置換することによりビットベクトルを結合できる場合にビットを結合できる。従って、いくつかの実施形態において、そのような結合はほぼ相関されるビットに対して行われる。
【０３６５】
そのような不可逆結合の一例は、００００００１１００を００００００１１１０と結合することである。そのような方法の利点は、データの圧縮がより適切であることであるが、欠点は、道路セグメントが最速経路の一部であることを追加の１が示すため、更なる道路セグメントがビットベクトルを使用して経路指定方法により評価されることである。
【０３６６】
可逆的結合の場合、閾値は０である。閾値を増加することにより更なる領域を結合することが可能になるが、いくつかのビット１をビットベクトルに導入する。しかし、閾値が小さく維持される場合、閾値は、経路指定がデータ形式を使用して実行される際の速度にほぼ何も影響を及ぼさない。例えば２ビットが１ビットのベクトル以外の数千個のビットベクトルにおいてほぼ常に同一である場合、これは、より多くのビットを結合することを可能にするために異なるものであるこの一意のビットベクトルを変更するために受け入れ可能であってもよい。閾値が大きい程、より高い地図圧縮を期待できる。
【０３６７】
ビットの再順序付け
いくつかの実施形態において、上述したようにビットが結合されると、ビットは再順序付けされてもよい。ビットの再順序付けは、符号化するビット数（ハフマン符号化前の）を減少しないが、ハフマン符号化をより効率的にすることを助長し、従って地図のサイズを縮小する。ビットの再順序付けは、ビットベクトルハフマン符号における別個の符号の数を減少することを更に助長し、従ってハフマン木に要求されるメモリを減少する。
【０３６８】
ビットの結合とは異なり、ビットの再順序付けはヒューリスティック法であるため、適切な再順序付けを見つけるが、最善の再順序付けを見つけない可能性がある。
【０３６９】
ビットベクトルはブロックにより符号化される。ブロックサイズは、カスタマイズ可能であり、地図ヘッダ８００に格納される。以下の説明において、一例として、ブロックサイズは１１ビットに設定される。ビットベクトルのビット数は１１で割り切れない可能性があるため、最後のブロックは１１ビットより小さい可能性がある。最後のブロックは、１１ビットの完全なブロックに対するハフマン木とは異なるハフマン木を使用する。各ビットベクトルを符号化することにより、以下を符号化する。
【０３７０】
・１１ビットのブロック（この例において）に対するハフマン符号を使用するいくつかの完全なブロック
・１１ビット未満が残っている時に別のハウマン符号を使用する最後の１つのブロック
以下の図は、２つの領域（結合後、異なるビット数を有する）のビットベクトルを有するブロックによりハフマン符号化するビットを示す。
【０３７１】
【表５】
0006030544.tif 000006
【０３７２】
領域毎にハフマン木を有することはメモリに関して高価すぎる可能性がある。従って、いくつかの実施形態において、同一のハフマン木が全ての領域に対して共有される。相関したビットが各領域において異なるため、各領域のビットを再順序付けでき、その結果、相関したビットは全ての領域の同一位置に体系的に置かれる。従って、全ての領域にわたりハフマン木を共有することは更に効率的になる。
【０３７３】
領域毎にビットを再順序付けするテーブルは地図データに格納される。尚、ビットを結合するための別個のテーブル及びビットを再順序付けするための別個のテーブルを符号化する必要はなく、その代わりに双方の変換（結合＋再順序付け）の合成である１つのテーブルのみを符号化できる。
【０３７４】
完全なブロックのビットを再順序付けする方法は以下のように進む。領域毎に、最も相関したビット対を見つける。完全に相関したビットが既に結合されているため、残りのビットで完全に相関されたものは存在しない。しかし、いくつかのビット対は他のビット対より相関される。最も相関したビット対（ａ，ｂ）は第１の完全なブロックのビット＃０及び＃１に再マッピングされる。
【０３７５】
【表６】
0006030544.tif 000007
【０３７６】
最も相関したビット対をグループ化した結果、完全なブロックのハフマン木はより少ない別個の符号（データを格納するのにより少ないメモリを使用するという利点を有する）を有し、統計はより偏る（これにより、ハフマン符号化がより効率的になる）。ランダムなビットシーケンスを含むのではなく、例えば最初の２ビットは殆どの場合が００又は１１を含み、１０又は０１を含むものはほぼない（他のビットについても同一である）。ビットを再順序付けせずに、最初の２ビットは全ての種類のパターン００、０１、１０、１１を含む。
【０３７７】
最初の２ビットを再マッピングした後、方法は、次に最も相関したビット対（ｃ，ｄ）を見つけ、それらを再マッピングして第２のブロックの最初の２ビットに格納する。
【０３７８】
【表７】
0006030544.tif 000008
【０３７９】
方法は、次に最も相関したビット対（ｅ，ｆ）を見つけ、それらを再マッピングして第３のブロックの最初の２ビットに格納する。
【０３８０】
【表８】
0006030544.tif 000009
【０３８１】
最後の完全なブロックに到達すると、方法は最初の完全なブロックに戻り、次に最も相関したビット対（ｇ，ｈ）を再マッピングする。いくつかの対が同一の相関性を有する場合、タイブレーカは、同一ブロックの前の対と最も相関した対（すなわち、（ａ，ｂ）と最も相関した対）を選択する。
【０３８２】
【表９】
0006030544.tif 000010
【０３８３】
アルゴリズム方法は、完全なブロック中の全てのビット対が再マッピングされるまで上記のように進む。
【０３８４】
【表１０】
0006030544.tif 000011
【０３８５】
この例において、ブロックサイズが奇数のビット数（１１ビット）を有するため、再マッピングされていないビットが完全な各ブロックに依然として存在する。方法は、「ｚ」と最も相関したビットを見つけ、それを第１のブロックに格納する。その後、Ｂと最も相関したビットを見つけ、それを第２のブロックに格納する。全ての完全なブロックが再マッピングされるまでこのような処理を行う。
【０３８６】
【表１１】
0006030544.tif 000012
【０３８７】
この時点で、全てのビットが完全なブロックに再マッピングされる。方法は、最後のブロックのビットを再マッピングし、完全なブロックに対して行ったように最も相関したビット対をグループ化しようとする。最後のブロックのビットを再順序付けすることは、地図のサイズを縮小することを助長できるが、以下の２つの理由により完全なブロックのビットの再順序付けほどは助長しない。
【０３８８】
・完全なブロックの方が重要である。この例において、各符号は、完全なブロックに対して３つのハフマン符号を使用するが、一方、最後のブロックに対しては１つのハフマン符号しか使用しないため、完全なブロックが最後の不完全なブロックより全体の地図のサイズに寄与していることは普通であり、完全なブロックのハフマン符号化を最適化することがより有用である。
【０３８９】
・最も相関したビットを全て既に選択してそれらを完全なブロックに再マッピングしたため、最後のブロックにおける再マッピングする残りのビットの相関性はより低い。従って、最後のブロックのビットのエントロピーは、完全なブロックのビットのエントロピーより高い。換言すると、最後のブロックのハフマン符号化は、完全なブロックのハフマン符号化ほど効率的ではない。
【０３９０】
【表１２】
0006030544.tif 000013
【０３９１】
尚、全ての領域の全ての完全なブロックに対して、同一のハフマン木が使用される。上記例におけるビットベクトルを符号化することにより、同一のハフマン符号を使用して全ての完全なブロックを符号化し、最終的に異なるハフマンコーデックにより最後のブロックを符号化する。
【０３９２】
【表１３】
0006030544.tif 000014
【０３９３】
方法が各ブロックの最初のビットを再マッピングする（第２のブロックに進む前に第１のブロックの全てのビットを再マッピングするのではなく）理由は、上記図面を見ることにより明らかである。同一のコーデックが全ての完全なブロックに使用されるため、全てのブロックに対する全ての符号を可能な限り同一にすることが望ましい。第１のブロックの全てのビット、次に第２のブロックの全てのビット（等）を再マッピングする場合、各ブロックは非常に異なるパターンを有する。すなわち、第１のブロックは最も相関したビットを有し、第２のブロックはより相関性の低いビットを有し、第３のブロックは更に相関性の低いビットを有する。完全なブロックの各列に対していくつかのハフマンコーデックを作成できるが、これはメモリに関して高価すぎると考えられる。ここまで概略を示した方法は、適切に動作する一方で、全ての完全なブロックに対して同一のハフマンコーデックを共有する。
【０３９４】
可能な他の最適化
ページのページ
ビットベクトルページ情報は、各ビットベクトルページの開始オフセットを見つけるために使用されるデルタフィールドを格納する。デルタフィールドは、オフセットの線形補間を使用して格納される。しかし、小さなノードＩＤ（レベル０、高速自動車道路）の周囲のビットベクトルがより大きいノードＩＤ（レベル５、行先道路）の周囲のビットベクトルより多くのビットを必要とするため、オフセットはそれ程線形ではない。
【０３９５】
補間が実際のオフセットを正確に予測しないため、ビットベクトルページ情報の符号化は要望される程の利点を有さない。補間を向上することにより、ビットベクトルページ情報テーブルの符号化を向上し、より効率的にすることができる。
【０３９６】
本発明のいくつかの実施形態は、１つのレベルではなく２つのレベルを有するビットベクトルページ（及び可能性として領域ページ）を使用してもよい。データをグループ化する２ｎ個のノードのページ（これらをサブページと呼ぶ）は、２Ｎ個のサブページのページにグループ化される。
【０３９７】
従って、線形補間パラメータは、グローバルではなくページ毎に格納される（ヘッダに）。例えば指標レベル２は、サブページの最初の方で２４＝１６個のノードをグループ化してもよく、指標１はページ中のそれらのサブページの２１０＝１０２３個のノードをグループ化してもよい。線形補間は、全体のノード数（ヨーロッパの西部及び中部の地図の４０，０００，０００個のノード）に対してではなく、１０２４＊１６＝１６Ｋ個のノードに対して行われるため、可変サイズオフセットの線形補間ははるかに正確になり、指標２のデルタフィールドはより小さくなる。
【０３９８】
ページが大きい（メモリに適合するのに十分に小さい）場合、追加の指標１のサイズは小さい。装置のメモリ内に適合可能であることは、データを使用する経路指定を遅くしないため有利である。平均ページサイズをヘッダに格納するのではなく、平均ページサイズは指標１のテーブルの全てのエントリに対して格納される。
【０３９９】
【表１４】
0006030544.tif 000015
【０４００】
ビットベクトルページのインタリーブ
上述したように、ビットベクトルが重要な道路（多くの非自明なフラグ）及びあまり重要でない道路（多くの自明なフラグ）に対して異なるため、ページオフセットに対する補間は正確でない。補間をより線形にする１つの単純な方法は、種々のネットワークレベルのページをインタリーブすることであり、これは本発明の実施形態において使用されてもよい。
【０４０１】
上記実施形態において説明したファイルは以下のページを格納する。
＃０
＃１
＃２
＃３
＃４
・・・
＃ｎ−３
＃ｎ−２
＃ｎ−１
より効率的である可能性のある他の実施形態において、以下のようにインタリーブして格納できる。
＃０
＃ｎ−１
＃１
＃ｎ−２
＃２
＃ｎ−３
＃３
＃ｎ−４
・・・
ページ＃ｘにアクセスする（例えば、経路計画アプリケーションにより）ために、ページはページ＃ｘ’をロードすることによりアクセスされる。
【０４０２】
・ｘ’ ＝ ２ ＊ ｘ  （ｘが偶数の場合）
・ｘ’ ＝ ２ ＊ （ｘ − （ｎ − １））  （ｘが奇数の場合）
このような一実施形態は、ページ毎に数ビットずつ指標付けのサイズを縮小するため有利である。しかし、データは、キャッシュするためにより不適切にグループ化される可能性があるため、データアクセスを遅くする可能性がある（ファイルシステムキャッシュにおいてヒット数が少なくなる）。
【０４０３】
全てのノードに対する領域ＩＤの非格納
領域ＩＤは、末端のノード及び２つの連結道路セグメントを有するノードに対して格納される必要はない。これらのノードは経路指定に対して無視される。これらのノードのうちの１つに行くことは、近傍の決定ノードに行くことに変換される。
【０４０４】
ページレベル及び／又はノードレベルにおける追加の情報の格納
地図データを見ると、自明なビットベクトル０００．．．０００又は１１１．．．１１１のみを含むビットベクトルページが多く存在する。いくつかの実施形態は、ページに印をつけるためにそれらページ毎に１ビットを格納してもよく、そのビットベクトルが０００．．．０００であるか又は１１１．．．１１１であるかを示すためにビットベクトル毎に単一ビットのみ必要とするため、ビットベクトルをそれらのページに格納することはより効率的になる。これは、自明なビットベクトルのみを含むページのサイズを縮小するだけでなく、非自明なビットベクトルを有するページに対してビットベクトル符号のハフマン木をより適切に最適化する（これらの符号の頻度のパーセント値が非常に増加するため、非自明なベクトルを示すためのビット数は減少される）。より精細なネットワークレベル（例えば、レベル３）において、殆どのページは自明なビットベクトルのみを含むため、約半分のページにおいてページ毎に１つのビットベクトルのみが存在する可能性がある。
【０４０５】
決定ノードのビットベクトルのみの格納
上述したように、いくつかの実施形態は、１つ又は２つの連結道路セグメントを有するノードに対するビットベクトルを格納しなくてもよい。しかし、他の実施形態は、より積極的であってもよく、決定ノードの周囲のビットベクトルのみを格納する概念を一般化してもよい。
【０４０６】
決定ノード及び決定道路セグメントの概念は、地図データの符号化に関して利点を有するため導入される。すなわち、次に説明するように、ビットベクトルは非決定道路セグメントに対して符号化される必要はない。
【０４０７】
・決定ノードは、ノードを出る（Ｕターンをせずに）複数の選択肢があるように経路指定するための進入道路セグメントが存在するノードである。
【０４０８】
・非決定ノードは、決定ノードでないノードである。従って、経路指定の出発地に関係なく、ノードを出る出口が常に１つのみ存在する。
【０４０９】
・決定道路セグメントは、決定ノードを出るのに合法な道路セグメントである。
【０４１０】
・非決定道路セグメントは、決定道路セグメントでない道路セグメントである。
【０４１１】
全ての決定道路セグメントは、決定ノードの周囲にある。しかし、決定ノードの周囲にある全ての道路セグメントが決定道路セグメントではない。非決定ノードの周囲にある全ての道路セグメントは非決定道路セグメントである。
【０４１２】
ビットベクトルは、決定道路セグメントに対してのみ符号化される。データを使用する経路決定技術が道路セグメントに既に存在する情報から判定できるため、ビットベクトルは、非決定道路セグメントに対して黙示的である（０００．．．０００又は１１１．．．１１１）。
【０４１３】
ノードが決定ノードであるかを判定する方法は？緩和できる基準は以下の通りである。
ｉｓＤｅｃｉｓｉｏｎＮｏｄｅ＝（ｌｉｎｅＣｏｕｎｔ＞＝３）＆＆（ｌｉｎｅＧｏｉｎｇＯｕｔＣｏｕｎｔ＞＝２）
式中、ｌｉｎｅＣｏｕｎｔは、経路指定不可能な線の種類（鉄道、基準線）を無視し、双方向に閉じた線を無視し、且つ通り抜け禁止道路（住宅エリア）を無視するノードに連結された線の合計である。ｌｉｎｅＧｏｉｎｇＯｕｔＣｏｕｎｔは、ノードを出るために利用するのに合法であるノードに連結された線の数である。
【０４１４】
ノードを出るためにある道路セグメントを利用するのが合法か否かは、以下の道路セグメント属性に依存する。
【０４１５】
・道路セグメントの種類（鉄道＆基準線は常に違法である）
・道路の順方向／逆方向の流れ（道路セグメントフラグに格納される）
・道路セグメントフラグの通り抜け禁止属性（通り抜け禁止道路セグメントはいずれのビットベクトルも有さない）
いくつかの実施形態において、非決定道路セグメントを無視することは、約４０％の道路セグメントを廃棄できる。このパーセント値は、地図に関係なく非常に安定していることが分かっている。自明なビットベクトルを主に除去するため、ビットベクトルの４０％の符号化を回避することは利点であるが、節約される地図のサイズは４０％未満である。
【０４１６】
３つ未満の連結道路セグメントを有するノード（ダミーノード）の周囲のビットベクトルを除去することにより、非自明なビットベクトルが除去されるため、このカテゴリの非決定道路セグメントに対する地図のサイズの節約は非決定道路セグメントに対する節約より大きい。一方、フィルタリングは、復号器（地図を使用する経路指定方法等）が道路セグメントの種類及び線の道路セグメントフラグを復号化し且つ黙示的であるビットベクトルを計算するためにそれらに論理を適用することを必要とする。これは、処理を遅くする可能性がある。
【０４１７】
理論上、実施形態は、退出道路セグメントが合法であるかを決定するために操作（すなわち、右左折制限）に着目するが、そのような技術は複雑さを増す。操作を無視することは、実施形態が厳密に必要な数より多くのビットベクトルを符号化してもよいが方法の単純化が達成されることを意味する。
【０４１８】
非決定ノードの例
ａ−−＜−＞−−ｂ−−＜−＞−−ｃ
この例において、（ｂ）は双方向にナビゲート可能である２つの道路セグメントに連結される。＜＝２個の連結道路セグメントが存在するため、（ｂ）は決定ノードではない。
【０４１９】
従って、ノード（ｂ）を出る双方の道路セグメントのビットベクトルは符号化されない。復号器は、それらを１１１．．．１１１に黙示的に設定できる。
ａ−−＞−−ｂ−−＜−＞−−ｃ
｜
＾
｜
ｄ
この例における矢印＞は、フローの合法な方向を示す。出口が１つのみ存在するため、（ｂ）は決定ブロックではない。従って、（ｂ）の周囲のいずれの道路セグメントもビットベクトルを必要としない。
【０４２０】
ノード（ｂ）を出る道路セグメント（ｂ）−＞（ｃ）に対するビットベクトルは符号化されず、黙示的に１１１．．．１１１となる。（ｂ）を出る違法な道路セグメントに対するビットベクトルも符号化されず、黙示的に０００．．．０００となる。
【０４２１】
決定ノードの例
ａ−−＜−＞−−ｂ−−＜−＞−−ｃ
｜
＾
｜
ｄ
（ｂ）は、（ｄ）から来る場合に選択肢があるため決定ノードである。すなわち、経路指定は（ａ）又は（ｃ）に向かって継続可能である。
【０４２２】
尚、この例において、（ａ）から来る場合、選択肢はない。すなわち、経路指定は（ｃ）に向かってのみ継続可能である。しかし、ノード（ｂ）は、（ｄ）から来る場合に少なくとも選択肢があるため依然として決定ノードである。従って、ビットベクトルは、ノード（ｂ）の周囲の２つの決定道路セグメントに対して格納されるべきである。
【０４２３】
道路セグメント（ｂ）−＞（ａ）及び道路セグメント（ｂ）−＞（ａ）が決定道路セグメントであるため、ビットベクトルはこれらの道路セグメントに対して格納される。
【０４２４】
交通の逆方向／順方向の流れによると道路セグメント（ｂ）−＞（ｄ）を利用するのは違法であるため、ビットベクトルはこの道路セグメントに対して格納されない。これは、黙示的に０００．．．０００である。
【０４２５】
ビットベクトルの論理和
ノードが３つの連結道路セグメントを有し、最初の２つの復号化道路セグメントが以下のビットベクトルを有すると仮定する。
【０４２６】
００００００００００００００００００００
００００００００００００００００００００
第３のビットベクトルは、以下の通りであるため符号化される必要はない。
【０４２７】
１１１１１１１１１１１１１１１１１１１１
これは、ノードａの周囲の道路セグメントのビットベクトルがこの順序で現れる場合にのみ動作可能である。すなわち、全てのビットベクトルが０００．．．０００であり、最後のビットベクトルが１１１．．．１１１である。実際には、これはより精細なレベル（例えば、レベル３）のネットワーク（殆どの道路セグメントが存在する）において非常に頻繁に現れると考えられる。
【０４２８】
最初の２つのビットベクトルは以下の通りとする。
【０４２９】
０００００００００００００００００１１０
００００００００００００００００００１０
第３のビットベクトルは、未知であり且つ何らかの方法で符号化される必要がある２ビット以外の全てのビットを１に設定できる。
【０４３０】
１１１１１１１１１１１１１１１１１？？１
上記例において、殆どのビットが既知であるため、ビットベクトル全体を符号化するより効率的に２つの未知のビットを符号化するためにこの情報を使用できるべきである。従って、この例において、２ビットを符号化すればよい。
【０４３１】
このプロパティを使用する可能な高速復号化方式は、道路セグメントの全ての先のビットベクトルの論理和をとることにより現在のノードの道路セグメントの全ての復号化ビットベクトルのビットマスクを計算することである。上記と同一の例を使用して、ノードが３つの連結道路セグメントを有する場合及び先の２つの道路セグメントが以下のビットベクトルを有する場合、
０００００００００００００００００１１０
００００００００００００００００００１０
ＯＲビットマスクは以下の通りである。
【０４３２】
０００００００００００００００００１１０
ノードの周囲の符号化する第３の最後のビットベクトルを以下の通りとする。
【０４３３】
１１１１１１１１１１１１１１１１１００１
極めて稀な１１１１１１１１１１１１１１１１１００１のハフマン符号を符号化する代わりに、符号器は、以下の場合に他のあらゆる符号（ｏｔｈｅｒＣｏｄｅ）を自由に符号化できる。
【０４３４】
ｖａｌｕｅ＿ｔｏ＿ｅｎｃｏｄｅ ＝ 〜ｂｉｔＭａｓｋ ｜ ｏｔｈｅｒＣｏｄｅ
この例において、ｏｔｈｅｒＣｏｄｅ＝０００００００００００００＊０００００００は、以下が成り立つために適格である。
【０４３５】
ｖａｌｕｅ＿ｔｏ＿ｅｎｃｏｄｅ ＝ １１１１１１１１１１１１１１１１１００１ ＝ 〜０００００００００００００＊００００１１０ ｜ ０００００００００００００＊０００００００
００００００００００００００００００００の頻度がより高いため、００００００００００００００００００００を符号化することは、１１１１１１１１１１１１１１１１１００１を符号化するより非常に効率的である。復号化は、ビットベクトルを復号化する時は常にビットマスク（又は動作）を計算し且つ最後に復号化されたビットベクトルにビットマスクを適用すればよいため、復号化は速い。
【０４３６】
実際のビットベクトル＝ビットマスク＆復号化ビットベクトル
＝〜０００００００００００００００００１１０ ＆ ００００００００００００００００００００
＝１１１１１１１１１１１１１１１１１００１
この最適化は、ノードの周囲の道路セグメントが最後の領域において殆どが１であるビットベクトルの道路セグメントを有するように格納される場合に適切に動作する。しかし、これは困難である。
【０４３７】
・ノードの周囲の道路セグメントの格納は、ビットベクトルの計算前に行われる（再符号化するためにビットベクトル情報を帰納的に使用しない限り）。
【０４３８】
・道路セグメントは道路名で既にソートされている。道路名が特定される場合、ノードの周囲の道路セグメントをソートできる。
【０４３９】
ネットワークレベルの使用
領域のレベルに加えて、地図データ内の道路セグメントは道路セグメントレベルに従って分類される。出発ノードの周囲において道路セグメントネットワークレベルとビットベクトルとの間には強い相関性がある。すなわち、一般に別の領域までの経路指定は、高速自動車道路等の高いレベルの道路セグメントネットワークを利用するのを好む。最も重要な道路セグメントネットワークレベルは、高速自動車道路レベルである可能性が高く、これはレベル１であってもよい。
【０４４０】
以下の例は、異なるネットワークレベルにおける道路セグメントとの交差点を示す。
【０４４１】
４
｜
｜
１＝＝＝＝＝＝＝２＝＝＝＝＝＝＝３
線（２）−＞（１）は、ネットワーク４（重要）にある。
線（２）−＞（３）はネットワーク５（あまり重要でない）にある。
線（２）−＞（３）はネットワーク５（あまり重要でない）にある。
【０４４２】
ビットパターンは以下のようになる可能性が高い。
２     １     ？？？？？？？？？？？？
２     ３     ？？？？？？？？？？？？
３     ４     ００００００００００００。
【０４４３】
精細ネットワークレベルのノードに対するビットベクトルの非格納
経路指定は、目的地又は出発地に近接する場所以外ではネットワークレベル５等の非重要道路セグメントネットワークレベルをほぼ通過しない。従って、レベル５のビットベクトルを格納しないことが可能であり、従ってレベル５の道路セグメント数が多くても経路指定への影響は最小である。殆どの場合の経路指定は、いくつかの更なる重要な道路セグメントネットワークレベルに迅速に到着するため、経路の開始又は終了において最も重要でないネットワークレベルの道路セグメントを殆ど探索しない。これらのノードに関する探索加速データは、最も重要でないネットワークレベルに戻るナビゲートセグメントをスキップし且つより重要なネットワークレベルに通じるか又は入るナビゲートセグメントを使用するようにルータにほぼ常に伝える。目的地が依然として遠い場合に最も重要なネットワークレベルが使用されるため、このことは、そのネットワークレベルにおいて当てはまる。
【０４４４】
最も重要でない道路セグメント（例えば、レベル５）におけるビットベクトルをドロップすることに加えて、そのネットワークにおいて領域ＩＤを符号化しないことも可能である。
【０４４５】
ビットベクトルのいくつかの０の１への変換
これは、不可逆圧縮方式である。
【０４４６】
ビットベクトルが１つの０だけ（又は可能性として小さい閾値未満）を含む場合、以下の結果（すなわち、その道路セグメントを最速経路の一部になるように設定する）が得られる場合はそれを１に変換できてもよい。
【０４４７】
・自明なビットベクトル１１１．．．１１１（自明なビットベクトルは非自明なビットベクトルよりコンパクトに符号化されるため）
・現在のビットベクトルページの履歴で既に見つけられたビットベクトル（より効率的に符号化されるため）
ビットベクトルにおいて０を１に変換することは経路指定結果に影響を及ぼさず、経路指定がより多くの道路セグメントを考慮するようにすることにより遅くなるだけである（最速経路の一部になるように設定されるため）。しかし、特に経路指定の速度に関して性能への悪影響が小さく、地図の節約が大きい場合、本発明のいくつかの実施形態はこの方法を採用してもよい。
【０４４８】
経路指定
図１８は、従来のＡ＊探索方法により探索された複数の道路セグメントと共に開始ノード１６０２及び行先ノード１６０４を有し且つあるエリアを範囲に含む地図１６００を示す。選択された経路を点線１６０６で示す。
【０４４９】
図１９は、図１８の地図と同一エリアを範囲に含み且つ同一の開始ノード１６０２及び行先ノード１６０４を示す地図１６５０を示す。図１９は、図１８の経路を生成するために使用したのと同一の道路ネットワーク及び基準（例えば、双方とも自動車で移動され、最小にするコスト関数として速度を使用することを要求する）を利用した本発明の一実施形態を使用して探索された道路を強調表示する。方法により選択された経路は、点線１６０６で示され、その道路セグメントは図１８で算出されたものと同一である。従って、本発明の実施形態により算出された経路は、いわゆる数学的に正確であり、最小になるように選択された所定のコストモデルに関して最善／最適な経路を見つける。従って、本発明の実施形態により探索された道路セグメントは、従来技術と比較して非常に少ないことが明らかである。本発明の実施形態の方法は、従来のＡ＊方法より高速であり、一般にははるかに高速である。
【０４５０】
尚、経路１６０６が目的地１６０４に近づくと開始時と比較してより多くの経路が探索される。すなわち、経路１６０６が地点１６５２を越えて進む場合、最低コスト経路以外に道路が探索される。この１つの説明としては、方法が地点１６５２においてレベル０領域からレベル１領域に切り替わったからである。目的地１６０４付近で更なる道路セグメントが探索されることが更に分かるだろう。ここでも、これは、経路計画方法がこの付近でレベル１からレベル２に切り替わったことを指摘することにより説明できる。
【０４５１】
従って、長い範囲での経路指定の場合、一般に最速経路は１つのみ存在する。しかし、方法がより精細なレベルに切り替わると（例えば、レベル０から１に）、「最低コスト」として印がつけられ且つ従って探索される必要がある経路が２つ以上存在してもよい。
【０４５２】
地図データが作成され、ビットベクトルが算出及び格納されると、２つの地点間の経路を算出するのに使用される。
【０４５３】
図２０は、ネットワークが経路計画アプリケーションにより探索される従来のＡ＊方法を示す。ここで、ノードにおいて更に探索する道路セグメントに関する決定が行われる。これを達成するために、次のノードまで移動するためのコストは、次のノードから目的地まで移動するための推定されたコストに追加される。所定のノードからの最小コストを有するパスは、更に探索される。方法が進み且つ各繰り返しにおいて最低コストが考慮されるため、方法はそれまでに発生したコストの合計を保持する。
【０４５４】
例えば、ノードＢから開始すると、双方のノードＣ及びＤは開始ノードであるＢから２コスト単位だけ離れていることが分かる。しかし、ノードＤからノードＦに到達するための推定コストは３単位であり、ノードＣからノードＦに到達するための推定コストは５単位である。従って、Ａ＊方法は、次のノードまでのコスト＋目的地までの推定コストがノードＤまでの道路セグメントに対してより少ないため（すなわち、ＢＣ＝２＋５＝７であるが、ＢＤ＝２＋３＝５である）、ノードＣへの経路よりノードＤへの経路を好んで探索する。
【０４５５】
経路計画が本発明の実施形態のビットベクトルを使用して実行されることを考慮すると、道路セグメント毎のビット（すなわち、図１０の列７０４）は、行先領域までの最低コスト経路の一部となる候補である道路セグメントを特定する。従って、図２０に関連して説明したＡ＊方法は修正され、図２１に示した方法が得られる。
【０４５６】
一般に経路計画は、図２１に関連して説明するようなビットベクトルを使用して実行される。しかし、本発明のいくつかの実施形態は、種々の状況下において経路計画がＡ＊（又は他の従来の方法）にフォールバックすることを可能にしてもよい。種々の実施形態は、以下のうちのいずれかを利用してもよい。すなわち、ビットベクトル情報が失われていること（これにより、ビットベクトルがない場合でもシステムは機能できる）、コスト関数が使用されること、ビットベクトルが算出されたコスト関数以外の経路指定（一般に最速経路であるが必ずしも最速経路である必要はない）、ユーザがビットベクトルを事前計算するのに使用された基準と異なる基準を指定すること（例えば、ユーザは高速自動車道路を回避したい）、乗り物の種類がビットベクトルの事前計算に使用されたものと異なる（例えば、ユーザは自動車ではなく徒歩である）こと、及び経路が閾値の長さを下回ること（例えば、経路の開始点及び終了点が同一領域内にある）である。
【０４５７】
図２０と比較して、２つの追加の数字１８００、１８０１を図２１に示す。更に領域は、図２１において破線１８０２及び１８０４により示される。「１」１８００は、道路セグメントＢＤがノードＢから目的地ノードが位置する領域までの少なくとも１つのコスト関数に対する１つの低コスト経路の一部であることを示す（他で説明するように、更に他の低コスト経路が存在してもよい）。「０」１８０１は、道路セグメントＢＣがノードＢから目的地ノードが位置する領域までのいずれの低コスト経路の一部でないことを示す。
【０４５８】
従って、ノードＡから開始すると、本発明の実施形態は、上記で概略を示したＡ＊を使用してＡからノードを探索する。しかし、ノードＢに到達すると、道路セグメントＢＤのみが最低コスト経路の一部である可能性があることの明示的な表記があるため、探索を更に使用する必要はない。従って、Ａ＊方法が使用され、最低コストパスを見つけると、次にビットベクトル内の関連ビットを見ることにより最低コスト経路を選択する。
【０４５９】
しかし、種々の最低コストパスが種々の時間における及び／又は種々のコスト関数に対する一対の領域の間に存在する場合、最低コストデータは、その対の領域間で２つ以上の最低コストパスを特定してもよい。従って、例えば道路セグメントＢＤ及びＢＣに対する数字１８００及び１８０１が、各道路セグメントが特定の時間において最低コストパスの一部であることを示す値「１」を有する場合、開始ノードと目的地ノードとの間（出発地と目的地との間）の経路指定は、２つ以上の最低コストパスを見つけてもよく、競合する最低コストパス間で判定する必要がある。本実施形態において、ビットベクトルは、各道路セグメントが最低コストパスの一部である時間を特定しない。そのため、経路指定アルゴリズムは、パスの区分を移動する時間及びコスト関数に基づいて双方の可能な最低コストパスに対してコスト解析を実行する。この時間は、出発地／開始ノードからの出発時間から判定されてもよい。コスト関数はユーザによる選択から判定され、例えばユーザは、全ての経路指定が選択に従って判定されるようなコスト関数／基準を図３２に示すような設定メニューから選択してもよい。例えばコスト関数／基準は、最短距離、最短移動時間、最安（環境的な影響に関して）、最小の使用燃料、最小の生成ＣＯ２、１つ以上の特定の道路の種類の回避又は好み等のうちの１つ以上であってもよい。
【０４６０】
あるいは、ユーザは特定の経路の計画を要求する時にコスト関数／基準を選択してもよい。
【０４６１】
本発明のいくつかの実施形態は、電子地図のユーザがその電子地図内の誤りを強調表示することを可能にしてもよい。特にユーザはブロックされているとして道路セグメントに印をつけることができ（すなわち、ベクトルがブロックされていることを示せる）、これは交通事象と同一の影響を交通の流れに与える。従って、ブロックされた道路セグメントを表すデータは、交通事象の詳細を示すデータと同様に考慮されてもよい。
【０４６２】
あるいは又はそれに加えて、実施形態は、道路のブロックが解除されたこと又は新しい道路ができたこと等をユーザが示せるようにしてもよい。これらのいずれも、電子地図内に新しいベクトルを作成するものと考えられてもよい。一般に例えば図１０に示すような経路指定加速データが前処理により生成されるため、経路指定加速データが新しいベクトルを参照しないために経路指定加速データを利用する経路指定方法はそのような新しいベクトルを考慮しない。
【０４６３】
ユーザは、タッチスクリーン又は他のボタン、スイッチ等を使用してＰＮＤ上に直接入力する手段、あるいは音声命令による手段等のあらゆる適切な手段を使用して訂正を電子地図に入力してもよい。
【０４６４】
上述したように、ユーザ（特定のナビゲーション装置のユーザであるか又はＭａｐ  Ｓｈａｒｅ（登録商標）等の技術により識別された別のユーザであるかに関らない）は、電子地図内に新しいベクトル（すなわち、以前に電子地図の一部ではなかったベクトル）が存在することを示せる。しかし、経路指定加速データが前処理により生成されるため、それらの新しいベクトルは経路の算出において考慮されない。従って、新しいベクトルが電子地図に追加されることを可能にする本発明の実施形態は、新しいベクトルが地図の各領域までの経路指定加速データにより示されるような最低コスト経路の一部であることを反映するように経路指定加速データを修正してもよい。すなわち、そのベクトルに対する全てのビットが、ベクトルが電子地図の各領域までの最低コスト経路の一部であったことを示す「１」に設定されるように、新しい各ベクトルに対する行は設定される。これは実際には当てはならないことが当業者には理解され、また、このようにビットを設定することにより、例えば出発地と目的地との間の経路を生成する時に経路の算出において新しいベクトルを考慮することになることが当業者には理解されるだろう。
【０４６５】
図１０ａに示すように、セグメント中の推定移動速度がどのように計時変化するかの速度プロファイルは各セグメントと関連付けられる。これらの速度プロファイルから、関連する時間における推定速度が判定され、これは、その時間にその道路セグメントを移動するためのコストを判定するために使用される。各最低コストパスの道路セグメントを移動するためのコストを合計することにより、各最低コストパスに対するコストが判定される。ナビゲーション装置は、その時間に対する最低コストを有する最低コストパスを経路に選択してもよい。
【０４６６】
決定された経路はディスプレイ２０６に表示されてもよい。図２３は、どのように地図データ上に経路が表示されうるかの一例を示す。
【０４６７】
本実施形態において、ディスプレイは、経路の複数のナビゲート可能セグメントの少なくともいくつかにおける予測速度の指標を含んで表示する。本実施形態によれば、それらの指標は、経路のカラーリング、及び、経路に沿った予測速度を示す地図の画像の端における時間バー２０００を含む。例えば、ナビゲート可能セグメントは、予測速度が第１の閾値を上回る場合には第１カラー、例えば緑でカラーリングされ、予測速度が第２の閾値を下回る場合には第２カラー、例えば赤でカラーリングされる。
【０４６８】
経路を決定する代替の方法を、図１０ａ、図２４乃至図３１を参照して以下で説明する。特定の時間での経路に対するコストを判定するよりもむしろ、時間と共に変化するコストを示すコストプロファイルが判定されうる。本実施形態において、各ナビゲート可能セグメントに対する速度プロファイルの単一の値よりも複数の値が複数の経路に対するコストプロファイルを決定するために使用される。
【０４６９】
例えば、図２１を参照すると、各道路セグメントＢＣ、ＣＥに対する単一値を有するよりもむしろ、各経路におけるコストが時間と共にどのようにコスト変化が起こるかを示す分布である。それらのコスト分布は、経路に対するコストプロファイルを決定するために加算される。ツリーを通じてコストプロファイルの伝播は図１０ａにも示す。
【０４７０】
本実施形態において、各ナビゲート可能セグメントは、各時間に対する１２時間ビン（ｂｉｎ）を含んで関連付けられた速度プロファイルを有し、各時間ビンは、当該時間におけるナビゲート可能セグメントを通じて移動する際の予測速度を含む。各ビンの予測速度に対するコストが決定され、各関連ビンに対するコストがコストプロファイルを決定するために経路の複数のナビゲート可能セグメントにおいて加算される。各セグメントにおいて加算される値は、ユーザが各ナビゲート可能セグメントに到達することを目的とする場合に依存して変更されるであろう、各セグメントに沿って移動する際の期待時間と同じ時間となるビンからでなくともよい。例えば、ナビゲート可能セグメントＢＤに沿った移動でユーザが５分掛かると予想され、したがって、セグメントＢＤ、ＤＦを加算したビン値は、５分ごとに分割されたビン値であってもよく、つまり、ＢＣにおける時間ビン値Ｔは、ＤＦにおける時間ビン値Ｔ＋５に加えられる。
【０４７１】
最小コストパスの一部であるナビゲート可能セグメントのみが、最小コストパスでないナビゲート可能セグメントと競合する中で探索される。したがって、考慮すべきパスＢＤＦ（登録商標）及びパスＢＣＥＦに関して、両方のパスが最小コストパスとして最小コストデータによって特定されなければならない。
【０４７２】
両方のパスＢＤＦ（登録商標）及びパスＢＣＥＦが種々の時間において最小コストパスであり、その後、２つの経路が交差する場合、ＢＤＦ（登録商標）及びＢＣＥＦのコストプロファイルは、程度（degree）及び更に伝播される可能性を維持することを必要とする。これを達成するために、プロセッサは、２つのコストプロファイルＣ１及びＣ２をお互いの上に重ね、上限分布ＵＢ（実線で示す）及び下限分布ＬＢ（点線で示す）を決定する計算を実行する。これは、図３０及び図３１に示す。ＵＢ及びＬＢ分布は、決定される各経路に対する最大及び最小コストプロファイルを許容する他の伝播に対して使用される。
【０４７３】
上限分布及び下限分布のさらなる伝播は、それらのプロファイルへ追加される次のナビゲート可能な経路に対するコスト値で同様に発生する。探索した経路が分岐し、その後、ノードＦのような後のノードで再び交差する場合、その後、各入力パスにおける２つの上限プロファイル及び２つの下限プロファイルが、単一の新たな上限プロファイルを決定するために２つの上限プロファイルを重ねることによって、かつ、単一の新たな下限プロファイルを決定するために２つの下限プロファイルを重ねることによって、再び処理される。このように、プロファイル数の増加は、経路を決定するために必要な時間やメモリの容量（ＰＮＤに限定されるメモリのように）を必要以上に増大させないレベルに維持される。
【０４７４】
他の実施形態において、上限プロファイル及び下限プロファイルのいずれか１つのみが経路に沿ったさらなる伝播に対して維持されるのみである。他の実施形態において、２つの入力プロファイル（incoming profile）の平均は経路に沿ったさらなる伝播に対して平均したプロファイルとなるように決定される。
【０４７５】
コストプロファイルが全体経路に対して決定されると、上限プロファイル又は下限プロファイルの１つが最終的なプロファイルとして選択される。当該プロファイルは、以下で説明するように、ナビゲーション装置上の表示を決定するために使用される。
【０４７６】
図２４及び図２５は、コストプロファイルの複数の値における道程が表示されている。
【０４７７】
図２４において、所定時間毎に、本実施形態では１５分毎に区分された個別の出発時間における時間バーとともに、コストファイルが始点（出発地）から出発した時間と、行先（目的地）への到達時間とが表示された様子を示す。図２３の時間バー２０００のように、各時間バーは、経路の異なる部分に沿って予測速度を示すように符号化された色で表示される。矢印２００１，２００２は、ユーザによって選択されると、より早い開始時間又はより遅い開始時間における出発時間、到着時間及び時間バーを表示するように提供される（左矢印２００１を選択するとより早い開始時間が表示され、右矢印２００２を選択するとより遅い開始時間が表示される。）。時間バーを選択すると、図２３に示すように、ディスプレイには選択された開始時間における表示が行われる。
【０４７８】
図２５において、コストプロファイルは設定した期間における、例えば、１６８時間（１週間と同等）の期間における連続したグラフとして表示される。このグラフは、当該コストプロファイルを形成するのに寄与する始点から行先までの経路を示す地図とともに表示される。グラフ及び経路は、ユーザが当該経路をいつ使用するかを決定できるようにカラーコード化（実線及び点線で表示するように）されて表示される。例えば、７時４０分と９時１５分との間のグラフは、破線２００３が点線２００４の第１部分よりむしろ続くべきである経路の開始をを示すように色づけされる。そのような表示は、ユーザが容易に始点と行先の間の移動コストがどのように計時変化するかや、当該計時変化が経路にどのように影響するかを容易に参照することを許容する。
【０４７９】
図２６乃至図２８は代替の実施形態を示す。本実施形態では、コストプロファイルは、上述したように決定されものの、ユーザが指定された移動時間において決定された経路の画像のみが表示されるのみである。しかし、表示した経路が適用可能な日時を示すボックス２０１０が表示される。日時の両方の端に提供される矢印が選択されると、日時の何れかを変更した、決定した経路を示す地図データの画像が表示される。日時の何れかの変更は、経路の変化をもたらし、経路の移動時間や移動する距離の変化とともに、新たな経路を表示するように表示が更新される。それらの更新した表示の例が図２７及び図２８に示される。
【０４８０】
表示の更新は、”リアルタイム”例えば、ミリ秒のオーダで発生し、例えば１０００ミリ秒よりも短く、好ましくは５００みりびょうよりも短い時間で行われる。そのような高速な再計算時間は、予め処理した最低コストデータの使用を通じてか、それらの他の時間が既にプロファイル探索を通じて決定されている経路であるか、の何れかによって達成されうる。
【０４８１】
図２９は、プロファイル探索を使用するナビゲーション装置の他の機能を示す。本実施形態において、移動時間、例えば、開始時間の選択に関し、ナビゲーション装置のプロセッサは、当該時間での移動コストを、移動時間、例えば、移動時間であれば３０分早い時間でのウィンドウ・アラウンドにおけるコストプロファイルの値と比較してもよい。プロセッサがより低いコストを有するウィンドウ内の移動時間を発見すると、その後、プロセッサは、より良い結果を与える移動時間の指標を表示させる。例えば、図示した実施形態において、Ｎｏｔｅ２０１５には、ユーザが１５分遅く出発すると、移動時間がこの例では１０分短縮することを当該ユーザに知らせる旨の表示が行われている。
【０４８２】
ここまで説明した経路指定を実行するために、ビットベクトル情報は、復号化処理を使用して図１１〜図１３に関連して説明した符号化副ファイルから取得される。
【０４８３】
上述した前処理の出力は以下を含む。
【０４８４】
・殆どのノードに対する階層領域の割り当て
・これらのノードにおける退出道路セグメントに対するビットベクトルの割り当て
地図のロード
一貫性検査
地図データがロードされる場合、副ファイルの集合は地図ディレクトリに存在すべきであり、存在しない場合、復号器は経路探索が探索加速データなしで実行されるように探索加速データを非アクティブにする。データ完全性を保証するのを助長するいくつかの検査がある。これを一覧表示する。
【０４８５】
副ファイルは命名規則に従う。
【０４８６】
レベルの数は副ファイルの数により与えられるが、各副ファイルのヘッダにも格納され、副ファイルの数に等しい。
【０４８７】
各副ファイルは、副ファイル名で指定されたレベルと同一の各レベルの領域数を格納する。更に副ファイルは、全ての副ファイルに対して同一であるべき以下の情報を格納する。
【０４８８】
・副ファイルのバージョン
・「ビットベクトルページ」（以下に説明する）毎のノード数
各副ファイルには、以下を特定するチェックサムが存在する。
【０４８９】
・全体の特定の副ファイル集合
・全体の地図
これらは、所定の電子地図に対して関連付けられた副ファイルに対して正確であるべきである。上記検査のいずれかが失敗した場合、探索加速データプロパティはこの地図に対してアクティブにされない。
【０４９０】
メモリにロードされるデータ構造
復号器は、外部メモリの実現例の副ファイルを読み出す。これは、ビットベクトル副ファイルのコンテンツがメモリに完全にロードされず、必要に応じてのみ読み出されることを意味する。しかし、ある一般的なデータは最初にメモリにロードされ、地図がロードされる限りそこに保持される。
【０４９１】
ヘッダ情報
各副ファイルは、図８〜図１０に関連して上述したデータを含むヘッダセクションで開始する。この情報は、副ファイル毎にメモリに格納される。
【０４９２】
ハフマン木の定義
副ファイルは、いくつかのハフマン木の定義を含む。ハフマン木の各定義は、特定のハフマン符号化の完全な記述を与え、副ファイルビットストリームの一部を元のデータに復号化するために（すなわち、副ファイルのビットシーケンスを数字又は他のある特定の値に復号化するために）後で使用される。以下のハフマン木の定義は、各副ファイルから読み出され且つメモリに保持される。
【０４９３】
・各ノードにおいて道路セグメント数を復号化するためのハフマン木。（符号化された道路セグメント数は、基礎となる地図の道路セグメント数より少ない。尚、復号器は基礎となる地図とは無関係である。すなわち、地図を読み出す必要はない。）このハフマン木は、レベル０の副ファイルにのみ格納される。
【０４９４】
・ページ符号を復号化するためのハフマン木（以下に説明する）。
【０４９５】
・ビットベクトルブロックを復号化するためのいくつかのハフマン木。木の定義数は、副ファイルヘッダに格納されるような正規のビットベクトルのブロックの長さにより与えられる。これはブロックの長さ−１に等しい。（道路セグメントに対するビットベクトルのビット列全体はブロックに分割される。ビットベクトルのビット列の長さが正規のブロックの長さの倍数でない場合、最終的なブロックはより短い。２〜正規のブロックの長さまでのブロックの長さ毎に１つのハフマン木が存在する。長さ１のブロックの場合、これは単に１ビットであり、直接格納されるため、ハフマン木は使用されない。）
・ビットベクトルに対して復号化方法を選択するためのいくつかのハフマン木。これらの木の数はヘッダで指定される。その使用については以下に説明する。
【０４９６】
近傍リスト
最も精細なレベル以外の各レベルにおいて、副ファイルは近傍リストを符号化する。レベルｋにおける領域の近傍リストは、レベルｋ領域の近傍領域と呼ばれる０個以上のレベル（ｋ＋１）領域のリストである。レベルｋの副ファイルの近傍リストセクションは以下の２つの部分を有する。
【０４９７】
・第１の部分は、各レベルｋサブ領域に対する近傍領域の数を含む。例えば（ｋ＝１）、グローバルレベル０において４０００個の領域があり、各グローバル領域が１０個のレベル１領域に細分される場合、レベル１の副ファイルは４０００＊１０個のレベル１サブ領域を含む。これらの各々に対して、個別の近傍リスト（レベル２領域から成る）の長さが与えられる。
【０４９８】
・第２の部分は、長さが第１の部分から既知である実際の近傍リストを含む。各近傍リストはレベル（ｋ＋１）サブ領域のリストである。
【０４９９】
領域再マッピングテーブル
副ファイルは、例えば結合及び再順序付け等により圧縮形式でビットベクトルを格納する。レベルｋの副ファイルは、ブロックにより符号化されたビットベクトルを伸張するのに使用される領域再マッピングテーブルを有する。これは以下の２つの部分から成る。
【０５００】
・第１の部分は、レベルｋサブ領域により指標をつけられる配列である。レベルｋのサブ領域毎に、圧縮ビットベクトルの長さを含む。これは、ビットベクトルがブロックにより符号化される各サブ領域におけるノードの退出道路セグメントにとって有意義である。
【０５０１】
・第２の部分は、（１）非圧縮ビットベクトルのビット位置及び（２）レベルｋサブ領域により指標をつけられた２次元配列である。配列のエントリは、ブロックにより読み出された非圧縮ビット列の所定のビット位置に対する圧縮ビットベクトルのビット位置を指定する。
【０５０２】
尚、第１の部分のみがメモリに保持される。第２の部分は、大きいため、復号化中に要望に応じてのみ使用される。現時点で、領域再マッピングテーブルはグローバルレベルの副ファイル（ｋ＝０）にのみ格納される。
【０５０３】
経路クエリの開始
復号器は、出発位置から行先ノードの集合までの経路探索を加速するために使用される。（目的地が２つ以上のノードから成る一例は、全体の道路の広がりが目的地として使用される場合である。）行先ノードは１つ以上の目標領域の集合を規定する。
【０５０４】
尚、目標領域は領域ＩＤのシーケンスであり、各領域ＩＤは各セグメントレベルに対するものであり、レベル０から開始する。新しい探索の各々の開始時、目標領域の集合は、先の目標領域集合をクリアし且つ新しい行先ノードを復号器に渡すことにより構築される。復号器は、重複のない目標領域のリストを判定する。所定のノードの領域を見つける機構は探索と同一であり、詳細については以下を参照。
【０５０５】
経路探索中のノードの走査
残りの説明は、目標領域の集合が設定されたと仮定する。復号器の特徴は、道路ネットワークのノードＩＤを仮定すると、このノードを出る道路セグメントにわたり指標をつけられるビット配列（このノードに対するビットベクトル及び所定の目標領域）を返す関数である。ノード及びあるノードにおける道路セグメントの順序付けは、地図により規定される。ビット値が０である場合は必ず、これは対応する道路セグメントが探索中に無視されることを意味する。（通常、これにより探索空間は大きく減少され、従って探索の実行時間が短縮される。）
少数のノードの場合、領域情報もビットベクトルデータも副ファイルに格納されない。これらのノードに対して、復号器は全てのビットが１であるビット列を返す。（これにより、経路探索がこのノードにおける道路セグメントをスキップすることを防止する。）復号器は、これが所定のノードに当てはまるかを示すブールクエリ関数を有する。更に所定のノードが先に固定された目標領域の１つに配置されるかを示すブールクエリ関数が存在する。目標領域のノードに対して復号器により返されたビットベクトルは、ここでも全てのビットが１であるビット列である。これらのブールクエリ関数は経路探索における最適化のために使用される。
【０５０６】
副ファイル形式に従って、所定のノードに対するビットベクトルデータはいくつかのステップで復号化される。各副ファイルにおいて、領域及びビットベクトル情報は、いわゆるページに編成される。ページ毎のノード数は２の既定の累乗（例えば、１６）であり、副ファイル集合の副ファイル毎に同一である。これは、所定のノードＩＤに対してビットベクトルページのページ指標が単純なビットシフトにより計算されることを意味する。ノードの情報は、ノードＩＤで連続して格納される。
【０５０７】
所定のノードに対するページオフセットの検索
ページ毎の平均バイト数は、副ファイル毎に副ファイルのヘッダに格納される。これは、ページ指標を平均サイズと乗算することによりページのバイトオフセットを近似するために使用される。修正項は、ページ指標により指標をつけられたテーブルに格納される。このテーブルは、副ファイルの別個のセクションに格納される。ページがクエリされると、修正項は、テーブルでルックアップされ且つ近似ページオフセットに加算され、それにより副ファイルにおけるページの位置が与えられる。
【０５０８】
ページの復号化
キャッシュ
ページが初めてクエリされる場合、ページのノードに対するビットベクトル列は復号化され（固定の目標領域集合に関して）且つキャッシュされる。次に同一ページのノードに対してデータがクエリされると、キャッシュされたデータはいずれの副ファイルにもアクセスせずに使用される。復号化されたビットベクトルのビット列の特別なマーカビットは、ノードが非情報ノードであるかを記憶するために使用される。
【０５０９】
ページ符号
いわゆるページ符号ビットは、ページの全てのノードが同一の領域ＩＤを有するかをページ毎に指定する。ページ符号はレベル毎に１ビットを含むが、全てのビットは、レベル０の副ファイルのページ開始時にのみ共通のハフマンシンボルとして格納される。
【０５１０】
退出道路セグメント数の復号化
上述したように、各ページは固定のノード数に対する情報を含む。このノード数は、各副ファイルのヘッダに格納される。ページの開始時（又はレベル０の場合はページ符号の後）、ページはページの各ノードに対する退出道路セグメント数を一覧表示する。退出道路セグメント数が０である場合は常に、これは対応するノードに対して情報が全く格納されていないことを意味する。ページが復号化される間、数字は一次配列に格納される。
【０５１１】
領域の復号化
道路セグメント数セクションの後、領域セクションが続く。ノードの領域は、レベル毎に１つである領域ＩＤのシーケンスにより与えられる。特定のレベルの領域ＩＤは、対応する副ファイルに格納される。復号器は、ページの全てのノードに対して全てのレベルの領域を読み出す。ノードに対して情報が格納されていない場合（すなわち、ノードの道路セグメント数が０である場合）、領域情報は空のままである。復号器は、０より大きい道路セグメント数を有する第１のノードに対する領域ＩＤシーケンスを読み出す。全ての領域ＩＤが所定のレベルで同一であるとそのレベルのページ符号が指定する場合、そのレベルにおいて、同一の領域ＩＤが全てのノードに対して設定される。指定しない場合、対応するレベルの領域ＩＤが正の道路セグメント数の全てのノードに対して読み出される。この処理の終了時、復号器はページの全てのノードに対する完全な領域ＩＤシーケンスでテーブルを埋めている（いくつかのシーケンスは空であってもよい）。
【０５１２】
ビットベクトルの復号化
関連するビット位置の集合の検索
所定のノード及び目標領域に対して、特定のレベルの特定のビットは、そのノードを出る道路セグメントに対するビットベクトルのビットの値を判定する。２つ以上の目標領域がある場合、結果として得られるビットの論理和がとられる。ノード毎に、復号器は関連するビット位置の集合を計算する。関連するビット位置の集合は、そのノードの退出道路セグメント毎に同一である。これは、ノードの領域及び目標領域の集合にのみ依存する。目標領域が１つだけ存在する場合、１つのレベルにおいて関連するビット位置は１つだけ存在する。換言すると、他のレベルで格納された情報は、このノードに関しては無視される。２つ以上の目標領域がある場合、関連するビット位置の一部は一致するため、最大で存在する目標領域と同数の関連するビット位置が常に存在する。以下において、復号器が１つの目標領域に対する関連するビット位置を判定する方法について説明する。２つ以上の目標領域がある場合、関連するビット位置は、同様に見つけられ、１つの集合に組み合わされる。
【０５１３】
近傍領域が規定されない場合、各レベルの目標領域毎にビットベクトルのビットが１つ存在する（退出道路セグメント毎に）。（簡潔にするために、ノード自体の領域ＩＤに対してビットが格納されないということを無視する。）関連するビットは第１のレベルにあり、ノードの領域ＩＤが目標領域の領域ＩＤと異なるレベル０からカウントアップする。例えばグローバルレベルのノードの領域ＩＤがグローバルの目標領域ＩＤと等しいが、２つの領域ＩＤがレベル１で異なる場合、関連するビット位置はレベル１にあり、目標領域ＩＤと等しい。これは、そのレベルの非圧縮ビットベクトル列のビット位置である。この列は、可能な目標領域ＩＤ毎に１ビットを含む。領域再マッピングテーブルは、この位置を実際にはそのレベルで符号化される圧縮ビットベクトル列の位置に変換するために使用される。
【０５１４】
近傍領域が規定される（すなわち、可視エリア内の領域）場合、関連するビットは、目標領域がノードの領域の近傍にある「最も精細な」レベルで判定される。４つのレベルを一例として利用して、目標領域ＩＤシーケンスを（ａ，ｂ，ｃ，ｄ）とし、ノードの領域ＩＤシーケンスを（ｅ，ｆ，ｇ，ｈ）とする。近傍リストセクションで規定されるように（ａ，ｂ，ｃ，ｄ）が（ｅ，ｆ，ｇ）の近傍にあり、（ａ，ｂ）が（ｅ）の近傍にある場合、関連するビットは（ａ，ｂ，ｃ，ｄ）により判定され且つレベル２で配置され、接頭辞（ｅ，ｆ，ｇ）のレベルは近傍にあるものとして（ａ，ｂ，ｃ，ｄ）を含む。より詳細には、関連するビット位置はレベル２の副ファイルにおける領域（ｅ，ｆ，ｇ）の近傍の（ａ，ｂ，ｃ，ｄ）の指標である。前の段落で説明したように、領域ＩＤ  ｈに対する正規のビットはこの場合は関連がない。ここでも、この関連するビット位置は、非圧縮ビットベクトル列に対するものである。復号器は、領域再マッピングテーブルを使用して、それをレベル２の圧縮ビット列のビット位置に変換する。近傍リストに関するより多くの情報は、文献「Ｐｒｏｐｏｓａｌ  ｆｏｒ  ｅｎｈａｎｃｅｄ  ｍｕｌｔｉ−ｌｅｖｅｌ  ｇｒａｐｈ  ｐａｒｔｉｔｉｏｎｉｎｇ」に含まれる。
【０５１５】
ビットベクトルのビットの復号化
固定の目標領域の集合を仮定すると、ページの各ノードのビットベクトルは退出道路セグメント毎に１ビットから成る。ノードの道路セグメント数が０である場合（すなわち、ノードが非情報ノードである場合）、各ビットは、そのノードに対して更に復号化を行わずに１に設定される。ノードが目標領域の１つに配置される場合、ここでもビットベクトルは全て１である。この場合、符号化データは、後続するノードに対するデータを復号化するためにスキップされる必要がある。
【０５１６】
現在のノードに対するビットベクトルが単純に全て１でない場合、上述したように、復号器は関連するビット位置の集合を判定する。各ビット位置は、特定のレベルに対するものである。すなわち、ビットは特定の副ファイルに配置される。各レベルにおいて、副ファイルは完全な圧縮ビット列を含むが、復号器は関連するビット位置においてのみビットを抽出する必要がある。復号化中、実際に必要な情報が後続する時のみ、未使用の情報は読み出される（スキップされる）。そうでない場合、ビットストリームの未使用部分は全く読み出されない。
【０５１７】
関連するビット位置の集合は、レベルに従ってグループ化される。圧縮ビット列を復号化し且つ関連する位置でビットを読み出すためにそれを伸張する代わりに、関連する位置は圧縮ビット列の位置に変換される。あるレベルにおいて関連するビットが存在する場合、最初に、先行ノードに対するデータが適宜スキップされる（復号器は、それがどの程度遠くから来たものかを各レベルの副ファイルに記憶する）。所定の副ファイルにおいて当該ノードに対するセクションに到達すると、ビットベクトルは線毎に復号化される。退出道路セグメント毎に１ビットが格納される。これは、全ての関連するビット位置に対する復号化ビットの論理和演算の結果である。現在のノードの特定の道路セグメントに対する情報は、復号化方法を指定するハフマンシンボルから開始する。これは以下の値のうちの１つを有する。
【０５１８】
・このレベルにおける道路セグメントに対する全てのビットベクトルのビットが０であることを指定するシンボル（このレベルにおける全ての近傍ビットを含む）。この道路セグメントに対して、これ以上ビットが復号化される必要はない。
【０５１９】
・このレベルにおける道路セグメントに対する全てのビットベクトルのビットが１であることを指定するシンボル（このレベルにおける全ての近傍ビットを含む）。この道路セグメントに対して、これ以上ビットが復号化される必要はない。
【０５２０】
・ビットベクトルのビット列がブロックにより明示的に与えられることを指定するシンボル。ブロックによる圧縮ビットベクトルのビット列の復号化については以下に説明する。道路セグメントに対するビットベクトルのビットは、ページ全体の符号化中に構築される「履歴トラック」に入れられる。
【０５２１】
・履歴トラックへの指標を指定するシンボル。所定の指標において、履歴トラックは道路セグメントに対する所望のビットベクトルのビット値を含む。
【０５２２】
履歴トラックの現在のサイズに依存して、復号化方法セレクタのための異なるハフマン木が使用される。ハフマン木の数を指定する限界値が副ファイルのヘッダにある。履歴トラックのサイズがこの値を越える場合、最後のハフマン木が再利用される。
【０５２３】
ビットベクトル列が明示的に符号化されるべきであることを方法セレクタシンボルが指定する場合、復号器は圧縮ビットベクトルのビット列をブロック毎に読み出す。これは、このレベルにおける関連するビット位置（圧縮ビットベクトル列に対する）のビット値を収集する。ビットの値の論理和がとられる。論理和の中間結果が１になるとすぐに、この道路セグメントに対する全ての更なるブロックの残りのビットがスキップされる。各ブロックを復号化するために使用されるハフマン木はブロック中のビット数に依存する。副ファイルヘッダで指定されるように、正規のブロックの長さに対して１つのハフマン木が存在する。道路セグメントに対する最後のブロックはより短くてもよい。そのサイズに依存して、復号化のために適切なハフマン木が使用される。長さ１のブロックは１ビットであり、ハフマン復号化を使用せずに直接読み出される。
【０５２４】
ブロック数が少なくとも２である場合、ビットベクトルから生成されたビットストリームはブロックに対するハフマンシンボルの前に追加のビットを含む。その値は、復号化列全体が実際の値のビット毎の否定となると理解されるかを指定する。（この否定の目的はより適切なハフマン圧縮である。）
【図１】
0006030544.tif 000016
【図２】
0006030544.tif 000017
【図３ａ】
0006030544.tif 000018
【図３ｂ】
0006030544.tif 000019
【図４】
0006030544.tif 000020
【図５】
0006030544.tif 000021
【図６】
0006030544.tif 000022
【図７】
0006030544.tif 000023
【図８】
0006030544.tif 000024
【図９】
0006030544.tif 000025
【図９ａ】
0006030544.tif 000026
【図１０】
0006030544.tif 000027
【図１０ａ】
0006030544.tif 000028
【図１１】
0006030544.tif 000029
【図１２】
0006030544.tif 000030
【図１３】
0006030544.tif 000031
【図１４】
0006030544.tif 000032
【図１５】
0006030544.tif 000033
【図１６ａ】
0006030544.tif 000034
【図１６ｂ】
0006030544.tif 000035
【図１７】
0006030544.tif 000036
【図１８】
0006030544.tif 000037
【図１９】
0006030544.tif 000038
【図２０】
0006030544.tif 000039
【図２１】
0006030544.tif 000040
【図２２】
0006030544.tif 000041
【図２３】
0006030544.tif 000042
【図２４】
0006030544.tif 000043
【図２５】
0006030544.tif 000044
【図２６】
0006030544.tif 000045
【図２７】
0006030544.tif 000046
【図２８】
0006030544.tif 000047
【図２９】
0006030544.tif 000048
【図３０】
0006030544.tif 000049
【図３１】
0006030544.tif 000050
【図３２】
0006030544.tif 000051