JPH02109167A - 文字列検索方法及び装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は文字列検索方法及び装置、更に詳しく言えば、
文献等の大量の文字列の中から特定の文字列すなわちキ
ーワードを高速に検索する方法及び装置に関するもので
ある。

〔従来の技術〕

従来、大量の文字列中から複数のキーワードを検索する
方法の有効なものとして、キーワードから状態遷移図を
作り検索すべきテキストの文字列の各文字を順次、上記
状態遷移図とつき合わせてキーワード検索を行う方法が
知られている（コミュニケーション　オブ　ニー・シー
・エム、１８゜６　（１９７５年６月）第３３３頁から
第３４０頁（Ｃｏ＋ａｍ、　ＡＣＭ。

１８、６　（Ｊｕｎｅ　１９７５）　ｐｐ、３３３−３
４０））。

上記従来技術（以下ＥＸ　Ｓ　Ａ法と呼ぶ）は、例えば
７キーワードとして、「並列」、「計算機」、「制御方
法」の３つが与えられると、第１２図（ａ）のような遷
移図を作成する。そしてテキストの各文字を順次この遷
移図とつき合わせて検索を行う。第１０図（ａ）の例で
は初期状態０にある時、入力テキスト文字が″並″′で
あれば状態１に遷移し、文字が″計″であれば状態３に
遷移し、文字が″制″であれば状態６に遷移する。状態
１にあって、テキスト文字列 状態２は最終状態であり、キーワード「並列」が検索さ
れたことがわかる。このようにＦ　Ｓ　Ａ　Ｖｊでは複
数のキーワードが検索できる効率の良い方法である。実
際のＦＳＡ法による文字列検索処理は、第１２図（ａ）
の状態遷移図を第１ｚｌｆｆｌ（ｂ）のような状態遷移
表にして第１２図（Ｃ）のようなプロゲラ１１で実現さ
れている。

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

に述のようにＦＳＡ法は優れた方法であるが、処理が逐
次的になるという問題点がある１、第１２図（ｃ）に示
すようにＦＳＡ法では初期化（＋２０３’ｌの後、テキ
ストの文字を１個入力する毎に（＋２０４）、まず現在
の状態が最終状態か否かを調べ（１２０５）。

そうであればキーワードの見つかったテキスト位置と長
さを出力する（１２０６）。そして現状態とテキスト文
字から遷移表を調べて次に遷移すべき状態を決定しく＋
２０７．１２０８．１，２０９．　！２１０．１２１１
）、状態とテキスｊ・位置を更新して（＋２１２）、次
のテキスト文字について同様の処理をくり返す。

つまりＦＳＡ法では、遷移先状態は各テキスト文字の処
理の最後（１２１２）でないと決定せず、かつ次のテキ
スト文字の処理は遷移先状態が決定しないと開始するこ
とができない。従って処理が本質的に逐次的となる。こ
のことは従来の汎用計算機ではもともと各命令は逐次的
に実行されるので欠点とはならない。しかし専用のハー
ドウェアでパイプライン／並列処理などの技術を用いて
高速化しようとした場合には、上述の逐次性により適用
できないという問題点があった。

従って、本発明の主な１］的は、大量の文字列のテキス
ト文字列情報から、パイプライン処理あるいはベクトル
計算処理等の並列処理によって、高速にキーワードを検
索する文字列検索方法及びそのための装置を提供するこ
とである。

本発明の他の目的は複数キーワードに対しても効率が良
くかつパイプライン処理などの専用ハードウェアや通常
のベクトル計算機による高速化に適した新しい文字列検
索方法と、その専用装置を提供することにある。

本発明の更に他の目的はＦＳＡ法に基づく文字列検索方
法に関して、この方法を四則・論理演算命令を備えた通
常のベクトル計算機上で高速処理する文字列検索方法を
提供することである。

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

本発明は上記目的を達成するため、テキスト文字列中か
ら、単一又は複数のキーワード文字列を検索する文字列
検索処理を、テキスト文字列の情報から、キーワード文
字列及びそれに類似する文字列とからなる候補文字列群
の情報を検出する第１のステップと、第１のステップで
得られた候補文字列群の情報からキーワード文字列に対
応する情報を選択する第２ステップを行い、特に第１の
ステップをパイプライン的処理を行うことによって大量
のテキスト文字列を高速に絞り込み、候補文字列群の情
報を高速で得て、文字検索処理全体の高速化を実現して
いる。

上記第１ステップは前処理として、検索の対象となるテ
キスト文字列に現われる全種類の文字に対して、キーワ
ード文字列の中でいかなる状態で表われるかの出現形態
情報を作る。

上記前処理後テキスト文字列の情報から各文字の情報を
順次取り出し、上記出現形態情報と照合し、個別の出現
形態情報に変換し、 同時に、現在検索中の候補文字列の長さの情報をカウン
タに保持し、 上記個別の出現形態情報と上記長さの情報を利用して、
上記順次取り出される各文字を候補文字列に加えるか否
か判定し、その判定に基づいて上記カウンタの長さの情
報を更新し、 Ｆ記判定で、上記個別の出現形態情報から検索中の文字
の情報が候補文字列の−と判別したとき、その長さ情報
及び上記テキスト文字列における位置の情報を候補文字
列群の情報として出力する。

上記出現形態情報としては、最も簡単なものは文字が、
単一又は複数のキーワード文字列に現われるか否かの１
ビツトの情報や、実施例で詳細に説明する如く、キーワ
ードの文字列の中の位置（最初、最後、中間等）の情報
、あるいはキーワード文字列群の最短キーワードの文字
数以下か否かの情報等がある。

上記第１のステップを実行する専用装置として、上記出
現形態情報を格納する記憶手段と、検索すべきテキスト
文字列の各文字情報を一定周期で入力する入力手段と、
上記各文字情報をアドレス信号に変えるアドレス手段と
、Ｉｎ記記憶手段から１一記アドレス手段で指定された
アドレスの個別の出現形態情報を得る手段、検索中の候
補文字列の長さを計数するカウンタと、上記カウンタの
値及び上記個別の出現形態情報を入力とし、　−，１：
記検出中の候補文字列の次のテキスト文字を候補文字列
に加えるか否かを判定し、上記カウンタの値を更新する
カウンタ制御手段を設けて構成される。

上記第１ステップを実行する他の実施形態は、上記出現
形態情報を出現情報ベクトルとして生成し、上記テキス
ト文字列の各文字に対して上記出現情報ベクトル内の上
記各文字に対応する出現情報を読み出しテキスト文字列
内の各文字に一意に対応する形で要素となる検出状態ベ
クトルを生成し、上記検出状態ベクトルに格納された出
現情報かを用いて、対応するテキスト文字列の各文字が
候補文字列を構成するか否かを判定する。

」：記憶の実施形態の方法は四則演算機能を持つベクト
ル計算機によって実現される。

上記第２のステップとしては従来知られている文字列検
索方法が適用されるが、従来知られている上記ＦＳＡ法
にベタ１−ル処理によって実現される。

すなわち、第１ステップで得られた候補文字列群を複数
の部分文字列とし、上記部分文字列上のどの文字が検索
処理の対象となっているかを示す検索位置情報を作り、
上記部分文字列について検索位置情報をもとに文字を読
み出して、その読み出した文字をベクトル形式の入力文
字ベクトルとして並び換え、上記各部分文字列について
検索処理の任意の時点で各部分文字列がキーワード文字
列中のどのキーワードの文字とまで一致しているかを示
す状態からなる状態ベクトルを保持し、Ｅ記各部分文字
列について上記入力文字ベクトルと上記状態ベクトルと
から新しい一致状態へと遷移するための状態遷移ベクト
ルをキーワード文字列から生成する。次に一上記状態遷
移ベクトルを用いて、上記保持された状態ベクトルと上
記入力文字ベクトルとから各部分文字列に対して状態遷
移を行い、上記状態ベグ１−ルの各要素についてキーワ
ード文字列を検出したか否かな判定する受理判定する方
法が実施される。

〔作用〕

本発明ではテキスト文字列の中にあるキーワード文字列
の存在する位置、文字数、あるいはキーワード文字の内
容を探索する方法において、検索処理が２段階で行われ
、第１段階の第１次絞り込み処理ではキーワード文字列
を含む可能性の強い候補文字群が検索される。又第２段
階の第２次絞り込み処理では上記候補文字群からキーワ
ード文字列を検索する。

第２次絞り込み処理は従来の文字列探索方法、あるいは
本発明の実施例として示した従来知られているＦＳＡ法
をベクトル処理的に行うこともできる。

第１次絞り込み処理はキーワード文字列そのものではな
く候補文字列を検索するものであり、以下の実施例に示
す如く、パイプライン動作を行う専用装置あるいはベク
トル計算機等でパイプラインあるいは並列処理が可能と
なるため、極めて高速の処理を実現することができる。

上記第１次絞り込み処理を専用装置で実現する場合、上
記記憶手段から出現形態情報を読み出すまでにテキスト
文字列の文字の読み出し、その文字を上記記憶装置のア
ドレスに変え、−上記記憶装置からの出現形態情報の読
み出す過程が１つの文字の処理について必要となるが、
出現形態情報は、その処理対象の文字がキーワード文字
列中に出現するか否か、あるいはキーワード文字列中で
どのような位置に出現するかを表わす情報であるため、
他の文字との関係を考慮することなく、−意に決定する
。従って、検索状態を表わすカウンタ値に関係なく先行
的な読み出しが可能であり、従って、相続く複数の文字
の処理を一部重複して、すなわち、１つの文字について
カウンタの値を更新中に、次の文字については出現状態
情報の読み出しを行い、更に次の文字についてはテキス
ト文字列から読み出しアドレス情報に変換する、すなわ
ちパイプライン処理を行うことができ、高速処理が実現
される。

又他の実施例である、第１次絞り込み処理をべクトル計
算機で処理する場合、テキスト文字列情報は、各文字が
キーワード文字列に現われる文字か否かの出現情報を要
素とした検出情報ベクトルに変換され、同一の検出情報
ベクトル要素の配列状態から、それが候補文字列を構成
するか（Ｆかを判定処理をベクトル処理によって行うも
のであり、上記検出情報ベクトルの生成は、−上記判定
処理に先行して独立して実行できるものであり、かつ上
記判定処理のベクトル処理は、間接アドレスに基づくベ
クトル要素の移動や、ベクｌ−ル間の差の演算の極めて
簡単な処理で並列的に行われるため高速処理が実現でき
る。

上記、出現情報を用いてベクトル処理を行う方法は、上
記第１次絞り込み処理のみでなく、上記入力テキスト文
字列が一定の条件を満たす複数の部分文字列に分割でき
るときは１分割された部分文字列から取り出された要素
をベクトル要素とするベクトル情報にして、上記複数の
部分文字列に対応してＦＳＡ法を適用することによって
、［？ＳＡ法の並列・パイプライン処理ができ、特に、
上記候補文字群を上記複数の部分文字列とみなしたとき
、上記ＦＳＡ法のベクトル処理が上記第２次絞り込み処
理に適用できる。

〔実施例〕

第１図は本発明による文字列検索方法を実施する文字列
検索装置の一実施例の構成を示す図である。本実施例は
特に複数のキーワードに対しても効率よくパイプライン
処理を行う専用装置を使用するものである。

同図において、主記憶装置１０】には検索すべき文字列
（すなわち、テキスト文字列）の情報を格納する領域１
０２．キーワード群の情報を格納する領域１４４．１４
５及び１４６．−Ｊｚ記テキストの各文字がキーワード
文字列中に出現するか否か、あるいはキーワード文字列
中でどのような位置に出現するかを示す出現形態情報を
格納する領域１０３．テキスト文字列からキーワー１く
文字列又はそれに類似する文字列（以下候補文字列群と
呼ぶ）の情報、すなわち、第１次絞り込み結果を格納す
る領域１０４、検索されたキーワード文字列の情報、す
なわち、第２次絞り込み結果を格納する領域１０５及び
プロセッサ１１８の動作を行わせるテキストサチプログ
ラムが格納される領域１０６を含む。以下、簡明のため
上記各領域に格納された情報を領域番号で示す。

