(57)【要約】  入力文字列から検出文字列の先端を含む先端文字列の位置情報と一致情報とを検出する先端検出手段と、入力文字列から検出文字列の終端を含む終端文字列の位置情報と一致情報とを検出する終端検出手段と、検出文字列において先端文字列と終端文字列に挟まれた中間文字列の一致情報を入力文字列から検出する中間検出手段と、を有する一致検出手段と、位置情報及び一致情報を用いて入力文字列から一致長を考慮して検出文字列を検出する範囲長検出手段と、を備える文字列検出回路とする。
2014041783.tif 000002
【特許請求の範囲】
【請求項１】
入力文字列から検出文字列の先端を含む先端文字列の位置情報と一致情報とを検出する先端検出手段と、前記入力文字列から前記検出文字列の終端を含む終端文字列の位置情報と一致情報とを検出する終端検出手段と、前記検出文字列の前記先端文字列と前記終端文字列に挟まれた中間文字列の一致情報を前記入力文字列から検出する中間検出手段と、を有する一致検出手段と、
前記位置情報及び前記一致情報を用いて前記入力文字列から一致長を考慮して前記検出文字列を検出する範囲長検出手段と、を備えることを特徴とする文字列検出回路。
【請求項２】
前記入力文字列は、前記先端検出手段、前記中間検出手段及び前記終端検出手段のそれぞれに同じタイミングで入力されることを特徴とする請求項１に記載の文字列検出回路。
【請求項３】
前記入力文字列は複数の部分文字列に分割され、
前記複数の部分文字列はそれぞれタイミングをずらして前記一致検出手段に入力されることを特徴とする請求項１または２に記載の文字列検出回路。
【請求項４】
前記範囲長検出手段は、
前記複数の部分文字列を入力された順に処理することを特徴とする請求項３に記載の文字列検出回路。
【請求項５】
前記範囲長検出手段は、
前記先端文字列及び前記終端文字列の一致とともに、前記中間文字列の一致長を考慮した一致を検出する状態遷移機械を備え、
前記状態遷移機械は、前記位置情報及び前記一致情報を入力とし、前記中間文字列の一致長を加算するカウンタを備えることを特徴とする請求項１乃至４のいずれか一項に記載の文字列検出回路。
【請求項６】
前記状態遷移機械は、
前記先端文字列が検出されていない未検出状態と、
前記先端文字列の位置情報及び一致情報と前記中間文字列の一致情報を基に前記検出文字列が検出されている検出中状態と、
前記終端文字列が部分的に検出されている半終端状態と、を有することを特徴とする請求項５に記載の文字列検出回路。
【請求項７】
前記検出中状態において、
前記範囲長検出手段は、
前記終端文字列を部分的に検出した際に、前記部分文字列の長さと前記終端位置とから算出された前記中間文字列の一致長を前記カウンタに加算し、
前記カウンタのカウンタ値が所定の範囲内である場合は前記半終端状態へと遷移し、
前記カウンタのカウンタ値が前記所定の範囲内にない場合は前記未検出状態へと遷移することを特徴とする請求項５または６に記載の文字列検出回路。
【請求項８】
前記半終端状態において、
前記範囲長検出手段は、
前記終端文字列が検出された場合、前記カウンタのカウンタ値が所定の範囲内である場合は一致結果を出力して前記未検出状態へと遷移し、
前記カウンタのカウンタ値が前記所定の範囲内にない、もしくは前記終端文字列が検出されなかった場合、一致結果を出力することなく前記未検出状態へと遷移することを特徴とする請求項５または６に記載の文字列検出回路。
【請求項９】
さらに、前記入力文字列を分割して前記部分文字列を作成する文字列処理手段を備えることを特徴とする請求項１乃至７のいずれか一項に記載の文字列検出回路。
【請求項１０】
入力文字列から検出文字列の先端を含む先端文字列の位置情報と一致情報との検出、前記入力文字列から前記検出文字列の終端を含む終端文字列の位置情報と一致情報との検出、及び前記検出文字列において前記先端文字列と前記終端文字列に挟まれた中間文字列の一致情報を前記入力文字列からの検出、を並列で行い、
前記位置情報及び前記一致情報を用いて前記入力文字列から一致長を考慮して前記検出文字列を検出することを特徴とする文字列検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文字列の一致検出をする文字列検出回路及び文字列検出方法に関する。特に、文字列の一致長を考慮した文字列検出装置及び文字列検出方法に関する。
【背景技術】
【０００２】
文字列一致検出は、ネットワーク侵入検知や迷惑メールフィルタ等、産業界で様々な応用が存在する。とりわけ近年、文字列の一致長を考慮した一致検出に注目が集まっている。【０００３】
例えば、最大一致長が２文字として任意のアルファベットとの一致検出を考える。この例では、ＡやＡＢという文字列に関しては一致検出されるものの、ＡＢＣという文字列に関しては最大一致長が３となるために検出されない。このように、一致長を指定することで、より高精度な文字列一致検出を実現することができる。しかしながら、このような文字列の一致長を考慮した一致検出を高速に実現することは非常に困難であった。【０００４】
図９は、一般的な文字列の繰返しを考慮した一致検出を行う繰返し数制約付き文字列検出回路９０を示した図である。なお、図９の方式の一例は、非特許文献１に開示されている。【０００５】
この例では、最小繰返しを１、最大繰返し数を４０としている。文字列検出回路９０では、入力文字列を、例えば、正規表現から生成される状態遷移機械９１によって一致検出を行う。この状態遷移機械９１は、もし一致していればカウンタ９２に内部カウンタを増加させる信号を送る。すなわち、状態遷移が繰り返されるたびに、繰返し回数を１増やす。比較器９３は内部カウンタの出力結果が１以上４０以下であれば、一致情報を出力回路９５へ送る。【０００６】
続いて、非一致検出回路９４は状態遷移機械９１の内部状態を監視し、もし今後一致する可能性がなければカウンタ９２と出力回路９５にリセット信号を送る。カウンタ９２はリセット信号により内部カウンタ値を０に戻す。すなわち、状態遷移が繰り返されなければ繰返し回数を０とし、出力回路９５はリセット信号を受信した際に、比較器９３の出力結果が一致していれば一致と判定し、一致結果を出力する。【０００７】
図９に示した方式の状態遷移機械９１は、１文字の繰返しからなる文字列に関しては、一致長を考慮した文字列の検出が可能である。１文字の繰返しからなる文字列とは「ＡＡＡＡＡ」のような、特定の文字や任意の文字の繰返しとして表現される。この場合、「Ａ」の繰返し数は５で、かつ、繰返し回数は５となるため、繰返し回数が一致長と同値になる。そのため、一致長を考慮した文字列の検出が可能となる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】M．Faezipour、M．Nourani、“Constraint  Repetition  Inspection  for  Regular  Expression  on  FPGA、”16th  IEEE  Symposium  on  High  Performance  Interconnects、pp．111−118（2008）
【発明の概要】
【発明が解決しようとする課題】
【０００９】
図９に示した方式では、「ＡＢＢＢＣ」という繰返し文字列ではない文字列の一致長を出力したい場合、入力文字列として「ＡＢＢＢＣ」が与えられたとしても、ＡとＣという異なる文字が付加されている。そのため、本方式では繰返し回数の１が出力され、実際の一致長である５は出力されない。【００１０】
すなわち、図９に示した方式では、繰返しを持たない文字列に関しては、一致長を考慮した文字列として検出できないという課題があった。【００１１】
また、図９に示した方式では、単一の状態遷移機械によってシリアルに処理を行うため、多バイト入力による処理が難しい。そのため、多バイト入力によって、文字列を高速に処理することができないという課題があった。【００１２】
本発明は上述の課題を鑑みてなされたものであり、文字列の一致長を考慮した一致検出を、制限なく、かつ高速に処理する装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明の文字列検出回路は、入力文字列から検出文字列の先端を含む先端文字列の位置情報と一致情報とを検出する先端検出手段と、入力文字列から検出文字列の終端を含む終端文字列の位置情報と一致情報とを検出する終端検出手段と、検出文字列の先端文字列と終端文字列に挟まれた中間文字列の一致情報を入力文字列から検出する中間検出手段と、を有する一致検出手段と、位置情報及び一致情報を用いて入力文字列から一致長を考慮して検出文字列を検出する範囲長検出手段と、を備える。【００１４】
本発明の文字列検出方法は、入力文字列から検出文字列の先端を含む先端文字列の位置情報と一致情報との検出、入力文字列から検出文字列の終端を含む終端文字列の位置情報と一致情報との検出、及び検出文字列において先端文字列と終端文字列に挟まれた中間文字列の一致情報を入力文字列からの検出、を並列で行い、位置情報及び一致情報を用いて入力文字列から一致長を考慮して検出文字列を検出する。
【発明の効果】
【００１５】
本発明によれば、文字列の一致長を考慮した一致検出を、繰返し文字列に制限されずに実施することができる。また、一致検出を、多バイト入力を活用することで、非常に高速に処理することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１の実施形態に係る文字列検出回路の構成図である。
【図２】本発明の第１の実施形態において検出対象とする文字列の構成図である。
【図３】本発明の第１の実施形態に係る文字列検出回路における入力文字列の構成図である。
【図４】本発明の第１の実施形態に係る文字列検出回路における入力文字列の構成図の一例である。
【図５】本発明の第１の実施形態に係る文字列検出回路の動作例を示す図である。
【図６】本発明の第１の実施形態に係る文字列検出回路の範囲長検出部の状態遷移図である。
【図７】本発明の第２の実施形態に係る文字列検出回路の構成図である。
【図８】本発明の第２の実施形態に係る文字列検出回路の文字列処理部の構成図である。
【図９】一般的な構成の最大長制約付き文字列検出回路の構成図である。
【発明を実施するための形態】
【００１７】
以下において、本発明を実施するための形態について図面を参照しながら説明する。
【００１８】
（第１の実施形態）
（文字列検出回路）
図１は、本発明の第１の実施形態に係る文字列検出回路１の構成例を示す図である。なお、本発明の実施形態に係る文字列検出回路１は、一致長制約付き文字列検出回路のことを指す。また、本発明の実施形態に係る文字列検出回路１は、正規表現の文字だけではなく、正規表現にはない記号やパターンなどの一致検出にも適応できる。
【００１９】
図１を参照すると、文字列検出回路１は、先端検出部２、中間検出部３、終端検出部４及び範囲長検出部５を備えている。
【００２０】
文字列検出回路１は、入力された文字列と検出文字列との比較を行い、一致長を考慮してそれらの一致を判定する回路である。
【００２１】
先端検出部２、中間検出部３、終端検出部４は、入力された文字列から、検出文字列の先端文字列、中間文字列、終端文字列のそれぞれを検出する。なお、先端検出部２、中間検出部３、終端検出部４は、それぞれ別の構成要素としているが、これらの検出機能を一つの一致検出部として実現することができれば、必ずしも検出部の全てを個別の構成要素としなくてもよい。
【００２２】
範囲長検出部５は、先端検出部２、中間検出部３、終端検出部４から出力された結果を入力し、それらの結果から入力された文字列と検出文字列の一致を判定する。
【００２３】
なお、上述の各構成要素の詳細については、後ほどあらためて説明する。
【００２４】
（検出文字列）
図２は、本発明の第１の実施形態に係る文字列検出回路１が検出する検出文字列２０の構成を示す図である。
【００２５】
検出文字列２０は、先端文字列２１、中間文字列２２及び終端文字列２３からなる。
【００２６】
先端文字列２１及び終端文字列２３は、それぞれ検出文字列２０の先端、終端を含む文字列である。先端文字列２１及び終端文字列２３には、一般に中間文字列２２とは異なる符号が割り当てられている。また、先端文字列２１及び終端文字列２３の文字長は任意であり、例えば、１バイト以上などと指定できる。
【００２７】
中間文字列２２は、一致長を考慮する文字列に相当する。なお、一致長とは、先端文字列２１と終端文字列２３に挟まれた中間文字列２２の文字数を示す。また、一致長は、最小長または最大長のいずれか一方、もしくは最小長及び最大長の両方を含む範囲として設定される。中間文字列２２は、一致長のみを考慮すればよいため、文字数のみを定義すればよい。ただし、中間文字列２２については、必要に応じて特定の文字列を含むこととしても構わない。
【００２８】
例えば、検出文字列２０を、「ＡＢＣ・・・ＣＹＺ」とし、先端文字列２１をＡＢ、終端文字列２３をＹＺ、中間文字列２２をＣの繰返し文字列と定義する。仮に、最大一致長を５とすると、「ＡＢＹＺ」、「ＡＢＣＹＺ」、「ＡＢＣＣＹＺ」、「ＡＢＣＣＣＹＺ」、「ＡＢＣＣＣＣＹＺ」、「ＡＢＣＣＣＣＣＹＺ」という文字列が検出対象となる。しかしながら、「ＡＢＣＣＣＣＣＣＹＺ」は、中間文字列２２の一致長が６となるため、検出対象外である。この例では、中間文字列２２としてＣの繰返し文字列をあげたが、中間文字列２２は任意の文字で構成されていてもよく、一致長のみを検出対象とする。
【００２９】
本発明の第１の実施形態に係る文字列検出回路１では、検出文字列２０と完全一致した文字列のみを検出対象とするのではなく、先端文字列２１、終端文字列２３と完全一致し、指定した一致長の条件に合致する中間文字列２２を含む文字列が検出対象となる。
【００３０】
このように、任意の文字列において先端文字列２１及び終端文字列２３を規定することができるため、本発明の実施形態に係る検出文字列の定義は、一般的な文字列に適用できる。
【００３１】
なお、検出文字列２０は、論理回路として実現されてもよいし、記憶素子に格納されていてもよいし、一般に文字が判定できる方式であればどのような実装でも構わない。
【００３２】
（入力文字列）
図３は、本発明の第１の実施形態に係る文字列検出回路１に入力される入力文字列３０の構成を示す図である。入力文字列３０としては、正規表現などで表される文字列を取り扱うことができる。また、正規表現で表されていない記号やパターンなどを含む記号列を文字列として取り扱うこともできる。
【００３３】
入力文字列３０は、任意長の文字列からなる複数個の部分文字列３１ａ、３１ｂ、・・・、３１ｎから構成される。この入力文字列３０から検出文字列２０と一致長を考慮した上で一致する文字列を検出する。なお、本発明の実施形態においては、部分文字列３１ａ、３１ｂ、・・・、３１ｎを用いて説明する際に、特に区別する必要がないときは部分文字列３１と記載する。
【００３４】
例えば、入力文字列３０が「ＡＢＣＣＣＣＣＣＣＣＹＺ」であるとする。文字列検出回路１が一度に処理できる最大の文字列長が４である場合、部分文字列３１は、「ＡＢＣＣ」、「ＣＣＣＣ」、「ＣＣＹＺ」に設定できる。無論、最大の文字列長が入力文字列長より大きければ、入力文字列３０を一度に文字列検出回路１へと入力することができる。
【００３５】
ただし、部分文字列３１ａ、３１ｂ、・・・、３１ｎのそれぞれの長さは、全て同じに設定してもよく、文字列の出現順などに応じて設定してもよい。
【００３６】
なお、部分文字列３１は、それぞれ符号部分とデータ部分を含んでいてもよく、また、それぞれの部分文字列３１を指定したアドレスに保存することができるのであれば、データ部分のみから構成されていてもよい。
【００３７】
（動作）
以下において、図４及び図５を用いて本発明の第１の実施形態に係る文字列検出回路１の動作を説明する。
【００３８】
図４は、部分文字列４１と部分文字列と４２からなる入力文字列４０である。入力文字列４０は、図３の入力文字列３０の一例である。
【００３９】
図５は、本発明の第１の実施形態に係る文字列検出回路１における入力方式の一例を示した図である。
【００４０】
文字列検出回路１は、部分文字列４１及び部分文字列４２が存在したときに、一致長を考慮した文字列検出を行う。
【００４１】
文字列検出回路１に対して、時刻Ｔ０では部分文字列４１を入力し、時刻Ｔ１では部分文字列４２を入力する。すなわち、これらの部分文字列４１、４２は、ある時刻で、順序良く文字列検出回路１に入力される。この際、入力文字列４０は、先端検出部２、中間検出部３及び終端検出部４に同時刻に入力されることになる。そのため、先端文字列２１、中間文字列２２、終端文字列２３のそれぞれにおいて、並列で文字列検出される。そのため、高速での文字列検出処理が可能となる。
【００４２】
なお、部分文字列４１、４２を文字列検出回路１に入力するタイミングは、範囲長検出部５の処理能力に応じて決定される。例えば、範囲長検出部５が並列処理できない場合、部分文字列４２は、部分文字列４１の文字列検出処理が終了してから文字列検出回路１に入力すればよい。
【００４３】
また、文字列検出回路１において並列処理が可能であれば、部分文字列４１の文字列検出処理が実行中であっても、部分文字列４１を文字列検出回路１に入力してもよい。例えば、先端検出部２、中間検出部３及び終端検出部４を複数設けたり、それぞれの検出部の内部処理を並行にしたり、それぞれの検出部の内部に記憶装置を設けたりすることによって、並行処理が可能となる。また、パイプライン方式で検出処理を実行することが可能であれば、並列処理を連続的に実行することができるため、さらに高速な処理が可能となる。なお、部分文字列４１、４２の入力方式によって、一致長を考慮した文字列検出が実施されるが、本発明の第１の実施形態に係る文字列検出回路１の検出方式は、ここであげたものに限らない。
【００４４】
以下において、文字列検出回路１の構成を詳細に説明する。例として、入力文字列３０を「ＦＦＡＢＣＣＣＣＹＺＦＦ」とし、先端文字列２１を「ＡＢ」、終端文字列２３を「ＹＺ」、中間文字列２２をＣの繰返し文字列と定義する。この時、最大一致長を５とし、部分文字列の長さは４とする。
【００４５】
（先端検出部）
先端検出部２は、部分文字列３１を入力とし、その部分文字列３１における先端文字列２１を検出する。
【００４６】
先端文字列２１が検出された場合には、先端位置１１と先端一致情報１２とを範囲長検出部５へと送信する。
【００４７】
先端位置１１とは、部分文字列３１内における先端文字列２１の位置を示す。ここで、位置とは部分文字列３１におけるオフセットを意味する。例えば、先端文字列２１の末尾の文字位置で定義することができる。一般に、オフセットとは先頭からの距離を表わす整数であるが、本実施形態においては、部分文字列３１の左または右からのどちらからでも位置を指定可能である。例えば、部分文字列３１の左を基準として位置を指定する場合、「ＦＦＡＢ」を入力すると、先端文字列「ＡＢ」は先頭から数えると３番目に位置しているので、先端位置１１は３となる。
【００４８】
また、先端一致情報１２とは、部分文字列３１内のいずれかの文字列が、先端文字列２１と一致したか否か、または、一致途上か、のいずれかを示す。すなわち、先端一致情報１２は、一致、不一致、一致途上の３つの情報を含む。ここで、一致途上とは、先端文字列２１の長さが１以上の場合において、先端文字列２１が連続する部分文字列３１にまたがっている場合を意味する。
【００４９】
（中間検出部）
中間検出部３は、部分文字列３１を入力とし、その部分文字列３１において、中間文字列２２を検出する。
【００５０】
中間文字列２２が検出された場合には、一致したか否かを示す中間一致情報１３を、範囲長検出部５へと送信する。ここで、中間文字列２２の一致情報は、一致長が所定の範囲内にあるか否かを示すことになる。
【００５１】
（終端検出部）
終端検出部４は、部分文字列３１を入力とし、その部分文字列３１において、終端文字列２３を検出する。
【００５２】
終端文字列２３が検出された場合には、終端位置１４と終端一致情報１５とを範囲長検出部５へと送信する。
【００５３】
終端位置１４とは、部分文字列２３内における終端文字列２３の位置を示す。例えば終端文字列２３が始まる文字位置で定義することができる。例えば、部分文字列３１の左を基準として位置を指定する場合、「ＹＺＦＦ」を入力すると、終端文字列「ＺＦ」はその部分文字列３１においては先頭から数えると２番目に位置している。ここで、それまでに入力した部分文字列長に２を加えた数値が終端位置１４となる。
【００５４】
また、終端一致情報１５とは、部分文字列３１内のいずれかの文字列が、終端文字列２３と一致したか否か、一致途上か、のいずれかを示す。すなわち、終端一致情報１５は、一致、不一致、一致途上の３つの情報を含む。
【００５５】
（範囲長検出部）
範囲長検出部５は、先端検出部２から出力された先端位置１１及び先端一致情報１２、中間検出部３から出力された中間一致情報１３、終端検出部４から出力された終端位置１４及び終端一致情報１５、といった位置情報と一致情報を入力とする状態遷移機械を構成する。範囲長検出部５は、内部に図示しないカウンタを備える。そのため、最小一致長または最大一致長のいずれか一方、もしくは最小一致長及び最大一致長の両方を考慮することが可能である。
【００５６】
図６は、本発明の第１の実施形態に係る範囲長検出部５の構成図である。なお、カウンタは図示していない。
【００５７】
図６を参照すると、範囲長検出部５は、未検出状態６１、検出中状態６２、半終端状態６３の３状態からなる状態遷移機械６０として構成される。
【００５８】
未検出状態６１は、検出する文字列を検出していない状態であり、いわゆる初期状態に相当する。
【００５９】
検出中状態６２は、先端位置１１と先端一致情報１２、中間検出部３から出力された中間一致情報１３を元に、検証対象の文字列を検証している状態に対応する。
【００６０】
半終端状態６３は、終端文字列２３が次に入力される部分文字列３１にまたがっている状態、すなわち、終端文字列２３である可能性はあるが次の時刻まで終端文字列２３であるか否かの判断がつかない場合に遷移する状態である。
【００６１】
ただし、本発明の実施形態に係る範囲長検出部５は、先端検出部２、中間検出部３、終端検出部４によって抽出された情報から、範囲長を算出できる回路でありさえすればよく、図６の構成に限定されるわけではない。
【００６２】
ここで、図６に示した状態遷移機械６０の状態遷移条件について詳細に説明する。なお、これ以降の説明においては、数値範囲を「〜以上、〜以下」という表現で範囲しているが、これは、「〜より大きい」、「〜より小さい」といった、一般の範囲表現に適宜置換することが可能である。また、以下の状態遷移条件の説明においては、先端位置１１及び終端位置１４は、文字列の左端、右端などといった同じ基準に対する位置で定義する。
【００６３】
以下の説明においては、一般的な文字列を入力することを想定し、実施形態としてはＳ１〜Ｓ９という状態遷移条件について説明している。
【００６４】
また、「ＦＦＡＢＣＣＣＣＹＺＦＦ」を入力文字列３０とし、先端文字列「ＡＢ」、中間文字列「Ｃ・・・Ｃ」、終端文字列「ＹＺ」からなる「ＡＢＣ・・・ＣＹＺ」を検出文字列２０とした例を交えて説明を加える。なお、以下に加える説明は一例であり、部分文字列３１の長さは、各状態遷移条件において任意に設定した値であって、本発明の実施形態を限定するものではない。
【００６５】
（状態遷移条件Ｓ１）
状態遷移条件Ｓ１は、未検出状態６１において、先端文字列２１の一致情報が一致を示し、中間文字列２２の一致情報が一致を示し、終端文字列２３の一致情報が一致を示した場合の遷移条件である。
【００６６】
状態遷移条件Ｓ１では、未検出状態６１から未検出状態６１へと遷移する。
【００６７】
ここで、終端位置１４と先端位置１１との差が、指定された最小長以上かつ指定された最大長以下という所定の範囲内に含まれるため、中間文字列２２の一致長が一致と判定されることになり、一致結果を出力する。なお、最小長には０または１、最大長には１以上無限大が指定可能である。
【００６８】
例えば、「ＦＦＡＢＣＣＣＣＹＺＦＦ」を入力する例において、「ＦＦＡＢＣＣＣＣＹＺＦＦ」を入力した場合が、この条件に相当する。
【００６９】
（状態遷移条件Ｓ２）
状態遷移条件Ｓ２は、未検出状態６１において、先端文字列２１の一致情報が一致を示し、中間文字列２２の一致情報が一致を示し、終端文字列２３の一致情報が不一致を示した場合の遷移条件である。
【００７０】
状態遷移条件Ｓ２では、未検出状態６１から検出中状態６２へと遷移する。
【００７１】
ここで、部分文字列長と先端位置１１から算出された中間文字列２２の一致長をカウンタに代入する。すなわち、先端文字列２１が検出され、中間文字列は未だ所定の範囲内にあるため、終端文字列２３の検出待ちの状態となる。
【００７２】
例えば、「ＦＦＡＢＣＣＣＣＹＺＦＦ」を入力する例において、「ＦＦＡＢ」を入力した場合が、この条件に相当する。「ＦＦＡＢ」を入力した場合、中間文字列の一致長は０なので、カウンタには０を代入する。
【００７３】
（状態遷移条件Ｓ３）
状態遷移条件Ｓ３は、検出中状態６２において、先端文字列２１の一致情報が不一致を示し、中間文字列２２の一致情報が一致、終端文字列２３の一致情報が不一致を示した場合の遷移条件である。
【００７４】
状態遷移条件Ｓ３では、検出中状態６２から検出中状態６２へと遷移する。
【００７５】
ここで、部分文字列長をカウンタに加算する。この遷移条件では、先端文字列２１との一致は既に検出されており、終端文字列２３が未だ未検出であるため、中間文字列２２が所定の範囲内にあるうちは検出中状態６２を維持することを示している。
【００７６】
例えば、「ＦＦＡＢＣＣＣＣＹＺＦＦ」を入力する例において、「ＣＣＣＣ」を入力した場合が、この条件に相当する。中間文字列２２「ＣＣＣＣ」を入力した場合、カウンタに４を加算することになる。
【００７７】
（状態遷移条件Ｓ４）
状態遷移条件Ｓ４は、検出中状態６２において、先端文字列２１の一致情報が不一致を示し、中間文字列２２の一致情報が一致を示し、終端文字列２３の一致情報が一致を示した場合の遷移条件である。
【００７８】
状態遷移条件Ｓ４では、検出中状態６２から未検出状態６１へと遷移する。
【００７９】
ここで、部分文字列長と終端位置１４から算出された、中間文字列２２の一致長をカウンタに加算する。その結果、中間文字列の一致長が指定された最小長以上かつ指定された最大長以下という所定の範囲内であれば、先端文字列２１と、中間文字列２２の一致長と、終端文字列２３が一致することになるため、一致結果を出力する。なお、最小長には０または１、最大長には１以上無限大が指定可能である。
【００８０】
例えば、「ＦＦＡＢＣＣＣＣＹＺＦＦ」を入力する例において、「ＹＺＦＦ」を入力した場合が、この条件に相当する。「ＹＺＦＦ」を入力した場合、中間文字列２２の一致長は０なので、カウンタには０を代入する。ここで、状態遷移条件Ｓ３の結果と合わせると、その一致長は４である。すなわち、指定された最大長を５とすると、入力文字列３０と検出文字列２０とは一致すると判定され、文字列検出回路１からは、一致結果が出力される。
【００８１】
（状態遷移条件Ｓ５）
状態遷移条件Ｓ５は、検出中状態６２において、先端文字列２１の一致情報が不一致を示し、中間文字列２２の一致情報が一致、終端文字列２３の一致情報が一致途上を示した場合の遷移条件である。
【００８２】
状態遷移条件Ｓ５では、部分文字列長と終端位置１４から算出された、中間文字列２２の一致長をカウンタに加算する。その結果、中間文字列２２の一致長が指定された最小長以上かつ指定された最大長以下であれば、検出中状態６２から半終端状態６３へと遷移する。すなわち、先端文字列２１は既に検出され、中間文字列２２は一致長が一致と判定され、終端文字列２３が途中まで検出された状態となる。
【００８３】
例えば、「ＦＦＡＢＣＣＣＣＹＺＦＦ」を入力する例において、既に先端文字列「ＡＢ」が検出済みであり、そこに「ＣＣＣＹ」を入力した場合が、この条件に相当する。「ＣＣＣＹ」を入力した場合、終端文字列「ＹＺ」の途中までが検出された状態となる。
【００８４】
（状態遷移条件Ｓ６）
状態遷移条件Ｓ６は、未検出状態６１において、先端文字列２１の一致情報が一致を示し、中間文字列２２の一致情報が一致、終端文字列の一致情報が一致途上を示した場合の遷移条件である。
【００８５】
状態遷移条件Ｓ６では、部分文字列長と終端位置１４から算出された、中間文字列２２の一致長をカウンタに加算する。その結果、指定された最小長以上かつ指定された最大長以下であれば、未検出状態６１から半終端状態６３へと遷移する。
【００８６】
例えば、「ＦＦＡＢＣＣＣＣＹＺＦＦ」を入力する例において、「ＡＢＣＣＣＹ」を入力した場合が、この条件に相当する。「ＦＦＡＢＣＣＣＹ」を入力した場合、終端文字列２３「ＹＺ」の途中までが検出された状態となる。
【００８７】
（状態遷移条件Ｓ７）
状態遷移条件Ｓ７は、半終端状態６３において、先端文字列２１の一致情報が不一致を示し、中間文字列２２の一致情報が一致、終端文字列２３の一致情報が一致を示した場合の遷移条件である
状態遷移条件Ｓ７では、半終端状態６３から未検出状態６１へと遷移する。
【００８８】
この場合、既に先端文字列２１は検出済みであり、中間文字列２２の一致長は所定の範囲内にあり、終端文字列２３も一致したことになるため、無条件で一致結果を出力する。
【００８９】
例えば、「ＦＦＡＢＣＣＣＣＹＺＦＦ」を入力する例において、既に先端文字列「ＡＢ」が検出済みであり、そこに「ＣＹＺＦＦ」を入力した場合が、この条件に相当する。「ＣＹＺＦＦ」を入力した場合、中間文字列２２と終端文字列２３の両方が一致と判定されるため、検出文字列２０が検出されたことになる。
【００９０】
（状態遷移条件Ｓ８）
状態遷移条件Ｓ８は、検出中状態６２において、状態遷移条件Ｓ３、Ｓ４、Ｓ５の、いずれの条件も満足しない場合の遷移条件である。
【００９１】
状態遷移条件Ｓ８では、検出中状態６２から未検出状態６１へと遷移する。
【００９２】
すなわち、先端文字列２１は検出されていたものの、中間文字列２２が一致長の範囲内になかった場合、もしくは終端文字列２３が一致条件を満たさなかった場合などに未検出状態６１に遷移する条件である。
【００９３】
例えば、「ＡＢＣ・・・ＣＹＺ」を検出文字列２０とし、中間文字列２２の一致長を５とした場合に、「ＦＦＡＢＣＣＣＣＣＣＹＺＦＦ」や「ＦＦＡＢＣＣＣＣＹＫＦＦ」などを入力する際に状態遷移条件Ｓ８を取りうる。
【００９４】
（状態遷移条件Ｓ９）
状態遷移条件Ｓ９は、半終端状態６３において、状態遷移条件Ｓ７を満足しない場合の遷移条件である。
【００９５】
状態遷移条件Ｓ９では、半終端状態６３から未検出状態６１へと遷移する。
【００９６】
すなわち、先端文字列２１は検出され、中間文字列２２の一致条件も満たされ、終端文字列２３の一部が一致していたところに、ある部分文字列３１が入力され、中間文字列２２の一致情報が不一致、もしくは終端文字列２３の一致情報が不一致となった際の条件である。
【００９７】
例えば、「ＡＢＣ・・・ＣＹＺ」を検出文字列２０とした場合において、入力文字列３０「ＦＦＡＢＣＣＣＣＹＫＦＦ」を、「ＦＦＡＢＣ」、「ＣＣＣＹ」、「ＫＦＦ」などの部分文字列３１として入力する際に状態遷移条件Ｓ９を取りうる。
【００９８】
このように、本発明の第１の実施形態によると、入力された文字列に対して、先端情報１１及び先端一致情報１２と、終端情報１４及び終端一致情報１５と、中間一致情報１３といった位置情報と一致情報から、指定された範囲長の中間文字列２２を検出することができる。
【００９９】
以上が、本発明の第１の実施形態に係る範囲長検出部５の状態遷移条件の説明である。なお、本発明の第１の実施形態に係る範囲長検出部５の状態遷移条件は、上述の条件に限定されず、各状態遷移条件に種々の変形を加えてもよい。
【０１００】
以上のように、本発明の第１の実施形態に係る文字列検出回路１によれば、先端文字列２１と終端文字２３に着目することで、繰返し文字列に留まらない幅広い、一致長を考慮した文字列検出処理が可能である。
【０１０１】
また、部分文字列３１を状態遷移機械６０で直接受信するのではなく、先端検出部２、中間検出部３、終端検出部４において抽出された情報によって状態遷移機械６０を駆動する。すなわち、多バイト入力を活用して処理することになるため、非常に高速な処理が可能となる。
【０１０２】
このように、本発明の第１の実施形態に係る文字列検出回路１によれば、重要な情報を抽出してから状態遷移機械を活用するため、非常に高速な処理が可能となっている。
【０１０３】
（第２の実施形態）
図７に、本発明の第２の実施形態に係る文字列検出回路７０を示した。
【０１０４】
第２の実施形態に係る文字列検出回路７０は、先端検出部７２、中間検出部７３、終端検出部７４、範囲長検出部７５及び文字列処理部７１を備えている。すなわち、文字列検出回路７０においては、第１の実施形態に係る文字列検出回路１に、文字列処理部７１が追加されている。なお、それぞれの文字列検出部の出力結果は第１の実施形態と同じであるため、出力結果の流れを矢印のみで示した。
【０１０５】
文字列処理部７１は、入力文字列３０を所定の長さの部分文字列３１に分割する。なお、分割する文字列の長さは、任意に設定可能である。
【０１０６】
文字列処理部７１は、入力文字列３０を、等分としたり、先端文字列２１や終端文字列２３の長さを基準とした長さとしたり、中間文字列２２を基準とした長さにすることができる。
【０１０７】
例えば、入力文字列３０が「ＡＢＣＣＣＣＣＣＣＣＹＺ」である場合、３等分すると、「ＡＢＣＣ」、「ＣＣＣＣ」、「ＣＣＹＺ」と設定できる。また、先端文字列２１や終端文字列２３に符号が含まれることが分かっている場合など、その符号の長さを考慮して部分文字列を設定してもよい。
【０１０８】
また、検出文字列２０の長さよりも、部分文字列３１の長さが長くなるような値を設定してもよいし、反対に部分文字列３１の長さが変化するように設定してもよい。
【０１０９】
例えば、部分文字列３１を入力していくにつれて、部分文字列３１の長さを次第に短くしたり、次第に長くしたりすることができる。例えば、入力文字列３０が「ＡＢＣＣＣＣＣＣＣＣＹＺ」である場合、部分文字列３１を「ＡＢＣＣＣ」、「ＣＣＣＣ」、「ＣＹＺ」としたり、「ＡＢＣ」、「ＣＣＣＣ」、「ＣＣＣＹＺ」としたりできる。
【０１１０】
また、部分文字列３１の長さをランダムに設定してもよく、例えば、「ＡＢ」、「ＣＣＣＣＣＣ」、「ＹＺ」とすることもできる。なお、入力文字列３０を分割して部分文字列３１を生成する方法はここにあげた限りではなく、各検出部の処理能力や外部の入力元・出力先にある装置の性能や設定に応じて任意に設定可能である。
【０１１１】
ただし、文字列処理部７１による入力文字列３０の分割は、ここであげた限りではない。
【０１１２】
図８は、文字列処理部７１の構成の一例を示す図である。
【０１１３】
図８に示した文字列処理部７１は、文字列分割部８１と、記憶部８２と、タイミング部８３と、選択部８４と、出力部８５と、を備えている。
【０１１４】
文字列分割部８１は、入力文字列３０を所定の長さに分割し、部分文字列３１を作製する。入力文字列３０を分割する長さは、任意に設定可能である。例えば、文字列分割部８１は、入力文字列３０を、等分してもよく、検出文字列２０の長さに応じて設定された長さに分割してもよく、ランダムな長さに分割してもよい。さらに、入力文字列３０の符号部分の長さが予め分かっている場合は、符号部分のみを取り出し、それ以外のデータ部分を任意の長さに分割してもよい。
【０１１５】
記憶部８２は、所定の長さに分割された部分文字列３１を記憶する。
【０１１６】
タイミング部８３は、選択部８４に、記憶部８２から部分文字列３１を取得するタイミングで信号を送信する。タイミング部８３は、設定されたタイミングで信号を送信できる。また、タイミング部８３を範囲長検出部７５内部のカウンタと同期させれば、範囲長検出部７５の処理に合わせて信号を送信することもできる。外部の演算処理装置に設けられたカウンタと同期させる場合は、そのカウンタのタイミングに合わせて処理を行えばよい。
【０１１７】
選択部８４は、タイミング部８３からの信号のタイミングに応じて、記憶部８２から部分文字列３１を選択し、出力部８５に送信する。
【０１１８】
出力部８５は、選択部８４から送信されてきた部分文字列３１を出力する。なお、選択部８４と出力部８５は、共通の構成要素としてもよい。
【０１１９】
以上が文字列処理部７１の構成及び動作の簡単な説明である。なお、文字列処理部７１は、入力文字列３０を分割しさえすれば、上述の構成及び動作に限定することはない。
【０１２０】
以上のように、第２の実施形態に係る文字列検出回路７０によれば、文字列検出回路７０に入力文字列３０を入力する前に、部分文字列３１に分割しなくても入力文字列３０をそのままの形で入力することができる。また、部分文字列３１の入力タイミングを設定しなくても、内部のタイミング部８３のタイミングで部分文字列３１を範囲長検出部７５に送信できる。このように、第２の実施形態の文字列検出回路７０によれば、入力文字列３０は、範囲長検出部７５が処理しやすい長さに分割されるため、さらに高速での処理が可能となる。
【０１２１】
以上、本発明を上記実施形態に即して説明したが、本発明は、上記実施形態の構成や動作にのみ限定されるものではなく、本発明の範囲内で当業者であればなしうることが可能な各種変形、修正を含むことはもちろんである。
【０１２２】
この出願は、２０１２年９月１１日に出願された日本出願特願２０１２−１９９０１５を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１２３】
１    文字列検出回路
２    先端検出部
３    中間検出部
４    終端検出部
５    範囲長検出部
２０    検出文字列
２１    先端文字列
２２    中間文字列
２３    終端文字列
３０    入力文字列
３１    部分文字列
４０    入力文字列
４１、４２    部分文字列
６１    未検出状態
６２    検出中状態
６３    半終端状態
７０    文字列検出回路
７１    文字列処理部
７２    先端検出部
７３    中間検出部
７４    終端検出部
７５    範囲長検出部
８１    文字列分割部
８２    記憶部
８３    タイミング部
８４    選択部
８５    出力部
９０    文字列検出回路
９１    状態遷移機械
９２    カウンタ
９３    比較器
９４    非一致検出回路
９５    出力回路
【図１】
2014041783.tif 000003
【図２】
2014041783.tif 000004
【図３】
2014041783.tif 000005
【図４】
2014041783.tif 000006
【図５】
2014041783.tif 000007
【図６】
2014041783.tif 000008
【図７】
2014041783.tif 000009
【図８】
2014041783.tif 000010
【図９】
2014041783.tif 000011
【国際調査報告】
2014041783.tif 000012
2014041783.tif 000013
2014041783.tif 000014
2014041783.tif 000015