JPH08287105A - 文書登録検索装置 - Google Patents

Abstract

(57)【要約】 【目的】 合理的且つ簡易な手法によって登録文書の情
報を格納するインデックスを圧縮する。 【構成】 登録対象の文書を読み込む文書入力手段１
と、文書からキーを抽出するキー抽出手段２と、文書の
識別番号と抽出されたキーとを対応付けたインデックス
を作成するインデックス作成手段１１と、登録された文
書を検索するための検索キーを入力する検索キー入力手
段１６と、検索キーを用いてインデックスから該当する
文書を検索する検索手段１７と、検索結果を出力する出
力手段１８と、を備え、インデックスファイルアクセス
手段１３が登録された文書の識別番号の総数とキーが出
現した文書の識別番号の総数との比較によって形式を換
えてインデックスに含まれた文書識別番号を圧縮し、当
該インデックスをインデックスアクセスファイル１４及
びインデックスファイル１５に格納し、検索処理に際し
ては、インデックスファイルアクセス手段１３がファイ
ル１４、１５に格納された情報から該当する圧縮形式に
基づいてインデックスを伸長させる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、登録文書から抽出した
キーと当該文書に関する情報（例えば、文書や文書中の
段落等の識別子）とをインデックスとして登録し、当該
インデックスから検索キーにより該当する文書を検索す
る文書登録検索装置に関し、特に、インデックスに含ま
れる文書に関する情報を圧縮させて保存する文書登録検
索装置に関する。

【０００２】

【従来の技術】従来より文書の登録及び検索において
は、例えば特開平２−１８６４７６号公報に記載される
ように、登録する文書から抽出したキーと当該文書名や
文書中の段落等といったキー出現位置の情報とを互いに
対応付けてインデックスとして登録し、検索に際して入
力した検索キーを用いてインデックスから該当する文書
名や文書中のキー出現位置を検索することが行われてい
る。このようにインデックスを用いた文書登録検索方式
は、検索に際して迅速に所定の文書を検索できる等の利
点を有し、広く一般的に用いられている。

【０００３】ここで、インデックスには登録した文書名
や文書中のキー出現位置等といった文書に関する情報が
格納されるが、登録件数が多くなるとインデックスのデ
ータ量が多くなって大きな記憶容量を必要としてしまう
ため、インデックスをコンパクト化することが要求され
ている。そこで、特開平５−２５７７７４号公報に記載
されるように、キーと対応付けてインデックスの格納す
るインデックスレコード番号を統計情報に基づいて圧縮
し、インデックスを格納するファイルの容量を減少さ
せ、検索に際しては圧縮したインデックスレコード番号
を伸長させる文書登録検索装置が提案されている。この
文書登録検索装置では統計情報から定めた１バイト差分
方式及び２バイト差分方式を用いて、基準データに対す
る１バイトの差分或いは２バイトの差分を圧縮したイン
デックスレコード番号としてインデックスに格納してい
る。

【０００４】

【発明が解決しようとする課題】しかしながら、従来の
文書登録検索装置にあっては、処理は、統計情報に基づ
いてインデックスを圧縮するものであるため、圧縮処理
が複雑化して処理に多くの時間を要し、また同様に、伸
長処理も複雑化して処理に多くの時間を要してしまう。
このため、従来の文書登録検索装置では、インデックス
を格納するファイル容量の減少を達成したとしても、登
録及び検索処理が複雑で迅速な処理が行えないという問
題があった。

【０００５】本発明は上記従来の事情に鑑みなされたも
ので、簡単且つ合理的な形式の圧縮手法を用いて、登録
処理及び検索処理の複雑化及び遅延化を防止しつつ、イ
ンデックスを格納するファイルの容量を減少させる文書
登録検索装置を提供することを目的とする。特に、請求
項１に記載した発明は、登録された文書に関する情報の
総数とキーが出現した文書に関する情報の総数との比較
によって、最適且つ簡単な形式でインデックスの圧縮及
びこれに対応した伸長を行う文書登録検索装置を提供す
ることを目的とする。また、請求項２乃至請求項４に記
載した発明は、特に、合理的な形式でインデックスの圧
縮及びこれに対応した伸長を行う文書登録検索装置を提
供することを目的とする。

【０００６】

【課題を解決するための手段】上記の目的を達成するた
めに、請求項１に記載した文書登録検索装置は、登録対
象の文書を読み込む文書入力手段と、入力された文書か
らキーを抽出するキー抽出手段と、登録された文書を特
定するための文書に関する情報と前記抽出されたキーと
を対応付けたインデックスを作成するインデックス作成
手段と、登録された文書を検索するための検索キーを入
力する検索キー入力手段と、検索キーを用いてインデッ
クスを検索する検索手段と、検索結果を出力する出力手
段と、を備えた文書登録検索装置において、インデック
スを圧縮するために、登録された文書の総数とキーが出
現した文書の総数とに基づいてインデックスに含まれる
文書に関する情報を形式を換えて圧縮するインデックス
圧縮手段と、圧縮されたインデックスを格納するファイ
ル手段と、検索処理に際してファイル手段に格納された
情報から該当する圧縮形式に基づいて文書に関する情報
を伸長させるインデックス伸長手段と、文書に関する情
報が伸長されたインデックスを保持するインデックス保
持手段と、を更に備え、登録に際してはインデックスを
圧縮し、検索に際してはインデックスを伸長させること
を特徴とする。

【０００７】また、請求項２に記載した文書登録検索装
置は、請求項１に記載の文書登録検索装置において、イ
ンデックス圧縮手段は、登録された文書に関する情報の
総数とキーが出現した文書に関する情報の総数とが等し
い場合には、文書に関する情報を削除するという形式で
インデックスを圧縮することを特徴とする。

