JP2718062B2 - 学習型文字列検索装置と同装置の制御方式 - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は特許や学術文献などのテキスト情報の内容検
索を能率よく高速に処理する事ができる文字列検索装置
に関するものである。

（従来の技術） 特許や学術文献などのテキスト情報はOA（オフィス・
オートメーション）機器の技術の進歩に合わせて増加の
一途にある。それらは再利用されるために次々と大容量
化するファイルメモリに貯えられて行く。しかし、それ
らの内容を高速に検索して、必要な情報をとり出せるよ
うにするファイル情報のデータベース化は余り進まな
い。すなわち、ファイル情報の各レコードにその内容に
マッチしたキーワードを付加し、且つ、キーワード検索
を高速化できるようなキーワードの並べ替えをする作業
が人手に頼っていて、容易に達成されないからである。
また、内容がマッチしていても、検索の時に使うキーワ
ードがレコードに付加するキーワードと一致しない用語
のばらつきの問題もあるからである。

したがって、キーワードを付加したり、並べ替えたり
の作業なしで、ファイルメモリの中のテキスト情報を高
速に検索できないかと、リアルタイムな文字列検索の色
々な技法が研究されていた。

一般に、文字列検索装置はキーワードとして与えられ
る検索文字列がテキスト情報のどこに含まれるかを探り
出す機能を持ったものである。この機能を実現するため
には、テキスト情報の中の各文字列を複数個の検索文字
列と一斉に比較照合する文字列照合手段が必須となる。

そこで、本願の発明者等は任意長さの文字列を複数個
記憶する連想メモリ部と入力文字列の各文字に対する連
想メモリ部の文字比較結果を並列に受付けて、入力文字
列と記憶文字列間の文字の並び（順序）の比較を行なう
順序ロジック部とで文字列照合を可能とする構成記号列
識別装置の発明について特許出願を行った。名称が異な
るが、以上の装置が文字列検索装置の基本要素となる。
（特開昭60−211539号（特願昭59−068495号）、特開昭
61−253536号（特願昭60−96213号）など） このような文字列検索装置は検索したいキーワード
（検索文字列）の登録した後、被検索テキスト文字列を
入力すると、テキスト文字列が検索文字列のいずれかに
一致した時にマッチ信号を発生し、テキスト文字列のど
の部分がどの検索文字列にマッチしたかを出力する。し
たがって、キーワードのついていないテキスト文字列情
報の全文検索（フルテキストサーチ）が可能である。

すなわち、ファイル記憶されるテキスト文字列情報に
キーワードを付加するなどの煩雑な作業を伴わないで、
ファイル情報をデータベース化できる。

しかしながら、全文検索方式による情報検索はキーワ
ードを付加したテキスト文字列情報のキーワード部分の
みの検索で検索条件にマッチしたテキスト文字列情報の
ファイル格納位置をみつけ出すインデスク検索方式に比
べてはるかに長い検索時間を必要とする。というのは、
文字列照合速度がたとえ毎秒1000万字に及んでも、テキ
スト文字列情報の長さが一例として、10億字（１ギガバ
イト）になると、検索時間は全文をサーチするかぎり、
100秒に及んでしまう。１組のキーワード（検索文字
列）での検索だけでも、検索の都度100秒もかかると、
多くの検索要求を次々と受けることができなくなる。

（発明が解決しようとする課題） 従来の文字列検索装置の検索条件に含まれるキーワー
ド（検索文字列）を文字列照合手段に登録し、そこにテ
キスト情報を入力し、テキスト情報のどの部分（レコー
ド）がどのキーワードを含んでいたかを見つけ、その
後、検索条件式に合ったレコードを決定する。検索条件
式に合っているか否かはソフトウェア（プログラム）に
よって決められる。このために、大量のテキスト情報の
サーチは全文検索方式に従って行うと、検索時間が長す
ぎて、実用にならなかった。

この検索時間が長すぎるために、一度のテキスト情報
のサーチに際して、多数の検索要求に含まれるキーワー
ドを文字列照合手段に登録ておく事も考えられたが、テ
キスト情報のどのレコードがどのキーワードを含んだと
いう照合結果情報を複数の検索条件式に照らし合わせる
作業が並列に進まないと、検索終了までのレスポンス時
間が更に長くなるだけであった。すなわち、相異なる検
索条件の検索要求が到着する時に、ソフトウェアの力を
借りないと、そらを順次に高速に処理し、マッチしたレ
コードアドレスを短時間に出力できないという問題があ
った。

