(57)【特許請求の範囲】
【請求項１】
ＩＴＶ環境でセクションをフィルタリングする方法であって、
前記方法は、
複数レベルを含み、かつ前記複数レベルのうちいずれが有効であるかを示すフィールドを含むデータ構造を供給することと、
複数レベルの第１レベルと関連する第１基準とセクションヘッダとを比較することと、
前記セクションヘッダが前記第１基準と一致した場合に、前記複数レベルの第２レベルと関連する第２基準と前記セクションヘッダとを比較することと
を備えることを特徴とする方法。
【請求項２】
請求項１において、前記セクションヘッダが前記第１基準と一致しない場合に、第２のデータ構造に関連する第３基準と前記セクションヘッダとを比較することをさらに備えることを特徴とする方法。
【請求項３】
請求項２において、前記第３基準は、前記複数レベルの第１レベルに関連する第３レベルに関連することを特徴とする方法。
【請求項４】
請求項１において、前記セクションを受信することをさらに備えることを特徴とする方法。
【請求項５】
請求項１において、前記データ構造は、特定のセクションが受信されているか否かを示すセクションマップも含むことを特徴とする方法。
【請求項６】
請求項１において、前記データ構造は、第２データ構造へのインデックスも含むことを特徴とする方法。
【請求項７】
請求項６において、前記セクションヘッダが前記第１基準に一致しない場合に、前記インデックスが使用されることを特徴とする方法。
【請求項８】
ＩＴＶ環境でセクションをフィルタリングするシステムであって、
前記システムは、
複数レベルを含み、かつ前記複数レベルのうちいずれが有効であるかを示すフィールドを含むデータ構造を供給する手段と、
複数レベルの第１レベルと関連する第１基準とセクションヘッダとを比較する手段と、
前記セクションヘッダが前記第１基準と一致した場合に、前記複数レベルの第２レベルと関連する第２基準と前記セクションヘッダとを比較する手段と
を備えたことを特徴とするシステム。
【請求項９】
請求項８において、前記セクションヘッダが前記第１基準に一致しない場合に、第２データ構造に関連する第３基準と前記セクションヘッダとを比較することを特徴とするシステム。
【請求項１０】
請求項９において、前記第３基準は、前記複数レベルの第１レベルに関連する第３レベルに関連することを特徴とするシステム。
【請求項１１】
請求項８において、前記セクションを受信する手段をさらに備えたことを特徴とするシステム。
【請求項１２】
請求項８において、前記データ構造は、特定のセクションが受信されているか否かを示すセクションマップも含むことを特徴とするシステム。
【請求項１３】
請求項８において、前記データ構造は、第２データ構造へのインデックスも含むことを特徴とするシステム。
【請求項１４】
請求項１３において、前記セクションヘッダが前記第１基準に一致しない場合に、前記インデックスが使用されることを特徴とするシステム。
【発明の詳細な説明】
【０００１】
（発明の分野）
本発明は、情報を電子的に受信することに関する。具体的には、本発明は、セットトップボックスによって受信された情報をフィルタリングするソフトウェアに関する。
【０００２】
（発明の背景）
ＩＴＶ（interactive television）システムのようなデータ受信システムでは、ＳＩ（service information）のような情報は、ヘッドエンドから、種々のデータブロック（セクションということもある）にして、種々の移送媒体を介して送信できる。例えばデータセクションは、ヘッドエンドからケーブルまたは衛星を介して、ＴＶ（television）セットに結合されたセットトップボックスに送信できる。このようなデータセクションのコンテンツの例としては、現イベントまたは後続イベントに関する情報と、セットトップボックスのユーザがアクセスできるサービスに関する情報と、現在の時刻および日付に関する情報とが含まれている。イベントの例としては、ＴＶ番組またはコマーシャルが含まれ、他方、サービスの例としては、視聴者によりサブスクライブ（subscribe）されるチャンネルのセットがある。
【０００３】
特定のセットトップボックスは、当該特定のセットトップボックスが必要とするセクションか、新しいセクションか、または、変更があったセクションのみを確保する必要がある。例えば、視聴者が基本チャンネルセットのみをサブスクライブした場合、当該基本チャンネルセットには含まれない特別のスポーツチャンネルまたは映画チャンネルに固有のセクションは、当該セットトップボックスにとって必要でなくなる。したがって、特定のセットトップボックス基準を満たさないセクションは、すべて無視される。幾つかのセレクト（select）セクションを受け入れたり、他の全てのセクションを拒否したりすることは、ハードウェアおよびソフトウェアのフィルタリングメカニズムの組合せによって行われる。
【０００４】
ハードウェアのフィルタリングメカニズムは、典型的には、フィルタリングの第１ラウンドをパフォームし、フィルタリングメカニズムに受け入れられたセクションをソフトウェアに渡す。このソフトウェアフィルタリングメカニズムは、典型的には、当該セクションのヘッダ（通常、セクションの最初の８byteから１２byte）を解析する。新しいセクションのスタートが検出されると、典型的には、当該セクションヘッダがトランスポートストリームから獲得される。ついで、このセクションヘッダはソフトウェアフィルタプロセスに渡され、このプロセスにおいて、典型的には、セクションの残りを獲得すべきか否かが判定される。そして、セクションが必要であると判定された場合は、セクションの残りが獲得され、典型的には、さらに処理するため、フォワードされる。したがって、典型的には、ソフトウェアフィルタプロセスをパスしたセクションのみが、さらに処理するため、フォワードされる。
【０００５】
セクションは、当該セクションのヘッダ中の多くの個別のフィールドによって一意に識別することができる。例えば、セクションタイプによって、最大４つの個別のフィールドを使用して、セクションを識別することができる。特定のセクションが必要になると、当該ソフトウェアフィルタプロセスは、セクションヘッダの個別のデータフィールドの予測値をストアすることができる。セクションヘッダがソフトウェアフィルタにパスされると、これら予測値は当該セクションヘッダからの実際の値と比較される。比較した結果、一致しない場合は、一致するまでか、あるいは、比較すべき予測値がなくなるまで、予測値の次のセットが比較される。ソフトウェアフィルタは実質的に莫大な数の予測セクションヘッダ値をサーチするので、高能率比較アルゴリズムを有するのが望ましい。当該ソフトウェアフィルタが現セクションの評価を終える前に、新しいセクションが到着した場合には問題を生じる可能性があるので、高能率比較アルゴリズムが特に望ましい。このような状況に起因してオーバフローが生じるか、新しいセクションが失われる可能性がある。さらに、セットトップボックスは任意の時点で種々の異なるセクションをサーチするため、益々、効率に対するニーズが高くなる。
【０００６】
この効率に対するニーズに加えて、別の共通の要因はメモリに対するニーズである。セットトップボックスで普通に用いられる非常に限られたメモリ容量において、莫大な数の予測値が占める割合は、実質的に大きいのが典型的である。
【０００７】
メモリ空間効率データ構造（memory space efficient data structure）を使用する時間効率マッチングアルゴリズム（time efficient matching algorithm）を有するのであれば望ましい。本発明はこのようなニーズに焦点を絞っている。
【０００８】
（発明の概要）
本発明の実施形態では、情報を受信するシステム、例えば、ＴＶセットとともに用いられるセットトップボックスにおいて、情報のフィルタリングを行なうため、高速マッチングアルゴリズムはメモリ空間効率データ構造を使用する。このメモリ空間効率データ構造は、本発明の実施形態では、特定レベルのマッチング識別が見つからないときに使用される別のノードに対する関係付けられたインデックスを含んだデータフィールドの予測値の複数レベルのノードを含むことが可能である。さらに、本発明の実施形態によると、このデータ構造中のノードはそのノードで有効なレベルを識別するレベルフィールドを含むことができる。
【０００９】
さらに、本発明の実施形態によると、一連のセクションマップを利用するセクションマップを使用することができ、各セクションマップは３２bitのような所定のビット数を含む。各セクションマップは、最初の１５bitに何がストアされているかを示す単一ビットを含むことができる。例えば、セクションマップの最後の１６bitは、最初の１６セクションが受信されているかを示す。もう１つのビットは、最初の１５bitに何がストアされているのかを示すのに使用することができる。例えば、最初の１５bitは、次の１５セクションが受信されているかを示すことができるか、次のセクションマップを指し示すインデックスを示すことができる。
【００１０】
本発明の実施形態によるＩＴＶ環境で情報をフィルタリングする方法を呈示する。この方法はデータ構造の供給を含み、そのデータ構造は複数のレベルを含み、この方法は情報を第１基準と比較することを含み、第１基準は複数レベルの第１レベルに関連する。この方法は情報を第２基準とも比較し、第２基準は複数レベルの第２レベルと関連するが、この比較は情報が第１基準に一致する場合に行われる。
【００１１】
本発明の実施形態によるＩＴＶ環境で情報をフィルタリングするシステムも呈示される。このシステムはデータ構造を供給するように構成されたメモリを備え、そのデータ構造は複数のレベルを含む。システムはメモリに結合されたプロセッサも含み、このプロセッサは情報を第１基準と比較するように構成され、第１基準は複数レベルの第１レベルに関連する。プロセッサは情報を第２基準とも比較するように構成され、第２基準は複数レベルの第２レベルと関連するが、この比較は情報が第１基準に一致する場合に行われる。
【００１２】
本発明の実施形態による、情報の受信を記録する方法も呈示される。この方法はセクション番号を提供すること、第１セクションマップを供給することを含み、第１セクションマップは幾つかのビットに関係付けられる。本方法は、セクション番号がビット数未満かどうかも判定し、セクション番号がビット数未満でない場合は、第２セクションマップを指し示す。
【００１３】
本発明の実施形態による情報の受信を記録するシステムも呈示される。本システムは第１セクションマップを供給するように構成されたメモリを備え、第１セクションマップは幾つかのビットと関係付けられ、本システムはメモリに結合されたプロセッサを備える。このプロセッサはセクション番号を供給するように構成され、そのセクション番号がビット数未満かどうかを判定し、セクション番号がビット数未満でない場合は、第２セクションマップを指し示す。
【００１４】
（好ましい実施の形態の詳細な説明）
以下、当業者が本発明を作成および使用可能なように説明するとともに、特許出願およびその要件のコンテクストで説明する。この好ましい実施の形態に対する種々の変更例は、当業者に明らかにし、一般的原理は他の実施形態に応用することができる。したがって、本発明は、本実施の形態に制限されるものではなく、ここに説明する原理および特徴と矛盾しない最大範囲のものである。
【００１５】
図１は本発明の実施形態をインプリメントするのに適した情報受信システムのブロック図である。図１のシステムはヘッドエンド１０２を含んでおり、ヘッドエンド１０２は関係付けをした音声を有する特定のビデオをヘッドエンド１０２に供給するビデオオーディオ装置１００と結合可能である。ビデオ情報はヘッドエンド１０２でデジタル化され、トランスミッタ１０４を介して受信システムに送信することができる。ヘッドエンド１０２によって送信された情報は、種々の方法で、この受信システムに送信される。例えば、送信された情報は衛星１０６を介してこの受信システムに送信することができる。あるいはまた、ケーブルを使用して、情報をヘッドエンド１０２から受信システムに送信することができる。受信システムの例には、セットトップボックス１１０と結合したＴＶ１１２が含まれる。セットトップボックス１１０を受信アンテナ１０８と結合して、情報を衛星１０６から受信してもよい。
【００１６】
一度、受信アンテナ１０８を介して情報が受信されると、この情報をセットトップボックス１１０によって処理し、ＴＶセット１１２に表示することができる。このようにして、音声と、ビデオと、対話型データを受信し、セットトップボックス１１０で処理することができる。
【００１７】
図２は例えば図１に示すようなセットトップボックス１１０であって、本発明の実施の形態をインプリメントするのに適したセットトップボックスのブロック図である。図２のセットトップボックス１１０は、受信アンテナ１０８およびＴＶ１１２と結合してある。受信アンテナ１０８によって受信された信号は、フロントエンド２００に送信され、フロントエンド２００では受信アンテナ１０８により受信された変調信号を復調デジタル信号に変換する。ついで、この復調デジタル信号はフロントエンド２００からマイクロコントローラ２０２に送信される。マイクロコントローラ２０２はハードウェアフィルタ、例えば、ＰＥＳ（private elementary stream）と、ＳＩ（service information）フィルタ２０４を含むことができる。図２には単一のＰＥＳフィルタ２０４を図示したが、実際には、複数のＰＥＳフィルタのセットを使用することができる。ＰＥＳフィルタ２０４は受信信号のパケットストリームからパケットを選択することができる。一度、これらパケットがＰＥＳフィルタ２０４によって選択されると、マイクロコントローラ２０２のソフトウェアフィルタによって処理するため、これら選択されたパケットを送信することができる。ついで、このソフトウェアフィルタは、ＰＥＳフィルタ２０４から受信したパケットセットから、パケットをさらに選択する。ついで、デジタルビデオ信号およびデジタルオーディオ信号が、デジタルアナログコンバータ２１０に送信される。デジタルビデオ信号をデジタルアナログ変換することができるとともに、デジタルオーディオ信号をデジタルアナログ変換することができる。
【００１８】
マイクロコントローラ２０２はＦＬＡＳＨメモリ２０６とシステムＲＡＭ（random access memory）２０８にも結合してある。マイクロコントローラ２０２によってラン（run）されるプログラムは、ＦＬＡＳＨメモリ２０６に置くことができ、他方、データベースのような他の情報はシステムＲＡＭ２０８に置くことができる。
【００１９】
デジタルアナログコンバータ２１０は圧縮信号を圧縮解除するのに利用可能な圧縮解除のためのメモリ２１４にも結合してある。デジタルアナログコンバータ２１０は、オーディオ信号とビデオ信号をＴＶ１１２に表示するための適正なフォーマットに再変調できる再変調装置２１２にも結合してある。
【００２０】
セットトップボックス１１０によって受信されたデータは、フォーマットして種々のテーブルにするようにできる。一連のパケットが受信されると、受信されたパケットはフォーマットされ、テーブル、例えば、ＮＩＴ（nerwork information table）と、ＢＡＴ（bouquet association table）、ＳＤＴ（service descriptor table）と、ＥＩＴ（event information table）にされる。これらのテーブルはＤＶＢ（Digital Video Broadcasting）標準に記載されている。ＤＶＢ標準に関する情報については、ＵＲＬがhttp://www.atsc.orgであるインターネットサイトを参照されたい。
【００２１】
当該データストリームが受信されると、図２のＰＥＳフィルタ２０４のようなＰＥＳフィルタは、当該パケットストリームの初期フィルタ機能をパフォームする。その後、このＰＥＳフィルタによって選択されたパケットは、ソフトウェアフィルタにより処理される。マイクロコントローラ２０２は、システムに高速度で入来するパケットを処理するため、複数のＰＥＳフィルタ、例えば、１６個ないし３２個のハードウェアＰＥＳフィルタを含むことができる。入来するパケットストリームは毎秒１８Mbitないし５０Mbitで送信することができる。
【００２２】
受信システムは、ＮＩＴと、ＢＡＴと、ＳＤＴと、ＥＩＴを含む全てのタイプのテーブルを受信することができる。ＴＶネットワークは莫大なサービスを有することができる。ＮＩＴはこれらサービスがどこで見つかるかを示し、ＢＡＴはこれらサービスをカテゴリ、例えば、映画またはスポーツに分類することができ、ＳＤＴはこれらサービスについてより詳細な情報を示し、ＥＩＴは、普通、タイトルおよび言語のようなサービスに関する追加情報を示す。
【００２３】
種々のタイプのテーブルは、ソフトウェアフィルタによる処理中に、異なるレベルのフィルタリング基準を有することができる。例えば、ＮＩＴテーブルはテーブルＩＤを識別するレベル１フィルタリング基準と、ネットワークＩＤのレベル２フィルタリング基準を有することができる。当該テーブルＩＤは、セクションがフォーマットされたときにその一部となるテーブル、例えば、ＮＩＴおよびＢＡＴ等を識別した。ネットワークＩＤはネットワークを識別した。この例では、ＢＡＴテーブルは、テーブルＩＤのレベル１基準と、bouquetＩＤのレベル２基準を有することができる。bouquetはサービスの予め定めた組み合せ、例えば、サブスクライバがサブスクライブするスポーツ番組と映画番組とを組み合せたものである。bouquetＩＤは特定タイプのbouquetを識別する。この例では、ＳＤＴはテーブルＩＤのレベル１基準と、トランスポートストリームＩＤのレベル２基準と、オリジナルネットワークＩＤのレベル３基準とを有することもできる。トランスポートストリームＩＤは衛星による信号送信にどの周波数を使用しているかを識別する。オリジナルネットワークＩＤは特定のサービスを最初にブロードキャストするネットワークを識別する。ＥＩＴはテーブルＩＤのレベル１基準と、サービスＩＤのレベル２基準と、トランスポートストリームＩＤのレベル３基準と、オリジナルネットワークＩＤのレベル４基準とを有することができる。サービスＩＤは特定のトランスポートストリームＩＤからサービスを識別する。
【００２４】
セクションは多くのパケットを含む送信ユニットである。セクションに含まれるパケットの総数はテーブルごとに異なる。例えば、ＮＩＴの最大セクションは約１０２４byteである。ＮＩＴのようなテーブルは複数のセクション、例えば、２５６個のセクションに分割することができる。セクションはヘッダを含むことができる。セクションヘッダに含まれるbyte数の例は、最初の８byteから１２byteである。新しいセクションのスタートが検出されると、セクションヘッダがトランスポートスクリーンから獲得され、ソフトウェアフィルタプロセスに渡され、セクションの残りを獲得すべきかどうかを判定する。ＮＩＴと、ＢＡＴと、ＳＤＴセクションは、最大１０２４byteの長さを有することができる。ただし、ＥＩＴセクションは最大４０９６bytの長さを有することができる。
【００２５】
データパケットがハードウェアＰＥＳフィルタからソフトウェアフィルタに渡されると、このソフトウェアフィルタはさらにパケットストリームをフィルタリングする。慣用のフィルタリングプロセスの一例を図３に示す。図３はノード３００Ａ〜３００Ｐと、リーフ３０２Ａ〜３０２Ｆとを含む２進木を示す。図３に示すソフトウェアフィルタリングで２進木を使用する例では、ハードウェアＰＥＳフィルタによってソフトウェアフィルタに渡されたパケットストリームのセクションは、ルートノード３００Ａに対してチェックし、このセクションが受け入れられるセクションであるかどうかを判定する。
【００２６】
解析されたセクションがレベル１ノード３００Ａに記録されている基準に一致しない場合は、この解析されたセクションはレベル１ノード３００Ｂにストアされている基準と比較される。解析されたセクションがレベル１ノード３００Ａ〜３００Ｄのいずれかにストアされているどの基準にも一致しない場合は、このセクションは拒否される。しかし、解析されたセクションが、レベル１ノード３００Ａ〜３００Ｄのうちの１つと関係付けられた基準の１つと一致する場合は、この解析されたセクションは、解析されたセクションと一致したレベル１基準と関係付けされたレベル２の基準セットと比較される。例えば、解析されたセクションがレベル１ノード３００Ａと関係付けされた基準と一致しなかったが、レベル１ノード３００Ｂと関係付けされた基準と一致した場合は、この解析されたセクションは、一致するレベル１ノード３００Ｂと関係付けされたレベル２ノード３００Ｆ〜３００Ｈのセットと比較される。
【００２７】
解析されたセクションが、一致するレベル１ノード３００Ｂと関係付けされたレベル２ノード３００Ｆ〜３００Ｈのいずれとも一致しない場合は、この解析されたセクションは拒否される。しかし、解析されたセクションが、ノード３００Ｈのようなレベル２ノードと関係付けされた基準に一致する場合は、解析されたセクションはレベル３ノード３００Ｋ〜３００Ｎのセットと関係付けされた基準と比較される。
【００２８】
上述した例のＮＩＴおよびＢＡＴのような特定のテーブルと関係付けされた基準のレベルが２つしかない場合は、解析されたセクションはノード３００Ｈのレベル２基準と一致すれば受け入れられる。
【００２９】
この処理は、解析されたセクションが特定レベルのノードと関係付けされたどの基準とも一致せずに拒否されるか、あるいは、解析されたセクションが全てのレベルで示される全ての基準と一致した後に受け入れられるまで続行される。リーフ３０２Ａ〜３０２Ｆは２進木の特定ブランチの最終エレメントであり、解析されたセクションは、この解析されたセクションがリーフ３０２Ａ〜３０２Ｆに到達した場合に受け入れられる。例えば、解析されたセクションは、ブランチ３００Ａ〜３００Ｂと、３００Ｆ〜３００Ｈと、３００Ｋ〜３００Ｍ〜３００Ｌを通って、最終リーフ３０２Ｅまで進行することができる。
【００３０】
予め定めた数のノードとリーフは、ソフトウェアフィルタリングプロセスに適応させるため、メモリに事前割り振りされる。ノードとリーフを事前割り振りしたメモリは、例えば、所定数のノード（例えば９３０ノード）と、所定数のリーフ（例えば２５０リーフ）に対して、約２７Ｋbyteにすることができる。セットトップボックスのメモリ容量は典型的には例えば約１／２Ｍbyteないし１Ｍbyteのように小さいので、この事前割り振りされたメモリ容量はＩＴＶシステムのセットトップボックスにおいては相当量になるのが典型的である。
【００３１】
一度、データセットがソフトウェアフィルタによって受け入れられると、特定のシステム情報テーブルと関係付けされたどのセクションが適正に受信されているかを判定するのが典型的に望ましい。図４は所定のシステム情報テーブルと関係付けされた特定のセクションが受信されているかどうかを把握するための慣用の方法を示す。典型的には、３２bitの配列が、特定のシステム情報テーブルのセクションが受信されているか否かを把握するために確保されている。普通、この３２bit配列はセクションマップと呼ばれる。システム情報テーブルは例えば２５６セクションのような多数のセクションを含むことができる。セクションマップの３２byte中の各ビットは、特定のセクション番号が受信されているかどうかを示すことができる。図４に示す例では、第１のバイトはセクション番号０〜７が受信されているかどうかを示すビット１ないしビット８を含み、第２のバイトもセクション番号８ないし１５が受信されているかどうかを含む８bitを含み、以下同様であり、第３２のバイトがセクション２４８ないし２５５が受信されているかどうかを示す。
【００３２】
テーブルは２５６セクションを含むことができる。したがって、典型的には、十分なメモリ空間が確保されて２５６セクションの受信を示すことができる。しかし、典型的には、システム情報テーブルには２つまたは３つのセクションしか含まれず、セクションマップのために確保されたメモリ空間の大半は未使用であるのが典型的である。
【００３３】
この処理はソフトウェアフィルタリングのメカニズムとして効果的であるが、ソフトウェアフィルタ処理速度を落とすことなく、ソフトウェアフィルタリング処理のメモリ要件を減らすことが望ましい。さらに、必要とするメモリがより少ないビットマップシステムを得ることも望ましい。本発明はこうしたニーズを対処するものである。
【００３４】
図５は本発明の実施の形態に係るデータ構造である。図５のデータ構造４００は図５に行４０６〜４１２と列４０２〜４０４で示す複数のフィールドを含む。この例では、受信されたテーブルデータに一致するかどうかをソフトウェアフィルタがサーチできる最大４つの基準レベル有することができるものとする。列４０２では、各レベル４０６〜４１２と関係付けされたフィールドに、要求された基準がリストアップしてある。列４０４では、要求され関係付けされた基準４０２と一致した場合に使用される次に適正なノードへのインデックスがリストアップしてある。要求される基準の列４０２とインデックスの列４０４では、フィールドごとに、２byteのような所定のバイト数が確保される。
【００３５】
サブテーブルノード４００はレベルフィールド４１４も含んでいる。レベルフィールド４１４のために確保されるメモリ空間の例は１byteである。レベルフィールドは、この例では、レベル１〜４を示す値を含み、この値はどのレベルが有効なフィールドであるかを示す。例えば、レベルフィールド４１４がレベル１を示した場合、所定のセクションについて一致があるか否かについては、レベル１（行４０６）のみを照合すればよい。別の例では、レベルフィールドが３を示す場合、レベル１（行４０６）と、レベル２（行４０８）と、レベル３（行４１０）が有効であり、レベル４（行４１２）は受信したセクションとの一致があるかについては照合する必要がない。
【００３６】
エリア４１６は追加情報のために確保することができる。例えば、エリア４１６は幾つかのフィールド、例えば、７フィールドにすることができ、情報、例えば、システム情報テーブルバージョン番号と、サブテーブルノード４００がまだ有効であるかどうかを示すフラッグと、処理のために待機しているセクションがいくつあるかをカウントするカウンタと、クライアントインデックスと、サブテーブルフィルタインデックスと、タグと、セクションマップとをストアするのに使用されている。セクションマップの詳細については、後程、図９Ａ〜図１１とともに説明する。クライアントインデックスは、このサブテーブルノード４００に関係付けされたルートサブテーブルノード（解析すべき最初のサブテーブルノード）を指し示すデータベース構造とすることができる。サブテーブルフィルタインデックスは、ソフトウェアフィルタ中の他の構造へのインデックスであるが、このサブテーブルノード２進木に関係付けされていないインデックスとすることができる。このタグはクライアントによるタグであり、クライアントにより決定される種々の目的のために使用されている。
【００３７】
図６は本発明の実施の形態に係るサブテーブルノード４００Ａ〜４００Ｄのセットの例を示す。セクションは、本発明の実施の形態によるソフトウェアフィルタにより、ハードウェアＰＥＳフィルタから受信される。このセクションは最初にルートサブテーブルノード４００Ａにより解析される。ルートサブテーブルノード４００Ａは、受信されたセクションと比較される最初のサブテーブルノードである。レベル１（行４０６）の基準４０２であって、解析されたセクションに一致する基準を有する２つの適正なサブテーブルノードがある場合には、レベルフィールド４１４での最高数を有するサブテーブルノードが、レベルフィールド４１４でそれより低い数のサブテーブルノードより先に評価される。したがって、セクションに一致するレベル１の基準を持つサブテーブルノードは、最高のレベルフィールド４１４によって最低のレベルフィールド４１４まで順次評価される。
【００３８】
本発明の実施の形態では、サブテーブルノード４００のフィールドが有効である場合、同一のサブテーブルノード４００中で前のフィールドも有効であるものとする。前のフィールドは、有効なフィールドよりも低いレベル４０６〜４１２にある列４０２中のフィールドである。例えば、レベルフィールド４１４がレベル３（行４１０）を識別する場合は、レベル１（行４０６）とレベル２（行４０８）も有効であるものとする。
【００３９】
図６に示す例では、セクションがルートノード４００Ａの列４０２Ａの第１レベル４０６Ａで評価される。当該セクションと、ルートノード４００Ａの第１レベル４０６Ａと関係付けされた基準とが一致する場合、ルートノード４００Ａの列４０２Ａの第２レベル４０８Ａが一致するかどうかチェックされ、列４０２Ａの第２レベル４０８Ａで一致した場合、列４０２Ａの第３レベル４１０Ａがチェックされ、以下同様に、ルートノード４００Ａで一致するかどうか、列４０２Ａの全てのレベル４０６Ａ〜４１２Ａがチェックされる。ルートノード４００Ａのレベル４０６Ａ〜４１２Ａで一致しない場合は、次にどのサブテーブルノードをチェックするかを判定するため、ルートノード４００Ａの列４０４Ａの同レベルに位置する関係付けされたインデックスがチェックされる。例えば、ルートノード４００Ａの列４０２Ａのレベル１の４０６Ａで一致しない場合は、ルートノード４００Ａのレベル２の４０８Ａをチェックせずに、行４０６Ａ、列４０４Ａのフィールド中に位置するインデックスをチェックして、チェックすべき次のサブテーブルノードを決定する。この例では、サブテーブルノード４００Ｂが、ルートノード４００Ａのレベル１の一致する基準と関係付けされたインデックスに示されるテーブルである。テーブル４００Ｂでは、ルートノード４００Ａで一致しなかった同じレベルが一致するかどうかがチェックされる。我々の例では、ルートノード４００Ａのレベル１で一致しなかったと判定したので、次のサブテーブルノード４００Ｂのレベル１の４０６Ｂがチェックされる。ルートノード４００Ａの第１レベル４０６Ａがセクションと一致する場合は、一致するかどうかをチェックするため、ルートノード４００Ａの列４０２Ａの第２レベル４０８Ａを用いて、そのセクションがチェックされる。
【００４０】
次のテーブル４００Ｂにおいて、チェックすべき第１のレベル（前のサブテーブルノードでセクションと一致しなかったレベルに対応するレベルである）も一致しない場合は、一致しなかったレベルに対応するインデックス４０４Ｂがチェックされ、解析すべき次のサブテーブルノードが決定される。この例では、一致しなかったルートノード４００Ａの対応するレベルもレベル１の４０６Ａにあったので、サブテーブルノード４００Ｂで解析すべき最初のレベルは、列４０２Ｂのレベル１の４０６Ｂである。
【００４１】
サブテーブルノード４００Ｂの列４０２Ｂのレベル１の４０６Ｂで一致した場合、サブテーブルノード４００Ｂの次のレベル４０８Ｂが一致するかどうかチェックされる。しかし、サブテーブルノード４００Ｂの列４０２Ｂの第１レベル４０６Ｂで一致しない場合は、行４０６Ｂ、列４０４Ｂのフィールドに位置する関係付けされたインデックスがチェックされ、次のサブテーブルノード４００Ｄをチェックすることを決定する。サブテーブル４００Ｂの列４０２Ｂのレベル１の４０６Ｂで一致した場合、次のレベルであるサブテーブルノード４００Ｂのレベル２の４０８Ｂが一致するかどうかチェックされる。そのレベルで一致がない場合、行４０８Ｂ、列４０４Ｂのフィールドに位置する関係付けされたインデックスがチェックされ、次のサブテーブルノード４００Ｃをチェックすることを決定する。
【００４２】
サブテーブルノード４００Ｂのレベル２の４０８Ｂで一致が見つからなかったと仮定する。列４０４Ｂ中の関係付けされたインデックスは、次の比較がサブテーブルノード４００Ｃのレベル２の４０８Ｃに対して行われるように指図する。
【００４３】
図７および図８は本発明の実施の形態によるパケットストリームからセクションをフィルタリングする方法の流れ図である。レベルは１にセットされ、ＳＮ（subtable node）はルートに等しくセットされる（ステップ５００）。レベル（レベルＩＤ）に対応するセクション中のフィールドは、解析すべきセクションから取り出される（ステップ５０２）。レベルのＩＤの例には、基準、例えば、テーブルＩＤと、ネットワークＩＤと、bouquetＩＤと、オリジナルネットワークＩＤと、トランスポートストリームＩＤと、サービスＩＤが含まれる。レベルのＩＤはセクションヘッダに見つけることができる。
【００４４】
図１２Ａ〜図１２Ｄは種々のセクションヘッダを例を示す。図１２Ａはフィールド９０２ａ〜９０２ｄを含むＮＩＴヘッダ９００ａの例を示す。この例では、フィールド９０２ａはテーブルＩＤであり、フィールド９０２ｂはネットワークＩＤであり、フィールド９０２ｃはバージョン番号である。フィールド９０２ｄは現在のセクション番号および最後のセクション番号を含む。図１２Ｂはフィールド９０２ａ′〜９０２ｄ′を含むＢＡＴヘッダ９００ｂの例を示す。この例では、フィールド９０２ａ′はテーブルＩＤであり、フィールド９０２ｂ′はbouquetＩＤであり、フィールド９０２ｃ′はバージョン番号である。フィールド９０２ｄ′は現在のセクション番号および最後のセクション番号を含む。図１２Ｃはフィールド９０２ａ″〜９０２ｅを含むＳＴＤヘッダ９００ｃの例を示す。この例では、フィールド９０２ａはテーブルＩＤであり、フィールド９０２ｂはトランスポートストリームＩＤであり、フィールド９０２ｃ″はバージョン番号である。フィールド９０２ｄ″は現在のセクション番号および最後のセクション番号を含む。フィールド９０２ｅはオリジナルネットワークＩＤである。図１２Ｄはフィールド９０２ａ′′′〜９０２ｆを含むＥＩＴヘッダ９００ｄの例を示す。この例では、フィールド９０２ａ′′′はテーブルＩＤであり、フィールド９０２ｂ′′′はサービスＩＤであり、フィールド９０２ｃ′′′はバージョン番号である。フィールド９０２ｄ′′′は現在のセクション番号および最後のセクション番号を含む。フィールド９０２ｅ′はトランスポートストリームＩＤであり、フィールド９０２ｆはオリジナルネットワークＩＤである。
【００４５】
図１２Ａ〜図１２Ｄに示す例では、フィールド９０２ａ〜９０２ａ′′′はレベル１のＩＤであり、フィールド９０２ｂ〜９０２ｂ′′′はレベル２のＩＤであり、フィールド９０２ｅ〜９０２ｅ′はレベル３のＩＤであり、フィールド９０２ｆはレベル４のＩＤである。例えば、これらのフィールドは図７のステップ５０２で取り出すことのできるレベルＩＤを含む。有効なレベルフィールドの数がセクションタイプ（ＮＩＴ、ＢＡＴ、ＳＤＴのような）によって異なることに注意されたい。図のフィールド９０２ａ、９０２ａ′、９０２ａ″、９０２ａ′′′は、テーブルＩＤを含む。これらのフィールド９０２ａ〜９０２ａ′′′のコンテンツは、残りのレベルＩＤ９０２ｂ、９０２ｂ′、９０２ｂ″、９０２ｅ、９０２ｂ′′′、９０２ｅ′、９０２ｇのコンテンツを決定することができる。
【００４６】
レベルＩＤに加え、ヘッダ９００には他の種々の情報、例えば、バージョン番号と、現在のセクション番号と、最後のセクション番号が含まれる。セクションヘッダに含むことができるフィールドの詳細は、ＤＶＢ（Digital Video Broadcasting）標準ＥＮ３００４６８で得られる。
【００４７】
ついで、セクションから取り出されたレベルＩＤ（セクションのフィールドの取り出された値）が同レベルのサブテーブルノードの基準と一致するかどうかが判定される（図７のステップ５０４）。例えば、レベルが１にセットされ、サブテーブルノードがルートノード、例えば、図６のルートノード４００Ａにセットされ、しかも、サブテーブルノードがルートノード、例えば、図６のルートノード４００Ａにセットされ、しかも、図６のルートノード４００Ａの列４０２Ａのレベル１の４０６Ａのフィールドと関係付けされた基準が特定のテーブルＩＤである場合に、解析されているセクションのセクションヘッダに見い出されるレベル１のＩＤが、ルートノード４００Ａのレベル１で識別されるテーブルＩＤと比較され、それらが一致するかどうかを調べる。
【００４８】
当該セクションから取り出されたレベルＩＤが現在のレベルのサブテーブルノードで識別される基準と同じでない場合は、次のサブテーブルノードが決定される（ステップ５０６）。次のサブテーブルノードは図６に示すように、サブテーブルノードの現在レベルの行の列４０４中のインデックスによって決定することができる。
【００４９】
ついで、このサブテーブルノードが有効であるかどうかが判定される（ステップ５０８）。図５に示すように、サブテーブルノードが有効であるかどうかを示すフラッグは、ノード４００のエリア４１６にストアすることができる。当該サブテーブルノードが有効でない場合、現在のセクションは拒否される（ステップ５１０）。しかし、現在のサブテーブルノードが有効である場合は、再度、セクションのレベルＩＤが同レベルの現在のサブテーブルノード中の基準と同じであるかどうかが判定される（ステップ５０４）。
【００５０】
当該セクションのレベルＩＤが、同レベルのサブテーブルノードの基準と同じである（ステップ５０４）場合は、そのレベルが現在のサブテーブルノードのレベルフィールド、例えば、図５のレベルフィールド４１４よりも大きいか、あるいは等しいかを判定する（ステップ５１２）。このレベルがサブテーブルノードのレベルフィールド未満である場合は、次のレベルが検討される（ステップ５１４）（level=level+1をセットする）。ついで、この次のレベルに対応するセクション中のフィールド（次のレベルＩＤ）が取り出される（ステップ５０２）。
【００５１】
当該レベルがサブテーブルノードのレベルフィールド、例えば、図５のレベルフィールド４１４より大きいか、あるいは等しい場合は（ステップ５１２）、現在のサブテーブルノードのバージョンがセクション中のバージョンと等しいかどうかが判定される（図８のステップ５５０）。このバージョン番号は、図５に示すサブテーブルノード４００の追加フィールド４１６に位置させることができる。サブテーブルノードにストアされているこのバージョン番号は、セクションヘッダ、例えば、図１２のヘッダ９００のフィールド９０２ｅのセクションヘッダにストアされているバージョン番号と比較することができる。サブテーブルノード中のバージョン番号がセクションヘッダのバージョン番号と等しくない場合は、サブテーブルノードのバージョンが更新され、セクションマップがクリアされ、新しいセクションマップが作成される（ステップ５５２）。新しいバージョンを有するセクションが受信されると、全ての変更が受信されていることを保障するため、その新バージョンと関係付けされた全てのセクションを再度獲得すべきである。したがって、旧バージョンの受信をトラッキング（tracking）してきたセクションマップをクリアし、新しいセクションマップを作成して、新バージョンでのセクションの受信をトラッキングすることができる。セクションマップの操作の詳細については、後程、図９Ａ〜図１１と関連させて説明する。その後、当該セクションマップが獲得されると、新しいバージョンのセクションにより更新される（ステップ５５４）。ついで、このセクションが受け入れられる（ステップ５５６）。
【００５２】
当該サブテーブルノードにあるバージョンが当該セクションのバージョンと等しい場合は（ステップ５５０）、そのセクションが以前に受信されているかどうかを判定する（ステップ５５８）。あるテーブルのバージョンのポーションが紛失セクションとともに受信される可能性がある。したがって、チェックを行って、このセクションがその紛失セクションの１つであるかどうかを判定する。この判定についての詳細は、後程、図１０と関連して説明する。このセクションが以前に受信されている場合は、そのセクションは拒否される（ステップ５６０）。しかし、このセクションが以前に受信されていない場合は、このセクションが受け入れられることを示すために、このセクションマップが更新され（ステップ５５４）、このセクションが受け入れられる（ステップ５５６）。
【００５３】
図９Ａ〜図９Ｂは本発明の実施の形態によるセクションマップを示す。セクションマップは図５に示すサブテーブルノードのエリア４１６に位置させることができる。このセクションマップは、複数ビットのフィールド、例えば、最後の１６ビット（６０２）が最初の１６セクションが受信されているかどうかを示す３２ビットのフィールドを含んでいる。１６ビットエリア６０２の各ビットは、それに対応するセクションが受信されているかどうかを示すことができる。もう１つのビット（６０４）は最初の１５ビット（６０６）の機能を指定するのに使用することができる。例えば、インディケータビット６０４が１にセットされると、最初のビットセット６０６は次の１５セクションが受信されているかどうかの受信ステータスを示すことができる。しかし、インディケータビット６０４がゼロである場合、このインディケータビットは、最初のセクション６０６が次のセクションマップフィールドを指し示すインデックスとすることができることを示す。
【００５４】
図９Ｂはインディケータビットの例を示す。このインディケータビットは、インディケータビットがゼロにセットされたときのインデックスを示し、インディケータビットが１にセットされたときの次の１５セクションのステータスを示す。この例では、最初の３２ビットフィールド６００Ａが最初の１６セクションのステータスを第２ポーション６０２Ａに集めている。この例では、第２ポーション６０２Ａは１６ビットを含み、各ビットはセクションが受信されているかどうかを示す。このインディケータビットは第１ポーション６０２Ａと第２ポーション６０６Ａの間に置かれている。この例では、インディケータビット６０４Ａはゼロにセットされており１ビットである。インディケータビット６０４Ａがゼロであることは、第１ポーション６０６Ａが次のセクションマップ６００Ｂを指し示すインデックスであることを示す。次のセクションマップ６００Ｂも３２ビットのフィールドであって、第１ポーション６０６Ｂと、第２ポーション６０２Ｂとを有するとともに、第１ポーション６０６Ｂと第２ポーション６０２Ｂとの間に位置するインディケータビットを有する３２ビットのフィールドとすることができる。第２ポーション６０２Ｂは１６セクションの第２セットのステータスを記録するためのものである。この例では、インディケータビット６０４Ｂもゼロにセットされており、したがって、第２のセクションマップ６００Ｂの第１ポーション６０６Ｂも第３のセクションマップ６００Ｃを指し示すインデックスであることを示している。第３のセクションマップ６００Ｃも、１６セクションのステータスを示す第３のビットセットをストアする。しかし、インディケータビット６０４Ｃは１にセットされており、このセクションマップ６００Ｃが最後のセクションマップであり、また第１ポーション６０６Ｃが次のセクション、この例では次の１５セクションのセットのステータスを示すことを示している。
【００５５】
図１０は本発明の一実施の形態に係る方法を示す流れ図である。これは、図８のステップ５５８の判定のようなセクションが既に受信されているかどうかを判定する方法の例である。セクション番号がセクションから取り出される（ステップ７００）。図９Ｂのセクションマップ６００Ａのような第１のセクションマップを解析する（ステップ７０２）。ついで、セクション番号が、セクションマップフィールドに事前割り振りされたビット数未満かどうかを判定する（ステップ７０４）。この例では、セクション番号が３１未満であるかどうかを判定する（この例では、セクションは０から２５５まで計数されることに留意されたい）。
【００５６】
セクション番号が、セクションマップフィールドに事前割り振りされたビット数未満でない場合は、そのセクション番号を、セクションマップフィールドの第２ポーションに事前割り振りされたビット数だけデクリメントする（ステップ７０６）。この例では、セクション番号は１６だけデクリメントされる。現在のセクションマップの第１ポーションは、次のセクションマップ（次の３２ビットのセクションマップフィールド）を指し示すために使用される（ステップ７０８）。その後、このセクション番号がセクションマップフィールドのビット数より小さいかどうかを再度判定する（ステップ７０４）。
【００５７】
このセクション番号がこのセクションマップフィールドのビット数未満である場合（ステップ７０４）は、そのセクション番号が第２ポーションのビット数未満かどうかを判定する（ステップ７１６）。この例では、第２ポーションのビット数は１５である。セクション番号が第２ポーションのビット数未満でない場合は、現在のセクションマップが別のセクションマップを指し示しているかどうかを判定する（ステップ７１８）。この判定例は、インディケータビットが別のセクションマップを指し示すことを示すように、セットするための例である。このセクションマップが別のセクションマップを指し示している場合は、そのセクション番号を第２ポーションのビット数だけデクリメントする（ステップ７０６）。しかし、このセクションマップが別のセクションマップを指し示していない場合（ステップ７１８）か、セクション番号が第２ポーションのビット数未満である場合（ステップ７１６）は、現在のセクションと関係付けされたビットが、セクションが受信されていることを示すかどうかが判定される（ステップ７１０）。例えば、そのセクションが受信されていることを示すため、現在のセクションと関係付けされたビットに１を使用することができる（ステップ７１４）。この関係付けされたビットが、指し示されたセクションマップにセットされていない場合（ステップ７１０）は、そのセクションはまだ受信されていない（ステップ７１２）。
【００５８】
図１１は本発明の一実施の形態に係る方法を示す流れ図である。これは、図８のステップ５５２で行われるような新しいセクションマップを作成する例である。最後のセクション番号が現在のセクションから取り出される（ステップ８００）。各セクションはそれ自体のセクション番号と最後のセクション番号を識別し、あといくつセクションが来るかを受信システムが知るようにする。第１のセクションマップ、例えば、図９Ｂのセクションマップ６００Ａが使用される（ステップ８０２）。ついで、最後のセクション番号がセクションマップフィールドのビット数未満であるかどうかを判定する（ステップ８０４）。この例では、最後のセクション番号が３１未満であるかどうかを判定する。最後のセクション番号がセクションマップフィールドのビット数未満である場合（ステップ８０４）、インディケータビットは１にセットされ、それ以上のセクションマップがないことを示す（ステップ８０６）。この例では、インディケータビットはビット１５である。したがって、新しいセクションマップの作成は完了する。
【００５９】
最後のセクション番号がセクションマップフィールドのビット数未満でない場合（ステップ８０４）は、最後のセクション番号がセクションマップフィールドの第２ポーションのビット数だけデクリメントされる（ステップ８０８）。セクションマップフィールドの最後のセクションのビット数の例は、図９Ａの第２ポーション６０２に位置する１６ビットである。
【００６０】
そして、インディケータビットはゼロにセットされ、セクションマップがさらにあることを示す（ステップ８１０）。ついで、新しいセクションマップがシステム、例えば、ＲＡＭ（random access memory）から取り出され、現在のセクションマップにリンクされる（ステップ８１２）。ついで、新しいセクションマップは前のセクションマップの第１ポーション、例えば、図９Ａの第１ポーション６０６によって指し示されている（ステップ８１４）。ついで、最後のセクション番号がセクションマップフィールドのビット数未満かどうかが再度判定され（ステップ８０４）、以下同様に、処理が完了するまで、引き続き判定される。
【００６１】
以上、情報フィルタリングの方法およびシステムを開示した。本発明に従って書かれたソフトウェアを、メモリまたはＣＤ−ＲＯＭのような何らかのコンピュータ可読媒体にストアするか、あるいは、ネットワークを介して伝送し、プロセッサによって実行することができる。
【００６２】
本発明の実施の形態を説明したが、このような実施の形態は変形可能であり、その変形例は本発明の精神および範囲を逸脱しないものであることは、当業者にとって当然のことである。したがって、特許請求の範囲の精神および範囲を逸脱せずに、多くの変形は当業者により行うことができる。
【図面の簡単な説明】
【図１】  本発明の実施の形態をインプリメントするのに適したシステムを示すブロック図である。
【図２】  本発明の実施の形態をインプリメントするのに適したセットトップボックスの例を示すブロック図である。
【図３】  ソフトウェアフィルタに使用することのできる解析木を示す図である。
【図４】  同じくソフトウェアフィルタで使用することのできるセクションマッピングを示す図である。
【図５】  本発明の実施の形態によるソフトウェアフィルタで使用するサブテーブルノードデータ構造を示す図である。
【図６】  本発明の実施の形態によるサブテーブルノード間の関係を示す図である。
【図７】  本発明の実施の形態による情報セクションをフィルタリングする方法を示す流れ図である。
【図８】  本発明の実施の形態による情報セクションをフィルタリングする方法を示す流れ図である。
【図９Ａ】  本発明の実施の形態によるセクションマップを示す図である。
【図９Ｂ】  本発明の実施の形態によるセクションマップを示す図である。
【図１０】  本発明の実施の形態による、セクションが既に受信されているかどうかを判定する流れ図である。
【図１１】  本発明の実施の形態による新しいセクションマップを作成する流れ図である。
【図１２Ａ】  本発明の実施の形態で使用するのに適したセクションヘッダの例を示す図である。
【図１２Ｂ】  本発明の実施の形態で使用するのに適したセクションヘッダの例を示す図である。
【図１２Ｃ】  本発明の実施の形態で使用するのに適したセクションヘッダの例を示す図である。
【図１２Ｄ】  本発明の実施の形態で使用するのに適したセクションヘッダの例を示す図である。
【図１】
0004445675.tif 000002
【図２】
0004445675.tif 000003
【図３】
0004445675.tif 000004
【図４】
0004445675.tif 000005
【図５】
0004445675.tif 000006
【図６】
0004445675.tif 000007
【図７】
0004445675.tif 000008
【図８】
0004445675.tif 000009
【図９Ａ】
0004445675.tif 000010
【図９Ｂ】
0004445675.tif 000011
【図１０】
0004445675.tif 000012
【図１１】
0004445675.tif 000013
【図１２Ａ】
0004445675.tif 000014
【図１２Ｂ】
0004445675.tif 000015
【図１２Ｃ】
0004445675.tif 000016
【図１２Ｄ】
0004445675.tif 000017