高速パターンマッチング装置の探索方法
【課題】バイナリデータのパターンマッチングを高速に行う装置を実現する。
【解決手段】探索領域Ａを入力されたサーチキーについて探索する場合に、探索領域Ａを複数の部分探索領域に分割し、その部分探索領域のそれぞれの代表点の集合を探索領域Ｂとするとき、 探索領域Ｂを記憶する記憶手段Ｂと、探索領域Ｂを上記のサーチキーについて探索する探索手段Ｂと、 探索領域Ａを記憶する記憶手段Ａと、探索領域Ａから選択された部分探索領域Ｃを上記のサーチキーについて探索する探索手段Ａと、を備える探索装置の探索方法で、 探索領域Ｂを上記のサーチキーについて探索した結果をもとに、上記の複数の部分探索領域から１つを選択するステップと、 選択された部分探索領域について探索手段Ａを用いて上記のサーチキーについて探索するステップと、 探索結果を出力するステップと、を備えるようにする。
【解決手段】探索領域Ａを入力されたサーチキーについて探索する場合に、探索領域Ａを複数の部分探索領域に分割し、その部分探索領域のそれぞれの代表点の集合を探索領域Ｂとするとき、 探索領域Ｂを記憶する記憶手段Ｂと、探索領域Ｂを上記のサーチキーについて探索する探索手段Ｂと、 探索領域Ａを記憶する記憶手段Ａと、探索領域Ａから選択された部分探索領域Ｃを上記のサーチキーについて探索する探索手段Ａと、を備える探索装置の探索方法で、 探索領域Ｂを上記のサーチキーについて探索した結果をもとに、上記の複数の部分探索領域から１つを選択するステップと、 選択された部分探索領域について探索手段Ａを用いて上記のサーチキーについて探索するステップと、 探索結果を出力するステップと、を備えるようにする。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、バイナリデータのパターンマッチングを高速に行う高速パターンマッチング装置の探索方法に関している。
【背景技術】
【０００２】
本発明は、従来のものに比べて高速で動作するパターンマッチング装置に関するものであるが、従来の速度で動作するものは、種々の装置に組み込まれて用いられている。例えば、コンピュ−タ上でデータの照合を行って目的とするデータを検索するデータベ−スには、種々のパターンマッチング技術が使われている。ここで用いられるパターンマッチングには、逐次探索（順探索あるいはリニアサーチとも呼ばれる）、ハッシュ法、２分木探索（２分探索あるいはバイナリサーチとも呼ばれる）などがある。
【０００３】
逐次探索は、探索領域のデータとサーチキーとの照合を順次進めるものであり、探索時間のサーチキー依存が激しく、また平均探索時間が長い、という特徴がある。
【０００４】
また、ハッシュ法は、探索領域のそれぞれのデータのハッシュ値を求めてハッシュテ−ブルを作成し、ハッシュ値にそれぞれのデータを連想するように対応させておくものであり、サーチキーのハッシュ値を入力して探索データを出力するように関数を作成しておく。このため短時間での探索が可能であるという利点があるが、探索領域（ア−カイブ）を変化させるためには、ハッシュ法に用いるハッシュテ−ブルを作り直す必要があり、大規模の探索領域を頻繁に変えるための処理に多大の時間が必要である、という特徴がある。
【０００５】
また、２分木探索は、探索領域をソートしておき、サーチキーと探索領域の代表点のデータ（多くの場合は、中央のデータ）との大小一致比較で新たな探索領域に絞り込み、その新たな探索領域でも、新たな代表点を選択して、その代表点とサーチキーとの大小一致比較によって、さらに新たな探索領域に絞り込む、という作業を繰り返して、探索するものである。この方法による探索時間は上記の２つの探索方法の中間的なものであり、大規模の探索領域を行なう場合でも、逐次探索の場合と同様な準備で探索を開始できる、という特徴がある。
【０００６】
高速探索が必要な大規模探索領域としては、例えば、情報通信ネットワークにおいて、有害情報の除去などのためのフィルタリングや顧客情報の検索などの際の探索領域である。ネットワークは、ますます高速化複雑化するため、これに対応できる強力なパターンマッチング装置の開発が求められている。
【０００７】
本発明は、主に上記の２分木探索に関しており、同等の回路を用いる場合に、従来よりも高速の探索を可能ならしめるものである。
【０００８】
［従来例１］
図５（ａ）に示す様に、ｄ１からｄ１５まで昇順にソートされた探索領域について、２分木探索を行なう場合を図５（ｂ）に沿って示す。探索領域のデータ数が極端に少ないのは、説明を容易にして誤解を避けるためであって、実際に適用する探索領域は、さらに多数のデータを含む領域である。サーチキーの入力があると、これと中央にあるｄ８とを比較する。この比較で、サーチキーとの一致あるいは大小関係を出力する。一致する場合は、ｄ８と一致する旨出力する。ここでは、ｄ８より大きいという結果であったとすると、あらたにｄ９からｄ１５までを新たな探索領域とすることになるので、その中央にあるｄ１２とサーチキーとを比較することになる。また、ここでは、ｄ１２より小さいという結果であったとすると、あらたにｄ９からｄ１１までを新たな探索領域とすることになるので、その中央にあるｄ１０とサーチキーとを比較することになる。さらに、ここでは、ｄ１０より小さいという結果であったとすると、最後にｄ９だけが残ることになるので、ｄ９とサーチキーとが一致するかどうかを確かめることになる。この操作によって、探索領域にサーチキーがあるかどうかを知ることが出来る。このようにデータ数が１５の探索領域であっても、３回の大小一致比較で最終的な候補に絞ることができる。この操作はひとつの比較手段をプログラムに従って動作させて２分木探索を行なっている。
【０００９】
しかし、比較的大きな探索領域に従来の２分木探索を適用する場合には、その探索領域を構成する記憶装置が大容量のものとなり、一般に大容量の記憶装置でのデータアクセス時間や読み出し時間は比較的大きいので、高速動作には適しておらず、充分に高速にパターンマッチングを進めることができないという問題があった。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、高速な２分木探索を実現するものである。
【発明の効果】
【００１１】
この発明によって、大規模な探索領域に対しても、同等の速度の電子回路を用いる場合に、従来よりも高速の探索が可能になる。
【課題を解決するための手段】
【００１２】
本発明は、大略では、探索領域とサーチキーが与えられたときに、探索領域の個々の要素を記憶装置に記憶させ、この要素を比較手段である比較回路に読み出してサーチキーとの照合を行なって探索を進める際に、従来の様にひとつの記憶装置を用いて探索を行なうのではなく、大まかな探索を高速な探索手段を用いて行い、徐々に大容量の記憶装置でのより詳しい探索へと進むものである。より詳しくは、以下に示す。
【００１３】
まず本発明は、予め決められた探索領域Ａを入力されたサーチキーについて探索する場合に、前記の探索領域Ａを複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域Ｂとするとき、
前記のあらたな探索領域Ｂを記憶する記憶手段Ｂと、前記のあらたな探索領域Ｂを上記のサーチキーについて探索する探索手段Ｂと、
前記の予め決められた探索領域Ａを記憶する記憶手段Ａと、前記の予め決められた探索領域Ａから選択された部分探索領域Ｃを上記のサーチキーについて探索する探索手段Ａと、を備えるパターンマッチング装置の探索方法であって、
前記のあらたな探索領域Ｂを上記のサーチキーについて探索した結果をもとに、上記の複数の部分探索領域から１つを選択してこれを部分探索領域Ｃとするとき、
選択された部分探索領域Ｃについて上記の探索手段Ａを用いて上記のサーチキーについて探索するステップと、
探索結果を出力するステップと、
を備えることを特徴としている。
【００１４】
上記の探索領域Ａは、探索領域Ａを含む探索領域から、何らかの選択方法により予め選択された探索領域であってもよい。
【００１５】
また、探索手段Ａと探索手段Ｂとは、同じ周期で探索をおこない、
探索手段Ｂは、上記のサーチキーについての探索を探索領域Ｂで行い、引き続き新たなサーチキーについての探索を探索領域Ｂで行うものであり、
探索手段Ａは、探索手段Ｂが上記のサーチキーにつての探索を終了した後、上記のサーチキーにつての探索を部分探索領域Ｃで行い、引き続き上記の新たなサーチキーについての探索を部分探索領域Ｃで行うようにして、次々に新しいサーチキーで探索を行なうことが出来る。
【００１６】
探索手段Ａ、Ｂは２分探索を用いた探索手段であり、探索領域Ｂにおいてサーチキーとの比較を１度行なう探索時間あるいはその平均を探索時間Ｂとし、部分探索領域Ｃにおいてサーチキーとの比較を１度行なう探索時間あるいはその平均を探索時間Ａとし、サーチキーとの比較を１度行なう毎に加算する探索回数をそれぞれ探索回数Ａ、Ｂとするとき、
探索時間の大きい方の探索回数を小さく設定することによって、一連の探索に要する時間を短縮することが出来る。
【００１７】
前記の場合に、探索回数Ａと探索回数Ｂとの和をＫとするとき、探索領域Ａを２分探索する場合には、探索回数Ａ、Ｂの割り振り方にはＫの値は依存しない。このとき、探索回数Ｂは、Ｋ×探索時間Ａを、探索時間Ａと探索時間Ｂとの和で除した数に最も近い整数とすると、探索手段Ａ、Ｂの一方のみに負担がかかることを回避できる。
【００１８】
また、上記の探索方法は、３層以上の多層構成とすることも可能であり、
第１の記憶装置に記憶され予め決められた第１の探索領域を入力されたサーチキーについて探索する場合に、
前記の第１の探索領域を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合を第２の記憶装置に記憶して第２の探索領域２とし、
以下順次に、３からＮまでのｎについて、
第（ｎ−１）の記憶装置に記憶した前記の第（ｎ−１）の探索領域を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合を第ｎの記憶装置に記憶して第ｎの探索領域とし、
第Ｎの探索領域を入力されたサーチキーについて第Ｎの探索手段を用いて２分木探索を行い、その探索結果をもとに、探索領域（Ｎ−１）の部分探索領域を選択し、
以下、順に、Ｎ−１から２までのｎについて、
探索領域ｎを入力されたサーチキーについて第ｎの探索手段を用いて探索し、その探索結果をもとに、探索領域（ｎ−１）の部分探索領域を選択し、
探索領域１の選択された部分探索領域についての探索を第１の探索手段で行なって探索結果を出力するものである。
【００１９】
上記の探索方法が特に有効なのは、次の構成にそれを適用する場合であって、
２からＮまでのｎについて、
前記の探索領域（ｎ−１）を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域ｎとし、
１からＮまでのｎについて、
それぞれの探索領域ｎのすべての要素を記憶する記憶手段ｎと、前記探索領域ｎを探索する探索手段ｎとについて、
記憶手段ｎの記憶容量をｃ（ｎ）とし、探索領域ｎの探索のスループットをｂ（ｎ）とし、
サーチキーの入力レートは、一定であり、その入力レートのビットレートをb(input)とし、
探索領域のビットサイズをＭとし、
探索手段ｎの行なう探索領域ｎに属する要素とサーチキーとの比較回数をp（ｎ）と、
するとき、
ｃ（１）＞ｃ（２）＞・・・＞ｃ（Ｎ）、
ｂ（１）＜ｂ（２）＜・・・＜ｂ（Ｎ）、
ｂ(ｎ) / ｐ(ｎ) ≧ ｂ(input)、かつ、
ｂ(ｎ) ≦ log2ｃ(ｎ)、
なる条件を満たし、
１からＮまでのp(ｎ）の和について、底を２としたＭの対数、log2Ｍ、を切り上げた整数と等しくなるように、
１からＮまでのｎについて、
ｂ（ｎ）、ｃ（ｎ）、p（ｎ）を定めた探索装置に、上記の探索方法を適用することが望ましい。
【発明を実施するための最良の形態】
【００２０】
以下にこの発明の実施の形態を詳細に説明するが、以下の説明においては、決められた探索領域についてサーチキーと比較するデータを代表点と呼ぶことにする。
【実施例１】
【００２１】
図１に示す例は、簡単のために図５と同じ探索領域についての探索を行なう場合を示している。図１の探索ブロック１では、２分木探索回路に３データ分のメモリが接続されている。第１次の２分木探索として、サーチキーの入力があると、これと中央にあるｄ８とを比較する。この比較で、サーチキーとの一致あるいは大小関係を出力する。一致する場合は、ｄ８と一致する旨出力する。ここでは、ｄ８より大きいという結果であったとすると、第２次の２分木探索として、あらたにｄ９からｄ１５までを新たな探索領域とすることになるので、その中央にあるｄ１２とサーチキーとを比較することになる。また、ここでは、ｄ１２より小さいという結果であったとすると、第３次の２分木探索として、あらたにｄ９からｄ１１までを新たな探索領域とすることになるので、新たな探索領域は、ｄ９からｄ１１までの領域であることを探索ブロック２に伝える。
【００２２】
探索ブロック２では、全ての探索領域のデータを備えているが、探索ブロック１で用いるデータを除いたものであってもよい。その中央にあるｄ１０とサーチキーとを比較することになる。さらに、ここでは、ｄ１０より小さいという結果であったとすると、最後にｄ９だけが残ることになるので、ｄ９を探索結果として出力してからｄ９とサーチキーとが一致するかどうかを確かめることになる。この操作によって、探索領域にサーチキーがあるかどうかを知ることが出来る。
【００２３】
このような構成にすることによって、探索ブロック１では、探索回数を２回にすることができ、この２回の探索の後には、あらたにサーチキーを受け付けることが出来るようになり、スループットが向上する。また、ブロック１で用いるメモリ数は少数で良いので、消費電流が大きくても高速動作のメモリを用いても全体の消費電力の増加を僅かなものに抑えることが出来る。
【００２４】
また、探索ブロック２では、探索回数は１回となるので、低速のメモリを用いてもよいことは明らかである。一般に高集積度のメモリや低消費電流のメモリは低速動作であるので、図５に示す従来例に低速メモリを用いた場合と比較して、低消費電流あるいは高速に、また、条件次第で低消費電流であって高速に探索を行なうことができる。
【００２５】
探索領域を変えるには、よく知られた２分木探索で用いる代表点の決定方法に従って、探索ブロック１に蓄えるべきデータを用意することは容易である。つまり、従来の最初の代表点１つと第２の代表点の２つを選択する。このような選択は、図１に示す制御回路３が行なう。
【実施例２】
【００２６】
より一般的には、図２に示す様にする。入力したサーチキーが探索領域にあるかどうかを見るために、探索ブロック４の探索結果をもとに探索領域を絞り込み、こうして絞り込まれた探索領域について探索ブロック５で探索を行なう。これと同様に、探索ブロック５の探索結果をもとに探索領域を絞り込み、こうして絞り込まれた探索領域について探索ブロック６で探索を行なう。探索領域−３は、探索すべきデータを全て保存しておく。探索ブロック４の探索領域−１には、探索領域−３のデータについて従来の２分木探索で探索する場合の最初の代表点から、予め決めた第Ｋ次の探索の２(K-1)個の代表点までの（２K−１）個のデータを保存する。また、探索ブロック５の探索領域には、第（Ｋ＋１）次の探索の代表点から予め決めた第Ｍ次の探索の代表点までのデータを保存する。探索ブロック１の結果で探索ブロック５で探索すべき領域（探索領域−２）を決定する。また、探索ブロック５の結果で探索ブロック６で探索すべき領域（探索領域−３）を決定する。
【００２７】
一般に第Ｋ次の探索に於いては、２K個の代表点が属するので、より後方の探索ブロックでより多くのデータを保存するためのメモリ数が必要である。このため、より前方の探索ブロックでより高速動作のメモリや探索回路を用いることが望ましい。しかし、サーチキーを順次送り込むには、それぞれの探索ブロックのスループットが等しいことが望ましく、またそのスループットが等しくなるように、それぞれの探索ブロックで行なう探索回数や探索回路の動作速度、あるいは探索領域用のメモリの動作速度を設定することが望ましい。
【実施例３】
【００２８】
上記の例では、複数回の２分木探索を行う探索ブロックを含んでいたが、それぞれの探索ブロックでの探索を１回に制限すると、さらに高速の２分木探索を実現することができる。このような探索は、動作速度の低い記憶装置を用いて、高速な探索を行なう場合に有効である。例えば、大容量の半導体集積回路で、低速な記憶回路のみを用いて高速な探索を行なう場合には、探索のスループットを改善する場合には多層階層の探索を行なうことになるが、多層化によってサーチキーが探索回路にある滞在時間は長くなる傾向にある。この実施例では、滞在時間を短くすることができるので、入力から出力までの時間を改善することができる。また、探索回路全体を本実施例のように、探索を１回に制限した回路のみで作る必要はなく、回路規模の増大を避けるために、探索初めの数段のブロックを本実施例の回路で作り、後段のブロックで大記憶容量の必要な部分では、上記の様な各ブロックごとに複数回の２分木探索を行なうようにしてもよい。
【００２９】
図３にそれぞれの探索ブロックで２分木探索を１度のみ行なう場合の例を示す。この場合に想定する探索領域は、図５の場合と同様にｄ１からｄ１５までの昇順にソートされた集合である。第１の探索ブロックでは、第１次の探索を行う。この場合の探索領域はＳ１である。まず、入力されたサーチキーとｄ８を大小一致の比較を行なう。ここでｄ８は、探索領域の中央にあるために２分木探索に用いているが、探索の能率が僅かに低下してよい場合は、必ずしも探索領域の中央に位置するデータを用いる必要はなく、それから少しはずれていてもよい。この事情は、通常の２分木探索と同様である。第１次の探索では、用いるデータは１つであるので、メモリも１つ用意する。この探索によって、ｄ８と一致するか、あるいはｄ８に対する相対位置かが明らかになる。ここでは、ｄ８に比べて大きいとすると、探索領域は、Ｓ２となる。
【００３０】
つぎに、このＳ２について、第２次の探索を行なうが、そのためにサーチキーとｄ１２との比較を行なう。この比較によって、探索領域が例えばＳ３に絞り込まれる。
【００３１】
さらに、このＳ３について、第３次の探索を行なうが、そのためにサーチキーとｄ１０との比較を行なう。この比較によって、探索領域が例えばｄ９に絞り込まれる。最後にｄ９は入力されたサーチキーと比較され、一致しているかどうか確かめられる。
【００３２】
このような２分木探索の全体像を図４に示す。この図４は、例えば第１次の探索で、サーチキーとｄ８とを比較してサーチキーの方が大きければ、サーチキーとｄ１２とを比較するル−トに進み、サーチキーの方が小さければサーチキーとｄ４とを比較するル−トに進む。また、サーチキーとｄ８とが一致する場合は、遅延器を通過して一致信号として出力する。ここで遅延器を通過させるのは、最後に絞り込まれたデータが出力される時期と一致させるためである。ｄ４あるいはｄ１２との比較以下では、これと同様にしてル−トを選択するものである。
【００３３】
上記の実施例１あるいは２においては、大小一致を判定する比較回路としてプログラム制御の比較回路を用いることも可能であるが、実施例３の場合には、論理回路で構成された比較回路であることがその高速性の観点から望ましい。例えば図６（ａ）の論理回路は、図６（ｂ）の論理式に相当する論理回路が組まれているものである。入力Ａ、Ｂに１ビットの２進数が入力されると、Ａが大きければ出力Ｘ＝１となり、一致すればＹ＝１となり、Ｂが大きければＺ＝１となる。
【００３４】
次に、入力Ａ、Ｂに図６（ｃ）に示す多桁の２進数が入力される場合には、例えば図６（ｄ）の回路で、Ｙ１、Ｘ１あるいはＺ１を調べることによって、Ａ、Ｂ間の大あるいは小と一致とを判定することができる。図４のそれぞれの比較判定には、このような回路をそれぞれに配置する。このため、回路規模は大型になるが、探索速度は高速である。また、この実施例３の回路を、上記の実施例１あるいは２の第１次あるいは第２次の探索にのみ適用して、初段部で探索速度を高速化して、全体としては、回路規模の大型化を抑制することも可能である。
【実施例４】
【００３５】
図７に示す様に、２分探索で探索領域Ａを２層の２分探索で探索する場合を考える。よく知られているように、探索領域が決まると、探索回数Ｋが決まる。この際、探索領域Ａを複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域Ｂとする。探索領域Ｂでは、入力されたサーチキーにもっとも近い代表点を探索して、探索領域Ａのひとつの部分探索領域Ｃを指定する。つまり、Ｋ回の２分探索からｍ回を探索領域Ｂでの探索にあて、残りのＫ−ｍ回を部分探索領域Ｃでの探索とする。また、探索領域Ｂに引き続いて探索領域Ｃの探索を行なう一方、同時に、探索領域Ｂでは、あらたなサーチキーを入力してあらたな探索を開始する。
【００３６】
一般に、それぞれの探索領域は、記憶装置に設けられた特定の領域であり、２分探索手段は、論理回路やマイクロプログラムをもった論理回路である。また、探索領域Ａは、探索領域Ｂよりも大容量である必要がある。ところが大容量の記憶装置は、一般に動作が遅いために、探索領域Ｃでの探索割合を大きくすると探索完了する時間が大きくなり、また、探索領域Ｂであらたな探索を始めるまでの待ち時間が大きくなることは容易に理解できる。
【００３７】
このような場合に探索のスループットの最適条件を求める事が出来る。基礎となる条件として、図７に示す様に、探索領域Ｂ、Ｃでのそれぞれの探索回数をｍ、Ｋ−ｍとし、また、それぞれの探索時間をｔB、ｔCとする。
このとき、ひとつのサーチキーについては、
経過時間＝ｍ×ｔB ＋（Ｋ−ｍ）×ｔC、
で探索が終了する。また、探索領域Ｂでの探索から探索領域Ｃでの探索に移るまでの時間として、ｍ×ｔB以上必要である。また、探索領域Ｃについての探索を終了するためには、（Ｋ−ｍ）×ｔC以上必要である。これは、あらたなサーチキーについて、探索領域Ｂでの探索から探索領域Ｃでの探索に移るまでに、満足しておく必要のある条件でもある。従って、探索領域Ｂ、Ｃを同じ周期で行なうには、その周期を、（ｍ×ｔB、（Ｋ−ｍ）×ｔC）のうちの大きいほうに設定する必要がある。
【００３８】
このように設定される周期を小さくすることで、探索のスループットを最適化できることは明らかである。図８は、これを説明する図であって、探索領域Ｂの探索回数を横軸に、また探索時間を縦軸にして、探索が終了するまでの滞在時間と、探索領域Ｃ、Ｂでのそれぞれの探索時間とを示す。上記の様に、探索領域Ａ、Ｂを同じ周期で行なうには、周期は（ｍ×ｔB、（Ｋ−ｍ）×ｔC）の大きいほうで決まるので、図８の太実線Ｔでの最小点（Ｓ）の値を求めればよいことが分かる。これから求まるｍは、
ｍ＝ＫｔC／（ｔC＋ｔB）、
であるが、ｍは整数である必要があることから、この値に最も近い整数を用いればよい事は明らかである。例えば、ｔCとｔBとが等しいときには、それぞれ半分ずつで割り振ればよい。また、ｔC＞＞ｔBの場合には、殆どの探索を探索領域Ｂで処理するとよい。特に、ｔCがｔBの（Ｋ−１）場合を超える場合には、探索領域Ａでの探索は１度あるいはゼロにするのが望ましいことが分かる。
【００３９】
また、上記の説明では、ｔCあるいはｔBは一定であるとしたが、一般には、記憶装置の特性から探索ごとに僅かに変動することが多い。このような場合には、ｔCあるいはｔBとしては、それぞれの平均値を用いればよい。
【００４０】
また、上記では、２分探索を２層に分けて行なう場合を説明したが、さらに多層にすることによって、それぞれの層での探索回数をすくなくすることができるので、探索のスループットを改善することができる。この場合に探索回数の配分を変えてスループットを最適化するためには、多層に分けた引き続く２層に注目して、上記の取り扱いと同様にして最適化をはかることができる。
【００４１】
また、多層の探索でスループットを改善するための最適化については、次のように進めることができる。まず、２からＮまでのｎについて、前記の探索領域（ｎ−１）を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域ｎとする。また、１からＮまでのｎについて、それぞれの探索領域ｎのすべての要素を記憶する記憶手段ｎと、前記探索領域ｎを探索する探索手段ｎとについて、記憶手段ｎの記憶容量をｃ（ｎ）とし、探索領域ｎの探索のスループットをｂ（ｎ）とする。さらに、サーチキーの入力レートは、一定であり、その入力レートのビットレートをb(input)とする。
探索領域のビットサイズをＭとし、探索手段ｎの行なう探索領域ｎに属する要素とサーチキーとの比較回数をp（ｎ）と、するとき、
ｃ（１）＞ｃ（２）＞・・・＞ｃ（Ｎ）、
ｂ（１）＜ｂ（２）＜・・・＜ｂ（Ｎ）、
ｂ(ｎ) / ｐ(ｎ) ≧ ｂ(input)、
ｂ(ｎ) ≦ log2ｃ(ｎ)、
なる条件を満たし、
１からＮまでのp(ｎ）の和について、底を２としたＭの対数を切り上げた整数と等しくなるように、１からＮまでのｎについて、ｂ（ｎ）、ｃ（ｎ）、p（ｎ）を定める。このような多変数を用いた関数の最適化には、市販されたコンピュ−タプログラムがありそれを用いることができる。
【００４２】
また、上記の実施例では、２分木探索を用いる方法について説明したが、大規模な探索領域を小規模な探索領域の処理の集合に変換することによって、ハッシュ法を用いることが困難でなくなる。特に上記の実施例の場合の初段の探索にハッシュ法を適用して初段部分を高速化することで、全体のスループットを改善することは容易である。
【産業上の利用可能性】
【００４３】
本発明の探索方法を用いた高速パターンマッチング装置をインタ−ネット通信に適用することによって、パソコンや携帯電話などを含むあらゆるインタ−ネット通信機器からの有害ＵＲＬへのアクセスを検出してそれをリアルタイムで防止することが低コストで可能になる。
【図面の簡単な説明】
【００４４】
【図１】第１の実施例を示すブロック図である。
【図２】第２の実施例を示すブロック図である。
【図３】第３の実施例を示す模式図である。
【図４】それぞれの探索ブロックでの探索を１回にして高速の２文探索を実現する例を示すブロック図である。
【図５】従来の２分木探索法を示す模式図である。
【図６】論理回路で構成された比較回路例を示すブロック図である。
【図７】２分探索で探索領域Ａを２層の２分探索で探索する場合を示すブロック図である。
【図８】探索回数を横軸、探索時間を縦軸にして、探索が終了するまでの時間と、それぞれの探索領域での探索時間とを示す図である。
【符号の説明】
【００４５】
１、２ 探索ブロック
３ 制御回路
４、５、６ 探索ブロック
【技術分野】
【０００１】
この発明は、バイナリデータのパターンマッチングを高速に行う高速パターンマッチング装置の探索方法に関している。
【背景技術】
【０００２】
本発明は、従来のものに比べて高速で動作するパターンマッチング装置に関するものであるが、従来の速度で動作するものは、種々の装置に組み込まれて用いられている。例えば、コンピュ−タ上でデータの照合を行って目的とするデータを検索するデータベ−スには、種々のパターンマッチング技術が使われている。ここで用いられるパターンマッチングには、逐次探索（順探索あるいはリニアサーチとも呼ばれる）、ハッシュ法、２分木探索（２分探索あるいはバイナリサーチとも呼ばれる）などがある。
【０００３】
逐次探索は、探索領域のデータとサーチキーとの照合を順次進めるものであり、探索時間のサーチキー依存が激しく、また平均探索時間が長い、という特徴がある。
【０００４】
また、ハッシュ法は、探索領域のそれぞれのデータのハッシュ値を求めてハッシュテ−ブルを作成し、ハッシュ値にそれぞれのデータを連想するように対応させておくものであり、サーチキーのハッシュ値を入力して探索データを出力するように関数を作成しておく。このため短時間での探索が可能であるという利点があるが、探索領域（ア−カイブ）を変化させるためには、ハッシュ法に用いるハッシュテ−ブルを作り直す必要があり、大規模の探索領域を頻繁に変えるための処理に多大の時間が必要である、という特徴がある。
【０００５】
また、２分木探索は、探索領域をソートしておき、サーチキーと探索領域の代表点のデータ（多くの場合は、中央のデータ）との大小一致比較で新たな探索領域に絞り込み、その新たな探索領域でも、新たな代表点を選択して、その代表点とサーチキーとの大小一致比較によって、さらに新たな探索領域に絞り込む、という作業を繰り返して、探索するものである。この方法による探索時間は上記の２つの探索方法の中間的なものであり、大規模の探索領域を行なう場合でも、逐次探索の場合と同様な準備で探索を開始できる、という特徴がある。
【０００６】
高速探索が必要な大規模探索領域としては、例えば、情報通信ネットワークにおいて、有害情報の除去などのためのフィルタリングや顧客情報の検索などの際の探索領域である。ネットワークは、ますます高速化複雑化するため、これに対応できる強力なパターンマッチング装置の開発が求められている。
【０００７】
本発明は、主に上記の２分木探索に関しており、同等の回路を用いる場合に、従来よりも高速の探索を可能ならしめるものである。
【０００８】
［従来例１］
図５（ａ）に示す様に、ｄ１からｄ１５まで昇順にソートされた探索領域について、２分木探索を行なう場合を図５（ｂ）に沿って示す。探索領域のデータ数が極端に少ないのは、説明を容易にして誤解を避けるためであって、実際に適用する探索領域は、さらに多数のデータを含む領域である。サーチキーの入力があると、これと中央にあるｄ８とを比較する。この比較で、サーチキーとの一致あるいは大小関係を出力する。一致する場合は、ｄ８と一致する旨出力する。ここでは、ｄ８より大きいという結果であったとすると、あらたにｄ９からｄ１５までを新たな探索領域とすることになるので、その中央にあるｄ１２とサーチキーとを比較することになる。また、ここでは、ｄ１２より小さいという結果であったとすると、あらたにｄ９からｄ１１までを新たな探索領域とすることになるので、その中央にあるｄ１０とサーチキーとを比較することになる。さらに、ここでは、ｄ１０より小さいという結果であったとすると、最後にｄ９だけが残ることになるので、ｄ９とサーチキーとが一致するかどうかを確かめることになる。この操作によって、探索領域にサーチキーがあるかどうかを知ることが出来る。このようにデータ数が１５の探索領域であっても、３回の大小一致比較で最終的な候補に絞ることができる。この操作はひとつの比較手段をプログラムに従って動作させて２分木探索を行なっている。
【０００９】
しかし、比較的大きな探索領域に従来の２分木探索を適用する場合には、その探索領域を構成する記憶装置が大容量のものとなり、一般に大容量の記憶装置でのデータアクセス時間や読み出し時間は比較的大きいので、高速動作には適しておらず、充分に高速にパターンマッチングを進めることができないという問題があった。
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は、高速な２分木探索を実現するものである。
【発明の効果】
【００１１】
この発明によって、大規模な探索領域に対しても、同等の速度の電子回路を用いる場合に、従来よりも高速の探索が可能になる。
【課題を解決するための手段】
【００１２】
本発明は、大略では、探索領域とサーチキーが与えられたときに、探索領域の個々の要素を記憶装置に記憶させ、この要素を比較手段である比較回路に読み出してサーチキーとの照合を行なって探索を進める際に、従来の様にひとつの記憶装置を用いて探索を行なうのではなく、大まかな探索を高速な探索手段を用いて行い、徐々に大容量の記憶装置でのより詳しい探索へと進むものである。より詳しくは、以下に示す。
【００１３】
まず本発明は、予め決められた探索領域Ａを入力されたサーチキーについて探索する場合に、前記の探索領域Ａを複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域Ｂとするとき、
前記のあらたな探索領域Ｂを記憶する記憶手段Ｂと、前記のあらたな探索領域Ｂを上記のサーチキーについて探索する探索手段Ｂと、
前記の予め決められた探索領域Ａを記憶する記憶手段Ａと、前記の予め決められた探索領域Ａから選択された部分探索領域Ｃを上記のサーチキーについて探索する探索手段Ａと、を備えるパターンマッチング装置の探索方法であって、
前記のあらたな探索領域Ｂを上記のサーチキーについて探索した結果をもとに、上記の複数の部分探索領域から１つを選択してこれを部分探索領域Ｃとするとき、
選択された部分探索領域Ｃについて上記の探索手段Ａを用いて上記のサーチキーについて探索するステップと、
探索結果を出力するステップと、
を備えることを特徴としている。
【００１４】
上記の探索領域Ａは、探索領域Ａを含む探索領域から、何らかの選択方法により予め選択された探索領域であってもよい。
【００１５】
また、探索手段Ａと探索手段Ｂとは、同じ周期で探索をおこない、
探索手段Ｂは、上記のサーチキーについての探索を探索領域Ｂで行い、引き続き新たなサーチキーについての探索を探索領域Ｂで行うものであり、
探索手段Ａは、探索手段Ｂが上記のサーチキーにつての探索を終了した後、上記のサーチキーにつての探索を部分探索領域Ｃで行い、引き続き上記の新たなサーチキーについての探索を部分探索領域Ｃで行うようにして、次々に新しいサーチキーで探索を行なうことが出来る。
【００１６】
探索手段Ａ、Ｂは２分探索を用いた探索手段であり、探索領域Ｂにおいてサーチキーとの比較を１度行なう探索時間あるいはその平均を探索時間Ｂとし、部分探索領域Ｃにおいてサーチキーとの比較を１度行なう探索時間あるいはその平均を探索時間Ａとし、サーチキーとの比較を１度行なう毎に加算する探索回数をそれぞれ探索回数Ａ、Ｂとするとき、
探索時間の大きい方の探索回数を小さく設定することによって、一連の探索に要する時間を短縮することが出来る。
【００１７】
前記の場合に、探索回数Ａと探索回数Ｂとの和をＫとするとき、探索領域Ａを２分探索する場合には、探索回数Ａ、Ｂの割り振り方にはＫの値は依存しない。このとき、探索回数Ｂは、Ｋ×探索時間Ａを、探索時間Ａと探索時間Ｂとの和で除した数に最も近い整数とすると、探索手段Ａ、Ｂの一方のみに負担がかかることを回避できる。
【００１８】
また、上記の探索方法は、３層以上の多層構成とすることも可能であり、
第１の記憶装置に記憶され予め決められた第１の探索領域を入力されたサーチキーについて探索する場合に、
前記の第１の探索領域を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合を第２の記憶装置に記憶して第２の探索領域２とし、
以下順次に、３からＮまでのｎについて、
第（ｎ−１）の記憶装置に記憶した前記の第（ｎ−１）の探索領域を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合を第ｎの記憶装置に記憶して第ｎの探索領域とし、
第Ｎの探索領域を入力されたサーチキーについて第Ｎの探索手段を用いて２分木探索を行い、その探索結果をもとに、探索領域（Ｎ−１）の部分探索領域を選択し、
以下、順に、Ｎ−１から２までのｎについて、
探索領域ｎを入力されたサーチキーについて第ｎの探索手段を用いて探索し、その探索結果をもとに、探索領域（ｎ−１）の部分探索領域を選択し、
探索領域１の選択された部分探索領域についての探索を第１の探索手段で行なって探索結果を出力するものである。
【００１９】
上記の探索方法が特に有効なのは、次の構成にそれを適用する場合であって、
２からＮまでのｎについて、
前記の探索領域（ｎ−１）を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域ｎとし、
１からＮまでのｎについて、
それぞれの探索領域ｎのすべての要素を記憶する記憶手段ｎと、前記探索領域ｎを探索する探索手段ｎとについて、
記憶手段ｎの記憶容量をｃ（ｎ）とし、探索領域ｎの探索のスループットをｂ（ｎ）とし、
サーチキーの入力レートは、一定であり、その入力レートのビットレートをb(input)とし、
探索領域のビットサイズをＭとし、
探索手段ｎの行なう探索領域ｎに属する要素とサーチキーとの比較回数をp（ｎ）と、
するとき、
ｃ（１）＞ｃ（２）＞・・・＞ｃ（Ｎ）、
ｂ（１）＜ｂ（２）＜・・・＜ｂ（Ｎ）、
ｂ(ｎ) / ｐ(ｎ) ≧ ｂ(input)、かつ、
ｂ(ｎ) ≦ log2ｃ(ｎ)、
なる条件を満たし、
１からＮまでのp(ｎ）の和について、底を２としたＭの対数、log2Ｍ、を切り上げた整数と等しくなるように、
１からＮまでのｎについて、
ｂ（ｎ）、ｃ（ｎ）、p（ｎ）を定めた探索装置に、上記の探索方法を適用することが望ましい。
【発明を実施するための最良の形態】
【００２０】
以下にこの発明の実施の形態を詳細に説明するが、以下の説明においては、決められた探索領域についてサーチキーと比較するデータを代表点と呼ぶことにする。
【実施例１】
【００２１】
図１に示す例は、簡単のために図５と同じ探索領域についての探索を行なう場合を示している。図１の探索ブロック１では、２分木探索回路に３データ分のメモリが接続されている。第１次の２分木探索として、サーチキーの入力があると、これと中央にあるｄ８とを比較する。この比較で、サーチキーとの一致あるいは大小関係を出力する。一致する場合は、ｄ８と一致する旨出力する。ここでは、ｄ８より大きいという結果であったとすると、第２次の２分木探索として、あらたにｄ９からｄ１５までを新たな探索領域とすることになるので、その中央にあるｄ１２とサーチキーとを比較することになる。また、ここでは、ｄ１２より小さいという結果であったとすると、第３次の２分木探索として、あらたにｄ９からｄ１１までを新たな探索領域とすることになるので、新たな探索領域は、ｄ９からｄ１１までの領域であることを探索ブロック２に伝える。
【００２２】
探索ブロック２では、全ての探索領域のデータを備えているが、探索ブロック１で用いるデータを除いたものであってもよい。その中央にあるｄ１０とサーチキーとを比較することになる。さらに、ここでは、ｄ１０より小さいという結果であったとすると、最後にｄ９だけが残ることになるので、ｄ９を探索結果として出力してからｄ９とサーチキーとが一致するかどうかを確かめることになる。この操作によって、探索領域にサーチキーがあるかどうかを知ることが出来る。
【００２３】
このような構成にすることによって、探索ブロック１では、探索回数を２回にすることができ、この２回の探索の後には、あらたにサーチキーを受け付けることが出来るようになり、スループットが向上する。また、ブロック１で用いるメモリ数は少数で良いので、消費電流が大きくても高速動作のメモリを用いても全体の消費電力の増加を僅かなものに抑えることが出来る。
【００２４】
また、探索ブロック２では、探索回数は１回となるので、低速のメモリを用いてもよいことは明らかである。一般に高集積度のメモリや低消費電流のメモリは低速動作であるので、図５に示す従来例に低速メモリを用いた場合と比較して、低消費電流あるいは高速に、また、条件次第で低消費電流であって高速に探索を行なうことができる。
【００２５】
探索領域を変えるには、よく知られた２分木探索で用いる代表点の決定方法に従って、探索ブロック１に蓄えるべきデータを用意することは容易である。つまり、従来の最初の代表点１つと第２の代表点の２つを選択する。このような選択は、図１に示す制御回路３が行なう。
【実施例２】
【００２６】
より一般的には、図２に示す様にする。入力したサーチキーが探索領域にあるかどうかを見るために、探索ブロック４の探索結果をもとに探索領域を絞り込み、こうして絞り込まれた探索領域について探索ブロック５で探索を行なう。これと同様に、探索ブロック５の探索結果をもとに探索領域を絞り込み、こうして絞り込まれた探索領域について探索ブロック６で探索を行なう。探索領域−３は、探索すべきデータを全て保存しておく。探索ブロック４の探索領域−１には、探索領域−３のデータについて従来の２分木探索で探索する場合の最初の代表点から、予め決めた第Ｋ次の探索の２(K-1)個の代表点までの（２K−１）個のデータを保存する。また、探索ブロック５の探索領域には、第（Ｋ＋１）次の探索の代表点から予め決めた第Ｍ次の探索の代表点までのデータを保存する。探索ブロック１の結果で探索ブロック５で探索すべき領域（探索領域−２）を決定する。また、探索ブロック５の結果で探索ブロック６で探索すべき領域（探索領域−３）を決定する。
【００２７】
一般に第Ｋ次の探索に於いては、２K個の代表点が属するので、より後方の探索ブロックでより多くのデータを保存するためのメモリ数が必要である。このため、より前方の探索ブロックでより高速動作のメモリや探索回路を用いることが望ましい。しかし、サーチキーを順次送り込むには、それぞれの探索ブロックのスループットが等しいことが望ましく、またそのスループットが等しくなるように、それぞれの探索ブロックで行なう探索回数や探索回路の動作速度、あるいは探索領域用のメモリの動作速度を設定することが望ましい。
【実施例３】
【００２８】
上記の例では、複数回の２分木探索を行う探索ブロックを含んでいたが、それぞれの探索ブロックでの探索を１回に制限すると、さらに高速の２分木探索を実現することができる。このような探索は、動作速度の低い記憶装置を用いて、高速な探索を行なう場合に有効である。例えば、大容量の半導体集積回路で、低速な記憶回路のみを用いて高速な探索を行なう場合には、探索のスループットを改善する場合には多層階層の探索を行なうことになるが、多層化によってサーチキーが探索回路にある滞在時間は長くなる傾向にある。この実施例では、滞在時間を短くすることができるので、入力から出力までの時間を改善することができる。また、探索回路全体を本実施例のように、探索を１回に制限した回路のみで作る必要はなく、回路規模の増大を避けるために、探索初めの数段のブロックを本実施例の回路で作り、後段のブロックで大記憶容量の必要な部分では、上記の様な各ブロックごとに複数回の２分木探索を行なうようにしてもよい。
【００２９】
図３にそれぞれの探索ブロックで２分木探索を１度のみ行なう場合の例を示す。この場合に想定する探索領域は、図５の場合と同様にｄ１からｄ１５までの昇順にソートされた集合である。第１の探索ブロックでは、第１次の探索を行う。この場合の探索領域はＳ１である。まず、入力されたサーチキーとｄ８を大小一致の比較を行なう。ここでｄ８は、探索領域の中央にあるために２分木探索に用いているが、探索の能率が僅かに低下してよい場合は、必ずしも探索領域の中央に位置するデータを用いる必要はなく、それから少しはずれていてもよい。この事情は、通常の２分木探索と同様である。第１次の探索では、用いるデータは１つであるので、メモリも１つ用意する。この探索によって、ｄ８と一致するか、あるいはｄ８に対する相対位置かが明らかになる。ここでは、ｄ８に比べて大きいとすると、探索領域は、Ｓ２となる。
【００３０】
つぎに、このＳ２について、第２次の探索を行なうが、そのためにサーチキーとｄ１２との比較を行なう。この比較によって、探索領域が例えばＳ３に絞り込まれる。
【００３１】
さらに、このＳ３について、第３次の探索を行なうが、そのためにサーチキーとｄ１０との比較を行なう。この比較によって、探索領域が例えばｄ９に絞り込まれる。最後にｄ９は入力されたサーチキーと比較され、一致しているかどうか確かめられる。
【００３２】
このような２分木探索の全体像を図４に示す。この図４は、例えば第１次の探索で、サーチキーとｄ８とを比較してサーチキーの方が大きければ、サーチキーとｄ１２とを比較するル−トに進み、サーチキーの方が小さければサーチキーとｄ４とを比較するル−トに進む。また、サーチキーとｄ８とが一致する場合は、遅延器を通過して一致信号として出力する。ここで遅延器を通過させるのは、最後に絞り込まれたデータが出力される時期と一致させるためである。ｄ４あるいはｄ１２との比較以下では、これと同様にしてル−トを選択するものである。
【００３３】
上記の実施例１あるいは２においては、大小一致を判定する比較回路としてプログラム制御の比較回路を用いることも可能であるが、実施例３の場合には、論理回路で構成された比較回路であることがその高速性の観点から望ましい。例えば図６（ａ）の論理回路は、図６（ｂ）の論理式に相当する論理回路が組まれているものである。入力Ａ、Ｂに１ビットの２進数が入力されると、Ａが大きければ出力Ｘ＝１となり、一致すればＹ＝１となり、Ｂが大きければＺ＝１となる。
【００３４】
次に、入力Ａ、Ｂに図６（ｃ）に示す多桁の２進数が入力される場合には、例えば図６（ｄ）の回路で、Ｙ１、Ｘ１あるいはＺ１を調べることによって、Ａ、Ｂ間の大あるいは小と一致とを判定することができる。図４のそれぞれの比較判定には、このような回路をそれぞれに配置する。このため、回路規模は大型になるが、探索速度は高速である。また、この実施例３の回路を、上記の実施例１あるいは２の第１次あるいは第２次の探索にのみ適用して、初段部で探索速度を高速化して、全体としては、回路規模の大型化を抑制することも可能である。
【実施例４】
【００３５】
図７に示す様に、２分探索で探索領域Ａを２層の２分探索で探索する場合を考える。よく知られているように、探索領域が決まると、探索回数Ｋが決まる。この際、探索領域Ａを複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域Ｂとする。探索領域Ｂでは、入力されたサーチキーにもっとも近い代表点を探索して、探索領域Ａのひとつの部分探索領域Ｃを指定する。つまり、Ｋ回の２分探索からｍ回を探索領域Ｂでの探索にあて、残りのＫ−ｍ回を部分探索領域Ｃでの探索とする。また、探索領域Ｂに引き続いて探索領域Ｃの探索を行なう一方、同時に、探索領域Ｂでは、あらたなサーチキーを入力してあらたな探索を開始する。
【００３６】
一般に、それぞれの探索領域は、記憶装置に設けられた特定の領域であり、２分探索手段は、論理回路やマイクロプログラムをもった論理回路である。また、探索領域Ａは、探索領域Ｂよりも大容量である必要がある。ところが大容量の記憶装置は、一般に動作が遅いために、探索領域Ｃでの探索割合を大きくすると探索完了する時間が大きくなり、また、探索領域Ｂであらたな探索を始めるまでの待ち時間が大きくなることは容易に理解できる。
【００３７】
このような場合に探索のスループットの最適条件を求める事が出来る。基礎となる条件として、図７に示す様に、探索領域Ｂ、Ｃでのそれぞれの探索回数をｍ、Ｋ−ｍとし、また、それぞれの探索時間をｔB、ｔCとする。
このとき、ひとつのサーチキーについては、
経過時間＝ｍ×ｔB ＋（Ｋ−ｍ）×ｔC、
で探索が終了する。また、探索領域Ｂでの探索から探索領域Ｃでの探索に移るまでの時間として、ｍ×ｔB以上必要である。また、探索領域Ｃについての探索を終了するためには、（Ｋ−ｍ）×ｔC以上必要である。これは、あらたなサーチキーについて、探索領域Ｂでの探索から探索領域Ｃでの探索に移るまでに、満足しておく必要のある条件でもある。従って、探索領域Ｂ、Ｃを同じ周期で行なうには、その周期を、（ｍ×ｔB、（Ｋ−ｍ）×ｔC）のうちの大きいほうに設定する必要がある。
【００３８】
このように設定される周期を小さくすることで、探索のスループットを最適化できることは明らかである。図８は、これを説明する図であって、探索領域Ｂの探索回数を横軸に、また探索時間を縦軸にして、探索が終了するまでの滞在時間と、探索領域Ｃ、Ｂでのそれぞれの探索時間とを示す。上記の様に、探索領域Ａ、Ｂを同じ周期で行なうには、周期は（ｍ×ｔB、（Ｋ−ｍ）×ｔC）の大きいほうで決まるので、図８の太実線Ｔでの最小点（Ｓ）の値を求めればよいことが分かる。これから求まるｍは、
ｍ＝ＫｔC／（ｔC＋ｔB）、
であるが、ｍは整数である必要があることから、この値に最も近い整数を用いればよい事は明らかである。例えば、ｔCとｔBとが等しいときには、それぞれ半分ずつで割り振ればよい。また、ｔC＞＞ｔBの場合には、殆どの探索を探索領域Ｂで処理するとよい。特に、ｔCがｔBの（Ｋ−１）場合を超える場合には、探索領域Ａでの探索は１度あるいはゼロにするのが望ましいことが分かる。
【００３９】
また、上記の説明では、ｔCあるいはｔBは一定であるとしたが、一般には、記憶装置の特性から探索ごとに僅かに変動することが多い。このような場合には、ｔCあるいはｔBとしては、それぞれの平均値を用いればよい。
【００４０】
また、上記では、２分探索を２層に分けて行なう場合を説明したが、さらに多層にすることによって、それぞれの層での探索回数をすくなくすることができるので、探索のスループットを改善することができる。この場合に探索回数の配分を変えてスループットを最適化するためには、多層に分けた引き続く２層に注目して、上記の取り扱いと同様にして最適化をはかることができる。
【００４１】
また、多層の探索でスループットを改善するための最適化については、次のように進めることができる。まず、２からＮまでのｎについて、前記の探索領域（ｎ−１）を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域ｎとする。また、１からＮまでのｎについて、それぞれの探索領域ｎのすべての要素を記憶する記憶手段ｎと、前記探索領域ｎを探索する探索手段ｎとについて、記憶手段ｎの記憶容量をｃ（ｎ）とし、探索領域ｎの探索のスループットをｂ（ｎ）とする。さらに、サーチキーの入力レートは、一定であり、その入力レートのビットレートをb(input)とする。
探索領域のビットサイズをＭとし、探索手段ｎの行なう探索領域ｎに属する要素とサーチキーとの比較回数をp（ｎ）と、するとき、
ｃ（１）＞ｃ（２）＞・・・＞ｃ（Ｎ）、
ｂ（１）＜ｂ（２）＜・・・＜ｂ（Ｎ）、
ｂ(ｎ) / ｐ(ｎ) ≧ ｂ(input)、
ｂ(ｎ) ≦ log2ｃ(ｎ)、
なる条件を満たし、
１からＮまでのp(ｎ）の和について、底を２としたＭの対数を切り上げた整数と等しくなるように、１からＮまでのｎについて、ｂ（ｎ）、ｃ（ｎ）、p（ｎ）を定める。このような多変数を用いた関数の最適化には、市販されたコンピュ−タプログラムがありそれを用いることができる。
【００４２】
また、上記の実施例では、２分木探索を用いる方法について説明したが、大規模な探索領域を小規模な探索領域の処理の集合に変換することによって、ハッシュ法を用いることが困難でなくなる。特に上記の実施例の場合の初段の探索にハッシュ法を適用して初段部分を高速化することで、全体のスループットを改善することは容易である。
【産業上の利用可能性】
【００４３】
本発明の探索方法を用いた高速パターンマッチング装置をインタ−ネット通信に適用することによって、パソコンや携帯電話などを含むあらゆるインタ−ネット通信機器からの有害ＵＲＬへのアクセスを検出してそれをリアルタイムで防止することが低コストで可能になる。
【図面の簡単な説明】
【００４４】
【図１】第１の実施例を示すブロック図である。
【図２】第２の実施例を示すブロック図である。
【図３】第３の実施例を示す模式図である。
【図４】それぞれの探索ブロックでの探索を１回にして高速の２文探索を実現する例を示すブロック図である。
【図５】従来の２分木探索法を示す模式図である。
【図６】論理回路で構成された比較回路例を示すブロック図である。
【図７】２分探索で探索領域Ａを２層の２分探索で探索する場合を示すブロック図である。
【図８】探索回数を横軸、探索時間を縦軸にして、探索が終了するまでの時間と、それぞれの探索領域での探索時間とを示す図である。
【符号の説明】
【００４５】
１、２ 探索ブロック
３ 制御回路
４、５、６ 探索ブロック
【特許請求の範囲】
【請求項１】
予め決められた探索領域Ａを入力されたサーチキーについて探索する場合に、前記の探索領域Ａを複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域Ｂとするとき、
前記のあらたな探索領域Ｂを記憶する記憶手段Ｂと、前記のあらたな探索領域Ｂを上記のサーチキーについて探索する探索手段Ｂと、
前記の予め決められた探索領域Ａを記憶する記憶手段Ａと、前記の予め決められた探索領域Ａから選択された部分探索領域Ｃを上記のサーチキーについて探索する探索手段Ａと、を備えるパターンマッチング装置の探索方法であって、
前記のあらたな探索領域Ｂを上記のサーチキーについて探索した結果をもとに、上記の複数の部分探索領域から１つを選択してこれを部分探索領域Ｃとするとき、
選択された部分探索領域Ｃについて上記の探索手段Ａを用いて上記のサーチキーについて探索するステップと、
探索結果を出力するステップと、
を備えることを特徴とする探索方法。
【請求項２】
探索領域Ａは、探索領域Ａを含む探索領域から、何らかの選択方法により予め選択された探索領域であることを特徴とする請求項１に記載の探索方法。
【請求項３】
探索手段Ａと探索手段Ｂとは、同じ周期で探索をおこない、
探索手段Ｂは、上記のサーチキーについての探索を探索領域Ｂで行い、引き続き新たなサーチキーについての探索を探索領域Ｂで行うものであり、
探索手段Ａは、探索手段Ｂが上記のサーチキーにつての探索を終了した後、上記のサーチキーにつての探索を部分探索領域Ｃで行い、引き続き上記の新たなサーチキーについての探索を部分探索領域Ｃで行うことを特徴とする請求項１に記載の探索方法。
【請求項４】
探索手段Ａ、Ｂは２分探索を用いた探索手段であり、探索領域Ｂにおいてサーチキーとの比較を１度行なう探索時間あるいはその平均を探索時間Ｂとし、部分探索領域Ｃにおいてサーチキーとの比較を１度行なう探索時間あるいはその平均を探索時間Ａとし、サーチキーとの比較を１度行なう毎に加算する探索回数をそれぞれ探索回数Ｂ、Ａとするとき、
探索時間の大きい方の探索回数を小さく設定することを特徴とする請求項１、２あるいは３に記載の探索方法。
【請求項５】
探索回数Ａと探索回数Ｂとの和をＫとするとき、
探索回数Ｂは、Ｋと探索時間Ａとの積を、探索時間Ａと探索時間Ｂとの和で除した数に最も近い整数とすることを特徴とする請求項４に記載の探索方法。
【請求項６】
第１の記憶装置に記憶され予め決められた第１の探索領域を入力されたサーチキーについて探索する場合に、
前記の第１の探索領域を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合を第２の記憶装置に記憶して第２の探索領域２とし、
以下順次に、３からＮまでのｎについて、
第（ｎ−１）の記憶装置に記憶した前記の第（ｎ−１）の探索領域を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合を第ｎの記憶装置に記憶して第ｎの探索領域とし、
第Ｎの探索領域を入力されたサーチキーについて第Ｎの探索手段を用いて２分木探索を行い、その探索結果をもとに、探索領域（Ｎ−１）の部分探索領域を選択し、
以下、順に、Ｎ−１から２までのｎについて、
探索領域ｎを入力されたサーチキーについて第ｎの探索手段を用いて探索し、その探索結果をもとに、探索領域（ｎ−１）の部分探索領域を選択し、
探索領域１の選択された部分探索領域についての探索を第１の探索手段で行なって探索結果を出力することを特徴とする探索方法。
【請求項７】
請求項６に記載の探索方法であって、
２からＮまでのｎについて、
前記の探索領域（ｎ−１）を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域ｎとし、
１からＮまでのｎについて、
それぞれの探索領域ｎのすべての要素を記憶する記憶手段ｎと、前記探索領域ｎを探索する探索手段ｎとについて、
記憶手段ｎの記憶容量をｃ（ｎ）とし、探索領域ｎの探索のスループットをｂ（ｎ）とし、
サーチキーの入力レートは一定であり、その入力レートのビットレートをb(input)とし、
探索領域のビットサイズをＭとし、
探索手段ｎの行なう探索領域ｎに属する要素とサーチキーとの比較回数をp（ｎ）と、するとき、
ｃ（１）＞ｃ（２）＞・・・＞ｃ（Ｎ）、
ｂ（１）＜ｂ（２）＜・・・＜ｂ（Ｎ）、
ｂ(ｎ) / ｐ(ｎ) ≧ ｂ(input)、
ｂ(ｎ) ≦ log2ｃ(ｎ)、
なる条件を満たし、
１からＮまでのp(ｎ）の和について、底を２としたＭの対数を切り上げた整数と等しくなるように、
１からＮまでのｎについて定めた
ｂ（ｎ）、ｃ（ｎ）、p（ｎ）を用いることを特徴とする探索方法。
【請求項１】
予め決められた探索領域Ａを入力されたサーチキーについて探索する場合に、前記の探索領域Ａを複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域Ｂとするとき、
前記のあらたな探索領域Ｂを記憶する記憶手段Ｂと、前記のあらたな探索領域Ｂを上記のサーチキーについて探索する探索手段Ｂと、
前記の予め決められた探索領域Ａを記憶する記憶手段Ａと、前記の予め決められた探索領域Ａから選択された部分探索領域Ｃを上記のサーチキーについて探索する探索手段Ａと、を備えるパターンマッチング装置の探索方法であって、
前記のあらたな探索領域Ｂを上記のサーチキーについて探索した結果をもとに、上記の複数の部分探索領域から１つを選択してこれを部分探索領域Ｃとするとき、
選択された部分探索領域Ｃについて上記の探索手段Ａを用いて上記のサーチキーについて探索するステップと、
探索結果を出力するステップと、
を備えることを特徴とする探索方法。
【請求項２】
探索領域Ａは、探索領域Ａを含む探索領域から、何らかの選択方法により予め選択された探索領域であることを特徴とする請求項１に記載の探索方法。
【請求項３】
探索手段Ａと探索手段Ｂとは、同じ周期で探索をおこない、
探索手段Ｂは、上記のサーチキーについての探索を探索領域Ｂで行い、引き続き新たなサーチキーについての探索を探索領域Ｂで行うものであり、
探索手段Ａは、探索手段Ｂが上記のサーチキーにつての探索を終了した後、上記のサーチキーにつての探索を部分探索領域Ｃで行い、引き続き上記の新たなサーチキーについての探索を部分探索領域Ｃで行うことを特徴とする請求項１に記載の探索方法。
【請求項４】
探索手段Ａ、Ｂは２分探索を用いた探索手段であり、探索領域Ｂにおいてサーチキーとの比較を１度行なう探索時間あるいはその平均を探索時間Ｂとし、部分探索領域Ｃにおいてサーチキーとの比較を１度行なう探索時間あるいはその平均を探索時間Ａとし、サーチキーとの比較を１度行なう毎に加算する探索回数をそれぞれ探索回数Ｂ、Ａとするとき、
探索時間の大きい方の探索回数を小さく設定することを特徴とする請求項１、２あるいは３に記載の探索方法。
【請求項５】
探索回数Ａと探索回数Ｂとの和をＫとするとき、
探索回数Ｂは、Ｋと探索時間Ａとの積を、探索時間Ａと探索時間Ｂとの和で除した数に最も近い整数とすることを特徴とする請求項４に記載の探索方法。
【請求項６】
第１の記憶装置に記憶され予め決められた第１の探索領域を入力されたサーチキーについて探索する場合に、
前記の第１の探索領域を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合を第２の記憶装置に記憶して第２の探索領域２とし、
以下順次に、３からＮまでのｎについて、
第（ｎ−１）の記憶装置に記憶した前記の第（ｎ−１）の探索領域を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合を第ｎの記憶装置に記憶して第ｎの探索領域とし、
第Ｎの探索領域を入力されたサーチキーについて第Ｎの探索手段を用いて２分木探索を行い、その探索結果をもとに、探索領域（Ｎ−１）の部分探索領域を選択し、
以下、順に、Ｎ−１から２までのｎについて、
探索領域ｎを入力されたサーチキーについて第ｎの探索手段を用いて探索し、その探索結果をもとに、探索領域（ｎ−１）の部分探索領域を選択し、
探索領域１の選択された部分探索領域についての探索を第１の探索手段で行なって探索結果を出力することを特徴とする探索方法。
【請求項７】
請求項６に記載の探索方法であって、
２からＮまでのｎについて、
前記の探索領域（ｎ−１）を複数の部分探索領域に分割し、前記の部分探索領域のそれぞれの代表点の集合をあらたな探索領域ｎとし、
１からＮまでのｎについて、
それぞれの探索領域ｎのすべての要素を記憶する記憶手段ｎと、前記探索領域ｎを探索する探索手段ｎとについて、
記憶手段ｎの記憶容量をｃ（ｎ）とし、探索領域ｎの探索のスループットをｂ（ｎ）とし、
サーチキーの入力レートは一定であり、その入力レートのビットレートをb(input)とし、
探索領域のビットサイズをＭとし、
探索手段ｎの行なう探索領域ｎに属する要素とサーチキーとの比較回数をp（ｎ）と、するとき、
ｃ（１）＞ｃ（２）＞・・・＞ｃ（Ｎ）、
ｂ（１）＜ｂ（２）＜・・・＜ｂ（Ｎ）、
ｂ(ｎ) / ｐ(ｎ) ≧ ｂ(input)、
ｂ(ｎ) ≦ log2ｃ(ｎ)、
なる条件を満たし、
１からＮまでのp(ｎ）の和について、底を２としたＭの対数を切り上げた整数と等しくなるように、
１からＮまでのｎについて定めた
ｂ（ｎ）、ｃ（ｎ）、p（ｎ）を用いることを特徴とする探索方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００７−２３３５５４（Ｐ２００７−２３３５５４Ａ）
【公開日】平成１９年９月１３日（２００７．９．１３）
【国際特許分類】
【出願番号】特願２００６−５２５００（Ｐ２００６−５２５００）
【出願日】平成１８年２月２８日（２００６．２．２８）
【出願人】（３０１０２１５３３）独立行政法人産業技術総合研究所 (6,529)
【出願人】（５０６２０９４２２）地方独立行政法人 東京都立産業技術研究センター (134)
【出願人】（５０５３５０４００）株式会社ビッツ (3)
【上記１名の代理人】
【識別番号】１０００８２６６９
【弁理士】
【氏名又は名称】福田 賢三
【公開日】平成１９年９月１３日（２００７．９．１３）
【国際特許分類】
【出願日】平成１８年２月２８日（２００６．２．２８）
【出願人】（３０１０２１５３３）独立行政法人産業技術総合研究所 (6,529)
【出願人】（５０６２０９４２２）地方独立行政法人 東京都立産業技術研究センター (134)
【出願人】（５０５３５０４００）株式会社ビッツ (3)
【上記１名の代理人】
【識別番号】１０００８２６６９
【弁理士】
【氏名又は名称】福田 賢三
[ Back to top ]