JPH08167852A

JPH08167852A - データ圧縮方法及び装置

Info

Publication number: JPH08167852A
Application number: JP30866294A
Authority: JP
Inventors: Nobuko Sato; 宣子佐藤; Yoshiyuki Okada; 佳之岡田; Shigeru Yoshida; 茂吉田
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1994-12-13
Filing date: 1994-12-13
Publication date: 1996-06-25

Abstract

(57)【要約】【目的】圧縮対象ファイルサイズが確率モデル構築に
十分な大きさでない場合に、予め個々の文字出現頻度を
保持せずに、良い圧縮率を得ることができるデータ圧縮
方法及び装置を提供することを目的とする。【構成】入力される可能性がある文字を、互いに同じ
統計的性質を有する文字毎に階層的な複数の群にそれぞ
れ分類する群構成ステップと、それぞれの群の出現確率
を計算する群出現確率計算ステップと、複数の群中にお
ける入力文字の出現確率を計算する群中文字出現確率計
算ステップと、群中文字出現確率計算ステップで計算さ
れた出現確率に基づいて入力文字を符号化する入力文字
符号化ステップとを備えて構成した。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】近年、文字コード、画像データ等
の様々なデータがコンピュータで扱われるようになるの
に伴い、取り扱われるデータ量も増大している。そのよ
うな大量のデータは、データ中の冗長な部分を省いて圧
縮することにより、記憶容量を減らしたり、早く伝送し
たりできるようになる。

【０００２】一方、圧縮を行ったデータは、参照・利用
する際に復元する必要があるため、圧縮する前のデータ
に比べアクセス速度が低下する。そこで、これまでのデ
ータ圧縮は、主に、一部参照を行うことが希な、データ
のバックアップや通信のときにのみ利用されている。

【０００３】しかし、近年では、圧縮専用ＬＳＩが利用
されるようになったため、圧縮データの復元速度は短く
なり、通常のデータと同様にアクセスを行うデータに対
しても、圧縮・復元を行うことが考えられてきている。

【０００４】そこで、圧縮を行った場合、圧縮データ単
位毎に復元を行うため、アクセスするデータサイズ単位
と、圧縮するデータサイズは同程度（５Ｋｂｙｔｅ以
下、１〜２Ｋｂｙｔｅ程度）で行うことが望まれてい
る。

【０００５】

【従来の技術】様々な種類のデータ（文字コード、画像
データ等）に適用できるデータ圧縮方式として、ユニバ
ーサル符号化方式が提案されている。ここで、本発明
は、文字コードの圧縮に限定されず、様々なデータに適
用できるが、以下では、情報理論に基づき、データの１
ワード単位を文字（アルファベット）と呼び、データが
任意ワードつながったものを文字列と呼ぶことにする。

【０００６】ユニバーサル符号化方式の中で代表的な方
式として、算術符号化方式がある。この方式は、従来よ
く使われているハフマン符号のように、１文字づつばら
ばらに符号化の１点に対応付け、２進数の小数点以下を
符号として出力するものである。

【０００７】ここで、多値算術符号化の原理を、図２を
参照して説明する。まず、算術符号では、文字列を実数
０と１の間（［０，１））のある実数の区間を用いて表
すということが基本アイデアになっている。

【０００８】ここで、区間［０，１）を採用するのは、
２進数の小数点以下を符号として出力するためである。
また、以上“［”と未満“）”となっている理由は、
［０，１］では、０と１の小数点以下が同じになって０
と１を区別できなくなるためであり、（０、１）では、
値としての０が使用できなくなるためである。

【０００９】図２（Ａ）は、ａ，ｂ，ｃ，ｄの４文字が
出現すると仮定した場合に、各々の文字の出現頻度を示
している。図２（Ａ）中、横軸の文字ａ，ｂ，ｃ，ｄの
下側に記された（４）、（２）、（１）、（３）は、そ
れぞれの文字の出現頻度順位を示している。

【００１０】図２（Ａ）に示された各文字の出現頻度に
基づいて、文字毎の累積出現頻度確率を出現頻度順に示
したのが図２（Ｂ）である。即ち、図２（Ｂ）中、横軸
にｃｆ０と記された列は、ｃ，ｂ，ｄ，ａの４文字中の
文字ｃの累積出現頻度確率を示している。同様に、横軸
にｃｆ１と記された列は、ｂ，ｄ，ａの３文字中の文字
ｂの累積出現頻度確率を示している。同様に、横軸にｃ
ｆ２と記された欄は、ｄ，ａの２文字中の文字ｄの累積
出現頻度確率を示している。同様に、横軸にｃｆ３と記
された欄は、文字ａの累積出現頻度確率を示している。

【００１１】そして、図２（Ｂ）に示された累積出現頻
度確率から算術符号化を行う方法を示したのが図２
（Ｃ）である。即ち、文字ｃを入力した段階で、対応す
る区間１０として、文字ｃの累積出現頻度確率（図２
（Ｂ）においてｃｆ０と記された列で斜線が付された箇
所）と同等の区間幅を採用する。

【００１２】次に、２番目の文字ａが入力された段階
で、対応する区間１１として、１文字目に対応する区間
１０を各文字の累積出現頻度確率で再分割して得られる
区間１１を採用する。

【００１３】そして、３番目の文字ｄが入力された段階
で、対応する区間１２として、２文字目に対応する区間
１１を各文字の累積出現頻度確率で再分割して得られる
区間１２を採用する。

