JPS6128134A - 記号列照合装置とその制御方式 - Google Patents

Abstract

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

Description

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

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

従来の記号列照合は汎用コンピュータのソフトウェアに
たよった逐次処理によるため、膨大な処理時間を必要と
し、小規模なものに限定されていた。また、単語毎に区
切られて構造化された記号列に照合対象が制限されて諭
た。−列として、。

個の記号列からなるテキスト中Ｋｎ個の記号列から々る
バタンかどこに有るかを調べる場合には、ｍ　（ｎ、−
ｍ　＋　１　）回の照合処理を必要とする。磁気ディス
クや元ディスク等に格納されたｍ＝１０９個の文字列の
テキストから、ｎ−＝１０”個の文字列の文章を捜すに
は１０　回の照合処理を必要とする従って、テキスト、
イメージ、図形、音声等の犬容附な原情報による検索は
非現実的であるため、予め原情報にキーワードを付加し
ての検束や表形式に構造化されたテークの検束に限定さ
れていた。

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

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

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

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

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

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

また、一部の記号に欠けや誤りのある記号列や余分な記
号が付加された記号列の照合が困難である。例えば、文
字列’　ＭＥＭＯＲＹ“　に門し、その中文字゛０“が
他の文字１１　Ｘ″に置換った文字列皐ＭＥＭＸＲ，Ｙ
“や、文字１１０　Ｌ／が欠けたＭＥＭＲＹ“や余分な
文字Ｉｔ　Ｘ　ｌ／が付加された”ＭＲＭＸＯＩ（、Ｙ
“が入力された場合に、照合又字列′″Ｍ、ＢΔ４０Ｒ
Ｙ”と類似していることを出力できることが記号列照合
ＶＣ望まれる。しかし、従来の記号列照合装置や照合方
式では一部の記号の誤りに関しでは照合記号列と重ね合
せて比較することにより類似性を調べることができるが
、一部の記号の欠けや余分な文字の付加に苅しては対処
できなかった。

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

捷た、一部の記号の欠けや誤り、あるいは余分な記号が
付加された記号列についても照合可能な低価格な記号列
照合装置を提供することにある、（発明の構成） したがって、本発明によれば以下の記号列照合装置４と
その開側ｊ方式が得られる。すなわち、記号コードをア
ドレス入力とし、照合記号列を記憶する記号列記憶手段
と、この各出力線につながる第１の演算手段と、複数の
演算手段間を相互に結合する第１の一時記憶手段と、特
定の第１の一時記憶手段の出力につながる第２の一時記
憶手段・と、第２の一時記憶手段につながる第２の演算
手段とを含む記号列照合装置。

１把号コートをアドレス入力とし、照合記号列を記憶す
る記号列記憶手段と、この間出力線につながるＥｆ４１
の演算手段と、ネジ数の演算手段間を相互に結合するε
様ｌの一時記憶手段と、特定の第１の一時〒：＋２１’
、は手段の出力につながる第２の一時記憶手段と、第２
の一時記憶手段Ｖこつながる第２の演算手段と、外部か
ら与えられる許容類似度全記憶するレジスタと、このレ
ジスタの内容と第２の演算手段の出力とを比較し、照合
結果を出力するコンパレータどを含む記号列照合装置。

とさらに該コンパレータに接続するエン：１〜ダとト亥
レジスタに接続するデコータとを４＃＋ｉえた記号列照
合装置４と記号に関連づけたビットパタンで照合記号列
を記憶する記号列記憶手段のへ（正精叔）節目と（へ＋
１）番目の出力線に各々つながるＮ番目第１；猜理演算
手段と（Ｎ＋１１街目第１演算手段との間のＮ番目第１
一時記憶手段の内容’（Ｃ（Ｎ−１）番目第１一時記憶
手段の内容Ｖ？ＣＮ番目１己号列記憶手段の出方線によ
り制御されたＮ番目第１演算手段の演算処理をｊＩｆＱ
こいｔものとし且つ、特定の第１一時記憶手段の互いに
異なる時刻の内容に第２の演：！：’？］手段による演
算処理を測ずことで前記記号り１托１シ憶手段の内容と
鏝次入力された記号列の類似１ノ１を求める記号列照合
装（Ｉ￥、ＯＩＩｉ：Ｉ　＆ＩＩ方式ティ〉ル、（実施
例） 以］・図面を用いて本・ｈ゛、明の史に１１組（な説明
を行なう。

第１図は本発明の一実施例の説明図である。この記号列
照合装置Ｉ′７は第６図に示したような長大な記号列と
なるチキン、１・あるいはイメージ、画像、音声等をコ
ード化し、ｉ己号列人カ端子１１１　がら逐次入力（７
、その中に登録済みの照合記号列と類似する記号列がど
こに含まれるがを外部に伝達するものであり、記号に関
連づけたビットパタンで記号列を記憶する記号列記憶手
段１１０、とその読み取り信号１１２　により内容の変
化がｆＨＩＪ　（＋ｉｌＩあれる複数段の複数ビットの
カウンタ１２０　　と、最下段のカウンタ１２０　　の
出力につながる第２の一時記憶手段としてのレジスタ１
３０　　最下段のカウンタ１２０　の内容Ｎ６とレジス
タ１３０　の内容とを加算する第２の演算手段である加
算器１４０　とから構成される。カウンタ１２０　Ｆｉ
論理演算手段１２３とそれからの演算結果を記憶する一
時記憶手段１２４　とを含んでいる。ここでは論理演算
手段１２３と一時記憶手段１２４　とをカウンタ１２０
　　で代表させて説明を行なう、 照合記号列の各記号は記号列記憶手段１１０　の各ビッ
トに記号に関連づけたビットパタンで格納される。図の
例でＦｉ６ビノトの記号列記憶手段１１０に’ＭＥＭＯ
ＲＹ“０６個の記号からなる照合記号列を格納している
。すなわち、記号列記憶手段１１０　の第１から第６ビ
ツト目の各々記号１Ｍ“気へ〃、・・Ｅ〃、ＲＭ　ＩＩ
、鳩０〃、′″Ｒ〃、’Ｙ“で指定されるアドレスにの
み“■〃が格納され、他は′０″が格納される。記号列
記憶手段１１０　のアドレスは記号の種類に対応し、そ
の第１から第６ビツト目の読取り信号１１２　は、各々
記号１−Ｍ〃、Ｉｔ　Ｉ、；　／７．　ＩＸＭ　／ｌ気
Ｏ〃、気Ｒ〃、パＹ〃　が入力されたときのみ■″とな
る。

各段のカウンタ１２０　はクロック信号１２１　に同期
して動作し、その各段の出力は次段のデータ入力に接続
されている。初段のカウンタ１２０　のデータ入力には
零が供給され、最終段のカウンタ１２０　の出力Ｎ６は
レジスタ１３０　に印加される。

クロック信号１２】　　の立上り時に転送信号１２２が
印加されていると、各段のカウンタ１２０　の内容は図
において上段から下段方向に一段づつ転送される。また
、転送信号１２２　が印加されておらず、記号列記憶手
段１１０　から１″の読取り信号】１２　が供給される
と、カウンタ１２０　の内容は１だけ増加（以後、イン
クリメントと称す）し、０“の読取り信号の場合には内
容が保たれる、このように動作させるカウンタ１２０　
として、市販されている集積回路、例えばテキサス・イ
ンストルメント社製の５Ｎ７４Ｌ８１６１Ｎ　’に利用
できる。

第２図はクロック信号１２１　と転送信号１２２のタイ
ミング図ケ示す。照合対象となる記号列は周期Ｔ＠に１
個の記号が記号列入力端子１１１　　から入力され、そ
の間に前後２発のパルス信号がクロック信号１２１　と
して印加される。転送信号１２２　はクロック信号１２
１　の創見のパルス信号の立上り時を含むパルス信号と
して印加される。

従って、１個の記号が入力されるごとに各段のカウンタ
１２０　の転送動作とインクリメント（但し、読取り信
号１１２が１“の場合）が交互に行なわれる。レジスタ
１３０は転送信号１２２により最終段のカウンタ１２０
の内容を取込む。

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

第１図に示したように記号列記憶手段１１０に’　ＭＦ
ｉＮＯＲ，Ｙ　″の照合記号列が格納されている状態で
、照合記号列と同じ記号列″ＭＥＭＯＲＹ“　が記号列
入力端子１１１から入力された場合の動作を同図（ａｌ
で説明する。また照合記号列内の一部の記号″０“が誤
った場合、欠けた場合及び余分な記号ＩＩ　Ｘ　ｒｒが
付加された場合について、それぞれ同図（ｂｌ、（ｃｌ
、（ｄ）を用いて説明する。

図において、第１行は記号列入力端子１１１　から入力
された記号列、第２行は記号の入力毎に仮に定めた時刻
’］’ｏ−’ｌ’７を示し、第３行以下はクロック信号
１２１　の後発のパルス信号が印加された後のカウンタ
１２０の内容を上段よりＮｌ、　Ｎ２．　Ｎ３゜Ｎ４．
Ｎ５．Ｎ６で代表させ、そめ値を示す。最後の行は加算
器１４０の出力への値を示す。

まず、照合動作前に各段のカウンタ１２０の内容Ｎ１か
らＮ６を零に設定しておく。これは図示していないが、
カウンタ１２０のクリア端子にパルス信号を印加するこ
とで容易に行なえる。

第３図（ａｌを参照して、照合記号列と同じ記号列’Ｍ
ＥＭＯＲＹ“が記号列入力端子１１１から入力された場
合の動作について説明する。まず、先頭の記号″′Ｍ“
が入力されたときに、クロック信号１２１の創見のパル
ス信号の立上り時に転送信号１２２が印加されているの
で、各段のカウンタ１２０の内容は上段から下段方向に
一斉に次段に転送される。この時点での全段のカウンタ
１２０の内容Ｎ１から〜６は零になっている。また、記
号列記憶手段１１０の第１ビツト目と第３ビツト目の読
堆り信号１】２のみ１“となる、Ｌ７？：、かって、ク
ロック信号】２１　の後発のノくルス信号が印加される
と、第１段目と第３段目のカウンタ１２０　の内容へ１
とＮ３のみインクリメントされ０から１となる、 これで照合対象となる記号列の先頭記号゛ＸＭ〃に対す
る照合処理がなされる。

同様にして次の記号″′Ｅ“が入力されると、第２段目
のカウンタの内容Ｎ２のみインクリメントされ、Ｊから
２となる。このようにして、全ての記号列に対する照合
処理に行なう。最終段のカウンタ１２０の各時刻におけ
る内容（この例ではＮＯ）は、その時刻以前に入力’Ｊ
　！’ｌ−た記号列の各記号とが一致する記号のｆ固数
を示すことになる。第３図（ａ）では時１１１Ｔ６の〜
６の値の６は、その時刻以前すなわちＴｌ〜Ｔ６に入力
をれた記号列に一致していることを示す。

従って、照合記号列の記号数をＭとすると（図の例では
Ｍ＝６）、同一の記号列が入力された場合に〜６の値は
Ｍとなり、１個の記号のみが異なるな゛らばＭ−１とな
る。すなわち、最終的段のカウンタ１２０の内容は入力
された記号列と照合記号列との類似度を示す。加算器１
２０は最終段のカウンタ１２０の内容と１時刻前のその
内容を記憶するレジスタ１３０の内容とを加算し、類似
度出力１２５　として外部に伝達する。

