【手続補正書】
【提出日】平成22年4月22日(2010.4.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のデータシンボルを含むデータ文字列が複数のパターンのうちのいずれかとの近似合致を含むか否かの決定を容易化するために、データ文字列内の複数のデータサブ文字列を処理する方法であって、
複数の可能性のある合致を検出するためにフィルタ回路にデータサブ文字列について問い合わせをするステップであって、各可能性のある合致がデータサブ文字列とパターン断片との間の可能性のある合致を表し、複数のパターンの各パターンが複数の対応するパターン断片を含み、フィルタ回路がパターン断片でプログラムされている、問い合わせをするステップと、
複数のパターンセットを決定するために、検出された可能性のある合致を削減ステージに適用するステップであって、各パターンセットが、検出された可能性のある合致と対応し、（１）対応する可能性のある合致を生じたパターン断片に対応するパターンを表すデータおよび（２）該パターンに関連する許容可能な誤りを表すデータを含む、適用するステップと、
配信されたパターンセット内の許容可能な誤りデータを考慮して、配信されたパターンセット内のパターンのいずれかと、データ文字列の少なくとも一部が近似合致するか否かを決定するために、決定されたパターンセットを近似合致エンジンに配信するステップとを含む、方法。
【請求項２】
フィルタ回路がブルームフィルタ回路である、請求項１に記載の方法。
【請求項３】
配信されたパターンセット内の許容可能な誤りデータを考慮して、データ文字列部分と配信されたパターンセット内のパターンとの間で何らかの近似合致が存在するか否かを近似合致エンジンを用いて判定するステップをさらに含む、請求項１または２に記載の方法。
【請求項４】
少なくとも複数のパターンであるパターンを複数のパターン断片にスライスするステップと、
パターン断片を用いてブルームフィルタ回路をプログラムするステップとをさらに含む、請求項２に記載の方法。
【請求項５】
問い合わせするステップおよび適用するステップをパイプライン方式で実行するステップをさらに含む、請求項１から４のいずれか一項に記載の方法。
【請求項６】
再構成可能なハードウェアを用いて、問い合わせするステップおよび適用するステップを実行するステップをさらに含む、請求項１から５のいずれか一項に記載の方法。
【請求項７】
再構成可能なハードウェアを用いて、判定するステップを実行するステップをさらに含む、請求項１から６のいずれか一項に記載の方法。
【請求項８】
ブルームフィルタ回路が複数の並列ブルームフィルタ回路を含み、各並列ブルームフィルタ回路が他の並列ブルームフィルタ回路とは異なるパターン断片長に対応するように、並列ブルームフィルタ回路の各々が同じ長さのパターン断片でプログラムされており、問い合わせステップが、複数のデータサブ文字列を並列ブルームフィルタ回路に並列に同時に提供するステップを含む、請求項４に記載の方法。
【請求項９】
ブルームフィルタ回路が、データ文字列の少なくとも一部を記憶するシフトレジスタをさらに含み、方法が、シフトレジスタを通してデータ文字列のデータシンボルを流すステップと、問い合わせするステップのためにシフトレジスタからデータサブ文字列を読むステップとをさらに含む、請求項２、４又は８のいずれか一項に記載の方法。
【請求項１０】
各並列ブルームフィルタ回路が、複数のビットベクトルを記憶するように構成されており、各ビットベクトルが複数のビットを含み、各ビットが値を有し、問い合わせするステップが、
少なくとも１つのハッシュキーを生成するために、各データサブ文字列を少なくとも１つのハッシュ関数に適用するステップと、
少なくとも１つの生成されたハッシュキーに基づいて、並列ブルームフィルタ回路からビットベクトルを取り出すステップと、
少なくとも１つの生成されたハッシュキーに基づいて、取り出されたビットベクトルの複数のビットの位置を選択するステップと、
選択されたビットの位置にあるビットの値に基づいて、該データサブ文字列とパターン断片との間に可能性のある合致が存在するか否かを判定するステップとをさらに含む、請求項８に記載の方法。
【請求項１１】
各データサブ文字列を少なくとも１つのハッシュ関数に適用するステップが、複数のハッシュキーを生成するために複数のハッシュ関数に各データサブ文字列を適用するステップを含み、ビットベクトルを取り出すステップが、生成されたハッシュキーに基づいて並列ブルームフィルタ回路からビットベクトルを取り出すステップを含み、ビットの位置を選択するステップが、複数の他の生成されたハッシュキーに基づいて、取り出されたビットベクトルの複数のビットの位置を選択するステップを含む、請求項１０に記載の方法。
【請求項１２】
各データサブ文字列を少なくとも１つのハッシュ関数に適用するステップが、単一のハッシュキーを生成するために単一のハッシュ関数に各データサブ文字列を適用するステップを含み、ビットベクトルを取り出すステップが、生成されたハッシュキーの一部に基づいて並列ブルームフィルタ回路からビットベクトルを取り出すステップを含み、ビットの位置を選択するステップが、生成されたハッシュキーの別の部分に基づいて、取り出されたビットベクトルの複数のビットの位置を選択するステップを含む、請求項１０に記載の方法。
【請求項１３】
削減ステージが、（１）各パターン断片識別子が問い合わせするステップの結果として生成されたデータによってインデックス付けされる、複数のパターン断片識別子を記憶し、（２）各パターン識別子がパターン断片識別子によってインデックス付けされる、複数のパターン識別子を記憶し、（３）各パターンセット対がパターン識別子によってインデックス付けされる、複数のパターンセット対を記憶するように構成されており、各パターンセット対が、（ａ）パターンを表すデータおよび（ｂ）該パターンに関連する許容可能な誤りを表すデータを含み、可能性のある合致を適用するステップが、
問い合わせするステップの結果として生じたデータに基づいて、記憶されているパターン断片識別子の少なくとも１つを取り出すステップと、
各取り出されたパターン断片識別子に基づいて、記憶されているパターン識別子の少なくとも１つを取り出すステップと、
各取り出されたパターン識別子に基づいて、記憶されているパターンセット対の少なくとも１つを取り出すステップとを含み、取り出された少なくとも１つのパターンセット対が、パターンセットの少なくとも一部を規定する、請求項１から１２のいずれか一項に記載の方法。
【請求項１４】
パターン断片識別子を取り出すステップが、少なくとも１つの生成されたハッシュキーに対応するデータに基づいて、記憶されているパターン断片識別子の少なくとも１つを取り出すステップを含む、請求項１３に記載の方法。
【請求項１５】
削減ステージが、（１）各パターン識別子がパターン断片によってインデックス付けされる、複数のパターン識別子を記憶し、（２）各パターンセット対がパターン識別子によってインデックス付けされる、複数のパターンセット対を記憶するように構成されており、各パターンセット対が、（ａ）パターンを表すデータおよび（ｂ）該パターンに関連する許容可能な誤りを表すデータを含み、可能性のある合致を適用するステップが、
可能性のある合致を生じたデータサブ文字列に基づいて、記憶されているパターン識別子の少なくとも１つを取り出すステップと、
各取り出されたパターン識別子に基づいて、記憶されているパターンセット対の少なくとも１つを取り出すステップとを含み、取り出された少なくとも１つのパターンセット対が、パターンセットの少なくとも一部を規定する、請求項１から１２のいずれか一項に記載の方法。
【請求項１６】
複数のデータシンボルを含むデータ文字列が複数のパターンのうちのいずれかとの近似合致を含むか否かの決定を容易化するために、データ文字列内の複数のデータサブ文字列を処理するシステムであって、
複数の可能性のある合致を検出するためにデータサブ文字列によって問い合わせされるように構成されているフィルタ回路であって、各可能性のある合致がデータサブ文字列とパターン断片との間の可能性のある合致を表し、複数のパターンの各パターンが複数の対応するパターン断片を含み、フィルタ回路がパターン断片でプログラムされている、フィルタ回路と、
フィルタ回路と通信する削減ステージであって、削減ステージが、（１）検出された可能性のある合致を処理し、（２）処理に応じて複数のパターンセットを決定し、各パターンセットが可能性のある合致に対応して（ａ）対応する可能性のある合致を生じたパターン断片に対応するパターンを表すデータと、（ｂ）該パターンに関連する許容可能な誤りを表すデータとを含み、（３）決定されたパターンセット内の許容可能な誤りデータを考慮して、データ文字列の少なくとも一部が、決定されたパターンセット内のいずれかパターンと近似合致するか否かを判定するために、近似合致エンジンに決定されたパターンセットを出力するように構成されている、削減ステージとを含む、システム。
【請求項１７】
フィルタ回路がブルームフィルタ回路である、請求項１６に記載のシステム。
【請求項１８】
削減ステージと通信しており、決定されたパターンセット内の許容可能な誤りデータを考慮して、データ文字列部分と決定されたパターンセット内のパターンとの間で何らかの近似合致が存在するか否かを判定するように構成されている近似合致エンジンをさらに含む、請求項１６または１７に記載のシステム。
【請求項１９】
ブルームフィルタ回路および削減ステージがパイプライン方式で動作するように構成されている、請求項１７に記載のシステム。
【請求項２０】
ブルームフィルタ回路および削減ステージが再構成可能なハードウェアを用いて実装されている、請求項１７または１９に記載のシステム。
【請求項２１】
近似合致エンジンが再構成可能なハードウェアを用いて実装されている、請求項１８に記載のシステム。
【請求項２２】
パターン断片が、異なる長さの複数のパターン断片である、請求項１６から２１のいずれか一項に記載のシステム。
【請求項２３】
同じパターンに対応するパターン断片が互いに重なり合わない、請求項１６から２１のいずれか一項に記載のシステム。
【請求項２４】
ブルームフィルタ回路が複数の並列ブルームフィルタ回路を含み、各並列ブルームフィルタ回路が他の並列ブルームフィルタ回路とは異なるパターン断片長に対応するように、並列ブルームフィルタ回路の各々が同じ長さのパターン断片でプログラムされており、ブルームフィルタ回路が、複数のデータサブ文字列を並列ブルームフィルタ回路に並列に同時に提供するようにさらに構成されている、請求項１７、１９または２０のいずれか一項に記載のシステム。
【請求項２５】
ブルームフィルタ回路が、データ文字列の少なくとも一部を記憶するシフトレジスタをさらに含み、ブルームフィルタ回路が、（１）シフトレジスタを通してデータ文字列のデータシンボルを流し、（２）並列ブルームフィルタ回路への配信のためにシフトレジスタからデータサブ文字列を読むようにさらに構成されている、請求項２４に記載のシステム。
【請求項２６】
各並列ブルームフィルタ回路が、複数のビットベクトルを記憶するように構成されており、各ビットベクトルが複数のビットを含み、各ビットが値を有し、ブルームフィルタ回路が、（１）少なくとも１つのハッシュキーを生成するために、各データサブ文字列を少なくとも１つのハッシュ関数に適用し、（２）少なくとも１つの生成されたハッシュキーに基づいて、並列ブルームフィルタ回路からビットベクトルを取り出し、（３）少なくとも１つの生成されたハッシュキーに基づいて、取り出されたビットベクトルの複数のビットの位置を選択し、（４）選択されたビットの位置にあるビットの値に基づいて、該データサブ文字列とパターン断片との間に可能性のある合致が存在するか否かを判定するようにさらに構成されている、請求項２４に記載のシステム。
【請求項２７】
各並列ブルームフィルタ回路が、（１）複数のハッシュキーを生成するために複数のハッシュ関数に各データサブ文字列を適用し、（２）生成されたハッシュキーに基づいて並列ブルームフィルタ回路からビットベクトルを取り出し、（３）複数の他の生成されたハッシュキーに基づいて、取り出されたビットベクトルの複数のビットの位置を選択するようにさらに構成されている、請求項２６に記載のシステム。
【請求項２８】
各並列ブルームフィルタ回路が、（１）単一のハッシュキーを生成するために単一のハッシュ関数に各データサブ文字列を適用し、（２）生成されたハッシュキーの一部に基づいて並列ブルームフィルタ回路からビットベクトルを取り出し、（３）生成されたハッシュキーの別の部分に基づいて、取り出されたビットベクトルの複数のビットの位置を選択するようにさらに構成されている、請求項２６に記載のシステム。
【請求項２９】
削減ステージが第１のテーブル、第２のテーブルおよび第３のテーブルを含み、第１のテーブルは、各パターン断片識別子がブルームフィルタ回路によって生成されたデータによってインデックス付けされる、複数のパターン断片識別子を記憶するように構成されており、第２のテーブルは、各パターン識別子がパターン断片識別子によってインデックス付けされる、複数のパターン識別子を記憶するように構成されており、第３のテーブルは、各パターンセット対がパターン識別子によってインデックス付けされる、複数のパターンセット対を記憶するようにさらに構成されており、各パターンセット対が、（ａ）パターンを表すデータおよび（ｂ）該パターンに関連する許容可能な誤りを表すデータを含み、削減ステージが、（１）ブルームフィルタ回路によって生じたデータに基づいて、第１のテーブルから記憶されているパターン断片識別子の少なくとも１つを取り出し、（２）各取り出されたパターン断片識別子に基づいて、第２のテーブルから記憶されているパターン識別子の少なくとも１つを取り出し、（３）各取り出されたパターン識別子に基づいて、第３のテーブルから記憶されているパターンセット対の少なくとも１つを取り出すようにさらに構成されており、少なくとも１つの取り出されたパターンセット対が、パターンセットの少なくとも一部を規定する、請求項１６から２８のいずれか一項に記載のシステム。
【請求項３０】
削減ステージが第１のデータ構造および第２のデータ構造を含み、第１のデータ構造は、各パターン識別子がパターン断片によってインデックス付けされる、複数のパターン識別子を記憶するように構成されており、第２のデータ構造は、各パターンセット対がパターン識別子によってインデックス付けされる、複数のパターンセット対を記憶するように構成されており、各パターンセット対が、（ａ）パターンを表すデータおよび（ｂ）該パターンに関連する許容可能な誤りを表すデータを含み、削減ステージが、（１）可能性のある合致を生じたデータサブ文字列に基づいて、第１のデータ構造から記憶されているパターン識別子の少なくとも１つを取り出し、（２）各取り出されたパターン識別子に基づいて、第２のデータ構造から記憶されているパターンセット対の少なくとも１つを取り出すようにさらに構成されており、少なくとも１つの取り出されたパターンセット対が、パターンセットの少なくとも一部を規定する、請求項１６から２８のいずれか一項に記載のシステム。