JPH09297771A - 文字列検索方法とその装置、並びに、文字列検索情報生成方法とその装置 - Google Patents
文字列検索方法とその装置、並びに、文字列検索情報生成方法とその装置Info
- Publication number
- JPH09297771A JPH09297771A JP8113684A JP11368496A JPH09297771A JP H09297771 A JPH09297771 A JP H09297771A JP 8113684 A JP8113684 A JP 8113684A JP 11368496 A JP11368496 A JP 11368496A JP H09297771 A JPH09297771 A JP H09297771A
- Authority
- JP
- Japan
- Prior art keywords
- character string
- character
- search
- predetermined
- information
- 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
- Document Processing Apparatus (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【課題】 文字列を高速に検索できる文字列検索方法と
その装置を提供する。 【解決手段】 文字列情報に含まれる各文字と前記各文
字の発生頻度を備えるテーブルを検索して、所定の文字
列に含まれる全ての文字が前記テーブルに存在している
かどうか検索し（Ｓ１０、Ｓ１１）、所定の文字列に含
まれる全ての文字が前記テーブルに存在していると判定
された場合、前記文字列情報を検索して、前記所定の文
字列に一致する文字列があるかどうかを検索する（Ｓ１
２，Ｓ１３）。
その装置を提供する。 【解決手段】 文字列情報に含まれる各文字と前記各文
字の発生頻度を備えるテーブルを検索して、所定の文字
列に含まれる全ての文字が前記テーブルに存在している
かどうか検索し（Ｓ１０、Ｓ１１）、所定の文字列に含
まれる全ての文字が前記テーブルに存在していると判定
された場合、前記文字列情報を検索して、前記所定の文
字列に一致する文字列があるかどうかを検索する（Ｓ１
２，Ｓ１３）。
Description
【０００１】
【発明の属する技術分野】本発明は、文字列検索方法と
その装置、並びに、文字列検索情報生成方法とその装
置、特に、ファイル中から文字列を高速に検索する文字
列検索方法とその装置に関する。
その装置、並びに、文字列検索情報生成方法とその装
置、特に、ファイル中から文字列を高速に検索する文字
列検索方法とその装置に関する。
【０００２】
【従来の技術】従来、文字列情報を含んだファイル中
に、所定の文字列が存在するか否かを調べる検索処理に
おいては、対象ファイルを読み出し、文字列情報と指定
文字列の比較を行うことによって文字列の存在の有無を
チェックしていた。この様な検索方法では、無条件に対
象ファイルを読み出し、文字列の比較を行っていた。
に、所定の文字列が存在するか否かを調べる検索処理に
おいては、対象ファイルを読み出し、文字列情報と指定
文字列の比較を行うことによって文字列の存在の有無を
チェックしていた。この様な検索方法では、無条件に対
象ファイルを読み出し、文字列の比較を行っていた。
【０００３】
【発明が解決しようとする課題】一般に、読み出し速度
の遅い記憶装置では、全検索時間に占めるファイル読み
出し時間の割合が大きくなる。また、ファイル中の文字
列が膨大な場合には、文字列の比較に時間がかかる。こ
れらの理由から、従来の無条件にファイルを読み出し、
文字列の比較を行う方法では、処理時間が長くなるとい
う問題があった。
の遅い記憶装置では、全検索時間に占めるファイル読み
出し時間の割合が大きくなる。また、ファイル中の文字
列が膨大な場合には、文字列の比較に時間がかかる。こ
れらの理由から、従来の無条件にファイルを読み出し、
文字列の比較を行う方法では、処理時間が長くなるとい
う問題があった。
【０００４】本発明は、上記従来例に鑑みてなされたも
ので、文字列を高速に検索できる文字列検索方法とその
装置を提供することを目的とする。
ので、文字列を高速に検索できる文字列検索方法とその
装置を提供することを目的とする。
【０００５】
【課題を解決するための手段】上記目的を達成するた
め、本発明の文字列検索方法とその装置、並びに、文字
列検索情報生成方法とその装置は以下の構成を備える。
即ち、文字列情報に含まれる各文字と前記各文字の発生
頻度を備えるテーブルを検索して、所定の文字列に含ま
れる全ての文字が前記テーブルに存在しているかどうか
検索する第１の検索工程と、前記第１の検索工程で、所
定の文字列に含まれる全ての文字が前記テーブルに存在
していると判定された場合、前記文字列情報を検索し
て、前記所定の文字列に一致する文字列があるかどうか
を検索する第２の検索工程とを備える。
め、本発明の文字列検索方法とその装置、並びに、文字
列検索情報生成方法とその装置は以下の構成を備える。
即ち、文字列情報に含まれる各文字と前記各文字の発生
頻度を備えるテーブルを検索して、所定の文字列に含ま
れる全ての文字が前記テーブルに存在しているかどうか
検索する第１の検索工程と、前記第１の検索工程で、所
定の文字列に含まれる全ての文字が前記テーブルに存在
していると判定された場合、前記文字列情報を検索し
て、前記所定の文字列に一致する文字列があるかどうか
を検索する第２の検索工程とを備える。
【０００６】また、別の発明は、文字列情報に含まれる
各文字の発生数をカウントして、前記各文字と対応する
発生頻度を備えるテーブルを生成するテーブル生成工程
と、前記テーブル生成工程で生成されたテーブルと前記
文字列情報を関連づけて格納する格納工程とを備える。
各文字の発生数をカウントして、前記各文字と対応する
発生頻度を備えるテーブルを生成するテーブル生成工程
と、前記テーブル生成工程で生成されたテーブルと前記
文字列情報を関連づけて格納する格納工程とを備える。
【０００７】また、別の発明は、文字列情報に含まれる
各文字と前記各文字の発生頻度を備えるテーブルを検索
して、所定の文字列に含まれる全ての文字が前記テーブ
ルに存在しているかどうか検索する第１の検索手段と、
前記第１の検索手段で、所定の文字列に含まれる全ての
文字が前記テーブルに存在していると判定された場合、
前記文字列情報を検索して、前記所定の文字列に一致す
る文字列があるかどうかを検索する第２の検索手段とを
備える。
各文字と前記各文字の発生頻度を備えるテーブルを検索
して、所定の文字列に含まれる全ての文字が前記テーブ
ルに存在しているかどうか検索する第１の検索手段と、
前記第１の検索手段で、所定の文字列に含まれる全ての
文字が前記テーブルに存在していると判定された場合、
前記文字列情報を検索して、前記所定の文字列に一致す
る文字列があるかどうかを検索する第２の検索手段とを
備える。
【０００８】また、別の発明は、文字列情報に含まれる
各文字の発生数をカウントして、前記各文字と対応する
発生頻度を備えるテーブルを生成するテーブル生成手段
と、前記テーブル生成手段で生成されたテーブルと前記
文字列情報を関連づけて格納する格納手段とを備える。
また、別の発明は、コンピュータプログラム製品であっ
て、文字列情報から所定の文字列を検索する、コンピュ
ータ読み取り可能なプログラムコード手段を有するコン
ピュータ使用可能な媒体を備え、前記コンピュータプロ
グラム製品は、文字列情報に含まれる各文字と前記各文
字の発生頻度を備えるテーブルを検索して、所定の文字
列に含まれる全ての文字が前記テーブルに存在している
かどうか検索する、第１のコンピュータ読み取り可能な
プログラムコード手段と、前記第１のコンピュータ読み
取り可能なプログラムコード手段で、所定の文字列に含
まれる全ての文字が前記テーブルに存在していると判定
された場合、前記文字列情報を検索して、前記所定の文
字列に一致する文字列があるかどうかを検索する第２の
コンピュータ読み取り可能なプログラムコード手段とを
備える。また、別の発明は、コンピュータプログラム製
品であって、文字列情報に基づいて、所定の文字列の検
索に適した構造の情報を生成する、コンピュータ読み取
り可能なプログラムコード手段を有するコンピュータ使
用可能な媒体を備え、前記コンピュータプログラム製品
は、文字列情報に含まれる各文字の発生数をカウントし
て、前記各文字と対応する発生頻度を備えるテーブルを
生成する第１のコンピュータ読み取り可能なプログラム
コード手段と、前記テーブル生成工程で生成されたテー
ブルと前記文字列情報を関連づけて格納する、第２のコ
ンピュータ読み取り可能なプログラムコード手段とを備
える。
各文字の発生数をカウントして、前記各文字と対応する
発生頻度を備えるテーブルを生成するテーブル生成手段
と、前記テーブル生成手段で生成されたテーブルと前記
文字列情報を関連づけて格納する格納手段とを備える。
また、別の発明は、コンピュータプログラム製品であっ
て、文字列情報から所定の文字列を検索する、コンピュ
ータ読み取り可能なプログラムコード手段を有するコン
ピュータ使用可能な媒体を備え、前記コンピュータプロ
グラム製品は、文字列情報に含まれる各文字と前記各文
字の発生頻度を備えるテーブルを検索して、所定の文字
列に含まれる全ての文字が前記テーブルに存在している
かどうか検索する、第１のコンピュータ読み取り可能な
プログラムコード手段と、前記第１のコンピュータ読み
取り可能なプログラムコード手段で、所定の文字列に含
まれる全ての文字が前記テーブルに存在していると判定
された場合、前記文字列情報を検索して、前記所定の文
字列に一致する文字列があるかどうかを検索する第２の
コンピュータ読み取り可能なプログラムコード手段とを
備える。また、別の発明は、コンピュータプログラム製
品であって、文字列情報に基づいて、所定の文字列の検
索に適した構造の情報を生成する、コンピュータ読み取
り可能なプログラムコード手段を有するコンピュータ使
用可能な媒体を備え、前記コンピュータプログラム製品
は、文字列情報に含まれる各文字の発生数をカウントし
て、前記各文字と対応する発生頻度を備えるテーブルを
生成する第１のコンピュータ読み取り可能なプログラム
コード手段と、前記テーブル生成工程で生成されたテー
ブルと前記文字列情報を関連づけて格納する、第２のコ
ンピュータ読み取り可能なプログラムコード手段とを備
える。
【０００９】
【発明の実施の形態】はじめに、本発明の実施の形態の
文字列検索方法とその装置のポイントを要約した後に、
その詳細な説明に入るものとする。本発明の実施の形態
の文字列検索方法とその装置は、所定の文字列情報か
ら、同一文字の出現回数を計測し、文字出現テーブルを
生成する。
文字列検索方法とその装置のポイントを要約した後に、
その詳細な説明に入るものとする。本発明の実施の形態
の文字列検索方法とその装置は、所定の文字列情報か
ら、同一文字の出現回数を計測し、文字出現テーブルを
生成する。
【００１０】そして、所定の検索文字列の含まれる各文
字がすべて、生成された文字出現テーブルに存在してい
るかどうか検索する。その結果、存在していなければ、
前述の文字列情報には、所定の検索文字列はないと判定
する。一方、存在していれば、前述の文字列情報を検索
して、前述の所定の検索文字列が存在するかどうか判定
する。ここで、この文字列情報検出処理では、出現頻度
の少ない文字から順に文字比較を行って、検索を進め
る。
字がすべて、生成された文字出現テーブルに存在してい
るかどうか検索する。その結果、存在していなければ、
前述の文字列情報には、所定の検索文字列はないと判定
する。一方、存在していれば、前述の文字列情報を検索
して、前述の所定の検索文字列が存在するかどうか判定
する。ここで、この文字列情報検出処理では、出現頻度
の少ない文字から順に文字比較を行って、検索を進め
る。
【００１１】以上の処理手順により、処理に関わるデー
タ量を大幅に削減できる。また、文字列の比較を必ずし
も、データの最後まで行う必要がなくなるため、検索時
間を大幅に短縮できる。以下、本発明の実施の形態の文
字列検索装置の詳細な説明を行う。図１は、本発明の一
実施の形態にかかる文字検索装置を説明するブロック図
である。
タ量を大幅に削減できる。また、文字列の比較を必ずし
も、データの最後まで行う必要がなくなるため、検索時
間を大幅に短縮できる。以下、本発明の実施の形態の文
字列検索装置の詳細な説明を行う。図１は、本発明の一
実施の形態にかかる文字検索装置を説明するブロック図
である。
【００１２】１は、マイクロプロセッサ（ＣＰＵ）であ
り、検索処理のための演算・論理判断等を行い、各バス
を介してそれらに接続された各構成要素を制御する。マ
イクロプロセッサ（ＣＰＵ）１は、ＲＯＭ２に格納され
た検索処理プログラムを読み出し、解釈し、実行する。
読み出し専用メモリ（ＲＯＭ）２は、上述の検索処理プ
ログラムの他にも、各種制御プログラムや関連データを
格納している。
り、検索処理のための演算・論理判断等を行い、各バス
を介してそれらに接続された各構成要素を制御する。マ
イクロプロセッサ（ＣＰＵ）１は、ＲＯＭ２に格納され
た検索処理プログラムを読み出し、解釈し、実行する。
読み出し専用メモリ（ＲＯＭ）２は、上述の検索処理プ
ログラムの他にも、各種制御プログラムや関連データを
格納している。
【００１３】３は、ランダムアクセスメモリ（ＲＡＭ）
であり、各構成要素からの各種データの一時保存に用い
たり、ＣＰＵ１の作業領域として用いられる。４は、キ
ーボード（ＫＢ）であり、文字や記号等を入力する文字
キーおよび各種機能を指示する機能キー等を配置してあ
る。５は、ＣＲＴコントローラ（ＣＲＴＣ）であり、表
示器（ＣＲＴ）７の表示制御を行う。
であり、各構成要素からの各種データの一時保存に用い
たり、ＣＰＵ１の作業領域として用いられる。４は、キ
ーボード（ＫＢ）であり、文字や記号等を入力する文字
キーおよび各種機能を指示する機能キー等を配置してあ
る。５は、ＣＲＴコントローラ（ＣＲＴＣ）であり、表
示器（ＣＲＴ）７の表示制御を行う。
【００１４】６は、キャラクタージェネレータ（ＣＧ）
であり、表示器（ＣＲＴ）１１に表示する文字・記号等
のキャラクタ信号を発生させる。７は、表示器（ＣＲ
Ｔ）であり、文字列等を表示する。８は、フロッピーデ
ィスクコントローラ（ＦＤＣ）であり、フロッピーディ
スクドライブ（ＦＤＤ）９の制御を行う。
であり、表示器（ＣＲＴ）１１に表示する文字・記号等
のキャラクタ信号を発生させる。７は、表示器（ＣＲ
Ｔ）であり、文字列等を表示する。８は、フロッピーデ
ィスクコントローラ（ＦＤＣ）であり、フロッピーディ
スクドライブ（ＦＤＤ）９の制御を行う。
【００１５】９は、フロッピーディスクドライブ（ＦＤ
Ｄ）であり、セットされているフロッピーディスク（Ｆ
Ｄ）１１へのデータの書き込み、読み込み等を行う。１
０は、バス（ＢＳ）であり、各処理ユニット間でのコン
トロール信号のやり取り、データの転送、アドレス信号
の転送等の為に使用される。図２は、ＦＤ１１へ保存さ
れるファイルの形式を表したものである。与えられた文
字列情報から、文字出現テーブルを構築し、文字列情報
の前に付加して、１つのファイルが作成される。
Ｄ）であり、セットされているフロッピーディスク（Ｆ
Ｄ）１１へのデータの書き込み、読み込み等を行う。１
０は、バス（ＢＳ）であり、各処理ユニット間でのコン
トロール信号のやり取り、データの転送、アドレス信号
の転送等の為に使用される。図２は、ＦＤ１１へ保存さ
れるファイルの形式を表したものである。与えられた文
字列情報から、文字出現テーブルを構築し、文字列情報
の前に付加して、１つのファイルが作成される。
【００１６】図３は、文字出現テーブルの詳細を示す図
である。尚、本実施の形態では、読者の理解を容易にす
るために、文字列情報中の文字は全て１ワード（１６ビ
ット）で表されるものとする。文字出現テーブルは、文
字列情報中に同一文字コードがいくつ存在するかを表す
テーブルであり、各文字コードに対して１バイト（８ビ
ット）の出現回数を格納する領域が１対１に対応してい
る。
である。尚、本実施の形態では、読者の理解を容易にす
るために、文字列情報中の文字は全て１ワード（１６ビ
ット）で表されるものとする。文字出現テーブルは、文
字列情報中に同一文字コードがいくつ存在するかを表す
テーブルであり、各文字コードに対して１バイト（８ビ
ット）の出現回数を格納する領域が１対１に対応してい
る。
【００１７】以後、文字コード００００Ｈ〜ＦＦＦＦＨ
（Ｈは１６進数を意味する）の出現回数をｔ［０００
０］〜ｔ［ＦＦＦＦ］と表すものとする。ここで、出現
回数が２５５回以上の場合には、出現回数は２５５とす
る。即ちｔ［ｉ］＝２５５の場合、文字コードｉは２５
５回以上存在することを表す。図４は、文字出現テーブ
ル構築処理手順を示すフローチャートである。尚、以
下、前置きなしに幾つかの変数名が登場するが、これら
は、ＲＡＭ３の所定の領域にアサインされているものと
する。
（Ｈは１６進数を意味する）の出現回数をｔ［０００
０］〜ｔ［ＦＦＦＦ］と表すものとする。ここで、出現
回数が２５５回以上の場合には、出現回数は２５５とす
る。即ちｔ［ｉ］＝２５５の場合、文字コードｉは２５
５回以上存在することを表す。図４は、文字出現テーブ
ル構築処理手順を示すフローチャートである。尚、以
下、前置きなしに幾つかの変数名が登場するが、これら
は、ＲＡＭ３の所定の領域にアサインされているものと
する。
【００１８】ステップＳ１では、文字出現テーブルに全
て０をセットする。即ち、 ｔ［００００］〜ｔ［ＦＦＦＦ］＝０ とする。ステップＳ２では、文字列情報の文字位置を表
すカウンタｉを０に初期化する。 ステップＳ３では、
文字列情報中のｉ番目の文字ｓ［ｉ］を取得し、ｃに格
納する。
て０をセットする。即ち、 ｔ［００００］〜ｔ［ＦＦＦＦ］＝０ とする。ステップＳ２では、文字列情報の文字位置を表
すカウンタｉを０に初期化する。 ステップＳ３では、
文字列情報中のｉ番目の文字ｓ［ｉ］を取得し、ｃに格
納する。
【００１９】ステップＳ４では、文字ｃに対応する文字
出現テーブルの出現回数が２５５を越えているかチェッ
クする。越えている場合は、ステップＳ６へ進む。ま
た、越えていない場合は、テーブルの更新は行なわず、
ステップＳ５へ進む。ステップＳ５では、文字ｃに対応
する文字出現テーブルの出現回数ｔ［ｃ］に１を加算す
る。
出現テーブルの出現回数が２５５を越えているかチェッ
クする。越えている場合は、ステップＳ６へ進む。ま
た、越えていない場合は、テーブルの更新は行なわず、
ステップＳ５へ進む。ステップＳ５では、文字ｃに対応
する文字出現テーブルの出現回数ｔ［ｃ］に１を加算す
る。
【００２０】ステップＳ６では、ｓ［ｉ］が文字列情報
の最後の文字かどうかをチェックする。そして、最後の
文字であれば、処理を終了する。ステップＳ７では、カ
ウンタｉを１カウントアップして、ステップＳ３に戻
り、同様の処理を繰り返す。以上の処理により、文字列
情報中の各文字コードの出現回数がテーブルにセットさ
れる。
の最後の文字かどうかをチェックする。そして、最後の
文字であれば、処理を終了する。ステップＳ７では、カ
ウンタｉを１カウントアップして、ステップＳ３に戻
り、同様の処理を繰り返す。以上の処理により、文字列
情報中の各文字コードの出現回数がテーブルにセットさ
れる。
【００２１】そして、生成された文字出現テーブルと文
字列情報を、図２に示したように、フロッピーディスク
（ＦＤ）に保存する。次に、図５は、検索処理を示すフ
ローチャートである。ステップＳ１０では、ファイルか
ら文字出現テーブルの部分のみをＲＡＭ３に読み出す。
字列情報を、図２に示したように、フロッピーディスク
（ＦＤ）に保存する。次に、図５は、検索処理を示すフ
ローチャートである。ステップＳ１０では、ファイルか
ら文字出現テーブルの部分のみをＲＡＭ３に読み出す。
【００２２】ステップＳ１１では、文字出現テーブルｔ
を元に、検索対象文字が文字列情報中に存在するか否か
を調べる。検索対象文字列ｆはｎ文字から構成されてお
り、各構成文字コードを ｆ［ｉ］（０≦ｉ＜ｎ） とすると、 ０≦ｉ＜ｎ に対し、 ｔ［ｆ［ｉ］］≠０ であれば、文字列情報中に、検索対象文字が全て含まれ
ていることになり、ステップＳ１２に進む。
を元に、検索対象文字が文字列情報中に存在するか否か
を調べる。検索対象文字列ｆはｎ文字から構成されてお
り、各構成文字コードを ｆ［ｉ］（０≦ｉ＜ｎ） とすると、 ０≦ｉ＜ｎ に対し、 ｔ［ｆ［ｉ］］≠０ であれば、文字列情報中に、検索対象文字が全て含まれ
ていることになり、ステップＳ１２に進む。
【００２３】また、 ｔ［ｆ［ｉ］］＝０ なるｉが少なくとも１つ存在すれば、文字コードｎ
［ｉ］は、文字列情報中に存在しないので、ステップＳ
１４に進み、検索文字列が存在しない旨のメッセージを
ＣＲＴ７に表示して、そのファイルに対する検索処理は
終了する。
［ｉ］は、文字列情報中に存在しないので、ステップＳ
１４に進み、検索文字列が存在しない旨のメッセージを
ＣＲＴ７に表示して、そのファイルに対する検索処理は
終了する。
【００２４】ステップＳ１２では、文字出現テーブルに
続く文字列情報部分をＲＡＭ３に読み込む。ステップＳ
１３では、ＲＡＭ３に読み込まれた文字列に基づき、文
字列検索処理を行う。ステップＳ１５では、検索された
結果をＣＲＴ３に表示して、処理を終了する。
続く文字列情報部分をＲＡＭ３に読み込む。ステップＳ
１３では、ＲＡＭ３に読み込まれた文字列に基づき、文
字列検索処理を行う。ステップＳ１５では、検索された
結果をＣＲＴ３に表示して、処理を終了する。
【００２５】以下に、ステップＳ１３の文字列検索の詳
細処理を示す。はじめに、検索対象文字列の比較順序の
設定を行う。比較対象文字列ｆの各文字コード ｆ［０］〜ｆ［ｎ−１］ に対する出現回数 ｔ［ｆ［０］］〜ｔ［ｆ−１］］ において、出現回数の少ない順に並べ換えた文字列ｆ’
を作成する。即ち、 ｔ［ｆ'［０］≦ … ≦ｔ［ｆ'［ｎ−１］］ となる。この時、ｆ'［０］の位置を０とした時の文字
列ｆでの相対位置を表す比較位置列ｐも作成する。
細処理を示す。はじめに、検索対象文字列の比較順序の
設定を行う。比較対象文字列ｆの各文字コード ｆ［０］〜ｆ［ｎ−１］ に対する出現回数 ｔ［ｆ［０］］〜ｔ［ｆ−１］］ において、出現回数の少ない順に並べ換えた文字列ｆ’
を作成する。即ち、 ｔ［ｆ'［０］≦ … ≦ｔ［ｆ'［ｎ−１］］ となる。この時、ｆ'［０］の位置を０とした時の文字
列ｆでの相対位置を表す比較位置列ｐも作成する。
【００２６】以下に一例を示す。 ｆ＝（ａ，ｂ，ｃ） のとき、 ｔ［ａ］＝２，ｔ［ｂ］＝６，ｔ［ｃ］＝１ であれば、 ｆ'＝（ｃ，ａ，ｂ） である。このときの比較位置列ｐは、 ｐ［０］＝０，ｐ［１］＝−２，ｐ［２］＝−１ となる。
【００２７】次に、文字列情報ｓから順次１文字を取得
しｆ'［０］と比較する。一致した場合、順次ｆ'
［１］，ｆ'［２］…と比較を行う。但し、比較位置は
比較位置列を元に行う。即ち、 ｆ'［０］＝ｓ［ｉ］ ならば、 ｆ'［ｊ］＝ｓ［ｉ＋ｐ［ｊ］］（０＜ｊ＜ｎ） の比較を行う。前記例では、 ｆ'［０］（ｃ）＝ｓ［ｉ］ ならば、 ｆ'［１］（ａ） と、 ｓ［ｉ＋ｐ［１］］（ｓ［ｉ−２］） とを比較し、一致していれば、更に、 ｆ'［２］（ｂ） と、 ｓ［ｉ＋ｐ［２］］（ｓ［ｉ−１］） とを比較する。
しｆ'［０］と比較する。一致した場合、順次ｆ'
［１］，ｆ'［２］…と比較を行う。但し、比較位置は
比較位置列を元に行う。即ち、 ｆ'［０］＝ｓ［ｉ］ ならば、 ｆ'［ｊ］＝ｓ［ｉ＋ｐ［ｊ］］（０＜ｊ＜ｎ） の比較を行う。前記例では、 ｆ'［０］（ｃ）＝ｓ［ｉ］ ならば、 ｆ'［１］（ａ） と、 ｓ［ｉ＋ｐ［１］］（ｓ［ｉ−２］） とを比較し、一致していれば、更に、 ｆ'［２］（ｂ） と、 ｓ［ｉ＋ｐ［２］］（ｓ［ｉ−１］） とを比較する。
【００２８】ｆ'［０］〜ｆ'［ｎ−１］ の全てが一致していれば、検索対象文字列ｆは、文字列
情報ｓ中に存在していたことになる。この場合、ステッ
プＳ１５に進み、検索結果の表示を行う。 ｆ'［ｉ］とｓ［ｊ］ が一致した場合、ｔ［ｓ［ｊ］］を１だけ減算する。
情報ｓ中に存在していたことになる。この場合、ステッ
プＳ１５に進み、検索結果の表示を行う。 ｆ'［ｉ］とｓ［ｊ］ が一致した場合、ｔ［ｓ［ｊ］］を１だけ減算する。
【００２９】但し、 ｔ［ｓ［ｊ］］＝２５５ の場合は減算は行わない。ｆ'［ｋ］で不一致を見た場
合、 ｔ［ｆ'［０］］〜ｔ［ｆ'［ｋ−１］］ の値を調べ、 ｔ［ｆ'［ｅ］］＝０ なる ｅ（０≦ｅ＜ｋ） が存在すれば、ｓ［ｉ］以降に文字ｆ'［ｅ］は存在し
ないことから、検索文字列は存在しないと判断し、ステ
ップＳ１４に進み、上述のメッセージを表示して、処理
を終了する。
合、 ｔ［ｆ'［０］］〜ｔ［ｆ'［ｋ−１］］ の値を調べ、 ｔ［ｆ'［ｅ］］＝０ なる ｅ（０≦ｅ＜ｋ） が存在すれば、ｓ［ｉ］以降に文字ｆ'［ｅ］は存在し
ないことから、検索文字列は存在しないと判断し、ステ
ップＳ１４に進み、上述のメッセージを表示して、処理
を終了する。
【００３０】（他の実施の形態）前記実施の形態では、
文字列の比較を文字列情報ｓから順次１文字取り出して
は比較文字列ｆ'［０］と比較する方法を取ったが、す
でに、Ｂｏｙｅｒ−Ｍｏｏｒｅ法やＫＭＰ法等の文字列
比較を高速化する為のアルゴリズムが考案されているの
で、それらのアルゴリズムを採用することも可能であ
る。
文字列の比較を文字列情報ｓから順次１文字取り出して
は比較文字列ｆ'［０］と比較する方法を取ったが、す
でに、Ｂｏｙｅｒ−Ｍｏｏｒｅ法やＫＭＰ法等の文字列
比較を高速化する為のアルゴリズムが考案されているの
で、それらのアルゴリズムを採用することも可能であ
る。
【００３１】また、前記実施の形態では、無条件に文字
出現テーブルを構築し、ファイルに付加したが、元の文
字列情報が少ない場合、文字出現テーブルの存在によっ
て、記憶装置へのアクセス時間が大きくなり、検索時間
が長くなる可能性がある。そこで、文字列情報が一定以
上の大きさの時のみ、文字出現テーブルを付加すること
も可能である。
出現テーブルを構築し、ファイルに付加したが、元の文
字列情報が少ない場合、文字出現テーブルの存在によっ
て、記憶装置へのアクセス時間が大きくなり、検索時間
が長くなる可能性がある。そこで、文字列情報が一定以
上の大きさの時のみ、文字出現テーブルを付加すること
も可能である。
【００３２】本実施の形態では、一文字毎の出現テーブ
ルを作成したが、２文字以上の組による出現テーブルを
作成することも可能である。例えば、英字の場合、ａ
ａ，ａｂ，．．．，ｚｚの２文字の出現テーブルを作成
しておけば、より高速な検索が可能である。なお、本発
明は、複数の機器から構成されるシステムに適用して
も、一つの機器からなる装置に適用してもよい。
ルを作成したが、２文字以上の組による出現テーブルを
作成することも可能である。例えば、英字の場合、ａ
ａ，ａｂ，．．．，ｚｚの２文字の出現テーブルを作成
しておけば、より高速な検索が可能である。なお、本発
明は、複数の機器から構成されるシステムに適用して
も、一つの機器からなる装置に適用してもよい。
【００３３】また、本発明の目的は、前述した実施形態
の機能を実現するソフトウェアのプログラムコードを記
録した記憶媒体を、システムあるいは装置に供給し、そ
のシステムあるいは装置のコンピュータ（またはＣＰＵ
やＭＰＵ）が記憶媒体に格納されたプログラムコードを
読出し実行することによっても、達成されることは言う
までもない。
の機能を実現するソフトウェアのプログラムコードを記
録した記憶媒体を、システムあるいは装置に供給し、そ
のシステムあるいは装置のコンピュータ（またはＣＰＵ
やＭＰＵ）が記憶媒体に格納されたプログラムコードを
読出し実行することによっても、達成されることは言う
までもない。
【００３４】この場合、記憶媒体から読出されたプログ
ラムコード自体が前述した実施形態の機能を実現するこ
とになり、そのプログラムコードを記憶した記憶媒体は
本発明を構成することになる。プログラムコードを供給
するための記憶媒体としては、例えば、フロッピディス
ク，ハードディスク，光ディスク，光磁気ディスク，Ｃ
Ｄ−ＲＯＭ，ＣＤ−Ｒ，磁気テープ，不揮発性のメモリ
カード，ＲＯＭなどを用いることができる。
ラムコード自体が前述した実施形態の機能を実現するこ
とになり、そのプログラムコードを記憶した記憶媒体は
本発明を構成することになる。プログラムコードを供給
するための記憶媒体としては、例えば、フロッピディス
ク，ハードディスク，光ディスク，光磁気ディスク，Ｃ
Ｄ−ＲＯＭ，ＣＤ−Ｒ，磁気テープ，不揮発性のメモリ
カード，ＲＯＭなどを用いることができる。
【００３５】また、コンピュータが読出したプログラム
コードを実行することにより、前述した実施形態の機能
が実現されるだけでなく、そのプログラムコードの指示
に基づき、コンピュータ上で稼働しているＯＳ（オペレ
ーティングシステム）などが実際の処理の一部または全
部を行い、その処理によって前述した実施形態の機能が
実現される場合も含まれることは言うまでもない。
コードを実行することにより、前述した実施形態の機能
が実現されるだけでなく、そのプログラムコードの指示
に基づき、コンピュータ上で稼働しているＯＳ（オペレ
ーティングシステム）などが実際の処理の一部または全
部を行い、その処理によって前述した実施形態の機能が
実現される場合も含まれることは言うまでもない。
【００３６】さらに、記憶媒体から読出されたプログラ
ムコードが、コンピュータに挿入された機能拡張ボード
やコンピュータに接続された機能拡張ユニットに備わる
メモリに書込まれた後、そのプログラムコードの指示に
基づき、その機能拡張ボードや機能拡張ユニットに備わ
るＣＰＵなどが実際の処理の一部または全部を行い、そ
の処理によって前述した実施形態の機能が実現される場
合も含まれることは言うまでもない。
ムコードが、コンピュータに挿入された機能拡張ボード
やコンピュータに接続された機能拡張ユニットに備わる
メモリに書込まれた後、そのプログラムコードの指示に
基づき、その機能拡張ボードや機能拡張ユニットに備わ
るＣＰＵなどが実際の処理の一部または全部を行い、そ
の処理によって前述した実施形態の機能が実現される場
合も含まれることは言うまでもない。
【００３７】本発明を上記記憶媒体に適用する場合、そ
の記憶媒体には、先に説明したフローチャートに対応す
るプログラムコードを格納することになるが、簡単に説
明すると、図６のメモリマップ例に示す各モジュールを
記憶媒体に格納することになる。すなわち、少なくと
も、図４のフローチャートの処理手順に対応するプログ
ラムモジュールである「文字出現テーブル生成モジュー
ル」、所定の文字列の含む文字を含むかどうか検索する
ステップＳ１０、Ｓ１１の処理に対応する「文字出現テ
ーブル検索モジュール」、ステップＳ１２、Ｓ１３の処
理に対応する「文字列検索モジュール」、Ｓ１４、Ｓ１
５での処理結果を表示する処理モジュールである「検索
結果表示モジュール」の各モジュールのプログラムコー
ドを記憶媒体に格納すればよい。
の記憶媒体には、先に説明したフローチャートに対応す
るプログラムコードを格納することになるが、簡単に説
明すると、図６のメモリマップ例に示す各モジュールを
記憶媒体に格納することになる。すなわち、少なくと
も、図４のフローチャートの処理手順に対応するプログ
ラムモジュールである「文字出現テーブル生成モジュー
ル」、所定の文字列の含む文字を含むかどうか検索する
ステップＳ１０、Ｓ１１の処理に対応する「文字出現テ
ーブル検索モジュール」、ステップＳ１２、Ｓ１３の処
理に対応する「文字列検索モジュール」、Ｓ１４、Ｓ１
５での処理結果を表示する処理モジュールである「検索
結果表示モジュール」の各モジュールのプログラムコー
ドを記憶媒体に格納すればよい。
【００３８】以上説明した様に、本実施の形態によれ
ば、検索対象文字列長がｎの場合、文字出現テーブルに
対し、ｎ回の比較で文字列情報中に対象文字が存在する
か否かの判断ができる。また、ある検索対象文字の出現
回数がｍの場合、文字列情報中にその文字がｍ回出現し
たことを検知した時点で、検索を中止できる。
ば、検索対象文字列長がｎの場合、文字出現テーブルに
対し、ｎ回の比較で文字列情報中に対象文字が存在する
か否かの判断ができる。また、ある検索対象文字の出現
回数がｍの場合、文字列情報中にその文字がｍ回出現し
たことを検知した時点で、検索を中止できる。
【００３９】さらに、検索対象文字列中で出現回数の一
番少ない文字を優先的に比較し、出現回数をチェックで
きる。そのため、特別な装置を必要とせずに高速な文字
列検索が可能となる。
番少ない文字を優先的に比較し、出現回数をチェックで
きる。そのため、特別な装置を必要とせずに高速な文字
列検索が可能となる。
【００４０】
【発明の効果】以上説明したように本発明によれば、文
字列を高速に検索できる。
字列を高速に検索できる。
【図１】本発明の一実施の形態を示すブロック構成図で
ある。
ある。
【図２】文字出現テーブルを含むファイル形式の概略で
ある。
ある。
【図３】文字出現テーブルの詳細図である。
【図４】文字出現テーブルの構築方法の一例を示すフロ
ーチャートである。
ーチャートである。
【図５】検索処理の一例を示すフローチャートである。
【図６】文字出現テーブルの構築処理、検索処理を実現
する各プログラムモジュールの記録媒体上のレイアウト
例を示す図である。
する各プログラムモジュールの記録媒体上のレイアウト
例を示す図である。
Claims (9)
- 【請求項１】 文字列情報に含まれる各文字と前記各文
字の発生頻度を備えるテーブルを検索して、所定の文字
列に含まれる全ての文字が前記テーブルに存在している
かどうか検索する第１の検索工程と、 前記第１の検索工程で、所定の文字列に含まれる全ての
文字が前記テーブルに存在していると判定された場合、
前記文字列情報を検索して、前記所定の文字列に一致す
る文字列があるかどうかを検索する第２の検索工程とを
備えることを特徴とする文字列検索方法。 - 【請求項２】 前記第２の検索工程は、前記第１の検索
工程で、所定の文字列に含まれる全ての文字が前記テー
ブルに存在していると判定された場合、前記所定の文字
列に含まれる文字のうち発生頻度のより発生頻度の低い
文字から順に、前記文字列情報を検索して、前記所定の
文字列に一致する文字列があるかどうかを検索すること
を特徴とする請求項１に記載の文字列検索方法。 - 【請求項３】 文字列情報に含まれる各文字の発生数を
カウントして、前記各文字と対応する発生頻度を備える
テーブルを生成するテーブル生成工程と、 前記テーブル生成工程で生成されたテーブルと前記文字
列情報を関連づけて格納する格納工程とを備えることを
特徴とする文字列検索情報生成方法。 - 【請求項４】 文字列情報に含まれる各文字と前記各文
字の発生頻度を備えるテーブルを検索して、所定の文字
列に含まれる全ての文字が前記テーブルに存在している
かどうか検索する第１の検索手段と、 前記第１の検索手段で、所定の文字列に含まれる全ての
文字が前記テーブルに存在していると判定された場合、
前記文字列情報を検索して、前記所定の文字列に一致す
る文字列があるかどうかを検索する第２の検索手段とを
備えることを特徴とする文字列検索装置。 - 【請求項５】 前記第２の検索手段は、前記第１の検索
手段で、所定の文字列に含まれる全ての文字が前記テー
ブルに存在していると判定された場合、前記所定の文字
列に含まれる文字のうち発生頻度のより発生頻度の低い
文字から順に、前記文字列情報を検索して、前記所定の
文字列に一致する文字列があるかどうかを検索すること
を特徴とする請求項４に記載の文字列検索装置。 - 【請求項６】 文字列情報に含まれる各文字の発生数を
カウントして、前記各文字と対応する発生頻度を備える
テーブルを生成するテーブル生成手段と、 前記テーブル生成手段で生成されたテーブルと前記文字
列情報を関連づけて格納する格納手段とを備えることを
特徴とする文字列検索情報生成装置。 - 【請求項７】 コンピュータプログラム製品であって、
文字列情報から所定の文字列を検索する、コンピュータ
読み取り可能なプログラムコード手段を有するコンピュ
ータ使用可能な媒体を備え、前記コンピュータプログラ
ム製品は、 文字列情報に含まれる各文字と前記各文字の発生頻度を
備えるテーブルを検索して、所定の文字列に含まれる全
ての文字が前記テーブルに存在しているかどうか検索す
る、第１のコンピュータ読み取り可能なプログラムコー
ド手段と、 前記第１のコンピュータ読み取り可能なプログラムコー
ド手段で、所定の文字列に含まれる全ての文字が前記テ
ーブルに存在していると判定された場合、前記文字列情
報を検索して、前記所定の文字列に一致する文字列があ
るかどうかを検索する第２のコンピュータ読み取り可能
なプログラムコード手段とを備えることを特徴とする。 - 【請求項８】 コンピュータプログラム製品であって、
文字列情報に基づいて、所定の文字列の検索に適した構
造の情報を生成する、コンピュータ読み取り可能なプロ
グラムコード手段を有するコンピュータ使用可能な媒体
を備え、前記コンピュータプログラム製品は、 文字列情報に含まれる各文字の発生数をカウントして、
前記各文字と対応する発生頻度を備えるテーブルを生成
する第１のコンピュータ読み取り可能なプログラムコー
ド手段と、 前記テーブル生成工程で生成されたテーブルと前記文字
列情報を関連づけて格納する、第２のコンピュータ読み
取り可能なプログラムコード手段とを備えることを特徴
とする。 - 【請求項９】 前記第２の検索工程は、前記第１の検索
工程で、所定の文字列に含まれる全ての文字が前記テー
ブルに存在していると判定された場合、前記所定の文字
列に含まれる文字のうち発生頻度のより発生頻度の低い
文字から順に、前記文字列情報を検索して、文字が一致
する毎に前記文字に対応する前記テーブル値を１減ら
し、 次の検索文字の２文字目以後で不一致となると、前記検
索文字列に対応する前記テーブルの中の１つでもゼロに
なっていれば検索を中止することを特徴とする請求項２
に記載の文字列検索方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP11368496A JP3847836B2 (ja) | 1996-05-08 | 1996-05-08 | 文字列検索方法とその装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP11368496A JP3847836B2 (ja) | 1996-05-08 | 1996-05-08 | 文字列検索方法とその装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH09297771A true JPH09297771A (ja) | 1997-11-18 |
| JP3847836B2 JP3847836B2 (ja) | 2006-11-22 |
Family
ID=14618564
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP11368496A Expired - Fee Related JP3847836B2 (ja) | 1996-05-08 | 1996-05-08 | 文字列検索方法とその装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3847836B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2016095639A (ja) * | 2014-11-13 | 2016-05-26 | 日本電気株式会社 | データベース装置、データ管理方法、及びプログラム |
-
1996
- 1996-05-08 JP JP11368496A patent/JP3847836B2/ja not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2016095639A (ja) * | 2014-11-13 | 2016-05-26 | 日本電気株式会社 | データベース装置、データ管理方法、及びプログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3847836B2 (ja) | 2006-11-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US8190613B2 (en) | System, method and program for creating index for database | |
| US5261087A (en) | Electronic information retrieval system with relative difference analyzer | |
| JPH11224258A (ja) | 画像検索装置及びその方法、コンピュータ可読メモリ | |
| US4688189A (en) | Electronic equipment for storing number of searches of information | |
| JP3847836B2 (ja) | 文字列検索方法とその装置 | |
| JPH05101102A (ja) | 検索装置 | |
| JP3665112B2 (ja) | 文字列検索方法及び装置 | |
| JP2817103B2 (ja) | データ検索装置及びデータ検索方法 | |
| JPH05113964A (ja) | 電子辞書 | |
| JP3596696B2 (ja) | 情報検索装置 | |
| JP3019286B2 (ja) | 文書検索装置 | |
| JPH07225761A (ja) | 文書データの一致検証方式 | |
| JPH05181719A (ja) | 可変長データの格納および参照システム | |
| JP3325326B2 (ja) | 電子ファイリング装置 | |
| JP3585944B2 (ja) | データ処理方法及びその装置 | |
| JP4139805B2 (ja) | 字句をデータに変換する装置、方法及びプログラム | |
| JPH06162096A (ja) | レコード検索方法 | |
| JPH0721182A (ja) | 文字処理装置およびその方法 | |
| JP3896683B2 (ja) | 使用者定義文字管理装置および記憶媒体 | |
| JP3272536B2 (ja) | 仮名漢字変換方法 | |
| JPH03110674A (ja) | 電子辞書 | |
| JPH0528194A (ja) | データアクセス方式 | |
| JPH0375960A (ja) | 文字処理装置の頻度変更方式 | |
| JPH0531191B2 (ja) | ||
| JPH05233687A (ja) | 電子辞書 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20060403 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20060519 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20060714 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20060814 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20060824 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090901 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100901 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110901 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110901 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120901 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120901 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130901 Year of fee payment: 7 |
|
| LAPS | Cancellation because of no payment of annual fees |