(57)【要約】      （修正有）【課題】誤打校正システム及び誤打校正方法を提供する。【解決手段】誤打校正システム１００は、ユーザの入力キーワードを感知するキーワード入力部と、入力キーワードが誤打入力に該当すれば、前記入力キーワードに対応する１つ以上の正打候補キーワードを選択して返還する正打候補決定部１７０と、それぞれの正打候補キーワードを対象として前記入力キーワードとの誤打出現確率を求め、前記誤打出現確率とそれぞれの正打候補キーワードの単語出現確率を利用して前記正打候補キーワードのうち正打キーワードを選択する誤打校正部１８０とを含むように構成される。【選択図】図１
2014194774.tif 000002
【特許請求の範囲】
【請求項１】
入力された誤打キーワードを正打キーワードに補正する誤打校正システムにおいて、
ユーザの入力キーワードを感知するキーワード入力部と；
入力キーワードが誤打入力に該当すれば、前記入力キーワードに対応する１つ以上の正打候補キーワードを選択して返還する正打候補決定部と；
それぞれの正打候補キーワードを対象として前記入力キーワードとの誤打出現確率を求め、前記誤打出現確率とそれぞれの正打候補キーワードの単語出現確率を利用して前記正打候補キーワードのうち正打キーワードを選択する誤打校正部と；を含む、誤打校正システム。
【請求項２】
前記誤打校正部は、前記入力キーワードが、単語出現確率が一定基準以上のキーワードで構成されたキャッシュリストで検索された場合に、前記キャッシュリストで前記入力キーワードに対応するキーワードを正打キーワードとして選択することを特徴とする請求項１に記載の誤打校正システム。
【請求項３】
前記誤打校正部は、それぞれの正打候補キーワードの単語出現確率と前記誤打出現確率を乗算した値が最も大きい正打候補キーワードを正打キーワードとして選択することを特徴とする請求項１に記載の誤打校正システム。
【請求項４】
入力キーワードログからエラーデータを抽出し、前記抽出されたエラーデータの誤打出現確率を計算し、エラーモデルＤＢを生成する誤打出現確率計算部をさらに含むことを特徴とする請求項１に記載の誤打校正システム。
【請求項５】
入力キーワードログから単語出現データを抽出し、前記抽出された単語出現データの単語出現確率を計算し、言語モデルＤＢを生成する単語出現確率計算部をさらに含むことを特徴とする請求項１に記載の誤打校正システム。
【請求項６】
前記正打候補決定部は、単語とこれに対応する発音の対よりなる音声インデックスとの比較を通じて、前記入力キーワードの発音にマッチングされる音声インデックスに対応する単語を正打候補キーワードとして決定することを特徴とする請求項１に記載の誤打校正システム。
【請求項７】
前記正打候補決定部は、
前記入力キーワードを字母に分離し、２字母よりなるバイグラム（ｂｉ−ｇｒａｍ）または３字母よりなるトライグラム（ｔｒｉ−ｇｒａｍ）を生成し、前記生成されたバイグラムまたはトライグラムを単語とこれに対応するバイグラムまたはトライグラムの組合よりなるｎ−グラムインデックスと比較し、マッチングされるバイグラムまたはトライグラムに対応する単語を正打候補キーワードとして決定することを特徴とする請求項１に記載の誤打校正システム。
【請求項８】
前記正打候補決定部は、
前記ｎ−グラムインデックスで前記入力キーワードのバイグラムまたはトライグラムのうち１つ以上を含む単語を検索し、前記検索された単語のバイグラムまたはトライグラム組合と前記入力キーワードのバイグラムまたはトライグラム組合間の類似度を計算し、類似度が高い単語の順に１つ以上の正打候補キーワードを決定することを特徴とする請求項７に記載の誤打校正システム。
【請求項９】
前記正打候補決定部は、前記入力キーワードを言語モデルＤＢと比較し、前記入力キーワードとの編集距離（ｅｄｉｔ  ｄｉｓｔａｎｃｅ）が小さい単語の順に１つ以上の正打候補キーワードを決定し、
前記編集距離は、挿入、交替、削除及び置換別にあらかじめ付与された加重値に基づいて、前記入力キーワードの字母配列と任意の単語の字母配列間の挿入、削除、交替または置換回数による加重値の合計を意味することを特徴とする請求項１に記載の誤打校正システム。
【請求項１０】
入力されたキーワードの誤打校正方法において、
ユーザの入力キーワードを感知する段階と；
入力キーワードが誤打入力に該当すれば、前記入力キーワードに対応する１つ以上の正打候補キーワードを決定する段階と；
それぞれの正打候補キーワードを対象として前記入力キーワードとの誤打出現確率を求める段階と；
前記誤打出現確率とそれぞれの正打候補キーワードの単語出現確率を利用して前記正打候補キーワードのうち正打キーワードを選択する段階と；
前記選択された正打キーワードを返還する段階と；を含む誤打校正方法。
【請求項１１】
前記キーワードを入力される段階後に、
前記入力キーワードが単語出現確率が一定基準以上のキーワードで構成されたキャッシュリストで検索された場合、前記キャッシュリストで前記入力キーワードに対応するキーワードを正打キーワードとして選択する段階をさらに含むことを特徴とする請求項１０に記載の誤打校正方法。
【請求項１２】
前記正打キーワードを選択する段階は、
それぞれの正打候補キーワードの単語出現確率と前記誤打出現確率を乗算した値が最も大きい正打候補キーワードを正打キーワードとして選択する段階であることを特徴とする請求項１０に記載の誤打校正方法。
【請求項１３】
前記キーワードを入力される段階前に、
入力キーワードログからエラーデータを抽出し、前記抽出されたエラーデータの誤打出現確率を計算し、エラーモデルＤＢを生成する段階をさらに含むことを特徴とする請求項１０に記載の誤打校正方法。
【請求項１４】
前記キーワードを入力される段階前に、
入力キーワードログから単語出現データを抽出し、前記抽出された単語出現データの単語出現確率を計算し、言語モデルＤＢを生成する段階をさらに含むことを特徴とする請求項１０に記載の誤打校正方法。
【請求項１５】
前記正打候補キーワードを決定する段階は、
単語とこれに対応する発音の対よりなる音声インデックスとの比較を通じて、前記入力キーワードの発音にマッチングされる発音に対応する単語を正打候補キーワードとして決定する段階を含むことを特徴とする請求項１０に記載の誤打校正方法。
【請求項１６】
前記正打候補キーワードを決定する段階は、
前記入力キーワードを字母に分離し、２字母よりなるバイグラム（ｂｉ−ｇｒａｍ）または３字母よりなるトライグラム（ｔｒｉ−ｇｒａｍ）を生成する段階と；
前記生成されたバイグラムまたはトライグラムを単語とこれに対応するバイグラムまたはトライグラムの組合よりなるｎ−グラムインデックスと比較し、マッチングされるバイグラムまたはトライグラムに対応する単語を正打候補キーワードとして決定する段階と；を含むことを特徴とする請求項１０に記載の誤打校正方法。
【請求項１７】
前記正打候補キーワードとして決定する段階は、前記ｎ−グラムインデックスで前記入力キーワードのバイグラムまたはトライグラムのうち１つ以上を含む単語を検索する段階と；
前記検索された単語のバイグラムまたはトライグラム組合と前記入力キーワードのバイグラムまたはトライグラム組合間の類似度を計算し、類似度が高い単語の順に１つ以上の正打候補キーワードを決定する段階と；を含むことを特徴とする請求項１６に記載の誤打校正方法。
【請求項１８】
前記正打候補キーワードを決定する段階は、
前記入力キーワードを言語モデルＤＢと比較し、前記入力キーワードとの編集距離（ｅｄｉｔ  ｄｉｓｔａｎｃｅ）が小さい単語の順に１つ以上の正打候補キーワードを決定する段階を含み、
前記編集距離は、挿入、削除、交替及び置換別にあらかじめ付与された加重値に基づいて、前記入力キーワードの字母配列と任意の単語の字母配列間の挿入、削除、交替または置換回数による加重値の合計を意味することを特徴とする請求項１０に記載の誤打校正方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索質疑語に対する誤打校正システム及びこれを利用した誤打校正方法に関する。
【背景技術】
【０００２】
誤打校正技術というのは、ユーザが間違った検索語に対して確率によって元々意図した検索語を提示する技術を意味する。一般的に、誤打は、大きく２つに分けられる。１つは、タイピング（ｔｙｐｏｇｒａｐｈｉｃａｌ）誤打であって、キーボード上の配置されたキーの位置に起因する誤打である。もう１つは、認識（ｃｏｇｎｉｔｉｖｅ）誤打であって、単語の正確なスペリングに対する誤解に起因する誤打である。
【０００３】
初期の誤打校正技術は、辞書を基盤とし、辞書で見つけなかった単語を誤打として見なし、辞書内の類似の単語のうち正打候補を選択し、校正する方法が一般的である。
【０００４】
しかし、検索質疑語（ｑｕｅｒｙ）の誤打校正は、従来の辞書に依存する方法では正確な誤打校正効果を得ることができない。なぜなら、検索質疑語は、非常に多様な形態を有していて、インターネット新造語などを含んでいるので、これらすべてを手作業でＤＢ化することは非常に困難である。したがって、このような検索質疑語の誤打校正のためにユーザの検索質疑語ログを蓄積し、これを利用して誤打校正を行う方法を考慮することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】韓国特許公開２０１３−００２０４１８号公報、「文字列推薦方法」
【発明の開示】
【発明が解決しようとする課題】
【０００６】
前述した従来技術の問題点を解決するために、本発明は、ユーザが入力した検索キーワードが誤打と判断されれば、１つ以上の正打候補群を抽出し、これらのうち、ユーザが意図した正打キーワードである確率が最も高いキーワードを選択し、入力された検索キーワードを代替するか、または推薦提示語として提供することができる誤打校正方法を提供する。
【０００７】
本発明の目的は、以上で言及した目的に制限されず、言及されていない他の目的は、下記の記載から明確に理解されることができる。
【課題を解決するための手段】
【０００８】
前記目的を達成するために、本発明の一態様による誤打校正システムは、ユーザの入力キーワードを感知するキーワード入力部と、入力キーワードが誤打入力に該当すれば、前記入力キーワードに対応する１つ以上の正打候補キーワードを選択して返還する正打候補決定部と、それぞれの正打候補キーワードを対象として前記入力キーワードとの誤打出現確率を求め、前記誤打出現確率とそれぞれの正打候補キーワードの単語出現確率を利用して前記正打候補キーワードのうち正打キーワードを選択する誤打校正部とを含む。
【０００９】
ここで、前記誤打校正部は、前記入力キーワードが、単語出現確率が一定基準以上のキーワードで構成されたキャッシュリストで検索された場合に、前記キャッシュリストで前記入力キーワードに対応するキーワードを正打キーワードとして選択することができる。
【００１０】
ここで、前記誤打校正部は、それぞれの正打候補キーワードの単語出現確率と前記誤打出現確率を乗算した値が最も大きい正打候補キーワードを正打キーワードとして選択することができる。
【００１１】
ここで、前記誤打校正システムは、入力キーワードログからエラーデータを抽出し、前記抽出されたエラーデータの誤打出現確率を計算し、エラーモデルＤＢを生成する誤打出現確率計算部をさらに含むことができる。
【００１２】
ここで、前記誤打校正システムは、入力キーワードログから単語出現データを抽出し、前記抽出された単語出現データの単語出現確率を計算し、言語モデルＤＢを生成する単語出現確率計算部をさらに含むことができる。
【００１３】
ここで、前記正打候補決定部は、単語とこれに対応する発音の対よりなる音声インデックスとの比較を通じて、前記入力キーワードの発音にマッチングされる発音に対応する単語を正打候補キーワードとして決定することができる。
【００１４】
ここで、前記正打候補決定部は、前記入力キーワードを字母に分離し、２字母よりなるバイグラム（ｂｉ−ｇｒａｍ）または３字母よりなるトライグラム（ｔｒｉ−ｇｒａｍ）を生成し、前記生成されたバイグラムまたはトライグラムを単語とこれに対応するバイグラムまたはトライグラムの組合よりなるｎ−グラムインデックスと比較し、マッチングされるバイグラムまたはトライグラムに対応する単語を正打候補キーワードとして決定することができる。
【００１５】
ここで、前記正打候補決定部は、前記ｎ−グラムインデックスで前記入力キーワードのバイグラムまたはトライグラムのうち１つ以上を含む単語を検索し、前記検索された単語のバイグラムまたはトライグラム組合と前記入力キーワードのバイグラムまたはトライグラム組合間の類似度を計算し、類似度が高い単語の順に１つ以上の正打候補キーワードを決定することができる。
【００１６】
ここで、前記正打候補決定部は、前記入力キーワードを言語モデルＤＢと比較し、前記入力キーワードとの編集距離（ｅｄｉｔ  ｄｉｓｔａｎｃｅ）が小さい単語の順に１つ以上の正打候補キーワードを決定することができ、ここで、前記編集距離は、挿入、交替、削除及び置換別にあらかじめ付与された加重値に基づいて、前記入力キーワードの字母配列と任意の単語の字母配列間の挿入、削除、交替または置換回数による加重値の合計を意味する。
【００１７】
また、本発明の他の態様による誤打校正方法は、ユーザの入力キーワードを感知する段階と、入力キーワードが誤打入力に該当すれば、前記入力キーワードに対応する１つ以上の正打候補キーワードを決定する段階と、それぞれの正打候補キーワードを対象として前記入力キーワードとの誤打出現確率を求める段階と、前記誤打出現確率とそれぞれの正打候補キーワードの単語出現確率を利用して前記正打候補キーワードのうち正打キーワードを選択する段階と、前記選択された正打キーワードを返還する段階とを含む。
【００１８】
ここで、前記キーワードを入力される段階後に、前記入力キーワードが、単語出現確率が一定基準以上のキーワードで構成されたキャッシュリストで検索された場合、前記キャッシュリストで前記入力キーワードに対応するキーワードを正打キーワードとして選択する段階をさらに含むことができる。
【００１９】
ここで、前記正打キーワードを選択する段階は、それぞれの正打候補キーワードの単語出現確率と前記誤打出現確率を乗算した値が最も大きい正打候補キーワードを正打キーワードとして選択する段階であることができる。
【００２０】
ここで、前記キーワードを入力される段階前に、入力キーワードログからエラーデータを抽出し、前記抽出されたエラーデータの誤打出現確率を計算し、エラーモデルＤＢを生成する段階をさらに含むことができる。
【００２１】
ここで、前記キーワードを入力される段階前に、入力キーワードログから単語出現データを抽出し、前記抽出された単語出現データの単語出現確率を計算し、言語モデルＤＢを生成する段階をさらに含むことができる。
【００２２】
ここで、前記正打候補キーワードを決定する段階は、単語とこれに対応する発音の対よりなる音声インデックスとの比較を通じて、前記入力キーワードの発音にマッチングされる発音に対応する単語を正打候補キーワードとして決定する段階を含むことができる。
【００２３】
ここで、前記正打候補キーワードを決定する段階は、前記入力キーワードを字母に分離し、２字母よりなるバイグラム（ｂｉ−ｇｒａｍ）または３字母よりなるトライグラム（ｔｒｉ−ｇｒａｍ）を生成する段階と、前記生成されたバイグラムまたはトライグラムを単語とこれに対応するバイグラムまたはトライグラムの組合よりなるｎ−グラムインデックスと比較し、マッチングされるバイグラムまたはトライグラムに対応する単語を正打候補キーワードとして決定する段階とを含むことができる。
【００２４】
ここで、前記正打候補キーワードとして決定する段階は、前記ｎ−グラムインデックスで前記入力キーワードのバイグラムまたはトライグラムのうち１つ以上を含む単語を検索する段階と、前記検索された単語のバイグラムまたはトライグラム組合と前記入力キーワードのバイグラムまたはトライグラム組合間の類似度を計算し、類似度が高い単語の順に１つ以上の正打候補キーワードを決定する段階とを含むことができる。
【００２５】
ここで、前記正打候補キーワードを決定する段階は、前記入力キーワードを言語モデルＤＢと比較し、前記入力キーワードとの編集距離（ｅｄｉｔ  ｄｉｓｔａｎｃｅ）が小さい単語の順に１つ以上の正打候補キーワードを決定する段階を含むことができ、この際、前記編集距離は、挿入、削除、交替及び置換別にあらかじめ付与された加重値に基づいて、前記入力キーワードの字母配列と任意の単語の字母配列間の挿入、削除、交替または置換回数による加重値の合計を意味することができる。
【００２６】
上記目的を達成するための具体的な事項は、添付の図面と共に詳細に後述された実施例を参照すれば明確になる。
【００２７】
しかし、本発明は、以下で開示される実施例に限定されるものではなく、互いに異なる多様な形態で構成されることができ、本実施例は、本発明の開示が完全になるようにし、本発明の属する技術分野における通常の知識を有する者に発明の範疇を完全に知らせるために提供されるものである。
【発明の効果】
【００２８】
本発明によれば、検索キーワードに対してもユーザの検索キーワードログを利用して高い正確度で誤打校正を行うことができるという効果がある。
【図面の簡単な説明】
【００２９】
【図１】本発明の一実施例による誤打校正システムの詳細構成を示すブロック図である。
【図２】本発明の一実施例による誤打校正システムにおいてユーザの検索クエリーログを利用してエラーモデルＤＢ及び言語モデルＤＢを生成する方法を示す流れ図である。
【図３ａ】本発明の一実施例による誤打校正システムにおいてユーザの検索クエリーログを利用して言語モデルＤＢを生成し、単語出現確率を計算する過程を説明するための図である。
【図３ｂ】本発明の一実施例による誤打校正システムにおいてユーザの検索クエリーログを利用して言語モデルＤＢを生成し、単語出現確率を計算する過程を説明するための図である。
【図４ａ】本発明の一実施例による誤打校正システムにおいてユーザの検索クエリーログを利用してエラーモデルＤＢを生成し、音節誤打出現確率を計算する過程を説明するための図である。
【図４ｂ】本発明の一実施例による誤打校正システムにおいてユーザの検索クエリーログを利用してエラーモデルＤＢを生成し、音節誤打出現確率を計算する過程を説明するための図である。
【図４ｃ】本発明の一実施例による誤打校正システムにおいてユーザの検索クエリーログを利用してエラーモデルＤＢを生成し、音節誤打出現確率を計算する過程を説明するための図である。
【図４ｄ】本発明の一実施例による誤打校正システムにおいてユーザの検索クエリーログを利用してエラーモデルＤＢを生成し、音節誤打出現確率を計算する過程を説明するための図である。
【図４ｅ】本発明の一実施例による誤打校正システムにおいてユーザの検索クエリーログを利用してエラーモデルＤＢを生成し、音節誤打出現確率を計算する過程を説明するための図である。
【図４ｆ】本発明の一実施例による誤打校正システムにおいてユーザの検索クエリーログを利用してエラーモデルＤＢを生成し、音節誤打出現確率を計算する過程を説明するための図である。
【図５】本発明の一実施例による誤打校正システムにおいてユーザの検索キーワードに対して誤打校正を行う過程を示す流れ図である。
【図６ａ】本発明の一実施例による誤打校正システムにおいて入力された誤打キーワードに関する正打候補キーワードを決定する過程を説明するための図である。
【図６ｂ】本発明の一実施例による誤打校正システムにおいて入力された誤打キーワードに関する正打候補キーワードを決定する過程を説明するための図である。
【図６ｃ】本発明の一実施例による誤打校正システムにおいて入力された誤打キーワードに関する正打候補キーワードを決定する過程を説明するための図である。
【図６ｄ】本発明の一実施例による誤打校正システムにおいて入力された誤打キーワードに関する正打候補キーワードを決定する過程を説明するための図である。
【発明を実施するための形態】
【００３０】
本発明は、多様な変更を行うことができ、様々な実施例を有することができるところ、特定実施例を図面に例示し、これを詳細な説明を通じて詳しく説明する。しかし、これは、本発明を特定の実施形態に対して限定しようとするものではなく、本発明の思想及び技術範囲に含まれるすべての変更、均等物ないし代替物を含むものと理解されなければならない。
【００３１】
本発明を説明するに際して、関連した公知技術に対する具体的な説明が本発明の要旨を不明にすることができると判断される場合、その詳細な説明を省略する。また、本明細書の説明過程で利用される数字（例えば、第１、第２など）は、１つの構成要素を他の構成要素と区分するための識別記号に過ぎない。
【００３２】
また、本明細書で、１つの構成要素が他の構成要素と「連結される」、または「接続される」などで言及されたとき、前記１つの構成要素が前記他の構成要素と直接連結されるか、または直接接続されることもできるが、特に反対される記載が存在しない以上、中間に他の構成要素を媒介で連結されるかまたは接続されることもできると理解するべきである。
【００３３】
以下、添付の図面を参照して本発明の実施のための具体的な内容を説明する。
【００３４】
図１は、本発明の一実施例による誤打校正システムの構成を示している。図１に示されたように、誤打校正システム１００は、入力部１１０、単語出現確率計算部１２０、誤打出現確率計算部１３０、インデックスＤＢ  １４０、言語モデルＤＢ  １５０、エラーモデルＤＢ  １６０、正打候補決定部１７０及び誤打校正部１８０を含むことができる。
【００３５】
入力部１１０は、ユーザの検索キーワード入力を感知し、これに対応する入力キーワードデータを返還する。以下、入力部１１０によって返還された入力キーワードデータを簡単に入力キーワードと称する。
【００３６】
検索された入力キーワードは、検索ログ（以下、入力キーワードログ）に格納され、言語モデルＤＢ  １５０及びエラーモデルＤＢ  １６０の構築のための基礎資料として使用される。言語モデルＤＢ  １５０及びエラーモデルＤＢ  １６０の生成方法は、図２に示されている。
【００３７】
単語出現確率計算部１２０は、入力キーワードログから単語出現データを抽出し、抽出された単語出現データの単語出現確率を計算し、言語モデルＤＢ  １５０を生成する。
【００３８】
図３には、このような抽出された単語出現データとその単語出現確率を含む言語モデルＤＢ１５０の構造の一例が示されている。例えば、一定期間中に蓄積された不特定ユーザに対する入力キーワードログが図３（ａ）に示された通りであると仮定すれば、当該ログで全体クエリー登場回数は１４回になり、「しょうじょじだい」キーワードの出現回数は、１回になり、「ネーんバー」キーワードの出現回数は、２回になる。
【００３９】
単語出現確率計算部１２０は、入力キーワード別に出現回数（検索頻度）を集計し、単語出現データを生成し（Ｓ２２２）、それぞれの入力キーワードに対して単語出現確率を計算する（Ｓ２２４）。ここで、単語出現確率Ｐ（）は、下記の式１によって計算されることができる。
【００４０】
（式１）Ｐ（キーワード）＝（キーワード検索頻度）／（全体入力キーワードの検索頻度の和）
【００４１】
図３（ａ）に例示された入力キーワードログを利用して単語出現確率を求める場合、「しょうじょじだい」キーワードの単語出現確率Ｐ（しょうじょじだい）は、１／１４＝０．０７１４になり、「ネーんバー」キーワードの単語出現確率Ｐ（ネーんバー）は、２／１４＝０．１４２になる。
【００４２】
このように生成された入力キーワード別に単語出現確率を利用して誤打キーワードに対する正打候補キーワードが２個以上存在する場合、単語出現確率がさらに高い正打候補キーワードに加算点を付与することができる。
【００４３】
生成された単語出現データは、図３（ｂ）に示されたように、言語モデルＤＢ  １５０に格納される（Ｓ２２６）。この際、単語出現データには、単語出現確率の基準になるログ集計期間に関するデータが含まれることができる。
【００４４】
さらに図１を参照すれば、誤打出現確率計算部１３０は、入力キーワードログからエラーデータを抽出し、抽出されたエラーデータの誤打出現確率を計算し、エラーモデルＤＢ  １６０を生成する。
【００４５】
図４ａ〜図４ｆには、このような抽出されたエラーデータとその音節誤打出現確率（以下、誤打出現確率）を含むエラーモデルＤＢ  １６０の構造の一例が示されている。例えば、一定期間中に不特定ユーザが検索した入力キーワードログが図４ａに示されたものなら、誤打出現確率計算部１３０は、同一ユーザによってあらかじめ設定された短い時間、例えば２〜３秒間にクエリーされた入力キーワードを抽出する。抽出された結果は、図４ｂのように先行キーワードと後行キーワードの対よりなることができる。その後、誤打出現確率計算部１３０は、先行キーワードと後行キーワードが互いに類似なレコードを抽出する。例えば、図４ｃのように、先行キーワードである「ネーんバー」と後行キーワードである「ネーバー」は、１字が異なるので、あらかじめ設定された基準によって互いに類似なキーワードと判断されることができる。同様に、先行キーワードである「かげっこ」と後行キーワードである「かけっこ」は、互いに類似なキーワードと判断されることができる。
【００４６】
このように互いに類似なキーワード対を有するレコードが抽出されれば、誤打出現確率計算部１３０は、クエリーを発行したユーザに関係なく、同一のキーワード対を有するレコードの個数を集計する。集計された結果は、図４ｄに示されている。このように抽出されたデータグループをエラーデータと言う（Ｓ２１２）。
【００４７】
その後、誤打出現確率計算部１３０は、それぞれのエラーデータに対して誤打出現確率を計算する（Ｓ２１４）。例えば、ここで、誤打出現確率Ｐ（正打音節｜誤打音節）は、下記の式２によって計算されることができる。
【００４８】
（式２）Ｐ（正打音節｜誤打音節）＝（当該誤打類型頻度の和）／（全体誤打類型頻度の和）
【００４９】
ここで、誤打類型には、置換、追加、削除及び交替が該当し、当該誤打類型が置換である場合、Ｐ（正打音節｜誤打音節）＝（当該置換頻度の和）／（全体置換頻度の和）になり、当該誤打類型が追加の場合には、Ｐ（正打音節｜誤打音節）＝（当該追加頻度の和）／（全体追加頻度の和）になる。
【００５０】
前記４つの誤打類型の一例が図４ｅに示されている。置換は、「かけっこ」を「かげっこ」に入力した場合のように、正打音節「け」が誤打音節「げ」に置換された形態の誤打を意味する。追加は、「ネーバー」を「ネーんバー」に入力した場合のように、「ん」のような誤字が追加に入力された形態の誤打を意味する。削除は、「ネーバー」の代わりに、「ネバー」を入力した場合のように、一部の音節が間違いで未入力された形態の誤打を意味する。そして、交替は、「ネーバー」を「―ネバー」に入力した場合のように、キー入力の手順が変わった形態の誤打を意味する。
【００５１】
このように、誤打出現確率計算部１３０は、それぞれの正打音節｜誤打音節に対して誤打出現確率Ｐ（正打音節｜誤打音節）を計算し、これをエラーモデルＤＢ  １６０に格納する（Ｓ２１６）。このようなエラーモデルＤＢ  １６０の一例が図４ｆに示されている。
【００５２】
正打候補決定部１７０は、入力キーワードが誤打入力に該当すれば、これと類似な予測される１つ以上の正打候補キーワードを選択して返還する。この際、正打候補決定部１７０は、正打候補キーワードを決定するためにインデックスＤＢ  １４０を利用することができる。インデックスＤＢ  １４０の構成例は、図６に示されている。
【００５３】
ここで、正打候補決定部１７０は、正打候補キーワードを選択するために次のような方法を適切に組み合わせて利用することができる。
【００５４】
一番目の方法は、音声学的方法であって、検索者が原本文字の発音を知っているが、正確なスペリングを知らない場合に利用されることができる。例えば、ユーザが意図した正打キーワードが「アインシュタイン」の英語単語である「ｅｉｎｓｔｅｉｎ」であり、ユーザが検索のために入力した誤打キーワードが「アインシュタイン」を音が出る通り表示した「ａｉｎｓｕｔａｉｎ」であることができる。
【００５５】
この場合、正打候補決定部１７０は、入力キーワード「ａｉｎｓｕｔａｉｎ」をインデックスＤＢ  １４０で検索し、同一の音声インデックスを有する単語を取得することができる。図６（ａ）で、入力キーワード「ａｉｎｓｕｔａｉｎ」と同一の音声インデックスを有する単語は、「ｅｉｎｓｔｅｉｎ」であり、その出現確率Ｐ（ｅｉｎｓｔｅｉｎ）＝０．０２３であることが分かる。もし候補が２個以上の場合には、当該入力キーワード言語類型（すなわち、韓国語、英語、日本語など）を考慮して当該ユニコードブロックで出現確率が高いものを返還することができる。
【００５６】
前記音声インデックスの生成は、インデックス生成部（図示せず）によって行われることができ、インデックス生成部は、ｓｏｕｎｄｅｘまたはメタホンアルゴリズムを利用して前記音声インデックスを生成し、これをインデックスＤＢ  １４０に格納することができる。
【００５７】
二番目の方法は、ｎ−グラム（ｇｒａｍ）インデックスを利用する方法であって、ユーザの入力キーワードが全般的には正打入力とマッチングされるが、部分的に誤打を含んでいる場合に利用されることができる。
【００５８】
正打候補決定部１７０は、まず、入力キーワードを字母に分離し、分離した  字母を順に２字母ずつ組み合わせてバイグラム（ｂｉ−ｇｒａｍ）を生成するか、または順に３字母ずつ組み合わせてトライグラム（ｔｒｉ−ｇｒａｍ）を生成する。例えば、入力キーワードが
2014194774.tif 000003
の場合に、
2014194774.tif 000004
は、図６（ｂ）のように、
2014194774.tif 000005
に字母分離し、これを順に２字母ずつ組み合わせて図６（ｃ）のように
2014194774.tif 000006
の３つのバイグラムが生成されることができる。
【００５９】
参照として、正打候補決定部１７０は、入力キーワードの長さによってバイグラムまたはトライグラムの生成可否を決定することができる。例えば、入力キーワードがあらかじめ設定された音節以下と短い場合には、バイグラムを使用し、あらかじめ設定された音節より長い場合には、トライグラムを使用してインデックシングするようにすることができる。
【００６０】
その後、正打候補決定部１７０は、入力キーワードのバイグラムまたはトライグラムをインデックスＤＢ  １４０のｎ−グラムインデックスと比較し、マッチングされる１つ以上の単語を取得することができる。図６（ｄ）を参照すれば、ユーザが
2014194774.tif 000007
と入力すれば、正打候補決定部１７０は、総３個のバイグラムクエリー
2014194774.tif 000008
を生成する。前記クエリー結果は、次の通りである。
2014194774.tif 000009
【００６１】
前記３個のバイグラムクエリーに対して
2014194774.tif 000010
が３回マッチングされ、
2014194774.tif 000011
が２回マッチングされた。この際、検索されたキーワードで
2014194774.tif 000012
は、
2014194774.tif 000013
の３個のバイグラムを含んでおり、
2014194774.tif 000014
は、
2014194774.tif 000015
の９個のバイグラムを含んでいる。
【００６２】
正打候補決定部１７０は、下記の式３を利用して入力キーワードとそれぞれの検索されたキーワードとの類似度ｒ（）を計算する。
【００６３】
（式３）ｒ（入力キーワード、検索されたキーワード）＝｜Ｓ（入力キーワード）∩Ｓ（検索されたキーワード）｜／｜Ｓ（入力キーワード）∪Ｓ（検索されたキーワード）｜
【００６４】
ここで、Ｓ（）は、キーワードに含まれたバイグラムの集合を意味する。
【００６５】
前記入力キーワード
2014194774.tif 000016
と検索された
2014194774.tif 000017
の
2014194774.tif 000018
であり、入力キーワード
2014194774.tif 000019
と検索されたキーワード
2014194774.tif 000020
の
2014194774.tif 000021
の類似度を有するようになる。したがって、ユーザが
2014194774.tif 000022
を検索したとき、
2014194774.tif 000023
が
2014194774.tif 000024
よりさらに入力キーワード
2014194774.tif 000025
と類似していることが分かる。
【００６６】
他の例として、ユーザが意図した
2014194774.tif 000026
の代わりに、
2014194774.tif 000027
を入力した場合を見れば、入力キーワード
2014194774.tif 000028
のバイグラムは、
2014194774.tif 000029
の４個であり、したがって、４個のバイグラムクエリーが発行される。この場合、正打候補決定部１７０は、図６（ｄ）のバイグラムインデックスとの比較を通じて
2014194774.tif 000030
及び
2014194774.tif 000031
を返還するようになり、それぞれの類似度は、３／４及び２／１１になるので、入力された誤打キーワード
2014194774.tif 000032
に対して
2014194774.tif 000033
を正打候補キーワードとして返還することができる。この際、返還される正打候補キーワードは、１つ以上であることができる。
【００６７】
一方、ｎ−グラムインデックスの生成時に最前トークンと最後トークンを区別し、検索される対象のインデックス数を減らすことができる。例えば、
2014194774.tif 000034
の場合に
2014194774.tif 000035
のように、最前トークンは、接頭に＿を付け、最後トークンは、接未に＿を付けて生成すれば、ユーザの入力キーワードの中間に
2014194774.tif 000036
が来ても、最前トークン
2014194774.tif 000037
【００６８】
前述したｎ−グラムインデックスを利用する方法は、すべての言語に共通的に適用することができる。一例として、英語単語“ｔｒｅｅ”の場合に、“ｔｒｅｅ”は、‘ｔ’、‘ｒ’、‘ｅ’、‘ｅ’に字母分離し、これを順に２字ずつ組み合わせて‘ｔｒ’、‘ｒｅ’、‘ｅｅ’のように３個のバイグラムが生成されることができる。同様に、英語単語“ｔｒｅｃｏｒｄｅ”の場合には、‘ｔｒ’、‘ｒｅ’、‘ｅｃ’、‘ｃｏ’、‘ｏｒ’、‘ｒｄ’、‘ｄｅ’の７個のバイグラムが生成されることができる。もしユーザが“ｔｒｅｅ”と入力すれば、正打候補決定部１７０は、総３個のバイグラムクエリー（‘ｔｒ’、‘ｒｅ’、‘ｅｅ’）を生成する。この３個のバイグラムクエリーに対して“ｔｒｅｅ”は、３回がマッチングされ、“ｔｒｅｃｏｄｅ”は、２回がマッチングされる。
【００６９】
したがって、正打候補決定部１７０は、式３を利用して入力キーワードとそれぞれの検索されたキーワードとの類似度ｒを計算する。すなわち、前述した例で、入力キーワード“ｔｒｅｅ”及び検索された“ｔｒｅｅ”の類似度は、ｒ（ｔｒｅｅ、ｔｒｅｅ）＝３／３＝１になり、入力キーワード“ｔｒｅｅ”及び検索された“ｔｒｅｃｏｒｄｅ”の類似度は、ｒ（ｔｒｅｅ、ｔｒｅｃｏｒｄｅ）＝２／８＝０．２５になる。したがって、ユーザが“ｔｒｅｅ”を検索したとき、“ｔｒｅｅ”が“ｔｒｅｃｏｒｄｅ”よりさらに入力キーワードに類似していることが分かる。また、ｎ−グラムインデックス生成時にトークンを利用することによって、索引候補を大きく減らすことができる。
【００７０】
また、日本語の場合にも、同一の方式でｎ−グラムインデックスを生成することができる。日本語単語「ひゃっかてん」の場合に、「ひゃっかてん」は、「ひ」、「ゃ」、「っ」、「か」、「て」、「ん」に字母分離し、これを順に２字ずつ組み合わせて「ひゃ」、「ゃっ」、「っか」、「かて」、「てん」 のように、５個のバイグラムが生成されることができる。同様に、日本語単語「ひゃっかそうめい」の場合には、「ひゃ」、「ゃっ」、「っか」、「かそ」、「そう」、「うめ」 、「めい」の７個のバイグラムが生成されることができる。
【００７１】
もしユーザが「ひゃっかて」と入力すれば、正打候補決定部１７０は、総４個のバイグラムクエリー（「ひゃ」、「ゃっ」、「っか」、「かて」 ）を生成する。この４個のバイグラムクエリーに対して「ひゃっかてん」は、４回がマッチングされ、「ひゃっかそうめい」は、３回がマッチングされる。したがって、正打候補決定部１７０は、式３を利用して入力キーワードとそれぞれの検索されたキーワードとの類似度ｒを計算する。
【００７２】
すなわち、前述した例で、入力キーワード「ひゃっかて」及び検索された「ひゃっかてん」の類似度は、ｒ（ひゃっかて、ひゃっかてん）＝４／５＝０．８になり、入力キーワード「ひゃっかて」及び検索された「ひゃっかそうめい」の類似度は、ｒ（ひゃっかて、ひゃっかそうめい）＝３／８＝０．３７５になる。したがって、ユーザが「ひゃっかて」を検索したとき、「ひゃっかてん」が「ひゃっかそうめい」よりさらに入力キーワードに類似していることが分かる。また、ｎ−グラムインデックス生成時にトークンを利用することによって、索引候補を大きく減らすことができる。
【００７３】
他の方法は、編集距離を利用する方法である。ここで、編集距離（ｅｄｉｔ  ｄｉｓｔａｎｃｅ）は、挿入、交替、削除及び置換別にあらかじめ付与された加重値に基づいて入力キーワードの字母配列と任意の単語の字母配列間の挿入、削除、交替または置換回数によって加重値を加えて合算された値を意味する。
【００７４】
正打候補決定部１７０は、入力キーワードを言語モデルＤＢ  １５０と比較し、前記入力キーワードとの編集距離が小さい単語の順に１つ以上の正打候補キーワードを決定する。例えば、入力キーワード「じゃがい」の字母配列「じ、ゃ、が、い」と大象キーワード「じゃがいも」の字母配列「じ、ゃ、が、い、も」は、「も」の挿入が生じるので、挿入に該当する加重値が加わるようになる。この際、編集距離が大きいほど、単語が互いに連関性が低下すると判断することができる。
【００７５】
誤打校正部１８０は、正打候補決定部１７０で決定されて返還された１つ以上の正打候補キーワードを対象として前記入力キーワードとの誤打出現確率を求め、当該誤打出現確率とそれぞれの正打候補キーワードの単語出現確率を利用して前記正打候補キーワードのうち正打キーワードを選択する。
【００７６】
具体的に、誤打校正部１８０は、以下の式４のように、それぞれの正打候補キーワードの単語出現確率と誤打出現確率を乗算した値が最も大きいキーワードを正打キーワードとして選択することができる。
【００７７】
（式４）変換点数＝ＭＡＸ（正打候補キーワード１〜ｎまでに対してＰ（正打候補キーワードｎ）＊Ｐ（正打音節｜誤打音節））
【００７８】
例えば、図４（ｆ）で「ヘーバー」という誤打は、「ネーバー」という正打候補キーワードも受けることができるが、「セーバー」という正打候補キーワードも受けることができる。Ｐ（ネ｜ヘ）＝０．００１２であり、Ｐ（セ｜ヘ）＝０．０４２であるので、ヘ→セの校正がヘ→ネの校正より校正確率が高くて、「ネーバー」、「セーバー」及び「ヘーバー」の単語出現確率がそれぞれ０．０８、０．０００２及び０．０００００１と例示すれば、「ネーバー」、「セーバー」及び「ヘーバー」の変換点数は、それぞれ０．００１２＊０．０８＝０．００００１６、０．０４２＊０．０００２＝０．０００００８４及び０．０００００１＊１＝０．０００００１になる。
【００７９】
したがって、入力キーワードが「ヘーバー」の場合に、誤打校正部１８０は、最終的に「ネーバー」を正打キーワードとして決定して返還することができる。
【００８０】
一方、誤打校正システムのロジッグに該当するものは、正打ではなく、誤打と予測される単語であるから、正打と確実視される単語に対しては、誤打校正作業を行わないようにすることが好ましい。このために、誤打校正部１８０は、出現確率が高いキーワードを任意の個数分だけあらかじめキャッシュしておいて、入力キーワードをキャッシュされたキーワードと比較し、キャッシュ内に入力キーワードが格納されていれば、当該キーワードにマッチングされてキャッシングされた正打キーワードを抽出して返還することができる。
【００８１】
図５は、本発明の一実施例による誤打校正方法を示す流れ図である。
【００８２】
図５に示されたように、ユーザが質疑キーワードを入力すれば（Ｓ３０２）、誤打校正部１８０は、入力されたキーワードが韓国語／英語変換誤打（あるいは、韓国語／日本語変換誤打、日本語／英語変換誤打）の場合に（Ｓ３０４）、入力された誤打データを変換して修正する（Ｓ３０６）。
【００８３】
一方、誤打校正部１８０は、出現確率が高いキーワードをキャッシュに格納して管理し、キーワードが入力されれば、当該キーワードをキャッシュと比較し、マッチングされるキーワードが発見された場合に（Ｓ３０８）、これに対応する正打キーワードをキャッシュで取得して返還する（Ｓ３１０）。
【００８４】
その後、正打候補決定部１７０は、前記説明した過程を利用して誤打入力された入力キーワードに対して正打候補キーワードを決定し、これを返還する（Ｓ３１２）。
【００８５】
その後、誤打校正部１８０は、返還された１つ以上の正打候補キーワードを対象として前記入力キーワードとの誤打出現確率を求め（Ｓ３１４）、それぞれの正打候補キーワードの単語出現確率を求めた後（Ｓ３１６）、求められた誤打出現確率と単語出現確率を乗算した値が最も大きい正打候補キーワードを選択する（Ｓ３１８）。選択された正打候補キーワードは、最終的に正打キーワードとして決定され、ユーザ入力窓を通じて推薦提示語として提示されるか、またはユーザ入力窓に入力された入力キーワードを校正することができる（Ｓ３２０）。
【００８６】
以上のような構成を通じて、本発明の誤打校正システム１００は、検索キーワードに対してもユーザの検索キーワードログを利用して高い正確度で誤打校正を行うことができる。
【００８７】
以上の説明は、本発明の技術思想を例示的に説明したものに過ぎず、本発明の属する技術分野における通常の知識を有する者なら本発明の本質的な特性を逸脱しない範囲で多様な修正及び変形が可能である。したがって、本発明に開示された実施例は、本発明の技術思想を限定するためのものではなく、説明するためのものであって、このような実施例によって本発明の技術思想の範囲が限定されるものではない。
【００８８】
本発明の保護範囲は、下記の請求範囲によって解釈されなければならないし、それと同等な範囲内にあるすべての技術思想は、本発明の権利範囲に含まれるものと解釈されなければならないでしょう。
【図１】
2014194774.tif 000038
【図２】
2014194774.tif 000039
【図３ａ】
2014194774.tif 000040
【図３ｂ】
2014194774.tif 000041
【図４ａ】
2014194774.tif 000042
【図４ｂ】
2014194774.tif 000043
【図４ｃ】
2014194774.tif 000044
【図４ｄ】
2014194774.tif 000045
【図４ｅ】
2014194774.tif 000046
【図４ｆ】
2014194774.tif 000047
【図５】
2014194774.tif 000048
【図６ａ】
2014194774.tif 000049
【図６ｂ】
2014194774.tif 000050
【図６ｃ】
2014194774.tif 000051
【図６ｄ】
2014194774.tif 000052