JPS63311530A - 文字列検索装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は情報処理システム、特に情報検索システムにお
ける検索方式に係り、被検索文字列中に複数の文字列の
集合が存在するか否かを一括して判別するためのもので
ある。データベース、文書ファイリングシステム、およ
びワードプロセッサなどにおける検索に利用され得るも
のである。

〔従来の技術〕

近年１文献情報や特許情報などの２次情報（書誌情報）
のみならず、１次情報（本文）をも含む大規模データベ
ース・サービスの重要性が増している。このようなデー
タベースの情報検索では。

従来、キーワードや分類コードによる方法が用いられて
きている。しかし、この方法では数十性から数百件まで
にしか絞り込めないため、検索者が最終段階で直接本文
を読んで内容を確認しなければならないという効率上の
問題がある。また１分類体系自体が年月と共に変化する
ため、常にキー９−ドや分類コードを更新しなければな
らないという問題も生じてくる。更に、キーワード付け
（インデキシングと言う）には時間がかかるため新たな
文書はバッチ処理によりかなりの量をまとめて登録する
。そのため、検索できる情報は常に一定期間の遅れを持
つという問題がある。

これらの問題に対処する一つの方法として、検索者が自
由なキーワードに基づいて文書の本文を直接参照して内
容を検索できる全文検索システムが考えられている。

一方、このような全文検索システムを日桁した文字列検
索装置がいくつか機素されている。その代表的な構成を
第１図に示し、まず、その内容について説明する。

文字列検索装置１におい′Ｃ１検索制御手段１０１は、
検索装置全体の制御と、ホストコンピュータとの通信を
行う、すなわち、ホストコンピュータから送られてくる
検索要求２０１を受は付け、これを解析し、文字列照合
手段２００と複合条件判・別手段１０３へ検索情報２０
２として送出する。

また、検索制御手段１０１はディスク制御手段１０４を
制御して、文字列記憶手段１０５に格納される文字列デ
ータ２０４を文字列照合手段２００へ送り込む。

文字列照合手段２００は、入力文字データ２０４の中に
検索要求に合致するものがあるかどうかを調べ、もし該
当するものがあれば、文字列を識別する情報２０５を複
合条件判別手段１０３へ出力する。複合条件判別手段１
０３は該文字列識別情報２０５に基づいて検索要求中に
指示された相互の位置関係などの複合条件が満足するか
否かを調べる。複合条件が満足する場合には、該当する
文書へのポインタ情報や文書内容のテキストデータを検
索結果２０６としてホストコンピュータへ返送する。

上述した文字列検索装置１の要とする文字列照合手段２
００における文字列の照合方式としては、有限オートマ
トンを用いて複数の文字列を１回の走査で検索する方法
が知られている。その代表的な方式としては、以下に説
明する２つの方法が知ら九でいる。（ニー、ブイ、二一
ホ　アンド　エム、ジエイ、コラツシツク：“エフイシ
ャントストリング　マツチング、コミュニケーションズ
ニーシーエム、１８巻、第６号、１９７５年。

Ａ、Ｖ、Ａｈｏ　ａｎｄ　Ｍ、Ｊ、Ｃｏｒａｓｉｃｋ　
：　“Ｅｆｆｉｃｉｅｎｔ　ＳｔｒｉｎｇＭａｔｃｈｉ
ｎｇ”、　ＣＡＣＭ、ＶＯＬ、１８．Ｎｃｉ６，１９７
５）　−まず、第１の方式（以後、方式１と呼ぶ）につ
いて第２図を用いて説明する。同図は、文字列デ−タの
中から、”ＡＴ３Ｘ″、　　“ＣＡＢＹ”、及び“ＤＣ
ＡＢＺ”の３つの文字列を検索する場合の有限オートマ
トンの状態遷移図である。ここで、円形はオートマトン
の状態を、矢印は状態遷移を表している。各矢印に付記
されたアルファベットはこれに対応した状態遷移が起き
る入力文字を示す、矢印４０３は初期状態への遷移を示
している。

各円形の内部に記された数値は、同状態の状態番号を示
す、方式１の特徴は起こり得る全ての状態遷移をオート
マトンに表現する点にある。したがって、各状態から状
態Ｏへの遷移も存在するが。

図が複雑になるので、これら状態Ｏ以外の状態から状態
０への遷移に関しては矢印の記載を省略している。

次に、方式１による照合動作について説明する。

このオー・トマトンの初期状態は状１ｆ／ＡＯであり、
ここから状態遷移が始まる。状ｓＯでは、入力文字が、
′Ａ”であると状態１へ遷移し、′Ｃ”ならば状態４へ
、′Ｄ”ならば状態８へ遷移する。状態Ｏにおいて“Ａ
”、“Ｂ”、及び“Ｃ”以外の文字が入力されてきた場
合は状態Ｏに戻る。状態１についても同様に、入力文字
が′Ｂ“ならば状態２へ、′Ｃ″ならば状態４へ遷移し
、ｕ　Ｄｊ＋ならば状態８に遷移し、′Ａ″ならば状態
１に再遷移し、それ以外は状態０へ戻る。状態２におい
て。

入力文字が“Ｘ”ならば、オートマトンの終点である状
態３へ移り、”ＡＢＸ”という文字列が検索されたこと
になる。以下、他の状態遷移についても同様である。

このように、方式１は全ての場合の入力文字の状態遷移
をオートマトンで表す方式である。したがって、オート
マトンの状態遷移の数が多くなり、オートマトンの作成
時間が極めて長くなるという問題がある。この方式を実
現するハードウェアにライては、特開昭６０−１０５０
３９．特開昭６０−１０５０４０に開示されている。

次に、第２の方式（以後、方式２と呼ぶ）について第３
図と第４図を用いて説明する。第３図のオートマトンは
、第２図と同様に１文字列データの中から、”ＡＢＸ”
、”ＣＡＢＹ”、及び“ＤＣＡＢＺ”の３つの文字列を
検索するためのものである。第４図は、このオートマト
ンに示されてない文字が入力された場合の遷移先を示す
フェイルテーブルの説明図である。

