JPS63187334A - 文字列パタ−ンマツチング装置 - Google Patents
文字列パタ−ンマツチング装置Info
- Publication number
- JPS63187334A JPS63187334A JP62018629A JP1862987A JPS63187334A JP S63187334 A JPS63187334 A JP S63187334A JP 62018629 A JP62018629 A JP 62018629A JP 1862987 A JP1862987 A JP 1862987A JP S63187334 A JPS63187334 A JP S63187334A
- Authority
- JP
- Japan
- Prior art keywords
- character
- pattern
- characters
- memory
- character string
- 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
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
（発明の属する技術分野）
本発明は、各文字が固定長のコードで表現されており、
テキストと呼ばれる比較的長い文字列中に、別途与えら
れたパターンと呼ばれる比較的短い文字列が部分列とし
て存在するか否かを判定する″文字列パターンマツチン
グ処理″に関するものである。
テキストと呼ばれる比較的長い文字列中に、別途与えら
れたパターンと呼ばれる比較的短い文字列が部分列とし
て存在するか否かを判定する″文字列パターンマツチン
グ処理″に関するものである。
（従来の技術）
データ処理システムの分野では、文章等の文字列データ
（テキストと呼ばれる）の集まりの中からパターンと呼
ばれる特定の部分文字列を含むもののみを検索したり、
テキストの中に含まれている全てのパターンを抽出する
ことがしばしば必要となる。
（テキストと呼ばれる）の集まりの中からパターンと呼
ばれる特定の部分文字列を含むもののみを検索したり、
テキストの中に含まれている全てのパターンを抽出する
ことがしばしば必要となる。
通常、１つの文字はｎビット（固定長）のコードで表現
されるため、テキストおよびパターンはｎビット単位の
コードの系列となる。
されるため、テキストおよびパターンはｎビット単位の
コードの系列となる。
この様な文字列パターンマツチング処理を指定するコマ
ンドとして、ＳＱＬのＬＩＫＥ述語が知られている。（
Ｉ Ｂ Ｍ Ｐｒｏｇｒａｍ Ｐｒｏｄｕｃｔ Ｓ Ｑ
Ｌ ／ＤＳ 適用業務プログラミング解説書）ＬＩＫ
Ｅ述語では、パターンの文字として、通常の文字以外に
任意の１文字と一致する固定長不確定文字（Ｆｉｘｅｄ
−１ｅｎｇｔｈ ｄｏｎ’ｔ ｃａｒｅ文字（ＦＤＣ）
；Ｈ３１で表す）、および任意桁の任意の文字列と一致
する可変長不確定文字（Ｖａｒｉａｂｌｅ−１ｅｎｇｔ
ｈ ｄｏｎ’ｔｃａｒｅ文字（ＶＤＣ）；”％″″で表
す）を使用することができる。
ンドとして、ＳＱＬのＬＩＫＥ述語が知られている。（
Ｉ Ｂ Ｍ Ｐｒｏｇｒａｍ Ｐｒｏｄｕｃｔ Ｓ Ｑ
Ｌ ／ＤＳ 適用業務プログラミング解説書）ＬＩＫ
Ｅ述語では、パターンの文字として、通常の文字以外に
任意の１文字と一致する固定長不確定文字（Ｆｉｘｅｄ
−１ｅｎｇｔｈ ｄｏｎ’ｔ ｃａｒｅ文字（ＦＤＣ）
；Ｈ３１で表す）、および任意桁の任意の文字列と一致
する可変長不確定文字（Ｖａｒｉａｂｌｅ−１ｅｎｇｔ
ｈ ｄｏｎ’ｔｃａｒｅ文字（ＶＤＣ）；”％″″で表
す）を使用することができる。
第６図は、この様な従来の文字列パターンマツチング機
構の説明図である。
構の説明図である。
第６図において、１はテキストが格納された記憶装置、
２は文字列パターンマツチング装置、３はデータ転送路
、４は検索結果を出力する信号線である。
２は文字列パターンマツチング装置、３はデータ転送路
、４は検索結果を出力する信号線である。
文字列パターンマツチング装置２において、文字列パタ
ーンマツチングを行う方法として、従来より有限オート
マトンを用いる方法が知られている。（Ｌ、Ａ、）ｌｏ
ｌｌａａｒ、 ”Ｈａｒｄｗａｒｅ Ｓｙｓｔｅｍｓ
ｆｏｒ ＴｅｘｔＩｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉ
ｅｖａｌ、”ＡＣＭ ５ＩＧＩＲ６ｔｈ Ｃｏｎｆｅｒ
ｅｎｃｅ １９８３）第７図は、有限オートマトンの状
態遷移を表した説明図であり、５０は有限オートマトン
の状態、６０は状態遷移の方向を表し、テキストの中の
“ＢＩＣ”という３文字のパターンを検出することがで
きる。
ーンマツチングを行う方法として、従来より有限オート
マトンを用いる方法が知られている。（Ｌ、Ａ、）ｌｏ
ｌｌａａｒ、 ”Ｈａｒｄｗａｒｅ Ｓｙｓｔｅｍｓ
ｆｏｒ ＴｅｘｔＩｎｆｏｒｍａｔｉｏｎ Ｒｅｔｒｉ
ｅｖａｌ、”ＡＣＭ ５ＩＧＩＲ６ｔｈ Ｃｏｎｆｅｒ
ｅｎｃｅ １９８３）第７図は、有限オートマトンの状
態遷移を表した説明図であり、５０は有限オートマトン
の状態、６０は状態遷移の方向を表し、テキストの中の
“ＢＩＣ”という３文字のパターンを検出することがで
きる。
以下、この動作を説明する。
有限オートマトンの初期状態は状態（０）であり、入力
文字がＩＩ Ｂ ＩＩであると状態（１）へ遷移する。
文字がＩＩ Ｂ ＩＩであると状態（１）へ遷移する。
同図のＩｔ ＃ ＩＩはその他の文字を表し、状態（０
）における入力文字がＩＩ Ｂ Ｔｌ以外ならば引き続
き状態（０）に留まる。
）における入力文字がＩＩ Ｂ Ｔｌ以外ならば引き続
き状態（０）に留まる。
状態（１）においても同様であり、入力文字が１′″で
あると状態（２）へ、Ｂ″′であると状態（１）へ、そ
れ以外であると状態（０）へ遷移する。
あると状態（２）へ、Ｂ″′であると状態（１）へ、そ
れ以外であると状態（０）へ遷移する。
状態（２）において、入力文字が１１０”であると“Ｂ
ＩＣ”というパターンを検出したことになる。
ＩＣ”というパターンを検出したことになる。
第８図は、テキストの中のＩｇＢ％Ｃ”というパターン
を検出する有限オートマトンの説明図である。
を検出する有限オートマトンの説明図である。
第９図は、テキストの中の”Ｂ Ｃ”というパターン
を検出する有限オートマトンの説明図である。
を検出する有限オートマトンの説明図である。
これら図中の記号の説明は、第７図における説明と同様
である。
である。
以上説明した、従来より知られた文字列パターンマツチ
ング装置では、ＦＤＣ（”−”）、ＶＤＣ（“％″）を
扱うことはできたが、文字の範囲を限定した不確定文字
を扱うことがきなかったため、以下のような欠点があっ
た。
ング装置では、ＦＤＣ（”−”）、ＶＤＣ（“％″）を
扱うことはできたが、文字の範囲を限定した不確定文字
を扱うことがきなかったため、以下のような欠点があっ
た。
例えば、パターンとして“ＢＩＣ”、“８２Ｇ”、“８
３Ｃ”、”８４Ｃ”、”８５Ｃ″、”Ｂ２Ｏ”、”８７
Ｇ”、”８８Ｃ”、”Ｂ９Ｏ”を扱いたい場合に、１１
８Ｃ”とすると、”ＢＡＣ”等も誤検出されるため、パ
ターンとして、陽に”ＢＩＣ”〜”Ｂ９Ｏ”を記述せね
ばならない。この場合の有限オートマドンは第１０図の
ごとくなり、状態数が多くなり、それを表現するテーブ
ルを格納するメモリの容量は大きくなり、テーブルの作
用時間も長くなる。
３Ｃ”、”８４Ｃ”、”８５Ｃ″、”Ｂ２Ｏ”、”８７
Ｇ”、”８８Ｃ”、”Ｂ９Ｏ”を扱いたい場合に、１１
８Ｃ”とすると、”ＢＡＣ”等も誤検出されるため、パ
ターンとして、陽に”ＢＩＣ”〜”Ｂ９Ｏ”を記述せね
ばならない。この場合の有限オートマドンは第１０図の
ごとくなり、状態数が多くなり、それを表現するテーブ
ルを格納するメモリの容量は大きくなり、テーブルの作
用時間も長くなる。
（発明の目的）
本発明の目的は、パターンの一部として、文字の範囲を
限定した、固定長または可変長の不確定文字を含むこと
を可能とする文字列パターンマツチング装置を提供する
ことにある。
限定した、固定長または可変長の不確定文字を含むこと
を可能とする文字列パターンマツチング装置を提供する
ことにある。
（発明の構成）
（発明の特徴と従来の技術の差異）
本発明は、パターンの一部として、文字の範囲を限定さ
れた不確定文字をマツチングする状態において、限定さ
れた範囲の文字が入力されたときのみパターン検出の条
件を維持することを特徴としている。
れた不確定文字をマツチングする状態において、限定さ
れた範囲の文字が入力されたときのみパターン検出の条
件を維持することを特徴としている。
従来の無限定の不確定文字のみを対象とする文字列パタ
ーンマツチング装置では、その文字をマツチングする状
態においては、無条件にパターン検出の条件を維持して
いた点が異なる。
ーンマツチング装置では、その文字をマツチングする状
態においては、無条件にパターン検出の条件を維持して
いた点が異なる。
（実施例）
第１図は、本発明の一実施例を示したブロック図であり
、５は有限オートマトンの状態遷移情報（次の状態番号
）を格納するランダムアクセスメモリ（ＲＡＭ）、６は
検出パターン情報を格納するＲＡＭ、７はＲＡＭ５およ
びＲＡＭ６から読み出すデータのアドレスを保持するア
ドレスレジスタ、８はＲＡ Ｍ ５およびＲＡＭ６共通
のアドレスデコーダ、９，１０はそれぞれＲＡＭ５．Ｒ
ＡＭ６から読み出したデータが格納されるメモリレジス
タ、１１は検索結果を出力する判別回路である。
、５は有限オートマトンの状態遷移情報（次の状態番号
）を格納するランダムアクセスメモリ（ＲＡＭ）、６は
検出パターン情報を格納するＲＡＭ、７はＲＡＭ５およ
びＲＡＭ６から読み出すデータのアドレスを保持するア
ドレスレジスタ、８はＲＡ Ｍ ５およびＲＡＭ６共通
のアドレスデコーダ、９，１０はそれぞれＲＡＭ５．Ｒ
ＡＭ６から読み出したデータが格納されるメモリレジス
タ、１１は検索結果を出力する判別回路である。
ここで、限定された範囲の任意の１文字と一致する固定
長不確定文字（ＲＦＤＣ）をＩＬＥ］ＴＴで、また任意
桁の限定された範囲の任意の文字と一致する可変長不確
定文字（ＲＶＤＣ）を％［コバで表すことにする。［コ
内が限定された範囲の文字を示す。
長不確定文字（ＲＦＤＣ）をＩＬＥ］ＴＴで、また任意
桁の限定された範囲の任意の文字と一致する可変長不確
定文字（ＲＶＤＣ）を％［コバで表すことにする。［コ
内が限定された範囲の文字を示す。
次に、第１図の動作について説明する。
入力文字はデータ転送路３よりアドレスレジスタ７の下
位８ビツトにセットされる。
位８ビツトにセットされる。
アドレスレジスタ７の上位８ビツトには初期値としてｘ
’ｏｏ’がセットされており、アドレスレジスタ７の示
すアドレスに格納されている８ビツトのデータがＲＡＭ
５、ＲＡＭ６からそれぞれ、メモリレジスタ９、メモリ
レジスタ１０に読み出される。
’ｏｏ’がセットされており、アドレスレジスタ７の示
すアドレスに格納されている８ビツトのデータがＲＡＭ
５、ＲＡＭ６からそれぞれ、メモリレジスタ９、メモリ
レジスタ１０に読み出される。
メモリレジスタ９の内容は、次のサイクルでアドレスレ
ジスタ７の上位８ビツトにセットされる。
ジスタ７の上位８ビツトにセットされる。
またメモリレジスタ１０の内容は、判別回路１１で検出
パターンが判定され信号線４に出力される。
パターンが判定され信号線４に出力される。
以」二の動作は、テキスト中の文字列が１文字入力され
る毎に繰返される。
る毎に繰返される。
第２図は、１文字を８ビツトのコードで表現し、最大２
５６状態の有限オートマトンを実現するシステムにおい
て、与えられたパターンが １１Ｂ％［１〜９１Ｃ”である場合に、検索の準備動作
としてＲＡＭ５、ＲＡＭ６にそれぞれ格納するデータの
一例を表したものである。
５６状態の有限オートマトンを実現するシステムにおい
て、与えられたパターンが １１Ｂ％［１〜９１Ｃ”である場合に、検索の準備動作
としてＲＡＭ５、ＲＡＭ６にそれぞれ格納するデータの
一例を表したものである。
第２図において、１２．１３はそわぞれ、ＲＡＭ５、Ｒ
ＡＭ６の１つワードに格納された８ビツトのデータ、１
４はＲＡＭのアドレスの上位８ビツト、１５はＲＡＭの
アドレスの下位８ビツトである。
ＡＭ６の１つワードに格納された８ビツトのデータ、１
４はＲＡＭのアドレスの上位８ビツト、１５はＲＡＭの
アドレスの下位８ビツトである。
なお、論理的にはＲＡＭアドレスの上位８ビツト１４は
有限オートマトンの状態番号、ＲＡＭアドレスの下位８
ビツト１５はテキストから入力された文字のコードに対
応する。また、１６は各文字コードに対応する文字であ
る。
有限オートマトンの状態番号、ＲＡＭアドレスの下位８
ビツト１５はテキストから入力された文字のコードに対
応する。また、１６は各文字コードに対応する文字であ
る。
第２図のデータ１２．１３において、値が明示されてい
ない所はｘ’ｏｏ’が格納されているものとする。デー
タ１２は次に遷移すべき状態番号である。
ない所はｘ’ｏｏ’が格納されているものとする。デー
タ１２は次に遷移すべき状態番号である。
データ１３はパターンが検出されたか否かを示すビット
マツプであり、例えば最下位ビットが１であれば１番目
のパターンが検出されたことを示す。
マツプであり、例えば最下位ビットが１であれば１番目
のパターンが検出されたことを示す。
第３図は、第２図と同様な条件の基で与えられたパター
ンが、”Ｂ−［ｌ〜９１Ｃ”である場合に、検索の準備
動作としてＲＡＭ５、ＲＡＭ６にそれぞれ格納するデー
タの一例を表したものである。
ンが、”Ｂ−［ｌ〜９１Ｃ”である場合に、検索の準備
動作としてＲＡＭ５、ＲＡＭ６にそれぞれ格納するデー
タの一例を表したものである。
第４図は、第２図におけるＲＡＭ５、ＲＡＭ６に格納さ
れた有限オートマトンの状態遷移情報、検出パターン情
報を状態遷移図で表したものである。状態遷移図の見方
は第７図と同様である。
れた有限オートマトンの状態遷移情報、検出パターン情
報を状態遷移図で表したものである。状態遷移図の見方
は第７図と同様である。
＝８−
第４図において、状態（１）は不確定文字をマツチング
する状態であり、限定された範囲の文字ＬＬ Ｉ ＩＩ
〜ＩＩ ９ ＴＴが入力されている限り、パターン検出
の条件を維持しており、次に最後の文字１１ Ｃ＋＋が
入力されたとき、与えられたパターン “Ｂ％［１〜９］Ｃ”を検出したことになる。
する状態であり、限定された範囲の文字ＬＬ Ｉ ＩＩ
〜ＩＩ ９ ＴＴが入力されている限り、パターン検出
の条件を維持しており、次に最後の文字１１ Ｃ＋＋が
入力されたとき、与えられたパターン “Ｂ％［１〜９］Ｃ”を検出したことになる。
ＲＡＭ５、ＲＡＭ６に第２図の内容が格納されていると
、第４図に示した状態遷移図に従った有限オートマトン
の動作をすることになる。
、第４図に示した状態遷移図に従った有限オートマトン
の動作をすることになる。
第５図は、第３図におけるＲＡＭ５、ＲＡＭ６に格納さ
れた有限オートマトンの状態遷移情報、検出パターン情
報を状態遷移図で表したものである。第５図において、
状態（１）、（２）は不確定文字をマツチングする状態
であり、限定された範囲の文字″１”〜ＬＬ ９ ＋＋
が入力されたときのみ、パターン検出の条件を維持して
状態（３）に遷移し、次に最後の文字＃ ＣＩＴが入力
されたとき、与えられたパターン“Ｂ−［１〜９コＣＩ
Ｉを検出したことになる。
れた有限オートマトンの状態遷移情報、検出パターン情
報を状態遷移図で表したものである。第５図において、
状態（１）、（２）は不確定文字をマツチングする状態
であり、限定された範囲の文字″１”〜ＬＬ ９ ＋＋
が入力されたときのみ、パターン検出の条件を維持して
状態（３）に遷移し、次に最後の文字＃ ＣＩＴが入力
されたとき、与えられたパターン“Ｂ−［１〜９コＣＩ
Ｉを検出したことになる。
同様に、第１図のＲＡＭ５、ＲＡＭ６に第３図の内容が
格納されていると、第５図に示した状態遷移図に従った
有限オートマトンの動作をすることになる。
格納されていると、第５図に示した状態遷移図に従った
有限オートマトンの動作をすることになる。
（発明の効果）
第２図と同様な条件の基で、第１０図の有限オートマト
ンの制御情報をＲＡＭ５、ＲＡＭ６に展開すると、第１
１図のごとくなる。
ンの制御情報をＲＡＭ５、ＲＡＭ６に展開すると、第１
１図のごとくなる。
この場合に必要なメモリ容量は１１ワードである。
一方、第３図の場合の必要メモリ容量は４ワードである
。
。
この様に、従来の文字列パターンマツチング装置では、
パターンとして文字の範囲を限定した不確定文字を含む
ことができなかったため、不確定文字の範囲を限定した
処理をやりたい場合に、多量のメモリを使用し、オート
マトンの作成効率も悪い。
パターンとして文字の範囲を限定した不確定文字を含む
ことができなかったため、不確定文字の範囲を限定した
処理をやりたい場合に、多量のメモリを使用し、オート
マトンの作成効率も悪い。
一方、本発明の文字列パターンマツチング装置では、パ
ターンの一部として文字の範囲を限定した不確定文字を
処理する場合に、ホ量のメモリで有限オートマトンを効
率よく作成できる。
ターンの一部として文字の範囲を限定した不確定文字を
処理する場合に、ホ量のメモリで有限オートマトンを効
率よく作成できる。
第１図は本発明の一実施例を示したブロック図、第２図
は１文字を８ビツトのコードで表現し、最大２５６状態
の有限オートマトンを表現するシステムにおいて、与え
られたパターンが “８％［１〜９１Ｇ”である場合のＲＡＭ５、ＲＡＭ６
にそれぞれ格納されたデータの一例の説明図、第３図は
１文字を８ビツトのコードで表現し、最大２５６状態の
オートマトンを実現するシステムにおいて与えられたパ
ターンが”Ｂ ［１〜９１Ｃ”である場合のＲＡＭ５
、ＲＡＭ６にそれぞれ格納されたデータの一例の説明図
、 第４図は第２図におけるＲＡＭ５、ＲＡＭ６に格納され
た有限オートマトンの状態遷移情報、検出パターン情報
を表現した状態遷移図、第５図は第３図におけるＲＡＭ
５、ＲＡＭ６に格納された有限オートマトンの状態遷移
情報、検出パターン情報を表現した状態遷移図、第６図
は従来の文字列パターンマツチング機構の説明図、 第７図は従来の有限オートマトンの状態遷移を＝１１− 表した説明図、 第８図はテキストの中のｔｔＢ％ＣＩｔというパターン
を検出する有限オートマトンの説明図、第９図はテキス
トの中のＩｔ Ｂ Ｃ１１というパターンを検出する
有限オートマトンの説明図、第１０図は、テキストの中
（ｉ’ｌ”Ｂ Ｉ Ｃ”、 ”８２ Ｇ”。 ・・・・・・、”８９Ｃ”のいずれかのパターンを検出
する有限オートマトンの説明図、 第１１図は従来の文字列パターンマツチング装置におい
て、与えられたパターンが”ＢＩＣ”。 “Ｂ２Ｏ”、・・・・・・、”Ｂ１０”である場合のＲ
ＡＭ５、ＲＡＭ６にそれぞれ格納されたデータの一例の
説明図である。 １ ・・・テキストが格納された記憶装置、２・・・文
字列パターンマツチング装置、３ ・・・データ転送路
、 ４ ・・・検索結果を出力する信号線、５・・・有限オ
ートマトンの状態遷移情報を格納するＲＡＭ、 ６ ・・・検出パターン情報を格納するＲＡＭ、＝１２
− ７・・・ＲＡＭ５およびＲＡＭ６のアドレスレジスタ、 ８・・・ＲＡＭ５およびＲＡＭ６共通のアドレスデコー
ダ、 ９．１０・・・ＲＡＭ５．ＲＡＭ６のメモリレジスタ、 １１・・・検索結果を出力する判別回路、１２、１３・
・・ＲＡＭ５．ＲＡＭ６の１つワードに格納された８ビ
ツトのデータ、 １４・・・ＲＡＭのアドレスの上位８ビツト、１５・・
・ＲＡＭのアドレスの下位８ビツト、１６・・・文字コ
ードに対応する文字。 ５０・・・有限オートマトンの状態、 ６０・・・状態遷移の方向。 特許出願人 日本電信電話株式会社 第２ ’ｌ’ ＃２”３’ ”４’ 写 ’６’ ”７
’ ”８’ ”グ ”Ｂ”Ｃ’ ン禮 ６第３ ”ｌ’ ”２”３’ ”４’ ”５’ ”６’
７° ”８” ”９” ”Ｂ”σン備 ６第１０図 第８図 第９図 第１１
は１文字を８ビツトのコードで表現し、最大２５６状態
の有限オートマトンを表現するシステムにおいて、与え
られたパターンが “８％［１〜９１Ｇ”である場合のＲＡＭ５、ＲＡＭ６
にそれぞれ格納されたデータの一例の説明図、第３図は
１文字を８ビツトのコードで表現し、最大２５６状態の
オートマトンを実現するシステムにおいて与えられたパ
ターンが”Ｂ ［１〜９１Ｃ”である場合のＲＡＭ５
、ＲＡＭ６にそれぞれ格納されたデータの一例の説明図
、 第４図は第２図におけるＲＡＭ５、ＲＡＭ６に格納され
た有限オートマトンの状態遷移情報、検出パターン情報
を表現した状態遷移図、第５図は第３図におけるＲＡＭ
５、ＲＡＭ６に格納された有限オートマトンの状態遷移
情報、検出パターン情報を表現した状態遷移図、第６図
は従来の文字列パターンマツチング機構の説明図、 第７図は従来の有限オートマトンの状態遷移を＝１１− 表した説明図、 第８図はテキストの中のｔｔＢ％ＣＩｔというパターン
を検出する有限オートマトンの説明図、第９図はテキス
トの中のＩｔ Ｂ Ｃ１１というパターンを検出する
有限オートマトンの説明図、第１０図は、テキストの中
（ｉ’ｌ”Ｂ Ｉ Ｃ”、 ”８２ Ｇ”。 ・・・・・・、”８９Ｃ”のいずれかのパターンを検出
する有限オートマトンの説明図、 第１１図は従来の文字列パターンマツチング装置におい
て、与えられたパターンが”ＢＩＣ”。 “Ｂ２Ｏ”、・・・・・・、”Ｂ１０”である場合のＲ
ＡＭ５、ＲＡＭ６にそれぞれ格納されたデータの一例の
説明図である。 １ ・・・テキストが格納された記憶装置、２・・・文
字列パターンマツチング装置、３ ・・・データ転送路
、 ４ ・・・検索結果を出力する信号線、５・・・有限オ
ートマトンの状態遷移情報を格納するＲＡＭ、 ６ ・・・検出パターン情報を格納するＲＡＭ、＝１２
− ７・・・ＲＡＭ５およびＲＡＭ６のアドレスレジスタ、 ８・・・ＲＡＭ５およびＲＡＭ６共通のアドレスデコー
ダ、 ９．１０・・・ＲＡＭ５．ＲＡＭ６のメモリレジスタ、 １１・・・検索結果を出力する判別回路、１２、１３・
・・ＲＡＭ５．ＲＡＭ６の１つワードに格納された８ビ
ツトのデータ、 １４・・・ＲＡＭのアドレスの上位８ビツト、１５・・
・ＲＡＭのアドレスの下位８ビツト、１６・・・文字コ
ードに対応する文字。 ５０・・・有限オートマトンの状態、 ６０・・・状態遷移の方向。 特許出願人 日本電信電話株式会社 第２ ’ｌ’ ＃２”３’ ”４’ 写 ’６’ ”７
’ ”８’ ”グ ”Ｂ”Ｃ’ ン禮 ６第３ ”ｌ’ ”２”３’ ”４’ ”５’ ”６’
７° ”８” ”９” ”Ｂ”σン備 ６第１０図 第８図 第９図 第１１
Claims (2)
- （１）各文字が固定長のコードで表現されており、テキ
ストと呼ばれる比較的長い文字列中に、別途与えられた
パターンと呼ばれる比較的短い文字列が部分列として存
在するか否かを判定する文字列パターンマッチング処理
において、パターンの一部として文字の範囲を限定した
、固定長または可変長の不確定文字を含むことを特徴と
する文字列パターンマッチング装置。 - （２）状態番号とコード番号との組に対応した次の状態
番号および検出パターン番号を格納するためのメモリと
、そのメモリへのデータ書き込みおよび読み出し機構と
を備え、与えられたパターンに応じて予めそのメモリへ
次の状態番号および検出パターン番号を格納しておき、
テキストが入力された後は、テキストの各文字毎にその
メモリを索引することにより実行する文字列パターンマ
ッチング処理において、文字の範囲を限定した不確定文
字をマッチングする状態で、入力された文字が限定され
た範囲の対象文字であるときのみその状態に留まること
を特徴とする特許請求の範囲第（１）項記載の文字列パ
ターンマッチング装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62018629A JPH07120356B2 (ja) | 1987-01-30 | 1987-01-30 | 文字列パタ−ンマツチング装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP62018629A JPH07120356B2 (ja) | 1987-01-30 | 1987-01-30 | 文字列パタ−ンマツチング装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63187334A true JPS63187334A (ja) | 1988-08-02 |
| JPH07120356B2 JPH07120356B2 (ja) | 1995-12-20 |
Family
ID=11976909
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP62018629A Expired - Fee Related JPH07120356B2 (ja) | 1987-01-30 | 1987-01-30 | 文字列パタ−ンマツチング装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH07120356B2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH04348469A (ja) * | 1990-07-23 | 1992-12-03 | Hitachi Ltd | 文字列検索装置およびその方法 |
| WO1998011509A1 (fr) * | 1996-09-13 | 1998-03-19 | Hitachi, Ltd. | Procede de traitement des informations de bibliotheque |
| CN112395853A (zh) * | 2020-11-04 | 2021-02-23 | 苏宁云计算有限公司 | 文本内容检测方式确定方法、装置、设备和存储介质 |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS58200343A (ja) * | 1982-05-18 | 1983-11-21 | Nec Corp | 文字列パタ−ン・マツチング装置 |
-
1987
- 1987-01-30 JP JP62018629A patent/JPH07120356B2/ja not_active Expired - Fee Related
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS58200343A (ja) * | 1982-05-18 | 1983-11-21 | Nec Corp | 文字列パタ−ン・マツチング装置 |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH04348469A (ja) * | 1990-07-23 | 1992-12-03 | Hitachi Ltd | 文字列検索装置およびその方法 |
| WO1998011509A1 (fr) * | 1996-09-13 | 1998-03-19 | Hitachi, Ltd. | Procede de traitement des informations de bibliotheque |
| CN112395853A (zh) * | 2020-11-04 | 2021-02-23 | 苏宁云计算有限公司 | 文本内容检测方式确定方法、装置、设备和存储介质 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH07120356B2 (ja) | 1995-12-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4053871A (en) | Method and system for the iterative and simultaneous comparison of data with a group of reference data items | |
| US4254476A (en) | Associative processor | |
| US4327407A (en) | Data driven processor | |
| JPH024026B2 (ja) | ||
| JPS63187334A (ja) | 文字列パタ−ンマツチング装置 | |
| JPH0315221B2 (ja) | ||
| JP3141428B2 (ja) | 数値検索装置およびその方法 | |
| JPS62179083A (ja) | 文字列照合方法 | |
| US3316538A (en) | Circuit arrangement for processing parts of words in electronic computers | |
| EP0468402A2 (en) | Character string retrieving system and method | |
| JPH03131969A (ja) | 記号列検索方法および検索装置 | |
| JP2931934B2 (ja) | 数値検索装置 | |
| JPH0664586B2 (ja) | 文字列照合方法 | |
| JPH06139278A (ja) | 文字コード変換機能を備えた文字列検索装置 | |
| JP2772124B2 (ja) | 辞書検索方式 | |
| SU926717A1 (ru) | Ассоциативное запоминающее устройство | |
| JPH04223566A (ja) | 数値検索装置および数値検索方法 | |
| JPS63286930A (ja) | 文字列検索装置 | |
| JPH03147036A (ja) | 可変長データ処理装置 | |
| JPH0193820A (ja) | 検索装置 | |
| JPS6373422A (ja) | 情報検索装置 | |
| JPS62278689A (ja) | 単語検索方式 | |
| JPH02109169A (ja) | 検索処理装置 | |
| JPS58117024A (ja) | カナ文字入力処理方式 | |
| JPS62194535A (ja) | 記号処理装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |