JPS63193228A - 文字列マツチング装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） １む、文字列を検索する文字列マツチング装置に関する
。

１　（従来の技術） 、　１文ず列に対するキーパターンのマツチングは、−
゛ｍｌ子計算機の非数値処理、特に文献等の検索におい
ては必要不可欠な処理である。文字列に対するキーパタ
ーンのマツチングとは、あるキーパターンとしての文字
列が他の文字列の中に含まれているかいないかを判定す
るものであり、完全一致を条件とする選択処理とは異な
る。例えばｅｏｆｆｌというキーパターンを含む文字列
は、ｃｏｍｐｕｔｅｒ、　ｗｅｌｃｏＩＩＩｅ、　Ｉｏ
ｃｏｍＯｔｌｏｎ等である。＊を可変長のドントケア文
字、つまり、０個以上の任意の文字数の文字列にマツチ
ングする特殊な文字と考えると、上記のＣＯＷというパ
ターンを含む文字列の検索は、＊ｃｏｍｉ：との一致を
検索するという問題になる。また、文字列に対する前方
や後方における一致を検索するには、可変長ドントケア
文字を検索対象パターンの前や後ろに付加してマツチン
グを行なえば良い。例えばｃｏｍ＊をキーパターンとし
て与えると上記の例のｃｏｍｐｕｔｅｒはマツチするが
、ｗｅｌｃｏｍｅる　　Ｐａ５ｔ　　Ｐａｔｔｅｒｎ　
　Ｍａｔｃｈｉｎｇ　　ｉｎ　　Ｓｔｒｉｎｇｓ　　（
ＳＩＡＭＪｏｕｒｎａｌ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ、
　Ｖｏｌ、６．　Ｎｏ、２　Ｊｕｎｅ　１９７７）やＭ
ｏｒｒｉｓ他によるＡ　Ｌｉｎｅａｒ　Ｐａｔｔｅｒｎ
　Ｍａｔｃｈｉｎｇして知られている。ハードウェアに
よる実現では１ｔａｓｋ１ｎ他（ＡＣＭ　Ｔｒａｎｓａ
ｃｔｉｏｎ　ｏｎ　ＤａｔａｂａｓｃＳｙｓｔｅｍｓ、
　Ｖｏｌ、８．　Ｎｏ、ｌ、　Ｍａｒｃｈ　１９８３）
によるパタニン・マツチャが提案されている。

しかしながら、Ｍｏｒｒｉｓ他によるアルゴリズムは、
パターン、文字列が共にランダム・アクセス可能な記憶
媒体上に記憶されている場合には効率が良いが、文字列
がシーケンシャルな２次記憶媒体に格納されているとき
には適用できない。このため、マツチング処理は、一旦
１時記憶媒体上に文字列を移してから行なわなくてはな
らず、効率の良い処理を行なうことができなかった。

また、Ｋｎｕｔｈ他によるアルゴリズムによれば、文字
列がシーケンシャルな記憶媒体に入っているときにも適
用できるが、ソフトウェアによる処理では十分な実行速
度を得るのが難しい。特に２次記憶に文字列が入ってお
り、それを読出している時間に処理を並列的に進めるこ
とができない。

さらに、Ｈａｓｋｉｎ他の提案したハードウェアによる
パターンマツチングは、入力文字列を受理するかどうか
でマツチングのｆ１１定を行なうオートマド−は高いが
必ずしも現実的、かつ効率的な実現方式と１．は言い難
かった。

（発明が解決しようとする問題点） は、特に人容金でシーケンシャルな記憶媒体上に　゛あ
る文字列に対するパターンのマツチングをソフトウェア
で実行するのが不可能であるか、または可能であるとし
ても、その処理速度は不十分なものであった。また、上
記のパターンマツチングをハードウェアで実行させるに
は、可変長ドントケア文字を扱うために大量のハードウ
ェアを必要とする上、効率的な処理か行なえないという
欠点を存していた。

本発明は、上記の問題点を解決するためになされたもの
で、その目的とするところは、少ないハードウェアで、
シーケンシャルな記憶媒体からの読出しと並列的に処理
を行なうことができ、高速で効率の良いマツチング処理
が可能な文字列マツチング装置を提供することにある。

［発明の構成］ 比較した結果、不一致が検出されたときに、比較を再開
する文字を効率良く決定するため、以下のようなパター
ンリワインドインデックス記憶手段とパターンアドバン
スインデックス記憶手段と制御部とを備えている。

即ち、パターンリワインドインデックス記憶手段は、前
記比較器での比較結果が不一致であった場合にパターン
文字列のどこまで戻って比較を再開するかを指定するパ
ターンリワインドインデックスを前記パターン文字列の
各文字毎に記憶する。

また、パターンアドバンスインデックス記憶手段は、前
記比較器での比較結果が不一致であった場合に前記文字
列バッファの読出しアドレスを歩進させるかどうかを示
すパターンアドバンスインデックスを前記パターン文字
列の各文字毎に記憶する。

さらに制御部は、前記比較器における比較結果が一致し
た場合には前記文字列バッファ、パターン記憶手段手段
及び前記両インデックス記憶手段の各読出しアドレスを
それぞれ歩進させ、前記比−ンアドバンスインデックス
に基づいて前記文字列バッファの読出しアドレスの歩進
／維持を決定する。

−”（作用） 検索キーとなるべきパターン文字列は、予めパターン記
憶手段に書込まれる。パターン文字列の各文字に対応し
たパターンリワンドインデックスとパターンアドバンス
インデックスは、予め各々のインデックス記憶手段に書
込まれる。人力文字列が文字列バッファにシーケンシャ
ルに人力されると、同時にマツチング処理が行われる。

入力文字列とパターン文字列とを１文字ずつ順次比較器
で比較して、比較結果が一致である場合には次の文字の
対の比較が行われる。パターンの最後の文字までの文字
のミスマツチが起こらず、比較が成功すれば、パターン
がこの文字列を含んでいることが制御部により検出され
マツチングが成功する。

マツチングの途中で不一致が検出されたら、制御部はそ
の文字の位置に対応するパターンリワイ較結果が明らか
な文字については重復して比較を行なわないようにする
ことにより効率の良い比較が行われる。

また、制御部はマツチングが失敗したときにパターンア
ドバンスインデックスに基づいて、入力文字列の読出し
アドレスを必要であれば歩進する。

この歩進は、ミスマツチを起こした文字と次に比較が再
開される文字とが同一であることが分っているときに行
われる。この場合には、入力文字列を更新させないとミ
スマツチが当然に起こってしまうからである。これによ
り、さらに効率の良いマツチングが行われる。

（実施例） 以下、図面を参照して本発明の実施例について詳細に説
明する。

第１図に本発明の第１の実施例の構成を示す。

文字列バッファ１は、外部の図示しないディスク装置な
どの２次記憶装置からシーケンシャルに送られてくる人
力文字列データを一時格納するバッ二２；− る。パターンメモリ３は、マツチングの対象となるパタ
ーンとして与えられるパターン文字列を格納する。パタ
ーンアドレスカウンタ４は、パターンメモリ３に格納さ
れたパターン文字列の読み出し用のアドレスを生成しパ
ターンメモリ３に与える。パターンリワインドインデッ
クス（以下ｒＰＲＩＪと呼ぶ）メモリ５には、次のよう
なＰＲＩ（戻り文字数）が格納されている。即ちＰＲＩ
は、パターンと入力文字列とが不一致になった時に現在
のパターンメモリ３のアドレス（パターンアドレスカウ
ンタ４に保持されている。）から相対的に何文字分だけ
前に戻ってパターンマツチングを再開したら良いかを示
す文字数であり、パターン文字列の各文字に対応して格
納されている。パターンアドバンスインデックス（以下
ｒＰＡ　ＩＪと呼ぶ）メモリ６は、やはりパターン文字
列のある文字でマツチングが失敗したときに、入力文字
列の読出しアドレスを歩進させても良いか、そのままに
しておくかを、ｒｌＪ、ｒＯＪで表示した歩進可否情報
（ＰＡＩ）をパターン文字−一される。つまり上記２つ
のインデックスメモリ５゜６からのデータは、パターン
文字列の各文字の位置に対応して読み出されるので、読
出しアドレス−は同一であり、共通のカウンタを用いる
ことができる。

