図面 (/)

技術 インデックス管理装置およびインデックスの更新方法およびインデックス管理方法ならびにインデックス更新用プログラムが記録されたコンピュータ読取可能な記録媒体およびインデックス管理用プログラムが記録されたコンピュータ読取可能な記録媒体

出願人 富士通株式会社
発明者 難波功
出願日 1998年3月20日 (21年6ヶ月経過) 出願番号 1998-071682
公開日 1999年10月8日 (19年11ヶ月経過) 公開番号 1999-272691
状態 特許登録済
技術分野 検索装置 計算機におけるファイル管理
主要キーワード 追加予定 記憶イメージ 初期割り当て 出現頻度数 登録予定 レコード列 追加文書 レコードキー
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(1999年10月8日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (5)

課題

インデックス管理装置において、全文検索装置などのようにキーに対して長大なレコード列を持ち、かつその長さがキーにより極端に異なるデータ構造を持つインデックスに対して、レコード情報出現頻度の数等の統計情報を利用することにより効率的に領域を割り当てる。

解決手段

インデックスを構成するキー情報に対応した内容情報を記憶領域上で管理するインデックス記憶管理部2と、インデックスに関する管理情報を記憶領域上で管理する管理情報記憶管理部3とをそなえる。これらの機能の中に、インデックスに追加すべき情報として入力されるキー情報および内容情報の組を単位とするレコード情報に基づいて、管理情報を更新する管理情報更新部4と、を、インデックスを更新する際に、管理情報を用いて必要に応じて設定すべき空き領域を演算により算出する領域算出部5と、それに基づいて、記憶領域を割り当てる領域割当部6とをそなえる。

概要

背景

一般的な検索装置は、例えば、文書ファイル群を対象として情報検索を行なうことができるものである。具体的には、文書番号の付された文書ファイル群を検索対象としながらある単語をキーとし、このキーに関して記述された文書番号群を検索結果として出力するといった情報検索処理を行なうことができるようになっている。

このような検索装置においては、検索キーを入力してから検索結果を出力するまでの処理速度を高速化させるために、予めキーとなるものに対する検索結果がまとめられたインバーテッドファイル形式インデックスファイルを記憶領域上に持つことにより、文書ファイル群の情報を管理している。すなわち、上述の検索装置にあるキーが入力されると、このキーから上述のインデックスファイルにおける対応レコード情報を単に開くという動作のみで、検索結果を出力することができるものである。

ところで、従来の検索装置において用いられるインデックスファイルの記憶領域上の領域割り当ては、キー情報に対するレコード情報の部分に対する領域として、初めに所定サイズの領域ブロックを与えて、その中にレコード情報を記憶する一方、所定サイズを超えるレコード情報については、複数の領域ブロックにわたって記憶するようになっている。

すなわち、初期設定値として記憶領域上に所定長の領域ブロックがキー毎割り当てられ、その領域ブロック中に各キーに対するレコード情報が記憶される一方、記憶すべきレコード情報に対して与えられた領域ブロックの領域サイズ不足すると、初めに与えられた領域とは離れた場所に、そのキーに対するレコードを記憶する領域ブロックを与え、各領域ブロック間をチェインすることで、キー情報に対するレコード情報を記憶する領域を確保するようになっている。

概要

インデックス管理装置において、全文検索装置などのようにキーに対して長大なレコード列を持ち、かつその長さがキーにより極端に異なるデータ構造を持つインデックスに対して、レコード情報の出現頻度の数等の統計情報を利用することにより効率的に領域を割り当てる。

インデックスを構成するキー情報に対応した内容情報を記憶領域上で管理するインデックス記憶管理部2と、インデックスに関する管理情報を記憶領域上で管理する管理情報記憶管理部3とをそなえる。これらの機能の中に、インデックスに追加すべき情報として入力されるキー情報および内容情報の組を単位とするレコード情報に基づいて、管理情報を更新する管理情報更新部4と、を、インデックスを更新する際に、管理情報を用いて必要に応じて設定すべき空き領域を演算により算出する領域算出部5と、それに基づいて、記憶領域を割り当てる領域割当部6とをそなえる。

目的

一方、従来の検索装置では、領域を増分するときにも一定の領域を割り当てようとすると、増分が見込まれる領域サイズもキーによってまちまちであり、特に、増分が少なく見込まれるキーに対しては、過剰な領域を与えるとの課題がある。本発明は、このような課題に鑑み創案されたもので、全文検索装置などのようにキーに対して長大なレコード列を持ち、かつレコード部の長さがキーにより極端に異なるデータ構造を持つインデックスに対して、キー毎のレコード情報の出現頻度の数等のインデックスに関する統計情報を利用することにより効率的に領域を割り当てることができるようにした、インデックス管理装置およびインデックスの更新方法およびインデックス管理方法ならびにインデックス更新用プログラムが記録されたコンピュータ読取可能な記録媒体およびインデックス管理用プログラムが記録されたコンピュータ読取可能な記録媒体を提供することを目的とする。

効果

実績

技術文献被引用数
1件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

項目となるキー情報と上記キー情報の内容となる内容情報とにより構成されるインデックスの、記憶領域上への記憶状態を管理するインデックス管理装置であって、上記インデックスを構成するキー情報に対応した内容情報を記憶領域上で管理するインデックス記憶管理部と、上記インデックスに関する管理情報を記憶領域上で管理する管理情報記憶管理部とをそなえ、上記記憶領域上で管理されるインデックスに追加すべき情報として入力されるキー情報および内容情報の組を単位とするレコード情報に基づいて、上記記憶領域上で管理される管理情報を更新する管理情報更新部を該管理情報記憶管理部にそなえるとともに、該インデックス記憶管理部が、上記の入力されるレコード情報に基づいて記憶領域上のインデックスを更新する際に、該管理情報記憶管理部にて管理されている上記管理情報を用いて、必要に応じて設定すべき空き領域を演算により算出する領域算出部と、該領域算出部にて算出された上記空き領域に基づいて、上記インデックスを記憶すべき記憶領域を割り当てる領域割当部とをそなえて構成されたことを特徴とする、インデックス管理装置。

請求項2

該管理情報記憶管理部が、上記キー情報毎の入力レコード情報の数,上記記憶領域にて記憶されている全ての入力レコード情報の数,上記各キー情報に対応したレコード情報として追加予定のレコード情報の数および上記インデックスを構成する各キー情報に対応する内容情報のサイズ情報のうちの、少なくとも一つを上記管理情報として管理すべく構成されたことを特徴とする、請求項1記載のインデックス管理装置。

請求項3

該領域割当部が、上記各キー情報に対応する内容情報を連続した領域に記憶しうるように上記記憶領域を割り当てるべく構成されたことを特徴とする、請求項1記載のインデックス管理装置。

請求項4

該領域割当部が、上記内容情報を記憶すべき連続領域を、上記キー情報毎に固有に割り当てるべく構成されたことを特徴とする、請求項3記載のインデックス管理装置。

請求項5

該領域算出部が、上記記憶領域に内容情報を追加するための領域が不足した場合に、上記内容情報を追加するために必要な空き領域を演算するように構成されたことを特徴とする、請求項4記載のインデックス管理装置。

請求項6

記憶領域上で管理された、項目となるキー情報と上記キー情報の内容となる内容情報とにより構成されるインデックスを更新すべく、上記インデックスに追加すべき情報を、上記記憶領域に登録する際に、上記インデックスに追加すべき情報として、キー情報および当該キー情報の内容情報を組とするレコード情報を入力され、上記入力されたレコード情報に基づき、上記インデックスの管理情報を更新する管理情報更新ステップと、上記入力されたレコード情報における内容情報を登録すべき記憶領域上の位置を、上記レコード情報に対応するキー情報に基づき抽出する抽出ステップと、該抽出ステップにおける抽出の結果得られた記憶領域上の位置に、上記レコード情報における内容情報を登録するために必要な大きさの連続した空き領域が有るか否かを判定する判定ステップと、該抽出ステップにおける抽出の結果、上記レコード情報における内容情報を登録すべき記憶領域上の位置が抽出できなかった場合、または該判定ステップにおいて上記レコード情報における内容情報を登録するために必要な大きさの連続した空き領域が無いと判定された場合には、上記レコード情報に対応するキー情報について必要であると予測される内容情報登録用の領域の大きさを所定の演算により算出する領域算出ステップと、該領域算出ステップにて算出された大きさの領域を、上記レコード情報における内容情報の登録のために割り当てる領域割当ステップと、該判定ステップにおいて上記連続した空き領域が有ると判定された場合には当該空き領域に、該領域割当ステップにて領域が割り当てられた場合には当該割り当てられた領域に、それぞれ追加すべき上記レコード情報における内容情報を登録する登録ステップとをそなえて構成されたことを特徴とする、インデックスの更新方法

請求項7

該領域算出ステップでは、出現頻度が少ないキー情報に対しては上記内容情報登録用として小さい領域を算出する一方、出現頻度が多いキー情報に対しては上記内容情報登録用として大きい領域を算出することを特徴とする、請求項6記載のインデックスの更新方法。

請求項8

該領域算出ステップにおける上記所定の演算が、上記インデックスに含まれる全レコード数が増加するにつれて、上記の初めて出現したキー情報に対して算出される内容情報登録用の領域の大きさを減少させることを特徴とする、請求項6記載のインデックスの更新方法。

請求項9

記憶領域上で管理された、項目となるキー情報と上記キー情報の内容となる内容情報とにより構成されるインデックスを更新すべく、上記インデックスに追加すべき情報を、上記記憶領域に登録する際に、コンピュータに、上記インデックスに追加すべき情報として、キー情報および当該キー情報の内容情報を組とするレコード情報を入力され、上記入力されたレコード情報に基づき、上記インデックスの管理情報を更新する管理情報更新手段と、上記入力されたレコード情報における内容情報を登録すべき記憶領域上の位置を、上記レコード情報に対応するキー情報に基づき抽出する抽出手段と、該抽出手段における抽出の結果得られた記憶領域上の位置に、上記入力されたレコード情報における内容情報を登録するために必要な大きさの連続した空き領域が有るか否かを判定する判定手段と、該抽出手段における抽出の結果、上記レコード情報における内容情報を登録すべき記憶領域上の位置が抽出できなかった場合、または該判定手段において上記レコード情報における内容情報を登録するために必要な大きさの連続した空き領域が無いと判定された場合には、上記レコード情報に対応するキー情報について必要であると予測される内容情報登録用の領域の大きさを所定の演算により算出する領域算出手段と、該領域算出手段にて算出された大きさの領域を、上記レコード情報における内容情報の登録のために割り当てる領域割当手段と、該判定手段において上記連続した空き領域が有ると判定された場合には当該空き領域に、該領域割当手段にて領域が割り当てられた場合には当該割り当てられた領域に、それぞれ追加すべき上記レコード情報における内容情報を登録する登録手段として機能させるためのインデックス更新用プログラムが記録されたことを特徴とする、インデックス更新用プログラムが記録されたコンピュータ読取可能な記録媒体

請求項10

項目となるキー情報と上記キー情報の内容となる内容情報とにより構成されるインデックスの、記憶領域上への記憶状態を管理するインデックス管理方法であって、上記記憶領域上で管理されるインデックスに追加すべき情報として入力されるキー情報および内容情報の組を単位とするレコード情報に基づいて、上記記憶領域上で管理される上記インデックスに関する管理情報を更新するステップと、入力されるレコード情報に基づいて記憶領域上のインデックスを更新する際に、上記管理情報を用いて、必要に応じて設定すべき空き領域を算出するステップと、算出された上記空き領域に基づいて、上記インデックスを記憶すべき記憶領域を割り当てるステップとをそなえて構成されたことを特徴とする、インデックス管理方法。

請求項11

項目となるキー情報と上記キー情報の内容となる内容情報とにより構成されるインデックスの、記憶領域上への記憶状態を管理するインデックス管理用プログラムが記録されたコンピュータ読取可能な記録媒体であって、上記インデックス管理用プログラムは、上記記憶領域上で管理されるインデックスに追加すべき情報として入力されるキー情報および内容情報の組を単位とするレコード情報に基づいて、上記記憶領域上で管理される上記インデックスに関する管理情報を更新するステップと、入力されるレコード情報に基づいて記憶領域上のインデックスを更新する際に、上記管理情報を用いて、必要に応じて設定すべき空き領域を算出するステップと、算出された上記空き領域に基づいて、上記インデックスを記憶すべき記憶領域を割り当てるステップとをそなえて構成されたことを特徴とする、インデックス管理用プログラムが記録されたコンピュータ読取可能な記録媒体。

--

0001

目次
発明の属する技術分野
従来の技術
発明が解決しようとする課題
課題を解決するための手段(図1
発明の実施の形態
実施の形態の説明(図2図4
その他
発明の効果

技術分野

0002

本発明は、項目キーとして大量のデータ情報検索し関連する情報を抽出する検索装置に用いられるインデックスファイルを、管理,更新する際に用いて好適の、インデックス管理装置およびインデックス更新方法およびインデックス管理方法ならびにインデックス更新用プログラムが記録されたコンピュータ読取可能な記録媒体およびインデックス管理用プログラムが記録されたコンピュータ読取可能な記録媒体に関するものである。

0003

インデックスファイルは、キー情報に対して長大なレコード情報を格納するものであって、特にインバーテッドファイル(inverted file、転置ファイル)形式のインデックスファイルは、インデックスを構成する項目となるキー情報から、高速にレコード情報を見つけ出すために作られるファイルであって、全文検索で使用されるようになっている。

背景技術

0004

一般的な検索装置は、例えば、文書ファイル群を対象として情報検索を行なうことができるものである。具体的には、文書番号の付された文書ファイル群を検索対象としながらある単語をキーとし、このキーに関して記述された文書番号群を検索結果として出力するといった情報検索処理を行なうことができるようになっている。

0005

このような検索装置においては、検索キーを入力してから検索結果を出力するまでの処理速度を高速化させるために、予めキーとなるものに対する検索結果がまとめられたインバーテッドファイル形式のインデックスファイルを記憶領域上に持つことにより、文書ファイル群の情報を管理している。すなわち、上述の検索装置にあるキーが入力されると、このキーから上述のインデックスファイルにおける対応レコード情報を単に開くという動作のみで、検索結果を出力することができるものである。

0006

ところで、従来の検索装置において用いられるインデックスファイルの記憶領域上の領域割り当ては、キー情報に対するレコード情報の部分に対する領域として、初めに所定サイズの領域ブロックを与えて、その中にレコード情報を記憶する一方、所定サイズを超えるレコード情報については、複数の領域ブロックにわたって記憶するようになっている。

0007

すなわち、初期設定値として記憶領域上に所定長の領域ブロックがキー毎割り当てられ、その領域ブロック中に各キーに対するレコード情報が記憶される一方、記憶すべきレコード情報に対して与えられた領域ブロックの領域サイズ不足すると、初めに与えられた領域とは離れた場所に、そのキーに対するレコードを記憶する領域ブロックを与え、各領域ブロック間をチェインすることで、キー情報に対するレコード情報を記憶する領域を確保するようになっている。

発明が解決しようとする課題

0008

しかしながら、このような従来のインデックスファイルの記憶領域上の領域割り当て手法においては、インデックスファイルとして全文検索で使われるインバーテッドファイル形式を適用した場合には、キー情報に対して格納するレコード情報のサイズがキー情報により大幅に異なっている。このような場合にKバイト単位の一定サイズの領域ブロックを初期に割り当てると、この領域ブロックよりもはるかに小さい領域しか必要としないキーが大部分であるため、このようなレコード情報記憶のために過剰な領域が確保され、記憶領域の効率的利用に支障を来すという課題がある。

0009

一方、従来の検索装置では、領域を増分するときにも一定の領域を割り当てようとすると、増分が見込まれる領域サイズもキーによってまちまちであり、特に、増分が少なく見込まれるキーに対しては、過剰な領域を与えるとの課題がある。本発明は、このような課題に鑑み創案されたもので、全文検索装置などのようにキーに対して長大なレコード列を持ち、かつレコード部の長さがキーにより極端に異なるデータ構造を持つインデックスに対して、キー毎のレコード情報の出現頻度の数等のインデックスに関する統計情報を利用することにより効率的に領域を割り当てることができるようにした、インデックス管理装置およびインデックスの更新方法およびインデックス管理方法ならびにインデックス更新用プログラムが記録されたコンピュータ読取可能な記録媒体およびインデックス管理用プログラムが記録されたコンピュータ読取可能な記録媒体を提供することを目的とする。

課題を解決するための手段

0010

図1は本発明の原理ブロック図であり、この図1において、1はインデックス管理装置であり、インデックス管理装置1は、項目となるキー情報とキー情報の内容となる内容情報とにより構成されるインデックスの、記憶領域上への記憶状態を管理するものである。

0011

このため、インデックス管理装置1は、インデックス記憶管理部2,管理情報記憶管理部3をそなえて構成される。ここで、インデックス記憶管理部2は、インデックスを構成するキー情報に対応した内容情報を記憶領域上で管理するものである。管理情報記憶管理部3は、インデックスに関する管理情報を記憶領域上で管理するものである。

0012

更に、管理情報記憶管理部3は、管理情報更新部4をそなえて構成されることを特徴とする。この管理情報更新部4は、記憶領域上で管理されるインデックスに追加すべき情報として入力されるキー情報および内容情報の組を単位とするレコード情報に基づいて、記憶領域上で管理される管理情報を更新するものである。

0013

また、インデックス記憶管理部2は、領域算出部5,領域割当部6をそなえて構成されることも特徴とする。領域算出部5は、入力されるレコード情報に基づいて記憶領域上のインデックスを更新する際に、管理情報記憶管理部にて管理されている管理情報を用いて、必要に応じて設定すべき空き領域を演算により算出するものである。

0014

領域割当部6は、領域算出部にて算出された空き領域に基づいて、インデックスを記憶すべき記憶領域を割り当てるものである(以上、請求項1)。更に、管理情報記憶管理部3が、キー情報毎の入力レコード情報の数,記憶領域にて記憶されている全ての入力レコード情報の数,各キー情報に対応したレコード情報として追加予定のレコード情報の数およびインデックスを構成する各キー情報に対応する内容情報のサイズ情報のうちの、少なくとも一つを管理情報として管理するようにも構成できる(請求項2)。

0015

または、領域割当部6が、各キー情報に対応する内容情報を連続した領域に記憶しうるように記憶領域を割り当てるべく構成することもできる(請求項3)。または、領域割当部6を、内容情報を記憶すべき連続領域を、キー情報毎に固有に割り当てるように構成することもできる(請求項4)。または、領域算出部5を、記憶領域に内容情報を追加するための領域が不足した場合に、内容情報を追加するために必要な空き領域を演算するように構成することもできる(請求項5)。

0016

一方、請求項6記載のインデックスの更新方法は、記憶領域上で管理された、項目となるキー情報とキー情報の内容となる内容情報とにより構成されるインデックスを更新すべく、インデックスに追加すべき情報を、記憶領域に登録する際に、インデックスに追加すべき情報として、キー情報およびキー情報の内容情報を組とするレコード情報を入力され、入力されたレコード情報に基づき、インデックスの管理情報を更新する管理情報更新ステップと、入力されたレコード情報における内容情報を登録すべき記憶領域上の位置を、レコード情報に対応するキー情報に基づき抽出する抽出ステップと、抽出ステップにおける抽出の結果得られた記憶領域上の位置に、レコード情報における内容情報を登録するために必要な大きさの連続した空き領域が有るか否かを判定する判定ステップと、抽出ステップにおける抽出の結果、レコード情報における内容情報を登録すべき記憶領域上の位置が抽出できなかった場合、または判定ステップにおいてレコード情報における内容情報を登録するために必要な大きさの連続した空き領域が無いと判定された場合には、レコード情報に対応するキー情報について必要であると予測される内容情報登録用の領域の大きさを所定の演算により算出する領域算出ステップと、領域算出ステップにて算出された大きさの領域を、レコード情報における内容情報の登録のために割り当てる領域割当ステップと、判定ステップにおいて連続した空き領域が有ると判定された場合には空き領域に、領域割当ステップにて領域が割り当てられた場合には割り当てられた領域に、それぞれ追加すべきレコード情報における内容情報を登録する登録ステップとをそなえて構成されたことを特徴とする。

0017

更に、領域算出ステップが、出現頻度が少ないキー情報に対しては内容情報登録用として小さい領域を算出する一方、出現頻度が多いキー情報に対しては内容情報登録用として大きい領域を算出することもできる(請求項7)。または、領域算出ステップにおける所定の演算が、インデックスに含まれる全レコード数が増加するにつれて、初めて出現したキー情報に対して算出される内容情報登録用の領域の大きさを減少させることもできる(請求項8)。

0018

他方、請求項9記載のインデックス更新用プログラムが記録されたコンピュータ読取可能な記録媒体は、記憶領域上で管理された、項目となるキー情報とキー情報の内容となる内容情報とにより構成されるインデックスを更新すべく、インデックスに追加すべき情報を、記憶領域に登録する際に、コンピュータに、インデックスに追加すべき情報として、キー情報およびキー情報の内容情報を組とするレコード情報を入力され、入力されたレコード情報に基づき、インデックスの管理情報を更新する管理情報更新手段と、入力されたレコード情報における内容情報を登録すべき記憶領域上の位置を、レコード情報に対応するキー情報に基づき抽出する抽出手段と、抽出手段における抽出の結果得られた記憶領域上の位置に、入力されたレコード情報における内容情報を登録するために必要な大きさの連続した空き領域が有るか否かを判定する判定手段と、抽出手段における抽出の結果、レコード情報における内容情報を登録すべき記憶領域上の位置が抽出できなかった場合、または判定手段においてレコード情報における内容情報を登録するために必要な大きさの連続した空き領域が無いと判定された場合には、レコード情報に対応するキー情報について必要であると予測される内容情報登録用の領域の大きさを所定の演算により算出する領域算出手段と、領域算出手段にて算出された大きさの領域を、レコード情報における内容情報の登録のために割り当てる領域割当手段と、判定手段において連続した空き領域が有ると判定された場合には空き領域に、領域割当手段にて領域が割り当てられた場合には割り当てられた領域に、それぞれ追加すべきレコード情報における内容情報を登録する登録手段として機能させるためのインデックス更新用プログラムが記録されたことを特徴とする。

0019

または、請求項10記載のインデックス管理方法は、項目となるキー情報とキー情報の内容となる内容情報とにより構成されるインデックスの、記憶領域上への記憶状態を管理するインデックス管理方法であって、記憶領域上で管理されるインデックスに追加すべき情報として入力されるキー情報および内容情報の組を単位とするレコード情報に基づいて、記憶領域上で管理されるインデックスに関する管理情報を更新するステップと、入力されるレコード情報に基づいて記憶領域上のインデックスを更新する際に、管理情報を用いて、必要に応じて設定すべき空き領域を算出するステップと、算出された空き領域に基づいて、インデックスを記憶すべき記憶領域を割り当てるステップとをそなえて構成されたことを特徴とする。

0020

または、請求項11記載のインデックス管理用プログラムが記録されたコンピュータ読取可能な記録媒体は、項目となるキー情報とキー情報の内容となる内容情報とにより構成されるインデックスの、記憶領域上への記憶状態を管理するインデックス管理用プログラムが記録されたコンピュータ読取可能な記録媒体であって、インデックス管理用プログラムが、記憶領域上で管理されるインデックスに追加すべき情報として入力されるキー情報および内容情報の組を単位とするレコード情報に基づいて、記憶領域上で管理されるインデックスに関する管理情報を更新するステップと、入力されるレコード情報に基づいて記憶領域上のインデックスを更新する際に、管理情報を用いて、必要に応じて設定すべき空き領域を算出するステップと、算出された空き領域に基づいて、インデックスを記憶すべき記憶領域を割り当てるステップとをそなえて構成されたことを特徴とする。

発明を実施するための最良の形態

0021

以下、図面を基に本発明の実施形態の説明をする。
(a)実施形態の説明
図2は、本発明の実施形態にかかるインデックス管理装置が適用されたシステムの全体構成図であり、この図2に示すシステム1−1は、レコード生成装置20,原文書データベース(以下「原文書DB」と言う)30,管理装置10をそなえて構成される。

0022

レコード生成装置20は、文書ドキュメントを格納する原文書DB30から文書を受け取り、レコード情報を生成して、管理装置10に送出するものである。ここで、レコード情報は、データの構造を項目(キー情報)と文書番号(内容情報)との組により構成されている。また、このレコード情報は、管理装置10にてインデックスの管理に用いられる。

0023

ここで、下記の表1は、本発明の実施の形態にかかるレコード情報の一例を示す表である。

0024

0025

上記表1に示すレコード情報の一例に言及すると、レコード生成装置20は、番号(1)の文書「これは、本です」から複数のレコード情報(〔これ,1〕,〔は,1〕等)を生成して、管理装置10へ送出するようになっている。このため、レコード生成装置20は、文書解析・レコード生成装置21,レコード入力装置22をそなえて構成される。

0026

ここで、文書解析・レコード生成装置21は、項目と文書番号とからなるレコード情報を生成するものである。文書解析・レコード生成装置21は、原文書DB30から読みだした文書から項目を抽出し、抽出した項目と文書番号を組み合わせてレコード情報を生成するようになっている。例えば、文書解析・レコード生成装置21は、日本語,中国語等の分かち書きされていない文書に対して形態素解析を基に単語或いは形態素に分割する処理を施して抽出した項目と、予め原文書DB30に格納する際に各文書に付与する番号とを組み合わせてレコード情報を生成できる。

0027

具体的には、文書解析・レコード生成装置21は、上記表1に示す文書番号2の文書「あれは、本です」を原文書DB30から読みだした後に、抽出した項目(あれ,本等)と文書番号(2)とを組み合わせてレコード情報(〔あれ,2〕,〔は,2〕,〔本,2〕等)を生成する。レコード入力装置22は、文書解析・レコード生成装置21にて生成されたレコード情報を管理装置10に出力するものである。

0028

管理装置10は、レコード生成装置20にて生成された複数のレコードを基にインデックスを管理するものである。ここで、下記の表2は、インデックスの一例を示す表である。

0029

0030

ここで、上記表2に示す〔これ,1,・・・〕等は、それぞれ項目に対して各項目を含んだ文書番号を引くことができるインデックスとして構成されているが、以下においては、上記表2に示すような項目と項目に対する文書番号との組合せを複数含むデータ群をインデックスであることを前提に説明をするが、1つの項目とその項目に対する文書番号との組合せをインデックスとする場合も同様の機能を有する。

0031

尚、文書解析・レコード生成装置21は、原文書DB30からの文書の読み出しを装置システム1−1の保守者等の設計に依存する。ここで、以下においては、文書番号順にレコード情報を生成することを前提に説明をするが、その他の場合も同様である事を意味する。このため、管理装置10は、インデックス管理装置10−1,記憶領域10−2をそなえて構成される。

0032

インデックス管理装置10−1は、項目と文書番号とにより構成されるインデックスの記憶領域10−2上への記憶状態を管理するものであるが、更に、インデックス管理装置10−1は、レコードキー管理装置11と計算・割当装置12をそなえて構成される。ここで、管理情報記憶管理部としてのレコードキー管理装置11は、インデックスに関する管理情報を記憶領域10−2上で管理するものである。

0033

換言するとレコードキー管理装置11は、インデックスに関する統計情報を管理情報として管理するようになっており、具体的には、レコードキー管理装置11は、項目毎の入力レコード情報の数(knum),記憶領域10−2上に記憶されている全ての入力レコード情報の数(N),各項目に対応したレコード情報として追加予定のレコード情報の数(L)(以下において、「暫定登録数」と言う場合がある。)およびインデックスを構成する各項目に対応する内容情報としての文書番号のサイズ情報(krsize)等を記憶するようになっている。

0034

また、レコードキー管理装置11は、各項目,各項目に対する文書番号を記憶する領域のアドレスとしてのポインタ等をも記憶することができるようになっている。ここで、下記の表3は、本発明の実施の形態にかかる管理情報の一例を示す表である。

0035

0036

この表3に示す全文書数(N)は、インデックスを更新するときの管理装置10にてレコード情報が管理される文書数であり、暫定登録予定数(L)は、管理装置10にて管理の対象となり得る文書の予定数であり、全キー数(K)は、管理装置10にて管理されている項目の種類数である。また、下記の表4は、本発明の実施の形態にかかる項目毎の管理情報の一例を示す表である。

0037

0038

ここで、管理情報としての一つの項目に対する文書番号数(knum)は、例えば、上記表4を基に項目「これ」について言えば500であり、500文書に項目「これ」が含まれていることを意味する。また、対項目記憶領域サイズ(krsize)は、項目に対応する文書番号を記憶するに必要な領域サイズであり、例えば、上記表4を基に項目「は」について言えば38000バイトである。ここで、項目「は」を一つ記憶する際に割り当てるのに必要な領域サイズが4バイトであるとともに、キーに対する文書番号数(knum)が9500となっていることから、対項目記憶領域サイズ(krsize)は、数式krsize=9500 × 4=38000 (バイト) となる。

0039

更に、レコードキー管理装置11は、レコード生成装置20からのレコード情報を処理する毎に、上記の管理情報を逐次更新するようになっている。換言すると、レコードキー管理装置11は、記憶領域上で管理されるインデックスに追加すべき情報として入力される項目と文書番号との組を単位とするレコード情報に基づいて、記憶領域10−2上で管理される管理情報を更新する管理情報更新部としても機能するものである。

0040

以下、上記表3,4を基に説明をすすめる。ここで、記憶領域10−2は、レコードキー管理装置11の制御の下で、インデックスを構成する複数の項目の情報及び全文書数(N)等の管理情報を記憶するものであるとともに、各項目に対応した文書番号を記憶するものでもある。このため、記憶領域10−2は、管理情報領域10−2a,文書番号領域10−2bをそなえて構成される。

0041

ここで、管理情報領域10−2aは、インデックスを構成する項目及び領域を割り当てるときに用いる全文書数(N)等の管理情報を記憶する領域である。具体的には、前述の各項目毎の入力レコード情報の数(knum),全文書数(N),インデックスを構成する各項目に対応する1以上の文書番号を記憶するに必要な領域サイズ(krsize)等が、管理情報領域10−2aにて記憶されるようになっている。更に、文書番号領域10−2bとなる領域の範囲を示す情報等も管理情報領域10−2aにて記憶されるようになっている。

0042

文書番号領域10−2bは、各項目に対応した文書番号を記憶する領域である。この文書番号領域10−2b内で文書番号を記憶する態様は、各項目に対応する文書番号を各項目毎に区分けされた連続した領域内に記憶するようになっている。例えば、上記表2に示す項目「本」の文書番号「1,2,・・・」は、文書番号領域10−2b内の項目「本」に対して固有に割り当てられた連続した領域に記憶される。

0043

一方、インデックス記憶管理部としての計算・割当装置12は、インデックスを構成する項目に対応した文書番号を記憶領域10−2上で管理するものである。具体的には、計算・割当装置12は、主として文書番号領域10−2b内に文書番号を記憶する際に、各項目毎に連続した領域を確保するための領域の割り当てや、割り当てる領域サイズを算出するものである。

0044

このため、計算・割当装置12は、領域割り当て計算装置12−1,領域割り当て装置12−2をそなえて構成される。さらに、計算・割当装置12は、文書番号領域10−2b内の項目に対して割り当てられた領域内に文書番号を記憶することができるものでもある。なお、文書番号を文書番号領域10−2b内の割り当てられた領域内に記憶する処理を他の装置が行なうようにすることもできるが、以下においては、計算・割当部12が、文書番号を記憶領域10−2上へ格納する処理を行なうことを前提に説明をする。

0045

領域算出部としての領域割り当て計算装置12−1は、入力されるレコード情報に基づいて記憶領域10−2上のインデックスを更新する際に、レコードキー管理装置11にて管理されている管理情報を用いて、必要に応じて設定すべき空き領域サイズを演算により算出するものである。また、領域割り当て計算装置12−1は、初めて出現したキーに対して初期に割り当てる領域サイズの計算を行なうことができるものでもある。

0046

ここで、領域割り当て計算装置12−1は、以下の数式(1)に基づき初期割り当て領域サイズ(r)を算出するようになっている。
r=n+A×1/log2(N) ・・・(1)
ここで、初期割り当て領域サイズの計算式(1)は、項目に対する1つの文書番号を記憶するに必要な領域サイズ(n)バイト,目安としての全文書登録したときに十分な領域サイズ(以下、「初期割り当て定数」と言う。)A及び処理時点での全文書数Nを用いて割り当てる領域サイズを算出する式となっている。

0047

以下、初期割り当て定数Aは、1024バイトを前提として説明を進めるが、初期割り当て定数Aは、システムの保守者等による設計により他の値を設定することができる。なお、数式(1)は、全文書数(N)が1のとき、換言すると、一番初めの文書を処理するときには、log2(N)=1 として計算することを条件とする。

0048

初期割り当て領域サイズ(r)の計算例として、領域割り当て計算装置12−1は、例えば、1文書目(N=1)で出現した項目に対する1つの文書番号を記憶するのに必要な領域サイズ(n)を4バイトとするキーに対して、数式(1)を用いて初期割り当て領域サイズ(r)を下記の数式(2)に示すように1028バイトと算出するようになっている。

0049

r=4+1028×1/log2(1)
=1028 ・・・(2)
他の初期割り当て領域サイズ(r)の計算例として、領域割り当て計算装置12−1は、例えば、1万文書目で出現した項目に対する文書番号を記憶するに必要な領域サイズ(n)を4バイトとするキーに対して、数式(1)を用いて初期割り当て領域サイズを下記の数式(3)に示すように82バイトと算出するようになっている。

0050

r=4+1028×1/log2(10000)
=82 ・・・(3)
上記の二つの例の初期割り当て計算結果を換言すると、領域割り当て計算装置12−1は、文書数の増大に伴い初期割り当て領域サイズ(r)を減少するような演算を行なうようになっている。

0051

また、領域割り当て計算装置12−1は、出現頻度の少ない項目に対しては文書番号登録用として小さい領域サイズ(r)を算出する一方、出現頻度の多い項目に対しては文書番号登録用として大きい領域サイズ(r)を算出するようになっている。すなわち、この領域割り当て計算装置12−1は、頻繁に出現する単語はある程度の文書数があれば、ほぼ出現してしまうとの統計上の事実を反映して領域サイズ(r)を算出するようになっている。

0052

一方、領域割り当て計算装置12−1は、記憶領域10−2上に文書番号を追加するための領域が不足した場合に、文書番号情報を追加するために必要な空き領域を演算するものでもある。即ち、領域割り当て計算装置12−1は、文書番号領域10−2b内に割り当てられた領域に新規に1つの文書番号を記憶することができないときに、再度割り当てるに必要な領域サイズを演算するようになっている。

0053

具体的には、領域割り当て計算装置12−1は、以下の数式(4)に基づき増分割り当て領域サイズ(r′)を算出する。
r′=n+krsize+(knum/N×krsize)×L/N・・(4)
ここで、増分割り当て領域サイズの計算式(4)は、項目に対する1つの文書番号を記憶するに必要な領域サイズ(n),対項目記憶領域サイズ(krsize),項目に対するレコード情報の数(knum),全文書数(N)及び暫定登録予定数(L)を用いて実際に割り当てるのに必要な領域サイズ(r)を算出する。

0054

なお、計算式(4)中で、(knum/N×krsize)×L/Nは、暫定登録予定数(L)までに必要であると予測される増分の領域サイズを意味する。増分した割り当て領域サイズ(r′)の計算例として、領域割り当て計算装置12−1は、例えば、現時点での処理文書数が10000で出現回数が10回,対項目記憶領域サイズ(krsize)が40バイト,登録予定最大文書数(L)が20000で新規に1つの文書番号を記憶するに必要な領域サイズ(n)が4バイトであるキーに対して、数式(4)を用いて増分した割り当て領域サイズ(r′)を下記の数式(5)のように44バイトと算出するようになっている。

0055

r′=4+40+(10/10000 ×40)×20000 /10000
=44 ・・・(5)
他の増分した割り当て領域サイズ(r′)の計算例として、領域割り当て計算装置12−1は、例えば、インデックスを更新する時点での処理文書数が10000で出現回数が3800回,対項目記憶領域サイズ(krsize)が15200バイトで新規に1つの文書番号を割り当てるのに必要な領域サイズ(n)が4バイトであるキーに対して、数式(4)を用いて増分した割り当て領域サイズ(r′)を下記の数式(6)のように26756バイトと算出する。

0056

r′=4+15200 +(3800/10000 ×15200 )×20000 /10000
=26756 ・・・(6)
上記二つの増分した割り当て領域サイズ(r′)の計算結果を考慮すると、領域割り当て計算装置12−1は、再割当ての領域サイズを計算するに際して、出現頻度の少ない項目に対しては小さい領域サイズ(r′)を算出する一方、出現頻度の多い項目に対しては大きい領域サイズ(r′)を算出するようになっている。

0057

また、領域割り当て計算装置12−1は、再度割り当てるに必要な領域サイズ(r′)を算出する際に、項目の出現頻度数(N),対項目記憶領域サイズ(krsize),登録予定最大文書数(L)等の統計情報に応じて、今後の出現確率を予測し、それに基づいた期待値を増分するときに必要であると予測される領域サイズとして算出するようになっている。

0058

領域割当部としての領域割り当て装置12−2は、領域割り当て計算装置12−1にて算出された空き領域サイズ(r),(r′)に基づいて、インデックスを記憶すべき記憶領域10−2の文書番号領域10−2b内に各項目に対応する文書番号を記憶する領域を割り当てるものである。ここで、図3(a)〜(c)は、本発明の実施の形態にかかる文書番号領域10−2bでの記憶イメージを示す図である。

0059

領域割り当て装置12−2は、領域割り当て計算装置12−1にて初期割り当て領域サイズ(r)或いは再度割り当てるに必要な領域サイズ(r′)を算出された項目に対して、文書番号領域10−2b上の空所リストのいずれかの領域13−1〜13−4を割り当てるようになっている。なお、空所リストの領域13−1〜13−4に関するアドレス,領域サイズ等の情報は、レコードキー管理装置11にて管理情報として管理されるようになっている。

0060

ここで、情報を記憶するに用いられるようになったいずれかの空所リストの領域13−1〜13−4は、それぞれ領域13−1〜13−4内で、領域割り当て計算装置12−1にて計算された領域サイズ(r),(r′)分の領域を用いられるようになっている。その算出された領域サイズ(r),(r′)内に文書番号が記憶される。

0061

図3(a)は、初期割り当て領域サイズを算出された際の記憶イメージを示す図であり、この図3(a)に示す文書番号領域10−2bは、領域割り当て装置12−2にて初期の割り当て領域として空所リストの領域13−1〜13−4中から一つの領域13−1を割り当てられて使用されるようになっている。領域割り当て装置12−2は、空所リストの領域13−1〜13−4中から一つの領域の選択を管理情報を基に行なうようになっている。

0062

例えば、領域割り当て装置12−2は、管理情報を基に、領域割り当て計算装置12−1にて算出された領域サイズ(r),(r′)より大きい空所リストの領域13−1〜13−4を選択するようになっている。この場合、領域割り当て装置12−2は、管理情報としてポインタ等のアドレス情報を用いることができる。

0063

なお、図3(a)〜(c)において、文書番号領域10−2b上の網掛けの部分は、使用中の領域であり、換言すると、キーに対する文書番号を記憶する領域として割り当てられていることを意味する。ここで、換言すると、図3(a)〜(c)中の網掛けを施した使用中の領域は、一つのキーに固有に割り当てられた領域となっている。更に、領域割り当て装置12−2は、各キーに対応する文書番号を連続した領域に記憶するように領域を割り当てるようになっている。即ち、図3(a)〜(c)中に示す網掛けを施した使用中の領域は、一つのキーに対応する文書番号を連続して記憶する領域となっており、例えば、一つの項目「は」に対する文書番号1,文書番号2,文書番号100000等が、連続して記憶されている。

0064

図3(b),(c)は、使用する領域を増分する場合の記憶領域のイメージであるが、図3(a)に示す文書番号領域10−2bの状態から使用する領域を増分するイメージであることを前提にして以下説明する。図3(b),(c)に示す使用中の領域は、初期に割り当てられた領域(図3(a)に示す使用中の領域)では新規に文書番号を追加して記憶する領域が不足するときに、当初割り当てられた領域を連続して拡張した状態を示している。

0065

なお、領域割り当て装置12−2は、拡張分の領域を割り当てるに際して、既に割り当てられている空所リストの領域13−1内で拡張することができないときは、増分した領域を他の空所リスト13−2〜13−4の一つの領域内へ移動して、割り当てるものでもある。ここで図3(c)は、増分した領域を他の空所リストへ移動して割り当てるときの記憶イメージを示す図であり、この図(c)に示す記憶イメージから領域割り当て装置12−2は、領域の増分の態様を拡張するだけでなく、他の領域へ移動して書き換えることによっても領域を割り当てることができるようになっている。

0066

なお、上記の記憶領域上の各項目毎に割り当てられている領域は、レコードキー管理装置11にて項目と,ポインタを対応させて管理情報として記憶されるようになっている。ところで、前記のシステム1−1は、レコード生成装置20と管理装置10として汎用或いは非汎用のコンピュータ等により構築することができるが、さらに、上記のレコードキー管理装置11,文書解析・レコード生成装置21等を具体的なハードウェアと関連付けて述べると、レコードキー管理装置11,領域割り当て装置12−2,領域割り当て計算装置12−1,文書解析・レコード生成装置21等は、中央処理装置としてのCPUに相当し、記憶領域10−2,原文書DB30は、メモリハードディスク磁気テープ磁気ディスク光磁気ディスク等の情報を保持,格納,記録する媒体或いは、その他記憶装置等が該当する。

0067

なお、下記において、管理装置10等が非汎用コンピュータ(以下、コンピュータと言う場合がある。)により構成されているとともに、CPUがレコードキー管理装置11,文書解析・レコード生成装置21等として機能する他、磁気ディスクが記憶領域10−2,原文書DB30に相当する場合を前提にして説明をするが、管理装置10等が汎用コンピュータにより構成されている場合や磁気ディスク以外の媒体により記憶領域10−2が構成されている場合においても同じ事を意味するものである。

0068

上述の構成により本発明の実施の形態にかかるコンピュータの動作について、以下、レコードキー管理装置11等とCPU等と関連付けて、具体的な動作を図4に示すフローチャートを用いて説明する。図4は、本発明の実施形態にかかるコンピュータがインデックスを更新するときの処理の流れを示すフローチャートであり、この図4に示す処理によりCPUは、レコード生成装置20から対象となるレコード情報を入力される(ステップS1)と、項目等に関する管理情報の更新を行なう(管理情報更新ステップS2)。

0069

ここで、CPUは、管理情報として全文書番号数(N),キーに対する文書番号数(Knum)の管理情報を更新する。言い換えれば、CPUは、レコードキー管理装置11として、前記の表3等に示される管理情報を更新して、管理情報領域10−2aに更新後の管理情報を記憶する。

0070

具体的には、CPUは、前記の表3に示す管理情報、例えば、全文書数(N)が1000であるときに、新たに新文書に関するキーが入力された場合は、CPUは、全文書数(N)を1001との情報に更新する。一方、CPUは、レコード情報における項目が初出現であるか否かを判定する(抽出ステップS3)。ここで、CPUは、入力されたレコード情報における文書番号を登録すべき記憶領域上の位置をレコード情報に対応する項目に基づき管理情報から抽出する。換言すると、CPUは、入力されたレコード情報における文書番号情報を記憶する領域が管理されているか否かを判定するようになっている。

0071

項目が初出現である場合は、項目に対して割り当てられた領域は存在しないので、CPUは、必要な領域ならびに暫定登録予定数(L)までに必要になると予測される領域を計算する(領域算出ステップS4)。即ち、領域割り当て計算装置12−1としてのCPUは、初期割り当て領域サイズ(r)の計算を行なう。

0072

ここで、CPUは、暫定登録予定数(L)までに必要であるとの見込みの領域サイズA×1/log2(N) を管理情報を用いて算出する。そして、CPUは、1新規文書番号だけを割り当てるのに必要な領域サイズ(n)に暫定登録予定数(L)までに必要になると予測される領域サイズA×1/log2(N) を加算して、初期割り当て領域サイズ(r)を算出する。

0073

例えば、CPUは、1文書目で出現した項目に対する1つの文書番号を記憶するに必要な領域サイズ(n)を4バイトとするキーに対して、数式(1)を用いて初期割り当て領域サイズ(r)を1028バイトと算出する。一方、CPUは、1万文書目で出現した項目に対する1つの文書番号を記憶するに必要な領域サイズ(n)を4バイトとするキーに対して、数式(1)を用いて初期割り当て領域サイズ(r)を82バイトと算出する。

0074

上記の二つの例の初期割り当て計算結果を換言すると、CPUは、レコード情報を処理する時点での文書数(N)に応じて、キーに対する初期割り当て領域サイズを算出する。即ち、CPUは、インデックスに含まれる全文書数(N)が増加するにつれて、初めて出現したキーに対する初期割り当て領域サイズを算出するに際して、その時点での全文書数(N)が大きければ大きい程割り当てる領域サイズ(r)を減少するように管理情報を用いて演算を行なう。

0075

一方、CPUは、入力されたレコード情報における項目が既に出現しているときは、新規に文書番号を記憶するに十分な領域があるか否かを管理情報を基に判定する(判定ステップS5)。項目が既に出現し、項目に対する管理情報が存在する場合には、CPUは、既に割り当てられた領域が十分であるか否か確かめる。

0076

換言すると、CPUは、管理情報を基に、判定を行なう。例えば、CPUは、管理情報領域10−2aに記憶されている項目毎の文書番号数(knum)や実際に割り当てられている領域サイズを比較して、判定を行なう。ここで、例えばキー「これ」について1つ新規に文書番号を記憶するに必要な領域サイズ(n)が4バイトで、実際に割り当てられている領域サイズ(r)が1024バイト及びキーに対する文書番号数(knum)が200であるときは、実際に割り当てられている領域中に1024−4×200=224バイトの記憶できる領域があることになる。

0077

既に割り当てられた領域では十分でない場合には、CPUは、現在までの項目の出現頻度などに基づき暫定登録予定数(L)までに必要であると予測される領域サイズの計算を再度行なう(領域算出ステップS6)。CPUは、前記の数式(4)に、1新規文書番号だけを割り当てるのに必要なサイズ(n)バイト,対項目記憶領域ドサイズ(krsize),項目毎の入力レコード情報の数(knum),全文書数(N)及び暫定登録予定数(L)等の管理情報を用いて再度割り当てるのに必要な領域サイズ(r)を算出する。

0078

ここで、CPUは、前述の数式(5)に示す増分割り当て領域サイズ(r)の計算例に示すキーの如く、出現頻度が少ない項目に対しては小さい領域を算出する他、前述の数式(6)においては、出現頻度が多い項目に対しては大きい領域を算出する。そして、CPUは、領域を割り当てるのに十分な空領域が空領域中に存在するか否かの空き領域の獲得を行なうための条件判定を行なう(ステップS8)。

0079

具体的にCPU等の処理を前掲図3に示すような記憶領域のイメージを基に説明すると、CPUは、算出された領域サイズ(ステップS4又はS6)に算出された値以上の領域が、文書番号領域10−2bの空所リストの領域13−1〜13−4内に存在するか否かを判断する。算出された値(ステップS4又はS6)以上の領域が文書番号領域10−2bの空所リスト13−1〜13−4に存在する場合は、CPUは、領域割り当て装置12−2として、使用する領域を割り当てる(領域割当ステップS9)。

0080

具体的には、前掲の図3(a)〜(c)に示すように文書番号領域10−2b中で、CPUは、新たに出現したキーに対する文書番号を格納する領域をレコードキー管理装置11が管理する空所リストの領域13−1〜13−4の内の一つの領域を割り当てる。また、図3(b)に示すように、CPUは、再度領域割当てを行なう際に既に使用されている空所リストの領域13−1内で領域を拡張することができるときは、増分する領域サイズ分を拡張前の使用領域後ろに領域を連続するように付け足した態様で領域の再割当てを行なう。

0081

並びに、図3(c)に示すように、CPUは、再度領域割当てを行なう際に、先に割り当てられた空所リストの領域13−1が再度割当てるに必要な領域サイズより小さいときは、条件を満たす他の空所リストの領域内で領域を連続するように割り当てる。他方、領域を割り当てるのに、十分な空領域が空領域中に存在しないときには、CPUは、文書番号領域10−2bの最後尾に領域サイズ分の領域を獲得する(領域割当ステップS10)。

0082

具体的には、CPUは、再度領域を割り当てるに必要な領域サイズの領域が空所リストの領域13−1〜13−4の中に存在しないときに、文書番号領域10−2bの領域外に領域を割り当てる。例えば、前掲の図3(a)〜(c)のイメージ図において、長方形の文書番号領域10−2bの底辺が文書番号領域の最後尾を意味すると仮定するならば、その底辺の下に、再度割り当てるに必要な領域を割り当てる。

0083

即ち、この場合、CPUは、文書番号領域10−2bを拡張する。所望の領域が割り当てられた後、CPUは、旧文書番号と追加文書番号を獲得された領域に記憶する(登録ステップS11)。具体的には、CPUは、初めて出現したキーに対しては、割り当てられた領域中に文書番号を記録する。

0084

一方、CPUは、拡張する態様で領域が割り当てられたときは、割り当てられた領域内で既に記録されている文書番号情報に連続する態様で新規の文書番号を記録する。他方、CPUは、領域が移動する態様で割り当てられたときは、再度割り当てられた領域に先に記憶していた文書番号をコピーして記録するとともに新たに追加して記録する文書番号を連続して記録する(登録ステップS11)。

0085

そして、レコードキー管理装置11としてのCPUは、項目に対する文書番号を記録する文書番号領域10−2b内のアドレスを示すポインタ等の管理情報の更新を行ない、その情報を管理情報領域10−2aに記録する(管理情報更新ステップS12)。並びに、CPUは、新規に文書番号を追加して記憶する領域があると判定した場合(ステップS5)にも、既に記録されている文書番号情報に連続した態様で記録する(登録ステップS7)。

0086

このように本発明の実施の形態にかかるコンピュータによれば、領域割り当て計算装置12−1が、レコードキー管理装置11にて管理して記憶するインデックスに関する管理情報としての統計情報を用いて割り当てる領域サイズを演算により算出して、この算出した値を基に、領域割り当て装置12−2が文書番号を記憶する領域を割り当てるので、過剰に領域を割り当てることを防止して、適切な大きさの領域を割り当てることができる。

0087

更に、本発明の実施の形態にかかるコンピュータによれば、全文書数(N),暫定登録予定数(L),項目毎の入力レコード情報の数(Knum),対項目記憶領域サイズ(Krsize)といった統計情報を管理情報として記憶して領域サイズの演算に用いることでも、過剰に領域を割り当てることを防止して、適切な大きさの領域を割り当てることができる。

0088

更に、本発明の実施の形態にかかるコンピュータによれば、領域割り当て装置12−2が各項目に対応する文書番号を連続した領域に記憶しうるように記憶領域を割り当てることによっても、過剰に領域を割り当てることを防止して、適切な大きさの領域を割り当てることができる。または、本発明の実施の形態にかかるコンピュータによれば、領域割り当て装置12−2が文書番号情報を記憶すべき連続領域を、項目毎に固有に割り当てることでも、過剰に領域を割り当てることを防止して、適切な大きさの領域を割り当てることができる。

0089

一方、本発明の実施の形態にかかるコンピュータによれば、領域割り当て計算装置12−1が記憶領域に文書番号情報を追加するための領域が不足した場合に、文書番号情報を追加するために必要な空き領域を演算するときにも、全文書数(N),項目毎の入力レコード情報の数(Knum)といった統計情報を基に領域サイズの演算を行なうので、過剰に領域を割り当てることを防止して、適切な大きさの領域を割り当てることができる。

0090

他方、本発明の実施の形態にかかるコンピュータによれば、領域割り当て計算装置12−1が出現頻度の少ない項目に対しては文書番号登録用の小さい領域サイズを算出するとともに、出現頻度の多いキー情報に対しては文書番号登録用の大きい領域サイズを算出するので、過剰に領域を割り当てることを防止して、適切な大きさの領域を割り当てることができる。

0091

更に、本発明の実施の形態にかかるコンピュータによれば、領域割り当て計算装置12−1が、インデックスに含まれる全文書番号数(N)が増加するにつれて、初めて出現したキーに対して割り当てる初期割り当て領域サイズの大きさを減少させる演算を行なうので、過剰に領域を割り当てることを防止して、適切な大きさの領域を割り当てることができる。

0092

ところで、本発明の実施の形態にかかるコンピュータは、インデックス更新用のプログラムを実行することによっても前述のCPUをレコードキー管理装置11等として機能させることができる。以下、コンピュータがインデックス更新用のプログラムを実行することに伴うインデックスの管理に関して述べる。

0093

なお、コンピュータは、インデックス更新用プログラムを光磁気ディスク,フロッピーディスク等の磁気ディスク,磁気テープ等の情報を記録する媒体から或いは通信回線等を経由してインデックス更新用プログラムをハードディスクに格納する他、随時通信回線や媒体からインデックス更新用プログラムを読み込む態様でインデックス更新用プログラムを入力する。

0094

コンピュータは、インデックス更新用プログラムを実行する際には、インデックス更新用プログラムをメモリ(図示しない)に展開してCPU(図示しない)が、所望の処理を行なうようになっている。以下、コンピュータが、記録媒体からインデックス更新用プログラムをインストールされる場合を前提に説明をするが、その他通信回線からインストールや随時記録媒体から読み込む等の態様でも同じ事を意味する。

0095

コンピュータは、記録媒体に記録されているインデックス更新用プログラムを読み込んで、CPUが、以下に説明するような、インデックスを管理する処理の制御を施すようになっている。ここで、インデックス更新用プログラムは、コンピュータに、項目と文書番号とにより構成されるインデックスを更新すべく、インデックスに追加すべき情報を、記憶領域10−2に登録する際に、管理情報更新手段,抽出手段,判定手段,領域算出手段,登録手段を実行させるためのコンピュータの処理に適した命令順番付けられた列である。

0096

なお、管理情報更新手段は、コンピュータを、インデックスに追加すべき情報として、項目および文書番号を組とするレコード情報を入力され、入力されたレコード情報に基づき、インデックスの管理情報を更新する(管理情報更新ステップ)ように機能させる手段である。ここで、メモリ上に展開されたインデックス更新用プログラムを実行することで、CPUは、ハードディスクに格納されている管理情報としての全文書数(N)の情報を更新する。

0097

抽出手段は、コンピュータを、入力されたレコード情報における文書番号を登録すべき記憶領域10−2上の位置を抽出する(抽出ステップ)ように機能させる手段である。ここで、メモリ上に展開されたインデックス更新用プログラムを実行することで、CPUは、ハードディスクに格納されている管理情報内に入力レコードの項目に関する情報を検索するためにハードディスクに制御を施す。

0098

判定手段は、コンピュータを、抽出手段における抽出の結果得られた記憶領域上の位置に、入力されたレコード情報の文書番号を登録するために必要な大きさの連続した空き領域が有るか否かを判定する(判定ステップ)ように機能させる手段である。ここで、メモリ上に展開されたインデックス更新用プログラムを実行することで、CPUは、ハードディスクに格納されている管理情報を用いるべく、ハードディスクからメモリに所望の管理情報を読みだすようにハードディスク等を制御する。即ち、CPUは、入力レコードの項目に関する出現頻度(Knum),新規に一つの文書番号を追加するに必要な領域サイズ(n)等の管理情報を用いて、メモリ上で既に割り当てられた領域に新規の文書番号を追加することができるか否かの判定を計算により行なう。

0099

領域算出手段は、コンピュータを、抽出手段における抽出の結果、レコードの項目を登録すべき記憶領域10−2上の位置が抽出できなかった場合、または判定手段においてレコード情報の項目を登録するために必要な大きさの連続した空き領域が無いと判定された場合には、レコード情報の項目に対して必要であると予測される文書番号情報登録用の領域の大きさを所定の演算式により算出する(領域算出ステップ)ように機能させる手段である。

0100

ここで、メモリ上に展開されたインデックス更新用プログラムを実行することで、CPUは、前述の数式(1)或いは数式(4)を基に割り当てる領域サイズ(r)の演算の計算を行なうために、統計情報をメモリに読み出すべくハードディスクを制御する。そして、CPUは、統計情報を基に、所望の領域サイズを求める演算処理を行なう。

0101

領域割当手段は、コンピュータを、領域算出手段にて算出された大きさの領域を、レコード情報の文書番号の登録のために割り当てる(領域割当ステップ)ように機能させる手段である。ここで、メモリ上に展開されたインデックス更新用プログラムを実行することで、CPUは、空所リストの領域13−1〜13−4の領域サイズ等の管理情報を読みだすためにハードディスクを制御し、読み出した管理情報と領域算出手段にて算出された値を基に、割り当てるに適した空所リストの領域が存在するか否かの計算を行なう。

0102

登録手段は、コンピュータを、判定手段において連続した空き領域が有ると判定された場合には空き領域に、領域割当手段にて領域が割り当てられた場合には割り当てられた領域に、それぞれ入力された追加すべきレコード情報の文書番号を登録する(登録ステップ)ように機能させる手段である。ここで、メモリ上に展開されたインデックス更新用プログラムを実行することで、CPUは、入力されたレコード情報の文書番号を所定の領域に記憶するようにハードディスクを制御する。

0103

または、CPUは、領域が移動した場合には、新たに割り当てられた領域に、既に記憶していた文書番号を複写して記憶するとともに、新規に入力されたレコード情報の文書番号をも記憶するようにハードディスクを制御する。並びに、CPUは、初めて出現してキーに対して割り当てた領域に、入力されたレコード情報の文書番号を記憶する。

0104

上記に述べた機能により、コンピュータは、記憶媒体に記憶されているインデックス更新用プログラムを実行することで、文書番号を記憶するに必要な領域を統計情報を基に予測し、不要な領域を省いた適切な領域を割り当てる。従って、コンピュータは、記憶媒体に記憶されているインデックス更新用プログラムを実行することで、過剰に領域を割り当てることを防止して、適切な大きさの領域を割り当てることができる。
(b)その他
前記(a)において、レコードキー管理装置11は、対象となるレコード情報が入力されて(ステップS1)、管理情報の更新を行なう(ステップS2)ようになっている。

0105

ここで、CPUは、管理情報としての全文書数(N)の情報をハードディスクへの格納処理を、更新と同時にすることなく、他のポインタ等の情報を更新する(ステップS12)と同時に処理するようにしてもよい。また、レコード情報が、そのデータの構造を1つの項目と複数の文書番号とにより構成することもできる。この場合においても、インデックスの管理情報を更新することができ得る。

0106

また、上記の如く詳述したが、本発明は、発明の趣旨を逸脱しない範囲で様々な態様で実施を行なうことができる。

発明の効果

0107

以上詳述したように、請求項1,2記載の本発明のインデックス管理装置によれば、領域算出部において、管理情報記憶管理部にて管理される管理情報を用いることにより必要に応じ設定すべき空き領域を演算により算出するとともに、領域割当部において、この算出された値を基に、インデックスを記憶すべき記憶領域を割り当てることができるので、過剰に領域を割り当てることを防止しつつ、入力されるレコード情報の管理情報に応じた適切な大きさの領域を割り当てることができる利点がある。

0108

また、請求項3記載の本発明によれば、領域割当部により、各キー情報に対応する内容情報を連続した領域に記憶しうるように記憶領域を割り当てることができるので、過剰に領域を割り当てることを防止しつつ、適切な大きさの領域を割り当てることができ、ひいては記憶領域の効率的利用を図ることができる利点もある。

0109

さらに、請求項4記載の本発明によれば、領域割当て部により、内容情報を記憶すべき連続領域をキー情報毎に固有に割り当てることができるので、記憶される情報の冗長性をなくし、上述の場合と同様に、過剰に領域を割り当てることを防止しつつ、適切な大きさの領域を割り当てることができ、ひいては記憶領域の効率的利用を図ることができる利点もある。

0110

また、請求項5記載の本発明によれば、領域算出部により、記憶領域に内容情報を追加するための領域が不足した場合に、内容情報を追加するために必要な空き領域を演算するので、上述の場合と同様に、過剰に領域を割り当てることを防止しつつ、適切な大きさの領域を割り当てることができ、ひいては記憶領域の効率的利用を図ることができる利点もある。

0111

一方、請求項6記載の本発明のインデックス更新方法によれば、領域算出ステップにおいて、管理情報を基に、レコード情報に対応するキー情報について必要であると予測される内容情報登録用の領域の大きさを算出する所定の演算を行なうとともに、領域割当ステップにおいて、この算出された値を基に、インデックスを記憶すべき記憶領域を割り当てることができるので、過剰に領域を割り当てることを防止しつつ、入力されるレコード情報の管理情報に応じた適切な大きさの領域を割り当てることができる利点がある。

0112

または、請求項7記載の本発明によれば、領域算出ステップにより、管理情報を基に、出現頻度が少ないキー情報に対しては内容情報登録用として小さい領域を算出する一方、出現頻度が多いキー情報に対しては内容情報登録用として大きい領域を算出するので、上述の場合と同様に、過剰に領域を割り当てることを防止しつつ、適切な大きさの領域を割り当てることができ、ひいては記憶領域の効率的利用を図ることができる利点もある。

0113

または、請求項8記載の本発明によれば、領域算出ステップにおける所定の演算により、インデックスに含まれる全レコード数が増加するにつれて、初めて出現したキー情報に対して算出される内容情報登録用の領域の大きさを減少させるので、上述の場合と同様に、過剰に領域を割り当てることを防止しつつ、適切な大きさの領域を割り当てることができ、ひいては記憶領域の効率的利用を図ることができる利点もある。

0114

他方、請求項9記載の本発明のインデックス更新用プログラムが記録されたコンピュータ読取可能な記録媒体によれば、コンピュータに、領域算出手段として、管理情報を基に、レコード情報に対応するキー情報について必要であると予測される内容情報登録用の領域の大きさを算出する所定の演算を行なうように機能させるとともに、領域割当手段として、この算出された値を基に、インデックスを記憶すべき記憶領域を割り当てるように機能させるので、過剰に領域を割り当てることを防止しつつ、入力されるレコード情報の管理情報に応じた適切な大きさの領域を割り当てることができる利点がある。

0115

また、請求項10記載の本発明のインデックス管理方法によれば、管理情報を入力されるレコード情報に基づいて更新し、インデックスを更新する際に、管理情報を用いて設定すべき空き領域を算出するとともに領域を割り当てるので、過剰に領域を割り当てることを防止しつつ、入力されるレコード情報の管理情報に応じた適切な大きさの領域を割り当てることができる利点がある。

0116

また、請求項11記載の本発明のインデックス管理用プログラムが記録されたコンピュータ読取可能な記録媒体によれば、コンピュータが管理情報を入力されるレコード情報に基づいて更新し、インデックスを更新する際に、管理情報を用いて設定すべき空き領域を算出するとともに領域を割り当てるので、過剰に領域を割り当てることを防止しつつ、入力されるレコード情報の管理情報に応じた適切な大きさの領域を割り当てることができる利点がある。

図面の簡単な説明

0117

図1本発明の原理ブロック図である。
図2本発明の実施形態にかかるインデックス管理装置が適用されたシステムの全体構成を示すブロック図である。
図3(a)〜(c)は、それぞれ本発明の実施の形態にかかる文書番号領域での記憶イメージを示す図である。
図4本発明の実施形態にかかるコンピュータのインデックスを更新するときの処理の流れを示すフローチャートである。

--

0118

1インデックス管理装置
2管理情報記憶管理部
3領域算出部
4 領域割当部
5インデックス記憶管理部
6 領域割当部
10管理装置
10−1 インデックス管理装置
10−2 記憶領域
10−2a管理情報領域
10−2b文書番号領域
11レコードキー管理装置
12 計算・割当装置
12−1領域割り当て計算装置
12−2 領域割り当て装置
13−1〜13−4空所リストの領域
20レコード生成装置
21文書解析・レコード生成装置
22レコード入力装置
30原文書データベース(原文書DB)

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • オムロン株式会社の「 マッチング処理装置」が 公開されました。( 2019/08/08)

    【課題・解決手段】利活用対象のセンシングデータによる容易なセンサマッチングを行うマッチング処理部50が提供される。マッチング処理部50は、提供側端末11により入力された提供側センシングデータを取得する... 詳細

  • オムロン株式会社の「 検索用データ生成装置」が 公開されました。( 2019/08/08)

    【課題・解決手段】センサの検索精度を向上させることができる検索用データ生成装置が提供される。検索用データ生成装置50は、入力された、センシングデバイス20に関連する検索条件301から検索用データを取得... 詳細

  • 三菱電機株式会社の「 情報処理装置および情報処理方法」が 公開されました。( 2019/08/08)

    【課題・解決手段】情報処理装置(10)は、時系列データである入力データを取得するデータ取得部(101)と、時系列データである学習データから抽出した部分列である複数の学習部分列の中で類似する学習部分列を... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