【００１４】このようにして、文字列ａｃｄは区間１２
の任意値（区間１２の上端と下端の間の任意の値）とし
て符号化される。ここで、各区間の下端は、式（１−
１）〜（１−２）により求められる。新たな部分区間の下端＝現部分区間の下端＋現部分区間幅×注目文字の累積確率・・・（１−１）新たな部分区間幅＝現部分区間幅×注目文字の確率・・・（１−２）なお、符号語を復元するには、符号語が各文字の確率に
分けたどの区間に含まれるか、逐次再分割しながら調べ
ればよい。

【００１５】このように、算術符号化では、区間で符号
化するが、復号する過程では実際に区間が与えられる必
要は無く、区間の中のある一つの数が指定されればよ
い。具体的な符号語としては、区間内の数の中でできる
だけ短いビット数で表せるものを選べばよい。

【００１６】即ち、出現頻度が高いほど区間幅が大きく
なるということから、区間幅が大きいほど小数点以下の
数が少なくなり、短いビット数で表せるようになる。以
上は、各シンボル出現頻度を固定した例の説明である
が、以下に示すように、出現頻度（確率モデル）を逐次
変更して、動的に行うこともできる。注目文字の累積確率＝注目文字より出現頻度の低い文字の出現回数の累積／入力文字列長・・・（２−１）注目文字の確率＝注目文字の出現回数／入力文字列長・・・（２−２）ここで、出現頻度を文字入力の度に再計算する動的な算
術符号化を行う装置の構成を図３に示す。この装置は、
図２（Ａ）のような入力された文字の出現頻度を作成す
ると共に、図２（Ｂ）のような文字ごとの出現頻度順の
累積出現頻度を作成する確率確率モデル（シンボル出現
頻度）作成部２０と、図２（Ｃ）のような累積出現頻度
確率から算術符号化を行う算術符号部４０とから構成さ
れている。そして、確率モデル作成部２０は、図示して
いない辞書とカウンタとを有している。

【００１７】次に、図４のフローにより、図３の算術符
号化装置の動作を説明する。まず、ステップ４０１で
は、上端＝１、下端＝０、区間幅＝１．０を算術符号化
の初期値とする。このとき、確率モデル作成部２０の辞
書は、シンボルと出現頻度順位を保持し、カウンタは各
シンボル出現頻度を保持する。また、初期化として、シ
ンボル数（出現が考えられる文字数：１ｂｙｔｅの時２
５６）の辞書を準備し、各文字ごとに出現頻度をカウン
トするカウンタを準備し“１”に初期化する。そして、
算術符号部４０は、各シンボルの順位、また、累積出現
頻度を保持する。

【００１８】入力文字列より一文字（ｋとする）入力す
る（ステップ４０２）毎に、辞書より出現頻度順位を選
択し、この番号及び累積出現頻度を用いて算術符号部４
０にて区間を計算し、算術符号化する（ステップ４０
３）。つまり、入力文字の区間の上端と下端を式（１−
１）〜（１−２）及び式（２−１）〜（２−２）に基づ
いて求め、区間の任意の値を符号として出力する。

【００１９】その後、カウンタにて入力文字の出現頻度
を“１”増やす（ステップ４０４）。“１”増加した文
字に伴い、頻度順に辞書を並び替える（ステップ４０
５）と共に、累積出現頻度を更新する（ステップ４０
６）。なお、ステップ４０５とステップ４０６は、逆に
処理してもよい。

【００２０】以上のステップ４０２からステップ４０６
までの操作は、繰り返し実行される。これまでの説明
は、一文字毎の出現確率に基づいて算術符号化する場合
の例である。更に圧縮率を高めるには、入力文字と直前
の文字との依存関係（以下、「文脈」とする）を取り入
れた、条件付出現確率を用いて算術符号化する。

【００２１】文脈は、図５に示すように、木構造で表さ
れる。各ノードの文字を通る文字列が出る毎に出現回数
を各ノードにて計数しておいて条件付き確率を求める。
図５において、各文字の右隣に記された数字が出現回数
を示している。例えば、rootの直ぐ下にある（枝の長さ
が１）文字ａの右隣に５と記されているのは、文字ａの
出現回数が５であることを意味し、rootから２段下にあ
る（枝の長さが２）文字ａの右隣に２と記されているの
は、文字ａａの出現回数が２であることを意味し、root
から３段下にある（枝の長さが３）文字ａの右隣に１と
記されているのは、文字ａａａの出現回数が１であるこ
とを意味している。

【００２２】ここで、全ての記号の生起確率は、その記
号の直前に出現した記号列である「文脈」に従って定め
られるが、この文脈の形成に利用される記号列の長さは
「次数」と呼ばれる。次数の設定の仕方である文脈収集
方法には、下記の（１）及び（２）がある。（１）固定次数の文脈条件付確率の条件を固定の次数にする方法。例えば、２
次の文脈では直前２文字につながる文字の文脈を収集
（図５では、rootからの枝の長さ３）し、条件付き確率
p(y|x1,x2)を得る。

【００２３】ただし、yは注目符号化文字、x1、x2はそ
れぞれ直前の第１文字、第２文字を意味し、p(y|x1,x2)
は、x1、x2が続いて出現した後に、yが出現する確率を
意味している。（２）Blending文脈 Blending（次数の混合）は、条件文字列の長さを固定せ
ずに、入力データに応じて次数を伸ばす。

