JPH0272481A - 論理式による文字列検索装置及び同装置の制御方式 - Google Patents

Abstract

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

Description

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

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

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

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

そこで、本願の発明者等は任意の長さの文字列を複数個
記憶する連想メモリ部と入力文字列の各文字に対する連
想メモリ部の文字比較結果を並列に受付けて、入力文字
列と記憶文字列間の文字の並び（順序）の比較を行なう
順序ロジック部とで文字列照合を可能とする構成の記号
列識別装置の特許出願を行った。名称が異なるが、以上
の装置が文字列検索装置の基本要素となる。（特開昭６
０−２１１５３９号公報（特願昭５９−０６８４９５号
明細書）、特開昭６１−２５３５３６号公報（特願昭６
０−９６２１３号明細書）など）このような文字列検索
装置は検索したいキーワード（検索文字列）を登録した
後、被検索テキスト文字列を入力すると、テキスト文字
列が検索文字列のいずれかに一致した時にマツチ信号を
発生し、テキスト文字列のどの部分がどの検索文字列に
マツチしたかを出力する。したがって、キーワードのつ
いていないテキスト文字列データの全文検索（フルテキ
ストサーチ）が可能となる。すなわち、ファイル記憶さ
れるテキスト文字列情報にキーワードを付加するなどの
作業を伴わないで、テキストファイル情報をデータベー
ス化できる。

しかしながら、全文検索（フルテキストサーチ）方式に
よる情報検索は、キーワードを付加したテキスト文字列
データのキーワード部分のみの検索で検索条件にマツチ
したテキスト文字列情報のファイル格納位置をみつけ出
すインデックスサーチ方式に比べて、はるかに長い検索
時間を必要とする。検索条件論理式の照合を考え合わせ
ると、さらに検索処理速度が低下する。ソフトウェアの
力を借りて照合を行なう場合には、速度低下が顕著とな
り、フルテキストサーチ方式の実用化が困難になる。

（発明が解決しようとする課題） 従来の文字列検索装置は検索条件の論理式に含まれるキ
ーワード（検索文字列）とテキストデータの文字列との
照合を行なうのみで、検索条件の論理式に合っているか
の照合についてはソフトウェア（プログラム）の助けを
借りていた。そのために、文字列照合は高速に達成され
ても、検索条件の論理式に合ったか否かの判定までの時
間は長ずざるという問題があった。

また、１つの検索条件理論式ではそこに含まれる検索文
字列に多くの同義語（シノニム）があって、検索要求に
合ったテキストレコードを見つけ出せない。そのような
事のないように、同義語の検索文字列を全て登録し、且
つ、それ等を含む検索条件の論理式を積和標準形で表わ
すと、積項の数が非常に多くなり、それを登録するハー
ドウェア量が多くなりすぎるという問題があった。

本発明の目的は上記２つの問題を解決する文字列技術を
提供することにある。

