"複数のナビゲート可能パスを含み、かつ、複数の領域に分割された地図データを使用して経路を決定する方法であって、少なくとも1つの処理装置を使用して、前記地図データ上の出発地及び目的地と、複数のコスト関数のうちの1つを選択する選択情報とを受信するステップと、前記地図データの領域間の最低コストのパスを特定する最低コストデータ及び前記地図データを使用して前記出発地から前記目的地までの経路を決定するステップとを実行し、前記最低コストデータは、前記複数のコスト関数のうちの種々のコスト関数に対して一対の領域の間に種々の最低コストパスが存在する場合に一対の領域の間の2つ以上の最低コストパスを特定し、前記経路を決定する前記ステップは、前記出発地及び前記目的地を含む一対の領域に対する最低コストパスから、前記選択されたコスト関数に対して最低コストを有する最低コストパスを特定することを特徴とする方法。前記決定された経路をディスプレイに表示させるステップと、前記ディスプレイの画像を見ながら、前記ユーザが前記選択されたコスト関数を変更することを可能にするステップと、新たに選択されたコスト関数に対して決定された新たな経路の画像とともに前記ディスプレイの表示を更新するステップとをさらに含むことを特徴とする請求項1に記載の方法。処理装置が請求項1又は2に記載の方法を実行するように、該処理装置によって実行される命令を格納した記憶媒体。複数の領域に分割される地図データであって、複数のナビゲート可能なパスと、種々のコスト関数に対して該地図データの複数の領域間の最低コストパスを特定する最低コストデータとを含む前記地図データを格納した記憶媒体。コンピュータデバイスであって、複数の領域に分割される地図データであって、複数のナビゲート可能なパスと、該地図データの複数の領域間の最低コストパスを特定する最低コストデータとを含む前記地図データを格納したメモリと、前記地図データ上の出発地及び目的地と、複数のコスト関数のうちの1つを選択する選択情報とを受信し、前記地図データ及び前記最低コストデータを使用する前記出発地から前記目的地までの経路を決定するように構成された処理装置とを備え、前記最低コストデータは、前記複数のコスト関数のうち種々のコスト関数に対して一対の領域の間に種々の最低コストパスが存在する場合に一対の領域の間の2つ以上の最低コストパスを特定し、前記経路の決定は、前記出発地及び前記目的地を含む領域の組み合わせにおける最低コストパスから経路を特定し、前記最低コストパスは、前記選択されたコスト関数における最低コストを有することを特徴とするコンピュータデバイス。測位システムと、ディスプレイと、ユーザインタフェースと、請求項5に記載のコンピュータデバイスとを備え、処理装置が、前記ユーザインタフェースにおける入力を介して前記出発地及び前記目的地を導出し、かつ、判定の結果をディスプレイに表示するように構成されることを特徴とするナビゲーション装置。前記ディスプレイは、前記決定した経路の画像を表示するように構成され、前記ユーザインタフェースは、前記ディスプレイの画像を見ながら、前記ユーザが前記選択されたコスト関数を変更することを可能にし、前記ディスプレイは、前記選択されたコスト関数の変更に応じて、新たに選択されたコスト関数に対して決定された新たな経路の画像とともに表示を更新することを特徴とする請求項6に記載のナビゲーション装置。電子地図によってカバーされる領域のナビゲート可能な経路のセグメントを表す複数のベクトルを含む該電子地図にわたり出発地から目的地までの経路を生成する方法であって、以前に電子地図の一部ではなかったベクトルを表すデータを含む電子地図に対して、訂正を提供するデータを利用するステップと、修正された経路指定加速データを形成するために、新たなベクトルが最低コスト経路の一部であることを示すように、該最低コスト経路の一部である前記電子地図のベクトルを示す経路指定加速データを修正するステップと、前記修正された経路指定加速データを利用することを含む経路の生成であって、出発地と目的地との間の経路を生成するステップとを含むことを特徴とする方法。前記電子地図に対する前記訂正は、リモートサーバからダウンロードされることを特徴とする請求項8に記載の方法。コンピュータデバイスであって、電子地図によってカバーされる領域のナビゲート可能な経路のセグメントを表す複数のベクトルを含む該電子地図を格納したメモリと、以前に電子地図の一部ではなかったベクトルを表すデータを含む電子地図に対して、訂正を提供するデータを利用し、修正された経路指定加速データを形成するために、新たなベクトルが最低コスト経路の一部であることを示すように、該最低コスト経路の一部である前記電子地図のベクトルを示す経路指定加速データを修正し、前記修正された経路指定加速データを利用することを含む経路の生成であって、出発地と目的地との間の経路を生成するように構成された処理装置とを備えることを特徴とするコンピュータデバイス。測位システムと、ディスプレイと、ユーザインタフェースと、請求項10に記載のコンピュータデバイスとを備え、前記処理装置は、前記ユーザインタフェースにおける入力を介して前記電子地図に対する前記訂正を受信するように構成されることを特徴とするナビゲーション装置。以下の説明において、同一の図中符号は同様の部分を特定するために使用される。種々の実施形態の説明において、一連の19xxの図中符号を有する図19のフローチャートを参照する。図1は、連続した位置、速度、時間及びいくつかの例においては無数のユーザに対する方向情報を判定するために利用されてもよい衛星無線を使用したナビゲーションシステムである全地球測位システムGPSを概略的に示す。以前はNAVSTARとして既知であったGPSは、極めて正確な軌道で地球を周回する複数の衛星を含む。これらの正確な軌道に基づいて、GPS衛星は自身の場所をGPSデータとしていかなる数の受信ユニットにも中継できる。しかし、GLOSNASS、欧州のGalileo測位システム、COMPASS測位システム又はIRNSSIndianRegionalNavigationSatelliteSystem等の全地球測位システムが使用可能であることが理解されるだろう。特にGPSデータを受信できる装置がGPS衛星信号に対する無線周波数の走査を開始する場合、GPSシステムは実現される。GPS衛星から無線信号を受信すると、装置は、複数の異なる従来の方法のうちの1つを使用してその衛星の正確な場所を判定する。殆どの例において、装置は、少なくとも3つの異なる衛星信号を取得するまで信号の走査を継続する尚、位置を判定する標準的な方法ではないが、2つの信号だけでも他の三角測量技術を使用して位置を判定できる。幾何学的三角測量を実現すると、受信機は、3つの既知の位置を利用して、衛星に対する自身の2次元位置を判定する。これは、既知の方法で行われる。更に、第4の衛星信号を取得することにより、受信装置は、同一の幾何学計算によって既知の方法でその3次元位置を算出できる。位置及び速度データは、無数のユーザにより連続的にリアルタイムで更新可能である。図1に示すように、GPSシステム100は、地球104の周囲の軌道上にある複数の衛星102を含む。GPS受信機106は、多くの衛星102からスペクトル拡散GPS衛星データ信号108としてGPSデータを受信する。スペクトル拡散データ信号108は、各衛星102から連続的に送信され、送信された各スペクトル拡散データ信号108は、データストリームの発信元である特定の衛星102を特定する情報を含むデータストリームを含む。一般にGPS受信機106は、2次元位置を算出できるように少なくとも3つの衛星102からスペクトル拡散データ信号108を必要とする。第4のスペクトル拡散データ信号を受信することにより、GPS受信機106は既知の技術を使用して3次元位置を算出できる。従って、GPSシステムにより、GPS受信機106を有する装置のユーザは数メートル内で地球上の自身の位置を判定できる。この情報を使用するために、ユーザの位置を示すことを可能にする電子地図に依存することが一般的になっている。そのような地図は、TeleAtlashttp://www.teleatlas.com等のプロバイダにより例示される。そのような電子地図は、GPSシステム又は他の手段を使用してユーザの位置を示すことを可能にするだけでなく、ユーザが移動等経路指定の目的のための経路を計画することを可能にする。この経路計画を行うために、電子地図はナビゲーション装置により処理され、これは一般的な演算装置により提供されてもよい。ナビゲーション装置の特定の例は、ポータブルナビゲーション装置PNDと呼ぶ便利な衛星ナビゲーション装置衛星ナビゲーションを含む。しかし、本発明の教示はPNDに限定されず、一般に経路計画及びナビゲーション機能性を提供するために電子地図を処理するように構成されるいかなる種類の処理装置にも例外なく適用可能である。従って、本出願において、ナビゲーション装置は、PND、自動車等の乗り物、例えば経路計画及びナビゲーションソフトウェアを実行するポータブルパーソナルコンピュータPC、移動電話又はパーソナルデジタルアシスタントPDA又はサーバであるポータブル計算リソース、あるいはネットワークを介してそのような機能性を提供する他の演算装置として実装されるか否かにかかわらず、どんな種類の経路計画及びナビゲーション装置も含むことを意図するそれらに限定されない。PNDの形態のそのようなナビゲーション装置の一例を図3a及び図4aに示す。尚、ナビゲーション装置200のブロック図は、ナビゲーション装置の全ての構成要素を含んでいるわけではなく、多くの構成要素の例を示しているにすぎない。ナビゲーション装置200は筐体不図示内に配置される。ナビゲーション装置200は、例えば上述したプロセッサ202を含む処理回路網を含む。プロセッサ202は、入力装置204及び例えば表示画面206である表示装置に結合される。ここで、入力装置204は単数で示されるが、入力装置204がキーボード装置、音声入力装置、タッチパネル及び/又は情報を入力するのに利用される他のあらゆる既知の入力装置を含む任意の数の入力装置を表すことは、当業者には理解されるべきである。同様に、表示画面206は、例えば液晶ディスプレイLCD等のあらゆる種類の表示画面を含むことができる。ナビゲーション装置200において、プロセッサ202は、接続210を介して入力装置204に動作可能に接続されて入力装置204から入力情報を受信でき、各出力接続212を介して表示画面206及び出力装置208のうち少なくとも一方に動作可能に接続されて情報を出力する。ナビゲーション装置200は、例えば可聴出力装置例えば、スピーカである出力装置208を含んでもよい。出力装置208がナビゲーション装置200のユーザに対して可聴情報を生成できるため、入力装置204は入力音声コマンドを受信するためのマイク及びソフトウェアを含むことができると同様に理解されるべきである。また、ナビゲーション装置200は、例えばオーディオ入出力装置等のあらゆる追加の入力装置204及び/又はあらゆる追加の出力装置を更に含むことができる。プロセッサ202は、接続216を介してメモリ214に動作可能に接続され、更に接続220を介して入出力I/Oポート218に対して情報を送受信するように更に構成される。I/Oポート218は、ナビゲーション装置200の外部のI/O装置222に接続可能である。外部I/O装置222は、例えばイヤホン等の外部リスニングデバイスを含んでもよいがこれに限定されない。I/O装置222への接続は、イヤホン又はヘッドホンへの接続及び/又は例えば移動電話への接続のためのハンズフリー動作及び/又は音声起動動作を行うカーステレオユニット等の他のあらゆる外部装置への有線又は無線接続であってもよい。ここで、例えばナビゲーション装置200とインターネット又は他のあらゆるネットワークとの間のデータ接続を確立するため、並びに/あるいは例えばインターネット又は他の何らかのネットワークを介してサーバとの接続を確立するために移動電話接続が使用される。ナビゲーション装置200のメモリ214は、不揮発性メモリ例えば、プログラムコードを格納するの一部及び揮発性メモリ例えば、プログラムコードが実行された時にデータを格納するの一部を含む。ナビゲーション装置は、接続230を介してプロセッサ202と通信するポート228を更に含み、取外し可能なメモリカード一般に、カードと呼ばれるが装置200に追加されるのを可能にする。説明している実施形態において、ポートは、SDセキュアデジタルカードが追加されるのを可能にするように構成される。他の実施形態において、ポートは他の形態のメモリが接続されるのを可能にしてもよいコンパクトフラッシュ登録商標CFカード、MemoryStick登録商標、xDメモリカード、USBUniversalSerialBusフラッシュドライブ、MMCマルチメディアカード、SmartMedia登録商標カード又はマイクロドライブ等。図2は、接続226を介するプロセッサ202とアンテナ/受信機224との間の動作可能接続を示す。ここで、アンテナ/受信機224は、例えばGPSアンテナ/受信機であってもよいため、図1のGPS受信機106として機能する。図中符号224で指定されたアンテナ及び受信機は図示するために概略的に組み合わされるが、アンテナ及び受信機は別個に配置された構成要素であってもよく、アンテナは例えばGPSパッチアンテナ又はヘリカルアンテナであってもよいことが理解されるべきである。更に、図3及び図4のポータブル又はハンドヘルドナビゲーション装置200は、例えば自転車、オートバイ、自動車又は船等の乗り物に既知の方法で接続又はドッキングされる。そのようなナビゲーション装置200は、ポータブル又はハンドヘルドナビゲーションに使用するためにドッキングされた場所から取り外し可能である。実際には、他の実施形態において、装置200はユーザのナビゲーションを可能にするためにハンドヘルド装置となるように構成されてもよい。図3aを参照すると、ナビゲーション装置200は、内蔵された入力及び表示装置206並びに図3aの他の構成要素内部GPS受信機224、プロセッサ202、電源不図示、メモリシステム214等を含むがこれらに限定されないを含むユニットであってもよい。ナビゲーション装置200は、吸着カップ254を使用して車両のダッシュボード/窓等に固定されてもよいアーム252上に位置してもよい。このアーム252は、ナビゲーション装置200がドッキングされるドッキングステーションの一例である。ナビゲーション装置200は、例えばナビゲーション装置200をアーム252に嵌合接続することによりドッキングステーションのアーム252にドッキングされるか又は接続される。ナビゲーション装置200は、アーム252を中心に回転可能であってもよい。ナビゲーション装置200とドッキングステーションとの間の接続を解放するために、例えばナビゲーション装置200上のボタン不図示が押下されてもよい。ドッキングステーションに対してナビゲーション装置200を結合及び分離する同様に適切な他の構成は当業者には既知である。図3bを参照すると、プロセッサ202及びメモリ214は協働して、ナビゲーション装置200の機能ハードウェア構成要素280と装置により実行されるソフトウェアとの間のインタフェースとして機能するBIOS基本入出力システム282をサポートする。プロセッサ202は、メモリ214からオペレーティングシステム284をロードし、アプリケーションソフトウェア286説明された経路計画及びナビゲーション機能性の一部又は全てを実現するが実行可能な環境を提供する。アプリケーションソフトウェア286は、例えば地図閲覧、経路計画、ナビゲーション機能及び関連する他のあらゆる機能であるナビゲーション装置の中核機能をサポートするグラフィカルユーザインタフェースGUIを含む動作環境を提供する。この点に関して、アプリケーションソフトウェア286の一部はビュー生成モジュール288を含む。説明している実施形態において、ナビゲーション装置のプロセッサ202は、アンテナ224により受信されたGPSデータを受信し且つGPSデータが受信された時のタイムスタンプと共にGPSデータを時々格納してナビゲーション装置の一連の位置を構築するようにプログラムされる。そのように格納された各データレコードはGPSフィックスと考えられてもよい。すなわち、ナビゲーション装置の場所のフィックスであり、緯度、経度、タイムスタンプ及び精度レポートを含む。この一連の位置は測位データと考えられてもよい。一実施形態において、データは、ほぼ周期的に、例えば5秒毎に格納される。他の周期も可能であり、データ解像度と記憶容量との間で均衡がとられることが当業者には理解されるだろう。すなわち、データの解像度がより多くのサンプルをとることにより向上されると、データを保持するのに必要なメモリはより多くなる。しかし、他の実施形態において、解像度は、ほぼ1秒毎、10秒毎、15秒毎、20秒毎、30秒毎、45秒毎、1分毎、2.5分毎又は実際にはそれらの周期の間のあらゆる周期であってもよい。従って、装置のメモリ内では、複数の時点における装置200の位置のレコードが構築される。いくつかの実施形態において、取り込まれたデータの品質は、周期が長くなるほど低下し、劣化の程度はナビゲーション装置200の移動していた速度に少なくとも部分的に依存するが、約15秒の周期が適切な上限を与える可能性があることが分かるだろう。更にプロセッサ202は、装置200の位置のレコードすなわち、GPSデータ及びタイムスタンプをサーバに対して時々アップロードするように構成される。ナビゲーション装置200が自身をサーバに接続する永続的な又は少なくとも一般的に存在する通信チャネルを有するいくつかの実施形態において、データのアップロードは、24時間に1回等の周期的に行われる。他の周期も可能であり、ほぼ15分毎、30分毎、1時間毎、2時間毎、5時間毎、12時間毎、2日毎、1週間毎又はそれらの期間の間のあらゆる時間のいずれであってもよいことが当業者には理解されるだろう。実際には、そのような実施形態において、プロセッサ202は、ほぼリアルタイムに位置のレコードをアップロードするように構成されてもよい。しかし、これは、データが実際には送信の間に相対的に短い周期で時々送信されることを必然的に意味するため、より正確には擬似リアルタイムであると考えられる。そのような擬似リアルタイムの実施形態において、ナビゲーション装置は、メモリ214内及び/又はポート228に挿入されたカードにGPSフィックスをバッファリングし且つ所定の数だけ格納された時にそれらを送信するように構成されてもよい。この所定の数は、20、36、100、200又はそれらの間のどのような数であってもよい。所定の数は、メモリ214/ポート228内のカードのサイズにより部分的に管理されることが当業者には理解されるだろう。一般的に存在する通信チャネルを有さない他の実施形態において、プロセッサは、通信チャネルが作成される時にレコードをサーバにアップロードするように構成されてもよい。例えばこれは、ナビゲーション装置200がユーザのコンピュータに接続される時であってもよい。ここでも、そのような実施形態において、ナビゲーション装置は、メモリ214内又はポート228に挿入されたカードにGPSフィックスをバッファリングするように構成されてもよい。メモリ214又はポート228に挿入されたカードがGPSフィックスで一杯になった場合、ナビゲーション装置は、最も古いGPSフィックスを削除するように構成されてもよいため、先入れ先出しFIFOバッファと考えられてもよい。説明している実施形態において、位置のレコードは、それぞれが24時間以内のナビゲーション装置200の動きを表す1つ以上のトレースを含む。24時間の各期間はカレンダーの日付と一致するように構成されるが、他の実施形態においては一致する必要はない。サーバ150は、装置の位置のレコードを受信し且つ処理するために大容量データ記憶装置内にそのレコードを格納するように構成される。従って、時間の経過と共に、大容量データ記憶装置はデータをアップロードした複数のナビゲーション装置200の位置のレコードを蓄積する。一般に、サーバは複数のナビゲーション装置200の位置を収集する。サーバは、各装置の収集した位置から速度データを生成するように構成されてもよい。この速度データは、地図のナビゲート可能セグメントに沿う平均速度が計時変化する様子を示す時間で変動する速度プロファイルを含んでもよい。図2は、説明している実施形態において、この例ではインターネットであるネットワークを介してナビゲーション装置において閲覧される電子地図の一例を示す。本明細書で説明している実施形態のいずれかにおける第1のステップは、そのような電子地図1900の生成である。地図は、http://routes.tomtom.com/Lid=1/map/center=55.012C-3.445zoom=4map=basicで閲覧されてもよい。図7の電子地図が行われる経路指定の目的で使用されるために、電子地図は一般に電子地図のユーザには見えない一連のノードを有する。従って、ノード等は一般に地図データと呼ばれてもよい。しかし、理解しやすいように、ノード300の一部が図6に示される。これらのノードは、交差点、道路の最終領域等に提供され、経路指定の目的で使用される。ユーザが自身のナビゲーション装置に2つ以上の地点間の経路を計画するように要求する場合、一般にナビゲーション装置は地図の関連するノード間の経路を計画するノードのグループまでの経路を計画することも可能であるが。従って、地図データは、ナビゲーション装置のユーザにより設定された少なくとも1つの基準に従って経路を生成するために使用される。電子地図は、道路セグメントの形状、建物への入り口の場所等を提供する更なるノードを更に含んでもよい。従って、各ノード300は、ユーザが移動してもよいそのノードから出る道路セグメントを少なくとも1つ、一般には複数有する。例えばノード302は、4つのそのような道路セグメント304a、304b、304c、304dを有する。他の実施形態において、ナビゲート可能セグメントは、歩道、自転車道路、運河、鉄道線路又は軌道等の道路ではないパスを参照するパスのセグメントを示してもよい。しかし、便宜上、道路セグメントを参照する。従って、図7に示すような地図は、それぞれが地図によってカバーされるエリアのナビゲート可能な経路の一部を表す複数の道路セグメントをユーザに対して示す。経路計画方法ダイクストラ法、A方法又はMoore/Pape方法は既知である。しかし、これらは、算出時間に関して非常に遅い。そのような経路計画の速度を向上する方法の一例は、米国特許第6,636,800号公報で示され、その教示は参考として本明細書に取り入れられている。本明細書で説明している実施形態は、前処理ステップにおいて、電子地図を処理する時に経路の生成を加速するためにナビゲーション装置によって使用される最低コストデータを含むいわゆる副ファイルを生成してもよい。この情報は、ビットベクトルと呼ばれてもよい2値データ、すなわち0及び1の列として保持されてもよい。従って、副ファイルは地図データと考えられてもよいが、電子地図例えば、図7に示すようなが供給されてもされなくてもよい。従って、本発明のいくつかの実施形態は、副ファイルから分離可能な地図として地図データを提供してもよいが、本発明の他の実施形態は、地図及び副ファイルデータを組み合わせてもよい。しかし、副ファイルが使用される場合、副ファイルが生成された電子地図と共に使用されるべきであることは、当業者には理解されるだろう。これが行われない場合、不正確な経路例えば、ユーザにより設定されたコスト関数を最小限にしない経路が取得されると考えられる。また、本発明の種々の実施形態は、最低コストデータ本実施形態においては、一連のビットベクトルであるの生成のための種々のパラメータを指定してもよい。従って、生成された地図データを使用する次の経路計画が最低コストデータを作成するのに使用されたパラメータとは異なるパラメータを使用する場合、最低コストデータはその経路計画に有用ではないと考えられる。例えばいくつかの実施形態は、自動車による地図上の移動に対して最低コストデータを生成してもよい。次の経路計画が徒歩のための経路を生成するために使用される場合、自動車用の最低コストデータは有用ではないと考えられる。別の例において、いくつかの実施形態は、ユーザが高速自動車道路、有料道路等を喜んで移動すると仮定して最低コストデータを生成してもよい。次の経路計画において、ユーザが高速自動車道路、有料道路等を利用しない経路を要求する場合、最低コストデータは有用ではないと考えられる。本発明のいくつかの実施形態は、それぞれが所定の基準の異なる集合を有する複数の最低コストデータの集合を生成してもよい。例えば本発明の実施形態は、2つ、3つ、4つ、5つ、6つ、10個、15個又はそれ以上の最低コストデータの集合のいずれを生成してもよい。従って、いくつかの実施形態において、副ファイルを生成するために、地図前処理ステップにおいてノードは複数の領域に分割されるため、あらゆる地図は既知の数の領域、例えばN個の領域に分割され、領域間の最低コストパスが判定される。この前処理は、経路計画方法の速度を向上するために地図と共に利用可能なデータを生成する。一般に前処理は、地図データがウェブサイト上で使用されるか又はPND等の装置上で使用されるかに関わらず、地図データが使用される前に実行される。従って、前処理ステップは、サーバ側処理と呼ばれることが多い。一般的なあらゆる演算装置が前処理を実行するのに適しているが、装置の性能が高い程、前処理は迅速に実行されることが当業者には理解されるだろう。一般に、X86アーキテクチャ演算装置が前処理に利用される。一般にそのようなX86アーキテクチャ装置は、Microsoft登録商標Windows登録商標、UNIX登録商標、LINUX登録商標、OSX登録商標等のオペレーティングシステムOSを実行する。しかし、他の実施形態はRISCアーキテクチャ等の他の演算プラットフォームを使用してもよい。また、他で説明するように、前処理は並列に実行されてもよいため、複数の演算装置又は少なくとも複数のプロセッサコア仮想又は実プロセッサコアであってもよいで実行されてもよい。次の前処理ステップとして、領域内の各道路セグメント例えば、304a~304dが処理され、それが地図内の領域数Nの各々までの最低コストパスの一部であるかを判定し、ビットベクトルが生成される最低コスト評価。従って、領域内の道路セグメント毎のビットベクトルは、領域内のナビゲート可能セグメント毎のビットを含む。すなわち、ビットベクトルは、経路がビットで表された領域までの最短経路の一部を形成するかに依存して0又は1に設定されるN-1ビット当該領域を除いた各領域に対して1ビットを含む。いくつかの実施形態は、ヘッダ及び可視エリア等の更なる情報を提供するために追加のビットを追加してもよい。これらの用語については以下に説明する。この意味で最低コストパスが複数の種々のコスト基準に対して判定されることは、当業者には理解されるだろう。例えば最低コストは、最短距離、最短移動時間、最安環境的な影響に関して、最小の使用燃料、最小の生成CO2等の基準のうちいずれかに対して判断されてもよい。本実施形態において、最低コストは最短移動時間に対して判断される。本発明の本実施形態において、最低コストパスは、複数のコスト基準コスト関数の各々に対して判定される。それに対応して、結果として得られる副ファイルは、いずれか1つの時間に適用可能な2つ以上の最低コストパスをいずれか2つの領域間で特定してもよい。各最低コストパスは、異なるコスト基準コスト関数に対するものである。例えば最速経路に対する最低コストパスは、最も燃料効率の良い経路に対する最低コストパスとは異なる可能性がある。従って、大きなエリアを範囲に含む地図の場合にNが大きい可能性が高いことは、当業者には理解されるだろう。そのため、前処理には多くの時間がかかる可能性がある。例えばヨーロッパ及びロシアを範囲に含む地図の一例において、一般に100,000,000個の道路セグメントを有する40,000,000個のノードが存在する。地図内に100個の領域が存在すると仮定すると、Nは100であり、100,000,000x100Nビットが存在する。すなわち、10x109ビットは地図の道路セグメント毎に99すなわち、N-1ビットを格納する必要がある。以下に説明する本発明の実施形態を使用すると、そのような地図は約500Mbの追加の記憶容量を使用してもよい。国際公開第WO2009/053410号は、時間の関数として地図のナビゲート可能セグメントに沿う速度を与える速度プロファイルを割り当てる方法を説明する。この出願の内容は、参考として本明細書に取り入れられている。従って、経路指定の目的で、あるナビゲート可能セグメントが別の領域までの最速経路の一部を構成するか否かは時間の関数として変動する。すなわち、例えばラッシュアワー等で、交通密度が増加するとナビゲート可能セグメントを使用するのが望ましくなくなり、交通密度が減少するとナビゲート可能セグメントを使用するのがより望ましくなる。いくつかの実施形態は、道路セグメント毎に複数のビットベクトルを格納してもよい。速度が記録される際の解像度が高い程、必要とされるビットベクトル数は増加することが当業者には理解されるだろう。しかし、他の実施形態は、国際公開第WO2009/053410号で説明するように時変関数を多く利用して最速経路の評価を行ってもよい。電子地図にわたる経路計画の時、約1/100秒の精度の時間粒度を使用してこれを行える必要があると考えられる。すなわち、最低コストの経路を正確に判定するために、0.01秒の精度でノードからの出発時間を指定できる必要があると考えられる。従って、このレベルの精度を考慮する場合、上記で考慮された地図に対して、40,000,000個のノード及び100,000,000個の道路セグメントを有することは100,000,0002個の可能な経路を有することが理解されるだろう。時間次元が更に考慮される場合、可能な経路の数は更に増加する。すなわち、7すなわち、1週間の日数x24すなわち、1日の時間数x3600すなわち、1時間の秒数x100すなわち、1秒間の100分のいくつかx100,000,0002=604,800,000,000,000,000,000,0001021個の可能な経路がある。現在の処理レベルで、各セグメントが各時間間隔で探索される単純な方法を使用すると、約19,178,082,191,780,821年かかるだろう。出願人が現在販売しているヨーロッパ西部及び中央の地図は120,000,000個の道路セグメントを有しており、年々さらに大きくなっている。従って、前処理段階でデータを格納及び処理するために多くのデータ量が必要とされることは理解されるだろう。本発明の実施形態は、前処理の量を非常に低減するために技術を使用する。これらの技術について次に更に詳細に説明する。本発明のいくつかの実施形態はそれら技術の全てを利用してもよいが、他の実施形態は一部のみを利用してもよい。本発明の種々の実施形態は、以下に概略を示す特徴の種々の組み合わせを使用してもよい。従って、いくつかの実施形態は、情報量を減少するために説明される技術の全てを利用してもよい。全く逆に、他の実施形態はデータを低減するためにそれら技術のいずれも利用しなくてもよい。本発明のいくつかの実施形態は、ステップ1902として示すように、所定の基準を満たさない道路セグメントに対するビットベクトルを算出しない。例えば、所定の種類の交通機関で道路セグメントを移動できない場合、道路セグメントは自身に対するビットベクトルを算出しなくてもよい。従って、交通機関のモードの基準が自動車に設定される一例において、以下の道路セグメントは自身に対するビットベクトルを算出しなくてもよい。鉄道線路道路セグメントに対応しない地図データに存在するセグメント間違った不法な方向の一方通行道路交通機関の形態によりナビゲート不可能な道路セグメント例えば、自動車による運転性を考慮した時、歩行用ゾーン、歩道非決定地点の道路セグメントすなわち、道路セグメントから方向転換できない。ネットワークの縮小1つの技術は、道路セグメントが最低コストの経路の一部を形成するかに関する評価に対して考慮されるネットワークのサイズを縮小することである。すなわち、ステップ1904で示すように、道路セグメント数を減少することにより算出を行うのにかかる時間が短縮される。この技術を図示するために、図7に示すような道路ネットワークを図6に示すが、図6では最低コスト評価に有用でない道路セグメントが削除されている。ネットワークの縮小の目的は、最低コスト評価が行われるべき最小のサブネットワークを提供することである。数学的には、残されたネットワークは、図7に示すように、図7の道路ネットワークの最大の強連結成分の無向表現の最大の2連結成分として記述される。コアネットワークは、右左折制限及びローカルアクセス等の道路交通規制に適応した双方の強い接続性2連結性としても既知であるに対して一般的な技術を適用することにより判定される。強い接続性は、2つのノード間で双方の方向に移動が可能であることすなわち、A->B及びB->Aを示すことが当業者には理解されるだろう。図5及び図7の双方を参照すると、袋小路250、冗長ループ252等の行き止まりの道が削除されていることが分かる。しかし、ノード例えば、図7の400は、除去された道路セグメントの出発地に残っていることが分かる。これは以下に説明する理由による。コアネットワーク例えば、図7に示すに縮小後、コアネットワークは、上述した領域を提供するようにセグメントされる。説明している実施形態において、ネットワークは、多方向の円弧状の区切り記号に従ってセグメントされる。そのようなネットワークにおいて、領域境界により二等分される道路セグメントすなわち、円弧が除去される場合、いずれか一方の領域に残っている道路セグメントは他方の領域に接続されないことが当業者には理解されるだろう。ネットワークのセグメント-ステップ1906しかし、セグメントの実行前に以下のステップが行われる。1.島が判定され、個々にセグメントされる。島は、フェリーリンク等の手段によりネットワーク及びリンクの他の部分から物理的に分離される傾向がある。これらは一般的な道路セグメントとは異なる挙動をしすなわち、平均速度が非常に遅い等、そのようなリンクがセグメントに含まれる場合、方法は実行されず、予想されてもよい。2.ネットワークにおいて2つ以上のノードで表される交差点、ロータリー及び他の分岐点は、同一の交差点等に属するノードが異なる領域で終了しないように短縮される。3.全てのナビゲート可能セグメントが同一のプロパティの集合例えば、フェリーセグメント、運転禁止セグメント、通り抜け禁止セグメント等を共有する単純なパスすなわち、方向転換の可能性のない2つのノード間の接続は、セグメントシステムに渡されるネットワークの入力サイズを縮小するために短縮される。例えば図6を見ると、ノード308は、道路310にまとめられてもよい。説明している本発明の実施形態は、http://labri.fr/perso/pelegrin/scotchで概略を示される分割統治法を採用する。そこで概略を示される方法は、地図のエリアに基づかず領域内に含まれたノード数に基づく多くの領域を含むように地図を分割する。そのように編成されるノードを有することは、同様のローカル探索の直径を有する領域を出力するのを助長するため、領域を使用する経路指定をより効率的にすることを助長できるという利点を有する。各ノードは、領域IDを含む関連付けられた特定番号を有するため、同一領域のノードは同一の領域ID番号を有する。ノードは、L個の階層レベルの領域に属する。レベル0は、慣例によって、最も粗なレベル長い距離の経路指定に使用されるである。レベルL-1は最も精細なレベルである。いずれか1つの領域内に含まれるノードの絶対数を設定するのではなく、ノードの最大数の上限を設定し、これを下回る自由度を可能にすることは便利である。例えば方法は、領域毎に最大100個のノードを指定してもよく、その結果、一般に60~100個のノードの領域毎のノードの広がりが得られる。設定されたノードの数が結果として不自然な形状の領域を与え、それら領域を使用する場合に次善の経路指定が得られるため、上限は設定された数より有利であると考えられる。複数レベル説明している実施形態において、複数のレベルのネストされた領域を提供するようにセグメントが行われる。これについては、図9に例示的に示す。最も粗なレベル0がレベル1を提供するように細分され、レベル1がレベル2に細分される階層性が存在することは図9から明らかである。各領域のノード数はレベル間で異なり、より粗なレベルより広い地理的エリアを範囲に含む傾向があるはより低いレベルより多くのノードを有する。従って、説明している実施形態におけるより粗なレベル例えば、レベル0は一般に長い範囲の経路指定の目的で使用され、より精細なレベル例えば、レベル2は短い範囲の経路指定に使用される。道路セグメント毎のビットベクトルの一部分はレベル毎にビットを含む。ビット数は、各レベルにおける領域数である。符号化するデータ量の概念を与えるために一般的な一実施形態において、一般にレベル数はL=3である、以下を示す。一般に、グローバルレベル=0は100個の領域を有する一般に、中間レベル=1はレベル0の領域毎に10個の領域を有するすなわち、100x10一般に、最も詳細なレベル=2は、レベル1の領域毎に5つの領域を有するすなわち、100x10x5階層レベルを使用することは、必要とされる処理量を可能性として非常に減少させるため有利である。説明している本実施形態において、100x10x5個の領域すなわち、5000個の領域である。従って、平坦な構造において、同数の領域を有することは5000個の領域を参照するために本明細書で概略を示された方法を必要とする。しかし、本明細書で説明される実施形態において、これは適切なレベルのノードを参照することにより減少される。一般に、種々の因子が地図に対して分かると、レベル数及びレベル毎の領域数は変更される。例えば、地図に割り当て可能な記憶容量及び経路指定が実行されるべき速度である。前処理量が増加すると、データを保持するために地図のサイズが大きくなるが、より速い経路はその地図を使用して算出されるという調和があることが当業者には理解されるだろう。一実施形態において、3つのレベルの領域が存在する。しかし、他の実施形態において、レベルがいくつ存在してもよい。例えば、1つ、2つ、4つ、5つ、6つ、7つ、8つ、9つ又は10個のレベルが存在してもよい。従って、上記例を使用して、一般に40,000,000個のノード及び100,000,000個の道路セグメントを有するヨーロッパの西部及び中央の地図において、最も単純な符号化は、各レベルの全てのノードの領域IDに対する固定サイズの符号化及び各レベルの各道路セグメントに対する固定サイズのビットベクトルarpフラグを使用する。従って、そのような基本的な符号化のサイズは以下のように容易に算出される。レベル0の各ノード領域IDはlog_2100ビット=7ビットを使用するレベル1の各ノード領域IDはlog_210ビット=4ビットを使用するレベル2の各ノード領域IDはlog_25ビット=3ビットを使用するレベル0の各ビットベクトルarpフラグは100ビット100個の領域-現在の領域である1つの領域を使用するレベル1の各ビットベクトルarpフラグは10ビット10個の領域-現在の領域である1つの領域を使用するレベル2の各ビットベクトルarpフラグは5ビット5個の領域-現在の領域である1つの領域を使用する図9は、最も粗なレベルの領域600を示す。図中、領域600は6つの領域1~6を提供する。これらの領域の各々は、領域600の粗なレベル内の破線により表されるように、更なる領域、本実施形態では9つのサブ領域に細分される。説明している実施形態において、破線で提供された各領域が更に細分される更なる細分のレベルが使用され、これにより3つのレベルのセグメントを提供するが、これについては参照を分かりやすくするため図9には示さない。当然、他の実施形態はより多くのレベル例えば、4つ、5つ、6つ、7つ又はそれ以上のレベル又はより少ないレベル例えば、1つ又は2つのレベルを使用してもよい。従って、本発明の実施形態は、ステップ1908において、より精細なレベルの領域に対していわゆる可視エリアを導入する。k領域の可視エリアは、k-1領域の集合であり、領域はフラグセットの自身のビットで区別可能である。当然、可視エリアは所定のk領域が属するk-1領域を常に含む。更に可視エリアは、近傍のk-1領域を含んでもよい。可視エリアは、前処理中に計算され、ビットベクトルと関連付けられて格納される。k領域とそれらのk-1レベルの可視エリアとの関係は反対側から見られる。各k-1領域は近傍にあるkレベルの領域から構成される限界を認識している。このように考えると、道路セグメントのフラグセットは地図全体にわたり固定長ではない。その代り、各1領域のビットベクトルは、特定の長さABCNoutskirts0Noutskirts1を有する。Aは最も粗なレベルの領域を示し、Bは中程度の粒度を示し、Cは最も精細な粒度の領域を示す3つのレベルが存在する一実施形態において。次の前処理は、ビットベクトルを生成するための最短パスの算出前に可視エリアを計算する。可視エリアを見つける方法は以下のように説明される。各k領域に関して、領域近傍グラフにおいて幅-第1探索を開始。その後、開始領域に十分に近接する訪問先k領域毎に、含んでいるk-1領域を可視エリアに追加する。密接度の関係は、地理的計測値例えば、領域中点間の距離及びグラフ理論距離を考慮に入れるべきである。従って、領域は、地理的に遠いが高速接続により現在の領域とリンクされる場合に近いだろう。同様に、領域は、地理的に近くても領域間を移動するのが困難である場合は遠いと考えられるだろう。厳密な閾値は、前処理の増加等の上述した悪影響を最も受けやすい首都圏の平均直径のような地図固有のプロパティに依存するため実験的調整を行われてもよい。非常に長い移動時間がかかるナビゲート可能セグメントフェリー又は運転禁止道路セグメント等は隣接グラフの横断中隠蔽される。このように、可視エリアは同一領域に属する小さな列島又は単独の島に常に制限される。従って、幅優先探索中に訪問される領域はRの近傍領域を構成する。近傍領域を完全に範囲に含む次に粗なレベルの領域の操作対象最小集合は、Rの可視エリアと呼ばれる。逆の関係は近傍と呼ばれる。領域QレベルLのの近傍リストは、可視エリアにQを有するレベルL1の全ての領域から成る。特定の例を与えるため、図6を参照すると、可視エリアの例は以下の通りである。各1領域とその可視エリアの境界との間の最短距離が少なくとも1であるべきであると判断した場合、いくつかの選択した1領域に対する可視エリアは以下の0領域自身の0領域は常に存在するため省略されるから成る。15:すなわち、その0レベル領域の中心であるため、レベル1領域no.15は可視エリアを示さない28:5すなわち、レベル1領域no.28は領域レベル0no.5である単一の可視エリアを含む37:2、5、6すなわち、レベル1領域no.37は3つの領域、すなわちレベル0領域no.2、5及び6を有する。レベル1領域のレベル0近傍領域を考慮することに加えて、レベル1近傍領域がレベル0領域毎に判定される。一例として以下を示す。1:21、24、27、28、41、42、43、51すなわち、レベル0領域no.1に対して、レベル1領域は21、24、27、41、42、43、51である従って、この例において、領域28が領域2の最も左側の列にないにも関わらず一覧表示されていることが分かる。例えばこれは、領域28が領域1への迅速なリンクを有しているために距離ではなく時間に関して考慮された時に近いからである。密接度は、環境性最少のCO2等等の他の計測値に対して判断されてもよい。近傍リストの符号化図9aは、図9と比較して採用されてもよいレベルの更なる詳細を示す。レベル0は、最も粗なレベルであり、レベルk-1と考えられてもよい。簡潔にするために、図6aにおいて、領域1~4のみが示されるすなわち、602、604、606、608。k-1領域の各々は、kレベル領域すなわちレベル1領域と呼ばれてもよい9つの領域1~9に更に分割される。また、これらのレベル1領域の各々は4つのk1レベル領域すなわち、レベル2領域に分割される。ビットベクトルの生成ネットワークが領域の3つのレベルにセグメントされると、ステップ1910において、それら領域の各々までの最低コストの経路を決定するために処理され、ビットベクトルは領域内の道路セグメント毎に作成される。従って、上述したように、いずれか1つの領域内の各道路セグメントは、他の各領域までの最低コストの経路の一部であるかを判定するためにコスト関数に関して解析される。ビットベクトルは、図7に示すように領域の全ての道路セグメントに対して生成される。図7は、理解しやすくするために簡素化されたビットベクトルを示す。最低コストの経路は、単一の期間で判定されるのではなく、以下に説明するように複数の期間に対して算出されることが理解されるべきである。この算出は、図7に示したネットワークすなわち、縮小されたネットワークに対して行われる。除去されたネットワークの部分は、出発地となるノードに効果的にまとめられる。例えば図5に示した領域250は、図7のノード400にまとめられる。各ビットベクトルは3列含むことが分かる。最も左側の列700は、考慮中の道路セグメントの開始のノードの特定番号を含む。第2の列702は、考慮中の道路セグメントの終了のノードの特定番号を含む。第3の列704はその道路セグメントのビットベクトルを含む。従って、各道路セグメントは、それぞれが道路セグメントの端部である2つのノードにより特定されることが分かるだろう。道路セグメントが最低コスト経路の一部であるかを判定するためにどのような適切な経路指定方法が使用されてもよい。特定の本実施形態において、既知のダイクストラ法がネットワーク全体を探索するために使用される。しかし、処理時間は種々の戦略を採用することにより短縮されてもよい。上述したネットワークを縮小する技術は、処理時間も短縮することが当業者には理解されるだろう。本発明の実施形態は、以下のうちいずれか1つ以上を採用してもよい。領域に対応する全てのビットベクトルエントリを1度に算出する。最短のパス木は、各境界ノードに対する逆グラフにおいて計算される。そのような方法は、各領域が並行に処理されることにより処理時間を短縮するため有利である。同様の最短のパス部分木の再計算を減少する。既に生成されたビットベクトルを再計算しない。従って、要約すると、一実施形態はビットベクトルを生成するために以下を実行してもよい。準備ステップ1.当業者には理解されるように、電子地図にわたる探索は有向非周期グラフDAGにより表される。このグラフ及び隣接するデータ構造方向転換コスト及び長い範囲テーブルが逆にされる。2.最も精細なレベルに対する単純な道路セグメントは短縮されるすなわち、他で説明するように、終端ノードは一方にまとめられる。道路セグメントは、所定のレベルの同一の領域にある程度=2の1つ以上のノードから構成される場合に単純であると言われ、ナビゲート可能セグメントは同一の属性を有する。例えば、フェリーである、NoThroughである及びNoDrivingであるである。3.道路ネットワークの道路セグメントは、領域毎に、先端すなわち、from_node及び/又は末端すなわち、to_nodeのノードがその領域に属するかに依存して、退出道路セグメント、進入道路セグメント及び内部道路セグメントの3つのグループにソートされる。すなわち、先端及び末端の双方が同一の領域内にある場合、道路セグメントは内部道路セグメントと呼ばれる。先端が領域内にあるが末端が領域内にない場合、道路セグメントは退出道路セグメントと呼ばれる。末端が領域内にあるが先端が領域内にない場合、道路セグメントは進入道路セグメントと呼ばれる。4.特別な右左折制限は、NoThrough及びNoDrivingエリアを出る全ての道路セグメントに設けられる。前処理ルーチンは、最も精細なセグメントレベル、すなわち説明している実施形態においてはレベル2から開始してボトムアップ方式で進む。領域の各レベルにおいて、以下のステップが領域R毎に繰り返される。1.Rの探索エリアを判定する。最上位レベル例えば、説明している実施形態においては領域0においてはグラフ全体であり、より精細なレベルにおいてはRの可視エリアにより制限された部分グラフである上述したように。従って、中間レベルすなわち、レベル1において、以下のステップはレベル1領域が含まれるレベル0領域の可視エリアに対してのみ実行される。レベル0において、長い範囲の経路指定に対して使用されることを注意すべきであり、グラフ全体の道路セグメントが考慮される。可視エリアの進入道路セグメント、すなわちエリア外のノードからエリア内に至る道路セグメントを収集する。その後、境界付近の道路セグメント、すなわち進入道路セグメントに続く道路セグメントを収集する。先端L1=末端L2でありL1からL2への方向転換が禁止されていない場合、道路セグメントL2はL1に続くと言われる且つL1はL2に先行する。複雑な交差点は、境界付近の道路セグメントを見つける目的で単一のノードに短縮される。フェリー道路セグメント及びNoDriving属性を有する道路セグメントは境界付近の道路セグメントと考えられない。このように進入道路セグメントを収集することにより、後述する探索ステップで必要とされる処理量を可能性として非常に減少できる。探索ステップは、進入経路を含む所定の領域までの経路を考慮するためにグラフの探索を減少できる。2.Rの退出道路セグメント毎に、ルート道路セグメント及び探索ステップ数を見つける。退出道路セグメントがR内にある先行道路セグメントの少なくとも1つの唯一の後続道路セグメントである場合、この退出道路セグメントは唯一のルート道路セグメントであり、単一の探索ステップが実行される。あるいは、退出道路セグメントが双方向である場合すなわち、双方向に運転可能である場合、道路セグメント自体及びその反対の進入道路セグメントは単一の探索ステップのルート道路セグメントとして利用される。あるいは、退出道路セグメントが一方向である場合、先行する各内部道路セグメント及び存在する場合はその反対の道路セグメントは別個の探索ステップのルート道路セグメントとして利用される。最後に、退出道路セグメントの種類に関係なく、退出道路セグメントを通る交通範囲パス毎に、範囲の開始道路セグメントR内にある場合は別個の探索ステップのルート道路セグメントとして利用される。より精細なレベルすなわち、レベル0以外の全てのレベルにおいて、退出フェリー道路セグメントは特別に処理される。上述したように、フェリー道路セグメントは、領域の近傍領域を判定する時に無視される。フェリー道路セグメントの先端領域がRの可視エリアに属さない場合、フェリー道路セグメントが唯一のルート道路セグメントであり且つ探索エリアが先端領域自体に制限された状態で単一の探索ステップが実行される。3.スケジュールされた探索ステップを実行する以下に説明する。4.探索エリア内の道路セグメントからルート道路セグメントまでの最短パスを辿る。最上位すなわち、レベル0以外の全てのレベルにおいて、辿ることを開始する道路セグメントの順序は結果に影響を及ぼす。RがレベルL領域L>0であるとすると、レベルL-1領域の退出道路セグメントは最初に処理され、その後、レベルLの残りの退出道路セグメント等、最も精細なレベルに向かって処理される。すなわち、最も精細なレベルに関して内部にあり且つまだ除去されていない道路セグメントが最後に処理される。先に辿った時に既に訪れた道路セグメントに遭遇した場合、2度目にそのパスに従う必要はない。辿っている間、適切な目標ビットベクトルが訪れた道路セグメント毎に設定される。最上位レベルすなわち、レベル0以外の全てのレベルにおいて、以下の追加の動作が行われる。パスがあるレベルL領域の境界を初めて横切った後、その境界道路セグメント及びルート道路セグメントまでの途中にある全ての更なる道路セグメントは通過線フラグにより印がつけられる。最短パスがUターンをするノードは、Uターンフラグで印がつけられる。最後に、最も精細なレベル以外の全てのレベルにおいて、相関行列エントリが満たされる。そのレベルの全ての領域が処理された後、グラフは次のレベルに対して簡素化される。最初に、通過線として印をつけられなかった全ての道路セグメントが除去される。その後、増加する新しい単純なパスは短縮される。Uターンノードとして印をつけられたノードは保存される。最後に、ビットベクトルは、相関行列に従って、このレベルを処理する前に除去された道路セグメントに伝播される。相関行列本発明のいくつかの実施形態は、道路セグメント上にビットベクトルを設定するのに必要な目標領域の間の関係を格納する相関行列を使用する。最も精細なレベル以外の各レベルLにおいて、新しい相関行列が作成され且つ使用される。レベルLにおいて、行列の行は、レベルL1領域により指標をつけられ、列はレベルL領域により指標をつけられ、各行列エントリは0個以上のレベルL1領域の集合である。より低いレベルにおいて、殆どの行列エントリが空の集合と等しい。すなわち、行列は疎である。相関行列の目的は、早い段階で削除された道路セグメントにビットベクトルを設定することを助長することである。これらの道路セグメントは、レベルLの探索ステップの結果として得られた有向非周期グラフに含まれないが、削除されなかった場合は含まれる。より詳細には、相関行列は、あるレベル>Lの算出中に削除されたSの探索エリアの道路セグメントのあるレベルL領域SLは最も精細なレベルではないにビットベクトルを設定するために使用される。Sの探索エリアに含まれたレベルL1領域Rの場合、行列成分M[R,S]は、SからRまでの全ての最短パス逆グラフにおけるが1つの領域を通過するように、最終的にRの可視エリアの境界にあるレベルL1領域の集合となる。行列が作成される場合、全てのエントリは空の集合に初期化される。その後、全てのレベルL領域Sに対して、以下の2つの動作が行われる。1.行列の構築:Sのルート道路セグメントl及び結果として得られる有向非周期グラフDを使用する各探索ステップに対して、Sの探索エリアに含まれた各レベルL1領域Rに対して、並びにRの各進入道路セグメントl’に対して、行列成分M[R,S]が以下のように更新される。Rの探索領域をAで示すレベルL1に対して早い段階で算出されたように。l’からlまでのDにおけるパスを辿り、Aを出たかを検査する。すなわち、Tが依然としてAに含まれるがT’は含まれない状態で、このパス上の道路セグメントがレベルL1領域TからレベルL1領域T’まで通っている場合、Tは集合M[R,S]に追加され、次のl’が処理される。2.行列を読み出す:レベルL算出が開始する前に削除されたSの探索エリアの各道路セグメントに対して、Rを道路セグメントが終了するここでも、逆グラフに対してレベルL1領域とする。ここで、その線上の領域Sに対するビットベクトルのビットは領域Tのビットベクトルの論理和に設定される。尚、TはM[R,S]の全ての要素に及ぶ。尚、T毎のビットベクトルのビットは、ある有向非周期グラフから直接又はより低いあるレベルにおいて相関行列を含む同様の手順で、より早いレベルで設定される。探索探索ステップは、所定の道路セグメント対を根とする最低コストパスの有向非周期グラフを構築することから成る。これは、最低コストパスの計算に対して既知のダイクストラ法の一変形例を使用することにより達成される。実際には、最小にされる目的関数が、例えば移動時間又は推定された燃料消費又は他で説明される他の因子のいずれかとして自由に選択される。一実施形態は、移動時間、パスの長さ、並びに望ましくない方向転換及び操作を抑制する他のペナルティ条件の加重和を使用する。以下の変形が従来のダイクストラ方法に行われる。1.道路セグメントグラフに対して動作する。すなわち、訪れた項目、緩和された項目等がノードではなく道路セグメントである。これは、方法が右左折制限及び/又は交通範囲を考慮することを可能にするのに有用である。2.ラベルの目的関数は、ルート道路セグメントにおける到着タイムスロットの固定の集合に対する対移動時間、コストのベクトルである。タイムスロットは、全ての関連交通モードが範囲に含まれるように自由流れ、平日の朝のラッシュアワー、夕方のラッシュアワー等選択される。これについては、複数の期間におけるコストの評価に関する説明において以下に更に詳述する。3.2つ以上のラベルが所定の道路セグメントに対して格納される。2つのラベルにおける保留中未完了の交通範囲の集合が等しくない場合、ラベル自体は独立していると言われ、後続する道路セグメントにわたり伝播し続ける。あるいは、種々の到着タイムスロットに対するコスト関数値の間の関係は交互にならない。すなわち、一方のラベルが他方のラベルより良いのは明確であり、悪い方のラベルは廃棄される。そうでなければ、新しいラベルがタイムスロット毎の良い方の値をマージすることにより作成され、これは元のラベルの代わりに伝播される。先行するマージされたラベルの集合は、先行する元のラベルの集合の結合である。4.特別なUターンラベルは、双方向の各道路セグメントにおいて作成される。それらラベルは、双方向の実際の逆にされていない経路を開始する可能性を符号化する。Uターンラベルは伝播されず、通常のラベルとマージされなくてもよい。しかし、それらラベルは、ビットベクトルが設定される時に追跡段階に影響を及ぼす。すなわち、開始ラベルが同一道路セグメント上のUターンラベルより悪くない場合のみ、最短パスはフラグを立てられる。5.探索エリアが領域の集合に制限されるより精細なレベルにおいて、上記で規定したような境界付近の道路セグメントは永続的に監視される。全ての境界付近道路セグメントに探索面が到達するとすぐに、監視コームはタイムスロット毎の最大=最悪のコスト関数値から構築される。その後、コスト関数値が少なくとも1つのタイムスロットにおいて現在の監視コームを下回る場合にのみ、探索エリア外の道路セグメントのラベルはヒープを出た時に伝播される。探索エリアがいくつかの島に及ぶ場合、別個の監視コームが島毎に維持される。時変関数本発明のいくつかの実施形態は、単一の時間ではなく複数の期間においてネットワークにわたる最低コストの経路を示すビットベクトルを算出してもよい。道路ネットワークにわたる最低コストの経路は、交通密度の影響等により計時変化する可能性があることが当業者には理解されるだろう。従って、あらゆる1つのノードに対して、それぞれが種々の時間に対するものである2つ以上の最低コストパスが存在してもよい。本実施形態において、ビットベクトルは、最低コストパスが適用可能である場合に対して時間参照により符号化されない。ビットベクトルは、最低コストパスの一部であるとして又は一部でないとしてナビゲート可能セグメントを特定するために単純に設定される。従って、最低コストデータを使用して経路指定する場合、経路指定アルゴリズムはノードからの可能な全ての最低コストパスを考慮する必要がある。この処理については、図10aを使用して次に簡単に説明する。ネットワークの一般的なダイクストラ探索において、ネットワークが探索されると、方法はネットワークのその地点に到達するために現在までに発生した合計コストまだ発生していない予想されるコストを使用する。従って、いくつかの実施形態は、各ノードにおいてコスト評価を行うために別個の値とは対照的に関数を利用する。図10aにおいて、探索されているグラフ751の各ノード例えば、750はコスト関数と関連付けられ、これは、探索されているパラメータ例えば、時間又は消費燃料等が計時変化する様子を特定する。コスト関数は、ノードとは対照的に道路セグメントと関連付けられてもよい。方法は費やしたコストを処理し、新しい関数を生成するために現在までに蓄積したコストを有する現在のノードにおいて関数を合計することにより推定されたコストを加算する。図7aの752で示した例は、探索方法によりノード750で生成されたコスト関数を示し、移動時間y軸が出発時間x軸に伴って変化する様子を示す。朝及び夕方のラッシュアワーのために移動時間がポイント754及び756において増加していることが分かる。特定の一実施形態において、コスト関数例えば、道路セグメントの平均速度は5分間隔で格納される。すなわち、これは5分間に変化し続ける関数ではなく量子化関数である。道路セグメントに対するビットベクトルは、その道路セグメントがどの期間においてもどのコスト関数に対しても最低コスト経路最低コストパスの一部である場合に設定される。完全なネットワークへのコアデータの投影セグメント方法により考慮される必要があるノード及び道路セグメントの数を減少するために地図に含まれたネットワークを縮小する方法について上述した。しかし、経路指定方法が削除された道路セグメント及びノードに対する経路を依然として生成できるようにするためには、縮小ステップで削除されたノードも更に考慮されるべきである。従って、削除されたノード及び道路セグメントは、それらがコアネットワークにおいて接続されるノードと同一の領域に割り当てられる。圧縮上述したように、生成されたビットベクトルはサイズが大きいため、情報を圧縮するのが望ましい。本発明の実施形態は、これを種々の方法で実行してもよい。しかし、一実施形態は、ビットベクトルを圧縮、結合及び/又は相関し、その後ビットベクトルのハフマン符号化を行う種々の技術を利用する。いくつかの実施形態は、ビットベクトルの不均一な分布があることを保証しようとしてもよい。これは、そのような分布がない場合よりハフマン符号化が効率的であることを保証するのを助長できるからである。例えばビットベクトルが以下のように分布される場合、0000....時間の491111....時間の49....時間の2以下のようなより不均一な分布を有するようにハフマン符号化前のビットベクトルを操作するのが望ましい。0000....時間の791111....時間の19....時間の2。生成されたビットベクトルの縮小生成される必要があるビットベクトルの量を減少するために、本発明の実施形態は、以下の戦略のうちいずれか1つ以上を使用してもよい。領域IDは、全てのノードに対して使用されるわけではなく、ナビゲート可能ノードに対してのみ生成される例えば、鉄道線路に対応するノードは無視される。ビットベクトルは、全ての道路セグメントに対して必要とされるわけではなく、決定ノードの周囲の決定道路セグメントに対して使用されてもよい。決定ノード決定道路セグメントは道路セグメントデータを見ることにより判定される本明細書で説明されるように。可能なビットベクトルが多く存在するが、その一部はその他のビットベクトルよりはるかに頻繁に発生するため、特定の符号化は最も頻度の高いビットベクトル例えば、000...000及び111...111に対して使用される。多くの場合、000...000でも111...111でもないビットベクトルは、それらの殆どのビットが1に設定されているか又は0に設定されている。従って、部分ブロックのハフマン符号は、それらを非常に効率的に符号化すべきである。ビットベクトルは、多くの場合に互いに近接するノードにおいて同一であるため、デルタ符号化がそれらを効率的に符号化できる。種々の領域は、ソース領域毎に行先領域IDを再順序付けすることにより、より類似するビットベクトルパターンを有するようにされてもよい概念は本明細書において説明する。ノードの道路セグメントの周囲の全てのビットベクトルは、常に111...111を与えるべきである。これはビットベクトルを更に効率的に符号化するために適切に使用される。これらのうちの一部について、以下に更に詳細に説明する。尚、この時点では、本明細書で説明される技術の目的はビットベクトルのサイズを縮小することである。しかし、経路指定の目的で地図データを使用する装置によりデータへのランダムアクセスが必要とされる。しかし、一般に、データの効率的な符号化にはデータへのランダムアクセスを防止する可変サイズが必要とされる。従って、本発明の実施形態は、データが指標をつけられる一連のページとして符号化され且つそれらのページ内で可変符号化を利用するというトレードオフの関係を使用してもよい。そのような実施形態において、ランダムアクセスは各ページに対して達成可能である指標をつけることにより。ページがアクセスされると、実施形態はページ全体を復号化してもよい。これにより、効率と地図のサイズとの間にはトレードオフの関係が提供される。ページ毎のノード数を増加すると地図のサイズは減少するが、データアクセスは遅くなる。本発明の特定の一実施形態は、ページ毎に16個のノードを使用する。いずれか1つのノードは、そのノードを出る異なる数の道路セグメントを有してもよいことが理解されるだろう。従って、同数のノードが存在してもよいが、ページ毎の道路セグメントの量は可変であってもよい。更に、各ページに格納されたビットベクトルの各々に対して異なる圧縮が適切に行われてもよい。そのような構造により、図11に示す地図形式が得られる。この図において、Arpフラグへの参照は、ビットベクトルと同様である。数字nは、ヘッダ内に格納され、その地図に対して性能を最適化するために種々の地図に対して変更されてもよい。nを調整することは、地図データを復号化する時のアクセス速度と地図のサイズにはトレードオフの関係がある。大きな値のnは多くのノードをグループ化する。これは、地図の圧縮には適切であるが、データへのランダムアクセスの速度には不適切である。小さな値のnは殆どのノードをグループ化しない。これは、データのランダムアクセスの速度には適切であるが、地図の圧縮には不適切である。nは例えば4に設定されてもよい。すなわち、16個の出発ノード出発ノードは道路セグメントの開始点あり、すなわち図10の列700であるから成るページであるが、各出発ノードはいくつかの到着道路セグメントを有する。平均で3つの到着道路セグメントを有すると仮定すると、各ページが~48個の道路セグメントを格納することを意味する。この形式において、符号化される領域のレベルに依存してデータに対する異なる形式が存在する。図12は、レベル0すなわち、最も粗な領域に対する形式の一例を示し、図12は、領域の他のレベルに対する形式の一例を示す。ビットベクトル及び関連情報はデータ構造に格納され、その形式を図11に示す。図11は、ヘッダ800、後述するハフマン符号化で使用されるハフマン木802、各階層における領域数804レベル毎の領域数が一定の場合は空、近傍領域806近傍領域がない場合は空、領域ID再マッピングテーブル808、ビットベクトルページ指標2n個のノード810、並びに領域ID及びビットベクトル812を含む。ビットベクトルを保持するデータ構造は、単一のファイル内に保持されてもよく、あるいは複数のファイル内に保持されてもよい。いくつかの実施形態において、地図ヘッダ800は、以下を示す更なる情報を含むように構成される。レベルの最大数最短近傍リストの長さ最長近傍リストの長さ全ての近傍リストを含むセクションのバイトオフセット。情報を保持する各ファイルは、近傍リストを符号化するためにセクションを有してもよい。全てのリストのサイズがまず符号化される。リストの各長さは、最短リストの長さに対して、BitsRequiredlongestListLength-shortestListLengthにより判定された固定のビット数に符号化される。尚、全てのリストが同一の長さを有する場合、長さを符号化するのにビットは必要ない。その後、全てのリストの内容に従う。各リストは、近傍領域IDのいくつかのタプル、すなわちレベル0ではいくつかの対、レベル2では3つの要素のいくつかのタプルから成る。尚、出発領域タプルASCIIファイルの:の前の部分は符号化されない。これらは、リストが全ての領域に対して昇順に格納されるため黙示的である。例えば地図が100x10x5レベル0の100個の領域、レベル1の10個の領域、レベル2の5つの領域を有する3つのレベルを有する場合、以下の通りである。レベル0において、リストは出発領域1、2、3、...100この順序で100個のリストに対して格納される。これらリスト各々は対を含む。レベル1において、リストは出発領域1.1、1.2、1.3、...1.10、2.1、2.2、...2.10、3.1、...100.9、100.10この順序で1000個のリストに対して格納される。これらのリストの各々は、3つの要素のタプルを含む。レベル2において、これは最後のレベルであり近傍領域が存在しないため、何も格納されない。タプルの各成分はnビットとして格納される。レベル毎のビット数は、対応するレベルの領域数から判定される。従って、リストにランダムにアクセスできる。3つのレベルの100x10x5の場合、タプルa.b.cを符号化するには、aに対しては7ビットレベル0の領域が100個存在するため、bに対しては4ビットレベル1の領域が10個存在するため及びcに対しては3ビットレベル2の領域が5つ存在するためを使用する。例:100x10x5個の領域、すなわち粗レベル0の100個の領域、中間レベル1の10個の領域及び詳細レベル2の5つの領域のセグメントを仮定する。レベル0のファイルにおいて、近傍リストを含むセクションは以下を含む。レベル0の100個の領域に対するリストの長さを示す100個の番号。ビット数は、BitsRequiredlongestListLength-shortestListLengthから算出される。各番号は、そのレベルの最短リストに相対的である最短リストはヘッダに格納される。その後、100個のリスト100対の内容に従う。各対の第1の要素は7ビットレベル0の領域が100個存在するために符号化され、各対の第2の要素は4ビットレベル1の領域が10個存在するために符号化される。レベル1のファイルにおいて、近傍リストを含むセクションは以下を含む。レベル1の1000個の領域に対するリストの長さを示す10010=1000個の数字。1000個のリスト1000個の3つの要素のタプルの内容に従う。各タプルの第1の要素は7ビットレベル0の領域が100個存在するために符号化され、各タプルの第2の要素は4ビット各レベル0領域においてレベル1の領域が10個存在するために符号化され、各タプルの第3の要素は3ビット各レベル1領域においてレベル2の領域が5つ存在するために符号化される。レベル2のファイルにおいて、これは最後のレベルであるため、何も格納する必要がない。符号化入力ファイルに関して、複数のリストのフォームの何れかが適合されてもよい。このように、3つのレベルへの分割が実行されると、各ノードは、1つのレベルあたり1つの領域、即ち、3つの領域に割り当てられる。ヘッダ800一般に、本発明の実施形態で使用されるヘッダは小さく、従ってそのサイズを縮小するためにサイズを最適化する必要はない。一般に、全てが便宜上位置合わせされたバイト又は単語である。4バイト符号化バージョン地図形式が変更される度に増加する4バイト地図フラグ機能をON又はOFFする。最初は0であるが、オプションの機能を追加する必要がある場合に後で使用される4バイト地図中のノードの合計数4バイト地図中の道路セグメントの合計数4バイトハフマン木セクションのバイトオフセット4バイト領域ブロブセクションのバイトオフセット4バイト領域ページ情報セクションのバイトオフセット4バイトビットベクトルページ情報セクションのバイトオフセット4バイト可変サイズレコードセクションのバイトオフセット4バイトビットベクトルarpフラグページの最大ビット数起動時にビットストリーム復号器に対して悪い例を事前に割り当てるために経路計画方法により使用される4バイト平均ビットベクトルarpフラグページサイズのビット数ビットベクトルページ位置を補間するために使用される4バイト最小ビットベクトルarpフラグページデルタ全てのデルタを>=0にするために使用され、ビットサインを格納することを回避する2バイトビットベクトルarpフラグ履歴の最大サイズ起動時に履歴バッファを事前に割り当てるために経路計画方法により使用される2バイトページ毎の道路セグメントの最大数現在使用されていない1バイトこのファイルのアポロレベル1バイトビットベクトルarpフラグ毎のビット1バイトビットベクトルarpフラグページデルタ毎のビットビットベクトルarpフラグページの固定サイズレコードのフィールド1バイトブロブ指標毎のビット領域ページ情報の固定サイズレコードのフィールド1バイト領域数毎のビット領域ページ情報の固定サイズレコードのフィールド1バイト非自明なビットベクトルarpフラグブロック毎のビット1バイト領域ノードページサイズのlog_21バイトビットベクトルarpフラグページサイズのlog_21バイトローカル領域IDを符号化するためのハフマン木の数1バイトビットベクトルarpフラグ履歴符号を符号化するためのハフマン木の数。ハフマン木802各ノードの周囲の道路セグメント数を符号化するためのハフマン木。小さく、10個ほどの符号がレベル0のファイルにのみ存在する非自明なビットベクトルarpフラグのブロックを格納するためのハフマン木。最大のハフマン木であり、大きい程、圧縮に適切であるが、経路計画方法で必要とされるメモリは多くなる経路計画方法でのメモリの使用量と地図圧縮との間のトレードオフの関係。履歴サイズが0である場合のビットベクトルarpフラグデルタ符号のハフマン木。小さく、符号を3つだけ含む。履歴サイズが1である場合のビットベクトルarpフラグデルタ符号のハフマン木。小さく、符号を4つだけ含む。履歴サイズが>=nである場合のビットベクトルarpフラグデルタ符号のハフマン木。小さいヘッダに格納されたハフマン木の数。領域ページに3つの領域が存在する場合の領域IDに対するハフマン木。小さく、符号を3つだけ含む。領域ページに4つの領域が存在する場合の領域IDに対するハフマン木。小さく、符号を4つだけ含む。領域ページに>=n個の領域が存在する場合の領域ID対するハフマン木。小さいヘッダに格納されたハフマン木の数。領域再マップテーブル804及び領域IDリスト806図8のファイル形式の他の部分より小さいが、領域ID806は、図11に例示するように圧縮されてもよい。ここで、使用されるデータ量を減少するために、地理的相関が使用されてもよい。各領域ページは、その領域ページの別個の領域のリストを格納する。このリストは、殆どの場合に小さいと予想される実際には、多くのページは少なくともレベル0の領域を1つだけ含む可能性が高い。領域のリストは可変サイズを有する。ページ内のデータは、ランダムにアクセス可能であるべきでありすなわち、ランダムアクセス、固定テーブルサイズはこれを可能にするために使用される。別個の領域の各リストは、各領域のノードの頻度により順序付けされる。リストの第1の要素は、ページ中の最大数のノードを含む領域に対応し、リストの再度の要素は、ページ中の最小数のノードを含む領域である。領域ページの各ノードにおいて、ローカル領域IDページにローカルなを使用してその領域IDを符号化できる。このローカルIDは、ページ中の領域の指標であるこれは小さい整数であり、0は領域ページの最も一般的な領域に対応するため、多くの場合は0である。ノードの領域IDは以下のように格納される。領域ID’を含む領域配列はページ中の領域の可能な重複リストを全て格納する。領域のリストは、その配列において連続した領域IDである。リストは、重複してもよい重複する。配列は各リストの開始及び終了を格納しないこれは、領域ページ情報テーブルにより行われる。領域ページ情報テーブルは固定サイズレコードテーブルであり従って、ランダムにアクセス可能である、各レコードはリストの開始の配列における指標リスト中の項目数を含む。各ノードはローカルノードIDそのページにローカルなを含む。これらの概念の各々については、以下に更に規定する。領域配列領域配列は、ページの全ての可能な領域リストを符号化する。領域IDのリストが重複してもよい領域IDの単純な配列である。そのサイズは、リストが重複するため小さい。領域配列については、領域ページ情報の節で更に説明される。領域ページ情報領域ページテーブルの領域IDのリストを指定するには、領域ページ情報テーブルの固定サイズレコードの2つのフィールドを使用する。領域数このページの領域数であり、小さいと予想される領域リストの配列へのオフセットここで領域のリストが開始する一実施形態において、これについては図12で説明する通りである。オフセットフィールドは領域配列を示す。領域ID毎に1バイトの固定サイズレコードで十分である。例えば、各レベルには256個未満の領域が常に存在すると仮定する。これは妥当な仮定であるしかし、レベル毎に256ビットというのは制限しすぎであると考えられる場合、8ビットより大きくすることは容易に可能である。領域ページテーブルレコードの領域数は、指定されたオフセットで配列にあると考えられる領域数を示す。いくつかの領域が同一リストを有する場合、それらは同一の場所を示せる。これは、多くのページが同一リストを共有するか又は同一リストの部分を共有することが予想できるためコンパクトであるべきである。これについては、図12を参照して更に詳細に説明する。図12は、2^nr個のノード例えば、512個のノードをグループ化するためにnr=9のページを有する一実施形態を示す。尚、いくつかのページが配列において同一の場所又は重複する場所図中、領域ブロブとラベル付されたを示せるため、領域IDの配列900は非常にコンパクトである。実際には、各ページがより少ない領域と重複し、組み合わせの可能性が低減されるため、ページ数を増加することにより配列のサイズは増加されない。従って、この配列は、生成された地図データがロードされる装置において多くの地図空間も多くのメモリも必要とせずに多くのページを作成することを可能にすべきである。方法の目的は、領域IDのリストを含む配列900を可能な限り小さく維持することである。方法の目的は、領域IDの同一のリストを配列において可能な限り多く再利用することである。方法は、リストの最後の2つの要素がハフマン符号のサイズに影響を及ぼさないためそれらの要素を自由に再順序付けできる。例えばリストが2つの領域10及び34を含む場合、2つのノードが存在する全ての例においてハフマン木が1ビットのみを使用するため、これはリスト10、34又は34、10を格納すること頻度に関係なくと同等である。換言すると、頻度により再順序付けすることは、最後の2つの領域に対して緩和される。同様に、第1の符号10頻度が最も高いのみが1ビットを使用し、他の符号40及び34の双方が2ビットを使用する順序に関係なくため、3つの要素10、34、40のリストは10、40、34として格納されてもよい。図9を参照すると、配列900が2つの値、すなわち長さ及び領域データの開始からのオフセットを格納することが分かる。第1の行3:0を考慮すると、これはファイルの開始から0だけオフセットして3つのデータを参照するすなわち、10、34、40。更なる例を考慮すると、配列エントリ1:2は、ファイルの開始から2だけオフセットした単一の領域すなわち、長さ1を参照するすなわち、領域40。別の実施形態において、領域ページ情報は、以下の方法に従って符号化される。このセクションは、各領域のサブ領域数を符号化する。サブ領域の数はレベル毎に可変であってもよい。しかし、サブ領域数がレベル毎に一定であることが多い。サブ領域数は、log_2max_number_of_regions-min_number_of_regionビットを使用して、各レベルの最小領域数に対して相対的に符号化される。従って、領域数が一定である場合、領域数を符号化するために0ビットが使用され、このセクションは空である。最小領域数及び最大領域数は、副ファイルのヘッダに格納される。近傍領域セクションの符号化近傍領域についは、図6及び図6aに関連して説明するこのセクションは、所定のレベルLの領域階層毎に、より詳細なレベルL1の近傍領域のリストを符号化する。例えば、レベルL=1の領域3.9は、レベルL=2において近傍領域のリスト、3.5.4、3.6.3、3.6.4、4.7.1、4.7.3を有してもよい。他で説明するように、近傍領域のリストは、各副ファイルを生成するのに使用される前処理の速度を向上するために使用されてもよい。このセクションは2つのサブセクションに分割される。全ての近傍リスト所定のレベルにある領域と同数の長さを符号化するサブセクション。長さは、最短リストに対して相対的に符号化され、ビット数はlog_2length_longest_list-length_shortest_listで計算される。全てのリストが同一の長さを有する場合、長さを符号化するのに0ビットが使用される従って、セクションは空である。全ての近傍リスト所定のレベルにある領域と同数を符号化するサブセクション。領域ID再マッピングテーブルの符号化このセクションは、レベル0の副ファイルでのみ符号化される。これは、レベル0の各領域のビットを再順序付けし且つ結合するのに使用される2次元テーブルを符号化するビットベクトルを効率的に符号化するために、結合及びビット再順序付けについて本文献において以下に更に説明する。ビットベクトルのビットの再順序付け及び結合は、ビットベクトルのハフマン符号化を最適化するために行われる。このテーブルは、以下が分かっている場合に復号化するビットベクトルにおけるビット位置を見つけるために経路計画方法により使用される。現在のノードの出発領域ID元の到着ビット指標すなわち、ビットベクトルのビットを分離した後のビット指標2次元テーブルの2つの指標は以下の通りである。出発領域ID行先ビット指標目的地の領域このセクションは2つのサブセクションから成る。レベル0の領域毎に結合ビット数を符号化するセクション。各数を符号化するために使用されるビット数は、log_2max_number_of_coalesced_bitsである。ビット再マッピングテーブルを符号化するセクション。経路指定する場合、行先ビットは変化しないが経路指定の間、目的地は同一のままである、出発領域IDは行先ビットの行により格納された行列を変更する経路指定中に探索されるノードに依存して。各行において、ビット再順序付け番号は、出発領域毎に格納される。一般に、経路計画方法は、経路指定中、所定の経路指定目的地に対応するメモリの1行のみをロードする。経路計画方法は、2次元行列全体をメモリに格納する必要はない。経路計画方法は、その行にランダムにアクセスできる。各再マッピングエントリを符号化するのに使用されるビット数は、log_2最大結合ビット数で計算される。図13は、レベル0領域図9を参照に対する図11に示したファイルのビットベクトルセクション812を展開する。各ページが道路セグメント数、領域ID及びビットベクトルを含むことが分かる。図14は、レベル0以外のレベルに対する図11に示したファイルのビットベクトルセクション812を展開する。他の領域に対して、ビットベクトルのみが格納され、レベル0に対して格納される道路セグメント数又は領域IDは格納されない。各レベルの領域によってカバーされる領域の差異を考慮して、ページ毎のノードの数がレベル毎に変更されうる。例えば、レベル0内の領域が大きな領域をカバーする場合に、レベル0に対する領域毎、ページ毎のより多くのノードがあってもよい。例えば、いくつかの実施形態は、レベル0に対するページ毎、レベル毎に512ノードを格納してもよい。その場合、多くの精細なレベルは、より少ない数のノード、例えば、256ノード、128ノード、64ノード、32ノード、16ノード等を有してもよい。実際に、いくつかの実施形態は、ページ毎に、1024ノード、2048ノード、又は4096ノードを利用してもよい。ビットベクトル810、812の符号化テーブル810は固定サイズレコードを含む。出発ノードIDは2nのページにグループ化される。ビットベクトルが同一の近傍領域のいくつかの道路セグメントに対して同様のパターンを有すると予想されるため、複数の連続したノードのページにデータをグループ化するのが便利である。ページを使用することにより、いくつかの道路セグメントをデルタに符号化でき、適切な圧縮を達成できる。同様に、ページにおいてデルタにノードの領域IDを符号化できる。一方、これは、1つの道路セグメントのデータにアクセスすることがいくつかの道路セグメントのデータをアンパックすることを必要とすること直接ランダムアクセスではないを意味する。1つの道路セグメント又はノードのデータにアクセスするのにいくつかのノード又は道路セグメントをアンパックする必要があることは、以下の理由により受け入れ可能であると考えられる。データは、1つの道路セグメントにアクセスする時に読み出された追加のデータが無用でないことが多いためキャッシュされる。この追加のデータはすぐ後で有用となるだろうこれは、ディスクキャッシングの先読みパラメータに類似する。ビットベクトルを使用する経路指定は、ダイクストラA経路指定と比較した時に拡張探索のサイズをある桁だけ減少する。ページ毎にデータをグループ化することにより、地図の小さな部分が依然として復号化される必要がある実際のパスに沿うページ。領域IDビットベクトルのデルタ圧縮のために符号化データサイズが非常に縮小される。上述したようにデータが副ファイルに格納されるため、ページは指標付けのサイズを縮小する。テーブル810内の各レコードは、デルタフィールドを含み、これは、各ページの可変サイズの開始位置補間位置に対するデルタを見つけるために使用される。デルタ毎のビット数はヘッダに格納される。領域ID及びビットベクトル812にアクセスするために、復号器は線形補間を行うことにより開始ページの推定されたオフセットを計算してもよい。interpolated_offset=from_node_idavg_page_size式中、avg_page_sizeはヘッダに格納された平均ページサイズのビット数である精度を向上するために可能性として固定点における。データのオフセットは、以下のように計算される。オフセット=interpolated_offsetmin_deltaデルタ式中、min_deltaは全てのページヘッダに格納されたに対する全てのデルタフィールドの最小値であり、デルタは、ページに格納された符号なしフィールドである。min_delta値は、全てのデルタフィールドが正の値であること格納するビット符号はないを保証する。可変サイズレコードは、上述したビットベクトルページ情報のデルタフィールドを介してアクセスされる。各レコードは、2n個のノードのデータ全てのレベルにおける出発ノードの領域ID及びそれらの連結道路セグメントのビットベクトルを含む。従って、同一の指標付け方式が全てのレベルに対して使用される。可変サイズレコードは以下を格納する。ページ符号-そのページ内のノードが同一領域の一部であるか否かを示すページ全体に対する符号。ビットベクトルページの各ノードの周囲の道路セグメント数全てのレベルに対して同一であるため、レベル0でのみ格納される。ページの出発ノードの領域ID。レベル毎に1つのIDがあるレベル0でファイルに格納された全てのレベルに対する情報。レベルiのみのページのノードの周囲>2個の連結道路セグメントを有するノードの周囲のみの道路セグメントのビットベクトル。これはデータの最大の部分である。各ノードの周囲の道路セグメント数の符号化。ビットベクトルページの2n個のノードの各々に対して、ハフマン符号はノードの周囲の道路セグメント数を符号化する。この情報は、全てのレベルに固有のものではなく、レベル0のファイルap_0_.datにのみ格納される。ノードの周囲の道路セグメント数を認識することは、ビットベクトルを復号化するのに使用される図10の1000を参照。この情報は、他のファイルに既に存在する情報と冗長するが、他の場所にある情報をルックアップする必要なくページ中のビットベクトルを復号化するのを容易に且つ迅速にする。これにより、サイズの小さな増加が性能を向上する。可変サイズレコードの領域IDの符号化ノードの領域ID1002は、各ノードの周囲の道路セグメント数1000の符号化の直後に可変サイズレコードに符号化される符号化レイアウトを参照。前処理において生成されたビットベクトルを使用して経路指定を行うために、一般に所定のノードに対する全てのレベルの領域ID1002にアクセスする必要があり、全てのレベルの領域IDは、レベル毎に異なるファイルに分割されるのではなく互いに近接して同一ファイルに格納される。3つのアポロレベルを有する2n例えば、n=4個のノードのビットベクトルページは以下のようにノードIDを格納する。ノード0:local_region_id_level_0local_region_id_level_1local_region_id_level_2ノード1:local_region_id_level_0local_region_id_level_1local_region_id_level_2ノード2:local_region_id_level_0local_region_id_level_1local_region_id_level_2...ノード15:local_region_id_level_0local_region_id_level_1local_region_id_level_2更に、以下の通りである。1つ又は2つの連結道路セグメントを有するノードの周囲で符号化されるものはないすなわち、連結道路セグメント数として0を格納するノードに対して。ページ符号のビットが所定のレベルで設定される場合、全てのノードはそのレベルの同一領域IDにあり、そのレベルの領域IDは1度だけ符号化される>=3個の連結道路セグメントを有する第1のノードに対して。領域IDを符号化するビット数はlog_2regionCount-1である。領域IDが符号化されるページの第1のノード以外は、各領域IDを符号化する前にビットが符号化される。このビットは、領域IDが同一レベルの先に符号化されたノードIDと同一であるかを示す。このビットが設定される場合、そのレベルの先に符号化されたものと同一であるため、領域IDを符号化する必要はない。このビットが0である場合、log_2regionCount-1ビットで領域IDを符号化する。多くの連続したノードが同一の領域にあるため、領域IDを符号化するのに1ビットだけ必要とすることが多い。以下の理由のために、ローカル領域指標のハフマン符号化は効率的である。領域は各領域ページにおける頻度によりソートされる従って、ローカル指標0はローカル指標1、...より頻度が高い。ページの領域数毎に別個の専用のハフマン木が存在する3つの領域がページにある場合に1つのハフマン、4つの領域がページにある場合に1つのハフマン木等。ハフマン木は小さいため、メモリを多く使用せずにいくつか格納できる。少なくともレベル0において、3つ以上の領域を有することは極めて珍しいしかし、他のレベルでは珍しくない。可変サイズレコードのビットベクトルの符号化各可変サイズレコードは、ページのノードの周囲の全ての道路セグメントに対するビットベクトルを含む。ビットベクトルは、3つ以上の連結された線道路セグメントを有するノードの周囲でのみ符号化される。1つ又は2つの連結道路セグメントを有するノードの場合、経路指定方法は、それらのノードにビットベクトル値111...111を黙示的に与えられる。到着ノードは符号化されない。図10を参照すると、道路セグメントは、それぞれが道路セグメントの端部にある2つのノードにより指定されてもよい。従って、方向が考慮される場合、方向の開始にあるノードはfrom_nodeと呼ばれてもよく、方向の終了にあるノードはto_nodeと呼ばれてもよい。ビットベクトルに関する種々のプロパティは、効率的にするために符号化内で使用される。ビットベクトルの多くは000...000又は111...111である。ビットベクトルの他の値すなわち、000...000でも111...111でもないに対しては、繰り返しになる可能性が高く、同一の値が繰り返される可能性が高い。また、所定ノード周辺の全てのビットベクトルのORが111...111であるべきである。ビットベクトルは、第1のハフマン符号及びオプションの更なるハフマン符号として符号化される。第1のハフマン符号は、ビットベクトルが以下のいずれであるかを示す。自明なビットベクトル000...000に対する符号0自明なビットベクトル111...111に対する符号1符号2、すなわちページでまだ遭遇していない非自明なビットベクトルを示す符号。この場合のみ、新たに遭遇したビットベクトルを符号化するために他のハフマン符号が後続する。ビットベクトルが現在のページの先に遭遇したビットベクトルと同一である場合自明なビットベクトル000...000及び111...111は無視する、>=2の符号。この符号化は、ページの先に遭遇した符号の履歴を使用する。符号は、実際には先に遭遇した全ての符号の履歴中の指標を与える。このハフマン符号以外は、履歴中で見つけられなかった非自明なビットベクトルの場合符号=2にのみ、更なる情報が符号化される必要がある。この場合、ハフマン符号==2の直後に以下が符号化される。否定ビットNビットのブロックによりn個の領域に対するビットベクトルを符号化するためのいくつかのハフマン符号N及びnは地図ヘッダで与えられる。例えば、100個の領域99ビットのビットベクトルを11ビットのブロックを使用して符号化することは、9個のハフマン符号9x11=99を符号化することを必要とする。殆どのビットベクトルは殆どが0又は殆どが1のベクトルを含むため、否定ビットは、ビットベクトルが否定されて格納されるか否かを示す。これにより、殆どが0のベクトルを多く含むハフマン木への符号の格納を可能にするこれにより、ブロックのハフマン符号化を向上する。ブロックのサイズが領域数より小さい場合にのみ否定ビットは存在し、これは、実際にはレベル0において当てはまるが、レベル1又は2において、ビットベクトル全体は1つのブロックにのみ符号化されるため否定ビットは必要ない。100個の領域が存在する場合、すなわちN=100従って、99ビットのビットベクトルの場合、第1のブロックは行先領域1~11に対するビットを符号化し、第2のブロックは領域12~22を符号化する。第1のブロックにおいて、LSB0x1は行先領域1に対応し、次のビット0x2は領域2に対応し、次のビット0x4は領域3に対応する。履歴を使用するビットベクトルの場合、履歴配列の深さはページ中の先に遭遇した別個のビットベクトルの数である自明なビットベクトル000...000及び111...111を考慮に入れない。異なるハフマン木は、履歴ベクトルが0個の要素、1つの要素、2つの要素、3つの要素等を含むかに関わらず使用される。全てのハフマン木が小さいために大きな記憶容量が必要とされないため、ハフマン木を増加することは受け入れられる。履歴が0個の要素を有する場合、ハフマン木は3つの符号、すなわち000...000に対する0、111...111に対する1、新しいビットベクトルに対する2を有する。履歴が1つの要素を有する場合、ハフマン木は4つの符号、すなわち000...000に対する0、111...111に対する1、新しいビットベクトルに対する2、履歴の要素0と同一のベクトルに対する3を有する。履歴が2つの要素を有する場合、ハフマン木は5つの符号、すなわち000...000に対する0、111...111に対する1、新しいビットベクトルに対する2、履歴の要素0と同一のベクトルに対する3、履歴の要素1と同一のベクトルに対する4を有する。その他。ビットベクトルページのサイズが小さい例えば、2n個の出発ノードと予想されると、ハフマン木の数も小さいと予想される。しかし、ハフマン木のサイズを最大値に制限できる。例えば履歴がH個より多くの要素を含む場合は必ず、単一のハフマン木が使用される値Hは地図ヘッダに格納される。この符号化は、各ページ中の別個のビットベクトルいくつかの符号のみを符号化する。経路指定の目的でビットベクトルページ中の復号化するより多くのビットベクトルを使用するために、符号化は、復号化を遅くする代わりに大きな指標のページに対してサイズに関してより効率的である。統計ベネルクスを254個の領域1つのレベルに符号化する場合のファイル形式に対する詳細な統計を示す。以下の入力パラメータを使用した。ビットベクトルブロック毎のビット数:11ビットベクトルページ毎のノード数:2^4=16領域ページ毎のノード数:2^9=512統計は、地図のサイズに関して地図形式の概念を与え且つ実データに関する地図形式の記述を示すために提供される。---グローバル統計カウンタ:ノード数.......................1598632線の数........................1598632100.0001つの線を有するノードの周囲の線をスキップする...22018013.7732つの線を有するノードの周囲の線をスキップする...72713845.485---レベル=[0]の統計:地図カウンタ......................87437736100.000符号化された自明なarpフラグ000...000...131091431.651符号化された自明なarpフラグ111...111...91334822.052履歴中の符号化されたarpフラグ...........3624328.751履歴中にない符号化されたarpフラグ.........60771714.673否定ブロック....................2351715.678地図のサイズビット.................87437736100.000グローバルヘッダ...................4960.001ハフマン木......................288080.033領域ブロブ......................526640.060領域ページ情報....................562160.064arpフラグページ情報................24978802.857可変サイズレコード..................8480167296.985ノードの周囲の線の数................28478443.257ノード領域ID...................21124512.416arpフラグ....................7984137091.312自明な符号000...000...........16893221.932自明な符号111...111...........18266962.089履歴中で見つけられた符号.............16680531.908履歴中で見つけられない..............7465729985.383履歴中で見つけられない符号...........14631831.673否定ビット...................6077170.695ブロック....................7258639983.015全てのサイズはビット単位である。地図の合計サイズは、87,437,736ビット10,929,717バイトである。インデントは階層を反映している。可変サイズレコード情報は、圧倒的に大きい情報地図のサイズの96.975である。可変サイズレコードにおいて、サブ項目インデントされたはより詳細を与える。ビットベクトルは、可変サイズレコードに格納する圧倒的に大きな情報91.312である。ビットベクトルにおいて、履歴においてまだ遭遇していない非自明なビットベクトルを格納することは地図の最大部分を構成する83.015。ハフマン木に関する統計このセクションは、ベネルクスを255個の領域に符号化するすなわち、上記で示した地図データに対して場合のハフマン木に対する統計を与える。各ノードの周囲の道路セグメント数のハフマン木---[ハフマン木:Nr本の線]---ビット:1値:3符号0ビット:2値:2符号10ビット:3値:1符号110ビット:4値:4符号1110ビット:5値:5符号11110ビット:6値:6符号111110ビット:7値:7符号1111110ビット:7値:8符号1111111殆どのノードは3つの連結道路セグメントを有するが、ハフマン木の第2及び第3の位置において、2つ又は1つの連結道路セグメントを有するノード決定ノードではないを見つける。非自明なビットベクトルブロックのハフマン木自明なビットベクトルのブロックを格納することが圧倒的に大きな地図のサイズを占めるベネルクスの255個の領域の例において83.015ため、これは最大のハフマン木である。---[ハフマン木:NonTrivialArpFlagBlock]---ビット:1値:0符号0ビット:6値:1符号100000ビット:6値:2符号100001ビット:6値:4符号100010ビット:6値:8符号100011ビット:6値:16符号100100ビット:6値:32符号100101ビット:6値:64符号100110ビット:6値:512符号100111ビット:6値:1024符号101000ビット:7値:128符号1010010ビット:7値:256符号1010011ビット:7値:384符号1010100ビット:8値:5符号10101010...大きすぎるため中略...ビット:24値:1534符号111111111111111111111011ビット:24値:1717符号111111111111111111111100ビット:24値:1741符号111111111111111111111101ビット:24値:1830符号111111111111111111111110ビット:24値:1973符号111111111111111111111111全て0から成るブロックを格納することは、頻度が最も高いパターンであり、上記ハフマン木に従って1ビットのみに符号化されるこれは、自明なビットベクトル000...000がブロックにより符号化されないが、ブロックの50以上が値0を符号化することを意味する。これは、殆どの非自明なビットベクトルが以下のいずれかを含むためである。殆どが0及びいくつかの1殆どが1及びいくつかの0符号化方式は、殆どが1であるビットベクトルに否定演算~をし、最終的にビットベクトルのブロックを符号化することは、主に、000...000を含むブロックを1ビットにのみ符号化する。次に頻度の高いブロックは、1ビットのみが設定されるブロックである1、2、4、8、16、32、64...。これらのブロックは同程度の頻度を有するため、同一又はほぼ同一のビット数を有する。ローカル領域IDのハフマン木領域のリストが頻度により各ページに格納されるため、ローカル領域ID0を格納することは他の場所の領域IDより少ないビット数実際には1ビットのみを利用する。種々のハフマン木は、3つの領域、4つの領域、5つの領域等を含むページに対応する。---[ハフマン木:Regions_0]---ビット:1値:0符号0ビット:2値:1符号10ビット:2値:2符号11---[ハフマン木:Regions_1]---ビット:1値:0符号0ビット:2値:1符号10ビット:3値:2符号110ビット:3値:3符号111---[ハフマン木:Regions_2]---ビット:1値:0符号0ビット:2値:1符号10ビット:3値:2符号110ビット:4値:3符号1110ビット:4値:4符号1111---[ハフマン木:Regions_3]---ビット:1値:0符号0ビット:2値:1符号10ビット:3値:2符号110ビット:4値:3符号1110ビット:5値:4符号11110ビット:5値:5符号11111...以下略...。ビットベクトル履歴符号のハフマン木符号0自明なビットベクトル000...000を意味するは、頻度が最も高い且つ殆どの場合、1ビットにのみ符号化される。符号1自明なビットベクトル111...111は、次に頻度が高い且つ1ビットにのみ符号化される。次に頻度が高い符号2は、ブロックにより符号化された非自明なビットベクトルに対するものである。他のコード>2は履歴中に見つけられるビットベクトルに対するものである。---[ハフマン木:ArpFlag_0]---ビット:1値:0符号0ビット:2値:1符号10ビット:2値:2符号11---[ハフマン木:ArpFlag_1]---ビット:1値:0符号0ビット:2値:1符号10ビット:3値:2符号110ビット:3値:3符号111---[ハフマン木:ArpFlag_2]---ビット:1値:0符号0ビット:2値:1符号10ビット:3値:2符号110ビット:4値:3符号1110ビット:4値:4符号1111---[ハフマン木:ArpFlag_3]---ビット:1値:0符号0ビット:2値:1符号10ビット:3値:2符号110ビット:4値:3符号1110ビット:5値:4符号11110ビット:5値:5符号11111---[ハフマン木:ArpFlag_4]---ビット:1値:0符号0ビット:2値:1符号10ビット:3値:2符号110ビット:4値:3符号1110ビット:5値:4符号11110ビット:6値:5符号111110ビット:6値:6符号111111---[ハフマン木:ArpFlag_5]---ビット:2値:0符号0ビット:2値:1符号01ビット:2値:2符号10ビット:4値:3符号1100ビット:4値:4符号1101ビット:4値:5符号1110ビット:5値:6符号11110ビット:5値:7符号11111...以下略...。地図のサイズに対する入力パラメータの影響図11に示したファイル形式を制御し且つ地図のサイズに影響を及ぼす入力パラメータが多く存在する。パラメータを微調整することは、パラメータに依存する伸張の速度又はメモリ使用量と地図のサイズとの間のトレードオフの関係となる。本発明の実施形態は、以下の入力パラメータを使用してもよい。領域ページサイズビットベクトルページサイズビットベクトルブロックサイズビットベクトルハフマンコーデック数領域ハフマンコーデック数。ビットベクトルブロックサイズの影響値地図のサイズビット435548192533648792632290344730853616831103200930436696デフォルト103005179211292667841228934696。ビットベクトルに対するハフマンブロックサイズを増加することにより、地図圧縮は向上される。ブロックサイズが大きい程、圧縮はより適切になる。しかし、ブロックサイズを増加することは、2^n個の値のより大きなハフマン木を格納するのにより大きなメモリが必要となる。上記テーブルはこのことを示す。ソース領域毎に領域IDを再マッピングするために最適化を導入する場合、このパラメータの影響はより大きくなると予想される。この最適化の結果、大きいビットベクトルブロックサイズを使用する場合に地図のサイズが非常に減少されるのが望ましい。ビットベクトルページサイズの影響値地図のサイズビット2^1555639442^2425029362^3348988402^430436696デフォルト2^5273899522^6251650322^723635936ページサイズを増加することは、地図をより適切に圧縮するのを助長する。しかし、ランダムな道路セグメントのビットベクトルにアクセスするにはページ中の全ての道路セグメントを復号化する必要があるため、大きなページは経路指定方法によりデータをファイル形式に伸張することを遅くする。上記テーブルはこのことを示す。ビットベクトルハフマンコーデック数の影響値地図のサイズビット130866920230748024330634168530504504730467944930436696デフォルト1130423688ビットベクトルハフマンコーデックの数を増加することは、圧縮を僅かに向上させるのを助長し、これを上記テーブルに示す。ハフマン木はいずれの場合も小さいため、値を増加することに対する欠点はほぼない。9個デフォルト値を上回ってハフマン木を増加しても大きな改善は得られない。このパラメータを増加することは、ビットベクトルページが大きいほど効果的である可能性がある。ビットベクトルのビットの結合再順序付けビットベクトルはパターンを有する。これらのパターンはソース領域すなわち、ビットベクトルが格納されるノードの領域毎に大きく異なる。Nビットのビットベクトルを格納するためのビット数は、ソース領域毎に小さな変換テーブルを格納することにより減少される。これらのテーブルは、この節で更に説明される2つの関数を実行する。ビットの結合ビットの再順序付け概念は、以下のように直感的に理解される。スペインの場合、スウェーデン行先領域スウェーデンに対してビット=1に通じている道路セグメントは、ノルウェーすなわち、目的地ノルウェーに対するビットも1に通じている可能性が高いことは明らかである。別の道路セグメントがスウェーデンビット=0に通じていない場合、その道路セグメントは殆どの場合においてノルウェーにも通じていない。従って、スペインの場合、行先領域スウェーデン及びノルウェーに対するビットベクトルのビットの値はほぼ常に等しい。実際には、ビットの値は多くの行先領域に対して常に厳密に等しい。どのビットがどのビットに相関しているかは、出発領域に大きく依存する。例えばフィンランドの場合、行先領域ノルウェー及びスウェーデンに対するビットは殆ど相関しない。一方、フィンランドにおいて、行先領域スペイン及びポルトガルに対するビットは100又は少なくともほぼ100相関する可能性が高い。ビットの結合は、いくつかのビットが常に等しい完全に相関されるというプロパティを利用する。これらのビットは単一ビットに結合される。ビットを結合することにより、各領域で符号化するビット数が減少される。ビットの再順序付けは、ビットベクトルのハフマン符号化を最適化するように且つ/又はハフマン木のサイズを縮小するようにビットをシャッフルするために、いくつかのビットが十分適切に相関されるしかし、100相関されるわけではないというプロパティを利用する。ビットを結合し且つ再順序付けするためのテーブルを計算する前に、全ての出発領域の全てのビット対の相関が算出される。別個の対の数は以下の通りである。CN,2=N/2N-2=NN-1/2式中、Nは領域数である。この数は、領域数が多い場合に大きくなる。全てのビット相関を計算することは、図8に示したファイル形式を生成する方法の最も遅い部分である。方法の複雑さはnNNであり、nはビットベクトル数であり、Nは領域数である。各領域のビット対すなわち、ビットベクトルの個別の列の対毎に3次元テーブルを計算する。bitCorrelation[fromRegionId][bitI][bitJ]テーブルの各エントリは、以下をカウントする4つのフィールドから成る構造を含む。fromRegionIdの全てのビットベクトルにおけるbitI=0及びbitJ=0の回数fromRegionIdの全てのビットベクトルにおけるbitI=0及びbitJ=1の回数fromRegionIdの全てのビットベクトルにおけるbitI=1及びbitJ=0の回数fromRegionIdの全てのビットベクトルにおけるbitI=1及びbitJ=1の回数計算するためのプロセッサの時間に関して高価である且つ従って遅いが、出発領域毎にビット相関を計算することは他の出発領域から完全に独立しているため、この処理は容易に並列化できる。本発明の実施形態は、マルチスレッディングを使用して、SMP対称型マルチプロセッシングマシンを効率的に使用するための全てのビットの相関の計算を加速する。1つのシステムにおいて、300個の領域を含むベネルクスのビット相関を計算する1CPUのマシンは約8分かかる。しかし、並行処理が適切に釣り合い、スレッドを可能にし且つビット相関を計算する4つのCPUを使用する場合は2分1/4の時間かかる。ビットの結合いくつかのビットが完全に相関される場合すなわち、常に全て0又は全て1、どの情報も損失することなくそれらのビットを1ビットのみに結合できる。所定の領域においてグループとして完全に相関されるビットの集合を参照すると、所定の領域のビットベクトルはいくつかのグループから成る。Nビットのビットベクトルがn個のグループから成る場合、Nビットのビットベクトルを符号化することはnビット各領域において等しいビットを示す小さなテーブルを使用する。そのようなビットの結合は、結果として得られるファイルのサイズが可逆的に縮小されるという利点を有する。領域数が増加すると、より多くのビットが結合される可能性があるため、領域数の増加に伴いこの利点も大きくなる可能性が高い。従って、地図のサイズは領域数に伴いほぼ線形的に増加する。一実施形態において、以下のデータが得られた。最小グループ数平均グループ数最大グループ数255個の領域のベネルクス1284152300個の領域のベネルクス1390.017163従って、255個の領域を有するベネルクスの例において、12個のグループのみを有する少なくとも1つの領域が存在するすなわち、ハフマン符号化の前であっても及びハフマン符号化の後であっても255ビットのビットベクトルすなわち、ビットベクトルが領域数と同一の長さであるを符号化するのに12ビットだけ必要とされる。平均して、領域は255個の領域のベネルクスに対して84ビット必要とする。この例において、ハフマン符号化の前、最悪な領域でも152ビット152個のグループを必要とする。別の例として、符号化データから得られるような以下の18個のグループを有する上記255個の領域のベネルクスにおいてregionId=3を利用する。regionId=[3]は[18]個のグループを有する。各行は1つのグループregionId=3に対する18個のグループを表す。小括弧内の数字は、各グループで結合されたビット指標である。の後の数字は各グループのビット数である。この例において、1つのグループは非常に大きく、141個もの領域を含む。これは異例ではない。一般に、地図の境界上の領域は、地図の中央の領域より多くのビットを結合する。この例において、ビット数は平均で~3~=255/84に減少されている。当然、これは、符号化する残りのビットが元のビットより高いエントロピーを有する従って、ハフマンブロックにより符号化するのはより困難であるため、地図のサイズが1/3に縮小されることを意味しない。しかし、ビットの結合により、地図のサイズは可能性として非常に縮小される可能性がある。各領域のビットを結合させる場合、各領域のビットベクトルは、図12に示すように結果として異なるビット数を有するしかし、所定の出発領域のビットベクトルに対しては同一のビット数を有する。陰影は、各ビットベクトルの出発領域IDを示す。y軸はセグメントの順序を表す。例えば、最上部のブロックは1043本の線を表してもよく、次のブロックは507本の線を表してもよい。テーブルbitCorrelationが計算されると、完全に相関したビットのグループを特定することは非常に容易で且つ迅速である。01又は10パターンが見つからない全てのビット対は完全に相関され、1ビットに結合される。ビットの結合の更なる一例を与えるために、以下のテーブルは、それぞれが15ビットから成る6つのビットベクトルの一例を与える。これらは結合されていない。これらの15ビットのビットベクトルは、4つのグループ、すなわちハフマン符号化の前のビットベクトル毎に4ビットに結合される。テーブルの右側部分の見出しは、テーブルの左側部分の4ビットの結合ベクトルのビットを示す。明示するために、4ビットの結合ベクトルの第1のビットは、左側部分の第1列、第3列及び第9列を表す。従って、左側部分すなわち、15ビットの元のベクトルの第1のビット、第3のビット及び第9のビットが上記例において常に同一であるため、それらのビットは上記テーブルの右側部分の第1列により表されてもよい。従って、要約すると、左側と右側との間の索引のテーブルは以下の通りである。元のビット結合されたビット00112130405362718292103110123131141ビットを効果的に結合することは、近傍の行先領域及び図16に示すように出発領域から同一角度の扇形内にある行先領域をグループ化することである。図16の陰影は、結合される領域のグループを示す。2つの図面すなわち、図16a及び図16bは、2つの異なる出発領域の観点から結合された同一領域を示す。結合される領域は、図示するように出発ノードの領域IDに依存する。図中、8つの領域が4つのグループに結合される。ビットの結合は、これらの図の出発領域A又は出発領域Bの観点から異なる。尚、垂直の縞模様の領域1300は、出発領域Aから見た場合に同一方向のあるため結合される。これは、図17において更に例示される。図17は、ビットの結合が各出発領域の観点から近傍の行先領域及び/-の同一角度の扇形内にある行先領域をグループ化することを示す。ビットを結合した後、ビットベクトルに対して符号化するビット数は領域毎に異なる。例えば255個の領域のベネルクスの場合、領域毎のビットベクトルのビット数は以下の通りである。出発領域->結合されたビット1->572->933->184->125->636->75...中略...251->21252->46253->117254->80方法は正確であるヒューリスティックではない。従って、理想的なビットのグループ数が分かる。いくつかの実施形態において、ビットの結合は可逆的に実現される。すなわち、領域は常に同一ビットを有する場合に結合される。しかし、他の実施形態において、これは不可逆にするように、すなわち元のデータの完全な回復が不可能であるように拡張されてもよい。そのような不可逆の実施形態は閾値すなわち、密接度の尺度を導入してもよい。すなわち、ビット対がX倍未満だけ異なる場合、一部のビットベクトルの1つ以上の0を1で置換することによりビットベクトルを結合できる場合にビットを結合できる。従って、いくつかの実施形態において、そのような結合はほぼ相関されるビットに対して行われる。そのような不可逆結合の一例は、0000001100を0000001110と結合することである。そのような方法の利点は、データの圧縮がより適切であることであるが、欠点は、道路セグメントが最速経路の一部であることを追加の1が示すため、更なる道路セグメントがビットベクトルを使用して経路指定方法により評価されることである。可逆的結合の場合、閾値は0である。閾値を増加することにより更なる領域を結合することが可能になるが、いくつかのビット1をビットベクトルに導入する。しかし、閾値が小さく維持される場合、閾値は、経路指定がデータ形式を使用して実行される際の速度にほぼ何も影響を及ぼさない。例えば2ビットが1ビットのベクトル以外の数千個のビットベクトルにおいてほぼ常に同一である場合、これは、より多くのビットを結合することを可能にするために異なるものであるこの一意のビットベクトルを変更するために受け入れ可能であってもよい。閾値が大きい程、より高い地図圧縮を期待できる。ビットの再順序付けいくつかの実施形態において、上述したようにビットが結合されると、ビットは再順序付けされてもよい。ビットの再順序付けは、符号化するビット数ハフマン符号化前のを減少しないが、ハフマン符号化をより効率的にすることを助長し、従って地図のサイズを縮小する。ビットの再順序付けは、ビットベクトルハフマン符号における別個の符号の数を減少することを更に助長し、従ってハフマン木に要求されるメモリを減少する。ビットの結合とは異なり、ビットの再順序付けはヒューリスティック法であるため、適切な再順序付けを見つけるが、最善の再順序付けを見つけない可能性がある。ビットベクトルはブロックにより符号化される。ブロックサイズは、カスタマイズ可能であり、地図ヘッダ800に格納される。以下の説明において、一例として、ブロックサイズは11ビットに設定される。ビットベクトルのビット数は11で割り切れない可能性があるため、最後のブロックは11ビットより小さい可能性がある。最後のブロックは、11ビットの完全なブロックに対するハフマン木とは異なるハフマン木を使用する。各ビットベクトルを符号化することにより、以下を符号化する。11ビットのブロックこの例においてに対するハフマン符号を使用するいくつかの完全なブロック11ビット未満が残っている時に別のハウマン符号を使用する最後の1つのブロック以下の図は、2つの領域結合後、異なるビット数を有するのビットベクトルを有するブロックによりハフマン符号化するビットを示す。領域毎にハフマン木を有することはメモリに関して高価すぎる可能性がある。従って、いくつかの実施形態において、同一のハフマン木が全ての領域に対して共有される。相関したビットが各領域において異なるため、各領域のビットを再順序付けでき、その結果、相関したビットは全ての領域の同一位置に体系的に置かれる。従って、全ての領域にわたりハフマン木を共有することは更に効率的になる。領域毎にビットを再順序付けするテーブルは地図データに格納される。尚、ビットを結合するための別個のテーブル及びビットを再順序付けするための別個のテーブルを符号化する必要はなく、その代わりに双方の変換結合再順序付けの合成である1つのテーブルのみを符号化できる。完全なブロックのビットを再順序付けする方法は以下のように進む。領域毎に、最も相関したビット対を見つける。完全に相関したビットが既に結合されているため、残りのビットで完全に相関されたものは存在しない。しかし、いくつかのビット対は他のビット対より相関される。最も相関したビット対a,bは第1の完全なブロックのビット0及び1に再マッピングされる。最も相関したビット対をグループ化した結果、完全なブロックのハフマン木はより少ない別個の符号データを格納するのにより少ないメモリを使用するという利点を有するを有し、統計はより偏るこれにより、ハフマン符号化がより効率的になる。ランダムなビットシーケンスを含むのではなく、例えば最初の2ビットは殆どの場合が00又は11を含み、10又は01を含むものはほぼない他のビットについても同一である。ビットを再順序付けせずに、最初の2ビットは全ての種類のパターン00、01、10、11を含む。最初の2ビットを再マッピングした後、方法は、次に最も相関したビット対c,dを見つけ、それらを再マッピングして第2のブロックの最初の2ビットに格納する。方法は、次に最も相関したビット対e,fを見つけ、それらを再マッピングして第3のブロックの最初の2ビットに格納する。最後の完全なブロックに到達すると、方法は最初の完全なブロックに戻り、次に最も相関したビット対g,hを再マッピングする。いくつかの対が同一の相関性を有する場合、タイブレーカは、同一ブロックの前の対と最も相関した対すなわち、a,bと最も相関した対を選択する。アルゴリズム方法は、完全なブロック中の全てのビット対が再マッピングされるまで上記のように進む。この例において、ブロックサイズが奇数のビット数11ビットを有するため、再マッピングされていないビットが完全な各ブロックに依然として存在する。方法は、zと最も相関したビットを見つけ、それを第1のブロックに格納する。その後、Bと最も相関したビットを見つけ、それを第2のブロックに格納する。全ての完全なブロックが再マッピングされるまでこのような処理を行う。この時点で、全てのビットが完全なブロックに再マッピングされる。方法は、最後のブロックのビットを再マッピングし、完全なブロックに対して行ったように最も相関したビット対をグループ化しようとする。最後のブロックのビットを再順序付けすることは、地図のサイズを縮小することを助長できるが、以下の2つの理由により完全なブロックのビットの再順序付けほどは助長しない。完全なブロックの方が重要である。この例において、各符号は、完全なブロックに対して3つのハフマン符号を使用するが、一方、最後のブロックに対しては1つのハフマン符号しか使用しないため、完全なブロックが最後の不完全なブロックより全体の地図のサイズに寄与していることは普通であり、完全なブロックのハフマン符号化を最適化することがより有用である。最も相関したビットを全て既に選択してそれらを完全なブロックに再マッピングしたため、最後のブロックにおける再マッピングする残りのビットの相関性はより低い。従って、最後のブロックのビットのエントロピーは、完全なブロックのビットのエントロピーより高い。換言すると、最後のブロックのハフマン符号化は、完全なブロックのハフマン符号化ほど効率的ではない。尚、全ての領域の全ての完全なブロックに対して、同一のハフマン木が使用される。上記例におけるビットベクトルを符号化することにより、同一のハフマン符号を使用して全ての完全なブロックを符号化し、最終的に異なるハフマンコーデックにより最後のブロックを符号化する。方法が各ブロックの最初のビットを再マッピングする第2のブロックに進む前に第1のブロックの全てのビットを再マッピングするのではなく理由は、上記図面を見ることにより明らかである。同一のコーデックが全ての完全なブロックに使用されるため、全てのブロックに対する全ての符号を可能な限り同一にすることが望ましい。第1のブロックの全てのビット、次に第2のブロックの全てのビット等を再マッピングする場合、各ブロックは非常に異なるパターンを有する。すなわち、第1のブロックは最も相関したビットを有し、第2のブロックはより相関性の低いビットを有し、第3のブロックは更に相関性の低いビットを有する。完全なブロックの各列に対していくつかのハフマンコーデックを作成できるが、これはメモリに関して高価すぎると考えられる。ここまで概略を示した方法は、適切に動作する一方で、全ての完全なブロックに対して同一のハフマンコーデックを共有する。可能な他の最適化ページのページビットベクトルページ情報は、各ビットベクトルページの開始オフセットを見つけるために使用されるデルタフィールドを格納する。デルタフィールドは、オフセットの線形補間を使用して格納される。しかし、小さなノードIDレベル0、高速自動車道路の周囲のビットベクトルがより大きいノードIDレベル5、行先道路の周囲のビットベクトルより多くのビットを必要とするため、オフセットはそれ程線形ではない。補間が実際のオフセットを正確に予測しないため、ビットベクトルページ情報の符号化は要望される程の利点を有さない。補間を向上することにより、ビットベクトルページ情報テーブルの符号化を向上し、より効率的にすることができる。本発明のいくつかの実施形態は、1つのレベルではなく2つのレベルを有するビットベクトルページ及び可能性として領域ページを使用してもよい。データをグループ化する2n個のノードのページこれらをサブページと呼ぶは、2N個のサブページのページにグループ化される。従って、線形補間パラメータは、グローバルではなくページ毎に格納されるヘッダに。例えば指標レベル2は、サブページの最初の方で24=16個のノードをグループ化してもよく、指標1はページ中のそれらのサブページの210=1023個のノードをグループ化してもよい。線形補間は、全体のノード数ヨーロッパの西部及び中部の地図の40,000,000個のノードに対してではなく、102416=16K個のノードに対して行われるため、可変サイズオフセットの線形補間ははるかに正確になり、指標2のデルタフィールドはより小さくなる。ページが大きいメモリに適合するのに十分に小さい場合、追加の指標1のサイズは小さい。装置のメモリ内に適合可能であることは、データを使用する経路指定を遅くしないため有利である。平均ページサイズをヘッダに格納するのではなく、平均ページサイズは指標1のテーブルの全てのエントリに対して格納される。ビットベクトルページのインタリーブ上述したように、ビットベクトルが重要な道路多くの非自明なフラグ及びあまり重要でない道路多くの自明なフラグに対して異なるため、ページオフセットに対する補間は正確でない。補間をより線形にする1つの単純な方法は、種々のネットワークレベルのページをインタリーブすることであり、これは本発明の実施形態において使用されてもよい。上記実施形態において説明したファイルは以下のページを格納する。01234n-3n-2n-1より効率的である可能性のある他の実施形態において、以下のようにインタリーブして格納できる。0n-11n-22n-33n-4ページxにアクセスする例えば、経路計画アプリケーションによりために、ページはページx’をロードすることによりアクセスされる。x’=2xxが偶数の場合x’=2x-n-1xが奇数の場合このような一実施形態は、ページ毎に数ビットずつ指標付けのサイズを縮小するため有利である。しかし、データは、キャッシュするためにより不適切にグループ化される可能性があるため、データアクセスを遅くする可能性があるファイルシステムキャッシュにおいてヒット数が少なくなる。全てのノードに対する領域IDの非格納領域IDは、末端のノード及び2つの連結道路セグメントを有するノードに対して格納される必要はない。これらのノードは経路指定に対して無視される。これらのノードのうちの1つに行くことは、近傍の決定ノードに行くことに変換される。ページレベル及び/又はノードレベルにおける追加の情報の格納地図データを見ると、自明なビットベクトル000...000又は111...111のみを含むビットベクトルページが多く存在する。いくつかの実施形態は、ページに印をつけるためにそれらページ毎に1ビットを格納してもよく、そのビットベクトルが000...000であるか又は111...111であるかを示すためにビットベクトル毎に単一ビットのみ必要とするため、ビットベクトルをそれらのページに格納することはより効率的になる。これは、自明なビットベクトルのみを含むページのサイズを縮小するだけでなく、非自明なビットベクトルを有するページに対してビットベクトル符号のハフマン木をより適切に最適化するこれらの符号の頻度のパーセント値が非常に増加するため、非自明なベクトルを示すためのビット数は減少される。より精細なネットワークレベル例えば、レベル3において、殆どのページは自明なビットベクトルのみを含むため、約半分のページにおいてページ毎に1つのビットベクトルのみが存在する可能性がある。決定ノードのビットベクトルのみの格納上述したように、いくつかの実施形態は、1つ又は2つの連結道路セグメントを有するノードに対するビットベクトルを格納しなくてもよい。しかし、他の実施形態は、より積極的であってもよく、決定ノードの周囲のビットベクトルのみを格納する概念を一般化してもよい。決定ノード及び決定道路セグメントの概念は、地図データの符号化に関して利点を有するため導入される。すなわち、次に説明するように、ビットベクトルは非決定道路セグメントに対して符号化される必要はない。決定ノードは、ノードを出るUターンをせずに複数の選択肢があるように経路指定するための進入道路セグメントが存在するノードである。非決定ノードは、決定ノードでないノードである。従って、経路指定の出発地に関係なく、ノードを出る出口が常に1つのみ存在する。決定道路セグメントは、決定ノードを出るのに合法な道路セグメントである。非決定道路セグメントは、決定道路セグメントでない道路セグメントである。全ての決定道路セグメントは、決定ノードの周囲にある。しかし、決定ノードの周囲にある全ての道路セグメントが決定道路セグメントではない。非決定ノードの周囲にある全ての道路セグメントは非決定道路セグメントである。ビットベクトルは、決定道路セグメントに対してのみ符号化される。データを使用する経路決定技術が道路セグメントに既に存在する情報から判定できるため、ビットベクトルは、非決定道路セグメントに対して黙示的である000...000又は111...111。ノードが決定ノードであるかを判定する方法は緩和できる基準は以下の通りである。isDecisionNode=lineCount>=3lineGoingOutCount>=2式中、lineCountは、経路指定不可能な線の種類鉄道、基準線を無視し、双方向に閉じた線を無視し、且つ通り抜け禁止道路住宅エリアを無視するノードに連結された線の合計である。lineGoingOutCountは、ノードを出るために利用するのに合法であるノードに連結された線の数である。ノードを出るためにある道路セグメントを利用するのが合法か否かは、以下の道路セグメント属性に依存する。道路セグメントの種類鉄道基準線は常に違法である道路の順方向/逆方向の流れ道路セグメントフラグに格納される道路セグメントフラグの通り抜け禁止属性通り抜け禁止道路セグメントはいずれのビットベクトルも有さないいくつかの実施形態において、非決定道路セグメントを無視することは、約40の道路セグメントを廃棄できる。このパーセント値は、地図に関係なく非常に安定していることが分かっている。自明なビットベクトルを主に除去するため、ビットベクトルの40の符号化を回避することは利点であるが、節約される地図のサイズは40未満である。3つ未満の連結道路セグメントを有するノードダミーノードの周囲のビットベクトルを除去することにより、非自明なビットベクトルが除去されるため、このカテゴリの非決定道路セグメントに対する地図のサイズの節約は非決定道路セグメントに対する節約より大きい。一方、フィルタリングは、復号器地図を使用する経路指定方法等が道路セグメントの種類及び線の道路セグメントフラグを復号化し且つ黙示的であるビットベクトルを計算するためにそれらに論理を適用することを必要とする。これは、処理を遅くする可能性がある。理論上、実施形態は、退出道路セグメントが合法であるかを決定するために操作すなわち、右左折制限に着目するが、そのような技術は複雑さを増す。操作を無視することは、実施形態が厳密に必要な数より多くのビットベクトルを符号化してもよいが方法の単純化が達成されることを意味する。非決定ノードの例a--<->--b--<->--cこの例において、bは双方向にナビゲート可能である2つの道路セグメントに連結される。<=2個の連結道路セグメントが存在するため、bは決定ノードではない。従って、ノードbを出る双方の道路セグメントのビットベクトルは符号化されない。復号器は、それらを111...111に黙示的に設定できる。a-->--b--<->--c|^|dこの例における矢印>は、フローの合法な方向を示す。出口が1つのみ存在するため、bは決定ブロックではない。従って、bの周囲のいずれの道路セグメントもビットベクトルを必要としない。ノードbを出る道路セグメントb->cに対するビットベクトルは符号化されず、黙示的に111...111となる。bを出る違法な道路セグメントに対するビットベクトルも符号化されず、黙示的に000...000となる。決定ノードの例a--<->--b--<->--c|^|dbは、dから来る場合に選択肢があるため決定ノードである。すなわち、経路指定はa又はcに向かって継続可能である。尚、この例において、aから来る場合、選択肢はない。すなわち、経路指定はcに向かってのみ継続可能である。しかし、ノードbは、dから来る場合に少なくとも選択肢があるため依然として決定ノードである。従って、ビットベクトルは、ノードbの周囲の2つの決定道路セグメントに対して格納されるべきである。道路セグメントb->a及び道路セグメントb->aが決定道路セグメントであるため、ビットベクトルはこれらの道路セグメントに対して格納される。交通の逆方向/順方向の流れによると道路セグメントb->dを利用するのは違法であるため、ビットベクトルはこの道路セグメントに対して格納されない。これは、黙示的に000...000である。ビットベクトルの論理和ノードが3つの連結道路セグメントを有し、最初の2つの復号化道路セグメントが以下のビットベクトルを有すると仮定する。0000000000000000000000000000000000000000第3のビットベクトルは、以下の通りであるため符号化される必要はない。11111111111111111111これは、ノードaの周囲の道路セグメントのビットベクトルがこの順序で現れる場合にのみ動作可能である。すなわち、全てのビットベクトルが000...000であり、最後のビットベクトルが111...111である。実際には、これはより精細なレベル例えば、レベル3のネットワーク殆どの道路セグメントが存在するにおいて非常に頻繁に現れると考えられる。最初の2つのビットベクトルは以下の通りとする。0000000000000000011000000000000000000010第3のビットベクトルは、未知であり且つ何らかの方法で符号化される必要がある2ビット以外の全てのビットを1に設定できる。111111111111111111上記例において、殆どのビットが既知であるため、ビットベクトル全体を符号化するより効率的に2つの未知のビットを符号化するためにこの情報を使用できるべきである。従って、この例において、2ビットを符号化すればよい。このプロパティを使用する可能な高速復号化方式は、道路セグメントの全ての先のビットベクトルの論理和をとることにより現在のノードの道路セグメントの全ての復号化ビットベクトルのビットマスクを計算することである。上記と同一の例を使用して、ノードが3つの連結道路セグメントを有する場合及び先の2つの道路セグメントが以下のビットベクトルを有する場合、0000000000000000011000000000000000000010ORビットマスクは以下の通りである。00000000000000000110ノードの周囲の符号化する第3の最後のビットベクトルを以下の通りとする。11111111111111111001極めて稀な11111111111111111001のハフマン符号を符号化する代わりに、符号器は、以下の場合に他のあらゆる符号otherCodeを自由に符号化できる。value_to_encode=~bitMask|otherCodeこの例において、otherCode=00000000000000000000は、以下が成り立つために適格である。value_to_encode=11111111111111111001=~00000000000000000110|0000000000000000000000000000000000000000の頻度がより高いため、00000000000000000000を符号化することは、11111111111111111001を符号化するより非常に効率的である。復号化は、ビットベクトルを復号化する時は常にビットマスク又は動作を計算し且つ最後に復号化されたビットベクトルにビットマスクを適用すればよいため、復号化は速い。実際のビットベクトル=ビットマスク復号化ビットベクトル=~0000000000000000011000000000000000000000=11111111111111111001この最適化は、ノードの周囲の道路セグメントが最後の領域において殆どが1であるビットベクトルの道路セグメントを有するように格納される場合に適切に動作する。しかし、これは困難である。ノードの周囲の道路セグメントの格納は、ビットベクトルの計算前に行われる再符号化するためにビットベクトル情報を帰納的に使用しない限り。道路セグメントは道路名で既にソートされている。道路名が特定される場合、ノードの周囲の道路セグメントをソートできる。ネットワークレベルの使用領域のレベルに加えて、地図データ内の道路セグメントは道路セグメントレベルに従って分類される。出発ノードの周囲において道路セグメントネットワークレベルとビットベクトルとの間には強い相関性がある。すなわち、一般に別の領域までの経路指定は、高速自動車道路等の高いレベルの道路セグメントネットワークを利用するのを好む。最も重要な道路セグメントネットワークレベルは、高速自動車道路レベルである可能性が高く、これはレベル1であってもよい。以下の例は、異なるネットワークレベルにおける道路セグメントとの交差点を示す。4||1=======2=======3線2->1は、ネットワーク4重要にある。線2->3はネットワーク5あまり重要でないにある。線2->3はネットワーク5あまり重要でないにある。ビットパターンは以下のようになる可能性が高い。212334000000000000。精細ネットワークレベルのノードに対するビットベクトルの非格納経路指定は、目的地又は出発地に近接する場所以外ではネットワークレベル5等の非重要道路セグメントネットワークレベルをほぼ通過しない。従って、レベル5のビットベクトルを格納しないことが可能であり、従ってレベル5の道路セグメント数が多くても経路指定への影響は最小である。殆どの場合の経路指定は、いくつかの更なる重要な道路セグメントネットワークレベルに迅速に到着するため、経路の開始又は終了において最も重要でないネットワークレベルの道路セグメントを殆ど探索しない。これらのノードに関する探索加速データは、最も重要でないネットワークレベルに戻るナビゲートセグメントをスキップし且つより重要なネットワークレベルに通じるか又は入るナビゲートセグメントを使用するようにルータにほぼ常に伝える。目的地が依然として遠い場合に最も重要なネットワークレベルが使用されるため、このことは、そのネットワークレベルにおいて当てはまる。最も重要でない道路セグメント例えば、レベル5におけるビットベクトルをドロップすることに加えて、そのネットワークにおいて領域IDを符号化しないことも可能である。ビットベクトルのいくつかの0の1への変換これは、不可逆圧縮方式である。ビットベクトルが1つの0だけ又は可能性として小さい閾値未満を含む場合、以下の結果すなわち、その道路セグメントを最速経路の一部になるように設定するが得られる場合はそれを1に変換できてもよい。自明なビットベクトル111...111自明なビットベクトルは非自明なビットベクトルよりコンパクトに符号化されるため現在のビットベクトルページの履歴で既に見つけられたビットベクトルより効率的に符号化されるためビットベクトルにおいて0を1に変換することは経路指定結果に影響を及ぼさず、経路指定がより多くの道路セグメントを考慮するようにすることにより遅くなるだけである最速経路の一部になるように設定されるため。しかし、特に経路指定の速度に関して性能への悪影響が小さく、地図の節約が大きい場合、本発明のいくつかの実施形態はこの方法を採用してもよい。経路指定図18は、従来のA探索方法により探索された複数の道路セグメントと共に開始ノード1602及び行先ノード1604を有し且つあるエリアを範囲に含む地図1600を示す。選択された経路を点線1606で示す。図19は、図18の地図と同一エリアを範囲に含み且つ同一の開始ノード1602及び行先ノード1604を示す地図1650を示す。図19は、図18の経路を生成するために使用したのと同一の道路ネットワーク及び基準例えば、双方とも自動車で移動され、最小にするコスト関数として速度を使用することを要求するを利用した本発明の一実施形態を使用して探索された道路を強調表示する。方法により選択された経路は、点線1606で示され、その道路セグメントは図18で算出されたものと同一である。従って、本発明の実施形態により算出された経路は、いわゆる数学的に正確であり、最小になるように選択された所定のコストモデルに関して最善/最適な経路を見つける。従って、本発明の実施形態により探索された道路セグメントは、従来技術と比較して非常に少ないことが明らかである。本発明の実施形態の方法は、従来のA方法より高速であり、一般にははるかに高速である。尚、経路1606が目的地1604に近づくと開始時と比較してより多くの経路が探索される。すなわち、経路1606が地点1652を越えて進む場合、最低コスト経路以外に道路が探索される。この1つの説明としては、方法が地点1652においてレベル0領域からレベル1領域に切り替わったからである。目的地1604付近で更なる道路セグメントが探索されることが更に分かるだろう。ここでも、これは、経路計画方法がこの付近でレベル1からレベル2に切り替わったことを指摘することにより説明できる。従って、長い範囲での経路指定の場合、一般に最速経路は1つのみ存在する。しかし、方法がより精細なレベルに切り替わると例えば、レベル0から1に、最低コストとして印がつけられ且つ従って探索される必要がある経路が2つ以上存在してもよい。地図データが作成され、ビットベクトルが算出及び格納されると、2つの地点間の経路を算出するのに使用される。図20は、ネットワークが経路計画アプリケーションにより探索される従来のA方法を示す。ここで、ノードにおいて更に探索する道路セグメントに関する決定が行われる。これを達成するために、次のノードまで移動するためのコストは、次のノードから目的地まで移動するための推定されたコストに追加される。所定のノードからの最小コストを有するパスは、更に探索される。方法が進み且つ各繰り返しにおいて最低コストが考慮されるため、方法はそれまでに発生したコストの合計を保持する。例えば、ノードBから開始すると、双方のノードC及びDは開始ノードであるBから2コスト単位だけ離れていることが分かる。しかし、ノードDからノードFに到達するための推定コストは3単位であり、ノードCからノードFに到達するための推定コストは5単位である。従って、A方法は、次のノードまでのコスト目的地までの推定コストがノードDまでの道路セグメントに対してより少ないためすなわち、BC=25=7であるが、BD=23=5である、ノードCへの経路よりノードDへの経路を好んで探索する。経路計画が本発明の実施形態のビットベクトルを使用して実行されることを考慮すると、道路セグメント毎のビットすなわち、図10の列704は、行先領域までの最低コスト経路の一部となる候補である道路セグメントを特定する。従って、図20に関連して説明したA方法は修正され、図21に示した方法が得られる。一般に経路計画は、図21に関連して説明するようなビットベクトルを使用して実行される。しかし、本発明のいくつかの実施形態は、種々の状況下において経路計画がA又は他の従来の方法にフォールバックすることを可能にしてもよい。種々の実施形態は、以下のうちのいずれかを利用してもよい。すなわち、ビットベクトル情報が失われていることこれにより、ビットベクトルがない場合でもシステムは機能できる、コスト関数が使用されること、ビットベクトルが算出されたコスト関数以外の経路指定一般に最速経路であるが必ずしも最速経路である必要はない、ユーザがビットベクトルを事前計算するのに使用された基準と異なる基準を指定すること例えば、ユーザは高速自動車道路を回避したい、乗り物の種類がビットベクトルの事前計算に使用されたものと異なる例えば、ユーザは自動車ではなく徒歩であること、及び経路が閾値の長さを下回ること例えば、経路の開始点及び終了点が同一領域内にあるである。図20と比較して、2つの追加の数字1800、1801を図21に示す。更に領域は、図21において破線1802及び1804により示される。11800は、道路セグメントBDがノードBから目的地ノードが位置する領域までの少なくとも1つのコスト関数に対する1つの低コスト経路の一部であることを示す他で説明するように、更に他の低コスト経路が存在してもよい。01801は、道路セグメントBCがノードBから目的地ノードが位置する領域までのいずれの低コスト経路の一部でないことを示す。従って、ノードAから開始すると、本発明の実施形態は、上記で概略を示したAを使用してAからノードを探索する。しかし、ノードBに到達すると、道路セグメントBDのみが最低コスト経路の一部である可能性があることの明示的な表記があるため、探索を更に使用する必要はない。従って、A方法が使用され、最低コストパスを見つけると、次にビットベクトル内の関連ビットを見ることにより最低コスト経路を選択する。しかし、種々の最低コストパスが種々の時間における及び/又は種々のコスト関数に対する一対の領域の間に存在する場合、最低コストデータは、その対の領域間で2つ以上の最低コストパスを特定してもよい。従って、例えば道路セグメントBD及びBCに対する数字1800及び1801が、各道路セグメントが特定の時間において最低コストパスの一部であることを示す値1を有する場合、開始ノードと目的地ノードとの間出発地と目的地との間の経路指定は、2つ以上の最低コストパスを見つけてもよく、競合する最低コストパス間で判定する必要がある。本実施形態において、ビットベクトルは、各道路セグメントが最低コストパスの一部である時間を特定しない。そのため、経路指定アルゴリズムは、パスの区分を移動する時間及びコスト関数に基づいて双方の可能な最低コストパスに対してコスト解析を実行する。この時間は、出発地/開始ノードからの出発時間から判定されてもよい。コスト関数はユーザによる選択から判定され、例えばユーザは、全ての経路指定が選択に従って判定されるようなコスト関数/基準を図32に示すような設定メニューから選択してもよい。例えばコスト関数/基準は、最短距離、最短移動時間、最安環境的な影響に関して、最小の使用燃料、最小の生成CO2、1つ以上の特定の道路の種類の回避又は好み等のうちの1つ以上であってもよい。あるいは、ユーザは特定の経路の計画を要求する時にコスト関数/基準を選択してもよい。本発明のいくつかの実施形態は、電子地図のユーザがその電子地図内の誤りを強調表示することを可能にしてもよい。特にユーザはブロックされているとして道路セグメントに印をつけることができすなわち、ベクトルがブロックされていることを示せる、これは交通事象と同一の影響を交通の流れに与える。従って、ブロックされた道路セグメントを表すデータは、交通事象の詳細を示すデータと同様に考慮されてもよい。あるいは又はそれに加えて、実施形態は、道路のブロックが解除されたこと又は新しい道路ができたこと等をユーザが示せるようにしてもよい。これらのいずれも、電子地図内に新しいベクトルを作成するものと考えられてもよい。一般に例えば図10に示すような経路指定加速データが前処理により生成されるため、経路指定加速データが新しいベクトルを参照しないために経路指定加速データを利用する経路指定方法はそのような新しいベクトルを考慮しない。ユーザは、タッチスクリーン又は他のボタン、スイッチ等を使用してPND上に直接入力する手段、あるいは音声命令による手段等のあらゆる適切な手段を使用して訂正を電子地図に入力してもよい。上述したように、ユーザ特定のナビゲーション装置のユーザであるか又はMapShare登録商標等の技術により識別された別のユーザであるかに関らないは、電子地図内に新しいベクトルすなわち、以前に電子地図の一部ではなかったベクトルが存在することを示せる。しかし、経路指定加速データが前処理により生成されるため、それらの新しいベクトルは経路の算出において考慮されない。従って、新しいベクトルが電子地図に追加されることを可能にする本発明の実施形態は、新しいベクトルが地図の各領域までの経路指定加速データにより示されるような最低コスト経路の一部であることを反映するように経路指定加速データを修正してもよい。すなわち、そのベクトルに対する全てのビットが、ベクトルが電子地図の各領域までの最低コスト経路の一部であったことを示す1に設定されるように、新しい各ベクトルに対する行は設定される。これは実際には当てはならないことが当業者には理解され、また、このようにビットを設定することにより、例えば出発地と目的地との間の経路を生成する時に経路の算出において新しいベクトルを考慮することになることが当業者には理解されるだろう。図10aに示すように、セグメント中の推定移動速度がどのように計時変化するかの速度プロファイルは各セグメントと関連付けられる。これらの速度プロファイルから、関連する時間における推定速度が判定され、これは、その時間にその道路セグメントを移動するためのコストを判定するために使用される。各最低コストパスの道路セグメントを移動するためのコストを合計することにより、各最低コストパスに対するコストが判定される。ナビゲーション装置は、その時間に対する最低コストを有する最低コストパスを経路に選択してもよい。決定された経路はディスプレイ206に表示されてもよい。図23は、どのように地図データ上に経路が表示されうるかの一例を示す。本実施形態において、ディスプレイは、経路の複数のナビゲート可能セグメントの少なくともいくつかにおける予測速度の指標を含んで表示する。本実施形態によれば、それらの指標は、経路のカラーリング、及び、経路に沿った予測速度を示す地図の画像の端における時間バー2000を含む。例えば、ナビゲート可能セグメントは、予測速度が第1の閾値を上回る場合には第1カラー、例えば緑でカラーリングされ、予測速度が第2の閾値を下回る場合には第2カラー、例えば赤でカラーリングされる。経路を決定する代替の方法を、図10a、図24乃至図31を参照して以下で説明する。特定の時間での経路に対するコストを判定するよりもむしろ、時間と共に変化するコストを示すコストプロファイルが判定されうる。本実施形態において、各ナビゲート可能セグメントに対する速度プロファイルの単一の値よりも複数の値が複数の経路に対するコストプロファイルを決定するために使用される。例えば、図21を参照すると、各道路セグメントBC、CEに対する単一値を有するよりもむしろ、各経路におけるコストが時間と共にどのようにコスト変化が起こるかを示す分布である。それらのコスト分布は、経路に対するコストプロファイルを決定するために加算される。ツリーを通じてコストプロファイルの伝播は図10aにも示す。本実施形態において、各ナビゲート可能セグメントは、各時間に対する12時間ビンbinを含んで関連付けられた速度プロファイルを有し、各時間ビンは、当該時間におけるナビゲート可能セグメントを通じて移動する際の予測速度を含む。各ビンの予測速度に対するコストが決定され、各関連ビンに対するコストがコストプロファイルを決定するために経路の複数のナビゲート可能セグメントにおいて加算される。各セグメントにおいて加算される値は、ユーザが各ナビゲート可能セグメントに到達することを目的とする場合に依存して変更されるであろう、各セグメントに沿って移動する際の期待時間と同じ時間となるビンからでなくともよい。例えば、ナビゲート可能セグメントBDに沿った移動でユーザが5分掛かると予想され、したがって、セグメントBD、DFを加算したビン値は、5分ごとに分割されたビン値であってもよく、つまり、BCにおける時間ビン値Tは、DFにおける時間ビン値T5に加えられる。最小コストパスの一部であるナビゲート可能セグメントのみが、最小コストパスでないナビゲート可能セグメントと競合する中で探索される。したがって、考慮すべきパスBDF登録商標及びパスBCEFに関して、両方のパスが最小コストパスとして最小コストデータによって特定されなければならない。両方のパスBDF登録商標及びパスBCEFが種々の時間において最小コストパスであり、その後、2つの経路が交差する場合、BDF登録商標及びBCEFのコストプロファイルは、程度degree及び更に伝播される可能性を維持することを必要とする。これを達成するために、プロセッサは、2つのコストプロファイルC1及びC2をお互いの上に重ね、上限分布UB実線で示す及び下限分布LB点線で示すを決定する計算を実行する。これは、図30及び図31に示す。UB及びLB分布は、決定される各経路に対する最大及び最小コストプロファイルを許容する他の伝播に対して使用される。上限分布及び下限分布のさらなる伝播は、それらのプロファイルへ追加される次のナビゲート可能な経路に対するコスト値で同様に発生する。探索した経路が分岐し、その後、ノードFのような後のノードで再び交差する場合、その後、各入力パスにおける2つの上限プロファイル及び2つの下限プロファイルが、単一の新たな上限プロファイルを決定するために2つの上限プロファイルを重ねることによって、かつ、単一の新たな下限プロファイルを決定するために2つの下限プロファイルを重ねることによって、再び処理される。このように、プロファイル数の増加は、経路を決定するために必要な時間やメモリの容量PNDに限定されるメモリのようにを必要以上に増大させないレベルに維持される。他の実施形態において、上限プロファイル及び下限プロファイルのいずれか1つのみが経路に沿ったさらなる伝播に対して維持されるのみである。他の実施形態において、2つの入力プロファイルincomingprofileの平均は経路に沿ったさらなる伝播に対して平均したプロファイルとなるように決定される。コストプロファイルが全体経路に対して決定されると、上限プロファイル又は下限プロファイルの1つが最終的なプロファイルとして選択される。当該プロファイルは、以下で説明するように、ナビゲーション装置上の表示を決定するために使用される。図24及び図25は、コストプロファイルの複数の値における道程が表示されている。図24において、所定時間毎に、本実施形態では15分毎に区分された個別の出発時間における時間バーとともに、コストファイルが始点出発地から出発した時間と、行先目的地への到達時間とが表示された様子を示す。図23の時間バー2000のように、各時間バーは、経路の異なる部分に沿って予測速度を示すように符号化された色で表示される。矢印2001,2002は、ユーザによって選択されると、より早い開始時間又はより遅い開始時間における出発時間、到着時間及び時間バーを表示するように提供される左矢印2001を選択するとより早い開始時間が表示され、右矢印2002を選択するとより遅い開始時間が表示される。。時間バーを選択すると、図23に示すように、ディスプレイには選択された開始時間における表示が行われる。図25において、コストプロファイルは設定した期間における、例えば、168時間1週間と同等の期間における連続したグラフとして表示される。このグラフは、当該コストプロファイルを形成するのに寄与する始点から行先までの経路を示す地図とともに表示される。グラフ及び経路は、ユーザが当該経路をいつ使用するかを決定できるようにカラーコード化実線及び点線で表示するようにされて表示される。例えば、7時40分と9時15分との間のグラフは、破線2003が点線2004の第1部分よりむしろ続くべきである経路の開始をを示すように色づけされる。そのような表示は、ユーザが容易に始点と行先の間の移動コストがどのように計時変化するかや、当該計時変化が経路にどのように影響するかを容易に参照することを許容する。図26乃至図28は代替の実施形態を示す。本実施形態では、コストプロファイルは、上述したように決定されものの、ユーザが指定された移動時間において決定された経路の画像のみが表示されるのみである。しかし、表示した経路が適用可能な日時を示すボックス2010が表示される。日時の両方の端に提供される矢印が選択されると、日時の何れかを変更した、決定した経路を示す地図データの画像が表示される。日時の何れかの変更は、経路の変化をもたらし、経路の移動時間や移動する距離の変化とともに、新たな経路を表示するように表示が更新される。それらの更新した表示の例が図27及び図28に示される。表示の更新は、リアルタイム例えば、ミリ秒のオーダで発生し、例えば1000ミリ秒よりも短く、好ましくは500みりびょうよりも短い時間で行われる。そのような高速な再計算時間は、予め処理した最低コストデータの使用を通じてか、それらの他の時間が既にプロファイル探索を通じて決定されている経路であるか、の何れかによって達成されうる。図29は、プロファイル探索を使用するナビゲーション装置の他の機能を示す。本実施形態において、移動時間、例えば、開始時間の選択に関し、ナビゲーション装置のプロセッサは、当該時間での移動コストを、移動時間、例えば、移動時間であれば30分早い時間でのウィンドウアラウンドにおけるコストプロファイルの値と比較してもよい。プロセッサがより低いコストを有するウィンドウ内の移動時間を発見すると、その後、プロセッサは、より良い結果を与える移動時間の指標を表示させる。例えば、図示した実施形態において、Note2015には、ユーザが15分遅く出発すると、移動時間がこの例では10分短縮することを当該ユーザに知らせる旨の表示が行われている。ここまで説明した経路指定を実行するために、ビットベクトル情報は、復号化処理を使用して図11~図13に関連して説明した符号化副ファイルから取得される。上述した前処理の出力は以下を含む。殆どのノードに対する階層領域の割り当てこれらのノードにおける退出道路セグメントに対するビットベクトルの割り当て地図のロード一貫性検査地図データがロードされる場合、副ファイルの集合は地図ディレクトリに存在すべきであり、存在しない場合、復号器は経路探索が探索加速データなしで実行されるように探索加速データを非アクティブにする。データ完全性を保証するのを助長するいくつかの検査がある。これを一覧表示する。副ファイルは命名規則に従う。レベルの数は副ファイルの数により与えられるが、各副ファイルのヘッダにも格納され、副ファイルの数に等しい。各副ファイルは、副ファイル名で指定されたレベルと同一の各レベルの領域数を格納する。更に副ファイルは、全ての副ファイルに対して同一であるべき以下の情報を格納する。副ファイルのバージョンビットベクトルページ以下に説明する毎のノード数各副ファイルには、以下を特定するチェックサムが存在する。全体の特定の副ファイル集合全体の地図これらは、所定の電子地図に対して関連付けられた副ファイルに対して正確であるべきである。上記検査のいずれかが失敗した場合、探索加速データプロパティはこの地図に対してアクティブにされない。メモリにロードされるデータ構造復号器は、外部メモリの実現例の副ファイルを読み出す。これは、ビットベクトル副ファイルのコンテンツがメモリに完全にロードされず、必要に応じてのみ読み出されることを意味する。しかし、ある一般的なデータは最初にメモリにロードされ、地図がロードされる限りそこに保持される。ヘッダ情報各副ファイルは、図8~図10に関連して上述したデータを含むヘッダセクションで開始する。この情報は、副ファイル毎にメモリに格納される。ハフマン木の定義副ファイルは、いくつかのハフマン木の定義を含む。ハフマン木の各定義は、特定のハフマン符号化の完全な記述を与え、副ファイルビットストリームの一部を元のデータに復号化するためにすなわち、副ファイルのビットシーケンスを数字又は他のある特定の値に復号化するために後で使用される。以下のハフマン木の定義は、各副ファイルから読み出され且つメモリに保持される。各ノードにおいて道路セグメント数を復号化するためのハフマン木。符号化された道路セグメント数は、基礎となる地図の道路セグメント数より少ない。尚、復号器は基礎となる地図とは無関係である。すなわち、地図を読み出す必要はない。このハフマン木は、レベル0の副ファイルにのみ格納される。ページ符号を復号化するためのハフマン木以下に説明する。ビットベクトルブロックを復号化するためのいくつかのハフマン木。木の定義数は、副ファイルヘッダに格納されるような正規のビットベクトルのブロックの長さにより与えられる。これはブロックの長さ-1に等しい。道路セグメントに対するビットベクトルのビット列全体はブロックに分割される。ビットベクトルのビット列の長さが正規のブロックの長さの倍数でない場合、最終的なブロックはより短い。2~正規のブロックの長さまでのブロックの長さ毎に1つのハフマン木が存在する。長さ1のブロックの場合、これは単に1ビットであり、直接格納されるため、ハフマン木は使用されない。ビットベクトルに対して復号化方法を選択するためのいくつかのハフマン木。これらの木の数はヘッダで指定される。その使用については以下に説明する。近傍リスト最も精細なレベル以外の各レベルにおいて、副ファイルは近傍リストを符号化する。レベルkにおける領域の近傍リストは、レベルk領域の近傍領域と呼ばれる0個以上のレベルk1領域のリストである。レベルkの副ファイルの近傍リストセクションは以下の2つの部分を有する。第1の部分は、各レベルkサブ領域に対する近傍領域の数を含む。例えばk=1、グローバルレベル0において4000個の領域があり、各グローバル領域が10個のレベル1領域に細分される場合、レベル1の副ファイルは400010個のレベル1サブ領域を含む。これらの各々に対して、個別の近傍リストレベル2領域から成るの長さが与えられる。第2の部分は、長さが第1の部分から既知である実際の近傍リストを含む。各近傍リストはレベルk1サブ領域のリストである。領域再マッピングテーブル副ファイルは、例えば結合及び再順序付け等により圧縮形式でビットベクトルを格納する。レベルkの副ファイルは、ブロックにより符号化されたビットベクトルを伸張するのに使用される領域再マッピングテーブルを有する。これは以下の2つの部分から成る。第1の部分は、レベルkサブ領域により指標をつけられる配列である。レベルkのサブ領域毎に、圧縮ビットベクトルの長さを含む。これは、ビットベクトルがブロックにより符号化される各サブ領域におけるノードの退出道路セグメントにとって有意義である。第2の部分は、1非圧縮ビットベクトルのビット位置及び2レベルkサブ領域により指標をつけられた2次元配列である。配列のエントリは、ブロックにより読み出された非圧縮ビット列の所定のビット位置に対する圧縮ビットベクトルのビット位置を指定する。尚、第1の部分のみがメモリに保持される。第2の部分は、大きいため、復号化中に要望に応じてのみ使用される。現時点で、領域再マッピングテーブルはグローバルレベルの副ファイルk=0にのみ格納される。経路クエリの開始復号器は、出発位置から行先ノードの集合までの経路探索を加速するために使用される。目的地が2つ以上のノードから成る一例は、全体の道路の広がりが目的地として使用される場合である。行先ノードは1つ以上の目標領域の集合を規定する。尚、目標領域は領域IDのシーケンスであり、各領域IDは各セグメントレベルに対するものであり、レベル0から開始する。新しい探索の各々の開始時、目標領域の集合は、先の目標領域集合をクリアし且つ新しい行先ノードを復号器に渡すことにより構築される。復号器は、重複のない目標領域のリストを判定する。所定のノードの領域を見つける機構は探索と同一であり、詳細については以下を参照。経路探索中のノードの走査残りの説明は、目標領域の集合が設定されたと仮定する。復号器の特徴は、道路ネットワークのノードIDを仮定すると、このノードを出る道路セグメントにわたり指標をつけられるビット配列このノードに対するビットベクトル及び所定の目標領域を返す関数である。ノード及びあるノードにおける道路セグメントの順序付けは、地図により規定される。ビット値が0である場合は必ず、これは対応する道路セグメントが探索中に無視されることを意味する。通常、これにより探索空間は大きく減少され、従って探索の実行時間が短縮される。少数のノードの場合、領域情報もビットベクトルデータも副ファイルに格納されない。これらのノードに対して、復号器は全てのビットが1であるビット列を返す。これにより、経路探索がこのノードにおける道路セグメントをスキップすることを防止する。復号器は、これが所定のノードに当てはまるかを示すブールクエリ関数を有する。更に所定のノードが先に固定された目標領域の1つに配置されるかを示すブールクエリ関数が存在する。目標領域のノードに対して復号器により返されたビットベクトルは、ここでも全てのビットが1であるビット列である。これらのブールクエリ関数は経路探索における最適化のために使用される。副ファイル形式に従って、所定のノードに対するビットベクトルデータはいくつかのステップで復号化される。各副ファイルにおいて、領域及びビットベクトル情報は、いわゆるページに編成される。ページ毎のノード数は2の既定の累乗例えば、16であり、副ファイル集合の副ファイル毎に同一である。これは、所定のノードIDに対してビットベクトルページのページ指標が単純なビットシフトにより計算されることを意味する。ノードの情報は、ノードIDで連続して格納される。所定のノードに対するページオフセットの検索ページ毎の平均バイト数は、副ファイル毎に副ファイルのヘッダに格納される。これは、ページ指標を平均サイズと乗算することによりページのバイトオフセットを近似するために使用される。修正項は、ページ指標により指標をつけられたテーブルに格納される。このテーブルは、副ファイルの別個のセクションに格納される。ページがクエリされると、修正項は、テーブルでルックアップされ且つ近似ページオフセットに加算され、それにより副ファイルにおけるページの位置が与えられる。ページの復号化キャッシュページが初めてクエリされる場合、ページのノードに対するビットベクトル列は復号化され固定の目標領域集合に関して且つキャッシュされる。次に同一ページのノードに対してデータがクエリされると、キャッシュされたデータはいずれの副ファイルにもアクセスせずに使用される。復号化されたビットベクトルのビット列の特別なマーカビットは、ノードが非情報ノードであるかを記憶するために使用される。ページ符号いわゆるページ符号ビットは、ページの全てのノードが同一の領域IDを有するかをページ毎に指定する。ページ符号はレベル毎に1ビットを含むが、全てのビットは、レベル0の副ファイルのページ開始時にのみ共通のハフマンシンボルとして格納される。退出道路セグメント数の復号化上述したように、各ページは固定のノード数に対する情報を含む。このノード数は、各副ファイルのヘッダに格納される。ページの開始時又はレベル0の場合はページ符号の後、ページはページの各ノードに対する退出道路セグメント数を一覧表示する。退出道路セグメント数が0である場合は常に、これは対応するノードに対して情報が全く格納されていないことを意味する。ページが復号化される間、数字は一次配列に格納される。領域の復号化道路セグメント数セクションの後、領域セクションが続く。ノードの領域は、レベル毎に1つである領域IDのシーケンスにより与えられる。特定のレベルの領域IDは、対応する副ファイルに格納される。復号器は、ページの全てのノードに対して全てのレベルの領域を読み出す。ノードに対して情報が格納されていない場合すなわち、ノードの道路セグメント数が0である場合、領域情報は空のままである。復号器は、0より大きい道路セグメント数を有する第1のノードに対する領域IDシーケンスを読み出す。全ての領域IDが所定のレベルで同一であるとそのレベルのページ符号が指定する場合、そのレベルにおいて、同一の領域IDが全てのノードに対して設定される。指定しない場合、対応するレベルの領域IDが正の道路セグメント数の全てのノードに対して読み出される。この処理の終了時、復号器はページの全てのノードに対する完全な領域IDシーケンスでテーブルを埋めているいくつかのシーケンスは空であってもよい。ビットベクトルの復号化関連するビット位置の集合の検索所定のノード及び目標領域に対して、特定のレベルの特定のビットは、そのノードを出る道路セグメントに対するビットベクトルのビットの値を判定する。2つ以上の目標領域がある場合、結果として得られるビットの論理和がとられる。ノード毎に、復号器は関連するビット位置の集合を計算する。関連するビット位置の集合は、そのノードの退出道路セグメント毎に同一である。これは、ノードの領域及び目標領域の集合にのみ依存する。目標領域が1つだけ存在する場合、1つのレベルにおいて関連するビット位置は1つだけ存在する。換言すると、他のレベルで格納された情報は、このノードに関しては無視される。2つ以上の目標領域がある場合、関連するビット位置の一部は一致するため、最大で存在する目標領域と同数の関連するビット位置が常に存在する。以下において、復号器が1つの目標領域に対する関連するビット位置を判定する方法について説明する。2つ以上の目標領域がある場合、関連するビット位置は、同様に見つけられ、1つの集合に組み合わされる。近傍領域が規定されない場合、各レベルの目標領域毎にビットベクトルのビットが1つ存在する退出道路セグメント毎に。簡潔にするために、ノード自体の領域IDに対してビットが格納されないということを無視する。関連するビットは第1のレベルにあり、ノードの領域IDが目標領域の領域IDと異なるレベル0からカウントアップする。例えばグローバルレベルのノードの領域IDがグローバルの目標領域IDと等しいが、2つの領域IDがレベル1で異なる場合、関連するビット位置はレベル1にあり、目標領域IDと等しい。これは、そのレベルの非圧縮ビットベクトル列のビット位置である。この列は、可能な目標領域ID毎に1ビットを含む。領域再マッピングテーブルは、この位置を実際にはそのレベルで符号化される圧縮ビットベクトル列の位置に変換するために使用される。近傍領域が規定されるすなわち、可視エリア内の領域場合、関連するビットは、目標領域がノードの領域の近傍にある最も精細なレベルで判定される。4つのレベルを一例として利用して、目標領域IDシーケンスをa,b,c,dとし、ノードの領域IDシーケンスをe,f,g,hとする。近傍リストセクションで規定されるようにa,b,c,dがe,f,gの近傍にあり、a,bがeの近傍にある場合、関連するビットはa,b,c,dにより判定され且つレベル2で配置され、接頭辞e,f,gのレベルは近傍にあるものとしてa,b,c,dを含む。より詳細には、関連するビット位置はレベル2の副ファイルにおける領域e,f,gの近傍のa,b,c,dの指標である。前の段落で説明したように、領域IDhに対する正規のビットはこの場合は関連がない。ここでも、この関連するビット位置は、非圧縮ビットベクトル列に対するものである。復号器は、領域再マッピングテーブルを使用して、それをレベル2の圧縮ビット列のビット位置に変換する。近傍リストに関するより多くの情報は、文献Proposalforenhancedmulti-levelgraphpartitioningに含まれる。ビットベクトルのビットの復号化固定の目標領域の集合を仮定すると、ページの各ノードのビットベクトルは退出道路セグメント毎に1ビットから成る。ノードの道路セグメント数が0である場合すなわち、ノードが非情報ノードである場合、各ビットは、そのノードに対して更に復号化を行わずに1に設定される。ノードが目標領域の1つに配置される場合、ここでもビットベクトルは全て1である。この場合、符号化データは、後続するノードに対するデータを復号化するためにスキップされる必要がある。現在のノードに対するビットベクトルが単純に全て1でない場合、上述したように、復号器は関連するビット位置の集合を判定する。各ビット位置は、特定のレベルに対するものである。すなわち、ビットは特定の副ファイルに配置される。各レベルにおいて、副ファイルは完全な圧縮ビット列を含むが、復号器は関連するビット位置においてのみビットを抽出する必要がある。復号化中、実際に必要な情報が後続する時のみ、未使用の情報は読み出されるスキップされる。そうでない場合、ビットストリームの未使用部分は全く読み出されない。関連するビット位置の集合は、レベルに従ってグループ化される。圧縮ビット列を復号化し且つ関連する位置でビットを読み出すためにそれを伸張する代わりに、関連する位置は圧縮ビット列の位置に変換される。あるレベルにおいて関連するビットが存在する場合、最初に、先行ノードに対するデータが適宜スキップされる復号器は、それがどの程度遠くから来たものかを各レベルの副ファイルに記憶する。所定の副ファイルにおいて当該ノードに対するセクションに到達すると、ビットベクトルは線毎に復号化される。退出道路セグメント毎に1ビットが格納される。これは、全ての関連するビット位置に対する復号化ビットの論理和演算の結果である。現在のノードの特定の道路セグメントに対する情報は、復号化方法を指定するハフマンシンボルから開始する。これは以下の値のうちの1つを有する。このレベルにおける道路セグメントに対する全てのビットベクトルのビットが0であることを指定するシンボルこのレベルにおける全ての近傍ビットを含む。この道路セグメントに対して、これ以上ビットが復号化される必要はない。このレベルにおける道路セグメントに対する全てのビットベクトルのビットが1であることを指定するシンボルこのレベルにおける全ての近傍ビットを含む。この道路セグメントに対して、これ以上ビットが復号化される必要はない。ビットベクトルのビット列がブロックにより明示的に与えられることを指定するシンボル。ブロックによる圧縮ビットベクトルのビット列の復号化については以下に説明する。道路セグメントに対するビットベクトルのビットは、ページ全体の符号化中に構築される履歴トラックに入れられる。履歴トラックへの指標を指定するシンボル。所定の指標において、履歴トラックは道路セグメントに対する所望のビットベクトルのビット値を含む。履歴トラックの現在のサイズに依存して、復号化方法セレクタのための異なるハフマン木が使用される。ハフマン木の数を指定する限界値が副ファイルのヘッダにある。履歴トラックのサイズがこの値を越える場合、最後のハフマン木が再利用される。ビットベクトル列が明示的に符号化されるべきであることを方法セレクタシンボルが指定する場合、復号器は圧縮ビットベクトルのビット列をブロック毎に読み出す。これは、このレベルにおける関連するビット位置圧縮ビットベクトル列に対するのビット値を収集する。ビットの値の論理和がとられる。論理和の中間結果が1になるとすぐに、この道路セグメントに対する全ての更なるブロックの残りのビットがスキップされる。各ブロックを復号化するために使用されるハフマン木はブロック中のビット数に依存する。副ファイルヘッダで指定されるように、正規のブロックの長さに対して1つのハフマン木が存在する。道路セグメントに対する最後のブロックはより短くてもよい。そのサイズに依存して、復号化のために適切なハフマン木が使用される。長さ1のブロックは1ビットであり、ハフマン復号化を使用せずに直接読み出される。ブロック数が少なくとも2である場合、ビットベクトルから生成されたビットストリームはブロックに対するハフマンシンボルの前に追加のビットを含む。その値は、復号化列全体が実際の値のビット毎の否定となると理解されるかを指定する。この否定の目的はより適切なハフマン圧縮である。"