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

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は情報処理システムの構成侠素に係シ、よシ具体
的には長大な記号列の中から特定の記号列を抽出する記
号列照合装置とこの照合方式に関するものである０ （従来技術とその問題点） 上記記号列照合装置はバタン認識システムでの特徴系列
の抽出、ワープロで作成された文章の原文ファイルから
のキーワードの抽出、言語翻訳の支援や通信文章の略文
の解読、図形、イメージ、テキスト等による非構造デー
タベースの構築に利用され、知能化されるこれらの情報
処理システムの形成に欠くことができ欧いものであるＯ
従来の記号列照合は汎用コンピュータのン７トウユアに
たよった逐次処理によるため、膨大な処　−現時間を必
要とし、小規模なものに限定されていた。また、単語毎
に区切られて構造化された記号列に照合対象が制限され
ていた。−例として、ｎ個の記号列からなるテキスト中
にｍ個の記号列からなるバタンかどこに有るかを調べる
場合には、ｍ　（ｎ−ｍ＋１　）回の照合処理を必要と
する。磁気ディスクや光ディスク等に格納されたｍ−１
０個の文字列のテキストから、ｎ＝１Ｏ”個の文字列の
文章を捜すには１０　回の照合処理を必要とする〇従っ
て、テキスト、イメージ、図形、音声等の大容量な原情
報による検索は非現実的であるため、予め原情報にキー
ワードを付加しての検索や表形式に構造化されたデータ
の検索に限定されていた。

また、記号列の構成要素の変動を許容する柔軟な記号列
照合に対して処理時間の長くなシすぎる欠点があった。

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

たとえば、第１図のテキストがｍｅｍｏｒｙ＋ｂｕｂｂ
ｌｅ等の記号列を含む論文であるかを知るためには、そ
のテキストの中でｍｅｍｏ　ｒ　ｙ　、　　ｍｅｍｏ　
ｒ　ｉ　ｅ　ｓやｂｕｂｂｌｅ等の記号列に整合する部
分があるか否かを検索する必要がある０そのような記号
列のテキストとの比較照合は従来のコンピュータとンフ
トウエアで対応させると、非常に長い時間ｋＭする〇 一般のＡ４サイズの英文はワード間のスペースを含める
と、約３０００文字分の長さになる。一方、比軸照合を
行なう記号列の長さはｍｅｍｏｒｙの場合も１）ＩＩ　
ｌ）　ｂ　Ｉ　ｅの杓合も６文字である０６文字と３０
００文字の記号列間の照合は一般にその積に等しいオー
ダの回数に及ぶ文字の比較全必要とする。マイクロプロ
セッサでの文字比較時間が１μｓｅｃであったとしても
、各記号列の検索に１８ｍ５ｅｃ　の時間がかかる。

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

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

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

（発明の構成） すなわち本発明は各記号で関連づりたピッドパクンで照
合記号列を記憶する記号列記憶手段と、記号列長記憶手
段と、それにより制御される第１の伝達手段と、この出
力を記号列記憶手段の各出力により選択的に出力する第
２の伝達手段と、この第１と第２の伝達手段を介して連
結された第１のレジスタアレイと、第１のレジスタアレ
イの各段のレジスタの出力を記号列長記憶手段の内容に
より選択的に出力する出力手段とを備えたことを特徴と
する記号列照合装置、さらに該装置の出力手段にエンコ
ーダ又はシフトレジスタを付加した記号列照合装置が得
られる０ （実施例） 第２図は本発明の第１の実施例の説明図である０この記
号列照合装置は長大な記号列となるテキストを逐次入力
し、その中に登録済みの記号列が含まれているか否か全
調べ、外部に伝達するものであシ、照合記号列をビット
バタンで記憶する記号記憶手段２１０と、照合記号列の
記号列長を記憶する記号列長記憶手段２５０と、それに
より制御される第１の伝達手段２７０と、記号列記憶手
段２１０の読取り出力によ勺制御される第２の伝達手段
２３０と、第１と第２の伝達手段２７０と２３０とで連
結されたレジスタ２４０から構成される第１のレジスタ
アレイと、記号列長記憶手段２５０の内容により第１の
レジスタアレイの各段のレジスタ２４０の内容を選択的
出力する出力手段２６０とからなる。

