JPS6128133A - 記号列照合装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は情報処理システムの構成要素に係り、よシ具体
的には長大な記号列の中から特定の記号列を抽出する記
号列照合装置とその照合方式に関するものである。

（従来技術とその問題点） 上記記号列照合装置はバタン認識システムでのへ゛￥徴
系列の抽出グワープロで作成された文章の原文ファイル
からのキーワードの抽出、言語翻訳の支援や通信文章の
略文の解読、図形、イメージ、テキスト等による非構造
データベースの構築に利用され、知能化されるこれらの
情報処理システムの形成に欠くことができないものであ
る。

従来の記号列照合は汎用コンピュータのソフトウェアに
たよった逐次処理によるため、膨大な処理時間を必要と
し、小規模なものに限定されていた。１だ、単語毎に区
切られて構造化された記号列に照合対象が制限さオ］て
いた。−例として、ｎ個の記号列からなるテキスト中に
ｍ個の記号列からなるバタンかどこに有るかを調べる場
合には、ｍ（ｎ　　ｍ＋１）回の照合処理を必要とする
。磁気ディスクや光ディスク等（で格納されたｍ＝１０
９個の文字列のテキストから、ｎ＝１０３個の文字列の
文章を抄すには１０１２回の照合処理を必要とする。従
って、テキストツイメージヌ図形ｙ音声等の大容量な原
情報による検索は非現実的であるだめ、予め原情報にキ
ーワードを付加しての検索や表形式に構造化されたデー
タの検索に限定されていた。まだ、記号列の構成要素の
変動を許容する柔軟な記号列照合に対して処理時間の長
くなシすぎる欠点があった。

さらに具体的に従来の記号列照合装置とその照合方式の
問題点について説明する。

第１図は記号列照合の対象となるテキストを示している
。このテキストは報告書の始めの部分を一例として示し
ている。このようなテキストはワープロのファイルメモ
リに多数個格納される。それ等のテキストの中から必要
なものをさがし出す時に、要求内容を示す単語によって
直接に検索できる詞１が求められる。

たとえば、第１図のテキストがｍｅｍｏｒｙ　ｒ　ｂｕ
−ｂｂｌｅ　％の記号列ケ含む論文であるかを知るため
には）そのデキストの中でｍｅｍｏｒｙ　ｚ　ｍｅｍｏ
ｒｉｅｓやｂｕｂｂｌｅ等の記号列に整合する部分があ
るか否がを検索する必要がろる。そのような記号列のテ
キストとの比較照合は従来のコンピュータとソフトウェ
アで対応させると、非常に長い時間を要する。

一般のＡ、サイズの英文はワード間のスペースを含める
と、約３０００文字分の長さになる。一方、比較照合を
行なう記号列の長さはｍｅｍｏｒｙの場合もｂｕｂｂｌ
ｅの場合も６文字である。６文字と３０００文字の記号
列間の照合に一般にその積に等しいオーダの回数に及ぶ
文字の比較を必要とする。マイクロプロセッサでの文字
比較時間が１μｍ１ｅＣであったとしても各記号列の検
索に１８　ｍｓｅ’ｃの時間がかかる。

現実に検索の対象となるテキストの文字数は１０°個に
及び、照合を行なう記号列の文字数も１００を越すこと
もあり得る。照合される記号列の数も１個だけでなく、
数１０個に及ぶ。その場合の照合時間は数１００時間に
及ぶ。故に、このような照合は現実的に不可能であり、
実除は人手により予めキーワードを抽出しておき、抽出
されたキーワードに対する照合に限定されていた。

〔発明の目的〕

本発明の目的は上記従来の記号列照合装置やその方式の
欠点を容易に解決し、テキスト２イメージを図形等の非
構造の記号列の中から任意の記号列を短時間にして、柔
軟な抽出が可能な記号列照合装置とその照合方式を提供
することにある。

まだ、本発明の他の目的は照合記号列の長さを任意に設
定可能な低価格な記号列照合装置を提供することにある
。

まだ、本発明の他の目的は出力端子数の少ないＬ　Ｓ　
Ｉ化が容易な記号列照合装置を提供することにある。

