JPH10294670A - 符号化装置、復号装置および符号化復号装置ならびにそれらの方法 - Google Patents

符号化装置、復号装置および符号化復号装置ならびにそれらの方法

Info

Publication number
JPH10294670A
JPH10294670A JP10121697A JP10121697A JPH10294670A JP H10294670 A JPH10294670 A JP H10294670A JP 10121697 A JP10121697 A JP 10121697A JP 10121697 A JP10121697 A JP 10121697A JP H10294670 A JPH10294670 A JP H10294670A
Authority
JP
Japan
Prior art keywords
code
symbol
codeword
encoding
data
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP10121697A
Other languages
English (en)
Other versions
JP3161697B2 (ja
Inventor
Taro Yokose
太郎 横瀬
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Fujifilm Business Innovation Corp
Original Assignee
Fuji Xerox Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Fuji Xerox Co Ltd filed Critical Fuji Xerox Co Ltd
Priority to JP10121697A priority Critical patent/JP3161697B2/ja
Priority to US09/058,355 priority patent/US6140945A/en
Publication of JPH10294670A publication Critical patent/JPH10294670A/ja
Application granted granted Critical
Publication of JP3161697B2 publication Critical patent/JP3161697B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00—Image coding
    • G06T9/005—Statistical coding, e.g. Huffman, run length coding

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)
  • Compression Of Band Width Or Redundancy In Fax (AREA)

Abstract