テキストサーチユニット１１７はプロセッサ１１８によ
って起動され、テキスト文字列１０２．キーワード文字
列１４４．１４５．１４６及び出現形態情報１０３を入
力として、上記第１次絞り込み結果祭パイプライン処理
によって得、これを領域１０４に第１次絞り込み結果と
して格納する専用処理装置である。

第２図は説明の都合上主記憶装置１０１に格納されるデ
ータの例を示す。同図においてテキスト文字列１０２は
「行列計算法及び並列計算機の制御方法」で、キーワー
ド群を「並列」、「計算機」及び「制御方法」とする。

なお図面は簡明のため文字で示しているが、実際には２
バイトの文字コードで記憶されている。テキスト文字列
左の数字はインデックス、すなわち、テキスト文字列の
配列位置を表わす。

出現形態情報１．０３（４ビツト）はテキスト文字列に
表われる全種類の文字に対し、その各文字がキーワード
に対して、いかなる表われ方を示す情報である。領域１
０３の左側の数字は前記２バイトの文字コードを１０進
数で表わしたものである。例えば文字「並」の文字コー
ドは」０進数で表わすと１３０となり、その出現形態は
”　１．１００　”で表わされる。この各ビットの意味
については後で説明する。

前記第１次絞り込み結果１０４の左設の数字は候補文字
列の先頭文字のテキスト文字列１０２におけるインデッ
クス、石段の数字は候補文字列の長さ。

例えば第１候補文字列の（２，３）はテキスト文字列１
０２のインデックス２の文字「計」から始まる長さ３の
文字列「計算法」を指している。第２図の第１次絞り込
み結果１０４は候補文字列群は「計算法」、「並列」、
「計算機」及び「制御方法」であることを表わしている
。

第２次絞り込み結果１０５は候補文字列群の情報１０４
から、キーワードに完全に−・致したもののみを選んで
記憶したもので、数字の内容は第１次絞り込み結果の場
合と同じ表記法である。上記候補文字列群の中で「計算
法」はキーワード群１４４゜１４５、１４６にないので
雑音として除かれている。

なお、領域１０４．１０５の情報は左、右それぞれ４バ
イトのコードで表わされる。

次に、上記文字列検索装置による文字列検索処理の概要
について説明する。

第３図は本発明の文字列検索方法の処理の概要を示す。

処理ユニット１１８はテキストサーチプログラム１０６
を開始する。まず、第１次絞り込み処理ルーチン３Ｉが
コールされると、キーワード群１４４．１４５゜１４６
を入力とし出現形態情報（出現形態マツプと呼ぶ）を作
り、主記憶装置＋０１の領域】０３に格納する。この８
現形態マツプ１０３の詳細については後述する。

上記出現形態マツプ１０３が形成された後、テキストサ
ーチ命令が入力されると、処理ユニット１１８はテキス
トサーチユニット１１７を起動し、テキスト文字列１０
２．キーワー１く群１４４〜１４６．出現形態マツプ１
０３の情報を主記憶装置！０１から入力する。

サーチユニット１１７は後述の構成と動作によって、候
補文字列を検索し、その結果を領域１０４に格納する。

この処理ルーチン３１が完了すると、第２次絞り込みル
ーチン；３２がコールされる。

第２次絞り込み処理ルーチン３２はテキスト文字列１０
２．キーツー１−群１４４〜１４６と第】次絞り込み処
理結果１０４の情報を入力とし、処理ユニツＭ１８で、
前述の如き雑音を除き、最終結果を得て、これを主記憶
装置＋０１の領域３０５に格納し、テキス（・サーチ処
理を終ｒする。第２次絞り込み処理ルチン３２では、従
来の文字列検索法、本実施例ではＦＳＡ法を第１次絞り
込み結果１０４の指す各候補文字列について適用する。

第１次絞り込み処理ルーチンではテキストサーチ命令ッ
ｌ−１１７によりパイプライン的処理が行われ高速に候
補が絞り込まれる。

以下、上記実施例の各部の構成動作の詳細について説明
する。

＝２７− 第４図は上記第１次絞り込み処理ルーチン３１の内容を
示すフローチャー１−である。

処理ユニット１１８はサーチプログラム１０６に従って
、最初に初期化を行う。すなわち、プログラム変数ｍに
キーワードのうち文字数の最も短いものの長さ（この場
合、キーワード１４４．１４５．１４６のうち最短は［
並列」の２）を代入し、出現形態マツプ１０３の全エン
トりをＯにクリアし、プログラム変数Ｎにテキスト１０
２の長さ（この場合１８）を代入する（ステップ４０１
）。

次にキーワード１４４〜１４６中の各文字を調べて出現
形態マツプ１０３を作成する。具体的には各キーワード
について（ステップ佃２）、キーワード中の文字Ｃｑ（
キーワードのｑ番目の文字の意）を順次取り出しくステ
ップ４０３）　、まず０９をあるハツシュ関数ｈａｓｈ
によりハツシュし結果をプログラム変数ｊに代入する（
ステップ４０４）。ハツシュ関数ｈａｓｈのハツシュ法
はテキストサーチュニノＮＩ７中のハツシュ回路１１６
のものと同一処理を行うもので後で説明する。ハシシュ
するｌ］的は出現形態マツプの大きさをできるだけ小さ
くするためである。次に文字Ｃ９の出現形態を調べる。

はじめに文字Ｃ９の出現位置（ｑ番目）と最短キーワー
ド長ｒｎとを比較しくステップ４０５）、出現位１１ｉ
ｑがＩｎ以前ならば出現形態マツプ１０３の第ｊエント
リの第Ｏビットに“Ｉ　ＩＩをたてる（ステップ４０６
）。第２の文字Ｃ９がキーワードの先頭に出現するかを
調べ（ステップ４０７）、出現する場合には出現形態マ
ツプ］０３の第９ｊエントリの第１ビツトを１′″にす
る（ステップ４０８）。同様に文字Ｃ９がキーワドの中
間（先頭と最後以外）に出現するか（ステップ４０９）
、あるいは文字ｃｑがキーワードの最後に出現するか（
ステップ旧１）を調べ、それぞれ出現形態マツプ１０３
の第ｊエントリの第２ビツト及び第３ビツトをＬＬ　Ｉ
　１１にする（ステップ４１０゜４１２）。以上により
出現形態マツプ１０３が作成される。この手順を第５図
及び第６図を用いて第２図に示した具体例で説明する。

第５図はハツシュ回路（第１図の回路１１６と同一の機
能を持つ）の構成を示す図である。入力はＣ３−Ｃ１，
の１６ビットであり、出力はＡ。−Ａ、の１０ピノＩ〜
である。０゜〜Ｃ，，のうち出力Ａ、〜Ａ、と接続され
ていないものは無視されることを示している。ずなオ〕
ぢ、ハツシュ法どしては入力Ｃ２とＣ３のｕｌ：他論理
和（１・：ＯＲ）がＡ。となり、（、、Ｃ，、Ｃ，の各
ビン１−がＡ、、Ａ２．Ａ、に等しく、Ｃ１０−ＣＩ　
ＳビットはΔ。

〜Ａ、に等しいことになる。第６図はキーワード１４４
〜１４６中の各文字についてその文字コードとハツシュ
結果と出現形態情報とをまとめた表である。

例えば、文字「並」についてはその文字コー１−（例え
ばＫＥＩＳコード）がＣＡ、　Ｃ２であり、第５図のハ
ツシュを行うと結果は８２　（＋６進）となる（１０進
１３０）。さらに文字「並」は最短キーワード長２より
前の位置に出現し、またキーワー１〜「並列」の先頭の
文字であるので、出現形態情報の第０ビツト及び第１ビ
ツトが１となる。また、中間あるいは最後に出現するも
のでないので第２．第３ビツトは′″０″となる。従っ
て出現形態マツプ１０３の第１３０エントリは、”１１
００”となる。他のキーツー１〜文字についても同様で
あり、出現形態マツプ１０３中の第６図のハツシュ値が
示す位置にその出現形態情報４ピツ］〜が格納されてい
る。

第１次絞り込み処理ルーチン３１のステップ４０１で初
期化として出現形態マツプ１０３はオールＯにクリアさ
れているので、キーワードに出現しない文字については
対応する出現形態情報は”　ｏ　ｏ　ｏ　ｏ　”となる
。

さてステップ４０２〜４１２により出現形態マツプ１０
３の作成が終わると、テキストサーチ命令が発行される
（ステップ４Ｉ３）。

第７図はテキストサーチ命令の内容を示す図である。命
令は３２ビツトで構成され、最初の１６ビツトは命令の
種類を示すコード７Ｉであり５次の８ピッ１−は無視さ
れ１次の４ピツＩ・には３つの汎用レジスタ７４．７５
及び７６を指定する値Ｒ１であり、最後の４ビツトには
２つの汎用レジスタ７６及び７８を指定する値Ｒ２でで
ある。汎用レジスタ７４にはテキスト文字列１０２の先
頭の文字のテキスト先頭アドレスが、汎用レジスタ７５
には出現形態マツプ１０３の先頭アドレスが、汎用レジ
スタ７６には、第１次絞り込み結果１０４の先頭アドレ
スが格納されている。汎用レジスタ７７には、耐記最短
のキーワード長（プログラム変数ｍの値、本実施例のｎ
１２）が、汎用レジスタ７８にはテキス１へ文字列の長
さ（プログラム変数Ｎ　（＝１８）の値）がそれぞれ格
納されている。

処理ユニツ１−１１８は上記テキストサーチ命令を検出
すると、汎用レジスタ７４．７５．７６、７７及び７８
の値を、それぞれ信号線１３９ｃ、　＋３９ｂ、　１３
９ａ。

＋３９　ｅ及び１３９ｄを介して、テギス１−サーチユ
ニット１１７のベクトル要素フェッチ回路１５２．フェ
ッチ回路Ｉ５４．ベク１−ル要素ストア回路１５１．制
御論理回路１．　Ｉ　］へ送られ、テキストサーヂユニ
ット１１７は起動される。以後処理ユニット＋１８は制
御回路１１．１の中のテキスト制御論理回路２１１から
の完了報告信号１４０が来るまで待状態に入る。

テキストサーチユニット１１７は起動されると、カウン
タ１１２〜１１５をＯリセットするとともに主記憶装置
１０１１の出現形態マツプ１０３をフェッチ回路１５４
によりパス１２０を介して出現形態マツプ格納用ＲＡ　
Ｍ　１０９にすへて読み込む。次に主記憶装置１０１」
二のテキスト文字列１０２の処理に移る。

テキスト文字列１０２はデータバス月９及びベクトル要
素フェッチ回路１５２を介して、ベクトルフエツチされ
、フェッチデータに含まれるテキスト文字列の各文字は
データバス１５３を介してレジスタ１０８に順次セラ１
−される。レジスタ１０８にセットされたテキスト文字
（２バイト）は、信号線１２７を介してハツシュ回路１
１６に送られて、１０ピッｌ−から成る値にハツシュさ
れる。このハツシュ値がアドレス線１２８を介してＲＡ
　Ｍ　１０９の読み出しアドレスとして送られ、テキス
ト文字に対応する出現形態情報が読み出されて信号線１
２９を介して制御論理回路１１１に送られる。制御論理
回路１１１はカウンタ制御論理回路２１１〜２１４及び
ストア制御論理回路を含み各カウンタ制御論理２１１〜
２１４は現在のカウンタ群１１２．　］１３．１１．４
．１．１５の値と、信号線１２９からの出現形態情報を
もとに、現在検出中の候補文字列に読み出したテキスト
文字（レジスタ１０８の内容）を加えられるか否かを判
定し、その判定結果にもとづいて各カウンタへの更新指
示信号１５６゜１３２．１３４．１３６を送出する。ス
トア制御論理１！ｊｌ路２］、５は各カウンタ１１２．
１１３．１１４．１１５の値と出現形態情報１２９をも
とに、レジスタ１１０に格納された。

