JPH08272814A - 文字列検索装置 - Google Patents

Abstract

(57)【要約】 【目的】 検索時間を短縮し、辞書ファイルの使用メモ
リ量も少なくてすむ文字列検索装置を提供する。 【構成】 辞書検索用ファイル（辞書ファイル）７０は
ディレクトリブロック７１０、複数の文字列ブロック７
２０、ＥＯＦブロック７３０から構成される。ディレク
トリブロック７１０には各文字列ブロックの先頭アドレ
スが格納されており、該ブロックは文字列の先頭の種類
と文字数で関係づけられている。各文字列ブロック７２
０には実際の文字列が格納される。ＥＯＦブロック７３
０はファイルの最後を表わす。入力文字列の文字数と先
頭文字の種類により、ディレクトリブロック７１０から
該当文字列ブロックのアドレスを取得し、該アドレスに
より該当文字列ブロック７２０の文字列群を読み込んで
検索する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は文字列検索装置に係り、
具体的には、図書や論文等の文字列検索、コードや品番
等の検索に有効な文字列検索装置に関する。

【０００２】

【従来の技術】従来の文字列検索装置では、キー指定し
て、キー値と一致したものをサーチする方式が一般的で
ある。図５に、この種の文字列検索装置に用いられる辞
書ファイルの構成例を示す。例えば「コマツ」という文
字列を検索すると次のようになる。まず、入力文字列
「コマツ」を元にインデックス部より該当するキー値
（文字数が「３」で、先頭文字が「カ」行）をサーチ
し、次に該当するキー値を元にデータ部をサーチし、文
字列「コマツ」の有無を検索する。

【０００３】

【発明が解決しようとする課題】上記従来技術では、２
段階のサーチ（インデックス部とデータ部）を行う必要
があるため、検索回数が多くなると非常に時間がかか
り、効率が悪くなるという問題がある。例えば、辞書フ
ァイルに既に同じ名前が登録されているかどうかを検索
するような場合にも、２段階のサーチを行うため、検索
に時間がかかっていた。また、データ部にもキー値を持
たないと検索ができないため、データ（文字列）が多く
なればなるほど、使用メモリ量が多くなるという問題も
ある。

【０００４】本発明の目的は、従来技術に比べて、検索
時間が短縮でき、かつ、辞書ファイルの使用メモリ量も
少なくできる文字列検索装置を提供することにある。

【０００５】

【課題を解決するための手段】本発明の文字列検索装置
は、辞書ファイルとして、文字列の内容を文字数と先頭
の文字の内容の組み合せによって分類し、各ブロック単
位にその文字列を格納した複数の文字列ブロックと、前
記文字列ブロックの存在するアドレスを登録したディレ
クトリブロックとで構成し、前記入力文字列の文字数と
先頭の文字により前記ディレクトリブロックから該当文
字列ブロックのアドレスを取得し、該アドレスにより該
当文字列ブロックの文字列を読み込み、前記入力文字列
と一致あるいは類似する文字列を検索する手段を有する
ようにしたことを特徴とするものである。

【０００６】

【作用】入力文字列の文字数とその先頭文字により、デ
ィレクトリブロックから該当文字列ブロックの存在する
アドレスが直接取得できる。このアドレスで該当文字列
ブロックのデータ（文字列群）を読み込み、入力文字列
と一致あるいは類似するものがあるか検索する。これに
より、検索回数は文字列ブロックの文字列群に対する１
度で済み、また、データはブロック単位で読み込むこと
ができるのでアクセス回数も少なく検索時間を短縮出来
る。またインデックス部をディレクトリブロックとして
１ブロックで管理し、データ部は文字列のみを格納する
ためメモリも最小限の領域で済む。

【０００７】

【実施例】以下、本発明の一実施例について図面により
説明する。

【０００８】図１は、本発明の文字列検索装置の一実施
例の全体構成図である。本システムは、検索する入力文
字列や検索結果を表示するディスプレィ１０、検索する
文字列やコマンド等を入力するキーボード２０、検索結
果を出力するプリンタ３０、検索する文字列が格納され
ている入力ファイル４０、辞書登録する文字列が格納さ
れている辞書入力ファイル５０、入力ファイル４０から
作成された検索用文字列が格納される入力検索用ファイ
ル６０、辞書入力ファイル５０から作成された検索用辞
書が格納される辞書検索用ファイル７０、処理途中ファ
イルや処理結果ファイルなどを格納する補助記憶装置８
０、及び、展開文字列の作成、コード化、検索、編集な
どの処理を行うＣＰＵ（中央処理装置）１００からな
る。ここで、入力ファイル４０および辞書入力ファイル
５０は順編成（ＳＡＭ）ファイルであり、磁気テープま
たは磁気ディスクからなる。入力検索用ファイル６０及
び辞書検索用ファイル７０は直接アクセス（ＤＡＭ）フ
ァイルである。プリンタ３０には例えば漢字プリンタを
用いる。