（発明の構成） 従って本発明によれば、各記号に関連づけだビットパタ
ンで複数の照合記号列を記憶する記号列記憶手段と、こ
の各出力につながる第１の伝達手段と、互いに隣接する
各レジスタ間が第１の伝達手段により連結された複数の
第１のレジスタアレイと、Ｉ！”＋接する各レジスタ間
が直列に接続された第２のレジスタアレイと、第２のレ
ジスタアレイの各段のレジスタの内容により、６第１の
レジスタアレイの出力を７′！ル択的に出力する出力手
段と、６第１のレジスタアレイの出力と第２のレジスト
アレイ内のレジスタの出力とを選択的に次の第１のレジ
スタアレイに伝達する第２の伝達手段とを含む記号列照
合装置及び該装置の出力手段にエンコーダ又はシフトレ
ジストが付加された記号列照合装ｆｉが得られる。

（実施例） 第２図は本発明の第１の実施例の説明図である。

この記号列照合装置は長大な記号列となるテキストを逐
次入力し、その中に登録した照合記号列が含１れている
か否かを調べ、外部に伝達するものであり、照合記号列
をビットバタンで記憶する記号列記憶手段２１０と、こ
の各出力につながる第１の伝達手段２３０となるアンド
ゲート回路と、互いに隣接する各レジスタ２４５間が該
アンドゲート回路２３０により連結された複数の第１の
レジスタアレイ２４０と、隣接する第２レジスタ２５５
間が直列姉接続された第２のレジスタアレイ２５０と、
第２のレジメ・タアレイ２５０の各レジスタ２５５の内
容により選択された第１のレジスタアレイ２４０の出力
を選択的に出力する出力手段２６０と、６第１のレジス
タアレイ２４０の出力と第２のレジスタアレイ２５０内
のレジスタ２５５の出力とを選択的に次の第１のレジス
タアレイ２４０に伝達する第２の伝達手段２７０とから
なる。

上段に位１賀する第１のレジスタアレイ２４０内には図
の例では６個の第ルジスタ２４５を含み、下段の第１の
レジスタアレイ２４０内には５個の第１のレジスタ２４
５を含む。６第１のレジスタアレイ２４０間はオアゲー
ト回路２７０とアンドゲート回路２３０とで連結されて
いる。記号の個数が６個以下の照合記号列を用いる場合
には第２レジスタの第１番目の第２レジスタ２５５に”
１″を格納させる。この場合、ｆＰ、１番目の第２レジ
スタ２５５につながる第２の伝達手段２７０は第１のレ
ジスタアレイ２４０の出力を通過させずに第２レジスタ
２５５の内容すなわち＠１″をアンドゲート回路に供給
する。従って、上段と下段に位置する６第１のレジスタ
アレイ２４０の入出力は分離される。また、上段の第１
のレジスタアレイ２４０は出力手段２６０を介して外部
に照合出力として出力される。

一方、７個以上の記号を有する照合記号列に対しては、
第２のレジスタアレイ２５０の第１段目と第２段目のｆ
４ｆＪ２レジスタ２５５に各々″０″と′１′を格納さ
せる。この場合、第２の伝達手段２７０は上段の第１の
レジスタアレイ２４０の出力を通過させ、アンドゲート
回路２３０に供給する。従って、上段と下段の第１のレ
ジスタアレイ２４０が連結される。また、出力手段２６
０は下段の第１のレジスタアレイ２４０の出力を照合出
力として通過させる。仁のように、７個以上の記号から
なる照合記号列に対しては、６第１のレジスタアレイ２
４０を連結させて用いる。この連結ハ第２のレジスタア
レイ２５０の内容により制御できる。

照合記号列の各記号は記号記憶手段２１０の各ビットに
記号に関連づけたピッドパクンで格納される。このビッ
トパタンは記号で選択された番地のみ”１″になってい
る。第２図の例では１１ビツトの記号記憶手段２１０に
”Ａ、ＢＡＢＢ″　の５個の記号からなる照合記号例を
格納している。すなわち、記号″Ａ”で指定されるアド
レスの第１ｆ３ビツトと記号″Ｂ”で指定されるアドレ
スの第：２ｊ４＋５ビツトにのみ１″が格納され、他は
０”が格納される。但し、記号列記憶手段２】０の第６
ビツトは全アドレスに１”を格納させる。

