JPH061479B2

JPH061479B2 - 記号列識別装置

Info

Publication number: JPH061479B2
Application number: JP60108667A
Authority: JP
Inventors: 恒介高橋; 八郎山田; 肇永井
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1985-05-21
Filing date: 1985-05-21
Publication date: 1994-01-05
Anticipated expiration: 2009-01-05
Also published as: JPS61267130A

Description

【発明の詳細な説明】（産業上の利用分野）本発明は情報検索システム、パタン認識システム、機械
翻訳システムなどに使われる記号列識別装置に関するも
のである。

上記記号列識別装置は入力データ記号列（テキスト情
報）が情報検索システムのファイルメモリの中のどの登
録パタン記号列（キーワードなど）とどこで一致するか
を判別するデバイスであり、テキスト情報の内容検索に
欠かせないものである。入力データ記号列としてパタン
観測、特徴抽出の後の特徴コード列を受付け、パタン記
号列としてパタンカテゴリーごとの特徴コード列を貯え
る装置はパタン認識システムにおいて欠かせないもので
あり、入力データ記号列として外国語のテキストを受付
け、パタン記号列として単語を貯えるものは機械翻訳シ
ステムで必要な辞書となる。

（従来技術）テキスト情報の内容検索の最も代表的な方法はキーワー
ドとなるパタン記号列をメモリに貯え、テキストとして
データ記号列が入力される都度、パタン記号列の長さに
等しい窓から見えるデータ記号列と比較し、一致すれば
マッチ信号を出し、一致しなければ窓を１文字分進め
て、次の比較に移るやり方である。パタン記号列の長さ
が８文字で、８文字単位の記号列の比較時間が１usecで
あると、１パタン記号列当りの内容検索処理速度が１MB
／secになる。

この方法のマッチング処理プログラムを従来のコンピュ
ータで走らせる時の第一の問題はパタン記号列の個数と
共に内容検索の処理速度が低下する事であり、256個の
時の処理速度は４KB／ｓにすぎない。

第二の問題は８文字とか１６文字とかのデータ記号列と
パターン記号列の比較に際して、いずれか一方に一文字
でもエラーがあると永久にマッチ信号を出せない事であ
る。第二の問題を救済するために、１文字の誤字や付加
や脱字のタイプミスによって生じる変形パタン記号列を
全てメモリに格納して、データ記号列をのぞく窓を１文
字ずらす都度、データ記号列とパタン記号列及び変形パ
タン記号列との比較を行うようにすると、処理速度は変
形パタン記号列の個数と記号列の長さに反比例して減少
する。

８ビット記号コードを使う時の８文字記号列の変形パタ
ン記号列の個数は２×８×２^８すなわち約4000となる。
従って、４KB／ｓの処理速度は１Ｂ／ｓに下ってしま
う。

これまでに提案された解決策は連想メモリを用いる方
法、セルラーアレイを用いる方法と、ダイナミック・プ
ログラミング(DP)を用いる方法に分かれる。

連想メモリやセルラーアレイを用いる方法は第１の問題
を解決するのに有効であるが、第２の問題に対しては効
力をもたない。状態遷移表を用いる方法は第１の問題の
解決には寄与しないが、第２の問題の解決にはある程度
有効である。しかしそのための状態遷移表を作ってRAM
に書込んでおくことはかなり高度な知的作業を必要とす
る。ＤＰを用いる方法は第２の問題の解決に有効である
が、第１の問題に対しては余り有効でない。真の解決策
は２つの問題を解決できるものでなければならず、これ
までに発見されていない。ましてや、どの文字がエラー
したかを指摘できる記号列識別装置は提案されていな
い。

以上のように、従来技術だけでは、これから発展する知
識情報システムに必要なあいまいテキストの内容検索の
高速化が達成されない。

（発明の目的）本発明の目的は文字エラーを含むテキスト情報の内容検
索における上記２つの問題を解決する事にある。もう少
し詳しく言えば、本発明の第１の目的は入力データ記号
列と複数個のパタン記号列との一斉比較を可能にする技
術を提供する事、第２の目的は色々の長さのパタン記号
列の登録を可能にする技術を提供する事、第３の目的は
データ記号列またはパタン記号列のいずれかに記号の脱
落、ミスタイプや誤字の混入などがあっても検索を達成
可能にする技術を提供する事、第４の目的は何文字分の
エラーがあって完全一致に至らなかったかを検出可能に
する技術を提供する事、第５の目的は記号列識別装置は
１チップのLSIで実現させるために必要な入力ピン数の
低減を可能にする技術を提供する事にある。

（発明の構成）したがって、本発明によれば、以下の装置と制御方式が
得られる。すなわち、 (1)記号列を構成する記号コードで指定された番地に外
部信号を記憶する外部信号記憶手段と、この外部信号記
憶手段の各ビット線に対応して設けられ、特定記号コー
ドに対して前記各ビット線から読出される外部信号を保
持するデリミタ信号保持手段と、行列状に配列され、各
行が前記各ビット線に対応する複数個の内部信号保持手
段と、一般記号コードに対して各ビット線から読出され
る外部信号によって制御され、隣接する行の内部信号保
持手段を列毎に上下に結合する第１ゲート手段と、前記
外部信号によって制御され、隣接する列間の内部信号保
持手段を隣り合う３つの行毎で斜めまたは左右に結合す
る第２ゲート手段と、前記デリミタ信号保持手段の内容
によって制御され、各行の端列の内部信号保持手段に内
部信号を設定する内部信号供給手段と、前記デリミタ保
持手段の内容で指定された行の内部信号保持手段の内容
を列毎に区別して出力するスイッチ手段とを備えた事を
特徴とする記号列識別装置と、 (2)記号列を構成する記号コードで指定された番地に外
部信号を記憶する外部信号記憶手段と、この外部信号記
憶手段の各ビット線に対応して設けられ、特定記号コー
ドに対して前記各ビット線から読出される外部信号を保
持するデリミタ信号保持手段と、行列状に配列され、各
行が前記各ビット線に対応する複数個の内部信号保持手
段と、一般記号コードに対して各ビット線から読出され
る外部信号によって制御され、隣接する行の内部信号保
持手段を列毎に上下に結合する第１ゲート手段と、前記
外部信号によって制御され、隣接する列間の内部信号保
持手段を隣り合う３つの行毎で斜めまたは左右に結合す
る第２ゲート手段と、前記デリミタ信号保持手段の内容
によって制御され、各行の端列の内部信号保持手段に内
部信号を設定する内部信号供給手段と、前記デリミタ保
持手段の内容で指定された行の内部信号保持手段の内容
を列毎に区別して出力するスイッチ手段と、前記スイッ
チ手段からどの行の内部信号保持手段の内容を出力すべ
きかを指定するデリミタ信号位置記憶手段と、前記スイ
ッチ手段の出力信号によって前記デリミタ信号位置記憶
手段のアドレスコードを選択する識別コード出力手段と
を備えた事を特徴とする記号列識別装置と、 (3)前記記号列識別装置であって、登録する各パタン記
号列の後尾に特定記号を付加し、登録後に、前記特定記
号に対して各ビット線から出力される外部信号を前記デ
リミタ保持手段に設定することを特徴とする記号列識別
装置と、 (4)同じくデリミタ信号位置記憶手段にデリミタ信号位
置指定コードと合わせて任意の応答出力コードを格納
し、前記スイッチ手段の出力信号によって前記応答出力
コードの出力を選択するようにした事を特徴とする記号
列識別装置と、 (5)同じく各列における前記デリミタ保持手段の内容で
指定された全ての行の内部信号保持手段の内容の論理和
が“１”を示す時に、どの行の内部信号保持手段の内容
が"1"になったかを外部へ出力する事を特徴とする記号
列識別装置と、 (6)同じく各列における前記デリミタ保持手段の内容で
指定された全ての行の内部信号保持手段の内容の論理和
が"1"を示す時にのみ、整合のあったパタン記号列の識
別コードまたはそれに関連ずけられた応答出力コードを
出力する事を特徴とする記号列識別装置である。

（実施例）以下、図面を用いて本発明のより詳細な説明を行なう。

第１図は本発明の第１の実施例の説明図である。この図
に示された記号列識別装置は左半分の外部記憶手段１１
０と中央のデリミタ（区切り）信号保持手段１２０及び
内部信号供給手段１２５と左半分に行列状に配列され、
第１ゲート手段１４１と第２ゲート手段１４２で結合さ
れた第１列目レジスタ１３１と第２列目レジスタ１３２
から成る内部信号保持手段１３０と、各行のレジスタ13
1と１３２に接続された第１のスイッチ１５０と第２の
スイッチ１５５とから成っている。

外部信号記憶手段１１０はアドレスデコーダ１１２とそ
れによって選択されるワード線１１３とそれに交わる多
数のビット線１１４につながる読取り回路１１５と書込
み回路１１６とから成る。入力端子１１１はデータ記号
列の構成要素である記号コードを受付る部分である。

外部信号記憶手段１１０に登録されるパタン記号列は上
端のビット線から下へと１ビット線当り１記号の割で貯
えられる。パタン記号列のｉ番目の記号を登録するには
その記号コードで指定されたワード線に交わるｉ番目の
ビット線"1"を書込めばよい。

例えば、パタン記号列をＡＢＣＤ＊とすると、１番目ビ
ット線は記号Ａのコードで指定された番地（ワード線１
１３）が選択された時にのみ丸印で示された位置から
"1"を出力し、他の記号コードに対しては"0"を出力す
る。

同様に、２番目、３番目、４番目、５番目のビット線１
１４はそれぞれ記号Ｂ，Ｃ，Ｄ，＊の各コードに対して
"1"を、それ以外の記号に対して"0"を出力する。この時
の各ビット線から出力される出力信号"1"または"0"を外
部信号と定義し右側のレジスタ１３１，１３２を伝ぱん
する内部信号と区別しておく。したがって、外部信号記
憶手段１１０は以上の方法でパタン記号列ＡＢＣＤ＊を
記憶する。

なお、記号＊は登録される多数のパタン記号列を区切る
ための特定記号として使われている。

登録後に、イニシャライズ信号を入力端子165に与え、
入力端子１１１に特定記号(*)コードを入力すると、そ
れを検知した信号がアドレスデコーダ１１２からタイミ
ング制御回路１６０に進み、特定記号(*)コードに対し
て各ビット線の出力する外部信号をデリミタ信号保持手
段１２０に取込ませる。デリミタ信号保持手段１２０が
取込んだ外部信号が内部信号供給手段１２５を制御し、
デリミタ信号保持手段１２０の中味（外部信号）が"1"
であれば、内部信号供給手段１２５は絶えず"1"の内部
信号を発生するようになる。

内部信号記憶手段１３０はタイミング制御回路１６０か
ら記号コード入力の都度、内部信号のシフトクロックパ
ルスを受け付けて、第１ゲート手段１４１がオン状態に
あると、内部信号を上から下へ順にシフトする。第１ゲ
ート手段１４１がオフ状態にあると、内部信号は下へ進
まなくなり第１列目のレジスタ１３１から消え去る。第
２列目のゲート手段１４３は第１ゲート手段１４１と全
く同じ機能を果たす。

このような第１ゲート手段１４１，１４３のオン・オフ
を制御するのは外部信号記憶手段の各ビット線から出力
される外部信号である。ただし、内部信号供給手段１２
５の発生する内部信号"1"は絶えず１行下のレジスタ１
３１へ第１ゲート手段１４１を介して送り込まれる。例
えば、４番目のビット線１１４につながるデリミタ信号
保持手段１２０は"1"を保持し、内部信号供給手段125に
内部信号"1"を発生させる。第１図で言えば、その内部
信号"1"は絶えず、内部信号記憶手段１３０の第１列目
５行目や10行目のレジスタ131に送り込まれることにな
る。

このような状態の後で、データ記号列XYABCDE………が
入力端子１１１から与えられると、記号Ａ，Ｂ，Ｃ，Ｄ
の入力と共に、１，２，３，４番目のビット線１１４か
ら順次に"1"の外部信号がそれぞれ第１ゲート手段１４
１の１，２，３，４行目へ送り込まれる。それによっ
て、第１列目１行目のレジスタ１３１の中味の内部信号
"1"がレジスタ１３１の２，３，４，５行目へと進む。
なお、１行目のレジスタ１３１は、常に内部信号"1"を
ホールドしている。入力される記号がＡでない限り、１
番目のビット線１１４からの外部信号が"0"であるか
ら、その内部信号"1"は１列目では下へ進まない。

第２ゲート手段１４２は記号Ａに対する１番目ビット線
１１４からの"1"の内部信号によって１行目のレジスタ
１３１の内部信号"1"を２列目の３行目レジスタ１３２
へ移動させる。記号ＢやＣに対する１番目ビット線１１
４からの"0"の外部信号に対しては１行目レジスタ１３
１の内部信号"1"を２列目の１行目と２行目のレジスタ
１３２へ移動させる。

２列目のレジスタ１３２へ移った内外信号"1"は１列目
と同じようにゲート手段１４３を通してパタン記号列に
整合したデータ記号列の入力によって下へ移動する。

１列目のレジスタ１３２にあった内部信号"1"が２列目
に移る事はデータ記号列とパタン記号列との間に１文字
分の違いがあった場合に起る。このようにして、１文字
の誤字（ミスタイプ）や誤字の混入を２列目のレジスタ
１３２で救済する事が可能になっている。

すなわち、パタン記号列ＡＢＣＤ＊を登録した後で、デ
ータ記号列ＡＣＤが入力されると、１列目１行目のレジ
スタ１３１の中の内部信号"1"は記号Ａのコードの入力
によって、１列目２行目のレジスタ１３１と２列目３行
目のレジスタ１３２の両方へ進む。この理由はＡの次の
記号がＢかどうかの２通りを予想するからである。Ａの
次の記号がＣなら、２列目３行目のレジスタ１３２に進
んだ内部信号"1"が４行目へ進み、１列目２行目のレジ
スタ１３１の内部信号は１列目３行目へ進まないで消え
る。Ｃの次に記号Ｄが来ると、２列目４行目の内部信号
"1"が５行目へ進む。

このようにして、記号の脱落エラーを２列目のレジスタ
１３２で救済できる。

もしデータ記号列ＡＸＣＤやＡＸＢＣＤが入力される
と、記号Ｘに対する外部信号が"0"であるから、１列目
２行目のレジスタ１３１の中の内部信号"1"は記号Ｘの
入力によって、２列目２行目と３行目のレジスタ１３２
へ進み、１列目３行目のレジスタ１３１には進まない。
Ｘの次の記号がＢならば２列目３行目のレジスタ１３２
に進んだ内部信号"1"は消滅し、代りに、２列目２行目
のレジスタ１３２の内部信号"1"が３行目のレジスタ１
３２へ進む。Ｘの次の記号がＣならば、逆に２列目２行
目のレジスタ１３２の中の内部信号"1"が消滅し、代り
に２列目３行目のレジスタ１３２の内部信号"1"だけが
４行目のレジスタ１３２へ進む。

第１のスイッチ１５０は外部から指定されるモード信号
(Strict/lerror free)によって１列目のレジスタ１３１
の内容を出力したり、２列目のレジスタ１３１の内容を
出力したりできる。すなわち、Strict（厳格に一致）モ
ードでは、"1"を含むデリミタ信号保持手段１２０につ
ながるレジスタ１３１に内部信号"1"が達していたか否
かがデータ記号列の各記号の入力の都度、判別される。
一方、１error free（１エラー許容）モードでは"1"を
含むデリミタ信号保持手段１２０につながるレジスタ１
３２に内部信号"1"が到達していたか否かが各記号の入
力の都度、判別される。

第２スイッチ１５５は第１スイッチ１５０の出力信号を
シリアルに走査して出力する出力端子１５７と第１スイ
ッチ１５０のいずれかが"1"になったかどうかを出力す
る出力端子１５９とを持っている。全ての第１スイッチ
１５０と出力端子１５７との間を結合する部分にはマル
チプレクサ１５５が使われ、それは端子１５６から入力
されるアドレスコードによって選択される。全ての第１
スイッチ１５０と出力端子１５９との間にはオアゲート
１５８が使われ、全ての第１スイッチ１５０の出力信号
の論理和が作られる。詳細は第６図で説明される。

第１図の場合、内部信号保持手段１３０の行列が２列で
あるが、３列とか４列に増やされると、２文字エラーや
３文字エラーを救済するものになる。第１スイッチ１５
０にもマルチプレクサを用いると、入力データ記号列が
どのパタン記号列に対して何個の文字エラーで一致した
かを識別する事が可能になる。

第１図の記号列識別装置へのパタン記号列の登録は左端
の書込み信号シフトレジスタ１１７と書込み回路１１６
を用いて行なわれる。登録される多数のパタン記号列は
すべて一旦外部のバッファメモリに準備されるとする。

登録の前には、外部信号記憶手段１１０は書込みモード
にセットされ、全ビット線１１４の記憶内容がクリアさ
れるとする。さらに、書込み信号シフトレジスタ１１７
の先頭レジスタには入力端子１１８から書込み指令信号
"1"が設定されるとする。

書込み指令信号"1"は入力端子１１１から記号コードが
入力される都度タイミング制御回路１６０から来るシフ
トクロックパルスによって、書込み信号シフトレジスタ
１１７に沿つて下の方へシフトされるものとする。

