(57)【特許請求の範囲】
【請求項１】
検索対象データの読みを２音節単位に分割して格納した音節バイグラム辞書と、
正式名称を格納した名称検索用辞書と、
与えられた読み文字列の一部の文字列と類似する読み文字列を前記音節バイグラム辞書から検索し、当該検索した文字列を組み合わせて類似読み候補を作成する類似読み候補作成部と、
前記類似読み候補作成部で作成された前記類似読み候補を元に前記名称検索用辞書から正式名称を検索する名称検索部とを備えた検索装置。
【請求項２】
前記類似読み候補作成部は、前記検索した文字列を組み合わせて作成した類似読み候補を取捨選択する類似読み候補選択部を備えたことを特徴とする請求項１記載の検索装置。
【請求項３】
前記類似読み候補選択部は、前記音節バイグラム辞書から検索された各音節の読みと、これと対応する前記与えられた読み文字列の部分文字列との編集距離が所定値以下の類似読み候補を選択し、これ以外の類似読み候補を棄却する音節別読み編集距離判定部を備えたことを特徴とする請求項２記載の検索装置。
【請求項４】
前記類似読み候補選択部は、前記音節バイグラム辞書から検索された各音節の読みと、これと対応する前記与えられた読み文字列の部分文字列との編集距離の累積値を計算する読み編集距離累積値計算部と、当該読み編集距離累積値計算部により計算された読み編集距離累積値が所定値以下の類似読み候補を選択し、これ以外の類似読み候補を棄却する読み編集距離累積値判定部とを備えたことを特徴とする請求項２記載の検索装置。
【請求項５】
前記類似読み候補選択部は、類似読み候補数が所定値を超えたかどうかを判定する新規候補数判定部と、当該新規候補数判定部で所定値を超えたと判定した場合、前記類似読み候補のスコアを計算し、スコア上位の前記所定値の類似読み候補のみを残す類似読み候補スコア順選択部を備えたことを特徴とする請求項２記載の検索装置。
【請求項６】
前記類似読み候補スコア順選択部は、前記読み編集距離累積値計算部により計算された読み編集距離の累積値を元に前記類似読み候補のスコアを計算することを特徴とする請求項５記載の検索装置。
【請求項７】
前記類似読み候補選択部は、前記音節バイグラム辞書から検索された各音節の出現確率の累積値を計算する読み出現確率累積値計算部を有し、前記類似読み候補スコア順選択部は、前記読み出現確率累積値計算部の計算結果を元に前記類似読み候補のスコアを計算することを特徴とする請求項５記載の検索装置。
【請求項８】
前記類似読み候補選択部は、前記類似読み候補に対し、前記名称検索用辞書を検索することで名称の一部となり得る類似読み候補を選択し、これ以外の類似読み候補を棄却する名称有無判定部を備えたことを特徴とする請求項２記載の検索装置。
【請求項９】
検索対象データの読みを２音節単位に分割して格納した音節バイグラム辞書と、
正式名称を格納した名称検索用辞書と、
音節単位で区切られた区切り付き読み文字列の一部の文字列と類似する読み文字列を前記音節バイグラム辞書から検索し、当該検索した文字列を組み合わせて類似読み候補を作成すると共に、前記区切り付き読み文字列に対し、当該区切り読み文字列中の音節区切りと前記音節バイグラム辞書の検索結果との一致判定を行い、区切りが一致しない音節バイグラム検索結果を棄却して類似読み候補を作成する区切り限定類似読み候補作成部と、
前記区切り限定類似読み候補作成部で作成された前記類似読み候補を元に前記名称検索用辞書から正式名称を検索する名称検索部とを備えた検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、正式名称だけでなく略称やうろ覚えの名称などを検索キーとして、大量に登録された住所データや施設名データ中をあいまい検索することが可能な検索装置に関するものである。
【背景技術】
【０００２】
住所や施設名を検索する場合、利用者は必ずしも正確な名称を記憶しておらず、通称や略称、うろ覚えの誤った名称などを検索キーとして検索する場合がある。
また、カーナビやスマートフォンのように、入力デバイスとしてキーボードを持たない端末や機器においては、マイクからの音声信号を音声認識した結果や、タッチパネルからの入力を文字認識した結果などから検索する場合もある。これらの入力デバイスを用いる入力の際には、認識誤り、打鍵誤りなどユーザの操作ミスによる入力誤りが存在する。
上記いずれの場合も、正式名称だけではなく、文字列あるいは発音が類似する名称をあいまい検索する技術が必要となる。【０００３】
上記のようなあいまい検索を可能とする技術の一例として例えば特許文献１に示す検索装置があった。特許文献１に示された検索装置は、入力されたキーワードから部分文字列の一致度を用いて類似語候補を検索し、さらにこれらの類似語候補から入力キーワードと編集距離の近い類似語を抽出して検索キーワードに追加することで曖昧な全文検索を行うものである。例えば、「アセトアルデヒド」が検索キーワードとして入力されると、その部分文字列である「アセト」「アルデ」「ヒド」などを含む類似語候補を検索する。この検索結果として「アセトアルデイド」や「アセトアルドール」などの類似語候補が得られると、今度は入力キーワード「アセトアルデヒド」と各類似語候補との編集距離を計算し、このうち編集距離が小さい類似語「アセトアルデイド」も用いて全文検索することで、検索もれを少なくしていた。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−１１０７８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記特許文献１に記載された技術では、事前の絞り込みに類似語候補を用いているため、ユーザからの入力が複数の単語を連ねたべた書きの場合に対応しにくいという問題があった。また、検索対象を事前に形態素解析して単語分割しておく必要もあった。【０００６】
また、類似語候補の検索にあたり、事前絞り込みの精度を上げるためにはトライグラム以上の索引利用が必要であり、辞書データサイズが巨大になるため、カーナビや携帯電話などの組み込み機器への用途には適さないという課題もあった。一方、メモリ容量を考慮し、事前絞り込みで使用する索引をバイグラム以下に限定すると、効果的な事前絞り込みが困難となり編集距離計算に時間を要するという課題があった。【０００７】
さらに、事前絞り込みの段階では誤りの偏りを考慮していないため、文字列の前方に差異が集中したり、逆に後方に集中したりと、入力誤りの補正という観点ではやや不適切な絞り込み結果となり、編集距離計算前の絞り込みが十分にできない場合があった。例えば、ユーザが「ＴＳＵＮＡＳＨＩＭＡ」と入力しようとして誤って「ＴＳＵＮＡＨＩＭＡ」と入力したとする。このとき、従来技術では事前絞り込みの結果として、「ＫＵＭＡＳＨＩＭＡ」（ＴＳ→Ｋ）や「ＴＳＵＮＡＨＡＲＡ」（ＩＭ→ＡＲ）なども含まれることになるが、これらは入力誤りという観点では、元データとの差異をもつ文字列が一か所に固まっており不自然である。【０００８】
この発明は、かかる問題を解決するためになされたもので、省メモリかつ高速に曖昧検索結果が得られる検索装置を得ることを目的とする。
【課題を解決するための手段】
【０００９】
この発明に係る検索装置は、検索対象データの読みを２音節単位に分割して格納した音節バイグラム辞書と、正式名称を格納した名称検索用辞書と、与えられた読み文字列の一部の文字列と類似する読み文字列を音節バイグラム辞書から検索し、検索した文字列を組み合わせて類似読み候補を作成する類似読み候補作成部と、類似読み候補作成部で作成された類似読み候補を元に名称検索用辞書から正式名称を検索する名称検索部とを備えたものである。
【発明の効果】
【００１０】
この発明に係る検索装置は、読み文字列の一部の文字列と類似する読み文字列を音節バイグラム辞書から検索し、検索した文字列を組み合わせて類似読み候補を作成して正式名称を検索するようにしたものである。これにより、省メモリかつ高速に曖昧検索結果を得ることができる。
【図面の簡単な説明】
【００１１】
【図１】この発明の実施の形態１の検索装置を示す構成図である。
【図２】この発明の実施の形態１の検索装置における検索処理を示すフローチャートである。
【図３】この発明の実施の形態１の検索装置における類似読み候補作成部の詳細を示す構成図である。
【図４】この発明の実施の形態１の検索装置における音節バイグラム辞書の説明図である。
【図５】この発明の実施の形態１の検索装置における類似読み候補木構造データの概念を示す説明図である。
【図６】この発明の実施の形態１の検索装置における類似読み候補木構造データの説明図である。
【図７】この発明の実施の形態１の検索装置における類似読み候補作成処理を示すフローチャートである。
【図８】この発明の実施の形態１の検索装置における音節バイグラム読み文字列検索処理を示すフローチャートである。
【図９】この発明の実施の形態１の検索装置における名称検索用辞書名称検索部との関係を示す説明図である。
【図１０】この発明の実施の形態１の検索装置における名称リストの説明図である。
【図１１】この発明の実施の形態２の検索装置を示す構成図である。
【図１２】この発明の実施の形態２の検索装置における名称先読み類似読み候補作成部の詳細を示す構成図である。
【図１３】この発明の実施の形態２の検索装置における名称先読み類似読み候補作成処理を示すフローチャートである。
【図１４】この発明の実施の形態３の検索装置を示す構成図である。
【図１５】この発明の実施の形態３の検索装置における区切り限定類似読み候補作成部の詳細を示す構成図である。
【図１６】この発明の実施の形態３の検索装置における区切り限定類似読み候補作成処理を示すフローチャートである。
【図１７】この発明の実施の形態３の検索装置における入力読み区切り判定処理による候補棄却の例を示す説明図である。
【発明を実施するための形態】
【００１２】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
実施の形態１．
図１は、この発明の実施の形態１による検索装置を示す構成図である。なお、以下ではカーナビにおける施設名検索を例として説明するが、本発明はカーナビの施設名検索に限定されるものではなく、住所の検索や電子マニュアルの検索など、組み込み機器上でなされる検索処理全般に適用しうるものである。
【００１３】
図１に示す検索装置は、入力部１０１、類似読み候補作成部１０３、音節バイグラム辞書１０４、名称検索部１０６、名称検索用辞書１０７を備える。入力部１０１は、ソフトウェアキーボードや音声認識などの利用者による入力操作を受け付け、読み文字列データ１０２に変換する。類似読み候補作成部１０３は、検索対象データの読みを２音節単位に分割して格納した音節バイグラム辞書１０４を参照して類似読み候補リスト１０５を作成する。名称検索部１０６は名称検索用辞書１０７を参照して、類似読み候補リスト１０５の各読み文字列を含む名称データを検索結果データ１０８として出力する。
【００１４】
なお、本発明の検索装置はコンピュータを用いて構成され、入力部１０１、類似読み候補作成部１０３、名称検索部１０６は、それぞれの機能に対応したソフトウェアをＣＰＵが実行することで構成されている。または、いずれかの処理部を専用のハードウェアで構成してもよい。また、音節バイグラム辞書１０４および名称検索用辞書１０７は、ハードディスク装置といった記憶装置上に格納されている。
【００１５】
以下、図１から図１０までを適宜参照しつつ、実施の形態１の処理内容について説明する。図２に検索処理の基本処理フローを示す。
ステップＳＴ２０１は類似読み候補作成処理であり、類似読み候補作成部１０３が、音節バイグラム辞書１０４を参照し、この検索結果の音節バイグラムを組み合わせて類似読み候補を作成する。類似読み候補作成処理の詳細については後述する。
ステップＳＴ２０２は名称検索処理である。名称検索部１０６が、名称検索用辞書１０７を参照して、類似読み候補リスト１０５を含む読みの一部に含むデータを検索結果データ１０８として出力する。名称検索処理の詳細については後述する。
【００１６】
上記のように、類似読み候補を作成するステップＳＴ２０１と、名称を検索するステップＳＴ２０２とを分割することには、以下の利点がある。すなわち、索引データ容量や計算量が大きくなる曖昧検索処理については、ステップＳＴ２０１の音節バイグラムを元にした処理とすることで、対象データ件数を少なくして容量や計算量の増大を抑制できる。また、検索対象件数が非常に多くなるステップＳＴ２０２の名称検索処理については、曖昧検索をせず単純な前方一致検索処理とすることにより、速度性能およびメモリ性能を重視した処理が可能となる。
【００１７】
次に、類似読み候補作成処理（ステップＳＴ２０１）の詳細について説明する。
図３に類似読み候補作成部１０３の詳細構成図を示す。類似読み候補木構造データ生成部３０１は、音節バイグラム辞書検索部３０２により入力読み文字列の各部分文字列と類似する音節バイグラムの情報を取得し、この情報を組み合わせて類似読み候補木構造データ３０３を生成する。このデータの詳細については後述する。類似読み候補選択部３０４は、音節別読み編集距離判定部３０５、読み編集距離累積値判定部３０６、読み編集距離累積値計算部３０７、新規候補数判定部３０８、類似読み候補スコア順選択部３０９、読み出現確率累積値計算部３１０の各手段を呼び出し、類似読み候補木構造データ生成部３０１で生成された類似読み候補木構造データ３０３をそれぞれ所定の条件に従って選択する。各処理部の動作および選択条件については後述する。類似読み候補抽出部３１１は、入力読み文字列のすべての文字位置に対して類似読み候補木構造データ３０３の生成および選択がなされた後、この類似読み候補木構造データ３０３から類似読み候補文字列のリスト（類似読み候補リスト１０５）を抽出する。
【００１８】
音節バイグラム辞書１０４は、検索対象データに付与された読み文字列を事前に音節単位に分割し、この音節単位の読み文字列中に出現するすべての音節２つ分の読み文字列をもとに作成する。音節とは、連続する言語音を区切る分節単位の一種である。ある母音を中心に、その母音単独で、またはその母音の前後に１個または複数個の子音を伴って構成する単位である。日本語でいえば平仮名１文字に相当する単位である。２つの音節の連接からなる音節バイグラムは、特許文献１に記載された装置で使用する文字トライグラムと比較すると非常に数が少なく、辞書データサイズを小さくできるという利点がある。
【００１９】
図４に音節バイグラム辞書の例を示す。同辞書データはデータを格納する部分（データ格納部４０１）と同辞書を高速に検索するための文字索引４０２からなる。データ格納部４０１では、各レコードに音節読みバイグラムＩＤ（１０４ａ）、第一音節の読み（１０４ｂ）、第二音節の読み（１０４ｃ）、出現確率（１０４ｄ）を格納する。これらは、検索対象データに付与された音節区切り入りの読み文字列、例えば検索対象データの読み文字列“ＭＩ  ＴＳＵ  ＢＩ  ＳＨＩ  ＤＥ  Ｎ  ＫＩ”からは、“ＭＩ  ＴＳＵ”、“ＴＳＵ  ＢＩ”、“ＢＩ  ＳＨＩ”、“ＳＨＩ  ＤＥ”、“ＤＥ  Ｎ”、“Ｎ  ＫＩ”という音節バイグラムを抽出し、データ格納部４０１の各レコードに格納する。その際、別途事前に各音節バイグラムの元データ中での出現頻度を計算しておき、これをもとに出現確率（１０４ｄ）を計算して格納する。
【００２０】
文字索引４０２には、上記のデータ格納部４０１に高速にアクセスするための索引情報を格納する。具体的には、入力された読み文字列中の各文字を含む音節バイグラムを高速に取得するための転置索引情報（１０４ｆ）をもつ。図４の例では、文字バイグラム（１０４ｅ）“ＡＫ”が、音節読みバイグラムＩＤが２であるレコードとＩＤが１００であるレコードに出現していることを示している。
【００２１】
次に、類似読み候補木構造データ３０３の概要を図５により説明する。類似読み候補木構造データ３０３は、多様な可能性を列挙するために生成する中間データ構造である。図中に示す音節バイグラム候補［ｎ］は、音節バイグラム辞書１０４を検索して得られる情報を示している。各候補は第一音節の読み、第二音節の読み、入力読み文字列中での文字位置などを保持する（図５中では音節バイグラム候補［１］のみに記載し、他候補では記載を省略している）。図中の音節バイグラム候補［１］〜［３］は、入力読み文字列の文字位置０で始まる部分文字列に類似する候補である。音節バイグラム［５］と［６］は、文字位置１で始まる部分文字列に類似する候補である。音節バイグラム［７］〜［１０］は文字位置３で始まる部分文字列に類似する候補である。ここで、音節バイグラム候補［５］と［６］は、音節バイグラム候補［３］に連なる候補であり、それぞれ“ＴＯ  ＳＵ  ＮＡ”、“ＴＯ  ＳＵ  ＭＡ”という類似読み候補を表現している。また、音節バイグラム候補［７］と［８］は、音節バイグラム候補［１］に連なる候補であり、それぞれ“ＴＳＵ  ＮＡ  ＳＨＩ”、“ＴＳＵ  ＮＡ  ＫＩ”という類似読み候補を表現している。このように類似読み候補木構造データ３０３では、音節バイグラムの組み合わせにより入力読み文字列と類似する読み文字列の候補を表現する。
【００２２】
図６に類似読み候補木構造データ３０３の具体例を示す。これは図５で概念的に示した木構造を具体化したものである。図６の表の１行が、図５で示した音節バイグラム候補の１つに対応する。各候補のデータは、候補ＩＤ（３０３ａ）、第一音節読み（３０３ｂ）、第二音節読み（３０３ｃ）、第一音節開始位置（３０３ｄ）、第二音節開始位置（３０３ｅ）、第二音節終了位置（３０３ｆ）、第一音節編集距離（３０３ｇ）、第二音節編集距離（３０３ｈ）、出現確率（３０３ｉ）、親ノードＩＤ（３０３ｊ）からなる。各情報がどのように設定されるかについては後述する。なお、木構造のリンク情報は３０３ｊの親ノードＩＤとして表現する。
【００２３】
図７に類似読み候補作成処理（ステップＳＴ２０１）の詳細フローを示す。以下では、図５に示した“ＴＳＵＮＡＨＩＭＡ”という読み文字列が入力された場合を例として説明する。ステップＳＴ７０１からステップＳＴ７１３は、入力読み文字数分だけ行うループ処理で、変数ｃｕｒを１ずつ増やしながらステップＳＴ７０２からステップＳＴ７１２の処理を繰り返す。ここで変数ｃｕｒは入力読み文字列中の文字位置を表しており、図５に示した読み文字列が入力された場合には、０から８まで順次更新される。
【００２４】
ステップＳＴ７０２は音節バイグラム読み文字列検索処理である。ここでは、音節バイグラム辞書検索部３０２が、入力読み文字列の文字位置ｃｕｒで始まる部分文字列と類似する読みをもつ音節バイグラムを音節バイグラム辞書１０４から検索する。
【００２５】
図８に音節バイグラム読み文字列検索処理（ステップＳＴ７０２）の詳細フローを示す。ステップＳＴ８０１は文字単位検索処理である。ここでは、文字位置ｃｕｒで始まる部分文字列の各文字を含む音節バイグラムを図４に示した文字索引４０２を用いて検索する。ｃｕｒ＝０の場合には、音節読みバイグラムＩＤが２００，２０１，２０２，２０３のデータが検索される。ｃｕｒ＝１の場合には、音節読みバイグラムＩＤが２０４，２０５のデータが検索される。ｃｕｒ＝３の場合には、音節読みバイグラムＩＤが１００，１０１，１０２，１０３のデータが検索される。この検索結果は、類似読み候補木構造データ３０３に仮登録される。ｃｕｒ＝０の場合には候補ＩＤが１，２，３，４の候補が、ｃｕｒ＝１の場合には候補ＩＤが５，６の候補が、ｃｕｒ＝３の場合には候補ＩＤが７，８，９，１０の候補がそれぞれ仮登録される。まず、音節バイグラム辞書１０４から得られる情報である第一音節読み（３０３ｂ）、第二音節読み（３０３ｃ）、出現確率（３０３ｉ）を各候補に格納する。続けて、文字位置ｃｕｒと各音節の読み長さを元に、第一音節開始位置（３０３ｄ）、第二音節開始位置（３０３ｅ）、第二音節終了位置（３０３ｆ）を計算して格納する。
【００２６】
ステップＳＴ８０２は編集距離計算処理である。ここでは、ステップＳＴ８０１で検索された音節バイグラムデータと、入力文字列の文字位置ｃｕｒで始まる部分文字列との編集距離を計算する。編集距離計算は非常にコストの大きい計算処理のため、ステップＳＴ８０１の文字単位の検索時には、ヒットした文字数、文字の出現確率等を考慮してランキングする。このランキング結果上位の所定件数について編集距離を計算し、編集距離計算結果に基づいてランキングをし直す。ここで編集距離計算は、第一音節の読みと入力読みの部分文字列、第二音節の読みと入力読みの部分文字列でそれぞれ計算する。計算結果を類似読み候補木構造データ３０３に仮登録したデータの第一音節編集距離（３０３ｇ）、第二音節編集距離（３０３ｈ）に格納する。
【００２７】
ステップＳＴ７０３は音節別読み編集距離判定処理である。ここでは、音節別読み編集距離判定部３０５が、ステップＳＴ８０２で計算された音節ごとの編集距離が所定値以下の候補を残し、それ以外の候補を棄却する。ここでは音節ごとの編集距離が１以下の候補を残すこととし、図５の音節バイグラム候補［４］を棄却する。棄却された候補であることを示すため、親ノードＩＤ（３０３ｈ）を−１に変更する。
【００２８】
ステップＳＴ７０４からステップＳＴ７１０までの二重ループ処理では、ステップＳＴ７０３の結果得られた音節バイグラム候補のすべてと、既存の音節バイグラム候補のすべての接続可否を判定すると共に、読み編集距離累積値に応じた候補選択のうえで新規の音節バイグラム候補を生成する。ｃｕｒ＝０の場合には直前の候補がない状態であるため、ステップＳＴ７０６の接続判定は常に真となりステップＳＴ７０７に進む。ｃｕｒ＞０の場合、ステップＳＴ７０３までで新たに得られた各音節バイグラム候補と既存の音節バイグラム候補の接続判定を行う。接続判定は、新規音節バイグラムの第一音節読みと既存音節バイグラムの第二音節読みが一致するかどうかにより行う。例えば、ｃｕｒ＝１の場合、音節バイグラム候補［５］［６］の第一音節読みと、音節バイグラム候補［３］の第二音節読みが一致するので、音節バイグラム候補［５］［６］の親ノードＩＤに３を格納する。同じくｃｕｒ＝３の場合、音節バイグラム候補［７］［８］の親ノードＩＤに１を、音節バイグラム候補［９］［１０］の親ノードＩＤに２をそれぞれ格納する。
【００２９】
ステップＳＴ７０７は読み編集距離累積値に応じた候補選択処理である。ここでは読み編集距離累積値計算部３０７により計算された読み編集距離累積値に応じて読み編集距離累積値判定部３０６が音節バイグラム候補を選択する。
【００３０】
読み編集距離累積値は、類似読み候補木構造データ３０３の第一音節編集距離（３０３ｇ）および第二音節編集距離（３０３ｈ）を元に計算する。ある音節バイグラム候補の編集距離累積値は、親ノードＩＤをたどりながら文字位置０となる音節バイグラム候補まで第二音節編集距離（３０３ｈ）を加算し、最後に第一音節編集距離（３０３ｇ）を加算することで得られる。例えば、図５及び図６に示した音節バイグラム候補［８］の場合、読み編集距離累積値は１＋０＋０＝１となる。また、音節バイグラム候補［１０］の場合、読み編集距離累積値は１＋１＋０＝２となる。
【００３１】
候補の採否を決める閾値Ｔｈ１は、入力読み文字列の長さＬによって決める。入力読み文字列が長い場合には、誤りの含まれる可能性が高いので大きな値を設定する。例えば、Ｌ／４を閾値とし、読み編集距離累積値がこれより大きくなった類似読み候補を棄却する。ｃｕｒ＝０の場合は、音節バイグラム候補［１］［２］［３］のいずれの候補も読み編集距離の累積値が１以下となるので、全候補が棄却されずに採用される。ｃｕｒ＝１の場合は、音節バイグラム候補［６］では編集距離の累積値が２となるので棄却される。ｃｕｒ＝３の場合、同様にして音節バイグラム［１０］が棄却される。
【００３２】
ステップＳＴ７０８は類似読み候補木構造更新処理である。上記のステップＳＴ８０１で仮登録された候補を正式に登録する。例えばｃｕｒ＝０の場合には図６における候補ＩＤが１，２，３の行が正式に登録される。候補ＩＤが４の行についてはステップＳＴ７０３において棄却済みであるため正式登録はされない。図５との対応をとりやすくするため図６中にも記載しているが、メモリ使用量を抑制するためｃｕｒ＝１以降の処理で上書きしてもよい。同様にｃｕｒ＝１の場合には、候補ＩＤが５の候補が正式登録され、候補ＩＤが６の候補はステップＳＴ７０７で棄却されるので正式登録されない。同じくｃｕｒ＝３の場合には、候補ＩＤが７，８，９の候補が正式登録される。
【００３３】
ステップＳＴ７０４からステップＳＴ７１０までの二重ループ処理が終了すると、ステップＳＴ７１１に進む。ステップＳＴ７１１では、新規候補数判定部３０８が、現在の文字位置ｃｕｒにおいて追加された新規音節バイグラム候補数による選択処理判定を行う。
【００３４】
新規候補数が所定の閾値Ｔｈ２よりも多い場合に、ステップＳＴ７１２に進み類似読み候補スコア順選択部３０９が音節バイグラム候補をスコア順に整列し、スコア上位の候補を残し、スコア下位の候補を棄却する。ここで閾値Ｔｈ２は、メモリ使用量や速度性能など該当機能が満たすべき外部の条件に従い、適宜設定するものとする。
【００３５】
スコア計算は、読み出現確率累積値計算部３１０により行う。具体的には、ある音節バイグラム候補のスコアは、親ノードＩＤをたどりながら文字位置０となる音節バイグラム候補まで出現確率（３０３ｉ）を順次加算することにより得る。また、読み編集距離累積値計算部３０７により計算された編集距離累積値をスコアとして用いても良い。編集距離累積値の計算方法は、ステップＳＴ７０７と同様の手順とする。
【００３６】
ステップＳＴ７０１からステップＳＴ７１３までのループ処理が終了すると、ステップＳＴ７１４に進む。なお、図７中には示していないが、ステップＳＴ７０１の直後に、ステップＳＴ７０６の接続判定を行うようにしても良い。すなわち、既存の音節バイグラム候補のいずれも第二音節終了位置（３０３ｆ）が現在の文字位置ｃｕｒでなければ、ステップＳＴ７０２、ＳＴ７０３の処理をしたとしてもステップＳＴ７０６ですべて棄却されてしまう。ループ処理の先頭でこのような事前の接続検定を行い、接続可能な候補がなければステップＳＴ７０２以下の処理をスキップすることで無駄な処理を防ぐことができる。
【００３７】
ステップＳＴ７１４では類似読み候補抽出部３１１が、類似読み候補木構造データ３０３から実際の類似読み候補文字列を抽出する。類似読み候補文字列は、木構造データの末端にあり、かつ、第二音節終了位置（３０３ｆ）が入力読み文字列の末端に達している音節バイグラム候補に対して、親ノードＩＤをたどりながら文字位置０となる音節バイグラム候補まで第二音節読み（３０３ｃ）を順次連結し、最後に第一音節読み（３０３ｂ）を連結して得られた文字列を逆順にすることで得られる。
【００３８】
以上が図２のステップ２０１の類似読み候補作成処理の詳細である。次にステップＳＴ２０２の名称検索処理について説明する。
【００３９】
名称検索処理では、名称検索部１０６が、名称検索用辞書１０７を参照して、類似読み候補リスト１０５を含む名称データを検索して出力する。ここでは、例えば、特開２０１０−２０５１１９号公報に示される検索手法を用いることとする。検索手法の詳細については文献中に記載されているため、以下では検索処理の概略を説明する。
【００４０】
図９に名称検索用辞書１０７の構成例を示す。名称検索部１０６は、ダブル配列索引データ９０１に基づいて、与えられた類似読み候補文字列に該当するノードを探索する。続けて、最小・最大子ノード索引９０２に基づいて、上記で探索されたノードの子ノードのうち、辞書順で最小の文字列となるノードと最大の文字列となるノードとを探索する。さらに、名称リスト９０３より、上記で探索された最小ノードに対応する名称から最大ノードに対応する名称までのすべての名称を抽出して検索結果データ１０８とする。
【００４１】
図１０に名称リスト９０３の例を示す。名称リスト９０３は少なくとも、各名称を一意に特定する名称ＩＤ（９０３ａ）と、その名称の読み文字列（９０３ｂ）と、種別情報（９０３ｃ）からなるものとする。なお、図１０では、同一の名称ＩＤである３をもつ行を２箇所に示しているが、これは、読み文字列（９０３ｂ）を、途中の文字からでも検索可能とするため事前に展開して索引化しているためである。
【００４２】
上記の説明では、一例として特開２０１０−２０５１１９号公報に記載のダブル配列索引を用いた検索手法を示したが、ステップＳＴ２０２の名称検索処理は、類似読み候補リスト１０５に含まれる各類似読み候補文字列から、その読み文字列を含む名称データを高速に検索できる手法であればどのようなものであっても適用可能である。例えば、組み込み機器向けのデータベースを用いても良いし、図９に示した名称リスト９０３のもつ情報を高速検索するための木構造索引データの中に埋め込む構造としても良い。
【００４３】
このように、実施の形態１では、検索対象データの読みを２音節単位に分割して格納した音節バイグラム辞書１０４と、ユーザが入力した読み文字列の一部の文字列と類似する読み文字列を音節バイグラム辞書１０４から検索し、これらを組み合わせて類似読み候補を作成する手段を設けたことにより、事前の単語区切りが不要で、かつ、日本語や韓国語や中国語などのユーザが複数の単語を連続して入力しうる言語において柔軟かつ高速な曖昧検索が可能となる。
また、所定の選択基準により適宜候補を選択しつつ類似読み候補を作成するための類似読み候補選択部３０４を設けたことにより、入力文字数が大きくなっても組み合わせが急激に増加することなく、省メモリかつ高速な類似読み文字列候補の作成が可能となる。
【００４４】
以上説明したように、実施の形態１の検索装置によれば、検索対象データの読みを２音節単位に分割して格納した音節バイグラム辞書と、正式名称を格納した名称検索用辞書と、与えられた読み文字列の一部の文字列と類似する読み文字列を音節バイグラム辞書から検索し、検索した文字列を組み合わせて類似読み候補を作成する類似読み候補作成部と、類似読み候補作成部で作成された類似読み候補を元に名称検索用辞書から正式名称を検索する名称検索部とを備えたので、通称や略称、うろ覚えの誤った名称などを検索キーとして検索した場合であっても元の正式名称を曖昧検索して出力できる検索装置として、省メモリでかつ高速な処理を実現することができる。
【００４５】
また、実施の形態１の検索装置によれば、類似読み候補作成部は、検索した文字列を組み合わせて作成した類似読み候補を取捨選択する類似読み候補選択部を備えたので、省メモリかつ高速に曖昧検索結果を得ることができる。
【００４６】
また、実施の形態１の検索装置によれば、類似読み候補選択部は、音節バイグラム辞書から検索された各音節の読みと、これと対応する与えられた読み文字列の部分文字列との編集距離が所定値以下の類似読み候補を選択し、これ以外の類似読み候補を棄却する音節別読み編集距離判定部を備えたので、省メモリかつ高速に曖昧検索結果を得ることができる。
【００４７】
また、実施の形態１の検索装置によれば、類似読み候補選択部は、音節バイグラム辞書から検索された各音節の読みと、これと対応する与えられた読み文字列の部分文字列との編集距離の累積値を計算する読み編集距離累積値計算部と、読み編集距離累積値計算部により計算された読み編集距離累積値が所定値以下の類似読み候補を選択し、これ以外の類似読み候補を棄却する読み編集距離累積値判定部とを備えたので、省メモリかつ高速に曖昧検索結果を得ることができる。
【００４８】
また、実施の形態１の検索装置によれば、類似読み候補選択部は、類似読み候補数が所定値を超えたかどうかを判定する新規候補数判定部と、新規候補数判定部で所定値を超えたと判定した場合、類似読み候補のスコアを計算し、スコア上位の所定値の類似読み候補のみを残す類似読み候補スコア順選択部を備えたので、省メモリかつ高速に曖昧検索結果を得ることができる。
【００４９】
また、実施の形態１の検索装置によれば、類似読み候補スコア順選択部は、読み編集距離累積値計算部により計算された読み編集距離の累積値を元に類似読み候補のスコアを計算するようにしたので、省メモリかつ高速に曖昧検索結果を得ることができる。
【００５０】
また、実施の形態１の検索装置によれば、類似読み候補選択部は、音節バイグラム辞書から検索された各音節の出現確率の累積値を計算する読み出現確率累積値計算部を有し、類似読み候補スコア順選択部は、読み出現確率累積値計算部の計算結果を元に類似読み候補のスコアを計算するようにしたので、省メモリかつ高速に曖昧検索結果を得ることができる。
【００５１】
実施の形態２．
図１１は、実施の形態２の検索装置を示す構成図である。実施の形態２は、実施の形態１における類似読み候補作成部１０３に代えて名称先読み類似読み候補作成部１１０１を設けたものである。名称先読み類似読み候補作成部１１０１は、検索対象データの読みを２音節単位に分割して格納した音節バイグラム辞書１０４を参照して類似読み候補リスト１０５ａを作成する。その際、候補選択処理の一部で名称検索用辞書１０７も参照する。その他の構成については図１に示した実施の形態１の構成と同様であるため、対応する部分に同一符号を付してその説明を省略する。
【００５２】
図１２に、名称先読み類似読み候補作成部１１０１の詳細構成図を示す。名称有無判定部１２０１は名称検索用辞書１０７を参照し、類似読み候補が名称辞書中に存在するかどうかを判定する。これ以外の構成については図３に示した実施の形態１の構成と同様であるので、対応する部分に同一符号を付してその説明を省略する。
【００５３】
図１３は、実施の形態２における名称先読み類似読み候補作成処理を示すフローチャートである。ステップＳＴ１３０１の名称検索有無判定処理以外については、実施の形態１の図７に示した処理と同様であるため、ステップＳＴ１３０１以外の処理についてはその説明を省略する。ステップＳＴ１３０１では、まず、ステップＳＴ７０７の処理結果の各音節バイグラム候補に対し、類似読み候補抽出部３１１により類似読み候補文字列を抽出する。次に、名称有無判定部１２０１が名称検索用辞書１０７を参照し、この類似読み候補文字列が名称検索用辞書１０７中に存在するかどうかを判定する。もし存在しないのであれば、後段の名称検索処理で検索に失敗するので、この時点で候補を棄却する。
なお、ステップＳＴ１３０１の名称有無判定処理では、最終的な名称データ自体は必要ないため、ダブル配列索引データ９０１（図９参照）のみを用いることで、より高速な検索処理を行う。
【００５４】
以上説明したように、実施の形態２の検索装置によれば、類似読み候補選択部は、類似読み候補に対し、名称検索用辞書を検索することで名称の一部となり得る類似読み候補を選択し、これ以外の類似読み候補を棄却する名称有無判定部を備えたので、類似読み候補のうち、実際に名称検索して結果が得られるもののみを選択でき、さらに省メモリかつ高速な曖昧検索処理が可能となる。
【００５５】
実施の形態３．
図１４は実施の形態３の検索装置を示す構成図である。実施の形態３は、実施の形態１における入力部１０１と類似読み候補作成部１０３に代えて読み変換入力部１４０１と区切り限定類似読み候補作成部１４０３とを設けたものである。読み変換入力部１４０１では、日本語の仮名漢字変換、中国語のピンイン漢字変換、韓国語の字母ハングル変換など、ユーザが読み文字列を入力して表記文字列に変換する。その結果を表記の１文字ずつに対応するよう読み文字列に区切りが付与された区切り付き読み文字列データ１４０２として取得する。区切り限定類似読み候補作成部１４０３では、区切り付き読み文字列データ１４０２を用いて、実施の形態１と同様に音節バイグラム辞書１０４を参照して、類似読み候補リスト１０５ｂを作成する。その他の構成については図１に示した実施の形態１と同様であるため、対応する部分に同一符号を付してその説明を省略する。
【００５６】
図１５は、区切り限定類似読み候補作成部１４０３の詳細を示す構成図である。区切り限定類似読み候補木構造データ生成部１５０１は、音節バイグラム辞書検索部３０２により区切り付き読み文字列データ１４０２の各部分文字列と類似する音節バイグラムの情報を取得し、この情報を組み合わせて類似読み候補木構造データ３０３を生成する。これ以外の構成については図３に示した実施の形態１の構成と同様であるので、対応する部分に同一符号を付してその説明を省略する。
【００５７】
図１６は、実施の形態３における区切り限定類似読み候補作成処理を示すフローチャートである。ステップＳＴ１６０１の入力読み区切り判定処理以外については、実施の形態１の図７に示した処理と同様であるため、ステップＳＴ１６０１以外の処理についてはその説明を省略する。ステップＳＴ１６０１では、入力された読み区切りの情報を元に、音節バイグラム検索結果を類似読み候補木構造データ３０３に登録するかどうかを判定する。具体的には、現在の文字位置ｃｕｒと検索結果の第一音節の読み長さが、入力された読み文字列区切りに一致するか否かを判定し、一致しない場合にはその候補を棄却する。
【００５８】
ステップＳＴ１６０１で候補が棄却される例を図１７に示す。この例では、区切り付き入力読み文字列が「ＴＳＵ／ＮＡ／ＨＩ／ＭＡ」であるのに対し、音節バイグラム候補［３］では、２音節分で区切り付き読み入力の「ＴＳＵ」に対応しており音節区切りが一致しないので棄却される。
【００５９】
以上説明したように、実施の形態３の検索装置によれば、検索対象データの読みを２音節単位に分割して格納した音節バイグラム辞書と、正式名称を格納した名称検索用辞書と、音節単位で区切られた区切り付き読み文字列の一部の文字列と類似する読み文字列を音節バイグラム辞書から検索し、検索した文字列を組み合わせて類似読み候補を作成すると共に、区切り付き読み文字列に対し、区切り読み文字列中の音節区切りと音節バイグラム辞書の検索結果との一致判定を行い、区切りが一致しない音節バイグラム検索結果を棄却して類似読み候補を作成する区切り限定類似読み候補作成部と、区切り限定類似読み候補作成部で作成された類似読み候補を元に名称検索用辞書から正式名称を検索する名称検索部とを備えたので、入力と一致しない不要な音節バイグラム候補を棄却でき、さらに省メモリかつ高速な曖昧検索が可能となる。
【００６０】
なお、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【産業上の利用可能性】
【００６１】
以上のように、この発明に係る検索装置は、読み文字列の一部の文字列と類似する読み文字列を音節バイグラム辞書  から検索し、検索した文字列を組み合わせて類似読み候補を作成して正式名称を検索するようにしたものであり、カーナビの施設名検索や、住所の検索や電子マニュアルの検索など組み込み機器上でなされる検索処理全般に適用しうる。
【符号の説明】
【００６２】
１０１  入力部、１０２  読み文字列データ、１０３  類似読み候補作成部、１０４  音節バイグラム辞書、１０５，１０５ａ，１０５ｂ  類似読み候補リスト、１０６  名称検索部、１０７  名称検索用辞書、１０８  検索結果データ、３０１  類似読み候補木構造データ生成部、３０２  音節バイグラム辞書検索部、３０３  類似読み候補木構造データ、３０４  類似読み候補選択部、３０５  音節別読み編集距離判定部、３０６  読み編集距離累積値判定部、３０７  読み編集距離累積値計算部、３０８  新規候補数判定部、３０９  類似読み候補スコア順選択部、３１０  読み出現確率累積値計算部、３１１  類似読み候補抽出部、１１０１  名称先読み類似読み候補作成部、１２０１  名称有無判定部、１４０１  読み変換入力部、１４０２  区切り付き読み文字列データ、１４０３  区切り限定類似読み候補作成部、１５０１  区切り限定類似読み候補木構造データ生成部。
【図１】
0005866084.tif 000002
【図２】
0005866084.tif 000003
【図３】
0005866084.tif 000004
【図４】
0005866084.tif 000005
【図５】
0005866084.tif 000006
【図６】
0005866084.tif 000007
【図７】
0005866084.tif 000008
【図８】
0005866084.tif 000009
【図９】
0005866084.tif 000010
【図１０】
0005866084.tif 000011
【図１１】
0005866084.tif 000012
【図１２】
0005866084.tif 000013
【図１３】
0005866084.tif 000014
【図１４】
0005866084.tif 000015
【図１５】
0005866084.tif 000016
【図１６】
0005866084.tif 000017
【図１７】
0005866084.tif 000018