第３図（ｂ）は一部の記号′０″が他の記号″Ｘ″に誤
っている記号例が入力された場合の各段のカウンタ１２
０の内容を示す。先頭から３個の記号゛Ｍ〃、′Ｅ“、
′Ｍ“の入力に対する各段のカウンタ１２０は、第３図
（ａ）と同様に動作する。しかし、次の４番目の記号″
′Ｘ“が入力されると、第４段目のカウンタ１２０の内
容Ｎ４は、記号列記憶手段１１０の第４ビツト目の読取
り信号１１２がＯ“であるためインクリメントされず、
同じ値３全保つ。従って、６個の記号からなる記号列″
ＩＭＥＭＸＲ，Ｙ″が入力され′ｆ？、、後の〜６の値
は、第３図（ａ）の場合より１だけ小さい５となる。す
なわち、照合記号列と１個の記号のみが異なる記号列が
入力されたと認識できる。

第３図（Ｃ１は照合記号列内の一部の配列゛０“が欠け
た記号列″”　Ｍ　Ｅ　Ｍｌｌ、　Ｙ　Ｘ“が入力され
た場合の各段のカウンタの内界条′示す。先頭から３個
の記号の入力に対し２てｉ’Ｔｉ：　２Ｂ　３図（ＸＩ
ｌと同様な動作をする。

しかし、以後の記号列”　Ｒ，γＸ″′は照合記号と１
記号つれでいろため、時刻’Ｊ’４．　Ｔ５．　Ｔ６に
おけるＮ４．〜５．〜６の１１？ｉに変化せず、３を保
つ。〕Ｆだ、記号″Ｒ／／が入力される時刻′■゛４に
〜５はインクリメントされ、０から１となる。次の記号
″Ｙ“が入力されたときに〜６はインクリメント式れ、
１から２となる。この結果、最終段のカウンタ１２０　
　の内容Ｎ６の最大イ１げは３となり、Ｎ６乏・監視し
ているだけでは入力された記号列が照合記号列からＴ　
１ｌＩＩＩの記号を抜いた記号列であることを認識でき
ない。しかし、加算器】４０の出力Ｎ　＆：１：　５と
なるので時刻Ｔ１から’Ｉ’６−＋でに入力されグこ記
号列内に照合記号列と整合する記号が５個含まれている
ことを認識できろ。４ｉｌっで、一部の記号が欠ｒ７だ
記号列についても加算器１４０の出力へを監視すること
により、照合が可能となる。加シ、器Ｊ　４０　の出力
〜は類似反出力１２５　として外部に伝達される。

第３図（ｄ＋は余分な記号″′Ｘ″ケ含む記七列’Ｍｉ
ｌ射ＪＸＯＲ，Ｙ’′　が入力され′ｆｉＣ場合の各段
のカウンタ］２０のｌ”Ｊ谷をボラ−０先 号の入力に対し′ｔは第３１ン」（ａ）と同様な動作を
する。

しかし、４　（１６１目以抜の記号列ｉｒ．　Ｉ′ｉ余
分な鮨シ号＋Ｓ　Ｘ　＃か含まれているのて、照合Ｂ１
シ合列と１記号つれている、このため、時刻′１゛４、
１゛５、′Ｊ．’　６　の各々におけるＮ４、〜５、ｊ
〜０　のイ１ｉにインクリメン１されず、３を保つ。し
かし、１叫刻ずラシ’ｆｒ時：２１ｊ　’ｉ’　５、１
゛６、９゛７の各々ｉ／−二ふ・け４，〜４、〜５、〜
６の１直ｂ、それそインクリメント式れ、０から３とな
る。し７たかつて、Ｎ６λ・’．ｆＫ　Ｉｌｌ’．　Ｌ
，ている／こけてぐま入力された記−号列が照合ｍｌも
列に１つの余分な記号を付加した記号例であることを認
識できない。しかし、加算器１４０の出力への値は時刻
１１７で６となるので入力をれた記号列が畠い類似性を
持つことを認識できる。