（課題を解決するための手段） したがって、本発明は複数検索文字列を記憶し、テキス
トレコードの入力文字列が複数検索文字列のいずれに一
致するかを判別する文字列照合手段と、前記文字列照合
手段の出力によってアクセス番地が決まり、各検索文字
列に関連づけられる概念コードを貯える第１記憶手段と
テキストレコード単位でどの概念コードが含まれたかを
一時記憶するマークビットレジスタと、前記マークビッ
トレジスタの出力によってアクセス番地が決まり、検索
条件の論理式を記憶する第２記憶手段とを備えた論理式
による文字列検索装置であって、この文字列検索装置の
制御方式は論理式に含まれる検索文字列とその概念コー
ドを対応づけて文字列照合手段と第１記憶手段に登録す
る文字列初期登録プロセスと、積和標準形に変換された
論理式の各積項に真（否定でない形）で含まれる検索文
字列に対する文字列照合手段と第１記憶手段の出力とマ
ークビットレジスタを用いて、第２記憶手段のアクセス
番地を決め、積項順に真の論理信号を書込んで行く論理
式初期登録プロセスと、新しい論理式に含まれる検索文
字列が文字列照合手段に登録された検索文字列にマツチ
しない時に、それを新検索文字列とし、その概念コード
と対応づけて文字列照合手段と第１記憶手段に追加登録
する検索文字列追加登録プロセスと、新しい論理式の各
積項に真で含まれる検索文字列に対する文字列照合手段
と第１記憶手段の出力とマークビットレジスタを用いて
、第２記憶手段のアクセス番地を決め、別の記憶領域に
積項順に真の論理信号を書込んで行く論理式追加登録プ
ロセスとを含む登録制御を行なう事を特徴とする。さら
に、上記の文字列検索装置の制御方式は検索条件論理式
を登録した後の全文検索に際して、文字列データをテキ
ストレコード単位で順次に文字列照合手段で受付け、文
字列マツチングのあった時に、第１記憶手段をアクセス
し、その出力をマークビットレジスタに設定する文字列
照合プロセスと、テキストレコードの切替り目にマーク
ビットレジスタの出力を用いて第２記憶手段をアクセス
し、論理式に対する照合結果を出力する論理式検索プロ
セスと、第２記憶手段のアクセス後に登録概念コードと
対応したマークビットレジスタのみをリセット状態に戻
し、残りをマークされた状態のままとするリセットプロ
セスとを含む検索制御を行なう事を特徴とする。

（作用） 本発明では検索条件論理式を登録でき、それを登録した
後でテキストファイルメモリの文字列データ全文を検索
し、ソフトウェアを介さないで論理式にマツチしたテキ
ストレコードを見つけ出す事ができる。

また、本発明は同義語（シノニム）の多い文字列を含む
検索条件論理式を同義語の文字列を概念コードにまとめ
る事で、記憶手段への登録に要する記憶容量が少なくて
すむ。概念コードにまとめるとは例えば次のようなこと
である。ＧａＡｓを表現するのにＧａＡｓ、砒化ガリウ
ム、ガリウム砒素、ガリウムアーセナイド等の同義語が
あるが、これを例えば“００１０”といったコードに統
一することである。

概念コードを使った検索の一例として、５個の検索文字
列を含む検索条件論理式の登録を行なう場合を考えよう
。各検索文字列に５個のシノニムがあるとすると、５５
個の検索条件論理式が存在することになり、各論理式に
おける積項の数が２２５個になる。したがって、通常の
やり方では、２２５Ｘ５５個（約１０００億個）のメモ
リセルが１組の検索条件論理式の登録に必要である。概
念コードを利用すると、２５個の積項を持つ論理式を１
つ記憶すればよく、使用メモリセル数が２５個（３２個
）へ減る。これが検索条件論理式を積和標準形に変換し
て登録する効呆的な方法となる。以下、図面に従って、
本発明のより詳細な説明を行なう。

（実施例） 第１図に本発明の第１の実施例の構成を示す。文字列照
合手段１１０は連想メモリ（ＣＡＭ、コンテント・アド
レッサブル・メモリの略）と順序ロジック（ＦＳＡ。

ファイナイト・ステート・オートマトンの略）とエンコ
ーダとから成り、複数個の検索文字列を記憶でき、入力
文字列が複数個の記憶検索文字列のいずれに一致するか
を判別する。

第１記憶手段１２０は文字列照合手段１１０の出力によ
ってアクセス番地が決まり、各検索文字列に関連づけら
れる概念コード１２１のＸデコーダ１２３でのデコード
結果と検索文字列のＸデコーダ１２２でのデコード結果
との関係の有無に対応した１、０のビット情報の形で記
憶する。したがって、メモリマトリクス内は概念コード
の記憶の一例を示している。

文字列照合手段１１０が文字列Ａ１．Ｂ１．Ｂ２．Ｃ１
，Ｃ２，Ｄｌ。

Ｂ２．Ｂ３並びにＥ工を記憶しているとし、各々の概念
コードをＡ、　Ｂ、　Ｂ、　Ｃ／Ａ、　Ｃ／Ｂ、　Ｄ、
　Ｄ、　Ｄ並びにＥ／Ｆとしている。故に、文字列Ａ１
が与えられると第１記憶手段１２０の左第１列目から′
１″が出力され、文字列Ｂ１かＢ２が与えられると、左
第２列目から１１１１１が出力され、文字列Ｄ１かＢ２
かＢ３が与えられると、左第４列目から“１”′が出力
される。この出力をエンコーダ１２４でエンコードした
ものは概念コードを表わす。

文字列Ｃ１が与えられると、左第１列目と第３列目から
１″が出力されるが、これは文字列Ｃ１が２つの概念コ
ードＡとＣにまたがっている場合に起こる。

例えば文字列Ａ１を半導体、Ｃ１をＨＢＴとすると、概
念コードＡとしては、ＭＯＳ、バイポーラ等が考えられ
る。一方概念コードＣとしては化合物半導体、バイポー
ラ等が考えられる。つまりＣ１の概念コードはＡのバイ
ポーラと共通するわけである。３つ以上の概念にまたが
る事もこの第１記憶手段１２０では許される。そのため
に、第１記憶手段１２０は各文字列がどの概念に属する
かを示すエンコーダ１２４にプライオリティエンコード
機能を使う。２つ以上の概念にまたがる時にはプライオ
°リティエンコーダ１２４が優先度の高い方から順に概
念コード１２５を出力する。

第１記憶手段１２０に接続されたマークビットレジスタ
１３０は概念コードのデコーダ１３１と概念数に等しい
個数のレジスタ１３２から成る。レコードアドレスの変
更時点にリセット端子１３３から与えられるリセントパ
ルスで全レジスタ１３２の内容がゼロになる。その後で
、第１記憶手段１２０から概念コードが与えられると、
それをデコードする事で選択されるレジスタ１３２にマ
ークビット″１”がセットされる。これによって、検索
されているテキストレコードに含まれる全概念コードに
対応するマークビットの“１″がレジスタ１３２に次々
と書込まれる。

書込みが終わった時のレジスタ１３２の内容が第２記憶
手段１４０のアクセス番地を決定する。

第２記憶手段１４０は検索条件の論理式を積和標準形で
表現し、その積項をマークビットレジスタ１３０の出力
によってＸデコーダ１４１を介して選択される各番地に
対応させて、検索条件の論理式に含まれた積項に対応す
る番地に′１″を書込むことで、論理式の記憶を行なう
。いくつかの検索条件の論理式を記憶する第２記憶手段
１４０の中で論理式の選択をＸデコーダ１４２で行なう
。選択コード１４５で指定した論理式と第１記憶手段１
２０の出力する概念コードとの整合結果１４４はこの第
２記憶手段１４０がら出力される。

第２記憶手段１４０のメモリマトリクス１６０には３つ
の論理式の格納例が示されている。マークビットレジス
タ１３０から、Ｘデコーダに３つの概念コード（Ａ、　
Ｂ、　Ｃ）が与えられるとし、残りの概念コードは未登
録と仮定し、１に固定されているとしている。したがっ
て、図中のメモリマトリクス１６０の左端１行目カラ１
ｌｌＮ　ニ各を地ニＡＢＣ，ＡＢｍ、ＡＢＣ，ＡＢＣ，
八ＢＣ。

ＡＢＣ，ＡＥｒＣ，ＡＢＮ、　９．、カ割当テラｈ　ル
。一方、メモツマトリクスの１行目は論理式（ＡＢＣ）
を、２行目は論理式（ＡＢＣ十人ＢＧ）を、３行目は論
理式（λＵＣ）を記憶する場合の記憶状態を示している
。記憶値をｉ番地のｊビット目で凧、とすると、ｊ番目
のビット線には次の論理式が格納されることになる。