登録時には、外部バッファメモリに用意されたパタン記
号列の各記号コードが順次に入力端子１１１から外部信
号記憶手段１１０に入力され、各記号コードで選択され
るワード線１１３と書込み指令信号"1"のあるレジスタ
１１７につながるビット線１１４との交点に外部信号の
"1"が書込まれる。書込み指令信号"1"が記号コード毎に
１ビット下へシフトすることによって、１ビット線１１
４当りに１記号コードの割で上から下へ順にパタン記号
列が書込まれる。

以上の登録が終った後、外部信号記憶手段１１０を読取
りモードにすると、入力データ記号列の各記号モードに
対して、全ビット線１１４から、その記号コードと登録
されたものとの一致があるかないかを示す外部信号が一
斉に出力される。そして、入力データ記号列の中に、登
録パタン記号列と同じ記号列が含まれている時には、
"1"を含むデリミタ信号保持手段１２０に対応した行の
レジスタ（内部信号保持手段）１３１か１３２に内部信
号"1"が到達している筈であって、それはマッチ信号と
して第１のスイッチ１５０を通して出力される。

今、記号コードを８ビット線１１３の本数が２５６本に
なる。１Ｍbitのメモリチップを使うと、ビット線１１
４の本数が4096になる。５文字長のパタン記号列なら１
チップに約800個、８文字長のものでも256個登録できる
とわかる。

第２図はパタン記号列の登録方法を示している。色々の
長さのパタン記号列をすき間なく登録する事を目的とし
て、登録時には各パタン記号列の後に特定記号（今の場
合＊）を付加する事を求めている。この特定記号はデリ
ミタ（区切り）記号とも呼ばれ、＊であってもブランク
であってもよい。

第２図(a)は４文字の記号列ＡＢＣＤを５文字のパタン
記号列ＡＢＣＤ＊に変えて登録すべき事を示し、第２図
(b)は５文字の記号列ＤＥＢＡＣを６文字のパタン記号
列ＤＥＢＡＣ＊に変えて登録すべき事を示している。

第２図(c)は第１図の外部信号記憶手段の中に登録され
る複数パタン記号列の一部を示している。これによっ
て、多数の記号列を特定記号＊で区切るだけで、長い１
つのパタン記号列として登録することが可能になる。

登録後、特定記号＊を入力した時に各ビット線１１４か
ら出力される外部信号はデリミタ信号と呼ばれるもの
で、タイミング制御手段１６０の働きによって、デリミ
タ信号保持手段に設定され、内部信号供給手段１２５の
制御に使われる。

第３図は第１図の一部の詳細説明図であって、内部信号
保持手段１３０の第１列目レジスタ131と第２目レジス
タ１３２およびそれ等を結合する第１ゲート手段１４
１，１４３と第２ゲート手段１４２の構成を中心に示し
たものである。

特に、第１ゲート手段１４１Ａ，１４１Ｂと143Ａ，１
４３Ｂおよび第２ゲート手段１４２Ａ，１４２Ｂがどの
ように実現されるかを示している。

第１ゲート手段１４１Ａ，１４１Ｂと１４３Ａ，１４３
Ｂは内部信号"1"を上から下へ伝達するか否かを決める
事と、内部信号"1"の取込みを行なうように、アンドゲ
ート３４１Ａ，３４３Ａとオアゲート３４１Ｂ，３４３
Ｂで構成されている。アンドゲート３４１Ａ，３４３Ａ
は左端の外部信号読取り回路１１５Ａから来る外部信号
が"1"の時に各列のｉ行目のレジスタ（たとえば１３１
Ａ，１３２Ａ）の内部信号を（ｉ＋１）行目のレジスタ
（たとえば１３１Ｂ，１３２Ｂ）へ進める役割を果す。

第２ゲート手段１４２Ａと１４２Ｂは内部信号"1"を１
列目レジスタから２列レジスタへどう配分するかを決め
る部分であってアンドゲート342Ａと３４２Ｂから成
る。

アンドゲート３４２Ａは外部信号"0"の時にｉ行目のレ
ジスタ（たとえば１３１Ｂ）の内部信号を２列目のｉ行
目と（ｉ＋１）行目のレジスタ（たとえば１３２Ｂと１
３２Ｃ）へ分配する役割を果し、アンドゲート３４２Ｂ
は外部信号"1"の時に１列目のｉ行目のレジスタ（たと
えば１３１Ａ）の内部信号を２列目の（ｉ＋２）行目の
レジスタ（たとえば１３２Ｃ）へ分配する役割を果す。

今、ｉ行ｊ列目のレジスタの時刻ｔにおける内部信号を
Ｓij(t)とし、ｉ行目のデリミタ信号保持手段１２０が
発生可能ならしめる内部信号をＳ_ioとすると、 S_i1(t)＝S_(i-1)0+x_i-1(t)*S_(i-1)1(t_-1) S_i2(t)＝x_i-1(t)*S_(i-2)2(t_-1)+x_i-2(t)*S_(i-2)1(t_-1)+x_i-1(t)*S_(i-1)(t_-1)+x_i
(t)*S_i1(t_-1) で表わされる。ここに、＊印は論理積を示し、＋印は論
理和の作用を示している。

第１図や第３図では３列目以降の内部信号保持手段１３
０を示していないが、３列目以降をも導入できるとすれ
ば、Ｓ_ij(t)は次のようになる。

S_ij(t)＝x_i-1(t)*S_(i-1)j(t_-1)+x_i-2(t)*S_(i-2)(j-1)(t_-1)+x_i-1(t)*S
_(i-1)(j-1)(t_-1)+x_i(t)*S_i(j-1)(t_-1) ここに、ｊ２，ｉ２としている。また、 S₁₁(t)＝"L"， S_1j(t)＝x₁(t)*S_1(j-1)(t_-1),j２である。