本発明の目的は全文検索方式での上記問題を解決する
文字列検索技術を提供することにある。もう少し具体的
には、検索条件に含まれるキーワードの中で、過去の検
索に使われた事のあるものがあればそれらが新しい検索
条件式を満足するかをソフトウェアの助けを借りずに直
ちに判定し、検索条件に合ったレコードアドレスを出力
し、使われた事のないキーワードが与えられた時にの
み、テキスト情報全文をサーチするようにして平均の検
索時間を短縮できるようにする学習型文字列検索技術を
提供する事にある。

（課題を解決するための手段） したがって、本発明は、複数検索文字列を記憶し、入
力文字列が複数検索文字列のいずれに一致するかを判別
する文字列照合手段と、どのテキストレコードがどの検
索文字列を含むかを記憶し、前記文字列照合手段の判別
する文字列のクラスコードによってアクセス番地の決ま
る第１記憶手段と、入力文字列間の検索条件論理に従っ
て第１記憶手段の出力の論理処理を行う検索条件照合手
段と、これにつながるエンコード手段と、照合のあった
文字列を含むテキストレコードの格納番地を記憶し、エ
ンコード手段の出力によってアクセス番地の決まる第２
記憶手段と、検索文字列照合手段の入力文字列として検
索文字列がテキスト文字列を選択するスイッチ手段とを
備える事を特徴とする学習型文字列検索装置と、 複数検索文字列を記憶し、入力文字列が複数検索文字
列のいずれに一致するかを判別する文字列照合手段と、
どのテキストレコードがどの検索文字列を含むかを記憶
し、前記文字列照合手段の判別する文字列のクラスコー
ドによってアクセス番地の決まる第１記憶手段と、入力
文字列間の検索条件論理に従って第１記憶手段の出力の
論理処理を行う検索条件照合手段と、これにつながり、
検索条件を満足するテキストレコードを指定するエンコ
ード手段と、前記テキストレコードの実際の格納番地を
記憶し、前記エンコード手段の出力によってアクセス番
地の決まる第２記憶手段と、前記文字列照合手段の入力
文字列として検索文字列かテキスト文字列を選択するス
イッチ手段とを備えた学習型文字列検索装置の制御方式
であって、前記文字列照合手段と第１及び第２記憶手段
にそれぞれ過去の検索文字列、文字列照合結果とテキス
トコレコードの格納番地を初期設定するイニシャライズ
モード、新検索文字列の中に検索文字列に一致しない検
索文字列のあった時に、その検索文字列を文字列照合手
段に追加登録する検索文字列登録モードと、文字列照合
手段にテキスト文字列を入力し、検索文字列を含んだテ
キストレコードをマークして第１記憶手段及び第２記憶
手段に書き込むテキスト文字列検索モードと、検索条件
論理と検索文字列を検索条件照合手段と文字列照合手段
に入力し、前記文字列照合手段の出力によってアクセス
番地の決まる記憶手段の出力を検索条件照合手段で処理
する検索条件照合モードと、その結果を用いて第２記憶
手段から検索条件にマッチしたテキストレコードの格納
番地を出力する検索結果出力モードとを備え、検索文字
列照合モードで全新検索文字列と過去の検索文字列との
マッチがあった時は、検索条件照合モードと検索結果出
力モードに移って、マッチしたテキストレコード格納番
地を出力するように制御し、検索文字列照合モードでマ
ッチのない時は、追加登録モードに移ってミスマッチ文
字列を文字列照合手段に登録し、その後、テキスト文字
列検索モードに移って検索結果を第１記憶手段と第２記
憶手段に書き込み、その後、検索条件照合モードを経
て、検索結果出力モードでマッチしたテキストレコード
の格納番地を出力するように制御する事を特徴とする学
習型文字列検索装置の制御方式である。

（作用） 本発明によると、検索文字列を、検索の都度、登録し
直すのでなく、追加登録し、テキスト情報全文のサーチ
によって得た検索結果を検索文字列毎に記憶する学習型
文字列検索装置で、検索条件式の違いによる検索のやり
直しをなくせるので検索時間が短縮でき、その結果とし
毎分当たりの検索サービス要求（トランザクション）の
受付回数が増えるという効果が期待される。

検索の都度検索条件を設定し直す従来方式では、たと
えば、テキスト情報全文のサーチ時間が１分に及ぶと、
毎分１回の検索要求しか受付けれない。本発明の学習型
文字列検索方式では、過去の検索要求に対する全文サー
チの結果を貯えているために、ほとんどの場合、テキス
ト情報全文のサーチをしないで新しい検索要求に対する
検索結果を直ちに出力できるようになる。ほとんどの場
合に検索時間が1msec以下に減る。検索結果を直ちに出
力できない検索要求の来た時にのみ、検索文字列を追加
登録してテキスト情報全文サーチを行い、その結果を記
憶された検索結果データに加えるので、その時だけは検
索時間が長いが、長期には、次第に、新検索要求に対す
る全文サーチの必要回数が減少する。1/10以下に減れ
ば、その分だけ、毎分の検索要求受付け回数が10倍以上
に増える事になる。