候補文字列のインデックスと、その文字列の長さとを主
記憶装置１０１にストアする要求信号＋２２を発生する
。

テキストカウンタ１１２は現在処理中のテキスト文字の
テキスト１０２内での位置ｉを示し、一致長カウンタ１
１３は現在検出中の候補文字列の長さＱを示し、有効長
カウンタ１１４はテキス１〜文字の出現形態からみてそ
のテキスト文字を候補文字列に加え得ない場合に、現在
検出中の候補文字列のうちどこ（Ｖ）までが有効な候補
文字列として出力可能かを示し、結果カウンタ１１５は
現在までにいくつ（ｋ）の候補文字列が検出済みかを示
すものである。

一つの候補文字列が検出される毎に、減算器１４１で得
られるテキストカウンタ１１２と一致長カウンタ１１３
との値の差と、有効長カウンタ１１４の値のペアがレジ
スタ１１０に信号線１２５及び１；３５を介してセント
される。セントされたデータは、データバス１５０を介
してベクトル要素ス１−ア回路１５１に送られる。ベク
トル要素ス］〜ア回路１５１は受けとったデータをデー
タバス１２＋を介して主記憶装置１０１に送出し、第１
次絞り込み結果１０４中の結果カウンタ】１５が示す位
置にス１−アする。

第１図のテキストカウンタ制御論理回路２１１゜一致長
カウンタ制御論理回路２１２．有効長カウンタ制御論理
回路２１３．結果カウンタ制御論理回路２１４、及びス
ト制御論理回路２１５はそれぞれ第８図（Ａ）、（Ｂ）
、（Ｃ）、（Ｄ）及び（ＩＩ）の真理値表で表わす機能
構成を持つ。］−記真理値表では、説明の簡りｉのため
、テキストカウンタ１１２を１゜致長カウンタ１１３を
Ｑ、有効長カウンタ１１４をＶ。

結果カウンタ１１５をに、出現形態情報１２９の第０〜
第３ピツ１〜をａ　Ｑ　〜ａ　３１最短キーワード長７
７をｍ。

テキスト長７８をＮと表わす。又、入力状態の中で、Ｎ
　＞　ｉ　、　Ｑ　”＝　Ｏ、Ｑ　＜　ｍ　Ａ　Ｋ　ｏ
　＋　Ｖ　＜　ｍ　＋は条件を表わし、これらの条件が
成立するときはＩＩ　ｉ、　ＩＩ不成立のときは１０′
″で表わす、ＩＩ　Ｘ　＋＋はこれらの条件は無視され
ることを表わす。

出力信号でＩＩ　、　Ｎｏ　Ｐ　、　５ｅｔｏ　、　５
ｅｔｌはそれぞれカウンタの値を１増すこと、変更しな
いこと。

０にセットすること、１にセットすることを表わす。

以下、第２図で示した、具体的テキスト文字列１０２か
ら候補文字列を検索する場合の制御論理回路１１１及び
カウンタ群の動作をより詳細に説明する。

第９図は各時刻にテキスト文字列＋０２の各文字を読み
込む毎の各カウンタあるいは信号の様子を示したもので
ある。

まず時刻Ｏではカウンタ群１１２〜１１５は初期状態で
いずれも０となっている。

時刻１でのカウンタ制御論理の入力状態は、Ｎ：Ｉ８．
　ｉ＝ｏであり、Ｎ＞ｉは成立するからｕ　ｉ　ｕ、Ｕ
＝Ｏも１　”　＋　Ｖ　＜ｍもＯ＜２なのでＩＩ　Ｊ、
　＋１０　（ｍ　Ａｒ　ｏはＯ＜２＆Ｏなので＋＋　１
　ｎ　、　、、、　、　ａ。

ａ３は”　ｏ　ｏ　ｏ”となっている（但し１′Δ″は
論；３６ 埋積を表わし、ａｏはａｏの否定を表わす）。

従ってテキストカウンタ制御論理２１１の項番２゜一致
長カウンタ制御論理２１２の項番】、有効長カウンタ制
御論理２１３の項番１．結果カウンタ制御論理２１４の
項番１．及びス１−ア制御論理２１５の項番」に対応す
る動作指示が行われる。すなわち、動作指示は門を＋１
更新し、Ｑ　ＨＶ　１スＩ〜ア信号１２２、及び完了報
告信号１４０はｒｒ　Ｏｎとし、ｋはそのまま更新しな
いことを示している。従って時刻１のテキス１〜文字「
行」処理の結果、テキストカウンタｊへは信号１５６を
介して＋Ｊ更新指示が出され、一致長カウンタｐ、有効
長カウンタＶには０リセツトの指示がそれぞれ信号線１
３２．１３４を介して出される。よって、各カウンタ、
ｊ、　ＨＱＩ　Ｖ　ｌｋの値は第９図時刻ｌの個所が示
すようにＪ、、０゜０．０となる。

時刻２ではテキストの次の文字「列」の出現形態情報が
読出される。文字［列Ｊのハツシュ値は４３５であり（
第６図参照）、出現形態マツプの第４３５エン１−りは
”　１００１”なので”　１００１　”がパス１２９を
介してカウンタ制御論理Ｉｌｌに送ｌ）れる。時刻２で
の入力状態は、Ｎ＞ｊは１８〉１なので１１”、Ｑ＝Ｏ
もＬＬ　］、　＋＋　、　■＜　ｍもＯ＜２なので“１
”　、Ｑ＜ｍＡａ、はａ。−１なので゛″０′″ａ工ａ
２ａ３は’００１”となる。対応する動作指示は時刻１
での項番１に対応するものと同一であり、カウンタｉの
みが＋１され、カウンタのイ直１゜Ｑ、ｖ、にはそれぞ
れ２．Ｏ，Ｏ，Ｏとなる。この意味は、ｒ列」はキーワ
ードの文字ではあるがその出現形態は”　１００１　’
″、すなオ〕ち最短キーワード長より前に出現しかつキ
ーワードの最後の文字であることを示している。　一致
長カウンタＱは現在０であるので、キーワード文字が表
オ〕れるとすればキーワードの先頭文字でなければなら
ない。従って［列Ｊは候補となり得ないので候補文字列
に加えられず、検出中の候補文字列の長さを示す一致長
カウンタの値ＱはＯのままとする。

時刻３ではテキスト文字［計」が読み込まれるが「計」
の出現形態情報は第６図に示したように”１４００”で
あり、カウンタ値１とカウンタ値Ｑが＋１され、カウン
タ値ｉ、Ｑ、ｖ、にはそれぞれ３．ｉ、Ｏ，Ｏとなる。

つまり現時点では候補文字列は未検出（Ｑ＝Ｏ）であり
、かつ「計」はキーワードの先頭に出現する文字なので
候補文字列の先頭となり得る。そこで一致長カウンタ値
Ｑを＋１して１として何らかの候補文字列が検出され始
めたことを記憶する。

時刻４ではテキスト文字「算」が読み込まれるが、文字
「算」の出現形態情報は”　１０１．０″′であり、カ
ウンタ値１とカウンタ値Ｑが＋１され、カウンタ値ｉ、
Ｑ、ｖ、にはそれぞれ４，２，０゜０となる。これは、
現時点で候補文字列を検出中（ｆｌ＝１）であったので
キーワードの中間に出現する文字［算Ｊを候補文字列に
加え得るためである。

時刻５ではテキスト文字「法ｊが読み込まれるが、文字
「法」の出現形態情報は”　ＯＯＯ１”であり、Ｎ　＞
　」は１８〉４であるから”］”、９＝０は２≠０であ
るから”Ｏ”　、ｖ＜ｍはＯ＜２であるから”　ｌ　”
　＋　Ｑ　＜　ｍ　Ａ　ａ　ｏは２≧２であるから”　
Ｏ”　＋　ａ　、ａ　ｚ　ａ　３は”　ＯＯＩ　”とな
る。従ってカウンタ値Ｑは０にリセットされ、有効長カ
ウンタ値Ｖにはト日、すなわち“３″がセットされる。

これは文字「法」はキーワードの最後に出現する文字な
ので候補文字列はこの［法」の文字を加えて１つ完結す
るからである。このように有効長カウンタ値Ｖは現在検
出中の候補文字列中でキーワードの最後に出現する文字
を発見した時にそこまでの候補文字列の長さを記憶する
ためのものである。

時刻６ではテキスト文字「お」が読み込まれるが「お」
の出現形態情報は”　ｏ　ｏ　ｏ　ｏ　”であり、ｖ＜
ｍは３≧２でＬＬ　Ｑ　ＩＩであり、　Ｑ　（ｒｎ　Ａ
　ａ　ｏは０く２△０であるから“１″となる。よって
、カウンタ値ｉとｋが＋１され、ストア信号１２２がＩ
Ｉ　ｉ　ＩＩとなり、値ＱとＶはＯになる。すなわち最
短キーワード長ｍ以上の有効長■をもつ候補文字列を検
出済みでかつ現テキスト文字は候補文字列には加え得な
いので検出済みの候補文字列（「計算法」）を第１次絞
り込み結果＋０４の第１要素としてベクトル要素ストア
回路１５１に主記憶装置＋０１に格納する。格納データ
はレジスタ１　］、　０に格納された値であり、前半４
バイトは時刻４のテキストカウンタ値１と一致長ａの差
２が、また後半４バイトには時刻５の有効長カウンタの
値３がそれぞれス１〜アされるので、第１次絞り込み結
果１０４の第Ｏ要素は（２，３）となる（レジスタ１．
１０の前半にはｊとＱの差が加算器１４＋で加算されて
レジスタ１４７で１時刻分遅延されるので１時刻４のカ
ウンタ値が反映される）。ベクトル要素ストア回路１５
１は信号線１３９ａに示された結果ベクトル１０４の先
頭アドレスと信号線１３６により示された結果カウンタ
とから、結果カウンタが指す要素の主記憶アドレスを計
算し、信号線＋５０が示すデータを信号線１２１を介し
てそのアドレスに格納する回路である。

以下同様に時刻が進むのに同期して第９図に示すように
候補文字列の検出が進み、時刻１８ではカウンタ値ｉ、
ｎ、ｖ、にはそれぞれ１８，０，４．。

３となる。ここで最後の候補文字列「制御方法」を指す
データ（１，４，４，）が第１次絞り込み結果１０４の
第３要素として格納されるとともに完了報告信号１４０
が１″′となり、処理ユニット１１８にテキストサーチ
ユニットの動作完了が伝えられる。

出現形態情報の第Ｏビット目はその文字がキーワード中
で最短キーワード長より前に出現するか否かを示してい
た。このビットが存在することにより、例えばテキスト
文字列中に、Ｆ側法」という文字列が出て来た場合にこ
の文字列を候補から除外できる。というのは「法」は最
短キーワード長２より後ろの位置（３番目）に出現する
ので、候補文字列としてはｒＨＪを検出している段階で
ｒ法ノが出現することはあり得ないとわかるからである
。このように出現形態情報はなるへく少ないビット数で
、かつなるべくキーワードに近い文字列のみを候補文字
列として検出するように工夫されている。

完了報告信号１４０を受取った処理ユニツｌｄ１８はテ
キストサーチ命令処理を完了し、第１次絞り込み処理ル
ーチン３１（第３図）のコールが完了しリターンする（
ステップ４１４）。

第１０図は第１図のテキストサーチユニットによる第１
次絞り込み処理における各部の時間関係を示す図である
。テキストサーチユニットの処理は１つの入力文字に対
してテキス１へ文字の読出しＴ（すなわち、フェッチ回
路１５３の出力からレジスタ１０８への入力）、ハツシ
ュ回路１】６によるＲＡＭ１０９のア１くレス生成Ａ、
ＲＡＭ１０９からの出現形態情報の読出しＲ２及びカウ
ンタ更新の処理Ｃが経時的に行われる。しかし、連続す
る複数の文字列に対し、第１０図に示す如くマシンサイ
クル（ｔｏ　。

１、オ□・・・・・む。、６）単位は処理が重複しパイ
プライン的に処理されるため、見かけ」−１マシンザイ
クルで１テキスト文字の処理が完了する。

次に、テキストサーチプログラム１０６は第２次絞り込
み処理ルーチン３２をコールする。

第１１１は第２次絞り込み処理ルーチン３２の構成を示
すフローチャートである。第２次絞り込み処理ルーチン
３２は第１次絞り込み処理結果１０４の各要素について
（ステップ１１）、プログラム変数’］’　ｃに各要素
が指す候補文字列を代入しくステップ１２）、Ｔｃを検
索対象テキスト文字列１４４〜１４６をキーワードとし
て従来知られている方法、ここではＦＳＡ法（第１１図
（Ｑ）参照）により文字列検索を行い（ステップ１３）
、第１次絞り込み結果＋０４内にある「計算法Ｊのよう
な雑音に除去して、第２次絞り込み結果１．０５を作成
してリターンする（ステップ１４）。ＦＳＡ法による文
字列検索は公知であり、その動作も例えばシー・ニー・
シー・エム、１８゜６　（１９７５年６月）第３３３頁
から第３４０頁（ＣＡＣＭ、　＋８゜６０ｕｎｅ　１９
７５）　ｐｐ、３３３−３４０）上記載されているので
、簡単に説明する。

第１２図は、従来知られているＦ　Ｓ　Ａ　ｉ／Ａを説
明する図で、（ａ）はキーワードに対する状態遷移図の
例で、キーワード「並列」、「計算機」、「制御方法」
の場合に、文字列の遷移な状態（丸で包んだ数字）で表
わしたものである。例えば初期状態を０とし入力文字が
「並」であれば状態Ｏは状態″１″′に１文字が「計」
であれば状態３に１文字が「制」であれば状態６に、そ
れぞれ遷移する６又状態が１のとき次の文字が「列Ｊで
あれば状態２に遷移する。もちろん入力文字がキーワー
ドにない文字、あるいはキーワードの文字列と異なった
順で入った時は状態はＯにリセッ１−される。

（ｂ）図は、上記（ａ）の状態遷移図を信号処理に適用
できるようにした状態遷移表である。

ＦＳＡ法では、（ｃ）図に示す如く、初期処理として、
状態遷移表を作成しく１２０３）、テキスト文字の１個
を入力する毎に（１２０４）、現在の状態が最終状態（
キーワードの最後の文字の入力）であるか否かを調へ（
＋２０５）、最終状態であればそのテキスト文字の位置
とキーワード長さを出力する（１２０６）、そして現状
態とテキスト文字から状態遷移表（ｂ）を調べ、次に遷
移すべき状態を決定しく１２０７．１２０８．１２０９
．１２＋０．１．２＋１．）、状態とテキスト位置を更
新（１１１２）、次のテキスト文字について同様の処理
をテキスト文字の処理の最後まで繰り返す。

上記公知の［パＳへ法を１本発明の文字列検索方法の第
２次絞り込み処理に適用する場合、入力テキスト文字列
（第１２図（ｃ）ステップ１２０４）とし。

て、第１次絞り込み結果１０・１の要素、すなオ）ち候
補文字列の先頭文字のテギスト文字列におけろイ◇Ｗ（
インデックス＝１、）及び候補文字列の長さ（字数：ｓ
）による文字をプログラム変数゛１゛Ｃとして、Ｌから
Ｉ；　＋　ｓ　−１の文字を順次入力ぐる。

各文字についての文字列検索処理は第１２図（（））の
プログラムステップ１２０５〜１２１２を実行すること
によって行う。

第２次絞り込み処理ルーチン３２が完ですると、目的と
していた最終結果＋０５が得られるのでテキストサーチ
プログラム１０６が完ｒする（ステップ３３）。

本実施例ではテキスト１０２の格納手段と１１．て主記
憶装置１０１を用いたが、テキストは順次読み出しであ
るので、磁気ディスク装置や磁気テープ装置でも良いこ
とは明らかである。

また、本実施例では文字コードを２パイ１−としたが、
】バイ１〜コー１くでも差し支えない。但し、１バイト
コードの場合（例えば■ζＢＣ（Ｕ　ｒ　Ｃコトなど）
は、第１次絞り込み処理で検出される候補文字列の址が
多くなり、第２次絞り込み処理での負荷が増大するＩＩ
Ｉ能性がある。これは例えばｌバイ（・コードで表現可
能な英字は２６種しかないのでキーワードが多くなると
ほとんどの英字がキーワード中に出現してしまい（２バ
イｌ−コードが必要な漢字はキーワードが増えてもキー
ワード中に出現する漢字群の、全漢字に対する割合は小
さい）、テキスｉ−中の多くの文字列がキーワー１くと
類似と判断されるからである。

この問題は１バイ１−コードの文字については。

連続する２バイトを１文字として扱うことにより解決で
きる。例えば英単語”ｐａｒａｌ、１．ｅｌ”ではＰａ
ＬＬ８％Ｉ　、　　ＬＬｒａ、　　ＬＬａ］′Ｔ　、　
　ＬＬ　　ＩＩ　、　　１ｌｌｅＩ＋及び月 ｒｒ　ｅｌ　＋″の７つの文字から成る列と考えて他は
本実施例と全く同じ処理を行えば良い。これについては
後述する。

ハツシュ回路１１６は入力２バイトを１０ビツトに圧縮
するものである。むろんより少ないビットに圧縮すれば
ＲＡＭ＋０９の容量を小さくできるが、反面、異なる文
字のハツシュ結果が同じ値となる（一般に衝突と呼ばれ
ている）確率が大きくなり、やはり第１次絞り込み結果
１０４中の雑音の量を増加させる。

本実施例での出現形態情報は４ビツトとしたが、回路簡
単化のため簡帖化することも考えられる。

例えば第Ｏビットは省略できる（むろん雑音量は増大す
る可能性がある）。また、最小構成としては、その文字
がキーワード中に出現するか否かのみを示す１ビツトだ
けにしても良い。この場合、有効長カウンタ１１４は不
要であり、カウンタ制御論理１　］、、　１では、キー
ワード中に出現する文字が連続して現われる毎に一致長
カウンタ１１３を＋１し、キーワード中に出現しない文
字が表われた時に。

一致長カウンタ１１３が最短キーワード長２０７以−ｈ
であれば候補として現在検出中の文字列を出力し、そう
でなければ出力しないようにすれば良い。従って回路が
大幅に簡単化されるが、この場合も雑音量は一般に増加
する。

次に１本発明による文字列検索方法をベクトル演算処理
によって行った実施例について説明する。

ベクトル演算処理は、ベクトルデータ、すなわち、一定
間隔で配列された要素のデータ群、の各要素毎の並列演
算、及びパイプライン処理を行うもので、四則論理演算
及び移動命令を備えた通常のベクトル計算機（例えば日
立製作所説Ｓ　８］０７レイプロセツサシステム）によ
って実施される。文字列検索においては文字列の各文字
のデータ、例えば、文字コート、文字の出現情報、ある
いは文字列における位置情報がベクトルデータのベクト
ル要素となる。以下簡明のためベクトルデータ、ベクト
ル要素は単に「ベクトル」、［要素Ｊと呼ぶ。

第１３図は前記候補文字列を検索する第１次絞り込み処
理の手順を示したフローチャー１−　Ｐ　Ａ　Ｄ（Ｐｒ
ｏｇｒａＩＩＩＡｎａｌｙｓｉｓ　Ｄｉａｇｒａｍ）で
あり、処理ベクトルデータの流れを示した第１４図を必
要に応して参照しながら説明する。なお第１１図のベク
トルデータは、記憶装置、あるいはベクトルレジスタに
格納されるデータであり、縦方向がそれぞれ］つのベク
トルを構成し、１つのます目は要素を表わす。

第１次絞り込み処理は、第１４図に示す検索キーワード
群を表わすキーワードベクトルＫＥＹと、テキスＩ−１
’　ＥＸ　Ｔを入力して、キーワー１〜あるいはこれに
類似する候補文字列のテキス１〜にでの位置を示す先頭
位置ベクトルＴＯＰと長さを示す候補長ベクトルＬＮＧ
を出力するプログラムで実現される。プログラムとその
処理対象である上述の各データはいずれも主記憶装置に
格納され、必要に応じてベクトルレジスタにロートされ
、演算をうける。

以下処理の詳細について説明する。

第１次絞り込み処理ルーチンを起動する（＋３００）と
、初期化が行われる。すなわち、プログラム変数Ｍ　Ｉ
　Ｎ　Ｋ　Ｌにキーワードのうち最も短いものの長さ（
第１４図の例ではキーワード群ＫＥＹのうち最短は”　
Ｔ　Ｅ　Ｘ　Ｔ”の４）を代入し、出現情報ベクトルに
、ＷＤの全エントリ１０クリアし、プログラム変数Ｎに
テキストベクトル’ｒ　Ｅ　Ｘ　Ｔの長さ（この場合は
２５）を代入する（ステップ１３０１）。

これらの長さのデータはテキスト文字、キーワード文字
の入力時に得られ、レジスタ（図示せず）上記録される
。次にキーツー１〜ＫＥＹ中の各文字を調べて出現情報
ベクトルＫＷＤを作成する。１１体的には、各キーワー
ドについて（ステップ＋３０２）　。

キーワードベクトルの文字Ｃｑ（キーワードの第ｑ文字
目の、意）を順次取り出しくステップ＋３０３）。

出現情報ベクトルＫＷＤの第Ｃ９エン１−りに１を代入
する（ステップ１３（１４）。以上により出現情報ベク
トルＫ　Ｖｔ’　Ｄが作成される。この手順を第１４図
を用いて具体例でみることにする。キーワードベクトル
の最初のキーワード”　Ｓ　Ｅ　Ａ　ＲＣＨ”について
、文字Ｓはその文字コード（ＥＢＣＤＩｉＫコード）が
”Ｅ２（、、）”であり、１０進数では２２６である。

従って出現情報ベクトルに、　Ｗ　ＩＪの第２２６エン
トリの要素を１にする。他のキーワード文字についても
同様であり、各文字に対応するエン１−りに１が代入さ
れる。前述のように、出現情報ベクトルＫＷＤは初期化
ステップ１３旧で全要素がＯにクリアされているので、
キーワードに出現しない文字については対応する出現情
報はＩｆ　ＯＩＪのままとなる。

さらに検出状態ベクトルＭＳＫＩの先頭と最終の要素を
０にセットする。これは、検出状態ベクトルより、候補
文字列を識別するステップ（１３０６）のためであり、
詳細は後述する。以上で初期化のステップが完了する（
ステップ１３０１）。

さて、ステップ１３０２により、出現情報ベクトルＫＷ
Ｄの作成が終わると、テキストベクトルＴＥＸＴより候
補文字列を検出する処理が行われる（ステップ１３０５
〜１３１４）。

検出の第１ステップとして、検出状態ベクトルＭＳＫＩ
の生成がなされる。すなわち、テキス１〜ベクトルＴＥ
ＸＴの各要素について、その値が読み出され、読み出さ
れた各要素（１要素がテキストの１文字に対応している
）の値から出現情報バク１ヘルの対応する要素を参照し
て各要素（つまり、テキスト中の各文字）に対する出現
情報を検出状態ベクトルＭＳＫＩに格納する（ステップ
＋３０５）。

この演算は、間接アドレスに基づくベクトル要素の移動
であり、通常のベクトル計算機に備えられた命令で実現
される。以上の処理により、検出状態ベクトルＭＳＫＩ
には、テキスト中の各文字についてその文字がキーワー
ド内に出現する文字であるか否かが（この例では、出現
する場合が」。