列が増えるにつれて、特定記号で区切られたパタン記号
列当りの文字エラー（脱字、誤字、誤字混入）を多くで
きる。そして、（ｊ＋_１）列目がｊ個の文字エラーあり
の時の整合のありなしを示すことになる。

第４図はマッチ信号の出力方法の説明図である。(a)は
外部信号記憶手段１１０の１ビット目から順に記憶され
るパタン記号列の一例を示している。(b)は登録後のス
ペース記号に対して各ビット線１１４が出力する"0"の
外部信号の印加に対応した内部信号保持手段１３０の１
列目と２列目の各レジスタの内容を１行目から22行目ま
で順に示したものである。(c)はデリミタ信号保持手段
１２０の内容を示している。デリミタ信号は内部信号
"1"の発生に使われ、(b)に示すように、対応する行のレ
ジスタに内部信号"1"を停留させる。ただし、(b)図の１
行目の"1"だけはデリミタ信号保持手段１２０によら
ず、無条件に設定されたものである。第４図(d)は第１
のスイッチ１５０が出力する信号を示しており、０の所
は常に"0"を出力し、？の所がマッチ信号の"1"または
"0"を表わす。第４図(e)は完全一致モード時の第１スイ
ッチ１５０のデータ記号列ＡＢＣＤ入力後の状態を示
し、１列目のレジスタ１３１の内容を反映し、４行目だ
けが"1"になっている。これによって、データ記号列と
パタン記号列ＡＢＣＤとの完全マッチのあった事が示さ
れる。第４図(f)はエラー許容モード時のデータ記号列
ＤＥＡＣ入力後の第１のスイッチ１５０の状態であっ
て、２列目のレジスタ１３２の内容を反映し、10行目だ
けが"1"になっている。これはデータ記号列にパタン記
号列ＤＥＢＡＣの中のＢが脱落した記号列との一致のあ
った事を示している。この事を可能にするスイッチ手段
について、以下にもう少し詳しい説明を行なう。

第５図は第１スイッチ１５０の回路の中味を示してい
る。回路の中味はマルチプレクサ５００とアンドゲート
５４０であり、ｊ２の時のマルチプレクサ５００は２
つのアンドゲート５１０と５２０とオアゲート５３０か
ら成り、端子１５１から与えられるモード信号が"1"の
時に１列目レジスタ１３１の内容を、"0"の時に２列目
レジスタ１３２の内容を出力する。このマルチプレクサ
５００の出力はデリミタ信号保持手段１２０の内容が
"1"の時にのみ、対応する行の２つのレジスタ１３１と
１３２のいずれか一方の内容を端子５５０から出力させ
る。

第６図はスイッチ手段での識別結果の出力回路を示して
いる。第６図(a)は第１図に記載されたものと同じ出力
回路であり、第１スイッチ１５０の出力信号をシリアル
に出力するマルチプレクサ１５５と全ての第１スイッチ
１５０の出力信号の論理和を出力するオアゲート１５８
とから成っている。

オアゲート１５８からマッチ信号"1"が検出された時に
のみ、全ての第１スイッチ１５０の出力信号をシリアル
に出力する。シリアルな出力時間を短縮するにはかなり
高速のマルチプレクサ１５５が必要である。また、デー
タ記号列の各部がどのパタン記号列に一致したかのチェ
ックは外部システムに要求されることになる。

第６図(b)は複数マルチプレクサ１５５によって多くの
第１スイッチ１５０の出力信号を複数の出力端子１５
７′からシリアルに出力する場合を示している。これに
よって、オアゲート１５８から"1"が検出された時に出
力される全ての第１スイッチ１５０の出力信号の出力時
間が大きく減少する。たとえば、第１スイッチ１５０の
個数が4096個の時に、出力端子157′の本数を８にする
と、各端子は第１スイッチ１５０の５１２個分を分担す
るだけに減る。マルチプレクサ１５５のスイッチングタ
イムを50nsecとしても、出力時間はまだ25.6μsecに及
ぶ。なお、本発明の請求範囲(1)に記載されたスイッチ
手段は第６図(a)や(b)までを含んだものである。

第６図(c)はデリミタ信号位置記憶手段６００と識別コ
ード出力手段６２０によってスイッチ手段１５０の出力
信号の出力時間の短縮を狙ったものである。

デリミタ信号位置記憶手段６００はアドレスカウンタ６
１０を用いて０番地から順にデリミタ信号の発生する行
を２進コードで記憶する。この記憶手段６００の１ビッ
ト目６０１は登録パタン記号列数に等しい番地でカウン
タ６１０をリセットするための情報を記憶している。た
とえば、登録数が２の時には１番地にリセット信号の
"1"が書込まれるとする。

ＡＢＣＤとＤＥＢＡＣの２つのパタン記号列を登録した
時には特定記号が第４図(c)に示すように５行目（０１
００）と11行目（１０１０）に出現するので、デリミタ
信号位置記憶手段６００は０番地に00100を、１番地に1
1010を貯えることになる。そしてデータ記号列の各文字
の入力の都度、タイミング制御手段１６０の出力するパ
ルスを計数するカウンタ６１０が記憶手段６００に対し
て０番地と１番地のアクセスを指定する。

記憶手段６００の２ビット目６０２、３ビット目６０
３、４ビット目６０４と５ビット目（６０５）の出力が
マルチプレクサ１５５のスイッチを制御し、始めに５行
目のスイッチ手段１５０の出力信号を、次に10行目の第
１スイッチ１５０の出力信号を出力端子１５７から出力
する。すなわち、オアゲート１５８から"1"が検出され
た時に、記憶手段６００を２回アクセスするだけで全て
の第１スイッチ１５０の出力信号が解読されることにな
る。勿論、パタン記号列の登録数と共にアクセス回数は
多くなる。

