JPH0574859B2 - - Google Patents

Description

【発明の詳細な説明】 産業上の利用分野 本発明は、データ処理装置と内部記憶装置と外
部記憶装置とで構成される情報検索装置に関する
ものであり、検索情報を外部記憶装置から取りだ
し、内部記憶装置に検索索引として格納した後
に、検索処理を行なう情報検索装置で利用するも
のである。

従来の技術 OAシステム等に用いられる情報検索装置に
は、その外部記憶装置内の検索情報を全て内部記
憶装置内に格納した上で検索処理を行なう内部記
憶検索と、外部記憶装置内の検索情報自体が検索
に適した構造に構成され、検索の度に必要になつ
たインデツクス情報や検索情報を外部記憶装置か
ら内部記憶装置に取り出して検索を行なう外部記
憶検索がある。

従来は殆どの情報検索装置は外部記憶検索を用
いていたが、 １ 半導体メモリの急速な価格低下により、大容
量の内部記憶装置を持つた情報検索装置を安価
に作成できる。

２ OAシステムは会話型処理が中心となり、情
報検索装置のシステム応答時間の速さが重要に
なつてきた。

等の理由により、内部記憶検索も多く用いられて
いる。

以降、内部記憶検索を使つた情報検索装置につ
いてのみ述べる。内部記憶検索方式を取つた情報
検索装置の場合は、次の２つの処理が問題とな
る。

１ 情報検索装置を使用開始する前に（例えば起
動時に）、外部記憶装置内に格納されている検
索情報を内部記憶装置内に転送し、検索処理が
行なえるようにする処理（以下内部記憶装置内
の検索情報（検索索引）の再構成処理または単
に再構成処理と呼ぶ）が必要がある。

２ 情報検索装置に新規の検索情報レコードを追
加する等の検索情報の更新処理時には、内部記
憶装置内の検索情報の更新処理と同時に、この
更新内容を長期的に保持するために、外部記憶
装置内に内部記憶装置内の更新内容に応じた情
報を記憶する処理（以下端に検索情報の更新処
理と呼ぶ）が必要がある。

この２点の処理の処理方式の違いにより内部記
憶検索を用いた情報検索装置の処理効率が決まり
ます。この２点の処理方式は内部記憶装置内と外
部記憶装置内の検索情報の格納形態により、大き
く下記の３つの方式に分けられます。

１ 外部記憶装置内の検索情報も、内部記憶装置
内の検索情報も共に、検索情報レコード毎、例
えば第３図のような一次正規形で格納される場
合 ２ 外部記憶装置内に検索情報が、検索情報レコ
ード毎、例えば第３図のような一次正規形で格
納され、内部記憶装置内の検索情報が、検索に
適した検索索引形式で、例えば第４図のような
逆フアイル形式で格納される場合。

３ 外部記憶装置内の検索情報も、内部記憶装置
内の検索情報も共に、検索に適した検索索引形
式で、例えば第４図のような逆フアイル形式で
格納される場合。

各方式の得失を判断するためには、次の３つの
処理速度を評価する必要がある。

Ａ 内部記憶装置内の検索情報の再構成処理速度 Ｂ 検索処理速度 Ｃ 検索情報の更新処理速度 次に、これら３つの点について上記の各方式の
得失を検討する。

Ａ 情報検索装置を使用開始直前のシステム起動
時等で行なう、内部記憶装置内の検索情報の再
構成処理は、 １と３の方式では、単純に外部記憶装置内の
検索情報形式で、検索情報を内部記憶装置内に
格納するため、外部記憶装置から内部記憶装置
への検索情報の転送処理だけで処理が終了す
る。このため、迅速な再構成処理が期待でき
る。

２の方式では、外部記憶装置内の検索情報を
１レコードづつ取りだし、通常の内部記憶装置
内の検索情報の更新処理と同様な方法で検索情
報の再構成処理を行なう。この再構成処理で
は、内部記憶装置内の検索索引の更新処理を全
ての登録済み検索情報に対して行なうため、
１、３の方式に比べて処理時間が掛かる。

Ｂ 内部記憶装置内に検索情報を再構成した後の
内部記憶装置内の検索情報の検索処理速度を比
較すると、 １の方式では内部記憶装置内も検索情報をレ
コード単位（例えば第３図のような一次正規
形）で格納する。このため、あるキーワードで
検索する場合は、検索情報全体から、そのキー
ワードが属する属性と同じ属性のキーワード群
全てと該当キーワードとが一致するかどうか走
査（調べる）する必要があり、検索処理時間が
かかる。（内部記憶装置内に格納されている検
索情報内もキーワードの重複格納が多く、格納
効率も悪い） ２と３の方式は内部記憶装置の場合は、検索
情報は検索に適した論理構造で、例えば第４図
のような逆フアイル形式等で内部記憶装置内に
格納されるため、最小限のキーワード群の走査
で検索処理が終了するため、１に比べて高速な
検索処理が望める。

Ｃ 内部記憶装置内の検索情報の更新処理速度で
比較すると、 １と２の方式は、内部記憶装置内の検索情報
を更新した後外部記憶装置内に更新要求があつ
た検索情報レコードのみを外部記憶装置に記録
することで処理が終了する。このため高速な更
新処理が期待できる。

３の場合は、内部記憶装置内の更新内容をそ
のまま外部記憶装置内に反映する必要がある。
一般に、内部記憶装置内の検索索引の更新処理
による変更箇所は広範囲に渡る。このため更新
された部分を全て外部記憶装置内に反映するた
めの処理では、多くの分散した検索情報の一部
を外部記憶装置に転送する必要が生じ、１、２
の方式に比べて更新処理速度が低下する。