加算器８は、現在のパターン文字列の読み出しアドレス
からＰＲＩを加算してパターン文字列の新しい読出しア
ドレスを作り出すための加算を行なう為のものである。

加算器９は、現在のインデックスメモリ５，６のアドレ
スにＰＲＩを加算してミスマツチの際にインデックスメ
モリ５．６の新しい読出しアドレスを計算するために用
いられる。比較器１０はパターンと文字列の現在対象と
なっている文字を一文字比較するものである。制御部１
１は上述の装置を制御する。出力バッファ１２は、マツ
チした文字列が出力として必要であれば、マツチングの
途中の文字列の先頭部分を格納するのに用いる。出力バ
ッファ１２のを効データアドレスを保持するのが出力バ
ッファカウンタ１３である。出力が文字列そのものでは
なく、助字列と、パターンメモリ３に格納されたキーと
なるパターン文字列とを比較器１０で比較して、その結
果が一致であれば制御部１１の制御によって入力文字列
及びパターン文字列の各続出し文字列を歩進させ、不一
致である場合にはパターン文字列の比較再開文字と、入
力文字列の比較再開文字とをＰＲＩ及びＦＡＩに基づい
て与えるようにしたものである。

例えばパターン文字列としてａｂｃａｂｄ、入力文字列
としてａｂａｂｃａｂｃｄａｂｃａｂｄａｃが与えられ
たとすると、このａｂｃａｂｄに対する各インデックス
は、第２図のような値になる。つまり、パターン文字列
には、その先頭から続く文字列ａｂと同一の文字列が４
文字口及び５文字口に含まれているので、これに続く６
文字口の文字ｄには、先頭から続く文字列ａｂの次の文
字ｃ　（３文字口）のアドレスを指定する−３というＰ
ＲＩが格納され゛る。その他のＰＲＩとしては、先頭の
文字ａのアドレスを示す値が設定される。

また、パターン文字列の先頭から続く文字列ａｂ行する
。図中Ｓは１文字のマツチが成功（５ａｃｃｅｓｓ　）
　Ｌ、たことを示し、Ｆは失敗（Ｆａｉｌｕｒｅ　）　
したことを示す。１回目は最初の文字ａのマツチが成功
するので、インデックスメモリカウンタ７とパターンア
ドレスカウンタ４とバッファアドレスカウンタ２とは制
御部１１によりカウントアツプされ、次のｂの文字が比
較される。

ｂもマツチするので、同様にカウントアツプが行われ、
３番目の文字の比較に移る。３番目の文字でミスマツチ
が起こるので、この時にＰＲＩメモリ５が読み出され、
３番目の文字に対応するＰＲＩ　ｒ−２Ｊが得られる。

この−２と現在のパターンアドレスカウンタ４の値とは
加算され、新しいパターンアドレスとしてパターンアド
レスカウンタ４にロードされる。インデックスメモリカ
ウンタ７も、現在のインデックスアドレスとＰＲＩとが
加算された値を新しいアドレスとして内部にロードする
。制御部１１は、ＰＡＩメモリ６の３番目の文字に対応
するＰＡＩが０（歩進ボッ回目のマツチング処理の開始
の時には、パターンアドレスカウンタ４は、パターンメ
モリ３の中の最初の文字のａを指しており、インデック
スメモリカウンタ７も最初のａの文字に対応したインデ
ックスを指していることになる。つまり、ここからの動
作は文字列の３番目の文字とパターン文字列の１番目の
文字からマツチを見ていくことになる。続けて比較を行
なっていくと、ａｂｃａｂと３〜７番目まではマツチす
るが８番目の文字でミスマツチが起こる。この時はパタ
ーン文字列の６番目の文字（ｄ）のところでミスマツチ
が起こったので、対応するＰＲｒは−３となり、ＦＡＩ
は０（歩進不可）である。従って、パターンアドレスカ
ウンタは３文字分戻され、３文字口のＣを指す。インデ
ックスメモリカウンタも対応した場所を指す。つまり、
パターンの３番目の文字から比較を再開すれば良い。

３回目の処理では、比較を進めて行くと９番口の文字列
のｄの文字でミスマツチが起こる。この回目の処理では
マツチが全文字にわたって成功するので、このマツチは
成功する。

第４図に文字のマツチが成功したときと失敗したときの
タイミングチャートを示す。マツチか成功しているとき
には、各カウンタにはインクリメントの為のカウントア
ツプパルスが１；す師部１１より与えられる。これに対
し、マツチが失敗したときには、インデックスメモリカ
ウンタ７により読み出されているＰＲＩによって求めら
れる新たなアドレスが制御部１１より与えられるロード
パルスに従ってパターンアドレスカウンタ２及びインデ
ックスメモリカウンタ７にロードされる。バッファアド
レスカウンタ２のカウントアツプパルスはＦＡＩが１の
ときのみカウントアツプされる。

第５図に第２の実施例を示す。第１の実施例においては
、ＰＲＩメモリ５、ＰＡＩメモリ６が独立のメモリであ
るとして説明したが、ＦＡＩメモリ６は１　　ｂｉｔの
情報を持てば良いので、この２つのメモリは同一のメモ
リのフィールドを割当てて用いることができる。また、
第１の実施例では、ＰＲＩメモリ５には、パターンアド
レスカウンタ４とインデックスメモリカランタフの相対
位置を格納していた。従って、ミスマツチ時に両方のカ
ウンタの更新に独立した加算器が必要であったが、ンタ
７にはこの値を直接ロードするようにした。

この時、パターンメモリ３に格納されているパターン文
字列の先頭アドレスＡｏと、この先頭の文字についての
ＰＲＩとの差を相対ペースレジスタ２２に予め書き込ん
でおくことにより、パターンアドレスカウンタ４にロー
ドする値を、上記相対ペースレジスタ２２に格納された
値とＰＲＩ部の内容を加算することで正しく計算できる
。

つまり、第２の実施例では、第１の実施例のＰＲＩメモ
リ５とＰＡＪメモリ６を同一のパターンインデックスメ
モリ２１とし、ＰＲＩを同メモリの絶対アドレスとする
ことで加算器９を省き、パターンアドレスカウンタ４の
更新値を計算するために相対ペースレジスタ２２を加算
器８に接続したものである。その他の部分の動作は第１
の実施例と同じである。第２の実施例ではＰＲＩ部にパ
ターンインデックスメモリ２１の絶対アドレスを格納す
るとしたが、その代わりにパターンメモリ３のパターン
の入っている絶対アドレスを格納す、るようにすること
もできる。この場合はＰＲＩ部；の出力が直接パターン
アドレスカウンタ４に人の値とＰＲＩ部の加算されたも
のになる。この場合の相対ペースレジスタ２の値は先の
場合の符号を変えた値となる。

次に第３の実施例につき説明する。第１、第２の実施例
ではインデックスメモリ２１をパターンメモリ３と分け
て置く例を示したが、ＰＲＩ。

ＦＡＩをパターンメモリ３に格納されたパターン文字列
の各文字に対応させた付帯情報としてのインデックスと
すれば、第７図に示すようにパターン文字列と、ＰＲＩ
と、ＦＡＩとを一つのパターン／インデックスメモリ３
１にまとめて格納することもできる。このパターン／イ
ンデックスメモリ３１は、第８図に示すように、１つの
レコードが文字部とＰＲＩ部とＰＡＩ部とで構成される
ことになる。文字の比較は文字部のデータのみを比較器
１０（、こ送ることて行ない、ミスマツチ時の次の比較
文字の選択はリワインドインデックス部のデータで行な
い、バッファアドレスカウンタ２を進めるかどうかはア
ドバンスインデックス部のデータを制御部に送りゲート
回路の信号とすること、ドレスを保持するパターン／イ
ンデックスメモリ１アドレスレジスタ３２を持つだけで
次の文字を指・′定できる。例えば５番地のｄの下でマ
ツチか失敗、Ｉ　Ｈ１゜ −したりすするとＰＲＩが２なので次の比較は２番地の
Ｃの文字から始めれば良い。

［発明の効果コ 以上説明したように、本発明によれば、簡単なハードウ
ェア構成で、２次記憶等に格納された大量の文字列に対
して、キーとなるパターン文字列をソフトウェアで行な
う場合に比べて極めて高速にサーチすることが可能にな
る。

また、例えばこの装置を２次記憶装置側に付属させる装
置とすれば、ホストとなる計算器の負荷を増やすことな
くデータの読出し時間内にパターン・マツチ処理を完了
させる事が可能になる。

【図面の簡単な説明】

第１図〜第４図は本発明の第１の実施例を示す図で、第
１図は装置の構成を示す図、第２図はパターン文字とＰ
ＲＩとＦＡＩとを各文字毎に対応して示す図、第３図は
文字列の例のパターンのマ“図で、第５図は装置の構成
を示す図、第６図はパターン文字とＰＲＩとＦＡＩとを
各文字毎に対応はパターン／インデックスメモリの内容
を示す図１・・・文字列バッファ、２・・・バッファア
ドレスカウンタ、３・・・パターンメモリ、４・・パタ
ーンアドレスカウンタ、５・・・パターンリワインドイ
ンデ。 クスメモリ、６・・・パターンアドバンスインデックス
メモリ、７・・・インデックスメモリカウンタ、８．９
・・・加算器、１０・・・比較器、１１・・・制御部、
１２・・・出力バッファ、１３・・・出）Ｊバッファカ
ウンタ、２１・・・パターンインデックスメモリ、。 ２２・・・相対ペースレジスタ、３１・・・パターン／
インデックスメモリ、３２・・・パターン／インデック
スメモリアドレスレジスタ。 出願人　工業技術院長　飯塚　幸三 人力文字列番号　　　＋　　２　３　４　５　６　７　
８　９１０１１　　＋２１３１１５＋６１７第３図 第５図

Claims (2)

【特許請求の範囲】
1. （１）入力文字列を格納する文字列バッファと、この文
   字列バッファに読出しアドレスを与えるバッファアドレ
   ス設定手段と、検索キーとなるパターン文字列を保持す
   るパターン記憶手段と、このパターン記憶手段に読出し
   アドレスを与えるパターンアドレス設定手段と、前記文
   字列バッファ及び前記パターン記憶手段からそれぞれ読
   出された文字を比較する比較器と、この比較器での比較
   結果が不一致であった場合のパターン文字列の比較を再
   開する位置を指定するパターンリワインドインデックス
   を前記パターン文字列の各文字毎に記憶したパターンリ
   ワインドインデックス記憶手段と、前記比較器での比較
   結果が不一致であった場合の前記文字列バッファの読出
   しアドレスの歩進可否を示すパターンアドバンスインデ
   ックスを前記パターン文字列の各文字毎に記憶したパタ
   ーンアドバンスインデックス記憶手段と、これら両イン
   デックス記憶手段に読出しアドレスを与えるインデック
   スアドレス設定手段と、前記比較器における比較結果が
   一致である場合には前記バッファアドレス設定手段、パ
   ターンアドレス設定手段及び前記インデックスアドレス
   設定手段に格納された各アドレスをそれぞれ歩進させ、
   前記比較器での比較結果が不一致である場合には前記パ
   ターンリワインドインデックスに応じて別記パターンア
   ドレス設定手段及び前記インデックスアドレス設定手段
   に格納された各アドレスを後退させるとともに前記パタ
   ーンアドバンスインデックスに基づいて前記バッファア
   ドレス設定手段に格納されたアドレスの歩進／維持を決
   定する制御部とを具備したことを特徴とする文字列マッ
   チング装置。
2. （２）パターンリワインドインデックス記憶手段は、前
   記パターン文字列の先頭から続く１文字以上の文字列と
   同一文字列が当該パターン文字列に含まれている場合に
   、前記先頭から続く文字列の次の文字のアドレスを、前
   記同一文字列に続く文字に対応する位置に記憶させたも
   のであり、前記パターンアドバンスインデックス記憶手
   段は、前記先頭から続く文字列の先頭と前記同一文字列
   の先頭とに対応させて前記バッファアドレスを歩進させ
   る情報が格納されているものであることを特徴とする特
   許請求の範囲第１項記載の文字列マッチング装置。