(57)【特許請求の範囲】
【請求項１】
あらかじめ入力された１つ以上のクエリと関連したログ情報に基づき、前記クエリに対する少なくとも１つの校正候補に関する情報を抽出する校正情報抽出部、
前記の抽出された情報に基づき、前記クエリの前記校正候補への変換に関するパラメータを取得するパラメータ取得部、および
前記の取得されたパラメータに基づき、前記クエリの前記少なくとも１つの校正候補のそれぞれへの変換と関連する確率を計算し、前記の計算された確率に基づき、前記クエリに対する校正結果として前記校正候補のうちから少なくとも１つの校正候補を抽出する校正結果生成部
を備え、
前記パラメータ取得部は、前記クエリに含まれる要素が前記校正候補それぞれに含まれる要素に変換される確率、前記クエリに含まれる要素の各校正候補の要素に対する位置関係、および前記クエリの前記校正候補それぞれへの変換の自然性の程度をパラメータとして取得する、クエリ校正システム。
【請求項２】
前記校正情報抽出部は、前記ログ情報を使用して前記クエリが誤字脱字を含むかを判定し、前記クエリが誤字脱字を含む場合、前記クエリに対する少なくとも１つの校正候補を識別する、請求項１に記載のクエリ校正システム。
【請求項３】
前記ログ情報は、ユーザによって第１クエリが入力された後に第２クエリが入力されるまでの時間、前記クエリに対する検索結果に対するユーザのクリック情報、前記第１クエリと前記第２クエリとの類似度に関する情報、および前記検索結果の属性のうち少なくとも１つを含む、請求項１または２に記載のクエリ校正システム。
【請求項４】
前記検索結果の属性は、前記検索結果が含むコンテンツのカテゴリである、請求項３に記載のクエリ校正システム。
【請求項５】
前記クエリに含まれる要素は、前記クエリに含まれる音節であり、前記校正候補それぞれに含まれる要素は、前記校正候補それぞれに含まれる音節である、請求項１乃至４のうちいずれか一項に記載のクエリ校正システム。
【請求項６】
前記校正結果生成部は、前記校正結果としての前記少なくとも１つの校正候補のうちから校正候補を抽出するにあたり、前記クエリに含まれる要素が配列される順序および前記少なくとも１つの校正候補の対応する要素が配列される順序を同じものと仮定する、請求項１乃至５のうちいずれか一項に記載のクエリ校正システム。
【請求項７】
前記校正結果として抽出された少なくとも１つの校正候補は、ユーザによる前記クエリの入力に対する検索結果に含まれる、請求項１乃至６のうちいずれか一項に記載のクエリ校正システム。
【請求項８】
前記校正候補は複数であり、
前記校正結果生成部は、
前記の複数の校正候補のそれぞれに対して計算された前記確率の分布に基づき、前記の複数の校正候補のうち少なくとも１つの校正候補を、前記クエリに対する校正結果としての校正候補抽出から除外する、請求項１乃至７のうちいずれか一項に記載のクエリ校正システム。
【請求項９】
前記変換と関連する前記確率は数式によって計算され、
前記数式は、
【数７】
0006261669.tif 000014
であり、
ｌは前記校正候補それぞれの長さであり、ｍは前記クエリの長さであり、ｊは前記校正候補それぞれに含まれる要素のインデックスであり、ｉは前記クエリに含まれる要素のインデックスであり、
ＴＲは、前記クエリに含まれるｉ番目の要素が前記校正候補それぞれに含まれるｊ番目の要素に変換される確率を示す関数であり、ＡＬは、前記クエリに含まれる要素の各校正候補の要素に対する位置関係を示す数値を示す関数であり、ＰＬＭは、前記クエリの前記校正候補それぞれへの変換の自然性の程度の確率を示す関数である、請求項１乃至８のうちいずれか一項に記載のクエリ校正システム。
【請求項１０】
前記校正情報抽出部および前記パラメータ取得部のうち少なくとも１つは、分散処理システムとして実現される、請求項１乃至９のうちいずれか一項に記載のクエリ校正システム。
【請求項１１】
前記校正候補に関する情報は、前記クエリおよび各校正候補で構成された誤字脱字−正字ペアを含む、請求項１乃至１０のうちいずれか一項に記載のクエリ校正システム。
【請求項１２】
前記変換と関連する前記確率は、前記クエリが入力されるときに各校正候補が発生する条件付き確率である、請求項１乃至１１のうちいずれか一項に記載のクエリ校正システム。
【請求項１３】
コンピュータが、あらかじめ入力された１つ以上のクエリと関連したログ情報に基づき、前記クエリに対する少なくとも１つの校正候補に関する情報を抽出する段階、
前記コンピュータが、前記の抽出された情報に基づき、前記クエリの前記校正候補への変換に関するパラメータを取得する段階、
前記コンピュータが、前記の取得されたパラメータに基づき、前記クエリの前記少なくとも１つの校正候補のそれぞれへの変換と関連する確率を計算する段階、および
前記コンピュータが、前記の計算された確率に基づき、前記クエリに対する校正結果として前記校正候補のうちから少なくとも１つの校正候補を抽出する段階
を含み、
前記パラメータを取得する段階は、
前記コンピュータが、前記クエリに含まれる要素が前記校正候補それぞれに含まれる要素に変換される確率、前記クエリに含まれる要素の各校正候補の要素に対する位置関係、および前記クエリの前記校正候補それぞれへの変換の自然性の程度をパラメータとして取得する、クエリ校正方法。
【請求項１４】
前記校正候補に関する情報を抽出する段階は、
前記コンピュータが、前記ログ情報を使用して前記クエリが誤字脱字を含むかを判定する段階、および
前記コンピュータが、前記クエリが誤字脱字を含む場合、前記クエリに対する少なくとも１つの校正候補を識別する段階
を含む、請求項１３に記載のクエリ校正方法。
【請求項１５】
前記コンピュータが、前記校正結果として抽出された少なくとも１つの校正候補を、ユーザによる前記クエリの入力に対する検索結果として出力する段階
をさらに含む、請求項１３または１４に記載のクエリ校正方法。
【請求項１６】
前記校正候補は複数であり、
前記少なくとも１つの校正候補を抽出する段階は、
前記コンピュータが、前記の複数の校正候補のそれぞれに対して計算された前記確率の分布に基づき、前記の複数の校正候補のうち少なくとも１つの校正候補を、前記クエリに対する校正結果としての校正候補抽出から除外する段階
を含む、請求項１３乃至１５のうちいずれか一項に記載のクエリ校正方法。
【請求項１７】
前記変換と関連する前記確率は数式によって計算され、
前記数式は、
【数８】
0006261669.tif 000015
であり、
ｌは前記校正候補それぞれの長さであり、ｍは前記クエリの長さであり、ｊは前記校正候補それぞれに含まれる要素のインデックスであり、ｉは前記クエリに含まれる要素のインデックスであり、
ＴＲは、前記クエリに含まれるｉ番目の要素が前記校正候補それぞれに含まれるｊ番目の要素に変換される確率を示す関数であり、ＡＬは、前記クエリに含まれる要素の各校正候補の要素に対する位置関係を示す数値を示す関数であり、ＰＬＭは、前記クエリの前記校正候補それぞれへの変換の自然性の程度の確率を示す関数である、請求項１３乃至１６のうちいずれか一項に記載のクエリ校正方法。
【請求項１８】
請求項１３乃至１７のうちいずれか一項に記載のクエリ校正方法をコンピュータに実行させるコンピュータプログラム。
【請求項１９】
請求項１８に記載のコンピュータプログラムを格納した、コンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザが入力したクエリに対して校正結果を提供するクエリ校正システムおよび方法に関し、より詳細には、翻訳モデルに基づいてユーザのクエリに対する校正結果を提供するクエリ校正システムおよび方法に関する。
【背景技術】
【０００２】
ユーザは、検索エンジンのようなサイトを通じ、所期の情報を得るために検索を行うことができる。ユーザは、ユーザの端末を通じて検索エンジンのクエリ入力ウィンドウにクエリを入力し、出力された検索結果を確認することによって所期の情報を得ることができる。
【０００３】
しかし、ユーザが端末を通じてこのようなクエリを入力するときに、端末のキーボードへの入力ミスおよび／または韓英変換キーの選択ミスなどにより、本来の意図とは異なる誤字脱字を含んだクエリが入力される場合が発生することがある。特に、ユーザの端末がタッチスクリーンを備える場合には、誤ったタッチ入力などにより、誤字脱字を含んだクエリが入力される可能性がさらに高くなることもある。
【０００４】
誤字脱字を含んだクエリが検索エンジンに入力された場合、出力される検索結果にユーザが意図していた所期の情報が含まれなくなるが、これは検索品質の劣化に繋がるようにもなる。
【０００５】
したがって、ユーザが誤字脱字を含むクエリを入力したとしても、ユーザが本来より意図していた所期の情報を検索結果として得ることができるように、入力されたクエリを所期の正字クエリに変換してユーザに提供する方法が求められている。
【０００６】
特許文献１（公開日２０１１年１月２５日）は、統計データに基づいて誤字脱字クエリと判定されたユーザクエリに対して全体クエリ単位または単語単位によって校正を行うシステムおよび方法を開示している。
【０００７】
上述した情報は、理解を助けるためのものに過ぎず、従来技術の一部を形成しない内容を含むこともあるし、従来技術が通常の技術者に提示できることを含まないこともある。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】韓国公開特許第１０−２０１１−０００７７４３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
一実施形態は、翻訳モデルに基づいてユーザクエリの校正候補への変換に関する確率を計算し最適な校正候補を抽出することにより、ユーザのクエリおよび校正候補の編集距離に制限なく、最適な校正候補を校正結果として提供する、ユーザクエリ校正システムおよび方法を提供する。
【課題を解決するための手段】
【００１０】
一側面において、入力されたクエリに対する検索結果のログ情報に基づき、前記クエリに対する少なくとも１つの校正候補に関する情報を抽出する校正情報抽出部、前記の抽出された情報に基づき、前記クエリの前記校正候補への変換に関する少なくとも１つのパラメータを取得するパラメータ取得部、および前記の取得されたパラメータに基づき、前記クエリの前記少なくとも１つの校正候補のそれぞれへの変換と関連する確率を計算し、前記の計算された確率に基づき、前記クエリに対する校正結果として前記校正候補のうちから少なくとも１つの校正候補を抽出する校正結果生成部を備える、クエリ校正システムを提供する。
【００１１】
前記校正情報抽出部は、前記ログ情報を使用して前記クエリが誤字脱字を含むかを判定してもよい。
【００１２】
前記校正情報抽出部は、前記クエリが誤字脱字を含む場合、前記クエリに対する少なくとも１つの校正候補を識別してもよい。
【００１３】
前記ログ情報は、ユーザによって第１クエリが入力された後に第２クエリが入力されるまでの時間、前記検索結果に対するユーザのクリック情報、前記第１クエリと前記第２クエリとの類似度に関する情報、および前記検索結果の属性のうち少なくとも１つを含んでもよい。
【００１４】
前記検索結果の属性は、前記検索結果が含むコンテンツのカテゴリであってもよい。
【００１５】
前記パラメータ取得部は、前記クエリに含まれる要素が前記校正候補それぞれに含まれる要素に変換される確率、前記クエリに含まれる要素の各校正候補の要素に対する位置関係を示す数値、および前記クエリの前記校正候補それぞれへの変換の自然性の程度を示す確率のうち少なくとも１つをパラメータとして取得してもよい。
【００１６】
前記クエリに含まれる要素は、前記クエリに含まれる音節であり、前記校正候補それぞれに含まれる要素は、前記校正候補それぞれに含まれる音節であってもよい。
【００１７】
前記校正結果生成部は、前記校正結果として前記少なくとも１つの校正候補のうちから校正候補を抽出するにあたり、前記クエリに含まれる要素が配列される順序および前記少なくとも１つの校正候補の対応する要素が配列される順序を等しいものとして仮定してもよい。
【００１８】
前記校正結果として抽出された少なくとも１つの校正候補は、ユーザによる前記クエリの入力に対する検索結果に含まれてもよい。
【００１９】
前記の取得されたパラメータは複数であってもよい。
【００２０】
前記校正結果生成部は、前記の取得されたパラメータの倍またはログ加算に基づいて前記確率を計算してもよい。
【００２１】
前記校正候補は複数であってもよい。
【００２２】
前記校正結果生成部は、前記の複数の校正候補のそれぞれに対して計算された前記確率の分布に基づき、前記の複数の校正候補のうち少なくとも１つの校正候補を、前記クエリに対する校正結果としての校正候補抽出から除外してもよい。
【００２３】
前記確率は、数式によって計算されてもよい。
【００２４】
前記数式は、
【００２５】
【数１】
0006261669.tif 000002
であってもよい。
【００２６】
ｌは前記校正候補それぞれの長さであり、ｍは前記校正候補それぞれの長さであり、ｊは前記校正候補のインデックスであり、ｉは前記クエリのインデックスである。
【００２７】
ＴＲは、前記クエリに含まれるｉ番目の要素が前記校正候補それぞれに含まれるｊ番目の要素に変換される確率を示す関数である。
【００２８】
ＡＬは、前記クエリに含まれる要素の各校正候補の要素に対する位置関係を示す数値を示す関数である。
【００２９】
ＰＬＭは、前記クエリの前記校正候補それぞれへの変換の自然性の程度の確率を示す関数である。
【００３０】
前記校正情報抽出部および前記パラメータ取得部のうち少なくとも１つは、分散処理システムとして実現されてもよい。
【００３１】
前記校正候補に関する情報は、前記クエリおよび各校正候補で構成された誤字脱字−正字ペアを含んでもよい。
【００３２】
前記確率は、前記クエリが入力されるときに各校正候補が発生する条件付き確率であってもよい。
【００３３】
他の一側面において、入力されたクエリに対する検索結果のログ情報に基づき、前記クエリに対する少なくとも１つの校正候補に関する情報を抽出する段階、前記の抽出された情報に基づき、前記クエリの前記校正候補への変換に関する少なくとも１つのパラメータを取得する段階、前記の取得されたパラメータに基づき、前記クエリの前記少なくとも１つの校正候補のそれぞれへの変換と関連する確率を計算する段階、および前記の計算された確率に基づき、前記クエリに対する校正結果として前記校正候補のうちから少なくとも１つの校正候補を抽出する段階を含む、クエリ校正方法が提供される。
【００３４】
前記校正候補に関する情報を抽出する段階は、前記ログ情報を使用して前記クエリが誤字脱字を含むかを判定する段階を含んでもよい。
【００３５】
前記校正候補に関する情報を抽出する段階は、前記クエリが誤字脱字を含む場合、前記クエリに対する少なくとも１つの校正候補を識別する段階を含んでもよい。
【００３６】
前記パラメータを取得する段階は、前記クエリに含まれる要素が前記校正候補それぞれに含まれる要素に変換される確率、前記クエリに含まれる要素の各校正候補の要素に対する位置関係を示す数値、および前記クエリの前記校正候補それぞれへの変換の自然性の程度を示す確率のうち少なくとも１つをパラメータとして取得してもよい。
【００３７】
前記クエリ校正方法は、前記校正結果として抽出された少なくとも１つの校正候補を、ユーザによる前記クエリの入力に対する検索結果として出力する段階をさらに含んでもよい。
【００３８】
前記校正候補は複数であってもよい。
【００３９】
前記少なくとも１つの校正候補を抽出する段階は、前記の複数の校正候補のそれぞれに対して計算された前記確率の分布に基づき、前記の複数の校正候補のうち少なくとも１つの校正候補を、前記クエリに対する校正結果としての校正候補抽出から除外する段階を含んでもよい。
【発明の効果】
【００４０】
翻訳モデルに基づいてユーザクエリの校正候補への変換に関する確率を計算して最適な校正候補を抽出することにより、ユーザのクエリおよび校正候補の編集距離に制限なく、ユーザのクエリに対してユーザの意図に符合する最適な校正候補を校正結果として提供することができる。
【００４１】
翻訳モデルに基づいてユーザクエリの校正候補への変換に関する確率を計算して最適な校正候補を抽出することにより、ユーザのクエリに対する校正の正確性を損なうことなく、校正のカバレッジを向上させることができる。
【図面の簡単な説明】
【００４２】
【図１】一実施形態における、ユーザクエリ校正システムの動作方法を示した図である。
【図２】一実施形態における、ユーザクエリ校正システムを示した図である。
【図３】一実施形態における、ユーザクエリの校正候補への変換に関するパラメータの取得方法を概念的に示した図である。
【図４Ａ】一実施形態における、ユーザクエリの校正候補への変換に関するパラメータとしての帯域確率および整列確率の取得方法を示した疑似コードである。
【図４Ｂ】一実施形態における、ユーザクエリの校正候補への変換に関するパラメータとしての帯域確率および整列確率の取得方法を示した疑似コードである。
【図５】図４Ａおよび図４Ｂのアルゴリズムによるパラメータ取得方法のパフォーマンスを示した図である。
【図６】一実施形態における、ユーザクエリの校正候補への変換に関するパラメータとしてのＬＭパラメータの取得方法を示した図である。
【図７】一実施形態における、ユーザクエリに対する校正結果としての校正候補を抽出する方法を示した概念図である。
【図８】一実施形態における、ユーザクエリに対する校正結果としての校正候補を抽出する方法を示した疑似コードである。
【図９】一実施形態における、ユーザクエリ校正システムの動作方法を示したフローチャートである。
【図１０】一実施形態における、ユーザクエリに対する少なくとも１つの校正候補に関する情報を抽出する方法を示したフローチャートである。
【図１１】一実施形態における、ユーザクエリに対する校正候補のうちから不必要な校正候補を除外することにより、校正結果としての校正候補を抽出する方法を示したフローチャートである。
【発明を実施するための形態】
【００４３】
以下、本発明の実試形態について、添付の図面を参照しながら詳細に説明する。
【００４４】
図１は、一実施形態における、ユーザクエリ校正システムの動作方法を示した図である。
【００４５】
図に示すユーザクエリ校正システム１００（以下、クエリ校正システムとする）は、ユーザの端末から入力されたユーザクエリ（以下、クエリとする）を処理し、前記クエリに対する適切な校正結果を提供するシステムである。例えば、ユーザは、ＰＣまたはモバイル端末（例えば、携帯電話、スマートフォン、タブレットＰＤＡなど）を通じてクエリを入力することができ、クエリ校正システム１００は、ユーザが入力したクエリに誤字脱字が存在するかを判定し、誤字脱字が存在すると判定された場合には、該当のクエリに対する校正結果としての校正候補を提供することができる。
【００４６】
端末を通じて入力されたユーザのクエリは、例えば、コンテンツの検索および／または照会、または情報の取得のような作業の実行を要求するために、検索エンジンなどに入力されるキーワードまたは文字列であってよい。クエリは少なくとも１つの要素で構成されてもよく、クエリを構成する各要素は単語または音節であってもよい。
【００４７】
校正システム１００は、ユーザが過去に入力したクエリに対する検索情報のログ情報に基づいて、入力されたクエリが正字であるかを判定し、該当のクエリの校正結果となり得る校正候補（群）を識別し、校正候補（群）のうち最適な校正候補を校正結果として提供することができる。
【００４８】
校正結果として決まった校正候補は、ユーザクエリと共にあるいは別に、ユーザクエリに対する検索結果として提供されてもよい。または、校正結果として決まった校正候補は、ユーザクエリに対する検索結果に含まれてもよい。さらに、校正結果として決まった校正候補に対する検索結果は、ユーザクエリに対する検索結果として提供されてもよい。
【００４９】
校正結果は、ユーザのクエリ入力に対してリアルタイムで提供されてもよい。
【００５０】
入力されたクエリに対して校正候補（群）を識別して校正結果を提供する方法については、図２乃至図７を参照しながらさらに詳しく説明する。
【００５１】
図２は、一実施形態における、ユーザクエリ校正システムを示した図である。図２を参照しながら、上述したクエリ校正システム１００についてさらに詳しく説明する。クエリ校正システム１００は、プロセッサ２１０を含んでよい。プロセッサ２１０は、ユーザのクエリを処理しクエリに対する校正結果を提供するために要求されるプログラムを実行したり、関連する演算を処理したりするための構成であってよい。プロセッサ２１０は、校正情報抽出部２２０、校正結果生成部２３０、およびパラメータ取得部２４０を含んでよい。校正情報抽出部２２０、校正結果生成部２３０、およびパラメータ取得部２４０のそれぞれは、プロセッサ２１０内で（または、図に示すものとは異なりプロセッサ２１０外部で）別のハードウェア構成によって実現されてもよい。図２では、プロセッサ２１０は単数で示されているが、複数のプロセッサであってもよく、プロセッサ内の少なくとも１つのコアを意味するものであってもよい。言い換えれば、校正情報抽出部２２０、校正結果生成部２３０、およびパラメータ取得部２４０のうち少なくとも一部は、プロセッサ２１０とは異なるプロセッサ２１０または異なるハードウェア構成内で実現されてもよい。
【００５２】
または、校正情報抽出部２２０、校正結果生成部２３０、およびパラメータ取得部２４０は、プロセッサ２１０が実行する機能を示す構成であってもよい。言い換えれば、校正情報抽出部２２０、校正結果生成部２３０、およびパラメータ取得部２４０のそれぞれは、ソフトウェアモジュールとして構成されてもよい。
【００５３】
校正システム１００は、通信部２５０をさらに含んでよい。通信部２５０は、外部サーバまたはその他の端末からデータおよび情報を送受信することができる。例えば、通信部２５０は、ユーザの端末からクエリを受信したり、検索結果のログ情報を取得したり、ユーザクエリおよびユーザクエリに対する校正結果を出力したりするための構成であってよい。
【００５４】
校正情報抽出部２２０は、予め入力されているクエリに対する検索結果のログ情報に基づき、ユーザの端末から入力されたクエリに対する少なくとも１つの校正候補に関する情報を抽出することができる。校正情報抽出部２２０は、ＳＶＭ基盤の誤字脱字−正字候補検出器（ＳＶＭ  ｂａｓｅｄ  Ｅｒｒａｔａ−Ｃｏｒｒｅｃｔ  Ｃａｎｄｉｄａｔｅ  Ｄｅｔｅｃｔｏｒ）に対応してもよい。
【００５５】
校正情報抽出部２２０は、前記ログ情報を使用して前記クエリが誤字脱字を含むかを判定し、前記クエリが誤字脱字を含む場合には、前記クエリに対する少なくとも１つの校正候補を識別することができる。
【００５６】
校正候補に関する情報は、クエリおよび各校正候補として構成された誤字脱字−正字ペアを含んでもよい。言い換えれば、識別されたクエリ−各校正候補は誤字脱字−正字のペアであってもよく、識別された誤字脱字−正字ペアは、データベース（図示せず）内に格納されて管理されてもよい。
【００５７】
ログ情報は、所定の期間にユーザ（ら）によって入力されたクエリ（群）および該当のクエリ（群）による検索結果（群）に関するログ情報であってもよい。ログ情報は、ユーザによって第１クエリが入力された後、その次に入力される第２クエリが入力されるまでの時間、クエリに対する検索結果に対するユーザのクリック情報、第１クエリと第２クエリとの類似度に関する情報および検索結果の属性のうち少なくとも１つを含んでもよい。
【００５８】
ログ情報が、ユーザによって第１クエリが入力された後、その次に入力される第２クエリが入力されるまでの時間を含む場合、例えば、第１クエリが入力された後、所定の時間以内に第２クエリが入力された場合に、校正情報抽出部２２０は、第１クエリが誤字脱字を含む（または含む可能性が高い）と判定してもよい。第１クエリが入力された後、所定の時間以後に第２クエリが入力された場合に、校正情報抽出部２２０は、第１クエリおよび第２クエリを互いに別のクエリとして判定してもよい。
【００５９】
ログ情報が、クエリに対する検索結果に対するユーザのクリック情報を含む場合、例えば、クエリの検索結果に対してユーザのクリックが存在する場合に、校正情報抽出部２２０は、前記クエリが誤字脱字を含まない（または含まない可能性が高い）と判定してもよい。
【００６０】
ログ情報が含む、前記第１クエリと前記第２クエリとの類似度に関する情報は、第１クエリと第２クエリとの編集距離（ｅｄｉｔ  ｄｉｓｔａｎｃｅ）であってもよい。編集距離は、レーベンシュタイン距離（Ｌｅｖｅｎｓｈｔｅｉｎ  ｄｉｓｔａｎｃｅ）であってもよい。ユーザによって第１クエリが入力された後、その次に第２クエリが入力された場合に、第１クエリと第２クエリとの編集距離が所定の値以下であるとき、校正情報抽出部２２０は、第１クエリが誤字脱字を含む（または含む可能性が高い）と判定してもよい。反対に、第１クエリと第２クエリとの編集距離が所定の値を超えるとき、校正情報抽出部２２０は、第１クエリおよび第２クエリを互いに別のクエリとして判定してもよい。
【００６１】
ログ情報が含む検索結果の属性は、検索結果が含むコンテンツの種類またはカテゴリであってもよい。例えば、カテゴリは、ウェブ文書、音楽、イメージ、ブログ、ニュース、および人物情報のうちいずれか１つであってもよい。校正情報抽出部２２０は、クエリに対する検索結果に含まれるコンテンツがウェブ文書だけである場合、該当のクエリは誤字脱字を含む（または含む可能性が高い）と判定してもよい。
【００６２】
クエリに対する校正候補を識別するにあたり、上述した実施形態のようにログ情報を考慮することで、クエリが誤字脱字を含んでいるかをより正確に判定することができ、クエリに対するより正確な校正候補（群）を識別することができる。
【００６３】
校正情報抽出部２２０は、分散処理システム、例えば、Ｈａｄｏｏｐ基盤の分散処理システムを使用して実現されてもよい。分散処理システムを基盤として実現することで、校正情報抽出部２２０は、膨大な量のデータを高速で処理することができる。
【００６４】
パラメータ取得部２４０は、校正情報抽出部２２０によって抽出された情報に基づき、入力されたクエリの校正候補への変換に関する少なくとも１つのパラメータを取得することができる。パラメータは、クエリの校正候補のそれぞれへの変換と関連する確率を計算するために使用されてもよい。
【００６５】
パラメータ取得部２４０は、クエリに含まれる要素が校正候補それぞれに含まれる要素に変換される確率、クエリに含まれる要素の各校正候補の要素に対する位置関係を示す数値、およびクエリの校正候補それぞれへの変換の自然性の程度を示す確率のうち少なくとも１つをパラメータとして取得してもよい。クエリに含まれる要素は、前記クエリに含まれる音節であり、前記校正候補それぞれに含まれる要素は、前記校正候補それぞれに含まれる音節であってもよい。
【００６６】
パラメータ取得部２４０は、例えば、ＩＢＭ（登録商標）  ＭＯＤＥＬ  ２技法を使用するアルゴリズムに基づき、クエリの校正候補のそれぞれへの変換と関連する確率を計算するために必要となるパラメータを取得してもよく、確率および整列パラメータ取得部２４２および言語モデルパラメータ取得部２４４を含んでもよい。
【００６７】
確率および整列パラメータ取得部２４２は、例えば、期待値最大化（Ｅｘｐｅｃｔａｔｉｏｎ−Ｍａｘｉｍｉｚａｔｉｏｎ；ＥＭ）アルゴリズムを使用してクエリに含まれる要素が校正候補それぞれに含まれる要素に変換される確率およびクエリに含まれる要素の各校正候補の要素に対する位置関係を示す数値を計算するＩＢＭ  ＭＯＤＥＬ  ２パラメータＥＭ学習器（ＩＢＭ  ＭＯＤＥＬ  ２  Ｐａｒａｍｅｔｅｒ  ＥＭ  Ｌｅａｒｎｅｒ）に対応してもよい。
【００６８】
言語モデルパラメータ取得部２４４は、例えば、クエリの校正候補それぞれへの変換の自然性の程度を示す確率として言語モデル（Ｌａｎｇｕａｇｅ  Ｍｏｄｅｌ；ＬＭ）パラメータを計算するＬＭパラメータ学習器（ＬＭ  Ｐａｒａｍｅｔｅｒ  Ｌｅａｒｎｅｒ）であってもよい。確率および整列パラメータ取得部２４２および言語モデルパラメータ取得部２４４は、分散処理システム、例えば、Ｈａｄｏｏｐ基盤の分散処理システムを使用して実現されてもよい。分散処理システムを基盤として実現することで、パラメータ取得部２４０は、膨大な量のデータを高速で処理することができる。
【００６９】
確率および整列パラメータ取得部２４２および言語モデルパラメータ取得部２４４の詳しい動作については、図３乃至図６を参照しながらさらに詳しく説明する。
【００７０】
校正結果生成部２３０は、パラメータ取得部２４０によって取得されたパラメータに基づき、クエリの少なくとも１つの校正候補のそれぞれへの変換と関連する確率を計算することができる。例えば、校正結果生成部２３０は、パラメータ取得部２４０によって取得されたパラメータの倍またはログ加算に基づいて前記確率を計算してもよい。クエリの校正候補への変換と関連する確率は、クエリが入力されるときに各校正候補が発生する条件付き確率であってもよい。校正結果生成部２３０は、下記の数式（１）を使用し、クエリが少なくとも１つの校正候補のそれぞれに変換される確率を計算してもよい。
【００７１】
【数２】
0006261669.tif 000003
【００７２】
ここで、ｌは校正候補それぞれの長さであり、ｍはクエリの長さであり、ｊは校正候補それぞれに含まれる要素のインデックスであり、ｉはクエリに含まれる要素のインデックスである。ＴＲは、前記クエリに含まれるｉ番目の要素が前記校正候補それぞれに含まれるｊ番目の要素に変換される確率を示す関数である。例えば、ＴＲは、帯域確率を計算するための関数であってもよい。ＡＬは、前記クエリに含まれる要素の各校正候補の要素に対する位置関係を示す数値を示す関数である。例えば、ＡＬは、整列確率を計算するための関数であってもよい。ＰＬＭは、クエリの校正候補それぞれへの変換の自然性の程度を示す確率を示す関数である。例えば、ＰＬＭは、ＬＭパラメータを計算するための関数であってもよい。
【００７３】
校正結果生成部２３０は、各校正候補に対して計算された確率に基づき、クエリに対する校正結果として校正候補のうちから少なくとも１つの校正候補を抽出することができる。抽出される校正候補は、所期の（最適な）校正候補であって、ユーザクエリに対する正字クエリであってもよい。校正結果生成部２３０は、校正結果として少なくとも１つの校正候補のうちから校正候補を抽出するにあたり、クエリに含まれる要素が配列される順序および前記少なくとも１つの校正候補の対応する要素が配列される順序を等しいものと仮定してもよい。言い換えれば、クエリと校正候補との間には、モノトニックアライメント（ｍｏｎｏｔｏｎｉｃ  ａｌｉｇｎｍｅｎｔ）が仮定されてもよい。
【００７４】
また、校正結果生成部２３０は、複数の校正候補のそれぞれに対して計算された前記確率の分布に基づき、複数の校正候補のうち少なくとも１つの校正候補を、クエリに対する校正結果としての校正候補抽出から除外してもよい。
【００７５】
校正結果生成部２３０は、例えば、ＩＢＭ  ＭＯＤＥＬ  ２技法を使用するアルゴリズムに基づいてクエリに対する校正結果を生成するＩＢＭ  ＭＯＤＥＬ  ２デコーダ（ＩＢＭ  ＭＯＤＥＬ  ２  Ｄｅｃｏｄｅｒ）に対応してもよい。
【００７６】
校正結果生成部２３０の詳しい動作については、図７および図８を参照しながらさらに詳しく説明する。
【００７７】
図１を参照しながら上述した技術的特徴についての説明は、図２に対してもそのまま適用することができるため、重複する説明は省略する。
【００７８】
図３は、一実施形態における、ユーザクエリの校正候補への変換に関するパラメータの取得方法を概念的に示した図である。
【００７９】
図３は、図２を参照しながら上述した、クエリに含まれる要素の各校正候補の要素に対する位置関係を示す数値を計算する方法を概念的に示した図である。図３では、ユーザが入力したクエリは「ニューバランス  シンチユン」であり、校正候補は「ニューバランス  シンチョン」であると仮定する。「要素」とは、クエリおよび校正候補を構成する音節を示すものである。
【００８０】
クエリに含まれる要素の各校正候補の要素に対する位置関係を示す数値とは、クエリの各要素が校正候補の各要素の位置に対応するようになる確率を意味してもよく、図３において各矢印に対応する値を意味してもよい。言い換えれば、各矢印に対応する値は、上述したＡＬ関数に基づいて決められた値（整列確率）であってもよい。
【００８１】
図に示すように、確率および整列パラメータ取得部２４２は、分散システム上でＥＭアルゴリズムを使用する反復（ｉｔｅｒａｔｉｏｎ）プロセスを実行することにより、クエリに含まれる要素の各校正候補の要素に対する位置関係を示す数値を計算してもよい。
【００８２】
図１および図２を参照しながら上述した技術的特徴についての説明は、図２に対してもそのまま適用することができるため、重複する説明は省略する。
【００８３】
図４Ａおよび図４Ｂは、一実施形態における、ユーザクエリの校正候補への変換に関するパラメータとしての帯域確率および整列確率の取得方法を示す疑似コード（ｐｓｅｕｄｏ  ｃｏｄｅ）を示した図である。図に示すアルゴリズムは、確率および整列パラメータ取得部２４２によって実行されてもよい。
【００８４】
確率および整列パラメータ取得部２４２は、マッパー（ｍａｐｐｅｒ）およびリデューサー（ｒｅｄｕｃｅｒ）で構成されてもよい。
【００８５】
マッパーの動作は、下記のアルゴリズムで示されてもよい（図４Ａ参照）。
【００８６】
【数３】
0006261669.tif 000004
【００８７】
ここで、音節ｔｒｉｇｒａｍを使用して計算されたｓｃｏｒｅに対する、出力としてのｅｓｔｉ＿ｐｒｏｂ（ｋ，ｉ，ｊ）は、ＴＲ（Ｅｒｒａｔａｉ｜Ｃｏｒｒｅｃｔｉｏｎｊ）を計算するために使用されてもよい。また、Ｌｅｎ関数を使用して計算されたｓｃｏｒｅに対する、出力としてのｅｓｔｉ＿ｐｒｏｂ（ｋ，ｉ，ｊ）値は、ＡＬ（ｊ｜ｉ，ｌ，ｍ）ｄｍｆを計算するために使用されてもよい。一方、ｅｓｔｉ＿ｐｒｏｂ値は、ｔ−１段階（ｓｔｅｐ）におけるリデューサーの出力であってもよい。初期ｅｓｔｉ＿ｐｒｏｂ値は、１／Ｌｅｎ（入力）であってもよい。上述したアルゴリズムを基盤とした計算は、ディスクメモリマップド（ｄｉｓｋ  ｍｅｍｏｒｙ  ｍａｐｐｅｄ）Ｉ／Ｏ方式の完全ハッシュ（ｐｅｒｆｅｃｔ  ｈａｓｈ）として格納されたデータを、分散型システムを構成する各ｈａｄｏｏｐノードによってローディングすることを通じて行われてもよい。
【００８８】
図４に示す出力されたデータのように、リデューサーは、ＡＬおよびＴＲの計算に必要な因子をそれぞれ「Ｃ」および「Ｍ」に区別してもよい（１ｓｔ  ｋｅｙ）。出力されたデータのうち分母にならなければならない情報（音節、インデックス、文字列の長さ）が区分されてもよく、分母であるか分子であるかは「０」、「１」で区分されてもよい（２ｎｄ  ｋｅｙ、３ｒｄ  ｋｅｙ）。さらに、分子となる情報（音節、インデックス）も区分されてもよい。出力されたデータのうち、フィールドの最後の値をｓｃｏｒｅとしてもよい。
【００８９】
マッパーの出力が整列された後にｓｕｍとなる結果は、リデューサーの動作を示す下記のアルゴリズムで表現されてもよい（図４Ｂ参照）。
【００９０】
【数４】
0006261669.tif 000005
【００９１】
図２および図３を参照しながら上述したパラメータに対応する、ＴＲ（帯域確率）およびＡＬ（整列確率）は、前記アルゴリズムによって計算されてもよい。また、計算されたｅｓｔｉ＿ｐｒｏｂ（ｋ，ｉ，ｊ）は、ｔ＋１段階でｓｃｏｒｅ値をアップデートするために使用されてもよく、完全ハッシュ構造でディスクまたはデータベースに格納されて管理されてもよい。
【００９２】
図１乃至図３を参照しながら上述した技術的特徴についての説明は、ここでもそのまま適用することができるため、重複する説明は省略する。
【００９３】
図５は、図４Ａおよび図４Ｂのアルゴリズムによるパラメータ取得方法のパフォーマンスを示した図である。
【００９４】
図５では、２４個のマッパーおよび２０個のリデューサーが使用され、合計１５個のノード（２．２ＧＨｚ、４８ＧＲＡＭ）が使用された。入力としては約３千７百万個の誤字脱字−正字ペアデータが使用され、出力としては約２億５千７百万個のモデルパラメータが得られた。
【００９５】
結果を詳察すると、各ＥＭ段階あたり１１乃至１４分を所要したことが確認された（合計９乃至１０回の反復プロセスが行われる）。
【００９６】
図６は、一実施形態における、ユーザクエリの校正候補への変換に関するパラメータとしてのＬＭパラメータの取得方法を示した図である。図６で示すアルゴリズムは、図２を参照しながら上述したクエリの校正候補それぞれへの変換の自然性の程度を示す確率（ＬＭパラメータ）を計算する方法を示している。図に示すアルゴリズムは、言語モデルパラメータ取得部２４４によって実行されてもよい。ＬＭパラメータは、クエリが校正候補に変換されるために必要となる文脈および／または自然性の程度を確率で示したものである。
【００９７】
言語モデルパラメータ取得部２４４は、平滑化（Ｓｍｏｏｔｈｉｎｇ）プロセスおよび線形補間（ｌｉｎｅａｒ  ｉｎｔｅｒｐｏｌａｔｉｏｎ）プロセスを実行することによってＬＭパラメータを取得してもよい。ただし、平滑化プロセスは、処理されなければならない誤字脱字−正字ペアの数が極めて多い場合（例えば、１０億個以上）にのみ実行されてもよい。
【００９８】
言語モデルパラメータ取得部２４２は、マッパーおよびリデューサーで構成されてもよい。ＬＭパラメータを取得するにあたり、分母ローカルＳＵＭ（ｌｏｃａｌ  ｓｕｍ）計算は、例えば、リデューサーキー（ｒｅｄｕｃｅｒ  ｋｅｙ）に分母となる情報をＦｉｒｓｔ−Ｐｒｉｏｒｉｔｙ−Ｋｅｙで生成することによって実行されてもよい。
【００９９】
ＬＭパラメータを取得するにあたり、分散環境における統計学習は、スパーク（Ｓｐａｒｋ）を使用して実行されてもよい。
【０１００】
図に示すアルゴリズムにおいて、入力されたクエリおよびその頻度はそれぞれ「あかさたなはまや」、「９９」と「あかさたなはまが」、「１」とが仮定された。推定された１０ｇｒａｍ確率がＬＭパラメータとして計算されてもよく、１０ｇｒａｍ確率は、８ｇｒａｍ確率および９ｇｒａｍ確率を計算した後、補間によって推定されてもよい。
【０１０１】
段階１で、マッパーは８乃至１０ｇｒａｍを抽出してもよく、リデューサーは頻度合計を計算してもよい。前記段階１は、例えば、文字列「ａｂｃｄ」に対してＰ（ｄ｜ａｂｃ）を計算するための前処理過程であってもよい。ＬＭパラメータの計算は、「ｍｉｎ（Ｎ）ｇｒａｍ」、「Ｎ−１ｇｒａｍ」、「Ｎｇｒａｍ」形式のキー構造（Ｎ＝８乃至１０）を使用して実行されてもよく、したがって、分母優先頻度合計の計算を容易に実行することができる。
【０１０２】
段階２で、段階１の結果を使用し（ｍａｐ＝‘ｃａｔ’＆ｓｏｒｔ）、リデューサーは８乃至１０ｇｒａｍそれぞれの確率値を計算してもよい。ここで、８ｇｒａｍの分母は、ｓｕｍ（ｃｎｔ＿ｏｆ＿ａｌｌ（８ｇｒａｍ））に割り当てられてもよい。
【０１０３】
段階３で、段階２で計算された８乃至１０ｇｒａｍ確率値を使用して１０ｇｒａｍ確率が線形補間されてもよい。マッパーは、段階１と同じキーを生成し、１番目のキー（１ｓｔ  ｋｅｙ）を文字列の逆順に変換し、「最終」音節を基準として８乃至１０ｇｒａｍが分類（ｓｏｒｔ）およびリデューサーにグルーピング（ｇｒｏｕｐｉｎｇ）されるようにしてもよい。リデューサーは、線形補間を実行することによって最終的なＬＭパラメータを生成してもよい。例えば、「あいうえ」の文字列に対し、ＬＭパラメータＰＬＭ（た｜さかあ）は、ａ×ＰＬＭ（た｜さかあ）、ｂ×ＰＬＭ（た｜さか）およびｃ×ＰＬＭ（た｜さ）の合計で計算されてもよい。ここで、加重値ａ、ｂおよびｃは、「Ａ  ｓｔａｔｉｓｔｉｃａｌ  Ｐａｒｔ−ｏｆ−Ｓｐｅｅｃｈ  Ｔａｇｇｅｒ，Ｔ．Ｂｒａｎｔ  ｅｔ  ａｌ，２０００」で提案された方法に基づいて計算されてもよい。ｕｎｓｅｅｎ確率は、１／ｓｕｍ（ｃｎｔ＿ｏｆ＿ａｌｌ（１０ｇｒａｍ）＋ｃｎｔ＿ｏｆ＿ｄｉｃ（１０ｇｒａｍ））で計算されてもよい。
【０１０４】
下記の表１は、図に示すアルゴリズムによるＬＭパラメータ取得方法のパフォーマンスを示す。表１の結果については、２４個のマッパーおよび２０個のリデューサーが使用され、合計１５個のノード（２．２ＧＨｚ、４８ＧＲＡＭ）が使用された。
【０１０５】
【表１】
0006261669.tif 000006
【０１０６】
図１乃至５を参照しながら上述した技術的特徴についての説明は、ここでもそのまま適用することができるため、重複する説明は省略する。
【０１０７】
図７は、一実施形態における、ユーザクエリに対する校正結果としての校正候補を抽出する方法を示した概念図である。図７は、例えば、ＩＢＭ  ＭＯＤＥＬ  ２技法を使用するアルゴリズムを基盤としてクエリに対する校正結果を生成するＩＢＭ  ＭＯＤＥＬ  ２デコーダに対応する校正結果生成部２３０のクエリに対する最適の校正候補を抽出する方法を示している。
【０１０８】
最適な校正候補は、下記の数式（２）によって決められてもよい。
【０１０９】
【数５】
0006261669.tif 000007
【０１１０】
言い換えれば、クエリに対する複数の校正候補のうち、上述した数式（１）に基づいて計算された確率が最大である校正候補を最適な校正候補として決めて抽出してもよい。
【０１１１】
クエリと校正候補との間には、モノトニックアライメントが仮定されてもよい。また、最適な校正候補は、ダイナミックアルゴリズム（ｄｙｎａｍｉｃ  ａｌｇｏｒｉｔｈｍ）を使用して決められてもよい。また、複数の校正候補のそれぞれに対して計算された前記確率の分布に基づき、複数の校正候補のうち少なくとも１つの校正候補が、クエリに対する校正結果としての校正候補抽出から除外されてもよい。例えば、確率分布で点値として示される中間確率値に対応する校正候補は、不必要な校正候補として校正候補抽出過程から除外されてもよい。前記過程により、校正候補の数が多い場合でも、最適な校正候補を高速で決めることができる。
【０１１２】
段階１で、校正結果生成部２３０は、クエリに対する可能な校正候補に対し、計算されたＴＲおよびＡＬパラメータを使用し、最適な校正候補決定のための情報を生成してもよい。
【０１１３】
段階２で、校正結果生成部２３０は、音節単位でクエリをデコードすることによって最適な校正候補を決めてもよい。段階２では、例えば、帯域確率、整列確率、およびＬＭパラメータのうち少なくとも１つによって計算された点数（ｓｃｏｒｅ）に基づいて不必要な校正候補が除外されてもよい。図に示す例示では、クエリ「ニューバランス  シンチユン」に対して「ニューバランス  シンチョン」が最適な校正候補として決められた。
【０１１４】
校正結果生成部２３０は、１０００乃至１５００  ＴＰＳ／ｃｏｒｅの速度で実現されてもよい。段階１および２については、図８のアルゴリズムを参照しながらさらに詳しく説明する。図１乃至図６を参照しながら上述した技術的特徴についての説明は、ここでもそのまま適用することができるため、重複する説明は省略する。
【０１１５】
図８は、一実施形態における、ユーザクエリに対する校正結果としての校正候補を抽出する方法を示した疑似コードである。図８では、図７を参照しながら上述した最適な校正候補を抽出するための段階１および２についてさらに詳しく説明する。
【０１１６】
段階１で、校正結果生成部２３０は、クエリに対する可能な校正候補に対し、計算されたＴＲおよびＡＬパラメータを使用し、最適な校正候補決定のための情報を生成してもよい。クエリは音節単位でトークン化されてもよく、有限状態トランスデューサ（ｆｉｎｉｔｅ  ｓｔａｔｅ  ｔｒａｎｓｄｕｃｅｒ）に基づいてクエリに対してすべての可能なＡＬおよびＴＲパラメータが抽出されてもよい。抽出されたＡＬおよびＴＲパラメータは格納されてもよく（データベースまたはメモリなどに）、クエリの音節インデックス（ｓｙｌｌａｂｌｅ  ｉｎｄｅｘ）にマッピングされてもよい。
【０１１７】
段階２で、校正結果生成部２３０は、校正候補のうちから最適な校正候補を決めてもよい。段階１における出力（入力クエリおよびそのＡＬおよびＴＲパラメータ）は、段階２における入力となってもよい。下記のアルゴリズムを通じて入力の校正候補に対する点数が計算されてもよく、点数に基づいて１つの校正候補が最適な校正候補として決められてもよい。
【０１１８】
【数６】
0006261669.tif 000008
【０１１９】
帯域確率、整列確率、およびＬＭパラメータに基づいて計算された点数にしたがって不必要な校正候補が除外され、計算された点数にしたがって校正候補のうちから最適な校正候補が決められてもよい。決められた最適な校正候補は、上述した校正結果として抽出された校正候補に対応してもよく、ユーザのクエリに対する検索結果として提供されてもよい。
【０１２０】
図１乃至図７を参照しながら上述した技術的特徴についての説明は、ここでもそのまま適用することができるため、重複する説明は省略する。
【０１２１】
図９は、一実施形態における、ユーザクエリ校正システムの動作方法を示したフローチャートである。
【０１２２】
段階９１０で、校正情報抽出部２２０は、予め入力されているクエリに対する検索結果のログ情報に基づき、ユーザクエリに対する少なくとも１つの校正候補に関する情報を抽出することができる。抽出される校正候補に関する情報は、クエリおよび校正候補で構成される誤字脱字−正字ペアを含んでもよい。
【０１２３】
段階９２０で、パラメータ取得部２４０は、段階９１０で抽出された情報に基づき、クエリの校正候補への変換に関する少なくとも１つのパラメータを取得することができる。クエリの校正候補への変換に対する帯域確率のパラメータおよび整列確率のパラメータは、パラメータ取得部２４０の確率および整列パラメータ取得部２４２によって計算および取得されてもよい。クエリの校正候補への変換に対するＬＭパラメータは、パラメータ取得部２４０の言語モデルパラメータ取得部２４４によって計算および取得されてもよい。
【０１２４】
段階９３０で、校正結果生成部２３０は、段階９２０で取得されたパラメータに基づき、クエリの校正候補（群）のそれぞれへの変換と関連する確率を計算することができる。例えば、校正結果生成部２３０は、上述した数式（１）を使用して前記確率の計算を実行してもよい。
【０１２５】
段階９４０で、校正結果生成部２３０は、段階９３０で計算された確率に基づき、クエリに対する校正結果として校正候補（群）のうちから少なくとも１つの校正候補を抽出することができる。例えば、校正結果生成部２３０は、上述した数式（２）を使用して校正候補（群）のうちから１つの校正候補を校正結果として抽出してもよい。
【０１２６】
段階９５０で、クエリ校正システム１００の通信部２５０は、段階９４０で抽出された校正結果としての校正候補を、ユーザのクエリ入力に対する検索結果として出力することができる。また、ユーザのクエリ入力に対する検索結果には、抽出された校正結果が含まれてもよい。
【０１２７】
図１乃至図８を参照しながら上述した技術的特徴についての説明は、ここでもそのまま適用することができるため、重複する説明は省略する。
【０１２８】
図１０は、一実施形態における、ユーザクエリに対する少なくとも１つの校正候補に関する情報を抽出する方法を示したフローチャートである。
【０１２９】
後述する段階１０１０および１０２０は、図９を参照しながら上述した段階９１０に含まれてもよい。
【０１３０】
段階１０１０で、校正情報抽出部２２０は、検索結果のログ情報を使用してクエリが誤字脱字を含むかを判定することができる。クエリが誤字脱字を含まなければ、該当のクエリは正字クエリに該当すると判定されるため、別途の校正結果が提供される必要はない。
【０１３１】
クエリが誤字脱字を含む場合、段階１０２０で、校正情報抽出部２２０は、クエリに対する少なくとも１つの校正候補を識別することができる。例えば、校正情報抽出部２２０は、校正候補を識別することにより、クエリ−校正候補に対する少なくとも１つの誤字脱字−正字ペアを校正候補に関する情報として識別してもよい。
【０１３２】
図１乃至図９を参照しながら上述した技術的特徴についての説明は、ここでもそのまま適用することができるため、重複する説明は省略する。
【０１３３】
図１１は、一実施形態における、ユーザクエリに対する校正候補のうち不必要な校正候補を除外することによって校正結果としての校正候補を抽出する方法を示したフローチャートである。
【０１３４】
後述する段階１１１０および１１２０は、図９を参照しながら上述した段階９４０に含まれてもよい。
【０１３５】
段階１１１０で、校正結果生成部２３０は、複数の校正候補のそれぞれに対して段階９３０で計算された確率の分布に基づき、複数の校正候補のうち少なくとも１つの校正候補を、クエリに対する校正結果としての校正候補抽出過程から除外することができる。
【０１３６】
段階１１２０で、校正結果生成部２３０は、段階１１１０によって不必要な校正候補が除外された複数の校正候補のうちから少なくとも１つの校正候補をクエリに対する校正結果として抽出することができる。
【０１３７】
図１乃至図１０を参照しながら上述した技術的特徴についての説明は、ここでもそのまま適用することができるため、重複する説明は省略する。
【０１３８】
下記では、従来技術と比較した本実施形態の効果および技術的な改善事項について説明する。
【０１３９】
効果および技術的改善事項の評価において、ＩＢＭ  ＭＯＤＥＬ  ２の学習のために使用されたデータは、ＩＢＭ＿ＳＥＴ−７およびＩＢＭ＿ＳＥＴ−２１によってそれぞれ示した。ＩＢＭ＿ＳＥＴ−７は、７日間のクエリに対する誤字脱字−校正候補のデータであり、ＩＢＭ＿ＳＥＴ−２１は、２１日間のクエリに対する誤字脱字−校正候補のデータである。また、ＬＭパラメータの学習のために使用されたデータは、ＬＭ＿ＳＥＴ−２１＿Ｑ５およびＬＭ＿ＳＥＴ−２０１５＿Ｑ３０によってそれぞれ示した。ＬＭ＿ＳＥＴ−２１＿Ｑ５は、２１日間のクエリに対して累積頻度が５以上のクエリに対するデータを示しており、ＬＭ＿ＳＥＴ−２０１５＿Ｑ３０は、２０１５年までの全体クエリに対して累積頻度が３０以上のクエリに対するデータを示している。テストセットとしては、ｕｎｓｅｅｎランダムサンプリングによる２１，２１９件の誤字脱字−＞正字データを構築した。実施形態との比較のための従来技術としては、最新の学習データを使用することが仮定される。
【０１４０】
下記の表２および表３は、ＩＢＭ  ＭＯＤＥＬ  ２の学習データおよびＬＭ学習データを増加させた場合、カバレージおよび品質が向上するかを示している。表２では、ＬＭ＿ＳＥＴ−２０１５＿Ｑ３０の使用が固定された。表３では、ＩＢＭ＿ＳＥＴ−２１の使用が固定された。
【０１４１】
【表２】
0006261669.tif 000009
【０１４２】
表２および表３の場合すべてにおいて、カバレージの増加および正確度の増加が確認された。下記の表４は、従来技術（ＡＳ−ＩＳ）および実施形態（ＴＯ−ＢＥ）のＳＥＥＮ  ＴＥＳＴの結果を示している。従来技術のシステムおよび実施形態のシステムのモデリングパワー（性能）を比較するために、学習に既に使用されていた（ＳＥＥＮ）データが評価のために使用された。
【０１４３】
【表３】
0006261669.tif 000010
【０１４４】
前記のように、カバレージおよび正確度において、実施形態の場合が従来技術よりもさらに優れることが確認された。
【０１４５】
下記の表５は、従来技術（ＡＳ−ＩＳ）および実施形態（ＴＯ−ＢＥ）のＵＮＳＥＥＮ  ＴＥＳＴの結果を示している。従来技術のシステムおよび実施形態のシステムのモデリングパワー（性能）を比較するために、学習データに存在しない（ＵＮＳＥＥＮ）データが評価のために使用された。
【０１４６】
【表４】
0006261669.tif 000011
【０１４７】
前記のように、実施形態の場合、従来技術に比べてカバレージが約２２２％増加した反面、正確度の減少は２％に過ぎないことが確認された。
【０１４８】
下記の表６および表７は、誤字脱字ではないクエリを正字クエリとしてどのくらい認識するかに対する従来技術および実施形態の比較結果を示している。表６において、評価データ１は、正字と見なされたショッピングドメインＱＣ  ｔｏｐの５，０００件のデータである。表７において、評価データ２は、正字と見なされたＵＮＳＥＥＮ  ＆  ｌｏｗ  ＱＣの地図飲食店名データの１７，０４０件のデータである。
【０１４９】
【表５】
0006261669.tif 000012
【０１５０】
前記のように、従来技術に比べて実施形態の正字認識率がさらに高いことが確認された。
【０１５１】
下記の表８は、誤字脱字校正の従来技術（ＡＳ−ＩＳ）および実施形態（ＴＯ−ＢＥ）の比較結果を示している。
【０１５２】
【表６】
0006261669.tif 000013
【０１５３】
前記のように、校正カバレージにおいて、実施形態の場合が従来技術よりも優れることが確認された。
【０１５４】
例えば、実施形態のシステムは、従来技術のシステムに比べて２乃至３倍の校正カバレージ向上の効果がある反面、校正正確度の劣化はほぼ無いか極めて少ないことが確認された。
【０１５５】
また、実施形態のシステムによると、校正カバレージが従来技術に比べて広くなることから、ユーザが誤字脱字クエリを入力した場合に、正字クエリを再入力しなければならない頻度が少なくなるため、正しい検索結果を出力するためのクエリ入力（クライアントの観点）および検索結果処理（検索サーバの観点）に求められるデータ処理量および計算量を減少させることができる効果がある。さらに、ユーザの端末がモバイル端末の場合に、誤字脱字クエリを入力した場合、正字クエリを再入力しなければならない頻度が少なくなるため、端末のバッテリー節約効果も達成することができる。
【０１５６】
上述した装置は、ハードウェア構成要素、ソフトウェア構成要素、および／またはハードウェア構成要素とソフトウェア構成要素との組み合わせによって実現されてもよい。例えば、実施形態で説明された装置および構成要素は、例えば、プロセッサ、コントローラ、ＡＬＵ（ａｒｉｔｈｍｅｔｉｃ  ｌｏｇｉｃ  ｕｎｉｔ）、デジタル信号プロセッサ、マイクロコンピュータ、ＦＰＧＡ（ｆｉｅｌｄ  ｐｒｏｇｒａｍｍａｂｌｅ  ｇａｔｅ  ａｒｒａｙ）、ＰＬＵ（ｐｒｏｇｒａｍｍａｂｌｅ  ｌｏｇｉｃ  ｕｎｉｔ）、マイクロプロセッサ、または命令を実行して応答することができる様々な装置のように、１つ以上の汎用コンピュータまたは特殊目的コンピュータを利用して実現されてもよい。処理装置は、オペレーティングシステム（ＯＳ）および前記ＯＳ上で実行される１つ以上のソフトウェアアプリケーションを実行してよい。また、処理装置は、ソフトウェアの実行に応答し、データにアクセスし、データを格納、操作、処理および生成してもよい。理解の便宜のために、１つの処理装置が使用されるとして説明される場合もあるが、当業者は、処理装置が複数個の処理要素（ｐｒｏｃｅｓｓｉｎｇ  ｅｌｅｍｅｎｔ）および／または複数種類の処理要素を含んでもよいことが理解できるであろう。例えば、処理装置は、複数個のプロセッサまたは１つのプロセッサおよび１つのコントローラを含んでもよい。また、並列プロセッサ（ｐａｒａｌｌｅｌ  ｐｒｏｃｅｓｓｏｒ）のような、他の処理構成（ｐｒｏｃｅｓｓｉｎｇ  ｃｏｎｆｉｇｕｒａｔｉｏｎ）も可能である。
【０１５７】
ソフトウェアは、コンピュータプログラム、コード、命令、またはこれらのうちの１つ以上の組み合わせを含んでもよく、思うままに動作するように処理装置を構成したり、独立的または集合的に処理装置に命令したりしてよい。ソフトウェアおよび／またはデータは、処理装置に基づいて解釈されたり、処理装置に命令またはデータを提供したりするために、いかなる種類の機械、コンポーネント、物理装置、仮想装置（ｖｉｒｔｕａｌ  ｅｑｕｉｐｍｅｎｔ）、コンピュータ格納媒体または装置、または伝送される信号波（ｓｉｇｎａｌ  ｗａｖｅ）に永久的または一時的に具現化（ｅｍｂｏｄｙ）されてもよい。ソフトウェアは、ネットワークによって接続されたコンピュータシステム上に分散され、分散された状態で格納されても実行されてもよい。ソフトウェアおよびデータは、１つ以上のコンピュータで読み取り可能な記録媒体に格納されてもよい。
【０１５８】
実施形態に係る方法は、多様なコンピュータ手段によって実行可能なプログラム命令の形態で実現されてコンピュータで読み取り可能な媒体に記録されてもよい。前記コンピュータで読み取り可能な媒体は、プログラム命令、データファイル、データ構造などを単独でまたは組み合わせて含んでもよい。前記媒体に記録されるプログラム命令は、実施形態のために特別に設計されて構成されたものであってもよいし、コンピュータソフトウェア当業者に公知な使用可能なものであってもよい。コンピュータで読み取り可能な記録媒体の例としては、ハードディスク、フロッピディスクおよび磁気テープのような磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤのような光媒体、フロプティカルディスク（ｆｌｏｐｔｉｃａｌ  ｄｉｓｋ）のような光磁気媒体およびＲＯＭ、ＲＡＭ、フラッシュメモリなどのようなプログラム命令を格納して実行するように特別に構成されたハードウェア装置が含まれる。プログラム命令の例は、コンパイラによって生成されるもののような機械語コードだけではなく、インタプリタなどを使用してコンピュータによって実行される高級言語コードを含む。上述したハードウェア装置は、実施形態の動作を実行するために１つ以上のソフトウェアモジュールとして動作するように構成されてもよく、その逆も同じである。
【０１５９】
以上のように、実施形態を限定された実施形態と図面に基づいて説明したが、当業者であれば、上述した記載から多様な修正および変形が可能である。例えば、説明された技術が、説明された方法とは異なる順序で実行されたり、および／あるいは、説明されたシステム、構造、装置、回路などの構成要素が、説明された方法とは異なる形態で結合されたりまたは組み合わされたり、他の構成要素または均等物によって対置されたり置換されたとしても、適切な結果を達成することができる。
【０１６０】
したがって、異なる実施形態であっても、特許請求の範囲と均等なものであれば、添付される特許請求の範囲に属する。
【符号の説明】
【０１６１】
１００：クエリ校正システム
２１０：プロセッサ
２２０：校正情報抽出部
２３０：校正結果生成部
２４０：パラメータ取得部
２５０：通信部 
【図１】
0006261669.tif 000016
【図２】
0006261669.tif 000017
【図３】
0006261669.tif 000018
【図４Ａ】
0006261669.tif 000019
【図４Ｂ】
0006261669.tif 000020
【図５】
0006261669.tif 000021
【図６】
0006261669.tif 000022
【図７】
0006261669.tif 000023
【図８】
0006261669.tif 000024
【図９】
0006261669.tif 000025
【図１０】
0006261669.tif 000026
【図１１】
0006261669.tif 000027