以上のように上記の３方式はそれぞれ一長一短
があるが、３の方式の欠点である、更新処理時間
の問題は、他の２点に比べて重要度が低く考えら
れているため、外部記憶装置が磁気記憶媒体のよ
うな書き換え可能な媒体の場合は、３の方式（実
際は３の方式の変形）が用いられている。

しかし、外部記憶装置が磁気記憶媒体のような
書き換え可能な媒体の場合は、３の方式を適応で
きるが、光デイスク装置のような追記型の媒体の
場合は書き直しができないため、３の方法を用い
ることが困難であつた。

発明が解決しようとする問題点 以上のように従来の内部記憶検索を用いる情報
検索装置では、以下のような問題点がある。

１ １の方式を用いた場合、検索処理時間と内部
記憶装置内の検索情報の格納効率が悪い。

２ ２の方式を用いた場合、内部記憶装置内の検
索情報の再構成処理速度が遅い。

３ ３の方式を用いた場合、更新処理速度が遅
い。

４ 外部記憶装置に追記型の媒体を利用した場合
は、３の方式を用いることができない。

本発明はかかる点を鑑みてなされたもので、上
記の欠点を克服するために２の方式を採用しつ
つ、２の方式の欠点である内部記憶装置内の検索
情報の再構成処理速度の問題を改善した手段を提
供することを目的としている。

問題点を解決するための手段 本発明は上記の欠点を解決するために以下のよ
うな処理を行なつている。

情報検索装置の検索情報を更新する際は、内部
記憶装置内の検索情報（以下、外部記憶装置内の
検索情報と区別するため検索索引と記述する）と
外部記憶装置内の検索情報を一度に更新する必要
がある。この際内部記憶装置内の検索索引を更新
した際に、その更新処理の経験を利用して、再度
その更新処理を行なう場合に更新処理内の一部の
処理を省略するための情報（例えば更新方法、検
索情報を格納した位置やその格納方法、その他変
更された情報の位置・内容等）を補助情報を作成
し、この補助情報を検索情報とともにレコード単
位で外部記憶装置に記憶する。次に処理速度が問
題となる、内部記憶装置内の検索情報の再構成処
理時には、外部記憶装置から検索情報の格納され
たレコードを１回の更新分づつ順次取りだし、そ
のレコード内の検索情報を用いて内部記憶装置内
の検索索引を更新する処理を補助情報を用いるこ
とにより、通常の更新処理時では必須だつた検索
索引内のキーワードの走査処理等を省いた更新処
理が行え、この更新処理を繰り返すことにより再
構成処理が可能となる。従つて、従来の通常の更
新処理を用いた再構成処理に比べて高速な再構成
処理が実現できるものである。

作 用 本発明は、上記の構成により外部記憶装置に格
納された検索情報を内部記憶装置内の検索索引と
して再構成する際に、通常の更新処理時の処理の
経験を利用して作成された補助情報（内部記憶装
置内への格納方法や格納位置の情報）を用いるこ
とにより、内部記憶装置内に検索索引を再構成す
る処理を、通常の更新処理より簡略化された処理
で行なうことができる情報検索装置であり、従来
困難であつた高速な再構成処理と高度な検索機能
を両立させることができる。

実施例 第１図は本発明の情報検索装置の一実施例を示
すブロツク図である。第１図において、１０２は
外部記憶装置、１０３は内部記憶装置、１０１は
外部記憶装置内の検索情報をレコード毎に取り出
し、内部記憶装置内に検索索引を再構成する情報
形式変換機能、１０４は内部記憶装置１０３内に
格納されている検索索引を用いて検索処理を行な
う情報検索装置、１０５は外部記憶装置内の検索
情報及び補助情報を取り出す情報取出機構、１０
６は取出した情報から補助情報の部分を抜き取る
補助情報抽出機構、１０７は取出した補助情報を
用いて検索情報を格納する位置を決定する情報格
納位置確定機構、１０８は情報格納位置確定機構
で決められた位置に情報を格納し、指定された方
法で内部記憶装置内の検索索引の更新を行なう情
報格納機構である。さらに、１１０，１１１は外
部記憶装置１０２から取り出される情報（検索情
報と補助情報を格納したレコード）、１１２は検
索情報と補助情報に分けられた情報、１１３，１
１４は検索情報とその検索情報の検索索引内の格
納位置、更新方法等を示す情報、１１５は内部記
憶装置１０３内の検索索引を検索した結果であ
る。

第２図は本発明の情報検索装置に対し、検索情
報の更新処理を行ない、これに伴つて作成され、
外部記憶装置１０２に格納される検索情報および
補助情報を格納するレコードフオーマツトの一実
施例を示す図であり、ａは検索情報の領域と補助
情報の領域を分けた例であり、ｂは検索情報に対
応する補助情報とを組にして格納した例である。

第３図は第２図のａのレコードフオーマツトで
情報（検索情報と補助情報）を実際に外部記憶装
置に記憶した場合の一実施例であり、第４図は第
３図内の属性「検索情報１」と部分を内部記憶装
置内に逆フアイル構造に変換して展開した場合の
論理構造の一例を示す図である。

第３図は検索情報を一次正規形で構成している
ため、このままの形式で内部記憶装置内に検索索
引として格納すると検索効率と記憶領域の使用効
率が良くない。従つて本発明の情報検索装置で
は、例えば第４図のような逆フアイル構造に再構
成した上で内部記憶装置内に検索索引を格納す
る。この実施例では一次正規形で外部記憶装置に
格納された検索情報を、逆フアイル構造に変換し
て内部記憶装置に再構成して格納する例について
のみ記載しているが、索引順次編成等の別の検索
に適した論理構造に再構成した上で内部記憶装置
内に格納する実施例も可能である。

