JPH05334355A - 任意一致検索方式 - Google Patents

Abstract

(57)【要約】 【目的】 任意一致検索に於ける検索時間を短縮させ
る。 【構成】 索引語抽出処理手段４１はデータベースを構
成する各レコードＲ１〜Ｒｎの索引語から任意一致検索
キー（索引語の各文字を先頭文字とする後方の文字列）
を抽出すると共に、抽出した任意一致検索キーとレコー
ドキーとの対応付けを行ない、ソート処理手段４２は索
引語抽出処理手段４１が抽出したレコードキーとの対応
付けが行なわれた任意一致検索キーをソートし、マージ
処理手段４３はソートされた任意一致検索キーの前方一
致するもの同士を１つの任意一致検索キーにマージする
ことにより、任意一致検索インデックス２を作成する。
サーチ手段１は任意一致検索語が入力されることによ
り、任意一致検索インデックス２をバイナリサーチし、
入力された任意一致検索語と前方一致する任意一致検索
キーを探し出し、探し出した任意一致検索キーと対応す
るレコードキーを出力する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はデータベース検索に関
し、特に任意一致検索を高速に行なうことができる任意
一致検索方式に関する。

【０００２】

【従来の技術】コンピュータの普及に伴ってデータベー
スの利用があらゆる分野に浸透しつつある。しかし、デ
ータ量の増大に伴い、データの検索時間の増加が問題と
なってきている。特に、任意一致検索に於いては、従来
は全文字列サーチ処理が必要になるため、多くの検索時
間が必要であった。

【０００３】図６，図７は従来の検索方式を説明するた
めの図であり、以下各図を参照して従来の検索方式を説
明する。

【０００４】図６は検索対象となるデータベースの構成
例を示した図であり、このデータベースは５個のレコー
ドＲ１〜Ｒ５から構成されている。

【０００５】各レコードＲ１〜Ｒ５はそれぞれ索引語５
１と、属性の組（ａ１，ａ２，…，ａｍ）５２と、レコ
ードキー５３とから構成されている。

【０００６】レコードキー５３は属性値に対する論理演
算処理やレコードの更新を行なう時に用いられる見出し
であり、レコードと１対１に対応している。この例の場
合、各レコードＲ１〜Ｒ５にはレコードキー５３として
ＤＢＫ−１〜ＤＢＫ−５が与えられている。

【０００７】また、索引語５１はデータベース利用者と
のインタフェースを円滑にするために設けられているキ
ーワードである。この例の場合、レコードＲ１，Ｒ２，
Ｒ３，Ｒ４，Ｒ５にはそれぞれ「アイウエオ」，「イウ
エ」，「カキウエオ」，「キウエ」，「サシス」が索引
語５１として与えられている。尚、ここでは説明を簡単
にするために、各レコードに索引語が１つしかないとし
たが、一般的には１つのレコードには複数の索引語が存
在するものである。また、この例では各レコードＲ１〜
Ｒ５の索引語は全て異なっているが、異なるレコードが
同じ索引語を持つ場合もある。

【０００８】図７は図６に示したデータベースの検索を
行なう場合に従来使用していたインデックスの構成例を
示した図であり、索引語６１と、レコードキー６２とか
ら構成されている。

【０００９】索引語６１には図６に示したデータベース
中の各レコードＲ１，Ｒ２，Ｒ３，Ｒ４，Ｒ５の索引語
「アイウエオ」，「イウエ」，「カキウエオ」，「キウ
エ」，「サシス」が完全な形で格納されている。また、
レコードキー６２には各レコードＲ１，Ｒ２，Ｒ３，Ｒ
４，Ｒ５のレコードキーＤＢＫ−１，ＤＢＫ−２，ＤＢ
Ｋ−３，ＤＢＫ−４，ＤＢＫ−５が索引語「アイウエ
オ」，「イウエ」，「カキウエオ」，「キウエ」，「サ
シス」に対応して格納されている。尚、インデックス中
の索引語６１は通常、昇順にソートされているものであ
り、図７に示すように、索引語が数字以外の文字列であ
る場合は、例えば５０音順にソートされる。

【００１０】次に、図６，図７を参照して従来の検索方
式について説明する。

【００１１】先ず、前方一致検索を行なう場合の動作を
説明する。

