JPS63155231A - 情報検索装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、データベースに総称される情報検索装置に関
するものである。

従来の技術 従来の情報検索装置においては、情報はレコードで管理
され、索引はレコード内のある属性の属性値に関して作
成されている。レコードの追加。

削除あるいは属性値の変更に伴う索引の更新が柔軟に行
なえるように、索引内の索引語は属性値の最大長つまり
属性の占める大きさく属性長）で固定的に扱っていた。

発明が解決しようとする問題点 しかしながら上記のような構成では、全ての索引語長が
属性長に一致するときは問題ないが、最長のものを想定
して余裕をもって設計している場合には、無駄な領域が
多くなり、ひいては検索速度の低下を招くという問題点
を有していた。

本発明はかかる点に鑑み、索引語を固定長の部分索引語
に分割して管理し、索引内の無駄領域を排除し、効率の
よい索引を作成する情報検索装置を提供することを目的
とする。

問題点を解決するための手段 本発明は、情報を管理する情報管理手段と、索引語を固
定長で分割して索引を作成する索引作成手段と、分割さ
れた索引語を合成して検索することにより目的とする情
報を得る検索手段を備えた情報検索装置である。

作用 本発明は、上記した構成によシ、索引語をある固定長の
整数倍単位で可変長に管理することができ、索引の圧縮
が行なわれる。

実施例 第１図は、本発明の一実施例における情報検索装置のブ
ロック図を示すものでちる。第１図において１は情報管
理手段、２は索引作成手段、３は検索手段、４は索引で
ある。

情報管理手段１は、情報をある識別子で管理する。索引
作成手段２は、索引語をＢ−ＴＲＥＥに準じた形で管理
する。検索手段３は、検索の条件として与えられた語と
索引４内の索引語とを順次条件比較し、条件に合う索引
語が見つかるとその索引語に対応する情報の識別子を求
める。

以上のように構成された本実施例の情報検索装置につい
て以下その動作を説明する。

索引４は固定長のブロック単位で管理され、ブロック内
には索引語格納用のスロットが形成される。第２図にお
いて、１００はスロット、２００はブロック図である。

索引４は階層構造を成す複数のブロックよシ構成される
。スロット１ｏＯば１０１の前索引ブロックポインタ、
１０２の索引語偏位値、１０３の情報識別子、１０４０
部分索引語で構成される。

索引語偏位値１０２と部分索引語１０４の関係について
、さらに説明する。索引４内では索引語は昇順に格納さ
れ、ある索引語人の次の索引語Ｂは索引語人との差分て
表現する。索引語偏位値１０２はその時の索引語人の最
終文字からの逆戻り文字位置を表わす。つまり、索引語
偏位値を（）内の数値で表現すると、 ａｂｅｄばａ　　に対して（ｏ）　ｂ　ｅ　ｄａｂ　　
　に対して（０）ｃｄ ａａ　　　に対して（−１）ｂｅｄ ｘｙｚ　はＸ　　に対して（ｃｅｙｚであるからＸ　（
０）　３’　Ｚｘｙ　　に対してに）２であるからＸ７
（Ｏ２ｘｘ　　に対して（−１）ｙｚでちるからｘｘ（
−１）ｙｚａｂｃ　　に対して（−３）ｘｙｚであるか
らａｂｃ（−３）ｘｙｚである。

索引作成手段２は、この索引語分割則にしたがって索引
４ｆｔ作成する。

いま、＃１〜＃了の識別子で示される７つの情報の索引
語を、それぞれ、ａｂｃｄ、ａｂｃ、ｈｉｊ　ｋ　、ｈ
ｉ　、ｈ　、ｘｙｚ　、ｘｙとする。スＯット１００の
部分索引語１０４の領域がＷ＝３文字分であるとし、１
ブロツクがＳ＝４スロットで構成されると仮定する。こ
の時の索引４の作られ方を第３図にそって説明する。こ
こで、前索引ブロックポインタ１０１の値が０の時は、
前索引ブロックがないことを示し、＊印が付与されてい
る時はそれ以降のスロットは空であることを示す。情報
識別子１０３の値が○の時は、その部分索引語１０４に
該当する情報が存在しないことを示す。