第５図は本発明の情報検索装置の異なる実施例
を示すブロツク図である。第５図の上半分は第１
図の実施例と同じ構成をとり、その第１図に検索
情報の更新時の処理を行なう検索情報更新機構５
０５を加えた構成である。検索情報更新機構５０
５内に、検索装置に対して送られてきた更新情報
５３０を受け取り、内部記憶装置内の検索情報を
更新する検索情報変更機構５１３があり、この検
索情報変更機構５１３では、更新情報５３０から
検索情報５３１を取り出し指定された更新方法で
内部記憶装置５０３内の検索索引を更新し、その
結果、更新方法、更新位置等の情報で構成され
る。補助情報を生成するための情報５３２を受け
取り、この補助情報を生成するための情報５３２
と更新情報内の検索情報とを補助情報生成機構５
１２に送る。補助情報生成機構５１２では送られ
てきた情報から補助情報を生成し、送られてきた
検索情報とともに記憶情報編集機構５１１に再転
送する。記憶情報編集機構５１１では送られてき
た検索情報と補助情報を第２図に示したようなフ
オーマツトの情報に編集し、情報記憶機構５１０
に送る。情報記憶機構５１０では転送されてきた
情報を外部記憶装置５０２に記憶する。

第６図は本発明の情報検索装置を光デイスク装
置を外部記憶装置に用いた文書フアイルシステム
に適応した場合のブロツク図である。６０１はシ
ステム全体の制御を行なう制御装置であり、第５
図の情報変換機構５０１及び検索情報更新機構５
０５もこの制御装置内に実現されている。６０２
は追記型の光デイスク装置を用いた外部記憶装置
であり、システムに入力された文書情報や検索情
報を記憶する。６０３は半導体メモリを用いた内
部記憶装置、６０５は文書の入出力を行なう画像
入出力装置、６０４は文書及び検索情報の表示を
行なう画像表示装置である。

第７図は補助情報のフオーマツトの一実施例で
あり、第８図は補助情報のフオーマツトの別の実
施例である。第７図の実施例の場合は５種類の更
新処理を１種類のフオーマツトで表現している例
であり、第８図の場合は３種類の更新処理をそれ
ぞれ別個のフオーマツトで表現している例であ
る。フオーマツトの形式自体は異なつているが、
ともに同様な処理に対する補助情報である。

第９図から第２０図までは、第５図の検索情報
更新機構５０５で行なわれる、更新処理５３０に
対する内部記憶装置５０３内の検索索引の更新処
理とその際同時に行う補助情報の作成処理と、情
報変換機構５０１内で行なわれる、検索情報更新
機構５０５で作成され、外部記憶装置５０２に格
納された各検索情報と補助情報を使つて、内部記
憶装置５０３内に検索索引を再構成する処理とを
対比して説明するための図である。

これらの説明により、実際に第２図のようなフ
オーマツト形式で検索情報と補助情報を格納した
検索情報レコード群を外部記憶装置５０２内に第
３図の様な形式に格納し、第４図で示したような
逆フアイル構造に検索索引を再構成する処理の一
実施方法が理解できる。

ここで、第９図から第２０図までを使つて更新
処理及び補助情報の作成処理と、再構成処理の実
際を説明する前に、この図の説明で前提になつて
いるいくつかの事項について説明する。内部記憶
装置５０３内の検索索引は第４図のような逆フア
イル構造の論理構造が持つが、この逆フアイル構
造については文献（日本コンピユータ協会発行、
「データベース」Martin著、国友義久他訳のペー
ジ613からの「逆フアイル・システム」の章）に
示されている。

ここで説明する例では、外部記憶装置内に第３
図の様な検索情報が格納されており、内部記憶装
置内にこの検索情報を各属性毎の逆フアイル形式
の検索索引が再構成されている。この情報検索装
置に対するキーワード検索は、内部記憶装置内に
検索索引を使つて検索対象キーワードが格納され
たレコード番号群を取り出し、そのレコード番号
群をキーにして外部記憶装置から実際の検索情報
レコードを取り出すことである。

各属性毎の逆フアイル形式の検索索引の論理構
造は、第４図のようにキーワードが論理的にソー
トされた順序で格納されているキーワード領域
と、各キーワードを格納したレコードを参照する
ためのレコード番号群を格納するレコード番号領
域と、論理的にソートされ並んでいる各キーワー
ドのインデツクスが格納されているインデツクス
領域とがある。

各属性毎の逆フアイル形式の検索索引内のキー
ワード領域では、各キーワードは論理的にソート
されているが、物理的にはソートされた順序で連
続していない。論理的な順序は個々のキーワード
を格納するキーワードセル（個々のキーワードと
附属情報格納したブロツク）間のポインタを使つ
て構成されている。

また検索索引内のレコード番号領域には、各キ
ーワード毎にそのレコード番号群を格納するレコ
ード番号セル（複数のレコード番号と附属情報を
格納したブロツク）がある。この検索索引の論理
構造は実際のメモリ内の配置である物理構造とは
異なる。このためこの論理構造を実現する方法
は、多種の格納方法が考えられるが、ここではそ
の一実施例として、下記のような物理構造を持つ
場合の説明を行なう。