出現しない場合はＯである）、テキス１〜ベクトルの各
要素と１対１に対応する形で格納されることになる。第
１４図の例で言えば、テキストベクトルＴ　Ｅ　Ｘ、　
Ｔの第１要素から第６要素の表わす文字列”　Ｓ　Ｅ　
Ａ　ＲＣＨ”については、各文字がキーワードに含まれ
る文字からなっているので、検出状態ベクトルＭ、　Ｓ
　Ｋ　１の第１要素から第６要素に格納される値は１で
ある。以下のステップでは、この検出状態ベクトルＭ　
Ｓ　Ｋ　１．　（１４０４）を走査して、キーワード内
に出現する文字が最短キーワード長ＭＩＮＫＬ以上連続
して表われる（すなわち、検出状態ベクＩ〜ルの要素に
ついて、その値が１であるような要素が連続して表われ
る）場合に、その文字から構成される文字列を候補文字
列として検出し、その位置情報を結果ベクトル（ＴＯＰ
。

ｉ　ＮＧ）として出力する。更に詳しく説明する。

まず、検出状態ベクトルＭＳＫｉから重複要素の検出を
行う。すなわち、検出状態ベクトルＭＳＫ１の各要素Ｍ
ＳＫＩ（Ｉ）（ここで、■は要素番号である）に対し、
１つ前の要素ＭＳＫＩ（１１）との差をとり、この値を
区切り位置ベクトルＭＳＫ２の第１番目の要素ＭＳＫ２
（１）に格納する。この演算はベクトル間の差をとる通
常のベクトル命令で実現される。また、前述の初期化ス
テップ（＋３０５）で、出現状態ベクトルＭＳＫ＋の第
０番目の要素と、第６＋１要素の要素をＯで初期化した
のは、このステップ（＋３０６）に備えたためである。

以」―、検出状態ベクＩ−ルＭＳＫＩの要素と区切り位
置ベクトルＭＳＫ２との要素は一意対応で演算される。

そこで検出状態ベグトルＭＳＫ１内で１の値をもつ要素
が連続する場合に、その連続する要素列の先頭要素ＭＳ
ＫＩ（１）（ただし■は要素番号である）に対応する区
切り位置ベクトルＭ、　Ｓ　Ｋ　２の要素ＭＳＫ２（Ｔ
）の値は■となり、同様に連続する要素列の最終要素Ｍ
ＳＫＩ（Ｊ）（ただしＪは要素番号である）に対応する
区切り位置ベクトルＭＳＫ２の要素ＭＳＫ２（Ｊ）の１
つ後の要素ＭＳＫ２（Ｊ＋１）の値は−１となる。第１
４図の例では、テキストベクトルＴＥＸＴの先頭の単語
”　Ｓ　Ｅ　Ａ、　ＲＣＨ″について、その先頭文字Ｉ
Ｉ　Ｓ　Ｉ＋の格納される要素の番号は１であり１区切
り位置ベクトルＭＳＫ２の第１要素の値は１となる。ま
た最後の文字”　Ｈ’″の格納される要素の番号は６で
あり１区切り位置ベクトルＭＳＫ２の第６＋１要素の値
は−１となる。

この結果、区切り位置ベクトルＭ　Ｓ　Ｋ　２　（＋４
０６）を走査して、各要素の値を検査することにより、
検出ベクトル内に出現する値］が連続する要素の列に対
して、その先頭と最終の要素の位置が検出される。また
前述のように、検出状態ベクトルＭＳＫＩの要素とテキ
ストベクトルＴＥＸＴの要素は一意に対応している。そ
こで、区切り位置ベクトルＭＳＫ２の各要ＭＭｓＫ２（
Ｉ）についてその要素の値が」であれば、その要素に対
応するテキストベクトルＴ　Ｅ　Ｘ、　Ｔの第１要素は
候補文字列の先頭要素であるから、候補文字列の先頭要
素の位置を示す要素番号■を先頭位置ベクトルＴＯＰと
して記憶装置に格納する（ステップ１３０７．１３０９
＞。

次に、区切り位置ベクトルＭＳＫ２の各要素についてそ
の要素の値が−１であれば、テキストベクトルＴ　Ｅ　
Ｘ、　Ｔの第１−１要素は候補文字列の最終要素である
から、候補文字列の最終要素の１つ後の要素の位置を示
す要素番号Ｉを終了位置ベクトルＢＴＭとして記憶装置
に格納する（ステップ１３０８、１３１０）。

以上の処理について、ステップ１３０７．１３０９を例
にとり、実際のベクトル命令列として如何に実行がなさ
れるかを説明する。検出状態ベクトルとスカラ値である
１をベクトル比較命令により比較し、先頭位置マスクベ
クトルＭ１を生成する（ステップ１３０７）。先頭位置
マスクベクトルには、検出状態ベクトルＭＳＫＩの値が
１である要素について、対応する位置に１が格納される
。次に、先頭位置マスクベクトルＭ１を用いて、位置ベ
クトルＩ）ＯＳの要素のうち、マスクの値が１であるも
のを、先頭位置ベクトルＴＯＰに格納する（ステップ１
３０９）。このステップについても、間接アドレスに基
づくベクトルの要素移動を行う通常のベクトル命令によ
り実現することができる。ステップ１．３０８．１３］
０についても同様に１通常のベクトル命令による実行が
可能である。

例えば、第１４図の例でいえば、区切り位置ベクトルＭ
、　Ｓ　Ｋ　２の第１要素は１であるから、先頭位置ベ
クトルＴＯＰの第１要素には１が格納され、区切り位置
ベクトルＭＳＫ２の第７要素は−」−であるから、終了
位置ベクトルＢＴＭの第１要素には７が格納される。

以上のステップにより、テキストベクトルＴＥＸ、Ｔ内
の候補文字列の先頭文字の位置が先頭位置ベクトル゛Ｉ
”　ＯＰと、候補文字列の最後の１つ後の位置が終了位
置ベクトルＢＴＭとして記憶装置に格納される。この候
補文字列の先頭位置と終了位置を検出するステップは、
各々区切り位置ベクトルＭＳＫ２をサーチして特定の要
素値（具体的にはＩＩ　Ｉ　１１と１１１１１である）
を検出する処理であり、要素毎に各々独立のベクトル命
令で並列に実行される。また、検出状態ベクトルＭＳＫ
Ｉから区切り位置ベクトルＭＳＫ２を生成するベクトル
命令処理（ステップ１３０６）について、区切り位置ベ
クトルＭＳＫ２の各要素の値が７１．、成される毎に、
後続のベクトル命令であるステップ１３０７．　＋３０
８゜１３０９、１３１０を実行することができる。従っ
て、ベクトル命令列をオーバラップすることくチエイニ
ング）が可能であり、高速な処理が実現される。

さて、前述のように第１次絞り込み処理では、テキスト
ベクトルＴ　Ｅ　Ｘ、　Ｔ内で、キーワードに使われる
文字が最短連続長ＭＴＮＫＬ以り連続して出現する場合
に、その文字列を候補文字列としてその先頭位置と文字
列長を出力する。そのため、以上のステップで得られた
候補文字列のうち、最短連続長未満の文字列を候補から
削除する。まず、終了位置ベクトルＢＴＭの各要素につ
いて、先頭位置ベクトルＴＯＰの対応する要素の減算を
行い（ステップ１３１１、この処理は通常のベクトル命
令により実行できる）、最短連続Ｍ　Ｉ　Ｎ　Ｋ　Ｌ以
上の値については（ステップ＋３１２＞、候補文字列長
として、候補長ベクトルＬ　Ｎ　Ｇに出力を行うと共に
、対応する候補文字列の先頭位置を先頭位置ベクトル゛
］”　ＯＰに出力する（ステップ！　３１３　）。また
、終了位置ベクトルＢＴＭの要素がら先頭位置ベクトル
ＴＯＰの要素を減算した値が最短連続長ＭＩＮＫ■７よ
りも小さい場合には、対応する候補文字列はキーワード
に一致しないことが明らかなので出力は行わない（ステ
ップ＋３１４）、第１４図の例でいえば、先頭位置ベク
トル丁’ｏｐと終了位置ベタ１−ルＢ　Ｔ　Ｍの第２要
素によって指定されるテキストベクトルＴＥＸＴＪ―の
１１　Ａ　Ｉ″なる文字列については、その長さは１で
あり、最短連続長ＭＩＮＫＬ＝４より小さいので、この
文字列を示す要素番号の値は先頭位置ベクトルＴ　ＯＩ
）と候補長ベクトルＬ　Ｎ　Ｇに出力されない。このよ
うに、最短連続長Ｍ　Ｉ　Ｎ　Ｋ　Ｌを設けてチエツク
を行うことで、なるべくキーワードに近い文字列が候補
文字列として検出される。

プログラムがステップ１３１５に達すると、第１次絞り
込み処理ルーチンは終了する。

第１５図は本発明による文字列検索方法の一実施例の処
理フロー図で、特に前述の第２次絞り込み処理、すなわ
ち候補文字列群の情報からキーワードに合致する情報を
検出する処理に有効な方法である。第２次絞り込み処理
の方法としては、通常のテキストサーチ処理機能をもつ
従来方式（例えばスカラＦＳＡ法など）が適用可能であ
る。しかし、次の理由から、第２次絞り込み処理はなる
べく高速であることが望ましい。すなわち、上記文字列
検索方法の実行時間は第１次絞り込み処理実行時間と第
２次絞り込み処理実行時間の和で決まる。従って、第１
次絞り込み処理結果の文字列に含まれる文字の量が、テ
キスト全体の文字量の１／ｎであるとし、第２次検索を
通常のスカラプログラムによるＦＳＡ法で行う場合を考
えると、第１次検索処理がいかに高速であってもスカラ
プログラムによるＦＳＡ法に対する性能向上比は、たか
だか０倍にとどまる。

６〇− そこで、本実施例では、第２次絞り込み処理製高速化す
るため、従来知られているＦＳＡ法とベクトル化方法を
巧みに組合せることによって、高速化を実現している。

すなわち、ベクトル演算処理の高速化に必要な条件は ０）ベクトル長が長いこと。

（２）各ベクトル要素が独立に計算可能であること。

である。

そこで、テキスト文字列において、そのテキスト文字列
が含むキーワードを分割することなく、テキスト文字列
が互いに重複することのないように複数の部分文字列に
テキス］・文字列を分割することができれば、以下の手
順に従ってＦＳＡ法をベクトル化して処理することが可
能である６豪略は以下の通りである。

まずキーワードから状態遷移表を作成し、これをベクト
ル形式のデータである状態遷移ベクトルとする。次に各
部分文字列について部分文字列毎に一意に対応する状態
を割り当て、これらの状態を要素とする状態ベクトルを
生成する。次に各部分文字列の第１番［１の文字からな
る入力文７八”りトルを生成する。この３つのベクｌ〜
ルに基づき、各部分文字列における１文字分の検出処理
（ＦＳＡ法の状態遷移処理）をベクトル処理として実行
する。すなわち、状態ベクトルの各要素について。

対応する入力文字ベクトルの要素に従って状態遷移ベク
トルを参照し、読み出した遷移先状態で状態遷移ベクト
ルの要素を書き換えることで、各部分文字列について１
文字分の検出処理かヘクトル処理の形で実現される。１
文字分の状態遷移処理を行った後は、各部分文字列の第
２文字Ｌ］の文字で入力文字ベクトルを作成し、状態遷
移処理を繰り返す。以−にの処理を部分文字列の最終文
字に到るまで繰り返せばよい。

この方法によれば、部分文字列数が十分大きけ九ば前述
の条件（１）が満たされ、また部分文字列どうしは互い
に無関係であるから条件（２）についても満足すること
ができ、ベクトル化が可能となる。前記第１次絞り込み
処理の結果である候補文字列は明らかに前述の２つの要
件な満たすテキスト文字列の部分文字列になっている。

