ターゲットページとは異なる文字セットおよび/または言語で書かれたクエリを使用する検索のためのシステムおよび方法
【課題】情報検索、より詳細には、検索される文章の少なくとも一部の文字セットまたは言語とは異なる文字セットまたは言語において書かれたクエリを使用して検索を実行するためのシステムおよび方法を提供すること。
【解決手段】本発明と合致する方法および装置により、ユーザは、曖昧な検索クエリを提出し、適切な検索結果を受け取ることが可能である。クエリは、検索されるデータの少なくとも一部の文字セットおよび/または言語とは異なる文字セットおよび/または言語を使用して表され得る。これらの文字セットおよび/または言語の間の変換は、連係されたテキストにおいて、言葉の使用を検証することによって実行され得る。確率は、それぞれの可能な変更に関連付けられ得る。改良は、検索結果を用いて、ユーザの相互作用を検証することによって、これらの確率に対してなされ得る。
【解決手段】本発明と合致する方法および装置により、ユーザは、曖昧な検索クエリを提出し、適切な検索結果を受け取ることが可能である。クエリは、検索されるデータの少なくとも一部の文字セットおよび/または言語とは異なる文字セットおよび/または言語を使用して表され得る。これらの文字セットおよび/または言語の間の変換は、連係されたテキストにおいて、言葉の使用を検証することによって実行され得る。確率は、それぞれの可能な変更に関連付けられ得る。改良は、検索結果を用いて、ユーザの相互作用を検証することによって、これらの確率に対してなされ得る。
【発明の詳細な説明】
【技術分野】
【0001】
(関連出願の参照)
本出願は、2000年12月26日に出願され、「METHODS AND APPARATUS FOR PROVIDING SEARCH RESULTS IN RESPONSE TO AN AMBIGUOUS SEARCH QUERY」と題された、米国特許出願シリアル番号第09/748,431号の一部継続であり、2000年7月6日に出願され、「DATA ENTRY AND SEARCH FOR HANDHELD DEVICES」と題された、米国特許仮出願シリアル番号第60/216,530号の優先権を、米国特許法第119条(e)に基づき主張し、その両方は、それらの全体においてここに援用される。
【0002】
(発明の分野)
本発明は一般に、情報検索に関する。より詳細には、検索される文章の少なくとも一部の文字セットまたは言語とは異なる文字セットまたは言語において書かれたクエリを使用して検索を実行するためのシステムおよび方法が開示される。
【背景技術】
【0003】
多くの検索エンジンは、エンドユーザが従来のキーボードなどのようなものを用いて検索クエリを入力するという想定の下で動作し、そこで、英数字の入力は難しいことではない。小さなデバイスがより一般的になってはいるが、しかしながら、この想定はいつも有効とは限らない。例えば、ユーザは、WAP(ワイヤレス・アプリケーション・プロトコル)規格をサポートする携帯電話を使用して、検索エンジンにクエリし得る。携帯電話などのデバイスは通常、データ入力インターフェースを有し、ユーザによる特定のアクション(例えばキーを押すなど)が一つ以上の英数字文字に対応し得る。WAP構成の詳細は、http://www1.wapforum.org/tech/documents/SPEC−WAPArch−19980439.pdf(「WAP 100 Wireless Application Protocol Architecture Specification」)にて利用可能である。
【0004】
通常の場合、WAPユーザは、検索クエリのページにナビゲートされ、ユーザが検索クエリを入力するフォームを提示される。従来の方法では、ユーザは、多数のキーを押して、特定の文字を選択し得る。標準の電話のキーパッドでは、ユーザは、例えば、文字「b」を選択する場合、「2」のキーを2回押す。または、文字「s」を選択したい場合は、「7」のキーを4回押す。従って、「ben smith」というクエリを入力するには、ユーザは通常、223366077776444844という一連のキーを押して入力する必要があり、以下のような文字に対応する。
22→b
33→e
66→n
0→スペース
7777→s
6→m
444→i
8→t
44→h
ユーザが検索リクエストを入力した後、検索エンジンは、ユーザから文字を受け取り、あたかも、ユーザが従来のキーボードを用いて、デスクトップのブラウザからリクエストを受け取ったかのように、同様の方法で処理する。
【0005】
前述の例から理解できるように、データ入力のこの形式は、「ben smith」に対応する9つの英数字文字(スペースを含む)を入力するために18回もキー入力を必要とする点で、非効率的である。
【0006】
同様の困難さは、ターゲットでない(non−target)言語のキーボードを用いてクエリをタイピングする場合に生じ得る。例えば、日本語のテキストは、ひらがな、カタナカ、および漢字などを含む様々な異なる文字セットを用いて表現され得、そのどれもが、ローマ字(Roman alphabet)に基づいた通常のASCIIキーボードを用いて容易に入力されるものではない。そのような状況において、ユーザはしばしば、日本の徳島市所在のJustSystem Corp.によって製造されたIchitaro(登録商標)などのようなワードプロセッサのソフトを使用し、romaji(日本語における音声的なローマ字(Roman alphabet)の表現)で書かれたテキストを、カタカナ、ひらがな、および漢字に変換することができる。ワードプロセッサソフトを使用し、ユーザはローマ字でクエリをタイピングし、次いで、ワードプロセッサのスクリーンから変換されたテキストを、ブラウザの検索ボックスへとカットアンドペーストする。このアプローチの不利な点は、相対的に遅く、面倒であり得、ユーザがワードプロセッサのコピーにアクセスすることが要求されるゆえ、コストの制約やメモリの制約などのために、ふさわしいとはいえない。
【0007】
それゆえ、曖昧な検索クエリに応じて、適切な検索結果を提供する方法および装置が必要とされるのである。
【発明の概要】
【課題を解決するための手段】
【0008】
具体化され、ここで広く記載される本発明と合致する方法および装置は、曖昧な検索クエリに応じた適切な検索結果を提供する。本発明と合致し、そのような方法は、ユーザからの一連の曖昧な情報構成要素を受け取ることを含む。その方法は、曖昧な情報構成要素を、より曖昧でない情報にマッピングする、マッピング情報を含む。このマッピング情報は、一連の曖昧な情報構成要素を、一つ以上の対応する一連の、より曖昧でない情報構成要素に変換するために使用される。一つ以上のこれらの一連の、より曖昧でない情報構成要素は検索エンジンへの入力として提供される。その検索結果は検索エンジンから得られ、ユーザに提示される。
【0009】
付け加えて、システムおよび方法は、検索される文書の少なくとも一部の文字セットまたは言語とは異なる文字セットにて表されたクエリを用いて検索を実行することが開示される。本発明の実施形態により、ユーザは、標準の入力デバイス(例えば、ASCIIキーボード)を用いてクエリをタイプすることができ、クエリをサーバにおいて適切な形式に変換させることができ(たとえば、ローマ字で書かれたクエリをカタカナ、ひらがな、および/または漢字に変換する)、ならびに、変換された形式に基づいて、検索結果を受け取ることができる。
【0010】
本発明は、プロセス、装置、システム、デバイス、方法、または、コンピュータ可読格納媒体、搬送波、またはコンピュータネットワークなどのコンピュータ可読媒体を含み、多様な方法においてインプリメントされ得ることは理解されるべきであり、プログラムの命令は、光学式または電気の通信線を介して送信される。いくつかの発明の実施形態は以下に記載される。
【0011】
一実施形態において、方法は、クエリの言葉を、一つの言語および/または文字セットから別のものへと、自動的に変換することが記載される。所定のクエリの言葉を含むアンカーテキストの第1のセットが識別され、それはアンカーテキストが提示する文書(例えばウェブページなど)のセットである。次いで、第2のフォーマットで書かれ、同じ文書のセットを提示するアンカーテキストの第2のセットが識別される。アンカーテキストの第2のセットは、次いで、分析され、第1のフォーマットにおける所定のクエリの言葉の表示が、第2のフォーマットにおける所定のクエリの言葉の表示に対応する確率を得る。
【0012】
別の実施形態において、確率辞書が作成され、第1のフォーマット(例えば、言語および/または文字セット)で書かれた言葉を、第2のフォーマット(例えば、別の言語および/または文字セット)にマッピングする。確率辞書は、第1のフォーマットで書かれたクエリを第2のフォーマットに変換するために使用される。変換されたクエリは、次いで、検索を実行するために使用され、その結果は、ユーザに戻される。一部の実施形態において、検索結果を用いたユーザの相互作用は、監視され得、確率辞書における確率を更新するために使用される。また、一部の実施形態において、クエリ自体は、検索に先立って、代替的な言語および/または文字セットのマッピングを含むように拡張され得る。
【0013】
さらなる別の実施形態において、確率辞書を作成する方法が記載される。確率辞書は、第1のフォーマットにおける言葉を第2のフォーマットに変換するために使用され得る。辞書は、アンカーテキストまたはその言葉を含む他のデータを識別することによって、好ましくは言葉毎に作成される。次に、アンカーテキストまたは他のデータに連係される(aligned with)データは分析され、第1のフォーマットにおける所定の言葉が、第2のフォーマットにおける一つ以上の言葉にマッピングされる確率を決定する。
【0014】
さらなる別の実施形態において、第1の言語または文字セットに提供されたクエリは、一つ以上のクエリの言葉を含み、第1の言語または文字セットで書かれたアンカーテキストと、第1のアンカーテキストに対応し、第2の言語または文字セットで書かれたアンカーテキストとを比較することによって、第2の言語または文字セットに変換される。
【0015】
別の実施形態において、コンピュータプログラム製品は、第1のフォーマットで書かれた言葉を第2のフォーマットに変換するために提供される。コンピュータプログラム製品は、コンピュータシステムに、連係されたアンカーテキストを識別させ、第1のフォーマットにおける所定の言葉の表示が、第2のフォーマットにおける一つ以上の言葉に対応する確率を決定させるように動作可能である。
【0016】
別の実施形態において、方法は、曖昧なクエリを用いて検索を実行するために提供される。ユーザが第1のフォーマットにおいてクエリを入力する場合、それは、第2のフォーマットで書かれた一つ以上の変形の一群に変換される。次いで、検索は、変換された変形を用いて実行され、応答の情報は、ユーザに戻される。例えば、第1のフォーマットは、電話キーパッドを用いて入力された一連の数を含み得、第2のフォーマットは、英数字のテキスト(例えば、英語、ローマ字、romaja、ピンインなど)を含み得る。一部の実施形態において、一つ以上の変形の群は、所定の語彙に現れない、および/または、所定の低い確率の文字の組み合わせを含む、変換された変形を除去することによって選択される。一部の実施形態において、確率辞書は、検索が実行される前に、一つ以上の変形の群を、第3のフォーマットに変換する。例えば、確率辞書は、ローマ字、romaja、またはピンインの一つ以上の変形の群を、漢字、カタカナ、ひらがな、ハングル、ハンジャ、または伝統的な中国文字(traditional Chinese character)に変換するために使用され得、検索は、次いで、変換された変形を用いて実行され得る。
【0017】
本発明のこれらおよび他の特徴および利点は、以下の詳細な記載、ならびに、本発明の原理の例によって例示された、添付された図面に、さらに詳細に提示されている。
【0018】
例えば、本発明は以下の項目を提供する。
(項目1)
第1のフォーマットで書かれ、所定の言葉を含む第1のアンカーテキストのセットを識別することと、
該第1のアンカーテキストのセットが指す文書のセットを識別することと、
第2のフォーマットで書かれ、該識別された文書のセットを指す第2のアンカーテキストのセットを識別することと、
該第1のフォーマットにおける該所定の言葉の表示が該第2のフォーマットにおける該所定の言葉の表示に対応することを決定するために該第2のアンカーテキストのセットを分析することと
を包含する、方法。
(項目2)
前記第1のフォーマットは第1の文字セットを含み、前記第2のフォーマットは第2の文字セットを含む、項目1に記載の方法。
(項目3)
前記第1のフォーマットは第1の言語を含み、前記第2のフォーマットは第2の言語を含む、項目1に記載の方法。
(項目4)
前記第2のアンカーテキストのセットを分析することは、該第2のアンカーテキストのセットで最も頻繁に現われる言葉を識別することと、該第2のフォーマットにおいて、該最も頻繁に現われる言葉を前記所定の言葉の表示として指定することを含む、項目1に記載の方法。
(項目5)
前記第2のアンカーテキストのセットを分析することは、前記所定の言葉が前記第2のアンカーテキストのセットにおける言葉に対応する確率を計算することを包含する、項目1に記載の方法。
(項目6)
前記確率は、ベイズ法、ヒストグラムスムージング、カーネルスムージング、および縮小推定量のうちの少なくとも一つを用いて得られる、項目5に記載の方法。
(項目7)
前記所定の言葉が前記第2のアンカーテキストのセットにおける言葉に対応する前記確率は、該第2のアンカーテキストのセットにおける該言葉の発生回数を、該第2のアンカーテキストのセットにおける全言葉の総発生回数で割ることによって得られる、項目5に記載の方法。
(項目8)
前記第2のアンカーテキストのセットを分析することは、前記所定の言葉が該第2のアンカーテキストのセットにおけるそれぞれの言葉に対応する確率を計算することを包含する、項目1に記載の方法。
(項目9)
前記第2のアンカーテキストのセットを分析することは、該第2のアンカーテキストのセットにおいて最も頻繁に現われる言葉を識別することを包含する、項目1に記載の方法。
(項目10)
前記第1のフォーマットは、ローマ字、romaja、およびピンインから成る群から選択され、前記第2の文字セットは、カタカナ、ひらがな、漢字、ハングル、ハンジャ、および伝統的な中国文字から成る群から選択される、項目2に記載の方法。
(項目11)
前記文書がウェブページを構成する、項目1に記載の方法。
(項目12)
前記第1のフォーマットで書かれ、前記所定の言葉を含むクエリを得ることと、
少なくとも部分的に前記分析するステップに基づいて、該クエリを前記第2のフォーマットに変換することと、
該変換されたクエリに応じた、該第2のフォーマットで書かれた情報のためにデータベースを検索することと
をさらに包含する、項目1に記載の方法。
(項目13)
前記ステップは、前記列挙された順序で実行される、項目12に記載の方法。
(項目14)
ユーザーから第1のフォーマットで書かれたクエリを得ることと、
確率辞書を用いて該クエリを第2のフォーマットに変換することであって、該確率的辞書は該第1のフォーマットから該第2のフォーマットに言葉をマッピングする、ことと、
該変換されたクエリに応じた情報のためにデータベースを検索することと、
該第2のフォーマットで書かれた検索結果を該ユーザーに戻すことと
を包含する、検索方法。
(項目15)
前記ユーザーからの検索結果選択を得ることと、
言葉マッピングの前記確率辞書を修正するために該検索結果選択を用いることと
をさらに包含する、項目14に記載の検索方法。
(項目16)
前記修正は、前記確率辞書における少なくとも一つのマッピングに関連する少なくとも一つの確率を調整することを包含する、項目15に記載の検索方法。
(項目17)
前記クエリを前記第2のフォーマットに変換する前記ステップは、該クエリを拡張することを含む、項目14に記載の検索方法。
(項目18)
前記拡張されたクエリは、前記クエリ言葉の代替のエンコーディングを含む、項目17に記載の検索方法。
(項目19)
前記拡張されたクエリは、前記クエリ言葉の代替の言語変換を含む、項目17に記載の検索方法。
(項目20)
前記拡張されたクエリは、前記クエリ言葉の、代替のエンコーディングおよび代替の言語変換を含む、項目17に記載の検索方法。
(項目21)
前記拡張されたクエリは、前記クエリ言葉の前記代替のエンコーディングの同義語を含む、項目18に記載の検索方法。
(項目22)
確率辞書を作成する方法であって、該確率辞書は第1のフォーマットにおける言葉を第2のフォーマットにおける言葉にマッピングするものであり、該方法は、
所定の言葉に対して、該言葉を含む、前記第1のフォーマットにおける第1のデータのセットを識別することと、
該第1のデータのセットと連係する、前記第2のフォーマットにおける第2のデータのセットを識別することと、
該所定の言葉が該第2のデータのセットにおける一つ以上の言葉にマッピングするのに用いる一つ以上の確率を決定するために、該第2のデータのセットを分析することと
を包含する、該方法。
(項目23)
前記所定の言葉が前記第2のデータのセットにおける一つ以上の言葉にマッピングするのに用いる一つ以上の確率とともに、該所定の言葉を前記辞書に加えることをさらに包含する、項目22に記載の方法。
(項目24)
前記辞書に加えられるそれぞれの言葉に対して、第1のデータのセットを識別する前記ステップと、第2のデータのセットを識別する前記ステップと、該第2のデータのセットを分析する前記ステップを繰り返すことをさらに包含する、項目23に記載の方法。
(項目25)
前記第1のデータのセットは、一つ以上のウェブページのセットを指す第1のアンカーテキストのセットを含み、前記第2のデータのセットは、一つ以上のウェブページの同じセットを指す第2のアンカーテキストのセットを含む、項目22に記載の方法。
(項目26)
前記第1のデータのセットは第1の言語で書かれたテキストのセットを含み、前記第2のデータのセットは第2の言語で書かれた同じテキストのセットを含む、項目22に記載の方法。
(項目27)
前記所定の言葉が前記第2のデータのセットにおける言葉にマッピングするのに用いる前記確率は、該第2のデータのセットでの該言葉の前記発生回数を該第2のデータのセットにおける言葉の総回数で割ることによって計算される、項目22に記載の方法。
(項目28)
前記所定の言葉が少なくとも部分的にユーザーの検索結果選択の分析に基づいて前記第2のデータのセットにおける言葉にマッピングするのに用いる、前記確率を修正することをさらに包含する、項目22に記載の方法。
(項目29)
前記所定の言葉が少なくとも部分的にユーザーの以前のクエリの分析に基づいて前記第2のデータのセットにおける言葉にマッピングするのに用いる、前記確率を修正することをさらに包含する、項目22に記載の方法。
(項目30)
コンピュータ読み取り可能媒体に内蔵のコンピュータプログラム製品であって、該コンピュータプログラム製品は、コンピュータシステムによって実行される場合に該コンピュータシステムに動作を実行させるように操作可能な命令を含み、該動作が、
第1のフォーマットで書かれ、所定の言葉を含む第1のアンカーテキストのセットを識別することと、
該第1のアンカーテキストのセットが指すウェブページのセットを識別することと、
第2のフォーマットで書かれ、該識別されたウェブページのセットを指す第2のアンカーテキストのセットを識別することと、
該第1のフォーマットにおける該所定の言葉の表示が該第2のフォーマットにおける該所定の言葉の表示に対応する確率を決定することと
を包含する、コンピュータプログラム製品。
(項目31)
前記コンピュータシステムによって実行される場合に該コンピュータシステムに動作を実行させるように操作可能な命令をさらに含み、該動作が、
少なくとも部分的にユーザーの検索結果の選択の分析に基づいて、前記第1のフォーマットにおける前記所定の言葉の表示が前記第2のフォーマットにおける該所定の言葉の表示に対応する確率を修正することを包含する、項目30に記載のコンピュータプログラム製品。
(項目32)
前記コンピュータシステムによって実行される場合に該コンピュータシステムに動作を実行させるように操作可能な命令をさらに含み、該動作が、
少なくとも部分的にユーザーの以前のクエリの分析に基づいて、前記第1のフォーマットにおける前記所定の言葉の表示が前記第2のフォーマットにおける該所定の言葉の表示に対応する確率を修正することを包含する、項目30に記載のコンピュータプログラム製品。
(項目33)
前記確率は、ベイズ法、ヒストグラムスムージング、カーネルスムージング、および縮小推定量の少なくとも一つを用いて少なくとも部分的に決定される、項目30に記載のコンピュータプログラム製品。
(項目34)
第1のフォーマットで書かれた第1のテキスト本体を識別することと、
第2のフォーマットで書かれた第2のテキスト本体を識別することであって、該第2のテキスト本体は該第1のテキスト本体と連係する、識別することと、
該第1のテキスト本体における前記言葉の発生と該第2のテキスト本体における言葉の発生を比べて、該第1のテキスト本体における言葉と該第2のテキスト本体における言葉の間の変換辞書を作ることと
を包含する、変換方法。
(項目35)
前記変換辞書は該変換に関する一つ以上の確率を含む、項目34に記載の変換方法。
(項目36)
前記第1のフォーマットは第1の文字セットを含み、前記第2のフォーマットは第2の文字セットを含む、項目34に記載の変換方法。
(項目37)
前記第1のフォーマットは第1の言語を含み、前記第2のフォーマットは第2の言語を含む、項目34に記載の変換方法。
(項目38)
前記第1のテキスト本体はアンカーテキストを含み、前記第2のテキスト本体はアンカーテキストを含む、項目34に記載の変換方法。
(項目39)
第1のフォーマットで書かれた少なくとも一つのクエリ言葉を含むクエリを受け取ることと、
該クエリ言葉を第2のフォーマットで書かれた複数の変形に変換することと、
該クエリに応じた該第2のフォーマットで書かれた情報を検索するために、一つ以上の該変形を用いることと
を包含する方法。
(項目40)
前記第1のフォーマットは電話キーパッドから入力された数字の順序を含み、前記第2のフォーマットは英数字テキストを含む、項目39に記載の方法。
(項目41)
所定の辞書の一部でない前記複数の変形における変形を除去することによって、前記一つ以上の変形を得ることをさらに包含する、項目39に記載の方法。
(項目42)
所定の低い確率の文字組合せを含む前記複数の変形における変形を除去することによって前記一つ以上の変形を得ることをさらに包含する、項目39に記載の方法。
(項目43)
前記第1のフォーマットはローマ字、romaja、およびピンインから成る群から選択された文字セットで書かれた英数字テキストを含み、前記第2のフォーマットは漢字、カタカナ、ひらがな、ハングル、ハンジャ、および伝統的な中国文字から成る群から選択される文字セットで書かれた英数字テキストを含む、項目39に記載の方法。
(項目44)
電話キーパッドから入力された数字クエリを受け取ることと、
該数字クエリを第1のフォーマットにおけるポテンシャル英数字変換の群に変換することと、
所定の低い確率文字組合せを含むために決定されたポテンシャル変換を除去することと、
確率辞書を用いて、残りの英数字変換を該第1のフォーマットから第2のフォーマットに変換することと、
該第2のフォーマットにおいて該英数字変換を用いて検索を実行することと
を包含する方法。
(項目45)
前記第1のフォーマットはローマ字、romaja、およびピンインから成る群から選択された文字セットで書かれたテキストを含み、前記第2のフォーマットは漢字、カタカナ、ひらがな、ハングル、ハンジャ、および伝統的な中国文字から成る群から選択される文字セットで書かれたテキストを含む、項目44に記載の方法。
【図面の簡単な説明】
【0019】
【図1】本発明と合致する方法および装置がインプリメントされ得るシステムのブロック図を例示する。
【図2】本発明と合致する、クライアントデバイスのブロック図を例示する。
【図3】3つの文書を例示する図である。
【図4a】従来の英数字のインデックスを例示する。
【図4b】従来の英数字の検索クエリに応じて、検索結果を提供するフロー図である。
【図5a】曖昧な検索クエリに応じた検索結果を提供するための、本発明に合致したフロー図を例示する。
【図5b】数字の情報を数字の情報にマッピングする図を例示する。
【図5c】(記載なし)
【図6】曖昧な検索クエリに応じた検索結果を提供するための、本発明に合致した別のフロー図を例示する。
【図7】本発明の実施形態に従い、検索を実行する方法を例示する。
【図8】文字セットの変換の確率辞書を例示する。
【図9】確率辞書を構築するためのパラレルアンカーテキストの使用を例示する。
【図10】アンカーテキストを使用してリンクされた文書の集まりを例示する。
【図11】図11Aおよび図11Bは、図10に示されたアンカーテキストに基づく適当な変換の計算を例示する。
【図12】例示的な言葉の変換と関連した確率分配を示す。
【発明を実施するための形態】
【0020】
添付された図面は、この明細書にて援用され、その一部として構成され、本発明の実施形態を例示し、記載とともに、本発明の利点および原理を説明するのに役立つ。
【0021】
添付された図面にて例示される本発明の実施形態を詳細に参照する。同様の数字は、図面や以下に続く記載を通して、同様の部分を示す。以下に続く記載は、当業者が本発明を利用することができるように提示される。特定の実施形態および応用の記載は例としてのみ提供されるのであり、様々な修正は当業者にとって容易に明白である。例えば、多くの例がインターネットのウェブページに記載されているが、本発明の実施形態は、本、新聞、雑誌などの文章および/または情報の他のタイプを検索するために使用され得る。同様に、例示のために、日本語のテキストをローマ字からカタカナ、ひらがなおよび/または漢字へと変換されることが記載されるが、当業者に明らかなように、本発明のシステムおよび方法は、任意の適切な変換へと応用され得る。例えば、限定なしに、本発明の実施形態は、一部の他のフォーマット(例えば、ピンインやローマ字など)において受け取られるクエリに基づき、伝統的な漢字、または韓国のハングル文字またはハンジャ文字にて書かれたテキストを検索するために用いられ得る。ここで記載される一般的な原理は、本発明の趣旨および範囲から逸脱することなく他の実施形態および応用に適用され得る。したがって、本発明は、ここで開示される原理および特徴に合致する多数の代替、修正、および均等物を含み、最も広い範囲に従うものである。明瞭さのために、本発明に関連する領域で既知である技術的事項に関する詳細は、本発明を不必要に曖昧にしないように、詳細に記載されていない。
【0022】
A.概説
本発明に合致する方法および装置により、ユーザは、曖昧な検索クエリを提出し、場合によっては明確にされた検索結果を受け取ることが可能である。一実施形態において、標準の電話のキーパッドのユーザから受け取る一連の数が、場合によってはそれに対応する英数字のシーケンスのセットに変換される。これらの対応する英数字のシーケンスは、ブール式の「OR」結果を使用し、従来の検索エンジンへ入力として提供される。この方法において、検索エンジンは、ユーザが興味を持ちそうなものに対する検索結果を制限するのに役立つ。
【0023】
B.構成
本発明に合致する方法および装置がインプリメントされ得る、システム100が図1に示される。システム100は、ネットワーク140を介して、多数のサーバ120および130に接続される多数のクライアントデバイス110を含み得る。ネットワーク140は、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)、公衆交換電話網(PSTN)などのような電話網、インターネット、またはネットワークの組み合わせを含み得る。2つのクライアントデバイス110および3つのサーバ120および130は、単純に、ネットワーク140に接続されるように例示される。実際には、ほぼ同数のクライアントデバイスおよびサーバが存在し得る。たま、一部の場合においては、クライアントデバイスは、サーバ機能を実行し得、サーバはクライアントデバイス機能を実行し得る。
【0024】
クライアントデバイス110は、メインフレーム、ミニコンピュータ、パーソナルコンピュータ、ラップトップ、PDA(携帯情報端末)などのようなデバイスを含み得、ネットワーク140に接続可能である。クライアントデバイス110は、ネットワーク140を介してデータを送信し、あるいは、有線、無線、または光学式の接続を介してネットワーク140からデータを受信する。
【0025】
図2は、本発明と合致する例示的なクライアントデバイス110を図示する。クライアントデバイス110は、バス210、プロセッサ220、メインメモリ230、読み出し専用メモリ(ROM)240、記憶装置250、入力デバイス260、出力デバイス270、および通信インターフェース280を含み得る。
【0026】
バス210は、一つ以上の従来のバスを含み得、クライアントデバイス110の間で通信を可能にする。プロセッサ220は、従来のタイプのプロセッサまたはミニコンピュータを含み得、命令を解釈し実行する。メインメモリ230はランダムアクセスメモリ(RAM)または他のタイプのダイナミック記憶装置を含み得、プロセッサ220による実行のための情報および命令を格納する。ROM240は、従来のROMデバイスまたは他のタイプのスタティック記憶装置を含み得、プロセッサ220が使用するためのスタティックな情報および命令を格納する。記憶装置250は磁気および/または光学式の記憶媒体、ならびにそれに対応するドライブを含み得る。
【0027】
入力デバイス260は、キーボード、マウス、ペン、音声認識および/または生体認識メカニズムなどのような一つ以上の従来のメカニズムを含み得、それによって、ユーザは、クライアントデバイス110へ情報を入力することが可能である。出力デバイス270は、一つ以上の従来のメカニズム(ディスプレイ、プリンタ、スピーカなど)を含み得、ユーザに情報を出力する。通信インターフェース280は、任意の送受信器のようなメカニズムを含み得、クライアントデバイス110が他のデバイスおよび/またはシステムと通信することが可能となる。例えば、通信インターフェース280は、ネットワーク140などのようなネットワークを介して、別のデバイスまたはシステムと通信するためのメカニズムを含み得る。
【0028】
以下で詳細に記載するように、本発明と合致するクライアントデバイス110は、所定の検索に関連する動作を実行する。クライアントデバイス110は、メモリ230などのコンピュータ可読媒体に含まれるソフトウェアの命令を実行するプロセッサ220に応答した動作を実行し得る。コンピュータ可読媒体は一つ以上のメモリデバイスおよび/または搬送波として定義され得る。ソフトウェアの命令は、データ記憶装置250などのような別のコンピュータ可読媒体から、または、通信インターフェース280を介して別のデバイスから、メモリ230へと読み出され得る。メモリ230に含まれるソフトウェアの命令により、プロセッサ220は、以下で記載される、検索に関連する動きを実行する。あるいは、ハードウェアに組み込まれている回路は、ソフトウェアの命令の代わりに、またはソフトウェアの命令と組み合わされて使用され得、本発明と合致する処理をインプリメントし得る。したがって、本発明は、特定のハードウェアに組み込まれている回路とソフトウェアとの任意の組み合わせに限定されるわけではない。
【0029】
サーバ120および130は、メインフレーム、ミニコンピュータ、またはパーソナルコンピュータなどの、一つ以上のコンピュータシステムのタイプを含み得、ネットワーク140と接続することができ、サーバ120および130は、クライアントデバイス110と通信することができる。代替的な実施において、サーバ120および130は、一つ以上のクライアントデバイス110と直接に接続するメカニズムを含み得る。サーバ120および130は、ネットワーク140を介してデータを送信し得、あるいは、有線、無線、または光学式の接続を介して、ネットワーク140からデータを受信し得る。
【0030】
サーバは、クライアントデバイス110に対して、図2を参照し上記されたのと同様な方法にて、構成され得る。本発明と合致する実施において、サーバ120は、クライアントデバイス110によって使用可能である検索エンジン125を含み得る。サーバ130は、クライアントデバイス110によってアクセス可能である文書(またはウェブページ)を格納し得る。
【0031】
C.構成動作
図3は、3つの文書を表す図を示し、サーバ130のうちの一つにおける例示として格納され得る。
【0032】
第1の文書(文書1)は、「car repair」および「car rental」の2つのデータ入力を含み、底に「3」という数がある。第2の文書(文書2)は「video rental」というデータ入力を含む。第3の文書(文書3)は、「wine」、「champagne」、および「bar items」という3つのデータ入力を含み、ならびに、文書2へのリンク(または参照)を含む。
【0033】
例示を単純にするために、図3に示される文書は、英数字文字列の情報(例えば、「car」、「repair」、「wine」など)のみを含む。しかしながら、当業者は、他の状況において、文書は、音声的、視聴覚的な情報などといった、他のタイプの情報を含み得ることを理解する。
【0034】
図4aは、図3に示された文書に基づき、従来の英数字のインデックスを示す。インデックスの第1の列は英数字のリストを含み、第2の列は、それらの言葉に対応する文書のリストを含む。英数字の「3」などの一部の言葉は、一つの文書(この場合は文書1)に対応する(にある)。「rental」などの他の言葉は、多数の文書(この場合は文書1および2)に対応する。
【0035】
図4bは、検索エンジン125のような従来の検索エンジンが、図4aにて示されたインデックスをどのように使用し、英数字の検索クエリに応じた検索結果を提供するのかを示す。英数字のクエリは、任意の従来の技術を用いて生成され得る。図示のために、図4bは2つの英数字のクエリ、「car」および「wine」を表す。従来のアプローチの下では、検索エンジン125は、「car」などの英数字のクエリを受け取り(ステージ410)、その英数字のインデックスを用いて、どの文書がそのクエリに対応するのかを決定する(ステージ420)。この例において、従来の検索エンジン125は、図4aにて示されたインデックスを用い、「car」が文書1に対応し、検索結果としてユーザに、文書1(またはそれへの参照)を戻す。同様に、従来の検索エンジンは、「wine」が文書3に対応し、ユーザに文書3(またはそれへの参照)を戻すことを決定する(ステージ430)。
【0036】
図5aは、本発明と合致し、個々に図3および図4aに示された文書およびインデックスに基づき、数字の検索クエリに応じた検索結果を提供する好ましい技術のフロー図を示す。理解し易い例示のために、図5aは標準の電話端末のマッピングに基づき、数字のクエリを処理する特定の技術を記載する。しかし、当業者は、本発明に合致する他の技術もまた使用され得ることを理解する。
【0037】
ステージ510において、シーケンス「227」(数字の構成要素「2」、「2」、および「7」からなる)がユーザから受け取られる。ステージ520において、数字の構成要素が文字へとマッピングされる方法についての情報が得られる。ユーザが標準の電話キーパッドから情報を入力したと想定し、このマッピング情報が図5bに示される。図5bに示されるように、文字「a」、「b」、および「c」はそれぞれ、「1」にマッピングされ、文字「p」、「q」、および「r」はそれぞれ、「7」にマッピングされている。
【0038】
ステージ530において、このマッピング情報を用い、シーケンス「227」は、その英数字の相当物に変換される。図5bに示される情報に基づいて、シーケンス「227」に対応する文字の可能な組み合わせは36通りあり、その組み合わせは、aap、bap、cap、abp、bbp、・・・bar・・・car・・・ccsなどを含む。数字が可能な組み合わせ(例えば「aa7」)に含まれる場合、80通りの可能な組み合わせが存在する。全ての可能な英数字の相当物を生成するよりもむしろ、一部の語彙に基づき、生成された相当物を限定するのが望ましい。例えば、辞書、または以前の検索クエリの検索エンジンログなどに存在する英数字の相当物のみを生成することが望ましい。あるいは、既知の統計的な技術(例えば、所定の言葉が一緒に現れる確率など)を用いることによって英数字の相当物を限定することが望ましい。
【0039】
ステージ540において、これらの英数字の相当物は、論理「OR」動作を用いて、図4aおよび図4bを参照して記載されたような、従来の検索エンジンへの入力データとして提供される。例えば、検索エンジンへ提供される検索クエリは、「aap OR bap OR cap OR abp・・・OR bar・・・OR car」であり得る。全ての可能な英数字の相当物が検索クエリに提供され得るが、サブセットは、その代わりに、意図されない相当物を除去する従来の技術を用いて使用され得る。例えば、ユーザは、言葉の使用についての確率的な情報を引き出す技術を用いて、可能な組み合わせのより狭いリストを生成することが可能である。すなわち、ユーザは、「qu」で始まる組み合わせを含む(好む)が「qt」で始まる組み合わせを無視することが可能である。
【0040】
ステージ550において、検索結果は検索エンジンから得られる。なぜなら、「aap」や「abp」などの言葉は検索エンジンのインデックスには存在せず、それらは効果的に無視されるからである。実際には、図4bに示されたインデックス内に含まれた言葉は「car」および「bar」のみであり、戻ってきた検索結果は、文書1および文書3を参照するもののみである。ステージ560において、これらの検索結果はユーザに提示される。その検索結果は、検索エンジンによって提供されたのと同じ順序にて提示され得るか、または、ユーザの言語などの検討材料に基づき、記録され得る。ユーザが「bar」という言葉を含む文書のみに興味を持っていると想定すると、ユーザは、望んでいない結果(文書3)、および望んだ結果(文書1)を受け取る。ユーザの利点として、検索クエリを編成する3つのキーを押すことが必要とされるのみであるが、これは許容可能な対価であり得る。
【0041】
図6は、本発明に合致し、個々に図3および図4aに示された文書およびインデックスに基づき、数字の検索クエリに対応する検索結果を提供する好ましい技術の、別のフロー図を示す。このフロー図は、受け取られたシーケンスのサイズの増加が、ユーザによって望まれたものへの検索結果をどのように限定するのを助けるのかを例証する。理解し易い例示のために、図6は、標準の電話キーパッドのマッピングに基づいて、数字のクエリを処理する特定の技術を再び記載するが、当業者は、本発明に合致する他の技術が利用され得ることを理解する。
【0042】
ステージ610において、シーケンス「227 48367」(数字の構成要素、「2」、「2」、「7」、「4」、「8」、「3」、「6」、「7」からなる)が、ユーザから受け取られる。説明のために、シーケンス「227」を「数字ワード」(number
word)と呼び、全体のシーケンス「227 48367」を「数字フレーズ」(number phrase)と呼ぶ。数字ワードの可能な英数字の相当物を「文字ワード」(letter word)と呼び、数字フレーズの可能な英数字の相当物を「文字フレーズ」(letter phrase)と呼ぶ。
【0043】
ステージ620において、数字の構成要素が文字にマッピングされる方法についての情報が得られる。ステージ630において、同様のマッピング情報が、図5bに示されるように使用されると想定し、数字フレーズ「227 48367」は、それに対応する文字フレーズに変換される。図5bに示される情報に基づき、シーケンス「227 48367」に対応する、11664通りの可能な文字フレーズが存在する。
【0044】
ステージ640において、これらの文字フレーズは、論理「OR」動作を用いて、図4aおよび図4bを参照して記載された、従来の検索エンジンへの入力データとして提供される。例えば、検索エンジンに提供された検索クエリは、「aap gtdmp‘OR’aap htdmp‘・・・OR’bar items‘・・・OR’car items‘」であり得る。全ての可能な文字フレーズが検索エンジンに提供され得るが、サブセットは、その代わり、意図されていない文字フレーズを除去するために従来の技術を用いて、使用され得る。
【0045】
ステージ650において、検索結果は検索エンジンから得られる。なぜなら、多くの検索エンジンが、ソートされた正確なフレーズを含むそれらの文書を上位にランクさせるように設計されており、文書3は、最上位にランクされた検索結果であるからである(つまり、正確なフレーズ、「bar items」を含むからである)。例における文書で、ステージ620にて生成された他の文字フレーズのうちの一つを含む文書はない。さらに、多くの検索結果は、フレーズの個々の部分を含む検索結果を減らす(除去する)が、全体のフレーズではない。例えば、文書1は、それが、「car」という文字ワードを含むゆえに減らされ(除去され)、その文字ワードは文字フレーズの第1の部分に対応するが、それは、文字フレーズの第2の部分に対応する任意の文字ワードを含まない。最後に、「aap htdmp」などの文字フレーズは効果的に無視される。というのは、それらは、検索エンジンのインデックスに存在する文字ワードを含まないからである。
【0046】
ステージ660において、検索結果がユーザに提示される。例において、ユーザに示された第1の結果は文書3であり、それは、ユーザのクエリに最も適切なものである。文書1は、可能な文字フレーズのうちの一つを含まないゆえに、共に除去され得る。この方法において、ユーザは、最も適切な検索結果が提供される。
【0047】
図5および図6を参照した上記は、数字の情報を受け取り、それを英数字の情報にマッピングすることを参照してなされるが、当業者は、他の実施が本発明と合致して可能であることを理解する。例えば、ユーザによって押されたキーに対応する数のシーケンスを受け取る代わりに、受け取られたシーケンスは、ユーザによって押されたキーに対応する第1の文字からなり得る。つまり、「227」を受け取る代わりに、受け取られたシーケンスは「aap」であり得る。本発明と合致し、ステージ530または630において生成された、その相当する文字シーケンスは、「aap」に対応する他の文字シーケンス(例えば「bar」)であり得る。実際には、受け取られたシーケンスは、音声的、視聴覚的、または他の任意の情報構成要素のタイプを含み得る。
【0048】
シーケンスが受け取られるフォームに関係なく、受け取られたシーケンスは、情報が検索エンジンのインデックスに格納されるフォーマットに対応するシーケンスに変換されるのが、通常は好ましい。例えば、検索エンジンのインデックスが英数字のフォーマットにて記憶される場合、受け取られたシーケンスは英数字のシーケンスに変換されるべきである。
【0049】
さらに、情報構成要素の受け取られたシーケンスを変換するために使用されるマッピング技術は、ユーザの入力をデバイスによって生成される情報にマッピングするためのユーザのデバイスにて用いられるのと同じ技術であることが通常は望ましい。しかしながら、ユーザの入力に使用されるのとは異なるマッピング技術が使用されるのが好ましい場合もあり得る。
【0050】
また、本発明の実施形態により、ユーザは、ターゲットではない言語のキーボードを用いて入力された検索を実行することを可能にする。例えば、日本語のテキストを含むウェブページは漢字で書かれる一方、そのページを検索しようとするユーザは、ローマ字のアルファベットに基づいて標準のASCIIキーボード(または携帯電話機)にアクセスを有するのみである。
【0051】
図7は、そのような検索を実行する方法を例示する。図7において示されるように、ユーザは、標準の入力デバイス(例えば、ASCIIキーボード、携帯電話機、など)を使用してクエリをタイプし、そのクエリを検索エンジンに送る。そのクエリは、それに対応する文書の一部が書かれている(例えば漢字)文字セットとは異なる文字セット(例えばローマ字)で書かれ得る。検索エンジンは、クエリを受信し(ブロック702)、それを適切な形式に変換し(ブロック704)、従来の検索技術などを使用して、変換されたクエリに対応して、文書の検索を実行する(ブロック706)。次いで検索エンジンは、対応する文書のリスト(および/または、文書のコピー)を、ユーザに戻す(ブロック708)。例えば、図6と関連して上記されたものと同様の方法にて、結果はユーザに戻され得る。
【0052】
図7に示されるように、ユーザのクエリは、好ましくは、クライアントとは逆の、検索エンジンサーバ側にて変換され、変換を実行するための、特殊な目的のためのソフトウェアを得る必要から、ユーザを解放させる。しかしながら、他の実施形態において、変換の一部または全ては、クライアント側にて実行され得ることは理解される。付け加えて、一部の実施形態において、クエリは、電話機のキーパッドなどのようなデバイスを使用して入力され得る。そのような実施形態において、初期の数字のクエリは、図5および図6に関連する上記されたマッピング技術を用いて、英数字の形式(例えばローマ字)に変換され得、例えば、低い確率のマッピング(例えば、ローマ字においては生じない文字の組み合わせなどを含むマッピング)を除去するための、語彙および/または確率的な技術の応用を含む。いったん、クエリの英数字の変換が得られると、図7に示されるステップの残りが実行され得る(つまり、704、706、および708)。
【0053】
一つの文字セットまたは言語から別のものへの変換(つまり、図7におけるブロック704)は、様々な方法にて実行され得る。一つの技術は、クエリにおけるそれぞれの言葉を、ターゲットの言語または文字セットにおいて対応する言葉にマッピングするために、言葉の意味または変換の従来のスタティックの辞書を使用する。しかしながら、このアプローチの問題は、しばしば不正確な結果を生じることである。というのは、言葉はしばしば曖昧であり、クエリはしばしば、短すぎて、この曖昧さを解消する十分な手掛かりを提供しない。例えば、「bank」という言葉は、川の土手、金融機関、飛行機による演習、などを意味し得、理論上、正確に変換することは困難である。付け加えて、辞書が相対的に、大きくなく、および/または頻繁に更新されていない場合、滅多に使用しない言葉、スラング、イディオム、適切な名前などの、検索エンジンが出くわし得る全ての言葉の入力が含まれ得ない。
【0054】
本発明の実施形態はまた、一つの言語または文字セット(例えばASCII)から別のもの(例えば漢字)へ、クエリの言葉を変換するために、確率辞書(probabilistic dictionary)を使用して、一部または全ての問題を克服または改善するために使用され得る。好ましい実施形態において、確率辞書は、一つの言葉のセットを別の言葉のセットへとマッピングし、確率をそのマッピングそれぞれに関連付ける。便宜上、「言葉(term)」または「トークン」は、言葉(words)、フレーズ、および/または、スペースを含み得る一つ以上の文字のシーケンスを参照する。
【0055】
図8は、上記されたような確率辞書800の例を示す。図8に示された例示的な確率辞書800は、romaji(日本語のローマ字のアルファベットの表示)で書かれた言葉を、漢字(ローマ字ではない、表意文字ベースの日本語の文字セット)で書かれた言葉にマッピングする。説明を容易にするために、図8は、ローマ字の言葉を、「<term>romaji」とし、漢字の言葉を「<term>kanji」とする。漢字辞典に対する実際のローマ字において、実際のローマ字および漢字の言葉は、図8にて示される英語変換よりも、使用されることが理解される。したがって、図8は、本発明の実施形態の説明を容易にするために提供されるのであり、日本語のテキストの実際の文字および意味を例示しているのではない。
【0056】
辞書800は、様々なローマ字の言葉802のための808、810、812、814のデータ入力を含む。辞書はまた、漢字804におけるそれぞれの言葉の表示を含み、それぞれの表示が正しい場合の、対応する確率806に沿っている。例えば、ローマ字の言葉「bank」は、「steep slope」を意味する言葉に、0.3の確率でマッピングされ得、「financial institution」を意味する言葉には、0.4の確率でマッピングされ得、「airplane maneuver」には0.2の確率でマッピングされ得る。0.1の確率では、その言葉は「その他」にマッピングされ得、それは単に、辞書に存在し得ない言葉に、それぞれの言葉をマッピングさせる、包括的な方法である。
【0057】
再び、図8に示された例は、第1の文字セットまたは言語における所定の言葉(例えば、「bank」など)が、別の文字セットまたは言語において2つ以上の言葉にマッピングされ得ることを例示するように構成されることが理解される。しかしながら、当業者が理解するように、明瞭さのために、図8における特定の例は、英語の言葉や意味を使用する原理を例示しており、「bank」などの言葉の実際のローマ字表示は、例えば、その英語の相当物と同じような方法にて曖昧ではあり得ない(例えば、financial institutionとairplane maneuverとの言葉の間で、ローマ字に曖昧さは存在し得ない)。また、理解すべきことは、説明を容易にするために、図8に示される辞書は、他の点においても単純化されている。例えば、実施の確率辞書は、それぞれの言葉の、さらに多くのマッピングを含み得、または、所定の確率閾値を超過するマッピングを含み得る。
【0058】
本発明の好ましい実施形態は、そのような確率辞書を用い、一つの言語および/または文字セットにおいて表現されたクエリを、別の言語および/または文字セットに変換し、それにより、ユーザが、元々のクエリとは異なる文字セットおよび/または言語にて書かれた文書を発見することを可能にする。例えば、ユーザがローマ字で「cars」というクエリを入力した場合、確率辞書は、「cars」というローマ字の言葉を、「cars」という漢字の言葉へとマッピングするために使用され得る。この方法において、クエリの文字セット(例えばローマ字)とマッチングする文書の文字セット(例えば漢字)とが同じではない場合でさえも、ユーザは、それらのクエリに関連する文書を発見することができる。この特定の例において、クエリの実際の言語は変化せず(ローマ字および漢字は日本語を表現するために使用される)、文字エンコードのみが変化することに注意されたい。
【0059】
別の例として、ASCIIの英語における「tired」という言葉は、Latin1の文字エンコードを用いたドイツ語における「muede」という言葉にマッピングされ得る。というのは、ウムラウトuという文字は、ASCIIに存在しないからである。この例において、辞書は、辞書は他の言語に変換され(英語からドイツ語)、他の文字エンコード(ASCIIからLatin1)へと変換されることに注意されたい。
【0060】
好ましい実施形態において、上記されたマッピング辞書は、自動的な方法において構築され、統計的な技術に関連して、ウェブ上で利用可能な情報を用いる。好ましい実施形態は、正確な変換に達するために、異なる言語および/または文字セットにて書かれたアンカーテキストなどのような、パラレルで連係されたバイリンガルのコーパスを用いる。このデータを用いて、好ましい実施形態は、言葉のマッピングの辞書を構築することが可能である。これは、例えば、単に言語Si(ソース言語)が、連係されたテキストの対(例えばアンカー、文、など)におけるトークンTj(ターゲット言語)と同時に生じる回数を数えることによってなされ得る。しかしながら、任意の適切な技術が用いられ得ることは理解されたい。十分に広く正確に連係されたセットが存在しない場合において、この方法は、相対的に曖昧な多対多のマッピングを生成し得る。したがって、例えば、S1は、一部の確率を用いて、T2、T3、T7およびT8にマッピングされ得ることが決定され得る。しかしながら、これは、以下で詳細に記載するように、許容可能であり、一部の実施形態において、追加的な改良が、それぞれのマッピングの個々の可能性(例えば、以前のユーザのクエリ、結果ページ上のアイテムのユーザ選択および/またはそのようなものを調べることによって)を増加させるためになされ得る。
【0061】
図9は、確率辞書を構築するための、パラレルアンカーテキストの使用を示す。アンカーテキストは、ウェブページ間(または、所定のウェブページ内の位置)のハイパーリンクに関連付けられたテキストを含む。例えば、ハイパーテキストマークアップ言語(HTML)において、「<A href=”http://www.abc.com”>Banks and Savings and Loans</A>」というコマンドは、「Banks and Savings and Loans」というテキストを、http://www.abc.comのウェブページを提示するハイパーリンクとして表示させる。「Banks and Savings and Loans」というテキストは、アンカーテキストと呼ばれ、通常は、提示されるウェブページ(例えば、www.abc.com)の短い記載を提供する。実際は、アンカーテキストは、しばしば、そのページ自体よりも、より正確なウェブページの記載を提供し、提示するウェブページの性質を決定するのに、特に有用であり得る。付け加えて、アンカーテキストにおける言葉の使用および配布は、しばしば、趣旨および長さにおいて、ユーザのクエリにて見出されるものに近い。また、所定のページを提示するアンカーの多くは、同じか、または高度に類似したテキストである場合がある。例えば、www.google.comを提示するアンカーは、単に、「Google」であるか、または、他のテキストとともに、この言葉を少なくとも使用する。したがって、例えばカタカナなど、www.google.comを提示する全てのアンカーを検証することで、「Google」のカタカナ変換は、最も高い頻度で現れる言葉を単に探すことによって、相対的に高い信頼度でもって推測され得る(可能であれば、単なる「ここをクリック」といったような、所定の低い情報内容を除去した後で)。本発明の好ましい実施形態は、正確な変換を提供するために、アンカーテキストのこれらの特性の利点を持つ。
【0062】
図9を参照すると、第1の文字セット(例えばASCII)に書かれた言葉を含むクエリを受け取ると(ブロック902)、サーバは、言葉にあるアンカーテキストのセットを検証し得る(ブロック904)。例えば、サーバは、その言葉を含むそれらのアンカーを識別するために、全ての既知のアンカーのインデックスを検証し得る。次に、それらのアンカーが提示するウェブページは識別され(ブロック906)、アンカーは、それらのページを提示するターゲット言語またはターゲット文字セット(例えば、ひらがな、カタカナ、および/または漢字)で書かれる(ブロック908)。システムはここで、2つの文書のセットを有する(そこでは、アンカーテキストは、文書のフォームと見なされる)。一つの文書のセット(例えば、もともとのASCIIのクエリを含むアンカー)におけるクエリの言葉の分配は、次いで、他の文書セット(例えば、パラレルアンカー)における変換されたフレーズの最も適当な候補を識別するために使用される。統計は、アンカーテキストが現れる頻度に関して計算され得、これらの統計は、アンカーテキストに見出される言葉の相対的な頻度または確率が、もともとのクエリの正しい変換であるかどうかを決定するために使用され得る(ブロック910)。多数の言葉を有するクエリに対して、上記のプロセスは、それぞれの言葉に対して繰り返され得、または、全体のクエリは、単一の言葉として扱われ得、あるいは、一部の他の適切な言葉の群が使用され得る。例えば、クエリが「big houses」である場合、可能な変換の辞書は、そのフレーズを含む、連係されたアンカーテキストを見出すことによって構築され得る。同様に、クエリが3つ以上の言葉を含む場合、適切なマッピングを決定するための経験は、クエリの言葉の適切なサブセットを取り上げ、それらの言葉の結果を生成することによって構築され得る。
【0063】
図9に示される方法において変換を実行する利点は、変換システムが一つの言語または文字セットにおける言葉とターゲットセットにおけるそれらとの間のマッピングの予備的知識を必要としない。その代わり、マッピングは、統計的分析を実行するために利用可能であるデータの本体に基づいて、ダイナミックに決定され得る。したがって、例えば、従来のスタティックな辞書を維持する労力または費用(例えば、言語的分析および調査)を負うことなしに、スラング、イディオム、適切な名前などに対する正確な変換を発見することが可能である。
【0064】
前述の変換の例示的な実施形態は、ここで、図10〜図12と関連して記載される。この例において、ユーザは「house」というクエリの言葉を入力し、スペイン語で書かれた検索結果(または、単に、クエリの言葉の変換)を得ることを望んでいると想定する。サーバは、英語の「house」を、スペイン語の相当物に変換することを企てる。
【0065】
図10を参照すると、様々なウェブページ959、961、963、965が、アンカーテキスト960、962、964、966を介して、ページ972および974にリンクされる。一部のページおよびそれらに関連するアンカーテキストは、英語で書かれており(つまり、ページ959a〜959eおよび963a〜963t)、一部はスペイン語で書かれている(ページ961a〜961eおよび965a〜965j)。サーバは、第1に、「house」という言葉を使用する全てのアンカーの位置を突き止める。これらのアンカーは、例えば、サーバにおいて格納されたアンカーテキストのインデックスを検索することによって、位置が突き止められ得る。そのようなインデックスを使用して、サーバは第1に5つのアンカー960を見出し得、それぞれが「big house」というフレーズを使用し、ウェブページ972を提示する。サーバはまた、次に、ページ972を提示する5つのターゲット言語(例えばスペイン語)のアンカー962が存在することを決定する。図10に示される例において、これらのアンカーは「casa grande」というテキストを含む。同じページ(アンカー960およびアンカー962など)、またはそれに対して所定の関係を有するページに提示されるアンカーは、「連係(aligned)」されているといい、そこでは、より一般的な意味では、配置が通常、連係されたアイテムの相当物(またはほぼ相当物)を意味する。
【0066】
図11Aは、それぞれのターゲット言語の言葉は、ターゲット言語のアンカー962に現れる頻度を示す。図11Aに示されるように、「casa」および「grande」はそれぞれ、5回現れる(つまり、それぞれのアンカー962に一度)。したがって、ターゲットアンカー962に現れる、トータルで10の言葉(つまり、5つのアンカーのそれぞれにおいて、アンカー毎に2つの言葉)から、「casa」は半分を占め、「grande」はもう半分を占める。したがって、図11Aで示されるように、この時点で、「house」という言葉は、「casa」および「grande」の両方の言葉が等しい頻度で現れるゆえに、等しい確率で、「casa」または「grande」のいずれかにマッピングされ得る。
【0067】
しかしながら、図10にて示されるように、システムはまた、「house」という言葉を含む20個の英語のアンカー964を見出し、ページ974に提示し、ならびに、「casa」という言葉を含む10個のスペイン語のアンカー966を見出し、ページ974を提示する。図11Bにて示されるように、「house」という言葉は、「casa」という言葉に、0.75の確率(つまり、15/20)でマッピングされ、「grande」という言葉に、0.25の確率(つまり5/20)でマッピングされる。これらの確率は、そのターゲット言語のアンカーにおけるそれぞれの言葉の出現回数のトータル(「casa」の場合は15)を、ターゲット言語のアンカーにおける言葉のトータル数(重複を含む)によって、単に割ることによって計算される(つまり、20の言葉とは、アンカー962に含まれる10、および964に含まれる10)。代替的には、または追加的には、他の技術が、所定の変換またはマッピングの確率を計算および/または改良するために使用され得る。例えば、当業者が理解するように、任意の様々な既知の技術は、ベイズ法(Bayesian methods)、ヒストグラムスムージング(histogram smoothing)、カーネルスムージング(kernel smoothing)、縮小推定量(shrinkage estimators)、および/または他の推定方法などの確率推定の分散エラーを減少させるために使用され得る。
【0068】
さらなるアンカーテキストが利用可能である場合、確率は、一層さらに改良され得る。例えば、最終確率分配は、図12にて示されたものと同様であり得、「house」は、相対的に高確率で、「casa」、および、それに接尾語が付いた形式「casita」にマッピングされ、幾分か低い確率で、「casino」および
【0069】
【数1】
【0070】
(スペイン語でmansionに相当する)にマッピングされ、僅かな確率で、「grande」にマッピングされる。したがって、正確な変換、およびほぼ同意語の識別は、変換される言語および/または文字セットの知識なしで得られ得る。
【0071】
クエリの言葉を変換すると、サーバは、変換を使用して検索を実行し得る。例えば、ユーザは「hotels in Kyoto」に対するローマ字のクエリを入力する場合、上記された技術は、サーバに、カタカナ、ひらがな、および漢字のクエリのフォームを推測させることができ、それらのクエリを使用して検索を実行させることができ、ならびに、適切なユーザインターフェース内で、ユーザへのそれらのクエリのフォームのそれぞれに対する、組み合わされた結果を提示させることができる。
【0072】
図10〜図12に関連して記載された例は、例示のために提供されるのであり、限定のためではなく、多くの変更がそこに表された方法論に対してなされ得ることは理解されるべきである。例えば、異なる統計的な技術が一定の確率に達するために使用され得、および/または、修正は、上記された基本的な技術に対してなされ得る。同様に、上記された変換技術は、単に、ユーザによって入力された言葉またはフレーズの変換を実行するために使用され得、関連するインターネット検索を実行し、または確率辞書を作成するために使用される必要はない。付け加えて、先行する例は、ユーザのクエリの受け取りのアプリケーションとに生じるものとして、変換プロセスを記載するが、他の実施形態においては、マッピングプロセスは、ユーザのクエリが受け取られる前に実行され得ることは理解されるべきである。そのような計算前のマッピングは、図8に記載されたような辞書に格納され得、次いで、それらが受け取られたときに、ユーザのクエリを変換するように適合される。最後に、連係されたアンカーテキストとは異なるテキストは、変換を実行するために使用され得ることは理解されるべきである。例えば、連係された文章または他のデータは、同様な方法にて使用され得る。多くの国では、一つ以上の公式言語または認められた言語が存在しており、新聞や定期刊行物はしばしばこれらの言語のそれぞれにて書かれた同じ記事を含む。これらのパラレルな変換は、言葉の変換の確率辞書を準備するために、前記されたアンカーテキストと同様の方法において使用され得る。
【0073】
したがって、好ましい実施形態により、有利にも、ユーザは、従来の方法において、検索クエリおよび/または変換要求を入力することができ、正確で自動の変換および検索を提供する。一部の実施形態において、追加の改良が上記された基本的なモデルに対してなされ得る。例えば、一部の実施形態において、優先(加重)は、もともとのクエリおよび/または他の連係されたアンカーにおける言葉の数と同様の言葉の数を含むアンカーに与えられ得る。例えば、図10に示されるシステムにおいて、優先は、ページ974に提示されるアンカーに与えられ得る。というのは、もともとのクエリと同様に、それらは、それぞれ単一の言葉を含むからである。同様に、「la casa grande」のテキストを含むアンカーがまたページ972に提示された場合、その加重は、適切な要因によって軽減され得、というのは、それが連係された他のアンカーよりも多くの言葉(例えば3つ)を含むからである。そのような加重スキームは、適切な要因によってこれらのアンカーの言葉と関連される頻度を増加させることによって、図11Bに示される確率計算に反映され得る。
【0074】
上記された変換プロセスはまた、検索それ自体の効率を改善するために利用され得る。例えば、確率辞書は、様々な変換およびもともとのクエリの言葉の同意語などを含む、進行中のクエリを拡張するために使用され得る。文書検索に先立つユーザのクエリを拡張することによって、同じ「概念」の同時検索が実行され得、それにより、検索結果は、ユーザが探しているものを含む可能性を増加させる。代替的には、または追加的には、確率辞書は、文書の言葉の拡張を提供することによって、通常の文書インデックス付けのプロセスを補うために使用され得る。例えば、文書にて見出される言葉は、確率辞書からの変換を用いて、文書のインデックスにおいて補われ得、その文書は、もともとの文書にて見出された同じ言葉を正確に使用しない検索によってさえも、位置を突き止められる可能性を増加させる。
【0075】
上記された変換技術を使用する場合に生じ得る問題は、データの希薄(例えば、「casa」を「house」にマップすることを最終的に決定するには十分なアンカーがない)、または、多様性の欠如(全てのアンカーが同じものを示す)などのためであり、システムは、十分に正確な確率のマッピングに達することが不可能であり得る。したがって、一部の実施形態において、確率マッピングは、ユーザの行動を検証することでさらに改良され得る。いくつかの例示的な技術が以下に記載される。
【0076】
例えば、再度、サーバが「house」に対する変換を得ることを望んでいる場合を想定する。しかしながら、見出され得るアンカーテキストが、「big house」というフレーズ、または「casa grande」というフレーズのいずれかを含むことを想定する。そのアンカーテキストにおける多様性の欠如のために、確率辞書は以下のマッピングに達し得る。
house→casa、0.5の確率
house→grande、0.5の確率
big→casa、0.5の確率
big→grande、0.5の確率
grande→house、0.5の確率
grande→big、0.5の確率
casa→house、0.5の確率
casa→big、0.5の確率
ここでユーザが「casa」という言葉を用いて検索エンジンにクエリすると想定する。この時点で、検索エンジンは、「casa」という言葉を含むページを返答し得、また、「house」という言葉をちょうど含むN結果と、「big」という言葉をちょうど含むM結果とを合わせる。実際には、NおよびMは、マッピングに内在する確率を考慮するように調整され得、その結果、相対的に見込みのないマッピングは、より少ない結果が表示されることになる。ユーザが、「big」という言葉を含む結果をクリックするよりも、「house」という言葉を含む結果を10倍、クリックした場合、マッピングの確率は、例えば、以下のように調整される。
house→casa、0.9の確率
house→grande、0.1の確率
big→casa、0.1の確率
big→grande、0.9の確率
grande→house、0.1の確率
grande→big、0.9の確率
casa→house、0.9の確率
casa→big、0.1の確率
実際の数は、クリックが考慮されるユーザの数、その言葉の両方を含むページのクリックの回数、結果のセットの中の、当該の言葉を含む結果の置換、および/またはそれらのようなものなど、他の様々な要因に依存し得ることに注意されたい。この例(つまり、0.1および0.9)に与えられた調整された確率は、例示の目的のためであることは理解されたい。当業者は、上記されたものなどのユーザフィードバックに与えられた実際の加重は、任意の適切な方法にてインプリメントされ得ることは理解する。
【0077】
また、前述の例は、ユーザフィードバックの使用の例を容易にするように簡易化されていることに注意されたい。例えば、一部のシステムにおいて、所定の変換を実行することを補助するために、他の変換から得られた情報を利用することが可能である。例えば、今提示された例において、「house」という言葉が「big house」という言葉を含んだアンカーテキストに現れる場合、「house」は、「grande」にマッピングされるよりも、より適切に「casa」にマッピングされることを決定することは可能であり得る。例えば、既に、「big」が非常に高確率で、および、十分に大きなデータのセットにわたって、「grande」にマッピングされるように決定されている場合(および、アンカーテキストが同意語のリストで構成されてない場合)、次いで、house−to−casaのマッピングは、たとえ、「house」または「casa」を含むアンカーが要領を得ない場合であっても、house−to−grandeのマッピングを介して、優先を与えられ得る。
【0078】
変換の正確さおよび/または検索結果の有用性はまた、ユーザのクエリセッションの履歴を検証することによって改善され得る。例えば、多くの場合、システムは、ユーザが入力した以前のクエリを知っている(例えば、クッキーまたはサーバ上のユーザアカウントに格納された情報などを介して)。この履歴データは、そのユーザからのクエリの、可能な意味をランクするために使用され得、飛行に関連するものから、フィッシングに関するクエリに対して「bank」を明確にする。したがって、このプロセスは、可能な変換のセットを狭めるために使用され得る。一部の実施形態において、ユーザインターフェースにて、「Xの検索を意図しますか?」(ここで、Xは所定の変換の優先を意味する)などのメッセージに関連して、それらを表示することによって、これらを示唆し得、その一方で、結果の第1のページにおいて、可能な再公式化のそれぞれからの結果の一部を表示する。ユーザが「…意図しますか?」によって示唆された代替のうちの一つを選択するか、結果ページに提示された結果のうちの一つを選択する場合、システムは、クエリの言葉の適当な変換、およびユーザの適当な検索バイアスに関する追加的な証拠を得る。これらの信号の両方は、次いで、システムによって利用され得、一般的な場合、およびユーザに特殊な場合の両方において、言葉のマッピングの適当な根拠を更新する(例えば、確率辞書において)。
【0079】
D.結論
上記されたように、本発明と合致する方法およびシステムは、曖昧な検索結果に応じて検索結果を提供し、言葉を他の文字セットおよび/または言語に変換するために使用され得る。様々な変換および検索技術、ならびにシステムが記載されている。しかしながら、前述の記載は、例示のために提示されるものであり、多くの修正および変更が、上記の教示に照らし合わせて、または、本発明の実施を通して、可能であることは理解されたい。例えば、前述の記載はクライアント−サーバ構成に基づいているが、当業者は、ピアツーピア構成もまた、本発明に合致して使用され得ることは理解されたい。さらに、記載された実施はソフトウェアを含むが、本発明は、ハードウェアとソフトウェアとの組み合わせ、またはハードウェアのみとして実施され得る。付け加えて、本発明の局面は、メモリに格納されるように記載されたが、当業者は、これらの局面もまた、ハードディスク、フロッピーディスク(登録商標)、またはCD−ROMなどのような二次的格納装置、インターネットからの搬送波、あるいは、RAMまたはROMの他の形式などの、他のタイプのコンピュータ可読媒体に格納され得る。本発明の範囲は、それゆえ、請求項およびそれらの均等物によって定義される。
【技術分野】
【0001】
(関連出願の参照)
本出願は、2000年12月26日に出願され、「METHODS AND APPARATUS FOR PROVIDING SEARCH RESULTS IN RESPONSE TO AN AMBIGUOUS SEARCH QUERY」と題された、米国特許出願シリアル番号第09/748,431号の一部継続であり、2000年7月6日に出願され、「DATA ENTRY AND SEARCH FOR HANDHELD DEVICES」と題された、米国特許仮出願シリアル番号第60/216,530号の優先権を、米国特許法第119条(e)に基づき主張し、その両方は、それらの全体においてここに援用される。
【0002】
(発明の分野)
本発明は一般に、情報検索に関する。より詳細には、検索される文章の少なくとも一部の文字セットまたは言語とは異なる文字セットまたは言語において書かれたクエリを使用して検索を実行するためのシステムおよび方法が開示される。
【背景技術】
【0003】
多くの検索エンジンは、エンドユーザが従来のキーボードなどのようなものを用いて検索クエリを入力するという想定の下で動作し、そこで、英数字の入力は難しいことではない。小さなデバイスがより一般的になってはいるが、しかしながら、この想定はいつも有効とは限らない。例えば、ユーザは、WAP(ワイヤレス・アプリケーション・プロトコル)規格をサポートする携帯電話を使用して、検索エンジンにクエリし得る。携帯電話などのデバイスは通常、データ入力インターフェースを有し、ユーザによる特定のアクション(例えばキーを押すなど)が一つ以上の英数字文字に対応し得る。WAP構成の詳細は、http://www1.wapforum.org/tech/documents/SPEC−WAPArch−19980439.pdf(「WAP 100 Wireless Application Protocol Architecture Specification」)にて利用可能である。
【0004】
通常の場合、WAPユーザは、検索クエリのページにナビゲートされ、ユーザが検索クエリを入力するフォームを提示される。従来の方法では、ユーザは、多数のキーを押して、特定の文字を選択し得る。標準の電話のキーパッドでは、ユーザは、例えば、文字「b」を選択する場合、「2」のキーを2回押す。または、文字「s」を選択したい場合は、「7」のキーを4回押す。従って、「ben smith」というクエリを入力するには、ユーザは通常、223366077776444844という一連のキーを押して入力する必要があり、以下のような文字に対応する。
22→b
33→e
66→n
0→スペース
7777→s
6→m
444→i
8→t
44→h
ユーザが検索リクエストを入力した後、検索エンジンは、ユーザから文字を受け取り、あたかも、ユーザが従来のキーボードを用いて、デスクトップのブラウザからリクエストを受け取ったかのように、同様の方法で処理する。
【0005】
前述の例から理解できるように、データ入力のこの形式は、「ben smith」に対応する9つの英数字文字(スペースを含む)を入力するために18回もキー入力を必要とする点で、非効率的である。
【0006】
同様の困難さは、ターゲットでない(non−target)言語のキーボードを用いてクエリをタイピングする場合に生じ得る。例えば、日本語のテキストは、ひらがな、カタナカ、および漢字などを含む様々な異なる文字セットを用いて表現され得、そのどれもが、ローマ字(Roman alphabet)に基づいた通常のASCIIキーボードを用いて容易に入力されるものではない。そのような状況において、ユーザはしばしば、日本の徳島市所在のJustSystem Corp.によって製造されたIchitaro(登録商標)などのようなワードプロセッサのソフトを使用し、romaji(日本語における音声的なローマ字(Roman alphabet)の表現)で書かれたテキストを、カタカナ、ひらがな、および漢字に変換することができる。ワードプロセッサソフトを使用し、ユーザはローマ字でクエリをタイピングし、次いで、ワードプロセッサのスクリーンから変換されたテキストを、ブラウザの検索ボックスへとカットアンドペーストする。このアプローチの不利な点は、相対的に遅く、面倒であり得、ユーザがワードプロセッサのコピーにアクセスすることが要求されるゆえ、コストの制約やメモリの制約などのために、ふさわしいとはいえない。
【0007】
それゆえ、曖昧な検索クエリに応じて、適切な検索結果を提供する方法および装置が必要とされるのである。
【発明の概要】
【課題を解決するための手段】
【0008】
具体化され、ここで広く記載される本発明と合致する方法および装置は、曖昧な検索クエリに応じた適切な検索結果を提供する。本発明と合致し、そのような方法は、ユーザからの一連の曖昧な情報構成要素を受け取ることを含む。その方法は、曖昧な情報構成要素を、より曖昧でない情報にマッピングする、マッピング情報を含む。このマッピング情報は、一連の曖昧な情報構成要素を、一つ以上の対応する一連の、より曖昧でない情報構成要素に変換するために使用される。一つ以上のこれらの一連の、より曖昧でない情報構成要素は検索エンジンへの入力として提供される。その検索結果は検索エンジンから得られ、ユーザに提示される。
【0009】
付け加えて、システムおよび方法は、検索される文書の少なくとも一部の文字セットまたは言語とは異なる文字セットにて表されたクエリを用いて検索を実行することが開示される。本発明の実施形態により、ユーザは、標準の入力デバイス(例えば、ASCIIキーボード)を用いてクエリをタイプすることができ、クエリをサーバにおいて適切な形式に変換させることができ(たとえば、ローマ字で書かれたクエリをカタカナ、ひらがな、および/または漢字に変換する)、ならびに、変換された形式に基づいて、検索結果を受け取ることができる。
【0010】
本発明は、プロセス、装置、システム、デバイス、方法、または、コンピュータ可読格納媒体、搬送波、またはコンピュータネットワークなどのコンピュータ可読媒体を含み、多様な方法においてインプリメントされ得ることは理解されるべきであり、プログラムの命令は、光学式または電気の通信線を介して送信される。いくつかの発明の実施形態は以下に記載される。
【0011】
一実施形態において、方法は、クエリの言葉を、一つの言語および/または文字セットから別のものへと、自動的に変換することが記載される。所定のクエリの言葉を含むアンカーテキストの第1のセットが識別され、それはアンカーテキストが提示する文書(例えばウェブページなど)のセットである。次いで、第2のフォーマットで書かれ、同じ文書のセットを提示するアンカーテキストの第2のセットが識別される。アンカーテキストの第2のセットは、次いで、分析され、第1のフォーマットにおける所定のクエリの言葉の表示が、第2のフォーマットにおける所定のクエリの言葉の表示に対応する確率を得る。
【0012】
別の実施形態において、確率辞書が作成され、第1のフォーマット(例えば、言語および/または文字セット)で書かれた言葉を、第2のフォーマット(例えば、別の言語および/または文字セット)にマッピングする。確率辞書は、第1のフォーマットで書かれたクエリを第2のフォーマットに変換するために使用される。変換されたクエリは、次いで、検索を実行するために使用され、その結果は、ユーザに戻される。一部の実施形態において、検索結果を用いたユーザの相互作用は、監視され得、確率辞書における確率を更新するために使用される。また、一部の実施形態において、クエリ自体は、検索に先立って、代替的な言語および/または文字セットのマッピングを含むように拡張され得る。
【0013】
さらなる別の実施形態において、確率辞書を作成する方法が記載される。確率辞書は、第1のフォーマットにおける言葉を第2のフォーマットに変換するために使用され得る。辞書は、アンカーテキストまたはその言葉を含む他のデータを識別することによって、好ましくは言葉毎に作成される。次に、アンカーテキストまたは他のデータに連係される(aligned with)データは分析され、第1のフォーマットにおける所定の言葉が、第2のフォーマットにおける一つ以上の言葉にマッピングされる確率を決定する。
【0014】
さらなる別の実施形態において、第1の言語または文字セットに提供されたクエリは、一つ以上のクエリの言葉を含み、第1の言語または文字セットで書かれたアンカーテキストと、第1のアンカーテキストに対応し、第2の言語または文字セットで書かれたアンカーテキストとを比較することによって、第2の言語または文字セットに変換される。
【0015】
別の実施形態において、コンピュータプログラム製品は、第1のフォーマットで書かれた言葉を第2のフォーマットに変換するために提供される。コンピュータプログラム製品は、コンピュータシステムに、連係されたアンカーテキストを識別させ、第1のフォーマットにおける所定の言葉の表示が、第2のフォーマットにおける一つ以上の言葉に対応する確率を決定させるように動作可能である。
【0016】
別の実施形態において、方法は、曖昧なクエリを用いて検索を実行するために提供される。ユーザが第1のフォーマットにおいてクエリを入力する場合、それは、第2のフォーマットで書かれた一つ以上の変形の一群に変換される。次いで、検索は、変換された変形を用いて実行され、応答の情報は、ユーザに戻される。例えば、第1のフォーマットは、電話キーパッドを用いて入力された一連の数を含み得、第2のフォーマットは、英数字のテキスト(例えば、英語、ローマ字、romaja、ピンインなど)を含み得る。一部の実施形態において、一つ以上の変形の群は、所定の語彙に現れない、および/または、所定の低い確率の文字の組み合わせを含む、変換された変形を除去することによって選択される。一部の実施形態において、確率辞書は、検索が実行される前に、一つ以上の変形の群を、第3のフォーマットに変換する。例えば、確率辞書は、ローマ字、romaja、またはピンインの一つ以上の変形の群を、漢字、カタカナ、ひらがな、ハングル、ハンジャ、または伝統的な中国文字(traditional Chinese character)に変換するために使用され得、検索は、次いで、変換された変形を用いて実行され得る。
【0017】
本発明のこれらおよび他の特徴および利点は、以下の詳細な記載、ならびに、本発明の原理の例によって例示された、添付された図面に、さらに詳細に提示されている。
【0018】
例えば、本発明は以下の項目を提供する。
(項目1)
第1のフォーマットで書かれ、所定の言葉を含む第1のアンカーテキストのセットを識別することと、
該第1のアンカーテキストのセットが指す文書のセットを識別することと、
第2のフォーマットで書かれ、該識別された文書のセットを指す第2のアンカーテキストのセットを識別することと、
該第1のフォーマットにおける該所定の言葉の表示が該第2のフォーマットにおける該所定の言葉の表示に対応することを決定するために該第2のアンカーテキストのセットを分析することと
を包含する、方法。
(項目2)
前記第1のフォーマットは第1の文字セットを含み、前記第2のフォーマットは第2の文字セットを含む、項目1に記載の方法。
(項目3)
前記第1のフォーマットは第1の言語を含み、前記第2のフォーマットは第2の言語を含む、項目1に記載の方法。
(項目4)
前記第2のアンカーテキストのセットを分析することは、該第2のアンカーテキストのセットで最も頻繁に現われる言葉を識別することと、該第2のフォーマットにおいて、該最も頻繁に現われる言葉を前記所定の言葉の表示として指定することを含む、項目1に記載の方法。
(項目5)
前記第2のアンカーテキストのセットを分析することは、前記所定の言葉が前記第2のアンカーテキストのセットにおける言葉に対応する確率を計算することを包含する、項目1に記載の方法。
(項目6)
前記確率は、ベイズ法、ヒストグラムスムージング、カーネルスムージング、および縮小推定量のうちの少なくとも一つを用いて得られる、項目5に記載の方法。
(項目7)
前記所定の言葉が前記第2のアンカーテキストのセットにおける言葉に対応する前記確率は、該第2のアンカーテキストのセットにおける該言葉の発生回数を、該第2のアンカーテキストのセットにおける全言葉の総発生回数で割ることによって得られる、項目5に記載の方法。
(項目8)
前記第2のアンカーテキストのセットを分析することは、前記所定の言葉が該第2のアンカーテキストのセットにおけるそれぞれの言葉に対応する確率を計算することを包含する、項目1に記載の方法。
(項目9)
前記第2のアンカーテキストのセットを分析することは、該第2のアンカーテキストのセットにおいて最も頻繁に現われる言葉を識別することを包含する、項目1に記載の方法。
(項目10)
前記第1のフォーマットは、ローマ字、romaja、およびピンインから成る群から選択され、前記第2の文字セットは、カタカナ、ひらがな、漢字、ハングル、ハンジャ、および伝統的な中国文字から成る群から選択される、項目2に記載の方法。
(項目11)
前記文書がウェブページを構成する、項目1に記載の方法。
(項目12)
前記第1のフォーマットで書かれ、前記所定の言葉を含むクエリを得ることと、
少なくとも部分的に前記分析するステップに基づいて、該クエリを前記第2のフォーマットに変換することと、
該変換されたクエリに応じた、該第2のフォーマットで書かれた情報のためにデータベースを検索することと
をさらに包含する、項目1に記載の方法。
(項目13)
前記ステップは、前記列挙された順序で実行される、項目12に記載の方法。
(項目14)
ユーザーから第1のフォーマットで書かれたクエリを得ることと、
確率辞書を用いて該クエリを第2のフォーマットに変換することであって、該確率的辞書は該第1のフォーマットから該第2のフォーマットに言葉をマッピングする、ことと、
該変換されたクエリに応じた情報のためにデータベースを検索することと、
該第2のフォーマットで書かれた検索結果を該ユーザーに戻すことと
を包含する、検索方法。
(項目15)
前記ユーザーからの検索結果選択を得ることと、
言葉マッピングの前記確率辞書を修正するために該検索結果選択を用いることと
をさらに包含する、項目14に記載の検索方法。
(項目16)
前記修正は、前記確率辞書における少なくとも一つのマッピングに関連する少なくとも一つの確率を調整することを包含する、項目15に記載の検索方法。
(項目17)
前記クエリを前記第2のフォーマットに変換する前記ステップは、該クエリを拡張することを含む、項目14に記載の検索方法。
(項目18)
前記拡張されたクエリは、前記クエリ言葉の代替のエンコーディングを含む、項目17に記載の検索方法。
(項目19)
前記拡張されたクエリは、前記クエリ言葉の代替の言語変換を含む、項目17に記載の検索方法。
(項目20)
前記拡張されたクエリは、前記クエリ言葉の、代替のエンコーディングおよび代替の言語変換を含む、項目17に記載の検索方法。
(項目21)
前記拡張されたクエリは、前記クエリ言葉の前記代替のエンコーディングの同義語を含む、項目18に記載の検索方法。
(項目22)
確率辞書を作成する方法であって、該確率辞書は第1のフォーマットにおける言葉を第2のフォーマットにおける言葉にマッピングするものであり、該方法は、
所定の言葉に対して、該言葉を含む、前記第1のフォーマットにおける第1のデータのセットを識別することと、
該第1のデータのセットと連係する、前記第2のフォーマットにおける第2のデータのセットを識別することと、
該所定の言葉が該第2のデータのセットにおける一つ以上の言葉にマッピングするのに用いる一つ以上の確率を決定するために、該第2のデータのセットを分析することと
を包含する、該方法。
(項目23)
前記所定の言葉が前記第2のデータのセットにおける一つ以上の言葉にマッピングするのに用いる一つ以上の確率とともに、該所定の言葉を前記辞書に加えることをさらに包含する、項目22に記載の方法。
(項目24)
前記辞書に加えられるそれぞれの言葉に対して、第1のデータのセットを識別する前記ステップと、第2のデータのセットを識別する前記ステップと、該第2のデータのセットを分析する前記ステップを繰り返すことをさらに包含する、項目23に記載の方法。
(項目25)
前記第1のデータのセットは、一つ以上のウェブページのセットを指す第1のアンカーテキストのセットを含み、前記第2のデータのセットは、一つ以上のウェブページの同じセットを指す第2のアンカーテキストのセットを含む、項目22に記載の方法。
(項目26)
前記第1のデータのセットは第1の言語で書かれたテキストのセットを含み、前記第2のデータのセットは第2の言語で書かれた同じテキストのセットを含む、項目22に記載の方法。
(項目27)
前記所定の言葉が前記第2のデータのセットにおける言葉にマッピングするのに用いる前記確率は、該第2のデータのセットでの該言葉の前記発生回数を該第2のデータのセットにおける言葉の総回数で割ることによって計算される、項目22に記載の方法。
(項目28)
前記所定の言葉が少なくとも部分的にユーザーの検索結果選択の分析に基づいて前記第2のデータのセットにおける言葉にマッピングするのに用いる、前記確率を修正することをさらに包含する、項目22に記載の方法。
(項目29)
前記所定の言葉が少なくとも部分的にユーザーの以前のクエリの分析に基づいて前記第2のデータのセットにおける言葉にマッピングするのに用いる、前記確率を修正することをさらに包含する、項目22に記載の方法。
(項目30)
コンピュータ読み取り可能媒体に内蔵のコンピュータプログラム製品であって、該コンピュータプログラム製品は、コンピュータシステムによって実行される場合に該コンピュータシステムに動作を実行させるように操作可能な命令を含み、該動作が、
第1のフォーマットで書かれ、所定の言葉を含む第1のアンカーテキストのセットを識別することと、
該第1のアンカーテキストのセットが指すウェブページのセットを識別することと、
第2のフォーマットで書かれ、該識別されたウェブページのセットを指す第2のアンカーテキストのセットを識別することと、
該第1のフォーマットにおける該所定の言葉の表示が該第2のフォーマットにおける該所定の言葉の表示に対応する確率を決定することと
を包含する、コンピュータプログラム製品。
(項目31)
前記コンピュータシステムによって実行される場合に該コンピュータシステムに動作を実行させるように操作可能な命令をさらに含み、該動作が、
少なくとも部分的にユーザーの検索結果の選択の分析に基づいて、前記第1のフォーマットにおける前記所定の言葉の表示が前記第2のフォーマットにおける該所定の言葉の表示に対応する確率を修正することを包含する、項目30に記載のコンピュータプログラム製品。
(項目32)
前記コンピュータシステムによって実行される場合に該コンピュータシステムに動作を実行させるように操作可能な命令をさらに含み、該動作が、
少なくとも部分的にユーザーの以前のクエリの分析に基づいて、前記第1のフォーマットにおける前記所定の言葉の表示が前記第2のフォーマットにおける該所定の言葉の表示に対応する確率を修正することを包含する、項目30に記載のコンピュータプログラム製品。
(項目33)
前記確率は、ベイズ法、ヒストグラムスムージング、カーネルスムージング、および縮小推定量の少なくとも一つを用いて少なくとも部分的に決定される、項目30に記載のコンピュータプログラム製品。
(項目34)
第1のフォーマットで書かれた第1のテキスト本体を識別することと、
第2のフォーマットで書かれた第2のテキスト本体を識別することであって、該第2のテキスト本体は該第1のテキスト本体と連係する、識別することと、
該第1のテキスト本体における前記言葉の発生と該第2のテキスト本体における言葉の発生を比べて、該第1のテキスト本体における言葉と該第2のテキスト本体における言葉の間の変換辞書を作ることと
を包含する、変換方法。
(項目35)
前記変換辞書は該変換に関する一つ以上の確率を含む、項目34に記載の変換方法。
(項目36)
前記第1のフォーマットは第1の文字セットを含み、前記第2のフォーマットは第2の文字セットを含む、項目34に記載の変換方法。
(項目37)
前記第1のフォーマットは第1の言語を含み、前記第2のフォーマットは第2の言語を含む、項目34に記載の変換方法。
(項目38)
前記第1のテキスト本体はアンカーテキストを含み、前記第2のテキスト本体はアンカーテキストを含む、項目34に記載の変換方法。
(項目39)
第1のフォーマットで書かれた少なくとも一つのクエリ言葉を含むクエリを受け取ることと、
該クエリ言葉を第2のフォーマットで書かれた複数の変形に変換することと、
該クエリに応じた該第2のフォーマットで書かれた情報を検索するために、一つ以上の該変形を用いることと
を包含する方法。
(項目40)
前記第1のフォーマットは電話キーパッドから入力された数字の順序を含み、前記第2のフォーマットは英数字テキストを含む、項目39に記載の方法。
(項目41)
所定の辞書の一部でない前記複数の変形における変形を除去することによって、前記一つ以上の変形を得ることをさらに包含する、項目39に記載の方法。
(項目42)
所定の低い確率の文字組合せを含む前記複数の変形における変形を除去することによって前記一つ以上の変形を得ることをさらに包含する、項目39に記載の方法。
(項目43)
前記第1のフォーマットはローマ字、romaja、およびピンインから成る群から選択された文字セットで書かれた英数字テキストを含み、前記第2のフォーマットは漢字、カタカナ、ひらがな、ハングル、ハンジャ、および伝統的な中国文字から成る群から選択される文字セットで書かれた英数字テキストを含む、項目39に記載の方法。
(項目44)
電話キーパッドから入力された数字クエリを受け取ることと、
該数字クエリを第1のフォーマットにおけるポテンシャル英数字変換の群に変換することと、
所定の低い確率文字組合せを含むために決定されたポテンシャル変換を除去することと、
確率辞書を用いて、残りの英数字変換を該第1のフォーマットから第2のフォーマットに変換することと、
該第2のフォーマットにおいて該英数字変換を用いて検索を実行することと
を包含する方法。
(項目45)
前記第1のフォーマットはローマ字、romaja、およびピンインから成る群から選択された文字セットで書かれたテキストを含み、前記第2のフォーマットは漢字、カタカナ、ひらがな、ハングル、ハンジャ、および伝統的な中国文字から成る群から選択される文字セットで書かれたテキストを含む、項目44に記載の方法。
【図面の簡単な説明】
【0019】
【図1】本発明と合致する方法および装置がインプリメントされ得るシステムのブロック図を例示する。
【図2】本発明と合致する、クライアントデバイスのブロック図を例示する。
【図3】3つの文書を例示する図である。
【図4a】従来の英数字のインデックスを例示する。
【図4b】従来の英数字の検索クエリに応じて、検索結果を提供するフロー図である。
【図5a】曖昧な検索クエリに応じた検索結果を提供するための、本発明に合致したフロー図を例示する。
【図5b】数字の情報を数字の情報にマッピングする図を例示する。
【図5c】(記載なし)
【図6】曖昧な検索クエリに応じた検索結果を提供するための、本発明に合致した別のフロー図を例示する。
【図7】本発明の実施形態に従い、検索を実行する方法を例示する。
【図8】文字セットの変換の確率辞書を例示する。
【図9】確率辞書を構築するためのパラレルアンカーテキストの使用を例示する。
【図10】アンカーテキストを使用してリンクされた文書の集まりを例示する。
【図11】図11Aおよび図11Bは、図10に示されたアンカーテキストに基づく適当な変換の計算を例示する。
【図12】例示的な言葉の変換と関連した確率分配を示す。
【発明を実施するための形態】
【0020】
添付された図面は、この明細書にて援用され、その一部として構成され、本発明の実施形態を例示し、記載とともに、本発明の利点および原理を説明するのに役立つ。
【0021】
添付された図面にて例示される本発明の実施形態を詳細に参照する。同様の数字は、図面や以下に続く記載を通して、同様の部分を示す。以下に続く記載は、当業者が本発明を利用することができるように提示される。特定の実施形態および応用の記載は例としてのみ提供されるのであり、様々な修正は当業者にとって容易に明白である。例えば、多くの例がインターネットのウェブページに記載されているが、本発明の実施形態は、本、新聞、雑誌などの文章および/または情報の他のタイプを検索するために使用され得る。同様に、例示のために、日本語のテキストをローマ字からカタカナ、ひらがなおよび/または漢字へと変換されることが記載されるが、当業者に明らかなように、本発明のシステムおよび方法は、任意の適切な変換へと応用され得る。例えば、限定なしに、本発明の実施形態は、一部の他のフォーマット(例えば、ピンインやローマ字など)において受け取られるクエリに基づき、伝統的な漢字、または韓国のハングル文字またはハンジャ文字にて書かれたテキストを検索するために用いられ得る。ここで記載される一般的な原理は、本発明の趣旨および範囲から逸脱することなく他の実施形態および応用に適用され得る。したがって、本発明は、ここで開示される原理および特徴に合致する多数の代替、修正、および均等物を含み、最も広い範囲に従うものである。明瞭さのために、本発明に関連する領域で既知である技術的事項に関する詳細は、本発明を不必要に曖昧にしないように、詳細に記載されていない。
【0022】
A.概説
本発明に合致する方法および装置により、ユーザは、曖昧な検索クエリを提出し、場合によっては明確にされた検索結果を受け取ることが可能である。一実施形態において、標準の電話のキーパッドのユーザから受け取る一連の数が、場合によってはそれに対応する英数字のシーケンスのセットに変換される。これらの対応する英数字のシーケンスは、ブール式の「OR」結果を使用し、従来の検索エンジンへ入力として提供される。この方法において、検索エンジンは、ユーザが興味を持ちそうなものに対する検索結果を制限するのに役立つ。
【0023】
B.構成
本発明に合致する方法および装置がインプリメントされ得る、システム100が図1に示される。システム100は、ネットワーク140を介して、多数のサーバ120および130に接続される多数のクライアントデバイス110を含み得る。ネットワーク140は、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)、公衆交換電話網(PSTN)などのような電話網、インターネット、またはネットワークの組み合わせを含み得る。2つのクライアントデバイス110および3つのサーバ120および130は、単純に、ネットワーク140に接続されるように例示される。実際には、ほぼ同数のクライアントデバイスおよびサーバが存在し得る。たま、一部の場合においては、クライアントデバイスは、サーバ機能を実行し得、サーバはクライアントデバイス機能を実行し得る。
【0024】
クライアントデバイス110は、メインフレーム、ミニコンピュータ、パーソナルコンピュータ、ラップトップ、PDA(携帯情報端末)などのようなデバイスを含み得、ネットワーク140に接続可能である。クライアントデバイス110は、ネットワーク140を介してデータを送信し、あるいは、有線、無線、または光学式の接続を介してネットワーク140からデータを受信する。
【0025】
図2は、本発明と合致する例示的なクライアントデバイス110を図示する。クライアントデバイス110は、バス210、プロセッサ220、メインメモリ230、読み出し専用メモリ(ROM)240、記憶装置250、入力デバイス260、出力デバイス270、および通信インターフェース280を含み得る。
【0026】
バス210は、一つ以上の従来のバスを含み得、クライアントデバイス110の間で通信を可能にする。プロセッサ220は、従来のタイプのプロセッサまたはミニコンピュータを含み得、命令を解釈し実行する。メインメモリ230はランダムアクセスメモリ(RAM)または他のタイプのダイナミック記憶装置を含み得、プロセッサ220による実行のための情報および命令を格納する。ROM240は、従来のROMデバイスまたは他のタイプのスタティック記憶装置を含み得、プロセッサ220が使用するためのスタティックな情報および命令を格納する。記憶装置250は磁気および/または光学式の記憶媒体、ならびにそれに対応するドライブを含み得る。
【0027】
入力デバイス260は、キーボード、マウス、ペン、音声認識および/または生体認識メカニズムなどのような一つ以上の従来のメカニズムを含み得、それによって、ユーザは、クライアントデバイス110へ情報を入力することが可能である。出力デバイス270は、一つ以上の従来のメカニズム(ディスプレイ、プリンタ、スピーカなど)を含み得、ユーザに情報を出力する。通信インターフェース280は、任意の送受信器のようなメカニズムを含み得、クライアントデバイス110が他のデバイスおよび/またはシステムと通信することが可能となる。例えば、通信インターフェース280は、ネットワーク140などのようなネットワークを介して、別のデバイスまたはシステムと通信するためのメカニズムを含み得る。
【0028】
以下で詳細に記載するように、本発明と合致するクライアントデバイス110は、所定の検索に関連する動作を実行する。クライアントデバイス110は、メモリ230などのコンピュータ可読媒体に含まれるソフトウェアの命令を実行するプロセッサ220に応答した動作を実行し得る。コンピュータ可読媒体は一つ以上のメモリデバイスおよび/または搬送波として定義され得る。ソフトウェアの命令は、データ記憶装置250などのような別のコンピュータ可読媒体から、または、通信インターフェース280を介して別のデバイスから、メモリ230へと読み出され得る。メモリ230に含まれるソフトウェアの命令により、プロセッサ220は、以下で記載される、検索に関連する動きを実行する。あるいは、ハードウェアに組み込まれている回路は、ソフトウェアの命令の代わりに、またはソフトウェアの命令と組み合わされて使用され得、本発明と合致する処理をインプリメントし得る。したがって、本発明は、特定のハードウェアに組み込まれている回路とソフトウェアとの任意の組み合わせに限定されるわけではない。
【0029】
サーバ120および130は、メインフレーム、ミニコンピュータ、またはパーソナルコンピュータなどの、一つ以上のコンピュータシステムのタイプを含み得、ネットワーク140と接続することができ、サーバ120および130は、クライアントデバイス110と通信することができる。代替的な実施において、サーバ120および130は、一つ以上のクライアントデバイス110と直接に接続するメカニズムを含み得る。サーバ120および130は、ネットワーク140を介してデータを送信し得、あるいは、有線、無線、または光学式の接続を介して、ネットワーク140からデータを受信し得る。
【0030】
サーバは、クライアントデバイス110に対して、図2を参照し上記されたのと同様な方法にて、構成され得る。本発明と合致する実施において、サーバ120は、クライアントデバイス110によって使用可能である検索エンジン125を含み得る。サーバ130は、クライアントデバイス110によってアクセス可能である文書(またはウェブページ)を格納し得る。
【0031】
C.構成動作
図3は、3つの文書を表す図を示し、サーバ130のうちの一つにおける例示として格納され得る。
【0032】
第1の文書(文書1)は、「car repair」および「car rental」の2つのデータ入力を含み、底に「3」という数がある。第2の文書(文書2)は「video rental」というデータ入力を含む。第3の文書(文書3)は、「wine」、「champagne」、および「bar items」という3つのデータ入力を含み、ならびに、文書2へのリンク(または参照)を含む。
【0033】
例示を単純にするために、図3に示される文書は、英数字文字列の情報(例えば、「car」、「repair」、「wine」など)のみを含む。しかしながら、当業者は、他の状況において、文書は、音声的、視聴覚的な情報などといった、他のタイプの情報を含み得ることを理解する。
【0034】
図4aは、図3に示された文書に基づき、従来の英数字のインデックスを示す。インデックスの第1の列は英数字のリストを含み、第2の列は、それらの言葉に対応する文書のリストを含む。英数字の「3」などの一部の言葉は、一つの文書(この場合は文書1)に対応する(にある)。「rental」などの他の言葉は、多数の文書(この場合は文書1および2)に対応する。
【0035】
図4bは、検索エンジン125のような従来の検索エンジンが、図4aにて示されたインデックスをどのように使用し、英数字の検索クエリに応じた検索結果を提供するのかを示す。英数字のクエリは、任意の従来の技術を用いて生成され得る。図示のために、図4bは2つの英数字のクエリ、「car」および「wine」を表す。従来のアプローチの下では、検索エンジン125は、「car」などの英数字のクエリを受け取り(ステージ410)、その英数字のインデックスを用いて、どの文書がそのクエリに対応するのかを決定する(ステージ420)。この例において、従来の検索エンジン125は、図4aにて示されたインデックスを用い、「car」が文書1に対応し、検索結果としてユーザに、文書1(またはそれへの参照)を戻す。同様に、従来の検索エンジンは、「wine」が文書3に対応し、ユーザに文書3(またはそれへの参照)を戻すことを決定する(ステージ430)。
【0036】
図5aは、本発明と合致し、個々に図3および図4aに示された文書およびインデックスに基づき、数字の検索クエリに応じた検索結果を提供する好ましい技術のフロー図を示す。理解し易い例示のために、図5aは標準の電話端末のマッピングに基づき、数字のクエリを処理する特定の技術を記載する。しかし、当業者は、本発明に合致する他の技術もまた使用され得ることを理解する。
【0037】
ステージ510において、シーケンス「227」(数字の構成要素「2」、「2」、および「7」からなる)がユーザから受け取られる。ステージ520において、数字の構成要素が文字へとマッピングされる方法についての情報が得られる。ユーザが標準の電話キーパッドから情報を入力したと想定し、このマッピング情報が図5bに示される。図5bに示されるように、文字「a」、「b」、および「c」はそれぞれ、「1」にマッピングされ、文字「p」、「q」、および「r」はそれぞれ、「7」にマッピングされている。
【0038】
ステージ530において、このマッピング情報を用い、シーケンス「227」は、その英数字の相当物に変換される。図5bに示される情報に基づいて、シーケンス「227」に対応する文字の可能な組み合わせは36通りあり、その組み合わせは、aap、bap、cap、abp、bbp、・・・bar・・・car・・・ccsなどを含む。数字が可能な組み合わせ(例えば「aa7」)に含まれる場合、80通りの可能な組み合わせが存在する。全ての可能な英数字の相当物を生成するよりもむしろ、一部の語彙に基づき、生成された相当物を限定するのが望ましい。例えば、辞書、または以前の検索クエリの検索エンジンログなどに存在する英数字の相当物のみを生成することが望ましい。あるいは、既知の統計的な技術(例えば、所定の言葉が一緒に現れる確率など)を用いることによって英数字の相当物を限定することが望ましい。
【0039】
ステージ540において、これらの英数字の相当物は、論理「OR」動作を用いて、図4aおよび図4bを参照して記載されたような、従来の検索エンジンへの入力データとして提供される。例えば、検索エンジンへ提供される検索クエリは、「aap OR bap OR cap OR abp・・・OR bar・・・OR car」であり得る。全ての可能な英数字の相当物が検索クエリに提供され得るが、サブセットは、その代わりに、意図されない相当物を除去する従来の技術を用いて使用され得る。例えば、ユーザは、言葉の使用についての確率的な情報を引き出す技術を用いて、可能な組み合わせのより狭いリストを生成することが可能である。すなわち、ユーザは、「qu」で始まる組み合わせを含む(好む)が「qt」で始まる組み合わせを無視することが可能である。
【0040】
ステージ550において、検索結果は検索エンジンから得られる。なぜなら、「aap」や「abp」などの言葉は検索エンジンのインデックスには存在せず、それらは効果的に無視されるからである。実際には、図4bに示されたインデックス内に含まれた言葉は「car」および「bar」のみであり、戻ってきた検索結果は、文書1および文書3を参照するもののみである。ステージ560において、これらの検索結果はユーザに提示される。その検索結果は、検索エンジンによって提供されたのと同じ順序にて提示され得るか、または、ユーザの言語などの検討材料に基づき、記録され得る。ユーザが「bar」という言葉を含む文書のみに興味を持っていると想定すると、ユーザは、望んでいない結果(文書3)、および望んだ結果(文書1)を受け取る。ユーザの利点として、検索クエリを編成する3つのキーを押すことが必要とされるのみであるが、これは許容可能な対価であり得る。
【0041】
図6は、本発明に合致し、個々に図3および図4aに示された文書およびインデックスに基づき、数字の検索クエリに対応する検索結果を提供する好ましい技術の、別のフロー図を示す。このフロー図は、受け取られたシーケンスのサイズの増加が、ユーザによって望まれたものへの検索結果をどのように限定するのを助けるのかを例証する。理解し易い例示のために、図6は、標準の電話キーパッドのマッピングに基づいて、数字のクエリを処理する特定の技術を再び記載するが、当業者は、本発明に合致する他の技術が利用され得ることを理解する。
【0042】
ステージ610において、シーケンス「227 48367」(数字の構成要素、「2」、「2」、「7」、「4」、「8」、「3」、「6」、「7」からなる)が、ユーザから受け取られる。説明のために、シーケンス「227」を「数字ワード」(number
word)と呼び、全体のシーケンス「227 48367」を「数字フレーズ」(number phrase)と呼ぶ。数字ワードの可能な英数字の相当物を「文字ワード」(letter word)と呼び、数字フレーズの可能な英数字の相当物を「文字フレーズ」(letter phrase)と呼ぶ。
【0043】
ステージ620において、数字の構成要素が文字にマッピングされる方法についての情報が得られる。ステージ630において、同様のマッピング情報が、図5bに示されるように使用されると想定し、数字フレーズ「227 48367」は、それに対応する文字フレーズに変換される。図5bに示される情報に基づき、シーケンス「227 48367」に対応する、11664通りの可能な文字フレーズが存在する。
【0044】
ステージ640において、これらの文字フレーズは、論理「OR」動作を用いて、図4aおよび図4bを参照して記載された、従来の検索エンジンへの入力データとして提供される。例えば、検索エンジンに提供された検索クエリは、「aap gtdmp‘OR’aap htdmp‘・・・OR’bar items‘・・・OR’car items‘」であり得る。全ての可能な文字フレーズが検索エンジンに提供され得るが、サブセットは、その代わり、意図されていない文字フレーズを除去するために従来の技術を用いて、使用され得る。
【0045】
ステージ650において、検索結果は検索エンジンから得られる。なぜなら、多くの検索エンジンが、ソートされた正確なフレーズを含むそれらの文書を上位にランクさせるように設計されており、文書3は、最上位にランクされた検索結果であるからである(つまり、正確なフレーズ、「bar items」を含むからである)。例における文書で、ステージ620にて生成された他の文字フレーズのうちの一つを含む文書はない。さらに、多くの検索結果は、フレーズの個々の部分を含む検索結果を減らす(除去する)が、全体のフレーズではない。例えば、文書1は、それが、「car」という文字ワードを含むゆえに減らされ(除去され)、その文字ワードは文字フレーズの第1の部分に対応するが、それは、文字フレーズの第2の部分に対応する任意の文字ワードを含まない。最後に、「aap htdmp」などの文字フレーズは効果的に無視される。というのは、それらは、検索エンジンのインデックスに存在する文字ワードを含まないからである。
【0046】
ステージ660において、検索結果がユーザに提示される。例において、ユーザに示された第1の結果は文書3であり、それは、ユーザのクエリに最も適切なものである。文書1は、可能な文字フレーズのうちの一つを含まないゆえに、共に除去され得る。この方法において、ユーザは、最も適切な検索結果が提供される。
【0047】
図5および図6を参照した上記は、数字の情報を受け取り、それを英数字の情報にマッピングすることを参照してなされるが、当業者は、他の実施が本発明と合致して可能であることを理解する。例えば、ユーザによって押されたキーに対応する数のシーケンスを受け取る代わりに、受け取られたシーケンスは、ユーザによって押されたキーに対応する第1の文字からなり得る。つまり、「227」を受け取る代わりに、受け取られたシーケンスは「aap」であり得る。本発明と合致し、ステージ530または630において生成された、その相当する文字シーケンスは、「aap」に対応する他の文字シーケンス(例えば「bar」)であり得る。実際には、受け取られたシーケンスは、音声的、視聴覚的、または他の任意の情報構成要素のタイプを含み得る。
【0048】
シーケンスが受け取られるフォームに関係なく、受け取られたシーケンスは、情報が検索エンジンのインデックスに格納されるフォーマットに対応するシーケンスに変換されるのが、通常は好ましい。例えば、検索エンジンのインデックスが英数字のフォーマットにて記憶される場合、受け取られたシーケンスは英数字のシーケンスに変換されるべきである。
【0049】
さらに、情報構成要素の受け取られたシーケンスを変換するために使用されるマッピング技術は、ユーザの入力をデバイスによって生成される情報にマッピングするためのユーザのデバイスにて用いられるのと同じ技術であることが通常は望ましい。しかしながら、ユーザの入力に使用されるのとは異なるマッピング技術が使用されるのが好ましい場合もあり得る。
【0050】
また、本発明の実施形態により、ユーザは、ターゲットではない言語のキーボードを用いて入力された検索を実行することを可能にする。例えば、日本語のテキストを含むウェブページは漢字で書かれる一方、そのページを検索しようとするユーザは、ローマ字のアルファベットに基づいて標準のASCIIキーボード(または携帯電話機)にアクセスを有するのみである。
【0051】
図7は、そのような検索を実行する方法を例示する。図7において示されるように、ユーザは、標準の入力デバイス(例えば、ASCIIキーボード、携帯電話機、など)を使用してクエリをタイプし、そのクエリを検索エンジンに送る。そのクエリは、それに対応する文書の一部が書かれている(例えば漢字)文字セットとは異なる文字セット(例えばローマ字)で書かれ得る。検索エンジンは、クエリを受信し(ブロック702)、それを適切な形式に変換し(ブロック704)、従来の検索技術などを使用して、変換されたクエリに対応して、文書の検索を実行する(ブロック706)。次いで検索エンジンは、対応する文書のリスト(および/または、文書のコピー)を、ユーザに戻す(ブロック708)。例えば、図6と関連して上記されたものと同様の方法にて、結果はユーザに戻され得る。
【0052】
図7に示されるように、ユーザのクエリは、好ましくは、クライアントとは逆の、検索エンジンサーバ側にて変換され、変換を実行するための、特殊な目的のためのソフトウェアを得る必要から、ユーザを解放させる。しかしながら、他の実施形態において、変換の一部または全ては、クライアント側にて実行され得ることは理解される。付け加えて、一部の実施形態において、クエリは、電話機のキーパッドなどのようなデバイスを使用して入力され得る。そのような実施形態において、初期の数字のクエリは、図5および図6に関連する上記されたマッピング技術を用いて、英数字の形式(例えばローマ字)に変換され得、例えば、低い確率のマッピング(例えば、ローマ字においては生じない文字の組み合わせなどを含むマッピング)を除去するための、語彙および/または確率的な技術の応用を含む。いったん、クエリの英数字の変換が得られると、図7に示されるステップの残りが実行され得る(つまり、704、706、および708)。
【0053】
一つの文字セットまたは言語から別のものへの変換(つまり、図7におけるブロック704)は、様々な方法にて実行され得る。一つの技術は、クエリにおけるそれぞれの言葉を、ターゲットの言語または文字セットにおいて対応する言葉にマッピングするために、言葉の意味または変換の従来のスタティックの辞書を使用する。しかしながら、このアプローチの問題は、しばしば不正確な結果を生じることである。というのは、言葉はしばしば曖昧であり、クエリはしばしば、短すぎて、この曖昧さを解消する十分な手掛かりを提供しない。例えば、「bank」という言葉は、川の土手、金融機関、飛行機による演習、などを意味し得、理論上、正確に変換することは困難である。付け加えて、辞書が相対的に、大きくなく、および/または頻繁に更新されていない場合、滅多に使用しない言葉、スラング、イディオム、適切な名前などの、検索エンジンが出くわし得る全ての言葉の入力が含まれ得ない。
【0054】
本発明の実施形態はまた、一つの言語または文字セット(例えばASCII)から別のもの(例えば漢字)へ、クエリの言葉を変換するために、確率辞書(probabilistic dictionary)を使用して、一部または全ての問題を克服または改善するために使用され得る。好ましい実施形態において、確率辞書は、一つの言葉のセットを別の言葉のセットへとマッピングし、確率をそのマッピングそれぞれに関連付ける。便宜上、「言葉(term)」または「トークン」は、言葉(words)、フレーズ、および/または、スペースを含み得る一つ以上の文字のシーケンスを参照する。
【0055】
図8は、上記されたような確率辞書800の例を示す。図8に示された例示的な確率辞書800は、romaji(日本語のローマ字のアルファベットの表示)で書かれた言葉を、漢字(ローマ字ではない、表意文字ベースの日本語の文字セット)で書かれた言葉にマッピングする。説明を容易にするために、図8は、ローマ字の言葉を、「<term>romaji」とし、漢字の言葉を「<term>kanji」とする。漢字辞典に対する実際のローマ字において、実際のローマ字および漢字の言葉は、図8にて示される英語変換よりも、使用されることが理解される。したがって、図8は、本発明の実施形態の説明を容易にするために提供されるのであり、日本語のテキストの実際の文字および意味を例示しているのではない。
【0056】
辞書800は、様々なローマ字の言葉802のための808、810、812、814のデータ入力を含む。辞書はまた、漢字804におけるそれぞれの言葉の表示を含み、それぞれの表示が正しい場合の、対応する確率806に沿っている。例えば、ローマ字の言葉「bank」は、「steep slope」を意味する言葉に、0.3の確率でマッピングされ得、「financial institution」を意味する言葉には、0.4の確率でマッピングされ得、「airplane maneuver」には0.2の確率でマッピングされ得る。0.1の確率では、その言葉は「その他」にマッピングされ得、それは単に、辞書に存在し得ない言葉に、それぞれの言葉をマッピングさせる、包括的な方法である。
【0057】
再び、図8に示された例は、第1の文字セットまたは言語における所定の言葉(例えば、「bank」など)が、別の文字セットまたは言語において2つ以上の言葉にマッピングされ得ることを例示するように構成されることが理解される。しかしながら、当業者が理解するように、明瞭さのために、図8における特定の例は、英語の言葉や意味を使用する原理を例示しており、「bank」などの言葉の実際のローマ字表示は、例えば、その英語の相当物と同じような方法にて曖昧ではあり得ない(例えば、financial institutionとairplane maneuverとの言葉の間で、ローマ字に曖昧さは存在し得ない)。また、理解すべきことは、説明を容易にするために、図8に示される辞書は、他の点においても単純化されている。例えば、実施の確率辞書は、それぞれの言葉の、さらに多くのマッピングを含み得、または、所定の確率閾値を超過するマッピングを含み得る。
【0058】
本発明の好ましい実施形態は、そのような確率辞書を用い、一つの言語および/または文字セットにおいて表現されたクエリを、別の言語および/または文字セットに変換し、それにより、ユーザが、元々のクエリとは異なる文字セットおよび/または言語にて書かれた文書を発見することを可能にする。例えば、ユーザがローマ字で「cars」というクエリを入力した場合、確率辞書は、「cars」というローマ字の言葉を、「cars」という漢字の言葉へとマッピングするために使用され得る。この方法において、クエリの文字セット(例えばローマ字)とマッチングする文書の文字セット(例えば漢字)とが同じではない場合でさえも、ユーザは、それらのクエリに関連する文書を発見することができる。この特定の例において、クエリの実際の言語は変化せず(ローマ字および漢字は日本語を表現するために使用される)、文字エンコードのみが変化することに注意されたい。
【0059】
別の例として、ASCIIの英語における「tired」という言葉は、Latin1の文字エンコードを用いたドイツ語における「muede」という言葉にマッピングされ得る。というのは、ウムラウトuという文字は、ASCIIに存在しないからである。この例において、辞書は、辞書は他の言語に変換され(英語からドイツ語)、他の文字エンコード(ASCIIからLatin1)へと変換されることに注意されたい。
【0060】
好ましい実施形態において、上記されたマッピング辞書は、自動的な方法において構築され、統計的な技術に関連して、ウェブ上で利用可能な情報を用いる。好ましい実施形態は、正確な変換に達するために、異なる言語および/または文字セットにて書かれたアンカーテキストなどのような、パラレルで連係されたバイリンガルのコーパスを用いる。このデータを用いて、好ましい実施形態は、言葉のマッピングの辞書を構築することが可能である。これは、例えば、単に言語Si(ソース言語)が、連係されたテキストの対(例えばアンカー、文、など)におけるトークンTj(ターゲット言語)と同時に生じる回数を数えることによってなされ得る。しかしながら、任意の適切な技術が用いられ得ることは理解されたい。十分に広く正確に連係されたセットが存在しない場合において、この方法は、相対的に曖昧な多対多のマッピングを生成し得る。したがって、例えば、S1は、一部の確率を用いて、T2、T3、T7およびT8にマッピングされ得ることが決定され得る。しかしながら、これは、以下で詳細に記載するように、許容可能であり、一部の実施形態において、追加的な改良が、それぞれのマッピングの個々の可能性(例えば、以前のユーザのクエリ、結果ページ上のアイテムのユーザ選択および/またはそのようなものを調べることによって)を増加させるためになされ得る。
【0061】
図9は、確率辞書を構築するための、パラレルアンカーテキストの使用を示す。アンカーテキストは、ウェブページ間(または、所定のウェブページ内の位置)のハイパーリンクに関連付けられたテキストを含む。例えば、ハイパーテキストマークアップ言語(HTML)において、「<A href=”http://www.abc.com”>Banks and Savings and Loans</A>」というコマンドは、「Banks and Savings and Loans」というテキストを、http://www.abc.comのウェブページを提示するハイパーリンクとして表示させる。「Banks and Savings and Loans」というテキストは、アンカーテキストと呼ばれ、通常は、提示されるウェブページ(例えば、www.abc.com)の短い記載を提供する。実際は、アンカーテキストは、しばしば、そのページ自体よりも、より正確なウェブページの記載を提供し、提示するウェブページの性質を決定するのに、特に有用であり得る。付け加えて、アンカーテキストにおける言葉の使用および配布は、しばしば、趣旨および長さにおいて、ユーザのクエリにて見出されるものに近い。また、所定のページを提示するアンカーの多くは、同じか、または高度に類似したテキストである場合がある。例えば、www.google.comを提示するアンカーは、単に、「Google」であるか、または、他のテキストとともに、この言葉を少なくとも使用する。したがって、例えばカタカナなど、www.google.comを提示する全てのアンカーを検証することで、「Google」のカタカナ変換は、最も高い頻度で現れる言葉を単に探すことによって、相対的に高い信頼度でもって推測され得る(可能であれば、単なる「ここをクリック」といったような、所定の低い情報内容を除去した後で)。本発明の好ましい実施形態は、正確な変換を提供するために、アンカーテキストのこれらの特性の利点を持つ。
【0062】
図9を参照すると、第1の文字セット(例えばASCII)に書かれた言葉を含むクエリを受け取ると(ブロック902)、サーバは、言葉にあるアンカーテキストのセットを検証し得る(ブロック904)。例えば、サーバは、その言葉を含むそれらのアンカーを識別するために、全ての既知のアンカーのインデックスを検証し得る。次に、それらのアンカーが提示するウェブページは識別され(ブロック906)、アンカーは、それらのページを提示するターゲット言語またはターゲット文字セット(例えば、ひらがな、カタカナ、および/または漢字)で書かれる(ブロック908)。システムはここで、2つの文書のセットを有する(そこでは、アンカーテキストは、文書のフォームと見なされる)。一つの文書のセット(例えば、もともとのASCIIのクエリを含むアンカー)におけるクエリの言葉の分配は、次いで、他の文書セット(例えば、パラレルアンカー)における変換されたフレーズの最も適当な候補を識別するために使用される。統計は、アンカーテキストが現れる頻度に関して計算され得、これらの統計は、アンカーテキストに見出される言葉の相対的な頻度または確率が、もともとのクエリの正しい変換であるかどうかを決定するために使用され得る(ブロック910)。多数の言葉を有するクエリに対して、上記のプロセスは、それぞれの言葉に対して繰り返され得、または、全体のクエリは、単一の言葉として扱われ得、あるいは、一部の他の適切な言葉の群が使用され得る。例えば、クエリが「big houses」である場合、可能な変換の辞書は、そのフレーズを含む、連係されたアンカーテキストを見出すことによって構築され得る。同様に、クエリが3つ以上の言葉を含む場合、適切なマッピングを決定するための経験は、クエリの言葉の適切なサブセットを取り上げ、それらの言葉の結果を生成することによって構築され得る。
【0063】
図9に示される方法において変換を実行する利点は、変換システムが一つの言語または文字セットにおける言葉とターゲットセットにおけるそれらとの間のマッピングの予備的知識を必要としない。その代わり、マッピングは、統計的分析を実行するために利用可能であるデータの本体に基づいて、ダイナミックに決定され得る。したがって、例えば、従来のスタティックな辞書を維持する労力または費用(例えば、言語的分析および調査)を負うことなしに、スラング、イディオム、適切な名前などに対する正確な変換を発見することが可能である。
【0064】
前述の変換の例示的な実施形態は、ここで、図10〜図12と関連して記載される。この例において、ユーザは「house」というクエリの言葉を入力し、スペイン語で書かれた検索結果(または、単に、クエリの言葉の変換)を得ることを望んでいると想定する。サーバは、英語の「house」を、スペイン語の相当物に変換することを企てる。
【0065】
図10を参照すると、様々なウェブページ959、961、963、965が、アンカーテキスト960、962、964、966を介して、ページ972および974にリンクされる。一部のページおよびそれらに関連するアンカーテキストは、英語で書かれており(つまり、ページ959a〜959eおよび963a〜963t)、一部はスペイン語で書かれている(ページ961a〜961eおよび965a〜965j)。サーバは、第1に、「house」という言葉を使用する全てのアンカーの位置を突き止める。これらのアンカーは、例えば、サーバにおいて格納されたアンカーテキストのインデックスを検索することによって、位置が突き止められ得る。そのようなインデックスを使用して、サーバは第1に5つのアンカー960を見出し得、それぞれが「big house」というフレーズを使用し、ウェブページ972を提示する。サーバはまた、次に、ページ972を提示する5つのターゲット言語(例えばスペイン語)のアンカー962が存在することを決定する。図10に示される例において、これらのアンカーは「casa grande」というテキストを含む。同じページ(アンカー960およびアンカー962など)、またはそれに対して所定の関係を有するページに提示されるアンカーは、「連係(aligned)」されているといい、そこでは、より一般的な意味では、配置が通常、連係されたアイテムの相当物(またはほぼ相当物)を意味する。
【0066】
図11Aは、それぞれのターゲット言語の言葉は、ターゲット言語のアンカー962に現れる頻度を示す。図11Aに示されるように、「casa」および「grande」はそれぞれ、5回現れる(つまり、それぞれのアンカー962に一度)。したがって、ターゲットアンカー962に現れる、トータルで10の言葉(つまり、5つのアンカーのそれぞれにおいて、アンカー毎に2つの言葉)から、「casa」は半分を占め、「grande」はもう半分を占める。したがって、図11Aで示されるように、この時点で、「house」という言葉は、「casa」および「grande」の両方の言葉が等しい頻度で現れるゆえに、等しい確率で、「casa」または「grande」のいずれかにマッピングされ得る。
【0067】
しかしながら、図10にて示されるように、システムはまた、「house」という言葉を含む20個の英語のアンカー964を見出し、ページ974に提示し、ならびに、「casa」という言葉を含む10個のスペイン語のアンカー966を見出し、ページ974を提示する。図11Bにて示されるように、「house」という言葉は、「casa」という言葉に、0.75の確率(つまり、15/20)でマッピングされ、「grande」という言葉に、0.25の確率(つまり5/20)でマッピングされる。これらの確率は、そのターゲット言語のアンカーにおけるそれぞれの言葉の出現回数のトータル(「casa」の場合は15)を、ターゲット言語のアンカーにおける言葉のトータル数(重複を含む)によって、単に割ることによって計算される(つまり、20の言葉とは、アンカー962に含まれる10、および964に含まれる10)。代替的には、または追加的には、他の技術が、所定の変換またはマッピングの確率を計算および/または改良するために使用され得る。例えば、当業者が理解するように、任意の様々な既知の技術は、ベイズ法(Bayesian methods)、ヒストグラムスムージング(histogram smoothing)、カーネルスムージング(kernel smoothing)、縮小推定量(shrinkage estimators)、および/または他の推定方法などの確率推定の分散エラーを減少させるために使用され得る。
【0068】
さらなるアンカーテキストが利用可能である場合、確率は、一層さらに改良され得る。例えば、最終確率分配は、図12にて示されたものと同様であり得、「house」は、相対的に高確率で、「casa」、および、それに接尾語が付いた形式「casita」にマッピングされ、幾分か低い確率で、「casino」および
【0069】
【数1】
【0070】
(スペイン語でmansionに相当する)にマッピングされ、僅かな確率で、「grande」にマッピングされる。したがって、正確な変換、およびほぼ同意語の識別は、変換される言語および/または文字セットの知識なしで得られ得る。
【0071】
クエリの言葉を変換すると、サーバは、変換を使用して検索を実行し得る。例えば、ユーザは「hotels in Kyoto」に対するローマ字のクエリを入力する場合、上記された技術は、サーバに、カタカナ、ひらがな、および漢字のクエリのフォームを推測させることができ、それらのクエリを使用して検索を実行させることができ、ならびに、適切なユーザインターフェース内で、ユーザへのそれらのクエリのフォームのそれぞれに対する、組み合わされた結果を提示させることができる。
【0072】
図10〜図12に関連して記載された例は、例示のために提供されるのであり、限定のためではなく、多くの変更がそこに表された方法論に対してなされ得ることは理解されるべきである。例えば、異なる統計的な技術が一定の確率に達するために使用され得、および/または、修正は、上記された基本的な技術に対してなされ得る。同様に、上記された変換技術は、単に、ユーザによって入力された言葉またはフレーズの変換を実行するために使用され得、関連するインターネット検索を実行し、または確率辞書を作成するために使用される必要はない。付け加えて、先行する例は、ユーザのクエリの受け取りのアプリケーションとに生じるものとして、変換プロセスを記載するが、他の実施形態においては、マッピングプロセスは、ユーザのクエリが受け取られる前に実行され得ることは理解されるべきである。そのような計算前のマッピングは、図8に記載されたような辞書に格納され得、次いで、それらが受け取られたときに、ユーザのクエリを変換するように適合される。最後に、連係されたアンカーテキストとは異なるテキストは、変換を実行するために使用され得ることは理解されるべきである。例えば、連係された文章または他のデータは、同様な方法にて使用され得る。多くの国では、一つ以上の公式言語または認められた言語が存在しており、新聞や定期刊行物はしばしばこれらの言語のそれぞれにて書かれた同じ記事を含む。これらのパラレルな変換は、言葉の変換の確率辞書を準備するために、前記されたアンカーテキストと同様の方法において使用され得る。
【0073】
したがって、好ましい実施形態により、有利にも、ユーザは、従来の方法において、検索クエリおよび/または変換要求を入力することができ、正確で自動の変換および検索を提供する。一部の実施形態において、追加の改良が上記された基本的なモデルに対してなされ得る。例えば、一部の実施形態において、優先(加重)は、もともとのクエリおよび/または他の連係されたアンカーにおける言葉の数と同様の言葉の数を含むアンカーに与えられ得る。例えば、図10に示されるシステムにおいて、優先は、ページ974に提示されるアンカーに与えられ得る。というのは、もともとのクエリと同様に、それらは、それぞれ単一の言葉を含むからである。同様に、「la casa grande」のテキストを含むアンカーがまたページ972に提示された場合、その加重は、適切な要因によって軽減され得、というのは、それが連係された他のアンカーよりも多くの言葉(例えば3つ)を含むからである。そのような加重スキームは、適切な要因によってこれらのアンカーの言葉と関連される頻度を増加させることによって、図11Bに示される確率計算に反映され得る。
【0074】
上記された変換プロセスはまた、検索それ自体の効率を改善するために利用され得る。例えば、確率辞書は、様々な変換およびもともとのクエリの言葉の同意語などを含む、進行中のクエリを拡張するために使用され得る。文書検索に先立つユーザのクエリを拡張することによって、同じ「概念」の同時検索が実行され得、それにより、検索結果は、ユーザが探しているものを含む可能性を増加させる。代替的には、または追加的には、確率辞書は、文書の言葉の拡張を提供することによって、通常の文書インデックス付けのプロセスを補うために使用され得る。例えば、文書にて見出される言葉は、確率辞書からの変換を用いて、文書のインデックスにおいて補われ得、その文書は、もともとの文書にて見出された同じ言葉を正確に使用しない検索によってさえも、位置を突き止められる可能性を増加させる。
【0075】
上記された変換技術を使用する場合に生じ得る問題は、データの希薄(例えば、「casa」を「house」にマップすることを最終的に決定するには十分なアンカーがない)、または、多様性の欠如(全てのアンカーが同じものを示す)などのためであり、システムは、十分に正確な確率のマッピングに達することが不可能であり得る。したがって、一部の実施形態において、確率マッピングは、ユーザの行動を検証することでさらに改良され得る。いくつかの例示的な技術が以下に記載される。
【0076】
例えば、再度、サーバが「house」に対する変換を得ることを望んでいる場合を想定する。しかしながら、見出され得るアンカーテキストが、「big house」というフレーズ、または「casa grande」というフレーズのいずれかを含むことを想定する。そのアンカーテキストにおける多様性の欠如のために、確率辞書は以下のマッピングに達し得る。
house→casa、0.5の確率
house→grande、0.5の確率
big→casa、0.5の確率
big→grande、0.5の確率
grande→house、0.5の確率
grande→big、0.5の確率
casa→house、0.5の確率
casa→big、0.5の確率
ここでユーザが「casa」という言葉を用いて検索エンジンにクエリすると想定する。この時点で、検索エンジンは、「casa」という言葉を含むページを返答し得、また、「house」という言葉をちょうど含むN結果と、「big」という言葉をちょうど含むM結果とを合わせる。実際には、NおよびMは、マッピングに内在する確率を考慮するように調整され得、その結果、相対的に見込みのないマッピングは、より少ない結果が表示されることになる。ユーザが、「big」という言葉を含む結果をクリックするよりも、「house」という言葉を含む結果を10倍、クリックした場合、マッピングの確率は、例えば、以下のように調整される。
house→casa、0.9の確率
house→grande、0.1の確率
big→casa、0.1の確率
big→grande、0.9の確率
grande→house、0.1の確率
grande→big、0.9の確率
casa→house、0.9の確率
casa→big、0.1の確率
実際の数は、クリックが考慮されるユーザの数、その言葉の両方を含むページのクリックの回数、結果のセットの中の、当該の言葉を含む結果の置換、および/またはそれらのようなものなど、他の様々な要因に依存し得ることに注意されたい。この例(つまり、0.1および0.9)に与えられた調整された確率は、例示の目的のためであることは理解されたい。当業者は、上記されたものなどのユーザフィードバックに与えられた実際の加重は、任意の適切な方法にてインプリメントされ得ることは理解する。
【0077】
また、前述の例は、ユーザフィードバックの使用の例を容易にするように簡易化されていることに注意されたい。例えば、一部のシステムにおいて、所定の変換を実行することを補助するために、他の変換から得られた情報を利用することが可能である。例えば、今提示された例において、「house」という言葉が「big house」という言葉を含んだアンカーテキストに現れる場合、「house」は、「grande」にマッピングされるよりも、より適切に「casa」にマッピングされることを決定することは可能であり得る。例えば、既に、「big」が非常に高確率で、および、十分に大きなデータのセットにわたって、「grande」にマッピングされるように決定されている場合(および、アンカーテキストが同意語のリストで構成されてない場合)、次いで、house−to−casaのマッピングは、たとえ、「house」または「casa」を含むアンカーが要領を得ない場合であっても、house−to−grandeのマッピングを介して、優先を与えられ得る。
【0078】
変換の正確さおよび/または検索結果の有用性はまた、ユーザのクエリセッションの履歴を検証することによって改善され得る。例えば、多くの場合、システムは、ユーザが入力した以前のクエリを知っている(例えば、クッキーまたはサーバ上のユーザアカウントに格納された情報などを介して)。この履歴データは、そのユーザからのクエリの、可能な意味をランクするために使用され得、飛行に関連するものから、フィッシングに関するクエリに対して「bank」を明確にする。したがって、このプロセスは、可能な変換のセットを狭めるために使用され得る。一部の実施形態において、ユーザインターフェースにて、「Xの検索を意図しますか?」(ここで、Xは所定の変換の優先を意味する)などのメッセージに関連して、それらを表示することによって、これらを示唆し得、その一方で、結果の第1のページにおいて、可能な再公式化のそれぞれからの結果の一部を表示する。ユーザが「…意図しますか?」によって示唆された代替のうちの一つを選択するか、結果ページに提示された結果のうちの一つを選択する場合、システムは、クエリの言葉の適当な変換、およびユーザの適当な検索バイアスに関する追加的な証拠を得る。これらの信号の両方は、次いで、システムによって利用され得、一般的な場合、およびユーザに特殊な場合の両方において、言葉のマッピングの適当な根拠を更新する(例えば、確率辞書において)。
【0079】
D.結論
上記されたように、本発明と合致する方法およびシステムは、曖昧な検索結果に応じて検索結果を提供し、言葉を他の文字セットおよび/または言語に変換するために使用され得る。様々な変換および検索技術、ならびにシステムが記載されている。しかしながら、前述の記載は、例示のために提示されるものであり、多くの修正および変更が、上記の教示に照らし合わせて、または、本発明の実施を通して、可能であることは理解されたい。例えば、前述の記載はクライアント−サーバ構成に基づいているが、当業者は、ピアツーピア構成もまた、本発明に合致して使用され得ることは理解されたい。さらに、記載された実施はソフトウェアを含むが、本発明は、ハードウェアとソフトウェアとの組み合わせ、またはハードウェアのみとして実施され得る。付け加えて、本発明の局面は、メモリに格納されるように記載されたが、当業者は、これらの局面もまた、ハードディスク、フロッピーディスク(登録商標)、またはCD−ROMなどのような二次的格納装置、インターネットからの搬送波、あるいは、RAMまたはROMの他の形式などの、他のタイプのコンピュータ可読媒体に格納され得る。本発明の範囲は、それゆえ、請求項およびそれらの均等物によって定義される。
【特許請求の範囲】
【請求項1】
確率辞書を作成する方法であって、前記確率辞書は第1のフォーマットにおける言葉を第2のフォーマットにおける言葉にマッピングし、前記方法は、
所定の言葉に対して、前記言葉を含む、前記第1のフォーマットにおける第1のデータのセットを識別することと、
前記第1のデータのセットと連係する、前記第2のフォーマットにおける第2のデータのセットを識別することと、
前記所定の言葉が前記第2のデータのセットにおける一つ以上の言葉にマッピングする一つ以上の確率を決定するために、前記第2のデータのセットを分析することと
を包含する、方法。
【請求項2】
前記所定の言葉が前記第2のデータのセットにおける一つ以上の言葉にマッピングする一つ以上の確率とともに、前記所定の言葉を前記辞書に加えることをさらに包含する、請求項1に記載の方法。
【請求項3】
前記辞書に加えられるそれぞれの言葉に対して、前記第1のデータのセットを識別するステップと、前記第2のデータのセットを識別するステップと、前記第2のデータのセットを分析するステップを繰り返すことをさらに包含する、請求項2に記載の方法。
【請求項4】
前記第1のデータのセットは、一つ以上のウェブページのセットを指す第1のアンカーテキストのセットを含み、前記第2のデータのセットは、一つ以上のウェブページの同じセットを指す第2のアンカーテキストのセットを含む、請求項1に記載の方法。
【請求項5】
前記第1のデータのセットは第1の言語で書かれたテキストのセットを含み、前記第2のデータのセットは第2の言語で書かれた同じテキストのセットを含む、請求項1に記載の方法。
【請求項6】
前記所定の言葉が前記第2のデータのセットにおける言葉にマッピングする確率は、前記第2のデータのセットでの前記言葉の発生回数を前記第2のデータのセットにおける言葉の総数で割ることによって計算される、請求項1に記載の方法。
【請求項7】
前記所定の言葉が少なくとも部分的にユーザーの検索結果選択の分析に基づいて前記第2のデータのセットにおける言葉にマッピングする確率を修正することをさらに包含する、請求項1に記載の方法。
【請求項8】
前記所定の言葉が少なくとも部分的にユーザーの以前のクエリの分析に基づいて前記第2のデータのセットにおける言葉にマッピングする確率を修正することをさらに包含する、請求項1に記載の方法。
【請求項9】
第1のフォーマットで書かれた第1のテキスト本体を識別することと、
第2のフォーマットで書かれた第2のテキスト本体を識別することであって、前記第2のテキスト本体は前記第1のテキスト本体と連係する、ことと、
前記第1のテキスト本体における言葉の発生と前記第2のテキスト本体における言葉の発生を比べて、前記第1のテキスト本体における言葉と前記第2のテキスト本体における言葉の間の変換辞書を作ることと
を包含する、変換方法。
【請求項10】
前記変換辞書は前記変換に関する一つ以上の確率を含む、請求項9に記載の変換方法。
【請求項11】
前記第1のフォーマットは第1の文字セットを含み、前記第2のフォーマットは第2の文字セットを含む、請求項9に記載の変換方法。
【請求項12】
前記第1のフォーマットは第1の言語を含み、前記第2のフォーマットは第2の言語を含む、請求項9に記載の変換方法。
【請求項13】
前記第1のテキスト本体はアンカーテキストを含み、前記第2のテキスト本体はアンカーテキストを含む、請求項9に記載の変換方法。
【請求項1】
確率辞書を作成する方法であって、前記確率辞書は第1のフォーマットにおける言葉を第2のフォーマットにおける言葉にマッピングし、前記方法は、
所定の言葉に対して、前記言葉を含む、前記第1のフォーマットにおける第1のデータのセットを識別することと、
前記第1のデータのセットと連係する、前記第2のフォーマットにおける第2のデータのセットを識別することと、
前記所定の言葉が前記第2のデータのセットにおける一つ以上の言葉にマッピングする一つ以上の確率を決定するために、前記第2のデータのセットを分析することと
を包含する、方法。
【請求項2】
前記所定の言葉が前記第2のデータのセットにおける一つ以上の言葉にマッピングする一つ以上の確率とともに、前記所定の言葉を前記辞書に加えることをさらに包含する、請求項1に記載の方法。
【請求項3】
前記辞書に加えられるそれぞれの言葉に対して、前記第1のデータのセットを識別するステップと、前記第2のデータのセットを識別するステップと、前記第2のデータのセットを分析するステップを繰り返すことをさらに包含する、請求項2に記載の方法。
【請求項4】
前記第1のデータのセットは、一つ以上のウェブページのセットを指す第1のアンカーテキストのセットを含み、前記第2のデータのセットは、一つ以上のウェブページの同じセットを指す第2のアンカーテキストのセットを含む、請求項1に記載の方法。
【請求項5】
前記第1のデータのセットは第1の言語で書かれたテキストのセットを含み、前記第2のデータのセットは第2の言語で書かれた同じテキストのセットを含む、請求項1に記載の方法。
【請求項6】
前記所定の言葉が前記第2のデータのセットにおける言葉にマッピングする確率は、前記第2のデータのセットでの前記言葉の発生回数を前記第2のデータのセットにおける言葉の総数で割ることによって計算される、請求項1に記載の方法。
【請求項7】
前記所定の言葉が少なくとも部分的にユーザーの検索結果選択の分析に基づいて前記第2のデータのセットにおける言葉にマッピングする確率を修正することをさらに包含する、請求項1に記載の方法。
【請求項8】
前記所定の言葉が少なくとも部分的にユーザーの以前のクエリの分析に基づいて前記第2のデータのセットにおける言葉にマッピングする確率を修正することをさらに包含する、請求項1に記載の方法。
【請求項9】
第1のフォーマットで書かれた第1のテキスト本体を識別することと、
第2のフォーマットで書かれた第2のテキスト本体を識別することであって、前記第2のテキスト本体は前記第1のテキスト本体と連係する、ことと、
前記第1のテキスト本体における言葉の発生と前記第2のテキスト本体における言葉の発生を比べて、前記第1のテキスト本体における言葉と前記第2のテキスト本体における言葉の間の変換辞書を作ることと
を包含する、変換方法。
【請求項10】
前記変換辞書は前記変換に関する一つ以上の確率を含む、請求項9に記載の変換方法。
【請求項11】
前記第1のフォーマットは第1の文字セットを含み、前記第2のフォーマットは第2の文字セットを含む、請求項9に記載の変換方法。
【請求項12】
前記第1のフォーマットは第1の言語を含み、前記第2のフォーマットは第2の言語を含む、請求項9に記載の変換方法。
【請求項13】
前記第1のテキスト本体はアンカーテキストを含み、前記第2のテキスト本体はアンカーテキストを含む、請求項9に記載の変換方法。
【図1】
【図2】
【図3】
【図4a】
【図4b】
【図5a】
【図5b】
【図5c】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図2】
【図3】
【図4a】
【図4b】
【図5a】
【図5b】
【図5c】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【公開番号】特開2013−84306(P2013−84306A)
【公開日】平成25年5月9日(2013.5.9)
【国際特許分類】
【外国語出願】
【出願番号】特願2013−15114(P2013−15114)
【出願日】平成25年1月30日(2013.1.30)
【分割の表示】特願2011−24457(P2011−24457)の分割
【原出願日】平成16年9月13日(2004.9.13)
【出願人】(502208397)グーグル インコーポレイテッド (161)
【公開日】平成25年5月9日(2013.5.9)
【国際特許分類】
【出願番号】特願2013−15114(P2013−15114)
【出願日】平成25年1月30日(2013.1.30)
【分割の表示】特願2011−24457(P2011−24457)の分割
【原出願日】平成16年9月13日(2004.9.13)
【出願人】(502208397)グーグル インコーポレイテッド (161)
[ Back to top ]