各キーワードセルには、キーワード自体の他
に、そのキーワードの論理的に次の順位のキーワ
ードを格納するキーワードセルへのポインタと、
該当キーワードが参照するレコード番号セルへの
ポインタと、その参照するレコード番号の総数が
格納されている。またレコード番号セルには、複
数のレコード番号を格納する領域と、キーワード
の論理順序に添つた順序でレコード番号セルを連
結させるためのポインタとが格納されている。こ
の例の内部記憶装置内のメモリ領域管理の方法を
説明すると、キーワード領域及びレコード番号領
域のメモリ管理を簡単にするため、キーワード領
域、レコード番号領域とも、大きなセグメント単
位では分離されているかもしれないが、基本的に
は連続した領域に格納されている。また、キーワ
ード領域内の空きエリアの管理は、領域の先頭か
ら詰めていくため、現在使用している最終エリア
の次のエリアを指すポインタ（空きキーワード領
域ポインタ）があれば管理できる。レコード番号
領域の場合の空きエリアの管理は、領域の再利用
を考慮しているため、レコード番号領域内の各空
きレコード番号セルをポインタで連結し、その最
初の空きレコード番号セルを指すポインタ（空き
レコード番号領域ポインタ）で管理している。

まとめると、各キーワードセルは論理的な順序
に従つて、ポインタで連結されている。新規のキ
ーワードセルの格納位置は空きキーワード領域ポ
インタで管理される。レコード番号セルはキーワ
ード毎にまとめられた複数のレコード番号を格納
し、キーワードの論理的な順序に従つて、ポイン
タで連結されている。新規のレコード番号セルの
格納位置は空きレコード番号領域ポインタで管理
される。

上記の前提条件を考慮に入れて、以下第９図か
ら第２０図までの各図を用いて、内部記憶装置内
の検索索引の更新処理と再構成処理の詳細を説明
する。各図では再新処理及び再構成処理によつ
て、どのように内部記憶装置内の状態が変化する
かを表している。ここで、各図の見方を説明する
と、各図との３段の横のポインタ列があり、上の
列はキーワード領域内にポインタを使つて論理的
な順序にしたがつて並べられた各キーワードセル
を示し、中の列はレコード番号領域内にポインタ
を使つて論理的な順序にしたがつて並べられた各
レコード番号セルを示し、下の列はレコード番号
領域の空き領域を管理するための、空きレコード
番号セルをつないで作つた空きレコード番号領域
リストを示し、上の列と中の列の間にある空の箱
は空きキーワード領域の先頭を表している。次
に、第９図から第２０図は各々２ページが組とな
つており、奇数ページが更新処理前の検索索引状
態を、偶数ページが更新処理後の検索索引状態を
表している。偶数ページ内の中カツコつき数字
（例えば｛１｝）が第５図の検索情報更新機構で行
う通常の更新処理の場合の処理順序を示し、カツ
コつき数字（例えば(1)）が同じく第５図の情報形
式変換機構５０１で行う補助情報を用いた再構成
処理の場合の処理順序を示している。さらに、こ
こに示す再構成処理が本発明を用いた再構成処理
の一例であり、従来例の再構成処理の場合は、更
新処理と同じ処理を行なうため、ここで、示す通
常の更新処理と補助情報を使つた際構成種の処理
効率の差が、本発明の情報検索装置の効果とな
る。

以下、上記の図の記法に従い、登録処理、削除
処理、変更処理の順で説明していく。

基本的な更新処理の方法としては、検索情報更
新機構５０５内で、更新情報５３０から、各属性
毎の更新対象のキーワードを取り出し、内部記憶
装置５０３内の各属性毎の検索索引に対して更新
処理を行なう。同様に、再構成処理の方法として
は、情報形式変換機構５０１内で、外部記憶装置
５０２から取り出した情報５２０から、各属性毎
の更新対象のキーワードとそれに対応する補助情
報を取り出し、内部記憶装置５０３内の各属性毎
の検索索引を再構成処理を行なう。

更新処理の順序を示すと、下記のように更新処
理内容に応じて、更新処理を選択する処理が必要
になる。

１ 取り出した更新対象のキーワードが、検索情
報内のどの位置に格納されているか、キーワー
ド領域内のキーワードセルリストを走査する
（インデツクスクを使うことで走査対象が絞り
込める。キーワードの有無の確認）。

２ 該当のキーワードを発見した場合に、そのキ
ーワードに対して各種更新処理（第１１図〜第
２０図）を行なう（登録済みキーワードに対す
る更新処理）。

３ キーワードを発見できなかつた場合は、更新
処理の内容が登録処理の場合は、新規キーワー
ドの登録処理（第９図、第１０図）を行なう
（新規キーワードの登録処理）。

４ それ以外の処理の場合は異常処理を行なう。

再構成処理の場合は、補助情報内に各処理方法
が格納されており、どのような更新処理を行う必
要があるかは、分かつているため、上記のような
処理は不要となる。

まず、第９図から第１４図を使つて、キーワー
ドの登録処理を説明する。通常の登録処理の場合
は、まずキーワード領域の検索を行ない、この結
果により該当キーワードが存在しない場合と存在
する場合とにわけ、さらにキーワードが存在する
場合には該当キーワードが管理しているレコード
番号領域内のレコード番号セル内に空き領域があ
る場合とない場合の３つの処理手順に分かれる。

最初に、登録処理の例を検索情報更新機構で行
われる更新処理時と情報形式変換機構で行われる
更新処理時とを対比して説明する。

通常の登録処理は次のような順序で行われる。

１ 登録するキーワードとレコード番号とを外部
からの更新指示として受けとる。

２ 取り出したキーワードを第４図のインデツク
ス領域とキーワード領域を走査することによ
り、該当のキーワードが格納されている位置を
探す。

３ キーワードが発見できなかつた場合は第９
図、第１０図に示す新規キーワードの登録処理
を行なう。

４ 発見した場合は、そのキーワードを用いてい
るレコード番号を格納しているレコード番号領
域へのポインタを辿り、該当キーワードのレコ
ード番号領域に空きがあるかどうか調べる。

５ レコード番号領域に空きがある場合は、第１
１図、第１２図に示したレコード番号の追加登
録処理１を行なう。

６ 空きがない場合は第１３図、第１４図に示し
たレコード番号の追加処理２を行なう。

次に、同じ処理を補助情報を用いた再構成処理
で行う場合は次のようになる。

1′ 登録するレコード番号とキーワードとそのキ
ーワードに対応する補助情報を外部記憶装置内
の検索情報から登録順にレコード単位に取り出
す。

2′ 取り出したキーワードの補助情報の種類の項
目を調べて処理の種類（新規キーワード登録、
レコード番号の追加処理１、レコード番号の追
加処理２のいずれか）を決定する。

3′ 各処理にキーワードと補助情報とレコード番
号を渡し処理を行なう。上記の登録処理の共通
部分のみを見ても、更新処理と再構成処理の作
業量の差異がわかる。2.のキーワード領域内を
走査する処理は処理時間が掛かる。

次に個々の登録処理（新規キーワード登録、レ
コード番号の追加処理１、レコード番号の追加処
理２）の具体的な方法を図を用いて記述する。

新規キーワード登録処理（再構成処理）の場合
（第９図、第１０図）は、次のような順序で行な
われる（処理順序を表す中カツコ数字は第１０図
のそれに対応している）。

｛０｝ 1.2.の処理を行なう ｛１｝ 空きキーワード領域ポインタが示す、空
きキーワードセルの先頭セルに該当キーワード
を格納する。

｛２｝ 2.の処理が失敗した位置の直前のキーワ
ード（論理的にキーワードを挿入する位置の直
前のキーワード）セルの位置を位置情報１とし
て記憶する（この処理は補助情報を作成するた
めの特殊な処理）。

｛３｝ 直前のキーワードのレコード番号へのポ
インタを辿り直前のキーワードセルの管理する
レコード番号の最終セルの位置を位置情報２と
して記憶する（この処理は補助情報を作成する
ための特殊処理）。

｛４｝ 直前のキーワードセル内の次キーワード
セルポインタの情報を登録したキーワードセル
内の次キーワードセルポインタの内容として設
定する。

｛５｝ 直前のキーワードセルの次キーワードセ
ルポインタの情報の内容を登録したキーワード
セルの位置情報に変える。

｛６｝ 登録されたキーワードの数を更新する
（１個増やす）。

｛７｝ 空きレコード番号領域ポインタで示され
た空きレコード番号セルの先頭位置に登録する
レコード番号を格納する。

｛８｝ 空きレコード番号領域ポインタの内容
を、登録したキーワードセル内のレコード番号
セルポインタに設定する。

｛９｝ レコード番号を登録したレコード番号セ
ルの次レコード番号セルポインタの内容を空き
レコード番号領域ポインタの内容に置き換え
る。

｛10｝ 位置情報２を付与したレコード番号セル
の次レコード番号セルポインタの内容をレコー
ド番号を登録したレコード番号セルの次レコー
ド番号セルポインタの内容に置き換える。

｛11｝ 位置情報２を付与したレコード番号セル
の次レコード番号セルポインタの内容をレコー
ド番号を登録したレコード番号セルの位置を示
すポインタ情報に変える。

｛12｝ 補助情報の種類の項目を０にする。（こ
の処理は補助情報を作成するための特殊な処
理） ｛13｝ 登録されたレコード番号の数を更新する
（１個増やす）。

新規キーワードの登録処理（更新処理）は、
1.2.の共通部分の処理のほか上記の処理が必要で
あり、特に2.の処理はキーワード領域内を走査す
るため、処理時間が掛かる。ところで、ここで説
明した｛１｝から｛13｝までの処理の内｛２｝
｛３｝｛12｝の処理は、補助情報を作成するための
特殊な処理であり、補助情報を作成する処理を行
なわない場合は必要ない。新規キーワードの登録
処理（再構成処理）は、次のような順序で行なわ
れる（処理順序を表すカツコつき数字は第１０図
のそれに対応している）。

（０） 共通部分である1′、2′の処理を行う。

(1) 空きキーワード領域ポインタが示す、空きキ
ーワードセルの先頭に該当キーワードを格納す
る。

(2) 補助情報１が示すキーワードセル内の次キー
ワードポインタの情報を、キーワードを登録し
たキーワードセルの次キーワードポインタ情報
の内容に設定する。

(3) キーワードを登録したキーワードセルの位置
情報を、補助情報１が示すキーワードセル内の
次キーワードポインタの内容に設定する。

(4) 空きレコード番号領域ポインタで示された空
きレコード番号セルの先頭位置に登録するレコ
ード番号を格納する。

(5) レコード番号を登録したレコード番号セル内
の次レコード番号セルポインタの情報を空きレ
コード番号領域ポインタの内容に設定する。

(6) 位置情報２が示すレコード番号セル内の次レ
コード番号セルポインタの情報を、レコード番
号を登録したレコード番号セル内の次レコード
番号セルポインタの内容に設定する。

(7) レコード番号を登録したレコード番号セルの
位置を示すポインタ情報を、位置情報２が示す
レコード番号セル内の次レコード番号セルポイ
ンタの内容に設定する。

(8) レコード番号を登録したレコード番号セルの
位置を示すポインタ情報を、キーワード登録し
たキーワードセル内のレコード番号へのポイン
タの内容に設定する。

(9) 登録されたキーワードの数を更新する（１個
増やす）。

(10) 登録されたレコード番号の数を更新する（１
個増やす）。