（実施例） 第１図は本発明の一実施例であり、基本構成図でもあ
る。文字列照合手段110がスイッチ手段120を介して入力
される検索文字列121を記憶し、次に、テキストファイ
ル装置130から来るテキスト文字列122を受付け、記憶し
た検索文字列121に等しい文字列を含むレコードが来た
時にマッチ信号を出力すると共に、検索文字列の識別コ
ードも出力する。

第１記憶手段140は文字列照合手段110の出力する識別
コードによって番地が指定され、マッチ信号によってア
クセスされる。各番地の複数ビットのメモリはマッチし
たレコードのどれがその番地に対応したキーワードを含
んだか否かのマークビットを貯えているものとする。す
なわち、ｉ番地のマッチしたレコードに対応して、ｉ番
目のビット位置のマークビットが“1"なら、そのレコー
ドがｉ番地に対応したキーワードを含み、“0"なら含ん
でいない事を示す。

検索条件照合手段150は、文字列照合手段110の出力す
る識別コードによってアクセス番地の決まる第１記憶手
段140から読み出されるマークビットデータを、順次に
入力端子151から与えられる論理条件に従って処理する
部分である。

エンコーダ160は検索条件照合手段150の出力の中の
“1"位置を符号化する部分である。“1"の発生位置が複
数個に及ぶ場合に、番号の低い方から順に符号化するに
は、エンコーダ160にプライオリテイ・エンコード機能
を持たせる必要があるが、それはエンコーダ160にマン
チェスター・チェイン回路を付加するだけで実現でき
る。

第２記憶手段170はマッチしたレコードのファイル装
置130での格納番地を記憶する部分である。当然、エン
コーダ160の出力によってアクセス番地が決まり、マッ
チしたレコードが複数個の場合にはテキスト情報の始め
の方のレコードの格納番地から順に出力される。

このような構成を採用する事によって、新検索文字列
を文字列照合手段110に登録し、その後でテキスト情報
を入力して、文字列照合結果の第１記憶手段140への一
時記憶が可能になるのは当然であるが、スイッチ手段12
0を切り替える事で新検索文字列と文字列照合手段110の
中の旧検索文字列との照合も可能になる。旧検索文字列
に対するテキスト情報の検索結果を第１と第２の記憶手
段140,170に記憶しておく事により、新検索文字列がす
べて旧検索文字列に一致するならば、テキスト情報全文
のサーチを行わず、検索のための条件論理を検索条件照
合手段150に入力するだけでマッチレコードの格納番地
を出力できるようになる。新検索文字列が旧検索文字列
に一致しない時にのみ、新検索文字列を文字列照合手段
110に追加登録し、テキスト情報全文のサーチを行なう
事が可能である。故に、検索サービスをすればする程、
文字列照合手段110への旧検索文字列の登録数が増え、
ほとんどの新検索文字列が旧検索文字列に一致するよう
になる。このために、テキスト情報全文サーチを行ずに
マッチレコードを出力できるようになり、性能が上が
る。この事が学習効果を示す。

この事から、本発明が学習型文字列検索装置と呼ばれ
る。

第２図は第１記憶手段、検索条件照合手段と第２記憶
手段の一実施例を示すと共に、第１記憶手段と第２記憶
手段の記憶内容の一例を示している。第１図と同じ番号
のものは第１図と同じ名称のものとする。

第１記憶手段140のＸアドレスレコーダ141には入力端
子119を通して文字列照合手段110の出力する検索文字列
の識別コードが入力され、Ｙアドレスデコーダ142には
アドレスカウンタ143が接続されている。テキスト情報
の全文サーチが始まる直前にアドレスカウンタ143の内
容は０（ゼロ）にセットされ、フリップ・フロップ144
からの立下り信号によって内容がカウントアップされ
る。フリップ・フロップ144には文字列照合手段110から
入力端子118を通してマッチ信号パルスが来て、内容を
ハイレベルにする。１つのレコードの中でマッチパルス
が２つ以上でも同じである。入力端子145にはテキスト
情報のレコード・クロック信号が与えられる。レコード
が変わる都度、レコード・クロック信号（RCLK）がフリ
ップ・クロップ144の内容をローレベルに下げる。その
時に、アドレスカウンタ143の内容を＋１だけ増加させ
る。以下では、まず始めにテキスト情報全文検索の結果
が第１と第２の記憶手段によってどのように貯えられる
かを説明する。

