(57)【特許請求の範囲】
【請求項１】
入力された文書データを記憶する文書データ記憶部から、入力された検索条件を含む文書データを、登録用の第１全文索引記憶部、削除用の第２全文索引記憶部、検索用の第３全文索引記憶部を用いて検索する全文検索装置であって、
登録処理を行う場合は、前記文書データからトークンとトークンの出現位置に関する情報を取得し、該トークンと該トークンの出現位置に関する情報を前記登録用の第１全文索引記憶部に記憶する登録処理手段と、
削除処理を行う場合は、前記トークンが前記登録用の第１全文索引記憶部に記憶されているかを判定し、該トークンの出現位置に関する情報が該第１全文索引記憶部に記憶されている場合には、該トークンの出現位置に関する情報を該第１全文索引記憶部から削除し、該トークンの出現位置に関する情報が該第１全文索引記憶部に記憶されていない場合には、該トークンと該トークンの出現位置に関する情報を前記削除用の第２全文索引記憶部に登録する削除処理手段と、
検索処理を行う場合は、前記入力された検索条件を含む文書データの文書識別子の第１の集合を、前記第３全文索引記憶部の索引を用いて求め、前記入力された検索条件を含む文書データの文書識別子の第２の集合を、前記第１全文索引記憶部の索引を用いて求め、前記入力された検索条件を含む文書データの文書識別子の第３の集合を、前記第２全文索引記憶部の索引を用いて求め、その後、前記第１の集合及び前記第２の集合の和集合から前記第３の集合を差し引いた集合を検索結果として出力する検索処理手段と、
前記第３全文索引記憶部の索引に記憶されているトークンの転置リストに対して、前記第１全文索引記憶部から取り出したトークンの転置リストを加えて、該第３全文索引記憶部に記憶されている前記第２全文索引記憶部から取り出したトークンの転置リストの出現位置に関する情報を削除するとともに、該第１全文索引記憶部の転置リスト及び該第２全文索引記憶部の転置リストをマージする処理を実行するマージ手段と、
を有することを特徴とする全文検索装置。
【請求項２】
前記マージ手段は、前記第１全文索引記憶部又は前記第２全文索引記憶部に記憶された文書データの件数が予め指定された件数に達したときに、前記マージする処理を実行することを特徴とする請求項１に記載の全文検索装置。
【請求項３】
前記マージ手段は、前記第１全文索引記憶部又は前記第２全文索引記憶部の容量が予め指定された容量に達したときに、前記マージする処理を実行することを特徴とする請求項１に記載の全文検索装置。
【請求項４】
前記第１全文索引記憶部又は前記第２全文索引記憶部を複数含み、前記第３全文索引記憶部にデータをマージする処理を行っている第１全文索引記憶部又は第２全文索引記憶部とは異なる、他の第１全文索引記憶部又は第２全文索引記憶部を使用して、登録処理又は削除処理を行うことを特徴とする請求項２又は３に記載の検索装置。
【請求項５】
前記第１全文索引記憶部又は第２全文索引記憶部を二つ含み、うち一つの第１全文索引記憶部又は第２全文索引記憶部から前記第３全文索引記憶部にデータをマージする処理を行っている間は、もう一つの第１全文索引記憶部又は第２全文索引記憶部を使用して、登録処理又は削除処理を行うことを特徴とする請求項２又は３に記載の検索装置。
【請求項６】
入力された文書データを記憶する文書データ記憶部から、入力された検索条件を含む文書データを、登録用の第１全文索引記憶部、削除用の第２全文索引記憶部、検索用の第３全文索引記憶部を用いて検索する全文検索方法であって、
登録処理手段が、登録処理を行う場合は、前記文書データからトークンとトークンの出現位置に関する情報を取得し、該トークンと該トークンの出現位置に関する情報を前記登録用の第１全文索引記憶部に記憶する登録処理ステップと、
削除処理手段が、削除処理を行う場合は、前記トークンが前記登録用の第１全文索引記憶部に記憶されているかを判定し、該トークンの出現位置に関する情報が該第１全文索引記憶部に記憶されている場合には、該トークンの出現位置に関する情報を該第１全文索引記憶部から削除し、該トークンの出現位置に関する情報が該第１全文索引記憶部に記憶されていない場合には、該トークンと該トークンの出現位置に関する情報を前記削除用の第２全文索引記憶部に登録する削除処理ステップと、
検索処理手段が、検索処理を行う場合は、前記入力された検索条件を含む文書データの文書識別子の第１の集合を、前記第３全文索引記憶部の索引を用いて求め、前記入力された検索条件を含む文書データの文書識別子の第２の集合を、前記第１全文索引記憶部の索引を用いて求め、前記入力された検索条件を含む文書データの文書識別子の第３の集合を、前記第２全文索引記憶部の索引を用いて求め、その後、前記第１の集合及び前記第２の集合の和集合から前記第３の集合を差し引いた集合を検索結果として出力する検索処理ステップと、
マージ手段が、前記第３全文索引記憶部の索引に記憶されているトークンの転置リストに対して、前記第１全文索引記憶部から取り出したトークンの転置リストを加えて、該第３全文索引記憶部に記憶されている前記第２全文索引記憶部から取り出したトークンの転置リストの出現位置に関する情報を削除するとともに、該第１全文索引記憶部の転置リスト及び該第２全文索引記憶部の転置リストをマージする処理を実行するマージステップと、
を含むことを特徴とする全文検索方法。
【請求項７】
前記マージステップは、前記第１全文索引記憶部又は前記第２全文索引記憶部に記憶された文書データの件数が予め指定された件数に達したときに、前記マージする処理を実行することを特徴とする請求項６に記載の全文検索方法。
【請求項８】
前記マージステップは、前記第１全文索引記憶部又は前記第２全文索引記憶部の容量が予め指定された容量に達したときに、前記マージする処理を実行することを特徴とする請求項６に記載の全文検索方法。
【請求項９】
コンピュータに、請求項６〜８のいずれか１項に記載の全文検索方法を実行させるためのプログラム。
【請求項１０】
請求項９に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、全文検索装置、全文検索方法、プログラム、及び記録媒体に関し、より詳細には、複数の文書データから指定された文字列を含む文書を検索する全文検索装置、全文検索方法、プログラム、及び記録媒体に関する。本発明は、例えば文書管理システム、電子図書館システム、特許公報検索システムなど、多量の文書データを管理するシステムに適用可能である。
【０００２】
【従来の技術】
近年、情報通信技術の発達により電子化された文書及びその文書に関する情報がインターネットなどを介して大量に流通している。この電子化文書及び情報の流通に際し、所望の文書を精度よく、さらには高速に検索する文書検索装置が提案されている。
【０００３】
そのような文書検索装置においてはキーワード検索手法や全文検索手法が用いられている。全文検索手法を用いた全文検索装置は、任意の検索文字列と検索対象の文書全てとの間で照合を行なって、検索文字列を含む文書を漏れなく抽出する装置であり、キーワード検索手法のように検索対象となる全ての文書に対してキーワードを予め付与するといった多大な人力が必要ない。全文検索装置としては、様々な種類のものが提案されているが、その１種として転置（索引）ファイル方式を採用した装置がある。転置ファイル方式では、検索のための補助ファイルとして、文字／単語／n-gram（n文字連接）などが出現する文書、或いはそれらの文書中の出現位置を記録する転置ファイルを予め構築し、全文検索時には、転置ファイルのみを用いて検索するもので非常に高速な検索を行なうことが可能であり大量文書の高速検索が要求されるシステムに対して有効である。
【０００４】
なお、全文検索方式一般、転置ファイル方式の詳細については、文献「情報検索アルゴリズム」（北研二、津田和彦、獅々堀正幹 著、共立出版株式会社、pp.160-179）、特開平１１−０７３４２９号公報の従来技術、及び全文検索システム協議会平成１０年度活動報告(http://www.ftsanet.com/dbtokyo99/Db99.htm)などで述べられており、公知であるのでその説明を省略する。
【０００５】
転置ファイル方式を採用した従来技術として、特許第３０２４５４４号公報には、検索用インデックスファイルとは別にリアルタイム処理データを記憶することにより、検索用インデックスファイルを更新中であっても検索処理を行うことが可能な情報検索装置が記載されている。また、特開平７−１４６８８０号公報には、新規文書を登録する際に、主インデックスよりも小さな副インデックスに登録し、登録時間を短くすることが可能な文書検索装置及び方法が記載されている。
【０００６】
しかしながら、上述した公報も含め、転置ファイル方式では通常原データの数倍にも及ぶ転置ファイルを構築する必要があり、転置ファイル方式の全文索引は登録されている文書データ量が多くなるにしたがって登録・削除処理に時間を要するようになり、全文検索装置としては利用者側からみた登録・削除処理のレスポンスタイムが長くなる。
【０００７】
【発明が解決しようとする課題】
本発明は、上述のごとき実情に鑑みてなされたものであり、利用者側からみた登録及び削除処理のレスポンスタイムを短くすることが可能な、全文検索装置、全文検索方法、コンピュータをその装置として機能させるためのプログラム、コンピュータにその方法の手順を実行させるためのプログラム、及びそれらのプログラムを記録したコンピュータ読み取り可能な記録媒体を提供することをその目的とする。
【０００９】
【課題を解決するための手段】
請求項１の発明は、入力された文書データを記憶する文書データ記憶部から、入力された検索条件を含む文書データを、登録用の第１全文索引記憶部、削除用の第２全文索引記憶部、検索用の第３全文索引記憶部を用いて検索する全文検索装置であって、登録処理を行う場合は、前記文書データからトークンとトークンの出現位置に関する情報を取得し、該トークンと該トークンの出現位置に関する情報を前記登録用の第１全文索引記憶部に記憶する登録処理手段と、削除処理を行う場合は、前記トークンが前記登録用の第１全文索引記憶部に記憶されているかを判定し、該トークンの出現位置に関する情報が該第１全文索引記憶部に記憶されている場合には、該トークンの出現位置に関する情報を該第１全文索引記憶部から削除し、該トークンの出現位置に関する情報が該第１全文索引記憶部に記憶されていない場合には、該トークンと該トークンの出現位置に関する情報を前記削除用の第２全文索引記憶部に登録する削除処理手段と、検索処理を行う場合は、前記入力された検索条件を含む文書データの文書識別子の第１の集合を、前記第３全文索引記憶部の索引を用いて求め、前記入力された検索条件を含む文書データの文書識別子の第２の集合を、前記第１全文索引記憶部の索引を用いて求め、前記入力された検索条件を含む文書データの文書識別子の第３の集合を、前記第２全文索引記憶部の索引を用いて求め、その後、前記第１の集合及び前記第２の集合の和集合から前記第３の集合を差し引いた集合を検索結果として出力する検索処理手段と、前記第３全文索引記憶部の索引に記憶されているトークンの転置リストに対して、前記第１全文索引記憶部から取り出したトークンの転置リストを加えて、該第３全文索引記憶部に記憶されている前記第２全文索引記憶部から取り出したトークンの転置リストの出現位置に関する情報を削除するとともに、該第１全文索引記憶部の転置リスト及び該第２全文索引記憶部の転置リストをマージする処理を実行するマージ手段と、を有することを特徴としたものである。
【００１３】
請求項２の発明は、請求項１の発明において、前記マージ手段は、前記第１全文索引記憶部又は前記第２全文索引記憶部に記憶された文書データの件数が予め指定された件数に達したときに、前記マージする処理を実行することを特徴としたものである。
【００１４】
請求項３の発明は、請求項１の発明において、前記マージ手段は、前記第１全文索引記憶部又は前記第２全文索引記憶部の容量が予め指定された容量に達したときに、前記マージする処理を実行することを特徴としたものである。
【００１５】
請求項４の発明は、請求項２又は３の発明において、前記第１全文索引記憶部又は前記第２全文索引記憶部を複数含み、前記第３全文索引記憶部にデータをマージする処理を行っている第１全文索引記憶部又は第２全文索引記憶部とは異なる、他の第１全文索引記憶部又は第２全文索引記憶部を使用して、登録処理又は削除処理を行うことを特徴としたものである。
【００１６】
請求項５の発明は、請求項２又は３の発明において、前記第１全文索引記憶部又は第２全文索引記憶部を二つ含み、うち一つの第１全文索引記憶部又は第２全文索引記憶部から前記第３全文索引記憶部にデータをマージする処理を行っている間は、もう一つの第１全文索引記憶部又は第２全文索引記憶部を使用して、登録処理又は削除処理を行うことを特徴としたものである。
【００１７】
請求項６の発明は、入力された文書データを記憶する文書データ記憶部から、入力された検索条件を含む文書データを、登録用の第１全文索引記憶部、削除用の第２全文索引記憶部、検索用の第３全文索引記憶部を用いて検索する全文検索方法であって、登録処理手段が、登録処理を行う場合は、前記文書データからトークンとトークンの出現位置に関する情報を取得し、該トークンと該トークンの出現位置に関する情報を前記登録用の第１全文索引記憶部に記憶する登録処理ステップと、削除処理手段が、削除処理を行う場合は、前記トークンが前記登録用の第１全文索引記憶部に記憶されているかを判定し、該トークンの出現位置に関する情報が該第１全文索引記憶部に記憶されている場合には、該トークンの出現位置に関する情報を該第１全文索引記憶部から削除し、該トークンの出現位置に関する情報が該第１全文索引記憶部に記憶されていない場合には、該トークンと該トークンの出現位置に関する情報を前記削除用の第２全文索引記憶部に登録する削除処理ステップと、検索処理手段が、検索処理を行う場合は、前記入力された検索条件を含む文書データの文書識別子の第１の集合を、前記第３全文索引記憶部の索引を用いて求め、前記入力された検索条件を含む文書データの文書識別子の第２の集合を、前記第１全文索引記憶部の索引を用いて求め、前記入力された検索条件を含む文書データの文書識別子の第３の集合を、前記第２全文索引記憶部の索引を用いて求め、その後、前記第１の集合及び前記第２の集合の和集合から前記第３の集合を差し引いた集合を検索結果として出力する検索処理ステップと、マージ手段が、前記第３全文索引記憶部の索引に記憶されているトークンの転置リストに対して、前記第１全文索引記憶部から取り出したトークンの転置リストを加えて、該第３全文索引記憶部に記憶されている前記第２全文索引記憶部から取り出したトークンの転置リストの出現位置に関する情報を削除するとともに、該第１全文索引記憶部の転置リスト及び該第２全文索引記憶部の転置リストをマージする処理を実行するマージステップと、を含むことを特徴としたものである。
【００１８】
請求項７の発明は、請求項６の発明において、前記マージステップは、前記第１全文索引記憶部又は前記第２全文索引記憶部に記憶された文書データの件数が予め指定された件数に達したときに、前記マージする処理を実行することを特徴としたものである。
【００１９】
請求項８の発明は、請求項６の発明において、前記マージステップは、前記第１全文索引記憶部又は前記第２全文索引記憶部の容量が予め指定された容量に達したときに、前記マージする処理を実行することを特徴としたものである。
【００４９】
請求項９の発明は、コンピュータに、請求項６〜８のいずれか１項に記載の全文検索方法を実行させるためのプログラムである。
【００５０】
請求項１０の発明は、請求項９に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【００５１】
【発明の実施の形態】
本発明は、小規模の全文索引を登録用及び削除用に別に用意し登録及び削除のレスポンスタイムの悪化を防ぎ、検索処理の際には大規模の全文索引の検索結果に、登録用の小規模全文索引の検索結果を加え、削除用の小規模全文索引の検索結果を除き、利用者に返す検索結果とする全文検索装置であり、これは、本出願人による特願２００１−７８０２６号明細書に記載の手法を全文検索装置に適用し、上述した課題を解決したものである。
【００５２】
なお、上述の特願２００１−７８０２６号明細書には、高度な検索要求に高速に応答できる性能を維持しつつ、システム稼働中の更新性能をさらに向上させることができるデータベース管理システム、プログラム、及び記録媒体が記載されており、登録・削除のためのデータ保持手段を検索向けデータ保持手段とは別に用意することによって、登録・削除のスループットを高くすることを特徴としている。しかしながら、上述の明細書に記載の手法では、登録用及び削除用の小規模な全文索引から検索用の大規模な全文索引へのデータ転送手段で小規模索引に登録されている文書データの識別子から元の文書データを取得し、大規模な索引に登録及び削除を行っている。上述のごとく、大規模な全文索引への登録・削除処理には時間がかかるので、データ転送処理の時間が長くなる。一般に全文索引への登録・削除処理の間は検索処理が行えないので、利用者から見た検索処理のレスポンスタイムが悪くなるという問題がある。
【００５３】
本発明では、小規模な全文索引から大規模な全文索引へのデータ転送手段において、元の文書データを用いるのではなく転置ファイル方式の全文索引を用いることによって、すなわち全文索引の構成要素である転置リストを用いることによって、データ転送に要する時間を短くするようにしている。
【００５４】
図１は、本発明の一実施形態に係る全文検索装置の機能を説明するためのブロック図、図２は、図１における全文検索装置をスタンドアロンで構成した場合のハードウェア構成例を示す図、図３は、図１における全文検索装置をサーバ／クライアントで構成した場合のハードウェア構成例を示す図である。
【００５５】
本発明に係る全文検索装置は、複数の文書データ（複数の電子化文書）から指定された文字列を含む文書を検索する装置である。なお、本明細書中、全文検索装置における「全文検索」とは、検索すべき全ての文字列を対象とした検索装置であることを意味しており、したがって、例えばＳＧＭＬ等のタグ付の文書であれば、適宜、所定のタグ間にある文字列のみを対象としてもよい。
【００５６】
図１を参照すると、本実施形態においては、入力手段１では、登録処理用のテキストデータ，削除処理用の文書識別子，検索処理用の検索条件などが入力され、夫々、登録処理手段３，削除処理手段４，検索処理手段５に渡される。登録処理手段３では文書データに関する登録処理を行う。登録処理手段３における登録処理は文書データ記憶部７及び登録用小規模全文索引記憶部９に対して行われる。削除処理手段４では文書データに関する削除処理を行う。削除処理手段４における削除処理は、入力手段１で入力された文書識別子に基づいて、文書データ記憶部７に記憶された文書データを読み出し、テキスト分割手段６を用い、登録用小規模全文索引記憶部９に登録された索引である場合にはそれを削除し、登録された索引でない場合には削除用小規模全文索引記憶部１０にその索引を記録する。なお、テキスト分割手段６では、登録処理手段３，削除処理手段４，検索処理手段５の各々で必要な、登録処理における文書データから部分文字列への分割処理、削除処理における文書データから部分文字列への分割処理、検索処理における検索条件（検索文字列）から部分文字列への分割処理を行う。
【００５７】
また、検索処理手段５における検索処理は、検索用大規模全文索引記憶部８，登録用小規模全文索引記憶部９，削除用小規模全文索引記憶部１０に対して実行し、記憶部８及び９の検索結果から記憶部１０における検索結果を差し引いた結果を求め、検索結果として出力手段２で出力する。マージ手段１１においては、検索用大規模全文索引記憶部８，登録用小規模全文索引記憶部９，削除用小規模全文索引記憶部１０間でのマージ処理（広義でデータ転送ともいえる）を行う。
【００５８】
なお、以降、特に説明はしないが、削除処理手段４における削除処理に関し、削除用小規模全文索引記憶部１０を使用しなくとも、例えば削除する文書データのみを削除して処理時間が得られる休日などに、文書データ記憶部７に存在する文書データと整合して検索用大規模全文索引記憶部８のデータを更新するなど、他の削除用の文書データ（及び索引）管理方法を用い、登録用小規模全文索引記憶部９を使用した登録処理のみを行う形態も採用できる。逆に、登録用小規模全文索引記憶部９を使用した登録処理を行わず、削除用小規模全文索引記憶部１０のみを使用した削除処理のみを行う形態も採用できる。
【００５９】
図２に示すスタンドアロンでのハードウェア構成においては、図１における入力手段１は入力装置２１に実現され、出力手段２は表示装置２２に実現される。各種処理手段３〜６，１１は主制御装置（ＣＰＵ，メモリ等）２４に、各種記憶部７〜１０は、例えば全てを記憶装置２５として、或いは個々の記憶装置として、さらには記憶装置２５におけるファイルとして実現される。例えば、１つの限られた記憶装置を用いて本発明に係る全文検索を行う場合、検索処理をメインに行うのか、登録・削除処理をメインに行うのかで、その使用する領域を上手く割り当てるとよい。また、入出力制御装置２３は主制御装置２４の制御信号に従って入力装置２１及び表示装置２２を制御する。
【００６０】
図３に示すサーバ／クライアントでのハードウェア構成においては、図１における入力手段１はクライアント３０の入力装置３１で実現され、出力手段２はクライアント３０の表示装置３２に実現される。各種処理手段３〜６，１１はクライアント３０及びサーバ５０の主制御装置（ＣＰＵ，メモリ等）３４，５２に実現され、各種記憶部７〜１０は、例えば、全てをサーバ５０の記憶装置５３として、或いはサーバ５０に接続された個々の記憶装置として、さらには記憶装置２５におけるファイルとして実現される。また、クライアント３０，サーバ５０のネットワーク制御装置３５，５１は、ネットワーク４０を介してクライアント３０とサーバ５０の間のデータ伝送等の制御を行う。さらにクライアント３０の入出力制御装置３３は、主制御装置３４の制御信号に従って入力装置２１及び表示装置２２を制御する。
【００６１】
以下に、上述のごとく構成された本実施形態に係る全文検索装置の動作の一例を詳細に説明する。
図４乃至図６は、図１の全文検索装置における処理例を説明するためのフロー図である。
全文検索装置は、利用者からの処理要求を受け取ると（ステップＳ１）、まず、その処理が、登録処理であるのか（ステップＳ２）、削除処理であるのか（ステップＳ３）、検索処理であるのか（ステップＳ３でＮＯ）を判定する。全文検索装置は、この判定に基づいて以下の各処理を実行することとなる。
【００６２】
（登録処理）
登録処理を実行するには、まず利用者が文書データを作成し、入力手段１からその文書データを登録する。登録処理手段３において文書データを文書データ記憶部７に保存し、同時にその文書データを示す識別子（文書識別子）を定める（ステップＳ１１）。例えばＳＧＭＬ等のタグ付の文書であれば、適宜、所定のタグ間にある文字列のみを対象としてもよい。さらに登録処理手段３において、テキスト分割手段６を用いて文書データから部分文字列（トークン）とそのトークンの出現位置情報を得る（ステップＳ１２）。最後に文書識別子と各トークンの出現位置情報を登録用小規模全文索引記憶部９に記録する（ステップＳ１３）。ここでの「記録」は記憶部の全文索引への記録であり（以下同様）、ステップ１３のごとき処理を索引記憶ステップとも呼ぶ。なお、テキスト分割手段６で使用される分割手法については、Ｎ文字組をトークンとする手法でもよいし、形態素解析を行い単語をトークンとする手法でもよい。以下の例ではＮ文字組みをトークンとする手法を用いたテキスト分割手段に限って説明するが形態素解析を行った単語をトークンとする手法に対しても同様に適用可能である。また、後述するが、ステップＳ１３における記録の後、適時マージ処理が行われる（ステップＳ１４〜Ｓ１６）。
【００６３】
図７は、図１の全文検索装置における処理を説明するための図で、全文索引の一例を示す図である。図７の例を用いて転置ファイル方式の全文索引について詳細に説明する。
登録文書データを文書１，文書２とし、それらの内容（ここではテキスト分割手段６で分割することにより得た内容）がそれぞれ、図７の符号６１，６２で表されるものとする。ここで、各文書の左の数字は文字列の先頭からの文字数を表している。つまり、文書１では、「全文検索」は先頭から１１文字目、「方法」は２０，６０文字目、「全文検索方法」は３１文字目に出現していることを意味する。また文書２では、「探索方法」は先頭から１文字目、「方法」は２４文字目、「全文」は３０，４２文字目に出現していることを意味する。
【００６４】
なお、２文字組を部分文字列とする場合、文書中の全ての部分文字列を抽出し、それらの文書内での出現位置（先頭からの文字数）を部分文字列ごとにまとめて索引に記録する。例えば、文書１からは「全文」が１１，３１の位置、「文検」が１２，３２の位置に出現しているので、索引に記録する。索引では、文書内での出現位置だけでなく、どの文書に出現したかを識別するための文書識別子と出現回数を加えて記録するので、図４の符号６３で示したような形式になる。例えば、「全文」に対する転置リスト｛１，２，（１１，３１）｝及び｛２，２，（３０，４２）｝はそれぞれ、文書１において２回出現してその位置は１１，３１であること、及び文書２において２回出現してその位置は３０，４２であることを意味する。
【００６５】
（削除処理）
削除処理を実行するには、まず利用者が入力手段１から削除する文書の文書識別子を入力する。次に、削除処理手段４において文書データ記憶部７から文書識別子に対応する文書データを読み出す（ステップＳ２１）。さらに削除処理手段４において、テキスト分割手段６を用いて文書データから部分文字列（トークン）とそのトークンの出現位置情報を得る（ステップＳ２２）。例えばＳＧＭＬ等のタグ付の文書であれば、適宜、所定のタグ間にある文字列のみを対象としてもよい。文書識別子が登録用小規模全文索引に登録されている文書識別子かを判定し（ステップＳ２３）、登録用小規模全文索引に登録されている文書識別子である場合には、各トークンの出現位置情報を登録用小規模全文索引記憶部９から削除する（ステップＳ２５）。文書識別子が登録用小規模全文索引に登録されていない場合（検索用大規模全文索引に登録されている場合）には、文書識別子と各トークンの出現位置情報を削除用小規模全文索引記憶部１０に記録する（ステップＳ２４）。そして、削除処理手段４において文書データ記憶部７から文書識別子に対応する文書データを削除する（ステップＳ２９）。また、後述するが、ステップＳ２４における記録の後、適時マージ処理が行われる（ステップＳ２６〜Ｓ２８）。
【００６６】
（検索処理）
検索処理を実行するには、まず利用者が入力手段１から検索文字列を入力する。次に、検索処理手段５において、テキスト分割手段６を用いて検索文字列からトークンを得る（ステップＳ４）。また、検索処理手段５において検索用大規模全文索引記憶部８の検索用大規模全文索引を用いて、検索文字列を含む文書データの文書識別子の集合（Ｒｓ）を得る（ステップＳ５）とともに、登録用小規模全文索引記憶部９の登録用小規模全文索引を用いて、検索文字列を含む文書データの文書識別子の集合（Ｒｉ）を得る（ステップＳ６）。さらに、検索処理手段５において削除用小規模全文索引記憶部１０の削除用小規模全文索引を用いて、検索文字列を含む文書データの文書識別子の集合（Ｒｄ）を得る（ステップＳ７）。検索処理手段５は得られた文書識別子の集合（Ｒｓ，Ｒｉ，Ｒｄ）に対して下記の集合演算を行い、その結果を検索結果（Ｒ）とし（ステップＳ８）、出力手段２を通じて利用者に検索文字列を含む文書データの文書識別子の集合を出力する（ステップＳ９）。
Ｒ＝Ｒｓ＋Ｒｉ−Ｒｄ
ただし、＋を論理和演算子、−を論理差演算子とする。
【００６７】
図７の全文索引６３を例として検索処理について詳細に説明する。
検索文字列を「全文検索」とすると、テキスト分割手段が「全文」，「文検」，「検索」の３個のトークンを抽出する。次に全文索引６３の対応するトークンの３つの転置リストを調べる。それぞれのトークン出現位置の差が１であるものを探すと文書識別子１の１１文字目と３１文字目に「全文検索」が存在することがわかる。
【００６８】
（マージ処理）
マージ手段１１によるマージ処理は、上述の特願２００１−７８０２６号明細書におけるデータ転送手段に変わる処理である。
元の文書データを用いて登録・削除処理を行う場合に比べて、処理開始時に既に作成されている転置リストを直接利用するのでテキスト分割処理によるトークンの切り出し及びその転置リスト作成に要する時間が不要となり、データ転送時間を短くできる。本発明においては転置リスト同士の処理であることからデータ転送処理（データ転送ステップ）のことをマージ処理（マージステップ）とも呼ぶ。全文検索装置における文書データの登録・削除処理を転置リスト同士の処理とすることにより、検索用全文索引へのデータ登録・削除の際に、既に作成されている転置リストを直接利用するので検索用全文索引へのマージ処理の時間を短縮でき、検索処理の待ち時間を短くすることができる。
【００６９】
マージ処理を実行するには、まず登録用小規模全文索引の全てのトークンに対して、（ａ）全文索引からそのトークンの転置リストを取り出す処理（ステップＳ１４）、及び（ｂ）検索用大規模全文索引の対応するトークンの転置リストの末尾に先の転置リストを加える処理（ステップＳ１５）を行う。次に登録用小規模全文索引を空にする（ステップＳ１６）。また、削除用小規模全文索引の全てのトークンに対して、（ｃ）全文索引からそのトークンの転置リストを取り出す処理（ステップＳ２６）、及び（ｄ）検索用大規模全文索引の対応するトークンの転置リストから（ｃ）で取り出した転置リスト中の出現位置情報を削除する処理（ステップＳ２７）を行う。次に削除用小規模全文索引を空にする（ステップＳ２８）。
【００７０】
図８は、図７における全文索引６３のトークン「全文」の転置リストを例にマージ処理の概要を説明するための図である。
検索用全文索引の転置リスト７１として、「全文」に対する転置リスト｛１，２，（１１，３１）｝，｛２，２，（３０，４２）｝、登録用全文索引の転置リスト７２として、「全文」に対する転置リスト｛５，２，（４，１６）｝，｛８，１，（３）｝をマージ処理７３する場合を説明する。マージ処理７３を実行することにより、「全文」に対する転置リスト｛１，２，（１１，３１）｝，｛２，２，（３０，４２）｝，｛５，２，（４，１６）｝，｛８，１，（３）｝（７４）が得られる。さらに、この転置リストと、削除用全文索引の転置リスト７６としての、「全文」に対する転置リスト｛１，２，（１１，３１）｝とをマージ処理７５することにより、「全文」に対する転置リスト｛２，２，（３０，４２）｝，｛５，２，（４，１６）｝，｛８，１，（３）｝（７７）が得られる。
【００７１】
（マージ処理の形態１）
マージ処理は、登録用小規模全文索引記憶部９における登録用小規模全文索引に登録されている文書識別子の数が予め指定されている数に達したときに登録処理手段３によって起動され、マージ手段１１により実行される。
【００７２】
（マージ処理の形態２）
マージ処理は、登録用小規模全文索引記憶部９における記憶容量（大きさ）が予め指定されているサイズになったときに登録処理手段３によって起動され、マージ手段１１により実行されるようにしてもよい。この形態により、利用者から登録される文書データの大きさにばらつきがあるような応用形態として使用される場合に、小さな文書データが連続して登録されたときに登録用小規模全文索引への登録時間が長くなる前にマージ処理が開始されることを防ぐことができる。サイズを起動条件にすることでマージの処理時間を均等にすることができる。さらに、前述のマージ処理（形態１）の場合には件数を起動条件にしており全文索引記憶部の大きさを管理する必要がないので処理が簡単になる利点がある。
【００７３】
（マージ処理の形態３）
削除用小規模全文索引のマージ処理は削除処理手段４によって起動され、マージ手段１１により実行されるようにしてもよい。起動条件は削除用小規模全文索引に登録されている文書識別子の数が予め指定されている数に達したときとしてもよい。
【００７４】
（マージ処理の形態４）
削除用小規模全文索引のマージ処理は削除処理手段４によって起動され、マージ手段１１により実行されるようにしてもよい。起動条件は削除用小規模全文索引記憶部１０の大きさが予め指定されているサイズに達したときとしてもよい。形態３，４では削除処理が多く発生しないような場合、マージ処理の時間を短縮できる利点がある。
【００７５】
上述のごときマージ処理の各形態により、全文検索装置においては登録・削除する文書データの特徴や利用分野の特徴に適した条件で全文索引のマージ処理を開始することが可能となり、マージ処理の発生回数を減らせ、システム全体のスループットを向上させることが可能となる。さらに、マージの開始条件は、マージ処理にかかる所要時間により可変としてもよいし、また、登録により生じるマージと、削除により生じるマージを、いずれかの開始条件のもとで同時に起動させてもよい。
【００７６】
上述した実施形態に係る全文検索装置では、本出願人による特願２００１−７８０２６号明細書に記載の手法を転置ファイル方式の全文索引を用いた全文検索装置に適用し、小規模な全文索引から大規模な全文索引へのデータ転送手段において、元の文書データを用いるのではなく転置ファイル方式の全文索引の構成要素である転置リストを用いることによってデータ転送に要する時間を短くしている。
【００７７】
次に説明する本発明の他の実施形態に係る全文検索装置は、上述した実施形態に係る全文検索装置において、本出願人による特願２００１−１０１０２４号明細書に記載の書き込み遅延データベース管理方法、装置、プログラム、及び記録媒体で用いた手法を適用したものである。これにより、登録用或いは削除用の小規模全文索引から検索用の大規模全文索引へのデータ転送（転置リストのマージ処理）を行っている間は、その登録用或いは削除用の小規模全文索引記憶部を使用することができず、登録処理或いは削除処理を実行することができないという問題を解決することができる。
【００７８】
図９は、本発明の他の実施形態に係る全文検索装置の機能を説明するためのブロック図である。
本実施形態に係る全文検索装置では、登録用及び削除用の小規模全文索引を二つずつ用意し、大規模全文索引へのマージ（データ転送）を行っている間は、他方の小規模全文索引を使用して登録処理或いは削除処理を実行することにより、処理不能な期間を無くすようにしている。すなわち、本実施形態に係る全文検索装置においては、登録用小規模全文索引を二つ備えることでマージ処理を実行中でも登録処理を行うことが可能となり、また削除用小規模全文索引を二つ備えることでマージ処理を実行中でも削除処理を行うことが可能となる。本実施形態によれば、例えば書類をスキャナ等で読み取り、ＯＣＲ処理して、各書類を登録したいときなど、登録処理とそれによるマージ処理が頻繁に連続して行われるときなどに好適である。このようなイメージデータも通常のアプリケーションデータと同じように全文検索が高レスポンスで可能となる。
【００７９】
図１で説明した登録用小規模全文索引記憶部９が登録用小規模全文索引記憶部Ａ（９ａ）及び登録用小規模全文索引記憶部Ｂ（９ｂ）の二つの記憶部を有するものとして、図１で説明した削除用小規模全文索引記憶部１０が削除用小規模全文索引記憶部Ａ（１０ａ）及び削除用小規模全文索引記憶部Ｂ（１０ｂ）の二つの記憶部を有するものとして本実施形態を説明する。なお、図２及び図３で説明したようなハードウェア構成例を本実施形態に係る全文検索装置にも適用可能である。ただし、これらの記憶部の１又は複数を記憶装置２５，５３ではなく、メモリ上に設けても効果的である。
【００８０】
以下に、上述のごとく構成された本実施形態に係る全文検索装置の動作の一例を詳細に説明する。
図１０乃至図１２は、図９の全文検索装置における処理例を説明するためのフロー図である。
全文検索装置は、利用者からの処理要求を受け取ると（ステップＳ３１）、まず、その処理が、登録処理であるのか（ステップＳ３２）、削除処理であるのか（ステップＳ３３）、検索処理であるのか（ステップＳ３３でＮＯ）を判定する。全文検索装置は、この判定に基づいて以下の各処理を実行することとなる。
【００８１】
（登録処理）
登録処理を実行するには、まず利用者が文書データを作成し、入力手段１からその文書データを登録する。登録処理手段３において文書データを文書データ記憶部７に保存し、同時にその文書データを示す識別子（文書識別子）を定める（ステップＳ４１）。さらに登録処理手段３において、テキスト分割手段６を用いて文書データから部分文字列（トークン）とそのトークンの出現位置情報を得る（ステップＳ４２）。なお、テキスト分割手段６で使用される分割手法や全文索引については前述した通りである。文書識別子と各トークンの出現位置情報をその時点の登録用小規模全文索引記憶部（例えば登録用小規模全文索引記憶部Ａ（９ａ））に記録する（ステップＳ４３）。
【００８２】
ステップＳ４３における記録の後、適時マージ処理が行われるが、ここではマージ開始条件に基づいて行われるものとして説明する。まず、ステップＳ４３において記録した結果、マージ開始条件を満たすかを判定する（ステップＳ４４）。マージ開始条件を満たさなければ処理を終了する。なお、図１乃至図８の実施形態において説明したマージ処理開始の条件の各形態は、本実施形態においても適用可能である。また、他方の登録用小規模全文索引記憶部（ここでは登録用小規模全文索引記憶部Ｂ（９ｂ））がマージ処理を実行中であるかも判定する（ステップＳ４５）。実行中の場合にはそのマージ処理の終了を待つ。
【００８３】
マージ開始条件を満たし、且つもう一方の登録用小規模全文索引記憶部Ｂ（９ｂ）がマージ処理を実行中ではない場合に、登録用小規模全文索引記憶部Ａ（９ａ）における登録用小規模全文索引Ａに対して後述のマージ処理（ステップＳ４７〜Ｓ４９）を起動し、次の登録処理に対して記録を行うべき記憶部を登録用小規模全文索引記憶部Ａ（９ａ）からもう一方の登録用小規模全文索引記憶部Ｂ（９ｂ）に切り替える（ステップＳ４６）。マージ処理が起動された場合、マージ手段１１は登録処理手段３とは非同期にマージ処理を実行する。
【００８４】
（削除処理）
削除処理を実行するには、まず利用者が入力手段１から削除する文書の文書識別子を入力する。次に、削除処理手段４において文書データ記憶部７から文書識別子に対応する文書データを読み出す（ステップＳ５１）。さらに削除処理手段４において、テキスト分割手段６を用いて文書データから部分文字列（トークン）とそのトークンの出現位置情報を得る（ステップＳ５２）。
【００８５】
次に、文書識別子が登録用小規模全文索引に登録されている文書識別子かを判定し（ステップＳ５３）、登録用小規模全文索引に登録されている文書識別子である場合には、各トークンの出現位置情報を登録用小規模全文索引記憶部９（９ａ及び９ｂ）から削除する（ステップＳ５５）。文書識別子が登録用小規模全文索引に登録されていない場合（検索用大規模全文索引に登録されている場合）には、文書識別子と各トークンの出現位置情報をその時点の削除用小規模全文索引記憶部（例えば削除用小規模全文索引記憶部Ａ（１０ａ））に記録する（ステップＳ５４）。そして、削除処理手段４において文書データ記憶部７から文書識別子に対応する文書データを削除する（ステップＳ６２）。
【００８６】
ステップＳ５４における記録の後、適時マージ処理が行われるが、ここではマージ開始条件に基づいて行われるものとして説明する。まず、ステップＳ５４において記録した結果、マージ開始条件を満たすかを判定する（ステップＳ５６）。マージ開始条件を満たさなければ処理を終了する（ステップＳ６２の処理は必要）。なお、図１乃至図８の実施形態において説明したマージ処理開始の条件の各形態は、本実施形態においても適用可能である。また、他方の削除用小規模全文索引記憶部（ここでは削除用小規模全文索引記憶部Ｂ（１０ｂ））がマージ処理を実行中であるかも判定する（ステップＳ５７）。実行中の場合にはそのマージ処理の終了を待つ。
【００８７】
マージ開始条件を満たし、且つもう一方の削除用小規模全文索引記憶部Ｂ（１０ｂ）がマージ処理を実行中ではない場合に、削除用小規模全文索引記憶部Ａ（１０ａ）における削除用小規模全文索引Ａに対して後述のマージ処理（ステップＳ５９〜Ｓ６１）を起動し、次の削除処理に対して記録を行うべき記憶部を削除用小規模全文索引記憶部Ａ（１０ａ）からもう一方の削除用小規模全文索引記憶部Ｂ（１０ｂ）に切り替える（ステップＳ５８）。マージ処理が起動された場合、マージ手段１１は削除処理手段４とは非同期にマージ処理を実行する。
【００８８】
（検索処理）
検索処理を実行するには、まず利用者が入力手段１から検索文字列を入力する。次に、検索処理手段５において、テキスト分割手段６を用いて検索文字列からトークンを得る（ステップＳ３４）。また、検索処理手段５において検索用大規模全文索引記憶部８の検索用大規模全文索引を用いて、検索文字列を含む文書データの文書識別子の集合（Ｒｓ）を得る（ステップＳ３５）。検索処理手段５は、登録用小規模全文索引記憶部Ａ（９ａ）の登録用小規模全文索引Ａを用いて、検索文字列を含む文書データの文書識別子の集合（ＲｉＡ）を得、登録用小規模全文索引記憶部Ｂ（９ｂ）の登録用小規模全文索引Ｂを用いて、検索文字列を含む文書データの文書識別子の集合（ＲｉＢ）を得る（ステップＳ３６）。さらに、検索処理手段５は、削除用小規模全文索引記憶部Ａ（１０ａ）の削除用小規模全文索引Ａを用いて、検索文字列を含む文書データの文書識別子の集合（ＲｄＡ）を得、削除用小規模全文索引記憶部Ｂ（１０ａ）の削除用小規模全文索引Ｂを用いて、検索文字列を含む文書データの文書識別子の集合（ＲｄＢ）を得る（ステップＳ３７）。
【００８９】
検索処理手段５は得られた文書識別子の集合（Ｒｓ，ＲｉＡ，ＲｉＢ，ＲｄＡ，ＲｄＢ）に対して下記の集合演算を行い、その結果を検索結果（Ｒ）とし（ステップＳ３８）、出力手段３を通じて利用者に検索文字列を含む文書データの文書識別子の集合を出力する（ステップＳ３９）。
Ｒ＝Ｒｓ＋ＲｉＡ＋ＲｉＢ−ＲｄＡ−ＲｄＢ
ただし、＋を論理和演算子、−を論理差演算子とする。
【００９０】
（マージ処理）
登録用小規模全文索引のマージ処理を実行するには、マージ処理の対象となっている登録用小規模全文索引（ここでは登録用小規模全文索引Ａ）の全てのトークンに対して、（ａ）全文索引からそのトークンの転置リストを取り出す処理（ステップＳ４７）、及び（ｂ）検索用大規模全文索引の対応するトークンの転置リストの末尾に先の転置リストを加える処理を行う（ステップＳ４８）。次に登録用小規模全文索引Ａを空にする（ステップＳ４９）。
【００９１】
削除用小規模全文索引のマージ処理を実行するには、マージ処理の対象となっている削除用小規模全文索引（ここでは削除用小規模全文索引Ａ）の全てのトークンに対して、（ｃ）全文索引からそのトークンの転置リストを取り出す処理（ステップＳ５９）、及び（ｄ）検索用大規模全文索引の対応するトークンの転置リストから（ｃ）で取り出した転置リスト中の出現位置情報を削除する処理（ステップＳ６０）を行う。次に削除用小規模全文索引Ａを空にする（ステップＳ６１）。なお、図８で説明した転置リストのマージ処理例が本実施形態においても適用可能である。
【００９２】
図９乃至図１２を参照して説明した実施形態において、三つ以上の登録用小規模全文索引記憶部及び／又は三つ以上の削除用全文索引記憶部を用いた全文検索装置の形態を、図１３乃至図１６を参照して次の実施形態として例示する。
【００９３】
図１３は、本発明の他の実施形態に係る全文検索装置の機能を説明するためのブロック図である。
本実施形態に係る全文検索装置では、登録用及び削除用の小規模全文索引を三つ以上ずつ（三つずつとして例示する）用意し、他の二つの小規模全文索引が大規模全文索引へのマージ（データ転送）を行っている間は、他の小規模全文索引を使用して登録処理或いは削除処理を実行することにより、処理不能な期間を無くすようにしている。すなわち、本実施形態に係る全文検索装置においては、登録用小規模全文索引を複数備えることでマージ処理が複数の登録用小規模全文索引に対して行われている場合でも他の登録処理が行われている場合でも登録処理を行うことが可能となり、また削除用小規模全文索引を複数備えることでマージ処理が複数の登録用小規模全文索引に対して行われている場合でも他の削除処理が行われている場合でも削除処理を行うことが可能となる。なお、実際には、登録や削除にかかる時間はマージ時間よりも短いので、マージ処理が重なることの方が多い。
【００９４】
図１で説明した登録用小規模全文索引記憶部９が登録用小規模全文索引記憶部Ａ（９ａ）及び登録用小規模全文索引記憶部Ｂ（９ｂ）及び登録用小規模全文索引記憶部Ｃ（９ｃ）の三つの記憶部を有するものとして、図１で説明した削除用小規模全文索引記憶部１０が削除用小規模全文索引記憶部Ａ（１０ａ）及び削除用小規模全文索引記憶部Ｂ（１０ｂ）及び削除用小規模全文索引記憶部Ｃ（１０ｃ）の三つの記憶部を有するものとして本実施形態を説明する。なお、図２及び図３で説明したようなハードウェア構成例を本実施形態に係る全文検索装置にも適用可能である。ただし、これらの記憶部の１又は複数を記憶装置２５，５３ではなく、メモリ上に設けても効果的である。
【００９５】
以下に、上述のごとく構成された本実施形態に係る全文検索装置の動作の一例を詳細に説明する。
図１４乃至図１６は、図１３の全文検索装置における処理例を説明するためのフロー図である。
全文検索装置は、利用者からの処理要求を受け取ると（ステップＳ７１）、まず、その処理が、登録処理であるのか（ステップＳ７２）、削除処理であるのか（ステップＳ７３）、検索処理であるのか（ステップＳ７３でＮＯ）を判定する。全文検索装置は、この判定に基づいて以下の各処理を実行することとなる。
【００９６】
（登録処理）
登録処理を実行するには、まず利用者が文書データを作成し、入力手段１からその文書データを登録する。登録処理手段３において文書データを文書データ記憶部７に保存し、同時にその文書データを示す識別子（文書識別子）を定める（ステップＳ８１）。さらに登録処理手段３において、テキスト分割手段６を用いて文書データから部分文字列（トークン）とそのトークンの出現位置情報を得る（ステップＳ８２）。なお、テキスト分割手段６で使用される分割手法や全文索引については前述した通りである。文書識別子と各トークンの出現位置情報をその時点の登録用小規模全文索引記憶部（例えば登録用小規模全文索引記憶部Ａ（９ａ））に記録する（ステップＳ８３）。
【００９７】
ステップＳ８３における記録の後、適時マージ処理が行われるが、ここではマージ開始条件に基づいて行われるものとして説明する。まず、ステップＳ８３において記録した結果、マージ開始条件を満たすかを判定する（ステップＳ８４）。マージ開始条件を満たさなければ処理を終了する。なお、図１乃至図８の実施形態において説明したマージ処理開始の条件の各形態は、本実施形態においても適用可能である。また、他方の登録用小規模全文索引記憶部（ここでは登録用小規模全文索引記憶部Ｂ（９ｂ））がマージ処理を実行中であるかも判定する（ステップＳ８５）。実行中の場合には、三つ目の登録用小規模全文索引記憶部（ここでは登録用小規模全文索引記憶部Ｃ（９ｃ））が実行中であるかを判定する（ステップＳ８６）。なお、記憶部Ｂ，Ｃが登録処理を実行中であるかも同時に判定しておく。ステップＳ８６において処理が実行中である場合には、その終了を待つ。なお、以降、最も想定されるマージ処理が実行中の場合のみ説明する。
【００９８】
マージ開始条件を満たし、且つ他のいずれかの登録用小規模全文索引記憶部Ｂ（９ｂ）／Ｃ（９ｃ）がマージ処理を実行中ではない場合に、登録用小規模全文索引記憶部Ａ（９ａ）における登録用小規模全文索引Ａに対して、図１１におけるステップＳ４７〜Ｓ４９と同様のマージ処理（ステップＳ８９〜Ｓ９１）を起動し、次の登録処理に対して記録を行うべき記憶部を登録用小規模全文索引記憶部Ａ（９ａ）から他の登録用小規模全文索引記憶部Ｂ（９ｂ）／Ｃ（９ｃ）（マージ処理を実行していない記憶部と同じ記憶部、以下同様の表現を用いる）に切り替える（ステップＳ８７／Ｓ８８）。マージ処理が起動された場合、マージ手段１１は登録処理手段３とは非同期にマージ処理を実行する。
【００９９】
（削除処理）
削除処理を実行するには、まず利用者が入力手段１から削除する文書の文書識別子を入力する。次に、削除処理手段４において文書データ記憶部７から文書識別子に対応する文書データを読み出す（ステップＳ１０１）。さらに削除処理手段４において、テキスト分割手段６を用いて文書データから部分文字列（トークン）とそのトークンの出現位置情報を得る（ステップＳ１０２）。
【０１００】
次に、文書識別子が登録用小規模全文索引に登録されている文書識別子かを判定し（ステップＳ１０３）、登録用小規模全文索引に登録されている文書識別子である場合には、各トークンの出現位置情報を登録用小規模全文索引記憶部９（９ａ及び９ｂ及び９ｃ）から削除する（ステップＳ１０５）。文書識別子が登録用小規模全文索引に登録されていない場合（検索用大規模全文索引に登録されている場合）には、文書識別子と各トークンの出現位置情報をその時点の削除用小規模全文索引記憶部（例えば削除用小規模全文索引記憶部Ａ（１０ａ））に記録する（ステップＳ１０４）。そして、削除処理手段４において文書データ記憶部７から文書識別子に対応する文書データを削除する（ステップＳ１１４）。
【０１０１】
ステップＳ１０４における記録の後、適時マージ処理が行われるが、ここではマージ開始条件に基づいて行われるものとして説明する。まず、ステップＳ１０４において記録した結果、マージ開始条件を満たすかを判定する（ステップＳ１０６）。マージ開始条件を満たさなければ処理を終了する（ステップＳ１１４の処理は必要）。なお、図１乃至図８の実施形態において説明したマージ処理開始の条件の各形態は、本実施形態においても適用可能である。また、他方の削除用小規模全文索引記憶部（ここでは削除用小規模全文索引記憶部Ｂ（１０ｂ））がマージ処理を実行中であるかも判定する（ステップＳ１０７）。実行中の場合には、三つ目の登録用小規模全文索引記憶部（ここでは登録用小規模全文索引記憶部Ｃ（１０ｃ））が実行中であるかを判定する（ステップＳ１０８）。なお、記憶部Ｂ，Ｃが登録処理を実行中であるかも同時に判定しておく。ステップＳ１０８において処理が実行中である場合には、その終了を待つ。なお、以降、最も想定されるマージ処理が実行中の場合のみ説明する。
【０１０２】
マージ開始条件を満たし、且つ他のいずれかの削除用小規模全文索引記憶部Ｂ（１０ｂ）／Ｃ（１０ｃ）がマージ処理を実行中ではない場合に、削除用小規模全文索引記憶部Ａ（１０ａ）における削除用小規模全文索引Ａに対して、図１２におけるステップＳ５９〜Ｓ６１と同様のマージ処理（ステップＳ１１１〜Ｓ１１３）を起動し、次の削除処理に対して記録を行うべき記憶部を削除用小規模全文索引記憶部Ａ（１０ａ）から他の削除用小規模全文索引記憶部Ｂ（１０ｂ）／Ｃ（１０ｃ）に切り替える（ステップＳ１０９／Ｓ１１０）。マージ処理が起動された場合、マージ手段１１は削除処理手段４とは非同期にマージ処理を実行する。
【０１０３】
（検索処理）
本実施形態に係る検索処理は、図１０を参照して説明した検索処理と基本的に同様の処理であり、図１０におけるステップＳ３４〜Ｓ３９が、夫々ステップＳ７４〜Ｓ７９に対応している。ただし、ステップＳ７６において、検索処理手段５は、集合ＲｉＡ，ＲｉＢに加えて、登録用小規模全文索引記憶部Ｃ（９ｃ）の登録用小規模全文索引Ｃを用いて検索文字列を含む文書データの文書識別子の集合（ＲｉＣ）を得る。さらに、ステップＳ７７において、検索処理手段５は、集合ＲｄＡ，ＲｄＢに加えて、削除用小規模全文索引記憶部Ｃ（１０ｃ）の削除用小規模全文索引Ｃを用いて検索文字列を含む文書データの文書識別子の集合（ＲｄＣ）を得る。検索処理手段５は得られた文書識別子の集合（Ｒｓ，ＲｉＡ，ＲｉＢ，ＲｉＣ，ＲｄＡ，ＲｄＢ，ＲｄＣ）に対して下記の集合演算を行い、その結果を検索結果（Ｒ）とする（ステップＳ７８）。
Ｒ＝Ｒｓ＋ＲｉＡ＋ＲｉＢ＋ＲｉＣ−ＲｄＡ−ＲｄＢ−ＲｄＣ
ただし、＋を論理和演算子、−を論理差演算子とする。
【０１０４】
図９乃至図１２の実施形態或いは図１３乃至図１６の実施形態では、複数の登録用小規模全文索引記憶部及び／又は複数の削除用全文索引記憶部を用いた全文検索装置を説明したが、これら全文索引記憶部（検索用大規模全文索引記憶部以外）を、図２及び図３で説明した記憶装置２５又は３５やメモリ上における、個々の記憶領域に対して割り当てるか、或いは、記憶装置２５又は３５やメモリ上に記憶された個々のファイルとして位置付けた場合に適用可能な形態を、次の実施形態として図１７乃至図２０を参照して例示する。
【０１０５】
図１７は、本発明の他の実施形態に係る全文検索装置の機能を説明するためのブロック図である。
本実施形態に係る全文検索装置では、登録用及び削除用の小規模全文索引を一つずつ予め用意し、その小規模全文索引が大規模全文索引へのマージ（データ転送）を行っている間など、登録（／削除）処理に際して登録用（／削除用）の全文索引を記憶する処理が可能な登録用（／削除用）全文索引記憶部が存在しない場合に、他の小規模全文索引を新規作成して、登録処理或いは削除処理を実行することにより、処理不能な期間を無くすようにしている。すなわち、本実施形態に係る全文検索装置においては、登録用小規模全文索引を適時、複数備えることでマージ処理が複数の登録用小規模全文索引に対して行われている場合でも他の登録処理が行われている場合でも登録処理を行うことが可能となり、また削除用小規模全文索引を適時、複数備えることでマージ処理が複数の登録用小規模全文索引に対して行われている場合でも他の削除処理が行われている場合でも削除処理を行うことが可能となる。なお、実際には、登録や削除にかかる時間はマージ時間よりも短いので、マージ処理が重なることの方が多い。
【０１０６】
本実施形態に係る全文検索装置は、登録用小規模全文索引記憶部Ａ（９ａ）とは異なる他の登録用小規模全文索引記憶部を管理する記憶部管理手段１２を有するものとする。また、削除処理に関し、記憶部管理手段１２は削除用小規模全文索引記憶部Ａ（１０ａ）とは異なる他の登録用小規模全文索引記憶部をも管理する。記憶部管理手段１２は、登録処理に際して登録用の全文索引を記憶する処理が可能な登録用全文索引記憶部が存在しない場合に、他の登録用全文索引記憶部を新規作成する手段を有する。さらに、記憶部管理手段１２は、余剰の（次の処理でも使用する予定のない）登録用（／削除用）全文索引記憶部を削除する手段をも有する。
【０１０７】
また、図１で説明した登録用小規模全文索引記憶部９が登録用小規模全文索引記憶部Ａ（９ａ）のみから登録用小規模全文索引記憶部Ｂ（９ｂ），Ｃ（９ｃ），Ｄ（９ｄ），．．．へと適時増数していき（順不同）、それらを適時削除していくものとして、図１で説明した削除用小規模全文索引記憶部１０が削除用小規模全文索引記憶部Ａ（１０ａ）のみから削除用小規模全文索引記憶部Ｂ（１０ｂ），Ｃ（１０ｃ），Ｄ（１０ｄ），．．．へと適時増数していき（順不同）、それらを適時削除していくものとして、本実施形態を説明する。
【０１０８】
適時作成／削除が行われた登録用小規模全文索引記憶部を利用して、登録処理手段３は、登録用全文索引記憶部のうち一つの登録用全文索引記憶部から検索用大規模全文索引記憶部８へデータをマージする処理（或いは他の登録処理）を行っている間は、他の登録用全文索引記憶部を使用して、登録処理を行う。一方、適時作成／削除が行われた削除用小規模全文索引記憶部を利用して、削除処理手段４は、削除用全文索引記憶部のうち一つの削除用全文索引記憶部から検索用大規模全文索引記憶部８へデータをマージする処理（或いは他の削除処理）を行っている間は、他の削除用全文索引記憶部を使用して、削除処理を行う。なお、図２及び図３で説明したようなハードウェア構成例を本実施形態に係る全文検索装置にも適用可能である。ただし、これらの記憶部の１又は複数を記憶装置２５，５３ではなく、メモリ上に設けても効果的である。
【０１０９】
以下に、上述のごとく構成された本実施形態に係る全文検索装置の動作の一例を詳細に説明する。
図１８乃至図２０は、図１７の全文検索装置における処理例を説明するためのフロー図である。
全文検索装置は、利用者からの処理要求を受け取ると（ステップＳ１２１）、まず、その処理が、登録処理であるのか（ステップＳ１２２）、削除処理であるのか（ステップＳ１２３）、検索処理であるのか（ステップＳ１２３でＮＯ）を判定する。全文検索装置は、この判定に基づいて以下の各処理を実行することとなる。
【０１１０】
（登録処理）
登録処理を実行するには、まず利用者が文書データを作成し、入力手段１からその文書データを登録する。登録処理手段３において文書データを文書データ記憶部７に保存し、同時にその文書データを示す識別子（文書識別子）を定める（ステップＳ１３１）。さらに登録処理手段３において、テキスト分割手段６を用いて文書データから部分文字列（トークン）とそのトークンの出現位置情報を得る（ステップＳ１３２）。なお、テキスト分割手段６で使用される分割手法や全文索引については前述した通りである。
【０１１１】
記憶部管理手段１２は、登録処理手段３からの命令により或いは適時、現時点で使用できる登録用小規模全文索引記憶部が存在するかを判定する（ステップＳ１３３）。存在しなければ他の登録用小規模全文索引記憶部（例えば登録用小規模全文索引記憶部Ｃ）を新たに作成する（ステップＳ１３５）。使用できる登録用小規模全文索引記憶部が存在した時点で、文書識別子と各トークンの出現位置情報をその時点の登録用小規模全文索引記憶部（例えば登録用小規模全文索引記憶部Ａ（９ａ）／Ｃ）に記録する（ステップＳ１３４／Ｓ１３６）。
【０１１２】
ステップＳ１３４／Ｓ１３６における記録の後、適時マージ処理が行われるが、ここではマージ開始条件に基づいて行われるものとして説明する。まず、ステップＳ１３４／Ｓ１３６において記録した結果、マージ開始条件を満たすかを判定する（ステップＳ１３７）。マージ開始条件を満たさなければ処理を終了する。なお、図１乃至図８の実施形態において説明したマージ処理開始の条件の各形態は、本実施形態においても適用可能である。また、他方の登録用小規模全文索引記憶部（ここでは登録用小規模全文索引記憶部Ｂ（９ｂ）／Ａ（９ａ））がマージ処理を実行中であるかも判定する（ステップＳ１３８）。なお、記憶部Ｂ／Ａが登録処理を実行中であるかも同時に判定しておく。ステップＳ１３８において処理が実行中である場合には、その終了を待つ。なお、以降、最も想定されるマージ処理が実行中の場合のみ説明する。
【０１１３】
マージ開始条件を満たし、且つ他の登録用小規模全文索引記憶部Ｂ（９ｂ）／Ａ（９ａ）がマージ処理を実行中ではない場合に、登録用小規模全文索引記憶部Ａ（９ａ）／Ｃにおける登録用小規模全文索引Ａ／Ｃに対して、図１１におけるステップＳ４７〜Ｓ４９と同様のマージ処理（ステップＳ１４０〜Ｓ１４２）を起動し、次の登録処理に対して記録を行うべき記憶部を登録用小規模全文索引記憶部Ａ（９ａ）／Ｃから他の登録用小規模全文索引記憶部Ｂ（９ｂ）／Ａ（９ａ）に切り替える（ステップＳ１３９）。マージ処理が起動された場合、マージ手段１１は登録処理手段３とは非同期にマージ処理を実行する。また、記憶部管理手段１２は、余剰の（次の処理でも使用する予定のない）登録用全文索引記憶部をマージ処理時や適時、削除するようにすればよい。
【０１１４】
（削除処理）
削除処理を実行するには、まず利用者が入力手段１から削除する文書の文書識別子を入力する。次に、削除処理手段４において文書データ記憶部７から文書識別子に対応する文書データを読み出す（ステップＳ１５１）。さらに削除処理手段４において、テキスト分割手段６を用いて文書データから部分文字列（トークン）とそのトークンの出現位置情報を得る（ステップＳ１５２）。
【０１１５】
次に、文書識別子が登録用小規模全文索引に登録されている文書識別子かを判定し（ステップＳ１５３）、登録用小規模全文索引に登録されている文書識別子である場合には、各トークンの出現位置情報を存在する全ての登録用小規模全文索引記憶部９（９ａ等）から削除する（ステップＳ１５５）。文書識別子が登録用小規模全文索引に登録されていない場合（検索用大規模全文索引に登録されている場合）には、次に示す削除用小規模全文索引記憶部への記録を行う。
【０１１６】
記憶部管理手段１２は、削除処理手段３からの命令により或いは適時、現時点で使用できる削除用小規模全文索引記憶部が存在するかを判定する（ステップＳ１５４）。存在しなければ他の削除用小規模全文索引記憶部（例えば削除用小規模全文索引記憶部Ｃ）を新たに作成する（ステップＳ１５７）。使用できる削除用小規模全文索引記憶部が存在した時点で、文書識別子と各トークンの出現位置情報をその時点の削除用小規模全文索引記憶部（例えば登録用小規模全文索引記憶部Ａ（１０ａ）／Ｃ）に記録する（ステップＳ１５６／Ｓ１５８）。そして、削除処理手段４において文書データ記憶部７から文書識別子に対応する文書データを削除する（ステップＳ１７５）。
【０１１７】
ステップＳ１５６／Ｓ１５８における記録の後、適時マージ処理が行われるが、ここではマージ開始条件に基づいて行われるものとして説明する。まず、ステップＳ１５６／Ｓ１５８において記録した結果、マージ開始条件を満たすかを判定する（ステップＳ１５９）。マージ開始条件を満たさなければ処理を終了する（ステップＳ１７５の処理は必要）。なお、図１乃至図８の実施形態において説明したマージ処理開始の条件の各形態は、本実施形態においても適用可能である。また、他方の削除用小規模全文索引記憶部（ここでは削除用小規模全文索引記憶部Ｂ（１０ｂ）／Ａ（９ａ））がマージ処理を実行中であるかも判定する（ステップＳ１７０）。なお、記憶部Ｂ／Ａが登録処理を実行中であるかも同時に判定しておく。ステップＳ１７０において処理が実行中である場合には、その終了を待つ。なお、以降、最も想定されるマージ処理が実行中の場合のみ説明する。
【０１１８】
マージ開始条件を満たし、且つ他のいずれかの削除用小規模全文索引記憶部Ｂ（１０ｂ）／Ｃ（１０ｃ）がマージ処理を実行中ではない場合に、削除用小規模全文索引記憶部Ａ（１０ａ）／Ｃにおける削除用小規模全文索引Ａ／Ｃに対して、図１２におけるステップＳ５９〜Ｓ６１と同様のマージ処理（ステップＳ１７２〜Ｓ１７４）を起動し、次の削除処理に対して記録を行うべき記憶部を削除用小規模全文索引記憶部Ａ（１０ａ）／Ｃから他の削除用小規模全文索引記憶部Ｂ（１０ｂ）／Ａ（１０ａ）に切り替える（ステップＳ１７１）。マージ処理が起動された場合、マージ手段１１は削除処理手段４とは非同期にマージ処理を実行する。また、記憶部管理手段１２は、余剰の（次の処理でも使用する予定のない）削除用全文索引記憶部をマージ処理時や適時、削除するようにすればよい。
【０１１９】
（検索処理）
本実施形態に係る検索処理は、図１０を参照して説明した検索処理と基本的に同様の処理であり、図１０におけるステップＳ３４〜Ｓ３９が、夫々ステップＳ１２４〜Ｓ１２９に対応している。ただし、ステップＳ１２６において、検索処理手段５は、集合Ｒｉとして、現時点で存在する全ての登録用小規模全文索引記憶部の登録用小規模全文索引を用いて検索文字列を含む文書データの文書識別子の集合を得る。さらに、ステップＳ１２７において、検索処理手段５は、集合Ｒｄとして、現時点で存在する全ての削除用小規模全文索引記憶部の削除用小規模全文索引を用いて検索文字列を含む文書データの文書識別子の集合を得る。
【０１２０】
以上、本発明の全文検索装置を中心に各実施形態を説明してきたが、全文検索装置における処理手順としても説明したように全文検索のシステムにおける全文検索方法としての形態も採り得る。さらに、本発明は、これら全文検索装置として機能させるためのプログラム、又はその各手段として機能させるためのプログラムとしても、或いは、これら全文検索方法を実行するためのプログラム、又はその処理手順を実行するためのプログラム、さらにはそれらのいずれかのプログラムを記録したコンピュータ読み取り可能な記録媒体としての形態も採用可能である。
【０１２１】
本発明による全文検索の機能を実現するためのプログラムやデータを記憶した記録媒体の実施形態を説明する。記録媒体としては、具体的には、ＣＤ−ＲＯＭ、光磁気ディスク、ＤＶＤ−ＲＯＭ、ＦＤ、フラッシュメモリ、及びその他各種ＲＯＭやＲＡＭ等が想定でき、これら記録媒体に上述した本発明の各実施形態のシステムの機能をコンピュータに実行させ、全文検索の機能を実現するためのプログラムを記録して流通させることにより、当該機能の実現を容易にする。そしてコンピュータ等の情報処理装置に上記のごとくの記録媒体を装着して情報処理装置によりプログラムを読み出すか、若しくは情報処理装置が備えている記憶媒体に当該プログラムを記憶させておき、必要に応じて読み出すことにより、本発明に係わる全文検索機能を実行することができる。
【０１２２】
【発明の効果】
本発明によれば、全文検索装置における登録処理や削除処理を小規模な全文索引記憶部に対して行うので、その処理時間は短く抑えることが可能となり、利用者へのレスポンスタイムを短くすることが可能となる。
【０１２３】
また、本発明によれば、登録用小規模全文索引を複数備えることでマージ処理を実行中でも登録処理を行うことが可能となり、また削除用小規模全文索引を複数備えることでマージ処理を実行中でも削除処理を行うことが可能となる。
【図面の簡単な説明】
【図１】  本発明の一実施形態に係る全文検索装置の機能を説明するためのブロック図である。
【図２】  図１における全文検索装置をスタンドアロンで構成した場合のハードウェア構成例を示す図である。
【図３】  図１における全文検索装置をサーバ／クライアントで構成した場合のハードウェア構成例を示す図である。
【図４】  図１の全文検索装置における処理例を説明するためのフロー図である。
【図５】  図１の全文検索装置における処理例を説明するためのフロー図である。
【図６】  図１の全文検索装置における処理例を説明するためのフロー図である。
【図７】  図１の全文検索装置における処理を説明するための図で、全文索引の一例を示す図である。
【図８】  図７における全文索引のトークン「全文」の転置リストを例にマージ処理の概要を説明するための図である。
【図９】  本発明の他の実施形態に係る全文検索装置の機能を説明するためのブロック図である。
【図１０】  図９の全文検索装置における処理例を説明するためのフロー図である。
【図１１】  図９の全文検索装置における処理例を説明するためのフロー図である。
【図１２】  図９の全文検索装置における処理例を説明するためのフロー図である。
【図１３】  本発明の他の実施形態に係る全文検索装置の機能を説明するためのブロック図である。
【図１４】  図１３の全文検索装置における処理例を説明するためのフロー図である。
【図１５】  図１３の全文検索装置における処理例を説明するためのフロー図である。
【図１６】  図１３の全文検索装置における処理例を説明するためのフロー図である。
【図１７】  本発明の他の実施形態に係る全文検索装置の機能を説明するためのブロック図である。
【図１８】  図１７の全文検索装置における処理例を説明するためのフロー図である。
【図１９】  図１７の全文検索装置における処理例を説明するためのフロー図である。
【図２０】  図１７の全文検索装置における処理例を説明するためのフロー図である。
【符号の説明】
１…入力手段、２…出力手段、３…登録処理手段、４…削除処理手段、５…検索処理手段、６…テキスト分割手段、７…文書データ記憶部、８…検索用大規模全文索引記憶部、９…登録用小規模全文索引記憶部、９ａ…登録用小規模全文索引記憶部Ａ、９ｂ…登録用小規模全文索引記憶部Ｂ、９ｃ…登録用小規模全文索引記憶部Ｃ、１０…削除用小規模全文索引記憶部、１０ａ…削除用小規模全文索引記憶部Ａ、１０ｂ…削除用小規模全文索引記憶部Ｂ、１０ｃ…削除用小規模全文索引記憶部Ｃ、１１…マージ手段、１２…記憶部管理手段、２１，３１…入力装置、２２，３２…表示装置、２３，３３…入出力制御装置、２４，３４，５２…主制御装置（ＣＰＵ・メモリ）、２５，５３…記憶装置、３０…クライアント、３５，５１…ネットワーク制御装置、４０…ネットワーク、５０…サーバ。
【図１】
0004219125.tif 000002
【図２】
0004219125.tif 000003
【図３】
0004219125.tif 000004
【図４】
0004219125.tif 000005
【図５】
0004219125.tif 000006
【図６】
0004219125.tif 000007
【図７】
0004219125.tif 000008
【図８】
0004219125.tif 000009
【図９】
0004219125.tif 000010
【図１０】
0004219125.tif 000011
【図１１】
0004219125.tif 000012
【図１２】
0004219125.tif 000013
【図１３】
0004219125.tif 000014
【図１４】
0004219125.tif 000015
【図１５】
0004219125.tif 000016
【図１６】
0004219125.tif 000017
【図１７】
0004219125.tif 000018
【図１８】
0004219125.tif 000019
【図１９】
0004219125.tif 000020
【図２０】
0004219125.tif 000021