JPH0375869A - 文字列検索方法 - Google Patents
文字列検索方法Info
- Publication number
- JPH0375869A JPH0375869A JP1212215A JP21221589A JPH0375869A JP H0375869 A JPH0375869 A JP H0375869A JP 1212215 A JP1212215 A JP 1212215A JP 21221589 A JP21221589 A JP 21221589A JP H0375869 A JPH0375869 A JP H0375869A
- Authority
- JP
- Japan
- Prior art keywords
- search
- character
- character string
- string
- retrieval
- 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.)
- Pending
Links
- 238000000034 method Methods 0.000 claims abstract description 33
- 238000010586 diagram Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 238000012795 verification Methods 0.000 description 2
- 238000004519 manufacturing process Methods 0.000 description 1
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
本発明は、コンピュータのメモリまたは２次記憶中に格
納された被検索文字列に対し複数の検索文字列を照合す
る文字列検索方法に関する。
納された被検索文字列に対し複数の検索文字列を照合す
る文字列検索方法に関する。
従来は、被検索文字列から複数の検索文字列を検索する
ために、検索文字列テーブルをハツシュテーブルにした
り、検索文字列を有限オートマトンとして表現したりし
ていた。
ために、検索文字列テーブルをハツシュテーブルにした
り、検索文字列を有限オートマトンとして表現したりし
ていた。
上述した従来の文字検索方法のうち、ハツシュテーブル
を用いる方法は、被検索文字列を適当な単語に分割する
ことができ、それらの単語のうちのいくつかを検索する
という照合には有効であるが、検索文字列として任意の
文字列を複数個与えた場合には、最悪の場合には被検索
文字列のすべての部分文字列に対しハツシュ関数を適用
しなければならなくなってしまい、複数個の任意の文字
列を検索する場合には不適当であるという欠点があり、
有限オート７１〜ンを用いる方法では、検索文字列が多
い場合や長い場合には有限オートマトンが犬きくなって
検索時のバックトラックか多くなるため処理効率か低下
するという欠点がある。
を用いる方法は、被検索文字列を適当な単語に分割する
ことができ、それらの単語のうちのいくつかを検索する
という照合には有効であるが、検索文字列として任意の
文字列を複数個与えた場合には、最悪の場合には被検索
文字列のすべての部分文字列に対しハツシュ関数を適用
しなければならなくなってしまい、複数個の任意の文字
列を検索する場合には不適当であるという欠点があり、
有限オート７１〜ンを用いる方法では、検索文字列が多
い場合や長い場合には有限オートマトンが犬きくなって
検索時のバックトラックか多くなるため処理効率か低下
するという欠点がある。
本発明の文字検索方法は、
複数の検索文字列を文字コード順にソートし、ソートし
た複数の検索文字列のそれぞれにインデックスを（ｔ
して検索文字列テーブルに格納するソート工程と、 被検索文字列の任意の位置から始まる部分文字列と検索
文字列テーブルの複数の検索文字列とを位置文字ずつ照
合して照合範囲を漸次狭めていく照合工程と、 照合に成功した検索文字列のインデックスを順次出力す
る出力工程とを有する。
た複数の検索文字列のそれぞれにインデックスを（ｔ
して検索文字列テーブルに格納するソート工程と、 被検索文字列の任意の位置から始まる部分文字列と検索
文字列テーブルの複数の検索文字列とを位置文字ずつ照
合して照合範囲を漸次狭めていく照合工程と、 照合に成功した検索文字列のインデックスを順次出力す
る出力工程とを有する。
このように、ソート工程で複数の検索文字列を文字コー
ド順にソートして、検索文字列テーブルに保持しておき
、照合工程で被検索文字列と検索文字列とを、文字コー
ド順に従って照合範囲を漸次狭めて照合することにより
、能率的に検索文字列を検出できる。
ド順にソートして、検索文字列テーブルに保持しておき
、照合工程で被検索文字列と検索文字列とを、文字コー
ド順に従って照合範囲を漸次狭めて照合することにより
、能率的に検索文字列を検出できる。
次に、本発明の実施例について図面を参照して説明する
。
。
第１図は本発明の文字列検索方法の一実施例の処理手順
を示すフローチャート、第２図は第１図の照合工程１４
の処理手順を詳細に示すフローチャート、第３図は本実
施例の動作を具体的に説明するためのデータ構造を示す
説明図である。
を示すフローチャート、第２図は第１図の照合工程１４
の処理手順を詳細に示すフローチャート、第３図は本実
施例の動作を具体的に説明するためのデータ構造を示す
説明図である。
検索文字列テーブル１１には検索に使用する文字列が与
えられている。ソート工程１２では与えられた文字列を
文字コード順にソートし、ソートした文字列を再度検索
文字列テーブル１１にそれぞれインデックスをイ」シて
格納する。照合工程１４では、被検索文字列１３を読込
み、読込んた被検索文字列１３を検索文字列テーブル１
１の検索文字列と順次照合する。出力工程］５ては照合
工程１４て一致した検索文字列があると、その検索文字
列のインデックスを出力データ１６として出力する。
えられている。ソート工程１２では与えられた文字列を
文字コード順にソートし、ソートした文字列を再度検索
文字列テーブル１１にそれぞれインデックスをイ」シて
格納する。照合工程１４では、被検索文字列１３を読込
み、読込んた被検索文字列１３を検索文字列テーブル１
１の検索文字列と順次照合する。出力工程］５ては照合
工程１４て一致した検索文字列があると、その検索文字
列のインデックスを出力データ１６として出力する。
次に、照合工程１４の処理手順を第２図を参照して説明
する。
する。
被検索文字列１３の先頭の文字に検索を開始する位置を
示す被検索文字列ポインタを設定する（ステップ２１）
。被検索文字列の検索は全て完了しているか判断しくス
テップ２２）、完了しておれば終了し、完了していなけ
れば被検索文字列１３と検索文字列とのパターンマツチ
処理を行う（ステップ２３）。パターンマツチ処理でマ
ツチした検索文字列が検出された場合、マツチした検索
文字列は１個か判断する（ステップ２４）。マツチした
検索文字列が１個てあれば検索は確定したことになるの
てマツチした検索文字列のインデックスを出力する（ス
テップ２５）。インテックスを出力した後、被検索文字
列１３の後続の文字列を検索するため被検索文字列ポイ
ンタをまたけカウントアツプしくステップ２６）、ステ
ップ２２にもどる。ステップ２４てマツチした検索文字
列が複数てあれば後続する文字についてもパターンマツ
チ処理を？ａ続して行う必要かあるのでステップ２６に
移行し、照合範囲を漸次狭めながら検索を繰り返す。ま
た、ステップ２４でマツチした検索文字列がない場合は
ｊ！ｉ号効なのでやはりステップ２６に移行し、被検索
文字列１３の次の部分のパターンマツチ処理を開始する
。 次に第３図を参照して、本実施例の動作を説明する
。
示す被検索文字列ポインタを設定する（ステップ２１）
。被検索文字列の検索は全て完了しているか判断しくス
テップ２２）、完了しておれば終了し、完了していなけ
れば被検索文字列１３と検索文字列とのパターンマツチ
処理を行う（ステップ２３）。パターンマツチ処理でマ
ツチした検索文字列が検出された場合、マツチした検索
文字列は１個か判断する（ステップ２４）。マツチした
検索文字列が１個てあれば検索は確定したことになるの
てマツチした検索文字列のインデックスを出力する（ス
テップ２５）。インテックスを出力した後、被検索文字
列１３の後続の文字列を検索するため被検索文字列ポイ
ンタをまたけカウントアツプしくステップ２６）、ステ
ップ２２にもどる。ステップ２４てマツチした検索文字
列が複数てあれば後続する文字についてもパターンマツ
チ処理を？ａ続して行う必要かあるのでステップ２６に
移行し、照合範囲を漸次狭めながら検索を繰り返す。ま
た、ステップ２４でマツチした検索文字列がない場合は
ｊ！ｉ号効なのでやはりステップ２６に移行し、被検索
文字列１３の次の部分のパターンマツチ処理を開始する
。 次に第３図を参照して、本実施例の動作を説明する
。
被検索文字列１３は左から右へシリアルにならんてＡ、
Ｂ、Ｃ，Ａ、Ｘ、〜”のようになっている。
Ｂ、Ｃ，Ａ、Ｘ、〜”のようになっている。
被検索文字列ポインタがまず最初の文字”Ａ“に設定さ
れ、検索文字列テーブル１１のインデックスａｌ ＋
ａ２ ＋〜、ａ□のものが該当することかわかる。しか
しマツチしたものが１個ではないので、被検索文字列ポ
インタを次の文字”Ｂ”に移動し、２文字目の検索を行
い、インデックスａ３ ＋ ａ４ ＋ ａ５のものか該
当することがわかる。そしてマツチしたものがまだ３個
なので被検索文字列ポインタを次の文字”Ｃ”に移動し
、３文字目の検索を行う。こんどはインデックスａ３の
もの１個しかないことかわかり、被検索文字列の最初の
３文字か検索文字列”ＡＢＣ”であることがわかる。し
たかって、検索文字列”ＡＢＣ”のインデックスａ３が
出力され、４文字目から新たに次の検索が開始さ井、同
しように検索処理が繰り返される。
れ、検索文字列テーブル１１のインデックスａｌ ＋
ａ２ ＋〜、ａ□のものが該当することかわかる。しか
しマツチしたものが１個ではないので、被検索文字列ポ
インタを次の文字”Ｂ”に移動し、２文字目の検索を行
い、インデックスａ３ ＋ ａ４ ＋ ａ５のものか該
当することがわかる。そしてマツチしたものがまだ３個
なので被検索文字列ポインタを次の文字”Ｃ”に移動し
、３文字目の検索を行う。こんどはインデックスａ３の
もの１個しかないことかわかり、被検索文字列の最初の
３文字か検索文字列”ＡＢＣ”であることがわかる。し
たかって、検索文字列”ＡＢＣ”のインデックスａ３が
出力され、４文字目から新たに次の検索が開始さ井、同
しように検索処理が繰り返される。
上記の検索処理において、ソート工程１２て各文字コー
ド毎のテーブル間の範囲を別途インデックステーブルに
格納しておけば、照合範囲が複数であればその文字コー
ドについて、検索文字列テーブルをサーチする必要はな
い。 Ａ”て始まる検索文字列がない場合はマツチする
文字列なしとする。
ド毎のテーブル間の範囲を別途インデックステーブルに
格納しておけば、照合範囲が複数であればその文字コー
ドについて、検索文字列テーブルをサーチする必要はな
い。 Ａ”て始まる検索文字列がない場合はマツチする
文字列なしとする。
（発明の効果）
以上説明したように本発明は、複数の検索文字列をソー
トして検索文字列テーブルに保持し、被検索文字列と検
索文字列デープルの検索文字列とを照合し、照合範囲を
漸次狭めていくことにより、照合の際のバックトラック
の少ない文字列検索が−Ｃきる効果がある。
トして検索文字列テーブルに保持し、被検索文字列と検
索文字列デープルの検索文字列とを照合し、照合範囲を
漸次狭めていくことにより、照合の際のバックトラック
の少ない文字列検索が−Ｃきる効果がある。
第１図は本発明の文字列検索方法の一実施例の処理手順
を示すフローチャート、第２図は第１図の照合工程１４
の処理手順を詳細に示すフローチャート、第３図は本実
施例の動作を具体的に説明するためのデータ構造を示す
説明図である。 １１・・・検索文字列テーブル、 １２・・・ソート工程、 Ｊ３・・・被検索文字列、 １４・・・照合工程、 １５・・・出力工程、 １６・・・出力データ。
を示すフローチャート、第２図は第１図の照合工程１４
の処理手順を詳細に示すフローチャート、第３図は本実
施例の動作を具体的に説明するためのデータ構造を示す
説明図である。 １１・・・検索文字列テーブル、 １２・・・ソート工程、 Ｊ３・・・被検索文字列、 １４・・・照合工程、 １５・・・出力工程、 １６・・・出力データ。
Claims (1)
- 【特許請求の範囲】 コンピュータのメモリまたは２次記憶中に格納された被
検索文字列に対し複数の検索文字列を照合する文字列検
索方法において、 複数の検索文字列を文字コード順にソートし、ソートし
た複数の検索文字列のそれぞれにインデックスを付して
検索文字列テーブルに格納するソート工程と、 被検索文字列の任意の位置から始まる部分文字列と検索
文字列テーブルの複数の検索文字列とを一文字ずつ照合
して照合範囲を漸次狭めていく照合工程と、 照合に成功した検索文字列のインデックスを順次出力す
る出力工程とを有することを特徴とする文字列検索方法
。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1212215A JPH0375869A (ja) | 1989-08-17 | 1989-08-17 | 文字列検索方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1212215A JPH0375869A (ja) | 1989-08-17 | 1989-08-17 | 文字列検索方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0375869A true JPH0375869A (ja) | 1991-03-29 |
Family
ID=16618844
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1212215A Pending JPH0375869A (ja) | 1989-08-17 | 1989-08-17 | 文字列検索方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0375869A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6249763B1 (en) | 1997-11-17 | 2001-06-19 | International Business Machines Corporation | Speech recognition apparatus and method |
-
1989
- 1989-08-17 JP JP1212215A patent/JPH0375869A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6249763B1 (en) | 1997-11-17 | 2001-06-19 | International Business Machines Corporation | Speech recognition apparatus and method |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7756847B2 (en) | Method and arrangement for searching for strings | |
| US6741985B2 (en) | Document retrieval system and search method using word set and character look-up tables | |
| US7062499B2 (en) | Enhanced multiway radix tree and related methods | |
| JPH08255176A (ja) | データベースのテーブルを比較する方法及びシステム | |
| CN105335481B (zh) | 一种大规模字符串文本的后缀索引构造方法及装置 | |
| Gonnet | Unstructured data bases or very efficient text searching | |
| US5619199A (en) | Order preserving run length encoding with compression codeword extraction for comparisons | |
| JPH0782504B2 (ja) | 情報検索処理方式および検索ファイル作成装置 | |
| JPH04326164A (ja) | データベース検索システム | |
| JPH0375869A (ja) | 文字列検索方法 | |
| US7039646B2 (en) | Method and system for compressing varying-length columns during index high key generation | |
| JP2786380B2 (ja) | キーワード照合検索処理方法 | |
| JP3534471B2 (ja) | マージソート方法及びマージソート装置 | |
| JPH10177582A (ja) | 最長一致検索方法及び装置 | |
| JPH02136969A (ja) | 文字列検索方式 | |
| JPH10240741A (ja) | 木構造型データの管理方法 | |
| JPH04340164A (ja) | マルチキーワード情報検索処理方式および検索ファイル作成装置 | |
| JPS6261118A (ja) | 木構造インデクスの検索方式 | |
| JP3104893B2 (ja) | 情報検索方式 | |
| JP2550022B2 (ja) | 文書情報検索方式 | |
| EP0649106B1 (en) | Compactly stored word groups | |
| JPH04279973A (ja) | 文字列比較方式 | |
| JPH07319888A (ja) | 索引検索方式 | |
| WO1992009960A1 (fr) | Dispositif d'extraction de donnees | |
| JPH01193928A (ja) | 推論機構付き情報検索システム |