JP2005524149A

JP2005524149A - コンテンツ・サーチ・エンジン

Info

Publication number: JP2005524149A
Application number: JP2004500213A
Authority: JP
Inventors: ジンテ・オー; イルサップ・キム; ホジェ・リー
Original assignee: Winnow Tech LLC
Current assignee: Winnow Tech LLC
Priority date: 2002-04-25
Filing date: 2003-04-25
Publication date: 2005-08-11
Also published as: WO2003091910A3; AU2003225183A1; AU2003225183A8; US20060050968A1; WO2003091910A2; US20030208487A1; US7464089B2; US6959297B2

Abstract

取得マトリックスが、検索語句のパターンに一致するパターンに関し、データ・ストリームの全コンテンツを検索する。上記データ・ストリームのパターンおよび検索語句の間でマッチングがある状況では、この方法およびシステムは正確なマッチング演算に進むことができる。特にポインタ・マトリックスおよび対応する制御マトリックスはルール・テーブル内の１組の語句により生成される。データは取得素子の階層により配列されて取得マトリックスになる。上記取得素子は配列データ・ストリームおよび上記ルール・テーブル内の１組の語句中の任意の検索語句の間のパターン・マッチング・チェックを実行する。明確なパターン・マッチングからの結果は好ましくは一致する取得素子から正確なマッチング検索へ送信される。

Description

本発明は一般的にコンテンツ・サーチ・エンジン、特に、取得マトリックス素子を使用したコンテンツ・サーチ・エンジンに関する。

データ・ストリーム中の語句を見つけるために、バイナリ・サーチ方法を使用するコンテンツ・サーチ・エンジンは現在知られている。さらに、そのような検索方法の使用において、上記データ・ストリームはメモリから読み出されることが知られている。そのような情報はデータベースまたは他のメモリデバイスに保存されている。また、上記データ・ストリームがインターネット（インターネット自体は分散データベース・システムの一形態と考えられる）などからコンピュータ・ネットワークを経由して通信されることが知られている。検索されるデータ・ストリームにかかわらず、そのようなバイナリ・サーチ・エンジンを使用するシステムは、上記検索語句に関して上記データ・ストリーム内の全ての可能な組み合わせを検索せねばならない。例えば、１０文字の語句（例えば“ｇｅｔｐａｓｓｗｄ”）に関するデータ・ストリームを検索するために、バイナリ・サーチ・エンジンは１．２＊１０²⁴を超える組み合わせ（２５６¹⁰の組み合わせ）を検索せねばならない。このような方法を使用すると、全体のデータ・ストリームは効率的に検索できない。多数のプロセッサが上記バイナリ・サーチ・エンジンに必要な全ての演算を計算するために並列に動作する必要があるか、または、データ・ストリームの一部のみを取得し、かつ、検索して、他の部分は正確なコンテンツを検索せずに通過させるかである。

本発明が開発されたのは上に記載した問題を考慮してである。本発明は、取得マトリックスを使用して、検索語句のパターンに一致するパターンのデータ・ストリームの全コンテンツを検索する方法およびシステムである。上記データ・ストリームの複数のパターンおよび検索語句の間に複数のマッチングがある状況では、上記方法およびシステムは正確なマッチング演算に進むことができる。特に、本発明はルール・テーブル内の１連の語句にしたがって、ポインタ・マトリックスおよび対応する制御マトリックスを生成する。データは取得マトリックスの取得素子の階層にしたがって配列され取得マトリックスにされる。上記取得素子は、上記配列データ・ストリームおよび上記ルール・テーブル内の１組の語句中の任意の検索語句の間で、パターン・マッチング・チェックを実行して、また、好ましくは文字マッチング・チェックを実行する。明確なパターン・マッチングおよび任意の対応する明確な文字マッチングからの結果は、好ましくは、マッチング取得素子から正確なマッチング検索へ送信される。

本発明の種々の実施の形態の構造および演算と同様に本発明のさらなる特徴と効果は添付した図を参照して以下に詳細に記載される。

同様な参照番号が同様な要素を示す添付の図を参照して、図１は本発明によるコンテンツ・サーチ・エンジン１０の概略図を示す。一般的に上記コンテンツ・サーチ・エンジンは入力装置１４、正確なマッチング検索１６およびルール・テーブル１８と通信する取得マトリックス１２をもつ。上記コンテンツ・サーチ・エンジンはまた上記入力装置１４および上記正確なマッチング検索１６の間にバッファ・メモリ２０を含み、また、上記入力装置１４および上記取得マトリックスの間に大文字小文字制御モジュール２２を含むことができる。以下に記載するように上記コンテンツ・サーチ・エンジン１０のシステムは、上記入力装置１４を経由して通信されるデータ・ストリーム２４に関して処理をする。

上記ルール・テーブル１８は１組の語句２６および１組のテーブル・アドレス２８を含む。上記１組の語句２６内の各語句は、上記１組のテーブル・アドレス２８により定義される位置３０で上記ルール・テーブルに格納される。例えば、語句“ｇｅｔｐａｓｓｗｄｆｉｌｅ”およびプロトコルのために使用可能な“ｈｔｔｐ”などの任意の対応するプレフィックスがテーブル・アドレス０−１８で定義される位置に格納される。連続する各語句は、任意の対応するプレフィックスとともに、その前の語句の次の位置にすぐに続く。この次の位置は次のテーブル・アドレスにより定義される。１つの例により、また以下の表を参照して、“ｇｅｔｐａｓｓｗｄｆｉｌｅ”に続く語句は、前の語句の中の最後の文字の後、すぐにアドレス１９で、始まることが可能である。上記ルール・テーブル１８の好ましい実施の形態が複数の語句と共に示されているが、１組の語句２６とは１の語句を含んでもよいことは分かる。

上記語句２６が多数の長さ３４および組み合わせ３６にある多数の文字３２をもつこともわかる。例えば、以下の表１に示されているように、“ｇｅｔｐａｓｓｗｄｆｉｌｅ”に続く１つの語句は“ｇｅｔｐｗｌｆｉｌｅｔｙｐｅ”かもしれず、プレフィックスをもっているかもしれない。この例では、両語句の最初の数文字（“ｇｅｔｐ”）は同一だが、それに続く文字は異なり、異なる文字組み合わせを表す。さらに、上記両語句の長さが異なる。語句“ｇｅｔｐａｓｓｗｄｆｉｌｅ”の長さは１５文字であり、語句“ｇｅｔｐｗｌｆｉｌｅｔｙｐｅ”の長さは１７文字である。上記ルール・テーブル１８が１つの語句をもつ場合、そのような語句は１文字の長さおよび１文字の組み合わせをもつ。
表１：ルール・テーブルの例

上記コンテンツ・サーチ・エンジン１０は、上記ルール・テーブル１８内の上記語句２６およびアドレス２８により定義されるポインタ・マトリックス３８を含む。上記ポインタ・マトリックス３８は１組の１対１ポインタ４０を含み、その１組の１対１ポインタ４０は上記ルール・テーブル１８内の上記語句２６の各々に関するテーブル・アドレス２８により特に定義される。上記ポインタ・マトリックス３８は文字長４４および文字組み合わせ４６により定義される行および列の座標４２をもつ。文字長４４および文字組み合わせは、それぞれ、文字長３４および文字組み合わせ３６により１組の語句２６に対応する。したがって、上記ルール・テーブル１８の中の各語句２６に関して、上記ポインタ・マトリックス３８は上記各語句２６の中の文字長３２および組み合わせ３４により上記行および列の座標４２で、対応するテーブル・アドレス２８を格納する。例えば、上記語句“ｇｅｔｐｗｌｆｉｌｅｔｙｐｅ”を同定するアドレス（上に記載した表１内の“７０”）は、上記ポインタ・マトリックス３８内で上記語句の対応する１対１ポインタ４０として格納される。上記アドレス（“７０”）は、各語句２６内の文字長および各語句２６内の文字組み合わせに対応する行および列４２により上記ポインタ・マトリックス３８へ格納され、またそこから読み出される。このように、上記１組の１対１ポインタ４０は上記テーブル・アドレス２８を上記ルール・テーブル１８内の各上記語句２６と相関させる。

本発明によれば、上記ポインタ・マトリックス３８内にポインタ４０を格納するために使用される文字の複数の組み合わせ４６は、上記語句２６の各々の中の文字により、上記１組の語句２６に唯一対応する１組のパターンにより一般的に定義される。以下に詳細に記載するように、上記文字組み合わせ４６を使用して定義可能な多くの種類のパターンがある。本発明の好ましい実施の形態では、上記１組のパターンは１組の圧縮された文字値であり、その圧縮された文字値は数値演算および切り捨て演算により上記各語句２６の内の文字を圧縮することにより生成される。異なる文字長をもった複数の語句２６が同じ圧縮文字値をもってもよい。なぜなら２つの語句の行および列の座標４２の少なくとも１つが、異なる文字長のために異なるからである。当然の結果、同じ文字長をもつ１対の語句２６は同じ圧縮値ももつとき、その両語句２６のうち１つの圧縮値はより少ない数の文字に基づいて計算でき、また、１組のポインタ４０が上記語句２６の各々と１対１対応をもつことを保証するため、ポインタ・アドレスは短くされた文字長にしたがって格納される。したがって、同じ文字長をもった語句２６に関しては、上記１組のパターンが、ある文字長をもつ上記語句２６の各々に関して、上記文字組み合わせに一意に対応する。上記１組の語句２６が１つの語句をもっているとすると、そのような語句に関する行および列の座標４２はその語句の文字長およびその語句の文字から生成されたパターンである。

上記取得マトリックス１２は１組の取得素子４８および対応する１組の遅延素子５０を含む。各取得素子４８は、対応する比較器５４と通信するメモリ５２をもち、一般的に各取得素子４８のためのメモリと比較器の対５６と呼ばれる。上記取得素子４８は入力装置１４と多重化通信して、また、上記１組の遅延素子５０により階層（１からＮ）をもつ。上記メモリと比較器の対５６を特に含む取得素子４８の上記階層は、好ましくは、上記１組の語句２６の上記文字長３４に１対１に対応する。特に、上記取得マトリックス１２は、各取得素子４８および入力装置１４の間に、１組の増加する遅延素子５０をもつ。上記１組の増加する遅延素子５０は、上記取得素子４８の階層における増加する順序を定義して、階層の上記の増加する順序は上記データ・ストリーム２４の増加する文字長に対応する。それ故、階層の順序が増えると、上記取得素子は、上記データ・ストリーム２４の増加する長さの文字パターンを検査できる。

動作しているとき、上記入力装置１４は、以下の表２に示されているように、ある時間間隔５８の間上記データ・ストリーム２４を受信する。上記データ・ストリーム２４は長さ６２および組み合わせ６４をもつ１組のデータ文字６０を含み、上記時間間隔５８は複数のクロック・サイクル６６からなる。上記入力装置１４は、また、バイパス６８経由で上記データ・ストリーム２４の上記バッファ・メモリ２０へ送信する。上記取得マトリックス１２は上記入力装置１４からのデータ・ストリーム２４を受信して、各取得素子４８経由で上記データ・ストリーム２４内の上記１組のデータ文字６０を配列する。上記配列された１組のデータ文字は、上記取得素子４８の上記階層により１組の配列データ７０として複数の上記メモリと比較器の対に入る。

上記取得マトリックス１２が取得素子４８経由で上記データ・ストリーム２４を配列するとき、上記メモリと比較器の対５６は、上記配列データ７０のパターン（Ｐ）と上記ルール・テーブル１８内の各語句２６に関する文字組み合わせ３６により定義される上記１組のパターンとの間でパターン・マッチング・チェックを実行する。各メモリと比較器の対５６は、上記取得素子４８の階層および上記１組の語句２６の上記文字長３４の１対１対応により上記パターン・マッチング・チェックを同時に実行する。マッチング用のメモリと比較器の対の１つによる明確なパターン・マッチングはある１対１ポインタ７２を定義し、その１対１ポインタ７２は上記ルール・テーブル１８内の１つの上記語句２６の上記アドレス２８を含む。上記１対１ポインタ７２は、一致する取得素子（ｋ）の階層および一致する取得要素（Ｐ［ｋ］）内の上記配列データ７０の上記パターン（Ｐ）により、行および列の座標７４をもつ。

上記正確なマッチング検索１６は上記バッファ・メモリ２０、取得マトリックス１２およびルール・テーブル１８と通信する。上記正確なマッチング検索１６は上記ポインタ・マトリックス３８から上記１対１ポインタを受信する。上記正確なマッチング検索１６は、上記ポインタ・マトリックス３８からの上記１対１ポインタ７２に対応する上記テーブル・アドレスにより、上記ルール・テーブル１８から１つの語句２６を読み出す。上記正確なマッチング検索１６は、一致させるメモリと比較器の対により、上記時間間隔に対応する上記バッファ・メモリ２０からの上記データ・ストリーム２４の一部で、その読み出された語句を検査する。上記ルール・テーブル１８から読み出された正確な語句および上記バッファ・メモリ２０からの上記データ・ストリーム２４の対応する部分を用いて、上記正確なマッチング検索が、それらの間の正確なマッチングをチェックする。

次に、上記取得マトリックス１２およびルール・テーブル１８の好ましい実施の形態は、図２を参照して詳しく記載される。上に説明したように、上記ルール・テーブル１８内の各上記語句２６の上記パターンは１組の圧縮文字値により定義可能である。一般的に、上記語句２６の各々は、定義された値により語句中の各文字を表し、かつ、１組の上記値について、１組の演算を実行することにより圧縮可能である。例えば、上記演算は加算、減算、積算、除算、排他的論理和、排他的論理和の否定、および、連結などの数値演算および／または論理演算である。上記１組の演算は例えば各上記語句２６内の各文字に実行される加算などの１つの数値演算である。また、上記１組の演算が複数の演算であることも可能である。本発明の好ましい実施の形態によれば、上記加算演算は上記語句２６の圧縮を例示する。例えば、以下の表２に要約されているように、語句“ｇｅｔｐａｓｓｗｄ”内の文字の１６進（０ｘ）表現は、加算されて圧縮文字値０ｘ３Ｅ２になることが可能である。
表２：圧縮文字値の例

この好ましい圧縮方法は、上記圧縮文字値および圧縮された語句の間に１対１対応がないので下記の式（１）により非可逆圧縮であることが分かる。上記語句中の文字の数が増加するにつれ、同じ圧縮文字値をもつ文字の他の組み合わせの数は指数関数的に増加する。したがって、一度上記語句が文字値の加算（または上記文字値に関する任意の他の演算）により圧縮されると、その圧縮された文字値は１対１表現として上記語句に伸長できない。上記圧縮文字値は、上記語句の１対１表現である代わりに、上記語句の確率である。例えば、１０文字の語句“ｇｅｔｐａｓｓｗｄ”の上記圧縮文字値は０ｘ３Ｅ２（すなわち、Σ“ｇｅｔｐａｓｓｗｄ”⇒０ｘ３Ｅ２）であり、１０文字の語句“ｇｏｔｐｉｓｓｅｄ”の上記圧縮文字値も０ｘ３Ｅ２（すなわち、Σ“ｇｏｔｐｉｓｓｅｄ”⇒０ｘ３Ｅ２）である。それ故、０ｘ３Ｅ２がそれ自体“ｇｅｔｐａｓｓｗｄ”の１対１表現でないことは明白である。
Σ（０ｘ語句），＠０ｘ語句中の文字⇒語句の圧縮文字値（１）

上記圧縮文字値は、さらに、以下の式（２）によりＭＳＢを削除し、かつ、合計をそのＬＳＢまで切り捨てることにより圧縮可能である。例えば、合計の０ｘ３Ｅ２内の最上位１６進ビットは削除でき、それにより、上記合計を切り捨てて、切り捨てられた圧縮文字値０ｘＥ２を生じる。したがって、上記語句“ｇｅｔｐａｓｓｗｄ”は、その語句の文字長１０およびパターン値０ｘＥ２に基づいて圧縮可能であって、配列データ・ストリーム７０とチェック可能である。上に説明したように、上記語句“ｇｅｔｐａｓｓｗｄ”のテーブル・アドレスは上記ポインタ・マトリックス３８内に上記１対１ポインタとして格納され、上記文字長１０およびパターン値０ｘＥ２に対応する行および列の座標に格納される。さらに、上記１組の１対１ポインタ４０は上記ルール・テーブル１８内の各上記語句２６の最初または最後の文字に対応しても良く、上記語句中の全ての文字が上記最初の文字のアドレスおよび上記語句の上記文字長に基づいて上記ルール・テーブル１８から読み出すことが出来る。
切り捨てられた圧縮文字値＝ＬＳＢ（圧縮文字値）（２）

上に記載したように、上記取得マトリックス１２は上記取得素子４８経由で上記データ・ストリーム２４を配列して、上記メモリと比較器の対５６は、上記配列データ７０の複数のパターン（Ｐ）および上記ルール・テーブル１８内の上記語句２６の各々により定義される上記１組のパターンの間のパターン・マッチング・チェックを実行する。したがって、上記取得マトリックス１２は、上記ルール・テーブル１８内の上記語句２６に関して実行された同じ組の演算を、上記データ・ストリーム２４に対して実行する。これは、上記取得素子４８の各々が、上記取得マトリックス１２内の各上記階層により、上記配列データ７０および上記語句２６の各々の間のパターン・マッチング・チェックを同時に実行することを可能にする。

したがって、上記好ましい実施の形態に関して、上記取得マトリックス１２は、上記入力装置および上記メモリと比較器の対５６の各々の間に位置する１組の圧縮演算器７６を含む。好ましい実施の形態では上記加算演算７８は上記１組の演算の中で実行され、上記取得素子４８の上記階層により、上記データ２４が配列される１組の遅延器５０に基づいて、現在の各文字８０を１組の過去に加算された文字８２に加える。

加えて、各加算器７８からの配列データ７０は好ましくはＬＳＢ演算器８４で切り捨てられる。次に、上記ポインタ・マトリックス内の上記１対１ポインタ４０は、上に記載したように、加算されて切り捨てられた上記配列データ７０の上記パターンが上記入力装置１４から各上記取得素子４８に送信された時、そのパターンに基づいて検査される。特に、上記比較器５４の各々は、上記取得素子４８の上記階層および対応する各メモリ５２内で、加算されて切り捨てられた上記配列データ７０の上記パターンに対応する行および列の座標で、上記ポインタ・マトリックス３８をクエリー可能である。上記ポインタ・マトリックス３８が、上記行および列の座標にポインタ７２を含む時、それに対応する比較器５４は明確なパターン・マッチングを同定して、上記コンテンツ・サーチ・エンジン１０は上記正確なマッチング検索１６に進むことが出来る。上記ルール・テーブル１８内の第１のテーブル・アドレスがゼロ値でもよいことや、上記第１のテーブル・アドレスがどの上記語句２６の最初の文字に使用される必要がないことは分かる。加えて、上記１対１ポインタ４０が、上記語句（最初の語句が上記ルール・テーブル１８内の第１のテーブル・アドレスとして始まっていても、全てゼロではない）の最後の文字を同定するために設定可能である。

上記データ・ストリーム２４内での文字の圧縮および切り捨てのため、階層にかかわらず、各トラップ素子４８の中のメモリ５２は、取得素子４８の各々上記配列データ７０のサイズになりうる。特に、好ましい実施の形態では、圧縮および切り捨てられた上記配列データ７０は１バイト（［７：０］）に格納可能であり、その１バイトは１６進形式で００からＦＦまでであり、１０進形式で０から２５５まで（２進形式で００００００００から１１１１１１１１まで）である。上記メモリ５２は、大文字小文字制御のため、およびデータ・パケット中のヘッダなどのプレフィックスのための追加のサイズのための追加の少なくとも１ビットを格納するサイズであるように、より大きくてもよい。

上に記載したように、上記ポインタ・マトリックス３８の直接検査は、いずれか１つの上記取得素子４８内の上記配列データ７０および上記ルール・テーブル１８内の上記語句２６の間のパターン・マッチング・チェックを実行するために使用可能である。加えて、本発明の好ましい実施の形態によれば、制御マトリックス８６が上記配列データ７０および上記語句２６の間でパターン・マッチング・チェックを実行するために使用可能である。上記制御マトリックス８６は上記ポインタ・マトリックス３８に非常に類似している。上記制御マトリックス８６は、上記行および列の座標４２の定義（すなわち、上記文字長４４および上記文字組み合わせ４６により定義される同じ行および列の座標系）を含み、上記ポインタ・マトリックス３８と同じ行および列の座標４２を使用する。上記制御マトリックス８６および上記ポインタ・マトリックス３８の間の違いはそれらの要素である。上に記載したように、上記ポインタ・マトリックス３８は上記ルール・テーブル１８内の上記語句２６に関する１組のアドレス２８を含む。比較すると、上記制御マトリックス８６は、１および０のビットをもつ１組の２進数などの１組のフラグ８８を含む。したがって、上記制御マトリックス８６内の上記１組のフラグ８８は、以下の式（３）により、上記ポインタ・マトリックス３８内のアドレスに対応する。一般的に、上記１組のフラグ８８は、各々の対応する行および列の座標４２で、上記ポインタ・マトリックス３８内のアドレスに対応する。それ故、好ましい実施の形態によれば、上記パターン・マッチングは第１に制御マトリックス８６内の１つのフラグ８８により同定され、次に、対応するパターンおよび長さを備えた上記語句のための上記ポインタ７２は、上記ポインタ・マトリックス３８内で同じ行および列の座標４２から上記制御マトリックス８６内のマッチング・フラグとして読み込まれる。
［ポインタ・マトリックス内のテーブル・アドレス］⇒
［制御マトリックス内のフラグ］（３）

好ましい実施の形態では、次に、明確なパターン・マッチングを同定する上記取得素子４８のいずれか１つは、上記正確なマッチング検索１６に進む前に文字マッチング・チェックを実行する。上記文字マッチング・チェックにおいて、上記データ・ストリーム２４からの１対のデータ文字９０は比較文字マトリックス９４からの２つの非圧縮語句の文字９２と比較される。上記比較文字マトリックス９４内の上記非圧縮データ文字９２は上記ルール・テーブル１８内の各語句２６からの文字のセグメントであり、語句３４の長さにより上記比較文字マトリックス９４に格納される。

上記非圧縮語句の文字は各上記語句２６の任意の対応する位置から取得可能であり、上記取得マトリックス１２はそれに応じて設計可能である。例えば、好ましい実施の形態では、上記非圧縮文字は上記語句２６の各々内の最後の２文字であり、上記取得マトリックスは、上記１対のデータ文字９０が、上記取得素子４８に入る上記データ・ストリーム２４からの最後の２文字になるように設計される。特に、上記１対のデータ文字９０は、１対の通信経路９６を経由して多重化通信される。上記１対のデータ文字９０は圧縮演算器を経由せずに、通信経路９６の前に遅延素子９８を経由して、通信経路９６の間の遅延素子１００を経由して通信される。

文字の他の組み合わせは１組の遅延素子９８、１００を変更することにより可能である。例えば、最後の文字および最後から３番目の文字は、上記通信経路９６の間の遅延素子１００に関して、２クロック・サイクルの遅延器６６、すなわち、１対の遅延素子を使用することにより、上記文字マッチング・チェックにおいて比較されるべき文字になりうる。単独の文字も上記文字マッチング・チェックに使用可能であり、３以上の文字も上記文字マッチング・チェックに使用可能である。

上記コンテンツ・サーチ・エンジン１０の一般的な記述および上に記載の上記ルール・テーブル１８の記述に基づき、上記ルール・テーブル１８内の複数の上記語句２６は、それらの長さ３２に基づき分類および格納可能である。上記ルール・テーブル１８は仮想的に１組のＮ個のルール・テーブル１０２に分割可能であり、ここで、１つの長さの全てのルールが上記１組のルール・テーブル１０２内の各ルール・テーブル１０４に格納される。

図３に詳しく示されているように、上記１組のルール・テーブル１０２内のルールの長さは、第２のルール・テーブル１０６の２文字の長さから第Ｎのルール・テーブル１０８のＮ文字の長さまで変わり、取得素子４８の数と１対１に対応する。上記第Ｎのルール・テーブルは好ましくは２４文字の長さ１１０をもつ語句を含む。上記ルール・テーブル１８内に２４文字よりかなり長い語句が存在してもよく、また、上記２４文字の長さを使用して生成されたパターンに基づいて、これらのより長い語句とのパターン・マッチングを使用可能である。例えば、上記コンテンツ・サーチ・エンジン１０が侵入検知システムに組み込まれると、語句２６は、複数の侵入検知ルールに基づく、それらのルールのいくつかは１５０文字の長さを超えることが知られている。

次に、本システムの動作を、図４を参照して一般的に記載し、また、本発明の好ましい実施の形態を参照して、再度、より詳細に記載する。一般的に上記ルール・テーブル１８および対応するポインタ・マトリックス３８は準備ステップ２１０で定義されて、上記データ・ストリーム２４は、入力ステップ２２０において、上記入力装置１４を経由して通信される。ステップ２２２により、上記バッファ・メモリ２０は、好ましくは、上記取得マトリックス１２を多重化バイパスデータ・ストリーム６８でバイパスする先入れ先出し（ＦＩＦＯ）メモリである。

上記コンテンツ・サーチ・エンジン１０は、処理ステップ２３０において、上記取得マトリックス１２を経由して、上記データ・ストリーム２４を配列する。特に、上記データ・ストリーム２４は、取得素子４８の上記階層により上記１組の遅延素子５０および上記メモリ５２の各々経由で、多重化方式により通信される。処理ステップ２４０は上記ポインタ・マトリックス３８の上記行および列の座標４２を定義して、このポインタ・マトリックス３８は上記配列データ・ストリーム７０に基づいて取得素子４８の各々によりクエリーされる（２３２）。取得素子４８の各々は決定ステップ２５０によりパターン・マッチング・チェック２５２を実行する。特に、上記比較器５４の各々は、上記取得素子４８の階層により、および、対応する各メモリ５２内の上記配列データ７０のパターンにより、行および列の座標を定義することにより、上記ポインタ・マトリックス３８をクエリーできる（２３２）。一般的に、上記コンテンツ・サーチ・エンジン１０は、パターン・マッチング２５４で一致した後、上記正確なマッチング検索１６に進む。上記コンテンツ・サーチ・エンジン１０が上記正確なマッチング検索１６に進むと、マッチング取得素子は上記１対１ポインタの行および列の座標を定義する。この１対１ポインタは、上記ルール・テーブル１８内の一致の可能性のある語句のテーブル・アドレスを定義する。明確なパターン・マッチング２５４がないと、上記コンテンツ・サーチ・エンジンは処理ステップ２３０によりデータ２３４を配列し続ける。

上記コンテンツ・サーチ・エンジン１０のための上記取得マトリックス１２の好ましい実施の形態を参照して上に特に説明したように、上記比較器５４は、上記制御マトリックス８６を、上記取得素子４８の上記階層および加算され切り捨てられた配列データ７０のパターンに対応する行および列の座標でクエリーする（２３２）。加えて、好ましい実施の形態を参照して上に記載したように、上記比較器５４は、明確なパターン・マッチング２５４があるとき、文字マッチング・チェック２５６も実行する。上記パターン・マッチング・チェック２５２および文字マッチング・チェック２５６の組み合わせは、圧縮され切り捨てられた上記データ・ストリーム７０中のパターンに基づいたフォールス・ポジティブの可能性を著しく下げる。したがって、上記正確なマッチング検索１６に進むために、好ましい実施の形態は上記パターン・マッチング・チェック２５２で一致することおよび上記文字マッチング・チェック２５６で一致することの両方を必要とする。好ましい実施の形態によれば、上記パターン・マッチング・チェック２５２および文字マッチング・チェック２５６のいずれも一致しないとき、上記コンテンツ・サーチ・エンジンは処理ステップ２３０によりデータを配列し続ける（２３４）。

上に記載したように、上記ルール・テーブル１８から上記語句２６の１つは上記正確なマッチング検索を実行するために読み込まれねばならない。したがって、上に記載したように、また処理ステップ２６０により、一致の可能性のある語句２６２は、上記ルール・テーブル１８から、取得された１対１ポインタに対応するアドレスから読み込まれる。処理ステップ２７０において、上記正確なマッチング検索１６は一致の可能性のある語句２６２を、バイパスされたデータ・フロー６８と比較する。上記正確なマッチング検索１６は、上記バイパスされたデータ・フロー６８が同じ組み合わせで正確に同じ文字をもつときは、正確な一致と同定し、また、大文字と小文字を識別する場合は、一致の可能性のある語句として同定する。処理ステップ２８０により、上記コンテンツ・サーチ・エンジン１０を実行するシステムは一般的に上記正確なマッチング２７２に基づいた同じポリシーで処理を進行する。

上に表２を参照して記載した文字圧縮の上記例に基づいて、圧縮されたデータ・ストリーム７０中の複数のパターンに基づいて、フォールス・ポジティブの可能性を下げるために上記パターン・マッチング・チェック２５２と組み合わせて上記文字マッチング・チェック２５６を使用する例が説明される。上に記載したように、上記ルール・テーブル１８が上記語句“ｇｅｔｐａｓｓｗｄ”を含むとき、上記語句についてのパターンは１６進文字値の合計により同等に表すことが可能である、すなわち、“ｇｅｔｐａｓｓｗｄ”⇒０ｘ３Ｅ２。上記語句“ｇｅｔｐａｓｓｗｄ”は１０文字をもつ。したがって、下記の表３を参照して、かつ、本発明の好ましい実施の形態の上に記載した説明により、第１０（１０番目）の取得素子は時間１３と時間２２の間（すなわち、取得したｇ−ｅ−ｔ− −ｐ−ａ−ｓ−ｓ−ｗ−ｄを含む）で上記データ・ストリームの明確なパターン・マッチングおよび明確な文字マッチングを同定する。以下に詳細に記載するように、第１０の取得素子は時間１と時間１０の間（Ｇ−ｏ−ｔ− −Ｐ−ｉ−ｓ−ｓ−ｅ−ｄを含む）で上記データ・ストリームの明確なパターン・マッチングも同定可能であるが、フォールス・ポジティブはこの文字マッチングにより避けられる。特に、上記語句の最後の２文字“ｗ−ｄ”の間の文字マッチングは上記データ・ストリームの最後の２文字“ｅ−ｄ”とは異なる。

第１０の取得素子の階層は１０に等しい文字長をもった語句に対応する（階層＝１０≒文字長＝１０）ので、第１０の取得素子以外のどの取得素子４８も“ｇ−ｅ−ｔ− −ｐ−ａ−ｓ−ｓ−ｗ−ｄ”を取得しない。これに対して、上記他の取得素子の上記階層は１０より長いまたは１０より短い文字長をもつ語句に対応する（階層＞１０≒文字長＞１０、階層＜１０≒文字長＜１０）。
表３：データ・ストリームの例

上の好ましい実施の形態の説明によれば、上記データ・ストリーム２４は、上記取得素子４８の上記階層により、上記取得素子４８の各々を経由して、配列される。特に、上記第１０の取得素子の上記階層は組み合わされた文字長１０に対応する。文字値が大文字小文字制御モジュール２２を使用して設定されると仮定すると、データ文字の上記“Ｇ−ｏ−ｔ− −Ｐ−ｉ−ｓ−ｓ−ｅ−ｄ”ストリームの値は、“ｇ−ｏ−ｔ− −ｐ−ｉ−ｓ−ｓ−ｅ−ｄ”データ文字のための値により、上記取得素子４８経由で配列される。したがって、時間１から時間１０では、配列データ・ストリーム中の“ｇ−ｏ−ｔ− −ｐ−ｉ−ｓ−ｓ−ｅ−ｄ”の文字値は式（１）および式（２）によりそれぞれ加算されて切り捨てられる（上記加算および上記切り捨ては上記１０文字を一般的に組み合わせる１つの例である）。上に記載したように、“ｇ−ｏ−ｔ− −ｐ−ｉ−ｓ−ｓ−ｅ−ｄ”の文字値の加算および切り捨てにより１６進値０ｘＥ２が導かれる。

上記第１０の取得素子は、制御マトリックス８６を、階層（１０）および加算され切り捨てられた配列データのパターン（Ｅ２）に対応する行および列の座標でクエリーする。上記語句“ｇｅｔｐａｓｓｗｄ”は１０文字の長さをもちその切り捨てられ圧縮された文字値はＥ２であるので、上記語句のテーブル・アドレスは対応する行および列の座標、すなわち、［１０，Ｅ２］に格納される。同様に、“ｇｏｔｐｉｓｓｅｄ”も１０文字の長さをもち、その切り捨てられ圧縮された文字値もＥ２である。しかし、上記ルール・テーブル１８は上記語句“ｇｏｔｐｉｓｓｅｄ”を含まない。したがって、第１０の取得素子の中のメモリは、“ｇ−ｏ−ｔ− −ｐ−ｉ−ｓ−ｓ−ｅ−ｄ”の切り捨てられて圧縮された文字値を取得して、そして、第１０の取得素子の中の比較器は、明確なパターン・マッチングを同定する。

上記制御マトリックス８６内の上記１組のフラグ８８は上記ポインタ・マトリックス３８内の１組のテーブル・アドレス２８に対応する。したがって、上記制御マトリックス８６および上記ポインタ・マトリックス３８は同じ行および列の座標系を使用するので、上記フラグは行および列の座標［１０，Ｅ２］に設定される。したがって、“ｇ−ｏ−ｔ− −ｐ−ｉ−ｓ−ｓ−ｅ−ｄ”のための上記文字長および上記切り捨てられて圧縮された文字値は明確なパターン・マッチングで得られた［１０，Ｅ２］である。しかし、上記語句中の最後の２文字“ｗｄ”の間の文字マッチングは上記データ・ストリーム中の最後の２文字“ｅ−ｄ”とは異なる。それ故、上記第１０の取得素子内の比較器はどの文字マッチングも同定せず、パターン・マッチングのみの使用により生じうるフォールス・ポジティブを避けられる。明確なマッチングの結果として、上記コンテンツ・サーチ・エンジン１０は単に上記正確なマッチング検索１６に進むので、当然、フォールス・ポジティブは必ずしもエラーにはならない。上記フォールス・ポジティブのマッチングに対応する上記非圧縮データ文字は上記バッファ・メモリ２０を経由して通信されるが、上記非圧縮データ文字が上記ルール・テーブル内の上記語句と同一ではないので（すなわち、“ｇ−ｏ−ｔ− −ｐ−ｉ−ｓ−ｓ−ｅ−ｄ”≠“ｇｅｔｐａｓｓｗｄ”）マッチング検索テーブルですべてのフォールス・ポジティブがそのように識別される。

上記コンテンツ・サーチ・エンジン１０内の上記取得マトリックス１２の別の実施の形態は図５に示されている。この実施の形態によれば、全体のデータ・ストリーム２４は、圧縮なしで上記取得素子４８を経由して配列可能である。上に記載したように、各メモリ５２内で組み合わされた配列データ・ストリーム７０内の複数の文字は、上記取得素子４８の上記階層に基づき、また、上記取得素子の上記階層は、上記入力装置１４および上記メモリ５２の各々の間の１組の遅延素子５０により定義される。上記メモリ５２の各々に取得される上記配列データ・ストリーム７０の文字長が上記メモリ５２のサイズに対応する。しかし、上記配列データ・ストリーム７０への圧縮がないと、上記メモリ５２のサイズは上記メモリ５２内に格納する各々の追加文字と共に指数関数的に増加する。

例えば、２バイト・メモリ・エンジンは２つの１バイト文字を取得できねばならず、３バイト・メモリ・エンジンは３つの１バイト文字を取得できねばならない。各８ビットバイトは２５６（２⁸＝２５６）文字まで定義するために使用可能である。したがって、２バイト・メモリ・エンジンが２つの連続した１バイト文字を取得するために、上記２バイト・メモリ・エンジンは（２⁸）²である８１９２バイトのメモリサイズをもつ。同様に、３バイト・メモリ・エンジンが３つの連続した１バイト文字を取得するために、上記３バイト・メモリ・エンジンは（２⁸）³である２０９７１５２バイト（約２メガバイト）のメモリサイズをもつ。上記メモリのサイズが圧縮なしでは指数関数的に増加する理由は、上記メモリ・エンジンが、上記ルール・テーブル１８内の上記１組の語句２６のための種々の組み合わせの各々により、非圧縮文字を取得できるように、上記メモリ・エンジンが上記データ・ストリーム２４中の文字の任意の可能な組み合わせに適応するためである。一般的に、最も大きいＮバイト・メモリ・エンジンは、Ｎ個の連続した１バイト文字をもつ最も長い非圧縮の配列データ・ストリーム７０を取得可能であり、上記Ｎバイト・メモリ・エンジンは概ね式（４）で定義されるメモリサイズをもつ。
メモリサイズ＝（２⁸）^N
ただしＮ＝取得された１バイト文字の数（４）

標準的なランダム・アクセス・メモリ（ＲＡＭ）の現在の技術は、メモリ・エンジンが、配列された文字および上記ルール・テーブル１８内の上記１組の語句２６のための文字の可能な組み合わせの間の並び替えの数のため、複数の１バイト文字を取得する能力をもつことのみを可能にさせている。上記配列データ７０はＣＡＭメモリ・レジスタのオペランドとして使用可能であり、上記ＣＡＭは、上記オペランドが上記１対１ポインタの１つに対応すると、上記ＣＡＭからアドレスを返すのみである。このためコンテンツ・アドレッサブル・メモリ（ＣＡＭ）における進歩に基づいて、より多くの１バイト文字が上記ＣＡＭにより効率的に取得可能である。ＲＡＭにおいては、上記配列データ７０は特定のアドレス位置に格納されねばならず、メモリの指数関数的増加となる。上記ＣＡＭにおいては、上記配列データ７０は、上記オペランドとしてメモリに供給されて、上記ＣＡＭは、１クロック・サイクルで、対応するマッチングが見つかると上記ＣＡＭ内のアドレスを返す。上記ＣＡＭの使用は、配列データ・ストリーム７０中の文字を圧縮しても、圧縮しなくても、使用可能である。上記配列データ７０を圧縮しないでも、上記ＣＡＭは上記メモリと比較器の対５６として上記取得マトリックス１２内に実装可能であり、そのような取得マトリックス１２では、上記ＣＡＭのコンテンツは上記１組の１対１ポインタを含む。

一般的に、上記取得マトリックス１２は、上記ルール・テーブル１８内の上記語句２６のための各々の文字の対応するパターンを一致する文字パターンに関して、上記文字が非圧縮か圧縮かおよび／または切り捨てられたかどうかにかかわらず、上記配列データ・ストリーム７０を同時に検索する。上に記載したように、同時検索は各上記取得素子４８内で実行される。特に、上記取得素子の各々内の上記メモリと比較器の対５６は文字組み合わせを同時に取得して（再度、上記文字が非圧縮か圧縮かおよび／または切り捨てられたかどうかにかかわらず）、上記配列データ・ストリーム７０内の文字組み合わせのパターンを上記語句２６の対応するパターンと比較する。上記メモリと比較器の対内で組み合わされ取得された上記文字の長さは、上記取得素子４８の上記階層により定義されて、取得されて組み合わされた文字に比較された上記語句２６の長さに対応する。

次に、図６および図７を参照して、上記コンテンツ・サーチ・エンジンの演算は本発明の好ましい実施の形態に関し詳細に記載する。特に、上記ルール・テーブル１８による上記ポインタ・マトリックス３８および上記制御マトリックス８６の生成は図６Ａから図６Ｂに示されている。上記パターン・マッチング・チェック並びに上記文字マッチング・チェックを含む上記取得マトリックス１２の演算および上記正確なマッチング検索１６は図７Ａから図７Ｃに示されている。

図６Ａを参照すると、上記ルール・テーブル１８の生成は、好ましくは長さおよび大文字小文字により上記ルール・テーブル１８内の上記１組の語句２６を分類することにより開始して、上に記載した１組のＮ個のルール・テーブル１０２を生成する。大文字小文字が区別されない語句は、好ましくは、小文字に設定され、大文字小文字の区別は好ましくは上記語句のＡＳＣＩＩ値のみに適用される。上に説明したように、上記１組の語句２６は少なくとも１つの語句を含むが、また、上記ルール・テーブル１８内に複数の語句が存在可能である。上記１組の語句２６に関して、第ｉ語句、第ｉ語句長、および第ｉ語句の大文字小文字の区別は各々ｔｅｒｍ［ｉ］、ｔｅｒｍ＿ｌｅｎｇｔｈ［ｉ］、およびｃａｓｅ［ｉ］に保存される。語句長の下限（ｌｏｗ＿ｔｅｒｍ）は整数値、好ましくは３などの小さい数に設定される。

上記ポインタ・マトリックス３８および上記制御マトリックス８６の生成は、変数の初期化で始まり、配列は初期化される（３０２）。特に、上記ポインタ・マトリックス３８内の１組のポインタ４０は好ましくは０に設定されて、上記制御マトリックス８６内の上記１組のフラグ８８も好ましくは０に設定される。変数“Ｎ”は取得素子の数の基準として使用されて、上に記載したように、本詳細な実施の形態は上記配列データ７０の圧縮演算および切り捨て演算の両方を使用して、最終的に１バイトパターンを生成する。したがって、マトリックスのサイズ、すなわち、行数×列数は、Ｎ×２５６に制限可能である。

上に記載したように、取得素子の数（Ｎ）は最も長い語句の最大文字長に等しいことが好ましい。しかし、上記ポインタ・マトリックス２８および上記制御マトリックス８６は、上記取得マトリックス１２が取得素子の数よりも長い文字長をもつ（ｔｅｒｍ＿ｌｅｎｇｔｈ＞Ｎ）語句２６に関する配列データ７０を取得可能であるように設定可能である（３０４）。これは、上記パターン・マッチングおよび上記文字マッチングに使用する文字の数を、最大、上記語句中の最初のＮ文字（ｃｏｓｔ＿ｅｎｄ）に制限することによりなされる（３０６）。当然、Ｎ文字以下の文字数をもつ語句にとって、それらの語句の実際の長さは、上記パターン・マッチングおよび上記文字マッチングに使用される文字の数（ｃｏｓｔ＿ｅｎｄ）を定義するためにその代わりに使用可能である。

好ましい実施の形態を参照して上に記載したように、各語句のパターンを定義することは、上記語句中の各文字に数値演算を実行して、その数値演算の結果を切り捨てることにより始まる（３１０）。好ましい実施の形態によれば、上記取得マトリックス１２は大文字小文字の区別がなく、上記語句中の任意の大文字が小文字として演算される（＋０ｘ２０）（３１２）。上記の例によれば、各語句の文字値は加算されて、１バイトのＬＳＢに切り捨てられる。（ｓｕｍ％２５６）（３１２、３１４）。

上に記載したように、上記語句の各々は等しい文字長をもち（ｃｏｓｔ＿ｅｎｄ＝ｉ）、これらの等しい長さの語句の１組のポインタは、上記文字長および切り捨て合計値により格納される。したがって、これらの等しい長さの語句にとって、本発明は、これらの等しい長さの語句の各々がその特定のパターンの異なる切り捨て合計をもつことを保証する。図６Ｂを参照すると、サブプロセスＡが、各上記等しい長さの語句が異なる切り捨て合計をもつことを保証する（３１６）。サブプロセスＡは１組の一意フラグ（ｅｎｄ＿ｓｕｍ［ｃｏｓｔ＿ｅｎｄ］［ｓｕｍ］）を使用して、ある切り捨て合計が、それをもつ語句の文字長と同じ文字長をもつ別の語句に既に使用されていないかを判断する（３１８）。上記１組の一意フラグ（ｅｎｄ＿ｓｕｍ［ｃｏｓｔ＿ｅｎｄ］［ｓｕｍ］）を含むマトリックスは、上記ポインタ・マトリックス３８と同じ行および列の座標に基づいていて、上記一意フラグは０に初期化される。語句に関して切り捨て合計が計算される時は、常に、一意フラグ・ビットが、上記語句の特定の文字長（ｃｏｓｔ＿ｅｎｄ）および切り捨て合計（ｓｕｍ％２５６）に関して、高レベルである１に設定される（３２０）。

もし同じ文字長をもつ他の語句が同じ切り捨て合計を生成しないならば、ポインタの値（ｒｅａｌ＿ｐｔｒ）は、上記文字長および上記切り捨て合計により、上記ポインタ・マトリックスの中の１組のポインタ（ｐｏｉｎｔｅｒ［ｃｏｓｔ＿ｅｎｄ］［ｓｕｍ］）に加算される（３２２）。加えて、対応する大文字小文字制御フラグ（ｃａｓｅ［ｉ］）および制御フラグ（高レベルビット）は各々上記取得マトリックス１２の大文字小文字制御マトリックス（ｃａｓｅ＿ｃｏｎｔｒｏｌ［ｃｏｓｔ＿ｅｎｄ］［ｓｕｍ］）および制御マトリックス（ａｃｔｉｖｅ［ｃｏｓｔ＿ｅｎｄ］［ｓｕｍ］）に格納される。これと比べて、もし同じ文字長をもったもう１つの語句が同じ切り捨て合計を生成するなら、上記語句中の、上記切り捨て合計を計算するために使用される文字の数は減らされ、新しい切り捨て合計が計算される（３２２）。上記切り捨て合計を計算するために使用される文字の数を減らすとき、上記文字の数が語句長の下限より長いことを保証することが好ましい。もしこの文字数削減システムが機能しないなら、上記取得マトリックス１２が増やされるべきであるということを暗示している（３２６）。例えば、Ｎ個の語句が全て同じＮ文字で始まるならば、上記取得マトリックス１２は取得素子の数だけ増加する。もう１つの例では、複数の語句の切り捨てられていない合計がそれらのＭＳＢによりかなり異なっていても、上記複数の語句の切り捨て合計は同じＬＳＢをもつこともあり得るので、この場合上記取得マトリックス１２は上記各取得素子４８の中の上記メモリ５２のサイズだけ増加する。圧縮文字値の切り捨ては任意であり、上記各取得素子の各々内のメモリのサイズは上記取得素子の上記階層および上記メモリに格納可能な対応する最大可能圧縮文字値により決定される。特に、圧縮文字値の切り捨てがない場合、上記取得素子の各階層において、上記メモリは式（５）によりサイズが決定される。
メモリサイズ＝（２⁸）＊（２^x），
ｘ≧ｌｏｇ（ｋ）／ｌｏｇ（２），ｋ＝第ｋ取得素子階層（５）

上に記載したように、上記切り捨て合計がパターン・マッチングに使用されると、フォールス・ポジティブを避けるために第２のマッチング技術を使用することが好ましい。例えば、各語句から２つの非圧縮文字が上記文字マッチングに使用される。したがって、ある１つの語句が同じ長さの他の語句と異なる切り捨て合計をもつことをサブ処理Ａが保証した後、これらの非圧縮文字は上記語句から選択可能である。図６Ｃを参照すると、サブ処理Ｂは切り捨てられ加算された語句の端から１対の文字を選択して、上記非圧縮文字を１対の文字マトリックス（ｃｏｍｐａｒｅ＿ｃｈａｒ［０，１］［ｃｏｓｔ＿ｅｎｄ］［ｓｕｍ］）に格納する（３２８）。加えて、上記パターン・マッチングおよび上記文字マッチングのために使用される上記語句の長さが上記語句中の全ての文字を必ずしも使用しなくても、上記語句全長が上記ルール・テーブル１８内に格納されて、それにしたがってポインタ値（ｒｅａｌ＿ｐｔｒ）が設定される（３３０）。特に、上記ポインタ値は、現在の語句の全文字長（ｔｅｒｍ＿ｌｅｎｇｔｈ［ｉ］）およびプロトコル比較において使用可能なヘッダ情報などのための任意の追加長（ｋバイト）を加えることにより、次の語句の開始ポインタ値へインクリメントされる。上記語句カウンタは１ずつインクリメントされて、この処理は、上記ルール・テーブルの終わりに達するまで、次の語句に関し繰り返される（３３２）。

図７Ａを参照すると、上記パターン・マッチング・チェック、上記文字マッチング・チェック、および上記正確なマッチング検索は、上記入力装置からデータを読み込み、上記１組の取得素子経由で上記データ・ストリームを配列することにより始まる。上記データ・ストリームの始めにおいて、上記取得素子４８の各々の上記メモリ５２内の切り捨て合計は０に初期化される（３５２）。例えば、もし上記データ・ストリームがヘッダおよびペイロードをもつデータ・パケットであるなら、上記ヘッダが識別されて、ペイロードの合計および切り捨てが開始可能であるとき、上記切り捨て合計を初期化可能である（３５４）。上に記載したように、加算以外の数値演算は、上記ルール・テーブル内の上記語句に関して実行される演算により使用可能である。上に記載したように、好ましい実施の形態の上記取得マトリックス１２は大文字小文字が区別されず、上記データ・ストリーム中のどの大文字も小文字として演算される（＋０ｘ２０）（３５６）。上記の例によれば、上記文字値は、取得素子の各々内で同時に加算および切り捨てされる（３５８）。上に詳細に記載したように、各上記取得素子内で上記加算のために使用される文字の数は上記取得素子の上記階層による。

上に記載したように、非圧縮文字も、上記文字マッチングのため、上記取得素子へ通信される。上記の例によれば、もし上記取得素子４８のいずれか１つでパッターン・マッチングが発生するならば、上記１対の文字マトリックスに格納されるように、最後から２番目および最後から３番目の文字（ｂｙｔｅ＿ｄｅｌａｙ［１，２］，ｃｕｒｒｅｎｔ＿ｄｅｌａｙ［１，２］）が、上記語句の対応する最後から２番目の文字および最後から３番目の文字とすぐに比較できるように元の文字および現在の文字は、ともに、２クロック・サイクル遅延される。上記元の文字は、大文字小文字の区別がある語句に関して、パターン・マッチングが発生した場合に遅延される（３６０）。上記現在の文字は、大文字小文字が区別されない語句に関してパターン・マッチングが発生した場合に遅延される。

次に、図７Ｂを参照すると、上記パターン・マッチングおよび上記文字マッチングのための処理は各上記取得素子４８内で同時に実行される。上記処理は一般的に上記取得マトリックス３６４内の第ｋ取得素子を参照して説明される。第ｋ取得素子のための比較器は、制御マトリックス内の上記フラグが、上記第ｋ取得素子の上記階層および上記第ｋ取得素子のメモリ内の切り捨て合計値に対応する行および列（ｋ，ｓｕｍ［ｋ］）で高レベルに設定されているか否かを決定することにより、上記パターン・マッチング・チェックを実行する（３６８）。マッチングは、上記配列データおよび上記語句の間の明確なパターン・マッチングを示し、また、上記比較器は上記語句の大文字小文字の区別に基づく文字マッチング・チェックへ進む。上記パターン・マッチング・チェックまたは上記文字マッチング・チェックのいずれも一致しないと、次の文字が上記取得素子経由で配列され、上記処理がもう一度開始する。上記パターン・マッチング・チェックおよび上記文字マッチング・チェックの両方で一致すると、上記取得素子はそのポインタを第ｋ正確マッチング検索３７２へ提供する（３７２）。特に、第ｋ正確マッチング検索のための上記ポインタはマッチング取得素子に対応するポインタ・マトリックスの行および列（ｋ，ｓｕｍ［ｋ］）から取得される。

次に、図７Ｃを参照すると、上記第ｋ正確マッチング検索のための上記の語句は上記ルール・テーブルから読み込まれる（３７４）。特に、上記語句は、第ｋ正確マッチング検索のための上記ポインタ（ｐｏｉｎｔｅｒ［ｋ］［ｓｕｍ［ｋ］］）と等しいアドレスから読み込まれる。大文字小文字区別の説明をすると、バッファ・メモリ経由でバイパスされた実際のコンテンツは、次に、上記ルール・テーブルからの上記語句と比較される（３７６）。もし上記コンテンツ・サーチ・エンジン１０が上記データ・ストリーム中のあるコンテンツおよび上記ルール・テーブル内の任意の語句の間で正確なマッチングを同定すると、一般的に、それを実行するシステムは上記正確なマッチングに基づいて同じポリシーで進む（３７８）。例えば、上記システムは上記正確なマッチングに基づいて他のステップを実行可能であると同様にパケットを取得可能でもある。次に、データを配列し、かつ、上記パターン・マッチング・チェック、上記文字マッチング・チェック並びに上記正確なマッチング検索を実行する処理が繰り返される（３８０）。

図８を参照すると、上記取得マトリックス１２は取得素子の複数の組で拡張可能である。例えば、１６ビットのビット幅を持つ上記データ・ストリーム２４の場合４０２、データ文字４０４は上記１組の取得素子４００を経由して交互に配列可能である。特に、ＭＳＢデータ文字４０６およびＬＳＢデータ文字４０８は、各々、取得素子４１０の第１の対を経由して配列される。上記複数の文字は、複数対の階層的取得素子４１２を経由して加算されるか、配列されて、そして、パターン・マッチングが上記階層的取得素子４１２のいずれか１つ内で決定可能である。例えば、”ｇ−ｅ−ｔ− −ｐ−ａ−ｓ−ｓ−ｗ−ｄ”が上記データ・ストリーム２４内にあり、語句”ｇｅｔｐａｓｓｗｄ”が上記ルール・テーブル１８内にあるとき、上記データ・ストリームは第１０の階層的取得素子４１４のいずれかで取得可能である。詳細に示されているように、取得されている上記データ・ストリームはＭＳＢの”ｇ”で始まり、上記第１０の階層的取得素子４１４の中の対応する１つの取得素子で取得される。上記データ・ストリームはＬＳＢ中の”ｇ”で始まり、上記第１０の階層的取得素子４１４の中のもう１つの取得素子に取得される。上記取得マトリックス１２の拡張性は、より多くの組の取得素子をもちいて広いビット幅も可能にする。

上記コンテンツ・サーチ・エンジン１０は任意のコンテンツ・サーチ・システムに組み込み可能である。例えば、コンテンツ・サーチ・エンジン１０は、図９および図１０に示されるように、外部コンピュータ・ネットワーク４２４および内部コンピュータ・ネットワーク４２６の間の侵入検知システム４２２の中に組み込み可能である。上記侵入検知システム４２２の各応用例では、上記ルール・テーブル１８内の上記語句２６は１組のセキュリティ・ルール４２８であり、その１組のセキュリティ・ルールは、コンピュータ・ネットワーク４２６、４２８への不正アクセスを試みるなどのコンピュータ・ハッキングに使用されることが知られている語句を含む。図１０に示されている侵入検知システム４２２の応用例では、上記１組のセキュリティ・ルール４２８が、入力データ・パケット４３０および／または出力データ・パケット４３２をチェックするために使用可能であることは明白である。入力データ・パケットおよび出力データ・パケットをチェックすることにより（４２８、４３０）、上記侵入検知システム４２２は、より一般的にコンピュータ・セキュリティ・システムとして使用可能である。例えば、ハッキング語句をチェックするほかに、上記セキュリティ・ルール４２８は、上記コンピュータ・システム経由で試みることのできる他の種類のセキュリティ攻撃を検索するために定義可能である。例えば、コンピュータ・ネットワーク４２６、４２８経由で、ある企業秘密を通信する企てを示すある語句が存在しうる。さらに、上記コンテンツ・サーチ・エンジン１０は上記内部コンピュータ・ネットワーク４２６内に存在して、そのネットワーク内の複数のコンピュータ間のハッキングをチェックして、顧客リスト、販売者リスト、従業員給与、および競争相手情報などの企業秘密および／または他の大切な企業情報を含む不正通信を含む企業スパイの証拠をチェックする。

図９および図１０に示された詳細な実施の形態では、上記データ・ストリーム２４は上記コンテンツ・サーチ・エンジン１０内の少なくとも１つのトランシーバ４３４経由でコンピュータ・ネットワーク４２６、４２８の間で通信される。上記データ・ストリーム２４は、上に記載したように、上記コンテンツ・サーチ・エンジン１０経由で配列される。もし正確なマッチングが上記データ・ストリーム２４中の文字と上記セキュリティ・ルール４２８内の文字の間で見つかると、上記データ・ストリーム中のマッチングしている部分は取得され、検知制御コンピュータ４３６へ送信される。上記検知制御コンピュータ４３６はその取得されたデータ・ストリームをログに残すことが可能であり、および／または、取得された上記データ・ストリームにより所定のポリシー・ルールを実行可能である。詳細な実施の形態によれば、もう１つのトランシーバ４３８が、上記検知制御コンピュータ４３６および上記コンテンツ・サーチ・エンジン１０の間の（図９）、または、入力および出力データ・パケット４２８、４３０の両方をチェックする時、コンピュータ・ネットワーク４２６、４２８の間（図１０）の通信のために使用可能である。図１０に示されているように、上記検知制御コンピュータ４３６が、ファースト・イーサネット接続などの他の種類のインターフェイス経由でも上記コンテンツ・サーチ・エンジン１０と通信可能である。上記トランシーバは光イーサネット・インターフェイスでもよい。

上記１組のパターンが正確な文字パターンの集合、ほぼ正確な文字パターンの集合、部分文字パターンの集合、文字演算パターンの集合、切り捨てられた文字演算パターンの集合、またはこれらのパターン集合の組み合わせでもよい。正確な文字パターンの集合は同じ順序で大文字小文字の別も同じ文字の正確な組み合わせにより例示されて、また、ほぼ正確な文字パターンは、上に記載した別の実施の形態またはＣＡＭで実現可能な、同じ順序の同じ文字をもつが大文字小文字が区別されない文字組み合わせにより例示される。文字部分パターンの集合は、上に記載したような文字マッチング演算およびＣＡＭなどの、同じ順序の同じ文字をもつが、上記語句の各々の部分のみである文字組み合わせにより例示される。文字演算パターンの集合は数値演算器および／または論理演算器により演算される文字組み合わせにより例示されて、切り捨てられた文字演算パターン・セットは、上に記載した好ましい実施の形態で実現されるように、文字演算パターン・セットを切り捨てることにより例示される。

本発明によるコンテンツ・サーチ・エンジンの概略図本発明の好ましい実施の形態による取得マトリックスの好ましい実施の形態の概略図本発明で使用されるルール・テーブルの詳細図本発明によるコンテンツ・サーチ・エンジンの演算のフローチャート本発明の代わりの実施の形態の概略図ルール・テーブルによる、また、本発明の好ましい実施の形態に従ったポインタ・マトリックスおよび制御マトリックスを生成する方法の詳細フローチャートルール・テーブルによる、また、本発明の好ましい実施の形態に従ったポインタ・マトリックスおよび制御マトリックスを生成する方法の詳細フローチャートルール・テーブルによる、また、本発明の好ましい実施の形態に従ったポインタ・マトリックスおよび制御マトリックスを生成する方法の詳細フローチャート本発明の好ましい実施の形態に従ったパターン・マッチング、文字マッチング、および正確なマッチング検索の方法の詳細フローチャート本発明の好ましい実施の形態に従ったパターン・マッチング、文字マッチング、および正確なマッチング検索の方法の詳細フローチャート本発明の好ましい実施の形態に従ったパターン・マッチング、文字マッチング、および正確なマッチング検索の方法の詳細フローチャート本発明の限定された実施の形態の概略図本発明により侵入検知システムに統合されたコンテンツ・サーチ・エンジンの概略図本発明により侵入検知システムに統合されたコンテンツ・サーチ・エンジンの概略図

符号の説明

１０コンテンツ・サーチ・エンジン
１２取得マトリックス
１４入力装置
１６正確なマッチング検索
１８ルール・テーブル
２０バッファ・メモリ
２２大文字小文字制御モジュール
２４データ・ストリーム
２６語句
２８テーブル・アドレス
３０テーブル・アドレス（２８）により定義される位置
３２語句内の文字
３４語句内の文字長
３６文字組み合わせ
３８ポインタ・マトリックス
４０１対１ポインタ
４２行および列の座標
４４文字長
４６文字組み合わせ
４８取得素子
５０遅延素子
５２メモリ
５４比較器
５６メモリと比較器の対
５８時間間隔
６０データ文字
６２データ文字（６０）の長さ
６４データ文字（６０）組み合わせ
６６クロック・サイクル
６８バイパス
７０配列データ・ストリーム
７２１対１ポインタ
７４行および列の座標
７６圧縮演算器
７８加算演算
８０現在の文字
８２過去に加算された文字
８４ＬＳＢ演算
８６制御マトリックス
８８フラグ
９０データ文字
９２非圧縮データ文字
９４比較文字マトリックス
９６通信経路
９８遅延素子
１００遅延素子
１０２ルール・テーブル
１０４ルール・テーブル
１０６第２のルール・テーブル
１０８第Ｎのルール・テーブル
１１０２４文字の長さ
４００取得素子
４０２１６ビットのビット幅を持つデータ・ストリーム（２４）の場合
４０４１６ビットのビット幅を持つデータ文字
４０６ＭＳＢデータ文字
４０８ＬＳＢデータ文字
４１０取得素子
４１２階層的取得素子
４１４第１０の階層的取得素子
４２２侵入検知システム
４２４外部コンピュータ・ネットワーク
４２６内部コンピュータ・ネットワーク
４２８セキュリティ・ルール
４３０入力データ・パケット
４３２出力データ・パケット
４３４トランシーバ
４３６検知制御コンピュータ
４３８もう１つのトランシーバ

Claims