【０００８】また、請求項３に記載した文書登録検索装
置は、請求項１又は請求項２に記載の文書登録検索装置
において、インデックス圧縮手段は、登録された文書に
関する情報の総数とキーが出現した文書に関する情報の
総数との比較において、キーが出現しなかった文書に関
する情報の総数がキーが出現した文書に関する情報の総
数より少ない場合には、キーが出現しなかった文書に関
する情報を用いてインデックスを書き換えるという形式
でインデックスを圧縮することを特徴とする。

【０００９】また、請求項４に記載した文書登録検索装
置は、請求項１乃至請求項３に記載のいずれか１項の文
書登録検索装置において、文書に関する情報の総数と等
しいビット列の各ビットに各文書に関する情報をそれぞ
れ割り当てて、ビットを反転させることにより各文書に
関する情報を示す形式と、各文書に関する情報をそれぞ
れ固有の２進化数値で示す形式との内の、登録された文
書に関する情報の総数とキーが出現した文書に関する情
報の総数との比較において、データ量の少ないいずれか
一方の形式によりインデックスの文書に関する情報を表
すことを特徴とする。

【００１０】

【作用】請求項１の文書登録検索装置による文書登録処
理では、文書入力手段から登録対象の文書が入力される
と、キー抽出手段が当該文書から装置に備えられた辞書
等を参照してキーを抽出し、文書識別番号等の登録され
た文書に関する情報と抽出されたキーとを対応付けてイ
ンデックス作成手段がインデックスを作成する。そし
て、インデックス圧縮手段が、登録された文書の総数と
キーが出現した文書の総数とを比較にして、データ量が
少なくて済む形式によってインデックスに含まれた文書
に関する情報を圧縮し、圧縮されたインデックスをファ
イル手段は格納保持する。

【００１１】また、請求項１の文書登録検索装置による
文書検索処理では、検索キー入力手段から検索キーが入
力されると、当該キーを用いて検索手段がインデックス
を検索して対応する文書に関する情報を検索するが、検
索に先立って或いは検索と同時に、インデックス伸長手
段がファイル手段に格納されているインデックスを伸長
させ、当該伸長されたインデックスにおいて検索手段に
検索処理を行わせる。そして、検索によって得られた結
果は出力手段により印刷出力、ディスプレイ表示されて
ユーザに提供される。

【００１２】また、請求項２の文書登録検索装置による
と、インデックス圧縮手段は、装置に登録されている文
書に関する情報の総数と或るキーが出現した文書に関す
る情報の総数とが等しい場合には、当該キーに関して文
書に関する情報をインデックスから削除する。すなわ
ち、装置に登録されている全ての文書に関する情報が或
るキーに対応しているときには、個々の文書に関する情
報を当該キーに関しては識別化する必要がないことか
ら、インデックスに当該文書に関する情報を格納しない
ことによりインデックスを圧縮する。

【００１３】また、請求項３の文書登録検索装置による
と、インデックス圧縮手段は、装置に登録されている登
録された文書に関する情報の総数と或るキーが出現した
文書に関する情報の総数との比較において、当該キーが
出現しなかった文書に関する情報の総数が当該キーが出
現した文書に関する情報の総数より少ない場合には、当
該キーが出現しなかった文書に関する情報でインデック
スを書き換える。すなわち、装置に登録されている全て
の文書に関する情報の総数から或るキーが出現した文書
に関する情報の総数を差し引いた数（すなわち、或るキ
ーが出現した文書に関する情報の補集合の数）が少ない
場合には、当該少ない数の情報を用いることによりイン
デックスを圧縮する。

【００１４】また、請求項４の文書登録検索装置による
と、インデックス圧縮手段は、装置に登録された文書に
関する情報の総数と或るキーが出現した文書に関する情
報の総数との比較において、当該キーが出現した文書に
関する情報の総数が少ない場合には当該文書に関する情
報をそれぞれ固有の２進化数値で識別化して表し、キー
が出現した文書に関する情報の総数が多い場合には当該
文書に関する情報をビット列で表す。

【００１５】例えば、３２個の文書に関する情報をそれ
ぞれ識別化して表す場合に、２進化１０進数表示では１
つ１つの情報について５ビット必要であり、３２個の情
報全体を識別化しつつ表すときには少なくとも５×３２
＝１６０ビット必要となる。一方、同じ場合に、ビット
列表示では３２ビットあれば全ての情報識別化しつつ表
せる。この両者の形式を比較すると、３２個の情報の内
の表す情報の総数が６個である場合には、２進化１０進
数表示の方が全体として最低３０ビットで足りるのでビ
ット列表示よりデータ量が少なくて済むが、表す情報の
総数が７個である場合には、２進化１０進数表示では最
低３５ビット必要となって３２ビットのビット列表示の
方がデータ量が少なくて済む。このように、両者の形式
の内の有利が方を用いて文書に関する情報を表すことに
よりインデックスを圧縮する。

【００１６】

【実施例】以下、本発明の一実施例に係る文書登録検索
装置を図面を参照して説明する。図１に示すように、文
書登録検索装置は、文書入力手段１、キー抽出手段２、
キーリスト作成手段３、キーリスト保持手段４、キーリ
ストファイルアクセス手段５、キーリストファイル６、
ファイルリスト作成手段７、ファイルリスト保持手段
８、ファイルリストアクセス手段９、ファイルリストフ
ァイル１０、インデックス作成手段１１、インデックス
保持手段１２、インデックスファイルアクセス手段１
３、インデックスアクセスファイル１４、インデックス
ファイル１５、検索キー入力手段１６、検索手段１７、
検索結果表示手段１８を備えている。