照合記号列の各記号は記号記憶手段２１０の各ビットに
記号に関連づけたビットバタンで格納される。このビッ
トバタンは記号で選択された番地のみ＠１′になってい
る。第２図の例では６ビツトの記号記憶手段２１０に’
ＡＢＡＢＢ’の５個の記号からなる照合記号列を格納し
ている。すなわち、記号“Ａ”で指定されるアドレスの
第１，３ピツトと記号゛１３”で指定されるアドレスの
第２．４．５ピツトにのみ１”が格納され、他は”０″
が格納される。記号列記憶手段２１０の第６ビツト目は
無視され、どのようなビットバタンか格納されてもよい
。

記号列長記憶手段２５０には照合記号列の記号列長が格
納される。記号列記憶手段２５０の内容は各相１の伝達
手段２７０に分配され、第１のレジスタアレイの各レジ
スタ２４０の内容を第２の伝達手段２３０に伝達するか
否かを制御する。図の例では１段目から４段目までの第
１の伝達手段２７０を通過状態にし、５段目の第１の伝
達手段２７０を非通過状態にする。記号列長記憶手段２
５０の内容はまた出力手段２６０にも供給され、第１の
レジスタアレイの特定のレジスタ２４０の内容を照合出
力端子２８０から発生するように出力手段２６０を制御
する。

図の例で社用１のレジスタアレイの第５段目の出力Ｑ５
が照合出力端子２８０に現われる０先に６兄明したよう
に、記号記憶手段２１０の番地ｔｉｉｄ号の種類に対応
し、その第１，３ビツトの読取り出力は記号″′Ａ″が
入力されたときのみ１′となり、第２．４，５ビツトの
読取り出力は＠Ｂ”が入力さｉｔだときのみ１′となる
。

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

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

これは第２図に示したように記号記憶手段２１０に”Ａ
ＢＡＢＢ”の照合記号列が格納され、そのアドレス人力
２１１にテキスト”　Ａ、　Ｂ　Ａ　Ｂ　Ａ　Ａ　ＢＢ
　Ａ、　Ｂ　Ａ　Ｂ　Ｂ　Ａ″の記号列が入力されたと
きの第１のレジスタアレイの各段レジスタ２４０の出力
Ｑ１〜Ｑ６を示している。第１のレジスタアレイの初段
の出力Ｑ１は記号″′Ａ”が入力されたときのみ“１”
となシ、また第２段の出力Ｑ２はＱｌが１で記号＠Ｂ”
が入力されたときにのみ′″１′となる。このようにし
て、照合出力端子２８０に出力されるＱ５はテキスト内
に照合記号列”ＡＢＡＩ３Ｂ’に等しい記号列が現われ
たときに１１”となる。この例では時刻’Ｉ’ｔｓにＱ
５が１′となるので、テキストの下線で示された記号列
が照合記号列に等しｂとわかる〇この例では記号記憶手
段２１０に格納された照合記号列”ＡＢＡＢＢ”のみ検
知しているが、テキスト内の記号列の１部が重複したシ
、欠けたシしても混同がなければ検知することも可能で
ある０たとえは、照合記号列の先頭が記号ｗ　Ｚ　ｓで
も良いとする場合には、記号記憶手段２１０の第Ｏビッ
トの記号２で指定される番地にも″１！格納しておくこ
とで、”　Ａ　Ｂ　Ａ、　１１　Ｂ″および”　Ｚ　Ｂ
　Ａ、　Ｂ　Ｂ　’″の両記号列を抽出できる。

この記号列照合装ｒｔけ単語等の意味を持つ記号列毎に
スペース等の区切り記号等がない記号列の照合も可能に
する。−）だ、同様な意味を有する異なる記号列の１！
α合も可能である。英＠１語、特に°名詞は単数形と復
数形で最終文字が異なる場合が多い０例えば１１１ｃｎ
Ｔｏ　ｒ　ｙ″は１１ｉｌ’ｌ形になると”ｍｅｍｏ　
ｒ　ｉ　ｅ　Ｓになる０この場合、照合記号列として“
ｍｅｎｌＯｒ：）”と”　ｍｅｍｏ　ｒ　ｉ　’すなわ
ち、”ｍｅｍｏｒ”の最後にｌＩｙ″と１１″の両記号
ケ付加した記号列を記憶しておくことでｂ　　”ｒｎｅ
ｍｏｒｙ”と”ｍｅｍｏｒｉｅｓ’の両記号列を照合で
きる。

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

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

