JPH0746362B2

JPH0746362B2 - 文字列照合方法

Info

Publication number: JPH0746362B2
Application number: JP61020239A
Authority: JP
Inventors: 治夫速水
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1986-02-03
Filing date: 1986-02-03
Publication date: 1995-05-17
Anticipated expiration: 2010-05-17
Also published as: JPS62179083A

Description

【発明の詳細な説明】（発明の属する技術分野）本発明は、テキストと呼ばれる比較的長い文字列中に、
別途与えられたパタンと呼ばれる比較的短い文字列が、
部分列として存在するか否かを判定し、存在する場合
は、存在するパタン全てを抽出する文字列照合方法に関
するものである。

（従来の技術）データ処理システムの分野では、文章等の文字列データ
の集りの中から、パタンと呼ばれる特定の部分文字列を
含むもののみを検索したり、文字列データの中に含まれ
る全てのパタンを抽出することがしばしば必要となる。

通常、１つの文字はｎビットの固定長のコードで表現さ
れるため、文字列データはｎビット単位のコードの系列
となる。

一般に文字列データは、磁気ディスク等の電子計算機の
外部記憶装置に格納されており、検索時に中央処理装置
へ１文字ずつ直列に転送される。従って、処理時間の短
縮のためには、データの転送と同時に検索を行うことが
必要となる。

第３図は従来の文字列照合機構の説明図であり、１は文
字列データが格納された記憶装置、２は文字列の照合を
行う文字列照合装置、３は文字列データ転送路、４は検
索結果を出力する信号線である。

文字列データは記憶装置１からデータ転送路３を経由し
て文字列照合装置２へ１文字ずつ直列に入力される。

文字列照合装置２では、予め記憶されているパタンとな
る部分文字列と入力されたデータを照合し、両者の一致
が検出された時点で信号線４に一致信号を出力する。

文字列照合装置２において文字列の照合を行う方法とし
て、従来より有限オートマンを用いる方法が一般に知ら
れている。

（L.A.Hollaar“Hardwarae ystem for Text Informatio
n Retrieval"ACM SIGIR 6th Conference 1983）第４図は有限オートマトンの状態遷移を表わした説明図
である。

題４図において、５はオートマトンの状態、６は状態遷
移の方向を表わし、文字列データの中の“DOG"という３
文字のパタンを照合することができる。

以下、この動作を説明する。

オートマトンの初期状態は状態（０）であり、入力文字
が“D"であると状態（１）へ遷移する。

第２図において“＃”はその他の文字を表わし、状態
（０）における入力文字が“D"以外ならば引き続き状態
（０）に留まる。

状態（１）についても同様であり、入力文字が“O"なら
ば状態（２）へ、“D"ならば再び状態（１）へ、それ以
外ならば状態（０）へ遷移する。

状態（２）において入力文字が“G"ならば状態（３）へ
遷移し、（DOG）というキーを検出したことになり、第
３図の信号線４から一致信号が出力される。

第５図は８ビットのJISコードで表現された文字列デー
タを対象とする従来の決定性有限オートマトンの実現回
路構成の説明図である。

第５図において、３は文字列データ転送路、４は検出結
果を出力する信号線、７は16ビットのアドレシレジス
タ、８と20はそれぞれ64KB（256×2⁸B）のランダムアク
セス・メモリ（RAMと略す）、９はアドレスデコーダ、1
0と21はそれぞれ８ビットのメモリレジスタ、12,14,24,
25は８ビット幅のデータ線、13は16ビット幅のアドレス
線、22は検出パタンの判別回路、23はアドレスデコーダ
出力線である。

第６図は従来の状態遷移表の構成図であり、パタンが
“ABC"と“BCD"の場合の、第５図のランダムアクセス・
メモリ８に格納される従来の状態遷移表の内容の一例を
表わしたものであり、16は16進数表現の８ビットデータ
であり、次の状態番号を表わす。

17はメモリアドレスの上位８ビット、18はメモリアドレ
スの下位８ビットである。なお、論理的にはメモリの上
位アドレス17が状態番号、メモリの下位アドレス18が文
字コードに対応しており、19はメモリの下位アドレス18
のコードによって表現されるコード対応の文字である。