【００１７】文書入力手段１は文書を電子化したデータ
として取り込む手段であり、例えば、紙媒体の文書を読
み込むＯＣＲ装置、電子情報化された文書を記憶手段か
ら読み込む装置、電子情報化された文書をネットワーク
から読み込む通信装置等から構成されている。キー抽出
手段２は辞書を備えており、文書入力手段１から読み込
まれた文書を辞書を参照して解析し、当該文書からキー
ワードや文節等といった辞書に定義されたキーを抽出す
る。このキーの抽出は形態素解析やパターンマッチング
等といった公知の手法を用いて行う。

【００１８】キーリスト作成手段３は、キー抽出手段２
が抽出したキーの重複のない一覧であるキーリストを作
成し、読出書込自在なメモリから成るキーリスト保持手
段４に保持させる。キーリスト保持手段４は文書登録処
理や文書検索処理に際して他の手段の作業領域となり、
当該作業のためにキーリストを保持する。キーリストフ
ァイルアクセス手段５はキーリスト保持手段４とキーリ
ストファイル６との間でキーリストの読み出し及び書き
込みを行い、文書登録処理に際してはキーリスト保持手
段４に保持されたキーリストをキーリストファイル６に
格納し、文書検索作業に際してはキーリストファイル６
に格納されたキーリストを読み出してキーリスト保持手
段４に保持させる。キーリストファイル６はハードディ
スク装置等から構成され、キーリストを読出書込自在に
格納する。

【００１９】ファイルリスト作成手段７は、文書入力手
段１から読み込まれた文書についての文書名と文書識別
番号との重複のない一覧であるファイルリストを作成
し、読出書込自在なメモリから成るファイルリスト保持
手段８に保持させる。ファイルリスト保持手段８は文書
登録処理や文書検索処理に際して他の手段の作業領域と
なり、当該作業のためにファイルリストを保持する。フ
ァイルリストファイルアクセス手段９はファイルリスト
保持手段８とファイルリストファイル１０との間でファ
イルリストの読み出し及び書き込みを行い、文書登録処
理に際してはファイルリスト保持手段８に保持されたフ
ァイルリストをファイルリストファイル１０に格納し、
文書検索作業に際してはファイルリストファイル１０に
格納されたファイルリストを読み出してファイルリスト
保持手段８に保持させる。ファイルリストファイル１０
はハードディスク装置等から構成され、ファイルリスト
を読出書込自在に格納する。

【００２０】インデックスリスト作成手段１１は、キー
抽出手段２で抽出されたキーと当該キーが抽出された文
書に関する情報とを対応付たインデックスを作成し、読
出書込自在なメモリから成るインデックス保持手段１２
に保持させる。本実施例では文書に関する情報として文
書の識別番号を用いており、インデックスは後述するよ
うにキーを見出しとして対応する文書識別番号を格納し
ている。インデックス保持手段１２は文書登録処理や文
書検索処理に際して他の手段の作業領域となり、当該作
業のためにインデックスを保持する。

【００２１】インデックスファイルアクセス手段１３は
インデックス保持手段１２とインデックスアクセスファ
イル１４及びインデックスファイル１５との間でインデ
ックスの読み出し及び書き込み、更には、圧縮処理及び
伸長処理を行う。すなわち、インデックスファイルアク
セス手段１３は、文書登録処理に際してはインデックス
保持手段１２に保持されたインデックスを圧縮処理して
インデックスアクセスファイル１４及びインデックスフ
ァイル１５に格納し、文書検索作業に際してはインデッ
クスアクセスファイル１４及びインデックスファイル１
５に格納されたインデックスを読み出し伸長処理してイ
ンデックス保持手段１２に保持させる。インデックスア
クセスファイル１４及びインデックスファイル１５はハ
ードディスク装置等から構成され、圧縮されたインデッ
クスの内容を読出書込自在に格納する。

【００２２】検索キー入力手段１６は、ユーザが文書検
索しようとする検索キーを入力する手段であり、例え
ば、キーボードから構成されている。なお、文や文節等
の検索要求から検索キーを形態素解析して抽出すること
も可能であり、この場合には、検索キー入力手段は例え
ば、紙媒体の文書を読み込むＯＣＲ装置、電子情報化さ
れた文書を記憶手段から読み込む装置、電子情報化され
た文書をネットワークから読み込む通信装置等から構成
されて、解析機能を有したものとなる。

【００２３】検索手段１７は、検索キー入力手段１６か
ら入力された検索キーを用いてインデックス保持手段１
２に保持されたインデックスを検索し、検索キーに対応
する文書識別番号を抽出し、更に、当該文書識別番号を
用いてファイルリスト保持手段８に保持されたファイル
リストを検索し、対応する文書名を抽出する。検索結果
表示手段１８は検索手段１７が検索した文書名をユーザ
に対して出力する手段であり、例えばディスプレイ装置
やプリンタ等から構成されている。

【００２４】上記したインデックス保持手段１２に保持
されるインデックスは、図２に示す構造となっている。
インデックスは同図の（ａ）に示す定型部分と同図の
（ｂ）に示す可変長部分とを有している。定型部分は抽
出されたキーと同じ個数の項目から成り、これらの項目
の並びはキーリスト保持手段４におけるキーの並びと同
じになっている。したがって、各項目は抽出されたキー
とそれぞれ対応している。

