(57)【要約】【課題】効率的な検索を行う技術の提供。【解決手段】複数の登録名称のそれぞれに各登録名称を示すハングル文字を字母に分解した順列である蓄積順列が対応付けられて記録媒体に記録され、かつ、前記蓄積順列の一部を構成する部分順列が共通である前記蓄積順列の中から前記部分順列に従って字母を組み合わせた場合に当該部分順列の最後の字母でハングル文字が完成する前記蓄積順列を特定するための順列特定情報が記録媒体に記録される。そして、前記ハングル文字単位で前記検索対象が指定された後に前記字母単位で前記検索対象が指定された場合、前記順列特定情報を参照し、前記ハングル文字単位で指定された前記検索対象を字母に分解した順列を前記部分順列とした場合に当該部分順列の最後の字母でハングル文字が完成する前記蓄積順列を特定し、特定された前記蓄積順列に基づいて検索を行う。【選択図】図２
2012133734.tif 000002
【特許請求の範囲】
【請求項１】
検索対象の指定をハングル文字単位または字母単位で受け付けて、記録媒体に蓄積された地図情報に含まれるハングル文字からなる複数の登録名称から、指定された検索対象を含む登録名称を検索する検索手段を備える検索装置であって、
前記記録媒体には、
前記複数の登録名称のそれぞれに各登録名称を示すハングル文字を字母に分解した順列である蓄積順列が対応付けられて記録され、かつ、
前記蓄積順列の一部を構成する部分順列が共通である前記蓄積順列の中から前記部分順列に従って字母を組み合わせた場合に当該部分順列の最後の字母でハングル文字が完成する前記蓄積順列を特定するための順列特定情報が記録されており、
前記検索手段は、前記ハングル文字単位で前記検索対象が指定された後に前記字母単位で前記検索対象が指定された場合、前記順列特定情報を参照し、前記ハングル文字単位で指定された前記検索対象を字母に分解した順列を前記部分順列とした場合に当該部分順列の最後の字母でハングル文字が完成する前記蓄積順列を特定し、特定された前記蓄積順列から前記ハングル文字単位で指定された前記検索対象を字母に分解した順列に前記字母単位で指定された字母が続く順列を含む前記蓄積順列を検索し、検索された前記蓄積順列が対応付けられた登録名称を検索結果とする、
検索装置。
【請求項２】
前記順列特定情報は、前記部分順列の最後の字母でハングル文字が完成する前記蓄積順列の前記記録媒体上での記録位置を示し、
前記検索手段は、前記順列特定情報が示す前記記録位置に記録された前記蓄積順列が、前記ハングル文字単位で指定された前記検索対象を字母に分解した順列を前記部分順列とした場合に当該部分順列の最後の字母でハングル文字が完成する前記蓄積順列であるとみなす、
請求項１に記載の検索装置。
【請求項３】
検索対象の指定をハングル文字単位または字母単位で受け付けて、記録媒体に蓄積された地図情報に含まれるハングル文字からなる複数の登録名称から、指定された検索対象を含む登録名称を検索する検索工程を含む検索方法であって、
前記記録媒体には、
前記複数の登録名称のそれぞれに各登録名称を示すハングル文字を字母に分解した順列である蓄積順列が対応付けられて記録され、かつ、
前記蓄積順列の一部を構成する部分順列が共通である前記蓄積順列の中から前記部分順列に従って字母を組み合わせた場合に当該部分順列の最後の字母でハングル文字が完成する前記蓄積順列を特定するための順列特定情報が記録されており、
前記検索工程は、前記ハングル文字単位で前記検索対象が指定された後に前記字母単位で前記検索対象が指定された場合、前記順列特定情報を参照し、前記ハングル文字単位で指定された前記検索対象を字母に分解した順列を前記部分順列とした場合に当該部分順列の最後の字母でハングル文字が完成する前記蓄積順列を特定し、特定された前記蓄積順列から前記ハングル文字単位で指定された前記検索対象を字母に分解した順列に前記字母単位で指定された字母が続く順列を含む前記蓄積順列を検索し、検索された前記蓄積順列が対応付けられた登録名称を検索結果とする、
を含む検索方法。
【請求項４】
検索対象の指定をハングル文字単位または字母単位で受け付けて、記録媒体に蓄積された地図情報に含まれるハングル文字からなる複数の登録名称から、指定された検索対象を含む登録名称を検索する検索機能をコンピュータに実現させる検索プログラムであって、
前記記録媒体には、
前記複数の登録名称のそれぞれに各登録名称を示すハングル文字を字母に分解した順列である蓄積順列が対応付けられて記録され、かつ、
前記蓄積順列の一部を構成する部分順列が共通である前記蓄積順列の中から前記部分順列に従って字母を組み合わせた場合に当該部分順列の最後の字母でハングル文字が完成する前記蓄積順列を特定するための順列特定情報が記録されており、
前記検索機能は、前記ハングル文字単位で前記検索対象が指定された後に前記字母単位で前記検索対象が指定された場合、前記順列特定情報を参照し、前記ハングル文字単位で指定された前記検索対象を字母に分解した順列を前記部分順列とした場合に当該部分順列の最後の字母でハングル文字が完成する前記蓄積順列を特定し、特定された前記蓄積順列から前記ハングル文字単位で指定された前記検索対象を字母に分解した順列に前記字母単位で指定された字母が続く順列を含む前記蓄積順列を検索し、検索された前記蓄積順列が対応付けられた登録名称を検索結果とする機能をコンピュータに実現させる、
検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置、検索方法および検索プログラムに関する。
【背景技術】
【０００２】
従来、記録媒体に蓄積されたハングル文字からなる登録名称を検索する際の検索対象の指定方法として、主に、２種類の指定方法が知られていた。すなわち、ハングル文字は、ハングル文字の構成単位である字母（jamo）を複数個組み合わせることによって完成するため、ハングル文字単位で検索対象を指定する方法と字母単位で検索対象を指定する方法との２種類の方法が開発されていた。具体的には、複数個の字母を入力して検索対象のハングル文字を指定する作業を繰り返すことによって検索対象のハングル文字列を指定する構成と、字母を一つずつ入力して検索対象のハングル文字列を構成する字母の順列を指定する字母単位の検索とが知られていた。例えば、特許文献１には、簡単な操作によって字母単位の検索を実行可能にするため、字母の入力順序と確定文字列とを対応付けて予測データとし、次回以降の字母の入力過程において当該予測データを参照して当該字母に対応した確定文字列を候補とする技術が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００２−０８２９４０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ハングル文字単位で検索対象を指定する従来の技術は、登録名称をハングル文字の順列によって示す情報を記録媒体に記録しておき、ハングル文字が指定される度に検索結果とすべき登録名称の候補を絞り込む技術である。一方、字母単位で検索対象を指定する従来の技術は、登録名称を示すハングル文字列を字母に分解した場合の順列を当該登録名称に対応付けておき、字母が指定される度に検索結果とすべき登録名称の候補を絞り込む技術である。このように、ハングル文字単位で検索対象を指定する従来の技術と、字母単位で検索対象を指定する従来の技術とでは、異なる情報に基づいて検索対象を検索する。
【０００５】
また、ハングル文字列を字母に分解した場合の順列を比較すると、異なるハングル文字列同士であっても字母の順列の一部が一致する場合がある。従って、ハングル文字単位での検索対象の指定を行った後に字母単位での検索対象の指定を行う場合に、ハングル文字単位で指定された検索対象を字母に分解した順列に字母単位で指定された字母を加えた順列で登録名称の候補を絞り込もうとしても、字母単位での検索対象の指定を行うことに伴って候補の数が増大することがあり、効率的に検索を行うことができなかった。
本発明は、上記課題に鑑みてなされたものであり、ハングル文字単位での検索対象の指定を行った後に字母単位での検索対象の指定を行う場合に効率的な検索を行うことが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の目的を達成するため、本発明においては、記録媒体に蓄積された地図情報にハングル文字からなる複数の登録名称が含まれる構成において、複数の登録名称のそれぞれに各登録名称を示すハングル文字を字母に分解した順列である蓄積順列を対応付けて記録媒体に記録される。さらに、当該蓄積順列の一部を構成する部分順列が共通である蓄積順列の中から部分順列に従って字母を組み合わせた場合に当該部分順列の最後の字母でハングル文字が完成する蓄積順列を特定するための順列特定情報が記録される。そして、ハングル文字単位で検索対象が指定された後に字母単位で検索対象が指定された場合に、順列特定情報を参照し、ハングル文字単位で指定された検索対象を字母に分解した順列を部分順列とした場合に当該部分順列の最後の字母でハングル文字が完成する蓄積順列を特定する。さらに、特定された蓄積順列から、ハングル文字単位で指定された前記検索対象を字母に分解した順列に字母単位で指定された字母が続く順列を含む蓄積順列を検索し、検索された蓄積順列が対応付けられた登録名称を検索結果とする。
【０００７】
すなわち、本発明においては、ハングル文字単位で検索対象が指定された後に字母単位で検索対象が指定された場合、ハングル文字単位で指定された検索対象を字母に分解すると分解された順列の最後の字母は、必ず、当該字母でハングル文字が完成する字母になる。そこで、部分順列が共通である蓄積順列の中から部分順列に従って字母を組み合わせた場合に当該部分順列の最後の字母でハングル文字が完成する蓄積順列を特定することができるように順列特定情報を定義する構成とした。この構成により、ハングル文字単位で指定された検索対象を字母に分解した場合の順列を部分順列とみなして順列特定情報を参照すれば、蓄積順列の中で部分順列が一致するものの中から、部分順列の最後の字母でハングル文字が完成する蓄積順列を特定することができ、検索対象と比較すべき蓄積順列を絞り込むことが可能になる。従って、ハングル文字単位での検索対象の指定を行った後に字母単位での検索対象の指定を行う場合に、効率的な検索を行うことが可能になる。
【０００８】
ここで、検索装置は、検索対象の指定をハングル文字単位または字母単位で受け付けて、指定された検索対象を含む登録名称を検索することができればよく、本発明においては、ハングル文字単位での検索対象の指定を行った後に字母単位での検索対象の指定を行うことが可能に構成される。むろん、字母単位での検索対象の指定を行った後にハングル文字単位での検索対象の指定を行うことが可能に構成されてもよい。また、検索対象の指定を受け付ける構成は、各種のユーザインタフェースによって実現可能であり、字母やハングル文字の選択肢を表示して当該選択肢の選択を受け付ける構成であっても良いし、矩形等の入力エリアに接触した状態で行われた指の動作から字母やハングル文字の形状の指定を受け付ける構成であっても良く、種々の構成を採用可能である。
【０００９】
記録媒体には、ハングル文字からなる複数の登録名称が含まれる地図情報が記録されている。さらに、登録名称には蓄積順列が対応付けられるとともに、記録媒体には順列特定情報が記録される。地図情報は、道路と道路上あるいは道路周辺の施設とを示す情報であり、当該施設に対しては施設の属性や住所、施設名称等を示す文字情報が対応付けられており、ここでは当該文字情報を登録名称と定義している。そして、当該登録名称は少なくともハングル文字によって表現され、当該登録名称が検索対象と比較されることによって検索が行われる。すなわち、指定された検索対象によって登録名称を絞り込むことによって最終的に検索結果が特定されるように構成されている。
【００１０】
蓄積順列は、登録名称を示すハングル文字列を字母に分解した順列である。すなわち、ハングル文字は複数の字母によって構成されるが、任意のハングル文字を字母に分解する場合に所定の規則で順序立てて分解することとする。そして、地図情報に含まれる登録名称のそれぞれを当該所定の規則で字母に分解して各登録名称に対応付けて蓄積順列とすれば、字母の順列として指定された検索対象と蓄積順列とを比較し、検索対象を含む蓄積順列を特定することによって当該蓄積順列に対応付けられた登録名称を検索することが可能になる。なお、ハングル文字列を字母に分解する場合の所定の規則は予め決められていれば良く、例えば、字母によってハングル文字を構成する場合の順序の逆に分解するなどの規則を採用可能である。
【００１１】
順列特定情報は、蓄積順列の一部を構成する部分順列が共通である蓄積順列の中から部分順列に従って字母を組み合わせた場合に当該部分順列の最後の字母でハングル文字が完成する蓄積順列を特定するための情報であればよい。すなわち、ハングル文字単位で指定された検索対象を字母に分解した場合の順列を部分順列とした場合、当該部分順列が共通であってもハングル文字列が異なり得る。しかし、ハングル文字単位で指定された検索対象を分解して順列を生成した場合、順列の最後の字母でハングル文字が完成するはずである。そこで、順列特定情報は、蓄積順列の中から、部分順列が一致し、かつ、部分順列の最後の字母でハングル文字が完成する蓄積順列と完成しない蓄積順列とを区別できるように構成されていればよい。
【００１２】
検索手段は、指定された検索対象に基づいて登録名称を検索する構成において、順列特定情報を参照し、ハングル文字単位で指定された検索対象を字母に分解した順列を部分順列とした場合に当該部分順列の最後の字母でハングル文字が完成する蓄積順列を特定し、特定された蓄積順列から、ハングル文字単位で指定された前記検索対象を字母に分解した順列に字母単位で指定された字母が続く順列を含む蓄積順列を検索し、検索された蓄積順列が対応付けられた登録名称を検索結果とすることができればよい。すなわち、ハングル文字単位で検索対象が指定された後に字母単位で検索対象が指定された場合には、効率的な検索ができるように検索対象と比較すべき蓄積順列を絞り込むことができればよい。
【００１３】
具体的には、字母単位での検索対象の指定の前にハングル文字単位で検索対象が指定されていた場合、検索対象と比較すべき蓄積順列は、ハングル文字単位で指定された検索対象を字母に分解した場合に最後の字母でハングル文字が完成するような順列を含んでいるはずである。そこで、ハングル文字単位で指定された検索対象を字母に分解した順列を部分順列とみなした場合に、部分順列が一致し、かつ、部分順列の最後の字母でハングル文字が完成するような蓄積順列を順列特定情報によって特定できれば、検索対象と比較すべき蓄積順列を容易に絞り込むことができ、効率的に検索を行うことができる。
【００１４】
さらに、順列特定情報は蓄積順列を絞り込むことができるように定義されていれば良く、その具体的な手法としては各種の手法を採用可能である。例えば、順列特定情報によって、部分順列の最後の字母でハングル文字が完成する蓄積順列の、記録媒体上での記録位置を示すように構成してもよい。この構成においては、順列特定情報が示す記録位置に記録された蓄積順列が、ハングル文字単位で指定された検索対象を字母に分解した順列を部分順列とした場合に当該部分順列の最後の字母でハングル文字が完成する蓄積順列であるとみなすことができ、部分順列の最後の字母でハングル文字が完成する蓄積順列を容易に特定することができる。
【００１５】
なお、記録位置は、当該記録位置に基づいて記録媒体を参照することによって部分順列の最後の字母でハングル文字が完成する蓄積順列を探し当てることができるように設定された情報であれば良く、例えば、記録媒体のアドレスを特定するための情報等を採用可能である。記録媒体の記録位置はアドレス値自体で指定されても良いし、基準のアドレスからの相対値で指定されても良い。後者としては、蓄積順列を示す情報を所定のデータ長で、かつ、順序を対応付けて記録媒体に記述することとし、先頭の蓄積順列からＮ個（Ｎは自然数）目の蓄積順列であることや、Ｎ個目の蓄積順列からＭ個目（ＭはＮ＋１以上の自然数）までの蓄積順列であることを順列特定情報によって示すような構成等を採用可能である。むろん、データ長の記述順序は仮想的に設定された順序であってよく、記録媒体における実際の記録位置が順序通りである場合の他、あるデータを記録する際に当該データの次のデータが記録されているアドレスを示す情報を記録することにより、実際の記録位置が順序通りでなくてもデータの順序を辿ることができるように構成されている場合も含む。
【００１６】
本発明のように、部分順列が共通である蓄積順列の中から、部分順列に従って字母を組み合わせた場合に当該部分順列の最後の字母でハングル文字が完成する蓄積順列を特定することによって効率的に検索を行う手法は、この処理を行う方法やプログラムとしても適用可能である。また、以上のような検索装置、方法、プログラムは、単独の装置として実現される場合もあれば、複数の装置として実現される場合もある。また、車両に備えられる各部と共有の部品を利用して実現される場合もあれば、車両に搭載されない各部と連携して実現される場合もあり、各種の態様を含むものである。また、一部がソフトウェアであり一部がハードウェアであったりするなど、適宜、変更可能である。さらに、検索装置を制御するプログラムの記録媒体としても発明は成立する。むろん、そのソフトウェアの記録媒体は、磁気記録媒体であってもよいし光磁気記録媒体であってもよいし、今後開発されるいかなる記録媒体においても全く同様に考えることができる。
【図面の簡単な説明】
【００１７】
【図１】検索装置を含むナビゲーション装置を示すブロック図である。
【図２】登録名称を検索するための情報を示す図である。
【図３】ユーザインタフェースの例を示す図である。
【図４】字母検索処理を示すフローチャートである。
【図５】ハングル検索処理を示すフローチャートである。
【発明を実施するための形態】
【００１８】
ここでは、下記の順序に従って本発明の実施の形態について説明する。
（１）ナビゲーション装置の構成：
（１−１）施設情報の構成：
（１−２）検索プログラムの構成：
（２）検索処理：
（２−１）字母検索処理：
（２−２）ハングル検索処理：
（３）他の実施形態：
【００１９】
（１）ナビゲーション装置の構成：
図１は、本発明の一実施形態にかかる検索装置として機能するナビゲーション装置の構成を示すブロック図である。本実施形態において検索装置は、ナビゲーション装置１０によって実現される。ナビゲーション装置１０は、ＣＰＵ、ＲＡＭ、ＲＯＭ等を備える制御部２０と記録媒体３０とを備えており、制御部２０は、記録媒体３０やＲＯＭに記憶されたプログラムを実行することができる。本実施形態においては、このプログラムの一つとして複数のプログラムモジュールからなるナビゲーションプログラムを実行可能であり、当該ナビゲーションプログラムを構成する一つのプログラムモジュールとして検索プログラム２１を備えている。ナビゲーションプログラムは、車両の現在位置から目的地までの走行経路を探索し、当該走行経路に従って車両を走行させるための支援を行う機能を制御部２０に実現させるプログラムである。
【００２０】
本実施形態においては、ナビゲーションプログラムによる機能を実現するため、車両にＧＰＳ受信部４０と車速センサ４１とジャイロセンサ４２とユーザＩ／Ｆ部４３とが備えられている。ＧＰＳ受信部４０は、ＧＰＳ衛星からの電波を受信し、図示しないインタフェースを介して車両の現在位置を算出するための信号を出力する。車速センサ４１は、車両が備える車輪の回転速度に対応した信号を出力する。ジャイロセンサ４２は、車両の旋回についての角加速度を検出し、車両の向きに対応した信号を出力する。制御部２０は、ＧＰＳ受信部４０，車速センサ４１，ジャイロセンサ４２等の出力信号および後述する地図情報３０ａに基づいて車両の現在位置を特定する。
【００２１】
ユーザＩ／Ｆ部４３は、ユーザに各種の情報を提供し、またはユーザの指示を入力するためのインタフェース部であり、図示しないタッチパネルディスプレイやスピーカーなどを備えている。制御部２０は、当該ユーザＩ／Ｆ部４３に対して制御信号を出力して任意の画像をタッチパネルディスプレイに表示させ、任意の音声をスピーカーから出力させる。また、制御部２０は、ユーザＩ／Ｆ部４３の出力信号に基づいて利用者の指示内容を特定する。
【００２２】
記録媒体３０には予め地図情報３０ａが記憶されている。地図情報３０ａは、車両が走行する道路上に設定されたノードを示すノードデータ、ノード間の道路の形状を特定するための形状補間点データ、ノード同士の連結を示すリンクデータ、道路あるいは道路の周辺に存在する複数の施設を示す施設情報３０ｂ等を含んでいる。施設情報３０ｂは、複数の施設のそれぞれに対して施設の属性や位置（座標および住所）、施設名称等の情報が対応づけられることによって定義される。
【００２３】
（１−１）施設情報の構成：
本実施形態において、施設情報３０ｂに対応付けられた施設の属性や住所、施設名称はハングル文字によって表現されており、ここでは、これらの属性や住所、施設名称を登録名称と呼び、当該登録名称を示す情報を図１において登録名称情報３０ｂ１として示している。また、図２においては、登録名称情報３０ｂ１の具体例を示している。同図２に示すように登録名称情報３０ｂ１は、各登録名称をハングル文字の順列であるハングル文字列で示す情報である。
【００２４】
本実施形態においては、検索対象を含む登録名称を検索することによって、利用者所望の施設を特定し、目的地に設定することが可能である。本実施形態においては、効率的な検索を行うため、地図情報３０ａの施設情報３０ｂに蓄積順列情報３０ｂ２と順列特定情報３０ｂ３とが含まれている。蓄積順列情報３０ｂ２は、登録名称情報３０ｂ１が示す各登録名称を示すハングル文字を字母に分解した蓄積順列を示す情報であり、各登録名称に対応づけられて定義されている。
【００２５】
例えば、図２に示す登録名称情報３０ｂ１に対して、図２に示すように各登録名称が字母に分解された蓄積順列情報３０ｂ２が対応付けられる。従って、字母の順列を含む蓄積順列を特定すれば、当該字母の順列に分解された元の登録名称を検索結果として特定することができる。ここでは、理解の容易のために蓄積順列情報３０ｂ２が構成する字母の順列を左から順に並べるとともにハングル文字の区切りにアットマークを配置して示している。なお、ハングル文字を字母に分解する場合の所定の規則は予め決められていれば良く、例えば、字母によってハングル文字を構成する場合の順序の逆に分解するなどの規則を採用可能である。
【００２６】
なお、本実施形態において、蓄積順列情報３０ｂ２と登録名称情報３０ｂ１とは固定長のデータ構造であり、記録媒体３０内での最初の登録名称情報３０ｂ１および最初の蓄積順列情報３０ｂ２が記録されるアドレスは予め特定されているとともに、固定長の一つのデータを記録したら次の固定長のデータを一つ記録する作業を繰り返すことにより、所定の記録順序で記録媒体３０に記録される。従って、記録された順序によって、記録媒体３０に記録された蓄積順列情報３０ｂ２と登録名称情報３０ｂ１とを特定することができる。
【００２７】
なお、本実施形態において、所定の記録順序は、蓄積順列を構成する字母が一致する度合いが高いほど近い順序になるとともに、同じ順列の字母が最後の字母となってハングル文字が完成するような蓄積順列が続けて記録媒体３０に記録されるように設定される。例えば、図２においては、記録媒体３０にて記録される順に登録名称情報３０ｂ１に対してＬ1〜Ｌ10の符号を付し、記録媒体３０にて記録される順に蓄積順列情報３０ｂ２に対してＰ1〜Ｐ10の符号を付して示している。そして、図２においては、２番目までの字母が共通する蓄積順列が蓄積順列Ｐ1〜Ｐ7となって連続して記録媒体３０に記録される。さらに、蓄積順列Ｐ1〜Ｐ4は２番目の字母でハングル文字が完成するような蓄積順列であり、蓄積順列Ｐ5〜Ｐ7は３番目の字母でハングル文字が完成するような蓄積順列であるため、両者は分けて記録媒体３０に記録される。すなわち、蓄積順列Ｐ1〜Ｐ4は連続して記録媒体３０に記録されるが、例えば、蓄積順列Ｐ5が蓄積順列Ｐ4よりも先に記録媒体３０に記録されることはない。
【００２８】
本実施形態において、順列特定情報３０ｂ３は、蓄積順列を２種類の蓄積順列に区別するための情報である。すなわち、順列特定情報３０ｂ３は、蓄積順列の一部を構成する部分順列が共通である蓄積順列の中から、部分順列に従って字母を組み合わせた場合に当該部分順列の最後の字母でハングル文字が完成する蓄積順列と、当該部分順列の最後の字母でハングル文字が完成しない蓄積順列とのいずれであるのかを特定するための情報である。ハングル文字列においては、ハングル文字列を字母に分解した場合の順列が共通であっても元のハングル文字列は異なり得るという特性がある。例えば、図２示す登録名称情報３０ｂ１の登録名称Ｌ3および登録名称Ｌ5に着目すると、これらの登録名称を字母に分解した場合の順列は蓄積順列Ｐ3および蓄積順列Ｐ5であり、蓄積順列において１番目の字母から３番目の字母まで共通である。
【００２９】
従って、１番目の字母から３番目の字母までが蓄積順列Ｐ3および蓄積順列Ｐ5のような順列である字母の順列を検索対象として蓄積順列情報３０ｂ２を検索しても、蓄積順列Ｐ3と蓄積順列Ｐ5とを区別することはできない。このため、単に順列のみに基づいて検索を行う構成では、蓄積順列Ｐ3および蓄積順列Ｐ5の双方を検索結果の候補とせざるを得ない。しかし、共通の順列であっても、順列内の字母でハングル文字が完成するか否かに着目すれば、蓄積順列を区別し得る。例えば、図２に示す蓄積順列Ｐ3および蓄積順列Ｐ5を比較すると、蓄積順列Ｐ3の３番目の字母でハングル文字は完成しないが、蓄積順列Ｐ5の３番目の字母でハングル文字は完成する。
【００３０】
そこで、順列特定情報３０ｂ３は、蓄積順列の中から、部分順列が一致し、かつ、部分順列の最後の字母でハングル文字が完成する蓄積順列と完成しない蓄積順列とを区別できるように構成されている。本実施形態においては、順列内のＸ番目（Ｘは０以上の整数）の字母においてハングル文字が完成する蓄積順列を示す蓄積順列情報３０ｂ２の記録位置と、Ｘ番目の字母においてハングル文字が完成しない蓄積順列を示す蓄積順列情報３０ｂ２の記録位置と、蓄積順列を構成するためにＸ番目の字母の次のＸ＋１番目で選択し得る字母と、を示す情報が順列特定情報３０ｂ３として定義されている。
【００３１】
本実施形態において、蓄積順列情報３０ｂ２の記録位置は、記録媒体３０内で最初に現れる蓄積順列の記録順序と該当する蓄積順列の個数によって特定される。すなわち、蓄積順列情報３０ｂ２は、固定長のデータによって管理されるとともに、所定の記録順序で記録媒体３０に記録されるため、固定長のデータを１個の蓄積順列と数えれば、最初に現れる蓄積順列の記録順序と該当する蓄積順列の個数によって、順列内の字母でハングル文字が完成するか否かを区別しながら蓄積順列を指定することができる。例えば、図２に示す例において、「オフセット」は最初に現れる蓄積順列の記録順序を意味し、「個数」は該当する蓄積順列の個数を意味している。
【００３２】
従って、図２において「完成時オフセット」は、Ｘ番目の字母においてハングル文字が完成する蓄積順列が最初に現れる蓄積順列の記録順序を意味し、「非完成時オフセット」は、Ｘ番目の字母においてハングル文字が完成しない蓄積順列が最初に現れる蓄積順列の記録順序を意味している。「個数」は「完成時オフセット」、「非完成時オフセット」のそれぞれに対応付けられており、図２に示す例においては、「完成時オフセット」、「非完成時オフセット」の右側に示す「個数」が「完成時オフセット」、「非完成時オフセット」のそれぞれに対応する。
【００３３】
また、０番目においては順列内の字母が一つも特定されていないため、０番目の字母においてハングル文字が完成しない蓄積順列は存在しない。一方、０番目の字母においてハングル文字が完成する蓄積順列は、蓄積順列情報３０ｂ２が示す全ての蓄積順列である。従って、図２に示す順列特定情報３０ｂ３において、「完成時オフセット」は１、個数は１０となっており、記録順序が１番目の蓄積順列Ｐ1から計１０個の蓄積順列である蓄積順列Ｐ1〜Ｐ10が０番目の字母においてハングル文字が完成する蓄積順列として示されていることになる。
【００３４】
さらに、蓄積順列を構成するためにＸ＋１番目で選択し得る字母を示す情報は、蓄積順列情報３０ｂ２に基づいて予め特定される。例えば、図２に示す例において、蓄積順列の０番目、すなわち、順列内の字母が一つも特定されていない場合において、蓄積順列を構成するために選択可能な選択肢は、蓄積順列情報３０ｂ２の全てから１番目の字母を抽出することによって特定される。図２に示す例において、蓄積順列情報３０ｂ２の１番目の字母は、蓄積順列Ｐ1〜蓄積順列Ｐ8において同一であり、蓄積順列Ｐ9と蓄積順列Ｐ10とで異なるため、１番目の字母はこれらの３種類の字母のいずれかである。従って、図２に示す順列特定情報３０ｂ３において、０番目での次の字母の選択肢は当該３種類の字母Ｊ1〜Ｊ3となっている。
【００３５】
さらに、図２においては、１番目の字母が字母Ｊ1である場合の順列特定情報３０ｂ３の例を示している。１番目の字母Ｊ1でハングル文字が完成する蓄積順列は蓄積順列情報３０ｂ２に登録されていないため、順列特定情報３０ｂ３において、「完成時オフセット」は定義されず、「非完成時オフセット」のみが定義される。また、１番目の字母Ｊ1でハングル文字が完成しない蓄積順列は蓄積順列Ｐ1〜Ｐ8であるため、「非完成時オフセット」が１、個数が８と定義されている。図２においては、以下、２番目の字母が字母Ｊ4、３番目の字母が字母Ｊ7である場合の例を示している。
【００３６】
（１−２）検索プログラムの構成：
ナビゲーションプログラム１０は、ＧＰＳ受信部４０と車速センサ４１とジャイロセンサ４２の出力信号に基づいて車両の現在位置を特定し、地図情報３０ａを参照して予め設定された目的地までの経路を車両が走行するように案内する機能を制御部２０に実現させる。利用者は、地図情報３０ａに含まれる施設情報３０ｂから登録名称を検索し、検索された登録名称が対応付けられた施設を目的地とすることが可能である。本実施形態において、制御部２０は検索部２１ａを備えた検索プログラム２１を実行して施設を検索する。
【００３７】
検索プログラム２１は、ユーザＩ／Ｆ部４３の出力信号に基づいて検索対象を受け付け、検索対象を含む登録名称を検索する機能を制御部２０に実現させる。本実施形態においては、検索対象の指定をハングル文字単位または字母単位で受け付けることが可能である。すなわち、検索プログラム２１は、ユーザＩ／Ｆ部４３に対して制御信号を出力し、ユーザＩ／Ｆ部４３の表示部にハングル文字単位または字母単位での入力を実行可能なインタフェースを表示させる。利用者が当該インタフェースによってハングル文字あるいは字母の入力を行うと、ユーザＩ／Ｆ部４３は、当該インタフェースによる入力内容を示す信号を出力し、制御部２０は、当該信号に基づいて入力内容を受け付ける。
【００３８】
図３は、表示部に表示されるインタフェースの一例を示す図である。同図３に示す例においては、ハングル文字単位または字母単位での入力を受け付ける入力部Ｉが画面左側に表示され、入力されたハングル文字を表示する文字表示部Ｄが画面右側上部に表示されている。さらに、本例においては、入力済の検索対象で検索を実行させるための指示を行うリストボタンＢが画面右側下部に表示されている。ユーザＩ／Ｆ部４３は、入力部Ｉ内で指が接触された位置を検出可能であり、指の動作に応じた接触位置の変化を示す信号を出力する。そして、制御部２０は、当該接触位置の変化が示す指の動作に基づいて利用者が指示した字母を特定する。また、利用者が字母を特定する作業を連続的に行って、ハングル文字を完成させた場合には、そのハングル文字を特定する。すなわち、制御部２０は、各字母が入力された後、一定期間以上他の字母が入力されない場合、字母単位での指定を受け付け、一定期間内に他の字母が入力された場合は複数の字母を組み合わせたハングル文字単位で指定を受け付ける。そして、制御部２０は、受け付けた内容を検索対象とする。
【００３９】
以上の構成において、利用者がハングル文字単位のみで検索対象を指定した場合、制御部２０は、検索プログラム２１の処理により、登録名称情報３０ｂ１を参照し、指定された検索対象を含む登録名称を検索する。また、制御部２０は、ユーザＩ／Ｆ部４３に対して制御信号を出力し、検索された登録名称を表示部に表示させる。利用者は、表示された登録名称を視認し、さらに、登録名称が示す施設を目的地にするための作業を行うことができる。また、利用者が字母単位のみで検索対象を指定した場合、制御部２０は、検索プログラム２１の処理により、蓄積順列情報３０ｂ２を参照し、指定された検索対象を含む蓄積順列を検索する。１個以上の蓄積順列が検索された場合、制御部２０は、検索された蓄積順列に対応する登録名称情報３０ｂ１を特定し、ユーザＩ／Ｆ部４３に対して制御信号を出力して当該登録名称情報３０ｂ１が示す登録名称を表示部に表示させる。利用者は、表示された登録名称を視認し、さらに、登録名称が示す施設を目的地にするための作業を行うことができる。
【００４０】
一方、利用者が、ハングル文字単位での検索対象の指定を行った後、字母単位での検索対象の指定を行った場合、本実施形態において制御部２０は、検索部２１ａの処理により、順列特定情報３０ｂ３を利用した効率的な検索を実行する。すなわち、検索部２１ａは、ハングル文字単位で検索対象が指定された後に字母単位で検索対象が指定された場合、順列特定情報を参照し、検索対象と比較するまでもなく検索結果とすべきでない蓄積順列を除外し、残りの蓄積順列と検索対象とを比較する機能を制御部２０に実現させるモジュールである。
【００４１】
具体的には、ハングル文字単位で検索対象が指定された後に字母単位で検索対象が指定された場合、制御部２０は、検索部２１ａの処理により、ハングル文字単位で指定された検索対象を字母に分解した順列を部分順列とした場合に当該部分順列の最後の字母でハングル文字が完成する蓄積順列を特定する。さらに、制御部２０は、検索部２１ａの処理により、特定された蓄積順列から、ハングル文字単位で指定された前記検索対象を字母に分解した順列に字母単位で指定された字母が続く順列を含む蓄積順列を検索し、検索された蓄積順列が対応付けられた登録名称を検索結果とする。
【００４２】
すなわち、ハングル文字単位で検索対象が指定された後に字母単位で検索対象が指定された場合、ハングル文字単位で指定された検索対象を字母に分解すると分解された順列の最後の字母は、必ず、当該字母でハングル文字が完成する字母になる。また、順列特定情報３０ｂ３は、部分順列が共通である蓄積順列の中から部分順列に従って字母を組み合わせた場合に当該部分順列の最後の字母でハングル文字が完成する蓄積順列を特定することができるように定義されている。そこで、制御部２０は、順列特定情報を参照してハングル文字単位で指定された検索対象を字母に分解した場合の順列を部分順列とみなし、蓄積順列の中で部分順列が一致するものの中から、部分順列の最後の字母でハングル文字が完成する蓄積順列を特定することで、検索対象と比較すべき蓄積順列を絞り込む構成を採用している。
【００４３】
例えば、図２に示す例において、利用者が字母Ｊ1および字母Ｊ4からなるハングル文字（例えば、登録名称Ｌ1の１文字目など）をハングル文字単位で指定した後に、字母Ｊ7を字母単位で指定した場合、制御部２０は、検索部２１ａの処理により、ハングル文字単位で指定された検索対象を字母の順列に分解する。すなわち、登録名称Ｌ1の１文字目などのハングル文字を分解し、字母Ｊ1，字母Ｊ4という順列を生成する。次に、制御部２０は、順列特定情報３０ｂ３を参照し、字母Ｊ1，字母Ｊ4という順列を部分順列とした場合に、当該部分順列の最後の字母でハングル文字が完成する蓄積順列を特定する。図２に示す例において、字母Ｊ1，字母Ｊ4という順列を含む蓄積順列は蓄積順列Ｐ1〜Ｐ8の計８個であるが、順列特定情報３０ｂ３には「完成時オフセット」が１であり、「個数」が４と定義されているため、当該順列を部分順列とした場合に、部分順列の最後の字母Ｊ4でハングル文字が完成する蓄積対象は蓄積順列Ｐ1〜Ｐ4の計４個であることが判明する。
【００４４】
そこで、制御部２０は、蓄積順列Ｐ1〜Ｐ4から、字母Ｊ1，字母Ｊ4という順列に字母単位で指定された字母Ｊ7を加えた順列である字母Ｊ1，字母Ｊ4，字母Ｊ7を含む蓄積順列を検索して検索結果とする。従って、図２に示す例においては、蓄積順列Ｐ1〜Ｐ4から検索された蓄積順列Ｐ4が検索結果となる。以上の構成によれば、字母Ｊ1，字母Ｊ4，字母Ｊ7を含む蓄積順列を検索する際に、字母Ｊ1，字母Ｊ4，字母Ｊ7という順列の検索対象と比較されるべき蓄積順列の個数が８個ではなく４個となる。従って、ハングル文字単位での検索対象の指定を行った後に字母単位での検索対象の指定を行う場合に、検索対象と比較すべき蓄積順列を絞り込むことができ、効率的な検索を行うことが可能になる。
【００４５】
（２）検索処理：
次に、本実施形態にかかる検索処理を詳細に説明する。図４は、字母単位で指定された検索対象の検索を行う字母検索処理、図５は、ハングル文字単位で指定された検索対象の検索を行うハングル検索処理である。後述するように、入力単位に応じて字母検索処理の過程でハングル検索処理が実行され、また、ハングル検索処理の過程で字母検索が実行されることもあり得るが、本実施形態において制御部２０は、まず図４に示す字母検索処理を実行する。なお、本実施形態においては、図４および図５に示す処理の過程で利用者に検索対象を指定させ、新たな検索対象が指定された場合には既存の検索対象に新たな検索対象を追加することによって検索対象となる字母あるいはハングル文字の数を増加させて検索結果を絞り込む処理が行われる。
【００４６】
（２−１）字母検索処理：
図４に示す字母検索処理の実行が開始されると、制御部２０は、検索部２１ａの処理により、リストボタンが押されたか否かを判定する（ステップＳ１００）。例えば、図３に示すユーザインタフェースにおいて、「ｌｉｓｔ」と表示されたリストボタンＢに利用者が触れるとユーザＩ／Ｆ部４３が当該リストボタンＢに対する接触を示す信号を出力する。制御部２０は、当該ユーザＩ／Ｆ部４３からの出力信号に基づいて、リストボタンＢが押されたと判定する。
【００４７】
ステップＳ１００にてリストボタンが押されたと判定された場合、制御部２０は、検索対象を含む登録名称を検索する（ステップＳ１４５）。本実施形態においては、図４に示す字母検索処理が最初に実行された場合と、後述する図５の処理過程で字母単位の入力が行われることで図４に示す字母検索処理が実行された場合に当該ステップＳ１００が実行される。前者の場合、検索対象が未入力であるため、ステップＳ１４５において制御部２０は、蓄積順列情報３０ｂ２が示す全ての蓄積順列を検索結果とする。
【００４８】
後者の場合、後述する図５の処理過程で指定されたハングル文字列と当該ハングル文字列に続く字母とが検索対象となる。この場合、制御部２０は、当該ハングル文字列を字母の順列に分解した場合の順列を部分順列として特定する。そして、制御部２０は、順列特定情報３０ｂ３を参照し、当該部分順列が一致するとともに部分順列の最後の字母でハングル文字が完成する蓄積順列から、検索対象の順列（ハングル文字単位で指定された検索対象を字母に分解した順列に字母単位で指定された字母が続く順列）を含む蓄積順列を検索する。
【００４９】
例えば、図５の処理過程で字母Ｊ1，字母Ｊ4からなるハングル文字が検索対象として指定され、その後に字母Ｊ7が検索対象として指定された場合、図５の処理過程で指定されたハングル文字列を字母に分解した場合の順列は字母Ｊ1，字母Ｊ4という順列であり、部分順列は字母Ｊ1，字母Ｊ4という順列になる。また、検索対象となる順列は字母Ｊ1，字母Ｊ4，字母Ｊ7という順列になる。そこで、制御部２０は、順列特定情報３０ｂ３を参照し、当該部分順列（字母Ｊ1，字母Ｊ4）が一致するとともに字母Ｊ4でハングル文字が完成する蓄積順列を特定する。図２においては、１番目の字母が字母Ｊ1、２番目の字母が字母Ｊ4、３番目の字母が字母Ｊ7である場合の順列特定情報３０ｂ３を示しているため、制御部２０は、当該図２に示す２番目の順列に関する順列特定情報３０ｂ３を参照し、字母Ｊ4でハングル文字が完成する蓄積順列の「完成時オフセット」が１、「個数」が４であると特定する。
【００５０】
この結果、字母Ｊ4でハングル文字が完成する蓄積順列が、蓄積順列Ｐ1〜Ｐ4であることが特定される。そこで、制御部２０は、蓄積順列Ｐ1〜Ｐ4の中から、検索対象となる順列である字母Ｊ1，字母Ｊ4，字母Ｊ7という順列を含む蓄積順列Ｐ4を特定し、検索結果とする。従って、部分順列が一致する全ての蓄積順列である蓄積順列Ｐ1〜Ｐ8を参照することなく、より限定された蓄積順列Ｐ1〜Ｐ4の中から、検索対象となる順列を含む蓄積順列を検索すれば良く、効率的に検索を行うことが可能になる。このような効率性の向上効果は、一般的な地図情報３０ａに含まれる施設情報３０ｂのように、極めて多数の登録名称が含まれる情報に基づく検索において特に顕著に現れる。
【００５１】
検索結果を取得すると、制御部２０は、検索結果を表示するとともに目的地とするための選択を受け付ける（ステップＳ１５０）。すなわち、制御部２０は、検索結果として得られた蓄積順列に対応する登録名称を特定し、ユーザＩ／Ｆ部４３に対して制御信号を出力して当該登録名称を表示する。さらに、制御部２０は、ユーザＩ／Ｆ部４３の出力信号に基づいて、表示された登録名称の選択を受け付ける。
【００５２】
一方、ステップＳ１００にて、リストボタンが押されたと判定されない場合、制御部２０は、検索対象の最後の字母の次に選択可能な字母およびハングル文字を特定する（ステップＳ１０５）。当該処理において、制御部２０は、まず検索対象の字母の順列を特定する。すなわち、検索対象が字母単位のみによって指定された場合、制御部２０は、字母が指定された順序通りの順列を検索対象の字母の順列とする。また、検索対象にハングル文字単位で指定された文字が含まれる場合、制御部２０は、当該文字を字母に分解した順列に対して字母単位で指定された字母が指定された順に加えられた順列を生成し、検索対象の字母の順列とする。さらに、検索対象が未入力の場合、制御部２０は、検索対象の最後の字母は任意の字母であるとみなす。
【００５３】
そして、制御部２０は、検索対象の字母の順列に従って順列特定情報３０ｂ３を参照し、検索対象の字母の順列の最後の字母に関する順列特定情報３０ｂ３に対応付けられた「次の字母の選択肢」によって検索対象の最後の字母の次に選択可能な字母を特定する。例えば、図２においては、１番目の字母が字母Ｊ1、２番目の字母が字母Ｊ4である場合の順列特定情報３０ｂ３を示しているため、検索対象の字母の順列が字母Ｊ1，字母Ｊ4である場合、制御部２０は、当該図２に示す２番目の順列に関する順列特定情報３０ｂ３を参照し、「次の字母の選択肢」が字母Ｊ6〜Ｊ8であると特定し、字母Ｊ6〜Ｊ8を検索対象の最後の字母の次に選択可能な字母であるとする。
【００５４】
また、図４に示す字母検索処理において、後述するステップＳ１３５が実行されると、その後にはハングル文字単位での入力を行うことが可能になる。そこで、ステップＳ１０５においては、検索対象の最後の字母の次に選択可能なハングル文字も特定する構成になっている。具体的には、制御部２０は、検索対象の字母の順列の最後の字母に関する順列特定情報３０ｂ３に対応付けられた「完成時オフセット」および「個数」によって、検索対象の最後の字母でハングル文字が完成する蓄積順列を特定し，当該蓄積順列において、検索対象の字母の順列の次に位置するハングル文字を特定する。図２において、検索対象の字母の順列が字母Ｊ1，字母Ｊ4である場合、制御部２０は、当該図２に示す２番目の順列に関する順列特定情報３０ｂ３を参照し、「完成時オフセット」が１、「個数」が４で示される蓄積順列Ｐ1〜Ｐ4および対応する登録名称Ｌ1〜Ｌ4を参照し、字母Ｊ1，字母Ｊ4の次に位置するハングル文字を特定する。図２に示す例においては、登録名称Ｌ1，Ｌ2の２文字目と登録名称Ｌ3の２文字目と登録名称Ｌ4の２文字目とが検索対象の最後の字母の次に選択可能なハングル文字として特定される。
【００５５】
次に、制御部２０は、入力部Ｉに対する利用者の入力を受け付ける（ステップＳ１１０）。ここで、制御部２０は、ユーザＩ／Ｆ部４３の出力信号が示す利用者の入力内容が、ステップＳ１０５にて特定された「次に選択可能な字母」と一致する場合、あるいはステップＳ１０５にて特定された「次に選択可能なハングル文字」と一致する場合にのみ利用者の入力を受け付ける。
【００５６】
次に、制御部２０は、ステップＳ１１０において受け付けた入力の入力単位が字母単位、ハングル文字単位のいずれであったのかを判定する（ステップＳ１１５）。すなわち、制御部２０は、ステップＳ１１０にて受け付けた入力が字母の場合は字母単位、ハングル文字の場合はハングル文字単位で指定が行われたとみなす。ステップＳ１１５にて、入力単位がハングル文字であったと判定された場合、入力されたハングル文字を既存の検索対象に加えて新たな検索対象に設定し、図５に示すハングル検索の実行を開始する。
【００５７】
一方、ステップＳ１１５にて、入力単位が字母であったと判定された場合、制御部２０は、ステップＳ１１０にて入力された字母でハングル文字が完成するか否かを判定する（ステップＳ１２０）。すなわち、制御部２０は、順列特定情報３０ｂ３を参照し、ステップＳ１１０にて入力された字母が検索対象の字母の順列の最後である場合に当該最後の字母でハングル文字が完成するか否かを判定する。例えば、検索対象の字母の順列が字母Ｊ1，字母Ｊ4である段階でステップＳ１１０にてさらに字母Ｊ7が入力された場合、検索対象の字母の順列の最後は字母Ｊ7である。そこで、制御部２０は、図２に示す順列特定情報３０ｂ３の３番目の順列に関する「完成時オフセット」の「個数」を特定する。そして、当該「個数」が０ではない場合に、ステップＳ１１０にて入力された字母でハングル文字が完成すると判定する。
【００５８】
ステップＳ１２０にて、入力された字母でハングル文字が完成すると判定されない場合、制御部２０は、リストボタンをトーンダウンさせ（ステップＳ１２５）、ステップＳ１０５以降の処理を繰り返す。すなわち、制御部２０は、リストボタンによる検索実行指示が受け付けられない状態とし、また、ステップＳ１１０にて入力された字母を検索対象に加えて新たな検索対象に設定した後、さらなる字母の入力を受け付ける処理を行う。
【００５９】
一方、ステップＳ１２０にて、入力された字母でハングル文字が完成すると判定された場合、制御部２０は、リストボタンをトーンアップさせる（ステップＳ１３０）。すなわち、制御部２０は、リストボタンによる検索実行指示を実行可能な状態とする。次に制御部２０は、ハングル文字を入力可能に設定する（ステップＳ１３５）。すなわち、制御部２０は、当該ステップＳ１３５以降において、入力部Ｉに対する入力内容として字母のみならずハングル文字も受け付ける状態となる。
【００６０】
次に、制御部２０は、リストボタンが押されたか否かを判定し（ステップＳ１４０）、リストボタンが押されたと判定されない場合にはステップＳ１０５以降の処理を繰り返す。すなわち、ステップＳ１１０にて入力された字母を検索対象に加えて新たな検索対象に設定した後、さらなる字母の入力を受け付ける処理を行う。
【００６１】
一方、ステップＳ１４０において、リストボタンが押されたと判定された場合、制御部２０は、ステップＳ１４５，Ｓ１５０を実行する。ステップＳ１１０〜Ｓ１４０を経てステップＳ１４５が実行される場合、検索対象が未入力ということはない。そこで、制御部２０は、検索対象に、ハングル文字単位で指定されたハングル文字が含まれる場合、制御部２０は、当該ハングル文字列を字母の順列に分解した場合の順列を部分順列として特定する。そして、制御部２０は、順列特定情報３０ｂ３を参照し、当該部分順列が一致するとともに部分順列の最後の字母でハングル文字が完成する蓄積順列から、検索対象となる順列（ハングル文字単位で指定された検索対象を字母に分解した順列に字母単位で指定された字母が続く順列）を含む蓄積順列を検索する。一方、検索対象に、ハングル文字単位で指定されたハングル文字が含まれず、字母のみによって当該検索対象が構成される場合、制御部２０は、蓄積順列情報３０ｂ２を参照して当該検索対象の順列を含む蓄積順列を検索する。ステップＳ１５０は、上述の処理と同様である。
【００６２】
（２−２）ハングル検索処理：
次に、ステップＳ１１５にて、入力単位がハングル文字であったと判定された場合に実行される図５のハングル検索処理を説明する。ハングル検索処理において、制御部２０は、検索対象のハングル文字列の次に選択可能なハングル文字を特定する（ステップＳ２００）。このため、制御部２０は、まず検索対象を指定した際の入力単位に基づいて検索対象のハングル文字列を特定する。すなわち、全ての検索対象がハングル文字単位で指定されている場合、制御部２０は、ハングル文字が指定された順序に従って形成される文字列を検索対象のハングル文字列とする。一方、検索対象を指定する際に字母単位での指定も行われていた場合、検索対象はハングル文字と字母とによって構成される。この場合、制御部２０は、字母によって構成される部分をハングル文字に変換する。ここでは、所定の規則で字母によって構成される部分をハングル文字に変換することができればよく、例えば、できるだけ少数の字母でハングル文字を構成するような規則や、できるだけ多数の字母でハングル文字を構成するような規則や、連続する字母によって字母を余らせることなくハングル文字を構成するような規則等を採用可能である。そして、制御部２０は、変換されたハングル文字とハングル文字単位で指定されたハングル文字とを組み合わせて検索対象のハングル文字列とする。
【００６３】
以上のようにして検索対象のハングル文字列を構成すると、制御部２０は、登録名称情報３０ｂ１を参照し、検索対象のハングル文字列を含む登録名称を検索する。そして、検索された登録名称のそれぞれにおいて、検索対象のハングル文字列の次に位置するハングル文字を特定する。例えば、図２に示す例において、ハングル文字単位で字母Ｊ1，字母Ｊ4からなるハングル文字が指定された場合、制御部２０は、登録名称情報３０ｂ１に基づいて、登録名称Ｌ1，Ｌ2の２文字目と登録名称Ｌ3の２文字目と登録名称Ｌ4の２文字目とを検索対象の最後の字母の次に選択可能なハングル文字として特定する。
【００６４】
また、図５に示すハングル索処理において、後述するステップＳ２１０では、字母単位での入力も受け付ける構成となっている。そこで、ステップＳ２００においては、検索対象のハングル文字列の次に選択可能な字母も特定する構成になっている。このために、制御部２０は、登録名称情報３０ｂ１に基づいて特定された検索対象のハングル文字列の次に位置するハングル文字を分解し、その先頭の字母を検索対象のハングル文字列の次に選択可能な字母として特定する。例えば、図２に示す登録名称Ｌ1，Ｌ2の２文字目と登録名称Ｌ3の２文字目と登録名称Ｌ4の２文字目とが検索対象のハングル文字列の次に位置するハングル文字である場合、字母Ｊ1を検索対象の最後の字母の次に選択可能なハングル文字として特定する。
【００６５】
次に、制御部２０は、リストボタンが押されたか否かを判定する（ステップＳ２０５）。ステップＳ２０５にて、リストボタンが押されたと判定されない場合、制御部２０は、入力部Ｉに対する利用者の入力を受け付け（ステップＳ２１０）、入力単位が字母単位、ハングル文字単位のいずれであったのかを判定する（ステップＳ２１５）。すなわち、制御部２０は、ユーザＩ／Ｆ部４３の出力信号が示す利用者の入力内容が、あるいはステップＳ２００にて特定された「次に選択可能なハングル文字」と一致する場合、ステップＳ２００にて特定された「次に選択可能な字母」と一致する場合にのみ利用者の入力を受け付ける。また、制御部２０は、ステップＳ２１０にて受け付けた入力がハングル文字の場合はハングル文字単位、字母の場合は字母単位で指定が行われたとみなす。
【００６６】
ステップＳ２１５にて、入力単位がハングル文字であったと判定された場合、入力されたハングル文字を既存の検索対象に加えて新たな検索対象に設定し、ステップＳ２００以降の処理を繰り返す。ステップＳ２１５にて、入力単位が字母であったと判定された場合、入力された字母を既存の検索対象に加えて新たな検索対象に設定し、図４に示す字母検索処理を開始する。
【００６７】
一方、ステップＳ２０５にて、リストボタンが押されたと判定された場合、制御部２０は、検索対象のハングル文字列を含む登録名称を検索する（ステップＳ２２０）。すなわち、制御部２０は、登録名称情報３０ｂ１を参照し、検索対象のハングル文字列を含む登録名称を検索結果として取得する。検索結果を取得すると、制御部２０は、検索結果をユーザＩ／Ｆ部４３の表示部に表示するとともに、ユーザＩ／Ｆ部４３を介して目的地とするための選択を受け付ける（ステップＳ２２５）。
【００６８】
（３）他の実施形態：
以上の実施形態は、本発明を実施するための一例であり、部分順列が共通である蓄積順列の中から、部分順列に従って字母を組み合わせた場合に当該部分順列の最後の字母でハングル文字が完成する蓄積順列を特定することによって効率的に検索を行う限りにおいて他にも種々の実施形態を採用可能である。例えば、検索対象の指定を受け付ける構成は、表示部に指を接触させた状態での指の動作に限定されず、各種のユーザインタフェースによって実現可能である。例えば、字母やハングル文字の選択肢を表示して当該選択肢の選択を受け付ける構成であっても良い。
【００６９】
さらに、順列特定情報によって、蓄積順列の記録媒体上での記録位置を示すための構成は種々の構成を採用可能である。すなわち、記録位置は、当該記録位置に基づいて記録媒体を参照することによって部分順列の最後の字母でハングル文字が完成する蓄積順列を探し当てることができるように設定された情報であれば良い。従って、記録媒体の記録位置はアドレス値自体で指定されても良い。さらに、上述の実施形態においては、「オフセット」によって先頭の蓄積順列からＮ個（Ｎは自然数）目の蓄積順列であることを示し、「個数」でＮ個目の蓄積順列からＭ個目（ＭはＮ＋１以上の自然数）までの蓄積順列が対象となることを示していたが、この構成に限らず、データ長の記述順序は仮想的に設定された順序であってよい。従って、記録媒体における実際の記録位置が順序通りである場合の他、あるデータを記録する際に当該データの次のデータが記録されているアドレスを示す情報を記録することにより、実際の記録位置が順序通りでなくてもデータの順序を辿ることができるように構成されている場合も含む。
【符号の説明】
【００７０】
１０…ナビゲーションプログラム、２０…制御部、２１…検索プログラム、２１ａ…検索部、３０…記録媒体、３０ａ…地図情報、３０ｂ…施設情報、３０ｂ１…登録名称情報、３０ｂ２…蓄積順列情報、３０ｂ３…順列特定情報、４０…ＧＰＳ受信部、４１…車速センサ、４２…ジャイロセンサ、４３…ユーザＩ／Ｆ部
【図１】
2012133734.tif 000003
【図２】
2012133734.tif 000004
【図３】
2012133734.tif 000005
【図４】
2012133734.tif 000006
【図５】
2012133734.tif 000007