【００２４】多値算術符号化において出現可能な文字数
が多い場合（例えば、１文字が１６bitで表現され、出
現可能な文字が６４Ｋ個の場合）には、該当する圧縮フ
ァイルに全く出現しない文字が多数存在する。この場
合、出現頻度を文字入力の度に再計算して動的に算術符
号化を行うときに、全各文字の出現可能性を考えて各出
現頻度の初期値に“１”を与えると、無駄な区間を多く
とり、圧縮率が低下することになる。この無駄をなくす
方法として、−１次と０次のBlending方法がある。−１
次は、未出現文字を等確率にしたものをあらわし、０次
は、文脈無しの文字出現頻度を表す。

【００２５】−１次、０次のBlending方法を用いた算術
符号化方式のフローを、図６を参照して説明する。な
お、このフローは、例えば図３に示す装置で処理され
る。まず、ステップ６０１では、算術符号化にあたっ
て、上端＝１、下端＝０、区間幅＝１．０を初期値とす
る。また、全出現可能な文字（情報源）を未出現文字と
して辞書に登録する。

【００２６】そして、入力文字列より一文字（ｋとす
る）入力する（ステップ６０２）毎に、それがフロー中
に出現したかどうかを辞書により判別する（ステップ６
０３）。

【００２７】ステップ６０３で、出現していないと判別
された場合は、未出現文字用区間を算術符号化し（ステ
ップ６０７）、全未出現文字を等確率として文字ｋを算
術符号化する（ステップ６０８）。その後、カウンタに
て入力文字ｋの出現頻度を“１”とし、文字ｋを未出現
文字より除く（ステップ６０９）。

【００２８】一方、ステップ６０３で、出現していたと
判別された場合は、文字ｋを算術符号化する（ステップ
６０４）。その後、カウンタにて入力文字の出現頻度を
“１”増やす（ステップ６０５）。そして、出現頻度順
に辞書を並び替える（ステップ６０６）。

【００２９】ステップ６０６とステップ６０９の実行後
に、累積出現頻度を更新する（ステップ６１０）。その
後、ステップ６０２から実行を繰り返す。

【００３０】

【発明が解決しようとする課題】統計的な各文字出現頻
度に従い、出現確率の高い文字に対して短い符号長を割
り振る圧縮方式（確率統計型圧縮方式）において、前述
したように、各シンボル出現頻度（確率モデル）を固定
的にするものと、動的に変更するものとがある。

【００３１】前者は、復元する際に予め設定した確率モ
デルまたは全文字列を操作して得た確率モデルを必要と
し、圧縮したデータとともに、先の出現頻度を保持する
必要がある。

【００３２】一方、後者は、文字列を入力するに従っ
て、確率モデルを再計算して使う適応型符号化方式であ
り、予め確率モデルを保持しなくてよく、また、各圧縮
対象データに即した確率モデルを構築することができ
る。しかし、圧縮を行う文字列が短い場合には、十分な
辞書を構築することができず、良い圧縮率が得られな
い。

【００３３】本発明は、このような事情に鑑みてなされ
たもので、圧縮対象ファイルサイズが確率モデル構築に
十分な大きさでない場合に、予め個々の文字出現頻度を
保持せずに、良い圧縮率を得ることができるデータ圧縮
方法及び装置を提供することを課題とする。

【００３４】

【課題を解決するための手段】

＜本発明の第１のデータ圧縮方法＞本発明の第１のデー
タ圧縮方法は、前述した課題を解決するため、下記の如
く構成されている（請求項１に対応）。

【００３５】即ち、出現確率に応じた符号長を出力する
可変長符号化を行うデータ圧縮方法において、群構成ス
テップと、群出現確率計算ステップと、群中文字出現確
率計算ステップと、入力文字符号化ステップとを備えて
いる。

【００３６】群構成ステップは、入力される可能性があ
る文字を、互いに同じ統計的性質を有する文字毎に階層
的な複数の群にそれぞれ分類する。群出現確率計算ステ
ップは、前記それぞれの群の出現確率を計算する。

【００３７】群中文字出現確率計算ステップは、前記複
数の群中における入力文字の出現確率を計算する。入力
文字符号化ステップは、前記群中文字出現確率計算ステ
ップで計算された出現確率に基づいて入力文字を符号化
する。

【００３８】＜本発明の第２のデータ圧縮方法＞本発明
の第２のデータ圧縮方法は、前述した課題を解決するた
め、下記の如く構成されている（請求項２に対応）。

【００３９】即ち、第１のデータ圧縮方法において、前
記群構成ステップ（Ｓ１）では、前記群の構成要素の分
類を予め固定して与える。＜本発明の第３のデータ圧縮方法＞本発明の第３のデー
タ圧縮方法は、前述した課題を解決するため、下記の如
く構成されている（請求項３に対応）。

【００４０】即ち、第１のデータ圧縮方法において、前
記群出現確率計算ステップ（Ｓ２）では、前記群の出現
確率を予め固定して与える。＜本発明の第４のデータ圧縮方法＞本発明の第４のデー
タ圧縮方法は、前述した課題を解決するため、下記の如
く構成されている（請求項４に対応）。

【００４１】即ち、第１のデータ圧縮方法において、前
記群出現確率計算ステップ（Ｓ２）では、前記群の出現
確率に予め初期値を設定するとともに、この群の出現確
率を前記文字の入力に応じて動的に再計算する。

【００４２】＜本発明の第５のデータ圧縮方法＞本発明
の第５のデータ圧縮方法は、前述した課題を解決するた
め、下記の如く構成されている（請求項５に対応）。

【００４３】即ち、第１のデータ圧縮方法において、前
記群出現確率計算ステップ（Ｓ２）では、前記群の出現
確率を、直前の複数文字が属する各々の群が出現するこ
とを条件とする条件付群出現確率で計算する。

【００４４】＜本発明の第６のデータ圧縮方法＞本発明
の第６のデータ圧縮方法は、前述した課題を解決するた
め、下記の如く構成されている（請求項６に対応）。

【００４５】即ち、第１のデータ圧縮方法において、前
記群構成ステップ（Ｓ１）では、前記階層的な複数の群
を、高出現確率文字で構成される第１の群と、低出現確
率文字で構成される第２の群とで構成する。

【００４６】＜本発明のデータ圧縮装置＞本発明のデー
タ圧縮装置は、前述した課題を解決するため、下記の如
く構成されている（請求項９に対応）。。

【００４７】即ち、出現確率に応じた符号長を出力する
可変長符号化を行うデータ圧縮装置において、群構成部
と、群出現確率計算部と、群中文字出現確率計算部と、
入力文字符号化部とを備えている。

【００４８】群構成部は、入力される可能性がある文字
を、互いに同じ統計的性質を有する文字毎に階層的な複
数の群にそれぞれ分類する。群出現確率計算部は、前記
それぞれの群の出現確率を計算する。

【００４９】群中文字出現確率計算部は、前記複数の群
中における入力文字の出現確率を計算する。入力文字符
号化部は、前記群中文字出現確率計算部で計算された出
現確率に基づいて入力文字を符号化する。

【００５０】

【作用】

＜本発明の第１のデータ圧縮方法の作用＞まず、群構成
ステップでは、入力される可能性がある文字が、互いに
同じ統計的性質を有する文字毎に階層的な複数の群に分
類される。そして、群出現確率計算ステップでは、それ
ぞれの群の出現確率が計算される。そして、群中文字出
現確率計算ステップでは、複数の群中における入力文字
の出現確率が計算される。そして、入力文字符号化ステ
ップでは、群中文字出現確率計算ステップで計算された
出現確率に基づいて入力文字が符号化される。

【００５１】＜本発明の第２のデータ圧縮方法の作用＞
第１のデータ圧縮方法の作用において、群構成ステップ
では、群の構成要素の分類が予め固定して与えられる。

【００５２】＜本発明の第３のデータ圧縮方法の作用＞
第１のデータ圧縮方法の作用において、群出現確率計算
ステップでは、群の出現確率が予め固定して与えられ
る。

【００５３】＜本発明の第４のデータ圧縮方法の作用＞
第１のデータ圧縮方法の作用において、群出現確率計算
ステップでは、群の出現確率に予め初期値が設定される
とともに、この群の出現確率が文字の入力に応じて動的
に再計算される。

【００５４】＜本発明の第５のデータ圧縮方法の作用＞
第１のデータ圧縮方法の作用において、群出現確率計算
ステップでは、群の出現確率が、直前の複数文字が属す
る各々の群が出現することを条件とする条件付群出現確
率で計算される。

【００５５】＜本発明の第６のデータ圧縮方法の作用＞
第１のデータ圧縮方法の作用において、群構成ステップ
では、階層的な複数の群が、高出現確率文字で構成され
る第１の群と、低出現確率文字で構成される第２の群と
で構成される。

【００５６】＜本発明のデータ圧縮装置の作用＞まず、
群構成部では、入力される可能性がある文字が、互いに
同じ統計的性質を有する文字毎に階層的な複数の群に分
類される。そして、群出現確率計算部では、それぞれの
群の出現確率が計算される。そして、群中文字出現確率
計算部では、複数の群中における入力文字の出現確率が
計算される。そして、入力文字符号化部で、群中文字出
現確率計算部で計算された出現確率に基づいて入力文字
が符号化される。

【００５７】

【実施例】以下、本発明の実施例を図面を参照して説明
する。＜実施例の構成＞図７は、本実施例の算術符号装置の構
成を示す。算術符号装置は、同図に示されるように、以
下の（イ）〜（ロ）の要素を備えて構成される。（イ）文字列を入力し、該文字列に含まれる文字を、文
字群１、文字群２及び文字群３のいずれかに分類する文
字群分類部１０。ここで、文字群１は、ひらがなを構成
要素とし、文字群２は、スペース、句読点及び改行マー
クを構成要素とし、文字群３は、その他の文字、例えば
漢字を構成要素とする。（ロ）文字群分類部１０が出力する文字群の群番号
（１、２、３のいずれか）を入力すると共に文字列を入
力し、文字出現頻度と各群における入力文字の順位を出
力する確率モデル作成部２０。（ハ）符号化文字の群番号からその群の累積出現頻度を
求め、その区間を符号化すると共に、続いて符号化文字
のその群における符号化文字の累積出現頻度を求め、そ
の区間を符号化する符号部３０。この符号部３０は、文
字群分類部１０から「群番号及び群出現頻度」を入力す
ると共に、確率モデル作成部２０から「文字出現頻度及
び各群における入力文字の順位」を入力し、算術符号を
出力する。

【００５８】以下、前記（イ）〜（ハ）の要素を詳細に
説明する。〔文字群分類部１０〕文字群分類部１０は、図８に示す
ように、群分類部１１と群確率保持部１２とからなる。

【００５９】群分類部１１は、文字列を入力し、該文字
列に含まれる文字（シンボルともいう）を、文字群１、
文字群２及び文字群３のいずれかに分類して、分類した
文字群の群番号を出力する。群分類部１１は、シンボル
と群番号とを対応させて格納する対応表１１ａを有して
いる。この対応表１１ａに格納された群番号は、確率モ
デル作成部２０及び符号部３０に出力される。