【００１２】前方一致検索は検索語が先頭部分に存在す
る索引語を検索対象とするものであり、検索語「カキウ
エオ」が指定されたとすると、図７のインデックスの検
索語６１の欄をサーチして検索語「カキウエオ」を探
し、それに対応してレコードキー６２の欄に格納されて
いるレコードキー「ＤＢＫ−３」を取得する。その後、
図６に示したデータベース中のレコードＲ１〜Ｒ５から
上記レコードキー「ＤＢＫ−３」を有するレコードＲ３
を選択する。ここで、図７のインデックスの索引文字は
昇順にソートされているので、バイナリサーチを行なう
ことにより、サーチ時間を大幅に短縮することが可能に
なる。

【００１３】次に、任意一致検索を行なう場合の動作を
説明する。

【００１４】任意一致検索は検索語を任意の部分に含む
索引語を全て検索対象とするものであり、例えば、検索
語「ギジュツ」で任意一致検索を行なう場合、「ギジュ
ツ」を含む「コウクウギジュツカイハツ」，「ドボクギ
ジュツカイハツ」等の索引語が全て検索の対象となる。

【００１５】今、例えば、任意一致検索を行なう検索語
として「ウエオ」が指定されたとすると、図５のインデ
ックスの索引語６１の欄をサーチして、任意の位置に指
定された検索語「ウエオ」が含む検索語を全て探し出
す。ここで、索引語６１は完全な文字列についてソート
されているので、索引語の任意の部分に含まれている検
索語を探し出すにはバイナリサーチを適用することがで
きない。従って、任意一致検索を行なう場合、従来はイ
ンデックスの端から全サーチを行ない、索引語が「アイ
ウエオ」のレコードキー「ＤＢＫ−１」と、索引語が
「カキウエオ」のレコードキー「ＤＢＫ−３」とを探し
出すことが必要であった。

【００１６】

【発明が解決しようとする課題】上述したように、従来
のインデックスは前方一致検索を念頭において作られて
おり、任意一致検索を行なう場合にはバイナリサーチを
行なうことができないため、索引語数が数１０万から数
１００万にもなる実用データベースに於いて任意一致検
索を行なう場合、検索時間が非常に長くなるという問題
があった。

【００１７】本発明の目的は、任意一致検索に於ける検
索時間を大幅に短縮させることができる任意一致検索方
式を提供することにある。

【００１８】

【課題を解決するための手段】本発明は上記目的を達成
するため、（Ａ）索引語を有する複数のレコードから構
成されるデータベースと、前記各索引語から索引語中の
各文字を先頭文字とする後方の文字列を任意一致検索キ
ーとして抽出し、抽出した任意一致検索キーとそれを抽
出した索引語を含んでいるレコードのレコードキーとの
対応付けを行なう索引語抽出処理手段と、該索引語抽出
処理手段で抽出され、レコードキーとの対応付けが行な
われた任意一致検索キーをソートすることにより、前記
レコードキーとの対応付けが行なわれた任意一致検索キ
ーが所定の順序で並んだ任意一致検索インデックスを作
成するソート処理手段と、任意一致検索語が入力される
ことにより、前記任意一致検索インデックスをバイナリ
サーチし、前記任意一致検索語と前方一致する任意一致
検索キーを探し出し、探し出した任意一致検索キーに対
応するレコードキーを出力するサーチ手段とを設けたも
のである。

【００１９】また、本発明は更に検索時間を短縮させる
ために、（Ｂ）索引語を有する複数のレコードから構成
されるデータベースと、前記各索引語から索引語中の各
文字を先頭文字とする後方の文字列を任意一致検索キー
として抽出し、抽出した任意一致検索キーとそれを抽出
した索引語を含んでいるレコードのレコードキーとの対
応付けを行なう索引語抽出処理手段と、該索引語抽出処
理手段で抽出され、レコードキーとの対応付けが行なわ
れた任意一致検索キーをソートすることにより、前記レ
コードキーとの対応付けが行なわれた任意一致検索キー
が所定の順序で並んだ集合を作成するソート処理手段
と、該ソート処理手段で作成された集合に含まれている
任意一致検索キーの内、前方一致する任意一致検索キー
同士をマージすることにより、前記レコードキーとの対
応付けが行なわれたマージされた任意一致検索キー及び
マージされなかった任意一致検索キーが所定の順序で並
んだ任意一致検索インデックスを作成するマージ処理手
段と、任意一致検索語が入力されることにより、前記任
意一致検索インデックスをバイナリサーチし、前記任意
一致検索語と前方一致する任意一致検索キーを探し出
し、探し出した任意一致検索キーに対応するレコードキ
ーを出力するサーチ手段とを設けたものである。

【００２０】

【作用】（Ａ）の構成に於いては、索引語抽出処理手段
によって各索引語から索引語中の各文字を先頭文字とす
る後方の文字列が任意一致検索キーとして抽出され、且
つ抽出した任意一致検索キーとレコードキーとの対応付
けが行なわれる。

【００２１】更に、ソート処理手段に於いて索引語抽出
処理手段で抽出され、レコードキーとの対応付けが行な
われた任意一致検索キーのソートが行なわれ、レコード
キーとの対応付けが行なわれた任意一致検索キーが所定
の順序で並んだ任意一致検索インデックスが作成され
る。

【００２２】サーチ手段は任意一致検索語が入力される
と、ソート処理手段によって作成された任意一致検索イ
ンデックスをバイナリサーチし、任意一致検索語と前方
一致する任意一致検索キーを探し出し、探し出した任意
一致検索キーと対応付けされているレコードキーを出力
する。

【００２３】（Ｂ）の構成に於いては、ソート処理手段
で作成されたレコードキーとの対応付けが行なわれた任
意一致検索キーが所定の順序で並んだ集合に対して、マ
ージ処理手段が前方一致する任意一致検索キー同士をマ
ージし、レコードキーとの対応付けが行なわれたマージ
された任意一致検索キー及びマージされなかった任意一
致検索キーが所定の順序で並んだ任意一致検索インデッ
クスを作成する。

【００２４】

【実施例】次に本発明の実施例について図面を参照して
詳細に説明する。

【００２５】図１は本発明の実施例のブロック図であ
り、サーチ手段１と、任意一致検索インデックス２と、
データベースマネージメントシステム３と、任意一致検
索インデックス作成手段４とから構成されている。

【００２６】任意一致検索インデックス２は図２に示す
ように、任意一致検索キー２１と、レコードキー２２と
を有している。

【００２７】任意一致検索キー２１の各欄には任意一致
検索キーＷＫ−ｉ（ｉ＝１，２，…，ｐ）が、レコード
キー２２の各欄には任意一致検索キーＷＫ−ｉを有する
レコードのレコードキーＤＢＫ−ｊ（ｊ＝１，２，…，
ｑ）が格納されている。

【００２８】図２の例は、任意一致検索キーＷＫ−１を
有するレコードは３つあり、そのレコードキーはＤＢＫ
−１，ＤＢＫ−２，ＤＢＫ−３であることを示してい
る。他の行も同様のことを示している。

【００２９】サーチ手段１は任意一致検索インデックス
２の任意一致検索キー２１の欄をサーチして入力された
検索語と前方一致する文字列を有する任意一致検索キー
を探し出し、探し出した任意一致検索キーと対応して任
意一致検索インデックス２に格納されているレコードキ
ーをデータベースマネージメントシステム３に出力す
る。

【００３０】データベースマネージメントシステム３は
レコードＲ１〜Ｒｎによって構成されるデータベース及
びデータベースの管理機能を含むものであり、サーチ手
段１から出力されたレコードキーを受け取って、このレ
コードキーを持つレコードの属性を出力する。

【００３１】データベースを構成する各レコードＲ１〜
Ｒｎは索引語３１と、属性の組３２と、レコードキー３
３とから構成されている。

【００３２】任意一致検索インデックス作成手段４は任
意一致検索インデックス２を作成するものであり、索引
語抽出処理手段４１と、ソート処理手段４２と、マージ
処理手段４３とから構成されている。

【００３３】次に、本実施例の動作を説明する。尚、以
下の説明に於いては、データベースマネージメントシス
テム３内のレコードＲ１〜Ｒｎのレコード数は５個（ｎ
＝５）であり、各レコードＲ１〜Ｒ５の内容はそれぞれ
図６に示したレコードＲ１〜Ｒ５と同一であるとする。

【００３４】先ず、任意一致検索インデックス作成手段
４の動作を説明する。

【００３５】任意一致検索インデックス作成手段４内の
索引語抽出処理手段４１はデータベースマネージメント
システム３から開始指示が加えられると、レコードＲ１
〜Ｒ５の索引語３１それぞれに対して、索引語中の各文
字を先頭文字とする後方の文字列を任意一致検索キーと
して抽出する処理を行ない、更に、抽出した任意一致検
索キーにそれを抽出した索引語を含んでいるレコードの
レコードキーを付加する処理を行なう。尚、データベー
スマネージメントシステム３はデータベースが更新され
た場合、上記開始指示を出力するものである。