従って、それにつながるアンドゲート回路２３０は第５
番目の第ルジスタ２４５の内容Ｑ５をそのまま第６番目
の第ルジスタ２４５に供給する。

また、第２のレジスタアレイ２５０の第１番目の第２レ
ジスタには１″を格納させ、上段の第１のレジスタアレ
イ２４０の出力Ｑ　５　ｌｘ出力手段２７０を介して外
部に出力させる。

先にｉ兄明したように、記号記憶手段２１０の番地は記
号の種類に対応し、その第１．３ビツトの読取や出力は
記号゛Ａ”が入力されたときのみ１”となシ、第２ν４
，５ビツトの読取り出力は”Ｂ″が入力されたときのみ
”１″となる。また、第６ビツトの読取り出力は常に”
１”を発生する。

照合しようとするテキストを構成する記号は逐次記号記
憶手段２１０のアドレス人力２１１に印加され、その記
号に対応する番地の内容が読み出される。記号記憶手段
２１０の第１ビツトの読取多出力は内部信号として第１
のレジスタアレイ２４０の初段のレジスタ２４５に供給
される。他の読取り出力はアンドゲート回路で構成され
た内部信号の伝達手段２３０に供給され、レジスタアレ
イ２４０内の各段のレジスタ２４５に蓄積された内部信
号を次段のレジスタ２４５に伝達するか否かを制御する
。このレジスタアレイ２４０内の各段のレジスタ２４５
は、記号の入力毎に印加される同一のクロック信号２４
１で内部信号の取込みを行なう。内部信号は記号記憶手
段２１０のアドレス人力２１１に記号列”ＡＢＡＢＢ”
が入カネれたときにのみレジスタアレイ２４０の各段の
レジスタを通過し、出力手段２７０を介して特定のレジ
スタの内容が照合出力端子２８０から出力される。

第３図は第２図の記号列照合装置の動作説明図である。

これは第２図に示したように記号記憶手段２１０にＡＢ
ＡＢＢ”の照合記号列が格納され、そのアドレス人力２
１１にテキスト”ＡＢＡＢＡＡＢＢＡＢＡＢＢＡＢ″の
記号列が入力されたときの第１のレジスタアレイ２４０
の各段の出力Ｑ１〜Ｑ６を示している。第１のレジスタ
アレイ２４０の初段の出力Ｑ１は記号”Ａ″が入力され
たときのみ１”となり、まだ第２段の出力Ｑ２はＱｌが
１で記号″Ｂ”が入力されたときにのみ１′となる。こ
のようにして、照合出力端子２８０に出力されるＱ６は
テキスト内に照合記号夕じＡＢＡＢＢ”に等しい記号列
が現われたときに１″となる。

この例では時刻Ｔ１４にＱ６が“１”となるので、それ
より一時刻前に入力された下線で示す記号列が照合記合
列に等しいとわかる。

この例では記号記憶手段２１０に格納された照合記号列
″ＡＢＡＢＢ″のみ検知しているが、テキスト内の記号
列の１部が重複したシ、欠けたシしても混同がなければ
検知することも可能である。

たとえば、照合記号列の先頭が記号″Ｚ″でも良いとす
る場合には記号記憶手段２１０の第０ピツトの記号２で
指定される番地にも１”を格納しておくことで、ＡＢＡ
Ｂ　Ｂ”および”　ＺＢＡＢＢ″の両記号列を抽出でき
る。

この記号列照合装置は単語等の意味を持つ記号列毎にス
ペース等の区切り記号等がない記号列の照合も可能にす
る。また、同様な意味を有する異なる記号列の照合も可
能である。英単語、特に名詞Ｖ１：単数形と板数形で最
終文字が異なる場合が多い。例えば’　ｒｌｅｍｏｒｙ
”は複数形になるとｍｅ−ｍｏｒｉｅｓ　”になる。こ
の場合、照合記号列としてｍｅｍｏ　ｒ　ｙ”とｍｅｍ
ｏｒｉ　”すなわちＳ”ｍｅｍｏｒｙの最後に”ｙ”と
ｉ″の両記号を付加した記号列を記憶しておくことで、
”ｍｅｍｏｒｙ”と”ｍ　ｅｍ　−ｏｒｉｅｓ”の両記
号列を照合できる。