(57)【要約】 【課題】 適応的なハフマン符号を簡易に生成する。 【解決手段】 度数集計部２０は入力データ１００に含
まれるシンボルの出現度数を計数する。支配シンボル選
択部３０は度数データ１２０から所定の閾値より大きい
度数をもつデータだけを支配シンボル度数データ１２０
として符号割当部４０へ送出する。固定符号語メモリ５
０は、予め生成されたハフマン符号を蓄積し、固定符号
語データ１３０として符号割当部４０へ送出する。符号
割当部４０は、支配シンボルに対してハフマン符号を生
成し、また、そのハフマン符号と固定符号語メモリ５０
に蓄積された固定符号語データとを合成して全体のハフ
マン符号を得る。得られたハフマン符号は符号語メモリ
６０に蓄積され、ハフマン符号化部７０は符号語メモリ
６０に蓄積されたハフマン符号を用いて入力データ１０
０に対してハフマン符号化を行う。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】この発明はデータの圧縮技
術、例えばハフマン符号を用いた圧縮技術に関するもの
である。
【０００２】
【従来の技術】一般に通信、蓄積等を行う場合、データ
の圧縮を行うとデータ量を削減する効果が得られる。こ
のような圧縮技術の代表例としてハフマン符号がある。
【０００３】以下ハフマン符号について説明する。ハフ
マン符号は公知の技術であり、例えば『文書データ圧縮
アルゴリズム入門（植松著／ＣＱ出版社）』（ｐｐ．４
６−５）にその記載がある。ハフマン符号は大まかに言
うと多く発生するシンボルには短い符号、発生しづらい
シンボルには長い符号を与えることによってデータを圧
縮する。ハフマン符号の一例を図１３に示す。
【０００４】ハフマン符号が有効であるための条件とし
て、以下の２つがあげられる。
【０００５】（１）各シンボルの出現確率が既知である
こと （２）各シンボルの出現確率が定常的であること 条件（１）はハフマン符号の生成が出現確率に依存する
こと、条件（２）はハフマン符号が固定の符号表を用い
ることに起因する。しかし条件（１）を満たすためには
入力データに対して符号化前に一度統計処理を行う必要
があり、処理が重くなる。また条件（２）は一般のデー
タ系列では成立しない。
【０００６】条件（１）と（２）を緩和する従来技術と
して、符号化しながら適当な間隔でハフマン符号を更新
する技術がある。この場合、直前に符号化したデータの
統計に基づいて符号を設計するので条件（１）の必要が
なく、また更新間隔毎に最適な符号を使うので条件
（２）も緩い変化であれば許容できる。以下、特開平７
−７４３６号公報を参考に、この従来例について説明す
る。図１４および１５はそれぞれ従来例の符号化装置、
復号装置を説明するブロック図である。まず図１４を用
いて従来例の符号化装置について説明する。図中、１０
はデータ入力部、２０は度数集計部、４０は符号割当
部、６０は符号語メモリ、７０はハフマン符号化部、８
０は符号出力部、１００は入力データ、１１０は度数デ
ータ、１４１は符号語データ、１５１は符号データであ
る。
【０００７】図１４の各部について説明する。データ入
力部１０は外部から符号化すべきデータを入力し、入力
データ１００として度数集計部２０およびデータメモリ
９０へ送出する。度数集計部２０は入力データ１００に
含まれるシンボルの出現度数を計数し、度数データ１１
０として符号割当部４０へ送出する。符号割当部４０は
度数データ１１０を基に符号語データ１４１を生成し、
符号語メモリ６０に蓄積する。ハフマン符号化部７０は
符号語メモリ６０に蓄積された符号語データ１４１を用
いて入力データ１００に対してハフマン符号化を行い、
符号データ１５１として符号出力部８０へ送出する。符
号出力部８０は作成された符号データ１５１を外部へ出
力する。
【０００８】次に図１６を用いて従来例の復号装置につ
いて説明する。図１４と同様の部分には同じ符号を付し
て説明を省略する。１５は符号入力部、７５はハフマン
復号部、８５はデータ出力部である。
【０００９】図１６の各部について説明する。符号入力
部１５は外部から復号すべき符号を入力し、符号データ
１５１としてハフマン復号部７５へ送出する。ハフマン
復号部７５は符号語メモリ６０に蓄積された符号語デー
タ１４１を用いて符号入力部１５から入力された符号デ
ータ１５１に対してハフマン復号を行い、入力データ１
００としてデータ出力部８５へ送出する。データ出力部
８５は作成された入力データ１００を外部へ出力する。
【００１０】以上の構成に基づいて従来例の動作につい
て説明する。図１５、１７はそれぞれ従来例の符号化、
復号動作を説明するフローチャートである。
【００１１】以下、図１５を用いて符号化処理を説明す
る。Ｓ１０では度数集計部２０において入力データ１０
０に含まれるシンボルを種類別にカウントし、度数デー
タ１１０を得る。Ｓ２１１ではその時点で予め定められ
た符号表更新処理条件を満たしているかどうかを判定
し、満たしていればＳ２１２へ、そうでなければＳ３０
へ進む。Ｓ２１２では符号割当部４０において度数デー
タ１１０に基づいてハフマン符号を生成し符号語データ
１４１を得る。Ｓ３０ではハフマン符号化部７０におい
て符号語データ１４１を用いて入力データ１００にハフ
マン符号化を行う。Ｓ４０では未処理の入力データ１０
０の有無を判定し、あればＳ１０へ、なければ符号化処
理を終了する。
【００１２】次に図１７を用いて復号処理を説明する。
図１５と同様の処理には同じ符号を付して説明を省略す
る。Ｓ５０ではハフマン復号部７５において符号語デー
タ１４１を用いて符号データ１５１に対してハフマン復
号を行う。
【００１３】以上の動作の中で、最初の符号化および復
号処理を行う際に用いる符号は同一の初期値が与えられ
るものとする。予め汎用的に設計されたものを固定的に
用いてもよいし、入力データ用に特に設計した符号を用
いてもよいが、後者の場合には符号データのヘッダに符
号表を付与するなどして、復号側に符号表を知らせる必
要がある。
【００１４】Ｓ２１２における符号表更新処理条件は任
意である。例えば前出の特開平７−７４３６号公報では
特に動画像を対象とし、１枚の画像毎に符号表を更新す
る。
【００１５】Ｓ２１３におけるハフマン符号の作成アル
ゴリズムは公知であり、例えば前出の『文書データ圧縮
アルゴリズム入門（植松著／ＣＱ出版社）』にも記載が
あるのでここでは詳述しない。おおざっぱにいえば各シ
ンボルを出現確率順にソートし、出現確率の小さい２つ
のシンボルを組み合せ新たなシンボルとする。これを繰
り返しながら符号を割り振る。
【００１６】以下、従来例の問題点について述べる。従
来例では符号表の更新は、入力されるシンボルの出現確
率分布の定常性が成立する単位で行われることが望まし
い。そのためには各シンボルの出現確率分布を推定する
のに十分な統計さえとれれば、更新の間隔はなるべく短
いほうがよい。例えば前出の特開平７−７４３６号公報
とは違って静止画像を対象とするような場合、画像間の
出現確率分布の類似性は期待できないので、画像内での
更新が有効になる。
【００１７】一方でＳ２１３におけるハフマン符号の生
成処理は、ソート処理を多用する。このため、符号表の
更新間隔の短縮は全体の処理負荷の増加を招く。
【００１８】これを改善する従来例としては、例えば特
開昭６３−２３２６２６号公報があげられる。特開昭６
３−２３２６２６号公報ではシンボルを出現頻度順に並
べ換え、予め用意された符号表に書き込むことで疑似的
にハフマン符号を構成する。この手法だとソート処理が
一度で済むのでハフマン符号生成処理の負荷を削減でき
る。
【００１９】この場合の問題点は符号量を効率的に小さ
くできる保証がないことにある。つまり、頻度順にソー
トしたとしてもその結果出てくる確率分布は何通りも考
えられるので、最適な符号を生成する保証がない。
【００２０】
【発明が解決しようとする課題】本発明は上記の事情を
鑑みてなされたもので、簡易に適応的な圧縮符号例えば
ハフマン符号を生成する符号化技術を提供することを目
的とする。
【００２１】
【課題を解決するための手段】本発明の第１の側面によ
れば、符号化装置に、符号化対象データを入力するデー
タ入力手段と、前記データ入力手段から入力される前記
符号化対象データに含まれる各シンボルの出現度数を計
数する度数集計手段と、前記度数集計手段により計数さ
れた出現度数に基づいて、前記シンボルのセットから支
配シンボルを選択するデータ選択手段と、各シンボルの
予測される出現確率に従って予め設計した符号語を保持
する固定符号語記憶手段と、前記支配シンボルに対して
は所定の手法で新たに符号語を生成し、さらにその他の
シンボルに対しては、前記支配シンボル以外のシンボル
であることを示す符号語と前記固定符号語記憶手段に保
持された符号語とを組み合せたものを新たな符号語とし
て割当てる符号割当手段と、前記符号割当手段で生成さ
れた符号語を保持する符号語記憶手段と、前記符号語記
憶手段に保持した符号語に基づいて前記データ入力手段
から入力される前記符号化対象データを符号化する符号
化手段と、前記符号化手段で生成された符号データを出
力する符号出力手段とを設けるようにしている。
【００２２】また、本発明の第２の側面によれば、復号
装置に、符号データを入力する符号入力手段と、符号語
を記憶する符号語記憶手段と、前記符号語記憶手段に保
持した符号語に基づいて前記符号入力手段から入力され
る前記符号データを復号する復号手段と、前記復号手段
の復号により生成したデータに含まれる各シンボルの出
現度数を計数する度数集計手段と、前記度数集計手段に
より計数した出現度数に応じて、前記シンボルのセット
から支配シンボルを選択するデータ選択手段と、各シン
ボルの予測される出現確率に従って予め設計した符号語
を保持する固定符号語記憶手段と、前記支配シンボルに
対しては所定の手法で新たに符号語を生成し、さらにそ
の他のシンボルに対しては前記支配シンボル以外のシン
ボルであることを示す符号語と前記固定符号語記憶手段
に保持された符号語とを組み合せたものを新たな符号語
として割当てる符号割当手段とを設け、前記符号割当手
段で生成された符号語を前記符号語記憶手段に記憶さ
せ、さらに、前記復号手段が復号したデータを出力する
データ出力手段を設けるようにしている。
【００２３】また、本発明の第３の側面によれば、上記
符号化装置と上記復号装置とを組み合わせて符号化復号
装置を構成している。
【００２４】このような構成によれば、平均符号語長に
とくに影響がある支配シンボルについて適応的に符号語
を更新するので符号量を小さくすることができ、しかも
符号語の更新の付加を少なくできる。
【００２５】また、以上の構成において、前記データ選
択手段で行われる選択処理は、前記度数集計手段の集計
結果に基づいて、予め定められた閾値より大きい度数を
持つシンボルを前記支配シンボルとして選択するように
することができる。
【００２６】また、前記データ選択手段で行われる選択
処理は、前記度数集計手段の集計結果に基づいて、出現
頻度の大きさ順に並べたときに予め定められた順位より
若い順位を持つシンボルを前記支配シンボルとして選択
するようにしてもよい。
【００２７】また、前記データ選択手段で行われる選択
処理は、前記度数集計手段の集計結果に基づいて、出現
頻度の大きさ順に並べ大きい方から出現頻度を累積した
ときの累積頻度が予め定められた閾値より小さいシンボ
ルを前記支配シンボルとして選択するようにしてもよ
い。
【００２８】また、前記符号割当手段で行われる符号化
はハフマン符号化とすることができる。
【００２９】また、前記符号割当手段において前記支配
シンボルに割当てるはずだった固定符号語が余ってお
り、かつそれより符号長の長い符号を持つ支配シンボル
でないシンボルがある場合、一時的にそのシンボルに前
記固定符号語を割当てるようにしてもよい。
【００３０】また、前記符号割当手段における符号語作
成処理は、各シンボルの出現確率が所定値を外れた場合
に行われるようにしてもよい。
【００３１】また、前記符号割当手段における符号語作
成処理は、所定数のシンボルの符号化または復号が完了
した場合に行われるようにしてもよい。
【００３２】また、前記符号割当手段で生成された符号
語の平均符号語長が前記固定符号語手段に保持された符
号語の平均符号語長より長くなると予測される場合には
前記固定符号語を新たな符号語とするようにしてもよ
い。
【００３３】また、前記度数集計手段で行われる統計値
の初期化はそれまでの統計値に１以下の正の数を乗算し
て行うようにしてもよい。
【００３４】また、前記固定符号語記憶手段に保持する
符号語を既処理データの統計に基づいて新たに生成した
符号語で置き換えるようにしてもよい。
【００３５】また、前記符号割当手段における符号語作
成処理は、予めシンボルの出現確率パターンとそれに対
応する符号語を用意しておき、前記支配シンボルを前記
出現確率パターンへ分類することによって簡易に前記符
号語を得るようにしてもよい。
【００３６】また、前記支配シンボルに対するパターン
分類は、最頻シンボルの出現確率と閾値の大小比較によ
って行うようにしてもよい。
【００３７】また、前記支配シンボルに対するパターン
分類は、支配シンボルを頻度順に並べたとき複数の予め
定められた順番に対応したシンボルの頻度による演算結
果で決定するようにしてもよい。
【００３８】また、前記符号語記憶手段に初期値として
設定される符号は予め定数が設定してあってもよい。
【００３９】また、前記符号語記憶手段に初期値として
設定される符号は前記固定符号語記憶手段に保持された
符号を用いてもよい。
【００４０】また、本発明の第４の側面によれば、複数
のシンボルを含むデータを入力し、前記入力されたデー
タに含まれる各シンボルの出現度数を計数し、前記計数
された出現度数に応じて、前記シンボルのセットから支
配シンボルを選択し、前記選択された支配シンボルに対
して所定の手法で符号語を生成し、前記選択された支配
シンボル以外のシンボルに対して予測される出現確率に
従って予め設計した符号語を生成し、前記生成された符
号語を用いて前記入力データを符号化するようにしてい
る。
【００４１】また、本発明の第５の側面によれば、符号
データを入力し、前記符号データを復号して得られる各
シンボルの出現度数を計数し、前記計数された出現度数
に応じて、前記シンボルのセットから支配シンボルを選
択し、前記選択された支配シンボルに対して所定の手法
で符号語を生成し、前記選択された支配シンボル以外の
シンボルに対して予測される出現確率に従って予め設計
した符号語を生成し、前記生成された符号語を用いて前
記符号データを復号するようにしている。
【００４２】このような構成においても、平均符号語長
にとくに影響がある支配シンボルについて適応的に符号
語を更新するので符号量を小さくすることができ、しか
も符号語の更新の付加を少なくできる。
【００４３】
【発明の実施の態様】
［実施例１］実施例の具体的な説明に入る前に、本発明
の原理について説明する。従来のハフマン符号化復号装
置の問題点はハフマン符号の生成処理の負荷が重く、更
新処理を短くしにくいことであった。そこでこれを解決
するために、ハフマン符号を簡易的に生成することにす
る。すなわち、平均符号長に影響が大きいと思われる出
現頻度の高いシンボルに対しては通常どおりのハフマン
符号を生成し、それ以外のシンボルについては予め汎用
的に用意された符号を与えることにする。以下、このよ
うに出現頻度の高いシンボルを支配シンボルと呼ぶ。
【００４４】以上の点を具体的に説明する。ハフマン符
号の平均符号長は各シンボルｓに与えられた符号長ｌ
（ｓ）と出現確率ｐ（ｓ）の積和で表される。すなわ
ち、
【００４５】
【数１】 ただしＳはシンボル全体の集合を表す。いまｓ０からｓ
５まで６個のシンボルがあり、ｓ０とｓ１の出現確率が
それぞれ１／２、１／４で、それ以外のシンボルは１／
４に満たなかったとする。この仮定の下でエントロピー
すなわち理論平均符号長が最小となるのは、例えばｓ２
の出現確率がぎりぎり１／４に届かず、それ以外のシン
ボルの出現確率がほぼ０となる場合である。この条件で
通常のハフマン符号を生成すると、最終的にｓ０、ｓ
１、ｓ２にそれぞれ符号長１、２、３［ｂｉｔ］の符号
が割当てられる。従って平均符号長は（１）式より、
【００４６】
【数２】 と計算できる。次に本発明において出現確率１／４以上
のシンボルを支配シンボルとみなしたとする。この場合
ｓ０とｓ１にそれぞれ符号長１、２［ｂｉｔ］の符号が
割当てられる。またその他のシンボルは支配シンボルで
ないことを表す２［ｂｉｔ］の符号と、ｓ２〜ｓ５のい
ずれかを示す２［ｂｉｔ］の符号で表す。この場合の平
均符号長は（１）式より、
【００４７】
【数３】 となる。出現確率にかかわらず符号を生成した場合の平
均符号長はｌｏｇ2（６）＝２．６［ｂｉｔ］となるか
ら、（３）式の値は（２）式には及ばないものの符号量
としては小さくなることがわかる。また以上の見積りは
本発明に対してかなり厳しい条件で計算したもので、実
際にはｓ２〜ｓ５の中でｓ２の出現確率だけが突出する
ような状況は考えにくいので、現実の（２）式と（３）
式の差はもっと小さいと考えられる。
【００４８】以下に本実施例について詳細に説明する。
図１および図４はそれぞれ本実施例の符号化装置および
復号装置の構成を示すブロック図である。図１４およ
び、１５に示した従来例と同様の部分には同じ符号を付
して説明を省略する。図中、３０は支配シンボル選択
部、５０は固定符号語メモリ、１２０は支配シンボル度
数データ、１３０は固定符号語データ、１４０は符号語
データ、１５０は符号データである。
【００４９】まず図１を用いて本実施例の符号化装置に
ついて説明する。図１の各部について説明する。支配シ
ンボル選択部３０は度数データ１２０から所定の閾値よ
り大きい度数をもつデータだけを支配シンボル度数デー
タ１２０として符号割当部４０へ送出する。固定符号語
メモリ５０は入力データ１００の想定される確率分布に
対して予め生成されたハフマン符号を蓄積し、固定符号
語データ１３０として符号割当部４０へ送出する。
【００５０】図４は本実施例の復号装置の構成を示す。
図４の各部の構成は従来例および本実施例の符号化装置
に関連して説明したものと同様であるので、説明を繰り
返さない。
【００５１】以上の構成に基づき、本実施例の動作につ
いて説明する。図２および図３は本実施例における符号
化処理の動作を、また図５は本実施例における復号処理
の動作を示すフローチャートである。
【００５２】まず図２および図３を用いて本実施例の符
号化処理の動作について説明する。ただし図２の各処理
については従来例と同様のため、同じ符号を付して説明
を省略する。以下、図３を用いてＳ２０の符号表更新に
ついて説明する。Ｓ２０１では符号表更新条件が成立し
ているかどうかを判定し、成立していればＳ２０２へ、
そうでなければＳ３０へ進む。Ｓ２０２ではシンボルの
ＩＤを示す変数ｎと支配シンボル度数データ１２０を蓄
積する支配シンボルリストを初期化する。Ｓ２０３では
度数データ１１０から変数ｎが示すシンボルの度数を取
り出して、所定の閾値Ｔｈと比較し大ならばＳ２０４
へ、小ならばＳ２０５へ進む。Ｓ２０４ではＳ２０３で
比較した度数データを、符号割当部４０の支配シンボル
リストに加える。Ｓ２０５では変数ｎに１を加える。Ｓ
２０６では処理されていないシンボルの有無を判断し、
未処理データがあればＳ２０３へ、なければＳ２０７へ
進む。Ｓ２０７では符号割当部４０において支配シンボ
ルリストに存在する支配シンボルに対してハフマン符号
を生成する。Ｓ２０８では符号割当部４０においてＳ２
０７で作成されたハフマン符号と固定符号語メモリ５０
に蓄積された固定符号語データ１３０を合成して全体の
ハフマン符号を得る。
【００５３】図５は本実施例の復号処理の動作を示す。
図５の全体は従来例と同様であり、また図５のＳ２０は
本実施例の符号化処理の動作と同様であるので省略す
る。
【００５４】以上の動作の中で、最初の符号化および復
号は例えば固定符号語メモリ５０の符号語に従う。この
とき、従来例で述べたように別の初期値が符号語メモリ
６０に書き込まれてもよい。
【００５５】次に符号割当部４０で行われる処理の詳細
について説明する。以下、説明を簡単化するためシンボ
ルをアルファベットの小文字２６個とする。符号割当部
４０の支配シンボルリストには選択されなかったシンボ
ルに符号を与えるため、”その他”というシンボルを初
期化時に登録しておく。このときの支配シンボルリスト
の内部フォーマット例を図６（ａ）に示す。Ｓ２０３で
用いる閾値Ｔｈを例えば全体の１／４とすれば、Ｔｈに
等しい度数を持つシンボルは選択されないので、支配シ
ンボルは最大で３個となる。支配シンボル度数データ１
２０のフォーマット例を図６（ｂ）に、全てのシンボル
に対する選択処理が終了しＳ２０７に入る直前の支配シ
ンボルリスト例を図６（ｃ）に示す。ただし符号表更新
条件を１００個のシンボルの符号化が終了した場合とし
た。このとき”その他”の出現度数は全体の度数から支
配シンボルの度数を減算したものとする。もしくはＳ２
０３の直後において選択されなかったシンボルの度数を
逐次的に加算していってもよい。図６（ｃ）で選択され
たシンボルに対してＳ２０７でハフマン符号化を行った
例を図６（ｄ）に示す。これで”ａ”、”ｅ”、”ｓ”
の３つの支配シンボルに対応する符号が生成された。
【００５６】これ以外のシンボルに対しては”その他”
の符号と固定符号語メモリ５０にデフォルトとして用意
された固定符号語を合成して割当てる。固定符号語の例
を図７（ｂ）に示す。この符号表は予め符号化処理開始
前にシンボルの出現確率を推定して作成しておく。Ｓ２
０７で作成した符号を図７（ａ）に、固定符号語と合成
した最終的な符号を図７（ｃ）にそれぞれ示す。このと
き支配シンボルに対して固定符号語が割当てた符号、図
７の例でいえばシンボル”ａ”を示す”１１１０００”
等が無駄になるが、平均符号長への影響は少ないので無
視する。ただし簡易的な処置として例えば固定符号語の
シンボルを符号長の長いものと入れ換えるような処理を
行ってもよい。図７の例でいえば”１１１０００”がど
うせ使われないのであるから、図７（ｂ）の”ａ”と”
ｂ”を一時的に入れ替えて”１１１０００”を”ｂ”の
符号としてもよい。
【００５７】もしＳ２０７に達したとき支配シンボル
が”その他”以外になかった場合には、固定符号語をそ
のまま符号語データ１４０として用いる。ところで支配
シンボルが”その他”を含めて２つ以上あっても、固定
符号語を用いた方が平均符号長が短くなる場合がある。
これを避けるためには以下のような処理を追加すればよ
い。
【００５８】簡単のため支配シンボルが”その他”を含
めて２つと仮定する。これ以外の条件でも以下の説明か
ら容易に類推が可能である。まず固定符号語の理想的な
確率分布が発生したとしたときの平均符号長をｌｔｈと
し、これを固定符号語の理論的平均符号長と考える。す
なわち、シンボル”ａ”の推定出現確率をｐｔｈ
（ａ）、割当てられた符号長をｌｆｉｘ（ａ）とすれば
（４）式のようになる。
【００５９】
【数４】 ただし総和は出現し得るシンボル全てについてとる。次
に支配シンボルを”その他”と”ｘ”とし、Ｓ２０７で
それぞれ”１”、”０”の符号を割当てられたとする。
このときの平均符号長ｌｓｅｌは以下の式で近似的に求
められる。
【００６０】
【数５】 ここでｐ（ａ）はシンボル”ａ”の出現頻度を実測して
計算した出現確率である。２項目のｌｔｈ’は固定符号
語から”ｘ”が抜けた場合の理論的平均符号長である。
これは（４）式から、
【００６１】
【数６】 として近似する。ただし総和は”ｘ”以外の出現し得る
シンボル全てについてとる。（５）式に対して”ｘ”が
選択されたにもかかわらず固定符号語を使いつづける場
合の平均符号長ｌｆｉｘは、
【００６２】
【数７】 となるから、（５）式−（７）式を計算して、
【００６３】
【数８】 となる。従ってこの（８）式が正であれば固定符号語そ
のままを、負であれば新たに合成した符号語を用いれば
よい。
【００６４】上記の動作の中で符号表更新条件は、従来
例同様に任意にとることができる。例えば上述の説明例
のように処理データ量に依存してもよいし、確率分布の
変化度合いに応じてもよい。例えば出現度数を監視して
おき、支配シンボル以外のシンボル（上述の例では出現
確率が１／４を越えないシンボル）の出現度数がある出
現確率（例えば１／３とか）を越えて出現しつづけるよ
うであれば、確率分布が変化したと判定する。この例を
図８に示す。これとは逆に支配シンボルの出現確率低下
を監視してもよい。
【００６５】また、上述の例では支配シンボルは出現頻
度を閾値処理して選択したが、その他の手法で支配シン
ボルを決定してもよい。要するに出現頻度に応じて支配
シンボルを決定すればよい。例えば、頻度順にソートし
たときの上からの順位を閾値処理してもよい。すなわ
ち、上位の所定番目までのシンボルを支配シンボルとし
てもよい。こうすれば、支配シンボルの個数を一定に保
つことができる。また頻度順にソートし、上の順位のシ
ンボルから順番にその頻度を累積し、その累積値を閾値
処理するようにしてもよい。すなわち、累積値が所定値
以下となるシンボルを支配シンボルとする。例えば、１
番目から５番目のシンボルを累積した値が所定値以下で
あり、６番目までの累積値が所定値を超える場合には、
１番目から５番目までのシンボルを支配シンボルとす
る。このようにすると、支配シンボルの影響を定性的に
安定化させることができる。すなわち、支配シンボルの
全頻度が上述の所定値となるので、支配シンボルの影響
を安定化させることができる。
【００６６】また、度数集計部２０における出現度数の
計数は０で初期化しているが、既処理データに応じて初
期化時にオフセットされていても構わない。例えば初期
値をｃｏｕｎｔi、直前の出現度数をｃｏｕｎｔi-1とす
れば（９）式のような初期化が考えられる。
【００６７】
【数９】 これにより度数データの平滑化が図れ、局所的な確率分
布の変動に左右されない大局的な符号を作成することが
できる。
【００６８】また、最初の符号更新までに用いる初期値
の符号は固定符号語メモリ５０に蓄積したハフマン符号
を用いてもよいし、仕様として適当な初期値を設定して
もよい。
【００６９】また、適当なタイミングで固定符号語メモ
リ５０に蓄積するハフマン符号を変更すれば符号量の減
少が図れる。すなわち、既処理データの統計に基づいて
事前に推定した出現確率を補正し、新たにハフマン符号
を生成する。この場合は全てのシンボルに対して通常の
手法で生成する必要がある。
【００７０】また、以上ではすべてハフマン符号を前提
に説明したが、適応的に設計できる符号であれば他の符
号でも応用できる。整数長の符号でいえば、シャノン・
ファノ符号等が応用可能であるし、算術符号も符号語を
オージェンドの分割に置き換えれば応用が可能である。
【００７１】［実施例２］本発明をさらに簡易な処理で
実現するため、第２の実施例として支配シンボルのハフ
マン符号生成処理を簡略化した例について述べる。本実
施例の原理は、選択されるシンボルの出現確率がある閾
値より大きいことを利用し、ビット割当をいくつかのパ
ターンに分類して予め対応する符号を用意しておくこと
にある。さらにパターンの分類はごく簡単な処理で近似
的に行う。
【００７２】本実施例の全体の構成と動作は第１の実施
例と同様のため、説明を省略する。本実施例は第１の実
施例における図３のＳ２０７の処理の変形例として位置
づけられる。以下、説明を簡略化するために閾値をシン
ボル度数の総数の１／８とし、かつ”その他”の出現確
率が１／８より大きいと仮定した場合について述べる
が、他の場合についても容易に類推が可能であり一般性
は失われない。
【００７３】具体的な説明に入る。支配シンボル数が”
その他”を含めて３個以下の場合は自明なので、まず４
個の場合について述べる。いま４個の支配シンボルは出
現度数順にソートされているものとし、順にシンボル
１、シンボル２、…と呼ぶ。またシンボルｎの出現確率
をｐ（ｎ）と書く。従って
【００７４】
【数１０】 となる。このときビット割当ては図９（ａ）の２通りが
考えられる。それぞれの符号木を図９（ｂ）（ｃ）に示
す。さて両符号木の平均符号長はそれぞれ、
【００７５】
【数１１】 で表すことができる。さてｌｃａｓｅ１＝ｌｃａｓｅ２
となるための条件は次のようになる。
【００７６】
【数１２】 ｐ（ｎ）の総和は１となるので、次式を得る。
【００７７】
【数１３】 （１０）式の条件を考慮するとｌｃａｓｅ１＝ｌｃａｓ
ｅ２が成立するｐ（１）の範囲は１／３≦ｐ（１）≦２
／５となる。この範囲でｐ（１）が極値をとったときの
平均符号長の上限、下限を図９（ｄ）に示す。例えばｐ
（１）が１／３の場合２／９≦ｐ（２）≦１／３でなけ
ればならず、さらにそれぞれの場合にｐ（３）、ｐ
（４）の値も限定される。その結果ｃａｓｅ１の平均符
号長は２ないし２．１１となることがわかる。図９
（ｄ）よりｐ（１）が２／５を越えれば必ず図９（ａ）
のｃａｓｅ１の、逆に１／３を下回れば必ずｃａｓｅ２
のビット割当てが最適となることがわかる。１／３＜ｐ
（１）＜２／５の場合は最適ビット割当ては特定できな
いが、いずれか判断を誤っても符号量の差は少ないので
無視する。
【００７８】図１０は第２の実施例の動作を説明するフ
ローチャートである。図１０を用いて処理手順を説明す
る。Ｓ２０７１では支配シンボルを度数順にソートす
る。Ｓ２０７２では出現頻度の最大値ｐ（１）が閾値ｐ
ｔｈを越えているかどうか判定し、ｐ（１）＞ｐｔｈで
あればＳ２０７４へ、そうでなければＳ２０７３へ進
む。Ｓ２０７３では図９（ａ）のｃａｓｅ２の符号を選
択し、Ｓ２０７４ではｃａｓｅ１の符号を選択する。Ｓ
２０７５では支配シンボルとＳ２０７３もしくはＳ２０
７４で得られた符号を対応づける符号表を生成する。以
上の動作の中でｐｔｈは１／３＜ｐ（１）＜２／５の範
囲で適当に選択する。例えば中間値である１１／３０で
もよいし、判定の容易さを考慮して１／３としてもよ
い。もし判定の容易さが符号量の増大よりも重要な場合
には上記の範囲を越えても評価が簡単な２のベキ乗の逆
数、例えば１／４や１／２としてもよい。ただし最適な
符号を得られない可能性が高くなる。
【００７９】逆に最適な符号を期すならば、ｌｃａｓｅ
２−ｌｃａｓｅ１＝ｐ（１）−ｐ（３）−ｐ（４）の正
負を計算してもよい。この場合処理負荷が若干増加する
が、符号は必ず最適となる。
【００８０】もうひとつの例として支配シンボルが”そ
の他”を含めて５個の場合について述べる。ビット割当
てを出現頻度順に列記する形式で示せば、支配シンボル
が５個の場合１２３４４、１３３３３、２２２３３の３
つのケースが考えられる。しかし各シンボルの出現確率
が１／８より大きいこととハフマン符号の生成規則か
ら、１２３４４となるケースは存在しない。従って実際
には図１１（ａ）の２つのケースを考えればよい。
【００８１】さてこの場合の両者の平均符号長はそれぞ
れ次式でかける。
【００８２】
【数１４】 前と同様にｌｃａｓｅ１＝ｌｃａｓｅ２が成立するｐ
（１）の範囲を考えると、１／３≦ｐ（１）≦３／８と
なる。それぞれの平均符号長の上限、下限を図１１
（ｄ）に示す。これよりｐ（１）≦１／３のときｃａｓ
ｅ２の、ｐ（１）≧３／８のときｃａｓｅ１のビット割
当てが最適となる。従って図１０のＳ２０７２で用いる
ｐｔｈは１／３から３／８の範囲、もしくはその近辺の
値から選べばよい。またシンボル数４個の時同様、ｌｃ
ａｓｅ２−ｌｃａｓｅ１＝ｐ（１）−ｐ（２）−ｐ
（３）の正負を計算すれば、最適な符号を得ることも可
能である。
【００８３】本実施例によればハフマン符号化処理が前
もって用意したパターンに分類するだけで行え、しかも
パターンの分類は支配シンボルのソート処理と比較処理
で行えるので、第１の実施例の処理の大幅な簡略化が図
れる。
【００８４】最後に本発明の効果を示す実験結果例を図
１２に示す。６ｂｉｔデータを入力とし次の４つの手法
で符号化した結果である。
【００８５】（１） 従来例 （２） 本発明 （支配シンボルが全体の１／１０） （３） 本発明 （支配シンボルが全体の１／５０） （４） 一般的ハフマン符号 （まずシンボルの統計を
とって符号生成し、２パス目で符号化するもの） 実験によれば（２）、（３）、（４）の処理時間はほぼ
等しく、（１）の約１／２０〜１／５０程度であった。
図１２から本発明の効果は明らかである。
【００８６】
【発明の効果】本発明によれば大量のメモリや処理負荷
なしに、簡易かつ適応的なハフマン符号を生成すること
ができる。
【図面の簡単な説明】
【図１】 本発明の符号化装置の第１の実施例を示す構
成図である。
【図２】 本発明の符号化装置の第１の実施例における
符号化処理の動作の一例を示すフローチャートである。
【図３】 本発明の符号化装置の第１の実施例における
符号表更新処理の動作の一例を示すフローチャートであ
る。
【図４】 本発明の復号装置の第１の実施例を示す構成
図である。
【図５】 本発明の復号装置の第１の実施例における復
号処理の動作の一例を示すフローチャートである。
【図６】 本発明の符号化装置の第１の実施例における
支配シンボルリストの内部フォーマット例を示す説明図
である。
【図７】 本発明の符号化装置の第１の実施例において
作成される符号例を示す説明図である。
【図８】 本発明の符号化装置の第１の実施例における
符号表更新に用いる条件例を示す説明図である。
【図９】 本発明の符号化復号装置の第２の実施例にお
いて作成される符号例を示す説明図である。
【図１０】 本発明の符号化復号装置の第２の実施例に
おける符号表更新処理の部分動作の一例を示すフローチ
ャートである。
【図１１】 本発明の符号化復号装置の第２の実施例に
おいて作成される符号例を示す説明図である。
【図１２】 本発明の符号化復号装置による実験結果例
を示す説明図である。
【図１３】 従来のハフマン符号例を示す説明図であ
る。
【図１４】 従来例の符号化装置を示す構成図である。
【図１５】 従来例の符号化装置における符号化処理の
動作の一例を示すフローチャートである。
【図１６】 従来例の復号装置を示す構成図である。
【図１７】 従来例の復号装置における復号処理の動作
の一例を示すフローチャートである。
【符号の説明】
１０ データ入力部 １５ 符号入力部 ２０ 度数集計部 ３０ 支配シンボル選択部 ４０ 符号割当部 ５０ 固定符号語メモリ ６０ 符号語メモリ ７０ ハフマン符号化部 ７５ ハフマン復号部 ８０ 符号出力部 ８５ データ出力部 １００ 入力データ １１０ 度数データ １２０ 支配シンボル度数データ １３０ 固定符号語データ １４０、１４１ 符号語データ １５０、１５１ 符号データ

