(57)【要約】【課題】  電子番組ガイド（ＥＰＧ）データのフリーテキスト検索および属性検索を提供すること。【解決手段】  本主旨は、電子番組ガイド（ＥＰＧ）データ用の検索エンジンおよびそれに関連する方法を含む。例示的方法では、テキスト検索文字列を正規化して検索可能な語とし、その語をテキスト検索語または属性検索語として解釈する。検索文字列の語の解釈に従って、複雑度が様々に異なる検索条件を有する１つまたは複数のクエリを作成する。テキスト語および属性語の解釈に基づいてＥＰＧデータベースおよび／またはウェブリソースで１回または複数回の検索を行い、解釈に従って結果に関連度のランク付けを与える。組み合わせた検索結果は、ユーザに表示するためにグループ化、ランク付け、およびフィルタリングすることができる。結果は、検索文字列の各文字がユーザによって入力されるのと同時に漸進的に表示することもできる。【選択図】  図２
2004289848.tif 000002
【特許請求の範囲】
【請求項１】
電子番組ガイド（ＥＰＧ）データを検索する方法であって、
テキスト検索文字列を受け取ること、
前記テキスト検索文字列を正規化することであって、前記正規化には、前記テキスト検索文字列中の記号を除去または変換して検索可能な語を作成することが含まれること、
前記検索可能な語をテキスト語および属性語に分離すること、
各テキスト語および各属性語について前記ＥＰＧデータの検索を行うこと、および
前記検索文字列に合致する番組を表示するために、前記検索の結果の組合せ、ランク付け、およびフィルタリングの１つを行うこと
を含むことを特徴とする方法。
【請求項２】
前記正規化することは、前記ＥＰＧデータの言語形式に一致するように、前記検索可能な語の言語形式を変換することを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記分離することは、前記検索可能な語と属性リストの属性とを比較して、前記テキスト語と前記属性語とを分離することを含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記分離することは、前記検索可能な語とテキスト検索の結果とを比較して、前記テキスト語と前記属性語とを分離することを含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記分離することはさらに、前記検索可能な語を各種の組合せでグループ化して、検索可能なフレーズのセットを実現することを含むことを特徴とする請求項１に記載の方法。
【請求項６】
前記分離することはさらに、前記グループ化の前に、前記検索可能な語の少なくとも２つの順序を入れ替えることを含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記検索可能なフレーズと属性リストの属性とを比較して、前記検索可能なフレーズのいずれかが属性であるかどうかを判定することをさらに含むことを特徴とする請求項５に記載の方法。
【請求項８】
前記属性リストは、インデックス付けされた属性を、インデックス付けされた各属性の対象リソースおよび検索値に関係付けるインデックスを含むことを特徴とする請求項７に記載の方法。
【請求項９】
前記属性リストは、前記属性を使用して検索を導く、前記属性リストの属性に関連付けられた分岐ロジックを含むことを特徴とする請求項７に記載の方法。
【請求項１０】
前記属性リストは、前記属性を使用して検索を導く、前記属性リストの属性についてのメタデータを含むことを特徴とする請求項７に記載の方法。
【請求項１１】
前記検索語を分離することは、前記テキスト検索文字列を作成した際のユーザの意図の解釈を形成することを含むことを特徴とする請求項１に記載の方法。
【請求項１２】
前記組合せ、ランク付け、およびフィルタリングは、前記解釈に従って行われることを特徴とする請求項１１に記載の方法。
【請求項１３】
電子番組ガイド（ＥＰＧ）データ用の検索エンジンであって、
属性リストに通信的に結合され、検索文字列中の語の意味を仮定する文字列インタープリタと、
前記文字列インタープリタに結合されたクエリジェネレータと、
前記検索文字列に合致する番組結果の列挙を実現する、前記クエリジェネレータに結合された結果コンパイラと
を含むことを特徴とする検索エンジン。
【請求項１４】
前記文字列インタープリタはさらに、文字列トランスフォーマおよび属性アイデンティファイアを含むことを特徴とする請求項１３に記載の検索エンジン。
【請求項１５】
前記属性アイデンティファイアは、前記属性リストを使用して前記検索文字列中の属性語とテキスト語とを分離することを特徴とする請求項１４に記載の検索エンジン。
【請求項１６】
前記検索エンジンは、ＥＰＧデータベースおよびウェブベースのＥＰＧリソースで検索を行うことを特徴とする請求項１３に記載の検索エンジン。
【請求項１７】
検索コンパレータ／フィルタおよび結果ランカーを有する結果コンパイラをさらに含むことを特徴とする請求項１３に記載の検索エンジン。
【請求項１８】
前記検索コンパレータ／フィルタは、検索結果と、前記検索インタープリタによって仮定される語の意味とを比較することを特徴とする請求項１７に記載の検索エンジン。
【請求項１９】
前記結果ランカーは、前記文字列インタープリタが仮定した語の意味に基づいて検索結果に関連度のランク付けを割り振ることを特徴とする請求項１７に記載の検索エンジン。
【請求項２０】
電子番組ガイド（ＥＰＧ）データベース検索のシステムであって、
潜在的なテキスト語と潜在的な属性語とを有するテキスト検索文字列を受け付ける検索文字列レシーバと、
前記検索文字列レシーバに結合されたノーマライザと、
前記ノーマライザに結合され、属性リストおよび検索制約条件テーブルへのアクセス権を有する文字列インタープリタと、
前記文字列インタープリタに含まれ、前記潜在的なテキスト語と属性語とを各種の組合せでグループ化し、前記検索可能な語の少なくとも２つの順序を入れ替える文字列トランスフォーマと、
前記文字列インタープリタに含まれ、属性語とテキスト語を分離し、属性リストおよび検索制約条件テーブルに結合された属性アイデンティファイアと、
前記文字列インタープリタに結合され、テキストクエリと属性クエリとを作成し、ＥＰＧデータベースおよびウェブベースのＥＰＧリソースに結合されるクエリジェネレータと、
前記クエリジェネレータに結合された結果コンパイラと、
前記結果コンパイラに含まれ、前記文字列インタープリタに結合された検索コンパレータ／フィルタと、
前記結果コンパイラに含まれ、検索結果に関連度を割り当てる結果ランカーと、
前記結果コンパイラに含まれ、割り当てられた関連度に従って検索結果をフィルタリングする包含フィルタと、
前記検索結果に合致する番組をリストする表示と
を含むことを特徴とするシステム。
【請求項２１】
前記文字列インタープリタは、前記属性リストの情報および前記検索制約条件テーブルの情報を使用して、前記検索文字列中の語に暫定的な意味を割り当てることを特徴とする請求項２０に記載のシステム。
【請求項２２】
前記クエリジェネレータは、前記暫定的な意味に合致する検索結果を実現するために、前記暫定的な意味に基づいてクエリ条件およびクエリロジックを作成することを特徴とする請求項２１に記載のシステム。
【請求項２３】
前記文字列インタープリタは、検索結果に基づいて前記暫定的な意味を変更することを特徴とする請求項２２に記載のシステム。
【請求項２４】
電子番組ガイド（ＥＰＧ）データの検索を支援する属性リストのフォーマットであって、
前記ＥＰＧデータにリストされる番組の属性と、
前記属性の少なくとも一部についてのメタデータであって、ある属性の前記メタデータは、前記属性を前記検索で使用する検索リソースおよび値に関係付けるメタデータと
を含むことを特徴とするフォーマット。
【請求項２５】
前記メタデータは、前記属性を、制約条件テーブルの論理的検索条件のセットに関係付けることを特徴とする請求項２４に記載のフォーマット。
【請求項２６】
前記属性リストの属性を、前記検索のための関連する属性および値に関係付けるインデックスをさらに含むことを特徴とする請求項２４に記載のフォーマット。
【請求項２７】
コンピュータによって実行することが可能な命令を含む１つまたは複数のコンピュータ可読媒体であって、前記命令は、
テキスト検索文字列を受け取る動作と、
前記テキスト検索文字列を、検索する電子番組ガイド（ＥＰＧ）データと互換性がある検索語にフォーマットする動作と、
前記検索語からテキスト語および属性語を導き出す動作と、
各テキスト語および各属性語について前記ＥＰＧデータで検索を行う動作と、
各検索結果のヒットに関連度のランクを割り当てる動作と、
関連度によってフィルタリングしたヒットを表示する動作と
を行うことを特徴とするコンピュータ可読媒体。
【請求項２８】
前記フォーマットする動作は、スペルチェック、オートコレクト、語の分離、大文字／小文字の正規化、句読点の除去、記号の正規化、冠詞の除去、および前記検索文字列の複数形化の１つを含むことを特徴とする請求項２７に記載の命令を含む１つまたは複数のコンピュータ可読媒体。
【請求項２９】
単語をステミングしたバージョンの検索語を使用して検索を行う命令をさらに含むことを特徴とする請求項２７に記載の命令を含む１つまたは複数のコンピュータ可読媒体。
【請求項３０】
単語を派生したバージョンの検索語を使用して検索を行う命令をさらに含むことを特徴とする請求項２７に記載の命令を含む１つまたは複数のコンピュータ可読媒体。
【請求項３１】
前記検索語と属性リストの属性とを比較して、前記テキスト語と前記属性語との分離を行う命令をさらに含むことを特徴とする請求項２７に記載の命令を含む１つまたは複数のコンピュータ可読媒体。
【請求項３２】
前記検索語を各種の組合せでグループ化して検索フレーズのセットを実現する命令をさらに含むことを特徴とする請求項２７に記載の命令を含む１つまたは複数のコンピュータ可読媒体。
【請求項３３】
前記検索語をグループ化する命令を行う前に前記検索語の少なくとも２つの順序を入れ替える命令をさらに含むことを特徴とする請求項３２に記載の命令を含む１つまたは複数のコンピュータ可読媒体。
【請求項３４】
前記検索フレーズと属性リストの属性とを比較して、前記検索フレーズのいずれかが属性であるかどうかを判定する命令をさらに含むことを特徴とする請求項３２に記載の命令を含む１つまたは複数のコンピュータ可読媒体。
【請求項３５】
前記テキスト語および属性語を導き出す動作はさらに、前記テキスト検索文字列を作成した際のユーザの意図の解釈を形成する動作を含むことを特徴とする請求項２７に記載の命令を含む１つまたは複数のコンピュータ可読媒体。
【請求項３６】
前記解釈に従って検索結果を組み合わせる、ランク付けする、およびフィルタリングする命令をさらに含むことを特徴とする請求項３５に記載の命令を含む１つまたは複数のコンピュータ可読媒体。
【請求項３７】
電子番組ガイド（ＥＰＧ）情報を検索する方法であって、
一度に一文字ずつテキスト検索文字列を受け取ること、
新しい文字を受け取るたびに新しい検索のセットを行うことであって、
前記新しい文字を前記テキスト検索文字列のすでに受け取っている文字に連結して新しいテキスト検索文字列を作成すること、
前記テキスト検索文字列を１つまたは複数の検索可能な語に正規化すること、
前記検索可能な語をテキスト語および属性語に分離すること、
各テキスト語および各属性語について前記ＥＰＧ情報の検索を行うこと、および
表示のために前記検索の結果の組合せ、ランク付け、およびフィルタリングの１つを行うことであって、前記検索の結果は、前記新しい検索文字列に合致する番組によって表されること
を含むことを特徴とする方法。
【請求項３８】
前記テキスト検索文字列の新しい文字を受け取る前に前記結果を表示することをさらに含むことを特徴とする請求項３７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にはマルチメディアデータの通信に関し、詳細には、電子番組ガイド（ＥＰＧ）データのフリーテキストおよび属性の検索に関する。
【背景技術】
【０００２】
通常、デジタルテレビジョンシステムでは、ユーザは電子番組ガイド（ＥＰＧ）の情報を見て番組を探す。ＥＰＧは、例えば１週間などのある期間中にユーザの地域のヘッドエンド（番組提供者のチャンネルラインアップ）から視聴できる番組に関連する番組とスケジュールのメタデータからなるデータセットである。ユーザは、キーワードとなる言葉を指定して番組名のテキスト検索を行うことにより番組を検索する。検索基準に一致する検索結果、通常は番組名であるが、これを「ヒット」と呼ぶ。
【０００３】
テレビ番組は、番組名に含まれるキーワードだけでなく、番組の属性を検索することによっても見つけることができる。番組名は番組の属性の１つと考えることができるが、マルチメディアの分野では、用語「属性」は番組の名前以外の多くの特性を表す語としてより専門的な意味で使用される。そのため、属性には、番組とその放映についての無限の多数の特性が含まれる。番組とその属性は通常、ＥＧＰ情報の巨大な階層の中に適合する。「カテゴリ」など一部の属性は、求める番組が構成要素である広範囲の番組の集合を記述することができ、すなわち、「カテゴリ」属性は、求める番組を包含する階層レベルを記述し、ユーザが「カテゴリ」属性の検索を行うとそのカテゴリのすべての番組がヒットする。例えば「西部劇」の検索では、西部劇を扱った映画およびテレビのジャンルに属する多くのヒットが得られる可能性がある。
【０００４】
属性は番組名に固有の属性も記述することができ、すなわち、属性は、同じ番組の２つのバージョンを互いと異ならせるオプションを記述することができる。このより狭いタイプの属性は、特定の番組より「下」のＥＧＰ階層の要素、すなわち１つの番組に異なる特性（ｆｌａｖｏｒ）を与える要素を記述する。例えば、スペンサー  トレーシー主演の「Ｔｈｅ  Ｍｏｕｎｔａｉｎ」の１バージョンは「白黒」および「モノラル」の属性を有し、一方、別のバージョンは「カラー」、「ドルビー（登録商標）デジタル」、「クローズキャプション」、および「格付けＰＧ」の属性を有する。番組名のキーワード要素に限定されたテキスト検索では両方のバージョンがヒットとして得られ、一方、「ドルビー」の属性検索と組み合わせた番組名のキーワード要素のテキスト検索では、ドルビー（登録商標）デジタルとドルビー（登録商標）ステレオサウンドシステムのバージョンだけが得られる。
【０００５】
従来の番組名のキーワード要素のテキスト検索は、ユーザインタフェース（ＵＩ）の検索欄にキーワードテキストを入力することによって行い、従来の属性検索は、ＵＩの別の部分、または全く別個のＵＩにテキスト検索のキーワードとは別に属性の基準を（例えばチェックボックスに）入力することによって行う。別個のテキスト検索と属性検索とのヒットを両方の検索の最後にのみ論理的に組み合わせてヒットリストを生成する。
【０００６】
図１に、従来のテキスト検索１００と従来の属性検索１０２とを示し、ここでは、テキストキーワードと属性検索の条件は、１つまたは複数のＵＩにより表示される属性のチェックボックスとは別個の検索欄などに、別々に入力される。
【０００７】
ブロック１０４でテキストキーワードを入力する。ブロック１０６で、キーワードの入力とは別に属性の条件を入力する。入力されたテキストキーワードを用いて通常は番組名に対してテキスト検索を行い（ブロック１０８）、入力された属性検索の条件を用いて属性検索を行う（ブロック１１０）。それぞれの検索により別個の結果が得られる（ブロック１１２、１１４）。フィルタリングロジック１１６により結果１１２、１１４を比較し、通常はテキスト検索１００と属性検索１０２との両方を満たすヒットリスト１１８を生成する。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
通常、ユーザはＵＩの別の部分で属性を検索することを求められるので、多くのユーザは検索の入力を番組名の単語からなるキーワード式のクエリだけに限定し、また一方で、他のユーザは、デジタルテレビジョンシステムではそのように入力された属性を通常の番組名の検索語として解釈することを理解せずに、誤って番組名のテキスト検索のキーワードとして属性を入力してしまう。
【課題を解決するための手段】
【０００９】
本主旨は、電子番組ガイド（ＥＰＧ）データ用の検索エンジンおよびそれに関連する方法を含む。例示的方法では、テキスト検索文字列（ｔｅｘｔ  ｓｅａｒｃｈ  ｓｔｒｉｎｇ）を正規化して検索可能な語とし、それらの語をテキスト検索語または属性検索語として解釈する。検索文字列の語の解釈に従って、様々な複雑度の検索ロジックを使用するクエリを作成する。各テキスト語および各属性語についてＥＰＧデータベースおよび／またはＥＰＧのウェブリソースで１回または複数回の検索を行い、検索文字列の解釈に従って結果に関連度のランク付けを与える。組み合わせた検索結果は、ユーザに表示するためにランク付け、フィルタリング、およびグループ化することができる。結果は、ユーザが検索文字列の各文字を入力するのと同時に漸進的に表示することもできる。
【００１０】
一実施形態では、属性のリストを使用してテキスト語と属性語を分離することができる。例示的な属性リストはさらに、検索文字列中の各属性語について行われる検索の進行を指示する各属性のインデックスまたはメタデータも含むことができる。
【発明を実施するための最良の形態】
【００１１】
概要
電子番組ガイド（ＥＰＧ）データの迅速で、直感的、かつ正確な検索は、テレビジョンセットに付加する「セットトップボックス」システムと、テレビ放送の受信および録画機能を持つパーソナルコンピュータ（ＰＣ）システムとの両方を含むデジタルテレビジョンシステムのエンドユーザにとって重要である。例示的な主旨は、デジタルテレビジョンシステムでユーザのテキストと属性とのクエリを入力し、解釈する検索エンジンとそれに関連する方法について記載する。この迅速で正確な検索機構は、例えば、ユーザが入力した単一のテキスト列を解釈し、可能性の高いユーザの意図を推測し、ユーザが検索する内容の解釈に一致することを試みるヒット結果のセットを表示する。このような高度な検索機能は、ＰＣのデジタルビデオレコーダ（ＤＶＲ）およびセットトップボックスの市場が急速に拡大しているのに従い重要となっている。
【００１２】
図２に、ＥＰＧデータベースまたは他のリソースにおける例示的検索２００の概要を示す。例示的検索２００は、ユーザが検索文字列２０２を入力する、あるいはユーザから文字列２０２を受け取るか、またはストレージから検索文字列２０２を取り出すことから開始する。例示的な検索エンジン２０４は、検索文字列２０２を受け取り、その文字列の語にいくつかの変形を行って、複雑度が様々に異なる、考えられるクエリ命令を生成する。
【００１３】
検索文字列２０２の複雑度と不確定性とに応じて、単一の検索文字列２０２から１つまたは複数の独立した検索が発生する可能性があり、したがって、一実施形態では、文字列インタープリタ２１４が特定の検索文字列２０２に基づいて可能な限り少なく（可能であれば１つ）可能な限り限定的なクエリを作成することを試みる。例えば、一実施形態では、文字列インタープリタ２１４は、検索文字列２０２中のどの語が属性検索語として検索すべき知られている属性であるかを判断することにより、この最小限の数の簡潔かつ／または限定的なクエリを実現する。検索文字列２０２中の残りの語は、可能な属性語または可能なテキスト語である可能性があるが、（例えば知られる属性のデータベースやリストを使用して）知られる属性を判定すると、多くの場合クエリの範囲がかなり絞られる。このように、文字列インタープリタ２１４は、下記で図３との関連でより詳しく述べるように各種の方法とリソースを使用して、一連のテキスト検索２０６、属性検索２０８、条件付きテキスト検索２１０、および条件付き属性検索２１２を「検討」する。
【００１４】
一実施形態では、検索文字列２０２の可能な意味の強制的な判定は、ＥＰＧデータベースおよび／またはオンライン辞書とランキング結果とで、検索文字列２０２中の正規化した各語に対する予備的な検索を行うことによって実現される。例えば、「Ｒｙａｎ」が検索語である場合は、その解釈がそのデータベースまたは辞書でより一般的であれば、「Ｓａｖｉｎｇ  Ｐｒｉｖａｔｅ  Ｒｙａｎ」が「Ｒｙａｎ  Ｏ’Ｎｅａｌ」よりも優位にその検索の可能性の高い解釈として選択される。別の実施形態では、文字列インタープリタ２１４は、組合せの１つが検索対象のＥＰＧリソースに見つかるか、論理的に好ましいものとなるまで、検索語の様々な組合せを試みる。したがって、検索文字列２０２中の多数の属性語の中で不規則にではあるが唯一のテキスト語として出現する検索語「ｍｏｏｎ」および「ｐａｐｅｒ」の場合は、恐らくは解釈「Ｐａｐｅｒ  Ｍｏｏｎ」が得られ、この解釈は、クエリを介して実際にヒットとして見つかった場合には高いランク付けになると考えられる。
【００１５】
このように、文字列インタープリタ２１４は１つまたは複数の解釈に到達し、その解釈がクエリ２１６となる。クエリ２１６を使用して１回または複数回の検索を行い、その結果、組み合わせ、フィルタリングし、および／またはランク付けしたヒットリスト２２２が得られ、このリスト２２２がユーザに表示される。例示的な検索２００は、１つのみの検索文字列２０２から、テキストと属性とを区別する１回または複数回の検索が発生する仕組みを示す一例に過ぎない。検索文字列２０２を例えば文字列インタープリンタ２１４によって構文解析、変形、および分析して、検索文字列２０２中の語のテキストと属性とを認識した解釈を達成する。
【００１６】
一実施形態では、組み合わせ、フィルタリングし、および／またはランク付けしたヒットリスト２２２は、各種の検索パスから結果が返されると更新される。あるいは、検索文字列２０２を入力する、すなわち検索文字列２０２に各文字を追加して新規の検索および／または修正した検索を開始するのと同時に、組み合わせ、フィルタリングし、および／またはランク付けしたヒットリスト２２２に漸進的に結果を表示していくことも可能である。
【００１７】
例示的な検索エンジン
図３に、図２の例示的検索エンジン２０４をより詳細に示す。例示的検索エンジン２０４は、１つまたは複数のＥＰＧデータベース３００に通信的に結合されている。例示的検索エンジン２０４が行う機能およびプロセスについて以下で説明するが、言うまでもなく、例示的検索エンジン２０４は、ここで説明する機能およびプロセスに追加的な機能を有し、プロセスを行うことも可能であり、それには例えばデータベース内容のインデックス付け（ｉｎｄｅｘｉｎｇ）が挙げられる。言うまでもなく、例示的検索エンジン２０４の各種の実装は各種の人間言語を用いて動作する。したがって、例示的検索エンジン２０４の一部の機能は、一部の言語には当てはまらない、あるいは必要でない場合がある。
【００１８】
一般に、例示的検索エンジン２０４は、まずアプリケーションプログラムインタフェース（ＡＰＩ）などの検索文字列レシーバ３０１を公開することによりＥＰＧデータベースの検索を行うが、レシーバ３０１は検索式を受け取り、プログラム的に生成された、あるいはユーザによって生成された制約条件のセットにアクセスする。部分的にその制約条件に基づいてクエリを作成すると、例示的検索エンジン２０４は結果のセットを返す。
【００１９】
検索文字列レシーバ３０１は、１つまたは複数のＵＩを介して検索文字列２０２を受け付けることができる。ＥＰＧデータ検索のためのＵＩは、「ｔｗｏ−ｆｏｏｔ」システムまたは「ｔｅｎ−ｆｏｏｔ」システムに合わせて最適化することができる。ｔｗｏ−ｆｏｏｔシステムは、ユーザがＰＣシステムに典型的な情報入力機能を有するデジタルテレビジョンシステムである。例えば、ｔｗｏ−ｆｏｏｔシステムでは、フルキーボード、マウス、およびモニタを使用する。一方、ｔｅｎ−ｆｏｏｔシステムは、ｔｗｏ−ｆｏｏｔシステムに比べてユーザの入力機能が限られたデジタルテレビジョンシステムである。ｔｅｎ−ｆｏｏｔシステムは、セットトップボックスによって生成されたＵＩであり、検索文字列２０２は、作動させるキーが比較的少ないリモートコントロールを使用して入力される可能性がある。
【００２０】
一般的にはｔｅｎ−ｆｏｏｔシステムではＵＩを中心としたデータ入力とナビゲーションがより難しいので、ｔｅｎ−ｆｏｏｔシステムに検索を入力する際のユーザの意図を把握するのに必要なデータ量を最小限にし、一方で、検索の精度と性能とを最大にすることは有用である。
【００２１】
検索文字列レシーバ３０１は、言うまでもなく、任意数の入力欄、チェックボックス、スイッチ、および／またはデバイスからユーザ入力を受け付けることができる。ただし、入力が単に単一の検索文字列２０２である場合、例示的検索エンジン２０４は、検索文字列を「デコード」してテキスト検索の情報と属性検索との情報を分離し、適切なクエリを作成することができる。
【００２２】
検索文字列レシーバ３０１に通信的に結合されたノーマライザ３０２は、検索文字列２０２中の不規則性を変換して（すなわち「標準化されていない」語のフォーマットを変換して）、各種クエリで整合的に適用できる語にする。非標準的な入力とは、検索するＥＰＧデータベース３００の形式（ｆｏｒｍａｌｉｔｙ）に一致しないテキスト、文字、言語および／または句読法の形式を有する検索文字列２０２の語または一部である。非標準的な入力は、文字列インタープリタ２１４にとって一部または全体が解釈不能となるリスクを伴い、その形式が検索対象のＥＰＧデータベース３００に合わない時にはヒットの判定の誤りが生じる可能性がある。
【００２３】
検索要求の一部として、検索文字列レシーバ３０１には、しばしば、例えば「Ｔｈｅ  Ｗｅｓｔ  Ｗｉｎｇ」などのユーザが入力した文字列が渡される。ノーマライザ３０２または例示的検索エンジン２０４の別のモジュールは、語の分離を用いて、その句を、句を構成する１つ１つの単語に分割することを試み、各単語について個別にテキスト検索を行う。この個々の単語に分離することには、ユーザがよく知られるタイトル中の単語を省略した時、あるいは並べ替えた時に一致を見つけられる利点があるが、ユーザが意図するよりも多くのヒットを生成する可能性もある。個々の単語検索語は、しばしばスペースとダッシュとによる境界で区切られている。ノーマライザ３０２は、引用符で囲まれた句の単語間にある余分な空間を取り除くこともできる。
【００２４】
ユーザは、大文字／小文字（ｌｅｔｔｅｒ  ｃａｓｉｎｇ）を常に正しく使用して検索文字列２０２を入力するとは限らない。例えば、「Ｔｈｅ  Ｗｅｓｔ  Ｗｉｎｇ」を「ｔｈｅ  ｗｅｓｔ  ｗｉｎｇ」とタイプする可能性がある。また、ＥＰＧデータベース情報は、「ＳＵＮＤＡＹ  ＴＩＣＫＥＴ」のような句で「Ｓｕｎｄａｙ  Ｔｉｃｋｅｔ」や「ｓｕｎｄａｙ  ｔｉｃｋｅｔ」の代わりに非慣用的な大文字／小文字の使用を含むことがある。ノーマライザ３０２は、各検索語と検索対象のＥＰＧデータベースのテキストを、例えば現在のロケールの規則に従って一般的な大文字／小文字の使用（大文字または小文字）に変換することにより、大文字／小文字の正規化を行うことができる。
【００２５】
ノーマライザ３０２は、特定の記号およびマークの正規化も行うことができる。発音区別符号は、多くの国際的な言語のアルファベットに見られるアクセントまたはウムラウトなどの結合文字であり、通常は母音を伴う。本主題の一実施形態では、検索語と検索対象のデータベースのテキストとは、発音区別符号がないものとして比較する。正確な検索を促進するために、ノーマライザ３０２により記号および特殊なアルファベット文字を書き直す、かつ／または検索語に追加することもできる。例えば、ドイツ語のエスツェット「Ｂ」などの文字は「ｓｓ」と書き直して、ドイツ語のエスツェットを含む検索が、検索対象のテキスト中にエスツェットの形または「ｓｓ」の形がある場合にヒットを生成するようにする。
【００２６】
記号の正規化には、より正確な一致を得るために検索語および検索対象のテキスト両方の句読記号などの記号を除去または変換することが伴う。例えば、「Ｆ．Ｂ．Ｉ」などの略語中のピリオドや「Ｍ＊Ａ＊Ｓ＊Ｈ」のアスタリスクを取り除く。「＆」や「＠」などの記号は、各自の単語の形態「ａｎｄ」、「ａｔ」に変換することができる。例えば「Ｖｅｇａ＄」の記号「＄」など、文字の代用とする記号を変換することができる。この記号の正規化により、追加的な検索が行われる可能性がある。例えば、例示的な検索エンジン２０４は、慣例的に１つだけの形を使用し、その慣用的な１つの形に従って検索語と検索対象のテキストとの両方を正規化するのではなく、ノーマライザ３０２が検索文字列２０２を処理した後に「Ｖｅｇａｓ」と「Ｖｅｇａ＄」の両方を検索することができる。
【００２７】
冠詞と、「ａ」、「ｔｈｅ」、「ｉｓ」、「ａｒｅ」、「ｅｌ」、「ｌａ」、「ｌｏｓ」、「ｌｅｓ」などの頻出するがあまり記述的ではない単語は、ノーマライザ３０２により検索語から取り除いて処理の速度を上げることができる。一部の実施形態では、冠詞と頻出する単語は、その語が検索にある唯一の単語である場合、あるいは検索の最初のパスで結果が得られなかった場合には、除去されないか、または条件をつけて検索される。
【００２８】
例示的検索エンジン２０４は、検索の意味を何らかの形で変える標識（ｔｏｋｅｎ）があるかどうか検索文字列を事前にスキャンすることができる。例えば、ある単語の前にマイナス記号「−」が付いている場合は、その単語が一致結果に出現してはならないことを意味する。複数の語を引用符で囲まれた語句としてまとめることは、そのグループの語が与えられた順序で共に出現する時だけにそのグループを考慮すべきことを意味する。単語「ＡＮＤ」、「ＯＲ」および「ＮＯＴ」は、特殊な形で使用して検索演算子に影響を与えることができる。これにより、検索に対するより多くのコントロールがユーザに与えられる。
【００２９】
一実施形態では、ノーマライザ３０２または検索エンジン２０４の他のコンポーネントは、入力された検索文字列２０２にスペルチェックを適用することができる。いくつかのストラテジを用いて、ユーザが検索文字列２０２を入力する際に間違いを防止するのを助ける。ユーザには、スペリングのダイアログボックスあるいは「波線」によるＩＮＴＥＬＬＩＳＥＮＳＥ（登録商標）ハイライト機能などの別のテキストによる表示機構を介して、検索を実行する前に、検索テキスト中にスペルが間違った単語があることを知らせることができる。あるいは、検索の実行の最後までスペルチェックを遅らせて、正確な結果が見つからない場合にのみ行うこともできる。そしてスペルチェックは透過に行うことができる。ノーマライザ３０２によってスペルが誤っていると解釈された単語の修正後の形態は、自動的に検索文字列２０２に付加され、条件付きの検索として照会することができる。そして検索でスペルが誤ったその検索語を実際に含むヒットが得られた場合は、関連度のランキング（下記で説明する）を使用してその条件付き検索語のランクを下げることができる。
【００３０】
ノーマライザ３０２は、スペルチェックを簡略化した形態であるオートコレクトも使用することができる。各検索語を辞書と比較するのではなく、よくスペルを間違う単語の単純な検索テーブルを使用して、タイプされるのと同時に単語を修正する。オートコレクトが間違った判断を行う（ユーザが意図的に「スペルを間違えた」単語を修正する）稀な事例では、ユーザは、１回バックスペースキーを押してその自動的な修正を無効にすることができる。ユーザがタイプするのと同時に、ノーマライザ３０２により、既存のフルテキストインデックスに基づいて考えられる単語の完成形のポップアップリストを提示することもできる。これにより、ユーザが検索基準をより迅速に入力することが可能になる。
【００３１】
文字列インタープリタ２１４は、ノーマライザ３０２と通信的に結合されている。一実施形態では、文字列インタープリタ２１４は、属性リスト３１０に通信的に結合された文字列トランスフォーマ３０６および属性アイデンティファイア３０８を含む。文字列インタープリタ２１４は、検索制約条件のテーブル３１２とも通信的に結合することができる。
【００３２】
文字列トランスフォーマ３０６は、検索文字列２０２中の検索語を単独で、または組み合わせてテストして、その検索文字列２０２の解釈に到達し、その文字列を再配置すべきかどうかを判定することができる。文字列トランスフォーマ３０６は、再配置および／またはスクランブリングの方式を使用して、検索文字列２０２中の各種語の組合せを試すことができ、様々な順序においてユーザが検索しようとしている可能な属性を識別することができる。したがって、「ｄｏｌｂｙ  ｔｈｅ  ｃｌｏｓｅｄ  ｍｉｌｅ  ｇｒｅｅｎ  ｃａｐｔｉｏｎｉｎｇ」からは、「ｄｏｌｂｙ」、「ｔｈｅ  Ｇｒｅｅｎ  Ｍｉｌｅ」、および「ｃｌｏｓｅｄ  ｃａｐｔｉｏｎｉｎｇ」を含む候補検索語を得ることができる。語の２つ以上を共にまとめる方がよいと思われる場合は、文字列トランスフォーマ３０６は、語を置き換えるか、かつ／または仮定したグループを検索文字列２０２の検索語に透過に追加することができる。これを行うために、文字列トランスフォーマ３０６は、属性リスト３１０および／または検索制約条件のテーブル３１２に照らして検索語をテストすることができる。
【００３３】
文字列トランスフォーマ３０６は、検索語をステミングして検索範囲を広げることができる。「ステミング」とは、検索語から接頭辞および／または接尾辞を取り除いて、検索語の語根を元の検索語の代わりとすることを可能にするプロセスである。これにより、元の検索語のより多くの変異形を捉えるヒットが増す。例えば、「ｄｉｖｉｎｅ」という単語は「ｄｉｖｉｎ」から派生することができるので、「ｄｉｖｉｎｉｔｙ」、「ｄｉｖｉｎａｔｉｏｎ」、「ｄｉｖｉｎｅｒ」、「ｄｉｖｉｎｉｔｙ」等と一致する。文字列トランスフォーマ３０６は、「Ｐｏｒｔｅｒ」アルゴリズムなど知られるステミングアルゴリズムを使用することができる。ステミングには、検索語をその通りの形で照会した場合には捉えられなかったヒットを生成する利点があるが、しばしば関連性のないヒットを生成するという欠点がある。この作用を、文字列トランスフォーマ３０６中、あるいは結果コンパイラ（下記）など例示的検索エンジン２０４の別の部分にある関連度ランカー（ｒａｎｋｅｒ）を使用することにより軽減することができる。一部の実施形態では、ステミングを行うには、検索速度を低下させる可能性のあるデータの前処理ステップが必要となる。したがって、一部の実施形態では、ステミングは、例えば出現頻度のインデックスから決定される稀にしか出現しない単語などの特別な単語に限って行う。
【００３４】
文字列トランスフォーマ３０６は、追加的な語と文字列の変形とを行うことができる。単語の派生は、単一の語から検索語のセットを生成するものである。関連する単語のリストを使用することができる。例えば、検索語「ＮＦＬ」の場合は「フットボール」が検索文字列２０２に付加され、したがって「ＮＦＬ」から追加的な「フットボール」の検索が生じることになる。語「３０」が検索文字列２０２中に出現する場合には、語「ｔｈｉｒｔｙ」が検索文字列２０２に追加される。これらの関連語は、検索するデータに関連する例外リスト、および／またはユーザによって定義された検索制約条件テーブル３１２、あるいはプログラム的に決定された検索制約条件テーブル３１２に格納された例外リストから得ることができる。単語の派生も検索の速度を低下させる可能性があり、また関連性のない結果を生成する可能性があるが、ヒットが見つからなかったであろう事例でもヒットを生成する。関連度ランカーを使用して、関連度の低い結果をヒットリスト２２２の下部に配置することができる。
【００３５】
複数形化も使用することができる。複数形化とは、元の単語の単数形または複数形に基づいて追加的な検索語を生成する単純な形態の単語ステミングである。例えば、検索語が「ｂａｂｙ」である場合は、追加的な検索語「ｂａｂｉｅｓ」を含めることができる。
【００３６】
オプションで、文字列インタープリタ２１４または検索エンジン２０４の別のコンポーネントが、他の文字列の解釈機能およびプロセスに自然言語の構文解析を追加することができる。このタイプの構文解析には、「Ｗｈｅｎ  ｉｓ  Ｓｔａｒ  Ｗａｒｓ  ｓｈｏｗｎ  ｉｎ  Ｄｏｌｂｙ−Ｄｉｇｉｔａｌ？（「スターウォーズ」がドルビーデジタルで放映されるのはいつ？）」などの検索フレーズを、ユーザの検索要求に合った実際的な検索語に変換することが含まれる。自然言語の構文解析は非常に強力であるが、一般に、文法はユーザによる名詞／動詞の意味の選択に限定される。また、（ブール型の語検索に比べて）自然言語の検索文字列２０２では単語数が多くなることを考えると、自然言語検索は、リモートコントロールのキーパッドを使用して検索語を入力しなければならないｔｅｎ−ｆｏｏｔシステムには最適な選択肢でない可能性がある。最後に、自然言語の構文解析には、実装するのにより多くの処理能力を必要とする可能性がある。
【００３７】
文字列トランスフォーマ３０６および例示的検索エンジン２０４の他のモジュールによって行われるこれらの機能およびプロセスは一定の順序で説明したが、これらの機能およびプロセスを提示した順序は、処理のパイプラインにおける提案される使用順序を意味するものではない。多くの場合、これらの各機能およびプロセスの順序および／または実行は、生成される結果にとって重要である。
【００３８】
属性アイデンティファイア３０８は、検索語の候補あるいは可能性のある検索語を属性リスト３１０の属性と比較するなどの各種の方法により属性検索語とテキスト検索語とを分離する。属性アイデンティファイア３０８はまた、テキスト検索の結果からフィードバックを受け取り、検索文字列２０２の語に除外のプロセスを適用して属性を見つける。この場合、属性アイデンティファイア３０８は、検索語間に各種のブール型関係を仮定することができる。例えば、検索語「グリーン  マイル  ドルビー」は、「‘グリーン’ＯＲ‘マイル’ＡＮＤ  ドルビー」または「‘グリーンマイル’ＡＮＤ  ドルビー」との解釈が可能であるが、２番目の仮定されたブール型関係のセットのために、ドルビー（登録商標）デジタルまたはドルビー（登録商標）ステレオ音声の番組「ザ  グリーンマイル」のインスタンスだけを返す検索を生む可能性がある。
【００３９】
言うまでもなく、属性のリスト３１０は、文字列の解釈を高速に行うためにコンピュータメモリに格納することができる。属性リスト３１０でおよそ２００個のテレビ番組属性のリストを使用する場合は、恐らくは、ユーザが入力するテレビ番組に関連する実質的にすべての属性を属性アイデンティファイア３０８で識別し、テキスト検索の語と分離することができる。
【００４０】
コンピュータプログラムリスティング
本主旨により使用するＸＭＬテキストファイルリスティングの１セットを添付の表として提供し、参照により本明細書に組み込む。このＸＭＬテキストファイルのリスティングは、例示的な属性リスト（図３のブロック３１０など）である。
【００４１】
例示的なＸＭＬ（ｅＸｔｅｎｓｉｂｌｅ  ｍａｒｋｕｐ  ｌａｎｇｕａｇｅ）のデータ構造として表した例示的な属性リスト３１０の表現を表１〜３の「例示的属性リスト」に示す。この表現は、テレビ番組属性、要素、および値の選択の例だけを含んでいる。したがって、典型的な属性リスト３１０は、これらの表よりも多くのエントリ、または少ないエントリ、および／または異なる要素、属性、および／または値を含むことができる。
【００４２】
表の例示的なＸＭＬバージョンの属性リスト３１０によって示すように、属性リスト３１０は、属性検索語の候補を与えられた時に真／偽または「存在する／存在しない」による一致だけを提供する連続的な属性要素の配列に限定する必要はない。属性リスト３１０は、少なくとも一部の属性についてのメタデータ３１１を含むことができ、ある属性のメタデータは、その属性を、検索で使用する検索リソースと値とに関係付ける。メタデータ３１１は、属性を、検索制約条件のテーブル３１２の論理検索条件のセットにも関係付けることができる。また、属性リスト３１０は、属性リスト３１０の属性を、検索文字列２０２に合致するヒットを生成するために検索するのが妥当な他の関連する属性および値に関係付けるインデックス３１３を含むことができる。
【００４３】
一部の実施形態では、インデックス３１３および／またはメタデータ３１１は、検索文字列２０２を作成した際のユーザの意図に合致するヒットを生成できる比較的複雑な分岐ロジックおよび／または論理検索条件のツリー構造を含むことができる。例えば、属性アイデンティファイア３０８が検索語「ステレオ」について属性リスト３１０を調べる場合は、この属性の名前そのものを指定するか、かつ／または番組のステレオ属性を含む可能性が高いＥＰＧ情報中の検索フィールドを指定することにより一致を見つけることができ、例えばデータベースレコードの「ＳｃｈｅｄｕｌｅＥｎｔｒｙＡｔｔｒｉｂｕｔｅ」フィールドを見ることにより、「ステレオ」の番組を見つけることができる。さらに、候補の検索語が属性の基準に合致することが判明し、ＥＰＧデータの検索フィールドを指定すると、属性リスト３１０は、ステレオの番組を見つける検索語、キー、またはカテゴリを表すことができる例えば「ＭＳＥＰＧＡ＿ＳＴＥＲＥＯ」などの１つまたは複数の正確な値も生じることができる。
【００４４】
属性リスト３１０のインデックス機能は複数分岐することができる。例えば、属性アイデンティファイア３０８が検索語の候補「スポーツ」について属性リスト３１０を調べる場合、属性リスト３１０は、「スポーツ」を属性として識別することができ、さらにその語が「カテゴリ」タイプの属性であると識別し、属性アイデンティファイア３０８に、関連する番組を求めて３つの他のカテゴリ、「ニュース」、「特別番組」、および「ＭＳＥＰＧＣ＿ＳＰＯＲＴＳ」をクロスチェックするように指示することができる。
【００４５】
文字列トランスフォーマ３０６について上述した機能およびプロセスを展開し、属性リスト３１０を介して属性と関連するメタデータを識別することにより、文字列インタープリタ２１４は、検索文字列２０２を作成した際のユーザの意図に近似しようとする検索語のセットに到達する。すなわち、文字列インタープリタ２１４は、大半のユーザがその検索文字列２０２を作成した場合に求めると思われる内容に一致するヒットを返す確率が高いテキスト検索語と属性検索語とのセットを実現する。例えば、ユーザが検索文字列「ＳＦ  ドルビー  レターボックス」を作成した場合、例示的な検索エンジン２０４は、レターボックス形式によりドルビー（登録商標）ステレオ音声で放映されるＳＦ番組のヒットリスト２２２を返す。ユーザが検索文字列「ゴールデンタイム  ネットワーク  コメディ」を作成した場合、例示的検索エンジン２０４は、ネットワーク局のゴールデンタイムのコメディ番組のヒットリスト２２２を返す。ユーザが検索文字列「格付けＰＧのドラマ」を作成した場合、例示的検索エンジン２０４は、格付けがＰＧのドラマ番組のヒットリスト２２２を返す。ユーザが検索文字列「Ｄｉｓｃｏｖｅｒｙ」を作成した場合、例示的検索エンジン２０４は、番組名に「ｄｉｓｃｏｖｅｒｙ」を含む番組、および例えば「ＤＩＳＣＯＶＥＲＹ  ＣＨＡＮＮＥＬ（登録商標）」などチャンネル名に「ｄｉｓｃｏｖｅｒｙ」を含むチャンネル両方のヒットリスト２２２を返す。
【００４６】
クエリジェネレータ３１４は、文字列インタープリタ２１４に通信的に結合されている。クエリジェネレータ３１４は、テキストクエリフォーミュレータ３１６と属性クエリフォーミュレータ３１８とを含むことができる。一実施形態では、テキストクエリフォーミュレータ３１６および属性クエリフォーミュレータ３１８は、ＥＰＧデータベース３００およびウェブベースのＥＰＧリソース３３４で検索する、可能な限り少なく（多くの場合１つ）限定的なクエリを作成する。複数のクエリを作成する場合は、結果を組み合わせることができる。
【００４７】
文字列インタープリタ２１４から受け取る各検索語について、クエリジェネレータ３１４は、ＥＰＧデータベース３００またはウェブベースのＥＰＧリソース３３４を照会する際に一致を見つける方式に影響する演算子を適用することができる。一実施形態では、各演算子は、検索対象のテキスト中で検索語を見つけなければならない（または見つけてはならない）場所または相対的位置を指定する。いくつかの例示的な演算子を以下で説明する。「完全一致」演算子は、その検索語が検索対象のテキストの所与の部分に正確に一致することを指定する。すなわち、クエリジェネレータ３１４が特定タイプのフィールドを検索している場合、検索語はそのフィールドに正確に一致しなければならない。「前方一致（フレーズ）」演算子は、検索対象のテキストフィールドの冒頭で検索語を見つけることを指定する。「前方一致（単語）」演算子は、検索語が、検索対象のテキストフィールド中のある単語の冒頭であることを指定する。「ｃｏｎｔａｉｎｓ」演算子は、検索語を検索対象のテキストフィールド中のどこで見つけてもよいことを指定する。
【００４８】
上述の各演算子について、「逆演算子」（ＮＯＴの形）を使用して、個々の条件が真である場合には検索エンジン２０４がヒットを生成しないことを指定することができる。検索演算子「ＡＮＤ」および「ＯＲ」も使用して、検索対象のテキストフィールドにすべての検索語を見つけなければならないか、または検索語の一部のみが一致すればよいことを指定することができる。
【００４９】
データマネジャ３１９は、クエリジェネレータ３１４が生成する各種の検索語を使用してＥＰＧデータベース３００で検索を行う。本主旨の一部の実施形態では、データマネジャ３１９は、ＳＱＬ（構造化クエリ言語）データベースエンジンまたはＪＥＴデータベースエンジンであっても、それらを用いてもよく、その場合は、結果コンパイラ３２０の機能の一部を兼ね備えることができる。したがって、データマネジャ３１９は、その内部で複数の検索パスを実行し、それらのパスを組み合わせることができる。そのため、ＥＰＧデータベース３００は、いくつかの異なるフォーマット（例えばＸＭＬ、バイナリ、ＪＥＴ、ＳＱＬなど）をとることができるが、それらのフォーマットには記憶に適したものと、ネットワークを通じた伝送に適したものとがある。伝送媒体の制約に応じて、伝送に最適なフォーマットは、記憶および／または検索に最適なフォーマットと異なる場合がある。上記のフォーマットの選択とぞれぞれの相対的な長所と短所との一部について以下で述べる。
【００５０】
一部のガイドサービスでは、定義されたスキーマに一致するようにフォーマットされたＸＭＬを使用して複数日分のガイドをクライアントに送信している。ＸＭＬは、理解が容易で、人間が読むことができ、既存のツールを多数所有するので扱いが利便なフォーマットである。しかしＸＭＬはあまりコンパクトなフォーマットではない。その理由から、ｅＨｏｍｅガイドは送信する前に圧縮してＣＡＢファイルにし、受信完了後に解凍する。
【００５１】
大きなＸＭＬファイルを容易に検索することはできない。例えば、１０日分のＥＰＧデータは、６．６メガバイトのファイルを満たす可能性がある。このサイズのＸＭＬファイルをドキュメントオブジェクトモデル（ＤＯＭ）にロードするには、およそ９０メガバイトのランダムアクセスメモリが必要となる。検索のたびにそのような大きなファイルをスキャンするのは実際的ではない。これらの理由から、ＸＭＬフォーマットは主に伝送と永続的な記憶とに使用することができる。多数のクライアントがＥＰＧデータファイルをロードする時、検索のために、非テキストデータはメモリに格納され、すべてのテキストベースのデータはメモリマップファイルに書き込まれる。一部のＥＰＧデータＡＰＩは、データおよび／または検索パターンの変更に対応するためにはカスタムデータベースを実装しなければならない。
【００５２】
ＥＰＧデータベース３００の別の選択肢はバイナリフォーマットである。バイナリフォーマットはしばしば非常にコンパクトであるが、一般にはその生成とブラウズを行うにはカスタムツールに依存する。ＸＭＬファイルと同様にバイナリファイルは必ずしも検索には最適でなく、検索のために代替の中間記憶フォーマットを必要とする。
【００５３】
検索エンジン２０４は、ＥＰＧデータベース３００を照会するのに、データベースツールとともに広くサポートされているＪＥＴデータベースエンジンを使用することもできる。ＭＤＡＣと称する再配布可能なＡＰＩは、ＳＱＬ、ＡＤＯ、またはＯＬＥ  ＤＢを使用してＪｅｔデータベースを作成し、照会するためのリッチなＡＰＩを提供する。ＥＰＧデータベース３００にＪｅｔデータベースを使用する利点の１つは、業界標準のＳＱＬコマンドを使用した検索の容易さと、共通ソフトウェアを使用した閲覧の容易さである。Ｊｅｔを使用した検索のパフォーマンスは一般に、インデックスを適切に生成し、記憶すれば、多くの他の方式よりも高速である（１つの例外はＳＱＬサーバ）。また、Ｊｅｔデータベースを単一のファイルに格納して、ＥＰＧデータベース３００全体の操作を容易にする。
【００５４】
Ｊｅｔデータベースエンジンと同様に、ＳＱＬは、広くサポートされるＥＰＧデータベース３００向けのデータベースプラットフォームであり、ツールとＡＰＩとの大規模なライブラリを備える。現在のよく知られるバージョンのＳＱＬサーバはサーバマシンでしか作動しないが、ＭＳＤＥと称するバージョンのＳＱＬサーバ（あるいはＳＱＬ  Ｄｅｓｋｔｏｐ  Ｅｄｉｔｉｏｎ）は、現在の多くのオペレーティングシステムのソフトウェアバージョンにインストールすることができる。適切にインデックス付けされたＳＱＬデータベースの検索は、恐らくは他の知られるデータ検索技術よりも高速で、柔軟性がある。ただし、ＳＱＬデータベースは、ネットワークを通じた伝送は容易ではない。ＭＳＤＥを使用するには、ＥＰＧデータを別のフォーマットからＳＱＬデータベースにロードする後処理ステップが必要となる。また、サーババージョンとは異なり、ＭＳＤＥは、自然言語検索あるいはフルテキストのインデックス付けをサポートするとは限らない（他の方法を用いればどちらもエミュレートすることは可能）。
【００５５】
多くの場合、ＥＰＧデータベース３００のネイティブフォーマットは、例示的検索エンジン２０４が必要とする最終的な形態ではないことに留意されたい。例えば、データインデックスを生成する必要があるか、あるいは検索のために最適化されているがネットワークを介して送信するのは難しい代替のデータベースにデータを読み込む必要がある場合がある。一実施形態では、例示的検索エンジン２０４は、検索をより高速にするために不必要なデータを破棄し、ユーザ固有のデータを併合することさえある。
【００５６】
データインデックスを使用する場合、検索エンジン２０４は、フルテキストのインデックス付けを実装することができる。これには、逆引きの単語（ｒｅｖｅｒｓｅ  ｗｏｒｄ）インデックスをテキストベースのＥＰＧデータの各要素の中に生成することが必要となる。フルテキストのインデックス付けにより、ＥＰＧデータベース３００がより大きくなり、インデックスの生成にかかる時間が増すが、検索のパフォーマンスが大幅に高まる。
【００５７】
検索エンジン２０４は、署名のインデックス付けも使用することができる。フルテキストのインデックス付けと同様に、署名のインデックス付けは、可能な検索の一致を迅速に識別する一方式である。ＥＰＧデータベース３００では、各データ行（番組、チャンネルなど）は、各単語中に出現する文字を示す、ハッシュに似たバイナリの署名を有する。検索語と検索対象のテキストの単語とにこのハッシュに似た計算を行い、２進の算術演算を使用して結果を照合すると、その単語が検索語に一致するかどうかを迅速に概算することができる。次いで、一致した単語を含む行がヒットを生成すべきかどうかを判定するために、よりプロセッサ集約的な第２の検索を必要とする場合がある。
【００５８】
上記で触れたように、本主旨は、単一の検索文字列２０２からテキスト検索語と属性検索語とを導き出す検索エンジン２０４の能力によって制限されない。例示的な検索エンジン２０４は、単一の検索文字列２０２からテキスト検索語と属性検索語とを導き出すのに加えて、ＵＩ中の各種の入力フィールドなど複数のソースから検索語を導き出すことができる。例えば、一部の製品では、「ステレオ」、「クローズドキャプション」、「開始時刻」、「公開年」などの属性をしばしば検索語として利用することができるが、これらは一部のＵＩではチェックボックスやラジオボタンを介して入力される。これらの属性は、例示的検索エンジン２０４により検索語として検索ＡＰＩに渡すことによって対処することもできる。この対処は、単一の検索文字列２０２から他の属性検索語とテキスト検索語とを導き出すことから検索エンジン２０４を制限しない。
【００５９】
例示的検索エンジン２０４は、ユーザが検索を行いたいフィールドを選択するようにユーザを促すことができる。そのため、例示的検索エンジン２０４は、すべてのドメイン（番組名、説明、チャンネル、出演者など）を自動的に検索し、各自の予測される関連度によってヒットをランク付けするのに加えて、ユーザがフィールドおよび／または検索ドメインを手動で絞りこむことも可能にする。
【００６０】
例示的検索エンジン２０４は、データマネジャ３１９および文字列インタープリタ２１４に通信的に結合された結果コンパイラ３２０も含む。結果コンパイラ３２０中のヒットレシーバ３２２は、各種の検索モダリティ、または複数のデータベースを検索する単一の検索モダリティからヒットを収集する。複数の検索は同時に行うことができるので、ヒットレシーバ３２２は、さらにコンパイルを進めるまで一時的にヒットを格納することができる受け取りマニホールドまたはバッファを備えることができる。
【００６１】
例示的検索エンジン２０４では、検索コンパレータ／フィルタ３２４が、ヒットレシーバ３２２および文字列インタープリタ２１４と通信的に結合されている。検索コンパレータ／フィルタ３２４は、文字列インタープリタ２１４が確立した文字列の解釈に照らしてヒットをテストする。上述のように、文字列インタープリタ２１４は、文字列トランスフォーマ３０６および属性アイデンティファイア３０８を介して、検索文字列２０２を作成した際のユーザの意図の実際的な仮説または解釈に到達する。結果コンパイラ３２０では、ヒットが解釈に合致しない場合は、そのヒットをフィルタリングすることができる。すなわち、表示されるヒットリスト２２２から排除するか、表示されるヒットリスト２２２中でランク付けする目的で格下げすることができる。一実施形態では、検索コンパレータ／フィルタ３２４は、検索のセットを１つずつスキャンして、各結果が本当にヒットであるかどうかを判定する。これは、すべてのヒットを含めるのと同時に、すべてのミスを排除するのに十分な精度までクエリを分解（ｆａｃｔｏｒ）できなかった場合に行われる可能性がより高い。解釈の一例として、元の検索文字列２０２が「ダック  ドルビー」であり、文字列インタープリタ２１４が、「ドルビーデジタル方式のドナルドダック」の解釈よりも「トーマスドルビーによる‘ハワード  ザ  ダック’」の解釈を支持する場合には、ドナルドダックのヒットは、ヒットリスト２２２から完全に排除されるか、または少なくともより低いランクを与えられる。
【００６２】
結果ランカー３２６は、すべての検索が終了した時か、あるいは一部の実施形態ではヒットレシーバ３２２が結果をばらばらに受け取り、その結果が検索コンパイラ／フィルタ３２４を通じて渡された時に、関連度またはその他の基準によりヒットを表示のために編成することができる。検索エンジン２０４が生成したヒットはしばしばランク付けして、最も可能性が高い結果、すなわち検索文字列２０２を作成した際のユーザの意図解釈に最も近いヒット（文字列インタープリタ２１４によって仮定される）を最初に提示する方式で、ヒット結果を表示のためにソートすることができる。例えば、各検索語の正確な一致には１００％の関連度ランキングを与え、最も高い優先度を与えることができる。ステミングやスペル補正などの何らかの変形の後を行った時にしか検索対象のテキストと一致しないヒットには、通常はより低い関連度を与える。
【００６３】
包含フィルタ３２８は、結果ランカー３２６と通信的に結合することができる。一部の変形形態では、包含フィルタ３２８は一定の方式でフィルタリングするようにプログラム的に設定することができ、一方、他の変形形態ではユーザによって調整することができる。例えば、包含フィルタ３２８は、関連度が１００％のヒットが少なくとも１つ見つかった場合には関連度が１００％未満のヒット結果を完全に排除するように設定または調整することができる。他の場合、包含フィルタ３２８は、長い結果リストを切り捨て、その結果の一部が１００％の関連度を有しても一定数の上位の結果だけを表示するように設定または調整することができる。さらに別の場合、包含フィルタ３２８は、一定のパーセンタイルより上に割り当てられたランクを有するヒット結果の表示だけを許可することができる。したがって、検索が「Ｗｈｅｒｅ  ｔｈｅ  Ｒｅｄ  Ｆｅｒｎ  Ｇｒｏｗｓ」に対するものであり、唯一のヒットが関連度ランクがわずか１５％の「Ｔｈｅ  Ｒｅｄ  Ｓｋｅｌｔｏｎ  Ｈｏｕｒ」である場合、包含フィルタ３２８は、「一致する結果は見つからない」と表示する。
【００６４】
包含フィルタ３２８は、結果の数を定義された値に制限するか、かつ／またはペアレンタルコントロールおよび／または検索を行うユーザに応じて結果を制限することも可能である。録画のコンテクストでは、包含フィルタ３２８は、今後放映がない結果を除くことができる。
【００６５】
表示アップデータ３３０は結果コンパイラ３２０に含まれ、ヒットリスト２２２をユーザに提示する表示３３２を制御する。検索結果のヒットリスト２２２を提示するには多くの可能な方式がある。ヒットは、アルファベット順または日付（時間）順に表示することができる。結果は、関連度によってグループ化し、ランク付けすることもできる。一部の実施形態では、表示アップデータ３３０は、結果の情報センター（ｃｌｅａｒｉｎｇｈｏｕｓｅ）であり、すなわち表示内容の記録を保持することができる。ヒット結果をばらばらに受け取る場合は、表示アップデータ３３０は、古い結果に新しい結果を組み合わせ、どの結果を表示するかを決定する統合機能を行うことができる。個別に行われる検索の際には、表示アップデータ３３０は、表示を区分して検索結果のグループを受け取る順序を表示するか、かつ／または表示を区分してどのヒットがどの検索語に関連するかを示すことができる。漸進的検索の際（下記でより詳しく説明する）には、表示アップデータ３３０は、ユーザが新しい数字を検索文字列２０２に追加する（例えばタイプおよび／または入力する）たびに、表示された結果のすべてまたは大半を破棄することができる。したがって、漸進的検索では、表示アップデータ３３０は、入力されている検索文字列２０２の意味が展開するのに従って検索結果を始めから再構成する。
【００６６】
無論、一部の実施形態では、結果コンパイラ３２０の各種のモジュールはともに組み合わせても、異なる順序としてもよい。変形形態では、モジュールの一部を排除しても、他の従来のデータベースモジュールを追加してもよい。
【００６７】
例示的検索エンジン２０４の変形形態を、実装で使用する利用可能なハードウェアおよび／またはソフトウェア環境の速度と処理能力に合うように適合させることができる。検索の実行には、ユーザが許容できる以上の時間がかかる可能性がある。検索エンジン２０４は、検索を実行しながら、ヒットが見つかると非同期にヒットを返すことができる。あるいは、例示的検索エンジン２０４は、インテリジェントに検索を部分に分割し、検索が完了するまで結果のセットを周期的に更新することができる。例えば、ステミングと正規化の機能を適用する前に正確な単語の一致のテキスト検索を行い（そして結果を返し）、後のパスで返すことができる。検索は時間を区分して行うこともでき、予定される放送時間に従って分割したグループごとに番組を検索する。
【００６８】
別のオプションでは、例示的検索エンジン２０４が追加的なデータストアを利用できる場合は、検索ドメインを拡大することができる。検索エンジン２０４は、各データストアにわたって検索を実行し、結果セットを最終的に確定する前に結果を併合することができる。これを使用して、例えば、ローカルのＥＰＧデータベース３００の検索にウェブベースのＥＰＧリソース３３４の検索を組み合わせることができる。また、ローカルの媒体に事前に記録された番組を検索ドメインに追加することもできる。そのような検索は、複数のＡＰＩを通じて実行し、表示する前に併合することができる。
【００６９】
例示的検索エンジン２０４は、後の実行および／またはバックグラウンドでの実行のために検索基準を持続することもできる。ユーザは、検索文字列２０２を再入力せずに呼び戻すことが可能な検索を作成することに関心を持つ可能性がある。ユーザがすでに閲覧したヒットを追跡し、一部の実施形態では、容易に目を通すことができるように結果の一部を隠す、分離する、あるいは「グレーアウト（選択不可能）」することも有用である。ＥＰＧデータベース３００の情報が更新されるたびに永続的な検索を実行し、ユーザが興味を持つ予定されるイベントをユーザに知らせることができる。
【００７０】
検索基準は例えばマクロ中にシリアライズし、自動的な記録、すなわち検索の履歴リストを定義するためのシリアライズ機構として機能することができる。検索語の各シリアライゼーションにトークンを割り当てて、ユーザがトークンを選択することによりシリアライゼーションを選択できるようにすることもできる。シリアライズした検索は、電子メール、ウェブリンクを介して他のユーザと交換するか、かつ／または「クリックして記録する」リンクのためにＴＶ放送中に埋め込むことができる。例示的検索エンジン２０４は、１つまたは複数のシリアライゼーションフォーマットを定義することもできる。検索および／またはシリアライゼーションは、コンパクトに格納するためにバイナリ形態で格納するか、電子メールで容易に送信できるようにＡＳＣＩＩ形態で表すことができる。シリアライゼーションは、単独で、または自動的な記録と連動して使用することができ、ここで、ユーザは検索を定義し、その検索基準に一致する今後のすべての番組（重複するインスタンスを除く）を記録するように指示することができる。
【００７１】
例示的な検索
図４に、本主旨による例示的な検索４００を示し、これは、例示的検索エンジン２０４などの検索エンジンによって行うことができる。「ｄｏＬＢｙ  ＷＥＳＴ−ｒａｔｅｄ‘ｇ’」などの比較的不明瞭な検索文字列２０２をユーザから、または例示的検索エンジン２０４を介して永続的なストレージから受け取る。この検索文字列２０２は、単一の簡潔なクエリに限定できない可能性がある。しかし、例示的検索エンジン２０４は、複数の検索を実行して可能性のあるヒットを見つける高い多機能性を持つ。例示的ノーマライザ３０２は、この文字列を、標準化した例示的な形態、すなわち正規化した検索文字列４０２「ＤＯＬＢＹ  ＷＥＳＴ  ＲＡＴＥＤ  Ｇ」に変形する。この場合、ノーマライザ３０２は、「ｄｏＬＢｙ」中の一部の文字の大文字／小文字を変えて、例えばＥＰＧデータベース３００で検索するテキストの大文字／小文字の使用に一致するテキスト検索語を実現している。ノーマライザ３０２は、単語間のスペースと「ＷＥＳＴ」と「ｒａｔｅｄ」の間のダッシュを境界として使用して検索語を分離する。ノーマライザ３０２は、「ｇ」から引用符を除去し、検索語の文字列全体を１種類の文字、すなわち大文字にしている。
【００７２】
正規化した検索文字列４０２を例示的な文字列インタープリタ２１４に渡し、インタープリタ２１４は、検索文字列２０２を作成した際のユーザの意図のかなり確定的な解釈に達することができる。かなり確定的な解釈は、ユーザが入力した属性検索語が、例えば属性リスト３１０を利用してテキスト検索語から明確に区別できる場合に到達することができる。文字列インタープリタ２１４は、テキストの語と属性の語との確定的な分離に達することができない場合があるが、その場合、文字列インタープリタ２１４は、代替の検索および／または条件付きの検索を行うために検索語をクエリジェネレータ３１４に渡すことができる。すなわち、ある語についてあいまい性がある場合、その語をテキスト検索に使用し、また属性検索にも使用して、例えばそれぞれのタイプの検索でいくつのヒットが得られるかを調べることができる。したがって、検索語「ＤＯＬＢＹ」は、「Ｔｈｅ  Ｄｏｌｂｙ  Ｄｉｇｉｔａｌ  Ｅｘｐｅｒｉｅｎｃｅ」などの番組名中の単語、「Ｔｈｏｍａｓ  Ｄｏｌｂｙ」など番組製作者の属性、あるいは「ＤＯＬＢＹ（登録商標）デジタル」など番組の性質的な属性である可能性がある。例示的なクエリジェネレータ３１４は、これらの可能性をそれぞれ、２つの属性検索４０６（ＤＯＬＢＹ（登録商標）デジタルとＤＯＬＢＹ（登録商標）ステレオサウンド）、代替のテキスト検索４１０（番組名中の語としての「ｄｏｌｂｙ」）、および代替の属性検索４１２（「Ｄｏｌｂｙ」という名前の出演者および関係者）としてテストすることができる。属性としての「ＤＯＬＢＹ」の関連度ランキングが非常に高いので、クエリジェネレータ３１４は、基本的なテキスト検索４０６として「ＤＯＬＢＹ」を検索しないことを決定することができる。ただし、「ＤＯＬＢＹ」がテキスト検索で見つかる場合は、代替のテキスト検索４１０で見つかる。したがって、代替の検索または条件付き検索は、より高い優先度を持つヒットが検索によって返されない場合の予備として使用するか、かつ／または、代替の検索４１０、４１２は、検索文字列２０２についてより多くの情報を得る、すなわち検索文字列２０２の解釈を強化するため、あるいは新しい検索手段を求めるための探知または修正機構として使用することができる。
【００７３】
正規化された検索文字列４０２の検索語「ＷＥＳＴ」は、番組名中の単語である可能性があり、または一部の方式では番組に関連付けられた人の属性である可能性があるので、代替の属性検索４１２でも使用することができる。ただし「ＷＥＳＴ」が文字列インタープリタ２１４による属性リスト３１０のスキャンで見つからない場合、文字列インタープリタ２１４は、「ＷＥＳＴ」は番組名検索のための主要なテキスト語であろうとの強い仮定を形成することができる。
【００７４】
文字列インタープリタ２１４は、検索語「ＲＡＴＥＤ」が検索語「Ｇ」より前にあり、そのため２つの語は「ＲＡＴＥＤ  Ｇ」と解釈される可能性が高く、それに従って検索されることを検出する。単一の語「ＲＡＴＥＤ」は代替のテキスト検索４１０で照会することができるが（すなわち番組名中に「ｒａｔｅｄ」という単語を含む番組）、そのような代替の検索は、「ＲＡＴＥＤ」と「Ｇ」がよく知られる属性の適切な順序で共に検索文字列２０２に見つかる場合には、低い関連度ランクを与えられる可能性が高い。
【００７５】
クエリジェネレータ３１４および／または検索エンジン２０４は、各種のテキスト検索４０６、属性検索４０８、代替のテキスト検索４１０、および代替の属性検索４１２を逐次行う。同時に行える検索、あるいは検索文字列２０２の長さと意味によって決まる論理的順序で行うことが可能な検索の数には制限がない。場合によっては、例示的検索エンジン２０４は、すべての検索を行い、すべての検索を通る「第１のパス」の後に関連度に従って結果をリストする。他の場合、例示的検索エンジン２０４は、文字列インタープリタ２１４またはクエリジェネレータ３１４によって設定された論理条件のツリーに従う。この論理条件は、例えば「テキスト検索４０６でＡが得られた場合は、検索語Ｘを使用して属性検索４０８および代替のテキスト検索４１０に進むが、テキスト検索４０６でＢが得られた場合は、３回の代替の属性検索４１２に進む」等である。このロジックはさらに、Ａがヒットの量であり、Ｂが特定のテキストの一致を含む特定のヒットであることを規定することができる。
【００７６】
各タイプの検索は、その特定の検索の結果を含む中間のヒットリストを返すことができる。検索語「ＷＥＳＴ」に対するテキスト検索のヒットリスト４１４は、「Ｈｏｗ  ｔｈｅ  Ｗｅｓｔ  ｗａｓ  Ｗｏｎ」、「Ｗｅｓｔ  Ｓｉｄｅ  Ｓｔｏｒｙ」、「Ｔｈｅ  Ｗｉｌｄ  Ｗｉｌｄ  Ｗｅｓｔ」、「Ｔｈｅ  Ｗｅｓｔ  Ｗｉｎｇ」などの番組名を含む可能性がある。「ＷＥＳＴ」のような比較的曖昧な単一の検索語の場合、クエリジェネレータ３１４は、恐らくは、汎用的な「ｉｎ−ｓｔｒｉｎｇ（文字列中）」演算子を使用して、単語「ＷＥＳＴ」を含む番組名を見つける。
【００７７】
属性検索のヒットリスト４１５は、「ＤＯＬＢＹ（登録商標）ステレオサウンド」、「ＤＯＬＢＹ（登録商標）デジタル」、「ｒａｔｅｄ  Ｇ」の属性を有する多数の番組名を含むか、あるいは返すことを試みる。クエリジェネレータ３１４は、これらの属性がかなり一般的であることを知っているので、一般的な属性に対する属性検索４０８を割愛し、代わりに、テキスト検索４０６の条件および／またはフィルタとしてそれらの属性を含める。すなわち、検索語「ＷＥＳＴ」を含むテキスト検索（４０６）のヒットは、そのヒットが少なくとも１つの「Ｄｏｌｂｙ」の属性および「Ｇ」の格付けにも関連付けられていない場合には許可されない。
【００７８】
「ＷＥＳＴ」のテキスト検索４０６では多数の種々のヒットが得られるので、検索エンジン２０４は、「ＤＯＬＢＹ」、「ＲＡＴＥＤ」、および「Ｇ」について代替のテキスト検索４１０を行うものと考えられ、恐らくは各検索のヒットの計数を行ってさらなる情報を収集する。恐らく、「Ｄｏｌｂｙ  Ｗｅｓｔ」という題の番組があった場合、検索エンジン２０４は、その正確な番組名の一致を鑑みて最初の解釈を変更する。すなわち、検索エンジン２０４は、当初は隣接する検索語をテキスト検索語と属性検索語との混合と推定した。
【００７９】
代替の属性検索４１２は、例えば出演者と関係者との名前を属性として使用する方式で追加的な結果を返すことができる。したがって、代替属性検索の語「ＤＯＬＢＹ」および「ＷＥＳＴ」は、Ｔｈｏｍａｓ  Ｄｏｌｂｙ  の映画、Ｓｔｅｖｅ  Ｄｏｌｂｙの映画、Ｄｏｍｉｎｉｃ  Ｗｅｓｔ  の映画、およびＳｈａｎｅ  Ｗｅｓｔの映画、の４カテゴリを返す。代替の属性検索語「Ｇ」も、格付け「Ｇ」に関連付けられた多数の番組名を返すが、それらはそのサイズのため、あるいはその検索がすでに属性検索４０８に包含されているためにフィルタリングして排除される。
【００８０】
最後に、各種検索４０６、４０８、４１０、４１２によるすべてのヒットリスト４１４、４１６、４１８、４２０を結果コンパイラ３２０で処理する。検索コンパレータ／フィルタ３２４は、受け取ったヒットと、文字列インタープリタ２１４によって確立された検索文字列２０２の解釈とを比較することができる。結果ランカー３２６は、各ヒットに関連度のランク付けを与えることができる。包含フィルタ３２８は、累積したヒット、ランク付けが低いヒット、および／またはオーバーフロー（多すぎる）ヒットと、検索文字列２０２の解釈に合わないヒットとを取り除くことができる。図のフィルタリング後のヒットリスト４２２で、文字列インタープリタ２１４がすでに検索語間のブール型関係を判定している場合、すなわち、番組名は語「ＷＥＳＴ」を含み、かつその番組はＤＯＬＢＹ（登録商標）デジタルであり、かつ格付けが「Ｇ」であるという検索文字列２０２の解釈に達している場合は、「Ｈｏｗ  ｔｈｅ  Ｗｅｓｔ  ｗａｓ  Ｗｏｎ」および比較的少ない他の番組名だけが表示されることになる。無論、例示的検索エンジン２０４が到達した解釈がユーザの意図に近くない（ユーザが有用な結果がないと判定することで明らかになる）場合、特に多くの実装ではプロセス全体がほぼ瞬時に行われるのでユーザは常に検索を修正することができる。
【００８１】
例示的な漸進的検索
図５に、本主旨による例示的な漸進的検索を示す。例示的検索エンジン２０４などの検索エンジンのモジュールを構成するのに利用できるハードウェアおよび／またはソフトウェアは強力で高い検索速度を提供できるので、例示的検索エンジン２０４の一実施形態では漸進的検索を行うことが可能である。
【００８２】
漸進的検索では、ユーザがＵＩに文字をタイプあるいは入力すると、結果を収集するのと同じ速さで検索結果を動的に更新する。各文字が入力される（または削除される）と、新たな一連の検索が開始される。非漸進的検索では、ユーザは、「Ｅｎｔｅｒ」キーを押すか、かつ／または何らかの他の方式で検索文字列２０２が完成したことを通知することによって手動で検索を開始することが必要である。
【００８３】
図５に、数週間分のＥＰＧ情報と、デジタルビデオ録画システムのローカルのハードドライブにローカルに録画した番組の集合を有するＥＰＧデータベース３００で検索をするために、検索文字列２０２「Ｔｈｅ  Ｗｅｓｔ  Ｗｉｎｇ  Ｄｏｌｂｙ  Ｅｌｅｃｔｉｏｎ」を入力する際のスナップショットを５つ示している。ブロック５０２では単語「Ｔｈｅ」が入力され、例示的検索エンジン２０４がゼロ個の結果５０４を掲示する。この理由としては、ノーマライザ３０２が「Ｔｈｅ」を冠詞と認識し、冠詞のみに基づく検索を抑制したことが考えられる。しかし、「Ｔｈｅ」の「Ｔ」が入力された時に、非常に高速のシステムであれば、例えば「Ｍｒ．Ｔ」など番組名中に「Ｔ」を単独で含む番組を返す。
【００８４】
ブロック５０６では単語「Ｔｈｅ  Ｗｅｓｔ」が入力されており、例示的検索エンジン２０４は、「Ｔｈｅ  Ｗｅｓｔ  Ｗｉｎｇ」、「Ｈｏｗ  ｔｈｅ  Ｗｅｓｔ  ｗａｓ  Ｗｏｎ」などの番組名を含む５０個の結果５０８を返す。
【００８５】
ブロック５１０では単語「Ｔｈｅ  Ｗｅｓｔ  Ｗｉｎｇ」が入力されており、ヒット数が５０から１０個の結果５１２に絞られる。恐らくはこの時点で番組名が確定し、１０個の結果は恐らくは、それぞれが各自の番組ＩＤ番号を有するテレビと映画との「Ｔｈｅ  Ｗｅｓｔ  Ｗｉｎｇ」のエピソードである。
【００８６】
ブロック５１４では単語「Ｔｈｅ  Ｗｅｓｔ  Ｗｉｎｇ  Ｄｏｌｂｙ」が入力されており、これを満たすヒットはさらに５個の結果５１６に絞られる。先の１０個のエピソードのうち、ＤＯＬＢＹ（登録商標）デジタルでない、または何らかの他のＤｏｌｂｙ属性を持つものが除外されている。
【００８７】
ブロック５１８では、単語「Ｔｈｅ  Ｗｅｓｔ  Ｗｉｎｇ  Ｄｏｌｂｙ  Ｅｌｅｃｔｉｏｎ」が入力されている。これで結果５２０は２つだけになる。この２つのヒットは、恐らくはそのエピソードの説明フィールド中の単語として「Ｄｏｌｂｙ」属性と、「Ｅｌｅｃｔｉｏｎ」属性を有する「Ｔｈｅ  Ｗｅｓｔ  Ｗｉｎｇ」のエピソードからなる。
【００８８】
検索文字列２０２が入力されるのと同時に各種のヒット結果が表示されるので、例えば、ブロック５０６で単語「Ｔｈｅ  Ｗｅｓｔ」だけが入力された時など、プロセスの初期に希望の「Ｔｈｅ  Ｗｅｓｔ  Ｗｉｎｇ」のエピソードが表示３３２に表示され、ユーザは、直ちにその希望のエピソードをハイライト表示し、選択することができるはずである。
【００８９】
例示的方法
図６に、本主旨によるフリーテキストおよび属性の検索を行う例示的方法６００を示す。この方法６００は、図２、３および５に示す例示的検索エンジン２０４などのモジュールによって行うことができる。流れ図で、動作は各ブロックに要約して記載している。この動作は、プロセッサによる実行が可能なハードウェア命令および／またはマシン可読命令（ソフトウェアまたはファームウェア）で実行することができる。
【００９０】
ブロック６０２で、検索文字列を受け取る。この文字列は、１つまたは複数のＵＩを通じてユーザから受け取るか、またはストレージから格納されたマクロあるいはシリアライズされた検索として受け取ることができる。検索文字列は、一度に一文字ずつ受け取ることもでき、新しい文字が受け取られ、長くなっていく検索文字列に追加されるたびに新しい検索のセットを漸進的に行うことができる。受け取る検索文字列は、属性がテキスト形態で書かれたテキスト文字列であると予測される。ただし、受け取った検索文字列は正規化して、非テキストの要素を標準化されたテキストまたは標準化された検索記号に変換するので、受け取る検索文字列は、ＡＳＣＩＩセットに割り当てられたアルファベット文字、記号、トークンおよび／または国際的なアルファベット文字の任意の組合せであってよい。一部の変形形態では、検索文字列は、チェックボックスへの入力、ソフトキー入力、クリックされたアイコンなども含むことができる。
【００９１】
ブロック６０４で、検索文字列を正規化する。正規化は、受け取った文字列を特定のＥＰＧ情報ソースを検索するために理解できる検索可能な語、すなわち検索するＥＰＧ情報のデータフォーマットに一致するフォーマットを有する語に変換するものである。この目的は、テキスト、大文字／小文字、および文字の形式の単なる違いをなくして、その形式の違いがなければヒットを生成するはずの検索語とＥＰＧ情報との一致を妨げないようにすることである。したがって、正規化は、検索語および恐らくは対象とするデータベース情報両方のスペルチェック、オートコレクト、語の分離、大文字／小文字の標準化、記号の正規化、冠詞の除去、句読点の除去などからなるツールキット全体を指す。例えば、「ｍａｓｈ」と「Ｍ＊Ａ＊Ｓ＊Ｈ」とは、検索語、検索対象の情報、またはその両方でどちらの形態が見つかっても常に一致する。
【００９２】
ブロック６０６で、検索文字列をテキスト語と属性語とに分離する。この分離は、検索文字列の解釈に影響し、検索文字列の解釈と同時に行われる。テキスト語と属性語とへの分離の結果、正規化によって得られる検索可能な語の何らかの解釈と、何らかの変形と置換とが行われる。平均的な検索文字列は通常は、わずか５〜６個あるいはそれ以下の検索語なので、様々な大きさのグループ化とすべての可能な順序でその検索語のすべての可能な組合せを試みる方式に従うことができる。したがって、検索文字列をスクランブルして、検索語の様々なグループ化と組合せを試すことができる。
【００９３】
各種の検索語と検索フレーズ（グループ化）との候補を生成すると、それらを既存の属性リストに照らしてテストまたは解釈して、どの検索語およびフレーズが知られている属性であるかを判定することができる。検索文字列に行われる各種の検索は、同時に行うのではなく、上述の検索文字列の解釈の際に検索の制約条件として設定される条件付きの検索ロジックに従って逐次あるいは反復的に行われることがあるので、検索語の候補は、すでにその検索文字列に行われている可能性のある検索結果があれば、それに照らしてテストすることもできる。
【００９４】
検索フレーズ中の単語を迅速にスキャンすることにより、ユーザが意図した他の詳細事項も明らかにすることができ、これは解釈の別の要素を構成する。「ｉｎ」、「ａｎｄ」、「ｉｓ」、「ｔｈｅ」など短い冠詞や接続語が多数ある場合、検索文字列は自然言語入力として解釈される。ただし、数個の簡潔な語だけを含む短い検索文字列は、ブール型の検索として解釈される可能性が高い。
【００９５】
ブロック６０８で、各テキスト語および各属性語について１回または複数回の検索を行う。存在するテキスト語と属性語、およびそれらの相互の関係に応じて、比較的複雑な検索クエリを確立することができる。ありそうもないが、説明のための例として、検索文字列「西部劇  １９８０以後  ＳＦ俳優（ｗｅｓｔｅｒｎ  ａｆｔｅｒ  １９８０  ｓｃｉ−ｆｉ  ａｃｔｏｒｓ）」は、「１９８０年より後に製作され、ＳＦ映画にも主演している俳優のみが出演する西部劇の検索」と解釈される。このような検索には、「西部劇」のカテゴリを検索し、減法のロジックを使用して１９８０年以前に製作された西部劇と、ＳＦ映画にも主演した俳優が出演していない西部劇とを除外することが伴う。多くのテキスト語および属性語の検索は、受け取る結果に応じて、同時に行うことも、逐次または繰り返し行うこともできる。したがって、例示的検索エンジン２０４など例示的方法６００を行う検索エンジンは、検索のマニホールドとして機能することができ、「同時にあらゆる方向に」行われる検索を開始する。
【００９６】
ブロック６１０で、表示のために検索結果を組み合わせる、ランク付けする、および／またはフィルタリングする。組合せは通常、属性語とテキスト語とを分離する際に仮定されるブール型の関係に従って行われる。すなわち、検索結果を組み合わせる方式は、部分的には、テキスト語と属性語とを分離する際、およびクエリを形成する際に行われる検索文字列の解釈によって事前に決定される。結果に関連度のランク付けを与える方式も、プロセスの早い段階で行われる解釈によって決まる。フィルタリングは、事前に設定されたユーザの表示の嗜好によって決まるか、または関連度のランク付けが閾値以下の結果を表示から除外する方式によって決まることができる。
【００９７】
ブロック６１２で検索結果をユーザに表示する。結果は、すべての検索が終わってから表示することができるが、受け取り、コンパイルするのと同時に表示してもよい。漸進的検索では、結果は、検索文字列が入力され、入力される各文字により新しい検索セット全体が開始されるのと同じ速度で表示される。
【００９８】
上述の例示的方法６００は、本主旨の一例に過ぎない。この方法は限定的なものではなく、ユーザが利用可能な多くの変形形態を備えるプロセスの一例を説明するものである。
【００９９】
例示的コンピューティングデバイス
図７に、本主旨の態様を実施するための環境として適した例示的コンピュータ７００を示す。例示的コンピュータ７００の構成要素には、これらに限定しないが、処理装置７２０、システムメモリ７３０、およびシステムメモリ７３０を含む各種のシステム構成要素を処理装置７２０に結合するシステムバス７２１が含まれる。システムバス７２１は、各種のバスアーキテクチャの任意のものを使用したメモリバスまたはメモリコントローラ、ペリフェラルバス、およびローカルバスを含む数タイプのバス構造のいずれでもよい。これらに限定しないが、例として、このようなアーキテクチャには、ＩＳＡ（Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＭＣＡ（Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ  ＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ）バス、およびメザニンバスとも称されるＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ）バスが含まれる。
【０１００】
例示的コンピュータ７００は通常各種のコンピュータ可読媒体を含む。コンピュータ可読媒体は、例示的コンピュータ７００がアクセスすることができる任意の利用可能媒体でよく、揮発性および不揮発性の媒体、取り外し可能および取り外し不能媒体が含まれる。これに限定しないが、例としてコンピュータ可読媒体は、コンピュータ記憶媒体と通信媒体を含むことができる。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータなどの情報を記憶するための任意の方法または技術に実装された揮発性および不揮発性の媒体、取り外し可能および取り外し不能の媒体が含まれる。コンピュータ記憶媒体には、これらに限定しないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）または他の光ディスクストレージ、磁気カセット、磁気テープ、磁気ディスクストレージまたは他の磁気記憶装置、あるいは、所望の情報の記憶に用いることができ、例示的コンピュータ７００によるアクセスが可能な任意の他の媒体が含まれる。通信媒体は、通常、搬送波または他の搬送機構などの変調データ信号にコンピュータ可読命令、データ構造、プログラムモジュール、または他のデータを実施し、任意の情報伝達媒体を含む。用語「変調データ信号」とは、信号中に情報を符号化する方式でその特性の１つまたは複数を設定または変化させた信号を意味する。例として、通信媒体には、配線ネットワークまたは直接配線接続などの配線媒体と、音響、ＲＦ、赤外線、および他の無線媒体などの無線媒体が含まれるが、これらに限定しない。上記の媒体のいずれの組合せもコンピュータ可読媒体の範囲に含めるべきである。
【０１０１】
システムメモリ７３０は、読み取り専用メモリ（ＲＯＭ）７３１およびランダムアクセスメモリ（ＲＡＭ）７３２など、揮発性および／または不揮発性メモリの形態のコンピュータ記憶媒体を含む。起動時などに例示的コンピュータ７００内の要素間の情報転送を助ける基本ルーチンを含むＢＩＯＳ（ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）７３３は、通常ＲＯＭ７３１に記憶される。ＲＡＭ７３２は通常、処理装置７２０から即座にアクセス可能な、かつ／または現在処理装置７２０によって操作中のデータおよび／またはプログラムモジュールを含む。これに限定しないが、例として、図７にはオペレーティングシステム７３４、アプリケーションプログラム７３５、例示的検索エンジン２０４、他のプログラムモジュール７３６、およびプログラムデータ７３７を示している。例示的検索エンジン２０４は、ソフトウェアとしてランダムアクセスメモリ７３２内に図示しているが、例示的検索エンジン２０４の他の実装は、ハードウェアであっても、ソフトウェアとハードウェアとの組合せであってもよい。
【０１０２】
例示的コンピュータ７００は、この他の取り外し可能／取り外し不能、揮発性／不揮発性のコンピュータ記憶媒体も含むことができる。単なる例として、図７には、取り外し不能、不揮発性の磁気媒体の読み取りまたは書き込みを行うハードディスクドライブ７４１、取り外し可能、不揮発性の磁気ディスク７５２の読み取りまたは書き込みを行う磁気ディスクドライブ７５１、およびＣＤ−ＲＯＭや他の光学媒体などの取り外し可能、不揮発性の光ディスク７５６の読み取りまたは書き込みを行う光ディスクドライブ７５５を示す。例示的動作環境で使用できるこの他の取り外し可能／取り外し不能、揮発性／不揮発性のコンピュータ記憶媒体には、これらに限定しないが、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭなどが含まれる。ハードディスクドライブ７４１は通常、インタフェース７４０などの取り外し不能のメモリインタフェースを通じてシステムバス７２１に接続され、磁気ディスクドライブ７５１および光ディスクドライブ７５５は通常、インタフェース７５０など取り外し可能なメモリインタフェースによってシステムバス７２１に接続される。
【０１０３】
上記で説明し、図７に示すドライブとそれに関連付けられたコンピュータ記憶媒体は、例示的コンピュータ７００のコンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータの記憶を提供する。例えば図７では、ハードディスクドライブ７４１にオペレーティングシステム７４４、アプリケーションプログラム７４５、他のプログラムモジュール７４６、およびプログラムデータ７４７を記憶している。これらのコンポーネントは、オペレーティングシステム７３４、アプリケーションプログラム７３５、他のプログラムモジュール７３６、およびプログラムデータ７３７と同じものでも、異なるものでもよいことに留意されたい。ここではオペレーティングシステム７４４、アプリケーションプログラム７４５、他のプログラムモジュール７４６、およびプログラムデータ７４７には、それらが少なくとも異なるコピーであることを表すために異なる参照符号をつけている。ユーザは、キーボード７６２、および一般にはマウス、トラックボール、タッチパッドと称するポインティングデバイス７６１などの入力装置を通じて例示的コンピュータ７００にコマンドと情報を入力することができる。他の入力装置（図示せず）には、マイクロフォン、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナなどがある。これらおよび他の入力装置は、システムバスに結合されたユーザ入力インタフェース７６０を通じて処理装置７２０に接続することが多いが、パラレルポート、ゲームポート、あるいはユニバーサルシリアルバス（ＵＳＢ）など他のインタフェースおよびバス構造によって接続することも可能である。モニタ７９１または他タイプの表示装置も、ビデオインタフェース７９０などのインタフェースを介してシステムバス７２１に接続される。コンピュータは、モニタに加えて、スピーカ７９７やプリンタ７９６など他の周辺出力装置も含むことができ、それらは出力周辺インタフェース７９５を通じて接続することができる。
【０１０４】
コンピュータ７００は、リモートコンピュータ７８０など１つまたは複数のリモートコンピュータとの論理接続を使用するネットワーク環境で動作することができる。リモートコンピュータ７８０はパーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、あるいはその他の一般的なネットワークノードでよく、図７にはメモリ記憶装置７８１しか示していないが、通常は例示的コンピュータ７００との関連で上記で挙げた要素の多くまたはすべてを含む。図７に示す論理接続には、ローカルエリアネットワーク（ＬＡＮ）７７１とワイドエリアネットワーク（ＷＡＮ）７７３が含まれるが、他のネットワークを含むことも可能である。このようなネットワーキング環境は、オフィス、企業内のコンピュータネットワーク、イントラネット、およびインターネットに一般的に見られる。
【０１０５】
ＬＡＮネットワーキング環境で使用する場合、例示的コンピュータ７００はネットワークインタフェースまたはアダプタ７８４を通じてＬＡＮ７７１に接続される。ＷＡＮネットワーキング環境で使用する場合、コンピュータ７００は通常、インターネットなどのＷＡＮ７７３を通じて通信を確立するためのモデム７７２またはその他の手段を含む。モデム７７２は内蔵型でも外付け型でもよく、ユーザ入力インタフェース７６０または他の適切な機構を介してシステムバス７２１に接続することができる。ネットワーク環境では、例示的コンピュータ７００との関連で図示したプログラムモジュール、またはその一部は遠隔のメモリ記憶装置に格納することができる。これに限定しないが、例として図７ではリモートアプリケーションプログラム７８５がメモリ装置７８１に常駐している。図のネットワーク接続は例示的なものであり、コンピュータ間に通信リンクを確立する他の手段を使用できることは理解されよう。
【０１０６】
言うまでもなく、本趣旨は、適切なハードウェアを有するセットトップボックス、ゲーム機、およびその他多くの種類の処置装置など多くの他の環境でも使用することができる。それらの環境はそれぞれ、例示的コンピュータ７００について上記で述べた構成要素のすべてではないが一部を含むことができる。
【０１０７】
結論
上述の本趣旨は、ハードウェア、ソフトウェア、またはハードウェアおよびソフトウェア両方に実施できることに留意されたい。一定の実施形態では、例示的システムとそれに関連する方法は、コンピュータによって実行されるプログラムモジュールなどのコンピュータ実行可能命令に概ね即して説明することができる。一般に、プログラムモジュールには、特定のタスクを行うか、または特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などが含まれる。本趣旨は、通信ネットワークを通じてリンクされた遠隔の処理装置によって無線通信を通じてタスクを行う分散通信環境でも実施することができる。無線ネットワークでは、メモリ記憶装置を含むローカルおよびリモート両方の通信デバイスの記憶媒体にプログラムモジュールを置くことができる。
【０１０８】
上述の説明では、ＥＰＧデータのフリーテキストおよび属性の検索のための例示的システムおよび方法について述べた。本発明について、構造的特徴および／または方法論的動作に固有の術語で記載したが、添付の特許請求の範囲に規定する趣旨は、必ずしもここに記載する特定の機能または動作に限定されないことを理解されたい。それら特定の機能および動作は、特許権を請求する本発明を実施する例示的形態として開示する。
【０１０９】
【表１】
2004289848.tif 000003
【０１１０】
【表２】
2004289848.tif 000004
【０１１１】
【表３】
2004289848.tif 000005
【図面の簡単な説明】
【０１１２】
【図１】従来技術によるテキスト検索および属性検索の図である。
【図２】本主旨による例示的検索の図である。
【図３】例示的検索エンジンのブロック図である。
【図４】図３の例示的検索エンジンが行う例示的検索の図である。
【図５】図３の例示的検索エンジンが行う例示的な漸進的検索の図である。
【図６】本主旨による例示的方法の流れ図である。
【図７】本主旨を実施する例示的なコンピューティングデバイス環境のブロック図である。
【符号の説明】
【０１１３】
１００  テキスト検索
１０２  属性検索
２００  検索
２０２、４０２  検索文字列
２０４  検索エンジン
２０６  テキスト検索
２０８  属性検索
２１０  条件付きテキスト検索
２１２  条件付き属性検索
２１４  文字列インタープリタ
２１６  クエリ
２２２  ヒットリスト
３００  データベース
３０１  検索文字列レシーバ
３０２  ノーマライザ
３０６  文字列トランスフォーマ
３０８  属性アイデンティファイア
３１０  属性リスト
３１１  メタデータ
３１２  検索制約条件テーブル
３１３  インデックス
３１４  クエリジェネレータ
３１６  テキストクエリフォーミュレータ
３１８  属性クエリフォーミュレータ
３１９  データマネジャ
３２０  結果コンパイラ
３２２  ヒットレシーバ
３２４  検索コンパレータ／フィルタ
３２６  結果ランカー
３２８  包含フィルタ
３３０  表示アップデータ
３３４  ＥＰＧリソース
４１０、４１２  代替の検索
７００、７８０  コンピュータ
７２０  処理装置
７２１  システムバス
７３０  システムメモリ
７３１  ＲＯＭ
７３２  ＲＡＭ
７３３  ＢＩＯＳ
７３４、７４４  オペレーティングシステム
７３５、７４５、７８５  アプリケーションプログラム
７３６、７４６  プログラムモジュール
７３７、７４７  プログラムデータ
７４１  ハードディスクドライブ
７５０  インタフェース
７５１  磁気ディスクドライブ
７５２  磁気ディスク
７５５  光ディスクドライブ
７５６  光ディスク
７６０  ユーザ入力インタフェース
７６１  ポインティングデバイス
７６２  キーボード
７７０  アダプタ
７７１  ＬＡＮ
７７２  モデム
７７３  ＷＡＮ
７９０  ビデオインタフェース
７９１  モニタ
７９６  プリンタ
７９７  スピーカ
【図１】
2004289848.tif 000006
【図２】
2004289848.tif 000007
【図３】
2004289848.tif 000008
【図４】
2004289848.tif 000009
【図５】
2004289848.tif 000010
【図６】
2004289848.tif 000011
【図７】
2004289848.tif 000012