(57)【特許請求の範囲】
【請求項１】
コンピュータにより実装される関連度システムであって、
１つまたは複数のプロセッサと、
前記１つまたは複数のプロセッサに結合されたメモリであって、複数の命令を記憶し、当該複数の命令は前記１つまたは複数のプロセッサにより実行されたときに、当該１つまたは複数のプロセッサに、
クエリ文字列に基づいた検索結果として受信した文書から文書情報を抽出する処理であって、前記文書情報は、複合語を有するユニフォームリソースロケータ（ＵＲＬ）含む、抽出する処理と、
前記複合語を複数の別個の用語に分割する処理と、
当該複数の別個の用語の少なくとも１つを用語の辞書中で見つける処理と、
抽出された前記文書情報に基づきターゲットデータの文字列を生成する処理であって、当該ターゲットデータ文字列は前記辞書中で見つけられた、前記複数の別個の用語の１つを含む、生成する処理と、
前記ターゲットデータ文字列と前記クエリ文字列の間の編集距離を計算する処理であって、順位付けの結果の一部として文書の関連度を決定する際に、前記編集距離が使用される、計算する処理と
を実行させることを特徴とするシステム。
【請求項２】
前記文書情報は、タイトル情報、ＵＲＬ情報、クリック情報、またはアンカーテキストのうちの少なくとも１つを含むことを特徴とする請求項１に記載のシステム。
【請求項３】
ＵＲＬに対する前記編集距離を計算するために、インデックス時間において前記文書情報の複合語が分割されることを特徴とする請求項１に記載のシステム。
【請求項４】
前記複数の命令は前記１つまたは複数のプロセッサに、さらに、インデックス時間において前記文書情報のアンカーテキストをフィルタリングしてアンカーテキストの上位順位付けセットを計算する処理を実行させることを特徴と
する請求項１に記載のシステム。
【請求項５】
前記文書情報は、タイトル文字、アンカー文字、クリック文字、またはＵＲＬ文字のうちの少なくとも１つを含み、前記文書情報と、ＢＭ２５Ｆ関数、クリック距離、ファイルタイプ、言語およびＵＲＬ深さの生の入力特徴とに基づいて前記文書の関連度を計算するニューラルネットワークをさらに有することを特徴とする請求項１に記載のシステム。
【請求項６】
前記編集距離は、前記データ文字列と前記クエリ文字列の間の近接性を高めるために、用語の挿入および削除に基づいて計算されることを特徴とする請求項１に記載のシステム。
【請求項７】
前記編集距離は、前記データ文字列と前記クエリ文字列の間の近接性を高めるために、用語の挿入および削除に関連付けられているコストに基づいて計算されることを特徴とする請求項１に記載のシステム。
【請求項８】
文書の関連度を決定するコンピュータ実施の方法であって、
検索プロセスの一部としてクエリ文字列をプロセッサにより受信するステップと、
ユニフォームリソースロケータ（ＵＲＬ）を、前記検索プロセス中に返された文書から前記プロセッサにより抽出するステップと、
前記ＵＲＬの複合語を別個の複数の用語に分割することにより前記ＵＲＬからターゲットデータ文字列を前記プロセッサにより生成するステップと、
前記ターゲットデータ文字列と前記クエリ文字列の間の編集距離を前記プロセッサにより計算するステップと、
前記編集距離に基づいて関連度スコアを前記プロセッサにより計算するステップと
を備えることを特徴とする方法。
【請求項９】
前記編集距離を計算するステップの一部として用語挿入を前記プロセッサにより使用するステップと、前記ターゲットデータ文字列を生成するために前記クエリ文字列に用語を挿入する挿入コストを前記プロセッサにより計算するステップであって、前記コストは重み付けパラメータとして表される、計算するステップをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１０】
前記編集距離を計算するステップの一部として用語削除を前記プロセッサにより使用するステップと、前記データ文字列を生成するために前記クエリ文字列の用語を削除する削除コストを前記プロセッサにより計算するステップであって、前記コストは重み付けパラメータとして表される、計算するステップをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１１】
前記編集距離を計算するステップの一部として位置コストを前記プロセッサにより計算するステップであって、前記位置コストは前記ターゲットデータ文字列内の１つまたは複数の用語位置の用語挿入および用語削除に関連付けられている、ステップをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１２】
前記編集距離を計算する全体コストを計算するため、前記ターゲットデータ文字列の文字と前記クエリ文字列の文字の間で照合プロセスを前記プロセッサにより実行するステップをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１３】
インデックス時間において前記データ文字列のＵＲＬの複合語を前記プロセッサにより分割することを特徴とする請求項８に記載の方法。
【請求項１４】
前記文書内の出現度数に基づいてアンカーテキストの上位順位付けセットを見出すために前記データ文字列のアンカーテキストを前記プロセッサによりフィルタリングするステップをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１５】
前記セット内のアンカーテキストの編集距離を前記プロセッサにより計算するステップをさらに備えることを
特徴とする請求項１４に記載の方法。
【請求項１６】
前記編集距離を計算するステップから導かれたスコアを、変換関数の適用後に２層ニューラルネットワークに前記プロセッサにより入力するステップであって、タイトル情報、アンカー情報、クリック情報、またはＵＲＬ情報のうちの少なくとも１つおよびその他の生の入力特徴に関連付けられている前記編集距離の計算に基づいて前記スコアが生成される、入力するステップをさらに備えることを特徴とする請求項８に記載の方法。
【請求項１７】
文書の関連度を計算するコンピュータ実施の方法であって、
クエリ文字列を検索プロセスの一部として前記プロセッサにより処理して文書の結果セットを返すステップと、
前記結果セットの文書から抽出された文書情報に基づいてターゲットデータ文字列を生成するステップであって、前記文書情報は複合語を有するＵＲＬ情報を含み、前記複合語を複数の別個の用語に分割しおよび用語の辞書中の前記複数の別個の用語の少なくとも１つを見つけるステップを有する、生成するステップと、
前記ターゲットデータ文字列と前記クエリ文字列の間の編集距離を、用語挿入、用語削除および用語位置に基づいて、前記プロセッサにより、計算するステップと、
前記編集距離に基づいて関連度スコアを前記プロセッサにより、計算するステップであって、前記関連度スコアは前記結果セットの前記文書を順位付けするために使用される、計算するステップと
を備えることを特徴とする方法。
【請求項１８】
用語挿入、用語削除、用語位置のそれぞれに関連付けられているコストを前記プロセッサにより、計算するステップと、前記コストを前記関連度スコアの計算に前記プロセッサにより、組み込むステップとをさらに備えることを特徴とする請求項１７に記載の方法。
【請求項１９】
インデックス時間において前記ＵＲＬの複合語を前記プロセッサにより、分割するステップと、インデックス時間において前記アンカーテキスト情報を前記プロセッサにより、フィルタリングして前記文書内のアンカーテキストの出現度数に基づいて前記アンカーテキストの上位順位付けセットを前記プロセッサにより、見出すステップとをさらに備えることを特徴とする請求項１７に記載の方法。
【請求項２０】
ソースＵＲＬ文字列内の出現の順序でクエリ用語の文字列を構築するために前記クエリ文字列の用語の出現を前記プロセッサにより、読み取るステップと、前記用語の間のスペースを単語マークで前記プロセッサにより、充填するステップとをさらに備えることを特徴とする請求項１７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、編集距離および文書情報を使用する検索結果順位付けに関する。
【背景技術】
【０００２】
標準的な検索エンジンサービスにおいて、ユーザは、クエリと一致するＵＲＬ（ｕｎｉｖｅｒｓａｌ  ｒｅｓｏｕｒｃｅ  ｌｏｃａｔｏｒ）のインデックス付きコレクションから最上位の関連文書を選択することにより、クエリを入力することができる。クエリに迅速に応じるために、検索エンジンは、キーワードを文書にマップする１つまたは複数の方法（たとえば、逆インデックスデータ構造体）を使用する。たとえば、エンジンにより実行される第１のステップは、ユーザのクエリによって指定されたキーワードを含む候補文書のセットを識別することであってもよい。これらのキーワードは、文書本文もしくはメタデータ、または（アンカーテキストのような）他の文書もしくはデータストアに実際に格納されるこの文書に関する追加のメタデータにあってもよい。
【０００３】
大規模なインデックスコレクションにおいて、候補文書セットの基数は、クエリ用語の共通性に応じて大きく（たとえば、場合によっては数百万に）なる可能性もある。検索エンジンは、候補文書のセット全体を返すのではなく、関連度に関して候補文書を順位付けする第２のステップを実行する。通常、検索エンジンは、特定のクエリに対する文書の関連度の度合いを予測するために、順位付け関数を使用する。順位付け関数は、文書から複数の特徴を入力として取り出し、検索エンジンが予測された関連度により文書をソートできるようにする数値を計算する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
関数がいかに正確に文書の関連度を予測するかに関する順序付け関数の品質は、最終的に、検索結果に対するユーザの満足度、またはユーザが提示した質問に回答を得られる平均回数によって決まる。システムに対する全般的なユーザ満足度は、単一の数値（またはメトリック）によって概算されてもよいが、それは順位付け関数を変更することで数値を最適化できるからである。通常、メトリックは、クエリログの無作為抽出により事前に選択されるクエリの代表的なセットにわたり計算され、評価クエリのそれぞれに対してエンジンによって返される結果ごとに関連度ラベルを割り当てるステップを伴う。しかし、文書の順序付けおよび関連度のためのこれらのプロセスは、望ましい結果をもたらすには依然として非効率的である。
【課題を解決するための手段】
【０００５】
本明細書において説明される一部の新規な実施形態の基礎的な理解をもたらすために、簡略化した要約（課題を解決するための手段）を以下に提示する。この要約（課題を解決するための手段）は、広範に及ぶ概要ではなく、主要／重要な要素を特定すること、またはその範囲を詳細に記述することを意図するものではない。その唯一の目的は、後段において提示されるさらに詳細な説明の前置きとして簡略化された形態で一部の概念を提示することである。
【０００６】
アーキテクチャは、クエリ文字列に基づいて検索結果として受信した文書から文書情報を抽出して、データ文字列とクエリ文字列の間の編集距離を計算するための機構を提供する。データ文字列は、たとえば、ＴＡＵＣ（タイトル、アンカーテキスト、ＵＲＬ（ｕｎｉｆｏｒｍ  ｒｅｓｏｕｒｃｅ  ｌｏｃａｔｏｒ）、およびクリック）のような、文書情報から得られた文書の簡略で正確な記述であってもよい。編集距離は、結果の順序付けの一部として文書の関連度を決定する際に採用される。機構は、クエリ全体またはクエリの一部のニアマッチを検出するために近接性に関連する特徴のセットを採用し、検索結果の順位付けの関連度を向上させる。
【０００７】
編集距離は、クエリ文字列が、文書情報を含む所与のデータストリームまでどのくらい近いかを評価するために処理される。アーキテクチャは、クエリ用語をさらに効果的に発見できるように、ＵＲＬに複合語のインデックス−時間分割を含む。加えて、１つまたは複数の文書結果の最上位Ｎ個のアンカーを見出すために、アンカーテキストのインデックス−時間フィルタリングが使用される。ＴＡＵＣを使用して、情報はニューラルネットワーク（たとえば、２層）に入力され、検索結果を順位付けするための関連度メトリックを向上させることができる。
【０００８】
前述の目的および関連する目的を達成するため、本明細書において特定の例示の態様が、以下の説明および付属の図面と共に説明される。しかし、それらの態様は、本明細書において開示される原理が採用されうるさまざまな方法のほんの一部を示すに過ぎず、すべてのそのような態様および等価物を含むことが意図される。その他の利点および新規の特徴は、図面と併せて検討すれば以下の詳細な説明から明らかとなろう。
【図面の簡単な説明】
【０００９】
【図１】コンピュータにより実施される関連度システムを示す図である。
【図２】編集距離を計算するための例示の照合アルゴリズムを示す流れ図である。
【図３】修正された編集距離および照合アルゴリズムを使用し、クエリ文字列およびデータ文字列に基づいて編集距離値を処理して生成するステップを示す図である。
【図４】修正された編集距離および照合アルゴリズムを使用し、クエリ文字列およびデータ文字列に基づいて編集距離値を処理して生成するステップのもう１つの例を示す図である。
【図５】ニューラルネットワークを採用して文書の関連度スコアの生成を補助するコンピュータ実施の関連度システムを示す図である。
【図６】クエリ文字列とデータ文字列の間の編集距離を決定するために文書情報に採用されうるデータの型を示す図である。
【図７】インデックス−時間処理データフローを示す図である。
【図８】結果を順位付けするための図７のインデックスプロセスからニューラルネットワークへの入力を示すブロック図である。
【図９】検索結果の生成を計算するためのニューラルネットワーク、編集距離入力、および生の特徴入力の例示的なシステムの実施態様を示す図である。
【図１０】文書結果セットの文書関連度を決定する方法を示す図である。
【図１１】文書の関連度を計算する方法を示す図である。
【図１２】開示されるアーキテクチャによる、ＴＡＵＣ特徴を使用して検索結果を順位付けするために編集距離処理を実行するよう動作可能なコンピューティングシステムを示すブロック図である。
【発明を実施するための形態】
【００１０】
開示されるアーキテクチャは、クエリ全体のニアマッチ、またはタイトル、アンカー、ＵＲＬ、もしくはクリックのような、文書に関する正確なメタデータとの一致を検出するために近接性に関連する特徴のセットを実施することにより、検索結果順序付けの関連度を向上させる。たとえば、クエリ「ｃｏｍｐａｎｙ  ｓｔｏｒｅ」、第１の文書の文書タイトル「ｃｏｍｐａｎｙ  ｓｔｏｒｅ  ｏｎｌｉｎｅ」および第２の文書の文書タイトル「ｎｅｗ  ＮＥＣ  ＬＣＤ  ｍｏｎｉｔｏｒｓ  ｉｎ  ｃｏｍｐａｎｙ  ｓｔｏｒｅ」を考察する。その他の特性は、第１の文書および第２の文書のいずれも同じであると仮定して、アーキテクチャは、選択されたストリームをクエリと一致させるためにどれほどの編集努力が注がれるかに基づいて、文書のスコアを割り当てる。この例において、文書タイトルは、評価のために選択される。完全一致させるため、第１の文書のタイトルには（「ｏｎｌｉｎｅ」という用語を削除する）１つの削除操作だけが必要であるが、第２の文書のタイトルには（「ｎｅｗ」、「ＮＥＣ」、「ＬＣＤ」、「ｍｏｎｉｔｏｒｓ」、および「ｉｎ」という用語を削除する）５つの削除が必要である。したがって、第１の文書は、より関連度が高いと計算される。
【００１１】
タイトルは、クエリ用語が複合語から見出されるようにデータの一部のストリーム（たとえば、ＵＲＬ）に処理を適用することができるＴＡＵＣ（タイトル、アンカー、ＵＲＬ、およびクリック）文書情報の１つの要素である。たとえば、ここでもまた、クエリ「ｃｏｍｐａｎｙ  ｓｔｏｒｅ」を考察し、ＵＲＬが「ｗｗｗ．ｃｏｍｐａｎｙｓｔｏｒｅ．ｃｏｍ」であるとする。その結果、ＵＲＬが「ｗｗｗ」、「ｃｏｍｐａｎｙ」、「ｓｔｏｒｅ」、および「ｃｏｍ」という４つの部分（または用語）に分割される。
【００１２】
これ以降、図面が参照されるが、全体を通じて類似する要素を参照するために類似する番号が使用される。以下の説明において、その十分な理解をもたらすために、説明を目的として多数の具体的な詳細が示される。しかし、新規の実施形態がそれらの特定の詳細なくして実施されうることは明らかとなろう。その他の例において、よく知られた構造体およびデバイスが、その説明を容易にするためにブロック図の形態で示される。
【００１３】
図１は、コンピュータにより実施される関連度システム１００を示す図である。システム１００は、クエリ文字列１１０に基づいて検索結果１０８として受信した文書１０６から文書情報１０４を抽出するための処理コンポーネント１０２を含む。システム１００はまた、文書情報１０４から導かれたデータ文字列１１６とクエリ文字列１１０の間の編集距離１１４を計算するための近接性コンポーネント１１２を含むこともできる。編集距離１１４は、検索結果１０８の一部として文書１０６の関連度を決定する際に採用される。
【００１４】
データ文字列１１６を生成するために採用される文書情報１０４は、たとえば、タイトル情報（または文字）、リンク情報（たとえば、ＵＲＬ文字）、クリックストリーム情報、および／またはアンカーテキスト（または文字）を含むことができる。処理コンポーネント１０２は、インデックス時間において文書情報１０４の複合語を分割して、編集距離１１４を計算する。処理コンポーネント１０２はまた、インデックス時間において、アンカーテキストのような文書情報をフィルタリングして、アンカーテキストの上位順位付けセットを計算する。
【００１５】
編集距離１１４の計算は、データ文字列１１６とクエリ文字列１１０の間の近接性を高める（近づける）ために、用語の挿入および削除に基づいて行われる。編集距離１１４の計算はまた、データ文字列１１６とクエリ文字列１１０の間の近接性を高める（近づける）ために、用語の挿入および削除に関連付けられているコストに基づいて行われてもよい。
【００１６】
クエリ文字列１１０からの用語の挿入および／または削除に基づいてデータ文字列１１６（たとえば、ＴＡＵＣ）を生成するシナリオを考察する。この用語の処理は、非クエリの単語をクエリ文字列１１０に挿入する、クエリ用語をクエリ文字列１１０に挿入する、クエリ文字列１１０からＴＡＵＣ用語を削除する、および／または、非ＴＡＵＣの用語をクエリ文字列１１０から削除する、という４つの操作に従って実行されてもよい。
【００１７】
編集距離１１４は、挿入操作および削除操作に基づくが、置換には基づいていない。挿入に対して定義されるコストには２つのタイプがあってもよい。データ文字列１１６をクエリ文字列１１０から生成するシナリオを考察する。生成する際、単語はクエリ文字列１１０に挿入することができるが、これが元のクエリ文字列１１０に存在する場合、コストは１として定義され、それ以外の場合、コストはｗ１（≧１）として定義される。ここで、ｗ１は、調整される重み付けパラメータである。たとえば、クエリ文字列１１０がＡＢである場合、ＡＢＣのデータ文字列を生成するコストは、データ文字列ＡＢＡを生成するコストよりも高い。「不適切な単語」をデータ文字列１１６に挿入することでデータ文字列１１６（たとえば、ＴＡＵＣ）全体をさらに不適切にすることは直感的に分かる。
【００１８】
削除のコストには２つのタイプがあってもよい。ここでもまた、データ文字列１１６をクエリ文字列１１０から生成するシナリオを考察する。クエリ文字列１１０の用語を削除する場合、その用語が元のデータ文字列１１６に存在すれば、コストは１として定義され、それ以外の場合、コストはｗ２（≧１）として定義される。
【００１９】
コストのもう１つのタイプは、位置コストである。削除または挿入がデータ文字列１１６の第１の位置において行われた場合、追加のコストがある（＋ｗ３）。２つの文字列（クエリ文字列１１０およびデータ文字列１１６）の最初の部分の一致は、文字列の後半部分の一致よりも重要視されることは直感的に分かる。クエリ文字列１１０が「ｃｎｎ」であり、データ文字列１１６がタイトル＝「ｃｎｎ．ｃｏｍ−ｂｌｕｒ  ｂｌｕｒ」である以下の例を考察する。挿入または削除が第１の位置において行われる場合、それはソリューションの有効性を大幅に低下させる可能性がある。
【００２０】
図２は、編集距離を計算するための例示の修正済み照合アルゴリズム２００を示す流れ図である。説明を簡潔にするために、本明細書において、たとえば流れ図またはフローダイアグラムの形態で示される１つまたは複数の方法論は、一連の動作として示され説明されるが、一部の動作はそれに従って、本明細書において示され説明される他の動作と異なる順序および／または他の動作と同時に生じることもあるので、方法論は、動作の順序に限定されないことを理解および認識されたい。たとえば、当業者は、方法論が代替として、状態図におけるように、一連の相互関係のある状態またはイベントとして表されてもよいことを理解し認識するであろう。さらに、方法論に示される動作のすべてが、新規の実施形態に必須とされるわけではない。
【００２１】
２００において、クエリ文字列およびデータ（またはターゲット）文字列の要素が列挙される。これは、クエリ文字列の長さをｎに設定し（クエリ文字列内の各用語はｓ［ｉ］である）、ターゲット（またはデータ）文字列の長さをｍに設定する（ターゲット文字列内の各用語はｔ［ｊ］と表される）ことで達成される。２０２において、０．．．ｍ行および０．．．ｎ列を含む行列が構築される（ここで、行列内の各用語はｄ［ｊ，ｉ］と表される）。２０４において、第１行は、削除のさまざまなコストに依存する値で初期化され、第１列は、挿入のさまざまなコストに依存する値で初期化される。２０６においてｎ＝０である場合、２０８に示されるようにｄ［ｍ，０］を返して終了し、２０６においてＭ＝０である場合、２０８に示されるようにｄ［０，ｎ］を返して終了する。２１０において、クエリ文字列の各文字は検査される（１からｎまでのｉ）。２１２において、ターゲット文字列の各文字は検査される（１からｍまでのｊ）。２１４において、クエリ文字列内の文字列がデータ文字列内の文字と等しい場合、フローは、コストがゼロであり次の行列セルが処理される２１６に進む。言い換えれば、ｓ［ｉ］がｔ［ｊ］と等しい場合、コストは０であり、ｄ［ｊ，ｉ］＝ｄ［ｊ−１，ｉ−１］である。
【００２２】
クエリ文字列セル内の文字がデータ文字列セル内の文字と等しくない場合、フローは２１４から２１８に進み、そこで現在のセルは真上のセルまたはすぐ左のセルに挿入コストまたは削除コストを加えた値に設定される。言い換えれば、ｓ［ｉ］がｔ［ｊ］と等しくない場合、行列のセルｄ［ｊ，ｉ］を、対応する挿入コストを加えた真上のセル（ｄ［ｊ−１，ｉ］＋ｃｏｓｔ＿ｉｎｓｅｒｔｉｏｎで表される）または対応する削除コストを加えたすぐ左のセル（ｄ［ｊ，ｉ−１］＋ｃｏｓｔ＿ｄｅｌｅｔｉｏｎで表される）の最小値と等しく設定する。２２０において、ステップ２１０、２１２、２１４、２１６、および２１８は、完了するまで繰り返される。２２２において、セルｄ［ｍ，ｎ］で得られた最終コストが出力される。例におけるｃｏｓｔ＿ｉｎｓｅｒｔｉｏｎおよびｃｏｓｔ＿ｄｅｌｅｔｉｏｎは、たとえば挿入コストにｗ＝１、ｗ３＝４、および削除コストにｗ２＝１、ｗ４＝２６というように、２種類の値を有することに留意されたい。
【００２３】
言い換えれば、ｄ［ｊ，ｉ］は、文字列ｓ［０．．．ｉ］とｔ［０．．．ｊ］の間の編集距離を含む。定義によりｄ［０，０］＝０（空文字列を空文字列と等しくするために編集は必要ない）。ｄ［０，ｙ］＝ｄ［０，ｙ−１］＋（ｗ２またはｗ４）。文字列ｄ［０，ｙ−１］を作成するために編集が使用される回数が既知である場合、ｄ［０，ｙ］はｄ［０，ｙ−１］＋ターゲット文字列から現在の文字を削除するコスト（そのコストはｗ２またはｗ４となりうる）として計算されてもよい。現在の文字がｓ［０．．．ｎ］、ｔ［０．．．ｍ］の両方に存在する場合、コストｗ２が使用され、それ以外の場合ｗ４が使用される。ｄ［ｘ，０］＝ｄ［ｘ−１，０］＋（ｗ１またはｗ３）。文字列ｄ［ｘ−１，０］を作成するために編集が使用される回数が既知である場合、ｄ［ｘ，０］はｄ［ｘ−１，０］＋ｓからｔまでの現在の文字の挿入のコスト（そのコストはｗ１またはｗ３となりうる）として計算されてもよい。現在の文字がｓ［０．．．ｎ］、ｔ［０．．．ｍ］の両方に存在する場合、コストｗ１が使用され、それ以外の場合ｗ３が使用される。
【００２４】
各（ｊ，ｉ）について、ｓ［ｉ］＝ｔ［ｊ］である場合、ｄ［ｊ，ｉ］はｄ［ｊ−１，ｉ−１］と等しくなりうる。編集距離は文字列ｔ［ｊ−１］、ｓ［ｉ−１］の間で計算されてもよく、ｓ［ｉ］＝ｔ［ｊ］である場合、文字列を等しくするために、編集を使用せずに、共通の文字を両方の文字列に付加することもできる。したがって、３つの移動が採用されており、現在のｄ［ｊ，ｉ］の最小編集距離をもたらす移動が選択される。言い換えれば、
【００２５】
【表１】
0005492187.tif 000002
【００２６】
図３は、修正された編集距離および照合アルゴリズムを使用し、クエリ文字列およびデータ文字列に基づいて編集距離値を処理して生成するステップを示す。プロセスは、左右、上下、および対角の計算のうちの１つまたは複数を伴う。用語「ＡＢＣ」のクエリ文字列は、用語「ＣＢＡＸ」（Ｘはクエリ文字列内にない用語を表す）のターゲットデータ文字列に対して処理される。編集距離を計算するためのプロセスは、さまざまな方法で実行されてもよいが、編集距離の修正バージョンを実行するための特定の詳細は、開示されるアーキテクチャにより計算される場合とは異なっている。４×５行列３００は、ｎ×ｍに基づいて構築され、クエリ文字列の場合ｎ＝３であり、データ文字列の場合ｍ＝４である。クエリ文字列３０２は、行列３００の横軸に沿って配置され、ターゲットデータ文字列３０４は縦軸に沿って配置される。
【００２７】
説明では、４列（０〜３）および５行（０〜４）で表される行列３００を使用する。図２で説明される編集距離照合アルゴリズムを行０、列０で始めて左から右に適用すると、クエリ文字列ＡＢＣの空セルとターゲットデータ文字列ＣＢＡＸの空セルを比較してもクエリ文字列をターゲットデータ文字列と同じにするために用語の挿入または削除を生じないので、交差するセルｄ［０，０］は「０」を受信する。「用語」は同じなので、編集距離はゼロである。
【００２８】
クエリ文字列３０２の用語Ａと行０の空セルを比較するように右へ移動すると、文字列を同じにするために１回の削除を使用するので、セルｄ［０，１］は「１」の値を受信する。再度右に列２まで移動すると、クエリ文字列３０２の用語ＡＢとターゲットデータ文字列の空セルの間で比較が行われる。したがって、文字列を同じにするためにクエリ文字列３０２で２回の削除が使用され、その結果「２」の編集距離がセルｄ［０，２］に入れられる。同じプロセスは列３に適用され、ここでクエリ文字列３０２の用語ＡＢＣがターゲット文字列の空セルと比較され、文字列を同様にするために３回の削除を使用して、その結果「３」の編集距離がセルｄ［０，３］に入れられる。
【００２９】
行１に下り、左から右へと続行すると、クエリ文字列行の空セルがターゲットデータ文字列３０４の第１の用語Ｃと比較される。文字列を同じにするために１回の削除が使用され、「１」の編集距離がｄ［１，０］に入れられる。右に列１まで移動すると、クエリ文字列３０２の用語Ａとターゲットデータ文字列３０４の用語Ｃの間で比較が行われる。文字列を同様にするために削除および挿入が使用され、したがって、「２」の値がセルｄ［１，１］に挿入される。最後のセルｄ［１，３］までスキップすると、ＡＢＣをＣに照合するための照合プロセスは、結果として２回の削除を使用して「２」の編集距離がｄ［１，３］に入れられる。簡略にするため、および全体の編集距離を求めるために行４および列３に移動すると、用語ＡＢＣの用語ＣＢＡＸとの照合は、結果として「８」の編集距離をセルｄ［４，３］にもたらすが、ターゲット文字列の第１の用語Ｃに挿入／削除を使用して「２」の値、用語Ｂの照合に「０」の値、第３の用語ＣおよびＡの照合のための挿入／削除に「２」の値、用語Ｘの挿入に「１」の値、および位置コストに「３」の値で、結果として「８」の最終編集距離値がセルｄ［４，３］に入れられる。
【００３０】
図４は、修正された編集距離および照合アルゴリズムを使用し、クエリ文字列およびターゲットデータ文字列に基づいて編集距離値を処理して生成するステップのもう１つの例を示す。ここで、行列４００は、挿入コストのｗ１＝１、ｗ３＝４のｃｏｓｔ＿ｉｎｓｅｒｔｉｏｎ、および削除コストのｗ２＝１およびｗ４＝２６の重み付けに基づいて、ＡＢＣのクエリ文字列４０２をＡＢのターゲットデータ文字列４０４と比較するために生成される。言い換えれば、行０を左から右に作業し、クエリ文字列４０２の用語Ａをターゲット文字列４０４の前の空セルに照合すると、結果として用語Ａのターゲット文字列４０４への１回の挿入で「１」の値がセルｄ［０，１］に入れられる。クエリ文字列４０２の用語ＡＢをターゲット文字列４０４の前の空セルに照合すると、結果として用語ＡＢのターゲット文字列４０４への２回の挿入で「２」の値がセルｄ［０，２］に入れられ、クエリ文字列４０２の用語ＡＢＣをターゲット文字列４０４の前の空セルに照合すると、結果として用語ＡＢのターゲット文字列４０４への２回の挿入の値に用語Ｃに対する値ｗ４＝２６を加えて（用語Ｃは両方の文字列にはないので）「２８」の値がセルｄ［０，３］に入れられる。
【００３１】
行１を左から右に作業し（ｄ［１，０］＝１であることを理解して）、クエリ文字列４０２の用語Ａをターゲット文字列４０４の用語Ａに照合すると、結果としてターゲット文字列４０４とクエリ文字列４０２の等価で（ｄ［ｊ−１，ｉ−１］＝ｄ［０，０］＝「０」から値を取ることにより）「０」の値がセルｄ［１，１］に入れられる。クエリ文字列４０２の用語ＡＢをターゲット文字列４０４の用語Ａに照合すると、結果として用語Ｂのターゲット文字列４０４への１回の挿入で「１」の最小値がセルｄ［１，２］に入れられる。セルｄ［１，３］について、クエリ文字列４０２の用語ＡＢＣをターゲット文字列４０４の用語Ａに照合すると、結果としてｄ［ｊ−１，ｉ］＝ｄ［０，３］にｗ３を加えた値に関連付けられている最小値で「２８」の値がセルｄ［１，３］に入るが、（用語Ｃは両方の文字列にはないので）ｄ［ｊ，ｉ−１］＝ｄ［１，２］の値１に２６を加えた値２７と比較して、結果として「２７」の最小値がセルｄ［１，３］に入れられる。
【００３２】
行２を左から右に作業し、クエリ文字列４０２の用語Ａをターゲット文字列４０４の用語ＡＢに照合すると、結果としてターゲット文字列４０４の１回の削除で「１」の値がセルｄ［２，１］に入れられる。セルｄ［２，２］の距離についてクエリ文字列４０２の用語ＡＢをターゲット文字列４０４の用語ＡＢに照合すると、結果として等価となり、それによりｄ［ｊ−１，ｉ−１］＝ｄ［１，１］から値を取りセルｄ［２，２］の値「０」とする。セルｄ［２，３］について、クエリ文字列４０２の用語ＡＢＣをターゲット文字列４０４の用語ＡＢに照合すると、結果としてｄ［ｊ−１，ｉ］＝ｄ［１，３］にｗ３＝１を加えた値に関連付けられている最小値で「２８」の値となるが、比較して、用語Ｃはターゲット文字列にはないので（また、用語Ｃは両方の文字列にないので、ｄ［ｉ，ｊ−１］＝ｄ［２，２］＝０に２６を加えた値に基づいて）、「２６」の最小値がｄ［２，３］に入れられる。
【００３３】
図５は、ニューラルネットワーク５０２を採用して文書１０６の関連度スコア５０４の生成を補助するコンピュータ実施の関連度システム５００を示す。システム５００は、クエリ文字列１１０に基づいて検索結果１０８として受信した文書１０６から文書情報１０４を抽出するための処理コンポーネント１０２、および文書情報１０４から導かれたデータ文字列１１６とクエリ文字列１１０の間の編集距離１１４を計算するための近接性コンポーネント１１２を含む。編集距離１１４は、検索結果１０８の一部として文書１０６の関連度を決定する際に採用される。
【００３４】
ニューラルネットワーク５０２は、文書１０６の関連度スコアを計算する際の入力として文書情報１０４を受信するために採用されてもよい。一部またはすべての検索結果１０８の関連度スコアのみに基づくかまたはその一部に基づいて、検索結果１０８内の文書は順位付けられてもよい。システム５００は、ニューラルネットワーク５０２およびコードベースを採用して、検索結果１０８内の関連する文書を順序付けるための関連度スコアを生成する。
【００３５】
以下で、クエリ文字列と各データ文字列の間の編集距離を計算して各ペアのＴＡＵＣスコアを取得するための編集距離アルゴリズムを説明する。
【００３６】
文書にはタイトルが１つしかないので、ＴＡＵＣスコアは、以下のようにタイトルに関して計算されてもよい。
ＴＡＵＣ（Ｔｉｔｌｅ）＝ＥＤ（Ｔｉｔｌｅ）
ここで、ＴＡＵＣ（Ｔｉｔｌｅ）は、変換関数の適用後にニューラルネットワークへの入力として後に使用され、ＥＤ（Ｔｉｔｌｅ）はタイトルの編集距離である。
【００３７】
文書のアンカーテキスト、ならびにＵＲＬおよびクリック（ここでクリックはその文書がクリックされた以前実行されたクエリである）に複数のインスタンスがあってもよい。これは、その文書が、類似するクエリについてより関連が高いということである。インデックス時間において、最高頻度を有するＮ個のアンカーテキストが選択される。次いで、選択されたアンカーごとにＥＤスコアが計算される。最後に、アンカーに対してＴＡＵＣスコアが、以下のように決定される。
ＴＡＵＣ（Ａｎｃｈｏｒ）＝Ｍｉｎ｛ＥＤ（Ａｎｃｈｏｒi）｝      ｉ：上位Ｎ個のアンカー
アンカーのうちの１つとの良好な一致が存在する場合、それで十分であることが直感的に分かる。ＴＡＵＣ（Ａｎｃｈｏｒ）は、変換関数を適用した後にニューラルネットワークの入力として使用される。
【００３８】
特殊処理は、ＵＲＬ文字列のＥＤを計算する前に使用される。インデックス時間において、ＵＲＬ文字列は、分離記号として文字のセットを使用して部分に分割される。次いで、用語は、タイトルおよびアンカー用語のディクショナリから各部分に見出される。ディクショナリからの用語の出現はそれぞれ、ＵＲＬ文字列の最初から文字で位置を測定されてインデックスに格納される。
【００３９】
クエリ時間において、クエリ用語のすべての出現は、インデックス時間に格納されたインデックスから読み込まれ、中断は「非クエリ」用語で充填される。この処理の後に、ＥＤは計算される。ＥＤ処理の結果は、変換関数の適用後のニューラルネットワークの入力である。
【００４０】
処理されうるもう１つの特性は、ユーザが所与の文書コンテンツに対して入力する「クリック」の数である。ユーザが文書をクリックするごとに、ストリームがデータベースに入力されて、文書に関連付けられる。このプロセスはまた、データの短いストリームのような、文書情報テキスト内のストリームデータに適用されてもよい。
【００４１】
インデックス−時間ＵＲＬ処理アルゴリズムは、ＵＲＬ全体を、分離記号として文字のセットを使用して部分に分割する。分割関数はまた、ｕｒｌｐａｒｔ．ｓｔａｒｔｐｏｓをソース文字列内の部分の位置に設定する。分割関数は、ＵＲＬの重要ではない部分のフィルタリングを行う。
【００４２】
たとえば、「ｈｔｔｐ：／／ｗｗｗ．ｃｏｍｐａｎｙｍｅｅｔｉｎｇ．ｃｏｍ／ｉｎｄｅｘ．ｈｔｍｌ」は「ｃｏｍｐａｎｙｍｅｅｔｉｎｇ／ｉｎｄｅｘ」にフィルタリングされ、「ｃｏｍｐａｎｙｍｅｅｔｉｎｇ」および「ｉｎｄｅｘ」に分割される。
【００４３】
【表２】
0005492187.tif 000003
【００４４】
ディクショナリが「ｃｏｍｐａｎｙ  ｍｅｅｔｉｎｇ  ｃｏｍｐ」を含むと仮定すると、Ｃｏｍｐａｎｙ：０、Ｍｅｅｔｉｎｇ：７、およびＣｏｍｐ：０というキーが生成される。文字列の合計長さは、ｐａｒｔｓ＿ｓｅｐａｒａｔｏｒ＊２である。
【００４５】
ＥＤ前のクエリ時間処理に関し、クエリ時間においてクエリ用語の出現が読み込まれ、ソースＵＲＬ文字列内の出現の順序でクエリ用語の文字列が構築され、用語の間のスペースが「非クエリ」単語マークで充填される。たとえば、「ｃｏｍｐａｎｙ  ｐｏｌｉｃｙ」のクエリ文字列、および結果として生じる「ｃｏｍｐａｎｙ」「非クエリ用語」「非クエリ用語」の文字列を考察する。
【００４６】
ｐａｒｔｓ＿ｓｅｐａｒａｔｏｒ、クエリ用語位置、およびストリーム長さは、元のＵＲＬ文字列に部分が何個あるか、およびどの部分が所与のクエリを含むかを知るために決定される。用語のない各部分は、「非クエリ用語」を含むと見なされる。部分がクエリ用語から始まらない場合、「非クエリ用語」がその用語の前に挿入される。クエリ用語の間のすべてのスペースは、「非クエリ用語」で充填される。
【００４７】
図６は、クエリ文字列とデータ文字列の間の編集距離を決定するために文書情報１０４に採用されうるデータの型を示す。文書情報１０４は、たとえば、処理コンポーネント１０２による処理およびデータ（またはターゲット）文字列１１６の生成のために、タイトルテキスト６０４、アンカーテキスト６０６、ＵＲＬ６０８テキストまたは文字、およびクリック情報６１０のような、ＴＡＵＣデータ６０２を含むことができる。文書情報１０４はまた、ユーザが文書コンテンツをクリックする回数、ユーザが（クリックを介して）選択するコンテンツのタイプ、コンテンツ、一般的な文書のクリック回数などに関連するクリック情報６１０も含むことができる。
【００４８】
図７は、インデックス−時間処理データフロー７００を示す。最上部において、文書情報は、タイトル６０４、文書アンカー６０６、クリック情報６１０などの形態で、文書分析および抽出に基づいて受信される。タイトル６０４は、用語−分割アルゴリズム７０４を通じて処理され、次いでディクショナリ７０６に進む。ディクショナリ７０６は、タイトル６０４、アンカー６０６、クリック情報６１０などに見出されたさまざまな用語の一次記憶域である。ディクショナリ７０６は、ＵＲＬ分割アルゴリズム７０８を介してＵＲＬ６０８を分割するために使用される。ＵＲＬ分割アルゴリズム７０８の出力は、関連度および順位付け処理のためにインデックス付けプロセス７１０に送信される。文書アンカー６０６はまた、上位Ｎ個のアンカーのフィルター７１２を通じて処理されてもよい。クリック情報６１０は、インデックス付けプロセス７１０を介して直接処理されてもよい。その他の文書情報は、（たとえば、用語分割、フィルタリングなど）それに応じて処理されてもよい。
【００４９】
図８は、結果を順位付けするための図７のインデックスプロセス７１０からニューラルネットワークへの入力を示すブロック図８００である。インデックス付けプロセス７１０は、クエリ文字列１１０に対するＵＲＬ編集距離（ＥＤ）８０２、クエリ文字列１１０に対する上位Ｎ個のアンカーＥＤ８０４、クエリ文字列１１０に対するタイトルＥＤ８０６、クエリ文字列１１０に対するクリックＥＤ８０８、および編集距離に関連しないその他の特徴８１０を計算するために使用されてもよいが、これらの一部または全部（ＵＲＬ  ＥＤ８０２、上位Ｎ個のアンカーＥＤ８０４、タイトルＥＤ８０６、クリックＥＤ８０８、およびその他の特徴８１０）は、最終的に関連文書の関連度スコア、次いで他の文書の検索結果の中の順位付けを見出すために、ニューラルネットワーク５０２への入力として採用されてもよい。ニューラルネットワーク５０２は、文書の関連度を識別することに寄与する生の入力特徴として少なくともＴＡＵＣ特徴を受信する２層モデルであってもよい。ニューラルネットワークは、それらの特徴が、検索エンジンによりソートするために使用できる単一の数字にどのように結合されるかを決定する。
【００５０】
ニューラルネットワーク５０２は、関連度および順位付け処理に採用されうる数学モデルまたは計算モデルの一例に過ぎないことを理解されたい。単純ベイズ、ベイジアンネットワーク、決定ツリー、ファジー論理モデル、および独立のさまざまなパターンを表すその他の統計分類モデルのような、統計的回帰のその他の形態を採用することもできるが、ここで分類は順位および／または優先度を割り当てるために使用される方法を含む。
【００５１】
図９は、検索結果の生成を計算するためのニューラルネットワーク５０２、編集距離入力、および生の特徴入力の例示的なシステム９００の実施態様を示す。ニューラルネットワーク５０２の入力にある生の順位付け特徴のセット８１０は、ＢＭ２５関数９０２（たとえば、ＢＭ２５Ｆ）、クリック距離９０４、ＵＲＬ深さ９０６、ファイルタイプ９０８、および言語一致９１０を含むことができる。ＢＭ２５コンポーネントは、たとえば、本文、タイトル、著者、アンカーテキスト、ＵＲＬ、表示名、および抽出されたタイトルを含むことができる。
【００５２】
図１０は、関連度を決定する方法を示す。１０００において、クエリ文字列は、検索プロセスの一部として受信される。１００２において、文書情報は、検索プロセス中に返された文書から抽出される。１００４において、データ文字列は、文書情報から生成される。１００６において、編集距離は、データ文字列とクエリ文字列の間で計算される。１００８において、関連度スコアは、編集距離に基づいて計算される。
【００５３】
方法のその他の態様は、編集距離を計算するステップの一部として用語挿入を採用するステップ、およびデータ文字列を生成するためにクエリ文字列に用語を挿入する挿入コストを計算するステップを含むことができ、コストは重み付けパラメータとして表される。方法はさらに、編集距離を計算するステップの一部として用語削除を採用するステップ、およびデータ文字列を生成するためにクエリ文字列で用語を削除する削除コストを計算するステップを含むことができ、コストは重み付けパラメータとして表される。位置コストは、編集距離を計算するステップの一部として計算されてもよく、位置コストはデータ文字列内の用語位置の用語挿入および／または用語削除に関連する。加えて、照合プロセスは、編集距離を計算する全体コストを計算するため、データ文字列の文字とクエリ文字列の文字の間で実行される。
【００５４】
データ文字列のＵＲＬの複合語を分割するステップは、インデックス時間に生じてもよい。方法はさらに、文書内の出現度数に基づいてアンカーテキストの上位順位付けされたセットを見出すためにデータ文字列のアンカーテキストをフィルタリングするステップと、セット内のアンカーテキストの編集距離を計算するステップとを備えることができる。編集距離を計算するステップから導かれた編集距離スコアは、変換関数の適用後に２層ニューラルネットワークに入力されてもよく、そのスコアはタイトル情報、アンカー情報、クリック情報、またはＵＲＬ情報のうちの少なくとも１つに関連付けられている編集距離を計算するステップに基づいて生成される。
【００５５】
図１１は、文書の関連度を計算する方法を示す。１１００において、クエリ文字列は、検索プロセスの一部として処理されて、結果の文書のセットを返す。１１０２において、データ文字列は、結果セットの文書から抽出された文書情報に基づいて生成され、文書情報は、タイトル情報、アンカーテキスト情報、クリック情報、および文書からのＵＲＬ情報のうちの１つまたは複数を含む。１１０４において、編集距離は、用語挿入、用語削除、および用語位置に基づいて、データ文字列とクエリ文字列の間で計算される。１１０６において、関連度スコアは編集距離に基づいて計算され、関連度スコアは結果セットの文書を順位付けするために使用される。
【００５６】
方法はさらに、用語挿入、用語削除、および用語位置のそれぞれに関連付けられているコストを計算するステップと、関連度スコアの計算にコストを組み込むステップと、インデックス時間においてＵＲＬ情報の複合語を分割するステップと、インデックス時間においてアンカーテキスト情報をフィルタリングして文書内のアンカーテキストの出現度数に基づきアンカーテキストの上位順位付けセットを見出すステップとを備えることができる。クエリ文字列の用語の出現の読み取りは、ソースＵＲＬ文字列内の出現の順序でクエリ用語の文字列を構築して、用語の間のスペースを単語マークで充填するように実行されてもよい。
【００５７】
本明細書において使用されるように、用語「コンポーネント」および「システム」は、ハードウェア、ハードウェアとソフトウェアの組み合わせ、ソフトウェア、または実行中のソフトウェアのいずれかの、コンピュータ関連エンティティを示すことを意図している。たとえば、コンポーネントは、プロセッサ上で稼働するプロセス、プロセッサ、ハードディスクドライブ、複数の（光および／または磁気記憶媒体の）ストレージドライブ、オブジェクト、実行可能ファイル、実行のスレッド、プログラム、および／またはコンピュータであってもよいが、これらに限定されることはない。例として、サーバ上で稼働するアプリケーションおよびサーバはいずれもコンポーネントであってもよい。１つまたは複数のコンポーネントは、プロセスおよび／または実行のスレッド内に常駐することができ、コンポーネントは１つのコンピュータでローカライズおよび／または２つ以上のコンピュータ間で分散されてもよい。
【００５８】
これ以降図１２を参照すると、開示されるアーキテクチャによるＴＡＵＣ特徴を使用して検索結果を順位付けするために編集距離処理を実行するように動作可能なコンピューティングシステム１２００のブロック図が示される。図１２および以下の説明は、そのさまざまな態様の追加のコンテキストを提供するため、さまざまな態様が実施されうる適切なコンピューティングシステム１２００の簡潔で一般的な説明をもたらすことを意図している。上記の説明は、１つまたは複数のコンピュータ上で実行できるコンピュータ実行可能命令の一般的なコンテキストにおけるものであるが、当業者であれば、新規の実施形態はまた、その他のプログラムモジュールとの組み合わせおよび／またはハードウェアとソフトウェアの組み合わせとして実施されてもよいことを理解するであろう。
【００５９】
一般に、プログラムモジュールは、特定のタスクを実行するか、または特定の抽象データ型を実施するルーチン、プログラム、プログラム、コンポーネント、データ構造などを含む。さらに、本発明の方法が、それぞれが１つまたは複数の関連するデバイスに動作可能に結合されうる、シングルプロセッサまたはマルチプロセッサコンピュータシステム、ミニコンピュータ、メインフレームコンピュータ、およびパーソナルコンピュータ、ハンドヘルドコンピューティングデバイス、マイクロプロセッサベースまたはプログラマブル消費者電化製品などを含む、他のコンピュータシステム構成で実施されてもよいことを当業者は理解するであろう。
【００６０】
示されている態様はまた、特定のタスクが通信ネットワークを通じてリンクされるリモート処理デバイスによって実行される分散コンピューティング環境において実施されてもよい。分散コンピューティング環境において、プログラムモジュールは、ローカルおよびリモートの記憶装置に配置されてもよい。
【００６１】
コンピュータは通常、各種のコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータによってアクセスされてもよく、揮発性および不揮発性媒体、取り外し可能および固定式の媒体を含む任意の使用可能な媒体であってもよい。一例として、コンピュータ可読媒体は、コンピュータ記憶媒体および通信媒体を備えることができるが、これらに限定されることはない。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュールおよびその他のデータなど、情報を格納するための任意の方法または技術において実施される揮発性および不揮発性の、取り外し可能および固定式の媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、ＤＶＤ（ｄｉｇｉｔａｌ  ｖｉｄｅｏ  ｄｉｓｋ）またはその他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたはその他の磁気記憶装置、もしくは望ましい情報を格納するために使用できる、コンピュータによりアクセスできる任意の他の媒体を含むが、これらに限定されることはない。
【００６２】
図１２を再度参照すると、さまざまな態様を実施するための例示のコンピューティングシステム１２００は、処理ユニット１２０４、システムメモリ１２０６、およびシステムバス１２０８を有するコンピュータ１２０６を含む。システムバス１２０８は、システムメモリ１２０６を含む（これに限定されることはない）システムコンポーネントの処理ユニット１２０４へのインターフェイスを提供する。処理ユニット１２０４は、さまざまな市販のプロセッサのいずれであってもよい。デュアルマイクロプロセッサおよびその他のマルチプロセッサアーキテクチャもまた、処理ユニット１２０４として採用されてもよい。
【００６３】
システムバス１２０８は、メモリバス（メモリコントローラの有無にかかわらず）、周辺バス、およびさまざまな市販のバスアーキテクチャのいずれかを使用するローカルバスにさらに相互接続することができるいくつかのタイプのバス構造のいずれかであってもよい。システムメモリ１２０６は、不揮発性メモリ（ＮＯＮ−ＶＯＬ）１２１０および／または揮発性メモリ１２１２（たとえば、ランダムアクセスメモリ（ＲＡＭ））を含むことができる。基本入出力システム（ＢＩＯＳ；ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）は、不揮発性メモリ１２１０（たとえば、ＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭなど）に格納されてもよいが、ＢＩＯＳは起動時などにコンピュータ１２０２内の要素間の情報の転送を補助する基本ルーチンである。揮発性メモリ１２１２はまた、データをキャッシュに入れるための静的ＲＡＭのような、高速ＲＡＭを含むことができる。
【００６４】
コンピュータ１２０２はさらに、適切なシャーシでの外部使用のために構成されてもよい内部ハードディスクドライブ（ＨＤＤ）１２１４（たとえば、ＥＩＤＥ、ＳＡＴＡ）、（たとえば、取り外し可能ディスケット１２１８との間の読み取りまたは書き込みを行う）磁気フロッピー（登録商標）ディスクドライブ（ＦＤＤ）１２１６、および（たとえば、ＣＤ−ＲＯＭディスク１２２２を読み取るか、またはＤＶＤのようなその他の大容量光媒体との間の読み取りまたは書き込みを行う）光ディスクドライブ１２２０を含む。ＨＤＤ１２１４、ＦＤＤ１２１６、および光ディスクドライブ１２２０は、それぞれＨＤＤインターフェイス１２２４、ＦＤＤインターフェイス１２２６、および光ドライブインターフェイス１２２８によってシステムバス１２０８に接続されてもよい。外部ドライブ実施のためのＨＤＤインターフェイス１２２４は、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）およびＩＥＥＥ１３９４インターフェイス技術のうちの少なくとも１つまたは両方を含むことができる。
【００６５】
ドライブおよび関連するコンピュータ可読媒体は、データの不揮発性ストレージ、データ構造、コンピュータ実行可能命令などを提供する。コンピュータ１２０２の場合、ドライブおよび媒体は、適切なデジタル形式の任意のデータの格納に適応する。上記のコンピュータ可読媒体の説明は、ＨＤＤ、取り外し可能磁気ディスケット（たとえば、ＦＤＤ）、およびＣＤまたはＤＶＤのような取り外し可能光媒体を参照するが、ｚｉｐドライブ、磁気カセット、フラッシュメモリカード、カートリッジなどのような、コンピュータによって読み取ることができるその他の種類の媒体も例示の動作環境において使用されてもよく、さらに、任意のそのような媒体は、開示されるアーキテクチャの新規の方法を実行するためのコンピュータ実行可能命令を含むことができることが、当業者には理解されるべきである。
【００６６】
オペレーティングシステム１２３０、１つまたは複数のアプリケーションプログラム１２３２、その他のプログラムモジュール１２３４、およびプログラムデータ１２３６を含む多数のプログラムモジュールは、ドライブおよび揮発性メモリ１２１２に格納されてもよい。１つまたは複数のアプリケーションプログラム１２３２、その他のプログラムモジュール１２３４、およびプログラムデータ１２３６は、システム１００および関連するブロック、システム５００および関連するブロック、文書情報１０４、ＴＡＵＣデータ６０２、クリック情報６１０、データフロー７００（ならびにアルゴリズム）、およびブロック図８００（ならびに関連するブロック）を含むことができる。
【００６７】
オペレーティングシステム、アプリケーション、モジュール、および／またはデータの全部または一部は、揮発性メモリ１２１２にキャッシュされてもよい。開示されるアーキテクチャは、さまざまな市販のオペレーティングシステムまたはオペレーティングシステムの組み合わせにより実施されうることを理解されたい。
【００６８】
ユーザは、たとえばキーボード１２３８、およびマウス１２４０のようなポインティングデバイスなどの１つまたは複数の有線／無線入力デバイスを通じてコンピュータ１２０２にコマンドおよび情報を入力することができる。その他の入力デバイス（図示せず）は、マイクロフォン、ＩＲリモートコントロール、ジョイスティック、ゲームパッド、スタイラスペン、タッチスクリーンなどを含むことができる。上記およびその他の入力デバイスは、システムバス１２０８に結合される入力デバイスインターフェイス１２４２を通じて処理ユニット１２０４に接続されることが多いが、パラレルポート、ＩＥＥＥ１３９４シリアルポート、ゲームポート、ＵＳＢポート、ＩＲインターフェイスなどの他のインターフェイスにより接続することもできる。
【００６９】
モニタ１２４４またはその他の種類の表示デバイスもまた、ビデオアダプタ１２４６などのインターフェイスを介してシステムバス１２０８に接続される。モニタ１２４４に加えて、コンピュータは通常、スピーカー、プリンタなどの、他の周辺出力デバイス（図示せず）を含む。
【００７０】
コンピュータ１２０２は、リモートコンピュータ１２４８のような、１つまたは複数のリモートコンピュータへの有線および／または無線通信を介する論理接続を使用してネットワーク環境において動作することができる。リモートコンピュータ１２４８は、ワークステーション、サーバコンピュータ、ルータ、パーソナルコンピュータ、ポータブルコンピュータ、マイクロプロセッサベースのエンターテイメント電気製品、ピアデバイスまたはその他の共通ネットワークノードなどであってもよく、通常はコンピュータ１２０２に関連して説明される要素の多くまたはすべてを含むが、簡略にするため、メモリ／ストレージデバイス１２５０のみが示される。示される論理接続は、ローカルエリアネットワーク（ＬＡＮ）１２５２および／または、たとえばワイドエリアネットワーク（ＷＡＮ）１２５４などのより大規模なネットワークへの有線／無線接続を含む。そのようなＬＡＮおよびＷＡＮネットワーク環境は、オフィスおよび企業において一般化しており、イントラネットのような企業規模のコンピュータネットワークを容易にするが、それらはすべて、たとえばインターネットなどのグローバル通信ネットワークに接続することができる。
【００７１】
ＬＡＮネットワーク環境に使用される場合、コンピュータ１２０２は有線および／または無線通信ネットワークインターフェイスまたはアダプタ１２５６を介してＬＡＮ１２５２に接続される。アダプタ１２５６は、ＬＡＮ１２５２への有線および／または無線通信を容易にすることができるが、ＬＡＮ１２５２はアダプタ１２５６の無線機能と通信するために配置された無線アクセスポイントも含むことができる。
【００７２】
ＷＡＮネットワーク環境に使用される場合、コンピュータ１２０２は、モデム１２５８を含むことができるか、またはＷＡＮ１２５４の通信サーバに接続されるか、またはインターネットなどによってＷＡＮ１２５４にわたる通信を確立するための他の手段を有する。モデム１２５８は、内蔵または外付けであっても、有線および／または無線デバイスであってもよく、入力デバイスインターフェイス１２４２を介してシステムバス１２０８に接続される。ネットワーク化された環境において、コンピュータ１２０２に関連して示されるプログラムモジュール、またはその部分は、リモートメモリ／ストレージデバイス１２５０に格納されてもよい。示されるネットワーク接続は例示的なものであり、コンピュータ間の通信リンクを確立する他の手段が使用されうることを理解されたい。
【００７３】
コンピュータ１２０２は、ＩＥＥＥ８０２ファミリーの標準を使用して、たとえばプリンタ、スキャナ、デスクトップおよび／またはポータブルコンピュータ、携帯情報端末（ＰＤＡ）、通信衛星、無線により検出可能なタグに関連付けられた機器または位置（たとえば、ｋｉｏｓｋ、新聞売店、トイレ）、および電話などとの無線通信（たとえば、ＩＥＥＥ８０２．１１無線変調技法）で動作するように配置された無線デバイスのような、有線および無線デバイスまたはエンティティと通信するように動作可能である。これは、少なくともＷｉ−Ｆｉ（つまり、Ｗｉｒｅｌｅｓｓ  Ｆｉｄｅｌｉｔｙ）、ＷｉＭａｘ、およびブルートゥース（商標）無線技術を含む。したがって、通信は、従来のネットワークと同様に定義済みの構造であってもよいか、または単に少なくとも２つのデバイス間の臨時の通信であってもよい。Ｗｉ−Ｆｉネットワークは、ＩＥＥＥ８０２．１１ｘ（ａ、ｂ、ｇなど）と呼ばれる無線技術を使用して、安全で信頼性の高い高速無線通信をもたらす。Ｗｉ−Ｆｉネットワークは、コンピュータを、相互、インターネット、および有線ネットワーク（ＩＥＥＥ８０２．３関連の媒体および機能）に接続するために使用されてもよい。
【００７４】
上記で説明された内容は、開示されるアーキテクチャの実施例を含む。すべての考えられるコンポーネントおよび／または方法論の組み合わせについて説明することはもちろん不可能であるが、さらに多くの組み合わせおよび置換が可能であることを当業者であれば理解するであろう。したがって、新規のアーキテクチャは、添付の特許請求の範囲の精神および範囲内に含まれるそのようなすべての変更、修正および変形を網羅することが意図される。さらに、「含む（ｉｎｃｌｕｄｅ）」という用語が詳細な説明または特許請求の範囲で使用される限りにおいて、そのような用語は、「備える（ｃｏｍｐｒｉｓｉｎｇ）」が特許請求の範囲において暫定的な用語として採用される場合に解釈される際の「備える」と同様の方法で包括的であることが意図される。
【図１】
0005492187.tif 000004
【図２】
0005492187.tif 000005
【図３】
0005492187.tif 000006
【図４】
0005492187.tif 000007
【図５】
0005492187.tif 000008
【図６】
0005492187.tif 000009
【図７】
0005492187.tif 000010
【図８】
0005492187.tif 000011
【図９】
0005492187.tif 000012
【図１０】
0005492187.tif 000013
【図１１】
0005492187.tif 000014
【図１２】
0005492187.tif 000015