Claims (50)

    【特許請求の範囲】
  1. 【請求項１】 符号化対象データを入力するデータ入力
    手段と、 前記データ入力手段から入力される前記符号化対象デー
    タに含まれる各シンボルの出現度数を計数する度数集計
    手段と、 前記度数集計手段により計数された出現度数に基づい
    て、前記シンボルのセットから支配シンボルを選択する
    データ選択手段と、 各シンボルの予測される出現確率に従って予め設計した
    符号語を保持する固定符号語記憶手段と、 前記支配シンボルに対しては所定の手法で新たに符号語
    を生成し、さらにその他のシンボルに対しては、前記支
    配シンボル以外のシンボルであることを示す符号語と前
    記固定符号語記憶手段に保持された符号語とを組み合せ
    たものを新たな符号語として割当てる符号割当手段と、 前記符号割当手段で生成された符号語を保持する符号語
    記憶手段と、 前記符号語記憶手段に保持した符号語に基づいて前記デ
    ータ入力手段から入力される前記符号化対象データを符
    号化する符号化手段と、 前記符号化手段で生成された符号データを出力する符号
    出力手段とを有することを特徴とする符号化装置。
  2. 【請求項２】 符号データを入力する符号入力手段と、 符号語を記憶する符号語記憶手段と、 前記符号語記憶手段に保持した符号語に基づいて前記符
    号入力手段から入力される前記符号データを復号する復
    号手段と、 前記復号手段の復号により生成したデータに含まれる各
    シンボルの出現度数を計数する度数集計手段と、 前記度数集計手段により計数した出現度数に応じて、前
    記シンボルのセットから支配シンボルを選択するデータ
    選択手段と、 各シンボルの予測される出現確率に従って予め設計した
    符号語を保持する固定符号語記憶手段と、 前記支配シンボルに対しては所定の手法で新たに符号語
    を生成し、さらにその他のシンボルに対しては前記支配
    シンボル以外のシンボルであることを示す符号語と前記
    固定符号語記憶手段に保持された符号語とを組み合せた
    ものを新たな符号語として割当てる符号割当手段とを有
    し、 前記符号割当手段で生成された符号語を前記符号語記憶
    手段に記憶させ、さらに、 前記復号手段が復号したデータを出力するデータ出力手
    段を有することを特徴とする復号装置。
  3. 【請求項３】 請求項１に記載の符号化装置と請求項２
    に記載の復号装置とを有することを特徴とする符号化復
    号装置。
  4. 【請求項４】 前記データ選択手段で行われる選択処理
    は、前記度数集計手段の集計結果に基づいて、予め定め
    られた閾値より大きい度数を持つシンボルを前記支配シ
    ンボルとして選択する請求項１に記載の符号化装置。
  5. 【請求項５】 前記データ選択手段で行われる選択処理
    は、前記度数集計手段の集計結果に基づいて、出現頻度
    の大きさ順に並べたときに予め定められた順位より若い
    順位を持つシンボルを前記支配シンボルとして選択する
    請求項１に記載の符号化装置。
  6. 【請求項６】 前記データ選択手段で行われる選択処理
    は、前記度数集計手段の集計結果に基づいて、出現頻度
    の大きさ順に並べ大きい方から出現頻度を累積したとき
    の累積頻度が予め定められた閾値より小さいシンボルを
    前記支配シンボルとして選択する請求項１に記載の符号
    化装置。
  7. 【請求項７】 前記符号割当手段で行われる符号化はハ
    フマン符号化であることを特徴とする請求項１、４、５
    または６に記載の符号化装置。
  8. 【請求項８】 前記符号割当手段において前記支配シン
    ボルに割当てるはずだった固定符号語が余っており、か
    つそれより符号長の長い符号を持つ支配シンボルでない
    シンボルがある場合、一時的にそのシンボルに前記固定
    符号語を割当てることを特徴とする請求項１または４、
    ５、６または７に記載の符号化装置。
  9. 【請求項９】 前記符号割当手段における符号語作成処
    理は、各シンボルの出現確率が所定値を外れた場合に行
    われることを特徴とする請求項１、４、５、６、７また
    は８に記載の符号化装置。
  10. 【請求項１０】 前記符号割当手段における符号語作成
    処理は、所定数のシンボルの符号化または復号が完了し
    た場合に行われることを特徴とする請求項１、４、５、
    ６、７、８または９に記載の符号化装置。
  11. 【請求項１１】 前記符号割当手段で生成された符号語
    の平均符号語長が前記固定符号語手段に保持された符号
    語の平均符号語長より長くなると予測される場合には前
    記固定符号語を新たな符号語とすることを特徴とする請
    求項１、４、５、６、７、８、９または１０に記載の符
    号化装置。
  12. 【請求項１２】 前記度数集計手段で行われる統計値の
    初期化はそれまでの統計値に１以下の正の数を乗算して
    行うことを特徴とする請求項１、４、５、６、７、８、
    ９、１０または１１に記載の符号化装置。
  13. 【請求項１３】 前記固定符号語記憶手段に保持する符
    号語を既処理データの統計に基づいて新たに生成した符
    号語で置き換えることを特徴とする請求項１、４、５、
    ６、７、８、９、１０、１１または１２に記載の符号化
    装置。
  14. 【請求項１４】 前記符号割当手段における符号語作成
    処理は、予めシンボルの出現確率パターンとそれに対応
    する符号語を用意しておき、前記支配シンボルを前記出
    現確率パターンへ分類することによって簡易に前記符号
    語を得ることを特徴とする請求項１、４、５、６、７、
    ８、９、１０、１１、１２または１３に記載の符号化装
    置。
  15. 【請求項１５】 前記支配シンボルに対するパターン分
    類は、最頻シンボルの出現確率と閾値の大小比較によっ
    て行うことを特徴とする請求項１４に記載の符号化装
    置。
  16. 【請求項１６】 前記支配シンボルに対するパターン分
    類は、支配シンボルを頻度順に並べたとき複数の予め定
    められた順番に対応したシンボルの頻度による演算結果
    で決定することを特徴とする請求項１４に記載の符号化
    装置。
  17. 【請求項１７】 前記符号語記憶手段に初期値として設
    定される符号は予め定数が設定してあることを特徴とす
    る請求項１、４、５、６、７、８、９、１０、１１、１
    ２、１３、１４、１５または１６記載の符号化装置。
  18. 【請求項１８】 前記符号語記憶手段に初期値として設
    定される符号は前記固定符号語記憶手段に保持された符
    号を用いることを特徴とする請求項１、４、５、６、
    ７、８、９、１０、１１、１２、１３、１４、１５また
    は１６記載の符号化装置。
  19. 【請求項１９】 前記データ選択手段で行われる選択処
    理は、前記度数集計手段の集計結果に基づいて、予め定
    められた閾値より大きい度数を持つシンボルを前記支配
    シンボルとして選択する請求項２に記載の復号装置。
  20. 【請求項２０】 前記データ選択手段で行われる選択処
    理は、前記度数集計手段の集計結果に基づいて、出現頻
    度の大きさ順に並べたときに予め定められた順位より若
    い順位を持つシンボルを前記支配シンボルとして選択す
    る請求項２に記載の復号装置。
  21. 【請求項２１】 前記データ選択手段で行われる選択処
    理は、前記度数集計手段の集計結果に基づいて、出現頻
    度の大きさ順に並べ大きい方から出現頻度を累積したと
    きの累積頻度が予め定められた閾値より小さいシンボル
    を前記支配シンボルとして選択する請求項２に記載の復
    号装置。
  22. 【請求項２２】 前記符号割当手段で行われる符号化は
    ハフマン符号化であることを特徴とする請求項２、１
    ９、２０または２１に記載の復号装置。
  23. 【請求項２３】 前記符号割当手段において前記支配シ
    ンボルに割当てるはずだった固定符号語が余っており、
    かつそれより符号長の長い符号を持つ支配シンボルでな
    いシンボルがある場合、一時的にそのシンボルに前記固
    定符号語を割当てることを特徴とする請求項２または１
    ９、２０、２１または２２に記載の復号装置。
  24. 【請求項２４】 前記符号割当手段における符号語作成
    処理は、各シンボルの出現確率が所定値を外れた場合に
    行われることを特徴とする請求項２、１９、２０、２
    １、２２または２３に記載の復号装置。
  25. 【請求項２５】 前記符号割当手段における符号語作成
    処理は、所定数のシンボルの符号化または復号が完了し
    た場合に行われることを特徴とする請求項２、１９、２
    ０、２１、２２、２３または２４に記載の復号装置。
  26. 【請求項２６】 前記符号割当手段で生成された符号語
    の平均符号語長が前記固定符号語手段に保持された符号
    語の平均符号語長より長くなると予測される場合には前
    記固定符号語を新たな符号語とすることを特徴とする請
    求項２、１９、２０、２１、２２、２３、２４または２
    ５に記載の復号装置。
  27. 【請求項２７】 前記度数集計手段で行われる統計値の
    初期化はそれまでの統計値に１以下の正の数を乗算して
    行うことを特徴とする請求項２、１９、２０、２１、２
    ２、２３、２４、２５または２６に記載の復号装置。
  28. 【請求項２８】 前記固定符号語記憶手段に保持する符
    号語を既処理データの統計に基づいて新たに生成した符
    号語で置き換えることを特徴とする請求項２、１９、２
    ０、２１、２２、２３、２４、２５、２６または２７に
    記載の復号装置。
  29. 【請求項２９】 前記符号割当手段における符号語作成
    処理は、予めシンボルの出現確率パターンとそれに対応
    する符号語を用意しておき、前記支配シンボルを前記出
    現確率パターンへ分類することによって簡易に前記符号
    語を得ることを特徴とする請求項２、１９、２０、２
    １、２２、２３、２４、２５、２６、２７または２８に
    記載の復号装置。
  30. 【請求項３０】 前記支配シンボルに対するパターン分
    類は、最頻シンボルの出現確率と閾値の大小比較によっ
    て行うことを特徴とする請求項２９に記載の復号装置。
  31. 【請求項３１】 前記支配シンボルに対するパターン分
    類は、支配シンボルを頻度順に並べたとき複数の予め定
    められた順番に対応したシンボルの頻度による演算結果
    で決定することを特徴とする請求項２９に記載の復号装
    置。
  32. 【請求項３２】 前記符号語記憶手段に初期値として設
    定される符号は予め定数が設定してあることを特徴とす
    る請求項２、１９、２０、２１、２２、２３、２４、２
    ５、２６、２７、２８、２９、３０または３１に記載の
    復号装置。
  33. 【請求項３３】 前記符号語記憶手段に初期値として設
    定される符号は前記固定符号語記憶手段に保持された符
    号を用いることを特徴とする請求項２、１９、２０、２
    １、２２、２３、２４、２５、２６、２７、２８、２
    ９、３０または３１に記載の復号装置。
  34. 【請求項３４】 前記データ選択手段で行われる選択処
    理は、前記度数集計手段の集計結果に基づいて、予め定
    められた閾値より大きい度数を持つシンボルを前記支配
    シンボルとして選択する請求項３に記載の符号化復号装
    置。
  35. 【請求項３５】 前記データ選択手段で行われる選択処
    理は、前記度数集計手段の集計結果に基づいて、出現頻
    度の大きさ順に並べたときに予め定められた順位より若
    い順位を持つシンボルを前記支配シンボルとして選択す
    る請求項３に記載の符号化復号装置。
  36. 【請求項３６】 前記データ選択手段で行われる選択処
    理は、前記度数集計手段の集計結果に基づいて、出現頻
    度の大きさ順に並べ大きい方から出現頻度を累積したと
    きの累積頻度が予め定められた閾値より小さいシンボル
    を前記支配シンボルとして選択する請求項３に記載の符
    号化復号装置。
  37. 【請求項３７】 前記符号割当手段で行われる符号化は
    ハフマン符号化であることを特徴とする請求項３、３
    ４、３５または３６に記載の符号化復号装置。
  38. 【請求項３８】 前記符号割当手段において前記支配シ
    ンボルに割当てるはずだった固定符号語が余っており、
    かつそれより符号長の長い符号を持つ支配シンボルでな
    いシンボルがある場合、一時的にそのシンボルに前記固
    定符号語を割当てることを特徴とする請求項３、３４、
    ３５、３６または３７に記載の符号化復号装置。
  39. 【請求項３９】 前記符号割当手段における符号語作成
    処理は、各シンボルの出現確率が所定値を外れた場合に
    行われることを特徴とする請求項３、３４、３５、３
    ６、３７または３８に記載の符号化復号装置。
  40. 【請求項４０】 前記符号割当手段における符号語作成
    処理は、所定数のシンボルの符号化または復号が完了し
    た場合に行われることを特徴とする請求項３、３４、３
    ５、３６、３７、３８または３９に記載の符号化復号装
    置。
  41. 【請求項４１】 前記符号割当手段で生成された符号語
    の平均符号語長が前記固定符号語手段に保持された符号
    語の平均符号語長より長くなると予測される場合には前
    記固定符号語を新たな符号語とすることを特徴とする請
    求項３、３４、３５、３６、３７、３８、３９または４
    ０に記載の符号化復号装置。
  42. 【請求項４２】 前記度数集計手段で行われる統計値の
    初期化はそれまでの統計値に１以下の正の数を乗算して
    行うことを特徴とする請求項３、３４、３５、３６、３
    ７、３８、３９、４０または４１に記載の符号化復号装
    置。
  43. 【請求項４３】 前記固定符号語記憶手段に保持する符
    号語を既処理データの統計に基づいて新たに生成した符
    号語で置き換えることを特徴とする請求項３、３４、３
    ５、３６、３７、３８、３９、４０、４１または４２に
    記載の符号化復号装置。
  44. 【請求項４４】 前記符号割当手段における符号語作成
    処理は、予めシンボルの出現確率パターンとそれに対応
    する符号語を用意しておき、前記支配シンボルを前記出
    現確率パターンへ分類することによって簡易に前記符号
    語を得ることを特徴とする請求項３、３４、３５、３
    ６、３７、３８、３９、４０、４１、４２または４３に
    記載の符号化復号装置。
  45. 【請求項４５】 前記支配シンボルに対するパターン分
    類は、最頻シンボルの出現確率と閾値の大小比較によっ
    て行うことを特徴とする請求項４４に記載の符号化復号
    装置。
  46. 【請求項４６】 前記支配シンボルに対するパターン分
    類は、支配シンボルを頻度順に並べたとき複数の予め定
    められた順番に対応したシンボルの頻度による演算結果
    で決定することを特徴とする請求項４４に記載の符号化
    復号装置。
  47. 【請求項４７】 前記符号語記憶手段に初期値として設
    定される符号は予め定数が設定してあることを特徴とす
    る請求項３、３４、３５、３６、３７、３８、３９、４
    ０、４１、４２、４３、４４、４５または４６記載の符
    号化復号装置。
  48. 【請求項４８】 前記符号語記憶手段に初期値として設
    定される符号は前記固定符号語記憶手段に保持された符
    号を用いることを特徴とする請求項３、３４、３５、３
    ６、３７、３８、３９、４０、４１、４２、４３、４
    ４、４５または４６記載の符号化復号装置。
  49. 【請求項４９】 複数のシンボルを含むデータを入力
    し、前記入力されたデータに含まれる各シンボルの出現
    度数を計数し、前記計数された出現度数に応じて、前記
    シンボルのセットから支配シンボルを選択し、前記選択
    された支配シンボルに対して所定の手法で符号語を生成
    し、前記選択された支配シンボル以外のシンボルに対し
    て予測される出現確率に従って予め設計した符号語を生
    成し、前記生成された符号語を用いて前記入力データを
    符号化することを特徴とする符号化方法。
  50. 【請求項５０】 符号データを入力し、前記符号データ
    を復号して得られる各シンボルの出現度数を計数し、前
    記計数された出現度数に応じて、前記シンボルのセット
    から支配シンボルを選択し、前記選択された支配シンボ
    ルに対して所定の手法で符号語を生成し、前記選択され
    た支配シンボル以外のシンボルに対して予測される出現
    確率に従って予め設計した符号語を生成し、前記生成さ
    れた符号語を用いて前記符号データを復号することを特
    徴とする復号方法。