以下の実施例の説明では上記第１次絞り込み結果を上記
部分文字列とした場合について説明するが、ＦＳＡ法の
ベクトル化は本実施例に限定されない。例えばテキスト
文字列を部分文字列に分割する方法としては、最も単純
にはテキスト中のキーワードでないような区切り記号を
用いることが考えられる。例えば和文であれば句点や読
点、英文であれば空白がこれにあたる。

以下、第１５図に示されるＰＡＤに従って、必要に応じ
てベクトルデータの流れを示した第１７図を参照して実
施例の処理を詳細に説明する。なお、第１７図のベクト
ルデータの内容は、第１４図で示したテキスト文字列、
キーワード文字列に対応するものである。

まず、テキス１〜サーチプログラム１０６により。

第２次絞り込みルーチン：＋２がコールされ、第１５図
のベクトル化ＦＳＡ法処理ルーチン１５０１が起動され
る。ベクトル化ＦＳＡ法処理ルーチンの起動にあたり、
呼出し側から渡されるパラメータを第１７図（ａ）に示
す。ただしパラメータの内、状態遷移ベクトルＦ　Ｓ　
Ａ、　Ｔ　Ｂ　Ｌと受理ベクトルＡ　ＣＣＩ）Ｔは９本
ルーチン１５０１の内部変数であり、パラメータとして
は渡していない。またテキストベクトルＴＥＸＴと、候
補文字列の位置と長さを示すベクトルである先頭位置ベ
クトル’ｒ　ｏ　ｐと候補長ベクトルＬ　Ｎ　Ｇが、さ
らに各候補文字列に対応する状態からなる状態ベクトル
５ＴＡＴＥが渡される。

ここで、候補文字列を示す２つのベクトルＴＯＰとＬＮ
Ｇには、第１次絞り込み処理の結果である３つの部分文
字列“５ＥＡＲＣ，Ｈ”、”５ＯＲＴ′’”　Ａ　Ｌ　
Ｇ　ＯＲＩ　Ｔ　ｉ（Ｍ″′を指し示すインデックス値
が格納されている。また状態ベクトル５ＴＡＴＥの各要
素については初期状態の値Ｏが格納されている。

さらに、第２次絞り込み処理の結果得られた文字列（キ
ーワードに一致する文字列）の位置と長さを格納する領
域として、検索結果位置ベクトルＲＴ　ＯＰと検索結果
長ベクトルＲＬ　Ｎ　Ｇが与えら一図一 れる、第１７図では、ベクトルＲＴＯＰ及びＲＬ　ＮＧ
は実施例に基づく最終結果に対する値が示されているが
、もちろん起動時にはこれらの値は格納されてはいない
。本実施例では簡単のため、出力領域として十分な長さ
すなわち要素数のベクトルが用意されている。

さて２以上のパラメータを渡されたベクトル化ＦＳＡ法
処理ルーチン（１，５０１）は、まず初期化を行う　（
ステップ１５０２）。まずキーワードＫＥＹより、状態
遷移ベクトルＦ　Ｓ　Ａ　ＴＢ　Ｌと受理ベクトルな生
成する。さらにプログラム変数りに先頭位置ベクトルＴ
ＯＰのベクトル長さをセットする。

つまり、プログラム変数りには、絞り込みの対象となる
候補文字列（部分文字列）の数（本実施例ではＬ−３）
がセットされる。

第１６図は上記状態遷移ベクトルＦＳＡＴＢＬ及び受理
ベクＩ〜ルＡＣＣＰＴを説明する図である。

第１６図（ａ）は、”５ＥＡＲＣＨ”　、”ＡＬＧＯＲ
ＩＴＨＭ”、”ＴＥＸＴ”の３つをキーワードとして与
えた場合の状態遷移図である。第１６図は上記状態遷移
図（ａ）をもとに作られた、状態と入力文字と状態遷移
先の関係を表わす表で、その中で、状態遷移先はベクト
ルデータＦ　Ｓ　Ａ　Ｔ　１３Ｌを構成する。状態遷移
先ＦＳＡＴＢ［、には各状態毎に入力文字セットの分（
この場合、入力文字はｉ　Ｂのコードであるから２　Ｂ
＝　２５６種）だけエン１−りが用意されており、各文
字はその文字コートを８ビツトの２進整数として昇順に
エン１−リ」−に並へられている。従ってＦ　Ｓ　Ａ　
Ｔ　Ｂ　Ｌのベクトルの要素数は〔状態数Ｘ２５６：ｌ
である。ＦＳΔｉ’　ＢＬの各要素には、ある状態のも
とて特定の入力文字を入力した場合の遷移先状態が格納
されている。

例えば、状態０で文字ＩＩ　Ａ　ＩＩを入力した場合、
状態遷移ベクトルＦ　Ｓ　Ａ　Ｔ　Ｂ　Ｌの第１９３番
目（ＩＩ　ＡＩＩのＥＢＣＤＩＣコードは１６進数のＣ
１であり、１０進数では１９３となる）の要素を参照し
て状態７に遷移することがわかる。また、第１６図（ｃ
）の受理衣は状態がキーワードとして受理できるものか
をチエツクするものである。すなわち、受理ベクトルＡ
ＣＣＰＴは、各状態に対応するエントリが用意されてお
り、受理状態であれば検出されたキーワードの長さが、
受理状態でなければＯが格納されている。第１６図の例
でいえば、キーワード″Ｓ）にΔＲＣＨ″を検出した状
態ｆ３に対応するＦＳＡＴＢＬの要素の値は６となり、
文字数６の文字列をキーワードとして検出したことが示
される。

第１５図に戻り、次に候補文字列が存在する限り（ステ
ップ１５０３）以下のステップを繰り返す。

まず、候補文字列の全てについて、先頭位置ベクトル１
゛ＯＰの指す１文字からなるベクトルＩＮＣＨを作成す
る（ステップ＋５０４）。この処理は間接アドレスによ
るベクトル移動命令により実現がなされる。結果のベク
トルＩ　Ｎ　ＣＦ（と状態ベクＩ〜ルＳ　Ｔ　Ａ、　Ｔ
　Ｅの値から、状態遷移ベクトルＦＳＡＴ　Ｂ　Ｌを参
照し、遷移先状態の値で状態ベクトルＳＴΔＴＥを更新
する（ステップ＋５０５）。このステップは通常のべり
１−ル命令（積演算、和演算。

間接アドレスに基づく移動演算等）の組合せで実現でき
る。

次に、ステップ１５０４．１５Ｃ１５により各候補文字
列に対し１文字分の状態遷移が終了したので、各候補文
字列について、先頭位置ベクトルＴＯＰの値を１インク
リメントし、候補長ベクトルＬ　Ｎ　Ｇの値を１デクリ
メントする（ステップ＋５０６）。すなわち先頭位置ベ
クトルＴＯＰは各候補文字列について、次の入力文字の
テキスト上での位置を示すベクトルであり、候補長ベク
トルＬ　Ｎ　Ｇは各候補文字列について、検索処理の対
象となる残りの文字数を示す値である。上述の例に従っ
て、３つの候補文字列の先頭文字について、上記のステ
ップを実行した時点（第１５図■の時点）での先頭位置
ベクトルＴＯＰと入力文字ベクトルＩＮＣＨ，状態ベク
トル５ＴＡＴＥ、そして候補長ベク］・ルＬＮＧの値を
第１７図（ｂ）■に示した。ここで先頭位置ベクトルＴ
ＯＰの値は初期値より各々１大きな値となり、各候補文
字列の第２文字目が次の遷移処理（ステップ１５０４．
１５０５）の対象となることを示している。また入力文
字ベクトルＩＮＣＨには、各候補文字列の先頭文字が格
納され、状態ベクトル５ＴＡＴＥには、入力文字ＴＮＣ
Ｈに基づく遷移結果が格納されている。第１番目の候補
文字列についてみれば、状態Ｏで文字パＳ′″を入力し
たことで状態］−に遷移したことがわかる。候補長ベク
トルＬ　Ｎ　Ｇについては、１文字分の遷移処理を行っ
たために、各要素とも初期状態より］少ない値が格納さ
れている。

さて状態遷移が終わると、各候補文字列について、遷移
後の断状態が受理状態であるか否かの検査を行う。まず
遷移後の状態５ＴＡＴＥをもとに受理ベクトルＡＣＣＰ
Ｔを参照して、参照した値が正の数であれば（ステップ
１５０７）受理状態であるから、検出文字列の先頭位置
と長さを出力用のベクトルＲＴＯＰ、ＲＬＮＧに格納す
る（ステップ１５０８）。受理ベクトルＡＣＣＰＴを参
照した値がＯなる受理状態ではないので、次のステップ
に進む。第１７図（ｂ）■の例では、状態ベクトル５Ｔ
ＡＴＥの各要素である状態１，７は共に受理状態ではな
いので、結果文字列の出力は行われない。

次に、候補文字列の圧縮ステップについて説明する。ま
ず圧縮結果を出力する位置を示すプログラム変数Ｊを１
にセットする（ステップ＋５０９）。

次に全ての候補文字列について、各候補文字列の残りの
長さである候補長ベクトルＬ　Ｎ　Ｇの要素の値を検査
する（ステップ１５］０）。もし長さがＯより大きけれ
ば、候補文字列の残りの部分に次の状Ｓ遷移処理を行う
必要があるから、先頭位置ベクトルＴＯＰ、候補長ベク
トルＬＮＧ、状態ベクトル５ＴＡＴＥから除外しないで
おく　（ステップ１５＋１）、もし長さがＯであれば、
該当する候補文字列の最終文字について状態遷移処理を
実行したことがわかるので、この候補文字列に関する先
頭位置、候補長、状態の各情報を各ベクトルから対応す
る要素を除外する。最後に、残った候補文字列の数をプ
ログラム変数Ｎにセラ１−する（ステップ１５１２）。

第１７図（ｂ）■の例で言えば、各候補文字列とも残り
の長さを示す候補長ベクトルの要素値がＯより大きいの
で、候補文字列数は不変である。

ステップ１５０４からステップ１５１１について、各候
補文字列の性質を表わすベクトル（先頭位置ベクトルＴ
ＯＰ、候補長ベクトルＬ　Ｎ　Ｇ　、入力文字ベクトル
ＩＮＣＨ，状態ベクトル５ＴＡＴＥ）において、各ベク
トル要素は互いに無関係である。従ってこれらのステッ
プを構成するベクトル命令例では、あるベクトル命令が
出力するベクトルにおいて、要素の値が確定した時点で
、このベクトルを入力とする次のベクトル命令の演算を
開始することが可能であるから、ベクトル命令列の間で
実行をオーバラップすること（チエイニングと呼ばれる
）ができ、高速化が達成される。このように本実施例の
バク１ヘルＦ　Ｓ　Ａ法は、ベクトル計算機において好
適なアルゴリズムとなっている。

以上で、各候補文字列について１文字分の処理が終了す
る。そこで、ステップ１５０３に戻り、候補文字列数を
示す変数Ｎ　ＩＪ＜　ｏより大きいか否かを調べる。変
数ＮがＮ＞Ｏ５つまり候補文字列が残っている限りは上
記のステップ（ステップ１５０４〜＋５１２）を繰り返
し実行する。候補文字列が尽きた時点でベクトル化ＦＳ
Ａ法の処理（＋５０１）が終了し、リターンする（ステ
ップ１５Ｊ３）。

最後に第１７図の例を用いて、候補文字列の圧縮と、結
果文字列の出力について説明する。第１６図ステップ１
５０４〜１５１２のループのうち、■点での各ベクトル
の値を示したものが第１７１（ｂ）である。

第１７図（ｂ）の■では、候補長ベクトルＬＮＧの第２
要素の値がＯとなり、候補文字列”　Ｓ　ＯＲＴ　”の
サーチが終了したことがわかる。そこでステップ１５１
０−１５１１の処理で候補文字列”５ＯＲＴ”＆、−関
するデータが削除され、第１７図■以降では候補長が２
　（Ｎ＝２）となる。また第１７図（ｂ）■では、状態
ベクトル５ＴＡＴＥの第１要素の値が６になっている。

