JPH02115973A - 記号列照合装置とその制御方法 - Google Patents
記号列照合装置とその制御方法Info
- Publication number
- JPH02115973A JPH02115973A JP63269746A JP26974688A JPH02115973A JP H02115973 A JPH02115973 A JP H02115973A JP 63269746 A JP63269746 A JP 63269746A JP 26974688 A JP26974688 A JP 26974688A JP H02115973 A JPH02115973 A JP H02115973A
- Authority
- JP
- Japan
- Prior art keywords
- symbol
- symbol string
- cell
- matching
- input
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/02—Comparing digital values
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/903—Querying
- G06F16/90335—Query processing
- G06F16/90344—Query processing by using string matching techniques
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F2207/02—Indexing scheme relating to groups G06F7/02 - G06F7/026
- G06F2207/025—String search, i.e. pattern matching, e.g. find identical word or best match in a string
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
- Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y10S707/00—Data processing: database and file management or data structures
- Y10S707/99931—Database or file accessing
- Y10S707/99937—Sorting
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Physics & Mathematics (AREA)
- Databases & Information Systems (AREA)
- General Engineering & Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Computational Linguistics (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
（産業上の利用分野）
本発明は情報処理システムの構成要素に係り、より具体
的には複数の被照合記号列の中から照合記号列と特定の
関係にある被照合記号列を抽出する記号列照合装置とそ
の制御方式に関するものである。
的には複数の被照合記号列の中から照合記号列と特定の
関係にある被照合記号列を抽出する記号列照合装置とそ
の制御方式に関するものである。
（従来の技術）
記号列照合装置はテキストデータベースの検索や、バタ
ン認識システムでの特徴系列の照合、ワープロで作成さ
れた文書からのキーワード抽出、言語翻訳の支援や電子
メールのアドレスフィルタリング等に使われ、これらの
情報処理システムにおいて欠くことの出来ないものであ
る。
ン認識システムでの特徴系列の照合、ワープロで作成さ
れた文書からのキーワード抽出、言語翻訳の支援や電子
メールのアドレスフィルタリング等に使われ、これらの
情報処理システムにおいて欠くことの出来ないものであ
る。
記号列照合では、照合記号列と完全に一致する被照合記
号列のみならず、照合記号列とある類似性を持った被照
合記号列をも複数の被照合記号列の中から抽出できるこ
とが望まれる。なぜならば、例えば、テキストデータベ
ース検索においては、テキストがミススペルを含む場合
や、あやふやなキーワードで検索を行なう場合にこの機
能が必要であるし、パターン認識において特徴系列同士
の照合を行なう場合には、完全に一致するものが見つか
ることは希で、複数の被照合記号列中より照合記号列に
最もよく似た被照合記号列を選び出すことが必要になる
からである。
号列のみならず、照合記号列とある類似性を持った被照
合記号列をも複数の被照合記号列の中から抽出できるこ
とが望まれる。なぜならば、例えば、テキストデータベ
ース検索においては、テキストがミススペルを含む場合
や、あやふやなキーワードで検索を行なう場合にこの機
能が必要であるし、パターン認識において特徴系列同士
の照合を行なう場合には、完全に一致するものが見つか
ることは希で、複数の被照合記号列中より照合記号列に
最もよく似た被照合記号列を選び出すことが必要になる
からである。
照合記号列と被照合記号列の類似度を測るのには距離と
いう概念が用いられる。ここで言う距離とは、１記号の
除去、置換、挿入を単位操作として、何回の操作である
記号列からある記号列に移れるかを考え、そのうち最少
の回数をこの二つの記号列間の距離とするものである。
いう概念が用いられる。ここで言う距離とは、１記号の
除去、置換、挿入を単位操作として、何回の操作である
記号列からある記号列に移れるかを考え、そのうち最少
の回数をこの二つの記号列間の距離とするものである。
この距離という概念については、例えば１９８０年発行
のコンピユーテイング・サーベイ（Ｃｏｍｐｕｔｉｎｇ
５ｕｒｖｅｙｓ）誌、第１２巻４号１．３８１ページ
の文献、題名アブロクシメイトストリング・マツチング
（Ａｐｐｒｏｘｉｍａｔｅ ＳｔｒｉｎｇＭａｔｃｈｉ
ｎｇ）、著者パトリックホール（Ｐａｔｒｉｃｋ、 Ｈ
ａｌｌ）、ジェオフ・ダウリング（Ｇｅｏｆｆ、 Ｄｏ
ｗｌｉｎｇ）、に詳しく記載されている。
のコンピユーテイング・サーベイ（Ｃｏｍｐｕｔｉｎｇ
５ｕｒｖｅｙｓ）誌、第１２巻４号１．３８１ページ
の文献、題名アブロクシメイトストリング・マツチング
（Ａｐｐｒｏｘｉｍａｔｅ ＳｔｒｉｎｇＭａｔｃｈｉ
ｎｇ）、著者パトリックホール（Ｐａｔｒｉｃｋ、 Ｈ
ａｌｌ）、ジェオフ・ダウリング（Ｇｅｏｆｆ、 Ｄｏ
ｗｌｉｎｇ）、に詳しく記載されている。
第１０図（ａ）〜（Ｃ）はそれぞれ上で述べた１記号の
除去、置換、挿入という単位操作の定義を例によって示
したものである。同図では、元の記号列“ＡＢＣＤ””
にこれらの単位操作を加えて記号列を変化させている。
除去、置換、挿入という単位操作の定義を例によって示
したものである。同図では、元の記号列“ＡＢＣＤ””
にこれらの単位操作を加えて記号列を変化させている。
同図において、ＣはＣ以外の任意の記号の意味であり、
Ｘは任意の記号の意味である。なお、これらの記号は以
下の文中において同様の意味で用いる。
Ｘは任意の記号の意味である。なお、これらの記号は以
下の文中において同様の意味で用いる。
第１０図（ｄ）は例として記号列“ＡＢＣＤ”から距離
３の範囲内にある記号列の一部を示したものである。
３の範囲内にある記号列の一部を示したものである。
同図より、例えば“ＡＢＣＤ”は距離１であるから、距
離２である“ＡＣＸＤ”よりも“ＡＢＣＤ”に近いとい
うことになる。
離２である“ＡＣＸＤ”よりも“ＡＢＣＤ”に近いとい
うことになる。
照合記号列から距離１の範囲内の被照合記号列を抽出で
きる記号列照合装置としては、特開昭５９−２１６８０
８号公報［記号列照合装置」（以下先行発明と呼ぶ）が
ある。
きる記号列照合装置としては、特開昭５９−２１６８０
８号公報［記号列照合装置」（以下先行発明と呼ぶ）が
ある。
第１１図に先行発明による記号列照合装置の動作の概念
を示す。同図は一例として“ＡＢＣＤ””を照合記号列
とし、この照合記号列から距離１の範囲内の被照合記号
列を抽出する場合を示している。−は１ビツトの情報を
記憶できるセルを示し、矢印はセル間の記憶データの転
送を示している。各セルは矢印の横に書かれた記号が入
力されたときに矢印で示された次のセルに記憶データを
転送する。矢印の横に書かれた記号以外の記号が人力さ
れると、図示していないが、セルの記憶データによらず
０が転送される。各矢印により転送されてきたデータは
、図示していないが、理論和を取られてセルに入力され
る。
を示す。同図は一例として“ＡＢＣＤ””を照合記号列
とし、この照合記号列から距離１の範囲内の被照合記号
列を抽出する場合を示している。−は１ビツトの情報を
記憶できるセルを示し、矢印はセル間の記憶データの転
送を示している。各セルは矢印の横に書かれた記号が入
力されたときに矢印で示された次のセルに記憶データを
転送する。矢印の横に書かれた記号以外の記号が人力さ
れると、図示していないが、セルの記憶データによらず
０が転送される。各矢印により転送されてきたデータは
、図示していないが、理論和を取られてセルに入力され
る。
同図において、初期状態ではセルｆ１１の記憶データの
み１にし、他の全てのセルの記憶データは０にしておく
。この状態から、被照合記号列として、例えば、”ＡＢ
ＣＤ”を１記号ずつ順に入力するとセルｆ１５の記憶デ
ータが１になり、”ＡＢＤ”、”ＡＢＣＤ”、“ＡＢＸ
ＣＤ”などを入力するとセルｆ２５の記憶データが１に
なる。すなわち、セルｆ１５を監視することによリ、入
力された被照合記号列が照合記号列から距離０であるか
どうかわかり、七ノ鴨、を監視することにより、入力さ
れた被照合記号列が照合記号列から距離１であるかどう
かがわかる。
み１にし、他の全てのセルの記憶データは０にしておく
。この状態から、被照合記号列として、例えば、”ＡＢ
ＣＤ”を１記号ずつ順に入力するとセルｆ１５の記憶デ
ータが１になり、”ＡＢＤ”、”ＡＢＣＤ”、“ＡＢＸ
ＣＤ”などを入力するとセルｆ２５の記憶データが１に
なる。すなわち、セルｆ１５を監視することによリ、入
力された被照合記号列が照合記号列から距離０であるか
どうかわかり、七ノ鴨、を監視することにより、入力さ
れた被照合記号列が照合記号列から距離１であるかどう
かがわかる。
これにより照合記号列から距離１の範囲内にある被照合
記号列を抽出する記号列照合装置を構成することが可能
になった。しかし、音声認識や手書き文字認識などのパ
ターン認識への応用においては、抽出する記号列間の距
離は１では足りない。例えば音声認識においては、音声
から抽出された特徴系列（照合記号列にあたる）には話
者の年齢や性別、出身地などの違いにより様々なゆらぎ
が含まれており、あらかじめ用意された特徴系列のテン
プレート（被照合記号列にあたる）との距離が距離１の
範囲内に納まることは希である。このような用途に応用
するためには、もっと遠くの距離にある被照合記号列ま
で抽出できるようにし、抽出された被照合記号列の中か
ら最も照合記号列に近いものを選べるようにならなけれ
ばならない。このような問題を解決するため前述の先行
発明は別の記号列照合装置を提示している。
記号列を抽出する記号列照合装置を構成することが可能
になった。しかし、音声認識や手書き文字認識などのパ
ターン認識への応用においては、抽出する記号列間の距
離は１では足りない。例えば音声認識においては、音声
から抽出された特徴系列（照合記号列にあたる）には話
者の年齢や性別、出身地などの違いにより様々なゆらぎ
が含まれており、あらかじめ用意された特徴系列のテン
プレート（被照合記号列にあたる）との距離が距離１の
範囲内に納まることは希である。このような用途に応用
するためには、もっと遠くの距離にある被照合記号列ま
で抽出できるようにし、抽出された被照合記号列の中か
ら最も照合記号列に近いものを選べるようにならなけれ
ばならない。このような問題を解決するため前述の先行
発明は別の記号列照合装置を提示している。
第１２図は先行発明による記号列照合装置の動作の概念
を示すものである。同図は第１１図と同じく例として照
合記号例“ＡＢＣＤ”の場合を示している。
を示すものである。同図は第１１図と同じく例として照
合記号例“ＡＢＣＤ”の場合を示している。
同図中のセルと矢印は第１１図と同じ意味を持っており
、このような構成により照合記号列に対してその記号列
長未満の任意数の記号を挿入、また置換した被照合記号
列を抽出することができる。
、このような構成により照合記号列に対してその記号列
長未満の任意数の記号を挿入、また置換した被照合記号
列を抽出することができる。
（発明が解決しようとする課題）
しかしこの構成では、単位操作の一つである上記号の除
去を考慮にいれていないため、照合記号列から一定の距
離内にある被照合記号列を公平に抽出することができな
い。具体的にいうと、例えば、距離３である“ＡＸＢＸ
ＣＸＤ”は抽出できるが、距離２である“ＡＤ”は抽出
できないということになる。
去を考慮にいれていないため、照合記号列から一定の距
離内にある被照合記号列を公平に抽出することができな
い。具体的にいうと、例えば、距離３である“ＡＸＢＸ
ＣＸＤ”は抽出できるが、距離２である“ＡＤ”は抽出
できないということになる。
これでは、照合記号列と類似度の高い被照合記号列が抽
出できず代わりに類似度の低い被照合記号列が抽出され
るといことになり、パターン認識などへの応用は困難で
ある。
出できず代わりに類似度の低い被照合記号列が抽出され
るといことになり、パターン認識などへの応用は困難で
ある。
以上説明したように従来の記号列照合装置では、照合記
号列から距離１の範囲内にある被照合記号列は抽出でき
るが、それ以上の距離になると有効な抽出を行なうこと
が出来ないという問題があった。
号列から距離１の範囲内にある被照合記号列は抽出でき
るが、それ以上の距離になると有効な抽出を行なうこと
が出来ないという問題があった。
本発明の目的はこのような問題を解決し、簡易な構成で
照合記号例から任意の距離にある被照合記号列を抽出す
ることが可能な記号列照合装置とその制御方式を提供す
ることにある。
照合記号例から任意の距離にある被照合記号列を抽出す
ることが可能な記号列照合装置とその制御方式を提供す
ることにある。
（課題を解決しようとするための手段）上記目的を達成
するため、本発明の記号列照合装置は、長さＮ（Ｎは正
整数）の照合記号列に対して、記号列比較結果を記憶す
るセルをＭ行（Ｍは正整数）Ｎ＋１列に並べたセルアレ
イと、照合記号列のｊ番目（ｊはＮ以下の任意の正整数
）の記号と同じ被照合記号が与えられたときのみ前記セ
ルアレイのｉ行（ｉはＭ以下の任意の正整数カ列目であ
るセルｆ１．の記憶リ データを七）Ｉ／ｆｉｊ＋、に転送する第１の転送手段
と、照合記号列のｊ番目の記号と違う被照合記号が与え
られなときのみ前記セルアレイのｈ行（ｈはＭ未満の任
意の正整数）ｊ列目であるセルｆ）１ｊの記憶データを
セルｆｈ＋１ｊ＋１に転送する第２の転送手段と、被照
合記号が与えられると、与えられた被照合記号の如何に
かかわらず前記セルアレイのｈ行に列目（ｋはＮ＋１以
下の任意の正整数）である七ノ鴨、の記憶データをセル
ｆｈ＋１ｋに転送する第３の転送手段と、前記第１から
第３の転送手段によりセル−に少なくとも一つ１が転送
されてくると七ルーの記憶データを１にし、前記第１か
ら第３の転送手段によりセル−に１が一つも転送されて
こなければセルｆ１にの記憶データを０にする人力手段
と、セル萄の記憶データが１になると、前記入力手段に
よりセ” ’ｈ ＋ ｌｊ ＋ １に与えられた入力に
よらず、セルｆ）ｌ＋１ｊ＋１の記憶データを１にセッ
トするセット手段より構成されており、このような構成
において、少なくとも、前記セルアレイの全てのセルの
記憶データを０にした後、セルｆ１１の記憶データを１
にセットすることにより初期設定を行なうことと、被照
合記号列を上記号ずつ順に与えることにより記号列照合
を実行することと、前記セルアレイのＮ＋１列目のＭ個
のセルの中から、記憶データが１であり、かついちばん
行番号が小さいセルを探すことにより、照合結果として
照合記号列と被照合記号列との距離を得ることとを含む
ことを特徴とする制御方式を用いている。
するため、本発明の記号列照合装置は、長さＮ（Ｎは正
整数）の照合記号列に対して、記号列比較結果を記憶す
るセルをＭ行（Ｍは正整数）Ｎ＋１列に並べたセルアレ
イと、照合記号列のｊ番目（ｊはＮ以下の任意の正整数
）の記号と同じ被照合記号が与えられたときのみ前記セ
ルアレイのｉ行（ｉはＭ以下の任意の正整数カ列目であ
るセルｆ１．の記憶リ データを七）Ｉ／ｆｉｊ＋、に転送する第１の転送手段
と、照合記号列のｊ番目の記号と違う被照合記号が与え
られなときのみ前記セルアレイのｈ行（ｈはＭ未満の任
意の正整数）ｊ列目であるセルｆ）１ｊの記憶データを
セルｆｈ＋１ｊ＋１に転送する第２の転送手段と、被照
合記号が与えられると、与えられた被照合記号の如何に
かかわらず前記セルアレイのｈ行に列目（ｋはＮ＋１以
下の任意の正整数）である七ノ鴨、の記憶データをセル
ｆｈ＋１ｋに転送する第３の転送手段と、前記第１から
第３の転送手段によりセル−に少なくとも一つ１が転送
されてくると七ルーの記憶データを１にし、前記第１か
ら第３の転送手段によりセル−に１が一つも転送されて
こなければセルｆ１にの記憶データを０にする人力手段
と、セル萄の記憶データが１になると、前記入力手段に
よりセ” ’ｈ ＋ ｌｊ ＋ １に与えられた入力に
よらず、セルｆ）ｌ＋１ｊ＋１の記憶データを１にセッ
トするセット手段より構成されており、このような構成
において、少なくとも、前記セルアレイの全てのセルの
記憶データを０にした後、セルｆ１１の記憶データを１
にセットすることにより初期設定を行なうことと、被照
合記号列を上記号ずつ順に与えることにより記号列照合
を実行することと、前記セルアレイのＮ＋１列目のＭ個
のセルの中から、記憶データが１であり、かついちばん
行番号が小さいセルを探すことにより、照合結果として
照合記号列と被照合記号列との距離を得ることとを含む
ことを特徴とする制御方式を用いている。
（作用）
第７図は本発明の技術思想を説明するための概念図であ
る。同図は列として４行５列のセルアレイを用い“ＡＢ
ＣＤ”′を照合記号列とした場合を示している。以下詳
しく説明するように、この構成により、“ＡＢＣＤ’”
から距離３の範囲内にある任意の被照合記号列を抽出す
ることができる。
る。同図は列として４行５列のセルアレイを用い“ＡＢ
ＣＤ”′を照合記号列とした場合を示している。以下詳
しく説明するように、この構成により、“ＡＢＣＤ’”
から距離３の範囲内にある任意の被照合記号列を抽出す
ることができる。
同図において、セルは丸印で示され、第一の転送手段は
行方向の実線の矢印、第二の転送手段は列方向の実線の
矢印、第３の転送手段は対角線方向の実線の矢印、セッ
ト手段は対角線方向の二重線の矢印で示されている。第
１及び第２の転送手段は、その矢印の横に書いである被
照合記号が与えられたときだけ、矢印にしたがって各セ
ルの記憶データを次のセルに転送する。第３の転送手段
は、被照合記号が与えられると、与えられた被照合記号
の如何にかかわらず、矢印にしたがって各セルの記憶デ
ータを次のセルに転送する。図中には明示していないが
、セルにはこれらの転送手段から転送されてきたデータ
を受は取る入力手段があり、少なくとも一つ１が転送さ
れてくるとセルの記憶データは１になり、一つも１が転
送されてこないとセルの記憶データは０になる。セット
手段は、本発明におけるもっとも特徴的な部分であって
、あるセルの記憶データが１になると、入力手段から入
力されたデータに関係なく、二重線の矢印に従って次の
セルの記憶データも１にセットする働きを持つ。つまり
、例えばセルｒ１□が１であると、同時にセルｆ２３、
ｆ３４、ｆ４５も１となり、セルｆ２□が１であると、
同時にセルｆ３３、ｆ４４も１となる。このような構成
において、第５列目のセルの記憶データを読み取ること
により照合結果を得ることができる。以下本発明を、第
８図、第９図（ａ）−（ｈ）に基づいて更に詳細に説明
する。
行方向の実線の矢印、第二の転送手段は列方向の実線の
矢印、第３の転送手段は対角線方向の実線の矢印、セッ
ト手段は対角線方向の二重線の矢印で示されている。第
１及び第２の転送手段は、その矢印の横に書いである被
照合記号が与えられたときだけ、矢印にしたがって各セ
ルの記憶データを次のセルに転送する。第３の転送手段
は、被照合記号が与えられると、与えられた被照合記号
の如何にかかわらず、矢印にしたがって各セルの記憶デ
ータを次のセルに転送する。図中には明示していないが
、セルにはこれらの転送手段から転送されてきたデータ
を受は取る入力手段があり、少なくとも一つ１が転送さ
れてくるとセルの記憶データは１になり、一つも１が転
送されてこないとセルの記憶データは０になる。セット
手段は、本発明におけるもっとも特徴的な部分であって
、あるセルの記憶データが１になると、入力手段から入
力されたデータに関係なく、二重線の矢印に従って次の
セルの記憶データも１にセットする働きを持つ。つまり
、例えばセルｒ１□が１であると、同時にセルｆ２３、
ｆ３４、ｆ４５も１となり、セルｆ２□が１であると、
同時にセルｆ３３、ｆ４４も１となる。このような構成
において、第５列目のセルの記憶データを読み取ること
により照合結果を得ることができる。以下本発明を、第
８図、第９図（ａ）−（ｈ）に基づいて更に詳細に説明
する。
第８図、第９図（ａ）−（ｈ）はそれぞれ第７図と同じ
構成を示すものであるが、簡単のため一部の記号を省略
して描いである。以下で用いる記号でこれらの図中に明
示いていないものは、第７図中の対応する部位の記号を
用いている。また図中のセルで斜線を施したものは記憶
データが１であることを示し、白いセルは記憶データが
０であること示している。
構成を示すものであるが、簡単のため一部の記号を省略
して描いである。以下で用いる記号でこれらの図中に明
示いていないものは、第７図中の対応する部位の記号を
用いている。また図中のセルで斜線を施したものは記憶
データが１であることを示し、白いセルは記憶データが
０であること示している。
第８図は、照合を始める前の、本発明による記号列照合
装置の初期状態を示す図である。初期状態ではセルｆ１
１の記憶データを１にセットしておく。するとセット手
段により、セノＬ／ｆ２２、ｆ３３、ｆ４４の記憶デー
タも１にセットされる。これら以外のセルの記憶データ
はすべてＯにしておく。
装置の初期状態を示す図である。初期状態ではセルｆ１
１の記憶データを１にセットしておく。するとセット手
段により、セノＬ／ｆ２２、ｆ３３、ｆ４４の記憶デー
タも１にセットされる。これら以外のセルの記憶データ
はすべてＯにしておく。
第９図（ａ）−（ｄ）は照合記号列“’ＡＢＣＤ’”に
対して被照合記号列“ＡＢＣＤ”を順にＡ、 Ｂ、 Ｃ
，Ｄと入力していったときの本発明による記号列照合装
置の動作を、１記号の入力毎に示したものである。各被
照合記号が人力された後のセルアレイは、それまでに入
力された被照合記号列と照合記号列“ＡＢＣＤ”との照
合結果を示している。この照合結果を知るには、５列目
のセルの記憶データを読み取ればよい。具体的には、５
列目のセルで記憶データが１になっているものの中で、
一番行番号が小さいものを探し、それがセルｆ１５なら
、被照合記号列と照合記号列との距離は距離０、セルｆ
２５なら距離１、セル曳なら距離２、ｒ４５なら距離３
、該当するセルがなければ距離４以上となる。以下、図
の順にしたがって各図について詳しく説明する。
対して被照合記号列“ＡＢＣＤ”を順にＡ、 Ｂ、 Ｃ
，Ｄと入力していったときの本発明による記号列照合装
置の動作を、１記号の入力毎に示したものである。各被
照合記号が人力された後のセルアレイは、それまでに入
力された被照合記号列と照合記号列“ＡＢＣＤ”との照
合結果を示している。この照合結果を知るには、５列目
のセルの記憶データを読み取ればよい。具体的には、５
列目のセルで記憶データが１になっているものの中で、
一番行番号が小さいものを探し、それがセルｆ１５なら
、被照合記号列と照合記号列との距離は距離０、セルｆ
２５なら距離１、セル曳なら距離２、ｒ４５なら距離３
、該当するセルがなければ距離４以上となる。以下、図
の順にしたがって各図について詳しく説明する。
まず初期状態から被照合記号Ａが入力されると、各セル
の記憶データは、第８図で示した初期状態から第９図（
ａ）のように変化する。この図は、上で述べたように、
被照合記号列“ＡＢＣＤ”の照合の途中経過として、照
合記号列“ＡＢＣＤ”に対する被照合記号列“Ａ”の照
合結果を示している。七ノｔ／ｆ４５の記憶データが１
になっており、これはＡ″が１“ＡＢＣＤ”から距離３
にあることを示している。
の記憶データは、第８図で示した初期状態から第９図（
ａ）のように変化する。この図は、上で述べたように、
被照合記号列“ＡＢＣＤ”の照合の途中経過として、照
合記号列“ＡＢＣＤ”に対する被照合記号列“Ａ”の照
合結果を示している。七ノｔ／ｆ４５の記憶データが１
になっており、これはＡ″が１“ＡＢＣＤ”から距離３
にあることを示している。
次に被照合記号Ｂが入力されると、各セルの記憶データ
は、第９図（ａ）で示した状態から第９図（ｂ）のよう
に変化する。この図は照合記号列“ＡＢＣＤ”に対する
被照合記号列“’ＡＢ”の照合結果を示している。セル
ｆ３５の記憶データが１になっており、これは“’ＡＢ
”が“ＡＢＣＤ”から距離２にあることを示している。
は、第９図（ａ）で示した状態から第９図（ｂ）のよう
に変化する。この図は照合記号列“ＡＢＣＤ”に対する
被照合記号列“’ＡＢ”の照合結果を示している。セル
ｆ３５の記憶データが１になっており、これは“’ＡＢ
”が“ＡＢＣＤ”から距離２にあることを示している。
続いて被照合記号Ｃが入力されると、各セルの記憶デー
タは、第９図（ｂ）で示した状態から第９図（ｅ）のよ
うに変化する。この図は照合記号列“ＡＢＣＤ”に対す
る被照合記号列“ＡＢＣ”の照合結果を示している。
タは、第９図（ｂ）で示した状態から第９図（ｅ）のよ
うに変化する。この図は照合記号列“ＡＢＣＤ”に対す
る被照合記号列“ＡＢＣ”の照合結果を示している。
セル’２５の記憶データが１になっており、これは“Ａ
ＢＣ”が“ＡＢＣＤ”から距離１にあることを示してい
る。
ＢＣ”が“ＡＢＣＤ”から距離１にあることを示してい
る。
最後に被照合記号りが入力されると、各セルの記憶デー
タは、第９図（Ｃ）で示した状態から第９図（ｄ）のよ
うに変化する。この図は照合記号“ＡＢＣＤ””に対す
る被照合記号列“ＡＢＣＤ”の最終的な照合結果を示し
ている。セルｆ１５の記憶データが１になっており、こ
れは“ＡＢＣＤ”が“ＡＢＣＤ”から距離０にあること
を示している。
タは、第９図（Ｃ）で示した状態から第９図（ｄ）のよ
うに変化する。この図は照合記号“ＡＢＣＤ””に対す
る被照合記号列“ＡＢＣＤ”の最終的な照合結果を示し
ている。セルｆ１５の記憶データが１になっており、こ
れは“ＡＢＣＤ”が“ＡＢＣＤ”から距離０にあること
を示している。
このように、被照合記号列“ＡＢＣＤ”を順に１記号ず
つ入力していくことにより、この被照合記号列に対する
照合の途中経過及び最終結果を順次知ることが出来る。
つ入力していくことにより、この被照合記号列に対する
照合の途中経過及び最終結果を順次知ることが出来る。
このようにして得られた照合結果は、明らかに被照合記
号列と照合記号列との間の正しい距離を与えている。な
ぜなら、被照合記号列“Ａｔｊは“ＡＢＣＤ””に単位
操作である１記号の除去を３回行なったものだし、同じ
くＡＢ”は２回、”ＡＢＣ”′は１回、“ＡＢＣＤ”は
０回行なったものだからである。
号列と照合記号列との間の正しい距離を与えている。な
ぜなら、被照合記号列“Ａｔｊは“ＡＢＣＤ””に単位
操作である１記号の除去を３回行なったものだし、同じ
くＡＢ”は２回、”ＡＢＣ”′は１回、“ＡＢＣＤ”は
０回行なったものだからである。
第９図（ｅ）−（ｈ）は第９図（ａ）−（ｄ）と同じ条
件で、被照合記号列を“ＡＣＸＤ”にした場合を示した
ものである。
件で、被照合記号列を“ＡＣＸＤ”にした場合を示した
ものである。
簡単に説明すると、第９図（ｅ）は被照合記号列“Ａ”
が照合記号列“ＡＢＣＤ”から距離３であることを、第
９図（Ｏｌ（ｇ）、（ｈ）はそれぞれ被照合記号列“Ａ
Ｃ”、”ＡＣＸ”１、”ＡＣＸＤ”が照合記号列”ＡＢ
ＣＤ”から距離２であることを示している。これらの結
果がそれぞれの記号列間の正しい距離を与えていること
は明らかである。
が照合記号列“ＡＢＣＤ”から距離３であることを、第
９図（Ｏｌ（ｇ）、（ｈ）はそれぞれ被照合記号列“Ａ
Ｃ”、”ＡＣＸ”１、”ＡＣＸＤ”が照合記号列”ＡＢ
ＣＤ”から距離２であることを示している。これらの結
果がそれぞれの記号列間の正しい距離を与えていること
は明らかである。
このようにして、第７図に示した構成により、ある被照
合記号列が照合記号列“ＡＢＣＤ”から距離３の範囲内
にあるかどうか判別することできる。よって、複数の被
照合記号列を次々に人力していけば、その中から照合記
号列から距離３の範囲内にある全ての被照合記号列を抽
出することが可能になる。他の任意の照合記号列に対し
ても、その記号列長に応じた列数を持ち、抽出したい任
意の距離数に応じた行数を持つセルアレイを構成すれば
、同様の記号列照合を行なうことができる。
合記号列が照合記号列“ＡＢＣＤ”から距離３の範囲内
にあるかどうか判別することできる。よって、複数の被
照合記号列を次々に人力していけば、その中から照合記
号列から距離３の範囲内にある全ての被照合記号列を抽
出することが可能になる。他の任意の照合記号列に対し
ても、その記号列長に応じた列数を持ち、抽出したい任
意の距離数に応じた行数を持つセルアレイを構成すれば
、同様の記号列照合を行なうことができる。
（実施例）
第１図は、本発明による記号列照合装置の一実施例を示
す構成図である。以下同図について説明する。
す構成図である。以下同図について説明する。
まず第１図の構成について説明する。同図において記号
列照合装置は、初期セット端子１１０と、Ｎ本（Ｎは正
整数）の入力端子１２０−１〜１２０−Ｎと、Ｍ行（Ｍ
は正整数）Ｎ＋１列に並べられ、データを入力するＤ端
子、データを出力するＱ端子、データを１にセットする
ＳＥＴ端子を持つレジスター３０と、ｉ行（ｉはＭ以下
の任意の正整数）ｊ列（ｊはＮ以下の任意の正整数）目
のレジスタｆ、、１３０のＱ端子と入力端子１２０−ｊ
に入力端子す がつながり、ｉ＝１であれば右横のレジスタｆｉｊ＋１
１３０のＤ端子に出力端子がつながる第１のアンドゲー
ト１４０と、レジスター１３０（ｈはＭ未満の任意の正
整数）のＱ端子に入力がつながり、入力端子１２０−ｊ
に反転入力端子がつながる第２のアンドゲート１５０と
、レジスター、１３０（ｋはＮ＋１以下の任意の正整数
）のＱ端子に入力がつながるデータ転送線１６０と、入
力として、レジスタｆｈ＋１，１３０のＱ端子につなが
る第１のアンドゲート１４０の出力と、レジスター１３
０のＱ端子につながる第２のアンドゲート１５０の出力
と、レジスタｆ、１１３０のＱ端子につながるデータ転
送線１６０の出力とを受はレジスタｆ）ｌ＋１ｊ＋１１
３０のＤ端子に出力するオアゲート１７０と、レジスタ
ｆゎ、１３０のＱ端子の出力をレジスタｆｈ＋１ｊ＋１
１３０のＳＥＴ端子に入力するセット線１８０と、Ｎ＋
１列目のレジスタ１３０のＱ端子のデータを出力するＭ
本の出力端子１９０−１〜１９０−Ｍとを備えている。
列照合装置は、初期セット端子１１０と、Ｎ本（Ｎは正
整数）の入力端子１２０−１〜１２０−Ｎと、Ｍ行（Ｍ
は正整数）Ｎ＋１列に並べられ、データを入力するＤ端
子、データを出力するＱ端子、データを１にセットする
ＳＥＴ端子を持つレジスター３０と、ｉ行（ｉはＭ以下
の任意の正整数）ｊ列（ｊはＮ以下の任意の正整数）目
のレジスタｆ、、１３０のＱ端子と入力端子１２０−ｊ
に入力端子す がつながり、ｉ＝１であれば右横のレジスタｆｉｊ＋１
１３０のＤ端子に出力端子がつながる第１のアンドゲー
ト１４０と、レジスター１３０（ｈはＭ未満の任意の正
整数）のＱ端子に入力がつながり、入力端子１２０−ｊ
に反転入力端子がつながる第２のアンドゲート１５０と
、レジスター、１３０（ｋはＮ＋１以下の任意の正整数
）のＱ端子に入力がつながるデータ転送線１６０と、入
力として、レジスタｆｈ＋１，１３０のＱ端子につなが
る第１のアンドゲート１４０の出力と、レジスター１３
０のＱ端子につながる第２のアンドゲート１５０の出力
と、レジスタｆ、１１３０のＱ端子につながるデータ転
送線１６０の出力とを受はレジスタｆ）ｌ＋１ｊ＋１１
３０のＤ端子に出力するオアゲート１７０と、レジスタ
ｆゎ、１３０のＱ端子の出力をレジスタｆｈ＋１ｊ＋１
１３０のＳＥＴ端子に入力するセット線１８０と、Ｎ＋
１列目のレジスタ１３０のＱ端子のデータを出力するＭ
本の出力端子１９０−１〜１９０−Ｍとを備えている。
次に請求項１に記載の各構成要素との対応について説明
する。レジスタｆｉｋ１３０はセル−に対応するもので
ある。第１のアンドゲート１４０、第２のアンドゲート
１５０、データ転送線１６０は、それぞれ第１の転送手
段、第２の転送手段、第３の転送手段に対応するもので
ある。また、オアゲート１７０は入力手段、セット線１
８０はセット手段に対応するものである。
する。レジスタｆｉｋ１３０はセル−に対応するもので
ある。第１のアンドゲート１４０、第２のアンドゲート
１５０、データ転送線１６０は、それぞれ第１の転送手
段、第２の転送手段、第３の転送手段に対応するもので
ある。また、オアゲート１７０は入力手段、セット線１
８０はセット手段に対応するものである。
第１図において、入力端子１２０−ｊには、照合記号列
のｊ番目の記号と被照合記号とが一致すれば１、一致し
なければ０が与えられる。すると、第１のアンドゲート
１４０は、照合記号列のｊ番目と被照合同じ記号が与え
られたときだけレジスタｆ）ｌｊ１３０の記憶データを
レジスタｆ、１１３０に転送し、それ以外は０を転送す
る。逆に第２のアンドゲート１５０は照合記号列のｊ番
目と違う被照合記号が与えられたときはレジスター、１
３０の記憶データをレジスター＋Ｊ＋１１３０に転送し
、同じであれば０を転送する。これらは明らかに特許請
求範囲第１項記載の第１及び第２の転送手段の機能に対
応している。
のｊ番目の記号と被照合記号とが一致すれば１、一致し
なければ０が与えられる。すると、第１のアンドゲート
１４０は、照合記号列のｊ番目と被照合同じ記号が与え
られたときだけレジスタｆ）ｌｊ１３０の記憶データを
レジスタｆ、１１３０に転送し、それ以外は０を転送す
る。逆に第２のアンドゲート１５０は照合記号列のｊ番
目と違う被照合記号が与えられたときはレジスター、１
３０の記憶データをレジスター＋Ｊ＋１１３０に転送し
、同じであれば０を転送する。これらは明らかに特許請
求範囲第１項記載の第１及び第２の転送手段の機能に対
応している。
続いて、第１図の実施例の動作について、第２図及び第
３図に基づいて説明する。
３図に基づいて説明する。
第２図は、レジスタ１３０のＤ端子に与えられた入力デ
ータとＳＥＴ端子に与えられたセット信号による、Ｑ端
子の出力データの変化を示したものである。同図は、レ
ジスタ１３０はＳＥＴ端子が０であればＤ端子より与え
られたデータを１周期遅らせてＱ端子より出力し、ＳＥ
Ｔ端子が１であれば、Ｑ端子より与えられたデータによ
らず、Ｑ端子から１を出力することを示している。この
ような機能を持つものとしては、例えばセット入力付き
のマスタースレーブ型フリップフロップなどがある。
ータとＳＥＴ端子に与えられたセット信号による、Ｑ端
子の出力データの変化を示したものである。同図は、レ
ジスタ１３０はＳＥＴ端子が０であればＤ端子より与え
られたデータを１周期遅らせてＱ端子より出力し、ＳＥ
Ｔ端子が１であれば、Ｑ端子より与えられたデータによ
らず、Ｑ端子から１を出力することを示している。この
ような機能を持つものとしては、例えばセット入力付き
のマスタースレーブ型フリップフロップなどがある。
第３図はこの実施例の動作を説明するためのものである
。同図は第１図においてＮ＝Ｍ＝４とし、（作用）の項
の説明で用いたのと同じく、照合記号列を“ＡＢＣＤ”
、被照合記号列を“ＡＢＣＤ”とした場合について、入
力端子１２０−１〜１２０−４に与えられる入力と、出
力端子１９０−１〜１９０−４からの出力とを示したも
のである。
。同図は第１図においてＮ＝Ｍ＝４とし、（作用）の項
の説明で用いたのと同じく、照合記号列を“ＡＢＣＤ”
、被照合記号列を“ＡＢＣＤ”とした場合について、入
力端子１２０−１〜１２０−４に与えられる入力と、出
力端子１９０−１〜１９０−４からの出力とを示したも
のである。
以下、（作用）の項で行なった説明に対応させながら同
図を説明する。まず、これは同図には示していないが、
初期状態を設定するために始めに全てのレジスタ１３０
の記憶データを０にリセットする必要がある。これは、
新たにレジスタ１３０にリセット端子をもうけるか、あ
るいは全てのレジスタ１３０の記憶データが０になるま
で入力端子１２０−１〜１２０−４にＯを与える続ける
ことなどによって実行される。次に、初期セット端子１
１０に１を与えることによりｆ１１〜ｆ４４のレジスタ
１３０のみが１にセットされる。この状態は第８図に対
応する。続いてＡを入力することに対応して、入力端子
１２０−１のみに１を与え、他の入力端子には０を与え
る。この入力後、出力端子１９０−４には１が、他の出
力端子にはＯが出力される。
図を説明する。まず、これは同図には示していないが、
初期状態を設定するために始めに全てのレジスタ１３０
の記憶データを０にリセットする必要がある。これは、
新たにレジスタ１３０にリセット端子をもうけるか、あ
るいは全てのレジスタ１３０の記憶データが０になるま
で入力端子１２０−１〜１２０−４にＯを与える続ける
ことなどによって実行される。次に、初期セット端子１
１０に１を与えることによりｆ１１〜ｆ４４のレジスタ
１３０のみが１にセットされる。この状態は第８図に対
応する。続いてＡを入力することに対応して、入力端子
１２０−１のみに１を与え、他の入力端子には０を与え
る。この入力後、出力端子１９０−４には１が、他の出
力端子にはＯが出力される。
これは第９図（ａ）におけるＮ列目のセルの状態に対応
する。同様に、Ｂ、 Ｃ，Ｄを入力することに対応した
入力信号を次々に入力端子１２０−１〜１２０−４に入
力することにより、第９図（ｂ）〜（ｄ）におけるＮ列
目のセルの状態に対応した出力が出力端子１９０−１〜
１９０−４より得られる。これらの出力により、（作用
）の項で詳細に説明したように、照合の途中経過として
、照合記号列“ＡＢＣＤ’と被照合記号列“Ａ”、“Ａ
Ｂ”、“ＡＢＣ’”との照合結果が、最終結果として被
照合記号列“ＡＢＣＤ”との照合結果がわかる。
する。同様に、Ｂ、 Ｃ，Ｄを入力することに対応した
入力信号を次々に入力端子１２０−１〜１２０−４に入
力することにより、第９図（ｂ）〜（ｄ）におけるＮ列
目のセルの状態に対応した出力が出力端子１９０−１〜
１９０−４より得られる。これらの出力により、（作用
）の項で詳細に説明したように、照合の途中経過として
、照合記号列“ＡＢＣＤ’と被照合記号列“Ａ”、“Ａ
Ｂ”、“ＡＢＣ’”との照合結果が、最終結果として被
照合記号列“ＡＢＣＤ”との照合結果がわかる。
以上説明した実施例では、入力端子１２０−１〜１２〇
−Ｎには上述のように、被照合記号と照合記号列の各記
号との一致信号を与える必要がある。また出力端子１９
０−１〜１９０−Ｍの出力は、照合結果がすぐ判るよう
にはなっていないため、照合結果を直接示すように変換
する必要がある。以下、これらの機能を実現する周辺装
置の例を第４図、第５図第６図に基づいて説明する。
−Ｎには上述のように、被照合記号と照合記号列の各記
号との一致信号を与える必要がある。また出力端子１９
０−１〜１９０−Ｍの出力は、照合結果がすぐ判るよう
にはなっていないため、照合結果を直接示すように変換
する必要がある。以下、これらの機能を実現する周辺装
置の例を第４図、第５図第６図に基づいて説明する。
第４図は第１図で示した本発明の実施例に入力を与える
入力装置の一例である。同図は各記号が１ビツトで構成
されている場合を示している。まず照合記号列登録端子
４１０−１〜４１ＯＮから、照合記号列をレジスタ４３
０に登録する。被照合記号列は、被照合列入力端子４２
０より１記号ずつ入力され、比較器４４０で照合記号列
の各記号と比較される。比較の結果、両記号が一致して
いれば１、一致していなければ０が一致信号出力端子４
５０−１〜４５０−Ｎから出力される。この４５０−ｊ
の出力を第１図の入力端子１２０−ｊに入力することに
より第１図の説明で述べたような入力を得ることができ
る。なお、ここでは１記号が１ビツトで構成されている
場合を例として示したが、１記号が数ビットで構成され
ている場合も同様の装置を構成することができることは
明らかである。
入力装置の一例である。同図は各記号が１ビツトで構成
されている場合を示している。まず照合記号列登録端子
４１０−１〜４１ＯＮから、照合記号列をレジスタ４３
０に登録する。被照合記号列は、被照合列入力端子４２
０より１記号ずつ入力され、比較器４４０で照合記号列
の各記号と比較される。比較の結果、両記号が一致して
いれば１、一致していなければ０が一致信号出力端子４
５０−１〜４５０−Ｎから出力される。この４５０−ｊ
の出力を第１図の入力端子１２０−ｊに入力することに
より第１図の説明で述べたような入力を得ることができ
る。なお、ここでは１記号が１ビツトで構成されている
場合を例として示したが、１記号が数ビットで構成され
ている場合も同様の装置を構成することができることは
明らかである。
第５図は第１図で示した本発明の実施例の出力を受は取
り、照合結果を出力する出力装置の一例である。同図に
おいて、入力端子５１０−１〜５１０−Ｍには、第１図
の出力端子１９０−１〜１９０−Ｍの対応する番号の出
力が与えられる。この回路は公知のものであるので詳し
い説明は省くが、入力端子５１０−ｉに与えられた入力
データの中に１が複数あれば、その中でｉの値が最も小
さいものだけ残して他の全てをＯとし、対応する番号の
出力端子５８０−ｉから出力する機能を持っている。ま
た、入力データ中に１が一つ以下であれば入力をそのま
ま出力する。これにより、出力端子５８０−ｉの出力が
１であれば、照合結果は距離ｉ−１であるとすぐわかる
ようになる。
り、照合結果を出力する出力装置の一例である。同図に
おいて、入力端子５１０−１〜５１０−Ｍには、第１図
の出力端子１９０−１〜１９０−Ｍの対応する番号の出
力が与えられる。この回路は公知のものであるので詳し
い説明は省くが、入力端子５１０−ｉに与えられた入力
データの中に１が複数あれば、その中でｉの値が最も小
さいものだけ残して他の全てをＯとし、対応する番号の
出力端子５８０−ｉから出力する機能を持っている。ま
た、入力データ中に１が一つ以下であれば入力をそのま
ま出力する。これにより、出力端子５８０−ｉの出力が
１であれば、照合結果は距離ｉ−１であるとすぐわかる
ようになる。
第６図は第１図の記号列照合装置、第４図の入力装置、
第５図の出力装置の接続を示したものである。
第５図の出力装置の接続を示したものである。
同図において、照合記号列登録端子６１０−１〜６１０
−Ｎから照合記号列を登録し、初期セット端子６３０で
初期セットを行なった後、被照合記号列入力端子６２０
から被照合記号を１記号ずつ入力することにより、照合
結果が照合結果出力端子６７０−１〜６７０−Ｍから出
力される。照合結果出力端子６７０−ｉの出力が１であ
れば、照合結果は距離ｉ−１であることを示す。
−Ｎから照合記号列を登録し、初期セット端子６３０で
初期セットを行なった後、被照合記号列入力端子６２０
から被照合記号を１記号ずつ入力することにより、照合
結果が照合結果出力端子６７０−１〜６７０−Ｍから出
力される。照合結果出力端子６７０−ｉの出力が１であ
れば、照合結果は距離ｉ−１であることを示す。
（発明の効果）
以上説明してきたように、本発明による記号列照合装置
は、転送手段とセット手段でセル間が結ばれたセルアレ
イにより構成されている。ここで、セット手段を導入し
たことが本発明の最大の特徴である。このセット手段を
導入することによって、 Ａ、セル間の結合が局所的なものに限られており、遠い
セルとの結合がない。
は、転送手段とセット手段でセル間が結ばれたセルアレ
イにより構成されている。ここで、セット手段を導入し
たことが本発明の最大の特徴である。このセット手段を
導入することによって、 Ａ、セル間の結合が局所的なものに限られており、遠い
セルとの結合がない。
Ｂ、セル間の結合が規則的であり、セルアレイの中でど
こでも同じである。
こでも同じである。
という二つの長所を持ったセルアレイで、任意の抽出距
離に対応できる記号列照合装置を構成することが可能に
なった。
離に対応できる記号列照合装置を構成することが可能に
なった。
この二つの長所は、本発明による記号列照合装置が、単
に照合記号列から任意の距離にある被照合記号列を抽出
できるというだけでなく、以下に示すような効果をも有
することを意味している。
に照合記号列から任意の距離にある被照合記号列を抽出
できるというだけでなく、以下に示すような効果をも有
することを意味している。
１、任意の長さの照合記号列に対応する記号列照合装置
を簡単に構成できる。
を簡単に構成できる。
２、任意の抽出距離に対応する記号列照合装置を簡単に
構成することができる。
構成することができる。
３、照合記号副長の変更や、抽出距離の変更をきわめて
容易に行なうことができる。
容易に行なうことができる。
４、集積回路化する際に設計時間が短くてすみ、しかも
チップ面積が小さくなる。
チップ面積が小さくなる。
１．２の効果は、セルアレイの列数もしくは行数の設定
を変えるだけで、任意の照合記号副長Ｎや抽出距離Ｍに
対応できることを指している。つまり本発明による記号
列照合装置のハードウェアー量はＮとＭの積に比例して
おり、ＮやＭが増えると装置がとたんに複雑化するとい
ったことがない。これは、Ａの結合の局所性とＢの結合
の規則性の二点による大きな効果である。
を変えるだけで、任意の照合記号副長Ｎや抽出距離Ｍに
対応できることを指している。つまり本発明による記号
列照合装置のハードウェアー量はＮとＭの積に比例して
おり、ＮやＭが増えると装置がとたんに複雑化するとい
ったことがない。これは、Ａの結合の局所性とＢの結合
の規則性の二点による大きな効果である。
３の効果は、１，２と似ているが、本発明による記号列
照合装置を任意の台数だけ行方向や列方向に接続するこ
とにより、１台では対応できなかった長い照合記号列や
、遠い抽出距離に容易に対応できるということを指して
いる。これもやはり、Ａ、Ｂの二点による効果である。
照合装置を任意の台数だけ行方向や列方向に接続するこ
とにより、１台では対応できなかった長い照合記号列や
、遠い抽出距離に容易に対応できるということを指して
いる。これもやはり、Ａ、Ｂの二点による効果である。
実際の応用の場面では照合記号副長や抽出距離は固定さ
れず、様々に変化することが考えられるので、このよう
な柔軟性は記号列照合装置に欠くことのできないもので
ある。
れず、様々に変化することが考えられるので、このよう
な柔軟性は記号列照合装置に欠くことのできないもので
ある。
４の効果は、本発明の実用性を高めているものである。
よく知られているように、集積回路化する際、規則的な
構成をしているものの方が、そうでないものより、設計
時間が短くしかもチップ面積も小さくできる。本発明に
よる記号列照合装置はＢの長所により極めて集積回路化
に適したものになっている。また、Ａの長所も配線の引
き回しが短くて済むという点で、集積回路化の際の利点
となる。
構成をしているものの方が、そうでないものより、設計
時間が短くしかもチップ面積も小さくできる。本発明に
よる記号列照合装置はＢの長所により極めて集積回路化
に適したものになっている。また、Ａの長所も配線の引
き回しが短くて済むという点で、集積回路化の際の利点
となる。
以上説明したことから明らかなように、本発明により、
高機能で、柔軟性に富み、かつ実用性の高い記号列照合
装置を提供することができる。
高機能で、柔軟性に富み、かつ実用性の高い記号列照合
装置を提供することができる。
なお、以上の実施例の説明において、レジスタ１３０の
例として、マスタースレーブ型のフリップフロップをあ
げたが、第２図のような入出力関係を満たすものであれ
ばこれはどのようなものでもよく、第１図において第１
、第２の転送手段はそれぞれ、アンドゲート１４０．１
５０で構成されているが、被照合記号と照合記号列の各
記号が一致したか否かによって開閉するスイッチの機能
をもつものであればこれらはどのようなものでもよい。
例として、マスタースレーブ型のフリップフロップをあ
げたが、第２図のような入出力関係を満たすものであれ
ばこれはどのようなものでもよく、第１図において第１
、第２の転送手段はそれぞれ、アンドゲート１４０．１
５０で構成されているが、被照合記号と照合記号列の各
記号が一致したか否かによって開閉するスイッチの機能
をもつものであればこれらはどのようなものでもよい。
また、第３図の波形図では入力が終わった後で対応する
出力が出るようになっているが、入力が終わる前に出力
が出るようになっていてもよい。このように、以上の実
施例は単なる一例であって、何ら本発明を限定するもの
ではない。
出力が出るようになっているが、入力が終わる前に出力
が出るようになっていてもよい。このように、以上の実
施例は単なる一例であって、何ら本発明を限定するもの
ではない。
第１図は本発明の記号列照合装置の実施例を示す構成図
、第２図はレジスタの入出力関係を示す波形図、第３図
は実施例の動作を示す波形図、第４図は実施例の記号列
照合装置に入力を与える入力装置の例を示す構成図、第
５図は実施例の記号列照合装置の出力を変換する出力装
置の例を示す構成図、第６図は、入力装置、記号列照合
装置、出力装置の接続を示す構成図、第７図、第８図、
第９図は本発明の詳細な説明する原理図、第１０図は記
号列間の距離という概念を説明するための説明図、第１
１図、第１２図は従来技術を説明するための原理図であ
る。
、第２図はレジスタの入出力関係を示す波形図、第３図
は実施例の動作を示す波形図、第４図は実施例の記号列
照合装置に入力を与える入力装置の例を示す構成図、第
５図は実施例の記号列照合装置の出力を変換する出力装
置の例を示す構成図、第６図は、入力装置、記号列照合
装置、出力装置の接続を示す構成図、第７図、第８図、
第９図は本発明の詳細な説明する原理図、第１０図は記
号列間の距離という概念を説明するための説明図、第１
１図、第１２図は従来技術を説明するための原理図であ
る。
Claims (2)
- （１）複数の被照合記号列の中から照合記号列と関係す
る被照合記号列を抽出する記号列照合装置において、長
さＮ（Ｎは正整数）の照合記号列に対して、記号列比較
結果を記憶するセルをＭ行（Ｍは正整数）Ｎ＋１列に並
べたセルアレイと、照合記号列のｊ番目（ｊはＮ以下の
任意の正整数）の記号と同じ被照合記号が与えられたと
きのみ、前記セルアレイのｉ行（ｉはＭ以下の任意の正
整数）ｊ列目であるセルｆ＿ｉ＿ｊの記憶データをセル
ｆ＿ｉ＿ｊ＿＋＿１に転送する第１の転送手段と、照合
記号列のｊ番目の記号と違う被照合記号が与えられたと
きのみ、前記セルアレイのｈ行（ｈはＭ未満の任意の正
整数）ｊ列目であるセルｆ＿ｈ＿ｊの記憶データをセル
ｆ＿ｈ＿＋＿１＿ｊ＿＋＿１に転送する第２の転送手段
と、被照合記号が与えられると、与えられた被照合記号
の如何にかかわらず前記セルアレイのｈ行ｋ列目（ｋは
Ｎ＋１以下の任意の正整数）であるセルｆ＿ｈ＿ｋの記
憶データをセルｆ＿ｈ＿＋＿１＿ｋに転送する第３の転
送手段と、前記第１から第３の転送手段によりセルｆ＿
ｉ＿ｋに少なくとも一つ１が転送されてくるとセルｆ＿
ｉ＿ｋの記憶データを１にし、前記第１から第３の転送
手段によりセルｆ＿ｉ＿ｋに１が一つも転送されてこな
ければセルｆ＿ｉ＿ｋの記憶データを０にする入力手段
と、セルｆ＿ｈ＿ｊの記憶データが１になると、前記入
力手段によりセルｆ＿ｈ＿＋＿１＿ｊ＿＋＿１に与えら
れた入力によらず、セルｆ＿ｈ＿＋＿１＿ｊ＿＋＿１の
記憶データを１にセットするセット手段を備えたことを
特徴とする記号列照合装置。 - （２）請求項１に記載の記号列照合装置の制御方式であ
って、少なくとも、前記セルアレイの全てのセルの記憶
データを０にした後、セルｆ＿１＿１の記憶データを１
にセットすることにより初期設定を行なうことと、被照
合記号列を１記号ずつ順に与えることにより記号列照合
を実行することと、前記セルアレイのＮ＋１列目のＭ個
のセルの中から、記憶データが１であり、かついちばん
行番号が小さいセルを探すことにより、照合結果として
照合記号列と被照合記号列との距離を得ることとを含む
ことを特徴とする記号列照合装置の制御方式。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63269746A JP2737173B2 (ja) | 1988-10-25 | 1988-10-25 | 記号列照合装置とその制御方法 |
| EP89119841A EP0366115B1 (en) | 1988-10-25 | 1989-10-25 | String collating system for searching for character string of arbitrary length within a given distance from reference string |
| DE68927625T DE68927625T2 (de) | 1988-10-25 | 1989-10-25 | Folgenkollationierungssystem zum Suchen nach einer Charakterfolge willkürlicher Länge innerhalb eines gegebenen Abstands einer Referenzfolge |
| US07/958,467 US5377349A (en) | 1988-10-25 | 1992-10-08 | String collating system for searching for character string of arbitrary length within a given distance from reference string |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63269746A JP2737173B2 (ja) | 1988-10-25 | 1988-10-25 | 記号列照合装置とその制御方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH02115973A true JPH02115973A (ja) | 1990-04-27 |
| JP2737173B2 JP2737173B2 (ja) | 1998-04-08 |
Family
ID=17476579
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63269746A Expired - Fee Related JP2737173B2 (ja) | 1988-10-25 | 1988-10-25 | 記号列照合装置とその制御方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5377349A (ja) |
| EP (1) | EP0366115B1 (ja) |
| JP (1) | JP2737173B2 (ja) |
| DE (1) | DE68927625T2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0460871A (ja) * | 1990-06-29 | 1992-02-26 | Nec Corp | 記号列照合装置の制御方式 |
| US10844848B2 (en) | 2010-01-21 | 2020-11-24 | The Abell Foundation, Inc. | Ocean thermal energy conversion power plant |
Families Citing this family (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5511159A (en) * | 1992-03-18 | 1996-04-23 | At&T Corp. | Method of identifying parameterized matches in a string |
| US5553272A (en) * | 1994-09-30 | 1996-09-03 | The University Of South Florida | VLSI circuit structure for determining the edit distance between strings |
| US5864683A (en) * | 1994-10-12 | 1999-01-26 | Secure Computing Corporartion | System for providing secure internetwork by connecting type enforcing secure computers to external network for limiting access to data based on user and process access rights |
| US5913024A (en) | 1996-02-09 | 1999-06-15 | Secure Computing Corporation | Secure server utilizing separate protocol stacks |
| US6072942A (en) * | 1996-09-18 | 2000-06-06 | Secure Computing Corporation | System and method of electronic mail filtering using interconnected nodes |
| US6144934A (en) * | 1996-09-18 | 2000-11-07 | Secure Computing Corporation | Binary filter using pattern recognition |
| EP0859332A1 (en) * | 1997-02-12 | 1998-08-19 | STMicroelectronics S.r.l. | Word recognition device and method |
| CN1092362C (zh) * | 1998-02-10 | 2002-10-09 | 北京多思科技工业园股份有限公司 | 阵列错位比较装置及用来实现查询的方法 |
| US7031002B1 (en) | 1998-12-31 | 2006-04-18 | International Business Machines Corporation | System and method for using character set matching to enhance print quality |
| US7039637B2 (en) * | 1998-12-31 | 2006-05-02 | International Business Machines Corporation | System and method for evaluating characters in an inputted search string against a character table bank comprising a predetermined number of columns that correspond to a plurality of pre-determined candidate character sets in order to provide enhanced full text search |
| US7191114B1 (en) | 1999-08-27 | 2007-03-13 | International Business Machines Corporation | System and method for evaluating character sets to determine a best match encoding a message |
| JP2001291060A (ja) * | 2000-04-04 | 2001-10-19 | Toshiba Corp | 単語列照合装置および単語列照合方法 |
| JP4740060B2 (ja) * | 2006-07-31 | 2011-08-03 | 富士通株式会社 | 重複データ検出プログラム、重複データ検出方法および重複データ検出装置 |
| DE102007010259A1 (de) | 2007-03-02 | 2008-09-04 | Volkswagen Ag | Sensor-Auswertevorrichtung und Verfahren zum Auswerten von Sensorsignalen |
| US8872888B2 (en) | 2010-10-01 | 2014-10-28 | Sony Corporation | Content transmission apparatus, content transmission method, content reproduction apparatus, content reproduction method, program and content delivery system |
| US10528556B1 (en) * | 2017-12-31 | 2020-01-07 | Allscripts Software, Llc | Database methodology for searching encrypted data records |
| CN112637600B (zh) * | 2020-12-14 | 2024-04-05 | 绍兴文理学院 | 对数据进行有损或无损压缩的编码、解码的方法或装置 |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3584205A (en) * | 1968-10-14 | 1971-06-08 | Ibm | Binary arithmetic and logic manipulator |
| US4630234A (en) * | 1983-04-11 | 1986-12-16 | Gti Corporation | Linked list search processor |
| JPS6195442A (ja) * | 1984-10-16 | 1986-05-14 | Nec Corp | 記号列照合装置 |
| US4916655A (en) * | 1986-02-14 | 1990-04-10 | Hitachi, Ltd. | Method and apparatus for retrieval of a search string |
| US4823306A (en) * | 1987-08-14 | 1989-04-18 | International Business Machines Corporation | Text search system |
-
1988
- 1988-10-25 JP JP63269746A patent/JP2737173B2/ja not_active Expired - Fee Related
-
1989
- 1989-10-25 EP EP89119841A patent/EP0366115B1/en not_active Expired - Lifetime
- 1989-10-25 DE DE68927625T patent/DE68927625T2/de not_active Expired - Fee Related
-
1992
- 1992-10-08 US US07/958,467 patent/US5377349A/en not_active Expired - Fee Related
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH0460871A (ja) * | 1990-06-29 | 1992-02-26 | Nec Corp | 記号列照合装置の制御方式 |
| US10844848B2 (en) | 2010-01-21 | 2020-11-24 | The Abell Foundation, Inc. | Ocean thermal energy conversion power plant |
| US11371490B2 (en) | 2010-01-21 | 2022-06-28 | The Abell Foundation, Inc. | Ocean thermal energy conversion power plant |
| US11859597B2 (en) | 2010-01-21 | 2024-01-02 | The Abell Foundation, Inc. | Ocean thermal energy conversion power plant |
| US12258947B2 (en) | 2010-01-21 | 2025-03-25 | The Abell Foundation, Inc. | Ocean thermal energy conversion power plant |
Also Published As
| Publication number | Publication date |
|---|---|
| DE68927625D1 (de) | 1997-02-20 |
| EP0366115B1 (en) | 1997-01-08 |
| US5377349A (en) | 1994-12-27 |
| EP0366115A3 (en) | 1991-11-21 |
| JP2737173B2 (ja) | 1998-04-08 |
| DE68927625T2 (de) | 1997-08-14 |
| EP0366115A2 (en) | 1990-05-02 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH02115973A (ja) | 記号列照合装置とその制御方法 | |
| JPS60501921A (ja) | 並列テキスト照合の方法および装置 | |
| CN110019795B (zh) | 敏感词检测模型的训练方法和系统 | |
| JP2715465B2 (ja) | 記号列照合装置 | |
| US3521238A (en) | Multi-processor computing apparatus | |
| JPS60105039A (ja) | 文字列照合方式 | |
| JPH04308B2 (ja) | ||
| JPH0484367A (ja) | 記号列照合装置の制御方式 | |
| CN116662598B (zh) | 基于矢量索引的人物画像信息管理方法及电子设备 | |
| JP2692345B2 (ja) | 記号列照合装置 | |
| JPH03208172A (ja) | 記号列照合装置の制御方式 | |
| JP2773657B2 (ja) | 文字列検索装置 | |
| Alsharif et al. | Remote sensing image retrieval using multilingual texts | |
| JPH0460871A (ja) | 記号列照合装置の制御方式 | |
| JP2839515B2 (ja) | 文字読取システム | |
| JPS60583A (ja) | 単語認識方式 | |
| JPS6128134A (ja) | 記号列照合装置とその制御方式 | |
| RU2065207C1 (ru) | Ассоциативная запоминающая матрица | |
| JPS60225273A (ja) | 単語検索方式 | |
| JPH0529950B2 (ja) | ||
| JPH01245493A (ja) | 連想メモリ装置 | |
| JPS60211539A (ja) | 記号列識別装置及びその制御方式 | |
| JPH01224831A (ja) | 文字列検索装置 | |
| JPS5820075B2 (ja) | パタ−ン認識装置 | |
| JPH05314169A (ja) | 並列データ処理装置および並列形態素抽出方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |