JP2745710B2

JP2745710B2 - ストリングサーチ方法およびそのための装置

Info

Publication number: JP2745710B2
Application number: JP1217148A
Authority: JP
Inventors: 匡大曾根; 弘行北嶋; 英俊伊東
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1989-08-23
Filing date: 1989-08-23
Publication date: 1998-04-28
Anticipated expiration: 2013-04-28
Also published as: JPH0380366A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、情報検索システム等に使用されるストリン
グサーチ方法、すなわち、入力データ記号列（以下、
「テキスト」という）中に、指定された記号列（「パタ
ーン」，「キーワード」等と呼ばれる）が存在するか否
かを判別する方法およびそのための装置に関する。上記
ストリングサーチ装置は、テキスト情報の検索に欠かせ
ないものである。

〔従来の技術〕

オフィスオートメーション（OA）化に伴なって文書情
報のデータベース化が急速に進んでおり、データベース
の規模も大規模化しつつある。このような状況の中で、
文書情報処理の高速化が強く望まれている。なかでも、
テキストと呼ばれる記号列の中からパターンあるいはキ
ーワードと呼ばれる指定された特定の記号列を探し出す
ストリングサーチ処理は、使用頻度が高く処理負荷も極
めて大きいので、その高速化が特に望まれている。

これに対しては、ストリングサーチ処理を、それ専用
のハードウェアを用いて処理する方法がいくつか提案さ
れている。その代表的なものに、セルアレイ法と、表一
暼（table look at）型の有限オートマトン法がある。
前者のセルアレイ法は、第32図に示す如く、多数のセル
10をアレイ状に直列に接続し、セル間の状態信号70の伝
達により、ストリングサーチを実現する方法である。各
セル10では、前段のセルの状態信号と当該セルにおける
パターン１文字とテキスト１文字との比較結果により、
新たに記号列を生成させ、それを後段のセルへ伝達す
る。この状態信号70の生成および伝達方法は、１文字単
位に状態遷移を惹き起こす有限オートマトンの原理に基
づいている。

第34図に、パターンが「HORSE」の場合に、従来方式
で用いられている有限オートマトンの状態遷移図を示
す。ここで、100は有限オートマトンの状態番号を表わ
し、200はテキストの入力文字に対する状態遷移の方向
を表わしている。この例の場合、テキストから文字が１
文字ずつ連続して「Ｈ」「Ｏ」「Ｒ」「Ｓ」「Ｅ」と入
力されると、状態番号100が、S₀から順次、S₁，S₂，
S₃，S₄，S₅と推移し、状態番号100がS₅となったところ
でパターンが検出される。第33図に、状態番号とそれに
対応するサーチ状態との関係を示した。

一方、前記後者の表一瞥型の有限オートマトン法は、
テキストを１文字ずつ入力しながら、その都度、状態遷
移テーブルを参照し、有限オートマトンの状態遷移を繰
り返しながら、パターンの検出を行う方法である。特
に、複数のパターンを検索する場合は、従来は、複数の
パターンの検索を考慮して、状態遷移テーブルを作成す
ることにより、同一のテーブルの参照により、複数のパ
ターンの検索を実現している。

第35図に、パターンが「CAT」と「DOG」の場合の、従
来方式における有限オートマトンの状態遷移図を示す。
ここで、100は有限オートマトンの状態遷移図を示し、2
00はテキストの入力文字に対する状態遷移の方向を示し
ている。第35図では、状態０で文字「Ｃ」が入力される
と状態は１になり、文字「Ｄ」が入力されると状態は４
になり、その他の文字が入力されると、状態は０のまま
であることを示している。また、状態１で文字「Ａ」が
入力されると状態は２になり、文字「Ｄ」が入力される
と状態は４になり、文字「Ｃ」が入力されると状態は１
のままで、その他の文字が入力されると状態は０に戻る
ことを示している。なお、状態番号とそれに対応するサ
ーチ状態との関係を、第37図に示した。

上述の如き状態遷移を実現するために、表一瞥型の有
限オートマトン法では、第36図に示す如き状態遷移テー
ブルを用いる。これは、入力文字と現在の状態から次の
状態を求めるためのテーブルである。ここで、入力文字
は整数の文字コードとしてテーブルを参照するようにす
る。この例の場合、テキストから文字が１文字ずつ連続
して「Ｃ」「Ａ」「Ｔ」と入力されると、状態は1,2,・
・・・と順次遷移し、状態番号が３となったところで、
パターン「CAT」の検出が認識される。同様に、「Ｄ」
「Ｏ」「Ｇ」と入力されると、状態は4,5,・・・・と順
次遷移し、状態番号が６となったところでパターン「DO
G」の検出が認識される。

上述の技術については、例えば、アイ・イー・イー・
イートランザクションオンコンピューターズ，シ
ー28（1979年），第384〜394頁（IEEE Transations on
Computers,vol.C−28,No.6,pp.384-394,1979）や、コン
ピュータ，第13巻第１号，第26〜40頁（Computer,vol.1
3,No.1,pp.26-40,1980）等において論じられている。