情報＃１の索引語は部分索引語１０４の領域を越える長
さを持っているので、ａｂｅｄ−＋ａｂｃ（Ｃｅｄの分
割が行なわれ、２スロツトにまたがって格納される〔第
３図（ａ）〕。

情報＃２の索引語は先頭の部分索引語に一致するので、
先頭の情報識別子１０３の値が○から＃２に更新される
〔第３図（ｂ）〕。

同様に、＃１〜＃４まで登録されると、ａｂｃ　　→ｐ
）ａｂｃ ａｂＣｄ−＋ゆ）ａｂｃ（ｃｏｄ ｈｉ　　−（ｑａｂｃ（（ｌｄ（−４）ｈｉｈｉｊｋ−
（ｃ＄ａｂｃｌ＝ｓ）ｄ（−４）ｈｉ（ｑｊ　ｋの分割
により第３図（Ｃ）のようになる。

次に、＃６の登録時にはブロックの溢れが生じ、ブロッ
クの分割が行なわれる。索引語の追加や挿入によるブロ
ックの分割や、索引語の清洗や変更によるブロックの統
合はＢ−ＴＲＥＥの手法に準するのでここでの説明は省
略する。＃４の索引語り工は＃６の索引語りの出現とブ
ロックの分割により、ｈｉ→ｈ　（ｏ）　ｉに変換され
る。

このようにして、＃１〜＃了のすべての索引語登録後の
索引４は第３図（ｄ）のようになる。

検索手段３は、この索引語分割則を逆変換して元の索引
語を合成し、検索動作を実行する。

ここで、本実施例の索ｌ引４を従来の索引と比較してみ
る。索引語の最大炎を２ＸＷ＝６とする。

第４図はブロックサイズ（ＷＸＳ　）を本実施例と同じ
にした場合、第６図はスロット数を本実施例と同じにし
た場合のＢ−ＴＲＥＥ　の構造を示している。図から明
らかなように、第４図では２ＷＸ７＝１４Ｗ、第６図で
ば８ＷＸ３：２４Ｗの領域を要しているのに対し、本実
施例では４Ｗ×３＝１２Ｗしか必要とせずしかも階層数
が低い。

なお、索引の作成法については、Ｂ−ＴＲＥＥに準じた
形で説明したが、その応用は本実施例に限るものではな
い。

発明の詳細 な説明したように、本発明によれば、索引語を固定長で
分割して管理し、分割された索引＠を合成して検索する
ことにより、索引語を固定長の整数倍単位で可変長に管
理することができ、索引の圧縮が行なわれその実用的効
果は大きい。

【図面の簡単な説明】

第１図は本発明における一実施例の情報検索装置のブロ
ック図、第２図は同実施例における索引の説明図、第３
図は同実施例による索引の生成過程の説明図、第４図、
第６図は従来の索引の構造を表わす説明図である。 １・・・・・・情報管理手段、２・・・・・・索引作成
手段、３・・・・・−検索手段、４・・・・・・索引、
１００・・・・・・スロット、１０１・・・・・・前索
引ブロックポインタ、１０２・・・・・・索引語偏位値
、１０３・・・・・・情報識別子、１０４・・・・・・
部分索引語、２００・・・・・・ブロック。 代理人の氏名　弁理士　中　尾　敏　男　ほか１名菓！
図 第２図　　　（の） 第３図 （ａ−）

Claims (1)

【特許請求の範囲】
1. 情報を管理する情報管理手段と、前記情報に関する索引
   を作成する索引作成手段と、前記索引を検索することに
   より目的とする前記情報を得る検索手段とを具備し、前
   記索引作成手段は索引語を固定長で分割して前記情報と
   対応づけて管理し、前記検索手段は分割された索引語を
   合成して検索することにより目的とする情報の検索を行
   なうことを特徴とする情報検索装置。