JP2005004560A - インバーテッドファイル作成方法 - Google Patents
インバーテッドファイル作成方法 Download PDFInfo
- Publication number
- JP2005004560A JP2005004560A JP2003168554A JP2003168554A JP2005004560A JP 2005004560 A JP2005004560 A JP 2005004560A JP 2003168554 A JP2003168554 A JP 2003168554A JP 2003168554 A JP2003168554 A JP 2003168554A JP 2005004560 A JP2005004560 A JP 2005004560A
- Authority
- JP
- Japan
- Prior art keywords
- inverted file
- inverted
- registered
- position information
- character string
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Images
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
【課題】検索速度を余り劣化させずに、インデックスのメモリ使用量を削減することができるインバーテッドファイルを提供すること。
【解決手段】このため、本発明は、インデックスとなる文字列とその位置情報を登録するインバーテッドファイル作成方法において、インバーテッドファイルに登録された位置情報数を示す登録数が記入されたインバーテッドファイルリスト９と、インバーテッドファイルリスト９をポイントする文字列に対応した区分を有するテーブル８を設け、１種または複数種の文字列をある１つのインバーテッドファイルに登録し、その位置情報を、以前に登録された他の位置情報との差分にもとづき符号化して格納する。
【選択図】 図４
【解決手段】このため、本発明は、インデックスとなる文字列とその位置情報を登録するインバーテッドファイル作成方法において、インバーテッドファイルに登録された位置情報数を示す登録数が記入されたインバーテッドファイルリスト９と、インバーテッドファイルリスト９をポイントする文字列に対応した区分を有するテーブル８を設け、１種または複数種の文字列をある１つのインバーテッドファイルに登録し、その位置情報を、以前に登録された他の位置情報との差分にもとづき符号化して格納する。
【選択図】 図４
Description
【０００１】
【発明の属する技術分野】近年インターネットの普及により、ネットワーク上に存在する多量の文書情報を扱えることが可能になってきた。しかし文書情報が多くなるにつれて、どれが有用な情報か逐一判断することができなくなってきた。これに対してあるキーワードをもとに有用な情報とそうでない情報とを取捨選択する全文検索システムの重要性が増加してきた。本発明は、この全文検索システムに有用なインバーテッドファイル作成方法に関するものである。
【０００２】
【従来の技術】被検索文書中に出現する文字列に対するインデックスつまり索引は、通常高速検索を実現するためにはコンピュータのメモリ上に予め展開しておくことが必要とされる。インデックスは通常被検索文書と同等以上のデータ量となるために、インデックスに必要なメモリ量を削減することがインデックス作成における技術課題となる。
【０００３】
本発明はインデックスの１種であるインバーテッドファイル（ｉｎｖｅｒｔｅｄ ｆｉｌｅ）のメモリ使用量を削減するためのものである。
【０００４】
インバーテッドファイルには、検索対象となるキーに関する位置情報が記載されている。位置情報とは、そのキーを有する文書の番号（以下文書番号という）や、文書先頭位置からの出現位置のことを指す。文書位置情報として文書番号のみが登録されている場合もあるし、文書番号と出現位置の二つを登録する場合もある。登録されるものはシステム要件により異なる。
【０００５】
例えば、キー「雑誌」に関するインバーテッドファイルには、図１２に示す如く、キーと文書番号の組が記載されている場合を説明する。
【０００６】
「雑誌」というキーワードを有する文書を検出したい場合には、ユーザはこのインバーテッドファイルにアクセスして、図１２に示す文書番号１、２、３、２５、７８・・・１９２３を抽出する。
【０００７】
このインバーテッドファイルのメモリ使用量を圧縮するために下記のことが提案されている（例えば非特許文献１参照）。
【０００８】
ａ．キーを有する文書の文書番号つまり位置情報を昇順に並べる。
ｂ．この位置情報間の差分を取る。
ｃ．差分値に対し小さい正整数ほど少ない符号語に割り当てられる符号を適用する。
【０００９】
前記ｃの符号としては、図１３に示す如きγ符号がよく知られている。γ符号は、整数ｘを表すのに、ｘを２進数で表したときの桁数すなわちビット数から１を引いた数だけ０を続けた後にｘの２進数表示を続けたものである。すなわち０を数によりｘの２進桁数を表し、ｘの２進数表示（必ず１から始まる）を続けたものになる。
【００１０】
いま、図１４に示す如く、キーを「雑誌」としたとき、イに示す如く、文書番号１、２、３、２５・・・１９２３の１２個の文書にこのキーが存在するとき、上記の圧縮手法について説明する。
【００１１】
まずキー「雑誌」を有する文書の文書番号を、図１４のイに示す如く、１、２・・・１９２３と昇順に並べる。
【００１２】
次にこの昇順に並べた文書番号間の差分を求め、図１４のロに示す如く、１、１、１、２２・・・３１７を得る。
【００１３】
この図１４のロで得られた差分値をγ符号化すると、図１４のハに示すビット長のγ符号が得られるので、その合計は１３６ビット長となる。これを文書番号に対して３２ビットの固定長を適用した場合は３２×１２＝３８４ビット長のものとなるので、上記の如く、位置情報の差分を求めてγ符号化することにより３８４ビットから１３６ビットに圧縮されることがわかる。
【００１４】
【非特許文献１】
Ｉａｎ Ｈ．Ｗｉｔｔｅｎ，Ａｌｉｓｔａｉｒ Ｍｏｆｆａｔ，Ｔｉｍｏｔｈｙ Ｃ．Ｂｅｌｌ著
「Ｍａｎａｇｉｎｇ Ｇｉｇａｂｙｔｅｓ：Ｃｏｍｐｒｅｓｓｉｎｇ ａｎｄｉｎｄｅｘｉｎｇ ｄｏｃｕｍｅｎｔｓ ａｎｄ ｉｍａｇｅｓ」Ｖａｎ Ｎｏｓｔｒａｎｄ Ｒｅｉｎｈｏｌｄ（米国）出版、１９９４年，ｐ８２〜９０ ３．３「Ｉｎｖｅｒｔｅｄ ｆｉｌｅ ｃｏｍｐｒｅｓｓｉｏｎ」
【００１５】
【発明が解決しようとする課題】ところでインバーテッドファイルにおいて、出現頻度の少ない文字列が多数存在する場合は、その文字列毎にインバーテッドファイルを作成すると、前記の如く、差分を取ったとしても多くのビットを必要とする。
【００１６】
インデックスを作成するとき、日本語の文書を一文字ずらして連続したＮ文字列で区切ってキーを抽出するＮ−ｇｒａｍ手法が行われる。例えば、図１５図に示す如く、「日本の雑誌が・・・」という文書を連続した２文字列で区切って文字数２のキーを抽出する２−ｇｒａｍ手法の場合は、「日本」から始まり、以下１文字ずらして「本の」、「の雑」、「雑誌」、「読が」というキーが抽出され、これらのキーの位置は図１５に示す通り付加される。
【００１７】
日本語では、例えば「雑誌が」、「雑誌を」、「雑誌の」の如く、語尾が多数変動するので、日本語の文書に対して文字数２文字の文字列のインバーテッドファイルを作成する場合などは、インバーテッドファイル数が多くなる。図１６に、前記１２等で説明したキー「雑誌」以降の語尾が上記３種類に変化した場合について説明する。
【００１８】
いま、「誌が」が文書番号１、２５、３９５、１３８４に存在し、「誌を」が文書番号２、７８、４５８、１５８６に存在し、「誌の」が文書番号３、１００、１２０５、１９２３に存在した場合、差分値、γ符号のビット長は「誌が」の場合「１、１１、１９、２１」となってその合計は５２ビット、「誌を」の場合「３、１５、１９、２３」となってその合計は６０ビット、「誌の」の場合「３、１５、２３、１９」となってその合計は６０ビットとなり、これらの総計は１７２ビットとなる。
【００１９】
ところで、キー「雑誌」と、「誌が」、「誌を」、「誌の」は同じ文書番号の組が分かれて出たにもかかわらず、「雑誌」の場合が前記の如く、１３６ビットであるのに対し、１７２ビットと増加している。このように頻度が少ない場合は、その差分値も大きくなるため、γ符号に使用するビット数が多くなる。
【００２０】
またインバーテッドファイル毎に、インバーテッドファイルをどこの物理アドレスに記録するか、インバーテッドファイル中の登録数、などの管理情報が必要となるため、インバーテッドファイルの数が多くなると、その分メモリ使用量が多くなる。
【００２１】
したがって本発明の目的は、このような問題点を改善したインバーテッドファイル作成方法を提供することである。
【００２２】
【課題を解決するための手段】前記目的を達成するため、本発明では、例えば図１に示す如く、１つのインバーテッドファイルに複数の文字列を対応付けする。あるいは図２に示す如く、差分値を更に小さい値に変換する。
【００２３】
図１（Ａ）に示す如く、「雑誌」のように出現頻度の大きいものについては、１グループ１キーでインバーテッドファイル１を作成するが、図１（Ｂ）に示す如く、「誌が」、「誌を」、「誌の」の如く、出現頻度の小さいものはこれらをまとめる。例えば１グループ３キーでインバーテッドファイル２を作成する。
【００２４】
このように複数の文字列（キー）を１つのインバーテッドファイルに対応付けること、つまりまとめることにより、位置情報の差分値が小さくなるため、符号長が短くできること、後述するインバーテッドファイルの管理情報を少なくできること等の利点がある。
【００２５】
ちなみに、例えばこのインバーテッドファイルを使用して「誌の」をキーとして検索を行う場合は、位置情報をもとに文字列検索を行ってその部分が本当に「誌の」なのかを検討する必要がある。なぜならば「誌を」「誌が」である可能性があるためである。このためこの文字列検索分だけ処理速度が遅くなる。このため、複数文字列を対応付ける方法としては、それぞれのインバーテッドファイルへの登録数が極力等しくなるようにする。これはインバーテッドファイルの登録数が不均一になり、特定のキーの検索にかかる時間が極端に遅くなるのを防ぐためである。さらにメモリ使用量を少なくすることを目的とする場合、差分値を更に小さい値に変換するために差分値を規定数で割った余りを位置情報として登録する。
【００２６】
図２はキー「誌が」に対する例であり、規定数を５１２とした場合を示す。キー「誌が」の文書番号が１、２５、３９５、１３８４の場合、その差分値は１、２４、３７０、９８９となり、規定数が５１２のため、差分値の５１２の剰余は１、２４、３７０、４７７となり、差分値９８９の代わりにビット数の少ない４７７が登録される。
【００２７】
検索時には文書番号１、２５、３９５、１３８４以外にも８７２に対してもキー「誌が」が存在するかどうか文字列検索を行うことになる。これは、差分値上は１、２４、３７０、４７７となっているので、文書番号に直された３９５の次の文書番号８７２（＝３９５（前回の番号）＋４７７）にキーが存在するかどうかを文字列検索によって確かめる処理が必要になる。しかし、存在しないので次は文書番号１３８４（８７２＋５１２）にキーが存在するかどうかを文字列検索によって確かめる。これで存在することがわかったので検索終了ということになるためである。このように文字列検索処理が多くなるが、より少ないビット数で位置情報を表すことができる。
【００２８】
本発明の前記目的は、下記（１）〜（５）により達成することができる。
【００２９】
（１）インデックスとなる文字列とその位置情報を登録するインバーテッドファイル作成方法において、インバーテッドファイルに登録された位置情報数を示す登録数が記入されたインバーテッドファイルリストと、インバーテッドファイルリストをポイントする文字列に対応した区分を有するテーブルを設け、１種または複数種の文字列をある１つのインバーテッドファイルに登録し、その位置情報を、以前に登録された他の位置情報との差分にもとづき符号化して格納することを特徴とするインバーテッドファイル作成方法。
【００３０】
（２）前記（１）においてインデックスを作成する過程で出現した新しい文字列をインバーテッドファイルに登録するとき、登録数が最も少ないインバーテッドファイルに対応付けることを特徴とするインバーテッドファイル作成方法。
【００３１】
（３）前記（１）においてインデックスを作成する過程で出現した新しい文字列をインバーテッドファイル登録するとき、予め登録するインバーテッドファイルが１つあるいは複数決定されており、以後新しい文字列が出現した場合も、そのインバーテッドファイルの登録数が一定数を超えない限りはそのグループに登録することを特徴とするインバーテッドファイル作成方法。
【００３２】
（４）前記（１）において、位置情報を以前に登録された他の位置情報との差分にもとづき符号化するとき、そのインバーテッドファイルに前回登録された位置情報との差分にもとづき符号化を行うことを特徴とするインバーテッドファイル作成方法。
【００３３】
（５）前記（１）において、位置情報を以前に登録された他の位置情報との差分にもとづき符号化するとき、規定数を、使用する符号が、ある限定された桁数で表し得る最大値とし、位置情報との差分値をこの規定数で割った余りに対して符号化を行うことを特徴とするインバーテッドファイル作成方法。 これにより下記の効果を奏することができる。
【００３４】
（１）１つのインバーテッドファイルに対して１種あるいは複数種の文字列を対応付けることにより、文字列間の出現位置情報の差分値を小さくし、インバーテッドファイルに対する管理情報を小さくできるため、メモリの消費量を抑えることができる。
【００３５】
（２）新しい文字列を登録数が最も少ないインバーテッドファイルに対応付けるので、極端に登録数が多いインバーテッドファイルを作らないことで検索時間が極端に遅い検索キーを作成しないようにしつつ、インバーテッドファイル管理情報を少なくし、更にインバーテッドファイル内の差分値を小さくすることで小さいビット数でインバーテッドファイルを構成、管理することができる。
【００３６】
（３）対応付けるインバーテッドファイルを予め決定しておき、そのインバーテッドファイルの登録数が規定数を超えるまでは、そのインバーテッドファイルに新規に出現した文字列を対応付けするので、新規な文字列が出現する度に登録数が最小のものを検出する必要がないので、処理を簡略化することができる。
【００３７】
（４）インバーテッドファイルに、前回登録された位置情報との差分値に対して符号化するので、差分値を取って小さな値は少ないビット数で、大きな値は多いビット数で表現する符号を使用して、インバーテッドファイルのメモリ使用量を削減することができる。
【００３８】
（５）差分値に対し規定数で割ってその余りを符号化したものを登録するので少ないビット数でインバーテッドファイルを表現できる。また規定数を、使用する符号がある限定された桁数で表し得る最大値に１加算したものを使用することにより、符号長を最大限有効利用できる。例えば図１３に示す如く、符号長１１ビットで６３まで表すことができるが、この場合規定値を６４にしてγ符号を使用すると１１ビットを最大限有効利用することができる。
【００３９】
【発明の実施の形態】本発明の一実施の形態を図３、図４、図５、図６、図７にもとづき説明する。図３は本発明の一実施の形態説明図、図４はインデックスの要部説明図、図５は動作説明図（その１）、図６は動作説明図（その２）、図７は動作説明図（その３）である。
【００４０】
図中、１はパソコン本体（以下ＰＣ本体という）、２は表示装置、３はキーボード、４は文書検索手段、５は文書データ、６はインデックス、７はインバーテッドファイル管理テーブル（以下管理テーブルという）、８はハッシュテーブル、９はインバーテッドファイルリスト（以下リストという）、１０はメモリ領域、１１は最大値保持部、１２はファイル数保持部である。
【００４１】
パソコン本体１は、図３に示すパソコンを動作するプロセッサや主記憶装置、磁気ディスク装置などが設けられているものであり、文書検索手段４、文書データ５等が用意されている。
【００４２】
表示装置２は、検索要求の入力を求めたり、検索結果を表示するものであって、ＣＲＴや液晶などで構成されている。
【００４３】
キーボード３はパソコンを操作するために必要な入力を行う入力操作キーが設けられており、検索キー入力端末として機能するものである。
【００４４】
文書検索手段４はインバーテッドファイルを作成したり、インバーテッドファイルを使用して検索処理を行うものであり、後述するインデックス６を有する。インデックス６には、例えば図２に示す如き、２文字列に対する複数のインバーテッドファイルを備える。また検索時には、インデックス６から検索キーに該当するインバーテッドファイルを抽出して、インバーテッドファイルに記載されている文書番号をユーザに返す。作成モードのときは、インデックスを作成し、検索モードのときはインデックスを使用して検索を行う。
【００４５】
文書データ５は、検索されるべき文書であって、この例では文書番号と題名により構成されている。文書の題名を検索対象とし、検索キーを題名に含む文書を検索により全て抽出する。
【００４６】
インデックス６は、前記検索時に使用されるインバーテッドファイルの外に、図４に示す如き、インバーテッドファイル管理テーブル（以下管理テーブルという）７を有する。
【００４７】
管理テーブル７は、ハッシュテーブル８とインバーテッドファイルリスト９、最大数保持部１１、ファイル数保持部１２を具備している。
【００４８】
ハッシュテーブル８は各文字列のハッシュ値に対応するインバーテッドファイルリスト９へのポインタが格納されている。ハッシュ値は文字列の文字コードを数値とみなし、ハッシュ関数にかけて得られた値、つまりハッシュ値を示す。「誌が」の場合、「誌」＋「を」を例えばＪＩＳの２進値で表された文字コードを数値化して、この数値を規定値で割算した余りをハッシュ値とし、このハッシュ値が取り得る数の区分を有するハッシュテーブル８を設ける。ハッシュテーブル８の区分０、１、・・・ｎがハッシュ値に対応している。
【００４９】
インバーテッドファイルリスト９は、登録数と最終登録数値と最後尾アドレスの項を有する。
登録数は、インバーテッドファイルに登録された文書番号数を示す。
【００５０】
最終登録数値は、そのインバーテッドファイルに最後に登録された文書番号の数値が記載されている。インバーテッドファイルに登録されるのは、前述の如く符号化された値であり、最初の値から順次復号しないと正確な数値が得られないので、インバーテッドファイルに新しく文書番号を登録するとき、それまでの最終登録数値をこれにより得ることにより登録時間が短縮できることになる。
【００５１】
最後尾アドレスは、メモリ領域のインバーテッドファイル記憶領域１０に登録されているインバーテッドファイルの最後尾アドレスを示すものであって、インバーテッドファイルに新しく文書データを追記するとき、この最後尾アドレスより記入することができるものである。
【００５２】
インバーテッドファイル記憶領域１０は、メモリ領域においてインバーテッドファイルが記憶されている領域を示す。
【００５３】
最大数保持部１１は、このシステムで作成可能なインバーテッドファイルの最大数Ｍａｘが記入されている区分である。図４に示す例では、インバーテッドファイルリスト９のリスト数Ｎが最大数Ｍａｘに相当する。
【００５４】
ファイル数保持部１２は、現在作成されているインバーテッドファイルの数が記入されている区分である。
【００５５】
次に図５、図６、図７を使用して、本発明の特徴的な文書検索手段５の機能であるインデックス作成処理について説明する。図５はインデックス作成処理の全体の動作説明図を示し、図６は図５における既存インバーテッドファイルへの対応付けモジュールの詳細説明図、図７は図５における文書番号登録モジュールの詳細説明図である。
【００５６】
インデックス作成処理を図５〜図７の動作説明図にもとづき説明する。この説明は２文字の文字列作成の例について行うが、本発明の文字列はこれに限定されるものではない。このインデックス作成処理は文書番号０から昇順で行われる。
【００５７】
Ｓ１．文書検索手段４は、文書中の題名から、２文字列を取得する。
Ｓ２．その文字列のハッシュ値を取得する。
【００５８】
Ｓ３．文書検索手段４は、このハッシュ値が示すハッシュテーブル８の区分の中の数値すなわちインバーテッドファイルＩＤを取得する。このハッシュテーブル８は、初期値が−１に初期化されているので、この数値が−１か否かを判断する。そしてこの数値が−１の場合は未登録、つまりその文字列がどんなインバーテッドファイルにも対応付けられていないことが認識され、ステップＳ４に進む。数値が−１でない場合は、対応済みであるため、後述する文書番号登録モジュールＳ１０に進む。
【００５９】
Ｓ４．前記Ｓ３において、数値が−１の場合は、ファイル数保持部１２の現在のインバーテッドファイルのファイル数と最大数保持部１１に記入された作成可能なインバーテッドファイルの最大数Ｍａｘ（この例ではＮ）を比較してインバーテッドファイルが新規登録可能かどうか判断する。可能な場合は後述するＳ６に進みインバーテッドファイルを新規作成し、不可能な場合は、登録数が最も少ないインバーテッドファイルに対応付けるためにＳ５に進む。これによりインバーテッドファイルの各登録数を極力小さくする。
【００６０】
Ｓ５．不可能な場合、後述する既存インバーテッドファイルへの対応付けモジュールを実行する。
【００６１】
Ｓ６．可能な場合、インバーテッドファイルを新規作成する。例えば空いているもっとも小さいリスト番号、例えばリスト番号１に作成する。
【００６２】
Ｓ７．前記Ｓ６で作成したインバーテッドファイルのリスト番号１を、前記Ｓ２で算出したハッシュ値が示す、ハッシュテーブル８の区分（この例ではｎ−１）に格納する。
【００６３】
Ｓ８．それから、このインバーテッドファイルのリスト番号１の区分を初期化する。そして登録数を０にし、最終登録数値すなわち最終文字列文書番号を０にする。また最後尾アドレスには未使用領域１０の先頭アドレスを入力する。なお初期化はシステムの立上りのとき行うこともできる。
【００６４】
Ｓ９．ファイル数保持部１２に、記入されているインバーテッドファイル数に＋１した、新インバーテッドファイル数を記入する。
【００６５】
Ｓ１０．次に後述する文書番号登録モジュールつまり「インバーテッドファイル登録モジュール」を実行する。
【００６６】
Ｓ１１．全文書の全文字列を登録したらインデックス作成処理を終了する。
【００６７】
次に図６により、前記Ｓ４において、インバーテッドファイルが新規登録不可能な場合について説明する。
【００６８】
Ｓ１０１．前記Ｓ４において、文書検索手段４が、作成可能なインバーテッドファイルの最大数を超えており新規作成が不可能と判断したとき、インバーテッドファイルリスト９の登録数の領域を検索して、登録数が最も少ないインバーテッドファイルのリスト番号（図４の例では２）を取得する。
【００６９】
Ｓ１０２．前記Ｓ１０１で取得したインバーテッドファイルリスト９のリスト番号２を、前記Ｓ２で算出したハッシュ値（例えば０）が示すハッシュテーブル８に格納する。
【００７０】
これによりハッシュ値２とハッシュ値０の文字列の、登録数、最終登録数値、最後尾アドレス等の管理データがインバーテッドファイルリスト９の同じリスト番号の区分に記入されることになる。勿論検索も前記図１（Ｂ）に示す如く、グループ化されて行われることになる。
【００７１】
図７により、前記Ｓ３、Ｓ５における既存インバーテッドファイルへの対応づけ、Ｓ６〜Ｓ９におけるインバーテッドファイルの新規作成による登録処理つまり文書番号登録モジュールについて説明する。
【００７２】
Ｓ２０１．前段の処理で特定されたインバーテッドファイルに、現在処理中の文字列の文書番号を登録する。まずインバーテッドファイルリスト９中の最終登録数値をもとにして新しく登録する文書の文書番号との差分値を求め、これを符号化する。
【００７３】
Ｓ２０２．次にインバーテッドファイルリスト９中の最終登録数値を、新しく登録する現在の文字列の文書番号に変更する。
【００７４】
Ｓ２０３．インバーテッドファイル記憶領域１０の最後尾アドレスに前記符号化したものを挿入する。
【００７５】
Ｓ２０４．この挿入により増加した分を最後尾アドレスとしてインバーテッドファイルリスト９に登録する。なおこのとき、インバーテッドファイルリスト９の登録数を＋１する。
【００７６】
なお、本発明は位置情報の差分値を小さくすることで圧縮符号による圧縮時に必要なビット数を削減することを目的としているため、上記説明で使用する圧縮符号はγ符号のみならず、図８に示す正整数の符号化説明図に示すα符号、δ符号、８ｂｉｔ ｂｌｏｃｋ符号などでもよい。これらはいずれも公知のものであり、ＣＱ出版社、植原智彦著、「文書データ圧縮アルゴリズム入門」に記載されている。
【００７７】
α符号は整数ｘを表すのにｘ−１個の０を続けた後に１を続けたものである。
【００７８】
δ符号は最初の桁数表示のかわりに符号γを利用したもの、つまりｘを２進数で表したときの桁数（ｂｉｔ数）を符号γで表現したあとに、ｘの２進数表示の先頭の１を除いたものである。
【００７９】
８ｂｉｔ ｂｌｏｃｋ符号は、８ｂｉｔのうちｔｏｐ１ｂｉｔを継続ｆｌａｇとし、そのフラグが存在したら次の８ｂｉｔも数が存在するとするものである。
【００８０】
本発明の第２の実施の形態を図９、図１０、図１１および図５を参照して説明する。図９は第２の実施の形態説明図、図１０は第２の実施の形態における動作説明図（その１）、図１１は第２の実施の形態における動作説明図（その２）である。
【００８１】
第１の実施の形態では、新しい文字列に対応してインバーテッドファイルを作成するとき、すでにインバーテッドファイルの登録数が許容登録数を超えていると、インバーテッドファイルの登録数を全部検索して最小値のものを求めることが必要のため、その検索に長い時間必要とした点があり、これを改善するため、第２の実施の形態では、このような場合あらかじめ登録数の少ないものの、全インバーテッドファイルの、例えば１／４を複数の文字列に対応付けするグループ化候補としてあらかじめ予定しておくものである。
【００８２】
第２の実施の形態では、パソコン内にある文書検索手段によるインデックス作成の実施例を示す。この方法は、文書（文章の外に題名等書誌的事項を含む）の文章中の文字列を検索キーとして、検索キーが出現する位置を全て抽出する。またこの方法は、文書データとして一つの文書を有する。
【００８３】
第２の実施の形態を実現する装置は、図９に示す如く構成され、他図と同符号は同一部を示し、３は検索キー入力端末として機能するキーボード、１４は文書検索手段、１５は文書データである。
【００８４】
キーボード３は、ユーザから入力された検索キーを文書検索手段１４に入力するものである。
【００８５】
文書検索手段１４は、２文字列に対するインバーテッドファイルからなるインデックス６を有しており、検索時には、検索キーのインバーテッドファイルを抽出して、インバーテッドファイルに記載されている、検索キーのその文章における出現位置（例えば先頭からの語数）を返す。
【００８６】
文書データ１５は、検索対象の文書で、１つのみであり、文章を有する。
【００８７】
なお、インデックス６の内部は、前記図３と同じである。
【００８８】
第２の実施の形態におけるインデックス作成の処理手順は、図５におけるＳ５の「既存インバーテッドファイルへの対応付けモジュール」と、Ｓ１０の「文書番号登録モジュール」以外は第一の実施の形態とまったく同一である。よってこの２つのモジュールのみを以下に説明する。
【００８９】
なお、第２の実施の形態では、検索出力は文書番号ではなく検索キーの文字列出現位置であるので、第２の実施の形態では、前記Ｓ１０の記載を「文字列出現位置登録モジュール」と読み替えるものとする。
【００９０】
第２の実施の形態における「既存インバーテッドファイルへの対応付けモジュール」では、新しく出現した文字列に対応付けるインバーテッドファイルを予め複数選択しておく。そして今回新しく出現した文字列をこの複数選択したインバーテッドファイルの内の１つに対応付け、前記選択された全てのインバーテッドファイルが次回以降新しく出現した文字列に順次対応付けされるように処理される。
【００９１】
図１０によりその動作を説明する。
【００９２】
Ｓ３０１．文書検索手段１４は、対応付け用インバーテッドファイルが未決定な場合、あるいはこれまでに選択された対応付け用インバーテッドファイルが全て新しく出現した文字列に対応付けられてもう存在しない場合はステップＳ３０２に進み、そうでない場合はステップＳ３０３に進む。
【００９３】
Ｓ３０２．文書検索手段１４は、全てのインバーテッドファイルから対応付け用インバーテッドファイルとして複数選択する。選択基準は、例えば登録数が少ない方から１／４とする。そして選択したインバーテッドファイルの中で新しく出現した文字列に対応付ける順番を予め決定しておく。決定方法は、例えば登録数の少ないインバーテッドファイルから対応付けられるような順番による。
【００９４】
Ｓ３０３．複数存在する対応付け用インバーテッドファイルの中から、現在の文字列に対応付けるインバーテッドファイルを選択する。次に選択したインバーテッドファイルのリスト番号を取得し、そのリスト番号を前記図５のＳ２で算出したハッシュ値が示すハッシュテーブル８に格納する。
【００９５】
Ｓ３０４．文書検索手段１４は前記Ｓ３０３で選択したインバーテッドファイルは、次回以降に新規出現した文字列への対応付けの対象外とする。但し次回以降でＳ３０２に通った場合は再度選択される場合もある。
【００９６】
図５におけるＳ１０の「文字列出現位置登録モジュール」では、前段の処理で特定されたインバーテッドファイルに、現在処理中の文字列の出現位置を登録する。はじめに、その出現位置を、最終登録数値をもとにして符号化処理を行い、次に最終登録数値を現在の文字列の出現位置に変更する。それから最後尾アドレスに前記符号化したものを挿入し、この挿入により増加した分を最後尾アドレスに登録する。
【００９７】
この動作を図１１により説明する。
【００９８】
Ｓ４０１．文書検索手段１４は、前段の処理で特定されたインバーテッドファイルに、現在処理中の文字列の出現位置を登録するため、以下の式から算出した整数値を符号化処理する。符号は例えばγ符号を使用する。なおＭｏｄ（Ａ、Ｂ）とはＡをＢで割った余りである。
【００９９】
この式に記載されている規定値は、使用する符号がある限定された桁数で表しうる最大値と同じものとする。そのようにしないと、例えば規定値が５１１で（Ｎｏｗ Ｏｆｆｓｅｔ − Ｂｅｆｏｒｅ Ｏｆｆｓｅｔ） が５１１であった場合、Ｉｎｔは１となり、符号結果をｂｉｔ表示すると“１”となり、メモリ使用量は１ｂｉｔと小さくなる。しかし検索時には、符号結果“１”を数式をもとに差分値に逆変換すると、０になる。よって、差分値０に該当する位置にはキーが存在しないのだが実際に文字列検索することになる。次に差分値５１１（＝０＋５１１×１）に該当する位置を実際に文字列検索して、キーが存在することが判明し、ヒットしたことになる。このように規定値以上の差分値は文字列検索を何度も行うことになる。このように、規定値が小さいと文字列検索の回数が増えることになる。しかし逆に規定値の数が大きいとメモリ使用量が多くなる傾向にある。このようなトレードオフの状況下で規定値を決定する必要がある。このときに、ビットを最大限有効利用するために、前述したように使用する符号がある限定された桁数で表しうる最大値と同じものとする。
【０１００】
例えば規定値が３００ならば、０〜５１０までの差分値は、使用ビット数は最大１７ｂｉｔと変化が無いにもかかわらず、３０１〜５１０は文字列検索回数が増えることになる。しかし、規定値が５１１ならば０〜５１０までの差分値は使用ビット数は最大１７ｂｉｔと維持され文字列検索回数も増えることは無い。このようにして検索時の文字列検索回数を極力減らしつつ、ビットを最大限有効利用する。
【０１０１】
Ｓ４０２．次に文書検索手段１４は、インバーテッドファイルリスト９の最終登録数値を今の文字列の出現位置に変更する。
【０１０２】
Ｓ４０３．それから、インバーテッドファイル記憶領域１０の最後尾アドレスに、前記符号化したものを挿入する。
【０１０３】
Ｓ４０４．この挿入により増加した分を、インバーテッドファイルリスト９の最後尾アドレスに加えて、これを変更する。
【０１０４】
なお、本発明は位置情報の差分値を小さくすることで圧縮符号による圧縮時に必要なビット数を削減することを目的としているため、ここで使用される符号はγ符号のみならずα符号、δ符号であってもよい。
【０１０５】
以上説明のように、本発明によれば、出現文字列をグループ化し、ある定数に対する出現位置情報の剰余をインバーテッドファイルに登録することで、検索速度を余り劣化させずにインデックスのメモリ使用量を削減することができる。
【０１０６】
【発明の効果】本発明により下記の効果を奏することができる。
【０１０７】
（１）１つのインバーテッドファイルに対して１種あるいは複数種の文字列を対応付けることにより、文字列間の出現位置情報の差分値を小さくし、インバーテッドファイルに対する管理情報を小さくできるため、メモリの消費量を抑えることができる。
【０１０８】
（２）新しい文字列を登録数が最も少ないインバーテッドファイルに対応付けるので、極端に登録数が多いインバーテッドファイルを作らないことで検索時間が極端に遅い検索キーを作成しないようにしつつ、インバーテッドファイル管理情報を少なくし、更にインバーテッドファイル内の差分値を小さくすることで小さいビット数でインバーテッドファイルを構成、管理することができる。
【０１０９】
（３）対応付けるインバーテッドファイルを予め決定しておき、そのインバーテッドファイルの登録数が規定数を超えるまでは、そのインバーテッドファイルに新規に出現した文字列を対応付けするので、新規な文字列が出現する度に登録数が最小のものを検出する必要がないので、処理を簡略化することができる。
【０１１０】
（４）インバーテッドファイルに、前回登録された位置情報との差分値に対して符号化するので、差分値を取って小さな値は少ないビット数で、大きな値は多いビット数で表現する符号を使用して、インバーテッドファイルのメモリ使用量を削減することができる。
【０１１１】
（５）差分値に対し規定数で割ってその余りを符号化したものを登録するので少ないビット数でインバーテッドファイルを表現できる。また規定数を、使用する符号がある限定された桁数で表し得る最大値を使用することにより、符号長を最大限有効利用できる。例えば図１３に示す如く、符号長１１ビットで６３まで表すことができるが、この場合規定値を６４にしてγ符号を使用すると１１ビットを最大限有効利用することができる。
【図面の簡単な説明】
【図１】複数の文字列の対応付け説明図である。
【図２】差分値を小さい値に変換する説明図である。
【図３】本発明の一実施の形態説明図である。
【図４】インデックスの要部説明図である。
【図５】本発明の第一の実施の形態の動作説明図（その１）である。
【図６】本発明の第一の実施の形態の動作説明図（その２）である。
【図７】本発明の第一の実施の形態の動作説明図（その３）である。
【図８】正整数の符号化説明図である。
【図９】本発明の第２の実施の形態説明図である。
【図１０】本発明の第２の実施の形態の動作説明図（その１）である。
【図１１】本発明の第２の実施の形態の動作説明図（その２）である。
【図１２】インバーテッドファイル説明図である。
【図１３】正整数の符号化説明図である。
【図１４】圧縮例説明図である。
【図１５】２文字列抽出説明図である。
【図１６】語尾が変化したときの位置情報説明図である。
【符号の説明】
１ パソコン本体
２ 表示装置
３ キーボード
４ 文書検索手段
５ 文書データ
６ インデックス
７ インバーテッドファイル管理テーブル
８ ハッシュテーブル
９ インバーテッドファイルリスト
１０ インバーテッドファイル記憶領域
１１ 最大数保持部
１２ ファイル数保持部
【発明の属する技術分野】近年インターネットの普及により、ネットワーク上に存在する多量の文書情報を扱えることが可能になってきた。しかし文書情報が多くなるにつれて、どれが有用な情報か逐一判断することができなくなってきた。これに対してあるキーワードをもとに有用な情報とそうでない情報とを取捨選択する全文検索システムの重要性が増加してきた。本発明は、この全文検索システムに有用なインバーテッドファイル作成方法に関するものである。
【０００２】
【従来の技術】被検索文書中に出現する文字列に対するインデックスつまり索引は、通常高速検索を実現するためにはコンピュータのメモリ上に予め展開しておくことが必要とされる。インデックスは通常被検索文書と同等以上のデータ量となるために、インデックスに必要なメモリ量を削減することがインデックス作成における技術課題となる。
【０００３】
本発明はインデックスの１種であるインバーテッドファイル（ｉｎｖｅｒｔｅｄ ｆｉｌｅ）のメモリ使用量を削減するためのものである。
【０００４】
インバーテッドファイルには、検索対象となるキーに関する位置情報が記載されている。位置情報とは、そのキーを有する文書の番号（以下文書番号という）や、文書先頭位置からの出現位置のことを指す。文書位置情報として文書番号のみが登録されている場合もあるし、文書番号と出現位置の二つを登録する場合もある。登録されるものはシステム要件により異なる。
【０００５】
例えば、キー「雑誌」に関するインバーテッドファイルには、図１２に示す如く、キーと文書番号の組が記載されている場合を説明する。
【０００６】
「雑誌」というキーワードを有する文書を検出したい場合には、ユーザはこのインバーテッドファイルにアクセスして、図１２に示す文書番号１、２、３、２５、７８・・・１９２３を抽出する。
【０００７】
このインバーテッドファイルのメモリ使用量を圧縮するために下記のことが提案されている（例えば非特許文献１参照）。
【０００８】
ａ．キーを有する文書の文書番号つまり位置情報を昇順に並べる。
ｂ．この位置情報間の差分を取る。
ｃ．差分値に対し小さい正整数ほど少ない符号語に割り当てられる符号を適用する。
【０００９】
前記ｃの符号としては、図１３に示す如きγ符号がよく知られている。γ符号は、整数ｘを表すのに、ｘを２進数で表したときの桁数すなわちビット数から１を引いた数だけ０を続けた後にｘの２進数表示を続けたものである。すなわち０を数によりｘの２進桁数を表し、ｘの２進数表示（必ず１から始まる）を続けたものになる。
【００１０】
いま、図１４に示す如く、キーを「雑誌」としたとき、イに示す如く、文書番号１、２、３、２５・・・１９２３の１２個の文書にこのキーが存在するとき、上記の圧縮手法について説明する。
【００１１】
まずキー「雑誌」を有する文書の文書番号を、図１４のイに示す如く、１、２・・・１９２３と昇順に並べる。
【００１２】
次にこの昇順に並べた文書番号間の差分を求め、図１４のロに示す如く、１、１、１、２２・・・３１７を得る。
【００１３】
この図１４のロで得られた差分値をγ符号化すると、図１４のハに示すビット長のγ符号が得られるので、その合計は１３６ビット長となる。これを文書番号に対して３２ビットの固定長を適用した場合は３２×１２＝３８４ビット長のものとなるので、上記の如く、位置情報の差分を求めてγ符号化することにより３８４ビットから１３６ビットに圧縮されることがわかる。
【００１４】
【非特許文献１】
Ｉａｎ Ｈ．Ｗｉｔｔｅｎ，Ａｌｉｓｔａｉｒ Ｍｏｆｆａｔ，Ｔｉｍｏｔｈｙ Ｃ．Ｂｅｌｌ著
「Ｍａｎａｇｉｎｇ Ｇｉｇａｂｙｔｅｓ：Ｃｏｍｐｒｅｓｓｉｎｇ ａｎｄｉｎｄｅｘｉｎｇ ｄｏｃｕｍｅｎｔｓ ａｎｄ ｉｍａｇｅｓ」Ｖａｎ Ｎｏｓｔｒａｎｄ Ｒｅｉｎｈｏｌｄ（米国）出版、１９９４年，ｐ８２〜９０ ３．３「Ｉｎｖｅｒｔｅｄ ｆｉｌｅ ｃｏｍｐｒｅｓｓｉｏｎ」
【００１５】
【発明が解決しようとする課題】ところでインバーテッドファイルにおいて、出現頻度の少ない文字列が多数存在する場合は、その文字列毎にインバーテッドファイルを作成すると、前記の如く、差分を取ったとしても多くのビットを必要とする。
【００１６】
インデックスを作成するとき、日本語の文書を一文字ずらして連続したＮ文字列で区切ってキーを抽出するＮ−ｇｒａｍ手法が行われる。例えば、図１５図に示す如く、「日本の雑誌が・・・」という文書を連続した２文字列で区切って文字数２のキーを抽出する２−ｇｒａｍ手法の場合は、「日本」から始まり、以下１文字ずらして「本の」、「の雑」、「雑誌」、「読が」というキーが抽出され、これらのキーの位置は図１５に示す通り付加される。
【００１７】
日本語では、例えば「雑誌が」、「雑誌を」、「雑誌の」の如く、語尾が多数変動するので、日本語の文書に対して文字数２文字の文字列のインバーテッドファイルを作成する場合などは、インバーテッドファイル数が多くなる。図１６に、前記１２等で説明したキー「雑誌」以降の語尾が上記３種類に変化した場合について説明する。
【００１８】
いま、「誌が」が文書番号１、２５、３９５、１３８４に存在し、「誌を」が文書番号２、７８、４５８、１５８６に存在し、「誌の」が文書番号３、１００、１２０５、１９２３に存在した場合、差分値、γ符号のビット長は「誌が」の場合「１、１１、１９、２１」となってその合計は５２ビット、「誌を」の場合「３、１５、１９、２３」となってその合計は６０ビット、「誌の」の場合「３、１５、２３、１９」となってその合計は６０ビットとなり、これらの総計は１７２ビットとなる。
【００１９】
ところで、キー「雑誌」と、「誌が」、「誌を」、「誌の」は同じ文書番号の組が分かれて出たにもかかわらず、「雑誌」の場合が前記の如く、１３６ビットであるのに対し、１７２ビットと増加している。このように頻度が少ない場合は、その差分値も大きくなるため、γ符号に使用するビット数が多くなる。
【００２０】
またインバーテッドファイル毎に、インバーテッドファイルをどこの物理アドレスに記録するか、インバーテッドファイル中の登録数、などの管理情報が必要となるため、インバーテッドファイルの数が多くなると、その分メモリ使用量が多くなる。
【００２１】
したがって本発明の目的は、このような問題点を改善したインバーテッドファイル作成方法を提供することである。
【００２２】
【課題を解決するための手段】前記目的を達成するため、本発明では、例えば図１に示す如く、１つのインバーテッドファイルに複数の文字列を対応付けする。あるいは図２に示す如く、差分値を更に小さい値に変換する。
【００２３】
図１（Ａ）に示す如く、「雑誌」のように出現頻度の大きいものについては、１グループ１キーでインバーテッドファイル１を作成するが、図１（Ｂ）に示す如く、「誌が」、「誌を」、「誌の」の如く、出現頻度の小さいものはこれらをまとめる。例えば１グループ３キーでインバーテッドファイル２を作成する。
【００２４】
このように複数の文字列（キー）を１つのインバーテッドファイルに対応付けること、つまりまとめることにより、位置情報の差分値が小さくなるため、符号長が短くできること、後述するインバーテッドファイルの管理情報を少なくできること等の利点がある。
【００２５】
ちなみに、例えばこのインバーテッドファイルを使用して「誌の」をキーとして検索を行う場合は、位置情報をもとに文字列検索を行ってその部分が本当に「誌の」なのかを検討する必要がある。なぜならば「誌を」「誌が」である可能性があるためである。このためこの文字列検索分だけ処理速度が遅くなる。このため、複数文字列を対応付ける方法としては、それぞれのインバーテッドファイルへの登録数が極力等しくなるようにする。これはインバーテッドファイルの登録数が不均一になり、特定のキーの検索にかかる時間が極端に遅くなるのを防ぐためである。さらにメモリ使用量を少なくすることを目的とする場合、差分値を更に小さい値に変換するために差分値を規定数で割った余りを位置情報として登録する。
【００２６】
図２はキー「誌が」に対する例であり、規定数を５１２とした場合を示す。キー「誌が」の文書番号が１、２５、３９５、１３８４の場合、その差分値は１、２４、３７０、９８９となり、規定数が５１２のため、差分値の５１２の剰余は１、２４、３７０、４７７となり、差分値９８９の代わりにビット数の少ない４７７が登録される。
【００２７】
検索時には文書番号１、２５、３９５、１３８４以外にも８７２に対してもキー「誌が」が存在するかどうか文字列検索を行うことになる。これは、差分値上は１、２４、３７０、４７７となっているので、文書番号に直された３９５の次の文書番号８７２（＝３９５（前回の番号）＋４７７）にキーが存在するかどうかを文字列検索によって確かめる処理が必要になる。しかし、存在しないので次は文書番号１３８４（８７２＋５１２）にキーが存在するかどうかを文字列検索によって確かめる。これで存在することがわかったので検索終了ということになるためである。このように文字列検索処理が多くなるが、より少ないビット数で位置情報を表すことができる。
【００２８】
本発明の前記目的は、下記（１）〜（５）により達成することができる。
【００２９】
（１）インデックスとなる文字列とその位置情報を登録するインバーテッドファイル作成方法において、インバーテッドファイルに登録された位置情報数を示す登録数が記入されたインバーテッドファイルリストと、インバーテッドファイルリストをポイントする文字列に対応した区分を有するテーブルを設け、１種または複数種の文字列をある１つのインバーテッドファイルに登録し、その位置情報を、以前に登録された他の位置情報との差分にもとづき符号化して格納することを特徴とするインバーテッドファイル作成方法。
【００３０】
（２）前記（１）においてインデックスを作成する過程で出現した新しい文字列をインバーテッドファイルに登録するとき、登録数が最も少ないインバーテッドファイルに対応付けることを特徴とするインバーテッドファイル作成方法。
【００３１】
（３）前記（１）においてインデックスを作成する過程で出現した新しい文字列をインバーテッドファイル登録するとき、予め登録するインバーテッドファイルが１つあるいは複数決定されており、以後新しい文字列が出現した場合も、そのインバーテッドファイルの登録数が一定数を超えない限りはそのグループに登録することを特徴とするインバーテッドファイル作成方法。
【００３２】
（４）前記（１）において、位置情報を以前に登録された他の位置情報との差分にもとづき符号化するとき、そのインバーテッドファイルに前回登録された位置情報との差分にもとづき符号化を行うことを特徴とするインバーテッドファイル作成方法。
【００３３】
（５）前記（１）において、位置情報を以前に登録された他の位置情報との差分にもとづき符号化するとき、規定数を、使用する符号が、ある限定された桁数で表し得る最大値とし、位置情報との差分値をこの規定数で割った余りに対して符号化を行うことを特徴とするインバーテッドファイル作成方法。 これにより下記の効果を奏することができる。
【００３４】
（１）１つのインバーテッドファイルに対して１種あるいは複数種の文字列を対応付けることにより、文字列間の出現位置情報の差分値を小さくし、インバーテッドファイルに対する管理情報を小さくできるため、メモリの消費量を抑えることができる。
【００３５】
（２）新しい文字列を登録数が最も少ないインバーテッドファイルに対応付けるので、極端に登録数が多いインバーテッドファイルを作らないことで検索時間が極端に遅い検索キーを作成しないようにしつつ、インバーテッドファイル管理情報を少なくし、更にインバーテッドファイル内の差分値を小さくすることで小さいビット数でインバーテッドファイルを構成、管理することができる。
【００３６】
（３）対応付けるインバーテッドファイルを予め決定しておき、そのインバーテッドファイルの登録数が規定数を超えるまでは、そのインバーテッドファイルに新規に出現した文字列を対応付けするので、新規な文字列が出現する度に登録数が最小のものを検出する必要がないので、処理を簡略化することができる。
【００３７】
（４）インバーテッドファイルに、前回登録された位置情報との差分値に対して符号化するので、差分値を取って小さな値は少ないビット数で、大きな値は多いビット数で表現する符号を使用して、インバーテッドファイルのメモリ使用量を削減することができる。
【００３８】
（５）差分値に対し規定数で割ってその余りを符号化したものを登録するので少ないビット数でインバーテッドファイルを表現できる。また規定数を、使用する符号がある限定された桁数で表し得る最大値に１加算したものを使用することにより、符号長を最大限有効利用できる。例えば図１３に示す如く、符号長１１ビットで６３まで表すことができるが、この場合規定値を６４にしてγ符号を使用すると１１ビットを最大限有効利用することができる。
【００３９】
【発明の実施の形態】本発明の一実施の形態を図３、図４、図５、図６、図７にもとづき説明する。図３は本発明の一実施の形態説明図、図４はインデックスの要部説明図、図５は動作説明図（その１）、図６は動作説明図（その２）、図７は動作説明図（その３）である。
【００４０】
図中、１はパソコン本体（以下ＰＣ本体という）、２は表示装置、３はキーボード、４は文書検索手段、５は文書データ、６はインデックス、７はインバーテッドファイル管理テーブル（以下管理テーブルという）、８はハッシュテーブル、９はインバーテッドファイルリスト（以下リストという）、１０はメモリ領域、１１は最大値保持部、１２はファイル数保持部である。
【００４１】
パソコン本体１は、図３に示すパソコンを動作するプロセッサや主記憶装置、磁気ディスク装置などが設けられているものであり、文書検索手段４、文書データ５等が用意されている。
【００４２】
表示装置２は、検索要求の入力を求めたり、検索結果を表示するものであって、ＣＲＴや液晶などで構成されている。
【００４３】
キーボード３はパソコンを操作するために必要な入力を行う入力操作キーが設けられており、検索キー入力端末として機能するものである。
【００４４】
文書検索手段４はインバーテッドファイルを作成したり、インバーテッドファイルを使用して検索処理を行うものであり、後述するインデックス６を有する。インデックス６には、例えば図２に示す如き、２文字列に対する複数のインバーテッドファイルを備える。また検索時には、インデックス６から検索キーに該当するインバーテッドファイルを抽出して、インバーテッドファイルに記載されている文書番号をユーザに返す。作成モードのときは、インデックスを作成し、検索モードのときはインデックスを使用して検索を行う。
【００４５】
文書データ５は、検索されるべき文書であって、この例では文書番号と題名により構成されている。文書の題名を検索対象とし、検索キーを題名に含む文書を検索により全て抽出する。
【００４６】
インデックス６は、前記検索時に使用されるインバーテッドファイルの外に、図４に示す如き、インバーテッドファイル管理テーブル（以下管理テーブルという）７を有する。
【００４７】
管理テーブル７は、ハッシュテーブル８とインバーテッドファイルリスト９、最大数保持部１１、ファイル数保持部１２を具備している。
【００４８】
ハッシュテーブル８は各文字列のハッシュ値に対応するインバーテッドファイルリスト９へのポインタが格納されている。ハッシュ値は文字列の文字コードを数値とみなし、ハッシュ関数にかけて得られた値、つまりハッシュ値を示す。「誌が」の場合、「誌」＋「を」を例えばＪＩＳの２進値で表された文字コードを数値化して、この数値を規定値で割算した余りをハッシュ値とし、このハッシュ値が取り得る数の区分を有するハッシュテーブル８を設ける。ハッシュテーブル８の区分０、１、・・・ｎがハッシュ値に対応している。
【００４９】
インバーテッドファイルリスト９は、登録数と最終登録数値と最後尾アドレスの項を有する。
登録数は、インバーテッドファイルに登録された文書番号数を示す。
【００５０】
最終登録数値は、そのインバーテッドファイルに最後に登録された文書番号の数値が記載されている。インバーテッドファイルに登録されるのは、前述の如く符号化された値であり、最初の値から順次復号しないと正確な数値が得られないので、インバーテッドファイルに新しく文書番号を登録するとき、それまでの最終登録数値をこれにより得ることにより登録時間が短縮できることになる。
【００５１】
最後尾アドレスは、メモリ領域のインバーテッドファイル記憶領域１０に登録されているインバーテッドファイルの最後尾アドレスを示すものであって、インバーテッドファイルに新しく文書データを追記するとき、この最後尾アドレスより記入することができるものである。
【００５２】
インバーテッドファイル記憶領域１０は、メモリ領域においてインバーテッドファイルが記憶されている領域を示す。
【００５３】
最大数保持部１１は、このシステムで作成可能なインバーテッドファイルの最大数Ｍａｘが記入されている区分である。図４に示す例では、インバーテッドファイルリスト９のリスト数Ｎが最大数Ｍａｘに相当する。
【００５４】
ファイル数保持部１２は、現在作成されているインバーテッドファイルの数が記入されている区分である。
【００５５】
次に図５、図６、図７を使用して、本発明の特徴的な文書検索手段５の機能であるインデックス作成処理について説明する。図５はインデックス作成処理の全体の動作説明図を示し、図６は図５における既存インバーテッドファイルへの対応付けモジュールの詳細説明図、図７は図５における文書番号登録モジュールの詳細説明図である。
【００５６】
インデックス作成処理を図５〜図７の動作説明図にもとづき説明する。この説明は２文字の文字列作成の例について行うが、本発明の文字列はこれに限定されるものではない。このインデックス作成処理は文書番号０から昇順で行われる。
【００５７】
Ｓ１．文書検索手段４は、文書中の題名から、２文字列を取得する。
Ｓ２．その文字列のハッシュ値を取得する。
【００５８】
Ｓ３．文書検索手段４は、このハッシュ値が示すハッシュテーブル８の区分の中の数値すなわちインバーテッドファイルＩＤを取得する。このハッシュテーブル８は、初期値が−１に初期化されているので、この数値が−１か否かを判断する。そしてこの数値が−１の場合は未登録、つまりその文字列がどんなインバーテッドファイルにも対応付けられていないことが認識され、ステップＳ４に進む。数値が−１でない場合は、対応済みであるため、後述する文書番号登録モジュールＳ１０に進む。
【００５９】
Ｓ４．前記Ｓ３において、数値が−１の場合は、ファイル数保持部１２の現在のインバーテッドファイルのファイル数と最大数保持部１１に記入された作成可能なインバーテッドファイルの最大数Ｍａｘ（この例ではＮ）を比較してインバーテッドファイルが新規登録可能かどうか判断する。可能な場合は後述するＳ６に進みインバーテッドファイルを新規作成し、不可能な場合は、登録数が最も少ないインバーテッドファイルに対応付けるためにＳ５に進む。これによりインバーテッドファイルの各登録数を極力小さくする。
【００６０】
Ｓ５．不可能な場合、後述する既存インバーテッドファイルへの対応付けモジュールを実行する。
【００６１】
Ｓ６．可能な場合、インバーテッドファイルを新規作成する。例えば空いているもっとも小さいリスト番号、例えばリスト番号１に作成する。
【００６２】
Ｓ７．前記Ｓ６で作成したインバーテッドファイルのリスト番号１を、前記Ｓ２で算出したハッシュ値が示す、ハッシュテーブル８の区分（この例ではｎ−１）に格納する。
【００６３】
Ｓ８．それから、このインバーテッドファイルのリスト番号１の区分を初期化する。そして登録数を０にし、最終登録数値すなわち最終文字列文書番号を０にする。また最後尾アドレスには未使用領域１０の先頭アドレスを入力する。なお初期化はシステムの立上りのとき行うこともできる。
【００６４】
Ｓ９．ファイル数保持部１２に、記入されているインバーテッドファイル数に＋１した、新インバーテッドファイル数を記入する。
【００６５】
Ｓ１０．次に後述する文書番号登録モジュールつまり「インバーテッドファイル登録モジュール」を実行する。
【００６６】
Ｓ１１．全文書の全文字列を登録したらインデックス作成処理を終了する。
【００６７】
次に図６により、前記Ｓ４において、インバーテッドファイルが新規登録不可能な場合について説明する。
【００６８】
Ｓ１０１．前記Ｓ４において、文書検索手段４が、作成可能なインバーテッドファイルの最大数を超えており新規作成が不可能と判断したとき、インバーテッドファイルリスト９の登録数の領域を検索して、登録数が最も少ないインバーテッドファイルのリスト番号（図４の例では２）を取得する。
【００６９】
Ｓ１０２．前記Ｓ１０１で取得したインバーテッドファイルリスト９のリスト番号２を、前記Ｓ２で算出したハッシュ値（例えば０）が示すハッシュテーブル８に格納する。
【００７０】
これによりハッシュ値２とハッシュ値０の文字列の、登録数、最終登録数値、最後尾アドレス等の管理データがインバーテッドファイルリスト９の同じリスト番号の区分に記入されることになる。勿論検索も前記図１（Ｂ）に示す如く、グループ化されて行われることになる。
【００７１】
図７により、前記Ｓ３、Ｓ５における既存インバーテッドファイルへの対応づけ、Ｓ６〜Ｓ９におけるインバーテッドファイルの新規作成による登録処理つまり文書番号登録モジュールについて説明する。
【００７２】
Ｓ２０１．前段の処理で特定されたインバーテッドファイルに、現在処理中の文字列の文書番号を登録する。まずインバーテッドファイルリスト９中の最終登録数値をもとにして新しく登録する文書の文書番号との差分値を求め、これを符号化する。
【００７３】
Ｓ２０２．次にインバーテッドファイルリスト９中の最終登録数値を、新しく登録する現在の文字列の文書番号に変更する。
【００７４】
Ｓ２０３．インバーテッドファイル記憶領域１０の最後尾アドレスに前記符号化したものを挿入する。
【００７５】
Ｓ２０４．この挿入により増加した分を最後尾アドレスとしてインバーテッドファイルリスト９に登録する。なおこのとき、インバーテッドファイルリスト９の登録数を＋１する。
【００７６】
なお、本発明は位置情報の差分値を小さくすることで圧縮符号による圧縮時に必要なビット数を削減することを目的としているため、上記説明で使用する圧縮符号はγ符号のみならず、図８に示す正整数の符号化説明図に示すα符号、δ符号、８ｂｉｔ ｂｌｏｃｋ符号などでもよい。これらはいずれも公知のものであり、ＣＱ出版社、植原智彦著、「文書データ圧縮アルゴリズム入門」に記載されている。
【００７７】
α符号は整数ｘを表すのにｘ−１個の０を続けた後に１を続けたものである。
【００７８】
δ符号は最初の桁数表示のかわりに符号γを利用したもの、つまりｘを２進数で表したときの桁数（ｂｉｔ数）を符号γで表現したあとに、ｘの２進数表示の先頭の１を除いたものである。
【００７９】
８ｂｉｔ ｂｌｏｃｋ符号は、８ｂｉｔのうちｔｏｐ１ｂｉｔを継続ｆｌａｇとし、そのフラグが存在したら次の８ｂｉｔも数が存在するとするものである。
【００８０】
本発明の第２の実施の形態を図９、図１０、図１１および図５を参照して説明する。図９は第２の実施の形態説明図、図１０は第２の実施の形態における動作説明図（その１）、図１１は第２の実施の形態における動作説明図（その２）である。
【００８１】
第１の実施の形態では、新しい文字列に対応してインバーテッドファイルを作成するとき、すでにインバーテッドファイルの登録数が許容登録数を超えていると、インバーテッドファイルの登録数を全部検索して最小値のものを求めることが必要のため、その検索に長い時間必要とした点があり、これを改善するため、第２の実施の形態では、このような場合あらかじめ登録数の少ないものの、全インバーテッドファイルの、例えば１／４を複数の文字列に対応付けするグループ化候補としてあらかじめ予定しておくものである。
【００８２】
第２の実施の形態では、パソコン内にある文書検索手段によるインデックス作成の実施例を示す。この方法は、文書（文章の外に題名等書誌的事項を含む）の文章中の文字列を検索キーとして、検索キーが出現する位置を全て抽出する。またこの方法は、文書データとして一つの文書を有する。
【００８３】
第２の実施の形態を実現する装置は、図９に示す如く構成され、他図と同符号は同一部を示し、３は検索キー入力端末として機能するキーボード、１４は文書検索手段、１５は文書データである。
【００８４】
キーボード３は、ユーザから入力された検索キーを文書検索手段１４に入力するものである。
【００８５】
文書検索手段１４は、２文字列に対するインバーテッドファイルからなるインデックス６を有しており、検索時には、検索キーのインバーテッドファイルを抽出して、インバーテッドファイルに記載されている、検索キーのその文章における出現位置（例えば先頭からの語数）を返す。
【００８６】
文書データ１５は、検索対象の文書で、１つのみであり、文章を有する。
【００８７】
なお、インデックス６の内部は、前記図３と同じである。
【００８８】
第２の実施の形態におけるインデックス作成の処理手順は、図５におけるＳ５の「既存インバーテッドファイルへの対応付けモジュール」と、Ｓ１０の「文書番号登録モジュール」以外は第一の実施の形態とまったく同一である。よってこの２つのモジュールのみを以下に説明する。
【００８９】
なお、第２の実施の形態では、検索出力は文書番号ではなく検索キーの文字列出現位置であるので、第２の実施の形態では、前記Ｓ１０の記載を「文字列出現位置登録モジュール」と読み替えるものとする。
【００９０】
第２の実施の形態における「既存インバーテッドファイルへの対応付けモジュール」では、新しく出現した文字列に対応付けるインバーテッドファイルを予め複数選択しておく。そして今回新しく出現した文字列をこの複数選択したインバーテッドファイルの内の１つに対応付け、前記選択された全てのインバーテッドファイルが次回以降新しく出現した文字列に順次対応付けされるように処理される。
【００９１】
図１０によりその動作を説明する。
【００９２】
Ｓ３０１．文書検索手段１４は、対応付け用インバーテッドファイルが未決定な場合、あるいはこれまでに選択された対応付け用インバーテッドファイルが全て新しく出現した文字列に対応付けられてもう存在しない場合はステップＳ３０２に進み、そうでない場合はステップＳ３０３に進む。
【００９３】
Ｓ３０２．文書検索手段１４は、全てのインバーテッドファイルから対応付け用インバーテッドファイルとして複数選択する。選択基準は、例えば登録数が少ない方から１／４とする。そして選択したインバーテッドファイルの中で新しく出現した文字列に対応付ける順番を予め決定しておく。決定方法は、例えば登録数の少ないインバーテッドファイルから対応付けられるような順番による。
【００９４】
Ｓ３０３．複数存在する対応付け用インバーテッドファイルの中から、現在の文字列に対応付けるインバーテッドファイルを選択する。次に選択したインバーテッドファイルのリスト番号を取得し、そのリスト番号を前記図５のＳ２で算出したハッシュ値が示すハッシュテーブル８に格納する。
【００９５】
Ｓ３０４．文書検索手段１４は前記Ｓ３０３で選択したインバーテッドファイルは、次回以降に新規出現した文字列への対応付けの対象外とする。但し次回以降でＳ３０２に通った場合は再度選択される場合もある。
【００９６】
図５におけるＳ１０の「文字列出現位置登録モジュール」では、前段の処理で特定されたインバーテッドファイルに、現在処理中の文字列の出現位置を登録する。はじめに、その出現位置を、最終登録数値をもとにして符号化処理を行い、次に最終登録数値を現在の文字列の出現位置に変更する。それから最後尾アドレスに前記符号化したものを挿入し、この挿入により増加した分を最後尾アドレスに登録する。
【００９７】
この動作を図１１により説明する。
【００９８】
Ｓ４０１．文書検索手段１４は、前段の処理で特定されたインバーテッドファイルに、現在処理中の文字列の出現位置を登録するため、以下の式から算出した整数値を符号化処理する。符号は例えばγ符号を使用する。なおＭｏｄ（Ａ、Ｂ）とはＡをＢで割った余りである。
【００９９】
【０１００】
例えば規定値が３００ならば、０〜５１０までの差分値は、使用ビット数は最大１７ｂｉｔと変化が無いにもかかわらず、３０１〜５１０は文字列検索回数が増えることになる。しかし、規定値が５１１ならば０〜５１０までの差分値は使用ビット数は最大１７ｂｉｔと維持され文字列検索回数も増えることは無い。このようにして検索時の文字列検索回数を極力減らしつつ、ビットを最大限有効利用する。
【０１０１】
Ｓ４０２．次に文書検索手段１４は、インバーテッドファイルリスト９の最終登録数値を今の文字列の出現位置に変更する。
【０１０２】
Ｓ４０３．それから、インバーテッドファイル記憶領域１０の最後尾アドレスに、前記符号化したものを挿入する。
【０１０３】
Ｓ４０４．この挿入により増加した分を、インバーテッドファイルリスト９の最後尾アドレスに加えて、これを変更する。
【０１０４】
なお、本発明は位置情報の差分値を小さくすることで圧縮符号による圧縮時に必要なビット数を削減することを目的としているため、ここで使用される符号はγ符号のみならずα符号、δ符号であってもよい。
【０１０５】
以上説明のように、本発明によれば、出現文字列をグループ化し、ある定数に対する出現位置情報の剰余をインバーテッドファイルに登録することで、検索速度を余り劣化させずにインデックスのメモリ使用量を削減することができる。
【０１０６】
【発明の効果】本発明により下記の効果を奏することができる。
【０１０７】
（１）１つのインバーテッドファイルに対して１種あるいは複数種の文字列を対応付けることにより、文字列間の出現位置情報の差分値を小さくし、インバーテッドファイルに対する管理情報を小さくできるため、メモリの消費量を抑えることができる。
【０１０８】
（２）新しい文字列を登録数が最も少ないインバーテッドファイルに対応付けるので、極端に登録数が多いインバーテッドファイルを作らないことで検索時間が極端に遅い検索キーを作成しないようにしつつ、インバーテッドファイル管理情報を少なくし、更にインバーテッドファイル内の差分値を小さくすることで小さいビット数でインバーテッドファイルを構成、管理することができる。
【０１０９】
（３）対応付けるインバーテッドファイルを予め決定しておき、そのインバーテッドファイルの登録数が規定数を超えるまでは、そのインバーテッドファイルに新規に出現した文字列を対応付けするので、新規な文字列が出現する度に登録数が最小のものを検出する必要がないので、処理を簡略化することができる。
【０１１０】
（４）インバーテッドファイルに、前回登録された位置情報との差分値に対して符号化するので、差分値を取って小さな値は少ないビット数で、大きな値は多いビット数で表現する符号を使用して、インバーテッドファイルのメモリ使用量を削減することができる。
【０１１１】
（５）差分値に対し規定数で割ってその余りを符号化したものを登録するので少ないビット数でインバーテッドファイルを表現できる。また規定数を、使用する符号がある限定された桁数で表し得る最大値を使用することにより、符号長を最大限有効利用できる。例えば図１３に示す如く、符号長１１ビットで６３まで表すことができるが、この場合規定値を６４にしてγ符号を使用すると１１ビットを最大限有効利用することができる。
【図面の簡単な説明】
【図１】複数の文字列の対応付け説明図である。
【図２】差分値を小さい値に変換する説明図である。
【図３】本発明の一実施の形態説明図である。
【図４】インデックスの要部説明図である。
【図５】本発明の第一の実施の形態の動作説明図（その１）である。
【図６】本発明の第一の実施の形態の動作説明図（その２）である。
【図７】本発明の第一の実施の形態の動作説明図（その３）である。
【図８】正整数の符号化説明図である。
【図９】本発明の第２の実施の形態説明図である。
【図１０】本発明の第２の実施の形態の動作説明図（その１）である。
【図１１】本発明の第２の実施の形態の動作説明図（その２）である。
【図１２】インバーテッドファイル説明図である。
【図１３】正整数の符号化説明図である。
【図１４】圧縮例説明図である。
【図１５】２文字列抽出説明図である。
【図１６】語尾が変化したときの位置情報説明図である。
【符号の説明】
１ パソコン本体
２ 表示装置
３ キーボード
４ 文書検索手段
５ 文書データ
６ インデックス
７ インバーテッドファイル管理テーブル
８ ハッシュテーブル
９ インバーテッドファイルリスト
１０ インバーテッドファイル記憶領域
１１ 最大数保持部
１２ ファイル数保持部
Claims (5)
- インデックスとなる文字列とその位置情報を登録するインバーテッドファイル作成方法において、
インバーテッドファイルに登録された位置情報数を示す登録数が記入されたインバーテッドファイルリストと、
インバーテッドファイルリストをポイントする文字列に対応した区分を有するテーブルを設け、
１種または複数種の文字列をある１つのインバーテッドファイルに登録し、
その位置情報を、以前に登録された他の位置情報との差分にもとづき符号化して格納することを特徴とする
インバーテッドファイル作成方法。 - 請求項１においてインデックスを作成する過程で出現した新しい文字列をインバーテッドファイルに登録するとき、登録数が最も少ないインバーテッドファイルに対応付けることを特徴とする
インバーテッドファイル作成方法。 - 請求項１においてインデックスを作成する過程で出現した新しい文字列をインバーテッドファイル登録するとき、
予め登録するインバーテッドファイルが１つあるいは複数決定されており、以後新しい文字列が出現した場合も、そのインバーテッドファイルの登録数が一定数を超えない限りはそのグループに登録することを特徴とする
インバーテッドファイル作成方法。 - 請求項１において、位置情報を以前に登録された他の位置情報との差分にもとづき符号化するとき、そのインバーテッドファイルに前回登録された位置情報との差分にもとづき符号化を行うことを特徴とする
インバーテッドファイル作成方法。 - 請求項１において、位置情報を以前に登録された他の位置情報との差分にもとづき符号化するとき、規定数を、使用する符号がある限定された桁数で表し得る最大値とし、位置情報との差分値をこの規定数で割った余りに対して符号化を行うことを特徴とする
インバーテッドファイル作成方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2003168554A JP2005004560A (ja) | 2003-06-13 | 2003-06-13 | インバーテッドファイル作成方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2003168554A JP2005004560A (ja) | 2003-06-13 | 2003-06-13 | インバーテッドファイル作成方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JP2005004560A true JP2005004560A (ja) | 2005-01-06 |
Family
ID=34093963
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2003168554A Pending JP2005004560A (ja) | 2003-06-13 | 2003-06-13 | インバーテッドファイル作成方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2005004560A (ja) |
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008192157A (ja) * | 2007-02-07 | 2008-08-21 | Fujitsu Ltd | コンパクトデシジョンダイアグラムを用いた効率的インデックス付け |
| KR100920745B1 (ko) | 2008-03-04 | 2009-10-07 | 재단법인대구경북과학기술원 | 질의 처리 방법, 역 리스트 관리 방법, 역 리스트 관리를위한 압축 방법, 및 구문 역 리스트 관리 방법 |
| US7701983B2 (en) | 2005-03-03 | 2010-04-20 | Nec Corporation | Tunable resonator, tunable light source using the same, and method for tuning wavelength of multiple resonator |
| JP2012064159A (ja) * | 2010-09-17 | 2012-03-29 | Casio Comput Co Ltd | Ｎグラム検索のための転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラム |
| JP2012203579A (ja) * | 2011-03-24 | 2012-10-22 | Casio Comput Co Ltd | Ｎグラム検索のための転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラム |
| US10409992B2 (en) | 2015-10-15 | 2019-09-10 | Fujitsu Limited | Investigation apparatus, computer-readable recording medium, and investigation method |
| KR20200014979A (ko) * | 2018-08-02 | 2020-02-12 | 주식회사 누리랩 | 역 색인 구성 방법, 역 색인을 이용한 유사 데이터 검색 방법 및 장치 |
-
2003
- 2003-06-13 JP JP2003168554A patent/JP2005004560A/ja active Pending
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7701983B2 (en) | 2005-03-03 | 2010-04-20 | Nec Corporation | Tunable resonator, tunable light source using the same, and method for tuning wavelength of multiple resonator |
| JP2008192157A (ja) * | 2007-02-07 | 2008-08-21 | Fujitsu Ltd | コンパクトデシジョンダイアグラムを用いた効率的インデックス付け |
| KR100920745B1 (ko) | 2008-03-04 | 2009-10-07 | 재단법인대구경북과학기술원 | 질의 처리 방법, 역 리스트 관리 방법, 역 리스트 관리를위한 압축 방법, 및 구문 역 리스트 관리 방법 |
| JP2012064159A (ja) * | 2010-09-17 | 2012-03-29 | Casio Comput Co Ltd | Ｎグラム検索のための転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラム |
| JP2012203579A (ja) * | 2011-03-24 | 2012-10-22 | Casio Comput Co Ltd | Ｎグラム検索のための転置インデックスの生成方法および生成装置、当該転置インデックスを用いた検索方法および検索装置、ならびに、コンピュータプログラム |
| US10409992B2 (en) | 2015-10-15 | 2019-09-10 | Fujitsu Limited | Investigation apparatus, computer-readable recording medium, and investigation method |
| KR20200014979A (ko) * | 2018-08-02 | 2020-02-12 | 주식회사 누리랩 | 역 색인 구성 방법, 역 색인을 이용한 유사 데이터 검색 방법 및 장치 |
| KR102081867B1 (ko) * | 2018-08-02 | 2020-02-26 | 주식회사 누리랩 | 역 색인 구성 방법, 역 색인을 이용한 유사 데이터 검색 방법 및 장치 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4805267B2 (ja) | トークンスペースレポジトリと共に使用される多段クエリ処理システム及び方法 | |
| Adjeroh et al. | The Burrows-Wheeler Transform:: Data Compression, Suffix Arrays, and Pattern Matching | |
| US8321445B2 (en) | Generating content snippets using a tokenspace repository | |
| JP4261779B2 (ja) | データ圧縮装置および方法 | |
| US8712977B2 (en) | Computer product, information retrieval method, and information retrieval apparatus | |
| JP3889762B2 (ja) | データ圧縮方法、プログラム及び装置 | |
| JP5415529B2 (ja) | 検索インデックスフォーマットの最適化 | |
| KR20130062889A (ko) | 데이터 압축 방법 및 시스템 | |
| JP5831298B2 (ja) | プログラム、情報処理装置およびインデックス生成方法 | |
| US9916314B2 (en) | File extraction method, computer product, file extracting apparatus, and file extracting system | |
| US20160321282A1 (en) | Extracting method, information processing method, computer product, extracting apparatus, and information processing apparatus | |
| JPS63292365A (ja) | 文字処理装置 | |
| US10146817B2 (en) | Inverted index and inverted list process for storing and retrieving information | |
| Al-Okaily et al. | Toward a better compression for DNA sequences using Huffman encoding | |
| US11669553B2 (en) | Context-dependent shared dictionaries | |
| Reznik | Coding of sets of words | |
| JP2005165598A (ja) | 可変長文字列検索装置及び可変長文字列検索方法並びにプログラム | |
| US20120254190A1 (en) | Extracting method, computer product, extracting system, information generating method, and information contents | |
| JP2005004560A (ja) | インバーテッドファイル作成方法 | |
| US8463759B2 (en) | Method and system for compressing data | |
| US7433880B2 (en) | Method and system for high speed encoding, processing and decoding of data | |
| Zhang | Transform based and search aware text compression schemes and compressed domain text retrieval | |
| KR20080087191A (ko) | 유알엘 압축 및 복원 방법 | |
| Sherlock et al. | Efficient sorting of search results by string attributes | |
| JPS62131348A (ja) | マルチインデツクスフアイルアクセス方式 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20060525 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20090512 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20090630 |
|
| RD03 | Notification of appointment of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7423 Effective date: 20090630 |
|
| RD04 | Notification of resignation of power of attorney |
Free format text: JAPANESE INTERMEDIATE CODE: A7424 Effective date: 20090630 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20090728 |