JPH08116263A - データ処理装置及びデータ処理方法 - Google Patents

Abstract

(57)【要約】 【目的】 データ処理装置に関し、圧縮すべきデータの
次のデータの出現確率を予測して、データ処理速度の高
速化を図ること、及び、出現確率の高いデータを短い圧
縮データに割当てて、データ圧縮率の向上を図る。 【構成】 圧縮すべきデータの種類毎に該データの出現
度数を計数して出現度数テーブルを作成するデータ作成
手段１１と、前記データ作成手段からの出現度数テーブ
ルを参照しながら、圧縮すべきデータの次のデータの出
現予測をするデータ予測手段１２と、前記データ予測手
段のデータの出現予測に応じて出現確率の高いデータほ
ど短いビット長の圧縮データに変換し、出現確率の低い
データほど長いビット長の圧縮データに変換するデータ
変換手段１３とを備える。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、データ処理装置及びデ
ータ処理方法に関するものであり、更に詳しく言えば、
ハフマン符号化を利用して入力データを圧縮又は圧縮デ
ータを復号化をする装置及び方法の改善に関するもので
ある。近年、情報処理装置の高機能化及び多様化に伴
い、膨大な量のデータを格納する磁気ディスク装置等の
記憶装置を使用した装置及びそれらデータを通信回線を
使用して伝送する装置が利用されている。このような情
報処理分野では、高効率化により利用者のコスト削減を
図るべく、データ格納に際しては、記憶容量を実質的に
増やすために、及び、データ転送に際しては、送信時間
を短縮するために、データを圧縮する装置が必要とな
る。

【０００２】

【従来の技術】データ圧縮を情報理論面から最初に確立
したのは、米国ベル研究所のＣlaudeＳhannon氏が1948
年に発表した「エントロピー」という概念であるといわ
れている。ほぼ同じ時期に米国ＭＩＴのＲ．Ｍ．Ｆano
氏も同様な理論を考えたことから、Ｓhannon−Ｆano 符
号化と一般に呼ばれることが多い。これは、出現確率が
高い文字を少ないビット数に割り当てることにより、デ
ータを圧縮するものである。その後、この可変長符号を
生成する方式として、1952年にＨuffman氏が発表した
‘Ａ Ｍethod for the Ｃonstruction of Ｍinimum
Ｒedundancy Ｃode'（最少冗長符号の構成方法）の論文
があり、いわゆる、「ハフマン符号化」が主流を占める
ようになった。これらはいずれも、文字の出現頻度の差
を利用して、データ圧縮をするというものである。

【０００３】これに対して、辞書という概念を持ち、文
字列の繰り返しに関してデータ圧縮をするという全く別
の方法が考えられた。これは通称、Ｌempel −Ｚiv符号
化のスライド辞書法又はＬＺ７７法と言われている。こ
の辞書ベースによりデータ圧縮をする方法は、Ｌempel
Ａbraham氏とＺivＪacob氏が1977年にＩＥＥＥ Ｔrans
action on Ｉnformation Ｔheory に発表した論文‘Ａ
Ｕniversal Ａlgorithm for Ｓequential Ｄata Ｃ
ompression’に見られる。つまり、従来の圧縮アルゴリ
ズムの基本原理を大別すると、文字の出現頻度に対し
て、データ圧縮をするもの（ハフマン符号化等）と、辞
書という概念を持ち、文字列の繰り返しに対してデータ
圧縮をするもの（Ｌempel-Ｚiv符号化）の２種類があ
る。

【０００４】図12は、従来例に係る説明図である。図12
（Ａ）は、日本国特許庁が発行する公開特許公報，特開
平４−１２３６１９号に見られるようなデータ圧縮装置
（以下第１の装置という）の構成図であり、図12（Ｂ）
は、同様に、特開平４−２８０５１７号に見られるよう
なデータ圧縮装置（以下第２の装置という）の構成図を
それぞれ示している。

【０００５】Ｌempel −Ｚiv符号化を改良した第１の装
置は、図12（Ａ）に示すように、入力データの出現頻度
を計測する計測手段１と、出現頻度に応じて入力データ
ＤINを変換する変換手段２と、辞書検索リストに従っ
て、変換データＤＴに基づき候補データを順次検索し、
候補データの参照番号を符号データＤOUT として出力す
る符号化手段３から成る。

【０００６】第１の装置の動作を説明する。まず、計測
手段１により入力データの出現頻度が計測されると、計
測手段１からの計測結果に基づき、変換手段２によって
出現頻度が高いほど小さな値のコードに、また、出現頻
度が低いほど大きな値のコードに、入力データＤINがそ
れぞれ変換される。ここで変換された変換データＤＴは
符号化手段３により、辞書検索リストに従って、入力デ
ータに一致する候補データが順次検索され、最後に一致
した候補データの参照番号が一連の入力データ列の符号
データＤOUT として出力される。これにより、入力デー
タＤINが符号化される。

【０００７】また、算術符号化によりデータを圧縮する
第２の装置は、図12（Ｂ）に示すように、検索・登録部
４Ａ及び辞書並べ替え部４Ｂを有する自己組織化符号化
部（以下単にＳＯＲ符号化部という）４と、辞書データ
を格納する辞書５と、各文字列の出現頻度及び累積頻度
等を計数するカウンタ６と、ＳＯＲ符号を算術符号化し
て多値符号データを出力する算術符号部７から成る。

【０００８】第２の装置の動作を説明する。まず、圧縮
すべき文字列が辞書５に登録されているか否かを識別す
べく、ＳＯＲ符号化部４の検索・登録部４Ａにより辞書
５が参照される。ここで、辞書並べ替え部４Ｂは自己組
織化の規則に従って、辞書５を更新し、出現頻度の高い
文字列ほど登録番号が小さくなるように文字列の並び替
えを行う。

【０００９】辞書５に同じ文字列が有ると、検索・登録
部４Ａは、辞書５の登録番号をＳＯＲ符号として算術符
号化部７に出力する。未登録の場合には文字列が登録さ
れると共に、この文字列がＳＯＲ符号として算術符号化
部７に出力される。算術符号部７では、ＳＯＲ符号を算
術符号化して多値符号データを出力する。この際に、算
術符号部７は、カウンタ６からの各文字列の出現頻度及
び累積頻度等のカウント値に基づいて、符号ビット値及
び上下ビットの数値を求め、これらを多値符号データと
して出力する。これにより、入力文字列を符号化した多
値符号データが出力される。

【００１０】

【発明が解決しようとする課題】ところで、従来例の第
１の装置によれば、入力データに一致する候補データを
辞書検索リストに従って、順次検索し、最後に一致した
候補データの参照番号を一連の入力データ列の符号デー
タＤOUT として出力しているため、ある程度，文字列の
順番が予想できる入力データ列であっても、連結リスト
構造を備えた辞書を検索リストに従って順次検索しなく
てはならない。

【００１１】例えば、英文の例で「ａｎｄ」という文脈
が頻繁に出現する入力データを仮定した場合に、「ａ」
の次に、「ｎ」が続く確率は高くなる。また、ローマ字
「ｑ」という文字の次に出現する文字が「ｕ」となる確
率が高い。このような文字列や文字に対しても、入力デ
ータに一致する候補データを検索しなくてはならず、辞
書検索時間やデータ転送時間に無駄を生じ、データ処理
時間の高速化の妨げとなるという問題がある。

【００１２】また、従来例の第２の装置によれば、辞書
５に同じ文字列が有ると、この登録番号がＳＯＲ符号と
して算術符号化部７に出力され、当該算術符号部７で
は、ＳＯＲ符号が算術符号化されて多値符号データが出
力されるため、文字列の順番が予想できる入力データ列
であっても、同じ文字列が有るか否かを辞書５を検索
し、その登録番号をＳＯＲ符号として算術符号部７に転
送しなくてはならない。

【００１３】これにより、第１の装置と同様にデータ処
理時間の高速化の妨げとなるという問題がある。なお、
日本国特許庁が発行する公開特許公報，特開平３−６８
２１９号に見られるようなデータ圧縮装置は、ハフマン
符号化を利用した入力データの出現頻度に対して圧縮を
するものである。これは、１文字のみの出現確率を計算
し、それを可変長符号に割当てるものである。

【００１４】つまり、この装置は１文字のみの出現頻度
のバラツキを利用しているため、ある程度，文字列の順
番が予想できる入力データ列であっても、１文字のみの
出現確率を計算しなくてはならず、一様に出現するデー
タ列の圧縮率がそれほど高くならないという問題があ
る。本発明は、かかる従来例の問題点に鑑み創作された
ものであり、ある程度，文字列の順番が予想できる場合
には、圧縮すべきデータの次のデータの出現確率を予測
して、データ処理速度の高速化を図ること、及び、出現
確率の高いデータを短い圧縮データに変換して、データ
圧縮率の向上を図ることが可能となるデータ処理装置及
びデータ処理方法の提供を目的とする。

【００１５】

【課題を解決するための手段】図１は、本発明に係るデ
ータ処理装置の原理図を示している。本発明の第１のデ
ータ処理装置は、図１に示すように、圧縮すべきデータ
の種類毎に該データの出現度数を計数して出現度数テー
ブルを作成するデータ作成手段１１と、前記データ作成
手段からの出現度数テーブルを参照しながら、圧縮すべ
きデータの次のデータの出現予測をするデータ予測手段
１２と、前記データ予測手段のデータの出現予測に応じ
て出現確率の高いデータほど短いビット長の圧縮データ
に変換し、出現確率の低いデータほど長いビット長の圧
縮データに変換するデータ変換手段１３とを備えること
を特徴とする。

【００１６】本発明の第２のデータ処理装置は、前記デ
ータ作成手段１１が、圧縮すべき１単位のデータを入力
する毎に出現度数テーブルを更新することを特徴とす
る。本発明の第３のデータ処理装置は、前記データ変換
手段１３によって変換された圧縮データの長さを調整す
るレベル調整手段１４が設けられることを特徴とする。

【００１７】本発明の第１〜３のデータ処理装置におい
て、前記データ作成手段１１は、圧縮すべき全てのデー
タ又は１単位のデータを取り込んで出現度数テーブルを
作成することを特徴とする。本発明の第１〜３のデータ
処理装置において、前記データ変換手段１３は、出現度
数テーブルでデータを出現度数の高い順に並べ換え、該
出現度数の高いデータから出現度数の低いデータに至る
位置に対して、該データを出現度数の高いデータほど短
い位置情報を割当て、かつ、出現度数の低いデータほど
長い位置情報を割当てた符号テーブルを参照することを
特徴とする。

【００１８】本発明の第１のデータ処理方法は、図２の
処理フローチャートに示すように、ステップＰ１で、予
め、圧縮すべきデータの種類毎に該データの出現度数を
計数して出現度数テーブルを作成し、次に、ステップＰ
２で前記作成された出現度数テーブルを参照しながら、
圧縮すべきデータの次のデータの出現予測をし、その
語、ステップＰ３で前記データの出現予測に応じて出現
確率の高いデータほど短いビット長の圧縮データに変換
し、かつ、出現確率の低いデータほど長いビット長の圧
縮データに変換することを特徴とする。

【００１９】本発明の第１のデータ処理方法において、
前記圧縮データの変換は、出現度数テーブルのデータを
出現度数の高い順に並べ換え、該出現度数の高いデータ
から出現度数の低いデータに至る位置に対して、該デー
タを出現度数の高いデータほど短い位置情報を割当て、
かつ、出現度数の低いデータほど長い位置情報を割当て
た符号テーブルを参照することを特徴とする。

【００２０】本発明の第２のデータ処理方法は、前記出
現度数テーブル及び符号テーブルを、圧縮すべき１単位
のデータが入力される毎に更新することを特徴とする。
本発明の第３のデータ処理方法は、前記圧縮すべきデー
タを圧縮データに変換した後に、図２の処理フローチャ
ートのステップＰ４で、圧縮データのビット長を調整す
ることを特徴とする。

【００２１】本発明の第１〜第３のデータ処理方法にお
いて、前記出現度数テーブルは、圧縮すべき全てのデー
タ又は１単位のデータに応じて作成することを特徴とす
る。本発明の第１〜第３のデータ処理方法において、前
記データの次のデータの出現予測は、出現度数テーブル
に書き込まれた各々の出現度数のデータと、圧縮すべき
データの次のデータとを比較することを特徴とする。

【００２２】本発明の第１〜第３のデータ処理方法にお
いて、前記圧縮データは、出現度数の高いデータから出
現度数の低いデータに至る位置を表示する位置情報及び
前記位置情報を識別する識別子から構成することを特徴
とし、上記目的を達成する。

【００２３】

【作用】次に、図１を参照しながら本発明の第１のデー
タ処理装置の動作を説明をする。図１において、まず、
圧縮すべき全てのデータＤIN又は１単位のデータＤINの
出現度数が、データ作成手段１１によりデータ種類毎に
計測されて出現度数テーブルが作成される。

【００２４】データ作成手段１１で作成された出現度数
テーブルはデータ予測手段１２により参照され、圧縮す
べきデータＤINの次のデータがデータ予測手段１２によ
り出現予測される。具体的な出現予測については、出現
度数テーブルに書き込まれた各々の出現度数のテータ
と、圧縮すべきデータＤINの次のデータとが比較され
る。

【００２５】ここで、データ予測手段のデータの出現予
測に応じて、データ変換手段は出現確率の高いデータほ
ど短いビット長の圧縮データに変換し、出現確率の低い
データほど長いビット長の圧縮データに変換する。例え
ば、データ変換手段１３は、出現度数テーブルでデータ
を出現度数の高い順に並べ換え、該出現度数の高いデー
タから出現度数の低いデータに至る位置に対して、出現
度数の高いデータほど短い位置情報を割当て、出現度数
の低いデータほど長い位置情報を割当てた符号テーブル
を参照する。

【００２６】このような符号テーブルを参照すること
で、ある程度，文字列の順番が予想できる入力データ列
の場合に、１文字のみの出現確率を計算するハフマン符
号化方法に比べて、一様に出現するデータ列の圧縮率を
向上させることが可能となる。これにより、圧縮すべき
データの前後の対象文字や文字列の出現を予測しなが
ら、データ圧縮をすることが可能となり、辞書検索時間
やデータ転送時間の削減することができ、データ処理動
作が高速化する。

【００２７】本発明の第２のデータ処理装置によれば、
圧縮すべき１単位のデータが入力される毎に出現度数テ
ーブルがデータ作成手段１１により更新されるため、デ
ータ作成手段１１での出現度数テーブルの更新に伴って
データ変換手段１３では短時間に圧縮データを書き換え
ることができ、タイナミック（動的）に符号テーブルを
再構成することができる（第２のデータ処理方法）。

【００２８】また、出現度数テーブルの更新によって圧
縮データの全ての並び変えを行うことなく、一部の位置
情報及び識別子の入替えのみで符号テーブルを更新する
ことでき、当該符号テーブルを圧縮データに含める必要
が無くなり、データ圧縮率が向上する。これにより、メ
モリ容量が限られている対象機器にデータ圧縮機能を組
み込む場合に、１バイト又は１文字単位の出現頻度をダ
イナミックに符号化することができる。