この記号列照合装置は容易にＬＳＩ化が可能であるので
低価格化をもたらし、また１個の記号を記号列記憶手段
、例えばＩＣメモリのほぼサイクルタイムで照合可能で
あるため、高速な記号列照合を可能にする。また、種々
の長さの記号列長の照合記号列を取扱うことができる。

まだ、照合出力を発生する出力端子数が削減され、よシ
容易にＬＳＩ化を可能にする。

第４図は本発明による記号列照合装置の他の実施例の説
明図である。この記号列照合装置は任意の記号列長の複
数の照合記号列を並列に照合できる。これを可能にする
ために、第２図の記号列記憶装置に使用した第２の伝達
手段２７０と第１の伝達手段２３０と出力手段２６０と
に各々対応するオアゲート回路４７０と第１のアンドゲ
ート回路４３０と第２のアンドゲート回路４６０と、さ
らに記号列記憶手段２１０と第１のレジスタアレイ４４
０と第２のレジスタアレイ４５０と出力手段としてのア
ンドゲート回路４６０に付加されるエンコーダ４９０と
から構成される。

第１のレジスタアレイ４４０はＭ個有シ、各々Ｎ個のレ
ジスタ４４５を含んでいる。各節」のレジスタアレイ４
４０内の各レジスタ４４５は第１のアンドゲート回路４
３０を介して連結され、各節１のレジスタアレイ４４０
はオアゲート回路４７０と第１のアンドゲート回路４３
０を介して接続される。第２のレジスタアレイ４５０は
第１のレジスタアレイ４４０の個数に対応するＭ個のレ
ジスタを含み、それらは直列に接続されている。

照合記号列は第２図と同様に記号に関連づけたビットバ
タンで記号列記憶手段２１０に格納される。すなわち、
照合記号列の記号で示される記号列記憶手段２１０のア
ドレスにのみ１″を書込むことでその記号が格納される
。照合記号列の記号数が第１のレジスタアレイ４４０の
レジスタ４４５の個数Ｎよシ小さい場合には、記号列記
憶手段２１０に第１のレジスタアレイ４４０に対応して
Ｍ個の照合記号列を格納できる。このとき、第２のレジ
スタアレイ４５０の各レジスタ４５５には、Ｍ個の照合
記号列を区切るマーカとして”１”を格納する。このマ
ーカはマーカ入力信号４５１と共に第２のレジスタアレ
イ４５０へのマーカ書込みクロック信号４５２を印加す
ることで直列に書込める。また、照合記号列の記号数と
Ｎとの差に相当する記号列記憶手段２１００ピツトには
全てのアドレスに”１”を格納して訃く必要がある。

例えば、第１のレジスタアレイ４４０のレジスタ４４５
０個数Ｎを８とし、そこに６文字の照合記号列”　ｍｅ
ｍｏｒｙ”を格納する場合には、記号列記憶手段の第１
ビツト目と第２ビツト目の全アドレスに”１″を格納し
、第３ビツト目から第８ビツト目に各々　ｍ″９″′ｅ
″　１　”　ｗＯ″ツ６ｒ″？”ｙ”の記号に対応する
アドレスにのみ１”を格納させる。このように格納する
と、第１のレジスタアレイ４４０内の第１段目と第２段
目のレジスタ４４５には、記号列入力端子２２１から入
力される記号にかかわらず常に”１″が保持され　　　
・る。その結果、照合記号夕１じｍｅｍｏｒｙ　″に等
しい６市袖列が記号列入力端子２２１から入力されたと
きのみ、”■”の内部信号が第１のレジスタアレイ４４
０内の最終段のレジスタ４４５に伝達され、第２のアン
ドゲート回路４６０を介して、照合出力４８０が発生す
る。すなわち、レジスタ４４５の段数Ｎよシ短い詫号列
長の照合記号列の照合が可能となる。

