(57)【要約】【課題】データベースのデータ量を低減できる「文字列検索システム、文字列データベースのデータ構造及びナビゲーション装置」を提供する。【解決手段】バイト長毎に対応してバイト長別ディレクトリ３０１を設け、バイト長nのバイト長別ディレクトリ３０１には、バイト長がnである施設名文字列を格納する。施設名文字列の格納は、施設名文字列を文字列番号の小さい順に、施設名文字列のデータの合計が所定サイズを超えない最大数、未抽出の施設名文字列の内から抽出して、新たに作成した文字列ファイル３０３に格納する処理を繰り返すことにより行う。各文字列ファイル３０３には、格納している施設名文字列の文字列番号範囲が小さい順に０から昇順にファイル番号FNをファイル名として与える。そして、データベースにおいて、施設名文字列の指定を、施設名文字列のバイト長と施設名文字列の文字列番号によって行う。【選択図】図３
2011048437.tif 000002
【特許請求の範囲】
【請求項１】
複数の文字列を登録した文字列データベースから文字列を検索する文字列検索システムであって、
前記文字列データベースは、文字列のデータサイズ毎に対応して設けたディレクトリを有し、各ディレクトリには、当該ディレクトリ内における順番が与えられた文字列ファイルが収容され、前記順番上最後の文字列ファイルを除く各文字列ファイルには、当該ディレクトリに対応するデータサイズの文字列が、文字列のデータサイズの合計が所定のファイルサイズを超えない範囲において最大数格納されており、
当該文字列検索システムは、
文字列を前記文字列データベースから検索する検索部を有し、
前記検索部は、
文字列のデータサイズと文字列番号とを表す文字列コードを指定文字列コードとして受け付け、前記文字列データベースの前記指定文字列コードが表すデータサイズに対応する前記ディレクトリを対象ディレクトリとして、当該対象ディレクトリから、当該指定文字列コードが表す前記文字列番号の文字列である目的文字列を取得する文字列取得部を有し、
前記文字列番号は、前記各文字列に、前記ディレクトリ毎に与えられた連番の番号であり、当該文字列番号は、前記各文字列に、当該文字列の前記文字列ファイル内の格納位置が後であるほど大きく、当該文字列が格納されている文字列ファイルの順番が後である程大きくなるように割り当てられており、
前記文字列取得部は、
前記指定文字列コードが表すデータサイズと前記所定のファイルサイズとから、前記対象ディレクトリに収容されている、当該対象ディレクトリ内の前記順番上最後の文字列ファイルを除く各文字列ファイルに格納されている文字列数をファイル内文字列数として算出すると共に、前記目的文字列が格納されている文字列ファイルの前記対象ディレクトリ内の順番を、算出した前記ファイル内文字列数と前記指定文字列コードが表す文字列番号とから算出して、前記対象ディレクトリ内の算出した順番の文字列ファイルを対象文字列ファイルとし、
前記対象文字列ファイル内の、前記目的文字列の格納範囲を、算出した前記ファイル内文字列数と前記指定文字列コードが表す文字列番号と前記指定文字列コードが表すデータサイズから算出し、
前記対象文字列ファイル内の前記算出した格納範囲のデータを前記目的文字列として取得することを特徴とする文字列検索システム。
【請求項２】
請求項１記載の文字列検索システムであって、
前記ディレクトリ内において、所定の前記順番の範囲の前記文字列ファイル、もしくは、全ての前記文字列ファイルは、所定のファイル数の文字列ファイル毎に、順番づけられたサブディレクトリに、より順番の大きいサブディレクトリに収容された前記文字列ファイルの順番の範囲がより大きくなるように収容された形態で前記ディレクトリに収容されており、
前記文字列取得部は、前記対象文字列ファイルが収容されているサブディレクトリを、前記目的文字列が格納されている文字列ファイルの前記対象ディレクトリ内の前記算出した順番と、前記所定のファイル数に基づいて算出することを特徴とする文字列検索システム。
【請求項３】
請求項１記載の文字列検索システムであって、
文字列の属性と、当該属性を有する文字列の前記文字列コードとの対応を登録した検索用データベースを有し、
前記検索部は、
前記検索用データベースを参照し、検索キーとして指定された属性に対応する各文字列コードを取得する文字列コード取得部を有し、
前記文字列取得部は、前記文字列コード取得部が取得した各文字列コードの各々を前記指定文字列コードとして受け付けて、受け付けた各指定文字列コードの各々について前記目的文字列を取得することを特徴とする文字列検索システム。
【請求項４】
請求項２記載の文字列検索システムであって、
文字列の属性と、当該属性を有する文字列の前記文字列コードとの対応を登録した検索用データベースを有し、
前記検索部は、
前記検索用データベースを参照し、検索キーとして指定された属性に対応する各文字列コードを取得する文字列コード取得部を有し、
前記文字列取得部は、前記文字列コード取得部が取得した各文字列コードの各々を前記指定文字列コードとして受け付けて、受け付けた各指定文字列コードの各々について前記目的文字列を取得することを特徴とする文字列検索システム。
【請求項５】
請求項３記載の文字列検索システムであって、
前記文字列は施設の名称を表す文字列であって、
前記文字列の属性は、当該文字列の任意字数の先頭文字列であることを特徴とする文字列検索システム。
【請求項６】
請求項３記載の文字列検索システムであって、
前記文字列は施設の名称を表す文字列であって、
前記文字列の属性は、当該文字列が名称を表す施設の電話番号の任意字数の先頭数字列であることを特徴とする文字列検索システム。
【請求項７】
請求項３記載の文字列検索システムであって、
前記文字列は施設の名称を表す文字列であって、
前記文字列の属性は、当該文字列が名称を表す施設のジャンルであることを特徴とする文字列検索システム。
【請求項８】
請求項５記載の文字列検索システムと、
当該文字列検索システムが取得した前記目的文字列が表す施設の名称の一覧を表示し、名称を表示した施設のうちから施設の選択を受け付けて、選択を受け付けた施設を目的地に設定する目的地設定部と、
前記目的地設定部が受け付けた目的地までの経路を案内する経路案内部とを有することを特徴とするナビゲーション装置。
【請求項９】
請求項６記載の文字列検索システムと、
当該文字列検索システムが取得した前記目的文字列が表す施設の名称の一覧を表示し、
名称を表示した施設のうちから施設の選択を受け付けて、選択を受け付けた施設を目的地に設定する目的地設定部と、
前記目的地設定部が受け付けた目的地までの経路を案内する経路案内部とを有することを特徴とするナビゲーション装置。
【請求項１０】
請求項７記載の文字列検索システムと、
当該文字列検索システムが取得した前記目的文字列が表す施設の名称の一覧を表示し、名称を表示した施設のうちから施設の選択を受け付けて、選択を受け付けた施設を目的地に設定する目的地設定部と、
前記目的地設定部が受け付けた目的地までの経路を案内する経路案内部とを有することを特徴とするナビゲーション装置。
【請求項１１】
複数の文字列を登録した文字列データベースのデータ構造であって、
文字列のデータサイズ毎に対応して設けたディレクトリを有し、
各ディレクトリには、当該ディレクトリ内における順番が与えられた文字列ファイルが収容され、
前記順番上最後の文字列ファイルを除く各文字列ファイルには、当該ディレクトリに対応するデータサイズの文字列が、文字列のデータサイズの合計が所定のファイルサイズを超えない範囲において最大数格納されていることを特徴とする文字列データベースのデータ構造。
【請求項１２】
請求項１１記載の文字列データベースのデータ構造であって、
前記ディレクトリ内において、所定の前記順番の範囲の前記文字列ファイル、もしくは、全ての前記文字列ファイルは、所定のファイル数の文字列ファイル毎に、順番づけられたサブディレクトリに、より順番の大きいサブディレクトリに収容された前記文字列ファイルの順番の範囲がより大きくなるように収容された形態で前記ディレクトリに収容されていることを特徴とする文字列データベースのデータ構造。
【請求項１３】
コンピュータによって読み取られ実行されるコンピュータプログラムであって、
前記コンピュータを請求項１記載の文字列検索システムとして機能させることを特徴とするコンピュータプログラム。
【請求項１４】
コンピュータによって読み取られ実行されるコンピュータプログラムであって、
前記コンピュータを請求項２記載の文字列検索システムとして機能させることを特徴とするコンピュータプログラム。
【請求項１５】
コンピュータによって読み取られ実行されるコンピュータプログラムであって、
前記コンピュータを請求項３記載の文字列検索システムとして機能させることを特徴とするコンピュータプログラム。
【請求項１６】
コンピュータによって読み取られ実行されるコンピュータプログラムであって、
前記コンピュータを請求項４記載の文字列検索システムとして機能させることを特徴とするコンピュータプログラム。
【請求項１７】
コンピュータによって読み取られ実行されるコンピュータプログラムであって、
前記コンピュータを請求項５記載の文字列検索システムとして機能させることを特徴とするコンピュータプログラム。
【請求項１８】
コンピュータによって読み取られ実行されるコンピュータプログラムであって、
前記コンピュータを請求項６記載の文字列検索システムとして機能させることを特徴とするコンピュータプログラム。
【請求項１９】
コンピュータによって読み取られ実行されるコンピュータプログラムであって、
前記コンピュータを請求項７記載の文字列検索システムとして機能させることを特徴とするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースに登録された文字列を検索するシステムにおいて、データベースのデータ量を削減する技術に関するものである。
【背景技術】
【０００２】
施設の施設名や電話番号や住所やジャンルや座標を施設情報として登録したデータベースを用いて、電話番号や住所やジャンルや施設名を検索キーとして施設情報を検索し、検索した施設情報に含まれる施設名を表示するナビゲーション装置が知られている（たとえば、特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００１-３１７９５０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
さて、上述したようなナビゲーション装置において、電話番号や住所やジャンルや施設名を検索キーとした前方一致検索により検索される施設情報の施設名の表示を高速化するために、電話番号や住所やジャンルや施設名の先頭文字列と成り得る任意字数の文字列毎に施設名を対応づけて登録した検索用データをデータベース中に予め用意し、この検索用データを用いて施設名の表示を行うことが考えられる。
【０００５】
すなわち、たとえば、施設名「ＡＡＡ」と施設名「ＡＢＢ」と施設名「ＡＡＢ」の三施設が存在する場合に、文字列「Ａ」の検索用データに施設名「ＡＡＡ」と施設名「ＡＢＢ」と施設名「ＡＡＢ」の三施設の施設名を登録し、文字列「ＡＡ」の検索用データに施設名「ＡＡＡ」と施設名「ＡＡＢ」の二施設の施設名を登録し、文字列「ＡＢ」の検索用データに施設名「ＡＢＢ」の施設の施設名を登録し、文字列「ＡＡＡ」の検索用データに施設名「ＡＡＡ」の施設の施設名を登録し、文字列「ＡＡＢ」の検索用データに施設名「ＡＡＢ」の施設の施設名を登録し、文字列「ＡＢＢ」の検索用データに施設名「ＡＢＢ」の施設の施設名を登録しておくことにより、この検索データを用いて、たとえば、ユーザから施設名の検索キーとして文字列「Ａ」が入力されたときに、文字列「Ａ」の検索用データから、施設名「ＡＡＡ」と施設名「ＡＢＢ」と施設名「ＡＡＢ」の三施設の施設名を直接取得して表示したり、ユーザから施設名の検索キーとして文字列「ＡＡ」が入力されたときに、文字列「ＡＡ」の検索用データから、施設名「ＡＡＡ」と「ＡＡＢ」の二施設の施設名を直接取得して表示できるようになる。
【０００６】
しかし、このようにすると、一つの施設名が複数の検索用データに多重に登録されることになり、データベースのデータ量が大きく増大してしまうことになる。一方、各施設名に識別子を与えて識別子と施設名の対応を記述した対応テーブルを設け、検索用データに施設名に代えて識別子を登録することも考えられるが、このようにすると、対応テーブル中から識別子を検索キーとして、施設名を検索する処理を行う必要が生じ、検索速度が低下してしまうことになる。
【０００７】
そこで、本発明は、検索キーに整合する文字列をデータベースから検索するシステムにおいて、検索速度の低下を抑制しつつ、データベースのデータ量を削減することを課題とする。
【課題を解決するための手段】
【０００８】
前記課題達成のために、本発明は、複数の文字列を登録した文字列データベースから文字列を検索する文字列検索システムにおいて、前記文字列データベースを、文字列のデータサイズ毎に対応して設けたディレクトリを有し、各ディレクトリには、当該ディレクトリ内における順番が与えられた文字列ファイルが収容され、前記順番上最後の文字列ファイルを除く各文字列ファイルには、当該ディレクトリに対応するデータサイズの文字列が、文字列のデータサイズの合計が所定のファイルサイズを超えない範囲において最大数格納されているものとした上で、当該前記文字列検索システムに、文字列を前記文字列データベースから検索する検索部を設けたものである。ここで、当該検索部は、文字列のデータサイズと文字列番号とを表す文字列コードを指定文字列コードとして受け付け、前記文字列データベースの前記指定文字列コードが表すデータサイズに対応する前記ディレクトリを対象ディレクトリとして、当該対象ディレクトリから、当該指定文字列コードが表す前記文字列番号の文字列である目的文字列を取得する文字列取得部を備えたものである。また、前記文字列番号は、前記各文字列に、前記ディレクトリ毎に与えられた連番の番号であり、当該文字列番号は、前記各文字列に、当該文字列の前記文字列ファイル内の格納位置が後であるほど大きく、当該文字列が格納されている文字列ファイルの順番が後である程大きくなるように割り当てられており、前記文字列取得部は、前記指定文字列コードが表すデータサイズと前記所定のファイルサイズとから、前記対象ディレクトリに収容されている、当該対象ディレクトリ内の前記順番上最後の文字列ファイルを除く各文字列ファイルに格納されている文字列数をファイル内文字列数として算出すると共に、前記目的文字列が格納されている文字列ファイルの前記対象ディレクトリ内の順番を、算出した前記ファイル内文字列数と前記指定文字列コードが表す文字列番号とから算出して、前記対象ディレクトリ内の算出した順番の文字列ファイルを対象文字列ファイルとし、前記対象文字列ファイル内の、前記目的文字列の格納範囲を、算出した前記ファイル内文字列数と前記指定文字列コードが表す文字列番号と前記指定文字列コードが表すデータサイズから算出し、前記対象文字列ファイル内の前記算出した格納範囲のデータを前記目的文字列として取得するものである。
【０００９】
このような文字列検索システムによれば、文字列コードから文字列データベースに格納されている文字列を取得でき、また、文字列コードは文字列のデータサイズと同データサイズの文字列中での順番を表す文字列番号より構成されるので、文字列コードのデータ長を、文字列自身の平均的なデータ長よりも短くすることができる。よって、このような文字列コードを文字列自身に代えて、任意のデータベース中で文字列を表す情報として用いることにより、当該データベースのサイズを低減することができる。また、文字列コードより直接文字列の格納範囲を算出して当該文字列を取得するので検索速度も大きく低下することはない。
【００１０】
ここで、このような文字列検索システムは、前記ディレクトリ内において、所定の前記順番の範囲の前記文字列ファイル、もしくは、全ての前記文字列ファイルを、所定のファイル数の文字列ファイル毎に、順番づけられたサブディレクトリに、より順番の大きいサブディレクトリに収容された前記文字列ファイルの順番の範囲がより大きくなるように収容された形態で前記ディレクトリに収容し、前記文字列取得部において、前記対象文字列ファイルが収容されているサブディレクトリを、前記目的文字列が格納されている文字列ファイルの前記対象ディレクトリ内の前記算出した順番と、前記所定に基づいて算出するように構成してもよい。
【００１１】
このようにサブディレクトリを設けることにより、前記対象文字列ファイルに、より速やかにアクセスすることができるようになることが期待できる。
また、このような文字列検索システムに、文字列の属性と、当該属性を有する文字列の文字列コードとの対応を登録した検索用データベースを設けると共に、前記検索部に、前記検索用データベースを参照し、検索キーとして指定された属性に対応する各文字列コードを取得する文字列コード取得部を設け、前記文字列取得部において、前記文字列コード取得部が取得した各文字列コードの各々を前記指定文字列コードとして受け付けて、受け付けた各指定文字列コードの各々について前記目的文字列を取得するように構成してもよい。
【００１２】
なお、以上の文字列検索システムにおいて、前記文字列は施設の名称を表す文字列であって良く、この場合に、前記文字列の属性としては、当該文字列の任意字数の先頭文字列、または、当該文字列が名称を表す施設の電話番号の任意字数の先頭数字列、または、当該文字列が名称を表す施設のジャンルなどを用いることができる。
【００１３】
また、この場合に、このような文字列検索システムと、当該文字列検索システムが取得した前記目的文字列が表す施設の名称の一覧を表示し、名称を表示した施設のうちから施設の選択を受け付けて、選択を受け付けた施設を目的地に設定する目的地設定部と、前記目的地設定部が受け付けた目的地までの経路を案内する経路案内部とを用いてナビゲーション装置を構成することができる。
【発明の効果】
【００１４】
以上のように、本発明によれば、検索キーに整合する文字列を検索するシステムにおいて、検索速度の低下を抑制しつつ、データベースのデータ量を削減することができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施形態に係るナビゲーション装置の構成を示すブロック図である。
【図２】本発明の実施形態に係る検索データベースの構成を示す図である。
【図３】本発明の実施形態に係る施設名データベースの構成を示す図である。
【図４】本発明の実施形態に係る施設名文字列取得処理を示すフローチャートである。
【図５】本発明の実施形態に係る施設名データベースの更新法を示す図である。
【図６】本発明の実施形態に係る施設名データベースの他の構成例を示す図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について、ナビゲーション装置への適用を例にとり説明する。
図１に、本実施形態に係るナビゲーション装置の構成を示す。
図示するように、ナビゲーション装置は、制御装置１０、操作部２１と、表示装置２２と、車両状態センサ２３と、ＧＰＳ受信機２４とを備えて構成される。ここで、車両状態センサ２３は、角加速度センサや地磁気センサなどである方位センサや、車速パルスセンサなどである車速センサなどの、車両状態を検出する各種センサの集合である。
【００１７】
また、ナビゲーション装置の制御装置１０は、ＨＤＤなどの記憶装置１１、現在状態算出部１２、ルート探索部１３、メモリ１４、制御部１５、案内画像生成部１６、操作部２１や表示装置２２を用いたＧＵＩを制御するＧＵＩ制御部１７とを有する。
ここで、ナビゲーション装置の記憶装置１１には、道路地図を表す地図データ、検索データベース、施設データベース、施設名データベースが格納されている。
但し、以上の制御装置１０は、ハードウエア的には、マイクロプロセッサや、メモリや、その他のグラフィックプロセッサやジオメトリックプロセッサ等の周辺デバイスを有する一般的な構成を備えたＣＰＵ回路であって良く、この場合、以上に示した制御装置１０の各部は、マイクロプロセッサが予め用意されたプログラムを実行することにより具現化するプロセスとして実現されるものであって良い。また、この場合、このようなプログラムは、記録媒体や適当な通信路を介して、制御装置１０に提供されるものであって良い。
【００１８】
さて、このようなナビゲーション装置の構成において、現在状態算出部１２は、車両状態センサ２３やＧＰＳ受信機２４の出力から推定される現在位置に対して、記憶装置１１から読み出した地図データが示す前回決定した現在位置の周辺の地図とのマップマッチング処理などを施して、現在位置として最も確からしい座標と、現在の進行方向として最も確からしい方向とを、それぞれ現在位置、現在進行方位として決定し、メモリ１４に設定する。
【００１９】
また、制御部１５は、ユーザから操作部２１、ＧＵＩ制御部１７を介して目的地の設定を受付け、これをメモリ１４にセットする。そして、目的地までの誘導経路をルート探索部１３に探索させる。ルート探索部１３は、必要地理的範囲の地図データを記憶装置１１から読み出し、メモリ１４に設定されている現在位置から目的地までの最小コストの経路を距離最小、時間最小などコストモデルに基づいて探索し、探索した経路を誘導経路とし、誘導経路の経路データを、メモリ１４にセットする。
【００２０】
また、制御部１５は、メモリ１４にセットされた現在位置が目的地近傍となったならば、目的地到着と判定し、メモリ１４にセットされている目的地や経路データをクリアする処理を行う。
また、案内画像生成部１６は、メモリ１４にセットされている現在位置を参照し、地図データが示す現在位置周辺の地図を、ユーザが設定している縮尺で表す地図画像を生成する。また、案内画像生成部１６は、描画した地図画像上に、施設詳細データのメモリ１４にセットされている現在位置を表す図形を描画し、案内画像としてＧＵＩ制御部１７を介して表示装置２２に表示する処理を繰り返し行う。ここで、メモリ１４に目的地や誘導経路の経路データがセットされている場合には、案内画像生成部１６は、経路データが示す誘導経路の地図画像が表す地図表示範囲内の部分を表す図形も案内画像に含めて表示する。また、地図表示範囲内に目的地が含まれる場合には、さらに、目的地を表す図形も案内画像に含めて表示する。
【００２１】
そして、制御部１５は、ユーザから施設検索を要求されると、検索処理を行って、ユーザから指定された検索キーにマッチする施設の施設名の一覧を表示する。
以下、この検索処理について説明する。
まず、記憶装置に記憶されている検索データベース、施設データベース、施設名データベースについて説明する。
まず、図２ａに示すように、検索データベースは、ジャンル検索データベース、電話番号検索データベース、５０音検索データベースより構成される。
そして、ジャンル検索データベースには、施設の「宿泊施設」、「飲食店」といったジャンルを施設属性として、各施設属性毎に対応して設けた検索データが格納されている。
また、電話番号検索データベースには、施設の電話番号の任意長の先頭数字列を施設属性として、各施設属性毎に対応して設けた検索データが格納されている。
また、５０音検索データベースには、施設の名称の任意長の先頭文字列を施設属性として、各施設属性毎に対応して設けた検索データが格納されている。
そして、これらジャンル検索データベース、電話番号検索データベース、５０音検索データベースに含まれる各検索データには、図２ｂに示すように、当該検索データに対応する施設属性を有する施設毎に対応して設けられたレコード（図の各行）を備える。
すなわち、ジャンル検索データベースであれば、ホテルである施設Ａは「宿泊施設」の施設属性を持つので、施設Ａのレコードが、「宿泊施設」の施設属性に対応する検索データに設けられる。
また、電話番号検索データベースであれば、施設の電話番号が、「012…」の施設Ａは、数字列長１の先頭数字列「0」、数字列長２の先頭数字列「01」、数字列長３の先頭数字列「012」といった１からn（nは施設Ａの電話番号の数字列長）までの各数字列長の先頭数字列の各々に対応して、「0」の施設属性、「01」の施設属性、「012」の施設属性、…といったように施設の電話番号の数字列長と同じ数だけの施設属性をあわせ持つので、当該施設Ａのレコードが、「0」の施設属性に対応する検索データ、「01」の施設属性に対応する検索データ、「012」の施設属性に対応する検索データ、のように、施設Ａの各施設属性に対応する各検索データにそれぞれ設けられる。
【００２２】
また、５０音検索データベースであれば、施設の名称が、「あいう…」の施設Ａは、文字列長１の先頭文字列「あ」、文字列長２の先頭文字列「あい」、文字列長３の先頭文字列「あいう」といった１からn（nは施設Ａの名称の文字列長）までの各文字列長の先頭文字列の各々に対応して、「あ」の施設属性、「あい」の施設属性、「あいう」の施設属性、…といったように、施設の名称の文字列長と同じ数だけの施設属性をあわせ持つので、施設Ａのレコードは、「あ」の施設属性に対応する検索データ、「あい」の施設属性に対応する検索データ、「あいう」の施設属性に対応する検索データ、…のように、施設Ａの各施設属性に対応する各検索データにそれぞれ設けられる。
【００２３】
そして、各検索データの各施設に対応するレコードには、施設データポインタと、施設名コードが含まれる。この施設データポインタと、施設名コードについては後述する。
次に、施設データベースには、図２ｃに示すように、施設毎に設けられた施設データが格納されており、各施設データには、施設の識別子である施設ＩＤ、施設名称、施設の住所、施設の電話番号、施設の位置を示す座標や、その他の施設の各種情報が登録されている。
【００２４】
ここで、前述した各検索データの各レコードの施設データポインタは、図２ｂ、ｃ間の矢印で示すように、当該レコードに対応する施設の施設データを指し示すものである。
次に、施設名データベースは、図３ａに示すように、文字列ディレクトリ３００によって構成される。
また、文字列ディレクトリ３００には、２バイト長、４バイト長、６バイト長、…といったように、偶数のバイト長毎に対応して設けたバイト長別ディレクトリ３０１が収容されている。
そして、バイト長nに対応するバイト長別ディレクトリ３０１には、バイト長がnである施設名文字列が格納される。ここで、施設名文字列とは、施設の名称を表す文字列である。ただし、施設の名称を表す文字列のバイト長が偶数である場合には、当該施設の名称を表す文字列自体を施設名文字列として用いるが、施設の名称を表す文字列のバイト長が奇数である場合には、施設の名称を表す文字列の後尾にキャラクタ“null（h）"を付加して、そのバイト長を１バイト増やして偶数としたものを、施設名文字列として用いている。
【００２５】
なお、施設名文字列の最大バイト長を超えるバイト長別ディレクトリ３０１は不要である。
ここで、施設名文字列のバイト長がnである施設名文字列は、以下のようにして、バイト長nに対応するバイト長別ディレクトリ３０１に格納する。
まず、バイト長nの全ての施設名文字列に０から昇順に連番の順番を与え、施設名文字列に与えた順番を施設名文字列の文字列番号とする。
次に、バイト長nの施設名文字列を文字列番号の小さい順に、施設名文字列のデータの合計が５１２KBを超えない最大数、未抽出の施設名文字列の内から抽出して、新たに作成した文字列ファイル３０３に格納する処理を、バイト長nの全ての施設名文字列が抽出されるまで行う。ここで、各文字列ファイル３０３には、格納しているデータに含まれる施設名文字列の文字列番号の範囲が小さい順に０から昇順に連番のファイル番号FNをファイル名として与える。
【００２６】
そして、ファイル番号FNが０から９９の１００個の文字列ファイル３０３は、バイト長nに対応するバイト長別ディレクトリ３０１に直接格納する。ファイル番号FNが１００以降の文字列ファイル３０３が存在する場合には、文字列ファイル数が１００の倍数を超える度に、サブディレクトリ３０２をバイト長nに対応するバイト長別ディレクトリ３０１内に新たに作成した上、新たに作成したサブディレクトリ３０２に文字列ファイル格納することにより、文字列ファイル３０３をバイト長nに対応するバイト長別ディレクトリ３０１に格納する。ここで、各サブディレクトリ３０２には、格納している文字列ファイル３０３のファイル番号FNの範囲が小さい順に１から昇順に連番のサブディレクトリ番号SDNをディレクトリ名として与える。したがって、１００×Mから（１００×M）+９９のファイル番号FNの文字列ファイル３０３は、サブディレクトリ番号SDNがMのサブディレクトリ３０２に格納されることになる。
【００２７】
さて、ここで、前述した各検索データの各レコードの施設名コードは、図３ｂに示すように、文字列バイト長コードと、文字列番号とよりなる。そして、文字列バイト長コードは、施設名コードが含まれるレコードに対応する施設の名称を表す施設名文字列のバイト長を、文字列バイト長コード=０は２バイト長、文字列バイト長コード=１は４バイト長、文字列バイト長コード=２は６バイト長といったように表すものである。また、文字列番号は、施設名コードが含まれるレコードに対応する施設の名称を表す施設名文字列に与えた上述の文字列番号である。ここで、詳細は後述するが、図３ａ、ｂ間の矢印で示すように、文字列バイト長コードは、施設名コードが含まれるレコードに対応する施設の名称を表す施設名文字列が格納されているバイト長別ディレクトリ３０１を指定し、文字列番号は、当該施設名文字列のバイト長別ディレクトリ３０１内の格納位置を指定するものである。
【００２８】
さて、次に、このような検索データベース、施設データベース、施設名データベースを用いて行う、ユーザから指定された検索キーにマッチする施設の施設名を一覧の表示動作について説明する。
まず、ユーザから、検索モードの選択を受けつけて設定する。ここで、検索モードとしては、ジャンル検索モード、電話番号検索モード、５０音検索モードのいずれかの選択を受けつける。
そして、検索モードとしてジャンル検索モードが設定されている場合には、ユーザから検索キーとして、検索する施設のジャンルの指定を受けつけ、指定を受けつけたジャンルを検索対象の施設属性として、検索データベースのジャンル検索データベースに格納されている、検索対象の施設属性に対応する検索データを、検索キーに対応する検索データとして抽出する。
【００２９】
また、検索モードとして電話番号検索モードが設定されている場合には、ユーザから検索キーとして、検索する施設の電話番号またはその先頭部分の数字列の入力を受けつけ、入力を受けつけた数字列を検索対象の施設属性として、検索データベースの電話番号検索データベースに格納されている、検索対象の施設属性に対応する検索データを検索キーに対応する検索データとして抽出する。
【００３０】
また、検索モードとして５０音検索モードが設定されている場合には、ユーザから検索キーとして、検索する施設の施設名またはその先頭部分の文字列の入力を受けつけ、入力を受けつけた数字列を検索対象の施設属性として、検索データベースの５０音検索データベースに格納されている、検索対象の施設属性に対応する検索データを検索キーに対応する検索データとして抽出する。
【００３１】
そして、抽出した検索キーに対応する検索データの各レコードに登録されている施設名コードの各々に対応する施設名文字列を、施設名データベースより取得し、取得した施設名文字列によって示される施設名の一覧をＧＵＩ制御部１７を介して表示装置２２に表示する。ただし、取得した施設名文字列の後尾にキャラクタ“null（h）"が付加されている場合には、これを無視して施設名文字列の表示を行う。
【００３２】
ここで、各施設名コードに対応する施設名文字列の取得は図４に示す施設名文字列取得処理によって行う。
すなわち、まず、施設名コードに対応する施設名文字列を目的文字列として、施設名コードに含まれる文字列バイト長コードから、目的文字列のバイト長SLを算出し（ステップ４０２）、バイト長SLから目的文字列が格納されているバイト長別ディレクトリ３０１を特定する（ステップ４０４）。すなわち、施設名コードに含まれる文字列バイト長コードがMバイト長を示していれば、目的文字列のバイト長SLはMであり、目的文字列が格納されているバイト長別ディレクトリ３０１は、Mバイト長に対応するバイト長別ディレクトリ３０１として特定される。
【００３３】
そして、次に、目的文字列が格納されているバイト長別ディレクトリ３０１内の（最後の文字列ファイル３０３を除く）各文字列ファイル３０３に格納されている施設名文字列数を表すファイル内文字列数STを、INT(512×1024バイト/目的文字列のバイト長SL)によって算出する（ステップ４０６）。なお、512×1024バイトは５１２KBである。また、INT(X)は、Xの整数部分を表すものとする。
【００３４】
また、目的文字列が格納されている文字列ファイル３０３のファイル番号FNを、施設名コードに含まれる文字列番号Nを用いて、INT(文字列番号N/ファイル内文字列数ST)によって求める（ステップ４０８）。
次に、目的文字列が格納されている文字列ファイル３０３が収容されているサブディレクトリ３０２のサブディレクトリ番号SDNを、ステップ４０８で求めたファイル番号FNを用いて、INT(ファイル番号FN/１００)によって求める（ステップ４１０）。
そして、求めたサブディレクトリ番号SDNが０であれば（ステップ４１２）、目的文字列が格納されている文字列ファイル３０３は、ステップ４０４で特定したバイト長別ディレクトリ３０１に直接格納されているので、ステップ４０４で特定したバイト長別ディレクトリ３０１に収容されている、ステップ４０８で求めたファイル番号FNをファイル名に持つ文字列ファイル３０３を参照ファイルとする（ステップ４１４）。
【００３５】
一方、求めたサブディレクトリ番号SDNが０でなければ（ステップ４１２）、ステップ４０４で特定したバイト長別ディレクトリ３０１内の、ステップ４１０で求めたサブディレクトリ番号SDNをディレクトリ名として持つサブディレクトリ３０２に収容されている、ステップ４０８で求めたファイル番号FNをファイル名に持つ文字列ファイル３０３を参照ファイルとする（ステップ４２２）。
【００３６】
そして、目的文字列の参照ファイル内の順番を表すファイル内文字列番号FSNを、MOD（文字列番号N/ファイル内文字列数ST）によって求める（ステップ４１６）。ここで、MOD（X/Y）は、整数型のわり算X/Yの余りを表す。
そして、目的文字列の参照ファイル内の先頭位置SSを、ファイル内文字列番号FSN×目的文字列のバイト長SLにより求め、参照ファイルの格納データの先頭からSSバイト目から、目的文字列のバイト長SLと等しいバイト長データを読み出す（ステップ４１８）。
そして、読み出したデータを、施設名コードに対応する施設名文字列とし（ステップ４２０）、処理を終了する。
以上、制御部１５が行う検索処理について説明した。
さて、制御部１５は、このような検索処理によって表示した施設名の一覧上で、ユーザによって選択された施設名の施設をユーザ選択施設として、ユーザ選択施設の施設データに登録されている各種情報を表示したり、ユーザ選択施設の施設データに登録されている座標が示すユーザ選択施設の位置を地図データが表す地図上で表示したり、ユーザ選択施設の施設データに登録されている座標を目的地に設定する処理も行う。ここで、ユーザ選択施設の施設データは、ユーザによって選択された施設名文字列の施設名コードが登録されていた、検索データのレコードの施設データポインタが示す施設データとして求めることができる。
【００３７】
次に、以上のような施設名データベースの更新法について説明する。
いま、図５ａ５００に示すように、文字列番号Nが0からPのP+1個の施設名文字列と、m01個の文字列ファイル３０３と、m個のサブディレクトリ３０２を上述のように収容したXバイト長に対応するバイト長別ディレクトリ３０１の内の、ファイル番号FNが099の文字列ファイル３０３に格納されている文字列番号Nがnの施設名文字列を削除し、Xバイト長の二つの施設名文字列を追加する場合を考える。
【００３８】
この場合、まず、矢印５０１で示すように、ファイル番号FNが099の文字列ファイル３０３に格納されている文字列番号Nがnの施設名文字列を、追加する一つの施設名文字列で置き換えることにより、ファイル番号FNが099の文字列ファイル３０３を更新し、一つの施設名文字列の削除と、一つ目の施設名文字列の追加とを行う。ここで、追加した施設名文字列は、削除した施設名文字列の文字列番号（N=n）を引き継ぐことになる。なお、図中５０２が更新前のファイル番号FNが099の文字列ファイル３０３の内容を、５０３が更新の後のファイル番号FNが099の文字列ファイル３０３の内容を表している。
【００３９】
また、二つ目の施設名文字列の追加は、矢印５１１で示すように、Xバイト長に対応するバイト長別ディレクトリ３０１に格納されている文字列番号（N）が最大の施設名文字列である、サブディレクトリ番号SDNがmのサブディレクトリ３０２中のファイル番号FNがm01の文字列ファイル３０３に格納されている文字列番号NがPの施設名文字列の次に、追加する二つ目の施設名文字列を追加して、ファイル番号FNがm01の文字列ファイル３０３を更新することにより行う。なお、図中５１２が更新前のファイル番号FNがm01の文字列ファイル３０３の内容を、５１３が更新の後のファイル番号FNがm01の文字列ファイル３０３の内容を表している。
【００４０】
このように、一つの施設名文字列の削除と一つの施設名文字列の追加とを、削除する施設名文字列を追加する施設名文字列で置換することによって行うことにより、施設名データベースの更新前後の差分を小さくすることができる。
よって、施設名データベースの更新を、更新前の施設名データベースを、更新前後の差分を表す差分データに従って変更することにより行う場合に、当該差分データを小さく抑えることができる。
以上、本発明の実施形態について説明した。
ところで、以上では、施設の施設名文字列として、施設毎に一つの施設名文字列を用いる場合について説明したが、以上の実施形態は、施設毎に複数の施設名文字列を用いる場合にも、同様に適用することができる。
すなわち、たとえば、施設の施設名文字列として、カタカナ表記で施設名称を表す文字列であるカタカナ施設名文字列と、かな漢字混じり文で施設名称を表すかな漢字施設名文字列と、英字で施設名称を表す英字施設名文字列とを用いる場合には、図６ａに示すように、カタカナ文字列ディレクトリと、かな漢字文字列ディレクトリと、英字文字列ディレクトリとを設け、カタカナ文字列ディレクトリに各施設のカタカナ施設名文字列を、図３の文字列ディレクトリ３００への施設名文字列の格納と同様の形態で格納し、かな漢字文字列ディレクトリに各施設のかな漢字施設名文字列を、図３の文字列ディレクトリ３００への施設名文字列の格納と同様の形態で格納し、英字文字列ディレクトリに各施設の英字施設名文字列を、図３の文字列ディレクトリ３００への施設名文字列の格納と同様の形態で格納する。
【００４１】
そして、各検索データの各レコードには、図６ｂに示すように、施設データポインタの他に、カタカナ施設名コードと、かな漢字施設名コードと、英字施設名コードを格納する。ここで、カタカナ施設名コードは、図３、４によって示した施設名コードによる文字列ディレクトリ３００内の施設名文字列の指定と同様な形態で、カタカナ文字列ディレクトリ内の当該レコードに対応するカタカナ施設名文字列を指定するものであり、かな漢字施設名コードは、図３、４によって示した施設名コードによる文字列ディレクトリ３００内の施設名文字列の指定と同様な形態で、かな漢字文字列ディレクトリ内の当該レコードに対応するかな漢字施設名文字列を指定するものであり、英字施設名コードは、図３、４によって示した施設名コードによる文字列ディレクトリ３００内の施設名文字列の指定と同様な形態で、英字文字列ディレクトリ内の当該レコードに対応する英字施設名文字列を指定するものである。
【００４２】
そして、前述した検索処理では、カタカナ表記の施設名称を表示したい場合には、各施設名コードに対応する施設名文字列の取得の際に、カタカナ施設名コードに基づいて、図４の施設名文字列取得処理と同様の処理により、カタカナ文字列ディレクトリからカタカナ施設名文字列を取得し、かな漢字混じり表記の施設名称を表示したい場合には、各施設名コードに対応する施設名文字列の取得の際に、かな漢字施設名コードに基づいて、図４の施設名文字列取得処理と同様の処理により、かな漢字文字列ディレクトリからかな漢字施設名文字列を取得し、英字表記の施設名称を表示したい場合には、各施設名コードに対応する施設名文字列の取得の際に、英字施設名コードに基づいて、図４の施設名文字列取得処理と同様の処理により、英字文字列ディレクトリから英字施設名文字列を取得するようにする。
【００４３】
なお、以上の実施形態では、各バイト長別ディレクトリ３０１に格納される文字列ファイル３０３が１００個を超える場合には、１０１個目からの文字列ファイル３０３をサブディレクトリ３０２に収容した形態でバイト長別ディレクトリ３０１に格納したが、これは、全ての文字列ファイル３０３を直接バイト長別ディレクトリ３０１に格納するようにしてもよい。または、全ての文字列ファイル３０３を、サブディレクトリ３０２に収容した形態でバイト長別ディレクトリ３０１に格納するようにしてもよい。
【００４４】
以上のように、本実施形態によれば、施設名コードから施設名データベースに格納されている施設名文字列を取得でき、施設名コードは施設名文字列のデータサイズと同データサイズの施設名文字列中での順番を表す文字列番号より構成されるので、平均的に見て施設名文字列自身よりもデータ長を短くすることができる。よって、このような施設名文字列コードを施設名文字列自身に代えて、検索データベース中で施設名文字列を表す情報として用いることにより、検索データベースのサイズを低減することができる。また、施設名文字列コードより直接施設名文字列の格納範囲を算出して当該施設名文字列を取得するので検索速度の低下を抑制することができる。
【００４５】
なお、本実施形態で示した各データベースの構造や、検索の技術は、施設名以外の任意の文字列の検索を行う任意のシステムに同様に適用することができる。
【符号の説明】
【００４６】
１０…制御装置、１１…記憶装置、１２…現在状態算出部、１３…ルート探索部、１４…メモリ、１５…制御部、１６…案内画像生成部、１７…ＧＵＩ制御部、２１…操作部、２２…表示装置、２３…車両状態センサ、２４…ＧＰＳ受信機、３００…文字列ディレクトリ、３０１…バイト長別ディレクトリ、３０２…サブディレクトリ、３０３…文字列ファイル。
【図１】
2011048437.tif 000003
【図２】
2011048437.tif 000004
【図３】
2011048437.tif 000005
【図４】
2011048437.tif 000006
【図５】
2011048437.tif 000007
【図６】
2011048437.tif 000008