JPH10501912A - Ｎグラム・ワード分解を用いた携帯型文書索引付け用のシステム及び方法 - Google Patents

Abstract

(57)【要約】 ｎグラム又は線形ワード副単位への文書内のワードの分解を用いて、格納されている文書の索引付け及び検索を行うためのシステム及び方法を提供すること。文書は、多数のバンク内のページとして索引付けられる。各バンクに対して、１つのバンク索引が存在する。個々のｎグラムは、各ページに対して識別されて、バンク索引内に格納される。各バンク索引は更に、所与のｎグラムがバンクのページのいずれかに存在するか否かを示し、次いで、バンク内のどのページがｎグラムを含むかを更に示すページマップに、索引を与える。探索照会が入力されると、照会ワードが、それらのｎグラムへと分解される。照会ワードｎグラムは、先ずエントリマップと比較されて、照会ワードｎグラムが、バンク内のいずれかのページに出現するか否かが判定される。出現する場合、関連したページマップが走査されて、バンク内のどのページが、照会ワードｎグラムを含むかが判定される。そのページのｎグラムが、照会ワードｎグラムと比較されて、それらの間の一致の存在が判定される。一致ページが掲げられる。全てのバンク内の全てのページの処理が完了すると、ページは、それらが属する文書に関して統合され、それにより結果として、探索照会に一致する文書リストとなる。結果はユーザに表示される。

Description