第１記憶手段140はテキスト情報全文サーチの期間は
書き込みモードにセットされ、文字列照合手段110から
入力端子118,119を通してマッチ信号と検索文字列の識
別コードが入力される。その識別コードで第１記憶手段
140のアクセス番地が決まる。検索文字列Ｂに対するマ
ッチ信号が39番目のレコードで始めて発生したとする
と、そのマッチ信号によって第１記憶手段140の第２行
目と第１列目（左端の列）が選択されて、そこにマーク
ビット“1"が書き込まれる。合わせて第２記憶手段170
の第１列目にアドレスデコーダ171とR/W回路172を介し
てマッチしたレコードのアドレスデータが書き込まれ
る。すなわち、39番目のレコードが第１番目にマッチの
あったレコードであれば、39が第２記憶手段170の第１
番地に書き込まれる。１つのレコードの中でいくつかの
検索文字列がマッチすると、第１記憶手段140の中の１
つの列のいくつかの番地にマークビット“1"が書き込ま
れる。

テキスト情報のレコードが切り替わる時（入力端子14
5からレコードクロック信号が与えられる時）にアドレ
スカウンタ143の内容が１つ増え、したがって、右隣の
列がＹアドレスデコーダ142によって選択される。しか
し、入力端子118からマッチ信号が来ないと、その列に
はマークビットが書き込まれない。次のレコードクロッ
ク信号がフリップフロップ144に与えられても、その後
にマッチ信号が発生しないと、フリップ・フロップ144
のレベルが変化しないのでアドレスカウンタ143の内容
は増えて行かない。したがって、Ｙアドレスデコーダ14
2は同一列を選択し続ける。

マッチ信号の発生したレコードが39番目の後、47番
目、48番目、91番目、140番目、275番目、302番目、…
だとすると、第２記憶手段170には図中に示したように
アドレスデコーダ171とR/W回路172を介して１番地から
順に39,47,48,91,140,275,302,…が書き込まれる。39番
目のレコードで検索文字列ＢとＣが含まれ、47番目のレ
コードで検索文字列Ａだけが含まれ、48番目レコードで
ＡとＤが含まれ、同様に、91番目レコードにA,BとＣが
含まれ、140番目レコードでＣとＤが含まれ、275番目レ
コードでＡとＢが含まれ、302番目レコードにA,BとＤが
含まれたとすると、第１記憶手段140では、それぞれ、
１列目に0110‥が、２列目に1000‥が、３列目に1001‥
が４列目に1110‥が、５列目に0011‥が、６列目に1100
‥が、７列目に1101‥が書き込まれることになる。検索
検索結果は以上のようにマークビットとマッチレコード
のアドレスデータとに分けられて第１と第２の記憶手段
に貯えられる。

次に、検索条件照合手段150について第２図で説明す
る。検索条件式で示す条件論理（たとえばオア論理、ノ
ア論理、アンド論理、ナンド論理など）が入力端子152
から与えられると、論理演算ユニット155は第１記憶手
段140の読出し信号レジスタ146の内容と処理結果のレジ
スタ156の内容との間の論理演算処理を行って、その結
果をレジスタ156に残す。論理演算ユニット155の処理機
能は入力端子152から与えられる条件論理によって変わ
る。入力端子151には入力端子118に与えられるマッチ信
号より時間遅れのあるタイミングで演算処理結果のレジ
スタ156へのセットパルスが与えられるとする。

入力端118からマッチ信号パルスが来ると、第１記憶
手段140の読み出し信号がレジスタ146に設定され、論理
演算ユニット155がレジスタ146とレジスタ156の内容に
対して論理演算を開始する。プライオリティエンコーダ
160は検索条件式の最後の記号が入力された時に、入力
端子161から与えられる検索結果トランスファパルスに
従って、第２記憶手段170のアドレスデコーダ171に選択
番地を与える。マッチしたレコードアドレスが複数個の
時には、選択番地を小さい方から順に出力する。

たとえば、検索条件式が（Ａ＊＋Ｃ）＊Ｄであると
すれば、それは＋Ａ）＊）＋Ｃ）＊Ｄ）＝に変換され
て、＊や＋などの条件論理が入力端子152に入力され
る。始めに、文字列A,B,C,Dは文字列照合手段110に入力
され、その後の右カッコ［）］が論理演算処理結果のレ
ジスタ156へのセットパルスとして入力端子151に入力さ
れる。レジスタ156の初期値は当然オール０（ゼロ）で
ある。

入力端子152に与えられる検索条件論理が、＋，＊，
＋−，＊−であれば、それぞれ論理演算ユニット155は
オアゲート、アンドゲート、ノアゲート、ナンドゲート
として働く。

第１の検索文字列Ａが入ると、マッチ信号パルスによ
って第１記憶手段140の第１行目の内容0111011‥が読み
出され、レジスタ146にセットされる。セットされると
同時に、レジスタ146と156の内容のオアゲートによる論
理演算が実行される。入力端子151からセットパルスが
与えられると、レジスタ146の156の内容のオア論理演算
結果がレジスタ156にセットされる。

その後、＊−（NAND）が入力端子152に与えられ、第
２の検索文字列Ｂが入力されると、第１記憶手段140の
第２行目の内容1001011‥がレジスタ146にセットされ
る。セットが終わると、レジスタ146の内容のノット
（補）とレジスタ156の内容との論理積の演算が実行さ
れる。次の右カッコ入力時に、演算結果がレジスタ156
にセットされる。故に、＋Ａ）＊）か入力され終わっ
た時点で、レジスタ156の内容は0110000‥になる。

次に、入力端子152から＋の条件論理が指定され、検
索文字列Ｃが文字列照合手段110に入力されると、第１
記憶手段140の第３行目の内容1001100‥がレジスタ146
にセットされ、その内容とレジスタ156の内容0110000と
の論理和が論理演算ユニット155で実行され、右カッコ
入力時に、論理演算ユニット155の演算結果がレジスタ1
56にセットされる。レジスタ156の内容は1111100‥に変
わる。

最後に、入力端子152から＊の条件論理が指定され、
検索文字列Ｄが文字列照合手段110に入力されると、第
１記憶手段140の第４行目に内容0010101‥がレジスタ14
6にセットされ、その内容とレジスタ156の内容1111100
‥との論理積が論理演算ユニット155で実行される。そ
の後の右カッコ入力時に、演算ユニット155の演算結果
がレジスタ156にセットされる。その内容は0010100‥と
なる。

この結果は最後の条件論理＝が入力された時に、入力
端子161にトランスファパルスが与えられ、プライオリ
ティ・エンコーダ160と第２記憶手段170を介してマッチ
・レコードのアドレスデータ（47と91）に変換され、4
7,91の順に出力される。

第２図はテキスト情報の全文検索の結果を第１記憶手
段140と第２記憶手段170に分けて、各検索文字列と対応
がつくように記憶できる事を示すと共に、新しい検索条
件が与えられた時に、以上の検索結果を用いて、マッチ
したレコードのアドレスデータを出力できる事を示し
た。もし新しい検索条件を満足するレコードアドレスデ
ータが求まらない時には、ミスマッチのあった検索文字
列を文字列照合手段110に追加登録して、テキスト情報
の全文サーチを行う必要がある。さらに、新しい検索文
字列に対する検索結果を第１記憶手段140と第２記憶手
段170へ記憶する必要がある。しかしながら、新検索文
字列を文字列照合手段110に追加登録した後でテキスト
情報全文をサーチすると、全検索文字列に対する検索結
果が求まる。この事は第１と第２記憶手段における検索
結果の記憶は追加する事でなく、最新のものを書き込め
る事を意味する。すなわち、テキスト情報に変更や追加
があってもこの時に修正が行われる。検索結果が単に追
加でなく、全文サーチの都度新しいものに書き替えられ
る事は実用的であり、検索時間の増加を伴わない。

第３図は文字列照合手段の一実施例の説明図である。
最もスマートと思われる例として、連想メモリ310の出
力段に順序論理回路320とエンコーダ330を付加したもの
をとり上げている。連想メモリ310は検索文字列を記憶
する。すなわち、検索文字列の各文字コードを先頭から
番地順に貯える。ｉ番地にｉ番地の文字コードX_iを記憶
した連想メモリに対して、入力テキスト文字列の時刻ｔ
で文字コードＸ（ｔ）がX_iに等しい時にはｉ行目の比較
器316からy_i＝“1"が出力される。X_iに等しくない時に
はy_i＝“0"が出力される。

順序論理回路320の中にはフラグビットのフリップフ
ロップFF_iのアレイがANDゲート325によって連結されて
いて、ｉ番目のANDゲート325にはFF_i-1の内容（フラグ
ビット）S_i-1と連想メモリ310のｉ行目比較器315の出力
y_iが入力されている。そして、ｉ番目のANDゲート325の
出力がFF_iにセットされ、その内容S_iが１ということは
テキスト文字列が検索文字列のｉ番目の文字まで一致し
てきた事を意味する。FF₁には検索文字列の１番目の文
字がテキスト文字列に含まれて入力された時に“1"に設
定される。検索文字列の長さがｎであるとするとS_nが
“1"になるか否かをチェックする事によって文字列の一
致があったか否かを判別できる。

第３図では検索文字列が可変長である場合にうまく対
応できるように、デリミタ・フリップフロップDF_iが導
入されている。検索文字列のスタート位置を任意にする
と、エンコーダ330の入力本数が多すぎるために、４行
置きに検索文字列の登録位置を指定できる。そのため
に、DF₀,DF₄,DF₈,DF₁₂とDF₁₆にフラグビットのイニシャ
ルセットを行うデリミタ信号を設定できるようにしてい
る。