【００２５】定型部分の各項目には当該キーが出現した
文書ファイル（文書識別番号）の数及び文書識別番号リ
ストへのポインタが含まれており、この文書識別番号リ
ストへのポインタによって可変長部分に含まれている対
応する文書識別番号リストへ関連付けられている。可変
長部分はキー毎に当該キーが出現した文書の識別番号を
リストにまとめて含んでおり、各文書識別番号リストに
は当該キーが出現した全ての文書識別番号が昇順で格納
されている。なお、文書識別番号リストへのポインタ
は、インデックス保持手段１２のメモリ上の絶対アドレ
スや相対アドレスであり、他の表現方式でもよい。すな
わち、インデックスの構造を定型部分と可変長部分とを
まとめて概念的に示すと、同図の（ｃ）に示すようにな
り、キーの個数と同数の項目にそれぞれ文書識別番号リ
ストが対応している。

【００２６】上記したインデックスアクセスファイル１
４に格納される内容（以下、単にインデックスアクセス
ファイルと称する）は、図３に示す構造となっている。
インデックスアクセスファイルは同図の（ａ）に示すよ
うに抽出されたキーと同数の項目から成り、これらの項
目の並びはキーリスト保持手段４におけるキーの並びと
同じになっている。したがって、各項目はインデックス
の各項目と対応し、抽出されたキーとそれぞれ対応して
いる。

【００２７】インデックスアクセスファイル１４の各項
目には、インデックスに対応して当該キーが出現した文
書ファイル（文書識別番号）の数が含まれている他に、
インデックスの形式及びインデックスファイル１５にお
けるアドレスが含まれている。インデックスの形式に
は、同図の（ｂ）に示すように本実施例では３つのビッ
トａ、ｂ、ｃが用いられ、これら各ビットの組合せによ
りインデックスファイル１５に格納された文書識別番号
の圧縮形式が示される。

【００２８】本実施例では同図の（ｃ）に示すように４
つの圧縮形式を用いており、これら形式をビットａ、
ｂ、ｃの組み合わせで示している。ビットａ、ｂ、ｃの
並びで”００１”は、「登録されている全ての文書（文
書識別番号）において当該キーが含まれているので、当
該キーについては文書識別番号をインデックスファイル
１５に格納しない」ことを示しており、文書識別番号を
格納しないという形式の圧縮が図られていることを示
す。なお、当該形式の圧縮は、当該キーについては文書
識別番号をもって登録されている文書をキーの有無で識
別する必要がないことから採用される。

【００２９】また、ビットａ、ｂ、ｃの並びで”００
０”は、「当該キーを含んでいる文書の識別番号をその
数値のままで表してインデックスファイル１５に格納す
る」ことを示しており、当該キーを含む文書の識別番号
のみを２進化数値で格納するという形式の圧縮が図られ
ていることを示す。なお、当該形式の圧縮は、登録され
ている全ての文書識別番号の総数に比較して当該キーを
含んでいる文書の識別番号が過半数に満たない比較的少
ない場合に採用される。

【００３０】また、ビットａ、ｂ、ｃの並びで”０１
０”は、「登録された全ての文書の内で当該キーを含ん
でいない文書の識別番号をその数値のままで表してイン
デックスファイル１５に格納する」ことを示しており、
当該キーを含まない文書の識別番号のみを２進化数値で
格納するという形式の圧縮が図られていることを示す。
なお、当該形式の圧縮は、登録されている全ての文書識
別番号の総数に比較して当該キーを含んでいる文書の識
別番号が過半数を上回わる比較的多い場合に採用され、
当該キーを含んでいる文書識別番号の補集合となる少な
い文書識別番号を用いて、全登録文書をキーの有無に関
して識別する。

【００３１】また、ビットａ、ｂ、ｃの並びで”１０
０”は、「登録された全ての文書の内で当該キーを含ん
でいる文書の識別番号をビット列表記で識別してインデ
ックスファイル１５に格納する」ことを示しており、２
進化数値ではなく、登録された全ての文書の識別番号の
総数と同じ数のビットの列で当該キーを含む文書の識別
番号のみを識別するという形式の圧縮が図られているこ
とを示す。なお、当該形式の圧縮は、登録されている全
ての文書識別番号の総数に比較して当該キーを含んでい
る文書の識別番号の総数が後述する基準を満たす場合に
採用される。

【００３２】上記したインデックスファイル１５に格納
される内容（以下、単にインデックスファイルと称す
る）は、図４に示す構造となっている。インデックスフ
ァイルは同図の（ａ）に示すように抽出されたキーと同
数の項目から成り、これらの項目の並びはキーリスト保
持手段４におけるキーの並びと同じになっている。した
がって、各項目はインデックス及びインデックスアクセ
スファイルの各項目と対応し、抽出されたキーとそれぞ
れ対応している。

【００３３】インデックスファイルの各項目には同図の
（ａ）に示すようにインデックスに対応して当該キーが
出現した文書の識別番号が一覧にまとめられて文書識別
番号リストとして格納されている。各項目のリストには
前記インデックス形式で示された圧縮形式でそれぞれ圧
縮が施されており、各リスト毎に適切な形式で圧縮され
て文書識別番号は格納されている。すなわち、前記ビッ
トａ、ｂ、ｃの並びで”００１”の場合には、当該キー
については文書識別番号はリストに格納されず、文書識
別番号リストは空の状態となっている。

【００３４】また、ビットａ、ｂ、ｃの並びで”００
０”の場合には、同図の（ｂ）に示すように、ヒットし
たすなわち当該キーを含む文書の識別番号のみが文書識
別番号リストに２進化数値で格納される。また、ビット
ａ、ｂ、ｃの並びで”０１０”の場合には、同図の
（ｃ）に示すように、ヒットしないすなわち当該キーを
含まない文書の識別番号のみが文書識別番号リストに２
進化数値で格納される。また、ビットａ、ｂ、ｃの並び
で”１００”の場合には、同図の（ｄ）に示すように、
当該キーを含む文書の識別番号のみを識別するビット列
が格納される。