【００６０】群確率保持部１２は、群分類部１１から群
番号を入力し、各文字群ごとの出現頻度を出力する。群
確率保持部１２は、群番号と群毎の確率とを対応させて
格納する対応表１２ａを有している。この対応表１２ａ
に格納された群出現確率は、符号部３０に出力される。

【００６１】〔確率モデル作成部２０〕確率モデル作成
部２０は、辞書２１と、カウンタ２２とからなる。辞書
２１は、文字列を入力すると共に、文字群分類部１０よ
り入力された文字が属する群番号を入力して、群番号順
位（群中の出現頻度順位）を出力する。そして、辞書２
１は、文字群毎に、シンボルと群番号順位とを対応させ
て格納する対応表２１ａを有している。この対応表２１
ａに格納された群番号順位は、符号部３０に出力され
る。

【００６２】カウンタ２２は、辞書２１から群番号順位
を入力し、文字出現確率を出力する。そして、カウンタ
２２は、文字群毎に、群中の出現頻度順位と文字出現頻
度とを対応させて格納する対応表２２ａを有している。

【００６３】〔符号部３０〕符号部３０は、テーブル３
１と、算術符号化部３２とからなる。テーブル３１は、
文字群分類部１０から「群番号及び群出現確率」を入力
すると共に、確率モデル作成部２０から「群内文字順位
及び群内文字出現確率」を入力する。そして、テーブル
３１は、群番号と累積出現頻度とを対応させて格納する
テーブル３１ａと、文字群毎に、郡内文字順位と累積出
現頻度とを対応させて格納する複数のテーブル３１ｂを
有している。

【００６４】算術符号化部３２は、テーブル３１が保持
する累積出現頻度を入力して、算術符号を出力する。こ
こで、どの文字がどの群に属するかという情報と文字群
の出現頻度に関する情報は、予め予想される出現頻度に
従って初期的に与えられる。例えば、図９に示すよう
に、スペース（空白）、Ｅ、Ｔ等の文字は、高出現文字
群に分類され、Ｈ、Ｄ、Ｌ等の文字は、低出現文字群に
分類される。そして、各々の群出現確率は、それぞれの
群に属する文字の個々の出現確率の総和をとったものと
する。

【００６５】＜実施例の動作＞次に、図１０を参照し
て、実施例の動作を説明する。まず、ステップ１００１
では、算術符号化する符号語の初期設定として、上端＝
１、下端＝０、区間幅＝１.０とする。

【００６６】ここで、文字群分類部１０は、予め予想さ
れる出現頻度に基づいて、群分類部１１の群分類と群確
率保持部１２の群確率とを初期化する。なお、群分類の
初期化とは、各群の構成要素とどの文字がどの群に属す
るのかという情報を与えることであり、群確率の初期化
とは、例えば、群１：群２：群３＝３：５：１と群の出
現確率を初期値に従って与えることである。

【００６７】そして、確率モデル作成部２０は、各シン
ボル群に分類し、各シンボルごとのカウンタ２２を準備
し１に初期化する。また、確率モデル作成部２０は、群
累積出現頻度を累積して計算すると共に、各文字群毎に
別々の各シンボルの順位、累積出現頻度を計算する。な
お、群累積出現頻度を累積して計算するとは、例えば、
群３〜群Ｍの出現頻度を足し合わせて群２の累積出現頻
度とすることをいう。

【００６８】次に、入力文字列より一文字（“ｋ”とす
る）入力する（ステップ１００２）毎に、文字群分類部
１０は、群分類部１１の辞書を検索して入力文字が属す
る群（“Ｋ”とする）を判別する（ステップ１００
３）。

【００６９】ここで、確率モデル作成部２０は、ステッ
プ１００３で判別された群と入力文字に基づいて辞書２
１を検索し、出現頻度順位と、群の各文字出現頻度を出
力する。

【００７０】そして、算術符号部３０は、文字群累積出
現頻度を使用して文字群Ｋを算術符号化する（ステップ
１００４）と共に、入力文字ｋを算術符号化する（ステ
ップ１００５）。なお、ステップ１００４の算術符号化
は、（イ）群番号及び群累積出現頻度を用いて入力文字
群の区間の上端と下端を求めること、（ロ）入力文字の
群内出現頻度順位及び当群の累積出現頻度を用いて入力
文字の区間の上端と下端を求めること、（ハ）区間の任
意の値を符号として出力すること、により行われる。

【００７１】そして、カウンタ２２にて入力文字ｋの出
現頻度を“１”増やし（ステップ１００６）、頻度順に
文字群Ｋの辞書を並び替える（ステップ１００７）。次
に、“１”増加した文字に伴い、出現頻度順位及び累積
出現頻度を更新する（ステップ１００８）。その後、ス
テップ１００２から実行を繰り返す。

【００７２】〔−１次、０次のBlending方法を用いた算
術符号化の動作〕次に、−１次、０次のBlending方法を
用いた算術符号化の動作を、図１１を参照して説明す
る。

【００７３】まず、ステップ１１０１では、算術符号化
の初期設定として、（イ）文字群累積出現頻度を準備す
ること、（ロ）各文字出現頻度を０とすること、（ハ）
未出現文字として各文字群毎に全文字を登録すること、
（ニ）各文字群毎に準備した未出現文字確率を１に設定
すること、を行う。

【００７４】次に、入力文字列より一文字（“ｋ”とす
る）入力する（ステップ１１０２）毎に、文字群分類部
１０は、群分類部１１の辞書を検索して入力文字が属す
る群（“Ｋ”とする）を判別する（ステップ１１０
３）。

【００７５】そして、算術符号化部３０は、文字群累積
出現頻度を使用して、文字群Ｋを算術符号化する（ステ
ップ１１０４）。ここで、文字群Ｋが先に出現していた
か否かが判断される（ステップ１１０５）。ステップ
１１０５で、先に出現していたと判断された場合、文字
群Ｋの累積出現頻度を使用して、文字ｋを算術符号化し
（ステップ１１０６）、文字ｋをカウントする（ステッ
プ１１０７）とともに、頻度順に辞書を並び替える（ス
テップ１１０８）。

【００７６】一方、ステップ１１０５で、先に出現して
いないと判断された場合、文字群Ｋの未出現文字区間を
算術符号化し（ステップ１１０９）、文字ｋを算術符号
化する（ステップ１１１０）とともに、文字ｋを文字群
Ｋの辞書に挿入し、文字ｋを文字群Ｋの未出現文字より
除く（ステップ１１１１）。なお、ステップ１１１０で
は、文字群Ｋの全未出現文字は、等確率にされる。

【００７７】ステップ１１０８とステップ１１１１の後
に、文字群Ｋの累積出現頻度が更新される。〔符号部３０の算術符号化の具体例〕図１２は、符号部
３０の算術符号化の具体例を示す図である。図１２で
は、「ひらがな」を文字群１、「スペース、句読点、改
行マーク」を文字群２、その他の「数字」等を文字群３
としている。一文字群としている。「ひらがな」の出現
確率は０．５２で、「スペース、句読点、改行マーク」
の出現確率は０．１３である。圧縮の初期では、どの文
字も出現したことがなく、各文字の出現頻度は０であ
る。

【００７８】この場合、従来の方式では、どの文字も等
確率で出現可能と考えて、等幅の符号区間を設定する
が、本実施例では、図１２（Ｂ）に示すように各群の出
現確率に応じて定め、文字群区間の中でその文字群に属
する各文字を等幅とする。各文字群区間は、前述した各
群出現確率（図１２（Ａ）参照）に従って分ける。

【００７９】本発明の文字群区間を定めた上で各文字区
間を定める方式によると、図１２（Ｂ）に示すように、
圧縮初期の段階から出現確率の高い文字に対して広い符
号区間を与えることができる。

【００８０】＜本実施例の変形例＞前記実施例では、文
字群出現確率を固定的なものとしてきたが、文字群出現
確率を動的に変える変形例を述べる。

【００８１】（１）文字群出現確率を個々の群の出現確
率を動的に変えるもの（２）群の文脈を取り入れた、条件付出現確率を動的に
変えるものまず、文字群出現確率を、個々の群の出現確率を動的に
変えるものを図１３に示す。これは、図７における文字
群分類部１０に相当する。文字群分類部１０は、どの文
字がどの群に属するかを示す群分類部１１と、各文字群
に初期値を与え、文字を入力するごとに、その文字の属
する群の出現頻度を“１”増やし、群累積出現頻度を更
新する群カウンタ１３とから構成されている。

【００８２】その動作は、図１４を参照して説明する。
まず、ステップ１４０１では、初期設定として、文字群
累積出現頻度をとって、各文字出現頻度を１とし、各文
字群毎に累積出現頻度をとる。

【００８３】次に、入力文字列より一文字（“ｋ”）入
力する（ステップ１４０２）毎に、文字群分類部１０
は、群分類部１１の辞書を検索して入力文字が属する群
（“Ｋ”とする）を判別する（ステップ１４０３）。

【００８４】そして、算術符号部３０は、文字群累積出
現頻度を使用して文字群Ｋを算術符号化する（ステップ
１４０４）と共に、入力文字ｋを算術符号化する（ステ
ップ１４０５）。

【００８５】そして、文字ｋの出現頻度と文字群Ｋの出
現頻度を、それぞれ１ずつ増加させ（ステップ１４０
６）、頻度順に文字群Ｋの辞書を並び替える（ステップ
１４０７）。

【００８６】次に、ステップ１４０６の増加に伴い、文
字群Ｋの累積出現頻度を更新する（ステップ１４０
８）。同様に、群の文脈を取り入れ、条件付出現確率を
動的に得ることもできる。０次の値は初期値を与え、１
次以上の条件付確率は、図５に示すように、各ノード群
を通る文字群が出る毎に、出現回数を各ノードにて計数
しておくことによって条件付確率が求められる。ここで
従来は、シンボルが木の各節点になっていたのに対し、
本実施例では、群が木の各節点になっている。

【００８７】群出現頻度に１次の条件付出現確率をとる
場合のフローを図１５に示す。まず、初期化として以下
の（イ）〜（ヘ）を行う（ステップ１６０１）。（イ）各文字群出現頻度を初期化する。（ロ）文字群累積出現頻度をとる。（ハ）各文字出現頻度を“１”とする。（ニ）各文字群毎に累積出現頻度をとる。（ホ）一つ前の文字の群番号を保持する。（ヘ）一つ前の群番号を保持しておくレジスタＲ（＝文
脈）を初期化する。

【００８８】次に、一文字（ｋとする）を入力する（ス
テップ１６０２）。そして、どの文字群（Ｋとする）に
入力文字ｋが属するかを判別する（ステップ１６０
３）。

【００８９】そして、「RKの出現頻度／Rの出現頻度」
を意味する条件付き確率P(K|R)を符号部３０にて算術符
号化する。つまり、R に続いてそれぞれの群が起こる確
率に従って区間を分割し、このうち群K の区間を選択す
る。なお、各群の区間は、Rに続いて起こる文字群の累
積出現頻度によってその下限が求まる（ステップ１６０
４）。

【００９０】そして、条件付き確率P(k|K)を算術符号化
すると共に、文字群の条件付累積出現頻度CF(k|K)を使
用して、入力文字ｋを算術符号化する（ステップ１６０
５）。

【００９１】そして、文字出現頻度C(k|K)、C(K|R)の値
をそれぞれ“１”だけ増加させる（ステップ１６０
６）。そして、文字群Ｋの辞書を文字出現頻度C(x|K)に
従って並び替える（ステップ１６０７）。

【００９２】そして、文字群Ｋの文字累積出現頻度CF(x
|K)を更新すると共に、文字群Ｒに続く文字群の群累積
出現頻度CF(X|R)を更新する（ステップ１６０８）。そ
して、レジスタＲに入力文字ｋを設定する（ステップ１
６０９）。

【００９３】以後、ステップ１６０２からの処理を繰り
返す。＜実施例の効果＞次に、実施例のデータ圧縮効果を図１
６を参照して説明する。

【００９４】図１６（Ａ）は、データ圧縮率が圧縮対象
ファイルのサイズによってどう変化するかを、本実施例
による場合、静的符号化方式（準適応型）による場合及
び適応型符号化方式による場合の３つのケースについて
示したものである。図１６（Ａ）の横軸と横軸は、それ
ぞれ圧縮対象ファイルサイズとデータ圧縮率であり、線
７ａは、本実施例による場合、線７ｂは、静的符号化方
式による場合、線７ｃは、適応型符号化方式による場合
をそれぞれ示している。

【００９５】図１６（Ａ）から明らかなように、静的符
号化方式による場合は、圧縮対象ファイルのサイズにか
かわらずほぼ一定のデータ圧縮率を保持し、比較対象の
中では最もデータ圧縮できていることが分かる。一方、
適応型符号化方式と本実施例による場合は、圧縮対象フ
ァイルのサイズが大きくなるほど圧縮率が小さく、即
ち、よりよくデータ圧縮され、静的符号化方式のデータ
圧縮率に近づくことが分かる。そして、本実施例による
場合は、適応型符号化方式による場合よりも常にデータ
圧縮率が小さくなっている。

【００９６】ここで、圧縮対象ファイルサイズがほぼ０
の時における、適応型符号化方式による場合と静的符号
化方式による場合のデータ圧縮率の差は、静的符号化方
式には、各文字出現頻度の初期値が与えられているため
である。

【００９７】また、圧縮対象ファイルサイズがぼぼ０の
時における、適応型符号化方式による場合と本実施例に
よる場合とのデータ圧縮率の差は、本実施例には、各群
出現頻度の初期値が与えられているためである。

【００９８】次に、図１６（Ｂ）は、圧縮前のファイル
サイズによって圧縮後のファイルサイズがどう変化する
かを、本実施例による場合、静的符号化方式（準適応
型）による場合及び適応型符号化方式による場合の３つ
のケースについて比較したものである。なお、図１６
（Ｂ）中には、符号化を行わない場合も参考に記してあ
る。図１６（Ｂ）の横軸と縦軸は、それぞれ圧縮前のフ
ァイルサイズと圧縮後のファイルサイズであり、線７ｄ
は、本実施例による場合、線７ｅは、静的符号化方式に
よる場合、線７ｆは、適応型符号化方式による場合、線
７ｇは、符号化を行わない場合をそれぞれ示している。

【００９９】図１６（Ｂ）から明らかなように、符号化
を行ういずれの場合にも、圧縮前のファイルサイズが大
きくなるほど、圧縮後のファイルサイズの増加は鈍るこ
とが分かる。また、静的符号化方式による場合と本実施
例による場合は、ファイルサイズが小さい場合に、圧縮
後のファイルサイズが圧縮前のファイルサイズよりも大
きくなることが分かる。

【０１００】そして、所定値よりも圧縮前のファイルサ
イズが小さいときは、静的符号化方式による場合、本実
施例による場合、適応型符号化方式による場合の順に圧
縮後のファイルサイズが小さくなるが、前記所定値より
も圧縮前のファイルファイルサイズが大きくなると、適
応型符号化方式による場合、静的符号化方式による場
合、本実施例による場合の順に圧縮後のファイルサイズ
が小さくなることが分かる。

【０１０１】ここで、圧縮前のファイルサイズがほぼ０
の時における、静的符号化方式に補助データを付加した
場合のファイルサイズが０でないのは、各文字出現頻度
の初期値情報を補助データとして持つためである。

【０１０２】また、圧縮前のファイルサイズがほぼ０の
時における、本実施例に補助データを付加した場合のフ
ァイルサイズが０でないのは、各群出現頻度の初期値情
報を補助データとして持つためである。

【０１０３】

【発明の効果】本発明の第１のデータ圧縮方法及びデー
タ圧縮装置によれば、文字を互いに同じ統計的性質を有
する文字ごとに複数の群に分類し、さらに、それぞれの
群の出現確率を計算するようにしたため、従来の方法に
比べ、初期の段階で最適な符号領域を割り振ることがで
きる。これは、出現可能な文字数が多く、圧縮対象ファ
イルが小さいときに特に有効である。つまり、従来の適
応型符号化方式では、確率モデルを構築するのにある程
度の長さの入力列を必要とし、圧縮対象のサイズが小さ
い場合は圧縮率が上がらないのに対して、本発明では、
十分な圧縮率を得ることができる。

