(57)【要約】  同じ値の連続を含むデータの圧縮率を向上させる。  第１の符号化手段（１ａ）は、圧縮対象データ（４）における同じ値が連続する部分を、同じ値が連続する回数に符号化する。分解手段（１ｂ）は、同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解する。計算手段（１ｄ）は、分解して得られた各整数の生起確率を計算する。第２の符号化手段（１ｅ）は、生起確率が高い整数ほど短い符号となるように、各整数を符号化する。
2013140530.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
圧縮対象データにおける同じ値が連続する部分を、同じ値が連続する回数に符号化し、
同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解し、
分解して得られた各整数の生起確率を計算し、
生起確率が高い整数ほど短い符号となるように、各整数を符号化する、
処理を実行させるプログラム。
【請求項２】
前記整数群には、０および特定の整数の冪乗の値が属しており、
前記コンピュータに、
整数の符号化では、前記整数群に属する整数それぞれに対応する葉を有する符号化の木を用いて、符号化を行う、
処理を実行させることを特徴とする請求の範囲第１項記載のプログラム。
【請求項３】
前記圧縮対象データは、複数の文字それぞれが、文字列を含む複数のレコードそれぞれに存在するか否かを示す、文字ごとのビット列の集合であり、
前記コンピュータに、
前記複数の文字のそれぞれを、対応するビット列内における、文字が存在することを示すビット値の割合に応じて複数の集合のいずれかに分類し、
生起確率の計算では、集合ごとに、該集合に属する文字に対応するビット列から得られた整数における、前記整数群に属する整数それぞれの生起確率を計算し、
整数の符号化では、集合ごとに、該集合に属する文字に対応するビット列から得られた整数を、該集合に関して計算された生起確率に基づいて符号化する、
処理を実行させることを特徴とする請求の範囲第１項または第２項のいずれかに記載のプログラム。
【請求項４】
前記コンピュータに、
文字が存在することを示すビット値の割合が５割を超えているビット列に対応する文字と、文字が存在することを示すビット値の割合が５割未満のビット列に対応する文字との、いずれか一方の文字については、対応するビット列内のビット値を反転させ、
同じ値が連続する回数への符号化では、ビット値反転対象の文字については、反転後のビット値を用いて、圧縮対象データにおける同じ値の連続を、同じ値が連続する回数に符号化する、
処理を実行させることを特徴とする請求の範囲第３項記載のプログラム。
【請求項５】
コンピュータに、
圧縮対象データを圧縮して得られた圧縮符号列を取得し、
前記圧縮符号列では、予め定めた整数群に属する整数の和によって、同じ値が連続する回数が表され、生起確率が高い整数ほど短い符号に符号化されており、前記整数群に属する各整数と符号との対応関係を示す管理情報を取得し、
前記取得した管理情報に基づいて、前記取得した圧縮符号列内の符号を復号する、
処理を実行させるプログラム。
【請求項６】
前記コンピュータに、
整数と符号との対応関係を示す情報の取得では、根の直下に複数の葉が接続されており、根から遷移する葉が符号に応じて決められており、前記複数の葉それぞれに整数が設定された、符号化の木を取得し、
符号の復号では、前記取得した符号化の木に基づいて、前記取得した圧縮符号列内の符号を、該符号に対応する葉に設定された整数で示される回数だけ同じ値が連続するデータに復号する、
処理を実行させる請求の範囲第５項記載のプログラム。
【請求項７】
コンピュータが、
圧縮対象データにおける同じ値が連続する部分を、同じ値が連続する回数に符号化し、
同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解し、
分解して得られた各整数の生起確率を計算し、
生起確率が高い整数ほど短い符号となるように、各整数を符号化する、
ことを特徴とする圧縮データ生成方法。
【請求項８】
コンピュータが、
圧縮対象データを圧縮して得られた圧縮符号列を取得し、
前記圧縮符号列では、予め定めた整数群に属する整数の和によって、同じ値が連続する回数が表され、生起確率が高い整数ほど短い符号に符号化されており、前記整数群に属する各整数と符号との対応関係を示す管理情報を取得し、
前記取得した管理情報に基づいて、前記取得した圧縮符号列内の符号を復号する、
ことを特徴とする伸張方法。
【請求項９】
圧縮対象データにおける同じ値が連続する部分を、同じ値が連続する回数に符号化する第１の符号化手段と、
同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解する分解手段と、
分解して得られた各整数の生起確率を計算する計算手段と、
生起確率が高い整数ほど短い符号となるように、各整数を符号化する第２の符号化手段と、
を有する情報処理装置。
【請求項１０】
圧縮対象データを圧縮して得られた圧縮符号列を取得する第１の取得手段と、
前記圧縮符号列では、予め定めた整数群に属する整数の和によって、同じ値が連続する回数が表され、生起確率が高い整数ほど短い符号に符号化されており、前記整数群に属する各整数と符号との対応関係を示す管理情報を取得する第２の取得手段と、
前記取得した管理情報に基づいて、前記取得した圧縮符号列内の符号を復号する復号手段と、
を有する情報処理装置。
【請求項１１】
圧縮対象データを圧縮した圧縮データを記憶するコンピュータ読み取り可能な記録媒体において、
前記圧縮データには、予め定めた整数群に属する整数に対応する符号が含まれており、
整数は、前記圧縮対象データにおける同じ値が連続する部分を、同じ値が連続する回数に符号化し、同じ値が連続する回数を、前記整数群に属する整数の和に分解して得られたものであり、
符号は、分解して得られた整数において、生起確率が高い整数ほど短い符号となるように、各整数を符号化したものである、
ことを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビットマップを圧縮するプログラム、圧縮データ生成方法、伸張方法、情報処理装置、および記録媒体に関する。
【背景技術】
【０００２】
文書検索を高速化する技術の１つとして、ビットマップ型インデックスを用いる技術がある。インデックスは、例えば所定の文字コードで表現可能な各文字が、複数の文書それぞれに含まれているか否かを、ビットマップで表したものである。例えばビットマップでは、ある文字について、その文字を含む文書の文書番号の位置に「１」が設定され、その文字を含まない文書の文書番号の位置に「０」が設定される。これにより文字ごとに、「０」または「１」によって、各文書内でのその文字の存否を示すビット列が得られる。【０００３】
文字の存否を示すビット列をハフマン圧縮する技術がある。例えば、４ビット（１デジット）または、８ビット（１バイト）毎に、その出現頻度を集計し、４（または８）ビット毎に、エントロピー符号化を施すデータ圧縮装置が考えられている。【０００４】
また４ビットにより表現されるパターンをすべて網羅した１６種類の記号列と、４ビットよりもビット数が多い特殊記号列とを葉とする特殊なハフマン木を用いたビット列圧縮技術がある。【０００５】
一方、文字列を圧縮する、連長圧縮（ＲＬＥ：Run Length Encoding）技術を応用することにより、ビット列を圧縮できる。連長圧縮は、例えば連続した文字列のデータを、そのデータの文字と、データの連続回数（連長：Run Length）で表現するものである。データが「０」と「１」のように２種類だけであれば、一方のデータ（例えば「０」の連長と、他方のデータ（例えば「１」）の連長とを交互に並べることで、ビット列を表現できる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−２６０４０８号公報
【特許文献２】国際公開第２００８／１４６７５６号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、連続する同じ値を含むビットマップを、連長圧縮とエントロピー符号化を単に結合して圧縮しても、十分な圧縮効果が得られない場合がある。このような連続する同じ値は、例えば、日本語の漢字のビットマップの場合では値「０」である。例えば、連長圧縮において、同じ値の連続を示す数値が分散し、偏りが少ない場合がある。他方、エントロピー符号化は、圧縮元の符号の生起確率の偏りが大きい程、圧縮率が高くなる符号化方式である。そのため、連長圧縮して得られた符号に対して、そのままエントロピー符号化を行っても十分な圧縮効果が得られない場合がある。【０００８】
１つの側面では、本発明は、連続する同じ値を含むデータに対して、その圧縮率や伸長速度を向上させるプログラム、圧縮データ生成方法、伸張方法、情報処理装置、および記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００９】
１つの案では、コンピュータに、圧縮対象データにおける同じ値が連続する部分を、同じ値が連続する回数に符号化し、同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解し、分解して得られた各整数の生起確率を計算し、生起確率が高い整数ほど短い符号となるように、各整数を符号化する、処理を実行させるプログラムが提供される。
【発明の効果】
【００１０】
１態様によれば、同じ値の連続を含むデータの圧縮率が向上する。
本発明の上記および他の目的、特徴および利点は本発明の例として好ましい実施の形態を表す添付の図面と関連した以下の説明により明らかになるであろう。
【図面の簡単な説明】
【００１１】
【図１】第１の実施の形態に係る装置の機能構成例を示す図である。
【図２】第２の実施の形態のシステム構成例を示す図である。
【図３】第２の実施の形態に用いるＡＰサーバのハードウェアの一構成例を示す図である。
【図４】第２の実施の形態における各装置の機能の一例を示すブロック図である。
【図５】辞書データ記憶部のデータ構造の一例を示す図である。
【図６】クローラによるレコードの圧縮およびインデックス作成機能の一例を示す図である。
【図７】ビットマップのデータ構造の一例を示す図である。
【図８】ビット列の連長圧縮の一例を示す図である。
【図９】連長圧縮で符号化されるビット列の例を示す図である。
【図１０】記号とビット列との関係例を示す図である。
【図１１】符号化単位ビット列と記号列との関係例を示す図である。
【図１２】領域分割の一例を示す図である。
【図１３】インデックスの生成および圧縮処理の手順の一例を示すフローチャートである。
【図１４】ビットマップ生成処理の手順の一例を示すフローチャートである。
【図１５】非圧縮のビットマップの一例を示す図である。
【図１６】連長圧縮処理の手順の一例を示すフローチャートである。
【図１７】連長圧縮後のインデックスの一例を示す図である。
【図１８】ハフマン符号化処理の手順の一例を示す図である。
【図１９】ハフマン木の第１の例を示す図である。
【図２０】記号に対応する圧縮符号の第１の例を示す図である。
【図２１】ハフマン木の第２の例を示す図である。
【図２２】記号に対応する圧縮符号の第２の例を示す図である。
【図２３】圧縮形式のインデックスの例を示す図である。
【図２４】全文検索処理の手順の一例を示すフローチャートである。
【図２５】無節点の木の一例を示す図である。
【図２６】Ａ領域の圧縮結果の一例を示す図である。
【図２７】Ｂ領域の圧縮結果の一例を示す図である。
【図２８】Ｃ領域の圧縮結果の一例を示す図である。
【図２９】Ｄ領域の圧縮結果の一例を示す図である。
【図３０】Ｅ領域の圧縮結果の一例を示す図である。
【図３１】Ｆ領域の圧縮結果の一例を示す図である。
【図３２】Ｇ領域の圧縮結果の一例を示す図である。
【図３３】Ｈ領域の圧縮結果の一例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本実施の形態について図面を参照して説明する。なお各実施の形態は、矛盾のない範囲で複数の実施の形態を組み合わせて実施することができる。
〔第１の実施の形態〕
まず第１の実施の形態について説明する。第１の実施の形態は、同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解し、生起確率が高い整数ほど短い符号となるように、整数を符号化するようにしたものである。このような符号化方式により、同じ値が連続する回数の生起確率よりも、整数の生起確率の方が高くなり、短い符号に符号化できる割合が高くなる。その結果、圧縮率が向上する。
【００１３】
図１は、第１の実施の形態に係る装置の機能構成例を示す図である。第１の実施の形態は、圧縮手段１、記録媒体２、および伸張手段３を有する。
圧縮手段１は、圧縮対象データ４を圧縮する。記録媒体２は、コンピュータで読み取り可能であり、圧縮対象データ４を圧縮した圧縮データ２ａを記憶する。伸張手段３は、圧縮データ２ａを伸張する。圧縮対象データ４は、例えば、複数の文字それぞれが、文字列を含む複数のレコードそれぞれに存在するか否かを示すビット列の集合からなるビットマップである。
【００１４】
圧縮手段１は、第１の符号化手段１ａ、分解手段１ｂ、分類手段１ｃ、計算手段１ｄ、および第２の符号化手段１ｅを有する。
第１の符号化手段１ａは、圧縮対象データ４における同じ値が連続する部分を、同じ値が連続する回数に符号化する。このような符号化は、連長圧縮と呼ばれる。例えば圧縮対象データ４が「０」と「１」とのビット列からなるビットマップであり、「０」の生起確率が「１」の生起確率より十分に高い場合、「０」が連続する回数が符号化される。この場合、先頭が「１」の場合、「０」が連続する回数が、０回であると表される。
【００１５】
分解手段１ｂは、同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解する。例えば同じ値が連続する回数を、０および２の冪乗の値の和に分解することができる。その場合、「０」の連続回数が「０」、「１」、「２」の場合には、これ以上分解できずに、そのままの値が用いられる。「０」の連続回数が「３」であれば、「１＋２」に分解することができる。
【００１６】
分類手段１ｃは、圧縮対象データ４が、文字の存否を示すビット列の集合の場合に、文字を分類する。例えば分類手段１ｃは、複数の文字のそれぞれを、対応するビット列内における、文字が存在することを示すビット値の割合に応じて複数の集合のいずれかに分類する。例えば分類手段１ｃは、レコードに文字が存在するときに、その文字のビット列内の該当レコードに対応するビットに「１」が設定される場合、ビット列内の全ビット数における値が「１」のビットの数に応じて、文字を分類する。
【００１７】
計算手段１ｄは、分解して得られた各整数の生起確率を計算する。なお計算手段１ｄは、文字が複数の集合に分類された場合、集合ごとに、該集合に属する文字に対応するビット列から得られた整数における、整数群に属する整数それぞれの生起確率を計算する。
【００１８】
第２の符号化手段１ｅは、生起確率が高い整数ほど短い符号となるように、各整数を符号化する。このような符号化技術は、例えばエントロピー符号化と呼ばれる。例えば第２の符号化手段１ｅは、ハフマン符号化により、圧縮対象データ４内のビット列をハフマン符号に符号化する。
【００１９】
なお第２の符号化手段１ｅは、文字が複数の集合に分類された場合、集合ごとに符号化を行うことができる。例えば第２の符号化手段１ｅは、集合ごとに、その集合に属する文字に対応するビット列から得られた整数を、その集合に関して計算された生起確率に基づいて符号化する。
【００２０】
第２の符号化手段１ｅは、例えば、符号化により生成した符号の、文字ごとの配列（圧縮符号列）の集合を、圧縮データ２ａとして記録媒体２に格納する。なお圧縮データ２ａには、例えば、文字に対応付けて、その文字が属する集合と、圧縮符号列とが設定される。
【００２１】
また第２の符号化手段１ｅは、記録媒体２に、管理情報２ｂを格納することもできる。管理情報２ｂは、整数と符号との対応関係を示す情報である。整数と符号との対応関係は、例えばハフマン木などの符号化の木で表すことができる。また集合ごとに符号化を行った場合、第２の符号化手段１ｅは、整数と符号との対応関係を、集合ごとに示した管理情報２ｂを、記録媒体２に格納することができる。
【００２２】
記録媒体２は、例えば圧縮対象データ４を圧縮して得られた圧縮データ２ａを記憶する。圧縮データ２ａには、整数群に属する整数のいずれかに対応する符号が含まれている。また記録媒体２には、管理情報２ｂを記録することもできる。
【００２３】
伸張手段３は、第１の取得手段３ａ、第２の取得手段３ｂ、および復号手段３ｃを有する。
第１の取得手段３ａは、圧縮対象データ４を符号化した圧縮符号列を取得する。例えば第１の取得手段３ａは、検索文字列が入力された場合に、検索文字列に含まれる文字それぞれに対応する圧縮符号列を、記録媒体２に格納されている圧縮データ２ａから取得する。
【００２４】
第２の取得手段３ｂは、整数群に属する整数と符号との対応関係を示す管理情報２ｂを取得する。例えば第２の取得手段３ｂは、記録媒体２から、管理情報２ｂを読み出す。第１の取得手段３ａが検索文字列に含まれる文字の圧縮符号列を取得した場合、第２の取得手段３ｂは、管理情報２ｂから、検索文字列に含まれる各文字が属する集合における、整数と符号との対応関係の情報を取得する。
【００２５】
復号手段３ｃは、取得した管理情報に基づいて、取得した圧縮符号列内の符号を復号する。例えば復号手段３ｃは、取得した圧縮符号列を先頭から順に読み出す。次に復号手段３ｃは、読み出した圧縮符号列の値に対応する符号を、取得した管理情報から検索する。該当する符号がある場合、復号手段３ｃは、圧縮符号列の先頭の該当符号に合致する部分を、その符号に対応する整数で示される回数の、同じ値の連続に変換する。復号手段３ｃは、このような変換を、取得した圧縮符号列全体に対して実行する。これにより、圧縮符号列が復号される。
【００２６】
このようなシステムにおいて、例えば圧縮対象データ４が文字ごとのビット列の集合の場合、第１の符号化手段１ａにより、ビット列が、「０」のビット値の連続回数に符号化される。次に、分解手段１ｂにより、０の連続回数が、整数の和に分解される。例えば、整数群に「０」と２の冪乗の値が含まれる場合、０の連続回数が、「０，１，２，４，８，・・・」という整数群の和に分解される。
【００２７】
また、分類手段１ｃによって、文字を複数の集合に分類することもできる。文字の分類では、例えば、文字「あ」が存在するレコードの割合と、文字「う」が存在するレコードの割合とが近い場合、文字「あ」と文字「う」とは、同じ集合「Ａ」に分類される。
【００２８】
その後、計算手段１ｄにより、整数ごとの生起確率が計算される。図１の例では、集合「Ａ」に属する文字における整数「０」の生起確率は「ａ１」、整数「１」の生起確率は「ａ２」、整数「２」の生起確率は「ａ３」、整数「４」の生起確率は「ａ４」となっている。このとき各生起確率の大小関係は、ａ４＞ａ３＞ａ２＞ａ１であるものとする。
【００２９】
第２の符号化手段１ｅは、生起確率が高い整数ほど、短い符号を割り当て、圧縮対象データ４内のビット列の符号化を行う。例えば図１の例では、集合「Ａ」に関し、整数「０」の符号は「１１０」（符号長３）、整数「１」の符号は「１０」（符号長２）、整数「２」の符号は「０」（符号長１）であるものとする。すると、文字「あ」の先頭のビット「１」は、符号「１１０」に変換される。また、文字「う」の先頭のビット列「００００」は、符号「０」に変換される。
【００３０】
圧縮手段１で生成された圧縮データ２ａや管理情報２ｂは、記録媒体２に格納される。そして、例えば伸張手段３に検索文字列が入力されると、第１の取得手段３ａにより、検索文字列に含まれる文字に対応する圧縮符号列が、圧縮データ２ａから抽出される。また第２の取得手段３ｂにより、抽出した文字が属する集合に対応する管理情報が取得される。そして復号手段３ｃにより、圧縮符号列が復号される。例えば図１の例では、集合「Ａ」に属する文字「あ」の先頭の「１１０」の圧縮符号が、ビット列「１」に復号される。また集合「Ａ」に属する文字「う」の先頭の「０」の圧縮符号が、ビット列「００００」に復号される。
【００３１】
このようにして、圧縮対象データ４の圧縮と伸張が可能となる。なお図１の例では、整数「４」については、ビット列「００００」を表しており、符号化後のビット長が「１」である。従って、符号化によって圧縮されている。他方、整数「０」については、ビット列の「１」が「１１０」に符号化され、符号化後の方がビット長が長くなってしまう。ただし、整数「０」の生起確率は、他の整数に比べて低いため、圧縮データ２ａ全体の圧縮率に対する悪影響は少ない。その結果、圧縮対象データ４よりも少ないデータ容量の圧縮データ２ａを得ることができる。
【００３２】
しかも、第１の実施の形態では、同じ値が連続する回数を、整数の和に分解している。そのため、同じ値が連続する回数の生起確率よりも、整数群に属する整数の生起確率の方が高くなる。ハフマン符号化のような、生起確率が高いほど短い符号に符号化する符号化方式では、符号化対象の値の偏りが大きい方が、圧縮率が高くなる。従って、同じ値が連続する回数を整数群の和に分解して、整数に符号を割り当てることで、圧縮率を向上させることができる。
【００３３】
また、このような圧縮処理は、「０」と「１」との出現率の偏りが大きいビットマップの圧縮に特に有効である。例えば、インデックスを用いた辞書検索を高速化する場合を考える。辞書検索では、辞書データを複数のレコードに分割し、各レコードを圧縮して格納しておく。そして検索文字列が入力されると、インデックスを用いて検索文字列に含まれる文字が出現するレコードを特定し、特定したレコードを伸張する。このとき、辞書データを非常に細かく分割し、１つのレコードのサイズを小さくすれば、そのレコードを伸張する先の処理量を減らすことができる。他方、辞書データを細かく分割すると、レコード数が膨大となる。このような場合、１つのレコード当たりのサイズが小さいため、圧縮対象データ４を作成すると、各レコードに対応する各ビットの値は、ほとんどが「０」となる。特に日本語の場合、使用頻度の低い漢字が多数存在し、そのような漢字のビット列には、「１」はほとんど含まれないこととなる。このような圧縮対象データ４は、０が多数連続する０の連続回数の出現頻度が高い。そのため、第１の実施の形態に示す技術で圧縮対象データ４を圧縮することで、高い圧縮率を得ることが可能となる。
【００３４】
しかも、文字を、対応するビット列内における、文字が存在することを示すビット値の割合に応じて複数の集合のいずれかに分類することで、各文字のビット列を、文字が存在することを示すビット値の割合に応じた、適切な符号に圧縮することが可能である。その結果、圧縮率がさらに向上する。
【００３５】
なお、圧縮手段１、伸張手段３は、情報処理装置が有するＣＰＵ（Central Processing Unit）により実現することができる。また、記録媒体２は、光ディスクなどの可搬型記録媒体、情報処理装置が有するＲＡＭ（Random Access Memory）、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）などにより実現することができる。
【００３６】
また、図１に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。
〔第２の実施の形態〕
次に第２の実施の形態について説明する。第２の実施の形態は、辞書データのインデックスを圧縮するものである。以下、第２の実施の形態について詳細に説明する。
【００３７】
図２は、第２の実施の形態のシステム構成例を示す図である。第２の実施の形態では、ネットワーク１０を介して、例えばＡＰサーバ１００、ＤＢサーバ２００、および端末装置２１が接続されている。ＤＢサーバ２００は、辞書データなど情報を格納したデータベースを有している。ＡＰサーバ１００は、端末装置２１からの要求に応じて、ＤＢサーバ２００に格納されている情報を検索し、検索結果を端末装置２１に送信する。端末装置２１は、ユーザの操作に応じて、ＡＰサーバ１００に検索要求を送信し、ＡＰサーバ１００から送られた検索結果をモニタに表示する。
【００３８】
図３は、第２の実施の形態に用いるＡＰサーバのハードウェアの一構成例を示す図である。ＡＰサーバ１００は、ＣＰＵ１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０８を介してＲＡＭ１０２と複数の周辺機器が接続されている。なおＡＰサーバ１００が有するＣＰＵ数は１つに限定されず、複数であってもよい。ＡＰサーバ１００が複数のＣＰＵを有する場合、複数のＣＰＵが連係動作し、装置全体を制御する。
【００３９】
ＲＡＭ１０２は、ＡＰサーバ１００の主記憶装置として使用される。ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。
【００４０】
バス１０８に接続されている周辺機器としては、ＨＤＤ１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、および通信インタフェース１０７がある。
【００４１】
ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、ＡＰサーバ１００の二次記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。
【００４２】
グラフィック処理装置１０４には、モニタ１１が接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１１の画面に表示させる。モニタ１１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００４３】
入力インタフェース１０５には、キーボード１２とマウス１３とが接続されている。入力インタフェース１０５は、キーボード１２やマウス１３から送られてくる信号をＣＰＵ１０１に送信する。なお、マウス１３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００４４】
光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク１４に記録されたデータの読み取りを行う。光ディスク１４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク１４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００４５】
通信インタフェース１０７は、ネットワーク１０に接続されている。通信インタフェース１０７は、ネットワーク１０を介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００４６】
以上のようなハードウェア構成によって、第２の実施の形態の処理機能を実現することができる。なお図３にはＡＰサーバ１００のハードウェア構成例を示したが、ＤＢサーバ２００や端末装置２１もＡＰサーバ１００と同様のハードウェアで実現することができる。また、第１の実施の形態に示した情報処理装置も、図３に示したＡＰサーバと同様のハードウェアにより実現することができる。
【００４７】
図４は、第２の実施の形態における各装置の機能の一例を示すブロック図である。ＤＢサーバ２００は、辞書データ記憶部２１０とＤＢ管理部２２０とを有している。
辞書データ記憶部２１０は、国語辞典、英和辞典、和英辞典などの辞書データを記憶している。例えばＤＢサーバ２００のＨＤＤの記憶領域の一部が、辞書データ記憶部２１０として使用される。なお辞書データは、複数のレコードで構成される。例えば、辞書データに項目ごとのレコードが設けられる。
【００４８】
ＤＢ管理部２２０は、辞書データ記憶部２１０に格納されたデータを管理する。例えばＤＢ管理部２２０は、ＡＰサーバ１００からの要求に応じて辞書データ記憶部２１０内のデータを読み出し、ＡＰサーバ１００に送信する。
【００４９】
ＡＰサーバ１００は、ＤＢエージェント１１０、クローラ１２０、サーチャ１３０、インデックス記憶部１４０、および圧縮データ記憶部１５０を有している。
ＤＢエージェント１１０は、ＤＢサーバ２００に対して、辞書データ記憶部２１０の操作要求を行う。例えばＤＢエージェント１１０は、クローラ１２０またはサーチャ１３０からの要求に応じて、ＤＢサーバ２００に対して、辞書データ記憶部２１０内のレコードの取得要求を送信する。この場合、ＤＢエージェント１１０は、ＤＢサーバ２００から応答されたレコードを、クローラ１２０またはサーチャ１３０に送信する。
【００５０】
クローラ１２０は、ＤＢエージェント１１０を介してＤＢサーバ２００からレコードを取得し、辞書データ記憶部２１０に格納されているレコードのインデックスを作成する。作成されるインデックスは、辞書データ記憶部２１０内の複数のレコードそれぞれにおける、各種の文字の存否をビットマップ形式で示した情報である。クローラ１２０は、作成したインデックスを、インデックス記憶部１４０に格納する。
【００５１】
またクローラ１２０は、取得したレコードを圧縮して、圧縮データ記憶部１５０に格納することもできる。これにより、圧縮データ記憶部１５０内に、辞書データのアーカイブ（書庫）が構築される。
【００５２】
サーチャ１３０は、端末装置２１からの検索要求に応じて、辞書データ記憶部２１０内のデータを検索する。例えばサーチャ１３０は、端末装置２１から検索要求を受信すると、インデックス記憶部１４０に格納されているインデックスに基づいて、検索要求に示されている文字列を構成する文字が、それぞれ少なくとも１回出現するレコードを特定する。次にサーチャ１３０は、ＤＢエージェント１１０を介して、特定したレコードをＤＢサーバ２００から取得する。サーチャ１３０は、取得したレコードを、圧縮データ記憶部１５０に格納する。そしてサーチャ１３０は、圧縮データ記憶部１５０に格納したレコードから、検索要求に示される文字列を検索し、その文字列を含むレコードのリストを、検索結果として端末装置２１に送信する。
【００５３】
インデックス記憶部１４０は、クローラ１２０により、辞書データ記憶部２１０に格納されたレコードをもとに作成されたインデックスが記憶される。例えばＨＤＤ１０３の記憶領域の一部がインデックス記憶部１４０として使用される。
【００５４】
圧縮データ記憶部１５０は、クローラ１２０により取得されたレコードが圧縮されて記憶される。例えば、ＨＤＤ１０３の記憶領域の一部が圧縮データ記憶部１５０として使用される。
【００５５】
このような構成のシステムにより、ビットマップ形式のインデックスの作成、およびインデックスを用いた情報検索が行われる。
なお、図４に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。
【００５６】
次に、辞書データ記憶部２１０に格納されているレコードについて詳しく説明する。
図５は、辞書データ記憶部のデータ構造の一例を示す図である。図５の例では、辞書データ記憶部２１０には、第１の辞書データ３０と第２の辞書データ４０とを統合した、統合辞書データ５０が格納されている。
【００５７】
第１の辞書データ３０は、項目ごとに分けられた複数のレコード３１，３２，３３，・・・で構成される。各レコード３１，３２，３３，・・・には、第１の辞書データ３０内で各レコードを一意に識別するためのＩＤ（ローカルＩＤ）、項目の見出し、および項目の本文などが含まれる。
【００５８】
第２の辞書データ４０は、項目ごとに分けられた複数のレコード４１，４２，４３，・・・で構成される。各レコード４１，４２，４３，・・・には、第２の辞書データ４０内で各レコードを一意に識別するためのＩＤ（ローカルＩＤ）、項目の見出し、および項目の本文などが含まれる。
【００５９】
辞書データ記憶部２１０に格納された統合辞書データ５０は、複数のレコード５１，５２，５３，・・・で構成される。複数のレコード５１，５２，５３，・・・は、例えば、第１の辞書データ３０のレコード３１，３２，３３，・・・、および第２の辞書データ４０のレコード４１，４２，４３，・・・をコピーし、ＩＤを変更することによって生成される。各レコード５１，５２，５３，・・・には、グローバルＩＤ（Ｇ−ＩＤ）、辞書ＩＤ（Ｄ−ＩＤ）、ローカルＩＤ（Ｌ−ＩＤ）、項目の見出し、および項目の本文などが含まれる。グローバルＩＤは、統合辞書データ５０内で各レコードを識別するためのＩＤである。辞書ＩＤは、複写元となった辞書データを識別するためのＩＤである。ローカルＩＤは、複写元の辞書データ内での複写元のレコードのＩＤである。
【００６０】
第１の辞書データ３０と第２の辞書データ４０とから統合辞書データ５０を作成する場合、第１の辞書データ３０と第２の辞書データ４０から複製したレコードに、グローバルＩＤと辞書ＩＤとが付与される。グローバルＩＤとしては、例えばシーケンシャルな番号が用いられる。なお統合辞書データ５０の作成は、例えばＤＢ管理部２２０が行う。また他のコンピュータで作成した統合辞書データ５０を、ＤＢサーバ２００に格納してもよい。
【００６１】
次に、統合辞書データ５０内の各レコードの圧縮、およびインデックス作成処理について説明する。レコードの圧縮、およびインデックス作成処理は、クローラ１２０で行われる。
【００６２】
図６は、クローラによるレコードの圧縮およびインデックス作成機能の一例を示す図である。クローラ１２０は、ワークメモリ１６０を用いて、レコード５１，５２，５３，・・・の圧縮と、レコード５１，５２，５３，・・・それぞれにおける文字の存否を示すビットマップを生成する。この処理を実行するため、クローラ１２０は、文書圧縮部１２１とインデックス生成部１２２とを有している。なお、ワークメモリ１６０としては、例えばＲＡＭ１０２内の記憶領域の一部が使用される。
【００６３】
文書圧縮部１２１は、ＤＢサーバ２００から取得したレコード５１，５２，５３，・・・を圧縮する。例えば、文書圧縮部１２１は、例えばハフマン符号化、スライド辞書法などのさまざまな符号化方式を組み合わせて、レコード５１，５２，５３，・・・を圧縮することができる。文書圧縮部１２１は、レコード５１，５２，５３，・・・それぞれ内の文字列を順次符号化し、圧縮結果をワークメモリ１６０に格納する。レコード５１，５２，５３，・・・内のすべての文字列が符号化されると、ワークメモリ１６０内に圧縮文書１６１が生成される。そして文書圧縮部１２１は、圧縮文書１６１を、圧縮データ記憶部１５０内の圧縮データ１５１に追加する。
【００６４】
インデックス生成部１２２は、レコード５１，５２，５３，・・・を解析し、例えば所定の文字コードで表されるすべての文字について、レコード５１，５２，５３，・・・内に出現するか否かを判断する。インデックス生成部１２２は、１文字の存否を判断することに、その存否を示す１ビットの値を、ワークメモリ１６０に格納する。所定の文字コードで表されるすべての文字の存否の判断が終了すると、ワークメモリ１６０内に追加ビットマップ１６２が生成される。この段階では、追加ビットマップ１６２は非圧縮の状態である。
【００６５】
インデックス生成部１２２は、生成した追加ビットマップ１６２をインデックス記憶部１４０に格納する。次にインデックス生成部１２２は、インデックス記憶部１４０に格納した追加分のビットマップ１４２を圧縮し、インデックス記憶部１４０内のインデックス１４１に追加する。
【００６６】
またインデックス生成部１２２は、追加ビットマップ１６２に関する管理情報１６３を生成し、ワークメモリ１６０に格納する。管理情報１６３には、インデックス１４１を用いた検索処理に用いられる各種情報が格納される。例えば第２の実施の形態では、インデックス生成部１２２は、ビットマップ１４２を圧縮する際に、文字の出現頻度を表す０〜１の数値の範囲を複数の領域に分割する。そしてインデックス生成部１２２は、各文字のレコードに対する出現頻度に応じて、文字が属する領域を決定する。そこでインデックス生成部１２２は、例えば管理情報１６３に、例えば文字の出現頻度、または文字が属する領域の情報を格納する。これにより、インデックス１４１の伸張の際には、管理情報１６３に基づいて、各文字の属する領域が判断できる。インデックス生成部１２２は、ワークメモリ１６０内に生成した管理情報１６３を、インデックス記憶部１４０に格納する。これによりインデックス記憶部１４０内に管理情報１４３が記憶される。
【００６７】
次に、統合辞書データ５０に基づいて作成された、圧縮前のビットマップ１４２について説明する。
図７は、ビットマップのデータ構造の一例を示す図である。インデックス記憶部１４０には、圧縮前のビットマップ１４２が格納されている。ビットマップ１４２は、文字に対応するビット列６１，６２，６３，・・・の集合である。ビット列６１，６２，６３，・・・は、統合辞書データ５０内のレコードの数分のビットの配列である。例えば、統合辞書データ５０内のレコードがｎ個（ｎは、１以上の整数）であれば、１つにビット列のビット数はｎである。
【００６８】
図７の例では、ビット列６１，６２，６３，・・・内の各ビットは、左から順に、「１」から昇順のグローバルＩＤに対応付けられている。例えば、左端のビットにグローバルＩＤ「１」に対応付けられ、右端のビットはグローバルＩＤ「ｎ」に対応付けられている。
【００６９】
ビット列６１，６２，６３，・・・内の各ビットは、ビット列に対応する文字が、統合辞書データ５０内の対応するグローバルＩＤで示されるレコードに、少なくとも１回出現するか否かを示している。例えば、ビット列に対応する文字が、レコード内に少なくとも１回出現した場合、そのレコードのグローバルＩＤに対応するビットに「１」が設定される。またビット列に対応する文字が、レコード内に１度も出現しない場合、そのレコードのグローバルＩＤに対応するビットに「０」が設定される。
【００７０】
このようなビットマップ１４２が圧縮され、インデックス１４１が生成される。ビットマップ１４２を圧縮する場合、まず、ビットマップ１４２に含まれるビット列６１，６２，６３，・・・の連長圧縮が行われる。
【００７１】
ここで、文字列に関する連長圧縮について説明する。連長圧縮では、ある連続したデータを、そのデータ１つ分と連続した長さで表現する。例えば、文字列「ＡＡＡＡＡＢＢＢＢＢＢＢＢＢＡＡＡ」は「Ａ５Ｂ９Ａ３」と表せる。これは、Ａが５回続き、そのあとにＢが９回、そしてＡが３回続いていることを表している。なお、連続回数を、元のデータを表す符号の前に記録することもある。その場合、符号化した後は「５Ａ９Ｂ３Ａ」と表される。
【００７２】
さらに、データがこの２種類（ＡとＢ）だけで、最初にＡが来ることにしておけば、「５９３」だけで表せる。このルールに従ったときにＢが最初に見つかった場合は、最初にＡが０回連続していることにすればよい。例えば、「ＢＢＢＡＡＡＡＡＢＢＢＢＢＡＡＡ」は「０３５５３」で表せることになる。
【００７３】
各レコード内での文字の存否を示すビットマップ１４２は、対象のファイルやレコードに、該当する文字や基礎単語が含まれるか、否かを「１」（ＯＮ）と「０」（ＯＦＦ）にて表現し、無記憶情報源に属するデータである。なお無記憶情報源とは、各データが他のデータに依存せずに独立に発生する情報源である。
【００７４】
日本語に関して、国語辞典を例にすると、約２０〜３０項目を１ファイルに格納した場合、日本語の漢字の平均的な出現頻度は１／１３であり、以下のように、「０」が連続し、「１」が単一である場合が多い。そこで、第２の実施の形態では、ビットマップ１４２内のビット列を、連続する「０」と単一の「１」からなるビット列（符号化単位ビット列）に分解し、分解して得られた符号化単位ビット列ごとに連長圧縮を行う。これにより、より短い符号に圧縮可能となる。
【００７５】
図８は、ビット列の連長圧縮の一例を示す図である。図８には「森鴎外」の文字列を構成する各文字のビット列６１，６２，６３の例を示している。図８に示すように、ビット列６１，６２，６３では、対応する文字が、ビット位置に対応するレコードに出現する場合、そのビットの値が「１」となり、出現しない場合、そのビットの値が「０」となる。
【００７６】
このようなビット列６１，６２，６３が、連長圧縮される。例えば、「外」の文字のビット列６３は、「００００００００１０００００１０・・・・・・・・・１００００１００」である。なお最後の２つの「０」は、終端を示す記号である。このビット列６３では、最初に「０」が８個続き、その後、１つの「１」を挟んで０が５回続いている。また終端の直前は、「１」の後に「０」が４回続き、最後が「１」となっている。この場合、「８５・・・４［ＥＯＢ］」（［ＥＯＢ］は終端を示す記号）という符号に圧縮できる。
【００７７】
ビット列６１，６２，６３，・・・を圧縮して得られた連長符号をハフマン符号化することで、さらに圧縮率を高めることができる。なお、ハフマン符号化は、生起確率が高いほど短い符号に符号化する符号化技術の一例である。
【００７８】
図９は、連長圧縮で符号化されるビット列の例を示す図である。図９の例では、「０」が連続する数を連長（ランレングス）とし、連長ごとの符号化単位ビット列、生起確率、ビット長、および残確率を示している。生起確率は、「０」と「１」との発生がランダム（同じ確率で発生）の場合に、連長に対応する符号化単位ビット列が出現する確率である。ビット長は、生起確率に基づいて、符号化単位ビット列をハフマン木により符号化した場合の符号の長さ（ビット数）である。残確率は、対応する連長よりも連長が多い符号化単位ビット列の生起確率である。例えば、連長「０」の生起確率は「１／２」であるため、その連長より多い連長（１以上）の符号化単位ビット列の生起確率は、「１／２」（＝１−１／２）となる。従って連長「０」の残確率は「１／２」となる。
【００７９】
図９に示すように、ビットの値がランダムに発生する場合、ビット長が短いほど生起確率が高い。またハフマン符号化は、生起確率が高いビット列（系列）ほど、短い符号に符号化する符号化方式である。すると、ビットの値がランダムに出現する場合には、もともと短いビット長のビット列に、短い符号が割り当てられることとなり、圧縮の効果はあまり期待できない。
【００８０】
他方、例えば「０」または「１」の密度が低下した場合に圧縮の効果が期待できる。すなわち、連長が多い符号化単位ビット列の生起確率が、連長が小さい符号化単位ビット列より高ければ、ハフマン符号化により、連長が多い符号化単位ビット列が、短い符号に符号化される。その結果、全体としての圧縮率が向上する。
【００８１】
日本語には、一般的に６〜８千種の文字が存在する。そのうち、高頻度な文字は、かな、カタカナ、英数字、および教育漢字の約千種である。国語辞書において、１万の項目のうち、１または２つの項目にしか出現しない文字が多数存在する。従って、符号化単位ビット列の連長の種類は数千にのぼる。このままハフマン木を生成すると、ハフマン木の葉の数が数千となる。ハフマン木の葉の数が多くなるほど、ハフマン木を生成する際の計算量は指数関数的に増大するため、低速ＣＰＵや小容量のメモリで構成される省資源のハード環境での実装は、極めて困難である。
【００８２】
そこで、第２の実施の形態では、所定の整数群に含まれる整数の組み合わせで、０が連続する長さ（連長）を表す。例えば、「０」と、ある整数の冪乗の値との組み合わせで連長を表すことができる。
【００８３】
２の冪乗の数の和によって、「０」が連続する長さを表す場合、冪乗の指数の値を、連長に対応する記号とする。また、第２の実施の形態では、連続する「０」と、連続する「０」の次に出現する「１」とをまとめて、符号化単位ビット列とする。このような符号化単位ビット列を符号化する場合、「１」を含む記号を用意しておくこととなる。例えば、連続する「１」に対応する記号を「α」、「０１」に対応する記号を「β」とする。「α」は、「０」の連続回数が０回であることを意味している。「β」は、「０」の連続回数が１回（２の０乗）であることを意味している。
【００８４】
符号化単位ビット列は、整数群に属する整数に対応するビット列パターンに分解できる。以下に、整数群に属する整数を示す記号とビット列パターンとの関係について図１０を参照して説明する。
【００８５】
図１０は、記号とビット列との関係例を示す図である。図１０に示すように、記号「α」で示される「０」の数は「０」であり、符号化単位ビット列内のビット列パターン「１」に対応する。この記号「α」は、符号化単位ビット列の終端を表している。
【００８６】
記号「β」で示される「０」の数は「１」であり、符号化単位ビット列内のビット列パターン「０１」に対応する。この記号「β」は、符号化単位ビット列の終端を表している。
【００８７】
記号「１」で示される「０」の数は「２」であり、この数を２の冪乗で表すと２の１乗となる。この記号「１」は、符号化単位ビット列のうちのビット列パターン「００」に対応する。この記号「１」は、符号化単位ビット列の終端以外である。図１０では、ビット列パターン「００」の後に、他のビット列パターンが続くことを表す記号「＋」が示されている。
【００８８】
記号「２」で示される「０」の数は「４」であり、この数を２の冪乗で表すと２の２乗となる。この記号「２」は、符号化単位ビット列のうちのビット列パターン「００００」に対応する。この記号「２」は、符号化単位ビット列の終端以外である。図１０では、ビット列パターン「００」の後に、他のビット列パターンが続くことを表す記号「＋」が示されている。
【００８９】
以下同様に、記号の値が１増加するごとに、ビット列パターンの「０」の数は、２倍になる。
図１０に示すような記号を定義すると、符号化単位ビット列をビット列パターンに分解し、符号化単位ビット列に含まれるビット列パターンを１以上の記号の組み合わせ（記号列）で表すことができる。
【００９０】
図１１は、符号化単位ビット列と記号列との関係例を示す図である。なお図１１では、連長ごとの、符号化単位ビット列、記号列、生起確率、ビット長、残確率を示している。なお、生起確率は、「０」と「１」とがランダムに出現する場合の、符号化単位ビット列の生起確率である。ビット長は、符号化単位ビット列のビット長である。残確率は、対応する連長よりも連長が多い符号化単位ビット列の存在確率である。
【００９１】
連長が「０」の符号化単位ビット列「１」は、記号列「α」に対応する。連長が「１」の符号化単位ビット列「０１」は、記号列「β」に対応する。連長が「２」の符号化単位ビット列「００１」は、記号列「１α」に対応する。連長が「３」の符号化単位ビット列「０００１」は、記号列「１β」に対応する。連長が「４」の符号化単位ビット列「００００１」は、記号列「２α」に対応する。以降、符号化単位ビット列の連続する「０」の数がいくつであっても、図１０に示した記号を組み合わせた記号列で表すことができる。
【００９２】
このように、ビットマップ中の符号化単位ビット列を、対応する記号列に変換すると、連長圧縮に用いる記号の数を少なくすることにより、省資源なハードウェア環境でも、実装が可能となる。
【００９３】
例えば、統合辞書データ５０内のレコード数が約１万の場合、ビットマップにおける各文字のビット列の長さも約１万である。この場合、最大で８１９２の連長に対応する記号が用意されていれば、すべての符号化単位ビット列を、記号列に変換できる。すると、約１０Ｋビットのビットマップを構成する符号化単位ビット列は、わずか１５（２＋１３）種の記号の組み合わせで表現することができる。
【００９４】
連長圧縮で符号化された記号列をハフマン符号化で圧縮する場合、各記号が、ハフマン木の葉に割り当てられる。すると、連長をハフマン木の葉に割り当てた場合に比べて、ハフマン木の葉の数を数千から１５に激減させることができ、ハフマン木のサイズ縮小や生成時間の短縮が図れる。
【００９５】
ハフマン木のサイズが小さくなり、生成時間が短縮されれば、文字を出現頻度で分類し、出現頻度に応じたハフマン木を生成することも容易となる。例えば第２の実施の形態では、文字の出現率を表す数値の範囲「０〜１」を、１０の領域に分割する。
【００９６】
図１２は、領域分割の一例を示す図である。図１２の例では、「１」の出現率が０以上１／３２（０．０３１）未満の範囲が、Ｅ領域である。「１」の出現率が１／３２（０．０３１）以上１／１６（０．０６３）未満の範囲が、Ｄ領域である。「１」の出現率が１／１６（０．０６３）以上１／８（０．１２５）未満の範囲が、Ｃ領域である。「１」の出現率が１／８（０．１２５）以上１／４（０．２５０）未満の範囲が、Ｂ領域である。「１」の出現率が１／４（０．２５０）以上１／２（０．５００）以下の範囲が、Ａ領域である。
【００９７】
さらに「１」の出現率が１／２（０．５００）より大きく３／４（０．７５０）以下の範囲が、Ａ’領域である。「１」の出現率が３／４（０．７５０）より大きく７／８（０．８７５）以下の範囲が、Ｂ’領域である。「１」の出現率が７／８（０．８７５）より大きく１５／１６（０．９３８）以下の範囲が、Ｃ’領域である。「１」の出現率が１５／１６（０．９３８）より大きく３１／３２（０．９６９）以下の範囲が、Ｄ’領域である。「１」の出現率が３１／３２（０．９６９）より大きく１．００以下の範囲が、Ｅ’領域である。
【００９８】
図１２に示した１０の領域は、０．５を対象点とした点対称の関係を有する。すなわち、０．５を中心として、Ａ’、Ｂ’、Ｃ’、Ｄ’、Ｅ’の各領域を１８０度回転させると、各領域はそれぞれＡ、Ｂ、Ｃ、Ｄ、Ｅの各領域に合致する。
【００９９】
Ａ’、Ｂ’、Ｃ’、Ｄ’、Ｅ’の各領域は、連長圧縮前のビット列の値を、反転させることで、０の出現確率が、対象関係にある領域と同じとなる。ビット列の値の反転とは、「０」のビットを「１」に、「１」のビットを「０」に変更する処理である。例えば、Ａ’領域に属する文字のビット列の値を反転すると、「０」の出現確率は１／４以上１／２以下となり、Ａ領域の０の出現確率と同じとなる。
【０１００】
そこで第２の実施の形態では、Ａ’、Ｂ’、Ｃ’、Ｄ’、Ｅ’に属する文字については、ビット列の値を反転させた後、連長圧縮を行う。そして、連長圧縮前に記号列は、対象関係にある領域と同じハフマン木を用いることで、効果的に圧縮可能である。なお、以下の説明では、０の出現確率が１／２より高い、Ａ’、Ｂ’、Ｃ’、Ｄ’、Ｅ’の各領域を総称して、反転領域と呼ぶこととする。
【０１０１】
Ａ領域は、符号化単位ビット列が「１」、「０１」のいずれかに集中する。すると連長圧縮で生成した記号は、「α」と「β」とが高頻度で出現し、他の記号の出現頻度は少ない。Ａ領域は、例えば記号「α」を１ビットで表し、記号「β」を２ビットで表すようにすることで、十分な圧縮率が得られ、ハフマン符号化をしてもそれ以上の圧縮率が得られない場合がある。従ってＡ領域に属する文字に関しては、連長圧縮で得られた記号列に対して、ハフマン符号化を行わなくてもよい。なお、ハフマン符号化によりＡ領域の文字の記号列の圧縮率を向上する場合には、Ａ領域の文字に関しても、連長圧縮で得られた記号列に対して、ハフマン符号化を行ってもよい。
【０１０２】
Ｂ領域は、符号化単位ビット列が「００１」と「０００１」とに集中する。この場合、連長圧縮すると、記号「１」の出現頻度が高頻度となる。すると、記号「１」に対して最も短い符号を割り当てるようなハフマン符号化を行うことで、Ｂ領域に属する文字に対応する記号列を圧縮可能である。
【０１０３】
Ｃ領域は、符号化単位ビット列が「００００１」から「０００００００１」の範囲に集中する。この場合、連長圧縮すると、記号「２」の出現頻度が高頻度となる。すると、記号「２」に対して最も短い符号を割り当てるようなハフマン符号化を行うことで、Ｃ領域に属する文字に対応する記号列を圧縮可能である。
【０１０４】
Ｄ領域は、符号化単位ビット列が「００００００００１」〜「０００００００００００００００１」の範囲に集中する。この場合、連長圧縮すると、記号「３」の出現頻度が高頻度となる。すると、記号「３」に対して最も短い符号を割り当てるようなハフマン符号化を行うことで、Ｄ領域に属する文字に対応する記号列を圧縮可能である。
【０１０５】
Ｅ領域は、連続する０の数が「１６」より多い符号化単位ビット列に集中する。この場合、連長圧縮すると、記号「４」の出現頻度が高頻度となる。すると、記号「４」に対して最も短い符号を割り当てるようなハフマン符号化を行うことで、Ｅ領域に属する文字に対応する記号列を圧縮可能である。
【０１０６】
このように、Ａ、Ｂ、Ｃ、Ｄ、Ｅの領域ごとに個別のハフマン木を生成し、ハフマン符号化が行われる。この場合、出現確率の高い符号化単位ビット列の０の数が多いほど、ハフマン符号化による圧縮の効果が高くなる。そのため、Ａ→Ｂ→Ｃ→Ｄ→Ｅ領域の順に圧縮率が向上する。
【０１０７】
次に、レコード群に対するインデックスの生成および圧縮手順について説明する。
図１３は、インデックスの生成および圧縮処理の手順の一例を示すフローチャートである。以下、図１３に示す処理をステップ番号に沿って説明する。
【０１０８】
［ステップＳ１０１］クローラ１２０内のインデックス生成部１２２は、レコード内に出現する文字を示すビットマップを生成する。この処理の詳細は後述する（図１４参照）。
【０１０９】
［ステップＳ１０２］インデックス生成部１２２は、ビットマップに対する連長圧縮処理を行う。この処理の詳細は後述する（図１６参照）。
［ステップＳ１０３］インデックス生成部１２２は、連長圧縮で得られた記号列に対するハフマン符号化処理を行う。この処理の詳細は後述する（図１８参照）。
【０１１０】
次に、図１３に示す各処理の詳細について説明する。
図１４は、ビットマップ生成処理の手順の一例を示すフローチャートである。以下、図１４に示す処理をステップ番号に沿って説明する。
【０１１１】
［ステップＳ１１１］インデックス生成部１２２は、ビットマップを初期化する。例えばインデックス生成部１２２は、レコード内の文字に適用されているコード体系で表現可能な文字のリストを作成する。インデックス生成部１２２は、初期化したビットマップを、例えばインデックス記憶部１４０に格納する。
【０１１２】
［ステップＳ１１２］インデックス生成部１２２は、インデックス未作成のレコードを１つ読み込む。
［ステップＳ１１３］インデックス生成部１２２は、読み込んだレコードに対応する追加ビットマップを生成する。例えばインデックス生成部１２２は、文字ごとに、読み込んだレコード内に該当文字が出現するか否か（存否）を判断する。インデックス生成部１２２は、出現する文字に関しては、読み込んだレコードと、その文字とに関連付けて「１」の値を設定する。またインデックス生成部１２２は、出現しない文字に関しては、読み込んだレコードと、その文字とに関連付けて「０」の値を設定する。インデックス生成部１２２は、例えば、文字の存否を判定するごとに、存否を示す値をワークメモリ１６０に書き込んでいく。これにより、読み込んだレコードに対応する追加ビットマップ１６２がワークメモリ１６０内に構築される（図６参照）。
【０１１３】
［ステップＳ１１４］インデックス生成部１２２は、生成した追加ビットマップ１６２を、インデックス記憶部１４０内の非圧縮のビットマップ１４２に追加する。
［ステップＳ１１５］インデックス生成部１２２は、インデックスを未作成の他のレコードがあるか否かを判断する。インデックス生成部１２２は、他のレコードがある場合、処理をステップＳ１１２に進める。またインデックス生成部１２２は、他のレコードがなければ、ビットマップ生成処理を終了する。
【０１１４】
図１５は、非圧縮のビットマップの一例を示す図である。ビットマップ１４２には、例えば文字種、文字、グローバルＩＤ（Ｇ−ＩＤ）の欄が設けられている。
文字種の欄には、文字の種別が設定される。文字の欄には、ビットマップ１４２の列のラベルとして、文字が設定される。グローバルＩＤの欄には、ビットマップ１４２の列のラベルとして、グローバルＩＤが設定されている。
【０１１５】
ビットマップ１４２では、各文字の列に、その文字の各ファイルでの存否を示す値が設定されている。例えば、その文字が出現したファイルのグローバルＩＤに対応する位置に「１」が設定され、その文字が出現していないファイルのグローバルＩＤに対応する位置に「０」が設定されている。
【０１１６】
このような非圧縮のビットマップ１４２に対して、まず連長圧縮が行われる。
図１６は、連長圧縮処理の手順の一例を示すフローチャートである。以下、図１６に示す処理をステップ番号に沿って説明する。
【０１１７】
［ステップＳ１２１］インデックス生成部１２２は、ビットマップ１４２から、未処理の文字を１つ選択する。
［ステップＳ１２２］インデックス生成部１２２は、選択した文字の出現確率を計算する。例えばインデックス生成部１２２は、選択した文字のビット列内の「１」の数を、レコードの総数で除算した結果を出現確率とする。インデックス生成部１２２は、例えば、計算した出現確率を、文字に対応付けて管理情報１６３（図６参照）内に設定する。
【０１１８】
［ステップＳ１２３］インデックス生成部１２２は、選択した文字が属する領域を判定する。例えばインデックス生成部１２２は、選択した文字の出現頻度が、図１２に示したような領域のどの領域に含まれるかを判断し、該当する領域を、その文字が属する領域と判定する。インデックス生成部１２２は、例えば、判定した領域を、選択した文字に対応付けて管理情報１６３内に設定する。
【０１１９】
［ステップＳ１２４］インデックス生成部１２２は、選択した文字の出現確率が５０％（０．５）より大きいか否かを判断する。インデックス生成部１２２は、出現確率が５０％より大きい場合、処理をステップＳ１２５に進める。またインデックス生成部１２２は、出現確率が５０％以下の場合、処理をステップＳ１２６に進める。
【０１２０】
［ステップＳ１２５］インデックス生成部１２２は、選択した文字に対応するビット列の各ビットの値を反転する。すなわちインデックス生成部１２２は、「０」のビットを「１」に変更し、「１」のビットを「０」に変更する。
【０１２１】
［ステップＳ１２６］インデックス生成部１２２は、選択した文字に対応するビット列の先頭から順に、符号化単位ビット列を抽出する。図１５の例では、各文字に対応するビット列の左端のビット（グローバルＩＤ「１」のビット）が先頭である。例えばインデックス生成部１２２は、ビット列の先頭から「１」のビットを検索する。ビット列の先頭から、最初に出現した「１」のビットのまでの部分ビット列が、符号化単位ビット列となる。２回目以降は、前回の検索で検出した「１」のビットの次のビットから検索を開始し、最初に出現する「１」のビットを検索する。そして、検索を開始したビットから、最初に出現した「１」のビットまでの部分ビット列を、符号化単位ビット列とする。
【０１２２】
なおインデックス生成部１２２は、ビット列の終端まで「１」のビットを検出できなかった場合、例えば、符号化単位ビット列の抽出は行わずに、次のステップＳ１２７に処理を進める。
【０１２３】
［ステップＳ１２７］インデックス生成部１２２は、抽出した符号化単位ビット列を、図１１に示したような規則で、連長（０が連続する数）に変換する。なおインデックス生成部１２２は、文字列の終端まで「１」のビットが検出されず、符号化単位ビット列が抽出されなかった場合、例えば、終端を示す記号［ＥＯＢ］を、記号列の末尾に追加する。この場合、最後に「１」が検出されたビットの次にビットから終端までは、すべて「０」であるものと認識される。
【０１２４】
［ステップＳ１２８］インデックス生成部１１２２は、連長を、０または２の冪乗の整数の和に分解し、０または２の冪乗に対応する記号を並べた記号列に変換する。
［ステップＳ１２９］インデックス生成部１２２は、選択した文字のビット列の終端に達したか否かを判断する。例えばインデックス生成部１２２は、ステップＳ１２６の処理において文字列の終端まで「１」のビットが検出されなかった場合、または検出した「１」のビットがビット列の終端のビットの場合には、終端に達したと判断する。終端に達した場合、処理をステップＳ１３０に進める。またインデックス生成部１２２は、終端に達していなければ、処理をステップＳ１２６に進める。
【０１２５】
［ステップＳ１３０］インデックス生成部１２２は、ビットマップ１４２内に未処理の文字があるか否かを判断する。未処理の文字がある場合、インデックス生成部１２２は、処理をステップＳ１２１に進める。またすべての文字について処理が完了した場合、インデックス生成部１２２は、連長圧縮処理を終了する。この際、インデックス生成部１２２は、例えばワークメモリ１６０内の管理情報をインデックス記憶部１４０に格納する。
【０１２６】
図１７は、連長圧縮後のインデックスの一例を示す図である。ビット列を連長圧縮によって符号化したインデックス１４１は、各文字種の文字に対応付けて、連長圧縮で生成された記号列が設定されている。また、管理情報１４３には、各文字に対応付けて、出現確率と、属する領域とが設定されている。
【０１２７】
次に、ハフマン符号化処理の詳細について説明する。
図１８は、ハフマン符号化処理の手順の一例を示す図である。以下、図１８に示す処理をステップ番号に沿って説明する。
【０１２８】
［ステップＳ１４１］インデックス生成部１２２は、Ａ、Ｂ、Ｃ、Ｄ、Ｅの領域のうちの未処理の領域を１つ選択する。
［ステップＳ１４２］インデックス生成部１２２は、インデックス１３４から、選択した領域に属する文字の記号列を抽出する。この際、インデックス生成部１２２は、選択した領域に対応する反転領域に属する文字の記号列も抽出する。例えば、Ａ領域が選択された場合、Ａ領域とＡ’領域とのいずれかに属する文字の記号列が抽出される。
【０１２９】
［ステップＳ１４３］インデックス生成部１２２は、抽出した記号列における記号ごとの生起確率を計算する。例えばインデックス生成部１２２は、抽出した記号列における、「α，β，１，２，３，・・・，ＥＯＢ」の記号それぞれの出現回数を計数する。そしてインデックス生成部１２２は、記号それぞれの出現回数を、抽出した記号列に含まれる記号の総数で除算し、除算結果を生起確率とする。なお終端を示す記号［ＥＯＢ］の出現回数は、１つの文字に対応する記号列に対して１回である。
【０１３０】
［ステップＳ１４４］インデックス生成部１２２は、記号ごとの葉を生成する。このとき、インデックス生成部１２２は、例えば終端を示す記号［ＥＯＢ］に対応する葉も生成する。生成された葉の構造体には、対応する記号と、その記号の生起確率とが設定される。
【０１３１】
［ステップＳ１４５］インデックス生成部１２２は、選択した領域のハフマン木を生成する。例えばインデックス生成部１２２は、ステップＳ１４４で生成した葉のうち、生起確率が最も小さい２つの葉を選択する。そしてインデックス生成部１２２は、新しい節点を生成し、生成した節点の下位に、選択した葉それぞれを枝で接続する。このとき、一方の枝には「０」、他方の枝には「１」のラベルが付与される。生成した節点には、選択した２つの葉それぞれの生起確率の和を設定する。インデックス生成部１２２は、以後、生成した節点を葉とみなす。そしてインデックス生成部１２２は、生起確率が最も小さい２つの葉の選択、節点の生成、葉の節点への接続処理を、節点の下位に接続されていない葉が１枚になるまで繰り返す。葉が１枚になったときに、最後に残った葉を根とする木構造が、ハフマン木である。
【０１３２】
［ステップＳ１４６］インデックス生成部１２２は、抽出した記号列内の各記号を、ステップＳ１４５で生成したハフマン木に従って、ハフマン符号に変換する。例えばインデックス生成部１２２は、ある記号を符号化する場合、ハフマン木の根からその記号に対応する葉まで枝を辿ったときに、各枝に付与されたラベルの列が、ハフマン符号となる。なおインデックス生成部１２２は、例えば生成したハフマン木を、領域に対応付けて管理情報１６３の一部としてワークメモリ１６０に格納する。
【０１３３】
［ステップＳ１４７］インデックス生成部１２２は、Ａ、Ｂ、Ｃ、Ｄ、Ｅの領域のうち未選択の領域があるか否かを判断する。インデックス生成部１２２は、未選択の領域があれば、処理をステップＳ１４１に進める。またインデックス生成部１２２は、未選択の領域がなければ、ハフマン符号化処理を終了する。この際、インデックス生成部１２２は、例えばワークメモリ１６０の管理情報１６３内のハフマン木を、インデックス記憶部１４０内に、管理情報１４３の一部として格納する。
【０１３４】
このようにして、領域ごとのハフマン木が生成され、領域ごとに異なるハフマン木で、連長圧縮で生成された記号が符号化される。
図１９は、ハフマン木の第１の例を示す図である。図１９には、Ａ領域のハフマン木７０が示されている。ハフマン木７０は、複数の葉７１ａ，７１ｂ，７１ｃ，７１ｄ，７１ｅ，７１ｆ，７１ｇ，７１ｈ，７１ｉと、複数の節点７２ａ，７２ｂ，７２ｃ，７２ｄ，７２ｅ，７２ｆ，７２ｇ，７２ｈとを含んでいる。節点７２ａは、ハフマン木７０の根である。
【０１３５】
葉７１ａは、記号「α」に対応する。葉７１ｂは、記号「β」に対応する。葉７１ｃは、記号「１」に対応する。葉７１ｄは、記号「２」に対応する。葉７１ｅは、記号「３」に対応する。葉７１ｆは、記号「４」に対応する。葉７１ｇは、記号「５」に対応する。葉７１ｈは、記号「６」に対応する。葉７１ｉは、記号［ＥＯＢ］に対応する。
【０１３６】
葉７１ａ，７１ｂ，７１ｃ，７１ｄ，７１ｅ，７１ｆ，７１ｇ，７１ｈ，７１ｉは、いずれかの節点の下に、枝によって接続されている。また節点同士も、枝で接続されている。複数の節点７２ａ，７２ｂ，７２ｃ，７２ｄ，７２ｅ，７２ｆ，７２ｇ，７２ｈのそれぞれには、２つの枝によって、葉または節点が下に接続されている。節点の下の２つの枝のうち、一方には「０」のラベルが付与され、他方には「１」のラベルが付与されている。
【０１３７】
このようなハフマン木７０の根となる節点７２ａから、符号化対象の記号までの経路を辿り、経路上の枝に付与されたラベルを辿った経路に沿って並べることで、その記号に対する圧縮符号（ハフマン符号）が得られる。
【０１３８】
図２０は、記号に対応する圧縮符号の第１の例を示す図である。図２０には、Ａ領域に属する文字に対応する記号列内の記号を、図１９に示したハフマン木７０で符号化した場合の圧縮符号が示されている。
【０１３９】
図２０の例では、記号に対応付けて、ビット列パターン、出現回数、生起確率、補正確率、残確率、圧縮符号長、圧縮符号が示されている。ビット列パターンは、記号に対応する、連長圧縮前のビット列である。出現回数は、Ａ領域に属するすべての文字に対応する記号列内における、対応する記号の出現回数である。生起確率は、Ａ領域に属するすべての文字に対応する記号列内での、記号の生起確率である。
【０１４０】
補正確率は、生起確率を１／２の冪乗の値に補正したときの確率である。例えば、生起確率より小さな１／２の冪乗の値のうちで、最大の値に補正される。生起確率が「０．５２０３」であれば、１／２の１乗、２乗、・・・の各値が、生起確率が「０．５２０３」より小さい。そのうちの最大の値は１／２の１乗（１／２）であるため、生起確率が「０．５２０３」の補正確率は１／２となる。残確率は、生起確率が高い順に補正確率を決定したときに、「１」から、決定した補正確率を減算した結果である。
【０１４１】
圧縮符号長は、記号に対応する圧縮符号のビット数である。圧縮符号は、記号に対応する圧縮符号である。
Ａ領域に属する文字は、ビット列における０の出現確率が、０．２５〜０．５である。そのため、連長圧縮が行われると、記号「α」や「β」の生起確率が高くなる。図２０に示す例では、記号「α」が最も生起確率が高い。そのため、記号「α」は、最も短い圧縮符号「０」に圧縮される。そして、生起確率が低くなるほど、圧縮符号の圧縮符号長が長くなる。
【０１４２】
Ａ領域とは別の領域では、記号の生起確率がＡ領域とは異なる。そのため、Ａ領域以外では、Ａ領域とは異なるハフマン木が生成される。
図２１は、ハフマン木の第２の例を示す図である。図２１には、Ｄ領域のハフマン木８０が示されている。ハフマン木８０は、複数の葉８１ａ，８１ｂ，８１ｃ，８１ｄ，８１ｅ，８１ｆ，８１ｇ，８１ｈ，８１ｉと、複数の節点８２ａ，８２ｂ，８２ｃ，８２ｄ，８２ｅ，８２ｆ，８２ｇ，８２ｈとを含んでいる。節点８２ａは、ハフマン木８０の根である。
【０１４３】
葉８１ａは、記号「α」に対応する。葉８１ｂは、記号「β」に対応する。葉８１ｃは、記号「１」に対応する。葉８１ｄは、記号「２」に対応する。葉８１ｅは、記号「３」に対応する。葉８１ｆは、記号「４」に対応する。葉８１ｇは、記号「５」に対応する。葉８１ｈは、記号「６」に対応する。葉８１ｉは、記号［ＥＯＢ］に対応する。
【０１４４】
Ｄ領域では、各記号の生起確率がＡ領域と異なるため、図１９に示したハフマン木７０とは異なる形態のハフマン木８０が生成されている。そのため、Ｄ領域に属する文字に対応する記号列の各記号を符号化する場合、Ａ領域とは別の圧縮符号に符号化される。
【０１４５】
図２２は、記号に対応する圧縮符号の第２の例を示す図である。図２２には、Ａ領域に属する文字に対応する記号列内の記号を、図２１に示したハフマン木８０で符号化した場合の圧縮符号が示されている。
【０１４６】
Ｄ領域に属する文字は、ビット列における０の出現確率が、０．０３１５〜０．０６２５である。そのため、連長圧縮が行われると、記号「α」や「β」の生起確率よりも、記号「２」、「３」、「４」の生起確率が高くなる。図２０に示す例では、記号「３」が最も生起確率が高い。そのため、記号「３」は、最も短い圧縮符号「０」に圧縮される。そして、生起確率が低くなるほど、圧縮符号の圧縮符号長が長くなる。
【０１４７】
記号「３」は、元のビット列では、「００００００００」の８ビットである。そのため、Ｄ領域では、８ビットのビット列が、１ビットの圧縮符号に圧縮されることになる。しかも、そのような高圧縮が可能なビット列が頻出している。その結果、高い圧縮率が期待できる。
【０１４８】
領域ごとに生成されたハフマン木により、各領域に属する文字に対応する記号列を符号化することで、圧縮形式のインデックス１４１が生成される。
図２３は、圧縮形式のインデックスの例を示す図である。インデックス１４１には、文字種に分類された文字それぞれに対応付けて、圧縮符号列が設定されている。圧縮符号列は、図１７に示した記号列の各記号を、ハフマン符号に変換したものである。
【０１４９】
例えば、図１７の管理情報を参照すると、文字「あ」は、Ａ’領域に属する。Ａ’領域に属する文字は、Ａ領域と同じハフマン木で符号化される。文字「あ」に対応する記号列の先頭の記号列は「２β」である。図２０を参照すると、記号「２」は「１１１０」の圧縮符号に符号化され、記号「β」は「１０」の圧縮符号に符号化される。そのため、「２β」は、「１１１０１０」に符号化される。
【０１５０】
以上のようにして、インデックスが圧縮される。その結果、少ない記憶容量のメモリにインデックスを格納することができる。第２の実施の形態に示したインデックスの圧縮技術には、例えば、携帯端末装置に辞書データを格納し、インデックスを用いた検索を行う場合に有用である。
【０１５１】
次に、サーチャ１３０（図４参照）による全文検索処理の手順について説明する。
図２４は、全文検索処理の手順の一例を示すフローチャートである。以下、図２４に示す処理をステップ番号に沿って説明する。
【０１５２】
［ステップＳ２０１］サーチャ１３０は、端末装置２１などから送られる検索文字列を取得する。
［ステップＳ２０２］サーチャ１３０は、検索文字列に含まれる文字のうち、未選択の文字を１つ選択する。
【０１５３】
［ステップＳ２０３］サーチャ１３０は、インデックス記憶部１４０内のインデックス１４１から、選択した文字に対応する圧縮符号列を取得する。
［ステップＳ２０４］サーチャ１３０は、選択した文字が属する領域を判断する。例えばサーチャ１３０は、管理情報１４３から、文字と領域との対応関係を示す情報（図１７参照）を取得し、その情報に基づいて、選択した文字が属する領域を判断する。
【０１５４】
［ステップＳ２０５］サーチャ１３０は、管理情報１４３の一部としてインデックス記憶部１４０に格納されている複数のハフマン木から、選択した文字が属する領域のハフマン木を抽出する。
【０１５５】
［ステップＳ２０６］サーチャ１３０は、選択した文字の圧縮符号列を、抽出したハフマン木を用いてビット列に復号する。例えばサーチャ１３０は、圧縮符号列のビットを先頭から順に選択する。次にサーチャ１３０は、抽出したハフマン木の根の節点から順に、選択したビットの値に対応するラベルが付与された枝で接続された葉または節点に、木構造を辿る。節点に達したときは、サーチャ１３０は、その節点から、次のビットの値に対応するラベルが付与された枝で接続された葉または節点に、木構造を辿る。このようにサーチャ１３０は、圧縮符号列のビットの値に従って、ハフマン木の木構造を辿る。そしてサーチャ１３０は、葉に到達した場合、根から葉に到達するまでの枝のラベルに対応する圧縮符号を、到達した葉に対応付けられた記号で示されるビット列に変換する。
【０１５６】
このような圧縮符号からビット列への変換が、選択した文字に対応する圧縮符号列内のすべての圧縮符号について行われる。なおサーチャ１３０は、終端を示す記号［ＥＯＢ］が対応付けられた葉に到達した場合、例えば、直前に復号して得られたビット列の後に、復号されたビット列の長さがレコード数に達するまで、「０」のビットを追加する。
【０１５７】
［ステップＳ２０７］サーチャ１３０は、選択した文字の属する領域が反転領域（Ａ’、Ｂ’、Ｃ’、Ｄ’、Ｅ’）か否かを判断する。サーチャ１３０は、反転領域であれば処理をステップＳ２０８に進める。またサーチャ１３０は、反転領域でなければ処理をステップＳ２０９に進める。
【０１５８】
［ステップＳ２０８］サーチャ１３０は、ステップＳ２０６で復号したビット列の各ビットの値を反転する。すなわちサーチャ１３０は、「０」のビットの値を「１」に変更し、「１」のビットの値を「０」に変更する。
【０１５９】
［ステップＳ２０９］サーチャ１３０は、検索文字列内の文字のうち、未処理の文字があるか否かを判断する。サーチャ１３０は、未処理の文字がある場合、処理をステップＳ２０２に進める。またサーチャ１３０は、すべての文字について処理が終了した場合、処理をステップＳ２１０に進める。
【０１６０】
［ステップＳ２１０］サーチャ１３０は、復号されたビット列に基づいて、検索文字列中のすべての文字が出現するレコードのグローバルＩＤを特定する。検索文字列中のすべての文字が出現するレコードは、復号したすべての文字のビット列において「１」が設定されているレコードである。
【０１６１】
例えば検索文字列が「森鴎外」であり、図８に示すようなビット列６１〜６３が復号された場合を考える。図８の例では、すべてのビット列において、９ビット目の値は「１」である。従って、９番目のレコードのグローバルＩＤ「９」が、検索文字列中のすべての文字が出現するレコードのグローバルＩＤとして特定される。
【０１６２】
［ステップＳ２１１］サーチャ１３０は、インデックス記憶部１４０から、検索文字列を構成する文字のビットマップを読み込み、該当するグローバルＩＤの絞込みを行う。特定されたグローバルＩＤに対応するレコードを、圧縮データ記憶部１５０から抽出する。例えば管理情報１４３には、グローバルＩＤと、そのグローバルＩＤに対応するレコードの圧縮データ記憶部１５０内でのアドレスとが対応付けて設定されている。サーチャ１３０は、管理情報１４３を参照し、特定したグローバルＩＤに対応するアドレスを判断し、圧縮データ記憶部１５０から、該当アドレスに格納されている圧縮データを取得する。そしてサーチャ１３０は、取得した圧縮データを復号する。これにより、平文のレコードが取得できる。
【０１６３】
［ステップＳ２１２］サーチャ１３０は、抽出したレコード内から、検索文字列を照合する。
［ステップＳ２１３］サーチャ１３０は、検索結果を出力する。例えばサーチャ１３０は、検索文字列を含むレコードのグローバルＩＤ、そのレコードのタイトル、検索文字列を含む文などを検索結果として、端末装置２１に送信する。これにより、端末装置２１では、検索結果が画面に表示される。
【０１６４】
このようにして、インデックス１４１を用いた全文検索が行われる。
以上のように、第２の実施の形態では、符号化単位ビット列を、所定のビット列パターンに分解し、分解して得られたビット列パターンをハフマン木の葉に割り当てている。これにより、葉の数を減少させることが可能となり、ハフマン木の生成、およびハフマン木を用いた符号化や復号を高速に行うことができる。
【０１６５】
また、第２の実施の形態では、ビット列パターンを記号に置き換えて圧縮処理を実行するため、ビットマップの読み出しが１回で済む。このようなビットマップの読み出しの１パス化により、圧縮処理の高速化が図られている。例えは、ビット列パターンの記号への置き換えを行わない場合、最初のビットマップの読み出しにおいて、文字ごとの「０」、「１」の密度を集計し、各文字が属する領域が判断される。次に、ビットマップの２回目の読み出しを行い、ハフマン符号化が行われる。他方、第２の実施の形態では、ビットマップを読み出して、文字ごとの「０」、「１」の密度を集計し、各文字が属する領域の判断時に、ビット列を記号列に変換する。そして記号列に基づいてハフマン符号化が行われる。記号列は、ビットマップに比べてデータ量が少なくなっているため、メモリからの読み出し時間は短くて済む。その結果、圧縮処理が高速化される。
【０１６６】
〔第３の実施の形態〕
次に第３の実施の形態について説明する。第３の実施の形態は、符号化の木として、第２の実施の形態で示したハフマン木に代えて、無節点の木を用いるものである。なお、第３の実施の形態におけるシステム構成は、図２、図３に示した第２の実施の形態の構成と同様である。また第３の実施の形態におけるＡＰサーバの機能の構成要素も、図４、図６に示した第２の実施の形態の構成要素と同様である。そこで、第２の実施の形態で示した各要素の符号を用いて、第３の実施の形態における、第２の実施の形態と異なる機能について説明する。
【０１６７】
第３の実施の形態では、クローラ１２０は、ハフマン木に代えて無節点の木を用いてインデックスの圧縮を行う。またサーチャ１３０は、ハフマン木に代えて無節点の木を用いてインデックスの伸張を行う。
【０１６８】
無節点の木は、ハフマン木と同様に、出現頻度が高い記号ほど、短い符号に符号化するものである。ただし、ハフマン木は、根（ルート）の下位に複数の節点が設けられるのに対して、無節点の木では、根の下位に節点は設けられず、すべての葉が根の下位に直接接続される。このような構造の無節点の木を用いると、圧縮符号を１パスで伸張することが可能となり、伸張速度が向上する。
【０１６９】
無節点の木を生成する際には、例えば各記号の生起確率に応じて、符号化時の符号長が決定される。例えば、クローラ１２０のインデックス生成部１２２は、図２０や図２２に示したように、各整数の出現回数を計数し、生起確率を求める。そして、インデックス生成部１２２は、出現頻度に基づいて補正確率を求める。補正確率は、例えば、「１／２」の冪乗のうち、生起確率以下の最も大きな数である。例えば、出現頻度「０．１３７」の場合、「１／４（０．２５）」より小さく、「１／８（０．１２５）」より大きい。そこで出現頻度「０．１３７」の補正確率は「１／８」となる。
【０１７０】
次にインデックス生成部１２２は、補正確率に基づいて、符号長を求める。符号長は、符号のビット数である。例えば補正確率を「１／２」の冪乗で表したときの指数（何乗か）が、符号長とされる。補正確率「１／８」であれば、「１／２」の３乗であることから、符号長は「３」となる。
【０１７１】
第２の符号化処理部１１２は、各整数の圧縮符号を、その整数の出現頻度に応じて決定した符号長の符号に決定する。例えば符号長が「３」であれば、圧縮符号は「０００」、符号長が「４」であれば、圧縮符号は「００１０」となる。すると各記号について、図２０、図２２に示された圧縮符号と同様の圧縮符号が生成される。
【０１７２】
このような記号と圧縮符号との対応関係に基づいて、無節点の木を生成することができる。例えば図２２に示すような、圧縮符号に決定された場合、図２５に示すような無節点の木が生成される。
【０１７３】
図２５は、無節点の木の一例を示す図である。無節点の木９０には、根９１と複数の葉９２ａ，９２ｂ，９２ｃ，９２ｄ，９２ｅ，９２ｆ，９２ｇ，９２ｈ，９２ｉが設けられている。根９１の直下に葉９２ａ，９２ｂ，９２ｃ，９２ｄ，９２ｅ，９２ｆ，９２ｇ，９２ｈ，９２ｉが設けられており、ハフマン木にあるような節点は存在しない。ここで葉９２ａ，９２ｂ，９２ｃ，９２ｄ，９２ｅ，９２ｆ，９２ｇ，９２ｈ，９２ｉそれぞれの識別番号を、左から順に１，２，３，４，５，６，７，８，９とする。
【０１７４】
根の構造体９３には、６ビットで表せるアドレスに対応する各領域に、葉９２ａ，９２ｂ，９２ｃ，９２ｄ，９２ｅ，９２ｆ，９２ｇ，９２ｈ，９２ｉへのポインタが設定されている。葉の構造体９４，９５には、例えば対応する葉９２ａ，９２ｆの識別番号、圧縮符号長、圧縮符号、記号、ビット列パターンなどが設定されている。
【０１７５】
ここで根の構造体９３においては、圧縮符号長が短い葉ほど、多くのポインタが設定される。例えば葉９２ａの圧縮符号長は「１」、圧縮符号は「０」である。この場合、「００００００」〜「０１１１１１」のアドレス範囲のすべての領域に、葉９２ａへのポインタが設定される。また葉９２ｆの圧縮符号長は「４」である。この場合、「１１１０００」〜「１１１０１１」のアドレス範囲のすべての領域に、葉９２ｆへのポインタが設定される。
【０１７６】
このような無節点の木９０によれば、復号を１パスで行うことができる。例えばサーチャ１３０は、復号対象の符号列の先頭の６ビットの値を取得し、根の構造体９３の先頭から、取得した値をオフセットとした領域に格納されているポインタを参照する。次にサーチャ１３０は、参照したポインタで示されている葉の構造体を参照する。そしてサーチャ１３０は、取得した６ビットのうち、参照した葉の構造体に示されている圧縮符号長で示されるビット数分の先頭ビットを、参照した葉の構造体に示されているビット列パターンに復号する。その後、サーチャ１３０は、復号していない符号列の先頭６ビットを再度取得し、同様に復号する。
【０１７７】
例えば、取得した６ビットの値が「１１１０００」であれば、対応するオフセットの領域が参照される。その領域には、葉９２ｆに対応する葉の構造体９５へのポインタが設定されている。葉の構造体９５には、圧縮符号長が「４」であること、ビット列パターン「１」に復号することが示されている。そこでサーチャ１３０は、６ビットの値「１１１０００」のうちの先頭の４ビット「１１１０」をビット列パターン「１」に復号する。
【０１７８】
このように、無節点の木９０を用いて復号することで、根９１から１パスで目的の葉を検出し、復号することができる。すなわち無節点の木９０により、圧縮データを１ビットごとでなく、６ビットをまとめた１回の判定で、葉の構造体を獲得することができる。これにより、ハフマン木を用いた復号のような、根からの節点を辿るための複数の判断が不要となり、圧縮された符号を高速に伸張することができる。
【０１７９】
次に、第３の実施の形態により実際に辞書データのビットマップ形式のインデックスを圧縮した場合の例について説明する。なお、以下の例では、１／２の冪乗に補正した補正確率を、圧縮率が向上するようにさらに補正している。このような補正を、二次補正と呼ぶこととする。二次補正は、各記号の補正確率の合計が１を超えない範囲で、補正確率を、より大きい値に変更する処理である。なお、二次補正後の補正確率も、１／２の冪乗の値である。例えばサーチャ１３０は、記号を選択し、生起確率に基づいて求めた補正確率を２倍したときに、すべての記号の補正確率の合計が１を超えるか否かを判断する。１を超えない場合、サーチャ１３０は、選択した記号の補正確率を、２倍の値に補正する。
【０１８０】
記号の補正確率が高くなると、その記号に対応する圧縮符号の符号長は短くなる。その結果、圧縮率が向上する。
以下に、ある国語辞書のビットマップ形式のインデックスを圧縮した場合の圧縮例を示す。以下に示す例では、０の出現率に応じた領域を、図１２に示した例よりも細かく設け、１６個の領域に分割している。以下の例では、Ａ〜Ｄ領域、Ａ’〜Ｄ’領域の範囲は図１２に示す通りとし、Ｅ領域とＥ’領域を細分化している。「１」の出現率が０以上１／２５６未満の範囲を、Ｈ領域としている。「１」の出現率が１／２５６以上１／１２８未満の範囲を、Ｇ領域としている。「１」の出現率が１／１２８以上１／６４未満の範囲を、Ｆ領域としている。「１」の出現率が１／６４以上１／３２未満の範囲を、Ｅ領域としている。「１」の出現率が３１／３２より大きく６３／６４以下の範囲を、Ｅ’領域としている。「１」の出現率が６３／６４より大きく１２７／１２８以下の範囲を、Ｆ’領域としている。「１」の出現率が１２７／１２８より大きく２５５／２５６以下の範囲を、Ｇ’領域としている。「１」の出現率が２５５／２５６より大きく１以下の範囲を、Ｈ’領域としている。
【０１８１】
Ａ’〜Ｈ’領域は、ビットの値を反転して、それぞれＡ〜Ｈ領域として符号化が行われる。そこで、Ａ〜Ｈ領域の圧縮結果の例を、図２６〜図３３に示す。
図２６〜図３３には、記号に対応付けて、ビット長、出現回数、ビットサイズ、および生起確率が示されている。ビット長は、記号に対応するビット列パターンのビット数である。出現回数は、記号に対応するビット列パターンが、該当領域に属する文字のビット列内に出現した回数である。ビットサイズは、該当領域に属する文字のビット列内の、記号に対応するビット列パターンの全ビット数である。なおビットサイズは、出現回数にビット長を乗算することで得られる。生起確率は、該当領域に属する文字のビット列内におけるビット列パターンが、記号に対応するビット列パターンであることの確率である。
【０１８２】
また図２６〜図３３には、記号に対応付けて、二次補正無しの場合と二次補正有りの場合とのそれぞれにおける、補正確率、符号長、および符号サイズが示されている。二次補正無しの場合の補正確率は、記号の生起確率を、１／２の冪乗の値のうち、生起確率以下の最大である。二次補正有りの場合の補正確率は、二次補正無しの場合のいずれかの記号の補正確率に対し、補正確率の合計が１を超えない範囲で、２を乗算したものである。符号長は、補正確率に応じて決定される符号のビット数である。符号サイズは、該当領域に属する文字のビット列内の記号に対応するビット列パターンを、記号を補正確率に応じて符号化した場合の、符号を表す全ビット数である。なお符号サイズは、出現回数に符号サイズを乗算することで得られる。
【０１８３】
さらに図２６〜図３３には、二次補正無しの場合と二次補正有りの場合とのそれぞれにおける、圧縮率が示されている。圧縮率は、該当領域に属する文字の圧縮前のサイズの合計に対する、圧縮後のサイズの合計の割合である。圧縮率は、ビットサイズの合計を符号サイズの合計で除算することで得られる。
【０１８４】
図２６は、Ａ領域の圧縮結果の一例を示す図である。Ａ領域の圧縮では、ビット長が短いビット列パターンほど生起確率が高い。そのため、二次補正無しの場合、圧縮率が１以上となっている。二次補正では、記号「β」に対応する補正確率が、「０．１２５０」から「０．２５００」に補正されている。これにより、記号「β」で示されるビット列パターンに対応する符号の符号長が、「３」から「２」に短縮される。また記号「３」に対応する補正確率が、「０．０１５６」から「０．０３１３」に補正されている。これにより、記号「３」で示されるビット列パターンに対応する符号の符号長が、「６」から「５」に短縮される。同様に、符号「４」〜「９」についても、二次補正により補正確率が２倍され、符号長が短縮されている。その結果、二次補正後の補正確率に基づいて符号長を決定し、符号化を行った場合、圧縮率が約０．９となっている。
【０１８５】
図２７は、Ｂ領域の圧縮結果の一例を示す図である。Ｂ領域の圧縮でも、Ａ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＢ領域では、Ａ領域と比べ、ビット長が長いビット列パターンの割合が増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．８６となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．７２となっている。
【０１８６】
図２８は、Ｃ領域の圧縮結果の一例を示す図である。Ｃ領域の圧縮結果でも、Ａ、Ｂ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＣ領域では、Ｂ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．６０となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．５２となっている。
【０１８７】
図２９は、Ｄ領域の圧縮結果の一例を示す図である。Ｄ領域の圧縮でも、Ａ、Ｂ、Ｃ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＤ領域では、Ｃ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．３８となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．３４となっている。
【０１８８】
図３０は、Ｅ領域の圧縮結果の一例を示す図である。Ｅ領域の圧縮でも、Ａ、Ｂ、Ｃ、Ｄ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＥ領域では、Ｄ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．２３となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．２１となっている。
【０１８９】
図３１は、Ｆ領域の圧縮結果の一例を示す図である。Ｆ領域の圧縮でも、Ａ、Ｂ、Ｃ、Ｄ、Ｅ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＦ領域では、Ｅ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．１４となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．１３となっている。
【０１９０】
図３２は、Ｇ領域の圧縮結果の一例を示す図である。Ｇ領域の圧縮でも、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＧ領域では、Ｆ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．０９となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．０８となっている。
【０１９１】
図３３は、Ｈ領域の圧縮結果の一例を示す図である。Ｈ領域の圧縮でも、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＨ領域では、Ｇ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．０２０となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．０１８となっている。
【０１９２】
このように、ビットマップ中のビット列パターンを、生起確率の高い要素ほど短い符号に符号化する符号化方式によって符号化することで、ビットマップ形式のインデックスに対して、高い圧縮率の圧縮と行うことができる。
【０１９３】
〔その他の実施の形態〕
第２の実施の形態では、連続する０の数が２の冪乗となるビット列を、ビット列パターンとしたが、別の法則でビット列パターンを決定することもできる。例えば連続する０の数が３の冪乗となるビット列を、ビット列パターンとすることもできる。この場合、ビット列「１」を示す記号「α」、ビット列「０１」を示す記号「β」に加え、ビット列「００１」を示す記号「γ」を定義する。また連続するビットの数を、その数の示す３の冪乗の指数の記号で表す。これにより、すべての符号化単位ビット列（０個以上の「０」の連続と「１」）を、記号の組み合わせで表現できる。
【０１９４】
また、第２の実施の形態では、文字の出現率が５割より高い、高密度の文字について、ビット列の各ビットの値を反転しているが、逆に、文字の出現率が５割より低い、低密度の文字について、ビット列の各ビットの値を反転することもできる。この場合、Ａ〜Ｅの各領域ではなく、Ａ’〜Ｅ’の領域ごとにハフマン木が生成される。
【０１９５】
また、第２の実施の形態では、レコードに対する文字の存否を示すビットマップを圧縮しているが、他の形式のデータであっても同様に圧縮可能である。例えば、イメージスキャナで画像を読み取ることで得られたビットマップデータを圧縮することが可能である。
【０１９６】
なお、上記の各実施の形態に示した処理機能は、コンピュータによって実現することができる。その場合、ＡＰサーバ１００が有する機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。なおプログラムを記録する記録媒体には、一時的な伝搬信号自体は含まれない。
【０１９７】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１９８】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１９９】
また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。
【０２００】
上記については単に本発明の原理を示すものである。さらに、多数の変形、変更が当業者にとって可能であり、本発明は上記に示し、説明した正確な構成および応用例に限定されるものではなく、対応するすべての変形例および均等物は、添付の請求項およびその均等物による本発明の範囲とみなされる。
【符号の説明】
【０２０１】
１  圧縮手段
１ａ  第１の符号化手段
１ｂ  分解手段
１ｃ  分類手段
１ｄ  計算手段
１ｅ  第２の符号化手段
２  記録媒体
２ａ  圧縮データ
２ｂ  管理情報
３  伸張手段
３ａ  第１の取得手段
３ｂ  第２の取得手段
３ｃ  復号手段
４  圧縮対象データ
【図１】
2013140530.tif 000003
【図２】
2013140530.tif 000004
【図３】
2013140530.tif 000005
【図４】
2013140530.tif 000006
【図５】
2013140530.tif 000007
【図６】
2013140530.tif 000008
【図７】
2013140530.tif 000009
【図８】
2013140530.tif 000010
【図９】
2013140530.tif 000011
【図１０】
2013140530.tif 000012
【図１１】
2013140530.tif 000013
【図１２】
2013140530.tif 000014
【図１３】
2013140530.tif 000015
【図１４】
2013140530.tif 000016
【図１５】
2013140530.tif 000017
【図１６】
2013140530.tif 000018
【図１７】
2013140530.tif 000019
【図１８】
2013140530.tif 000020
【図１９】
2013140530.tif 000021
【図２０】
2013140530.tif 000022
【図２１】
2013140530.tif 000023
【図２２】
2013140530.tif 000024
【図２３】
2013140530.tif 000025
【図２４】
2013140530.tif 000026
【図２５】
2013140530.tif 000027
【図２６】
2013140530.tif 000028
【図２７】
2013140530.tif 000029
【図２８】
2013140530.tif 000030
【図２９】
2013140530.tif 000031
【図３０】
2013140530.tif 000032
【図３１】
2013140530.tif 000033
【図３２】
2013140530.tif 000034
【図３３】
2013140530.tif 000035
【手続補正書】
【提出日】平成27年3月12日(2015.3.12)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビットマップを圧縮するプログラム、圧縮データ生成方法、伸張方法、情報処理装置、および記録媒体に関する。
【背景技術】
【０００２】
文書検索を高速化する技術の１つとして、ビットマップ型インデックスを用いる技術がある。インデックスは、例えば所定の文字コードで表現可能な各文字が、複数の文書それぞれに含まれているか否かを、ビットマップで表したものである。例えばビットマップでは、ある文字について、その文字を含む文書の文書番号の位置に「１」が設定され、その文字を含まない文書の文書番号の位置に「０」が設定される。これにより文字ごとに、「０」または「１」によって、各文書内でのその文字の存否を示すビット列が得られる。
【０００３】
文字の存否を示すビット列をハフマン圧縮する技術がある。例えば、４ビット（１デジット）または、８ビット（１バイト）毎に、その出現頻度を集計し、４（または８）ビット毎に、エントロピー符号化を施すデータ圧縮装置が考えられている。
【０００４】
また４ビットにより表現されるパターンをすべて網羅した１６種類の記号列と、４ビットよりもビット数が多い特殊記号列とを葉とする特殊なハフマン木を用いたビット列圧縮技術がある。
【０００５】
一方、文字列を圧縮する、連長圧縮（ＲＬＥ：Run Length Encoding）技術を応用することにより、ビット列を圧縮できる。連長圧縮は、例えば連続した文字列のデータを、そのデータの文字と、データの連続回数（連長：Run Length）で表現するものである。データが「０」と「１」のように２種類だけであれば、一方のデータ（例えば「０」の連長と、他方のデータ（例えば「１」））の連長とを交互に並べることで、ビット列を表現できる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−２６０４０８号公報
【特許文献２】国際公開第２００８／１４６７５６号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、連続する同じ値を含むビットマップを、連長圧縮とエントロピー符号化を単に結合して圧縮しても、十分な圧縮効果が得られない場合がある。このような連続する同じ値は、例えば、日本語の漢字のビットマップの場合では値「０」である。例えば、連長圧縮において、同じ値の連続を示す数値が分散し、偏りが少ない場合がある。他方、エントロピー符号化は、圧縮元の符号の生起確率の偏りが大きい程、圧縮率が高くなる符号化方式である。そのため、連長圧縮して得られた符号に対して、そのままエントロピー符号化を行っても十分な圧縮効果が得られない場合がある。
【０００８】
１つの側面では、本発明は、連続する同じ値を含むデータに対して、その圧縮率や伸長速度を向上させるプログラム、圧縮データ生成方法、伸張方法、情報処理装置、および記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００９】
１つの案では、コンピュータに、圧縮対象データにおける同じ値が連続する部分を、同じ値が連続する回数に符号化し、同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解し、分解して得られた各整数の生起確率を計算し、生起確率が高い整数ほど短い符号となるように、各整数を符号化する、処理を実行させるプログラムが提供される。
【発明の効果】
【００１０】
１態様によれば、同じ値の連続を含むデータの圧縮率が向上する。
本発明の上記および他の目的、特徴および利点は本発明の例として好ましい実施の形態を表す添付の図面と関連した以下の説明により明らかになるであろう。
【図面の簡単な説明】
【００１１】
【図１】第１の実施の形態に係る装置の機能構成例を示す図である。
【図２】第２の実施の形態のシステム構成例を示す図である。
【図３】第２の実施の形態に用いるＡＰサーバのハードウェアの一構成例を示す図である。
【図４】第２の実施の形態における各装置の機能の一例を示すブロック図である。
【図５】辞書データ記憶部のデータ構造の一例を示す図である。
【図６】クローラによるレコードの圧縮およびインデックス作成機能の一例を示す図である。
【図７】ビットマップのデータ構造の一例を示す図である。
【図８】ビット列の連長圧縮の一例を示す図である。
【図９】連長圧縮で符号化されるビット列の例を示す図である。
【図１０】記号とビット列との関係例を示す図である。
【図１１】符号化単位ビット列と記号列との関係例を示す図である。
【図１２】領域分割の一例を示す図である。
【図１３】インデックスの生成および圧縮処理の手順の一例を示すフローチャートである。
【図１４】ビットマップ生成処理の手順の一例を示すフローチャートである。
【図１５】非圧縮のビットマップの一例を示す図である。
【図１６】連長圧縮処理の手順の一例を示すフローチャートである。
【図１７】連長圧縮後のインデックスの一例を示す図である。
【図１８】ハフマン符号化処理の手順の一例を示す図である。
【図１９】ハフマン木の第１の例を示す図である。
【図２０】記号に対応する圧縮符号の第１の例を示す図である。
【図２１】ハフマン木の第２の例を示す図である。
【図２２】記号に対応する圧縮符号の第２の例を示す図である。
【図２３】圧縮形式のインデックスの例を示す図である。
【図２４】全文検索処理の手順の一例を示すフローチャートである。
【図２５】無節点の木の一例を示す図である。
【図２６】Ａ領域の圧縮結果の一例を示す図である。
【図２７】Ｂ領域の圧縮結果の一例を示す図である。
【図２８】Ｃ領域の圧縮結果の一例を示す図である。
【図２９】Ｄ領域の圧縮結果の一例を示す図である。
【図３０】Ｅ領域の圧縮結果の一例を示す図である。
【図３１】Ｆ領域の圧縮結果の一例を示す図である。
【図３２】Ｇ領域の圧縮結果の一例を示す図である。
【図３３】Ｈ領域の圧縮結果の一例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本実施の形態について図面を参照して説明する。なお各実施の形態は、矛盾のない範囲で複数の実施の形態を組み合わせて実施することができる。
〔第１の実施の形態〕
まず第１の実施の形態について説明する。第１の実施の形態は、同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解し、生起確率が高い整数ほど短い符号となるように、整数を符号化するようにしたものである。このような符号化方式により、同じ値が連続する回数の生起確率よりも、整数の生起確率の方が高くなり、短い符号に符号化できる割合が高くなる。その結果、圧縮率が向上する。
【００１３】
図１は、第１の実施の形態に係る装置の機能構成例を示す図である。第１の実施の形態の装置は、圧縮手段１、記録媒体２、および伸張手段３を有する。
圧縮手段１は、圧縮対象データ４を圧縮する。記録媒体２は、コンピュータで読み取り可能であり、圧縮対象データ４を圧縮した圧縮データ２ａを記憶する。伸張手段３は、圧縮データ２ａを伸張する。圧縮対象データ４は、例えば、複数の文字それぞれが、文字列を含む複数のレコードそれぞれに存在するか否かを示すビット列の集合からなるビットマップである。
【００１４】
圧縮手段１は、第１の符号化手段１ａ、分解手段１ｂ、分類手段１ｃ、計算手段１ｄ、および第２の符号化手段１ｅを有する。
第１の符号化手段１ａは、圧縮対象データ４における同じ値が連続する部分を、同じ値が連続する回数に符号化する。このような符号化は、連長圧縮と呼ばれる。例えば圧縮対象データ４が「０」と「１」とのビット列からなるビットマップであり、「０」の生起確率が「１」の生起確率より十分に高い場合、「０」が連続する回数が符号化される。この場合、先頭が「１」の場合、「０」が連続する回数が、０回であると表される。
【００１５】
分解手段１ｂは、同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解する。例えば同じ値が連続する回数を、０および２の冪乗の値の和に分解することができる。その場合、「０」の連続回数が「０」、「１」、「２」の場合には、これ以上分解できずに、そのままの値が用いられる。「０」の連続回数が「３」であれば、「１＋２」に分解することができる。
【００１６】
分類手段１ｃは、圧縮対象データ４が、文字の存否を示すビット列の集合の場合に、文字を分類する。例えば分類手段１ｃは、複数の文字のそれぞれを、対応するビット列内における、文字が存在することを示すビット値の割合に応じて複数の集合のいずれかに分類する。例えば分類手段１ｃは、レコードに文字が存在するときに、その文字のビット列内の該当レコードに対応するビットに「１」が設定される場合、ビット列内の全ビット数における値が「１」のビットの数に応じて、文字を分類する。
【００１７】
計算手段１ｄは、分解して得られた各整数の生起確率を計算する。なお計算手段１ｄは、文字が複数の集合に分類された場合、集合ごとに、該集合に属する文字に対応するビット列から得られた整数における、整数群に属する整数それぞれの生起確率を計算する。
【００１８】
第２の符号化手段１ｅは、生起確率が高い整数ほど短い符号となるように、各整数を符号化する。このような符号化技術は、例えばエントロピー符号化と呼ばれる。例えば第２の符号化手段１ｅは、ハフマン符号化により、圧縮対象データ４内のビット列をハフマン符号に符号化する。
【００１９】
なお第２の符号化手段１ｅは、文字が複数の集合に分類された場合、集合ごとに符号化を行うことができる。例えば第２の符号化手段１ｅは、集合ごとに、その集合に属する文字に対応するビット列から得られた整数を、その集合に関して計算された生起確率に基づいて符号化する。
【００２０】
第２の符号化手段１ｅは、例えば、符号化により生成した符号の、文字ごとの配列（圧縮符号列）の集合を、圧縮データ２ａとして記録媒体２に格納する。なお圧縮データ２ａには、例えば、文字に対応付けて、その文字が属する集合と、圧縮符号列とが設定される。
【００２１】
また第２の符号化手段１ｅは、記録媒体２に、管理情報２ｂを格納することもできる。管理情報２ｂは、整数と符号との対応関係を示す情報である。整数と符号との対応関係は、例えばハフマン木などの符号化の木で表すことができる。また集合ごとに符号化を行った場合、第２の符号化手段１ｅは、整数と符号との対応関係を、集合ごとに示した管理情報２ｂを、記録媒体２に格納することができる。
【００２２】
記録媒体２は、例えば圧縮対象データ４を圧縮して得られた圧縮データ２ａを記憶する。圧縮データ２ａには、整数群に属する整数のいずれかに対応する符号が含まれている。また記録媒体２には、管理情報２ｂを記録することもできる。
【００２３】
伸張手段３は、第１の取得手段３ａ、第２の取得手段３ｂ、および復号手段３ｃを有する。
第１の取得手段３ａは、圧縮対象データ４を符号化した圧縮符号列を取得する。例えば第１の取得手段３ａは、検索文字列が入力された場合に、検索文字列に含まれる文字それぞれに対応する圧縮符号列を、記録媒体２に格納されている圧縮データ２ａから取得する。
【００２４】
第２の取得手段３ｂは、整数群に属する整数と符号との対応関係を示す管理情報２ｂを取得する。例えば第２の取得手段３ｂは、記録媒体２から、管理情報２ｂを読み出す。第１の取得手段３ａが検索文字列に含まれる文字の圧縮符号列を取得した場合、第２の取得手段３ｂは、管理情報２ｂから、検索文字列に含まれる各文字が属する集合における、整数と符号との対応関係の情報を取得する。
【００２５】
復号手段３ｃは、取得した管理情報２ｂに基づいて、取得した圧縮符号列内の符号を復号する。例えば復号手段３ｃは、取得した圧縮符号列を先頭から順に読み出す。次に復号手段３ｃは、読み出した圧縮符号列の値に対応する符号を、取得した管理情報２ｂから検索する。該当する符号がある場合、復号手段３ｃは、圧縮符号列の先頭の該当符号に合致する部分を、その符号に対応する整数で示される回数の、同じ値の連続に変換する。復号手段３ｃは、このような変換を、取得した圧縮符号列全体に対して実行する。これにより、圧縮符号列が復号される。
【００２６】
このようなシステムにおいて、例えば圧縮対象データ４が文字ごとのビット列の集合の場合、第１の符号化手段１ａにより、ビット列が、「０」のビット値の連続回数に符号化される。次に、分解手段１ｂにより、０の連続回数が、整数の和に分解される。例えば、整数群に「０」と２の冪乗の値が含まれる場合、０の連続回数が、「０，１，２，４，８，・・・」という整数群の和に分解される。
【００２７】
また、分類手段１ｃによって、文字を複数の集合に分類することもできる。文字の分類では、例えば、文字「あ」が存在するレコードの割合と、文字「う」が存在するレコードの割合とが近い場合、文字「あ」と文字「う」とは、同じ集合「Ａ」に分類される。
【００２８】
その後、計算手段１ｄにより、整数ごとの生起確率が計算される。図１の例では、集合「Ａ」に属する文字における整数「０」の生起確率は「ａ１」、整数「１」の生起確率は「ａ２」、整数「２」の生起確率は「ａ３」、整数「４」の生起確率は「ａ４」となっている。このとき各生起確率の大小関係は、ａ４＞ａ３＞ａ２＞ａ１であるものとする。
【００２９】
第２の符号化手段１ｅは、生起確率が高い整数ほど、短い符号を割り当て、圧縮対象データ４内のビット列の符号化を行う。例えば図１の例では、集合「Ａ」に関し、整数「０」の符号は「１１０」（符号長３）、整数「１」の符号は「１０」（符号長２）、整数「２」の符号は「０」（符号長１）であるものとする。すると、文字「あ」の先頭のビット「１」は、符号「１１０」に変換される。また、文字「う」の先頭のビット列「００００」は、符号「０」に変換される。
【００３０】
圧縮手段１で生成された圧縮データ２ａや管理情報２ｂは、記録媒体２に格納される。そして、例えば伸張手段３に検索文字列が入力されると、第１の取得手段３ａにより、検索文字列に含まれる文字に対応する圧縮符号列が、圧縮データ２ａから抽出される。また第２の取得手段３ｂにより、抽出した文字が属する集合に対応する管理情報が取得される。そして復号手段３ｃにより、圧縮符号列が復号される。例えば図１の例では、集合「Ａ」に属する文字「あ」の先頭の「１１０」の圧縮符号が、ビット列「１」に復号される。また集合「Ａ」に属する文字「う」の先頭の「０」の圧縮符号が、ビット列「００００」に復号される。
【００３１】
このようにして、圧縮対象データ４の圧縮と伸張が可能となる。なお図１の例では、整数「２」については、ビット列「００００」を表しており、符号化後のビット長が「１」である。従って、符号化によって圧縮されている。他方、整数「０」については、ビット列の「１」が「１１０」に符号化され、符号化後の方がビット長が長くなってしまう。ただし、整数「０」の生起確率は、他の整数に比べて低いため、圧縮データ２ａ全体の圧縮率に対する悪影響は少ない。その結果、圧縮対象データ４よりも少ないデータ容量の圧縮データ２ａを得ることができる。
【００３２】
しかも、第１の実施の形態では、同じ値が連続する回数を、整数の和に分解している。そのため、同じ値が連続する回数の生起確率よりも、整数群に属する整数の生起確率の方が高くなる。ハフマン符号化のような、生起確率が高いほど短い符号に符号化する符号化方式では、符号化対象の値の偏りが大きい方が、圧縮率が高くなる。従って、同じ値が連続する回数を整数群の整数の和に分解して、整数に符号を割り当てることで、圧縮率を向上させることができる。
【００３３】
また、このような圧縮処理は、「０」と「１」との出現率の偏りが大きいビットマップの圧縮に特に有効である。例えば、インデックスを用いた辞書検索を高速化する場合を考える。辞書検索では、辞書データを複数のレコードに分割し、各レコードを圧縮して格納しておく。そして検索文字列が入力されると、インデックスを用いて検索文字列に含まれる文字が出現するレコードを特定し、特定したレコードを伸張する。このとき、辞書データを非常に細かく分割し、１つのレコードのサイズを小さくすれば、そのレコードを伸張する先の処理量を減らすことができる。他方、辞書データを細かく分割すると、レコード数が膨大となる。このような場合、１つのレコード当たりのサイズが小さいため、圧縮対象データ４を作成すると、各レコードに対応する各ビットの値は、ほとんどが「０」となる。特に日本語の場合、使用頻度の低い漢字が多数存在し、そのような漢字のビット列には、「１」はほとんど含まれないこととなる。このような圧縮対象データ４は、０が多数連続する０の連続回数の出現頻度が高い。そのため、第１の実施の形態に示す技術で圧縮対象データ４を圧縮することで、高い圧縮率を得ることが可能となる。
【００３４】
しかも、文字を、対応するビット列内における、文字が存在することを示すビット値の割合に応じて複数の集合のいずれかに分類することで、各文字のビット列を、文字が存在することを示すビット値の割合に応じた、適切な符号に圧縮することが可能である。その結果、圧縮率がさらに向上する。
【００３５】
なお、圧縮手段１、伸張手段３は、情報処理装置が有するＣＰＵ（Central Processing Unit）により実現することができる。また、記録媒体２は、光ディスクなどの可搬型記録媒体、情報処理装置が有するＲＡＭ（Random Access Memory）、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）などにより実現することができる。
【００３６】
また、図１に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。
〔第２の実施の形態〕
次に第２の実施の形態について説明する。第２の実施の形態は、辞書データのインデックスを圧縮するものである。以下、第２の実施の形態について詳細に説明する。
【００３７】
図２は、第２の実施の形態のシステム構成例を示す図である。第２の実施の形態では、ネットワーク１０を介して、例えばＡＰサーバ１００、ＤＢサーバ２００、および端末装置２１が接続されている。ＤＢサーバ２００は、辞書データなど情報を格納したデータベースを有している。ＡＰサーバ１００は、端末装置２１からの要求に応じて、ＤＢサーバ２００に格納されている情報を検索し、検索結果を端末装置２１に送信する。端末装置２１は、ユーザの操作に応じて、ＡＰサーバ１００に検索要求を送信し、ＡＰサーバ１００から送られた検索結果をモニタに表示する。
【００３８】
図３は、第２の実施の形態に用いるＡＰサーバのハードウェアの一構成例を示す図である。ＡＰサーバ１００は、ＣＰＵ１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０８を介してＲＡＭ１０２と複数の周辺機器が接続されている。なおＡＰサーバ１００が有するＣＰＵ数は１つに限定されず、複数であってもよい。ＡＰサーバ１００が複数のＣＰＵを有する場合、複数のＣＰＵが連係動作し、装置全体を制御する。
【００３９】
ＲＡＭ１０２は、ＡＰサーバ１００の主記憶装置として使用される。ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。
【００４０】
バス１０８に接続されている周辺機器としては、ＨＤＤ１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、および通信インタフェース１０７がある。
【００４１】
ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、ＡＰサーバ１００の二次記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリなどの半導体記憶装置を使用することもできる。
【００４２】
グラフィック処理装置１０４には、モニタ１１が接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１１の画面に表示させる。モニタ１１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００４３】
入力インタフェース１０５には、キーボード１２とマウス１３とが接続されている。入力インタフェース１０５は、キーボード１２やマウス１３から送られてくる信号をＣＰＵ１０１に送信する。なお、マウス１３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００４４】
光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク１４に記録されたデータの読み取りを行う。光ディスク１４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク１４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００４５】
通信インタフェース１０７は、ネットワーク１０に接続されている。通信インタフェース１０７は、ネットワーク１０を介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００４６】
以上のようなハードウェア構成によって、第２の実施の形態の処理機能を実現することができる。なお図３にはＡＰサーバ１００のハードウェア構成例を示したが、ＤＢサーバ２００や端末装置２１もＡＰサーバ１００と同様のハードウェアで実現することができる。また、第１の実施の形態に示した情報処理装置も、図３に示したＡＰサーバと同様のハードウェアにより実現することができる。
【００４７】
図４は、第２の実施の形態における各装置の機能の一例を示すブロック図である。ＤＢサーバ２００は、辞書データ記憶部２１０とＤＢ管理部２２０とを有している。
辞書データ記憶部２１０は、国語辞典、英和辞典、和英辞典などの辞書データを記憶している。例えばＤＢサーバ２００のＨＤＤの記憶領域の一部が、辞書データ記憶部２１０として使用される。なお辞書データは、複数のレコードで構成される。例えば、辞書データに項目ごとのレコードが設けられる。
【００４８】
ＤＢ管理部２２０は、辞書データ記憶部２１０に格納されたデータを管理する。例えばＤＢ管理部２２０は、ＡＰサーバ１００からの要求に応じて辞書データ記憶部２１０内のデータを読み出し、ＡＰサーバ１００に送信する。
【００４９】
ＡＰサーバ１００は、ＤＢエージェント１１０、クローラ１２０、サーチャ１３０、インデックス記憶部１４０、および圧縮データ記憶部１５０を有している。
ＤＢエージェント１１０は、ＤＢサーバ２００に対して、辞書データ記憶部２１０の操作要求を行う。例えばＤＢエージェント１１０は、クローラ１２０またはサーチャ１３０からの要求に応じて、ＤＢサーバ２００に対して、辞書データ記憶部２１０内のレコードの取得要求を送信する。この場合、ＤＢエージェント１１０は、ＤＢサーバ２００から応答されたレコードを、クローラ１２０またはサーチャ１３０に送信する。
【００５０】
クローラ１２０は、ＤＢエージェント１１０を介してＤＢサーバ２００からレコードを取得し、辞書データ記憶部２１０に格納されているレコードのインデックスを作成する。作成されるインデックスは、辞書データ記憶部２１０内の複数のレコードそれぞれにおける、各種の文字の存否をビットマップ形式で示した情報である。クローラ１２０は、作成したインデックスを、インデックス記憶部１４０に格納する。
【００５１】
またクローラ１２０は、取得したレコードを圧縮して、圧縮データ記憶部１５０に格納することもできる。これにより、圧縮データ記憶部１５０内に、辞書データのアーカイブ（書庫）が構築される。
【００５２】
サーチャ１３０は、端末装置２１からの検索要求に応じて、辞書データ記憶部２１０内のデータを検索する。例えばサーチャ１３０は、端末装置２１から検索要求を受信すると、インデックス記憶部１４０に格納されているインデックスに基づいて、検索要求に示されている文字列を構成する文字が、それぞれ少なくとも１回出現するレコードを特定する。次にサーチャ１３０は、ＤＢエージェント１１０を介して、特定したレコードをＤＢサーバ２００から取得する。サーチャ１３０は、取得したレコードを、圧縮データ記憶部１５０に格納する。そしてサーチャ１３０は、圧縮データ記憶部１５０に格納したレコードから、検索要求に示される文字列を検索し、その文字列を含むレコードのリストを、検索結果として端末装置２１に送信する。
【００５３】
インデックス記憶部１４０は、クローラ１２０により、辞書データ記憶部２１０に格納されたレコードをもとに作成されたインデックスが記憶される。例えばＨＤＤ１０３の記憶領域の一部がインデックス記憶部１４０として使用される。
【００５４】
圧縮データ記憶部１５０は、クローラ１２０により取得されたレコードが圧縮されて記憶される。例えば、ＨＤＤ１０３の記憶領域の一部が圧縮データ記憶部１５０として使用される。
【００５５】
このような構成のシステムにより、ビットマップ形式のインデックスの作成、およびインデックスを用いた情報検索が行われる。
なお、図４に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。
【００５６】
次に、辞書データ記憶部２１０に格納されているレコードについて詳しく説明する。
図５は、辞書データ記憶部のデータ構造の一例を示す図である。図５の例では、辞書データ記憶部２１０には、第１の辞書データ３０と第２の辞書データ４０とを統合した、統合辞書データ５０が格納されている。
【００５７】
第１の辞書データ３０は、項目ごとに分けられた複数のレコード３１，３２，３３，・・・で構成される。各レコード３１，３２，３３，・・・には、第１の辞書データ３０内で各レコードを一意に識別するためのＩＤ（ローカルＩＤ）、項目の見出し、および項目の本文などが含まれる。
【００５８】
第２の辞書データ４０は、項目ごとに分けられた複数のレコード４１，４２，４３，・・・で構成される。各レコード４１，４２，４３，・・・には、第２の辞書データ４０内で各レコードを一意に識別するためのＩＤ（ローカルＩＤ）、項目の見出し、および項目の本文などが含まれる。
【００５９】
辞書データ記憶部２１０に格納された統合辞書データ５０は、複数のレコード５１，５２，５３，・・・で構成される。複数のレコード５１，５２，５３，・・・は、例えば、第１の辞書データ３０のレコード３１，３２，３３，・・・、および第２の辞書データ４０のレコード４１，４２，４３，・・・をコピーし、ＩＤを変更することによって生成される。各レコード５１，５２，５３，・・・には、グローバルＩＤ（Ｇ−ＩＤ）、辞書ＩＤ（Ｄ−ＩＤ）、ローカルＩＤ（Ｌ−ＩＤ）、項目の見出し、および項目の本文などが含まれる。グローバルＩＤは、統合辞書データ５０内で各レコードを識別するためのＩＤである。辞書ＩＤは、複写元となった辞書データを識別するためのＩＤである。ローカルＩＤは、複写元の辞書データ内での複写元のレコードのＩＤである。
【００６０】
第１の辞書データ３０と第２の辞書データ４０とから統合辞書データ５０を作成する場合、第１の辞書データ３０と第２の辞書データ４０から複製したレコードに、グローバルＩＤと辞書ＩＤとが付与される。グローバルＩＤとしては、例えばシーケンシャルな番号が用いられる。なお統合辞書データ５０の作成は、例えばＤＢ管理部２２０が行う。また他のコンピュータで作成した統合辞書データ５０を、ＤＢサーバ２００に格納してもよい。
【００６１】
次に、統合辞書データ５０内の各レコードの圧縮、およびインデックス作成処理について説明する。レコードの圧縮、およびインデックス作成処理は、クローラ１２０で行われる。
【００６２】
図６は、クローラによるレコードの圧縮およびインデックス作成機能の一例を示す図である。クローラ１２０は、ワークメモリ１６０を用いて、レコード５１，５２，５３，・・・の圧縮と、レコード５１，５２，５３，・・・それぞれにおける文字の存否を示すビットマップを生成する。この処理を実行するため、クローラ１２０は、文書圧縮部１２１とインデックス生成部１２２とを有している。なお、ワークメモリ１６０としては、例えばＲＡＭ１０２内の記憶領域の一部が使用される。
【００６３】
文書圧縮部１２１は、ＤＢサーバ２００から取得したレコード５１，５２，５３，・・・を圧縮する。例えば、文書圧縮部１２１は、例えばハフマン符号化、スライド辞書法などのさまざまな符号化方式を組み合わせて、レコード５１，５２，５３，・・・を圧縮することができる。文書圧縮部１２１は、レコード５１，５２，５３，・・・それぞれ内の文字列を順次符号化し、圧縮結果をワークメモリ１６０に格納する。レコード５１，５２，５３，・・・内のすべての文字列が符号化されると、ワークメモリ１６０内に圧縮文書１６１が生成される。そして文書圧縮部１２１は、圧縮文書１６１を、圧縮データ記憶部１５０内の圧縮データ１５１に追加する。
【００６４】
インデックス生成部１２２は、レコード５１，５２，５３，・・・を解析し、例えば所定の文字コードで表されるすべての文字について、レコード５１，５２，５３，・・・内に出現するか否かを判断する。インデックス生成部１２２は、１文字の存否を判断することに、その存否を示す１ビットの値を、ワークメモリ１６０に格納する。所定の文字コードで表されるすべての文字の存否の判断が終了すると、ワークメモリ１６０内に追加ビットマップ１６２が生成される。この段階では、追加ビットマップ１６２は非圧縮の状態である。
【００６５】
インデックス生成部１２２は、生成した追加ビットマップ１６２をインデックス記憶部１４０に格納する。次にインデックス生成部１２２は、インデックス記憶部１４０に格納した追加分のビットマップ１４２を圧縮し、インデックス記憶部１４０内のインデックス１４１に追加する。
【００６６】
またインデックス生成部１２２は、追加ビットマップ１６２に関する管理情報１６３を生成し、ワークメモリ１６０に格納する。管理情報１６３には、インデックス１４１を用いた検索処理に用いられる各種情報が格納される。例えば第２の実施の形態では、インデックス生成部１２２は、ビットマップ１４２を圧縮する際に、文字の出現頻度を表す０〜１の数値の範囲を複数の領域に分割する。そしてインデックス生成部１２２は、各文字のレコードに対する出現頻度に応じて、文字が属する領域を決定する。そこでインデックス生成部１２２は、例えば管理情報１６３に、例えば文字の出現頻度、または文字が属する領域の情報を格納する。これにより、インデックス１４１の伸張の際には、管理情報１６３に基づいて、各文字の属する領域が判断できる。インデックス生成部１２２は、ワークメモリ１６０内に生成した管理情報１６３を、インデックス記憶部１４０に格納する。これによりインデックス記憶部１４０内に管理情報１４３が記憶される。
【００６７】
次に、統合辞書データ５０に基づいて作成された、圧縮前のビットマップ１４２について説明する。
図７は、ビットマップのデータ構造の一例を示す図である。インデックス記憶部１４０には、圧縮前のビットマップ１４２が格納されている。ビットマップ１４２は、文字に対応するビット列６１，６２，６３，・・・の集合である。ビット列６１，６２，６３，・・・は、統合辞書データ５０内のレコードの数分のビットの配列である。例えば、統合辞書データ５０内のレコードがｎ個（ｎは、１以上の整数）であれば、１つにビット列のビット数はｎである。
【００６８】
図７の例では、ビット列６１，６２，６３，・・・内の各ビットは、左から順に、「１」から昇順のグローバルＩＤに対応付けられている。例えば、左端のビットにグローバルＩＤ「１」に対応付けられ、右端のビットはグローバルＩＤ「ｎ」に対応付けられている。
【００６９】
ビット列６１，６２，６３，・・・内の各ビットは、ビット列に対応する文字が、統合辞書データ５０内の対応するグローバルＩＤで示されるレコードに、少なくとも１回出現するか否かを示している。例えば、ビット列に対応する文字が、レコード内に少なくとも１回出現した場合、そのレコードのグローバルＩＤに対応するビットに「１」が設定される。またビット列に対応する文字が、レコード内に１度も出現しない場合、そのレコードのグローバルＩＤに対応するビットに「０」が設定される。
【００７０】
このようなビットマップ１４２が圧縮され、インデックス１４１が生成される。ビットマップ１４２を圧縮する場合、まず、ビットマップ１４２に含まれるビット列６１，６２，６３，・・・の連長圧縮が行われる。
【００７１】
ここで、文字列に関する連長圧縮について説明する。連長圧縮では、ある連続したデータを、そのデータ１つ分と連続した長さで表現する。例えば、文字列「ＡＡＡＡＡＢＢＢＢＢＢＢＢＢＡＡＡ」は「Ａ５Ｂ９Ａ３」と表せる。これは、Ａが５回続き、そのあとにＢが９回、そしてＡが３回続いていることを表している。なお、連続回数を、元のデータを表す符号の前に記録することもある。その場合、符号化した後は「５Ａ９Ｂ３Ａ」と表される。
【００７２】
さらに、データがこの２種類（ＡとＢ）だけで、最初にＡが来ることにしておけば、「５９３」だけで表せる。このルールに従ったときにＢが最初に見つかった場合は、最初にＡが０回連続していることにすればよい。例えば、「ＢＢＢＡＡＡＡＡＢＢＢＢＢＡＡＡ」は「０３５５３」で表せることになる。
【００７３】
各レコード内での文字の存否を示すビットマップ１４２は、対象のファイルやレコードに、該当する文字や基礎単語が含まれるか、否かを「１」（ＯＮ）と「０」（ＯＦＦ）にて表現し、無記憶情報源に属するデータである。なお無記憶情報源とは、各データが他のデータに依存せずに独立に発生する情報源である。
【００７４】
日本語に関して、国語辞典を例にすると、約２０〜３０項目を１ファイルに格納した場合、日本語の漢字の平均的な出現頻度は１／１３であり、以下のように、「０」が連続し、「１」が単一である場合が多い。そこで、第２の実施の形態では、ビットマップ１４２内のビット列を、連続する「０」と単一の「１」からなるビット列（符号化単位ビット列）に分解し、分解して得られた符号化単位ビット列ごとに連長圧縮を行う。これにより、より短い符号に圧縮可能となる。
【００７５】
図８は、ビット列の連長圧縮の一例を示す図である。図８には「森鴎外」の文字列を構成する各文字のビット列６１，６２，６３の例を示している。図８に示すように、ビット列６１，６２，６３では、対応する文字が、ビット位置に対応するレコードに出現する場合、そのビットの値が「１」となり、出現しない場合、そのビットの値が「０」となる。
【００７６】
このようなビット列６１，６２，６３が、連長圧縮される。例えば、「外」の文字のビット列６３は、「００００００００１０００００１０・・・・・・・・・１００００１００」である。なお最後の２つの「０」は、終端を示す記号である。このビット列６３では、最初に「０」が８個続き、その後、１つの「１」を挟んで０が５回続いている。また終端の直前は、「１」の後に「０」が４回続き、最後が「１」となっている。この場合、「８５・・・４［ＥＯＢ］」（［ＥＯＢ］は終端を示す記号）という符号に圧縮できる。
【００７７】
ビット列６１，６２，６３，・・・を圧縮して得られた連長符号をハフマン符号化することで、さらに圧縮率を高めることができる。なお、ハフマン符号化は、生起確率が高いほど短い符号に符号化する符号化技術の一例である。
【００７８】
図９は、連長圧縮で符号化されるビット列の例を示す図である。図９の例では、「０」が連続する数を連長（ランレングス）とし、連長ごとの符号化単位ビット列、生起確率、ビット長、および残確率を示している。生起確率は、「０」と「１」との発生がランダム（同じ確率で発生）の場合に、連長に対応する符号化単位ビット列が出現する確率である。ビット長は、生起確率に基づいて、符号化単位ビット列をハフマン木により符号化した場合の符号の長さ（ビット数）である。残確率は、対応する連長よりも連長が多い符号化単位ビット列の生起確率である。例えば、連長「０」の生起確率は「１／２」であるため、その連長より多い連長（１以上）の符号化単位ビット列の生起確率は、「１／２」（＝１−１／２）となる。従って連長「０」の残確率は「１／２」となる。
【００７９】
図９に示すように、ビットの値がランダムに発生する場合、ビット長が短いほど生起確率が高い。またハフマン符号化は、生起確率が高いビット列（系列）ほど、短い符号に符号化する符号化方式である。すると、ビットの値がランダムに出現する場合には、もともと短いビット長のビット列に、短い符号が割り当てられることとなり、圧縮の効果はあまり期待できない。
【００８０】
他方、例えば「０」または「１」の密度が低下した場合に圧縮の効果が期待できる。すなわち、連長が多い符号化単位ビット列の生起確率が、連長が小さい符号化単位ビット列より高ければ、ハフマン符号化により、連長が多い符号化単位ビット列が、短い符号に符号化される。その結果、全体としての圧縮率が向上する。
【００８１】
日本語には、一般的に６〜８千種の文字が存在する。そのうち、高頻度な文字は、かな、カタカナ、英数字、および教育漢字の約千種である。国語辞書において、１万の項目のうち、１または２つの項目にしか出現しない文字が多数存在する。従って、符号化単位ビット列の連長の種類は数千にのぼる。このままハフマン木を生成すると、ハフマン木の葉の数が数千となる。ハフマン木の葉の数が多くなるほど、ハフマン木を生成する際の計算量は指数関数的に増大するため、低速ＣＰＵや小容量のメモリで構成される省資源のハード環境での実装は、極めて困難である。
【００８２】
そこで、第２の実施の形態では、所定の整数群に含まれる整数の組み合わせで、０が連続する長さ（連長）を表す。例えば、「０」と、ある整数の冪乗の値との組み合わせで連長を表すことができる。
【００８３】
２の冪乗の数の和によって、「０」が連続する長さを表す場合、冪乗の指数の値を、連長に対応する記号とする。また、第２の実施の形態では、連続する「０」と、連続する「０」の次に出現する「１」とをまとめて、符号化単位ビット列とする。このような符号化単位ビット列を符号化する場合、「１」を含む記号を用意しておくこととなる。例えば、「１」に対応する記号を「α」、「０１」に対応する記号を「β」とする。「α」は、「０」の連続回数が０回であることを意味している。「β」は、「０」の連続回数が１回（２の０乗）であることを意味している。
【００８４】
符号化単位ビット列は、整数群に属する整数に対応するビット列パターンに分解できる。以下に、整数群に属する整数を示す記号とビット列パターンとの関係について図１０を参照して説明する。
【００８５】
図１０は、記号とビット列との関係例を示す図である。図１０に示すように、記号「α」で示される「０」の数は「０」であり、符号化単位ビット列内のビット列パターン「１」に対応する。この記号「α」は、符号化単位ビット列の終端を表している。
【００８６】
記号「β」で示される「０」の数は「１」であり、符号化単位ビット列内のビット列パターン「０１」に対応する。この記号「β」は、符号化単位ビット列の終端を表している。
【００８７】
記号「１」で示される「０」の数は「２」であり、この数を２の冪乗で表すと２の１乗となる。この記号「１」は、符号化単位ビット列のうちのビット列パターン「００」に対応する。この記号「１」は、符号化単位ビット列の終端以外である。図１０では、ビット列パターン「００」の後に、他のビット列パターンが続くことを表す記号「＋」が示されている。
【００８８】
記号「２」で示される「０」の数は「４」であり、この数を２の冪乗で表すと２の２乗となる。この記号「２」は、符号化単位ビット列のうちのビット列パターン「００００」に対応する。この記号「２」は、符号化単位ビット列の終端以外である。図１０では、ビット列パターン「００００」の後に、他のビット列パターンが続くことを表す記号「＋」が示されている。
【００８９】
以下同様に、記号の値が１増加するごとに、ビット列パターンの「０」の数は、２倍になる。
図１０に示すような記号を定義すると、符号化単位ビット列をビット列パターンに分解し、符号化単位ビット列に含まれるビット列パターンを１以上の記号の組み合わせ（記号列）で表すことができる。
【００９０】
図１１は、符号化単位ビット列と記号列との関係例を示す図である。なお図１１では、連長ごとの、符号化単位ビット列、記号列、生起確率、ビット長、残確率を示している。なお、生起確率は、「０」と「１」とがランダムに出現する場合の、符号化単位ビット列の生起確率である。ビット長は、符号化単位ビット列のビット長である。残確率は、対応する連長よりも連長が多い符号化単位ビット列の存在確率である。
【００９１】
連長が「０」の符号化単位ビット列「１」は、記号列「α」に対応する。連長が「１」の符号化単位ビット列「０１」は、記号列「β」に対応する。連長が「２」の符号化単位ビット列「００１」は、記号列「１α」に対応する。連長が「３」の符号化単位ビット列「０００１」は、記号列「１β」に対応する。連長が「４」の符号化単位ビット列「００００１」は、記号列「２α」に対応する。以降、符号化単位ビット列の連続する「０」の数がいくつであっても、図１０に示した記号を組み合わせた記号列で表すことができる。
【００９２】
このように、ビットマップ中の符号化単位ビット列を、対応する記号列に変換すると、連長圧縮に用いる記号の数を少なくすることにより、省資源なハードウェア環境でも、実装が可能となる。
【００９３】
例えば、統合辞書データ５０内のレコード数が約１万の場合、ビットマップにおける各文字のビット列の長さも約１万である。この場合、最大で８１９２の連長に対応する記号が用意されていれば、すべての符号化単位ビット列を、記号列に変換できる。すると、約１０Ｋビットのビットマップを構成する符号化単位ビット列は、わずか１５（２＋１３）種の記号の組み合わせで表現することができる。
【００９４】
連長圧縮で符号化された記号列をハフマン符号化で圧縮する場合、各記号が、ハフマン木の葉に割り当てられる。すると、連長をハフマン木の葉に割り当てた場合に比べて、ハフマン木の葉の数を数千から１５に激減させることができ、ハフマン木のサイズ縮小や生成時間の短縮が図れる。
【００９５】
ハフマン木のサイズが小さくなり、生成時間が短縮されれば、文字を出現頻度で分類し、出現頻度に応じたハフマン木を生成することも容易となる。例えば第２の実施の形態では、文字の出現率を表す数値の範囲「０〜１」を、１０の領域に分割する。
【００９６】
図１２は、領域分割の一例を示す図である。図１２の例では、「１」の出現率が０以上１／３２（０．０３１）未満の範囲が、Ｅ領域である。「１」の出現率が１／３２（０．０３１）以上１／１６（０．０６３）未満の範囲が、Ｄ領域である。「１」の出現率が１／１６（０．０６３）以上１／８（０．１２５）未満の範囲が、Ｃ領域である。「１」の出現率が１／８（０．１２５）以上１／４（０．２５０）未満の範囲が、Ｂ領域である。「１」の出現率が１／４（０．２５０）以上１／２（０．５００）以下の範囲が、Ａ領域である。
【００９７】
さらに「１」の出現率が１／２（０．５００）より大きく３／４（０．７５０）以下の範囲が、Ａ’領域である。「１」の出現率が３／４（０．７５０）より大きく７／８（０．８７５）以下の範囲が、Ｂ’領域である。「１」の出現率が７／８（０．８７５）より大きく１５／１６（０．９３８）以下の範囲が、Ｃ’領域である。「１」の出現率が１５／１６（０．９３８）より大きく３１／３２（０．９６９）以下の範囲が、Ｄ’領域である。「１」の出現率が３１／３２（０．９６９）より大きく１．００以下の範囲が、Ｅ’領域である。
【００９８】
図１２に示した１０の領域は、０．５を対象点とした点対称の関係を有する。すなわち、０．５を中心として、Ａ’、Ｂ’、Ｃ’、Ｄ’、Ｅ’の各領域を１８０度回転させると、各領域はそれぞれＡ、Ｂ、Ｃ、Ｄ、Ｅの各領域に合致する。
【００９９】
Ａ’、Ｂ’、Ｃ’、Ｄ’、Ｅ’の各領域は、連長圧縮前のビット列の値を、反転させることで、０の出現確率が、対象関係にある領域と同じとなる。ビット列の値の反転とは、「０」のビットを「１」に、「１」のビットを「０」に変更する処理である。例えば、Ａ’領域に属する文字のビット列の値を反転すると、「１」の出現確率は１／４以上１／２以下となり、Ａ領域の０の出現確率と同じとなる。
【０１００】
そこで第２の実施の形態では、Ａ’、Ｂ’、Ｃ’、Ｄ’、Ｅ’に属する文字については、ビット列の値を反転させた後、連長圧縮を行う。そして、連長圧縮後の記号列は、対象関係にある領域と同じハフマン木を用いることで、効果的に圧縮可能である。なお、以下の説明では、１の出現確率が１／２より高い、Ａ’、Ｂ’、Ｃ’、Ｄ’、Ｅ’の各領域を総称して、反転領域と呼ぶこととする。
【０１０１】
Ａ領域は、符号化単位ビット列が「１」、「０１」のいずれかに集中する。すると連長圧縮で生成した記号は、「α」と「β」とが高頻度で出現し、他の記号の出現頻度は少ない。Ａ領域は、例えば記号「α」を１ビットで表し、記号「β」を２ビットで表すようにすることで、十分な圧縮率が得られ、ハフマン符号化をしてもそれ以上の圧縮率が得られない場合がある。従ってＡ領域に属する文字に関しては、連長圧縮で得られた記号列に対して、ハフマン符号化を行わなくてもよい。なお、ハフマン符号化によりＡ領域の文字の記号列の圧縮率を向上する場合には、Ａ領域の文字に関しても、連長圧縮で得られた記号列に対して、ハフマン符号化を行ってもよい。
【０１０２】
Ｂ領域は、符号化単位ビット列が「００１」と「０００１」とに集中する。この場合、連長圧縮すると、記号「１」の出現頻度が高頻度となる。すると、記号「１」に対して最も短い符号を割り当てるようなハフマン符号化を行うことで、Ｂ領域に属する文字に対応する記号列を圧縮可能である。
【０１０３】
Ｃ領域は、符号化単位ビット列が「００００１」から「０００００００１」の範囲に集中する。この場合、連長圧縮すると、記号「２」の出現頻度が高頻度となる。すると、記号「２」に対して最も短い符号を割り当てるようなハフマン符号化を行うことで、Ｃ領域に属する文字に対応する記号列を圧縮可能である。
【０１０４】
Ｄ領域は、符号化単位ビット列が「００００００００１」〜「０００００００００００００００１」の範囲に集中する。この場合、連長圧縮すると、記号「３」の出現頻度が高頻度となる。すると、記号「３」に対して最も短い符号を割り当てるようなハフマン符号化を行うことで、Ｄ領域に属する文字に対応する記号列を圧縮可能である。
【０１０５】
Ｅ領域は、連続する０の数が「１６」より多い符号化単位ビット列に集中する。この場合、連長圧縮すると、記号「４」の出現頻度が高頻度となる。すると、記号「４」に対して最も短い符号を割り当てるようなハフマン符号化を行うことで、Ｅ領域に属する文字に対応する記号列を圧縮可能である。
【０１０６】
このように、Ａ、Ｂ、Ｃ、Ｄ、Ｅの領域ごとに個別のハフマン木を生成し、ハフマン符号化が行われる。この場合、出現確率の高い符号化単位ビット列の０の数が多いほど、ハフマン符号化による圧縮の効果が高くなる。そのため、Ａ→Ｂ→Ｃ→Ｄ→Ｅ領域の順に圧縮率が向上する。
【０１０７】
次に、レコード群に対するインデックスの生成および圧縮手順について説明する。
図１３は、インデックスの生成および圧縮処理の手順の一例を示すフローチャートである。以下、図１３に示す処理をステップ番号に沿って説明する。
【０１０８】
［ステップＳ１０１］クローラ１２０内のインデックス生成部１２２は、レコード内に出現する文字を示すビットマップを生成する。この処理の詳細は後述する（図１４参照）。
【０１０９】
［ステップＳ１０２］インデックス生成部１２２は、ビットマップに対する連長圧縮処理を行う。この処理の詳細は後述する（図１６参照）。
［ステップＳ１０３］インデックス生成部１２２は、連長圧縮で得られた記号列に対するハフマン符号化処理を行う。この処理の詳細は後述する（図１８参照）。
【０１１０】
次に、図１３に示す各処理の詳細について説明する。
図１４は、ビットマップ生成処理の手順の一例を示すフローチャートである。以下、図１４に示す処理をステップ番号に沿って説明する。
【０１１１】
［ステップＳ１１１］インデックス生成部１２２は、ビットマップを初期化する。例えばインデックス生成部１２２は、レコード内の文字に適用されているコード体系で表現可能な文字のリストを作成する。インデックス生成部１２２は、初期化したビットマップを、例えばインデックス記憶部１４０に格納する。
【０１１２】
［ステップＳ１１２］インデックス生成部１２２は、インデックス未作成のレコードを１つ読み込む。
［ステップＳ１１３］インデックス生成部１２２は、読み込んだレコードに対応する追加ビットマップを生成する。例えばインデックス生成部１２２は、文字ごとに、読み込んだレコード内に該当文字が出現するか否か（存否）を判断する。インデックス生成部１２２は、出現する文字に関しては、読み込んだレコードと、その文字とに関連付けて「１」の値を設定する。またインデックス生成部１２２は、出現しない文字に関しては、読み込んだレコードと、その文字とに関連付けて「０」の値を設定する。インデックス生成部１２２は、例えば、文字の存否を判定するごとに、存否を示す値をワークメモリ１６０に書き込んでいく。これにより、読み込んだレコードに対応する追加ビットマップ１６２がワークメモリ１６０内に構築される（図６参照）。
【０１１３】
［ステップＳ１１４］インデックス生成部１２２は、生成した追加ビットマップ１６２を、インデックス記憶部１４０内の非圧縮のビットマップ１４２に追加する。
［ステップＳ１１５］インデックス生成部１２２は、インデックスを未作成の他のレコードがあるか否かを判断する。インデックス生成部１２２は、他のレコードがある場合、処理をステップＳ１１２に進める。またインデックス生成部１２２は、他のレコードがなければ、ビットマップ生成処理を終了する。
【０１１４】
図１５は、非圧縮のビットマップの一例を示す図である。ビットマップ１４２には、例えば文字種、文字、グローバルＩＤ（Ｇ−ＩＤ）の欄が設けられている。
文字種の欄には、文字の種別が設定される。文字の欄には、ビットマップ１４２の列のラベルとして、文字が設定される。グローバルＩＤの欄には、ビットマップ１４２の行のラベルとして、グローバルＩＤが設定されている。
【０１１５】
ビットマップ１４２では、各文字の列に、その文字の各ファイルでの存否を示す値が設定されている。例えば、その文字が出現したファイルのグローバルＩＤに対応する位置に「１」が設定され、その文字が出現していないファイルのグローバルＩＤに対応する位置に「０」が設定されている。
【０１１６】
このような非圧縮のビットマップ１４２に対して、まず連長圧縮が行われる。
図１６は、連長圧縮処理の手順の一例を示すフローチャートである。以下、図１６に示す処理をステップ番号に沿って説明する。
【０１１７】
［ステップＳ１２１］インデックス生成部１２２は、ビットマップ１４２から、未処理の文字を１つ選択する。
［ステップＳ１２２］インデックス生成部１２２は、選択した文字の出現確率を計算する。例えばインデックス生成部１２２は、選択した文字のビット列内の「１」の数を、レコードの総数で除算した結果を出現確率とする。インデックス生成部１２２は、例えば、計算した出現確率を、文字に対応付けて管理情報１６３（図６参照）内に設定する。
【０１１８】
［ステップＳ１２３］インデックス生成部１２２は、選択した文字が属する領域を判定する。例えばインデックス生成部１２２は、選択した文字の出現頻度が、図１２に示したような領域のどの領域に含まれるかを判断し、該当する領域を、その文字が属する領域と判定する。インデックス生成部１２２は、例えば、判定した領域を、選択した文字に対応付けて管理情報１６３内に設定する。
【０１１９】
［ステップＳ１２４］インデックス生成部１２２は、選択した文字の出現確率が５０％（０．５）より大きいか否かを判断する。インデックス生成部１２２は、出現確率が５０％より大きい場合、処理をステップＳ１２５に進める。またインデックス生成部１２２は、出現確率が５０％以下の場合、処理をステップＳ１２６に進める。
【０１２０】
［ステップＳ１２５］インデックス生成部１２２は、選択した文字に対応するビット列の各ビットの値を反転する。すなわちインデックス生成部１２２は、「０」のビットを「１」に変更し、「１」のビットを「０」に変更する。
【０１２１】
［ステップＳ１２６］インデックス生成部１２２は、選択した文字に対応するビット列の先頭から順に、符号化単位ビット列を抽出する。図１５の例では、各文字に対応するビット列の左端のビット（グローバルＩＤ「１」のビット）が先頭である。例えばインデックス生成部１２２は、ビット列の先頭から「１」のビットを検索する。ビット列の先頭から、最初に出現した「１」のビットのまでの部分ビット列が、符号化単位ビット列となる。２回目以降は、前回の検索で検出した「１」のビットの次のビットから検索を開始し、最初に出現する「１」のビットを検索する。そして、検索を開始したビットから、最初に出現した「１」のビットまでの部分ビット列を、符号化単位ビット列とする。
【０１２２】
なおインデックス生成部１２２は、ビット列の終端まで「１」のビットを検出できなかった場合、例えば、符号化単位ビット列の抽出は行わずに、次のステップＳ１２７に処理を進める。
【０１２３】
［ステップＳ１２７］インデックス生成部１２２は、抽出した符号化単位ビット列を、図１１に示したような規則で、連長（０が連続する数）に変換する。なおインデックス生成部１２２は、文字列の終端まで「１」のビットが検出されず、符号化単位ビット列が抽出されなかった場合、例えば、終端を示す記号［ＥＯＢ］を、記号列の末尾に追加する。この場合、最後に「１」が検出されたビットの次にビットから終端までは、すべて「０」であるものと認識される。
【０１２４】
［ステップＳ１２８］インデックス生成部１２２は、連長を、０または２の冪乗の整数の和に分解し、０または２の冪乗に対応する記号を並べた記号列に変換する。
［ステップＳ１２９］インデックス生成部１２２は、選択した文字のビット列の終端に達したか否かを判断する。例えばインデックス生成部１２２は、ステップＳ１２６の処理において文字列の終端まで「１」のビットが検出されなかった場合、または検出した「１」のビットがビット列の終端のビットの場合には、終端に達したと判断する。終端に達した場合、処理をステップＳ１３０に進める。またインデックス生成部１２２は、終端に達していなければ、処理をステップＳ１２６に進める。
【０１２５】
［ステップＳ１３０］インデックス生成部１２２は、ビットマップ１４２内に未処理の文字があるか否かを判断する。未処理の文字がある場合、インデックス生成部１２２は、処理をステップＳ１２１に進める。またすべての文字について処理が完了した場合、インデックス生成部１２２は、連長圧縮処理を終了する。この際、インデックス生成部１２２は、例えばワークメモリ１６０内の管理情報１６３をインデックス記憶部１４０に格納する。
【０１２６】
図１７は、連長圧縮後のインデックスの一例を示す図である。ビット列を連長圧縮によって符号化したインデックス１４１は、各文字種の文字に対応付けて、連長圧縮で生成された記号列が設定されている。また、管理情報１４３には、各文字に対応付けて、出現確率と、属する領域とが設定されている。
【０１２７】
次に、ハフマン符号化処理の詳細について説明する。
図１８は、ハフマン符号化処理の手順の一例を示す図である。以下、図１８に示す処理をステップ番号に沿って説明する。
【０１２８】
［ステップＳ１４１］インデックス生成部１２２は、Ａ、Ｂ、Ｃ、Ｄ、Ｅの領域のうちの未処理の領域を１つ選択する。
［ステップＳ１４２］インデックス生成部１２２は、インデックス１４１から、選択した領域に属する文字の記号列を抽出する。この際、インデックス生成部１２２は、選択した領域に対応する反転領域に属する文字の記号列も抽出する。例えば、Ａ領域が選択された場合、Ａ領域とＡ’領域とのいずれかに属する文字の記号列が抽出される。
【０１２９】
［ステップＳ１４３］インデックス生成部１２２は、抽出した記号列における記号ごとの生起確率を計算する。例えばインデックス生成部１２２は、抽出した記号列における、「α，β，１，２，３，・・・，ＥＯＢ」の記号それぞれの出現回数を計数する。そしてインデックス生成部１２２は、記号それぞれの出現回数を、抽出した記号列に含まれる記号の総数で除算し、除算結果を生起確率とする。なお終端を示す記号［ＥＯＢ］の出現回数は、１つの文字に対応する記号列に対して１回である。
【０１３０】
［ステップＳ１４４］インデックス生成部１２２は、記号ごとの葉を生成する。このとき、インデックス生成部１２２は、例えば終端を示す記号［ＥＯＢ］に対応する葉も生成する。生成された葉の構造体には、対応する記号と、その記号の生起確率とが設定される。
【０１３１】
［ステップＳ１４５］インデックス生成部１２２は、選択した領域のハフマン木を生成する。例えばインデックス生成部１２２は、ステップＳ１４４で生成した葉のうち、生起確率が最も小さい２つの葉を選択する。そしてインデックス生成部１２２は、新しい節点を生成し、生成した節点の下位に、選択した葉それぞれを枝で接続する。このとき、一方の枝には「０」、他方の枝には「１」のラベルが付与される。生成した節点には、選択した２つの葉それぞれの生起確率の和を設定する。インデックス生成部１２２は、以後、生成した節点を葉とみなす。そしてインデックス生成部１２２は、生起確率が最も小さい２つの葉の選択、節点の生成、葉の節点への接続処理を、節点の下位に接続されていない葉が１枚になるまで繰り返す。葉が１枚になったときに、最後に残った葉を根とする木構造が、ハフマン木である。
【０１３２】
［ステップＳ１４６］インデックス生成部１２２は、抽出した記号列内の各記号を、ステップＳ１４５で生成したハフマン木に従って、ハフマン符号に変換する。例えばインデックス生成部１２２は、ある記号を符号化する場合、ハフマン木の根からその記号に対応する葉まで枝を辿ったときに、各枝に付与されたラベルの列が、ハフマン符号となる。なおインデックス生成部１２２は、例えば生成したハフマン木を、領域に対応付けて管理情報１６３の一部としてワークメモリ１６０に格納する。
【０１３３】
［ステップＳ１４７］インデックス生成部１２２は、Ａ、Ｂ、Ｃ、Ｄ、Ｅの領域のうち未選択の領域があるか否かを判断する。インデックス生成部１２２は、未選択の領域があれば、処理をステップＳ１４１に進める。またインデックス生成部１２２は、未選択の領域がなければ、ハフマン符号化処理を終了する。この際、インデックス生成部１２２は、例えばワークメモリ１６０の管理情報１６３内のハフマン木を、インデックス記憶部１４０内に、管理情報１４３の一部として格納する。
【０１３４】
このようにして、領域ごとのハフマン木が生成され、領域ごとに異なるハフマン木で、連長圧縮で生成された記号が符号化される。
図１９は、ハフマン木の第１の例を示す図である。図１９には、Ａ領域のハフマン木７０が示されている。ハフマン木７０は、複数の葉７１ａ，７１ｂ，７１ｃ，７１ｄ，７１ｅ，７１ｆ，７１ｇ，７１ｈ，７１ｉと、複数の節点７２ａ，７２ｂ，７２ｃ，７２ｄ，７２ｅ，７２ｆ，７２ｇ，７２ｈとを含んでいる。節点７２ａは、ハフマン木７０の根である。
【０１３５】
葉７１ａは、記号「α」に対応する。葉７１ｂは、記号「β」に対応する。葉７１ｃは、記号「１」に対応する。葉７１ｄは、記号「２」に対応する。葉７１ｅは、記号「３」に対応する。葉７１ｆは、記号「４」に対応する。葉７１ｇは、記号「５」に対応する。葉７１ｈは、記号「６」に対応する。葉７１ｉは、記号［ＥＯＢ］に対応する。
【０１３６】
葉７１ａ，７１ｂ，７１ｃ，７１ｄ，７１ｅ，７１ｆ，７１ｇ，７１ｈ，７１ｉは、いずれかの節点の下に、枝によって接続されている。また節点同士も、枝で接続されている。複数の節点７２ａ，７２ｂ，７２ｃ，７２ｄ，７２ｅ，７２ｆ，７２ｇ，７２ｈのそれぞれには、２つの枝によって、葉または節点が下に接続されている。節点の下の２つの枝のうち、一方には「０」のラベルが付与され、他方には「１」のラベルが付与されている。
【０１３７】
このようなハフマン木７０の根となる節点７２ａから、符号化対象の記号までの経路を辿り、経路上の枝に付与されたラベルを辿った経路に沿って並べることで、その記号に対する圧縮符号（ハフマン符号）が得られる。
【０１３８】
図２０は、記号に対応する圧縮符号の第１の例を示す図である。図２０には、Ａ領域に属する文字に対応する記号列内の記号を、図１９に示したハフマン木７０で符号化した場合の圧縮符号が示されている。
【０１３９】
図２０の例では、記号に対応付けて、ビット列パターン、出現回数、生起確率、補正確率、残確率、圧縮符号長、圧縮符号が示されている。ビット列パターンは、記号に対応する、連長圧縮前のビット列である。出現回数は、Ａ領域に属するすべての文字に対応する記号列内における、対応する記号の出現回数である。生起確率は、Ａ領域に属するすべての文字に対応する記号列内での、記号の生起確率である。
【０１４０】
補正確率は、生起確率を１／２の冪乗の値に補正したときの確率である。例えば、生起確率より小さな１／２の冪乗の値のうちで、最大の値に補正される。生起確率が「０．５２０３」であれば、１／２の１乗、２乗、・・・の各値が、生起確率が「０．５２０３」より小さい。そのうちの最大の値は１／２の１乗（１／２）であるため、生起確率が「０．５２０３」の補正確率は１／２となる。残確率は、生起確率が高い順に補正確率を決定したときに、「１」から、決定した補正確率を減算した結果である。
【０１４１】
圧縮符号長は、記号に対応する圧縮符号のビット数である。圧縮符号は、記号に対応する圧縮符号である。
Ａ領域に属する文字は、ビット列における１の出現確率が、０．２５〜０．５である。そのため、連長圧縮が行われると、記号「α」や「β」の生起確率が高くなる。図２０に示す例では、記号「α」が最も生起確率が高い。そのため、記号「α」は、最も短い圧縮符号「０」に圧縮される。そして、生起確率が低くなるほど、圧縮符号の圧縮符号長が長くなる。
【０１４２】
Ａ領域とは別の領域では、記号の生起確率がＡ領域とは異なる。そのため、Ａ領域以外では、Ａ領域とは異なるハフマン木が生成される。
図２１は、ハフマン木の第２の例を示す図である。図２１には、Ｄ領域のハフマン木８０が示されている。ハフマン木８０は、複数の葉８１ａ，８１ｂ，８１ｃ，８１ｄ，８１ｅ，８１ｆ，８１ｇ，８１ｈ，８１ｉと、複数の節点８２ａ，８２ｂ，８２ｃ，８２ｄ，８２ｅ，８２ｆ，８２ｇ，８２ｈとを含んでいる。節点８２ａは、ハフマン木８０の根である。
【０１４３】
葉８１ａは、記号「α」に対応する。葉８１ｂは、記号「β」に対応する。葉８１ｃは、記号「１」に対応する。葉８１ｄは、記号「２」に対応する。葉８１ｅは、記号「３」に対応する。葉８１ｆは、記号「４」に対応する。葉８１ｇは、記号「５」に対応する。葉８１ｈは、記号「６」に対応する。葉８１ｉは、記号［ＥＯＢ］に対応する。
【０１４４】
Ｄ領域では、各記号の生起確率がＡ領域と異なるため、図１９に示したハフマン木７０とは異なる形態のハフマン木８０が生成されている。そのため、Ｄ領域に属する文字に対応する記号列の各記号を符号化する場合、Ａ領域とは別の圧縮符号に符号化される。
【０１４５】
図２２は、記号に対応する圧縮符号の第２の例を示す図である。図２２には、Ｄ領域に属する文字に対応する記号列内の記号を、図２１に示したハフマン木８０で符号化した場合の圧縮符号が示されている。
【０１４６】
Ｄ領域に属する文字は、ビット列における１の出現確率が、０．０３１５〜０．０６２５である。そのため、連長圧縮が行われると、記号「α」や「β」の生起確率よりも、記号「２」、「３」、「４」の生起確率が高くなる。図２２に示す例では、記号「３」が最も生起確率が高い。そのため、記号「３」は、最も短い圧縮符号「０」に圧縮される。そして、生起確率が低くなるほど、圧縮符号の圧縮符号長が長くなる。
【０１４７】
記号「３」は、元のビット列では、「００００００００」の８ビットである。そのため、Ｄ領域では、８ビットのビット列が、１ビットの圧縮符号に圧縮されることになる。しかも、そのような高圧縮が可能なビット列が頻出している。その結果、高い圧縮率が期待できる。
【０１４８】
領域ごとに生成されたハフマン木により、各領域に属する文字に対応する記号列を符号化することで、圧縮形式のインデックス１４１が生成される。
図２３は、圧縮形式のインデックスの例を示す図である。インデックス１４１には、文字種に分類された文字それぞれに対応付けて、圧縮符号列が設定されている。圧縮符号列は、図１７に示した記号列の各記号を、ハフマン符号に変換したものである。
【０１４９】
例えば、図１７の管理情報１４３を参照すると、文字「あ」は、Ａ’領域に属する。Ａ’領域に属する文字は、Ａ領域と同じハフマン木で符号化される。文字「あ」に対応する記号列の先頭の記号列は「２β」である。図２０を参照すると、記号「２」は「１１１０」の圧縮符号に符号化され、記号「β」は「１０」の圧縮符号に符号化される。そのため、「２β」は、「１１１０１０」に符号化される。
【０１５０】
以上のようにして、インデックスが圧縮される。その結果、少ない記憶容量のメモリにインデックスを格納することができる。第２の実施の形態に示したインデックスの圧縮技術には、例えば、携帯端末装置に辞書データを格納し、インデックスを用いた検索を行う場合に有用である。
【０１５１】
次に、サーチャ１３０（図４参照）による全文検索処理の手順について説明する。
図２４は、全文検索処理の手順の一例を示すフローチャートである。以下、図２４に示す処理をステップ番号に沿って説明する。
【０１５２】
［ステップＳ２０１］サーチャ１３０は、端末装置２１などから送られる検索文字列を取得する。
［ステップＳ２０２］サーチャ１３０は、検索文字列に含まれる文字のうち、未選択の文字を１つ選択する。
【０１５３】
［ステップＳ２０３］サーチャ１３０は、インデックス記憶部１４０内のインデックス１４１から、選択した文字に対応する圧縮符号列を取得する。
［ステップＳ２０４］サーチャ１３０は、選択した文字が属する領域を判断する。例えばサーチャ１３０は、管理情報１４３から、文字と領域との対応関係を示す情報（図１７参照）を取得し、その情報に基づいて、選択した文字が属する領域を判断する。
【０１５４】
［ステップＳ２０５］サーチャ１３０は、管理情報１４３の一部としてインデックス記憶部１４０に格納されている複数のハフマン木から、選択した文字が属する領域のハフマン木を抽出する。
【０１５５】
［ステップＳ２０６］サーチャ１３０は、選択した文字の圧縮符号列を、抽出したハフマン木を用いてビット列に復号する。例えばサーチャ１３０は、圧縮符号列のビットを先頭から順に選択する。次にサーチャ１３０は、抽出したハフマン木の根の節点から順に、選択したビットの値に対応するラベルが付与された枝で接続された葉または節点に、木構造を辿る。節点に達したときは、サーチャ１３０は、その節点から、次のビットの値に対応するラベルが付与された枝で接続された葉または節点に、木構造を辿る。このようにサーチャ１３０は、圧縮符号列のビットの値に従って、ハフマン木の木構造を辿る。そしてサーチャ１３０は、葉に到達した場合、根から葉に到達するまでの枝のラベルに対応する圧縮符号を、到達した葉に対応付けられた記号で示されるビット列に変換する。
【０１５６】
このような圧縮符号からビット列への変換が、選択した文字に対応する圧縮符号列内のすべての圧縮符号について行われる。なおサーチャ１３０は、終端を示す記号［ＥＯＢ］が対応付けられた葉に到達した場合、例えば、直前に復号して得られたビット列の後に、復号されたビット列の長さがレコード数に達するまで、「０」のビットを追加する。
【０１５７】
［ステップＳ２０７］サーチャ１３０は、選択した文字の属する領域が反転領域（Ａ’、Ｂ’、Ｃ’、Ｄ’、Ｅ’）か否かを判断する。サーチャ１３０は、反転領域であれば処理をステップＳ２０８に進める。またサーチャ１３０は、反転領域でなければ処理をステップＳ２０９に進める。
【０１５８】
［ステップＳ２０８］サーチャ１３０は、ステップＳ２０６で復号したビット列の各ビットの値を反転する。すなわちサーチャ１３０は、「０」のビットの値を「１」に変更し、「１」のビットの値を「０」に変更する。
【０１５９】
［ステップＳ２０９］サーチャ１３０は、検索文字列内の文字のうち、未処理の文字があるか否かを判断する。サーチャ１３０は、未処理の文字がある場合、処理をステップＳ２０２に進める。またサーチャ１３０は、すべての文字について処理が終了した場合、処理をステップＳ２１０に進める。
【０１６０】
［ステップＳ２１０］サーチャ１３０は、復号されたビット列に基づいて、検索文字列中のすべての文字が出現するレコードのグローバルＩＤを特定する。検索文字列中のすべての文字が出現するレコードは、復号したすべての文字のビット列において「１」が設定されているレコードである。
【０１６１】
例えば検索文字列が「森鴎外」であり、図８に示すようなビット列６１〜６３が復号された場合を考える。図８の例では、すべてのビット列において、９ビット目の値は「１」である。従って、９番目のレコードのグローバルＩＤ「９」が、検索文字列中のすべての文字が出現するレコードのグローバルＩＤとして特定される。
【０１６２】
［ステップＳ２１１］サーチャ１３０は、インデックス記憶部１４０から、検索文字列を構成する文字のビットマップを読み込み、該当するグローバルＩＤの絞込みを行う。特定されたグローバルＩＤに対応するレコードを、圧縮データ記憶部１５０から抽出する。例えば管理情報１４３には、グローバルＩＤと、そのグローバルＩＤに対応するレコードの圧縮データ記憶部１５０内でのアドレスとが対応付けて設定されている。サーチャ１３０は、管理情報１４３を参照し、特定したグローバルＩＤに対応するアドレスを判断し、圧縮データ記憶部１５０から、該当アドレスに格納されている圧縮データを取得する。そしてサーチャ１３０は、取得した圧縮データを復号する。これにより、平文のレコードが取得できる。
【０１６３】
［ステップＳ２１２］サーチャ１３０は、抽出したレコード内から、検索文字列を照合する。
［ステップＳ２１３］サーチャ１３０は、検索結果を出力する。例えばサーチャ１３０は、検索文字列を含むレコードのグローバルＩＤ、そのレコードのタイトル、検索文字列を含む文などを検索結果として、端末装置２１に送信する。これにより、端末装置２１では、検索結果が画面に表示される。
【０１６４】
このようにして、インデックス１４１を用いた全文検索が行われる。
以上のように、第２の実施の形態では、符号化単位ビット列を、所定のビット列パターンに分解し、分解して得られたビット列パターンをハフマン木の葉に割り当てている。これにより、葉の数を減少させることが可能となり、ハフマン木の生成、およびハフマン木を用いた符号化や復号を高速に行うことができる。
【０１６５】
また、第２の実施の形態では、ビット列パターンを記号に置き換えて圧縮処理を実行するため、ビットマップの読み出しが１回で済む。このようなビットマップの読み出しの１パス化により、圧縮処理の高速化が図られている。例えは、ビット列パターンの記号への置き換えを行わない場合、最初のビットマップの読み出しにおいて、文字ごとの「０」、「１」の密度を集計し、各文字が属する領域が判断される。次に、ビットマップの２回目の読み出しを行い、ハフマン符号化が行われる。他方、第２の実施の形態では、ビットマップを読み出して、文字ごとの「０」、「１」の密度を集計し、各文字が属する領域の判断時に、ビット列を記号列に変換する。そして記号列に基づいてハフマン符号化が行われる。記号列は、ビットマップに比べてデータ量が少なくなっているため、メモリからの読み出し時間は短くて済む。その結果、圧縮処理が高速化される。
【０１６６】
〔第３の実施の形態〕
次に第３の実施の形態について説明する。第３の実施の形態は、符号化の木として、第２の実施の形態で示したハフマン木に代えて、無節点の木を用いるものである。なお、第３の実施の形態におけるシステム構成は、図２、図３に示した第２の実施の形態の構成と同様である。また第３の実施の形態におけるＡＰサーバの機能の構成要素も、図４、図６に示した第２の実施の形態の構成要素と同様である。そこで、第２の実施の形態で示した各要素の符号を用いて、第３の実施の形態における、第２の実施の形態と異なる機能について説明する。
【０１６７】
第３の実施の形態では、クローラ１２０は、ハフマン木に代えて無節点の木を用いてインデックスの圧縮を行う。またサーチャ１３０は、ハフマン木に代えて無節点の木を用いてインデックスの伸張を行う。
【０１６８】
無節点の木は、ハフマン木と同様に、出現頻度が高い記号ほど、短い符号に符号化するものである。ただし、ハフマン木は、根（ルート）の下位に複数の節点が設けられるのに対して、無節点の木では、根の下位に節点は設けられず、すべての葉が根の下位に直接接続される。このような構造の無節点の木を用いると、圧縮符号を１パスで伸張することが可能となり、伸張速度が向上する。
【０１６９】
無節点の木を生成する際には、例えば各記号の生起確率に応じて、符号化時の符号長が決定される。例えば、クローラ１２０のインデックス生成部１２２は、図２０や図２２に示したように、各記号の出現回数を計数し、生起確率を求める。そして、インデックス生成部１２２は、出現頻度に基づいて補正確率を求める。補正確率は、例えば、「１／２」の冪乗のうち、生起確率以下の最も大きな数である。例えば、出現頻度「０．１３７」の場合、「１／４（０．２５）」より小さく、「１／８（０．１２５）」より大きい。そこで出現頻度「０．１３７」の補正確率は「１／８」となる。
【０１７０】
次にインデックス生成部１２２は、補正確率に基づいて、符号長を求める。符号長は、符号のビット数である。例えば補正確率を「１／２」の冪乗で表したときの指数（何乗か）が、符号長とされる。補正確率「１／８」であれば、「１／２」の３乗であることから、符号長は「３」となる。
【０１７１】
インデックス生成部１２２は、各整数の圧縮符号を、その記号の出現頻度に応じて決定した符号長の符号に決定する。例えば符号長が「３」であれば、圧縮符号は「０００」、符号長が「４」であれば、圧縮符号は「００１０」となる。すると各記号について、図２０、図２２に示された圧縮符号と同様の圧縮符号が生成される。
【０１７２】
このような記号と圧縮符号との対応関係に基づいて、無節点の木を生成することができる。例えば図２２に示すような、圧縮符号に決定された場合、図２５に示すような無節点の木が生成される。
【０１７３】
図２５は、無節点の木の一例を示す図である。無節点の木９０には、根９１と複数の葉９２ａ，９２ｂ，９２ｃ，９２ｄ，９２ｅ，９２ｆ，９２ｇ，９２ｈ，９２ｉが設けられている。根９１の直下に葉９２ａ，９２ｂ，９２ｃ，９２ｄ，９２ｅ，９２ｆ，９２ｇ，９２ｈ，９２ｉが設けられており、ハフマン木にあるような節点は存在しない。ここで葉９２ａ，９２ｂ，９２ｃ，９２ｄ，９２ｅ，９２ｆ，９２ｇ，９２ｈ，９２ｉそれぞれの識別番号を、左から順に１，２，３，４，５，６，７，８，９とする。
【０１７４】
根の構造体９３には、６ビットで表せるアドレスに対応する各領域に、葉９２ａ，９２ｂ，９２ｃ，９２ｄ，９２ｅ，９２ｆ，９２ｇ，９２ｈ，９２ｉへのポインタが設定されている。葉の構造体９４，９５には、例えば対応する葉９２ａ，９２ｆの識別番号、圧縮符号長、圧縮符号、記号、ビット列パターンなどが設定されている。
【０１７５】
ここで根の構造体９３においては、圧縮符号長が短い葉ほど、多くのポインタが設定される。例えば葉９２ａの圧縮符号長は「１」、圧縮符号は「０」である。この場合、「００００００」〜「０１１１１１」のアドレス範囲のすべての領域に、葉９２ａへのポインタが設定される。また葉９２ｆの圧縮符号長は「４」である。この場合、「１１１０００」〜「１１１０１１」のアドレス範囲のすべての領域に、葉９２ｆへのポインタが設定される。
【０１７６】
このような無節点の木９０によれば、復号を１パスで行うことができる。例えばサーチャ１３０は、復号対象の符号列の先頭の６ビットの値を取得し、根の構造体９３の先頭から、取得した値をオフセットとした領域に格納されているポインタを参照する。次にサーチャ１３０は、参照したポインタで示されている葉の構造体を参照する。そしてサーチャ１３０は、取得した６ビットのうち、参照した葉の構造体に示されている圧縮符号長で示されるビット数分の先頭ビットを、参照した葉の構造体に示されているビット列パターンに復号する。その後、サーチャ１３０は、復号していない符号列の先頭６ビットを再度取得し、同様に復号する。
【０１７７】
例えば、取得した６ビットの値が「１１１０００」であれば、対応するオフセットの領域が参照される。その領域には、葉９２ｆに対応する葉の構造体９５へのポインタが設定されている。葉の構造体９５には、圧縮符号長が「４」であること、ビット列パターン「１」に復号することが示されている。そこでサーチャ１３０は、６ビットの値「１１１０００」のうちの先頭の４ビット「１１１０」をビット列パターン「１」に復号する。
【０１７８】
このように、無節点の木９０を用いて復号することで、根９１から１パスで目的の葉を検出し、復号することができる。すなわち無節点の木９０により、圧縮データを１ビットごとでなく、６ビットをまとめた１回の判定で、葉の構造体を獲得することができる。これにより、ハフマン木を用いた復号のような、根からの節点を辿るための複数の判断が不要となり、圧縮された符号を高速に伸張することができる。
【０１７９】
次に、第３の実施の形態により実際に辞書データのビットマップ形式のインデックスを圧縮した場合の例について説明する。なお、以下の例では、１／２の冪乗に補正した補正確率を、圧縮率が向上するようにさらに補正している。このような補正を、二次補正と呼ぶこととする。二次補正は、各記号の補正確率の合計が１を超えない範囲で、補正確率を、より大きい値に変更する処理である。なお、二次補正後の補正確率も、１／２の冪乗の値である。例えばサーチャ１３０は、記号を選択し、生起確率に基づいて求めた補正確率を２倍したときに、すべての記号の補正確率の合計が１を超えるか否かを判断する。１を超えない場合、サーチャ１３０は、選択した記号の補正確率を、２倍の値に補正する。
【０１８０】
記号の補正確率が高くなると、その記号に対応する圧縮符号の符号長は短くなる。その結果、圧縮率が向上する。
以下に、ある国語辞書のビットマップ形式のインデックスを圧縮した場合の圧縮例を示す。以下に示す例では、１の出現率に応じた領域を、図１２に示した例よりも細かく設け、１６個の領域に分割している。以下の例では、Ａ〜Ｄ領域、Ａ’〜Ｄ’領域の範囲は図１２に示す通りとし、Ｅ領域とＥ’領域を細分化している。「１」の出現率が０以上１／２５６未満の範囲を、Ｈ領域としている。「１」の出現率が１／２５６以上１／１２８未満の範囲を、Ｇ領域としている。「１」の出現率が１／１２８以上１／６４未満の範囲を、Ｆ領域としている。「１」の出現率が１／６４以上１／３２未満の範囲を、Ｅ領域としている。「１」の出現率が３１／３２より大きく６３／６４以下の範囲を、Ｅ’領域としている。「１」の出現率が６３／６４より大きく１２７／１２８以下の範囲を、Ｆ’領域としている。「１」の出現率が１２７／１２８より大きく２５５／２５６以下の範囲を、Ｇ’領域としている。「１」の出現率が２５５／２５６より大きく１以下の範囲を、Ｈ’領域としている。
【０１８１】
Ａ’〜Ｈ’領域は、ビットの値を反転して、それぞれＡ〜Ｈ領域として符号化が行われる。そこで、Ａ〜Ｈ領域の圧縮結果の例を、図２６〜図３３に示す。
図２６〜図３３には、記号に対応付けて、ビット長、出現回数、ビットサイズ、および生起確率が示されている。ビット長は、記号に対応するビット列パターンのビット数である。出現回数は、記号に対応するビット列パターンが、該当領域に属する文字のビット列内に出現した回数である。ビットサイズは、該当領域に属する文字のビット列内の、記号に対応するビット列パターンの全ビット数である。なおビットサイズは、出現回数にビット長を乗算することで得られる。生起確率は、該当領域に属する文字のビット列内におけるビット列パターンが、記号に対応するビット列パターンであることの確率である。
【０１８２】
また図２６〜図３３には、記号に対応付けて、二次補正無しの場合と二次補正有りの場合とのそれぞれにおける、補正確率、符号長、および符号サイズが示されている。二次補正無しの場合の補正確率は、記号の生起確率を、１／２の冪乗の値のうち、生起確率以下の最大である。二次補正有りの場合の補正確率は、二次補正無しの場合のいずれかの記号の補正確率に対し、補正確率の合計が１を超えない範囲で、２を乗算したものである。符号長は、補正確率に応じて決定される符号のビット数である。符号サイズは、該当領域に属する文字のビット列内の記号に対応するビット列パターンを、記号を補正確率に応じて符号化した場合の、符号を表す全ビット数である。なお符号サイズは、出現回数に符号長を乗算することで得られる。
【０１８３】
さらに図２６〜図３３には、二次補正無しの場合と二次補正有りの場合とのそれぞれにおける、圧縮率が示されている。圧縮率は、該当領域に属する文字の圧縮前のサイズの合計に対する、圧縮後のサイズの合計の割合である。圧縮率は、符号サイズの合計をビットサイズの合計で除算することで得られる。
【０１８４】
図２６は、Ａ領域の圧縮結果の一例を示す図である。Ａ領域の圧縮では、ビット長が短いビット列パターンほど生起確率が高い。そのため、二次補正無しの場合、圧縮率が１以上となっている。二次補正では、記号「β」に対応する補正確率が、「０．１２５０」から「０．２５００」に補正されている。これにより、記号「β」で示されるビット列パターンに対応する符号の符号長が、「３」から「２」に短縮される。また記号「３」に対応する補正確率が、「０．０１５６」から「０．０３１３」に補正されている。これにより、記号「３」で示されるビット列パターンに対応する符号の符号長が、「６」から「５」に短縮される。同様に、記号「４」〜「９」についても、二次補正により補正確率が２倍され、符号長が短縮されている。その結果、二次補正後の補正確率に基づいて符号長を決定し、符号化を行った場合、圧縮率が約０．９となっている。
【０１８５】
図２７は、Ｂ領域の圧縮結果の一例を示す図である。Ｂ領域の圧縮でも、Ａ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＢ領域では、Ａ領域と比べ、ビット長が長いビット列パターンの割合が増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．８６となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．７２となっている。
【０１８６】
図２８は、Ｃ領域の圧縮結果の一例を示す図である。Ｃ領域の圧縮結果でも、Ａ、Ｂ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＣ領域では、Ｂ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．６０となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．５２となっている。
【０１８７】
図２９は、Ｄ領域の圧縮結果の一例を示す図である。Ｄ領域の圧縮でも、Ａ、Ｂ、Ｃ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＤ領域では、Ｃ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．３８となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．３４となっている。
【０１８８】
図３０は、Ｅ領域の圧縮結果の一例を示す図である。Ｅ領域の圧縮でも、Ａ、Ｂ、Ｃ、Ｄ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＥ領域では、Ｄ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．２３となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．２１となっている。
【０１８９】
図３１は、Ｆ領域の圧縮結果の一例を示す図である。Ｆ領域の圧縮でも、Ａ、Ｂ、Ｃ、Ｄ、Ｅ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＦ領域では、Ｅ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．１４となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．１３となっている。
【０１９０】
図３２は、Ｇ領域の圧縮結果の一例を示す図である。Ｇ領域の圧縮でも、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＧ領域では、Ｆ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．０９となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．０８となっている。
【０１９１】
図３３は、Ｈ領域の圧縮結果の一例を示す図である。Ｈ領域の圧縮でも、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ領域と同様に、ビット長が短いビット列パターンほど生起確率が高い。ただしＨ領域では、Ｇ領域と比べ、ビット長が長いビット列パターンの割合がさらに増加している。その結果、二次補正を行わない場合であっても、圧縮率が約０．０２０となっている。また二次補正を行うことで、圧縮率はさらに低減し、約０．０１８となっている。
【０１９２】
このように、ビットマップ中のビット列パターンを、生起確率の高い要素ほど短い符号に符号化する符号化方式によって符号化することで、ビットマップ形式のインデックスに対して、高い圧縮率の圧縮と行うことができる。
【０１９３】
〔その他の実施の形態〕
第２の実施の形態では、連続する０の数が２の冪乗となるビット列を、ビット列パターンとしたが、別の法則でビット列パターンを決定することもできる。例えば連続する０の数が３の冪乗となるビット列を、ビット列パターンとすることもできる。この場合、ビット列「１」を示す記号「α」、ビット列「０１」を示す記号「β」に加え、ビット列「００１」を示す記号「γ」を定義する。また連続するビットの数を、その数の示す３の冪乗の指数の記号で表す。これにより、すべての符号化単位ビット列（０個以上の「０」の連続と「１」）を、記号の組み合わせで表現できる。
【０１９４】
また、第２の実施の形態では、文字の出現率が５割より高い、高密度の文字について、ビット列の各ビットの値を反転しているが、逆に、文字の出現率が５割以下、低密度の文字について、ビット列の各ビットの値を反転することもできる。この場合、Ａ〜Ｅの各領域ではなく、Ａ’〜Ｅ’の領域ごとにハフマン木が生成される。
【０１９５】
また、第２の実施の形態では、レコードに対する文字の存否を示すビットマップを圧縮しているが、他の形式のデータであっても同様に圧縮可能である。例えば、イメージスキャナで画像を読み取ることで得られたビットマップデータを圧縮することが可能である。
【０１９６】
なお、上記の各実施の形態に示した処理機能は、コンピュータによって実現することができる。その場合、ＡＰサーバ１００が有する機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷなどがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。なおプログラムを記録する記録媒体には、一時的な伝搬信号自体は含まれない。
【０１９７】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１９８】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１９９】
また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現することもできる。
【０２００】
上記については単に本発明の原理を示すものである。さらに、多数の変形、変更が当業者にとって可能であり、本発明は上記に示し、説明した正確な構成および応用例に限定されるものではなく、対応するすべての変形例および均等物は、添付の請求項およびその均等物による本発明の範囲とみなされる。
【符号の説明】
【０２０１】
１  圧縮手段
１ａ  第１の符号化手段
１ｂ  分解手段
１ｃ  分類手段
１ｄ  計算手段
１ｅ  第２の符号化手段
２  記録媒体
２ａ  圧縮データ
２ｂ  管理情報
３  伸張手段
３ａ  第１の取得手段
３ｂ  第２の取得手段
３ｃ  復号手段
４  圧縮対象データ
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピュータに、
圧縮対象データにおける同じ値が連続する部分を、同じ値が連続する回数に符号化し、
同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解し、
分解して得られた各整数の生起確率を計算し、
生起確率が高い整数ほど短い符号となるように、各整数を符号化する、
処理を実行させるプログラム。
【請求項２】
前記整数群には、０および特定の整数の冪乗の値が属しており、
前記コンピュータに、
整数の符号化では、前記整数群に属する整数それぞれに対応する葉を有する符号化の木を用いて、符号化を行う、
処理を実行させることを特徴とする請求項１記載のプログラム。
【請求項３】
前記圧縮対象データは、複数の文字それぞれが、文字列を含む複数のレコードそれぞれに存在するか否かを示す、文字ごとのビット列の集合であり、
前記コンピュータに、
前記複数の文字のそれぞれを、対応するビット列内における、文字が存在することを示すビット値の割合に応じて複数の集合のいずれかに分類し、
生起確率の計算では、集合ごとに、該集合に属する文字に対応するビット列から得られた整数における、前記整数群に属する整数それぞれの生起確率を計算し、
整数の符号化では、集合ごとに、該集合に属する文字に対応するビット列から得られた整数を、該集合に関して計算された生起確率に基づいて符号化する、
処理を実行させることを特徴とする請求項１または２のいずれかに記載のプログラム。
【請求項４】
前記コンピュータに、
文字が存在することを示すビット値の割合が５割を超えているビット列に対応する文字と、文字が存在することを示すビット値の割合が５割未満のビット列に対応する文字との、いずれか一方の文字については、対応するビット列内のビット値を反転させ、
同じ値が連続する回数への符号化では、ビット値反転対象の文字については、反転後のビット値を用いて、圧縮対象データにおける同じ値の連続を、同じ値が連続する回数に符号化する、
処理を実行させることを特徴とする請求項３記載のプログラム。
【請求項５】
コンピュータに、
圧縮対象データを圧縮して得られた圧縮符号列を取得し、
前記圧縮符号列では、予め定めた整数群に属する整数の和によって、同じ値が連続する回数が表され、生起確率が高い整数ほど短い符号に符号化されており、前記整数群に属する各整数と符号との対応関係を示す管理情報を取得し、
前記取得した管理情報に基づいて、前記取得した圧縮符号列内の符号を復号する、
処理を実行させるプログラム。
【請求項６】
前記コンピュータに、
整数と符号との対応関係を示す情報の取得では、根の直下に複数の葉が接続されており、根から遷移する葉が符号に応じて決められており、前記複数の葉それぞれに整数が設定された、符号化の木を取得し、
符号の復号では、前記取得した符号化の木に基づいて、前記取得した圧縮符号列内の符号を、該符号に対応する葉に設定された整数で示される回数だけ同じ値が連続するデータに復号する、
処理を実行させる請求項５記載のプログラム。
【請求項７】
コンピュータが、
圧縮対象データにおける同じ値が連続する部分を、同じ値が連続する回数に符号化し、
同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解し、
分解して得られた各整数の生起確率を計算し、
生起確率が高い整数ほど短い符号となるように、各整数を符号化する、
ことを特徴とする圧縮データ生成方法。
【請求項８】
コンピュータが、
圧縮対象データを圧縮して得られた圧縮符号列を取得し、
前記圧縮符号列では、予め定めた整数群に属する整数の和によって、同じ値が連続する回数が表され、生起確率が高い整数ほど短い符号に符号化されており、前記整数群に属する各整数と符号との対応関係を示す管理情報を取得し、
前記取得した管理情報に基づいて、前記取得した圧縮符号列内の符号を復号する、
ことを特徴とする伸張方法。
【請求項９】
圧縮対象データにおける同じ値が連続する部分を、同じ値が連続する回数に符号化する第１の符号化手段と、
同じ値が連続する回数を、予め定めた整数群に属する整数の和に分解する分解手段と、
分解して得られた各整数の生起確率を計算する計算手段と、
生起確率が高い整数ほど短い符号となるように、各整数を符号化する第２の符号化手段と、
を有する情報処理装置。
【請求項１０】
圧縮対象データを圧縮して得られた圧縮符号列を取得する第１の取得手段と、
前記圧縮符号列では、予め定めた整数群に属する整数の和によって、同じ値が連続する回数が表され、生起確率が高い整数ほど短い符号に符号化されており、前記整数群に属する各整数と符号との対応関係を示す管理情報を取得する第２の取得手段と、
前記取得した管理情報に基づいて、前記取得した圧縮符号列内の符号を復号する復号手段と、
を有する情報処理装置。
【請求項１１】
圧縮対象データを圧縮した圧縮データを記憶するコンピュータ読み取り可能な記録媒体において、
前記圧縮データには、予め定めた整数群に属する整数に対応する符号が含まれており、
整数は、前記圧縮対象データにおける同じ値が連続する部分を、同じ値が連続する回数に符号化し、同じ値が連続する回数を、前記整数群に属する整数の和に分解して得られたものであり、
符号は、分解して得られた整数において、生起確率が高い整数ほど短い符号となるように、各整数を符号化したものである、
ことを特徴とする記録媒体。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図１７
【補正方法】変更
【補正の内容】
【図１７】
2013140530.tif 000036
【手続補正４】
【補正対象書類名】図面
【補正対象項目名】図２０
【補正方法】変更
【補正の内容】
【図２０】
2013140530.tif 000037
【手続補正５】
【補正対象書類名】図面
【補正対象項目名】図２２
【補正方法】変更
【補正の内容】
【図２２】
2013140530.tif 000038
【手続補正６】
【補正対象書類名】図面
【補正対象項目名】図２４
【補正方法】変更
【補正の内容】
【図２４】
2013140530.tif 000039
【手続補正７】
【補正対象書類名】図面
【補正対象項目名】図３３
【補正方法】変更
【補正の内容】
【図３３】
2013140530.tif 000040
【国際調査報告】
2013140530.tif 000041
2013140530.tif 000042
2013140530.tif 000043
2013140530.tif 000044