Ｗｌ、ＡＢＣ＋Ｗ２．ＡＢＣ＋Ｗ３．Ａ百Ｃ＋・・・Ｗ
、は１か０の論理信号であり、各テキストレコーダリ に対する希望の出力をそのテキストレコードに対する第
２記憶手段１２０の出力によって選択される番地に書込
む事によって決まる。

以上のような回路構成を実現すると、ここへの検索条件
論理式の登録と検索の制御は次のように行なわれる。ま
ず、第１に、論理式に含まれる検索文字列とその概念コ
ードを対にしてそれぞれ、文字列照合手段１１０と第１
記憶手段１２０に初期登録する。これを文字列登録プロ
セスと呼ぶ。勿論、初期登録の前には文字列照合手段１
１０と第１記憶手段１２０の記憶内容がクリヤされてい
るものとする。特に、第１記憶手段１２０の読み出し出
力がすべて“０″であるとする。クリヤの後、文字列照
合手段１１０に検索文字列を登録する時に合わせ、その
登録アドレスが第１記憶手段１２０のＸデコーダ１２２
に入力され、概念コードに対するＹデコーダ１２３の選
択するビット線に“１″を書込む事で概念コードの登録
を行なう。

第２に、積和標準形に表わされた論理式の中に含まれる
概念コード間の論理積項に対し、マークビットレジスタ
１３０の出力で選択された番地に“１″を初期登録する
。ただし、初期登録の前には第２記憶手段１４０のメモ
リマトリクスの記憶内容は論理信号０にクリヤされてい
るものとする。すなわち、登録前には Ｏｘ　Ａ−Ｂ−Ｃ＋　Ｏｘ　ｋ−Ｂ：Ｃ＋　Ｏｘ　Ａ−
Ｂ−Ｃ＋・・・・・であるが、論理式（ＡＢＣ＋　ＡＢ
Ｃ）を登録するには、ＩＸＡＢＣ＋０ＸＡＢＣ＋ＩＸＡ
−Ｂ−Ｃ・・・・・に標準化して、１番地と３番地に入
力端子１４３から与えられる論理信号１を書き込む。

多数の相異なる論理式を初期登録するには、論理式の選
択コードを第２記憶手段１４０のＹデコーダに与え、メ
モリマトリクスの上の行から下の行へ入力端子１４３か
ら与えられる論理信号１を順次に書き込んで行けばよい
。

検索条件の論理式の登録が終わった後、テキストデータ
ファイルメモリから文字列データを全文検索する。検索
制御は、まず検索条件の論理式を選択コード１４５によ
って指定し、次に文字列データ１５０をテキストレコー
ド単位（数１００Ｂから数ＫＢ）で順次にテキストデー
タファイルメモリから読み出して、文字列照合手段１１
０に入力する事からはじまる。文字列データ１５０が文
字列照合手段１１０に登録された検索文字列にマツチす
る都度、第１記憶手段１２０がアクセ′スされ、マツチ
した検索文字列の概念コードがマークビットレジスタ１
３０に送り出される。この制御を文字列検索プロセスと
呼ぶ。

マークビットレジスタ１３０はテキストレコード単位で
マツチした概念コードをデコードした後のマークピット
として貯える。登録概念コードに対応したレジスタ１３
０の内容はテキストレコードが切替る時にＯにリセット
される。他のレジスタ１３０の内容は１のままとする。

リセットされる直前に、第２記憶手段１４０がアクセス
され、マークビットレジスタ１３０の出力で選択される
番地の記憶内容（０か１か）が各テキストレコーダの検
索条件論理式に対する照合結果として出力される。これ
らの制御を論理式検索プロセスとリセットプロセスと呼
ぶ。全文検索処理の後で、検索条件の変更や追加が起こ
る。その時には次のプロセスが使われる。

まず、新しい検索条件論理式に含まれる検索文字列が文
字列照合手段１１０に登録済みの検索文字列とマツチし
ない時に、それを新検索文字列とし、その概念コードと
対応づけて文字列照合手段と第Ｊ記憶手段に追加登録す
る。文字列照合手段１１０における新検索文字列の登録
アドレスはその前に行なわれた検索文字列の登録後に決
められ、追加登録時まで保持されるものとする。一方、
第１記憶手段１２０への追加登録は文字列照合手段１１
０の新検索文字列に対する出力で選択される番地と入力
端子１２１から与えられる概念コードで選択されるビッ
ト列との交点に論理信号“′１″を書き込むことで達成
される。この制御は文字列追加登録プロセスと呼ぶ。

次に、新しい検索条件の論理式を第２記憶手段１４０に
追加登録する。そのためには、標準形で表わされた新検
索条件論理式を複数積項に分解し、各項に真で含まれる
検索文字列を順次に文字列照合手段１１０に与えて、照
合結果によって第１記憶手段１２０から出力される概念
コードを順次にマークビットレジスタ１３０に貯え、積
項毎の出力によって選択される番地の第２記憶手段１４
０に論理信号１を書き込んで行く。この時、Ｙデコーダ
１４２に与えられる選択コードは検索条件論理式が登録
済みのものと同一でない限り、新たに設定される必要が
ある。たとえば、論理式Ａ−Ｂ−Ｃ＋Ａ−Ｂ−Ｃを追加
登録する場合、まず始めに、概念コードＡ、　Ｂ、　Ｃ
に対応する文字列を文字列照合手段１１０に入力し、そ
れらに対する照合結果で第１記憶手段１２０からＡ、　
Ｂ、　Ｃの概念コードを出力し、それらをマークピント
レジスタ１３０に貯え終わると、それの出力で選択され
る番地の第２記憶手段１４０に論理信号１を書き込む。

次に、Ａ、Ｂに対応した文字列を文字列照合手段１１０
に入力し、第１記憶手段１２０からＡ、Ｈの概念コード
を出力し、それらをマークビットレジスタ１３０に貯え
終わると、それの出力で選択される番地の第２記憶手段
１４０に１を書き込む。２回の書き込み動作でＡ−Ｂ−
Ｃ＋Ａ−Ｂ−Ｃの登録を終える。この制御が論理式追加
登録プロセスと呼ばれる。

以上のように、制御方式は登録制御と検索制御に分かれ
、登録制御は文字列初期登録、論理式初期登録、文字列
追加登録と論理式追加登録の４つのプロセスから成り、
検索制御は文字列検索と論理式検索とりセントの３つの
プロセスから成る。

（発明の効果） 第１図に示した論理式による文字列検索装置の実施例の
説明でわかるように、本発明によれば、検索条件論理式
を積和標準形で表わし、それを積項順に登録することが
でき、且つ、検索文字列の表現にバラエティ−がある時
にそれを概念コードで代表して登録することができる。

さらに、テキストファイルメモリに貯えられた文字列デ
ータの全文検索に際しては、文字列照合だけでなく、各
テキストレコードが概念コードの論理式にマツチしたか
否かの判定結果をテキストファイルメモリの全文文字列
データを高速で連続読み出しながら出力できる。

本発明の効果は検索条件論理式を登録するに際して、論
理式を貯える第２記憶手段１４０の記憶容量を大巾に低
減できるという点と、テキストファイルメモリの文字列
データの論理式による全文検索を一括して高速に行なえ
る点にある。

検索条件論理式の登録に際して、検索文字列に多くの同
義語が存在すると、その都度、別の論理式として登録す
ると、第１の記憶手段１２０を削減できる代わりに、第
２記憶手段１４０の記憶容量が実大なものとなる。