一般に照合記号列の記号列長ｆｎとすると、時刻Ｔｉに
おける最終段のカウンタ］２０の内容Ｎ　ｎは、時刻Ｔ
ｉ　−ｎ＋１　から時刻Ｔｉ捷でに入力きれた記号列が
照合記号列と整合する記号の個数を示す。Ｔｉ時刻にお
ける加算器１４０の出力へすなわち類似度出力１２５は
、最終段のカウンタ１２０の時刻Ｔｉ　とその１時刻前
の内容の和を示す。すなわち、類似度出力】２５は入力
した記号列及びそれを１記号分ずらした記号列が照合記
号列と整合する記号の個数の和を示す。従って、一部の
記号が欠けた記号列および余分な記号が付加された記号
列についても、類似度出力１２５を監視することで照合
できる。

以上述べ女ように第１図に示した記号列照合装置は照合
記号列と完全に一致する記号列だけでなく、その中の任
意の個数の記号が誤っている記号列も抽出でき、柔軟性
の茜い記号列照合装置といえる。

一般に記号列の照合に際しては、照合記号列と一致した
記号の個数よりも異なる記号の個数が出力される方が取
扱いやすい。第１図に示したように一致する記号の個数
全計数すると、カウンタ１２０は照合記号列の記号数を
へ４とすると０がらＭ４で計数できるｌｏｇ２（Ｍ−ｆ
−１）のビット数が必要となる。しかし、異なる記号の
個数を計数するならば、許容できる不一致の割合を５％
とすると、カウンタ１２０はＭの５チ程度を計数できれ
ば良いため、そのビット数を削減できる。

これを可能にする記号列照合装置は第１図に示した記号
列照合装置を少し変更することで実現できる。

例えば、記号列記憶手段１１０の読取り信号１１２が”
０“であるときにカラ／り１２０　をインクリメントあ
るいはティクリメント（値を１だけ減少）させる。また
は、記号列記憶手段１１０の内容を反転させ、読取りイ
百号１１２が１“であるときに、カウンタ１２０の増減
を行なってもよい。この場合、カウンタ１２０の初期値
としてインクリメン、トを行なわせる場合Ｋｕ、零、テ
ィクリメントを行なわせる場合にはその計数可能な最大
値以上のインクリメン）　ｊｉ１３作あるいはディクリ
メント動作を禁止する必要がある。これは、カウンタ１
２０の全てのビットを入力とするナントゲート回路で全
ビットが１、あるいはノアゲート回路で零を検出し、そ
の検出出力で記号列記憶手・段１１０の読取り信号２１
２をマスクすることで容易に実現できる。但し、カウン
タ１２０　としてその最大値あるいは最小値を検出する
回路を内蔵しているカウンタ、金利用する場合には、ナ
ントゲート回路あるいはノアケート回路が不要となる。

ｉｆｒ、カウンタ１２０を並列入力可能なシフトレジス
タに置換えることも可能である。この場合、転送イム号
１２２で次段のシフトレジスタへの並列転送が開側１さ
れ、読取り信号１１２により内容の左シフトあるいは右
シフトが制御される。初段のシフトレジスタのデータ入
力にニ最上位ピッ）６るいは最下位ビットのみ異なるデ
ータを供給する。

このようなシフトレジスタにはテキサス・インストルメ
ント社から敗売されている７　４．ＬＳ　２９９の集積
回路を利用できる。カウンタ１２０の代りにシフトレジ
スタを用いると、照合記号列と異なる記号数を計数した
場合、シフトレジスタのビット数以上の異なる記号数が
入力されると、シフトレジスタの内容は自動的に零に設
定はれるので、制御が容易になる。

さらに、カウンタ】２０けシフトレジスタたけでなく他
の論理演算手段に置換えることも容易に可能である。

また、以上の説明では１個の記号の欠けや付加を許容で
きる記号列照合装置について説明したが、複数個の記号
の欠けや伺加を許容できるように拡張できる。これは、
レジスタ１３０として直列に接続した複数段のレジスタ
を使用し、加算器１４０が各レジスタの内容を加算する
ことで可能となる。

第４図も本発明による実施例の説明図である。

この記号列照合装置は照合対象となる記号列の中から照
合記号列と高り類似＃を示す記号列のみ抽出するもので
あり、第１図の記号列照合装置４００にコンパレータ４
１０　とレベル設定レジスタ４２０を追加している。

照合動作開始前にレベル設定レジスタ４２０には抽出し
ようとする記号列の許容類似度が設定される。これは、
許容類似度を示すレベル信号４２１とレジスタセノ）信
号４２２をレベル設定レジスタ４２０に供給することに
よ−り行なわれる。

コンパレータ４１０　ｉｔ類（Ｕ度出力１２５　とレベ
ル設定レジスタ４２０の内容とを各々入力Ａ、Ｂに入力
し、両者を比較する。そして前者が太きいか等しいかを
示すＡＺＢ出力を照合出力信号４１］として外部に伝達
する。記号列記号記憶手段１１０に格納づれている照合
記号列の記号数Ｍに対し、レベル設定レジスタ４２０　
に１ｌ−１）を設定すると、記号列入力端子１１１　力
・ら入力された記号列と照合記号列とが（Ｍ−１）個以
上の記号が整合しているνΔ合に、コンパレータ４】０
は照合出力４１１　を発生ずる。従って、ＩＡφ合出力
出力４１１監視することで照合記号列と１ｈり類イυ度
を示す記号列のみ抽出できる。

第５図も本発明による実施例の説明図である。

この記号列照合装置は複数の照合記号列を並列に照合し
、整合１７れ照合記号列を示す整合コードを出力するも
のであり、第４図に示した記号列照合装置に対応する記
号列照合ユニット５００を複数個含む記号列照合部５１
０　と、各記号列照合ユニット５００から出力される各
照合出力４１１　　ｆ入力するエンコーダ５２０　と、
各記号列照合ユニット５００にレジスタセット信号４２
２を供給するデコーダ５３０　とから構成される。

記号列入力端子１１１から入力される記号コード、りＯ
，り信号１２１、転送イｈ号１２２、許容類似度を示す
レベル信号４２１は各記号列照合ユニッ）　５００に共
通に供給される。

記号列照合ユニット５００への許容類似度の設定は、ユ
ニット選択値＋ｊ５３ｘ　　と共に基本レジスタセット
信号５３２をデコーダ５３０　に供給し、レベル信号４
２１　全記号列照合部５１０に供給することに、！：り
行なわれる。このとき、デコーダ５３０は許容類似度を
設定しようとする記号列照合ユニット５００にのみレジ
スタセット信号４２２を印加する。

記号列入力Ａｊ５子１１１　から照合ヌゴ称となる記号
列を７１′八成する記号コードを逐次入力すると、各記
号列照合ユニット５０（ｌ　内に登録されている各照合
記号列と並列に１ｊ４ｊ合１７、許容類似度以上の高い
’Ｊｕｌ　イｊヅ塵を小す１１ｆ（合Ｂｅ号夕１島記憶
し、ている；）１シ号列照合ユニノ）５（１（＋からＩ
Ｉべ合出力４１１か発生する。

エン−１−夕５２（１に−この照合出力４１１を蛍けで
それをニー７〜ｌ−イｌ＜　Ｌ、入力さ力／６二記号列
の分類コード５；２１と七・合したこと４−示す０〃の
イ１幼イば号５２２不二発生する。いずれの！］（１合
出力４１１も不整合を示Ｌ７７いる土・・シ合ＶこｋＪ
ｌ、エンコーダは不整合を示す１″のイ」効（＋’ｊ号
５２２攻゛発生１″る。

従って、イ］幻化号５２２と分類コード５２１を監視す
イ、ことにより、入力さオ］た記＋じ一列の分類か可能
とな４、。また、エンコーダ５２０とテコータ′５３０
　とにより、入出力端子数を削減し、木りに一吋列照合
装置道のＬＳＩ化を容易にする。

（発明の効果） 以上述べたように、本発明の記号列照合部■？は類似度
による照合を可能とするので、一部の記号が誤った記号
列の照合も可能にする。英単語、特に名詞は単数形、複
数形に」こり最終文学が異なる場合が多い。例えは、’
ｒｎｅｍｏｒｙ”は複数形になるとＶｍｅｍｏｒｉｅｓ
“になる。この場合、基本の”　ｎＩｅｍｏ　ｒ　３’
　”を照合記号列とし、−文学の誤りをボ「すように許
容類似度を設定すれは、ｍｅｍｏ　ｒ　ｉ　ｅ　ｓ　”
も抽出できる。捷だ、一部の記号が欠けた記号列あるい
は余分な記号が付加された記号列の照合も〒１」能にす
る。このような一部の記号の欠けや余分な記号の付加は
一般に記号列内のどこに生ずるかまたどのように記号が
欠けるか、付加されるか予め判断できない。したがって
、起りうるすべでの記号列の変化に刈し、従来の記号列
照合ではそれらの許容するようにプログラミングしてお
かなければならない。しかし、本発明の記号列照合方式
及び記号列照合装置では許容類似度を設定しておくこと
で容易に対処できる。すなわち、本発明の記号列照合装
置ζＣとその方式し１柔軟な記号列照合全可能にする ！！た、人υ３力Ｑｉｆ１：子数を削減し、Ｊ、ＳＩ化
を容易に可能にし、価格低下をもたらす。

なお、現状の２５６キロビツトＨ，ＡＭの半２５１体技
術を用いれば、８ビツトコードの記号８個からなる照合
記号列全１２８個を１チツプに格納でき、それらを並列
に照合できる。

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

この記号列識別装置はＯＣＲ，装置や音声認識装置など
バタン認ｉｉ！ｇ！を行なうシステムにおける特徴系列
の分類においても役立つ。この記号列識別装置なの１チ
ツプＬＳＩ化は言語翻訳に必要な辞言としでも役立つ。

このチップに通常Ｉ（、Ａ　Ｍを接続し、各記号列の分
類コードに対応すけて、単語の訳語を格納すると、１チ
ノフにつき１２８単語丑での翻訳が記号列の入力の完了
時に直ちに求する。記号列識別チップに接続される通常
Ｒ，ＡＭには記号別の分類コードに対応ずけて、各種の
情報を格納することが可能であって、そＦ′Ｌによっで
、種々の記号列情報処理構能が達成される。、たとえは
、記号列の分類コードに対応すけ、単語の品詞コードや
記号列の出現回数や記号列文章に対する処理命令を格納
すると、知識情報の収集や整理が行ないやすくなる。

この記号列抽出装置の処理速度は、記号記憶手段２］０
．４］０に使われる半導体ＲＡＭのサイクルタイムＴｃ
が１つの記号の処理時間にほぼヌ゛１応する。１゛Ｃを
１００ｍ５とすると、１０　個の記号列のテキストに対
する１０　個の記号列による照合を１０秒で行なえる。

現状のソフトウェアによる照合では１０時間程度を心太
とするので、本発明の記号列照合装置は著しく照合時間
を短酩する。

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

【図面の簡単な説明】

