JP2713962B2 - 文字列検索方法および装置 - Google Patents
文字列検索方法および装置Info
- Publication number
- JP2713962B2 JP2713962B2 JP63060372A JP6037288A JP2713962B2 JP 2713962 B2 JP2713962 B2 JP 2713962B2 JP 63060372 A JP63060372 A JP 63060372A JP 6037288 A JP6037288 A JP 6037288A JP 2713962 B2 JP2713962 B2 JP 2713962B2
- Authority
- JP
- Japan
- Prior art keywords
- code
- character string
- string search
- character
- conversion
- 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.)
- Expired - Fee Related
Links
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、データベースの検索方法に係り、特に、長
大な文字列の中から指定された文字列を検索するのに好
適な文字列検索方法および装置に関する。
大な文字列の中から指定された文字列を検索するのに好
適な文字列検索方法および装置に関する。
オフイス・オートメーシヨン化に伴つて、文書情報の
データベース化が急速に進んでおり、そのデータベース
の規模も大規模化してきている。このような状況の中
で、文書情報検索の高速化が強く望まれている。なかで
も、テキストと呼ばれる文字列の中から、パターンまた
はキーワードと呼ばれる指定された特定の文字列を探し
出す文字列検索処理は、使用頻度も高く、処理負荷も極
めて大きいので、高速化のニーズが特に望まれている。
データベース化が急速に進んでおり、そのデータベース
の規模も大規模化してきている。このような状況の中
で、文書情報検索の高速化が強く望まれている。なかで
も、テキストと呼ばれる文字列の中から、パターンまた
はキーワードと呼ばれる指定された特定の文字列を探し
出す文字列検索処理は、使用頻度も高く、処理負荷も極
めて大きいので、高速化のニーズが特に望まれている。
このようなニーズにこたえるために、文字列検索をハ
ードウエア化して処理する方法がいくつか提案されてい
る。例えば、「ハードウエア・システムズ・フオア・テ
キスト・インフオメイシヨン・リトリーバル（Hollaar,
L.A.:Hardware Systems for Text Information Retriev
al,ACM SIGIR Conf.June 1983）や「ザ・デザイン・オ
ブ・スペシヤルパーポス・ブイエルエスアイ・チツプ
ス」（Foster,M.J.and Kung,H.T.:The Design of Speci
al−Purpose VLSI Chips,Computer,Vol.13.No.1.1980）
ではセルラ・アレイ法による文字列検索方法について論
じられている。これは、第４図に示すように、テキスト
の入力文字コード103を文字列検索装置101に入れ、その
セル内でパターンレジスタ110のパターンの１文字とテ
キストの入力文字１文字とを比較器111により比較し、
その結果に応じて制御情報を発生させ、それをとなりの
セルに伝達しながら文字列検索を実行する方法である。
これらの方法はいずれも、テキストの入力文字をそのま
ま文字列検索装置に入力する方法となつていた。
ードウエア化して処理する方法がいくつか提案されてい
る。例えば、「ハードウエア・システムズ・フオア・テ
キスト・インフオメイシヨン・リトリーバル（Hollaar,
L.A.:Hardware Systems for Text Information Retriev
al,ACM SIGIR Conf.June 1983）や「ザ・デザイン・オ
ブ・スペシヤルパーポス・ブイエルエスアイ・チツプ
ス」（Foster,M.J.and Kung,H.T.:The Design of Speci
al−Purpose VLSI Chips,Computer,Vol.13.No.1.1980）
ではセルラ・アレイ法による文字列検索方法について論
じられている。これは、第４図に示すように、テキスト
の入力文字コード103を文字列検索装置101に入れ、その
セル内でパターンレジスタ110のパターンの１文字とテ
キストの入力文字１文字とを比較器111により比較し、
その結果に応じて制御情報を発生させ、それをとなりの
セルに伝達しながら文字列検索を実行する方法である。
これらの方法はいずれも、テキストの入力文字をそのま
ま文字列検索装置に入力する方法となつていた。
上記のように従来技術はテキストの入力文字をそのま
ま文字列検索装置に入力させていたので、文字列検索装
置のハードウエア量が大きくなるという問題があつた。
例えば第４図の場合、文字列検索装置101内には、パタ
ーン１文字を格納するための８ビツトのパターンレジス
タ110とパターン１文字とテキストの入力文字とを比較
するための８ビツトの比較器110がパターン長分だけ必
要であつた。
ま文字列検索装置に入力させていたので、文字列検索装
置のハードウエア量が大きくなるという問題があつた。
例えば第４図の場合、文字列検索装置101内には、パタ
ーン１文字を格納するための８ビツトのパターンレジス
タ110とパターン１文字とテキストの入力文字とを比較
するための８ビツトの比較器110がパターン長分だけ必
要であつた。
本発明の目的は、ハードウエア量を削減することが可
能な文字列検索方法および装置を提供することにある。
能な文字列検索方法および装置を提供することにある。
上記目的を達成するために、本発明は、入力文字コー
ドを入力文字コード長より短かいコードに変換するコー
ド変換機構を設けることに特徴がある。
ドを入力文字コード長より短かいコードに変換するコー
ド変換機構を設けることに特徴がある。
本発明によれば、コード変換機構は入力文字を入力文
字コード長より短かいコードに変換するので、その変換
コードを文字列検索装置の入力とすれば、文字列検索装
置内のレジスタや比較器は変換コード長のレジスタや比
較器で済ませることができ、ハードウエア量を削減でき
る。
字コード長より短かいコードに変換するので、その変換
コードを文字列検索装置の入力とすれば、文字列検索装
置内のレジスタや比較器は変換コード長のレジスタや比
較器で済ませることができ、ハードウエア量を削減でき
る。
以下、本発明の実施例を図面により説明する。
まず、本発明の第一の実施例を第１図と第２図により
説明する。第１図は本発明の全体構成図である。５はテ
キストを記憶している記憶装置、３はテキストの入力文
字格納する入力文字コードレジスタ、２は入力文字コー
ドを変換コードに変換するコード変換機構、４は変換さ
れたコードを格納する変換コードレジスタ、１は文字列
検索装置である。本発明では、テキストが１文字ずつ記
憶装置５から入力文字コードレジスタ３を経てコード変
換機構２に入力され、入力文字コード長より短かい変換
コードに変換され、変換コードレジスタ４を経て文字列
検索装置１に入力され、文字列検索が実行される。した
がつて、文字列検索装置１内のレジスタや比較器は変換
コード長に対応したもので十分である。第２図は第１図
の文字列検索装置の一例の構成を示す。第２図により、
例を用いて詳しく説明する。パターンの例として「AB
C」を考える。この場合、文字列検索装置１は、入力コ
ードが「Ａ」か「Ｂ」か「Ｃ」かその他の文字かを判別
できれば、検索の機能を果たすのに十分である。すなわ
ち、文字列検索装置への入力コードとして４種類の変換
コードを用意すれば良い。これは２ビツトの情報で可能
である。本実施例ではコード変換機構２の実現形態とし
てコード変換テーブル20を用い、「Ａ」を表現する８ビ
ツトのコードＸ▼C1▼に２ビツトのコード「Ｂ」▼01▼
を、「Ｂ」を表現するコードＸ▼C2▼にＢ▼10▼を、
「Ｃ」を表現するコードＸ▼C3▼にＢ▼11▼を対応さ
せ、その他の文字を表現する８ビツトのコードに対して
は全てに２ビツトのコードＢ▼00▼を対応させる。
説明する。第１図は本発明の全体構成図である。５はテ
キストを記憶している記憶装置、３はテキストの入力文
字格納する入力文字コードレジスタ、２は入力文字コー
ドを変換コードに変換するコード変換機構、４は変換さ
れたコードを格納する変換コードレジスタ、１は文字列
検索装置である。本発明では、テキストが１文字ずつ記
憶装置５から入力文字コードレジスタ３を経てコード変
換機構２に入力され、入力文字コード長より短かい変換
コードに変換され、変換コードレジスタ４を経て文字列
検索装置１に入力され、文字列検索が実行される。した
がつて、文字列検索装置１内のレジスタや比較器は変換
コード長に対応したもので十分である。第２図は第１図
の文字列検索装置の一例の構成を示す。第２図により、
例を用いて詳しく説明する。パターンの例として「AB
C」を考える。この場合、文字列検索装置１は、入力コ
ードが「Ａ」か「Ｂ」か「Ｃ」かその他の文字かを判別
できれば、検索の機能を果たすのに十分である。すなわ
ち、文字列検索装置への入力コードとして４種類の変換
コードを用意すれば良い。これは２ビツトの情報で可能
である。本実施例ではコード変換機構２の実現形態とし
てコード変換テーブル20を用い、「Ａ」を表現する８ビ
ツトのコードＸ▼C1▼に２ビツトのコード「Ｂ」▼01▼
を、「Ｂ」を表現するコードＸ▼C2▼にＢ▼10▼を、
「Ｃ」を表現するコードＸ▼C3▼にＢ▼11▼を対応さ
せ、その他の文字を表現する８ビツトのコードに対して
は全てに２ビツトのコードＢ▼00▼を対応させる。
まず２ビツトの変換コードに変換されたパターンを予
め文字列検索装置１内のレジスタ10にセツトする。テキ
ストは１文字ずつ８ビツトのコードとして入力文字コー
ドレジスタ３に入力される。この入力文字コードをアド
レスとしてコード変換テーブル２によりコード変換し、
変換コードを２ビツトの変換コードレジスタ４に入力す
る。さらに、この変換コードを文字列検索装置１の入力
コードとして入力する。文字列検索装置１内の各セルで
は、入力された変換コードとパターンレジスタ10のパタ
ーンとを比較器11で比較し、その結果に応じて制御情報
を発生させ、シフトレジスタ等の伝達機構12により、隣
りのセルに伝達しながら文字列検索を実行する。したが
つて、文字列検索装置１内のパターンレジスタ10や比較
器11は２ビツトのもので十分である。これにより、文字
列検索装置１内のハードウエア量を大幅に削減すること
ができる。
め文字列検索装置１内のレジスタ10にセツトする。テキ
ストは１文字ずつ８ビツトのコードとして入力文字コー
ドレジスタ３に入力される。この入力文字コードをアド
レスとしてコード変換テーブル２によりコード変換し、
変換コードを２ビツトの変換コードレジスタ４に入力す
る。さらに、この変換コードを文字列検索装置１の入力
コードとして入力する。文字列検索装置１内の各セルで
は、入力された変換コードとパターンレジスタ10のパタ
ーンとを比較器11で比較し、その結果に応じて制御情報
を発生させ、シフトレジスタ等の伝達機構12により、隣
りのセルに伝達しながら文字列検索を実行する。したが
つて、文字列検索装置１内のパターンレジスタ10や比較
器11は２ビツトのもので十分である。これにより、文字
列検索装置１内のハードウエア量を大幅に削減すること
ができる。
次に本発明の第二の実施例を用いて、変換コード長が
２ビツトでも４文字以上のパターン長のパターンの検索
が可能であることを示す。パターンの例としてパターン
長が６であるパターン「ABCDEF」を考える。この場合の
本発明の構成図を第３図に示す。ここでは、パターンの
３文字毎にコード変換テーブル20を用いている。コード
変換テーブル20−１はパターンの前半の３文字「Ａ」
（Ｘ▼C1▼），「Ｂ」（Ｘ▼C2▼），「Ｃ」（Ｘ▼C3
▼）をそれぞれ２ビツトのコードＢ▼01▼,B▼10▼,B▼
11▼に変換し、その他の文字はＢ▼00▼に変換する。第
２のコード変換テーブル20−２はパターンの後半の３文
字「Ｄ」（Ｘ▼C4▼），「Ｅ」（Ｘ▼C5▼），「Ｆ」
（Ｘ▼C6▼）をそれぞれ２ビツトのコードＢ▼01▼,B▼
10▼,B▼11▼に変換し、その他の文字はＢ▼00▼に変換
する。そして、この２つの変換コードがそれぞれパター
ンの前半の「ABC」文字列検索を実行する文字列検索装
置１−１と後半の「DEF」の文字列検索を実行する文字
列検索装置１−２に入力される。このようにして、変換
コード長が２ビツトであつても、４文字以上のパターン
長のパターンを検索すことが複数のコード変換テーブル
を用いることにより可能になる。コード変換テーブル20
−１と20−２は１つのテーブルとして表現し、１つのRA
Mを用いて実行してもよい。このようにして、変換コー
ド長に応じて複数のコード変換テーブルを用いることに
より、パターン長が長くても、パターン数が多くても、
文字列検索が実行できる。
２ビツトでも４文字以上のパターン長のパターンの検索
が可能であることを示す。パターンの例としてパターン
長が６であるパターン「ABCDEF」を考える。この場合の
本発明の構成図を第３図に示す。ここでは、パターンの
３文字毎にコード変換テーブル20を用いている。コード
変換テーブル20−１はパターンの前半の３文字「Ａ」
（Ｘ▼C1▼），「Ｂ」（Ｘ▼C2▼），「Ｃ」（Ｘ▼C3
▼）をそれぞれ２ビツトのコードＢ▼01▼,B▼10▼,B▼
11▼に変換し、その他の文字はＢ▼00▼に変換する。第
２のコード変換テーブル20−２はパターンの後半の３文
字「Ｄ」（Ｘ▼C4▼），「Ｅ」（Ｘ▼C5▼），「Ｆ」
（Ｘ▼C6▼）をそれぞれ２ビツトのコードＢ▼01▼,B▼
10▼,B▼11▼に変換し、その他の文字はＢ▼00▼に変換
する。そして、この２つの変換コードがそれぞれパター
ンの前半の「ABC」文字列検索を実行する文字列検索装
置１−１と後半の「DEF」の文字列検索を実行する文字
列検索装置１−２に入力される。このようにして、変換
コード長が２ビツトであつても、４文字以上のパターン
長のパターンを検索すことが複数のコード変換テーブル
を用いることにより可能になる。コード変換テーブル20
−１と20−２は１つのテーブルとして表現し、１つのRA
Mを用いて実行してもよい。このようにして、変換コー
ド長に応じて複数のコード変換テーブルを用いることに
より、パターン長が長くても、パターン数が多くても、
文字列検索が実行できる。
本発明の実施例では、文字列検索装置としてセルラ・
アレイ法を用いた場合について説明したが、本発明はセ
ルラ・アレイ法に限定せず、その他の方式でも有効であ
る。例えば、有限オートマトンを利用した方法でも、本
発明を用いてコード長の短かい変換コードに変換すれ
ば、利用する状態遷移テーブルの大きさを少なくできる
効果がある。
アレイ法を用いた場合について説明したが、本発明はセ
ルラ・アレイ法に限定せず、その他の方式でも有効であ
る。例えば、有限オートマトンを利用した方法でも、本
発明を用いてコード長の短かい変換コードに変換すれ
ば、利用する状態遷移テーブルの大きさを少なくできる
効果がある。
セルラ・アレイ法を用いた文字列検索装置内のハード
ウエア量はレジスタや比較器の幅と個数によつてほぼ決
定される。従来方式では、８ビツト幅のレジスタや比較
器を必要としたので、極めて大きなハードウエア量とな
つていた。本発明では、変換コード長をｋビツトとする
と、ｋビツト幅のレジスタや比較器で済むので、ハード
ウエア量をk/8化することができる。本発明では、コー
ド変換を実現するコード変換テーブルを必要とするが、
これはRAMで実現でき、レジスタや比較器などのハード
ウエアに比べて極めて安価であるので経済性においても
効果がある。
ウエア量はレジスタや比較器の幅と個数によつてほぼ決
定される。従来方式では、８ビツト幅のレジスタや比較
器を必要としたので、極めて大きなハードウエア量とな
つていた。本発明では、変換コード長をｋビツトとする
と、ｋビツト幅のレジスタや比較器で済むので、ハード
ウエア量をk/8化することができる。本発明では、コー
ド変換を実現するコード変換テーブルを必要とするが、
これはRAMで実現でき、レジスタや比較器などのハード
ウエアに比べて極めて安価であるので経済性においても
効果がある。
第１図は本発明の全体構成図、第２図と第３図は本発明
のそれぞれの実施例の説明図、第４図は従来技術の説明
図である。 １……文字列検索装置、２……コード変換機構、３……
入力文字コードレジスタ、４……変換コードレジスタ、
５……記憶装置、20……コード変換テーブル。
のそれぞれの実施例の説明図、第４図は従来技術の説明
図である。 １……文字列検索装置、２……コード変換機構、３……
入力文字コードレジスタ、４……変換コードレジスタ、
５……記憶装置、20……コード変換テーブル。
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 昭56−2063（ＪＰ，Ａ) 特開 昭60−105040（ＪＰ，Ａ)
Claims (7)
- 【請求項１】テキストと呼ばれる文字列の中からパター
ンと呼ばれる特定の文字列を探し出す文字列検索方法に
おいて、テキストの入力文字コードをそのコード長より
短かいコード長のコードに変換し、該変換コード列に対
して文字列検索を行うことを特徴とする文字列検索方
法。 - 【請求項２】パターンを形成している文字の種類とその
他の文字だけを判別できるようにすることにより変換コ
ードの種類を減らし変換コード長を短かくすることを特
徴とする請求項１項記載の文字列検索方法。 - 【請求項３】多種のコードから成つている検索すべき原
データを、少なくも検索するのに必要な種類のコードだ
けからなるデータに変換することを特徴とする請求項１
項記載の文字列検索方法。 - 【請求項４】変換されるデータのコード長は、変換され
る前の原データのコード長より短かくすることを特徴と
する請求項１項記載の文字列検索方法。 - 【請求項５】テキストと呼ばれる文字列の中からパター
ンと呼ばれる特定の文字列を探し出す文字列検索方法に
おいて、テキストの入力文字コードをそのコード長より
短かいコード長のコードに変換する変換手段を設け、該
変換コード列に対して文字列検索を行うことを特徴とす
る文字列検索装置。 - 【請求項６】パターンを形成している文字の種類とその
他の文字だけを判別できるようにすることにより変換コ
ードの種類を減らし変換コード長を短かくすることを特
徴とする請求項５項記載の文字列検索装置。 - 【請求項７】上記変換手段は、多種のコードから成つて
いる検索すべき原データを、少なくも検索するのに必要
な種類のコードだけからなるデータに変換する手段から
なることを特徴とする請求項５項記載の文字列検索装
置。
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 JPH01234930A (ja) | 1989-09-20 |
| JP2713962B2 true 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) |
Families Citing this family (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
Also Published As
| Publication number | Publication date |
|---|---|
| JPH01234930A (ja) | 1989-09-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN1531692B (zh) | 用于处理大量字符的高效整理元素结构 | |
| CA2326153C (en) | Feature diffusion across hyperlinks | |
| US5621908A (en) | Parallel sorting system to reduce the amount of communication between processing devices | |
| JP2765506B2 (ja) | 論理回路遅延情報保持方式 | |
| JP2006127552A (ja) | データ送信方法、データ等化方法及び装置 | |
| US6347315B1 (en) | Method and apparatus for selecting and utilizing one of computers or databases | |
| JP2713962B2 (ja) | 文字列検索方法および装置 | |
| Lee et al. | Text retrieval machines | |
| JP3278440B2 (ja) | 検索制御装置及び検索システム | |
| US6147628A (en) | Efficient data conversion of list of strings | |
| Delcaro et al. | A method for transposing externally stored matrices | |
| Duff et al. | MA62-A Frontal Code for Sparse Positive-Definite Symmetric Systems from Finite-Element Applications | |
| JPH0749880A (ja) | データベースアクセス要求装置 | |
| Temperton | Fast methods on parallel and vector machines | |
| JPS6393033A (ja) | デ−タ検索方式 | |
| JPS59189442A (ja) | ソ−テイング処理方式 | |
| Chen et al. | Efficient permutation-based range-join algorithms on N-dimensionalmeshes using data-shifting | |
| KR20000004589A (ko) | 데이터베이스 검색을 최적화하기 위한 시뮬레이션 시스템 및 그방법과 그에 따른 데이터베이스 검색 방법 | |
| Stallings | An application of coroutines and backtracking in interactive systems | |
| JPH0581339A (ja) | データ処理装置 | |
| Niblett | Macro Search Techniques in the Interrogation of Legal Languare | |
| JPH03211627A (ja) | データ型変換方式 | |
| JPH02247733A (ja) | バイナリコード変換の簡略化方式 | |
| Chen et al. | Multimedia task reliability analysis based on token ring network | |
| JPS5897742A (ja) | 検索装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |