JPH01234930A - 文字列検索方法および装置 - Google Patents
文字列検索方法および装置Info
- Publication number
- JPH01234930A JPH01234930A JP63060372A JP6037288A JPH01234930A JP H01234930 A JPH01234930 A JP H01234930A JP 63060372 A JP63060372 A JP 63060372A JP 6037288 A JP6037288 A JP 6037288A JP H01234930 A JPH01234930 A JP H01234930A
- Authority
- JP
- Japan
- Prior art keywords
- code
- character string
- conversion
- character
- string search
- 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
- 238000000034 method Methods 0.000 title claims description 20
- 238000006243 chemical reaction Methods 0.000 claims description 42
- 238000010586 diagram Methods 0.000 description 5
- 230000001413 cellular effect Effects 0.000 description 4
- 230000000694 effects Effects 0.000 description 3
- 229940127030 Foster Drugs 0.000 description 1
- 235000006732 Torreya nucifera Nutrition 0.000 description 1
- 244000111306 Torreya nucifera Species 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 238000007796 conventional method Methods 0.000 description 1
- 230000001902 propagating effect Effects 0.000 description 1
- 230000007704 transition Effects 0.000 description 1
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は、データベースの検索方法に係り、特に、長大
な文字列の中から指定された文字列を検索するのに好適
な文字列検索方法および装置に関する。
な文字列の中から指定された文字列を検索するのに好適
な文字列検索方法および装置に関する。
オフィス・オートメーション化に伴って、文書情報のデ
ータベース化が急速に進んでおり、そのデータベースの
規模も大規模化してきている。このような状況の中で、
文書情報検索の高速化が強く望まれている。なかでも、
テキストと呼ばれる文字列の中から、パターンまたはキ
ーワードと呼ばれる指定された特定の文字列を探し出す
文字列検索処理は、使用頻度も高く、処理負荷も極めて
大きいので、高速化のニーズが特に望まれている。
ータベース化が急速に進んでおり、そのデータベースの
規模も大規模化してきている。このような状況の中で、
文書情報検索の高速化が強く望まれている。なかでも、
テキストと呼ばれる文字列の中から、パターンまたはキ
ーワードと呼ばれる指定された特定の文字列を探し出す
文字列検索処理は、使用頻度も高く、処理負荷も極めて
大きいので、高速化のニーズが特に望まれている。
このようなニーズにこたえるために、文字列検索をハー
ドウェア化して処理する方法がいくつか提案されている
。例えば、［ハードウェア・システムズ・フォア・テキ
スト・インフオメイション・リトリーバルＪ （Ｈｏｌ
ｌａａｒ、 Ｌ、Ａ、 ： ＨａｒｄｗａｒｅＳｙｓｔ
ｅｍｓ ｆｏｒ Ｔｅｘｔ Ｉｎｆｏｒｍａｔｉｏｎ
Ｒｅｔｒｉｅｖａｌ、ＡＣＭＳＩＧＩＲＣｏｎｆ、 Ｊ
ｕｎｅ １９８３）や「ザ・デザイン・オブ・スペシャ
ルバーボス・ブイエルニスアイ・チップスＪ （Ｆｏｓ
ｔｅｒ、Ｍ、Ｊ、ａｎｄ Ｋｕｎｇ、 Ｈ，Ｔ、 ：
Ｔｈｅ Ｄｅｓｉ、ｇｎｏｆ ５ｐｅｃｉａｌ−Ｐｕｒ
ｐｏｓｅ ＶＬＳＩ Ｃｈｉｐｓ、Ｃｏｍｐｕｔｅｒ、
Ｖｏｌ。
ドウェア化して処理する方法がいくつか提案されている
。例えば、［ハードウェア・システムズ・フォア・テキ
スト・インフオメイション・リトリーバルＪ （Ｈｏｌ
ｌａａｒ、 Ｌ、Ａ、 ： ＨａｒｄｗａｒｅＳｙｓｔ
ｅｍｓ ｆｏｒ Ｔｅｘｔ Ｉｎｆｏｒｍａｔｉｏｎ
Ｒｅｔｒｉｅｖａｌ、ＡＣＭＳＩＧＩＲＣｏｎｆ、 Ｊ
ｕｎｅ １９８３）や「ザ・デザイン・オブ・スペシャ
ルバーボス・ブイエルニスアイ・チップスＪ （Ｆｏｓ
ｔｅｒ、Ｍ、Ｊ、ａｎｄ Ｋｕｎｇ、 Ｈ，Ｔ、 ：
Ｔｈｅ Ｄｅｓｉ、ｇｎｏｆ ５ｐｅｃｉａｌ−Ｐｕｒ
ｐｏｓｅ ＶＬＳＩ Ｃｈｉｐｓ、Ｃｏｍｐｕｔｅｒ、
Ｖｏｌ。
１３、Ｎα１．１９８０）ではセルラ・アレイ法による
文字列検索方法について論じられている。これは、第４
図に示すように、テキストの入力文字コード１０３を文
字列検索装置１０１に入れ、そのセル内でパターンレジ
スタ１１０のパターンの１文字とテキストの入力文字１
文字とを比較器１１１により比較し、その結果に応じて
制御情報を発生させ、それをとなりのセルに伝達しなが
ら文字列検索を実行する方法である。これらの方法はい
ずれも、テキストの入力文字をそのまま文字列検索装置
に入力する方法となっていた。
文字列検索方法について論じられている。これは、第４
図に示すように、テキストの入力文字コード１０３を文
字列検索装置１０１に入れ、そのセル内でパターンレジ
スタ１１０のパターンの１文字とテキストの入力文字１
文字とを比較器１１１により比較し、その結果に応じて
制御情報を発生させ、それをとなりのセルに伝達しなが
ら文字列検索を実行する方法である。これらの方法はい
ずれも、テキストの入力文字をそのまま文字列検索装置
に入力する方法となっていた。
上記のように従来技術はテキストの入力文字をそのまま
文字列検索装置に入力させていたので、文字列検索装置
のハードウェア量が大きくなるという問題があった０例
えば第４図の場合、文字列検索装置１０１内には、パタ
ーン１文字を格納するための８ビツトのパターンレジス
タ１１０とパターン１文字とテキストの入力文字とを比
較するための８ビツトの比較器１１０がパターン要分だ
け必要であった。
文字列検索装置に入力させていたので、文字列検索装置
のハードウェア量が大きくなるという問題があった０例
えば第４図の場合、文字列検索装置１０１内には、パタ
ーン１文字を格納するための８ビツトのパターンレジス
タ１１０とパターン１文字とテキストの入力文字とを比
較するための８ビツトの比較器１１０がパターン要分だ
け必要であった。
本発明の目的は、ハードウェア量を削減することが可能
な文字列検索方法および装置を提供することにある。
な文字列検索方法および装置を提供することにある。
上記目的を達成するために１本発明は、入力文字コード
を入力文字コード長より短かいコードに変換するコード
変換機構を設けることに特徴がある。
を入力文字コード長より短かいコードに変換するコード
変換機構を設けることに特徴がある。
本発明によれば、コード変換機構は入力文字を入力文字
コード長より短かいコードに変換するので、その変換コ
ードを文字列検索装置の入力とすれば１文字列検索装置
内のレジスタや比較器は変換コード長のレジスタや比較
器で済ませることができ、ハードウェア量を削減できる
。
コード長より短かいコードに変換するので、その変換コ
ードを文字列検索装置の入力とすれば１文字列検索装置
内のレジスタや比較器は変換コード長のレジスタや比較
器で済ませることができ、ハードウェア量を削減できる
。
以下１本発明の実施例を図面により説明する。
まず１本発明の第一の実施例を第１図と第２図により説
明する。第１図は本発明の全体構成図である。５はテキ
ストを記憶している記憶装置、３はテキストの入力文字
格納する入力文字コードレジスタ、２は入力文字コード
を変換コードに変換するコード変換機構、４は変換され
たコードを格納する変換コードレジスタ、１は文字列検
索装置である。本発明では、テキストが１文字ずつ記憶
装置５から入力文字コードレジスタ３を経てコード変換
機構２に入力され、入力文字コード長より短かい変換コ
ードに変換され、変換コードレジスタ４を経て文字列検
索装置１に入力され１文字列検索が実行される。したが
って、文字列検索装置１内のレジスタや比較器は変換コ
ード長に対応したもので十分である。第２図は第１図の
文字列検索装置の一例の構成を示す。第２図により、例
を用いて詳しく説明する。パターンの例として「ＡＢＣ
Ｊを考える。この場合、文字列検索装置１は、入力コー
ドがｒＡＪかｒＢＪかｒＣＪかその他の文字かを判別で
きれば、検索の機能を果たすのに十分である。すなわち
、文字列検索装置への入力コードとして４種類の変換コ
ードを用意すれば良い、これは２ビツトの情報で可能で
ある０本実施例ではコード変換機構２の実現形態として
コード変換テーブル２０を用い、ｒＡＪを表現する８ビ
ツトのコードＸＩＣ１マに２ビツトのコードｒＢＪマ０
１マを、「Ｂ」を表現するコードＸＩＣ２マにＢマ１０
マを、ｒＣＪを表現するコードＸＩＣ１マにＢマ１１マ
を対応させ、その他の文字を表現する８ビツトのコード
に対しては全てに２ビツトのコードＢマＯｏマを対応さ
せる。
明する。第１図は本発明の全体構成図である。５はテキ
ストを記憶している記憶装置、３はテキストの入力文字
格納する入力文字コードレジスタ、２は入力文字コード
を変換コードに変換するコード変換機構、４は変換され
たコードを格納する変換コードレジスタ、１は文字列検
索装置である。本発明では、テキストが１文字ずつ記憶
装置５から入力文字コードレジスタ３を経てコード変換
機構２に入力され、入力文字コード長より短かい変換コ
ードに変換され、変換コードレジスタ４を経て文字列検
索装置１に入力され１文字列検索が実行される。したが
って、文字列検索装置１内のレジスタや比較器は変換コ
ード長に対応したもので十分である。第２図は第１図の
文字列検索装置の一例の構成を示す。第２図により、例
を用いて詳しく説明する。パターンの例として「ＡＢＣ
Ｊを考える。この場合、文字列検索装置１は、入力コー
ドがｒＡＪかｒＢＪかｒＣＪかその他の文字かを判別で
きれば、検索の機能を果たすのに十分である。すなわち
、文字列検索装置への入力コードとして４種類の変換コ
ードを用意すれば良い、これは２ビツトの情報で可能で
ある０本実施例ではコード変換機構２の実現形態として
コード変換テーブル２０を用い、ｒＡＪを表現する８ビ
ツトのコードＸＩＣ１マに２ビツトのコードｒＢＪマ０
１マを、「Ｂ」を表現するコードＸＩＣ２マにＢマ１０
マを、ｒＣＪを表現するコードＸＩＣ１マにＢマ１１マ
を対応させ、その他の文字を表現する８ビツトのコード
に対しては全てに２ビツトのコードＢマＯｏマを対応さ
せる。
まず２ビツトの変換コードに変換されたパターンを予め
文字列検索装置１内のレジスタ１０にセットする。テキ
ストは１文字ずつ８ビツトのコードとして入力文字コー
ドレジスタ３に入力される。
文字列検索装置１内のレジスタ１０にセットする。テキ
ストは１文字ずつ８ビツトのコードとして入力文字コー
ドレジスタ３に入力される。
この入力文字コードをアドレスとしてコード変換テーブ
ル２によりコード変換し、変換コードを２ビツトの変換
コードレジスタ４に入力する。さらに、この変換コード
を文字列検索装置１の入力コードとして入力する。文字
列検索装置１内の各セルでは、入力された変換コードと
パターンレジスタ１０のパターンとを比較器１１で比較
し、その結果に応じて制御情報を発生させ、シフトレジ
スタ等の伝達機構１２により、隣りのセルに伝達しなが
ら文字列検索を実行する。したがって１文字列検索装置
１内のパターンレジスタ１０や比較器１１は２ビツトの
もので十分である。これにより。
ル２によりコード変換し、変換コードを２ビツトの変換
コードレジスタ４に入力する。さらに、この変換コード
を文字列検索装置１の入力コードとして入力する。文字
列検索装置１内の各セルでは、入力された変換コードと
パターンレジスタ１０のパターンとを比較器１１で比較
し、その結果に応じて制御情報を発生させ、シフトレジ
スタ等の伝達機構１２により、隣りのセルに伝達しなが
ら文字列検索を実行する。したがって１文字列検索装置
１内のパターンレジスタ１０や比較器１１は２ビツトの
もので十分である。これにより。
文字列検索装置１内のハードウェア量を大幅に削減する
ことができる。
ことができる。
次に本発明の第二の実施例を用いて、変換コード長が２
ビツトでも４文字以上のパターン長のパターンの検索が
可能であることを示す。パターンの例としてパターン長
が６であるパターンｒＡＢＣＤＥＦＪを考える。この場
合の本発明の構成図を第３図に示す。ここでは、パター
ンの３文字毎にコード変換テーブル２０を用いている。
ビツトでも４文字以上のパターン長のパターンの検索が
可能であることを示す。パターンの例としてパターン長
が６であるパターンｒＡＢＣＤＥＦＪを考える。この場
合の本発明の構成図を第３図に示す。ここでは、パター
ンの３文字毎にコード変換テーブル２０を用いている。
コード変換テーブル２０−１はパターンの前半の３文字
１’ＡＪ（ＸＴＣＩり、ｒＢＪ（ＸＴＣ２り、ｒＣＪ（
ＸＴＣ３？）をそれぞれ２ビツトのコードＢマ０１マ、
Ｂマ１０マ。
１’ＡＪ（ＸＴＣＩり、ｒＢＪ（ＸＴＣ２り、ｒＣＪ（
ＸＴＣ３？）をそれぞれ２ビツトのコードＢマ０１マ、
Ｂマ１０マ。
Ｂマ１１マに変換し、その他の文字はＢマＯＯマに変換
する。第２のコード変換テーブル２０−２はパターンノ
後半の３文字ｒＤＪ （ＸＩＣ４Ｔ）、ｒＥＪ（ＸＴＣ
５Ｄ 、ｒＦＪ （ＸＩＣ６？）をそれぞれ２ビツト
のコードＢマ０１マ、Ｂマ１６マ、Ｂマ１１マに変換し
、その他の文字はＢマＯＯマに変換する。そして、この
２つの変換コードがそれぞれパターンの前半のｒＡＢｃ
Ｊ文字列検索を実行する文字列検索装置１−１と後半の
ｒＤＥＦＪの文字列検索を実行する文字列検索装置１−
２に入力される。
する。第２のコード変換テーブル２０−２はパターンノ
後半の３文字ｒＤＪ （ＸＩＣ４Ｔ）、ｒＥＪ（ＸＴＣ
５Ｄ 、ｒＦＪ （ＸＩＣ６？）をそれぞれ２ビツト
のコードＢマ０１マ、Ｂマ１６マ、Ｂマ１１マに変換し
、その他の文字はＢマＯＯマに変換する。そして、この
２つの変換コードがそれぞれパターンの前半のｒＡＢｃ
Ｊ文字列検索を実行する文字列検索装置１−１と後半の
ｒＤＥＦＪの文字列検索を実行する文字列検索装置１−
２に入力される。
このようにして、変換コード長が２ビツトであっても、
４文字以上のパターン長のパターンを検索すことが複数
のコード変換テーブルを用いることにより可能になる。
４文字以上のパターン長のパターンを検索すことが複数
のコード変換テーブルを用いることにより可能になる。
コード変換テーブル２０−１と２０−２は１つのテーブ
ルとして表現し、１つのＲＡＭを用いて実行してもよい
、このようにして、変換コード長に応じて複数のコード
変換テーブルを用いることにより、パターン長が長くて
も。
ルとして表現し、１つのＲＡＭを用いて実行してもよい
、このようにして、変換コード長に応じて複数のコード
変換テーブルを用いることにより、パターン長が長くて
も。
パターン数が多くても、文字列検索が実行できる。
本発明の実施例では、文字列検索装置としてセルラ・ア
レイ法を用いた場合について説明したが、本発明はセル
ラ・アレイ法に限定せず、その他の方式でも有効である
。例えば、有限オートマトンを利用した方法でも１本発
明を用いてコード長の短かい変換コードに変換すれば、
利用する状態遷移テーブルの大きさを少なくできる効果
がある。
レイ法を用いた場合について説明したが、本発明はセル
ラ・アレイ法に限定せず、その他の方式でも有効である
。例えば、有限オートマトンを利用した方法でも１本発
明を用いてコード長の短かい変換コードに変換すれば、
利用する状態遷移テーブルの大きさを少なくできる効果
がある。
セルラ・アレイ法を用いた文字列検索装置内のハードウ
ェア量はレジスタや比較器の幅と個数によってほぼ決定
される。従来方式では、８ビット幅のレジスタや比較器
を必要としたので、極めて大きなハードウェア量となっ
ていた。本発明では、変換コード長をにビットとすると
、ｋピット幅のレジスタや比較器で済むので、ハードウ
ェア量をに／８化することができる。本発明では、コー
ド変換を実現するコード変換テーブルを必要とするが、
これはＲＡＭで実現でき、レジスタや比較器などのハー
ドウェアに比べて極めて安価であるので経済性において
も効果がある。
ェア量はレジスタや比較器の幅と個数によってほぼ決定
される。従来方式では、８ビット幅のレジスタや比較器
を必要としたので、極めて大きなハードウェア量となっ
ていた。本発明では、変換コード長をにビットとすると
、ｋピット幅のレジスタや比較器で済むので、ハードウ
ェア量をに／８化することができる。本発明では、コー
ド変換を実現するコード変換テーブルを必要とするが、
これはＲＡＭで実現でき、レジスタや比較器などのハー
ドウェアに比べて極めて安価であるので経済性において
も効果がある。
第１図は本発明の全体構成図、第２図と第３図は本発明
のそれぞれの実施例の説明図、第４図は従来技術の説明
図である。 １・・・文字列検索装置、２・・・コード変換機構、３
・・・入力文字コードレジスタ、４・・・変換コードレ
ジス茅 ＩＴ２］ ｔｌ−化ベーム ＋）−ｙべμ
のそれぞれの実施例の説明図、第４図は従来技術の説明
図である。 １・・・文字列検索装置、２・・・コード変換機構、３
・・・入力文字コードレジスタ、４・・・変換コードレ
ジス茅 ＩＴ２］ ｔｌ−化ベーム ＋）−ｙべμ
Claims (1)
- 【特許請求の範囲】 １、テキストと呼ばれる文字列の中からパターンと呼ば
れる特定の文字列を探し出す文字列検索方法において、
テキストの入力文字コードをそのコード長より短かいコ
ード長のコードに変換し、該変換コード列に対して文字
列検索を行うことを特徴とする文字列検索方法。 ２、パターンを形成している文字の種類とその他の文字
だけを判別できるようにすることにより変換コードの種
類を減らし変換コード長を短かくすることを特徴とする
請求項１項記載の文字列検索方法。 ３、多種のコードから成つている検索すべき原データを
、少なくも検索するのに必要な種類のコードだけからな
るデータに変換することを特徴とする請求項１項記載の
文字列検索方法。 ４、変換されるデータのコード長は、変換される前の原
データのコード長より短かくすることを特徴とする請求
項１項記載の文字列検索方法。 ５、テキストと呼ばれる文字列の中からパターンと呼ば
れる特定の文字列を探し出す文字列検索方法において、
テキストの入力文字コードをそのコード長より短かいコ
ード長のコードに変換する変換手段を設け、該変換コー
ド列に対して文字列検索を行うことを特徴とする文字列
検索装置。 ６、パターンを形成している文字の種類とその他の文字
だけを判別できるようにすることにより変換コードの種
類を減らし変換コード長を短かくすることを特徴とする
請求項５項記載の文字列検索装置。 ７、上記変換手段は、多種のコードから成つている検索
すべき原データを、少なくも検索するのに必要な種類の
コードだけからなるデータに変換する手段からなること
を特徴とする請求項５項記載の文字列検索装置。
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63060372A JP2713962B2 (ja) | 1988-03-16 | 1988-03-16 | 文字列検索方法および装置 |
| DE3817139A DE3817139A1 (de) | 1987-05-20 | 1988-05-19 | Verfahren und vorrichtung zum suchen einer zeichenfolge |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63060372A JP2713962B2 (ja) | 1988-03-16 | 1988-03-16 | 文字列検索方法および装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH01234930A true JPH01234930A (ja) | 1989-09-20 |
| JP2713962B2 JP2713962B2 (ja) | 1998-02-16 |
Family
ID=13140238
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63060372A Expired - Fee Related JP2713962B2 (ja) | 1987-05-20 | 1988-03-16 | 文字列検索方法および装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2713962B2 (ja) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH04348469A (ja) * | 1990-07-23 | 1992-12-03 | Hitachi Ltd | 文字列検索装置およびその方法 |
| JP2006505043A (ja) * | 2002-10-29 | 2006-02-09 | ロッキード・マーチン・コーポレイション | ハードウェアパーサアクセラレータ |
-
1988
- 1988-03-16 JP JP63060372A patent/JP2713962B2/ja not_active Expired - Fee Related
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH04348469A (ja) * | 1990-07-23 | 1992-12-03 | Hitachi Ltd | 文字列検索装置およびその方法 |
| JP2006505043A (ja) * | 2002-10-29 | 2006-02-09 | ロッキード・マーチン・コーポレイション | ハードウェアパーサアクセラレータ |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2713962B2 (ja) | 1998-02-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4959785A (en) | Character processing system with spelling check function that utilizes condensed word storage and indexed retrieval | |
| US5621908A (en) | Parallel sorting system to reduce the amount of communication between processing devices | |
| US4514826A (en) | Relational algebra engine | |
| EP0688105B1 (en) | A bit string compressor with boolean operation processing capability | |
| JPS60134945A (ja) | データベース処理方法 | |
| US5502832A (en) | Associative memory architecture | |
| JPH01234930A (ja) | 文字列検索方法および装置 | |
| Nagumo et al. | Parallel algorithms for the static dictionary compression | |
| JPS583033A (ja) | 木構造検索処理装置 | |
| US6532468B2 (en) | Binary data search method for selecting from among candidate data, and apparatus therefor | |
| JP3062119B2 (ja) | 文字列探索用テーブル、その作成方法及び文字列探索方法 | |
| JP2540899B2 (ja) | ソ―タ記憶管理方式 | |
| EP0649106A1 (en) | Compactly stored word groups | |
| JPH10177582A (ja) | 最長一致検索方法及び装置 | |
| JPH03211627A (ja) | データ型変換方式 | |
| JPS60254254A (ja) | ハツシユテ−ブル | |
| JPS6373422A (ja) | 情報検索装置 | |
| JPS6393033A (ja) | デ−タ検索方式 | |
| JPH0226257B2 (ja) | ||
| JPS6295628A (ja) | インデクスキ−管理方式 | |
| JPH0668145A (ja) | 探索方法 | |
| JPH07182386A (ja) | 集積回路設計データの階層展開方法 | |
| JPS5995641A (ja) | 文字変換装置 | |
| JPH0531790B2 (ja) | ||
| JPS5854443A (ja) | ハツシユ変換装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |