(57)【要約】【課題】本発明は、検索文字数の制限、処理の遅延化、インデックスデータベースの肥大化を改善したＮグラムによる全文検索システムを提供する。【解決手段】テキスト情報の１文字以上の分割文字列から生成されるハッシュキー、インデックスデータベースの中で分割文字列を先頭に有するデータのアドレスを示すハッシュ値を有するハッシュテーブルと、分割文字列にテキスト情報における後続文字を１文字以上付加した付加文字列、付加文字列の出現位置を含むインデックスデータベースとを生成するインデクサ部２、ハッシュキーに対応するハッシュ値を検索し、ハッシュ値が示すインデックスデータベースのアドレスデータに存在する付加文字列を検索する文字列検索部、検索対象文字列と付加文字列の同一比較を行い、かつ、付加文字列の出現位置整合演算を行う文字列比較演算部３を備えた全文検索システムを構成する。【選択図】図１
2007133682.tif 000002
【特許請求の範囲】
【請求項１】
電子ファイルから取り出されたテキスト情報をＮグラム分割し（Ｎ：Ｎ＞１の整数）、該Ｎグラムと該Ｎグラムの出現位置を含むＮグラムデータをデータベースのデータテーブルに登録し、該Ｎグラムデータテーブルを用いて、検索対象の文字列による該テキスト情報の全文検索を行う全文検索システムにおいて、
前記Ｎグラムの（Ｎ−ｎ）文字の各々から生成したハッシュキー（ｎ：Ｎ＞ｎの整数）をハッシュテーブルに登録するハッシュキー登録手段、
前記（Ｎ−ｎ）文字を含むＮグラムのＮグラムデータを前記Ｎグラムデータテーブルに登録するＮグラムデータ登録手段、
前記Ｎグラムデータを登録した前記Ｎグラムデータテーブルのアドレスを、前記ハッシュキーと関連付けてハッシュテーブルに登録するアドレス登録手段、
前記検索対象の文字列をＮグラム分割し、該検索Ｎグラムに含まれる（Ｎ−ｎ）グラムからハッシュキーを生成し、該ハッシュキーに関連する前記アドレスを、前記ハッシュテーブルから取得し、該アドレスに基づいて前記ＮグラムデータテーブルからＮグラムを検索するハッシュキー関連Ｎグラム検索手段、および、
前記検索Ｎグラムと前記ハッシュキー関連Ｎグラムとの同一性の比較を行い、かつ、該ハッシュキー関連Ｎグラムの出現位置整合演算を行う文字列比較演算手段、を備えることを特徴とする全文検索システム。
【請求項２】
前記Ｎグラムデータテーブルにおいて、同一のハッシュキーを有する前記Ｎグラムデータは、同一のブロック、または、同一のバッファに保存する請求項１に記載の全文検索システム。
【請求項３】
前記ハッシュテーブル内に、前記生成したハッシュキーが既に登録されている場合、該既登録ハッシュキーと関連付けられるアドレスに基づいて、前記Ｎグラムデータテーブルに前記Ｎグラムデータを登録すること、を備える請求項１および２に記載の全文検索システム。
【請求項４】
前記ＮグラムデータのＮグラムが、既に前記Ｎグラムデータテーブル内に登録されている場合、該既登録Ｎグラムデータに前記Ｎグラムデータの出現位置を書き込み、または、更新する請求項１〜３に記載の全文検索システム。
【請求項５】
電子ファイルから取り出されたテキスト情報をＮグラム分割し（Ｎ：Ｎ＞１の整数）、該（Ｎ−１）グラムと該（Ｎ−１）グラムの出現位置を含む（Ｎ−１）グラムデータをデータベースのデータテーブルに登録し、該（Ｎ−１）グラムデータテーブルを用いて、検索対象の文字列による該テキスト情報の全文検索を行う全文検索システムにおいて、
前記（Ｎ−１）グラムの各々から生成したハッシュキーをハッシュテーブルに登録するハッシュキー登録手段、
前記（Ｎ−１）グラムデータを前記（Ｎ−１）グラムデータテーブルに登録する（Ｎ−１）グラムデータ登録手段、
前記（Ｎ−１）グラムデータを登録した前記（Ｎ−１）グラムデータテーブルのアドレスを、前記ハッシュキーと関連付けてハッシュテーブルに登録するアドレス登録手段、
前記検索対象の文字列を（Ｎ−１）グラム分割し、該検索（Ｎ−１）グラムからハッシュキーを生成し、該ハッシュキーに関連する前記アドレスを、前記ハッシュテーブルから取得し、該アドレスに基づいて前記（Ｎ−１）グラムデータテーブルから（Ｎ−１）グラムを検索するハッシュキー関連（Ｎ−１）グラム検索手段、および、
前記検索（Ｎ−１）グラムと前記ハッシュキー関連（Ｎ−１）グラムとの同一性の比較を行い、かつ、該ハッシュキー関連（Ｎ−１）グラムの出現位置整合演算を行う文字列比較演算手段、を備えることを特徴とする全文検索システムを備える請求項１〜４に記載の全文検索システム。
【請求項６】
電子ファイルから取り出されたテキスト情報をＮグラム分割し（Ｎ：Ｎ＞１の整数）、該Ｎグラムと該Ｎグラムの出現位置を含むＮグラムデータをデータベースのデータテーブルに登録し、該Ｎグラムデータテーブルを用いて、検索対象の文字列による該テキスト情報の全文検索を行う全文検索方法において、
前記Ｎグラムの（Ｎ−ｎ）文字の各々から生成したハッシュキー（ｎ：Ｎ＞ｎの整数）をハッシュテーブルに登録するハッシュキー登録ステップ、
前記（Ｎ−ｎ）文字を含むＮグラムのＮグラムデータを前記Ｎグラムデータテーブルに登録するＮグラムデータ登録ステップ、
前記Ｎグラムデータを登録した前記Ｎグラムデータテーブルのアドレスを、前記ハッシュキーと関連付けてハッシュテーブルに登録するアドレス登録ステップ、
前記検索対象の文字列をＮグラム分割し、該検索Ｎグラムに含まれる（Ｎ−ｎ）グラムからハッシュキーを生成し、該ハッシュキーに関連する前記アドレスを、前記ハッシュテーブルから取得し、該アドレスに基づいて前記ＮグラムデータテーブルからＮグラムを検索するハッシュキー関連Ｎグラム検索ステップ、および、
前記検索Ｎグラムと前記ハッシュキー関連Ｎグラムとの同一性の比較を行い、かつ、該ハッシュキー関連Ｎグラムの出現位置整合演算を行う文字列比較演算ステップ、を有することを特徴とする全文検索方法。
【請求項７】
電子ファイルから取り出されたテキスト情報をＮグラム分割し（Ｎ：Ｎ＞１の整数）、該Ｎグラムと該Ｎグラムの出現位置を含むＮグラムデータをデータベースのデータテーブルに登録し、該Ｎグラムデータテーブルを用いて、検索対象の文字列による該テキスト情報の全文検索するため、コンピュータに、
前記Ｎグラムの（Ｎ−ｎ）文字の各々から生成したハッシュキー（ｎ：Ｎ＞ｎの整数）をハッシュテーブルに登録するハッシュキー登録手順、
前記（Ｎ−ｎ）文字を含むＮグラムのＮグラムデータを前記Ｎグラムデータテーブルに登録するＮグラムデータ登録手順、
前記Ｎグラムデータを登録した前記Ｎグラムデータテーブルのアドレスを、前記ハッシュキーと関連付けてハッシュテーブルに登録するアドレス登録手順、
前記検索対象の文字列をＮグラム分割し、該検索Ｎグラムに含まれる（Ｎ−ｎ）グラムからハッシュキーを生成し、該ハッシュキーに関連する前記アドレスを、前記ハッシュテーブルから取得し、該アドレスに基づいて前記ＮグラムデータテーブルからＮグラムを検索するハッシュキー関連Ｎグラム検索手順、および、
前記検索Ｎグラムと前記ハッシュキー関連Ｎグラムとの同一性の比較を行い、かつ、該ハッシュキー関連Ｎグラムの出現位置整合演算を行う文字列比較演算手順、を実行させるためのプログラム。
【請求項８】
前記Ｎグラムデータテーブルにおいて、同一のハッシュキーを有する前記Ｎグラムデータは、同一のブロック、または、同一のバッファに保存する手順を実行させる請求項７に記載のプログラム。
【請求項９】
前記ハッシュテーブル内に、前記生成したハッシュキーが既に登録されている場合、該既登録ハッシュキーと関連付けられるアドレスに基づいて、前記Ｎグラムデータテーブルに前記Ｎグラムデータを登録する手順を実行させる請求項７および８に記載のプログラム。
【請求項１０】
前記ＮグラムデータのＮグラムが、既に前記Ｎグラムデータテーブル内に登録されている場合、該既登録Ｎグラムデータに前記Ｎグラムデータの出現位置を書き込み、または、更新する手順を実行させる請求項７〜９に記載のプログラム。
【請求項１１】
電子ファイルから取り出されたテキスト情報をＮグラム分割し（Ｎ：Ｎ＞１の整数）、該（Ｎ−１）グラムと該（Ｎ−１）グラムの出現位置を含む（Ｎ−１）グラムデータをデータテーブルに登録し、該（Ｎ−１）グラムデータテーブルを用いて、検索対象の文字列による該テキスト情報の全文検索を行うために、コンピュータに、
前記（Ｎ−１）グラムの各々から生成したハッシュキーをハッシュテーブルに登録するハッシュキー登録手順、
前記（Ｎ−１）グラムデータを前記（Ｎ−１）グラムデータテーブルに登録する（Ｎ−１）グラムデータ登録手順、
前記（Ｎ−１）グラムデータを登録した前記（Ｎ−１）グラムデータテーブルのアドレスを、前記ハッシュキーと関連付けてハッシュテーブルに登録するアドレス登録手順、
前記検索対象の文字列を（Ｎ−１）グラム分割し、該検索（Ｎ−１）グラムからハッシュキーを生成し、該生成ハッシュキーに関連する前記アドレスを、前記ハッシュテーブルの中から検索し、該アドレスに基づいて前記（Ｎ−１）グラムデータテーブルから（Ｎ−１）グラムを検索するハッシュキー関連（Ｎ−１）グラム検索手順、および、
前記検索（Ｎ−１）グラムと前記ハッシュキー関連（Ｎ−１）グラムとの同一性の比較を行い、かつ、該ハッシュキー関連（Ｎ−１）グラムの出現位置整合演算を行う文字列比較演算手順、を実行させる請求項７〜１０に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全文検索システム、及び、その全文検索方法に関し、特に、電子化された文章情報からインデックス情報を作成し、そのインデックス情報を用いて検索対象文字列の検索を高速に行う全文検索システム、及び、その全文検索方法に関する。
【背景技術】
【０００２】
インターネットの普及により、インターネットに存在する情報量も急速に増大している。このような莫大な情報の中から、いち早く目的とする情報を探し出すための検索システムが必要不可欠となっている。また、イントラネットやローカルエリアネットワーク（ＬＡＮ）等のネットワークにおいても、ネットワークに繋がれたコンピュータに保存される情報量が増大しているため、それらの情報を、早く正確に検索するためにも検索システムが必要である。
【０００３】
検索システムは、分野を限定せず大量の情報を収集し、収集した情報をデータベース化し、それらの情報を文字列等で検索できるものである。そのような検索システムは、大きく分けてディレクトリ型とロボット型の２種類がある。ディレクトリ型検索システムは、収集情報をカテゴリー別に分類して検索する検索システムである。収集情報を階層構造で分類しており、分類階層をユーザがたどって絞り込むことで検索を行うものである。しかし、収録データの選定および階層構造の分類作業等を人間が行っているため、検索対象の情報量において、後述するロボット型検索システムに劣っている。そのため、ディレクトリ型検索システムは、インターネットポータルサイトに一部使用されるのみで、現在、検索システムの殆どは、ロボット型である。
【０００４】
ロボット型検索システムは、インターネットのＷｅｂページ全体、または、ネットワークに接続されたコンピュータに保存される電子ファイル（ハイパーテキストやソフトウェアで読取可能なテキスト情報）全体を検索対象とすることから、全文検索システムとも呼ばれる。
【０００５】
ここでいう、全文検索システムには、全文検索を行うためのコンピュータ・ハードウェアおよびコンピュータ上で起動するソフトウェア全てが含まれる。そして、クライアント・コンピュータ上に検索画面を表示させ、検索を受け付けおよび検索結果を出力する検索サービスのためのソフトウェア、全文検索を行うために予め作成するインデックスデータベース、そのインデックスデータベース作成のためのソフトウェア（インデクサ）なども含む。
【０００６】
全文検索システムには、大きく分けて２つの機能から構成される。１つは検索サービスを始める前に実行する機能で、インデクサによるインデックスデータベース生成（インデクシング）である。もう１つは、インデックスデータベースで作成されたデータを利用し、検索対象の入力を受け付け、検索結果を出力する検索サービスである。
【０００７】
さらに、インターネットやコンピュータ上に保存された情報は、英語のみならず、日本語、中国語等の言語で書かれており、我が国においては、日本語を対照に検索できる検索システムは重要である。しかし、日本語文章の全文検索においては、インデックス生成において特有の問題がある。この問題は、日本語文章は、英語のように分かち書き（単語毎に区切って記述すること）文法で文章が記述されていないため、日本語文章のインデックス生成においては、検索対象の文章に対して単語の分割処理を行う必要があることである。
【０００８】
日本語のような、分かち書きされていない文章の単語分け方法の１つに、形態素解析がある。形態素解析とは、文法を意識して文字列を単語に分割し、分割した文字列に対して、名詞、動詞、助詞といった文法要素の並びを理解し、文法要素毎に文字列を分けていく方法である。この方法は、日本語本来の単語に分解するため、うまく分解できれば、単語レベルでの検索には最も適している。形態素解析の例として、例えば、「台風２０号が北上中です」という文章に対して形態素解析を行うと、「台風」、「２０」、「号」、「が」、「北上中」、「です」というように、文章が文法要素に従った単語毎に区切られる。
【０００９】
しかし、コンピュータで日本語を入力する際に、仮名漢字変換を使っていると誤った単語の区切り方をすることがよくあるのと同じように、文書を記述した人が望んだとおりに文章が分割できないことがある。文法要素毎に文字列を正しく分割できなかった場合は、正しい単語での登録が行われなくなるので、検索を行ったときに検索対象が見つからないという検索精度の低下という問題が発生する。
【００１０】
このような問題を生じない別の単語分け方法に、Ｎグラムがある。Ｎグラムとは、テキスト情報（文章、特定の画像に記述したり、関連づける語句、またはそれらの組み合わせ）から、文字の並びを例えば、１文字（１グラム）、２文字（２グラム）、３文字（３グラム）というように取り出して、その取り出した文字の出現位置を計算して、その言語の特質を記述するものである。Ｎグラムは、日本語の文法を特に意識せず、ある特定の文字数で日本語を分解し、それをとりあえず単語としてインデックスに登録してしまう方法である。ＮグラムのＮは分割する文字数を示す。Ｎを１としたものを１グラムといい、これは、１文字ごとに分割することを示す。１文字毎に分解すると、文字列中の各１文字が単語として認識されるため、たった１文字でも検索できるようになる。１グラムの単語分けの例として、例えば、「台風２０号が北上中です」という文章に対して１グラム単語分けを行うと、「台」、「風」、「２」、「０」、「号」、「が」、「北」、「上」、「中」、「で」、「す」というように、文章が１文字毎に区切られる。
【００１１】
１グラムにおいて、「２０号」という文字を検索する場合、「２」、「０」、「号」という文字を検出し、それらが互いに隣りあっていれば、つまり、区切られた各文字の出現位置が検索文字の出現位置と同じであれば、「２０号」という文字を含む言葉が正確に検出されたことになる。このように、Ｎグラムによる検索は、区切られた文字データと共に文字の連続性情報をデータベースで管理することで、どのような文字列でも検索を可能にする検索方法である。
【００１２】
また、２グラムの場合では、テキスト情報を２文字ずつに区切って登録する。例えば「台風２０号が北上中です」という文章に対して２グラム解析を行うと、「台風」、「風２」、「２０」、「０号」、「号が」、「が北」、「北上」、「上中」「中で」、「です」というふうに文章が２文字毎に区切られる。この２グラムデータに対して、「２０号」という文字を検索すると、「２０」と「０号」という２グラムデータが検索され、互いの出現位置が正しい場合、つまり、上記の例では、「２０」と「０号」のテキスト情報内での出現位置が１つだけ異なるときは、「２０号」が検出されたと判定される。
【００１３】
Ｎグラムでは、Ｎより小さい文字列の検索は行えず、また、Ｎより大きい文字列の場合は、文字列の長さをＬとすると、[（Ｌ＋Ｎ−１）／Ｎ］の式で表される回数の検索を行い、かつ、出現位置が検索文字列と一致しているかを判断することで、検出を行っている。なお、ここで［ｘ］は、ｘを超えない最大の整数を意味している。従って、[（Ｌ＋Ｎ−１）／Ｎ］式で表されるように、Ｎの数が大きくなればなる程、検索回数は減少する。
【００１４】
また、上述した全文検索システムは、よく知られている（例えば、非特許文献１を参照。）。例えば、全文検索システムの機能構成、ならびに、日本語処理に必要な単語分けの詳細が開示されている。
【００１５】
【非特許文献１】リチャード・セルツァー等著、干場  信之等訳「ＡＬＴＡ  ＶＩＳＴＡ完全活用ガイド」Ｐ２６０〜Ｐ２９６、翔泳社、１９９７年１１月２５日発行。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
上述のように、従来の全文検索システムは、検索精度を上げるためにＮグラムによって、全文検索を行っている。しかし、ＮグラムのＮの数によって、検索文字数の制限、処理の遅延化、インデックスデータベースの肥大化という問題がある。
【００１７】
Ｎグラムの検索の回数を減らすためには、Ｎを大きくすれば良いが、Ｎを大きくすると、Ｎより小さい文字列の検索ができなり、検索文字数の制限が生じる。そのため、検索可能な文字列の最小文字数とＮが等しくなるように、Ｎグラムデータベースを持つ必要がある。
【００１８】
また、Ｎを小さくし過ぎると、検索処理が遅延化する。上述の例を用いて説明すると、３文字の検索を行う際、２グラムデータベースでは、３文字中の前２文字と後２文字（例えば、前２文字は「２０」、後２文字は「０号」）の２回のインデックスデータベース検索を行い、検索した２文字の出現位置情報の整合処理を行う必要がある。一方、３グラムデータベースでは、検索文字数と、インデックスデータベースに登録されている単語の文字数が同一であるため（検索文字列は「２０号」、インデックスデータベースに登録されている文字列も「２０号」）１回のインデックスデータベース検索で検索が終了し、出現位置情報整合処理は発生しない。
【００１９】
そのため、複数のＮグラムデータベースを持つことによって、出現位置の整合処理を減らす試みが、行われている。例えば、２グラムと、３グラムのインデックスデータベースを切り分けて使用するものである。検索文字数が２文字の検索は、２グラムデータベース、３文字以上の検索は、３グラムデータベースで検索を行うことで、検索システム全体としての検索時間を減らすことが可能である。しかし、この方法では、検索システムに、異なるＮの数だけインデックスデータベースを備える必要があり、そのデータベース容量をＮの異なる数だけ用意する必要がある。
【課題を解決するための手段】
【００２０】
以上の課題を解決するために、本発明による全文検索システムでは、電子ファイルから取り出されたテキスト情報をＮグラム分割し（Ｎ：Ｎ＞１の整数）、ＮグラムとＮグラムの出現位置を含むＮグラムデータをデータベースのデータテーブルに登録し、Ｎグラムデータテーブルを用いて、検索対象の文字列によるテキスト情報の全文検索を行う全文検索システムにおいて、Ｎグラムの（Ｎ−ｎ）文字の各々から生成したハッシュキー（ｎ：Ｎ＞ｎの整数）をハッシュテーブルに登録するハッシュキー登録手段、（Ｎ−ｎ）文字を含むＮグラムのＮグラムデータをＮグラムデータテーブルに登録するＮグラムデータ登録手段、Ｎグラムデータを登録したＮグラムデータテーブルのアドレスを、ハッシュキーと関連付けてハッシュテーブルに登録するアドレス登録手段、検索対象の文字列をＮグラム分割し、検索Ｎグラムに含まれる（Ｎ−ｎ）グラムからハッシュキーを生成し、ハッシュキーに関連するアドレスを、ハッシュテーブルから取得し、アドレスに基づいてＮグラムデータテーブルからＮグラムを検索するハッシュキー関連Ｎグラム検索手段、および、検索Ｎグラムとハッシュキー関連Ｎグラムとの同一性の比較を行い、かつ、ハッシュキー関連Ｎグラムの出現位置整合演算を行う文字列比較演算手段、を備えた。
【００２１】
上述のハッシュキー登録手段と、Ｎグラムデータ登録手段と、アドレス登録手段は、インデクサによって実行される。
【００２２】
また、電子ファイルから取り出されたテキスト情報をＮグラム分割し（Ｎ：Ｎ＞１の整数）、ＮグラムとＮグラムの出現位置を含むＮグラムデータをデータテーブルに登録し、Ｎグラムデータテーブルを用いて、検索対象の文字列によるテキスト情報の全文検索を行う全文検索方法において、Ｎグラムの（Ｎ−ｎ）文字の各々から生成したハッシュキー（ｎ：Ｎ＞ｎの整数）をハッシュテーブルに登録するハッシュキー登録ステップ、（Ｎ−ｎ）文字を含むＮグラムのＮグラムデータをＮグラムデータテーブルに登録するＮグラムデータ登録ステップ、Ｎグラムデータを登録したＮグラムデータテーブルのアドレスを、ハッシュキーと関連付けてハッシュテーブルに登録するアドレス登録ステップ、検索対象の文字列をＮグラム分割し、検索Ｎグラムに含まれる（Ｎ−ｎ）グラムからハッシュキーを生成し、ハッシュキーに関連するアドレスを、ハッシュテーブルから取得し、アドレスに基づいてＮグラムデータテーブルからＮグラムを検索するハッシュキー関連Ｎグラム検索ステップ、および、検索Ｎグラムとハッシュキー関連Ｎグラムとの同一性の比較を行い、かつ、ハッシュキー関連Ｎグラムの出現位置整合演算を行う文字列比較演算ステップ、を有する全文検索方法とした。
【発明の効果】
【００２３】
本発明は、検索文字列から生成されるハッシュキー、その検索文字列を含む文字列データを有するインデックスデータベース内のアドレスデータからなるハッシュテーブル、および、検索文字列を先頭に含む文字列データと、その文字列データの出現位置を有するインデックスデータベースにより、全文検索処理の高速化を可能とするものである。
【発明を実施するための最良の形態】
【００２４】
本発明による全文検索システムに係る実施形態について、添付図面を参照して詳述する。以下では、その実施形態を、全文検索システムの実施例として説明する。
【実施例】
【００２５】
図１は、本発明に係る全文検索システムにおける機能の概略構成例を示す。この全文検索システムは、情報収集部１、インデクサ２、文字列比較演算部３、検索結果表示部４、ハッシュテーブルＨＴ、ＮグラムデータテーブルＤＴ、ハッシュテーブルＨＴとＮグラムデータテーブルＤＴを管理するインデックスデータベースＤＢを有し、さらに、検索文字列設定部ａ、を備えている。なお、ハッシュテーブルＤＴは、インデックスデータベースＤＢ外部に配置しても良く、例えば、外部のアプリケーション内で起動され、インデックスデータベースＤＢと相互通信しても良い。
【００２６】
情報収集部１は、無線、有線（電線、光ケーブル）等の公知のネットワークに繋がったコンピュータ上の電子ファイルから電子化されたテキスト情報を収集する。
【００２７】
インデクサ部２は、情報収集部１が収集したテキスト情報をＮグラムに分割し、ハッシュテーブルＨＴに、Ｎグラムデータの先頭（Ｎ−ｎ）文字からハッシュキー（ハッシュ法によりデータベースレコードの検索を高速に行なうためのキー）を生成し、登録する。次に、インデクサ部２は、ＮグラムデータをＮグラムデータテーブルＤＴに登録し、登録したＮグラムデータテーブルＤＴのアドレスデータを、ハッシュテーブルＨＴのハッシュ値として登録する。このようにして、ハッシュキーとハッシュ値はペアで登録され、ハッシュキーを参照することで、ハッシュ値で示されるアドレスのレコードに直接アクセスすることができる。従って、ハッシュテーブルＨＴによって、ハッシュキーに相当する（Ｎ−ｎ）文字は、ＮグラムデータテーブルＤＴのＮグラムデータと関係付けられる。
【００２８】
さらに、インデクサ部２は、ＮグラムデータテーブルＤＴに、Ｎグラムデータの出現位置情報を登録する。
【００２９】
文字列比較演算部３は、検索対象となった文字列をＮグラムデータに分割し、その分割Ｎグラムデータの先頭（Ｎ−ｎ）文字を用いてハッシュキーを計算し、そのハッシュキーによりハッシュテーブルＨＴからハッシュ値であるＮグラムデータのＮグラムデータテーブルＤＴ内アドレスを取得する。文字列比較演算部３は、取得したアドレスを用いて、Ｎグラムデータと出現位置を取得する。さらに、検索対象文字列を分割したＮグラムデータと、ＮグラムデータテーブルＤＴから検索したＮグラムデータの同一性を比較し、さらに、Ｎグラムデータの出現位置情報からそれらの整合性を判断し、適切な検索対象文字列の出現位置（ファイルパスもしくはＵＲＬ等）を取得する。
【００３０】
検索結果表示部４は、文字列比較演算部３によって検索された文字列を表示部（示されない）と出現位置を表示する。なおこの場合、検索文字列の出現位置に加えて、「単語の重要度」によって、表示順序が決められて表示される。表示方法は、公知の全文検索システムと同じである。
【００３１】
図２は、本発明の一実施例としてインデクサ部２によるインデックスデータベースＤＢの２グラムのハッシュテーブルＨＴおよび３グラムのＮグラムデータテーブルＤＴ生成処理の概要を示す。図２に示すテキスト情報（ａ）は、電子ファイルのテキスト情報の例であり、所定の出現位置を有している。２グラムデータ（ｂ）は、テキスト情報（ｂ）を２グラムに分割したデータであり、ハッシュキーに対応する２グラムデータである。ハッシュテーブルＨＴは、ハッシュキーとハッシュ値から構成されるテーブルである。ＮグラムデータテーブルＤＴ（ｃ）は、インデックスデータベースＤＢ内において、３グラムと出現位置の関係を定義したテーブルである。
【００３２】
図２を参照して、インデクサ部２によるハッシュテーブルＨＴへのハッシュキー生成処理について、さらに詳細に説明する。インデクサ部２は、情報収集部１が収集した電子化テキスト情報を、１文字ずつずらしながら３グラムに分割し、さらに、その３グラム文字の先頭２文字（２文字のユニコードからなる４バイトデータ）を使って、２バイトのハッシュキーを生成し、予めエントリが用意されているハッシュテーブルＨＴに登録する。このハッシュキーは、２グラムデータに対して良い分散が得られるように生成されることが望ましく、公知の生成方法が適用可能である。本実施例においては、２グラムデータのユニコード２文字それぞれの下位８ビットを使って２バイトのハッシュキーを生成している。
【００３３】
図２のテキスト情報（ａ）として、“／Ａｆｉｌｅ／Ａ．ｔｘｔ”というファイルに保存されている（出現位置を有する）「私は会社へ」と、“／Ｂｆｉｌｅ／Ｂ．ｔｘｔ”というファイルに保存されている「私の会社で」と、“／Ｃｆｉｌｅ／Ｃ．ｔｘｔ”というファイルに保存されている「私の会議」がある。インデクサ部２は、テキスト情報（ａ）を、それぞれ１文字ずつずらしながら３グラムを生成し、それら３グラムの先頭２文字を使って、「私は」、「は会」、「会社」、「社へ」という２グラムデータ（ｂ）と、「私の」、「の会」、「会社」、「社で」という２グラムデータ（ｂ）と、「私の」、「の会」、「会議」という２グラムデータ（ｂ）に分割する。
【００３４】
インデクサ部２は、２グラムデータ（ｂ）から、２バイトデータのハッシュキーを生成する。例えば、「私は」という２グラムデータは、「1000」というハッシュキーを生成し、生成したハッシュキーがハッシュテーブルＨＴに存在しない場合は、新規にハッシュキーをハッシュテーブルＨＴに登録する。同じテキスト情報（ａ）に重複して出現した「会社」という２グラムデータ（ｂ）は、複数あるため、１つのハッシュキー「9881」しか生成されない。
【００３５】
なお、本発明の実施例においては、ハッシュテーブルＨＴは、予め用意されており、６５，５３６（２の１６乗）のデータエントリ数を有する。日本語の場合、一般に使用する文字は５０００文字程度である。２文字の場合は、１０万種類程度になる。それを２バイトデータ（２の１６乗＝６５，５３６）で表示する。ハッシュテーブルのエントリ数は、複数の検索文字列が１つのハッシュキーに集中しないように考慮された数値であり、そのため、エントリ数は、対象となる言語、発生する文字種類数、検索文字列の文字列数から適宜変更する必要がある。
【００３６】
インデクサ部２は、ハッシュキー生成後、ハッシュテーブルＨＴにおいて、そのハッシュキーが新規な場合は、新３グラムとして上述の分割した３グラムおよびその関連情報をＮグラムデータテーブルＤＴに登録する。登録したデータベースのアドレスを、ハッシュテーブルＨＴのハッシュ値としてハッシュテーブルに登録する。このようにして、ハッシュキーとハッシュ値がハッシュテーブルＨＴ内でペアとなるため、後述する全文検索処理において、ハッシュキーをハッシュテーブルＨＴで参照することで、そのハッシュキーの元となった２文字を先頭に有する３グラムのデータを、ＮグラムデータテーブルＤＴに直接的にアクセス可能となる。
【００３７】
インデクサ部２は、ハッシュキー生成後、ハッシュテーブルＨＴにおいて、そのハッシュキーが新規で無い場合は、既に存在するハッシュキーとペアを組むハッシュ値（アドレス）を参照して、ＮグラムデータテーブルＤＴを検索し、ハッシュキー作成の元となった３グラムが、ＮグラムデータテーブルＤＴ内に既に存在するか否かの判断を行う。３グラムが未登録の場合は、参照したアドレスが示すデータブロックに、新規３グラムとしてレコードを書き込む。３グラムが既登録の場合は、その３グラムの出現位置のみを登録する。
【００３８】
例えば、「私は会社へ」とういテキスト情報（ａ）から、分割された「私は」という２グラムデータは、「1000」というハッシュキーを生成し、「1000」がハッシュテーブルＨＴに既に存在する場合は、そのハッシュキー「1000」とペアを組むハッシュ値「0x188」が示すインデックスデータベースＤＢ内のＮグラムデータテーブルＤＴのアドレスに、「私は会」という３グラムが存在するか否かを判断し、未登録の場合は、「私は会」という新３グラム及びその関連情報を登録する。既登録の場合は、出現位置のみが登録される。
【００３９】
例えば、図２のテキスト情報（ａ）の「私の会社で」から分割される「私の会」と、テキスト情報（ａ）の「私の会議」から分割される「私の会」は同じ３グラムであるが、出現位置が異なる。従って、ＮグラムデータテーブルＤＴ（ｃ）では、同じ１つの３グラム「私の会」に複数の出現位置「／Ｂｆｉｌｅ／Ｂ．ｔｘｔ．１」と、「／Ｃｆｉｌｅ／Ｃ．ｔｘ．１」を有することになる。
【００４０】
図２において、２グラム「会社」は、ハッシュキー生成時は重複したため、１つのハッシュキーしか生成されなかったが、３グラムとしては、「会社へ」と「会社で」とは異なるため、ＮグラムデータテーブルＤＴに独自レコードとして保存される。
【００４１】
同一のハッシュキーを有するデータは、まず、同一のブロックに書き込まれる。もしブロックが同一ハッシュキーを有する他の３グラムで一杯の場合は、異なるブロックに書き込む。追加データが異なるブロックに書き込まれた場合は、その追加データの検索が可能なように、異なるブロックに存在し、かつ、同一ハッシュキーを有するデータのチェーン列に、追加データが保存されたブロックのアドレスデータを書き込む。
【００４２】
このようにして、同一のハッシュキーを有する３グラムのデータがインデックスデータベース内にブロック化して登録されることとなる。これは、後の全文検索時に、同一のハッシュキーを有するデータをブロック単位で一括読出す場合のハードディスクやバッファメモリに対するＩ/Ｏ数を減らす。これにより、ハッシュ値で示されたＮグラムデータテーブルＤＴ内のアドレスを検索することで、ブロック化／バッファリング化された同一のハッシュキーを有する３グラムのデータを一括で取得することが可能となる。また、ハードディスクのシークタイムを減らすために、新規ブロックは、同一ハッシュキーを有するブロックに隣接するように設けても良い。
【００４３】
図２のＮグラムデータテーブルＤＴ（ｃ）の３グラム「会社へ」と「会社で」は、同じハッシュキーを有するが、同一のブロックに書き込めなかった場合を示している。レコード「会社へ」のチェーン列に、レコード「会社で」のアドレスが記載されているため、チェーン列を追うことで、同一ハッシュ値を有する３グラム検索を可能にしている。
【００４４】
３グラムは、一般に、複数の電子ファイルに存在するため、１つの３グラムは、複数の出現位置を有する。例えば、３文字データの出現位置（上記例では「私の会」に相当する）を、ＮグラムデータテーブルＤＴの情報として格納する。ＮグラムデータテーブルＤＴ（ｃ）の出現位置列により、「私の会」という３グラムが、「／Ｂｆｉｌｅ／Ｂ．ｔｘｔ．１」と、「／Ｃｆｉｌｅ／Ｃ．ｔｘ．１」というファイルにあることがわかる。なお、ここで、示す“１”は、「私の会」の先頭の文字がテキスト情報（ａ）の１番目に位置することを示す。
【００４５】
また、３グラムの関連情報は、「出現位置」に加えて、「単語に関する情報」、「単語の重要度」、「単語そのもののイメージ」、「ファイル（ＵＲＬ）に関する情報」、「ファイル名（ＵＲＬ）」、「ファイル作成日時（最終更新日時）」、「ファイルの所有者」、「ファイルのサイズ」、「収集日時」、「タイトル」、「概要」等の情報があり、ＮグラムデータテーブルＤＴに格納され得る。
【００４６】
上記のＮグラム以外の情報は、Ｎグラムと比較して膨大な数となる。そのため、出現位置等の位置情報は、Ｎグラムデータテーブルと異なる別テーブルで管理し、Ｎグラムデータテーブルには、そのＮグラムデータ毎の位置情報リスト（別テーブルで管理される位置情報が保存されるアドレス）だけを持たせても良い。
【００４７】
文字列設定部ａから入力された文字列は、文字列比較演算部３によって、まず、３グラムに分割される。文字列比較演算部３は、ハッシュテーブルＨＴから、分割した３グラムの先頭２文字からハッシュキーを計算し、その２文字を先頭に有する３グラムのアドレスを示すハッシュ値を取得する。
【００４８】
文字列比較演算部３は、ハッシュ値で示されたアドレスから、検索対象文字列の３グラムの先頭２文字から生成するハッシュキーを有する３グラムの全関連情報（出現位置等）を取得する。例えば、「私は会社へ」を検索対象文字列とする場合、「会社へ」の先頭２文字「会社」からハッシュキーを計算し、そのハッシュキーに対応するハッシュ値を取得し、「会社」から生成した同一のハッシュキーを有する全３グラム「会社へ」および「会社で」が検索される。
【００４９】
次に、文字列比較演算部３は、検索対象文字列から分割した３グラムと、検索された３グラムとの同一性を検査する。例えば、検索対象文字列の３グラムの一部「会社へ」と、同一のハッシュキーを有する３グラム「会社へ」および「会社で」の同一性を判断する。この場合、検索された３グラム「会社で」は、検索文字列の一部「会社へ」と同一ではないため、３グラム「会社で」のデータは、破棄される。
【００５０】
本実施例においては、ハッシュキーは、ユニコード下位８文字を利用して生成するため、同一のハッシュキーを有する３グラムは、常にその先頭２文字が共通するとは限らない。従って、検索文字列とＤＢから取得した３グラムの比較は、３文字全てに行う必要がある。
【００５１】
さらに、文字列比較演算部３は、検索した文字列の出現位置の整合性を計算する。例えば、「私は会」と「会社へ」が同じファイルもしくはＵＲＬに存在し、その文字の出現位置が２だけ異なるか否かについて計算し、正しければ、それらの文字列から得られる検索情報を、正しい検索情報としてメモリ等に保存する。
【００５２】
このように、本実施例においては、「私は会社へ」というデータを２グラムデータベースでは、「私は」、「会社」、「社へ」の３回の検索が必要なところを、３グラムデータベースのように、「私は会」、「会社へ」という２組の３文字列データとしてＮグラム検索が行えることがわかる。
【００５３】
また、本実施例において、２文字検索を行う場合は、その２文字からハッシュキーを生成し、ハッシュ値で示される３グラムデータのチェーンをたどりながら、３グラムの先頭２文字を探す。これは、通常の２グラムエンジンでは、１つの２グラムデータだけ見つかれば終わる処理であるが、本実施例では、該当するデータレコードは、複数存在する可能性がある。そのため、３グラムデータのチェーンはコード順にソートされており、連続して見付かるようになっている。従って、通常の２グラムエンジンの処理と殆ど変わらない処理速度で、２文字の検索が可能である。
【００５４】
以上に説明された本発明に係る全文検索システムに関するインデックス生成処理の一例を、図３のフローチャートにより説明する。
【００５５】
図３に示されるように、フローチャートでは、まず、ステップＳ１０１において、情報収集部１は、インターネットまたはＬＡＮ（ローカルエリアネットワーク）上のコンピュータに保存された電子化ファイルからテキスト情報を取得する。次いで、ステップＳ１０２に進む。
【００５６】
ステップＳ１０２では、情報収集部１が取得した情報を元に、インデクサ２は、テキスト情報を１文字ずらしながら３グラム及びその関連情報を生成し、その３グラムの先頭２文字を使って、ハッシュキーを生成する。次に、ステップＳ１０３に進む。
【００５７】
ステップＳ１０３では、生成したハッシュキーが既にハッシュテーブルＨＴに存在するか否かの判断処理を行う。そして、ハッシュキーが存在する場合は、ステップＳ１０５に進み、ハッシュキーが存在しない場合は、ステップＳ１０４に進む。
【００５８】
ステップＳ１０４では、インデクサ２は、ハッシュテーブルＨＴに新たなハッシュキーを加える。次に、ステップＳ１０５に進む。
【００５９】
ステップＳ１０５では、インデクサ２は、３グラムが既にＮグラムデータテーブルＤＴに存在するか否かの判断処理を行う。新ハッシュキーの場合は、ＮグラムデータテーブルＤＴに同一ハッシュキーを有する３グラムデータは存在しないことを意味するため、新３グラムデータの登録のため、ステップＳ１０６に進む。新ハッシュキーで無い場合は、そのハッシュキーとペアを組むハッシュ値を使って、ＮグラムデータテーブルＤＴに登録されている３グラムデータを検索する。インデクサ２は、このアドレスで示された３グラムをまず検索し、次に、当該３グラムがアドレスに存在しない場合は、そのアドレスに存在するデータのチェーン列で示された同一ハッシュキーを有する他の３グラムを検索する。検索した結果、同一のハッシュキーを有する３グラムがＮグラムデータテーブルＤＴ内に存在しない場合は、ステップＳ１０６に進む。同一のハッシュキーを有する他の３グラムが存在する場合は、ステップＳ１０７に進む。
【００６０】
ステップＳ１０６では、インデクサ２は、新３グラムデータを３グラムデータテーブルＤＴに登録する。新３グラムデータが、新ハッシュキーに基づくものである場合は、登録したＮグラムデータテーブルＤＴ内のアドレスを、対応する新ハッシュキーのハッシュ値としてハッシュテーブルＨＴに登録する。次に、ステップＳ１０７に進む。
【００６１】
ステップＳ１０７では、インデクサ２は、登録する３グラムに関連する出現位置等の位置情報をＮグラムデータテーブルＤＴに登録する。
【００６２】
ステップＳ１０８では、登録した３グラムデータが、ステップＳ１０１で取得したテキスト情報の最終文字列か否かの判断処理を行う。最終文字列の場合は、そのテキスト情報に関するインデックス生成処理は終了し、最終文字列ではない場合は、ステップＳ１０２に戻り、再度インデックス生成処理を繰り返す。
【００６３】
図４に、本発明に係る全文検索システムに関する全文検索処理の一例を、フローチャートにより説明する。
【００６４】
図４に示されるように、フローチャートでは、まず、ステップＳ２０１において、全文検索システムのユーザから、検索文字列設定部ａでの入力データにより、検索対象文字列が設定される。次に、ステップＳ２０２に進む。
【００６５】
Ｓ２０２では、文字列比較演算部３が、入力された検索文字列を３グラムに分割し、その分割データの先頭２文字からハッシュキーを計算し、ハッシュテーブルＨＴから、そのハッシュキーに対応するハッシュ値であるアドレスを取得する。次に、ステップＳ２０３に進む。
【００６６】
Ｓ２０３では、文字列比較演算部３は、ＮグラムデータテーブルＤＴにおいて、ハッシュ値で示されるアドレスを検索する。そのアドレス、または、検索データのチェーン列で示すアドレスから、該当する複数の３グラムデータの情報（３グラム、出現位置等）を一括取得する。次に、ステップＳ２０４に進む。
【００６７】
ステップＳ２０４では、文字列比較演算部３は、ＮグラムデータテーブルＤＴから一括取得した複数の３グラムが、検索対象文字列から分割した３グラムと一致するか否かを判断する。一致しない場合、Ｓ２０７に進み、一致する場合、ステップＳ２０５に進む。なお、位置情報をＮグラムデータテーブルＤＴの別テーブルで定義し、Ｎグラムとその位置情報に関するリストだけをＮグラムデータテーブルとして場合は、ステップＳ２０４では、グラム（文字列）情報だけの整合を行う。
【００６８】
ステップＳ２０５では、検索された複数の３グラムの出現位置に基づいて、各３グラムの出現位置が連続性を持つか否かが判断される。出現位置の連続性が無い３グラムは、ステップＳ２０７に進み、出現位置の連続性が有る３グラムは、ステップＳ２０６に進む。
【００６９】
ステップＳ２０６では、検索文字列の分割文字列が、最終分割文字列か否かを判断する。最終分割文字列の場合、ステップＳ２０８に進み、最終分割文字列ではない場合、ステップＳ２０２に戻り、ステップＳ２０６において、分割文字列が最終分割文字列と判断されるまで、上述の処理が繰り返される。
【００７０】
ステップＳ２０７では、ＤＢから取得した３グラムデータ、および／または、出現位置の連続性の無い３グラムデータが破棄される。
【００７１】
ステップＳ２０８では、検索対象文字列が、出現位置連続性の有る３グラムデータから得られる出現位置情報等と共に検索結果として画面表示され、全文検索処理が終了する。
【００７２】
図６は、本発明に係る全文検索システムのハードウェア構成例を示す図である。図１の全文検索システムは、例えば、図６に示すようなコンピュータ１０により実行される。コンピュータ１０は、必要な処理を実行するＣＰＵ１１、処理された結果を格納するメモリ１２（例えば、ＲＡＭ（Random Access Memory））、ディスプレイ１３、例えば、キーボードやマウスのような入力装置１４、ハードディスク１５等を備える。
【００７３】
全文検索処理を実行するプログラム（データ）は、記録媒体に保存され、ＣＤ／ＤＶＤドライブ１７等からローディングされ、もしくは、他のコンピュータ１９からネットワーク１６を介してダウンロードされ、ＣＰＵ１１の制御によって、コンピュータ１０のハードディスク１５に保存される。次に、プログラムを実行するために、ＣＰＵ１１の制御によって、メモリ１２に格納され、更に、ＣＰＵ１１の制御によってＣＰＵ１１に送られ、そこで、プログラムは、ＣＰＵ１１で実行および処理される。また、図１に示される、情報収集部１、インデクサ２、文字列比較演算部３、検索結果表示部４の各処理は、ＣＰＵ１１で実行される。
【００７４】
検索文字列設定部ａの設定画面、および、検索結果表示部４による検索結果表示画面は、ディスプレイ１３に画面表示され、検索文字列設定部ａの設定情報は入力装置１４によって入力される。
【００７５】
インデックス生成処理においては、ＣＰＵ１１上で実行される情報収集部１は、インターネットやＬＡＮ上に接続されたコンピュータ上の電子ファイルからテキスト情報をメモリ１２に格納する。
【００７６】
次に、ＣＰＵ１１上で実行されるインデクサ２は、メモリ１２に格納されたテキスト情報から、メモリ上に用意されたハッシュテーブルＨＴに、ハッシュキーを生成する。さらに、ＣＰＵ１１は、ハードディスク上のインデックスデータベースＤＢ内のハッシュ値で示されたＮグラムデータテーブルＤＴのアドレスデータに３グラムやその出現位置情報等の情報を生成する。
【００７７】
全文検索処理においては、ＣＰＵ１１は、入力装置１４を介して入力された検索文字列は、ＣＰＵ１１によって、メモリに格納される。メモリ格納された検索文字列は、文字列比較演算部３によって、３グラムの文字列に分割され、さらに３グラムの先頭２グラムを用いて、メモリに格納されているハッシュテーブルＨＴにあるハッシュ値を用いて、ハードディスク内のＮグラムデータテーブルＤＴの該当アドレスにアクセスする。なお、ハードディスクに保存されたＮグラムデータテーブルＤＴに問い合わせが発行されると、ハードディスク上のＮグラムデータテーブルＤＴから取得されたデータブロックはメモリ（バッファ・キャッシュ）に保持される。次回に同じ問い合わせが発生すると、ＣＰＵ１１は、まずバッファ・キャッシュを先に探し、存在しない場合にハードディスク上のＮグラムデータテーブルＤＴにアクセスする。一般に、ＮグラムデータテーブルＤＴのバッファ・キャッシュ上の存在確率は、ＮグラムデータテーブルＤＴに対して相対的にメモリ容量が大きければ大きいほど高い。従って、メモリがＮグラムデータテーブルＤＴに対して十分に大きい場合は、ＮグラムデータテーブルＤＴをメモリ上に全て格納しても良い。さらに、ＮグラムデータテーブルＤＴ内では、位置情報がその多くを占めるため、検索速度を向上するために、位置情報を別テーブルで定義し、Ｎグラムとその位置情報に関するリストだけをＮグラムデータテーブルとしても良い。
【００７８】
本発明によれば、同一のハッシュキーを有する３グラムデータは、同一のブロック、または、同一のバッファにキャッシュされている。また、同一ハッシュキーを有する３グラムデータが非常に多い場合は、複数のブロックに跨る場合がある。その場合も、ＮグラムデータテーブルＤＴ内のチェーン列によって、同一ハッシュキーを有する３グラムデータのアドレスは定義され、線形検索とは異なる直接的な検索が可能である。そのため、高速問い合わせ処理が可能である。
【００７９】
検索された３グラムは、文字列比較演算部３によって、メモリ１１に保存された検索対象文字列の分割文字列との同一性の判断がされる。同一性が無い場合は、メモリ１１から破棄される。ＣＰＵ１１上で実行する文字列比較演算部３は、同一性があった検索された３グラムデータに対して、出現位置整合処理を行う。出現位置整合の取れないデータは、メモリ１１から破棄され、出現位置整合の取れたデータは、ディスプレイ１３を介してその文字列の出現位置と共に出力される。
【００８０】
また、本発明に係る全文検索システムの起動や、アクセスは、入力装置１４からの起動の他に、ＣＰＵ１１で実行中の他プログラムから起動し、回線１６に接続された他コンピュータ１９から起動し、或いは、他コンピュータ１９内の実行中のプログラムから起動されるようにしても良い。さらに、ハッシュテーブルＤＴは、インデックスデータベースＤＢの管理外として、同じコンピュータ１０内、または、他のコンピュータ１９に存在する外部のアプリケーションで起動されていても良い。
【００８１】
以上説明したように、本発明においては、全文検索システムにより、最小検索文字列が２グラムでありながら、３グラム専用の全文検索システムと同様の検索処理速度の提供を可能にしている。また、これは、ハッシュテーブルＨＴで、２グラムのインデックス情報を有し、ＮグラムデータテーブルＤＴで、３グラムの出現位置等を有することにより実現したものである。
【００８２】
しかし、これは、３グラムのハッシュテーブル内のインデックス情報と、４グラムのＮグラムデータテーブルＤＴの出現位置においても、各々で管理する文字列の数が異なるだけでその原理は同じである。その場合、種類の異なる３文字の組み合わせに対応するハッシュテーブルが必要となるため、２文字のハッシュテーブルよりもハッシュテーブルのエントリ数が増加する点が相違する。この場合、２グラムハッシュテーブルと２グラムインデックスデータベース、および、３グラムハッシュテーブルと４グラムデータベースの組合せで、２、３、４グラムデータベースを有する場合と同じ処理速度でありながら、２、４グラムデータベースの容量で実現が可能である。
【００８３】
さらに、２グラムハッシュテーブルと３グラムインデックスデータベース、および、１グラムハッシュテーブルと１グラムデータベースの組合せで、１、２、３グラムデータベースを有する場合と同じ処理速度でありながら、１、３グラムデータベースの容量で実現が可能である。
【００８４】
なお、同一のＮグラムで構成されるハッシュテーブルとインデックスデータベースにおいても上述された本発明の実施例が適用される。例えば、１文字のユニコードの下位８ビットで生成されるハッシュキーでハッシュテーブルが構成される。全文検索処理においては、ハッシュテーブルＨＴを介して、ＮグラムデータテーブルＤＴ内の１グラムを検索するため、検索処理が高速化される。また、文字列比較演算処理においては、検索対象文字列の文字数と、インデックスデータベースから検索された文字の文字数は同一であるが、両文字列はハッシュキーで関係付けられているため、上述の実施例と同様に同一性の検証が必要である。
【図面の簡単な説明】
【００８５】
【図１】本発明に係る全文検索システムにおける機能の概略構成例を示す図である。
【図２】インデクサ部２によるハッシュテーブルおよびＮグラムデータテーブルＤＴのＮグラムデータテーブル生成処理の概要を示す図である。
【図３】発明に係る全文検索システムにおけるインデックス生成処理の例を示す図である。
【図４】本発明に係る全文検索システムに関する全文検索処理の一例を示す図である。
【図５】本発明に係る全文検索システムのハードウェア構成例を示す図である。
【符号の説明】
【００８６】
１    情報収集部
２    インデクサ部
３    文字列比較演算部
４    検索結果表示部
１０    コンピュータ
１１    ＣＰＵ
１２    メモリ
１３    ディスプレイ
１４    入力装置
１５    ハードディスク
１６    回線
１７    ＣＤ／ＤＶＤドライブ
１９    他のコンピュータ
【図１】
2007133682.tif 000003
【図２】
2007133682.tif 000004
【図３】
2007133682.tif 000005
【図４】
2007133682.tif 000006
【図５】
2007133682.tif 000007