【００３６】例えば、レコードＲ１の索引語「アイウエ
オ」について上述した処理を行なうことにより、任意一
致検索キー「アイウエオ」，「イウエオ」，「ウエ
オ」，「エオ」，「オ」が抽出され、抽出された各任意
一致検索キーにレコードＲ１のレコードキーＤＢＫ−１
が付加される。

【００３７】以上の処理を全てのレコードＲ１〜Ｒ５の
索引語に対して行なうことにより、図３に示すレコード
キーが付加された任意一致検索キーの集合が得られる。

【００３８】ソート処理手段４２は索引語抽出処理手段
４１が作成した図３の集合中のレコードキーの付加され
た任意一致検索キーに対して昇順のソート（５０音順）
を行なう。

【００３９】これにより、図４に示す集合が得られる。

【００４０】マージ処理手段４３はソート処理手段４２
が作成した図４の集合に対して以下の処理を行なう。

【００４１】マージ処理手段４３は、先ず、集合内の先
頭の任意一致検索キーを選択し、それと前方一致する任
意一致検索キーを探す。

【００４２】前方一致する任意一致検索キーを探し出せ
なかった場合は、上記選択した任意一致検索キーを任意
一致検索インデックス２の任意一致検索キー２１の先頭
領域に格納すると共に、上記選択した任意一致検索キー
に付加されているレコードキーを任意一致検索インデッ
クス２のレコードキー２２の先頭領域に格納する。

【００４３】また、前方一致する任意一致検索キーを探
し出せた場合は、探し出した任意一致検索キーの中で最
も文字数の多いものを任意一致検索インデックス２の任
意一致検索キー２１の先頭領域に格納すると共に、上記
前方一致した任意一致検索キーに付加されているレコー
ドキーを全て任意一致検索インデックス２のレコードキ
ー２２の先頭領域に格納する。

【００４４】図４の集合の場合、先頭の任意一致検索キ
ーは「アイウエオ」あり、それと前方一致する任意一致
検索キーは集合内に存在しないので、図５に示すよう
に、任意一致検索インデックス２の任意一致検索キー２
１の先頭領域には任意一致検索キー「アイウエオ」が、
レコードキー２２の先頭領域にはレコードキー「ＤＢＫ
−１」が格納される。

【００４５】その後、マージ手段４３は集合内の未処理
の任意一致検索キーの内の先頭に最も近いものを選択
し、前述したと同様の処理を行なう。

【００４６】図４の集合の場合、未処理の任意一致検索
キーの内の先頭に最も近い任意一致検索キーは「イウ
エ」であるので、それと前方一致する任意一致検索キー
として任意一致検索キー「イウエオ」が探し出される。
また、前方一致する任意一致検索キーの内で最も文字数
の多い任意一致検索キーは「イウエオ」であるので、図
５に示すように、任意一致検索キー２１の第２番目の領
域に任意一致検索キー「イウエオ」が格納され、レコー
ドキー２２の第２番目の領域に任意一致検索キー「イウ
エオ」，「イウエ」に付加されているレコードキー「Ｄ
ＢＫ−１，ＤＢＫ−２」が格納される。

【００４７】以下、未処理の任意一致検索キーがなくな
るまで、前述した処理が行なわれ、図５に示す任意一致
検索インデックス２が作成される。

【００４８】次に、任意一致検索を行なう場合の動作を
説明する。

【００４９】サーチ手段１は任意一致検索語が入力され
ると、任意一致検索インデックス２の任意一致検索キー
２１の欄に対してバイナリサーチを行ない、入力された
任意一致検索語と前方一致する任意一致検索キーを探し
出し、探し出した任意一致検索キーと対応してレコード
キー２２の欄に格納されているレコードキーをデータベ
ースマネージメントシステム３に出力する。

【００５０】データベースマネージメントシステム３は
サーチ手段１からレコードキーが加えられると、そのレ
コードキーを有するレコードを出力する。

【００５１】今、例えば、任意一致検索語として「ウ
エ」がサーチ手段１に入力されたとすると、サーチ手段
１は任意一致検索インデックス２の任意一致検索キー２
１の欄に対してバイナリサーチを行ない、任意一致検索
語「ウエ」と前方一致する任意一致検索キー「ウエオ」
を探し出し、探し出した任意一致検索キー「ウエオ」と
対応してレコードキー２２の欄に格納されているレコー
ドキー「ＤＢＫ−１」，「ＤＢＫ−２」，「ＤＢＫ−
３」，「ＤＢＫ−４」をデータベースマネージメントシ
ステム３に出力することになる。