【０００９】図２はＣＰＵ１００の全体的動作の流れを
示すフロー図である。入力ファイル４０及び辞書入力フ
ァイル５０はＳＡＭファイルである。これらのファイル
４０、５０をもとに展開文字列を作成し、その文字列を
コード化する（ステップ１１０、２１０）。この内容を
出力したものが、展開済入力ファイル１２０及び展開済
辞書ファイル２２０であり、これらのファイルもＳＡＭ
ファイルである。次に、これらの展開済ファイル１２
０、２２０の中に同一の文字列が存在した場合、これら
を一つにし、入力検索用ファイル６０、辞書検索用ファ
イル７０を作成する（ステップ１３０、２３０）。これ
らのファイル６０、７０はＤＡＭファイルである。この
入力検索用ファイル６０を対象に、辞書検索用ファイル
７０を参照して文字列を検索する（ステップ１４０）。
これについては、後で詳述する。入力検索結果ファイル
１５０及び辞書検索結果ファイル２５０は検索結果を出
力したものであり、入力検索結果ファイル１５０には入
力ファイル４０より抽出した文字列の全情報及び辞書入
力ファイル５０のどの文字列と類似したか、また類似し
ながったかといった情報が格納される。また、辞書検索
結果ファイル２５０は類似した文字列が格納される。こ
れらの検索結果ファイル１５０、２５０をもとに統合編
集して、検索結果リスト１７０を作成する（ステップ１
６０）。この統合編集処理では文字列以外の情報は最初
の入力である入力ファイル４０及び辞書入力ファイル５
０から情報を取得する。これは、文字列の検索時は文字
列データだけで膨大な量のデータとなるため、検索時に
余計なデータをファイル上に持たないためである。作成
された検索結果リスト１７０は、ディスプレィ１０やプ
リンタ３０に出力する。

【００１０】なお、辞書検索用ファイル７０が既に用意
されており、検索する文字列がキーボード２０から入力
される場合には、ステップ１４０において、直接、この
入力された文字列について、辞書検索用ファイル７０を
参照して検索を実行すればよい。

【００１１】図３に辞書検索用ファイル７０の構成例を
示す。辞書検索用ファイル７０はディレクトリブロック
７１０、複数の文字列ブロック７２０、及びＥＯＦブロ
ック７３０から構成される。ディレクトリブロック７１
０は、文字列（データ）の内容を文字数と先頭の文字の
内容の組合せによって分類して複数のブロック（文字列
ブロック）に分け、そのブロックの存在するアドレスを
格納したものである。このディレクトリブロック７１０
がインデックスの役割を果たす。図３では、該ディレク
トリブロック７１０は、文字列の先頭の文字を「ア
行」、「カ行」…に分け、文字数ごとに、各文字列ブロ
ックの先頭アドレスを格納したものである。各文字列ブ
ロック７２０には実際の文字列が格納され、ＥＯＦブロ
ック７３０はファイルの最後を表すものである。尚、図
３の実施例では、分かりやすいように文字列が日本語で
示されているが、実際には文字列はコードで扱われる。

【００１２】次に、図３の辞書検索用ファイル７０を使
用して、実際にどのように文字列検索が行われるかを、
入力文字列が「コマツ」の場合を例に説明する。この場
合の処理フローを図４に示す。

【００１３】入力文字列が「コマツ」の場合、まず、デ
ィレクトリブロック８１０より、カ行で文字数が３音の
文字列ブロックの先頭アドレス“０１０３”を取得する
（ステップ８１０）。次に、該アドレス“０１０３”の
文字列ブロックからデータ（文字列）を読み込み（ステ
ップ８２０）、該ブロックの文字列を順に検索する（ス
テップ８３０）。そして、入力文字列「コマツ」に一致
・類似する文字列があるか判定し（ステップ８４０）、
あれば、検索結果を出力して（ステップ８５０）、次の
文字列の検索に行き（ステップ８６０）、なければ、ス
テップ８５０をスキップする。なお、各文字列ブロック
の最後には次のブロックに続きがあるかを示すフラグを
つけておき、そのフラグをみて次のブロックも検索する
か判断する。

【００１４】

【発明の効果】以上説明したように、本発明の文字列検
索装置によれば、検索回数は辞書ファイルの文字列ブロ
ック中のデータの１度で済み、また、データはブロック
単位で読み込むことができるのでアクセス回数も少な
く、検索時間を短縮出来る。さらにインデックス部をデ
ィレクトリブロックの１ブロックで管理し、データ部は
文字列ブロックで文字列のみを格納するため，メモリも
最小限の領域で済む。従って、本発明の文字列検索装置
は、特に、検索回数が多く、データ量の多い検索対象に
向いている。

【図面の簡単な説明】

【図１】本発明の文字列検索装置の一実施例の全体構成
図である。

【図２】図１の全体的動作の流れを示すフロー図であ
る。

【図３】本発明による辞書検索用ファイルの構成例を示
す図である。

【図４】本発明による文字列検索の具体的処理例を示す
フロー図である。

【図５】従来の文字列検索処理を説明する図である。

【符号の説明】

１０ ディスプレィ ２０ キーボード ３０ プリンタ ４０ 入力ファイル ５０ 辞書入力ファイル ６０ 入力検索用ファイル ７０ 辞書検索用ファイル ７１０ ディレクトリブロック ７２０ 文字列ブロック １００ ＣＰＵ

Claims (1)

【特許請求の範囲】
1. 【請求項１】 入力文字列と一致あるいは類似した文字
   列を辞書ファイルより検索する文字列検索装置におい
   て、 前記辞書ファイルを、文字列の内容を文字数と先頭の文
   字の内容の組み合せによって分類し、各ブロック単位に
   その文字列を格納した複数の文字列ブロックと、前記文
   字列ブロックの存在するアドレスを登録したディレクト
   リブロックとで構成し、 前記入力文字列の文字数と先頭の文字により前記ディレ
   クトリブロックから該当文字列ブロックのアドレスを取
   得し、該アドレスにより該当文字列ブロックの文字列を
   読み込み、前記入力文字列と一致あるいは類似する文字
   列を検索する手段を有することを特徴とする文字列検索
   装置。