【００３５】上記したインデックス、インデックスアク
セスファイル、インデックスファイルをまとめて示すと
図５の（ａ）、（ｂ）、（ｃ）にそれぞれ示すようにな
る。なお、文書の識別番号の総数は２０、各識別番号は
１〜２０の番号、キーの総数は５、とした場合を示すて
ある。同図の（ａ）のインデックスにおける定型部分の
各項目には、それぞれキーに該当する文書の識別番号の
総数と、可変長部分に格納されているそれぞれの文書識
別番号リストへのポインタとが格納されている。例え
ば、定型部分の１番目の項目では当該キーに対応する文
書識別番号は２個であり、ポインタ（ｐｔｒ１）で示さ
れる文書識別番号リストには文書識別番号”１０”と”
１５”とが格納されている。

【００３６】同図の（ｂ）のインデックスアクセスファ
イルには、インデックスと同様にそれぞれキーに該当す
る文書の識別番号の総数と、圧縮形式を示すビット列
と、インデックスファイルでのアドレスとが格納されて
いる。また、同図の（ｃ）のインデックスファイルで
は、インデックスアクセスファイルに格納されているア
ドレスを先頭アドレスとした領域にそれぞれ文書識別番
号が圧縮して格納されている。

【００３７】例えば、インデックスアクセスファイルの
１番目の項目ではインデックスと同じく当該キーに対応
する文書識別番号は２個であり、アドレス（ａｄｄｒ
１）で示されるインデックスファイルの領域には、圧縮
形式”０００”に対応して当該キーを含む文書識別番
号”１０”、”１５”のみが２進化数値で格納されてい
る。なお、アドレスａｄｄｒ１は全領域の先頭アドレス
であるので”０”となる。また、インデックスアクセス
ファイルの２番目の項目では、圧縮形式”００１”に対
応してインデックスファイルには文書識別番号が格納さ
れないため、アドレス欄は空となっている。また、イン
デックスアクセスファイルの３番目の項目では、圧縮形
式”１００”に対応してインデックスファイルには文書
識別番号がビット列で格納されている。

【００３８】上記した文書識別番号の圧縮形式を選択基
準を説明する。ここで、Ｌｉをｉ番目のキーを含んだ文
書の識別番号の総数とし、文書識別番号を数値で表記す
る場合は文書識別番号１つ当たりＤバイト（ｂｙｔｅ）
を要し、ビット列で表記する場合はＫバイトを要すると
し、登録された文書の識別番号の総数をＮ、ビット列が
８ビットで１バイトの場合では、ＫはＮ／８バイト（Ｎ
が８で割り切れる場合）、又は、Ｋ＋１バイト（Ｎが８
で割り切れない場合）であるとする。

【００３９】まず、ＬｉとＮとが等しい場合には、圧縮
形式が”００１”の場合であるので、インデックスファ
イルには文書識別番号は何も格納されない。次いで、Ｌ
ｉ・ＤがＫ以下の場合には、圧縮形式が”０００”の場
合であるので、図４の（ｂ）に示すように、インデック
スファイルにはキーを含んだ登録文書の識別番号をそれ
ぞれ数値で格納する。

【００４０】次いで、（Ｎ−Ｌｉ）・ＤがＫ以下の場合
には、圧縮形式が”０１０”の場合であるので、図４の
（ｃ）に示すように、インデックスファイルにはキーを
含まない登録文書の識別番号を数値で格納する。次い
で、Ｌｉ・ＤがＫを越え、（Ｎ−Ｌｉ）・ＤもＫを越え
る場合には、圧縮形式が”１００”の場合であるので、
図４の（ｄ）に示すように、全登録文書の識別番号をビ
ット列とし、キーを含む文書の識別番号に該当するビッ
トをＯＮ、それ以外をＯＦＦとしてインデックスファイ
ルに格納する。

【００４１】上記構成の文書登録検索装置による主要な
登録処理の手順を図６を参照して説明する。まず、文書
入力手段１が登録対象の文書にアクセスして登録すべき
全ての文書を読み込むと（ステップＳ１）、ファイルリ
スト作成手段７が読み込んだ文書の文書名を一覧にし、
更に、これら文書名に固有の文書識別番号を与えてファ
イルリストを作成する（ステップＳ２）。この作成され
たファイルリストはファイルリスト保持手段８、ファイ
ルリストファイルアクセス手段９を介してファイルリス
トファイル１０に格納される。

【００４２】また、ファイルリストの作成後或いは同時
に、読み込んだ文書をキー抽出手段２が順に解析して各
文書からキーを抽出し（ステップＳ３）、キーリスト作
成手段３が抽出したキーを全文書において重複のない一
覧としてのキーリストを作成する（ステップＳ４）。こ
の作成されたキーリストはキーリスト保持手段４、キー
リストファイルアクセス手段５を介してキーリストファ
イル６に格納される。

【００４３】また、キーリストの作成後或いは同時に、
インデックス作成手段１１がキーリストの順序に従って
キーとキーが出現した文書の文書識別番号との一覧であ
るインデックスを作成し（ステップＳ５）、作成された
インデックスはインデックス保持手段１２、インデック
スファイルアクセス手段１３を介してインデックスアク
セスファイル１５及びインデックスファイル１５に格納
される。上記一連の処理を読み込まれた登録対象の文書
がなくなるまで繰り返し行なって処理を終了する（ステ
ップＳ６）。なお、本実施例では、文書識別番号は文書
が登録された順に１から始まり以下２、３、・・・と続
き、最後に登録された文書の文書識別番号は登録された
文書の総数と同じ値となる。

