JPH0527150B2

JPH0527150B2 -

Info

Publication number: JPH0527150B2
Application number: JP59148925A
Authority: JP
Inventors: Hachiro Yamada; Tsunesuke Takahashi
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1984-07-18
Filing date: 1984-07-18
Publication date: 1993-04-20
Also published as: JPS6128133A

Description

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

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

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

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

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

たとえば、第１図のテキストがmemory，
bubble等の記号列を含む論文であるかを知るた
めには、そのテキストの中でmemory，
memoriesやbubble等の記号列に整合する部分が
あるか否かを検索する必要がある。そのような記
号列のテキストとの比較照合は従来のコンピユー
タとソフトウエアで対応させると、非常に長い時
間を要する。

一般のA₄サイズの英文はワード間のスペース
を含めると、約3000文字分の長さになる。一方、
比較照合を行なう記号列の長さはmemoryの場合
もbubbleの場合も６文字である。６文字と3000
文字の記号列間の照合に一般にその積に等しいオ
ーダの回数に及ぶ文字の比較を必要とする。マイ
クロプロセツサでの文字比較時間が1μsecであつ
たとしても各記号列の検索に18msecの時間がか
かる。

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

〔発明の目的〕

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

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

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

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

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

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

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

照合記号列の各記号は記号記憶手段２１０の各
ビツトに記号に関連づけたビツトパタンで格納さ
れる。このビツトパタンは記号で選択された番地
のみ“１”になつている。第２図の例では11ビツ
トの記号記憶手段２１０に“ABABB”の５個の
記号からなる照合記号列を格納している。すなわ
ち、記号“Ａ”で指定されるアドレスの第１，３
ビツトと記号“Ｂ”で指定されるアドレスの第
２，４，５ビツトにのみ“１”が格納され、他は
“０”が格納される。但し、記号列記憶手段２１
０の第６ビツトは全アドレスに“１”を格納させ
る。従つて、それにつながるアンドゲート回路２
３０は第５番目の第１レジスタ２４５の内容Ｑ５
をそのまま第６番目の第１レジスタ２４５に供給
する。

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

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

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

第３図は第２図の記号列照合装置の動作説明図
である。これは第２図に示したように記号記憶手
段２１０に“ABABB”の照合記号列が格納さ
れ、そのアドレス入力２１１にテキスト
“ABABAABBABABBAB”の記号列が入力さ
れたときの第１のレジスタアレイ２４０の各段の
出力Ｑ１〜Ｑ６を示している。第１のレジスタア
レイ２４０の初段の出力Ｑ１は記号“Ａ”が入力
されたときのみ“１”となり、また第２段の出力
Ｑ２はＱ１が１で記号“Ｂ”が入力されたときに
のみ“１”となる。このようにして、照合出力端
子２８０に出力されるＱ６はテキスト内に照合記
号列“ABABB”に等しい記号列が現われたとき
に“１”となる。この例では時刻Ｔ１４にＱ６が
“１”となるので、それより一時刻前に入力され
た下線で示す記号列が照合記合列に等しいとわか
る。

この例では記号記憶手段２１０に格納された照
合記号列“ABABB”のみ検知しているが、テキ
スト内の記号列の１部が重複したり、欠けたりし
ても混同がなければ検知することも可能である。
たとえば、照合記号列の先頭が記号“Ｚ”でも良
いとする場合には記号記憶手段２１０の第０ビツ
トの記号Ｚで指定される番地にも“１”を格納し
ておくことで、“ABABB”および“ZBABB”
の両記号列を抽出できる。

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

この記号列照合装置は容易にLSI化が可能であ
るので低価格化をもたらし、また１個の記号を記
号列記憶手段、例えばICメモリのほぼサイクル
タイムで照合可能であるため、高速な記号列照合
を可能にする。また、種々の長さの記号列長の照
合記号列を取扱うことができる。また、照合出力
を発生する出力端子数が削減され、より容易に
LSI化を可能にする。

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

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