〔発明が解決しようとする課題〕

上記従来技術は、（１）１文字単位に状態遷移を惹き起こす有限オート
マトンを基本としているので、ストリングサーチの検索
速度は原理的に１単位時間あたり１文字となっていた。
テキストを格納している記憶装置から文字をフェッチす
る速度が１単位時間あたり１文字であるならば、これで
問題はない。しかし、現在では、16ビッシマシン/32ビ
ットマシンが出現しており、１時刻あたり２バイトフェ
ッチ/4バイトフェッチも可能となってきた。前述の従来
技術ではこれに対応できず、テキストの文字のフェッチ
速度がこのように向上しても、検索速度は１単位時刻あ
たり１文字に制限されてしまうという問題（２）複数パターンを同時検索するためには、その状
態遷移が第35図に示した如く、極めて複雑となり、その
ために、状態遷移テーブルを作成するのに多大のオーバ
ヘッドを要するという問題があった。これは、複数のパターン間の遷移についても
考慮してテーブルを作成しなければならないことに起因
している。特に、パターン数の多いときや、あるパター
ンの部分文字列が他のパターンの中の部分文字列として
存在している場合に、極めて複雑となる。このテーブル
作成時間のオーバヘッドは、ストリングサーチを行う上
で、特に長大なテキストの検索を行う場合以外、無視で
きないものである。

本発明は上記事情に鑑みてなされたもので、その目的
とするところは、従来の技術における上述の如き問題を
解消し、検出速度を向上させるとともに、複数パターン
検索のための表一瞥型の有限オートマトン法における状
態遷移テーブルの作成時間を短縮可能としたストリング
サーチ方法およびそのための装置を提供することにあ
る。

〔課題を解決するための手段〕

本発明の上述の目的は、ある長さのコード長のコード
で表現される文字（記号）により構成される第１の文字
列中に、指定された第２の文字列が存在するかどうかを
判定するストリングサーチ方法において、前記第１の文
字列から複数文字単位のデータを入力し、複数文字単位
に状態遷移を惹き起こす有限オートマトンを用いて、該
複数文字単位の入力データと現在のサーチ状態とから次
のサーチ状態を決定し、該新たなサーチ状態が検索すべ
き前記第２の文字列を検出したことを表わすサーチ状態
になったかどうかを判断し、前記第２の文字列を検出し
た状態になった場合には検出処理を行い、前記第１の文
字列の入力アドレスを複数文字分だけ先に更新し、前記
第１の文字列から次の複数文字単位のデータを入力する
動作を繰り返すことを特徴とするストリングサーチ方
法、および、ある長さのコード長のコードで表現される
文字（記号）により構成される第１の文字列中に、指定
された第２の文字列が存在するかどうかを判定するスト
リングサーチ装置において、前記第１の文字列を複数文
字単位にシーケンシャルに入力する手段と、複数文字単
位に状態遷移を惹き起こす有限オートマトンを用い、前
記複数文字単位の入力データと現在のサーチ状態とから
次のサーチ状態を決定し、該新たなサーチ状態と検索す
べき前記第２の文字列を検出したことを表わすサーチ状
態（パターン検出状態）とを比較する手段を有すること
を特徴とするストリングサーチ装置によって達成され
る。

〔作用〕

まず、本発明に係るストリングサーチ方法において
は、第１の文字列から複数文字単位のデータを入力し、
複数文字単位に状態遷移を惹き起こす有限オートマトン
を用いることにより、複数文字単位にストリングサーチ
におけるサーチ状態の遷移が実現できる。これから、新
たなサーチ状態が検索すべき前記第２の文字列（パター
ン）を検出したことを表わすサーチ状態になったかどう
かを判断し、前記第２の文字列を検出した状態になった
場合には検出処理を行うことができる。これらにより、
テキストの文字入力を複数文字単位としてストリングサ
ーチを実行できるので、検索速度の向上が達成できる。
なお、本発明に係るストリングサーチ装置は、上記スト
リングサーチ方法を効率的に実行するのに好適なストリ
ングサーチ装置を実現できるものである。

また、本発明に係るストリングサーチ装置において、
単数のパターンに対する表一瞥型の有限オートマトン機
構を複数個設け、そられらを並列に実行させる手段を導
入することにより、複数パターンの検索を個々の単数パ
ターンの検索に展開することができる。これにより、前
記状態遷移テーブルを作成する際、パターン間の遷移を
考慮する必要がなくなり、個々のパターンに対する状態
遷移テーブルを独立に作成すれば良くなるので、テーブ
ル作成オーバヘッドを短縮することができるものであ
る。

〔実施例〕

以下、本発明の実施例を図面に基づいて詳細に説明す
る。なお、以下の説明においては、文字のコード長は１
バイトと仮定する。