JP10121697A 1997-04-18 1997-04-18 符号化装置、復号装置および符号化復号装置ならびにそれらの方法 Expired - Fee Related JP3161697B2 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP10121697A JP3161697B2 (ja) 1997-04-18 1997-04-18 符号化装置、復号装置および符号化復号装置ならびにそれらの方法
US09/058,355 US6140945A (en) 1997-04-18 1998-04-10 Coding apparatus, decoding apparatus, coding-decoding apparatus and methods applied thereto

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP10121697A JP3161697B2 (ja) 1997-04-18 1997-04-18 符号化装置、復号装置および符号化復号装置ならびにそれらの方法

Publications (2)

Publication Number Publication Date
JPH10294670A true JPH10294670A (ja) 1998-11-04
JP3161697B2 JP3161697B2 (ja) 2001-04-25

Family

ID=14294722

Family Applications (1)

Application Number Title Priority Date Filing Date
JP10121697A Expired - Fee Related JP3161697B2 (ja) 1997-04-18 1997-04-18 符号化装置、復号装置および符号化復号装置ならびにそれらの方法

Country Status (2)

Country Link
US (1) US6140945A (ja)
JP (1) JP3161697B2 (ja)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001218207A (ja) * 2000-01-28 2001-08-10 Samsung Electronics Co Ltd 可変長コーディング方法及び装置
JP2009182808A (ja) * 2008-01-31 2009-08-13 Nec Corp 画像処理装置、画像処理方法および画像処理プログラム
JP2010136417A (ja) * 2004-12-28 2010-06-17 Casio Electronics Co Ltd データ圧縮装置、及びデータ復元装置
JP2012151840A (ja) * 2011-01-19 2012-08-09 Samsung Electronics Co Ltd データ圧縮装置、その動作方法、及びそれを含むデータ処理装置
JP2017528015A (ja) * 2014-06-09 2017-09-21 ティダル システムズ, インク.Tidal Systems, Inc. Ｖｌｓｉでの効率的なハフマン符号化を行う装置および方法