状態６については受理ベクトルＡＣＣＰ　Ｔ　（１，５
０２）の第６要素の値が６であり、受理状態であること
がわかる。そこで、ステップ１５０７〜１５０８により
候補文字列“Ｓ　Ｅ　Ａ　Ｒ，ＣＨ”についてはキーワ
ードに一致する文字列として結果格納用のベクトルＲＴ
ＯＰ、ＲＬＮＧに対する出力（キーワードのテキスト文
字列の位置及び文字数）が取り出される。

以上の処理によってベクトル化ＦＳＡ法による第２次絞
り込み処理の結果、第１次絞り込み処理結果である候補
文字列”　Ｓ　Ｅ　Ａ　ＲＣＨ″“Ｓ○ＲＴ”　、”Ａ
ＬＧＯＲＴＴＩ−ＩＭ”のうち、雑音である候補文字列
”　Ｓ　ＯＲＴ　”が除去され、全体として完全なサー
チが実現される。

第２次絞り込み処理ルーチン３２が完了すると、目的の
最終結果が得られるのでテキストサーチプログラムが完
了する（ステップ３３）。

本実施例では、第１次絞り込み処理と第２次絞り込み処
理の対象となる文字コードを１バイトとしたが２バイト
コートでも差し支えない。また、１バイトコードのテキ
ストについても、連続する２バイトを１文字として扱う
ことにより、２バイト単位で第１次絞り込み処理を実現
すれば、第１次絞り込み処理で検出される候補文字列の
量が１バイト単位で検出した場合に比べて低下し、第２
次絞り込み処理の負荷を低下することができる。

この改良方法について、第１８図を用いてその概要を説
明する。対象とするテキスト及びキーワードは】バイ］
・コード（ＥＢＣＤＴＫコード）で表わされるものとし
、また簡単のため出現文字はアルファベット２６文字と
空白の全部で２７種類とする。

さらに出現状態ベクトルＫＷＤ　（２００１）のエント
リを７２９　（＝２７Ｘ２７）に制限する。第１８図に
示されるように、キーワードは連続する２バイ１−が１
文字として扱われ出現状態ベクトルに、ＷＤＩ８１に賛
録されている。例えば単語“ＴＥＸＴ”はＩＩ　Ｔ　Ｆ
　ＩＴ　、　　ＩＩ　ＥＸ　＋＋　、　　１１　Ｘ　Ｔ
　＋＋の４つの文字からなる列として扱い、対応するエ
ントリに１が格納されている。テキスト文字列について
も連続する２バイトを１文字として扱う（テキストベク
１〜ルＴ　Ｅ　Ｘ　Ｔ　１８２）。第１次絞り込み処理
のアルゴリズムに関しては、処理の単位が変わるだけで
あとは」二連の実施例と全く同じ処理を行えばよい。本
改良法では、１バイト髪１文字として処理を行う場合に
候補文字列に出現する”　ＨＡ　Ｓ　Ｈ”なる雑音を除
去することができる（エントリ”　ＨＡ　””ＡＳ”　
、”ＳＨ”の出現状態ベクトルに、　Ｗ　Ｄ１８１での
値がＯであるため）。従って、第１次絞り込み処理の結
果である候補文字量が低減されて、第２次絞り込み処理
での処理量が少なくなり、全体として高速化が達成され
る。

〔発明の効果〕

本発明によれば、複数キーワードに対する文字列検索が
２段階から構成され、第１段階ではテキス１〜がキーワ
ード及びそれに類似する文字列とに絞り込まれ、第２段
階では絞り込まれた各文字列に対し、キーワードを含む
か否かが再度チエツクされる。第１０図で説明したよう
に第１段階はパイプライン処理による高速化が行え、第
２段階では処理する文字量が絞り込まれて低減されてい
るので、全体として高速化される。今、従来の文字列検
索の処理速度を１５、第１段階での処理速度をα。

第１段階による絞り込みの串（すなわち候補文字列の量
÷テキスト量）をβとし、第２段階では従来の文字列検
索と同じ方法を適用するものとすると、第１段階での処
理時間はテキスト文字をＮとしてＮ／α、第２段階での
処理時間は候補の量はＮβで速度］、なのでＮβとなる
。

従って本発明の方法と従来方法の処理時間の比＝７５ は Ｎ／α＋Ｎβ：Ｎ＝−＋β：１である。

例えば、α＝ＩＯ１β＝０．１とすれば本発明の方法は
従来方法よりも５倍高速であることがわかる。

ここでαとβの実際の値についてもう少し詳しく説明す
る。始めに専用ハードウェアにより、本発明を実現した
場合について述べる。

まず、αについてみる。本発明の第１段階における１テ
キスト文字の処理は、テキスト文字の読み出し、ハツシ
ュによるＲＡＭアドレスの生成。

ＲＡＭからの出現形態情報読み出し、及びカウンタ更新
から成っており、第１０図に示したようにパイプライン
化され見かけ上１単位時刻（マシンサイクル）で１テキ
スト文字の処理が完了する。

方第１２図に示すＦＳＡ法のプログラムでは１テキスト
文字当たりステップ１２０４〜１２１２のループを回る
ので少なくとも１０マシンサイクル以上を要する。

従ってα≧１０となる。

次に、βについて説明する。βは前述のように、テキス
トが第１段階でどの程度まで絞り込まれたかを示す割合
である。この割合はテキストとキーワードに依存して大
きく変化する。種々のテキストとキーワードの紹合せに
ついてβを実測した結果を第１９図に示す。第１９図は
あるテキス１〜とキーワードの組合せをｊつのケースと
して、９つのケースについてβを実測したもので、絞り
込まれた候補をさらに雑音とキーワード一致文字列とに
分離して示している。ケース３〜ケース２は、同一分野
のテキストとキーワード、例えば計算機関係の文献をテ
キストとして計算機の技術用語をキーワードとして与え
たような場合であり、ケース３〜ケース８は異分野のテ
キストとキーワードの組合せについてみたものである。

第１９図より明らかなように同一分野ではβは０．１〜
０．１５程度、異分野では０〜０．０１程度となり、こ
の例では平均約０．０５　＜らいになる。

従って本発明の文字列検索方法及び装置は、第１９図の
例ではＦＳＡ法に比べ約６．７倍程度高速となる。

次に、通常のベクトルδ１算機を用いて本発明を実現し
た場合の効果について説明する。この場合、第１次絞り
込み処理のルーチンは第１３図のフロチャートに従い、
第２次絞り込み処理ルーチンは第１５図のフローチャー
１−に従い実現される。しかしベクトル化されたプログ
ラムを処理する場合に、ベクトル命令列のうちでオーバ
ラップ可能な命令列を並列に実行する能力（チエイニン
グと呼ばｔｉ。

る）は、通常ベクトル計算機の機種毎に異なる。

従って、前述のパラメータαに一〕いて、−概にこれを
言うことはできない。以丁では、プログ弓ム言語ＦＯＲ
Ｔ　ＲＡ　Ｎにより記述された本発明のアルゴリズムを
１日立製作所製Ｓ８１．Ｏアレイプロセッサシステムで
実行した場合の性能と、従来のＦパＳＡ法を５８１０ア
レイプロセツサシステムのスカシプロセシングユニット
で実行した場合の性能とを実測した結果に基づいて、本
発明の効果を述べる。第２０図は、１６３８６文字のテ
キストに対し、２通りのキーワードを与えて両者の性能
を実測した値である。前述のように１本発明のテキスｌ
〜サチ方式では、耐記のパラメータβの値が性能を大き
く左右する。そこで、キーワード列を２通り与えて、β
の値力司、０１５と０．８の場合の性能を実測している
。この値から逆算すると、ベクトル化された第１次検索
処理ルーチンの、スカラＦＳＡ法に対する性能比は１３
．２倍、ベクトル化ＦＳＡ法のスカシＦ　Ｓ　Ａ法に対
する性能比は６．５６倍である。従って、ベクトル計算
機による本発明のテキストサチ処理方法とスカラＦＳＡ
法の処理時間の比はである（ここでＮはテキストの巣で
ある）。

次に、英語論文を対象とした絞り込み率βの実測結果を
第２１図に示す。第１９図では、ケース０〜ケース２は
同一分野のテキストとキーワード、ケス３〜ケース８は
異分野のテキストとキーワードの組合せについてみてい
る。しかし、第１９図とは異なり、テキスｌ〜とキーワ
ード間での−Ｍ、不一致に関する情報と、絞り込み率β
の間に明確な相関関係はない。これは、キーワードを出
現情報ベクトルへ登録する際にＩＢ小単位登録を行って
いるため、雑音の占める割合いが大きいことによる。こ
の例で、βの平均値は約０．６１である。

従って、ベクトル計算機上での本アルゴリズ１１の性能
は、第２１図の例ではＩ”　Ｓ　Ａ法と比べて約５．９
倍程度高速となる。

【図面の簡単な説明】

第１図は本発明による文字列検索装置の−・実施例の構
成を示す図、第２図は第１図の１−、記憶装置の詳細図
、第３図は本発明による文字列検索方法の一実施例の処
理を示すフローチャート、第４図は第３図における第１
次絞り込み処理の詳細なフローチャート、第５図は第１
図の実施例に使用されるハツシュ回路の構成図、第６図
は第１図の実施例におけるキーワード文字の属性を表わ
す図、第７図は第１図の実施例におけるテキストサーチ
命令の形式を示す図、第８図は第１図の実施例における
各カウンタ制御論理回路及びストア制御論理回路の構成
を示す真理値表、第９図は第１図の実施例における動作
履歴を示す図、第１０図は第１図の実施例のパイプライ
ン動作を示すタイムチャート、第１１図は本発明による
文字検索方法における第２次絞り込み処理の一実施例の
処理フローチャー１・、第１２図はＦＳＡ法の説明図、
第１３図及び第１５図は本発明による文字検索方法の他
の実施例のフローチャート、第１４図は第１３図の実施
例におけるベクトルデータの流れを示す図、第１６図は
第１５図の実施例に使用される状態遷移表を示した図。 第１７図は第１５図の実施例によるベクトル化ＦＳＡ法
の処理におけるベクトルデータの流れを示す図。 第１８図は本発明による文字列検索方法の一実施例に使
用されるデータの構成を示す図、第１９図及び第２１図
はいずれも本発明による第１次絞り込み処理による絞り
込みの割合を実測した結果に示す図、第２０図は本発明
による文字検索方法の一実施例における実測した結果を
示す図である。 〈符号の説明〉 】０２・テキスト文字列 １０３・出現形態マツプ ＋０４・第１次絞り込み結果 １０５・・・第２次絞り込み結果 １０６・・・テキストサーチプログラム１１７・・・テ
キスＩ〜サーチユニット３１・・・第１次絞り込み処理
ルーチン３２・・・第２次絞り込み処理ルーチン１０９
・・・出現形態マツプ格納用ＲＡＭ】１３・・・一致長
カウンタ ＋１６・・・ハツシュ回路 １４４〜１４６・・・キーワード文字列１５０１・・ベ
クトル化ＦＳＡ法プログラム２１１・・・テキストカウ
ンタ制御論理２１２・・・一致長カウンタ制御論理 ２１３・・・有効長カウンタ制御論理 ２］４・・・結果カウンタ制御論理 ２１５・・・ストア制御論理

Claims (1)