【００２９】本発明の第３のデータ処理装置によれば、
入力データを圧縮データに変換した後に、レベル調整手
段１４により、圧縮データの長さが調整されるため、入
力データの種別に応じて、圧縮データの長さをダイナミ
ックにレベル調整して圧縮データを再構成するオフセッ
ト符号化を実行することができる（第３のデータ処理方
法）。

【００３０】すなわち、入力データの種類によっては、
圧縮すべきデータに偏りを生じ、出現確率が平均化され
る場合や、データの出現度数が十分に収集されていない
場合等には、次のデータの予測が困難となる場合があ
る。しかし、オフセット符号化を実行することにより、
度数分布の傾向が明確な場合には、入力データをより短
いビット長の圧縮データに変換し、出現度数分布に偏り
が生じている場合には、レベルを上げることにより、短
いビット長の圧縮データに変換することができる。

【００３１】これにより、データ圧縮率が向上する。な
お、各データ別の出現確率が事前に把握されている場合
には、出現度数の高いデータをメモリの上位に初期設定
をして置くことで、更に、短い位置情報に変換される確
率が高まる。本発明の第１のデータ処理方法によれば、
図２の処理フローチャートに示すように、ステップＰ１
で、予め、圧縮すべきデータの種類毎に該データの出現
度数を計数して出現度数テーブルを作成しているため、
圧縮すべきデータの前後の対象文字や文字列の接続状態
を把握することができる。例えば、英文の例で「ａｎ
ｄ」という文脈が頻繁に出現する入力データを仮定した
場合に、「ａ」の次に、「ｎ」が続く場合が多くなり、
また、ローマ字「ｑ」という文字の次に出現する文字が
「ｕ」となる場合が多いが、このような対象文字や文字
列の前後の接続状態が把握できる。

【００３２】また、ステップＰ２では出現度数テーブル
を参照しながら、圧縮すべきデータＤINの次のデータの
出現予測をしているため、先の例で「ａ」の次に出現す
る「ｎ」やローマ字「ｑ」の次に出現する「ｕ」の文字
を予測することができる。さらに、ステップＰ３では、
符号テーブルを参照しながら、入力データＤINの出現予
測に応じて出現確率の高い入力データＤINほど短いビッ
ト長の圧縮データに変換され、その出現確率の低い入力
データＤINほど長いビット長の圧縮データに変換されて
いるため、符号テーブルから直接，位置情報及び識別子
から構成される圧縮データＤOUT を出力することができ
る。

【００３３】これにより、文字列や文字の出現予測をす
ることで、辞書の検索といった概念が無くなる。特に、
文字列の順番が予想できるような入力データ列の場合に
は、辞書検索時間やデータ転送時間が低減し、データ処
理動作が高速化する。

【００３４】

【実施例】次に、図を参照しながら本発明の各実施例に
ついて説明をする。図３〜11は本発明の実施例に係るデ
ータ処理装置及びデータ処理方法を説明する図である。 （１）第１の実施例の説明 図３は、本発明の各実施例に係るデータ圧縮及び復元装
置の構成図であり、図４は、本発明の第１の実施例に係
るデータの圧縮及び復元フローチャートである。図５
は、データ圧縮時の符号変換エディタの機能説明図であ
り、図６は、各実施例に係る圧縮データのフォーマット
及び符号木の説明図をそれぞれ示している。

【００３５】例えば、本発明の第１〜第３の装置を組み
合わせたデータ圧縮又は復元装置は、図３に示すよう
に、出現度数作成エディタ２１，テータ比較エディタ２
２，符号変換エディタ２３，レベル調整エディタ２４，
メモリ２５，ＥＰＲＯＭ２６，ディスプレイ２７，キー
ボード２８，中央処理装置（以下ＣＰＵという）２９，
入力データファイル３０及び圧縮データファイル３１か
ら成る。

【００３６】出現度数作成エディタ２１はデータ作成手
段１１の一例であり、圧縮すべきデータＤINを入力して
該データＤINと出現度数とを対比させた出現度数テーブ
ルを作成する。出現度数作成エディタ２１は、圧縮すべ
き全てのデータＤIN又は１単位のデータを取り込んで出
現度数テーブルを作成する。出現度数はエディタ２１に
よって加算しても積算しても良い。

【００３７】例えば、エディタ２１は表１に示すような
１６進法により表される２５６個のデータ「００」〜
「ＦＦ」及び１０進法により表される出現回数を対比さ
せた出現度数テーブルを作成する。

【００３８】

【表１】

【００３９】表１の例では、データ「００」に対する出
現度数が７５回，データ「０１」に対する出現度数が５
０回，データ「０２」に対する出現度数が100 回，デー
タ「ＦＦ」に対する出現度数が５０回となっている。ま
た、出現度数作成エディタ２１は、圧縮すべき１単位の
データが入力される毎に出現度数テーブルを更新する
（本発明の第２の装置）。

【００４０】テータ比較エディタ２２はデータ予測手段
１２の一例であり、出現度数作成エディタ２１からの出
現度数テーブルを参照しながら、圧縮すべきデータＤIN
の次のデータの出現予測をする。例えば、データ比較エ
ディタ２２は、出現度数テーブルに書き込まれた各々の
出現度数のテータと、圧縮すべきデータＤINの次のデー
タとを比較する。この比較結果から、次のデータの出現
予測をする。

【００４１】符号変換エディタ２３はデータ変換手段１
３の一例であり、データ比較エディタ２２からの入力デ
ータＤINの出現予測に応じて、該データＤINを位置情報
に変換するものである。例えば、エディタ２３は出現度
数の高いデータほど短い位置情報に変換し、かつ、出現
度数の低いデータほど長い位置情報に変換する。先の表
１の例を具体的な位置情報で示すと、表２に示すような
符号テーブルが得られる。

【００４２】

【表２】

【００４３】表２の符号テーブルの例では、出現度数の
高いデータ「０２」，「ＦＤ」に対しては、「００」，
「０１」の位置情報に変換され、次に出現度数の高いデ
ータ「００」，「０３」に対しては、「１００」，「１
０１」の位置情報に変換され、次に出現度数の高いデー
タ「０１」，「０４」，「ＦＥ」，「ＦＦ」に対して
は、「１１００」、「１１０１」，「１１１０」，「１
１１１」の位置情報にそれぞれ変換される。なお、符号
テーブルの作成機能をエディタ２１に持たせても良い。

【００４４】本発明の各実施例における圧縮データのフ
ォーマットは、図６（Ａ）に示すようになる。図６
（Ａ）において、圧縮データＤOUT は識別子及び位置情
報から構成する。具体的な例を表３に示している。

【００４５】

【表３】

【００４６】表３では、例えば、２５６個のデータサン
プルに対して、位置情報を識別するために４つの識別子
を割当てている。具体的には、先頭位置又は第１番目の
位置情報を識別する識別子として「００」を割当てる。
第２番目〜第５番目の位置情報を識別する識別子として
「０１０」を割当てる。同様に、第８番目〜第１３番目
の位置情報を識別する識別子として「０１１」を割当
て、第１４番目〜第２５５番目の位置情報を識別する識
別子として「１」をそれぞれ割当てる。

【００４７】また、位置情報のビット幅は識別子「０
０」に対して１ビットを割当て、位置情報の内容は
「０」又は「１」を割り当てる。識別子「０１０」に対
しては２ビットを割当て、その内容は「００」，「０
１」，「１０」，「１１」となる。識別子「０１１」に
対しては３ビットを割当て、その内容は「０００」，
「００１」，「０１０」，「１００」，「０１１」，
「１０１」，「１１０」，「１１１」となる。識別子
「１」に対しては８ビットを割当て、その内容は「００
００００００」〜「１１１１１１１１」となる。なお、
符号変換エディタ２３の機能については図５（Ａ），
（Ｂ）において説明をする。