一方：記号列長がＮより大きい照合記号列に対しては、
２個以上の第１のレジスタアレイ４４．０にまたがって
照合記号列を格納する。このために、その第１のレジス
タアレイ４４０のつなが９に対応する第２のレジスタア
レイ４５０のレジスタ４５５に連続していることを意味
するＯ″を格納させる。この結果、”０”を出力する第
２のレジスタアレイ４５０のレジスタ４５５につながる
一オアゲー）・回路４７０は、第１のレジスタアレイ４
４０の最終段のレジスタ４４５の内容を次の策１のレジ
スタアレイ４４００Å力につながるアンドゲート回路４
３０に伝達する。すなわち、２個の第１のレジスタアレ
イ４４０が連わ１′、に接続されたことになる。とのよ
うに、第２のレジスタアレイ４５０内のレジスタ４５５
の内容により、各節１のレジスタアレイ４４０を直列に
接続しだシ、捷だ分離することができる。すなわち、第
１のレジスタアレイ４４０内のレジスタ４４５の段数Ｎ
の単位でそのレジスタ４４５・をっなけることできる。

このように第２のレジスタアレイ４５０の内容により、
任意の第１のレジスタアレイ４４０内の最終段のレジス
タ４４５内の内部信号を照合出力４８０に導くことがで
き、複数の第１のレジスタアレイ４４０を任意に分割、
接続ができる。従って、記号列記憶手段２１０に任意の
記号列長の複数の照合記号列を格納でき、その照合記号
列に関する並列照合が可能となる。

また、照合出力端子４８０の数は、第１のレジスタアレ
イ４４０の数Ｍで複数の第１のレジスタアレイ４４０内
のレジスタ４４５の１１１数のＮ分の１である。出力端
子数が少ないため、容易にＩ、Ｓ■化が可能となシ価格
低下をもたらす。

各照合出力４８０はエンコーダ４９０に導かれ、照合し
た記号列の分類コード４９】をエンコーダは発生する。

いずれの照合出力４８０もエンコーダ４９０に到達して
いない場合に、エンコーダ４９０は判別不能信号４９２
を出力する。このようなエンコーダ４９０はプライオリ
ティ・エンコーダの商品名で市販されている。分類コー
ト４９１のビット数は照合出力４８０の個数を２Ｎとす
ると、Ｎビットとなり、記号列照合装置の出力端子数を
削減し、容易にＬＳ’Ｉ化を実現できる。

また、エンコーダ４９０の代シに照合出力４８０の信号
を並列に入力し、それを直列に出力するシフトレジスタ
に鰺換えることも可能である。仁の場合、出力端子数が
１個となりさらにＬＳＩ化が容易になる。

々お、第１２第２のアンドゲート回路４３０゜４６０及
びオアゲート回路４７０は各々内部信号の第１の伝達手
段、内部信号の出力手段、内部信号の第２の伝達　手段
の機能を有するものならば、他のゲート回路に１１テ換
えることも可能である。

（発明の効果） 以上述べたように、本発明によれば従来の記号列照合に
おいて照合時間が掛かりすぎる問題を容易に解決した記
号列照合装置を実現できる。才だ一部の記号の誤りや変
化にも柔軟に対応できる照合が可能である。さらに、記
号列長が異なる複数の照合記号列を格納でき、それらを
並列に照合できる。従って、ハードウェアを効率的に利
用し、価格低下と照合時間の短縮をもたらす。

本発明の記号列照合装置は現状の２５６キロピツ）　Ｒ
ＡＭの半導体技術を用いれば、記号のコード長を８ビツ
トとすると、平均８個の記号列長の照合記号列を１２８
個を１チツプに収納でき、それらを並列に照合できる。

１チツプで２５６種の記号から成る記号列を１２８クラ
スに分類することができる事はワープロで作成した文章
の原文ファイルからシーケンシアルに読出される記号列
文章の中から１２８個寸でのキーワード（記号列）の抽
出を一挙にやシとけれる事を意味する。従来は多数のキ
ーワードの同時検索が困難であったから、上記チップの
インパクトは太きい。