複数の照合記号列は第２図と同様に記号に関連づけだビ
ットパタンで記号列記憶手段２１０に格納されている。

ここに格納されている複数の照合記号列の最後の記号に
対応する第２のレジスタアレイ４５０のレジスタには、
記号列の区切シを意味するマーカ（ここでは、＠１′が
区切＃）全意味するとする。）全格納させる。このマー
カは、マーカ入力信号４５１と共にＥ６２のレジスタア
レイ４５０へのマーカ書込みクロック信号４５２ヲ印加
することで直列に書込める。

Ｊ￥α合記号列の区切シを示す１”が第２のレジスタア
レイ４５０のＮ段のレジスタに格納されていると、第１
のレジスタアレイ４４０内のＮ段のレジスタの出力すな
わち内部信号は第２のアンドゲート回路４６０を介して
照合出力端子４８０に導き出される。一方、その内部（
Ｆ３号はオアゲート回路４７０により、次段のレジスタ
に伝達されず、第２のレジスタアレイ４５０のＮ段しジ
スタの出力がオアゲート回路４７０ヲ介して、Ｎ＋１段
の内部信号に使われる。すなわち、第１のレジスタアレ
イ４４０のＮ＋１段のレジスタへの内部信号は、記号列
記憶手段２１０の対応するピッ）（Ｎ−１−１ビツト）
の読取多信号が初期値となる。

このように、第２のレジスタアレイ４５０の内容により
、第１のレジスタアレイ４４０の任意のレジスタ内の内
部信号を照合出力端子４８０に専くことができ、また、
第１のレジスタアレイ４４０に任意に分割できる。従っ
て、記号列記憶手段２１０に任意の記号列長の複数の照
合記号列全格納でき、複数の照合記号列に関する並列照
合が可能となるつなお、第１．第２のアンドゲート回路
４３０．　４６０及びオアゲート回路４７０は各々内部
信号の第２の伝達手段、内部信号の出力手段、内部信号
の第１の伝達手段の機能を有するものならば、他のゲー
ト回路に置換えることも可能である。

第５図は本発明による別の実施例の説明図である。本実
施例は、第１図に示しだ記号列照合装置５００の照合出
力端子４８０につながるエンコーダを新だに導入するこ
とにより、入力された記号列の分類コード５２０ヲ出力
することが可能となる。いずれの照合出力端子４８０に
内部信号が致達していない時には、判別不能信号５２１
を出力する。このようなエンコーダ５１０はプライオリ
ティ・エンコーダの商品名で市販されている。分類コー
ド５２００ビツト数は照合出力端子４８０の個数を２Ｎ
とすると、Ｎビットとなり、記号列照合装置の出力端子
数を削減（〜、容易にＩ、ＳＴ化を実現できる。

また、エンコーダ５１００代シに照合出力端子４６０の
信号を並列に入力し、それを直列に出力するシフトレジ
スタに置換えることも可能である。

この場合、出力端子数が１個となりさらにＬ　Ｓ　Ｉ化
が容易になる。

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

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

１テツグで２５６種の記号から成る記号列を１２８クラ
スに分類することができる事はワープロで作成した文章
の原文ファイルからシーケンシャルに読出される記号列
文章の中から１２８個までのキーワード（記号列）の抽
出會−挙にやりとける事を意味する。従来は多数のキー
ワードの同時検索が困難であったから、上記チップのイ
ンパクトは大きい〇 この記号列識別装置はＯＣＲ装置や音声認識装置などバ
タン認識を行なうシステムにおける特徴系列の分類にお
いても役立つ。この記号列識別装置の１チツプＬＳＩ化
は言語翻訳に必要な辞書としても役立つ０このチップに
通常ＲＡＭ’を接続し、各記号列の分類コードに対応す
けて、単語の訳語に格納すると、１テツプにつき１２８
単語までの翻訳が記号列の入力の完了時に直ちに求まる
。記号列識別チップに接続される通常ＲＡＭには記号列
の分類コードに対応ずけて、各種の情報を格納すること
が可能であって、それによって、種々の記号列情報処理
機能が達成される。たとえば、記号列の分類コードに対
応すけ、単語の品詞コードや記号列の出現回数や記号列
文章に対する処理命令を格納すると、知識情報の収集や
整理が行ないやすくなる。

