JPH11284518A - 前処理付きデータ圧縮方法および圧縮データの伸長方法 - Google Patents

Abstract

(57)【要約】 【課題】データ圧縮の圧縮率を高める。 【解決手段】データをフィールド毎に分離し、分離した
結果に適切な前処理を加えた後に各々分離したデータを
圧縮し、その結果を結合する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、データ処理におい
てデータ量の縮小化を図り、データ格納コストやデータ
通信コストの削減などに係わるデータ圧縮方法および圧
縮データの伸長方法に関する。

【０００２】

【従来の技術】従来、データ圧縮では、奥村晴彦著「Ｃ
言語による最新アルゴリズム辞典」技術評論社（１９９
１年）の１９２項にあるように、データの内部構造を考
える事無く、データ圧縮技法を適用してデータ圧縮を行
っていた。例えば図４の３１に示されるデータの場合、
これを、D8A7A5A3E2C1或いは、DAAAEC875321なる１つの
データとみなして圧縮技法を適用していた。

【０００３】

【発明が解決しようとする課題】しかしながら、被圧縮
データは必ずしも１フィールドだけから出来ているとは
限らず、複数フィールドより構成される場合があり、更
に、フィールドの中には大きい順にソートされていると
いった特徴を持つものがある。従って、データ圧縮によ
るデータ量の削減効果を上げるためには、これらデータ
の持つ特徴を生かす必要がある。例えば図４の３１に示
されるデータの場合、データ圧縮では同一の文字または
同一パターンの繰り返しが圧縮の対象となるため、ＡＡ
Ａの部分しか圧縮の対象とならない。

【０００４】

【課題を解決するための手段】１個または複数のフィー
ルドよりなるデータが多数集まって構成しているデータ
群に対して、前記データ群を各フィールド毎のデータ群
に分離する手段と、前記分離されたデータ群に対する圧
縮手段と、前記分離されたデータ群に対して前処理を行
う手段と、前記分離されたデータ群に対して前処理を行
った結果に対して圧縮処理を行う手段と、前記分離され
たデータ群に対して、圧縮処理を行った結果および前処
理を行った後に圧縮した結果を結合する手段とを有する
事を特徴とする前処理付きデータ圧縮方法によって行
う。

【０００５】

【発明の実施の形態】本発明に係わる前処理付きデータ
圧縮方法および伸長方法の実施例を図を用いて詳細に説
明する。

【０００６】図１は本発明の実施例を示したブロック図
であり、データ処理の流れを表わす。図中、１は元デー
タであり、これは被圧縮データである。２はデータ分離
処理を表わしており、図４の３１にある様な複数フィー
ルドからなるデータを図４の３２，３３にある様に各フ
ィールド毎に分離する。ただし、１の元データが１つの
フィールドだけの場合は何もしない。３は前処理１であ
り、４は前処理２を表わし、ここで、圧縮に先立って前
処理が行われる。ただし、この前処理においては、何も
処理を行わない場合も含む。５は圧縮処理１であり、６
は圧縮処理２である。ただし、ここでも圧縮方法とし
て、圧縮しない場合も含む。７はデータ結合であり、５
と６で圧縮された結果に対して、図３の２１で示すヘッ
ダを付けて結合する。

【０００７】図１でのデータの処理の流れは図３と図４
を用いて示す必要があるため、図３と図４の説明をす
る。

【０００８】図３はヘッダの構造を示した図であり、図
中２１はヘッダを表わす。２１のヘッダはヘッダ長を示
すフィールド、圧縮方法を示すフィールド、前処理を示
すフィールド、圧縮データの先頭へのポインタよりな
る。ここで、ヘッダ長はヘッダの先頭から圧縮データの
先頭へのポインタまでの長さを格納する。この長さによ
って、図１の元のデータ１が何個のフィールドに分離し
て圧縮されているかが分かる。図３の２１ではヘッダ長
はヘッダの先頭から、圧縮データ２の先頭へのポインタ
までの長さが格納されている実施例である。

【０００９】圧縮方法１および圧縮方法２では、それぞ
れ２つに分離したフィールドの各々に対してどのような
圧縮方法が用いられたかを示す圧縮方法の種類が格納さ
れる。データの性質によっては圧縮が不要、または圧縮
すると逆にデータが増大する場合があるため、圧縮しな
い場合をも圧縮方法の種類に含めておく。一般的に圧縮
は全てのデータに効果がある訳ではなく、データの性質
によっては逆効果になる場合も多く、特に乱数データに
対しては逆効果になる場合が多い。

【００１０】前処理１および前処理２では圧縮に先立っ
て行われる前処理の種類を格納する。ここでも、前処理
が逆効果になる場合も考慮し、何もしない場合も前処理
の種類に含めておく。前処理として通常使われる方法
は、差分，和分，排他論理和であるが、逆変換処理の存
在するものなら何でも使用できる。使用にあたっては次
の圧縮処理の際に圧縮効果があるものを選ぶ事である。

【００１１】圧縮データ１の先頭および圧縮データ２の
先頭では、２つのフィールドに分離されて、各々が処理
され圧縮された結果を結合した場合のそれぞれの先頭へ
のポインタが格納される。

【００１２】図４は図１の各処理に対応するデータの流
れを示したものである。図中３１は２つのフィールドか
らなる元データであり、これは図１の元データ１であっ
て、第２フィールドのデータは値が大きい順にソートさ
れている。３２は図１のデータ分離によって分離された
データの第１フィールドであり、３３は分離されたデー
タの第２フィールドである。前処理データ３４は分離デ
ータ３２が図１の前処理１によって処理された結果であ
るが、特に分離データ３２は有効な前処理が存在する訳
ではないので、前処理１として何もしない場合の結果で
ある。従って、３２と３４は全く同一のデータになって
いる。前処理データ３５は３３の分離データに対して、
前処理２として差分を用いた場合の結果である。

【００１３】これを詳しく説明すると、分離データ３３
の先頭データである「８」は先頭データであるため何も
せず前処理データ３５の先頭に格納する。３３の２番目
のデータである「７」は３３の先頭である「８」との差
分が取られ、その結果である「１」が前処理データ３５
の２番目のデータとして格納される。３３の３番目のデ
ータである「５」は３３の２番目である「７」との差分
が取られ、その結果である「２」が３５の３番目のデー
タとして格納される。以下同様に差分が取られ、前処理
データ３５が得られる。この結果に見られるように、圧
縮の対象となり難いデータである分離データ３３が差分
のような前処理によって、前処理データ３５のように同
一文字が繰り返し出現して圧縮の対象となり得るデータ
に変換される。

【００１４】圧縮データ３６は前処理データ３４に対し
て、図１の圧縮処理１によって圧縮した結果である。こ
の圧縮処理にはランレングス法やハフマン法等の既存の
圧縮処理が用いられる。圧縮データ３７は前処理データ
３５に対して、図１の圧縮処理２によって圧縮した結果
である。この圧縮処理にはランレングス法やハフマン法
等の既存の圧縮処理が用いられる。

【００１５】圧縮方法については、圧縮結果がデータの
特徴に依存して変わる事から、図１の圧縮処理１と圧縮
処理２とは同じ圧縮方法であっても異なる圧縮方法であ
ってもよい。データに依存して圧縮方法は適切なものを
選択すればよい。

【００１６】圧縮データ３８は２つの圧縮結果３６，３
７に対して、図１のデータ結合７によって、図３のヘッ
ダ２１を先頭に付加して、３６の圧縮結果１，３７の圧
縮結果２をこの順に結合して得た結果であり、図１の圧
縮データ８である。

【００１７】以上が圧縮データに至るまでのデータ流れ
であるが、次に、図２によって伸長の方法を示す。

【００１８】図２は伸長方法を示したブロック図であ
り、伸長処理におけるデータの流れを表わす。図中、１
１は圧縮データであり、これは図４の３８のフォーマッ
トである。１２はデータ分離であり、１１のデータをヘ
ッダから２つの圧縮データに分離する。１３は伸長処理
１であり、分離されたデータの圧縮処理に対応した伸長
処理を行う。１４は伸長処理であり、分離されたデータ
の圧縮処理に対応した伸長処理を行う。１５は後処理１
であり、圧縮に先立って行われた前処理に対応する逆処
理を行う。１６は後処理２であり、圧縮に先立って行わ
れた前処理に対応する逆処理を行う。１７はデータ結合
であり、後処理を終えて回復したデータを結合して元の
データに戻す。１８は元データであり、図１の１に復元
されたデータである。