以下、同方式の動作について説明する。初期状態は状態
Ｏである。この例の場合、入力文字が“Ａ　”であると
状ｆｌＡ１へ遷移し、′Ｃ”ならば状態４．′Ｄ”なら
ば状態８へ遷移する。もし、ここでこれら以外の文字が
入ってきた場合は状態Ｏに戻る。一方、状態ｌでは入力
文字が“Ｂ”ならば、状態２に遷移する。ここで、もし
、同オートマトンに記述されていない“Ｂ”以外の例え
ば“Ｄ　”が入力されたときは１水力式では「フェイル
」したと言い、第４図のフェイルテーブルを参照する。

フェイルテーブルには現在の状態番号に対して再試行す
べきフェイル先の状態番号が格納されている。この場合
、現在の状態番号１に対応するフェイル先の値Ｏを得て
状ｓＯへ遷移する。

そして、該入力文字“Ｄ″′について再試行することに
より状ｆｆ！ＩＡ８へ遷移する。このような機能をフェ
イル機能と呼んでいる。

方式２ではこのフェイル機能を導入することにより、第
３図に示すように方式１（第２図）に比べて、大幅に遷
移の数を削減している。しかしながら、方式２には次の
ような問題がある６例えば。

第３図のオートマトンにおいて、入力文字列“Ｄ　ＣＡ
　Ｂ　Ｘ　”が入力された場合を考える。この場合、オ
ートマトンの状態は、０→８→９→１０→１１→６→２
→３のように遷移し１文字列“ＡＢＸ”が検索されるこ
とになる。この場合５、状態１１から状態２までの２つ
の遷移はフェイルによる遷移であり、入力“ｘ″１１文
字合処理にフェイル機能が２回も使用されたことになる
。

したがって本方式の場合、有限オートマトンの状態遷移
図が簡単になるため、オートマトンの作成時間は短くな
る利点があるが、フェイルが発生する場合には処理速度
が遅くなる欠点がある。さらに、フェイルは一つの入力
文字に対して繰り返して複数回発生することがある。し
たがって、そのフェイルの発生回数により単位時間当た
りの処理文字数が異なってくる。その結果、一定時間間
隔で入力される被検索文字列に対し、処理速度を整合さ
せるためのバッファや、同期制御８！摺等に必要になる
ため、装置や制御が複雑になるという問題がある。

〔本発明が解決しようとする問題点〕

従来の方式の、問題点をまとめると、以下のようになる
。

（１）方式１は全ての状態遷移をオートマトンで直接表
すためオートマｊ・ンの作成時間が長くなるという問題
がある。

（２）方式２はフェイル機能を用いているためオートマ
トンの作成時間は短くなるが、フェイルが発生すると処
理速度が遅くなり、さらに、単位時間当たりの処理文字
数が異なるという問題がある。

したがって、本発明の目的は、以上の問題点を解決して
、オートマトンの作成時間が短く、かつ回路制御方式が
単純になる文字列検索方式を提供することにある。

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

上記の問題点は、方式２において１文字当たりのフェイ
ル機能の使用回数に上限を設け、この上限を超えるフェ
イル機能は方式１と同様に、オートマトンで表すように
することにより解決できる。

〔作用〕

本発明の文字列検索方式においては、１文字当たりのフ
ェイル機能の使用回数に上限を設け、この上限を超える
フェイル処理は方式１と同様に。

オートマトンで表すことにより、オートマトンの作成を
方式２と同程度の時間に収めることができ。

また、方式１と同様に単位時間当たりの処理文字数を一
定にすることが可能となり、入力部が簡単で制御しやす
い文字列検索装置が実現できる。

以下、本発明方式の基本原理について説明する（以後、
方式３と呼ぶ）、第５図は本発明の基本原理を説明する
ための有限オートマトンの状態遷移図である。

同図のオートマトンは第３図に示したオートマトンと同
様に“ＡＢＸ”、“ＣＡＢＹ”、および“ＤＣＡＢＺ”
の３つの文字列を検索するためのものである。第６図に
、同オートマトンに対応するフェイルテーブルを示す、
この例では、フェイル機能の使用回数の上限を２回に限
定している。

第５１ｉｉ＋１に示したオートマド、ン及び第６図のフ
ェイルテーブルはフェイル回数を２回までに限定するた
めに、フェイル回数が３回以上になる状態１０と状態１
１に関して、そのフェイル先となる状態５と状＠６に遷
移先の追加あるいはフェイル先の変更が行なわれている
。すなわち、状態５に関しては、フェイル先状ｍ＋番号
が状態０に変更される。

また、状態６に関しては、状態３へ文字１１　Ｘ　’＃
で遷移する新たな遷移パスが付加されると共に、フェイ
ル先状態番号が状態０に変更されている。

このオートマトンは、例えば以下に示すような方法で作
成することができる。まず、従来方式２を用いて、第３
図に示したオートマトンと第４図に示したフェイルテー
ブルを作成する。次に、第４図のフェイルテーブルを調
べ、フェイル回数が２回を超える状態１０　ｊ；よび状
態１１について、フェイル回数を限定する処理を加える
。すなわら、この場合には、状態１０と状ｊｌｌｌｌの
第１回目のフェイル先である状態５と状ｓ６に着目する
。そして、状態５と状態６のフェイル回数を１回に限定
する処理を加える。まず、状態６に関しては。

状態７からの遷移起動文字“１Ｙ”とそのフェイル先で
ある状態２からの遷移起動文字１１ｘ＃が異なるので“
Ｙ”による状態３への遷移パスを新たに追加する。また
、フェイルテーブルに関しては、フェイル先状態番号を
状態２から初期状態番号のＯへ変更する６次に、状態５
に関しても同様の処理を行なう、この場合には、状態６
への遷移起動文字“Ｂ″とそのフェイル先状態１からの
遷移起動文字ｔｔ　Ｂ”が等しい、したがって、状態５
への新たな遷移パス付けは行なわない、また、フェイル
先状態番号は１から初期状態番号のＯに修正する。この
ような処理を、フェイル回数が２回を超える状態全てに
ついて繰り返すことによって、本発明におけるオートマ
トンが作成される。

