(57)【特許請求の範囲】
【請求項１】
第１の文字と、任意の文字の文字数と、第２の文字とが入力文字列に含まれるか否かを確認する入力文字列確認装置であって、
前記入力文字列の先頭から順に判定対象の文字を変更しながら、判定対象の文字と前記第１の文字とが一致するかを順次判定する第１の文字判定回路と、
前記第１の文字判定回路が、判定対象の文字と前記第１の文字とが一致すると判定した後、判定対象の文字が前記第１の文字と一致するかの判断を前記任意の文字の文字数分だけ実行したタイミングで、判定を許可する信号を出力する制御回路と、
前記信号が出力された場合に、次の判定対象の文字が前記第２の文字と一致するかを判定する第２の文字判定回路と、
前記第２の文字判定回路が前記第２の文字と一致すると判定した場合に、前記入力文字列に、前記第１の文字と、前記任意の文字の文字数と、前記第２の文字とが含まれていると判断する照合確認回路と、を備える入力文字列確認装置。
【請求項２】
前記制御回路は、
複数のビットを有するマスクビット列と、
前記マスクビット列の前記複数のビットに対応する複数のビットを有する状態ビット列と、を有し、
前記マスクビット列には、先頭から前記任意の文字の文字数の位置のビットに予め第１フラグが設定されており、
前記状態ビット列は、前記第１の文字判定回路が判定対象の文字と前記第１の文字とが一致すると判定した場合に、先頭のビットに第２フラグを設定し、前記第１の文字判定回路が判定対象の文字と前記第１の文字との一致を判定する毎に前記第２フラグを前記状態ビット列の後方に１ビットずつ遷移させ、
前記マスクビット列のうち前記第１フラグが設定されたビットは、対応する前記状態ビット列のビットに前記第２フラグが設定された場合に、前記判定を許可する信号を出力する、
ことを特徴とする請求項１に記載の入力文字列確認装置。
【請求項３】
前記任意の文字の文字数が範囲で指定されている場合には、前記マスクビット列のうち前記範囲に含まれる文字数に対応するビットに前記第１フラグが設定されていることを特徴とする請求項２に記載の入力文字列確認装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、入力文字列確認装置に関する。
【背景技術】
【０００２】
従来、入力される文字列において、１又は複数の特定文字が存在してから任意の文字を１又は複数挟んで、同一又は別の特定文字が１又は複数存在する箇所（所定のパターン）があれば、検出したいという要望がある（例えば、特許文献１参照）。このような要望は、例えば、特定のコマンドを検出する侵入検知システムや、ペイロード分析によるネットワーク効率化の分野などにおいて多くなっている。
【０００３】
従来においては、入力された文字が特定文字か否かを判断する文字チェック回路を複数並べた正規表現回路に対して、入力された文字列に含まれる文字を順に入力し、所定のパターンの有無を判断する処理を行っている。
【０００４】
この場合、図３９に示すように、任意の文字に対応する文字チェック回路には、任意文字を表す「＊」を設定し、どのような文字が入力されても次の文字チェック回路を有効にする（状態ビットを０から１にする）ようにしている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００７−１０２７４４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、文字チェック回路は、各文字を判断するための辞書機能（図３９のメモリ部分）を有しており、当該辞書機能には、例えば２５６ビットの回路を用いる必要がある。このため、文字チェック回路は８ビットの回路等に比べると大きさ（面積や容積）が大きくなり、ひいては、文字チェック回路が搭載されるＬＳＩやＦＰＧＡの大きさ（面積や容積）が大きくなるおそれがある。
【０００７】
そこで本件は上記の課題に鑑みてなされたものであり、小型化を図ることが可能な入力文字確認装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本明細書に記載の入力文字列確認装置は、第１の文字と、任意の文字の文字数と、第２の文字とが入力文字列に含まれるか否かを確認する入力文字列確認装置であって、前記入力文字列の先頭から順に判定対象の文字を変更しながら、判定対象の文字と前記第１の文字とが一致するかを順次判定する第１の文字判定回路と、前記第１の文字判定回路が、判定対象の文字と前記第１の文字とが一致すると判定した後、判定対象の文字が前記第１の文字と一致するかの判断を前記任意の文字の文字数分だけ実行したタイミングで、判定を許可する信号を出力する制御回路と、前記信号が出力された場合に、次の判定対象の文字が前記第２の文字と一致するかを判定する第２の文字判定回路と、前記第２の文字判定回路が前記第２の文字と一致すると判定した場合に、前記入力文字列に、前記第１の文字と、前記任意の文字の文字数と、前記第２の文字とが含まれていると判断する照合確認回路と、を備える入力文字列確認装置である。
【発明の効果】
【０００９】
本明細書に記載の入力文字確認装置は、小型化を図ることができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】第１の実施形態に係る処理装置の構成を概略的に示す図である。
【図２】図１の正規表現回路を示す図である。
【図３】文字チェック回路の処理の概要を示す図である。
【図４】第１の実施形態に係る回路マッピング処理を示すフローチャートである。
【図５】図５のステップＳ１０の具体的処理を示すフローチャートである。
【図６】図５のステップＳ３６（Ｓ３０）の具体的処理を示すフローチャートである。
【図７】図７（ａ）、図７（ｂ）は、第１の実施形態に係る回路マッピング作成処理を説明するための図（その１）である。
【図８】図８（ａ）、図８（ｂ）は、第１の実施形態に係る回路マッピング作成処理を説明するための図（その２）である。
【図９】図９（ａ）、図９（ｂ）は、第１の実施形態に係る回路マッピング作成処理を説明するための図（その３）である。
【図１０】照合時におけるＣＰＵの処理を示すフローチャートである。
【図１１】照合時におけるマスクビットの処理を示すフローチャートである。
【図１２】照合時におけるバイパスマスクビットの処理を示すフローチャートである。
【図１３】照合時における転送マスクビットの処理を示すフローチャートである。
【図１４】照合時における文字チェック回路の処理を示すフローチャートである。
【図１５】照合時における状態ビットの処理を示すフローチャートである。
【図１６】照合時における照合確認回路の処理を示すフローチャートである。
【図１７】図１７（ａ）、図１７（ｂ）は、第１の実施形態に係る照合処理を説明するための図（その１）である。
【図１８】図１８（ａ）、図１８（ｂ）は、第１の実施形態に係る照合処理を説明するための図（その２）である。
【図１９】図１９（ａ）、図１９（ｂ）は、第１の実施形態に係る照合処理を説明するための図（その３）である。
【図２０】図２０（ａ）、図２０（ｂ）は、第１の実施形態に係る照合処理を説明するための図（その４）である。
【図２１】図２１（ａ）、図２１（ｂ）は、第１の実施形態に係る照合処理を説明するための図（その５）である。
【図２２】図２２（ａ）、図２２（ｂ）は、第１の実施形態に係る照合処理を説明するための図（その６）である。
【図２３】図２３（ａ）、図２３（ｂ）は、第１の実施形態に係る照合処理を説明するための図（その７）である。
【図２４】第１の実施形態に係る照合処理を説明するための図（その８）である。
【図２５】第２の実施形態に係る正規表現回路を示す図である。
【図２６】第２の実施形態に係る、図５のステップＳ３６（Ｓ３０）の具体的処理を示すフローチャートである。
【図２７】図２７（ａ）、図２７（ｂ）は、第２の実施形態に係る回路マッピング作成処理を説明するための図（その１）である。
【図２８】図２８（ａ）、図２８（ｂ）は、第２の実施形態に係る回路マッピング作成処理を説明するための図（その２）である。
【図２９】図２９（ａ）、図２９（ｂ）は、第２の実施形態に係る回路マッピング作成処理を説明するための図（その３）である。
【図３０】図３０（ａ）、図３０（ｂ）は、第２の実施形態に係る照合処理を説明するための図（その１）である。
【図３１】図３１（ａ）、図３１（ｂ）は、第２の実施形態に係る照合処理を説明するための図（その２）である。
【図３２】図３２（ａ）、図３２（ｂ）は、第２の実施形態に係る照合処理を説明するための図（その３）である。
【図３３】図３３（ａ）、図３３（ｂ）は、第２の実施形態に係る照合処理を説明するための図（その４）である。
【図３４】図３４（ａ）、図３４（ｂ）は、第２の実施形態に係る照合処理を説明するための図（その５）である。
【図３５】図３５（ａ）、図３５（ｂ）は、第２の実施形態に係る照合処理を説明するための図（その６）である。
【図３６】図３６（ａ）、図３６（ｂ）は、第２の実施形態に係る照合処理を説明するための図（その７）である。
【図３７】第２の実施形態に係る照合処理を説明するための図（その８）である。
【図３８】変形例に係る処理装置の概略構成を示す図である。
【図３９】従来技術を説明するための図である。
【発明を実施するための形態】
【００１１】
《第１の実施形態》
以下、第１の実施形態について、図１〜図２４に基づいて詳細に説明する。図１には、第１の実施形態に係る処理装置１００の構成が概略的に示されている。処理装置１００は、例えば、所定のコマンド（文字列）を検知する侵入検知システム（ＩＤＳ：Intrusion Detection System）や、所定のコマンド（文字列）を検知してネットワーク効率化を図るペイロード分析システムなどであるものとする。
【００１２】
図１に示すように、処理装置１００は、ＣＰＵ１０と、記憶装置１２と、ＦＰＧＡ（Field-Programmable Gate Array）２０と、を備える。なお、ＦＰＧＡに代えて、ＬＳＩ（Large Scale Integration）を用いることとしてもよい。
【００１３】
ＣＰＵ１０は、記憶装置１２に格納されている回路マッピング作成プログラムを用いて、外部から入力される正規表現に対応する回路マッピングを作成し、ＦＰＧＡ２０に対して入力する。また、ＣＰＵ１０は、外部から入力された入力文字列（入力テキスト）に正規表現が含まれているか否かを確認するため、ＦＰＧＡ２０に対して入力文字列を入力する。なお、正規表現とは、ａ．｛２｝ｂや、ａ．｛２，４｝ｂなどと表されるものであり、前者は、ａ、２文字の任意文字、ｂの順に並ぶ文字列を意味し、後者は、ａ、２〜４文字の任意文字、ｂの順に並ぶ文字列を意味する。
【００１４】
ＦＰＧＡ２０は、Ｉ／Ｆ回路２２と、１又は複数の入力文字列確認装置としての正規表現回路３０と、を備える。Ｉ／Ｆ回路２２は、ＣＰＵ１０と正規表現回路３０との間のデータのやり取りを行う。正規表現回路３０は、外部から入力された入力文字列（文字テキスト）に正規表現が含まれているか否かを確認し、確認結果をＣＰＵ１０に対して送信する。
【００１５】
図２には、正規表現回路３０の具体的な構成が示されている。正規表現回路３０は、入力文字送信回路３６と、文字判定回路としての文字チェック回路３４ａ，３４ｂ，３４ｃと、メモリ３２ａ，３２ｂ，３２ｃと、８つの状態ビット３８ａ〜３８ｈと、８つのマスクビット４０ａ〜４０ｈと、転送マスクビット４０ｉと、バイパスマスクビット４０ｊと、判断回路としての照合確認回路４２と、メモリ４４と、を備える。
【００１６】
入力文字送信回路３６は、ＣＰＵ１０から入力された入力テキストに含まれる文字を順に、文字チェック回路３４ａ〜３４ｃ及び状態ビット３８ａ〜３８ｈに入力する機能を有する。
【００１７】
文字チェック回路３４ａ〜３４ｃは、ＣＰＵ１０によって割り当てられた文字（メモリ３２ａ〜３２ｃに書き込まれた文字）又は文字群に、ＣＰＵ１０から入力された文字（入力文字送信回路３６から送信される）が含まれているか否かをチェックする回路である。例えば、図３に示すように、メモリ３２ａ〜３２ｃにおいては、ＣＰＵ１０によって割り当てられた文字のＡＳＣＩＩコードに「○」が関連付けられており、文字チェック回路３４ａ〜３４ｃは、当該メモリ３２ａ〜３２ｃを参照して、入力された文字をチェックする。なお、文字チェック回路に任意文字「＊」が割り当てられた場合には、全てのＡＳＣＩＩコードに「○」が関連付けられる。
【００１８】
状態ビット３８ａ〜３８ｈのうち、状態ビット３８ａ〜３８ｄは、文字チェック回路３４ａ，３４ｂの間に配置され、状態ビット３８ｅ〜３８ｈは、文字チェック回路３４ｂ，３４ｃの間に配置されている。状態ビット３８ａ〜３８ｈは、ＣＰＵ１０から文字が入力されるたびに、保持している情報（１（フラグＯＮ）又は０（フラグＯＦＦ））を次の状態ビット（右隣の状態ビット）に送る機能（右シフトする機能）を有している。
【００１９】
マスクビット４０ａ〜４０ｈには、ＣＰＵ１０によって正規表現に応じた情報（１又は０）が割り当てられる。マスクビット４０ａ〜４０ｈは、状態ビット３８ａ〜３８ｈと１対１で対応付けられている。マスクビット４０ａ〜４０ｈが保持する情報が１（フラグＯＮ）の場合、マスクビット４０ａ〜４０ｈは、対応する状態ビット３８ａ〜３８ｈが保持する情報を後方（右側）の文字チェック回路に送る機能を有している。
【００２０】
転送マスクビット４０ｉは、情報として１（フラグＯＮ）を保持している場合に、状態ビット３８ｄの情報を状態ビット３８ｅに送る機能を有している。なお、転送マスクビット４０ｉは、情報として０（フラグＯＦＦ）を有している場合には、文字チェック回路３４ｂの出力を次の状態ビット３８ｅへ送る機能を有している。
【００２１】
バイパスマスクビット４０ｊは、情報として１（フラグＯＮ）を保持している場合に、文字チェック回路３４ｂの出力を文字チェック回路３４ｃに送る機能を有している。
【００２２】
照合確認回路４２は、メモリ４４に格納された照合パターンと、文字チェック回路３４ａ〜３４ｃからの出力と、を照合して、入力テキストに正規表現が含まれているか否かを確認する機能を有する。
【００２３】
（回路マッピング処理）
次に、本実施形態のＣＰＵ１０による、正規表現回路３０の回路マッピング処理について図４〜図６のフローチャートに沿って、かつその他図面を適宜参照しつつ詳細に説明する。
【００２４】
図４の処理では、ステップＳ１０において、ＣＰＵ１０が、回路マッピング作成処理を実行する。
【００２５】
ステップＳ１０においては、図５のフローチャートに沿った処理が実行される。図５の処理では、まず、ステップＳ２０において、ＣＰＵ１０は、正規表現をｃとする。なお、本実施形態では、一例として、ｃ＝ａ．｛２，４｝ｂである場合について説明する。
【００２６】
次いで、ステップＳ２２では、ＣＰＵ１０が、ｃが空か否かを判断する。ここでの判断が否定された場合には、ステップＳ２４に移行する。ステップＳ２４に移行すると、ＣＰＵ１０は、ｃの先頭が１文字目か否かを判断する。ここでは、「ａ」がｃの１文字目であるので、ステップＳ２４の判断が肯定され、ステップＳ３２に移行する。
【００２７】
ステップＳ３２に移行すると、ＣＰＵ１０は、ｃの先頭の文字を次の文字チェック回路に割り当てる。ここでは、先頭の文字チェック回路３４ａに文字「ａ」を割り当てる（図７（ａ）参照）。
【００２８】
次いで、ステップＳ３４では、ＣＰＵ１０は、ｃから処理した文字列を取り除く。この場合、「ａ」を取り除くので、ｃ＝．｛２，４｝ｂとなる（図７（ｂ）の破線枠内参照）。その後は、ステップＳ２２に戻る。ステップＳ２２の判断が否定されて、ステップＳ２４に移行すると、ｃの先頭は「．」なので、ステップＳ２４の判断が肯定されて、ＣＰＵ１０は、ステップＳ３６に移行する。ステップＳ３６に移行すると、ＣＰＵ１０は、「．」の直後の繰り返し回数を基にマスクパターンを作成し、マスクビットに割り当てる。このステップＳ３６では、具体的には、図６に示すフローチャートに沿った処理が実行される。
【００２９】
図６のステップＳ５０では、ＣＰＵ１０が、最小繰り返し回数がＮ以上か否かを判断する。なお、Ｎは、文字チェック回路間に存在するマスクビットの数（本実施形態ではＮ＝４）であるものとする。ここでの判断が否定されると、ステップＳ５２に移行し、最小繰り返し回数分のマスクビットを前から「０」に設定する（図７（ｂ）のマスクビット４０ａ，４０ｂ参照）。
【００３０】
次いで、ステップＳ５４では、ＣＰＵ１０が、最大繰り返し回数から最小繰り返し回数を引く（減算する）。この場合、最大繰り返し回数は４から２になる（図７（ｂ）の破線枠内参照）。
【００３１】
次いで、ステップＳ５６では、ＣＰＵ１０は、最大繰り返し回数＋１が未設定マスクビット数以上であるか否かを判断する。上記例の場合、最大繰り返し回数（２）＋１＝３は、未設定のマスクビット数（２）以上であるので、ステップＳ５６の判断は肯定され、ステップＳ５８に移行する。
【００３２】
ステップＳ５８に移行すると、ＣＰＵ１０は、未設定のマスクビットを「１」に設定し、転送マスクビット４０ｉ及びバイパスマスクビット４０ｊを「１」に設定する。また、次のステップＳ６０では、ＣＰＵ１０は、任意文字「＊」を次の文字チェック回路３４ｂ（メモリ３２ｂ）に割り当て、次のマスクビットを対象とする。なお、ステップＳ５８、Ｓ６０の処理が行われた後の状態が、図８（ａ）に示されている。
【００３３】
次いで、ステップＳ６２では、ＣＰＵ１０は、最大繰り返し回数から未設定マスクビット数を引く。ここでは、最大繰り返し回数から未設定マスクビット数を引くと０となる（図８（ａ）の破線枠内参照）。その後は、ステップＳ５６に戻る。
【００３４】
ステップＳ５６では、最大繰り返し回数（０）＋１が未設定マスクビット数以上か否かを判断する。ここでは、未設定マスクビット数は４（マスクビット４０ｅ〜４０ｈ）であるので、判断は否定されて、ステップＳ６４に移行する。ステップＳ６４では、ＣＰＵ１０は、最大繰り返し回数＋１分の未設定のマスクビットを前から「１」に設定し、残りを０に設定する。本実施形態では、図８（ｂ）に示すように、マスクビット４０ｅが「１」に設定されるとともに、マスクビット４０ｆ〜４０ｈが「０」に設定される。
【００３５】
その後は、図５のステップＳ３４に移行する。なお、ステップＳ５０の判断が肯定された場合、すなわち、最小繰り返し回数がＮ（＝４）以上であった場合には、ステップＳ６６〜Ｓ７０の処理を実行する。具体的には、ステップＳ６６では、ＣＰＵ１０が、各マスクビットを「０」に設定し、転送マスクビット４０ｉ及びバイパスマスクビット４０ｊを「１」に設定する。次いで、ステップＳ６８では、ＣＰＵ１０は、任意文字「＊」を次の文字チェック回路に割り当て、次のマスクビットを対象とする。次いで、ステップＳ７０では、ＣＰＵ１０は、最小繰り返し回数、及び最大繰り返し回数からＮを引く。その後は、ステップＳ５０に戻る。
【００３６】
図５に戻り、図６（ステップＳ３６）の処理の後、ステップＳ３４に移行すると、ＣＰＵ１０は、ｃから処理した文字列を取り除く。図６の処理では、ｃ＝．｛２，４｝ｂのうち、「．｛２，４｝」の処理が行われたので、ｃ＝ｂとなる（図９（ａ）の破線枠内参照）。その後は、ステップＳ２２に戻る。
【００３７】
ステップＳ２２では、ＣＰＵ１０が、ｃが空か否かを判断するが、ここでの判断が否定されると、ステップＳ２４に移行する。また、ステップＳ２４では、ＣＰＵ１０がｃの先頭が「．」であるか否かを判断するが、ここでの判断が否定されると、ステップＳ２６に移行する。更に、ステップＳ２６では、ＣＰＵ１０が、ｃの先頭が１文字目か否かを判断するが、ここでの判断が否定されるとステップＳ２８に移行する。また、ステップＳ２８では、ＣＰＵ１０が、直前の処理は「．」又は「．」に関する繰り返しか否かを判断する。ここでの判断が肯定された場合には、ステップＳ３２に移行する。
【００３８】
ステップＳ３２に移行すると、ＣＰＵ１０は、ｃの先頭文字を次の文字チェック回路に割り当てる。すなわち、ＣＰＵ１０は、文字チェック回路３４ｃ（メモリ３２ｃ）に対して「ｂ」を割り当てる（図９（ａ）参照）。そして、ステップＳ３４に移行すると、ＣＰＵ１０は、ｃから処理した文字列を取り除く。この場合、ｃは空となる（図９（ｂ）の破線枠内参照）。
【００３９】
次いで、ステップＳ２２では、ｃが空か否かを判断する。ここでの判断が肯定された場合には、ステップＳ３８に移行する。ステップＳ３８では、ＣＰＵ１０が、現在のチェック回路に対応する照合パターンビットを１にする。この場合、現在の文字チェック回路３４ｃは、先頭から３番目の文字チェック回路であるので、ＣＰＵ１０は、照合確認回路４２のメモリ４４に「００１」を設定する（図９（ｂ）参照）。以上により、図５に示す回路マッピング作成処理は終了し、図４のステップＳ１２に移行する。
【００４０】
なお、ステップＳ３０に移行した場合（文字が連続する部分の処理の場合）には、ＣＰＵ１０は、「．｛０｝」として、最小繰り返し回数＝０、最大繰り返し回数＝０のマスクパターンを作成し、マスクビットに割り当てる処理を行う。なお、このステップＳ３０の具体的な処理は、図６と同様となっている。
【００４１】
図４に戻り、ステップＳ１２では、ＣＰＵ１０は、作成した回路マッピングをパターンＩＤ（正規表現に割り当てられたＩＤ）とともに正規表現回路３０に送信し、図４の全処理を終了する。
【００４２】
（照合処理）
次に、上記のようにして作成された回路マッピングを用いた正規表現回路３０による照合処理について詳細に説明する。まず、ＣＰＵ１０及び正規表現回路３０の各部の処理について説明する。
【００４３】
（ＣＰＵ１０の処理）
図１０には、照合処理時のＣＰＵ１０の処理がフローチャートにて示されている。
【００４４】
図１０の処理では、ＣＰＵ１０は、まず、ステップＳ８０において、照合対象の文字列データ（入力テキスト）が入力されるまで待機する。照合対象の文字列データ（入力テキスト）が入力されると、ＣＰＵ１０は、ステップＳ８２に移行する。
【００４５】
ステップＳ８２に移行すると、ＣＰＵ１０は、照合対象の文字列データ（入力テキスト）を、Ｉ／Ｆ回路２２を介して、正規表現回路３０に対して送信する。その後は、ステップＳ８０に戻り、ステップＳ８０、Ｓ８２の処理・判断を繰り返す。
【００４６】
（マスクビット４０ａ〜４０ｈの処理）
図１１には、照合処理時のマスクビット４０ａ〜４０ｈの処理がフローチャートにて示されている。
【００４７】
図１１の処理では、まず、ステップＳ９０において、マスクビットが１であるか否かを判断する。ここでの判断が肯定された場合には、ステップＳ９２に移行し、マスクビットは、当該マスクビットに対応する状態ビットを次の文字チェク回路（右隣の文字チェック回路）へ送信する。すなわち、マスクビットが１で、対応する状態ビットが０であれば、マスクビットは次の文字チェック回路に０を送信し、対応する状態ビットが１であれば、マスクビットは次の文字チェック回路に１を送信する。
【００４８】
一方、ステップＳ９０の判断が否定された場合、すなわち、マスクビットが０であった場合には、ステップＳ９４に移行し、０を次の文字チェック回路へ送信する。
【００４９】
（バイパスマスクビット４０ｊの処理）
図１２には、照合処理時のバイパスマスクビット４０ｊの処理がフローチャートにて示されている。
【００５０】
図１２の処理では、まず、ステップＳ１００において、文字チェック回路３４ｂの出力及びバイパスマスクビット４０ｊが１か否かを判断する。ここでの判断が肯定された場合には、ステップＳ１０２に移行し、バイパスマスクビットは、１を次の文字チェク回路へ送信する。
【００５１】
一方、ステップＳ１００の判断が否定された場合、すなわち、文字チェック回路３４ｂの出力及びバイパスマスクビット４０ｊのいずれかが０であった場合には、ステップＳ１０４に移行し、０を次の文字チェック回路へ送信する。
【００５２】
（転送マスクビット４０ｉの処理）
図１３には、照合処理時の転送マスクビット４０ｉの処理がフローチャートにて示されている。
【００５３】
図１３の処理では、まず、ステップＳ１０５において、転送マスクビット４０ｉが１であるか否かを判断する。ここでの判断が肯定された場合には、ステップＳ１０６に移行し、転送マスクビット４０ｉは、前の状態ビット３８ｄの情報を次の状態ビット３８ｅへ送信する。すなわち、転送マスクビット４０ｉが１で、前の状態ビット３８ｄが０であれば、転送マスクビットは０を送信し、転送マスクビット４０ｉが１で、前の状態ビット３８ｄが１であれば、転送マスクビット４０ｉは１を送信する。
【００５４】
一方、ステップＳ１０５の判断が否定された場合、すなわち、転送マスクビット４０ｉが０であった場合には、ステップＳ１０７に移行する。この場合、転送マスクビット４０ｉは、文字チェック回路３４ｂの出力を次の状態ビット３８ｅへ送信する。
【００５５】
（文字チェック回路３４ａ〜３４ｃの処理）
図１４には、照合処理時の文字チェック回路３４ａ〜３４ｃの処理がフローチャートにて示されている。
【００５６】
図１４の処理では、まず、ステップＳ１１０において、文字チェック回路は、当該文字チェック回路に接続されているマスクビット及びバイパスマスクビットからの出力のうち１つでも１があるか否かを判断する。ここでの判断が否定された場合には、文字チェック回路は、ステップＳ１１８において１を出力し、図１４の全処理を終了する。一方、ステップＳ１１０の判断が肯定された場合には、ステップＳ１１２に移行する。
【００５７】
ステップＳ１１２に移行すると、文字チェック回路は、入力文字が、設定された文字あるいは文字群と一致しているか否かを確認する。次いで、ステップＳ１１４では、文字チェック回路は、一致するものがあったか否かを判断する。ここでの判断が肯定された場合には、文字チェック回路は、ステップＳ１１６において１を出力し、否定された場合には、ステップＳ１１８において０を出力する。
【００５８】
なお、文字チェック回路３４ａには、マスクビットもバイパスマスクビットも接続されていない。したがって、文字チェック回路３４ａにおいては、ステップＳ１１０の判断を省略することとしてもよい。
【００５９】
（状態ビット３８ａ〜３８ｈの処理）
図１５には、照合処理時の状態ビット３８ａ〜３８ｈの処理がフローチャートにて示されている。
【００６０】
図１５の処理では、ステップＳ１２０において、状態ビット３８ａ〜３８ｈは、文字チェック回路のチェック結果あるいは前の状態ビットを保持し、次のサイクルで次の状態ビットへ保持した情報を送信する処理を行う。
【００６１】
（照合確認回路の処理）
図１６には、照合処理時の照合確認回路４２の処理がフローチャートにて示されている。
【００６２】
図１６の処理では、照合確認回路４２は、ステップＳ１３０において、照合パターンが１のビットに対応するチェック回路の出力が１か否かを判断する。ここでの判断が否定された場合には、そのまま図１６の処理を終了する。
【００６３】
一方、ステップＳ１３０の判断が肯定された場合には、照合確認回路４２は、パターンＩＤ（図４のステップＳ１２参照）を出力する。
【００６４】
（正規表現回路３０による照合処理）
次に、図１７〜図２４に基づいて、図９（ｂ）のように回路マッピングされた正規表現回路３０を用いた照合処理について詳細に説明する。なお、以下の説明では、上述した各フローチャートのステップ番号についても適宜併記するものとする。
【００６５】
本実施形態では、前述した回路マッピング（正規表現ａ．｛２，４｝ｂ）（図９（ｂ）参照）を受信した正規表現回路３０に対して、入力テキスト：ａｂａａｂｃｃｂが入力された場合について説明する。なお、以下においては、入力テキスト：ａｂａａｂｃｃｂのうち、入力される文字には「」を付して表記するものとする
【００６６】
（「ａ」ｂａａｂｃｃｂの入力）
図１７（ａ）には、入力テキスト：ａｂａａｂｃｃｂの最初の文字「ａ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致している（「○」と表記）ので、図１７（ｂ）に示すように、状態ビット３８ａに「１」を出力するとともに、照合確認回路４２に「１」を出力する（Ｓ１１６（図１４））。一方、文字チェック回路３４ｂでは、マスクビット４０ａ〜４０ｄからの出力の全てが０であるので、文字チェックを行わず（「×」と表記）、バイパスマスクビット４０ｊ、照合確認回路４２に「０」を出力する（Ｓ１１０：否定、Ｓ１１８（図１４））。また、文字チェック回路３４ｃでは、マスクビット４０ｅ〜４０ｈ及びバイパスマスクビット４０ｊからの出力の全てが０であるので、文字チェックを行わず（「×」と表記）、照合確認回路４２に「０」を出力する（Ｓ１１０：否定、Ｓ１１８（図１４））。
【００６７】
なお、この場合における照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「１００」であり、照合パターン「００１」の１に対応するビットが「０」である（Ｓ１３０（図１６）：否定）。したがって、照合確認回路４２からＣＰＵ１０に対してパターンＩＤは出力されない。
【００６８】
（ａ「ｂ」ａａｂｃｃｂの入力）
図１８（ａ）には、入力テキスト：ａｂａａｂｃｃｂの２番目の文字「ｂ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致していない（「×」と表記）ので、図１８（ｂ）に示すように、状態ビット３８ａに「０」を出力するとともに、照合確認回路４２に「０」を出力する。なお、状態ビット３８ａ〜３８ｈでは、「ｂ」が入力される直前に、予め次の状態ビットに対して保持していた情報（０又は１）を送っておく（右にシフトしておく）ものとする（図１８（ｂ）参照、Ｓ１２０（図１５））。
【００６９】
一方、文字チェック回路３４ｂ、３４ｃでは、マスクビット４０ａ〜４０ｈやバイパスマスクビット４０ｊからの出力の全てが０である。したがって、文字チェック回路３４ｂ、３４ｃでは文字チェックを行わず（「×」と表記）、バイパスマスクビット４０ｊ及び照合確認回路４２に「０」を出力する。
【００７０】
なお、この場合における照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「０００」であり、照合パターン「００１」の１に対応するビットが「０」である。したがって、照合確認回路４２からＣＰＵ１０に対してパターンＩＤは出力されない。
【００７１】
（ａｂ「ａ」ａｂｃｃｂの入力）
図１９（ａ）には、入力テキスト：ａｂａａｂｃｃｂの３番目の文字「ａ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致しているので（「○」と表記）、図１９（ｂ）に示すように、状態ビット３８ａに「１」を出力するとともに、照合確認回路４２に「１」を出力する。なお、状態ビット３８ａ〜３８ｈでは、「ａ」が入力される直前に、予め次の状態ビットに対して保持していた情報（０又は１）を送っておく（右にシフトしておく）ものとする。
【００７２】
一方、文字チェック回路３４ｂ、３４ｃでは、マスクビット４０ａ〜４０ｈやバイパスマスクビット４０ｊからの出力の全てが０である。したがって、文字チェック回路３４ｂ、３４ｃでは、文字チェックを行わず（「×」と表記）、バイパスマスクビット４０ｊや照合確認回路４２に「０」を出力する。
【００７３】
なお、この場合における照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「１００」であり、照合パターン「００１」の１に対応するビットが「０」である。したがって、照合確認回路４２からＣＰＵ１０に対してパターンＩＤは出力されない。
【００７４】
（ａｂａ「ａ」ｂｃｃｂの入力）
図２０（ａ）には、入力テキスト：ａｂａａｂｃｃｂの４番目の文字「ａ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致している（「○」と表記）。一方、文字チェック回路３４ｂでは、保持する情報が「１」のマスクビット４０ｃから、状態ビット３８ｃの情報「１」が送信されてくるため（Ｓ９２（図１１））、文字チェックを行う。この場合、文字チェック回路３４ｂのメモリ３２ｂには、任意文字「＊」が設定されているので、入力文字「ａ」と一致することになる（「○」と表記）。なお、文字チェック回路３４ｃについては、マスクビット４０ｅ〜４０ｈ及びバイパスマスクビット４０ｊからの出力が０なので、文字チェックは行われない（「×」と表記）。
【００７５】
したがって、入力テキスト：ａｂａａｂｃｃｂの４番目の文字「ａ」が入力された場合、図２０（ａ）から状態ビット３８ａ〜３８ｈの情報が右にシフトした状態で、図２０（ｂ）に示すように、文字チェック回路３４ａから状態ビット３８ａ及び照合確認回路４２に「１」が送信される。また、文字チェック回路３４ｂから照合確認回路４２及びバイパスマスクビット４０ｊに「１」が送信され、文字チェック回路３４ｃから照合確認回路４２に「０」が送信される。
【００７６】
なお、この場合における照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「１１０」であり、照合パターン「００１」の１に対応するビットが「０」である。したがって、照合確認回路４２からＣＰＵ１０に対してパターンＩＤは出力されない。
【００７７】
（ａｂａａ「ｂ」ｃｃｂの入力）
図２１（ａ）には、入力テキスト：ａｂａａｂｃｃｂの５番目の文字「ｂ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致していない（「×」と表記）。一方、文字チェック回路３４ｂでは、保持する情報が「１」のマスクビット４０ｄから、状態ビット３８ｄの情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｂのメモリ３２ｂには、任意文字「＊」が設定されているので、入力文字「ｂ」と一致することになる（「○」と表記）。また、文字チェック回路３４ｃでは、保持する情報が「１」のバイパスマスクビット４０ｊから、文字チェック回路３４ｂから出力された情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｃのメモリ３２ｃには、文字「ｂ」が設定されているので、入力文字「ｂ」と一致することになる（「○」と表記）。
【００７８】
したがって、入力テキスト：ａｂａａｂｃｃｂの５番目の文字「ｂ」が入力された場合には、図２１（ａ）から状態ビット３８ａ〜３８ｈの情報が右にシフトした状態で、図２１（ｂ）に示すように、文字チェック回路３４ａから状態ビット３８ａ及び照合確認回路４２に「０」が送信される。また、文字チェック回路３４ｂから照合確認回路４２及びバイパスマスクビット４０ｊに「１」が送信され、文字チェック回路３４ｃから照合確認回路４２に「１」が送信される。
【００７９】
この場合、照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「０１１」であり、照合パターン「００１」の１に対応するビットが「１」であるので、ＣＰＵ１０に対して、パターンＩＤが出力されることになる（Ｓ１３２（図１６））。
【００８０】
（ａｂａａｂ「ｃ」ｃｂの入力）
図２２（ａ）には、入力テキスト：ａｂａａｂｃｃｂの６番目の文字「ｃ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致していない（「×」と表記）。一方、文字チェック回路３４ｂでは、保持する情報が「１」のマスクビット４０ｃから、状態ビット３８ｃの情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｂのメモリ３２ｂには、任意文字「＊」が設定されているので、入力文字「ｃ」と一致することになる（「○」と表記）。また、文字チェック回路３４ｃでは、保持する情報が「１」のバイパスマスクビット４０ｊから、文字チェック回路３４ｂから出力された情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｃのメモリ３２ｃには、文字「ｂ」が設定されているので、入力文字「ｃ」とは一致しない（「×」と表記）。
【００８１】
したがって、入力テキスト：ａｂａａｂｃｃｂの６番目の文字「ｃ」が入力された場合には、図２２（ａ）から状態ビット３８ａ〜３８ｈの情報が右にシフトした状態で、図２２（ｂ）に示すように、文字チェック回路３４ａから状態ビット３８ａ及び照合確認回路４２に「０」が送信される。また、文字チェック回路３４ｂから照合確認回路４２及びバイパスマスクビット４０ｊに「１」が送信され、文字チェック回路３４ｃから照合確認回路４２に「０」が送信される。
【００８２】
この場合、照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「０１０」であり、照合パターン「００１」の１に対応するビットが「０」である。したがって、照合確認回路４２からＣＰＵ１０に対してパターンＩＤは出力されない。
【００８３】
（ａｂａａｂｃ「ｃ」ｂの入力）
図２３（ａ）には、入力テキスト：ａｂａａｂｃｃｂの７番目の文字「ｃ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致していない（「×」と表記）。一方、文字チェック回路３４ｂでは、保持する情報が「１」のマスクビット４０ｃ、４０ｄから、状態ビット３８ｃ，３８ｄの情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｂのメモリ３２ｂには、任意文字「＊」が設定されているので、入力文字「ｃ」と一致することになる（「○」と表記）。また、文字チェック回路３４ｃでは、保持する情報が「１」のバイパスマスクビット４０ｊから、文字チェック回路３４ｂから出力された情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｃのメモリ３２ｃには、文字「ｂ」が設定されているので、入力文字「ｃ」とは一致しない（「×」と表記）。
【００８４】
したがって、入力テキスト：ａｂａａｂｃｃｂの７番目の文字「ｃ」が入力された場合には、図２３（ａ）から状態ビット３８ａ〜３８ｈの情報が右にシフトした状態で、図２３（ｂ）に示すように、文字チェック回路３４ａから状態ビット３８ａ及び照合確認回路４２に「０」が送信される。また、文字チェック回路３４ｂから照合確認回路４２及びバイパスマスクビット４０ｊに「１」が送信され、文字チェック回路３４ｃから照合確認回路４２に「０」が送信される。
【００８５】
この場合、照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「０１０」であり、照合パターン「００１」の１に対応するビットが「０」であるので、パターンＩＤは出力されない。
【００８６】
（ａｂａａｂｃｃ「ｂ」の入力）
図２４には、入力テキスト：ａｂａａｂｃｃｂの８番目の文字「ｂ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致していない（「×」と表記）。一方、文字チェック回路３４ｂでは、保持する情報が「１」のマスクビット４０ｄから、状態ビット３８ｄの情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｂのメモリ３２ｂには、任意文字「＊」が設定されているので、入力文字「ｃ」と一致することになる（「○」と表記）。また、文字チェック回路３４ｃでは、保持する情報が「１」のバイパスマスクビット４０ｊから文字チェック回路３４ｂの出力「１」が送信されてきたり、保持する情報が「１」のマスクビット４０ｅから、状態ビット３８ｅの情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｃのメモリ３２ｃには、文字「ｂ」が設定されているので、入力文字「ｂ」と一致する（「○」と表記）。
【００８７】
したがって、入力テキスト：ａｂａａｂｃｃｂの８番目の文字「ｂ」が入力された場合には、文字チェック回路３４ａから照合確認回路４２に「０」が送信され、文字チェック回路３４ｂから照合確認回路４２に「１」が送信され、文字チェック回路３４ｃから照合確認回路４２に「１」が送信される。
【００８８】
この場合、照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「０１１」であり、照合パターン「００１」の１に対応するビットが「１」であるので、ＣＰＵ１０に対して、パターンＩＤが出力されることになる。
【００８９】
上述したように、図２１や図２４においてパターンＩＤが出力されることで、入力テキスト：ａｂａａｂｃｃｂの中に、正規表現ａ．｛２，４｝ｂが含まれているという情報を出力することができる。
【００９０】
なお、これまでの説明からわかるように、状態ビット３８ａ〜３８ｈ及びマスクビット４０ａ〜４０ｊを含んで、複数の文字判定回路の判定を有効にするか無効にするかを制御する判定制御回路としての機能が実現されている。
【００９１】
以上、詳細に説明したように、本第１の実施形態によると、入力テキストに含まれる文字が順に入力され、当該入力された文字が予め定められた文字と一致するかを判定する複数の文字チェック回路３４ａ〜３４ｃと、文字チェック回路の判定を有効にするか無効にするかを制御する状態ビット３８ａ〜３８ｈ及びマスクビット４０ａ〜４０ｊと、複数の文字チェック回路３４ａ〜３４ｃのうちの最後の文字チェック回路が、入力文字と予め定めた文字とが一致すると判定した場合に、前記入力テキストに正規表現が含まれると判断し、パターンＩＤを出力する照合確認回路４２と、を備え、状態ビット３８ａ〜３８ｈ及びマスクビット４０ａ〜４０ｊは、判定が有効な文字チェック回路において、入力文字が予め定めた文字と一致すると判定された後、正規表現において定められている任意の文字の文字数だけ文字が入力されるまでの間、次の文字チェック回路の判定を無効にし、次に入力される文字の判定を有効にする。このようにすることで、本第１の実施形態では、従来のように正規表現に含まれる任意の文字の文字数に対応する文字チェック回路を用意しなくても、入力テキストに正規表現が含まれるか否かを判断することができる。これにより、文字チェック回路の数を減らすことができるので、正規表現回路３０の大きさを小さくすることができ、ひいては、正規表現回路３０が搭載されるＦＰＧＡ２０の小型化を図ることが可能となる。また、文字チェック回路の数を減らすことで、正規表現回路やＦＰＧＡ２０のコスト削減も可能となる。
【００９２】
また、本第１の実施形態では、マスクビット４０ａ〜４０ｉの情報（１又は０）と、状態ビット３８ａ〜３８ｈの情報（１又は０）に基づいて、文字チェック回路の判定を有効にしたり無効にしたりする。これにより、複雑な回路を用いることなく、正規表現回路３０を実現することが可能である。また、本第１の実施形態では、正規表現において任意の文字の文字数が範囲で指定されている場合であっても、当該範囲に対応するマスクビットに１を設定しておくことで、対応することができる。これにより、簡易な構成で、正規表現における任意文字の範囲指定に対応することができる。
【００９３】
また、本第１の実施形態では、正規表現で定められている任意文字の文字数よりも、文字チェック回路間に配列されているマスクビットの数が少ない場合には、文字チェック回路に任意文字「＊」を入力することで、文字チェック回路の前後のマスクビットを連続的に用いることとしている。これにより、任意文字の文字数が文字チェック回路間のマスクビットの数より多い場合であっても柔軟に対応することができる。
【００９４】
なお、上記第１の実施形態で図示した構成では、正規表現に含まれる文字数や、任意文字の数によっては対応できない場合もある。このような場合には、実際の使用状況等を想定して、回路設計段階において、マスクビットや状態ビットの数を増やしたり、文字チェック回路の数を増やしたりすれば良い。
【００９５】
《第２の実施形態》
次に、第２の実施形態について、図２５〜図３７に基づいて、詳細に説明する。本第２の実施形態では、正規表現回路３０’が、第１の実施形態の正規表現回路３０と一部異なっている。
【００９６】
本第２の実施形態の正規表現回路３０’は、図２５に示すように、図２の正規表現回路３０に存在していた転送マスクビット４０ｉが省略されており、文字チェック回路３４ｂと状態ビット３８ｅが接続されている。また、本第２の実施形態では、ＣＰＵ１０は、回路マッピングの際に、第１の実施形態で説明した図６の処理に代えて図２６の処理を行う。また、本第２の実施形態では、転送マスクビット４０ｉが省略されているので、図１３の処理も省略される。
【００９７】
ここで、図２６の処理では、図６のステップＳ５８に代えて、ステップＳ５８’が実行される。具体的には、ステップＳ５８’では、ＣＰＵ１０は、未設定のマスクビットを１に設定しバイパスマスクビット４０ｊを１に設定する。また、図２６の処理では、図６のステップＳ６６に代えて、ステップＳ６６’が実行される。具体的には、ステップＳ６６’では、ＣＰＵ１０は、最終マスクビット以外を０、最終マスクビットを１、バイパスマスクビット４０ｊを０に設定する。なお、図２６のその他の処理については、図６と同様となっている。
【００９８】
なお、図２７〜図２９には、本第２の実施形態における回路マッピング作成処理の手順が示されている。なお、図２７〜図２９においては、正規表現ａ．｛５，６｝ｂの回路マッピングを作成する場合について図示している。
【００９９】
図２７（ａ）では、文字チェック回路３４ａに文字「ａ」が割り当てられ（Ｓ３２（図５））、図２７（ｂ）では、マスクビット４０ａ〜４０ｄ及びバイパスマスクビット４０ｊに情報（１又は０）が割り当てられるとともに（Ｓ３６）、文字チェック回路３４ｂに任意文字「＊」が割り当てられる（Ｓ３２）。
【０１００】
また、図２８（ａ）では、マスクビット４０ｅに情報（０）が割り当てられ、図２８（ｂ）では、マスクビット４０ｆ〜４０ｈが割り当てられる。
【０１０１】
更に、図２９（ａ）では、文字チェック回路３４ｃに文字「ｂ」が割り当てられ、図２９（ｂ）では、照合確認回路４２に照合パターン「００１」が定められ（Ｓ３８）、回路マッピング作成処理が終了する。
【０１０２】
次に、図２９（ｂ）のように回路マッピングされた正規表現回路３０’を用いた、照合処理について、図３０〜図３７に基づいて説明する。なお、本第２の実施形態においては、回路マッピング（正規表現ａ．｛５，６｝ｂ）された正規表現回路３０’に、上記第１の実施形態と同一の入力テキスト：ａｂａａｂｃｃｂが入力された場合について説明する。
【０１０３】
（「ａ」ｂａａｂｃｃｂの入力）
図３０（ａ）には、入力テキスト：ａｂａａｂｃｃｂの最初の文字「ａ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致している（「○」と表記）ので、図３０（ｂ）に示すように、状態ビット３８ａに「１」を出力するとともに、照合確認回路４２に「１」を出力する。一方、文字チェック回路３４ｂでは、マスクビットからの出力の全てが０であるので、文字チェックを行わず（「×」と表記）、状態ビット３８ｅ、バイパスマスクビット４０ｊ、照合確認回路４２に「０」を出力する。また、文字チェック回路３４ｃでは、マスクビット及びバイパスマスクビット４０ｊからの出力の全てが０であるので、文字チェックを行わず（「×」と表記）、照合確認回路４２に「０」を出力する。なお、この場合における照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「１００」であり、照合パターン「００１」の１に対応するビットが「０」であるので、照合確認回路４２からパターンＩＤは出力されない。
【０１０４】
（ａ「ｂ」ａａｂｃｃｂの入力）
図３１（ａ）には、入力テキスト：ａｂａａｂｃｃｂの２番目の文字「ｂ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致していない（「×」と表記）ので、図３１（ｂ）に示すように、状態ビット３８ａに「０」を出力するとともに、照合確認回路４２に「０」を出力する。一方、文字チェック回路３４ｂ、３４ｃでは、マスクビットやバイパスマスクビットからの出力の全てが０であるので、文字チェックを行わず（「×」と表記）、照合確認回路４２等に「０」を出力する。なお、この場合における照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「０００」であり、照合パターン「００１」の１に対応するビットが「０」であるので、照合確認回路４２からパターンＩＤは出力されない。
【０１０５】
（ａｂ「ａ」ａｂｃｃｂの入力）
図３２（ａ）には、入力テキスト：ａｂａａｂｃｃｂの３番目の文字「ａ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致している（「○」と表記）ので、図３２（ｂ）に示すように、状態ビット３８ａに「１」を出力するとともに、照合確認回路４２に「１」を出力する。
【０１０６】
一方、文字チェック回路３４ｂ、３４ｃでは、マスクビットやバイパスマスクビットからの出力の全てが０であるので、文字チェックを行わず（「×」と表記）、照合確認回路４２等に「０」を出力する。なお、この場合における照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「１００」であり、照合パターン「００１」の１に対応するビットが「０」であるので、照合確認回路４２からパターンＩＤは出力されない。
【０１０７】
（ａｂａ「ａ」ｂｃｃｂの入力）
図３３（ａ）には、入力テキスト：ａｂａａｂｃｃｂの４番目の文字「ａ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致している（「○」と表記）ので、図３３（ｂ）に示すように、状態ビット３８ａに「１」を出力するとともに、照合確認回路４２に「１」を出力する。
【０１０８】
一方、文字チェック回路３４ｂ、３４ｃでは、マスクビットやバイパスマスクビットからの出力の全てが０であるので、文字チェックを行わず（「×」と表記）、照合確認回路４２等に「０」を出力する。なお、この場合における照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「１００」であり、照合パターン「００１」の１に対応するビットが「０」であるので、照合確認回路４２からパターンＩＤは出力されない。
【０１０９】
（ａｂａａ「ｂ」ｃｃｂの入力）
図３４（ａ）には、入力テキスト：ａｂａａｂｃｃｂの５番目の文字「ｂ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致していない（「×」と表記）。一方、文字チェック回路３４ｂでは、保持する情報が「１」のマスクビット４０ｄから、状態ビット３８ｄの情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｂのメモリ３２ｂには、任意文字「＊」が設定されているので、入力文字「ｂ」と一致することになる（「○」と表記）。これに対し、文字チェック回路３４ｃでは、マスクビット４０ｅ〜４０ｈやバイパスマスクビット４０ｊからの出力の全てが０であるので、文字チェックを行わず（「×」と表記）、照合確認回路４２に「０」を出力する。
【０１１０】
したがって、入力テキスト：ａｂａａｂｃｃｂの５番目の文字「ｂ」が入力された場合には、図３４（ｂ）に示すように、文字チェック回路３４ａから状態ビット３８ａ及び照合確認回路４２に「０」が送信される。また、文字チェック回路３４ｂから照合確認回路４２、状態ビット３８ｅ、バイパスマスクビット４０ｊに対して「１」が送信され、文字チェック回路３４ｃから照合確認回路４２に対して「０」が送信される。
【０１１１】
この場合、照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「０１０」であり、照合パターン「００１」の１に対応するビットが「０」であるので、照合確認回路４２からパターンＩＤは出力されない。
【０１１２】
（ａｂａａｂ「ｃ」ｃｂの入力）
図３５（ａ）には、入力テキスト：ａｂａａｂｃｃｂの６番目の文字「ｃ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致していない（「×」と表記）。また、文字チェック回路３４ｂでは、マスクビット４０ａ〜４０ｄからの出力の全てが０であるので、文字チェックを行わない（「×」と表記）。また、文字チェック回路３４ｃでは、保持する情報が「１」のバイパスマスクビット４０ｊから、文字チェック回路３４ｂの出力「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｃのメモリ３２ｃには、文字「ｂ」が設定されているので、入力文字「ｃ」とは一致しない（「×」と表記）。
【０１１３】
したがって、入力テキスト：ａｂａａｂｃｃｂの６番目の文字「ｃ」が入力された場合には、図３５（ａ）から状態ビット３８ａ〜３８ｈの情報が右にシフトした状態で、図３５（ｂ）に示すように、文字チェック回路３４ａから状態ビット３８ａ及び照合確認回路４２に「０」が送信される。また、文字チェック回路３４ｂから照合確認回路４２、状態ビット３８ｅ、バイパスマスクビット４０ｊに「０」が送信され、文字チェック回路３４ｃから照合確認回路４２に「０」が送信される。
【０１１４】
この場合、照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「０００」であり、照合パターン「００１」の１に対応するビットが「０」であるので、照合確認回路４２からパターンＩＤは出力されない。
【０１１５】
（ａｂａａｂｃ「ｃ」ｂの入力）
図３６（ａ）には、入力テキスト：ａｂａａｂｃｃｂの７番目の文字「ｃ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致していない（「×」と表記）。一方、文字チェック回路３４ｂでは、保持する情報が「１」のマスクビット４０ｄから、状態ビット３８ｄの情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｂのメモリ３２ｂには、任意文字「＊」が設定されているので、入力文字「ｃ」と一致することになる（「○」と表記）。また、文字チェック回路３４ｃでは、保持する情報が「１」のマスクビット４０ｆから、状態ビット３８ｆの情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｃのメモリ３２ｃには、文字「ｂ」が設定されているので、入力文字「ｃ」とは一致しない（「×」と表記）。
【０１１６】
したがって、入力テキスト：ａｂａａｂｃｃｂの７番目の文字「ｃ」が入力された場合には、図３６（ａ）から状態ビット３８ａ〜３８ｈの情報が右にシフトした状態で、図３６（ｂ）に示すように、文字チェック回路３４ａから状態ビット３８ａ及び照合確認回路４２に「０」が送信される。また、文字チェック回路３４ｂから照合確認回路４２、状態ビット３８ｅ、バイパスマスクビット４０ｊに「１」が送信され、文字チェック回路３４ｃから照合確認回路４２に「０」が送信される。
【０１１７】
この場合、照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「０１０」であり、照合パターン「００１」の１に対応するビットが「０」であるので、照合確認回路４２からパターンＩＤは出力されない。
【０１１８】
（ａｂａａｂｃｃ「ｂ」の入力）
図３７には、入力テキスト：ａｂａａｂｃｃｂの８番目の文字「ｂ」が入力文字送信回路３６に入力され、各文字チェック回路、各状態ビットへ送信された状態が示されている。この場合、文字チェック回路３４ａでは、メモリ３２ａに格納されている文字「ａ」と入力文字が一致していない（「×」と表記）。一方、文字チェック回路３４ｂでは、保持する情報が「１」のマスクビット４０ｄから、状態ビット３８ｄの情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｂのメモリ３２ｂには、任意文字「＊」が設定されているので、入力文字「ｃ」と一致することになる（「○」と表記）。また、文字チェック回路３４ｃでは、保持する情報が「１」のマスクビット４０ｇから、状態ビット３８ｇの情報「１」が送信されてくるため、文字チェックを行う。この場合、文字チェック回路３４ｃのメモリ３２ｃには、文字「ｂ」が設定されているので、入力文字「ｂ」と一致する（「○」と表記）。
【０１１９】
したがって、入力テキスト：ａｂａａｂｃｃｂの８番目の文字「ｂ」が入力された場合には、文字チェック回路３４ａから照合確認回路４２に「０」が送信され、文字チェック回路３４ｂから照合確認回路４２に「１」が送信され、文字チェック回路３４ｃから照合確認回路４２に「１」が送信される。この場合、照合確認回路４２に対する文字チェック回路３４ａ〜３４ｃからの出力は「０１１」であり、照合パターン「００１」の１に対応するビットが「１」であるので、照合確認回路４２からＣＰＵ１０に対してパターンＩＤが出力されることになる。
【０１２０】
このように、パターンＩＤが出力されることで、入力テキスト：ａｂａａｂｃｃｂの中に、正規表現ａ．｛５，６｝ｂが含まれているという情報を出力することができる。
【０１２１】
以上、詳細に説明したように、本第２の実施形態によると、上記第１の実施形態と同様、従来のように正規表現に含まれる任意の文字の文字数に対応する文字チェック回路を用意しなくても、入力テキストに正規表現が含まれるか否かを判断することができる。これにより、文字チェック回路の数を減らすことができるので、正規表現回路３０の大きさを小さくすることができ、ひいては、正規表現回路３０が搭載されるＦＰＧＡ２０の小型化を図ることが可能となる。また、文字チェック回路の数を減らすことで、正規表現回路やＦＰＧＡ２０のコスト削減も可能となる。
【０１２２】
なお、上記各実施形態では、ＦＰＧＡ２０（又はＬＳＩ）とＣＰＵ１０とが別体である場合について説明したが、これに限らず、図３８に示すように、ＦＰＧＡ２０’上にＣＰＵ１０が搭載されていてもよい。
【０１２３】
上述した各実施形態は本発明の好適な実施の例である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施可能である。
【０１２４】
なお、以上の説明に関して更に以下の付記を開示する。
（付記１）  特定の文字と、任意の文字の文字数との組み合わせで表される正規表現が入力文字列に含まれるか否かを確認する入力文字列確認装置であって、
前記入力文字列に含まれる文字が順に入力され、当該入力された文字が予め定められた判定文字と一致するかを判定する複数の文字判定回路と、
前記複数の文字判定回路の判定を有効にするか無効にするかを制御する判定制御回路と、
前記複数の文字判定回路のうちの最後の文字判定回路が、入力された文字と前記判定文字とが一致すると判定した場合に、前記入力文字列に前記正規表現が含まれると判断する判断回路と、を備え、
前記判定制御回路は、判定が有効な所定の文字判定回路において、入力された文字が判定文字と一致すると判定された後、前記正規表現において定められている任意の文字の文字数だけ文字が入力されるまでの間、前記所定の文字判定回路の次の文字判定回路の判定を無効にし、次に入力される文字の判定を有効にすることを特徴とする入力文字列確認装置。
（付記２）  前記判定制御回路は、
前記所定の文字判定回路と前記次の文字判定回路との間に配列された複数のマスクビットと、該複数のマスクビットに対応して配列された前記マスクビットと同数の状態ビットとを有し、
前記正規表現において定められている任意の文字の文字数に対応するマスクビットに予めフラグを立てておき、
前記所定の文字判定回路において前記入力された文字が予め定められた特定の文字であったと判定されたときに状態ビットの先頭にフラグを立て、
前記入力文字列に含まれる文字が入力される度に、前記状態ビットのフラグを後方に１つずつ遷移させ、
フラグが立っている状態ビットとフラグが立っているマスクビットとの位置が一致した場合に、次に入力される文字の前記次の文字判定回路における判定を有効にすることを特徴とする請求項１に記載の入力文字列確認装置。
（付記３）  前記判定制御回路は、
正規表現で定められている任意の文字の文字数よりも、前記所定の文字判定回路と前記次の文字判定回路との間に配列されたマスクビットの数が少ない場合には、
前記次の文字判定回路の判定文字として任意の文字を定め、当該次の文字判定回路の前後の複数のマスクビットを連続するマスクビットとして用いることを特徴とする付記２に記載の入力文字列確認装置。
（付記４）  前記正規表現において、前記任意の文字の文字数が範囲で指定されている場合には、前記マスクビットのうち前記範囲に含まれる文字数に対応するマスクビットに予めフラグを立てておくことを特徴とする付記２又は３に記載の入力文字列確認装置。
【符号の説明】
【０１２５】
３０  正規表現回路（入力文字列確認装置）
３４ａ〜３４ｃ  文字チェック回路（文字判定回路）
３８ａ〜３８ｈ  状態ビット（判定制御回路の一部）
４０ａ〜４０ｈ  マスクビット（判定制御回路の一部）
４０ｉ  転送マスクビット（判定制御回路の一部）
４０ｊ  バイパスマスクビット（判定制御回路の一部）
４２  照合確認回路（判断回路）
【図１】
0005942600.tif 000002
【図２】
0005942600.tif 000003
【図３】
0005942600.tif 000004
【図４】
0005942600.tif 000005
【図５】
0005942600.tif 000006
【図６】
0005942600.tif 000007
【図７】
0005942600.tif 000008
【図８】
0005942600.tif 000009
【図９】
0005942600.tif 000010
【図１０】
0005942600.tif 000011
【図１１】
0005942600.tif 000012
【図１２】
0005942600.tif 000013
【図１３】
0005942600.tif 000014
【図１４】
0005942600.tif 000015
【図１５】
0005942600.tif 000016
【図１６】
0005942600.tif 000017
【図１７】
0005942600.tif 000018
【図１８】
0005942600.tif 000019
【図１９】
0005942600.tif 000020
【図２０】
0005942600.tif 000021
【図２１】
0005942600.tif 000022
【図２２】
0005942600.tif 000023
【図２３】
0005942600.tif 000024
【図２４】
0005942600.tif 000025
【図２５】
0005942600.tif 000026
【図２６】
0005942600.tif 000027
【図２７】
0005942600.tif 000028
【図２８】
0005942600.tif 000029
【図２９】
0005942600.tif 000030
【図３０】
0005942600.tif 000031
【図３１】
0005942600.tif 000032
【図３２】
0005942600.tif 000033
【図３３】
0005942600.tif 000034
【図３４】
0005942600.tif 000035
【図３５】
0005942600.tif 000036
【図３６】
0005942600.tif 000037
【図３７】
0005942600.tif 000038
【図３８】
0005942600.tif 000039
【図３９】
0005942600.tif 000040