まず、本発明の第一の実施例として、テキストが２文
字単位で入力される場合について、説明する。第１図
は、本実施例のストリングサーチシステムの構成例であ
る。図において、１は検索すべきテキストを格納する記
憶装置、２は上記テキスト１に対しストリングサーチを
実行するストリングサーチ装置、３はテキストデータ転
送路、４は検索結果を出力する信号線を示している。本
実施例においては、テキストデータは、記憶装置１か
ら、入力手段1001を用いて複数文字単位にシーケンシャ
ルにテキストデータ転送路３を経由してストリングサー
チ装置２に入力される。更に、２文字単位に状態遷移を
惹き起こす有限オートマトン1007を用いることで、パタ
ーンの検出を行う。以下、検索パターンの例として、
「HORSE」を考える。

この場合、有限オートマトンの状態は、第２図に示す
如く定義する。また、ここで提案する、２文字単位に状
態遷移を惹き起こす有限オートマトン1007の状態遷移図
は、第３図のようになる。ここで、1200が有限オートマ
トンの状態番号を表わし、1300がテキスト入力文字（２
文字単位）に対する状態遷移の方向を表わしている。こ
れは、テキストから文字が２文字ずつ連続して「XH」
「OR」「SE」と入力されると、状態番号がS₀から順次、
S₁₁，S₁₂，S₁₃と推移し、また、テキストから文字が２
文字ずつ連続して「HO」「RS」「EX」と入力されると、
状態番号がS₀から順次、S₂₁，S₂₂，S₂₃と推移すること
を示している。ここで、Ｘは任意の１文字を表わすもの
とする。なお、状態番号S₁₃とS₂₃はパターンが検出され
た状態である。このような有限オートマトンを用いるこ
とにより、テキストを２文字単位に入力しながら、スト
リングサーチを実行することが可能となる。

これを実現するストリングサーチ装置２の構成例を第
４図と第５図に示す。第４図は第一の実施例におけるス
トリングサーチ装置２の全体構成図であり、第５図はそ
こで使用されるセル110の構成図である。第４図におい
て、120はパターンの１文字を格納するパターンレジス
タ、110はセルである。セル110は、記置装置３から転送
されてきたテキストの２バイトの文字データ130と、パ
ターンデータ転送路140を通して入力されるパターンの
２バイトの文字データと、前段セルから転送されてきた
状態信号170とを入力として、パターン検出信号150と本
セルの状態信号170を生成する回路である。本実施例に
おける２文字単位入力有限オートマトンの場合、第４図
に示す如く、直列に接続したセルを２段並べた構成とす
る。これは、第３図に示す有限オートマトンの状態遷移
図に対応している。一方、160は各セルから転送されて
きたパターン検出信号150から検出信号４を生成する検
出信号生成回路である。これは、例えば、すべてのパタ
ーン検出信号150のORをとる論理によって実現できる。

次に、第５図に示したセル110の構成について説明す
る。各セル110には、テキストの入力文字２バイトがテ
キスト入力線を通して入力される。111はこれら２バイ
トのデータ同志の一致／不一致をマスク付きで判定し、
一致信号116を生成する一致判定回路である。また、114
はマスクラッチであり、マスクラッチ114aの内容がバイ
ナリコードの“1"（以下、単に「“1"」という）である
ときに、一致判定回路111においてその第１バイトにマ
スクをすることを示し、同様に、マスクラッチ114bの内
容が“1"であるときに、一致判定回路111においてその
第２バイトにマスクをすることを示す。114aを第１マス
クラッチ、114bを第２マスクラッチと呼ぶ。

一致判定回路111は、例えば、第６図の如き回路によ
り実現できる。第６図に示す回路においては、テキスト
入力線130とパターン入力線140から入力される２バイト
のデータを16個のEXOR回路で同時に比較し、それらがす
べて一致した場合に、更に、マスクラッチ出力線118a,1
18bの値を考慮して、一致信号116を出力するというもの
である。なお、一致判定回路111として、コンテントア
ドレサブルメモリを用いてもよい。

一方、115はインジケータラッチであり、特に115aは
パターンの先頭を示す先頭インジケータラッチ、115bは
パターンの末尾を示す末尾インジケータラッチである。
また、113は有限オートマトンの状態を示す状態ラッチ
である。制御回路112は、インジケータラッチ115の情報
と、前段のセルの状態信号170と一致信号116とから、本
セルの状態ラッチ113への入力信号117とパターン検出信
号150を生成する回路である。これは、例えば、第７図
に示す如き回路によって実現できる。入力信号117は、
本セルの状態ラッチ113の入力となる。

次に、パターンが「HORSE」の場合の、本実施例の動
作を説明する。

まず、予めパターン「Ｈ」，「Ｏ」，「Ｒ」，
「Ｓ」，「Ｅ」を１文字ずる第４図のパターンバッファ
120−１〜120−５にセットしておく。また、第３図の状
態遷移図における入力文字のうち、任意文字「Ｘ」に対
するマスクラッチ114に“1"をセットする。つまり、第
８図に示す如く、第１マスクラッチ114a-11と第２マス
クラッチ114b-23に、“1"をセットする。更に、パター
ンの先頭文字と末尾文字を教えるために、先頭インジケ
ータラッチ115a-11と115a-21,末尾インジケータラッチ1
15b-13と115b-23に“1"をセットしておく。

この後、テキストに対するストリングサーチを開始す
る。すなわち、テキストを記憶装置１から１時刻毎に２
文字ずつ、テキストデータ転送路３を通して、ストリン
グサーチ装置２のすべてのセル110に同時に入力してい
く。各セル110の内部では、まず、一致判定回路111にお
いて２バイトのテキストの入力文字と、パターンバッフ
ァ120から各セルそれぞれに転送されてくる２バイトの
パターンの文字とが比較される。例えば、一致判定回路
111-12では、入力文字とパターンの第２文字と第３文字
「OR」との比較が行われる。同様にして、一致判定回路
111-13,111-21,111-22では、それぞれ、入力文字とパタ
ーンの「SE」，「HO」，「RS」との比較が行われる。

但し、一致判定回路111-11では、第１マスクラッチ11
4a-11が“1"であるため、第１バイトをマスクして比較
する。従って、論理的には、「XH」と比較していること
になる。同様に、一致判定回路111-23では、第２マスク
ラッチ114b-23が“1"であるため、論理的には、「EX」
と比較していることになる。ここで、Ｘは前述の通り、
任意の１文字を指す。

次に、制御回路112では、第７図に示す如く、前段セ
ルの状態信号170と先頭インジケータラッチ115aの出力
線119aとのOR出力と、一致信号116とのANDをとり、新た
な状態信号117を生成する。この新たな状態信号117は、
本セルの状態ラッチ113の入力とする。また、本状態信
号117と末尾インジケータ115bの出力線119bとのANDをと
った結果をパターン検出信号150とする。これが“1"と
なることが、パターンの検出を意味する。

上述の構成では、前記状態ラッチ113-ijの内容が“1"
であることが、第３図における有限オートマトンの状態
信号がS_ijとなったことを表わしている。

以下、テキストの例として、16文字のテキスト「CAT,
HORSE,MONKEY」を考える。この例の場合の時刻に対する
テキスト入力線130と各セル110-ijのパターン入力線140
-ij,一致信号116-ij,状態ラッチ113-ijの値の変化を、
第９図に示す。この例の場合は、時刻3,時刻4,時刻５、
それぞれ、状態ラッチ113-21,113-22,113-23が、“1"と
なる。また、セル110-23の末尾インジケータラッチ115b
-23の内容が“1"であるので、パターン検出信号150-23
は“1"となり、パターンを検出したことがわかる。この
例の場合、８時刻でストリングサーチを終了することが
できる。

以下、第二の実施例として、テキストを４文字単位に
入力する方式について説明する。この場合には、４文字
単位に状態遷移を惹き起こす有限オートマトンを用い
る。検索パターンの例として、第一の実施例と同じ、
「HORSE」を考える。

この場合の有限オートマトンの状態は、第10図に示す
如く定義する。また、ここで提案する４文字単位に状態
遷移を惹き起こす有限オートマトンの状態遷移図は、第
11図のようになる。第11図において、2200が有限オート
マトンの状態番号を表わし、2300がテキストの入力文字
（４文字単位）に対する状態遷移の方向を表わしてい
る。第11図では、テキストから文字が４文字ずつ連続し
て「XXXH」，「ORSE」と入力されると、状態番号がS₀か
ら順次、S₁₁，S₁₂と推移し、また、テキストから文字が
４文字ずつ連続して「XXHO」，「RSEX」と入力される
と、状態番号がS₀から順次S₂₁，S₂₂と推移することを示
している。同様に、文字が「XHOR」，「SEXX」と入力さ
れると、状態番号がS₀から順次、S₃₁，S₃₂と推移し、
「XHOR」，「SEXX」と入力されると、状態番号がS₀から
順次、S₄₁，S₄₂と推移することを示している。Ｘは任意
の１文字を表わしており、状態番号S₁₂，S₂₂，S₃₂およ
びS₄₂は、すべて、パターンが検出された状態である。
このような有限オートマトンを用いることにより、テキ
ストを４文字単位に入力しながら、ストリングサーチを
実行することが可能となる。

これを実現するストリングサーチ装置２の構成例を第
12図に示す。ここでは、図に示す如く、セル210を直列
に接続したものを４段並べる構成とする。ここで、220
はパターンの１文字を格納するパターンレジスタ、260
は検出信号生成回路である。セル210の構成例を第13図
に示す。ここで211は４バイトのデータ同志の一致／不
一致をマスク付きで判定する一致判定回路、213は有限
オートマトンの状態を示す状態ラッチ、214はマスクラ
ッチを示しており、特に、214aは一致判定回路211にお
いて、その第１バイトにマスクをすることを示す第１マ
スクラッチ、同様に、210b,214cおよび214dは一致判定
回路211において、その第2,第3,第４バイトにマスクを
することを示すマスクラッチである。

また、215はインジケータラッチであり、特に215aは
パターンの先頭を示す先頭インジケータラッチ、215bは
パターンの末尾を示す末尾インジケータラッチである。
制御回路212は、第一の実施例の場合と同様に、本セル
の状態信号270とパターン検出情報250を生成する回路で
ある。

次に、動作を説明する。