【００４４】図７には上記ステップＳ５のインデックス
ファイル作成に関する処理の詳細な手順を示してある。
なお、以下の例では、全登録文書の識別番号の総数を
Ｎ、抽出されたキーの総数をＭ、ｉ番目のキーを持つ登
録文書の識別番号をＬｉ、文書識別番号を表す数値のフ
ァイル上の大きさをＤバイトとする。また、図２の
（ａ）、（ｂ）に示したインデックスを、インデックス
ファイルアクセス手段１３が圧縮して図３及び図４に示
したインデックスアクセスファイルとインデックスファ
イルとして格納するとする。

【００４５】まず、全登録文書の識別番号をビット列で
表す時の領域の大きさＫバイトを求め（ステップＳ１
１）、各キー毎にインデックスアクセスファイルとイン
デックスファイルとを作成する。すなわち、インデック
スファイルでの書き込み開始アドレスと、ｉ番目のキー
を持つ文書の識別番号の総数Ｌｉとをインデックスアク
セスファイルに書き込む（ステップＳ１２、Ｓ１３）。
なお、インデックスファイルでの書き込み開始アドレス
は、一番最初は０で、書き込みがあると次に書き込むべ
きアドレスを指す。

【００４６】次いで、ｉ番目のキーを持つ登録文書の識
別番号の数Ｌｉと全登録文書の識別番号の総数Ｎとが等
しいかどうか調べ（ステップＳ１４）、ＬｉとＮが等し
い場合には、インデックスアクセスファイルにのみ書き
込みを行い、インデックスファイルには文書識別番号の
書き込みを行わない（ステップＳ１５）。すなわち、イ
ンデックスアクセスファイルの「インデックスの形式」
には”００１”とする。一方、ＬｉとＮが等しくない場
合には、Ｌｉ・ＤがＫ以下かどうか調べて（ステップＳ
１６）、ｉ番目のキーを持つ文書の文書識別番号を数値
で表す場合とビット列で表す場合とでどちらが領域が小
さいか調べる。

【００４７】この結果、Ｌｉ・ＤがＫ以下の場合には、
ｉ番目のキーを持つ文書の識別番号を数値でインデック
スファイルに書き込み（ステップＳ１７）、インデック
スアクセスファイルのインデックスの形式には”００
０”を書き込んで（ステップＳ１８）、ｉ番目のキーを
持つ文書の識別番号を数値でインデックスファイルに書
き込んだことを示す。一方、Ｌｉ・ＤがＫを越える場合
には、ｉ番目のキーを持たない文書の識別番号の総数
（Ｎ−Ｌｉ）・ＤがＫ以下かどうか調べて（ステップＳ
１９）、キーを持たない文書の識別番号を数値で表す場
合とキーを持つ文書の識別番号をビット列で表す場合の
どちらが領域が小さいか調べる。

【００４８】この結果、（Ｎ−Ｌｉ）・ＤがＫ以下の場
合には、ｉ番目のキーを持たない文書の文書識別番号を
数値でインデックスファイルに書き込み（ステップＳ２
０）、インデックスアクセスファイルのインデックスの
形式には”０１０”を書き込んで（ステップＳ２１）、
キーを持たないファイルの文書識別番号を数値でインデ
ックスファイルに書き込んだことを示す。一方、（Ｎ−
Ｌｉ）・ＤがＫを越える場合には、登録されている全て
の文書の識別番号についてｉ番目のキーの有無をビット
列でインデックスファイルに書き込み（ステップＳ２
２）、インデックスアクセスファイルのインデックスの
形式には”１００”を書き込んで（ステップＳ２３）、
ｉ番目のキーを持つ文書の識別番号をビット列でインデ
ックスファイルに書き込んだことを示す。そして、上記
した一連の処理をキーの総数Ｍ回繰り返し行って処理を
終了する（ステップＳ２４）。

【００４９】なお、上記したステップＳ１４、Ｓ１６、
Ｓ１９の判断処理は順序を入れ替えてもよく、実施上任
意に設定することができる。上記の一連の処理によっ
て、例えば、図５の（ａ）に示すインデックスから、同
図の（ｂ）に示すインデックスアクセスファイルと同図
の（ｃ）に示すインデックスファイルとが作成され、イ
ンデックスファイルには文書識別番号が合理的且つ簡易
な手法で圧縮されて格納される。

【００５０】図８には、検索処理に際して行う、インデ
ックスアクセスファイル及びインデックスファイルから
インデックスファイルアクセス手段１３によって伸長処
理をしてインデックスを再生する処理の手順を示してあ
る。この処理では、インデックスアクセスファイル及び
インデックスファイルから抽出した情報でインデックス
の定型部分の内容を書き、また、インデックスの形式に
基づいてインデックスファイルに格納された文書識別番
号を伸長処理してインデックスの可変長部分に書き込
む。なお、インデックスの定型部分の領域は、例えば、
キーリストファイル６からキーの総数Ｍを得て事前にイ
ンデックス保持手段１２に生成しておく。

【００５１】まず、インデックスアクセスファイルから
ｉ番目のキーを持つ文書の識別番号の総数Ｌｉとインデ
ックスファイルでの圧縮形式であるインデックスの形式
とを読み出す（ステップＳ３１、Ｓ３２）。そして、イ
ンデックスの形式が”００１”であるかを調べ（ステッ
プＳ３３）、全登録文書がｉ番目のキーを持つ場合に
は、全登録文書の識別番号の総数分の文書識別番号のリ
ストの領域をインデックス保持手段１２に確保し、当該
領域に先頭の識別番号が”１”、最後の識別番号が全登
録文書の識別番号の総数”Ｎ”となるようにリストに数
値を書き込み、ｉ番目のキーを持つ文書識別番号（登録
文書ファイル数）と文書識別番号リストへのポインタと
をインデックスの定型部分に書き込む（ステップＳ３
４）。

【００５２】一方、インデックスの形式が”００１”で
はなく、全登録文書でｉ番目のキーを持つのではない場
合には、インデックスアクセスファイルからインデック
スファイルでのアドレスを読み出して書き込み開始アド
レスを得て、インデックスファイルから文書識別番号を
読み出す用意をする（ステップＳ３５）。次いで、イン
デックスの形式が”０００”であるかを調べて、ｉ番目
のキーを持つ文書の文書識別番号を数値で書いたかどう
か調べ（ステップＳ３６）、ｉ番目のキーを持つ文書の
文書識別番号を数値で書いている場合には、ｉ番目のキ
ーを持つ文書の識別番号の総数Ｌｉ分の文書識別番号の
リストの領域をインデックス保持手段１２に確保し、イ
ンデックスファイルから文書識別番号の数値を読み出し
て文書識別番号のリストに書き込み、ｉ番目のキーを持
つ文書識別番号の総数Ｌｉと文書識別番号リストへのポ
インタとをインデックスの定型部分に書き込む（ステッ
プＳ３７）。

【００５３】一方、ｉ番目のキーを持つ文書の識別番号
を数値で書いているのではない場合には、インデックス
の形式が”０１０”であるかを調べて、ｉ番目のキーを
持たない文書の識別番号を数値で書いたかどうか調べる
（ステップＳ３８）。この結果、ｉ番目のキーを持たな
い文書の識別番号を数値で書いている場合には、ｉ番目
のキーを持つ文書識別番号の総数Ｌｉ分の文書識別番号
リストの領域をインデックス保持手段１２に確保し、イ
ンデックスファイルから文書識別番号の数値を読み出し
てビット列に変換し、各ビットの”０”と”１”とを反
転させた後に、更にビット列を数値に再変換して文書識
別番号リストに書き込み、ｉ番目のキーを持つ文書識別
番号の総数数Ｌｉと文書識別番号リストへのポインタと
をインデックスの定型部分に書き込む（ステップＳ３
９）。

【００５４】一方、上記以外の場合には、ｉ番目のキー
を持つ文書の識別番号の総数Ｌｉ分の文書識別番号リス
トの領域をインデックス保持手段１２に確保し、インデ
ックスファイルから文書識別番号のビット列を読み出
し、数値に変換して文書識別番号リストに書き込み、ｉ
番目のキーを持つ文書識別番号の総数Ｌｉと文書識別番
号リストへのポインタとをインデックスの定型部分に書
き込む（ステップＳ４０）。上記一連の処理をキーの総
数数Ｍ回繰り返し行って処理を終了する（ステップＳ４
１）。

【００５５】なお、上記したステップＳ３６、Ｓ３８の
判断処理は順序を入れ替えてもよく、また、インデック
スの形式の各欄について１ビットずつ”０”か”１”か
の条件判断をして処理を変えてもよく、手順は実施上任
意に設定することができる。上記の一連の処理によっ
て、例えば、図５の（ｂ）に示すインデックスアクセス
ファイルと同図の（ｃ）に示すインデックスファイルと
から、同図の（ａ）に示すインデックスが作成され、イ
ンデックスには文書識別番号が合理的且つ簡易な手法で
伸長されて格納される。

【００５６】なお、本発明では、インデックスを定型部
分と可変長部分とに分けなくともよく、これらを一体と
したインデックスとしてもよい。また、インデックスに
は文書識別番号を昇順でなく降順で格納してもよく、ま
た、インデックスに格納する文書識別番号は数値ではな
くビット列で表したものでもよい。また、上記実施例で
は文書に関する情報として文書識別番号を用いた例を示
したが、文書名、文書ファイルの物理的なアドレス等を
用いるようにしてもよく、また、文書に関する情報は、
文書識別番号のような文書をファイル単位で特定するも
のではなく、文書中の章、段落、文等の単位でを特定す
る番号や記号等であってもよい。また、検索された文書
に関する情報は、文書名等を出力するばかりではなく、
検索キーがヒットした文書中の文や段落等も表示するよ
うにしてもよい。

【００５７】また、インデックスアクセスファイルにお
いて、圧縮方法を示すインデックスの形式は持たずに、
伸張してメモリに展開する都度、キーを持つ文書数と全
登録文書数とを比較して文書識別番号を展開してもよ
い。また、文書識別番号は、文書の登録日時によって割
当ててもよく、連続した値でなくてもよい。また、イン
デックスを格納するインデックスアクセスファイルとイ
ンデックスファイルは別個の記憶装置で構成しても、１
つの記憶装置に領域を仕切って構成してもよい。また、
インデックスをこれらファイルに保存する時期は、文書
登録検索装置の操作終了時、文書登録検索装置の登録処
理終了時、文書登録検索装置の操作開始から一定時間経
過後、文書登録検索装置の操作開始から一定時間経過す
る毎、種々設定することができる。

【００５８】

【発明の効果】以上説明したように、請求項１の文書登
録検索装置によると、登録された文書に関する情報の総
数とキーが出現した文書に関する情報の総数との比較に
よって形式を換えて、インデックスを圧縮してファイル
に格納し、検索処理に際しては圧縮されたインデックス
を伸長させて用いるようにしたため、簡易且つ適切な圧
縮処理によりインデックスがコンパクト化されて格納に
必要とされるファイル容量が大幅に削減され、また、簡
易且つ迅速な伸長処理により伸長されたインデックスを
用いて迅速な検索処理が実現される。