フェイル回数を限定したオートマトンの作成方法に関し
ては、上に述べた以外の方法もある。この方法では、フ
ェイル回！＆を２回までに限定したオートマトンが第７
図に示すようになり、フェイルテーブルは第８図に示す
ようになる。この場合も前述の方法と同様に、まず従来
方式２を用いて第３図に示すオートマトンと、第４図に
示すフェイルテーブルを作成する。そして、フェイル回
数が２回を超える状態１０と状態１１に関し、そこから
の遷移起動文字に含まれない文字が、そのフェイル先で
ある状態５と状１６からの遷移起動文字として存在する
かどうかを調べるつもし存在する場合には、その遷移起
動文字による）°−移を着目状態の状態１０あるいは状
態１１に付は加える。

これと同時に、フェイルテーブルの遷移先状態番号は、
次のフェイル先、すなわち第２回目のフェイル先状態番
号へ変更する。この場合には、状態１１から状態７への
文字“Ｙ”による遷移が新たに付は加えられると共に、
フェイルテーブルに関しては状ＭＡ１０のフェイル先が
状態１に、状態１１のフェイル先が状態２に書き直され
ることになる。

以上、本発明におけるオートマトンおよびフェイルテー
ブルの作成方法を、フェイル回数を最大２回に限定する
場合を例にして説明したが、フェイル回数を１回に限定
する場合についても、また、フェイル先を状態Ｏに限定
しない場合でも全く同様の操作で実現できる。

以上の説明から明らかなように、このフェイル回数に上
限を設けたオートマトンの作成には、それほど複雑な処
理を必要とせず、またこの処理を要する箇所も、検索対
象となる文字列の相互関係に依存はするものの、それほ
ど多くはならない。

したがって、全体のオートマトン作成時間も、従来方式
２より多少長くなるものの、従来方式１に比較すれば大
幅に短縮される。

この本発明におけるオートマトンの作成時間の具体例に
ついて、第９図に示す。測定条件は、以下の通りである
。

（１）文字コード：　ＫＥ　Ｉ　Ｓコード、およびＥＢ
ＣＤＩＫコード（ＫＥＩＳコードは漢字を含めた文字を
２バイトのコードで表わすための日立製作所の標準文字
コードである。） （２）文字列長：１０バイト／語 （３）プログラム言１ａ：　Ｉ”ＯＲＴＲＡＭ（４）計
算機：３２ビツトＣＰＵ ただし、この場合の本１明の方式３におけるオートマト
ンは、フェイル回数を１回に限定したものとしている。

したがって、フェイル先としては５初期状態になること
になる。

本図に示されるように、キーワード数が２００個の場合
を取ると、方式１．方式３、および方式２はオートマト
ン作成に、それぞれ１５００ｍｓ。

４７０ｍ５、および３６０ｍ５を要する。

方式３は方式１に比較して約３分の１の作成時間となっ
ている。これは、方式３がフェイル処理を導入して不一
致時の遷移先を一括処理しているのに対して、方式１で
は各遷移状態について全ての遷移先を求める処理を行っ
ているためである。

方式３が方式２に比較して処理時間が約３０％増加して
いるのは、状態０以外にフェイルするものを、全てオー
トマトンでその遷移を記述するための処理が追加されて
いるためである。

このように、本発明によれば、オートマトンの作成時間
が短く、かつ、単位時間当たりの処理文字数を一定にす
ることにより、入力部が簡単で制御しやすい文字列検索
装置が実現できるようになる。

〔実施例〕

以下１本発明の原理を用いた文字列検索装置の実施例に
ついて述べる。

まず、第１の実施例である方式３−１について説明する
。本方式は、フェイル先を一つに限定せず、複数個設け
る必要がある場合に適用される方式である。すなわち１
例えば、ＥＢＣＤＩＫコードとＫＥＩＳコードが混在し
ている文字列を検索する場合などのように、複数のフェ
イル先を必要とする際に有効となる。例えば、ＥＢＣＤ
Ｉにコードで表現された文字“Ｓ６０”とＫＥＩＳコー
ドで表現された文字列“昭六十″′を検索する場合につ
いて説明する０文字列“Ｓｈｏ”はＥＢＣＤＩＫコード
で（Ｆ２Ｆ６ＦＯ）と、また文字列“昭六十”はＫＥ　
Ｉ　Ｓコードで（ｆｌＥＢｃｃＦＢＢＢＤＢＤ）と表す
される。したがって。

これらを検索するための本発明を用いた有限オートマト
ンは第１０図のよ−）に作成される。

矢印に付記されたアルファベットは、これに対応した状
態遷移を引き起こす入力文字コードを示している。ここ
で、　ＥＢＣＤＩにコードがＫＥＩＳコードへの切り替
えコート５ＨＩＦＴ−ＩＮは（ＯＡ４２）で、ＫＥＩＳ
コードからＥＲＣＩ）ＩＫコードへの切り替えコード５
ＨＩＦＴ−ＯＵＴは（ＯＡ４１）で表わされ、それらは
状態１→状態２→状態４の状態　４遷移、および状態４
　→状１．ｉ　３−ｓ状ｍ　１　（７）状ｊｌ！、１ｉ
＋！！８を引き起こす、また、初期入力コードはＥＢＣ
Ｉ）ＩＫコードで表わされているものとしている。

したがって、文字列“Ｓ６０”が入力されてきた場合に
は、初期状態１から、状態６．状態７゜状態８への順に
遷移し、最終端の状態８で被検索文字列中における文字
列“Ｓ６０”の存在が検出されることになる。また、５
ＨＩＦＴ−ＩＮコードに引き続いて“昭六十″が入力さ
れてきた場合の状態遷移は、１→２→４→９→１０→１
１→１２→１３→１４と順番に遷移し、最終端オートマ
トン状態１４で被検索文字列中における文字列パ昭六十
”の存在が検出されることになる。

この場合、例えば“８６１　″（Ｅ２Ｆ６Ｆ１）という
文字列が入力された場合には、状７！１１→状ｆＩＡ６
→状ｍ７と遷移した後１文字“１″の入力時に、状態１
ヘフエイルし、ここで該入力文字“１″に対する照合処
理を再度組り返す必要がある。また。

ＫＥＩＳコード入力モードで゛昭和六十′″（ＢＥＥＣ
ＣＦＣ２ＣＦＢＢＢＤＢＤ）という文字列が入力された
場合には、状態１１で“和″のローバイトコード（Ｃ２
）が入力された時点で、状態５ヘフエイルし、その後状
態４へ遷移する。一方、゛′昭六−″（ＢＥＢＣＣＦＢ
ＢＢＯＩＩＩＣ）という文字列が入力された場合は、状
態１２で−″のハイバイトコード（ＢＯ）、。

で−星状ＭＡ４にフェイルして、状ｊｌ１５に遷移し、
・・。

ここから次に続く“−”のローバイトコード（１７Ｃ）
・で状態４に遷移する形になる。ここで、状態５がら状
ｓ４への遷移は、ハイバイトコードで不一致が検出され
たＫＥＩＳコードのローバイトコードを処理対象から除
外し１次の文字コードの処理に移行する時のバイト調整
を行うためのものである。

すなわち、状態１はＥＢＣＤＩＫコードに対応したフェ
イル先であり、状態４はＫＥＩＳコードのローバイトコ
ードでのフェイル先で、状！ｌＡ５はＫＥＩＳコードの
ハイバイトコードでのフェイル先である。

このように、Ｅ口ＣＤＩＫコードとＫＥＩＳコードが混
在している文字列を検索するオートマトンを簡単に記述
するためには、フェイル先状態として、状態１．状態４
．および状態５の３箇所が必要となる。　このように、
フェイル先を複数持った給酸の実施例である方式３−１
のブロック図を第１１図に示す。

文字列記憶手段１０５から読み出された文字列３０１は
１文字ずつレジスタ２１１に格納される。

レジスタ２１１から出力される文字コード：１０２は１
本発明によるオートマトンの′ｉ！１移表がイ、％納さ
れている状態遷移テーブル２２０にアドレス情報として
入力される。状態遷移テーブル２２０では現在の状態番
号（以後、現状態番号と呼ぶ）３０５と文字コード３０
２から次に遷移すべき遷移先状態番号（以後、次状態番
号と呼ぶ）３０３を出力する。現状態番号の初期値とし
ては初期状態番号を設定しておく、フェイルテーブル２
７１には、フェイルが発生した場合に遷移すべきフェイ
ル先状態番号が、現状態番号に対応して格納されている
。状態遷移テーブル２２０とフェイルテーブル２７１に
は、それぞれ第１２図に示した状’Ｍ”＞Ｍ移表と第１
３図に示したフェイル先状態番号表が格納される。これ
らは、第１０図のオートマトンに対応したものである。

フェイル検出器２３０は、状態遷移テーブル２２０の出
力である第１２図に示した次状態番号３０３と現状Ｓ番
号３０５からフェイルの発生を検出すると共に、フェイ
ル検出時にはレジスタ２１１への新たな文字入力を待機
させる。フェイル検出器２３０では現状態番号３０５が
Ｏでなく、かつ遷移先状態番号３０３がＯの場合にフェ
イルが発生したものと見なす、セレクタ２４０は、フェ
イルが発生しない場合次状層番号３０３を選択し、フェ
イルが発生した場合フェイル時の遷移先状態番号である
フェイル先状態番号３０８を選択し、レジスタ２５０へ
出力する。セレクタ２４０から８力された次状態番号は
レジスタ２５０に格納され、現状態番号３０５として出
力される。レジスタ２１１は通常（フェイルが発生しな
いとき）は、レジスタ２５０と同期して文字列データを
取り込むが、フェイルが発生したときは文字列データを
保持し、フェイルが回復するまで待つことになる。照合
結果テーブル２６０には文字列の終点となるオートマト
ンの状１１（第１０図では状態８．状態１４）に対応し
て各文字列を識別するための特定のコード′が格納され
ている。

第１４図に第１０図のオートマトンに対応した照合結果
テーブル２６０の内容を示す、Ｏ以外の内容が文字列番
号を表している。すなわち、状態番号に対応した該文字
列番号がＯ以外のとき照合結果として複合条件判別手段
１０３へ送られる。

以上の動作が、第１（ｌに示したオートマトンを実行す
る形で、入力文字列を構成する各文字ごとに繰返し行わ
れることにより検索処理が実現される。

このように本実施例によれば、フェイル回数を１回に限
定した複数のフェイル先を持たせることにより、ＥＢＣ
ＤＩＫコードとＫＥＩＳコードの混在している文字列の
検索が比較的簡単なオートマトンを用いて、比較的小規
模な回路構成で実現できるようになる。

次に、第２の実施例である方式３−２について説明する
０本方式は方式３−１のフェイルテーブル２７１をコン
パクトにするためのものである。

方式３−１では、処理文字コードがＥＢＣＤＩＫコード
か、あるいはＫＥＩＳコードのハイバイトコードかロー
バイトコードかによって、それぞれフェイル先状態が３
つの状態に分かれている。そのため、フェイルテーブル
には各文字コードに対応した全ての状態にこの３つのフ
ェイル先状態番号を重複して記す形になっている。そこ
で、文字コードの［１１によってフェイル先状態を選択
できるようにすれば、この重複を省くことができ、フェ
イルテーブルのサイズを小さくすることができる。この
方法の一実施例を第１５図で説明する１文字コード判別
器２９０は文字コードの種類に応じて異なるコードを出
力し、フェイルテーブル２７３はそのコードにしたがい
フェイル先番号３０８を出力する０文字コード判別器２
９０ではＥＢＣＤＩＫコードの場合Ｏを、ＫＥＩＳコー
ドのハイバイトコードでは１を、ローバイトコードでは
２を出力する。

フェイルテーブル２７３では１文字コード判別器２９０
の出力が０のとき状態１を、１のとき状態４を、２のと
き状態５をフェイル先状態番号３０８として出力するよ
うに設定しておく、このように設定しておけば、ｔ！Ｂ
ＣＤＩＫコードおよびＫＥＩＳコードの文字列が入力さ
れても、第１０図に示したオートマトンにしたがって、
状態遷移させることができる。

このように本実施例によれば、小規模のフェイルテーブ
ルで複数の文字コードが混在する文字列の検索を行う文
字列検索”、ｉｉ’ｉが実現できる。

次に、第３の実施例である方式３−３について説明する
０本方式も、方式３−１と同様にフェイル先を一つに限
定せず、複数個設ける必要がある場合に適用される方式
である。方式３−１ではフェイルが発生したときに、状
態処理に２サイクル必要となるという問題がある０本方
式はフェイルが発生した場合でも状態処理を１サイクル
で可能とするためのものである。第１６図に本方式を実
現するためのハードウェアのブロック図を示す。