【発明の詳細な説明】 Ｎグラム・ワード分解を用いた携帯型文書索引付け用のシステム及び方法 背景 発明の分野 本発明は、光学式スキャナ及び光学式文字認識による文書処理の分野に関し、 更に詳細には、後の探索及び検索のために、文書内のワードに索引付けするシス テム及び方法に関する。 発明の背景 光学式文字認識（ＯＣＲ）は、コンピュータ読み取り可能形式で、印刷及び手 書き文書を捕捉するために広く用いられ、それにより、文書を、情報検索システ ムを用いて後で探索及び検索することが可能になる。完全テキスト検索能力を備 えた典型的な情報検索システムは、システムへと入力される文書中のあらゆる重 要なワードに索引付けし、索引内の各ワードに対して、通常文書、ページ、及び ある型式のワードオフセット、又は他の類似型式の連係により、ワードが発生す る場所の識別子のリストをもたらす。文書は、入力探索照会に応答して検索され るが、これは、探索照会中のワードと索引中のワードとの正確な一致をとり、ワ ードに対し索引付けられた文書を検索することによりなされる。ブール探索演算 子が通常与えられるので、複雑な探索照会が可能となる。 従って、入力文書の正確な検索は、主に、正確な入力及びＯＣＲ解析に頼って いる。ＯＣＲシステムは、一般に、文字、フォント型 式、フォントサイズ、ページ割付、画像分解能、及び画像品質間の空間隔差に非 常に敏感である。従って、９９％の精度を有する高精度ＯＣＲシステムでさえも 、１００個に１個は文字を誤解釈することになり、その結果、レター置換、レタ ー喪失、又は同様の綴りエラーとなる。結果として、典型的なＯＣＲ処理文書は その後、任意の場所に３から８個の、又は更に多くのページ単位の間違った綴り すなわちエラーを有することになる。これには、文書に元々存在する誤植は含ま れない。他の問題は、ＯＣＲシステムが別個のワードを共に実行するという点に ある。 綴りの間違ったワードは適切には索引付けされず、従って、適切な綴りのワー ドを含む探索照会に応答している間は検索されないことになる。同様に、同時進 行ワード列中の個々のワードは、全く索引付けされず、唯一、ワード列全体の一 部として索引付けされ、従って、ワード列中の個々のワードのどれもが、かかる ワードを特定する探索照会に応答して検索されないことになる。 綴り間違いの問題に対する通常の解決策は、シソーラス又は類似デバイスに頼 って、共通の間違った綴りをそれらの正確な綴りの供給源に索引付けするもので ある。この手法に伴う１つの問題は、それが、共通でない間違った綴りを考慮し ない点にある。これらの手法は又、索引のサイズを大幅に増大させ、このことが 、情報検索システム設計の別の側面に結びついた。 情報検索システムにおける第２の主要問題は、索引を作成し維持するのに要す る性能、及び時間である。通常、反転索引が、二重連 結リスト等の単一の一枚岩データ構造、又はツリー構造として維持される。新規 の文書が、オンライン・データベースに対して日常的であるシステムに追加され る度に、索引全体を調整する必要があり、また入力文書に出現する索引中の各ワ ード登録が、入力文書に対する等価データで更新される必要がある。これは、オ ンライン索引付けを大型システムに対して不適切にするため、索引付けはオフラ インで実行され、それにより、追加文書を探索できる素早さが制限される。加え て、索引が詳細になるほど、索引付け処理に多くの時間が費やされる。しかし、 索引付け時間と探索時間との間には、妥協点が存在する。 最後に、情報システムについての他の関心事は、付随又はクライアントシステ ムと共に利用するために、索引付き文書を交換する能力である。目下のところ、 多数のソフトウェア・アプリケーション、特に、データベース及び情報システム が、クライアント−サーバに基づいている。加えて、絶えず数が増大する携帯型 コンピュータがある。これらの要因により、再索引付けに相当のオーバーヘッド なしに探索するために、索引付き文書を、索引付けシステムに効率的に付加し、 又は索引付けシステムから外すことを可能にする、索引付けシステムを提供する ことが望まれる。慣用的な情報検索システムは、携帯型でないモノリシック反転 索引を使用する。というのは、この索引は、多数メガバイト、又はギガバイトす らあり、文書のページの数万倍となる。このサイズの索引、すなわちこの複雑な 索引は、遠隔のクライアント、携帯型コンピュータ装置、又は着脱可能 な記憶媒体に都合良く転送することができない。 従って、ＯＣＲ解析からであろうとなかろうと、入力文書中のエラーを補償し て、高速の索引付け、及び間違った綴り又は他の誤植を含んだ文書の正確な検索 を可能にする索引付けシステムを提供することが望まれる。更に望まれるのは、 探索時間を大幅に増大することなく敏速な索引付けを考慮し、更に、索引付き文 書の携帯性を支援するシステムを提供することである。 発明の摘要 改善型の索引付け及び検索方法及びシステムが、各ワードを多数の「ｎグラム (gram)」又はワード副単位に分解することにより、現存の情報検索システムの制 限を克服する。ｎグラムとは、ｎ個の文字が、所定のワード、特に「cho」、「t hi」、「ment」等のレター又は番号に出現する際の、そのｎ個の文字の順序付き 線形組合せである。一般に、ｎグラムは、そのｎグラム内の文字数であるｎグラ ムパラメータＮ_pを有する。３のｎグラムパラメータを備えたｎグラムは、便宜 的に「トリグラム(trigram)」と呼ばれる。例えば、「houseboat」というワード は、トリグラム「hou」、「ous」、「use」、「seb」、「ebo」、「boa」、「oa t」から構成される。レターの全てがワードに存在するとしても、「tbh」も「hb t」も、「houseboat」のトリグラムではないことに留意されたい。というのは、 レターがワード内に出現する際のレターの順番及び関係が重要であるためである 。 本発明において、文書の各ページの非停止ワードがｎグラムへと 分解されて、それらが索引付け及び格納される。完全なワードではなくｎグラム によりワードを索引付けすることで、間違った綴り、部分ワード、又はワード列 内に埋め込まれたワードが、ワード全体間の一致ではなく、照会ワードのｎグラ ムと文書内のｎグラムの間の一致を探索することにより識別できる。例えば、「 factory」というワードが、文書内で「factori」と綴りが間違っていると仮定す る。そのｎグラムは、「fac」、「act」、「cto」、「tor」及び「ori」として 格納される。これらは、正確な綴りの「factory」という探索照会ワードのｎグ ラム、すなわち「fac」、「act」、「cto」、「tor」、「ory」と比較される。 ５個のｎグラムのうちの４個が一致して、その文書が検索されることになる。同 様に、第１のレターが、ＯＣＲ解析問題に起因して外れるとしても、ｎグラムは やはり「acｕ」、「cto」、「tor」、「ory」となるであろう。ここで、５個の ｎグラムのうちの４個がやはり一致するので、そのワードは検索されることにな る。明らかに、同時進行ワード列の内側のワードに対するｎグラムは、同様に識 別可能であり、また別個に一致可能であろう。 従って、文書を探索及び検索するために、探索照会が入力されて、探索照会内 のワードが、それらのｎグラムへと同様に分解される。照会ワードのｎグラムは 次に、各種文書のページのワードに対するｎグラムと比較される。任意の照会ワ ードｎグラムが、あるページの任意のｎグラムと一致する場合、そのページは検 索されて、照会ワードｎグラムは更に、各ワードｎグラムと比較される。これに よ り、照会ワードとそのページのワードとの間の一致精度の判定が可能になる。そ のページを含む文書は次に、検索されてユーザに表示可能となる。また、照会ワ ードと文書ワード間の一致の判定が終了すると、ブール探索を実行可能である。 以上は、ｎグラム分解及び索引付け処理の基本概念の説明である。多数の異な るシステムが考案され、ｎグラムを用いてワード又は文書が解析される。しかし 望まれるのは、効率的な索引付け、及び高精度の高速探索をもたらし、更に、索 引及び文書の携帯性を与えるシステムにおいて、ｎグラム分解を使用することで ある。従って、本発明の別の及び更なる態様は、階層的索引付け方式の使用であ り、これは、多数のドロワ内の文書を表現するデータを格納し、各ドロワには、 テキスト及びイメージデータのページを有する文書が含まれる。ページは、ある ドロワ内の多数のバンクに作表される。Ｎグラム分解及び索引付けは、文書全体 に関してではなく、離散ページに関して実行される。 各ドロワは、多数のバンクを含んでいる。各バンクに対して、１つのバンク索 引が存在する。このバンク索引は、関連したバンクにおいて各ページに実際に出 現するｎグラムを表すデータを格納している。所定サイズの既知で固定数のｎグ ラムが存在するので、各バンクは更に、バンク内に作表された任意のページのｎ グラムの任意の事例が存在するか否かを、各可能なｎグラムに対して示すエント リマップを含んでいる。バンク内の任意のページの事例が存在する各ｎグラムに 関して、次に、エントリマップは、そのｎグラムを含 むバンク内の各ページを特定的に識別する、更なるページマップにアクセスを行 う。この型式の記憶構造は、索引付け及び検索時に、メモリの非常に小型で効率 的な利用を考慮するものである。 バンク、及びバンク索引により、敏速な検索システムが提供される。照会が入 力されると、照会ワードのｎグラムが決定される。照会ワード内の各ｎグラムは 、先ず、エントリマップに対して直ぐ比較されて、バンクの任意のページ内にｎ グラムの任意の事例が存在するか否かが判定される。エントリマップが、あるペ ージにそのｎグラムが含まれると示す場合、そのページマップが走査されて、特 にどのページに更なる処理が必要であるかを決定する。この初期の前処理は、所 与の参照ワードを更に探索する必要のあるページのみを非常に敏速に識別し、照 会ワードのｎグラムを含んでいないページを検討から削除する。 次に、第２の処理段が、照会の部分を含む、バンク内のページのみをアクセス することになる。かかる各ページに関して、そのページのｎグラムが、これはバ ンク索引に格納されているが、次に照会ワードｎグラムと比較される。これらが 、十分な割合で照会ワードのｎグラムと一致する場合、そのページに関連した文 書が、検索のために指示される。文書と索引のこの編成により、文書の携帯性が もたらされる。というのは、ドロワ、文書、バンク、及びバンク索引を含むドロ ワ全体が、文書が索引付けられたコンピュータ・システムから他のコンピュータ ・システムへと転送されて、そこで、ドロワ内の文書を再索引付けする必要なく 探索できるためである。 図面の簡単な説明 図１は、ｎグラム分解を用いて、文書を索引付け及び検索するためのシステム のブロック図である。 図２ａは、このシステムの記憶要素の物体モデルであり、ドロワ、フォルダ、 文書、バンク、バンクリスト、バンク索引、解放リスト、及び文書リストの関係 を示す。 図２ｂは、これら記憶要素のユーザ側から見た図である。 図３は、文書リストの構造図である。 図４は、バンクの構造図である。 図５は、バンク索引の構造図である。 図６は、バンクとバンク索引の間の関係の一例を示す図である。 図７は、文書を索引付け及び検索する方法全般の流れ図である。 図８は、文書に対する索引付け処理の流れ図である。 図９は、文書内のあるページを索引付けする行程の流れ図である。 図１０は、バンク索引に記憶するために、あるページ内のワードキーを作成す る行程の流れ図である。 図１１は、探索行程の流れ図である。 図１２は、あるバンクに関する前処理演算の流れ図である。 図１３は、前処理の後に続く、あるバンクの選択ページを探索する行程の流れ 図である。 図１４は、照会ワードのｎグラムをあるページのワードのｎグラムと突合せる 行程の流れ図である。 発明の詳細な説明 システムアーキテクチャー 図１を参照すると、そこには、本発明の改善型文書索引付け及び検索システム を用いるためのシステムが示されている。システム１００は、コンピュータ１０ １を備え、これは、走査済み文書の長期保存用の二次記憶装置１０７と、コマン ド及びデータを受信及び出力するための入力装置１０９及び出力装置１１６と、 プロセッサ１１１による実行用の各種符号モジュールを格納するためのアドレス 指定可能メモリ１１３を有する。 入力装置１０９にはスキャナ１１５が含まれ、これは、入力文書を走査して、 入力文書に対してグレイスケール、２階調、又はカラービットマップファイルの いずれかを生成することが可能である。スキャナ１１５は、少なくとも２００ｄ ｐｉの分解能を有することが好ましい。入力装置１０９は更に、コマンド及びデ ータを入力するためのキーボード１４９を備える。出力装置１１６は、走査済み 文書、又はシステム１００内に常駐する他の文書を含めた文書を印刷するための プリンタ１１７を備える。出力装置１１６は又、探索結果及び他の情報と共に、 ユーザに対してシステム用のユーザインターフェースを表示するためのディスプ レイ１５１を備える。 アドレス指定可能メモリ１１３には、多数の符号モジュールが含まれ、これら は共に、本発明のシステム１００を管理する実行可能アプリケーションを構成す る。更に詳細には、アドレス指定可能メモリ１１３には、アプリケーション監視 １１９と、索引監視１２１と、探索監視１２３と、文書参照モジュール１２５と 、ページ索引 付けモジュール１２７と、探索実行モジュール１２９と、探索リストモジュール １３１と、光学式文字認識モジュール１３３とが含まれる。これら各種モジュー ルの動作を以下で説明するが、その前に携帯型文書索引付けを支援する記憶要素 について説明する。索引／探索バッファ１４３を用いて、索引付け及び探索段の 間に生成されたデータが一時的に格納される。ページバッファ１４５を用いて、 探索時に文書からのデータが一時的に格納される。停止ワードファイル１３５が 、索引付けから除外されるワードのリストを維持する。停止ワードファイル１３ ５は、システム１００に設けられて、ユーザにより修正される。 システム１００は、アプリケーション監視１１９を通じてアクセスされ、これ は、ディスプレイ１５１上に適切なユーザインターフェースを提供し、それによ りユーザが、スキャナ１５１を通じてシステム１００内に文書を、又は現存のテ キストファイル、イメージファイル、グラフィックファイルその他といった他の ソースを入力したり、ワード、汎用文字、及びブール又はＳＱＬ演算子の組合せ を含む探索照会を入力したり、またディスプレイ１５１又はプリンタ１１７等の 出力装置上で、探索照会の結果を見直すことが可能になる。 アドレス指定可能メモリ１１３には更に、本発明のｎグラム分解索引付けを実 施するのに有用な記憶構造のデータベース１４１が含まれる。ここで図２ａを参 照すると、そこには、アドレス指定可能メモリ１１３におけるこれら記憶構造の 物体モデルが示されている。 図２ｂは、これらの記憶構造をユーザ側から見た図である。 アドレス指定可能メモリ１１３は、１つ以上のドロワ２０１を含む。各ドロワ ２０２は、好適には、ドロワ名と論理名、及び着脱可能媒体か、又は固定媒体か の媒体型式を有する。この最後の属性により、ドロワ２０１を、携帯型記憶媒体 上で各種のコンピュータ装置に転送することが可能になる。 各ドロワ２０１は更に、０個以上のフォルダ２０３の階層リストを含む。各フ ォルダ２０３は、１つのフォルダ名を有し、０個以上の文書２０５又は他のフォ ルダ２０３を含む。 各文書２０５は、ユーザによる認識のための文書名、及びシステム１００によ り使用される固有の文書番号を有するのが好ましい。１つの書類２０５は、少な くとも１つのテキストファイル２０７から構成される。更に、１つの書類２０５ には、イメージファイル２０９、アイコンファイル２１３、及び書類ファイル構 造（ＤＦＳ）ファイル２１１が含まれる。テキストファイル２０７は、ＡＳＣＩ Ｉ又は類似のフォーマットで書類のテキストデータを収納する。テキストデータ は、一般に、イメージデータに関するＯＣＲ処理から生成されることになる。テ キストデータは、ユーザ入力からでも直接作成できる。テキストデータは、例え ば、文書２０５がビットマップ化又はベクトル・グラフィック・ファイルである 場合、及びユーザが、索引付けのために、ファイルの注釈又は記述を含めたい場 合にも入力することができる。テキストファイル２０７は、１つ以上のページ２ １５にそのデータを収納する。各ページは、そのペー ジ番号、文書名、フォルダ名、及びドロワ名によって識別される。 イメージファイル２０９は、対応する入力文書の走査及び認識、又は他の類似 の処理から生じる、２階調、グレイスケール、又はカラーのビットマップである 。イメージファイル２０９中のデータは、同様にページ２０５に格納される。 ＤＦＳファイル２１１は、テキストファイルデータをイメージファイルデータ にマッピングする。ＤＦＳファイル２１１は、テキストファイル２０７における テキストのライン毎に、イメージページ２１５へのマッピングと、テキストのラ インがイメージページ２１５内に出現する場所での画素座標（好適には、左上及 び右下の角）により規定される、境界を示す矩形とを含む。このマッピングによ り、ユーザが、あるページの画像を見る場合に、そのページのテキストデータを アクセス可能となる。ＤＦＳファイル２１１は又、好適には、文書２０５内のテ キスト及びイメージページ数に対して、ページカウント値を維持する。ＤＦＳフ ァイル２１１は更に、文書２０５内の各ページについての参照データを維持し、 これには、ページ番号と、文書番号及び文書名と、完全経路名と、アイコンファ イル名とが含まれる。 アイコンファイル２１３は、文書２０５の各ページのごく小さなビットマップ 化イメージを収納する。ごく小さなイメージは、探索及び検索動作時に、又は文 書２０５がユーザによりアクセスされている間、ユーザに対して表示される。好 適な実施例において、文書だけが、走査その他なしに生成されたテキストデータ を含む場合に は、付随のイメージファイル２０９、又はアイコンファイル２１３は存在しない 。 各ドロワ２０１は、文書リスト２２５と関連づけられる。文書リストは、ドロ ワ２０１内の全ての文書２０５の索引である。図３は、文書リスト２２５の構造 を示す。文書リスト２２５は、可変数の、多くても最大限度Ｄ_maxまでのエント リ３１１を格納する。好適な実施例の場合、Ｄ_maxは、ドロワ２０１内の文書の 全てにおけるページ全体の数により制限され、各ドロワ２０１は、最大で１，０ ４４，４８０ページを扱うことが可能である。各エントリ３１１は、ドロワ２０ １内の各文書２０５の完全経路名を含む。各文書２０５は、文書リスト２２５に おけるそのオフセットの結果として、文書リスト２２５内に固有の文書番号３０ １を有する。状態値３０３が、好適には、各エントリ３１１に対して、どれが文 書を格納するのに利用可能であるかを指示するために維持される。文書リスト２ ２５は、文書エントリ３１１の数３０７のカウント値、及び未使用エントリの数 ３０９のカウント値を維持するが、これらは、現存の文書が外された場合に作成 される。 システム１００は更に、少なくとも１つのバンク２１７を含む。図４は、バン ク２１７の構造図である。各バンク２１７は、システム１００に各種文書からの ページのリストを含み、これは、最大で所定数Ｐ_maxのエントリ４１３である。 好適な実施例の場合、バンク２１７は最大で２５５個のエントリ又はページ参照 を含む。他の実施例の場合、Ｐ_maxが更に大きいと、結果として更に多くのペー ジの索引付けとなり、Ｐ_maxが更に小さいと、ページがほとんど索引付けできな くなるが、記憶容量の必要性は少なくなる。文書ページは、ドロワ２０１用の文 書リスト２２５からの文書番号３０１で作表され、次いで、文書２０５内のペー ジ番号４０３により作表される。各エントリ４１３に対して、そのエントリ内で いずれのページを参照するかを示す状態値４０５が維持されるのが好ましい。各 エントリ４１３は更に、関連したバンクオフセット４１１を有し、これは、バン ク２１７内のエントリ４１３のオフセットである。すなわち、バンクオフセット ４１１は、実際にはエントリ４１３に格納されていない。各バンク２１７は、好 適には、バンク２１７において新しいページが参照され、他のページは参照され ない際に更新される、未使用エントリの数４０７を維持する。好適な実施例の場 合、ドロワ２０１は、４０９６個のバンク２１７を含み、結果として、各ドロワ ２０１に対する索引付きデータの最大で１，０４４，４８０ページとなる。各バ ンク２１７は、それをドロワ２０１及びバンクリスト２１９内で固有に識別する 、バンク番号４０９を有する。すなわち、バンク番号４０９は、それ自体のバン ク２１７に格納されるか、又はバンク２１７のファイル名により識別可能である 。共に、バンク番号４０９とバンクオフセット４１１は、ページに対するバンク 参照を形成する。 各バンク２１７は、バンク索引２２３及び解放リスト２２１と関連づけられる 。各バンク索引２２３は、バンク２１７内の各ページエントリ４１３に見出され るｎグラムを識別する。図５を参照する と、そこには、バンク索引２２３の好適な構造が示されている。好適な実施例の 場合、バンク索引２２３は、全ｎグラムのリストをデータとして直接には含まな い。むしろ、各ｎグラムには、固有の番号が割り当てられ、これを用いて、固定 数のｎグラム・エントリマップ５０５が索引付けられる。 最初に、索引付けのために、システム１００により索引付け可能な文字組、及 び文字範囲が選択される。索引付け可能な文字の総数をＣ_maxと呼ぶ。そうする と、ｎグラムの総数Ｌは、 Ｌ：［Ｃ_max］^Np となる。 好適な実施例の場合、索引付け可能な文字は、「Ａ」−「Ｚ」及び「Ｏ」−「 ９」である。全ての句読点及び特殊文字が、これらは通常、データを探索するの に使用されないが、「〜」等の単一文字にマッピングされるのが好ましい。これ により、「AT＆T」といったワードが「AT〜T」と、また「3.1415926」といった 数字が「3〜1415926」と索引付けることが可能になる。更に、１つのワードの最 後の幾つかの文字が、それら自体によるｎグラムにとって不十分な数である場合 、「〜」を用いてｎグラムが完成される。例えば、「at」のトリグラムは「at〜 」となる。国際文字は、対応する英語の等価文字にマッピングされる。小文字は それらの大文字値に変換される。これにより結果として、ｎグラム内の各位置に 対して３７個の異なる文字での好適な実施例となる。そうすると、好適な実施例 の場合、５０，５６３（３７³）個のトリグラムが存在する。３７個の文字 は、任意の有用な仕方で、例えばそれらのＡＳＣＩＩ値又は他の手段により順序 付けられる。次に、可能なｎグラムが作表されて、ｎグラム番号で直列に番号付 けられる。例えば、最初に数表示を、次に「〜」を想定すると、その順番付けは 、「000」、「001」、…、「00A」、…、「00Z」、「00〜」、…「〜〜〜」とな る。好適な実施例の場合、ｎグラム番号は以下のように計算される。 ｎグラム番号＝（第１のｎグラムレター番号）＊max_char^N-1 ＋ （第２のｎグラムレター番号）＊max_char^N-2 ＋ （第３のｎグラムレター番号）＊max_char^N-3 ＋ … （第Ｎ−１のｎグラムレター番号）＊max_char＋ （第Ｎのｎグラムレター番号）＊max_char^N-1 ここで、ｎグラムレター番号は、レターがｎグラムに出現する際の順序付き数で あり、ＮはｎグラムパラメータＮ_pであり、max_charはＣ_maxに等しい。好適な実 施例の場合、Ｃ_maxは３７であり、ｎグラムパラメータＮ_pは３であるので、上記 式は以下のように簡約化される。 トリグラム番号＝（第１のトリグラムレター番号）＊３７² ＋ （第２のトリグラムレター番号）＊３７ ＋ （第３のトリグラムレター番号） 代替実施例の場合、参照テーブル２２７がｎグラムを格納し、そのテーブル内 の所与のｎグラムのオフセットは、そのｎグラム番号である。 各バンク索引２２３には、使用されているｎグラムの総数Ｌに等しい数である 、ｎグラム・エントリマップ５０５の固定数が含まれる。各ｎグラム・エントリ マップ５０５は、索引ページマップ５０７に対する索引値を維持するが、それは 索引ページマップ５０７が、ｎグラムエントリ５０５と関連したｎグラムに対し て割り当て済みの場合である。各索引値単位は、索引ページマップ５０７内の要 素の総数を表す。索引オフセット５０１が、第１の索引ページマップ５０７のア ドレスを格納する。ｎグラム・エントリマップ５０５内の索引値は、索引オフセ ット５０１に加えられて、ｎグラム・エントリマップ５０５と関連した索引ペー ジマップ５０７となる。多数のｎグラムは、バンク２１７内のページエントリ４ １３のいずれにも出現しないので、ｎグラム・エントリマップ５０５により、シ ステム１００が、どのｎグラムに関して、ページに実際の事例が存在するかを敏 速に判定することが可能となり、従って、実際の索引ページマップ５０７を探索 時に更に解析することが可能となる。 索引値が非ゼロである各ｎグラム・エントリマップ５０５に対して、１つの索 引ページマップ５０７が存在する。各索引ページマップ５０７は、バンク２１７ 内のどのページ４０３がｎグラムを含むかを示すデータを収納する。索引ページ マップ５０７は、バンク２１７内の各可能なページエントリ４１３に対して、１ ビットを収納する。好適な実施例の場合、各マップ５０７内のビット数は、バン ク２１７内のエントリの最大数Ｐ_maxに対応する。索引ページマップ５０７内の ビット位置は、バンク２１７内のページエントリ４１ ３のバンクオフセット４１１に対応する。そのビットは、ページエントリ４１３ が、素引ページマップ５０７と関連したｎグラムを含む場合にセットされ、含ま ない場合にはセットされない。バンク２１７内に２５５個のページエントリを備 えた好適な実施例の場合、各索引ページマップ５０７は、３２バイト（２５６ビ ット）を収納して、ｎグラムをページエントリ４１３にマッピングする。他の実 施例の場合、他の形式のマッピングが用いられるが、例えばポインタのリスト等 がある。索引ページマップ５０７の更新について、以下で更に説明する。 図６は、バンク２１７とバンク索引２２３の間の索引付け関係の一例である。 図６には、各種のページエントリ４１３ａ−ｆ、エントリ総数Ｐ_bを含む１つの バンク２１７の一部が示されている。エントリの幾つかは、それらの状態値４０ ５において「使用中」と表記され、かかる各エントリ４１３には、文書番号３０ ３が含まれ、これは、それが文書リスト２２５（不図示）内のどの文書に属する かを示し、また、文書内のどのページかを示すページ番号４０３が含まれる。こ こで留意されたいのは、エントリ４１３は、多数の異なる文書から到来し、エン トリ４１３ｂ、ｃ等の同一文書からのエントリでさえも、文書の唯一選択された ページである。バンクオフセット４１１は、各エントリ４１３に対して指示され る。 バンク索引２２３には、ｎグラム・エントリマップ５０５ａ−ｆの完全な作表 の一部が含まれる。これらのｎグラム・エントリマップ５０５ａ−ｆの各々には 、もしあれば、どの索引ページマップ５ ０７ａ−ｆが、ｎグラム・エントリマップと関連したｎグラムに対して割り当て られるかを示す、索引値６０１が含まれる。従って、第１の（図で見られるよう に、バンク索引２２３内のｎ番目とすることもできる）ｎグラム・エントリマッ プ５０５ａは、ゼロに等しい索引値６０１を有し、これは、そのマップと関連し たｎグラムが、バンク２１７内のどのページにも出現しないことを示し、従って 、ｎグラム・エントリマップ５０５に対して割り当てられる索引ページマップ５ ０７はない。第３のｎグラム・エントリマップ５０５ｃについても同様である。 しかし、第２のｎグラム・エントリマップ５０５ｂは、２に等しい索引値を有 し、第２の索引ページマップ５０７ｂに対して索引付ける。従って、それがどん なｎグラムであっても、ｎグラム・エントリマップ５０５ｂと関連したｎグラム の一事例を有するｎグラムバンク２１７には、少なくとも１つのページが存在す る。同様に、第４のｎグラム・エントリマップ５０５ｄは、第４の索引ページマ ップ５０７ｄに索引付けし、ｎグラム・エントリマップ５０５ｅは、第３の索引 ページマップ５０７ｃに索引付けし、またｎグラム・エントリマップ５０５ｆは 、第１の索引ページマップ５０７ａに索引付けする。 各索引ページマップ５０７には、バンク２１７内のエントリ４１３にマッピン グされる、１組のビットが含まれる。ある索引ページマップ５０７内の第ｍビッ トの値は、その索引ページマップ５０７に対するｎグラム・エントリマップ５０ ５と関連したｎグラムが、 第ｍエントリ４１３により表されるページに出現するか否かを示す。各索引エン トリマップ５０７内の第１ビットは、第１エントリ４１３ａにマッピングされ、 第２ビットは第２エントリ４１３ｂに、等となる。 例えば、枠６０３には、バンク２１７内の第４エントリ４１３ｄに対するマッ ピングが示されている。第１及び第２の索引ページマップ５０５ａ、ｂの両方に おいて、エントリ４１３ｄに対応するビットはセットされない。これは、ｎグラ ム・エントリマップ５０５ｂ及び５０５ｆと関連したｎグラムが、文書番号７１ １のページ８７には出現しないことを示す。しかし、索引ページマップ５０７ｃ 、ｄ内のビットはセットされるので、ｎグラム・エントリマップ５０５ｄ、ｅと 関連したｎグラムはそのページに出現する。同様に、索引ページマップ５０７ｂ の第Ｐ_maxビットは、このマップと関連したｎグラムが、文書番号８１８のペー ジ９３に出現することを示す。 再度図５を参照すると、バンク索引２２３は更に、バンク２１７内のページエ ントリ４１３により識別されるページに出現するｎグラムを表すデータを格納す る。これは、実際の探索が実行されて、入力照会に一致する文書を突き止める場 所である、バンク索引２２３の領域である。このデータは、ページキー５０９の 可変長テーブル５１７に格納されるが、各ページエントリ４１３に対して１つで ある。ページキー５０９は、以下の形式の可変長フィールドである。 ［ｋ_i、ｎグラムｉ₁、、ｎグラムｉ₂、…、ｎグラムｉ_k］ ［ｋ_(i+1)、ｎグラム（ｉ＋１）₁、ｎグラム（ｉ＋１）₂、…、 ｎグラム（ｉ＋１）_k］… ここで、ｋ_iはページの第ｉワード内のｎグラムの数であり、ｎグラムｉ_{(1 …k)} は第ｉワード内のｎグラム番号のリストである。値［ｋ］の各グループ［ｎグラ ム１、ｎグラム２、…、ｎグラムｋ］は「ワードキー」と呼ばれる。あるページ の全てのワードに対するワードキーの集合がページキー５０９である。ここで留 意されたいのは、好適な実施例において、ｎグラム自体が格納されるのではなく 、各ｎグラムを固有に識別するｎグラム番号がページキー５０９に格納される、 ということである。ｎグラム自体ではなくｎグラム番号を用いることにより、結 果としてメモリの節約になる。各ｎグラムは各文字に対して１バイトを要するの で、トリグラムは３バイトである。しかし、ｎグラム番号は以下のビットしか必 要としない。 ｌｏｇ₂（［Ｃ_max］^Np） 従って、トリグラムは、１５．６ビット、又は２バイトしか必要としない。 １ページに対して３２ｋの最大テキストデータサイズを想定すると、１つのペ ージキー５０９の最大サイズは、好適な実施例の場合、１２８ｋしかない。実際 には、各ページの平均サイズは約２ｋであるので、各ページキー５０９は約８ｋ である。 個々のページキー５０９にアクセスするために、固定サイズのページオフセッ トテーブル５１５が設けられている。それ内の各エントリには、各ページキー５ ０９に対して、１つのページキーオフセット５１１及びページキーサイズ５１３ が含まれる。好適な実施例 の場合、バンク２１７内のページエントリ４１３の各々に対して、１つのエント リが存在する。ページキーオフセット５１１とは、テーブルエントリに対応する 可変長ページキー５０９の開始に対するオフセットのことである。ページキーサ イズ５１３とは、ｎグラム及びｋ値に対する全エントリを含む、対応するページ キー５０９内のバイトの総数のことである。ページキーサイズ５１３を維持する ことにより、システム１００が、システムから索引付きページを削除すること、 及び新規ページを追加及び索引付けするのに利用可能な領域に関する情報を依然 として有することが可能になり、それによって記憶空間の浪費が回避される。 解放リスト２２１は、各バンク２１７と関連づけられて、バンク２１７内のど のページエントリ４１３が、索引付けに利用可能であるかに関する情報、これに は以前に索引付けられたページエントリ４１３が削除された場所も含まれるが、 その情報を格納する。あるページエントリ４１３があるバンク２１７から削除さ れる場合、そのバンク索引２２３内のページキーオフセット５１１及びページキ ーサイズ５１３が、解放リスト２２１に格納され、次いでページキーオフセット ５１１は、バンク索引２２３でゼロにセットされる。 バンクリスト２１９が、ドロワ２０１内のバンク２１７の全てに対するデータ を収納する。バンクリスト２１９は、各バンク２１７に対して、バンク２１７内 の解放エントリ４１３の数のカウント値を維持する。これらの値は、新規ページ がバンク２１７に追加される際、又は古いページが削除される際に更新される。 好適な実施例 の場合、バンクリスト２１９には、バンク番号に従って、最大で４０９６個のバ ンク２１７に対する解放エントリのカウント値が含まれる。表１はバンクリスト ２１９の構造を示す。 再度ＤＦＳファイル２１１を参照すると、好適な実施例の場合、それには、そ の関連した文書２０５の各ページ２１５に対して、バンクリスト２１９で順序付 けられる通りのページ２１５を含むバンク２１７のバンク番号、バンク２１７内 のバンクオフセット４１１、文書のページ番号４０３、及び文書リスト２２５内 の文書番号３０１が収納される。 システム動作 Ｉ．全体の処理流れ システム１００は、情報記憶及び検索システムにおいて、文書を索引付け及び 探索する改善された方法を提供する。その方法には、２つの基本的な行程が含ま れ、すなわち文書を索引付けする行程と、探索照会を用いて文書を探索する行程 である。 図７を参照すると、そこには、本発明の方法全体の流れ図が示さ れている。１つの文書、又は１組の文書がシステム１００へと入力される（ステ ップ７０１）。印刷文書又は画像に対して、文書が、スキャナにより慣用的な仕 方で走査され、次いでＯＣＲモジュール１３３により処理されて、テキストファ イル２０７のテキストデータが生成される。あるいは、イメージファイル２０９ を有する文書が、ファクシミリ画像等の他のシステムから読み込まれて、ＯＣＲ モジュール１３３により処理される。代替として、文書は、テキストファイル２ ０７内のテキストデータとして直接入力されるか、又はユーザが、テキストファ イル２０７に追加のテキスト情報を与えた、イメージとすることもできる。文書 がテキストデータとして直接受信される場合、テキストファイル２０７とイメー ジファイル２０９間のＤＦＳファイル２１１でマッピングは行われない。代替と して、テキストデータが直接受信される場合、それは、慣用的な画像処理技法を 用いてイメージファイルへと描写され、次いで、ＤＦＳファイル２１１が、テキ スト／イメージ・マッピング情報を含むように更新される。好適には、ユーザは 、アプリケーション監視１１９により促されて、入力文書を格納するドロワ２０ １及びフォルダ２０３を選択／作成する。 入力文書のテキストデータが得られた後、入力文書は索引付けられる（ステッ プ７０３）。索引付けは、索引監視１２１により管理される。好適には、索引付 けは、入力ステップ７０１の間、文書が走査されている場合に１ページ毎に行わ れる。索引付けは又、１文書毎に、又は所望ならばバッチ或いは据置きモードで も行われるが、 これは、大量の文書を都合良く扱うためである。索引付けは、文書の各ページ内 のｎグラムの全てを識別し、ユーザ選択のドロワ及びフォルダの１つ以上のバン ク２１７内で利用可能な空間を突き止め、それに従って、バンク２１７、バンク 索引２２３、バンクリスト２１９、及び解放リスト２２１を更新する。 索引付けが終了すると、ユーザは、索引付き文書２０５のドロワ２０１全体を 他のコンピュータに、直接ネットワーク接続を経由して、又は携帯型記憶媒体を 介して転送する（ステップ７０５）ことを決めることができる。これにより、他 のコンピュータが、文書を再索引付けする必要なく、ドロワ２０１内の文書２０ ５に関して探索可能となる。代替として、ユーザは、１つ以上の文書２０５又は フォルダを転送することを決めることもできる。再索引付けは、文書がドロワ２ ０１間で転送される場合にのみ必要である。 システム１００は、任意の索引付きドロワ２０１に関して探索することが可能 である。アプリケーション監視１１９が、ユーザに、探索する（ステップ７０９ ）ためのドロワ２０１、フォルダ２０３、又は文書２０１を選択するよう促す。 ユーザは、所望のワード及びブール演算子を特定する探索照会を入力する（ステ ップ７０７）。ユーザは又、一致パラメータＥも特定し、これは、探索照会と任 意の文書に存在するワードとの間の精度の割合を記述するものである。好適な実 施例の場合、Ｅは有用な範囲、例えば２０％−１００％に制限される。 探索照会が入力されると、探索監視１２３が、探索行程７０９を 管理する。要約すれば、探索には、照会ワードをｎグラムに変換し、次いで、こ れらの照会ワードｎグラムをバンク索引内のｎグラムと比較することが伴う。次 に、ｎグラムの一致が解析され、一致パラメータで重み付けされて、一致の度合 いが決定される。探索照会と一致パラメータを満足する一致を有する文書が検索 されて、ユーザに対して表示される（ステップ７１１）。ユーザは、更なる探索 を行い、結果を格納し、文書をプリントアウトし、文書の部分を内部のユーザ用 の他のアプリケーション・ソフトウェアへとコピーし、又は探索を終了すること ができる。 II ．文書索引付け 次に図８を参照すると、そこには、文書をシステム１００へと索引付けする行 程７０３の流れ図が示されており、これは索引監視１２１により管理される。索 引監視１２１は、一連の演算を実行して、ユーザにより入力された文書２０５の 各ページ２１５内の各ｎグラムを索引付けし、また適切なバンク２１７、バンク リスト２１９、解放リスト２２１、及びバンク索引２２３を更新する。 索引監視１２１は、メモリを索引付け行程に対して割り当てる（ステップ８０ １）。これには、バッファ１４３、１４５をクリアして、多数のページの索引付 けを可能にするのに十分である、他のどんな追加のメモリ資源も外してセットす ることが伴う。 索引監視１２１は、文書参照モジュール１２５を呼び、索引付けしようとする 文書２０５に対する文書番号３０１を得る。索引監視１２１は、入力ステップ７ ０１の間にユーザにより与えられるよう な、特定の文書２０５、及び文書２０５の文書名を含むドロワ２０１の根ノード を、文書参照モジュール１２５に与える。文書参照モジュール１２５は、ドロワ ２０１に対して文書リストを開き、未使用エントリ数３０９から、エントリ３１ １の現存リスト内で新規文書に対して利用可能な空間があるか否かを判定する。 空間がない場合、新規のエントリ３１１が、文書リスト２２５内のエントリのリ ストの終わりに作成される。状態値３０３がセットされて、文書の完全経路名３ ０５が格納される。リスト内に未使用エントリ３１１がある場合、文書参照モジ ュール１２５は、リストを走査して、未セットの状態値で第１エントリ３１１を 突き止める。状態値３０３がセットされて、完全経路名が格納される。いずれの 場合でも、文書参照モジュール１２５は、文書リスト２２５内の更新／新規エン トリ３１１のオフセットである、文書番号３０１を戻すことになる。 次に、索引監視１２１は、ページ索引付けモジュール１２７を呼び出して、文 書２０５の各ページを索引付けし（ステップ８０５）、結果のデータをバンク索 引２２３に格納する。ページ索引付けモジュール１２７は、文書の各ページに関 してｎグラム番号の実際の作成を行う。図９を参照すると、そこには、あるペー ジを索引付けする行程の流れ図が示されている。この工程は、文書の各ページに 対して繰り返される。 ページ索引付けモジュールは、先ず、あるバンク２１７内のページに対してバ ンクオフセット４１１を得る。これは、索引付けしようとするページを、ユーザ 選択のドロワ２０１内の特定のバンク２ １７内の位置と関連づける。それにより更に、文書の各ページを異なるバンク２ １７に格納することが可能になる。これは以下のように行われる。 ページ索引付けモジュール１２７は、バンクリスト２１９を読み取り（ステッ プ９０１）、内部に作表された完全でない第１のバンク２１７を識別するが、こ れは、非ゼロ値に達するまで、各バンク２１７に対する解放エントリのカウント 値を読み取ることによりなされる（ステップ９０３）。ページ索引付けモジュー ル１２７は、その解放エントリのカウント値をディクリメントして（ステップ９ ０５）、関連したバンク２１７を開く（ステップ９０７）。 ページ索引付けモジュール１２７は、バンク２１７内の未使用エントリ数４０ ７をチェックする（ステップ９０９）。やはり、この値は、以前にはバンク２１ ７において索引付け及び含まれていたページが、どこで除去されたかを示す。こ の値がゼロでない場合、ページ索引付けモジュール１２７は、バンク２１７内の エントリを走査して（ステップ９１１）、空エントリを示す状態値４０５で第１ エントリを識別する。未使用エントリ数４０７がゼロである場合、ページ索引付 けモジュール１２７は、バンク２１７内のエントリ数４０１を用いて最後のエン トリに対してオフセットを持つように、バンク２１７の終わりに新規のエントリ を作成する。いずれの場合でも、ページ索引付けモジュール１２７は、現在のエ ントリを示す状態値４０５をセットして、そのエントリの文書リスト２２５から 文書番号３０１を、また文書のページ番号を格納する。次に、それ はバンク２１７内のエントリ数４０１をインクリメントして（ステップ９１７） 、バンク２１７のバンク番号と、バンク２１７内のバンクオフセット４１１を得 る。 次に、ページ索引付けモジュール１２７は、停止ワードファイル１３５をロー ドする（ステップ９１９）が、これは、停止ワードが、そのページに対して生成 されたワードキーに含まれないようにするためである。ページ索引付けモジュー ル１２７は、次いで、ページに対してワードキーを作成する（ステップ９２１） 。ワードキーは、そのページを含むバンク２１７と関連したバンク索引２２３内 のページに対して、ページキー５０９に格納されることになる。ページキー５０ ９用のワードキーは、先ず全てが作成され、次に続いて、ページキー５０９に格 納される。というのは、ページキーサイズ５１３は、実際の記憶に先立って、ペ ージキー５０９に対して決定されるためである。ワードキーは以下のように作成 される。 図１０を参照すると、そこには、所与のページのページキー５０９を構成する ワードキーを作成する行程の流れ図が示されている。ページキーサイズ５１３が ゼロに初期化されて（ステップ１００１）、バッファ１４３、１４５がクリアさ れる。索引バッファ１４３を用いて、ページキー５０９が、それが作成される際 に格納されることになる。ページバッファ１４５を用いて、ページのテキストデ ータが保持される。索引付けしようとするページが、ページバッファ１４５へと ロードされる（ステップ１００２）。ページ索引付けモジュール１２７は、ペー ジバッファ１４５に格納される際に、ページ のワードの全てにわたってループを実行する（ステップ１００３）。ページ索引 付けモジュール１２７は、現在のワードがファイル終端であるか否かを判定する （ステップ１００５）。現在のワードがファイル終端でない場合、そのワードが 停止ワードファイル１３５内の停止ワードであるか否かがチェックされる（ステ ップ１００７）。これは、ハッシュ法、又は他の慣用的な技法により行うことが できる。現在のワードが停止ワードである場合、ループ（ステップ１００３）は 継続する。 現在のワードが停止ワードでない場合、ページ索引付けモジュール１２７は、 そのワードの長さをチェックして（ステップ１００９）、その長さがｎグラム長 に等しくなるまで、ワードに「〜」を付加する。例えば、好適な実施例の場合、 ２レターのワードが、１つの「〜」で拡張されて、それらを３つのレターにする 。更に、１レターのワードは拡張されない方が好ましい。というのは、それらは 、探索用の識別可能なデータに殆ど寄与しないためである。 次に、ページ索引付けモジュール１２７は、ワード用のワードキーを作成する 。これには、ワードに対してｎグラム数ｋを決定するステップ（ステップ１０１ １）が含まれる。ワードキーに対するｎグラム数ｋは２のワード長である。 次に、ワードはそのｎグラムに分解されて、各グラムがそのワードから読まれ るが、これは第１文字で始まり、ｎグラムを作成するのに必要な文字数が読まれ る。各ｎグラムに対して、ｎグラム番号が決定される（ステップ１０１３）。こ れは、上記のように、ｎグ ラム参照テーブル２２７内のｎグラム番号を参照するか、又は直接、ｎグラム番 号を計算することにより実行される。 いずれの場合でも、ステップ１０１１及び１０１３の結果は、そのワードに対 するワードキーとなり、これは、番号ｋ、及びワード内のｎグラムの各々に対す る個々のｎグラム番号からなる。ワードキーはバッファ１４３に付け加えられる 。ページキーサイズ５１３が更新されて（ステップ１０１４）、ワードキーのサ イズが累算される。新規のページキーサイズ５１３は以下のようになる。 ページキーサイズ＝ページキーサイズ＋（１＋ｋ＊（ｎグラム番号） のサイズ） 機能サイズは、ｎグラム番号を格納するのに用いられるバイト数となる。トリ グラムの場合、これは２であるが、より大きなｎグラムの場合には更に大きくな る。特別な要素がｋを格納するために付加される。 そのようにして生成されワードキーに含まれる各ｎグラム番号に対して、ｎグ ラム・エントリマップ５０５、及び索引ページマップ５０７を更新する必要があ る。ｎグラム番号は、ｎグラム・エントリマップ５０５への索引として用いられ る。ｎグラム・エントリマップ５０５内の索引値が得られて（ステップ１０１５ ）、チェックされる（ステップ１０１７）。索引値がゼロである場合、それが意 味するのは、ｎグラムが、バンク２１７内に以前の参照を有しておらず、新規の 索引ページマップを作成すべきである、ということである。索引値がゼロでない 場合、それが意味するのは、ｎグラムが、 バンク２１７のあるページで以前に見出されて、そのｎグラムに対する索引ペー ジマップ５０７が既に存在している、ということである。次に、ｎグラム・エン トリマップ５０５からの索引値１が、索引オフセット５０１に付加されて、正し い索引ページマップ５０７となる。従って、ｎグラム・エントリマップ５０５の 索引値がゼロである場合、別の索引ページマップ５０７が、索引ページマップ５ ０７の現在の組の終わりに付加される（ステップ１０１９）。ｎグラム番号によ って参照されたｎグラム・エントリマップ５０５の索引値が、新規の索引ページ マップ５０７の位置で更新される（ステップ１０２１）ため、ｎグラムに対する 別の参照が作成される（索引付け時に）か、又は識別される（探索時に）場合に 、ｎグラム・エントリマップ５０５を用いて、新規の索引ページマップ５０７を 直接アクセスすることが可能になる。従って、あるバンク２１７に含めるべき第 １ページの第１のｎグラムに対して、そのｎグラム（そのｎグラム番号が何であ っても）は、ｎグラム・エントリマップ５０５内で索引番号１を有することにな り、それと第１の索引ページマップ５０７が関連することになる。次のｎグラム は、やはりそのｎグラム番号に関係なく、又は第１のｎグラムからいかに「遠く 」ても、そのｎグラム・エントリマップ５０５内で索引値２を有することになり 、第２の索引ページマップ５０７に割り当てられることになる。 ｎグラム・エントリマップ５０５内の索引値がゼロでない場合、ページ索引付 けモジュール１２７は、その索引値１を用いて、ｎグ ラムに対する索引ページマップ５０７となる（ステップ１０２３）。 ページ索引付けモジュール１２７は、ｎグラムに対する索引ページマップ５０ ７内の（バンクオフセット第４１１）ビットをセットする。これは、バンク２１ ７内の（バンクオフセット第４１１）エントリが、ｎグラムに対するある参照を 有することを意味する。これは、現在索引付けされているページである。 この更新は、ワードキー内の各ｎグラムに対して繰り返される（ステップ１０ １３）。ページ索引付けモジュール１２７は、ページ内で次に利用可能なワード について継続する（ステップ１００３）。 一旦、ページに対する全てのワードキーが、ループ１００３において完成する と、ページに対するワードキーの全体組は、完全なページキー５０９を構成する ことになる。ページキーサイズ５１３は、ページキー５０９全体のサイズとなり 、バッファ１４３内に存在することになる。ここで残っているのは、このページ キー５０９を、バンク索引２２３のページキーテーブル５１７内の適切な場所に 格納することである。 ページ索引付けモジュール１２７は、バンク２１７に対する解放リスト２２１ を走査して、今まさに完成したページキーのページキーサイズに等しいか、又は それより大きなページキーサイズ５１３により、第１の利用可能なページキー５ ０９のページキーオフセット５１１を決定する（ステップ１０２９）。上述のよ うに、解放リスト２２１は、削除されてしまった、従って他のページ用の他のペ ージキーを格納するのに利用可能な空間を有するページに対するペ ージキー５０９用のオフセット５１１を維持する。 かかるページキーオフセット５１１が突き止められると、新規に作成したペー ジキーが、ページキーテーブル５１７内のページキー５０９エントリに書き込ま れる。十分なサイズの間隙エントリがない場合、ページキーは、ページキーテー ブル５１７内の最後の現存エントリの後に書き込まれる（ステップ１０３３）。 いずれの場合でも、ページキーオフセット５１１、及びページキーサイズ５１３ は更新される。 再度図９を参照すると、ページ索引付けモジュール１２７は、次いで、停止ワ ードファイル１３５をアンロードして（ステップ９２３）、索引監視モジュール １２１に制御を戻す（ステップ９２５）。 再度図８を参照すると、索引監視１２１は、索引付きページのバンク参照（バ ンク番号４０９、及びバンクオフセット４１１）によりＤＦＳファイル２１１を 更新して（ステップ８０７）、索引付きページに対する特定のイメージ及びテキ ストページとバンク参照を関連づける。これにより、探索時に、またユーザがペ ージ画像を見たり、アクセス用のテキストデータにマッピングしたりする場合に 、システム１００がページに対する索引情報を検索することが可能になる。同様 に、索引監視１２１は、文書リスト２２５からの文書番号３０１により、ＤＦＳ ファイル２１１を更新する（ステップ８０９）ことにより、やはり、システム１ ００が文書を検索することが可能になる。最後に、索引監視１２１は、割当て済 みメモリ資源を解放する（ステップ８１１）。次に、索引監視１２１は、アプリ ケ ーション監視１１９に制御を戻して、更なる索引付け、索引及び文書の転送（ス テップ７０５）、又は探索（ステップ７０９）に対処する。 III ．文書探索 再度図７を参照すると、ユーザは又、入力探索照会に一致する文書に対して、 任意の数のドロワを探索する。一般に、探索には、探索照会内の各ワードをその ｎグラムに分解し、どの文書ページがどのｎグラムを含むかを判定して、結果と しての一致に基づき任意のブール演算又は他の演算を実行するステップが伴う。 更に詳細には、各バンクが探索されて、照会ワードのいずれのｎグラムが、その バンク内のいずれのページに出現するかが判定される。これらのページは注記さ れる。次に各ページに対して、照会ワードのｎグラムが、そのページの各ページ キー内の各ワードキーにおける各ｎグラムと比較される。これは、照会ワードと 各ページのワードの間の一致精度を判定する。 ここで図１１を参照すると、そこには、入力探索照会でシステム１００を探索 する行程７０９の流れ図が示されており、これは探索監視１２３により管理され る。 探索監視１２３は、先ず始めに、探索時に利用するのに十分なメモリ資源を割 り当てる（ステップ１１０１）。これには、ページバッファ１４５及び探索バッ ファ１４３のクリアが含まれる。通常、約７００ｋが、１６，０００文書を含む ドロワを探索するために割り当てられる。加えて、探索監視１２３は、どのペー ジエントリ４ １３（バンクオフセット４１１による）が照会ワードに対するヒットを含むかを 、各バンクに対して追跡する結果バッファを初期化する。 探索監視１２３は次いで、探索用に選択された全てのドロワ２０１にわたって ループ１１０３を初期化し、その後、各ドロワ２０１内の全てのバンク２１７に 対して、第２のループ１１０５を初期化する。 探索監視１２３は、現在のバンク２１７に対してバンク索引２２３を検索し（ ステップ１１０７）、探索実行モジュール１２９を呼び出して、前処理（ステッ プ１１０９）演算を実行する。前処理１１０９により、一致パラメータを満足す る探索照会ワード内のいずれかのｎグラムと一致するような、現在のバンク内の ページが識別される。従って、前処理は第１のフィルタリング・ステップであり 、探索ワードのｎグラムを何も含まないページを更に探索するのを不要にする。 図１２は、前処理演算の流れ図である。 探索実行モジュール１２９が、ページフラグリストアレイを初期化するが、こ れは、バンク２１７内の各ページに対して、任意の照会ワードの任意のｎグラム に関してヒットを含むか否かを追跡し、それにより、更なる処理に対してページ を適格にする。好適な実施例の場合、ページフラグリストアレイは１次元アレイ であり、バンク２１７内の各ページに対して１つのエントリを有し、そのバンク オフセット４１１に対応する。すなわち、ページフラグリスト［Ｐ_max］であり 、ここでＰ_maxは、バンク２１７内のページの最大数 である。 次に、探索実行モジュール１２９は、探索照会内の各ワードＱにわたってルー プ１２０３を初期化する。探索実行モジュール１２９は又、ｎグラム一致カウン タアレイＧも初期化する。ｎグラム一致カウンタアレイＧは、ページに対して、 照会ワードのうちｎグラムがそのページに見出される回数を追跡する。すなわち 、Ｇ［Ｐ］が、バンク２１７のページＰにおいて、任意の照会ワードのうちのｎ グラムの発生数である。別のループ１２０５は、現在の照会ワードＱ内の各ｎグ ラムにわたって開始される。現在の照会ワードＱに対するｎグラムは、索引付け 時に、上記のようにして判定される。 探索実行モジュール１２９は、Ｑの現在のｎグラムがバンク２１７内のいずれ のページに存在するか否かを判定する（ステップ１２０７）が、これは、そのｎ グラムのｎグラム番号を取って、バンク索引２２３内のそのｎグラム番号に対し て、ｎグラム・エントリマップ５０５の索引値をチェックすることにより行われ る。上記のように、ｎグラム・エントリマップ５０５は、所与のｎグラム番号、 ゆえにｎグラムに対して、バンク２１７内でそのｎグラムの任意の発生があるか 否かを示す。 索引値がゼロである場合、これは、そのバンク２１７に対するどのページにも 、照会ワードＱのそのｎグラムの事例が存在しなかったことを意味する。この場 合、ループ１２０５は継続する。 索引値がゼロでない場合、これは、バンク２１７内のあるページに、照会ワー ドＱのｎグラムの少なくとも１つの発生があることを 意味し、その索引値は、その発生によりバンク２１７内のページを識別する、索 引ページマップ５０７への索引を示す。従って、探索実行モジュール１２９は、 索引ページマップ５０７に対して走査を行う（バンク索引２２３用の索引オフセ ットに（索引値１）を加えて）。 探索実行モジュール１２９は、次いで、索引ページマップ５０７にわたってル ープを行い（ステップ１２０９）、ページマップ内の各ビットＢを読む。探索実 行モジュール１２９は、各ページに対するビットがセットされているか否かを判 定する（ステップ１２１１）。セットされていない場合、ループ１２０９は継続 する。 ビットがセットされている場合、これは、そのページがそのテキストデータ内 のどこかに照会ワードＱのｎグラムを含むことを示す。探索実行モジュール１２ ９は、ｎグラム一致カウンタＧ［Ｐ］をインクリメントする。これは、照会ワー ドＱのｎグラムがバンク２１７のページＰに出現することを示す。 次に、探索実行モジュール１２９は、インクリメントしたカウント値Ｇ［Ｐ］ が、そのページが現在の照会ワードＱに対するヒットを含むと見なすのに十分で あるか否かを試験する（ステップ１２１５）。これは、Ｇ［Ｐ］が、ユーザによ り入力された一致パラメータで重み付けされる、照会ワードＱ内のｎグラム数に 等しいか、又は大きいかを試験する。ユーザが、照会ワードＱとあるページのワ ード間の正確な一致を所望する場合、照会ワードＱ内のあらゆるｎグラムがその ページに存在する必要があり、従って、照会ワードＱ のｎグラムの各々に対する各索引ページマップ５０７内のページに対して、１つ のビットをセットする必要がある。例えば、照会ワードが「doorknob」である場 合、６個のｎグラムが存在し、同一のページビットを、「doorknob」のｎグラム に対する６個の索引ページマップ５０７内にセットする必要がある。ユーザがあ まり正確でない一致を所望する場合、更に少ない（ある割合で）索引ページマッ プ５０７しかセットする必要がない。従って、試験１２１５は以下となる。 Ｇ［Ｐ］≦Ｋ_Q＊Ｅ／１００ ここで、ＫＱはＱ内のｎグラム数であり、Ｅは一致パラメータである。Ｅは、２ ０等の有用な下境界と１００の間のあるであるのが好ましい。 この試験１２１５が満足されれば、ページフラグリストアレイが更新されて（ ステップ１２１７）、このページが照会ワードＱに対してヒットを含むことが示 される。すなわち、ページリストアレイが［Ｑ，Ｂ］でセットされる。ここで、 Ｂは現在のページの索引であり、ループ１２０９により制御される。その後、処 理はループ１２０９から出るまで続く。全ループが完了すると、前処理１１０９ （図１１）が行われたことになる。 再度図１１を参照すると、このようにして、前処理１１０９によりページリス トアレイが生成され、これは、各照会ワードＱに対して、現在処理されているバ ンク２１７内のどのページが、その照会ワードの一事例を有するかを示す。これ は、ページのどこに、照会 ワードとあるワード間の一致が発生するかを示すものではない。ここで、バンク ２１７内の各ページが処理されて（ステップ１１１１）、更に、照会ワードとあ るページのワード間の正確な一致が判定されて、任意のブール演算子を満足する か否かが判定可能となる。 次に、図１３を参照すると、そこには、あるバンク２１７の処理１１１１の流 れ図が示されている。この段階では、前処理１１０９時に選択されたページだけ が更に処理される。探索実行モジュール１２９が、バンク２１７内の各ページエ ントリ４１３にわたってループ１３０１を開始するが、これはバンクオフセット ４１１値だけ繰り返される。第２のループ１３０３が、探索照会内の各ワードＱ にわたって開始される。 探索実行モジュール１２９は、そのページが、照会ワードＱの一事例を有する か否かをチェックする（ステップ１３０５）。これは好適には、［Ｑ，バンクオ フセット４１１］でのページリストアレイをチェックすることにより行われる。 この値は、索引ページマップ５０７において決定されるページに、照会ワードＱ のいずれかの事例が存在するとしたら、前処理１１０９時にセットされることに なる。ページがそのように指示されていない場合、ループ１３０３は継続する。 そうでなければ、ページに対するページキー５０９が、ページバッファ１４３ へとロードされる（ステップ１３０７）。これは、バンクオフセット４１１を用 いて行われ、ペーオフセットテーブル５１５内に索引付けされて、正しいページ キー５０９に対する実際の ページキーオフセット５１１が得られる。ページキー５０９は次に、処理されて （ステップ１３０９）、ページのｎグラムの幾つが照会ワードに一致するかが判 定される。図１４は、この行程１３０９の流れ図を示す。 探索実行モジュール１２９が、各照会ワードＱに関して、ページキー５０９内 の各ワードキーＷに対するワードキー一致カウンタを初期化する。これは２次元 アレイ［Ｑ_n，Ｗ_n］であることが好ましく、Ｑ_nは照会ワードＱの数であり、Ｗ_n はページキー５０９内のワードキーＷの数である。 探索実行モジュール１２９は、一連のループを初期化する。外部のループ１４ ０３が、（図１３に示すループ１３０３により制御されるような）現在の照会ワ ードＱ内の各ｎグラムにわたって繰り返される。ｎグラムは、上記のように、比 較で実際に使用されるｎグラム番号と共に決定される。第２のループ１４０５が 、ページに対するページキー５０９内の各ワードキーＷにわたって繰り返される 。上記のように、索引付け時には、各ワードが、そのワード用のｎグラムの全て により１つのワードキーを生成する。このループにより、各ワードキー（ゆえに 、各ワード）が、各照会ワードと比較される。最後のループ１４０７が、あるワ ードキー内の各ｎグラムにわたって繰り返される。これらループの中核では、探 索実行モジュール１２９が、照会ワードＱの現在のｎグラムを、ワードキーの現 在のｎグラムと比較する（ステップ１４０９）。それらが同一である場合、ワー ドキー一致カウンタがインクリメントされる（ステップ１４１ １）（ゆえに、Ｑ及びＷの現在の繰り返しに対して、ワードキー一致カウンタア レイ［Ｑ，Ｗ］がインクリメントされる）。これが意味するのは、照会ワードＱ に対する１つのｎグラムが、ページ内のあるワードからの１つのｎグラムに一致 した、ということである。カウンタは、これらの一致の数を追跡することになる 。 次に、探索実行モジュール１２９は、照会ワードＱ自体とそのワード自体の間 の一致を示すのに（ワードキー一致カウンタアレイ［Ｑ，Ｗ］の値を用いて）十 分な一致か存在するか否かを判定する（ステップ１４１３）。やはり、この試験 は一致パラメータＥに基づくものである。そこで、正確な一致を必要とする（Ｅ ＝１００）場合、ワードキーＷ内のあらゆるｎグラムが、照会ワードＱ内のあら ゆるｎグラムと一致する必要がある。すなわち、ワードキー一致カウンタアレイ ［Ｑ，Ｗ］＝ＫＱとなる。ここで、ＫＱは照会ワードＱ内のｎグラム数である。 正確な一致が必要でない（Ｅ＜１００）場合、ある割合が一致する必要がある。 一般に、 ワードキー一致カウンタアレイ［Ｑ，Ｗ］≦Ｋ_Q＊Ｅ／１００となる。この試 験が満足されると、探索実行モジュール１２９は、探索照会に対するヒットを示 すように、バンク及びページエントリ４１１に対して結果バッファをセットする （ステップ１４１４）。内部のループ１４０７は完了する必要はない。というの は、ｎグラムが十分一致するためである。 次に続いて、探索実行モジュール１２９は、ループ１４０５及び１４０３を出 て、ワードキーＷ内の各ワードに対する評価、及び （図１３に示すループ１３０１により制御されるような）現在のページキー５０ ９内の各ワードキーＷに対する評価を終了させる。 再度図１３を参照すると、現在のページエントリ４１３が、各照会ワードＱに 対して処理される（ステップ１３０９）。一旦、全ての照会ワードの解析が終了 すると、上記のように、探索実行モジュール１２９は、探索照会が任意のブール 演算を含むか否かを判定する（ステップ１３１３）。ブール演算が必要とされる 場合、探索実行モジュール１２９は、ブール処理１３１５を実施する。ブール処 理１３１５慣用的に実施できる。というのは、この時点で、探索実行モジュール １２９は、照会ワードＱが現在のページに対してヒットであるか否かを既に識別 しているためである。偽の状態のみが、結果バッファにおいて識別される必要が ある。というのは、ブール照会を満足するページが、ユーザに戻されることにな るためである。ブール処理１３１５は、一般に、以下のようになされる。 照会ワードＱが、ＡＮＤ演算用の引数であり、且つ（ワードキー一致カウンタ により決定されるような）ページに、照会ワードＱの事例が存在しない場合、そ のページを除去するように標示される。 照会ワードＱが、ＮＯＴ演算用の引数であり、且つそのページに照会ワードＱ の事例が存在する場合、そのページを除去するように標示される。照会ワードＱ₁ 、Ｑ₂の任意の対が、ＸＯＲ用の引数であり、且つ唯一それらの両方ともそのペ ージに見出されるか、又はそれらのいずれも見出されない場合、そのページを除 去するように標示される。 照会ワードＱが、句（引用符でのワード列）であり、且つ同一列が見出されな い場合、そのページを除去するように標示される。 ブール処理１３１５の後、探索実行モジュール１２９の処理が続く。 ブール処理１３１５が必要でない場合、探索実行モジュール１２９は続いてル ープ１３０１を終了させ、バンク２１７内の次のページエントリ４１３に対して 繰り返される。終了時に、探索実行モジュール１２９は、制御を探索監視１２３ に戻す。 次に再度、図１１を参照すると、探索監視１２３は次いで、探索リストモジュ ール１３１を呼び出して、探索行程の結果を整理統合する（ステップ１１１３） 。探索結果の整理統合が用いられるのは、所与の文書のページが、多数のバンク ２１７に常駐し得るためである。探索リストモジュール１３１が、結果バッファ を再検討して、今まさに処理されたバンク２１７を識別する。各ヒットのバンク ２１７及びバンクオフセット４１１によるページエントリ４１３が決定されて、 探索リストモジュール１３１が、文書番号をアクセスして、そのページエントリ ４１３を含む文書を取得する。そこから、ＤＦＳファイル２１１をアクセスする ことができ、文書の残りのページがアクセスされて整理統合される。探索照会に 一致する文書の整理統合リストが、探索監視１２３に戻される。 次に、探索監視１２３は、各バンク及び各ドロワにわたってループ１１０５、 １１０３を完了させ、適切なドロワ及びバンクを閉じる。バンク及びドロワの全 てに対する結果が、同様に整理統合され、 探索照会に一致する文書の最終リストが展開されて（ステップ１１１７）、評価 用にユーザに表示される（図７のステップ７１１）。探索監視１２３は次いで、 探索時に使用したメモリを割当て解除して、アプリケーション監視１１９に制御 を戻す（ステップ１１１９）。 情報及び検索システムに関して、本発明のｎグラム分解法を説明した。しかし 、ｎグラム分解の他の多数の利用も、本発明の範囲内にある。Ｎグラム分解は、 他のテキスト処理法又はシステムで、内部の性能を改善するために使用すること ができる。例えば、ｎグラム分解を綴りチェッカで用いて、バッチ又は会話形式 で、間違った綴りのワードを識別して、各々に対して可能な置換の更に正確なリ ストを提供することができる。同様に、ｎグラムをコンピュータ化辞書又は類語 辞典で使用して、ワード根を識別し、また適切な定義又は同義語、反意語、その 他を参照することができる。また、ｎグラムを同様な仕方で文法チェッカで使用 して、文法解析の前にワードを識別することもできる。テキストデータを処理す るためのｎグラム分解のこれら及び他の利用は全て、本発明の範囲内である。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，Ｌ Ｕ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＭＬ，ＭＲ，ＮＥ， ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＫＥ，ＬＳ，ＭＷ，ＳＤ，Ｓ Ｚ，ＵＧ)，ＵＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，ＭＤ ，ＲＵ，ＴＪ，ＴＭ)，ＡＬ，ＡＭ，ＡＴ，ＡＵ，ＡＺ ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ，ＣＺ， ＤＥ，ＤＫ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，ＧＥ，ＨＵ，Ｉ Ｓ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ，ＬＫ，ＬＲ ，ＬＳ，ＬＴ，ＬＵ，ＬＶ，ＭＤ，ＭＧ，ＭＫ，ＭＮ， ＭＷ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，Ｓ Ｄ，ＳＥ，ＳＧ，ＳＩ，ＳＫ，ＴＪ，ＴＭ，ＴＲ，ＴＴ ，ＵＡ，ＵＧ，ＵＺ，ＶＮ (72)発明者 ラヴィチャンドラン，ナタラジャン インド国バンガロール−560040 ヴィジャ ヤナガール，アチグペ，メイン・ロード・ ザ・サード，グッドウィル・アパートメン ト，シテ・51，フラット・15 【要約の続き】 完了すると、ページは、それらが属する文書に関して統 合され、それにより結果として、探索照会に一致する文 書リストとなる。結果はユーザに表示される。