連想メモリ310の中には１例として、ABCD,CAT,DONKEY
の３つの検索文字列の登録例が示されている。４文字に
等しい場合、それより短い場合と、４文字より長い場合
にデリミッタ信号どう設定するかというと、一般に、検
索文字列の登録の始まりの行と終わりの行のデリミッタ
・フリップフロップに“1"をセットする。図中ではわか
りやすいように、“1"のセットされたDFに斜線を施し
た。すなわち、ABCDに対して、DF₀とDF₄に“1"をセット
し、CATに対してDF₄とDF₇に“1"をセットし、DONKEYに
対してDF₈とDF₁₄に“1"をセットしてある。

始まりの行のデリミッタ・フリップフロップDF₀,DF₄,
DF₈の“1"はフラグビットフリップ・フロップFF₀,FF₄,F
F₈の出力信号に論理的に加算しされる。それによって、
フラグビットのイニシャルセットが行われる。検索文字
列の最後を示す行のデリミタ・フリップフロップDF₄,DF
₇,DF₁₄はフラグビットがFF₄,FF₇,FF₁₄に到達したか否か
をORゲートOG₁,OG₂,OG₄を通してエンコーダ330に伝達す
るために使われる。フラグビットがFF₄,FF₇,FF₁₄に到達
するという事によって、テキスト文字列が検索文字列に
対して始めから終わりまで一致した事を示す。故に、OR
ゲートOF₁,OG₂,OG₃,OG₄の中のいずれかで“1"が出力さ
れる事は文字列マッチのあった事を意味する。ここに、
DONKEYを登録した場合に、DONKの４文字分の照合結果が
OG₃から出力されないのは、DF₁₂に“1"をセットしてい
ないからである。つまり、DONKEYの最後まで一致しない
時にはマッチ信号を出さないようにDF₉からDF₁₃までを
“0"にしている。

このように、文字列照合回路は連想メモリ310はデリ
ミタ・フリップフロップ付きの順序論理回路320とエン
コーダ330を付加する事によって実現できる。マッチ信
号はOG₁,OG₂,…,OG₄,…のオアゲートの出力の論理和の
形で出力端子331から、また入力テキスト文字列がどの
検索文字列に一致したかを示すクラスコードが出力端子
332から送り出される。テキスト文字列の各成分が連想
メモリ310に入力されると、そこに貯えられた検索文字
列の全文字コードと一斉に比較が行われ、入力クロック
の周期内にエンコーダ330から応答結果が出力される。

第１図から第３図までの説明で文字列照合手段110の
中の連想メモリ310、第１記憶手段140、第２記憶手段17
0はそれぞれ文字コード、検索結果のマークビットやマ
ッチしたレコードのアドレスデータを随時に高速に書き
込める事、それ等を高速に読み出せる事を前提とした
が、代わりに電源停止の時に記憶内容が削減してしま
う。したがって、連想メモリ310の内容、第１、第２の
記憶手段の記憶内容はテキストファイル装置130の一部
に格納され、電源投入時に、テキストファイル装置130
からこれらのメモリに記憶内容がロードされる事が望ま
しい。そのためにも、第１図の学習型文字列検索装置に
は文字列照合手段110、第１記憶手段140や第２記憶手段
170に過去の検索条件や検索結果のデータを初期設定す
るイニシャライスモードが用意されていなければならな
い。

イニシャライズモードでは、まず、過去に登録された
検索文字列がリセット後の文字列照合手段110に順次に
登録され、次に、各検索文字列に対するマークビットデ
ータが第１記憶手段140に１行目から順に書き込まれ
る。第２図の第１記憶手段140のアドレスカウンタ143は
各行のマークビットの個数までカウントするとゼロに戻
るようにセットされ、過去の検索結果に相当するデータ
ビットを順次に書き込んでいく。

すなわち、第２図における書き込みデータスイッチ14
7は入力端子148からマークビット“1"を、入力端子149
からデータビットを、第１記憶手段140への書き込み信
号として受け付ける部分である。イニシャライズモード
の時には入力端子149側の方にスイッチが倒れ、テキス
ト情報全文検索時は入力端子148側の方にスイッチが倒
れる。

第２記憶手段170への過去の検索でマッチしたレコー
ドアドレスに関するテータの書き込みは入力端子173か
らR/W（read/Write）回路172を介して行われ、書き込み
アドレスはアドレスカウンタ175からオアゲート176を介
して与えられる。アドレスカウンタ175の内容は入力端
子174から与えられる書き込みクロック信号によってイ
ンクリメント（＋１ずつ増や）される。

以上によって、文字列照合手段110の連想メモリ310、
第１記憶手段140、第２記憶手段170への初期状態（過去
の検索条件と検索結果）の設定が達成される。