第７図は従来のパタン検出判定表の構成図であり、同じ
くパタンが“ABC"と“BCD"の場合の、第５図のランダム
アクセス・メモリ20に格納される従来のパタン検出判定
表の内容を表わしたものであり、26は８ビットデータで
あり検出パタン符号を表わす。27はメモリアドレスの上
位８ビット、28はメモリアドレス下位８ビットであり、
構成としては第６図の状態遷移表と同一である。

テキストの入力文字はデータ転送路３よりアドレスレジ
スタ７の下位８ビットにセットされる。アドレスレジス
タ７の上位８ビットには初期値としてオールゼロがセッ
トされており、アドレス線３を経由してアドレスデコー
ダ９に入力される。

アドレスデコーダ９の出力は出力線23によって２方向へ
分配され、ランダアクセス・メモリ８から当該アドレス
に格納されている８ビットのデータ16が読出され、デー
タ線14を経由してメモリレジスタ10へセットされると共
に、ランダムアクセス・メモリ20からも同一アドレスに
格納されている８ビットのデータ26が読出され、データ
線24を経由してメモリレジスタ21にセットされる。

メモリレジスタ10の内容は、テキストの次の入力文字が
アドレスレジスタ７の下位ビットにセットされる時に、
データ線12を経由してアドレスレジスタ７の上位ビット
にセットされる。

メモリレジスタ21の内容は、データ線25により判別回路
22に加えられ、値がオールゼロ以外なら信号線４に検出
信号およびメモリレジスタ21の内容が出力される。

以上の動作をデータ転送路３から１文字入力される毎に
繰り返すことにより、テキストとパタンの照合処理が実
行される。

以上説明した従来の方法では、各状態において、各入力
文字に対して１回のテーブル牽引動作で次の状態を決定
するために、即ち、決定性有限オートマトンにするため
に、文字コードの全てに対応するエントリが必要であっ
た。

上記の説明例においては、各状態当り2⁸＝256エントリ
である。

また文字が16ビットのコードで表現される場合は2¹⁶＝6
5536エントリである。しかし、上記説明例でも分かる様
に、256エントリの中で初期状態以外の有意な遷移情報
が記入されているのは数エントリである。他のエントリ
には初期状態への遷移情報が記入されている。

この様に、従来方法では状態遷移表およびパタン検出判
定表を格納するRAMが有意な情報を格納するに必要な容
量以上になるという欠点があった。

（発明の目的）本発明は、状態遷移表およびパタン検出判定表を格納す
るメモリが不必要に大きくなる点を解決した、有限オー
トマトンによる文字列照合方法を提供することにある。

（発明の構成）（発明の特徴と従来の技術との差異）本発明は、状態遷移表および検出パタン判定表を格納す
るメモリとして、連想メモリ〔アドレス内蔵メモリ;Con
tent Address Memory（CAMと略す）とも呼ばれる〕を使
用することも最も主要の特徴とする。

状態遷移表において、次の状態番号が初期以外のエント
リ、または、検出パタン判定表の内容がオールゼロ以外
のエントリを有意なエントリと呼び、このエントリに対
応する状態番号と文字コードとの組のみをCAMに格納
し、対応する次の状態番号とパタン検出符号をCAMに関
連付けられたRAMの対応する番地にそれぞれ格納する。

テキストから１文字入力される毎に、現在の状態番号と
入力文字の組として、CAMに対して一致検索する。

一致エントリが有る場合は、当該エントリと関連付けら
れたRAMから、次の状態番号およびパタン検出符号を得
ることができる。

また、一致しなかった場合は、次の状態番号は初期値で
あることが分かり、別途回路でで初期状態番号を作成す
る。

従来方法では、ランダムアクセスメモリのみを使用する
ために、有意なエントリ以外も格納する必要があった
が、本発明では有意なエントリのみを格納すればよい点
が異なる。

（実施例）第１図は本発明を用いた決定性有限オートマトンの実現
回路の構成を示す一実施例のブロック図であり、８ビッ
トのコードで表現された文字列データを対象とした照合
方法の説明図である。

