(57)【要約】    【課題】      文書データベースの更新処理における記憶容量の消費を抑え、効率的な文書ＤＢの更新・検索を可能とする文書データベース更新処理装置、文書データベース検索装置、文書データベース索引作成方法及び文書データベース検索方法を提供すること。    【解決手段】  文書ＤＢ更新処理装置１０２は、世代管理方式の文書ＤＢにおいて、現世代から次世代への索引更新の際に、新版で削除される単語と、その出現位置リストの組のリストを記録した負の索引と、変更後の索引で特に追加、変更のあった文字列の出現位置と位置シフト値を記録した正の索引の組を有する更新情報を作成し、この更新情報と、索引の組で次世代の文書ＤＢを表現する。また、文書ＤＢ更新処理装置１０２は、複数世代の更新情報をマージする更新情報マージ処理機能を有する。  【選択図】      図２
2006185368.tif 000002
【特許請求の範囲】
【請求項１】
世代管理された文書データベースを更新する文書データベース更新処理装置であって、
一意に識別されるＩＤを持つ複数のレコード単位で構成される初期世代文書から、レコード毎に文字列を切出し、その切出された文字列と、その文字列の出現文字位置とを対で示す索引と、前記初期世代文書を文書データベースに記録する文書データベース記録部と、
更新用文書を入力する文書入力部と、
前記初期世代文書と前記更新用文書間における変更箇所の文字列の部分を判定する更新文書判定部と、
前記判定により該当文字列部分について、切出された文字列とその出現位置及び文字列の変更において発生する文字列長の差分値の組を索引要素として正の索引を作成する正の索引作成部と、
前記判定により削除されるべき初期世代の索引要素を負の索引として作成する負の索引作成部と、
前記判定により削除されたレコードについては、その文書ＩＤを削除レコード表として作成する削除レコード表作成部と、から成り、前記作成された正の索引、負の索引及び削除レコード表を新たな世代の更新情報として更新・登録する文書データベース更新処理部と、を備えたことを特徴とする文書データベース更新処理装置。
【請求項２】
世代管理された文書データベースを更新する文書データベース更新処理装置であって、
一意に識別されるＩＤを持つ複数のレコード単位で構成される初期世代から世代Ｎまでの文書と、負の索引、正の索引及び削除レコード表からなる索引情報を、それぞれ文書データベースに記録する文書データベース記録部と、
世代Ｎ＋１の更新用文書を入力する文書入力部と、
前記初期世代から世代Ｎまでの文書と、負の索引、正の索引及び削除レコード表からなる索引情報と、前記世代Ｎ＋１の更新用文書から変更箇所の文字列の部分を判定する更新文書判定部と、
前記判定により該当文字列部分について、切出された文字列とその出現位置及び文字列の変更において発生する文字列長の差分値の組を索引要素として正の索引を作成する正の索引作成部と、
前記判定により削除されるべき初期世代の索引要素を負の索引として作成する負の索引作成部と、
前記判定により削除されたレコードについては、その文書ＩＤを削除レコード表として作成する削除レコード表作成部と、から成り、前記判定により作成された正の索引、負の索引及び削除レコード表を世代Ｎ＋１の更新情報として更新・登録する文書データベース更新処理部と、を備えたことを特徴とする文書データベース更新処理装置。
【請求項３】
前記初期世代から世代Ｎまでの文書と、前記負の索引、前記正の索引及び前記更新用文書に基づく世代ｉ＋１（０＜ｉ＜Ｎ）の更新処理においては、世代ｉ〜世代Ｎの負の索引、正の索引及び削除レコード表に基づいて削除する索引要素と、追加・変更された索引要素と、削除されたレコードとを解釈する複数更新情報解釈部を備えることにより、前記世代Ｎ＋１の更新情報を作成することを特徴とする請求項２記載の文書データベース更新処理装置。
【請求項４】
前記更新文書判定部は、更新前世代の索引から、更新後世代の索引への更新処理時に、更新対象レコードの変更される文字列の数が任意の閾値より多いか否かを判定し、多い場合には、そのレコードを変更レコードとみなして索引を作成し、当該レコード番号を前記削除レコード表に記録することを特徴とする請求項１または２記載の文書データベース更新処理装置。
【請求項５】
前記複数世代にわたる更新により蓄積される複数世代の更新情報を一つの更新情報に纏める処理を行う更新情報マージ処理部を、更に備えること特徴とする請求項２記載の文書データベース更新処理装置。
【請求項６】
前記更新情報マージ処理部により、必要のなくなった更新情報は削除することを特徴とする請求項５記載の文書データベース更新処理装置。
【請求項７】
前記更新文書判定部は、前記更新用文書から比較対照とする文書レコードを指定し、この文書レコードと、前記初期文書の該当文書レコードとの間の差分文字列リストを求め、当該差分文字列リストの要素数が前記閾値より多いか否かを判定することを特徴とする請求項４記載の文書データベース更新処理装置。
【請求項８】
検索対象とする文字列を入力する検索文字列入力部と、
複数世代の正の索引、負の索引及び削除レコード表からなる更新情報と、その各世代の文書情報を記憶する文書データベース保持部と、
前記入力された文字列を解析して文字列に分割し、分割した各文字列について、前記文書データベース保持部から複数世代に渡る更新情報と、初期世代の索引及び文書とを用いて検索する文書データベース検索部と、
前記文書データベース検索部により得られたレコード集合を出力する検索結果出力部と、を具備することを特徴とする文書データベース検索装置。
【請求項９】
世代Ｎ＋１の前記正の索引と、世代０と世代１から世代Ｎ＋１までの更新情報を用いて、世代ｉ（ｉ＝１〜Ｎ＋１）の検索時に、世代Ｎ＋１から世代ｉ＋１までの負の索引の要素と、削除レコード表の要素に基づいて削除された索引要素と、削除されたレコードを累積的に解釈する負索引・削除レコード表解釈部を備え、
前記文書データベース検索部は、世代Ｎ＋１の索引検索において、前記分割された文字列毎に、前記世代Ｎ＋１の正の索引を検索して該当する文字列があれば、当該文字列を検索候補とし、世代Ｎの索引検索において、前記分割された文字列毎に該当する文字列があれば、当該文字列を前記負索引・削除レコード表解釈部に出力し、
前記負索引・削除レコード表解釈部は、前記文書データベース検索部から入力された文字列に該当する文字列が前記世代Ｎ＋１の負の索引にあれば、当該文字列を検索対象とせず、前記世代Ｎ＋１の削除レコード表に登録されたレコード番号の文書データを解釈して、前記入力された文字列の要素があれば、その要素を検索対象としないことを特徴とする請求項８記載の文書データベース検索装置。
【請求項１０】
前記世代Ｎ＋１の正の索引から前記世代ｉ＋１の正の索引までの各要素の位置シフト値を累算する位置シフト累算部を、更に備え、
前記文書データベース検索部は、前記世代Ｎ＋１の正の索引から検索された文字列の出現位置に、前記位置シフト累算部により累算された位置シフト値を加算して、当該文字列より前に検索された文字列の出現位置と連接するか否かを判定し、連接していれば、前記検索された文字列を検索対象とすることを特徴とする請求項９記載の文書データベース検索装置。
【請求項１１】
前記文書データベース検索部は、前記分割した各文字列に対して、前記世代０〜Ｎ＋１の各世代の正の索引から該当文字列を検索する処理を繰り返し実行し、検索した該当文字列毎に前記連接の判定を行って、前記分割した全ての文字列に対して、前記世代Ｎ＋１の正の索引から前記世代ｉ＋１の正の索引までの全要素から検索対象を検索することを特徴とする請求項９または１０記載の文書データベース検索装置。
【請求項１２】
世代管理された文書データベースの索引を作成する文書データベース索引作成方法であって、
一意に識別されるＩＤを持つ複数のレコード単位で構成される初期世代文書から、レコード毎に文字列を切出し、その切出された文字列と、その文字列の出現文字位置とを対で示す索引と、前記初期世代文書を文書データベースに記録する文書データベース記録ステップと、
更新用文書を入力する文書入力ステップと、
前記初期世代文書と前記更新用文書間における変更箇所の文字列の部分を判定する更新文書判定ステップと、
前記判定により該当文字列部分について、切出された文字列とその出現位置及び文字列の変更において発生する文字列長の差分値の組を索引要素として正の索引を作成する正の索引作成ステップと、
前記判定により削除されるべき初期世代の索引要素を負の索引として作成する負の索引作成ステップと、
前記判定により削除されたレコードについては、その文書ＩＤを削除レコード表として作成する削除レコード表作成ステップと、
前記作成された正の索引、負の索引及び削除レコード表を新たな世代の更新情報として更新・登録する更新・登録ステップと、
を具備することを特徴とする文書データベース索引作成方法。
【請求項１３】
世代管理された文書データベースの索引を作成する文書データベース索引作成方法であって、
一意に識別されるＩＤを持つ複数のレコード単位で構成される初期世代から世代Ｎまでの文書と、負の索引、正の索引及び削除レコード表からなる索引情報を、それぞれ文書データベースに記録する文書データベース記録ステップと、
世代Ｎ＋１の更新用文書を入力する文書入力ステップと、
前記初期世代から世代Ｎまでの文書と、負の索引、正の索引及び削除レコード表からなる索引情報と、前記世代Ｎ＋１の更新用文書から変更箇所の文字列の部分を判定する更新文書判定ステップと、
前記判定により該当文字列部分について、切出された文字列とその出現位置及び文字列の変更において発生する文字列長の差分値の組を索引要素として正の索引を作成する正の索引作成ステップと、
前記判定により削除されるべき初期世代の索引要素を負の索引として作成する負の索引作成ステップと、
前記判定により削除されたレコードについては、その文書ＩＤを削除レコード表として作成する削除レコード表作成ステップと、
前記判定により作成された正の索引、負の索引及び削除レコード表を世代Ｎ＋１の更新情報として更新・登録する更新・登録ステップと、
を具備することを特徴とする文書データベース索引作成方法。
【請求項１４】
検索対象とする文字列を入力する検索文字列入力ステップと、
複数世代の正の索引、負の索引及び削除レコード表からなる更新情報と、その各世代の文書情報を記憶する文書データベース保持ステップと、
前記入力された文字列を解析して文字列に分割し、分割した各文字列について、前記文書データベースから複数世代に渡る更新情報と、初期世代の索引及び文書とを用いて検索する文書データベース検索ステップと、
前記文書データベース検索ステップにより得られたレコード集合を出力する検索結果出力ステップと、
を具備することを特徴とする文書データベース検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、文書データベース更新装置、文書データベース検索装置、文書データベース索引作成方法及び文書データベース検索方法に関し、特に、文書データベースの更新処理及び検索処理を行う文書データベース更新装置、文書データベース検索装置、文書データベース索引作成方法及び文書データベース検索方法に関する。
【背景技術】
【０００２】
近年、電子計算機やネットワークの高性能化、低価格化、インターネット通信環境の整備、普及に伴い、情報技術の利用が盛んになってきている。その中で、情報蓄積、情報検索の基盤として、データベース、データベース管理システムが盛んに利用されている。
【０００３】
このようなデータベース管理システムの中には、データベースの「世代」という概念を導入し、世代管理を行うものがある。世代管理型のデータベース管理システムでは、更新処理において、補助記憶装置等に記憶された更新元のデータベースの実体を変更せずに、次の世代のデータベースを作成する。
【０００４】
このような従来の世代管理型のデータベース管理システムとしては、文書データベースの世代を管理するものがあり、例えば、非特許文献１に記載されるような文書データベース管理システムが存在する。この文書データベース管理システムでは、文書データベース（以下、文書ＤＢという）の更新内容を考慮して、投入データ期間で複数のＤＢに分割して、差分更新を効率化している。
【０００５】
以下、この文書ＤＢ管理システムについて図２１を参照して説明する。図２１に示す文書ＤＢ管理システム２１００おいて、２１０１は投入された更新文書と、世代Ｎ−１の索引及び文書を用いて世代Ｎを作成する文書ＤＢ更新処理装置、２１０２は文書を入力する文書入力装置、２１０３は複数世代に渡る文書ＤＢの実体を永続的に補助記憶装置２１１０に記録または、検索処理の高速化のために、最新の数世代の更新情報を主記憶装置２１０９に記録する文書ＤＢ保持装置、２１０４は文書から初期世代の索引を作成する文書ＤＢ作成装置、２１０５はキーボード等の入力インタフェースを備え、文書ＤＢを検索するための検索キーワード及び検索対象とする世代を入力する検索キーワード入力部、２１０６は入力された検索キーワードを文書ＤＢより検索する文書ＤＢ検索部、２１０７は検索結果をディスプレイなどの表示装置に表示する検索結果出力部、２１０８は検索キーワード入力部２１０５、文書ＤＢ検索部２１０６及び検索結果出力部２１０７を含む文書ＤＢ検索装置である。
【０００６】
以上の構成の文書ＤＢ管理システム２１００において、その動作と、簡単な更新及び検索の具体例について図３を用いて説明する。
【０００７】
図３（ａ）〜（ｃ）は、文書ＤＢとして、個人の日記等の雑感を格納した文書ＤＢの例である。
【０００８】
図３（ａ）の更新前の文書ＤＢの例３０１に示すように、文書ＤＢは、タグ（＜ｄｏｃ  ＩＤ＝Ｘ＞と表記（Ｘ：ＩＤ番号））で区切られた複数の文書レコードとして表現され、各文書レコードは、「文書ＩＤ」と「本文」の２項目を、ＩＤ番号順に並べ、特に文書ＩＤについては、文書ＩＤがＸの場合、タグの要素として、＜ｄｏｃ  ＩＤ＝Ｘ＞のように記録して表現するものとする。なお、この文書ＤＢは、高速な検索、更新処理を行うために、図４の更新前の文書ＤＢの索引例４０１に示すように、文書ＤＢから、各文書レコードに出現する単語と、その単語の出現する文書ＩＤと、出現文字位置が記録されている。３０１の例では、文書ＩＤが１、２、３の３つの文書レコードがあり、更新の際には、文書ＩＤで各雑感文書を識別し、追加・変更・削除のそれぞれの更新処理を行う。図３（ｂ）、（ｃ）は、それぞれ文書ＤＢ３０１に対する更新用文書の例３０２及び更新後の文書ＤＢの例３０３を示している。
【０００９】
これらの例では、文書ＩＤ１、ＩＤ３の既存の文書レコードに対する変更データと、文書ＩＤ２の既存の雑感文書の削除レコード（本文が空の雑感文書は文書ＩＤで指定した既存の文書の削除を指示するものとする）と、文書ＩＤ４の新たに追加された文書レコードが含まれており、３０２の更新用文書を入力として差分更新処理を行うと、３０３のような次の世代の文書ＤＢ（更新後の文書ＤＢ）が作成される。
【００１０】
文書ＤＢ更新処理装置２１０１と、文書ＤＢ作成装置２１０４では、図３（ｂ）に示すような更新用文書３０２を入力として受け取ると、新たな更新用文書の内容を検索し、更新するためのデータ構造である差分索引を、図２２に示す更新後の文書ＤＢの索引例２２０１のように作成し、文書ＤＢ保持装置２１０３に格納する。
【００１１】
この文書ＤＢ管理システム２１００では、このように動作する事で、文書ＤＢの更新内容を考慮して、投入データ期間で複数の文書ＤＢに分割して、世代管理型の文書ＤＢの差分更新を効率化している。
【００１２】
なお、他に従来データベースと重ね合わせて検索を可能とする世代管理型のデータ更新装置としては、例えば、特許文献１に記載されている概念辞書管理装置が存在する。この装置では、複数の利用者が共用する基本概念辞書をその内容を変更することなく、分野別または利用者別に調整された概念辞書を作成して、これらを重ね合わせて検索できるようにする事で、基本概念辞書を破壊することなく拡張、縮小することを可能にしている。
【特許文献１】特開平６−０７５９８９号公報
【非特許文献１】Narayanan Shivakumar, Hector Garcia-Molina: Wave-Indices: Indexing Evolving Databases. SIGMOD Conference 1997: 381-392
【発明の開示】
【発明が解決しようとする課題】
【００１３】
しかし、上記従来の非特許文献１の文書ＤＢ管理システムでは、文書ＤＢ中のある文書ＩＤの一単語だけを変更するような小規模な更新でも、変更の発生した文書ＩＤの全ての文字列の切出しを行い、切り出された文字列全てについて索引を作成するため、更新情報を格納する補助記憶領域の容量を多く消費し、かつ、更新速度が更新情報量に比例してかかるため、更新処理の効率が低下するという問題がある。
【００１４】
また、上記従来の特許文献１の概念辞書管理装置では、変更部分の単語のみに関する少量の差分概念辞書と元の概念辞書とを組み合わせることで、効率的な更新処理は行えるが、あくまでも概念辞書であり、文書を高速に検索するための索引は持たないため、文書ＤＢの世代更新処理を実現できるものではない。
【００１５】
本発明はかかる点に鑑みてなされたものであり、文書データベースの更新処理における記憶容量の消費を抑え、効率的な文書データベースの更新・検索を可能とする文書データベース更新処理装置、文書データベース検索装置、文書データベース索引作成方法及び文書データベース検索方法を提供することを目的としている。
【課題を解決するための手段】
【００１６】
本発明の第１の態様にかかる文書データベース更新処理装置は、世代管理された文書データベースを更新する文書データベース更新処理装置であって、一意に識別されるＩＤを持つ複数のレコード単位で構成される初期世代文書から、レコード毎に文字列を切出し、その切出された文字列と、その文字列の出現文字位置とを対で示す索引と、前記初期世代文書を文書データベースに記録する文書データベース記録部と、更新用文書を入力する文書入力部と、前記初期世代文書と前記更新用文書間における変更箇所の文字列の部分を判定する更新文書判定部と、前記判定により該当文字列部分について、切出された文字列とその出現位置及び文字列の変更において発生する文字列長の差分値の組を索引要素として正の索引を作成する正の索引作成部と、前記判定により削除されるべき初期世代の索引要素を負の索引として作成する負の索引作成部と、前記判定により削除されたレコードについては、その文書ＩＤを削除レコード表として作成する削除レコード表作成部と、から成り、前記作成された正の索引、負の索引及び削除レコード表を新たな世代の更新情報として更新・登録する文書データベース更新処理部と、を備えた構成を採る。
【００１７】
この構成によれば、初期世代から次世代への索引更新の際に、新版で削除されるべき初期世代の索引要素を記録した負の索引と、追加、変更のあった文字列の出現位置と文字列長の差分値の組を記録した正の索引と、削除されたレコードの文書ＩＤを記録した削除レコード表の組を有する更新情報を作成し、この更新情報と、索引の組で次世代の文書データベースを表現することにより、変更した文字列部分のみに比例した量の更新情報となるため、更新情報の記憶領域を削減でき、同時に、更新情報量の削減に比例して、更新情報作成処理時間も短縮することができる。
【００１８】
本発明の第２の態様にかかる文書データベース更新処理装置は、世代管理された文書データベースを更新する文書データベース更新処理装置であって、一意に識別されるＩＤを持つ複数のレコード単位で構成される初期世代から世代Ｎまでの文書と、負の索引、正の索引及び削除レコード表からなる索引情報を、それぞれ文書データベースに記録する文書データベース記録部と、世代Ｎ＋１の更新用文書を入力する文書入力部と、前記初期世代から世代Ｎまでの文書と、負の索引、正の索引及び削除レコード表からなる索引情報と、前記世代Ｎ＋１の更新用文書から変更箇所の文字列の部分を判定する更新文書判定部と、前記判定により該当文字列部分について、切出された文字列とその出現位置及び文字列の変更において発生する文字列長の差分値の組を索引要素として正の索引を作成する正の索引作成部と、前記判定により削除されるべき初期世代の索引要素を負の索引として作成する負の索引作成部と、前記判定により削除されたレコードについては、その文書ＩＤを削除レコード表として作成する削除レコード表作成部と、から成り、前記判定により作成された正の索引、負の索引及び削除レコード表を世代Ｎ＋１の更新情報として更新・登録する文書データベース更新処理部と、を備えた構成を採る。
【００１９】
この構成によれば、初期世代から世代Ｎへの索引更新の際に、新版で削除されるべき初期世代の索引要素を記録した負の索引と、追加、変更のあった文字列の出現位置と文字列長の差分値の組を記録した正の索引と、削除されたレコードの文書ＩＤを記録した削除レコード表の組を有する世代Ｎ＋１の更新情報を作成し、この更新情報と、索引の組で世代Ｎ＋１の文書データベースを表現することにより、世代毎に変更した文字列部分のみに比例した量の更新情報となるため、各世代の更新情報の記憶領域を削減でき、同時に、更新情報量の削減に比例して、更新情報作成処理時間も短縮することができる。
【００２０】
本発明の第３の態様は、第２の態様にかかる文書データベース更新処理装置において、前記初期世代から世代Ｎまでの文書と、前記負の索引、前記正の索引及び前記更新用文書に基づく世代ｉ＋１（０＜ｉ＜Ｎ）の更新処理においては、世代ｉ〜世代Ｎの負の索引、正の索引及び削除レコード表に基づいて削除する索引要素と、追加・変更された索引要素と、削除されたレコードとを解釈する複数更新情報解釈部を備えることにより、前記世代Ｎ＋１の更新情報を作成する構成を採る。
【００２１】
この構成によれば、初期世代から世代Ｎへの索引更新の際に、世代ｉ〜世代Ｎの負の索引、正の索引及び削除レコード表の要素を解釈して世代Ｎ＋１の更新情報を作成することができ、世代Ｎまでに追加・変更された文字列部分のみの更新情報作成処理となるため、更新情報作成処理の効率化を図ることができる。
【００２２】
本発明の第４の態様は、第１または第２の態様にかかる文書データベース更新処理装置において、前記更新文書判定部は、更新前世代の索引から、更新後世代の索引への更新処理時に、更新対象レコードの変更される文字列の数が任意の閾値より多いか否かを判定し、多い場合には、そのレコードを変更レコードとみなして索引を作成し、当該レコード番号を前記削除レコード表に記録する構成を採る。
【００２３】
この構成によれば、変更される文字列数が予め決定した閾値を超える場合は、削除対象レコードとして削除レコード表に記録することにより、常に更新情報を適用して更新処理を行う場合よりも処理効率の向上を図ることができる。
【００２４】
本発明の第５の態様は、第２の態様にかかる文書データベース更新処理装置において、前記複数世代にわたる更新により蓄積される複数世代の更新情報を一つの更新情報に纏める処理を行う更新情報マージ処理部を、更に備える構成を採る。
【００２５】
この構成によれば、複数世代にわたる更新情報を一つの更新情報に纏めることにより、以降の世代更新処理、検索処理の際の処理速度を向上させることができる。
【００２６】
本発明の第６の態様は、第５の態様にかかる文書データベース更新処理装置において、前記更新情報マージ処理部により、必要のなくなった更新情報は削除する構成を採る。
【００２７】
この構成によれば、必要のなくなった更新情報は削除することにより、文書データベースを格納する記憶領域を効率よく使用することができる。
【００２８】
本発明の第７の態様は、第４の態様にかかる文書データベース更新処理装置において、前記更新文書判定部は、前記更新用文書から比較対照とする文書レコードを指定し、この文書レコードと、前記初期文書の該当文書レコードとの間の差分文字列リストを求め、当該差分文字列リストの要素数が前記閾値より多いか否かを判定する構成を採る。
【００２９】
この構成によれば、差分文字列リストの要素数と予め決定した閾値との大小を判定することにより、削除すべきレコードの判定処理を効率よく実行することができる。
【００３０】
本発明の第８の態様にかかる文書データベース検索装置は、検索対象とする文字列を入力する検索文字列入力部と、複数世代の正の索引、負の索引及び削除レコード表からなる更新情報と、その各世代の文書情報を記憶する文書データベース保持部と、前記入力された文字列を解析して文字列に分割し、分割した各文字列について、前記文書データベース保持部から複数世代に渡る更新情報と、初期世代の索引及び文書とを用いて検索する文書データベース検索部と、前記文書データベース検索部により得られたレコード集合を出力する検索結果出力部と、を具備する構成を採る。
【００３１】
この構成によれば、検索対象文字列を正の索引、負の索引及び削除レコード表から成る更新情報から検索するため、索引に記録された各要素から検索対象を検索できるため、世代管理型文書データベースに対する検索処理効率の向上を図ることができる。
【００３２】
本発明の第９の態様は、第８の態様にかかる文書データベース検索装置において、世代Ｎ＋１の前記正の索引と、世代０と世代１から世代Ｎ＋１までの更新情報を用いて、世代ｉ（ｉ＝１〜Ｎ＋１）の検索時に、世代Ｎ＋１から世代ｉ＋１までの負の索引の要素と、削除レコード表の要素に基づいて削除された索引要素と、削除されたレコードを累積的に解釈する負索引・削除レコード表解釈部を備え、前記文書データベース検索部は、世代Ｎ＋１の索引検索において、前記分割された文字列毎に、前記世代Ｎ＋１の正の索引を検索して該当する文字列があれば、当該文字列を検索候補とし、世代Ｎの索引検索において、前記分割された文字列毎に該当する文字列があれば、当該文字列を前記負索引・削除レコード表解釈部に出力し、前記負索引・削除レコード表解釈部は、前記文書データベース検索部から入力された文字列に該当する文字列が前記世代Ｎ＋１の負の索引にあれば、当該文字列を検索対象とせず、前記世代Ｎ＋１の削除レコード表に登録されたレコード番号の文書データを解釈して、前記入力された文字列の要素があれば、その要素を検索対象としない構成を採る。
【００３３】
この構成によれば、複数世代に渡る更新処理により作成された文書データベースから検索対象を効率よく検索することができる。
【００３４】
本発明の第１０の態様は、第９の態様にかかる文書データベース検索装置において、前記世代Ｎ＋１の正の索引から前記世代ｉ＋１の正の索引までの各要素の位置シフト値を累算する位置シフト累算部を、更に備え、前記文書データベース検索部は、前記世代Ｎ＋１の正の索引から検索された文字列の出現位置に、前記位置シフト累算部により累算された位置シフト値を加算して、当該文字列より前に検索された文字列の出現位置と連接するか否かを判定し、連接していれば、前記検索された文字列を検索対象とする構成を採る。
【００３５】
この構成によれば、複数世代に渡る更新処理により作成された文書データベースから検索対象の位置シフト後の出現位置と、他の検索対象の出現位置との連接関係も考慮して検索することができ、検索対象を正確に検索することができる。
【００３６】
本発明の第１１の態様は、第９または第１０の態様にかかる文書データベース検索装置において、前記文書データベース検索部は、前記分割した各文字列に対して、前記世代０〜Ｎ＋１の各世代の正の索引から該当文字列を検索する処理を繰り返し実行し、検索した該当文字列毎に前記連接の判定を行って、前記分割した全ての文字列に対して、前記世代Ｎ＋１の正の索引から前記世代ｉ＋１の正の索引までの全要素から検索対象を検索する構成を採る。
【００３７】
この構成によれば、複数世代に渡る更新処理により作成された文書データベースから検索対象の文字列を検索する際に、索引の各要素の出現位置集合等に対する加減算の演算だけで処理できるため、検索処理速度を低下させずに、正確かつ効率的な検索処理を実現することができる。
【００３８】
本発明の第１２の態様にかかる文書データベース索引作成方法は、世代管理された文書データベースの索引を作成する文書データベース索引作成方法であって、一意に識別されるＩＤを持つ複数のレコード単位で構成される初期世代文書から、レコード毎に文字列を切出し、その切出された文字列と、その文字列の出現文字位置とを対で示す索引と、前記初期世代文書を文書データベースに記録する文書データベース記録ステップと、更新用文書を入力する文書入力ステップと、前記初期世代文書と前記更新用文書間における変更箇所の文字列の部分を判定する更新文書判定ステップと、前記判定により該当文字列部分について、切出された文字列とその出現位置及び文字列の変更において発生する文字列長の差分値の組を索引要素として正の索引を作成する正の索引作成ステップと、前記判定により削除されるべき初期世代の索引要素を負の索引として作成する負の索引作成ステップと、前記判定により削除されたレコードについては、その文書ＩＤを削除レコード表として作成する削除レコード表作成ステップと、前記作成された正の索引、負の索引及び削除レコード表を新たな世代の更新情報として更新・登録する更新・登録ステップと、を具備するようにした。
【００３９】
この方法によれば、初期世代から次世代への索引更新の際に、新版で削除されるべき初期世代の索引要素を記録した負の索引と、追加、変更のあった文字列の出現位置と文字列長の差分値の組を記録した正の索引と、削除されたレコードの文書ＩＤを記録した削除レコード表の組を有する更新情報を作成し、この更新情報と、索引の組で次世代の文書データベースを表現することにより、変更した文字列部分のみに比例した量の更新情報となるため、更新情報の記憶領域を削減でき、同時に、更新情報量の削減に比例して、更新情報作成処理時間も短縮することができる。
【００４０】
本発明の第１３の態様にかかる文書データベース索引作成方法は、世代管理された文書データベースの索引を作成する文書データベース索引作成方法であって、一意に識別されるＩＤを持つ複数のレコード単位で構成される初期世代から世代Ｎまでの文書と、負の索引、正の索引及び削除レコード表からなる索引情報を、それぞれ文書データベースに記録する文書データベース記録ステップと、世代Ｎ＋１の更新用文書を入力する文書入力ステップと、前記初期世代から世代Ｎまでの文書と、負の索引、正の索引及び削除レコード表からなる索引情報と、前記世代Ｎ＋１の更新用文書から変更箇所の文字列の部分を判定する更新文書判定ステップと、前記判定により該当文字列部分について、切出された文字列とその出現位置及び文字列の変更において発生する文字列長の差分値の組を索引要素として正の索引を作成する正の索引作成ステップと、前記判定により削除されるべき初期世代の索引要素を負の索引として作成する負の索引作成ステップと、前記判定により削除されたレコードについては、その文書ＩＤを削除レコード表として作成する削除レコード表作成ステップと、前記判定により作成された正の索引、負の索引及び削除レコード表を世代Ｎ＋１の更新情報として更新・登録する更新・登録ステップと、を具備するようにした。
【００４１】
この方法によれば、初期世代から世代Ｎへの索引更新の際に、新版で削除されるべき初期世代の索引要素を記録した負の索引と、追加、変更のあった文字列の出現位置と文字列長の差分値の組を記録した正の索引と、削除されたレコードの文書ＩＤを記録した削除レコード表の組を有する世代Ｎ＋１の更新情報を作成し、この更新情報と、索引の組で世代Ｎ＋１の文書データベースを表現することにより、世代毎に変更した文字列部分のみに比例した量の更新情報となるため、各世代の更新情報の記憶領域を削減でき、同時に、更新情報量の削減に比例して、更新情報作成処理時間も短縮することができる。
【００４２】
本発明の第１４の態様にかかる文書データベース検索方法は、検索対象とする文字列を入力する検索文字列入力ステップと、複数世代の正の索引、負の索引及び削除レコード表からなる更新情報と、その各世代の文書情報を記憶する文書データベース保持ステップと、前記入力された文字列を解析して文字列に分割し、分割した各文字列について、前記文書データベースから複数世代に渡る更新情報と、初期世代の索引及び文書とを用いて検索する文書データベース検索ステップと、前記文書データベース検索ステップにより得られたレコード集合を出力する検索結果出力ステップと、を具備するようにした。
【００４３】
この方法によれば、検索対象文字列を正の索引、負の索引及び削除レコード表からなる更新情報から検索するため、索引に記録された各要素から検索対象を検索できるため、世代管理型文書データベースに対する検索処理効率の向上を図ることができる。
【発明の効果】
【００４４】
本発明によれば、初期世代から次世代への索引更新の際に、新版で削除されるべき初期世代の索引要素を記録した負の索引と、追加、変更のあった文字列の出現位置と文字列長の組を記録した正の索引と、削除されたレコードの文書ＩＤを記録した削除レコード表の組を有する更新情報を作成し、この更新情報と、索引の組で次世代の文書データベースを表現することにより、変更した文字列部分のみに比例した量の更新情報となるため、更新情報の記憶領域を削減でき、同時に、更新情報量の削減に比例して、更新情報作成処理時間も短縮することができる。
【発明を実施するための最良の形態】
【００４５】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００４６】
図１は、本発明の実施の形態に係る世代管理型の文書データベース処理システムの全体構成を示す図である。図１において、文書データベース処理システム１００は、文書入力装置１０１と、文書ＤＢ更新処理装置１０２と、文書ＤＢ保持装置１０３と、文書ＤＢ検索装置１０４と、主記憶装置１０８，１１０と、補助記憶装置１０９とから構成される。
【００４７】
文書入力装置１０１は、文書データを入力するためのキーボード等を備え、文書ＤＢ更新処理装置１０２に対して文書データを入力する。
【００４８】
文書ＤＢ更新処理装置１０２は、文書入力装置１０１から入力された初期文書（世代０）からレコード単位に文字列を切り出して初期索引を作成して、初期文書と初期索引を世代０の文書ＤＢ１０３ａとして文書ＤＢ保持装置１０３に記録する。
【００４９】
また、文書ＤＢ更新処理装置１０２は、文書入力装置１０１から新たに更新用文書が入力されると、その更新用文書と、世代０の文書ＤＢ１０３ａの初期文書との文字列の差分情報からレコード単位に索引（後述する正の索引と負の索引）と、後述する削除レコード表を作成する。これらと、入力された更新用文書を、世代０→１の更新情報１０３ｂとして文書ＤＢ保持装置１０３に記録する。
【００５０】
また、文書ＤＢ更新処理装置１０２は、文書入力装置１０１から入力された新たなＮ−１世代目の更新用文書と、一世代前（Ｎ−２世代）の更新情報（図示せず）から更新用文書と初期文書との文字列の差分情報である各世代に記録された更新情報の索引（正の索引、負の索引）を解釈した上で、今回の更新に対応する索引（正の索引、負の索引）と削除レコード表を作成する。作成された索引（正の索引、負の索引）と削除レコード表と入力された更新用文書を、世代Ｎ−２→Ｎ−１の更新情報１０３ｃとして文書ＤＢ保持装置１０３に記録する。
【００５１】
また、文書ＤＢ更新処理装置１０２は、文書入力装置１０１から新たなＮ世代目の更新用文書が入力されると、上記の説明と同様に、索引（正の索引、負の索引）と削除レコード表を作成し、入力された更新用文書とともに、世代Ｎ−１→Ｎの更新情報１０３ｄとして文書ＤＢ保持装置１０３に記録する。
【００５２】
また、文書ＤＢ更新処理装置１０２は、文書ＤＢ保持装置１０３に記録した複数世代の更新情報をマージする更新情報マージ処理機能を有する。これについては、後述する。
【００５３】
文書ＤＢ保持装置１０３は、世代０の文書ＤＢ１０３ａを永続的に保持するとともに、文書ＤＢ更新処理装置１０２により更新用文書が入力される毎に作成される世代間の更新情報１０３ａ〜１０３ｄを保持する。なお、図１に示す世代０の更新情報１０３ａには、初期文書１０３１と初期索引４０１が記録されていることを示している。
【００５４】
主記憶装置１０８は、文書ＤＢ更新処理装置１０２において実行される文書ＤＢ更新処理の処理プログラムを記憶するとともに、後述する更新情報マージ処理において、比較対照となる索引の各要素（検索対象文字列）等を一時的に記憶する。
【００５５】
補助記憶装置１０９は、更新情報マージ処理において複数世代の更新情報の索引から作成された索引等を記憶する。
【００５６】
文書ＤＢ検索装置１０４は、検索キーワード入力部１０５と、文書ＤＢ検索部１０６と、検索結果出力部１０７とから構成される。
【００５７】
検索キーワード入力部１０５は、ユーザが文書ＤＢを検索する検索文字列を入力するためのキーボード等を備え、入力された検索文字列を文書ＤＢ検索部１０６に出力する。
【００５８】
文書ＤＢ検索部１０６は、検索キーワード入力部１０５から検索キーワードが入力されると、検索文字列に含まれる文字列毎に、文書ＤＢ保持装置１０３に記録された複数世代の更新情報と、世代０の文書ＤＢを入力として、世代Ｎの更新情報を検索する検索機能を有し、その検索結果を検索結果出力部１０７に出力する。
【００５９】
検索結果出力部１０７は、文書ＤＢ検索部１０６から入力される検索結果を、ディスプレイ等に表示する。
【００６０】
主記憶装置１１０は、文書ＤＢ検索装置１０４において実行される文書ＤＢ検索処理の処理プログラムを記憶するとともに、文書ＤＢ検索処理の検索結果等を記憶する。
【００６１】
次に、文書ＤＢ更新処理装置１０２で実行される更新情報作成処理について、図２に示す文書ＤＢ更新処理装置１０２のブロック図、図３に示す文書ＤＢの更新例、図４に示す更新前の文書ＤＢの索引例、図５に示す更新後の文書ＤＢの索引例、図６に示す削除レコード表の例及び図７に示すフローチャートを参照して説明する。
【００６２】
なお、この更新情報作成処理では、最初に入力された文書である初期世代文書（世代０の文書）と、次に更新用文書として入力された世代１の更新用文書との間の差分文字列に対して、更新情報を作成する場合を説明する。
【００６３】
図２は、初期の文書から作成された初期世代の文書ＤＢから、次世代つまり世代１の文書ＤＢを作成する文書ＤＢ更新処理装置１０２の構成を示す図である。
【００６４】
図２において、文書ＤＢ更新処理装置１０２は、更新文書判定部２０１と、正の索引作成部２０２、負の索引作成部２０３及び削除レコード表作成部２０５を含む文書ＤＢ更新処理部２０４と、索引作成部２０６と、から構成される。
【００６５】
図３（ａ）〜（ｃ）は、文書ＤＢとして、個人の雑感を記録した文書の更新例を示す図であり、従来で説明したものと同じ内容の文書ＤＢである。
【００６６】
図３（ａ）に示すように、更新前の文書ＤＢ３０１は、タグ（＜ｄｏｃ  Ｉｄ＝Ｘ＞と表記）で区切られた複数の文書レコードの列として表現され、各文書レコードは、「文書ＩＤ」と「本文」の２項目を、文書ＩＤ順に並べて記述されている。特に文書ＩＤについては、文書ＩＤがＸの場合、タグの要素として、＜ｄｏｃ  Ｉｄ＝Ｘ＞のように記録して表現するものとする。なお、この文書ＤＢは高速な検索、更新処理を行うために、図４に示す更新前の文書ＤＢの索引（初期索引）４０１のように、各文書レコードから、文書に出現する単語と、その単語の出現する文書ＩＤと、出現文字位置が記録されている。
【００６７】
図３（ａ）の更新前の文書ＤＢ３０１では、文書ＩＤが１、２、３の３つの文書レコードがあり、更新の際には、文書ＩＤで各文書レコードを識別し、追加・変更・削除のそれぞれの更新処理を行う。図３（ｂ）、（ｃ）は、それぞれ更新前の文書ＤＢ３０１に対する更新用文書３０２及び更新後の文書ＤＢ３０３である。
【００６８】
この更新用文書３０２の例では、文書ＩＤ１、ＩＤ３の既存の文書レコードに対する変更データと、文書ＩＤ２の既存の文書レコードの削除データ（本文が空の雑感文書は文書ＩＤで指定した既存の雑感文書の削除を指示するものと定める）と、文書ＩＤ４の新たな追加文書レコードが含まれており、文書ＤＢ更新処理装置１０２において差分更新処理を行うと、図３（ｃ）に示すような次の世代の雑感文書ＤＢ、すなわち、更新後の文書ＤＢ３０３が作成される。
【００６９】
図２の文書ＤＢ更新処理部２０４では、図３（ｂ）に示す更新用文書３０２あるいは初期文書（更新処理でなく初めての文書データの場合を特別にこのように呼ぶこととする）を入力として受け取り、図３（ａ）のような更新前の文書ＤＢ３０１を高速に検索し、更新するために、文書ＩＤ及び本文から切り出す文字列に対して初期索引あるいは初期索引からの差分索引である更新情報を作成し、更新文書あるいは初期文書と共に、文書ＤＢ保持装置１０３に記録する。
【００７０】
図２において、索引作成部２０６は、世代０の文書ＤＢ１０３ａから初期文書１０３１（図３（ａ）の更新前の文書ＤＢ３０１に含まれる文書レコードのこと）を読み出し、従来の全文検索ＤＢ作成における既知の手法であるＮ−ｇｒａｍ分割方式や、各文書レコードに対して単語辞書を用いて単語で分割する方式等といった方式を用いて、初期文書に含まれる各文書レコードから文字列の切出しを行い、その出現位置を記録して、図４に示すような更新前の文書ＤＢの索引、すなわち、初期索引４０１を作成する。そして、索引作成部２０６は、作成した初期索引４０１を世代０の文書ＤＢ１０３ａに記録する。
【００７１】
次に、文書入力装置１０１から次の世代（世代１）の更新用文書３０２（図３（ｂ）参照）が入力されて、世代０の文書ＤＢ１０３ａ内の初期文書１０３１を次の世代１に更新する際に、世代０→１の更新情報１０３ｂを作成する更新情報作成処理について、図２の構成図及び図７に示すフローチャートを参照して説明する。また、図５（ａ）、（ｂ）は、図２の文書ＤＢ更新処理装置１０２による更新処理おいて作成される正の索引５０１の例と、負の索引５０２の例を示す図である。
【００７２】
図２において、世代Ｎの更新用文書３０２が文書ＤＢ更新処理装置１０２に入力される（ステップＳ７０１）。更新文書判定部２０１は、更新用文書３０２の総レコード数を判定し、比較対照とする文書レコードｊ（ｊ：レコード番号、すなわち、文書ＩＤ）を指定し、その指定文書レコードｊが判定した総レコード数以下か否かを判定する（ステップＳ７０２）。
【００７３】
更新文書判定部２０１は、指定文書レコードｊが総レコード数以下であると判定した場合（ステップＳ７０２：ＹＥＳ）、指定文書レコードｊと初期文書１０３１の対応する文書レコードｊとの比較を行い、レコード間の差分文字列リストＬ（図示せず）を求める（ステップＳ７０３）。
【００７４】
次に、更新文書判定部２０１は、差分文字列リストＬの要素数が、予め設定した閾値εを越えるか否かを判定する（ステップＳ７０４）。更新文書判定部２０１は、要素数が閾値εを越えないと判定した場合（ステップＳ７０４：ＮＯ）、その差分文字列リストＬを文書ＤＢ更新処理部２０４に通知する。
【００７５】
次に、文書ＤＢ更新処理部２０４は、更新文書判定部２０１から差分文字列リストＬの通知を受けると、差分文字列リストＬの各要素である文字列に基づいて、従来のＮ−ｇｒａｍや、極大単語切出し方式などの従来の索引作成方法により、更新用文書３０２の文書レコードｊから文字列Ｗｏｒｄ（ｌ）〜Ｗｏｒｄ（Ｍ）の分割切出しを行う（ステップＳ７０５）。
【００７６】
次に、文書ＤＢ更新処理部２０４は、切り出した文字列Ｗｏｒｄ（ｌ）〜Ｗｏｒｄ（Ｍ）の中から、最初の文字列Ｗｏｒｄ（ｉ）（ｉ＝ｌ）を指定し（ステップＳ７０６：ＹＥＳ）、その文字列Ｗｏｒｄ（ｉ）の出現位置に、世代０の初期索引４０１の要素Ｗｏｒｄ（ｐ）で削除されるべき文字列が存在するかどうかを判定する（ステップＳ７０７）。
【００７７】
文書ＤＢ更新処理部２０４は、文字列Ｗｏｒｄ（ｉ）の出現位置に削除されるべき文字列Ｗｏｒｄ（ｐ）が存在しないと判定した場合（ステップＳ７０７：ＮＯ）、文字列Ｗｏｒｄ（ｉ）の文書ＩＤ、出現位置及び文字列長の差分値の情報を正の索引作成部２０２に渡す。正の索引作成部２０２は、文書ＤＢ更新処理部２０４から渡された文字列Ｗｏｒｄ（ｉ）の文書ＩＤ、出現位置及び文字列長の差分値の情報を組み合わせて、位置ポスティングとして、図５（ａ）に示すような正の索引５０１に記録する（ステップＳ７０８）。
【００７８】
また、ステップＳ７０７において、文書ＤＢ更新処理部２０４は、文字列Ｗｏｒｄ（ｉ）の出現位置に削除されるべき文字列Ｗｏｒｄ（ｐ）が存在すると判定した場合（ステップＳ７０７：ＹＥＳ）、文字列Ｗｏｒｄ（ｐ）の文書ＩＤ及び出現位置を負の索引作成部２０３に渡す。負の索引作成部２０３は、文書ＤＢ更新処理部２０４から渡された文字列Ｗｏｒｄ（ｐ）の文書ＩＤ及び出現位置の対を、図５（ｂ）に示すような負の索引５０２に記録する（ステップＳ７０９）。
【００７９】
以後、文書ＤＢ更新処理部２０４は、切り出した文字列Ｗｏｒｄ（ｌ）〜Ｗｏｒｄ（Ｍ）の中から、文字列Ｗｏｒｄ（ｉ）を順次指定（ｉ＋＋）して（ステップＳ７０６）、切り出した文字列Ｗｏｒｄ（ｉ）の全てを指定し、同様に、文書ＤＢ更新処理部２０４は、指定された各文字列Ｗｏｒｄ（ｉ）に対して、ステップＳ７０７〜ステップＳ７０９の処理を繰り返し実行して、正の索引５０１及び負の索引５０２を作成する。
【００８０】
以上の処理により、文書ＤＢ更新処理部２０４は、文書ＩＤにより示される１つの文書レコードに対して、初期文書との差分文字列Ｌと、差分文字列Ｌからの文字列の切り出しと、正の索引５０１及び負の索引５０２の各作成処理が終了し、その正の索引５０１と負の索引５０２を、図２に示す世代０→１の更新情報１０３ｂ内に記録する。
【００８１】
次に、更新文書判定部２０１は、切り出した文字列Ｗｏｒｄ（ｉ）の全ての指定を終了すると（ｉ＝Ｍの条件成立）（ステップＳ７０６：ＮＯ）、次に比較対照とする文書レコードｊを指定するため、ｊを加算する（ｊ＋＋）（ステップＳ７１０）。
【００８２】
次に、更新文書判定部２０１は、ステップＳ７１０で加算したｊに基づいて、比較対照とする文書レコードｊを指定し、その指定文書レコードｊが判定した総レコード数以上か否かを判定する（ステップＳ７０２）。
【００８３】
更新文書判定部２０１は、指定文書レコードｊが総レコード数以下であると判定した場合（ステップＳ７０２：ＹＥＳ）、指定文書レコードｊと初期文書１０３１の対応する文書レコードｊとの比較を行い、レコード間の差分文字列リストＬを求め（ステップＳ７０３）、ステップＳ７０４以下の処理を繰り返し実行する。
【００８４】
また、更新文書判定部２０１は、ステップＳ７０４において、差分文字列リストＬの要素数が、予め設定した閾値εを越えると判定した場合（ステップＳ７０４：ＹＥＳ）、初期文書と更新用文書において、指定文書レコードｊ間の違いが多すぎるため、その指定文書レコードｊの情報を削除レコード表作成部２０５に通知する。削除レコード表作成部２０５は、更新文書判定部２０１から指定文書レコードｊの情報が通知されると、図６に示すような削除レコード表に文書レコードｊを記録する（ステップＳ７１１）。
【００８５】
また、更新文書判定部２０１は、文書ＤＢ更新処理部２０４に更新用文書３０２の文書レコードｊを、追加レコードとして処理するように通知する。文書ＤＢ更新処理部２０４は、更新文書判定部２０１から更新用文書３０２の文書レコードｊを追加レコードとして処理する通知を受けると、位置ポスティングが全て０の正の索引である当該文書レコードｊの索引を作成する（ステップＳ７１２）。
【００８６】
以上のステップＳ７１１及びステップＳ７１２の処理は、更新用文書３０２の全ての文書レコードｊに対して実行されて、削除レコード表６０１の作成が完了し、図２に示すように世代０→１の更新情報１０３ｂ内に記録される。
【００８７】
また、ステップＳ７０２において、更新文書判定部２０１は、指定文書レコードｊが総レコード数を越えたと判定した場合（ｊ＞総レコード数）（ステップＳ７０２：ＮＯ）、更新用文書３０２の全ての文書レコードｊに対する処理が終了したため、本更新情報作成処理を終了する。
【００８８】
以上の更新情報作成処理により、図３（ａ）の更新前の文書ＤＢ３０１に記録された初期文書１０３１の各文書レコードと、図３（ｂ）の更新用文書３０２の各文書レコードとの間の差分文字列から、図５（ａ）の正の索引５０１が作成され、図５（ｂ）の負の索引５０２が作成され、図６の削除レコード表６０１が作成されて、図２の世代０→１の更新情報１０３ｂとして、図１の文書ＤＢ保持装置１０３に記録される。
【００８９】
ここで、図３（ａ）、（ｂ）、図４、図５（ａ）、（ｂ）及び図６を参照して、上記更新情報作成処理に基づく更新情報１０３ｂの作成過程を具体的に説明する。
【００９０】
まず、図３（ａ）の更新前の文書ＤＢ３０１に対しては、図４に示す更新前の文書ＤＢの索引（以下、初期索引という）４０１が作成済みである。この初期索引４０１では、更新前の文書ＤＢ３０１内の文書ＩＤ＜ｄｏｃ  ＩＤ＝１＞で示される文書レコードから切り出した４つの要素の文字列を示している。図中の（１，１）、（１，２）、（１，３）、（１，６）は、それぞれ前者の数値が文書ＩＤを示し、後者の数値が要素の出現位置（文字桁数）を示している。
【００９１】
そして、更新文書判定部２０１は、図３（ｂ）の更新用文書３０２が入力されると、更新用文書３０１の総レコード数が「４」であることを判定し、比較対照とする文書レコード１（＜ｄｏｃ  ＩＤ＝１＞）を指定し、この文書レコード１と初期文書１０３１の文書レコード１との間の差分文字列リストＬを求める。
【００９２】
この場合、初期索引４０１に記録された文書レコード１の要素に基づいて、初期文書１０３１の文書レコード１と更新用文書３０２の文書レコード１との間の差分文字列は、図３（ａ）、（ｂ）に示す各下線部分である。すなわち、差分文字列リストＬには、初期文書１０３１の文書レコード１の“だというのに”、“暑い。”、“気温”、“３０度”と、更新用文書３０２の文書レコード１の“に”、“近づいている”、“が”、“未だ”、“暑く、”、“最高気温”、“３５度”が、要素として記録される。
【００９３】
次に、更新文書判定部２０１は、差分文字列リストＬの要素数が、予め設定した閾値ε（例えば、２０）を越えるか否かを判定する。この場合、図３（ａ）、（ｂ）の各文書レコード１に示す差分文字列リストＬの要素の要素数は１１であるため、要素数が閾値εを越えないと判定される。
【００９４】
そして、更新文書判定部２０１は、その差分文字列リストＬを文書ＤＢ更新処理部２０４に通知する。次に、文書ＤＢ更新処理部２０４は、更新文書判定部２０１から差分文字列リストＬを受けると、差分文字列リストＬの各要素に基づいて、従来のＮ−ｇｒａｍや、極大単語切出し方式などの従来の索引作成方法により、更新用文書３０２の文書レコード１から、上記文字列Ｗｏｒｄ（ｌ）〜Ｗｏｒｄ（Ｍ）に相当する“に”、“近づいている”、“が、”、“未だ”、“暑く、”、“最高気温”、“３５度”の分割切出しを行う。
【００９５】
次に、文書ＤＢ更新処理部２０４は、切り出した文字列Ｗｏｒｄ（ｌ）〜Ｗｏｒｄ（Ｍ）の中から、上記文字列Ｗｏｒｄ（ｉ）に相当する文書レコード１の“に”を指定し、その出現位置「６」に、初期文書１０３１の文書レコード１で削除されるべき文字列Ｗｏｒｄ（ｐ）が存在するか否かを判定する。
【００９６】
図３（ａ）の文書レコード１では、出現位置「６」に文字列“だというのに”が存在するため、文書ＤＢ更新処理部２０４は、削除されるべき文字列Ｗｏｒｄ（ｐ）が存在すると判定し、文字列“だというのに”の文書ＩＤ「１」及び出現位置「６」を負の索引作成部２０３に渡す。負の索引作成部２０３は、文書ＤＢ更新処理部２０４から渡された文字列“だというのに”の文書ＩＤ「１」及び出現位置「６」の対（１，６）を、図５（ｂ）に示す負の索引５０２に記録する。
【００９７】
また、文書ＤＢ更新処理部２０４は、文字列“に”は、初期文書１０３１の文書レコード１の文字列“だというのに”と比較して、文字列長が５文字分短くなっているため、文字列“に”の文書ＩＤ「１」、出現位置「６」及び文字列長の差分値「−５」の情報を、正の索引作成部２０２に渡す。正の索引作成部２０２は、文書ＤＢ更新処理部２０４から渡された文字列“に”の文書ＩＤ「１」、出現位置「６」及び文字列長の差分値「−５」の情報を組み合わせて位置ポスティング（１，６，−５）として、図５（ａ）に示すような正の索引５０１に記録する。
【００９８】
また、文書ＤＢ更新処理部２０４は、切り出した文字列Ｗｏｒｄ（ｌ）〜Ｗｏｒｄ（Ｍ）の中から、次の文字列“近づいている”を指定し、その出現位置「７」に、初期文書１０３１の文書レコード１で削除されるべき文字列Ｗｏｒｄ（ｐ）が存在するか否かを判定する。
【００９９】
図３（ａ）の文書レコード１では、出現位置「７」には、削除されるべき文字列Ｗｏｒｄ（ｐ）が存在しない。このため、文書ＤＢ更新処理部２０４は、文字列「近づいている」の文書ＩＤ「１」、出現位置「７」及び文字列長「６」の情報を、正の索引作成部２０２に渡す。正の索引作成部２０２は、文書ＤＢ更新処理部２０４から渡された文字列“近づいている”の文書ＩＤ「１」、出現位置「７」及び文字列長の差分値「６」の情報を組み合わせて位置ポスティング（１，７，６）として、図５（ａ）に示すような正の索引５０１に記録する。
【０１００】
以上の処理を、文書レコード１の他の差分文字列及び他の文書レコード２〜３の各差分文字列に対しても実行するにより、図５（ａ）に示すような正の索引５０１が作成される。
【０１０１】
次に、更新文書判定部２０１は、更新用文書３０２の次の文書レコード２（＜ｄｏｃ  ＩＤ＝２＞）を指定し、この文書レコード２と、初期文書１０３１の文書レコード２との間の差分文字列リストＬを同様に求めるが、更新用文書３０２の文書レコード２には、文書が存在しないため、差分文字列数が閾値εを越えることになり、その文書レコード２の情報を削除レコード表作成部２０５に渡す。
【０１０２】
また、更新文書判定部２０１は、更新用文書３０２の文書レコード３についても、初期文書１０３１の文書レコード３との間の差分文字列リストＬを求めるが、図３（ａ）、（ｂ）の下線部分が差分文字列であり、上記閾値εとして「２０」を越えるため、その文書レコード３の情報を削除レコード表作成部２０５に渡す。
【０１０３】
削除レコード表作成部２０５は、更新文書判定部２０１から渡された文書レコード２，３の情報に基づいて、図６に示す削除レコード表６０１を作成して、図２の世代０→１の更新情報１０３ｂに記録する。
【０１０４】
以上のように、文書ＤＢ更新処理装置１０２では、初期文書ＤＢ１０３ａに対して、次の世代の更新用文書が入力されると、更新情報として正の索引、負の索引及び削除レコード表が作成されて、図１の文書ＤＢ保持装置１０３に記録される。また、図３（ｃ）に示す更新後の文書ＤＢ３０３が作成される。
【０１０５】
したがって、正の索引とは、入力された更新用文書の各文書レコードにおいて、初期文書１０３１の各文書レコードから新たに追加された文字列を切り出し、その文書ＩＤ、出現位置及び位置ポスティングとを組み合わせて索引として記録するためのものである。
【０１０６】
また、負の索引とは、入力された更新用文書の各文書レコードに対して、初期文書１０３１の各文書レコードで不要になった文字列の文書ＩＤと出現位置とを組み合わせて索引として記録するためのものである。
【０１０７】
また、削除レコード表とは、入力された更新用文書の各文書レコードにおいて、初期文書１０３１から削除された文書レコード、又は大幅に変更された文書レコードを記録するためのものである。
【０１０８】
以上の更新情報作成処理では、世代０から世代１の更新情報を作成する場合を説明したが、より一般的な世代１から世代２以降の更新情報作成処理について、図８に示す文書ＤＢ更新処理装置１０２のブロック図、図９に示す文書ＤＢの更新例、図１０に示す更新用文書の例、図１１に示す初期文書ＤＢの索引例、図１２に示す更新文書ＤＢの更新情報の例及び図１３に示すフローチャートを参照して説明する。
【０１０９】
図８は、世代０から世代１、世代２以降の更新情報を作成する文書ＤＢ更新処理装置１０２の構成を示す図であり、上記図２の文書ＤＢ更新処理装置１０２と同一の構成部分には、同一符号を付している。
【０１１０】
図８において、文書ＤＢ更新処理装置１０２は、複数更新情報解釈部８０１を含む更新文書判定部２０１と、正の索引作成部２０２及び負の索引作成部２０３を含む文書ＤＢ更新処理部２０４と、削除レコード表作成部２０５と、から構成される。
【０１１１】
複数更新情報解釈部８０１は、図１３のフローチャートに示す複数更新情報解釈処理を実行し、世代Ｎの更新用文書ｉが入力されたとき、世代１〜Ｎ−１の各世代０→１〜世代Ｎ−２→Ｎ−１の各更新情報に含まれる削除レコード表ｉ＋１に記述される削除対象となる文書レコード番号のレコードについて、既に削除済みとして解釈する（ステップＳ１３０１，Ｓ１３０２）。
【０１１２】
図９（ａ）〜（ｃ）は、上記図３（ａ）に示した世代０の更新前の文書ＤＢ３０１と、図３（ｃ）に示した世代１の更新文書ＤＢ又は更新後の文書ＤＢ３０３とから更に更新を行い、世代２の更新文書ＤＢ９０１を作成する例を示している。
【０１１３】
図１０（ａ）は、上記図３（ｂ）に示した世代１の更新用文書３０２と、同図（ｂ）は世代２の更新用文書１００１とをそれぞれ示している。
【０１１４】
また、図１１は、上記図４に示した初期索引４０１と、図１に示した初期文書１０３１とを含む世代０の文書ＤＢ１０３ａを示している。図１２（ａ）は、上記図５（ａ）に示した正の索引５０１と、図５（ｂ）に示した負の索引５０２と、図６に示した削除レコード表６０１と、図３（ｂ）に示した更新用文書３０２とを含む世代０→１の更新情報１０３ｂを示している。
【０１１５】
図１２（ｂ）は、世代１→２の更新情報１２０１に含まれる正の索引１２０１ａと、負の索引１２０１ｂと、削除レコード表１２０１ｃと、更新用文書１００１とを示している。
【０１１６】
図９（ａ）の世代０の文書ＤＢ３０１から、同図（ｂ）の世代１の更新文書ＤＢ３０３を作成するところまでは、上記図７に基づく更新情報作成処理において説明したが、図１０（ｂ）の更新用文書１００１が入力されると、文書ＩＤ３の文書レコードが削除され、文書ＩＤ４の文書レコードは内容が変更されるため、世代２の更新文書ＤＢは、同図（ｃ）の９０１のように作成される。図１２（ｂ）は、図９の例において、図８の文書ＤＢ更新処理部２０４により世代１→２の更新情報１２０１を作成した場合を示す図である。
【０１１７】
図１２（ｂ）の世代１→２の更新情報１２０１では、図１０（ａ）の更新用文書３０２中の文書ＩＤ３の文書レコードは、同図（ｂ）の更新用文書１００１により削除対象となるので、削除レコード表１２０１ｃに記録される。また、世代１から世代２への更新において、文書ＩＤ４の文書レコードは、更新情報判定部２０１により、図１０（ａ）の更新用文書３０２と同図（ｂ）の更新用文書１００１の各該当文書レコードが比較され、差分文字列数が判定されると、この例ではほとんど変更が無いものと判定され、その判定結果が文書ＤＢ更新処理部２０４に通知される。
【０１１８】
そして、文書ＤＢ更新処理部２０４において、上記図７で説明した通常の更新処理が実行されると、図１２（ｂ）に示す正の索引１２０１ａのように文字列が切り出され、世代１の正の索引５０１と比較されることにより、削除対象となる文字列が負の索引１２０１ｂのように記録される。
【０１１９】
また、複数更新情報解釈部８０１において、図１３のフローチャートに示す複数更新情報解釈処理を実行することにより、図１２（ｂ）に示す削除レコード表１２０１ｃが記録される。
【０１２０】
上記の図９〜図１２の例のように、世代０→１の更新情報１０３ｂと、世代１→２の更新情報１２０１と、世代０の初期索引４０１を組にすることで、図９（ｃ）に示す世代２の更新文書ＤＢ９０１を表現することができる。これらの複数世代における世代間の索引の関係を概念的な式で表現すると下記のようになる。
【０１２１】
（正の索引Ｎ）＝Ｆ（正の索引Ｎ−１）−（負の索引Ｎ）−（削除レコード表Ｎ）
但し、Ｎ：世代番号（１＜＝Ｎ）
Ｆ（索引ｎ）：世代ｎの正の索引Ｎにおける位置シフト値を反映させる関数
【０１２２】
したがって、本実施の形態による更新情報作成処理では、世代管理方式の文書ＤＢにおいて、現世代から次世代への索引更新の際に、新版で削除される単語と、その出現位置リストの組のリストを記録した負の索引と、変更後の索引で特に追加、変更のあった文字列の出現位置と位置シフト値を記録した正の索引と、削除されたレコードの文書ＩＤを記録した削除レコード表の組を有する更新情報を作成し、この更新情報と、索引の組で次世代の文書ＤＢを表現することにより、変更した文字列部分のみに比例した量の更新情報となるため、更新情報の記憶領域を削減でき、同時に、更新情報量の削減に比例して、更新情報作成処理時間も短縮することができる。
【０１２３】
なお、本実施の形態による更新情報作成処理では、文字列の切出し方法については、従来の全文検索の索引作成時に用いられている既知の技術である、Ｎ−ｇｒａｍ分割方式や、辞書単語による分割方式など、すなわち、切出し文字列とその出現位置で情報を記録している索引であれば、どのような方式にも適用できる。
【０１２４】
また、本実施の形態の更新情報作成処理では、更新情報作成の際に、変更される文字列箇所が多い文書レコードは、従来方式よりも更新・検索処理共に、オーバーヘッドが大きくなる。このため、本実施の形態の更新情報作成処理では、変更される文字列数が予め決定した閾値εを超える場合は、削除対象レコードとして削除レコード表に記録し、通常通りの索引更新を行う事により、常に更新情報を適用して更新処理を行う場合よりも処理効率の向上を図ることができる。
【０１２５】
なお、閾値の決定については、管理者の経験的な値でも良いし、更新データの性質に合わせて、前もって更新処理の統計を採っておき、その値に基づいて経験的に決める事も可能であり、また、ユーザにその最適な閾値を決定させることもできる。
【０１２６】
次に、本実施の形態の更新情報作成処理により、更新用文書が入力される度に作成される各世代間の更新情報、特に、複数世代にわたる更新情報を効率化する手段であるマージ処理について説明する。
【０１２７】
図１４は、文書ＤＢ更新処理装置１０２に、新たな機能として、複数の更新情報を一つの更新情報にまとめる更新情報マージ処理部１４０１と、マージ処理に伴い、複数の更新情報を場合に応じて消去する更新情報削除部１４０２とを新たに設けた文書ＤＢ更新処理装置１０２の構成を示すブロック図である。また、図１５は、文書ＤＢ更新処理装置１０２において実行される、世代ｊの更新情報〜世代ｋの更新情報を一つの更新情報にまとめるための更新情報マージ処理を示すフローチャートである。
【０１２８】
なお、図１６は、図１２（ａ）、（ｂ）で説明した世代０〜世代２の更新情報の作成において、作成される二つの更新情報（世代０→１の更新情報１０３ｂと、世代１→２の更新情報１２０１）を本実施の形態の更新情報マージ処理部１４０１において、一つの更新情報にまとめて、世代０→２の更新情報１６０１とする例を示す図である。
【０１２９】
まず、更新情報マージ処理部１４０１は、世代１→２の更新情報１２０１である、正の索引１２０１ａ、負の索引１２０１ｂの全要素を、不揮発メモリ等である主記憶装置１０８に、累積正要素集合（図示せず）及び累積負要素集合（図示せず）として記録する（ステップＳ１５０１）。次に、更新情報マージ処理部１４０１は、削除レコード表１２０１ｃの要素を累積削除レコード集合として主記憶装置１０８に記録する（ステップＳ１５０２）。
【０１３０】
次に、更新情報マージ処理部１４０１は、一時変数ｉの値をｊになるまで１増加させつつ、ステップＳ１５０４以降の処理を実行する（ステップＳ１５０３）。「ｉ＜ｊ」の条件が成立するまでの更新情報マージ処理部１４０１は、一時正要素集合と呼ぶことにする正の索引の要素集合の格納領域を主記憶装置１０８内に用意して初期化し、正の索引１２０１ａの全要素を一時正要素集合に記録する（ステップＳ１５０４）。但し、この際、更新情報マージ処理部１４０１は、削除レコード表１２０１ｃに記録された文書ＩＤを持つ要素、つまり文書ＩＤが３の文書レコードについては、一時正要素集合には記録しない。
【０１３１】
次に、更新情報マージ処理部１４０１は、累積負要素集合の各要素ＭＷｏｒｄ（ｍ）をそれぞれ取り出しつつ（ステップＳ１５０５）、一時正要素集合（図示せず）にＭＷｏｒｄ（ｍ）が存在するかを調べる（ステップＳ１５０６）。存在する場合（ステップＳ１５０６：ＹＥＳ）、更新情報マージ処理部１４０１は、一時正要素集合からＭＷｏｒｄ（ｍ）を削除し、累積負要素集合からＭＷｏｒｄ（ｍ）を削除する（ステップＳ１５０７）。
【０１３２】
図１２（ｂ）の世代１→２の更新情報１２０１の例では、現時点で負の索引１２０１ｂに記録されている情報が累積負要素集合に記録されており、累積負要素集合の“Ｍ電器(４，１，０)”と、一時正要素集合の“Ｍ電器(４，１，０)”が共に存在するため、“Ｍ電器(４，１，０)”は一時正要素集合から削除される。
【０１３３】
次に、更新情報マージ処理部１４０１は、累積負要素集合の要素を全て比較が終わると（ステップＳ１５０５：ＮＯ）、世代０→１の削除レコード表６０１の要素を累積削除レコード集合（図示せず）として主記憶装置１０８に記録する（ステップＳ１５０８）。さらに、一時正要素集合を累積正要素集合に追加記録し（ステップＳ１５０９）、世代０→１の負の索引５０２の要素を累積負要素集合（図示せず）に追加記録する（ステップＳ１５１０）。
【０１３４】
その後、更新情報マージ処理部１４０１は、ステップＳ１５０３の処理における比較式が成立しない場合（ステップＳ１５０３：ＮＯ）、これまでに求めた累積負要素集合を図１６に示す世代０→２の更新情報１６０１内に、負の索引（０＿２）１６０３として、累積正要素集合を正の索引（０＿２）１６０２、累積削除レコード集合を削除レコード表（０＿２）１６０４として記録し（ステップＳ１５１１）、更新処理を終了する。
【０１３５】
このように複数世代にわたる更新情報を一つの更新情報にまとめることにより、以降の世代更新処理、検索処理の際の処理速度を向上させることができる。
【０１３６】
また、マージ処理が終了すると、文書データベースの管理者が予め指定した条件等に応じて、更新情報削除部１４０２は、世代０→１の更新情報１０３ｂと、世代１→２の更新情報１２０１を文書ＤＢ保持装置１０３より消去することもでき、文書ＤＢ保持装置１０３の記憶領域を有効に活用できる。また、その削除の際に他の記憶メディア、例えば、ディスクメディア等の外部記憶メディアへのバックアップ書き出しを行った上で消去する事で、より安全に削除を行うことができる。
【０１３７】
また、本実施の形態の更新情報作成処理では、複数回の更新を行い、更新情報が蓄積されると、その更新情報に比例し、更新速度、検索速度共に遅くなるが、複数の更新情報に対して更新情報マージ処理を行うため、更新及び検索処理速度の低下を緩和することができる。同時に、マージ処理完了後に必要のなくなった更新情報を削除する事で、文書ＤＢを格納する記憶領域を効率よく使用することができる。
【０１３８】
ここまでは、文書ＤＢの更新処理について述べたが、以下、上記の動作で作成した文書ＤＢを検索する文書ＤＢ検索装置１０４の動作について、以下に説明する。
【０１３９】
図１７は、文書ＤＢ検索装置１０４の構成を示すブロック図である。図１７において、文書ＤＢ検索装置１０４は、検索キーワード入力部１０５と、索引検索部１７０１と、位置シフト累算部１７０２と、負索引・削除レコード表解釈部１７０３と、検索結果出力部１０７と、から構成される。
【０１４０】
図１８は、文書ＤＢ検索装置１０４において実行される文書ＤＢ検索処理を示すフローチャートである。これらの図を参照して、検索処理を説明する。
【０１４１】
ユーザにより検索キーワード入力部１０５から検索文字列が入力される（ステップＳ１８０１）。文書ＤＢ検索装置１０４は、入力された検索文字列を辞書単語に基づいてキーワード分割処理により切り出す（ステップＳ１８０２）。
【０１４２】
次に、文書ＤＢ検索装置１０４は、初期準備として、負の索引の要素と、削除レコード表の要素を格納する一時負集合（図示せず）と、上記キーワード分割処理で得られた文字列で、かつ、正の索引で検索が可能な場合に、その先頭出現位置のリストを、複数世代に渡って累積的に格納する累積結果集合（図示せず）と、累積結果集合の各要素に対して複数世代の正の索引における位置シフト値を累算する位置シフト累算集合（図示せず）とを初期化する（ステップＳ１８０３）。
【０１４３】
以後、文書ＤＢ検索装置１０４は、分割された各切出し文字列についてｉがＭを越えるまで処理を行う（ステップＳ１８０４）。次に、世代を表す添え字として用いるｊを、最初に検索対象とする世代Ｎをｊに代入しておき、これを１ずつ減らしながら、ｊが０以上の間処理を続ける（ステップＳ１８０５）。
【０１４４】
ｊが０以上の場合（ステップＳ１８０５：ＹＥＳ）、索引検索部１７０１は、前述の切り出した文字列Ｗｏｒｄ（ｉ）に対して、正の索引ｊで検索可能か否かを判定する（ステップＳ１８０６）。検索可能と判定した場合は（ステップＳ１８０６：ＹＥＳ）、ステップＳ１８０７に移行する。なお、正の索引ｊの添え字として用いるｊには、世代を表す「０〜Ｎ」を代入する。以後の負の世代ｊまたは削除レコード表ｊについても同様である。
【０１４５】
また、ステップＳ１８０６において、位置シフト累算部１７０２は、位置シフト累算集合の値を算出する。また、この際、負索引・削除レコード表解釈部１７０３は、索引検索部１７０１により検索された文字列Ｗｏｒｄ（ｉ）が、一時負集合に登録されている負の索引の要素と同じ文字出現位置、または削除レコード表の要素を持つレコードであるか否かを判定する。
【０１４６】
また、ステップＳ１８０６において、負索引・削除レコード表解釈部１７０３は、検索された文字列Ｗｏｒｄ（ｉ）が、一時負集合に登録されている負の索引の要素と同じ文字出現位置、または削除レコード表の要素を持つレコードに該当する場合、その位置では検索対象としないものとして処理を行い、一時負集合から該当要素である文字列Ｗｏｒｄ（ｉ）を削除する。この結果として、検索可能な正の索引の要素が存在するか否かにより次の処理として、ステップＳ１８０７に移行するか、ステップＳ１８０８に移行するかを決定する。
【０１４７】
索引検索部１７０１は、累積結果集合の各要素ｓと、前述の索引検索処理により求まった正の索引の要素集合の要素ｐに対し、出現位置が連接するか判定し、連接する要素ｐについては、位置シフト累算集合の要素ｅ（ｐ）に位置シフト値を合算する。また、索引検索部１７０１は、ｊ＝＝０である初期索引の場合であり、かつ、連接するｐが存在しない場合、累積結果集合から要素ｓを削除する（ステップＳ１８０７）。
【０１４８】
次に、位置シフト累算部１７０２は、一時負集合に負の索引ｊ及び削除レコード表ｊの集合を一時負集合に累積して格納する（ステップＳ１８０８）。なお、ステップＳ１８０６において、検索可能な正の索引の要素が存在しない場合（ステップＳ１８０６：ＮＯ）、位置シフト累算部１７０２によりステップＳ１８０８の処理を行うように遷移する。
【０１４９】
また、ステップＳ１８０５において、０＜＝ｊの条件が成立しなくなると（ステップＳ１８０５：ＮＯ）、文書ＤＢ検索装置１０４は、累積結果集合が空集合か否かを判定し（ステップＳ１８０９）、空集合なら検索結果が無いとして（ステップＳ１８０９：ＹＥＳ）、結果レコード集合を返し、検索処理を終了する（ステップＳ１８１０）。
【０１５０】
また、文書ＤＢ検索装置１０４は、空集合で無い場合は（ステップＳ１８０９：ＮＯ）、次の切出し文字列について、これまでと同様に、ステップＳ１８０４〜ステップＳ１８０９の処理を行う。また、文書ＤＢ検索装置１０４は、全ての切出し文字列についてステップＳ１８０４〜ステップＳ１８０９の処理を繰り返し行い、求まった累積結果集合を結果集合として、検索結果出力部１０７に出力する。
【０１５１】
このような検索処理により、文書ＤＢ更新処理装置１０２において複数世代に渡る更新処理により作成された文書ＤＢを効率よく検索することができる。
【０１５２】
次に、文字列検索処理の具体例について、図１９，２０を参照して説明する。
【０１５３】
図１９の例では、“Ｈ社”という検索文字列１９０１の入力に対して、索引検索部１７０１は、世代０の文書ＤＢ１９０２の初期索引１９０２ａから“Ｈ社  （１，７，０）”という文字列１９０３の切り出しを行う（ステップＳ１９１０）。
【０１５４】
次に、索引検索部１７０１は、更新情報（世代０→１）１９０４の正の索引１９０４ａを検索して“Ｈ社”がヒットしないため（ステップＳ１９１１）、次に、負の索引１９０４ｂを検索して（ステップＳ１９１２）、“Ｈ社  （１，７，０）”がヒットしたため、これを累積負集合Ｂ１９０５に登録する（ステップＳ１９１３）。
【０１５５】
次に、索引検索部１７０１は、初期索引１９０２ａから検索した文字列１９０３である“Ｈ社”は、出現位置７番目でヒットするが、累積負集合Ｂ１９０５に同じ出現位置でヒットするものが存在するため、この位置では“Ｈ社”はヒットしない。すなわち、図中に示す初期索引１９０２ａから切り出した文字列１９０３は、累積負集合１９０５から削除されて（ステップＳ１９１４）、その結果集合φ１９０６が出力される。
【０１５６】
次に、図２０の例では、図１９の世代０の文書ＤＢ１９０２に対して、“ＭＥＩ社とＳＯ社が”という検索文字列２００１が入力された場合の検索処理の例を示している。
【０１５７】
まず、索引検索部１７０１は、検索文字列２００１を、“ＭＥＩ社”、“と”、“ＳＯ社”、“が”というように文字列の切出しを行う。
【０１５８】
次に、索引検索部１７０１は、図１９の例と同様に、正の索引１９０４ａを検索して（ステップＳ２０１０）、“ＭＥＩ社”、と、“ＳＯ社”が出現するため、これらを累積結果集合（図示せず）に格納する。
【０１５９】
次に、索引検索部１７０１は、負の索引１９０４ｂの全要素を累積負集合（図示せず）に格納する（ステップＳ２０１１）。その後、索引検索部１７０１は、世代０の初期索引１９０２ａを検索し（ステップＳ２０１２）、累積負集合に登録された要素と、初期索引１９０２ａに登録された要素とで、同じ文字列でかつ、同じ出現位置のものを検索対象からは省き、その上で、世代０でヒットする文字列を探す。
【０１６０】
この場合、まず、初期索引１９０２ａには“ＭＥＩ社”は存在しないため、累積結果集合は、正の索引１９０４ａでヒットした“ＭＥＩ社  （１，４，２）”の先頭位置「４」が記録され、その位置シフト値である「２」が位置シフト累算集合に記録される。
【０１６１】
次に、索引検索部１７０１は、検索文字列から切り出した文字列“と”については、正の索引１９０４ａでは検索されず、負の索引１９０４ｂにも記録されないため、世代０の初期索引１９０２ａの検索時に初めて“と  （１，６，０）”がヒットする。次に、累積結果集合に保存されている唯一つの“ＭＥＩ社”と連接するかどうかを判定するに当たり、“と”の出現位置「６」に、位置シフト累算集合に記録した位置シフト値「２」を加算した上で、連接を判定する。
【０１６２】
この処理により、図中２００２で示すように、“と”の出現位置は「８」となり、“ＭＥＩ社”の出現位置が「４」でその文字列長が「４」であるため、出現位置的に連接すると判定することで、この位置は累積結果集合に残る。
【０１６３】
また、切り出し文字列“が”についても同様に検索処理を行い、その出現位置と位置シフト値を加算して、正の索引１９０４ａでヒットした“ＳＯ社”との連接を判定することで、その位置は累積結果集合に残る。
【０１６４】
このように、切出された文字列毎に処理を繰り返すことによって、最終的に、この文書ＩＤが「１」の出現文字位置が「４」である部分でヒットするように検索することができる。
【０１６５】
したがって、本実施の形態の文書ＤＢ検索装置１０４による検索処理では、従来の検索処理に加え、更新情報を解釈する処理が発生するが、この処理は、文字列の出現位置集合に対する加減算の演算だけで処理できるため、検索処理速度の低下は無く、また、変更の無い文字列の検索処理については、従来の索引を用いて検索すればよいため、検索速度が低下しない。
【産業上の利用可能性】
【０１６６】
本発明の文書データベース更新処理装置、文書データベース検索装置、文書データベース索引作成方法及び文書データベース検索方法は、世代管理型文書データベースの更新情報量を削減し、文字列検索の効率化を図ることができるため、文書データベース処理システム等に適用することが可能である。
【図面の簡単な説明】
【０１６７】
【図１】本発明の実施の形態に係る文書データベース処理システムの構成を示すブロック図
【図２】本実施の形態に係る世代１の文書ＤＢを作成する文書ＤＢ更新処理装置の構成を示すブロック図
【図３】本実施の形態に係る（ａ）は更新前の文書ＤＢの例を示す図、（ｂ）は更新用文書の例を示す図、（ｃ）は更新後の文書ＤＢの例を示す図
【図４】本実施の形態に係る更新前の文書ＤＢの索引例を示す図
【図５】本実施の形態に係る（ａ）は更新後の文書ＤＢの正の索引例を示す図、（ｂ）は更新後の文書ＤＢの負の索引例を示す図
【図６】本実施の形態に係る更新後の文書ＤＢの削除レコード表の例を示す図
【図７】本実施の形態に係る更新情報作成処理を示すフローチャート
【図８】本実施の形態に係る世代０から世代１、世代２以降の更新情報を作成する文書ＤＢ更新処理装置の構成を示すブロック図
【図９】本実施の形態に係る（ａ）は世代０の文書ＤＢの例を示す図、（ｂ）は世代１の更新文書ＤＢの例を示す図、（ｃ）は世代２の更新文書ＤＢの例を示す図
【図１０】本実施の形態に係る（ａ）は更新用文書の例を示す図、（ｂ）は他の更新用文書の例を示す図
【図１１】本実施の形態に係る世代０の文書ＤＢの例を示す図
【図１２】本実施の形態に係る（ａ）は世代０→１の更新情報の例を示す図、（ｂ）は世代１→２の更新情報の例を示す図
【図１３】本実施の形態に係る複数更新情報解釈処理を示すフローチャート
【図１４】本実施の形態に係る更新情報マージ処理を実行する文書ＤＢ更新処理装置の構成を示すブロック図
【図１５】本実施の形態に係る更新情報マージ処理を示すフローチャート
【図１６】本実施の形態に係る更新情報マージ処理により作成した世代０→２の更新情報の例を示す図
【図１７】本実施の形態に係る文書ＤＢ検索装置の構成を示すブロック図
【図１８】本実施の形態に係る文書ＤＢ検索処理を示すフローチャート
【図１９】本実施の形態に係る文字列検索処理の具体例を示す図
【図２０】本実施の形態に係るその他の文字列検索処理の具体例を示す図
【図２１】従来の文書ＤＢ管理システムの構成を示すブロック図
【図２２】従来の更新後の文書ＤＢの索引例を示す図
【符号の説明】
【０１６８】
１００  文書データベース処理システム
１０１  文書入力装置
１０２  文書ＤＢ更新処理装置
１０３  文書ＤＢ保持装置
１０３ａ  世代０の文書ＤＢ
１０３ｂ  世代０→１の更新情報
１０３ｃ  世代Ｎ−２→Ｎ−１の更新情報
１０３ｄ  世代Ｎ−１→Ｎの更新情報
１０４  文書ＤＢ検索装置
１０５  検索キーワード入力部
１０６  文書ＤＢ検索部
１０７  検索結果出力部
１０８、１１０  主記憶装置
１１０  補助記憶装置
２０１  更新文書判定部
２０２  正の索引作成部
２０３  負の索引作成部
２０４  文書ＤＢ更新処理部
２０５  削除レコード表作成部
２０６  索引作成部
８０１  複数更新情報解釈部
１４０１  更新情報マージ処理部
１４０２  更新情報削除部
１７０１  索引検索部
１７０２  位置シフト累算部
１７０３  負索引・削除レコード表解釈部
【図１】
2006185368.tif 000003
【図２】
2006185368.tif 000004
【図３】
2006185368.tif 000005
【図４】
2006185368.tif 000006
【図５】
2006185368.tif 000007
【図６】
2006185368.tif 000008
【図７】
2006185368.tif 000009
【図８】
2006185368.tif 000010
【図９】
2006185368.tif 000011
【図１０】
2006185368.tif 000012
【図１１】
2006185368.tif 000013
【図１２】
2006185368.tif 000014
【図１３】
2006185368.tif 000015
【図１４】
2006185368.tif 000016
【図１５】
2006185368.tif 000017
【図１６】
2006185368.tif 000018
【図１７】
2006185368.tif 000019
【図１８】
2006185368.tif 000020
【図１９】
2006185368.tif 000021
【図２０】
2006185368.tif 000022
【図２１】
2006185368.tif 000023
【図２２】
2006185368.tif 000024