第１図の学習型文字列検索装置はイニシャライズモー
ドの他に、新検索文字列が過去の検索文字列（連想メモ
リ310に登録ずみの文字列）に一致しない時に新検索文
字列を文字列照合手段110の連想メモリ310に追加登録す
る検索文字列登録モードと、その後で、文字列照合手段
110にテキストファイル装置130からテキスト文字列を入
力し、検索文字列を含んだテキストレコードをマークし
て第１記憶手段140と第２記憶手段170に検索結果を書き
込む（または検索結果の記憶内容を書き直す）テキスト
文字列検索モードと、検索条件論理と検索文字列をそれ
ぞれ検索条件照合手段150と文字列照合手段110を入力
し、文字列照合手段110の出力によってアクセス番地の
決まる第１記憶手段140の出力を検索条件照合手段で処
理する検索条件照合モードと、その結果を用いて第２記
憶手段170から検索条件にマッチしたテキストレコード
の格納番地を出力する検索結果出力モードとがある。各
モードでの動作はすでに説明した通りである。

これらの動作モードによって学習型文字列検索装置は
過去の検索結果を利用してテキスト情報全文サーチの回
数を大幅に削減できる。そのためには、まず、電源投入
後にイニシャライズモードでメモリへのデータの初期設
定が行われる。次に新検索条件が検索結果出力モードで
与えられる。その時の検索文字列はA,B,CとかＤではな
く、具体的にはそれぞれ、Magnetic,Memory,Materialと
かThin−filmのように与えられ、検索条件式も単に＋
Ａ）＊）＋Ｃ）＊Ｄ）＝でなく、＋Magnetic）＊▲
▼）＋Material）＊Thin−film）＝のように
与えられる。条件論理は検索条件照合手段150へ、文字
列の方は文字列照合手段110に与えられ、その出力でア
クセス番地の決まる第１記憶手段140の出力が論理演算
ユニット155で処理される。そしてカット“）”記号の
入力時にレジスタ156にセットされる。そして、＝（イ
コール）記号が入力されると、レジスタ156の内容がエ
ンコードされ、第２記憶手段170からR/W回路172を介し
てマッチレコードの格納番地（レコードアドレス）が出
力される。

もし新検索条件が検索結果出力モードで入力されてい
る時に、文字列照合手段110がミスマッチ信号を発生す
る時は、その検索文字列をホストコンピュータ側のメモ
リに一時貯え、レジスタ146の内容をオール“1"にして
から、次の検索文字列の入力を受付け、ミスマッチがな
ければ、そのまま検索条件の照合を続ける。ミスマッチ
信号発生の都度、新検索文字列を一時的にホストコンピ
ュータ側のメモリに待避させる。検索条件の照合の終わ
った時点で検索結果を第２記憶手段170から出力するこ
とは可能であるが、ミスマッチの検索文字列を無視した
ものとなっている。１つでも新検索文字列が過去の検索
文字列にマッチすると、その文字列を含むテキストレコ
ードアドレスが求まり、検索対象に関する速報を提供す
ることができる。

次に、検索文字列登録モードに設定して、ホストコン
ピュータ側のメモリに一時的に待避させられたミスマッ
チの検索文字列を文字列照合手段110に追加登録する
と、その後は、テキスト文字列検索、モードによる全文
サーチで検索結果を第１記憶手段140と第２記憶手段170
に書き込める。その後、検索条件照合モードを経て検索
結果出力モードに戻ると、新検索条件にマッチしたレコ
ードアドレスが求まる。このような制御方式を採用する
と、新検索文字列が過去の検索文字列一致する限り、検
索条件が違っていても、テキスト情報の全文サーチなし
で新検索条件にマッチしたレコードアドレスを出力でき
ることになる。

（発明の効果） 以上のように新検索条件の検索文字列が過去の検索文
字列に等しくても検索条件式が異なるために、過去の検
索結果を利用できず、新たにテキスト情報の全文サーチ
を必要とするために検索要求の受付速度の高くならない
問題が本発明によれば容易に解決される。

学習型文字列検索装置では、検索要求受付が増えれ
ば、増えるほど、多くの検索文字列を文字列照合手段11
0に追加登録することが積み重なるために、新しい検索
条件に含まれるほとんどの検索文字列が文字列照合手段
110にすでに登録された検索文字列に一致するようにな
る。したがって、90％の検索文字列がマッチする（ヒッ
ト率90％）と考えると、全文サーチは10回の検索要求の
中で１回ですみ、99％がマッチすると、全文サーチは10
0回の検索要求に対して１回ですむ。テキスト情報全文
サーチに１分を要していたとすると、従来ならば、毎分
１階しか検索要求を受け付けられなかったが、本発明に
よれば、毎分10回とか100回も検索要求を受付できるよ
うになると言える。ヒット率は検索要求の条件の内容に
よるため、一概に高くなるとは言えないが、パーソナル
なテキストデータベースの検索においてはかなりの効果
が期待される。