本方式は、フェイル時のフェイル先状態番号：１０８が
登録されたフェイルテーブル２７１とフェイル処理専用
の状態遷移テーブル２２１を、状態遷移テーブル２２０
とフェイル検出器２３０に付加した構成としている。こ
のフェイル処理専用の状態遷移テーブル２２１の内容は
１本来の状態遷移テーブル２２０の内容と全く同じもの
である。このような構成にすることにより、フェイルが
発生した場合にでも、状態遷移を１サイクルで処理でき
るようになる。すなわち、入力文字コードに対応する状
態遷移テーブル２２０を参照した次状態番号３０３の読
み出しと並行して、フェイルテーブル２７１からの現状
態番号３０５に対するフェイル先状態番号３０８の読み
出しと、このフェイル先状態番号３０８に基づいた状態
遷移テーブル２２１からのフェイル後の遷移先状態番号
（以後。

フェイル後状態番号と呼ぶ）３０４の読み出しを同時に
行う、そして、現状態番号３０５の読み出しの結果、・
フェイルが検出された場合に、セレクタ２４０で出力６
号を既に読み出しが終了している遷移先状態番号３０４
に切り替えるというものである。

このように本実施例によれば、フェイルが発生した場合
でも、１入力文字コードに対する状態遷移を１サイクル
で処理できるようになる。

次に、第４の実施例である方式３−４について説明する
１本方式もまた、方式３二１と同様にフェイル先を一つ
に限定せずに複数個設ける必要がある場合に適用される
方式である。上述した第３の実施例である方式３−３で
は、第１の実施例である方式３−１における問題点、す
なわちフェイル発生時の遷移処理に２サイクルを要する
という問題を解消してはいるものの、状態遷移テーブル
を２面持たなければならないという欠点がある。

本方式は方式３−３におけるフェイルテーブルをなくす
ことによって５回路規模を少しでも小さくするためのも
のである。第１７図に本方式を実現するためのハードウ
ェアのブロック図を示す。

本方式は、方式３−１におけるフェイルテーブル２７１
と状態遷移テーブル２２１を一つにまとめ、これをフェ
イル処理専用の先行フェイルテーブル２７４として設け
たものである。したがって、本フェイルテーブル２７４
の内容としては、第１２図に示した方式３−１の状態遷
移テーブルにおいて、各状態番号に対応した内容を、第
１３図に示したフェイル先の状態番号に対応する内容で
置き換えたものになる。この結果、方式３−３における
フェイルテーブル２７１は不要となる。

このように本方式によれば、フェイルの発生にかかわら
ず、全ての状態遷移が１サイクルの間に完了できると共
に、方式３−３に比較して、フェイルテーブル２７１の
分だけ回路規模を小さくすることができる。

′　　次に、第５の実施例である方式３−５について説
明する。前述した方式二３−４では、方式３−３に比較
して回路規模が小さくなってはいるものの、状態遷移テ
ーブル２２０と同じ大きさの先行フェイルテーブル２７
４を持つことになる。したがって、方式３−１や方式３
−２と比較すると約倍近い回路規模にならざるを得ない
、これは、方式３−４で先行フェイルテーブル内に全て
の状態番号において、３種類の処理文字コードに対応し
たフェイル後のフェイル後状態番号を重複して格糖して
いるためである０本方式は、この重複部分を削除するこ
とにより、先行フェイルテーブルを小さくしようとする
ものである。

この方式を実現するためのハードウェアのブロック図を
第１８図に示す１本方式では、前述した方式３−２に用
いた文字コード判別器２９０を採用し、入力文字コード
の種別で先行フェイルテーブル２７５のフェイル先を切
り替えて、処理文字コードに応じたフェイル後状態番号
番読み出す形にしている。このように本実施例によれば
、フェイル発生時にも１サイクルで遷移処理を完了する
ことができ、かつ、その制御回路の規模も、方式３−１
や方式３−２とほぼ同じ程度゛まで小さくすることがで
きる。

次に、第６の実施例である方式３−６について説明する
０本方式はフェイル先を初期状態に限定できる場合に適
用される方式である。例えば、単一の文字コードで構成
される文書を検索する場合には、フェイル先を一つにま
とめることができる。

更に、これに加えて処理速度を最大にするためにフェイ
ル回数を１回に限定すると、このフェイル先としては、
必然的に初期状態Ｏとなる。したがって、前述した方式
３−５における文字コード判別器２９０も不要となり、
かつ、先行フェイルテーブル２９５もその内の１状態分
となることになる。

本方式に用いるフェイル回数を１回に限定したオートマ
トンとしては第１９図に示したものになる。これは第３
図に示したオートマトンと同様に、”ＡＢＸ”　、”Ｃ
ＡＢＹ”　、および”Ｄ　ＣＡ　Ｂ　Ｚ”の３つの文字
列を検索するためのものである。このオートマトンは本
発明の原理説明において述べた方法を用い、フェイル回
数を１回に限定することによって作成することができる
。第３図のオートマトンと比較すると、状態６からその
フェイル先である状７！ｌＩ２における遷移起動文字“
Ｘ”による状態３への遷移パスと、状＄１１から状態３
への遷移起動文字″Ｘ”による遷移パス、および。

状態１１から状態７への遷移起動文字“Ｙ”による遷移
パスが付は加えられた形になる。

本オートマトンを実行する回路の一実施例のブロック図
を第２０図に示す０本方式では、フェイル先を状態Ｏに
限定しているため、先行フェイルテーブル２７０には状
態遷移テーブル２２０の状態０で示される内容を格納す
ることになる。第１９図に示したオートマトンに対応す
る状態遷移テーブル２２０の内容を第２１図で示す０本
方式では、前述した方式３−３．方式３−４、および方
式３−５と同様に、フェイル時の遷移先状態番号の読み
出しを先行して、次状態番号の読み出しと並行させるこ
とにより、フェイル発生時にも１サイクルで状態遷移を
処理することができる。また、回路規模としても状態遷
移テーブル２２０の１状態分を先行フェイルテーブル２
７０として持つだけで済むため、比較的小規模に収める
ことが可能となる。