【００４８】レベル調整エディタ２４はレベル調整手段
１４の一例であり、符号変換エディタ２３によって変換
された圧縮データの長さを調整するものである（本発明
の第３の装置）。当該エディタ２４の機能については図
10，図11において詳述する。メモリ２５は圧縮時には、
入力データＤINを一時記憶するものである。例えば、メ
モリ２５には随時書込み／読出し可能なメモリを用い
る。メモリ２５は復元時には、復元すべき圧縮データを
一時記憶する。

【００４９】ＥＰＲＯＭ２６は、各実施例で使用する制
御アルゴリズムを格納するプログラム可能な読出し専用
メモリである。例えば、第１の実施例では図４（Ａ）に
示すようなデータ圧縮アルゴリズムや図４（Ｂ）に示す
ようなデータ復元アルゴリズムがＥＰＲＯＭ２６に格納
される。第２の実施例では、図７（Ａ）に示すようなデ
ータ圧縮アルゴリズム（メインルーチン）や、図７
（Ｂ）に示すようなデータ復元アルゴリズムが格納され
る。また、図７（Ａ）のメインルーチンに対して図８に
示すような出現度数テーブルの更新アルゴリズム（サブ
ルーチン）がＥＰＲＯＭ２６に格納される。

【００５０】第３の実施例では、図10（Ａ）に示すよう
なデータ圧縮アルゴリズムや図10（Ｂ）に示すようなデ
ータ復元アルゴリズムが格納される。図10（Ａ）のメイ
ンルーチンに対して図11に示すような位置情報のレベル
調整アルゴリズム（サブルーチン）がＥＰＲＯＭ２６に
格納される。この制御アルゴリズムの具体的な内容につ
いては各実施例において説明をする。

【００５１】ディスプレイ２７はキーボード２８やＣＰ
Ｕ２９の入出力を補助するツールである。キーボード２
８は各エディタ２１〜２４の初期設定や起動命令等を制
御文にして入力するツールである。ＣＰＵ２９は、各エ
ディタ２１〜２４，メモリ２５，ＥＰＲＯＭ２６，ディ
スプレイ２７，キーボード２８，入力データファイル３
０及び圧縮データファイル３１の入出力を制御する。

【００５２】入力データファイル３０は圧縮時又は復元
時のデータを格納するものである。圧縮データファイル
３１は、圧縮時又は復元時の圧縮データを格納するメモ
リであり、ファイル３０と同様なメモリ装置を用いる。
これらにより、データ圧縮及び復元装置が構成され、圧
縮すべきデータを符号化し、該符号化された圧縮データ
を復号化することができる。

【００５３】次に、本発明の第１の実施例に係るデータ
圧縮方法について、図４（Ａ）の処理フローチャートを
参照しながら、当該装置の動作を説明する。図４（Ａ）
は、本発明の第１の実施例に係るデータの圧縮フローチ
ャートであり、図３に示したＥＰＲＯＭ２６に格納され
た制御アルゴリズムを成す。例えば、入力データＤINの
次のデータの出現予測をしながら、データを符号化して
圧縮データＤOUT を出力する場合、図４（Ａ）のフロー
チャートにおいて、まず、ステップＰ１で、入力データ
列をファイル３０から全て読み込んで出現度数テーブル
を作成する。出現度数テーブルは、出現度数作成エディ
タ２１によって、入力データＤINの種類毎に該データを
計数することにより作成する。

【００５４】具体的には、図５（Ａ）に示すような１６
進法により表される２５６個のデータ「００」〜「Ｆ
Ｆ」及び１０進法により表される出現回数を一覧表にま
とめた出現度数テーブルがエディタ２１により作成され
る。本実施例では出現度数テーブルＴ１に関し、データ
「００」に対して出現度数が３回、データ「０１」に対
して出現度数が０回、データ「０２」に対して出現度数
が２３回、データ「０３」に対して出現度数が０回、デ
ータ「０４」に対して出現度数が１０回、データ「Ｆ
Ｅ」に対して出現度数が５回、データ「ＦＦ」に対して
出現度数が１回となっている。

【００５５】このような例では、英文の場合、「ａｎ
ｄ」という文脈が頻繁に出現する入力データを仮定した
場合に、１６進法の６１により表されるデータ「ａ」の
次には１６進法の６Ｅにより表されるデータ「ｎ」が続
く場合が多くなり、また、ローマ字「ｑ」という文字の
次に出現する文字が「ｕ」となる場合が多く出現する。
このような統計情報を取得すると、対象文字や文字列の
前後の接続状態が把握できる。なお、出現度数テーブル
は、入力データを全て読み込むことなく、圧縮すべき１
単位の入力データ毎に作成しても良い。

【００５６】次いで、ステップＰ２で出現度数テーブル
から符号テーブルを作成する。ここで、図５（Ａ）にお
いて、符号変換エディタ２３は、出現度数テーブルＴ１
のデータを出現度数の高い順に並べ換える。この結果、
交換後のテーブルＴ２の先頭位置には、データ「０２」
が書き込まれ、以下順に、データ「０４」，「ＦＥ」，
「００」，「ＦＦ」…「０１」，「０３」が並ぶ。

【００５７】次に、ステップＰ３で圧縮すべきデータ列
をファイル３０から１単位のデータを読込んで符号化を
する。この際に、出現度数作成エディタ２１からの出現
度数テーブルを参照しながら、圧縮すべきデータＤINの
次のデータを出現予測をする。例えば、データ比較エデ
ィタ２２により、出現度数テーブルに書き込まれた各々
の出現度数のテータと、圧縮すべきデータＤINの次のデ
ータとが比較される。これにより、先の例で「ａ」の次
に出現する「ｎ」やローマ字「ｑ」の次に出現する
「ｕ」の文字を予測することができる。

【００５８】さらに、エディタ２３は図５（Ｂ）に示す
ように、該出現度数の高いデータ「０２」から出現度数
の低いデータ「０３」に至る相対位置０〜１５…に対し
て、データを位置情報に変換する。これを先に説明をし
た図５（Ａ）の交換後のテーブルＴ２に関し、具体的に
識別子を導入してデータ変換すると、図５（Ｂ）に示す
ようになる。相対位置「０」，「１」に対しては、デー
タが識別子「００」及び位置情報「０」，「１」にそれ
ぞれ変換される。

【００５９】相対位置「２」〜「５」に対しては、デー
タが識別子「０１０」及び位置情報「００」，「０
１」，「１０」，「１１」にそれぞれ変換される。相対
位置「６」〜「１３」に対しては、データが識別子「０
１１」及び位置情報「０００」，「００１」，「０１
０」，「１００」，「０１１」，「１０１」，「１１
０」，「１１１」にそれぞれ変換される。

【００６０】その後、ステップＰ４では、入力データＤ
INを全て圧縮したか否かを判断する。ここで、入力デー
タＤINを全て圧縮した場合（ＹES）には、制御アルゴリ
ズムを終了する。全てのデータを圧縮していない場合
（ＮＯ）には、ステップＰ３に戻って符号化処理を継続
する。これにより、入力データＤINの次のデータの出現
予測をしながら、データを符号化し、これら圧縮データ
ＤOUT をファイル３１に格納することができる。

【００６１】次に、本発明の第１の実施例に係る圧縮デ
ータの復元処理について説明をする。図４（Ｂ）の復号
フローチャートにおいて、まず、ステップＰ１で圧縮デ
ータをファイル３１から読出し識別子及び位置情報から
符号テーブルを作成する。符号テーブルについては、図
５において説明したものが再現される。次に、ステップ
Ｐ２で再度、圧縮データをファイル３１から読出して符
号テーブルを参照しながら、圧縮データを復号化する。
復号化は、一般的に用いられる図６（Ｂ）に示すような
符号木の構成によって実行する。

【００６２】次いで、ステップＰ３で圧縮データを全て
復元したか否かを判断する。この際に、圧縮データを全
て復元した場合（ＹES）には、制御アルゴリズムを終了
し、圧縮データを全て復元していない場合（ＮＯ）に
は、ステップＰ２に戻って、圧縮データの復号化処理を
継続する。これにより、圧縮データが復号化され、この
原データがファイル３０に格納される。

【００６３】このようにして、本発明の各実施例に係る
データ処理装置によれば、図３に示すように、出現度数
作成エディタ２１，テータ比較エディタ２２，符号変換
エディタ２３及びレベル調整エディタ２４等を備えるた
め、出現度数作成エディタ２１により出現度数テーブル
が作成されると、テータ比較エディタ２２により、圧縮
すべきデータの次に出現する文字又は文字列を予測する
ことができ、この出現予測されたデータを符号変換エデ
ィタ２３により、その出現確率が高いデータほど短い位
置情報に変換し、出現確率の低いデータほど長い位置情
報に変換することができる。

【００６４】これにより、入力データの出現度数が高い
ものテーブル領域の上位に持ち、最上位からの位置を符
号化（仮称：オフセット符号化）をすることができる。
特に、文字列の順番がテータ比較エディタ２２によって
予想できる入力データ列の場合には、従来例のような符
号木によって、１文字のみの出現確率を計算するハフマ
ン符号化方法に比べて、一様に出現するデータ列の圧縮
率が向上し、データ処理速度が高速化する。

【００６５】また、本発明の装置によれば、符号変換エ
ディタ２３によって変換された圧縮データの長さがレベ
ル調整エディタ２４により調整されるため、入力データ
の種別に応じて、圧縮データの長さをダイナミックにレ
ベル調整した圧縮データを再構成することができる。さ
らに、本発明の第１の実施例に係るデータ圧縮方法によ
れば、図４（Ａ）の処理フローチャートに示すように、
ステップＰ１で、予め、圧縮すべきデータの種類毎に該
データの出現度数を計数して出現度数テーブルを作成し
ているため、順次、読み込まれる入力データＤINの前後
の対象文字の接続状態を把握することができる。

【００６６】英文の例で説明したように「ａｎｄ」とい
う文脈が頻繁に出現する入力データを仮定した場合に、
「ａ」の次に、「ｎ」が続く場合が多くなることや、ロ
ーマ字「ｑ」という文字の次に出現する文字が「ｕ」と
なる場合等の規則性を確率的に把握できる。また、ステ
ップＰ３では、出現度数テーブルを参照しながら、圧縮
すべきデータＤINの次のデータの出現予測をしているた
め、先の例で「ａ」の次に出現する「ｎ」やローマ字
「ｑ」の次に出現する「ｕ」の文字を予測することがで
きる。

【００６７】さらに、ステップＰ３では、符号テーブル
を参照しながら、入力データＤINの出現予測に応じて出
現確率の高いデータほど短い位置情報に変換し、その出
現確率の低いデータほど長い位置情報に変換しているた
め、符号テーブルから直接，位置情報及び識別子を有す
る圧縮データＤOUT を出力することができる。これによ
り、文字列や文字の出現予測をすることで、辞書の検索
といった概念が無くなる。特に、文字列の順番が予想で
きるような入力データ列の場合には、従来例の第２の装
置のように同じ文字列が有るか否か等の辞書検索が不要
となり、辞書検索時間やデータ転送時間が削減化する。

【００６８】なお、符号化及び復号化の処理時間を短く
するための更なる工夫として、表３及び図５（Ｂ）の識
別子が「１」のときに、位置情報の代わりに入力データ
ＤINを８ビットのまま符号化しても良い。これにより、
〔入力データ／圧縮データ〕×100 ％で表されるデータ
圧縮率が向上する。また、圧縮率を高めるためには、入
力データＤINの次の１文字だけではなく、複数の文字列
のつながりを判断すると良い。この場合、圧縮率が高ま
るが、データ処理速度やメモリ容量等に制約が生じる。

【００６９】（２）第２の実施例の説明 図７（Ａ）は、本発明の第２の実施例に係るデータの圧
縮フローチャートであり、図７（Ｂ）は、その復元フロ
ーチャートである。図８は、出現度数テーブルの更新フ
ローチャートであり、図９（Ａ）〜（Ｃ）は、その更新
時のデータ交換の状態図をそれぞれ示している。各フロ
ーチャートは制御アルゴリズムとして図３に示したＥＰ
ＲＯＭ２６に格納される。

【００７０】第２の実施例では第１の実施例と異なり、
出現度数テーブル及び符号テーブルを、圧縮すべき１単
位のデータが入力される毎にダイナミック（動的）に更
新するものである。図９（Ａ）に示すような出現度数テ
ーブルのデータ配列Ａを更新する場合、図７（Ａ）のフ
ローチャートにおいて、まず、ステップＰ１で、出現度
数テーブル及び符号テーブルを初期化する。図９（Ａ）
において、更新前の出現度数テーブルのデータ配列Ａ
は、例えば、「００」，「０１」，「０２」，「０３」
…のようになる。

【００７１】次に、ステップＰ２で１単位の入力データ
列ＤINをファイル３０から読み込んで、それを符号化す
る。符号化は第１の実施例で説明したように、１バイト
又は１文字単位に符号変換エディタ２３により実行され
る。次いで、ステップＰ３で出現度数テーブルを更新す
る。具体的には、出現度数作成エディタ２１により１単
位のデータが入力される毎に、出現度数テーブルが更新
される。出現度数テーブルの更新については、図８のサ
ブルーチンに移行して、ステップＰ31で、順次入力され
たコードに対応して、データ配列Ｂの出現度数を更新す
る。この例では、図９（Ａ）に示すように、順次，出現
度数テーブルに入力されてくるデータ（コード）「０
３」，「００」，「０１」，「０２」に対して、配列Ｂ
の「０３」にポインタが指示された場合を示している。

【００７２】次に、ステップＰ32でデータ配列Ｂの現在
の出現度数と上位にエントリーされた出現度数とを比較
する。これは、出現度数の高いコードを上位に移動する
ためである。その後、ステップＰ33で両出現度数を比較
した結果、現在の出現度数が大きい場合もしくは上位の
出現度数と等しい場合（ＹES）には、ステップＰ34に移
行する。また、比較結果、現在の出現度数が小さい場合
（ＮＯ）には、更新を行わずに、メインルーチンに復帰
する。

【００７３】現在の出現度数が大きいと判断された場合
（ＹES）には、ステップＰ34でデータ配列Ｂの上位のエ
ントリーの出現度数を検索する。この検索は、データ配
列Ｂの上位の出現度数と比較して、現在の出現度数が小
さくなるまで行う。次に、ステップＰ35でデータ配列Ｂ
で検索したエントリー内容と交換する。図９（Ｂ）では
コード「０１」と「０２」とが交換されることにより、
図９（Ａ）に示した更新前のデータ配列Ａが図９（Ｃ）
に示すように、「０２」，「０３」が入れ替わり、デー
タ配列Ａが更新される。これと共に、符号変換エディタ
２３は、データ配列Ａの更新に伴って位置情報を書換え
る。

【００７４】その後、ステップＰ36でデータ配列Ａの対
応するポインタを移動し、メインルーチンに復帰する。
そして、メインルーチンのステップＰ４では圧縮データ
を全て符号化したか否かを判断する。この際に、入力デ
ータＤINを全て符号化した場合（ＹES）には、制御アル
ゴリズムを終了し、データＤINを全て符号化していない
場合（ＮＯ）には、ステップＰ２に戻って、データＤIN
の符号化処理を継続する。

