(57)【要約】      （修正有）【課題】ルールを格納するために必要なＣＡＭの使用エントリ数を低減する技術を提供する。【解決手段】ライトデータ変換装置２３０は、３値以上を保持可能な連想メモリに格納される、検索キーの比較対象であるエントリデータ７８０を生成する。このライトデータ変換装置は、入力された正規表現に従うルールから、正規表現に基づいて複数の文字列を抽出し、複数の文字列に含まれる第１および第２文字列を互いに異なる第１および第２ビットデータにそれぞれ変換するための変換回路７１０と、第１ビットデータと第２ビットデータとをビットごとに比較して、比較結果に基づいて第１ビットデータを構成する複数のビットのうち不一致であるビットを、ドントケア値に変換したエントリデータを生成するエンコード回路７４０とを備える。【選択図】図７
2018026046.tif 000002
【特許請求の範囲】
【請求項１】
３値以上を保持可能な連想メモリに格納される、検索キーの比較対象であるエントリデータを生成するためのデータ変換装置であって、
入力された正規表現に従うルールから、前記正規表現に基づいて複数の文字列を抽出し、前記複数の文字列に含まれる第１および第２文字列を互いに異なる第１および第２ビットデータにそれぞれ変換するための変換回路と、
前記第１ビットデータと前記第２ビットデータとをビットごとに比較して、比較結果に基づいて前記第１ビットデータを構成する複数のビットのうち不一致であるビットを、ドントケア値に変換したエントリデータを生成するエンコード回路とを備える、データ変換装置。
【請求項２】
前記変換回路は、前記複数の文字列に共通するカテゴリを示すビットデータを含むように、前記第１および第２文字列を、前記第１および第２ビットデータにそれぞれ変換する、請求項１に記載のデータ変換装置。
【請求項３】
前記ルールは、論理和の正規表現を含む、請求項１に記載のデータ変換装置。
【請求項４】
前記変換回路は、
前記複数の文字列の各々を、連続した数字の登録コードに変換し、
前記第１文字列に対応する最小値の登録コード、および前記第２文字列に対応する最大値の登録コードを、前記登録コードの数字に応じて第１および第２ビットデータにそれぞれ変換する、請求項３に記載のデータ変換装置。
【請求項５】
前記ルールは、文字の繰り返しの正規表現を含む、請求項１に記載のデータ変換装置。
【請求項６】
前記変換回路は、前記ルールに含まれる正規表現の種類に応じて、前記第１および第２ビットデータをそれぞれ生成する、請求項１に記載のデータ変換装置。
【請求項７】
前記エンコード回路は、前記ルールに含まれる正規表現の種類を示す第３ビットデータを含むようにエントリデータを生成する、請求項１に記載のデータ変換装置。
【請求項８】
複数の文字列を記憶するための記憶装置と、
前記抽出された複数の文字列の各々が、前記記憶装置に格納される複数の文字列のいずれかに一致するか否かを判断するための比較回路とをさらに備え、
前記比較回路は、
一致すると判断した場合に、前記抽出された複数の文字列を前記変換回路に出力し、
一致しないと判断した場合に、前記抽出された複数の文字列を前記エントリデータとして前記連想メモリに出力する、請求項１に記載のデータ変換装置。
【請求項９】
３値以上を保持可能な連想メモリを有する検索装置と、
前記連想メモリに格納される、検索キーの比較対象であるエントリデータを生成するためのデータ変換装置と、
入力された検索条件を検索キーに変換して前記検索装置に出力するためのサーチデータ変換装置とを備え、
前記データ変換装置は、
入力された正規表現に従うルールから、前記正規表現に基づいて複数の文字列を抽出し、前記複数の文字列に含まれる第１および第２文字列を互いに異なる第１および第２ビットデータにそれぞれ変換するための変換回路と、
前記第１ビットデータと前記第２ビットデータとをビットごとに比較して、比較結果に基づいて前記第１ビットデータを構成する複数のビットのうち不一致であるビットを、ドントケア値に変換したエントリデータを生成するエンコード回路とを含む、検索システム。
【請求項１０】
前記変換回路は、予め定められた条件に従って前記第１および第２ビットデータを生成し、
前記サーチデータ変換装置は、入力された検索条件に含まれる文字列を、前記予め定められた条件に従って前記検索キーに変換して前記検索装置に出力する、請求項９に記載の検索システム。
【請求項１１】
正規表現に従う検索条件に基づいて検索を実行可能に構成される検索エンジンと、
入力された検索条件に含まれる正規表現の種類に応じて、当該検索条件に含まれる複数の文字列を、前記サーチデータ変換装置および前記検索エンジンのいずれか一方に出力するための切替装置とをさらに備える、請求項９に記載の検索システム。
【請求項１２】
３値以上を保持可能な連想メモリに格納される、検索キーの比較対象であるエントリデータを生成するための方法であって、
入力された正規表現に従うルールから、前記正規表現に基づいて複数の文字列を抽出するステップと、
前記複数の文字列に含まれる第１および第２文字列を互いに異なる第１および第２ビットデータにそれぞれ変換するステップと、
前記第１ビットデータと前記第２ビットデータとをビットごとに比較して、比較結果に基づいて前記第１ビットデータを構成する複数のビットのうち不一致であるビットをドントケア値に変換したエントリデータを生成するステップとを備える、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この開示は、データを変換する技術に関し、より特定的には、ルール（マッチ条件）を連想メモリに格納するためのエントリデータに変換する技術に関する。
【背景技術】
【０００２】
高速な検索動作が可能な連想メモリ（ＣＡＭ：Content  Addressable  Memory）が一般的に知られている。連想メモリを用いた検索装置は、ルータやネットワークスイッチに用いられており、ネットワークトラフィックの増大に伴い、検索データワードを格納するエントリの数の増大（ＣＡＭの大容量化）が求められている。
【０００３】
米国特許出願公開第２００８／０３４１２８４号明細書（特許文献１）は、連想メモリを用いて正規表現に従う文字列を検索する正規表現検索エンジンを開示している。より具体的には、この検索エンジンは、入力された正規表現の複雑度レベルを判定し、当該複雑度に従って選択された１つのＣＡＭデバイスに正規表現を記憶するように構成される。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許出願公開第２００８／０３４１２８４号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１に開示される技術は、例えば、「ａｂ（ｃ｜ｄ）」のような論理和の正規表現に従うルール（マッチ条件）をＴＣＡＭ（Ternary  Content  Addressable  Memory）に格納する場合、ａ，ｂ，ｃ，ｄの各々を異なるエントリに格納する。そのため、当該技術は、ルールを格納するために必要なＣＡＭの使用エントリ数が多いという問題がある。
【０００６】
また、同技術は、検索条件に含まれる正規表現の種類に応じて、ＰＲＳ（Programmable  interconnect  Structure：ローカル配線帯）のＰＳＭ（Programmable  Switch  Matrixes：接続スイッチ）を切り替えることにより、文字列検索を行なう。そのため、同技術は、汎用的なＴＣＡＭに、ＰＲＳ、ＰＳＭ、およびラッチ回路等の文字列検索ロジックを追加する必要がある、という問題を有する。
【０００７】
本開示は、上記のような問題を解決するためになされたものであって、ある局面における目的は、ルール（マッチ条件）を格納するために必要なＣＡＭの使用エントリ数を低減する技術を提供することである。
【課題を解決するための手段】
【０００８】
ある実施形態に従うデータ変換装置は、３値以上を保持可能な連想メモリに格納される、検索キーの比較対象であるエントリデータを生成する。このデータ変換装置は、入力された正規表現に従うルールから、正規表現に基づいて複数の文字列を抽出し、複数の文字列に含まれる第１および第２文字列を互いに異なる第１および第２ビットデータにそれぞれ変換するための変換回路と、第１ビットデータと第２ビットデータとをビットごとに比較して、比較結果に基づいて第１ビットデータを構成する複数のビットのうち不一致であるビットを、ドントケア値に変換したエントリデータを生成するエンコード回路とを備える。
【発明の効果】
【０００９】
ある実施形態に従うデータ変換装置は、ルールを格納するために必要なＣＡＭの使用エントリ数を低減できる。これにより、ＣＡＭは、より多くのルール（マッチ条件）を格納できる。
【００１０】
この発明の上記および他の目的、特徴、局面および利点は、添付の図面と関連して理解されるこの発明に関する次の詳細な説明から明らかとなるであろう。
【図面の簡単な説明】
【００１１】
【図１】実施形態に従う検索条件（文字列）のデータ変換装置の概要について説明する図である。
【図２】実施形態１に従う検索システムの構成例について説明する図である。
【図３】実施形態１に従うＴＣＡＭ装置に含まれるＴＣＡＭセルの構成例を説明する図である。
【図４】図３のＸセルおよびＹセルの記憶内容とＴＣＡＭセルデータとの対応関係を表形式で示す図である。
【図５】ＴＣＡＭ装置を構成する１つのサブアレイの構成を示すブロック図である。
【図６】ＴＣＡＭ装置の構成を示すブロック図である。
【図７】実施形態１に従うライトデータ変換回路の構成例について説明する図である。
【図８】実施形態１に従う文字列抽出変換回路の動作について説明する図である。
【図９】実施形態１に従う文字列レジスタの動作について説明する図である。
【図１０】実施形態１に従う比較変換回路の動作について説明する図である。
【図１１】実施形態１に従う第１エンコード回路の動作について説明する図である。
【図１２】実施形態１に従う第２エンコード回路の動作について説明する図である。
【図１３】実施形態１に従うセレクタ回路の動作について説明する図である。
【図１４】実施形態１に従うサーチデータ変換回路の構成例について説明する図である。
【図１５】実施形態２に従う第１エンコード回路について説明する図である。
【図１６】実施形態３に従うライトデータ変換回路の構成例について説明する図である。
【図１７】実施形態３に従う文字列抽出変換回路の動作について説明する図である。
【図１８】実施形態３に従う文字列レジスタの動作を説明する図である。
【図１９】実施形態３に従う第１エンコード回路の動作について説明する図である。
【図２０】実施形態３に従う第２エンコード回路の動作を説明する図である。
【図２１】実施形態３に従うセレクタ回路の動作について説明する図である。
【図２２】実施形態３に従うサーチデータ変換回路の構成例について説明する図である。
【図２３】実施形態３に従う文字列変換回路の動作について説明する図である。
【図２４】実施形態３に従う繰り返し変換回路の動作について説明する図である。
【図２５】実施形態３に従う比較回路の動作について説明する図である。
【図２６】実施形態４に従う繰り返し回数を示すビットデータのデータ構造について説明する図である。
【図２７】実施形態４に従う第１エンコード回路の動作について説明する図である。
【図２８】実施形態５に従う検索システムの構成例について説明する図である。
【図２９】実施形態５に従う第３エンコードデータおよび第４エンコードデータのデータ構造について説明する図である。
【図３０】実施形態６に従う検索システムの構成例を説明する図である。
【発明を実施するための形態】
【００１２】
以下、この発明の実施形態について図面を参照しながら詳細に説明する。以下の説明では、同一の部品には同一の符号を付してある。それらの名称および機能も同じである。従って、それらについての詳細な説明は繰り返さない。
【００１３】
［技術思想］
図１は、実施形態に従うデータ変換装置の概要について説明する図である。分図（Ａ）は、関連技術に従うデータ変換装置について説明する図である。一例として、論理和の正規表現を含む「ＪＡＮ｜ＤＥＣ」を検索キーに対するマッチ条件（Ｈｉｔ条件）としてのルール１０５とする。
【００１４】
ステップＳ１１０において、関連技術に従うデータ変換装置は、ルール１０５から、論理和の正規表現に基づいて文字列「ＪＡＮ」と「ＤＥＣ」とを抽出する。同ステップにおいて、これらの文字列をＡＳＣＩＩ文字コード１１２，１１４にそれぞれ変換する。
【００１５】
ステップＳ１２０において、関連技術に従うデータ変換装置は、文字コード１１２，１１４をそれぞれ２進数のビットデータ１２２，１２４に変換する。ステップＳ１４０において、データ変換装置は、ビットデータ１２２，１２４をエントリデータとしてＴＣＡＭに格納する。したがって、関連技術に従うデータ変換装置は、２つの文字列から構成される論理和のルールに対して、２つのエントリデータをＴＣＡＭに格納する。
【００１６】
分図（Ｂ）は、実施形態に従うデータ変換装置について説明する図である。実施形態に従うデータ変換装置は、関連技術に従うデータ変換装置と比して、ステップＳ１３０をさらに有する点で相違する。
【００１７】
ステップＳ１３０において、実施形態に従うデータ変換装置は、ビットデータ１２２と、ビットデータ１２４とをビットごとに比較して、ビットデータ１２２および１２４のうちいずれか一方のビットデータを構成するビットのうち、不一致のビットをドントケア（Don't  Care）”＊”に変換する。ドントケア“＊”は“０”および“１”のどちらでも良いことを示す。データ変換装置は、変換されたエンコードデータ１３２を、ＴＣＡＭに格納する。したがって、実施形態に従うデータ変換装置は、２つの文字列から構成される論理和のルールに対して、１つのエントリデータをＴＣＡＭに格納する。実施形態に従うデータ変換装置は、関連技術に従うデータ変換装置よりも、ルールを格納するために使用するＴＣＡＭのエントリ数を低減できる。以下、このデータ変換装置についての構成および制御について説明する。
【００１８】
［実施形態１］
図２は、実施形態１に従う検索システム２００の構成例について説明する図である。検索システム２００は、ＴＣＡＭ装置２１０と、入力Ｉ／Ｆ２２０と、ライトデータ変換回路２３０と、サーチデータ変換回路２４０と、ＣＰＵ（Central  Processing  Unit）２５０とを備える。
【００１９】
ＴＣＡＭ装置２１０は、３値以上を保持可能なＴＣＡＭセルを含む。このＴＣＡＭセルを含むＴＣＡＭ装置２１０の構成は、図３〜図６を用いて後述される。
【００２０】
入力Ｉ／Ｆ２２０は、ライトデータ変換回路２３０、サーチデータ変換回路２４０、およびＣＰＵ２５０に情報を入力するための装置である。一例として、入力Ｉ／Ｆ２２０は、キーボード、マウス、タッチパネル等のデバイスによって実現され得る。ユーザは、入力Ｉ／Ｆ２２０を介して、ＴＣＡＭ装置２１０に格納するためのルール（マッチ条件）、および検索条件を入力し得る。
【００２１】
ライトデータ変換回路２３０は、入力された正規表現に従うルールを、ＴＣＡＭ装置２１０に格納するためのエントリデータに変換する。ＴＣＡＭ装置２１０は、変換されたエントリデータを格納する。
【００２２】
サーチデータ変換回路２４０は、入力された検索条件を、ＴＣＡＭ装置２１０で検索可能なサーチデータ（検索キー）に変換する。ＴＣＡＭ装置２１０は、サーチデータと、エントリデータとをビットごとに比較して、サーチ結果をＣＰＵ２５０に出力する。
【００２３】
ＣＰＵ２５０は、ＴＣＡＭ装置２１０、入力Ｉ／Ｆ２２０、ライトデータ変換回路２３０、およびサーチデータ変換回路２４０とそれぞれ電気的に接続される。ＣＰＵ２５０は、これらデバイスの動作を制御する。
【００２４】
（ＴＣＡＭセルの構成）
図３は、実施形態１に従うＴＣＡＭ装置２１０に含まれるＴＣＡＭセルの構成例を説明する図である。図３を参照して、ＴＣＡＭセル（メモリセルＭＣとも称する）は、２個のＳＲＡＭセル（Static  Random  Access  Memory  Cell）１１，１２と、データ比較部１３とを含む。ＳＲＡＭセル１１をＸセルとも称し、ＳＲＡＭセル１２をＹセルとも称する。Ｘセル１１は、内部の記憶ノード対ＮＤ１，ＮＤ１＿ｎに互いに相補となる（一方が“１”のとき他方が“０”となる）１ビット（ｂｉｔ）のデータを記憶する。Ｙセル１２は、内部の記憶ノード対ＮＤ２，ＮＤ２＿ｎに互いに相補となる１ビットのデータを記憶する。
【００２５】
ＴＣＡＭセルは、ビット線対ＢＬ，ＢＬ＿ｎ、サーチ線対ＳＬ，ＳＬ＿ｎ、マッチ線ＭＬ、およびワード線ＷＬＸ，ＷＬＹと接続される。ビット線対ＢＬ，ＢＬ＿ｎは、図５のＴＣＡＭセルアレイ２０の列方向（Ｙ方向）に延在し、列方向に配列された複数のＴＣＡＭセルによって共有される。サーチ線対ＳＬ，ＳＬ＿ｎは、ＴＣＡＭセルアレイ２０の列方向（Ｙ方向）に延在し、列方向に配列された複数のＴＣＡＭセルによって共有される。マッチ線ＭＬは、ＴＣＡＭセルアレイ２０の行方向（Ｘ方向）に延在し、行方向に配列された複数のＴＣＡＭセルによって共有される。ワード線ＷＬＸ，ＷＬＹは、ＴＣＡＭセルアレイ２０の行方向（Ｘ方向）に延在し、行方向に配列された複数のＴＣＡＭセルによって共有される。
【００２６】
Ｘセル１１は、インバータＩＮＶ１，ＩＮＶ２と、ＮチャネルＭＯＳ（Metal  Oxide  Semiconductor）トランジスタＱ１，Ｑ２とを含む。インバータＩＮＶ１は、記憶ノードＮＤ１＿ｎから記憶ノードＮＤ１へ向かう方向が順方向となるように、記憶ノードＮＤ１と記憶ノードＮＤ１＿ｎの間に接続される。インバータＩＮＶ２は、ＩＮＶ１と並列かつ逆方向に接続される。ＭＯＳトランジスタＱ１は、記憶ノードＮＤ１とビット線ＢＬとの間に接続される。ＭＯＳトランジスタＱ２は、記憶ノードＮＤ１＿ｎとビット線ＢＬ＿ｎとの間に接続される。ＭＯＳトランジスタＱ１，Ｑ２のゲートは、ワード線ＷＬＸと接続される。
【００２７】
Ｙセル１２は、インバータＩＮＶ３，ＩＮＶ４と、ＭＯＳ（Metal Oxide Semiconductor）トランジスタＱ３，Ｑ４とを含む。インバータＩＮＶ３は、記憶ノードＮＤ２＿ｎから記憶ノードＮＤ２に向かう方向が順方向となるように、記憶ノードＮＤ２と記憶ノードＮＤ２＿ｎの間に接続される。インバータＩＮＶ４は、ＩＮＶ３と並列かつ逆方向に接続される。ＭＯＳトランジスタＱ３は、記憶ノードＮＤ２とビット線ＢＬとの間に接続される。ＭＯＳトランジスタＱ４は、記憶ノードＮＤ２＿ｎとビット線ＢＬ＿ｎとの間に接続される。ＭＯＳトランジスタＱ３，Ｑ４のゲートは、ワード線ＷＬＹと接続される。
【００２８】
データ比較部１３は、ＮチャネルＭＯＳトランジスタＱ６〜Ｑ９を含む。ＭＯＳトランジスタＱ６，Ｑ７はマッチ線ＭＬとの接続点であるノードＮＤ３と接地ノードＧＮＤとの間に直列に接続される。ＭＯＳトランジスタＱ８，Ｑ９は、ノードＮＤ３と接地ノードＧＮＤとの間に直列に、かつ、直列接続されたＭＯＳトランジスタＱ６，Ｑ７の全体と並列に接続される。ＭＯＳトランジスタＱ６，Ｑ８のゲートは、記憶ノードＮＤ１，ＮＤ２とそれぞれ接続される。ＭＯＳトランジスタＱ７，Ｑ９のゲートは、サーチ線ＳＬ，ＳＬ＿ｎとそれぞれ接続される。
【００２９】
図４は、図３のＸセルおよびＹセルの記憶内容とＴＣＡＭセルデータとの対応関係を表形式で示す図である。
【００３０】
図３および図４を参照して、ＴＣＡＭセルは、２ビットのＳＲＡＭセルを用いて、“０”、“１”、“＊”（ドントケア：don't care）の３値を格納することができる。具体的に、Ｘセル１１の記憶ノードＮＤ１に“１”が格納され、Ｙセル１２の記憶ノードＮＤ２に“０”が格納されているとき、ＴＣＡＭセルには“０”が格納されているとする。Ｘセル１１の記憶ノードＮＤ１に“０”が格納され、Ｙセル１２の記憶ノードＮＤ２に“１”が格納されているとき、ＴＣＡＭセルには“１”が格納されているとする。Ｘセル１１の記憶ノードＮＤ１に“０”が格納され、Ｙセル１２の記憶ノードＮＤ２に“０”が格納されているとき、ＴＣＡＭセルには“＊”（ドントケア）が格納されているとする。Ｘセル１１の記憶ノードＮＤ１に“１”が格納され、Ｙセル１２の記憶ノードＮＤ２に“１”が格納されている場合は使用しない。
【００３１】
上記のＴＣＡＭセルの構成によれば、サーチデータが“１”（すなわち、サーチ線ＳＬが“１”、かつ、サーチ線ＳＬ＿ｎが“０”）であり、ＴＣＡＭデータが“０”（記憶ノードＮＤ１が“１”、かつ、記憶ノードＮＤ２が“０”）である場合には、ＭＯＳトランジスタＱ６，Ｑ７がオン状態となるために、プリチャージされたマッチ線ＭＬの電位が接地電位まで引き抜かれる。サーチデータが“０”（すなわち、サーチ線ＳＬが“０”、かつ、サーチ線ＳＬ＿ｎが“１”）であり、ＴＣＡＭデータが“１”（記憶ノードＮＤ１が“０”、かつ、記憶ノードＮＤ２が“１”）である場合には、ＭＯＳトランジスタＱ８，Ｑ９がオン状態となるために、プリチャージされたマッチ線ＭＬの電位が接地電位まで引き抜かれる。すなわち、サーチデータとＴＣＡＭデータとが不一致の場合には、マッチ線ＭＬの電位は接地電位まで引き抜かれる。
【００３２】
逆に、入力されたサーチデータが“１”であり、かつ、ＴＣＡＭデータが“１”または“＊”の場合、もしくは、サーチデータが“０”であり、かつ、ＴＣＡＭデータが“０”または“＊”の場合（すなわち、両者が一致する場合）、プリチャージされたマッチ線ＭＬの電位（電源電位ＶＤＤレベル）は維持される。
【００３３】
上記のように、ＴＣＡＭセルでは、１つのエントリ（行）に対応するマッチ線ＭＬに接続された全てのＴＣＡＭセルのデータが入力サーチデータと一致しない限り、マッチ線ＭＬに蓄えられた電荷が引き抜かれる。
【００３４】
（サブアレイの構成）
図５は、ＴＣＡＭ装置２１０を構成する１つのサブアレイの構成を示すブロック図である。図５を参照して、サブアレイＳＡは、ＴＣＡＭセルアレイ２０（単にセルアレイとも称する）と、書込みドライバ２１と、サーチ線（ＳＬ）ドライバ２２と、マッチアンプ部２３と、制御論理回路２４とを含む。サブアレイＳＡは、さらに、図３のワード線ＷＬＸ，ＷＬＹを駆動するためのワード線ドライバ（不図示）を含む。
【００３５】
セルアレイ２０は、行列状（ｍ行；ｋ列）に配列されたＴＣＡＭセルを含む。図５に示される例において、セルアレイ２０は、行数（エントリ数）ｍが２５６であり、列数（ビット数）ｋが８である。
【００３６】
セルアレイ２０の各列に対応して、ｋ個（ｋ＝８）のビット線対（ＢＬ［０］，ＢＬ＿ｎ［０］からＢＬ［ｋ−１］，ＢＬ＿ｎ［ｋ−１］まで）と、ｋ個（ｋ＝８）のサーチ線対（ＳＬ［０］，ＳＬ＿ｎ［０］からＳＬ［ｋ−１］，ＳＬ＿ｎ［ｋ−１］まで）とが設けられる。セルアレイ２０の各行に対応して、ｍ本（ｍ＝２５６）のマッチ線（ＭＬ［０］からＭＬ［ｍ−１］まで）と、図示しないｍ本のＸセル用のワード線（ＷＬＸ［０］からＷＬＸ［ｍ−１］まで）と、図示しないｍ本のＹセル用のワード線（ＷＬＹ［０］からＷＬＹ［ｍ−１］まで）とが設けられている。
【００３７】
書込みドライバ２１は、書込み時に、ビット線対ＢＬ，ＢＬ＿ｎを介して各ＴＣＡＭセルに書込みデータを供給する。サーチ線ドライバ２２は、検索時に、サーチ線対ＳＬ，ＳＬ＿ｎを介して各ＴＣＡＭセルにサーチデータを供給する。制御論理回路２４は、サブアレイＳＡ全体の動作を制御する。例えば、制御論理回路２４は、検索時には、サーチコマンドを受け取り、サーチ線ドライバ２２と、マッチアンプ部２３に制御信号を出力することによって、サーチ線ドライバ２２、マッチアンプ部２３、およびプリチャージ回路の動作を制御する。
【００３８】
マッチアンプ部２３は、セルアレイの行にそれぞれ対応する複数のマッチアンプＭＡを含む。マッチアンプＭＡは、検索時に、対応するマッチ線ＭＬの電位に基づいて、対応するＴＣＡＭセルデータと入力サーチデータの対応部分とが一致するか否かを検出する。この実施形態では、マッチアンプＭＡは、検索時に対応するマッチ線ＭＬをプリチャージするためのプリチャージ回路を含む。
【００３９】
（ＴＣＡＭ装置２１０の構成）
図６は、ＴＣＡＭ装置２１０の構成を示すブロック図である。図６を参照して、ＴＣＡＭ装置２１０は、行列状に配列された複数のサブアレイＳＡと、プライオリティ・エンコーダ３０と、データ入力回路３１と、コマンド入力回路３２とを含む。
【００４０】
図６に示されている例において、ＴＣＡＭ装置２１０が実現している検索テーブルサイズは、１エントリ（１行）のビット長が３２ビット（ｂｉｔ）であり、総エントリ数が４０９６エントリ（entry）である。ＴＣＡＭ装置２１０は、１６行４列のサブアレイＳＡ［０，０］〜ＳＡ［１５，３］に分割されている。各サブアレイＳＡのサイズは、総エントリ数は２５６エントリ、１エントリのビット長は８ビットになる。なお、これらの数字は一例であって、ＴＣＡＭ装置２１０の構成はこれに限られるものでない。
【００４１】
すでに説明したサーチ線対ＳＬ，ＳＬ＿ｎ、ビット線対ＢＬ，ＢＬ＿ｎ、マッチ線ＭＬ、およびワード線は、各サブアレイごとに配設されている。例えば、サブアレイＳＡ［０，０］には、サーチ線対ＳＬ［０］，ＳＬ＿ｎ［０］からサーチ線対ＳＬ［７］，ＳＬ＿ｎ［７］までが設けられる。サブアレイＳＡ［０，１］には、サーチ線対ＳＬ［８］，ＳＬ＿ｎ［８］からサーチ線対ＳＬ［１５］，ＳＬ＿ｎ［１５］までが設けられる。サブアレイＳＡ［０，２］には、サーチ線対ＳＬ［１６］，ＳＬ＿ｎ［１６］からサーチ線対ＳＬ［２３］，ＳＬ＿ｎ［２３］までが設けられる。サブアレイＳＡ［０，３］には、サーチ線対ＳＬ［２４］，ＳＬ＿ｎ［２４］からサーチ線対ＳＬ［３１］，ＳＬ＿ｎ［３１］までが設けられる。
【００４２】
図６において、１エントリのサーチデータ全体および１エントリのＴＣＡＭセルデータ（書込みデータ）全体に対して、マッチ線ＭＬは８ビット単位で４分割された構成になっている。このため、マッチアンプ部２３には、各マッチアンプＭＡの検出結果の論理積をとるためのＡＮＤゲート（不図示）が行ごとに設けられている。
【００４３】
データ入力回路３１は、データ書込み時には、エントリデータをライトデータ変換回路２３０から受信し、受信した書込みデータを対応するサブアレイのＳＡの書込みドライバ２１に出力する。データサーチ時には、サーチデータをサーチデータ変換回路２４０から受信し、受信したサーチデータを対応するサブアレイＳＡのサーチ線ドライバ２２に出力する。
【００４４】
コマンド入力回路３２は、書込みコマンド、サーチコマンドなどの各種コマンドをＣＰＵ２５０から受信し、受信したコマンドを対応するサブアレイＳＡの制御論理回路２４に出力する。
【００４５】
プライオリティ・エンコーダ３０は、エントリごとのサーチ結果（入力されたサーチデータとＴＣＡＭデータとが一致したか否か）を隣接するサブアレイＳＡ［０，３］，ＳＡ［１，３］，…，ＳＡ［１５，３］から受け取る。プライオリティ・エンコーダ３０は、複数のエントリがヒット（一致）した場合には、優先度の高いヒットエントリのアドレスを出力する。以上のようにして、ＴＣＡＭ装置２１０は動作する。次に、図７〜１３を用いてライトデータ変換回路２３０の構成について説明する。
【００４６】
（ライトデータ変換回路２３０の構成および制御）
図７は、実施形態１に従うライトデータ変換回路２３０の構成例について説明する図である。図７を参照して、ライトデータ変換回路２３０は、文字列抽出変換回路７１０と、文字列レジスタ７２０と、比較変換回路７３０と、エンコード回路７４０と、セレクタ回路７７０とを備える。エンコード回路７４０は、第１エンコード回路７５０と、第２エンコード回路７６０とを含む。一例として、図８〜１３を用いて、論理和の正規表現を含むルール「ＪＡＮ｜ＦＥＢ｜ＭＡＲ｜ＡＰＲ｜ＭＡＹ｜ＪＵＮ｜ＪＵＬ｜ＡＵＧ｜ＳＥＰ｜ＯＣＴ｜ＮＯＶ｜ＤＥＣ」が文字列抽出変換回路７１０に入力された場合の、各デバイスの動作について説明する。
【００４７】
図８は、実施形態１に従う文字列抽出変換回路７１０の動作について説明する図である。図７および８を参照して、文字列抽出変換回路７１０は、入力Ｉ／Ｆ２２０を介して正規表現に従うルール（マッチ条件）を入力される。文字列抽出変換回路７１０は、ルールから文字列を抽出して、抽出した文字列をビットデータ７１２に変換する。文字列抽出変換回路７１０は、変換したビットデータ７１２を、文字列レジスタ７２０と、比較変換回路７３０と、セレクタ回路７７０とに出力する。
【００４８】
本例において、文字列抽出変換回路７１０は、入力されたルールから、当該ルールに含まれる正規表現（論理和）に基づいて、複数の文字列「ＪＡＮ」「ＦＥＢ」「ＭＡＲ」「ＡＰＲ」「ＭＡＹ」「ＪＵＮ」「ＪＵＬ」「ＡＵＧ」「ＳＥＰ」「ＯＣＴ」「ＮＯＶ」「ＤＥＣ」を抽出する。文字列抽出変換回路７１０は、これらの文字列を２進数のＡＳＣＩＩ文字コードに変換してビットデータ７１２を生成する。
【００４９】
図９は、実施形態１に従う文字列レジスタ７２０にデータを登録する制御について説明する図である。文字列レジスタ７２０は、登録データレジスタ９２２と、登録コードレジスタ９２４とを含む。登録コードレジスタは、アドレスとして機能する。
【００５０】
図７および９を参照して、文字列抽出変換回路７１０は、変換したビットデータ７１２を登録データレジスタ９２２に格納する。ＣＰＵ２５０は、ライトコマンド７２６を制御することにより、後述するエンコード回路７４０によるエンコードの対象とする文字列（を示すビットデータ）を文字列レジスタ７２０に登録する。一例として、文字列レジスタ７２０は、ＣＰＵ２５０から入力されるライトコマンド７２６が”１”のときに、ライトアドレス７２８に従って、ビットデータ７１２を登録データレジスタ９２２に格納する。このとき、ＣＰＵ２５０は、ビットデータ７１２が連続する登録コード（アドレス）に格納されるようにライトアドレス７２８を出力する。図９の例において、ルール「ＪＡＮ｜ＦＥＢ｜・・・｜ＤＥＣ」に含まれる最初の文字列「ＪＡＮ」に対応するビットデータ７１２が、登録コードレジスタ９２４のアドレス「０００００」に格納される。文字列「ＪＡＮ」の次の文字列「ＦＥＢ」に対応するビットデータ７１２が、登録コードレジスタ９２４のアドレス「００００１」に格納される。
【００５１】
文字列レジスタ７２０は、登録データレジスタ９２２の各アドレスに格納される複数の登録データ７２２と、登録コードレジスタ９２４に格納される複数の登録コード７２４とを関連付けて格納する。
【００５２】
図１０は、実施形態１に従う比較変換回路７３０の動作について説明する図である。図７および１０を参照して、比較変換回路７３０は、文字列抽出変換回路７１０から入力されるビットデータ７１２を、登録コード７３２に変換してエンコード回路７４０に出力する。また、比較変換回路７３０は、ビットデータ７１２と、複数の登録データ７２２とを比較して、比較結果を示すセレクタ信号７３４をセレクタ回路７７０に出力する。
【００５３】
比較変換回路７３０は、文字列抽出変換回路７１０から入力されるビットデータ７１２と、文字列レジスタ７２０から入力される複数の登録データ７２２とを比較する。比較変換回路７３０は、ビットデータ７１２が複数の登録データ７２２のいずれかに一致する場合、一致した登録データ７２２に関連付けられた登録コード７２４（７３２）をエンコード回路７４０に出力する。
【００５４】
本例において、登録データレジスタ９２２には、「ＪＡＮ」「ＦＥＢ」・・・「ＤＥＣ」の文字列に対応するビットデータが格納されているものとする。この場合、比較変換回路７３０は、これらの文字列に対応するビットデータ７１２の各々が、複数の登録データ７２２のいずれかと一致すると判断する。これにより、比較変換回路７３０は、一致した登録データ７２２に関連付けられた登録コード７２４「０００００」「００００１」・・・「０１０１１」を、登録コード７３２としてエンコード回路７４０に出力する。また、比較変換回路７３０は、入力されるビットデータ７１２と、複数の登録データ７２２との比較結果（一致）を示すセレクタ信号７３４をセレクタ回路７７０に出力する。なお、図９で説明した通り、一致した登録データ７２２に関連付けられた登録コード７２４は、連続した数字（２進数）である。
【００５５】
他の局面において、仮に文字列「ＳＵＮ」に対応するビットデータ７１２が入力された場合、比較変換回路７３０は、このビットデータ７１２と一致する登録データ７２２ないと判断して、登録コード７３２を出力しない。比較変換回路７３０は、入力されるビットデータ７１２と、複数の登録データ７２２との比較結果（不一致）を示すセレクタ信号７３４をセレクタ回路７７０に出力する。
【００５６】
図１１は、実施形態１に従う第１エンコード回路７５０の動作について説明する図である。第１エンコード回路７５０は、比較変換回路７３０から入力される登録コード７３２を、予め定められた方式に従ってエンコードする。
【００５７】
図１１に示される例において、第１エンコード回路７５０は、登録コードが示す数字（２進数）に応じて、下位のビットから順に”１”を立てるようにエンコードデータを生成する。一例として、エンコードデータは、３１ビットで構成される。例えば、第１エンコード回路７５０は、文字列「ＡＰＲ」に対応する登録コード「０００１１」（１０進数の３）を、「０００００００＿００００００００＿００００００００＿０００００１１１」にエンコードする。なお、他の局面において第１エンコード回路７５０は、他の方式（たとえば、ワンホットエンコーディング）に従って登録コードをエンコードしてもよい。
【００５８】
第１エンコード回路７５０は、入力される複数の登録コード７３２のうち、最小値および最大値の登録コードをエンコードする。本例において、文字列「ＪＡＮ」「ＦＥＢ」・・・「ＤＥＣ」に関連付けられた登録コード「０００００」「００００１」・・・「０１０１１」が第１エンコード回路７５０に入力される。これに応じて、第１エンコード回路７５０は、最小値「０００００」と最大値「０１０１１」とをエンコードした２つの第１エンコードデータ７５２を第２エンコード回路７６０に出力する。
【００５９】
このとき、２つの第１エンコードデータ「０００００００＿００００００００＿００００００００＿００００００００」「０００００００＿００００００００＿０００００１１１＿１１１１１１１１」には、上位１ビット目から２０ビット目まで、共通するビットデータ（以下、「共通ビットデータ」とも称する）が含まれる。この共通ビットデータは、ルールに含まれる複数の文字列に共通するカテゴリを示すビットデータとして機能する。ルール「ＪＡＮ｜ＦＥＢ｜・・・｜ＤＥＣ」が文字列抽出変換回路７１０に入力された場合、共通ビットデータは、当該ルールに含まれる複数の文字列に共通する「月」を示す。
【００６０】
図１２は、実施形態１に従う第２エンコード回路７６０の動作について説明する図である。図７および１２を参照して、第２エンコード回路７６０は、第１エンコード回路７５０から入力される２つの第１エンコードデータ７５２を比較して、第２エンコードデータ７６２を生成する。より具体的には、第２エンコード回路７６０は、一方の第１エンコードデータ７５２を、他方の第１エンコードデータ７５２とビットごとに比較して、不一致のビットをドントケア”＊”に変換する。第２エンコード回路７６０は、生成した第２エンコードデータ７６２をセレクタ回路７７０に出力する。
【００６１】
本例において、第１エンコードデータ「０００００００＿００００００００＿００００００００＿００００００００」と、「０００００００＿００００００００＿０００００１１１＿１１１１１１１１」とが第２エンコード回路７６０に入力される。この場合、第２エンコード回路７６０は、これら２つの第１エンコードデータ７５２の下位１１ビットが不一致であるとして、第２エンコードデータ７６２「０００００００＿００００００００＿０００００＊＊＊＿＊＊＊＊＊＊＊＊」を生成する。
【００６２】
図１３は、実施形態１に従うセレクタ回路７７０の動作例について説明する図である。図７および１３を参照して、セレクタ回路７７０は、ビットデータ７１２と、第２エンコードデータ７６２のうち、いずれか一方のデータをセレクタ信号７３４に従って出力する。実施形態１において、比較変換回路７３０は、入力されるビットデータ７１２が複数の登録データ７２２のいずれかと一致したと判断した場合”１”のセレクタ信号７３４をセレクタ回路７７０に出力する。比較変換回路７３０は、入力されるビットデータ７１２が複数の登録データ７２２のいずれとも一致しない場合、”０”のセレクタ信号７３４をセレクタ回路７７０に出力する。セレクタ回路７７０は、”１”のセレクタ信号７３４が入力された場合、第２エンコードデータ７６２をエントリデータ７８０としてＴＣＡＭ装置２１０に出力する。一方、”０”のセレクタ信号７３４が入力された場合、セレクタ回路７７０は、ビットデータ７１２をエントリデータ７８０としてＴＣＡＭ装置２１０に出力する。
【００６３】
ＴＣＡＭ装置２１０は、１エントリを構成するＴＣＡＭセルにエントリデータ７８０を格納する。なお、本例において、ＴＣＡＭ装置２１０の１エントリは３２ビットであるのに対して、ビットデータ７１２は２４ビット、第２エンコードデータ７６２は３１ビットである。そのため、ある局面において、ＴＣＡＭ装置２１０は、ビットデータ７１２に８ビットの”＊”を、第２エンコードデータ７６２に１ビットの”＊”を追加して１エントリを構成するＴＣＡＭセルに格納する。これにより、ＴＣＡＭ装置２１０に格納されるエントリデータのビット長が揃う。そのため、ＴＣＡＭ装置２１０は、入力される検索キーに対して特別な処理を行なわなくとも、検索キーとエントリデータとを比較できる。
【００６４】
上記によれば、実施形態１に従うライトデータ変換回路２３０は、ルールを格納するために使用するＴＣＡＭのエントリ数を低減できる。例えば、ライトデータ変換回路２３０は、論理和の正規表現を含むルール「ＪＡＮ｜ＦＥＢ｜・・・｜ＤＥＣ」を、１つのエントリデータとして表現する。これにより、ＴＣＡＭ装置２１０は、より多くのルールをＴＣＡＭセルに格納できる。
【００６５】
また、ライトデータ変換回路２３０は、論理和の正規表現を含むルールに含まれる複数の文字列を連続する数字の登録コードに変換し、当該登録コードの最小値と最大値に応じた数だけ”１”のビットを含む２つの第１エンコードデータ７５２を生成する。これにより、ライトデータ変換回路２３０は、ルールに含まれる複数の文字列を全て包含したエントリデータ７８０（第２エンコードデータ７６２）を生成できる。なお、図１で説明したように、登録コードの最小値と最大値を用いない場合であっても、ライトデータ変換回路２３０は、少なくとも２つの文字列を１つのエントリデータとして表現できる。
【００６６】
加えて、ライトデータ変換回路２３０は、ＴＣＡＭ装置２１０とは独立した回路であるため、実施形態１に従う検索システムは、ＴＣＡＭ装置２１０として汎用的なＴＣＡＭを用いることができる。そのため、この検索システムは、ＴＣＡＭのコストを抑制できる。
【００６７】
なお、他の局面において、エンコード回路７４０は、入力される登録コードを３つ以上第１エンコードデータにエンコードし、ある１つの第１エンコードデータと他の複数の第１エンコードデータ７５２とをビットごとに比較して、いずれかと不一致であるビットを”＊”に変換して第２エンコードデータを生成し得る。
【００６８】
例えば、エンコード回路７４０は、入力される複数の登録コード７３２「０００００」「００００１」・・・「０１０１１」を全て第１エンコードデータ７５２に変換し得る。この場合、エンコード回路７４０は、ある１つの第１エンコードデータと他の複数の第１エンコードデータ７５２とをビットごとに比較して、いずれかと不一致であるビットを”＊”に変換した第２エンコードデータ７６２「０００００００＿００００００００＿０００００＊＊＊＿＊＊＊＊＊＊＊＊」を生成し得る。
【００６９】
（サーチデータ変換回路２４０の構成および制御）
図１４は、実施形態１に従うサーチデータ変換回路２４０の構成例について説明する図である。サーチデータ変換回路２４０は、文字列変換回路１４１０と、文字列レジスタ１４２０と、比較変換回路１４３０と、エンコード回路１４４０と、セレクタ回路１４７０とを備える。文字列変換回路１４１０、文字列レジスタ１４２０、比較変換回路１４３０、エンコード回路１４４０、およびセレクタ回路１４７０はそれぞれ、図７で説明した文字列抽出変換回路７１０、文字列レジスタ７２０、比較変換回路７３０、第１エンコード回路７５０、セレクタ回路７７０と略同じ動作を行なうため、その詳細な動作については繰り返し説明しない。
【００７０】
文字列変換回路１４１０は、入力された検索条件としての文字列を、文字列抽出変換回路７１０と同様に２進数のビットデータ１４１２に変換し、比較変換回路１４３０と、セレクタ回路１４７０とに出力する。
【００７１】
文字列レジスタ１４２０は、文字列レジスタ７２０に格納されるデータと同じデータを格納する。すなわち、文字列レジスタ１４２０に格納される登録データ１４２２および登録コード１４２４は、文字列レジスタ７２０に格納される登録データ９２２および登録コード９２４とそれぞれ同一データである。文字列レジスタ１４２０は、登録データ１４２２と当該データに関連付けられた登録コード１４２４とを格納する。なお、他の局面において、文字列レジスタ７２０および文字列レジスタ１４２０は、同一レジスタであってもよい。
【００７２】
比較変換回路１４３０は、入力されたビットデータ１４１２が複数の登録データ１４２２のいずれかに一致する場合、一致した登録データ１４２２に関連付けられた登録コード１４２４（１４３２）をエンコード回路１４４０に出力する。
【００７３】
また、比較変換回路１４３０は、入力されるビットデータ１４１２が複数の登録データ１４２２のいずれかと一致したか否かを示すセレクタ信号１４３４をセレクタ回路１４７０に出力する。
【００７４】
エンコード回路１４４０は、入力された登録コード１４３２を、第１エンコード回路７５０が実行するエンコード方式と同じ方式に従ってエンコードする。エンコード回路１４４０は、登録コード１４３２をエンコードして生成したエンコードデータ１４４２をセレクタ回路１４７０に出力する。
【００７５】
セレクタ回路１４７０は、一致を示すセレクタ信号１４３４が入力された場合、エンコードデータ１４４２をサーチデータ１４８０としてＴＣＡＭ装置２１０に出力する。一方、不一致を示すセレクタ信号１４３４が入力された場合、セレクタ回路１４７０は、ビットデータ１４１２をサーチデータ１４８０としてＴＣＡＭ装置２１０に出力する。
【００７６】
具体例を用いて上記の動作を説明する。一例として、「ＦＥＢ」の文字列（検索条件）が文字列変換回路１４１０に入力されたとする。文字列レジスタ１４２０には、文字列「ＪＡＮ」「ＦＥＢ」・・・「ＤＥＣ」に対応する登録データ１４２２と、当該データに関連付けられた登録コード１４２４とが格納されているものとする。
【００７７】
文字列変換回路１４１０は、検索条件「ＦＥＢ」を２進数のＡＳＣＩＩ文字コードに変換して、ビットデータ「０１０００１１０＿０１００００１０１＿０１００００１０」を得る。比較変換回路１４３０は、複数の登録データ１４２２の中に、上記ビットデータと一致する登録データがあると判断して、当該登録データに関連付けられた登録コード「００００１」をエンコード回路１４４０に出力する。また、比較変換回路１４３０は、一致を示すセレクタ信号１４３４をセレクタ回路１４７０に出力する。
【００７８】
エンコード回路１４４０は、図１１に示される第１エンコード回路７５０のエンコード方式に従い、登録コード「００００１」を「０００００００＿００００００００＿００００００００＿０００００００１」にエンコードして、当該データをセレクタ回路１４７０に出力する。
【００７９】
セレクタ回路１４７０は、一致を示すセレクタ信号１４３４に従い、エンコードデータ「０００００００＿００００００００＿００００００００＿０００００００１」をサーチデータ１４８０（検索キー）としてＴＣＡＭ装置２１０に出力する。
【００８０】
ＴＣＡＭ装置２１０には、サーチデータが「ＪＡＮ」「ＦＥＢ」・・・「ＤＥＣ」のいずれかであることを示すエントリデータ「０００００００＿００００００００＿０００００＊＊＊＿＊＊＊＊＊＊＊＊」が格納されている。そのため、ＴＣＡＭ２１０は、入力されたサーチデータ「０００００００＿００００００００＿００００００００＿０００００００１」がＨｉｔしたこと、および上記エントリデータが格納されるアドレス情報をサーチ結果としてＣＰＵ２５０に出力する。
【００８１】
上記によれば、検索システム２００は、複数の文字列を含むルールを共通ビットデータを含むエントリデータに変換してＴＣＡＭセルに格納する。これにより、検索システム２００は、ルールを格納するために使用するＴＣＡＭのエントリ数を低減できる。
【００８２】
また、検索システム２００は、予め登録されている文字列と一致する検索条件（文字列）を、上記共通ビットデータを含むようにサーチデータを生成する。これにより、検索システム２００は、少ないエントリ数で、検索条件に含まれる文字列が、共通ビットが示すカテゴリに含まれることを判断（検索）できる。これにより、例えば、検索システム２００は、検索条件に含まれる文字列がどのようなカテゴリに属するのかを、少ないエントリ数で判断することができる。ある局面において、検索システム２００は、検索条件に含まれる文字列が属するカテゴリに関連する情報をディスプレイ（不図示）に表示する構成であってもよい。
【００８３】
［実施形態２］
実施形態１の第１エンコード回路７５０は、登録コードが示す数字（２進数）の大きさに応じて、下位のビットから順に”１”を立てるようにエンコードデータを生成する構成であった。この構成において、生成されるエンコードデータのビット長が３１ビットであるため、文字列レジスタ７２０（および１４２０）に登録できる文字列の数は３２個である。
【００８４】
実施形態２に従う検索システムは、実施形態１に従うシステムに対してエンコードデータのビット長を変えずに、文字列レジスタに登録できる文字列の数を増やす。以下、その構成について説明する。なお、実施形態２に従う検索システムの基本構成は、実施形態１に従う検索システムと略同じであるため、相違する点についてのみ説明する。
【００８５】
図１５は、実施形態２に従う第１エンコード回路１５５０について説明する図である。実施形態２に従うライトデータ変換回路２３０は、実施形態１に従う第１エンコード回路７５０に替えて第１エンコード回路１５５０を備える。
【００８６】
実施形態１に従う文字列レジスタは、５ビットの登録コードを格納する。これに対して実施形態２に従う文字列レジスタ７２０および１４２０は、８ビットの登録コードを格納する。換言すれば、実施形態２に従う文字列レジスタは、登録データを８ビットのアドレスと関連付けて格納する。
【００８７】
第１エンコード回路１５５０には、第１エンコード回路７５０と同様に、登録コードが示す数字（２進数）の大きさに応じて、下位のビットから順に”１”を立てるように第１エンコードデータ１５５２を生成する。加えて、第１エンコード回路１５５０は、３１ビットのエンコードデータのうち、上位７ビットを、下位２４ビットが全て”１”になったときの桁上がりビットとして扱う。
【００８８】
具体例を用いて説明する。第１エンコード回路１５５０は、登録コード「０００１＿１００１」（１０進数の２５）を、下位２４ビット全てが”１”である第１エンコードデータ１５５２に変換する。第１エンコード回路１５５０は、次の登録コード「０００１＿１０１０」（１０進数の２６）を、下位２４ビットが全て”０”であって、２５ビット目が”１”である第１エンコードデータ１５５２に変換する。
【００８９】
第１エンコード回路１５５０は、登録コード「００１１＿００１０」（１０進数の５０）を、下位２４ビットが全て”１”であって、２５ビット目が”１”である第１エンコードデータ１５５２に変換する。第１エンコード回路１５５０は、次の登録コード「００１１＿００１１」（１０進数の５１）を、下位２４ビットが全て”０”であって、２５および２６ビット目が”１”である第１エンコードデータ１５５２に変換する。
【００９０】
上記によれば、実施形態２に従う第１エンコード回路１５５０は、生成する３１ビットの第１エンコードデータ１５５２を、上位７ビットと下位２４ビットに分けて扱うことによって、最大２００（＝（７＋１）×（２４＋１））通りのエンコードデータを生成できる。換言すれば、実施形態２に従う検索システムは、第１エンコードデータのビット長を増やさずに、文字列レジスタに登録できる文字列の数を実施形態１に従うシステムよりも増やすことができる。
【００９１】
なお、上記の例では第１エンコードデータ１５５２は、上位７ビットと下位２４ビットに分かれているが、他の局面において、この割合は任意に設定され得る。一例として、第１エンコードデータ１５５２の上位をＭビット、下位をＮビットに設定した場合、文字列レジスタに登録できる文字列の数は、（Ｍ＋１）×（Ｎ＋１）となる。
【００９２】
さらに他の局面において、第１エンコードデータ１５５２は、３つ以上に分けて扱われてもよい。一例として、第１エンコードデータ１５５２の上位をＫビット、中位をＭビット、下位をＮビットに設定した場合、文字列レジスタに登録できる文字列の数は、（Ｋ＋１）×（Ｍ＋１）×（Ｎ＋１）となる。
【００９３】
図７を参照して、実施形態２に従うライトデータ変換回路２３０を用いてＴＣＡＭ装置２１０にエントリデータを格納する例について説明する。文字列抽出変換回路７１０に、論理和の正規表現に従うルール「ＵＳＡ｜ＣＨＮ｜・・・｜ＪＰＮ」（国名を表す１００個の３文字）が入力されたとする。また、ＣＰＵ２５０は、”１”のライトコマンド７２６を文字列レジスタ７２０に出力して、文字列レジスタ７２０へのビットデータ７１２の登録（書き込み）を有効化する。このとき、文字列レジスタ７２０に登録される「ＵＳＡ」「ＣＨＮ」・・・「ＪＰＮ」の登録コード７２４は「１０１」「１０２」・・・「２００」を２進数で表したビットデータとする。
【００９４】
かかる場合、エンコード回路１５５０は、登録コードのうち最小値「１０１」および最大値「２００」を、第１エンコードデータ１５５２として「０００１１１１＿００００００００＿００００００００＿００００００００」および「１１１１１１１＿１１１１１１１１＿１１１１１１１１＿１１１１１１１１」にそれぞれ変換する。このとき、各第１エンコードデータ１５５２には、２５〜２８ビット目に、共通ビット「１１１１」が含まれる。
【００９５】
第２エンコード回路７６０は、一方の第１エンコードデータ１５５２と、他方の第１エンコードデータ１５５２とをビットごとに比較して、いずれか一方のビットデータを構成するビットのうち、不一致のビットをドントケア”＊”に変換する。これにより、第２エンコード回路７６０は第２エンコードデータ７６２として「＊＊＊１１１１＿＊＊＊＊＊＊＊＊＿＊＊＊＊＊＊＊＊＿＊＊＊＊＊＊＊＊」を生成してセレクタ回路７７０に出力する。
【００９６】
上記によれば、実施形態２に従うライトデータ変換回路２３０は、ＴＣＡＭ装置２１０に格納するエントリデータのビット長を増やさずに、より多くの文字列を含むルールを、少ないエントリデータとして表現できる。その結果、実施形態２に従う検索システムは、よりルールを格納するために使用するＴＣＡＭのエントリ数を低減できる。
【００９７】
［実施形態３］
実施形態１および２では、論理和の正規表現を含むルールを１つのエントリデータとして表現する構成であった。実施形態３では、繰り返しの正規表現を含むルールを１つのエントリデータとして表現する構成について説明する。実施形態３に従う検索システムは、実施形態１に従うライトデータ変換回路２３０およびサーチデータ変換回路２４０の代わりにライトデータ変換回路１６００およびサーチデータ変換回路２２００を備える。その他の構成については実施形態１に従う検索システムと同じであるので、繰り返し説明しない。
【００９８】
図１６は、実施形態３に従うライトデータ変換回路１６００の構成例について説明する図である。ライトデータ変換回路１６００は、文字列抽出変換回路１６１０と、文字列レジスタ１６２０と、エンコード回路１６４０と、セレクタ回路１６７０とを備える。エンコード回路１６４０は、第１エンコード回路１６５０と、第２エンコード回路１６６０とを含む。一例として、図１７〜２１を用いて、繰り返しの正規表現を含むルール「Ａ｛２，４｝」が文字列抽出変換回路１６１０に入力された場合の、各デバイスの動作について説明する。なお、他の局面において、繰り返しの正規表現として「＊」、「＋」、および「？」が用いられてもよい。
【００９９】
図１７は、実施形態３に従う文字列抽出変換回路１６１０の動作について説明する図である。図１６および１７を参照して、文字列抽出変換回路１６１０は、入力される繰り返しの正規表現を含むルール（マッチ条件）に基づいてビットデータ１６１２を文字列レジスタ１６２０とエンコード回路１６４０とに出力する。また、文字列抽出変換回路１６１０は、入力されるルールから複数の文字列を抽出し、これら文字列を変換した文字列データ１６１４をセレクタ回路１６７０に出力する。
【０１００】
本例において、文字列抽出変換回路１６１０はルール「Ａ｛２，４｝」をビットデータ１６１２として「０１０００００１＿０００１０＿００１００」に変換する。上位８ビットは、繰り返しの対象である文字「Ａ」をＡＳＣＩＩ文字コード（２進数）に変換したものである。中位５ビットは、繰り返しの回数の下限値「２」を２進数に変換したものである。下位５ビットは、繰り返し回数の上限値「４」を２進数に変換したものである。
【０１０１】
また、文字列抽出変換回路１６１０は、ルール「Ａ｛２，４｝」から、当該ルールに含まれる正規表現（繰り返し）に基づいて、複数の文字列「ＡＡ」「ＡＡＡ」「ＡＡＡＡ」を抽出する。文字列抽出変換回路１６１０は、これらの文字列をそれぞれＡＳＣＩＩ文字コード（２進数）に変換して文字列データ１６１４を生成する。
【０１０２】
図１８は、実施形態３に従う文字列レジスタ１６２０の動作を説明する図である。図１６および１８を参照して、文字列抽出変換回路１６１０は、変換したビットデータ１６１２を、文字列レジスタ１６２０に格納する。文字列レジスタ１６２０は、ＣＰＵから入力されるライトコマンド７２６が”１”のときに、ライトアドレス７２８に従ってビットデータ１６１２を格納する。
【０１０３】
図１８に示される例において、文字列レジスタ１６２０には、ルール「Ａ｛２，４｝」、「Ｂ｛１０，２０｝」「Ｃ｛２０，２４｝」に対応するビットデータ１６１２がそれぞれ格納されている。
【０１０４】
図１９は、実施形態３に従う第１エンコード回路１６５０の動作について説明する図である。図１９を参照して、第１エンコード回路１６５０は、入力されるビットデータ１６１２から、２つの変換ビットデータ１６５２を生成する。一方の変換ビットデータ１６５２は、繰り返しの対象である文字を示すビット（上位８ビット）と、繰り返し回数の下限値を示すビット（下位５ビット）とから構成される。他方の変換ビットデータ１６５２は、繰り返しの対象である文字を示すビット（上位８ビット）と、繰り返し回数の上限値を示すビット（下位５ビット）とから構成される。
【０１０５】
本例において、第１エンコード回路１６５０は、ビットデータ「０１０００００１＿０００１０＿００１００」に基づいて、上位８ビットと中位５ビットとから構成される変換ビットデータ「０１０００００１＿０００１０」と、上位８ビットと下位５ビットとから構成される変換ビットデータ「０１０００００１＿００１００」とを生成する。
【０１０６】
第１エンコード回路１６５０は、生成した２つの変換ビットデータ１６５２を、第１エンコードデータにそれぞれ変換する。第１エンコードデータは、一例として３１ビットで構成される。第１エンコードデータの上位８ビットは、変換ビットデータ１６５２の上位８ビットと一致する。２つの第１エンコードデータの上位８ビットは、ルールから抽出される複数の文字列に共通するカテゴリ（例えば、文字「Ａ」の繰り返し）を示す共通ビットとして機能する。第１エンコードデータの下位２３ビットは、変換ビットデータ１６５２の下位５ビットが示す数字（２進数）の大きさに応じて、下位のビットから順に”１”が立つように生成される。つまり、下位２３ビットは、繰り返し回数を示す。
【０１０７】
本例において、第１エンコード回路１６５０は、変換ビットデータの下位５ビット「０００１０」（１０進数の２）から第１エンコードデータの下位２３ビット「０００００００＿００００００００＿０００００００１」を生成する。また、第１エンコード回路１６５０は、変換ビットデータの下位５ビット「００１００」（１０進数の４）から第１エンコードデータの下位２３ビット「０００００００＿００００００００＿０００００１１１」を生成する。第１エンコード回路１６５０は、これら生成したデータの各々に、ビットデータ１６１２の上位８ビットを加えて第１エンコードデータを生成する。なお、他の局面において第１エンコード回路１６５０は、他のエンコード方式（たとえば、ワンホットエンコーディング）に従って登録コードをエンコードしてもよい。さらに他の局面において、第１エンコード回路１６５０は、入力されるビットデータ１６１２から直接２つの第１エンコードデータを生成してもよい。
【０１０８】
図２０は、実施形態３に従う第２エンコード回路１６６０の動作を説明する図である。図２０を参照して、第２エンコード回路１６６０は、第１エンコード回路１６５０から入力される２つの第１エンコードデータ１６５４に基づいて、第２エンコードデータ１６６２を生成する。より具体的には、第２エンコード回路１６６０は、一方の第１エンコードデータ１６５４を、他方の第１エンコードデータ１６５４とビットごとに比較して、不一致のビットをドントケア”＊”に変換した第２エンコードデータ１６６２を生成する。つまり、第２エンコードデータの下位２３ビットは、繰り返し回数の範囲を示す。第２エンコード回路１６６０は、生成した第２エンコードデータ１６６２をセレクタ回路１６７０に出力する。
【０１０９】
本例において、第２エンコード回路１６６０は、一方の第１エンコードデータ「０１０００００１＿０００００００＿００００００００＿０００００００１」と、他方の第１エンコードデータ「０１０００００１＿０００００００＿００００００００＿０００００１１１」とをビットごとに比較して、不一致である下位２および３ビット目をドントケア”＊”に変換した「０１０００００１＿０００００００＿００００００００＿０００００＊＊１」を生成する。
【０１１０】
図２１は、実施形態３に従うセレクタ回路１６７０の動作について説明する図である。図１６および２１を参照して、セレクタ回路１６７０は、文字列データ１６１４と、第２エンコードデータ１６６２のうち、いずれか一方のデータをＣＰＵ２５０から入力されるセレクタ信号１６７２に従って選択する。セレクタ回路１６７０は、選択したデータをエントリデータ１６８０としてＴＣＡＭ装置２１０に出力する。ＴＣＡＭ装置２１０は、当該データをＴＣＡＭセルに格納する。
【０１１１】
上記によれば、実施形態３に従うライトデータ変換回路１６００は、繰り返しの正規表現を含むルールを格納するために使用するＴＣＡＭのエントリ数を低減できる。また、ライトデータ変換回路１６００は、繰り返しの下限値および上限値に応じた数だけ”１”のビットが立つ部分を含む２つの第１エンコードデータを生成する。これにより、ライトデータ変換回路１６００は、ルールに含まれる複数の文字列を全て包含したエントリデータ１６８０（第２エンコードデータ１６６２）を生成できる。
【０１１２】
加えて、ライトデータ変換回路１６００は、ＴＣＡＭ装置２１０とは独立した回路であるため、ＴＣＡＭ装置２１０として、汎用的なＴＣＡＭを用いることができる。そのため、この検索システムは、ＴＣＡＭのコストを抑制できる。
【０１１３】
図２２は、実施形態３に従うサーチデータ変換回路２２００の構成例について説明する図である。サーチデータ変換回路２２００は、文字列変換回路２２１０と、繰り返し変換回路２２１５と、文字列レジスタ２２２０と、比較回路２２３０と、エンコード回路２２４０と、セレクタ回路２２７０とを備える。一例として文字列「ＡＡＡ」が検索条件として文字列変換回路２２１０に入力された場合の各デバイスの動作について図２３〜２５を用いて説明する。
【０１１４】
図２３は、実施形態３に従う文字列変換回路２２１０の動作について説明する図である。図２２および２３を参照して、文字列変換回路２２１０は、入力される検索条件（文字列）を、ビットデータ２２１２に変換して繰り返し変換回路２２１５およびセレクタ回路２２７０に出力する。
【０１１５】
本例において、文字列変換回路２２１０は、文字列「ＡＡＡ」を検索条件として入力された場合、当該文字列をＡＳＣＩＩ文字コード（２進数）に変換してビットデータ２２１２を生成する。
【０１１６】
図２４は、実施形態３に従う繰り返し変換回路２２１５の動作について説明する図である。実施形態３に従う繰り返し変換回路２２１５は、入力されるビットデータ２２１２を繰り返しデータ２２１７に変換して、繰り返しデータ２２１７を比較回路２２３０およびエンコード回路２２４０に出力する。
【０１１７】
より具体的には、繰り返し変換回路２２１５は、ビットデータ２２１２から文字コードの繰り返しを検出し、当該文字コードおよび繰り返し回数を示す繰り返しデータ２２１７に変換する。
【０１１８】
本例において、繰り返し変換回路２２１５は、ビットデータ「０１０００００１＿０１０００００１＿０１０００００１」において「Ａ」の文字コード「０１０００００１」が３回繰り返していることを検出する。繰り返し変換回路２２１５は、検出結果に応じて、上位８ビットで「Ａ」の文字コード、下位５ビットで繰り返し回数「３」をそれぞれ示す繰り返しデータ「０１０００００１＿０００１１」を生成する。
【０１１９】
図２２を再び参照して、文字列レジスタ２２２０について説明する。文字列レジスタ２２２０は、登録データ２２２２を保持する。登録データ２２２２は、文字列レジスタ１６２０に格納されるデータと同じデータである。本例において、登録データ２２２２は、なお、他の局面において、文字列レジスタ１６２０および文字列レジスタ２２２０は、同一レジスタであってもよい。
【０１２０】
図２５は、実施形態３に従う比較回路２２３０の動作について説明する図である。図２２および２５を参照して、比較回路２２３０は、入力される繰り替えしデータ２２１７と、文字列レジスタ２２００に格納されている複数の登録データ２２２２とを比較する。比較回路２２３０は、繰り返しデータ２２１７が複数の登録データ２２２２のいずれかに包含されるか否かを判断する。
【０１２１】
より具体的には、比較回路２２３０は、繰り返しデータ２２１７の上位８ビットと、複数の登録データ２２２２の上位８ビットとを比較して、一致する登録データ２２２２を抽出する。次に、比較回路２２３０は、繰り返しデータ２２１７の下位５ビットが示す数字が、一致した登録データ２２２２の中位５ビットが示す数字から下位５ビットが示す数字の範囲内に含まれるか否かを判断する。比較回路２２３０は、繰り返しデータ２２１７の下位５ビットが示す数字が上記範囲内に含まれると判断した場合、繰り返しデータ２２１７が登録データ２２２２に包含されると判断する。比較回路２２３０は、繰り返しデータ２２１７が登録データ２２２２に包含されるか否かを示すセレクタ信号２２３４をセレクタ回路２２７０に出力する。
【０１２２】
図２５に示される例において、文字列レジスタ２２２０には、ルール「Ａ｛２，４｝」、「Ｂ｛１０，２０｝」「Ｃ｛２０，２４｝」を示すビットデータ１６１２が登録データ２２２２として格納されているものとする。この条件において、比較回路２２３０は、「Ａ｛３｝」を示す繰り返しデータ２２１７が、ルール「Ａ｛２，４｝」を示す登録データ２２２２に包含されると判断する。
【０１２３】
図２２を再び参照して、エンコード回路２２４０は、第１エンコード回路１６５０が変換ビットデータ１６５２を第１エンコードデータに変換するエンコード方式と同じ方式に従って、繰り返しデータ２２１７をエンコードデータ２２４２に変換する。
【０１２４】
本例において、エンコード回路２２４０は、「Ａ｛３｝」を示す繰り返しデータ「０１００００００１＿０００１１」を、「０１０００００１＿０００００００＿００００００００＿００００００１１」に変換してエンコードデータ２２４２としてセレクタ回路２２７０に出力する。
【０１２５】
セレクタ回路２２７０は、比較回路２２３０から繰り返しデータ２２１７が登録データ２２２２に包含されるとするセレクタ信号２２３４の受信に応じて、エンコードデータ２２４２をサーチデータ２２８０としてＴＣＡＭ装置２１０に出力する。一方、繰り返しデータ２２１７が登録データ２２２２に包含されないとするセレクタ信号２２３４の受信に応じて、セレクタ回路２２７０は、ビットデータ２２１２をサーチデータ２２８０としてＴＣＡＭ装置２１０に出力する。ＴＣＡＭ装置２１０は、サーチデータ２２８０（検索キー）が、格納されるエントリデータのいずれかにＨｉｔするか否かを判断する。
【０１２６】
本例において、サーチデータ変換回路２２００は、サーチデータ「０１０００００１＿０００００００＿００００００００＿００００００１１」をＴＣＡＭ装置２１０に出力する。ＴＣＡＭ装置２１０には、ルール「Ａ｛２，４｝」に対応するエントリデータ「０１０００００１＿０００００００＿００００００００＿００００＊＊＊１」が格納されている。従って、ＴＣＡＭ装置２１０は、入力されたサーチデータがＨｉｔしたこと、および上記エントリデータが格納されるアドレス情報をサーチ結果としてＣＰＵ２５０に出力する。
【０１２７】
上記によれば、実施形態３に従う検索システムは、繰り返しの正規表現を含むルールを、繰り返しの対象である文字を示すビットと、繰り返し回数の範囲を示すビットとを含むエントリデータに変換してＴＣＡＭセルに格納する。また、この検索システムは、検索条件として入力される文字列を、繰り返される文字を示すビットと、繰り返し回数を示すビットとを含むサーチデータとに変換する。これにより、実施形態３に従う検索システムは、文字の繰り返しで表現される検索条件が上記ルールにＨｉｔするか否かを少ないエントリ数で判断することができる。
【０１２８】
［実施形態４］
実施形態３の第１エンコード回路１６５０は、３１ビットの第１エンコードデータ１６５２のうち、下位２３ビットを繰り返し回数を示すビットデータとして扱い、繰り返し回数に応じて下位のビットから順に”１”を立てる構成であった。かかる構成の場合、第１エンコード回路１６５０は、２４（＝２３＋１）回までしか繰り返し回数を表現できない。
【０１２９】
そこで、実施形態４に従う検索システムは、実施形態３に従う検索システムに対して、第１エンコードデータのビット長を変えずに、表現できる繰り返し回数を増やす。以下、その構成について説明する。なお、実施形態４に従う検索システムの構成は、実施形態３に従う検索システムと略同じであるため、相違する点についてのみ説明する。
【０１３０】
図２６は、実施形態４に従う繰り返し回数を示すビットデータのデータ構造について説明する図である。一例として、実施形態４に従う変換ビットデータ２６００を用いて説明する。実施形態３において、変換ビットデータ１６５２のビット長は１３ビットであって、下位５ビットが繰り返し回数を示す。これに対して実施形態４に従う変換ビットデータは、１８ビットであって、下位１０ビットが繰り返し回数を示す。この下位１０ビットを繰り返し回数データ２６２０と定義する。
【０１３１】
実施形態４では、実施形態３において繰り返し回数を示すビットデータ１６１２の中位５ビット並びに下位５ビット、ビットデータ２２１２の下位５ビット、および繰り返しデータの下位５ビットは、全て１０ビットで表現される。
【０１３２】
図２７は、実施形態４に従う第１エンコード回路２７５０の動作について説明する図である。実施形態４に従う検索システムは、実施形態３に従う第１エンコード回路１６５０の替わりに第１エンコード回路２７５０を備える。
【０１３３】
第１エンコード回路２７５０は、変換ビットデータ２６００に含まれる繰り返し回数データ２６２０を、一例として、２３ビットの繰り返しエンコードデータ２７６０に変換する。第１エンコード回路２７５０は、変換ビットデータ２６００の上位８ビットと、繰り返しエンコードデータ２７６０とを併合して第１エンコードデータとして第２エンコード回路１６６０に出力する。
【０１３４】
繰り返しエンコードデータ２７６０は、実施形態２に従う第１エンコードデータ１５５２と同様に、上位５ビット、中位９ビット、下位９ビットに分けて設定される。中位９ビットは、下位９ビットが全て”１”になったときの桁上がりビットとして機能する。上位５ビットは、中位９ビットが全て”１”になったときの桁上がりビットとして機能する。
【０１３５】
具体例を用いて説明する。繰り返し回数が「２」を示す繰り返し回数データ「００＿００００＿００１０」は、「０００００＿０００００００００＿００００００００１」に変換される。繰り返し回数が「１０」を示す繰り返し回数データ「００＿００００＿１０１０」は、「０００００＿０００００００００＿１１１１１１１１１」に変換される。繰り返し回数が「１１」を示す繰り返し回数データ「００＿００００＿１０１１」は、中位９ビットの最下位ビットが桁上がりして「０００００＿００００００００１＿０００００００００」に変換される。
【０１３６】
繰り返し回数が「１００」を示す繰り返し回数データ「００＿０１１０＿０１００」は、「０００００＿１１１１１１１１１＿１１１１１１１１１」に変換される。繰り返し回数が「１０１」を示す繰り返し回数データ「００＿０１１０＿０１０１」は、上位５ビットの最下位ビットが桁上がりして「００００１＿０００００００００＿０００００００００」に変換される。
【０１３７】
このように、２３ビットの繰り返しエンコードデータを上位５ビット、中位９ビット、下位９ビットに分けて設定した場合、６００（＝（５＋１）×（９＋１）×（９＋１））通りの繰り返し回数を表現できる。したがって、実施形態４に従う検索システムは、第１エンコードデータのビット長を増やさずに、取扱い可能な繰り返し回数を実施形態３に従う検索システムよりも増やすことができる。
【０１３８】
［実施形態５］
上記実施形態１および２は、論理和の正規表現に従うルールを少ないエントリ数でＴＣＡＭ装置に格納し、実施形態３および４は、繰り返しの正規表現に従うルールを少ないエントリ数でＴＣＡＭ装置に格納する構成であった。
【０１３９】
実施形態５に従う検索システムは、論理和の正規表現に従うルールおよび繰り返しの正規表現に従うルールの両方を、少ないエントリ数でＴＣＡＭ装置に格納する。以下、その構成について説明する。
【０１４０】
図２８は、実施形態５に従う検索システム２８００の構成例について説明する図である。なお、図２に示される検索システム２００と同じ符号を付している部分については略同じであるため、相違する点についてのみ説明する。
【０１４１】
検索システム２８００は、ライトデータ変換回路２３０および１６００と、サーチデータ変換回路２４０および２２００を備える。検索システム２８００は、ルール判断回路２８１０と、検索条件判断回路２８２０とをさらに備える。
【０１４２】
ルール判断回路２８１０は、入力されるルールに含まれる正規表現の種類を判断し、当該ルールをライトデータ変換回路２３０および１６００のいずれかに出力する。より具体的には、ルール判断回路２８１０は、論理和の正規表現を含むルールを入力された場合、当該ルールをライトデータ変換回路２３０に出力する。ルール判断回路２８１０は、繰り返しの正規表現を含むルールを入力された場合、当該ルールをライトデータ変換回路１６００に出力する。
【０１４３】
実施形態５に従うライトデータ変換回路２３０および１６００はそれぞれ、基本的には図７および１６で説明したように動作するが、第２エンコード回路７６０（１６６０）が出力するデータ（第３エンコードデータ）が、上記説明したデータ（第２エンコードデータ７６２，１６６２）とは若干異なる。
【０１４４】
図２９は、実施形態５に従う第３エンコードデータ２９１０（２９１５）および第４エンコードデータ２９３０（２９３５）のデータ構造について説明する図である。分図（Ａ）は、実施形態５に従う第２エンコード回路７６０（１６６０）が出力する第３エンコードデータ２９１０（２９１５）のデータ構造について説明する図である。
【０１４５】
分図（Ａ）を用いて、まず、第２エンコード回路７６０が出力する第３エンコードデータ２９１０について説明する。第３エンコードデータ２９１０は、分類コード２９２０と、上記説明した第２エンコードデータ７６２とを含む。分類コード２９２０は、ルールに含まれる正規表現の種類を示すデータである。一例として、実施形態５に従う第２エンコード回路７６０は、分類コード２９２０を”１”に設定することにより、第３エンコードデータ２９１０が、論理和の正規表現に従うルールであることを示す。
【０１４６】
実施形態５に従う第２エンコード回路１６６０は、分類コード２９２０と、上記説明した第２エンコードデータ１６６２とを含む第３エンコードデータ２９１５を出力する。このとき、第２エンコード回路１６６０は、分類コード２９２０を”０”に設定することにより、第３エンコードデータ２９１５が、繰り返しの正規表現に従うルールであることを示す。
【０１４７】
これにより、ＴＣＡＭ装置２１０には、論理和の正規表現に従うルールと、繰り返しの正規表現に従うルールとが、区別されて格納される。
【０１４８】
図２８を再び参照して、検索条件判断回路２８２０は、入力される検索条件としての文字列に応じて、当該文字列をサーチデータ変換回路２４０および２２００のいずれかに出力する。一例として、検索条件判断回路２８２０は、入力される文字列が繰り返しの文字列である場合（たとえば、「ＡＡ」や「ＡＡＡ」など）、当該文字列をサーチデータ変換回路２２００に出力する。一方、入力される文字列が論理和の文字列である場合、検索条件判断回路２８２０は、入力される文字列をサーチデータ変換回路２４０に出力する。
【０１４９】
実施形態５に従うサーチデータ変換回路２４０および２２００はそれぞれ、基本的には図１４および２２で説明したように動作するが、エンコード回路１４４０（２２４０）が出力するデータ（第４エンコードデータ）が、上記説明したエンコードデータ１４４２（２２４２）とは若干異なる。
【０１５０】
図２９の分図（Ｂ）を参照して、まず、実施形態５に従うエンコード回路１４４０が出力する第４エンコードデータ２９３０について説明する。エンコード回路１４４０は、分類コード２９４０と、上記説明したエンコードデータ１４４２とを含む第４エンコードデータ２９３０を出力する。このとき、エンコード回路１４４０は、分類コード２９４０を”１”に設定することにより、第４エンコードデータ２９３０が、論理和のサーチデータ（検索キー）であることを示す。
【０１５１】
実施形態５に従うエンコード回路２２４０は、分類コード２９４０と、上記説明したエンコードデータ２２４２とを含む第４エンコードデータ２９３５を出力する。このとき、エンコード回路２２４０は、分類コード２９４０を”０”に設定することにより、第４エンコードデータ２９３５が、繰り返しのサーチデータ（検索キー）であることを示す。
【０１５２】
上記によれば、実施形態５に従う検索システム２８００は、同一のＴＣＡＭセルアレイに、論理和の正規表現に従うルールと、繰り返しの正規表現に従うルールとを少ないエントリ数で格納できる。これにより、検索システム２８００は、ＴＣＡＭ装置２１０のＴＣＡＭセルアレイの数（エントリの数）、およびＴＣＡＭセルを冷却するファン（不図示）の数をより低減できる。その結果、当該技術は、検索システムのコストをより低減できる。
【０１５３】
さらに、この検索システム２８００は、正規表現の種類を示す分類コードを含むようにエントリデータおよびサーチデータを生成する。これにより、この検索システム２８００は、同一のＴＣＡＭセルアレイの中で、検索条件に含まれる文字列が上記ルールにＨｉｔするか否かを少ないエントリ数で判断できる。
【０１５４】
［実施形態６］
実施形態１〜５に従う検索システムはＴＣＡＭ装置を用いて検索する構成であった。実施形態６に従う検索システム３０００は、ＴＣＡＭ装置に加え、さらに検索エンジンを用いて検索する。
【０１５５】
図３０は、実施形態６に従う検索システム３０００の構成例を説明する図である。なお、図２と同一符号を付している部分については同じであるため、その部分についての説明は繰り返さない。
【０１５６】
図３０を参照して、検索システム３０００は、ＴＣＡＭ装置２１０に加え、さらに正規表現検索エンジン３０１０を備える。検索システム３０００は、検索条件振り分け回路３０２０と、ＴＣＡＭ入力回路３０３０と、エンジン入力回路３０４０と、サーチ結果マージ回路３０５０とをさらに備える。
【０１５７】
実施形態６に従うＴＣＡＭ装置２１０には、実施形態５で説明した方法に従い論理和の正規表現に従うルールと、繰り返しの正規表現に従うルールとが各エントリに格納される。
【０１５８】
正規表現検索エンジン３０１０は、入力される正規表現の文法を解釈し、パターンマッチング処理を行なうためのプログラムである。正規表現検索エンジン３０１０は、既知の検索エンジンであって、例えば、非決定性有限オートマトン（ＮＦＡ）型エンジンであってもよいし、決定性有限オートマトン（ＤＦＡ）型エンジンであってもよい。
【０１５９】
検索条件振り分け回路３０２０は、検索条件に含まれる正規表現の種類に応じて、当該検索条件をＴＣＡＭ入力回路３０３０およびエンジン入力回路３０４０のうちいずれか一方の回路に出力する。より具体的には、検索条件振り分け回路３０２０は、論理和の正規表現に従う検索条件、および繰り返しの正規表現に従う検索条件を、ＴＣＡＭ入力回路３０３０に出力する。それ以外の正規表現に従う検索条件について、検索条件振り分け回路３０２０は、エンジン入力回路３０４０に出力する。
【０１６０】
ＴＣＡＭ入力回路３０３０は、実施形態５で説明した検索条件判断回路２８２０と、サーチデータ変換回路２４０および２２００とを備える。ＴＣＡＭ入力回路３０３０は、入力された検索条件（を示す文字列）を、正規表現の種類を示す分類コードを含むサーチデータに変換してＴＣＡＭ装置２１０に出力する。これにより、ＴＣＡＭ装置２１０は、検索条件に含まれる文字列が格納されるルールにＨｉｔするか否かを示す第１サーチ結果をサーチ結果マージ回路３０５０に出力する。他の局面において、第１サーチ結果は、ＴＣＡＭ装置２１０においてＨｉｔしたエントリのアドレスを含み得る。
【０１６１】
一方、エンジン入力回路３０４０は、入力された検索条件（を示す文字列）を、正規表現検索エンジン３０１０が検索可能なデータ形式に変換して、正規表現検索エンジン３０１０に出力する。正規表現検索エンジン３０１０は、エンジン入力回路３０４０から入力されるサーチデータ（検索キー）に対する検索結果を示す第２サーチ結果をサーチ結果マージ回路３０５０に出力する。
【０１６２】
サーチ結果マージ回路３０５０は、入力される第１サーチ結果と第２サーチ結果とを統合（マージ）して、サーチ結果としてＣＰＵ２５０に出力する。
【０１６３】
上記によれば、実施形態６に従う検索システム３０００は、ＴＣＡＭ装置２１０に加えて正規表現検索エンジン３０１０を併用することで、サーチの処理負荷を軽減できる。また、一般的にハードウェアであるＴＣＡＭ装置２１０が行なうサーチ処理の方が、ソフトウェアである正規表現検索エンジン３０１０が行なうサーチ処理よりも速い。そのため、単に正規表現検索エンジン３０１０のみを用いるよりも、検索システム３０００は、速いサーチ処理を実現できる。
【０１６４】
なお、エントリデータを格納するのはＴＣＡＭセルに限定されない。具体的には、エントリデータは、３値以上を保持可能な連想メモリセルに格納され得る。
【０１６５】
上記説明した種々の回路は、少なくとも１つのプロセッサのような半導体集積回路、少なくとも１つの特定用途向け集積回路ＡＳＩＣ（Application  Specific  Integrated  Circuit）、少なくとも１つのＤＳＰ（Digital Signal Processor）、少なくとも１つのＦＰＧＡ（Field  Programmable  Gate  Array）、および／またはその他の演算機能を有する回路を含む回路によって実現され得る。
【０１６６】
これらの回路は、有形の読取可能な少なくとも１つの媒体から、１以上の命令を読み出すことにより上記に示される各種機能を実現しうる。
【０１６７】
このような媒体は、磁気媒体（たとえば、ハードディスク）、光学媒体（例えば、コンパクトディスク（ＣＤ）、ＤＶＤ）、揮発性メモリ、不揮発性メモリの任意のタイプのメモリなどの形態をとるが、これらの形態に限定されるものではない。
【０１６８】
揮発性メモリはＤＲＡＭ（Dynamic  Random  Access  Memory）およびＳＲＡＭ（Static  Random  Access  Memory）を含み得る。不揮発性メモリは、ＲＯＭ、ＮＶＲＡＭを含み得る。半導体メモリは、少なくとも１つのプロセッサとともに半導体回路の１部分であり得る。
【０１６９】
以上、本発明者によってなされた発明を実施形態に基づき具体的に説明したが、本発明者は前記実施形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることは言うまでもない。
【符号の説明】
【０１７０】
２００  検索システム、２１０  ＴＣＡＭ装置、２３０，１６００  ライトデータ変換回路、２４０，２２００  サーチデータ変換回路、７１０，１６１０  文字列抽出変換回路、７２０，１４２０，１６２０，２２２０  文字列レジスタ、７３０，１４３０  比較変換回路、７４０，１４４０，１６４０，２２４０  エンコード回路、７５０，１５５０，１６５０，２７５０  第１エンコード回路、７６０，１６６０  第２エンコード回路、７７０，１４７０，１６７０，２２７０  セレクタ回路、１４１０，２２１０  文字列変換回路、２２３０  比較回路、２８１０  ルール判断回路、２８２０  検索条件判断回路、２９２０，２９４０  分類コード、３０１０  正規表現検索エンジン、３０２０  検索条件振り分け回路、３０３０  ＴＣＡＭ入力回路、３０４０  エンジン入力回路、３０５０  サーチ結果マージ回路。
【図１】
2018026046.tif 000003
【図２】
2018026046.tif 000004
【図３】
2018026046.tif 000005
【図４】
2018026046.tif 000006
【図５】
2018026046.tif 000007
【図６】
2018026046.tif 000008
【図７】
2018026046.tif 000009
【図８】
2018026046.tif 000010
【図９】
2018026046.tif 000011
【図１０】
2018026046.tif 000012
【図１１】
2018026046.tif 000013
【図１２】
2018026046.tif 000014
【図１３】
2018026046.tif 000015
【図１４】
2018026046.tif 000016
【図１５】
2018026046.tif 000017
【図１６】
2018026046.tif 000018
【図１７】
2018026046.tif 000019
【図１８】
2018026046.tif 000020
【図１９】
2018026046.tif 000021
【図２０】
2018026046.tif 000022
【図２１】
2018026046.tif 000023
【図２２】
2018026046.tif 000024
【図２３】
2018026046.tif 000025
【図２４】
2018026046.tif 000026
【図２５】
2018026046.tif 000027
【図２６】
2018026046.tif 000028
【図２７】
2018026046.tif 000029
【図２８】
2018026046.tif 000030
【図２９】
2018026046.tif 000031
【図３０】
2018026046.tif 000032