(57)【要約】  【課題】照合すべきパターンが複数存在するパターン照合の処理の高速化とメモリ消費量の抑制との双方を実現する。  【解決手段】複数のパターンの各々における先頭より所定長のデータである先行パターンを基に定まる値に関連づけて少なくとも先行パターンに後続する部分のデータである後続パターンを記憶手段に格納する格納ステップと、前記対象データにおける照合開始位置より前記所定長に対応する長さのデータである前方データを抽出する抽出ステップＳ３と、前記抽出ステップＳ３で抽出した前方データを基に定まる値に関連づけられた後続パターンが前記記憶手段に格納されている場合にこの後続パターンを記憶手段より読み込む読込ステップＳ４と、前記読込ステップＳ４で読み込んだ後続パターンと前記対象データにおける前記前方データに後続するデータとを比較する比較ステップＳ６と、前記対象データにおける照合開始位置を後方に変位させた上で前記抽出ステップ、前記読込ステップ及び前記比較ステップを再度実行すべく制御する反復ステップＳ５、Ｓ７、Ｓ９、Ｓ２とを実施する。  【選択図】図９
2005025657.tif 000002
【特許請求の範囲】
【請求項１】
複数のパターンのうち少なくとも一つが対象データ中に存在するか否かを判断するパターン照合を実行するための方法であって、
前記パターンにおける先頭より所定長のデータである先行パターンを基に定まる値に関連づけて、少なくともこの先行パターンに後続する部分のデータである後続パターンを記憶手段に格納する格納ステップと、
前記対象データにおける照合開始位置より前記所定長に対応する長さのデータである前方データを抽出する抽出ステップと、
前記抽出ステップで抽出した前方データを基に定まる値に関連づけられた後続パターンが前記記憶手段に格納されている場合に、この後続パターンを記憶手段より読み込む読込ステップと、
前記読込ステップで読み込んだ後続パターンと、前記対象データにおける前記前方データに後続するデータとを比較する比較ステップと、
少なくとも、前記読込ステップにて前方データを基に定まる値に関連づけられた後続パターンが前記記憶手段に格納されていない場合または前記比較ステップにて前記後続パターンと前記前方データに後続するデータとが合致しない場合に、前記対象データにおける照合開始位置を後方に変位させた上で前記抽出ステップ、前記読込ステップ及び前記比較ステップを再度実行すべく制御する反復ステップと
を具備することを特徴とするパターン照合方法。
【請求項２】
前記格納ステップにて、前記先行パターンに後続する後続パターンを前記記憶手段上の所要の記憶領域に格納するとともに、前記先行パターンを基に定まる値で要素を特定可能な配列を前記記憶手段に設定して、その要素として前記後続パターンが格納される記憶領域を指示するポインタを格納し、
前記読込ステップにて、前記抽出ステップで抽出した前方データを基に定まる値で前記配列の要素を参照し、その要素として格納されているポインタにより指示される前記記憶領域に前記後続パターンが格納されている場合に、この後続パターンを読み込む請求項１記載のパターン照合方法。
【請求項３】
前記格納ステップにて、複数のパターンの各々についてその先行パターンをそれぞれ所定のビット長を有し所定の順序が与えられる複数の数値に分割するとともに、これら複数の数値のそれぞれに対応して木構造をなす複数の配列を前記記憶手段に設定するものとし、
前記複数の数値のうち最先の数値に対応し、最先の数値のビット長に応じた要素数を包含してこの数値で要素を特定可能な始段配列を予め前記記憶手段に設定しておき、
前記順序に従い前記複数の数値を一つずつ選出して選出した数値に対応する配列の要素をこの数値で参照するにあたり、その要素として次の順序の数値に対応する配列へのポインタが格納されているときにはこのポインタで指示される配列の要素を前記次の順序の数値で参照する一方、次の順序の数値に対応する配列へのポインタが格納されていないときには次の順序の数値のビット長に応じた要素数を包含してこの数値で要素を特定可能な配列を次の順序の数値に対応する配列として前記記憶手段に設定した上でこの配列へのポインタを前記選出した数値で参照される配列の要素として格納し、
かつ、前記複数の数値のうち最後の数値に対応する配列である終段配列においてこの数値で特定される要素として前記後続パターンが格納される記憶領域を指示するポインタを格納して、
前記読込ステップにて、前記抽出ステップで抽出した前方データを前記所定のビット長を有し前記所定の順序が与えられる複数の数値に分割し、これら複数の数値で前記複数の配列を前記始段配列を起点に探索し、前記終段配列の要素として格納されているポインタにより指示される前記記憶領域に前記後続パターンが格納されている場合にこの後続パターンを読み込む請求項２記載のパターン照合方法。
【請求項４】
前記複数のパターンの各々は、予め設定された一または複数のグループに属しており、
前記格納ステップにて、前記パターンが属しているグループを識別するグループ識別情報を前記後続パターンに付加して、これらグループ識別情報及び後続パターンを前記記憶手段に格納するものとし、
さらに、前記比較ステップにて前記後続パターンと前記前方データに後続するデータとが合致した場合に、この後続パターンに係るグループ識別情報を含む結果情報を出力する出力ステップを具備している請求項１、２又は３記載のパターン照合方法。
【請求項５】
前記複数のパターンの各々は、予め設定された一または複数のグループに属しており、
前記格納ステップにて、前記パターンが属しているグループを識別するグループ識別情報を前記後続パターンに付加して、これらグループ識別情報及び後続パターンを前記記憶手段に格納するものとし、
さらに、前記複数のパターンのうち前記対象データとの照合を行うべきパターンのグループの指定を受け付ける指定ステップを具備して、
前記読込ステップにて、前記指定ステップで指定されたグループを識別するグループ識別情報が付加されている後続パターンのみを前記記憶手段より読み込む請求項１、２、３又は４記載のパターン照合方法。
【請求項６】
請求項１、２、３、４又は５記載のパターン照合方法を実施するために用いられるプログラムであって、コンピュータに、
前記パターンにおける先頭より所定長のデータである先行パターンを基に定まる値に関連づけて、少なくともこの先行パターンに後続する部分のデータである後続パターンを記憶手段に格納する格納ステップと、
前記対象データにおける照合開始位置より前記所定長に対応する長さのデータである前方データを抽出する抽出ステップと、
前記抽出ステップで抽出した前方データを基に定まる値に関連づけられた後続パターンが前記記憶手段に格納されている場合に、この後続パターンを記憶手段より読み込む読込ステップと、
前記読込ステップで読み込んだ後続パターンと、前記対象データにおける前記前方データに後続するデータとを比較する比較ステップと、
少なくとも、前記読込ステップにて前方データを基に定まる値に関連づけられた後続パターンが前記記憶手段に格納されていない場合または前記比較ステップにて前記後続パターンと前記前方データに後続するデータとが合致しない場合に、前記対象データにおける照合開始位置を後方に変位させた上で前記抽出ステップ、前記読込ステップ及び前記比較ステップを再度実行すべく制御する反復ステップと
を実行させるパターン照合プログラム。
【請求項７】
複数のパターンのうち少なくとも一つが対象データ中に存在するか否かを判断するパターン照合を実行するためのものであって、
前記パターンにおける先頭より所定長のデータである先行パターンを基に定まる値に関連づけて、少なくともこの先行パターンに後続する部分のデータである後続パターンを記憶手段に格納する格納部と、
前記対象データにおける照合開始位置より前記所定長に対応する長さのデータである前方データを抽出する抽出部と、
前記抽出部が抽出した前方データを基に定まる値に関連づけられた後続パターンが前記記憶手段に格納されている場合に、この後続パターンを記憶手段より読み込む読込部と、
前記読込部が読み込んだ後続パターンと、前記対象データにおける前記前方データに後続するデータとを比較する比較部と、
少なくとも、前方データを基に定まる値に関連づけられた後続パターンが前記記憶手段に格納されていない場合または前記後続パターンと前記前方データに後続するデータとが合致しない場合に、前記対象データにおける照合開始位置を後方に変位させた上で前記抽出部による前方データの抽出、前記読込部による後続パターンの読み込み及び前記比較部による比較を再度実行させるべく制御する反復部と
を具備することを特徴とするパターン照合装置。
【請求項８】
前記格納部は、前記先行パターンに後続する後続パターンを前記記憶手段上の所要の記憶領域に格納するとともに、前記先行パターンを基に定まる値で要素を特定可能な配列を前記記憶手段に設定して、その要素として前記後続パターンが格納される記憶領域を指示するポインタを格納し、
前記読込部は、前記抽出部が抽出した前方データを基に定まる値で前記配列の要素を参照し、その要素として格納されているポインタにより指示される前記記憶領域に前記後続パターンが格納されている場合に、この後続パターンを読み込む請求項７記載のパターン照合装置。
【請求項９】
前記格納部は、複数のパターンの各々についてその先行パターンをそれぞれ所定のビット長を有し所定の順序が与えられる複数の数値に分割するとともに、これら複数の数値のそれぞれに対応して木構造をなす複数の配列を前記記憶手段に設定するものとし、
前記複数の数値のうち最先の数値に対応し、最先の数値のビット長に応じた要素数を包含してこの数値で要素を特定可能な始段配列を予め前記記憶手段に設定しておき、
前記順序に従い前記複数の数値を一つずつ選出して選出した数値に対応する配列の要素をこの数値で参照するにあたり、その要素として次の順序の数値に対応する配列へのポインタが格納されているときにはこのポインタで指示される配列の要素を前記次の順序の数値で参照する一方、次の順序の数値に対応する配列へのポインタが格納されていないときには次の順序の数値のビット長に応じた要素数を包含してこの数値で要素を特定可能な配列を次の順序の数値に対応する配列として前記記憶手段に設定した上でこの配列へのポインタを前記選出した数値で参照される配列の要素として格納し、
かつ、前記複数の数値のうち最後の数値に対応する配列である終段配列においてこの数値で特定される要素として前記後続パターンが格納される記憶領域を指示するポインタを格納して、
前記読込部は、前記部が抽出した前方データを前記所定のビット長を有し前記所定の順序が与えられる複数の数値に分割し、これら複数の数値で前記複数の配列を前記始段配列を起点に探索し、前記終段配列の要素として格納されているポインタにより指示される前記記憶領域に前記後続パターンが格納されている場合にこの後続パターンを読み込む請求項８記載のパターン照合装置。
【請求項１０】
前記複数のパターンを、各パターンが属している一または複数のグループに関連づけて登録し得るパターン登録部と、
前記比較部による比較の結果前記後続パターンと前記前方データに後続するデータとが合致した場合に、パターン照合が成功した事実に関する情報である結果情報を出力する出力部とをさらに具備しており、
前記格納部は、前記パターンが属しているグループを識別するグループ識別情報を前記後続パターンに付加して、これらグループ識別情報及び後続パターンを前記記憶手段に格納し、
前記出力部は、前記比較部による比較の結果前記後続パターンと前記前方データに後続するデータとが合致した場合に、この後続パターンに係るグループ識別情報を含む結果情報を出力する請求項７、８又は９記載のパターン照合方法。
【請求項１１】
前記複数のパターンを、各パターンが属している一または複数のグループに関連づけて登録し得るパターン登録部と、
前記複数のパターンのうち前記対象データとの照合を行うべきパターンのグループの指定を受け付ける指定部とをさらに具備しており、
前記読込部は、前記指定部を介して指定されたグループを識別するグループ識別情報が付加されている後続パターンのみを前記記憶手段より読み込む請求項７、８、９又は１０記載のパターン照合方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン照合、特に文字列照合の方法に関する。
【背景技術】
【０００２】
対象となるテキスト中に所要の文字列パターン（照合文字列）が出現するか否かを判断する文字列照合のアルゴリズムには種々のものが存在する。例示すると、照合すべき文字列パターンが単一である場合のアルゴリズムとして、Ｋｎｕｔｈ−Ｍｏｒｒｉｓ−Ｐｒａｔｔ（ＫＭＰ）法やＢｏｙｅｒ−Ｍｏｏｒｅ（ＢＭ）法等が知られており、また、照合すべき文字列パターンが複数である場合のアルゴリズムとして、Ａｈｏ−Ｃｏｒａｓｉｃｋ（ＡＣ）法等が知られている（例えば、下記特許文献１を参照）。
【特許文献１】特開平０９−１９８３９８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
近年、大量のテキストデータを効率よく分類できるようにしたいという要求が高まっている。複数の文字列パターンと対象テキストとを照合する文字列照合プログラムは、そのための最も基本的なツールとなる。つまり、文字列照合プログラムに基づく照合処理の高速化が求められていると言える。一方、コンピュータを使用して文字列照合処理を実行するに際し、照合すべき文字列パターンが数多くなると、少なからぬ量のメインメモリが消費されるという問題が生じる。
【０００４】
以上に鑑みて、本発明は、照合すべきパターンが複数存在するパターン照合の処理の高速化とメモリ消費量の抑制との双方を実現可能であるようなパターン照合方法を提供しようとするものである。
【課題を解決するための手段】
【０００５】
本発明に係るパターン照合方法は、例えば、プロセッサ、記憶手段といったハードウェア資源を最低限備えているコンピュータまたは装置によって実行される。通常、プロセッサはレジスタを有し、レジスタに格納した値を処理したり、他の値と比較したり、あるいは外部とのデータ授受を行うためのロード命令やストア命令を実行したりできるものである。記憶手段は、プロセッサが高速にアクセスすることが可能なデバイス、即ちメインメモリやキャッシュメモリ、その他である。
【０００６】
しかして、プロセッサが、まず、照合すべき複数のパターンの各々における先頭より所定長のデータである先行パターンを切り出し、この先行パターンを基に定まる値に関連づけて、先行パターンに後続する部分のデータである後続パターンを少なくとも記憶手段に格納する格納ステップを実施する。前記所定長即ち先行パターンの長さは、プロセッサのレジスタで扱いやすい大きさ（特に、レジスタ長）に設定することが望ましい。例えば、プロセッサが汎用の３２ビットプロセッサであるような場合に、先行パターンの長さを３２ビットとする。そして、先行パターンより一意に定まる値に関連づけて、言い換えるならばプロセッサがこの値を用いて事後的に参照することができるように、複数のパターンの各後続パターンを記憶手段に格納する。なお、共通する先行パターンを有する複数のパターンが存在するとき、この先行パターンを基に定まる単一の値に関連づけて複数の後続パターンを記憶手段に格納することとなる。
【０００７】
照合すべき複数のパターンの後続パターンを記憶手段に格納してしかる後、プロセッサが、パターン照合の対象となる対象データにおける照合開始位置より前記所定長に対応する長さのデータである前方データを抽出する抽出ステップを実施する。先行パターンの長さが３２ビットであるとき、ここで抽出される前方データの長さも３２ビットである。
【０００８】
続いて、プロセッサが、抽出した前方データを基に定まる値に関連づけられて格納されている後続パターンを記憶手段より読み込む読込ステップを実施する。即ち、前方データより一意に定まる値を用いて記憶手段を検索し、この値に関連づけられている後続パターンを読み込む。後続パターンの読み込みに成功したことは、対象データにおける照合開始位置より所定長の前方データと、少なくとも一のパターンの先行パターンとが合致したということを意味する。また、このステップで読み込まれる後続パターンは、複数であることがある。
【０００９】
後続パターンの読み込みに成功した場合、プロセッサが、この後続パターンと、対象データにおける前方データに後続するデータとを比較する比較ステップを実施する。前記読込ステップで複数の後続パターンを読み込んだときには、その各々を前方データに後続するデータと比較する。そして、後続パターンと、前方データに後続するデータとが合致したならば、その後続パターン及び先行パターンよりなるパターンと対象データにおける照合開始位置以降のデータとが合致したということになる。
【００１０】
一方で、読込ステップにて前方データを基に定まる値に関連づけられた後続パターンの読み込みができなかった場合や、比較ステップにて後続パターンと前方データに後続するデータとが合致しなかった場合には、プロセッサが、対象データにおける照合開始位置を後方に変位させた上で、抽出ステップ、読込ステップ及び比較ステップを再度実行すべく制御する反復ステップを実施する。但し、比較ステップにて後続パターンと前方データに後続するデータとが一致した場合においても、対象データにおける照合開始位置を後方に変位させて抽出ステップ、読込ステップ及び比較ステップをさらに実行してよい。
【００１１】
また、通常、比較ステップにて後続パターンと前方データに後続するデータとが合致した場合には、プロセッサが、パターン照合が成功した事実に関する情報である結果情報を構成しこれを出力させる出力ステップを実施する。結果情報とは、照合成功の事実を告知するための情報であり、例えば、照合に成功したパターンまたはその識別子、パターン照合が成功した時点での対象データにおける照合開始位置やその周囲のデータ、等の情報を含む。但し、結果情報が単なるフラグの如きものであることを妨げない。結果情報の出力とは、記憶手段や各種補助記憶デバイスへの書き込み、通信インタフェースや電気通信回線を介した外部への発信、ディスプレイの画面への表示、プリントアウトその他を包括する概念である。因みに、当該パターン照合方法を実行するためのプログラムが他のプログラムと協働する、あるいはこのプログラムが大きなプログラムの一部として機能するモジュールプログラムであるような場合に、他のプログラムに照合結果を提供するべく結果情報を記憶手段または補助記憶デバイスの所要の記憶領域に書き込むという態様で結果情報の出力を行うことがある。
【００１２】
本発明に係るパターン照合方法の特長として、第一に、共通の先行パターンを有する複数のパターンについて、それらの後続パターンを先行パターンを基に定まる単一の値に関連づけて記憶手段に格納するようにしたので、共通する先行パターン部分を重複して記憶手段に格納せずともよくなり、記憶手段上の記憶領域の消費量を抑制することが可能となる。第二に、先行パターン、前方データの長さをプロセッサのレジスタで取り扱いやすいレジスタ長以下の大きさに設定しておくことで、前方データの抽出及び前方データを基に定まる値による記憶手段の参照の処理を高速化できる。第三に、対象データにおける照合開始位置以降のデータを複数のパターンの各々と照合するに際し、まず所定長の前方データと先行パターンとを照合することとなり、前方データと先行パターンとが合致しないことが判明すれば速やかに照合開始位置の後方への変位、照合処理の再試行に移ることができる。即ち、後続パターンの照合を省略することができる。しかも、共通の先行パターンを有する複数のパターンが照合すべきものとしてあたえられているとき、その先行パターンが前方データと合致しなければこれら複数のパターンの全てが照合開始位置以降のデータとは合致しないものであるということが即座に判明する。第四に、前方データを基に定まる値で記憶手段を参照し、この値によって特定できる記憶領域に格納されているであろう後続パターンを読み込むという処理を通じて先行パターンと前方データとの比較が行われる、いわば先行パターンの照合と後続パターンのロードとを同一の処理としているため、パターン照合の一層の高速化に資する。上記の特長により、本発明に係る方法は、照合すべきパターンが多数存在するパターン照合を高速に実行でき、かつ、そのメモリ消費量を抑制し得るものとなる。
【発明の効果】
【００１３】
以上に詳述した本発明によれば、照合すべきパターンが複数存在するパターン照合の処理の高速化とメモリ消費量の抑制との双方を実現可能である。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施の形態を、図面を参照して説明する。本実施形態におけるパターン照合装置は、コンピュータ１に所定のプログラムをインストールすることで構成されるものである。このコンピュータ１は、例えば、図１に示すように、プロセッサ１ａ、記憶手段たるメインメモリ１ｂ、ハードディスクドライブに代表される補助記憶デバイス１ｃ、ディスプレイに情報を表示させるための表示制御デバイス１ｄ、ユーザによる操作入力を受け付ける入力デバイス１ｅ等のハードウェア資源が、コントローラ１ｆ（即ち、いわゆるシステムコントローラ、Ｉ／Ｏコントローラ等）により制御され連携して動作するものである。表示制御装置１ｄは、プロセッサ１ａより受けた描画指示をもとに表示させるべき画像を生成してディスプレイに向けて送出する機能を有するビデオチップ（あるいは、グラフィクスチップ）、画像データ等を一時的に格納しておく役割を担うビデオメモリ（Ｖｉｄｅｏ  ＲＡＭ）等の既知のデバイスを用いて構成できる。入力デバイス１ｅには、キーボード、マウス、トラックパッド、タッチパネルその他が含まれる。
【００１５】
通常、プロセッサ１ａによって実行されるべきプログラムが補助記憶デバイス１ｃに格納されており、プログラムの実行の際には補助記憶デバイス１ｃからメインメモリ１ｂに読み込まれ、プロセッサ１ａによって解読される。そして、該プログラムに従い上記のハードウェア資源を作動して、少なくとも、図２に示す格納部１１、抽出部１２、読込部１３、比較部１４、反復部１５としての機能を発揮するようにしている。
【００１６】
格納部１１は、本実施形態のパターン照合方法における格納ステップを司り、対象データと照合すべきものとして与えられた複数のパターンの各々を、先頭より所定長の先行パターンと、先行パターンに後続する後続パターンとに切り分け、そのうちの少なくとも後続パターンをメインメモリ１ｂに格納する。このとき、各後続パターンを、その後続パターンの前方に連なる先行パターンを基に定まる値に関連づけて格納する。プロセッサ１ａがプログラムに基づき実施する格納ステップは、パターン照合実行のための下準備にあたる。
【００１７】
ここで、格納部１１が実行する、あるいはプロセッサ１ａがプログラムに基づいて実行する格納ステップの処理の内容に関して詳述する。本実施形態では、対象データとしてテキストデータ、照合パターンとして文字列を想定している。与えられるパターンは、通常、図１に示すパターン登録部１７に予め登録されている。パターン登録部１７は、メインメモリ１ｂまたは補助記憶デバイス１ｃの所要の記憶領域を利用して構成され、登録された複数のパターンを記憶している。加えて、複数のパターンをグループ分けして登録しておくことが可能である。このとき、複数のパターンの各々が、一または複数のグループに属することとなる。従って、複数のパターンの各々は、その属しているグループを識別可能な態様でパターン登録部１７に登録される。例えば、図３に示すように、個々のパターンを複数グループに分類した形で（特に、各グループ毎に別個のデータファイルを構成し、それぞれにパターンたる照合文字列を列挙して記述した形で）登録しておくことができる。この図示例では、例えば、「社外秘」、「機密」、等のパターンがグループ（Ｐ）に属するものとして登録され、「社外活動」、「特許」、等のパターンがグループ（Ｒ）に属するものとして登録されている。また、図４に示すようなデータ構造で個々のパターンを登録しておくことも可能である。「山田太郎」、「木田次郎」、等のパターンは少なくともグループ（Ｉ）に属し、「山田太郎」、「８４０１２」、等のパターンは少なくともグループ（Ｘ）に属する。この図示例では、一のパターンにつき複数（図示例では、２つ）のグループ識別が付与されている。即ち、「山田太郎」というパターンは、グループ（Ｘ）に属すると同時にグループ（Ｉ）にも属している。
【００１８】
格納ステップにおいて、複数のパターンをメインメモリ１ｂに格納するにあたり、パターン登録部１７よりパターンを一つずつ読み出し、読み出したパターンより先行パターンと後続パターンとを得る。先行パターンの長さは、プロセッサ１ａのレジスタ長に対応させる。本実施形態では、プロセッサ１ａとして３２ビットプロセッサを想定しており、先行パターンを３２ビット長とする。１文字を２バイトで表現する一般的な日本語文字コードでパターンが表現されている場合には、先頭の２文字が先行パターンとなり、残りが後続パターンとなる。例えば、「社外秘」というパターンからは、「社外」という先行パターンと「秘」という後続パターンとが得られる。なお、パターン自体の長さが先行パターンの長さに一致するときの後続パターンは、例えばヌル文字等のパターンの終端を表す符号とする。しかして、図５及び図６に例示するように、後続パターンをメインメモリ１ｂ上の所要の記憶領域ＭＲに格納する。このとき、後続パターンに、パターンが属しているグループを識別するグループ識別情報を付加し、その上で後続パターン及びグループ識別情報をメインメモリ１ｂ上の記憶領域ＭＲに格納することができる。並びに、先行パターンを基に定まる値で要素を特定可能な配列をメインメモリ１ｂに設定して、その要素として後続パターンが格納される記憶領域ＭＲを指示するポインタを格納する。言い換えるならば、先行パターンより一意に定まる値を添字として要素を参照することができるポインタ配列をメインメモリ１ｂ上に確保する。
【００１９】
ここに言う配列についてより具体的に述べる。先行パターンを３２ビット長とすると、この先行パターンのとり得るバリエーションの数は２32である。これだけの要素数を有するポインタ配列をそのままメインメモリ１ｂ上に確保しようとすれば、莫大なメモリ空間を消費することは避けられない。従って、メインメモリ１ｂの消費量を抑制するための手法として、先行パターンをそれぞれ所定のビット長を有し所定の順序が与えられる複数の数値に分割するものとし、そのうちの最先の数値に対応する始段配列Ａ１のみをまずメインメモリ１ｂに設定する。本実施形態では、３２ビット長の先行パターンを、それぞれ８ビットの４つの数値に分割するものとする。例えば、先行パターンが「社外」であり、このパターンがシフトＪＩＳコードで表現されるとき、先行パターンより８Ｅｈ、Ｄ０ｈ、８Ａｈ、４Ｆｈ（それぞれ、１６進数表記）という４つの値が得られる。勿論、シフトＪＩＳコードに基づいた数値を得るのでなく、ＥＵＣコードやＵＣＳ２コード（Ｕｎｉｃｏｄｅ）等に基づいた数値を得ることもできる。個々の数値は、やはりプロセッサ１ａで扱いやすい大きさとすることが望ましい。ここでは８ビット長としているが、８ビット長には限定されず、例えばこれが１６ビット長であっても構わない。加えて、先行パターンを４つの数値に分割するとは限られない。先行パターンを均一のビット長の値に分割するとも限られない。始段配列Ａ１は、最先の数値のビット長に応じた要素数を包含し、この数値で要素を特定可能な（あるいは、最先の数値を添字として要素を参照し得る）１次元配列である。最先の数値を８ビット長とすれば、これに応じた２8の要素数を有する始段配列Ａ１がメインメモリ１ｂ上に確保されることとなる。始段配列Ａ１は、複数のパターンについてそれらの後続パターンをメインメモリ１ｂに格納する処理に先んじて設定しておくことが必須である。また、始段配列Ａ１は単一である。
【００２０】
次に、先行パターンより得た最先の数値で特定される始段配列Ａ１の要素を参照し、この最先の数値に次ぐ２番目の数値に対応する２段目の配列Ａ２を指示するポインタが格納されていない場合、即ち、この最先の数値に次ぐ２番目の数値に対応する配列Ａ２が未だメインメモリ１ｂに設定されていない場合、２番目の数値に対応する配列Ａ２をメインメモリ１ｂに設定するとともに、設定した配列Ａ２を指示するポインタを始段配列Ａ１における前記最先の数値で特定される要素として格納する。ここで設定すべき２番目の数値に対応する配列Ａ２は、先行パターンを複数の数値に分割したときの２番目の数値のビット長に応じた要素数を有し、この２番目の数値で要素を特定可能な配列である。一方で、先行パターンより得た最先の数値で特定される始段配列Ａ１の要素として２段目の配列Ａ２を指示するポインタが格納されている場合、即ち、２段目の配列Ａ２が既にメインメモリ１ｂに設定されている場合には、新たな配列の確保は行わない。上記例に当てはめると、最先の数値が８Ｅｈであり、始段配列Ａ１における８Ｅｈ番目の要素を参照して、最先の数値８Ｅｈに次ぐ２番目の数値に対応する配列Ａ２へのポインタが格納されていない場合には２8の要素数を有する１次元配列Ａ２を新たにメインメモリ１ｂに設定し、かつ設定した配列Ａ２を指示するポインタを始段配列Ａ１の８Ｅｈ番目の要素として格納する。因みに、２段目の配列Ａ２は、最大で始段配列Ａ１の要素数と同じ数だけ設定され得るが、２段目の配列Ａ２が最大数まで設定される可能性は低い。
【００２１】
続いて、先行パターンより得た複数の数値のうち２番目の数値に対応する配列Ａ２を参照する。即ち、始段配列Ａ１において最先の数値で参照できる要素として格納されているポインタによって指示される２段目の配列Ａ２を参照する。この２段目の配列Ａ２において、先行パターンより得た２番目の数値で参照できる要素として、この２番目の数値に次ぐ３番目の数値に対応する３段目の配列Ａ３を指示するポインタが格納されていない場合、即ち、該当の配列Ａ３が未だメインメモリ１ｂに設定されていない場合、３番目の数値に対応する配列Ａ３を設定するとともに、設定した配列Ａ３を指示するポインタを現在参照している２段目の配列Ａ２における前記２番目の数値で特定される要素として格納する。ここで設定すべき３番目の数値に対応する配列Ａ３もやはり、３番目の数値のビット長に応じた要素数を有し、この３番目の数値で要素を特定可能なものである。一方で、３段目の配列Ａ３を指示するポインタが格納されている場合、即ち、３段目の配列が既にメインメモリ１ｂに設定されている場合には、新たな配列の確保は行わない。上記例に当てはめると、最先の数値８Ｅｈに次ぐ２番目の数値に対応する２段目Ａ２の配列において、Ｄ０ｈ番目の要素を参照して、数値８Ｅｈ及び数値Ｄ０ｈに次ぐ３番目の数値に対応する配列Ａ３へのポインタが格納されていない場合には２8の要素数を有する１次元配列Ａ３を新たにメインメモリ１ｂに設定し、かつ設定した配列Ａ３を指示するポインタを現在参照している２段目の配列Ａ２のＤ０ｈ番目の要素として格納する。因みに、３段目の配列Ａ３は、最大で始段配列Ａ１の要素数と２段目の配列Ａ２の要素数との積と同じ数だけ設定され得るが、３段目の配列Ａ３が最大数まで設定される可能性は極めて低い。
【００２２】
さらに、３番目の数値で３段目の配列Ａ３の要素を参照して、必要な場合には４段目の配列Ａ４を新たに設定する処理を行う。この処理の手順は上記と同様であるため、説明は割愛する。総じて言えば、格納部１１が、所定の順序が与えられた複数の数値をその順序に従い一つずつ選出し、選出した数値に対応する配列の要素をこの数値で参照するにあたり、その要素として次の順序の数値に対応する配列へのポインタが格納されているときにはこのポインタで指示される配列の要素を前記次の順序の数値で参照する一方、次の順序の数値に対応する配列へのポインタが格納されていないときには次の順序の数値のビット長に応じた要素数を包含してこの数値で要素を特定可能な配列を次の順序の数値に対応する配列としてメインメモリ１ｂに設定した上でこの配列へのポインタを前記選出した数値で参照される配列の要素として格納する処理を実行する。この処理は、先行パターンより得られる複数の数値のうちの最後の数値に対応する配列である終段配列Ａ４がメインメモリ１ｂ上に確保されるまで続行される。
【００２３】
終段配列即ち本実施形態における４段目の配列Ａ４における、最後の数値である４番目の数値で参照される要素には、後続パターンを格納すべきメインメモリ１ｂ上の記憶領域ＭＲを指示するためのポインタを格納する。このポインタで指示される記憶領域ＭＲに後続パターンを格納することで、あるパターンについてその後続パターンを先行パターンより定まる値に関連づけてメインメモリ１ｂに格納する処理が完了する。以上の手順を、複数のパターンについて反復的に実行する。その結果、図５及び図６に例示するように、先行パターンより得られる複数の数値のそれぞれに対応して設定された複数の配列Ａ１、Ａ２、Ａ３、Ａ４が節（ノード）となった木構造が構成される。この木構造の根は始段配列Ａ１である。そして、終段配列Ａ４に格納されたポインタによってリンクしている複数の（後続パターンを格納すべき）記憶領域ＭＲが木構造の葉となる。この木構造において、例えば、パターン「社外秘」における後続パターン「秘」が格納されているメインメモリ１ｂ上の記憶領域ＭＲを参照したいとき、先行パターン「社外」より４つの数値８Ｅｈ、Ｄ０ｈ、８Ａｈ、４Ｆｈを得、これらの数値によって始段配列Ａ１を起点として木構造を探索すればよい。すると、最後の数値の一つ前までの（３つの）数値によって特定されるある終段配列Ａ４に至り、この終段配列Ａ４における４Ｆｈ番目の要素を参照することで先行パターン「社外」に後続する後続パターンを格納しているある記憶領域ＭＲへのポインタを得ることができ、後続パターンを読むことが可能となる。つまり、「社外秘」、「社外活動」のように共通する先行パターンを有する複数のパターンが存在するとき、「秘」、「活動」といった複数の後続パターンが一の記憶領域ＭＲに格納されることとなる。ある記憶領域ＭＲにおいて複数の後続パターンを格納するデータ構造は特に限定されないが、例えば、図６に示しているように、複数の後続パターンをポインタでリンクさせたリスト構造とすることができる。このとき、終段配列Ｍ４に格納されているポインタは、後続パターンを要素とするリスト構造の先頭を指示するポインタとなる。
【００２４】
抽出部１２は、本実施形態のパターン照合方法における抽出ステップを司り、パターン照合の対象である対象データにおける照合開始位置より、前記先行パターンと同じ長さのデータである前方データを抽出する。与えられる対象データは、通常、メインメモリ１ｂまたは補助記憶デバイス１ｃの所要の記憶涼気に予め格納されている。プロセッサ１ａは、プログラムに基づき、ある照合開始位置より所定長の前方データを対象データが格納されているメインメモリ１ｂまたは補助記憶デバイス１ｃより読み出すという態様で抽出ステップを実施する。本実施形態では、先行パターンを３２ビット長としており、抽出ステップで抽出する前方データの長さも３２ビットである。なお、後述するが、対象データにおける照合開始位置は当初は対象データの先頭にあり、パターン照合の進行に伴い後方に変位する。
【００２５】
読込部１３は、本実施形態のパターン照合方法における読込ステップを司り、抽出ステップで抽出した前方データを基に定まる値に関連づけられた後続パターンをメインメモリ１ｂより読み込む。先に実施された格納ステップにより、個々のパターンにおける後続パターンがメインメモリ１ｂ上の所要の記憶領域ＭＲに格納されるとともに、この記憶領域ＭＲを指定するポインタが、先行パターンを基に定まる値で要素を特定可能な配列Ａ１、Ａ２、Ａ３、Ａ４に格納されている。よって、当該読込ステップでは、抽出ステップで抽出した前方データを基に定まる値で前記配列Ａ１、Ａ２、Ａ３、Ａ４の要素を参照し、その要素として格納されているポインタにより指示された記憶領域ＭＲより後続パターンを読み込む処理を実行する。
【００２６】
ここで、読込部１３が実行する、あるいはプロセッサ１ａがプログラムに基づいて実行する読込ステップの処理の内容に関して詳述する。既に述べたように、上記の格納ステップの結果、先行パターンより得られる複数の数値のそれぞれに対応して設定された複数の配列Ａ１、Ａ２、Ａ３、Ａ４が節となった論理的な木構造がメインメモリ１ｂを利用して構成されている。始段配列Ａ１がこの木構造の根であり、終段配列Ａ４に格納されたポインタにより指示される後続パターンが格納された記憶領域ＭＲが木構造の葉である。抽出ステップで抽出した前方データに合致する先行パターンに後続する後続パターンを前記記憶領域ＭＲより読み込むためには、この前方データを先行データと同様にして複数の数値に分割し、これら複数の数値で木構造をなす複数の配列Ａ１、Ａ２、Ａ３、Ａ４を始段配列Ａ１を起点に探索し、終段配列Ａ４に要素として格納されたポインタにより指示される記憶領域ＭＲを参照して、この記憶領域ＭＲより後続パターンを読み込む。例えば、図７に示すような文書の内容を規定するテキストデータが対象データとされ、図８（ａ）に示すように対象データにおける照合開始位置より３２ビット長のデータが文字列「社外」を表すものであるとき、この文字列「社外」を前方データとして抽出し、抽出した前方データを８ビット長の４つの数値、即ち８Ｅｈ、Ｄ０ｈ、８Ａｈ、４Ｆｈに分割する。しかる後、これらの数値によって始段配列Ａ１を起点として木構造を探索すると、最後の数値の一つ前までの（３つの）数値によって特定されるある終段配列Ａ４に至り、この終段配列Ａ４における４Ｆｈ番目の要素を参照することで先行パターン「社外」に後続する後続パターンを格納しているある記憶領域ＭＲへのポインタを得ることができる。最終的に、このポインタにより指示される記憶領域ＭＲに格納されている一または複数の後続パターンを読み込むことができる。しかしながら、前方データより得られた複数の数値で木構造を探索しても終段配列Ａ４に至らない、または後続パターンが格納された記憶領域ＭＲを指示するポインタを得られないこともある。このように、後続パターンの読み込みが成功しなかったときには、照合開始位置を先頭とする前方データと合致する先行パターンを有する照合パターンが存在していないものと判断することができる。因みに、図６に例示しているように、後続パターンにグループ識別情報が付加されてこれら後続パターン及びグループ識別情報がメインメモリ１ｂ上の記憶領域ＭＲに格納されている場合、読込ステップにて、後続パターンのみならずグループ識別情報をも読み込むことができる。あるいは、読込ステップにて、あるグループ識別子が付加されている後続パターンのみを選択的に読み込むことができる。
【００２７】
比較部１４は、本実施形態のパターン照合方法における比較ステップを司り、読込ステップにて後続パターンの読み込みに成功した場合に、読み込んだ後続パターンと、対象データにおける前方データに後続する部分のデータとの比較を行う。即ち、プロセッサ１ａが、プログラムに基づき、読込ステップで読み込んだ後続パターンの各々を対象データ中の前方データ以降のデータと照らし合わせ、合致するか否かを一つ一つ調べる。上記例に当てはめると、対象データにおける照合開始位置より３２ビット長の前方データが文字列「社外」を表すものである場合、この前方データに合致する先行パターン文字列「社外」を有する一または複数のパターン、即ち「社外秘」、「社外活動」等における後続パターン「秘」、「活動」等が読込ステップで読み込まれる。しかして、比較ステップにおいては、これら「秘」、「活動」等の後続パターンの各々を、対象データにおける照合開始位置から３２ビット分離れた位置より後続するデータと照らし合わせる。そして、後続パターンの少なくとも一つが合致したならば、この後続パターンを有する照合パターンが、対象データにおける照合開始位置以降のデータに合致するものであるという判断を下すことができる。一方で、何れの後続パターンも合致しなかったならば、「社外」という先行パターンを有する何れの照合パターンも対象データにおける照合開始位置以降のデータには合致しないと判断できる。因みに、後続パターンがヌル文字等のコードである場合には、上述したように、先行パターンの長さに等しく後続パターンが本来存在していない照合パターンである。即ち、後続パターンがヌル文字等である場合、前方データに後続する部分のデータとの比較を行うまでもなく、対象データにおける照合開始位置以降のデータと照合パターンとが一致することが明らかとなる。
【００２８】
比較ステップにて前記後続パターンと前記前方データに後続するデータとが合致したとき即ちパターン照合が成功したときには、出力部１６が、パターン照合が成功した事実に関する情報である結果情報を出力する出力ステップを実行する。特に本実施形態では、読込ステップにて、後続パターンとともに当該後続パターンに付加されているグループ識別情報をも読み込むことができる。このことを利用すれば、比較ステップにおける比較の結果前方データに後続するデータと合致した後続パターンに係るグループ、即ち、対象データにおける照合開始位置以降のデータに合致した照合パターンが属しているグループを知得することが可能である。よって、出力ステップにおいて、対象データにおける照合開始位置以降のデータと合致したパターンが属しているグループを識別するグループ識別情報を含む結果情報を出力するものとすることができる。なお、出力部１６の具体的構成は、結果情報の出力の態様に応じたものとなる。結果情報をディスプレイの画面に表示するという態様で出力する場合、プロセッサ１ａが、プログラムに基づき、結果情報を構成するとともに表示制御デバイス１ｄの機能を利用して画面への表示を実行する。結果情報を印刷するという態様で出力する場合には、プリンタ（図示せず）により結果情報の印刷出力を行う。外部のコンピュータ等へ向けて送信するという態様で結果情報を出力する場合には、電気通信回線を経由してデータの授受を行うための通信デバイス（図示せず）の機能を利用するものとなる。また、結果情報をメインメモリ１ｂまたは補助記憶デバイス１ｃの所要の記憶領域に書き込むという態様で出力する場合には、プロセッサ１ａが、プログラムに基づき、メインメモリ１ｂまたは補助記憶デバイス１ｃへ結果情報の書き込みを行う。但し、結果情報に、照合に成功したパターンが属するグループを識別するグループ識別情報が含まれているとは限られない。
【００２９】
反復部１５は、本実施形態のパターン照合方法における反復ステップを司り、少なくとも、読込ステップにて前方データを基に定まる値に関連づけられた後続パターンがメインメモリ１ｂに格納されておらずその読み込みに失敗した場合、または、比較ステップにて後続パターンと前方データに後続するデータとが合致しなかった場合に、対象データにおける照合開始位置を後方に変位させた上で上記の抽出ステップ、読込ステップ及び比較ステップを再度実行させるべく制御する。照合開始位置を変位させる量は、対象データの最小単位のデータ長に対応させることが望ましい。既に述べたように、本実施形態では、対象データとしてテキストデータを想定しており、その最小単位は言うまでもなく文字である。従って、プロセッサ１ａは、プログラムに基づき、図８（ｂ）に示すように、最小単位である一文字分のデータ長、例えば１６ビット（ＡＳＣＩＩ文字では、８ビット）分だけ照合開始位置を後方に変位させた上で、抽出ステップを再び実施するための制御を行う。
【００３０】
なお、照合すべき複数のパターンがグループ分けされているとき、そのうちの一部のグループのみを選択的に指定し、指定したグループに属している照合パターンのみを対象データと照合できるようにすることも好ましい。本実施形態におけるパターン照合装置は、対象データとの照合を行うべきパターンの指定を受け付ける指定部１８をも備えている。指定部１８は、本実施形態のパターン照合方法における指定ステップを司り、入力デバイス１ｅを介してユーザによるグループの指定を直接受け付けるか、あるいは予めメインメモリ１ｂまたは補助記憶デバイス１ｃの所要の記憶領域に格納された設定データを読み込み、この設定情報に記述されている指定グループに関する情報を参照するという態様で、グループの指定の受け付けを行う。即ち、プロセッサ１ａが、プログラムに基づき、指定されたグループを識別するグループ識別情報を、入力デバイス１ｅを介して受け付けるか、メインメモリ１ｂまたは補助記憶デバイス１ｃに格納されている設定データより読み取る。なお、指定ステップでは、複数のグループの指定を受け付けることが可能であり、かつ、複数のグループの何れにも属する照合パターンのみを対象データと照合するものとするいわゆるＡＮＤ指定、または、複数のグループの何れかに属する照合パターンを対象データと照合するものとするいわゆるＯＲ指定の受け付けが可能である。なお、指定部１８はパターン照合装置に必須の要素ではなく、指定ステップは必ず実行されるとは限られない。
【００３１】
そして、グループの指定を受け付けた場合に、読込ステップでは、指定されたグループを識別するグループ識別情報が付加されている後続パターンのみをメインメモリ１ｂより読み込み、比較ステップでは、この読み込んだ後続パターンを対象データにおける前方データに後続するデータと比較する。
【００３２】
以上に述べたパターン照合方法の手順をまとめると、図９に示すフローチャートのようになる。但し、格納ステップはパターン照合のための下準備であることから、図９のフローチャート上には記載していない。順を追って説明すると、ステップＳ１で、パターン照合対象データと照合すべきパターンのグループの指定を受け付ける（指定ステップに該当）。ステップＳ２では、対象データにおける照合開始位置の設定を行う。パターン照合開始時点では、通常、照合開始位置は対象データの先頭である。続いて、ステップＳ３で、設定した照合開始位置より所定長のデータを前方データとして抽出し（抽出ステップに該当）、ステップＳ４で、前方データを基に定まる値に関連する後続パターンの読み込みを試みる（読込ステップに該当）。前方データを基に定まる値に関連づけられている後続パターンの読み込みに成功した場合、ステップＳ６で、読み込んだ各後続パターンを対象データにおける前方データ以降のデータと比較する（比較ステップに該当）。その結果、少なくとも一の後続パターンが前方データ以降のデータに合致した場合には、ステップＳ８で、パターン照合成功の事実に関する結果情報を出力する（出力ステップに該当）。一方で、後続パターンの読み込みに失敗した場合（ステップＳ５）、前方データ以降のデータに合致する後続パターンが存在しなかった場合（ステップＳ７）、または対象データ中の照合開始位置以降のデータとある照合パターンとが合致したにもかかわらずパターン照合を終了せずにさらに続行する場合（ステップＳ９）場合には、上記のステップＳ２以降を反復する。このときのステップＳ２では、対象データにおける照合開始位置を、直前の試行におけるそれよりも（対象データの最小単位のデータ長だけ）後方に変位させた位置に設定する。つまり、図９のフローチャートにおけるステップＳ５、ステップＳ７、ステップＳ９及びステップＳ２が反復ステップに該当する。
【００３３】
本実施形態によれば、複数のパターンのうち少なくとも一つが対象データ中に存在するか否かを判断するパターン照合を実行するためのパターン照合方法を、前記パターンにおける先頭より所定長のデータである先行パターンを基に定まる値に関連づけて、少なくともこの先行パターンに後続する部分のデータである後続パターンをメインメモリ１ｂに格納する格納ステップと、前記対象データにおける照合開始位置より前記所定長に対応する長さのデータである前方データを抽出する抽出ステップと、前記抽出ステップで抽出した前方データを基に定まる値に関連づけられた後続パターンが前記メインメモリ１ｂに格納されている場合に、この後続パターンをメインメモリ１ｂより読み込む読込ステップと、前記読込ステップで読み込んだ後続パターンと、前記対象データにおける前記前方データに後続するデータとを比較する比較ステップと、少なくとも、前記読込ステップにて前方データを基に定まる値に関連づけられた後続パターンが前記メインメモリ１ｂに格納されていない場合または前記比較ステップにて前記後続パターンと前記前方データに後続するデータとが合致しない場合に、前記対象データにおける照合開始位置を後方に変位させた上で前記抽出ステップ、前記読込ステップ及び前記比較ステップを再度実行すべく制御する反復ステップとを具備するものとしたため、照合すべきパターンが多数存在するパターン照合を高速に実行でき、かつ、メインメモリ１ｂの消費量を抑制し得る。
【００３４】
前記格納ステップにて、前記先行パターンに後続する後続パターンを前記メインメモリ１ｂ上の所要の記憶領域ＭＲに格納するとともに、前記先行パターンを基に定まる値で要素を特定可能な配列を前記メインメモリ１ｂに設定して、その要素として前記後続パターンが格納される記憶領域ＭＲを指示するポインタを格納し、前記読込ステップにて、前記抽出ステップで抽出した前方データを基に定まる値で前記配列の要素を参照し、その要素として格納されているポインタにより指示される前記記憶領域ＭＲに前記後続パターンが格納されている場合に、この後続パターンを読み込むものとしたため、先行パターンが共通し後続パターンが相異する複数のパターンについて、メモリ消費量を節約しつつ好適にメインメモリ１ｂへの格納を行うことができる。加えて、読込ステップにて、前方データと合致する先行パターンに後続する後続パターンを速やかに読み込むことが可能となる。
【００３５】
さらに、前記格納ステップにて、複数のパターンの各々についてその先行パターンをそれぞれ所定のビット長を有し所定の順序が与えられる複数の数値に分割するとともに、これら複数の数値のそれぞれに対応して木構造をなす複数の配列Ａ１、Ａ２、Ａ３、Ａ４を前記メインメモリ１ｂに設定するものとし、前記複数の数値のうち最先の数値に対応し、最先の数値のビット長に応じた要素数を包含してこの数値で要素を特定可能な始段配列Ａ１を予め前記メインメモリ１ｂに設定しておき、前記順序に従い前記複数の数値を一つずつ選出して選出した数値に対応する配列の要素をこの数値で参照するにあたり、その要素として次の順序の数値に対応する配列へのポインタが格納されているときにはこのポインタで指示される配列の要素を前記次の順序の数値で参照する一方、次の順序の数値に対応する配列へのポインタが格納されていないときには次の順序の数値のビット長に応じた要素数を包含してこの数値で要素を特定可能な配列を次の順序の数値に対応する配列として前記メインメモリ１ｂに設定した上でこの配列へのポインタを前記選出した数値で参照される配列の要素として格納し、かつ、前記複数の数値のうち最後の数値に対応する配列である終段配列Ａ４においてこの数値で特定される要素として前記後続パターンが格納される記憶領域ＭＲを指示するポインタを格納して、前記読込ステップにて、前記抽出ステップで抽出した前方データを前記所定のビット長を有し前記所定の順序が与えられる複数の数値に分割し、これら複数の数値で前記複数の配列Ａ１、Ａ２、Ａ３、Ａ４を前記始段配列Ａ１を起点に探索し、前記終段配列Ａ４の要素として格納されているポインタにより指示される前記記憶領域ＭＲに前記後続パターンが格納されている場合にこの後続パターンを読み込むものとしており、メインメモリ１ｂの浪費を避けることができるのみならず、読込ステップにて所望の後続パターンが格納されている記憶領域ＭＲを参照するに際し複雑なアドレス計算を実行する必要から解放されるため、パターン照合処理の一層の高速化を図ることが可能となっている。
【００３６】
前記複数のパターンの各々は、予め設定された一または複数のグループに属しており、前記格納ステップにて、前記パターンが属しているグループを識別するグループ識別情報を前記後続パターンに付加して、これらグループ識別情報及び後続パターンを前記メインメモリ１ｂに格納するものとし、さらに、前記比較ステップにて前記後続パターンと前記前方データに後続するデータとが合致した場合に、この後続パターンに係るグループ識別情報を含む結果情報を出力する出力ステップを具備するものとしたため、何れのグループに属する照合パターンと対象データとが合致したのかを知得できる。このことは、対象データを（照合パターンのグループに応じて）分類する場合等に有効となる。
【００３７】
前記複数のパターンの各々は、予め設定された一または複数のグループに属しており、前記格納ステップにて、前記パターンが属しているグループを識別するグループ識別情報を前記後続パターンに付加して、これらグループ識別情報及び後続パターンを前記メインメモリ１ｂに格納するものとし、さらに、前記複数のパターンのうち前記対象データとの照合を行うべきパターンのグループの指定を受け付ける指定ステップを具備して、前記読込ステップにて、前記指定ステップで指定されたグループを識別するグループ識別情報が付加されている後続パターンのみを前記メインメモリ１ｂより読み込むものとしているため、比較的処理時間を要する格納ステップを再度実行することなく、照合パターンの一部のみを有効にまたは無効にすることが可能となっている。
【００３８】
なお、本発明は以上に詳述した実施形態に限られるものではない。上記実施形態の方法では、パターン全体の長さが先行パターンの設定長よりも短いような場合に問題が起こり得る。典型的には、１文字のみの照合パターンが、先行パターンの長さである３２ビットに満たない。このような場合には、格納ステップにおいて、当該パターンの後方に特定のビット列、例えば、０ビットのみからなるビット列のように文字コードとして使用されていないものを付加して全体として先行パターンの設定長に相当する長さとなるパターンを構成し、かつこれの後続パターンをヌル文字等とした上で、上述した格納ステップを実行する。さらに、読込ステップにおける追加処理として、各段の配列における００ｈ番目の要素を必ず参照するようにして、ヌル文字等を後続パターンとして格納している記憶領域へのポインタが格納された終段配列に至るか否かを確認するようにする。このような方法をとれば、先行パターンより短い照合パターンについても対象データとの照合を行い得る。勿論、先行パターンの設定長に満たない照合パターンを対象外とするという単純な解決策をとることを妨げない。
【００３９】
その他各部の具体的構成やデータ構造、処理の詳細な手順等もまた、上記実施形態に限られるものではなく、本発明の趣旨を逸脱しない範囲で種々変形が可能である。勿論、パーソナルコンピュータその他の汎用的なコンピュータにプログラムをインストールすることで本発明に係るパターン照合装置を構成するのではなく、専用ハードウェアとして構成することも可能である。
【図面の簡単な説明】
【００４０】
【図１】本発明の一実施形態におけるパターン照合装置が具備するハードウェア資源を示す図。
【図２】同パターン照合装置の機能ブロック図。
【図３】グループ分けされ、グループ識別情報と関連づけられた照合パターンを例示する図。
【図４】グループ分けされ、グループ識別情報と関連づけられた照合パターンを例示する図。
【図５】格納ステップを経て記憶手段に格納された後続パターンの論理構造を例示する図。
【図６】格納ステップを経て記憶手段に格納された後続パターンの論理構造を例示する図。
【図７】対象データを例示する図。
【図８】対象データ、照合開始位置、前方データを説明する図。
【図９】本実施形態におけるパターン照合の処理の手順を示すフローチャート。
【符号の説明】
【００４１】
１…コンピュータ（パターン照合装置）
１１…格納部
１２…抽出部
１３…読込部
１４…比較部
１５…反復部
１６…出力部
１７…指定部
【図１】
2005025657.tif 000003
【図２】
2005025657.tif 000004
【図３】
2005025657.tif 000005
【図４】
2005025657.tif 000006
【図５】
2005025657.tif 000007
【図６】
2005025657.tif 000008
【図７】
2005025657.tif 000009
【図８】
2005025657.tif 000010
【図９】
2005025657.tif 000011