【００５２】尚、上述した実施例に於いては、マージ処
理手段４３の処理結果を任意一致検索インデックス２と
したが、ソート処理手段４２の処理結果（図４に示す集
合）を任意一致検索インデックス２とすることもでき
る。この場合は、マージされていないので、任意一致検
索インデックス２の項目数が多く、マージ処理手段４３
の処理結果を任意一致検索インデックス２とした場合に
比べて検索速度は遅くなるが、任意一致検索に於いてバ
イナリサーチを行なうことができるので、従来例に比較
すれば、検索時間は非常に短くなる。

【００５３】

【発明の効果】以上説明したように、本発明は各索引語
から索引語中の各文字を先頭文字とする後方の文字列を
抽出することにより得た任意一致検索キーをソートした
任意一致検索インデックスを用いて任意一致検索を行な
うものであり、任意一致検索に於いてもバイナリサーチ
を行なうことができるので、任意一致検索時に於ける検
索時間を短縮することができる効果がある。

【００５４】また、本発明はマージ処理手段により前方
一致する任意一致検索キー同士を１つにマージするの
で、任意一致検索インデックスの項目数を少なくするこ
とができ、従って検索時間を更に短縮することが可能に
なる効果がある。

【図面の簡単な説明】

【図１】本発明の実施例のブロック図である。

【図２】任意一致検索インデックス２の論理構成図であ
る。

【図３】索引語抽出処理手段４１の処理結果の一例を示
す図である。

【図４】ソート処理手段４２の処理結果の一例を示す図
である。

【図５】マージ処理手段４３の処理結果の一例を示す図
である。

【図６】データベースの構成例を示す図である。

【図７】従来使用されていたインデックスの構成例を示
す図である。

【符号の説明】

１…サーチ手段 ２…任意一致検索インデックス ２１…任意一致検索キー ２２…レコードキー ３…データベースマネージメントシステム ３１…索引語 ３２…属性の組 ３３…レコードキー ４…任意一致検索インデックス作成手段 ４１…索引語抽出処理手段 ４２…ソート処理手段 ４３…マージ処理手段

Claims (2)

【特許請求の範囲】
1. 【請求項１】 索引語を有する複数のレコードから構成
   されるデータベースと、 前記各索引語から索引語中の各文字を先頭文字とする後
   方の文字列を任意一致検索キーとして抽出し、抽出した
   任意一致検索キーとそれを抽出した索引語を含んでいる
   レコードのレコードキーとの対応付けを行なう索引語抽
   出処理手段と、 該索引語抽出処理手段で抽出され、レコードキーとの対
   応付けが行なわれた任意一致検索キーをソートすること
   により、前記レコードキーとの対応付けが行なわれた任
   意一致検索キーが所定の順序で並んだ任意一致検索イン
   デックスを作成するソート処理手段と、 任意一致検索語が入力されることにより、前記任意一致
   検索インデックスをバイナリサーチし、前記任意一致検
   索語と前方一致する任意一致検索キーを探し出し、探し
   出した任意一致検索キーに対応するレコードキーを出力
   するサーチ手段とを含むことを特徴とする任意一致検索
   方式。
2. 【請求項２】 索引語を有する複数のレコードから構成
   されるデータベースと、 前記各索引語から索引語中の各文字を先頭文字とする後
   方の文字列を任意一致検索キーとして抽出し、抽出した
   任意一致検索キーとそれを抽出した索引語を含んでいる
   レコードのレコードキーとの対応付けを行なう索引語抽
   出処理手段と、該索引語抽出処理手段で抽出され、レコ
   ードキーとの対応付けが行なわれた任意一致検索キーを
   ソートすることにより、前記レコードキーとの対応付け
   が行なわれた任意一致検索キーが所定の順序で並んだ集
   合を作成するソート処理手段と、 該ソート処理手段で作成された集合に含まれている任意
   一致検索キーの内、前方一致する任意一致検索キー同士
   をマージすることにより、前記レコードキーとの対応付
   けが行なわれたマージされた任意一致検索キー及びマー
   ジされなかった任意一致検索キーが所定の順序で並んだ
   任意一致検索インデックスを作成するマージ処理手段
   と、 任意一致検索語が入力されることにより、前記任意一致
   検索インデックスをバイナリサーチし、前記任意一致検
   索語と前方一致する任意一致検索キーを探し出し、探し
   出した任意一致検索キーに対応するレコードキーを出力
   するサーチ手段とを含むことを特徴とする任意一致検索
   方式。