データ・ストリームを検索する方法であって、
（ａ）１組の語句に基づいてポインタ・マトリックスを定義するステップであって、上記語句は複数の文字長と複数の文字組み合わせとをもつ複数の語句の文字を含み、上記ポインタ・マトリックスは上記１組の語句に一意に対応する１組の１対１ポインタを含み、上記１対１ポインタは、上記ポインタ・マトリックスにおいて上記文字長により定義される行の座標と、上記文字組み合わせによって定義される１組のパターンにより定義される列の座標とに格納され、上記１組の語句は少なくとも１つの語句を含み、上記１組のパターンは、上記少なくとも１つの語句に対応する少なくとも１つのパターンを含むステップ；
（ｂ）ある時間間隔の間に入力装置でデータ・ストリームを受信するステップであって、上記データ・ストリームは、データ長およびデータ組み合わせをもつ１組のデータ文字を含み、上記時間間隔は複数のクロック・サイクルを含むステップ；
（ｃ）上記時間間隔の間、取得マトリックス経由で上記データ・ストリームを配列するステップであって、上記取得マトリックスは１組の取得素子および１組の遅延素子を含み、上記取得素子は上記入力装置と多重化通信し、上記１組の取得素子は上記１組の遅延素子により階層をもち、各々の上記取得素子と上記入力装置の間の１組の順次増加する複数の上記遅延素子は、上記取得素子の上記階層における等級の増加を定義し、上記配列データ・ストリームは上記取得素子の上記階層により１組のデータ長を含み、さらに、上記配列データ・ストリームは１組のデータ組み合わせを含み、上記１組のデータ組み合わせは上記取得素子の上記階層により上記１組のデータ長に対応するステップ；および
（ｄ）上記取得素子の上記階層により各上記取得素子で上記１組のパターンおよび上記１組のデータ組み合わせの間でパターン・マッチング・チェックを実行するステップ
を備える方法。
請求項１に記載の方法であって、上記ポインタ・マトリックスを定義する上記ステップがさらに、
（ｉ）上記１組の語句を定義するステップ；
（ii）１組のテーブル・アドレスによりルール・テーブル内に上記１組の語句を格納するステップ；および
（iii）上記１組の１対１ポインタを上記１組のテーブル・アドレスとして定義するステップ
を備える方法。
請求項２に記載の方法であって、上記パターン・マッチング・チェックを実行する上記ステップが、上記パターン・マッチング・チェックが明確なパターン・マッチングのとき、上記ポインタ・マトリックスから１つの上記テーブル・アドレスを読み込むステップをさらに備える方法。
請求項３に記載の方法であって、上記パターン・マッチング・チェックが明確なパターン・マッチングのとき、正確なマッチング検索を実行するステップをさらに備える方法。
請求項１に記載の方法であって、
上記１組の語句からの１組の圧縮語句値を上記語句の上記文字組み合わせ中の文字に関する演算により計算するステップ；
上記計算するステップの間に、上記演算により上記文字組み合わせの組を計算するステップ；および
上記１組の圧縮語句値を上記１組の語句に関する上記文字組み合わせの上記パターンとして定義するステップ
をさらに備える方法。
請求項５に記載の方法であって、上記パターン・マッチング・チェックが明確なパターン・マッチングの時、文字マッチング・チェックを実行するステップをさらに備える方法。
請求項６に記載の方法であって、上記パターン・マッチング・チェックおよび上記文字マッチング・チェックが各々明確なパターン・マッチングおよび明確な文字マッチングのとき正確なマッチング検索を実行するステップをさらに備える方法。
データ・ストリームを検索する方法であって、
（ａ）１組の語句を定義するステップであって、上記語句が複数の文字長および上記文字長に関しての複数の文字組み合わせをもつ複数の語句の文字を含み、上記１組の語句は１つの文字長および１つの文字組み合わせをもつ少なくとも１つの語句を含むステップ；
（ｂ）１組のテーブル・アドレスにより上記１組の語句をルール・テーブル内に格納するステップ；
（ｃ）ポインタ・マトリックスにより格納された上記１組の語句を上記１組のテーブル・アドレスに相関させるステップであって、上記ポインタ・マトリックスは１組の１対１ポインタおよび１組の行および列の座標を含み、上記１組の１対１ポインタは上記１組のテーブル・アドレスにより定義され、上記行および列の座標は上記１組の語句に対応する上記文字長および１組のパターンにより定義され、上記１組のパターンは上記文字組み合わせに一意に対応して、上記１組のパターンは上記少なくとも１つの語句に対応する少なくとも１つのパターンを含むステップ；
（ｄ）ある時間間隔の間、入力装置で上記データ・ストリームを受信するステップであって、上記データ・ストリームはあるデータ長およびあるデータ組み合わせをもつ１組のデータ文字を含み、上記時間間隔は複数のクロック・サイクルを含むステップ；
（ｅ）上記時間間隔の間、取得マトリックス経由で上記受信データ・ストリームを配列するステップであって、上記取得マトリックスは１組の取得素子および１組の遅延素子を含み、上記取得素子は上記入力装置と多重化通信して、上記取得素子は上記１組の遅延素子により階層をもち、各上記取得素子と上記入力装置の間の増加する１組の上記遅延素子が上記取得素子の上記階層内に数を増やして、上記配列受信データ・ストリームは上記取得素子の上記階層によるおよび上記１組の語句の上記文字長に対応する１組のデータ長をもち、上記配列するステップは、
（ｉ）各上記取得素子に関し上記入力装置から現在の文字を並列に読み込むステップ、
（ii）上記取得素子の上記階層により上記現在の文字を１組の以前組み合わされた文字の組と並列に組み合わせ、上記組み合わされた文字の組は上記取得素子の上記階層により上記クロック・サイクルに関連するステップ、および
（iii）上記組み合わされた文字の組を上記階層により上記１組の遅延素子および上記１組の取得素子経由でシフトして、上記組み合わされた文字の組は上記取得素子の上記階層経由で上記増加する数シフトされるステップ
をさらに備えるステップ；
（ｆ）上記組み合わされた文字の組を各上記データ長に関する上記文字組み合わせの上記パターンと比較するステップであって、上記比較ステップは、
（ｉ）各上記取得素子に関して上記取得素子の上記階層により上記文字長を各々定義するステップ、および
（ii）上記取得素子のいずれか１つ内の上記組み合わされた文字の組が上記文字組み合わせの対応する１つの上記パターンと一致するかどうか決定するステップ
をさらに備えるステップ；および
（ｇ）任意の組み合わされた文字の組が上記文字組み合わせの対応する上記パターンと一致すると、正確なマッチングのために上記受信したデータ・ストリームの一部を上記１組の語句からの正確な語句とチェックするステップであって、上記データ・ストリームの上記一部が上記組み合わされた文字の組に関する上記クロック・サイクルに対応して、上記正確な語句は上記ポインタ・マトリックスからの一意の１対１ポインタによるテーブル・アドレスに格納され、上記一意の１対１ポインタは１つの一致する上記取得素子の上記階層および上記文字組み合わせの対応する上記パターンに等しい行および列の座標をもつステップ
を備える方法。
請求項８に記載の方法であって、
大文字小文字区別マトリックスにより大文字小文字が区別される１組の上記語句を同定するステップ；
いずれの大文字小文字区別からも独立した上記１組の語句の上記パターンを定義するステップ；および
上記データ・ストリーム中の各上記文字を上記入力装置において大文字小文字を統一して設定するステップ
をさらに備える方法。
請求項８に記載の方法であって、
上記文字組み合わせ中の上記語句の文字に関する演算により、上記１組の語句から１組の圧縮語句値を計算するステップ；
上記組み合わせるステップの間上記演算により上記組み合わされた文字の組を計算するステップ；および
上記１組の語句に関する上記文字組み合わせの上記パターンとして上記１組の圧縮された語句値を定義するステップ
をさらに備える方法。
請求項１０に記載の方法であって、上記演算により上記圧縮語句値を計算する上記ステップが
上記１組の語句中の１組の値および各上記語句の文字の間の相関を定義するステップ；
各上記語句中の語句の文字を上記定義された相関による上記値と同等と見なすステップ；
各上記語句の合計を計算して、上記合計が、各上記語句の文字に相関する各上記値を含むステップ；
一意でない圧縮語句の上記合計を計算するのに使用される上記語句の文字を減らすステップであって、上記一意でない圧縮語句は同じ文字長および同じ圧縮語句値をもつ他の語句と等しい文字長および圧縮語句値をもつ任意の語句であるステップ；および
上記一意でない圧縮語句のための上記計算するステップおよび上記減らすステップを繰り返すステップ
をさらに備える方法。
請求項１１に記載の方法であって、上記演算により上記圧縮語句値を計算する上記ステップが上記合計を各上記語句に関する複数のＬＳＢに切り捨てるステップをさらに備える方法。
請求項１０に記載の方法であって、
上記演算のための最大文字長を定義して、上記最大文字長が上記取得素子の最多階層に対応するステップ；および
上記最大文字長を超える文字長をもつ各上記語句に関し上記語句値を計算する上記ステップを上記最大文字長に制限するステップ
をさらに備える方法。
請求項１３に記載の方法であって、
加算、減算、積算、除算、排他的論理和、排他的論理和の否定、および連結から構成されるグループからの上記演算を選択するステップ；
上記圧縮語句値を各上記語句値に関して複数のＬＳＢに切り捨てるステップ；
上記１組の語句中の各上記語句からの少なくとも１つの語句の文字を比較文字マトリックス内に格納するステップであって、上記比較文字マトリックスは上記取得素子の上記階層および上記切り捨てられた圧縮語句値により定義される行および列をもつステップ；
各上記取得マトリックス素子を経由して少なくとも１つのデータ文字をいずれの圧縮もせずに配列するステップ；
いずれの組み合わされた文字の組も上記文字組み合わせの上記対応するパターンに一致するとき、文字マッチングに関して、上記データ文字を上記１組の語句からの上記語句の文字と比較するステップ；および
上記文字マッチングが発生したとき上記正確なマッチングを判断する上記ステップへ進むステップ
をさらに備える方法。
請求項１４に記載の方法であって、
上記１組の圧縮語句値中の各上記圧縮語句値を１組のマッチング制御ビットと同定するステップ；および
各上記マッチング制御ビットを制御マトリックス内に格納するステップであって、上記制御マトリックスは上記取得素子の上記階層および上記切り捨てられた圧縮語句値により定義される行および列をもつステップ
をさらに備える方法。
請求項１５に記載の方法であって、
大文字小文字区別マトリックスにより大文字小文字が区別される１組の上記語句を同定するステップ；
いずれの大文字小文字区別からも独立した上記１組の語句の上記パターンを定義するステップ；および
上記データ・ストリーム中の各上記文字を上記入力装置において大文字小文字を統一して設定するステップ
をさらに備える方法。
請求項１３に記載の方法であって、コンピュータ・ネットワークのための１組のセキュリティ・ルールを上記１組の語句として定義するステップをさらに備えた方法。
請求項１７に記載の方法であって、
上記時間間隔の間上記入力装置において上記データ・ストリーム中のデータ・パケットを受信するステップであって、上記データ・パケットはヘッダおよび本体を含み、上記ヘッダは１組のプロトコル・パラメータを含み、上記包帯は上記１組のデータ文字を含むステップ；および
上記プロトコル・パラメータおよび上記データ文字を上記１組のセキュリティ・ルールとチェックして、上記コンピュータ・ネットワーク経由でセキュリティ攻撃をする試みを検出するステップ
をさらに備える方法。
請求項１８に記載の方法であって、
セキュリティ攻撃する上記試みのために、上記コンピュータ・ネットワークへ入力される複数の入力データ・パケットを検索するステップ；および
セキュリティ攻撃する上記試みのために、上記コンピュータ・ネットワークから出力される複数の出力データ・パケットを検索するステップ
をさらに備える方法。
データ・ストリームを検索する方法であって、
（ａ）上記１組のテーブル・アドレスにより１組の語句を語句テーブル内に格納するステップであって、上記語句テーブル内に格納された各上記語句が複数の語句の文字をもち、上記１組の語句は複数の文字長をもつステップ；
（ｂ）各上記語句の上記語句の文字に関する圧縮演算により、上記１組の語句を１組の圧縮された語句値へ圧縮するステップ；
（ｃ）１組の１対１ポインタにより格納された上記１組の語句を上記１組のテーブル・アドレスと相関づけるステップであって、上記１組の１対１ポインタはポインタ・マトリックスを備え、上記ポインタ・マトリックスは上記文字長および上記圧縮語句値により行および列の座標をもつステップ；
（ｄ）ある時間間隔の間入力装置で上記データ・ストリームを受信するステップであって、上記データ・ストリームは複数のデータ文字長をもつ１組のデータ文字を含み、上記時間間隔は複数のクロック・サイクルを含むステップ；
（ｅ）受信した上記データ・ストリームを取得マトリックス経由で上記時間間隔の間配列するステップであって、上記取得マトリックスは１組の取得素子および１組の遅延素子を備え、上記１組の取得素子は上記１組の遅延素子による階層をもち、上記取得素子の上記階層は上記１組の語句の上記文字長と１対１対応をもち、上記配列するステップは、
（ｉ）各上記取得素子に関して、上記入力装置から並列に現在の文字を読み込むステップ、
（ii）上記圧縮演算により上記１組のデータ文字を１組のデータ値に並列に圧縮して、上記圧縮演算が各上記取得素子内で同時に実行されるステップ、および
（iii）上記遅延素子の上記階層により上記１組の遅延素子経由で上記１組の圧縮データ値をシフトするステップ
を備えるステップ；
（ｆ）各々、各上記取得素子および各上記文字長に関する、上記１組の圧縮データ値および上記１組の圧縮語句値中の圧縮語句値の間の値のマッチングを同時にチェックするステップであって、上記１組の圧縮データ値は、上記取得素子の上記階層および上記１組の語句の上記文字長の間の上記１対１対応により、各々、上記１組の圧縮語句値とチェックして、パターン・マッチングは上記１組の圧縮データ値からの一致する圧縮データ値および上記取得素子の上記階層からの一致する階層を返すステップ；および
（ｇ）上記値のマッチングが発生したとき、上記受信データ・ストリームおよび上記１組の語句からの正確な語句の間の正確なマッチングをチェックするステップであって、上記正確な語句は上記ポインタ・マトリックスからの一意の１対１ポインタによりあるテーブル・アドレスに格納され、上記一意の１対１ポインタは上記一致する圧縮データ値および上記一致する階層と等しい行および列の座標をもつステップ
を備える方法。
請求項２０に記載の方法であって、上記圧縮演算が合計を計算する上記ステップをさらに備える方法。
請求項２１に記載の方法であって、各上記語句に関し上記合計を複数のＬＳＢへ切り捨てるステップをさらに備える方法。
請求項２０に記載の方法であって、
大文字小文字区別マトリックスにより大文字小文字が区別される１組の上記語句を同定するステップ；
いずれの大文字小文字区別からは独立して上記比較演算を定義するステップ；
上記圧縮演算のための最大文字長を定義して、上記最大文字長が上記取得素子の最多階層に対応するステップ；
上記１組の語句を圧縮する上記ステップを、上記最大文字長を超える文字長をもつ各上記語句に関する上記最大文字長に制限するステップ；および
上記データ・ストリーム中の各上記文字を上記入力装置において大文字小文字を統一して設定するステップ
をさらに備える方法。
請求項２３に記載の方法であって、
加算、減算、積算、除算、排他的論理和、排他的論理和の否定、および連結から構成されるグループからの上記演算を選択するステップ；
上記圧縮語句値を各上記語句値に関して複数のＬＳＢに切り捨てるステップ；
上記１組の語句中の各上記語句からの少なくとも１つの語句の文字を比較文字マトリックス内に格納するステップであって、上記比較文字マトリックスは上記取得素子の上記階層および上記切り捨てられた圧縮語句値により定義される行および列をもつステップ；
各上記取得マトリックス素子を経由して少なくとも１つのデータ文字をいずれの圧縮もせずに配列するステップ；
上記値マッチングが発生したとき、上記データ文字および上記１組の語句からの上記語句の文字の間の文字マッチングをチェックするステップ；および
上記文字マッチングが発生したとき、上記正確なマッチングをチェックする上記ステップへ進むステップ
をさらに備える方法。
請求項２４に記載の方法であって、
上記１組の圧縮語句値中の各上記圧縮語句値を１組のマッチング制御ビットと同定するステップ；および
各上記マッチング制御ビットを制御マトリックス内に格納するステップであって、上記制御マトリックスは上記取得素子の上記階層および上記切り捨てられた圧縮語句値により定義される行および列をもつステップ
をさらに備える方法。
請求項２０に記載の方法であって、１組のセキュリティ・ルールを上記１組の語句として定義するステップをさらに備えた方法。
コンピュータ・ネットワークへセキュリティ攻撃する試みを検出する方法であって、
（ａ）１組のセキュリティ・ルールを定義するステップであって、上記セキュリティ・ルールは複数の文字長内および複数の文字組み合わせ内の複数の文字を含むステップ；
（ｂ）上記１組のセキュリティ・ルールを１組のテーブル・アドレスによりルール・テーブル内に格納するステップ；
（ｃ）格納された上記１組のセキュリティ・ルールを１組の１対１ポインタにより上記１組のテーブル・アドレスと相関づけるステップであって、上記１組の１対１ポインタはポインタ・マトリックスを含み、上記ポインタ・マトリックスは上記１組のセキュリティ・ルールの上記文字長および上記１組のセキュリティ・ルールに対応する１組のパターンによる行および列をもち、上記１組のパターンは各上記セキュリティ・ルールに関する上記文字長内の上記文字組み合わせにより上記１組のセキュリティ・ルールと一意に対応するステップ；
（ｄ）上記時間間隔の間上記入力装置においてデータ・パケットを受信するステップであって、上記データ・パケットはある長さをもつ１組の文字を含み、上記時間間隔は複数のクロック・サイクルを含むステップ；
（ｅ）上記時間間隔の間取得マトリックスを経由して受信した上記データ・パケットを配列するステップであって、上記取得マトリックスは１組の取得素子および１組の遅延素子を含み、上記取得素子は上記入力装置と多重化通信して、上記取得素子は上記１組の遅延素子により階層をもち、各上記取得素子および入力装置の間の増加する１組の上記遅延素子が上記取得素子の上記階層の増加する数となり、上記配列データ・パケットは上記取得素子の上記階層による１組の長さをもち、上記取得素子の上記階層は上記１組のセキュリティ・ルールの上記文字長に１対１対応をもち、上記配列するステップは、
（ｉ）各上記取得素子に関し上記入力装置から現在の文字を並列に読み込むステップ、
（ii）上記取得素子の上記階層により上記現在の文字を１組の以前組み合わされた文字の組と並列に組み合わせ、組み合わされた文字の組を生成するステップ、および
（iii）上記階層により上記１組の遅延素子および上記１組の取得素子経由で上記組み合わされた文字の組をシフトするステップ
をさらに備えるステップ；
（ｆ）上記受信したデータ・パケットからの上記組み合わされた文字の組および上記取得素子並びに各上記文字長各々に関する上記１組のセキュリティ・ルールに一意に対応する上記１組のパターンのパターン・マッチングを同時にチェックするステップであって、上記組み合わされた文字の組は上記取得素子の上記階層および上記１組の語句の上記文字長の間の上記１対１対応により上記１組のパターンと各々チェックされて、パターン・マッチングは上記組み合わされた文字の組のうち一致する文字の組および上記取得素子の一致する階層を返すステップ；および
（ｇ）上記パターン・マッチングが発生すると、上記データ・パケットの一部および上記１組のセキュリティ・ルールからの正確なセキュリティ・ルールの間の正確なマッチングをチェックするステップであって、上記正確なセキュリティ・ルールは上記ポインタ・マトリックスからの一意の１対１ポインタにより上記ルール・テーブル内のあるテーブル・アドレスに格納され、上記一意の１対１ポインタは上記一致する組み合わされた文字の組および上記一致する階層と等しい行と列をもつステップ
を備える方法。
データ・ストリームを検索するシステムであって、
１組の語句および１組のテーブル・アドレスをもつルール・テーブルであって、上記１組の語句中の各上記語句は、上記ルール・テーブル内の、上記１組のテーブル・アドレス内のあるテーブル・アドレスにより定義される位置に格納され、上記１組の語句は複数の文字長および上記文字長に関する複数の文字組み合わせをもつ複数の語句の文字を含み、上記１組の語句は１つの文字長および１つの文字組み合わせをもつ少なくとも１つの語句を含むルール・テーブル；
ポインタ・マトリックスを含む１組の１対１ポインタであって、上記１組の１対１ポインタは上記テーブル・アドレスを上記ルール・テーブル内の上記１組の語句と相関づけ、上記ポインタ・マトリックスは上記１組の語句に対応する上記文字長および上記１組のパターンにより定義される行および列の座標を含み、上記１組のパターンは同じ文字長をもつ任意の上記語句に関し上記文字組み合わせと一意に対応して、上記１組のパターンは上記少なくとも１つの語句に対応する少なくとも１つのパターンを含む１組の１対１ポインタ；
バッファ・メモリ；
ある時間間隔の間上記データ・ストリームを受信する入力装置であって、上記データ・ストリームは１つのデータ長と１つのデータ組み合わせをもつ１組のデータ文字を含み、上記時間間隔は複数のクロック・サイクルを含み、上記入力装置は上記バッファ・メモリ経由で上記データ・ストリームを通信するバイパスをさらに含む入力装置；
１組の取得素子および１組の遅延素子を含む取得マトリックスであって、上記取得マトリックスは上記入力装置からの上記データ・ストリーム中の上記１組の上記データ文字を各上記取得素子経由で配列して、上記取得素子は上記入力装置と多重化通信して、上記取得素子は上記１組の遅延素子による階層をもち、上記取得素子の上記階層は上記１組の語句の上記文字長と１対１対応をもち、上記１組の取得素子は上記取得素子の上記階層により１組のメモリと比較器の対をさらに含み、上記１組のデータ文字は上記メモリと比較器の対に配列データの１組の組として入っていき、上記１組のメモリと比較器の対は上記１組の配列データおよび上記１組のパターンの間のパターン・マッチングをチェックして、各上記メモリと比較器の対は上記取得素子の上記階層および上記１組の語句の上記文字長の間の上記１対１対応により上記パターン・マッチングを同時にチェックして、一致するメモリと比較器の対は上記取得素子の上記階層および上記配列データにより行および列の座標を定義する取得マトリックス；
上記バッファ、上記取得マトリックスおよび上記ルール・テーブルと通信する正確なマッチング検索であって、上記正確なマッチング検索が上記バッファから上記データ・ストリームの一部を受信して、および上記取得マトリックスから上記行および列の座標を受信して、上記行および列の座標は階層および上記一致するメモリと比較器の対により配列データを含み、上記正確なマッチング検索は、上記ポインタ・マトリックス内のテーブル・アドレスにより上記ルール・テーブルから正確な語句を抽出し、上記テーブル・アドレスは上記行および列の座標をもつ一意の１対１ポインタにより定義され、上記正確なマッチング検索は上記正確な語句および上記データ・ストリームの上記部分の間の正確なマッチングをチェックする正確なマッチング検索
を備えるシステム。
請求項２８に記載のシステムであって、上記取得マトリックスが各上記取得素子および上記入力装置の間の増加する１組の上記遅延素子を含み、上記増加する１組の上記遅延素子が上記取得素子の上記階層の増加する数を定義し、上記増加する数の上記階層が上記データ・ストリームの増加する文字長に対応するシステム。
請求項２８に記載のシステムであって、各上記取得素子が上記入力装置と各上記メモリと比較器の対の間に位置する比較演算器をさらに含むシステム。
請求項３０に記載のシステムであって、上記比較演算器が、加算、減算、積算、除算、排他的論理和、排他的論理和の否定、および連結から構成される演算器のグループから選択されるシステム。
請求項３０に記載のシステムであって、各上記取得素子が上記比較演算器および各上記メモリと比較器の対の間に位置する切り捨て素子をさらに含むシステム。
請求項２８に記載のシステムであって、各上記取得素子が上記入力装置および各上記メモリ比較器の組の間に位置する加算演算器をさらに含むシステム。
請求項３３に記載のシステムであって、各上記取得素子が上記加算演算器および各上記メモリと比較器の対の間に位置する切り捨て素子をさらに含むシステム。
請求項２８に記載のシステムであって、上記取得素子が上記ルール・テーブル内の上記１組の語句の最大文字長に対応する最多階層をもつシステム。
請求項２８に記載のシステムであって、上記１組の語句が１組のセキュリティ・ルールをさらに含むシステム。
請求項２８に記載のシステムであって、上記取得マトリックスがコンテンツ・アドレッサブル・メモリであり、上記メモリと比較器の対が上記１組の１対１ポインタを含むシステム。
請求項２８に記載のシステムであって、上記取得マトリックスが標準的なメモリであり、上記メモリと比較器の対が比較器と通信するメモリから構成されるシステム。
請求項２８に記載のシステムであって、追加の取得マトリックスをさらに含み、上記追加の取得マトリックスが追加の１組の取得素子および追加の１組の遅延素子を含み、上記追加の取得マトリックスが上記入力装置および上記取得マトリックスと通信するシステム。