図において、30は1K語（１語は2B＋１ビット）のCAM、3
1はCAMの一致エントリのアドレスを作成するエンコー
ダ、32はCAMに一致エントリが無かった場合に次の状態
番号として初期値を作成する初期状態発生回路、33はCA
Mに対して一致検索を行うデータをセットするCAMアクセ
スレジスタ、34は８ビットのデータ線の選択回路、35は
17ビットのデータ線、36はCAMの一致エントリが表示さ
れるエントリ対応の一致エントリ信号線、37はCAMの一
致エントリのアドレス線、38はCAMに一致エントリが無
かったことを表示する不一致エントリ信号線、40は1K語
（１語は2B）のRAM、41はアドレスデコーダ、42はメモ
リレジスタ、43はアドレスデコーダ出力線、44は16ビッ
トのデータ線、45,46,47は８ビットのデータ線、 301はCAMの有効エントリを表示する１ビットのデータを
格納するエントリ有効性表示ビット格納域、302は８ビ
ットの状態番号格納域、303は８ビットの文字コード格
納域、 401,402は８ビットのデータ格納域で、401は次の状態番
号格納域、402はパタン検出符号格納域である。

第２図は第１図に対応する状態遷移表とパタン検出判定
表の構成図であり、与えられたパタンが“ABC"と“BCD"
である場合のCAMとRAMの内容の一例を表わしたものであ
る。

図において、311,312,313,411,412はそれぞれ301,302,3
03,401,402に格納される内容である。

311は１ビットのデータであり、“1"の時に当該エント
リが有効であることを表わす。

312は16進数表現の８ビットのデータであり、現在の状
態番号を表わす。

313は16進数表現の８ビットのデータであり、文字コー
ドを表わす。

411は16進数表現の８ビットのデータであり、次の状態
番号を表わす。

412は16審数表現の８ビットのデータであり、パタン検
出符号を表わす。

323は313のコードによって表現されるコード対応の文字
である。

次に、第２図と、従来方法の第６図、第７図との対応関
係について説明する。

現在の状態番号312は、第６図の17および第７図の27に
対応する。

文字コード313は、第６図の18、第７図の28に対応する
が、第２図の場合はパタン中にある文字コードのみが使
用されている。

次の状態番号411は、第６図の16に対応するが、第２図
の場合は、初期状態番号（00）が入っているのはパタン
検出符号412が（00）以外の場合のみである。

パタン検出符号412は第７図の26に対応する。

次に、第１図の動作について説明する。

入力文字はデータ転送路３よりCAMアクセスレジスタ33
の下位８ビットにセットされる。

CAMアクセスレジスタ33の中間８ビットには初期値とし
て（00）がセットされており、CAMアクセスレジスタ33
の上位１ビットは常に“1"がセットされる。

CAMアクセスレジスタの17ビットがデータ線35を経由し
てCAMに一致検索される。

一致エントリが有った場合は、アドレスエンコーダによ
り当語エントリのアドレスがデータ線37を経由してRAM
のアドレスデコーダ41に転送される。

アドレスデコーダでデコードされ、CAMの一致エントリ
に対応する番地から、RAM40の内容411,412が、データ線
44を経由してメモリレジスタ42にセットされる。

本発明の場合、CAMの複数のエントリと一致することが
ないことは、CAMの内容から明白である。

一致するエントリがない場合は、信号線36が全てゼロで
あることから判定され、不一致エントリ信号線38から不
一致信号が出力される。

不一致信号が初期状態発生回路32に加えられると、次の
状態番号として（00）が作成され、データ線46を経由し
て選択回路47へ転送される。

一致エントリ有りの場合は、メモリレジスタ42の上位８
ビットは、次の状態番号としてデータ線45を経由して選
択回路34へ転送される。

また、メモリレジスタ42の下位８ビットはパタン検索符
号として、データ線25を経由して判別回路22に加えら
れ、値が（00）以外なら、信号線４に、検出信号および
データ線25で転送された内容が出力される。

選択回路34は一致エントリ有りの場合は、データ線45を
選択し、一致エントリ無しの場合は、データ線46を選択
し、データ線47に出力する。

データ線47を経由したデータは、次の状態番号としてCA
Mアクセスレジスタ33の中間８ビットにセットされる。

以上の動作をデータ転送路３から１文字入力される毎に
繰り返されることにより、テキストパタンの照合処理が
実行される。

以上の説明から明らかなように、状態遷移表と検出パタ
ン判定表の有意なエントリのみをCAMに格納すればよい
ので、メモリ容量の削減ができる。

