JPH0554146B2 - - Google Patents

Description

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

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

（従来技術とその問題点） 従来の記号列抽出はマイクロコンピユータ等に
抽出プログラムを設定することによつて達成可能
であつたが、プログラムの逐次処理によるために
膨大な処理時間を必要とし、小規模なものに限定
された。また、従来は特開昭60−105039号公報に
記載されているように、単語毎に句読点やスペー
ス等の区切り符号で区切られて構造化された記号
列に照合対象が限定されていた。すなわち、ｎ個
の記号列からなるテキスト中にｍ個の記号列から
なるパタンがどこに有るかを調べるにはｍ（ｎ−
ｍ＋１）回の照合処理を必要とする。光デイスク
等に格納されたｍ＝10⁹個の文字列のテキストか
らｎ＝10³個の文字列の文章を捜すには10¹²回の
照合処理を必要とする。従つて、テキスト、イメ
ージ、図形等の原情報による検索は非現実的であ
るため、予め原情報にキーワードを付加しての検
索や表形式に構造化されたデータの検索に限定さ
れていた。

また、記号列の構成要素の変動を許容する柔軟
な記号列識別に対して処理時間の長くなりすぎる
欠陥があつた。

（発明の目的） 本発明は上記欠陥を解決するものであり、その
目的とする所はテキスト、イメージ、図形等の非
構造の記号列の中から任意の記号列を短時間に抽
出可能な記号列照合装置の制御方式を提供するこ
とにある。

（発明の構成） したがつて、本発明によれば、記号で指定され
た番地のみ値が異なるように記号列内の各記号を
記号記憶手段の各列に記憶させ、記号列の照合時
に記号を前記記号記憶手段のデコーダに入力し、
記号で示される前記記号記憶手段の番地の複数列
の内容を並列に読み取り、前記記号記憶手段の各
列の読み取り情報に基づきレジスタアレイ各段の
内容の伝達を制御し、前記レジスタアレイの特定
段の内容により入力された記号列内の特定の記号
列を抽出することを特徴とする記号列照合装置の
制御方式が得られる。

（構成に関する説明） 以下、図面を用いて本発明の更に詳細な説明を
行なう。

まず、第１図は言語翻訳のための電子辞書に格
納されるデータテーブルの一例を示す。このテー
ブルの第１欄の英単語は第２欄のアドレスを介し
て第３欄の日本語訳に変換されるとする。外部か
ら与えられる入力英単語が第１欄のどの英単語と
一致するかを見つける事がこの電子辞書での一番
難かしいプロセスであり、これが記号列照合の問
題である。

すなわち、入力英単語が第１欄のどの英単語と
一致するかを見つけるにはアドレス順に第１欄の
英単語を全部読取つて比較を行う事が最も楽であ
るが、時間がかかる。第１欄の英単語をアルフア
ベツト順に並べて、入力英単語の文字を見て、第
１欄の英単語のサーチの範囲を順次に絞るトリー
サーチが比較時間を短縮させるのに役立つ。

このような言語翻訳のための電子辞書は大容量
のメモリを持つマイコンによつて容易に実現され
ると考えられるが、英単語長や単語数の増加と共
に処理時間が大きくなりすぎる問題があつて広範
囲には使われていない。また英単語の入力ミスに
対して柔軟性のない点も問題となつて、使い難
い。

記号列抽出の機能は言語翻訳のための電子辞書
以外でも必要である。ワープロで作成された多数
の論文が磁気デイスクや光デイスクに原文のまゝ
でフアイルされていたとする。その原文フアイル
から著者が誰々であるような論文を捜すとか、
Computer SystemやData baseなどのキーワー
ドを含んでいるか否かを調べるとかが記号列抽出
の対象となる。

新聞社や出版社など情報発生の源となる所で印
刷される過去の記事や解説文など各種の文章は原
文のまゝでフアイルされるようになり、知識情報
社会の中で今までとは違つた形でアクセスされる
ようになる。すなわち、読者が過去に印刷された
書物を紙の形で保存しないで、端末から通信回線
とコンピユータを介して直接、原文フアイルへ知
識問合わせのアクセスを行うようになると考えら
れる。

知識問合わせのアクセスの際にはキーワードが
原文フアイルに設定され、そのキーワードを含む
箇所、またはその出典が検索されて、読者に送り
返えされるとする。この時の原文フアイルからの
キーワードの抽出が必要となる。多くのユーザか
らの知識問合わせに対して、多くのキーワードの
検索を並列に行なえることが重要であり、従来の
マイコンでは対応が困難である。

（実施例） 第２図は本発明の第１の実施例の説明図であ
る。この記号列照合装置とその方式は長大な記号
列となるテキストを逐次入力し、その中に登録済
みの照合記号列が含まれているか否かを調べ、外
部に伝達するものであり、照合記号列をビツトパ
タンで記憶する記号記憶手段２１０と、その読取
り出力により制御される内部信号の伝達手段２３
０と、これに連結されたレジスタアレイ２４０と
からなる。

照合記号列の各信号は、ランダムアクセスメモ
リ（RAM）等で構成される記憶手段２１０の各
ビツトに記号に関連づけたビツトパタンで格納さ
れる。このビツトパタンは記号で選択された番地
のみ“１”になつている。第２図の例では５ビツ
トの記号記憶手段２１０に“ABABB”の５個の
記号からなる照合記号列を格納している。すなわ
ち、記号“Ａ”で指定されるアドレスの第１、３
ビツトと記号“Ｂ”で指定されるアドレスの第
２、４、５ビツトにのみ“１”が格納され、他は
“０”が格納されている。記号記憶手段２１０の
番地は記号の種類に対応し、その第１、３ビツト
の読取り出力は記号“Ａ”が入力されたときのみ
“１”となり、第２、４、５ビツトの読取り出力
は“Ｂ”が入力されたときのみ“１”となる。

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

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

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