この記号列抽出装置の処理速度は、記号記憶手段２１０
に使われる半導体ＲＡＭのサイクルタイムＴｏが１つの
記号の処理時間にほぼ対応する。Ｔ。

’ｆｒ−１００ｎ　ｓとすると、１０　個の記号列のテ
キストに対する１０個の記号列による照合を１０秒で行
なえる。現状のソフトウェアによる照合では１０時間程
度を必要とするので、本発明の記号列照合装置は著しく
照合時間を短縮する。

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

【図面の簡単な説明】

第１図は記号列照合問題の説明図、本発明による記号列
照合装置の一実施例の説明図、第３図は第２図の動作説
明図、第１図は本発明による他の実施例の説明図、第５
図は本実施の別の実施例の説明図である。 ２１０・・・記号列記憶手段、２３０・・・第２の伝達
手段、２４０・・・レジスタ、４４０ｉ・・第１のレジ
スタアレイ、２５０・・・Ｗｔ２号列長記憶手段、２６
０・・・出力手段、２７゜・・・第１の伝達手段、４３
０・・・第１のアンドゲート回ｕ、　４５０・・・第２
のレジスタアレイ、４６ｏ・・・第２のアンドゲート回
路、４７０・・・オアゲート回路、５００・・・記号列
照合装置、５１０・・・エンコーダ。 ”＋Ｔ′Ａ５′’：、’ｐ・ｌ”ｌＺ＋ノ・ｊ’ｊ’、
７ｐ、（・。 第１図 第２図 第１図 第５図 手続補正書（方式） ％式％ １、事件の表示　　　昭和５９年　　特許願第１４８９
２４号２、発明の名称　　記号列照合装置 ３、補正をする者 事件との関係　　　　　　　出　願　人東京都港区芝五
丁目３３番１号 （４２３）　　　日本電気株式会社 代表古　関本忠弘 ４、代理人 （連絡先　日本電気株式会社特許部） ５、補正命令の日付　　昭和５９年１０月３０日（発送
日） ６、補正の対象　　図面の簡単な説明の欄７　補正の内
容 明細書第１８頁第１行目に１第１図は記号列照合問題の
説明図、本発明に」とあるのを「第１図は記号列照合問
題の説明図、第２図は本発明に」と補正する。

Claims (4)

【特許請求の範囲】
1. （１）各信号で関連づけたビットパタンで照合記号列を
   記憶する記号列記憶手段と、記号列長記憶手段と、それ
   により制御される第１の伝達手段と、この出力を記号列
   記憶手段の各出力により選択的に出力する第２の伝達手
   段と、この第１と第２の伝達手段を介して連結された第
   １のレジスタアレイと、第１のレジスタアレイの各段の
   レジスタの出力を記号列長記憶手段の内容により選択的
   に出力する出力手段とを備えたことを特徴とする記号列
   照合装置。
2. （２）前記記号列長記憶手段が第２のレジスタアレイで
   構成されることを特徴とする特許請求の範囲第１項記載
   の記号列照合装置。
3. （３）各記号で関連づけたビットパタンで照合記号列を
   記憶する記号列記憶手段と、記号列長記憶手段と、それ
   により制御される第１の伝達手段と、この出力を記号列
   記憶手段の各出力により選択的に出力する第２の伝達手
   段と、この第１と第２の伝達手段を介して連結された第
   １のレジスタアレイと、第１のレジスタアレイの各段の
   レジスタの出力を記号列長記憶手段の内容により選択的
   に出力する出力手段と、該出力手段に接続するエンコー
   ダ又はシフトレジスタとを備えたことを特徴とする記号
   列照合装置。
4. （４）前記記号列長記憶手段が第２のレジスタアレイで
   構成されることを特徴とする特許請求の範囲第３項記載
   の記号列照合装置。