有意なエントリ以外の初期状態への遷移情報は、CAMに
一致するエントリが無かったことを判定することにより
作成している。

なお、上記説明では、初期状態番号として（00）を用い
ていたが、任意の番号を用いることも可能である。

また、文字コードは８ビットに限らないことも明白であ
る。

CAMに対して一致検索し、一致エントリがあった場合、
当該エントリのアドレスではなく、当該エントリの内容
を出力する機能を有するCAMも知られている。

この様なCAMを使用する場合は、前記実施例ではRAMに格
納している情報を、CAMの同一エントリの別格納域に格
納することにより、本発明を実施することも可能であ
る。

（発明の効果）以上説明したように、本発明は状態遷移表およびパタン
検出判定表の有意なエントリのみをメモリに格納するだ
けでよいので、次の利点がある。

一定容量のメモリに格納できるパタンの合計長の上限
が大きくなる。

一定容量のパタンの状態遷移表とパタン検出判定表を
メモリに格納する時間が短くなる。

以上の利点は、特に文字コード長が長い場合は、従来方
法との差が著しくなる。

【図面の簡単な説明】

第１図は本発明を用いた決定性有限オートマトンの表現
回路の構成を示す一実施例のブロック図、第２図は第１
図に対応する状態遷移表とパタン検出判定表の構成図、
第３図は従来の文字列照合機構の説明図、第４図は有限
オートマトンの状態遷移を表わした説明図、第５図は８
ビットのJISコードで表現された文字列データを対象と
する従来の決定性有限オートマトンの実現回路構成の説
明図、第６図は従来の状態遷移表の構成図、第７図は従
来のパタン検出判定表の構成図である。１……記憶装置、２……文字列照合装置、３……データ転送路、４……信号線、５……オートマトンの状態、６……状態遷移の方向、７……アドレスレジスタ、 8,20,40……ランダムアクセス・メモリ、 9,41……アドレスデコーダ、 10,21,42……メモリレジスタ、 12,14,24,25,35,44,45,46,47……データ線、 13,37……アドレス線、 16,26……データ、 17,27……メモリの上位アドレス、 18,28……メモリの下位アドレス、 19,29,323……コード対応の文字、 22……判別回路、 23,43……アドレスデコーダ出力線、 30……連想メモリ（CAM）、 31……アドレスエンコーダ、 32……初期状態発生回路、 33……CAMアクセスレジスタ、 34……選択回路、 36……CAMの一致エントリ信号線、 37……CAMの一致エントリアドレス線、 38……CAMの不一致エントリ信号線、 301……エントリ有効性表示ビット格納域、 302……状態番号格納域、 303……文字コード格納域、 311……エントリ有効性表示ビット、 312……状態番号、313……文字コード、 401……次の状態番号格納域、 402……パタン検出符号格納域、 411……次の状態番号、 412……パタン検出符号。

Claims

【特許請求の範囲】

【請求項１】テキストと呼ばれる比較的長い文字列中
に、別途与えられたパタンと呼ばれる比較的短い文字列
が部分列として存在するか否かを判定するために、状態番号とパタンを構成する各文字との組合せに対し
て、次の状態番号を記入した状態遷移表および状態番号
と、特にパタンの最終文字の組合せにおいては、当該パ
タン検出符号を記入したパタン検出判定表を予め作成し
ておき、テキストの１文字を入力するたびに、上記状態遷移表に
従って状態遷移しながら、パタン検出判定表を参照して
パタンの存在を判定する決定性有限オートマトンに基づ
いたテキストサーチ法において、前記状態遷移表の状態番号とパタンを構成する文字の組
合せを連想メモリに、当該組合せに対応する次の状態番
号とパタン検出符号と上記連想メモリと関連付けられた
ラダムアクセスメモリの対応する番地に、それぞれ格納
しておき、テキストの１文字を入力するたびに、現在の状態番号
と、入力された１文字を組として連想メモリに対し一致
検索し、一致エントリが有る場合は、関連付けられたランダムア
クセスから次の状態番号を得て、一致エントリが無い場
合は、次の状態番号は初期状態にリセットすることによ
り、状態遷移を行いながら、一致エントリに関連付けら
れたランダムアクセスメモリから得た当該パタン検出符
号によって、パタンの存在を判定することを特徴とする
文字列照合方法。