次に、第７の実施例である方式３−７について説明する
０本方式も、前述した方式３−６と同様に、フェイル先
を一つに限定できる場合に適用される方式である。方式
３−６ではフェイル処理を先行して行うために、専用の
先行フェイルテーブル２７０を設け、全ての状態遷移処
理を１サイクルで済ませるようにしている。しかし、も
し、状態遷移処理が２サイクルに渡ることが許容できる
場合には、この先行フェイルテーブル２７０を取り去る
ことができる。すなわち、本方式は、先行フェイルテー
ブルを削除することによって、更に回路規模を小さくし
ようというものである。第２２図に本方式を実現するた
めのハードウェアのブロック図を示す０本方式の場合の
フェイルテーブルとしては、状態遷移テーブルの状態番
号がＯの部分に相当するものどなるため、状態遷移テー
ブル２２０の初期状態の部分を兼用することにしている
。

したがって、フェイルが検出された場合には、状態番号
出力用のレジスタ２５１をクリアして初期状態番号０に
セットし直し、ここで再び入力文字コード３０２の照合
を行うことになる。つまり。

本方式においてはフェイルが発生した場合、状態遷移処
理が２サイクルに渡ることになる。また。

レジスタ２１１は通常（フェイルが発生しないとき）は
、レジスタ２５１と同期して文字列データの取り込みを
行うが、フェイルが発生したときは新たな文字コードの
入力を中止し、現在入力中の文字コードを保持し、フェ
イルが回復するまで待つことになる。

このように本方式においては、フェイルが発生した場合
状態処理に２サイクル必要となるが、先行フェイルテー
ブルがなくなる分回路規模を小さくすることができる。

次に、第８の実施例である方式３−８について説明する
０本方式は方式３−５を複数のフィールドで構成される
文字列や１文字認識装置で作成した文字列に対しても検
索が行えるように機能を゛拡張した方式である。まず第
１に、複数のフィールドで構成される文字列に対し、各
フィールド毎に指定した文字列集合で検索を行う場合に
ついて説明する。この場合、各フィールド毎に独立した
フェイル先を設定できなければならない、すなわち。

例えば、第１フイールドに文書番号が、第２フイールド
に年号が記載された文字列を検索する場合には、第２３
図に示すようなオートマトンが必要になる０点線の矢印
はフェイル先を表わしている。

ここでは、あらかじめ定めた［セパレータ」と呼ぶフィ
ールド間区切りコード“：”を各フィールドを構成する
文字列の間に挿入し、これによってフェイル先を切り替
えるようにしている０例えば。

第１フイールドの処理が終了し、第２フィールドの処理
に移る場合、第１フイールドと第２フイールドの文字列
間に挿入されたセパレータ゛５；”の入力により、状態
】から状ｓ２へ遷移すると同時に、フェイル先も状態２
に切り替えてしまう。したがって、第２フイールド内で
照合不一致が生じた場合でも、第１フイールドのフェイ
ル先とは無関係に状ｔｌａ２にフェイルさせることがで
きる。こうすることにより、複数フィールドで構成され
る文字列の検索用オートマトンが比較的簡単な構造で記
述できるようになり、その作成時間も短くす゛ることが
できるようになる。

第２に、文字認識装置で認識した文書の文字列を検索す
る場合について説明する０文字認識装置で１００％正し
い認識結果を得ることは現状の技術では困難である。し
たがって、文字認識装置で読み取った文書には、誤りや
と識不能などの不完全な認識結果が含まれることになる
。このため、このような文書に対しては、正しい文字列
で検索できないことになる。こうした問題に対処するた
めの方法として、例えば“文字認識”という文字列を文
字認識装置で認識する際、認”という文字に曖昧性が残
る場合には、その第１候補から第４候補までをまとめて
パ文字〔設認評識〕”という形でコード化しておくもの
とする。このような文書を「曖味表記文ＷＪと呼んでい
る。この曖昧表記文書に対し検索を行う場合には、第２
４図に示したようなオートマトンが必要になる。すなわ
ち１本図のオートマトン遷移図において、９文字認識″
という文字列で検索処理を行った場合、“〔“と”〕”
で囲まれた文字群の中に″認″という文字があった時に
のみ、次の状態へ遷移し、他の文字は読み飛ばされるこ
とになる。その結果。

元の文書にあった“文字認識”という文字列が検索でき
ることになる。

以上述べた複数フィールドで構成される文字列と曖昧表
記文書に対する本検索方式３−８を実現するためのハー
ドウェアのブロック図を第２５図に示す、状態遷移テー
ブル２２０には、第２４図に示した複数フィールド検索
用のオートマトン遣移表が格納されている。

多段先行フェイルテーブル２７２は文字列と入力文字列
との不一致、すなわちフェイルが検出された場合の遷移
先状態番号（フェイル後状態番号）３０４を記述したテ
ーブルであり、処理対象フィールドに応じて複数の先行
フェイルテーブルをまとめたものである。これらの先行
フェイルテーブルは、あらかじめ指定したセパレータで
切り替えられるようにしている。セパレータの文字コー
ドはレジスタ２９３にあらかじめ格納されており、コン
パレータ２９２により入力文字コード３０２と比較され
る。セパレータと同じ文字コードが入力されたとき、カ
ウンタ２９１（初期値はｌ）がインクリメントされ、フ
ィールド番号３０７が切り替えられる。この場合の多段
先行フェイルテーブル２７２の内容を第２７図に示す、
フィールド番号１の内容は状態遷移テーブル２２０にお
ける第１フイールドの始点である状態１と同じ内容で。

フィールド番号２の内容は第２フイールドの始点である
状態２と同じ内容である。したがつ°Ｃ１第１フィール
ドの検索処理中にフェイルが発生した場合には状ａ】に
フェイルし、第２フイールドの場合には状態２にフェイ
ルできることになる。

このように多段先行フェイルテーブル２７２を採用する
ことにより、フェイル先を各フィールド毎に分離するこ
とができるため、複数のフィールドでオ、弯成される文
書検索用のオートマトンをｆＮ惧なものにすることがで
きる。

補助状態遷移テーブル２２３は、指定した文字コード以
外のコードを全て検索対象から除外する機能を実現する
ためのものである。すなわち、状態遷移テーブル２２０
に遷移先の記述されていない文字が入力された場合には
、この補助状態遷移テーブル２２３を参照して次の遷移
先を決定する。

