(57)【要約】  【課題】  タイプミスが検索結果に及ぼす影響を低減し、ユーザが所望の検索結果を得やすい検索装置を提供すること。  【解決手段】  本発明の検索装置によれば、入力文字列及び検索文字列の類似性を判定する上で、（１）それぞれの文字列に基づく画像に基づいて得られる類似性を判定可能な値と、（２）文字列を作成する装置における各構成文字の配列又は入力規則に応じて１の座標を予め対応付けた文字マップ上における、入力文字列及び検索対象文字列において互いに対応する出現位置の構成文字間の距離に基づいて得られる類似性を判定可能な値とを組み合わせて利用する。その結果として、従来であれば予測の範囲外とされて別の文字列として認識されるようなタイプミスを有する検索文字列に対しても、ユーザの意図通りの検索が行われるので、ユーザの所望する検索結果が提供される。  【選択図】    図４
2006227743.tif 000002
【特許請求の範囲】
【請求項１】
ユーザにより入力された１又は複数の構成文字からなる文字列に一致又は類似する文字列が存在するか否かを検索する検索装置において、
１又は複数の構成文字からなる文字列を入力文字列として入力する入力手段と、
その入力手段により入力された入力文字列に対する検索対象とされる文字列を複数記憶するメモリと、
そのメモリから１の文字列を検索対象文字列として抽出する検索対象文字列抽出手段と、
文字列を構成する構成文字の各々に対して１の座標を予め対応付けた文字マップと、
文字列を構成する構成文字毎に、前記文字マップに対応する座標に該文字列における出現位置に応じた値を付与することによって各座標に濃淡を発生させて、該文字列を濃淡画像の画像データに変換する画像化手段と、
前記画像化手段によって画像化した前記入力手段により入力された入力文字列に基づく画像データと、前記画像化手段により画像化した前記検索対象文字列抽出手段により抽出された１の検索対象文字列に基づく画像データとを比較することに基づいて、前記１の検索対象文字列に対する前記入力文字列の類似性を判定可能な値を取得する画像類似度取得手段と、
その画像類似度取得手段により取得された類似性を判定可能な値に基づいて、前記入力文字列と前記１の検索対象文字列との類似性を判定する類似性判定手段とを備え、
前記類似性判定手段による判定を、前記メモリに記憶される複数の文字列の各々に対して行うことを特徴とする検索装置。
【請求項２】
ユーザにより入力された１又は複数の構成文字からなる文字列に一致又は類似する文字列が存在するか否かを検索する検索装置において、
１又は複数の構成文字からなる文字列を入力文字列として入力する入力手段と、
その入力手段に対する検索対象となり得る文字列を複数記憶するメモリと、
そのメモリから１の文字列を検索対象文字列として抽出する検索対象文字列抽出手段と、
文字列を構成する構成文字の各々に対して、その文字列を作成する装置における各構成文字の配列又は入力規則に応じて１の座標を予め対応付けた第１文字マップと、
前記入力手段により入力された入力文字列を構成する各構成文字と、前記検索対象文字列抽出手段により抽出された１の検索対象文字列を構成する各構成文字とについて、前記第１文字マップの座標を参照して、互いに対応する出現位置にある構成文字の各組の構成文字間の距離をそれぞれ得、得られた距離に基づいて前記入力文字列と前記１の検索対象文字列との類似性を判定可能な値を取得する位置類似度取得手段と、
その位置類似度取得手段により取得された類似性を判定可能な値に基づいて、前記入力文字列と前記１の検索対象文字列との類似性を判定する類似性判定手段とを備え、
前記類似性判定手段による判定を、前記メモリに記憶される複数の文字列の各々に対して行うことを特徴とする検索装置。
【請求項３】
前記位置類似度取得手段により得られる前記類似性を判定可能な値として、前記距離が離れるに従って類似性を否定する値を用いることを特徴とする請求項２記載の検索装置。
【請求項４】
文字列を構成する構成文字の各々に対して１の座標を予め対応付けた第２文字マップと、
文字列を構成する構成文字毎に、前記第２文字マップに対応する座標に該文字列における出現位置に応じた値を付与することによって各座標に濃淡を発生させて、該文字列を濃淡画像の画像データに変換する画像化手段と、
前記画像化手段によって画像化した前記入力手段により入力された入力文字列に基づく画像データと、前記画像化手段により画像化した前記検索対象文字列抽出手段により抽出された１の検索対象対象文字列に基づく画像データとを比較することに基づいて、前記１の検索対象文字列に対する前記入力文字列の類似性を判定可能な値を取得する画像類似度取得手段とを備え、
前記類似性判定手段は、前記位置類似度取得手段により取得された前記類似性を判定可能な値と、前記画像類似度取得手段により取得された前記類似性を判定可能な値とを組み合わせることによって、前記入力文字列と前記１の検索対象文字列との類似性を判定することを特徴とする請求項２又は３記載の検索装置。
【請求項５】
前記位置類似度取得手段により取得された前記類似性を判定可能な値と前記画像類似度取得手段により取得された前記類似性を判定可能な値とを組み合わせる場合に、前記入力文字列の構成文字数又は前記検索対象文字列の構成文字数のうちの少ない方の構成文字数が所定数以下又は所定数未満であれば、前記位置類似度取得手段により取得された前記類似性を判定可能な値に対する重み付け係数を、前記画像類似度取得手段により取得された前記類似性を判定可能な値に対する重み付け係数より大きくして互いの値を組合わせることを特徴とする請求項４記載の検索装置。
【請求項６】
前記位置類似度取得手段により取得された前記類似性を判定可能な値と前記画像類似度取得手段により取得された前記類似性を判定可能な値とを組み合わせる場合に、前記入力文字列の構成文字数又は前記検索対象文字列の構成文字数のうちの少ない方の構成文字数が所定数を越える又は所定数以上であれば、前記画像類似度取得手段により取得された前記類似性を判定可能な値に対する重み係数を、前記位置類似度取得手段により取得された前記類似性を判定可能な値に対する重み係数より大きくして互いの値を組み合わせることを特徴とする請求項４記載の検索装置。
【請求項７】
前記検索対象文字列抽出手段は、前記メモリに記憶される複数の文字列の中から、前記入力文字列の構成文字数に応じた範囲内の構成文字数から構成されるものを検索対象文字列として抽出することを特徴とする請求項１から６のいずれかに記載の検索装置。
【請求項８】
前記入力文字列を構成する構成文字数と前記検索対象文字列抽出手段により抽出された検索対象文字列を構成する構成文字数とが異なる場合に、構成文字数の多い方の文字列から、その文字列の文字配列順に従って、構成文字数の少ない方の文字列に応じた数の構成文字を抽出することによって、複数の異なる小文字列を得る小文字列抽出手段を備え、
前記画像類似度取得手段及び／又は前記位置類似度取得手段による前記類似性を判定可能な値は、前記小文字列抽出手段によって前記構成文字数の多い方の文字列から抽出された複数の異なる小文字列のそれぞれと構成文字数の少ない方の文字列との類似性の比較に基づいて得られることを特徴とする請求項１から７のいずれかに記載の検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索装置に関し、特に、入力の際にタイプミスがあっても所望の情報を有効に検索できる検索装置に関する。
【背景技術】
【０００２】
一般的に、ユーザが入力する入力文字列に基づいて情報を検索する場合には、入力文字列が所望する情報に対して正確であることが要求される。しかし、入力時の文字列のタイプミスやユーザ自身の誤認識などの種々の理由により、正確な（適切な）入力文字列が入力されずに所望の情報に到達できないという問題があり、従来より、そのような問題を解決するための技術が多く提案されている。
【０００３】
例えば、特開１０−２４０７４３号公報（特許文献１）には、文字列を有する名簿やカタログなどの情報検索・蓄積方法が記載されている。この方法によれば、文字列情報の蓄積時に、入力された原文字列以外の入力候補文字列が生成され、その入力候補文字列に応じた文字列が蓄積文字列として蓄積される。一方で、検索時に、検索文字列が入力されると、該検索文字列以外で検索可能な検索候補文字列が生成され、検索文字情報と蓄積されている蓄積文字列とを照合することにより検索が行われて検索解候補が出力される。
【特許文献１】特開１０−２４０７４３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１に記載される方法は、蓄積時に間違いやすい文字列を予め予測して蓄積文字列として蓄積しておく方式であるので、予測不能なタイプミスがあった場合には、蓄積文字列の範囲外の文字列と判断されることになる。そのため、ユーザが検索を意図して入力した原文字列にいくつかの誤字や脱字が含まれた場合などは、ユーザの意図とは別の文字列として処理されてしまい、その結果として、ユーザは所望する検索結果を得られなくなってしまう問題点があった。
【０００５】
本発明は、上述した問題点を解決するためになされたものであり、タイプミスが検索結果に及ぼす影響を低減し、ユーザが所望の検索結果を得やすい検索装置を提供することを目的としている。
【課題を解決するための手段】
【０００６】
この目的を達成するために、請求項１記載の検索装置は、ユーザにより入力された１又は複数の構成文字からなる文字列に一致又は類似する文字列が存在するか否かを検索するものであって、１又は複数の構成文字からなる文字列を入力文字列として入力する入力手段と、その入力手段により入力された入力文字列に対する検索対象とされる文字列を複数記憶するメモリと、そのメモリから１の文字列を検索対象文字列として抽出する検索対象文字列抽出手段と、文字列を構成する構成文字の各々に対して１の座標を予め対応付けた文字マップと、文字列を構成する構成文字毎に、前記文字マップに対応する座標に該文字列における出現位置に応じた値を付与することによって各座標に濃淡を発生させて、該文字列を濃淡画像の画像データに変換する画像化手段と、前記画像化手段によって画像化した前記入力手段により入力された入力文字列に基づく画像データと、前記画像化手段により画像化した前記検索対象文字列抽出手段により抽出された１の検索対象文字列に基づく画像データとを比較することに基づいて、前記１の検索対象文字列に対する前記入力文字列の類似性を判定可能な値を取得する画像類似度取得手段と、その画像類似度取得手段により取得された類似性を判定可能な値に基づいて、前記入力文字列と前記１の検索対象文字列との類似性を判定する類似性判定手段とを備え、前記類似性判定手段による判定を、前記メモリに記憶される複数の文字列の各々に対して行う。
【０００７】
請求項２記載の検索装置は、ユーザにより入力された１又は複数の構成文字からなる文字列に一致又は類似する文字列が存在するか否かを検索するものであって、１又は複数の構成文字からなる文字列を入力文字列として入力する入力手段と、その入力手段に対する検索対象となり得る文字列を複数記憶するメモリと、そのメモリから１の文字列を検索対象文字列として抽出する検索対象文字列抽出手段と、文字列を構成する構成文字の各々に対して、その文字列を作成する装置における各構成文字の配列又は入力規則に応じて１の座標を予め対応付けた第１文字マップと、前記入力手段により入力された入力文字列を構成する各構成文字と、前記検索対象文字列抽出手段により抽出された１の検索対象文字列を構成する各構成文字とについて、前記第１文字マップの座標を参照して、互いに対応する出現位置にある構成文字の各組の構成文字間の距離をそれぞれ得、得られた距離に基づいて前記入力文字列と前記１の検索対象文字列との類似性を判定可能な値を取得する位置類似度取得手段と、その位置類似度取得手段により取得された類似性を判定可能な値に基づいて、前記入力文字列と前記１の検索対象文字列との類似性を判定する類似性判定手段とを備え、前記類似性判定手段による判定を、前記メモリに記憶される複数の文字列の各々に対して行う。
【０００８】
請求項３記載の検索装置は、請求項２記載の検索装置において、前記位置類似度取得手段により得られる前記類似性を判定可能な値として、前記距離が離れるに従って類似性を否定する値を用いる。
【０００９】
請求項４記載の検索装置は、請求項２又は３記載の検索装置において、文字列を構成する構成文字の各々に対して１の座標を予め対応付けた第２文字マップと、文字列を構成する構成文字毎に、前記第２文字マップに対応する座標に該文字列における出現位置に応じた値を付与することによって各座標に濃淡を発生させて、該文字列を濃淡画像の画像データに変換する画像化手段と、前記画像化手段によって画像化した前記入力手段により入力された入力文字列に基づく画像データと、前記画像化手段により画像化した前記検索対象文字列抽出手段により抽出された１の検索対象対象文字列に基づく画像データとを比較することに基づいて、前記１の検索対象文字列に対する前記入力文字列の類似性を判定可能な値を取得する画像類似度取得手段とを備え、前記類似性判定手段は、前記位置類似度取得手段により取得された前記類似性を判定可能な値と、前記画像類似度取得手段により取得された前記類似性を判定可能な値とを組み合わせることによって、前記入力文字列と前記１の検索対象文字列との類似性を判定する。
【００１０】
請求項５記載の検索装置は、請求項４記載の検索装置において、前記位置類似度取得手段により取得された前記類似性を判定可能な値と前記画像類似度取得手段により取得された前記類似性を判定可能な値とを組み合わせる場合に、前記入力文字列の構成文字数又は前記検索対象文字列の構成文字数のうちの少ない方の構成文字数が所定数以下又は所定数未満であれば、前記位置類似度取得手段により取得された前記類似性を判定可能な値に対する重み付け係数を、前記画像類似度取得手段により取得された前記類似性を判定可能な値に対する重み付け係数より大きくして互いの値を組合わせる。
【００１１】
請求項６記載の検索装置は、請求項４記載の検索装置において、前記位置類似度取得手段により取得された前記類似性を判定可能な値と前記画像類似度取得手段により取得された前記類似性を判定可能な値とを組み合わせる場合に、前記入力文字列の構成文字数又は前記検索対象文字列の構成文字数のうちの少ない方の構成文字数が所定数を越える又は所定数以上であれば、前記画像類似度取得手段により取得された前記類似性を判定可能な値に対する重み係数を、前記位置類似度取得手段により取得された前記類似性を判定可能な値に対する重み係数より大きくして互いの値を組み合わせる。
【００１２】
請求項７記載の検索装置は、請求項１から６のいずれかに記載の検索装置において、前記検索対象文字列抽出手段は、前記メモリに記憶される複数の文字列の中から、前記入力文字列の構成文字数に応じた範囲内の構成文字数から構成されるものを検索対象文字列として抽出する。
【００１３】
請求項８記載の検索装置は、請求項１から７のいずれかに記載の検索装置において、前記入力文字列を構成する構成文字数と前記検索対象文字列抽出手段により抽出された検索対象文字列を構成する構成文字数とが異なる場合に、構成文字数の多い方の文字列から、その文字列の文字配列順に従って、構成文字数の少ない方の文字列に応じた数の構成文字を抽出することによって、複数の異なる小文字列を得る小文字列抽出手段を備え、前記画像類似度取得手段及び／又は前記位置類似度取得手段による前記類似性を判定可能な値は、前記小文字列抽出手段によって前記構成文字数の多い方の文字列から抽出された複数の異なる小文字列のそれぞれと構成文字数の少ない方の文字列との類似性の比較に基づいて得られる。
【発明の効果】
【００１４】
請求項１記載の検索装置によれば、画像化手段によって、文字列を構成する構成文字毎に、文字マップに対応する座標に該文字列における出現位置に応じた値を付与することによって各座標に濃淡を発生させ、該文字列が濃淡画像の画像データに変換される。なお、文字マップとは、文字列を構成する構成文字の各々に対して１の座標を予め対応付けたものである。
【００１５】
一方で、入力手段から１又は複数の構成文字からなる文字列が入力文字列として入力されると、その入力文字列に対する検索対象とされる文字列を複数記憶するメモリから、検索対象文字列抽出手段によって、１の文字列が検索対象文字列として抽出される。
【００１６】
すると、抽出された１の検索対象文字列と入力文字列とに基づく画像データが、それぞれ該画像化手段により得られ、それらの画像データが、画像類似度取得手段により、比較された結果として、該入力文字列と該１の検索対象文字列との類似性を判定可能な値が取得される。
【００１７】
画像類似度取得手段により、該１の検索対象文字列に対する該入力文字列の類似性を判定可能な値が取得されると、その値に基づいて、類似性判定手段により、該１の検索対象文字列に対する該入力文字列の類似性が判定される。
【００１８】
そして、そのような類似性判定手段による類似性の判定が、該メモリに記憶される複数の文字列の各々に対して行われる。
【００１９】
よって、検索文字列（入力文字列）及び検索文字列のそれぞれに基づく画像を用いてそれらの文字列の類似性を判定するので、入力文字列と検索対象文字列との間において一部に局部的な相違があったとしても、そのような文字列間の局部的な相違が文字列間の類似性に与える影響は相対的に小さいものとなる。その結果として、従来であれば予測の範囲外とされて別の文字列として認識されるようなタイプミスを有する検索文字列に対しても、ユーザの意図通りの検索が行われるので、ユーザの所望する検索結果を提供することができるという効果がある。
【００２０】
なお、請求項１における「入力文字列に基づく画像データ」は、入力文字列の全てに対して得られた画像データだけでなく、入力文字列の一部に対して得られた画像データを含む。同様に、「１の検索対象文字列に基づく画像データ」もまた、１の検索対象文字列の全てに対して得られた画像データだけでなく、その検索対象文字列の一部に対して得られた画像データを含む。
【００２１】
請求項２記載の検索装置によれば、入力手段から１又は複数の構成文字からなる文字列が入力文字列として入力されると、その入力文字列に対する検索対象とされる文字列を複数記憶するメモリから、検索対象文字列抽出手段によって、１の文字列が検索対象文字列として抽出される。
【００２２】
すると、抽出された１の検索対象文字列及び入力文字列をそれぞれ構成する各構成文字について、位置類似度取得手段により、第１文字マップを用いて、互いに対応する出現位置にある構成文字間の距離を各構成文字の組毎に得た上で、それらの距離に基づいて、該１の検索対象文字列に対する該入力文字列の類似性を判定可能な値が取得される。なお、第１文字マップとは、文字列を構成する構成文字の各々に対して、その文字列を作成する装置における各構成文字の配列又は入力規則に応じて１の座標を予め対応付けたものである。
【００２３】
位置類似度取得手段により、該１の検索対象文字列に対する該入力文字列の類似性を判定可能な値が取得されると、その値に基づいて、類似性判定手段により、該入力文字列と該１の検索対象文字列との類似性が判定される。
【００２４】
そして、そのような類似性判定手段による類似性の判定が、該メモリに記憶される複数の文字列の各々に対して行われる。
【００２５】
よって、文字列を作成する装置における各構成文字の配列又は入力規則に応じて１の座標を予め対応付けた第１文字マップを用いることによって位置類似度取得手段により取得される類似性を判定可能な値は、ユーザが検索を意図して入力する入力文字列におけるタイプミスによる影響を考慮した値となる。即ち、入力文字列と検索対象文字列との相違が、ユーザの意図に基づく検索文字列と全く違うものであることに起因するものであるのか、ユーザによる検索文字列の入力時のキーのタイプミスに起因するものであるのかを判定することが可能な値である。
【００２６】
従って、位置類似度取得手段により取得される類似性を判定可能な値を用いて、入力文字列と検索対象文字列との類似性に対する判定がなされる結果として、従来であれば予測の範囲外とされて別の文字列として認識されるようなタイプミスを有する検索文字列に対しても、ユーザの意図通りの検索が行われるので、ユーザの所望する検索結果を提供することができるという効果がある。
【００２７】
なお、請求項２における「互いに対応する出現位置」とは、類似性を比較する上で用いられる入力文字列の全体又は一部と１の検索対象文字列の全体又は一部とについて、それらの全体又は一部の文字列における比較の上での対応する出現位置を意味する。
【００２８】
請求項３記載の検索装置によれば、請求項２記載の検索装置の奏する効果に加えて、位置類似度取得手段により得られる前記類似性を判定可能な値として、第１文字マップ上における距離が離れるに従って類似性を否定する値を用いるので、入力文字列と検索対象文字列との相違が、ユーザの意図に基づく検索文字列と全く違うものであることに起因するものであるのか、ユーザによる検索文字列の入力時のキーのタイプミスに起因するものであるのかを判定することが容易である。
【００２９】
従って、位置類似度取得手段により取得される類似性を判定可能な値を用いて、入力文字列と検索対象文字列との類似性に対する判定がなされる結果として、従来であれば予測の範囲外とされて別の文字列として認識されるようなタイプミスを有する検索文字列に対しても、ユーザの意図通りの検索が行われるので、ユーザの所望する検索結果を提供することができるという効果がある。
【００３０】
請求項４記載の検索装置によれば、請求項２又は３記載の検索装置の奏する効果に加えて、文字列を構成する構成文字の各々に対して１の座標を予め対応付けた第２文字マップを用いて、文字列が濃淡画像の画像データに変換される。即ち、画像化手段によって、文字列を構成する構成文字毎に、第２文字マップに対応する座標に該文字列における出現位置に応じた値を付与することによって各座標に濃淡を発生させ、該文字列が濃淡画像の画像データに変換される。
【００３１】
そのような画像化手段によって、入力文字列と検索対象文字列抽出手段により抽出された１の検索対象文字列と入力文字列とに基づく画像データがそれぞれ得られ、それらの画像データが、画像類似度取得手段によって比較されて、該１の検索対象文字列に対する該入力文字列の類似性を判定可能な値が取得される。
【００３２】
そして、類似性判定手段では、位置類似度取得手段及び画像類似度取得手段のそれぞれから得られた類似性を判定可能な値を組み合わせることによって、該入力文字列と該検索対象文字列との類似性が判定される。
【００３３】
よって、検索文字列（入力文字列）及び検索文字列のそれぞれに基づく画像を用いてそれらの文字列の類似性を判定するので、入力文字列と検索対象文字列との間において一部に局部的な相違があったとしても、そのような文字列間の局部的な相違が文字列間の類似性に与える影響は相対的に小さいものとなる。その結果として、従来であれば予測の範囲外とされて別の文字列として認識されるようなタイプミスを有する検索文字列に対しても、ユーザの意図通りの検索が行われるので、ユーザの所望する検索結果を提供することができるという効果がある。
【００３４】
従って、位置類似度取得手段により得られる類似性判定可能な値に、画像類似度取得手段により得られる類似性判定可能な値を組み合わせることによって、それぞれの値が有する検索に対する長所が組み合わされ、その結果、ユーザの所望する検索結果をより効果的に提供し得るという効果がある。
【００３５】
なお、請求項５における「入力文字列に基づく画像データ」は、入力文字列の全てに対して得られた画像データだけでなく、入力文字列の一部に対して得られた画像データを含む。同様に、「１の検索対象文字列に基づく画像データ」もまた、１の検索対象文字列の全てに対して得られた画像データだけでなく、その検索対象文字列の一部に対して得られた画像データを含む。
【００３６】
請求項５記載の検索装置によれば、請求項４記載の検索装置の奏する効果に加えて、位置類似度取得手段により取得された類似性を判定可能な値と、画像類似度取得手段により取得された類似性を判定可能な値とを組み合わせる場合に、入力文字列の構成文字数又は検索対象文字列の構成文字数のうちの少ない方の構成文字数が所定数以下又は所定数未満であれば、位置類似度取得手段により取得された類似性を判定可能な値に対する重み付け係数を、画像類似度取得手段により取得された類似性を判定可能な値に対する重み付け係数より大きくして互いの値が組み合わされる。
【００３７】
検索の際に比較に用いられる文字列の構成文字数が少ない場合には、画像類似度取得手段により取得された類似性を判定可能な値より、位置類似度取得手段により取得された類似性を判定可能な値の方がより類似性判定の精度が高い。よって、位置類似度取得手段により取得された類似性に対する重み付け係数をより大きくすることによって、検索精度が向上し、ユーザの所望する検索結果をより効果的に得ることなできるという効果がある。
【００３８】
請求項６記載の検索装置によれば、請求項４記載の検索装置の奏する効果に加えて、位置類似度取得手段により取得された類似性を判定可能な値と、画像類似度取得手段により取得された類似性を判定可能な値とを組み合わせる場合に、入力文字列の構成文字数又は前記検索対象文字列の構成文字数のうちの少ない方の構成文字数が所定数を越える又は所定数以上であれば、画像類似度取得手段により取得された類似性を判定可能な値に対する重み係数を、位置類似度取得手段により取得された類似性を判定可能な値に対する重み係数より大きくして互いの値が組み合わされる。
【００３９】
検索の際に比較に用いられる文字列の構成文字数が多い場合には、位置類似度取得手段により取得された類似性を判定可能な値より、画像類似度取得手段により取得された類似性を判定可能な値の方がより類似性判定の精度が高い。よって、画像類似度取得手段により取得された類似性に対する重み付け係数をより大きくすることによって、検索精度が向上し、ユーザの所望する検索結果をより効果的に提供し得るという効果がある。
【００４０】
請求項７記載の検索装置によれば、請求項１から６のいずれかに記載の検索装置の奏する効果に加えて、メモリに記憶される複数の文字列の中から、入力文字列の構成文字数に応じた範囲内の構成文字数から構成されるものが、検索対象文字抽出手段によって、検索対象文字列として抽出されるので、入力文字列とは異なる文字列である可能性が著しく高い文字列を検索対象外とすることができる。その結果として、処理効率を向上させることができるという効果がある。
【００４１】
請求項８記載の検索装置によれば、請求項１から７のいずれかに記載の検索装置の奏する効果に加えて、入力文字列を構成する構成文字数と検索対象文字列抽出手段により抽出された検索対象文字列を構成する構成文字数とが異なる場合に、小文字列抽出手段によって、構成文字数の多い方の文字列からその文字列の文字配列順に従って構成文字数の少ない方の文字列に応じた数の構成文字が小文字列として抽出される。
【００４２】
そして、画像類似度取得手段及び／又は位置類似度取得手段による類似性を判定可能な値は、該小文字列抽出手段によって構成文字数の多い方の文字列から抽出された複数の異なる小文字列のそれぞれと構成文字数の少ない方の文字列との類似性の比較に基づいて得られる値である。
【００４３】
よって、構成文字数の多い方の文字列の中の一部分である小文字列と構成文字数の少ない方の文字列との類似性を比較した結果として、入力文字列と検索対象文字列との類似性を判定するので、部分一致（前方一致や後方一致など）の検索を行うことができるという効果がある。
【００４４】
また、構成文字数の多い方の文字列の中から小文字列が小文字列抽出手段によって抽出されるので、入力文字列の構成文字数の方が検索対象文字列の構成文字数よりも多い場合であっても、入力文字列の中から抽出された小文字列に対して、検索対象文字列との部分一致（前方一致や後方一致など）の検索が行われる。よって、例えば、正式名称として入力された入力文字列に対して、検索対象文字列がその省略形態の名称を示す文字列であった場合にも、ユーザの所望する検索結果を提供することができるという効果がある。
【発明を実施するための最良の形態】
【００４５】
以下、本発明の好ましい実施例について、添付図面を参照して説明する。まず、図１〜図３を参照して、本発明の検索装置であるホストコンピュータ１の構成について説明する。図１は、ホストコンピュータ１の構成を示すブロック図であり、図２は、本実施例における文字マップ１２ａの模式図であり、図３は、コンテンツデータベース１４ａ（以下、「コンテンツＤＢ１４ａ」と称する）の構造の模式図である。
【００４６】
ホストコンピュータ１は、ユーザのパーソナルコンピュータ６０（以下、「ＰＣ６０」と称する）と通信回線７０を介して通信可能に接続され、ユーザによるダウンロード要求に応じて楽曲の曲データをユーザに提供すると共に、ユーザから検索要求があった場合にその検索結果をユーザに返すものである。
【００４７】
図１に示すように、ホストコンピュータ１は、ホストコンピュータ１全体の動作を制御するＣＰＵ１１と、そのＣＰＵ１１により実行される各種の制御プログラムや固定値データを記憶するＲＯＭ１２と、ＣＰＵ１１により実行される各種処理に必要なデータやプログラム等を一時的に記憶するためのメモリであるＲＡＭ１３と、書き換え可能な大容量の記憶装置であり、電源断後もデータを保持する不揮発性のメモリであるハードディスクなどの記憶部１４と、液晶表示装置（ＬＣＤ）などの表示部１５と、英数字データや仮名データを入力可能なテンキー又はキーボードや、操作ボタンなどの入力部１６と、通信回線７０と接続するためのモデム１８とを主に備えており、これらの構成が互いにバスライン２０によって接続されている。
【００４８】
ＲＯＭ１２は、文字マップ１２ａを備えている。この文字マップ１２ａは、文字列を構成する構成文字の１つ１つに対し、１の座標を割り当てた仮想的な座標である。本実施例の文字マップ１２ａは、図２に示すように、（ｘ，ｙ）＝（０，０）から（ｘ，ｙ）＝（１０，４）までの１０×４のマトリックスの各格子点に、ＰＣ６０のキーボード６０ａ等の一般的な文字入力用キーボードの配列に応じた数字、アルファベット文字、記号が割り当てられたものである。
【００４９】
具体的には、ｙ＝４の行には、ｘ＝０〜９の列にそれぞれ「１」〜「０」の数字が割り当てられている。また、ｙ＝３の行におけるｘ＝０〜９の列、ｙ＝２の行におけるｘ＝０〜８の列、及び、ｙ＝１の行におけるｘ＝０〜６の列には、それぞれ、アルファベット文字が割り当てられており、（ｘ、ｙ）＝（１０，４），（１０，３），（９，２），（１０，２），（７，１），（８，１），（９，１），（１０，１）には各種記号が割り当てられている。そして、（ｘ、ｙ）＝（４，０）には、スペース（「ＳＰ」）が対応付けられている。
【００５０】
ＲＡＭ１３は、検索結果メモリ１３ａと、相関関数メモリ１３ｂと、位置相関点数メモリ１３ｃと、位置相関度メモリ１３ｄとを備えている。なお、これらのメモリ１３ａ〜１３ｄは、いずれも、ホストコンピュータ１の電源投入時に初期化される。
【００５１】
検索結果メモリ１３ａは、図４を参照して後述する検索処理の結果として、ユーザが検索を意図して入力した入力文字列（以下、「検索文字列」と称する）とその検索文字列の検索対象である文字列（以下、「検索対象文字列」と称する）との類似性が所定のレベル以上であると判定された場合に、その検索対象文字列を記憶（蓄積）するメモリである。
【００５２】
相関係数メモリ１３ｂは、図５を参照して後述する画像類似度取得処理において、テンプレート文字列に基づいて作成された画像データと比較文字列に応じて作成された画像データとに対して得られた正規化相関係数の値を記憶（蓄積）するメモリである。
【００５３】
なお、「テンプレート文字列」とは、文字列の一致又は類似を検索する際のテンプレートとして用いる文字列であり、検索文字列に含まれる構成文字数と検索対象文字列に含まれる構成文字数とが異なる場合には、構成文字数の少ない方の文字列がテンプレート文字列とされる。ここで、テンプレート文字列とされなかった方の検索文字列又は検索対象文字列を以下では「被テンプレート文字列」と称する。
【００５４】
また、「比較文字列」とは、被テンプレート文字列から、その文字順列に従って、テンプレート文字列に応じた数の構成文字数を抽出して得られた文字列である。本実施例では、比較文字列の構成文字数は、テンプレート文字数と等しいものとする。
【００５５】
位置相関点数メモリ１３ｃは、図６を参照して後述する位置相関点数化処理において得られた、テンプレート文字列と比較文字列とにおける先頭からの出現位置の等しい構成文字間の文字マップ１２ａ上における位置の相違を示す尺度である位置相関点数を記憶するメモリである。
【００５６】
位置相関度メモリ１３ｄは、テンプレート文字列と比較文字列との類似度を示す値であり、位置相関点数に基づいて得られる位置相関度Ｐｄを記憶するメモリである。
【００５７】
記憶部１４は、コンテンツＤＢ１４ａと、コンテンツＤＢ１４ａに記憶された各コンテンツに対応する曲データが、コンテンツＩＤ１４ａ１に対応付けて記憶されている曲データメモリ１４ｂとを備えている。
【００５８】
コンテンツＤＢ１４ａは、曲データメモリ１４ｃに記憶されている曲データ（コンテンツ）の情報を記憶するデータベースである。図２（ａ）に示すように、コンテンツＤＢ１４ａには、１のコンテンツを表す１のコンテンツＩＤ１４ａ１に対し、そのコンテンツ情報１４ａ２として、コンテンツに対応する各種情報（曲名や歌手名など）が記憶されている。
【００５９】
ここで、ユーザが、コンテンツＤＢ１４ａの中から所望のコンテンツがあるか否かを検索する場合には、ユーザにより指定された検索条件に応じて対応するコンテンツ情報１４ａ２が参照される。
【００６０】
例えば、ユーザが検索条件として曲名を指定した場合には（曲名検索）、ユーザにより入力された検索文字列に対して、各コンテンツＩＤ１４ａ１のコンテンツ情報１４ａ２における曲名の情報が参照される。また、ユーザが検索条件として歌手名を指定した場合には（歌手名検索）、ユーザにより入力された検索文字列に対して、各コンテンツＩＤ１４ａ１のコンテンツ情報１４ａ２における歌手名の情報が参照される。
【００６１】
次に、図４〜図６のフローチャートを参照して、上記のように構成された本発明の検索装置であるホストコンピュータ１で実行される検索処理について説明する。図４は、本実施例のホストコンピュータ１で実行される検索処理を示すフローチャートであり、図５は、画像類似度取得処理を示すフローチャートであり、図６は、位置相関度取得処理を示すフローチャートである。なお、図４〜図６のフローチャートで示す処理を実行するプログラムは、ホストコンピュータ１のＲＯＭ１２に制御プログラムの一部として記憶されている。
【００６２】
図４に示す入力処理は、ユーザがキーボード６０ａなどを操作することによって作成された検索文字列がユーザにより指定された検索条件の情報と共にホストコンピュータ１に入力された場合に起動する処理である。
【００６３】
図４に示すように、この検索処理では、まず、ユーザにより指定された検索条件が曲名検索であるかを確認し（Ｓ４０１）、曲名検索であれば（Ｓ４０１：Ｙｅｓ）、コンテンツＤＢ１４ａに記憶されているコンテンツ情報１４ａ２の中から１の曲名情報を検索対象文字列として参照し（Ｓ４０２）、検索文字列に含まれる構成文字数と検索対象文字列に含まれる構成文字数との数が同じであるかを確認する（Ｓ４０３）。
【００６４】
Ｓ４０３の処理により確認した結果、検索文字列に含まれる構成文字数と検索対象文字列に含まれる構成文字数との数が同じであれば（Ｓ４０３：Ｙｅｓ）、検索文字列をテンプレート文字列とする（Ｓ４０５）。
【００６５】
一方で、Ｓ４０３の処理により確認した結果、検索文字列に含まれる構成文字数と検索対象文字列に含まれる構成文字数との数が異なる場合には（Ｓ４０３：Ｎｏ）、検索対象文字列に含まれる文字数が検索文字列に含まれる構成文字数より多いかを確認する（Ｓ４０４）。
【００６６】
Ｓ４０４の処理により確認した結果、検索対象文字列に含まれる文字数が検索文字列に含まれる構成文字数より多い場合には（Ｓ４０４：Ｙｅｓ）、Ｓ４０５の処理へ移行し、検索文字列をテンプレート文字列とする。
【００６７】
一方で、Ｓ４０４の処理により確認した結果、検索対象文字列に含まれる文字数が検索文字列に含まれる構成文字数より少ない場合には（Ｓ４０４：Ｎｏ）、検索対象文字列をテンプレート文字列とする（Ｓ４１４）。
【００６８】
Ｓ４０５又はＳ４１４の処理後、文字列を文字マップ１２ａを用いて濃淡画像の画像データに変換することによって、検索文字列と検索対象文字列との類似度を示す値（画像類似度Ｐｎ）を得る処理である画像類似度取得処理を実行する（Ｓ４０６）。
【００６９】
この画像類似度取得処理（Ｓ４０６）によって得られる画像類似度Ｐｎは、０≦Ｐｎ≦１の範囲を取り得る値であり、検索文字列と検索対象文字列との類似性が全くない場合には０となり、検索文字列と検索対象文字列とが完全一致する場合には１となる値である。なお、この画像類似度取得処理（Ｓ４０６）の具体的処理については図５を参照して後述する。
【００７０】
画像類似度取得処理（Ｓ４０６）の実行後、位置相関点数に基づいて得られる位置相関度Ｐｄを得る処理である位置相関度取得処理を実行する（Ｓ４０７）。
【００７１】
この位置相関度取得処理（Ｓ４０７）によって得られる位置相関度Ｐｄは、０≦Ｐｄ≦１の範囲を取り得る値であり、検索文字列と検索対象文字列との類似性が全くない場合には０となり、検索文字列と検索対象文字列とが完全一致する場合には１となる値である。なお、この位置相関度取得処理（Ｓ４０７）の具体的処理については図６を参照して後述する。
【００７２】
位置相関度取得処理（Ｓ４０７）の実行後、Ｓ４０６及びＳ４０７の処理の結果として得られた画像類似度Ｐｎと位置相関度Ｐｄとから以下の式（１）に従って総合類似度Ｐを算出する（Ｓ４０８）。
【００７３】
【数１】
2006227743.tif 000003
ここで、ｃ１及びｃ２は、それぞれ、画像類似度Ｐｎに対する重み係数及び位置相関度Ｐｄに対する重み係数（０≦ｃ１≦１，０≦ｃ２≦１）であり、本実施例では、ｃ１＝０．６，ｃ２＝０．４とする。
【００７４】
なお、テンプレート文字列に含まれる構成文字数が所定数以下の場合（例えば、５文字以下の場合）には、画像類似度Ｐｎより位置相関度Ｐｄの方がより類似性判定の精度が高くなるので、重み係数ｃ２による重みを大きくすることが好ましい。
【００７５】
また、テンプレート文字列に含まれる構成文字数が所定数を越える場合（例えば、５文字を越える場合）には、位置相関度Ｐｄより画像類似度Ｐｎの方がより類似性判定の精度が高くなるので、重み係数ｃ１による重みを大きくすることが好ましい。
【００７６】
Ｓ４０８の処理後、得られた総合類似度Ｐの値が所定の閾値以上であるかを確認し（Ｓ４０９）、所定の閾値以上であれば（Ｓ４０９：Ｙｅｓ）、検索文字列と検索対象文字列との間には類似性があると判定し、参照中の検索対象文字列に対応するコンテンツＩＤ１４ａ１を検索結果メモリ１３ａに記憶し（Ｓ４１０）、Ｓ４１１の処理へ移行する。
【００７７】
一方で、Ｓ４０９において、総合類似度Ｐの値が所定の閾値未満であることが確認された場合には（Ｓ４０９：Ｎｏ）、検索文字列と検索対象文字列との間には類似性がないと判定され、その結果として、Ｓ４１０の処理をスキップし、Ｓ４１１の処理へ移行する。
【００７８】
Ｓ４１１の処理では、コンテンツＤＢ１４ａに記憶されている全ての曲名情報（コンテンツ情報１４ａ２）に対し、検索が行われたかを確認する。このＳ４１１において、全ての曲名情報に対して検索が行われたことが確認された場合には（Ｓ４１１：Ｙｅｓ）、検索結果メモリ１３ａに記憶されているコンテンツＩＤ１４ａ１に基づいて、所定の情報（例えば、コンテンツＩＤ１４ａ１に基づいて参照可能な曲名情報や歌手名情報などのコンテンツ情報１４ａ２）をＰＣ６０へ出力し（Ｓ４１２）、検索結果メモリ１３ａをクリアし（Ｓ４１３）、この検索処理を終了する。
【００７９】
Ｓ４１２の処理の結果として、ユーザは、自身が検索を意図して入力した検索文字列に対する検索結果を知ることができる。ここで、詳細は後述するが、画像類似度取得処理（Ｓ４０６）によって得られる画像類似度Ｐｎは、検索文字列と検索対象文字列との間において一部に局部的な相違があったとしても、そのような文字列間の局部的な相違が文字列間の類似性に与える影響が相対的に小さくされた値である。また、位置相関度取得処理（Ｓ４０７）によって得られる位置相関度Ｐｄは、ユーザが検索を意図して入力する検索文字列におけるタイプミスによる影響を考慮した値である。
【００８０】
よって、画像類似度Ｐｎと位置相関度Ｐｄとを組み合わせて、検索文字列と検索対象文字列との類似性を判定することによって、従来であれば予測の範囲外とされて別の文字列として認識されるようなタイプミスを有する検索文字列に対しても、ユーザの所望する検索結果を有効に得ることができる。
【００８１】
一方で、Ｓ４１１の処理により確認した結果、未だ全ての曲名情報に対して検索が行われていない場合には（Ｓ４１１：Ｎｏ）、Ｓ４０１の処理へ移行し、Ｓ４０１からの処理を繰り返す。
【００８２】
また、Ｓ４０１の処理により確認した結果、ユーザにより指定された検索条件が曲名情報でなければ（Ｓ４０１：Ｎｏ）、検索条件に応じた検索処理などの各処理を行い（Ｓ４１５）、この検索処理を終了する。
【００８３】
次に、図５のフローチャートを参照して、上述した画像類似度取得処理（Ｓ４０６）について説明する。この画像類似度取得処理（Ｓ４０６）では、まず、文字マップ１２ａを用いて、テンプレート文字列に基づく画像データを作成する（Ｓ５０１）。
【００８４】
具体的には、Ｓ５０１の処理では、テンプレート文字列を構成する各構成文字毎に、その出現位置に応じた値を、文字マップ１２ａにおける対応する座標（図２参照）に付与し、その結果として、各座標が付与された値に応じた濃淡を生じる濃淡画像の画像データを作成する。
【００８５】
例えば、文字列における出現位置に応じた値を、文字列の先頭から順に１，２，３…であるとする。よって、テンプレート文字列が「karaokesystem」という文字列である場合には、文字列における出現位置に応じた値は、先頭文字である「ｋ」に対しては「１」、２番目の文字である「ａ」に対しては「２」、３番目の文字である「ｒ」に対しては「３」、…、６番目の文字である「ｋ」に対しては「６」、…、最後尾（１３番目）の文字である「ｍ」に対しては「１３」となる。
【００８６】
この場合、Ｓ５０１において、文字マップ１２ａ（図２参照）における「ｋ」に対応する座標（７，２）には、「ｋ」が先頭と６番目に出現することから、１＋６＝「７」が付与される。また、「ａ」に対応する座標（０，２）には、「ａ」が２番目と４番目に出現することから、２＋４＝「６」が付与される。また、「ｒ」に対応する座標（３，３）には、「ｒ」が３番目のみに出現することから「３」が付与される。以下同様に、座標（８，３）には「５」、座標（２，３）には「１９」、座標（１，２）には「１８」、座標（５，３）には「３」、座標（４，３）には「１１」、座標（６，１）には「１３」がそれぞれ付与される。
【００８７】
そして、上記のように文字マップ１２ａ上の座標に、文字列における出現位置に応じた値を付与した結果として、付与された値に応じた濃淡を各座標に発生させて濃淡画像の画像データが作成される。
【００８８】
Ｓ５０１の処理後、被テンプレート文字列の先頭文字を比較文字列の先頭文字として指定し（Ｓ５０２）、被テンプレート文字列における比較文字列の先頭文字として指定された位置からテンプレート文字列の構成文字数分を比較文字列として抽出する（Ｓ５０３）。
【００８９】
Ｓ５０３の処理後、文字マップ１２ａを用いて、比較文字列に基づく画像データをＳ５０１と同様に作成し（Ｓ５０４）、Ｓ５０４により作成された画像データとＳ５０１により作成された画像データとに対し、画像処理におけるテンプレートマッチングに対して一般的に用いられる以下の式（２）を用いて正規化相関係数Ｒを求める（Ｓ５０５）。
【００９０】
【数２】
2006227743.tif 000004
ここで、Ｔｉｊは、テンプレート文字列に基づいて作成された画像データの各座標（ｉ，ｊ）における値であり、Ｗｉｊは、比較文字列に基づいて作成された画像データの各座標（ｉ，ｊ）における値であり、Ｔａｖｅ及びＷａｖｅは、それぞれの画像データの全体の平均値である。
【００９１】
Ｓ５０５の処理の結果として、−１≦Ｒ≦１の範囲の正規化相関係数Ｒの値が得られる。ここで、正規化相関係数Ｒの値が１の場合は、両濃淡画像のパターンが完全に一致していることを示す。よって、正規化相関係数Ｒの値が１に近いほど、テンプレート文字列に基づいて作成された濃淡画像のパターンと比較文字列に基づいて作成された濃淡画像のパターンとの類似性が高く、テンプレート文字列と比較文字列との類似性が高いことを示す。一方で、正規化相関係数Ｒの値が１から逸脱するに従って、両濃淡画像のパターンの類似性が低いことを示す。
【００９２】
文字列が画像化されることによって、検索文字列と検索対象文字列との間において一部に局部的な相違があったとしても、そのような文字列間の局部的な相違が正規化相関係数Ｒに与える影響が相対的に小さくなる。よって、Ｓ５０５の処理により得られた相関係数Ｒは、検索文字列と検索対象文字列との類似性を判定する上で有効なパラメータである。
【００９３】
Ｓ５０５の処理後、得られた正規化相関係数Ｒの値を、式（Ｒ＋１）／２を用いて０≦Ｒ≦１の範囲の値に補正し、相関係数メモリ１３ｂに記憶（蓄積）する（Ｓ５０６）。
【００９４】
Ｓ５０６の処理後、比較文字列の最後尾と被テンプレート文字列の最後尾とを比較し、比較文字列の最後尾が被テンプレート文字列の最後尾に一致するかを確認する（Ｓ５０７）。
【００９５】
Ｓ５０７の処理により確認した結果、比較文字列の最後尾が被テンプレート文字列の最後尾に一致していれば（Ｓ５０７：Ｙｅｓ）、相関係数メモリ１３ｂに蓄積されている値（補正された正規化相関係数Ｒ）の中で最も１に近い値を画像類似度Ｐｎとして取得し（Ｓ５０８）、相関係数メモリ１３ｂをクリアして（Ｓ５０９）、この画像類似度取得処理を終了する。
【００９６】
一方で、Ｓ５０７の処理により確認した結果、比較文字列の最後尾が被テンプレート文字列の最後尾に一致していなければ（Ｓ５０７：Ｎｏ）、比較文字列の先頭を、被テンプレート文字列の後方側に１字分移動した位置に指定し（Ｓ５１０）、Ｓ５０３の処理へ移行し、Ｓ５０７において比較文字列の最後尾が被テンプレート文字列の最後尾に一致することが確認されるまで、Ｓ５０３〜Ｓ５０７の処理を繰り返す。
【００９７】
即ち、Ｓ５０３〜Ｓ５０７及びＳ５１０の処理により、被テンプレート文字列からその順列に従うテンプレート文字列の構成文字数分の比較文字列が（被テンプレート文字列の構成文字数−テンプレート文字列の構成文字数＋１）種類抽出されて、それぞれの比較文字列とテンプレート文字列との正規化相関関数が取得される。
【００９８】
よって、Ｓ５０８の処理により、被テンプレート文字列から抽出された比較文字列に基づく画像の中で、テンプレート文字列に基づく画像に最も類似性を有するものに対して得られた補正された相関係数Ｒが画像類似度Ｐｎとして取得されるので、本実施例の方法によれば、検索文字列と検索対象文字列とが完全一致するものを検索できるだけでなく、部分一致（前方一致や後方一致など）の検索を行うことも可能となる。
【００９９】
次に、図６のフローチャートを参照して、上述した位置相関度取得処理（Ｓ４０７）について説明する。この位置相関度取得処理（Ｓ４０７）では、まず、被テンプレート文字列の先頭文字を比較文字列の先頭文字として指定し（Ｓ６０１）、被テンプレート文字列における比較文字列の先頭文字として指定された位置からテンプレート文字列の構成文字数分を比較文字列として抽出する（Ｓ６０２）。
【０１００】
Ｓ６０２の処理後、テンプレート文字列及び比較文字列の先頭文字を抽出し（Ｓ６０３）、その抽出された２文字間の文字マップ１２ａ上における距離に基づいて、以下の式（３）を用いて位置相関点数Ｄを求める（Ｓ６０４）。
【０１０１】
【数３】
2006227743.tif 000005
ここで、ｄは、抽出された２文字間の文字マップ１２ａ上における距離であり、ｄｍａｘは、文字マップ上における最長距離である。また、εは、位置相関点数Ｄの値が距離ｄの増加に伴って０へ収束するまでの速さを調整するための所定の定数である。
【０１０２】
この位置相関点数Ｄは、距離ｄが０である場合、即ち、抽出された２文字が一致する場合には１となり、距離ｄが大きくなるに従って０へ収束する関数である。ここで、位置相関点数Ｄを得るための距離ｄは、本実施例においては、一般的な文字入力用キーボードにおける文字の配列に応じて文字マップ１２ａ上に配置された文字の座標に応じて決定される。よって、本発明の検索装置であるホストコンピュータ１によれば、検索文字列と検索対象文字列とが完全一致しない場合であっても、位置相関点数Ｄの値の１からの逸脱の程度を参照することによって、その相違が、ユーザの意図に基づく検索文字列と全く違うものであることに起因するものであるのか、ユーザによる検索文字列の入力時のキーのタイプミスに起因するものであるのかを判定することが可能となるのである。
【０１０３】
なお、位置相関点数Ｄを得るための式としては、上記の式（３）のように、距離が所定の閾値までは距離の増大に伴って緩やかに変化し、所定の閾値を越えると距離の増大に伴って急激に値が変化するような関数を用いることが好ましい。
【０１０４】
次いで、Ｓ６０４の処理によって求められた位置相関点数Ｄを位置相関点数メモリ１３ｃに記憶（蓄積）し（Ｓ６０５）、Ｓ６０３又はＳ６１２の処理によって抽出された文字がテンプレート文字列及び比較文字列の最後尾の文字であるかを確認する（Ｓ６０６）。
【０１０５】
Ｓ６０６の処理により確認した結果、抽出された文字がテンプレート文字列及び比較文字列の最後尾の文字であれば（Ｓ６０６：Ｙｅｓ）、Ｓ６０７の処理へ移行する。一方で、最後尾の文字でなければ（Ｓ６０６：Ｎｏ）、テンプレート文字列及び比較文字列における１字後方の文字を抽出し（Ｓ６１２）、Ｓ６０４の処理へ移行し、Ｓ６０６の処理により最後尾の文字であることが確認されるまで、Ｓ６０４〜Ｓ６０６の処理を繰り返す。
【０１０６】
即ち、Ｓ６０４〜Ｓ６０６及びＳ６１２の処理によって、比較文字列とテンプレート文字列とにおける出現位置の等しい構成文字の文字マップ１２ａ上における位置の相違の程度がそれぞれ位置相関点数Ｄによって数値化される。
【０１０７】
Ｓ６０７では、位置相関点数メモリ１３ｃに蓄積された出現位置毎の位置相関点数Ｄをテンプレート文字列の構成文字数で割って平均値とし、その値を位置相関度メモリ１３ｄに記憶（蓄積）する。Ｓ６０７の処理後、位置相関点数メモリ１３ｃをクリアし（Ｓ６０８）、Ｓ６０９の処理へ移行する。
【０１０８】
Ｓ６０９では、比較文字列の最後尾と被テンプレート文字列の最後尾とを比較し、比較文字列の最後尾が被テンプレート文字列の最後尾に一致するかを確認する。Ｓ６０９の処理により確認した結果、比較文字列の最後尾が被テンプレート文字列の最後尾に一致すれば（Ｓ６０９：Ｙｅｓ）、位置相関度メモリ１３ｄに蓄積されている値（位置相関点数Ｄのテンプレート文字列の構成文字列あたりの平均値）の中で最も１に近い値を位置相関度Ｐｄとして取得し（Ｓ６１０）、位置相関度メモリ１３ｄをクリアして（Ｓ６１１）、この位置相関度取得処理を終了する。
【０１０９】
一方で、Ｓ６０９の処理により確認した結果、比較文字列の最後尾が被テンプレート文字列の最後尾に一致しなければ（Ｓ６０９：Ｎｏ）、比較文字列の先頭を、被テンプレート文字列の後方側に１字分移動した位置に指定し（Ｓ６１３）、Ｓ６０２の処理へ移行し、Ｓ６１３において比較文字列の最後尾が被テンプレート文字列の最後尾に一致することが確認されるまで、Ｓ６０２〜Ｓ６０９の処理を繰り返す。
【０１１０】
即ち、Ｓ６０２〜Ｓ６０９及びＳ６１３の処理により、被テンプレート文字列からその順列に従うテンプレート文字列の構成文字数分の比較文字列が（被テンプレート文字列の構成文字数−テンプレート文字列の構成文字数＋１）種類抽出されて、各比較文字列に対し、位置相関点数Ｄの平均値が取得される。
【０１１１】
よって、Ｓ６１０の処理により、被テンプレート文字列から抽出された比較文字列の中で、テンプレート文字列に最も類似性を有するものに対して得られた位置相関点数Ｄの平均値が位置相関度Ｐｄとして取得されるので、本実施例の方法によれば、検索文字列と検索対象文字列とが完全一致するものを検索できるだけでなく、部分一致（前方一致や後方一致など）の検索を行うことも可能となる。
【０１１２】
また、この位置相関度取得処理（Ｓ４０７）、及び、先に説明した画像類似度取得処理（Ｓ４０６）のいずれにおいても、検索文字列の構成文字数と検索対象文字列の構成文字数とが異なる場合には、構成文字数の少ない方の文字列がテンプレート文字列とされる（図４のＳ４０４，Ｓ４０５，Ｓ４１４参照）。そのため、検索対象文字列の構成文字数より検索文字列の構成文字数の方が多い場合には、検索対象文字列がテンプレート文字列とされ、テンプレート文字列に応じた構成文字数からなる比較文字列が検索文字列から抽出される。よって、例えば、ユーザが入力した検索文字列が正式名称を示す文字列（例えば、「karaokesystem」）であるのに対して、コンテンツＤＢ１４ａに記憶されている情報（コンテンツ情報１４ａ２）が省略形態の名称（例えば、「karaoke」）を示す文字列であった場合にも、検索対象文字列に対する検索文字列の部分一致（前方一致や後方一致など）が検索され、その結果として、ユーザの所望する検索結果が提供されるのである。
【０１１３】
以上説明したように、本発明の検索装置であるホストコンピュータ１によれば、検索文字列（入力文字列）及び検索文字列のそれぞれに基づく画像に基づいて得られる類似性を判定可能な値を利用して、それらの文字列の類似性が判定される。
【０１１４】
そのように文字列が画像化されることによって、検索文字列と検索対象文字列との間において一部に局部的な相違があったとしても、そのような文字列間の局部的な相違が文字列間の類似性に与える影響は相対的に小さくなる。その結果として、従来であれば予測の範囲外とされて別の文字列として認識されるようなタイプミスを有する検索文字列に対しても、ユーザの意図通りの検索が行われるので、ユーザの所望する検索結果を提供できるのである。
【０１１５】
また、本発明の検索装置であるホストコンピュータ１によれば、文字列を作成する装置における各構成文字の配列（本実施例では、一般的な文字入力用キーボードにおける文字の配列）に応じて１の座標を予め対応付けた文字マップ１２ａ上における、検索文字列及び検索対象文字列において互いに対応する出現位置の構成文字間の距離に基づいて得られる類似性を判定可能な値を利用して、それらの文字列の類似性が判定される。
【０１１６】
よって、ユーザが検索を意図して入力する検索文字列におけるタイプミスによる影響を考慮した値を利用して、類似性が判断されるので、従来であれば予測の範囲外とされて別の文字列として認識されるようなタイプミスを有する検索文字列に対しても、ユーザの意図通りの検索が行われるので、ユーザの所望する検索結果を提供できるのである。
【０１１７】
さらに、本発明の検索装置であるホストコンピュータ１によれば、上記のような画像化に基づいて得られる類似性を判定可能な値と、上記のような文字列を作成する装置における各構成文字の配列を考慮した文字マップ１２ａを用いることによって得られる検索文字列におけるタイプミスを考慮した値とを組み合わせて、検索文字列と検索対象文字列との類似性が判定される。よって、それぞれの値が有する検索に対する長所が組み合わされるので、ユーザの所望する検索結果をより効果的に提供できるのである。
【０１１８】
なお、上記実施例では、曲名検索の場合に、入力された検索文字列に対してコンテンツＤＢ１４ａに記憶されている全ての曲名情報（コンテンツ情報１４ａ２）を検索対象文字列として検索するように構成されているが、入力された検索文字列の構成文字数に応じて、検索対象文字列とする文字列の構成文字数の範囲を限定するように構成してもよい。
【０１１９】
具体的には、検索処理（図４参照）におけるＳ４０２の処理の後に、参照された検索対象文字列の構成文字数が、検索文字列の構成文字数に応じた所定範囲内の数であるかを確認し（Ｓ７０１）、参照された検索対象文字列の構成文字数が所定範囲内の数であれば（Ｓ７０１：Ｙｅｓ）、Ｓ４０３の処理へ移行し、一方で、参照された検索対象文字列の構成文字数が所定範囲内の数でなければ（Ｓ７０１：Ｎｏ）、Ｓ４０２の処理へ移行し、次の検索対象文字列をコンテンツＤＢ１４ａの中から参照する。
【０１２０】
あるいは、Ｓ４０２の処理において、検索文字列の構成文字数に応じた所定範囲内の数の構成文字から構成される文字列を検索対象文字列として参照するように構成してもよい。
【０１２１】
このように、入力された検索文字列の構成文字数に応じて、検索対象文字列とする文字列の構成文字数の範囲を限定することによって、検索文字列の構成文字数と大幅に違う構成文字数から構成され、検索文字列とは異なる文字列である可能性が著しく高い文字列を検索対象外とすることができるので、その結果として、処理効率を向上させることができる。
【０１２２】
なお、請求項１又は２記載の文字列抽出手段としては、Ｓ４０２の処理が該当する。また、請求項１又は３記載の画像化手段としては、Ｓ５０１，Ｓ５０４の処理が該当する。また、請求項１又は３記載の画像類似度取得手段としては、Ｓ４０６の処理が該当する。また、請求項１又は２記載の類似性判定手段としては、Ｓ４０９の処理が該当する。また、請求項２記載の位置類似度取得手段としては、Ｓ４０７の処理が該当する。また、請求項８記載の小文字列抽出手段としては、Ｓ５０３及びＳ６０２の処理が該当する。
【０１２３】
以上、実施例に基づき本発明を説明したが、本発明は上述した実施例に何ら限定されるものではなく、本発明の趣旨を逸脱しない範囲内で種々の改良変更が可能であることは容易に推察できるものである。
【０１２４】
例えば、上記実施例では、本発明の検索装置を説明するために、着信メロディ配信システムを例示したが、カラオケシステムにおける検索装置としても当然適用可能である。
【０１２５】
また、上記実施例では、コンテンツＤＢ１４ａに記憶されている複数の曲名情報の中から検索対象文字列として１の曲名情報を抽出し、各検索対象文字列毎に検索文字列との類似性を判定する、所謂データベース検索について例示するものであった。本発明の検索装置はこれに限定されることなく、例えば、ＲＡＭ１３に一時的に記憶された複数の文字列から構成されるテキストに対して検索を行う所謂テキスト検索に対しても当然適用可能である。
【０１２６】
なお、テキスト検索の場合には、例えば、図４の検索処理におけるＳ４０２の処理において、テキストから、その先頭文字から検索文字列の構成文字数に応じた数の文字を検索対象文字列として参照するように構成すればよい。そして、Ｓ４１１の処理において、テキストの最後尾の文字と検索対象文字列の最後尾の文字とが一致するまで、検索対象文字列とする文字列の先頭文字を順次テキストの後方へ移動させて、参照される各検索対象文字列と検索文字列との類似度を総合類似度Ｐを用いて判定するように構成すればよい。
【０１２７】
このようなテキスト検索を行うことによって、インターネット上からＲＡＭ１３へ一時的に読み込んだテキストから、ユーザが入力した検索文字列に一致又は類似する文字列を抽出したり、あるいは、記憶部１４に各コンテンツに対応する歌詞データを記憶する歌詞データベースを設けた場合に、各歌詞データに対して上記のようなテキスト検索を行った上で、ユーザが入力した検索文字列に所定レベル以上で類似すると判定された歌詞データを歌詞データベースの中から抽出し、そのコンテンツ情報（コンテンツ情報１４ｂ２）を検索結果として出力することなどができる。また、テキストデータに対するスペルチェックに利用することも可能である。
【０１２８】
また、上記実施例では、画像類似度Ｐｎと位置相関度Ｐｄとの両方を組合わせた総合類似度Ｐに基づいて、検索文字列と検索対象文字列との類似性を判定するように構成した。しかし、画像類似度Ｐｎ及び位置相関度Ｐｄは、それぞれ、単独で類似性を判定可能な値であるので、画像類似度取得処理（Ｓ４０６）又は位置相関度取得処理（Ｓ４０７）のいずれか一方を実行し、それによって得られた画像類似度Ｐｎ又は位置相関度Ｐｄに対して所定の閾値以上であるか否かを判断するように構成しても、上記実施例と同様の効果を得ることができる。
【０１２９】
また、上記実施例では、画像類似度Ｐｎを得るために式（２）を例示したが、画像間の類似性を判定可能な値を得る式又は方法であれば、式（２）以外の式又は方法を用いて画像類似度Ｐｎを得るように構成してもよい。
【０１３０】
また、上記実施例では、位置相関度Ｐｄを得るために式（３）を例示したが、距離に比例して文字列間の類似性を否定するような値が得られる式又は方法であれば、式（３）以外の式又は方法を用いて位置相関度Ｐｄを得るように構成してもよい。
【０１３１】
また、上記実施例では、コンテンツＤＢ１４ａに記憶される各曲名情報（コンテンツ情報１４ａ２）に対してそれぞれ画像類似度取得処理（Ｓ４０６）おいて画像データを作成するように構成したが、各コンテンツ情報１４ａ２に対応する画像データを予めコンテンツＤＢ１４ａに対応付けて記憶させておき、それを必要に応じて読み出すように構成してもよい。
【０１３２】
また、上記実施例では、画像類似度取得処理（Ｓ４０６）及び位置相関度取得処理（Ｓ４０７）において共通の文字マップ１２ａを用いるように構成したが、画像類似度取得処理（Ｓ４０６）と位置相関度取得処理（Ｓ４０７）とにおいて、異なる文字マップを用いるようにしてもよい。
【０１３３】
また、上記実施例における文字マップ１２ａは、一般的な文字入力用キーボードにおける文字の配列に応じて各構成文字に対し座標を割り当てたものとして構成したが、文字マップ上における各文字の配置はこれに限定されるものではない。また、文字の種類も図２に示したものに限定されるものではない。
【０１３４】
また、上記実施例における文字マップ１２ａは、アルファベット文字、数字、記号対応に構成されているが、かな文字対応に構成してもよい。また、ユーザから入力される検索文字列がかな文字であった場合に、アルファベット文字に変換するように構成してもよい。
【０１３５】
また、上記実施例における文字マップ１２ａは、ｘ，ｙの２軸からなる２次元座標であるが、ｘ，ｙ，ｚの３軸からなる３次元座標からなる文字マップを用いるように構成してもよい。
【０１３６】
また、上記実施例における位置相関度取得処理（Ｓ４０７）では、一般的な文字入力用キーボードにおける文字の配列に応じた文字マップ１２ａを用いて位置相関点数Ｄを得ることにより、ユーザによるキーのタイプミスを考慮した検索を行った。文字マップ１２ａにおける構成文字の配列は、そのような一般的な文字入力用キーボードにおける文字の配列に応じたものに限定されず、これに換えて、又はこれと組み合わせて、入力規則に応じた文字マップ（例えば、タイプミスしやすい母音や子音がそれぞれ近傍に配置されるような文字マップ）を作成し、その文字マップを用いて位置相関点数Ｄを得るように構成してもよい。
【０１３７】
また、上記実施例における画像類似度取得処理（Ｓ４０６）において、テンプレート文字列又は比較文字列から画像データを作成する際、文字列における出現位置に応じた値を、各文字列の先頭から順に１，２，３…であるとしたが、このように文字順列に応じて１ずつ増加するような値に限定されるものではない。例えば、全ての出現位置に対して同じ値（例えば、１）を付与するように構成してもよいし、文字列の後方にいくに従って値が減少するようなものであってもよい。あるいは、文字順列に応じて次第に増分が増すような値、例えば、１，２，４，８…としてもよい。このように、文字順列に応じて次第に増分が増すような値を用いた場合には、得られる濃淡画像の特徴が明確となり、類似性の判定精度が向上する。
【０１３８】
また、上記実施例において総合類似度Ｐを得るために用いた重み係数ｃ１及びｃ２の値を、テンプレート文字列が所定の閾値より多いか少ないかに応じて可変的に設定されるように構成してもよい。
【０１３９】
また、上記実施例では、比較文字列の構成文字数を、テンプレート文字数と等しいものとしたが、テンプレート文字数より大きい構成文字数からなる文字列を比較文字列としてもよい。これによって、脱字や重複文字が原因で本来正しくあるべき構成文字数よりも少ない又は多い構成文字数から構成される検索文字列に対しても、本来正しくあるべき文字列に類似する検索対象文字列を検索することが可能となる。
【０１４０】
あるいは、テンプレート文字列に基づいて被テンプレート文字列から比較文字列を抽出することなく、テンプレート文字列と被テンプレート文字列とを直接比較する、即ち、検索文字列と検索対象文字列とを直接比較するように構成してもよい。なお、この場合、検索対象文字列に対応する画像データを文字マップ（上記実施例における文字マップ１２ａに相当するもの）を用いて予め作成し、記憶部１４などに記憶させておくように構成してもよい。検索文字列と検索対象文字列との類似性を比較する際に、検索対象文字列に対して予め作成された画像データを用いることにより、処理効率を向上させることができる。
【０１４１】
また、上記実施例では、検索文字列をユーザによって入力される文字列であるとしたが、音声入力されたものをアルファベット文字列などの文字列に変換して用いるように構成してもよい。
【０１４２】
また、上記実施例では、Ｓ４０９の判断処理において、所定の閾値以上であるかを確認するように構成したが、所定の閾値を越えたかを判断するように構成してもよい。
【０１４３】
また、上記実施例では、検索結果がＰＣ６０へ出力されるように構成したが、例えば、表示部１５に検索結果を表示したり、音声出力などの種々の出力形式にしてもよい。
【０１４４】
また、上記実施例では、通信回線７０を介してホストコンピュータ１に接続されたＰＣ６０から検索文字列が入力されるように構成したが、例えば、ホストコンピュータ１の一部である入力部１６からの検索文字列に対しても同様の検索を行ってもよい。
【図面の簡単な説明】
【０１４５】
【図１】本発明における実施例の検索装置であるホストコンピュータの構成を示すブロック図である。
【図２】文字マップの模式図である。
【図３】コンテンツＤＢの構造の模式図である。
【図４】検索処理を示すフローチャートである。
【図５】画像類似度取得処理を示すフローチャートである。
【図６】位置相関度取得処理を示すフローチャートである。
【符号の説明】
【０１４６】
１                  ホストコンピュータ（検索装置）
１２ａ              文字マップ（第１文字マップ，第２文字マップ）
１４ａ              コンテンツＤＢ（メモリ）
１８                モデム（入力手段）
【図１】
2006227743.tif 000006
【図２】
2006227743.tif 000007
【図３】
2006227743.tif 000008
【図４】
2006227743.tif 000009
【図５】
2006227743.tif 000010
【図６】
2006227743.tif 000011