JPH06332947A - データ記憶再生方法及びその装置 - Google Patents

Abstract

(57)【要約】 【目的】 大量の文書データを蓄えた２次記憶装置から
検索用のインデックス情報を付与することなしに要求さ
れた文書データを引き出してくる全文検索装置に関する
もので、特に全文検索の本文を連想する内容番地記憶型
の連想表をファイルの物理的連続性を保ち高速に効率良
く生成管理すること。 【構成】 予めファイルシステム１に２つ以上の予約領
域を確保し、第１番目の領域には固定容量でエントリや
フラグやポインタをおき第２の領域には可変容量で追加
を容易にしている。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、大量の文書データを蓄
えた２次記憶装置から検索用のインデックス情報を付与
することなしに要求された文書データを引き出してくる
全文検索方式を基本とした検索方法及び検索装置に関す
るものである。

【０００２】

【従来の技術】近年、ワードプロセッサーやパーソナル
コンピューターの普及により大量の文書データが仕事場
や家庭において流通利用される状況になってきた。この
大量の文書データを整理して有効に利用していくため
に、大容量データベースと高速検索マシンが研究開発さ
れている。しかし、従来の検索マシンでは検索用にイン
デックス情報を付ける必要があり、データ量が増大する
につれてこのインデックス付け作業に大変な労力が必要
となってきた。これに対して、前記インデックス情報を
つける作業を必要としない方法として、前記インデック
ス情報なしにこの大量の文書データの中から的確かつ高
速に所望の文書データを探し出すことができる全文検索
方式に基づく検索装置が発表されている。例えば、１９
７０年スロトニック（Slotnick,D.L.）が提案したロジ
ック・パー・トラックディスクは、２次記憶装置の一種
であるディスクの各ヘッドに検索専用のプロセッサーを
付加し、検索条件を満足した情報だけをホストコンピュ
ーターに転送することにより検索の高速化を試みたもの
であり、具体的な装置としてトロント大学のＲＡＰ等が
実現している。一方、また全文検索用テキストサーチマ
シンの研究の例としては、「K.Murai et.al.: Jpn. J.
Appl. Phys. Vol.31(1992), pp.680-687, Part1, No.
2B, February 1992, Index-Free Full-Text Search F
unction Installed into Optical Disk Drive」等があ
り、原文書の文字連接情報を用い、検索語に含まれる文
字連接を含む文書を候補として引く内容番地記憶の表の
形の連想記憶を用い、候補とされた文書ファイルをハー
ドウェアで高速に全文検索して実際に検索語が含まれて
いるかをチェックする構成により、高速な全文検索を実
現している。

【０００３】

【発明が解決しようとする課題】しかしながらこのよう
な連想記憶構造を文字連接を用いて実際のコンピュータ
ファイル上で実現しようとしても、ディレクトリ管理さ
れている文書ファイルを矛盾なく管理するのは容易では
なく、最も時間のかかる記憶ファイル装置のファイルの
読みだしをセクタの連続性を確保して効率的でかつ小容
量かつ高速に候補文書ファイルを候補として提示するこ
とは困難であった。

【０００４】本発明ではこれら従来の装置においては効
率が悪く、また検索速度的にも十分でなかったのもの
を、効率的な内容番地記憶連想方法で小型高性能な検索
装置を提供することを目的とする。

【０００５】

【課題を解決するための手段】上記問題点を解決するた
めに本発明の内容番地記憶検索方法は、記憶装置に蓄え
られた文書データを読み出し、適当な文書量毎に識別名
称を付与し、かつその文書データの内容を調べ、文字ｉ
に連接する文字ｊの文字並びを抽出して内容番地記憶構
造の表として書き込んでおき、この書き込みの際には、
予め特定の文書に関し、文字ｉと連接する連接文字ｊの
統計的出現情報を得て、単位文書あたりに出現する文字
ｉと文字ｊの連接文字の組み合わせ数を予測して文字ｉ
毎の連接種類数に応じて確保した第１の領域に文字ｉに
連接する文字種ｊを前記記憶ファイル装置の位置情報と
ともに記録する書き込み、また文字連接の文字種類によ
らない別の第２の文字連接初期予約領域を確保してお
き、もし最初に文字ｉについて確保されていた第１の初
期予約領域を越えてしまった場合はこの領域を廃棄ない
しは移動して、第２の記録領域に文字種ｉに対応した予
測記録領域を新たに確保して文字ｉに連接する文字種ｊ
を前記記憶ファイル装置の位置情報とともに記録する。
この時第１の文字連接初期予約領域に文字連接が書き込
まれているのか、また第２の初期予約領域の特定位置に
文字連接が書き込まれているのかは、例えば第１の初期
予約領域に識別符号を書いておき、最初に第１の初期予
約領域をまず見るようにして知る。

【０００６】次に検索要求者から出された検索文字列
（例えば検索単語）とそれらの検索論理式を受け付け、
それら検索文字列を調べて文字並びの文字ｉを先頭と
し、引き続く文字ｊがどのようなものであるかを知って
先ほどの第１の初期予約領域、次にもし識別符号が存在
すればポインタに従って第２の初期予約領域を読んで、
文字ｊが含まれて検索文字列の連接文字並びがすべて含
まれているもの（ＡＮＤ）の位置情報（識別名称）を持
つ文書ファイルを検索候補として選び、記憶ファイル中
の実際の記録場所を得て全文検索する。

【０００７】本発明は、基本的に先行技術である全文検
索用テキストサーチマシンと同様に内容番地記憶による
連想検索方式を採用したものであるが（表と記述）、本
発明においてはこの連想表を構築していく際にディスク
ファイル中の連続性を考慮し、文書ファイル本文の増加
に対応して連想表の記録領域を確保することが可能な構
成となっている。

【０００８】

【作用】本発明によれば上記のように予め記録文書デー
タの文字ｉをエントリとする文字連接の連想表を作って
おき、データメモリ回路、文字検索回路とを具備して、
ホストコンピューターからの要求を受け付けて記憶ファ
イル装置から読み出された文書データが、この表を引い
て検索文字列と同一の文字並びがあるかどうか調べ、も
しあったなら文書記録場所に対応する識別名称を得、記
憶ファイルの記録場所のディレクトリエントリを得る。
この時の文字連接の連想表は記憶ファイル内で少なくと
もディレクトリエントリ毎に可能な限り連続配置させる
ことができ、記憶ファイル装置のアクセスが少なくな
り、検索の高速化が可能となる。

【０００９】

【実施例】以下本発明の実施例を図面を用いて詳細に説
明する。

【００１０】図１は本発明の内容番地記憶検索装置の構
成図である。図１において、１は大量の文書データを蓄
えておく２次記憶装置であり、２は文字列の一致を検出
するデータマッチング回路であり、３はホストコンピュ
ータである。

【００１１】図２は前記２次記憶装置のデータ記憶内容
であり、４は予め文字ｉと連接する連接文字ｊの特定の
文書に関する出現頻度予測した文字連接出現頻度情報の
記録領域、５は単位文書あたりに出現する文字ｉと文字
ｊの連接文字の組み合わせの連接種類数に対応した大き
さの文字ｉ個分の領域を初期設定する第１の文字連接初
期予約領域、６は第２の文字連接初期予約領域、また７
は第３の初期予約領域である。第３の初期予約領域には
検索対象となる文書が格納される。

【００１２】図３は連接情報の書き込み手順を示すフロ
ーチャートである。以上の様に構成された検索装置にお
いて、図１、図２、図３を用いて動作を説明する。ホス
トコンピュータ３の要求に従い第３の初期予約領域７か
ら文書データを読みだし、２文字（ｉ，ｊ）の連接が対
応する文書ファイルに存在するか調べ分類する。この時
同一の連接があった場合には重複しているとして削除す
る。第１の文字連接初期予約領域の先頭に書き込まれて
いるフラグ情報を読み取り、もし２文字（ｉ，ｊ）の連
接が第１の文字連接初期予約領域５に書き込む余裕があ
ると判定されるならこれを書き込み、もしそうでないな
らポインタ情報を読み取り、第２の文字連接初期予約領
域６に文字ｊと文書ファイル番号を書き込む。もし第２
の文字連接予約領域に未だ文字ｉに対応する領域が確保
されていないなら、現時点での出現頻度から計算して領
域を確保するととも第１の領域の対応するデータをコピ
ーし、フラグ情報を変更して新たに作成した領域のポイ
ンタを書き込む。