1. 【特許請求の範囲】 １、テキスト文字列を表わすテキスト文字列情報から、
   キーワード文字列に対応する情報を検索する方法であっ
   て、 上記テキスト文字列情報から上記キーワード及び上記キ
   ーワード文字列に類似する文字列とからなる候補文字列
   の情報を検出する第１ステップと、 上記第１ステップで得られた候補文字列の情報が上記キ
   ーワード文字列の情報に一致するか否かを調べ、上記候
   補文字列の情報からキーワード文字列の情報を抽出する
   第２ステップとを有することを特徴とする文字列検索方
   法。 ２、請求項第１記載において、上記第１ステップは、少
   なくとも上記テキスト文字列に表われる全ての文字のそ
   れぞれについて、上記キーワード文字列中の出現形態を
   表わす出現形態情報を得る第３ステップと、上記テキス
   ト文字列情報の各文字の情報を順次得る第４ステップと
   、上記第４ステップで得られた文字の情報を上記出現形
   態情報に照合して個別の出現形態情報に変換する第６ス
   テップと、上記個別の出現形態情報を用いて、上記個別
   の出現形態情報に対応する文字を上記候補文字列に加え
   るか否かを判定する第７ステップとを有し、上記第４、
   第５、第６及び第７ステップが複数の文字に対してパイ
   プライン処理されることを特徴とする文字列検索方法。 ３、請求項第２記載の文字列検索方法において、上記第
   ２ステップが、上記キーワード文字列情報を用いて、キ
   ーワードの状態遷移表を作る第８ステップと、上記候補
   文字列の情報に対応するテキスト文字列を入力とし、上
   記状態遷移表によって、上記候補文字列の中から上記キ
   ーワード文字列に対応する情報を選出する第９ステップ
   を有する文字列検索方法。 ４、請求項第２記載において、上記出現形態情報は各文
   字がキーワード文字列に出現するか否かを表わす情報で
   ある文字列検索方法。 ５、請求項第２記載において、上記出現形態情報は各文
   字がキーワード文字列の中のどのような位置に出現する
   かを示す情報である文字列検索方法。 ６、請求項第１、第２、第３、第４又は第５記載におい
   て、上記第２ステップで得られるキーワード文字列の情
   報が上記テキスト文字列におけるキーワードの最初の文
   字の上記テキスト文字列における位置情報及び上記キー
   ワード文字列の長さの情報である文字列検索方法。 ７、テキスト文字列を表わす第１情報、キーワード文字
   列を表わす第２情報、上記テキスト文字列の各文字が上
   記キーワード文字列に現れる形態を表わす出現形態情報
   、上記第１及び第２情報ならび上記出現形態情報を用い
   て上記テキスト文字列から上記キーワード文字列又は上
   記キーワード文字列に類似する文字列からなる候補文字
   列群を表わす第３情報を得る第１プログラム及び上記第
   １情報と上記第２情報と上記第３情報を用いて上記第３
   情報の中の上記キーワード文字列に関する第４の情報を
   選ぶ第２プログラムを格納する単一又は複数の記憶装置
   と、上記第１及び第２プログラムによって動作する処理
   ユニットと、 上記処理ユニットが第１プログラムが実行されるときに
   起動し、上記記憶手段の出現状態情報を記憶するメモリ
   と、上記テキスト文字列の第１情報を各文字毎に順次読
   み出し、上記第１情報を上記メモリのアドレスとして上
   記出現形態情報を読み出す第１手段と、検出中の候補文
   字列の長さを保持する一致長カウンタと、上記一致長カ
   ウンタの計数値及び第１の手段で得られた出現形態情報
   とに従って、上記検出中の候補文字列の次のテキスト文
   字を候補文字列に加えるか否かを判定し上記一致長カウ
   ンタを更新する制御手段とを有するテキストサーチ装置
   とを持つ文字列検索装置。 ８、請求項第８記載において、上記出現形態情報がテキ
   スト文字列に表われる全種類の文字について、各文字が
   キーワード文字列に出現するか否かの情報である文字検
   索装置。 ９、請求項第７記載において、上記出現形態情報がテキ
   スト文字列に表われる全種類の文字について、各文字が
   キーワード文字列中でどのような位置に出現するかを表
   わす情報である文字検索装置。 １０、請求項第９記載において、上記出現形態情報が、
   キーワード文字列の最短長さ以下であるか否かの情報、
   キーワード文字列の先頭に表われるかの情報、キーワー
   ド文字列の先頭と最後外に出現するか否かの情報、キー
   ワード文字列の最後に出現するか否かの情報を有する文
   字列検索装置。 １１、請求項第１０記載において、さらに、テキスト文
   字列の検索された文字の位置を計数するテキストカウン
   タと、候補文字列の最後の文字が検出されたとき、その
   候補文字列の長さを計数する有効長カウンタと、複数の
   候補文字列の順位を計数する結果カウンタとを有し、上
   記制御手段は候補文字列が検出される毎に、上記テキス
   トカウンタ、一致長カウンタ、有効長カウンタより、上
   記候補文字列の最初の文字の上記テキスト文字列上の位
   置情報及び上記候補文字列の長さの情報を得るように制
   御する論理回路で構成された文字列検索装置。 １２、テキスト文字列を表わす第１情報を順次入力する
   第１手段、テキストに現われる全文字のそれぞれに対し
   、上記全文字のそれぞれが検索すべきキーワードの文字
   列の中で表われる形態情報を記憶した形態情報メモリ、
   上記第１手段で得られた第１情報を上記形態情報メモリ
   のアドレス信号に変換するアドレス変換手段、検索中の
   テキストの文字列が上記キーワード文字列の候補文字と
   して連続して発生しているとき、その長さを保持する第
   １のカウンタと、上記第１のカウンタの及び上記形態情
   報メモリからの形態情報を入力し、上記第１のカウンタ
   で保持されている候補文字列の次のテキスト文字を候補
   文字列に加えるか否かを判定し、上記カウンタを更新す
   る制御手段とを有し、テキスト文字列の情報から、キー
   ワード文字列の候補文字列群の情報を得る文字列検索装
   置。 １３、請求項第１２記載において、上記候補文字列群の
   情報は、上記候補文字列の先頭文字の上記テキスト文字
   列上における位置情報と候補となるキーワード文字列の
   文字数の情報とからなる文字列検索装置。 １４、請求項第１２記載において、上記形態情報は、検
   索すべき文字がキーワード文字列に出現するか否かの情
   報である文字列検索装置。 １５、請求項第１３記載において、上記形態情報は検索
   すべき文字のキーワード文字列における位置に関する情
   報である文字列検索装置。 １６、請求項第１記載の文字列検索方法において、上記
   第１のステップは、上記テキスト文字列に表われる全て
   の文字に対して、各文字がキーワード文字列内に出現す
   るか否かを表わす出現情報からなる出現情報ベクトルを
   生成する第３のステップと、上記テキスト文字列の各文
   字に対して上記出現情報ベクトル内の上記各文字に対応
   する出現情報を読み出し、上記読み出した出現情報がテ
   キスト文字列の各文字に一意に対応する要素となる検出
   状態ベクトル情報を生成する第４のステップと、 上記検出状態ベクトルを読み出し、検出状態ベクトルを
   構成する出現情報から対応するテキスト文字列の各文字
   が候補文字列を構成する文字であるか否かを判定する第
   ５のステップとを有する文字列検索方法。 １７、請求項第１６記載の文字列検索方法において、上
   記第５のステップは、上記検出状態ベクトルで同一の出
   現情報が連続して並ぶ両端の位置を表わす区切り位置ベ
   クトルを生成する第６のステップと、上記第６ステップ
   で得られた区切り位置ベクトル情報から上記両端の位置
   の先頭位置のベクトル要素のみを集めて構成される先頭
   位置ベクトル及び上記両端の位置の終了位置のベクトル
   要素のみを集めて終了位置ベクトル情報を作る第７のス
   テップと、上記先頭位置ベクトル及び上記終了位置ベク
   トルから、候補文字列の先頭文字の位置情報及び字数の
   情報を上記候補文字列の情報として出力する第８ステッ
   プとを持つ文字列検索方法。 １８、請求項第１７記載の文字列検索方法において、上
   記第８のステップは、上記候補文字列の字数がキーワー
   ド文字列群の最少文字数より少ないものを候補文字列情
   報より除くステップを有する文字列検索方法。 １９、請求項第１記載において、上記第１ステップは、
   少なくとも上記テキスト文字列にあらわれる、あらかじ
   め定められた長さを有する全ての部分文字列のそれぞれ
   について、上記キーワード文字列中の出現形態を表わす
   出現形態情報を得る第３ステップと、上記テキスト文字
   列情報の各部分文字列の情報を順次得る第４ステップと
   、上記第４ステップで得られた部分文字列の情報を上記
   出現形態情報に照合して個別の出現形態情報に変換する
   第６ステップと、上記個別の出現形態情報に対応する部
   分文字列を上記候補文字列に加えるか否かを判定する第
   ７ステップとを有し、上記第４、第５、第６及び第７ス
   テップが複数の部分文字列に対してパイプライン処理さ
   れることを特徴とする文字列検索方法。 ２０、テキスト文字列を表わす第１の文字列情報からキ
   ーワード文字列に対応する情報を検索する方法であって
   、 上記キーワード文字列に対応する状態遷移表を作り、上
   記テキスト文字列に表われる文字と状態とによって定ま
   る新たな状態をベクトル要素とする状態遷移先ベクトル
   を作る第１ステップと、 上記テキスト文字列の情報を、上記テキスト文字列に含
   まれるキーワード文字列が分断されることなく、かつ、
   テキスト文字列中の任意の文字が２つ以上の部分文字列
   に含まれないように、複数の部分文字列情報に分割する
   第２ステップと、 上記複数の部分文字列情報のそれぞれから検索対象とな
   っている文字の情報を取り出し、上記取り出した情報の
   それぞれをベクトル要素とする入力文字ベクトルを作る
   第３ステップと、上記入力文字ベクトル及び上記状態遷
   移先ベクトルより上記検索対象となっている文字の状態
   をベクトル要素とする状態ベクトルを作る第４ステップ
   と、 上記入力文字ベクトルと状態ベクトルを用いて上記部分
   文字列毎の状態遷移処理をパイプライン処理によって行
   う第５ステップとを有する文字列検索方法。 ２１、テキスト文字列を表わす第１の文字列情報から、
   検索すべきキーワード文字列の存在する上記テキスト文
   字列の位置及び文字列の字数を検索する方法において、 上記キーワード文字列の文字の遷移を状態情報で表わす
   状態遷移表を作り、上記状態遷移表を用いて、上記テキ
   スト文字列に表われる全文字のそれぞれと上記状態情報
   によって定まる新しい状態情報をベクトル要素とする状
   態遷移ベクトルを作る状態遷移ベクトル生成ステップと
   、上記テキスト文字列の情報を上記テキスト文字列に含
   まれるキーワード文字列が分断されることなく、かつ、
   上記テキスト文字列中の任意の文字が、重複して２つ以
   上の部分文字列に含まれないように、複数の部分文字列
   情報に分割する分割ステップと、 上記複数の部分文字列情報のそれぞれから、検索すべき
   文字情報を順次切り出し、これをベクトル要素として、
   上記部分文字列の数の要素からなる入力文字ベクトルを
   作る入力文字ベクトル生成ステップと、 上記入力文字ベクトルと上記状態遷移ベクトルと、上記
   検索すべき文字情報の１つ前の文字列情報に対応する状
   態情報とから、上記入力文字ベクトルに対応する遷移状
   態を要素とする状態ベクトルを作る状態ベクトル生成ス
   テップと、上記状態ベクトルの各要素の状態情報がキー
   ワードの最終文字の状態であるか否かを判別し、キーワ
   ード文字列の最終文字の状態であるときは、その要素に
   対応する部分文字列における上記最終文字の位置及び文
   字数を出力し、キーワード文字列の最終文字の状態でな
   いときは上記入力文字ベクトル生成ステップに戻り、次
   の検索すべき文字情報の処理に進む判別ステップとを有
   し、 上記入力文字ベクトル生成ステップ、状態ベクトル生成
   ステップ及び判別ステップを上記部分文字列毎に独立に
   行うことを特徴とする文字列検索方法。