(57)【特許請求の範囲】
【請求項１】
指定された文字列を含む文書を複数の文書データから検索する全文検索装置において、
検索用の全文索引記憶部と、
登録用の全文索引記憶部と、
削除用の全文索引記憶部と、
前記登録用の全文索引記憶部及び前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージするマージ手段と、
削除するデータが記憶されている領域を示す情報に基づき、前記検索用の全文索引記憶部から前記削除するデータが記憶されている領域を解放する領域解放手段と
を有し、
前記マージ手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージするときに、削除するデータが記憶されている領域を示す情報を前記検索用の全文索引記憶部へ付加し、
前記領域解放手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージした回数、又は、前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へマージしたデータのサイズが、閾値に達すると、前記検索用の全文索引記憶部の前記削除するデータが記憶されている領域を解放すること
を特徴とする全文検索装置。
【請求項２】
前記検索用の全文索引記憶部、前記登録用の全文索引記憶部及び前記削除用の全文索引記憶部は、入出力単位である固定長のページに前記データを格納していること
を特徴とする請求項１記載の全文検索装置。
【請求項３】
指定された文字列を含む文書を複数の文書データから検索する全文検索装置において、
検索用の全文索引記憶部と、
登録用の全文索引記憶部と、
削除用の全文索引記憶部と、
前記登録用の全文索引記憶部及び前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージするマージ手段と、
削除するデータが記憶されている領域を示す情報に基づき、前記検索用の全文索引記憶部から前記削除するデータが記憶されている領域を解放する領域解放手段と
を有し、
前記マージ手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージするときに、削除するデータが記憶されている領域を示す情報を前記検索用の全文索引記憶部へ付加し、
前記領域解放手段は、前記マージ手段が前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージしたあとで、前記検索用の全文索引記憶部の前記削除するデータが記憶されている領域を解放すること
を特徴とする全文検索装置。
【請求項４】
前記マージ手段は、前記領域解放手段が前記検索用の全文索引記憶部から前記削除するデータが記憶されている領域を解放したあとで、前記登録用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージすること
を特徴とする請求項３記載の全文検索装置。
【請求項５】
指定された文字列を含む文書を複数の文書データから検索するコンピュータを、
検索用の全文索引記憶部、
登録用の全文索引記憶部、
削除用の全文索引記憶部、
前記登録用の全文索引記憶部及び前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージするマージ手段、
削除するデータが記憶されている領域を示す情報に基づき、前記検索用の全文索引記憶部から前記削除するデータが記憶されている領域を解放する領域解放手段
として機能させ、
前記マージ手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージするときに、削除するデータが記憶されている領域を示す情報を前記検索用の全文索引記憶部へ付加し、
前記領域解放手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージした回数、又は、前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へマージしたデータのサイズが、閾値に達すると、前記検索用の全文索引記憶部の前記削除するデータが記憶されている領域を解放すること
を特徴とするプログラム。
【請求項６】
指定された文字列を含む文書を複数の文書データから検索するコンピュータを、
検索用の全文索引記憶部、
登録用の全文索引記憶部、
削除用の全文索引記憶部、
前記登録用の全文索引記憶部及び前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージするマージ手段、
削除するデータが記憶されている領域を示す情報に基づき、前記検索用の全文索引記憶部から前記削除するデータが記憶されている領域を解放する領域解放手段
として機能させ、
前記マージ手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージするときに、削除するデータが記憶されている領域を示す情報を前記検索用の全文索引記憶部へ付加し、
前記領域解放手段は、前記マージ手段が前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージしたあとで、前記検索用の全文索引記憶部の前記削除するデータが記憶されている領域を解放すること
を特徴とするプログラム。
【請求項７】
請求項５又は６に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全文検索装置、プログラム及び記録媒体に関する。
【背景技術】
【０００２】
近年、情報通信技術の発達により電子化された文書（電子化文書）及びその電子化文書に関する情報がインターネットなどを介して大量に流通している。この電子化文書及びその電子化文書に関する情報の流通に際し、所望の電子化文書を精度よく、さらには高速に検索する文書検索装置が提案されている。
【０００３】
文書検索装置ではキーワード検索手法や全文検索手法が用いられている。全文検索手法を用いた全文検索装置は、任意の検索文字列と検索対象の電子化文書の全てとの間で照合を行なって、検索文字列を含む電子化文書を漏れなく抽出する装置である。全文検索手法を用いた全文検索装置は、キーワード検索手法のように、検索対象となる全ての電子化文書に対してキーワードを予め付与するといった多大な人力が必要ない。
【０００４】
全文検索装置としては、様々な種類のものが提案されている。全文検索装置の１種としては、転置（索引）ファイル方式を採用した装置がある。転置ファイル方式を採用した全文検索装置は、検索のための補助ファイルとして文字／単語／n-gram（ｎ文字連接）などが出現する電子化文書、或いはそれらの電子化文書中の出現位置を記録する転置ファイルを予め構築しておく。そして、転置ファイル方式を採用した全文検索装置は、全文検索時に、転置ファイルを用いて検索することで非常に高速な検索を行なうことができ、大量の電子化文書の高速検索が要求されるシステムに対して有効である。
【０００５】
なお、全文検索方式一般、転置ファイル方式の詳細については、文献「情報検索アルゴリズム」（北研二、津田和彦、獅々堀正幹 著、共立出版株式会社、pp.160-179）、特開平１１−０７３４２９号公報の従来技術、及び全文検索システム協議会平成１０年度活動報告(http://www.ftsanet.com/dbtokyo99/Db99.htm)などで述べられており、公知であるのでその説明を省略する。
【０００６】
転置ファイル方式を採用した全文検索装置では、通常、原データ（電子化文書）の数倍にも及ぶ転置ファイルを構築する必要がり、登録されている電子化文書のデータ量が多くなるに従って登録・削除処理に時間を要するようになる。そこで、従来は、利用者側からみた登録・削除処理のレスポンスタイムを短くすることができる全文検索装置が知られていた（例えば特許文献１参照）。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
転置ファイル方式を採用した全文検索装置では全文索引の構成要素を転置ファイルに実装するとき、転置ファイルを、データ長が固定長のページ（ブロック）に実装するのが一般的である。なお、全文索引の構成要素は、電子化文書の登録や削除によりデータ長が変動する。
【０００８】
したがって、従来の転置ファイル方式を採用した全文検索装置では、全文索引の構成要素を固定長のページに分割して格納しているため、電子化文書の登録や削除によりページ内に空き領域が発生してしまう。一般に、電子化文書の登録であれば、ページ内に発生する空き領域は小さい。一方、電子化文書の削除の場合、ページ内に発生する空き領域は大きくなる。このように、電子化文書の削除の場合、従来の転置ファイル方式を採用した全文検索装置では、転置ファイルが格納されたページの利用率が低下し、転置ファイルのサイズ（データ量）が大きくなってしまうという問題があった。
【０００９】
本発明は、上記の点に鑑みなされたもので、転置ファイルのサイズの増加を防ぐことができる全文検索装置、プログラム及び記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するため、請求項１に記載した全文検索装置は、指定された文字列を含む文書を複数の文書データから検索する全文検索装置において、検索用の全文索引記憶部と、登録用の全文索引記憶部と、削除用の全文索引記憶部と、前記登録用の全文索引記憶部及び前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へデータをマージするマージ手段と、削除するデータが記憶されている領域を示す情報に基づき、前記検索用の全文索引記憶部から前記削除するデータが記憶されている領域を解放する領域解放手段とを有し、前記マージ手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージするときに、削除するデータが記憶されている領域を示す情報を前記検索用の全文索引記憶部へ付加し、前記領域解放手段は、前記削除用の全文索引記憶部からデータを前記検索用の全文索引記憶部へマージした回数、又は、前記削除用の全文索引記憶部から前記検索用の全文索引記憶部へマージしたデータのサイズが、閾値に達すると、前記検索用の全文索引記憶部の前記削除するデータが記憶されている領域を解放することを特徴とする。
【００１１】
なお、本発明の構成要素、表現または構成要素の任意の組合せを、方法、装置、システム、コンピュータプログラム、記録媒体、データ構造などに適用したものも本発明の態様として有効である。
【発明の効果】
【００１２】
本発明によれば、転置ファイルのサイズの増加を防ぐことができる。
【図面の簡単な説明】
【００１３】
【図１】本実施形態に係る全文検索装置の一例のハードウェア構成図である。
【図２】本実施形態に係る全文検索装置をサーバ／クライアントで構成した場合の一例のシステム構成図である。
【図３】本実施形態に係る全文検索装置の一例の処理ブロック図である。
【図４】本実施形態に係る全文検索装置の処理の流れを表した一例のフローチャート（１／３）である。
【図５】本実施形態に係る全文検索装置の処理の流れを表した一例のフローチャート（２／３）である。
【図６】本実施形態に係る全文検索装置の処理の流れを表した一例のフローチャート（３／３）である。
【図７】本実施形態に係る全文検索装置の処理の一例を説明する為の説明図である。
【図８】マージ処理及びバキューム処理の概要を説明する為の説明図である。
【図９】転置リストの論理的な構造について説明する為の説明図である。
【図１０】入出力単位であるページに合わせて格納された転置リストの構造について説明する為の説明図である。
【図１１】削除回数記憶部に記録されているバキューム処理を実施するか否かを判断するための情報の一例の構成図である。
【図１２】ステップＳ２８の処理の詳細を表したフローチャートである。
【発明を実施するための形態】
【００１４】
次に、本発明の実施の形態について、詳細に説明する。
［第１の実施形態］
＜ハードウェア構成＞
図１は本実施形態に係る全文検索装置の一例のハードウェア構成図である。図１の全文検索装置１００は、スタンドアローンで構成した場合のハードウェア構成の一例を示している。
【００１５】
図１に示した全文検索装置１００は、入力装置１０１、表示装置１０２、外部Ｉ／Ｆ１０３、ＲＡＭ（Random Access Memory）１０４、ＲＯＭ（Read Only Memory）１０５、ＣＰＵ（Central Processing Unit）１０６、通信Ｉ／Ｆ１０７、及びＨＤＤ（Hard Disk Drive）１０８などを備え、それぞれがバスＢで相互に接続されている。
【００１６】
入力装置１０１はキーボードやマウスなどを含み、全文検索装置１００に各操作信号を入力するのに用いられる。表示装置１０２はディスプレイなどを含み、全文検索装置１００による処理結果を表示する。通信Ｉ／Ｆ１０７は全文検索装置１００をネットワークに接続するインタフェースである。
【００１７】
ＨＤＤ１０８は、プログラムやデータを格納している不揮発性の記憶装置である。格納されるプログラムやデータには、全文検索装置１００全体を制御する基本ソフトウェアであるＯＳ（Operating System）、及びＯＳ上において各種機能を提供するアプリケーションソフトウェアなどがある。また、ＨＤＤ１０８は格納しているプログラムやデータを、所定のファイルシステム及び／又はＤＢ（Data Base）により管理している。
【００１８】
外部Ｉ／Ｆ１０３は、外部装置とのインタフェースである。外部装置には、記録媒体１０３ａなどがある。これにより、全文検索装置１００は外部Ｉ／Ｆ１０３を介して、記録媒体１０３ａの読み取り及び／又は書き込みを行うことができる。記録媒体１０３ａにはフレキシブルディスク、ＣＤ（Compact Disk）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（SD Memory card）、ＵＳＢメモリ（Universal Serial Bus memory）等がある。
【００１９】
ＲＯＭ１０５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリ（記憶装置）である。ＲＯＭ１０５には、全文検索装置１００の起動時に実行されるＢＩＯＳ（Basic Input/Output System）、ＯＳ設定、及びネットワーク設定などのプログラムやデータが格納されている。ＲＡＭ１０４は、プログラムやデータを一時保持する揮発性の半導体メモリ（記憶装置）である。
【００２０】
ＣＰＵ１０６は、ＲＯＭ１０５やＨＤＤ１０８などの記憶装置からプログラムやデータをＲＡＭ１０４上に読み出し、処理を実行することで、全文検索装置１００全体の制御や機能を実現する演算装置である。
【００２１】
本実施形態に係る全文検索装置１００は、上記ハードウェア構成により、後述するような各種処理を実現できる。
【００２２】
図２は本実施形態に係る全文検索装置をサーバ／クライアントで構成した場合の一例のシステム構成図である。なお、全文検索装置１００及び端末装置１１０のハードウェア構成は図１と同様である。
【００２３】
図２の全文検索システム２００はサーバとしての全文検索装置１００及びクライアントとしての端末装置１１０が、インターネットやＬＡＮなどのネットワークＮ１を介して接続可能である。ネットワークＮ１は有線通信／無線通信の何れかであっても、両方を含むものであってもよい。
【００２４】
端末装置１１０は全文検索装置１００にアクセス可能である。全文検索装置１００は端末装置１１０からの要求（リクエスト）に対して応答（レスポンス）できる。全文検索装置１００は、複数の文書データ（複数の電子化文書）から、指定された文字列を含む文書データを検索する装置である。
【００２５】
なお、本実施形態において、全文検索装置１００における「全文検索」とは、検索すべき全ての文字列を対象とした検索であることを意味している。したがって、例えばＳＧＭＬ等のタグ付の文書であれば、全文検索装置１００は、適宜、所定のタグ間にある文字列を検索の対象としてもよい。
【００２６】
また、図２の全文検索システム２００は、１台の全文検索装置１００を含む構成を一例として表しているが、全文検索装置１００で行う一部の処理を行う他のサーバ装置などが含まれていてもよい。
【００２７】
＜ソフトウェア構成＞
全文検索装置１００は、例えば図３に示すような処理ブロックで実現される。図３は本実施形態に係る全文検索装置の一例の処理ブロック図である。全文検索装置１００はプログラムを実行することで、入力部１、出力部２、登録処理部３、削除処理部４、検索処理部５、テキスト分割部６、文書データ記憶部７、検索用大規模全文索引記憶部８、登録用小規模全文索引記憶部９、削除用小規模全文索引記憶部１０、マージ部１１、バキューム部１２、削除回数記憶部１３を実現している。
【００２８】
入力部１は、登録処理用の文書データ，削除処理用の文書識別子，検索処理用の検索条件などが入力される。入力部１は、入力された登録処理用の文書データを登録処理部３に渡す。入力部１は入力された削除処理用の文書識別子を削除処理部４に渡す。入力部１は入力された検索処理用の検索条件を検索処理部５に渡す。
【００２９】
登録処理部３は文書データに関する登録処理を行う。登録処理部３は文書データ記憶部７及び登録用小規模全文索引記憶部９に対し、文書データに関する登録処理を行う。削除処理部４は文書データに関する削除処理を行う。削除処理部４は、入力部１に入力された削除処理用の文書識別子に基づいて、文書データ記憶部７に記憶された文書データを読み出す。削除処理部４は文書データ記憶部７から読み出した文書データを、テキスト分割部６を用いて部分文字列に分割する。
【００３０】
削除処理部４は分割した部分文字列が登録用小規模全文索引記憶部９に登録された索引である場合に、その索引を削除し、分割した部分文字列が登録用小規模全文索引記憶部９に登録された索引でない場合に、分割した部分文字列を索引として削除用小規模全文索引記憶部１０に記録する。
【００３１】
テキスト分割部６は、登録処理部３，削除処理部４，検索処理部５の各々で必要な、登録処理における文書データから部分文字列への分割処理、削除処理における文書データから部分文字列への分割処理、検索処理における検索条件（検索文字列）から部分文字列への分割処理を行う。
【００３２】
検索処理部５は検索用大規模全文索引記憶部８，登録用小規模全文索引記憶部９，削除用小規模全文索引記憶部１０に対して検索処理を行う。検索処理部５は検索用大規模全文索引記憶部８及び登録用小規模全文索引記憶部９の検索結果から、削除用小規模全文索引記憶部１０の検索結果を差し引いた結果を求め、検索結果として出力部２に出力する。
【００３３】
マージ部１１は、検索用大規模全文索引記憶部８，登録用小規模全文索引記憶部９及び削除用小規模全文索引記憶部１０の間でのマージ処理（広義でデータ転送ともいえる）を行う。マージ部１１に含まれるバキューム部１２は検索用大規模全文索引記憶部８に対してバキューム処理を行う。削除回数記憶部１３はバキューム処理を実施するか否かを判断するための情報の一例として削除回数を記録している。なお、バキューム処理を実施するか否かを判断するための情報は削除回数に限るものでなく、検索用大規模全文索引記憶部８における後述の未使用領域のサイズであってもよい。検索用大規模全文索引記憶部８に記録されている検索用大規模全文索引は転置ファイルの一例である。
【００３４】
＜全文検索装置１００の動作＞
以下に、上述のごとく構成された本実施形態に係る全文検索装置１００の動作の一例を詳細に説明する。図４〜図６は本実施形態に係る全文検索装置の処理の流れを表した一例のフローチャートである。
【００３５】
ステップＳ１において、全文検索装置１００は利用者からの処理要求を受け取る。全文検索装置１００は、ステップＳ２において、利用者から受け取った処理要求が登録処理に関するものか判定する。また、ステップＳ３において、全文検索装置１００は利用者から受け取った処理要求が削除処理に関するものか検索処理に関するものか判定する。全文検索装置１００は、ステップＳ２及びＳ３の判定結果に基づいて以下の登録処理、削除処理及び検索処理の何れかの処理を実行する。
【００３６】
《登録処理》
登録処理を実行する場合、利用者は文書データを作成し、入力部１から文書データを登録する。ステップＳ１１において、登録処理部３は文書データを文書データ記憶部７に保存し、その文書データを示す識別子（文書識別子）を定める。例えばＳＧＭＬ等のタグ付の文書であれば、登録処理部３は所定のタグ間にある文字列を対象としてもよい。
【００３７】
ステップＳ１２において、登録処理部３はテキスト分割部６を用いて、文書データから部分文字列（トークン）と、そのトークンの出現位置情報とを得る。そして、登録処理部３はステップＳ１３において、文書識別子と各トークンの出現位置情報とを登録用小規模全文索引記憶部９に記録する。ここでの「記録」は、登録用小規模全文索引記憶部９の登録用小規模全文索引（全文索引）への記録であり（以下同様）、ステップ１３のごとき処理を索引記憶ステップとも呼ぶ。
【００３８】
なお、テキスト分割部６で使用される分割手法については、Ｎ文字組をトークンとする手法でもよいし、形態素解析を行い、単語をトークンとする手法でもよい。以下ではＮ文字組みをトークンとする手法を用いたテキスト分割部について説明するが、形態素解析を行った単語をトークンとする手法も同様に適用可能である。また、ステップＳ１３における記録のあと、登録処理部３はステップＳ１４〜Ｓ１６において、適時、後述のマージ処理を行う。
【００３９】
図７は本実施形態に係る全文検索装置の処理の一例を説明する為の説明図である。図７は全文索引の一例を示している。ここでは図７の例を用いて転置ファイル方式の全文索引について詳細に説明する。また、「文書１」及び「文書２」は、入力部１から登録される文書データであるとする。
【００４０】
図７では「文書１」の内容（ここではテキスト分割部６で「文書１」を分割することにより得た内容）６１と「文書２」の内容（ここではテキスト分割部６で「文書２」を分割することにより得た内容）６２とを表している。
【００４１】
「文書１」及び「文書２」の内容６１及び６２は、左側の数字が文字列の先頭からの文字数を表している。例えば「文書１」の内容６１の「全文検索」は先頭から１１文字目に出現していることを意味する。また「文書１」の内容６１の「方法」は先頭から２０文字目及び６０文字目に出現していることを意味する。また「文書１」の内容６１の「全文検索方法」は先頭から３１文字目に出現していることを意味する。
【００４２】
例えば「文書２」の内容６２の「探索方法」は先頭から１文字目に出現していることを意味する。また「文書２」の内容６２の「方法」は先頭から２４文字目に出現していることを意味する。また「文書２」の内容６２の「全文」は先頭から３０文字目及び４２文字目に出現していることを意味する。
【００４３】
なお、２文字組を部分文字列とする場合、登録処理部３は登録された文書データ中の全ての部分文字列を抽出し、それらの文書データ内での出現位置（先頭からの文字数）を部分文字列ごとにまとめて全文索引６３に記録する。
【００４４】
例えば「文書１」は「全文」が先頭から１１，３１文字目の位置、「文検」が先頭から１２，３２文字目の位置に出現しているので、全文索引６３に記録する。全文索引６３では、文書データ内での出現位置だけでなく、どの文書データに出現したかを識別するための文書識別子と部分文字列の出現回数とを加えて記録するので、図７に示したような形式になる。
【００４５】
例えばトークン「全文」に対する転置リスト｛１，２，（１１，３１）｝は「文書１」において２回出現して、その文書データ内での出現位置が先頭から１１，３１文字目であることを意味している。
【００４６】
トークン「全文」に対する転置リスト｛２，２，（３０，４２）｝は「文書２」において２回出現して、その文書データ内での出現位置が先頭から３０，４２文字目であることを意味している。
【００４７】
《削除処理》
削除処理を実行する場合、利用者は入力部１から削除する文書データの文書識別子を入力する。ステップＳ２１において、削除処理部４は文書データ記憶部７から、利用者により入力された文書識別子に対応する文書データを読み出す。
【００４８】
ステップＳ２２において、削除処理部４はテキスト分割部６を用いて、文書データから部分文字列（トークン）と、そのトークンの出現位置情報を得る。例えばＳＧＭＬ等のタグ付の文書であれば、削除処理部４は所定のタグ間にある文字列を対象としてもよい。
【００４９】
ステップＳ２３において、削除処理部４は利用者により入力された文書識別子が登録用小規模全文索引記憶部９に登録されている文書識別子か判定する。登録用小規模全文索引記憶部９に登録されている文書識別子であれば、削除処理部４はステップＳ２５において各トークンの出現位置情報を登録用小規模全文索引記憶部９から削除する。ステップＳ３０において、削除処理部４は文書データ記憶部７から、利用者により入力された文書識別子に対応する文書データを削除する。
【００５０】
なお、登録用小規模全文索引記憶部９に登録されている文書識別子でなければ（検索用大規模全文索引記憶部８に登録されている文書識別子であれば）削除処理部４はステップＳ２４において、文書識別子と、各トークンの出現位置情報とを削除用小規模全文索引記憶部１０に記録する。ステップＳ２４における記録のあと、削除処理部４はステップＳ２６〜Ｓ２９において、適時、後述のマージ処理及びバキューム処理を行う。
【００５１】
《検索処理》
検索処理を実行する場合、利用者は入力部１から検索文字列を入力する。ステップＳ４において、検索処理部５はテキスト分割部６を用いて、利用者から入力された検索文字列から部分文字列（トークン）を得る。
【００５２】
ステップＳ５において、検索処理部５は検索用大規模全文索引記憶部８の検索用大規模全文索引を用いて、検索文字列を含む文書データの文書識別子の集合（Ｒｓ）を得る。ステップＳ６において、検索処理部５は登録用小規模全文索引記憶部９の登録用小規模全文索引を用いて、検索文字列を含む文書データの文書識別子の集合（Ｒｉ）を得る。
【００５３】
また、ステップＳ７において、検索処理部５は削除用小規模全文索引記憶部１０の削除用小規模全文索引を用いて、検索文字列を含む文書データの文書識別子の集合（Ｒｄ）を得る。
【００５４】
ステップＳ８において、検索処理部５はステップＳ５〜Ｓ７で得られた文書データの文書識別子の集合（Ｒｓ，Ｒｉ，Ｒｄ）に対して下記の集合演算を行い、その結果を検索結果（Ｒ）とする。ステップＳ９において、検索処理部５は出力部２を利用して利用者に検索文字列を含む文書データの文書識別子の集合を出力する。
【００５５】
Ｒ＝Ｒｓ＋Ｒｉ−Ｒｄ
ただし、＋を論理和演算子、−を論理差演算子とする。
【００５６】
ここでは、図７の全文索引６３を例として検索処理について詳細に説明する。検索文字列を「全文検索」とすると、テキスト分割部６は「全文」「文検」「検索」の３個のトークンを抽出する。次に、検索処理部５は全文索引６３の対応するトークンの３つの転置リストを調べる。検索処理部５は、それぞれのトークンの出現位置の差が１であるものを探すことで、文書識別子１の文書データの先頭から１１文字目と３１文字目に「全文検索」が存在すると判定できる。
【００５７】
《マージ処理》
マージ部１１によるマージ処理は、元の文書データを用いて登録・削除処理を行う場合に比べて、マージ処理開始時に既に作成されている登録用小規模全文索引及び削除用小規模全文索引の転置リストを直接利用するので、テキスト分割処理によるトークンの切り出し及びその転置リスト作成に要する時間が不要となり、データ転送時間を短くできる。
【００５８】
本実施形態においては転置リスト同士の処理であることからデータ転送処理（データ転送ステップ）のことをマージ処理（マージステップ）と呼ぶ。
【００５９】
全文検索装置１００における文書データの登録・削除処理を転置リスト同士の処理とすることにより、検索用大規模全文索引への文書データの登録・削除処理の際に、既に作成されている登録用小規模全文索引及び削除用小規模全文索引の転置リストを直接利用するので、検索用大規模全文索引へのマージ処理の時間を短縮でき、検索処理の待ち時間を短くすることができる。
【００６０】
登録用小規模全文索引のマージ処理を実行する場合、マージ部１１はステップＳ１４において、登録用小規模全文索引の全てのトークンに対し、そのトークンの転置リストを取り出す。ステップＳ１５において、マージ部１１は登録用小規模全文索引の全てのトークンに対して、検索用大規模全文索引の対応するトークンの転置リストの末尾にステップＳ１４で取り出した転置リストを加える。マージ部１１はステップＳ１６において、登録用小規模全文索引記憶部９に記録されている登録用小規模全文索引を空にする。
【００６１】
削除用小規模全文索引のマージ処理を実行する場合、マージ部１１はステップＳ２６において、削除用小規模全文索引の全てのトークンに対し、そのトークンの転置リストを取り出す。
【００６２】
ステップＳ２７において、マージ部１１は検索用大規模全文索引の対応するトークンの転置リストから、ステップＳ２６で取り出した対応するトークンの転置リスト中の出現位置情報を削除する。ステップＳ２８において、マージ部１１のバキューム部１２はバキューム処理を実施する必要があれば、検索用大規模全文索引記憶部８の検索用大規模全文索引に対してバキューム処理を実施する。ステップＳ２９において、マージ部１１は削除用小規模全文索引を空にする。
【００６３】
バキューム処理とは、例えばデータを固定長のページに分割して格納するデータベース管理システム等において、データの登録や削除によりページ内に発生した空き領域が大きくなってページの利用率が低下したとき、ページ内に発生している空き領域が少なくなるように、順次、データを詰めてページに格納する処理である。つまり、バキューム処理はデータの登録や削除によりページ内に発生した空き領域を集めて、データを格納できるようにする（空き領域を解放する）処理である。
【００６４】
図８はマージ処理及びバキューム処理の概要を説明する為の説明図である。図８は図７における全文索引６３のトークン「全文」の転置リストを例にマージ処理及びバキューム処理の概要を説明するための図である。
【００６５】
検索用大規模全文索引の転置リスト７１の一例として、図８では「全文」に対する転置リスト｛１，２，（１１，３１）｝｛２，２，（３０，４２）｝が記録されている。削除用小規模全文索引の転置リスト７２の一例として、図８では｛１，２，（１１，３１）｝が記録されている。
【００６６】
また、マージ処理７３は図６のステップＳ２６〜Ｓ２８に示した削除用小規模全文索引のマージ処理（削除のマージ処理）である。検索用大規模全文索引の転置リスト７１と削除用小規模全文索引の転置リスト７２とにマージ処理７３を実行することで「全文」に対する転置リスト｛＜空き領域＞｝｛２，２，（３０，４２）｝７４が得られる。
【００６７】
バキューム処理７５は例えば削除回数記憶部１３に記録されている削除回数「１」と閾値との比較により実施するか否かを判断される。ここではバキューム処理を実施すると判断されたものとして説明する。検索用大規模全文索引の転置リスト７４にバキューム処理７５を実行することで「全文」に対する転置リスト｛｛２，２，（３０，４２）｝７６が得られる。検索用大規模全文索引の転置リスト７６は転置リスト７４の空き領域を解放したものである。
【００６８】
また、マージ処理７７は図５のステップＳ１４〜Ｓ１６に示した登録用小規模全文索引のマージ処理（登録のマージ処理）である。図８は登録用小規模全文索引の転置リスト７８の一例として「全文」に対する転置リスト｛５，２，（４，１６）｝，｛８，１，（３）｝が記録されている。
【００６９】
検索用大規模全文索引の転置リスト７６と登録用小規模全文索引の転置リスト７８とにマージ処理７７を実行することで、検索用大規模全文索引の転置リスト７９の一例として「全文」に対する転置リスト｛１，２，（１１，３１）｝，｛２，２，（３０，４２）｝，｛５，２，（４，１６）｝，｛８，１，（３）｝が得られる。
【００７０】
図８に示すように、バキューム処理７５は削除のマージ処理７３と登録のマージ処理７７との間で必要に応じて実施されることで、利用者が明示的に起動しなくても、自動的に実施される。バキューム処理７５が実施されることにより、検索用大規模全文索引の転置リスト７９は空き領域が解放される。したがって、本実施形態に係る全文検索装置１００は転置リストが格納されたページの利用率を上昇させることで、転置ファイルのサイズの増加を抑制できる。
【００７１】
ここでは、マージ処理及びバキューム処理の詳細について説明する。図９は転置リストの論理的な構造について説明する為の説明図である。図９に示すように、転置リスト８２はトークン８１と対応付けられている。図９の転置リスト８２は論理的な構造として文書識別子の一例としての文書ＩＤ、出現回数の一例として出現頻度、１つ以上の出現位置を持つ。
【００７２】
転置ファイル方式を採用した全文検索装置１００では、転置ファイルの入出力を固定長のページに分割して格納する必要がある。したがって、転置ファイル方式を採用した全文検索装置１００は図１０（Ａ）に示すように、入出力単位であるページに合わせて転置リストを複数のページに分割して格納する。
【００７３】
図１０は入出力単位であるページに合わせて格納された転置リストの構造について説明する為の説明図である。転置ファイルへのアクセスは非常に時間が掛かる処理である。したがって、一般的にはページの参照回数を最小限にする実装が行われている。例えば転置リストから文書ＩＤ「２」のものを削除する場合、削除によりページ内に発生した空き領域を削除の度に詰めようとすると、削除する度にＮページを参照しなければならず、非常に時間が掛かってしまう。
【００７４】
そこで、本実施形態に係る全文検索装置１００は文書ＩＤ「２」のものが格納されている領域を図１０（Ｂ）のように、未使用領域としてマークすることで、削除処理を行っている。なお、マークの仕方は様々考えられるが、例えば未使用領域とする領域の先頭に未使用領域であることを示すデータと、未使用領域のサイズとを格納しておくことが考えられる。
【００７５】
しかし、未使用領域は徐々に蓄積されていく。したがって、転置ファイル方式を採用した全文検索装置１００では、転置ファイルが格納されたページの利用率が低下し、転置ファイルのサイズが大きくなってしまう。そこで、本実施形態に係る全文検索装置１００は図１０（Ｂ）に示す未使用領域を図１０（Ｃ）に示すように詰めて、空き領域を開放するバキューム処理を行っている。
【００７６】
バキューム処理は、例えば転置リストが格納されているページを参照し、未使用領域を詰める方法、又は、新しいページを用意し、転置リストの未使用領域以外の部分を新しいページにコピーする方法などが一般的である。
【００７７】
図１１は削除回数記憶部に記録されているバキューム処理を実施するか否かを判断するための情報の一例の構成図である。削除回数記憶部１３はバキューム処理を実施するか否かを判断するための情報として、概念的に図１１（Ａ）又は図１１（Ｂ）のような構造の情報を持っている。なお、実際の構造としては、例えばハッシュ表や、木構造の一種であるＢ＋木などが考えられる。
【００７８】
図１１（Ａ）はバキューム処理を実施するか否かを判断するための情報として削除回数を記録する例である。図１１（Ｂ）はバキューム処理を実施するか否かを判断するための情報として未使用領域のサイズを記録する例である。図１１（Ａ）のようにバキューム処理を実施するか否かを判断するための情報として削除回数を記録した場合、バキューム部１２は削除回数が閾値に達しているとバキューム処理７５を行う。
【００７９】
また、図１１（Ｂ）のようにバキューム処理を実施するか否かを判断するための情報として未使用領域のサイズを記録した場合、バキューム部１２は未使用領域のサイズが閾値に達しているとバキューム処理７５を行う。
【００８０】
図１２はステップＳ２８の処理の詳細を表したフローチャートである。なお、図１２は一例としてバキューム処理を実施するか否かを判断するための情報として削除回数を利用する例を示している。
【００８１】
ステップＳ５１において、バキューム部１２は削除回数記憶部１３が記録している削除回数が、予め指定された回数（閾値）に達しているか判定する。削除回数記憶部１３が記録している削除回数が、予め指定された回数（閾値）に達していれば、バキューム部１２はステップＳ５２において、検索用大規模全文索引記憶部８に記録されている検索用大規模全文索引に対してバキューム処理７５を実施する。なお、削除回数記憶部１３が記録している削除回数が、予め指定された回数（閾値）に達していなければ、バキューム部１２はバキューム処理７５を実施しない。
【００８２】
＜まとめ＞
本実施形態によれば、マージ処理７３及びバキューム処理７５を実施する条件を満たしたときに、マージ処理７３を自動的に行うことで、転置リストが格納されたページの利用率を上昇させることができ、転置ファイルのサイズの増加を抑制できる。
【００８３】
本発明は、具体的に開示された実施例に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。例えば文書管理システム、電子図書館システム、特許公報検索システム、データベース管理システム、エンタープライズインフォメーションポータルなど、多量の文書データを管理するシステムに適用可能である。
【００８４】
なお、特許請求の範囲に記載したマージ手段はマージ部１１に相当し、領域解放手段はバキューム部１２に相当する。
【符号の説明】
【００８５】
１    入力部
２    出力部
３    登録処理部
４    削除処理部
５    検索処理部
６    テキスト分割部
７    文書データ記憶部
８    検索用大規模全文索引記憶部
９    登録用小規模全文索引記憶部
１０    削除用小規模全文索引記憶部
１１    マージ部
１２    バキューム部
１３    削除回数記憶部
１００    全文検索装置
１０１    入力装置
１０２    表示装置
１０３    外部Ｉ／Ｆ
１０３ａ    記録媒体
１０４    ＲＡＭ（Random Access Memory）
１０５    ＲＯＭ（Read Only Memory）
１０６    ＣＰＵ（Central Processing Unit）
１０７    通信Ｉ／Ｆ
１０８    ＨＤＤ（Hard Disk Drive）
１１０    端末装置
２００    全文検索システム
Ｂ    バス
【先行技術文献】
【特許文献】
【００８６】
【特許文献１】特開２００３−１２２７９４号公報
【図１】
0005906810.tif 000002
【図２】
0005906810.tif 000003
【図３】
0005906810.tif 000004
【図４】
0005906810.tif 000005
【図５】
0005906810.tif 000006
【図６】
0005906810.tif 000007
【図７】
0005906810.tif 000008
【図８】
0005906810.tif 000009
【図９】
0005906810.tif 000010
【図１０】
0005906810.tif 000011
【図１１】
0005906810.tif 000012
【図１２】
0005906810.tif 000013