識別コード出力手段６２０は出力端子１５７から"1"の
マッチ信号が出力された時に、その時のカウンタ６１０
の内容を出力端子６２５から識別コードとして外部へ呈
示する。次にマッチ信号が来るまで、以前にマッチした
パタン記号列の識別コードを保持するものとする。な
お、記憶手段６００の１ビット目６０１から出力される
リセット信号はタイミング制御手段１６０にもフィード
バックされ、そこからカウンタ６１０に与えられるパル
ス数を制御するものとする。

第７図は本発明のもう一つの実施例であって、出力回路
以外は第１図と同じである。すなわち、第１のスイッチ
１５０（第５図）と第２のスイッチであるマルチプレク
サ１５５（第６図ａ）の他にデリミタ信号位置記憶手段
６００と識別コード出力手段６２０とを加えた出力回路
（第６図ｃ）を用いている点が第１図との違いである。
これによって、任意の長さのパタン記号列を多数個登録
した時の識別コードの出力時間は大巾に減少する。

第８図は第６図(c)を改良した識別結果の出力回路の説
明図である。

第６図(c)と異なる点はデリミタ信号位置記憶手段８０
０が単にデリミタ信号の発生位置コードだけでなく、そ
れと対応ずけて、パタン記号列に関連ずけられる応答出
力コードを貯えている点と、パタン記号列の登録番号の
識別コードの代りに、上記応答出力コードを送り出す出
力手段８２０を用いている点にある。

応答出力コードとは各パタン記号列に関連ずけられる記
号コードとか関連したデータのファイルメモリのアドレ
スとかである。たとえば、パタン記号列ＡＢＣＤに対し
て「アルファベットの最初の４文字」という文章を出力
させたいならば、その文章を格納する外部のファイルメ
モリのアドレス（例えば101010）が応答出力コードにな
る。カナ漢字変換とか英単語の日本語への変換とかを行
なう場合にはカナ文字や英単語のパタン記号列に対し
て、同じ意味を持つ漢字や日本語訳の出力を行なうROM
（固定メモリ）のアドレスコードが応答出力コードに該
当する。パタン記号列が命令語の場合には、それを実行
するマイクロプログラムの格納アドレスが応答出力にな
る。

このような応答出力コードを出力するために、出力手段
８２０は、第２のスイッチ（マルチプレクサ）１５５か
ら出力されるマッチ信号によってデリミタ信号位置記憶
手段８００の読取り出力信号の中の応答出力コードの部
分を取込む。

デリミタ信号位置記憶手段８００は書込み時に登録され
る多数のパタン記号列を区切る特定記号＊を計数するア
ドレスカウンタが１ビットインクレメントされる都度、
各パタン記号列の長さに等しいデリミタ信号位置コード
を貯え、それと同じアドレスに応答出力コードをも貯え
る。

読取り時は、オアゲート１５８は"1"のマッチ信号を出
力した時にタイミング制御回路１６０がアドレスカウン
タ６１０へアドレスインクリメント用のパルスを出力す
る。それによって、デリミタ信号位置記憶手段８００が
０番地から（登録記号列数−１）番地まで順次に走査
（スキャン）される。第８図の例では、登録記号列数が
２であり、０番地と１番地がアクセスされる。この記憶
装置８００の１ビット目８０１が"1"であると、アドレ
スカウンタ６１０がリセットされ、また、タイミング制
御回路１６０からアドレスカウンタ６１０へ送られるパ
ルスも１ビット目８０１の"1"によって禁止される。

デリミタ信号位置記憶手段８００の（ｉ−１）番地にお
ける２ビット目８０２から５ビット目８０５までは登録
された多数のパタン記号列における先頭からｉ番目の特
定記号出現までの文字数の２進コードを貯えていて、第
２のスイッチ（マルチプレクサ）１５５のスイッチ選択
に使われる。一方、６ビット目８０６から11ビット目８
１１までは登録されるパタン記号列のｉ番目に関連した
応答出力コードを貯えていて、出力手段８２０に送られ
る。

たとえば、データ記号列にＡＢＣＤが含まれると、５行
目の第１スイッチ１５０が"1"を出力する。最後の記号
Ｄの印加時に、出力端子１５９から"1"のマッチ信号が
出ると、アドレスカウンタ６１０がデリミタ信号位置記
憶手段８００の０番地と１番地のアクセスを順次に指定
し、その結果マルチプレクサ１５５が５行目と11行目の
第１スイッチ１５０の出力を順次に出力するように働き
"1"と"0"をシリアルに出力する。出力端子157から"1"が
出力された時に、出力手段８２０はデリミタ信号位置記
憶手段８００の０番地の６ビット目８０６から11ビット
目８１１までの応答出力コードを取り込み、"0"が出力
される時の１番地の応答出力コードを受付けない。

このようなデリミタ信号位置記憶手段８００と応答出力
手段８２０をそれぞれ第７図のデリミタ信号位置記憶手
段６００と応答出力手段６２０の代りに設けると、第７
図がデータ記号列の各部に対してそれに一致したパタン
記号列の検知信号を端子１５９から出力すると共に、そ
のパタン記号列に関連ずけられた応答出力コードを端子
８２５から出力するようになる。

（発明の効果）第１図や第７図に示した本発明の記号列識別装置は外部
信号記憶手段１１０のRead／Writeサイクルタイムが１
μsecであれば1MB／secまでの速度でデータ記号列の受
付けを許す。そして、第１スイッチ１５０からデータ記
号列の各部とパタン記号列との整合のありなしを出力す
る。パタン記号列との完全一致及び一文字エラーを許容
した一致を区別して検知できる。従来技術では256個の
パタン記号列とのマッチング処理速度が4KB／secであ
り、一文字エラーを許容した場合のマッチング処理速度
が１Ｂ／secであった事を考えると本発明によるマッチ
ング処理速度が一文字エラーを許容する場合でも１MB／
secのままであるから処理速度の改善は１００万倍に及
ぶとわかる。