この補助状態遷移テーブル２２３の内容を第２８図に示
す、補助状態遷移テーブル２２３には現状態番号３０５
に対応して補助次状態番号３０９が格納されている。こ
こでは、例えば状態５において、状Ｓ遷移テーブル２２
０の遷移先の記述されていない“説”や“識”などの文
字が入力されてきた場合、この補助状態遷移テーブルの
出力である状態５に再遷移することになる。すなわち、
誤認識文字を読み飛ばし指定された正しい文字に基づい
て検索が行えるようになる。

このように、補状態遣移テーブル２２３を用いることに
よって、指定外の人力文字コードに対応した遷移を簡単
なオートマトンで記述できるようになるため、曖昧表記
文書の検索への適用が容易になる。

状Ｂ遷移テーブル２２０．多段先行フェイルテーブル２
７２．補助状態遷移テーブル２２３の参照出刃は、フェ
イル検出器２３０の検出結果に応じて選択さ九、現状態
番号３０５として以後の処理の基準状態となる。１なわ
ち、状ｍ遷移テーブル２２０から参照される次状態番号
３０３が０でない場合には、この状Ｈ番号が遷移先状態
番号３０５として選択され、次状態番号３０３がＯの場
合には、補助状態遷移テーブルから参照された補助次状
態番号３０９の値により、この補助次状態番号３０９か
多段先行フェイルテーブル２７２の参照値であるフェイ
ル後状態番号３０４のどちらかが選択される。補助次状
態番号３０９が０の場合には、フェイル後状態番号３０
４が選択され。

他の場合には、補助次状態番号３０９が選択されること
になる０以上のように、３種類のテーブルの出力が、各
文字の照合処理毎に各テーブルの出力に応じて選択され
、検索処理が進められる。

このように多段先行フェイルテーブル２７２を用いるこ
とにより、複数のフィールドで構成される文字列を検索
するオートマトンが簡単に記述でき、また補助状態遷移
テーブル２２３を用いることによって、曖昧表記文書を
対象とした検索用の有限オートマトンが比較的簡単に記
述できるようになる。

以上の実施例においては、状態遷移テーブルにランダム
アクセスメモリＲＡＭを使用した場合について述べてき
たが、連想メモリＣＡＭを使用することも可能である。

第２９図に前述した方式３−６の状態遷移テーブルとし
て連想メモリＣＡＭを用いた場合の実施例を示す、第２
０図に示した方式３−６と構成が異なるのは状態遷移テ
ーブル２２２に検出信号３１０が追加されている点であ
る。方式３−６の状態遷移テーブル２２０の内容に対応
した状ｓ１１移テーブル２２２の内容を第３０図に示す
６本状Ｓ還移テーブル２２２には。

現状態番号と、ここからの遷移起動文字コードと、この
遷移先状態番号すなわち次状態番号が１組のデータとし
て同一アドレスに格納されている。＠状態番号３０５と
文字・コード３０２が入力された場合、もしこれらに一
致するデータが零状態ｙ１移テーブルに記述されている
ならば、検出信号３１０が１になり、対応した次状態番
号３０３がセレクタ２４０に出力されろ。もし、該当す
る状態番号と文字コードが格納されてないならば、検出
４３号３１０はＯになり次状態番号３０３は出力されな
い。例えば、第２９図で現状態番号３０５が状態６の場
合、文字コード３０２が“Ｘ”またはＹ”のとき検出信
号３１０は１になり、それ以外の文字コードのときは検
出信号３１０はＯになる。そして、文字コード３０２が
“ｘｎのとき次状態番号３０５は３になり、文字コード
が“Ｙ”のとき欣状態番号３０５は７になる。このよう
に、次々と遷移先の状態番号が連想メモリＣＡＭで構成
された状態遷移テーブル２２２から読み出されて照合処
理が進むことになる。

以上説明したように、連想メモリＣＡＭでもランダムア
クセスメモリＲＡＭを使用したときと同様に状態遷移テ
ーブルの機能を実現することができる。この場合、第２
１図と第３０図の比較から明らかなように極めて少ない
メモリ容量で状態遷移テーブルが構成できることになる
。

〔発明の効果〕

以上説明したように、本発明によれば１文字に対するフ
ェイル機能の使用回数に上限を設けることにより、オー
トマトンの作成時間が短く、また、単位時間当たりの処
理文字数を一定にすることが可能となり制御しやすい文
字列検索装置が実現できる。そして、処理速度が最大の
とき１サイクルで１文字の遷移処理が可能となる。また
、複数フィールドで構成される文書や、曖昧表記文書に
対する文字列検索用オートマトンを簡単に記述できるよ
うになるため、これらの文書を対象とした文字列検索装
置が容易に実現できろ。

【図面の簡単な説明】

第１図は文字検察機構の説明図、第２図、第３図は従来
の有限オートマトンによる文字検索原理を表した説明図
、第４図は従来のフェイルテープ）Ｉ／（１）説明図、
第５１Ｍ、　ｆｆ１７図、　ｍｌ　ＯＩＭ、　第１９図
、第２３図、第２４図は本発明を用いた有限オートマト
ンによる文字列検索方法の原理を表した説明図、第９図
は本発明を用いた有限オートマトン作成時間を従来方式
と比較して表わしたグラフを示す図、第１１図、第１５
図、第１６図、第１７図、第１８図、第２０図、第２２
図、第２５図、第２９図は本発明を用いた有限オートマ
トンによる文字列検索回路の実施例の構成を示すブロッ
ク図、第１２図、第２１図、雫守を一１第２６図、＠３
０図は本発明を用いた状態遷移テーブルの説明図、第１
４図は検索結果テーブルの説明図、第６図、第ｄｐ８図
、第１３図は、本発明を用いたフェイルテーブルを表し
た説明図、第２７図は、本発明を用いた先行フェイルテ
ーブルを表した説明図、第２８図は、本発明を用いた補
助状ＩＩＡ″ｆｉ′４移テーブルを表した説明図である
。

Claims (1)