まず、予め検索パターン「HORSE」を１文字ずつ、第1
2図に示したパターンバッファ220−１〜220−５までに
セットしておく。また、第11図の状態遷移図における入
力文字のうち、任意文字「Ｘ」に対応するマスクラッチ
214に、“1"をセットする。すなわち、マスクラッチ214
a-11,214b-11,214c-11,214a-21,214b-21,214a-31,214d-
22,214c-32,214d-32,214b-42,214c-42,214d-42に、“1"
をセットしておく。更に、パターンの先頭文字と末尾文
字を教えるために、先頭インジケータラッチ210a-11,21
5a-21,215a-31および215a-41と、末尾インジケータラッ
チ215b-12,215b-22,215b-32および215b-42に、“1"をセ
ットしておく。

次に、テキストを記憶装置１から４文字ずつテキスト
データ転送路３を通して各セル210に入力していく。各
セル210内部の一致判定回路211では、４バイトの入力文
字と４文字のパターンの文字とが比較される。つまり、
一致判定回路211-11では、入力４文字と「XXXH」とが比
較される。同様に、一致判定回路211-12,211-21,211-2
2,211-31,211-32,211-41,211-42では、それぞれ、入力
４文字とパターン「ORSE」，「XXHO」，「RSEX」，「XH
OR」，「SEXX」，「HORS」，「EXXX」とが比較される。

制御回路212は、一致判定回路211からの出力である一
致信号216と、前段のセル210の状態信号270と先頭イン
ジケータラッチ215aの出力線219aとから、本セルの状態
信号217を生成し、それを状態ラッチ213の入力とする。
状態ラッチ213-ijが“1"であることが、第12図における
有限オートマトンの状態番号がS_ijとなったことを表わ
している。そして、本セルの状態信号217と末尾インジ
ケータ215bの出力線219bとのANDをとった結果を、パタ
ー使検出信号250とする。それが“1"となることが、パ
ターンの検出を意味するのは前述の通りである。

テキストの例として、第一の実施例と同様に、16文字
のテキスト「CAT,HORSE,MONKEY」を考える。この例の場
合の時刻に対する、テキスト入力線230と各セル210-ij
のパターン入力線240-ij,一致信号216-ij,状態ラッチ21
3-ijの値の変化を、第14図に示す。この例の場合には、
時刻2,時刻３にそれぞれ、状態ラッチ213-41と213-42と
が“1"となる。そして、セル210-43の末尾インジケータ
ラッチ215b-43の内容が“1"であるので、パターン検出
信号250-43は“1"となり、パターンを検出したことがわ
かる。この例の場合は、４時刻でストリングサーチが終
了する。

次に、第三の実施例として、パターンにドントケア文
字（ワイルド文字）を含んだパターンを検索する場合を
説明する。

例として、第一の実施例で用いた２文字単位入力の有
限オートマトンを用いる。検索パターンの例としては
「H!RSE」を考える。ここで、「！」はドントケア文字
（ワイルド文字）、すなわち、１文字の任意文字を表わ
すものとする。この場合の有限オートマトンの状態は、
第15図に示す如く定義する。また、第16図に、この場合
の、２文字単位入力の有限オートマトンの状態遷移図を
示す。状態番号S₁₃，S₂₃はパターンが検出された状態を
示している。

これを表現するストリングサーチ装置２は、第一の実
施例に示したものと同じ構成で良い。予め各レジスタや
ラッチにセットしておくデータも、ドントケア文字に対
応するマスクレジスタ114a-12と114b-21に“1"をセット
しておくことを除いて、同じで良い。なお、マスクレジ
スタ114a-12と114b-21に“1"をセットしておくことは、
第一の実施例において、セル110-12や110-21にパターン
として「OR」や「HO」を入力させる代りに「!R」や「H
!」を入力させる役割を果たしている。この場合の動作
は、第10図と同様になる。

次に、可変長ドントケア文字「？」を含んだパターン
検索について簡単に説明する。なお、ここで、可変長ド
ントケア文字「？」とは、０文字以上の任意の文字列を
表わしている。この場合の、有限オートマトンの状態の
定義および状態遷移の例を、第17図と第18図に示す。こ
の例では、２文字単位に状態遷移を惹き起こす有限オー
トマトンを用いている。これを実現する装置は、第４図
に示した装置内のセル110の内部論理とセル間の接続
を、第18図における状態遷移に対応するように若干変更
するだけで良い。

また、複数のパターンの同時検索は、複数のパターン
をぱターンバッファにシリアルにセットして、インジケ
ータラッチにそれに対応した値をセットするだけで容易
に実現できる。

本実施例では、前述の文献（前者）によるセルアレイ
法をベースとした装置を例に説明したが、他のセルアレ
イ法をベースとした装置にも容易に適用することが可能
である。

次に、第四の実施例として、表一瞥型の有限オートマ
トン法を利用した場合の例を説明する。以下に説明する
実施例では、２文字単位に状態遷移を惹き起こす有限オ
ートマトンを用いることにする。

