(57)【特許請求の範囲】
【請求項１】
曖昧さを含む入力文字列を検索キーとして検索処理を行い、検索テキストを取得する検索装置において、
前記検索テキストを単語ごとに分割した単語文字列データを格納する単語辞書と、
前記入力文字列と前記単語辞書に格納された単語文字列データとの照合を行い、前記入力文字列と類似する単語文字列データを検索し、検索された単語文字列データを類似単語候補として取得する単語辞書検索部と、前記単語辞書検索部が取得した類似単語候補からあらかじめ設定した閾値に従って類似単語候補を選択する類似単語候補数制御部とを備えた類似単語候補取得部と、
前記類似単語候補数制御部が選択した各類似単語候補と前記入力文字列との編集距離を算出し、算出した編集距離が所定の距離以内の類似単語候補を類似単語として選択する類似単語選択部と、
前記検索テキストを格納した検索用索引データ蓄積部と、
前記検索用索引データ蓄積部を参照し、前記類似単語選択部が選択した類似単語を含む検索テキストを検索するテキスト検索部とを備え、
前記類似単語候補取得部は、前記入力文字列の文字数の大小を判定し、文字数が大きい場合には文字数が小さい場合に比べ、選択する類似単語候補の数が小さくなるように前記閾値を算出する入力文字数判定部を備えたことを特徴とする検索装置。
【請求項２】
前記類似単語候補取得部は、前記入力文字列が複数の単語で構成される場合に、前記入力文字列の単語数の大小を判定し、判定結果に応じて前記閾値を算出する入力単語数判定部を備えたことを特徴とする請求項１記載の検索装置。
【請求項３】
前記類似単語候補取得部は、前記入力文字列があらかじめ設定された特定文字列に合致するか否か判定を行い、判定結果に応じた前記閾値を取得する特定文字列判定部を備えたことを特徴とする請求項１記載の検索装置。
【請求項４】
前記類似単語候補取得部は、当該検索装置の演算負荷を取得して当該演算負荷の高低を判定し、判定結果に応じて前記閾値を算出する演算負荷判定部を備えたことを特徴とする請求項１記載の検索装置。
【請求項５】
類似する文字列の組み合わせを定義した類似文字列重みテーブルと、
前記類似単語候補取得部は、前記類似文字列重みテーブルを参照して前記入力文字列を類似文字列に展開する類似文字列展開部とを備え、
前記単語辞書検索部は、前記入力文字列および前記類似文字列展開部が展開した類似文字列と、前記単語辞書に格納された単語文字列データとの照合を行い、前記入力文字列および前記展開した類似文字列に類似する単語文字列データを検索し、前記類似単語候補として取得することを特徴とする請求項１記載の検索装置。
【請求項６】
前記類似単語選択部が選択した類似単語と前記入力文字列を比較し、前記類似単語のうち先頭文字列が前記入力文字列と一致する複数の類似単語を検索し、検索した複数の類似単語を統合する類似単語統合部を備え、
前記テキスト検索部は、前記検索用索引データ蓄積部を参照し、前記類似単語統合部が統合した類似単語を含む検索テキストを検索することを特徴とする請求項１記載の検索装置。
【請求項７】
前記入力文字列が複数の単語で構成される場合に、当該入力文字列を単語ごとに分割した分割済入力文字列を生成する入力文字列分割部と、
前記テキスト検索部が検索した検索テキストに基づいて、前記分割済入力文字列の全てに対して、前記類似単語候補取得部、前記類似単語選択部および前記テキスト検索部の処理がおこなわれたか否か判定を行う処理残単語数判定部と、
前記処理残単語数判定部が前記分割済入力文字列の全てに対して前記処理が行われたと判定した場合に、前記テキスト検索部が検索した各検索テキストを統合する検索結果統合部とを備えたことを特徴とする請求項１記載の検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、正式名称のみではなく、略称やうろ覚えの名称などを検索キーとして、あらかじめ登録されたデータ内を曖昧検索する検索装置に関するものである。
【背景技術】
【０００２】
検索装置を用いて住所や施設名を検索する場合、利用者は必ずしも正確な名称を記憶しておらず、通称や略称、うろ覚えの誤った名称などを検索キーとして検索する場合がある。また、カーナビゲーションやスマートフォンのように、入力デバイスとしてキーボードを有さない端末や機器においては、マイクを介して入力された音声信号を音声認識した結果や、タッチパネルを介した入力を文字認識した結果などから検索を行う場合もある。これらの入力デバイスを用いる入力の際には、認識誤りや打鍵誤りなど利用者の操作ミスによる入力誤りが存在する。
通称や略称、うろ覚えの誤った名称などを検索キーとする場合、あるいは利用者による入力誤りが存在する場合のいずれの場合にも、正式名称のみではなく、文字列あるいは発音が類似する名称を曖昧検索する技術が必要となる。【０００３】
曖昧検索を行う技術として、例えば特許文献１がある。特許文献１には、入力されたキーワードから部分文字列の一致度を用いて類似語候補を検索し、さらにこれらの類似語候補から入力キーワードと編集距離の近い類似語を抽出して検索キーワードに追加することで曖昧な全文検索を行う技術が開示されている。例えば、「アセトアルデヒド」が検索キーワードとして入力されると、その部分文字列である「アセト」「アルデ」「ヒド」などを含む類似語候補、例えば「アセトアルデイド」や「アセトアルドール」などの類似語候補が検索される。次に、入力キーワード「アセトアルデヒド」と各類似語候補との編集距離を計算し、このうち編集距離が小さい類似語「アセトアルデイド」も用いて全文検索を行うことにより、検索漏れを抑制している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−１１０７８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した特許文献１に開示された技術では、編集距離の計算コストが非常に大きく、類似語の候補が多数存在する場合には長い計算時間を要するという課題があった。なお、特許文献１では、部分文字列の一致度を用いることで事前に類似語候補を絞り込んでいるものの、カーナビゲーションなどの組み込み機器上で検索漏れが生じないように多数の類似語候補に対して編集距離を計算することは困難であるという課題があった。【０００６】
また、上述した特許文献１に開示された技術では、類似検索を行う際の曖昧性に影響を与える入力文字数や入力単語数を考慮していないため、これらのパラメータに応じて検索精度と検索速度性能を両立することが困難であるという課題がった。【０００７】
さらに、上述した特許文献１に開示された技術では、類似語候補の検索の際に、字面の似ている単語のみを対象としているため、打鍵誤りや音声認識誤りにより字面上の類似性が小さくなる類似単語の検索が困難であるという課題があった。また、全文検索処理において、類似語候補間の類似性を考慮していないため、不要な全文検索処理を繰り返す可能性があり、検索処理の高速化が困難であるという課題があった。【０００８】
この発明は上記のような課題を解決するためになされたもので、検索漏れを抑制し、且つ高速な検索処理を実現すると共に、検索漏れの抑制と処理の高速性のバランスを考慮した検索処理を実現する検索装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
この発明に係る検索装置は、検索テキストを単語ごとに分割した単語文字列データを格納する単語辞書と、入力文字列と単語辞書に格納された単語文字列データとの照合を行い、入力文字列と類似する単語文字列データを検索し、検索された単語文字列データを類似単語候補として取得する単語辞書検索部と、単語辞書検索部が取得した類似単語候補からあらかじめ設定した閾値に従って類似単語候補を選択する類似単語候補数制御部とを備えた類似単語候補取得部と、類似単語候補数制御部が選択した各類似単語候補と入力文字列との編集距離を算出し、算出した編集距離が所定の距離以内の類似単語候補を類似単語として選択する類似単語選択部と、検索テキストを格納した検索用索引データ蓄積部と、検索用索引データ蓄積部を参照し、類似単語選択部が選択した類似単語を含む検索テキストを検索するテキスト検索部とを備え、類似単語候補取得部は、入力文字列の文字数の大小を判定し、文字数が大きい場合には文字数が小さい場合に比べ、選択する類似単語候補の数が小さくなるように前記閾値を算出する入力文字数判定部を備えるものである。
【発明の効果】
【００１０】
この発明によれば、検索漏れを抑制した高速な検索処理を可能とし、さらに検索漏れの抑制と処理の高速性のバランスを考慮した検索処理を行うことができる。
【図面の簡単な説明】
【００１１】
【図１】実施の形態１による検索装置の構成を示すブロック図である。
【図２】実施の形態１による検索装置の動作を示すフローチャートである。
【図３】実施の形態１による検索装置であって、複数単語を処理する構成を示すブロック図である。
【図４】実施の形態１による検索装置であって、複数単語を処理する動作を示すフローチャートである。
【図５】実施の形態１による検索装置の類似単語候補取得部および単語辞書の構成を示すブロック図である。
【図６】実施の形態１による検索装置の特定文字列テーブルの一例を示す図である。
【図７】実施の形態１による検索装置の単語文字列テーブルおよび文字列バイグラム索引の一例を示す図である。
【図８】実施の形態１による検索装置の類似単語候補取得部の動作を示すフローチャートである。
【図９】実施の形態１による検索装置の類似単語選択部の構成を示すブロック図である。
【図１０】実施の形態１による検索装置の類似単語選択部の動作を示すフローチャートである。
【図１１】実施の形態１による検索装置の名称検索用索引データ蓄積部の構成を示すブロック図である。
【図１２】実施の形態１による検索装置の名称リストの一例を示す図である。
【図１３】実施の形態２による検索装置の構成を示すブロック図である。
【図１４】実施の形態２による検索装置の動作を示すフローチャートである。
【図１５】実施の形態２による検索装置の類似単語候補取得部および単語辞書の構成を示すブロック図である。
【図１６】実施の形態２による検索装置の類似単語候補展開検索部の動作を示すフローチャートである。
【図１７】実施の形態２による検索装置の類似文字列重みテーブルの一例を示す図である。
【図１８】実施の形態３による検索装置の構成を示すブロック図である。
【図１９】実施の形態３による検索装置の動作を示すフローチャートである。
【図２０】実施の形態３による検索装置の類似単語統合部の動作を示すフローチャートである。
【発明を実施するための形態】
【００１２】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
なお、以下では本発明の検索装置として、カーナビゲーションにおける施設名検索を例として説明するが、本発明はカーナビゲーションの施設名検索に限定されるものではなく、住所の検索や電子マニュアルの検索など、組み込み機器内で行われる検索処理全般に適用しうるものである。
【００１３】
実施の形態１．
図１は、この発明の実施の形態１による検索装置の構成を示すブロック図である。
検索装置１００は、入力部１、類似単語候補取得部２、単語辞書３、類似単語選択部４、名称検索部（テキスト検索部）５および名称検索用索引データ蓄積部（検索用索引データ蓄積部）６で構成されている。
入力部１は、ソフトウェアキーボードや音声認識機能などで構成され、利用者による入力操作を受け付け、受け付けた入力操作を入力文字列１０１に変換する。類似単語候補取得部２は、単語辞書３を参照して入力文字列１０１に対する類似単語候補リスト１０２を取得する。類似単語選択部４は、類似単語候補取得部２が取得した類似単語候補リスト１０２の各候補と入力文字列１０１との編集距離に基づく類似性を計算し、後段の処理で用いる類似単語リスト１０３を選択する。名称検索部５は、名称検索用索引データ蓄積部６に蓄積された名称検索用索引データを参照し、類似単語リスト１０３の各単語を含む名称データ（検索テキスト）を検索結果データ１０４として出力する。名称検索用索引データ蓄積部６は、名称検索用索引データを蓄積する。
【００１４】
次に、検索装置１００の動作について説明する。
図２は、この発明の実施の形態１による検索装置の動作を示すフローチャートである。
入力操作が行われると（ステップＳＴ１）、入力部１は入力操作を入力文字列１０１に変換する（ステップＳＴ２）。類似単語候補取得部２は、単語辞書３を参照して入力文字列１０１の類似単語候補を取得して類似単語候補リスト１０２を作成する（ステップＳＴ３）。この際、単語の補完入力も可能とするよう、単語辞書を参照して前方一致優先の曖昧照合を行い、類似単語候補を取得する。なお単語辞書３は、検索対象とする名称データを事前に単語毎に分割し、重複を除去した上で作成されている。このステップＳＴ３の類似単語候補取得処理では、編集距離計算よりも計算量が小さく高速処理可能なアルゴリズムにより検索する。なお、ステップＳＴ３の類似単語候補取得処理の詳細については後述する。
【００１５】
類似単語選択部４は、ステップＳＴ３で類似単語候補取得部２が取得した類似単語候補で構成される類似単語候補リスト１０２を取得し、類似単語候補リスト１０２中の全ての類似語候補と入力文字列１０１との編集距離に基づく類似性を計算し、所定の類似度以内の類似語候補を選択して類似単語リスト１０３を作成する（ステップＳＴ４）。名称検索部５は、名称検索用索引データ蓄積部６に蓄積された索引データを参照し、ステップＳＴ４で作成された類似単語リスト１０３のいずれかの単語を含む名称データを検索し、検索結果データ１０４として出力する（ステップＳＴ５）。なお、ステップＳＴ５の名称検索処理の詳細については後述する。
【００１６】
上述のように、ステップＳＴ３の類似単語の取得処理およびステップＳＴ４の類似単語の選択処理と、ステップＳＴ５の複数単語からなる名称を検索する処理を分割して実行することには以下の利点がある。
まず、索引データ容量や計算量が大きくなる曖昧検索処理、すなわち類似単語の取得および選択処理を単語ベースの処理とすることにより、対象データ件数を少なくして容量や計算量の増大を抑制できる。一方、検索対象件数が非常に多くなる後者の名称検索処理については、曖昧検索をせず単純な前方一致検索処理とすることにより、速度性能およびメモリ性能を重視した処理が可能となる。
【００１７】
上述した図１および図２では説明を簡易にするため、入力文字列１０１は１つの単語またはその部分文字列であるとして説明を行ったが、入力文字列１０１を複数の単語またはその部分文字列とすることも可能である。
図３は、この発明の実施の形態１による検索装置のその他の構成を示すブロック図であり、複数単語の入力文字列１０１を処理する場合の構成を示している。なお、図１で示した検索装置１００の構成要素と同一の部分には図１で示した符号と同一の符号を付して説明を省略する。
【００１８】
入力文字列分割部７は、入力文字列１０１を空白などの単語区切り文字により分割し、複数の文字列からなる分割済入力文字列１０５を生成する。分割済入力文字列１０５は、分割された個々の文字列および単語番号で構成される。類似単語候補取得部２、類似単語選択部４および名称検索部５は、入力文字列分割部７が分割した個々の文字列に対して、図２のフローチャートで示した処理を実行する。
【００１９】
処理残単語数判定部８は、分割済入力文字列１０５を構成する全ての文字列に対して処理が終了したか否か判定を行う。検索結果統合部９は、分割済入力文字列１０５を構成する全ての文字列に対する検索結果を統合し、統合検索結果データ１０６を出力する。
【００２０】
次に、複数単語の入力文字列１０１に対して検索処理を行う動作について説明を行う。
図４は、実施の形態１による検索装置のその他の動作を示すフローチャートであり、複数単語の入力文字列１０１に対して検索処理を行う動作を示している。なお、図２で示した検索装置１００と同一のステップには図２で使用した符号と同一の符号を付し、説明を省略する。
ステップＳＴ２において、入力部１が入力操作を入力文字列１０１に変換すると、入力文字列分割部７は入力文字列１０１を空白などの単語区切り文字により分割し、分割済入力文字列１０５を生成する（ステップＳＴ１１）。分割済入力文字列１０５を構成する各文字列に対して、ステップＳＴ３からＳＴ５の処理を繰り返し実行し、格納領域（不図示）に格納する。
【００２１】
処理残単語数判定部８は、ステップＳＴ３からＳＴ５の繰り返し処理の対象単語数の判定を行い、繰り返し処理を実行する残単語が存在するか否か判定を行う（ステップＳＴ１２）。繰り返し処理を実行する残単語が存在する場合（ステップＳＴ１２；ＹＥＳ）、ステップＳＴ３の処理に戻り上述した処理を繰り返す。一方、繰り返し処理を実行する残単語が存在しない場合（ステップＳＴ１２；ＮＯ）、検索結果統合部９はステップＳＴ３からステップＳＴ５の繰り返し処理で得られた各検索結果を統合し、統合検索結果データ１０６を出力し（ステップＳＴ１３）、処理を終了する。
【００２２】
ステップＳＴ１３の統合処理では、各検索結果データ１０４に含まれる名称ＩＤを用いて重複する結果を排除する。また、分割済入力文字列１０５に付与された単語番号を用いて、検索結果の各名称データに含まれる複数の単語文字列を照合することにより、入力単語順序を考慮した順位付けを行うことも可能である。なお、以下の説明では入力文字列１０１に対する処理として説明を行うが、上述の通り分割済入力文字列１０５のそれぞれに対する処理も同様に行われる。
【００２３】
次に、類似単語候補取得部２の詳細について説明する。以下では、文字位置情報つきの文字バイグラムを索引として高速に曖昧照合する方法を説明する。なお、後述する編集距離に基づく類似単語選択処理（図２および図４のフローチャートにおけるステップＳＴ４の処理）よりも高速に実行可能であり、且つ編集距離計算結果を近似できる曖昧検索手法であれば本発明の特徴を損なうものではない。
【００２４】
図５は、この発明の実施の形態１による検索装置の類似単語候補取得部および単語辞書の構成を示すブロック図である。
類似単語候補取得部２は、単語辞書検索部２１、類似単語候補数制御部２２、入力文字数判定部２３、入力単語数判定部２４、特定文字列判定部２５、ＣＰＵ負荷判定部２６および特定文字列テーブル２７で構成されている。また、単語辞書検索部２１が参照する単語辞書３は、単語文字列テーブル３１および文字バイグラム索引３２で構成されている。なお、特定文字列テーブル２７は、類似単語候補取得部２の外部構成としてもよい。
【００２５】
単語辞書検索部２１は、単語の補間入力も可能とするために、単語辞書３を参照して前方一致優先の曖昧照合を行い、類似単語候補を取得する。類似単語候補数制御部２２は、入力文字数判定部２３、入力単語数判定部２４、特定文字列判定部２５およびＣＰＵ負荷判定部２６が算出した候補数の上限値ｎに基づいて、最終的な候補数の上限値Ｎを決定し、単語辞書検索部２１の単語辞書検索結果の上位Ｎ件を選択して類似単語候補リスト１０２を作成し、出力する。
【００２６】
入力文字数判定部２３は、入力文字列１０１の入力文字数を判定し、判定結果に基づいて候補数の上限値ｎを算出する。入力単語数判定部２４は、入力文字列１０１の入力単語数を判定し、判定結果に基づいて候補数の上限値ｎを算出する。特定文字列判定部２５は、特定文字列テーブル２７を参照して入力文字列１０１が特定文字列に合致するか否か判定し、判定結果に基づいて特定文字列テーブル２７に事前に定義された特定文字列に対応した候補数の上限値ｎを取得する。ＣＰＵ負荷判定部２６は、検索処理実行時の検索装置１００のＣＰＵ負荷（演算負荷）を判定し、判定結果に基づいて候補数の上限値ｎを算出する。
【００２７】
特定文字列テーブル２７は、極端に類似語候補数が多い特定の文字列や、その逆であって類似候補数が少ないことが事前に分かっている文字列などに対応するためのテーブルである。
図６は、この発明の実施の形態１による検索装置の特定文字テーブルの一例を示す図である。
特定文字列テーブル２７は、特定文字列２７ａと特定文字列上限候補数２７ｂとの対応関係を示すテーブルである。
【００２８】
次に、単語辞書３について説明する。単語辞書３は単語文字列テーブル３１および文字バイグラム索引３２で構成され、検索対象とする名称データを事前に単語ごとに分割し、重複を除去した上で作成される。
図７はこの発明の実施の形態１による検索装置の単語辞書蓄積部の蓄積例を示す図であり、図７（ａ）は単語文字列テーブル、図７（ｂ）は文字バイグラム索引の一例を示している。
単語文字列テーブル３１は、単語番号３１ａと単語文字列３１ｂとの対応関係を示すテーブルである。文字バイグラム索引３２は、各単語を２文字ずつに分割した文字バイグラム３２ａと、転置索引情報３２ｂとを対応付けて格納した索引データである。転置索引情報３２ｂは、文字バイグラム３２ａの単語番号と出現文字位置で構成される。文字バイグラム索引３２の索引データを用いることにより、入力文字列１０１を２文字ずつに分割した部分文字列から、当該部分文字列が類似する位置に出現する単語を高速に検索することができる。
【００２９】
次に、類似単語候補取得部２の類似単語候補取得処理の詳細について説明する。
図８は、この発明の実施の形態１による検索装置の類似単語候補取得部の動作を示すフローチャートである。
単語辞書検索部２１は、単語辞書３を参照し、入力文字列１０１と類似する単語を検索する（ステップＳＴ２１）。具体的には、入力文字列１０１を２文字ずつに分割し、図７（ｂ）で示した文字バイグラム索引３２を参照して入力文字列１０１から得られた各文字バイグラムを含む単語番号とその文字バイグラムが単語内で出現する出現文字位置のペアを抽出する。
【００３０】
例えば、入力文字列１０１として“ＥＤＩＮＢ”が与えられたとする。単語辞書検索部２１は、最初に当該入力文字列１０１を２文字ずつに分割し、“ＥＤ”、“ＤＩ”、“ＩＮ”、“ＮＢ”の４種類の文字バイグラムを得る。各文字バイグラムに対して図７（ｂ）で示したバイグラム索引３２から単語番号と出現文字位置のペアである＜１０，１＞、 ＜２０，１＞、…、又は＜１０，２＞、 ＜２０，２＞、…などを得る。このとき、入力時の打鍵誤りや音声認識誤りを考慮し、文字位置の照合については完全一致ではなく所定値以内、たとえば２文字以内であれば許容するものとする。例えば、入力文字列１０１中の“ＩＮ”の文字位置は３文字目だが、“ＥＤＷＩＮ”内に出現する＜４０，４＞も照合可とする。
【００３１】
上記のように単語番号ごとに索引から取得した文字バイグラムの個数を加算し、類似単語候補のスコアとする。上述した“ＥＤＩＮＢ”の例では、“ＥＤＩＮＢＡＮＥ”（単語番号１０）および“ＥＤＩＮＢＵＲＧＨ”（単語番号２０）にはスコア「４」、“ＥＤＩＮＧＴＯＮ”（単語番号３０）にはスコア「３」、“ＥＤＷＩＮ”（単語番号４０）にはスコア「２」がそれぞれ与えられる。
【００３２】
次に、入力文字数判定部２３は、入力文字列１０１の入力文字数を判定する処理を行い、判定結果に応じて類似語候補取得候補数（すなわち、取得する類似単語候補数の数）の上限値ｎを算出する（ステップＳＴ２２）。上限値ｎは、例えば以下の式（１）に従って算出される。
0005951105.tif 000002
式（１）では、入力文字数ｉが小さい場合には、多くの類似単語がカバー可能なように上限値ｎを大きく設定する。一方、入力文字数ｉが大きい場合には、類似単語の数が少なくなるため、後述する名称検索処理における速度性能を重視し、上限値ｎを小さく設定する。
【００３３】
入力単語数判定部２４は、入力文字列１０１が複数単語からなる場合に、入力文字列分割部７から入力される分割入力文字列１０５に付された単語番号に基づいて入力単語数を判定する処理を行い、判定結果に応じて類似語候補取得候補数の上限値ｎを算出する（ステップＳＴ２３）。上限値ｎは、例えば以下の式（２）に従って算出される。
ｎ＝１０００＊ｌｏｇ（ｗ＊１００００）            式（２）
式（２）では、単語番号ｗが小さい場合には入力誤りが少ないと仮定し、上限値ｎを小さく設定する。一方、単語番号ｗが大きい時には、入力誤りの可能性があると仮定し、上限値ｎを大きく設定する。
【００３４】
特定文字列判定部２５は、特定文字列テーブル２７を参照し、入力文字列１０１が特定文字列に合致するか否か判定を行い、判定結果に応じて類似語候補取得候補数の上限値ｎを取得する（ステップＳＴ２４）。具体的には、入力文字列１０１が、特定文字列テーブル２７の特定文字列２７ａに合致する場合、該当する特定文字列上限候補数２７ｂを類似語候補取得候補数の上限値ｎとして取得する。これにより、極端に類似語候補数が多い特定の文字列に対しては検索もれを防ぐことができる。一方、極端に類似語候補数が少ない文字列に対しては、余計な類似語に対する検索処理の実行を抑制し、処理を高速化することができる。
【００３５】
ＣＰＵ負荷判定部２６は、検索装置１００の現時点でのＣＰＵ負荷（演算負荷）を示す値を取得してＣＰＵ負荷の高低を判定する処理を行い、判定結果に応じて類似語候補取得候補数の上限値ｎを算出する（ステップＳＴ２５）。上限値ｎは、例えば以下の式（３）に従って算出される。ここで、ＣＰＵ負荷を示す値は０．０より大きく、１．０より小さい値をとるものとする。
ｎ＝（１．０−（ＣＰＵ負荷））＊１０００          式（３）
式（３）では、ＣＰＵ負荷が高い状態であれば検索処理に要する時間が大きくなるのを防ぐために上限値ｎを小さい値に設定する。逆に、ＣＰＵ負荷が低い状態であれば検索漏れを少なくするため上限値ｎを大きい値に設定する。
【００３６】
類似単語候補数制御部２２は、ステップＳＴ２２からステップＳＴ２５の処理結果に従って、類似語候補取得候補数の最終的な上限値Ｎを設定する（ステップＳＴ２６）。ここでは、ステップＳＴ２２からステップＳＴ２５の各ステップで設定された類似語候補取得候補数の上限値ｎを記憶領域（不図示）に格納し、格納された値を比較して最小値または最大値を最終的な類似語候補取得候補数の上限値Ｎとして設定する。なお、格納された値の平均値を最終的な類似語候補取得候補数の上限値Ｎとして用いてもよい。最終的な類似語候補取得候補数の上限値Ｎを決定するための具体的手段がどのようなものであっても、本発明の特徴を損なうものではない。
【００３７】
類似単語候補数制御部２２は、ステップＳＴ２６で設定した最終的な類似語候補取得候補数の上限値Ｎに従って、ステップＳＴ２１の検索結果のうち、スコア上位のＮ件を選択して類似単語候補リスト１０２を作成して出力する（ステップＳＴ２７）。以上が、類似単語候補取得部２の動作である。
【００３８】
次に、類似単語選択部４の詳細について説明する。
図９は、この発明の実施の形態１による検索装置の類似単語選択部の構成を示すブロック図である。
類似単語選択部４は、編集距離計算部４１および類似単語判定部４２で構成されている。
編集距離計算部４１は、類似単語候補リスト１０２の各単語と入力文字列１０１との編集距離を計算する。類似単語判定部４２は、入力文字数に応じて決定される距離が、所定の距離以内であるか否かに基づいて類似単語の判定を行う。当該判定処理において、入力文字数に応じて決定された距離が所定の距離以内であるものを類似単語としてリスト化した類似単語リスト１０３を作成し、出力する。
【００３９】
図１０は、この発明の実施の形態１による検索装置の類似単語選択部の動作を示すフローチャートである。
編集距離計算部４１は、類似単語候補リスト１０２の各単語と、入力文字列１０１との編集距離を計算する（ステップＳＴ３１）。編集距離の計算については、動的計画法を用いる一般的な手法が公知であり、当該手法を用いるものとして説明を省略する。
【００４０】
次に、類似単語判定部４２は、例えば以下の式（４）に従って、入力文字列１０１の入力文字数ｉに応じて決定される閾値である所定の距離Ｄを決定する（ステップＳＴ３２）。
0005951105.tif 000003
【００４１】
また、類似単語判定部４２は、ステップＳＴ３１で計算された編集距離がステップＳＴ３２で決定された所定の距離Ｄ以内であるか否かを判定する類似単語判定を行う（ステップＳＴ３３）。ステップＳＴ３３の類似単語判定結果に基づいて、編集距離が所定の距離Ｄ以内にある類似単語候補を選別して類似単語リスト１０３を作成し、出力する（ステップＳＴ３４）。以上が、類似単語選択部４の処理である。
【００４２】
次に、名称検索部５および名称検索用索引データ蓄積部６の詳細について説明する。
図１１は、この発明の実施の形態１による検索装置の名称検索部および名称検索用索引データ蓄積部の構成を示すブロック図である。
名称検索部５は、名称検索用索引データ蓄積部６を参照し、類似単語リスト１０３に含まれる各単語を含む名称データを検索し、検索結果データ１０４として出力する。名称検索部５は、検索手法として以下の参考文献１に開示された検索手法を用いるものとする。なお、検索方法の詳細は参考文献１に記載されているため、以下では検索処理の概略について示す。
・参考文献１
特開２０１０−２０５１１９
【００４３】
名称検索用索引データ蓄積部６は、ダブル配列索引データ６１、最小・最大子ノード索引６２および名称リスト６３で構成されている。
ダブル配列索引データ６１は、ダブル配列法におけるＢａｓｅ配列とＣｈｅｃｋ配列を格納するデータである。最小・最大子ノード索引６２は、辞書順で最小となる文字列へ遷移するための内部コードおよび最大となる文字列へ遷移するための内部コードを値に持つ配列を格納するデータである。名称リスト６３は、登録されている名称の文字列を辞書順にソートして格納するデータである。
【００４４】
名称検索部５は、ダブル配列索引データ６１に基づいて、与えられた検索文字列に該当するノードを探索する。続けて、最小・最大子ノード索引６２に基づいて、探索されたノードの子ノードのうち、辞書順で最少の文字列となるノードと最大の文字列となるノードを探索する。さらに、名称リスト６３を参照し、探索された最小ノードに対応する名称から最大ノードに対応する名称までの全ての名称を抽出して検索結果データ１０４とする。
【００４５】
図１２は、この発明の実施の形態１による検索装置の名称検索用索引データ蓄積部が蓄積する名称リストの一例を示す図である。
名称リスト６３は、少なくとも各名称を一意に特定する名称ＩＤ６３ａ、各名称を構成する単語の単語ＩＤリスト６３ｂおよび各名称を構成する単語の種別情報６３ｃからなるものとする。ここで単語ＩＤリスト６３ｂは、各単語の単語番号のリストであり、図７（ａ）で示した単語文字列テーブル３１の単語文字列３１ｂと一対一で対応する単語番号３１ａと同一のものである。  
【００４６】
当該名称リスト６３を用いて検索結果データ１０４を表示するためには、図７（ａ）の単語文字列テーブル３１を参照して単語ＩＤリスト６３から通常の単語文字列に変換する。なお、図１２の例では同一の名称ＩＤ「３」を有する行を２箇所に示しているが、これは複数単語（単語番号１および１００）からなる名称を、途中の単語からでも検索可能とするために事前に展開して索引化しているためである。
【００４７】
なお、上記では一例として参考文献１に記載されたダブル配列索引を用いた検索方法を示したが、名称検索部５の名称検索処理は類似単語リスト１０３に含まれる各単語から、その単語を含む名称データを高速に検索する方法であれば適宜適用可能である。例えば、組み込み機器向けのデータベースを用いてもよいし、名称検索用索引データ蓄積部６の名称リスト６３が有する情報を高速検索するための木構造索引データの中に埋め込む構造としてもよい。
【００４８】
以上のように、この実施の形態１によれば、類似単語候補数制御部２２により類似単語候補取得候補数の上限値Ｎを設定し、設定した上限値Ｎの類似単語候補を取得する類似単語候補取得部２と、取得された類似単語候補と入力文字列との編集距離計算に基づいて類似単語を選択する類似単語選択部４と、選択された類似単語の各単語を含む名称を検索する名称検索部５を備えるように構成したので、入力文字数や入力単語数などの状況に応じて類似単語候補数を調整することができ、検索漏れを少なく抑制し、且つ高速な検索処理を実現することができる。
【００４９】
また、この実施の形態１によれば、類似単語候補数制御部２２が入力文字数判定部２３の判定結果を用いて算出した類似単語候補取得候補数の上限値ｎに基づいて最終的な上限値Ｎを設定するように構成したので、曖昧性が大きくなる文字数の少ない入力に対して類似単語候補の候補数の上限値Ｎを大きく設定することができ、検索漏れを防ぐことができる。一方、曖昧性が小さくなる文字数の多い入力に対して類似単語候補の候補数の上限値Ｎを小さく設定することができ、検索の速度性能を向上させることができる。
【００５０】
また、この実施の形態１によれば、類似単語候補数制御部２２が入力単語数判定部２４
の判定結果を用いて算出した類似単語候補取得候補数の上限値ｎに基づいて最終的な上限値Ｎを設定するように構成したので、曖昧性が大きくなる入力順最後の単語に対して類似単語候補の候補数の上限値Ｎを大きく設定することができ、検索漏れを防ぐことができる。一方、曖昧性が小さくなる入力順最初の単語に対して類似単語候補の候補数の上限値Ｎを小さく設定することができ、検索の速度性能を向上させることができる。
【００５１】
また、この実施の形態１によれば、類似単語候補数制御部２２が特定文字列判定部２５の判定結果を用いて取得した類似単語候補取得候補数の上限値ｎに基づいて最終的な上限値Ｎを設定するように構成したので、特定の文字列に対して個別に類似単語候補の候補数の上限値Ｎを設定することができ、必要に応じて検索漏れの防止を重視する設定を行う、あるいは速度性能を重視した設定を行うことができる。
【００５２】
また、この実施の形態１によれば、類似単語候補数制御部２２がＣＰＵ負荷判定部２６の判定結果を用いて取得した類似単語候補取得候補数の上限値ｎに基づいて最終的な上限値Ｎを設定するように構成したので、ＣＰＵ負荷に応じた類似単語候補の候補数の上限値Ｎを設定することができ、必要に応じて検索漏れの防止を重視する設定を行う、あるいは速度性能を重視した設定を行うことができる。
【００５３】
なお、上述した実施の形態１では、類似単語候補数制御部２２が入力文字数判定部２３
、入力単語数判定部２４、特定文字列判定部２５およびＣＰＵ負荷判定部２６を備える構成を示したが、少なくともいずれか１つの判定部を備えていればよく、設ける判定部は適宜選択可能である。
【００５４】
実施の形態２．
この実施の形態２では、打鍵誤りや音声認識誤りにより通常の文字バイグラム検索では検索しにくい入力文字列に対しても検索漏れを抑制する構成について説明する。
図１３は、この発明の実施の形態２による検索装置の構成を示すブロック図である。
実施の形態２の検索装置１００´は、図１で示した実施の形態１の検索装置１００の類似単語候補取得部２に新たな内部構成を追加して設け、さらに類似文字列重みテーブル１１を追加して設けている。なお、以下では、実施の形態１に検索装置１００の構成要素と同一または相当する部分には実施の形態１で使用した符号と同一の符号を付して説明を省略または簡略化する。
類似単語候補取得部２´は、類似文字列重みテーブル１１および単語辞書３を参照して、類似単語候補リスト１０２を作成する。
【００５５】
図１４は、この発明の実施の形態２による検索装置の動作を示すフローチャートである。なお、以下では実施の形態１による検索装置１００と同一のステップには図２で使用した符号と同一の符号を付し、説明を省略または簡略化する。
ステップＳＴ２において入力部１が入力操作を入力文字列１０１に変換すると、類似単語候補取得部２´は、類似文字列重みテーブル１１および単語辞書３を参照して入力文字列１０１に対して類似単語候補展開検索処理を行って類似単語候補を取得して類似単語候補リスト１０２を作成する（ステップＳＴ４１）。
【００５６】
この際、単語の補完入力も可能とするよう、単語辞書を参照して前方一致優先の曖昧照合を行い、類似単語候補を取得する。単語辞書は、検索対象とする名称データを事前に単語ごとに分割し、重複を除去した上で作成されている。ステップＳＴ４１の類似単語候補展開検索処理では、編集距離計算よりも計算量が小さく高速処理可能なアルゴリズムにより検索する。なお、ステップＳＴ４１の類似単語候補取得処理の詳細については後述する。その後、実施の形態１と同様にステップＳＴ４およびステップＳＴ５の処理を行い、検索処理を終了する。
【００５７】
次に、類似単語候補取得部２´の詳細について説明する。
図１５は、この発明の実施の形態２による検索装置の類似単語候補取得部の構成を示すブロック図である。実施の形態２の類似単語候補取得部２´は、実施の形態１の類似単語候補取得部２の構成に加えて類似文字列展開部２８を追加して設けている。なお以下では、実施の形態１の類似単語候補取得部２の構成要素と同一または相当する部分には、実施の形態１で使用した符号と同一の符号を付して説明を省略または簡略化する。
類似文字列展開部２８は、類似文字列重みテーブル１１を参照して、単語辞書検索部２１が入力文字列１０１に基づいて生成した単語辞書検索用の文字バイグラムを展開する。
【００５８】
図１６は、この発明の実施の形態１による検索装置の類似単語候補展開検索部の動作を示すフローチャートである。
なお、以下では実施の形態１による検索装置１００の類似単語候補取得部２と同一のステップには図８で使用した符号と同一の符号を付し、説明を省略または簡略化する。
単語辞書検索部２１は、入力文字列１０１に基づいて単語辞書検索用の文字バイグラムを生成する（ステップＳＴ５１）。例えば、入力文字列１０１が“ＸＹＣ”である場合、単語辞書検索用の文字バイグラムとして“ＸＹ”および“ＹＣ”が生成される。類似文字列展開部２８は、類似文字列重みテーブル１１を参照して、ステップＳＴ５１で生成された単語辞書検索用の文字バイグラムを展開する（ステップＳＴ５２）。
【００５９】
類似文字列重みテーブル１１の構成例を図１７に示す。類似文字列重みテーブル１１は、打鍵誤りや音声認識誤りしやすい文字列などの組合せを重みつきで定義し、少なくとも第１の文字列１１ａ、第２の文字列１１ｂおよび類似文字列重み１１ｃで構成される。例えば、上記説明で生成された文字バイグラム“ＸＹ”および“ＹＣ”は、それぞれ“ＸＩＥ”（重み０．４） および“ＹＫ”（重み０．７）に展開される。
【００６０】
次に、単語辞書検索部２１は、入力文字列１０１の文字バイグラムに加えて、ステップＳＴ５２で展開された文字バイグラムに基づいて単語辞書３を検索する（ステップＳＴ２１´）。
具体的には、入力文字列１０１の文字バイグラム“ＸＹ”および“ＹＣ”に加えて、展開された文字バイグラム“ＸＩＥ” および“ＹＫ” に基づいて、単語辞書３の検索が行われる。単語辞書３の検索における検索スコアとして、類似文字列重みテーブル１１の類似文字列重み１１ｃを用いる。すなわち、“ＸＩＥ”（重み０．４）を検索キーとして単語辞書３から取得した各文書には、重み「０．４」を加算する。このように類似文字列重み１１ｃを用いてスコア計算を行うことにより、入力文字列１０１と完全一致した文字バイグラムを有する候補を類似単語候補として優先して検索することができる。
【００６１】
その後、類似単語候補展開検索部１０は、実施の形態１のステップＳＴ２２からＳＴ２７と同一の処理を行い、類似単語候補リスト１０２を作成して出力する。
【００６２】
以上のように、この実施の形態２によれば、打鍵誤りや音声認識誤りしやすい文字列などの組合せを重みつきで定義した類似文字列重みテーブル１１を参照して、単語辞書検索部２１が生成した文字バイグラムから類似文字列を展開する類似文字列展開部２８を備えるように構成したので、打鍵誤りや音声認識誤りにより通常の文字バイグラム検索では検索しにくい入力文字列に対しても、検索漏れの少ない検索処理を実行することができる。
【００６３】
実施の形態３．
この実施の形態３では、名称検索処理の回数を低減し、検索処理を高速化する構成について説明する。
図１８は、この発明の実施の形態３による検索装置の構成を示すブロック図である。
実施形態３の検索装置１００´´は、図１で示した実施の形態１の検索装置１００に、類似単語統合部１２を追加して設けている。なお、以下では、実施の形態１に検索装置１００の構成要素と同一または相当する部分には実施の形態１で使用した符号と同一の符号を付して説明を省略または簡略化する。
類似単語統合部１２は、入力文字列１０１および類似単語リスト１０３に基づいて、類似単語統合処理を行い、前方一致類似単語リスト１０７を作成する。
【００６４】
図１９は、この発明の実施の形態３による検索装置の動作を示すフローチャートである。なお、以下では実施の形態１による検索装置と同一のステップには図２で使用した符号
と同一の符号を付し、説明を省略または簡略化する。
ステップＳＴ４において類似単語選択部４が類似単語リスト１０３を作成すると、類似単語統合部１２は当該類似単語リスト１０３およびステップＳＴ２で変換された入力文字列１０１に基づいて類似単語統合処理を行い、前方一致類似単語リスト１０７を作成する（ステップＳＴ６１）。ステップＳＴ６１の類似単語統合処理の詳細については後述する。その後、名称検索部５はステップＳＴ６１で作成された前方一致類似単語リスト１０７のいずれかの単語を含む名称データを検索し、検索結果データ１０４として出力し（ステップＳＴ５´）、処理を終了する。
【００６５】
次に、類似単語統合部１２の詳細について説明する。
図２０は、この発明の実施の形態３による検索装置の類似単語統合部の動作を示すフローチャートである。
類似単語統合部１２は、類似単語選択部４が作成した類似単語リスト１０３を文字列順に整列する（ステップＳＴ７１）。次に、整列させた類似単語リスト１０３の先頭から順次入力文字列１０１との比較を行い、入力文字列１０１の文字数以上であって先頭文字列が一致するかの判定を行い、一致する類似単語同士を統合する（ステップＳＴ７２）。
具体的には、例えば入力文字列１０１が“ＥＤＩＮ”で、類似単語リスト１０３に“ＥＤＩＮＢＡＮＥ”と“ＥＤＩＮＢＵＲＧＨ”が存在する場合、入力文字列１０１の文字数が４文字であるので、先頭の４文字が一致する単語を類似単語として統合して“ＥＤＩＮ”とする。
【００６６】
このように入力文字列１０１と一致する文字列を有する単語を類似単語として統合することにより、類似単語統合部１２の後段の名称検索部５が行う名称検索処理の回数を低減させることができ、検索処理が高速化する。
図１９のフローチャートのステップＳＴ５で示した名称検索処理について実施の形態１と同様であるため詳細な説明は省略するが、ステップＳＴ５の名称検索処理では、類似単語統合部１２から入力された前方一致類似単語リスト１０７の各単語で前方一致検索を行うため、上述したステップＳＴ７１およびステップＳＴ７２で統合された文字列“ＥＤＩＮ”の検索結果と、“ＥＤＩＮＢＡＮＥ”、“ＥＤＩＮＢＵＲＧＨ”等の“ＥＤＩＮ”で始まる類似単語すべてで検索した結果とは一致する。
【００６７】
以上のように、この実施の形態３によれば、類似単語リストと入力文字列との比較を行い、入力文字列の文字数であって先頭文字列が一致する類似単語同士を統合し、前方一致類似単語リストを作成する類似単語統合部１２を備えるように構成したので、前方一致類似単語リストを元に行う名称検索処理において名称検索処理の回数を低減させ、検索処理の高速化を実現することができる。
【００６８】
なお、上述した実施の形態２および実施の形態３では、入力文字列は１つの単語またはその部分文字列である場合を例に説明を行ったが、実施の形態１と同様に入力文字列を複数の単語またはその部分文字列とすることが可能である。その場合、実施の形態１の図２のブロック図で示した構成および図４のフローチャートで示した処理を適用して構成することができる。
【００６９】
なお、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【産業上の利用可能性】
【００７０】
以上のように、この発明に係る検索装置は、施設名称などの検索を行うナビゲーション装置や、例えば住所検索や電子マニュアルの検索などを行う種々の装置に適用可能であり、検索漏れを低減した高速な曖昧検索処理を実現することができる。
【符号の説明】
【００７１】
１  入力部、２，２´  類似単語候補取得部、３  単語辞書、４  類似単語選択部、５  名称検索部、６  名称検索用索引データ蓄積部、７  入力文字列分割部、８  処理残単語数判定部、９  検索結果統合部、１１  類似文字列重みテーブル、１２  類似単語統合部、２１  単語辞書検索部、２２  類似単語候補数制御部、２３  入力文字数判定部、２４  入力単語数判定部、２５  特定文字列判定部、２６  ＣＰＵ負荷判定部、２７  特定文字列テーブル、２８  類似文字列展開部、３１  単語文字列テーブル、３２  文字バイグラム索引、４１  編集距離計算部、４２  類似単語判定部、６１  ダブル配列索引データ、６２  最小・最大子ノード索引、６３  名称リスト、１００，１００´，１００´´  検索装置、１０１  入力文字列、１０２  類似単語候補リスト、１０３  類似単語リスト、１０４  検索結果データ、１０５  分割済入力文字列、１０６  統合検索結果データ、１０７  前方一致類似単語リスト。
【図１】
0005951105.tif 000004
【図２】
0005951105.tif 000005
【図３】
0005951105.tif 000006
【図４】
0005951105.tif 000007
【図５】
0005951105.tif 000008
【図６】
0005951105.tif 000009
【図７】
0005951105.tif 000010
【図８】
0005951105.tif 000011
【図９】
0005951105.tif 000012
【図１０】
0005951105.tif 000013
【図１１】
0005951105.tif 000014
【図１２】
0005951105.tif 000015
【図１３】
0005951105.tif 000016
【図１４】
0005951105.tif 000017
【図１５】
0005951105.tif 000018
【図１６】
0005951105.tif 000019
【図１７】
0005951105.tif 000020
【図１８】
0005951105.tif 000021
【図１９】
0005951105.tif 000022
【図２０】
0005951105.tif 000023