Families Citing this family (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7158684B2 (en) * 2002-04-25 2007-01-02 Texas Instruments Incoporated Entropy coding scheme for video coding
TWI318058B (en) * 2005-01-26 2009-12-01 Qisda Corp Message compression method, system and machine-readable storage medium
TWI378654B (en) * 2009-02-04 2012-12-01 Novatek Microelectronics Corp Adaptive canonical huffman decoder and method thereof and video decoder
CN101520771A (zh) * 2009-03-27 2009-09-02 广东国笔科技股份有限公司 一种对词库压缩编码及解码的方法和系统
CN110739974B (zh) * 2018-07-19 2023-11-10 嘉楠明芯(北京)科技有限公司 数据压缩方法及装置和计算机可读存储介质
US11296720B2 (en) * 2020-08-24 2022-04-05 Innogrit Technologies Co., Ltd. Data compression using reduced numbers of occurrences
CN115310409B (zh) * 2022-06-29 2024-07-12 杭州似然数据有限公司 一种数据编码的方法、系统、电子装置和存储介质

Family Cites Families (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS63232626A (ja) * 1987-03-20 1988-09-28 Fujitsu Ltd デ−タ圧縮復元方式
US5510785A (en) * 1993-03-19 1996-04-23 Sony Corporation Method of coding a digital signal, method of generating a coding table, coding apparatus and coding method
JP2638426B2 (ja) * 1993-06-16 1997-08-06 日本電気株式会社 可変長符号化装置
US5574449A (en) * 1995-02-24 1996-11-12 Intel Corporation Signal processing with hybrid variable-length and entropy encodidng
US5793896A (en) * 1995-03-23 1998-08-11 Intel Corporation Ordering corrector for variable length codes
US5970177A (en) * 1995-06-07 1999-10-19 America Online, Inc. Data compression using selective encoding

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001218207A (ja) * 2000-01-28 2001-08-10 Samsung Electronics Co Ltd 可変長コーディング方法及び装置
JP2010136417A (ja) * 2004-12-28 2010-06-17 Casio Electronics Co Ltd データ圧縮装置、及びデータ復元装置
JP2009182808A (ja) * 2008-01-31 2009-08-13 Nec Corp 画像処理装置、画像処理方法および画像処理プログラム
JP2012151840A (ja) * 2011-01-19 2012-08-09 Samsung Electronics Co Ltd データ圧縮装置、その動作方法、及びそれを含むデータ処理装置
JP2017528015A (ja) * 2014-06-09 2017-09-21 ティダル システムズ, インク.Tidal Systems, Inc. Ｖｌｓｉでの効率的なハフマン符号化を行う装置および方法
US10230393B2 (en) 2014-06-09 2019-03-12 Tidal Systems, Inc. VLSI efficient Huffman encoding apparatus and method

Also Published As

Publication number Publication date
US6140945A (en) 2000-10-31
JP3161697B2 (ja) 2001-04-25

Similar Documents

Publication Publication Date Title
US5045852A (en) Dynamic model selection during data compression
US6711295B2 (en) Encoding apparatus and method, and storage medium
JP5221047B2 (ja) 圧縮率の向上のために改善されたコンテキストモデル選択を使用するｃａｂａｃ符号化方法及び装置、並びにｃａｂａｃ復号化方法及び装置
US7233266B2 (en) Data compression/decompression device and data compression/decompression method
KR100340828B1 (ko) 적응 확률 추정방법 및 적응 부호화 방법과 적응 복호화 방법
JP3161697B2 (ja) 符号化装置、復号装置および符号化復号装置ならびにそれらの方法
EP1624580A1 (en) Context-based adaptive binary arithmetic decoding method and apparatus
US11265561B2 (en) Method and apparatus for range derivation in context adaptive binary arithmetic coding
KR100733795B1 (ko) 이진상태들의 산술적 인코딩 및 디코딩 방법 및 장치, 및이에 해당하는 컴퓨터 프로그램 및 컴퓨터 판독가능저장매체
US5650783A (en) Data coding/decoding device and method
JP3593884B2 (ja) 符号化装置および復号装置
US6252992B1 (en) Variable length coding
CN101095284A (zh) 用于有选择地压缩和解压缩的设备与数据方法以及压缩数据的数据格式
JP2002368625A (ja) 符号量予測装置、符号化選択装置および符号化装置ならびにその方法
US6622145B2 (en) Huffman coding for infinite symbol sets
Shamir Sequential universal lossless techniques for compression of patterns and their description length
CN119625087B (zh) 一种jbig算术编码和解码方法及系统
JP2009182809A (ja) 画像データ量子化装置、画像データ量子化方法および画像データ量子化プログラム
Rajwan Universal finite memory coding of binary sequences
JP2755091B2 (ja) 符号化方式及び符号化方法
Rakitskiy The efficient approach of calculating the predictors
Ramabadran et al. Efficient compression of medical images through arithmetic coding
US20070096956A1 (en) Static defined word compressor for embedded applications
JP2001086513A (ja) 符号化装置、復号装置、符号変換テーブル生成方法、および符号化方法ならびに復号方法
JPH1032496A (ja) 算術符号化装置

Legal Events

Date Code Title Description
FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20090223

Year of fee payment: 8

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100223

Year of fee payment: 9

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110223

Year of fee payment: 10

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120223

Year of fee payment: 11

LAPS Cancellation because of no payment of annual fees