第１図は本発明による記号列照合装置の一実施例の説明
図、第２図はクロ２２４８号と転送信号のタイミング図
、第３図は記号列照合装置の動作説明図、第４図、４５
図は本発明の他の実施例の説明図、第６図は記号夕１」
照合の説明図である。 １】（）・・・・・・記号列記憶手段、１２０・・・・
・カウンタ、１２３・・・・・・第１の演算手段、】２
４・−一時記憶手段、１３０・・・・・レジスタ、１４
０・・・・・加算器、４１ｏ・・曲コンパレータ、’４
２０・・・・・・レベル設定レジスタ、５００・・・・
・・記号列照合ユニット、５］０・・・・・・記号列照
合部、５２０・・・・・　エンコーダ、５３０・・・・
・・テコータ。 第２図 ＭＥＭＲＹＸ　　　　　　　　ＭＥ７．ｌＸ０ＲＹＴｏ
　Ｔ′ＴｈＴ３Ｔ４Ｔ５１下２　　　　　　　　　　　
　　　丁ＯＴ＋　丁２丁３丁４丁５丁６−「ｉ第４図 第５図 第６図

Claims (7)

【特許請求の範囲】
1. （１）記号コードをアドレス入力とし、照合記号列を記
   憶する記号列記憶手段と、この各出力線につながる第１
   の演算手段と、複数の演算手段間を相互に結合する第１
   の一時記憶手段と、特定の第１の一時記憶手段の出力に
   つながる第２の一時記憶手段と、第２の一時記憶手段に
   つながる第２の演算手段とを備えたことを特徴とする記
   号列照合装置。
2. （２）第１の演算手段と第１一時記憶手段とがそれぞれ
   カウンタあるいはシフトレジスタであることを特徴とす
   る特許請求の範囲第１項、記載の記号列照合装置。
3. （３）記号コードをアドレス入力とし、照合記号列を記
   憶する記号列記憶手段と、この各出力線につながる第１
   の演算手段と、複数の演算手段間を相互に結合する第１
   の一時記憶手段と、特定の第１の一時記憶手段の出力に
   つながる第２の一時記憶手段と、第２の一時記憶手段に
   つながる第２の演算手段と、外部から与えられる許容類
   似度を記憶するレジスタと、このレジスタの内容と第２
   の演算手段の出力とを比較し、照合結果を出力するコン
   パレータとを含むことを特徴とする記号列照合装置。
4. （４）第１の演算手段と第１一時記憶手段とがそれぞれ
   カウンタあるいはシフトレジスタであることを特徴とす
   る特許請求の範囲第３項記載の記号列照合装置。
5. （５）記号コードをアドレス入力とし、照合記号列を記
   憶する記号列記憶手段と、この各出力線につながる第１
   の演算手段と、複数の演算手段間を相互に結合する第１
   の一時記憶手段と、特定の第１の一時記憶手段の出力に
   つながる第２の一時記憶手段と、第２の一時記憶手段に
   つながる第２の演算手段と、外部から与えられる許容類
   似度を記憶するレジスタと、このレジスタの内容と第２
   の演算手段の出力とを比較し、照合結果を出力するコン
   パレータと該コンパレータに接続するエンコーダと、該
   レジスタに接続するデコーダとを備えたことを特徴とす
   る記号列照合装置。
6. （６）第１の演算手段と第１一時記憶手段とがそれぞれ
   カウンタあるいはシフトレジスタであることを特徴とす
   る特請許求の範囲第５項記載の記号列照合装置。
7. （７）記号に関連づけたビットパタンで照合記合列を記
   憶する記号列記憶手段のＮ（正整数）番目と（Ｎ＋１）
   番目の出力線に各々つながるＮ番目第１論理演算手段と
   （Ｎ＋１）番目第１演算手段との間のＮ番目第１一時記
   憶手段の内容を（Ｎ−１）番目第１一時記憶手段の内容
   にＮ番目記号列記憶手段の出力線により制御されたＮ番
   目第１演算出段の演算処理を施こしたものとし且つ、特
   定の第１一時記憶手段の互いに異なる時刻の内容に第２
   の演算手段による演算処理を施すことで前記記号列記憶
   手段の内容と逐次入力された記号列の類似度を求めるこ
   とを特徴とする記号列照合装置の制御方式。