(57)【特許請求の範囲】
【請求項１】
検索結果を順位付けるための方法であって、
クエリ文字列を受信し、
クエリ文字列に関連する対応する複数のターゲット文字列を含む複数の検索結果を取得し、
前記クエリ文字列と、前記複数のターゲット文字列のそれぞれを分割し、
複数の組み合わせを形成するために、前記クエリ文字列内の分割部分と、各前記ターゲット文字列内の分割部分とを対にし、
単語の組み合わせと各単語の組み合わせに対する重みとのマッピングに基づいて、前記複数の組み合わせに対応する複数の重みを取得し、重みは単語の組み合わせに含まれる単語間の意味的相関の指標となり、
前記複数のターゲット文字列それぞれに対応する前記重みに基づいて重み付けされた単語長を決定し、
前記複数のターゲット文字列を前記複数のターゲット文字列のそれぞれについて重み付けされた単語長に基づいて順位付けること、
を備える、方法。
【請求項２】
請求項１に記載の方法において、単語の組み合わせと各単語の組み合わせに対する重みとの前記マッピングは、予め決定されている、方法。
【請求項３】
請求項２に記載の方法において、単語の組み合わせと各単語の組み合わせに対する重みとの前記マッピングは、
１組の統計サンプルを取得し、
前記１組の統計サンプルから第１の単語および第２の単語を選択し、前記第１および第２の単語の両方が前記統計サンプル内で出現する回数をＣ（前記第１の単語、前記第２の単語）としてカウントし、
前記第２の単語が前記統計サンプル内で出現する回数をΣＣ（Ｙi、前記第２の単語）としてカウントし、Ｙiは前記第２の単語と一緒に出現するそれぞれの前記単語を表し、
前記第１および第２の単語の両方が前記統計サンプル内で出現する回数と、前記第２の単語が前記統計サンプル内で出現する回数とに基づいて、前記第２の単語が出現する条件のもとでの前記第１の単語の出現確率Ｐを計算し、
前記第２の単語の検索の際に、前記第１および第２の単語の間の意味的相関の指標となる重みをＷ＝１−Ｐによって決定し、Ｗは前記重みであり、Ｐは前記第２の単語が出現する前記条件のもとでの前記第１の単語の前記確率であり、
前記統計サンプル内の単語の組み合わせの間の意味的相関の指標となる前記重みを決定するために、前記選択、カウント、計算、および、決定を繰り返し、
前記単語の組み合わせと各単語の組み合わせに対する重みとの前記マッピングを格納すること、によって決定される、方法。
【請求項４】
請求項３に記載の方法であって、前記統計サンプルは、ウェブページ、ユーザ検索ログ、または、ユーザ選択ログから取得される、方法。
【請求項５】
請求項１に記載の方法であって、
前記重み付けされた単語長は、最短スライディングウィンドウの前記重み付けされた単語長であり、
前記重みから前記重み付けされた単語長を決定して、それぞれの前記ターゲット文字列を順位付けすることは、
前記クエリ文字列の分割部分に対する前記ターゲット文字列の分割部分の最小重みは、前記ターゲット文字列内の各分割部分を用いて、前記複数の組み合わせをグループ化し、各グループ内における最小の重みをそれぞれ決定して求められ、または、前記ターゲット文字列の分割部分に対する前記クエリ文字列の分割部分の最小重みは、前記クエリ文字列の各分割部分を用いて、前記複数の組み合わせをグループ化し、各グループ内における最小の重みをそれぞれ決定して求められ、
前記最小重みに基づいて、ターゲット文字列について前記最短スライディングウィンドウの前記重み付けされた長さを計算し、
前記ターゲット文字列の前記最短スライディングウィンドウの前記重み付けされた長さを比較すること、を含み、
重み付けされた長さが短いターゲット文字列が、重み付けされた長さが長いターゲット文字列よりも高く順位付けされる、方法。
【請求項６】
請求項５に記載の方法であって、前記最小重みに基づいて、ターゲット文字列について前記最短スライディングウィンドウの前記重み付けされた長さを計算することは、以下の式に基づいており、
【数４】
0005597255.tif 000012
Ｗは重みを表し、Ｔiはターゲット文字列のｉ番目の分割部分を表し、ｋおよびｈはそれぞれ前記ターゲット文字列の前記最短スライディングウィンドウの開始位置および終了位置を表し、Ｑjは前記クエリ文字列のｊ番目の分割部分を表し、ｍは前記クエリ文字列の分割部分の数を表す、方法。
【請求項７】
検索結果を順位付けするための方法であって、
クエリ文字列を受信し、
クエリ文字列に関連する対応する複数のターゲット文字列を含む複数の検索結果を取得し、
前記クエリ文字列と、前記複数のターゲット文字列のそれぞれを分割し、
単語の組み合わせと単語の組み合わせに対する重みとのマッピングに基づいて、前記クエリ文字列の分割部分に対する各挿入単語の最小重みを決定し、
単語の組み合わせと単語の組み合わせに対する重みとのマッピングに基づいて、前記ターゲット文字列の分割部分に対する各削除単語の最小重みを決定し、
各挿入単語の前記最小重みおよび各削除単語の前記最小重みに少なくとも部分的に基づいて総編集距離を決定し、
前記総編集距離に基づいて前記ターゲット文字列を順位付けること、
を備える、方法。
【請求項８】
請求項７に記載の方法であって、前記クエリ文字列の分割部分に対する各挿入単語の最小重みを決定することは、
単語の組み合わせと単語の組み合わせに対する重みとの前記マッピングに基づいて、前記クエリ文字列の分割部分に対する前記挿入単語の複数の重みを決定し、
前記クエリ文字列のそれぞれの前記分割部分に対する前記挿入単語の前記最小重みを以下のように計算すること、を備え、
【数５】
0005597255.tif 000013
Ｗは重みを表し、Ｉtは挿入文字列のｔ番目の分割部分を表し、ｎは挿入された分割部分の数を表し、Ｑjは前記クエリ文字列のｊ番目の分割部分を表し、ｍは前記クエリ文字列の分割部分の数を表す、方法。
【請求項９】
請求項７に記載の方法であって、前記ターゲット文字列の分割部分に対する前記削除単語の前記最小重みを決定することは、
単語の組み合わせと単語の組み合わせに対する重みとの前記マッピングに基づいて、前記ターゲット文字列の前記分割部分に対する前記削除単語の複数の重みを決定し、
前記ターゲット文字列のそれぞれの前記分割部分に対する前記削除単語の前記最小重みを以下のように計算することと、を備え、
【数６】
0005597255.tif 000014
Ｗは重みを表し、Ｔiは前記ターゲット文字列のｔ番目の分割部分を表し、ｑは前記ターゲット文字列の分割部分の数を表し、Ｄdは前記削除単語内のｄ番目の分割部分を表し、ｐは削除された分割部分の数を表す、方法。
【請求項１０】
請求項７に記載の方法であって、前記総編集距離を決定することは、
前記複数のターゲット文字列の複数の総編集距離をＷTotal＝ＷI＋ＷDとして計算することを含み、
ＷTotalは前記総編集距離を表し、ＷIは前記クエリ文字列の分割部分に対する前記挿入単語の前記最小重みを表し、ＷDは前記複数のターゲット文字列の内の一ターゲット文字列の分割部分に対する前記削除単語の前記最小重みを表す、方法。
【請求項１１】
請求項７に記載の方法であって、さらに、
各置換単語の最小重みを決定することを備え、
前記総編集距離を決定することは、さらに、各置換単語の前記最小重みに基づき、
前記総編集距離は、ＷTotal＝ＷI＋ＷD＋ＷCとして計算され、
ＷTotalは前記総編集距離を表し、ＷIは前記クエリ文字列の分割部分に対する前記挿入単語の前記最小重みを表し、ＷDは前記複数のターゲット文字の内の一ターゲット文字列の分割部分に対する前記削除単語の前記最小重みを表し、ＷCは前記クエリ文字または前記ターゲット文字列の分割部分に対する前記置換単語の前記最小重みを表す、方法。
【請求項１２】
請求項１１に記載の方法であって、前記各置換単語の前記最小重みを決定することは、事前設定された固定値に前記置換単語の前記編集距離の前記最小重みを設定することを含む、方法。
【請求項１３】
請求項１１に記載の方法であって、前記各置換単語の前記最小重みを決定することは、前記置換単語の前記編集距離を、前記クエリ文字列の分割部分に対する前記挿入単語の前記最小重みと前記ターゲット文字列の前記分割部分に対する前記削除単語の前記最小重みとの合計値、平均値、または、最大値に設定することを含む、方法。
【請求項１４】
検索結果を順位付けるためのシステムであって、
１または複数のプロセッサであって、
クエリ文字列を受信し、
クエリ文字列に関連する対応する複数のターゲット文字列を含む複数の検索結果を取得し、
前記クエリ文字列と、各前記複数のターゲット文字列を分割し、
複数の組み合わせを形成するために、前記クエリ文字列の分割部分を前記ターゲット文字列のそれぞれの分割部分と対にし、
単語の組み合わせと単語の組み合わせに対する重みとのマッピングに基づいて、前記複数の組み合わせに対応する複数の重みを取得し、重みは単語の組み合わせに含まれる単語間の意味的相関の指標となり、
前記複数のターゲット文字列のそれぞれに対応する前記重みに基づいて重み付けされた単語長を決定すし、
前記複数のターゲット文字列を前記複数のターゲット文字列のそれぞれについて重み付けされた単語長に基づいて順位付けることを実行するよう構成されている１または複数のプロセッサと、
前記１または複数のプロセッサに接続され、前記１または複数のプロセッサに命令を提供するよう構成されている１または複数のメモリと、
を備える、システム。
【請求項１５】
請求項１４に記載のシステムであって、単語の組み合わせと各単語の組み合わに対する重みとの前記マッピングは、
１組の統計サンプルを取得し、
前記１組の統計サンプルから第１の単語および第２の単語を選択し、前記第１および第２の単語の両方が前記統計サンプル内で出現する回数をＣ（前記第１の単語、前記第２の単語）としてカウントし、
前記第２の単語が前記統計サンプル内で出現する回数をΣＣ（Ｙi、前記第２の単語）としてカウントし、Ｙiは前記第２の単語と一緒に出現するそれぞれの前記単語を表し、
前記第１および第２の単語の両方が前記統計サンプル内で出現する回数と、前記第２の単語が前記統計サンプル内で出現する回数とに基づいて、前記第２の単語が出現する条件のもとでの前記第１の単語の出現確率Ｐを計算し、
前記第２の単語の検索の際に、前記第１および第２の単語の間の意味的相関の指標となる重みをＷ＝１−Ｐによって決定し、Ｗは前記重みであり、Ｐは前記第２の単語が出現する前記条件のもとでの前記第１の単語の前記確率であり、
前記統計サンプル内の単語の組み合わせの間の意味的相関の指標となる前記重みを決定するために、前記選択、カウント、計算、および、決定を繰り返し、
前記単語の組み合わせと各単語の組み合わせに対する重みとの前記マッピングを格納すること、によって決定される、システム。
【請求項１６】
請求項１４に記載のシステムであって、
前記重み付けされた単語長は、最短スライディングウィンドウの前記重み付けされた単語長であり、
前記重みから前記重み付けされた単語長を決定して、それぞれの前記ターゲット文字列を順位付けことは、
前記クエリ文字列の分割部分に対する前記ターゲット文字列の分割部分の最小重みは、前記ターゲット文字列内の各分割部分を用いて、前記複数の組み合わせをグループ化し、各グループ内における最小の重みをそれぞれ決定して求められ、または、前記ターゲット文字列の分割部分に対する前記クエリ文字列の分割部分の最小重みは、前記クエリ文字列の各分割部分を用いて、前記複数の組み合わせをグループ化し、各グループ内における最小の重みをそれぞれ決定して求められ、
前記最小重みに基づいて、ターゲット文字列について前記最短スライディングウィンドウの前記重み付けされた長さを計算し、
前記ターゲット文字列の前記最短スライディングウィンドウの前記重み付けされた長さを比較すること、を含み、
重み付けされた長さが短いターゲット文字列が、重み付けされた長さが長いターゲット文字列よりも高く順位付けされる、システム。
【請求項１７】
請求項１６に記載のシステムであって、前記最小重みに基づいて、ターゲット文字列について前記最短スライディングウィンドウの前記重み付けされた長さを計算することは、以下の式に基づいており、
【数７】
0005597255.tif 000015
Ｗは重みを表し、Ｔiはターゲット文字列のｉ番目の分割部分を表し、ｋおよびｈはそれぞれ前記ターゲット文字の前記最短スライディングウィンドウの開始位置および終了位置を表し、Ｑjは前記クエリ文字列のｊ番目の分割部分を表し、ｍは前記クエリ文字列の分割部分の数を表す、システム。
【請求項１８】
検索結果を順位付けるためのシステムであって、
１または複数のプロセッサであって、
クエリ文字列を受信し、
クエリ文字列に関連する対応する複数のターゲット文字列を含む複数の検索結果を取得し、
前記クエリ文字列と、前記複数のターゲット文字列のそれぞれを分割し、
単語の組み合わせと単語の組み合わせに対する重みとのマッピングに基づいて、前記クエリ文字列の分割部分に対する各挿入単語の最小重みを決定し、
単語の組み合わせと単語の組み合わせに対する重みとのマッピングに基づいて、前記ターゲット文字列の分割部分に対する各削除単語の最小重みを決定し、
各挿入単語の前記最小重みおよび各削除単語の前記最小重みに少なくとも部分的に基づいて総編集距離を決定し、
前記総編集距離に基づいて前記ターゲット文字列を順位付けることを実行するよう構成されている１または複数のプロセッサと、
前記１または複数のプロセッサに接続され、前記１または複数のプロセッサに命令を提供するよう構成されている１または複数のメモリと、
を備える、システム。
【請求項１９】
請求項１８に記載のシステムであって、前記クエリ文字列の分割部分に対する各挿入単語の最小重みを決定することは、
単語の組み合わせと単語の組み合わせに対する重みとの前記マッピングに基づいて、前記クエリ文字列の分割部分に対する前記挿入単語の複数の重みを決定し、
前記クエリ文字列のそれぞれの前記分割部分に対する前記挿入単語の前記最小重みを以下のように計算すること、を含み、
【数８】
0005597255.tif 000016
Ｗは重みを表し、Ｉtは挿入文字列のｔ番目の分割部分を表し、ｎは挿入された分割部分の数を表し、Ｑjは前記クエリ文字列のｊ番目の分割部分を表し、ｍは前記クエリ文字列の分割部分の数を表す、システム。
【請求項２０】
請求項７に記載の方法であって、前記ターゲット文字列の分割部分に対する前記削除単語の前記最小重みを決定することは、
単語の組み合わせと単語の組み合わせに対する重みとの前記マッピングに基づいて、前記ターゲット文字列の前記分割部分に対する前記削除単語の複数の重みを決定し、
前記ターゲット文字列のそれぞれの前記分割部分に対する前記削除単語の前記最小重みを以下のように計算すること、を備え、
【数９】
0005597255.tif 000017
Ｗは重みを表し、Ｔiは前記ターゲット文字列のｔ番目の分割部分を表し、ｑは前記ターゲット文字列の分割部分の数を表し、Ｄdは前記削除単語のｄ番目の分割部分を表し、ｐは削除された分割部分の数を表す、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の相互参照］
本願は、すべての目的のために参照により本明細書に組み込まれる、２００９年７月２０日出願の発明の名称を「ＭＥＴＨＯＤ  ＡＮＤ  ＤＥＶＩＣＥ  ＦＯＲ  ＲＡＮＫＩＮＧ  ＳＥＡＲＣＨ  ＲＥＳＵＬＴＳ（検索結果を順位付けるための方法および装置）」とする中国特許出願第２００９１０１５１６４７．３号に基づく優先権を主張する。
【０００２】
本願は、コンピュータデータ処理の分野に関し、特に、検索結果を順位付けるための方法およびデバイスに関する。
【背景技術】
【０００３】
検索エンジンは、一般に、クエリ文字列内のいくつかの単語が検索結果内で出現する位置の間の距離に従って、検索結果（ターゲット文字列ともいう）がクエリ文字列と一致する程度を評価し、より短い距離の検索結果が、通例、高い程度で一致するため、より高く順位付けされる。例えば、クエリ文字列「ｄｉｓｉｎｆｅｃｔｉｏｎ  ｍａｃｈｉｎｅ」については、「ｄｉｓｉｎｆｅｃｔｉｏｎ  ｍａｃｈｉｎｅ」を含む検索結果が、「ｄｉｓｉｎｆｅｃｔｉｏｎ  ｅｑｕｉｐｍｅｎｔ」よりもユーザの意図に近い傾向があり、「ｄｉｓｉｎｆｅｃｔｉｏｎ  ｅｑｕｉｐｍｅｎｔ」は、「ｉｎｄｕｓｔｒｉａｌ  ｄｉｓｉｎｆｅｃｔｉｏｎ  ｗａｓｈｉｎｇ  ｍａｃｈｉｎｅ」、「ｄｅｈｙｄｒａｔｏｒ」、および、「ｄｒｙｅｒ」よりもユーザの意図に近く、これらはすべて、検索結果の順位付けにいくらかの影響を持つ。
【０００４】
検索結果を順位付けするための標準的な方法は、通常、最短のスライディングウィンドウ（すなわち、クエリ文字列の単語を含むターゲット文字列内での最小間隔）を用いたターゲット文字列内におけるクエリ文字列の単語の距離、クエリ文字列およびターゲット文字列の編集距離、品詞（ＰＯＳ）としての単語コンテキスト、などに基づいている。
【０００５】
これらの単純な技術は、文字列のクエリ検索とターゲット文字列との間の相関の問題に対処しない傾向があり、それらの結果は、文字列のクエリ検索とターゲット文字列との一致度を正確に反映しないことが多い。クエリ文字列「Ｎｏｋｉａ  ｂａｔｔｅｒｙ」を例にとり、３つの検索結果Ａ、Ｂ、および、Ｃは、それぞれ、文字列「Ｎｏｋｉａ  ｂａｔｔｅｒｙ」、「Ｎｏｋｉａ  ｃｅｌｌ  ｐｈｏｎｅ，  ｃｏｍｐｌｉｍｅｎｔａｒｙ  ｂａｔｔｅｒｙ」、および、「Ｎｏｋｉａ  ｎ７３  ｃｅｌｌ  ｐｈｏｎｅ  ｗｉｔｈ  ｏｒｉｇｉｎａｌ  ｂａｔｔｅｒｙ」を含むとする。単純な距離計算は、文字列Ａ内の「Ｎｏｋｉａ」および「ｂａｔｔｅｒｙ」の間の距離が０であるため、Ａが最高の一致度を有することを示す。文字列ＢおよびＣにおける「Ｎｏｋｉａ」および「ｂａｔｔｅｒｙ」の間の距離は、それぞれ、３単語および５単語であり、Ｃの方がＢよりも一致度が低いことを示している。しかしながら、「Ｎｏｋｉａ  ｂａｔｔｅｒｙ」を検索するユーザの意図に基づくと、検索結果Ｃは、実際には、単語間隔が大きいにも関わらず、Ｂよりも良好に一致している。
【図面の簡単な説明】
【０００６】
以下の詳細な説明と添付の図面に、本発明の様々な実施形態を開示する。
【０００７】
【図１】単語の重みのマッピングを生成するための処理の一実施形態を示すフローチャート。
【０００８】
【図２】検索結果を順位付けするための処理の一実施形態を示すフローチャート。
【０００９】
【図３】検索結果を順位付けするための処理の別の実施形態を示すフローチャート。
【００１０】
【図４】検索結果を順位付けするためのシステムの一実施形態を示すブロック図。
【００１１】
【図５】検索結果を順位付けするためのシステムの別の実施形態を示すブロック図。
【発明を実施するための形態】
【００１２】
本発明は、処理、装置、システム、物質の組成、コンピュータ読み取り可能な格納媒体上に具現化されたコンピュータプログラム製品、および／または、プロセッサ（プロセッサに接続されたメモリに格納および／またはそのメモリによって提供される命令を実行するよう構成されたプロセッサ）を含め、様々な形態で実装されうる。本明細書では、これらの実装または本発明が取りうる任意の他の形態を、技術と呼ぶ。一般に、開示された処理の工程の順序は、本発明の範囲内で変更されてもよい。特に言及しない限り、タスクを実行するよう構成されるものとして記載されたプロセッサまたはメモリなどの構成要素は、ある時間にタスクを実行するよう一時的に構成された一般的な構成要素として、または、タスクを実行するよう製造された特定の構成要素として実装されてよい。本明細書では、「プロセッサ」という用語は、１または複数のデバイス、回路、および／または、コンピュータプログラム命令などのデータを処理するよう構成された処理コアを指すものとする。
【００１３】
以下では、本発明の原理を示す図面を参照しつつ、本発明の１または複数の実施形態の詳細な説明を行う。本発明は、かかる実施形態に関連して説明されているが、どの実施形態にも限定されない。本発明の範囲は、特許請求の範囲によってのみ限定されるものであり、多くの代替物、変形物、および、等価物を含む。以下の説明では、本発明の完全な理解を提供するために、多くの具体的な詳細事項が記載されている。これらの詳細事項は、例示を目的としたものであり、本発明は、これらの具体的な詳細事項の一部または全てがなくとも特許請求の範囲に従って実施可能である。簡単のために、本発明に関連する技術分野で周知の技術事項については、本発明が必要以上にわかりにくくならないように、詳細には説明していない。
【００１４】
特定の意味的要因を考慮したターゲット文字列の順位付けについて説明する。順位付けは、クエリ文字列とターゲット文字列との間の意味的相関を考慮に入れることにより、クエリ文字列がターゲット文字列と一致する程度をより良好に評価し、典型的なユーザの意図をより厳密に追跡する電子商取引プラットフォームのための検索エンジンにおける検索結果の順位を生成する。検索エンジンでその技術を用いる例を、例示の目的で広く議論する。その技術は、多くの他の用途にも適用可能である。
【００１５】
いくつかの実施形態では、サンプルセット内の文字列間の意味的相関を考慮するために、サンプルセット内の２単語のあらゆる組み合わせの間の意味的相関が重み付けされて、単語重みのテーブルが生成される。図１は、単語の重みのマッピングを生成するための処理の一実施形態を示すフローチャートである。処理１００は、サーバ、検索エンジン、または、任意の他の適切なデバイス上で実行されてよい。生成された単語の重みのマッピングは格納されて、後に利用される。
【００１６】
工程１０１では、統計サンプルが、ウェブページ、ユーザ検索ログ、ユーザ選択ログなど、様々なフォーマットを有するテキストまたは記号群から取得される。
【００１７】
一般に、第１の単語および第２の単語の両方が統計サンプルに出現する回数が大きくなるほど、それらの相関は高くなる。例えば、「Ｎｏｋｉａ」および「ｃｅｌｌ  ｐｈｏｎｅ」の両方がテキスト中に出現する場合、または、ユーザがしばしば「Ｎｏｋｉａ」を検索した後に「ｃｅｌｌ  ｐｈｏｎｅ」という用語を含む結果を選択する場合、「Ｎｏｋｉａ」および「ｃｅｌｌ  ｐｈｏｎｅ」の相関は高いことが示唆される。
【００１８】
工程１０２では、第１の単語および第２の単語が統計サンプルから選択され、第１および第２の単語の両方が統計サンプル内で出現する回数がカウントされ、Ｃ（第１の単語、第２の単語）として表される。例えば、「ｃｅｌｌ  ｐｈｏｎｅ」および「Ｎｏｋｉａ」の両方がサンプル内で出現する回数がカウントされ、Ｃ（ｃｅｌｌ  ｐｈｏｎｅ、Ｎｏｋｉａ）として記録される。次に、それぞれの単語の重みが計算され、後に、検索結果の順位付けを生成するために利用される。
【００１９】
工程１０３では、第２の単語が統計サンプル内で出現する回数がカウントされ、ΣＣ（Ｙi、第２の単語）として記録される。ここで、Ｙiは、第２の単語と一緒に出現するそれぞれの単語を示す。例えば、「Ｎｏｋｉａ」が他の単語（「ｂａｔｔｅｒｙ」、「ｏｒｉｇｉｎａｌ」など）と一緒に出現する総回数（これは「Ｎｏｋｉａ」がサンプル内で出現する総回数と等しい）がカウントされ、ΣＣ（Ｙi、”Ｎｏｋｉａ”）として記録される。ここで、Ｙiは「Ｎｏｋｉａ」と一緒に出現するそれぞれの単語を示す。
【００２０】
工程１０４では、第２の単語も出現するという条件のもとでの第１の単語の出現確率Ｐが、以下のように計算される。
Ｐ（第１の単語｜第２の単語）＝Ｃ（第１の単語、第２の単語）／ΣＣ（Ｙi、第２の単語）
【００２１】
例えば、「Ｎｏｋｉａ」も出現するという条件のもとでの「ｃｅｌｌ  ｐｈｏｎｅ」の出現確率は以下のように計算される。
Ｐ（ｃｅｌｌ  ｐｈｏｎｅ｜Ｎｏｋｉａ）＝Ｃ（ｃｅｌｌ  ｐｈｏｎｅ）／ΣＣ（Ｙｉ、Ｎｏｋｉａ）
【００２２】
工程１０５では、第１および第２の単語の間の意味的相関の指標となる重みが決定される。この例では、重みＷは、第２の単語の所与の検索に対してＷ＝１−Ｐに従って決定される。ここで、Ｗは重みであり、Ｐは第２の単語が出現するという条件下での第１の単語の確率である。
【００２３】
例えば、「ｃｅｌｌ  ｐｈｏｎｅ」および「Ｎｏｋｉａ」の間の意味的相関は、「Ｎｏｋｉａ」の検索の際には、Ｗ＝１−Ｐ＝１−Ｐ（ｃｅｌｌ  ｐｈｏｎｅ｜Ｎｏｋｉａ）＝１−Ｃ（ｃｅｌｌ  ｐｈｏｎｅ）／ΣＣ（Ｙi、Ｎｏｋｉａ）で重み付けされる。
【００２４】
この例では例示の目的で、Ｗ＝１−Ｐという重みが用いられているが、重みは他の方法で計算することもできる。例えば、いくつかの実施形態において、重みは、Ｐに設定される。重みは、いくつかの実施形態において、他の形態（対数の形態など）に変換されてもよい。
【００２５】
工程１０６では、上記の工程が、統計サンプル内のすべての単語に対して実行されたか否かが判定され、実行された場合には、制御は工程１０７へ移行し、そうでない場合には、統計サンプル内のそれぞれの単語およびその他のそれぞれの単語の間の意味的相関を順に重み付けするために、工程１０２〜１０６が繰り返される。
【００２６】
工程１０７では、統計サンプル内のそれぞれの単語およびその他のそれぞれの単語の間の意味的相関の重みが、単語重みのマッピングテーブルとして格納され、任意選択的に出力される。リスト、ツリーなど、その他の適切なフォーマットも利用可能である。
【００２７】
単語の重みテーブルの一例を表１に示す。
【００２８】
【表１】
0005597255.tif 000002
【００２９】
表１に示した単語の重みテーブルの例は、例示にすぎず、単語重みテーブルは、他の実施形態では他の形態で具現化されてもよい。また、単語は多くの異なる方法で重み付けされてよく、図１は単に、統計的言語モデルから得られた統計確率の一実施形態を示すものである。重みは、自動計算または手作業での設定など、他の適切な技術を用いて導出されてもよい。
【００３０】
図２は、検索結果を順位付けするための処理の一実施形態を示すフローチャートである。処理２００は、サーバまたは任意の他の適切なデバイス上で実行されてよい。ターゲット文字列がクエリ文字列に一致する程度（一致度ともいう）が決定される。
【００３１】
工程２０１では、クエリ文字列および対応するターゲット文字列が取得される。いくつかの実施形態において、クエリ文字列は、ユーザによるキーワード入力を含み、キーワード入力は、潜在的な結果のデータベース内のターゲット文字列を特定するために用いられる。キーワードマッチングまたはインデックスマッチングなど様々な技術が、ターゲット文字列を取得するために利用されうる。ターゲット文字列は、クエリ文字列と相関性がある文字を含む。例えば、ユーザが「Ｎｏｋｉａ  Ｂａｔｔｅｒｙ」というクエリ文字列を入力し、サーバから取得されたターゲット文字列が、文字列Ａ「Ｎｏｋｉａ  Ｂａｔｔｅｒｙ」、文字列Ｂ「Ｎｏｋｉａ  Ｃｅｌｌ  Ｐｈｏｎｅ  Ｗｉｔｈ  Ｆｒｅｅ  Ｂａｔｔｅｒｙ」、および、文字列Ｃ「Ｎｏｋｉａ  ｎ７３  Ｃｅｌｌ  Ｐｈｏｎｅ  Ｗｉｔｈ  Ｏｒｉｇｉｎａｌ  Ｂａｔｔｅｒｙ」である場合、取得されたすべての文字列Ａ、Ｂ、および、Ｃがターゲット文字列である。
【００３２】
工程２０２では、クエリ文字列およびターゲット文字列が分割される。ここで、Ｑはクエリ文字列を表し、Ｔはターゲット文字列を表し、クエリ文字列が、単語Ｑ1Ｑ2・・・Ｑmに分割され、ターゲット文字列が、単語Ｔ1Ｔ2・・・Ｔnに分割されるとする。文字列を、意味的単語、キャラクタ（ｃｈａｒａｃｔｅｒｓ）、文字（ｌｅｔｔｅｒｓ）、記号などに分割するなど、他の分割技術も可能である。
【００３３】
この例では、クエリ文字列は、Ｑ1Ｑ2＝Ｎｏｋｉａ｜ｂａｔｔｅｒｙに分割される。ターゲット文字列Ｃは、Ｔ1Ｔ2Ｔ3Ｔ4Ｔ5＝Ｎｏｋｉａ｜ｎ７３｜ｃｅｌｌ  ｐｈｏｎｅ｜ｏｒｉｇｉｎａｌ｜ｂａｔｔｅｒｙに分割される。その他のターゲット文字列も、同様に分割できる。
【００３４】
工程２０３では、クエリ文字列内のそれぞれの分割単語が、ターゲット文字列内の分割単語と対になって順次組み合わされ、分割単語の組み合わせが形成される。ここで、各組み合わせは、クエリ文字列の分割単語と、文字のターゲットクエリの分割単語を含む。具体的には、（Ｔi、Ｑ1）、（Ｔi、Ｑ2）・・・（Ｔi、Ｑm）が得られる。
【００３５】
クエリ文字列およびターゲット文字列Ｃから得られる分割単語の組み合わせは、（Ｔ1、Ｑ1）、（Ｔ1、Ｑ2）、（Ｔ2、Ｑ1）、（Ｔ2、Ｑ2）、（Ｔ3、Ｑ1）、（Ｔ3、Ｑ2）、（Ｔ4、Ｑ1）、（Ｔ4、Ｑ2）、（Ｔ5、Ｑ1）、および、（Ｔ5、Ｑ2）、である。
【００３６】
工程２０４では、予め生成された単語の重みテーブルで検索が行われ、分割単語のそれぞれの組み合わせの重みが取得される。
【００３７】
ここで、Ｗが、単語重みテーブルから取得された分割単語のそれぞれの組み合わせの重みを表すとすると、Ｗは、それぞれ、Ｗ（Ｔ１、Ｑ１）、Ｗ（Ｔ１、Ｑ２）、Ｗ（Ｔ２、Ｑ１）、Ｗ（Ｔ２、Ｑ２）、Ｗ（Ｔ３、Ｑ１）、Ｗ（Ｔ３、Ｑ２）、Ｗ（Ｔ４、Ｑ１）、Ｗ（Ｔ４、Ｑ２）、Ｗ（Ｔ５、Ｑ１）、および、Ｗ（Ｔ５、Ｑ２）、である。
【００３８】
ここで、Ｗ（Ｔ１、Ｑ１）＝Ｗ１  Ｗ（Ｔ１、Ｑ２）＝Ｗ１’
Ｗ（Ｔ２、Ｑ１）＝Ｗ２  Ｗ（Ｔ２、Ｑ２）＝Ｗ２’
Ｗ（Ｔ３、Ｑ１）＝Ｗ３  Ｗ（Ｔ３、Ｑ２）＝Ｗ３’
Ｗ（Ｔ４、Ｑ１）＝Ｗ４  Ｗ（Ｔ４、Ｑ２）＝Ｗ４’
Ｗ（Ｔ５、Ｑ１）＝Ｗ５  Ｗ（Ｔ５、Ｑ２）＝Ｗ５’とする。
【００３９】
特に、ＴｉがＱの中に含まれる場合、Ｗｉ＝０である。例えば、Ｔ１およびＱ１の両方が「Ｎｏｋｉａ」であるため、Ｗ（Ｔ１、Ｑ１）＝Ｗ１＝０であり、同様に、Ｔ５およびＱ２の両方が「Ｂａｔｔｅｒｙ」であるため、Ｗ（Ｔ５、Ｑ２）＝Ｗ５’＝０である。
【００４０】
工程２０５では、各ターゲット文字列について重み付けされた単語長が、分割単語の重みに基づいて計算される。いくつかの実施形態では、重み付けされた単語長は、最短スライディングウィンドウ（ｓｈｏｒｔｅｓｔ  ｓｌｉｄｉｎｇ  ｗｉｎｄｏｗ）の重み付けされた長さである。
【００４１】
いくつかの実施形態では、重み付けされた単語長を決定するために、クエリ文字列内の対応する分割単語に対するターゲット文字列内の分割単語の最小重みが計算される。いくつかの実施形態では、ターゲット文字列内のそれぞれの分割単語に対するクエリ文字列内の分割単語の最小重みが計算される。クエリ文字列内のそれぞれの分割単語に対するターゲット文字列内のそれぞれの分割単語の最小重みを計算する処理は、ターゲット文字列内のそれぞれの分割単語に対するクエリ文字列内のそれぞれの分割単語の最小重みを計算する処理と非常に類似しているため、例示の目的で前者のみを以下で詳述する。
【００４２】
したがって、（Ｔ１、Ｑ１）および（Ｔ１、Ｑ２）に対応する２つの重みの内の小さい方、（Ｔ２、Ｑ１）および（Ｔ２、Ｑ２）に対応する２つの重みの内の小さい方などが決定される。
【００４３】
この例において、Ｗ（Ｔ１、Ｑ１）とＷ（Ｔ１、Ｑ２）との間ではＷ（Ｔ１、Ｑ１）が小さく、Ｗ（Ｔ２、Ｑ１）とＷ（Ｔ２、Ｑ２）との間ではＷ（Ｔ２、Ｑ１）の方が小さく、Ｗ（Ｔ３、Ｑ１）とＷ（Ｔ３、Ｑ２）との間ではＷ（Ｔ３、Ｑ１）の方が小さく、Ｗ（Ｔ４、Ｑ１）とＷ（Ｔ４、Ｑ２）との間ではＷ（Ｔ４、Ｑ１）の方が小さく、Ｗ（Ｔ５、Ｑ１）とＷ（Ｔ５、Ｑ２）との間ではＷ（Ｔ５、Ｑ２）の方が小さい、と仮定する。したがって、上記によると、最小の重みは、Ｗ１、Ｗ２、Ｗ３、Ｗ４、および、Ｗ５’である。
【００４４】
次に、最短スライディングウィンドウの重み付けされた長さが、ターゲット文字列の最小重みに基づいて計算される。いくつかの実施形態では、ターゲット文字列の最短スライディングウィンドウの重み付けされた長さは、以下のように計算される。
【００４５】
【数１】
0005597255.tif 000003
【００４６】
ここで、Ｗは重みを表し、Ｔiはターゲット文字列内のｉ番目の分割単語を表し、ｋおよびｈはそれぞれターゲット文字列の最短スライディングウィンドウの開始位置および終了位置を表し、Ｑjはクエリ文字列内のｊ番目の分割単語を表し、ｍはクエリ文字列内の分割単語の数を表す。
【００４７】
この例では、最短スライディングウィンドウの重み付けされた長さは、以下の通りである。
Ｗsw＝ΣＷｉ＝Ｗ１＋Ｗ２＋Ｗ３＋Ｗ４＋Ｗ５’
【００４８】
すべてのターゲット文字列に対してクエリ文字列における最短スライディングウィンドウの重み付けされた長さが計算されると、工程２０６では、クエリ文字列とターゲット文字列との一致度が、重み付けされた単語長に基づいて決定される。それぞれのターゲット文字列は、重み付けされた単語長によって順位付けされ、順位付けの結果は、任意選択的に、ユーザ端末に送り返される。
【００４９】
順位付けは、それぞれのターゲット文字列の最短スライディングウィンドウの重み付けされた長さを比較する工程を含む。長さが短いほど、一致度が高く、ターゲット文字列の順位が高くなり、長さが長いほど、一致度は低く、ターゲット文字列の順位は低くなる。
【００５０】
処理２００によると、クエリ文字列とそれぞれのターゲット文字列との一致度は、ターゲット文字列内の単語とクエリ文字列内の単語との間の意味的相関を考慮しない従来の計算方法よりも正確に決定される。例えば、ターゲット文字列「Ｎｏｋｉａ  ｂａｔｔｅｒｙ」および「Ｎｏｋｉａ  ｎ７３  ｃｅｌｌ  ｐｈｏｎｅ  ｏｒｉｇｉｎａｌ  ｂａｔｔｅｒｙ」は長さが異なるが、それらの重み付けされた単語長が同等であるため、いずれも「Ｎｏｋｉａ  ｂａｔｔｅｒｙ」というクエリ文字列に対して高い関連性がある。この応用例は、クエリ文字列とターゲット文字列との間の意味的相関を示す単語重みを導入することで、クエリ文字列と相関性のあるターゲット文字列を高く順位付けてそれぞれのターゲット文字列とクエリ文字列との一致度を反映することによってそれぞれのターゲット文字列を正確に順位付けることが可能であり、実際に、簡単かつ効果的に適用されうる。
【００５１】
図３は、検索結果を順位付けするための処理の別の実施形態を示すフローチャートである。処理３００は、ターゲット文字列とクエリ文字列との一致度を、それらの編集距離に基づいて決定する。本明細書で用いられているように、編集距離とは、一の文字列を他の文字列に変更するために必要とされる基本動作の数、または、２つの文字列の異なる部分の長さの合計を指す。典型的な基本動作は、文字／単語の挿入、削除、または、置換、もしくは、その他の指定された動作を含む。例えば、「Ｉ  ｌｏｖｅ  ｙｏｕ」は、少なくとも２つの基本動作（すなわち、「ｄｏｎ’ｔ」を挿入する動作と、「ｙｏｕ」を「ｈｅｒ」に置換する動作）によって「Ｉ  ｄｏｎ’ｔ  ｌｏｖｅ  ｈｅｒ」に変更されるため、２つの文字列の間の編集距離は２である。
【００５２】
工程３０１では、クエリ文字列および対応するターゲット文字列がサーバによって取得される。これは、処理２００の工程２０１と同様の工程である。例えば、「Ｎｏｋｉａ  ｃｅｌｌ  ｐｈｏｎｅ  ｂａｔｔｅｒｙ」というクエリ文字列に対して、ターゲット文字列は、「ｏｒｉｇｉｎａｌ  Ｎｏｋｉａ  ｂａｔｔｅｒｙ」、「Ｓａｍｓｕｎｇ  ｃｅｌｌ  ｐｈｏｎｅ  ｂａｔｔｅｒｙ」などである。
【００５３】
工程３０２では、クエリ文字列およびターゲット文字列は、それぞれ、クエリ文字列を構成する分割単語およびターゲット文字列を構成する分割単語に分割される。ここで、Ｑはクエリ文字列を表し、Ｔはターゲット文字列を表し、クエリ文字列が、単語Ｑ1Ｑ2・・・Ｑmに分割され、ターゲット文字列が、単語Ｔ1Ｔ2・・・Ｔnに分割されるとする。具体的には、クエリ文字列「Ｎｏｋｉａ  ｃｅｌｌ  ｐｈｏｎｅ  ｂａｔｔｅｒｙ」は、Ｑ１Ｑ２Ｑ３＝「Ｎｏｋｉａ｜ｃｅｌｌ  ｐｈｏｎｅ｜ｂａｔｔｅｒｙ」に単語分割され、ターゲット文字列は、Ｔ１Ｔ２Ｔ３＝「ｏｒｉｇｉｎａｌ｜Ｎｏｋｉａ｜ｂａｔｔｅｒｙ」に分割される。
【００５４】
工程３０３では、予め計算された単語重みのマッピングに基づいて、クエリ文字列内のそれぞれの分割単語に対する挿入単語の最小重みが決定される。クエリ文字列内のそれぞれの分割単語に対する挿入単語の重みは、単語重みテーブルから取得される。この例では、Ｉ１で示される挿入単語「ｏｒｉｇｉｎａｌ」の重みは、クエリ文字列内のそれぞれの分割単語に対して、Ｗ（Ｉ１、Ｑ１）、Ｗ（Ｉ１、Ｑ２）、および、Ｗ（Ｉ１、Ｑ３）である。
【００５５】
クエリ文字列内のそれぞれの分割単語に対する挿入単語の最小重みは、以下のように計算される。
【数２】
0005597255.tif 000004
ここで、Ｗは重みを表し、Ｉtは挿入文字列内のｔ番目の分割単語を表し、ｎは挿入された分割単語の数を表し、Ｑjはクエリ文字列内のｊ番目の分割単語を表し、ｍはクエリ文字列内の分割単語の数を表す。
【００５６】
工程３０４では、ターゲット文字列内の分割単語に対する削除単語の最小重みが、単語重みテーブルに基づいて計算される。ターゲット文字列内のそれぞれの分割単語に対する削除単語の重みは、単語の重みテーブルから取得される。この例では、Ｄ１で示される削除単語「ｃｅｌｌ  ｐｈｏｎｅ」の重みは、ターゲット文字列内のそれぞれの分割単語に対して、Ｗ（Ｄ１，Ｔ１）、Ｗ（Ｄ１、Ｔ２）、および、Ｗ（Ｄ１、Ｔ３）である。
【００５７】
ターゲット文字列内の分割単語に対する削除単語の最小重みは、以下のように計算される。
【数３】
0005597255.tif 000005
ここで、Ｗは重みを表し、Ｔiはターゲット文字列内のｔ番目の分割単語を表し、ｑはターゲット文字列内の分割単語の数を表し、Ｄdは削除単語内のｄ番目の分割単語を表し、ｐは削除された分割単語の数を表す。
【００５８】
時に、編集距離は、単語の置換の影響を受ける。例えば、ある文字列が「Ｎｏｋｉａ  Ｂａｔｔｅｒｙ」であり、別の文字列が「Ｓａｍｓｕｎｇ  Ｂａｔｔｅｒｙ」である場合、「Ｎｏｋｉａ」から「Ｓａｍｓｕｎｇ」に置換されている。いくつかの実施形態では、置換動作は、別個の動作ではなく、追加動作および削除動作の組み合わせとして認識される。例えば、「Ｎｏｋｉａ」が削除されると共に「Ｓａｍｓｕｎｇ」が追加されることにより、「Ｎｏｋｉａ  Ｂａｔｔｅｒｙ」が「Ｓａｍｓｕｎｇ  Ｂａｔｔｅｒｙ」に変更されると考えることができる。したがって、挿入単語または削除単語に関係する上述の計算を用いて、編集距離の最小重みが決定される。
【００５９】
いくつかの実施形態において、置換動作は、挿入および削除に加えて第３の種類の動作と見なされる。置換単語の編集距離の最小重みを決定する１つの方法は、事前設定された固定値（例えば、１）に最小重みを設定する方法である。その他の方法は、クエリ文字列内のそれぞれの分割単語に対する挿入単語の最小重みとターゲット文字列内のそれぞれの分割単語に対する削除単語の最小重みとの合計値、平均値、最大値、または、任意の他の適切な組み合わせに、置換単語の編集距離を設定することを含む。
【００６０】
例えば、いくつかの実施形態において、置換単語「Ｓａｍｓｕｎｇ」の編集距離は、クエリ文字列「Ｎｏｋｉａ  Ｂａｔｔｅｒｙ」内の分割単語に対する挿入単語「Ｓａｍｓｕｎｇ」の最小重みとターゲット文字列「Ｓａｍｓｕｎｇ  Ｂａｔｔｅｒｙ」内の分割単語に対する削除単語「Ｎｏｋｉａ」の最小重みとの合計である。
【００６１】
あるいは、いくつかの実施形態において、置換単語「Ｓａｍｓｕｎｇ」の編集距離は、クエリ文字列「Ｎｏｋｉａ  Ｂａｔｔｅｒｙ」内の分割単語に対する挿入単語「Ｓａｍｓｕｎｇ」の最小重みとターゲット文字列「Ｓａｍｓｕｎｇ  Ｂａｔｔｅｒｙ」内の分割単語に対する削除単語「Ｎｏｋｉａ」の最小重みとの合計を２で割ったものである。
【００６２】
工程３０５では、ターゲット文字列の総編集距離の最小重みが、前の工程で決定された単語の最小重みに基づいて計算され、それらの値は、クエリ文字列とターゲット文字列との一致度を決定するために用いられる。
【００６３】
挿入動作および削除動作のみを考慮する実施形態では、総編集距離が、それぞれのターゲット文字列に対して計算され、ターゲット文字列の総編集距離は以下の通りである。
ＷTotal＝ＷI＋ＷD
ここで、ＷTotalは総編集距離の最小重みを表し、ＷIはクエリ文字列内のそれぞれの分割単語に対する挿入単語の最小重みを表し、ＷDはターゲット文字列内のそれぞれの分割単語に対する削除単語の最小重みを表す。
【００６４】
挿入、削除、および、置換動作を考慮する実施形態では、総編集距離が、それぞれのターゲット文字列に対して計算され、総編集距離は以下の通りである。
ＷTotal＝ＷI＋ＷD＋ＷS
ここで、ＷTotalは総編集距離を示し、ＷIはクエリ文字列内のそれぞれの分割単語に対する挿入単語の最小重みを表し、ＷDはターゲット文字列内のそれぞれの分割単語に対する削除単語の最小重みを表し、ＷSはクエリ文字列および／またはターゲット文字列内のそれぞれの分割単語に対する置換単語の最小重みを表す。
【００６５】
工程３０６では、ターゲット文字列の総編集距離の最小重みが、順位を生成するために比較される。総編集距離の最小重みが小さいほど、一致度が大きくなり、ターゲット文字列の順位が高くなる。逆に、総編集距離の最小重みが大きいほど、一致度が小さくなり、ターゲット文字列の順位が低くなる。
【００６６】
処理２００および３００は、様々な異なる方法で実施されてもよい。
【００６７】
重みは、クエリ文字列およびターゲット文字列に対して交互に計算されてよい。挿入文字列は、クエリ文字列に対して重み付けされてよく、削除文字列は、ターゲット文字列に対して重み付けされてよい。
【００６８】
任意の形態で（例えば、対数的に）重みが計算または変換されてもよいし、また、ターゲット単語が、それぞれのクエリ単語に対するターゲット単語の重みの最大値、平均値、または、別の形態（「重み付けされた長さ」）によって重み付けされてもよい。ターゲット文字列およびクエリ文字列の順序は、いくつかの実施形態において逆転されてもよい。
【００６９】
単語の距離または長さは、文字列全体を通して計算されてもよいし、アルゴリズムで選択された任意の間隔（「例えば、ある文字列が別の文字列から異なっている部分」）において計算されてもよい。
【００７０】
順位付けは、最短スライディングウィンドウまたは編集距離の代わりに、任意の重み付けされた単語の距離または長さの計算を含んでもよい。
【００７１】
図４は、検索結果を順位付けするためのシステムの一実施形態を示すブロック図である。システム４００は、１組の統計サンプル内の２単語のあらゆる組み合わせの間の意味的相関を重み付けし、単語重みテーブルを生成および格納するよう適合されている単語重み生成モジュール４０１と、クエリ文字列を受信し、クエリ文字列を検索し、ターゲット文字列を取得するよう適合されている単語取得モジュール４０２と、クエリ文字列とターゲット文字列の各々とを分割するよう適合されている単語分割モジュール４０３と、クエリ文字列内のそれぞれの分割単語とターゲット文字列内のそれぞれの分割単語とを対にして順次組み合わせるよう適合されている組み合わせモジュール４０４と、分割単語のそれぞれの組み合わせの重みを取得するために単語重みテーブルに照会するよう適合されている照会モジュール４０５と、重み付けされた単語長を重みから計算し、重み付けされた単語長に基づいてターゲット文字列を順位付けし、任意選択的に順位付けの結果をユーザ端末にフィードバックするよう適合されているマッチングモジュール４０６と、を備える。
【００７２】
いくつかの実施形態において、単語重み生成モジュール４０１は、さらに、統計サンプルを取得するよう適合されたサンプル取得モジュールと、統計サンプルから第１の単語および第２の単語を選択し、第１および第２の単語の両方が統計サンプル内で出現する回数をＣ（第１の単語、第２の単語）としてカウントするよう適合された第１のカウントモジュールと、第２の単語が統計サンプル内で出現する回数をΣＣ（Ｙi、第２単語）（Ｙiはサンプル内で第２の単語と一緒に出現する単語を示す）としてカウントするよう適合された第２のカウントモジュールと、第２の単語が出現する条件のもとでの第１の単語の確率をＰ（第１の単語｜第２の単語）＝Ｃ（第１の単語、第２の単語）／ΣＣ（Ｙi、第２の単語）として計算するよう適合された確率計算モジュールと、第２の単語の検索の際に、例えばＷ＝１−Ｐとして第１および第２の単語の間の意味的相関の重みを計算するよう適合された重み付けモジュールと（ここで、Ｗは重みであり、Ｐは第２の単語が出現する条件のもとでの第１の単語の確率である）、統計サンプル内のそれぞれの単語とそれぞれの他の単語との間の意味的相関の重みから単語の重みテーブルを生成するよう適合された生成モジュールと、を備える。
【００７３】
いくつかの実施形態において、重み付けされた単語長は、最短スライディングウィンドウの重み付けされた単語長であり、マッチングモジュール４０６は、さらに、クエリ文字列内の分割単語に対するターゲット文字列内の分割単語の最小重み、または、ターゲット文字列内の分割単語に対するクエリ文字列内の分割単語の最小重みを計算するよう適合された最小重み計算モジュールと、最小重みに従ってそれぞれのターゲット文字列について最短スライディングウィンドウの重み付けされた長さを計算するよう適合された第１の計算モジュールと、それぞれのターゲット文字列の最短スライディングウィンドウの重み付けされた長さを比較し、重み付けされた長さに基づいてターゲット文字列を順位付けするよう適合された順位付けモジュールと、を備える。
【００７４】
図５は、検索結果を順位付けするためのシステムの別の実施形態を示すブロック図である。システム５００は、１組の統計サンプル内の２単語のあらゆる組み合わせの間の意味的相関を重み付けし、単語重みテーブルを生成および格納するよう適合された単語重み生成モジュール５０１と、クエリ文字列を受信し、クエリ文字列を検索し、ターゲット文字列を取得するよう適合された単語取得モジュール５０２と、クエリ文字列とターゲット文字列の各々とを分割するよう適合された単語分割モジュール５０３と、クエリ文字列内の分割単語に対する挿入単語の最小重みを計算するよう適合された第１の最小重み計算モジュール５０４と、ターゲット文字列内の分割単語に対する削除単語の最小重みを計算するよう適合された第２の最小重み計算モジュール５０５と、最小重みから総編集距離を計算し、それぞれのターゲット文字列を順位付けし、任意選択的に順位付けの結果をユーザ端末にフィードバックするよう適合されたマッチングモジュール５０６と、を備える。
【００７５】
いくつかの実施形態において、マッチングモジュール５０６は、それぞれのターゲット文字列についての総編集距離をＷTotal＝ＷI＋ＷD（ここで、ＷTotalは総編集距離を表し、ＷIはクエリ文字列内の分割単語に対する挿入単語の最小重みを表し、ＷDはターゲット文字列内の分割単語に対する削除単語の最小重みを表す）として計算するよう適合された総編集距離計算モジュールと、それぞれのターゲット文字列の総編集距離を比較し、総編集距離に基づいてターゲット文字列を順位付けるよう適合された順位付けモジュールと、を備える。
【００７６】
いくつかの実施形態において、システム５００は、さらに、総編集距離を計算する前に置換単語の編集距離の最小重みを計算するよう適合された第３の最小重み計算モジュールを備える。したがって、総編集距離計算モジュールは、それぞれのターゲット文字列についての総編集距離をＷTotal＝ＷI＋ＷD＋ＷCとして計算するよう適合され、ＷTotalは総編集距離を示し、ＷIはクエリ文字列内のそれぞれの分割単語に対する挿入単語の最小重みを表し、ＷDはターゲット文字列内のそれぞれの分割単語に対する削除単語の最小重みを表し、ＷCはクエリ文字列および／またはターゲット文字列内のそれぞれの分割単語に対する置換単語の最小重みを表す。
【００７７】
システム４００および５００は、クエリ文字列およびターゲット文字列の間の意味的相関を示す単語重みを用いて、それぞれのターゲット文字列がクエリ文字列と一致する程度をより正確に反映するものであり、実際に、簡単かつ効果的に適用されうる。各システムは、以下のような１または複数の計算デバイスを用いて実装されてよい。パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたは携帯型デバイス、フラットパネルデバイス、マルチプロセッサシステム、マイクロプロセッサを用いたシステム、セットトップボックス、プログラム可能な消費者電子デバイス、ネットワークＰＣ、ミニコンピュータ、大規模コンピュータ、専用デバイス、任意の前述のシステムまたはデバイスを含む分散型計算環境、もしくは、１または複数のプロセッサと、プロセッサに接続されてプロセッサに命令を提供するよう構成されたメモリとを備えたその他のハードウェア／ソフトウェア／ファームウェアの組み合わせ。
【００７８】
上述のモジュールは、１または複数の汎用プロセッサ上で実行されるソフトウェアコンポーネントとして、特定の機能を実行するよう設計されたプログラム可能論理デバイスおよび／または特定用途向け集積回路などのハードウェアとして、もしくは、それらの組み合わせとして実装することができる。いくつかの実施形態において、モジュールは、コンピュータデバイス（パーソナルコンピュータ、サーバ、ネットワーク装置など）に本発明の実施形態に記載された方法を実行させるための複数の命令など、不揮発性記憶媒体（光学ディスク、フラッシュ記憶装置、携帯用ハードディスクなど）に格納することができるソフトウェア製品の形態で具現化されてよい。モジュールは、単一のデバイス上に実装されてもよいし、複数のデバイスにわたって分散されてもよい。モジュールの機能は、互いに統合されてもよいし、複数のサブモジュールにさらに分割されてもよい。
【００７９】
上述の実施形態は、理解し易いようにいくぶん詳しく説明されているが、本発明は、提供された詳細事項に限定されるものではない。本発明を実施する多くの代替方法が存在する。開示された実施形態は、例示であり、限定を意図するものではない。
適用例１：検索結果を順位付けるための方法であって、クエリ文字列を受信し、クエリ文字列に関連する対応する複数のターゲット文字列を含む複数の検索結果を取得し、前記クエリ文字列と、前記複数のターゲット文字列のそれぞれを分割し、複数の組み合わせを形成するために、前記クエリ文字列内の分割部分と、各前記ターゲット文字列内の分割部分とを対にし、単語の組み合わせと各単語の組み合わせに対する重みとのマッピングに基づいて、前記複数の組み合わせに対応する複数の重みを取得し、重みは単語の組み合わせに含まれる単語間の意味的相関の指標となり、前記複数のターゲット文字列それぞれに対応する前記重みに基づいて重み付けされた単語長を決定し、
前記複数のターゲット文字列を前記複数のターゲット文字列のそれぞれについて重み付けされた単語長に基づいて順位付けること、を備える、方法。
適用例２：適用例１に記載の方法において、単語の組み合わせと各単語の組み合わせに対する重みとの前記マッピングは、予め決定されている、方法。
適用例３：適用例２に記載の方法において、単語の組み合わせと各単語の組み合わせに対する重みとの前記マッピングは、１組の統計サンプルを取得し、前記１組の統計サンプルから第１の単語および第２の単語を選択し、前記第１および第２の単語の両方が前記統計サンプル内で出現する回数をＣ（前記第１の単語、前記第２の単語）としてカウントし、前記第２の単語が前記統計サンプル内で出現する回数をΣＣ（Ｙi、前記第２の単語）としてカウントし、Ｙiは前記第２の単語と一緒に出現するそれぞれの前記単語を表し、前記第１および第２の単語の両方が前記統計サンプル内で出現する回数と、前記第２の単語が前記統計サンプル内で出現する回数とに基づいて、前記第２の単語が出現する条件のもとでの前記第１の単語の出現確率Ｐを計算し、前記第２の単語の検索の際に、前記第１および第２の単語の間の意味的相関の指標となる重みをＷ＝１−Ｐによって決定し、Ｗは前記重みであり、Ｐは前記第２の単語が出現する前記条件のもとでの前記第１の単語の前記確率であり、前記統計サンプル内の単語の組み合わせの間の意味的相関の指標となる前記重みを決定するために、前記選択、カウント、計算、および、決定を繰り返し、前記単語の組み合わせと各単語の組み合わせに対する重みとの前記マッピングを格納すること、によって決定される、方法。
適用例４：適用例３に記載の方法であって、前記統計サンプルは、ウェブページ、ユーザ検索ログ、または、ユーザ選択ログから取得される、方法。
適用例５：適用例１に記載の方法であって、前記重み付けされた単語長は、最短スライディングウィンドウの前記重み付けされた単語長であり、前記重みから前記重み付けされた単語長を決定して、それぞれの前記ターゲット文字列を順位付けすることは、前記クエリ文字列の分割単語に対する前記ターゲット文字列の分割単語の最小重み、または、前記ターゲット文字列の分割単語に対する前記クエリ文字列の分割単語の最小重みを決定し、前記最小重みに基づいて、ターゲット文字列について前記最短スライディングウィンドウの前記重み付けされた長さを計算し、前記ターゲット文字列の前記最短スライディングウィンドウの前記重み付けされた長さを比較すること、を含み、重み付けされた長さが短いターゲット文字列が、重み付けされた長さが長いターゲット文字列よりも高く順位付けされる、方法。
適用例６：適用例５に記載の方法であって、前記最小重みに基づいて、ターゲット文字列について前記最短スライディングウィンドウの前記重み付けされた長さを計算することは、以下の式に基づいており、
【数４】
0005597255.tif 000006
Ｗは重みを表し、Ｔiはターゲット文字列のｉ番目の分割単語を表し、ｋおよびｈはそれぞれ前記ターゲット文字列の前記最短スライディングウィンドウの開始位置および終了位置を表し、Ｑjは前記クエリ文字列のｊ番目の分割単語を表し、ｍは前記クエリ文字列の分割単語の数を表す、方法。
適用例７：検索結果を順位付けするための方法であって、クエリ文字列を受信し、クエリ文字列に関連する対応する複数のターゲット文字列を含む複数の検索結果を取得し、前記クエリ文字列と、前記複数のターゲット文字列のそれぞれを分割し、単語の組み合わせと単語の組み合わせに対する重みとのマッピングに基づいて、前記クエリ文字列の分割単語に対する各挿入単語の最小重みを決定し、単語の組み合わせと単語の組み合わせに対する重みとのマッピングに基づいて、前記ターゲット文字列の分割単語に対する各削除単語の最小重みを決定し、各挿入単語の前記最小重みおよび各削除単語の前記最小重みに少なくとも部分的に基づいて総編集距離を決定し、前記総編集距離に基づいて前記ターゲット文字列を順位付けること、を備える、方法。
適用例８：適用例７に記載の方法であって、前記クエリ文字列の分割単語に対する各挿入単語の最小重みを決定することは、単語の組み合わせと単語の組み合わせに対する重みとの前記マッピングに基づいて、前記クエリ文字列の分割単語に対する前記挿入単語の複数の重みを決定し、前記クエリ文字列のそれぞれの前記分割単語に対する前記挿入単語の前記最小重みを以下のように計算すること、を備え、
【数５】
0005597255.tif 000007
Ｗは重みを表し、Ｉtは挿入文字列のｔ番目の分割単語を表し、ｎは挿入された分割単語の数を表し、Ｑjは前記クエリ文字列のｊ番目の分割単語を表し、ｍは前記クエリ文字列の分割単語の数を表す、方法。
適用例９：適用例７に記載の方法であって、前記ターゲット文字列の分割単語に対する前記削除単語の前記最小重みを決定することは、単語の組み合わせと単語の組み合わせに対する重みとの前記マッピングに基づいて、前記ターゲット文字列の前記分割単語に対する前記削除単語の複数の重みを決定し、前記ターゲット文字列のそれぞれの前記分割単語に対する前記削除単語の前記最小重みを以下のように計算することと、を備え、
【数６】
0005597255.tif 000008
Ｗは重みを表し、Ｔiは前記ターゲット文字列のｔ番目の分割単語を表し、ｑは前記ターゲット文字列の分割単語の数を表し、Ｄdは前記削除単語内のｄ番目の分割単語を表し、ｐは削除された分割単語の数を表す、方法。
適用例１０：適用例７に記載の方法であって、前記総編集距離を決定することは、前記複数のターゲット文字列の複数の総編集距離をＷTotal＝ＷI＋ＷDとして計算することを含み、ＷTotalは前記総編集距離を表し、ＷIは前記クエリ文字列の分割単語に対する前記挿入単語の前記最小重みを表し、ＷDは前記複数のターゲット文字列の内の一ターゲット文字列の分割単語に対する前記削除単語の前記最小重みを表す、方法。
適用例１１：適用例７に記載の方法であって、さらに、各置換単語の最小重みを決定することを備え、前記総編集距離を決定することは、さらに、各置換単語の前記最小重みに基づき、前記総編集距離は、ＷTotal＝ＷI＋ＷD＋ＷCとして計算され、ＷTotalは前記総編集距離を表し、ＷIは前記クエリ文字列の分割単語に対する前記挿入単語の前記最小重みを表し、ＷDは前記複数のターゲット文字の内の一ターゲット文字列の分割単語に対する前記削除単語の前記最小重みを表し、ＷCは前記クエリ文字または前記ターゲット文字列の分割単語に対する前記置換単語の前記最小重みを表す、方法。
適用例１２：適用例１１に記載の方法であって、前記各置換単語の前記最小重みを決定することは、事前設定された固定値に前記置換単語の前記編集距離の前記最小重みを設定することを含む、方法。
適用例１３：適用例１１に記載の方法であって、前記各置換単語の前記最小重みを決定することは、前記置換単語の前記編集距離を、前記クエリ文字列の分割単語に対する前記挿入単語の前記最小重みと前記ターゲット文字列の前記分割単語に対する前記削除単語の前記最小重みとの合計値、平均値、または、最大値に設定することを含む、方法。
適用例１４：検索結果を順位付けるためのシステムであって、１または複数のプロセッサであって、クエリ文字列を受信し、クエリ文字列に関連する対応する複数のターゲット文字列を含む複数の検索結果を取得し、前記クエリ文字列と、各前記複数のターゲット文字列を分割し、複数の組み合わせを形成するために、前記クエリ文字列の分割部分を前記ターゲット文字列のそれぞれの分割部分と対にし、単語の組み合わせと単語の組み合わせに対する重みとのマッピングに基づいて、前記複数の組み合わせに対応する複数の重みを取得し、重みは単語の組み合わせに含まれる単語間の意味的相関の指標となり、前記複数のターゲット文字列のそれぞれに対応する前記重みに基づいて重み付けされた単語長を決定し、前記複数のターゲット文字列を前記複数のターゲット文字列のそれぞれについて重み付けされた単語長に基づいて順位付けることを実行するよう構成されている１または複数のプロセッサと、前記１または複数のプロセッサに接続され、前記１または複数のプロセッサに命令を提供するよう構成されている１または複数のメモリと、を備える、システム。
適用例１５：適用例１４に記載のシステムであって、単語の組み合わせと各単語の組み合わせに対する重みとの前記マッピングは、１組の統計サンプルを取得し、前記１組の統計サンプルから第１の単語および第２の単語を選択し、前記第１および第２の単語の両方が前記統計サンプル内で出現する回数をＣ（前記第１の単語、前記第２の単語）としてカウントし、前記第２の単語が前記統計サンプル内で出現する回数をΣＣ（Ｙi、前記第２の単語）としてカウントし、Ｙiは前記第２の単語と一緒に出現するそれぞれの前記単語を表し、前記第１および第２の単語の両方が前記統計サンプル内で出現する回数と、前記第２の単語が前記統計サンプル内で出現する回数とに基づいて、前記第２の単語が出現する条件のもとでの前記第１の単語の出現確率Ｐを計算し、前記第２の単語の検索の際に、前記第１および第２の単語の間の意味的相関の指標となる重みをＷ＝１−Ｐによって決定し、Ｗは前記重みであり、Ｐは前記第２の単語が出現する前記条件のもとでの前記第１の単語の前記確率であり、前記統計サンプル内の単語の組み合わせの間の意味的相関の指標となる前記重みを決定するために、前記選択、カウント、計算、および、決定を繰り返し、前記単語の組み合わせと各単語の組み合わせに対する重みとの前記マッピングを格納すること、によって決定される、システム。
適用例１６：適用例１４に記載のシステムであって、前記重み付けされた単語長は、最短スライディングウィンドウの前記重み付けされた単語長であり、前記重みから前記重み付けされた単語長を決定して、それぞれの前記ターゲット文字列を順位付けことは、前記クエリ文字列の分割単語に対する前記ターゲット文字列の分割単語の最小重み、または、前記ターゲット文字列の分割単語に対する前記クエリ文字列の分割単語の最小重みを決定し、前記最小重みに基づいて、ターゲット文字列について前記最短スライディングウィンドウの前記重み付けされた長さを計算し、前記ターゲット文字列の前記最短スライディングウィンドウの前記重み付けされた長さを比較すること、を含み、重み付けされた長さが短いターゲット文字列が、重み付けされた長さが長いターゲット文字列よりも高く順位付けされる、システム。
適用例１７：適用例１６に記載のシステムであって、前記最小重みに基づいて、ターゲット文字列について前記最短スライディングウィンドウの前記重み付けされた長さを計算することは、以下の式に基づいており、
【数７】
0005597255.tif 000009
Ｗは重みを表し、Ｔiはターゲット文字列のｉ番目の分割単語を表し、ｋおよびｈはそれぞれ前記ターゲット文字の前記最短スライディングウィンドウの開始位置および終了位置を表し、Ｑjは前記クエリ文字列のｊ番目の分割単語を表し、ｍは前記クエリ文字列の分割単語の数を表す、システム。
適用例１８：検索結果を順位付けるためのシステムであって、１または複数のプロセッサであって、クエリ文字列を受信し、クエリ文字列に関連する対応する複数のターゲット文字列を含む複数の検索結果を取得し、前記クエリ文字列と、前記複数のターゲット文字列のそれぞれを分割し、単語の組み合わせと単語の組み合わせに対する重みとのマッピングに基づいて、前記クエリ文字列の分割単語に対する各挿入単語の最小重みを決定し、単語の組み合わせと単語の組み合わせに対する重みとのマッピングに基づいて、前記ターゲット文字列の分割単語に対する各削除単語の最小重みを決定し、各挿入単語の前記最小重みおよび各削除単語の前記最小重みに少なくとも部分的に基づいて総編集距離を決定し、前記総編集距離に基づいて前記ターゲット文字列を順位付けることを実行するよう構成されている１または複数のプロセッサと、前記１または複数のプロセッサに接続され、前記１または複数のプロセッサに命令を提供するよう構成されている１または複数のメモリと、を備える、システム。
適用例１９：適用例１８に記載のシステムであって、前記クエリ文字列の分割単語に対する各挿入単語の最小重みを決定することは、単語の組み合わせと単語の組み合わせに対する重みとの前記マッピングに基づいて、前記クエリ文字列の分割単語に対する前記挿入単語の複数の重みを決定し、前記クエリ文字列のそれぞれの前記分割単語に対する前記挿入単語の前記最小重みを以下のように計算すること、を含み、
【数８】
0005597255.tif 000010
Ｗは重みを表し、Ｉtは挿入文字列のｔ番目の分割単語を表し、ｎは挿入された分割単語の数を表し、Ｑjは前記クエリ文字列のｊ番目の分割単語を表し、ｍは前記クエリ文字列の分割単語の数を表す、システム。
適用例２０：適用例７に記載の方法であって、前記ターゲット文字列の分割単語に対する前記削除単語の前記最小重みを決定することは、単語の組み合わせと単語の組み合わせに対する重みとの前記マッピングに基づいて、前記ターゲット文字列の前記分割単語に対する前記削除単語の複数の重みを決定し、前記ターゲット文字列のそれぞれの前記分割単語に対する前記削除単語の前記最小重みを以下のように計算すること、を備え、
【数９】
0005597255.tif 000011
Ｗは重みを表し、Ｔiは前記ターゲット文字列のｔ番目の分割単語を表し、ｑは前記ターゲット文字列の分割単語の数を表し、Ｄdは前記削除単語のｄ番目の分割単語を表し、ｐは削除された分割単語の数を表す、方法。
【図１】
0005597255.tif 000018
【図２】
0005597255.tif 000019
【図３】
0005597255.tif 000020
【図４】
0005597255.tif 000021
【図５】
0005597255.tif 000022