【００７５】これにより、符号テーブルをダイナミック
に更新しながら、入力データＤINを符号化し、この圧縮
データをファイル３１に格納することができる。次に、
本発明の第２の実施例に係る圧縮データの復元処理につ
いて説明をする。図７（Ｂ）は、本発明の第２の実施例
に係る圧縮データの復元フローチャートである。復元フ
ローチャートは制御アルゴリズムとして図３に示したＥ
ＰＲＯＭ２６に格納される。

【００７６】すなわち、出現度数テーブル及び符号テー
ブルをダイナミックに更新しながら、圧縮データを復号
化する場合、図７（Ｂ）において、まず、ステップＰ１
で出現度数テーブル及び符号テーブルを初期化する。次
に、ステップＰ２で圧縮データをファイル３１から読出
し復号化する。次いで、ステップＰ３で圧縮データを入
力する毎に出現度数テーブルを更新する。これにより、
圧縮データが原データに復元される。

【００７７】このようにして、本発明の第２の実施例に
係るデータ圧縮方法によれば、図７（Ａ）に示したよう
に、圧縮すべき１単位のデータが入力される毎に出現度
数テーブルが更新される。このため、出現度数作成エデ
ィタ２１での出現度数テーブルの更新に伴って符号変換
エディタ２３では短時間に位置情報を書き換えることが
でき、タイナミック（動的）に符号テーブルを再構成す
ることができる。また、出現度数テーブルの更新は、一
部のデータのみの入替えで済み、全てのデータを並び変
えが不要となる。

【００７８】これにより、当該符号テーブルを圧縮デー
タに含める必要が無くなり、データ圧縮率が向上する。
また、本発明の実施例によれば、１バイト又は１文字単
位の出現頻度をダイナミックに符号化することができ、
メモリ容量が限られている対象機器に本実施例のデータ
圧縮機能を組み込む場合等に、有効にメモリ領域を使用
することができる。

【００７９】（３）第３の実施例の説明 図10（Ａ）は、本発明の第３の実施例に係るデータの圧
縮フローチャートであり、図10（Ｂ）は、その復元フロ
ーチャートである。図11は、データ圧縮時の位置情報の
レベル調整フローチャートをそれぞれ示している。各フ
ローチャートは制御アルゴリズムとして図３に示したＥ
ＰＲＯＭ２６に格納される。

【００８０】第３の実施例では第１，第２の実施例と異
なり、データを位置情報に変換した後に、圧縮データの
長さを調整するものである。第１，第２の実施例に係る
データ処理方法では、入力データの次に出現する文字の
出現度数分布が平均化されている場合や、データの出現
度数が十分に収集されていない場合等には、次のデータ
を正確に出現予測することができない。

【００８１】そこで、本発明の第３の実施例では、レベ
ル調整エディタ２４により、圧縮データの長さを調整
し、データ圧縮率の劣化を防ぐことを特徴としている。
例えば、圧縮すべきデータがプログラムデータ等の場合
には、機械語で書かれた転送命令等の分布に偏りが生ず
る。具体例を示すと、オペレーションコードの次にアド
レスが付随されているジャンプ命令等では、次の１バイ
トの出現確率が平均化されてしまう。

【００８２】データの種類はファイルの拡張子から判断
する。一般には、オペレーションシステムには規則性が
あり、例えば、パーソナルコンピュータのＭＳ−ＤＯＳ
の場合、拡張子＝ＥＸＥから入力データが実行形式（機
械語）のファイルであることが判断できる。すなわち、
本発明の第３の実施例では、出現度数分布の偏りが明確
なものに対しては、最初の符号化によって変換された圧
縮データの長さを調整する。これにより、更に、短い位
置情報に変換することで、データ圧縮率が向上する。

【００８３】表４は、１バイト（８ビット）単位の入力
データに対する圧縮データの構成内容を示している。す
なわち、本実施例では、原データを識別子無しの８ビッ
トにより符号化するレベル「０」を含めて、７つのレベ
ルを設け、これに基づいて圧縮データを構成する。

【００８４】

【表４】

【００８５】表４において、第１のレベルでは、例え
ば、２５６個のデータサンプルに対して、位置情報を識
別するために５つの識別子を割当てる。具体的には、先
頭位置〜第15番目の位置情報を識別する識別子として
「００」を割当てる。その位置情報には４ビットを割当
てる。これにより、圧縮データは６ビット長になる。同
様に、第16番目〜第31番目の位置情報の識別子には、
「０１０」を割当て、その位置情報には４ビットを割当
てる。これにより、圧縮データは７ビット長になる。第
32番目〜第63番目の位置情報の識別子には、「０１１」
を割当て、その位置情報には５ビットを割当てる。これ
により、圧縮データは８ビット長になる。第64番目〜第
127 番目の位置情報の識別子には、「１０」を割当て
る。その位置情報には６ビットを割当てる。これによ
り、圧縮データは８ビット長になる。第128 番目〜第25
5 番目の位置情報の識別子には、「１１」を割当て、そ
の位置情報には７ビットを割当てる。これにより、圧縮
データは９ビット長になる。

【００８６】第２のレベルでは、第１のレベルと同様に
５つの識別子を割当てる。具体的には、先頭位置〜第３
番目の位置情報を識別する識別子として「０００」を割
当て、その位置情報には２ビットを割当てる。これによ
り、圧縮データは５ビット長になる。同様に、第４番目
〜第11番目の位置情報の識別子には、「００１」を割当
て、その位置情報には３ビットを割当てる。これによ
り、圧縮データは６ビット長になる。第12番目〜第27番
目の位置情報の識別子には、「０１０」を割当て、その
位置情報には４ビットを割当てる。これにより、圧縮デ
ータは７ビット長になる。第28番目〜第59番目の位置情
報の識別子には、「０１１」を割当てる。その位置情報
には５ビットを割当てる。これにより、圧縮データは８
ビット長になる。第60番目〜第255 番目の位置情報の識
別子には、「１」を割当て、その位置情報には７ビット
を割当てる。これにより、圧縮データは９ビット長にな
る。

【００８７】第３のレベルでは、第１，２のレベルと同
様に５つの識別子を割当てる。具体的には、先頭位置及
び第１番目の位置情報を識別する識別子として「００
０」を割当て、その位置情報には１ビットを割当てる。
これにより、圧縮データは４ビット長になる。同様に、
第２番目〜第５番目の位置情報の識別子には、「００
１」を割当て、その位置情報には２ビットを割当てる。
これにより、圧縮データは５ビット長になる。第６番目
〜第13番目の位置情報の識別子には、「０１０」を割当
て、その位置情報には３ビットを割当てる。これによ
り、圧縮データは６ビット長になる。第14番目〜第29番
目の位置情報の識別子には、「０１１」を割当てる。そ
の位置情報には４ビットを割当てる。これにより、圧縮
データは７ビット長になる。第60番目〜第255 番目の位
置情報の識別子には、「１」を割当て、その位置情報に
は８ビットを割当てる。これにより、圧縮データは９ビ
ット長になる。

【００８８】第４のレベルでは、第１〜３のレベルと異
なり、４つの識別子を割当てる。具体的には、先頭位置
及び第１番目の位置情報を識別する識別子として「０
０」を割当て、その位置情報には１ビットを割当てる。
これにより、圧縮データは３ビット長になる。同様に、
第２番目及び第３番目の位置情報の識別子には、「０１
０」を割当て、その位置情報には１ビットを割当てる。
これにより、圧縮データは４ビット長になる。第４番目
〜第７番目の位置情報の識別子には、「０１１」を割当
て、その位置情報には２ビットを割当てる。これによ
り、圧縮データは５ビット長になる。第８番目〜第255
番目の位置情報の識別子には、「１」を割当てる。その
位置情報には８ビットを割当てる。これにより、圧縮デ
ータは９ビット長になる。