しかも、本発明の記号列識別装置では登録される多数の
パタン記号列の長さがばらばらであっても登録が容易で
あり、且つ、データ記号列の中に含まれるパタン記号列
にその先頭位置を示す区切り記号を付加しなくてもデー
タ記号列の各部がどのパタン記号列にマッチするかを識
別する事（Unanchorモードの識別）が可能である。

識別結果は単に、どれかのパタン記号列にマッチした事
を示す情報だけでなく、マッチしたパタン記号列の識別
（登録番号）コードやマッチしたパタン記号列に関連ず
けられた応答出力コードをも出力する。応答出力コード
はデータ記号列の中にどれかのパタン記号列とのマッチ
があった時にのみ出力されるので、その出力時間が数μ
secから数10μsecに及んでも、綜合的な処理速度は低下
しない。

しかも、このような記号列識別装置が進歩した半導体LS
I技術によって１チップで実現されるようになる。入出
力端子数も20数ピンで済む。外部信号記憶手段の記憶容
量が１Mb以上になる事もそう遠くはない。１Mbは８ビッ
トの記号コードの4096個分を収容できる。この時、内部
信号保持手段はビット線１１４の本数、例えば4096本、
の２倍程度の容量で良く、またデリミタ信号位置記憶手
段８００の記憶容量は登録記号列数、例えば２５６個、
の16倍程度で良いので、それ程大きなチップサイズを占
めない。１チップの中に８文字長のパタン記号列を２５
６個も登録できて、１MB／secの処理速度でデータ記号
列と２５６個のパタン記号列との並列照合を進めること
ができる事はテキスト情報の内容検索の高速化を大巾に
促進する事になる。

以上に述べたように、本発明によれば、従来技術では一
文字エラーを許容する条件下で多数のパタン記号列との
照合を高速化する事の難かしかった問題点を１チップ上
で解決できるとわかる。本発明の技術は情報検索システ
ムやパタン認識システムや機械翻訳システムなどに応用
された時に特に大きな効果を発揮する。

なお、本発明の実施例において、外部信号記憶手段１１
０はＲＡＭで実現されるように説明されたが、ROMやPRO
MやEEPROMによって実現されて良いし、内部信号保持手
段１３０のレジスタ１３１，１３２はフリップフロップ
だけでなく、単なる電荷保持素子（コンデンサー）で実
現されて良く、以上の記述は何ら本発明の請求範囲を限
定するものでない。また、第１図や第７図の左端の書込
み回路１１６のシリアル選択がシフトレジスタ１１７に
よって達成されるように説明されたがアドレスデコーダ
を用いても達成可能であって、以上の記述は何ら本発明
の請求範囲を限定するものではない。

【図面の簡単な説明】

第１図は本発明の一実施例の説明図、第２図(a)〜(c)は
パタン記号列の登録方法の説明図、第３図は第１図の部
分図、第４図(a)〜(f)はマッチ信号の出力方法の説明
図、第５図は第１スイッチ回路の説明図、第６図(a)〜
(c)はスイッチ手段における識別結果の出力回路図、第
７図は本発明の第２の実施例を示す図、第８図は第６図
(c)を改良した識別結果の出力回路図である。以上の図面において、 110……外部信号記憶手段、111……記号コードの入力端
子、112……アドレスデコーダ、113……ワード線、114
……ビット線、115……読取り回路、116……書込み回
路、117……書込み信号シフトレジスタ、118……入力端
子、120……デリミタ信号保持手段、125……内部信号供
給手段、130……内部信号保持手段（レジスタアレ
イ）、131……第１列目のレジスタ、132……第２列目の
レジスタ、141，143……第１ゲート手段、142……第２
ゲート手段、150……第１スイッチ、155，155′……第
２スイッチまたはマルチプレクサ、151……モード信号
端子、156……アドレスコード入力端子、157，157′…
…マルチプレクサの出力端子、158……マッチ信号のオ
アゲート、159……オアゲートの出力端子、160……タイミ
ング制御回路、165……イニシャライズ信号入力端子、3
41A，343A，324B，540……アンドゲート、342A，510…
…否定信号とのアンドゲート、341B，343B，530……オ
アゲート 600，800……デリミタ信号保持手段、601，6
02，603，604，605……１ビット目、２ビット目、３ビ
ット目、４ビット目と５ビット目、610……アドレスカ
ウンタ、 620……識別コード出力手段、625……識別コ
ード出力端子、820……応答出力コード出力手段、825…
…応答出力コード出力端子。

Claims

【特許請求の範囲】

