(57)【要約】  Ｎ−ｇｒａｍ索引方式において、Ｕｎｉｃｏｄｅ等の１種の文字コードで複数の言語の文字を扱うことができる文字コードを用いた場合であっても、効率的に検索可能とすることを目的とする。文書情報におけるＮ−ｇｒａｍの位置を示す出現位置情報を、Ｎ−ｇｒａｍの種類に比べ少ない数のブロック３０５に分類して索引情報１１１を作成する。特に、各位置情報ページ３０４における各ブロック３０５のサイズが概ね等しくなるように、Ｎ−ｇｒａｍに応じて出現位置情報を格納する各ブロック３０５を割り当てる。
2011021282.tif 000002
【特許請求の範囲】
【請求項１】
文書情報における文字情報の位置を示す出現位置情報を複数のブロックに分類して記憶装置に記憶する文字情報管理装置であり、
文書情報を入力する文書入力部と、
前記文書入力部が入力した前記文書情報における所定の位置を示す出現位置情報を抽出するとともに、前記出現位置情報が示す位置における文字情報を抽出する抽出部と、
前記抽出部が抽出した前記文字情報に含まれる文字を所定の文字コードにおける値で表した場合に、前記所定の文字コードにおいて前記値との差が所定の差以内の値で表される文字を含む他の文字情報とは異なるブロックが割り当てられるように、前記抽出部が抽出した前記文字情報に割り当てるブロックを選択する選択部と、
前記記憶装置における前記選択部が選択したブロックに、前記出現位置情報を格納する格納部と
を備えることを特徴とする文字情報管理装置。
【請求項２】
前記選択部は、文字情報に割り振られる識別値であって、前記所定の文字コードにおいて隣接する文字を含む文字情報について所定の数以上離れるように割り振られる識別値を、昇順又は降順に前記所定の数ずつ前記複数のブロックの各ブロックに割り当てることにより、前記抽出部が抽出した前記文字情報に割り当てるブロックを選択する
ことを特徴とする請求項１に記載の文字情報管理装置。
【請求項３】
前記選択部は、文字情報が１文字である場合には、前記所定の文字コードにおいて前記文字情報を構成する文字を表すビット値の上位ビットと下位ビットとを入れ替えたビット値を、前記文字情報の前記識別値とする
ことを特徴とする請求項２に記載の文字情報管理装置。
【請求項４】
前記選択部は、文字情報に２文字以上の文字が含まれる場合には、前記文字情報を構成する各文字についての前記識別値の上位一部のビットを組み合わせて、前記文字情報の前記識別値とする
ことを特徴とする請求項３に記載の文字情報管理装置。
【請求項５】
前記選択部は、前記抽出部が抽出した前記文字情報が１文字である場合には、前記所定の文字コードにおいて前記文字情報を構成する文字を表す値を、ブロックの個数で割った値に応じて、前記文字情報に割り当てるブロックを選択する
ことを特徴とする請求項１に記載の文字情報管理装置。
【請求項６】
前記選択部は、前記抽出部が抽出した前記文字情報に２文字以上の文字が含まれる場合には、前記文字情報を構成する各文字について、前記所定の文字コードにおいてその文字を表すビット値の下位ビットを文字毎に異なるビットずつ上位へシフトして、前記各文字についてシフトして得たビット値を加算した値を、ブロックの個数で割った値に応じて、前記文字情報に割り当てるブロックを選択する
ことを特徴とする請求項５に記載の文字情報管理装置。
【請求項７】
前記選択部は、文字情報に含まれる文字数毎に異なるブロックになるように、前記抽出部が抽出した前記文字情報に割り当てるブロックを選択する
ことを特徴とする請求項１に記載の文字情報管理装置。
【請求項８】
前記文字情報管理装置は、さらに、
前記文字コードに定義されていない文字である拡張文字と、前記文字コードに定義された文字のうちの一部の文字とを対応付けて記憶する拡張文字記憶部を備え、
前記選択部は、前記抽出部が抽出した前記出現位置情報が示す位置における文字情報に、前記拡張文字記憶部が記憶した拡張文字と対応付けられた文字である対応文字が含まれる場合には、前記抽出部が抽出した前記文字情報に割り当てるブロックを選択するとともに、前記文字情報に含まれる前記対応文字を前記拡張文字に置き換えた文字情報についても割り当てるブロックを選択し、
前記格納部は、前記選択部が、前記抽出部が抽出した前記文字情報について選択したブロックと、前記拡張文字に置き換えた文字情報について選択したブロックとに、前記出現位置情報を格納する
ことを特徴とする請求項１に記載の文字情報管理装置。
【請求項９】
前記選択部は、同一言語における文字に対応付けられた前記拡張文字を含む複数の文字情報の各文字情報に割り当てるブロックが異なるブロックとなるように、前記拡張文字に置き換えた文字情報に割り当てるブロックを選択する
ことを特徴とする請求項８に記載の文字情報管理装置。
【請求項１０】
前記文字情報管理装置は、さらに、
前記所定の文字コードにおける一部の文字に連続した値を割り当てるとともに、前記文字コードにおける他の文字については所定の値を割り当てた中間文字コードを記憶する中間文字コード記憶部を備え、
前記選択部は、前記抽出部が抽出した前記文字情報に含まれる文字を前記中間文字コードにおける値で表した場合に、前記中間文字コードにおいて前記値との差が所定の差以内の値で表される文字を含む他の文字情報とは異なるブロックが割り当てられるように、前記抽出部が抽出した前記文字情報に割り当てるブロックを選択する
ことを特徴とする請求項１に記載の文字情報管理装置。
【請求項１１】
前記文字情報管理装置は、前記記憶装置に、前記文字コードにおける文字の種類よりも少ない数のブロックに前記出現位置情報を分類して記憶するとともに、前記ブロックの格納位置を示す管理情報を記憶する
ことを特徴とする請求項１に記載の文字情報管理装置。
【請求項１２】
前記文字情報管理装置は、さらに、
前記抽出部が抽出した前記文字情報に割り当てるブロックを選択した場合、前記文字情報を示す識別値と選択したブロックを示すブロック番号とを対応付けて記憶する対応情報記憶部と、
検索キーワードを入力する検索条件入力部とを備え、
前記選択部は、前記対応情報記憶部が、前記検索条件入力部が入力した前記検索キーワードに含まれる文字情報と対応付けて記憶したブロック番号を取得することにより、前記検索キーワードに含まれる文字情報についての出現位置情報が格納されたブロックを選択し、
前記文字情報管理装置は、さらに、
前記選択部が選択したブロックを前記記憶装置からバッファに読み出す読出部と、
前記読出部が前記バッファに読み出したブロックから、前記検索キーワードの出現位置情報を検索する検索部と
を備えることを特徴とする請求項１に記載の文字情報管理装置。
【請求項１３】
前記記憶装置には、Ｎ文字の文字情報について出現位置情報が格納され、
前記検索部は、前記検索条件入力部が入力した検索キーワードがＮ文字以上の文字情報である場合、前記検索キーワードを一部の文字に重複を許してＮ文字の文字情報に分割することにより１つ以上のＮ文字の文字情報を生成して、生成したＮ文字の文字情報の出現位置情報を検索することにより、前記検索キーワードの出現位置情報を検索する
ことを特徴とする請求項１２に記載の文字情報管理装置。
【請求項１４】
文書情報における文字情報の位置を示す出現位置情報を複数のブロックに分類して記憶する記憶装置であって、所定の文字情報に含まれる文字を所定の文字コードにおける値で表した場合に、前記所定の文字コードにおいて前記値との差が所定の差以内の値で表される文字を含む他の文字情報についての出現位置情報と、前記所定の文書情報についての出現位置情報とを異なるブロックに分類して記憶した記憶装置から検索キーワードの出現位置情報を検索する文字情報検索装置であり、
文字情報を示す識別値と選択したブロックを示すブロック番号とを対応付けて記憶した対応情報記憶部と、
検索キーワードを入力する検索条件入力部と、
前記対応情報記憶部が、前記検索条件入力部が入力した前記検索キーワードに含まれる文字情報と対応付けて記憶したブロック番号を取得することにより、前記検索キーワードに含まれる文字情報についての出現位置情報が格納されたブロックを選択する選択部と、
前記選択部が選択したブロックをバッファに読み出す読出部と、
前記読出部が前記バッファに読み出したブロックから、前記検索キーワードの出現位置情報を検索する検索部と
を備えることを特徴とする文字情報検索装置。
【請求項１５】
文書情報における文字情報の位置を示す出現位置情報を複数のブロックに分類して記憶装置に記憶する文字情報管理プログラムであり、
文書情報を入力する文書入力処理と、
前記文書入力処理で入力した前記文書情報における所定の位置を示す出現位置情報を抽出するとともに、前記出現位置情報が示す位置における文字情報を抽出する抽出処理と、
前記抽出処理で抽出した前記文字情報に含まれる文字を所定の文字コードにおける値で表した場合に、前記所定の文字コードにおいて前記値との差が所定の差以内の値で表される文字を含む他の文字情報とは異なるブロックが割り当てられるように、前記抽出処理で抽出した前記文字情報に割り当てるブロックを選択する選択処理と、
前記記憶装置における前記選択処理で選択したブロックに、前記出現位置情報を格納する格納処理と
をコンピュータに実行させることを特徴とする文字情報管理プログラム。
【請求項１６】
文書情報における文字情報の位置を示す出現位置情報を複数のブロックに分類して記憶装置に記憶する文字情報管理方法であり、
入力装置が、文書情報を入力する文書入力ステップと、
処理装置が、前記文書入力ステップで入力した前記文書情報における所定の位置を示す出現位置情報を抽出するとともに、前記出現位置情報が示す位置における文字情報を抽出する抽出ステップと、
処理装置が、前記抽出ステップで抽出した前記文字情報に含まれる文字を所定の文字コードにおける値で表した場合に、前記所定の文字コードにおいて前記値との差が所定の差以内の値で表される文字を含む他の文字情報とは異なるブロックが割り当てられるように、前記抽出ステップで抽出した前記文字情報に割り当てるブロックを選択する選択ステップと、
処理装置が、前記記憶装置における前記選択ステップで選択したブロックに、前記出現位置情報を格納する格納ステップと
を備えることを特徴とする文字情報管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば、文書情報から文字情報を検索するのに用いられる索引情報を管理する技術と、管理される索引情報を用いて文書情報から文字情報を検索する技術とに関する。
【背景技術】
【０００２】
各種文書情報や電子メール等に含まれる文字情報を検索する方式の一種として、索引情報を使った検索方式がある。索引情報を使った検索方式では、予め文書情報における文字情報の位置を示す位置情報を索引情報として保存しておき、検索時に保存した索引情報を使用することにより検索処理を高速化する。
索引情報を使った検索方式の一種として、Ｎ−ｇｒａｍ索引方式がある（特許文献１，２参照）。Ｎ−ｇｒａｍ索引方式では、文書情報における連続するＮ文字を組合せた文字情報（Ｎ−ｇｒａｍ）に対して、そのＮ−ｇｒａｍの位置を示すＮ−ｇｒａｍ位置情報を索引情報とする。ここで、Ｎは１以上の整数である。【０００３】
特許文献１には、索引情報の格納方式を工夫することにより、検索対象の文書情報の数が増加しても、検索速度が低下することを防止する方法についての記載がある。
具体的には、特許文献１では、位置情報と管理情報との２つの情報から索引情報が構成される。位置情報は、閾値以下のデータサイズの文書情報毎にページを分けて、Ｎ−ｇｒａｍ位置情報が格納された情報である。ここで、ページとは、情報の記憶単位を意味し、特許文献１では「位置情報ブロック」と呼ばれている。管理情報は、位置情報における各ページの位置を管理する情報である。この位置情報と管理情報との２つの情報から索引情報を構成することで、ブロックを読み出す際のディスク装置におけるヘッドの移動方向が一方向になるとともに、ヘッドの移動距離を短くすることができ、効率的な検索が可能となる。【０００４】
既存の文書検索装置の多くは、特定の単一の言語で記述された文書を管理の対象とした装置である。しかし、近年の情報の国際化に伴って、１台の文書検索装置によって、多言語で記述された文書を管理する必要性が高まっている。多言語の文書を管理の対象とした文書検索装置を実現する方式として、使用する文字コードをＵｎｉｃｏｄｅとする方式が考えられる（非特許文献１参照）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００３−６７４００号公報
【特許文献２】特開２００４−１９９２８２号公報
【非特許文献】
【０００６】
【非特許文献１】原田昌紀，他：“Ｕｎｉｃｏｄｅを用いたＮ−ｇｒａｍ索引の一実現方式とその評価”，情報処理学会研究報告，２０００−ＮＬ−１３６−１７，ｐｐ．１３５−１４２，２０００．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
Ｕｎｉｃｏｄｅ等の１種の文字コードで複数の言語の文字を扱うことができる文字コードを用いて、従来の検索方式における索引情報を作成した場合、検索効率が悪くなる。
この発明は、Ｎ−ｇｒａｍ索引方式において、Ｕｎｉｃｏｄｅ等の１種の文字コードで複数の言語の文字を扱うことができる文字コードを用いた場合であっても、効率的に検索可能とすることを目的とする。
【課題を解決するための手段】
【０００８】
この発明に係る文字情報管理装置は、例えば、
文書情報における文字情報の位置を示す出現位置情報を複数のブロックに分類して記憶装置に記憶する文字情報管理装置であり、
文書情報を入力する文書入力部と、
前記文書入力部が入力した前記文書情報における所定の位置を示す出現位置情報を抽出するとともに、前記出現位置情報が示す位置における文字情報を抽出する抽出部と、
前記抽出部が抽出した前記文字情報に含まれる文字を所定の文字コードにおける値で表した場合に、前記所定の文字コードにおいて前記値との差が所定の差以内の値で表される文字を含む他の文字情報とは異なるブロックが割り当てられるように、前記抽出部が抽出した前記文字情報に割り当てるブロックを選択する選択部と、
前記記憶装置における前記選択部が選択したブロックに、前記出現位置情報を格納する格納部と
を備えることを特徴とする。
【発明の効果】
【０００９】
この発明によれば、文書情報における文字情報の位置を示す出現位置情報を、効果的にブロックに分類して記憶装置に記憶することにより、Ｕｎｉｃｏｄｅ等の１種の文字コードで複数の言語の文字を扱うことができる文字コードを用いた場合であっても、効率的に検索可能にすることを特徴とする。
【図面の簡単な説明】
【００１０】
【図１】Ｕｎｉｃｏｄｅにおける文字を表す値の例を示す図。
【図２】実施の形態１に係る文書検索装置１００の機能を示す機能ブロック図。
【図３】実施の形態１に係る文書検索装置１００における索引情報１１１の構成を示す図。
【図４】図３におけるブロック３０５の構成を示す図。
【図５】索引情報１１１を作成する処理の流れを示すフローチャート。
【図６】検索キーワードを検索する処理の流れを示すフローチャート。
【図７】実施の形態１における検索キーワードと分割文字情報との一例を示す図。
【図８】単純な方法により割り当てられたＮ−ｇｒａｍ識別番号の例を示す図。
【図９】文書情報における文字の出現頻度を説明するための図。
【図１０】Ｎ−ｇｒａｍ識別番号毎のＮ−ｇｒａｍ位置情報３０６のサイズを説明するための図。
【図１１】位置情報１１３におけるブロック３０５のサイズを説明するための図。
【図１２】１−ｇｒａｍのＮ−ｇｒａｍ識別番号の算出方法を説明するための図。
【図１３】隣接する文字により構成される１−ｇｒａｍについてのＮ−ｇｒａｍ識別番号の比較図。
【図１４】２−ｇｒａｍのＮ−ｇｒａｍ識別番号の算出方法を説明するための図。
【図１５】隣接する文字を含む２−ｇｒａｍについてのＮ−ｇｒａｍ識別番号の比較図。
【図１６】３−ｇｒａｍのＮ−ｇｒａｍ識別番号の算出方法を説明するための図。
【図１７】実施の形態２における検索キーワードと分割文字情報との一例を示す図。
【図１８】１−ｇｒａｍと２−ｇｒａｍとのＮ−ｇｒａｍ位置情報３０６のサイズを説明するための図。
【図１９】実施の形態３に係るＮ−ｇｒａｍ識別番号の算出方法を説明するための図。
【図２０】実施の形態３に係るＮ−ｇｒａｍ識別番号の算出方法を説明するための図。
【図２１】実施の形態５に係る文書検索装置１００の機能を示す機能ブロック図。
【図２２】実施の形態６に係る文書検索装置１００の機能を示す機能ブロック図。
【図２３】中間文字コードを説明するための図。
【図２４】文書検索装置１００のハードウェア構成の一例を示す図。
【発明を実施するための形態】
【００１１】
以下図に基づき、この発明の実施の形態について説明する。
なお、以下の説明において、処理装置とは、後述するＣＰＵ９１１等である。また、入力装置とは、後述するキーボード９１２、通信ボード９１５等である。また、出力装置とは、後述する通信ボード９１５、ＬＣＤ９０１等である。また、記憶装置１１０とは、後述する磁気ディスク装置９２０等である。また、バッファとは、後述するＲＡＭ９１４等の比較的高速なメモリである。
【００１２】
また、以下の説明では、文字コードとしてＵｎｉｃｏｄｅを用いて説明するが、１種の文字コードで複数の言語の文字を扱うことができる文字コードであれば、他の文字コードであってもよい。
ここで、Ｕｎｉｃｏｄｅは、計算機の領域で使用される多言語の文字を、単一の文字コード体系で扱うことができるように定義された文字コードである。Ｕｎｉｃｏｄｅの文字コード空間には、約１００万種の文字が含まれ、各文字を一意に識別するために各文字に「０ｘ００」から「０ｘ１０ＦＦＦＦ」までの値が割り当てられている。なお、「０ｘ００」から「０ｘ１０ＦＦＦＦ」までは、１６進数表記である。以下「０ｘ〜」と表記した場合は、数値の１６進数表記とする。
【００１３】
図１は、Ｕｎｉｃｏｄｅにおける文字を表す値の例を示す図である。
図１に示すように、ＡＳＣＩＩ文字「ａ」には「０ｘ６１」、漢字の文字１には「０ｘ６４３Ａ」、漢字の文字２には「０ｘ５Ｅ２Ｆ」のように値が割り当てられる。
【００１４】
また、実際にＵｎｉｃｏｄｅの文字を計算機で扱う場合には、ＵＴＦ−８（Ｕｎｉｃｏｄｅ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ  Ｆｏｒｍａｔ  ８）やＵＴＦ−３２などと呼ばれる符号化がなされることが一般的であるが、符号化された状態から元のＵｎｉｃｏｄｅ空間における文字の値を導き出すことは容易である。
【００１５】
実施の形態１．
実施の形態１では、Ｕｎｉｃｏｄｅを用いた場合であっても、効率的に検索可能な文書検索装置１００（文書情報管理装置、文書情報検索装置）について説明する。
【００１６】
図２は、実施の形態１に係る文書検索装置１００の機能を示す機能ブロック図である。
文書検索装置１００は、文書入力部１０１、抽出部１０２（Ｎ−ｇｒａｍ位置情報抽出部）、選択部１０３（Ｎ−ｇｒａｍ位置情報ブロック選択部）、格納部１０４（Ｎ−ｇｒａｍ位置情報ブロック追加部）、検索条件入力部１０５、読出部１０６（Ｎ−ｇｒａｍ位置情報読出部）、検索部１０７（Ｎ−ｇｒａｍ位置情報照合部）、検索結果出力部１０８、ブロック管理テーブル１０９（Ｎ−ｇｒａｍ位置情報ブロック管理テーブル，対応情報記憶部）を備える。
また、文書検索装置１００は、記憶装置１１０とネットワークを介して接続される。記憶装置１１０には、索引情報１１１（ブロック化Ｎ−ｇｒａｍ索引情報）が記憶される。索引情報１１１は、管理情報１１２と位置情報１１３とを備える。なお、文書検索装置１００は、記憶装置１１０を内部に備える構成としてもよい。
【００１７】
文書入力部１０１、抽出部１０２、選択部１０３、格納部１０４、ブロック管理テーブル１０９は、新たな文書情報１２０についての索引情報１１１を記憶装置１１０に格納する際に機能する。
文書入力部１０１は、登録対象の文書情報１２０を入力装置により入力する。抽出部１０２は、文書入力部１０１が入力した登録対象の文書情報１２０におけるＮ−ｇｒａｍの出現位置情報を処理装置により抽出する。選択部１０３は、抽出部１０２が抽出したＮ−ｇｒａｍの出現位置情報を格納するブロック３０５（図３参照）を処理装置により選択する。また、選択部１０３は、Ｎ−ｇｒａｍと、選択したブロック３０５との対応関係を示す情報をブロック管理テーブル１０９に格納する。格納部１０４は、選択部１０３が選択した記憶装置１１０におけるブロック３０５にＮ−ｇｒａｍの出現位置情報を格納する。
【００１８】
検索条件入力部１０５、読出部１０６、検索部１０７、検索結果出力部１０８、選択部１０３、ブロック管理テーブル１０９は、索引情報１１１を用いて検索キーワードを検索する際に機能する。
検索条件入力部１０５は、検索キーワードを指定した検索条件１２１を入力装置により入力する。読出部１０６は、検索条件入力部１０５が入力した検索条件１２１により指定された検索キーワードに関連したＮ−ｇｒａｍの出現位置情報が格納されたブロック３０５を処理装置によりバッファに読み出す。この際、選択部１０３は、ブロック管理テーブル１０９に格納された情報を用いて、Ｎ−ｇｒａｍの出現位置情報が格納されたブロック３０５を特定する。検索部１０７は、読出部１０６がバッファに読み出したブロック３０５から検索条件１２１に該当する文字情報についての出現位置情報を処理装置により検索する。検索結果出力部１０８は、検索部１０７が検索した結果を検索結果情報１２２として出力装置により出力する。
【００１９】
ここでは、文書情報１２０は、文字列の情報だけを含むプレーンテキストであるとする。画像や図形などの非文字列情報と、文字列情報やその書式の情報とが混在した文書情報（ワードプロセッサや表計算アプリケーションで作成した文書情報など）を検索の対象とする場合には、別にそれらの文書情報から文字列の情報を抽出するための文字列情報抽出部を備えておくとよい。文字列情報抽出部は、文書検索装置１００が備えていてもよいし、文書検索装置１００と異なる装置が備えていてもよい。
【００２０】
図３は、実施の形態１に係る文書検索装置１００における索引情報１１１の構成を示す図である。
図３に示すように、索引情報１１１は、管理情報１１２と位置情報１１３とを備える。
位置情報１１３には、文書情報１２０における単数又は複数のＮ−ｇｒａｍ位置情報３０６（図４参照）が格納された複数のブロック３０５が、複数の位置情報ページ３０４に分割して格納される。図３においては、位置情報ページ＃１（３０４ａ）にはブロック＃１（３０５ａ）からブロック＃ＮＢ（３０５ｃ）までのＮＢ個のブロック３０５が格納され、位置情報ページ＃２（３０４ｂ）にはブロック＃１（３０５ｄ）からブロック＃ＮＢ（３０５ｅ）までのＮＢ個のブロック３０５が格納されている。なお、特許文献１に係る文書管理装置と同様に、所定の閾値以下のデータサイズの文書情報１２０毎に各位置情報ページ３０４が作成される。また、検索キーワードを検索する処理において、ブロック３０５が索引情報１１１を読み出す最小単位となる。
管理情報１１２には、位置情報１１３における各ブロック３０５に格納された文書情報１２０の数を示すブロック内文書数３０２と、各ブロック３０５の格納位置を示すブロック格納位置３０３とが格納される。図３においては、管理情報ページ＃１（３０１ａ）には、位置情報ページ＃１（３０４ａ）における全てのブロック３０５に格納された文書情報の合計数を示すブロック内文書数３０２ａと、位置情報ページ＃１（３０４ａ）におけるブロック＃１（３０５ａ）からブロック＃ＮＢ（３０５ｃ）までの各ブロック３０５の格納位置を示すブロック＃１格納位置３０３ａからブロック＃ＮＢ格納位置３０３ｃまでのブロック格納位置３０３とが格納されている。また、管理情報ページ＃２（３０１ｂ）には、位置情報ページ＃２（３０４ｂ）における全てのブロック３０５に格納された文書情報の合計数を示すブロック内文書数３０２ｂと、位置情報ページ＃２（３０４ｂ）におけるブロック＃１（３０５ｄ）からブロック＃ＮＢ（３０５ｅ）までの各ブロック３０５の格納位置を示すブロック＃１格納位置３０３ｄからブロック＃ＮＢ格納位置３０３ｅまでのブロック格納位置３０３とが格納されている。
【００２１】
図４は、図３におけるブロック３０５の構成を示す図である。
各ブロック３０５には、単数又は複数のＮ−ｇｒａｍ位置情報３０６が格納される。Ｎ−ｇｒａｍ位置情報３０６は、Ｎ−ｇｒａｍ毎に設けられ、対応するＮ−ｇｒａｍについての出現位置情報が格納される。図４においては、ブロック３０５には、Ｎ−ｇｒａｍ位置情報＃１（３０６ａ）からＮ−ｇｒａｍ位置情報＃ｎ（３０６ｃ）までのＮ−ｇｒａｍ位置情報３０６が格納されている。つまり、図４におけるブロック３０５には、Ｎ−ｇｒａｍ位置情報＃１（３０６ａ）からＮ−ｇｒａｍ位置情報＃ｎ（３０６ｃ）までのｎ個のＮ−ｇｒａｍ位置情報３０６に対応するｎ個のＮ−ｇｒａｍが割り当てられている。そして、各Ｎ−ｇｒａｍ位置情報３０６に、割り当てられたＮ−ｇｒａｍについての出現位置情報が格納される。
また、各Ｎ−ｇｒａｍ位置情報３０６には、単数又は複数の文書内位置情報３０７に分けて、割り当てられたＮ−ｇｒａｍについての出現位置情報が格納される。文書内位置情報３０７は、文書情報毎に設けられ、対応する文書情報における出現位置情報が格納される。図４においては、Ｎ−ｇｒａｍ位置情報＃１（３０６ａ）には、文書内位置情報＃１（３０７ａ）と文書内位置情報＃２（３０７ｂ）とが格納されている。つまり、図４におけるＮ−ｇｒａｍ位置情報＃１（３０６ａ）には、Ｎ−ｇｒａｍ位置情報＃１（３０６ａ）に割り当てられたＮ−ｇｒａｍについての出現位置情報であって、文書内位置情報＃１（３０７ａ）と文書内位置情報＃２（３０７ｂ）とが示す文書情報における出現位置情報が格納される。なお、１個のブロック３０５に含まれる文書内位置情報３０７の数は、ブロック内文書数３０２と等しいか、それ以下である。
また、文書内位置情報３０７には、文書番号３０８、出現回数３０９、Ｎ−ｇｒａｍ出現位置情報３１０が格納される。文書番号３０８は、その文書情報を識別するための識別情報である。出現回数３０９は、文書番号３０８が示す文書情報におけるそのＮ−ｇｒａｍが出現した回数である。Ｎ−ｇｒａｍ出現位置情報３１０は、文書番号３０８が示す文書情報におけるそのＮ−ｇｒａｍの出現位置を示す位置情報である。なお、Ｎ−ｇｒａｍ出現位置情報３１０は、文書情報の先頭からそのＮ−ｇｒａｍの先頭文字までの文字数である。Ｎ−ｇｒａｍ出現位置情報３１０は、出現回数３０９の数だけ存在する。なお、Ｎ−ｇｒａｍ出現位置情報３１０は、文書情報の先頭からそのＮ−ｇｒａｍの先頭文字までのバイト数等、そのＮ−ｇｒａｍの先頭文字の位置を示す情報であればよい。
なお、出現回数３０９が０である文書内位置情報３０７は、Ｎ−ｇｒａｍ位置情報３０６に格納しなくてもよい。
【００２２】
索引情報１１１を作成する処理と、作成された索引情報１１１を用いて指定された検索キーワードを検索する処理とを説明する。
まず、索引情報１１１を作成する処理の流れを説明する。
図５は、索引情報１１１を作成する処理の流れを示すフローチャートである。
【００２３】
（Ｓ１１）では、文書入力部１０１は、文書情報１２０を入力装置により入力する。ここで、文書入力部１０１は、文書情報１２０を識別するための文書番号を、文書情報１２０とともに入力してもよい。
【００２４】
（Ｓ１２）では、格納部１０４は、索引情報１１１の最後の管理情報ページ３０１におけるブロック内文書数３０２が閾値以下か否かを処理装置により判定する。格納部１０４は、閾値以下であると判定した場合（Ｓ１２でＹＥＳ）、処理を（Ｓ１４）へ進める。一方、格納部１０４は、閾値を越えていると判定した場合（Ｓ１２でＮＯ）、処理を（Ｓ１３）へ進める。
【００２５】
（Ｓ１３）では、格納部１０４は、新しい管理情報ページ３０１と、対応する位置情報ページ３０４とを記憶装置１１０に記憶された索引情報１１１の最後に作成する。
【００２６】
（Ｓ１４）では、抽出部１０２は、処理装置により、（Ｓ１１）で入力された文書情報１２０の先頭の位置にポインタをセットする。
【００２７】
（Ｓ１５）では、抽出部１０２は、現在ポインタがセットされている位置の位置情報を出現位置情報として処理装置により抽出する。例えば、抽出部１０２は、ポインタが文書情報１２０の先頭にセットされている場合には、１文字目を示す位置情報を出現位置情報として処理装置により抽出する。また、抽出部１０２は、抽出した出現位置情報が示す位置におけるＮ−ｇｒａｍを抽出する。なお、Ｎ−ｇｒａｍの文字数Ｎは予め指定されているものとする。例えば、文書情報１２０が“ａｂｃｄｅｆｇ”である場合に、ポインタが先頭（つまり、文字ａの位置）にある場合、抽出部１０２は、１−ｇｒａｍであれば“ａ”を抽出し、２−ｇｒａｍであれば“ａｂ”を抽出する。なお、Ｎ−ｇｒａｍの文字数Ｎは、複数の文字数が指定されていてもよい。つまり、例えば、文字数Ｎは、１文字から３文字まで（すなわち、１−ｇｒａｍ、２−ｇｒａｍ、３−ｇｒａｍ）と指定されていてもよい。Ｎ−ｇｒａｍの文字数Ｎとして複数の文字数が指定されている場合、抽出部１０２は、出現位置情報が示す位置における各文字数のＮ−ｇｒａｍを抽出する。つまり、文字数Ｎが１文字から３文字までと指定されている場合には、抽出部１０２は、出現位置情報が示す位置における１−ｇｒａｍと２−ｇｒａｍと３−ｇｒａｍとを抽出する。
【００２８】
（Ｓ１６）では、選択部１０３は、索引情報１１１の最後の位置情報ページ３０４におけるブロック３０５から、（Ｓ１５）で抽出部１０２が抽出したＮ−ｇｒａｍについて出現位置情報を格納するブロック３０５を所定の方法で処理装置により選択する。つまり、選択部１０３は、Ｎ−ｇｒａｍについて、Ｎ−ｇｒａｍ位置情報３０６を格納するブロック３０５を選択する。（Ｓ１５）で複数のＮ−ｇｒａｍが抽出されている場合には、選択部１０３は、各Ｎ−ｇｒａｍについて出現位置情報を格納するブロック３０５を選択する。なお、選択部１０３がブロック３０５を選択する方法については後述する。
また、選択部１０３は、Ｎ−ｇｒａｍとブロック番号との対応関係を示す対応情報をブロック管理テーブル１０９に記憶する。
【００２９】
（Ｓ１７）では、格納部１０４は、（Ｓ１６）で選択部１０３が選択したブロック３０５に、抽出部１０２が抽出した出現位置情報を格納する。なお、（Ｓ１５）で複数のＮ−ｇｒａｍが抽出されている場合には、格納部１０４は、各Ｎ−ｇｒａｍについて出現位置情報を格納する。
具体的には、まず、格納部１０４は、選択部１０３が選択したブロック３０５に、（Ｓ１５）で抽出部１０２が抽出したＮ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６が格納されているか否かを処理装置により判定する。
そして、格納部１０４は、Ｎ−ｇｒａｍ位置情報３０６が格納されていないと判定した場合、選択部１０３が選択したブロック３０５に（Ｓ１５）で抽出部１０２が抽出したＮ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を追加する。また、格納部１０４は、追加したＮ−ｇｒａｍ位置情報３０６に、新たな文書内位置情報３０７を追加する。そして、文書検索装置１００は、追加した文書内位置情報３０７の文書番号３０８に登録対象の文書番号を格納し、出現回数３０９に１を格納し、Ｎ−ｇｒａｍ出現位置情報３１０に出現位置情報を格納する。
一方、格納部１０４は、Ｎ−ｇｒａｍ位置情報３０６が格納されていると判定した場合、格納されているＮ−ｇｒａｍ位置情報３０６の文書内位置情報３０７に、文書情報１２０の文書番号が文書番号３０８として格納されているか否かを処理装置により判定する。
格納部１０４は、文書情報１２０の文書番号が格納されていないと判定した場合、（Ｓ１５）で抽出部１０２が抽出したＮ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６に、新たな文書内位置情報３０７を追加する。そして、文書検索装置１００は、追加した文書内位置情報３０７の文書番号３０８に登録対象の文書番号を格納し、出現回数３０９に１を格納し、Ｎ−ｇｒａｍ出現位置情報３１０に出現位置情報を格納する。
一方、格納部１０４は、文書情報１２０の文書番号が格納されていると判定した場合、文書情報１２０の文書番号が登録された文書内位置情報３０７の出現回数３０９に１を加え、Ｎ−ｇｒａｍ出現位置情報３１０の末尾に出現位置情報を格納する。
【００３０】
（Ｓ１８）では、抽出部１０２は、処理装置により、文書情報１２０におけるポインタの位置を、現在ポインタがセットされている位置の次の文字に進める。つまり、現在１文字目にポインタがセットされている場合には、抽出部１０２は、２文字目にポインタをセットする。
【００３１】
（Ｓ１９）では、抽出部１０２は、ポインタが登録対象の文書情報の末尾（例えば、ＥＯＦ（Ｅｎｄ  Ｏｆ  Ｆｉｌｅ））にセットされているか否かを処理装置により判定する。
抽出部１０２は、末尾にセットされていると判定した場合（Ｓ１９でＹＥＳ）、処理を終了する。一方、抽出部１０２は、末尾にセットされていないと判定した場合（Ｓ１９でＮＯ）、処理を（Ｓ１５）へ戻す。
【００３２】
次に、索引情報１１１を用いて指定された検索キーワードを検索する処理を説明する。
図６は、索引情報１１１を用いて指定された検索キーワードを検索する処理の流れを示すフローチャートである。
【００３３】
（Ｓ２１）では、検索条件入力部１０５は、検索キーワードを指定した検索条件１２１を入力装置により入力する。
【００３４】
（Ｓ２２）では、検索部１０７は、検索結果情報１２２を初期状態として空に設定する。
【００３５】
（Ｓ２３）では、読出部１０６と選択部１０３とは、検索キーワードを検索するために必要なブロック３０５のブロック番号をブロック管理テーブル１０９から取得する。
まず、読出部１０６は、検索キーワードからＮ−ｇｒａｍを処理装置により抽出する。例えば、読出部１０６は、検索キーワードを先頭から順にＮ文字に分割する。なお、検索キーワードの文字数がＮの倍数でない場合は、末尾のＮ文字以下の文字をそのまま切り出す。例えば、図７に示す文字情報が検索キーワードであり、検索キーワードから３−ｇｒａｍを抽出する場合、検索キーワードを先頭から順に３文字に分割して、図７に示す分割文字情報１，２，３を抽出する。つまり、図７に示す検索キーワードは７文字であるため、２つの３−ｇｒａｍと１つの１−ｇｒａｍとが抽出される。
次に、選択部１０３は、読出部１０６が抽出した各Ｎ−ｇｒａｍに対して、ブロック管理テーブル１０９から対応するブロック番号を取得する。つまり、選択部１０３は、読出部１０６が抽出した各Ｎ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６が格納されたブロック３０５のブロック番号を取得する。図７に示す例であれば、２つの３−ｇｒａｍと１つの１−ｇｒａｍとのそれぞれについて、Ｎ−ｇｒａｍ位置情報３０６が格納されたブロック３０５のブロック番号を取得する。選択部１０３がブロック番号を取得する方法については後述する。
【００３６】
（Ｓ２４）では、読出部１０６は、先頭の管理情報ページ３０１を現在の管理情報ページ３０１として処理装置により設定する。
【００３７】
（Ｓ２５）では、読出部１０６は、現在の管理情報ページ３０１から、（Ｓ２３）で抽出した各ブロック番号が示すブロック３０５のブロック格納位置３０３を読み出す。
【００３８】
（Ｓ２６）では、読出部１０６は、（Ｓ２５）で読み出したブロック格納位置３０３が示すブロック３０５を全て、索引情報１１１の位置情報１１３からバッファに読み出す。図７に示す例であれば、２つの３−ｇｒａｍと１つの１−ｇｒａｍとについてのＮ−ｇｒａｍ位置情報３０６が格納されたブロック３０５をバッファに読み出す。
【００３９】
（Ｓ２７）では、検索部１０７は、（Ｓ２６）でバッファに読み出したブロック３０５から、（Ｓ２３）で抽出した各Ｎ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を抽出して、検索キーワードの出現位置情報を処理装置により検索する。
図７に示す検索キーワードを例にして、検索キーワードの出現位置情報を検索する処理を説明する。まず、検索部１０７は、分割文字情報１のＮ−ｇｒａｍ出現位置情報３１０を全て抽出する。次に、検索部１０７は、抽出した各分割文字情報１のＮ−ｇｒａｍ出現位置情報３１０について以下の処理を行う。検索部１０７は、抽出した分割文字情報１のＮ−ｇｒａｍ出現位置情報３１０に３を加えた位置を示す出現位置情報が、分割文字情報２のＮ−ｇｒａｍ位置情報３０６におけるＮ−ｇｒａｍ出現位置情報３１０として格納されているか否かを判定する。出現位置情報が格納されていると判定した場合、検索部１０７は、分割文字情報１のＮ−ｇｒａｍ出現位置情報３１０に３を加えた位置にさらに３を加えた位置を示す出現位置情報が、分割文字情報３のＮ−ｇｒａｍ位置情報３０６におけるＮ−ｇｒａｍ出現位置情報３１０として格納されているか否かを判定する。出現位置情報が格納されていると判定した場合、その分割文字情報１のＮ−ｇｒａｍ出現位置情報３１０と、文書番号３０８とを抽出して、検索結果情報１２２に追加する。
【００４０】
（Ｓ２８）では、読出部１０６は、管理情報ページ３０１を、現在の管理情報ページ３０１の次の管理情報ページ３０１に設定する。
【００４１】
（Ｓ２９）では、読出部１０６は、全ての管理情報ページ３０１について処理が済んだか否かを処理装置により判定する。読出部１０６は、全ての管理情報ページ３０１について処理が済んでいる場合（Ｓ２９でＹＥＳ）、処理を（Ｓ３０）へ進める。一方、読出部１０６は、全ての管理情報ページ３０１について処理が済んでいない場合（Ｓ２９でＮＯ）、処理を（Ｓ２５）へ戻し、処理が済んでいない管理情報ページ３０１について処理を行う。
【００４２】
（Ｓ３０）では、検索結果出力部１０８が検索結果情報１２２を出力装置により出力する。
【００４３】
次に、図５の（Ｓ１６）で選択部１０３がブロック３０５を選択する方法と、図６の（Ｓ２３）で選択部１０３がブロック番号を取得する方法とを説明する。しかし、この説明に先立ち、文書検索装置１００が、単一の言語の文字コードではなく、多言語の文字コードであるＵｎｉｃｏｄｅを用いる場合の留意点について説明する。そして、以下に説明する留意点を踏まえた上で、図５の（Ｓ１６）で選択部１０３がブロック３０５を選択する方法と、図６の（Ｓ２３）で選択部１０３がブロック番号を取得する方法とを説明する。
【００４４】
Ｕｎｉｃｏｄｅを用いる場合には、特に以下の２点に留意する必要がある。
【００４５】
第１に、単一の言語の文字コードと比較して、多言語の文字コードであるＵｎｉｃｏｄｅでは、文字種が多いことに留意する必要がある。
例えば、日本語のＳｈｉｆｔ−ＪＩＳコードの文字種は高々数万文字であるが、Ｕｎｉｃｏｄｅの文字種は百万文字以上になる。そのため、索引情報１１１として登録される情報が多い。
特に、Ｎ−ｇｒａｍ索引方式の場合、Ｎの値に応じてＮ−ｇｒａｍの数が指数的に増加する。そのため、特に、Ｎ−ｇｒａｍ索引方式の場合、索引情報１１１として登録される情報が多い。
【００４６】
第２に、多言語に対応した文書検索装置であっても、実際の運用の場面では、管理対象の文書情報が１乃至少数の言語によって記述された文書情報が大多数を占める場合があることに留意する必要がある。
これは、Ｎ−ｇｒａｍ位置情報３０６を格納するブロック３０５の選択方法を工夫しないと、Ｎ−ｇｒａｍ位置情報３０６が登録されたブロック３０５のサイズが大きく偏りやすいことを意味する。
特にＵｎｉｃｏｄｅでは、言語毎に文字コード空間に文字が配置されている。そのため、１乃至少数の言語によって記述された文書情報では、Ｕｎｉｃｏｄｅの文字コード空間において、連続して配置されている一部の文字だけが、極めて高い頻度で出現することになる。
例えば、日本語によって記述された文書情報であれば、ＡＳＣＩＩ文字と、ひらがな・カタカナと、漢字とのみによって記述されている場合がほとんどである。ここで、Ｕｎｉｃｏｄｅの文字コード空間において、ＡＳＣＩＩ文字は「０ｘ００」から「０ｘ７Ｆ」、ひらがな・カタカナは「０ｘ３０４０」から「０ｘ３０ＦＦ」、漢字は「０ｘ４Ｅ００」から「０ｘ９ＦＦＦ」の領域に連続して配置されている。つまり、日本語によって記述された文書情報の場合、ＡＳＣＩＩ文字の「０ｘ００」から「０ｘ７Ｆ」の領域、ひらがな・カタカナの「０ｘ３０４０」から「０ｘ３０ＦＦ」の領域、漢字の「０ｘ４Ｅ００」から「０ｘ９ＦＦＦ」の領域に配置された文字だけが極めて高い頻度で出現することになる。
【００４７】
そこで、文書検索装置１００の能力を最大限に引き出すためには、以下の２点に留意する必要がある。
【００４８】
第１に、ブロック３０５のサイズを、可能な限り均一にする必要がある。
ブロック３０５のサイズの偏りが大きい場合、索引情報１１１の読み出し効率が低下する。また、並列処理の並列度が低下する。これにより、検索速度が低下する。
【００４９】
第２に、ブロック３０５の数を、ある一定数以下に抑える必要がある。
ブロック３０５の数が多くなった場合、ブロック３０５の格納位置を管理する管理情報１１２のサイズも比例して大きくなる。そのため、管理情報１１２からブロック３０５の格納位置を読み出すための時間がかかり検索効率が低下する。したがって、管理情報１１２のサイズは、計算機に搭載されたＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）に格納して参照できる程度のサイズがよい。
また、実際のブロック３０５には、Ｎ−ｇｒａｍ位置情報３０６の実体だけでなく、図３，４には表れていない個々のブロック３０５を管理するための固定的な情報が含まれている。そのため、特にＮ−ｇｒａｍ位置情報３０６の実体を含まないブロック３０５の数が増加すると、Ｎ−ｇｒａｍ位置情報３０６に対して、ブロック３０５を管理するための固定的な情報のサイズが相対的に大きくなる。その結果、出現位置情報を記憶装置へ格納する効率が低下する。それにより、索引情報１１１を保存するために、より大きな容量の記憶装置１１０が必要となる。
以上のことを考慮して、例えば、ブロック３０５は高々１００万個程度が望ましい。
【００５０】
そこで、文書検索装置１００を計算機において実装する場合、例えば、出現頻度の低い複数のＮ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を、１個のブロック３０５として出現位置情報に登録する。これにより、検索時に読み出すデータのサイズを均一化すると同時に、ブロック３０５の数を少なくする。
【００５１】
つまり、Ｕｎｉｃｏｄｅを用いる場合、非常に種類の多いＮ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を少ない数のブロック３０５に格納する必要がある。そして、非常に種類の多いＮ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を少ない数のブロック３０５に格納するには、複数種類のＮ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を、１個のブロック３０５に格納する必要がある。
例えば２−ｇｒａｍの種類は、Ｕｎｉｃｏｄｅの文字数（約百万文字）の２乗で約１兆種類になる。そのため、ブロック３０５の数を百万個にするのであれば、１個のブロック３０５に約百万種類のＮ−ｇｒａｍ位置情報３０６を格納する必要がある。
【００５２】
索引情報１１１に１−ｇｒａｍと２−ｇｒａｍとの出現位置情報を格納する場合について、Ｎ−ｇｒａｍ位置情報３０６をブロック３０５に割り当てる単純な方法を説明する。
まず、個々のＮ−ｇｒａｍ（ここでは、１−ｇｒａｍと２−ｇｒａｍ）を一意に識別するためのＮ−ｇｒａｍ識別番号を割り当てる。Ｎ−ｇｒａｍ識別番号の単純な割り当て方法としては、次のような方法がある。ここでは、Ｎ−ｇｒａｍ識別番号を６４ビットの整数値とする。
（１）１−ｇｒａｍについてのＮ−ｇｒａｍ識別番号は、その文字の文字コード空間での値とする。
（２）２−ｇｒａｍについてのＮ−ｇｒａｍ識別番号は、Ｎ−ｇｒａｍ識別番号の上位３２ビットに１文字目の文字の文字コード空間での値をセットし、Ｎ−ｇｒａｍ識別番号の下位３２ビットに２文字目の文字の文字コード空間での値をセットする。
図８は、（１）（２）に示す単純な方法により割り当てられたＮ−ｇｒａｍ識別番号の例を示す図である。
図８に示すように、１文字の「ａ」（１−ｇｒａｍ）に割り当てられたＮ−ｇｒａｍ識別番号は、「０ｘ００００００００００００００６１」である。１文字の文字１（１−ｇｒａｍ）に割り当てられたＮ−ｇｒａｍ識別番号は、「０ｘ００００００００００００６４３Ａ」である。１文字の文字２（１−ｇｒａｍ）に割り当てられたＮ−ｇｒａｍ識別番号は、「０ｘ００００００００００００５Ｅ２Ｆ」である。２文字の組の文字情報である文字１と文字２との組合せ（文字１＋文字２）（２−ｇｒａｍ）に割り当てられたＮ−ｇｒａｍ識別番号は、「０ｘ００００６４３Ａ００００５Ｅ２Ｆ」である。
【００５３】
同様に、３−ｇｒａｍについてのＮ−ｇｒａｍ識別番号は、６４ビットのＮ−ｇｒａｍ識別番号の上位又は下位６３ビットを２１ビットずつ区切り、Ｎ−ｇｒａｍ識別番号の上位２１ビットに１文字目の文字の文字コード空間での値をセットし、Ｎ−ｇｒａｍ識別番号の中位２１ビットに２文字目の文字の文字コード空間での値をセットし、Ｎ−ｇｒａｍ識別番号の下位２１ビットに３文字目の文字の文字コード空間での値をセットすればよい。４以上のＮについてのＮ−ｇｒａｍについても同様にＮ−ｇｒａｍ識別番号を割り当てることができる。
【００５４】
次に、Ｎ−ｇｒａｍ識別番号とブロック３０５との対応関係を決定する。
Ｎ−ｇｒａｍ識別番号空間をブロック３０５と同じ数に分割して、分割した各Ｎ−ｇｒａｍ識別番号空間を各ブロック３０５へ割り当てることにより、Ｎ−ｇｒａｍ識別番号とブロック３０５との対応関係を決定する。
例えば、Ｎ−ｇｒａｍ識別番号を値の昇順に整列する。そして、整列したＮ−ｇｒａｍ識別番号を先頭から順に適当な個数ずつ各ブロック３０５に割り当てる。
つまり、先頭からＭ１番目を１番目のＮ−ｇｒａｍ識別番号を１番目のブロック３０５に割り当て、Ｍ１＋１番目からＭ２番目のＮ−ｇｒａｍ識別番号を２番目のブロック３０５に割り当て、・・・、ＭＸ＋１番目から最後のＮ−ｇｒａｍ識別番号を最後のブロック３０５に割り当てる。
すなわち、先頭からＭ１番目のＮ−ｇｒａｍ識別番号が示すＮ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を１番目のブロック３０５に格納するものとし、Ｍ１＋１番目からＭ２番目のＮ−ｇｒａｍ識別番号が示すＮ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を２番目のブロック３０５に格納するものとし、・・・、ＭＸ＋１番目から最後のＮ−ｇｒａｍ識別番号が示すＮ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を最後のブロック３０５に格納するものとする。
【００５５】
ここで、上述したように、多言語に対応した文書検索装置１００であっても、実際の運用の場面では、管理対象の文書情報が１乃至少数の言語によって記述された文書情報が大多数を占める場合がある。そのため、上記のような単純な方法でＮ−ｇｒａｍ位置情報３０６を格納するブロック３０５を決定した場合、特定のブロック３０５にばかり実体のあるＮ−ｇｒａｍ位置情報３０６が集中して割り当てられる。つまり、一部のブロック３０５に実体のあるＮ−ｇｒａｍ位置情報３０６が偏り、一部のブロック３０５のサイズが大きくなる。そのため、上述したように、検索効率が低下することになる。
【００５６】
図９から図１１は、ブロック３０５のサイズの偏りが大きくなることを説明するための図である。図９は、文書情報における文字の出現頻度を説明するための図である。図１０は、Ｎ−ｇｒａｍ識別番号毎のＮ−ｇｒａｍ位置情報３０６のサイズを説明するための図である。図１１は、位置情報１１３におけるブロック３０５のサイズを説明するための図である。なお、図９から図１１では、簡単のため、ひらがな・カタカナと漢字とを日本語として表している。
図９に示すように、文書情報は日本語で書かれたものであり、文書情報にはＡＳＣＩＩ文字と日本語の文字だけが含まれているものとする。つまり、ＡＳＣＩＩ文字の「０ｘ００」から「０ｘ７Ｆ」までの領域、ひらがな・カタカナの「０ｘ３０４０」から「０ｘ３０ＦＦ」までの領域、漢字の「０ｘ４Ｅ００」から「０ｘ９ＦＦＦ」までの領域に配置された文字だけが文書情報に含まれているものとする。
この文書情報に含まれる１−ｇｒａｍと２−ｇｒａｍについて上述した方法によりＮ−ｇｒａｍ識別番号を割り当てると、ＡＳＣＩＩ文字の１文字からなる１−ｇｒａｍには連続した番号がＮ−ｇｒａｍ識別番号として割り当てられる。同様に、ひらがな・カタカナや漢字の１文字からなる１−ｇｒａｍには連続した番号がＮ−ｇｒａｍ識別番号として割り当てられる。同様に、ＡＳＣＩＩ文字の２文字からなる２−ｇｒａｍには連続した番号がＮ−ｇｒａｍ識別番号として割り当てられる。同様に、１文字目がＡＳＣＩＩ文字で、２文字目がひらがな・カタカナの２文字からなる２−ｇｒａｍには連続した番号がＮ−ｇｒａｍ識別番号として割り当てられる。他の組合せの２−ｇｒａｍについても同様に連続した番号がＮ−ｇｒａｍ識別番号として割り当てられる。つまり、一部の連続したＮ−ｇｒａｍ識別番号が示す文字情報のみが存在することになる。
そのため、図１０に示すように、一部の連続したＮ−ｇｒａｍ識別番号が示す文字情報についてのＮ−ｇｒａｍ位置情報３０６の数だけが多くなり、それ以外の文字を含む文字の組に関するＮ−ｇｒａｍ位置情報３０６の数が０となる。
そして、上述した手順によってＮ−ｇｒａｍ識別番号とブロック３０５との対応関係を決定した場合、連続したＮ−ｇｒａｍ識別番号は、１つのブロック３０５又は連続した少数のブロック３０５に割り当てられる。そのため、少数のブロック３０５に全てのＮ−ｇｒａｍ識別番号が割り当てされ、残りの多数のブロック３０５にはＮ−ｇｒａｍ識別番号が割り当てされないことになる。つまり、少数のブロック３０５に全てのＮ−ｇｒａｍ位置情報３０６が格納され、残りの多数のブロック３０５にはＮ−ｇｒａｍ位置情報３０６が格納されないことになる。
その結果、図１１に示すように、位置情報５０１の中の、ＡＳＣＩＩ文字や日本語文字に関するＮ−ｇｒａｍ位置情報３０６を格納したブロック３０５（網掛けにしたブロック５０２）のサイズだけが大きくなり、それ以外のブロック３０５（網掛けになっていないブロック５０３）のサイズは小さくなる。
【００５７】
なお、特定の言語を対象とした文書検索装置１００の場合は、その言語の文字コードの特徴を考慮したブロック３０５の割り当てを行うことにより、ブロック３０５毎のサイズの偏りを抑制するができる。
例えば、日本語文字コードのＳｈｉｆｔ−ＪＩＳの場合、文字コード空間の先頭から、ＡＳＣＩＩ文字、半角カタカナ、ひらがな・カタカナ・全角英数字・記号文字、第１水準漢字、第２水準漢字、・・・のように配置されている。そのため、文字コード空間の後方に配置されていて、使用頻度の低い第２水準漢字に関するＮ−ｇｒａｍ識別情報を数千種類をまとめて１個のブロック３０５に割り当てる。一方、それ以外の使用頻度の高い文字に関するＮ−ｇｒａｍ識別情報を１つだけまたは少数をまとめて１個のブロック３０５に割り当てる。つまり、使用頻度の低い第２水準漢字に関するＮ−ｇｒａｍ位置情報３０６を数千種類をまとめて１個のブロック３０５に格納することとし、使用頻度の高い文字に関するＮ−ｇｒａｍ位置情報３０６を１つだけまたは少数をまとめて１個のブロック３０５に格納することにする。これにより、ブロック３０５毎のサイズの偏りを抑制することができる。
【００５８】
しかし、多言語を対象とした文書検索装置１００の場合、言語毎の文字の出現頻度や、個別の言語内での文字の出現頻度を仮定して、Ｎ−ｇｒａｍ識別番号をブロック３０５に割り当てると、汎用性が失われてしまう。特にＵｎｉｃｏｄｅでは、Ｓｈｉｆｔ−ＪＩＳのように使用頻度を考慮した文字の並びには、必ずしもなっていない。また、全ての言語の組合せに対して、文字の出現頻度を考慮した最適なＮ−ｇｒａｍ識別番号とブロック３０５との割り当て方法を決定するのは現実的に不可能である。
そのため、文字コードをＵｎｉｃｏｄｅとし、Ｎ−ｇｒａｍ索引方式を用いた多言語の文書情報の管理が可能な文書検索装置１００において、文字の種類数と比較して少数のブロック３０５にＮ−ｇｒａｍ位置情報３０６を格納する場合には、人手や言語毎の特徴に依存せず、ブロック３０５のサイズを均等にする方法が必要になる。
【００５９】
以上の留意点を踏まえた上で、図５の（Ｓ１６）で選択部１０３がブロック３０５を選択する方法と、図６の（Ｓ２３）で選択部１０３がブロック番号を取得する方法とを説明する。
なお、上述したように、ブロック３０５の数を少なくする必要があるため、ここではブロック３０５の数はＮ−ｇｒａｍの種類数と比較して少数（例えば、上述したように１００万個）であるとする。つまり、図３に示す各位置情報ページ３０４に格納されたブロック３０５の数ＮＢは、Ｎ−ｇｒａｍの種類数と比較して少数であるとする。
また、以下の説明では、索引情報１１１には、１−ｇｒａｍ，２−ｇｒａｍ，３−ｇｒａｍの出現位置情報が格納されるものとする。
【００６０】
以下の説明において、ＮＣは、文字コード空間における文字数である。Ｃｉ、Ｃｊ、Ｃｋは、文字コード空間における文字の値（０からＮＣ−１まで）である。ＮＢはブロック３０５の数である。また、各ブロック３０５には、一意に識別可能なブロック番号（１からＮＢまで）が割り当てられているものとする。
【００６１】
まず、図５の（Ｓ１６）で選択部１０３がブロック３０５を選択する方法を説明する。
【００６２】
選択部１０３は、以下のように、Ｎ−ｇｒａｍに対してＮ−ｇｒａｍ識別番号を割り当てる。
＜１−ｇｒａｍの場合＞
文字Ｃｉに対して、Ｎ−ｇｒａｍ識別番号Ｘｉを式１のように割り当てる。
（式１）  Ｘｉ＝ＩＮＶ６４（Ｃｉ）
ここで、ＩＮＶ６４（Ｃ）は、値Ｃを６４ビット整数に変換後、その値の上位と下位のビットを入れ替えた６４ビット整数値を出力する関数である。つまり、ＩＮＶ６４（Ｃ）は、ビット転置処理である。
＜２−ｇｒａｍの場合＞
２文字の組ＣｉＣｊに対して、Ｎ−ｇｒａｍ識別番号Ｘｉｊを式２のように割り当てる。
（式２）  Ｘｉｊ＝ＡＬＴ６４（ＩＮＶ６４（Ｃｉ），ＩＮＶ６４（Ｃｊ））
ここで、ＡＬＴ６４（Ｙ，Ｚ，・・・）は、Ｙ、Ｚ、・・・の上位から１ビットずつ交互に取り出し、上位から６４ビット分並べた値を出力する関数である。つまり、ＡＬＴ６４（Ｙ，Ｚ，・・・）は、交互配置処理である。
＜３−ｇｒａｍの場合＞
３文字の組ＣｉＣｊＣｋに対して、Ｎ−ｇｒａｍ識別番号Ｘｉｊｋを式３のように割り当てる。
（式３）  Ｘｉｊｋ＝ＡＬＴ６４（ＩＮＶ６４（Ｃｉ），ＩＮＶ６４（Ｃｊ），ＩＮＶ６４（Ｃｋ））
【００６３】
次に、選択部１０３は、Ｎ−ｇｒａｍ識別番号を、昇順にまたは降順に、各ブロック３０５に同じ数ずつ割り当てる。Ｎ−ｇｒａｍ識別番号の種類数をＮＸとすると、１個のブロック３０５あたりＮＸ／ＮＢ種類のＮ−ｇｒａｍ識別番号を割り当てる。ここで、Ｎ−ｇｒａｍ識別番号の種類数は、凡そ式４の数となる。
（式４）  ＮＸ≒ＮＣ＋ＮＣ２＋ＮＣ３
つまり、選択部１０３は、Ｎ−ｇｒａｍ識別番号を昇順または降順に整列する。そして、選択部１０３は、先頭からＮＸ／ＮＢ種のＮ−ｇｒａｍ識別番号を１番目のブロック３０５に、次のＮＸ／ＮＢ種のＮ−ｇｒａｍ識別番号を２番目のブロック３０５にと、各ブロック３０５に順次割り当てる。
【００６４】
なお、選択部１０３は、Ｎ−ｇｒａｍ識別番号と、そのＮ−ｇｒａｍ識別番号が割り当てられたブロック３０５のブロック番号との対応関係を示す対応情報をブロック管理テーブル１０９に格納する。この対応情報は、文字コード空間における文字の数ＮＣ、Ｎ−ｇｒａｍの最大の文字の数Ｎ、ブロック３０５の数ＮＢなどが予め決まっている場合は、一意に定めることが可能なため、文書の索引情報１１１の作成に先立って、ブロック管理テーブル１０９に格納しておいても良い。
【００６５】
例えば、図１２に示すように、１−ｇｒａｍである文字１（Ｕｎｉｃｏｄｅにおける値：０ｘ６４３Ａ）のＮ−ｇｒａｍ識別番号は、式１の演算を適用して求めることができる。
つまり、まず、文字１の文字コードを６４ビット整数値にする。次に、６４ビット整数値を２進数表記にする。そして、この値の、上位ビットと下位ビットを入れ替える。つまり、式１を計算する。これを１６進数表記に変換すると、“０ｘ５Ｃ２６００００００００００００”となり、この値が文字１のＮ−ｇｒａｍ識別番号となる。
なお、図１２では、見易さのため、２進数表記については８ビット毎に空白を挿入している。
【００６６】
ここで、文字１に隣接する文字、すなわちＵｎｉｃｏｄｅ文字空間において文字１と値が１だけ異なる文字３（Ｕｎｉｃｏｄｅにおける値：０ｘ６４３９）や文字４（Ｕｎｉｃｏｄｅにおける値：０ｘ６４３Ｂ）についても、同様にしてＮ−ｇｒａｍ識別番号を求めると、図１３のようになる。
図１３に示すように、Ｕｎｉｃｏｄｅ文字空間で近接する文字は、Ｎ−ｇｒａｍ識別番号の上位の桁の値が異なる。そのため、Ｕｎｉｃｏｄｅ文字空間で近接する文字からなる１−ｇｒａｍについて、Ｎ−ｇｒａｍ識別番号に大きな差をつけることができる。この差は、１個のブロック３０５に割り当てられるＮ−ｇｒａｍ位置情報３０６の数（数百万種）より大きい。そのため、Ｕｎｉｃｏｄｅ文字空間で隣接する文字のＮ−ｇｒａｍ位置情報３０６が異なるブロック３０５に格納されることが保証される。
なお、Ｕｎｉｃｏｄｅ文字空間で近接する文字との説明があるが、ある文字とＵｎｉｃｏｄｅ文字空間で近接する文字とは、前記ある文字をＵｎｉｃｏｄｅにおけるビット値で表した場合に、Ｕｎｉｃｏｄｅにおいて前記ビット値との差が所定の差（所定の値）以内のビット値で表される文字のことである。
【００６７】
また、例えば、図１４に示すように、２−ｇｒａｍである文字１（Ｕｎｉｃｏｄｅにおける値：０ｘ６４３Ａ）と文字２（Ｕｎｉｃｏｄｅにおける値：０ｘ５Ｅ２Ｆ）との組合せ（文字１＋文字２）のＮ−ｇｒａｍ識別番号は、式２の演算を適用して求めることができる。
つまり、まず、１−ｇｒａｍの場合と同様に、文字１と文字２とのそれぞれのＮ−ｇｒａｍ識別番号を求める。次に、文字１のＮ−ｇｒａｍ識別番号の１ビット目から３２ビット目までを１ビットずつ取り出し、出力となる２−ｇｒａｍ（文字１＋文字２）のＮ−ｇｒａｍ識別番号の奇数ビット目に先頭から順にセットする。同様に、文字２のＮ−ｇｒａｍ識別番号の１ビット目から３２ビット目までを１ビットずつ取り出し、出力となる２−ｇｒａｍ（文字１＋文字２）のＮ−ｇｒａｍ識別番号の偶数ビット目に先頭から順にセットする。この操作により、２−ｇｒａｍ（文字１＋文字２）のＮ−ｇｒａｍ識別番号“０ｘ７７Ｂ０１Ｄ６Ｃ００００００００”が得られる。
【００６８】
ここで、文字２に隣接する文字、すなわちＵｎｉｃｏｄｅ文字空間において文字２と文字コードが１だけ異なる値を割り当てられた文字５（Ｕｎｉｃｏｄｅにおける値：０ｘ５Ｅ２Ｅ）や文字６（０ｘ５Ｅ３０）と、文字１とを組合せた２−ｇｒａｍ（文字１＋文字５，文字１＋文字６）についても、同様にしてＮ−ｇｒａｍ識別番号を求めると図１５のようになる。
図１５に示すように、Ｕｎｉｃｏｄｅ文字空間で近接する文字を含む２−ｇｒａｍのＮ−ｇｒａｍ識別番号は上位の桁の値が異なる。そのため、Ｕｎｉｃｏｄｅ文字空間で近接する文字を含む２−ｇｒａｍについて、Ｎ−ｇｒａｍ識別番号に大きな差をつけることができる。この差は、１個のブロック３０５に割り当てられるＮ−ｇｒａｍ位置情報３０６の数（数百万種）より大きいため、近接する文字を含む２−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６が異なるブロック３０５に格納されることが保証される。
また、図１２に示す文字１から構成される１−ｇｒａｍのＮ−ｇｒａｍ識別番号と、図１５に示す文字１を含む２−ｇｒａｍのＮ−ｇｒａｍ識別番号とにも大きな差がある。つまり、Ｕｎｉｃｏｄｅ文字空間で近接する文字を含む１−ｇｒａｍと２−ｇｒａｍとについて、Ｎ−ｇｒａｍ識別番号に大きな差をつけることができる。この差は、１個のブロック３０５に割り当てられるＮ−ｇｒａｍ位置情報３０６の数（数百万種）より大きいため、Ｕｎｉｃｏｄｅ文字空間で近接する文字を含む１−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６と２−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６とが異なるブロック３０５に格納されることが保証される。
【００６９】
また、例えば、図１６に示すように、３−ｇｒａｍである文字１（Ｕｎｉｃｏｄｅにおける値：０ｘ６４３Ａ）と文字２（Ｕｎｉｃｏｄｅにおける値：０ｘ５Ｅ２Ｆ）と文字７（Ｕｎｉｃｏｄｅにおける値：０ｘ９６ＦＢ）との組合せ（文字１＋文字２＋文字７）のＮ−ｇｒａｍ識別番号は、式３の演算を適用して求めることができる。
つまり、まず、１−ｇｒａｍの場合と同様に、文字１と文字２と文字７とのそれぞれのＮ−ｇｒａｍ識別番号を求める。次に、文字１のＮ−ｇｒａｍ識別番号の１ビット目から２１ビット目までを１ビットずつ取り出し、出力となる３−ｇｒａｍ（文字１＋文字２＋文字７）のＮ−ｇｒａｍ識別番号の１、４、７、・・・、６１ビット目に先頭から順にセットする。同様に文字２のＮ−ｇｒａｍ識別番号の１ビット目から２１ビット目までを１ビットずつ取り出し、出力となる３−ｇｒａｍ（文字１＋文字２＋文字７）のＮ−ｇｒａｍ識別番号の２、５、８、・・・、６２ビット目に先頭から順にセットする。さらに文字７のＮ−ｇｒａｍ識別番号の１ビット目から２１ビット目までを１ビットずつ取り出し、出力となる３−ｇｒａｍ（文字１＋文字２＋文字７）のＮ−ｇｒａｍ識別番号の３、６、９、・・・、６３ビット目に先頭から順にセットする。そして、出力となる３−ｇｒａｍ（文字１＋文字２＋文字７）のＮ−ｇｒａｍ識別番号の６４ビット目に０をセットする。この操作により、３−ｇｒａｍ（文字１＋文字２＋文字７）のＮ−ｇｒａｍ識別番号“０ｘ７Ｄ７ＢＣ９０ＦＡ７３１００００”が得られる。
【００７０】
３−ｇｒａｍの場合も、１−ｇｒａｍや２−ｇｒａｍの場合と同様に、Ｕｎｉｃｏｄｅ文字空間で近接する文字を含む３−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６が異なるブロック３０５に格納されることが保証される。また、Ｕｎｉｃｏｄｅ文字空間で近接する文字を含む１−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６と２−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６と３−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６とが異なるブロック３０５に格納されることが保証される。
【００７１】
Ｕｎｉｃｏｄｅにおける文字の値は、２１ビットあれば表現可能である。そのため、Ｎ−ｇｒａｍ識別番号を６４ビット整数値とすると、最大で３−ｇｒａｍまでを上記の手順によって一意に割り当てることができる。
４−ｇｒａｍ以上の場合についても、単純には、Ｎ−ｇｒａｍ識別番号を２１×Ｎビット以上の整数値とすることで実現することが可能である。
また、逆に索引情報１１１に出現位置情報を格納する文字の種類を、２１６種以下に限定することにより、４−ｇｒａｍについてもＮ−ｇｒａｍ識別番号を６４ビット整数値を使って表現可能となるようにしてもよい。一般に、ある文字コード空間の文字の種類数をＮＣとすると、そこに含まれる文字の値はｌｏｇ２ＮＣビットの数値で一意に識別可能である。よって、その文字コード空間の文字に対して、索引情報１１１を生成したい場合は、Ｎ−ｇｒａｍ識別番号をｌｏｇ２ＮＣ×Ｎビットの数値とすればよい。
【００７２】
以上のようにＮ−ｇｒａｍ位置情報３０６を格納するブロック３０５を決定することにより、文字の種類数と比較して少数のブロック３０５にＮ−ｇｒａｍ位置情報３０６を格納する場合に、ブロック３０５のサイズを均等にすることができる。
【００７３】
次に、図６の（Ｓ２３）で選択部１０３がブロック番号を取得する方法を説明する。
図６の（Ｓ２３）において、選択部１０３は、図５の（Ｓ１６）のときと同様に、各Ｎ−ｇｒａｍについてＮ−ｇｒａｍ識別番号を処理装置により計算する。そして、選択部１０３は、計算したＮ−ｇｒａｍ識別番号に対応するブロック番号をブロック管理テーブル１０９から取得する。
つまり、図６の（Ｓ２３）において、選択部１０３は、図５の（Ｓ１６）で計算したＮ−ｇｒａｍ識別番号と同じＮ−ｇｒａｍ識別番号を計算する。そして、選択部１０３は、計算したＮ−ｇｒａｍ識別番号でブロック管理テーブル１０９を検索することにより、Ｎ−ｇｒａｍ識別番号に対応するブロック番号、つまり、Ｎ−ｇｒａｍに対応するブロック番号を取得できる。
【００７４】
以上のように、実施の形態１に係る文書検索装置１００は、Ｕｎｉｃｏｄｅ文字空間において近接した文字を含むＮ−ｇｒａｍを、Ｎ−ｇｒａｍ識別番号の空間において、分散して配置する。これにより、ある特定の言語で使用される文字を含むＮ−ｇｒａｍ位置情報３０６が、１乃至少数のブロック３０５に集中して格納されることを抑止することができる。したがって、ブロック３０５の偏りに起因する検索速度の低下を防止し、文書情報を高速に検索することが可能である。
つまり、実施の形態１に係る文書検索装置１００は、Ｕｎｉｃｏｄｅ等の１種の文字コードで複数の言語の文字を扱うことができる文字コードを用いた場合であっても、効率的に検索することができる。
【００７５】
また、実施の形態１に係る文書検索装置１００は、閾値以下のデータサイズの文書情報毎にページを分けてＮ−ｇｒａｍ位置情報３０６を記憶するため、特許文献１と同様の効果を得ることができる。なお、図５（Ｓ１２）の説明において、索引情報１１１に管理情報ページ３０１と位置情報ページ３０４を追加するか否かを、ブロック内文書数３０２によって判定した。しかし、これに限らず、例えば、特許文献１に記載された異なる方法を適用しても良い。
【００７６】
実施の形態２．
実施の形態２では、実施の形態１とは異なるＮ−ｇｒａｍ位置情報３０６とブロック３０５との割り当て方法について説明する。また、実施の形態２で説明するＮ−ｇｒａｍ位置情報３０６とブロック３０５との割り当て方法に基づく検索処理についても説明する。
なお、実施の形態２に係る文書検索装置１００の構成は、図２に示す実施の形態１に係る文書検索装置１００の構成と同様である。
【００７７】
実施の形態２に係る文書検索装置１００による索引情報１１１を作成する処理について、実施の形態１に係る文書検索装置１００による処理と異なる部分のみを説明する。実施の形態２に係る文書検索装置１００による索引情報１１１を作成する処理は、図５の（Ｓ１６）のみ実施の形態１に係る文書検索装置１００による処理と異なる。
なお、ここでは、文書検索装置１００が、１−ｇｒａｍ、２−ｇｒａｍ、３−ｇｒａｍの出現位置情報を索引情報１１１に保存する場合を例として説明する。しかし、４−ｇｒａｍ以上のＮ−ｇｒａｍの出現位置情報を索引情報１１１に保存する場合であっても同様の処理を適用することができる。
【００７８】
選択部１０３は、Ｎ−ｇｒａｍの文字数Ｎ毎に、Ｎ−ｇｒａｍ位置情報を格納するブロック３０５を予め決めておく。つまり、文書検索装置１００が、１−ｇｒａｍ、２−ｇｒａｍ、３−ｇｒａｍの出現位置情報を索引情報１１１に保存するとすると、選択部１０３は、１−ｇｒａｍに関する出現位置情報を格納するブロック３０５の組と、２−ｇｒａｍに関する出現位置情報を格納するブロック３０５の組と、３−ｇｒａｍに関する出現位置情報を格納するブロック３０５の組とに予め分けてブロック３０５を管理する。
【００７９】
選択部１０３は、以下のようにＮ−ｇｒａｍ位置情報３０６を格納するブロック３０５を選択する。
選択部１０３は、予めブロック３０５を、識別番号の順に、先頭のＮＢ１−ｇｒａｍ個を１−ｇｒａｍ位置情報格納用のブロック３０５、次のＮＢ２−ｇｒａｍ個を２−ｇｒａｍ位置情報格納用のブロック３０５、その次のＮＢ３−ｇｒａｍ個を３−ｇｒａｍ位置情報格納用のブロック３０５と定義しておく。
ここで、式５が成り立つものとする。
（式５）  ＮＢ＝ＮＢ１−ｇｒａｍ＋ＮＢ２−ｇｒａｍ＋ＮＢ３−ｇｒａｍ
例えば、式６のように定義してもよい。
（式６）  ＮＢ１−ｇｒａｍ＝ＮＢ２−ｇｒａｍ＝ＮＢ３−ｇｒａｍ＝ＮＢ／３
【００８０】
選択部１０３は、実施の形態１で説明した手順と同様に、Ｎ−ｇｒａｍ識別番号を算出する。続いて、Ｎ−ｇｒａｍの文字数Ｎ毎に、Ｎ−ｇｒａｍ識別番号を整列し、各ブロック３０５に等しい数ずつ割り当てる。
具体的には、１−ｇｒａｍに関するＮ−ｇｒａｍ識別番号の種類数をＮＸ１−ｇｒａｍとすると、選択部１０３は、１個の１−ｇｒａｍ用のブロック３０５あたりＮＸ１−ｇｒａｍ／ＮＢ１−ｇｒａｍ種類のＮ−ｇｒａｍ識別番号を割り当てる。同様に、２−ｇｒａｍに関するＮ−ｇｒａｍ識別番号の種類数をＮＸ２−ｇｒａｍ、３−ｇｒａｍに関するＮ−ｇｒａｍ識別番号の種類数をＮＸ３−ｇｒａｍとすると、選択部１０３は、１個の２−ｇｒａｍ用のブロック３０５あたりＮＸ２−ｇｒａｍ／ＮＢ２−ｇｒａｍ種類のＮ−ｇｒａｍ識別番号を割り当て、１個の３−ｇｒａｍ用のブロック３０５あたりＮＸ３−ｇｒａｍ／ＮＢ３−ｇｒａｍ種類のＮ−ｇｒａｍ識別番号を割り当てる。
すなわち、選択部１０３は、まず、１−ｇｒａｍに関するＮ−ｇｒａｍ識別番号を昇順または降順に整列する。そして、選択部１０３は、先頭からＮＸ１−ｇｒａｍ／ＮＢ１−ｇｒａｍ種のＮ−ｇｒａｍ位置情報を１−ｇｒａｍ用のブロック３０５の１番目のブロック３０５に、次のＮＸ１−ｇｒａｍ／ＮＢ１−ｇｒａｍ種のＮ−ｇｒａｍ位置情報を２番目のブロック３０５にというように順次割り当てる。同様に、選択部１０３は、まず、２−ｇｒａｍに関するＮ−ｇｒａｍ識別番号を昇順または降順に整列する。そして、選択部１０３は、先頭からＮＸ２−ｇｒａｍ／ＮＢ２−ｇｒａｍ種のＮ−ｇｒａｍ位置情報をＮＢ１−ｇｒａｍ＋１番目のブロック３０５に、次のＮＸ２−ｇｒａｍ／ＮＢ２−ｇｒａｍ種のＮ−ｇｒａｍ位置情報をＮＢ１−ｇｒａｍ＋２番目のブロック３０５にというように順次割り当てる。さらに、選択部１０３は、３−ｇｒａｍに関するＮ−ｇｒａｍ識別番号を昇順または降順に整列する。そして、選択部１０３は、先頭からＮＸ３−ｇｒａｍ／ＮＢ３−ｇｒａｍ種のＮ−ｇｒａｍ位置情報をＮＢ１−ｇｒａｍ＋ＮＢ２−ｇｒａｍ＋１番目のブロック３０５に、次のＮＸ３−ｇｒａｍ／ＮＢ３−ｇｒａｍ種のＮ−ｇｒａｍ位置情報をＮＢ１−ｇｒａｍ＋ＮＢ２−ｇｒａｍ＋２番目のブロック３０５にというように順次割り当てる。
【００８１】
次に、図６に基づき、実施の形態２に係る文書検索装置１００による検索キーワードを検索する処理について、実施の形態１に係る文書検索装置１００による処理と異なる部分のみを説明する。実施の形態２に係る文書検索装置１００による検索キーワードを検索する処理は、図６の（Ｓ２３）と（Ｓ２７）とのみ実施の形態１に係る文書検索装置１００による処理と異なる。
【００８２】
まず、図６における（Ｓ２３）での処理について説明する。
読出部１０６は、索引情報１１１から１−ｇｒａｍからＮ−ｇｒａｍまでのうち、最大文字数であるＮ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を優先的に読み出す。
例えば、索引情報１１１が１−ｇｒａｍ、２−ｇｒａｍ、３−ｇｒａｍの出現位置情報を格納したものである場合は、検索キーワードが３文字未満である場合を除いて、３−ｇｒａｍの出現位置情報だけを検索に使用する。
【００８３】
読出部１０６は、検索キーワードが３文字未満であるか否かを判定する。
読出部１０６は、検索キーワードが３文字未満である場合、実施の形態１と同様に処理を実行する。
一方、読出部１０６は、検索キーワードが３文字以上である場合、検索キーワードを先頭から３文字ずつに分割して、３−ｇｒａｍを抽出する。検索キーワードが３の倍数でない場合、読出部１０６は、検索キーワードの末尾についても３文字を切り出し、３−ｇｒａｍを抽出する。
例えば、図１７に示す文字情報が検索キーワードである場合、先頭から順に３文字ずつに分割して、分割文字情報１，２，４を抽出する。つまり、単純に検索キーワードを３文字に分割すると、図７に示すように、分割文字情報１，２，３が抽出される。しかし、ここでは、検索キーワードが３の倍数でない場合、読出部１０６は、検索キーワードの末尾について、不足する文字数分、前の文字を抽出する。つまり、不足する文字数分、検索キーワードの末尾の３−ｇｒａｍと、その直前の３−ｇｒａｍとは重複する。図１７の例では、検索キーワードの末尾の３−ｇｒａｍと、その直前の３−ｇｒａｍとでは、２文字の重複がある。ここで、読出部１０６は、重複した文字数（図１７の例では２）を記憶装置に記憶しておく。
【００８４】
重複する文字数は、式７に示す値となる。
（式７）  重複した文字数＝Ｎ−（検索キーワードの文字数％Ｎ）
なお、式７において％は、余剰を求める演算である。つまり、Ａ％Ｂとは、値Ａを値Ｂで割った余剰を求めることを意味する。
【００８５】
そして、選択部１０３は、抽出した３−ｇｒａｍに対して、この実施の形態で説明した図５の（Ｓ１６）の場合と同様に、Ｎ−ｇｒａｍ識別番号を計算し、ブロック３０５のブロック番号をブロック管理テーブル１０９から取得する。
【００８６】
次に、図６における（Ｓ２７）での処理について説明する。
検索部１０７は、バッファに読み出したブロック３０５から、（Ｓ２３）で抽出した各Ｎ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を抽出して、検索キーワードの出現位置情報を処理装置により検索する。
図１７に示す検索キーワードを例にして、検索キーワードの出現位置情報を検索する処理を説明する。まず、検索部１０７は、分割文字情報１のＮ−ｇｒａｍ出現位置情報３１０を全て抽出する。次に、検索部１０７は、抽出した各分割文字情報１のＮ−ｇｒａｍ出現位置情報３１０について以下の処理を行う。検索部１０７は、抽出した分割文字情報１のＮ−ｇｒａｍ出現位置情報３１０に３を加えた位置を示す出現位置情報が、分割文字情報２のＮ−ｇｒａｍ位置情報３０６におけるＮ−ｇｒａｍ出現位置情報３１０として格納されているか否かを判定する。出現位置情報が格納されていると判定した場合、検索部１０７は、分割文字情報１のＮ−ｇｒａｍ出現位置情報３１０に３を加えた位置にさらに（３−重複した文字数（ここでは、２））を加えた位置を示す出現位置情報が、分割文字情報３のＮ−ｇｒａｍ位置情報３０６におけるＮ−ｇｒａｍ出現位置情報３１０として格納されているか否かを判定する。つまり、検索部１０７は、分割文字情報１のＮ−ｇｒａｍ出現位置情報３１０に３を加えた位置にさらに１を加えた位置を示す出現位置情報が、分割文字情報３のＮ−ｇｒａｍ位置情報３０６におけるＮ−ｇｒａｍ出現位置情報３１０として格納されているか否かを判定する。出現位置情報が格納されていると判定した場合、その分割文字情報１のＮ−ｇｒａｍ出現位置情報３１０と、文書番号３０８とを抽出して、検索結果情報１２２に追加する。
【００８７】
実施の形態１に係る文書検索装置１００のように、Ｎ−ｇｒａｍ位置情報３０６を格納するブロック３０５が文字数Ｎ毎に分かれていない場合、１個のブロックに各文字数のＮ−ｇｒａｍ（上記例であれば、１−ｇｒａｍ，２−ｇｒａｍ，３−ｇｒａｍ）のＮ−ｇｒａｍ位置情報３０６が混在して格納される。
ここで、１個のＮ−ｇｒａｍ位置情報３０６のサイズに着目すると、ある文字の１−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６のサイズは、その文字を含む２−ｇｒａｍ以上のＮ−ｇｒａｍ位置情報３０６のサイズと同じか、その文字を含む２−ｇｒａｍ以上のＮ−ｇｒａｍ位置情報３０６のサイズよりも大きくなる。例えば、図１８に示す文書情報の場合、文字７である１−ｇｒａｍの出現位置の数は３である（図１８の下線部参照）。これに対し、文字７を含む２−ｇｒａｍの出現位置の数はそれぞれ１である（図１８の下線部参照）。Ｎ−ｇｒａｍ位置情報３０６を格納するブロック３０５が、文字数Ｎ毎に決定されていない場合、１個のブロック３０５に、１個あたりのサイズが大きい１−ｇｒａｍの位置情報と、１個あたりのサイズが小さい２−ｇｒａｍ、３−ｇｒａｍの位置情報とが混在して含まれることになる。
一般的に文書情報の検索では１文字のキーワードによる検索を行う頻度は低い。そのため、実施の形態１で示した検索処理の流れでは、１−ｇｒａｍの出現位置情報の使用頻度よりも２−ｇｒａｍ、３−ｇｒａｍの出現位置情報の使用頻度の方が高い。一方で、文書検索装置１００は、ブロック３０５の単位で索引情報１１１の読み出しを行うため、例えば、サイズが小さい３−ｇｒａｍの出現位置情報だけが必要な場合でも、サイズが大きい１−ｇｒａｍの出現位置情報まで読み出す必要がある。そのため、記憶装置１１０から索引情報１１１を読み出す処理に無駄が多くなる。
【００８８】
そこで、実施の形態２に係る文書検索装置１００のように、文字数Ｎ毎にＮ−ｇｒａｍ位置情報３０６を格納するブロック３０５を予め決定しておくことにより、以下のような効果が得られる。
【００８９】
まず、サイズが小さい３−ｇｒａｍの出現位置情報だけが必要な場合には、サイズが小さい３−ｇｒａｍの出現位置情報だけを読み出すことができる。つまり、サイズが小さい３−ｇｒａｍの出現位置情報だけが必要な場合に、サイズが大きい１−ｇｒａｍの出現位置情報まで読み出されてしまうことがない。そのため、記憶装置１１０から索引情報１１１を読み出す処理における無駄を削減できる。
【００９０】
また、上記説明の通り、１個あたりの３−ｇｒａｍの出現位置情報の平均サイズは、１−ｇｒａｍの出現位置情報の平均サイズよりも小さい。また、文書検索装置１００では、ブロック３０５のサイズが可能な限り均等になるよう索引を構成する。
そのため、１個の１−ｇｒａｍ用のブロック３０５に格納されるＮ−ｇｒａｍ位置情報３０６の数より、１個の２−ｇｒａｍ用のブロック３０５や３−ｇｒａｍ用のブロック３０５に格納されるＮ−ｇｒａｍ位置情報３０６の数が多くなる。その結果、１−ｇｒａｍでの検索に比べ、２−ｇｒａｍや３−ｇｒａｍでの検索では、検索処理で読み出すブロック３０５の数を削減することができ、記憶装置１１０から索引情報１１１を読み出す処理における無駄を削減することができる。
【００９１】
特に、実施の形態２に係る文書検索装置１００による検索処理では、索引情報１１１に１−ｇｒａｍ、２−ｇｒａｍ、３−ｇｒａｍの出現位置情報が含まれる場合、検索キーワードの文字数が３文字未満の場合を除いて、３−ｇｒａｍの出現位置情報のみを用いて検索を行う。つまり、索引情報１１１に出現位置情報が含まれるＮ−ｇｒａｍの最大文字数をＮとすると、検索キーワードの文字数がＮ文字未満の場合を除いて、最大文字数Ｎについての出現位置情報のみで検索を行う。そのため、検索処理で読み出すブロック３０５の数を削減することができ、記憶装置１１０から索引情報１１１を読み出す処理における無駄を削減することができる。
【００９２】
さらに、１−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６に含まれるＮ−ｇｒａｍ出現位置情報３１０の数よりも、３−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６に含まれるＮ−ｇｒａｍ出現位置情報３１０の数の方が平均的に少ない。そのため、図６の（Ｓ２７）において、Ｎ−ｇｒａｍ出現位置情報３１０の照合を行う回数を減らすことができ、処理を効率よくすることができる。
【００９３】
なお、上記説明では、索引情報１１１に１−ｇｒａｍ、２−ｇｒａｍ、３−ｇｒａｍの出現位置情報を格納する場合について説明した。しかし、索引情報１１１に４−ｇｒａｍ以上の出現位置情報を格納する場合であっても、ＮＢを式８のように定義することで、上記説明と同様の手順によってブロック番号を決定することができる。
（式８）  ＮＢ＝ＮＢ１−ｇｒａｍ＋ＮＢ２−ｇｒａｍ＋ＮＢ３−ｇｒａｍ＋ＮＢ４−ｇｒａｍ＋・・・
【００９４】
また、実施の形態１と実施の形態２では、Ｎ＝１，２，３の場合を例として、１−ｇｒａｍ、２−ｇｒａｍ、３−ｇｒａｍの全てに対してＮ−ｇｒａｍ位置情報３０６を抽出するものとした。しかし、一部を抽出しないようにしてもよい。
例えば、最大文字数Ｎ（ここでは、３）のＮ−ｇｒａｍに対するＮ−ｇｒａｍ位置情報３０６と１−ｇｒａｍに対するＮ−ｇｒａｍ位置情報３０６だけを索引情報１１１に格納して、２−ｇｒａｍに対するＮ−ｇｒａｍ位置情報３０６を索引情報１１１に格納しないようにしてもよい。検索時には、Ｎ文字以上の検索キーワードに関しては、実施の形態２で説明した検索処理の流れ同様に、Ｎ文字毎に区切ることにより検索が可能である。一方、Ｎ文字未満の検索キーワードに関しては、１文字毎に区切ることにより、１−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６を使用して検索を行うことが可能である。
また、１−ｇｒａｍに対するＮ−ｇｒａｍ位置情報３０６だけを索引情報１１１に格納しておき、全ての検索キーワードについて、１−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６だけを用いて検索を行うとしてもよい。
いずれの場合であっても、１−ｇｒａｍからＮ−ｇｒａｍまでのＮ−ｇｒａｍ位置情報３０６を全て索引情報１１１に格納する場合と比較して、索引情報１１１を格納するための記憶装置１１０の容量を削減することができる。
【００９５】
この他にも、最大文字数ＮやＮ−１などの長い文字の組に対してだけＮ−ｇｒａｍ位置情報３０６を索引情報１１１に格納し、所定未満の文字数に対するＮ−ｇｒａｍ位置情報３０６を索引情報１１１に格納しないとしてもよい。
この場合、所定未満の文字数の検索キーワードについては検索できなくする（検索条件１２１として入力できなくする）などの制限を設けてもよい。あるいは、所定未満の文字数の検索キーワードについては、検索キーワードを含むＮ−ｇｒａｍに関連するＮ−ｇｒａｍ位置情報３０６を索引情報１１１から全て読み出して照合するとしてもよい。
この場合も、１−ｇｒａｍからＮ−ｇｒａｍまでのＮ−ｇｒａｍ位置情報３０６を全て索引情報１１１に格納する場合と比較して、索引情報１１１を格納するための記憶装置１１０の容量を削減することができる。
【００９６】
実施の形態３．
実施の形態３では、実施の形態１とは異なるＮ−ｇｒａｍ識別番号の算出方法について説明する。
なお、実施の形態３に係る文書検索装置１００の構成は、図２に示す実施の形態１に係る文書検索装置１００の構成と同様である。
【００９７】
実施の形態３に係る文書検索装置１００による索引情報１１１を作成する処理と、検索キーワードを検索する処理とについて、実施の形態１に係る文書検索装置１００による処理と異なる部分のみを説明する。実施の形態３に係る文書検索装置１００による索引情報１１１を作成する処理と検索キーワードを検索する処理とは、図５の（Ｓ１６）と図６の（Ｓ２３）とにおけるＮ−ｇｒａｍ識別番号の算出方法のみ実施の形態１に係る文書検索装置１００による処理と異なる。
【００９８】
実施の形態１では、２文字以上のＮ−ｇｒａｍからＮ−ｇｒａｍ識別番号を算出するには、まず、選択部１０３は、Ｎ−ｇｒａｍの各文字の文字コードの上位と下位のビットを反転させた。次に、選択部１０３は、ビットを反転させた各文字の文字コードの上位から１ビットずつ抽出して順番に並べた。これにより、Ｎ−ｇｒａｍからＮ−ｇｒａｍ識別番号を算出していた。この処理は、１ビット単位の処理であるため、文書情報における全ての文字について同様の処理を行うと、Ｎ−ｇｒａｍ識別番号の算出負荷が高い。
【００９９】
実施の形態１では、ＡＬＴ６４（Ｙ，Ｚ，・・・）という演算を定義し、この演算を用いてＮ−ｇｒａｍ識別番号を算出した。実施の形態１では、ＡＬＴ６４（Ｙ，Ｚ，・・・）とは、Ｙ、Ｚ、・・・の上位から１ビットずつ交互に取り出し、上位から６４ビット分並べた値を出力する関数であるとした。
【０１００】
実施の形態３では、ＡＬＴ６４（Ｙ，Ｚ，・・・）の代わりに用いるＡＬＴ６４Ｍ（Ｙ，Ｚ，・・・）を次のように定義する。
ＡＬＴ６４Ｍ（Ｙ，Ｚ，・・・）は、Ｙ、Ｚ、・・・の上位からＭビットずつ交互に取り出し、上位から６４ビット分並べた値を出力する。
つまり、実施の形態１におけるＡＬＴ６４（Ｙ，Ｚ，・・・）は、ＡＬＴ６４Ｍ（Ｙ，Ｚ，・・・）をＭ＝１の場合に限定した定義であった。しかし、実施の形態３では、１よりも大きいＭについても適用可能に定義した。そして、Ｍ＝２やＭ＝４やＭ＝８等、Ｍを２以上の値とすることにより、選択部１０３が、Ｎ−ｇｒａｍ識別番号を演算する処理の回数を削減できるようにした。これにより、Ｎ−ｇｒａｍ識別番号の算出負荷を軽減することができる。
【０１０１】
同様に、ＩＮＶ６４（Ｃ）の代わりに用いるＩＮＶ６４Ｍ（Ｃ）を次のように定義しても良い。
ＩＮＶ６４Ｍ（Ｃ）は、値Ｃを６４ビット整数に変換後、その値の上位と下位のビットをＭ単位で入れ替えた６４ビット整数値を出力する。
つまり、実施の形態１におけるＩＮＶ６４（Ｃ）は、ＩＮＶ６４Ｍ（Ｃ）をＭ＝１の場合に限定した定義であった。実施の形態３では、１よりも大きいＭについても適用可能に定義した。そして、Ｍ＝２やＭ＝４やＭ＝８等、Ｍを２以上の値とすることにより、選択部１０３が、Ｎ−ｇｒａｍ識別番号を演算する処理の回数を削減できるようにした。これにより、Ｎ−ｇｒａｍ識別番号の算出負荷を軽減することができる。
【０１０２】
なお、索引情報１１１を作成する処理と検索キーワードを検索する処理とで、同じＮ−ｇｒａｍから同じＮ−ｇｒａｍ識別番号を算出できるのであれば、Ｍは固定値でなくてもよい。例えば、ＡＬＴ６４（Ｙ，Ｚ，・・・）を用いた交互配置処理において、初回は１ビット、２回目は２ビット、・・・、のように下位のビットになるに従って、Ｍが増えるようにしてもよい。
【０１０３】
Ｍの値を大きくするに従って、Ｎ−ｇｒａｍ識別番号の演算処理の負荷を削減することができる一方で、Ｎ−ｇｒａｍ識別番号の分散度合いは低下する。つまり、Ｎ−ｇｒａｍ識別番号の演算処理の負荷とＮ−ｇｒａｍ識別番号の分散度合いとには、トレードオフの関係がある。そこで、実施の形態３における２−ｇｒａｍ（文字１＋文字２）のＮ−ｇｒａｍ識別番号の算出処理の一例を示す。
ブロック３０５の数をＮＢとした場合、ＮＢのビット幅は以下のＮＢ’と表すことができる。
（式９）  ＮＢ’＝ＦＬＯＯＲ（ｌｏｇ２ＮＢ）
ここで、ＦＬＯＯＲ（Ｘ）とは、小数Ｘに対して、Ｘ以下の整数値で最大の値を求める演算である。つまり、Ｘが正の数である場合は、その小数点以下を切り捨てた値を求める演算である。
ブロック３０５の数のビット幅がＮＢ’ということは、実施の形態１や実施の形態２のＮ−ｇｒａｍ位置情報３０６とブロック３０５の割り当て方法に従うと、Ｎ−ｇｒａｍ識別番号の上位ＮＢ’ビットの値で、割り当てられるブロック３０５の番号が決定されることを意味する。そのため、少ない演算負荷で、Ｕｎｉｃｏｄｅの文字コード空間において近接した文字を含むＮ−ｇｒａｍを、Ｎ−ｇｒａｍ識別番号の空間において分散して配置するためには、Ｎ−ｇｒａｍ識別番号の上位ＮＢ’ビットに、Ｎ−ｇｒａｍに含まれる文字の下位のビット値が反映されるようにすると良い。
Ｕｎｉｃｏｄｅの場合、各文字の値の有効なビット幅は２１ビットである。１−ｇｒａｍの場合は、１−ｇｒａｍの文字の値の下位ＮＢ’ビットをＮ−ｇｒａｍ識別番号の上位ＮＢ’ビットにセットし、１−ｇｒａｍの文字の下位ＮＢ’＋１ビット目から２１ビット目までをＮ−ｇｒａｍ識別番号の上位ＮＢ’＋１以降にセットする。２−ｇｒａｍの場合は、その１文字目と２文字目の値の下位ＮＢ’／２ビットを取り出し、Ｎ−ｇｒａｍ識別番号の上位ＮＢ’ビットにセットし、２-ｇｒａｍの１文字目と２文字目の値の下位ＮＢ’／２＋１目ビットから２１ビット目を取り出し、Ｎ−ｇｒａｍ識別番号の上位ＮＢ’＋１ビット以下にセットする。
一般化すると、（１）Ｎ−ｇｒａｍの各文字の値の下位からＦＬＯＯＲ（ＮＢ’／Ｎ）ビットずつを取り出し、Ｎ−ｇｒａｍ識別番号の上位ＦＬＯＯＲ（ＮＢ’／Ｎ）×Ｎビットにセットする。次に、（２）ＮＢ’％Ｎ（＝Ｒ）が０で無い場合は、Ｎ−ｇｒａｍを構成する文字のうちいずれかのＲ個の文字の値のＦＬＯＯＲ（ＮＢ’／Ｎ）＋１ビット目を取り出し、Ｎ−ｇｒａｍ識別番号のＦＬＯＯＲ（ＮＢ’／Ｎ）×Ｎ＋１ビット以下に順に配置する。なお、％とは、上述したように剰余を求める演算である。そして、（３）Ｎ−ｇｒａｍの各文字の残りの２１ビット目までを取り出し、Ｎ−ｇｒａｍ識別番号の下位のビットにセットする。
【０１０４】
図１９は、２−ｇｒａｍの場合の具体例である。ここでの索引情報１１１のブロック数は２６２１１４（＝２１８）個、つまりブロック番号は最大で１８ビットの整数値で表すことのできる数であるとする。すなわち、ＮＢ’＝１８である。したがって、ＮＢ’／Ｎを計算すると、１８／２＝９となる。この場合、（１）２−ｇｒａｍの文字１の値と文字２の値からそれぞれ下位９ビットずつを取り出し、それをＮ−ｇｒａｍ識別番号の上位１８ビットにセットする。ＮＢ’％Ｎ＝０であるため（２）は実行されず、続いて、（３）文字１、文字２の値の下位１０ビット目から２１ビット目を取り出し、Ｎ−ｇｒａｍ識別番号の上位１９ビット目から４２ビット目にセットする。
なお、（２）が実行される場合とは、例えば、ＮＢ’＝１８で、Ｎ＝４の場合などである。この場合、ＮＢ’／Ｎを計算すると、１８／４＝「４余り２」となる。つまり、ＮＢ’％Ｎ＝２である。そのため、（１）４−ｇｒａｍの各文字の値からそれぞれ下位４ビットずつを取り出し、それをＮ−ｇｒａｍ識別番号の上位１６ビットにセットする。次に、（２）４−ｇｒａｍを構成する文字のうち、いずれかの２文字の値のＦＬＯＯＲ（ＮＢ’／Ｎ）＋１ビット目を取り出し、それをＮ−ｇｒａｍ識別番号の１７ビット目、１８ビット目にそれぞれセットする。４−ｇｒａｍを構成する文字のうち、いずれかの２文字とは、例えば、最後の文字とその前の文字などである。そして、（３）４−ｇｒａｍを構成する各文字の残りの２１ビット目までを取り出し、Ｎ−ｇｒａｍ識別番号の上位１９ビット目以降にセットする。
【０１０５】
以上のようにすることにより、先頭からｎ番目（１≦ｎ≦Ｎ）の文字が値Ｃｎで表される文字であるＮ−ｇｒａｍと、値Ｃｎとの値の差がＮＢ’／２Ｎ以内の値Ｃ’で表される文字（但し、Ｃｎ自身は除く）を先頭からｎ番目に含むＮ−ｇｒａｍとは、Ｎ−ｇｒａｍ位置情報３０６が、同じブロック３０５に格納されないことが保証される。ここで、値Ｃｎと値の差がＮＢ’／２Ｎ以内の値Ｃ’とは、「Ｃｎ−ＮＢ／２Ｎ≦Ｃ’≦Ｃｎ＋ＮＢ／２Ｎ」である。
【０１０６】
図２０は、図１９の変形例である。ここでは、Ｕｎｉｃｏｄｅの文字コード空間における文字の値の有効ビット幅２１ビットの中で、下位から７、１、１、１，１、１０ビット毎にビット転置処理・交互配置処理を適用している。すなわち、文字１の値と文字２の値からそれぞれ下位の７ビットずつを取り出し、それをＮ−ｇｒａｍ識別番号の上位１４ビットにセットする。文字１、文字２の値の下位８ビット目から１１ビット目については、交互に取り出して、Ｎ−ｇｒａｍ識別番号の上位１５ビット目から２２ビット目にセットする。そして、文字１、文字２の値の下位１２ビット目から２１ビット目を取り出し、Ｎ−ｇｒａｍ識別番号の上位２３ビット目から４２ビット目にセットし、残りの４３ビット目から６４ビット目には０をセットする。図１９に示した例と異なるのは、Ｎ−ｇｒａｍ識別番号の上位１５ビット目から２２ビット目に対して、文字１と文字２から１ビットずつ順に取り出し交互に配置する点である。こうすることにより、索引情報１１１のブロック３０５の数を多少変化させても（この例の場合は、ブロック３０５の数を１６３８４（＝２１４）から４１９４３０４（＝２２２）まで変化させても）、同じ算出方法を適用することができる。
Ｎ−ｇｒａｍ識別番号の上位何ビット目から何ビット目までを文字１と文字２から１ビットずつ取り出し交互に配置するかは、ブロック３０５の数が変化する可能性のある範囲に応じて決定すればよい。
なお、ここでは、２−ｇｒａｍの場合について説明したので、Ｎ−ｇｒａｍ識別番号の上位１５ビット目から２２ビット目に対して、文字１と文字２から１ビットずつ取り出し交互に配置したが、Ｎ＝３以上のＮ−ｇｒａｍの場合には、Ｎ−ｇｒａｍ識別番号の上位１５ビット目から２２ビット目に対して、各文字から順に１ビットずつ取り出して順に配置すればよい。
【０１０７】
この他にも、式１０のように３−ｇｒａｍＣｉＣｊＣｋに対するＮ−ｇｒａｍ識別番号Ｘｉｊｋを算出するようにしてもよい。
（式１０）  Ｘｉｊｋ＝ＩＮＶ６４（ＡＬＴ６４Ｍ（Ｃｉ，Ｃｊ，Ｃｋ））  （Ｍ＝１，２，・・・，２１）
【０１０８】
以上のように、実施の形態３に係る文書検索装置１００は、Ｎ−ｇｒａｍ識別番号の算出における交互配置処理を、１ビット単位ではなく２ビット以上の複数ビット単位で実施する。これにより、Ｎ−ｇｒａｍ識別番号の算出処理の負荷を削減できる。
【０１０９】
実施の形態４．
実施の形態４では、実施の形態１や実施の形態３とは異なるＮ−ｇｒａｍ識別番号の算出方法について説明する。
なお、実施の形態４に係る文書検索装置１００の構成は、図２に示す実施の形態１に係る文書検索装置１００の構成と同様である。
【０１１０】
実施の形態４に係る文書検索装置１００による索引情報１１１を作成する処理と、検索キーワードを検索する処理とについて、実施の形態１に係る文書検索装置１００による処理と異なる部分のみを説明する。実施の形態４に係る文書検索装置１００による索引情報１１１を作成する処理と検索キーワードを検索する処理とは、図５の（Ｓ１６）と図６の（Ｓ２３）とにおけるＮ−ｇｒａｍ識別番号の算出方法のみ実施の形態１に係る文書検索装置１００による処理と異なる。
【０１１１】
実施の形態１や実施の形態３では、Ｎ−ｇｒａｍからＮ−ｇｒａｍ識別番号を算出するために、選択部１０３がビット転置処理や交互配置処理を行った。実施の形態４では、選択部１０３がビット転置処理や交互配置処理を行うことなく、Ｎ−ｇｒａｍ識別番号を算出する。
【０１１２】
まず、選択部１０３は、Ｎ−ｇｒａｍ識別番号のビット幅を最大文字数Ｎで割った値をシフト演算の基数ｓとする。例えば、実施の形態１の例では、Ｎ−ｇｒａｍ識別番号のビット幅は６４ビット、最大のＮは３であるため、６４を３で割って基数ｓは２１となる。
次に、選択部１０３は、Ｎ−ｇｒａｍを構成する各文字について、Ｎ−ｇｒａｍの先頭からの文字数ｉを用いて、その文字の文字コードをｓ×（Ｎ−ｉ）ビット上位にシフトする。つまり、基数ｓが２１であり、３−ｇｒａｍＣｉＣｊＣｋであれば、選択部１０３は、１文字目のＣｉについては（２１×（３−１））ビット、つまり４２ビット文字コードを上位にシフトする。また、選択部１０３は、２文字目のＣｊについては、（２１×（３−２））ビット、つまり２１ビット文字コードを上位にシフトする。また、選択部１０３は、３文字目のＣｋについては、（２１×（３−３））ビット、つまり０ビット文字コードを上位にシフトする。
そして、選択部１０３は、シフトした文字コードの値を加算して、Ｎ−ｇｒａｍ識別番号とする。
例えば、選択部１０３は、３−ｇｒａｍＣｉＣｊＣｋに対するＮ−ｇｒａｍ識別番号Ｘｉｊｋを式１１のように算出する。
（式１１）  Ｘｉｊｋ＝（Ｃｉ＜＜４２）＋（Ｃｊ＜＜２１）＋（Ｃｋ＜＜０）
【０１１３】
選択部１０３は、算出したＮ−ｇｒａｍ識別番号を、ブロック３０５の数で割った余剰を、Ｎ−ｇｒａｍ位置情報３０６が格納されるブロック番号とする。
【０１１４】
これにより、少なくとも隣接するＮ−ｇｒａｍに関するＮ−ｇｒａｍ位置情報３０６を、異なるブロック３０５に格納できる。
この方式（ラウンドロビン方式）でも、Ｎ−ｇｒａｍ位置情報３０６を格納するブロック３０５の決定する際の算出処理の負荷を軽減できる。
【０１１５】
実施の形態５．
実施の形態５では、Ｕｎｉｃｏｄｅの文字に加えて、文書検索装置１００で独自に定義する拡張文字を扱う場合について説明する。
【０１１６】
拡張文字とは、例えば、２種類以上の文字の組を同一視した同一視文字である。
例えば、Ｕｎｉｃｏｄｅにおいて、英字「ａ」には、大文字・小文字と全角・半角で４通りの字形の文字が存在する。実施の形態１に係る文書検索装置１００において、単純に検索を実行すると、これら４文字は異なる文字として検索される。そのため、検索キーワードに半角・小文字の「ａ」を指定して検索を実行すると、例えば、半角・大文字の「Ａ」が検索の対象から漏れて、所望の検索結果が得られない場合がある。
【０１１７】
そこで、２種類以上の文字の組を同一視した検索をしたい場合、文字コード空間に、その２種類以上の文字の組を同一視したことを示す同一視文字を定義する。
例えば、文字コード空間の文字が割り当てられていない領域に、半角・小文字、半角・大文字、全角・小文字、全角・大文字の「ａ」を全て同一視したことを示す同一視文字を定義する。同一視文字を含む文字コード空間の文字数をＮｃ’とすると、ｌｏｇ２Ｎｃ’ビットの数値の中から、同一視文字の値（文字コード）を決定すればよい。例えば、実施の形態１のＵｎｉｃｏｄｅを使った場合を例にすると、「０ｘ００」から「０ｘ１０ＦＦＦＦ」までの範囲で、文字が割り当てられていない範囲に同一視文字を定義してもよいし、「０ｘ１１００００」（Ｕｎｉｃｏｄｅで定義された文字の最大値＋１）から「０ｘ１ＦＦＦＦＦ」（２１ビット整数の最大値）までの範囲に同一視文字を定義してもよい。
【０１１８】
ここで、同一の言語に属する文字の同一視文字に対して連続値を割り当てることが望ましい。
例えば、英字の場合は、半角・小文字、半角・大文字、全角・小文字、全角・大文字の「ａ」を全て同一視したことを示す同一視文字の値を「０ｘ１１００００」、半角・小文字、半角・大文字、全角・小文字、全角・大文字の「ｂ」を全て同一視したことを示す同一視文字の値を「０ｘ１１０００１」、・・・、半角・小文字、半角・大文字、全角・小文字、全角・大文字の「ｚ」を全て同一視したことを示す同一視文字の値を「０ｘ１１００２５」のように割り当てる。
また、その後の値として、半角・小文字の「ａ」と半角・大文字の「Ａ」だけを同一視したことを示す同一視文字のように、同じ文字種で異なる形態の文字を同一視したことを示す同一視文字を定義してもよい。さらに、その後の値として、数字や英語以外の欧州言語についての同一視文字を定義し、日本語やそれ以外の言語についての同一視文字を定義してもよい。
【０１１９】
図２１は、実施の形態５に係る文書検索装置１００の機能を示す機能ブロック図である。
図２１に示す実施の形態５に係る文書検索装置１００は、図１に示す実施の形態１に係る文書検索装置１００が備える機能に加え、拡張文字記憶部１１４（拡張文字コード管理テーブル）を備える。拡張文字記憶部１１４は、同一視する文字（例えば、半角・小文字、半角・大文字、全角・小文字、全角・大文字の「ａ」）と、その文字に対応する同一視文字に割り当てられた文字コード空間における値（上記例であれば、「０ｘ１１００００」）との組を記憶する。
また、拡張文字記憶部１１４は、同時に、ある文字と関連している同一視文字の一覧を記憶しておいてもよい。例えば、拡張文字記憶部１１４は、半角・小文字の「ａ」であれば、半角・小文字、半角・大文字、全角・小文字、全角・大文字の「ａ」を全て同一視したことを示す同一視文字と、半角・小文字の「ａ」と半角・大文字の「Ａ」だけを同一視したことを示す同一視文字とを一覧として記憶しておいてもよい。
【０１２０】
実施の形態５に係る文書検索装置１００による索引情報１１１を作成する処理について、実施の形態１に係る文書検索装置１００による処理と異なる部分のみを説明する。実施の形態５に係る文書検索装置１００による索引情報１１１を作成する処理は、図５の（Ｓ１５）と（Ｓ１６）とのみが実施の形態１に係る文書検索装置１００による処理と異なる。
【０１２１】
（Ｓ１５）では、抽出部１０２は、現在ポインタがセットされている位置の出現位置情報を処理装置により抽出する。また、抽出部１０２は、抽出した出現位置情報が示す位置におけるＮ−ｇｒａｍを処理装置により抽出する。この時、抽出したＮ−ｇｒａｍの中に同一視文字を持つ文字が含まれている場合は、その文字を同一視文字に置き換えたＮ−ｇｒａｍも抽出する。なお、複数の同一視文字を持つ文字が含まれる場合には、その文字を各同一視文字に置き換えたＮ−ｇｒａｍを抽出する。
具体的には、抽出部１０２は、拡張文字記憶部１１４を参照して、現在ポインタがセットされている位置から抽出したＮ−ｇｒａｍに、同一視文字が含まれているか否かを判定する。抽出部１０２は、同一視文字を持つ文字が含まれていた場合は、その文字と同一視文字とを置き換えたＮ−ｇｒａｍを抽出する。
【０１２２】
（Ｓ１６）では、選択部１０３は、（Ｓ１５）で抽出されたＮ−ｇｒａｍについて、抽出した出現位置情報を格納するブロック３０５を選択する。なお、（Ｓ１５）で抽出されたＮ−ｇｒａｍには、ポインタがセットされた位置のＮ−ｇｒａｍと、そのＮ−ｇｒａｍの一部の文字を同一視文字に置き換えたＮ−ｇｒａｍとが含まれる。
【０１２３】
実施の形態５に係る文書検索装置１００による検索キーワードを検索する処理について、実施の形態１に係る文書検索装置１００による処理と異なる部分のみを説明する。実施の形態５に係る文書検索装置１００による検索キーワードを検索する処理は、（Ｓ２１）と（Ｓ２３）と（Ｓ２７）とのみが実施の形態１に係る文書検索装置１００による処理と異なる。
ここでは、索引情報１１１には、１−ｇｒａｍ、２−ｇｒａｍ、３−ｇｒａｍの出現位置情報が格納されているものとする。
【０１２４】
（Ｓ２１）では、検索条件入力部１０５は、検索キーワードに加えて、どの文字を同一とみなすか否かを示すフラグの情報（異表記フラグ）を指定した検索条件１２１を入力装置により入力する。
【０１２５】
（Ｓ２３）では、読出部１０６は、検索キーワードと異表記フラグとから読み出すブロック番号をブロック管理テーブル１０９から取得する。
まず、読出部１０６は、読出部１０６は、検索キーワードからＮ−ｇｒａｍを処理装置により抽出する。つまり、読出部１０６は、実施の形態１と同様に、検索キーワードを先頭から順に３文字に分割する。次に、読出部１０６は、抽出したＮ−ｇｒａｍに他の文字と同一視する文字が含まれている場合、つまり、Ｎ−ｇｒａｍに異表記フラグが同一視する文字であることを示す文字が含まれる場合、そのＮ−ｇｒａｍにおける他の文字と同一視する文字を、同一視文字に置き換えたＮ−ｇｒａｍを生成する。
例えば、検索キーワードが「Ｎ−ｇｒａｍ」であり、異表記フラグが文字「Ｎ」については大文字と小文字を同一視するが、その他の文字についてはいかなる同一視もしないと示すとする。この場合、読出部１０６は、検索キーワードを３文字ずつに、「Ｎ−ｇ」と「ｒａｍ」との分割文字情報に分割する。さらに、読出部１０６は、「Ｎ−ｇ」の文字「Ｎ」を「Ｎ」の同一視文字に置き換えた３−ｇｒａｍを生成する。
そして、選択部１０３は、読出部１０６が同一視文字に置き換えて生成したＮ−ｇｒａｍについて、Ｎ−ｇｒａｍ識別番号を算出して、ブロック番号を取得する。
【０１２６】
（Ｓ２７）では、検索部１０７は、バッファに読み出したブロック３０５から、（Ｓ２３）で抽出した各Ｎ−ｇｒａｍについてのＮ−ｇｒａｍ位置情報３０６を抽出して、検索キーワードの出現位置情報を処理装置により検索する。
なお、検索部１０７は、先頭の分割文字情報の文字を同一視文字に置き換えて生成したＮ−ｇｒａｍは先頭の分割文字情報として扱い、２番目の分割文字情報の文字を同一視文字に置き換えて生成したＮ−ｇｒａｍは２番目の分割文字情報として扱う。３番目の分割文字情報以降も同様である。
つまり、上記例において、先頭の分割文字情報である「Ｎ−ｇ」の文字「Ｎ」を「Ｎ」の同一視文字に置き換えた３−ｇｒａｍを先頭の分割文字情報として扱う。したがって、まず、検索部１０７は、先頭の分割文字情報（「Ｎ−ｇ」の文字「Ｎ」を「Ｎ」の同一視文字に置き換えた３−ｇｒａｍ）のＮ−ｇｒａｍ出現位置情報３１０を全て抽出する。そして、検索部１０７は、抽出した各Ｎ−ｇｒａｍ出現位置情報３１０に３を加えた位置を示す出現位置情報が、分割文字情報２のＮ−ｇｒａｍ位置情報３０６におけるＮ−ｇｒａｍ出現位置情報３１０として格納されているか否かを判定する。これにより、検索部１０７は、検索キーワードの出現位置を検索する。
【０１２７】
以上のように、実施の形態５に係る文書検索装置１００は、拡張文字記憶部１１４を備え、文書検索装置１００で独自に定義する拡張文字を記憶することにより、その拡張文字を利用した検索が可能である。
ここで、拡張文字は、Ｕｎｉｃｏｄｅで定義されていない外字のようなものでもよいし、複数の文字を同一視するための同一視文字でもよい。また、拡張文字が同一視文字の場合には、同一の言語に属する文字に関連する同一視文字に対して連続値（連続した文字コード）を割り当てることにより、その同一視文字に関するＮ−ｇｒａｍ位置情報３０６が、同一のブロック３０５に格納されないようにすることができる。したがって、ブロック３０５のサイズの偏りを抑止することができる。これにより、ブロック３０５のサイズの偏りに起因する検索速度の低下を防止し、文字情報を高速に検索することができる。
【０１２８】
実施の形態６．
実施の形態６では、文書検索装置１００において、Ｎ−ｇｒａｍ識別番号の算出に用いる文字の値を、Ｕｎｉｃｏｄｅの文字コード空間における文字の値ではなく、Ｕｎｉｃｏｄｅから文字の配置を変更した中間文字コードにおける値とする場合について説明する。
【０１２９】
特に実施の形態３で説明したとおり、文書検索装置１００では、索引情報１１１のブロック３０５の数ＮＢのビット幅に応じて、異なるブロック３０５に割り当てられるＮ−ｇｒａｍ識別番号の範囲が決まってくる。そこで、Ｕｎｉｃｏｄｅの文字コード空間における文字の値に替えて、新たな中間文字コードを定義することにより、ブロック３０５のサイズの均等化を図ることが可能になる。
具体的には、Ｎ−ｇｒａｍ位置情報３０６のサイズが大きくなると予想されるＮ−ｇｒａｍを構成する文字（以下、頻出文字と呼ぶ）を、文字コード空間上の限られた範囲に配置し直した中間文字コードを定義する。頻出文字は、言い換えれば出現頻度が高い文字であり、その様な文字として例えば、ＡＳＣＩＩ文字や実施の形態４で説明した同一視文字がある。
ＡＳＣＩＩ文字は、英語圏や日本語に限らず、多くの言語の文書に出現する。特に、メールやＷｅｂなどの分野では、言語を問わず出現頻度が高い。また、同一視文字については、例えば、半角・小文字、半角・大文字、全角・小文字、全角・大文字の「ａ」のいずれかを含むＮ−ｇｒａｍは、半角・小文字の「ａ」を含むＮ−ｇｒａｍと比較して、単純計算でも２から４倍出現する可能性があり、出現頻度が高いと考えられる。
【０１３０】
このような、頻出文字を割り当てる範囲は、索引情報１１１のブロック３０５の数ＮＢとＮ−ｇｒａｍの最大の文字数Ｎの値によって定めることができる。
例えば、ブロック３０５の数ＮＢのビット幅をＮＢ’とすると、中間文字コード空間の先頭からＮＢ’／Ｎビットの範囲に、配置可能な範囲で、上記のＮ−ｇｒａｍ位置情報３０６のサイズが大きいＮ−ｇｒａｍに関する文字を割り当てる。それ以外の文字については、中間文字コードの先頭の領域に割り当てを変更した文字数分、Ｕｎｉｃｏｄｅの文字コード空間における値に加えることで、文字の値を定義し直す。つまり、１００文字の中間文字コードを割り当てた場合には、他の文字についてはＵｎｉｃｏｄｅの文字コード空間における値に１００加えた値を割り当てる。
中間文字コードを定義したあとは、実施の形態１から実施の形態３で示したものとほぼ同様の方法で、Ｎ−ｇｒａｍに含まれる文字の中間文字コード上の文字の値から、Ｎ−ｇｒａｍ識別番号を算出すればよい。そうすることにより、中間文字コードの先頭ＮＢ’／Ｎビットの範囲に配置した文字に関しては、Ｎ−ｇｒａｍ位置情報３０６が同じブロック３０５に対応しないことが保証される。
【０１３１】
図２２は、実施の形態６に係る文書検索装置１００の機能を示す機能ブロック図である。
図２２に示す実施の形態６に係る文書検索装置１００は、図１に示す実施の形態１に係る文書検索装置１００が備える機能に加え、中間文字コード記憶部１１５（中間文字コード管理テーブル）を備える。中間文字コード記憶部１１５は、Ｎ−ｇｒａｍ位置情報３０６のサイズが大きいＮ−ｇｒａｍに関する文字（例えば、実施の形態４の同一視文字）を、文字コード空間上の先頭領域に配置し、ＡＳＣＩＩ文字以降の文字を、文字コード空間上の先頭領域に配置した文字数分シフトさせた、中間文字コードを記憶する。
【０１３２】
実施の形態６に係る文書検索装置１００による索引情報１１１を作成する処理について、実施の形態１に係る文書検索装置１００による処理と異なる部分のみを説明する。実施の形態６に係る文書検索装置１００による索引情報１１１を作成する処理は、図５の（Ｓ１６）のみが実施の形態１に係る文書検索装置１００による処理と異なる。
【０１３３】
（Ｓ１６）では、選択部１０３は、（Ｓ１５）で抽出されたＮ−ｇｒａｍについて、抽出した出現位置情報を格納するブロック３０５を選択する。このとき選択部１０３は、Ｎ−ｇｒａｍに含まれる文字の値を、中間文字コード記憶部１１５から抽出し、その値を用いてＮ−ｇｒａｍ識別番号を算出して、ブロック番号を取得する。
【０１３４】
実施の形態６に係る文書検索装置１００による検索キーワードを検索する処理について、実施の形態１に係る文書検索装置１００による処理と異なる部分のみを説明する。実施の形態６に係る文書検索装置１００による検索キーワードを検索する処理は、（Ｓ２３）のみが実施の形態１に係る文書検索装置１００による処理と異なる。
【０１３５】
（Ｓ２３）では、読出部１０６は、検索キーワードから読み出すブロック番号をブロック管理テーブル１０９から取得する。
まず、読出部１０６は、検索キーワードからＮ−ｇｒａｍを処理装置により抽出する。そして、選択部１０３は、読出部１０６が検索キーワードを分割して抽出したＮ−ｇｒａｍに含まれる文字の値を、中間文字コード記憶部１１５から抽出し、その値を用いてＮ−ｇｒａｍ識別番号を算出して、ブロック番号を取得する。
【０１３６】
実施の形態１から実施の形態４では、文書検索装置１００における言語毎の出現頻度や、個別の言語内での文字の出現頻度などに仮定を設けない、汎用的な文書検索装置１００について示した。ここでは、文書検索装置１００が扱う文書の言語や、文字の出現頻度に、ある前提を設ける場合の応用についても説明する。
ここでは、例として日本語を主に扱う文書検索装置１００の場合について説明する。つまり、実施の形態６の文書検索装置１００に入力される文書情報１２０の大部分は日本語文字で記述されたものであり、残りの一部分が少数の他言語文字で記述されたものである場合である。このような文書検索装置１００では、頻出文字として、ＡＳＣＩＩ文字に加えて、ひらがな、カタカナ、半角英数字や、ひらがな・カタカナにおける同一視文字がある。ひらがな、カタカナ、半角英数字は、日本語の文書においては出現頻度が高いことは明らかである。また、ひらがな・カタカナにおける同一視文字とは、例えば、ひらがなやカタカナの大文字と小文字との組や、カタカナの全角文字と半角文字のとの組である。
図２３に具体例を示す。ここでは、索引情報１１１のブロック数は２６２，１１４個、つまりブロック番号は最大で１８ビットの整数値で表すことのできる数であるとする。また、索引情報１１１のＮの最大値は２とする。この場合、ＮＢ’／Ｎ＝９である。
Ｕｎｉｃｏｄｅの文字コード空間では、先頭にＡＳＣＩＩが配置され、ひらがな／カタカナ、漢字の順序で出現する。図２３の中間文字コードの例では、まず先頭にひらがな・カタカナを配置している。続いてひらがな・カタカナの同一視する文字を配置している。続いて、ＡＳＣＩＩの同一視する文字で、これは例を実施の形態４で示した。その次はＡＳＣＩＩ文字である。ＡＳＣＩＩ文字以降は、中間文字コードの先頭領域に割り当てた文字数分、Ｕｎｉｃｏｄｅの文字コード空間における配置位置からシフトさせる。このように中間文字コードを定義することにより、中間文字コードが割り当てられた文字を含む２−ｇｒａｍについては、Ｎ−ｇｒａｍ位置情報３０６が異なるブロック３０５に格納される。
【０１３７】
ここまでの説明では、索引情報１１１のブロック３０５の数をＮＢとしているが、実施の形態２で説明したように、Ｎ−ｇｒａｍのＮ毎に、Ｎ−ｇｒａｍ位置情報を格納するブロック３０５を予め決めている場合は、最大文字数であるＮについてのブロック数ＮＢＮ−ｇｒａｍをブロック３０５の数として考えればよい。
【０１３８】
また、実施の形態２では、Ｎ−ｇｒａｍのＮ毎に、Ｎ−ｇｒａｍ位置情報３０６を格納するブロック３０５を予め決めた。実施の形態６では、実施の形態２と同様の考え方に基づき、頻出文字を含むＮ−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６を格納するブロックを予め決めておいてもよい。つまり、頻出文字を含むＮ−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６と、頻出文字を含まないＮ−ｇｒａｍのＮ−ｇｒａｍ位置情報３０６とを別のブロック３０５に格納するようにしてもよい。
【０１３９】
以上のように、実施の形態６に係る文書検索装置１００は、中間文字コード記憶部１１５を備え、Ｎ−ｇｒａｍ位置情報３０６のサイズが大きいＮ−ｇｒａｍに関する文字を、先頭の領域に配置し直した中間文字コードを記憶する。索引情報１１１作成時には、中間文字コード記憶部１１５より抽出した文字の値を用いてＮ−ｇｒａｍ識別番号を算出し、ブロック番号を算出することにより、サイズの大きいＮ−ｇｒａｍ位置情報３０６が、同一のブロック３０５に格納されないようにすることができる。したがって、ブロック３０５のサイズの偏りを抑止することができる。これにより、ブロック３０５のサイズの偏りに起因する検索速度の低下を防止し、文字情報を高速に検索することができる。
【０１４０】
なお、上記説明では、中間文字コード空間の先頭に頻出文字を割り当てるとした。しかし、頻出文字は、中間文字コード空間の先頭以外の場所であっても、連続する値が割り当てられていればよい。
【０１４１】
以上をまとめると次のようになる。
以上の実施の形態に係る文書検索装置１００は、
ブロック化閾値以下の文書単位毎に、Ｎ−ｇｒａｍに関連する位置情報をブロックとして格納する手段を備えたＮ−ｇｒａｍ索引方式の文書検索装置１００であり、以下のことを特徴とする。
Ｎ−ｇｒａｍに関連する位置情報を格納する先のブロックを決定するブロック選択手段を備える。
ブロック選択手段は、Ｎ文字の組に含まれる各文字を表す値に対して、値の上位ビットと下位ビットとを入れ替えるビット転置処理、Ｎ個の値から交互に任意の幅で取り出したビットを、取り出した順序で配置する処理を繰り返す交互配置処理を適用してＮ−ｇｒａｍ識別番号を算出する。
Ｎ−ｇｒａｍ識別番号の種類数をブロックの数で割った商をＮ−ｇｒａｍ格納数とする。
ブロック選択手段は、Ｎ−ｇｒａｍ識別番号の数値を予め定められた順序で整列し、その先頭から順にＮ−ｇｒａｍ格納数ずつ同じブロックに割り当てることにより、元のＮ−ｇｒａｍに関連する位置情報を格納するブロックを決定する。
検索時においては、検索キーワードに含まれるＮ以下の文字の組に関する位置情報を格納したブロックを、上記と同様の手順で選択し、Ｎ−ｇｒａｍ位置情報を読み出して照合することにより検索結果を出力する。
【０１４２】
ブロック選択手段において、Ｎ文字の組に含まれる各文字に対して、その値（第１の数値）にビット転置処理を適用して第２の数値を算出し、Ｎ個の第２の数値から１以上の固定のビット幅でビットを取り出し配置する交互配置処理を適用して得られた第三の数値をＮ−ｇｒａｍ識別番号とすることを特徴とする。
【０１４３】
Ｎ−ｇｒａｍに関連する位置情報に加え、１からＮ−１までに対しても、１−ｇｒａｍから（Ｎ−１）−ｇｒａｍのＮ−ｇｒａｍ識別番号を算出し、ブロックに割り当てることにより、１−ｇｒａｍから（Ｎ−１）−ｇｒａｍまでに関連する位置情報を格納することを特徴とする。
【０１４４】
Ｎ−ｇｒａｍのＮ毎にＮ−ｇｒａｍ位置情報を格納するブロックを予め定めておく。Ｎ毎にＮ−ｇｒａｍ識別番号の種類数を、ブロックの数で割ったＮ−ｇｒａｍ格納数を得る。また、ブロック選択手段は、Ｎ−ｇｒａｍ識別番号をＮ毎に予め定められた順序で整列し、その先頭から順にＮ毎のＮ−ｇｒａｍ格納数ずつ同じブロックに割り当てることにより、元のＮ−ｇｒａｍに関連する位置情報を格納するブロックを決定することを特徴とする文書検索装置。
【０１４５】
Ｎ−ｇｒａｍ索引に含まれる最大のＮに対してＮ文字以上の長さの検索キーワードによる検索の場合には、検索キーワードを丁度Ｎ文字ずつに分解し、それらに関するＮ−ｇｒａｍ位置情報を読み出して出現位置を照合することを特徴とする。
【０１４６】
文書検索装置１００は、さらに、拡張文字コード管理テーブルを備え、以下のことを特徴とする。
文書検索装置１００は、検索対象とする元の文字コードに加えて、その文書検索装置独自の拡張文字を定義し、その文字が同一の言語に関連付いたものである場合には、それぞれに連続もしくは近接した値を割り当てて、上記拡張文字コード管理テーブルに記憶する。
Ｎ文字の組からＮ−ｇｒａｍ識別番号の算出において、そのＮ文字の中に上記拡張文字そのもの、もしくは関連した文字が含まれていた場合は、その拡張文字の値を使ってＮ−ｇｒａｍ識別番号を算出する。
【０１４７】
文書検索装置１００は、さらに、中間文字コード管理テーブルを備え、以下のことを特徴とする。
文書検索装置１００は、元の文字コードの一部の文字や、その文書検索装置独自の拡張文字を、文字空間上の先頭の領域に配置した中間文字コードを定義し、上記中間文字コード管理テーブルに記憶する。
Ｎ文字の組からＮ−ｇｒａｍ識別番号の算出において、そのＮ文字の文字の値を、前記中間文字コード管理テーブルから抽出し、その値を使ってＮ−ｇｒａｍ識別番号を算出する。
【０１４８】
次に、上述した実施の形態における文書検索装置１００のハードウェア構成について説明する。
図２４は、文書検索装置１００のハードウェア構成の一例を示す図である。
図２４に示すように、文書検索装置１００は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、演算装置、演算回路、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ９１１は、バス９１２を介してＲＯＭ９１３、ＲＡＭ９１４、ＬＣＤ９０１（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）、キーボード９０２（Ｋ／Ｂ）、通信ボード９１５、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置９２０（固定ディスク装置）の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。磁気ディスク装置９２０は、所定の固定ディスクインタフェースを介して接続される。
【０１４９】
ＲＯＭ９１３、磁気ディスク装置９２０は、不揮発性メモリの一例である。ＲＡＭ９１４は、揮発性メモリの一例である。
【０１５０】
磁気ディスク装置９２０又はＲＯＭ９１３などには、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。プログラム群９２３のプログラムは、ＣＰＵ９１１、オペレーティングシステム９２１、ウィンドウシステム９２２により実行される。
【０１５１】
プログラム群９２３には、上記の説明において「文書入力部１０１」、「抽出部１０２」、「選択部１０３」、「格納部１０４」、「検索条件入力部１０５」、「読出部１０６」、「検索部１０７」、「検索結果出力部１０８」等として説明した機能を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
ファイル群９２４には、上記の説明において「文書情報１２０」、「検索条件１２１」、「検索結果情報１２２」として記憶される情報やデータや信号値や変数値やパラメータ、記憶装置１１０やバッファに記憶される情報やデータや信号値や変数値やパラメータが、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵ９１１の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵ９１１の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
【０１５２】
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、その他光ディスク等の記録媒体やＩＣチップに記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体や電波によりオンライン伝送される。
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組合せ、さらには、ファームウェアとの組合せで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ＲＯＭ９１３等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
【符号の説明】
【０１５３】
１００  文書検索装置、１０１  文書入力部、１０２  抽出部、１０３  選択部、１０４  格納部、１０５  検索条件入力部、１０６  読出部、１０７  検索部、１０８  検索結果出力部、１０９  ブロック管理テーブル、１１０  記憶装置、１１１  索引情報、１１２  管理情報、１１３  位置情報、１１４  拡張文字記憶部、１２０  文書情報、１２１  検索条件、１２２  検索結果情報、３０１  管理情報ページ、３０２  ブロック内文書数、３０３  ブロック格納位置、３０４  位置情報ページ、３０５  ブロック、３０６  Ｎ−ｇｒａｍ位置情報、３０７  文書内位置情報、３０８  文書番号、３０９  出現回数、３１０  Ｎ−ｇｒａｍ出現位置情報。
【図１】
2011021282.tif 000003
【図２】
2011021282.tif 000004
【図３】
2011021282.tif 000005
【図４】
2011021282.tif 000006
【図５】
2011021282.tif 000007
【図６】
2011021282.tif 000008
【図７】
2011021282.tif 000009
【図８】
2011021282.tif 000010
【図９】
2011021282.tif 000011
【図１０】
2011021282.tif 000012
【図１１】
2011021282.tif 000013
【図１２】
2011021282.tif 000014
【図１３】
2011021282.tif 000015
【図１４】
2011021282.tif 000016
【図１５】
2011021282.tif 000017
【図１６】
2011021282.tif 000018
【図１７】
2011021282.tif 000019
【図１８】
2011021282.tif 000020
【図１９】
2011021282.tif 000021
【図２０】
2011021282.tif 000022
【図２１】
2011021282.tif 000023
【図２２】
2011021282.tif 000024
【図２３】
2011021282.tif 000025
【図２４】
2011021282.tif 000026
【国際調査報告】
2011021282.tif 000027
2011021282.tif 000028
2011021282.tif 000029
2011021282.tif 000030