【００１９】次に、図２におけるデータの流れを図５を
用いて説明する。図５は図２の各処理に対応するデータ
の流れを示したものである。図中、４１は図２の１１の
圧縮データであり、これは図４の３８として得られたデ
ータである。４２は図２の１２のデータ分離によって分
離された圧縮結果１であり、４３は図２の１２によって
分離された圧縮結果２である。この分離に際しては、図
３の２１にあるヘッダからそれぞれ圧縮データの先頭へ
のポインタによって分離する。４４は圧縮結果１を図２
の１３の伸長処理１によって伸長したデータであり、４
５は圧縮結果２を伸長処理２によって伸長したデータで
ある。これらの伸長処理に際しては、それぞれ図３の２
１における圧縮方法の種類に対応する伸長処理を行って
伸長する。４６は４４に図２の１５の後処理１を行って
変換したデータであり、４７は４５に図２の１６の後処
理２を行って変換したデータである。

【００２０】これらの後処理に際しては、それぞれ図２
の２１における前処理に対応する逆処理を後処理として
行う。ここでは、図１の３の前処理１が何もしない事で
あったから、図２の１５の後処理１は何もしない。図１
の４の前処理２が差分を取る事であったから、図２の１
６の後処理２は差分の逆である差分を行う。

【００２１】これを詳しく説明すると、４５の先頭の
「８」はそのまま４７の先頭に「８」として格納され
る。４５の２番目の「１」は４７の先頭の「８」との差
分が取られ、その結果の「７」が４７の２番目のデータ
として格納される。４５の３番目の「２」は４７の２番
目の「７」と差分が取られ、その結果の「５」が４７の
３番目のデータとして格納される。以下同様である。４
８は４６と４７に図２の１７のデータ結合を行って得ら
れた結果である。つまり４６，４７をフィールドとする
データとして図４の３１に完全に復元している。

【００２２】以上はデータが２つのフィールドよりなる
場合の例であるが、フィールドが３つ以上になった場合
も同様であり、また、元のデータがたった１つのフィー
ルドのみであった場合は、図１の２のデータ分離で何も
せず、図１の７のデータ結合ではデータにヘッダを付け
るだけの処理となり、図１の４，５は不要になる。図２
も同様である。

【００２３】図６は前処理と圧縮処理の適切な組み合わ
せを判定する方法を示したブロック図である。図中、５
１は被圧縮データの一部であり、これは図１の２のデー
タ分離を行った後のデータの一部である。通常データの
数が１００個から１０００個ほどもあれば全体の傾向が
つかめる。５２は前処理無しであり、何もしない事であ
る。５３は前処理であり、差分，和分，排他論理和など
の処理が行われる。

【００２４】５４は圧縮法１であり、５５は圧縮法２で
ある。５６は圧縮法１であり、これは５４の圧縮法１と
同一のものである。５７は圧縮法２であり、これは５５
の圧縮法２と同様のものである。５８は圧縮データ長比
較であり、ここで、各圧縮結果のデータ長を比較して最
適な組み合わせを判定する。

【００２５】図６で示した処理を説明する。まず、５１
でサンプルとして被圧縮データの一部を取り出し、これ
に、５２，５３で前処理を行わない場合と、行った場合
のデータを作る。しかる後、５４，５５，５６，５７で
圧縮法１と圧縮法２を前処理を行わないデータと前処理
を行ったデータの各々に対して適用して、その結果、前
処理無し圧縮法１，前処理無し圧縮法２，前処理有り圧
縮法１，前処理有り圧縮法２のデータを得る。これらを
比較処理５８で比較して、どの場合が最もデータ量の削
減効果が高いかを判定する。この結果を用いて図１の前
処理と圧縮法の組み合わせを選定してもよい。もちろ
ん、図６の処理を用いる事無しにユーザーの知識と経験
によって前処理と圧縮法の組み合わせを選定してもよ
い。

【００２６】図７は３つのフィールドより成るデータの
例である。図中、６１は３つのフィールドよりなるデー
タの例であり、ここで用いられる文字は全て８ビットよ
り成るものとする。以下、本発明の一実施例を用いて、
図１０における圧縮結果９１が生成されるまでを説明す
る。

【００２７】図８は図７の６１に対して、フィールド間
の分離、および、前処理を行ったものである。図中、７
１は、図７の６１を３つのフィールドに分離し、更に、
第１フィールドに対して差分をとったものである。７２
は、図７の６１を３つのフィールドに分離し、第２フィ
ールドに対して何もしなかったものである。７３は、図
７の６１を３つのフィールドに分離し、第３フィールド
に対し何もしなかったものである。

【００２８】図９は圧縮法としてハフマン法を用いた場
合のハフマン木の説明図である。図中、８１は図８の７
１に対応するハフマン木であり、８２は図８の７２に対
応するハフマン木であり、８３は７３に対応するハフマ
ン木である。

【００２９】まず、図８の７１において文字の出現頻度
を求めると、１が９回で最多であり、０が５回と続き、
９が１回で最貧である。これからハフマン木を構成す
る。ハフマン木では左に頻度の高い文字を置き右に頻度
の低い文字を置くので、９１に示される様に、１，０，
９の順序に文字が置かれる。次に、これらの文字にコー
ドを割り振るのであるが、出現頻度の多いものに短いコ
ード、出現頻度の少ないものに長いコードを割り振る。
このコードの割り振りに対して、ハフマン木を左に進む
とビットの０を割り当て、ハフマン木を右に進むとビッ
トの１を割り当てる。従って、結果として、文字である
８ビットの１に対しては、１ビットの０を割り振り、文
字である８ビットの０には２ビットの１０を割り振り、
文字である８ビットの９には２ビットの１１を割り振
る。

【００３０】８２では、７２でＣが最多の７回、Ａが６
回と続きＢが３回と最貧である事から、８１と同様にし
てハフマン木が生成される。

【００３１】８３では、７３でＸが最多で８回、Ｚが５
回と続き、Ｙが３回で最貧である事から、８１と同様に
してハフマン木が生成される。

【００３２】図１０は、図７の６１に対する本発明の一
実施例による圧縮結果である。図中、９１は図７の６１
に対して第１フィールドのみ差分を取って各フィールド
をハフマン法で圧縮し、それにヘッダを付けて結合した
結果である。

【００３３】９１ではヘッダ長は８ビットであり、圧縮
方法は１ビットの０か１で表わす事にして、０ならば無
圧縮、１ならばハフマン法とする。前処理は１ビットの
０か１で表わす事にして、０ならば無処理、１ならば差
分であるとする。圧縮データの先頭アドレスは８ビット
で表わす事にする。従って、ヘッダは８＋１＋１＋８＋
１＋１＋８＋１＋１＋８＝３８ビットである。これによ
り、ヘッダ長には３８が入る。

【００３４】次に第１フィールドはハフマン法を用い、
前処理として差分を行っているから、圧縮法の部分に１
前処理の部分に１が入る。また、第１フィールドは先頭
に置かれているので、圧縮データへの先頭アドレスに０
が入る。第２フィールドではハフマン法を用い、前処理
が無処理であるため、圧縮法は１で前処理は０である。
圧縮データへの先頭は、第１フィールドの圧縮結果であ
るハフマン木２４ビット＋コード２３ビット＝４７が入
る。ハフマン木とデータの説明は後で行う。第３フィー
ルドではハフマン法を用い、前処理が無処理であるた
め、圧縮法は１で前処理は０である。圧縮データへの先
頭は、第１フィールドの圧縮結果である４７＋第２フィ
ールドのハフマン木２４ビット＋コード２５ビット＝９
６が入る。以上が９１のヘッダである１行目の内容であ
る。

【００３５】９１の第２行，第３行，第４行はそれぞ
れ、図８の７１，７２，７３のハフマン法による圧縮結
果である。第２行について説明する。これはハフマン木
とコードよりなり、図９の８１のハフマン木にある文字
の１，０，９がこの順序に格納される。つまり、出現頻
度の高い順であり、ハフマン木でみると左から順に格納
される。なお、各文字は８ビットであるため、１，０，
９が格納された１０９と言う文字は２４ビットである。
次に、コード部分であるが、これは、図９の８１に従っ
て、図８の７１を文字の１はビットの０、文字の０はビ
ット１０文字の９はビットの１１に置き換えたものであ
る。

【００３６】第３行目，第４行目についても同様であ
る。なお、伸長に際しては、ハフマン木の作り方に従っ
て、まず、１０９より文字１に対しては０、文字０に対
しては１０、文字９に対しては１１とコード割り当てが
一意に決まる。これにより、第２行目の最初の１１は９
とデコードされ、次の１０は０、次の１０は０、次の０
は１、次の１０は０、次の０は１、次の０は１、次の１
０は０、次の１０は０、次の０は１、次の１０は０、次
の０は１、次の０は１、次の０は１、次の０は１、次の
０は１と、それぞれデコードされる。これにより、９，
０，０，１，０，１，１，０，０，１，０，１，１，
１，１，１と伸長され、確かに図８の７１に復元されて
いる。

【００３７】

【発明の効果】本発明によれば、データをフィールド毎
に区切り、データの特徴を基に適切に選定された前処理
を行う事によって、圧縮によるデータの削減効果を増大
させる事が出来る。これにより、データの通信コストや
格納コストが削減され、計算機システム全体としての処
理効率の向上につながる。

【図面の簡単な説明】

【図１】本発明の一実施例による圧縮方法の処理手順の
ブロック図。

【図２】本発明の一実施例による伸長方法の処理手順の
ブロック図。

【図３】本発明の一実施例におけるヘッダフォーマット
の説明図。

【図４】図１の各処理に対応したデータの流れを示す説
明図。

【図５】図２の各処理に対応したデータの流れを示す説
明図。

【図６】本発明の一実施例での前処理と圧縮法の組み合
わせの判定処理の説明図。

【図７】本発明の一実施例により処理されるデータの説
明図。

【図８】本発明の一実施例の処理により分離されたデー
タの説明図。

【図９】本発明の一実施例によるハフマン木の説明図。

【図１０】本発明の一実施例による圧縮結果を示す説明
図。

【符号の説明】

１…被圧縮データ、２…被圧縮データのデータ分離処
理、３…前処理、４…前処理、５…圧縮処理、６…圧縮
処理、７…分離して圧縮したデータの結合処理、８…圧
縮結果、１１…圧縮データ、１２…圧縮データの分離、
１３…伸長処理、１４…伸長処理、１５…後処理、１６
…後処理、１７…分離して伸長したデータの結合処理、
１８…復元されたデータ、２１…ヘッダ。

Claims (6)

【特許請求の範囲】
1. 【請求項１】１個または複数のフィールドよりなるデー
   タが多数集まって構成されているデータ群に対して、前
   記データ群を各フィールド毎のデータ群に分離する手段
   と、前記分離されたデータ群に対する圧縮手段と、前記
   分離されたデータ群に対して前処理を行う手段と、前記
   分離されたデータ群に対して前処理を行った結果に対し
   て圧縮処理を行う手段と、前記分離されたデータ群に対
   して、圧縮処理を行った結果および前処理を行った後に
   圧縮した結果を結合する手段とを有する事を特徴とする
   前処理付きデータ圧縮方法。
2. 【請求項２】請求項１において生成された結果に対し
   て、前記結果を１個または複数のデータ群に分離する手
   段と、前記分離された結果を伸長する手段と、伸長した
   結果に、請求項１において行われた前処理が実施された
   場合に前処理の逆処理としての後処理を行う手段と、前
   記伸長処理のみの結果および伸長処理後に後処理を実施
   した結果を結合する手段とを有し、データの復元を行う
   事を特徴とする圧縮データの伸長方法。
3. 【請求項３】請求項１において、フィールドの内のデー
   タ群の１つが値の大きい順にソートされている時に、前
   処理として差分を用い、圧縮手段としてハフマン法を用
   いる事を特徴とする前処理付きデータ圧縮方法。
4. 【請求項４】請求項１において、前処理および圧縮手段
   が複数用意され、データの特性に合わせてフィールド毎
   に前処理手段と圧縮手段を組み合わせて用いる事を特徴
   とする前処理付きデータ圧縮方法。
5. 【請求項５】請求項４において、前処理手段として、差
   分，和分，排他論理和を用いる事を特徴とする前処理付
   きデータ圧縮方法。
6. 【請求項６】請求項４において、データ群の内、所定個
   数のデータを抽出する手段を有し、前記抽出したデータ
   群をフィールド毎に分離し、前記分離結果に対して前処
   理と圧縮処理の組み合わせによる処理を実施し、その結
   果のデータ量を比較する手段を有し、前記比較結果に基
   づいて各々のフィールドに対し最も効率のよい前処理と
   圧縮手段を適用する事を特徴とする前処理付きデータ圧
   縮方法。