以上のように時間の掛かる処理である、2.（キ
ーワードの走査処理）を行なう必要がなく、補助
情報が示すセルと新規に登録したセルのポインタ
情報を変えるだけで容易にと処理が終ることが分
る。以上述べたように新規にキーワードの登録処
理の場合、通常の更新処理と補助情報を用いた再
構成処理とを比較すると、上記のように必要な処
理量にはかなりの差があることがわかる。このた
め、システム起動時等に必要となる内部記憶装置
内の検索索引の再構成処理を、補助情報を使つた
再構成処理でなく、通常の更新処理を用いるとす
ると、各レコード番号毎（例えば第６図に示した
文書フアイルシステムに応用した媒体は１万から
２万文書程度の文書が光デイスクに記憶できるた
め、この程度の回数の登録処理が行なわれること
を想定する必要がある）に更新処理を行なう必要
があるため非常に時間がかかり実用にならない。
そこでこの補助情報を使つた再構成処理で、通常
の更新処理を置き換えることで高速な再構成処理
を実現できる。

次に、レコード番号の追加登録処理１（更新処
理）の場合は、第１１図、第１２図に示すよう
に、次のような順序で行なわれる。（処理順序を
表す中カツコ数字は第１２図のそれに対応してい
る）。

｛０｝ 共通処理である、1.、2.の処理を行な
う。

｛１｝ 2.の処理の結果発見した、登録するキー
ワードを格納したセルの位置を、位置情報１と
して記憶する（この処理は補助情報を作成する
ための特殊な処理）。

｛２｝ 4.の処理を行ないレコード番号セル内に
新たなレコード番号を登録する場所を発見す
る。

｛３｝ ｛２｝の処理の結果発見された、登録す
るレコード番号を格納した位置を位置情報２と
して記憶する。（この処理は補助情報を作成す
るための特殊な処理） ｛４｝ 位置情報２の示す位置に登録するレコー
ド番号を格納する。

｛５｝ 登録されたレコード番号の数を更新する
（１個増やす）。

｛６｝ 補助情報の種類の項目を１にする（この
処理は補助情報を作成するための特殊な処理）。

この処理では｛０｝で行なうキーワード領域内
の登録キーワード位置の走査処理と｛２｝で行な
うレコード番号セル内の空き領域を発見するため
の処理に処理時間を食う。

同じ登録処理を補助情報を用いた再構成処理の
場合について記述する。（処理順序を表すカツコ
つき数字は第１２図のそれに対応している）。

（０） 共通処理である、1′、2′を行う。

(1) 位置情報２の示す位置に登録するレコード番
号を格納する。

(2) 位置情報１の示すキーワード領域内にある登
録されたレコード番号の数を更新する（１個増
やす）。

の２つの処理で処理を終了することができ、非常
に高速であることがわかる。

さらに、レコード番号の追加登録処理２（更新
処理）の場合は、第１３図、第１４図に示すよう
に、次のような順序で行なわれる。（処理順序を
表す中カツコ数字は第１４図のそれに対応してい
る）。

｛０｝ 共通処理である、1.2.の処理を行なう。

｛１｝ 2.の処理の結果発見した、登録するキー
ワードを格納した位置を、位置情報１として記
憶する（この処理は補助情報を作成するための
特殊な処理）。

｛２｝ 4.の処理を行ないレコード番号セル内に
新たなレコード番号を登録する場所の発見が失
敗する。

｛３｝ ｛２｝の処理の結果、同一キーワードの
レコード番号セル群の最終レコード番号セル内
の次レコード番号セルポインタの格納位置を位
置情報２として記憶する。（この処理は補助情
報を作成するための特殊な処理） ｛４｝ 空きレコード番号領域指定ポインタの示
す空きレコード番号セルの先頭位置に登録する
レコード番号を格納する。

｛５｝ 新たにレコード番号を格納したレコード
番号セルの次レコード番号セルポインタの情報
を空きレコード番号領域指定ポインタの内容に
設定する（この処理に先だつて空きレコード番
号領域指定ポインタの内容を退避する）。

｛６｝ 位置情報２が示す位置の次レコード番号
セルポインタの内容を、レコード番号を格納し
たレコード番号セル内の次レコード番号セルポ
インタの内容に設定する。

｛７｝ 退避した空きレコード番号領域ポインタ
の情報を、位置情報２が示す位置の次レコード
番号セルポインタの内容に置き換える。

｛８｝ 登録されたレコード番号の数を更新する
（１個増やす）。

｛９｝ 補助情報の種類の項目を２にする（この
処理は補助情報を作成するための特殊な処理）。

この処理では｛０｝で行なうキーワード領域内
の登録キーワード位置の走査処理と｛２｝で行な
うレコード番号セル内の空き領域を発見するため
の処理に処理時間を食う。

同じ登録処理を補助情報を用いた再構成処理の
場合について詳述する。（処理順序を表すカツコ
つき数字は第１４図のそれに対応している）。

（０） 共通処理である、1′、2′を行う。

(1) 空きレコード番号領域ポインタの示す空きレ
コード番号セルの先頭位置に登録するレコード
番号を格納する。

(2) 空きレコード番号領域指定ポインタの情報
を、レコード番号を格納したレコード番号セル
内の次レコード番号領域ポインタの内容に設定
する（この処理に先だつて空きレコード番号領
域指定ポインタの内容を退避する）。

(3) 位置情報２が示す位置の次レコード番号セル
ポインタの情報を、レコード番号を格納したレ
コード番号セル内の次レコード番号セルポイン
タの内容に設定する。

(4) 退避した空きレコード番号領域ポインタの情
報を、位置情報２が示すレコード番号セル内の
次レコード番号セルポインタの内容に設定す
る。

(5) 位置情報１の示すキーワードセル内にある登
録レコード番号数を更新する（１個増やす）。

以上の処理で登録処理を終了することができる
ことができ、処理速度が高速であることが分る。

以上、通常の更新処理と補助情報を用いた再構
成処理の対比を登録処理の例（新規キーワード登
録、レコード番号登録１、レコード番号登録２の
３つの場合）行つた。この結果登録処理の場合、
通常の更新処理に比べ、補助情報を用いた再構成
処理が高速であることがわかる。

次に検索情報の削除を行う処理について述べ
る。検索情報の削除は、削除対象となる検索情報
レコードを削除するために該当検索情報レコード
のレコード番号とレコード内のキーワード群とを
対にした情報の削除処理で行える。第１５図、第
１６図を用いて特定のキーワードの特定のレコー
ド番号を削除する処理を説明していく。ここで用
いる削除処理は実際に領域を開放を伴うものでは
なく、レコード番号を削除マークに置き換えるこ
とによる論理的な削除の例である。またここで削
除されたレコード番号はガーベージコレクシヨン
処理により一括削除が行なえる。この処理につい
ては第１７図、第１８図を用いて説明する。

まず通常の更新処理時の削除処理を説明する。
（処理順序を表す中カツコ数字は第１６図のそれ
に対応している）。

｛１｝ 削除するレコード番号とキーワードを取
り出す。

｛２｝ 取り出したキーワードがキーワード領域
のどの位置に格納されているか走査し、発見す
る。発見できない場合はエラー処理を行なう。

｛３｝ 発見した位置を位置情報１として記憶す
る（この処理は補助情報を作成するための特殊
な処理）。

｛４｝ 当該キーワード領域のレコード番号領域
ポインタを用いてレコード番号セルの先頭を割
だし、レコード番号セル内を削除対象のレコー
ド番号が格納されている位置を走査する。

｛５｝ ｛４｝の処理の結果、削除マークを、発
見したレコード番号セル内の削除対象レコード
番号の位置に設定する。

｛６｝ 削除されたレコード番号の数を更新する
（１個減らす）。

｛７｝ ｛５｝で削除マークを設定した位置を位
置情報２として記憶する（この処理は補助情報
を作成するための特殊な処理）。

｛８｝ 補助情報の種類の項目を３にする（この
処理は補助情報を作成するための特殊な処理）。

この処理でも｛２｝で行なうキーワード領域内
の削除キーワード位置の検索情報と｛４｝で行な
うレコード番号セル内の削除対象のレコード番号
を発見するための処理が時間を食う。

次に補助情報を用いた再構成処理時の削除処理
について記述する（処理順序を表すカツコつき数
字は第１６図のそれに対応している）。

(1) 位置情報２の示す位置に削除マークを格納す
る。

(2) 位置情報１の示すキーワードセル内にある登
録されたレコード番号の数を更新する（１個減
らす）。

以上の処理で削除処理を終了することができ、
処理速度が非常に高速であることがわかる。

さらに、第１７図、第１８図を用いてレコード
番号の削除処理用の補助情報を用いた特殊な処理
としてガーベージーコレクシヨン処理に削除時の
補助情報を用いた例を説明していく。

(1) 位置情報１の示すレコード番号セル内の位置
情報１の位置以降に、レコード番号が登録され
ているか調べる。ない場合はの位置情報１の削
除マークを消して終了。

(2) ある場合は１個づつレコード番号を前にづら
す。

(3) 最後のレコード番号セル内にレコード番号が
あるかどうか調べる。ない場合は最終レコード
番号領域の次レコード番号セルポインタの内容
を直前の次レコード番号セルポインタの内容に
置き換える。あつた場合は終了。

(4) 空きレコード番号領域ポインタの内容を最終
レコード番号セルの次レコード番号領域指示ポ
インタの内容に置き換える。

(5) 空きレコード番号領域ポインタの内容を最終
レコード番号セルの位置情報に置き換える。

以上の処理でレコード番号セル内の削除マーク
を総当たり的に調べることなしでガーベージーコ
レクシヨン処理を高速に行なうこともできる。従
つて本発明の補助情報を作成しそれを更新処理に
用いる本発明の用途は起動時の検索情報の展開処
理に限定されるものではなく、一般的なデータ構
造の変更処理にも利用できることが分る。

さらに、第１９図、第２０図を用いてレコード
番号の変更処理の場合を説明する。更新処理は次
のような順序で行なわれる（処理順序を表す中カ
ツコ数字は第２０図のそれに対応している）。

｛１｝ 変更するレコード番号と新たなレコード
番号とキーワードとを取り出す。

｛２｝ 取り出したキーワードがキーワード領域
のどの位置に格納されているか走査し、発見す
る。発見できない場合はエラー処理を行なう。

｛３｝ 新たなレコード番号自体を位置情報１と
して記憶する（この処理は補助情報を作成する
ための特殊な処理）。

｛４｝ 該当キーワードセル内のレコード番号セ
ルポインタを用いて先頭のレコード番号セルを
取り出し、レコード番号セル内の変更対象のレ
コード番号が格納されている位置を走査する。

｛５｝ ｛４｝の処理結果、発見したレコード番
号セル内の変更対象レコード番号の位置を、位
置情報２として記憶する（この処理は補助情報
を作成するための特殊な処理）。

｛６｝ 位置情報２の位置に新たなレコード番号
を格納する。

｛７｝ 補助情報の種類の項目を４にする（この
処理は補助情報を作成するための特殊な処理）。

この処理でも｛２｝で行なうキーワード領域内
の削除キーワード位置の検索処理と｛４｝で行な
うレコード番号セル内の削除対象のレコード番号
を発見するための処理が処理時間を食う。

次に補助情報を用いた再構成処理時のレコード
番号の変更処理について記述する（処理順序を表
すカツコ付け数字は第２０図のそれに対応してい
る）。

(1) 位置情報２の示す位置に位置情報１を格納す
る。

以上の処理で処理を終了することができ、処理
速度が非常に高速であることが分る。

