(57)【特許請求の範囲】
【請求項１】
有限数のテキスト源における項目の文書処理的情報を文書処理システムが処理する方法において、
（ａ）  前記テキスト源の各々における項目を、これら項目の発生頻度に基づいてリニアな配列に並べるステップと、
（ｂ）  前記テキスト源の各々における前記項目の各々のランク番号を、前記リニアな配列に基づいて決定するステップと、
（ｃ）  前記テキスト源の各々における前記項目の各々に、当該テキスト源内の項目の前記ランク番号に対応するような順序番号を割り当てるステップと、
（ｄ）  前記テキスト源の各々に対して、当該テキスト源における個々の項目に各々割り当てられる一連のデータ群を前記順序番号の順にメモリに記憶するステップであって、これらデータ群の各々が、
（イ）前記個々の項目と同一の項目を有する次のテキスト源の識別情報と、
（ロ）前記次のテキスト源における前記個々の項目の前記順序番号と、該個々の項目の前記リニアな配列におけるランク番号との両方を示すオフセット値と、
を有するようなステップと、
（ｅ）  前記項目の各々に関して前記テキスト源のうちの最初のテキスト源の識別情報と該最初のテキスト源におけるオフセット値とを有するような第１テーブルと、該第１テーブルにより示される前記最初のテキスト源の各々に対して前記一連のデータ群のうちの最初のデータ群の位置を示すような第２テーブルとを設けるステップと、
を有していることを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、或る項目の発生頻度に関するランクと、該項目の公称重みとの間の関係により支配される正規化係数を記憶するステップを更に有し、前記正規化係数が当該ランクと、変数としての特定のテキスト源における異なる項目の数とに専ら依存することを特徴とする方法。
【請求項３】
請求項２に記載の方法であって、更に、各テキスト源に関して前記正規化係数を記憶し、これにより、入力される各オフセットの値を当該テキスト源における項目の数に依存するような重み係数に正規化するステップを有することを特徴とする方法。
【請求項４】
請求項３に記載の方法であって、テキスト源における各項目に対する前記重み係数が、該各項目の発生頻度のランクの平方根に逆比例することを特徴とする方法。
【請求項５】
全テキスト検索システムが実施する、語の派生的項目にアクセスする方法であって、前記派生的項目が複数の文書に関して記憶されているような方法において、
特定の語の表現の入力を受け付けるステップと、
メモリ上の派生的項目ベーステーブルを用いて前記特定の語の最初の派生的項目をサーチするステップであって、前記派生的項目ベーステーブルは、各語に関して、前記複数の文書のうちの当該語を含むような最初の文書の文書識別情報と、該最初の文書における当該語の派生的項目に対するオフセット値とを前記メモリに記憶しているようなステップと、
ループを実行するステップであって、各ループ行程においては最も新しい文書識別情報と最も新しいオフセット値とを用いて前記特定の語と同一の語に対応する次の派生的項目のアドレスを計算し、これによりアドレスされた各派生的項目は、前記特定の語と同一の語を含むような次の文書の文書識別情報と、該次の文書における前記特定の語に対応する派生的項目のオフセット値とを含むようなステップと、
前記各ループ行程において、更に、前記オフセット値を、アドレスされるべき次の派生的項目へのポインタとして、及び前記特定の語に関連する当該ループ行程に関連する文書における該特定の語の発生頻度に関しての重みを表す数として使用するステップと、
を有し、
前記メモリ上の前記派生的項目ベーステーブルにおける前記文書識別情報は、各文書に関してベースアドレスポインタを記憶したメモリ上の文書ベースアドレステーブルをアドレスし、前記次の派生的項目のアドレスは、前記文書識別情報に対応する前記文書ベースアドレスポインタを、前記派生的項目ベーステーブルにおける対応する前記オフセット値に加算することにより計算されることを特徴とする方法。
【請求項６】
請求項５に記載の方法であって、更に、前記文書識別情報を用いて正規化テーブル内の重み正規化係数をアドレスし、該重み正規化係数は対応する前記オフセット値と組み合わされて前記特定の語の重み量となることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
この発明は、限られたテキスト源（例えば、文書のテキスト）の項目（例えば、語）に関する文書処理情報(bibliometric information)を記憶する方法に関する。
【０００２】
【従来の技術】
本明細書における用語に関しては、ジャーナル・オブ・ドキュメンテイション、1988年３月第１号第44巻のL. Eggheによる「古典的文書処理法の分類について」なる記事を参照されたい。ある項目に就いての文書処理情報とは、該項目の意味については要約されているが、テキスト源における当該項目について言うことができる全ての事項を示す。限定するものではない例として示すと、文書処理情報は次のような情報を有することができる。
−当該項目が情報源（通常はテキスト源）においてどの程度頻繁に発生するか；
−その発生の広がりはどのようであるか、例えば、それらの発生は集団化しているか否か；
−当該情報源内の他の項目との空間的な関係；
−当該項目がどのような位置で（例えばヘッダのみで）発生するのか。
Egghe の記事より明らかなように、科学としての文書処理は少なくとも20年の歴史がある。
【０００３】
【発明の目的及び概要】
そして、本発明のおおまかな目的は、文書処理情報の容量の少ない及び容易な記憶、並びにその操作の探求にあり、限定するものではないが、特にはテキスト源そのものの検索、さもなければ管理を指向するものである。更に詳細には、本発明の目的は、例えば、多数のテキスト源を含むデータベースから所望のテキスト源を検索するようなシステムにおいて、各テキスト源内の多数の項目（例えば、検索のキーとして使用することが可能な語）に関する情報（本明細書における文書処理情報：例えば、語の重み情報）を少ない容量で容易に記憶しておくことができ、且つ、斯かる情報の処理が容易となるような方法を提供することにある。本発明のキーとなる理解のうちの一つは、上記文書処理情報が、かなり変化しても基本的情報は高程度にそのまま保たれるという点において、あまり正確な量ではなくても良いということである。
一つの構成によれば、本発明は、テキスト源における項目に関する文書処理情報を、該テキスト源における或る項目の文書処理的特性と、該文書処理特性に関する所定の規則に基づいた前記テキスト源における全項目のリニアな配列における前記或る項目のランク番号との間の関係を用いて記憶する方法において、
（ａ）前記テキスト源における各項目に関し、前記各項目を前記リニアな配列で配置すると共に、該配列から前記各項目の前記リニアな配列におけるランク番号を決定し、
（ｂ）前記テキスト源における各項目に関し、前記（ａ）の過程において決定された前記各項目のランク番号を当該各項目の文書処理的特性を表す情報として記憶する、
ステップを有していることを特徴とするような方法を提供する。リニアな配列とは、各項目が所定の規則に関して全ての他の項目に対し相対的位置を有し、従って固有のランク（順位）番号が割り当てられることを意味している。更に詳細には、上記項目が或るテキスト源内の語に対応し、上記所定の規則が該テキスト源内の各語を発生頻度順に並べるという規則であると仮定した場合、上記リニアな配列とは、例えば最も発生頻度の高い語を先頭とし、最も発生頻度の低い語を末尾とするような全ての語の配列である。このようなリニアな配列においては、当該テキスト源がｎ個の異なる語を含むとすると、先頭の語が最高のランク（rank:順位）番号「１」を有し、末尾の語が最低のランク番号「ｎ」を有することになる。そして上記構成の方法の場合、ランク番号の記憶は文書処理特性そのものを記憶するというよりは、少ない情報量となる代用物の記憶となるので、多くの場合、５０％の記憶空間の節約となる一方、アクセスのよさは維持される。上記においては、リニアな配列は文書処理的な規則に基づく順序のものであるが、例えば各テキスト源の著者によるアルファベット順のもの、発生日付による年代順のものであってもよい。原理的には、他の多くのリニアな順序が利用可能である。
【０００４】
他の有利な構成によれば、本発明による上記方法は、前記過程（ａ）及び（ｂ）を複数のテキスト源の各々に対して繰り返すと共に、前記複数のテキスト源の結果としての文書処理情報を、
（ａ）メモリのアドレス内に記憶するために、各テキスト源における各項目に対して、前記複数のテキスト源において一様であると共に各テキスト源においては前記リニアな配列を維持するようなアドレスマッピング変換規則に基づいて順序番号を割り当て、
（ｂ）各テキスト源に関して、前記各テキスト源における項目に各々割り当てられるデータ組の系列を前記順序番号に従って前記メモリに記憶し、
ここで、前記各データ組が、
（b1）当該データ組に対応する項目と同一の項目を有する次のテキスト源の識別情報と、
（b2）前記次のテキスト源における当該項目の前記順序番号と、当該項目の文書処理的特性を表す情報としての当該項目の前記リニアな配列におけるランク番号との両方を示すオフセット値と、
を有するようにしてリンクするステップを更に有していることを特徴とする。このようにリンクされて記憶された文書処理情報は、本発明の他の有利な用途を提供する。
【０００５】
特定の利用分野においては、本発明は、例えば多数のテキスト文書を含むデータベースから所望のテキスト文書を検索するような、全テキスト文書検索システムに使用される文書の各語の派生的項目（postings;  後述する）を記憶する方法に関し、特に文書内の各々の語彙的な語（lexical term）に当該文書における該語の関連性（重要性）を示す重みが割り当てられるような種類の検索に関するものである。ここで、上記の語彙的語とは、単に文法上必要とされる文法的語（例えば、接続詞又は英語における冠詞等）とは異なり、語彙を形成する語であり、例えば名詞、副詞、数及び数式等を指す。この発明は上記システムが動的環境において使用される場合に特に有効である。従来の重み割当法は、"情報処理及び管理"1988年第24号、513 〜523 頁、のG. Salton 及びC. Buckleyによる「自動テキスト検索における語の重み付けの取組法」に述べられており、該文献の特に518 頁は語の頻度、集合頻度及び正規化のような重み成分の種々の用法に基づく種々の重み付けシステムを示している。動的な検索環境においては、文書の群は、特に文書が追加されたり削除されたりするという理由により、一定ではない。通常、重みを使用するということは、文書の或る種のランク付けが、これら文書と何らかの例示的語、語の繋がり若しくは組又はテキストとの一致性に基づいて、重みに基づく一致性を考慮して行われるということである。文書のランク付けの後において、その後の使用のために全文書の中の一つ又はそれ以上の文書にアクセスすることは使用者次第であろうが、この後者の使用は本発明の一部をなすものではない。本発明は、先ず、重みは非常に正確な量とはいえないが、他の量、すなわち各語彙的語の発生頻度、には十分正確に関連しているので、後者の各語彙的語の発生頻度をその代わりに使用することができる、という洞察に基づいている。第２に、同一の語彙的語に関連する派生的項目の記憶は、各派生的項目に十分なポインタ情報を含めることにより、鎖状にリンクすることができるという洞察に基づく。ここで、本明細書における派生的項目(posting) とは、文書中の特定の語彙的語、従って単一文書における上記と同一の特定の語彙的語の全ての発生、に固有に関連するような情報項目として定義される。本発明では、上記派生的項目は、少なくとも当該文書の識別情報と、当該文書における関連する語の重みの表示とを有する。本発明の拡張された例においては、上記派生的項目は前記語彙的語自身の識別情報も含む。更に他の見方によれば、本発明は上述したような方法であって、限定された記憶空間及び妥協のないサーチ速度を可能にし、それでいてデータベースを拡張し且つ文書を他の文書に置換することができるような方法を提供する。このために、本発明による方法は、或る項目の発生頻度に関するランクと、該項目の公称重みとの間の関係により支配される正規化係数を記憶するステップを更に有し、前記正規化係数が当該ランクと、変数としての特定のテキスト源における異なる項目の数とに専ら依存することを特徴とする。
【０００６】
本発明は、更に、上述した方法により発生されるデータベースに基づく文書検索システムにも関する。このようなデータベースはＣＤ−ＲＯＭ上で又はオンラインで提供することができ、上記検索にはランダムアクセス記憶を利用することができる。
【０００７】
【実施例】
以下に、語の重み付け型文書検索システムにおけるメモリに、できるだけ多くの派生的項目を記憶するための派生的項目の圧縮に関して説明する。効果的には、高速処理を実現するために、上記メモリは計算機の固体主メモリのような直接アドレスが可能なものとする。これによれば、派生的項目用の記憶容量を２５％から５０％削減するような派生的項目圧縮技術が得られる。この圧縮技術は、新たな文書の挿入に際して如何なる長大なインデクシング処理も必要としないので、高度に動的な検索環境においても使用することができる。上記技術はベクトル空間検索モデルに基づいているので、検索品質は高い。
【０００８】
語重み付け型検索においては、語の重みはテキスト中に発生する各語に関連したものとなる。そのようなテキストは、文書データベース内の文書のテキストであるか、又はユーザにより提示された質問のテキストとすることができる（文書は、テキスト情報以上のものを含むことができる）。語の重みｗは、テキストｔ内の語（即ち単語又は語幹）ｓと関連付けられた場合、テキストｔ内における語ｓの関連性を示し、通常正規化の後「０」と「１」との間にあるような実数である。ここで、「０」は全く関連性がないことを示し、「１」は最大の関連性を示す。語の重みは、最終的に、文書データベース内に記憶された各文書と、ユーザにより提示された質問との間のテキストの類似性を計算するために使用される。上記のような質問は、上記データベースに記憶された全ての文書を前記質問テキストに対する類似性が減少する順に一覧（リスト）することにより回答される。
【０００９】
語の重みの計算は、種々の方法で行うことができる。ここでは、以下の方法が使用される。ここで、文書データベース内の全てのテキストｄ、質問テキストｑ及び語（即ち単語又は語幹）ｓに関して、frq(s, d) 及びfrq(s, q) を、各々、テキストｄにおける語ｓの発生頻度（即ち、発生回数）及び質問テキストｑにおける語ｓの発生頻度とする。ここで、ｉは「１」、「２」、「３」又は「４」のいずれか１つに等しいから、データベース内のテキストｄにおける語ｓの文書の語の重み docu-wghti (s, d)、及び質問テキストｑにおける語ｓの質問語の重み quer-wghti (s, q)は以下のようにして計算される。
【００１０】
【数１】
0003767909.tif 000002
及び
【数２】
0003767909.tif 000003
【００１１】
上記において、Ｎは文書データベースに記憶された全ての文書テキストの合計数であり、ｎs 及びｎr は語ｓ又はｒを各々含むこれらの文書テキストの数である。ここで、log Ｎ／ｎs 及びlog Ｎ／ｎr は、各々、語ｓ及びｒのいわゆる逆文書頻度である。更に、ｉの値が大きければ大きいほど、これらの逆文書頻度が語の重みに一層貢献するようになり、発生頻度の役割はより重要でなくなる。先に示したように、ｉの標準値は［１，４］における整数であるが、これは明示的な限定ではない。
【００１２】
前述したように、文書の語の重み及び質問語の重みは、文書データベースにおける文書と質問との間におけるテキストの類似性を計算するために使用される。ｉ＝１，２，３，４に関しては、文書テキストｄと質問テキストｑとの間の斯様な類似性text-simi (d, q)は、文書語の重みベクトルと質問語の重みベクトル（これらの語の重みベクトルの成分は、全ての可能性のある語の対応する語の重みである）との内積として計算される。
【００１３】
【数３】
0003767909.tif 000004
【００１４】
文書語重みベクトルと質問語重みベクトルとは長さに関して正規化されるので、テキスト類似値は常に「０」と「１」との間にある。実験的に、特にｉ＝２の場合は生の発生頻度に対する注意の低下を犠牲にして逆文書頻度に対する注意を増加させると、そのような注意のずらしを伴わない場合に較べてより良好な検索結果が得られ、特に、ｉ＝１の場合よりも良好な検索結果が得られることが分かっている。以下においては、ｉ＝２を使用する。
【００１５】
我々の式においては、逆文書頻度（例えば、log Ｎ／ｎs 及びlog Ｎ／ｎr ）は質問語重みのみに組み入れられることが分かる。このことは、文書語重みに組み入れると、文書データベースにおける変更の度に、全てのこれらの語重みの再計算を要するという事実による。言い換えれば、ここで提案された解決法は、非常に動的であるというような我々の目標とする環境により良く適合している。それでもなお、上記の全てにかかわらず、我々の方法は依然としてベクトル空間検索モデル内での構成と考えられることが分かる。
【００１６】
派生的項目の圧縮
ここで、語ｓに関連する派生的項目ｐが、ｗが（文書識別情報を伴う）文書ｄにおける語ｓの語重みとなるようなデータ対ｐ＝（ｄ，ｗ）であることを回想されたい。
【００１７】
下記の例においては、派生的項目を記憶すべき文書が最大で65,536 個あると仮定する。更に、平均して文書当たり最大で256 個の異なる語、従って文書当たりの派生的項目、があると仮定する。このことは、文書識別情報は２バイトで記憶することができ、特有の派生的項目の識別情報、即ち派生的項目へのポインタは３バイトでのみ記憶することができることを意味する。最後に、語の重みの記憶のために１バイトあれば、大いに関連する語と、あまり関連しない語との間の識別をするのに十分な程正確であると仮定する。これらのパラメータ値に関する他の選択に関しては、本発明の方法のステップ及び利点は同じままである。
【００１８】
動的環境に対しては、リンクされたリストの方法が有効であると考えられる。この方法においては、同一の語彙的語に関連する全ての派生的項目をリンクする。第１に、語ｓに関連する派生的項目ｐ＝（ｄ，ｗ）が、語ｓに関連する３つ組データ［ｄ，ｗ，ｌ］として構成され、ここでｌは、同一の語ｓに関連する次の派生的項目の３つ組データへのリンク、即ちポインタである。第２に、同一の（文書識別情報を伴う）文書ｄの全ての派生的項目の３つ組データは、派生的項目３つ組データ系列Ｐd 内に隣接して記憶される。第３に、上記のような全ての派生的項目３つ組データ系列Ｐd は、１個の大きな派生的項目３つ組データ系列Ｐとなるように連結され、これにより前記文書データベースにおける全ての文書の全ての派生的項目を符号化する。最後に、派生的項目ベーステーブルＴが存在し、該テーブルは各語ｓに関し、上記系列Ｐ内の語ｓに関連する最初の派生的項目３つ組データへのポインタを返送する。明らかに、語ｓに関連する全ての派生的項目は、上記テーブルＴを使用することにより語ｓに関連する最初の派生的項目３つ組データにおいて上記系列Ｐに入り込み、次いで上記リンクを用いて、当該語ｓに関連する後続の派生的項目３つ組データへ移動することにより、得ることができる。
【００１９】
文書毎に派生的項目をグループ化する上記方法を用いれば、文書データベースへの新たな（文書識別情報を伴う）文書ｄの挿入は容易である。即ち、該新文書ｄの全ての派生的項目３つ組データは、上記系列Ｐの末尾に派生的項目３つ組データ系列Ｐdとして隣接して記憶される。文書データベースの寸法に関して前述のようになした仮定の下では、当該方法は各派生的項目に関して６バイトを要する。即ち、文書識別情報に２バイト、語の重みに１バイト、そして次の派生的項目３つ組データへのポインタに３バイトである。
【００２０】
ここで、動的環境で記憶容量の消費を３３％低減する方法を提示する。上記においては、語ｓに関連する派生的項目ｐ＝（ｄ，ｗ）は、語ｓに関連する３つ組データ［ｄ，ｗ，ｌ］として構成され、ここで、ｌは同一の語ｓに関連する次の派生的項目３つ組データへのリンク、即ちポインタであった。この方法は、同一の文書ｄの全ての派生的項目３つ組データを派生的項目３つ組データ系列内Ｐｄ内に隣接して記憶するので、ｌは(d', o')なる対により置換することが可能であり、ここで、d'は同一の語ｓに関連する次の派生的項目における文書識別情報であり、o'は系列Ｐd'における対応する３つ組データのオフセットである。上記のような置換は、追加のテーブル（文書ベースアドレステーブル）Ｄを想定しており、該テーブルは各文書識別情報ｄ’に対して系列Ｐd 'における最初の派生的項目３つ組データの位置（アドレス）を返送する。テーブル（派生的項目ベーステーブル）Ｔが、各語ｓに関して語ｓに関連する最初の派生的項目の文書識別情報ｄと、系列Ｐdにおける対応する派生的項目３つ組データのオフセットとを、各々、返送する２個のテーブルＴD及びＴOにより置換されると仮定する。明らかに、ＴD、Ｄ及びＴOを使用して語ｓに関連する最初の派生的項目３つ組データにおいて系列Ｐに入り込み、次いでリンク及びテーブルＤを繰り返し用いて同一の語ｓに関連する後続の派生的項目３つ組データへ移動すれば、該語ｓに関連する全ての派生的項目を得ることができる。
【００２１】
語ｓに関連した派生的項目ｐにおける文書識別情報ｄは、対応する派生的項目３つ組データｐtが系列Ｐdにおいてアクセスされる以前に知ることができることに注意されたい（ｄは既に３つ組データｐtへのポインタの一部であったからである）。かくして、派生的項目３つ組データｐtは文書識別情報ｄなしで記憶することができる。上記から、１≦ｊ≦ｎとした場合の語ｓに関連するｎ個の派生的項目ｐj＝（ｄj，ｗi）は、語ｓに関連するｎ個の派生的項目３つ組データｐt, j＝［ｗｊj，ｄj+1，ｏj+1］として構成することができ、ここで、ｏi+1はPdj+1におけるｐt, j+1のオフセットであり、ｄn+1およびｏn+1は不定である。
【００２２】
当該方法はオフセットと共に動作する場合及び文書ベースアドレステーブルＤを使用する場合、幾らかの記帳用の時間及び記憶空間を要する。しかしながら、前述した仮定及び文書当たり256 個以上の語は無いとの仮定の下では、派生的項目当たり６バイトの代わりに４バイトしか必要でなくなる。この場合、１バイトは語の重み、２バイトは文書識別情報及び１バイトはオフセット用である。ここで、ｋ個以上の語を伴う文書が存在すると仮定する。この場合、この文書の派生的項目の全組は、ｋ個の派生的項目の１以上の組と、ｋ個以下の派生的項目の１つの組とに分割することができる。更に、何らかの補助テーブルを用いて互いに結合するために、これらの組の各々は擬似文書識別情報に関連付けることができるが、上記テーブルは擬似文書識別情報を対応する実際の文書識別情報に関係付ける。
【００２３】
ジップのランク−頻度の法則
この節においては、前述したEgghe による引用文献に述べられているジップ（G. Zipf ）のランク−頻度法則を参照する。ジップによれば、テキスト中の全語が減少する発生頻度に応じてランク付けされている場合は、該テキストにおける語の発生頻度と、そのランク番号との間にはある関係が成り立つ。形式的に述べなければ、そのような発生頻度とランク番号との積は概ね一定であることが分かった。
【００２４】
もっと形式的に言えば、このジップのランク−頻度法則は以下のように表すことができる。テキストｔと該テキストｔにおける語ｓに関して、frq(s, t) をテキストｔにおける語ｓの発生頻度とする。また、ｔをｎ≧１個の異なる語ｓ1 ，…，ｓn を含むテキストとし、更にこれらの語が、普遍性を失うことなく、
frq(ｓ1，ｔ) ≧frq(ｓ2，ｔ) ≧…≧frq(ｓn，ｔ)
が成り立つようにランク付けされていると仮定する。この場合、ジップのランク−頻度法則は、１≦ｊ≦ｎなる各ｊに関して、ｊ・frq(ｓj，ｔ)とzpf(t) とが略等しくなるような一定のzpf(t)が存在する、即ちテキストｔにおいては語ｓiのランク番号ｊと語ｓjの発生頻度frq(ｓj，ｔ) との積は概ね一定である、と主張している。明らかに、ジップの定数zpf(t)はテキストｔに依存し、テキストｔの大きさが増加すると、テキストｔにおける最も頻繁な語の発生頻度とテキストｔにおける異なる語の数とは増加し（ジップの法則によれば、これらは一様に増加する）、かくしてzpf(t)もまた増加する。
【００２５】
実際には、ジップの法則は中程度の発生頻度を有する語に最も適合することが分かった。1000個以上の異なる語を持つ例示的な文書に関しては、８ないし600 のランクは±25％以下のジップの積の値の広がりを有するが、40ないし300のランクに関してはその広がりは±10％のみである。
【００２６】
ジップの法則の使用
このように、ジップのランク−頻度の法則は、語の発生頻度は全ての語が減少する発生頻度に応じてランク付けされている場合には語のランク番号を用いて推定することができることを意味している。もっと正確には、各テキストｔに関して、テキストｔにおける各語ｓに対して当該語ｓの発生頻度がzpf(t)と当該語ｓのランク番号との商により近似されるような定数のzpf(t)が存在する。
【００２７】
前述した一般的な派生的項目の圧縮技術に関しては、以下の事項を特記することができる。第１に、文書の派生的項目が記憶される順序が考慮されていない。第２に、必要とされる記憶のかなりの部分を使用してしまうが、語の重みは派生的項目においては圧縮されていない。
【００２８】
語の重みが語の発生頻度のみを用いて計算されるような語重み付け検索方法に関して、上述した検討の結果、文書の派生的項目の記憶に関する以下に説明するような本発明による進んだ圧縮技術に到達した。先ず、全ての文書の語の派生的項目を、対応する語の発生頻度の減少に応じてランク付けする。次に、これらの派生的項目を前述したのと同様の方法により且つ同様の補助テーブルを用いてメモリに上記のランク順序で記憶する。しかしながら、これらの派生的項目における語の重みは実際には記憶せず、検索時において対応する派生的項目３つ組データのランク番号、即ち該３つ組データへのオフセットに対して上記ランク−頻度の法則を適用することにより近似される。このように、派生的項目３つ組データ［ｗ’，ｄ，ｏ］の代わりに、派生的項目のデータ組［ｄ，ｏ］とテーブルＴD、Ｄ及びＴOのみを記憶する。
【００２９】
この圧縮技術を用いると、所定のジップ定数を持つ追加のテーブルにアクセスする必要があると思われる。更に、検索時における時間的効率の理由から、各文書に関して予め計算された語重み正規化成分（式（１）参照）を含む第２のテーブルにアクセルするのが経済的であるように思われる。しかしながら、多くの語重み検索方法に関しては、各文書に関する異なる語の数がどうにかして利用可能である場合には、両テーブルを省略することができることが分かった。
【００３０】
従って、ジップのランク−頻度の法則は、文書の派生的項目を３バイトのみを用いて記憶するために利用することができる。以下においては、語の重みを近似するために用いる式を扱う。
【００３１】
前述したように、検討された記憶及び圧縮技術は語の発生頻度の近似に基づくものである。この場合、テキストｔ及び該テキストｔにおける語ｓに関し、テキストｔにおける語ｓの発生頻度frq(s, t) は、frq(s, t) とzpf(t)/rnk(s, t)とが略等しいことにより近似することができ、ここでzpf(t)はテキストｔに関連するジップの定数であり、rnk(s, t) は減少する発生頻度に応じてテキストｔにおける全ての語のランク付けした場合の当該語ｓのランク番号である（以下においても、これらの定義を使用する）。文書重みの計算に当該式を用いると、文書テキストｄにおける語ｓの文書語重みを近似する下記の式が得られる（ｉ＝１，２，３，４）
【数４】
0003767909.tif 000005
【００３２】
かくしてジップ定数zpf(d)をうまく取り除くことができる。結果として、文書ｄに関連する正規化係数は、文書ｄにおける異なる語彙的語の数にのみ依存するようになる。また、実験的に、高頻度の語に関しては文書語重みは過度に高く近似され、低頻度の語に関してはこれらの重みは過度に低く近似されることが分かった。そして、一層の改善が、生の発生頻度そのものの代わりに、推定された発生頻度の平方根を採ることにより得られる。このようにして、文書テキストｄにおける語ｓの文書語重みを近似する下記の式が得られた（ｉ＝１，２，３，４）
【数５】
0003767909.tif 000006
【００３３】
好ましい実施態様
図１は、本発明を一般的に構成した場合の限定されたテキスト源（ソース）における項目（例えば、語彙的語）に関する文書処理情報を記憶する方法のフローチャートである。図のブロック100 においては、中間記憶空間及び必要なレジスタを割り当て、当該項目の文書処理特性と当該テキスト源の全項目についてのリニアな配列における該項目のランク番号との間の所定の関係を特定することによって、処理が初期化される。ブロック102 においては、前記テキスト源の各項目が順次入力され、それらのリニア順序値に関して評価がされる。このためには種々の方法がある。第１に、この値は当該項目の発生のみから直接に又はその環境との関係において認識することができる。第２に、当該項目から文書処理値自体を推測し、これをリニアな順序値に変換することも可能である。この評価は、計算（例えば、発生の総和）による、ヒストグラム的又は他の統計的処理のいずれかを必要とするであろう。前記の限られたテキスト源の全項目が入力された後に各項目に関して処理可能な量として上記のリニアな順序値を割り当てるためには多くても限られた時間しか掛からないと考えられる。ブロック104 においては、上記の各項目は例えばそれらのスカラー、即ちアルファベット、論理又はその他の測定可能な量の減少に応じて並び替えられ、次いでランク番号が割り当てられる。上記各項目には、例えばアドレス順序の反転及び頁間の繋がりを伴って限られた頁長への適合等の標準の及び一様なアドレス変換を施すこともできるが、このような処理に関しては説明の簡略化のためこれ以上説明しない。ブロック106 においては、当該テキスト源に関連するデータは、例えば以前に吟味されたテキスト源のような他のテキスト源に関連するデータにリンクされる。このリンクは例えば連結により行われる。先ず、如何なる項目に関しても、当該システムは、該項目の一連の繋がりにおける最初の発生は何処であったかについて検査する。かくして、新たなテキスト源に関連するデータは、当該項目を特徴とするテキスト源の系列における次のテキスト源の識別情報を得ることになる。更に、上記の新たなテキスト源に関連するデータにおける各項目は、その新たな項目の発生を指すオフセットを得ることになる。各項目に関するテキスト源識別情報とオフセット値とのデータ組は、ブロック108 において例えば頁等の対応する記憶位置に記憶される。その後、当該システムは次に続くテキスト源からの入力のためにブロック102 に戻るか、又は終了する。記憶されたテキスト源を削除するためには、当該処理手順は削除するべき各項目に関して当該項目の先行した発生をサーチしなければならないという点でより複雑なものとなる。このことは、しばしば特定の項目の発生の一連の繋がりの最初から開始し、削除すべきデータの順序位置のところをブリッジする必要を生じる。そのようにすれば、当該記憶位置は他の目的に再び使用することができる。勿論、特定のテキスト源のみを無視することのみが必要な場合は、当該テキスト源を無効にするようにすればよい。
【００３４】
本発明をより特定的に構成した場合の全テキスト文書検索システムにおける文書派生的項目を、語の発生頻度のランクと、その公称重みとの間のジップの関係を用いて、検索する構成を図２に示す。この骨組みのシステムにおいては、各々が多数の派生的項目又は要素からなる３つの文書（20、22、24で示す) のみが記憶されている。この場合、各派生的項目は、名詞、副詞、数値、又は数学的表現等の表現の単一の語彙的語に関するものであってもよい。他の例として、或る派生的項目は、動詞が書かれる種々の態様又はそれらのスペルミスを考慮にいれたもの等の、複数の関連する語彙的語に関するものであってもよい。図示したように、文書20は多数の異なる語を有し、文書24はそれより少ない数の語彙的語を有し、文書22は更に少ない数の語を有している。記憶手段は頁単位で空間を割り当てるモジュール形式のものであってもよいが図示はされていない。各派生的項目は、文書識別情報とオフセット値とからなり、これらは一緒になって同一の語彙的語に関連する次の派生的項目を示す。図示したように、派生的項目26、32、36は、28／34及び30／38と同様にリンクされている。各派生的項目は、当該文書内で語彙的語の発生頻度の減少する順となっている。従って、文書20においては、派生的項目26に関連する語彙的語は、派生的項目28に関連するものより頻繁に発生し、派生的項目30に関連するものはそれより頻度が少ない。全ての語彙的語が全ての文書中で発生するとは限らないので、発生のランク付けはこれら文書中では一様ではない。図示の例では、各派生的項目は３個のバイトを有し、その中の２個は派生的項目の一連の繋がりにおける次の文書を示すためのもので、他の１個はこの次の文書におけるオフセットを示すためのものである。このことは、当該構成を、この文書内の同一の語彙的語に関連する派生的項目について、256 個の語彙的語に制限する。語彙的語の総数は、極めて大きなものとすることができる。特定の文書を、より多くの語彙的語に関してサーチする必要がある場合には、次の２つの解決法がある。
（ａ）オフセットを増加させる。
（ｂ）文書を、各々が擬似文書を表すような部分に分割する。
【００３５】
検索の構成は次のようになっている。即ち、先ず語彙的語が入力部40に供給される。この入力部は、勿論、例えばコードの記憶手段を持つレジスタであり得る。次に、装置42において語ベーステーブル（派生的項目ベーステーブル）44における当該語彙的語のアドレスを見つけるために例えばツリーサーチが実行される。このようなサーチ自身は標準的技術であると考えられる。上記語ベーステーブル44は信号線43を介してアドレスされる。該テーブル４４の各アドレスは、使用された場合、当該語彙的語と、派生的項目記憶部（即ち20、22、24）におけるのと同様なフォーマットでの該語彙的語の派生的項目とを含むことができる。尚、検索システムのみが語の同一性を逆追跡する何らかの手段を有するか、又はその代わりとして、結果として文書全体がアクセスされるので語の同一性自体が有用ではない場合は、語の記憶はしばしば必要ではない。上記テーブル４４から派生的項目が読み出されると、該派生的項目における文書識別情報ｄは、信号線46を介して文書ベースアドレステーブル48と正規化テーブル49とをアドレスする。この場合、文書ベースアドレステーブル48は文書ベースアドレスを出力し、該アドレスは加算手段52において信号線50上のオフセットoff（前記の読み出された派生的項目におけるオフセット値）と加算される。この和は、関連する派生的項目の一連の繋がりにおける最初の派生的項目のアドレスを可能にする（この場合は、例えば30）。図示の例においては、他の何れの派生的項目も関連する派生的項目の繋がりにおける最初のものではない。当該派生的項目の信号線54への読出は、文書ベースアドレステーブル48の再度のアドレス指定と、加算手段52の左側の入力端子への新たなオフセット値の直接の供給を可能にする。図示しない手段により同期されて実行される上記のような動作のサイクルにおける各サイクルにより、当該派生的項目の一連の繋がりにおける次の派生的項目がアドレスされる。最後のサイクルは、終端を示すようなダミー派生的項目をアドレスするであろう。上記文書ベースアドレステーブル48のアドレス指定に同期して、正規化テーブル49からは正規化係数ｎが出力される。更に、重み決定ブロック56にオフセット値offが（語ベーステーブル44から、又は20、22、24のような派生的項目の系列の記憶部の何れかから）供給されると、当該ブロックは、正規化テーブル49に各テキスト源ｄとの所定の関係に従って永久的に記憶されている正規化係数ｎを入力する。該ブロック56は、
【数６】
0003767909.tif 000007
なる式に基づいて出力端子58に出力すべき重みｗを計算する。この出力ｗは、文書識別情報の出力ｄと一緒になされる。重みｗに関する上記式は前述した原理に基づくものである。文書識別情報ｄを伴う当該重みｗは検索部で使用されるが、この使用は従来の方法で行われる。この実施例が記憶部の構成に関する限りは（特にブロック20、22、24、44、48におけるもの）、説明を簡略化するためにこれ以上は説明しない。
【図面の簡単な説明】
【図１】  図１は、本発明に基づく文書の記憶処理の一例を示すフローチャート、
【図２】  図２は、本発明を適用した検索システムの一例のブロック図である。
【符号の説明】
20、22、24…文書、
26、28、30、32、34、36、38…派生的項目、
40…入力部、
44…語ベーステーブル（派生的項目ベーステーブル）、
48…文書ベースアドレステーブル、
49…正規化テーブル、
52…加算手段、
56…重み決定ブロック。
【図１】
0003767909.tif 000008
【図２】
0003767909.tif 000009