【００５９】また、請求項２乃至請求項４の文書登録検
索装置によると、登録された文書に関する情報の総数と
キーが出現した文書に関する情報の総数との関係に基づ
いた、合理的な形式でインデックスの圧縮処理及びこれ
に対応した伸長処理を行うことができ、簡便且つ迅速な
登録検索作業を実現することができる。特に、文書に関
する情報を数値やビット列に統一してインデックスに展
開するようにすれば、より一層の迅速なる検索処理が実
現される。なお、特許公報のように各文書が同じ決まり
文句を持つ文書を登録・検索する時には、圧縮しない場
合の半分以下の容量となることもあり、多大なる効果が
得られる。

【図面の簡単な説明】

【図１】 本発明の一実施例に係る文書登録検索装置の
構成を示すブロック図である。

【図２】 本発明の一実施例に係るインデックスの構成
を示す概念図である。

【図３】 本発明の一実施例に係るインデックスアクセ
スファイルの構造を示す概念図である。

【図４】 本発明の一実施例に係るインデックスファイ
ルの構造を示す概念図である。

【図５】 本発明の一実施例に係るインデックス、イン
デックスアクセスファイル、インデックスファイルの構
造を示す概念図である。

【図６】 本発明の一実施例に係るインデックス作成処
理の手順を示すフローチャートである。

【図７】 本発明の一実施例に係るインデックス圧縮処
理の手順を示すフローチャートである。

【図８】 本発明の一実施例に係るインデックス伸長処
理の手順を示すフローチャートである。

【符号の説明】

１・・・文書入力手段、 ２・・・キー抽出手段、１１
・・・インデックス作成手段、 １２・・・インデック
ス保持手段、１３・・・インデックスファイルアクセス
手段（インデックス伸長手段、インデックス圧縮手
段）、１４・・・インデックスアクセスファイル、１５
・・・インデックスファイル、 １６・・・検索キー入
力手段、１７・・・検索手段、 １８・・・検索結果表
示手段、

───────────────────────────────────────────────────── フロントページの続き (72)発明者 山下 明男 神奈川県川崎市高津区坂戸３丁目２番１号 ＫＳＰ Ｒ＆Ｄ ビジネスパークビル 富士ゼロックス株式会社内 (72)発明者 相原 一雄 神奈川県川崎市高津区坂戸３丁目２番１号 ＫＳＰ Ｒ＆Ｄ ビジネスパークビル 富士ゼロックス株式会社内 (72)発明者 喜多 辰臣 神奈川県川崎市高津区坂戸３丁目２番１号 ＫＳＰ Ｒ＆Ｄ ビジネスパークビル 富士ゼロックス株式会社内 (72)発明者 山口 浩 神奈川県川崎市高津区坂戸３丁目２番１号 ＫＳＰ Ｒ＆Ｄ ビジネスパークビル 富士ゼロックス株式会社内 (72)発明者 川本 真司 神奈川県川崎市高津区坂戸３丁目２番１号 ＫＳＰ Ｒ＆Ｄ ビジネスパークビル 富士ゼロックス株式会社内 (72)発明者 平岡 直美 神奈川県川崎市高津区坂戸３丁目２番１号 ＫＳＰ Ｒ＆Ｄ ビジネスパークビル 富士ゼロックス株式会社内

Claims (4)

【特許請求の範囲】
1. 【請求項１】 登録対象の文書を読み込む文書入力手段
   と、入力された文書からキーを抽出するキー抽出手段
   と、登録された文書を特定するための文書に関する情報
   と前記抽出されたキーとを対応付けたインデックスを作
   成するインデックス作成手段と、登録された文書を検索
   するための検索キーを入力する検索キー入力手段と、検
   索キーを用いてインデックスを検索する検索手段と、検
   索結果を出力する出力手段と、を備えた文書登録検索装
   置において、 インデックスを圧縮するために、登録された文書の総数
   とキーが出現した文書の総数とに基づいてインデックス
   に含まれる文書に関する情報を形式を換えて圧縮するイ
   ンデックス圧縮手段と、 圧縮されたインデックスを格納するファイル手段と、 検索処理に際してファイル手段に格納された情報から該
   当する圧縮形式に基づいて文書に関する情報を伸長させ
   るインデックス伸長手段と、 文書に関する情報が伸長されたインデックスを保持する
   インデックス保持手段と、を更に備え、登録に際しては
   インデックスを圧縮し、検索に際してはインデックスを
   伸長させることを特徴とする文書登録検索装置。
2. 【請求項２】 請求項１に記載の文書登録検索装置にお
   いて、 インデックス圧縮手段は、登録された文書に関する情報
   の総数とキーが出現した文書に関する情報の総数とが等
   しい場合には、文書に関する情報を削除するという形式
   でインデックスを圧縮することを特徴とする文書登録検
   索装置。
3. 【請求項３】 請求項１又は請求項２に記載の文書登録
   検索装置において、 インデックス圧縮手段は、登録された文書に関する情報
   の総数とキーが出現した文書に関する情報の総数との比
   較において、キーが出現しなかった文書に関する情報の
   総数がキーが出現した文書に関する情報の総数より少な
   い場合には、キーが出現しなかった文書に関する情報を
   用いてインデックスを書き換えるという形式でインデッ
   クスを圧縮することを特徴とする文書登録検索装置。
4. 【請求項４】 請求項１乃至請求項３に記載のいずれか
   １項の文書登録検索装置において、文書に関する情報の
   総数と等しいビット列の各ビットに各文書に関する情報
   をそれぞれ割り当てて、ビットを反転させることにより
   各文書に関する情報を示す形式と、各文書に関する情報
   をそれぞれ固有の２進化数値で示す形式との内の、登録
   された文書に関する情報の総数とキーが出現した文書に
   関する情報の総数との比較において、データ量の少ない
   いずれか一方の形式によりインデックスの文書に関する
   情報を表すことを特徴とする文書登録検索装置。