以上内部記憶装置内の検索索引のいろいろな更
新処理について、第７図に示した補助情報フオー
マツトを用いた例で、通常の更新処理と補助情報
を用いて行なつた再構成処理を対比させながら説
明してきた。第８図をはじめとして他の補助情報
フオーマツトを用いた場合も同様な処理が可能で
ある。

以上まとめると、内部記憶装置内の検索索引の
更新時に補助情報を作成し、この補助情報を検索
情報とともに外部記憶装置内に記憶し、内部記憶
検索を用いる情報検索装置のシステム起動等で必
要となる、内部記憶装置内の検索索引の再構成処
理（検索に適したフオーマツトに内部記憶装置内
の検索索引を展開すること）が、この検索情報と
補助情報を使つて行なうことにより、通常の更新
処理を行なう場合に比べて高速行なうことができ
る。これは特に第６図に示したような文書フアイ
ルシステムの情報検索装置に応用した場合、高速
かつ高度な検索処理機能と高速システム起動処理
の２つを同時に満たすことができ、非常に有効な
内部記憶検索方式の情報検索装置を構成できる。

発明の効果 以上述べてきたように、本発明によれば、情報
検索装置に更新情報が追加された際、内部記憶装
置内の検索索引の再構成処理を効率化させる補助
情報と検索情報とを外部記憶装置に記憶し、この
検索情報と補助情報を用いることにより、内部記
憶装置内は検索に適した論理構造を採りつつ、外
部記憶装置内の検索情報を内部記憶装置内の検索
索引に再構成する処理を通常の更新処理を行なう
場合に比べて高速に行なうことが可能にするもの
である。これにより、高速かつ高度な検索処理機
能と高速なシステム起動処理の２つを同時に満た
した内部記憶検索方式の情報検索装置が実現でき
る。

【図面の簡単な説明】

第１図は本発明の情報検索装置の一実施例を示
すブロツク図、第２図は本発明の情報検索装置に
おいて１回の更新処理に伴つて作成され、外部記
憶装置１０２に格納する検索情報および補助情報
フオーマツトの一実施例を示す図、第３図は第２
図のａの情報を実際に外部記憶装置に記憶した場
合の一実施例を示す図、第４図はその情報の検索
情報１の属性の部分を内部記憶装置内に逆フアイ
ル構造に変換して展開した場合の論理構造を示す
図、第５図は本発明の異なる実施例の情報検索装
置のブロツク図、第６図は本発明の一実施例を応
用した文書フアイルシステムの概念図、第７図は
補助情報フオーマツトの一実施例を示す図、第８
図は補助情報フオーマツトの別の一実施例を示す
図、第９図から第２０図までは更新処理を説明す
るためのキーワード領域とレコード番号領域での
更新処理内容を示す図、第２１図は従来例の情報
検索装置のブロツク図、第２２図は従来例で外部
記憶装置内に検索情報を一次正規形で格納した図
である。 １０１……情報形式変換機構、１０２……外部
記憶装置、１０３……内部記憶装置、１０４……
情報検索機構、１０５……情報取出機構、１０６
……補助情報抽出機構、１０７……情報格納位置
確定機構、１０８……情報格納機構、１１０，１
１１……外部記憶装置から取り出される情報、１
１２……検索情報と補助情報に分けられた情報、
１１３，１１４……検索情報とその格納位置、方
法等を指示する情報。

Claims (1)

1. 【特許請求の範囲】 １ 論理的な単位であるレコード毎にデータを格
   納した検索情報を保持する外部記憶装置と、前記
   検索情報の索引情報を保持する内部記憶装置と、
   前記検索情報から索引情報を作成する手段であつ
   て、前記索引情報の再生の際には、検索情報をレ
   コード毎に取りだし、前記レコード毎の検索情報
   内に記憶された更新データと、追加、削減または
   変更のいずれかである更新データの更新方法と更
   新位置の情報を用いて、前記索引情報内の該当す
   る更新位置をその更新データで更新することによ
   り索引情報の作成を行なう索引情報作成手段と、
   前記索引情報を検索し、対応するデータを前記検
   索情報から抽出する情報検索手段と、検索情報の
   追加、削除または変更要求に応じて前記索引情報
   と前記検索情報を更新する手段であつて、検索情
   報の更新要求と更新データを入力した際には、前
   記更新データの前記索引情報内の更新方法と更新
   位置に関する情報を求め、その結果に基づき前記
   索引情報を前記更新データで更新し、かつ、前記
   検索情報に前記更新データと前記更新方法と更新
   位置に関する前記情報を記憶する検索情報更新手
   段とを有することを特徴とする情報検索装置。 ２ 索引情報更新手段は、検索情報の更新要求と
   更新データを入力した際には、前記更新データの
   索引情報内の更新方法と更新位置を求め、その結
   果に基づき前記索引情報を前記更新データで更新
   し、かつ、前記検索情報に前記更新データと更新
   方法と更新位置に関する情報を記憶した後、一定
   個数の更新要求を処理した場合は、索引情報全体
   と検索情報内の最終記録した検索情報レコードの
   位置情報とを外部記憶装置に記憶し、索引情報作
   成手段は、前記索引情報の再生の際には、前記最
   終記録した検索情報レコードの位置情報が示す位
   置以降の検索情報を外部記憶装置からレコード毎
   に取り出し、前記レコード毎の検索情報内に記録
   された更新データと更新データの更新方法と更新
   位置に関する情報を用いて、前記索引情報内の該
   当する更新位置をその更新データで更新すること
   により索引情報の作成を行なう特許請求の範囲第
   １項記載の情報検索装置。 ３ 外部記憶装置が追記型記録媒体であることを
   特徴とする特許請求の範囲第１項又は第２項記載
   の情報検索装置。