【００８９】第５のレベルでは、第１〜４のレベルと異
なり、３つの識別子を割当てる。具体的には、先頭位置
を識別する識別子として「００」のみを割当てる。これ
により、圧縮データは２ビット長になる。同様に、第１
番目及び第２番目の位置情報の識別子には、「０１」を
割当て、その位置情報には１ビットを割当てる。これに
より、圧縮データは３ビット長になる。第３番目〜第25
5 番目の位置情報の識別子には、「１」を割当て、その
位置情報には８ビットを割当てる。これにより、圧縮デ
ータは９ビット長になる。

【００９０】第６のレベルでは、第１〜５のレベルと異
なり、２つの識別子を割当てる。具体的には、先頭位置
を識別する識別子として「０」のみを割当てる。これに
より、圧縮データは１ビット長になる。同様に、第１番
目及び第255 番目の位置情報の識別子には、「１」を割
当て、その位置情報には８ビットを割当てる。これによ
り、圧縮データは９ビット長になる。

【００９１】なお、表４に示した７つのレベルはメモリ
２５等に予め格納される。符号変換エディタ２３は、こ
の７つのレベルを参照して入力データを符号化する。レ
ベル調整エディタ２４は符号変換エディタ２３によって
割当てられた圧縮データのレベルを検討し、出現度数分
布の偏りが明確なものに対して、更に、短い位置情報に
変換する。

【００９２】次に、本発明の第３の実施例に係るデータ
圧縮方法について説明をする。例えば、出現度数分布の
偏りに応じて入力データを符号化する場合、図10（Ａ）
のフローチャートにおいて、まず、ステップＰ１で、入
力データ列をファイル３０から全て読み込んで出現度数
テーブルを作成し、ステップＰ２で出現度数テーブルか
ら符号テーブルを作成する。これまでは第１の実施例と
同様である。

【００９３】次に、ステップＰ３で圧縮データの長さを
調整するオフセット符号化処理をする。この際に、レベ
ル調整エディタ２４により圧縮データの長さが調整され
る。圧縮データの長さ調整については、図11のサブルー
チンに移行して、ステップＰ31で、１単位のデータをフ
ァイル３０からメモリ２５に読み込み、次に、ステップ
Ｐ32で符号化処理をする。符号化は第１の実施例で説明
したように、１バイト又は１文字単位に符号変換エディ
タ２３により実行される。

【００９４】次いで、ステップＰ33で圧縮データのビッ
ト長を把握する。ここで、先に符号変換エディタ２３に
より割当てられた圧縮データが８ビット以下の場合（Ｎ
Ｏ）には、ステップＰ35に移行する。また、圧縮データ
が９ビット以上の場合（ＹES）には、ステップＰ34に移
行して、符号化レベルを１ランク下げて、メインルーチ
ンに復帰する。例えば、入力データの次のデータの出現
分布に偏りが生じているとして、符号変換エディタ２３
により、表４に示すような第５のレベルが割当てられ、
これがレベル調整エディタ２４により、あまりデータの
出現分布に偏りが生じていないと判断されると、１ラン
ク下の第４のレベルによって圧縮データが構成される。

【００９５】また、圧縮データが８ビット以下の場合に
は、ステップＰ35で、符号化レベルが最も高いか否かを
判断する。この際に、レベルが最も高い場合（ＹES）に
は、そのままメインルーチンに復帰する。しかし、符号
化レベルが高くない場合（ＮＯ）には、ステップＰ36に
移行して、擬似レベル調整を実行する。擬似レベル調整
は、現在よりも圧縮データのビット長が上がるか下がる
かを見いだすために、仮に符号化を実行するものであ
る。

【００９６】すなわち、仮に符号化を実行した結果、ス
テップＰ37で、現在よりも短い圧縮データになる場合
（ＹES）には、ステップＰ38に移行して符号化のレベル
を上げる。例えば、入力データの次のデータの出現分布
に偏りが生じたとして、符号変換エディタ２３により、
表４に示すような第５のレベルが割当てられ、これがレ
ベル調整エディタ２４により、データの出現分布に偏り
が生じていると判断されると、１ランク下の第４のレベ
ルによって圧縮データが構成される。反対に、圧縮デー
タが現在よりも長くなる場合（ＹES）には、擬似レベル
調整をキャンセルしてメインルーチンに復帰する。

【００９７】そして、メインルーチンのステップＰ４で
はデータの符号化の終了判断を第１の実施例と同様に行
う。これにより、出現度数分布の偏りに応じて入力デー
タをを符号化し、この圧縮データをファイル３１に格納
することができる。次に、本発明の第３の実施例に係る
圧縮データの復元処理について説明をする。図10（Ｂ）
は、本発明の第３の実施例に係る圧縮データの復元フロ
ーチャートである。復元フローチャートは制御アルゴリ
ズムとして図３に示したＥＰＲＯＭ２６に格納される。

【００９８】図10（Ｂ）において、まず、ステップＰ１
で圧縮データをファイル３１から読出し識別子及び位置
情報から符号テーブルを作成する。符号テーブルについ
ては、図５において説明したものが再現される。次に、
ステップＰ２で再度、圧縮データをファイル３１から読
出し、レベル調整された符号テーブルを把握しながら、
圧縮データを復号化する。復号化は、一般的に用いられ
る図６（Ｂ）に示すような符号木の構成によって実行す
る。

【００９９】次いで、ステップＰ３で圧縮データを全て
復元したか否かを判断する。この際に、圧縮データを全
て復元した場合（ＹES）には、制御アルゴリズムを終了
し、圧縮データを全て復元していない場合（ＮＯ）に
は、ステップＰ２に戻って、圧縮データの復号化処理を
継続する。これにより、圧縮データが復号化され、この
原データがファイル３０に格納される。

【０１００】このようにして、本発明の第３の実施例に
係るデータ圧縮方法によれば、図11に示すように、ステ
ップＰ32で圧縮データが変換された後に、ステップＰ33
〜ステップＰ38で圧縮データの長さが調整されるため、
入力データの種別に応じて、圧縮データの長さをダイナ
ミックにレベル調整した圧縮データを再構成するオフセ
ット符号化を実行することができる。

【０１０１】すなわち、本実施例のオフセット符号化で
は、圧縮すべきデータがプログラムデータ等の場合に
は、データの出現度数分布が明確になることから、より
短い位置情報に変換し、また、出現度数分布に偏りが生
じている場合には、レベルを上げることにより、短い位
置情報に変換することができる。更に、圧縮率を高める
ための工夫としては、予め、統計情報を収集する等し
て、各入力データ別の出現度数を事前に把握し、これが
把握できた場合には、出現度数の高いデータをメモリ２
５の上位アドレスに初期設定して置く。

【０１０２】具体的には、該当するコードの出現度数を
計数するカウンタの初期値を１以上に設定する。これに
より、短い位置情報の符号ビットに変換される確率が高
まる。例えば、コンピュータ（Ｃソース）プログラム等
では、１６進数により表される「０Ｄ」の次に、「０
Ａ」が出現する確率が高くなる。このように出現頻度の
高いデータほど短い位置情報に変換される確率が高ま
り、統計情報が少ない場合や、次の文字の出現確率の度
数分布が平均化され、予測が困難である文字や文字列に
対して、次の文字や文字列を正確に出現予測することが
でき、データ圧縮率が向上する。

【０１０３】

【発明の効果】以上説明したように、本発明のデータ処
理装置によれば、出現度数テーブルを参照しながら、圧
縮すべきデータの次のデータの出現予測をするデータ予
測手段が設けられるため、次に出現する文字又は文字列
を、その出現確率が高いデータほど短い位置情報にデー
タ変換手段により変換すること、及び、出現確率の低い
データほど長い位置情報に変換することができ、文字列
の順番が予想できる入力データ列の場合に、１文字のみ
の出現確率を計算するハフマン符号化方法に比べて、デ
ータ列の圧縮率を向上させることができる。