【０１０４】本発明の第２及び第３のデータ圧縮方法に
よれば、第１のデータ圧縮方法に比べ、データの出現確
率に従った符号を予め割り当てることができるため、フ
ァイルサイズが小さい場合にも高い圧縮率を得ることが
可能になる。

【０１０５】本発明の第４のデータ圧縮方法によれば、
入力データに従って出現頻度を計算し直すので、徐々に
データに即した出現頻度に基づく圧縮が可能になる。本
発明の第５及び第６のデータ圧縮方法によれば、直前に
出現した文字が属する群あるいは直々前に出現した文字
が属する群を条件とした条件付確率を用いることで、さ
らに高い圧縮率が得られるようになる。

【図面の簡単な説明】

【図１】本発明のデータ圧縮の原理図である。（Ａ）は
データ圧縮方法の原理図を示し、（Ｂ）はデータ圧縮装
置の原理図を示す。

【図２】多値算術符号の原理を示す図である。（Ａ）
は、各文字の出現頻度を示している。（Ｂ）は、出現頻
度順の累積出現頻度を示している。（Ｃ）は、算術符号
化の原理を示している。

【図３】算術符号化の装置構成を示す図である。

【図４】従来の多値算術符号化のフローを示す図であ
る。

【図５】文脈の木構造（２次の場合）を示す図である。

【図６】従来の多値算術符号化（−１、０次のブレンデ
ィング）のフローを示す図である。

【図７】実施例の装置構成の概略を示す図である。

【図８】実施例の装置構成を詳細に示す図である。

【図９】群分類と群出現確率を示す図である。

【図１０】実施例の多値算術符号化のフローを示す図で
ある（その１）。

【図１１】実施例の多値算術符号化のフローを示す図で
ある（その２）。このフローは、−１、０次のブレンデ
ィングになっている。

【図１２】文字群出現確率及び初期符号区間を示す図で
ある。（Ａ）は、文字群出現確率を示している。（Ｂ）
は、確率モデル未保持区間時点における符号区間を示し
ている。

【図１３】文字群分類部を示す図である。

【図１４】実施例の多値算術符号化のフローを示す図で
ある（その３）。

【図１５】実施例の多値算術符号化のフローを示す図で
ある（その４）。

【図１６】従来の算術符号化と本実施例の算術符号化と
の効果の比較図である。（Ａ）は、圧縮対象ファイルサ
イズが変化した場合におけるデータ圧縮率の変化を示し
ている。（Ｂ）は、圧縮前のファイルサイズが変化した
場合における圧縮後のファイルサイズの変化を示してい
る。

【符号の説明】

Ｓ１群構成ステップＳ２群出現確率計算ステップＳ３群中文字出現確率計算ステップＭ１群構成部Ｍ２群出現確率計算部Ｍ３群中文字出現確率計算部１０文字群分類部１１群分類部１２群確率保持部１３群カウンタ２０確率モデル作成部２１辞書２２カウンタ３０符号部３１テーブル３２算術符号化部４０算術符号部

Claims

【特許請求の範囲】

【請求項１】入力された文字を、その出現確率に応じた
符号長を持つ可変長符号に符号化することでデータの圧
縮を行うデータ圧縮方法において、入力される可能性がある文字を、互いに同じ統計的性質
を有する文字毎に階層的な複数の群にそれぞれ分類する
群構成ステップと、前記それぞれの群の出現確率を計算する群出現確率計算
ステップと、前記複数の群中における入力文字の出現確率を計算する
群中文字出現確率計算ステップと、前記群中文字出現確率計算ステップで計算された出現確
率に基づいて入力文字を符号化する入力文字符号化ステ
ップとを備えたことを特徴とするデータ圧縮方法。
【請求項２】前記群構成ステップでは、前記群の構成要
素の分類を予め固定して与えることを特徴とする請求項
１に記載のデータ圧縮方法。
【請求項３】前記群出現確率計算ステップでは、前記群
の出現確率を予め固定して与えることを特徴とする請求
項１に記載のデータ圧縮方法。
【請求項４】前記群出現確率計算ステップでは、前記群
の出現確率に予め初期値を設定するとともに、この群の
出現確率を前記文字の入力に応じて動的に再計算するこ
とを特徴とする請求項１に記載のデータ圧縮方法。
【請求項５】前記群出現確率計算ステップでは、前記群
の出現確率を、直前の複数文字が属する各々の群が出現
することを条件とする条件付群出現確率で計算すること
を特徴とする請求項１に記載のデータ圧縮方法。
【請求項６】前記群構成ステップでは、前記階層的な複
数の群を、高出現確率文字で構成される第１の群と、低
出現確率文字で構成される第２の群とで構成することを
特徴とする請求項１に記載のデータ圧縮方法。
【請求項７】入力された文字を、その出現確率に応じた
符号長を持つ可変長符号に符号化することでデータの圧
縮を行うデータ圧縮装置において、入力される可能性がある文字を、互いに同じ統計的性質
を有する文字毎に階層的な複数の群にそれぞれ分類する
群構成部と、前記それぞれの群の出現確率を計算する群出現確率計算
部と、前記複数の群中における入力文字の出現確率を計算する
群中文字出現確率計算部と、前記群中文字出現確率計算部で計算された出現確率に基
づいて入力文字を符号化する入力文字符号化部とを備え
たことを特徴とするデータ圧縮装置。