(57)【特許請求の範囲】
【請求項１】
コンピュータネットワーク上でユーザがアクセス可能なサーチエンジンを実装するコンピュータシステムにおいて、サーチ照会内のミススペルされたサーチタームを処理する方法であって、
（ａ）少なくとも同一サーチ照会内でのサーチタームの以前の出現頻度に基づいてサーチターム間の相関関係を示す相関データを生成するように、ある期間中に複数のユーザによってサーチエンジンに提出されたサーチ照会を処理するステップと、
（ｂ）複数のサーチタームを含み、サーチが行われるように情報データベースに向けられた前記サーチ照会を、コンピュータネットワーク上でユーザから受け取るステップと、
（ｃ）前記情報データベース内でマッチを生じないマッチしないサーチターム、および前記情報データベース内でマッチを生じる少なくとも１つのマッチするサーチタームを、前記サーチ照会内で識別するステップと、
（ｄ）前記少なくとも１つのマッチするサーチタームに関係していると考えられる複数の追加のタームを識別するために、少なくとも前記相関データを使用するステップと、
（ｅ）前記マッチしないサーチタームに対する正しくスペルされた置換候補タームである追加のタームを識別するために、ステップ（ｄ）において識別された前記追加のタームを前記マッチしないサーチタームと比較するステップとをコンピュータ実行ステップとして含む方法。
【請求項２】
請求項１に記載の方法であって、
（ｆ）ユーザ入力を必要とせずに、前記サーチ照会内で前記マッチしないサーチタームを前記置換候補タームで置き換えて、変更されたサーチ照会を生成するステップと、
（ｇ）サーチを実行するために、前記変更されたサーチ照会を前記情報データベースに適用するステップと、
（ｈ）前記ユーザに、ステップ（ｇ）の照会結果およびステップ（ｆ）で行われた置き換えを通知するステップとをコンピュータ実行ステップとしてさらに含む方法。
【請求項３】
ステップ（ａ）が、ユーザからサーチ照会を受け取ると、ほぼリアルタイムで前記相関データを更新するステップを含む、請求項１に記載の方法。
【請求項４】
ステップ（ａ）が、前記サーチエンジンに提出されたサーチ照会を含んだログの構文解析を行うステップを含む、請求項１に記載の方法。
【請求項５】
ステップ（ａ）が、古くなったサーチ照会提出よりも最新のサーチ照会提出を優先するように、時間ベースのバイアス機能をログに適用するステップをさらに含む、請求項４に記載の方法。
【請求項６】
時間ベースのバイアス機能を適用するステップが、前記ログにウィンドウ機能を適用するステップを含む、請求項５に記載の方法。
【請求項７】
ステップ（ａ）が、ヌル照会結果を生じるサーチ照会を無視するステップを含む、請求項１に記載の方法。
【請求項８】
ステップ（ａ）が、成功したと考えられるサーチ照会を識別するために、ユーザの照会提出後の行動を評価して、相関データを生成する際に、成功したサーチ照会により多く加重するステップをさらに含む、請求項１に記載の方法。
【請求項９】
ステップ（ｃ）が、前記サーチ照会内で複数のマッチしないサーチタームを識別するステップを含み、マッチしないサーチタームのそれぞれに対する置換候補タームを識別するために、前記マッチしないサーチタームのそれぞれについてステップ（ｅ）を繰り返すステップを含む、請求項１に記載の方法。
【請求項１０】
請求項１に記載の方法であって、ステップ（ｄ）が、
（ｄ１）複数のマッチするサーチタームのそれぞれについて、関係するタームのそれぞれのリストを識別するステップと、
（ｄ２）ステップ（ｄ１）において識別された関係するタームの前記リストを組み合わせるステップとを含む方法。
【請求項１１】
ステップ（ｅ）が、前記マッチしないサーチタームを前記追加のタームと比較するために、第１文字ストリングおよび第２文字ストリングをソートして、前記ソートされた第１文字ストリングおよび第２文字ストリングを文字単位で比較することによって、前記第１文字ストリングおよび第２文字ストリングを比較するように適合されたスペリング比較機能を使用するステップを含む、請求項１に記載の方法。
【請求項１２】
前記スペリング比較機能が、前記第１文字ストリングおよび第２文字ストリングの間の類似の度合いを示すスコアを生成し、ステップ（ｅ）が、対応する追加のタームが置換候補であるかどうかを判断するために、スコア機能によって生成されたスコアを、前記マッチしないサーチタームの文字数に依存する閾値と比較するステップをさらに含む、請求項１１に記載の方法。
【請求項１３】
ステップ（ｅ）が、前記マッチしないサーチタームに対する複数の正しくスペルされた置換候補タームを識別するステップを含み、選択のために前記ユーザに置換候補タームのリストを提示するステップをさらに含む、請求項１に記載の方法。
【請求項１４】
前記ユーザにリストを提示するステップが、変更されたサーチを開始するために、それぞれのハイパーリンク内で前記ユーザによって選択され得る置換候補タームを提示するステップを含む、請求項１３に記載の方法。
【請求項１５】
前記コンピュータシステムがウェブサイトの一部分であって、前記情報データベースが、前記ウェブサイトを介して購入可能な製品に関する情報を含む、請求項１に記載の方法。
【請求項１６】
コンピュータネットワーク上でユーザがアクセス可能なサーチエンジンを実装するコンピュータシステムにおいて、少なくとも１つのミススペルされたサーチタームを含むサーチ照会を処理する方法であって、
（ａ）複数のサーチタームを含み、サーチを行うために情報データベースに向けられたサーチ照会を、ネットワーク上でユーザから受け取るステップと、
（ｂ）前記情報データベース内でマッチを生じないマッチしないサーチターム、および前記情報データベース内でマッチを生じる少なくとも１つのマッチするサーチタームを、前記サーチ照会内で識別するステップと、
（ｃ）前記少なくとも１つのマッチするサーチタームに関係していると考えられる複数の追加のタームを識別するために、少なくとも履歴上のユーザの照会提出に基づき且つサーチターム間の相関を示すサーチターム相関データを使用するステップと、
（ｄ）前記マッチしないサーチタームに対する正しくスペルされた置換候補である追加のタームを識別するために、ステップ（ｃ）で識別された前記追加のタームを前記マッチしないサーチタームと比較するステップとをコンピュータ実行ステップとして含む方法。
【請求項１７】
前記サーチターム相関データが、少なくともサーチタームが以前に同一照会内で出現した頻度に基づく、請求項１６に記載の方法。
【請求項１８】
前記サーチターム相関データを生成するためにログ内の履歴上の照会提出を処理するステップをさらに含む、請求項１６に記載の方法。
【請求項１９】
前記履歴上の照会提出を処理するステップが、前記ログにウィンドウ機能を適用するステップを含む、請求項１８に記載の方法。
【請求項２０】
前記履歴上の照会提出を処理するステップが、ヌル照会結果を生じた照会を無視するステップを含む、請求項１８に記載の方法。
【請求項２１】
請求項１６に記載の方法であって、
（ｅ）ユーザ入力を必要とせずに、前記サーチ照会内で前記マッチしないサーチタームを前記置換候補タームで置き換えて、変更されたサーチ照会を生成するステップと、
（ｆ）サーチを実行するために、前記変更されたサーチ照会を前記情報データベースに適用するステップと、
（ｇ）前記ユーザに、ステップ（ｆ）の前記照会結果およびステップ（ｅ）において行われた置き換えを通知するステップとをコンピュータ実行ステップとしてさらに含む方法。
【請求項２２】
ステップ（ｄ）が、前記マッチしないサーチタームを前記追加のタームと比較するために、第１文字ストリングおよび第２文字ストリングをソートして、前記ソートされた第１文字ストリングおよび第２文字ストリングを文字単位で比較することによって、前記第１文字ストリングおよび第２文字ストリングを比較するように適合されたスペリング比較機能を使用するステップを含む、請求項１６に記載の方法。
【請求項２３】
スペリング比較機能が、前記第１文字ストリングおよび第２文字ストリングの間の類似の度合いを示すスコアを生成し、ステップ（ｄ）が、対応する追加のタームが置換候補であるかどうかを判断するために、スコア機能によって生成されたスコアを、前記マッチしないサーチタームの文字数に依存する閾値と比較するステップをさらに含む、請求項２２に記載の方法。
【請求項２４】
コンピュータネットワークのユーザが、項目のデータベースのサーチを行えるようにするサーチエンジンであって、
少なくともユーザの以前の照会提出に基づいて、サーチターム間の相関関係を示すサーチターム相関データを、そのメモリ内に格納しているコンピュータシステムを備え、
前記コンピュータシステムが、
ユーザから受け取ったサーチ照会を使用して項目データベースをサーチするように構成され、
前記コンピュータシステムが、少なくとも、
前記サーチ照会の、１つまたは複数のマッチするタームに関係していると考えられる複数の追加のタームを識別するために、前記サーチターム相関データにアクセスするステップと、
前記追加のタームのどれかが、マッチしないタームに対する置換候補であるかどうか判断するために、前記追加のタームのスペリングを、前記サーチ照会の、少なくとも１つのマッチしないタームのスペリングと比較するステップによって、
前記マッチするタームと前記マッチしないタームの両方を含んだ複数タームサーチ照会を処理するように構成されているサーチエンジン。
【請求項２５】
前記サーチターム相関データが、少なくとも同一のサーチ照会内で以前にサーチタームが出現した頻度に基づいている、請求項２４に記載のサーチエンジン。
【請求項２６】
ユーザ入力を必要とせずに、サーチ照会内でマッチしないタームを置換候補タームで置き換えて、変更されたサーチ照会を生成し、かつ前記変更されたサーチ照会でデータベースのサーチを行うように、前記コンピュータシステムが構成されている、請求項２４に記載のサーチエンジン。
【請求項２７】
第１文字ストリングおよび第２文字ストリングをソートして、ソートされた前記第１文字ストリングおよび第２文字ストリングを文字単位で比較することによって、前記第１文字ストリングおよび第２文字ストリングを比較するように適合されたスペリング比較機能を使用して、前記マッチしないタームを前記追加のタームと比較するように、前記コンピュータシステムが構成されている、請求項２４に記載のサーチエンジン。
【請求項２８】
前記スペリング比較機能が、前記第１文字ストリングと第２文字ストリングの間の類似の度合いを示すスコアを生成し、かつ
前記コンピュータシステムが、対応する追加のタームが置換候補であるかどうか判断するために、前記スコア機能によって生成されたスコアを閾値と比較するように構成されている、請求項２７に記載のサーチエンジン。
【発明の詳細な説明】
【０００１】
（添付資料および著作権資料）
この明細書は、２つの文字ストリングを比較するのに使用されるスペリング比較機能のＣ＋＋リストを添付資料として含む。この添付資料の内容は、著作権保護の対象となる。著作権者は、米国特許商標庁または他の特許庁のファイルまたは記録に表われるとおりに、特許文献またはその一部分を複製することに異議はないが、それ以外ではすべてどのような権利も保持する。
【０００２】
（発明の分野）
本発明は、情報サーチおよび検索に関するものであり、より詳細にはサーチ照会を処理するための方法に関係する。
【０００３】
（発明の背景）
多くのワールドワイドウェブサイトおよびオンラインサービスは、項目のドメインから興味の項目をユーザが探し出すのを助けるために、サーチエンジンプログラム（「サーチエンジン」）を提供する。例えば、ＡｌｔａＶｉｓｔａおよびＩｎｆｏｓｅｅｋは、ユーザが他のウェブサイトを探し出すのを助け、ＬｅｘｉｓおよびＷｅｓｔｌａｗなどのオンラインサービスは、ユーザが論文や法廷の見解を探し出すのを助けるためのサーチエンジンを実装している。さらに、オンラインマーチャントは通常、顧客がオンラインカタログから項目を探し出すのを助けるためのサーチエンジンを提供している。
【０００４】
サーチエンジンを使用してサーチを実行するために、ユーザは、１つまたは複数のサーチタームを含んだ照会を提出する。また、照会は明示的または暗黙的に、項目のタイトル、著者、またはサブジェクト分類などのサーチされるべきレコードフィールドを識別する。例えば、オンライン書店のユーザは、本のタイトルで表われるとユーザが信じるタームを含んだ照会を提出することができる。サーチエンジンの照会サーバプログラムは、照会にマッチするどのような項目でも識別するように、その照会を処理する。照会サーバプログラムによって識別された項目のセットは、「照会結果」と呼ばれ、通常、探し出された項目のリストとしてユーザに提示される。書店の例では、照会結果は通常、サーチタームのすべてを含んだ本のタイトルのセットであることになり、通常、これらの項目のハイパーテキストのリストとしてユーザに提示される。
【０００５】
サーチエンジンのユーザが照会内で、タームをミスタイプする、またはそれを覚えていないなどしてサーチタームをミススペルしたとき、そのミススペルされたタームは通常、サーチに含まれるデータベースのタームのどれにもマッチしないことになる。こうした場合、多くのサーチエンジンは単に、ヌル（空の）サーチ結果を返すことになる。しかし、ヌルサーチ結果をユーザに提示することは、かなりのユーザのフラストレーションを引き起こし得る。この問題を低減するため、いくつかのサーチエンジンは事実上、サーチの間、マッチしないタームを無視する。この方法には、ユーザによって指定された潜在的に重要な情報を考慮しないという不都合があり、比較的多数の無関係なタームを含んだ照会結果を生み出す傾向がある。
【０００６】
（発明の概要）
本発明は、サーチ照会内でのミススペルされたタームを修正するためのシステムおよび方法を提供することによって、前述の問題に対処する。このシステムは、サーチタームの間の相関関係を示す相関データのデータベースを含む。相関データは好ましくは、特定のタームが同一の照会内で履歴上、一緒に表われた頻度に基づき、好ましくは、照会ログファイルから生成される。一実施の形態では、データベース（表として実装される）内の各エントリは、キーワードおよび「関係ターム」リストを含み、そこでの関係タームリストは、高い頻度でキーワードとの組み合わせで表われたタームから成っている。
【０００７】
スペリング修正方法は、好ましくは、少なくとも１つのマッチするタームと少なくとも１つのマッチしないタームを含んだサーチ照会が提出されたときに呼び出される。相関データベースを使用して、マッチする１つまたは複数のタームに関係していると考えられるタームのリストが、最初に生成される。これは例えば、各マッチするタームごとに関係するタームを抽出することによって、また、照会が複数のマッチするタームを含む場合には、これらのリストを単一の関係タームリストに組み合わせることによって達成することができる。
【０００８】
次に、関係するタームは、なんらかの適切な置き換えを識別するため、そのスペリングについて、マッチしない単語と比較される。スペリングの比較は好ましくは、２つの文字ストリングの間の類似の度合いを示すスコアを生成する、アナグラムタイプのスペリング比較機能を使用して実行される。マッチしないタームと十分に類似したスペリングをもつ関係するタームが見つかった場合、そのマッチしないタームは、好ましくは、その関係するタームで自動的に置き換えられる。別法としてユーザは、タームのリストから置き換えの１つまたは複数のタームを選択するようにプロンプト指示を受けることができる。マッチしない１つまたは複数のタームが置き換えられると、その変更された照会が、サーチを実行するのに使用される。また好ましくは、ユーザは、照会に加えられた１つまたは複数の変更の通知を受ける。
【０００９】
従来のスペリング修正方法に勝る前述のスペリング修正方法の重要な利点は、選択された置き換えのタームが、ユーザによって意図されたタームである可能性が相当に高いということである。この利点は、サーチターム相関データの前述の使用、詳細には履歴の照会提出を反映する相関データの使用の結果として生じる。この方法はこれにより、照会結果がユーザの関心のある項目を含むことになる可能性を高める。もう１つの利点は、この方法が、著者やアーティストの固有名およびタイトルや製品名にある空想的なタームなどの、辞書に現れないタームを修正するのによく適しているということである。
【００１０】
この発明の別の態様によれば、相関データは好ましくは、最新の照会提出を反映し、したがってユーザの現在の好みを強く反映するように生成される。これは例えば、望みの数（例えば、１２）の最新デイリー照会ログから相関表を定期的に生成することによって達成される。最新の照会提出を強く反映する相関データを使用することは、スペリング修正処理によって行われる置き換えが、ユーザによって意図されたものとなる可能性をさらに高める。
【００１１】
次に、この発明のこれらの特徴および他の特徴が、以下に要約される図面を参照して説明される。これらの図面およびそれに関連する説明は、この発明の好ましい実施の形態を例示するために提供されるものであり、発明の範囲を制限するものではない。
【００１２】
（好ましい実施の形態の詳細な説明）
本発明は、サーチエンジンに提出される照会のスペリングエラーを訂正する方法を提供する。端的に言えば、この方法は、サーチターム相関データを使用して正確に綴られた照会のサーチタームに関係サーチタームを識別すること、およびその関係したタームのどれかがミススペルのサーチタームに類似のスペルを有することを評価することを含む。サーチターム相関データは、照会提出履歴に基づくのが好ましく、より具体的には、同じ照会内で以前一緒に実行したサーチタームの頻度に基づくのが好ましい。この方法は、例えばインターネットサーチエンジン、リーガルリサーチサーチエンジン、オンライン業者の提供するサーチエンジンなどを含む様々な異なるサーチエンジン内で実施することができる。
【００１３】
例示のため、この方法は、本明細書では製品のオンラインカタログから項目（書籍、ＣＤなど）を位置付ける際のＡｍａｚｏｎ．ｃｏｍ  Ｉｎｃ．の顧客を補助するために使用されるサーチエンジンという設定で記述する。この記述を通して、Ａｍａｚｏｎ．ｃｏｍの実施態様の様々な実施態様特有の詳細を参照する。この詳細は、本発明の好ましい実施の形態を完全に例示するために提供されるもので、本発明の範囲を限定するものではない。本発明の範囲は、添付の請求の範囲に記述されている。
【００１４】
Ｉ．ウェブサイトおよびサーチエンジンの概要
図１は、本発明に従ってサーチエンジンを実施するために使用される構成要素を含めて、Ａｍａｚｏｎ．ｃｏｍウェブサイト３０を図示している。インターネット商取引の技術で周知の通り、Ａｍａｚｏｎ．ｃｏｍウェブサイトは、ユーザが検索し、ブラウズし、オンラインカタログから書籍タイトル、音楽タイトル、その他の種類の項目を購入するための機能を含んでいる。そのカタログには多数のブラウジング可能な項目が含まれているので、そのサイトでユーザが項目を位置付けるのを補助するための効率的な機構を提供することが重要である。
【００１５】
図１に例示の通り、ウェブサイト３０はウェブサーバアプリケーション３２（「ウェブサーバ」）を含み、そのアプリケーションは、ユーザコンピュータ３４からインターネットを経て受信した要求を処理する。その要求は、カタログで製品をサーチするためにユーザによって提出されるサーチ照会を含む。ウェブサーバ３２は、照会ログ３６内での照会提出を含むユーザトランザクションを記録する。図１で示される実施の形態で、照会ログ３６は、それぞれが１日のトランザクションを表す日毎照会ログ３６のシーケンスを含む。
【００１６】
ウェブサイト３０は、目録データベース４０をサーチすることによってサーチ照会を処理する照会サーバ３８も含む。目録データベース４０は、そのサイトから購入することが可能な様々な項目に関する情報を含む。この情報は、例えば書籍タイトルの書名、著者名、出版社名、主題の記述、ＩＳＢＮ（国際標準図書番号）、音楽タイトルの曲名、アーティスト、レーベル、音楽の分類を含む。各項目の情報は、フィールド内で調整され（「著者名」フィールドや「タイトル」フィールドなど）、データベース４０をフィールド限定ベースでサーチ可能にする。このサイトは、ＨＭＴＬ（Ｈｙｐｅｒｔｅｘｔ  Ｍａｒｋｕｐ  Ｌａｎｇｕａｇｅ）コンテンツのデータベース４１を含み、そのコンテンツはとりわけ様々なカタログ項目を示し記述する製品情報ページを含む。
【００１７】
図２は、目録データベース４０で書籍タイトルをサーチするのに使用することができる書籍サーチページの一般形式を例示する。このページは、著者名フィールド、タイトルフィールド、主題フィールド４２、４３、４４とユーザに書籍タイトルのフィールド限定サーチを開始させる関連付けられた制御を含む。ユーザは、アーティスト、タイトル及びレーベルのフィールドを使用して音楽タイトルをサーチするための音楽サーチページ（図示せず）にもアクセスすることができる。このサイトの他の領域は、ユーザがサーチタームを特有のデータベースフィールドに限定することなくサーチ照会を提出することを可能にする。
【００１８】
ユーザが書籍サーチページまたはそのサイトの他のページからサーチ照会を提出すると、照会サーバ３８（図１）は目録データベース４０に照会を適用し、照会内のあらゆるフィールド制限を考慮する。この照会結果が単一項目であれば、その項目の製品情報ページがユーザに提示される。照会結果が複数項目を含む場合、項目のそれぞれの製品情報ページへのハイパーテキストリンクを含む１つまたは複数のサーチエンジン結果ページ（図示せず）を介してその項目のリストがユーザに提示される。
【００１９】
複数ターム照会については、照会サーバ３８は、実際にはサーチタームを一緒に論理積をとってサーチを実行する。たとえば、ユーザが「Ｊａｖａ」および「ｐｒｏｇｒａｍｍｉｎｇ」というタームをタイトルフィールドに入力すると、照会サーバ３８はタイトル内にそれらの両方のタームを有するすべての項目をサーチし、そのリストを戻す。したがって、この照会のいかなるサーチタームもマッチを生成しなければ（本明細書では「マッチしないターム」と称する）、この照会はヌル照会結果を生成する。この場合、「近似マッチ」とみなされる項目のリストとして、ユーザは提示され得る。
【００２０】
本明細書で記述されるサーチエンジンはサーチタームを一緒に論理積をとるが、本発明はサーチタームを結合する他の方法を使用するサーチエンジンに適用することもできることが理解されよう。
【００２１】
ＩＩ．スペリング訂正機能の概要
本発明に従って、マッチするタームとマッチしないタームの両方を含む複数タームサーチ照会をユーザが提出すると、照会サーバ３８のスペリング訂正プロセス４８（図１）は、サーチターム相関データとあいまってマッチするタームを使用して、マッチしないタームのスペリングの訂正を試みる。これは、マッチするサーチタームに関係するとみなされる追加のタームを識別するサーチターム相関表５０を使用し、次いでそのような関係タームのスペリングをマッチしないタームのスペリングと比較することによって達成されるのが好ましい。たとえば、ユーザが、
Ｊａｖａ  ＡＰＰＩ
という照会を提出し、「ＡＰＰＩ」がマッチしないタームであるとすると、スペル訂正プロセス４８は、相関表を使用して「Ｊａｖａ」に関係するとみなされるタームのリストを識別する。このリストは次のように、ｃｏｆｆｅｅ、ＡＰＩ、ｍａｎａｇｅｍｅｎｔ、ｌａｎｇｕａｇｅとなるかもしれない。この関係タームのスペリングをマッチしないタームのスペリングと比較すると、スペル訂正プロセス４８は、「ＡＰＩ」を置換候補タームとして識別する。スペリングの比較は、アナグラムタイプのスペリング比較機能を使用して実行するのが好ましいが、この機能は、２種類の文字ストリング間の類似性の度合いを示すスコアを生成するものである。
【００２２】
相関表５０に含まれるデータは、サーチタームの間の関係を示し、同じ照会内に現れる可能性のあるサーチタームを効果的に予見するのに使用される。このような予見をスペリング訂正プロセスに組み込むことによって、そのプロセスによって指示される所与の置換タームがユーザの意図したタームである可能性を著しく高める。
【００２３】
前記プロセスが所与のマッチしないタームに対する適切な置換を識別すると、そのマッチしないタームは自動的に関係タームと置き換えられる。所与のマッチしないタームに対する適切な置換が見つからなければ、そのマッチしないタームは照会から削除されるのが好ましい。一旦すべてのマッチしないタームが置換または削除されると、修正された照会が使用されて目録データベース４０をサーチし、その結果がユーザに提示される。ユーザには、そのサーチ照会になされた修正も通知される。
【００２４】
マッチしないタームの自動置換の別法として、置換候補タームのリストから置換タームを選択するように、ユーザがプロンプト指示されることができる。ユーザが修正されたサーチを開始するために選択できるそれぞれのハイパーリンク（図示せず）として各置換候補タームを提示することによって達成されることが好ましい。その結果、ユーザは修正された照会を選択することも、単一の行為で新規サーチを開始することも可能となる。
【００２５】
本発明の他の態様では、相関表５０は、同じサーチ照会内に一緒に現れた特有のサーチタームの頻度に関する履歴情報を含むかまたは反映することが好ましい。図１に示す通り、このデータはテーブル作成プロセス４６を使用して照会ログ３６から抽出されるのが好ましい。このような履歴情報をスペル訂正プロセスに組み込むことによって、このプロセスによって位置付けられる置換タームがユーザの意図したタームである可能性がさらに増大する。
【００２６】
一実施の形態（下記参照）では、テーブル作成プロセス４６は、Ｍ個の最新日毎ログファイル３６（１）ないし３６（Ｍ）から日毎の相関表５０を再生成するが、ここでＭは１０または２０などの固定番号である。この「スライディングウィンドウ」の手法は、最新照会提出にのみ基づいて相関表を生成することが有利であり、したがってユーザの現在の好みを反映するものである。たとえば、比較的多数のユーザが、Ｊｏｎ  Ｋｒａｋａｕｅｒ著「Ｉｎｔｏ  Ｔｈｉｎ  Ａｉｒ」という書籍を先週一杯サーチしたとすると、ターム「ｉｎｔｏ」、「ｔｈｉｎ」、「ａｉｒ」、「Ｋｒａｋａｕｅｒ」の間の相関関係が相応して高くなる。その結果、相関が高まることによって、この書籍をサーチする（多重ターム照会の）タームをミススペルしたユーザが、この書籍に誘導される可能性が高まる。同様の結果を達成するために多様な他のタイプのバイアス方法をログに適用することが可能であり、古い照会提出よりも最新の照会提出に重きをおく方法もこれに含まれる。
【００２７】
図３は、相関表５０の一般形式を例示する。図３に示され、本明細書で詳細を記述した実施の形態では、サーチタームの間の相関関係は同じ照会内の発生頻度にのみ基づくものである。下記で記述するように、他のタイプのサーチターム相関を追加的または別法として使用することができる。さらに、開示の実施態様では相関データを格納するためにテーブルを使用するが、他のタイプのデータベースも使用され得る。
【００２８】
図３に例示するように、相関表内の各エントリ（３つのエントリを示す）は、次の２つの主要な構成要素を有することが好ましい。すなわち、（１）キーワード６０および（２）そのキーワードに対する「関係付けられたターム」リスト６２である。関係付けられたタームリスト６２は、同じ照会内に高頻度のキーワードとして表示されたＮ（例：２０）サーチタームのリストであり、頻度に従って順序付けられる。たとえば、キーワードＣＯＳＭＯＳのエントリが、
ＣＯＳＭＯＳ：ＡＳＴＲＯＮＯＭＹ，ＳＡＧＡＮ，ＵＮＩＶＥＲＳＥ，ＳＰＡＣＥ，ＣＡＲＬ．．．
である場合、ＡＳＴＲＯＮＯＭＹは最高の頻度でＣＯＳＭＯＳと一緒に現れたこと、ＳＡＧＡＮは２番目に高い頻度でＣＯＳＭＯＳと一緒に現れたこと、以下同様のことを示している。リスト部分６２内に表示された各タームは、そのタームが同じ照会内で比較的高頻度で現れたことにより対応するキーワード６０に関係付けられると見なされる。本明細書で記述される実施態様では、キーワードと関係付けられたタームはアルファベットの大文字小文字に関係なくテーブルに格納されるが、別法として大文字小文字の情報を保存することも可能である。
【００２９】
さらに図３を参照すると、テーブル５０内の関係付けられた各タームと各キーワード６０は、（ユーザがタームを入力したサーチフィールドに基づいて）そのタームが対応するサーチフィールド４２、４３、４４を示す１文字フィールドのプレフィックス（図示せず）を好適に含んでいる。このプレフィックスは、たとえば、Ａ＝著者、Ｔ＝タイトル、Ｓ＝主題、Ｒ＝アーティスト、Ｌ＝レーベルのようなものでよい。したがって、たとえば図３のキーワードＣＯＳＭＯＳがプレフィックス「Ｔ」を有し、関連付けられたタームＳＡＧＡＮがプレフィックス「Ａ」を有する場合、これは、タイトルフィールド４３にＣＯＳＭＯＳを含む比較的多数の照会が、著者フィールド４２のＳＡＧＡＮと一緒に提出されたことを示す。下記で記述するように、関係付けられたタームのプレフィックスは、スペリング訂正プロセス４８によって使用されて、関係付けられたタームリストから非フィールド対応タームを効果的に透過し、その結果、所与のサーチフィールド内のマッチしないタームだけが同じフィールドの関係付けられたタームと比較される。したがって、たとえば著者フィールド４２内のマッチしないタームは著者フィールド４２に入力された履歴のある他のタームとのみ比較される。スペリング訂正プロセス４８は、キーワード６０のプレフィックスを同様に使用して、マッチするタームのそれぞれのサーチフィールドに対応するテーブルエントリを選択する。たとえば、タイトルフィールド４３内にマッチするタームＭＯＵＮＴＡＩＮを含む誤った照会が受信されると、スペリング訂正プロセス４８がキーワードＴＭＯＵＮＴＡＩＮを有するテーブルエントリをサーチする。
【００３０】
図３にさらに示すように、相関表５０は、キーワードとあいまって関係付けられた各タームが表示される回数を示す相関スコア６４も含むことが好ましい。たとえば、ＪＡＶＡのエントリ内にタームＰＲＯＧＲＡＭＭＩＮＧが３２０のスコアを有すると、それはＪＡＶＡとＰＲＯＧＲＡＭＭＩＮＧが同じ照会内で（それぞれのフィールドのプレフィックスによって示されたフィールド内で）３２０回表示されたことを示している。下記に記述する通り、ヌル照会結果を生成する紹介は、テーブル作成プロセス６４によって無視され、その結果、相関スコア６４には反映されない。他の実施態様では、相関スコア６４は他のタイプの相関を組み込んでもよい。下記に記述する通り、スコア６４は、照会が複数のマッチするタームを有するときは、関係付けられたタームリストを組み合わせるために使用されるのが好ましい。
【００３１】
動作中に、照会サーバ３８が、照会がマッチするタームとマッチしないタームの両方を含むと判定すると、スペリング訂正プロセス４８は当初、相関表５０にアクセスして関連付けられた関係付けられたタームリスト６２を抽出する。照会が、マッチする複数のサーチタームを含む場合、プロセス４８は、マッチする各タームに対する関係付けられたタームリスト６２を獲得し、そのリストを（下記に記述するように）一緒に組み合せて複合関係タームリストを生成する。前記の通り、プロセスは次いで結果として生じる関係付けられたタームのスペリングをマッチしないタームのスペリングと比較し、マッチしない各タームを照会から置換または削除する。このスペリング比較プロセス中、マッチしない各タームはマッチしないタームのサーチフィールド内に移動した関係付けられたタームのみと比較されるのが好ましい。
【００３２】
この方法の重要な利点は、辞書に表示されないタームのミススペリングを訂正するのに特に良く適している。したがって、この技法は、辞書にないタームによって特徴付けられる傾向のある項目を識別するのに特に有用である。このような項目は、たとえば、オンライン業者によって販売される製品、（通常、関係者の名称によって識別される）裁判所の意見、ビジネスおよびそのウェブサイトを含む。たとえば、オンライン書籍／音楽商店という状況で、この方法は、著者／アーティストの正規の名称とタイトルに表示されるしゃれたタームのミススペリングを訂正するのに有用である。たとえば、Ｊｏｎ  Ｋｒａｋａｕｅｒの著書をサーチするユーザは、タイトルの数語と「Ｋｒａｋａｕｅｒ」のミススペルした語をタイプしてもその書籍を見つけることが可能である。サーチが所望の書籍を識別する可能性は、比較的多数のユーザが最近同じ書籍をサーチした場合には特に高くなる。
【００３３】
この方法は、前の照会提出に基づくサーチターム提出を使用するのが好ましいが、相関データは他のソースによって生成することができることを理解されたい。たとえば、同じ項目レコード、タイトル、項目記述、書籍レビュー、他のデータベースフィールド内に一緒に表示されたタームを識別するために目録データベース４０に情報を処理することによって、相関データを生成することができる。すなわち、このプロセスの実行において、各項目は、例えば先週一杯に販売された項目のユニット数に比例して重み付けされ得る。
【００３４】
さらに、この方法は、他のタイプのユーザ行動履歴に基づく相関を含む他のタイプの相関を組み込むために修正されることができる。たとえば、照会ログ３６から相関データを抽出するにあたり、ユーザの後続の行動に基づいて、成功した照会結果を生成したとみなすことのできる照会提出により重きをおくことができる。たとえばユーザがサーチによって位置付けられた項目を閲覧したり、購入したり、ショッピングカートに追加したりする場合に、このような成功が想定される。
【００３５】
図１をさらに参照すると、ウェブサーバ３２、照会サーバ３８、テーブル作成プロセス４６、データベースソフトウェアは、ウェブサイト３０の１つまたは複数のＵｎｉｘベースのサーバとワークステーション（図示せず）上で実行することもできる。相関表５０は、照会サーバ３８を実施するために使用される同じワークステーション上のＲＡＭ（ランダムアクセスメモリ）に格納される。
【００３６】
ＩＩＩ．照会処理方法
次に、図４を参照しながらスペリング訂正プロセスをさらに詳細に述べるが、図４は、ユーザが照会をサブミットするときに照会サーバ３８（図１）によって実施されるステップのフローチャートである。このプロセスを示すために、ユーザがアパラチア山道のハイキングに関する本をサーチしており、「ｈｉｋｅ  Ａｐｐａｌａｔｉａｎ  ｔｒａｉｌ」の照会を主題フィールド４４（図２）中にタイプしたと仮定する。また、「Ａｐｐａｌａｔｉａｎ」はマッチしないタームであり（「Ａｐｐａｌａｃｈｉａｎ」はマッチするが）、さらに「ｈｉｋｅ」および「ｔｒａｉｌ」は、以下の関係タームリストを有するマッチするタームであると仮定する。
ＨＩＫＥ：ＣＡＭＰＩＮＧ（２３５）、ＷＡＬＫＳ（１６０）、ＴＲＡＩＬ（１５０）
ＴＲＡＩＬ：ＢＩＫＥ（２００）、ＡＰＰＡＬＡＣＨＩＡＮ（１６５）、ＷＡＬＫＳ（１６０）
また、上記のキーワードおよび関係タームがすべて、「主題」にちなんだフィールドプレフィックス「Ｓ」を有するとも仮定する。
【００３７】
ステップ７０で示すように、照会サーバ３８は、最初に目録データベース４０に照会を適用する。ステップ７２および７４で示すように、１つまたは複数の項目が検出された場合は、照会サーバはそれらの項目のリストをウェブサーバ３２に返す。ウェブサーバ３２は、そのリストを１つまたは複数のサーチ結果ページ中に取り込むか、あるいは項目が１つだけ突き止められた場合は、その項目に関する製品情報ページを返す。さらに、ウェブサーバは、検出された項目の数を照会ログ３６（図５参照）に記録する。この例では、「Ａｐｐａｌａｔｉａｎ」が主題語として目録データベース４０中にないため、項目は検出されないことになる。
【００３８】
この例のように、検出された項目の数が０であることがステップ７２で分かった場合、照会サーバ３８は、その照会がマッチするタームとマッチしないタームを両方とも含むかどうかを決定する（ステップ７６）。それらを含む場合、照会サーバ３８は、そのスペリング訂正プロセス４８（図４のステップ８０〜９０）を呼び出して、マッチしないタームの訂正を試みる。それらを含まない場合、完全なマッチが検出されなかったことを示すメッセージをユーザに返す。この場合、照会サーバ３８はまた、マッチするタームのサブセットしか含まない項目を含めることのできる「近いマッチ」のリストも生成して返す。照会サーバ３８は、追加でまたは別法として、代替スペリング訂正方法（図示せず）を呼び出して、いずれかのマッチしないタームの訂正を試みるように構成することもできる。この例では、照会がマッチするタームとマッチしないタームの両方を含むため、スペル訂正プロセス４８が呼び出されることになる。
【００３９】
スペル訂正プロセスはステップ８０で開始し、マッチする各タームに対する関係タームリストを相関表５０から検索する。ステップ８０の間に関係タームリスト（表エントリ）が検出されない場合、プロセスは、好ましくはヌル照会結果メッセージを返し、終了する（図示せず）。あるいは、プロセスは、代替スペリング訂正方法を使用してマッチしないタームの訂正を試みるか、または「近いマッチ」のリストを生成して返すこともできる。
【００４０】
この例のように、照会が複数のマッチするタームを含む場合、これらのタームに対する関係タームリストはステップ８０で共にマージされて、複合関係タームリストが形成される。これらのリストは、例えば、いずれかの交差ターム（複数のリスト中にみられるターム）の相関スコアを合計しながらリストを結合し、次いで最高頻度スコアから最低頻度スコアの順に複合リストをソートすることによって、マージすることができる。この例では、この方法は以下の関係タームリストを作成することになる。すなわちＣＡＭＰＩＮＧ（２３５）、ＷＡＬＫＳ（２１０）、ＢＩＫＥ（２００）、ＡＰＰＡＬＡＣＨＩＡＮ（１６５）、ＴＲＡＩＬ（１５０）である。ソートされた複合リストは、後続のステップの処理負担を低減するために切り捨てることができる。
【００４１】
次いで、スペル訂正プロセスはループ（ステップ８４〜９０）に入り、マッチしないタームとその関係タームのスペリングが比較される。このループの各パスで、プロセスは、マッチしないタームを関係タームのリストと１つずつ比較し（ステップ８４）、マッチしないタームのサーチフィールドに対応しないフィールドプレフィックスを有する関係タームがあればそれを排除する。これらの比較は、２つの文字ストリングを比較して数値的な類似性スコアを返すアナグラムタイプの関数を使用して行われる。類似性スコアは、２つのストリングのスペリング間における類似性の度合いを示し、したがって、所与の関係タームが目下のマッチしないタームに適した代用である可能性を示す。類似性スコアがゼロなのは類似性の度合いが最高であることを示し、スコアが漸進的に上昇するのは類似性の度合いが漸進的に低下することを示す。
【００４２】
ＳＴＲＩＮＧ１をＳＴＲＩＮＧ２と比較するためにスペリング比較関数によって実施されるステップを以下に述べるが、この場合、変数ＲＥＳＵＬＴは、その関数によって返されるスコアを表す。この方法のＣ＋＋実施例のコードリスト（２つの別々の関数として実施する）は付録として添付されている。
【００４３】
ステップ１：ＳＴＲＩＮＧ１とＳＴＲＩＮＧ２をアルファベット順にソートする。
【００４４】
ステップ２：ＰＯＩＮＴＥＲ１をソート済みＳＴＲＩＮＧ１の第１文字に、ＰＯＩＮＴＥＲ２をソート済みＳＴＲＩＮＧ２の第１文字に、ＲＥＳＵＬＴを０に初期化する。
【００４５】
ステップ３：ＰＯＩＮＴＥＲ１およびＰＯＩＮＴＥＲ２によって指されたそれぞれの文字を、大文字、小文字を考慮せずに比較する。等しい場合は、両方のポインタをストリングの次の文字に進める。そうでない場合は、アルファベット順でより若い順の文字を指している方のポインタを進め、ＲＥＳＵＬＴを１つインクリメントする。
【００４６】
ステップ４：ポインタがそれぞれのストリングの最後の文字を越えるまでステップ３を繰り返す。
【００４７】
ステップ５：ポインタの一方がまだ文字を指している場合は、そのストリング中に残っている（指されている文字を含めた）文字数をＲＥＳＵＬＴに加える。
【００４８】
この例では、ステップ８４の結果、マッチしないタームＡＰＰＡＬＡＴＩＡＮがＣＡＭＰＩＮＧ、ＷＡＬＫＳ、ＢＩＫＥ、ＡＰＰＡＬＡＣＨＩＡＮ、およびＴＲＡＩＬと比較される。これらの比較によって生成されたスコアが下の表に列挙されている。
【表１】
0004035685.tif 000002
【００４９】
ステップ８６で、スコアが評価されて、関係タームのいずれかが候補代用タームとして十分に類似するスペリングを有するかどうかが決定される。好ましい実施の形態では、関係タームのスコアがマッチしないタームの長さの半分（類似性しきい値）以下である場合、その関係タームは類似する（したがって置換候補と）と考えられる。この例では、ターム「Ａｐｐａｌａｃｈｉａｎ」は類似性テストを満たし（３  ５なので）、残りの関係タームは満たさない。
【００５０】
スペリング比較関数の効率を向上させるために、ＲＥＳＵＬＴが類似性しきい値を超えた後でステップ３の処理を停止することができる。また、十分に低いスコア（例えば０）を有するタームが識別された後で追加のタームの処理を停止することによっても効率を向上させることができる。
【００５１】
少なくとも１つの関係タームがステップ８６で類似性テストを満たす場合、マッチしないタームは最低スコアを有する関係タームで置換される（ステップ８８）。ステップ８８で複数の関係タームが最低スコアを共有する場合、関係タームリスト中で最初にくる（したがって最高の頻度スコアを有する）タームが代用として使用される。
【００５２】
ステップ８６でどの関係タームも類似性テストを満たさない場合、マッチしないタームは照会から削除される。あるいは、この時点でヌル照会結果メッセージをユーザに返してもよい。マッチしないすべてのタームが置換されるか削除された後、修正された照会を使用してサーチが再試行され、その結果がユーザに返される（ステップ９４）。
【００５３】
ステップ９４で再試行されたサーチが１つまたは複数の項目を生み出す場合、それらの項目は、照会に加えられた修正を示すメッセージと共に呈示される。この例では、このメッセージは次のように書かれる。
主題語「Ａｐｐａｌａｔｉａｎ」を含む本は見つかりませんでした。しかし我々は、ターム「Ａｐｐａｌａｔｉａｎ」の代わりに「Ａｐｐａｌａｃｈｉａｎ」を使用してあなたのサーチを再試行し、以下のタイトルを見つけました。
サーチ結果ページは、ユーザが効果的にサーチタームの代用を拒否し、かつ／またはそうでない場合に照会を変更できるように、修正済み照会を表示し、ユーザが修正済み照会を編集できるようにすることが好ましい。
【００５４】
ステップ９４の再試行サーチが厳密なマッチを何も生み出さない場合、近いマッチのリストがユーザに呈示されるか、または単に、マッチが検出されなかったことがユーザに通知される。あるいは、追加の置換およびサーチを試行することもできる。
【００５５】
以上のことから理解されるであろうが、図４のプロセスは、所望の目的を達成する様々な方式のいずれにも改変することができる。例えば、別々の相関表を生成して、異なるタイプの項目（例えば本と音楽）および／または異なるタイプのフィールド（例えばタイトルと主題）に使用することもできる。さらに、スペル訂正プロセスは、特定のフィールド（著者フィールド４２など）内のミススペリングを訂正するためだけに使用したり、タームの辞書内に出ていないマッチしないタームだけに適用したりすることもできる。
【００５６】
ＩＶ．相関表の生成
次に、図５および６を参照しながらテーブル作成プロセス４６（図１）について述べる。
【００５７】
テーブル作成プロセス４６は、一日一度など定期的に実行されるオフラインプロセスとして実行されて、新しい相関表５０を生成する。上記のように、このプロセスは、Ｍ個の最新デイリー照会ログファイル３６（１）〜３６（Ｍ）から表を生成する。相対的に小さいＭ（例えば５）を使用すると、短期の購買動向（例えば新刊、習慣ベストセラーなど）を強く反映する相関を生成する傾向があり、より大きいＭ（例えば１００）を使用すると、より広い範囲にわたるデータベースを生成する傾向がある。別法としてハイブリッド手法を使用することもでき、その場合は、表は多数のログファイルから生成されるが、最新ログファイルにより重みが与えられる。例えば、相関スコア６４を生成するときに、先週サブミットされた照会を３倍に数え、１週間前から１箇月前までにサブミットされた照会を１倍に数えることができる。
【００５８】
図５に、照会ログファイルの一般的なフォーマットを示す。ログ中の各エントリ（４つのエントリを示してある）は、特定のＨＴＴＰ（Ｈｙｐｅｒｔｅｘｔ  Ｔｒａｎｓｆｅｒ  Ｐｒｏｔｏｃｏｌ）トランザクションに関する情報を含む。例えば、エントリ１００は、１９９８年２月１３日金曜日午前２時２３分にユーザ２９３８４７１９２８７が、書籍検索ページから照会｛著者＝Ｓｅａｇａｌ，タイトル＝Ｈｕｍａｎ  Ｄｙｎａｍｉｃｓ｝をサブミットし、照会にマッチした２つの項目が検出されたことを示す。ログ中のＩＴＥＭＳ＿ＦＯＵＮＤの値は、元の照会に厳密にマッチした項目の数を示すことが好ましく、したがって「近いマッチ」もスペリング訂正から得られたマッチも反映しないことが好ましい。
【００５９】
エントリ１０２は、同じユーザが２０秒後に１８８３８２３０６４のＩＳＢＮを有する項目を選択し、この選択がサーチ結果ページから行われた（「ＨＴＴＰ＿ＲＥＦＥＲＲＥＮＣＥ」の行から明白である）ことを示す。ショッピングカートに項目を入れる要求や、項目を購入する要求など、その他のタイプのユーザアクションも同様にログファイル内に反映される。上記の例で示したように、ログファイル３６内のエントリを比較することによって、所与のユーザのナビゲーションパスを決定することができる。
【００６０】
図６に、テーブル作成プロセス４６によって実施される一連のステップを示す。この例では、プロセスは一日一度、最新デイリーログファイルが閉じられたすぐ後の真夜中に実行されると仮定する。また、Ｍ−１個の最新デイリーログファイルがプロセスのステップ１１０〜１１４を使用してすでに処理されて、それぞれのデイリー結果ファイルが生成されたとも仮定する
【００６１】
ステップ１１０で、プロセスは、新しいログファイルを解析して、ＩＴＥＭＳ＿ＦＯＵＮＤ＞０であるすべての照会サブミッションを抽出する。ヌル照会結果（ＩＴＥＭＳ＿ＦＯＵＮＤ＝０）を生じた照会サブミッションを無視することにより、（１）マッチしないタームがキーワードまたは相関タームとして相関表に追加されることが回避され、（２）マッチするターム間の潜在的に「弱い」相関関係が考慮から除外される  という重要な利点がもたらされる。。
【００６２】
ステップ１１２において、ステップ１１０において抽出されたエントリが処理されて、同じ照会内で発生する頻度によってサーチタームが相関付けられる。このステップは、同じ照会内に少なくとも１回出てくるサーチタームの対のそれぞれについて、その２つのタームが一日を通して一緒に出てくる回数をカウントすることを含む。このプロセスの間、異なるサーチフィールド中でサブミットされた同一のタームは、異なるタームとして扱われる。例えば、フィールドプレフィックス「Ｔ」を有するタームＴＲＡＩＬは、プレフィックス「Ｓ」を有するＴＲＡＩＬとは異なるものとして扱われることになる。
【００６３】
上に示したように、他の様々なファクタが、ステップ１１２プロセスの間に考慮され得る。例えば、ユーザが引き続きサーチ結果ページから項目を選択した場合に、所与の照会サブミッションを２倍に数えることができ、次いでユーザがその項目を購入したか、またはその項目を個人ショッピングカートに追加した場合には、３倍に数えることができる。外部からの相関データもまた、プロセスに組み込むことができる。ステップ１１２の結果は、図３の一般的な相関表の形をとり、デイリー結果ファイルとして保存される。
【００６４】
ステップ１１６で、ステップ１１４で作成されたデイリー結果ファイルがその前のＭ−１個のデイリー結果ファイルとマージされて、相関表５０が作成される。このプロセスの一部として、関係タームリストが固定長Ｎに切り捨てられ、得られる相関データは、効率的な参照のためにＢツリーデータ構造で格納される。次いで、新しい相関表５０が、既存の相関表の代わりにＲＡＭに書き込まれる。
【００６５】
本発明をいくつかの好ましい実施の形態から述べたが、当業者に明らかなその他の実施の形態もまた本発明の範囲内である。したがって、本発明の範囲は、添付の特許請求の範囲を参照することによってのみ定義されるものである。
【００６６】
特許請求の範囲では、プロセスステップを示すのに使用する参照文字を設けるが、これは記述の便を図るためでしかなく、ステップを実施する特定の順番を意味するためではない。
【００６７】
【表２】
0004035685.tif 000003
【表３】
0004035685.tif 000004
【表４】
0004035685.tif 000005
【図面の簡単な説明】
【図１】  この発明に係るサーチエンジンを実装するウェブサイトを示す図である。
【図２】  ウェブサイトの書籍検索ページを示す図である。
【図３】  図１の相関表の一般的形式を示す図である。
【図４】  照会提出を処理するために照会サーバによって実行されるステップを示す図である。
【図５】  図１の照会ログの一般的形式を示す図である。
【図６】  照会ログから相関表を定期的に生成するために利用される処理を示す図である。
【図１】
0004035685.tif 000006
【図２】
0004035685.tif 000007
【図３】
0004035685.tif 000008
【図４】
0004035685.tif 000009
【図５】
0004035685.tif 000010
【図６】
0004035685.tif 000011