【００１３】検索時にはホストコンピュータ３の検索文
字列の検索要求に従い検索文字列の文字連接を一組以上
得て、２次記憶装置に格納されている各々の先頭文字ｉ
に対応する第１の文字連接初期予約領域先頭のフラグ情
報を読み取り、このまま初期予約領域のデータを読み取
るべきか、あるいは第２の文字連接初期予約領域のデー
タを読み取るべきかを決定する。文字ｉをエントリとす
る格納内容の中にもし文字ｊが含まれているならば対応
する文書番号を読み取った後、対応するディレクトリエ
ントリの第３の文書ファイルを読み取り、データマッチ
ング回路２で真に検索文字列が含まれているかをしら
べ、対応する文をユーザに提示する。

【００１４】次に別の実施例を図と共に示す。図４は第
１の文字連接初期予約領域５を非常に少なく確保したも
のであり、２次記憶装置１内に確保されると共にホスト
コンピュータ３の主記憶にコピーされる。このことによ
り、文字連接データ書き込み時は主記憶を主にアクセス
し、主記憶が溢れた時点で２次記憶装置の領域に転送さ
れる。

【００１５】図５は２次記憶装置１内に確保され、ホス
トコンピュータ３の主記憶にコピーされるセクター使用
状況管理のフラグ情報を図示したものである。これは予
め領域を確保していない文字連接記録領域に連続的に領
域確保するため、物理的に連続領域が確保できるかどう
かをこの管理情報を読み取って調べ確保するのである。

【００１６】次に別の実施例を図６と共に示す。図６に
おいて８は統計データにより予め高頻度に発生すること
が予想される文字連接の先頭文字に対応する領域と特定
の文字によらない予備領域である。

【００１７】また９は文書データ領域であり、５の第１
の文字連接初期予約領域にも予め統計データにより高頻
度に発生すると予測される文字連接に対しては、フラグ
情報と対応する第２の文字連接初期予約領域へのポイン
タを書きこんでおく。

【００１８】次に別の実施例を図７と図８と共に示す。
図７では２次記憶に記録されている文書の概略位置を与
える文書番号と実際の文書ファイルの記憶領域について
示している。文書ファイルはそれぞれ大きさが異なるわ
けだが、いま仮想的な文書番号を考える。ここで１セク
ターを８ＫＢとし、ファイルシステムが２セクタの１６
ＫＢで１クラスタ単位でファイルを管理しているとする
と、文書Ａ、文書Ｂ、文書Ｃ、文書Ｄはすべて１クラス
タ以内なので、あまった領域を含めて連続に配置されて
いるとするとこれらをまとめ６４ＫＢ毎に一つの文書番
号ｍを付与する。また大きな文書ファイルＥについては
分割して複数の文書番号ｎとｎ＋１を付与する。

【００１９】図８はこの文書番号とファイルシステムと
の管理テーブルで、２次記憶の文書記録位置の概略番地
を示す文書番号は、固定領域にて詳細情報へのポインタ
と分割や連結等の情報を示すフラグと共に記録されてい
る。連想表に連接文字ｊと共に記録されている文書番号
を得たならば、簡単な計算で詳細情報の先頭記録番地を
得ることができ、実際の文書ファイルはファイル名等を
参照して具体的に得ることができる。

【００２０】次に別の実施例を図９と共に示す。図９は
文書番号とファイルシステムとの管理テーブルであり、
１０は「文書番号２」を付与されたファイルシステムの
ディレクトリ番号である。このディレクトリ番号に通常
ありえないＦＦＦＦＨの値を書き込んでいる。これはも
しある文書ファイルをファイルシステムで削除してしま
うと、虫食いのように空いた領域にまた追加した文書が
記録されてしまい、ファイルの連続性が保てなくなるた
めである。ここでは実際のファイルは消去せず、管理テ
ーブル上のみで削除している。

【００２１】なお本発明は上記実施例に限定されるもの
ではなく、本発明の主旨に基づいて種々の変形が可能で
あり、これらを本発明の範囲から排除するものではな
い。