第19図は、本実施例におけるストリングサーチ装置の
構成例である。図中、510はテキストデータ転送路を通
して記憶装置から入力されてくるテキストの入力文字を
格納する２バイト分の入力文字レジスタ、511は有限オ
ートマトンの状態の情報を格納する状態レジスタ、512
は検索パターンに対する状態遷移テーブルを格納するラ
ンダムアクセスメモリ（RAM）、515は該RAM512に対する
アドレス線、513は次の有限オートマトンの状態の情報
を格納する次状態レジスタ、514は次状態がパターンを
検出した状態になったかどうかを判定するパターン検出
判定回路を示している。

検索パターンの例として、「HORSE」を考えると、そ
の状態遷移図は、第20図のようになる。これに対応する
状態遷移テーブルは、第21図のようになる。状態遷移テ
ーブルは、現在の状態と入力文字とから、次の状態がわ
かるようにしたテーブルである。この状態遷移テーブル
は、予め前記RAM512にセットしておく。そして、初期状
態０を状態レジスタ511にセットしてから、検索を開始
する。

第22図に、本実施例の動作を示す。テキストの例とし
て「CAT,HORSE,MONKEY」を考える。テキストは、１時刻
に２文字ずつ、記憶装置からテキスト転送路を通して入
力していく。時刻１では、状態レジスタ511と入力文字
レジスタ510の内容が、それぞれ、「０」と「CA」であ
るので、それをアドレスとして、RAM512に格納されてい
る状態遷移テーブルにアクセスする。そして、次状態
「０」をフェッチし、それを次状態レジスタ513に入力
する。そして、それを再び、状態レジスタ511に入力す
る。一方、パターン検出回路514では、次状態が「３」
か「６」になったかどうかにより、パターンの検出を監
視している。

以下、この動作を繰り返し、第22図に示される如く、
時刻５で次状態レジスタ513に「６」が入力され、パタ
ーン「HORSE」が検出される。本実施例では、８時刻で
ストリングサーチを終了させることができる。

次に、第五の実施例を説明する。第23図は、本発明の
表一瞥型の有限オートマトン法を用いたストリングサー
チ装置の構成例を示すものである。この例では、２つの
パターン「CAT」と「DOG」の検索を行う場合を考える。
図において、11と21は上述のそれぞれのパターンに対す
る有限オートマトンの状態の情報を格納する状態レジス
タ、10はテキストデータの転送路を通して記憶装置から
入力されてくるテキストの入力文字を格納する入力文字
レジスタ、12と22はそれぞれのパターンに対する状態遷
移テーブルを格納するRAM、15と25は該RAM12と同22に対
するそれぞれのアドレス線、また、13と23はそれぞれの
パターンに対する次の有限オートマトンの状態を格納す
る次状態レジスタ、14と24は次状態がパターンを検出し
た状態になったかどうかを判定するパターン検出判定回
路、30はパターンの検出情報を生成する検出情報生成回
路を示している。

本装置を用いれば、２つのパターンの状態遷移は、別
々に作成することができる。従って、状態遷移テーブル
の作成時間が短縮できる。２つのパターン「CAT」と「D
OG」に対する有限オートマトンの状態遷移を、第24図お
よび第25図に示す。これは、「CAT」に対しては、テキ
ストから文字が連続して「Ｃ」，「Ａ」，「Ｔ」と入力
されると、状態番号が０から順次、1,2,3と推移してパ
ターンが検出されることを示しており、また、「DOG」
に対しては、文字が連続して「Ｄ」，「Ｏ」，「Ｇ」と
入力されると、状態番号が０から順次、4,5,6と推移し
てパターンが検出されることを示しているものである。
これに対する状態遷移テーブルを、第26図および第27図
に示す。第23図におけるRAM12と22には、この状態遷移
テーブルを、それぞれ、格納しておく。

次に、本実施例の動作を第28図を用いて説明する。第
28図は、状態レジスタ，入力文字レジスタ，次状態レジ
スタの内容の変化を示すものである。テキストの例とし
て、13文字のテキスト「CAT,HORSE,DOG」を考える。ま
ず、検索を始める前に、状態レジスタ11と12に初期状態
０をセットしておく。そして、テキストのデータを一時
刻に１文字ずつ、記憶装置からテキストデータ転送路を
通して本装置に入力していく。

時刻１では、状態レジスタ11と入力文字レジスタ10の
内容が、それぞれ「０」と「Ａ」であるので、それをア
ドレスとしてRAM12に格納されている状態遷移テーブル1
6にアクセスする。そして、次状態「１」をフェッチ
し、それを次状態レジスタ13に入力する。そして、それ
を再び、状態レジスタ11に入力する。一方、パターン検
出判定回路14では、次状態が「３」になったかどうかに
より、パターンの検出を監視している。同様な動作を、
状態レジスタ21,アドレス線22,次状態レジスタ23および
パターン検出判定回路24により並行して行い、状態レジ
スタ21には「０」が入力される。以下、この動作が繰り
返され、第28図に示される如く、時刻３で次状態レジス
タ13に「３」が入力され、パターン「CAT」が検出さ
れ、時刻13で次状態レジスタ23に「３」が入力され、パ
ターン「DOG」が検出される。