1. 【特許請求の範囲】 １、コード表現された文字で構成される被検索文字列中
   に複数の検索対象文字列が存在するか否かを一括して判
   定する有限オートマトンを用いた文字列検索方法におい
   て、被検索文字と検索対象文字の照合を行い、該照合の
   結果、一致する検索対象文字が存在する場合には該有限
   オートマトンで指定される所定の状態に遷移し、一致す
   る検索対象文字が存在しない場合には、予め定めた所定
   の遷移先に遷移するフェイル処理を行い、該フェイル処
   理は一被検索文字に対して所定の上限値の回数で終了す
   ることを特徴とする文字列検索方法。 ２、特許請求の範囲第１項記載の文字列検索方法におい
   て、上記被検索文字と検索対象文字の照合処理と、該照
   合処理として不一致が検出された場合のフェイル処理と
   並行して同時に行うと共に、該不一致検出時に前記フェ
   イル処理の結果指示される状態へ遷移することを特徴と
   する文字列検索方法。 ３、特許請求の範囲第１項記載の文字列検索方法におい
   て、上記フェイル処理回数の上限値が１であることを特
   徴とする文字列検索方法。 ４、特許請求の範囲第２項記載の文字列検索方法におい
   て、上記フェイル処理機能の使用回数を１に限定したこ
   とを特徴とする文字列検索方法。 ５、特許請求の範囲第１項記載の文字列検索方法におい
   て、上記フェイル処理を行うべき状態として、複数の状
   態を定めると共に、外部からの信号によりフェイル先と
   して処理対象とすべき状態を選択できるようにしたこと
   を特徴とする文字列検索方法。 ６、特許請求の範囲第１項記載の文字列検索方法におい
   て、上記フェイル処理を行うべき状態として、複数の状
   態を定めると共に、照合処理中の被検索文字コードによ
   りフェイル先として処理対象とすべき状態を選択するよ
   うにしたことを特徴とする文字列検索方法。 ７、特許請求の範囲第５項記載の文字列検索方法におい
   て、上記フェイル処理を行うべき状態として、被検索文
   字列中に存在するあらかじめ定めた文字コードによつて
   、該文字コードに続く被検索文字列中の文字に対するフ
   ェイル先状態を選択するようにしたことを特徴とする文
   字列検索方法。 ８、特許請求の範囲第１項記載の文字列検索方法におい
   て、あらかじめ定めた文字コード以外の入力があつた場
   合、該文字コードに対応してあらかじめ定めたオートマ
   トン状態に遷移するようにしたことを特徴とする文字列
   検索方法。 ９、特許請求の範囲第８項記載の文字列検索方法におい
   て、上記あらかじめ定めた所定文字コード以外の入力が
   あつた場合の遷移先オートマトン状態として、現在の状
   態を選択するようにしたことを特徴とする文字列検索方
   法。 １０、コード表現された文字で構成される被検索文字列
   中に複数の検索対象文字列が存在するか否かを一括して
   判定する有限オートマトンを用いた文字列検索装置にお
   いて、 被検索文字から一文字を入力し、これを被検索文字とし
   て保持、出力する文字入力手段と、被検索文字と検索対
   象文字との照合時に、遷移元状態に対してあらかじめ定
   めた状態で該被検索文字と該検索対象文字との照合を行
   うフェイル処理を、あらかじめ定めた回数以内繰り返す
   だけで済むように作成した状態遷移表を、該遷移先状態
   番号と該検索対象文字コードに対する遷移先の状態番号
   として格納した状態遷移表格納手段と、 遷移先状態番号に対して、前記フェイル処理を行うべき
   状態番号を格納したフェイル先状態番号格納手段と、 前記状態遷移表格納手段の出力である遷移先状態番号と
   遷移先状態番号から被検索文字と検索対象文字の照合時
   の不一致を検出すると共に、前記文字入力手段の新たな
   入力を待機させるフェイル検出手段と、 前記状態遷移表格納手段の出力と、前記フェイル先状態
   番号格納手段の出力を入力とし、前記フェイル検出手段
   の出力に応じて一方を選択して出力する遷移先選択手段
   と、 前記遷移先選択手段の出力を一時的に保持し、これを遷
   移先状態番号として出力すると共に、本遷移元状態番号
   と該被検索文字コードに基づいて、前記状態遷移表格納
   手段から該遷移先状態番号の読み出しを行う状態番号を
   読み出し手段と、 前記状態番号読み出し手段から出力される状態番号が検
   索対象文字列を構成する最後の文字コードによる遷移先
   状態番号の場合、該検索対象文字列の識別番号を出力す
   る文字列識別手段を有することを特徴とする文字列検索
   装置。 １１、コード表現された文字で構成される被検索文字列
   中に複数の検索対象文字列が存在するか否かを判定する
   有限オートマトンを用いた文字列検索装置において、 被検索文字列から一文字を入力し、これを被検索文字と
   して保持、出力する文字入力手段と、被検索文字と検索
   対象文字との照合時に、遷移元状態に対してあらかじめ
   定めた状態で該被検索文字と該検索対象文字との照合を
   行うフェイル処理を、あらかじめ定めた回数以内繰り返
   すだけで済むように作成した状態遷移表を、該遷移先状
   態番号と該検索対象文字コードに対する遷移先の状態番
   号として格納した状態遷移表格納手段と、 前記フェイル処理の結果としての遷移先状態番号を前記
   遷移先状態番号と該被検索文字コードに対応させて格納
   したフェイル後状態番号格納手段と、 前記状態遷移表格納手段の出力である遷移先状態番号と
   遷移先状態番号から被検索文字と検索対象文字の照合時
   の不一致を検出すると共に、前記文字入力手段の新たな
   入力を待機させるフェイル検出手段と、 前記状態遷移表格納手段の出力と、前記フェイル後状態
   番号格納手段の出力を入力とし、前記フェイル検出手段
   の出力に応じて一方を選択して出力する遷移先選択手段
   と、 前記遷移先選択手段の出力を一時的に保持し、これを遷
   移元状態番号として出力すると共に、本遷移元状態番号
   と該被検索文字コードに基づいて、前記状態遷移表格納
   手段から該遷移先状態番号の読み出しを行う状態番号を
   読み出し手段と、 前記状態番号読み出し手段から出力される状態番号が検
   索対象文字列を構成する最後の文字コードによる遷移先
   状態番号の場合、該検索対象文字列の識別番号を出力す
   る文字列識別手段を有することを特徴とする文字列検索
   装置。