【００２２】

【発明の効果】以上、詳細に説明したように、本発明に
よれば次のような効果を得ることができる。

【００２３】(1)光ディスクや磁気ディスクに代表され
る２次記憶ではアクセス時間が最も問題になるが、ファ
イルシステムは通常物理的な連続性まで考慮していな
い。

【００２４】このため特に最初に領域を確保した状態で
セクタの連続性を確保することができ、この後、特に専
用のファイル管理を行うことにより内容番地記憶による
高速検索に最も適したファイル構造を作りあげることが
できる。

【００２５】(2)通常のファイルシステムと検索の為の
管理が自然に行うことが出来、簡単かつ効率のよい検索
が可能になる。

【図面の簡単な説明】

【図１】本発明の一実施例における内容番地記憶検索装
置の構成図

【図２】本発明の一実施例における２次記憶装置のデー
タ記憶内容を示す図

【図３】本発明の一実施例における連接情報の書き込み
手順を示すフロー図

【図４】本発明の別の一実施例における２次記憶装置の
データ記憶内容を示す図

【図５】本発明の別の一実施例における記憶ファイルの
使用状況管理のフラグ情報内容を示す図

【図６】本発明の別の一実施例における２次記憶装置の
データ記憶内容を示す図

【図７】本発明の別の一実施例における文書番号と文書
ファイルの分割・結合関係を示す図

【図８】本発明の別の一実施例における文書番号と文書
ファイルの管理関係を示す図

【図９】本発明の別の一実施例における文書番号と文書
ファイルの管理関係を示す図

【符号の説明】

１ ２次記憶装置 ２ データマッチング回路 ３ ホストコンピュータ ４ 文字連接出現頻度情報の記録領域 ５ 第１の文字連接初期予約領域 ６ 第２の文字連接初期予約領域 ７ 第３の初期予約領域 ８ 第２の文字連接初期予約領域 ９ 文書データ領域 １０ 削除対象となっているファイルシステムのディレ
クトリ番号

Claims (7)

【特許請求の範囲】
1. 【請求項１】記憶装置に蓄えられた文書データを読み出
   し、適当な文書量毎に識別名称を付与し、かつその文書
   データの内容を調べ、文字ｉに連接する文字ｊの文字並
   びを抽出して内容番地記憶構造の表として書き込んでお
   き、この書き込みの際には、予め特定の文書に関し、文
   字ｉと連接する連接文字ｊの統計的出現情報を得て、単
   位文書あたりに出現する文字ｉと文字ｊの連接文字の組
   み合わせ数を予測して文字ｉ毎の連接種類数に応じて確
   保した第１の領域に文字ｉに連接する文字種ｊを前記記
   憶ファイル装置の位置情報とともに記録する書き込み、
   文字連接の文字種類によらない別の第２の文字連接初期
   予約領域を確保しておき、もし最初に文字ｉについて確
   保されていた第１の初期予約領域を越えた場合はこの領
   域を廃棄ないしは移動して、第２の記録領域に文字種ｉ
   に対応した予測記録領域を新たに確保して文字ｉに連接
   する文字種ｊを前記記憶ファイル装置の位置情報ととも
   に記録し、第１の文字連接初期予約領域に文字連接が書
   き込まれているのか、また第２の初期予約領域の特定位
   置に文字連接が書き込まれているのかは、例えば第１の
   初期予約領域に識別符号を書いておき、最初に第１の初
   期予約領域を読みとり、次に検索要求者から出された検
   索文字列（例えば検索単語）とそれらの検索論理式を受
   け付け、それら検索文字列を調べて文字並びの文字ｉを
   先頭とし、引き続く文字ｊがどのようなものであるかを
   知って先ほどの第１の初期予約領域、次にもし識別符号
   が存在すればポインタに従って第２の初期予約領域を読
   んで、文字ｊが含まれて検索文字列の連接文字並びがす
   べて含まれているもの（ＡＮＤ）の位置情報（識別名
   称）を持つ文書ファイルを検索候補として選び、記憶フ
   ァイル中の実際の記録場所を得て全文を検索するデータ
   記憶再生方法。
2. 【請求項２】文書等のデータを記憶する記憶装置と、デ
   ータマッチング回路手段と、予め文字ｉと連接する連接
   文字ｊの特定の文書に関する出現頻度予測情報を得て、
   前記記憶装置に単位文書あたりに出現する文字ｉと文字
   ｊの連接文字の組み合わせの連接種類数に対応した大き
   さの、文字ｉ個分の領域を初期設定する第１の文字連接
   初期予約領域を確保する第１の確保手段と、前記記憶装
   置に文字種類によって初期分割されていない前記とは別
   の第２の文字連接初期予約領域を確保する第２の確保手
   段と、前記第１の文字連接初期予約領域に文字連接が書
   き込まれているか、また前記第２の初期予約領域に文字
   連接が書き込まれているかを識別する識別手段と、前記
   記憶装置内に対象文書を記録する第３の初期予約領域を
   確保する第３の確保手段と、データの記憶、検索、再生
   を制御する制御装置とからなり、前記制御装置は前記第
   ３の初期予約領域に記録された対象文書の文字ｉとｊの
   連接の存在を調べて文字ｉに連接する文字種ｊを前記記
   憶装置の位置情報とともに、前記第１の確保手段で文字
   連接予約領域に確保されていた領域に書き込み、前記第
   １の確保手段で確保されていた文字ｉの初期記録領域を
   越える場合は初期予約領域を廃棄して、前記第２の記録
   領域初期確保手段によって確保されていた領域内に前記
   出現予測情報を計算修正して文字種ｉに対応した予測記
   録領域を新たに確保して文字ｉに連接する文字種ｊを前
   記記憶ファイル装置の位置情報とともに記録し、検索時
   には検索語の構成文字ｉとｊの連接を得た後、前記の識
   別手段によりにｉが第１の領域にあるか第２の領域にあ
   るかを検出し、連接文字ｊが存在する位置情報を読み取
   り対象文書の概略位置を検出してから対象文書を読み取
   って検索することを特徴とするデータ記憶再生装置。
3. 【請求項３】制御装置は第１の文字連接初期予約領域を
   記憶装置内に確保すると共に、連接データ作成時には別
   のメモリ内に複写しておき、前記メモリ内のデータを使
   用して連接データを作成することを特徴とする請求項２
   記載のデータ記憶再生装置。
4. 【請求項４】文書等のデータを記憶する記憶装置と、前
   記記憶装置に文字ｉ分の領域を初期設定する第１の文字
   連接初期予約領域確保手段と、前記記憶装置に文字連接
   の文字種類によらない前記とは別の第２の文字連接初期
   予約領域確保手段と、前記第２の文字連接初期予約領域
   の使用状況を管理するセクタ使用状況管理手段とからな
   り、前記第１の手段で確保されていた文字ｉの初期記録
   領域を越えて文字連接を記録する場合は初期予約領域を
   廃棄して、前記使用状況管理手段で連続する空き領域を
   調べて前記第２の記録領域初期確保手段によって確保さ
   れていた領域内に文字種ｉに対応した予測記録領域を新
   たに確保して文字ｉに連接する文字種ｊを前記記憶装置
   の位置情報とともに記録することを特徴とするデータ記
   憶再生装置。