次に、第六の実施例を説明する。第29図は、第六の実
施例を実行するためのストリングサーチ装置の構成例を
示すものである。ここで、ストリングサーチを行う機構
は、第五の実施例と同じである。第五の実施例と異なる
点は、本実施例においては、状態遷移テーブル作成装置
19や29を、各RAM毎に設けている点である。これによ
り、各パターン毎に、状態遷移テーブルを並列に作成で
きるので、テーブル作成時間を削減することができるも
のである。

次に、第七の実施例を以下、説明する。第五の実施例
では、個々のパターンに対して状態遷移テーブルを作成
し、それを用いて検索する方法を説明した。この方法に
よる場合には、検索パターン数だけ、独立にアクセスで
きるRAMを用意する必要がある。そこで、本実施例で
は、独立にアクセスできるRAMの個数よりも検索パター
ン数の方が多い場合の、効率的な検索方法について説明
する。例として、４個の検索パターンを、２個のRAM、
すなわち、２個の状態遷移テーブルを用いて検索する方
法について説明する。

ここでは、４個の検索パターンをパターン１〜パター
ン４とする。本実施例においては、これを、例えば、パ
ターン１とパターン２を同時に検索するための状態遷移
テーブル（第36図参照）と、パターン３とパターン４を
同時に検索するための状態遷移テーブルとを作成し、こ
の２つの状態遷移テーブルを用いて検索を行う。これに
より、２つの独立にアクセスできるRAMを用いて４個の
パターンを検索することができる。

次に、第八の実施例を説明する。これは、第五の実施
例で説明した構成例（第23図参照）で実現できる。但
し、本実施例においては、入力文字レジスタ13および状
態遷移テーブルを格納するRAM12は、前記第四の実施例
（第19図参照）で説明した複数文字分の入力文字レジス
タ510および複数文字単位に状態遷移を惹き起こす有限
オートマトンの状態遷移テーブルを格納するRAM512を、
用いるものとする。これにより、状態遷移テーブル作成
時間の削減と、入力テキスト文字を複数文字単位で処理
することによるストリングサーチ処理の高速化とが、同
時に実現できる。

次に、第九の実施例として、第30図に示す如きテキス
トデータを複数文字単位に入力する入力手段1001および
複数文字単位の比較器2003から構成されるストリングサ
ーチ装置について説明する。本実施例においては、予
め、テキスト文字列と比較するパターン文字列を記憶装
置2001に格納し、かつ、パターン文字列中の任意の１文
字をキーパターンレジスタ2005およびパターンデータレ
ジスタ2004に、複数文字分格納する。入力手段1001を用
いて、テキストデータレジスタ2004のデータを比較器20
03を用いて比較し、その結果を検索制御手段2002で判定
する。

ここで、テキストを「BULL・HORSE」、パターンを「H
ORSE」とした場合の動作を説明する。テキストは、入力
手段1001を用いて、４文字単位で入力されるものとす
る。また、キーパターンレジスタ2005の値としては、パ
ターン文字列中の先頭文字「Ｈ」を４文字並べた「HHH
H」とする。第31図は、テキストデータレジスタ1004と
パターンデータレジスタ2002の入力およびその比較結果
を示すものである。まず、時刻１では、テキスト「BUL
L」と上記キーパターン「HHHH」とを比較する。結果
は、全文字不一致であるので、４文字分シフトして、次
のテキストを入力する。

時刻２では、テキスト「・HOR」とキーパターン「HHH
H」を比較する。ここでは、２文字目の「Ｈ」が一致し
ているので、時刻３では、テキストは２文字分シフト
し、パターンは２文字目以降のデータを入力する。つま
り、ここでの入力テキストは「ORSE」、入力パターンは
「ORSE」であり、完全に一致し、パターン「HORSE」が
検出される。本実施例では、３時刻でストリングサーチ
を終了させることができる。

上述の各実施例は、いずれも本発明の一例として示し
たものであり、本発明はこれらに限定されるべきもので
はないことは言うまでもない。

〔発明の効果〕

以上、詳細に述べた如く、本発明によれば、第１の文
字列から複数文字単位のデータを入力し、複数文字単位
に状態遷移を惹き起こす有限オートマトンを用いること
により、複数文字単位にストリングサーチにおけるサー
チ状態の遷移が実現できることから、検出速度を向上さ
せるとともに、複数パターン検索のための表一瞥型の有
限オートマトン法における状態遷移テーブルの作成時間
を短縮可能としたストリングサーチ方法およびこのため
の装置を実現できるという顕著な効果を奏するものであ
る。

【図面の簡単な説明】