第４図は本発明の第２の実施例の説明図であ
り、より柔軟性の高い記号列を照合可能な記号列
照合装置について説明する。同図の記号列照合装
置は記号列記憶手段４１０と、この読取り出力を
符号化する複数のデコーダ４２０と、この出力に
より制御される複数の選択回路４３０と、この出
力を一時記憶するレジスタアレイ４４０と、これ
に供給されるクロツク信号４５１をデコーダ４２
０でマスクするアンドゲード回路４５０とからな
る。デコーダ４２０と、選択回路４３０及びアン
ドゲート回路４５０は第２図における内部信号の
伝達手段２３０に対応する。

第２図での記号列記憶手段２１０では、記憶情
報“１”をレジスタのシフト、“０”をクリアに
対応させていたが、第４図の記号列記憶手段４１
０にはレジスタアレイ４４０の内容のクリア、シ
フト、ホールド、バイパスを２ビツトで表現させ
ている。ここではデコーダ４２０は入力00、01、
10、11に対応して各々クリア制御信号４２１、シ
フト制御信号４２２、ホールド制御信号４２３、
バイパス制御信号４２４を出力する。クリア制御
信号４２１は選択回路４３０の出力をマスクし、
クロツク信号４５１の供給時にレジスタの内容の
クリアを行ない、シフト制御信号４２２は他に接
続されず、レジスタアレイ４４０をシフトレジス
タとして動作させる。ホールド制御信号４２３は
レジスタアレイ４４０の各段へのクロツク信号４
５１をマスクし、レジスタの内容を保持する。ま
た、バイパス制御信号４２４は選択回路４３０を
切換え、レジスタをバイパスさせる。

照合対象となるテキストが記号毎に記号記憶手
段４１０のアドレス入力に供給されると、その記
号で選択された番地の内容がデコーダ４２０に供
給され、レジスタアレイ４４０の制御が行なわれ
る。シフト、クリアだけでなくホールドあるいは
バイパスの機能を持たせると照合記号に柔軟性を
持たせることができる。例えば、“PROM”、
“Ｐ・ROM”、“RAM”、“ROM”のいずれの記
号列もテキストから検知したい場合、記号列記憶
手段４１０に図のようなビツトパタンを格納させ
ればよい。すなわち、記号列記憶手段４１０の第
１段の記号“Ｐ”、“Ｒ”、・に対応する番地に各々
にシフト、バイパス、ホールド動作を意味する
01、11、10を格納させ、さらに第２段の記号
“Ｒ”、第３段の記号“Ａ”、“”、第４段の記号
“Ｍ”に対応する番地にシフト動作を意味する01
を格納させている。

この状態で記号列入力端子４１１に記号を入力
すると共に、クロツク信号４５１を印加すると、
レジスタアレイ４４０の第１段の内容Ｑ１は記号
Ｐが入力されたときのみセツトされ、それに続き
記号“・”が入力されてもホールドされる。しか
し記号“Ｒ”が入力されると第１段のレジスタを
バイパスし、第２段のレジスタをセツトする。従
つて、最終段の選択回路の出力につながる照合出
力端子４５２は記号列“PROM”、“Ｐ・ROM”、
“ROM”あるいは“RAM”が入力されたときに
“１”を示すことになる。すなわち、入力された
テキスト内のいくつかの記号列を検知できる。

第２，４図の記号列照合装置は現在の半導体
VLSI技術を用いれば容易に１チツプに収容され
る回路から成つている。入出力端子数は記号コー
ドのビツト数とクロツク信号端子、照合出力端
子、電源系端子の和となるのでICメモリと同程
度になる。記号コードを８ビツトにすると、256
種類の記号が受付け可能になり、カタカナ、ひら
がな、アルフアベツト、特殊文字などを含ませる
ことが可能となる。この場合、１個の照合記号当
り256ビツトのメモリを必要とする。現状の
256kbRAMの技術を用いれば、１チツプで1024
列の照合記号列を取扱える。A4サイズの文章の
文字数は300文字程度であるので、A4数枚の文章
の照合が１チツプで可能となる。あるいは512ド
ツト×512ドツトで表現された画像１枚の照合や
4KHzのサンプリング周波数で８ビツトにコード
化された８秒間の音声情報の照合も１チツプで可
能となる。

また、キーワード等の短い記号列の抽出では、
１チツプで多数の照合記号列を取扱える。記号コ
ードのビツト数が８ビツト、照合記号列長が８個
ならば、128クラスの記号列を１チツプで並列に
抽出できる。

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

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

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

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

【図面の簡単な説明】

第１図は記号列照合問題の説明図、第２図は本
発明による第１の実施例の説明図、第３図は第１
の実施例の動作説明図、第４図は本発明による第
２の実施例の説明図である。 ２１０，４１０……記号記憶手段、２３０……
内部信号の伝達手段、２４０，４４０……レジス
タアレイ、４２０……デコーダ、４３０……選択
回路、４５０……アンドゲート回路。

Claims (1)

【特許請求の範囲】
1. １ 記号で指定された番地のみ値が異なるように
   記号列内の各記号を記号記憶手段の各列に記憶さ
   せ、記号列の照合時に記号を前記記号記憶手段の
   デコーダに入力し、記号で示される前記記号記憶
   手段の番地の複数列の内容を並列に読み取り、前
   記記号記憶手段の各列の読み取り情報に基づきレ
   ジスタアレイ各段の内容の伝達を制御し、前記レ
   ジスタアレイの特定段の内容により入力された記
   号列内の特定の記号列を抽出することを特徴とす
   る記号列照合装置の制御方式。