5. 【請求項５】文書等のデータを記憶する記憶装置と、デ
   ータマッチング回路手段と、第１の記憶テーブルと、第
   １の記憶バッファと、前記第１の記憶テーブルを文字種
   ｉに対応して分割し、文字種ｉが与えられると対応する
   各分割領域の番地を検出してデータを読み書きする手段
   と、前記第１の記憶テーブルの前記各分割領域内に新た
   にデータを書き込む余地があるかどうかを示すデータ占
   有識別情報あるいはデータ占有情報としてのデータ量の
   値そのものを前記各分割領域内の一定の番地に書き込む
   手段と、予め初期情報として設定しておいた、あるいは
   前記記憶装置に記録対象文書から抽出された文字ないし
   は文字連接の発生頻度から設定する、高頻度文字連接の
   識別情報を、前記各分割領域の特定の番地に書き込むと
   ともに予め前記第１の記憶バッファ中に領域確保しまた
   予備領域を設ける手段と、前記高頻度文字連接の識別情
   報が高頻度を指示していない場合にはデータ占有情報を
   読み取って書き込み可能なら前記各分割領域の対応する
   番地にデータを追加していき、前記高頻度文字連接の識
   別情報が高頻度を指示している場合には前記リンク番地
   情報を読み取って前記第１の記憶バッファあるいは前記
   記憶ファイル装置にデータとして文字連接の他方の文字
   と文字連接概略位置情報との組を書き込む手段と、前記
   データ占有識別情報がデータ書き込み余地なしと示して
   いる場合には前記各分割領域内のデータを前記第１の記
   憶バッファあるいは前記記憶ファイル装置へを移動した
   ことを示して対応する移動先のリンク番地情報を前記各
   分割領域内の一定の番地に書き込む手段と、前記記憶フ
   ァイル装置から文書データを読み取り文字連接を調べて
   文字連接の一方の文字から前記第１の記憶テーブルの前
   記分割領域番地を検出し、前記データ量占有状況の識別
   情報を読み取って、もし第１の記憶テーブルに書き込み
   可能ならデータとして前記文字連接の他方の文字と文字
   連接概略位置情報との組を書き込み、もし第１の記憶テ
   ーブルに書き込み不可能ならば前記リンク番地情報を読
   み取って前記第１の記憶バッファあるいは前記記憶ファ
   イル装置にデータとして文字連接の他方の文字と文字連
   接概略位置情報との組を書き込む手段とからなり、検索
   語が入力された場合は文字連接の一方の文字に対応する
   前記分割領域番地の前記データ占有識別情報に従って、
   前記第１の記憶テーブルか前記第１の記憶バッファある
   いは前記記憶ファイル装置に、対象文書の文字連接の他
   方の文字の実際の記録領域を読みに行き、前記検索語の
   他方の文字と一致する文字があるかどうか調べて得た対
   象文書の文字連接概略位置情報で対象文書を絞り込んむ
   ことを特徴とするデータ記憶再生装置。
6. 【請求項６】文書等のデータを記憶する記憶装置と、デ
   ータマッチング回路手段と、前記記憶装置に書き込まれ
   た文書データを一定数のセクターを最小記録単位（クラ
   スタ）毎にディレクトリで管理する文書領域管理手段
   と、前記クラスタのＰ倍の予め定めたＰクラスタ単位毎
   に番号を与えて前記記憶ファイル装置における概略記録
   番地と対応させる管理番号付与手段と、前記文書データ
   が前記Ｐクラスタ単位より大きければ複数の前記管理番
   号を与えて分割管理し、Ｐクラスタ単位より小さければ
   複数の文書と同一の前記管理番号を与え連結管理し、前
   記概略番号を番地として分割ないしは連結を含む識別情
   報と、前記管理番号の付与されている前記文書領域管理
   手段による詳細記録領域へのポインタを内容とする管理
   テーブルとからなり、前記記憶装置の文書データを概略
   番地で管理することを特徴とするデータ記憶再生装置。
7. 【請求項７】記憶装置と、データマッチング回路手段
   と、前記記憶装置に書き込まれた文書データを一定数の
   セクターを最小記録単位（クラスタ）毎にディレクトリ
   管理する文書領域管理手段と、前記クラスタのＰ倍の予
   め定めたＰクラスタ単位毎に番号を与えて前記記憶ファ
   イル装置における概略記録番地と対応させる管理番号付
   与手段と、前記文書データが前記Ｐクラスタ単位より大
   きければ複数の前記管理番号を与えて分割管理し、Ｐク
   ラスタ単位より小さければ複数の文書と同一の前記管理
   番号を与え連結管理し、前記概略番号を番地として分割
   ないしは連結を含む識別情報と、前記管理番号の付与さ
   れている前記文書領域管理手段による詳細記録領域への
   ポインタを内容とする管理テーブルと、前記記憶装置の
   文書データを概略番地で管理する手段とからなり、前記
   文書データのうちの特定の文書ファイルを削除する場
   合、前記ポインタで指し示される前記詳細記録領域の対
   応するディレクトリ番号を非存在を識別できる番号に変
   えることにより削除管理することを特徴とするデータ記
   録再生装置。