拒絶査定不服の審決｜不服2014-5164 - 特許審決データベース

会員機能

ランキング

請求人別審判件数

判例データベース

審決データベース

ポートフォリオ機能

ポートフォリオを新規に作成して保存		追加
既存のポートフォリオに追加保存		追加

この審決の個人情報、企業機密に関する修正依頼をする

PDF	PDFをダウンロード

審決分類	審判査定不服 2項進歩性特許、登録しない。 G06F
管理番号	1299997
審判番号	不服2014-5164
総通号数	186
発行国	日本国特許庁(JP)
公報種別	特許審決公報
発行日	2015-06-26
種別	拒絶査定不服の審決
審判請求日	2014-03-18
確定日	2015-04-23
事件の表示	特願2010-503940「マルチバイト処理向け文字列照合用有限オートマトン生成システム」拒絶査定不服審判事件〔平成21年 9月24日国際公開、WO2009/116646〕について、次のとおり審決する。
結論	本件審判の請求は、成り立たない。
理由	第1 手続の経緯本願は,平成21年3月19日(優先権主張平成20年3月19日,日本)を国際出願日とする特許出願であって,平成25年7月5日付けの拒絶理由通知に対して,同年9月9日に意見書の提出とともに手続補正がなされ,同年12月11日付けの拒絶査定に対して平成26年3月18日に審判請求がなされるとともに,同日付けで手続補正がなされたものである。第2 平成26年3月18日に提出された手続補正書による補正(以下,「本件補正」という。)の適否について 1.本件補正前の特許請求の範囲の記載本件補正前の特許請求の範囲の記載は以下のとおりである。「【請求項1】正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する手段を有するマルチバイト処理向け文字列照合用有限オートマトン生成装置。【請求項2】到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトン、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少ないため回路規模が削減できる有限オートマトンのいずれかを選択して生成することができることを特徴とする請求項1に記載のマルチバイト処理向け文字列照合用有限オートマトン生成装置。【請求項3】入力された正規表現を記憶する正規表現記憶手段と、前記正規表現記憶手段に記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFA(Nｏn-deｔeｒminiｓｔic Finiｔe Aｕｔｏmaｔｏn)へ変換する1-bｙｔe NFA変換手段と、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換するMｕlｔibｙｔe NFA変換手段と、 Mｕlｔibｙｔe NFA変換手段で変換したNFAを記憶するNFA記憶手段と、を備えることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン生成装置。【請求項4】前記Mｕlｔibｙｔe NFA変換手段は請求項1又は請求項2に記載のNFAを生成する手段を備えることを特徴とする請求項3に記載のマルチバイト処理向け文字列照合用有限オートマトン生成装置。【請求項5】前記Mｕlｔibｙｔe NFA変換手段は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成するか、入力された文字列のどの位置でパターンが一致したかは単独では判別できないNFAを生成するかを利用目的に応じて選択できる、ことを特徴とする請求項3又は請求項4に記載のマルチバイト処理向け文字列照合用有限オートマトン生成装置。【請求項6】前記1-bｙｔe NFA変換手段において、正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Mｕlｔibｙｔe NFA変換手段での変換処理が簡略化できる、ことを特徴とする請求項3乃至請求項5いずれか一つに記載のマルチバイト処理向け文字列照合用有限オートマトン生成装置。【請求項7】正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できるNFAを生成するNFA生成手段を有することを特徴とするマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。【請求項8】到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトン、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少ないため回路規模が削減できる有限オートマトンのいずれかを選択して生成することができることを特徴とする請求項7に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。【請求項9】入力された正規表現を記憶する正規表現記憶手段と、前記正規表現記憶手段に記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFA(Nｏn-deｔeｒminiｓｔic Finiｔe Aｕｔｏmaｔｏn)へ変換する1-bｙｔe NFA変換手段と、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換するMｕlｔibｙｔe NFA変換手段と、 Mｕlｔibｙｔe NFA変換手段で変換したNFAを記憶するNFA記憶手段と、 Mｕlｔibｙｔe NFA変換手段で変換したNFAから、そのハードウェア回路を記述するハードウェア記述言語を生成するHDL変換手段と、 HDL変換手段で変換したハードウェア記述言語を記憶するHDL記憶手段と、を備えることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。【請求項10】前記Mｕlｔibｙｔe NFA変換手段は、前記NFA生成手段を有することを特徴とする請求項9記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。【請求項11】前記Mｕlｔibｙｔe NFA変換手段は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成するか、入力された文字列のどの位置でパターンが一致したかは単独では判別できないNFAを生成するかを利用目的に応じて選択できる、ことを特徴とする請求項9又は請求項10に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。【請求項12】前記1-bｙｔe NFA変換手段において、正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Mｕlｔibｙｔe NFA変換手段での変換処理が簡略化できる、ことを特徴とする請求項9乃至請求項11いずれか一つに記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成装置。【請求項13】正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成するNFA生成処理を有することを特徴とする状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン生成方法。【請求項14】到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトン、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少ないため回路規模が削減できる有限オートマトンのいずれかを選択して生成することができることを特徴とする請求項13に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン生成方法。【請求項15】入力された正規表現を記憶し、前記記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFAへ変換し、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換し、前記変換したNFAを記憶する、ことを特徴とする状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン生成方法。【請求項16】さらに、前記ε遷移のない1 bｙｔeで遷移するNFAから指定された処理バイト数で遷移を行うNFAへの変換は、前記NFA生成処理であることを特徴とする請求項15に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン生成方法。【請求項17】前記ε遷移のない1 bｙｔeで遷移するNFAから指定された処理バイト数で遷移を行うNFAへの変換は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成するか、入力された文字列のどの位置でパターンが一致したかは単独では判別できないNFAを生成するかを利用目的に応じて選択できる、ことを特徴とする請求項15又は請求項16に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン生成方法。【請求項18】前記正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAは、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、1-bｙｔe NFAから指定された処理バイト数で遷移を行うMｕlｔibｙｔe NFAへの変換が容易になる、ことを特徴とする請求項15乃至請求項17いずれか一つに記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン生成方法。【請求項19】正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する第二NFA生成処理を有することを特徴とする状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。【請求項20】到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトン、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少ないため回路規模が削減できる有限オートマトンのいずれかを選択して生成することができることを特徴とする請求項19に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。【請求項21】入力された正規表現を記憶し、前記記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFAへ変換し、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換し、前記変換したNFAを記憶し、前記記憶されたNFAから、そのハードウェア回路を記述するハードウェア記述言語を生成し、そのハードウェア記述言語を記憶することを特徴とする状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。【請求項22】さらに、前記ε遷移のない1 bｙｔeで遷移するNFAから指定された処理バイト数で遷移を行うNFAへの変換は、前記第二NFA生成処理であることを特徴とする請求項21に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。【請求項23】前記ε遷移のない1 bｙｔeで遷移するNFAから指定された処理バイト数で遷移を行うNFAへの変換は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成する処理か、入力された文字列のどの位置でパターンが一致したかを単独では判別できないNFAを生成する処理かを利用目的に応じて選択できる、ことを特徴とする請求項21又は請求項22に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。【請求項24】前記正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAは、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、ε遷移のない1 bｙｔeで遷移するNFAから指定された処理バイト数で遷移を行うNFAへの変換が容易になる、ことを特徴とする請求項21乃至請求項23いずれか一つに記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用有限オートマトン回路生成方法。【請求項25】正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する第三NFA生成処理をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。【請求項26】到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトン、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少ないため回路規模が削減できる有限オートマトンのいずれかを選択して生成する処理をコンピュータに実行させることを特徴とする請求項25に記載のマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。【請求項27】入力された正規表現を記憶する正規表現記憶処理と、前記記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFAへ変換する1-bｙｔe NFA変換処理と、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換するMｕlｔibｙｔe NFA変換処理と、前記変換したNFAを記憶するNFA記憶処理と、をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。【請求項28】前記Mｕlｔibｙｔe NFA変換処理は、前記第三NFA生成処理をコンピュータに実行させることを特徴とする請求項27に記載のマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。【請求項29】前記Mｕlｔibｙｔe NFA変換処理は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成するか、入力された文字列のどの位置でパターンが一致したかを単独では判別できないNFAを生成するかを利用目的に応じて選択できる、ことを特徴とする請求項27又は請求項28に記載のマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。【請求項30】前記1-bｙｔe NFA変換処理において、正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Mｕlｔibｙｔe NFA変換処理が簡略化できる、ことを特徴とする請求項27乃至請求項29いずれか一つに記載のマルチバイト処理向け文字列照合用有限オートマトン生成プログラム。【請求項31】正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する第四NFA生成処理をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。【請求項32】到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できる有限オートマトン、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記有限オートマトンよりも少ないため回路規模が削減できる有限オートマトンのいずれかを選択して生成する処理をコンピュータに実行させることを特徴とする請求項31に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。【請求項33】入力された正規表現を記憶する正規表現記憶処理と、前記正規表現記憶手段に記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFAへ変換する1-bｙｔe NFA変換処理と、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換するMｕlｔibｙｔe NFA変換処理と、 Mｕlｔibｙｔe NFA変換処理で変換したNFAを記憶するNFA記憶処理と、 Mｕlｔibｙｔe NFA変換処理で変換したNFAから、そのハードウェア回路を記述するハードウェア記述言語を生成するHDL変換処理と、 HDL変換処理で変換したハードウェア記述言語を記憶するHDL記憶処理と、をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。【請求項34】前記Mｕlｔibｙｔe NFA変換処理は、前記第四NFA生成処理をコンピュータに実行させることを特徴とする請求項33に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。【請求項35】前記Mｕlｔibｙｔe NFA変換処理は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成するか、入力された文字列のどの位置でパターンが一致したかを単独では判別できないNFAを生成するかを利用目的に応じて選択できる、ことを特徴とする請求項33又は請求項34に記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。【請求項36】前記1-bｙｔe NFA変換処理において、正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Mｕlｔibｙｔe NFA変換処理が簡略化できる、ことを特徴とする請求項33乃至請求項35いずれか一つに記載のマルチバイト処理向け文字列照合用有限オートマトン回路生成プログラム。【請求項37】請求項9から請求項12に記載の有限オートマトン回路生成装置、または、請求項21から請求項24に記載の有限オートマトン回路生成方法、または、請求項33から請求項36に記載の有限オートマトン回路生成プログラムを用いて生成したハードウェア記述言語を用いて、再構成可能ハードウェアデバイス上に前記有限オートマトン回路を用いることを特徴とするパターンマッチング装置。【請求項38】請求項7から請求項12に記載の有限オートマトン回路生成装置に加え、前記有限オートマトン回路生成装置で生成したハードウェア記述言語から、再構成ハードウェアデバイスの構成情報であるCｏnfigｕｒaｔiｏn daｔaを生成するCｏnfigｕｒaｔiｏn daｔa変換手段と、を備え、前記生成したCｏnfigｕｒaｔiｏn daｔaを用いて再構成可能ハードウェアデバイス上に前記有限オートマトン回路を用いることを特徴とするパターンマッチング装置。【請求項39】請求項7から請求項12に記載の有限オートマトン回路生成装置、または、請求項19から請求項24に記載の有限オートマトン回路生成方法、または、請求項31から請求項36に記載の有限オートマトン回路生成プログラムを用いて生成したハードウェア記述言語を用いて構成した、再構成可能ハードウェアデバイス上のマルチバイト処理向け文字列照合用有限オートマトン回路。【請求項40】請求項7から請求項12に記載の有限オートマトン回路生成装置に加え、前記有限オートマトン回路生成装置で生成したハードウェア記述言語から、再構成ハードウェアデバイスの構成情報であるCｏnfigｕｒaｔiｏn daｔaを生成するCｏnfigｕｒaｔiｏn daｔa変換手段と、を備え、前記生成したCｏnfigｕｒaｔiｏn daｔaを用いて再構成可能ハードウェアデバイス上のマルチバイト処理向け文字列照合用有限オートマトン回路。」 2.本件補正後の特許請求の範囲の記載これに対し,本件補正により,特許請求の範囲は以下のとおり補正された。(なお,下線は補正の個所を示すものとして審判請求人が付したものである。) 「【請求項1】正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFA(Nｏn-deｔeｒminiｓｔic Finiｔe Aｕｔｏmaｔｏn)を生成する手段を有するマルチバイト処理向け文字列照合用NFA生成装置。【請求項2】到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できるNFA、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記NFAよりも少ないため回路規模が削減できるNFAのいずれかを選択して生成することができる手段を有することを特徴とする請求項1に記載のマルチバイト処理向け文字列照合用NFA生成装置。【請求項3】入力された正規表現を記憶する正規表現記憶手段と、前記正規表現記憶手段に記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFAへ変換する1-bｙｔe NFA変換手段と、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換するMｕlｔibｙｔe NFA変換手段と、 Mｕlｔibｙｔe NFA変換手段で変換したNFAを記憶するNFA記憶手段と、を備えることを特徴とするマルチバイト処理向け文字列照合用NFA生成装置。【請求項4】前記Mｕlｔibｙｔe NFA変換手段は請求項1又は請求項2に記載のNFAを生成する手段を備えることを特徴とする請求項3に記載のマルチバイト処理向け文字列照合用NFA生成装置。【請求項5】前記Mｕlｔibｙｔe NFA変換手段は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成するか、入力された文字列のどの位置でパターンが一致したかは単独では判別できないNFAを生成するかを利用目的に応じて選択できる、ことを特徴とする請求項3又は請求項4に記載のマルチバイト処理向け文字列照合用NFA生成装置。【請求項6】前記1-bｙｔe NFA変換手段において、正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Mｕlｔibｙｔe NFA変換手段での変換処理が簡略化できる、ことを特徴とする請求項3乃至請求項5いずれか一つに記載のマルチバイト処理向け文字列照合用NFA生成装置。【請求項7】正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できるNFAを生成するNFA生成手段を有することを特徴とするマルチバイト処理向け文字列照合用NFA回路生成装置。【請求項8】到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できるNFA、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記NFAよりも少ないため回路規模が削減できるNFAのいずれかを選択して生成することができることを特徴とする請求項7に記載のマルチバイト処理向け文字列照合用NFA回路生成装置。【請求項9】入力された正規表現を記憶する正規表現記憶手段と、前記正規表現記憶手段に記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFA(Nｏn-deｔeｒminiｓｔic Finiｔe Aｕｔｏmaｔｏn)へ変換する1-bｙｔe NFA変換手段と、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換するMｕlｔibｙｔe NFA変換手段と、 Mｕlｔibｙｔe NFA変換手段で変換したNFAを記憶するNFA記憶手段と、 Mｕlｔibｙｔe NFA変換手段で変換したNFAから、そのハードウェア回路を記述するハードウェア記述言語を生成するHDL変換手段と、 HDL変換手段で変換したハードウェア記述言語を記憶するHDL記憶手段と、を備えることを特徴とするマルチバイト処理向け文字列照合用NFA回路生成装置。【請求項10】前記Mｕlｔibｙｔe NFA変換手段は、正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できるNFAを生成するNFA生成手段を有することを特徴とする請求項9記載のマルチバイト処理向け文字列照合用NFA回路生成装置。【請求項11】前記Mｕlｔibｙｔe NFA変換手段は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成するか、入力された文字列のどの位置でパターンが一致したかは単独では判別できないNFAを生成するかを利用目的に応じて選択できる、ことを特徴とする請求項9又は請求項10に記載のマルチバイト処理向け文字列照合用NFA回路生成装置。【請求項12】前記1-bｙｔe NFA変換手段において、正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Mｕlｔibｙｔe NFA変換手段での変換処理が簡略化できる、ことを特徴とする請求項9乃至請求項11いずれか一つに記載のマルチバイト処理向け文字列照合用NFA回路生成装置。【請求項13】 CPU、入出力装置、データ処理装置および記憶装置から構成されるマルチバイト処理向け文字列照合用NFA回路生成装置であって、プログラム制御により動作する該マルチバイト処理向け文字列照合用NFA回路生成装置のデータ処理装置が、正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成するNFA生成処理を実行することを特徴とするマルチバイト処理向け文字列照合用NFA生成方法。【請求項14】到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できるNFA、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記NFAよりも少ないため回路規模が削減できるNFAのいずれかを選択して生成することができることを特徴とする請求項13に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用NFA生成方法。【請求項15】 CPU、入出力装置、データ処理装置および記憶装置から構成されるマルチバイト処理向け文字列照合用NFA回路生成装置であって、プログラム制御により動作する該マルチバイト処理向け文字列照合用NFA回路生成装置において、入力された正規表現を前記記憶装置に記憶し、前記記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFAへ前記データ処理装置が変換し、前記データ処理装置が前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換し、前記変換したNFAを前記記憶装置が記憶する、ことを特徴とするマルチバイト処理向け文字列照合用NFA生成方法。【請求項16】前記データ処理装置が、前記ε遷移のない1 bｙｔeで遷移するNFAから指定された処理バイト数で遷移を行うNFAへの変換は、前記NFA生成処理であることを特徴とする請求項15に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用NFA生成方法。【請求項17】前記データ処理装置が、前記ε遷移のない1 bｙｔeで遷移するNFAから指定された処理バイト数で遷移を行うNFAへの変換は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成するか、入力された文字列のどの位置でパターンが一致したかは単独では判別できないNFAを生成するかを利用目的に応じて選択できる、ことを特徴とする請求項15又は請求項16に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用NFA生成方法。【請求項18】前記データ処理装置が、前記正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAは、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、1-bｙｔe NFAから指定された処理バイト数で遷移を行うMｕlｔibｙｔe NFAへの変換が容易になる、ことを特徴とする請求項15乃至請求項17いずれか一つに記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用NFA生成方法。【請求項19】前記データ処理装置は、正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する第二NFA生成処理を実行することを特徴とするマルチバイト処理向け文字列照合用NFA回路生成方法。【請求項20】前記データ処理装置は、到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できるNFA、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記NFAよりも少ないため回路規模が削減できるNFAのいずれかを選択して生成することができることを特徴とする請求項19に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用NFA回路生成方法。【請求項21】 CPU、入出力装置、データ処理装置および記憶装置から構成されるマルチバイト処理向け文字列照合用NFA回路生成装置であって、プログラム制御により動作する該マルチバイト処理向け文字列照合用NFA回路生成装置において、入力された正規表現を前記記憶装置が記憶し、前記データ処理装置が、前記記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFAへ変換し、および前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換し、前記変換したNFAを前記記憶装置が記憶し、前記データ処理装置が、前記記憶されたNFAから、そのハードウェア回路を記述するハードウェア記述言語を生成し、そのハードウェア記述言語を前記記憶装置が記憶することを特徴とする状態遷移マシンを用いたマルチバイト処理向け文字列照合用NFA回路生成方法。【請求項22】前記データ処理装置が、前記ε遷移のない1 bｙｔeで遷移するNFAから指定された処理バイト数で遷移を行うNFAへの変換は、正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する第二NFA生成処理であることを特徴とする請求項21に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用NFA回路生成方法。【請求項23】前記データ処理装置が、前記ε遷移のない1 bｙｔeで遷移するNFAから指定された処理バイト数で遷移を行うNFAへの変換は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成する処理か、入力された文字列のどの位置でパターンが一致したかを単独では判別できないNFAを生成する処理かを利用目的に応じて選択できる、ことを特徴とする請求項21又は請求項22に記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用NFA回路生成方法。【請求項24】前記データ処理装置が、前記正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAは、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、ε遷移のない1 bｙｔeで遷移するNFAから指定された処理バイト数で遷移を行うNFAへの変換が容易になる、ことを特徴とする請求項21乃至請求項23いずれか一つに記載の状態遷移マシンを用いたマルチバイト処理向け文字列照合用NFA回路生成方法。【請求項25】正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する第三NFA生成処理をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用NFA生成プログラム。【請求項26】到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できるNFA、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記NFAよりも少ないため回路規模が削減できるNFAのいずれかを選択して生成する処理をコンピュータに実行させることを特徴とする請求項25に記載のマルチバイト処理向け文字列照合用NFA生成プログラム。【請求項27】入力された正規表現を記憶する正規表現記憶処理と、前記記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFAへ変換する1-bｙｔe NFA変換処理と、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換するMｕlｔibｙｔe NFA変換処理と、前記変換したNFAを記憶するNFA記憶処理と、をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用NFA生成プログラム。【請求項28】前記Mｕlｔibｙｔe NFA変換処理は、正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する第三NFA生成処理をコンピュータに実行させることを特徴とする請求項27に記載のマルチバイト処理向け文字列照合用NFA生成プログラム。【請求項29】前記Mｕlｔibｙｔe NFA変換処理は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成するか、入力された文字列のどの位置でパターンが一致したかを単独では判別できないNFAを生成するかを利用目的に応じて選択できる、ことを特徴とする請求項27又は請求項28に記載のマルチバイト処理向け文字列照合用NFA生成プログラム。【請求項30】前記1-bｙｔe NFA変換処理において、正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Mｕlｔibｙｔe NFA変換処理が簡略化できる、ことを特徴とする請求項27乃至請求項29いずれか一つに記載のマルチバイト処理向け文字列照合用NFA生成プログラム。【請求項31】正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する第四NFA生成処理をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用NFA回路生成プログラム。【請求項32】到達した終了状態によって入力された文字列のどの位置でパターンに一致したかを単独で判別できるNFA、あるいはどの位置でパターンに一致したかを単独では判別できないが、状態数は前記NFAよりも少ないため回路規模が削減できるNFAのいずれかを選択して生成する処理をコンピュータに実行させることを特徴とする請求項31に記載のマルチバイト処理向け文字列照合用NFA回路生成プログラム。【請求項33】入力された正規表現を記憶する正規表現記憶処理と、前記正規表現記憶手段に記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFAへ変換する1-bｙｔe NFA変換処理と、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換するMｕlｔibｙｔe NFA変換処理と、 Mｕlｔibｙｔe NFA変換処理で変換したNFAを記憶するNFA記憶処理と、 Mｕlｔibｙｔe NFA変換処理で変換したNFAから、そのハードウェア回路を記述するハードウェア記述言語を生成するHDL変換処理と、 HDL変換処理で変換したハードウェア記述言語を記憶するHDL記憶処理と、をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用NFA回路生成プログラム。【請求項34】前記Mｕlｔibｙｔe NFA変換処理は、正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する第四NFA生成処理をコンピュータに実行させることを特徴とする請求項33に記載のマルチバイト処理向け文字列照合用NFA回路生成プログラム。【請求項35】前記Mｕlｔibｙｔe NFA変換処理は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成するか、入力された文字列のどの位置でパターンが一致したかを単独では判別できないNFAを生成するかを利用目的に応じて選択できる、ことを特徴とする請求項33又は請求項34に記載のマルチバイト処理向け文字列照合用NFA回路生成プログラム。【請求項36】前記1-bｙｔe NFA変換処理において、正規表現から変換するε遷移のない1 bｙｔeで遷移するNFAに対し、終了状態からは自身も含めた他の状態へ遷移しないという制約を加えることにより、前記Mｕlｔibｙｔe NFA変換処理が簡略化できる、ことを特徴とする請求項33乃至請求項35いずれか一つに記載のマルチバイト処理向け文字列照合用NFA回路生成プログラム。【請求項37】請求項9から請求項12に記載のNFA回路生成装置、または、請求項21から請求項24に記載のNFA回路生成方法、または、請求項33から請求項36に記載のNFA回路生成プログラムを用いて生成したハードウェア記述言語を用いて、再構成可能ハードウェアデバイス上に前記NFA回路を用いることを特徴とするパターンマッチング装置。【請求項38】請求項7から請求項12に記載のNFA回路生成装置に加え、前記NFA回路生成装置で生成したハードウェア記述言語から、再構成ハードウェアデバイスの構成情報であるCｏnfigｕｒaｔiｏn daｔaを生成するCｏnfigｕｒaｔiｏn daｔa変換手段と、を備え、前記生成したCｏnfigｕｒaｔiｏn daｔaを用いて再構成可能ハードウェアデバイス上に前記NFA回路を用いることを特徴とするパターンマッチング装置。【請求項39】請求項7から請求項12に記載のNFA回路生成装置、または、請求項19から請求項24に記載のNFA回路生成方法、または、請求項31から請求項36に記載のNFA回路生成プログラムを用いて生成したハードウェア記述言語を用いて構成した、再構成可能ハードウェアデバイス上のマルチバイト処理向け文字列照合用NFA回路。【請求項40】請求項7から請求項12に記載のNFA回路生成装置に加え、前記NFA回路生成装置で生成したハードウェア記述言語から、再構成ハードウェアデバイスの構成情報であるCｏnfigｕｒaｔiｏn daｔaを生成するCｏnfigｕｒaｔiｏn daｔa変換手段と、を備え、前記生成したCｏnfigｕｒaｔiｏn daｔaを用いて再構成可能ハードウェアデバイス上のマルチバイト処理向け文字列照合用NFA回路。」 3.本件補正の内容及び目的について本件補正は,特許請求の範囲の記載を本件補正による補正前の請求項1?40に対し,以下のとおり補正するものと認められる。 (1)上記拒絶理由通知において,請求項2,4?6,8,10?12,14,16?18,20,22?24,26,28?30,32,34?36につき,「NFA」と「有限オートマトン」とが表現が統一されておらず不適切である旨の指摘がなされ,上記拒絶査定においても当該拒絶理由が解消されていなかったところ,請求項1?40において「有限オートマトン」と記載していたものを,下位概念である「NFA」に統一するとともに,請求項1において「NFA」が「Nｏn-deｔeｒminiｓｔic Finiｔe Aｕｔｏmaｔｏn」の略であることを明確化する。 (2)上記拒絶理由通知において,請求項10,22,28,34における「NFA生成手段」,「第二NFA生成処理」,「第三NFA生成処理」,「第四NFA生成処理」が前記されておらず,記載が整合しない旨の指摘がなされ,上記拒絶査定においても当該拒絶理由が解消されていなかったところ,当該記載について「正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する」旨を明確化する。 (3)上記拒絶理由通知において,請求項13?24の各ステップにおける動作の主体が特定されておらず,請求項に係る発明を明確に把握することができない旨の指摘がなされ,上記拒絶査定においても当該拒絶理由が解消されていなかったところ,当該請求項における各ステップの動作主体を明確化する。 4.補正の適否の結論以上のとおり,本件補正は,いずれも明りょうでない記載を明確化するものに該当するから,特許法第17条の2第5項第4号に掲げる「明りようでない記載の釈明(拒絶理由通知に係る拒絶の理由に示す事項についてするものに限る。) 」を目的としてなされたものといえる。第3 本願発明について上記のとおり,本件補正は補正要件を満たすから,本願の請求項27に係る発明(以下「本願発明」という。)は,本件補正による特許請求の範囲の請求項27に記載された事項により特定される,次のとおりのものと認める。「入力された正規表現を記憶する正規表現記憶処理と、前記記憶された正規表現からε遷移のない1 bｙｔeで遷移するNFAへ変換する1-bｙｔe NFA変換処理と、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換するMｕlｔibｙｔe NFA変換処理と、前記変換したNFAを記憶するNFA記憶処理と、をコンピュータに実行させることを特徴とするマルチバイト処理向け文字列照合用NFA生成プログラム。」第4 原査定の拒絶の理由について原査定の拒絶理由の理由3は,本願発明は後記する引用例に記載された発明に基いて当業者が容易に発明することができたものであるから,特許法第29条第2項の規定により特許を受けることができないというものである。第5 当審の判断 1.引用例について 1-1.引用例について原査定の拒絶理由通知で引用した引用例(山垣則夫,外1名,NFA埋め込み型パターンマッチング回路におけるマルチバイト処理化に関する検討,電子情報通信学会技術研究報告,2007年9月13日,Vｏl.107,Nｏ.225,ｐｐ.65?70(RECONF2007-26))には,以下のことが記載されている。(以下「引用例摘記事項」という。なお,下線は当審において付したものである。) (ア)「あらまし近年,FPGAのようなReconfigurable Deviceに,非決定性有限オートマトン(NFA:Non-deterministic Finite Automaton)と呼ばれる汎用性の高い状態遷移アルゴリズムを回路化し,直接埋め込むことで,高速なパターンマッチを実現する研究がなされている.このようなNFA埋め込み型パターンマッチング回路は,ネットワーク侵入検知システム(NIDS:Network Intrusion Detection System)等の高速検索が求められる装置内に組み込まれることが想定されるため,その検索スループットと回路規模が重要な課題である.そこで,本稿では,これらの課題に対し,行列演算を利用することで1 byte処理のNFAを,その状態数を増加させることなく,任意のバイト数で処理を行うNFAへ容易に変換するマルチバイトNFA生成手法を提案する.」(第65頁第1行?第7行) (イ)「1.はじめに近年,インターネットのブロードバンド化により,オンラインショッピングやネットバンク,オンラインゲーム等,様々なアプリケーションの利用が広まっている.その一方で,コンピュータウィルスや不正侵入,攻撃といった問題も増加しており,セキュリティの確保が重要課題となっている.特に,10Gbps級のネットワーク環境における高度なセキュリティ機能を実現するには,ネットワークプロトコル処理だけでなく,コンテンツチェック等のアプリケーションレイヤ処理の高速化が必須[1]であり,多様化する攻撃や侵入に対応すべく,正規表現[2]を用いた柔軟で高速なパターンマッチング処理の実現が望まれる. 一般的に,正規表現を用いたパターンマッチングは,有限オートマトン(FA: Finite Automaton)と呼ばれる状態遷移マシンを用いて行われる.FAは,ある状態における入力による状態遷移先が複数存在する非決定性有限オートマトン(NFA: Non-deterministic FA)と,遷移先が1つだけの決定性有限オートマトン(DFA: Deterministic FA)に分類できる.通常,NFAは正規表現から変換でき,DFAはNFAから変換可能であるが,正規表現に含まれる文字数nに対して,NFAの状態数はn,DFAの状態数は最大2^(n)となる[3][4].このため,DFAをハードウェアによって実装する場合,状態数の増加に伴って遷移数も爆発的に増加してしまうため,その状態数最大が構成上ボトルネックとなる. そこで,NFAを回路化し,再構成可能なハードウェアデバイスであるFPGAに直接埋め込むことで高速なパターンマッチを実現する手法が提案されている[5].このようなNFA埋め込み型パターンマッチング回路は,正規表現から変換したNFAの各状態を,単純な構成の基本構成素子として実現し,多数の基本構成素子を状態遷移に応じて接続することで,ハードウェアにおける同時並列処理の利点を活かした高速な正規表現検索を行うことが可能となる. また,さらなる検索スループットの向上や回路規模の削減に関する研究も多くなされている[6][7][8][9].特に,文献[6][8]では,1クロックサイクルあたり複数バイト(文字)を処理するNFA回路を利用することで,検索スループットの向上を目指した手法が提案されている.しかし,これらの方式では,1つの検索パターンに対して,同時に処理するバイト数分のNFAが必要である上,厳密一致(Exact Match)を用いた場合しか例示されておらず,状態数の削減と正規表現のサポートが課題であると考えられる. そこで,筆者らは,これらの課題を解決するため,マルチバイト処理のNFA生成手法を提案している[10].本手法は,NFA回路をハードウェアに埋め込む前段階の処理であり,1 byte処理のNFAから状態数を変化させることなく任意のマルチバイト処理のNFAに変換することが可能である.このため,処理バイト数に応じた検索スループットの向上と,利用レジスタ数を抑制することによる回路規模の削減が期待できる.さらに,本手法は,1 byte処理のNFAに対して処理を行うため,全ての正規表現に対応することが可能である.本稿では,本手法を用いて生成したマルチバイトNFA回路の性能評価について報告する.」(第65頁左欄第1行?第66頁左欄第27行) (ウ)「2.1. NFA NFAとは,ある状態における入力による状態遷移先が複数存在する状態遷移マシンであり,grepやperl等における正規表現を用いたパターンマッチングで利用されている.一般的には,(1) 正規表現をSyntax Tree(構文木)に変換し,(2) Syntax Treeの各ノードに対して,NFAの基本パターン(図1)を再帰的に適用する,ことで正規表現からNFAを構築することができる[4].なお,図1中のN_(1),N_(2)は正規表現,I,Fは初期状態,終了状態を示し,εは入力を読み込まずに次の状態への遷移が可能なε遷移(ε-transition)示している.例えば,正規表現“a(bc)(d\|e)”を上記の手法に従って変換すると,図2に示すようなNFAが得られる. なお,NFAではこのε遷移を除去することが可能であり,この操作をε閉包(ε-closure)と呼ぶ[3][4].」(第66頁左欄第36行?第50行) (エ)「2.2 マルチバイト処理 NFA埋め込み型パターンマッチング回路の検索スループット(Throughput)[Mbps]は,1クロックサイクルあたりに処理できる文字数m(=8×m[bits])と動作周波数K[MHz]によって,次式で与えられる. Throughput=8×m×K (1) 2.2節で示したNFA回路[5]では,1クロックサイクルあたりに1文字(m=1)を処理するため,回路の動作周波数Kが検索スループットに直接影響する. そこで,1クロックサイクルに複数の文字を処理させることで,検索スループットの向上を目指した手法が提案されている[6][7][8]. 文献[6][8]では,入力された複数文字の識別を行うCharacter Decorderに違いはあるものの,図5に示すようなアーキテクチャを提案している.ここで,図5は4 bytes処理時の概念図であり,図中の‘’は任意の文字を示す.これらの手法では,入力文字数であるN文字を遷移条件としたNFAを構築し,それを回路化することでマルチバイト処理を行う.」(第66頁右欄第25行?第67頁左欄第5行) (オ)「3. 提案方式本章では,新たなアプローチを採用したマルチバイト処理化手法を提案する.以下,1 byte処理のNFAを“Sigle Byte NFA”,マルチバイト処理のNFAを“Multibyte NFA”(k bytes処理であれば,“k-byte NFA”),ε遷移のないNFAを“ε-free NFA”,ε遷移のあるNFAを“ε-NFA”と呼ぶものとする. 3.1. 概要提案するMultibyte NFA変換手法は,1 byte処理のε-free NFAを,状態数を変化させずに任意のMultibyte NFAへ変換する手法であり,NFA回路をハードウェアデバイスに埋め込む前段階の処理として必要な手順である.本提案手法を用いて正規表現からNFA回路を生成する際の処理フローを図6に示す.正規表現からNFA回路の生成処理は,(1) 正規表現から1 byte処理のε-free NFAの生成と,(2) 生成したε-free NFAからMultibyte NFAへの変換,の2つに大きく分類することができ,本提案手法は,図6の処理(2)(図6の太線)に相当する.また,処理(1)は,文献[4]等の従来手法を用いることで実現できるため,詳細については省略する.なお,2.2節で述べたNFA回路構築手法のアプローチは図6の点線部分に相当する. 具体的に,処理(2)では,NFAを表すNFA記述行列と呼ぶ行列を定義し,処理(1)で生成した1 byte処理のε-free NFAをNFA記述行列によって記述する.続いて,新たに定義する演算規則に従ってNFA記述行列を用いた行列演算を行うことで,任意のMultibyte NFAへの変換を行う.最後に,得られたNFAを回路化し,ハードウェアに埋め込むことで,NFA埋め込み型パターンマッチング回路を実現する. 本提案手法の特徴を以下に示す. 1. 任意のバイト数で処理できるMultibyte NFA埋め込み型パターンマッチング回路が構成可能. 2. 既存手法とは異なり,生成されるMultibyte NFAの状態数はSingle Byte NFAの状態数と等しい. 3. Single Byte NFAを生成できる全ての正規表現に対して適用可能.」(第67頁左欄第23行?同頁右欄第30行) (カ)「3.3. 変換手法 NFA記述行列を用いて,Single Byte NFAから所望のk-byte NFAを生成する.例えば,図7のSingle Byte NFAから2-byte NFAを生成する場合,状態1から状態3への遷移は,状態1から状態2への遷移(‘a’)と状態2から状態3への遷移(‘b’)を結合した文字列“ab”となる.つまり,状態iから状態jへの遷移条件は,元のNFAの状態iから状態kへの遷移と,状態kから状態jへの遷移を結合した文字列となる(i, j, k=1,…, n).」(第68頁左欄第17行?第25行) また,上記(ア)?(カ)に加え,引用例の図6(第68頁左上)及び図7(第68頁右上)にはそれぞれ以下のことが記載されているものと認められる。 (キ)(1)「Regular Expressions」から,「Syntax Tree」,「ε-NFA(Single Byte NFA)」を経て,「ε-free NFA(Single Byte NFA)」に至る処理と,(2)該「ε-free NFA(Single Byte NFA)」から「Multibyte NFA」へと至る処理により,該「ε-free NFA(Single Byte NFA)」から「NFA logic(single byte)」が,該「Multibyte NFA」から「NFA logic(multibyte)」が生成される提案手法の処理フロー。 (ク)Initial Stateを状態1,Final Stateを状態5とし,状態1から状態2の遷移(‘a’),状態1から4への遷移(‘a’),状態2から状態3への遷移(‘b’),状態3から状態2への遷移(‘c’),状態3から状態4への遷移(‘c’)及び状態4から状態5への遷移(‘d,e’)からなる「正規表現“a(bc)(d\|e)”のSingle Byte NFA」の図 1-2.引用発明について引用例に記載される手法は,1 byte処理のNFAを,「任意の」バイト数で処理を行うNFAであって(引用例摘記事項(ア)),「所望の」k-byte NFAに変換することができるものである(引用例摘記事項(カ))。ここで,「k-byte NFA」は,k bytes処理のMultibyte NFAを意味し(引用例摘記事項(オ)),Multibyte NFAはNFAの一種であることから,該手法は1 byte処理のNFAを「指定されたバイト数で処理を行うNFAへ変換する」ものであることは当業者にとって自明である。そうすると,引用例摘記事項(ア)?(ク)から,引用例には以下の発明が開示されているものと認められる。「正規表現から1 byte処理のε遷移のないNFAを生成する処理と、前記1 byte処理のε遷移のないNFAから、指定されたバイト数で処理を行うNFAへ変換する処理と、を実行することを特徴とするマルチバイト処理向けパターンマッチング用NFA生成手法。」 (以下「引用発明」という。) 2.対比 2-1.引用発明と本願発明とを対比する。 (ア)引用発明の「正規表現」,「NFA」,「指定されたバイト数」は,本願発明の「正規表現」,「NFA」,「指定された処理バイト数」にそれぞれ相当する。 (イ)引用発明の「1 byte処理のε遷移のない」NFAと本願発明の「ε遷移のない1 bｙｔeで遷移する」NFAとは,引用例摘記事項(ウ),(オ)と本願の発明の詳細な説明における, 「(前略)通常、NFAには、入力を読み込まずに次の状態への遷移が可能なε遷移(ε-ｔｒanｓiｔiｏn)という特殊な遷移が含まれるが、上記のような直接NFAを組み込んだパターンマッチング回路(以下、NFA回路と呼ぶ)では、ε遷移を含まないNFAを用いる必要がある。このようなNFAからε遷移を除去する操作をε閉包(ε-clｏｓｕｒe)と言う(非特許文献1、非特許文献2)。」(【0005】段落) との記載,及び「(前略)また、1-bｙｔe NFA変換部21は、正規表現記憶部31から読み出した正規表現を、例えば非特許文献1に記載されたような従来の手法を用いてε遷移のない1-bｙｔe NFAに変換し、(後略)」(【0044】段落) との記載からみて,「ε遷移のない」NFAという点で共通する。さらに,本願の発明の詳細な説明には,【発明の効果】として, 「【0028】第1の効果は、1 bｙｔeで処理するNFAの遷移条件そのものを複数バイトに拡張させたNFAでも、入力した文字列のどの位置でパターンに一致したかを単独で判別できることにある。【0029】その理由は、1 bｙｔeで処理するNFAから指定された処理バイト数のNFAへ変換する際に、終了状態を処理バイト数に応じて増加させることで、どの終了状態に到達したかにより、入力された文字列のどの位置でパターンに一致したかが判別できるためである。」と記載され,本願発明における「1 bｙｔeで遷移するNFA」とは,「1 bｙｔeで処理するNFA」と同義のものと解される。また,引用例では,引用例摘記事項(カ),(ク)のとおり,「Single Byte NFA」すなわち「1 byte 処理のNFA」(引用例摘記事項(オ)には「1 byte処理のNFA」をSingle Byte NFAと呼ぶことが記載されている。)において,ある状態からある状態へ「a」,「b」,・・・等の1文字で遷移していることから,「1 byte処理のNFA」が1文字で遷移するNFAの意で用いられていることは明らかである。一方,本願発明の「前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換するMｕlｔibｙｔe NFA変換処理」に対応する本願の発明の詳細な説明の記載として, 「【0055】 (前略)Mｕlｔibｙｔe NFA変換部22は、変換手段21から受け取ったε遷移のない1-bｙｔe NFAを処理バイト数BTのMｕlｔibｙｔe NFAへ変換する(ステップA6)。【0056】図5は、ステップA6のより詳細な動作を説明するための流れ図である。また、例として、図24に示す正規表現“a(bc)(d｜e)”から生成したε遷移のない1-bｙｔe NFAの変換例を挙げて説明する。」とあり,本願発明の「ε遷移のない1 bｙｔeで遷移するNFA」が,発明の詳細な説明では「ε遷移のない1-bｙｔe NFA」として説明されるところ,該「ε遷移のない1-bｙｔe NFA」の例を示す図24には状態0から状態1への「a」での遷移等の1文字で遷移するNFAが表現された図が記載されている。そうすると,引用発明の「1 byte処理の」NFAと本願発明の「1 bｙｔeで遷移する」NFAとは,単なる表現上の差異にすぎず,実質的な意味において相違しないものと解される。なお,上記のとおり,本願発明では「1-bｙｔeで遷移するNFA」に関して「1-bｙｔe NFA」と説明されているところ,一般に「1-bｙｔe」を「Single Byte」と表記することは慣用的な言い換え表現であることからみても,引用発明の「1 byte処理のNFA」すなわち「Single Byte NFA」は,本願発明の「1 bｙｔeで遷移するNFA」と解すべきものである。以上を総合すると,引用発明の「1 byte処理のε遷移のない」NFAは,本願発明の「ε遷移のない1 bｙｔeで遷移する」NFAに相当する。 (ウ)引用発明の指定されたバイト数「で処理を行う」NFAについては,上記2-1(イ)で検討したのと同様,引用発明の所定のバイト数「で処理を行う」ことと本願発明の所定の処理バイト数「で遷移を行う」こととが,表現上の相違にすぎないから,本願発明の指定された処理バイト数「で遷移を行う」NFAに相当する。 (エ)正規表現とは,文字列の集合を記述するための記法を指す語として慣用のものであるところ,引用例は,該正規表現からNFA回路を生成し,パターンマッチング回路を実現しようとする提案であることから(引用例摘記事項(オ)),引用発明は,文字列の集合についてのパターンマッチングすなわち照合を行うことに係る手法と認められる。そして,本願の発明の詳細な説明にも, 「【0003】従来、正規表現を用いた文字列照合(パターンマッチ)は、有限オートマトン(FA: Finiｔe Aｕｔｏmaｔｏn)と呼ばれる状態遷移マシンを用いて行われる。(後略)」と記載され,正規表現を用いた文字列照合を行うことが,パターンマッチを意味するものとされていることからみても,引用発明と本願発明とは,「文字列照合用NFAを生成する処理アルゴリズム」である点で共通するといえる。また,該「NFA」が「マルチバイト処理向け」である点でも共通する。 2-2.してみると,引用発明と本願発明との一致点と相違点とは,以下のとおりである。 [一致点] 「正規表現からε遷移のない1 bｙｔeで遷移するNFAへ変換する1-bｙｔe NFA変換処理と、前記ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換するMｕlｔibｙｔe NFA変換処理と、を実行することを特徴とするマルチバイト処理向け文字列照合用NFAを生成する処理アルゴリズム。」 [相違点] 本願発明が,「入力された正規表現を記憶する正規表現記憶処理」,「前記変換したNFAを記憶するNFA記憶処理」とを備え,各処理を「コンピュータに実行させることを特徴とする」「プログラム」の発明であるのに対し,引用発明は,マルチバイト処理向け文字列照合用NFA生成の「手法」を開示するものであって,該「手法」に係る処理を「コンピュータに実行させ」ることや,処理を実行させる「プログラム」については明示されておらず,さらに,「入力された正規表現を記憶する正規表現記憶処理」,「前記変換したNFAを記憶するNFA記憶処理」を備えること,及び「1-bｙｔe NFA変換処理」を行う際に変換元を「前記記憶された正規表現から」とすることについては明示していない点。 3.判断以上の相違点について,以下に判断する。引用発明は,引用例摘記事項(ア)に記載されるとおり,行列演算を利用することで1 byte処理のNFAを,その状態数を増加させることなく,任意のバイト数で処理を行うNFAへ容易に変換するマルチバイトNFA生成手法を提案するものである。そして,一般に行列演算をコンピュータのプログラムで実行させることは周知の技術である。また,本願と引用発明は,上記一致点で示したように「マルチバイト処理向け文字列照合用NFAを生成する」処理アルゴリズムである点で一致しており,本願発明は該処理アルゴリズムをコンピュータのプログラムとして実現したものであることは明らかである。そして,一般にコンピュータのプログラムにおいては,処理対象として入力された情報や処理結果として出力された情報を記憶手段に格納することは技術常識にすぎないから,上記処理アルゴリズムをプログラム化するにあたり,上記相違点の「入力された正規表現を記憶する正規表現記憶処理」及び「前記変換したNFAを記憶するNFA記憶処理」を備えることに何ら技術的困難性はなく,また,「1-bｙｔe NFA変換処理」を行う際には,処理対象である変換元の正規表現を記憶手段から読み出して処理することになるのであるから,「前記記憶された正規表現から」とすることも,当業者であれば自明な構成であるといわざるを得ない。したがって,相違点に係る構成は,引用発明の処理アルゴリズムのプログラム化に伴う自明な構成でしかなく,本願発明には,その他にコンピュータのプログラムとしての創意工夫があるとはいえないから,単に引用発明の処理アルゴリズムをプログラム化したものでしかないことは明らかである。以上のとおりであるから,本願発明は,引用発明の処理アルゴリズムを周知技術に基づいてプログラム化したものであり,当業者であれば容易に想到し得たものである。また,本願発明の作用効果も,引用発明及び周知技術から当業者が予測できる範囲のものである。したがって,本願発明は,引用発明及び周知技術に基いて当業者が容易に発明をすることができたものであるから,特許を受けることができない。 4.請求人の主張についてなお,請求人は審判請求書において, 「本発明で開示している手法は、引用文献2とは異なり、一般的な正規表現を複数文字で処理可能なマルチバイト処理向けNFAへの変換手法を開示しており、変換したマルチバイト処理向けNFAは、入力された複数文字のどの位置でパターンに一致したかを判別可能なNFAとなります。具体的には、明細書[0054]から[0065]段落目に記載しているように、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別するNFAへ変換する請求項3、9、27におけるMｕlｔibｙｔe NFA変換手段、あるいは、請求項33におけるMｕlｔibｙｔe NFA変換処理によって生成されたNFAがこれを実現します。」と主張する。しかしながら,本願発明においては,「Mｕlｔibｙｔe NFA変換処理」が,「入力された複数文字のどの位置でパターンに一致したかを判別可能」である旨は何ら明示的な特定がなされていない。そして,本願発明に係る請求項27を引用する請求項28において,「前記Mｕlｔibｙｔe NFA変換処理は、正規表現を用いたパターンから、複数の文字数から成る遷移条件をもち、到達した終了状態によって入力された文字列のどの位置で前記パターンに一致したかを単独で判別できるNFAを生成する第三NFA生成処理をコンピュータに実行させることを特徴とする」として,「Mｕlｔibｙｔe NFA変換処理」を更に限定していること,また,請求項27を引用する請求項29において,「前記Mｕlｔibｙｔe NFA変換処理は、指定された動作モードにより、入力された文字列のどの位置でパターンが一致したかを単独で判別できるNFAを生成するか、入力された文字列のどの位置でパターンが一致したかを単独では判別できないNFAを生成するかを利用目的に応じて選択できる」と限定していることからみても,本願発明における「Mｕlｔibｙｔe NFA変換処理」とは,請求人が主張する「入力された複数文字のどの位置でパターンに一致したかを判別可能」なもののみならず,入力された文字列のどの位置でパターンが一致したかを単独では判別できないものをも含む上位概念を特定しようとするものと解される。そうすると,本願発明の「Mｕlｔibｙｔe NFA変換処理」は,「入力された複数文字のどの位置でパターンに一致したかを判別可能」であるか否かにかかわらず,「ε遷移のない1 bｙｔeで遷移するNFAを、指定された処理バイト数で遷移を行うNFAへ変換する」という点において,引用発明と相違するものではないから,上記請求人の主張を採用することはできない。第6 むすび以上のとおり,本願発明は,引用発明及び周知技術に基いて当業者が容易に発明をすることができたものであるから,他の請求項の発明について検討するまでもなく,特許法第29条第2項の規定により特許を受けることができない。したがって,本願は原査定で通知した拒絶理由によって拒絶されるべきものである。よって,結論のとおり審決する。
審理終結日	2015-02-19
結審通知日	2015-02-24
審決日	2015-03-09
出願番号	特願2010-503940(P2010-503940)
審決分類	P 1 8・ 121- Z (G06F)
最終処分	不成立
前審関与審査官	早川学
特許庁審判長	金子幸一
特許庁審判官	小太刀慶明須田勝巳
発明の名称	マルチバイト処理向け文字列照合用有限オートマトン生成システム
代理人	下坂直樹
代理人	机昌彦

プライバシーポリシーセキュリティーポリシー運営会社概要サービスに関しての問い合わせ