【図面の簡単な説明】

第１図は本発明の一実施例を示す図、第２図は本発明の
第１記憶手段、検索条件照合手段と第２記憶手段の一実
施例を示す図、第３図は本発明の文字列照合手段の一実
施例の説明図である。 第１図において、110……文字列照合手段、120……文字
列スイッチ、140,170……記憶手段、150……検索条件照
合手段、第２図において、118……文字列マッチ信号、1
19……検索文字列識別コード入力端子、141,142……ア
ドレス・デコーダ、143……アドレスカウンタ、144……
フリップ・フロップ、145……マッチレコード・クロッ
ク入力端子、146……読出しデータ・レジスタ、147……
書き込みデータスイッチ、148……マークビット入力端
子、149……検索結果データ入力端子、151……セットパ
ルス入力端子、152……検索条件論理入力端子、156……
検索条件照合結果レジスタ、160……プライオリティ・
エンコーダ、161……検索結果トランスファ・パルス入
力端子、171……アドレスデコーダ、172……R/W回路、1
73……マッチレコードアドレスデータ入出力端子、174
……アドレスデータR/Wクロック入力端子、175……アド
レス・カウンタ、176……オアゲート。

Claims (2)

(57)【特許請求の範囲】
1. 【請求項１】複数検索文字列を記憶し、入力文字列が複
   数検索文字列のいずれに一致するかを判別する文字列照
   合手段と、どのテキストレコードがどの検索文字列を含
   むかを記憶し、前記文字列照合手段の判別する文字列の
   クラスコードによってアクセス番地の決まる第１記憶手
   段と、入力文字列間の検索条件論理に従って第１記憶手
   段の出力の論理処理を行う検索条件照合手段と、これに
   つながるエンコード手段と、照合のあった文字列を含む
   テキストレコードの格納番地を記憶し、エンコード手段
   の出力によってアクセス番地の決まる第２記憶手段と、
   検索文字列照合手段の入力文字列として検索文字列かテ
   キスト文字列を選択するスイッチ手段とを備える事を特
   徴とする学習型文字列検索装置。
2. 【請求項２】複数検索文字列を記憶し、入力文字列が複
   数検索文字列のいずれに一致するかを判別する文字列照
   合手段と、どのテキストレーコドがどの検索文字列を含
   むかを記憶し、前記文字列照合手段の判別する文字列の
   クラスコードによってアクセス番地の決まる第１記憶手
   段と、入力文字列間の検索条件論理に従って第１記憶手
   段の出力の論理処理を行う検索条件照合手段と、これに
   つながり、探索条件を満足するテキストレコードを指定
   するエンコード手段とを、前記テキストレコードの実際
   の格納番地を記憶し、前記エンコード手段の出力によっ
   てアクセス番地の決まる第２記憶手段と、前記文字列照
   合手段の入力文字列として検索文字列かテキスト文字列
   を選択するスイッチ手段とを備えた学習型文字列検索装
   置の制御方式であって、前記文字列照合手段と第１と第
   ２記憶手段にそれぞれ過去の検索文字列、文字列照合結
   果とテキストレコードの格納番地を初期設定するイニシ
   ャライズモード、新検索文字列の中に検索文字列に一致
   しない検索文字列のあった時に、その検索文字列を文字
   列照合手段に追加登録する検索文字列登録モードと、文
   字列照合手段にテキスト文字列を入力し、検索文字列を
   含んだテキストレコードをマークして第１記憶手段及び
   第２記憶手段に書き込むテキスト文字列検索モードと、
   検索条件論理と検索文字列を検索条件照合手段と文字列
   照合手段に入力し、前記文字列照合手段の出力によって
   アクセス番地の決まる記憶手段の出力を検索条件照合手
   段で処理する検索条件照合モードと、その結果を用いて
   第２記憶手段から検索条件にマッチしたテキストレコー
   ドの格納番地を出力する検索結果出力モードとを備え、
   検索文字列照合モードで全新検索文字列と過去の検索文
   字列とのマッチがあった時は、検索条件照合モードと検
   索結果出力モードに移って、マッチしたテキストレコー
   ド格納番地を出力するように制御し、検索文字列照合モ
   ードでマッチのない時は、追加登録モードに移ってミス
   マッチ文字列を文字列照合手段に登録し、その後、テキ
   スト文字列検索モードに移って検索結果を第１記憶手段
   と第２記憶手段に書き込み、その後、検索条件照合モー
   ドを経て、検索結果出力モードでマッチしたテキストレ
   コードの格納番地を出力するように制御する事を特徴と
   する学習型文字列検索装置の制御方式。