【請求項１】記号列を構成する記号コードで指定された
番地に外部信号を記憶する外部信号記憶手段と、この外
部信号記憶手段の各ビット線に対応して設けられ、特定
記号コードに対して前記各ビット線から読出される外部
信号を保持するデリミタ信号保持手段と、行列状に配列
され、各行が前記各ビット線に対応する複数個の内部信
号保持手段と、一般記号コードに対して各ビット線から
読出される外部信号によって制御され、隣接する行の内
部信号保持手段を列毎に上下に結合する第１ゲート手段
と、前記外部信号によって制御され、隣接する列間の内
部信号保持手段を隣り合う３つの行毎で斜めまたは左右
に結合する第２ゲート手段と、前記デリミタ信号保持手
段の内容によって制御され、各行の端列の内部信号保持
手段に内部信号を設定する内部信号供給手段と、前記デ
リミタ保持手段の内容で指定された行の内部信号保持手
段の内容を列毎に区別して出力するスイッチ手段とを備
えた事を特徴とする記号列識別装置。
【請求項２】記号列を構成する記号コードで指定された
番地に外部信号を記憶する外部信号記憶手段と、この外
部信号記憶手段の各ビット線に対応して設けられ、特定
記号コードに対して前記各ビット線から読出される外部
信号を保持するデリミタ信号保持手段と、行列状に配列
され、各行が前記各ビット線に対応する複数個の内部信
号保持手段と、一般記号コードに対して各ビット線から
読出される外部信号によって制御され、隣接する行の内
部信号保持手段を列毎に上下に結合する第１ゲート手段
と、前記外部信号によって制御され、隣接する列間の内
部信号保持手段を隣り合う３つの行毎で斜めまたは左右
に結合する第２ゲート手段と、前記デリミタ信号保持手
段の内容によって制御され、各行の端列の内部信号保持
手段に内部信号を設定する内部信号供給手段と、前記デ
リミタ保持手段の内容で指定された行の内部信号保持手
段の内容を列毎に区別して出力するスイッチ手段と、前
記スイッチ手段からどの行の内部信号保持手段の内容を
出力すべきかを指定するデリミタ記号位置記憶手段と、
前記スイッチ手段の出力信号によって前記デリミタ信号
位置記憶手段のアドレスコードを選択する識別コード出
力手段とを備えた事を特徴とする記号列識別装置。
【請求項３】記号列を構成する記号コードで指定された
番地に外部信号を記憶する外部信号記憶手段と、この外
部信号記憶手段の各ビット線に対応して設けられ、特定
記号コードに対して前記各ビット線から読出される外部
信号を保持するデリミタ信号保持手段と、行列状に配列
され、各行が前記各ビット線に対応する複数個の内部信
号保持手段と、一般記号コードに対して各ビット線から
読出される外部信号によって制御され、隣接する行の内
部信号保持手段を列毎に上下に結合する第１ゲート手段
と、前記外部信号によって制御され、隣接する列間の内
部信号保持手段を隣り合う３つの行毎で斜めまたは左右
に結合する第２ゲート手段と、前記デリミタ信号保持手
段の内容によって制御され、各行の端列の内部信号保持
手段に内部信号を設定する内部信号供給手段と、前記デ
リミタ保持手段の内容で指定された行の内部信号保持手
段の内容を列毎に区別して出力するスイッチ手段とを備
えた記号列識別装置であって、登録する各パターン記号
列の後尾に特定記号を付加し、登録後に、前記特定記号
に対して各ビット線から出力される外部信号を前記デリ
ミタ保持手段に設定することを特徴とする記号列識別装
置。
【請求項４】記号列を構成する記号コードで指定された
番地に外部信号を記憶する外部信号記憶手段と、この外
部信号記憶手段の各ビット線に対応して設けられ、特定
記号コードに対して前記各ビット線から読出される外部
信号を保持するデリミタ信号保持手段と、行列状に配列
され、各行が前記各ビット線に対応する複数個の内部信
号保持手段と、一般記号コードに対して各ビット線から
読出される外部信号によって制御され、隣接する行の内
部信号保持手段を列毎に上下に結合する第１ゲート手段
と、前記外部信号によって制御され、隣接する列間の内
部信号保持手段を隣り合う３つの行毎で斜めまたは左右
に結合する第２ゲート手段と、前記デリミタ信号保持手
段の内容によって制御され、各行の端列の内部信号保持
手段に内部信号を設定する内部信号供給手段と、前記デ
リミタ保持手段の内容で指定された行の内部信号保持手
段の内容を列毎に区別して出力するスイッチ手段とを備
えた記号列識別装置であって、デリミタ信号位置記憶手
段にデリミタ信号位置指定コードと合わせて任意の応答
出力コードを格納し、前記スイッチ手段の出力信号によ
って前記応答出力コードの出力を選択するようにしたこ
とを特徴とする記号列識別装置。
【請求項５】記号列を構成する記号コードで指定された
番地に外部信号を記憶する外部信号記憶手段と、この外
部信号記憶手段の各ビット線に対応して設けられ、特定
記号コードに対して前記各ビット線から読出される外部
信号を保持するデリミタ信号保持手段と、行列状に配列
され、各行が前記各ビット線に対応する複数個の内部信
号保持手段と、一般記号コードに対して各ビット線から
読出される外部信号によって制御され、隣接する行の内
部信号保持手段を列毎に上下に結合する第１ゲート手段
と、前記外部信号によって制御され、隣接する列間の内
部信号保持手段を隣り合う３つの行毎で斜めまたは左右
に結合する第２ゲート手段と、前記デリミタ信号保持手
段の内容によって制御され、各行の端列の内部信号保持
手段に内部信号を設定する内部信号供給手段と、前記デ
リミタ保持手段の内容で指定された行の内部信号保持手
段の内容を列毎に区別して出力するスイッチ手段とを備
えた記号列識別装置であって、各列における前記デリミ
タ保持手段の内容で指定された全ての行の内部信号保持
手段の内容の論理和が“１”を示す時に、どの行の内部
信号保持手段の内容が“１”になったかを外部へ出力す
ることを特徴とする記号列識別装置。
【請求項６】記号列を構成する記号コードで指定された
番地に外部信号を記憶する外部信号記憶手段と、この外
部信号記憶手段の各ビット線に対応して設けられ、特定
記号コードに対して前記各ビット線から読出される外部
信号を保持するデリミタ信号保持手段と、行列状に配列
され、各行が前記各ビット線に対応する複数個の内部信
号保持手段と、一般記号コードに対して各ビット線から
読出される外部信号によって制御され、隣接する行の内
部信号保持手段を列毎に上下に結合する第１ゲート手段
と、前記外部信号によって制御され、隣接する列間の内
部信号保持手段を隣り合う３つの行毎で斜めまたは左右
に結合する第２ゲート手段と、前記デリミタ信号保持手
段の内容によって制御され、各行の端列の内部信号保持
手段に内部信号を設定する内部信号供給手段と、前記デ
リミタ保持手段の内容で指定された行の内部信号保持手
段の内容を列毎に区別して出力するスイッチ手段とを備
えた記号列識別装置であって、各列における前記デリミ
タ保持手段の内容で指定された全ての行の内部信号保持
手段の内容の論理和が“１”を示す時にのみ、整合のあ
ったパタン記号列の識別コードまたはそれに関連ずけら
れた応答出力コードを出力することを特徴とする記号列
識別装置。