第１図は本発明の第一の実施例におけるストリングサー
チシステムとストリングサーチ装置の構成図、第２図〜
第９図は第一の実施例の説明図、第10図〜第14図は第二
の実施例の説明図、第15図〜第18図は第三の実施例の説
明図、第19図〜第22図は第四の実施例の説明図、第23図
〜第28図は第五の実施例の説明図、第29図は第六の実施
例におけるストリングサーチ装置の構成図、第30図〜第
31図は第九の実施例におけるストリングサーチ装置の構
成図、第32図は従来のストリングサーチ装置の構成図、
第33図〜第37図は従来技術の説明図である。 1:記憶装置、2:ストリングサーチ装置、3:テキストデー
タ転送路、4:検出信号線、10:入力文字レジスタ、11,2
1:状態レジスタ、12,22:RAM、13,23:次状態レジスタ、1
4,24:パターン検出判定回路、19,29:状態テーブル作成
装置、30:検出情報生成回路、110:セル、111:一致判定
回路、112:制御回路、113:状態ラッチ、114:マスクラッ
チ、115:インジケータラッチ、120:パターンバッファ。

───────────────────────────────────────────────────── フロントページの続き (72)発明者北嶋弘行神奈川県川崎市麻生区王禅寺1099番地株式会社日立製作所システム開発研究所内 (72)発明者伊東英俊茨城県日立市幸町３丁目１番１号日立ニュークリアエンジニアリング株式会社内 (56)参考文献特開昭60−211539（ＪＰ，Ａ) 特開昭63−73422（ＪＰ，Ａ) 特開昭61−52739（ＪＰ，Ａ) 特開昭63−228220（ＪＰ，Ａ) 特開昭60−105039（ＪＰ，Ａ) 特開昭53−54937（ＪＰ，Ａ) 有川節夫ほか，「テキストデータ管理システムＳＩＧＭＡについて」，情報処理学会技術研究報告Ｖｏｌ．87，Ｎｏ．65 ＰＰ．１−８，1987年９月21日

Claims

(57)【特許請求の範囲】

【請求項１】ある長さのコード長のコードで表現される
文字（記号）により構成される第１の文字列中に、指定
された第２の文字列が存在するかどうかを判定するスト
リングサーチ方法において、前記第１の文字列から複数
文字単位のデータを入力し、複数文字単位に状態遷移を
惹き起こす有限オートマトンを用いて、該複数文字単位
の入力データと現在のサーチ状態とから次のサーチ状態
を決定し、該新たなサーチ状態が検索すべき前記第２の
文字列を検出したことを表わすサーチ状態になったかど
うかを判断し、前記第２の文字列を検出した状態になっ
た場合には検出処理を行い、前記第１の文字列の入力ア
ドレスを複数文字分だけ先に更新し、前記第１の文字列
から次の複数文字単位のデータを入力する動作を繰り返
すことを特徴とするストリングサーチ方法。
【請求項２】検索すべき前記第２の文字列が与えられた
とき、該文字列に対応して、各サーチ状態に対して複数
文字の入力データが入力された場合の、次のサーチ状態
がわかる状態遷移テーブルを作成し、検索時に、複数文
字単位に前記第１の文字列中のデータを入力し、現在の
サーチ状態と第１の文字列中の複数文字単位の入力デー
タとを引数として、前記状態遷移テーブルをアクセスし
て次の状態を取得することによりストリングサーチを実
行することを特徴とする請求項１記載のストリングサー
チ方法。
【請求項３】ある長さのコード長のコードで表現される
文字（記号）により構成される第１の文字列中に、指定
された第２の文字列が存在するかどうかを判定するスト
リングサーチ装置において、前記第１の文字列を複数文
字単位にシーケンシャルに入力する手段と、複数文字単
位に状態遷移を惹き起こす有限オートマトンを用い、前
記複数文字単位の入力データと現在のサーチ状態とから
次のサーチ状態を決定し、該新たなサーチ状態と検索す
べき前記第２の文字列を検出したことを表わすサーチ状
態（パターン検出状態）とを比較する手段を有すること
を特徴とするストリングサーチ装置。
【請求項４】前記比較手段が、入力された第１の文字列
と前記第２の文字列との複数文字単位の一致不一致を判
定する手段と、前方のセルからのサーチ状態を表現する
状態信号と前記判定手段からの一致信号とから新たな状
態信号を生成し、後方のセルに伝達する手段と、前記新
たな状態信号から前記第２の文字列が検出状態になった
かどうかを判断する手段から構成されるセルを直列に接
続し、それを複数個多段に並べて構成されたものである
ことを特徴とする請求項３記載のストリングサーチ装
置。
【請求項５】前記セルを多段に接続して用いて、前記第
２の文字列のすべての部分列と前記第１の文字列の入力
文字列とを同時に比較することを特徴とする請求項４記
載のストリングサーチ装置。
【請求項６】前記比較手段が、複数文字の入力データと
現在のサーチ状態とのペア情報から、前記状態遷移テー
ブルを格納する記憶手段をアクセスし、次のサーチ状態
を取得するであることを特徴とする請求項３記載のスト
リングサーチ装置。
【請求項７】前記状態遷移テーブルを複数個格納する記
憶手段と、該状態遷移テーブルに並列にアクセスする手
段を有することを特徴とする請求項６記載のストリング
サーチ装置。
【請求項８】前記複数個の状態遷移テーブルを用いて、
複数の文字列を検索する際に、個々の文字列に対し独立
に前記状態遷移テーブルを作成する手段を有することを
特徴とする請求項７記載のストリングサーチ装置。