例えば、１つの検索条件論理式に５個の検索文字列が含
まれるとし、各検索文字列が５個の同義語（シノニム）
を持つとすると、５５個（３１２５個）の組合せの検索
条件論理式が存在する。その時、２５個の検索文字列を
文字列照合手段１１０に登録すると共に、第２記憶手段
１４０のＸデコーダ１４１に２５ピントのアドレスコー
ドを与える必要があり、かつＹデコーダ１４２にはｌｏ
ｇ２３１２５以上、すなわち１２ビツトもの選択コード
を与える必要がある。メモリマトリクスのセル数は２２
５Ｘ３１２５個でなければならい。これは約１０００億
個に及び、実現不可能である。もし２５個の検索文字列
を５個の概念コードにまとめる第１記憶手段１２０を使
えば、第２記憶手段１４０はＸデコーダ１４１から５ビ
ツトのアドレスコードを受けて、１本のビット線に論理
式を貯えるので、使用メモリセル数は１２５個にすぎな
い。これは１０００億個に比べ、５億分の１以下である
。本発明を用いると論理式の個数が８０００個に増えて
も、ＩＭｂのＲＡＭチップ１個で対応できる。論理式が
６４個程度であるとすれば、ＩＭｂの１チプで概念コー
ドの数を１４個に増やせる。

１６個に増やすとしても４Ｍｂのチップ１個に収まる。

この効果は天文学的数字になる。

以上のように、本発明によれば、従来の文字列検索装置
での論理式による文字列データの検索にソフトウェアを
介在させる必要のある問題点が容易に解決される。

【図面の簡単な説明】

第１図は本発明の一実施例の構成図である。

Claims (3)

【特許請求の範囲】
1. （１）複数検索文字列を記憶し、テキストレコードの入
   力文字列が複数検索文字列のいずれに一致するかを判別
   する文字列照合手段と、前記文字列照合手段の出力によ
   ってアクセス番地が決まり、各検索文字列に関連づけら
   れる概念コードを貯える第１記憶手段と、テキストレコ
   ード単位でどの概念コードが含まれたかを一時記憶する
   マークビットレジスタと、前記マークビットレジスタの
   出力によってアクセス番地が決まり、検索条件の論理式
   を記憶する第２記憶手段とを備えたことを特徴とする論
   理式による文字列検索装置。
2. （２）請求項１記載の論理式による文字列検索装置の制
   御方式であって、論理式に含まれる検索文字列とその概
   念コードを対応づけて文字列照合手段と第１記憶手段に
   登録する文字列初期登録プロセスと、積和標準形に変換
   された論理式の各積項に真（否定でない形）で含まれる
   検索文字列に対する文字列照合手段と第１記憶手段の出
   力とマークビットレジスタを用いて、第２記憶手段のア
   クセス番地を決め、積項順に真の論理信号を書込んで行
   く論理式初期登録プロセスと、新しい論理式に含まれる
   検索文字列が文字列照合手段に登録された検索文字列に
   マッチしない時に、それを新検索文字列とし、その概念
   コードと対応づけて文字列照合手段と第１記憶手段に追
   加登録する検索文字列追加登録プロセスと、新しい論理
   式の各積項に真で含まれる検索文字列に対する文字列照
   合手段と、第１記憶手段の出力とマークビットレジスタ
   を用いて、第２記憶手段のアクセス番地を決め、別の記
   憶領域に積項順に真の論理信号を書込んで行く論理式追
   加登録プロセスとを含む登録制御を行なう事を特徴とす
   る論理式による文字列検索装置の制御方式。
3. （３）請求項１記載の論理式による文字列検索装置の制
   御方式であって、検索条件論理式を登録した後の全文検
   索に際して、文字列データをテキストレコード単位で順
   次に文字列照合手段で受付け、文字列マッチングのあっ
   た時に、第１記憶手段をアクセスし、その出力をマーク
   ビットレジスタに設定する文字列照合プロセスと、テキ
   ストレコードの切替り目にマークビットレジスタの出力
   を用いて第２記憶手段をアクセスし、論理式に対する照
   合結果を出力する論理式検索プロセスと、第２記憶手段
   のアクセス後に登録概念コードと対応したマークビット
   レジスタのみをリセット状態に戻し、残りをマークされ
   た状態のままとするリセットプロセスとを含む検索制御
   を行なう事を特徴とする論理式による文字列検索装置の
   制御方式。