Claims (1)

1. 【特許請求の範囲】 １．複数のワードを含む格納された文書を索引付けして、少なくとも１つの照会 ワードを含む入力探索照会に一致する少なくとも１つの文書を探索する方法にお いて、 各文書の選択されたワードのｎグラムを格納するステップと、 少なくとも１つの照会ワードに対して、少なくとも１つの照会ワードｎグラ ムを決定するステップと、 照会ワードｎグラムのうちの選択されたものに一致するｎグラムを有する文 書を検索するステップと、 を含む方法。 ２．ｎグラムを格納するステップは、 ある文書の各ページの非停止ワードを識別するステップと、 各非停止ワードに対して、少なくとも１つのｎグラムを決定するステップと 、 各ページのｎグラムを格納するステップと、 を更に含む、請求項１の方法。 ３．各ｎグラムに対して、そのｎグラムが生じる少なくとも１つのページのマッ プを格納するステップと、 ｎグラムのリストに対応して、マップのリストを格納するステップと、 を更に含む、請求項２の方法。 ４．文書を検索するステップは、 照会ワードｎグラムをｎグラムのリストの１つに突合せるス テップと、 ｎグラムのリストの１つの対応するマップを決定するステップと、 マップから、照会ワードｎグラムを含むページを決定するステップと、 ページ、及びそれと関連した文書を検索するステップと、 を更に含む、請求項３の方法。 ５．ｎグラムにより文書を索引付けするための記憶構造を備えるコンピュータ読 み取り可能メモリであって、各文書は文書番号、文書名、及び少なくとも１つの ページを有し、各ページはページ番号を有するコンピュータ読み取り可能メモリ において、 ページエントリのリストからなるバンクであって、各ページエントリは、そ のページを含む文書の文書番号によりページを、また文書内のページ番号を識別 する、バンクと、 バンクと関連したバンク索引であって、 ｉ）複数のｎグラム・エントリマップであって、各ｎグラム・エントリマッ プは単一のｎグラムと関連し、選択されたｎグラム・エントリマップは、バンク で識別された少なくとも１つのページが、ｎグラム・エントリマップと関連した ｎグラムを含む索引エントリマップへの索引を有する、複数のｎグラム・エント リマップと、 ii）複数の索引エントリマップであって、各索引エントリマップは、ｎグラ ム・エントリマップの１つにより索引付け られ、各索引エントリマップは、索引エントリマップを索引付けするｎグラム・ エントリマップと関連したｎグラムを含むあるページを識別する、バンク内の各 ページエントリを識別する、複数の索引エントリマップと、 を備えるバンク索引と、 からなるコンピュータ読み取り可能メモリ。 ６．バンク内の各ページエントリはオフセットを有し、 各索引エントリマップは複数のビット位置を含み、各ビット位置はバンク内 のあるページエントリと関連し、各ビット位置は、そのビット位置と関連したペ ージエントリにおいて識別されるページが、索引エントリマップを索引付けする ｎグラム・エントリマップと関連したｎグラムを含む第１の値と、そのビット位 置と関連したページエントリにおいて識別されるページが、索引エントリマップ を索引付けするｎグラム・エントリマップと関連したｎグラムを含まない第２の 値とを有する、請求項５のコンピュータ読み取り可能メモリ。 ７．ドロワから更になり、該ドロワは、 ｉ）文書のリストであって、各文書は該リスト内で固有に識別される、文書の リストと、 ii）複数のバンク、及び関連したバンク索引と、 iii）複数のバンクの各々に対して、バンク内の多数の空ページエントリのカ ウント値を含むバンクリストと、 を備える、請求項５のコンピュータ読み取り可能メモリ。 ８．各バンクは更に、 少なくとも１つのページキーを含むページキーテーブルであって、各ページ キーはバンク内のあるページエントリと関連し、 ｉ）ページの各ワードに対して、そのワード内のｎグラムのリストを備えるペ ージキーテーブルからなる、請求項５のコンピュータ読み取り可能メモリ。 ９．文書を検索するコンピュータ実施の方法において、 コンピュータ読み取り可能メモリ上に、請求項５の記憶構造を格納するステ ップと、 照会語を受信するステップであって、照会語内の多数のｎグラムの各々に対 して、 ｉ）照会語のｎグラムと関連したバンク索引内のｎグラムマップから、ある索 引エントリマップがｎグラムに対して存在するか否かを判定するステップと、 ii）現存する索引エントリマップに応答して、索引エントリマップから、索引 エントリマップと関連したｎグラムを含むあるページを識別する、バンク内の各 ページエントリを決定するステップと、 iii）ｎグラムを含む各ページに対して、ｎグラムカウンタをインクリメント するステップと、 を含むステップと、 バンク内の各ページに対して、そのページに対するｎグラムカウンタが、そ のページが照会語を含むことを示すために、照 会語内のｎグラムの数と十分類似しているか否かを判定するステップと、 照会語内のｎグラムの数と十分類似しているページ用のｎグラムカウンタに 応答して、後続の照会解析のためのページを含む文書を検索するステップと、 を含む方法。 10．ページ用のｎグラムカウンタが、照会語内のｎグラムの数と十分類似するの は、 Ｇ［Ｐ］≦Ｋ＊Ｅ／１００ の場合であり、ここで、Ｐはページであり、Ｇ［Ｐ］はページＰ用のｎグラム 一致カウンタであり、Ｋは照会語内のｎグラム数であり、Ｅはｎグラム一致カウ ンタとＫの間の一致の割合を制御するために選択された、一致パラメータである 、請求項９のコンピュータ実施の方法。 11．複数の文書を索引付けするコンピュータ実施の方法であって、各文書は少な くとも１つのページを有し、各ページは、データの最大量よりすくないデータ量 を有し、また複数のワードを有する、コンピュータ実施の方法において、 ページのリストを格納するステップであって、各ページはある文書と関連す る、ステップと、 ｎグラムのリストを決定するステップと、 各ｎグラムに対して、そのｎグラムを含むページのマップを確立するステッ プであって、該ステップは、 ｉ）文書から現在のページを検索するステップと、 ii）該現在のページの各非停止ワードに対して、 １）ワード内のｎグラムを決定するステップと、 ２）ワード内の各ｎグラムに対して、そのｎグラムと固有に関連し、またペ ージのリスト内の各ページに対するあるエントリを含むマップにおいて、ページ がｎグラムを含むことを指示するように、現在のページに対するエントリを更新 するステップと、 により行われる、ステップと、 を含むコンピュータ実施の方法。 12．照会語を含む書類を更に検索するために、 照会語を受信するステップと、 該照会語内の多数のｎグラムの各々に対して、 ｉ）マップがそのｎグラムに対して存在するか否かを判定するステップと、 ii）現存するマップに応答して、そのマップから、マップと関連したｎグラ ムを含むリスト内の各ページを決定するステップと、 iii）リスト内の各ページに対して、そのページが、照会語を含むことを指 示するために、照会語内の十分な数のｎグラムを含むか否かを判定するステップ と、 照会語を含む各ページに応答して、後続の照会解析のためにそのページを含 む文書を検索するステップと、 を含む、請求項１１のコンピュータ実施の方法。 13．請求項１１のステップを実行するために、プロセッサを構成及び制御するコ ンピュータ・プログラムを含む、コンピュータ読み取り可能メモリ。 14．各文書が少なくともいつのページを含む、複数の文書を索引付けするプロセ ッサを制御するためのコンピュータ読み取り可能メモリにおいて、 索引付きページのリストと、 索引マップのリストであって、各索引マップは、１つのｎグラムと固有に関 連し、且つ複数のエントリを有し、各エントリは、索引付きページのリスト内の ページと固有に関連し、且つそのページが、索引マップと関連したｎグラムを含 むか否かを指示する、索引マップのリストと、 ページ索引付けモジュールであって、 ｉ）索引付けすべき現在のページを受け取り、 ii）索引付きページのリストにおいて、現在のページに対するエントリを作 成し、 iii）現在のページの各非停止ワードに対して、ワード内のｎグラムのリス トを格納して、 iv）各ｎグラムに対して、現在のページがｎグラムを含むことを指示するた めに、ｎグラムと関連した索引マップにおいて、現在のページに対するエントリ を更新する、 ページ索引付けモジュールと、 からなるコンピュータ読み取り可能メモリ。 15．ページ索引付けモジュールは、現在のページの非停止ワードに対して、 ワード内の各ｎグラムに対してｎグラム番号を決定し、 ワード内の各ｎグラムのｎグラム番号を格納して、 現在のページと、格納されたｎグラム番号を関連づけることにより、ワード 内のｎグラムのリストを格納する、請求項１４のコンピュータ読み取り可能メモ リ。 16．あるワードのｎグラム番号は、 という式により決定され、ここで、ＮＧはワードのｎグラム番号であり、ｘは ワードの第ｉ文字のｎグラム文字番号であり、Ｃ_maxは索引付け可能な文字の総 数であり、Ｎ_pはｎグラム内のレターの所望数である、請求項１５のコンピュー タ読み取り可能メモリ。 17．各文書が少なくとも１つのページを含む、複数の文書からの照会語を含む文 書を索引付けするプロセッサを制御するためのコンピュータ読み取り可能メモリ において、 各ページがある文書と関連した、索引付きページのリストと、 索引マップのリストであって、各索引マップは、１つのｎグラムと固有に関 連し、且つ複数のエントリを有し、各エントリは、索引付きページのリスト内の ページと固有に関連し、且つ そのページが、索引マップと関連したｎグラムを含むか否かを指示する、索引マ ップのリストと、 探索モジュールであって、 ｉ）照会語を受け取り、 ii）照会語内の多数のｎグラムの各々に対して、 iii）照会語内の多数のｎグラムの各々に対して、そのｎグラムと関連した 索引マップがあるか否かを判定し、 iv）現存する索引マップに応答して、その索引マップから、マップと関連し たｎグラムを含む索引付きページのリスト内の各ページを決定し、 ｖ）索引付きページのリスト内の各ページに対して、そのページが、照会語 を含むことを指示するために、照会語内の充分な数のｎグラムを含むか否かを判 定し、 vi）照会語を含むページに応答して、後続の照会解析のためにそのページを 含む文書を検索する、 探索モジュールと、 からなるコンピュータ読み取り可能メモリ。 18．探索モジュールは、あるページが、照会語内の充分な数のｎグラムを含むか 否かを、 Ｇ［Ｐ］≦Ｋ＊Ｅ／１００ という式により判定し、ここで、Ｐはページであり、Ｇ［Ｐ］はページＰ内に 含まれる照会語におけるｎグラム数であり、Ｋは照会語内のｎグラム数であり、 Ｅは、ページＰ内に含まれる 照会語内のｎグラム数とＫの間の一致の割合を制御するために選択された、一致 パラメータである、請求項１７のコンピュータ読み取り可能メモリ。