(57)【要約】【課題】  データの復号化処理の速度を落とさずに、インデックス作成処理を高速化し、インデックスのサイズを抑えることが課題である。【解決手段】  圧縮手段は、情報検索のためのインデックス内で用いられる数値データの粒度を粗くして、数値データを圧縮し、格納手段は、圧縮されたデータを格納する。復元手段は、数値データを復元し、復元された数値データの粒度を元に戻す。【選択図】図２１
2005129071.tif 000002
【特許請求の範囲】
【請求項１】
情報検索のためのインデックス内で用いられる数値データの粒度を粗くして、該数値データを圧縮する圧縮手段と、
圧縮されたデータを格納する格納手段と
を備えることを特徴とするデータ圧縮装置。
【請求項２】
前記圧縮手段は、前記数値データを、より小さな数値を表す中間数値データに変換して、圧縮することを特徴とする請求項１記載のデータ圧縮装置。
【請求項３】
前記圧縮手段は、情報検索のためのインデックス内で用いられる文書内単語出現頻度データと文書内単語出現位置データのうち、少なくとも１つ以上の数値データを圧縮することを特徴とする請求項１記載のデータ圧縮装置。
【請求項４】
前記圧縮手段は、粒度の粗くなった中間数値データを、４ビットをブロックの単位として圧縮し、前記圧縮されたデータの先頭部分に、該圧縮されたデータのブロック長を表す継続フラグ情報を生成することを特徴とする請求項１記載のデータ圧縮装置。
【請求項５】
前記圧縮手段は、粒度の粗くなった中間数値データが２以下の数値を表すとき、該中間数値データを２ビットのブロックで表し、該中間数値データが３以上の数値を表すとき、該中間数値データを、４ビットをブロックの単位として圧縮することを特徴とする請求項１記載のデータ圧縮装置。
【請求項６】
前記圧縮手段は、３以上６以下の数値データが与えられたとき、与えられた数値データを、２ビットの継続フラグ情報と２ビットのビットパターンで表すことを特徴とする請求項５記載のデータ圧縮装置。
【請求項７】
情報検索のためのインデックス内で用いられる数値データの粒度を粗くし、圧縮して格納する格納手段と、
前記数値データを復元し、復元された数値データの粒度を元に戻す復元手段とを備えることを特徴とするデータ復元装置。
【請求項８】
情報検索のためのインデックス内で用いられる数値データの粒度を粗くし、圧縮して格納する格納手段と、
前記数値データを復元し、復元された数値データの粒度を元に戻す復元手段と、
復元された元のデータを用いてデータベースを検索する検索手段と
を備えることを特徴とする情報検索装置。
【請求項９】
コンピュータのためのプログラムを記録した記録媒体であって、
情報検索のためのインデックス内で用いられる数値データの粒度を粗くして、該数値データを圧縮する機能を前記コンピュータに実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１０】
コンピュータのためのプログラムを記録した記録媒体であって、
情報検索のためのインデックス内で用いられる数値データの粒度を粗くして圧縮したデータを復元し、復元された数値データの粒度を元に戻す機能を前記コンピュータに実現させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１１】
情報検索のためのインデックス内で用いられる数値データの粒度を粗くして、
該数値データを圧縮する
ことを特徴とするデータ圧縮方法。
【請求項１２】
情報検索のためのインデックス内で用いられる数値データの粒度を粗くして圧縮したデータを復元し、
復元された数値データの粒度を元に戻す
ことを特徴とするデータ復元方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、任意のデータを符号化して圧縮するデータ圧縮装置およびその方法と、圧縮されたデータを復元するデータ復元装置およびその方法に関する。
【背景技術】
【０００２】
全文検索装置やランキング検索装置等の情報検索装置においては、検索に用いるインデックスの作成速度を高め、かつ、そのサイズを抑えることが重要である。ここで、全文検索装置とは、文書ＤＢ（データベース）内の文書の全文を対象として、ユーザにより指定された文字列（キーワード）の存在する文書を検索する装置を指し、ランキング検索装置とは、指定された文字列に対し、関連度の高い文書を検索する装置を指す。
【０００３】
このような情報検索装置におけるインデックスとは、検索対象となるキーに対して、文書番号、文書内単語出現頻度、文書内単語出現位置等の情報が付加されたデータ構造である。例えば、キーワード「犬」とそれを含む文書の［文書番号，文書内単語出現頻度］の組は、図３８のように表される。
【０００４】
図３８のインデックスは、「犬」というキーは、文書番号１の文書に１回、文書番号２の文書に１回、文書番号３の文書に２回、文書番号２５の文書に３回出現していることを表している。
【０００５】
この例において、仮に１つの数値データを３２ｂｉｔ（４ｂｙｔｅ）で表すとすると、キー「犬」に対するインデックスは８つの数値を含むので、これを表すのに２５６ｂｉｔ（＝３２ｂｉｔ＊８）の領域が必要となる。Ｇｂｙｔｅ単位の文書に対して、この方法による文書番号のみの格納領域の試算を行ってみると、図３９に示すように、原文のサイズに対して非常に巨大なものになる。そこで、インデックスサイズを圧縮する必要が生じる。
【０００６】
インデックスサイズの圧縮の基本は、１つの数値を決まったビット数（通常、３２ｂｉｔ）で表すのではなく、できるだけ少ないビット数で表すことである。後述するように、既存の符号化手法は、小さな数値を少ないビット数で表し、大きな数値を大きなビット数で表すようになっている。
【０００７】
そこで、インデックスサイズ圧縮の第一段階として、インデックス内に含まれる数値をできるだけ小さくすることが考えられる。これは、文書番号および文書内単語出現位置のそれぞれについて、連続する２つのデータの差分を取ることにより実現される。文書番号および文書内単語出現位置は、数値の小さいものから大きいものへと順に並んでいるため、各数値間の差分をとることにより、表現される数値を小さくすることができる。
【０００８】
例えば、図３８のインデックスに対して、各文書番号間の差分を取ると、図４０のようになる。図４０の最初のデータ［１，１］の文書番号“１”は、実際の文書番号そのものを表しており、２番目のデータ［１，１］の文書番号“１”は、最初のデータの文書番号“１”と２番目のデータの実際の文書番号“２”との差分値を表している。ここで、実際の文書番号とは、図３８に示された、差分をとる前の文書番号を指す。
【０００９】
また、３番目のデータ［１，２］の文書番号“１”は、２番目のデータの実際の文書番号“２”と３番目のデータの実際の文書番号“３”との差分値を表しており、４番目のデータ［２２，３］の文書番号“２２”は、３番目のデータの実際の文書番号“３”と４番目のデータの実際の文書番号“２５”との差分値を表している。
【００１０】
このような数値データに対する符号化手法としては、８ｂｉｔ  ｂｌｏｃｋ（８ＢＢ）符号化、４ｂｉｔ  ｂｌｏｃｋ（４ＢＢ）符号化、Ｕｎａｒｙ  ｃｏｄｉｎｇ、γ−ｃｏｄｉｎｇ、δ−ｃｏｄｉｎｇ等が知られている。これらの符号化手法のいずれにおいても、小さな数値は少ないｂｉｔ数で表され、大きな数値は大きなｂｉｔ数で表される。
【００１１】
まず、８ｂｉｔ  ｂｌｏｃｋ符号化とは、８ｂｉｔ（１ｂｙｔｅ）から成る各ブロックの中の最初の１ビット（ｔｏｐ  ｂｉｔ）を継続フラグとし、そのフラグが立っていれば、後続する次のブロックが存在するとみなす方法である。いくつかの数値の例を以下に挙げる。
表す数    ｂｉｔ
１        ０００００００１
２        ００００００１０
３        ００００００１１
１２８    １００００００１  ００００００００
１２９    １００００００１  ０００００００１
ここで、数値１、２、３の場合は、後続するブロックが存在しないので先頭のビットは０となっており、数値１２８、１２９の場合は、２番目のブロックが存在するので先頭のビットが１となっている。この方法では、１ワード（３２ｂｉｔ）で表現される数値を表す符号の最小のビット数は８ｂｉｔ、最大のビット数は４０ｂｉｔとなる。
【００１２】
また、４ｂｉｔ  ｂｌｏｃｋ符号化とは、４ｂｉｔから成る各ブロックの中の最初の１ビットを継続フラグとし、そのフラグが立っていれば、後続する次のブロックが存在するとみなす方法である。いくつかの数値の例を以下に挙げる。
表す数    ｂｉｔ
１        ０００１
２        ００１０
３        ００１１
４        ０１００
５        ０１０１
６        ０１１０
７        ０１１１
８        １００１  ００００
９        １００１  ０００１
１２８    １０１０  １０００  ００００
１２９    １０１０  １０００  ０００１
ここで、数値１、２、３、４、５、６、７の場合は、後続するブロックが存在しないので先頭のビットは０となっており、数値８、９の場合は、２番目のブロックが存在するので先頭のビットが１となっている。また、数値１２８、１２９の場合は、３番目のブロックが存在するので、１番目および２番目のブロックの先頭のビットが１となっている。この方法では、１ワードで表現される数値を表す符号の最小のビット数は４ｂｉｔ、最大ビット数は４４ｂｉｔとなる。
【００１３】
また、Ｕｎａｒｙ  ｃｏｄｉｎｇとは、数ｎを、ｎ−１個の１の連続＋０で表す方法である。これは、主として、後述するγ−ｃｏｄｉｎｇおよびδ−ｃｏｄｉｎｇの説明に用いられる。いくつかの数値の例を以下に挙げる。
表す数    ｂｉｔ
１        ０
２        １０
３        １１０
４        １１１０
５        １１１１０
６        １１１１１０
１２８    １１１１１・・・１２７個の１の連続・・・０
１２９    １１１１１・・・１２８個の１の連続・・・０
この方法では、１ワードで表現される数値を表す符号の最小のビット数は１ｂｉｔ、最大のビット数は４２９４９６７２９５（２32−１）となる。
【００１４】
また、γ−ｃｏｄｉｎｇでは、数ｘの符号を、ｐｒｅｆｉｘ部とｓｕｆｆｉｘ部に分けて表す。ここで、ｌｏｇ2 ｘの値以下の整数のうち最大のものをＩ１（ｘ）＝
2005129071.tif 000003
と書くことにすると、ｐｒｅｆｉｘ部は、数（１＋Ｉ１（ｘ））をＵｎａｒｙ  ｃｏｄｉｎｇで表すことで得られ、ｓｕｆｆｉｘ部は、値（ｘ−２I1(x) ）をＩ１（ｘ）ｂｉｔ分の２進数で表すことで得られる。いくつかの数値の例を以下に挙げる。
表す数  ｐｒｅｆｉｘ部                ｓｕｆｆｉｘ部
１      ０                            なし
（１＋０ビットで０を表す）    （０ビットで１−２0 を表す）
２      １０                          ０
（１＋１ビットで１を表す）    （１ビットで２−２1 を表す）
３      １０                          １
（１＋１ビットで１を表す）    （１ビットで３−２1 を表す）
４      １１０                        ００
（１＋２ビットで２を表す）    （２ビットで４−２2 を表す）
５      １１０                        ０１
（１＋２ビットで２を表す）    （２ビットで５−２2 を表す）
６      １１０                        １０
（１＋２ビットで２を表す）    （２ビットで６−２2 を表す）
７      １１０                        １１
（１＋２ビットで２を表す）    （２ビットで７−２2 を表す）
８      １１１０                      ０００
（１＋３ビットで３を表す）    （３ビットで８−２3 を表す）
９      １１１０                      ００１
（１＋３ビットで３を表す）    （３ビットで９−２3 を表す）
１０    １１１０                      ０１０
（１＋３ビットで３を表す）    （３ビットで１０−２3 を表す）
１２８  １１１１１１１０              ０００００００
（１＋７ビットで７を表す）    （７ビットで１２８−２7 を表す）
１２９  １１１１１１１０              ００００００１
（１＋７ビットで７を表す）    （７ビットで１２９−２7 を表す）
例えば、数値１２９の場合は、ｐｒｅｆｉｘ部の符号‘１１１１１１１０’は８ビットであり、７つの連続する“１”を含んでいる。これは、Ｉ（１２９）＝７、すなわち、数値１２９のｓｕｆｆｉｘ部が７ビットであることを表している。そして、ｓｕｆｆｉｘ部‘００００００１’は、７ビットで１２９−２7 を表している。この方法では、１ワードで表現される数値を表す符号の最小のビット数は１ｂｉｔ、最大のビット数は６３ｂｉｔ（＝１＋３１＋３１ｂｉｔ）となる。
【００１５】
δ−ｃｏｄｉｎｇでも、γ−ｃｏｄｉｎｇと同様に、数ｘの符号を、ｐｒｅｆｉｘ部とｓｕｆｆｉｘ部に分けて表す。ｐｒｅｆｉｘ部は、数（１＋Ｉ１（ｘ））をγ−ｃｏｄｉｎｇで表すことで得られ、ｓｕｆｆｉｘ部は、γ−ｃｏｄｉｎｇと同様に、値（ｘ−２I1(x) ）をＩ１（ｘ）ｂｉｔ分の２進数で表すことで得られる。いくつかの数値の例を以下に挙げる。
表す数  ｐｒｅｆｉｘ部                ｓｕｆｆｉｘ部
１      ０                            なし
（１のγｃｏｄｉｎｇ）        （０ビットで１−２0 を表す）
２      １００                        ０
（２のγｃｏｄｉｎｇ）        （１ビットで２−２1 を表す）
３      １００                        １
（２のγｃｏｄｉｎｇ）        （１ビットで３−２1 を表す）
４      １０１                        ００
（３のγｃｏｄｉｎｇ）        （２ビットで４−２2 を表す）
５      １０１                        ０１
（３のγｃｏｄｉｎｇ）        （２ビットで５−２2 を表す）
６      １０１                        １０
（３のγｃｏｄｉｎｇ）        （２ビットで６−２2 を表す）
７      １０１                        １１
（３のγｃｏｄｉｎｇ）        （２ビットで７−２2 を表す）
８      １１０００                    ０００
（４のγｃｏｄｉｎｇ）        （３ビットで８−２3 を表す）
９      １１０００                    ００１
（４のγｃｏｄｉｎｇ）        （３ビットで９−２3 を表す）
１０    １１０００                    ０１０
（４のγｃｏｄｉｎｇ）        （３ビットで１０−２3 を表す）
１２８  １１１００００                ０００００００
（８のγｃｏｄｉｎｇ）        （７ビットで１２８−２7 を表す）
１２９  １１１００００                ００００００１
（８のγｃｏｄｉｎｇ）        （７ビットで１２９−２7 を表す）
この方法では、１ワードで表現される数値を表す符号の最小のビット数は１ｂｉｔ、最大のビット数は４２ｂｉｔ（＝（５＋１＋５）＋３１ｂｉｔ）となる。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、上述した従来の符号化手法には、次のような問題がある。
例えば、これらの符号化手法を用いて図４０のインデックス構造を表現した場合に、必要となるｂｉｔ数は図４１に示すようになる。図４１においては、符号化前の元データのみ１０進数の値で記述され、符号化後のインデックス構造は、元データを表現するのに必要なビット数を用いて記述されている。図４１を見ると、圧縮を行わない３２ｂｉｔ符号化が最も多くのビット数を必要とし、δ−ｃｏｄｉｎｇが最も少ないビット数で記述できることが分かる。
【００１７】
一般に、８ｂｉｔ  ｂｌｏｃｋ符号化、４ｂｉｔ  ｂｌｏｃｋ符号化のようなブロック系の符号化手法では、どんなに小さな数値でも、必ず１ブロック分のビット数を必要とする。ところが、図４０のように、差分値を用いたインデックス構造においては、“１”や“２”のような小さな数値がデータの大部分を占めるため、インデックスサイズがあまり小さくならないという問題がある。また、各ブロックの先頭に継続フラグを付加していく処理が必要なため、インデックス作成処理に時間がかかるという問題もある。
【００１８】
これに対して、Ｕｎａｒｙ  ｃｏｄｉｎｇ、γ−ｃｏｄｉｎｇ、δ−ｃｏｄｉｎｇのようなビット系の符号化手法では、“１”や“２”のような小さな数値をブロック系よりも小さなビット数で表すことができる。しかし、数値が大きくなるにつれて、ブロック系よりもはるかにビット数が多くなる傾向にあるため、必ずしもインデックスサイズが小さくなるという保証はない。また、アルゴリズムが複雑なため、インデックス作成処理および復号化処理ともに、処理時間が長くなるという問題もある。
【００１９】
本発明の課題は、数値データの復号化処理の速度を落とさずに、インデックス作成処理を高速化し、インデックスのサイズを抑えることのできるデータ圧縮装置およびその方法と、データ復元装置およびその方法を提供することである。
【課題を解決するための手段】
【００２０】
図１は、本発明のデータ圧縮装置およびデータ復元装置の原理図である。図１のデータ圧縮装置は圧縮手段１と格納手段２を備え、データ復元装置は格納手段２と復元手段３を備える。
【００２１】
圧縮手段１は、与えられたデータ４をブロック単位で圧縮し、圧縮されたデータ５の先頭部分に、そのデータ５の長さを表す継続フラグ情報を生成する。
格納手段２は、圧縮されたデータ５を格納する。
【００２２】
復元手段３は、ブロック単位で圧縮されたデータ５の先頭部分の継続フラグ情報に基づいて、そのデータ５の長さを決定し、元のデータ４を復元する。
元のデータ４がバイナリのビットパターンである場合、一般に、それが表す数値が大きいほど圧縮率は低下し、小さいほど圧縮率は向上する。圧縮手段１は、元のデータ４の値に応じて圧縮されたデータ５のブロック長を決定し、対応する継続フラグ情報を生成する。そして、その継続フラグ情報をデータ５の先頭部分に格納し、それに続いてデータ４を表すデータを格納する。
【００２３】
数値が比較的小さければ、データ５はデータ４より短いビットパターンで表される。また、継続フラグ情報は、データ５から継続フラグ情報を除いた残りの部分のブロック長を表すようにしてもよい。
【００２４】
このような圧縮処理によれば、従来のブロック系の符号化のように、各ブロックの先頭に１つずつ継続フラグを付加していく必要がなく、継続フラグ情報の作成処理を１回で済ませることができる。したがって、データ５の作成処理が高速化され、これを用いてインデックス作成処理を高速化することができる。
【００２５】
また、データ４の値に応じてデータ５の先頭ブロックの長さを変えることができ、小さな数値の場合にこれを短くすることで、データ５の圧縮率が向上する。インデックス内で用いられる数値データには、１や２のような小さな値が多数現れるため、これはインデックスサイズの削減につながる。
【００２６】
復元手段３は、圧縮されたデータ５の先頭部分から継続フラグ情報を取り出し、それを元にデータ５のブロック長を決定する。次に、その長さから継続フラグ情報のブロック長を差し引いて、データ５の残りの部分のブロック長を求め、残りのデータを取り出す。そして、取り出したデータから元のデータ４を生成する。継続フラグ情報が残りのデータのブロック長を表す場合は、それをそのまま用いて残りのデータを取り出すことができる。
【００２７】
このような復元処理によれば、従来のブロック系の復号化のように、各ブロックの先頭から継続フラグを１つずつ取り出す必要がなく、継続フラグ情報の取り出しを１回で済ませることができる。したがって、比較的大きな数値の場合には、データ４の作成処理が高速化される。
【００２８】
さらに、従来のビット系の符号化と比較して、圧縮処理および復元処理がより簡単であり、処理時間が短くて済む。また、大きな数値の圧縮率はより高くなると考えられる。
本発明の別のデータ圧縮装置およびデータ復元装置において、圧縮手段１は、情報検索のためのインデックス内で用いられる数値データの粒度を粗くして、数値データを圧縮し、格納手段２は、圧縮されたデータを格納する。復元手段３は、数値データを復元し、復元された数値データの粒度を元に戻す。
【００２９】
例えば、図１の圧縮手段１と復元手段３は、後述する図２のＣＰＵ１６（中央処理装置）とメインメモリ１９に対応し、格納手段２はメインメモリ１９または磁気ディスク装置１１に対応する。
【発明の効果】
【００３０】
本発明によれば、数値データの復号化処理の速度を落とさずに、インデックス作成処理を高速化することができ、また、インデックスの圧縮率を高めることができる。
特に、４ＢＢ改符号化により、インデックス作成に要する時間を短縮することができ、Ｂ２４符号化および８４ＢＢ符号化により、それほど符号化／復号化の処理速度を落とすことなく、インデックスの圧縮率を高めることができる。また、Ｐｅｒ符号化により、情報の精度は多少落ちるものの、インデックスの圧縮率を高めることができる。
【発明を実施するための最良の形態】
【００３１】
以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。
本発明においては、新たな符号化方法として、４ｂｉｔ  ｂｌｏｃｋ（４ＢＢ）改符号化、８４ｂｉｔ  ｂｌｏｃｋ（８４ＢＢ）符号化、およびＢ２４（ｂｌｏｃｋ２４）符号化の３種類のブロック系符号化方法を提案する。まず、これらの符号化の概要を、それぞれ説明することにする。
【００３２】
４ＢＢ改符号化は、基本的には、上述の４ＢＢ符号化を改良したものである。通常の４ＢＢ符号化では、４ｂｉｔのうちｔｏｐ  １ｂｉｔを継続フラグ‘１’とし、そのフラグが存在していたら次の４ｂｉｔも数が存在するとみなす。これに対し、４ＢＢ改符号は、すべての継続フラグをまとめて先頭に持つ構造とする。そして、最初に現れる０より後のビットパターンを数値部分とみなす。いくつかの数値の例を以下に挙げる。
表す数    ｂｉｔ
１      ０００１
２      ００１０
３      ００１１
４      ０１００
５      ０１０１
６      ０１１０
７      ０１１１
８      １０００  １０００
９      １０００  １００１
１２８  １１００  １０００  ００００
１２９  １１００  １０００  ０００１
ここで、数値１、２、３、４、５、６、７の場合は、後続するブロックが存在しないので先頭のビットは０となっており、数値８、９の場合は、２番目のブロックが存在するので、１番目のブロックの先頭のビットが１となっている。また、数値１２８、１２９の場合は、３番目のブロックも存在するので、１番目のブロックの１番目および２番目のビットが１となっている。継続フラグに続く数値のビットパターンのＬＳＢ（least significant bit ）は、いずれの場合も最後のブロックの右端に来るようになっている。
【００３３】
この方法では、１ワードで表現される数値を表す符号の最小のビット数は４ｂｉｔ、最大ビット数は４４ｂｉｔとなり、圧縮効率自体は４ＢＢ符号化と等価である。しかしながら、符号化処理におけるステップ数が４ＢＢ符号化よりも少なくなる。このため、大規模データベース（ＤＢ）に対してインデックスを作成するような場合には、かなりの高速化が期待できる。
【００３４】
また、復号化に関しては、４ＢＢ符号化では、１つ１つ継続フラグを判定しながらループ処理を繰り返し、４ＢＢ改符号化では、継続フラグを先に復号化してから、まとめて数値を求めることになる。このような違いはあるが、復号化の処理速度は、符号化と比べると、両者の間でそれほど変化はない。ただし、数値が大きくなった場合には、４ＢＢ符号より４ＢＢ改符号のほうが速くなる。
【００３５】
次に、４ＢＢ改符号化と類似する８４ＢＢ符号化について説明する。４ＢＢ改符号化のブロック長は、どんな数値に対しても４ｂｉｔ一定であるのに対し、８４ＢＢ符号化では、初めの１ｂｌｏｃｋだけを８ｂｉｔ、継続フラグによって後ろに続く各ブロックを４ｂｉｔとする。この方法では、１２７以下の数値は１ｂｉｔの０と７ｂｉｔの数値のビットパターンで表され、１２８以上の数値はいくつかの継続フラグと数値のビットパターンで表現される。いくつかの数値の例を以下に挙げる。
表す数        ｂｉｔ
１    ０００００００１
２    ００００００１０
３    ００００００１１
４    ０００００１００
５    ０００００１０１
６    ０００００１１０
７    ０００００１１１
８    ００００１０００
９    ００００１００１
１２７    ０１１１１１１１
１２８    １０００１０００  ００００
１２９    １０００１０００  ０００１
ここで、数値１、２、３、４、５、６、７、８、９、１２７の場合は、後続するブロックが存在しないので先頭のビットは０となっており、数値１２８、１２９の場合は、２番目のブロックが存在するので、１番目のブロックの先頭のビットが１となっている。この方法では、１ワードで表現される数値を表す符号の最小のビット数は８ｂｉｔ、最大のビット数は４４ｂｉｔとなる。
【００３６】
例えば、インデックスにおいて文書内単語出現位置として扱われる数値は、文書番号（差分値）や文書内単語出現頻度と比較して、かなり大きな値になる。このため、差分値を用いたとしても、通常の数値データ符号化方法ではうまく圧縮することができない。
【００３７】
８４ＢＢ符号化は、４ＢＢ符号化や４ＢＢ改符号化と比較した場合、最初の８ｂｉｔで、１ｂｉｔ分だけ大きな数値まで表現することができる。これにより、中くらいの大きさの数値を、他の符号化よりも少ないビット数で表すことができ、文書内単語出現位置の符号化に適しているといえる。
【００３８】
次に、Ｂ２４符号化とは、数値１、２を２ｂｉｔで符号化し、数値３〜６を４ｂｉｔで符号化し、数値７以上を４ＢＢ改符号化で符号化する方法である。数値１、２は、初めの１ｂｉｔを継続フラグ‘０’とする２ｂｉｔ符号で表し、数値３〜６は、初めの２ｂｉｔを継続フラグ‘１０’とする４ｂｉｔ符号で表す。それらより大きい数値の符号化は、４ＢＢ改符号化の処理と同様になる。
【００３９】
ただし、４ＢＢ改符号化では、継続フラグの後に続く数値にはそのままの値が用いられるのに対し、Ｂ２４符号化では、数値１、２の場合には１を減じた値が用いられ、数値３〜６の場合には３を減じた値が用いられ、７以上の場合には７を減じた値が用いられる。また、継続フラグは、４ＢＢ改符号より１ｂｉｔ多くなる。いくつかの数値の例を以下に挙げる。
表す数    ｂｉｔ
１        ００
２        ０１
３        １０００
４        １００１
５        １０１０
６        １０１１
７        １１００  ００００
８        １１００  ０００１
９        １１００  ００１０
３９      １１１０  ００１０  ００００
４０      １１１０  ００１０  ０００１
ここで、数値１、２の場合は、先頭のビットは０となっており、その次のビットは元の数値から１を減じた値を表している。また、数値３、４、５、６の場合は、先頭の２ビットが１０となっており、その次の２ビットは元の数値から３を減じた値を表している。
【００４０】
また、数値７、８、９の場合は、２番目のブロックが存在するので、先頭の２ビットは１１となっており、２番目のブロックは元の数値から７を減じた値を表している。また、数値３９、４０の場合は、３番目のブロックも存在するので、先頭の３ビットが１１１となっており、２番目および３番目のブロックは元の数値から７を減じた値を表している。
【００４１】
この方法では、１ワードで表現される数値を表す符号の最小のビット数は２ｂｉｔ、最大のビット数は４４ｂｉｔとなり、数値１および２を表した場合に、４ＢＢ改符号化よりも２ビット節約することができる。通常のＤＢでは、文書内単語出現頻度のほとんどの数値が１もしくは２となるため、これらの数値を２ｂｉｔで表すことで、４ＢＢ符号化および４ＢＢ改符号化よりも、実際のインデックスの圧縮率が高くなることが期待される。
【００４２】
また、符号化処理自体も、４ＢＢ改符号化と比較して、それほど処理速度は低下しない。さらに、符号化する数値のほとんどが１もしくは２ならば、ステップ数は４ＢＢ改符号化よりも少なくなるため、より高速である。復号化の処理速度に関しても、符号化と同様である。
【００４３】
図２は、上述した符号化方法に基づくデータ圧縮装置／復元装置を含む情報検索装置の構成図である。図２の情報検索装置は、ソフトウェアを搭載した情報処理装置（コンピュータ）により実現され、磁気ディスク装置１１、フロッピーディスク駆動装置（ＦＤＤ）１２、プリンタ１４、ディスプレイ１５、ＣＰＵ（中央処理装置）１６、キーボード１７、ポインティング・デバイス１８、メインメモリ１９、およびネットワーク接続装置３１を備え、それらの各装置はバス２０により互いに結合されている。
【００４４】
磁気ディスク装置１１には、文書ＤＢ２１とインデックス２２が格納される。磁気ディスク装置１１の代わりに、光ディスク装置、光磁気ディスク装置等を用いてもよい。
ＣＰＵ１６は、メインメモリ１９に格納されたプログラムを用いて、情報検索に必要な処理を実現する。メモリ１９は、例えばＲＯＭ（read only memory）、ＲＡＭ（random access memory）等を含む。メモリ１９には、インデックス作成プログラム２３、検索エンジン（検索プログラム）２４、文書表示プログラム２５等が保持され、ワーク領域２６が設けられる。
【００４５】
インデックス作成プログラム２３は、文書ＤＢ２１からインデックス２２を作成して、磁気ディスク装置１１に格納する。このプログラム２３は、４ＢＢ改符号化、８４ＢＢ符号化、あるいはＢ２４符号化等に基づくデータ圧縮処理を含んでいる。
【００４６】
検索エンジン２４は、インデックス２２を用いて、文書ＤＢ２１の文書を検索する。全文検索装置の場合には、ユーザが指定した単語列を含む文書を検索し、ランキング検索装置の場合には、ユーザが指定した単語列に対して関連度の高い文書を検索する。この検索エンジン２４は、４ＢＢ改符号化、８４ＢＢ符号化、あるいはＢ２４符号化等に基づくデータ復元処理（復号化処理）を含んでいる。  文書表示プログラム２５は、検索結果から指定された文書を切り出し、それをユーザに表示する。ワーク領域２６は、これらのプログラム２３、２４、２５が処理に使用する領域である。
【００４７】
また、キーボード１７およびポインティング・デバイス１８は、ユーザからの要求や指示の入力に用いられ、プリンタ１４およびディスプレイ１５は、ユーザへの問い合せや処理結果等の出力に用いられる。
【００４８】
ＦＤＤ１２は、フロッピーディスク１３を駆動し、その記憶内容にアクセスする。フロッピーディスク１３に、必要なデータやプログラム２３、２４、２５等を格納しておき、必要に応じて、それらをメモリ１９にロードして使用することができる。また、フロッピーディスク１３以外にも、メモリカード、ＣＤ−ＲＯＭ（compact disk read only memory ）、光ディスク、光磁気ディスク等の任意のコンピュータ読み取り可能な記録媒体を使用することができる。
【００４９】
ネットワーク接続装置３１は、ＬＡＮ（local area network）等の任意の通信ネットワークに接続され、通信に伴うデータ変換等を行う。情報検索装置は、ネットワーク接続装置３１を介して、外部の情報提供者の装置３２（データベース等）と通信する。これにより、必要に応じて、上述のプログラムとデータを装置３２からネットワークを介して受け取り、それらをメモリ１９にロードして使用することができる。
【００５０】
次に、図３から図２０までを参照しながら、本発明のデータ圧縮装置／復元装置で用いる４ＢＢ改符号化、８４ＢＢ符号化、およびＢ２４符号化について、より具体的に説明する。
【００５１】
図３から図２０において、変数Ｖａｌｕｅは、元データのビットパターンを表し、変数Ｂｉｔｂｕｆは、符号化されたビットパターンを表す。また、‘：＝’は、右辺の値を左辺の値へ代入する操作を表し、‘ｂｉｔｃｏｐｙ（第１引数，第２引数）’は、第２引数のビットパターンを第１引数の先頭にコピーする操作を表す。
【００５２】
また、‘ｂｉｔｃａｔ（第１引数，第２引数）’は、第２引数のビットパターンを第１引数の後に追加する操作を表し、‘ｒｅａｄ（第１引数，第２引数）’は、第１引数から第２引数の個数分のビットパターンを読み取って数値にする操作を表す。その他の記述については、Ｃ言語もしくは数学記号と同様である。
【００５３】
比較のため、最初に、４ＢＢ符号化処理および４ＢＢ復号化処理の実現例を説明することにする。図３は、４ＢＢ符号化処理のフローチャートである。処理が開始されると、情報検索装置は、まず、ｉ＝１１とおいて（ステップＳ１）、８ビットの１次バッファＣｏｄｅ［ｉ］を用意し、Ｖａｌｕｅのビットパターンの下位３ビットをＣｏｄｅ［ｉ］の後半に入れる（ステップＳ２）。ここで、‘Ｖａｌｕｅ  ＆  ０ｘ７’は、Ｖａｌｕｅと０ｘ７＝‘０１１１’の論理積を表している。
【００５４】
次に、Ｖａｌｕｅを３ビット右にシフトし（ステップＳ３）、Ｖａｌｕｅの値を０と比較する（ステップＳ４）。Ｖａｌｕｅが０より大きい場合、ｉを１だけデクリメントし（ステップＳ５）、シフト後のＶａｌｕｅの下位３ビットの前にフラグの値１を付加して、Ｃｏｄｅ［ｉ］の後半に入れる（ステップＳ６）。ここで、‘０ｘ８  ｜  （Ｖａｌｕｅ  ＆  ０ｘ７）’は、０ｘ８＝‘１０００’とＶａｌｕｅの下位３ビットとの論理和を表している。そして、Ｖａｌｕｅを３ビット右にシフトし（ステップＳ７）、ステップＳ４以降の処理を繰り返す。
【００５５】
ステップＳ４において、Ｖａｌｕｅの値が０になると、次に、ｉと１２を比較する（ステップＳ８）。ｉが１２より小さければ、Ｃｏｄｅ［ｉ］の後半に格納された４ビットのデータを、Ｂｉｔｂｕｆの空領域の先頭部分にコピーして（ステップＳ９）。ｉを１だけインクリメントする（ステップＳ１０）。
【００５６】
そして、ステップＳ８以降の処理を繰り返し、ステップＳ８においてｉが１２に達すると、処理を終了する。このような符号化処理のプログラムコード（Ｃ言語で記述）は、例えば、図４に示すようになる。
【００５７】
図５は、４ＢＢ復号化処理のフローチャートである。処理が開始されると、情報検索装置は、まず、Ｂｉｔｂｕｆの初めの４ビットをＶａｌｕｅに読み込み（ステップＳ１１）、その値を０ｘ７と比較する（ステップＳ１２）。Ｖａｌｕｅが０ｘ７以下の場合は、先頭のフラグが０であり、後続ブロックが存在しないことを意味するので、そのまま処理を終了する。
【００５８】
Ｖａｌｕｅが０ｘ７より大きければ、先頭のフラグが１であり、後続ブロックが存在することを意味する。そこで、Ｖａｌｕｅのビットパターンの下位３ビットのみを改めてＶａｌｕｅとし（ステップＳ１３）、Ｂｉｔｂｕｆ内の次の４ビットを変数ｔｅｍｐに読み込む（ステップＳ１４）。
【００５９】
次に、Ｖａｌｕｅを３ビット左にシフトして、ｔｅｍｐの下位３ビットを加算する（ステップＳ１５）。これにより、ｔｅｍｐから先頭のフラグを除いた残りの部分がＶａｌｕｅに付加される。そして、ｔｅｍｐの値を０ｘ７と比較する（ステップＳ１６）。
【００６０】
ｔｅｍｐが０ｘ７より大きければステップＳ１４以降の処理を繰り返し、ｔｅｍｐが０ｘ７以下であれば処理を終了する。終了時のＶａｌｕｅのビットパターンは、Ｂｉｔｂｕｆに対応する元データを表している。このような復号化処理のプログラムコード（Ｃ言語で記述）は、例えば、図６に示すようになる。図６において、ｇｅｔ ｘｂｉｔｓ（Ｂｉｔｂｕｆ）は、Ｂｉｔｂｕｆからｘビット分のビットパターンを読み出す関数を表す。
【００６１】
次に、４ＢＢ改符号化処理および４ＢＢ改復号化処理を説明する。図７は、４ＢＢ改符号化処理のフローチャートである。処理が開始されると、情報検索装置は、まず、Ｉ２（Ｖａｌｕｅ）＝
2005129071.tif 000004
を求め、Ｉ２（Ｖａｌｕｅ）＋１を継続フラグＦｌａｇの値とする（ステップＳ２１）。ここで、Ｉ２（ｘ）＝
2005129071.tif 000005
は、ｌｏｇ8 ｘの値以下の整数のうち最大のものを表す。
次に、ＦｌａｇをＵｎａｒｙコードに変換してＢｉｔｂｕｆに入れ（ステップＳ２２）、それに続いてＶａｌｕｅを入れて（ステップＳ２３）、処理を終了する。
【００６２】
図７を図３と比較すると、４ＢＢ改符号化処理のステップ数は、４ＢＢ符号化処理のそれよりはるかに少ないことが分かる。４ＢＢ改符号化では、継続フラグを元データのビットパターンの前に付加するだけなので、このようにステップ数が少なくて済み、高速な処理が実現される。また、継続フラグの値が小さければ、そのＵｎａｒｙコードは容易に求められる。
【００６３】
４ＢＢ改符号化処理のプログラムコード（Ｃ言語で記述）は、例えば、図８に示すようになる。図８においては、実際にＩ２（Ｖａｌｕｅ）を計算する代わりに、ｉｆ−ｅｌｓｅ  ｉｆで代用している。これは、Ｖａｌｕｅの値の範囲と、それに対応するＩ２（Ｖａｌｕｅ）の値の範囲とが、あらかじめ分かっているためである。また、ｓｅｔ ｘｂｉｔｓ（Ｂｉｔｂｕｆ，Ｘ）は、Ｘからｘビット分のビットパターンを読み出してＢｉｔｂｕｆに書き込む関数を表す。
【００６４】
例えば、十進法で２１という数値は以下の手順により符号化され、対応する符号‘１００１０１０１’が得られる。
１．Ｉ２（２１）＋１＝２であるため、継続フラグは２となる（ステップＳ２１）。
【００６５】
２．継続フラグ２をＵｎａｒｙコード‘１０’でＢｉｔｂｕｆに入れる（ステップＳ２２）。
３．継続フラグに続いて、Ｖａｌｕｅ＝２１のビットパターン‘０１０１０１’をＢｉｔｂｕｆに入れる（ステップＳ２３）。
【００６６】
また、十進法で３００という数値は以下の手順により符号化され、対応する符号‘１１０１００１０１１００’が得られる。
１．Ｉ２（３００）＋１＝３であるため、継続フラグは３となる（ステップＳ２１）。
【００６７】
２．継続フラグ３をＵｎａｒｙコード‘１１０’でＢｉｔｂｕｆに入れる（ステップＳ２２）。
３．継続フラグに続いて、Ｖａｌｕｅ＝３００のビットパターン‘１００１０１１００’をＢｉｔｂｕｆに入れる（ステップＳ２３）。
【００６８】
次に、図９は、４ＢＢ改復号化処理のフローチャートである。処理が開始されると、情報検索装置は、まず、継続フラグのビット数を表す変数ＣＦｌａｇを０とおき（ステップＳ３１）、Ｂｉｔｂｕｆの初めの４ビットを変数Ｆｌａｇに読み込み（ステップＳ３２）、その値を０ｘ８と比較する（ステップＳ３３）。
【００６９】
Ｆｌａｇが０ｘ８より小さい場合は、先頭のビットが０であり、後続するブロックが存在しないことを意味する。そこで、ＦｌａｇをＶａｌｕｅに代入して（ステップＳ３４）、処理を終了する。
【００７０】
Ｆｌａｇが０ｘ８以上であれば、先頭のビットが１であり、後続ブロックが１つ以上存在することを意味する。そこで、最初の後続ブロックが継続フラグに対応するかどうかを調べるために、Ｆｌａｇと０ｘｆ＝‘１１１１’を比較する（ステップＳ３５）。
【００７１】
Ｆｌａｇが０ｘｆであれば、さらに継続フラグのブロックが続くことが分かる。そこで、ＣＦｌａｇに４を加算し、Ｂｉｔｂｕｆ内の次の４ビットをＦｌａｇに読み込む（ステップＳ３６）。そして、ステップＳ３５以降の処理を繰り返す。
【００７２】
Ｆｌａｇが０ｘｆより小さければ、そのビットパターンは０を含んでおり、継続フラグが途切れることが分かる。そこで、Ｆｌａｇの中で最初に０が現れた位置の順位をＣＦｌａｇに加算する。また、その位置より下のビットにマスクを掛けてそれらのビットを抽出し、Ｍａｓｋに代入する（ステップＳ３７）。
【００７３】
次に、今までにＢｉｔｂｕｆより読み込んだビット数をＣＦｌａｇの４倍から減算した値をＲｅａｄＢｉｔとする（ステップＳ３８）。ＣＦｌａｇを４倍することで、Ｂｉｔｂｕｆに含まれるデータの全ビット数が得られ、それから読み込み済みのビット数を差し引くことで、残りのデータの全ビット数が得られる。
【００７４】
次に、ＭａｓｋをＲｅａｄＢｉｔのビット数だけ左にシフトしてＶａｌｕｅに代入し、Ｂｉｔｂｕｆから、ＲｅａｄＢｉｔのビット数だけの残りのデータを読み込んで、それをＶａｌｕｅに加算し、処理を終了する。これにより、継続フラグの部分を除いた元データのビットパターンが、Ｖａｌｕｅとして得られる。
【００７５】
図９を図５と比較すると、４ＢＢ改復号化処理のステップ数は、４ＢＢ復号化処理のそれより少し多いことが分かる。しかし、図５および図９のループ内の処理において、４ＢＢ復号化の場合は、継続フラグとデータ部分を同時に読み込むのに対して、４ＢＢ改復号化の場合は、継続フラグ部分のみ読み込めばよい。このため、１ブロックまたは２ブロック程度の符号を復号化する場合は、４ＢＢ改復号化の処理速度は４ＢＢ復号化処理とそれほど変わらないが、大きなブロックの復号化では４ＢＢ改復号化の方がはるかに速くなる。
【００７６】
４ＢＢ改復号化処理のプログラムコード（Ｃ言語で記述）は、例えば、図１０に示すようになる。図１０においては、実際にＣＦｌａｇおよびＲｅａｄＢｉｔの値を計算する代わりに、ｉｆ−ｅｌｓｅ  ｉｆで代用している。これは、Ｖａｌｕｅの値の範囲と、それに対応するＲｅａｄＢｉｔの値の範囲とが、あらかじめ分かっているためである。また、変数Ｖａｌｕｅを変数Ｆｌａｇの代わりに用いており、変数Ｍａｓｋの代わりに、Ｖａｌｕｅとマスク用ビットパターンの論理積を用いている。
【００７７】
例えば、上述の符号‘１００１０１０１’は以下の手順により復号化され、対応する数値２１が得られる。
１．初めの４ビット‘１００１’を読み込む（ステップＳ３２）。
【００７８】
２．継続フラグは‘１０’であり、これは上の２ビットに相当するため、下の２ビットにマスクを掛け、Ｍａｓｋ＝‘１００１’＆０ｘ３＝‘０００１’を得る（ステップＳ３７）。また、ＲｅａｄＢｉｔ＝２×４−４＝４となるので、‘０００１’を４ビット左へシフトし、Ｖａｌｕｅに代入する（ステップＳ３８）。これにより、Ｖａｌｕｅ＝‘１００００’＝１６となる。
【００７９】
３．次の４ビット（ＲｅａｄＢｉｔのビット数）である‘０１０１’＝５を読み込み、Ｖａｌｕｅに加算する（ステップＳ３８）。こうして、Ｖａｌｕｅ＝１６＋５＝２１となる。
【００８０】
また、上述の符号‘１１０１００１０１１００’は以下の手順により復号化され、対応する数値３００が得られる。
１．初めの４ビット‘１１０１’を読み込む（ステップＳ３２）。
【００８１】
２．継続フラグは‘１１０’であり、これは上の３ビットに相当するため、下の１ビットにマスクを掛け、Ｍａｓｋ＝‘１１０１’＆０ｘ１＝‘０００１’を得る（ステップＳ３７）。また、ＲｅａｄＢｉｔ＝３×４−４＝８となるので、‘０００１’を８ビット左へシフトし、Ｖａｌｕｅに代入する（ステップＳ３８）。これにより、Ｖａｌｕｅ＝‘１００００００００’＝２５６となる。
【００８２】
３．次の８ビット（ＲｅａｄＢｉｔのビット数）である‘００１０１１００’＝４４を読み込み、Ｖａｌｕｅに加算する（ステップＳ３８）。こうして、Ｖａｌｕｅ＝２５６＋４４＝３００となる。
【００８３】
次に、８４ＢＢ符号化処理および８４ＢＢ復号化処理を説明する。図１１は、８４ＢＢ符号化処理のフローチャートである。処理が開始されると、情報検索装置は、まず、Ｖａｌｕｅの値を１２８と比較する（ステップＳ４１）。そして、Ｖａｌｕｅが１２８より小さければ、それをＢｉｔｂｕｆにコピーして（ステップＳ４２）、処理を終了する。
【００８４】
Ｖａｌｕｅが１２８以上であれば、上述のＩ２（ｘ）を用いてＩ２（Ｖａｌｕｅ）を求め、それを継続フラグＦｌａｇの値とする（ステップＳ４３）。次に、ＦｌａｇをＵｎａｒｙコードに変換してＢｉｔｂｕｆに入れ（ステップＳ４４）、それに続いてＶａｌｕｅを入れて（ステップＳ４５）、処理を終了する。
【００８５】
図１１を図７と比較すると、８４ＢＢ符号化処理では、４ＢＢ改符号化処理より条件判定が１つ増えるだけなので、その処理速度は４ＢＢ改符号化とほとんど変わらない。
また、８４ＢＢ符号化処理のプログラムコード（Ｃ言語で記述）は、例えば、図１２に示すようになる。図１２においては、４ＢＢ改符号化と同様に、実際にＩ２（Ｖａｌｕｅ）を計算する代わりに、ｉｆ−ｅｌｓｅ  ｉｆで代用している。
【００８６】
例えば、上述の３００という数値は以下の手順により符号化され、対応する符号‘１００１００１０１１００’が得られる。
１．Ｉ２（３００）＝２であるため、継続フラグは２となる（ステップＳ４３）。
【００８７】
２．継続フラグ２をＵｎａｒｙコード‘１０’でＢｉｔｂｕｆに入れる（ステップＳ４４）。
３．継続フラグに続いて、Ｖａｌｕｅ＝３００のビットパターン‘０１００１０１１００’をＢｉｔｂｕｆに入れる（ステップＳ４５）。
【００８８】
次に、図１３は、８４ＢＢ復号化処理のフローチャートである。処理が開始されると、情報検索装置は、まず、Ｂｉｔｂｕｆの初めの８ビットを変数Ｆｌａｇに読み込み（ステップＳ５１）、その値を１２８と比較する（ステップＳ５２）。Ｆｌａｇが１２８より小さい場合は、先頭のビットが０であり、後続するブロックが存在しないことを意味する。そこで、ＦｌａｇをＶａｌｕｅに代入して（ステップＳ５３）、処理を終了する。
【００８９】
Ｆｌａｇが１２８以上の場合は、先頭のビットが１であり、後続ブロックが１つ以上存在することを意味する。そこで、継続フラグのビット数を表す変数ＣＦｌａｇを０とおき（ステップＳ５４）、最初の後続ブロックが継続フラグに対応するかどうかを調べるために、Ｆｌａｇの値を０ｘｆｆ＝‘１１１１１１１１’と比較する（ステップＳ５４ａ）。
【００９０】
Ｆｌａｇが０ｘｆｆであれば、さらに継続フラグのブロックが続くことが分かる。そこで、ＣＦｌａｇに８を加算し（ステップＳ５４ｂ）、Ｂｉｔｂｕｆ内の次の４ビットをＦｌａｇに読み込む（ステップＳ５４ｃ）。そして、読み込んだブロックの次のブロックが継続フラグに対応するかどうかを調べるために、Ｆｌａｇの値を０ｘｆ＝‘１１１１’と比較する（ステップＳ５５）。
【００９１】
Ｆｌａｇが０ｘｆであれば、さらに継続フラグのブロックが続くことが分かる。そこで、ＣＦｌａｇに４を加算し、Ｂｉｔｂｕｆ内の次の４ビットをＦｌａｇに読み込む（ステップＳ５６）。そして、ステップＳ５５以降の処理を繰り返す。
【００９２】
ステップＳ５４ａでＦｌａｇが０ｘｆｆより小さいとき、および、ステップＳ５５でＦｌａｇが０ｘｆより小さいときは、そのビットパターンは０を含んでおり、継続フラグが途切れることが分かる。そこで、Ｆｌａｇの中で最初に０が現れた位置の順位をＣＦｌａｇに加算する。また、その位置より下のビットにマスクを掛けてそれらのビットを抽出し、Ｍａｓｋに代入する（ステップＳ５７）。
【００９３】
次に、今までにＢｉｔｂｕｆより読み込んだビット数を（ＣＦｌａｇ＋１）の４倍から減算した値をＲｅａｄＢｉｔとする（ステップＳ５８）。次に、ＭａｓｋをＲｅａｄＢｉｔのビット数だけ左にシフトしてＶａｌｕｅに代入し、Ｂｉｔｂｕｆから、ＲｅａｄＢｉｔのビット数だけの残りのデータを読み込んで、それをＶａｌｕｅに加算し、処理を終了する。これにより、継続フラグの部分を除いた元データのビットパターンが、Ｖａｌｕｅとして得られる。
【００９４】
このような８４ＢＢ復号化処理のプログラムコード（Ｃ言語で記述）は、例えば、図１４に示すようになる。図１４においては、４ＢＢ改復号化と同様に、実際にＣＦｌａｇおよびＲｅａｄＢｉｔの値を計算する代わりに、ｉｆ−ｅｌｓｅ  ｉｆで代用している。また、変数Ｖａｌｕｅを変数Ｆｌａｇの代わりに用いており、変数Ｍａｓｋの代わりに、Ｖａｌｕｅとマスク用ビットパターンの論理積を用いている。
【００９５】
例えば、上述の符号‘１００１００１０１１００’は以下の手順により復号化され、対応する数値３００が得られる。
１．初めの８ビット‘１００１００１０’を読み込む（ステップＳ５１）。
【００９６】
２．継続フラグは‘１０’であり、これは上の２ビットに相当するため、下の６ビットにマスクを掛け、Ｍａｓｋ＝‘１００１００１０’＆０ｘ３ｆ＝‘０００１００１０’を得る（ステップＳ５７）。また、ＲｅａｄＢｉｔ＝（２＋１）×４−８＝４となるので、‘０００１００１０’を４ビット左へシフトし、Ｖａｌｕｅに代入する（ステップＳ５８）。これにより、Ｖａｌｕｅ＝‘１００１０００００’＝２８８となる。
【００９７】
３．次の４ビット（ＲｅａｄＢｉｔのビット数）である‘１１００’＝１２を読み込み、Ｖａｌｕｅに加算する（ステップＳ５８）。こうして、Ｖａｌｕｅ＝２８８＋１２＝３００となる。
【００９８】
次に、Ｂ２４符号化処理およびＢ２４復号化処理を説明する。図１５は、Ｂ２４符号化処理のフローチャートである。処理が開始されると、情報検索装置は、まず、Ｖａｌｕｅを１と比較する（ステップＳ６１）。Ｖａｌｕｅ＝１の場合は、ビットパターン‘００’をＢｉｔｂｕｆに入れて（ステップＳ６２）、処理を終了する。
【００９９】
Ｖａｌｕｅが１でなければ、次に、それを２と比較する（ステップＳ６３）。Ｖａｌｕｅ＝２の場合は、ビットパターン‘０１’をＢｉｔｂｕｆに入れて（ステップＳ６４）、処理を終了する。
【０１００】
Ｖａｌｕｅが２でなければ、次に、それを７と比較する（ステップＳ６５）。Ｖａｌｕｅが７より小さければ、ビットパターン‘１０’を継続フラグとしてＢｉｔｂｕｆに入れ、その後に（Ｖａｌｕｅ−３）のビットパターンを入れて（ステップＳ６６）、処理を終了する。
【０１０１】
Ｖａｌｕｅが７以上であれば、ここで、上述のＩ２（ｘ）を用いてＩ２（Ｖａｌｕｅ）を求め、Ｉ２（Ｖａｌｕｅ）＋２を変数Ｆｌａｇに代入する（ステップＳ６７）。そして、ＦｌａｇをＵｎａｒｙコードに変換してＢｉｔｂｕｆに入れ、それに続いて（Ｖａｌｕｅ−７）のビットパターンを入れて、処理を終了する。
【０１０２】
図１５を図７と比較すると、Ｖａｌｕｅが１または２であれば、Ｂ２４符号化処理のステップ数は４ＢＢ改符号化処理のそれよりも少なくなり、処理速度はより速くなる。また、図１５のステップＳ６７の処理は、図７のステップＳ２１、Ｓ２２、Ｓ２３の処理に対応している。したがって、Ｖａｌｕｅが７以上であっても、４ＢＢ改符号化処理と比較して条件判定が３つ追加されているだけなので、処理速度はそれほど低下しない。Ｖａｌｕｅが３〜６の場合も同様である。
【０１０３】
Ｂ２４符号化処理のプログラムコード（Ｃ言語で記述）は、例えば、図１６に示すようになる。図１６においては、上述の４ＢＢ改符号化と同様に、実際にＩ２（Ｖａｌｕｅ）を計算する代わりに、ｉｆ−ｅｌｓｅ  ｉｆで代用している。  例えば、上述の２１という数値は以下の手順により符号化され、対応する符号‘１１００１１１０’が得られる。
【０１０４】
１．Ｉ２（２１）＋２＝３であるため、継続フラグは３となる（ステップＳ６７）。
２．継続フラグ３をＵｎａｒｙコード‘１１０’でＢｉｔｂｕｆに入れる（ステップＳ６７）。
【０１０５】
３．継続フラグに続いて、Ｖａｌｕｅ−７＝２１−７＝１４のビットパターン‘０１１１０’をＢｉｔｂｕｆに入れる（ステップＳ６７）。
次に、図１７は、Ｂ２４復号化処理のフローチャートである。処理が開始されると、情報検索装置は、まず、Ｂｉｔｂｕｆの初めの２ビットを変数Ｆｌａｇに読み込み（ステップＳ７１）、その値を１と比較する（ステップＳ７２）。
【０１０６】
Ｆｌａｇが１以下の場合は、先頭のビットが０であり、後続するビットパターンが存在しないことを意味する。そこで、（Ｆｌａｇ＋１）のビットパターンをＶａｌｕｅに代入して（ステップＳ７３）、処理を終了する。
【０１０７】
Ｆｌａｇが１より大きければ、先頭のビットが１であり、後続するビットパターンが存在することを意味する。そこで、次に、その値を２と比較する（ステップＳ７４）。
Ｆｌａｇが２であれば、後続するビットパターンは２ビットであることを意味する。そこで、Ｂｉｔｂｕｆの残りの２ビットを変数Ｖａｌｕｅに読み込み、３を加算して（ステップＳ７５）、処理を終了する。
【０１０８】
Ｆｌａｇが２より大きければ、それは‘１１’であり、後続する１つ以上のブロックが存在することを意味する。そこで、Ｆｌａｇ＝‘１１’を２ビット左へシフトし、Ｂｉｔｂｕｆの次の２ビットの値を読み込んで、Ｆｌａｇに加算する（ステップＳ７６）。そして、継続フラグのビット数を表す変数ＣＦｌａｇを０とおき、最初の後続ブロックが継続フラグに対応するかどうかを調べるために、Ｆｌａｇと０ｘｆ＝‘１１１１’を比較する（ステップＳ７８）。
【０１０９】
Ｆｌａｇが０ｘｆであれば、さらに継続フラグのブロックが続くことが分かる。そこで、ＣＦｌａｇに４を加算し、Ｂｉｔｂｕｆ内の次の４ビットをＦｌａｇに読み込む（ステップＳ７９）。そして、ステップＳ７８以降の処理を繰り返す。
【０１１０】
Ｆｌａｇが０ｘｆより小さければ、そのビットパターンは０を含んでおり、継続フラグが途切れることが分かる。そこで、Ｆｌａｇの中で最初に０が現れた位置の順位をＣＦｌａｇに加算する。また、その位置より下のビットにマスクを掛けてそれらのビットを抽出し、Ｍａｓｋに代入する（ステップＳ８０）。
【０１１１】
次に、今までにＢｉｔｂｕｆより読み込んだビット数を（ＣＦｌａｇ−１）の４倍から減算した値をＲｅａｄＢｉｔとする（ステップＳ８１）。そして、ＭａｓｋをＲｅａｄＢｉｔのビット数だけ左にシフトしてＶａｌｕｅに代入し、Ｂｉｔｂｕｆから、ＲｅａｄＢｉｔのビット数だけの残りのデータを読み込んで、それをＶａｌｕｅに加算する。これにより、符号から継続フラグの部分を除いたビットパターンが、Ｖａｌｕｅとして得られる。元データを得るために、Ｖａｌｕｅにさらに７を加算して、処理を終了する。
【０１１２】
図１７を図９と比較すると、Ｂ２４復号化処理では４ＢＢ改復号化処理よりも条件判定が１つ多いが、処理速度はそれほど低下しない。
Ｂ２４復号化処理のプログラムコード（Ｃ言語で記述）は、例えば、図１８に示すようになる。図１８においては、上述の４ＢＢ改復号化と同様に、実際にＣＦｌａｇおよびＲｅａｄＢｉｔの値を計算する代わりに、ｉｆ−ｅｌｓｅ  ｉｆで代用している。また、変数Ｖａｌｕｅを変数Ｆｌａｇの代わりに用いており、変数Ｍａｓｋの代わりに、Ｖａｌｕｅとマスク用ビット列の論理積を用いている。
【０１１３】
例えば、上述の符号‘１１００１１１０’は以下の手順により復号化され、対応する数値２１が得られる。
１．初めの２ビット‘１１’をＦｌａｇに読み込む（ステップＳ７１）。
【０１１４】
２．読み込んだ値は３であるため、Ｆｌａｇを２ビット左にシフトして、さらに次の２ビット‘００’を読み込み（ステップＳ７６）、継続フラグを確認する（ステップＳ７８）。ここで、継続フラグが‘１１０’であることが分かる。
【０１１５】
３．継続フラグが３ビット目で途切れているので、継続フラグに続く残りの１ビットにマスクを掛け、Ｍａｓｋ＝‘１１００’＆０ｘ１＝‘００００’を得る。また、ＲｅａｄＢｉｔ＝（３−１）×４−４＝４となるので、‘００００’を４ビット左へシフトし、Ｖａｌｕｅに代入する（ステップＳ８１）。
【０１１６】
４．次の４ビット（ＲｅａｄＢｉｔのビット数）である‘１１１０’＝１４を読み込み、Ｖａｌｕｅに加算して、さらに７を加算する（ステップＳ８１）。こうして、Ｖａｌｕｅ＝１４＋７＝２１となる。
【０１１７】
以上説明した４ＢＢ改符号化、８４ＢＢ符号化、およびＢ２４符号化に必要な各ビット数を、４ＢＢ符号化、γ−ｃｏｄｉｎｇ、およびδ−ｃｏｄｉｎｇに必要な各ビット数と比較すると、図１９に示すようになる。
【０１１８】
図１９において、ほとんどの符号化方法が小さい数値を少ないビット数、大きい数値を多いビット数で表していることが分かる。ある数値列が与えられた時にどの符号化が最も圧縮率が高くなるかは、その数値列中においてどの範囲の数値が多く出現しているかによって大きく異なる。
【０１１９】
例えば、１、２のみが多く出現する数値列に対しては、Ｂ２４符号化が最も圧縮率が高いと予想され、また、５１２付近の値が多く出現するような数値列に対しては、８４ＢＢ符号化が最も圧縮率が高いと期待できる。
【０１２０】
また、３２ビットで表現できる最大数である４２９４９６７２９５を各方法で符号化すると、得られる符号のビットパターンとビット数は図２０に示すようになる。
ところで、インデックスに用いられる文書内単語出現位置は、必ずしも小さな数値とは限らず、差分情報を活用したとしてもかなり大きな数値となることが多い。このような大きな数値を扱った場合には、いずれの符号化方法を用いても圧縮効率は上がらない。
【０１２１】
そこで、本発明では、本来の文書内単語出現位置等の数値データを適当な整数値で除算することにより、情報の粒度を粗くし、より小さな中間数値に変換することにする。小さな数値であれば、図１９から分かるように、いずれの符号化方法を用いても圧縮効率が良くなる。このような変換を用いた符号化をＰｅｒ符号化と呼び、特に、除算の分母をｎとする場合をＰｅｒ（ｎ）符号化と呼ぶことにする。
【０１２２】
図２１は、Ｐｅｒ符号化処理のフローチャートである。処理が開始されると、情報検索装置は、まず、元データを変数ｎｕｍに読み込み（ステップＳ９１）、それをあらかじめ決められた分母値Ｐｅｒで除算する（ステップＳ９２）。
【０１２３】
除算に用いるＰｅｒの値は、高速に実行できるシフト命令が利用可能な値から選択することが望ましい。例えば、２、４、８、１６、３２、６４等の値がＰｅｒとして用いられる。ここでは、得られた商の少数点以下の端数は切り捨て、その整数部分を中間数値とし、それを改めてｎｕｍに代入する。
【０１２４】
次に、ｎｕｍの値を符号化して（ステップＳ９３）、処理を終了する。ステップＳ９３では、任意の符号化方法を用いることができる。ただし、例えばＢ２４符号化のように、０を表現できない符号化方法を用いる場合には、ステップＳ９２で得られたｎｕｍが０のとき、それに１を加算してから符号化するものとする。
【０１２５】
ここで、ステップＳ９３における符号化方法としてＢ２４符号化を用いた場合の例を説明する。ここでは、分母値を２とするＰｅｒ（２）符号化により、上述の２１という数値は以下の手順により符号化され、対応する符号‘１１００００１１’が得られる。
【０１２６】
１．２１を２で除算し、商の小数点以下は切り捨てる。これにより、ｎｕｍ＝１０となる（ステップＳ９２）。
２．Ｉ２（１０）＋２＝３であるため、継続フラグは３となる（図１５、ステップＳ６７）。
【０１２７】
３．継続フラグ３をＵｎａｒｙコード‘１１０’でＢｉｔｂｕｆに入れる（ステップＳ６７）。
４．継続フラグに続いて、Ｖａｌｕｅ−７＝１０−７＝３のビットパターン‘０００１１’をＢｉｔｂｕｆに入れる（ステップＳ６７）。
【０１２８】
次に、図２２は、Ｐｅｒ復号化処理のフローチャートである。処理が開始されると、情報検索装置は、まず、Ｐｅｒ符号を復号化し、得られた数値を変数ｎｕｍに読み込む（ステップＳ１０２）。ただし、ステップＳ１０２では、図２１のステップＳ９３で用いた符号化方法に対応する復号化方法を用いる。次に、ｎｕｍに上述の分母値Ｐｅｒを乗算し（ステップＳ１０３）、その結果を呼び出し元のプログラムへ返して（ステップＳ１０４）、処理を終了する。
【０１２９】
一般に、Ｐｅｒ復号化により得られる数値データは、必ずしも元データと一致するとは限らない。例えば、上述の数値２１に対応する符号‘１１００００１１’をＢ２４復号化処理により復号化すると、数値１０が得られる（ステップＳ１０２）。しかし、この数値にＰｅｒ＝２を乗算すると、ｎｕｍ＝２０となり（ステップＳ１０３）、元の数値には戻らない。したがって、Ｐｅｒ符号化は、文書内単語出現位置のように、元データのおおよその値が再現されればよい場合に有効である。
【０１３０】
インデックスの圧縮に用いられる各符号化方法は、いずれも小さな数値を少ないビットで、大きな数値を多くのビットで表すようになっている。Ｐｅｒ符号化によれば、大きな数値を小さな数値に変換してから符号化するので、それだけ圧縮の効果が期待できる。
【０１３１】
ところで、文書内単語出現位置の情報を含めたインデックス構造は、［文書番号，文書内単語出現頻度，文書内単語出現位置領域数，文書内単語出現位置，・・・，］のようになる。ここで、文書内単語出現位置領域数には、後続する文書内単語出現位置のデータ領域の大きさが記述される。
【０１３２】
文書番号の情報は、該当する文書番号と前の組の文書番号との差分で表すことができ、文書内単語出現位置の情報も、同一文書内における該当する位置と前の文書内単語出現位置との差分で表すことができる。しかし、文書内単語出現頻度や文書内単語出現位置領域数は、数値の小さいものから大きいものの順に並んでいないので、差分値を取ることはできない。
【０１３３】
通常の情報検索装置では、文書内単語出現位置領域数はビット単位で記述される。しかし、本発明の符号化方法では、最小のブロックのビット数が２ビットまたは４ビットであることから、文書内単語出現位置領域数を最小ブロック単位で記述することができる。
【０１３４】
例えば、あるキーの出現位置の情報を表現するのに２００ｂｉｔ必要だったとすると、ビット単位では２００という数値で表現されるのに対して、２ビット単位では１００という数値で表現され、４ビット単位では５０という数値で表現される。文書内単語出現位置領域数も他の数値とともに符号化されるため、より小さい数値で表現することによって、インデックスサイズの圧縮率の向上が期待できる。
【０１３５】
また、文書内単語出現位置領域数として文書内単語出現頻度を代用した場合のインデックス構造は、［文書番号，文書内単語出現頻度，文書内単語出現位置，・・・，］のようになる。ここで、文書内単語出現頻度は、後続する文書内単語出現位置の個数を表す。
【０１３６】
ただし、この場合、次の組の文書番号を取り出すためには、文書内単語出現頻度の後の文書内単語出現位置をすべて復号化しなければならない。これに対して、文書内単語出現位置領域数を付加した場合には、文書内単語出現位置を復号化する必要はなく、その領域数から計算されるビット数だけ離れた場所にアクセスすればよい。
【０１３７】
次に、図２３から図３７までを参照しながら、上述の各符号化方法を組み合わせて用いたインデックス構造の例を説明する。インデックスの構造は、その用途に応じて、以下の５つの構成を取るものとする。
【０１３８】
第１のインデックス構造：［文書番号］
第２のインデックス構造：［文書番号，文書内単語出現頻度］
第３のインデックス構造：［文書番号，文書内単語出現頻度，文書内単語出現位置，・・・，］
第４のインデックス構造：［文書番号，文書内単語出現位置領域数，文書内単語出現位置，・・・，］
第５のインデックス構造：［文書番号，文書内単語出現頻度，文書内単語出現位置領域数，文書内単語出現位置，・・・，］
例えば、図４０のインデックス構造を第５のインデックス構造を用いて書き直すと、図２３に示すように表現される。ここで、‘？’の位置には、文書内単語出現位置領域数が書き込まれる。以下に示す例では、元データとして図２３の数値を用いており、それらは１０進数で表されている。
【０１３９】
図２４は、第１のインデックス構造を用いた場合の４ＢＢ改符号およびＢ２４符号のビットパターンと、それぞれの符号の総ビット数を示している。第１のインデックス構造は文書番号のみであるので、Ｐｅｒ符号化は用いられない。
【０１４０】
図２５は、第２のインデックス構造を用いた場合の符号のビットパターンと総ビット数を示している。ここでは、Ｐｅｒ（２）符号化を、文書内単語出現頻度のみに適用し、（文書内単語出現頻度／２）の整数部分を符号化している。ただし、その整数部分が０となる場合は代わりに数値１を符号化している。
【０１４１】
また、文書番号と文書内単語出現頻度を符号化する際、上述の各符号化方法の様々な組合せが考えられる。ここでは、以下の６通りの組合せについて、符号化の結果が示されている。
【０１４２】
１．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改（図２５、組合せ１）
２．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改＋Ｐｅｒ（２）（図２５、組合せ２）
３．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４＋Ｐｅｒ（２）（図２５、組合せ３）
４．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改（図２５、組合せ４）  ５．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改＋Ｐｅｒ（２）（図２５、組合せ５）
６．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４＋Ｐｅｒ（２）（図２５、組合せ６）
図２６、２７、２８は、第３のインデックス構造を用いた場合の符号のビットパターンと総ビット数を示している。ここでは、Ｐｅｒ（１６）符号化を、文書内単語出現位置のみに適用し、（文書内単語出現頻度／１６）の整数部分を符号化している。ただし、その整数部分が０となる場合は代わりに数値１を符号化している。
【０１４３】
第３のインデックス構造の場合には、文書内単語出現位置の個数が文書内単語出現頻度となるため、文書内単語出現頻度のみにＰｅｒ符号化を適用することはできない。そこで、以下の２４通りの組合せについて、符号化の結果が示されている。
【０１４４】
１．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：４ＢＢ改（図２６、組合せ１）
２．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図２６、組合せ２）
３．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：Ｂ２４（図２６、組合せ３）
４．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図２６、組合せ４）
５．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：４ＢＢ改（図２６、組合せ５）
６．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図２６、組合せ６）
７．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：Ｂ２４（図２６、組合せ７）
８．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図２６、組合せ８）
９．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：４ＢＢ改（図２７、組合せ９）
１０．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図２７、組合せ１０）
１１．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：Ｂ２４（図２７、組合せ１１）
１２．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図２７、組合せ１２）
１３．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：４ＢＢ改（図２７、組合せ１３）
１４．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図２７、組合せ１４）
１５．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：Ｂ２４（図２７、組合せ１５）
１６．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図２７、組合せ１６）
１７．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：８４ＢＢ（図２８、組合せ１７）
１８．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図２８、組合せ１８）
１９．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：８４ＢＢ（図２８、組合せ１９）
２０．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図２８、組合せ２０）
２１．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：８４ＢＢ（図２８、組合せ２１）
２２．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図２８、組合せ２２）
２３．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：８４ＢＢ（図２８、組合せ２３）
２４．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図２８、組合せ２４）
図２９、３０、３１は、第４のインデックス構造を用いた場合の符号のビットパターンと総ビット数を示している。ここでは、Ｐｅｒ（１６）符号化を、文書内単語出現位置のみに適用し、（文書内単語出現頻度／１６）の整数部分を符号化している。ただし、その整数部分が０となる場合は代わりに数値１を符号化している。
【０１４５】
文書内単語出現位置を４ＢＢ改符号化で符号化した場合には、文書内単語出現位置領域数の単位は４ビットとなり、Ｂ２４符号化で符号化した場合には、文書内単語出現位置領域数の単位は２ビットとなる。コード系のコラムの（）内のビット数は、この単位ブロックの大きさを表し、各ビットパターンの右側の（）内の数値は、そのビットパターンに対応する十進数を表す。ここでは、以下の２４通りの組合せについて、符号化の結果が示されている。
【０１４６】
１．文書番号：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改（図２９、組合せ１）
２．文書番号：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図２９、組合せ２）
３．文書番号：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４（図２９、組合せ３）
４．文書番号：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図２９、組合せ４）
５．文書番号：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改（図２９、組合せ５）
６．文書番号：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図２９、組合せ６）
７．文書番号：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４（図２９、組合せ７）
８．文書番号：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図２９、組合せ８）
９．文書番号：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改（図３０、組合せ９）
１０．文書番号：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図３０、組合せ１０）
１１．文書番号：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４（図３０、組合せ１１）
１２．文書番号：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図３０、組合せ１２）
１３．文書番号：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改（図３０、組合せ１３）
１４．文書番号：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図３０、組合せ１４）
１５．文書番号：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４（図３０、組合せ１５）
１６．文書番号：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図３０、組合せ１６）
１７．文書番号：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ（図３１、組合せ１７）
１８．文書番号：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３１、組合せ１８）
１９．文書番号：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ（図３１、組合せ１９）
２０．文書番号：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３１、組合せ２０）
２１．文書番号：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ（図３１、組合せ２１）
２２．文書番号：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３１、組合せ２２）
２３．文書番号：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ（図３１、組合せ２３）
２４．文書番号：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３１、組合せ２４）
図３２、３３、３４、３５、３６、３７は、第５のインデックス構造を用いた場合の符号のビットパターンと総ビット数を示している。ここでは、Ｐｅｒ（１６）符号化を、文書内単語出現位置のみに適用し、（文書内単語出現頻度／１６）の整数部分を符号化している。ただし、その整数部分が０となる場合は代わりに数値１を符号化している。
【０１４７】
コード系のコラムの（）内のビット数は、文書内単語出現位置領域数の単位の大きさを表し、各ビットパターンの右側の（）内の数値は、そのビットパターンに対応する十進数を表す。ここでは、以下の４８通りの組合せについて、符号化の結果が示されている。
【０１４８】
１．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改（図３２、組合せ１）
２．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図３２、組合せ２）
３．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４（図３２、組合せ３）
４．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図３２、組合せ４）
５．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改（図３２、組合せ５）
６．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図３２、組合せ６）
７．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４（図３２、組合せ７）
８．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図３２、組合せ８）
９．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改（図３３、組合せ９）
１０．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図３３、組合せ１０）
１１．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４（図３３、組合せ１１）
１２．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図３３、組合せ１２）
１３．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改（図３３、組合せ１３）
１４．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図３３、組合せ１４）
１５．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４（図３３、組合せ１５）
１６．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図３３、組合せ１６）
１７．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改（図３４、組合せ１７）
１８．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図３４、組合せ１８）
１９．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４（図３４、組合せ１９）
２０．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図３４、組合せ２０）
２１．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改（図３４、組合せ２１）
２２．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図３４、組合せ２２）
２３．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４（図３４、組合せ２３）
２４．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図３４、組合せ２４）
２５．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改（図３５、組合せ２５）
２６．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図３５、組合せ２６）
２７．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４（図３５、組合せ２７）
２８．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図３５、組合せ２８）
２９．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改（図３５、組合せ２９）
３０．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：４ＢＢ改＋Ｐｅｒ（１６）（図３５、組合せ３０）
３１．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４（図３５、組合せ３１）
３２．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：Ｂ２４＋Ｐｅｒ（１６）（図３５、組合せ３２）
３３．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ（図３６、組合せ３３）  ３４．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３６、組合せ３４）
３５．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ（図３６、組合せ３５）
３６．文書番号：４ＢＢ改、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３６、組合せ３６）
３７．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ（図３６、組合せ３７）
３８．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３６、組合せ３８）
３９．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ（図３６、組合せ３９）
４０．文書番号：４ＢＢ改、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３６、組合せ４０）
４１．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ（図３７、組合せ４１）
４２．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３７、組合せ４２）
４３．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ（図３７、組合せ４３）
４４．文書番号：Ｂ２４、文書内単語出現頻度：４ＢＢ改、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３７、組合せ４４）
４５．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ（図３７、組合せ４５）
４６．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：４ＢＢ改、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３７、組合せ４６）
４７．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ（図３７、組合せ４７）
４８．文書番号：Ｂ２４、文書内単語出現頻度：Ｂ２４、文書内単語出現位置領域数：Ｂ２４、文書内単語出現位置：８４ＢＢ＋Ｐｅｒ（１６）（図３７、組合せ４８）
以上説明した実施形態においては、本発明のデータ圧縮／復元装置を情報検索装置に適用しているが、このデータ圧縮／復元装置は、検索用インデックスのみに限らず、任意のデータの圧縮／復元に用いることができる。
【図面の簡単な説明】
【０１４９】
【図１】本発明のデータ圧縮／復元装置の原理図である。
【図２】情報検索装置の構成図である。
【図３】４ＢＢ符号化処理のフローチャートである。
【図４】４ＢＢ符号化のプログラムを示す図である。
【図５】４ＢＢ復号化処理のフローチャートである。
【図６】４ＢＢ復号化のプログラムを示す図である。
【図７】４ＢＢ改符号化処理のフローチャートである。
【図８】４ＢＢ改符号化のプログラムを示す図である。
【図９】４ＢＢ改復号化処理のフローチャートである。
【図１０】４ＢＢ改復号化のプログラムを示す図である。
【図１１】８４ＢＢ符号化処理のフローチャートである。
【図１２】８４ＢＢ符号化のプログラムを示す図である。
【図１３】８４ＢＢ復号化処理のフローチャートである。
【図１４】８４ＢＢ復号化のプログラムを示す図である。
【図１５】Ｂ２４符号化処理のフローチャートである。
【図１６】Ｂ２４符号化のプログラムを示す図である。
【図１７】Ｂ２４復号化処理のフローチャートである。
【図１８】Ｂ２４復号化のプログラムを示す図である。
【図１９】数値表現に必要なビット数を示す図である。
【図２０】３２ｂｉｔ最大数の符号化例を示す図である。
【図２１】Ｐｅｒ符号化処理のフローチャートである。
【図２２】Ｐｅｒ復号化処理のフローチャートである。
【図２３】第５のインデックス構造の例を示す図である。
【図２４】第１のインデックス構造のビットパターンを示す図である。
【図２５】第２のインデックス構造のビットパターンを示す図である。
【図２６】第３のインデックス構造のビットパターンを示す図（その１）である。
【図２７】第３のインデックス構造のビットパターンを示す図（その２）である。
【図２８】第３のインデックス構造のビットパターンを示す図（その３）である。
【図２９】第４のインデックス構造のビットパターンを示す図（その１）である。
【図３０】第４のインデックス構造のビットパターンを示す図（その２）である。
【図３１】第４のインデックス構造のビットパターンを示す図（その３）である。
【図３２】第５のインデックス構造のビットパターンを示す図（その１）である。
【図３３】第５のインデックス構造のビットパターンを示す図（その２）である。
【図３４】第５のインデックス構造のビットパターンを示す図（その３）である。
【図３５】第５のインデックス構造のビットパターンを示す図（その４）である。
【図３６】第５のインデックス構造のビットパターンを示す図（その５）である。
【図３７】第５のインデックス構造のビットパターンを示す図（その６）である。
【図３８】キーとインデックス構造を示す図である。
【図３９】圧縮のされていないインデックスのサイズを示す図である。
【図４０】差分を用いたインデックス構造を示す図である。
【図４１】差分値の符号化例を示す図である。
【符号の説明】
【０１５０】
１  圧縮手段
２  格納手段
３  復元手段
４  元のデータ
５  圧縮されたデータ
１１  磁気ディスク装置
１２  フロッピーディスク駆動装置
１３  フロッピーディスク
１４  プリンタ
１５  ディスプレイ
１６  ＣＰＵ
１７  キーボード
１８  ポインティング・デバイス
１９  メインメモリ
２０  バス
２１  文書データベース
２２  インデックス
２３  インデックス作成プログラム
２４  検索エンジン
２５  文書表示プログラム
２６  ワーク領域
３１  ネットワーク接続装置
３２  外部の装置
【図１】
2005129071.tif 000006
【図２】
2005129071.tif 000007
【図３】
2005129071.tif 000008
【図４】
2005129071.tif 000009
【図５】
2005129071.tif 000010
【図６】
2005129071.tif 000011
【図７】
2005129071.tif 000012
【図８】
2005129071.tif 000013
【図９】
2005129071.tif 000014
【図１０】
2005129071.tif 000015
【図１１】
2005129071.tif 000016
【図１２】
2005129071.tif 000017
【図１３】
2005129071.tif 000018
【図１４】
2005129071.tif 000019
【図１５】
2005129071.tif 000020
【図１６】
2005129071.tif 000021
【図１７】
2005129071.tif 000022
【図１８】
2005129071.tif 000023
【図１９】
2005129071.tif 000024
【図２０】
2005129071.tif 000025
【図２１】
2005129071.tif 000026
【図２２】
2005129071.tif 000027
【図２３】
2005129071.tif 000028
【図２４】
2005129071.tif 000029
【図２５】
2005129071.tif 000030
【図２６】
2005129071.tif 000031
【図２７】
2005129071.tif 000032
【図２８】
2005129071.tif 000033
【図２９】
2005129071.tif 000034
【図３０】
2005129071.tif 000035
【図３１】
2005129071.tif 000036
【図３２】
2005129071.tif 000037
【図３３】
2005129071.tif 000038
【図３４】
2005129071.tif 000039
【図３５】
2005129071.tif 000040
【図３６】
2005129071.tif 000041
【図３７】
2005129071.tif 000042
【図３８】
2005129071.tif 000043
【図３９】
2005129071.tif 000044
【図４０】
2005129071.tif 000045
【図４１】
2005129071.tif 000046