(57)【要約】【課題】非連続なマスクへの対応が可能で、かつ、容易にハードウェア化することが可能なデータ列検索用ノード、並びに、位置不定の部分データ列を含むデータ列を検索キーとして取り扱い可能としたデータ列検索用ノード、およびこれを用いるデータ列検索方法並びにデータ列検索処理装置を提供すること。【解決手段】検索キーとなるデータ列の部分列、または検索キーとなるデータ列上の位置情報等、検索キーとなるデータ列の部分列を特定するための情報を持ち（登録データ部１２）、前記データ部分列と検索対象として与えられたデータ列との比較結果（入力データ・登録データ比較部１３）によって分岐先を変更することを特徴とするデータ列検索用ノード（検索ツリー部１１内）、これを用いるデータ列検索方法並びにデータ列検索処理装置。【選択図】      図１
2004187201.tif 000002
【特許請求の範囲】
【請求項１】
検索キーとなるデータ列の部分列、または検索キーとなるデータ列上の位置情報等、検索キーとなるデータ列の部分列を特定するための情報を持ち、前記データ部分列と検索対象として与えられたデータ列との比較結果によって分岐先を変更することを特徴とするデータ列検索用ノード。
【請求項２】
前記分岐先の１つを自ノードを含む検索ツリー上の祖先ノードとし、この祖先ノードに分岐する際には検索位置をずらすことにより、位置不定の部分データ列を含むデータ列を検索キーとして取り扱い可能としたことを特徴とするデータ列検索用ノード。
【請求項３】
請求項１または２に記載のデータ列検索用ノードを用いるデータ列検索方法であって、
前記データ列検索用ノードを多段に組み合わせた検索ツリーないしはツリーの変形を用いることにより、非連続のマスクを有する検索キーおよびデータ列上の検索位置が確定していない検索キーの取り扱いを可能としたことを特徴とするデータ列検索方法。
【請求項４】
請求項１または２に記載のデータ列検索用ノードに加えて、検索対象として与えられたデータ列上の位置情報を持ち、その位置のビット値により分岐先を変更するノードを用い、
これらを多段に組み合わせることにより、非連続のマスクを有する検索キーおよびデータ列上の検索位置が確定していない検索キーの取り扱いにおいて、マスク部分に複数の候補を対応付けることを可能としたことを特徴とするデータ列検索方法。
【請求項５】
請求項１または２に記載のデータ列検索用ノードを用いるデータ列検索処理装置であって、
前記データ列検索用ノードを有する検索ツリーないしはツリーの変形を用いる検索ツリー部と、
この検索ツリー部により指定された登録データを出力する登録データ部と、
入力データと上記登録データ部から出力された登録データとの比較を行うデータ比較部と
を有することを特徴とするデータ列検索処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ列検索用ノード，これを用いるデータ列検索方法並びにデータ列検索処理装置に関し、特に、イーサフレーム，ＩＰパケット，ＨＴＴＰテキストのヘッダ情報等に、特定のアドレス等、所定のデータ列が含まれるか否かを高速に検索可能とするするデータ列検索用ノード，これを用いるデータ列検索方法並びにデータ列検索処理装置に関する。
【０００２】
【従来の技術】
ＩＰパケット等のアドレス検索においては、ハッシュ関数による方法，ＣＡＭを用いる方法，検索ツリーを用いる方法が一般的である（非特許文献１参照）。検索ツリーによる方法は、検索キー長等に対する柔軟性，高速性，経済性の観点から用いられることが多い。検索ツリーを用いる方法において、単純な２分木探索による手法は高速検索が可能であるが、検索ツリーのエントリ追加・削除に関する手間が大きいため、ＰＡＴＲＩＣＩＡ（Ｐｒａｃｔｉｃａｌ  Ａｌｇｏｒｉｔｈｍ  ｔｏ  Ｒｅｔｒｉｅｖｅ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｃｏｄｅ  ｉｎ  Ａｌｐｈａｎｕｍｅｒｉｃ）ツリー（非特許文献２参照）ないしは類似の方法が多く使用される。
【０００３】
ＰＡＴＲＩＣＩＡツリーは、ツリーの各ノードが２つの子ノード、および検索キー上の位置情報を持つツリーで、最も子孫側のノード（リーフ）を検索結果に対応させる。例えば、ＩＰパケットのルーティングに用いる場合、検索キーはＩＰアドレスで、検索結果はＩＰアドレスと次方路の組である。ツリーの各ノードが持つ検索キー上の位置情報は、当該ノードがＩＰアドレスの何ビット目に対応するかの情報となる。簡単化のためにアドレスを１６ビットとした例を、図１３，図１４に示す。
【０００４】
検索は、以下のように行う（図１４）。
（１）最も先祖側のノード（ノード１）を、処理ノードとする。
（２）与えられたアドレスの、処理ノードの位置情報に対応するビットを読み出す（ノード１では２ビット目、ノード２では４ビット目）。
（３）読み出したビットが‘０’ならば子１を、‘１’ならば子２を処理ノードとする。
（４）リーフについたら（５）へ、それ以外は（２）へ進む。
（５）与えられたアドレスと、リーフに登録されたアドレスとが一致したら、方路情報を返す。一致しない場合は、該当エントリなしとする。
【０００５】
例えば、“１１００１１００００１１１００１”は２ビット目が１、４ビット目が‘０’なので、上記の手順から登録データ２のリーフに到達するが、アドレスの全桁が一致しないので、該当なしになる。
ＩＰアドレス等にマスクを用いた場合、上記の手順のみでは対応できないが、一旦リーフに到達した後、ツリーを遡る等の手法により対処可能である。マスクが不連続な場合、ツリーを遡り、再度探索を繰り返す手順がとられるが、この場合Ｒａｄｉｘツリーと呼ばれる（非特許文献３参照）。
【０００６】
前述のＰＡＴＲＩＣＩＡツリーの高速化を目的としては、様々な試みがなされている。特許文献１では、検索処理を並列処理化することにより高速化を図っている。また、特許文献２，特許文献３では、検索ツリーのデータ構造を改良することにより高速化を図っている。これらの技術は、検索の高速化を目的としており、非連続マスクへの対応等、検索対象の拡張を図るものではなかった。
【０００７】
【非特許文献１】
「ＬＡＮスイッチング徹底解説」Ｒｉｃｈ  Ｓｅｉｆｅｒｔ  著、間宮あきら訳、日経ＢＰ社、２００１年発行、ｐ．７８‐８８）
【非特許文献２】
ｈｔｔｐ：／／ｗｗｗ．ｃｓｓｅ．ｍｏｎａｓｈ．ｅｄｕ．ａｕ／〜ｌｌｏｙｄ／ｔｉｌｄｅＡｌｇＤＳ／Ｔｒｅｅ／ＰＡＴＲＩＣＩＡ．ｈｔｍｌ
【非特許文献３】
ｈｔｔｐ：／／ｗｗｗ．ｗｉｄｅ．ａｄ．ｊｐ／ｄｏｃｕｍｅｎｔ／ｒｅｐｏｒｔｓ／ｐｄｆ１９９６／ｏａｒｔ５．ｈｔｍ
【０００８】
【特許文献１】
特開２０００−８３０５４号公報
【特許文献２】
特開２０００−８３０５６号公報
【特許文献３】
特開２０００−１９６６７０号公報
【０００９】
【発明が解決しようとする課題】
アドレス検索において、ＩＰアドレスのみを目的とする場合、連続なマスクに対応できれば十分であるが、ＯＳＩ参照モデルのレイヤ２〜レイヤ７への対応を図る場合、不連続なマスクへの対応は必須である。従って、単純なＰＡＴＲＩＣＩＡツリーは不適であり、Ｒａｄｉｘツリーが用いられる。但し、Ｒａｄｉｘツリーは前述のようにツリーを遡り、再検索を行う手順を含んでいるため、検索に手間がかかり、またハードウェア化が困難であるという問題があった。
【００１０】
上記に加え、レイヤ７（アプリケーションレイヤ）への適用に際しては、検索キーとなるデータ列の位置が不定となる問題がある。例えば、ＨＴＴＰテキストにおいて、各ＨＴＴＰヘッダの形式，名称は規定されているが、出現の有無，順番，データ長については、通常規定されない。このような、位置が不定の部分検索キーに対しては、従来のツリー型検索で取り扱うことは困難であった。
【００１１】
本発明は上記事情に鑑みてなされたものであり、その目的とするところは、従来の技術における上述のような問題を解消し、不連続なマスクへの対応が可能で、かつ、容易にハードウェア化することが可能なデータ列検索用ノード，これを用いるデータ列検索方法並びにデータ列検索処理装置を提供することにある。
【００１２】
また、本発明の他の目的は、位置不定の部分データ列を含むデータ列を検索キーとして取り扱い可能としたデータ列検索用ノード，これを用いるデータ列検索方法並びにデータ列検索処理装置を提供することにある。
【００１３】
【課題を解決するための手段】
上記目的を達成するため、本発明に係るデータ列検索用ノードは、検索キーとなるデータ列の部分列、または検索キーとなるデータ列上の位置情報等、検索キーとなるデータ列の部分列を特定するための情報を持ち、前記データ部分列と検索対象として与えられたデータ列との比較結果によって分岐先を変更することを特徴とする。
【００１４】
また、本発明に係る他のデータ列検索用ノードは、前記分岐先の１つを自ノードを含む検索ツリー上の祖先ノードとし、この祖先ノードに分岐する際には検索位置をずらすことにより、位置不定の部分データ列を含むデータ列を検索キーとして取り扱い可能としたことを特徴とする。
【００１５】
また、本発明に係るデータ列検索方法は、上述のデータ列検索用ノードのいずれかを用いるデータ列検索方法であって、前記データ列検索用ノードを多段に組み合わせた検索ツリーないしはツリーの変形を用いることにより、非連続のマスクを有する検索キーおよびデータ列上の検索位置が確定していない検索キーの取り扱いを可能としたことを特徴とする。
【００１６】
また、本発明に係る他のデータ列検索方法は、上述のデータ列検索用ノードのいずれかに加えて、検索対象として与えられたデータ列上の位置情報を持ち、その位置のビット値により分岐先を変更するノードを用い、これらを多段に組み合わせることにより、非連続のマスクを有する検索キーおよびデータ列上の検索位置が確定していない検索キーの取り扱いにおいて、マスク部分に複数の候補を対応付けることを可能としたことを特徴とする。
【００１７】
さらに、本発明に係るデータ列検索処理装置は、上述のデータ列検索用ノードのいずれかを用いるデータ列検索処理装置であって、前記データ列検索用ノードを有する検索ツリーないしはツリーの変形を用いる検索ツリー部と、この検索ツリー部により指定された登録データを出力する登録データ部と、入力データと上記登録データ部から出力された登録データとの比較を行うデータ比較部とを有することを特徴とする。
【００１８】
より具体的には、本発明においては、例えば、図１に示すようなシステム構成を採用することにより、課題を解決したものである。図１中、１０は検索エンジンを示している。また、１１は検索ツリー部であり、ここには、先に述べたような、後述する本発明の特徴を導き出すノード、更には、従来から用いられているノード（例えば、前記ＰＡＴＲＩＣＩＡツリーのノード）からなる検索ツリーが用いられる。
【００１９】
また、１２は登録データ部であり、ここには、検索キーによる検索結果に対する登録データが格納されている。１３は入力データ・登録データ比較部であり、両者を比較して、次方路等の検索結果を出力する。
なお、本発明における検索ツリーは、複雑な構成が取り得るため、登録データの追加／削除時に検索ツリーの変更点の指示を行うための、検索ツリーデータ生成部１４が設けられている。
【００２０】
上述のように、本発明においては、図１３に示した通常のＰＡＴＲＩＣＩＡツリーのノードの他に、図２に示すマスク処理用ノードを用いる。
図１３に示す通常のＰＡＴＲＩＣＩＡツリーのノードは、各ノードの情報として、２つの子ノードと検索キー上の位置情報を持つ。当該ノードが処理対象になった場合、位置情報に対応する位置のｂｉｔ値を検索対象となるデータ列から読み取り、‘０’の場合は子ノード１へ、‘１’の場合は子ノード２へ分岐する。
【００２１】
これに対し、図２に示す本発明で用いられるマスク処理ノードは、２つの子ノードと、検索キー上の区間を指定する情報（例えば、開始位置と終了位置）と、検索キーとして登録されたデータ列、またはその格納場所の情報を、各ノードに保持する。当該ノードが処理対象となった場合には、登録された区間で登録されたデータ列と検索対象のデータ列とを比較し、一致した場合は子ノード１へ、一致しなかった場合は子ノード２へ分岐する。
【００２２】
図３に、マスクを含むデータ列の検索の場合の検索ツリーの構成例を示す。
また、図４には、マスク処理ノードを位置不定の部分検索キーの処理に用いる場合を示す。データ列の部分が一致しなかった場合には祖先ノードへ戻り、検索位置をずらして再度検索を行う。
図５は、位置不定の部分検索キーを扱う検索ツリーの構成例を示すものである（位置不定の部分検索キーの処理を行う場合には、祖先ノードへの分岐を含むため、正確に言えば「ツリー」構造ではなくなる）。
【００２３】
【作用】
図３の検索ツリーに、例えば、“０１１０１１１１１０１１１００１”のデータ列が加わった場合、以下のように検索が行われる。
・ツリーの最も先祖側のノード（ノード１：このノードは、通常のＰＡＴＲＩＣＩＡツリーのノードである）から検索を開始する。検索対象のデータ列の３ｂｉｔ目が‘１’なので、子ノード２側のノード２へ進む。
【００２４】
・ノード２はマスク処理ノードなので、検索対象データ列の５〜９ｂｉｔ目である、“１１１１１”と、ノードに登録された登録データ２の検索キーの５〜９ｂｉｔ目である“１００１０”とを比較する。
・比較の結果、一致しないので、子ノード２側へ進み、登録データ３を得る。
・検索対象のデータ列と登録データ３の検索キーのマスクされていない部分とを比較する。
・比較の結果、一致するので、検索結果として方路−Ｃを得る。
【００２５】
以上の手順でマスク付きの検索キーの検索を行う。ノード２において、マスクされた部分が登録データ２の検索キーと一致する場合は、登録データ２へ分岐することから、マスクされた検索キーとマスクされない検索キーとがある場合、マスクされない検索キーの方が優先されることがわかる。
【００２６】
図５の検索ツリーに、例えば“０１１００００１００１０１００１”のデータが加わった場合、以下のように検索が行われる。
・ツリーの最も先祖側のノード（ノード１：このノードは、通常のＰＡＴＲＩＣＩＡツリーのノードである）から検索を開始する。検索対象のデータ列の３ｂｉｔ目が‘１’なので、子ノード２側のノード２へ進む。
【００２７】
・ノード２はマスク処理ノードなので、検索対象データ列の５〜９ｂｉｔ目である、“０００１０”と、ノードに登録された登録データ２の検索キーの５〜９ｂｉｔ目である、“１００１０”とを比較する。
・一致しないので、検索位置を所定のｂｉｔ数（この例では１ｂｉｔ。多くの場合１ｂｙｔｅ）だけずらして、祖先ノード側（この例では、自ノードであるノード２）へ進む。
【００２８】
・検索対象データ列の６〜１０ｂｉｔ目である“００１００”と、ノードに登録された登録データ２の検索キーの５〜９ｂｉｔ目である、“１００１０”とを比較する。一致しないので、さらに１ｂｉｔだけずらして自ノードへ進む。
・・・
・検索対象データ列の８〜１２ｂｉｔ目である“１００１０”と、ノードに登録された登録データ２の検索キーの５〜９ｂｉｔ目である、“１００１０”とを比較する。一致するので、子ノード側へ進み、登録データ２を得る。
【００２９】
・検索対象のデータ列と、登録データ２の検索キーの、位置不定部分検索キーの前まで（１〜４ｂｉｔ目）とを比較する。また、位置不定部分検索キー以降を位置ずれを考慮して比較する（１３ｂｉｔ目以降と１０ｂｉｔ目以降）。
・一致するので、検索結果として方路−Ｂを得る。
以上のように、位置不定の部分検索キーを含んだ検索が行われる。また、検索位置をずらして行き、データ列の終端に達した場合は、検索失敗として検索処理を終了する。
【００３０】
【発明の実施の形態】
以下に本発明を用いた場合の検索ツリーの構成および動作例を示す。なお、下記の例では、検索結果として方路データを返しているが、実際の使用においてはこの限りではなく、用途に応じたデータを返せばよい。
【００３１】
〔実施例１〕：マスク部分に複数の検索キーが対応する場合の例
マスク部分に、複数の検索キーが対応する場合の検索ツリーの構成を、図６に示す。
ここに、例えば、“０１１０１１１１１０１１１００１”のデータ列が加わった場合、６ｂｉｔ目が‘１’なので、ノード１からノード３へ進む。ノード３では、５〜９ｂｉｔ目が登録データ３の検索キーと一致しないので、登録データ３が検索ツリーによる処理の結果となる。与えられた文字列と、登録データ３の検索ツリーとを、マスクを考慮して比較すると一致するので、検索結果として、方路−Ｃを返す。
この例は、例えば、複数のＩＰアドレスと、それらに一致しなかった場合のデフォルトの方路を設定するような場合に相当する。
【００３２】
〔実施例２〕：位置不定の部分検索キーを複数種類持つ場合の例
位置不定の部分検索キーを複数持つ場合の検索ツリーの構成を、図７に示す。ここに、例えば、“０１１００１１０１００１１１００１”のデータ列が加わった場合、まず、
・ノード１で６ｂｉｔ目をみて、‘１’なのでノード３へ進む
・５〜９ｂｉｔ目を登録データ２の検索キーと比較し、不一致なので、検索位置を（この例では）１ｂｉｔずらしてノード１へ戻る
・７ｂｉｔ目が‘１’なのでノード３へ進む
【００３３】
・与えられたデータ列の６〜１０ｂｉｔ目と、登録データ２の検索キーの５〜９ｂｉｔ目が一致するので、登録データ２が検索ツリーによる処理の結果となる。
・与えられたデータの１〜５ｂｉｔ目と登録データ２の検索キーの１〜５ｂｉｔ目、および１１〜１７ｂｉｔ目と１０〜１６ｂｉｔ目とを比較し、一致するので方路−Ｂを検索結果として返す。
となる。
この例は、例えば、複数のＨＴＴＰヘッダを検索するような場合に相当するものである。
【００３４】
〔実施例３〕：非連続のマスクの場合の例
非連続のマスクの場合の検索ツリーの構成を、図８に示す。
ノード３では、与えられたデータ列の５〜９ｂｉｔ目が登録データ１の検索キーと一致しない場合に処理が行われる。ノード３のように、検索キーのマスク部分がマスクされない他の検索キーが存在しない場合、マスク処理ノードには検索キーは対応させず、常に子ノード２側に分岐させる。また、検索処理上ノード３は意味を持たないので、省略することも可能である。
【００３５】
このツリーに、例えば、“０１１０１１０１００１１１１０１”のデータ列が加わった場合、
・ノード１で５〜９ｂｉｔ目を見て、一致するのでノード２へ進む。
・ノード２で１２〜１４ｂｉｔ目を見て、一致しないので、登録データ２が検索ツリーによる処理の結果となる。
・与えられたデータと登録データ２の検索キーを比較し、一致するので方路−Ｂを検索結果として返す。
この例は、例えば、ＩＰヘッダにおいて発アドレスと着ポート番号だけを指定し、あとの部分にマスクをかけるような場合に相当する。
【００３６】
〔実施例４〕：マスクが重なる場合の例
マスクが重なる場合の検索ツリーの構成を、図９に示す。本実施例では、登録データ２と登録データ３の検索キーの５〜９ｂｉｔ目のマスクが重なる。
このツリーに、例えば、“０１１０１１０１００１１１１０１”のデータ列が加わった場合、
・ノード１で５〜９ｂｉｔ目を見て、一致しないのでノード３へ進む。
【００３７】
・ノード３で１０〜１１ｂｉｔ目を見て、一致するので登録データ２が検索ツリーによる処理の結果となる。
・与えられたデータと登録データ２の検索キーとを比較し、一致するので方路−Ｂを検索結果として返す。
この例は、例えば、全桁を指定したＩＰアドレス、一部の桁を指定したＩＰアドレス、どちらにも一致しない場合のデフォルト値、を扱うような場合に相当するものである。
【００３８】
〔実施例５〕：非連続のマスクと位置不定の部分検索キーを持つ場合の例
非連続のマスクと位置不定の部分検索キーを持つ場合の検索ツリーの構成を、図１０に示す。
本実施例は、図９の例と図８の例とを組み合わせたもので、特定のＩＰアドレス間のＨＴＴＰ通信でＨＴＴＰヘッダにＡｕｔｈｏｒｉｚａｔｉｏｎヘッダがついているパケットをフィルタリングするような場合に相当する。動作は、実施例４と実施例３の組み合わせになる。なお、図１０はノード２およびノード３の、子ノード２側のノードを共通化し、メモリの節約を図った場合を示しており、ノード５と同じ情報を持つ別のノードを、ノード２の子ノード２としても同様に動作する。
【００３９】
〔実施例６〕：マスクが検索キー全体を覆う場合の例
マスクが検索キー全体を覆う場合の検索ツリーの構成を図１１に示す。登録データ３のマスクは検索キーの全体を覆うため、他に該当する登録データがない場合は、常に検索結果として方路−Ｃを得る。
このツリーに、例えば、“０１１０１０１１１１１１１１１１”のデータ列が加わった場合、
・ノード１で１〜８ｂｉｔ目を見て、一致するのでノード２へ進む。
・ノード２で９〜１６ｂｉｔ目を見て、一致しないので登録データ３が検索ツリーによる処理の結果となる。
【００４０】
・与えられたデータと登録データ３の検索キーとを比較し、一致するので方路−Ｂを検索結果として返す（この場合、マスクが全桁に及んでいるため、必ず一致する）。
となる。
この例は、例えば、発着のＩＰアドレス、着側のみのＩＰアドレス、どちらにも一致しない場合のデフォルト値、を扱うような場合に相当する。
本実施例のような場合、マスク処理ノードでのデータ列比較が検索キーの全長に及ぶため、検索ツリーでの処理後の全桁の比較は省略することが可能である。
【００４１】
〔実施例７〕：マスクの優先順位を考慮する場合の例
図中、上部の登録データ１〜５に基づくツリーの例を、図１２（ａ），（ｂ）に示す。
図１２（ａ）に示す検索ツリー１は、検索キーの１〜９ｂｉｔ目が検索対象データ列と一致するか否かを、１０〜１６ｂｉｔ目に優先して判定する。同図（ｂ）に示す検索ツリー２は、その逆となる。
【００４２】
例えば、“０１１０１１００１０１０１００１”のデータ列は、登録データ１でも登録データ３でも一致する。このデータ列が図１２のツリーに加わった場合、（ａ），（ｂ）双方のツリーで、ノード１→ノード２→ノード６→ノード７と動作するが、得られる結果は、検索ツリー１では登録データ１、検索ツリー２では登録データ３となる。このように、ノードの並べ方によりマスクの優先順位を設定することが可能である。
この例は、例えば、発側および着側ＩＰアドレスを登録し、どちらかを優先する場合などに相当するものである。
【００４３】
なお、上記各実施例はいずれも本発明の一例を示すものであり、本発明はこれらに限定されるべきものではなく、本発明の要旨を逸脱しない範囲内で任意の変更・改良を行ってもよいことはいうまでもない。
【００４４】
【発明の効果】
以上、詳細に説明したように、本発明によれば、非連続なマスクを有し、位置の不定な検索キーを含むデータ列の検索を高速に行うことが可能となるという顕著な効果を奏するものである。
【００４５】
また、本発明によれば、位置不定の部分データ列を含むデータ列を検索キーとして取り扱い可能となるという顕著な効果をも奏するものである。
【図面の簡単な説明】
【図１】本発明に係るデータ列検索システムの概要を説明する図である。
【図２】マスク処理用ノードを説明する図である。
【図３】マスクを含むデータ列の検索を行う場合の検索ツリーの構成例を説明する図である。
【図４】マスク処理のードを位置不定の部分検索キーの処理に用いる場合を説明する図である。
【図５】位置不定の部分検索キーを扱う検索ツリーの構成例を説明する図である。
【図６】マスク部分に複数の検索キーが対応する場合の例（実施例１）を説明する図である。
【図７】位置不定の部分検索キーを複数種類持つ場合の例（実施例２）を説明する図である。
【図８】非連続のマスクの場合の例（実施例３）を説明する図である。
【図９】マスクが重なる場合の例（実施例４）を説明する図である。
【図１０】非連続のマスクと位置不定の部分検索キーを持つ場合の例（実施例５）を説明する図である。
【図１１】マスクが検索キー全体を覆う場合の例（実施例６）を説明する図である。
【図１２】マスクの優先順位を考慮する場合の例（実施例７）を説明する図である。
【図１３】通常のＰＡＴＲＩＣＩＡツリーのノードを説明する図である。
【図１４】ＰＡＴＲＩＣＩＡツリーの例を説明する図である。
【符号の説明】
１０  検索エンジン
１１  検索ツリー部
１２  登録データ部
１３  入力データ・登録データ比較部
１４  検索ツリーデータ生成部
【図１】
2004187201.tif 000003
【図２】
2004187201.tif 000004
【図３】
2004187201.tif 000005
【図４】
2004187201.tif 000006
【図５】
2004187201.tif 000007
【図６】
2004187201.tif 000008
【図７】
2004187201.tif 000009
【図８】
2004187201.tif 000010
【図９】
2004187201.tif 000011
【図１０】
2004187201.tif 000012
【図１１】
2004187201.tif 000013
【図１２】
2004187201.tif 000014
【図１３】
2004187201.tif 000015
【図１４】
2004187201.tif 000016