照合記号列は第２図と同様に記号に関連づけた
ビツトパタンで記号列記憶手段２１０に格納され
る。すなわち、照合記号列の記号で示される記号
列記憶手段２１０のアドレスにのみ“１”を書込
むことでその記号が格納される。照合記号列の記
号数が第１のレジスタアレイ４４０のレジスタ４
４５の個数Ｎより小さい場合には、記号列記憶手
段２１０に第１のレジスタアレイ４４０に対応し
てＭ個の照合記号列を格納できる。このとき、第
２のレジスタアレイ４５０の各レジスタ４５５に
は、Ｍ個の照合記号列を区切るマーカとして
“１”を格納する。このマーカはマーカ入力信号
４５１と共に第２のレジスタアレイ４５０へのマ
ーカ書込みクロツク信号４５２を印加することで
直列に書込める。また、照合記号列の記号数とＮ
との差に相当する記号列記憶手段２１０のビツト
には全てのアドレスに“１”を格納しておく必要
がある。例えば、第１のレジスタアレイ４４０の
レジスタ４４５の個数Ｎを８とし、そこに６文字
の照合記号列“memory”を格納する場合には、
記号列記憶手段の第１ビツト目と第２ビツト目の
全アドレスに“１”を格納し、第３ビツト目から
第８ビツト目に各々“ｍ”，“ｅ”，“ｍ”，“ｏ”，
“ｒ”，“ｙ”の記号に対応するアドレスにのみ
“１”を格納させる。このように格納すると、第
１のレジスタアレイ４４０内の第１段目と第２段
目のレジスタ４４５には、記号列入力端子２２１
から入力される記号にかかわらず常に“１”が保
持される。その結果、照合記号列“memory”に
等しい記号列が記号列入力端子２２１から入力さ
れたときのみ、“１”の内部信号が第１のレジス
タアレイ４４０内の最終段のレジスタ４４５に伝
達され、第２のアンドゲート回路４６０を介し
て、照合出力４８０が発生する。すなわち、レジ
スタ４４５の段数Ｎより短い記号列長の照合記号
列の照合が可能となる。

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

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

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

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

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

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

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

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

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

この記号列識別装置はOCR装置や音声認識装
置などパタン認識を行なうシステムにおける特徴
系列の分類においても役立つ。この記号列識別装
置の１チツプLSI化は言語翻訳に必要な辞書とし
ても役立つ。このチツプに通常RAMを接続し各
記号列の分類コードに対応ずけて、単語の訳語を
格納すると、１チツプにつき128単語までの翻訳
が記号列の入力の完了時に直ちに求まる。記号列
識別チツプに接続される通常RAMには記号列の
分類コードに対応ずけて、各種の情報を格納する
ことが可能であつて、それによつて種々の記号列
情報処理機能が達成される。たとえば、記号列の
分類コードに対応ずけ、単語の品詞コードや記号
列の出現回数や記号列文章に対する処理命令を格
納すると、知識情報の収集や整理が行ないやすく
なる。

この記号列抽出装置の処理速度は、記号記憶手
段に使われる半導体RAMのサイクルタイムTcが
１つの記号の処理時間にほぼ対応する。Tcを
100nsとすると、10⁹個の記号列のテキストに対す
る10³個の記号列による照合を10秒で行なえる。
現状のソフトウエアによる照合では10時間程度を
必要とするので、本発明の記号列照合装置は著し
く照合時間を短縮する。

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

【図面の簡単な説明】

第１図は記号列照合問題の説明図、第２図は本
発明による記号列照合装置の一実施例の説明図、
第３図は動作説明図、第４図は本発明による他の
実施例の説明図である。２１０……記号列記憶手段、２３０……第１の
伝達手段、２４０，４４０……第１のレジスタア
レイ、２４５……レジスタ、２５０，４５０……
第２のレジスタアレイ、２５５……レジスタ、２
６０……出力手段、２７０……第２の伝達手段、
４３０……第１のアンドゲート回路、４６０……
第２のアンドゲート回路、４７０……オアゲート
回路、４９０……エンコーダ。

Claims

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