この記号列識別装置はＯＣＲ装置や音声認識装置などバ
タン認識を行なうシステムにおける特徴系列の分Ｘ口に
おいても役立つ。この記号列識別装置の１チツプＬＳＩ
化は言語翻訳に必要な辞書としても役立つ。このチップ
に通常ＲＡＭを接続し各記号列の分類コードに対応すけ
て、単語の訳語を格納すると、１チツプにつき１２８単
語までの翻訳が記号列の入力の完了時に直ちに求まる。

記号列識別チップに接続される通常ＲＡＭには記号列の
分）頂コードに対応ずけて、各種の情報を格納すること
が可能であって、それによって種々の記号列情報処理機
能が達成される。たとえば、記号列の分’４’ａ４コー
ドに対応すけ、単語の品詞コードや記号列の出現回数や
記号列文章に対する処理命令を格納すると、知識情報の
収集や整理が行ないやすくなる。

この記号列抽出装置の処理速度は、記号記憶手段に使わ
れる半導体ＲＡＭのサイクルタイムＴｃが１つの記号の
処理時間にはぼ対応する。Ｔｃを１００　ｎｓとすると
、１０９個の記号列のテギス）Ｋ対する１０３個の記号
列による照合を１０秒で行なえる。現状のソフトウェア
による照合では１０時間程度を必要とするので、本発明
の記号列照合装置は著しく照合時間を短縮する。

以上まとめると、従来のマイコンとソフトウェアの組合
わせによる記号列の分類による処理時間の大きい事と柔
軟性に欠ける事の欠陥が容易に解決する。また、本発明
の記号列識別装置が１チツプのＬＳＩにまとまシ易い事
を考えると、このようなＬＳ’Ｉは文章の原文ファイル
からのキーワードの抽出や言語翻訳用の電子辞書やバタ
ン認識システムの特徴系列の分類において欠かすことの
できない機能素子になる。

【図面の簡単な説明】

第１図は記号列照合問題の説明図、第２図は本発明によ
る記号列照合装置の一実施例の説明図、第７図 第３図

Claims (4)

【特許請求の範囲】
1. （１）各記号に関連づけたビットパタンで複数の照合記
   号列を記憶する記号列記憶手段と、この各出力につなが
   る第１の伝達手段と、互いに隣接する各レジスタ間が第
   １の伝達手段により連結された複数の第１のレジスタア
   レイと、隣接する各レジスタ間が直列に接続された第２
   のレジスタアレイと、第２のレジスタアレイの各段のレ
   ジスタの内容により各第１のレジスタアレイの出力を選
   択的に出力する出力手段と、各第１のレジスタアレイの
   出力と第２のレジスタアレイ内のレジスタの出力とを選
   択的に次の第１のレジスタアレイに伝達する第２の伝達
   手段とを備えたことを特徴とする記号列照合装置。
2. （２）第１の伝達手段と出力手段がアンドゲート回路で
   あり、前記第２の伝達手段がオアゲート回路であること
   を特徴とする特許請求の範囲第１項記載の記号列照合装
   置。
3. （３）各記号に関連づけたビットパタンで複数の照合記
   号列を記憶する記号列記憶手段と、この各出力につなが
   る第１の伝達手段と、互いに隣接する各レジスタ間が第
   １の伝達手段により連結された複数の第１のレジスタア
   レイと、隣接する各レジスタ間が直列に接続された第２
   のレジスタアレイと、第２のレジスタアレイの各段のレ
   ジスタの内容により各第１のレジスタアレイの出力を選
   択的に出力する出力手段と、各第１のレジスタアレイの
   出力と第２のレジスタアレイ内のレジスタの出力とを選
   択的に次の第１のレジスタアレイに伝達する第２の伝達
   手段と前記出力手段に付加するエンコーダ又はシフトレ
   ジスタとを備えたことを特徴とする記号列照合装置。
4. （４）第１の伝達手段と出力手段がアンドゲート回路で
   あり、前記第２の伝達手段がオアゲート回路であること
   を特徴とする特許請求の範囲第３項記載の記号列照合装
   置。