【０１０４】本発明の他のデータ処理装置によれば、１
単位のデータが入力される毎に出現度数テーブルがデー
タ作成手段により更新されるため、出現度数テーブルの
更新に伴ってデータ変換手段では短時間に位置情報を書
き換えることができ、タイナミック（動的）に符号テー
ブルを再構成することができる。また、全ての位置情報
の並び変えを行わずに、符号テーブルを更新することで
き、データ圧縮時間の高速化が図られる。

【０１０５】本発明の他のデータ処理装置によれば、入
力データを圧縮データに変換した後に、レベル調整手段
により圧縮データの長さが調整されるため、入力データ
の種別に応じて、圧縮データの長さをダイナミックにレ
ベル調整した圧縮データを再構成するオフセット符号化
を実行することができ、出現度数分布の傾向が明確な場
合には、より短いビット長の圧縮データに変換し、出現
度数分布に偏りが生じている場合には、レベルを上げて
短いビット長の圧縮データに変換することができ、デー
タ圧縮率が向上する。

【０１０６】このような１バイト又は１文字単位の出現
頻度をダイナミックに符号化するデータ圧縮機能を対象
機器に組み込むと、メモリ容量の削減化が図れる。本発
明のデータ処理方法によれば、予め、圧縮すべきデータ
の種類毎に、出現度数を計数した出現度数テーブルを作
成しているため、圧縮すべきデータの前後の対象文字や
文字列の接続状態を把握することができる。

【０１０７】また、本発明のデータ処理方法によれば、
符号テーブルから直接，位置情報及び識別子から構成さ
れる圧縮データを出力することができる。これにより、
文字列や文字の出現予測をしながら、高速に符号化又は
復号化可能なデータ圧縮又は復元装置を構成することが
でき、磁気ディスク装置等の記憶容量の実質的な増加及
びデータ伝送時の送信時間の短縮化に寄与するところが
大きい。

【図面の簡単な説明】

【図１】本発明に係るデータ処理装置の原理図である。

【図２】本発明に係るデータ処理方法の原理図である。

【図３】本発明の各実施例に係るデータ圧縮及び復元装
置の構成図である。

【図４】本発明の第１の実施例に係るデータの圧縮及び
復元フローチャートである。

【図５】本発明の各実施例に係る符号変換エディタの機
能説明図である。

【図６】本発明の各実施例に係る圧縮データのフォーマ
ット及び符号木の説明図である。

【図７】本発明の第２の実施例に係るデータの圧縮及び
復元フローチャートである。

【図８】本発明の第２の実施例に係る出現度数テーブル
の更新フローチャートである。

【図９】本発明の第２の実施例に係る出現度数テーブル
の更新時のデータ交換の状態図である。

【図10】本発明の第３の実施例に係るデータの圧縮及び
復元フローチャートである。

【図11】本発明の第３の実施例に係る圧縮データのレベ
ル調整フローチャートである。

【図12】従来例に係るデータ圧縮装置の構成図である。

【符号の説明】

１１…データ作成手段、 １２…データ予測手段、 １３…データ変換手段、 １４…レベル調整手段、 ２１…出現度数作成エディタ、 ２２…データ比較エディタ、 ２３…符号変換エディタ、 ２４…レベル調整エディタ、 ２５…メモリ、 ２６…ＥＰＲＯＭ ２７…ディスプレイ、 ２８…キーボード、 ２９…ＣＰＵ、 ３０…入力データファイル、 ３１…圧縮データファイル、 ３２…バス、 ＤIN…入力データ、 ＤOUT …圧縮データ。

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁶ 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｈ０４Ｎ 1/417 7/32

Claims (13)

【特許請求の範囲】
1. 【請求項１】 圧縮すべきデータの種類毎に該データの
   出現度数を計数して出現度数テーブルを作成するデータ
   作成手段と、 前記データ作成手段からの出現度数テーブルを参照しな
   がら、圧縮すべきデータの次のデータの出現予測をする
   データ予測手段と、 前記データ予測手段のデータの出現予測に応じて該デー
   タを出現確率の高いデータほど短いビット長の圧縮デー
   タに変換し、出現確率の低いデータほど長いビット長の
   圧縮データに変換するデータ変換手段とを備えることを
   特徴とするデータ処理装置。
2. 【請求項２】 前記データ作成手段は、圧縮すべき１単
   位のデータを入力する毎に出現度数テーブルを更新する
   ことを特徴とする請求項１記載のデータ処理装置。
3. 【請求項３】 前記データ変換手段によって変換された
   圧縮データの長さを調整するレベル調整手段が設けられ
   ることを特徴とする請求項１記載のデータ処理装置。
4. 【請求項４】 前記データ作成手段は、圧縮すべき全て
   のデータ又は１単位のデータを取り込んで出現度数テー
   ブルを作成することを特徴とする請求項１，２及び３記
   載のいずれかのデータ処理装置。
5. 【請求項５】 前記データ変換手段は、出現度数テーブ
   ルでデータを出現度数の高い順に並べ換え、該出現度数
   の高いデータから出現度数の低いデータに至る位置に対
   して、該データを出現度数の高いデータほど短い位置情
   報を割当て、かつ、出現度数の低いデータほど長い位置
   情報を割当てた符号テーブルを参照することを特徴とす
   る請求項１，２及び３記載のいずれかのデータ処理装
   置。
6. 【請求項６】 前記データ変換手段は、データ作成手段
   での出現度数テーブルの更新に伴って圧縮データを書換
   えることを特徴とする請求項１，２及び３記載のいずれ
   かのデータ処理装置。
7. 【請求項７】 予め、前記圧縮すべきデータの種類毎に
   該データの出現度数を計数して出現度数テーブルを作成
   し、 前記作成された出現度数テーブルを参照しながら、圧縮
   すべきデータの次のデータの出現予測をし、 前記データの出現予測に応じて該データを出現確率の高
   いデータほど短いビット長の圧縮データに変換し、か
   つ、出現確率の低いデータほど長いビット長の圧縮デー
   タに変換することを特徴とするデータ処理方法。
8. 【請求項８】 前記圧縮データの変換は、出現度数テー
   ブルのデータを出現度数の高い順に並べ換え、該出現度
   数の高いデータから出現度数の低いデータに至る位置に
   対して、該データを出現度数の高いデータほど短い位置
   情報を割当て、かつ、出現度数の低いデータほど長い位
   置情報を割当てた符号テーブルを参照することを特徴と
   する請求項７記載のいずれかのデータ処理方法。
9. 【請求項９】 前記出現度数テーブル及び符号テーブル
   は、圧縮すべき１単位のデータが入力される毎に更新す
   ることを特徴とする請求項７及び８記載のいずれかのデ
   ータ処理方法。
10. 【請求項10】 前記圧縮すべきデータを圧縮データに変
    換した後に、圧縮データのビット長を調整することを特
    徴とする請求項７，８及び９記載のいずれかのデータ処
    理方法。
11. 【請求項11】 前記出現度数テーブルは、圧縮すべき全
    てのデータ又は１単位のデータに応じて作成することを
    特徴とする請求項７，８及び９記載のいずれかのデータ
    処理方法。
12. 【請求項12】 前記データの次のデータの出現予測は、
    出現度数テーブルに書き込まれた各々の出現度数のデー
    タと、圧縮すべきデータの次のデータとを比較すること
    を特徴とする請求項７，８及び９記載のいずれかのデー
    タ処理方法。
13. 【請求項13】 前記圧縮データは、出現度数の高いデー
    タから出現度数の低いデータに至る位置を表示する位置
    情報及び前記位置情報を識別する識別子から構成するこ
    とを特徴とする請求項７，８及び９記載のいずれかのデ
    ータ処理方法。