(57)【要約】【課題】表記のゆれなどにより異なる長さの文字列を同一の索引語として扱う場合でも、データ量の増加をできるだけ抑えながら、元文書内での文字列の出現場所を正しく求められるデータベースマネジメントシステムを提供する。【解決手段】文書を管理する文書データベースと、索引語が含まれている前記文書中の位置情報を管理する索引データベースを有するデータベースマネジメントシステムであって、前記文書データベースへは読み込んだ文書を元文書として登録する。また、前記索引データベースへは、該元文書中の代表索引語を用いて正規化した文書（正規化文書という）での位置と、元文書での位置との対応表を作成し、前記正規化文書から取り出されたすべての索引語に対して、前記対応表を参照して、該索引語が検出された開始位置と終了位置を元文書での開始位置と終了位置へ変換した索引を作成し、該索引の転置索引を作成して記憶させるようにした。【選択図】図１
2006031243.tif 000002
【特許請求の範囲】
【請求項１】
索引語が含まれている文書中の位置情報を管理する索引データベースを有するデータベースマネジメントシステムにおいて、該索引データベースは、長さの異なる複数の索引語を一つの代表索引語で表し、この代表索引語のそれぞれに対して、該代表索引語に代表されたそれぞれの索引語のいずれかを含む文書のリストを対応させ、該文書リスト中の文書それぞれに対して、文書中に該索引語が出現する、開始位置と終了位置とからなる出現場所を対応させて記憶し、文書に最初に現れる索引語の開始位置は先頭からの文字数で表し、二つ目以降に現れる索引語の開始位置はその索引語の一つ前に現れる索引語の開始位置との文字数の差分で表し、終了位置は前記索引語の文字数で表すことを特徴とするデータベースマネジメントシステム。
【請求項２】
請求項１に記載のデータベースマネジメントシステムにおいて、文書に最初に現れる索引語の開始位置は先頭からの文字数で表し、二つ目以降に現れる索引語の開始位置はその索引語の一つ前に現れる索引語の終了位置との文字数の差分で表し、終了位置は前記索引語の文字数で表すことを特徴とするデータベースマネジメントシステム。
【請求項３】
請求項１または２に記載のデータベースマネジメントシステムにおいて、前記終了位置を、代表索引語の文字数と各索引語の文字数の差分で表すことを特徴とするデータベースマネジメントシステム。
【請求項４】
請求項１、２または３に記載のデータベースマネジメントシステムにおいて、開始位置と終了位置とを、文字数の代わりにバイト数で表すことを特徴とするデータベースマネジメントシステム。
【請求項５】
請求項１乃至４のいずれかに記載のデータベースマネジメントシステムにおいて、索引語に、任意の長さを持つ文字列あるいはビット列を用いることを特徴とするデータベースマネジメントシステム。
【請求項６】
文書を管理する文書データベースと、索引語が含まれている前記文書中の位置情報を管理する索引データベースを有するデータベースマネジメントシステムにおいて、読み込んだ文書を元文書として前記文書データベースへ登録する入力手段と、該元文書中の代表索引語を用いて正規化した文書（正規化文書という）での位置と、元文書での位置との対応表を作成する正規化手段と、前記正規化文書から取り出されたすべての索引語に対して、前記対応表を参照して、該索引語が検出された開始位置と終了位置を元文書での開始位置と終了位置へ変換した索引を作成し、該索引の転置索引を作成して前記索引データベースへ記憶させる索引作成手段とを備えることを特徴とするデータベースマネジメントシステム。
【請求項７】
文書を管理する文書データベースと、索引語が含まれている前記文書中の位置情報を管理する索引データベースを有してデータベースを管理するデータベース管理方法であって、読み込んだ文書を元文書として前記文書データベースへ登録する入力ステップと、該元文書中の代表索引語を用いて正規化した文書（正規化文書という）での位置と、元文書での位置との対応表を作成する正規化ステップと、前記正規化文書から取り出されたすべての索引語に対して、前記対応表を参照して、該索引語が検出された開始位置と終了位置を元文書での開始位置と終了位置へ変換した索引を作成し、該索引の転置索引を作成して前記索引データベースへ記憶させる索引作成ステップとを備えることを特徴とするデータベース管理方法。
【請求項８】
コンピュータに、請求項６に記載のデータベースマネジメントシステムの機能を実行させるためのプログラム。
【請求項９】
請求項８に記載のプログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースマネジメントシステム、データベース管理方法、プログラムおよび記録媒体に関し、より詳細には、データベースに登録された文書に含まれる索引語の位置を管理するデータベースマネジメントシステム、データベース管理方法、プログラムおよび記録媒体に関する。
【背景技術】
【０００２】
登録された文書群から必要な文書を検索する文書検索方法には、単語単位の検索（以下、単語単位検索）と文字列単位の検索（以下、文字列単位検索）の２つの方法がある。
【０００３】
単語単位検索では、ユーザが指定した検索文字列を単語として含む文書を検索する。単語単位検索を高速化する方法としては、文書中の単語を索引単位として、索引単位ごとに出現した文書識別子と文書内での出現場所を記録する単語索引を用意しておく方法が知られている。
【０００４】
この単語単位検索の場合、日本語においては単語の区切れが明示的に示されないため、索引を作成する際に形態素解析などを施して単語を切り出す必要があるが、現在の技術レベルでは形態素解析の誤りが避けられない。
したがって、形態素解析誤りが原因で検索漏れが起こる。例えば、「東京都にある清水寺」（ひがしきょうとにあるきよみずでら）という文書を登録する際、
／東／京都／に／ある／清水寺／
と形態素解析されるべきところを
／東京／都／に／ある／清水／寺／
のように誤って解析されれば、検索文字列が「京都」のときに「東京都にある清水寺」という文書を検索することができない。
【０００５】
このような問題点を解決するために、文字列単位検索では、ユーザが指定した検索文字列を文字列として含む文書を検索する。この文字列単位検索を高速化する方法としては、文書中のｎ文字組（以下、ｎ−ｇｒａｍ）を索引単位として、索引単位ごとに出現した文書識別子と文書内での出現場所を記録するｎ−ｇｒａｍ索引を用意しておく方法が知られている。
【０００６】
しかし、文字列単位検索の場合、単語境界を無視して検索するため、ユーザが意図しない文書が検索結果に含まれることがある。例えば、２−ｇｒａｍ索引で「帯電」（電気を帯びること）を検索文字列とした場合に、「携帯電話」という文字列を含む文書も検索されてしまう。
【０００７】
これを解決するために、特許文献１の技術では、文字ごとにその文字が出現する文書、その文書における出現場所、および各出現場所が単語の先頭あるいは末尾かのフラグを記録しておく。検索時には文字ごとの出現場所に基づいて文字列単位の検索を実現するとともに、単語の先頭あるいは末尾かのフラグも参照することにより単語単位の検索も実現できる。
【０００８】
しかし、特許文献１の技術は、文字列単位の検索が文字索引に基づいているので、ｎ−ｇｒａｍ索引と比較して検索速度が遅いという問題がある。
また、単語の切れ目を発見するための形態素解析系（あるいはそれが使用する辞書）を更新した場合、切れ目の位置が変わるため、索引全体の作り直しが必要となり、その結果、索引のメンテナンス作業に多大な時間を要することになる。
【０００９】
そこで、特許文献２の技術では、登録文書中のｎ−ｇｒａｍに関する出現情報をｎ−ｇｒａｍごとに保持するｎ−ｇｒａｍ索引と、登録文書中の単語境界に関する出現情報を圧縮して記録する単語境界位置索引とを保持しておき、登録文書あるいは検索文字列であるテキストをｎ−ｇｒａｍおよび単語に分割し、この分割結果に基づいて前記ｎ−ｇｒａｍ索引を参照して検索文字列を含む文書あるいはその文書における出現場所を検索し、この検索結果に対し検索文字列を単語に分割した結果に基づいて前記単語境界位置索引を参照して検索文字列が単語として現われているか否かを判断して、検索文字列を単語として含む文書を検索するようにしている。
【特許文献１】特開平７−８５０３３号公報
【特許文献２】特開２００３−５８５７８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ところで、文書中に「データベース」という単語があり、「データーベース」という検索語で文書検索する場合について考える。
３−ｇｒａｍを使用して索引語を作成すると、「データベース」からは、「データ」、「ータベ」、「タベー」、「ベース」が索引語として得られる。また、検索語「データーベース」からは、「データ」、「ーター」、「ターベ」、「ーベー」、「ベース」が得られる。
したがって、これらの索引語のうち「データ」と「ベース」しか一致しないので、検索語「データーベース」を含む文書は検索されないことになる。
【００１１】
このように、表記にゆれがあった場合でも検索するようにするためには、文書に現れる用語および検索語の正規化を行って、正規化された文書や検索語に対してｎ−ｇｒａｍ索引を作成していた。例えば、「データーベース」を正規化して「データベース」に統一し、この「データベース」からｎ−ｇｒａｍ索引を作成する。
【００１２】
しかし、このように正規化された索引語および検索語を用いて検索したときに、その検索語が元文書中での出現場所をハイライト表示する場合には、正確な位置をハイライト表示することができないので、文字列一致などで対応箇所を確定するための後処理が必要になってくるという問題が起きる。
【００１３】
本発明は、上述のような実情を考慮してなされたものであって、表記のゆれなどにより異なる長さの文字列を同一の索引語として扱う場合でも、データ量の増加をできるだけ抑えながら、元文書内での文字列の出現場所を正しく求められるデータベースマネジメントシステム、データベース管理方法、プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記の課題を解決するために、請求項１に記載の発明は、索引語が含まれている文書中の位置情報を管理する索引データベースを有するデータベースマネジメントシステムにおいて、該索引データベースは、長さの異なる複数の索引語を一つの代表索引語で表し、この代表索引語のそれぞれに対して、該代表索引語に代表されたそれぞれの索引語のいずれかを含む文書のリストを対応させ、該文書リスト中の文書それぞれに対して、文書中に該索引語が出現する、開始位置と終了位置とからなる出現場所を対応させて記憶し、文書に最初に現れる索引語の開始位置は先頭からの文字数で表し、二つ目以降に現れる索引語の開始位置はその索引語の一つ前に現れる索引語の開始位置との文字数の差分で表し、終了位置は前記索引語の文字数で表すことを特徴とする。
【００１５】
請求項２に記載の発明は、請求項１に記載のデータベースマネジメントシステムにおいて、文書に最初に現れる索引語の開始位置は先頭からの文字数で表し、二つ目以降に現れる索引語の開始位置はその索引語の一つ前に現れる索引語の終了位置との文字数の差分で表し、終了位置は前記索引語の文字数で表すことを特徴とする。
【００１６】
請求項３に記載の発明は、請求項１または２に記載のデータベースマネジメントシステムにおいて、前記終了位置を、代表索引語の文字数と各索引語の文字数の差分で表すことを特徴とする。
【００１７】
請求項４に記載の発明は、  請求項１、２または３に記載のデータベースマネジメントシステムにおいて、開始位置と終了位置とを、文字数の代わりにバイト数で表すことを特徴とする。
【００１８】
請求項５に記載の発明は、請求項１乃至４のいずれかに記載のデータベースマネジメントシステムにおいて、索引語に、任意の長さを持つ文字列あるいはビット列を用いることを特徴とする。
【００１９】
請求項６に記載の発明は、文書を管理する文書データベースと、索引語が含まれている前記文書中の位置情報を管理する索引データベースを有するデータベースマネジメントシステムにおいて、読み込んだ文書を元文書として前記文書データベースへ登録する入力手段と、該元文書中の代表索引語を用いて正規化した文書（正規化文書という）での位置と、元文書での位置との対応表を作成する正規化手段と、前記正規化文書から取り出されたすべての索引語に対して、前記対応表を参照して、該索引語が検出された開始位置と終了位置を元文書での開始位置と終了位置へ変換した索引を作成し、該索引の転置索引を作成して前記索引データベースへ記憶させる索引作成手段とを備えることを特徴とする。
【００２０】
請求項７に記載の発明は、文書を管理する文書データベースと、索引語が含まれている前記文書中の位置情報を管理する索引データベースを有してデータベースを管理するデータベース管理方法であって、読み込んだ文書を元文書として前記文書データベースへ登録する入力ステップと、該元文書中の代表索引語を用いて正規化した文書（正規化文書という）での位置と、元文書での位置との対応表を作成する正規化ステップと、前記正規化文書から取り出されたすべての索引語に対して、前記対応表を参照して、該索引語が検出された開始位置と終了位置を元文書での開始位置と終了位置へ変換した索引を作成し、該索引の転置索引を作成して前記索引データベースへ記憶させる索引作成ステップとを備えることを特徴とする。
【００２１】
請求項８に記載の発明は、コンピュータに、請求項６に記載のデータベースマネジメントシステムの機能を実行させるためのプログラムである。
請求項９に記載の発明は、請求項８に記載のプログラムを記録したコンピュータ読取可能な記録媒体である。
【発明の効果】
【００２２】
本発明によれば、一つの索引に長さの異なる複数の索引語が対応付けられている場合でも、元文書における索引語の出現箇所を特定できるので、検索結果一覧等で検索語のハイライト表示を高速に行うことができる。
また、開始位置や終了位置をさらに小さい数値で表せるので、データ量の増加を抑えることができる。
また、マルチバイト文字コードを使って文書が作成されているときでも、検索語の出現箇所の特定にエンコードの必要がないので、検索一般を高速にすることができる。
また、任意のビット長で索引語を取り出しを行えるので、単語の切り出しをしなくとも索引の作成ができるようになり、日本語のように単語の切り出しが難しい言語においても容易に適用することができる。
【発明を実施するための最良の形態】
【００２３】
以下、図面を参照して、本発明のデータベースマネジメントシステムに係る好適な実施形態を説明する。
【００２４】
＜実施形態１＞
図１は、本発明のデータベースマネジメントシステムのシステム構成を示すブロック図であり、同図において、データベースマネジメントシステムは、構築部１、検索部２、索引データベース３および文書データベース４とからなっている。
【００２５】
構築部１は、本データベースマネジメントシステムで維持管理する文書を入力して文書データベース４へ登録する入力手段５、入力された文書の異表記の単語を正規化して正規化文書を作成する正規化手段６、入力された文書に対して索引を作成して索引データベース３へ格納する索引作成手段７を含んで構成される。
【００２６】
検索部２は、文書データベース４中の文書の検索要求を入力する入力手段５、検索要求中の検索語の異表記を正規化する正規化手段６、索引データベース３と文書データベース４を参照して、正規化された検索語の解析や索引語の探索などを行って該当する文書を検索する検索手段８、検索結果を出力する出力手段９を含んで構成される。
【００２７】
次に、図２のフローチャートを用いて、構築部１における索引の作成手順を説明する。
まず、文書を入力装置や記憶手段等を介して入力し、元文書として文書データベース４へ登録するとともに、異表記の文字列とそれらの文字列を統一した代表文字列とを対応させた異表記統一用のテーブルを予め記憶手段等へ用意しておき、このテーブルを参照して、この読み込んだ文書中の異表記の文字列を検出し、この文字列を代表文字列に置き換えることによって元文書を正規化文書として作成して一時的に記憶装置へ記憶させる（ステップＳ１）。
このとき、正規化文書の何文字目と元文書の何文字目が対応しているかを対応表として保存しておく。この対応表には、正規化文書における各文字の「文字位置」と、この文字位置の文字に対応する元文書の文字とが何文字ずれたかを示す「ずれ情報」とを対応させて記録する。
【００２８】
例えば、「データーベースにデーターを・・・」という文書の「データー」を「データ」に正規化した場合、「データベースにデータを・・・」という正規化文書が得られる。
正規化文書の「データベースに」の「ベ」は、正規化前は先頭から５文字目であったのが４文字目に変わる。同様に、「データを」の「を」は、正規化前は先頭から１３文字目であったのが１１文字目に変わる。
【００２９】
これらの文字の対応は、正規化の規則が一つ適用される毎に、正規化によって文字順が何文字ずれたかを記録しておくことで把握できる。
例えば、一つ目の「データー」を正規化したときに４文字目の「べ」以降の各文字はマイナス１文字、二つ目の「データー」を正規化したときに１１文字目の「を」以降の各文字はさらにマイナス１文字の変更があった、即ち、先頭から数えるとマイナス２文字の変更があったことを対応表に記録しておく。
【００３０】
ただし、このままであると正規化前の元文書における「データー」の後ろの「ー」に対応する文字がないため、正規化後の「データ」から正規化前の「データー」への対応もとれなくなる。そこで、正規化によってどの位置の文字が削除されたかも記録しておく。
即ち、３文字目の「タ」と、１０文字目の「タ」の直後の文字が削除されたことも記録しておく。
上記の例についてまとめると、対応表には以下の表に示した情報が記録されることになる。
【００３１】
【表１】
2006031243.tif 000003
【００３２】
次に、一時的に記憶した正規化された文書から単語を取り出し、取り出された単語を索引語にする（ステップＳ２）。
正規化文書から単語を取り出す場合、形態素解析を利用するが、形態素解析は既存の手法（例えば、松本裕治他、「単語と辞書」言語の科学第３巻、岩波書店の５３ページ以降に書かれている）を採用すればよい。
【００３３】
または、一時的に記憶した正規化文書をｎ−ｇｒａｍに分割して、分割されたｎ−ｇｒａｍを索引語とするようにしてもよい。
例えば、図３に示したように、３−ｇｒａｍで分割して、正規化文書に含まれるすべての３文字の文字列を順番に取り出して索引語とする。
【００３４】
次に、取り出したすべての索引語に対して、その索引語の一文字目が出現する位置（開始位置という）と、その索引語の最後の文字目が出現する位置（終了位置という）を検出する。ここで、出現場所は、正規化文書の先頭から数えた文字数で表すものとする。
これらの索引語、文書、および文書中での索引語の位置から、文書データベース４へ記憶した元文書の文書識別子ごとに、その正規化文書が含んでいる索引語のリストを対応させ、さらに、この索引語のリストの各索引語に正規化文書中で出現場所（開始位置と終了位置）を対応させた索引を作成する（図４参照）（ステップＳ３）。
【００３５】
次に、正規化文書での索引語の出現場所（開始位置および終了位置）をステップＳ１で作成した対応表を参照して、元文書での出現場所（開始位置および終了位置）へ変換する（ステップＳ４）。
例えば、索引語の文字列の開始位置に対する「ずれ情報」に「マイナス１文字」とあれば、正負を反転してプラス１文字すれば元文書の文字位置に戻せることを意味するので、１を加える。
また、索引語の文字列の終了位置に対する「ずれ情報」に「直後の１文字削除」とあれば、「データー」が「データ」に正規化されたことを意味するので、これにも１を加える。ここで、１を加えないと、正規化後の「データ」が対応するのは、元文書の「データ」であって「データー」ではなくなってしまうからである。
【００３６】
次に、出現場所の値を圧縮変換する（ステップＳ５）。
同じ索引語が文書中に複数個現れる場合、二つ目の出現場所を一つ目の出現場所との差分で表した方が出現場所を小さな数値で表せるので、索引のデータ量を抑えることができる。このため、次の漸化式のように、二つ目からの開始位置は一つ前の開始位置との文字数の差分で表し、終了位置は開始位置からの文字数で表して、出現場所の値を圧縮する。
【００３７】
ｓ（１）＝Ｓ（１）
ｓ（ｋ）＝Ｓ（ｋ）−Ｓ（ｋ−１）
ｅ（ｋ）＝Ｅ（ｋ）−Ｓ（ｋ）＋１
【００３８】
ここで、上記の記号は、次のことを意味している。
Ｓ（ｋ）：  ｋ番目に出現した索引語の元文書における開始位置。
Ｅ（ｋ）：  ｋ番目に出現した索引語の元文書における終了位置。
ｓ（ｋ）：  ｋ番目に出現した索引語の開始位置として索引に記録する値。
ｅ（ｋ）：  ｋ番目に出現した索引語の終了位置として索引に記録する値。
【００３９】
次に、索引語に対して、その索引語が含まれる文書の文書識別子とその文書における索引語の出現場所を素早く取り出せるデータ構造の転置索引を作成し索引データベース３へ格納する（ステップＳ６）。
例えば、転置索引は図５のようなデータ構造をしている。索引語のリストは、一般にＢ木で構成され、各索引語はその索引語を含む文書識別子のリストを持ち、さらにその文書識別子は索引語の出現場所のリストを持つように構成される。このようなデータ構造をしているので、ある索引語を含む文書ＩＤと出現場所を素早く取り出すことができる。
【００４０】
次に、図６のフローチャートを用いて、検索部２における検索手順を説明する。
まず、入力された検索要求にある検索語の異表記を、異表記統一用テーブルを参照して正規化する（ステップＳ１１）。
例えば、「データー」という文字列を「データ」に統一することで、「データー」を含む文書を「データ」を含む文書として扱えるので、検索語が「データ」の場合でも、「データー」を含む文書も検索でき、検索漏れを防止することができる。
【００４１】
次に、索引を作成したときと同様にして、正規化された検索語から単語を取り出す（ステップＳ１２）。例えば、「データベース」を「データ」と「ベース」に分割する。
次に、分割された各単語について、索引データベース３のＢ木を探索して、探索結果として索引語を得て（ステップＳ１３）、各索引語に関連付けられた文書識別子のリストを取得する（ステップＳ１４）。
【００４２】
次に、各検索語に共通する文書識別子を選択する（ステップＳ１５）。
これは、「データ」と「ベース」の片方しか含まれない文書には「データベース」は含まれないので、両方に含まれる文書識別子を選択する。
【００４３】
選択された各文書識別子に関連付けられている出現場所リストを取得し（ステップＳ１６）、索引語の隣接関係を確認する（ステップＳ１７）。
即ち、出現場所の値から各索引語の開始位置と終了位置を、以下に示す漸化式から計算して、検索語と同じ順番で隣接していることを確認する。即ち、終了位置と開始位置が隣り合っていることを確認する。
【００４４】
Ｓ（１）＝ｓ（１）
Ｓ（ｋ）＝Ｓ（ｋ−１）＋ｓ（ｋ）
Ｅ（ｋ）＝Ｓ（ｋ）＋ｅ（ｋ）−１
【００４５】
このようにすることで、「・・・したデータをベースにして・・・」という文書には、「データ」と「ベース」を含むが「データベース」は含まないことがわかる。
【００４６】
＜実施形態２＞
実施形態１では、最初に現れる索引語の開始位置だけ先頭からの文字数で表し、二つ目以降の索引語の開始位置は一つ前の開始位置との文字数の差分で表し、終了位置は開始位置からの文字差分で表していた。
本実施形態２では、開始位置が最初に現れる索引語だけ先頭からの文字数で表し、二つ目以降の索引語からは開始位置をその索引語の一つ前に現れる索引語の終了位置との文字数の差分で表し、終了位置は開始位置からの文字数の差分で表すようにした。
【００４７】
このようにすると、一つ前の索引語の開始位置に比べて、終了位置は明らかに同じか大きいため、開始位置との差分を取っていたときよりも、ｓ（ｋ）はより小さな数値となり、索引全体のデータ量も小さくすることができる。
このため、索引データベース３に記憶される出現場所は、次の漸化式で計算され、索引の作成方法および検索方法は実施形態１と同様に行える。
【００４８】
ｓ（１）＝Ｓ（１）
ｓ（ｋ）＝Ｓ（ｋ）−Ｅ（ｋ−１）
ｅ（ｋ）＝Ｅ（ｋ）−Ｓ（ｋ）＋１
【００４９】
また、検索するときには、次のように漸化式を変形して用いる。
Ｓ（１）＝ｓ（１）
Ｓ（ｋ）＝Ｅ（ｋ−１）＋ｓ（ｋ）
Ｅ（ｋ）＝Ｓ（ｋ）＋ｅ（ｋ）−１
【００５０】
＜実施形態３＞
一般に小さい値で表せるほどデータ量も小さくすることができる。これらの数値の分布に偏りが見られる場合、圧縮アルゴリズムを使って、データ量をさらに減らすことができる。例えば、同一意味であるが異表記の文字列である索引語を正規化した索引語（代表索引語という）で表した場合、代表索引語の長さと異表記の各索引語の長さの差分で終了位置を表した場合、値は０の近くに集まることが予想される。
【００５１】
このような場合、終了位置の値には正負が出てくるので、正を奇数に、負を偶数にマッピングしてから、Exponential Golomb符号化（小さい正の整数を少ないデータ量で表すことができる符号化である）を利用する。
また、代表索引語を、索引語群の中で最も長いか、あるいは短い索引語とすることで、終了位置の値を正か負のいずれかにすることができる。負であれば、正負を反転させることによってExponential Golomb符号化を利用することができる。
【００５２】
本実施形態３では、最初に現れる索引語の開始位置だけ先頭からの文字数で表し、二つ目以降の索引語の開始位置は一つ前の開始位置との文字数の差分で表し、終了位置は代表索引語の文字数と各索引語の文字数の差分で表すようにした。
この場合の索引データベース３に記憶される出現場所は、次のような漸化式で計算され、索引の作成方法および検索方法は実施形態１と同様に行える。
【００５３】
ｓ（１）＝Ｓ（１）
ｓ（ｋ）＝Ｓ（ｋ）−Ｅ（ｋ−１）
ｅ（ｋ）＝（Ｅ（ｋ）−Ｓ（ｋ）＋１）−Ｎ
ここで、Ｎは、正規化された索引語の文字数を表す。
【００５４】
また、検索するときには、次のように漸化式を変形して用いる。
Ｓ（１）＝ｓ（１）
Ｓ（ｋ）＝Ｓ（ｋ−１）＋ｓ（ｋ）
Ｅ（ｋ）＝Ｓ（ｋ）＋Ｎ−１＋ｅ（ｋ）
【００５５】
このように、正規化されなかった単語や、正規化によって長さが変わらなかった単語はｅ（ｋ）＝０になるので、このような単語が多ければ、ｅ（ｋ）は平均的に小さい数値となり、索引全体のデータ量も小さくすることができる。
【００５６】
上述した実施形態では、文書の内容をテキスト形式の文字列として説明してきたが、画像データ等の数値列やビット列などであっても同様に扱うことができる。
また、索引語としては、固定長の文字列に限らず、任意の長さの文字列、数値列、ビット列のいずれであってもよい。
さらに、出現場所を文字数で表していたが、これをバイト数やビット数で表すようにしてもよい。
【００５７】
さらに、本発明は上述した実施形態のみに限定されたものではない。上述した実施形態のデータベースマネジメントシステムを構成する各機能をそれぞれプログラム化し、あらかじめＣＤ−ＲＯＭ等の記録媒体に書き込んでおき、このＣＤ−ＲＯＭをＣＤ−ＲＯＭドライブのような媒体駆動装置を搭載したコンピュータに装着して、これらのプログラムをコンピュータのメモリあるいは記憶装置に格納して、実行することによって、本発明の目的を達成することができる。
【００５８】
なお、記録媒体としては半導体媒体（例えば、ＲＯＭ、不揮発性メモリカード等）、光媒体（例えば、ＤＶＤ、ＭＯ、ＭＤ、ＣＤ−Ｒ等）、磁気媒体（例えば、磁気テープ、フレキシブルディスク等）のいずれであってもよい。
【００５９】
また、ロードしたプログラムの指示に基づき、オペレーティングシステムやアプリケーションプログラム等が実際の処理の一部または全部を行い、その処理によって上述した実施形態の機能が実現される場合も含まれる。
【００６０】
また、上述したプログラムをサーバコンピュータの磁気ディスク等の記憶装置に格納しておき、ネットワークで接続された利用者のコンピュータからダウンロードして頒布する場合、また、サーバコンピュータから配信して頒布する場合、このサーバコンピュータの記憶装置も本発明の記録媒体に含まれる。
このように、本発明の機能をプログラムして、記録媒体に記録し頒布することによって、コスト、可搬性、汎用性を向上させることができる。
【図面の簡単な説明】
【００６１】
【図１】本発明のデータベースマネジメントシステムのシステム構成を示すブロック図である。
【図２】本発明のデータベースマネジメントシステムの構築部における索引の作成手順を説明するフローチャートである。
【図３】文書から３−ｇｒａｍの索引語を取り出す例である。
【図４】索引のデータ構造例である。
【図５】転置索引のデータ構造例である。
【図６】検索部における検索手順を説明するフローチャートである。
【符号の説明】
【００６２】
１…構築部、２…検索部、３…索引データベース、４…文書データベース、５…入力手段、６…正規化手段、７…索引作成手段、８…検索手段、９…出力手段。
【図１】
2006031243.tif 000004
【図２】
2006031243.tif 000005
【図３】
2006031243.tif 000006
【図４】
2006031243.tif 000007
【図５】
2006031243.tif 000008
【図６】
2006031243.tif 000009