JPH01125028A - 適応データ圧縮方法および装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は一般にデータ圧縮に関し、特に実時間で動作し
入力情報の流れにおけるキャラクタの出現統計の変化に
動的に適応できる適応データ圧縮方法および装置に関る
、。

（従来の技術） データ圧縮用の方法および装置は多数知られている。こ
れら既知の技術の多くは、データセット中の要素または
キャラクタの出現頻度に関係る、統計に依存している。

一般に、圧縮されるデータセットまたはデータファイル
は、あらかじめ走査または処理し、データセット中のキ
ャラクタの出現統計を累算る、ことにより、これらキャ
ラクタを表現る、コードを割り当てるための準備をる、
必要がある。次に、より短いコードをより頻繁に出現る
、キャラクタに割り当て、より長いコードを出現頻度の
低いキャラクタに割り当てる。

良く知られているシャノンーファノコードは、圧縮され
る入力ファイルを分析し、特定のキャラクタの出現確率
を降順に配置る、。次にキャラクタセットを等しいまた
はほぼ等しい合計確率のサブセットに分割し、一つのサ
ブセット中の第１コード数値としてＯを割り当て、第２
のサブセット中の第１コード数値として１を割り当てる
。これらステップを繰り返し、各サブセットが単一のキ
ャラクタを有る、ようにる、。この方法によって作られ
るコードは即座に復号可能である。これはあるコードワ
ードは他のいかなるコードワードの接頭語とならないか
らである。

良く知られているハフマンコードもやはり即座の復号特
性を有しているが、符号化ツリーを使用る、。この方法
は、可能な最小平均ワード長を作るが、ソース家たは入
力データファイルをあらかじめ走査しなければならず、
キャラクタの確率は降順に配置される。ａも低い二つの
確率は結合され、確率ツリーは高い確率の枝を上部に置
くことによって構成される。このツリーにおいて、各ペ
アの高い方に０が割り当てられ低い方に１が割り当てら
れる９次に、各確率項からの通路は統−点に至り、その
通路に沿って１および０が記録される。この結果得られ
るコードは１，０の並びである、いうまでもなく、コー
ドを割り当てる前に全データを分析る、必要がある。

これらデータ圧縮技術は、データを前もって走査る、た
めの十分な処理時間がある場合には適切であるが、変復
調器（モデム）を含むデータ通信など実時間分野におい
ては、データを前もって走査して最も効率のよいコード
を確立る、ことが常にできるとは限らず、常に望まれる
ものでもない。

このような場合、データの性質は変化し得るので、固定
圧縮機構は効率が悪い０例えばモデムは、テキストファ
イル、グラフィックファイル、テキストおよびグラフィ
ックの混合、ソフトウェアオブジェクトコード、スプレ
ッドシートファイル、他のシステムとの対話式通信、そ
の他データなどを送信る、ものである。圧縮を効率的に
行うには、前走査や独立した符号化機構が多異なるタイ
プのデータに必要となろう。これらのデータタイプは、
与えられた送信においてさえ予測不能に変化る、。

多くの場合、最適以下のコードでも、全体送信時間、デ
ータ記憶時間、および圧縮を減少させる上で許容可能で
ある。

１従って、モデムや他の実時間データ圧縮分野に対して
適切であるようなデータ圧縮技術が必要であり、この分
野においてはデータのタイプが頻繁に変化し、１回の送
信内においてさえ、それが変化る、。

従来の適応実時間データ通信方法の一つは、符号化装置
および復号化装置の両方において動的Ｃご生成されるテ
ーブルを使用る、。フランセスエルベーコン等による米
国特許第４，６１２，５３２号において、データ流れ中
の一連のキャラクタは、符号化装置内において動的に生
成されるテーブルに基づいて符号化される。そして復号
化装置は、対応る、テーブルを生成してその符号化され
たデータを復号る、ように構成される。ここで復号テー
ブルは、符号化されたデータの構造に基づいて動的Ｇこ
生成される。基本的に、この符号化装置では、データ流
れ中の与えらなキャラクタの後には、所定の確率を有し
たキャラクタの候補の一つが従うという仮定を立ててい
る。従って、この符号化装置の生成る、テーブルは、与
えられたキャラクタについて、そのデータ流れ中に出現
る、であろう次の連続る、キャラクタに対る、おおよそ
の出現頻度の順に並んだ候補のリストが提供される。

そのデータ流れ中に、テーブル中のキャラクタに従われ
た与えられたキャラクタが出現る、と、符号化装置はテ
ーブル中のそのキャラクタの通常の位置に基づいたその
文字キャラクタを表現る、２進コードを送る。このコー
ドは、最も頻繁に発生る、候補に対して最も短いもので
あり、出現頻度の低い候補については長い、このテーブ
ルは、与えられたキャラクタの後のキャラクタの局所的
な頻度に基づいて生成されるやこのため、このテーブル
は、局所的な出現頻度が変化る、と動的に変更され得る
。

（発明が解決しようとる、課題） このベーコンの特許において、圧縮されるデータはラン
ダムでなく、与えられたキャラクタは。

次のキャラクタについての複数の可能な候補の一つによ
って従われる可能性があると仮定している。

この仮定のため、この方法は英語テキストなどへの応用
に限定される。英語テキストにおいては、この技術は極
めて有効に使用される可能性がある。

しかしながら、テキストと数字データとの混合が含まれ
るような（スプレッドシートなど）場合、データタイプ
がテキストから数字に変化る、と圧縮効率は失われる。

これは数字ファイルがテキストファイルよりもさらに無
作意だからである。ところが、データタイプが数字に変
化る、と、数字。

の出現確率がテキストキャラクタの出現確率に比較して
極端に上昇る、ので、圧縮アルゴリズムをデータタイプ
の性質の変化に適応させ得るなら、効率を上げることが
可能である。

従って、前記ベーコンの方法の最も適している応用分野
は、データタイプが予測可能であること、つまり、送信
されるファイルがテキストまたは数値（ただし両方では
ない）としてあらかじめ決っているか、データが不規則
でない分野である９しかしながら、テキストと数値の混
合のようにデータタイプが予測不可能であり、データタ
イプが不明である場合、この方法は最適以下のコードを
使用る、ようになる。従って、あらゆるデータタイプま
たはデータタイプの分布に対して動的に適応可能である
適応データ圧縮方法を提供る、必要がある。

（課題を解決る、ための手段） 本発明は、適応データ圧縮方法および装置を提供る、も
のであり、これら方法および装置は、入力ファイルが前
走査されることを必要とせず、また非任意データという
仮定にも依存しない。本方法は、あらゆるデータの冗長
性に適応可能であり、与えられたキャラクタに続く他の
キャラクタの与えられた確率を有る、キャラクタで構成
されるデータに限定されない。また本方法は、モデムな
ど実時間でのデータ圧縮が求められる応用装置に使用る
、ことが適切である。また、生成されるコードは即座に
復号される特性を有る、。

簡単に説明すれば、本発明は、動的適応データ圧縮方法
を提供し、この方法はデータ統計の周期的な蓄積と圧縮
コードの特定のキャラクタへの再割当を出現確率の変化
の関数として行うものである。他の多くのデータ圧縮技
術と同様に、本発明はデータ統計の原理に基づいて動作
る、。しかしながら、これら統計は、本発明においては
処理中に蓄積されるものであって、データを前走査して
その特性を決定る、必要はない。より頻繁に出現る、デ
ータは、出現頻度が低いデータよりも少ないビットを持
つ。

また、ハフマンコード等の最適コード法において一般に
使用されるように任意長のビットパターンでデータを表
現る、のではなく、本発明は所定ビット長の圧縮コード
のセットを使用る、。好適実施例において、４，８．１
２の各ビット長が使用されるので、本方法は、オクテツ
トベースのパケットシステムや８ビットマイクロプロセ
ツサにおいて容易に実現可能である。ｆ＆適の圧縮およ
び動作は、本発明において、多数のデータキャラクタが
４ビット圧縮コードで表現される場合に実現される。

本発明の好適方法および装置は、データ特性やタイプの
変化に適応できる能力を有る、９周期的に、現在の圧縮
動作がその時の統計を利用して評価される。この評価に
応じて、圧縮レベル、すなわち異なる圧縮コードに対応
づけられているアルファベットキャラクタのキャラクタ
数が変更されて動作を最適にる、。

データ統計は、カウンタと呼ばれるレジスタまたはメモ
リ箇所の線形の配列に保持され、ここではデータセット
またはアルファベットにおける各データキャラクタにつ
いて一つの要素が保持される。これらカウンタは、所定
数のキャラクタの処理において出現る、各キャラクタの
出現回数を格納る、。この配列は、常に相対的にソート
されており、最も頻繁に出現る、キャラクタのカウント
数は、配列の開始端側に位置される。このカウント配列
内におけるキャラクタの順序は、圧縮コードを決定し、
さらに幾つの４ビットニブル（１゜２、または３）が入
力データ流れにおけるキャラクタを表現る、ために使用
されるかを決定る、。

アルファベットキャラクタの最初の所定数ａは、１ニブ
ルで符号化される。ｆ＆後の１６ａ個のキャラクタは、
３ニブルで符号化される。残りのキャラクタは、２ニブ
ル（８ビットバイト）で符号化される。ここでａを圧縮
レベルと呼ぶ、このａの値は、キャラクタカウント数と
して表現されるキャラクタの出現頻度の関数として周期
的に再計算される。

さらに詳細に説明すれば、好適データ圧縮方法は、モデ
ムに内蔵されるプログラム済みのマイクロコンピュータ
において実行され、次のような一連のステップからなる
。

（１）アルファベットキャラクタを符号化る、ための複
数のデジタル表現を有る、符号化テーブルをマイクロコ
ンピュータに付属したメモリに設ける。各キャラクタに
は、そのキャラクタの出現頻度に関る、カウント数が付
与される。この符号化テーブルは、アルファベットキャ
ラクタに対して、複数の圧縮コードの一つを演算る、た
めに使用される。これら圧縮コードの幾つかは、他より
も短い。最も短いコードは、アルファベットキャラクタ
の符号化前のデジタル表現よりも短い。

（２）アルファベットキャラクタの一つで表現されるデ
ータ項目が符号化用に提供されると、その特定のアルフ
ァベットキャラクタに対応る、圧縮コードが前記符号化
テーブルを使用して演算される。また、その特定のキャ
ラクタに関る、カウント数が増分され、その特定のキャ
ラクタがデータ流れにおいて出現したことを反映させる
。圧縮コードの演算は、前記符号化テーブル内における
提供された特定のキャラクタの位置の関数として行われ
る。

（３）次に、演算された圧縮コードは、圧検出力として
提供される。このコードは、モデムによって通信回線を
介して他のモデムに送信される。

（４）符号化テーブルにおける圧縮コードとアルファベ
ットキャラクタとの関係が周期的に調整される。この調
整は、符号化用に提供される所定数の複数のキャラクタ
における各アルファベットキャラクタのカウント数とし
て表現される出現頻度の関数としてなされる。この所定
の複数は限定数として更新速度の便宜を計るように選択
される。

従って、キャラクタの出現頻度が符号化用に提供される
複数のキャラクタについて変化る、と、より出現頻度の
高いキャラクタは、符号化テーブルにおいてより短い圧
縮コードに対応づけられるようになる。

前記したように、符号化テーブルは、キャラクタと圧縮
コードとの対応と、キャラクタとカウント数との対応を
格納る、。！＆初に、アルファベットの各キャラクタと
それらに対応る、圧縮コードとは、初期順序配列に配置
され、４ビットコードが配列の開始端側に配置される。

圧縮コードとアルファベットキャラクタとの関係の周期
的な調整は、次のようなステップで実行される。

（１）符号化テーブルにおいて、別個のキャラクタカウ
ント数が各アルファベットキャラクタごと保持される。

（２）データ項目が符号化用に提供されると、符号化テ
ーブルを使用して圧縮コードが演算され、符号化用に提
供された該キャラクタに対応る、キャラクタカウント数
が増分され更新される。

（３）該キャラクタカウント数が増分されると、該更新
されたキャラクタカウント数は、配列中においてより短
いコードに対応付けされていると見なされる位置にある
所定のキャラクタのカウント数と比較される。すなわち
、特定のキャラクタのカウント数は、配列の開始端に近
いより短いコードのある位置の所定のキャラクタのカウ
ント数と比較される。

（４）前記特定のキャラクタのカウント数が配列の開始
端に近い所定のキャラクタのカウント数より大きければ
、符号化直後のキャラクタと所定キャラクタとの配列中
の相対位置が交換される。

これにより、より大きなカウント数を有る、キャラクタ
が、配列中においてより短いコードに対応していると見
なされる位置に関連付けられる。

（５）前記特定のキャラクタのカウント数が配列の開始
端に近い所定のキャラクタのカウント数より大きくなけ
れば、次にステップ（３）が繰り返され、更新直後のキ
ャラクタのカウント数と配列の開始端から１ステツプだ
け遠いキャラクタのカウント数とが比較される（すなわ
ち符号化用に提供されたキャラクタのキャラクタのカウ
ント数に近いもの）、この処理は符号化用に提供された
キャラクタに到達る、と停止される。

圧縮コードとアルファベットキャラクタとの対応関係の
周期的な調整は、符号化された各項目について行われる
ので、より頻繁に出現る、キャラクタが配列の開始端の
方向に移動してより短いコードに関連付けられるように
なる。開示実施例において、前記あらかじめ選択された
キャラクタは、配列内の開始端に向かって配列内におい
て所定数の位置に配置され、好適実施例においては１６
＠所に配置される。このため、比較および交換は部分的
なソートであり、マイクロコンピュータ上で容易に迅速
に実行可能である。これは必要な比較演算とデータ交換
とが極めて少ないからである。

圧縮データの復号は、符号化と同一の方法で維持される
並列復号化テーブルによって実現される。

符号化テーブルおよび復号化テーブルは、限定された栄
件で調整または更新されるので、極めて高速で圧縮また
は復元が可能であり、現在のデータマイクロコンピュー
タ回路の性能内で実現可能である。従って、本発明は、
モデムにおいて実施された場合、１９，２００ビット／
秒の同期データ通信が可能である。これはテーブルの更
新速度が早いからである。

さらに、本発明の好適方法は、より短い圧縮コードに対
応る、キャラクタ数を最大にる、段階を含む。まず、配
列は、４ビットコードに対応づけられる所定数のアルフ
ァベットキャラクタと、この１６倍の数の１ｚビットコ
ードに対応づけられるアルファベットキャラクタと、８
ビットコードに対応づけられる残りのアルファベットキ
ャラクタとにリセットされる。符号化レベルは、所定数
ａ′ｃ表され、これはデータ統計が蓄積されるに連れて
動的に変化し、出現確率の高いキャラクタが４ビットコ
ードを受け取るようになる。従って、４．８，１ｚビッ
トコードに各々対応づけられるキャラクタのセットのサ
イズを周期的に調整る、段階が実行される。これは、キ
ャラクタカウント数のグループをまとめて、出現頻度の
低いキャラクタについてグループカウント数を与え、こ
れらグループカウント数と、より出現頻度の高いキャラ
クタのキャラクタカウント数とを比較し、４ビットコー
ド（すなわち最短コード）のセットの項目数を順次に増
加させる。このように、最短デジタルコードに対応る、
キャラクタセットのサイズを拡大して、より高い出現確
率を有る、より多くのキャラクタを含めることにより、
短いキャラクタコードをより最適に使用る、。すなわち
、より多くの短いコードがより出現頻度の高いキャラク
タに対応づけられ、より多くの長いコードが出現頻度の
低いキャラクタに割り当てられる。

さらに、本発明は、繰り返しキャラクタの列を表現る、
ための新規で有効な方法を含む。当業者には良く知られ
ているように、モデムによって送信されるある種のデー
タファイル、例えばスプレッドシートファイルには繰り
返しキャラクタ列が含まれることが多い０本発明の方法
は、符号器および復号器の両方によって、所定数例えば
３個を越えるキャラクタの列が出現る、と繰り返し状態
に入らせる。この繰り返し状態は、自動的に、３個の繰
り返しキャラクタの送信または記録に続いて確立される
。この繰り返し状態に入った後、繰り返しキャラクタ（
所定数以後の）の追加の出現数を表す繰り返し記号が送
信または記録される。

この繰り返し記号は、第２の所定数例えば１５までの追
加の出現数を表すことができる。または、その繰り返し
記号は、前記第２の所定数を表すとともに、繰り返し状
態が続行して別の繰り返し記号が予測されることを示す
こともできる。第１の所定数を越える繰り返しキャラク
タの列を含むことが頻繁であるデータは著しい圧縮が実
現される。

従って、本発明の目的は、データ統計の変化に実時間で
動的に適応可能なデータ圧縮方法および装置を提供る、
ことである。

本発明の他の目的は、最適コードを選択る、ためＧこデ
ータの前走査を必要としない改良されたデータ圧縮方法
および装置を提供る、ことである。

本発明の他の目的は、情報を表現するために使用される
コードが即座に復号され得るようなデータ圧縮方法を提
供る、ことである。

本発明の他の目的は、モデム等のデータ通信装置への使
用が適切である改良データ圧縮方法および装置を提供る
、ことである。

本発明の他の目的は、データ特性の変化に動的に適応る
、改良データ圧縮装置および方法を提供る、ことである
。

本発明の他の目的は、テキストファイル、グラフィック
フ゛アイル、テキストおよびグラフィック混合ファイル
、ソフトウェアオブジェクトコード、スプレッドシート
ファイル、他のシステムとの会話式通信、または他のタ
イプのデータなど、データタイプが送信中においても急
速に変化し得るデータの圧縮に動的に適応できる改良デ
ータ圧縮方法および装置を提供る、ことである。

本発明の他の目的は、あらゆるタイプのデータまたはデ
ータタイプの分布は動的は適応可能な適応データ圧縮方
法を提供る、ことである。

本発明の他の目的は、ディスク駆動装置などのデータ記
録または記憶装置への使用も適切である改良データ圧縮
方法および装置を提供る、ことである。

本発明の他の目的は、８ビットマイクロプロセツサまた
はパケット用装置と共に有効に実施可能であり、１９，
２００ビット／秒の同期データ通信を処理可能な改良デ
ータ圧縮方法および装置を提供る、ことである。

本発明の他の目的は、データの送信または格納に大きな
遅れをもたらさずに、流れるデータを圧縮できる改良デ
ータ圧縮方法および装置を提供る、ことである。

本発明の他の目的は、圧縮性能が周期的に所定の時間間
隔またはキャラクタ数にわたって蓄積された統計を使用
して評価され、圧縮のレベルまたは程度がその評価に応
じて変更されて性能を最適にる、ような改良データ圧縮
方法および装置を提供る、ことである。

本発明の他の目的は、繰り返し連続キャラクタを圧縮表
現できる改良繰り返しキャラクタ状態を有る、改良デー
タ圧縮方法および装置を提供る、ことである。

本発明の他の目的は、代表的なＡＳＣＩＩテキストファ
イルの各キャラクタの送信データを平均約５ビットに減
少できるモデムにおいて使用されるデータ圧縮方法およ
び装置を提供る、ことである。

本発明の他の目的は、簡単であって８ビットマイクロコ
ンピユータ上に実施でき、双方向１９゜２００ビット／
秒同期チャネルを処理でき、Ｘ。

２５プロトコル機能を処理できるようなデータ通信方法
を提供る、ことである。

本発明の前記およびその他目的、特徴、および利点を、
添付図面および添付前を多照して以下に詳細に説明る、
。

（実施例） 図面を参照しながら実施例を説明る、。これら図におい
て同一番号は同一部品を示す９好適方法におけるデータ
圧縮は、データ通信の応用分野において使用される変復
調器（モデム）に適している。このモデムは、例えばモ
デム１０であり、通信回線または電話回線１２を介して
第２のモデム１５にデータを送信る、。ここに開示した
好適実施例はモデムに使用されているが、本発明はあら
ゆる種類のデータ圧縮分野に適している９例えば、大量
データ記憶、データバス圧縮、遠隔測定、映像／画像圧
縮、会話圧縮、地震データ圧縮などに適用できる。

本発明の好適実施例では、データ圧縮用の符号化器と、
それとは別個ではあるが並列の圧縮データ復号用復号器
とを使用る、。このため好適実施例に基づくモデム１０
は、それに付属して符号化テーブルＴ１を有る、。この
テーブルの詳細は後述る、。モデム１５には復号化テー
ブルＴ２が付属る、。このテーブルＴ２は、符号化テー
ブルＴ１と並列に保持されており、詳細については後述
る、。

次に幾つかの語の定義を行う３まず本明細書で使用る、
［アルファベットＪとは、情報を表すなめに使用される
キャラクタのセットを意味る、９例えばＡＳＣＩＩデー
タセットは２５６個のキャラクタからなるが、これを「
アルファベット」とみなす。同様にＥＢＣＤＩＣ規格も
「アルファベット」とみなす。

本明細書で使用る、「キャラクタ」の語は、文字、数字
、およびデジタルコードのみならず、２進コードに符号
化し得るあらゆる種類の情報要素を意味る、。はとんど
のキャラクタは所定の書式に基づいて符号化される。従
ってＡＳＣＩＩまたはＥＢＣＤＩＣ規格において、カン
マ、スペース、数字、および文字は全て「キャラクタ」
とみなす９同様に数値もキャラクタであり、特定の書式
に属さない純粋なデータの２進符号化表記もキャラクタ
である。

好適実施例における符号化テーブルＴ１および復号化テ
ーブルＴ２は、共にデータ配列として実現され、第２図
に示すように、マイクロコンピュータに付属したメモリ
に格納される。代表的にモデム１０は、本発明のデータ
圧縮を実行る、手峻を内蔵しており、データ圧Ｉｌ！１
回路２０を有る、。

このデータ圧縮回路２０は、モデム／コンピュータイン
タフェース回路２２に接続される。この回路２２は従来
のモデム回路であり、回線２３を介してコンピュータ等
の入力源からデータのキャラクタを受け取るための回路
要素を備え、前記データの項目の送信準備を行う、一般
にデータのキャラクタは８ビットバイトとして受信され
るやこの８ビットバイトは、データバス２５を介してデ
ータ圧縮回路２０に接続される。

データ圧縮した結果は、データバス２５を介してモデム
／電話インタフェース回路２４に提供される。このイン
タフェース回路２４は、圧鼾回路２０からデータを受け
取り、データｆ！−調整して電話回線１２等の通信回線
へのデータの直列伝送の準備をる、。好適実施例におい
て、圧縮回路２０からモデム／電話インタフェース回路
２４に提供されるデータは、後述る、方法において符号
化され、モデム／コンピュータインタフェース回路２２
から圧縮回路２０に与えられたキャラクタを表す符号が
提供される。

データ圧縮回路２０の好適実施例は、７８０マイクロコ
ンピユータ３０を備える。マイクロコンピュータ３０は
、モデム／コンピュータインタフェース回路２２から１
バイトのデータを受け取り、それを圧縮し、その符号化
された結果をデータバス２５に戻し、モデム／電話イン
タフェース回路２４に送り、そこから圧縮データを直列
伝送る、。

２８０マイクロコンピユータは、ザイログ社の製品であ
り８ビットマイクロコンピユータであって当業者に良く
知られているものである。従ってこのマイクロコンピュ
ータの詳細説明は省略る、。

それらについては製造会社から供給される説明書が参照
できる。

好適実施例においてマイクロコンピュータ３０と共に動
作る、他の構成要素は、プログラムメモリ３１を含む。

このプログラムメモリ３１は、マイクロコンピュータ３
０用のプログラムを格納し、好ましくはプログラマブル
リードオンリメモリ（ＰＲＯＭ）であってデータバス２
５に接続され、プログラムの制御下でプログラム命令が
マイクロコンピュータ３０に転送される。マイクロコン
ピュータ３０のデータバス３２は、ラインＡ０〜Ａ１５
からなり、１０グラムメモリ３１とマイクロコンピュー
タ３０との間に接続されている。このため、マイクロコ
ンピュータ３０からのアドレス信号は、公知の方法にお
いてプログラムメモリをアドレスできる。プログラマブ
ルタイマ・カウンタ回路３３は、データバス２５を介し
てマイクロコンピュータ３０に接続され、タイミングル
ーチンを実行る、。好適実施例において、回路３３はザ
イログ社製のｚ８０−ＣＴＣであって、４個の独立した
タイマ回路を有しており、−意の割込ベクトルを発生さ
せ、割込駆動タイミングルーチンの便宜をはかる。

符号化テーブルＴＩ（復元の場合は復号化テーブルＴ２
）は、ランダムアクセスメモリ（ＲＡＭ）３５内に格納
される。ＲＡＭ３５は、アドレスバス３２からアドレス
信号を受け取ると共に、データバス２５に対してデータ
信号を送受る、ように接続される。１実施例において、
ＲＡＭ３５は１０２４ｘ８ビットメモリであり、５１２
ｘ１６に配列されている。この特定の構成は、２５６キ
ャラクタのアルファベットを容易に可能にる、。つまり
、アルファベットの各キャラクタに８ビットが割り当て
られ、アルファベットの各キャラクタのカウント用に８
ビットが割り当てられ、１２ビット（３個の４ビットニ
ブル）が各キャラクタの圧縮コード用として演算される
。従ってこの構成は、提供される８１９２ビットのうち
２５６ｘ２８＝７１６８ビットを使用る、。当然ながら
このメモリのサイズは、アルファベットのサイズ、アル
ファベットを符号化る、ために使用されるビット数、お
よびキャラクタカウント数を示すなめに使用されるビッ
ト数に応じて小さくも大きくもできる。

好適実施例において、１２ビットの圧縮コードは、格納
されるのではなくマイクロコンピュータ３０によって実
時間で演算される。この構成により、ＲＡＭ３５の容量
は２５６ｘ１６＝４０９６でよく、これは２５６キャラ
クタのアルファベットの各キャラクタについての８ビッ
トと、アルファベットの各キャラクタのカウント用の８
ビットとを格納る、ためである。

マイクロコンピュータ３０に関連る、制御信号は、当業
者に良く知られているので第２図に示していない９本発
明の好適実施例は、入力データ流れの各キャラクタを圧
縮するために動作る、ので、符号化される各キャラクタ
は、モデム／コンピュータインタフェース回路２２によ
って圧縮用としてキャラクタ毎に提供されるものである
。圧縮されるキャラクタの存在は、ライン３６上の割込
（ＩＮＴ）がモデム／コンピュータインタフェース回路
２２から提供されることによって通知される。

同様に、本装置が復号モードで使用される場合、モデム
／電話インタフェース回路２４がＩＮＴ信号を提供る、
。モデム回路２２，２４からの各ｌＮＴ信号は、ワイヤ
ードＯＲ接続され、いずれもが割込を発生できる。この
割込信号は、マイクロコンピュータ３０に符号化用式た
は復号用のデータの存在を、各々の場合に応じてデータ
バス２５を介して通知る、。

モデムインタフェース回路２２，２４には、制御レジス
タ２７．２８が含まれる。これら制御レジスタは、モデ
ムインタフェース回路２２．２４とデータ圧縮回路２０
とのインタフェースの補助として使用される。制御レジ
スタ２７．２８は、マイクロコンピュータ３０とのイン
タフェースに必要な各種の制御信号を提供る、機能を有
る、。

例えば、マイクロコンピュータ３０が符号化状態にある
場合、このマイクロコンピュータ３０は、回路２２から
の符号化用のキャラクタの受信に対し肯定応答る、必要
がある。従ってマイクロコンピユータ３０は、ハンドシ
ェイク形式においてモデム／コンピュータインタフェー
ス回路２２からの割込に対して応答し、制御レジスタ２
７にビットを設定る、ことによりその割込に肯定応答る
、と共に、マイクロコンピュータ３０が「使用中」であ
ることを知らせる。マイクロコンピュータ３０が他の符
号化用キャラクタを受付可能になると、この「使用中」
ビットはクリアされ、次にモデム／コンピュータインタ
フェース回路２２が他の圧縮および最終送信用キャラク
タを提供る、状態となる。

同様に、制御レジスタ２８は、マイクロコンピュータ３
０とモデム／電話インタフェース回路２４との間のイン
タフェースの便宜をはかる０例えば、符号化され圧縮さ
れな１キャラクタが送信可能状態にある場合、マイクロ
コンピュータ３０は、モデム／を話インタフェース回路
２４の制御レジスタ２８にビットを設定し、該回路２４
に対して１コードが送信可能であることを通知し、その
コードがデータバス２５に置かれていて回路２４内の適
切な格納レジスタ（図示せず）にストローブされ得るこ
とを通知る、。

また本装置が復号モードに構成されている場合は、デー
タ経路は前記したものと逆になる。つまり、データは電
話回線１２から受信され、モデム／電話インタフェース
回路２４を介してマイクロコンピュータ３０に送られ、
復元され、モデム／コンピュータインタフェース回路２
２に供給され、回線２３を介してコンピュータに送られ
る。従って、電話回線１２を介して受信されるデータは
、モデム回路２４を介して提供され、８ビットバイトに
変換され、データバス２５を介して「復号状態」まなは
「復元状態」となっている圧縮回路２０に提供される。

制御レジスタ２８は、制揶レジスタ２７が行うものと同
様のハンドシェイク機能を提供し、モデム／′：４話イ
ンタフェース回路２４と圧ｌｆｔ／復元回路２０との間
のデータ通信の便宜をはかる。

次にデータ圧縮の好適方法および装置の理論および動作
を説明る、。一般に、好適なデータ圧縮方法は、マイク
ロコンピュータ３０用のプログラムとして実行される一
連のステップからなる。これらステップは次のとおりで
ある。

（１）アルファベットのキャラクタに関る、複数の項目
が入力された符号化テーブルＴ１をＲＡＭ３５内に与え
る。この符号化テーブルＴ１にはアルファベットの各キ
ャラクタに関る、カウント数も与えられる。好適実施例
におけるアルファベットはｎ＝２５６キャラクタを有し
、ＡＳＣＩＩデータセットからなる。この符号化テーブ
ルＴ１は、圧縮または送信モデム１０内に提供される。

またこのテーブルＴ１は、圧縮コードを演算る、ための
ものであり、その演算方法の詳細は後述る、。各圧縮コ
ードは所定の２ビットを有る、。しかしながら、好適実
施例においては、複数セットの圧縮コードが提供される
。このビット数２は、各圧縮コードのセット内では同一
であるが、各セット間では異なる。またこれら圧縮コー
ドの幾つかは、他よりも短い。最も短いコードは、アル
ファベットのキャラクタの符号化前の表現よりも短い。

本開示実施例において、３種類のセットの圧縮コードが
ある。つまり、４ビットコードと８ビットコードと１ｚ
ビットコードとである。従ってビット数２は、４，８．
または１２である。

（２）符号化用のデータの各項目は、順次のデータ流れ
で表現される。各項目は、一般に項目Ｘとして参照され
る。アルファベットキャラクタの一つによって表現され
るデータの項目Ｘが符号化用に提供されると、その提供
された特定のアルファベットキャラクタに対応る、圧縮
コードが、符号化テーブルにおける項目Ｘの順番と圧縮
レベルａとに基づいて演算される。

（３）このようにして選択された圧縮コードは、圧縮出
力として提供される。このコードは、モデム１０によっ
て電話回線１２を介して受信モデム１５に送信される。

（４）符号化テーブルＴ１における圧縮コードとアルフ
ァベットキャラクタとの関係は、周期的に調整される。

この調整は、他のキャラクタと比較して比較的頻繁に出
現る、キャラクタについてのみ行われ、特定のキャラク
タに関る、圧縮コードを変更る、ことによって行われる
。まなこの調整は、アルファベットの特定のキャラクタ
の符号化用に提供される所定の複数のキャラクタについ
ての出現頻度に基づいて行われる。これらキャラクタの
数は、符号化テーブルＴｌ内にキャラクタのカウント数
として示されるものである。この所定の複数のサイズは
ｋで表され、更新速度を上げるような限度数として選択
される。従って、符号化用に提供されるにキャラクタに
ついてキャラクタの出現頻度が変化すれば、より頻繁に
出現る、キャラクタが、符号化テーブルＴ１において、
より短い圧縮コードに対応ｔ＝ｔｃすされるようになる
。

前記したように、符号化テーブルＴ１は、アルファベッ
トのキャラクタと、それらキャラクタに対応る、カウン
ト数とを格納る、と共に、圧縮コードが演算される場合
はそれらキャラクタに対応る、圧縮コードも格納できる
。最初に、アルファベットの各キャラクタとそれらに対
応る、圧縮コードとは、初期順序配列に配置される。す
なわち、ａ個の４ビットコードが配列の開始端側に配置
される。またｂ個の８ビットコードと０個の１ｚビット
コードもある。圧縮コードとアルファベットキャラクタ
との関係の周期的な調整は、次のようなステップで実行
される。

（１）符号化テーブルＴ１において、各カウント数ＣＣ
が各アルファベットキャラクタ毎に保持される。

（２）データ項目Ｘが符号化用に提供されると、符号化
テーブルＴ１を使用して圧縮コードが演算式なは選択さ
れ、符号化用に提供された該キャラクタに対応る、キャ
ラクタカウント数ＣＣが増分される。

（３）そのキャラクタカウント数が増分されると、該更
新されたキャラクタカウント数は、配列中においてより
短いコードに対応付けされていると見なされる位置の所
定のキャラクタのカウント数と比較される。開示実施例
においてこの所定のキャラクタは、配列の開始端方向に
ｄ個の位置に配置され、このｄは好適実施例において１
６である。つ才り、更新直後の特定のキャラクタのカウ
ント数は、配列の開始端に近いより短いコードのある位
置の所定のキャラクタのカウント数と比較される。

（４）配列の開始端に近い所定のキャラクタのカウント
数が符号化直後のキャラクタのカウント数よりも少なけ
れば、符号化直後のキャラクタと所定キャラクタとの配
列中の相対位置が交換される。配列の開始端に近い所定
キャラクタのカウント数が符号化直後のキャラクタのカ
ウント数よりも少なくなければ、同様の比較が符号化直
後のキャラクタの位置に近付きながら各キャラクタカウ
ント数に対して行われる。より少ないキャラクタカウン
ト数が見つかれば、前記したような位置の交換が行われ
る９あるいは、ｄ個のカウント数との全比較が行われる
。これにより、より大きなカウント数を有る、キャラク
タが、配列中においてより短いコードに対応しているで
あろう位置に関連付けられる。

配列中において、特定の圧縮コードは特定の位置に対応
しており、キャラクタの位置を交換る、と、キャラクタ
とそれに対応る、カウント数とは配列中の別の位置に移
動されるので、そのキャラクタは、それよりも低いカウ
ント数を有る、キャラクタにそれまで関連していた圧縮
コードに対応る、ようになる。

圧縮コードとアルファベットキャラクタとの対応関係の
周期的な調整は、符号化された各項目について行われる
ので、より頻繁に出現る、キャラクタが配列の開始端の
方向に移動してより短いコードに関連付けられるように
なる。この移動は比較的徐々に行われる。これは１キャ
ラクタが１回につきｄ＝１６位置以上は移動しないから
である。

このなめ、比較および交換は部分的なものであり、マイ
クロコンピュータ上で容易に迅速に実行可能である。こ
れはごく少数の比較演算とデータ交換とのみが必要とさ
れるからである。

本発明においては、より短いコードに関連付けられるキ
ャラクタの数を最大にる、なめ、さらに別のステップが
実行される。これは圧縮コードの各セットのサイズの調
整を含む。つまりａ、ｂ。

Ｃの値を調整る、ものである。開示実施例において、ｂ
およびＣの値は、ａの関数である。まず好適実施例にお
ける配列は、所定数ａのアルファベットキャラクタが４
ビットコードに関連付けられ、ａの１６倍の数のキャラ
クタが１ｚビットコードに対応づけられ、残りのアルフ
ァベットキャラクタが８ビットコードに対応づけられる
。４ビットコードに対応づけられるキャラクタの所定数
ａによって示される「符号１ヒレベル」は、データの統
計が累積されるに連れて動的に変化し、出現の可能性が
高いキャラクタが４ビットコードを受け取ってより大幅
な圧縮を実現る、ようにる、。従って、４ビットコード
２８ビットコード、および１ｚビットコードによって表
されるキャラクタの数の各セットのサイズを周期的に調
整る、ステップが実行される。これは次のようなステッ
プである。

（１）復号用に提供される複数に個の項目について（好
適実施例ではに＝１２８）、所定の連続る、キャラクタ
のグループのキャラクタカウント数が合計されて複数の
［グループカウント数」が与えられる。好適方法におい
て、これらグループカウント数または合計数は、アルフ
ァベットの２５６個のキャラクタを１６個ごとのグルー
プに分割し１６のグループを提供る、ことによって求め
られる９つまり１６個のグループカウント数がある。

（２）次に、配列の終端側のグループのグループカウン
ト数と、配列の開始端にある単一のキャラクタのキャラ
クタカウント数とを順次に比較る、。最初に、終端のキ
ャラクタグループのグループカウント数と、開始端の最
も出現頻度の高いキャラクタのキャラクタカウント数と
を比較る、。

（３）最も短いコードである４ビットコードのセットに
おける項目数ａは、グループカウント数とキャラクタカ
ウント数とが一致る、まで増分される９この時、終端の
グループカウント数から配列の開始端に移動しながらそ
の処理が行われる９このように、最短のデジタルコード
に対応づけられるキャラクタセットのサイズは、出現頻
度の高いキャラクタをより多く含むように増加され、短
いキャラクタコードをより最適に使用る、ようにる、。

基本的に、これにより、より多くの短いコードがより出
現頻度の高いキャラクタに対応づけられるようになり、
より多くの長いコードが出現頻度の低いキャラクタに対
応づけられるようになる９好適方法において、３セット
のコードがあり、４ビ・ソトコードに対応づけられるａ
個のキャラクタを有る、セットは、そのサイズが０〜１
５個の間で変化し、最長のデジタルコードに対応づけら
れるＣ＠のキャラクタを有る、セットは、そのサイズが
０〜２４０個の間で変化る、。

前記したように、好適実施例におけるデータ比較方法は
、マイクロコンピュータ３０用のプログラムによって実
現される。以下に詳細に説明る、データ比較用の好適方
法は、マイクロコンピュータ３０用の一連のプログラム
命令によって実行される。以下の説明を読めば、当業者
はマイクロコンピュータ３０をプログラムして本発明の
目的を遂行る、方法を理解る、であろう、以下の説明に
おいては第３図〜第１６図も釡照る、。

（１）丈ず、アルファベットのｎ個のキャラクタが情報
の表現用として選択される。前記したようにこのアルフ
ァベットキャラクタは、ｎ個のキャラクタを含むいずれ
かの所定のセ・ソトである９好適実施例においては、Ａ
ＳＣＩＩキャラクタセット分使用る、９これは、そのセ
ットを使用る、データ通信が本発明の主要な有効＠域だ
がらである９好適実施例におけるアルファベットは、ｎ
＝２５６個の８ビットＡＳＣＩＩキャラクタを備える。

第３図はそれらアルファベットを示す９この図において
、キャラクタの前に付けられているカラット（力は、Ａ
ＳＣＩＩコントロールキャラクタを示し、キャラクタの
前に付けられている（ｖ）はＡＳＣＩＩグラフィック記
号を示し、キャラクタの前に付けられているプラス（＋
）はイタリック体ＡＳＣＩＩキャラクタを示す。

（２）これらキャラクタは、まずメモリ３５内においで
ある所定の順序で初期順序配列に配置され、テーブルＴ
１を形成る、。第３図において、キャラクタはＡＳＣＩ
Ｉデータセットの１６進表現の順序で配置されている。

ここに開示る、好適方法は、データ統計の変化に応じて
動的に適応る、ので、前記キャラクタを何等かの特定の
順序に配置る、必要はない、しかしながら、場合によっ
てはある種のデータが他よりも多く出現し得る。

例えば、ある環境においては、英語のテキストが多く発
生し得ることが分かる。このような場合は、出現確率の
高い順にキャラクタを並べ、最も出現頻度の高いことが
予測されるキャラクタを配列の開始端に配置し、出現頻
度の最も低いことが予測されるキャラクタを配列の終端
に並べる。このようにあらかじめ配置る、ことにより、
アルゴリズムを最もありえそうなデータ流れに迅速に適
応させることができる。

（３）次に、アルファベットキャラクタを符号化して圧
縮る、ために使用る、圧縮コードのセットを提供る、必
要がある。好適実施例においては、３セットのキャラク
タ符号化用の圧縮コードがある。すなわち、４ビットニ
ブル、８ビットバイト、または１２ビットである。一般
には、少なくとも第１セットのｐビット圧縮コードがア
ルファベットの幾つかのキャラクタの符号化用に提供さ
れ、少なくとも他のセットのｒビット圧縮コードがアル
ファベットの他のキャラクタの符号化用に提供される。

好適実施例において、第１のｐビット圧縮コードのセッ
トは、ｎ個のキャラクタのうちの第１の所定数ａ個のキ
ャラクタを符号化するために使用され、第２のｑビット
コードのセットはｎ個のキャラクタのうちの第２の所定
数す個のキャラクタを符号化る、ために使用され、第３
のｒビットコードのセットはｎ個のキャラクタのうちの
第３の所定数０個のキャラクタを符号化る、ために使用
される。この特定の状態においてａ＋ｂ＋ｃ＝ｎである
。これは、すべてのキャラクタがこれら３種類の異なる
コードセットのいずれかで表現されなければならないか
らである。好適実施例において、２は三つの値（ｐ＝４
．ｑ＝８．ｒ＝１２）のいずれかを取ることができる。

また、一般には、少なくとも２セットの長さの異なる圧
縮コードがある。ここで、第１のａｒｍのキャラクタの
セットはｐビットコードを有し、第２の０個のキャラク
タのセットはｒビットコードを有る、。好適実施例にお
いては３セットの圧縮コードがあるが、より多くのセッ
トを使用る、ことも可能である。

１実施例において使用される圧縮コードは、添付第１表
〜第■表に示す通りであり、６段階の圧縮レベルを例示
している。これら表において、ＩＮで示される欄は、テ
ーブルＴＩの配列内におけるキャラクタの位置を表現し
、０〜ＦＦまでの１６進表現の位置識別子として示され
ている。配列内におけるこれら位置に対応る、圧縮コー
ドは。

ＯＵＴの桐に示されており、やはり１６進表現である。

好適実施例において、添付衣に示した圧縮コードは、提
供されるキャラクタの符号化表における位置に基づいて
実時間で演算される。この実時間演算の方法の詳細は後
述る、。これらコードは、あらかじめ演算して添付表仁
示すような形式でメモリに格納してもよい。

またこれら圧縮コードは、コードの固定テーブルではな
い。これらコードは、圧縮レベルの関数として動的に変
更されるものである。これに関し、第１表においては、
ａ＝１の圧縮レベルが示されている。すなわち、１個の
キャラクタのみが４ビット圧縮コードを与えられる。こ
のコードはＯＵＴの第１カラムの１６進数Ｏである。開
示方法に基づき、１ｚビットコードの数はｃ＝１６ａ＝
１６である。これら１ｚビットコードは、第１表の終端
の０ｔＪＴカラムに見られ、１６３１！数ＦＦ０〜ＦＦ
Ｆの範囲にある。残りのコードは８ビットコードであっ
てその数はｂ＝ｎ−ａ−ｃ＝２３９であり、カラム１の
１６進数１０から最終カラムの１６進数ＦＦの範囲にあ
る。

圧縮レベルａ＝０は、好適実施例における一極端を表す
、この場合、全データは８ビット圧縮コードで表現され
、圧縮（または復元）は行われない。これは純粋なラン
ダムデータには最適である。

他の極端は、ａ＝１５の圧縮レベルであり、１５個のキ
ャラクタが４ビット圧縮コードに対応づけられる。これ
の状態は第■表に示すように、ａ＝１５のキャラクタが
０〜Ｅの範囲の４ビットコードに対応づけられる。この
結果ｃ＝１６ａ＝１６（１５）＝２４０のキャラクタが
ＦＩ０〜ＦＦＦの範囲の１ｚビットコードに対応づけら
れ、１個のキャラクタのみがＦＯの８ビットコードに対
応づけられる。

より頻繁に起こり得る圧縮レベルは第７表に示すａ＝１
２のレベルである。この圧縮レベルは、ある程度のデー
タ統計を累積した後に発生る、可能性があり、データ流
れ中に再出現る、キャラクタのパターンを処理した後に
発生し得る。第７表においては、１２のキャラクタが０
〜Ｂの範囲の４ビットコードに対応づけられている。従
ってＣ−１６ａ＝１６　（１２）＝１９２のキャラクタ
がＦ４０〜ＦＦＦの範囲の１２ビット圧縮コードに対応
づけられている。残り２５６−１２−１９２＝５２のキ
ャラクタは、Ｃ０〜Ｆ３の範囲の８ビットコードに対応
づけられる９ 第１表〜第■表を見て分かるように、与えられた圧縮コ
ードの翻訳は、圧縮レベルａの関数となる。すなわち、
圧縮レベルと、圧縮コードを表現る、１２ビットまでの
データとが与えられれば、テーブル中の位置（および対
応る、アルファベットキャラクタ）は一意的に同定され
る。つまり、すべての圧縮コードは即座に復号される。

これは、圧縮レベルａが４ビットコードを有る、キャラ
クタの数を決定し、ａの値が８ビットコードおよび１ｚ
ビットコードを有る、キャラクタの数すおよびＣの値を
決定る、からである。このため、第７表のように圧縮レ
ベルが１２であれば、第１のＯＵＴカラム中の最初の１
２個の０〜Ｂの１６進数は各別個のコードを表す。Ｃが
現れればそれは少なくとも別の１個の１６進数を伴うこ
とになる。

これは４ビットコードの数がＢまでであるからである。

同様に、次の５２個の８ビットコードを有る、キャラク
タが第７表のＦ３で終了る、と、次からは必ず３個の１
６進数すなわちＦ２Ｏ等を必要とる、１ｚビットコード
が続く。

（４）これら初期パラメータを確立した後、次のステッ
プは、アルファベットキャラクタで表現される符号化用
の順次入力情報の流れに圧縮コードを与えることである
。

（５）符号化用に順次に提供されるこの入力情報の流れ
の各キャラクタは、項目ｘ′ｃ表されるが、この項目Ｘ
に対して次のようなステップが実行される。

（ｉ）符号化テーブルＴ１を使用して、項目Ｘに対応る
、キャラクタの配列中の相対位置の関数として圧縮コー
ドが演算または選択される。基本的にこの処理は、テー
ブルＴ１においてインデキシング、ハツシング、または
順次検索を行い、テーブルＴｌ中に項目Ｘを表現る、キ
ャラクタと同一のキャラクタを見つける。これにより圧
縮コードが一意的に同定される。例えば、第３図に例示
したデータの流れ’　Ｔｈｅ　Ｈａｙｅｓ　Ｃｏｓ＋ｐ
ｒｅｓｓｉｏｎ　、　、　、　Ｊは、キャラクタ「Ｔ」
で始まっている。このキャラクタは、テーブルＴ１の第
６カラムの上から第５番目のキャラクタであり、ＩＮカ
ラムの１６進位置５４に対応る、。従って、このキャラ
クタを符号化る、ため、１６進位置５４に対応る、圧縮
レベルに関る、圧縮コードが選択または演算されて圧縮
出力として提供される９ 前記したように、好適実施例においてはこの圧縮コード
はマイクロコンピュータ３０によって実時間で演算され
る。実時間での演算は好ましいものである。もし実時間
での演算をしないと、１６の圧縮コードテーブルが必要
となり、それらの各々がＲＯＭまたはＲＡＭに格納され
るので、１６ｘ２５６ｘ８＝４０９６バイトの記憶装置
が必要となる。あるいは単一の圧縮テーブルを設けるこ
ともできるが、そのテーブルはａの値が変化る、たびに
更新しなければならない。

好適実施例において圧縮コードの演算用に使用される方
法は次の通りである。供給されたデータ項目Ｘの位置を
テーブルＴｌ中に見つける。これによりその圧縮レベル
が容易に同定される。Ｘの位置をｐ　（ｘ）とし、これ
がａよりも小さければ、圧縮コードはｐ（ｘ）に等しい
４ビットニブルである。例えば、第■表において、キャ
ラクタが第ｌのＩＮカラムの位置４を占めれば、圧縮コ
ード４が選択される。

ｐ　（ｘ）が（２５５−１６ａ）より大きければ、１６
進数Ｆに８ビット数ｐ　（ｘ）が続く３ニブルコードが
送られる９例えば、第■表においてはａ＝８であり、第
６のＩＮカラムにおける位ｒ［Ａ。

を占めるキャラクタは、圧縮コードＦＡＯを受け取る。

あるいは２ニブルコードｐ（ｘ）＋１５ａが送られる９
例えば、第■表の第５のＩＮカラムの位置６０を占める
キャラクタは、（６０＋１５　（８））＝Ｄ８の１６進
圧縮コードを受け取る。これらの演算はすべてマイクロ
コンピュータ上での実行が迅速で容易である。これは１
６による乗算が４回の友シフト演算であり・、１５によ
る乗算が４回の甜シフトおよび元のバイトの減算だがら
である。

第３図において、圧縮レベルは４であり、これは第１表
の圧縮コードに対応る、。第３図に明らかなように、キ
ャラクタ「Ｔ」によってｑビットコードが選択され、そ
れが出力として提供される。

第３図に示すテーブルは、適切な第１表のコードを示し
ていない。第１表は圧縮レベル４用のコードテーブルで
あるが、この表において第３図の配列中のＴ（１６進表
現で５４）のキャラクタ位置に対応る、１６進コードが
、演算式なは選択によって１・６進圧縮コード９０とな
る。つまり、符号化る、項目の適切なキャラクタ位置が
第３図の例示テーブルＴｌ中に見つかると、それに対応
る、圧縮コードが第１表から演算または選択される。

（ｉｉ）入力情報の流れの各項目に対る、次のステップ
は、その入力情報の流れの特定の項目を表現る、アルフ
ァベットキャラクタに関る、カウント数を増分る、こと
である。このキャラクタカウント数はＣＣで表されてお
り、そのキャラクタの出現頻度のデータ統計を維持る、
手段となる。

（ｆｉｔ）キャラクタカウント数ＣＣが増分されると、
そのカウント数は、配列の開始端方向の所定の範囲にあ
る各キャラクタに付随る、キャラクタカウント数と比較
される。この比較は、配列中の所定数ｄの位置に対して
実行される。ここでｄはあらかじめ設定される数であり
ｎよりも小さい。

好適実施例において、前記比較は配列中の１６箇所まで
実施され、それ以上は行われない。これは、処理時間の
遅延を大きくさせないためである。マイクロコンピュー
タ３０用のクロック周波数を２゜５ＭＨｚとし、ＣＰＩ
Ｒ命令（ｆ＆大２１クロックサイクルを必要とる、比較
、増分、および繰返し命令）を使用る、とすれば、最大
１６メモリ箇所の検索および比較は、本発明に好適であ
る２８０マイクロコンピユータを使用した場合、約１３
５μｓ以内に実行できる。処理される各キャラクタにつ
いては他の命令も実行される必要があるが、キャラクタ
カウントに関連した演算は、各キャラクタについての処
理時間の大部分を占める。従って、本発明が適用される
モデムの目標ビット速度１９．２００ビット／秒（１９
２０キャラクタ／秒に相当）は、処理される８ビットキ
ャラクタ当り約４１６μｓの平均時間に相当し、大きな
影響を受けない。もちろん、さらに早いマイクロコンピ
ュータを使用すれば、その影響はさらに小さくなる。

従って、第３図において、キャラクタＴについてのキャ
ラクタカウント数ＣＣは、第６カラムのＴの真上のキャ
ラクタから第５カラムのキャラクタＤまでの各キャラク
タのカウント数と比較される。

（ｉｖ）キャラクタカウント数ＣＣが、配列の同始端に
近い所定範囲内のｄ個のキャラクタのうちあるキャラク
タのカウント数より大きいか等しければ、交換が行われ
る０項目Ｘに対応る、キャラクタと、それよりも小さい
か等しいキャラクタカウント数を有る、配列中の開始端
に近い位置のキャラクタとの配列中における相対位置は
、単に交換され、第４図に示すような結果が得られる０
例示したデータ流れの第１のキャラクタの後、キャラク
タＴのみがキャラクタカウント数を有しており、前記交
換の結果キャラクタＴとＤとの位置が対で交換される。

キャラクタの出現に応じてキャラクタカウント数を増分
させ、そのキャラクタカウント数と配列中の所定の低い
範囲内の各キャラクタのカウント数とを比較る、ことの
効果は、部分的にソートる、ことでめり、除々に特定の
キャラクタの出現の可能性を降順に並べることである。

この部分的ソートは、所定範囲内に限定されており完全
なソートではないが、各キャラクタに対して比較が行わ
れるので、テーブルは徐々にソートされる。さらに、あ
るキャラクタがより頻繁に出現すれば、そのキャラクタ
はテーブル内においてより頻繁に再配置されることにな
り、これらキャラクタに対る、有効ソート率はより大き
くなる。これは当然、４ビット圧縮コードを出現頻度の
高いキャラクタに迅速に割り当てる結果となる。

前記の処理は符号化用に提供される各キャラクタについ
て実行される。第４図において、図示の対の交換が行わ
れた後、キャラクタＴは第５カラムの第５番目の位置に
対応づけられており、第■表の４４のＩＮ（ｆＬ置に対
応し、８０のＯＵＴ圧縮コードを受け収る９このコード
が、次にキャラクタＴが出現した場合に与えられる。ま
たキャラクタＤは、第６カラムの第５番目の位置に対応
しており、これは第■表の位置５４に対応し、圧縮コー
ドとして９０を受け取る。

次に第５図および第６図を参照る、。これらの図は、例
示したデータ流れの第２キャラクタおよび第３キャラク
タの後のテーブルＴ１の状態を示す。例示データ流れの
第２キャラクタ「ｈ」の後、このキャラクタｈに関る、
キャラクタカウント数は増分される。キャラクタｈの処
理後キャラクタカウント数を比較る、と、ｈのカウント
数はＷのカウント数よりも大きいので、第５図に示すよ
うに位置の交換が行われる。同様に、例示したデータ流
れの第３キャラクタｒ　ｅＪの処理後、ｅのカウント数
は増分され、第５図におけるしのカウント数と比較され
る。ｅのカウント数はＵのカウント数よりも多いので、
ｅとＵどの位置は交換され、第６図に示すような配置と
なる。

次に第７図と第８図とを参照る、９これらは例示したデ
ータ流れの第１行目の終端前後のテーブルＴ１の状態を
示す９これらの図から分かるように、データ統計は有効
な方法で累算されており、キャラクタ位置の移動は有効
に行われている０例えば、例示したデータ流れの第１行
目の終端において、スペースキャラクタｓｐは、最も出
現頻度の高いキャラクタであり、第１行目において９回
出現している。次に頻度の高いキャラクタは０であり、
６回出現している。また第７図および第８図から分かる
ように、第１行目の最後のキャラクタａは、そのキャラ
クタカウント数が増分されるのに応じて、前記した通り
の方法で配列中の開始端に向かって移動を続ける。

第２行目の終端においては、第９図および第１０図に示
すように、テーブルＴ１は著しくソートされており、各
キャラクタは出現確率の高い順にはっきりと配置されて
いる。第９図および第１０図の時点において、初期の符
号化レベル４は、最も出現頻度の高いキャラクタの四つ
のみを４ビットで符号化る、だけであるが、このレベル
はその丈ま残っている。このため、ｓｐ、ｓ、ｅ、およ
びｔのキャラクタだけが４ビットで符号化されるだけで
ある。そしてこの例示したデータの流れにおいて出現る
、残りのキャラクタの実質的にすべてが、８ビットで符
号化される。

次に好適実施例において、符号化レベルを周期的に変更
る、ステップを詳細に説明る、。この「符号化レベル」
の語は、最も短いコードに対応づけられるキャラクタの
数ａの値を意味しているに過ぎない。符号化レベルを変
更る、ことにより、最短コードに対応づけられるキャラ
クタの数を最大にる、ことができる。まず、配列は所定
数ａの４ビットコードと、ｂ＝１６ａの１ｚビットコー
ドと、ｃ＝ｎ−ａ−ｂの８ビットコードとでキャラクタ
があらかじめ設定される。この符号化レベルは、データ
統計が累積されるに従って動的に変更され、出現確率の
高いキャラクタが多いほど４ビットコードを受け収るキ
ャラクタが増えるようになる。

従って、４ビットコード、８ビットコード、および１ｚ
ビットコードで表現されるキャラクタのセットのサイズ
を周期的に調整る、ステップが収られる。好適実施例に
おいて、この周期調整は、所定数にのキャラクタの後に
実施される。ここでｋは、好適実施例において１２８で
ある。しかしながら、符号化レベルの調整は、必ずしも
所定数のキャラクタの後や所定時間後に実施る、必要は
なく、重要な概念は、データの実際の圧縮、伝送。

格納中において、圧縮されるデータに関る、統計が分析
されて、符号化機構をデータ統計の変化による確率に動
的に適応させることである。この周期的な調整は、時間
の関数、処理キャラクタの数の関数、または当業者に知
られている他の方法によって処理中に実施される。

好適方法において、この符号化レベルは、多数ａ、ｂ、
ｃの相対値を調整る、ことによって変更される。ここで
多数すおよびＣはａの関数である。

符号化レベルを調整る、好適ステップは次の通りである
。

（ｉ）まず、キャラクタの連続る、グループのキャラク
タ数を求め、複数の「グループカウント数」を発生させ
る。好適方法において、各ｍキャラクタを有る、連続る
、グループを合計し、ｎ／ｍ＝＝２５６／１６＝１６グ
ループのグループカウント数を得る。第１１図に示すよ
うに、好適方法においてこのグループカウント数は、配
列を直線的にではなく２次元的に見た場合、各１６キャ
ラクタを有る、各カラムの合計に対応る、。

（ｉｉ）各グループのグループカウント数は、テーブル
Ｔ１における最も右側の位置から開始して、配列の開始
端から始まる連続の各キャラクタのキャラクタカウント
数と比較される。すなわち、第１１図における最も右側
のグループのカウント数は、最も出現頻度の高いキャラ
クタｓｐのカウント数と比較される。最も右側の次のグ
ループは、次に出現頻度の高いキャラクタｅと比較され
、このようにして順次に比較が行われる。（第１１図に
おいては、右から第１０番目のカラムまで全てのグルー
プカウント数はゼロであるので、これらのグループのカ
ウント数は図示していない。）数字的に示せば、この方
法は、グループ（ｎ　／　ｍ　）−ｉ−１についてのグ
ループカウント数とキャラクタｊについてのキャラクタ
カウント数と比較る、。ここでｉはゼロで始まるグルー
プカウント数の整数指標であり、ｊは配列内の開始端か
らゼロで始まる整数指標である。０〜１５のグループが
ある、 （ｉｉｉ）グループカウント数が比較されたキャラクタ
カウント数よりも小さければ、左方向に次のカラムまた
はグループのカウント数が次のキャラクタカウント数と
比較される。詳細に説明すれば、グループ（ｎ／ｍ）−
ｉ−１のグループカウント数がキャラクタｊのキャラク
タカウント数よりも小さければ、ｉおよびｊは増分され
、前記比較ステップが繰り返される。これら比較ステッ
プと増分ステップとは、グループカウントとキャラクタ
カウントとが一致る、まで繰り返される。

（ｉｖ）グループカウントが特定のキャラクタのカウン
ト数と一致る、と比較は終了し、符号化レベルが、前記
一致が見つかるまでに行われた比較の数の関数として確
立される。ＰＡえば、第１１図に示すように、右から第
８番目のカラムのグループカウント数はゼロであって、
これはキャラクタ−Ｈのキャラクタカウント数に等しい
。この時点で、−Ｈに続くキャラクタの出現頻度は、比
較されたグループ内のどのキャラクタの出現頻度ともほ
ぼ同じであると見なされる。このため、好適方法におい
て、この時点で比較が終了し、符号化レベルは、グルー
プカウントとキャラクタカウントとの間に一致が見られ
た点の直前の位置に確立される。

すなわち、第１２図において説明すれば、新しい符号化
レベルミニ８キャラクタが確立される。

これは、この時点から４ビット符号を受け取るキャラク
タセットの最後のキャラクタである一Ｍが、第１１図に
示したグループカウントとキャラクタカウントとの一致
点よりも配列内において１キャラクタ分、低い位置にあ
るからである。第１２図において、このレベル演算の後
、キャラクタ間の位置交換が続行され、ＡＳＣＩＩ表現
でラインフィ〒ドキャラクタを意味る、キャラクタ“Ｊ
がキャラクタ間Ｈと位置交換されている９ 第１２図に示すように、新しい符号化レベルａ＝８の確
立に応じてさらに別のステップが実行される。まず、ａ
の演算の結果、ｃ＝１６ａ＝１２８キャラクタが１２ビ
ット圧縮コードに対応づけられ、ｂ＝２５６−ａ−ｃ＝
１２０キャラクタが８ビット圧縮コードに対応づけられ
る。

第１２図に示すように、レベル演算の後、キャラクタカ
ウント数は１／２（切下げ）にされる。

新しいにキャラクタの開始時にテーブルＴ１を完全にリ
セットる、のではなく、また以前のにキャラクタの記録
をすべて保持る、のでもなく、好適方法においては以前
の記録の一部を保持る、のである。これは、各所しいに
キャラクタのセットの開始においてキャラクタカウント
数を半分にる、ことによって実施される。これにより、
以前のキャラクタの記録の一部を保持る、と共に、テー
ブルを大きく変更る、ことなく、変化る、データ統計へ
の迅速な適応が阻害されないという二重の機能を提供る
、。好適方法においてはキャラクタカウント数を半分に
したが、当業者には明らかなように、以前の記録の保持
量および変化る、データ特性への適応速度は、キャラク
タカウント数を減少させる量によって調整し得る。キャ
ラクタカウント数を半分に減らすことは、好適実施例に
おいて実行が都合がよい、これはカウント数を格納して
いる各メモリ箇所におけるシフト演算を行うだけで良い
からであり、この処理は好適なＺ８０マイクロコンピュ
ータで容易に実行できる。

第１５図および第１６図は、第２レベルの再演算を示す
。これは次のに＝１２８キャラクタが収られた後に実行
される。すなわち、例示したデータ流れの第５行目の語
ｒｉｎｊの後に実行される。

第１５図に示すように、テーブルＴ１の右側から開始し
て左方向へのグループカウントと、最も出現頻度の高い
キャラクタｓｐから開始して配列の下方向へのキャラク
タカウント数とを比較る、場合、キャラクタｌ（キャラ
クタカウント数４）とグループ３（左から４番目のグル
ープであってグループカウント数４）との間でカウント
数に一致が見られる。この結果、新しい符号化レベルミ
ニ１２キャラクタが確立され、第１６図の第１カラム内
のＭよりも低位の全てのキャラクタが、それ以ｆ＆４ビ
ット圧縮コードを受け収るようになり、第７表に基づい
てその選択が行われる。これに対応して、１９２のキャ
ラクタが１２ビット圧縮コードな受け取り、残りの５２
のキャラクタが８ビットで符号化される。

復元のために基本的に必要なことは、第１図に示したモ
デム１５などの受信端末における並列復号化テーブルＴ
２を保守る、ことである。受信される符号化されたデー
タを復元る、ために、この復号化テーブルは、第３図に
示すように同一の初期テーブルで開始される９次に前記
した符号化テーブルＴ１の保守ステップと全く同一のス
テップが復号化テーブルＴ２についてデータ項目ごとに
行われる。ただし処理される項目は符号化されたキャラ
クタであり、その目的は復号化出力としてアルファベッ
トの適切なキャラクタを提供る、ことである。

本発明に基づいて圧縮されたデータを復元る、方法は、
通信回線の他端側において一部に実行される。符号化の
際の第１のアルファベットの複製であるｎｄ個のキャラ
クタの第２のアルファベットが並列に提供される。ここ
でｎｄは第１のアルファベットにおけるキャラクタ数ｎ
と同一であり、添字ｄは演算が復号装置または復元装置
において行われることを意味る、。第２のアルファベッ
トのｎｄ個のキャラクタは、第１のアルファベットの配
列と同一の初期順序配列において配置される。

圧縮コードに基づいて符号化された順次データの流れは
、通信回線を介して受信される。次に圧縮コードに対応
る、アルファベットキャラクタが参照される９提供され
る出力は、圧縮コードに対応る、アルファベットキャラ
クタである。ｉ後に、第２のアルファベット用の配列の
順序は、前記した送信モデムまたは符号化モデムにおけ
るアルファベットに対る、ものと同様の方法で維持され
る。

従って、符号化される入力情報の流れにおけるキャラク
タの出現頻度が変化る、と、第２のアルファベット中の
より出現頻度の高い対応キャラクタは、符号化配列と平
行して復号化テーブルの開始端方向に移動る、ようにな
る。

好適実施例において、これには、圧縮コードを演算る、
ために使用したものと逆のアルゴリズムが使用される。

この逆アルゴリズムは、受信端におけるマイクロコンピ
ュータ用のプログラムとして実現されるが、これについ
て次に説明る、。４ビットニブルのデータは、最小パケ
ットサイズであり、Ｎ１は第１の受信ニブルを表し、Ｎ
２は第２の受信ニブルを表し、Ｎ３は第３の受信ニブル
を表す。また、ＮｌＮ２という表現は、１６＊Ｎ１十Ｎ
２を簡潔に示すものである９復号用のステップは次の通
りである。

Ｎｌが現在の圧縮レベルａよりも小さい場合、出力キャ
ラクタは、テーブル下２内の位置Ｎｌにあるキャラクタ
である９そうでなければＮ１は記憶されて装置はＮ２の
到着を待つ。

ＮｌＮ２が２５６−ａよりも小さければ、出力キャラク
タは、テーブル下２内の位置（ＮｌＮ２−１５＊ａ）の
キャラクタである。そうでなければＮ１およびＮ２は記
憶されて、装置はＮ３の到着を待つ。

第３のニブルが受信されると、Ｎ１は放棄されて（常に
Ｆである）、Ｎ２Ｎ３の位置にあるキャラクタが復元出
力として与えられる。

このように、データが復号用に提供されると。

この提供されたデータ項目が表す特定のデジタルコード
に対応る、キャラクタがテーブルＴ２から選択される。

復号化テーブルＴ２から選択されたキャラクタは、復号
出力として提供される。符号化テーブルと同様の方法で
、配列中のコードとアルファベットキャラクタとの位置
関係は、キャラクタが復元されてから、キャラクタの出
現頻度の間数として周期的に調整される。従って符号化
テーブルと同様の方法で、複数のキャラクタについての
復号されたキャラクタの出現頻度が変化る、と、より頻
繁に出現る、キャラクタは、符号化テーブルにおけるコ
ードと平行してより短いコードに対応づけられる。

復号器においては符号器と同一方法を実行しなければな
らず、しかもこれを同期して行い適切な動作を実現しな
ければならない９同期動作を確実にる、ため、次のよう
な動作手順が符号器と復号器とによって実行される。（
１）１キャラクタがテーブルＴＩに基づいて符号化され
て送信モデムによって送信され、（２）送信モデムはテ
ーブルＴ１を更新し、（３）受信モデムは受信キャラク
タをその時点のテーブルＴ２に基づいて復号し、（４）
受信モデムはテーブルＴ２を更新る、。

リセット用の追加手段を設けて、符号器と復号器による
動作が確実に同期して開始されるようにる、。好適実施
例において、余り使用されないＡＳＣＩＩキャラクタコ
ードを透過フラグまたはエスケープキャラクタとして使
用る、と共に、複数の制御コードを提供る、。これらコ
ードの一つがリセット用に使用される。準備期間中にお
いて、送信モデムは、そのテーブルを既知の初期状態に
リセットし、次にリセットキャラクタを送信る、。

これにより受信モデムは、そのテーブルＴ２をテーブル
Ｔ１と同一の初期状態にリセットる、。

リセットまたは他の理由により、データ圧縮回路から復
元回路に制卸情報を送信る、必要がある。

好適実施例において、制振情報はフラグバイトを使用し
て送信される。このフラグバイトは、開示実施例におい
て１６進数のＦＡが使用される。このバイトは、制９ｆ
機能が必要の場合に出力流れに挿入される。このフラグ
バイトには、常に副脚情報を有る、フラグコードバイト
が続く。次に説明る、一掃（フラッシュ）動作は、フラ
グバイトを挿入る、前に必ず実行る、必要がある。

好適実施例において、３個のフラグコードが提供される
が、それ以上または以下の数を使用してもよい。これら
３個は、無動作（ｎｏ−ｏｐ）コード、Ｄ−フラグコー
ド、およびリセットコードである。このｎｏ−ｏｐコー
ドは無動作を意味る、コードであって一掃動作に使用さ
れる。Ｄ−フラグは、データ流れ中にフラグバイトを保
持る、ためのコマンドである。代表的なデータ流れにお
ける各２５６バイトに約１個が、フラグバイトとして定
義されたバイトである可能性がある。デー夕が失われな
いようにる、なめ、圧縮回路はこれらバイトを認識して
、各バイトの後に１個のＤ−フラグを挿入る、ことによ
り復元回路に対してそのフラグバイトをデータ流れ中に
残すように知らせる必要がある。リセットコードは当然
、テーブルを初期状態にリセットするために使用される
。

もちろん本発明においてフラグバイトは任意のものであ
る。特別のフラグバイトを持つことは、送信されるデー
タ量を約０．４％増加させるが、それにより追加される
機能は都合の良いものである９ 好適方法は、一連の繰り返しキャラクタが送信または格
納されるデータ中に出現した場合に追加の圧縮を行うス
テップを備える。当業者には明らかなように、一連の繰
り返しキャラクタ内には冗長データが出現る、ことが多
い。特にある種の情報ファイルの通信においてそれが出
現る、３例えば、ある種のスプレッドシートファイルは
、そのスプレッドシート内の空領域を表す一連の空キャ
ラクタまたはゼロキャラクタを含むことが多い。

連続る、繰り返しキャラクタを処理る、ために使用され
る従来の圧縮方法の一つは、フラグキャラクタを送信る
、ことからなる。このフラグキャラクタは、繰り返し状
態の入口を意味る、ものであり、それに続いて特定のキ
ャラクタの繰り返し数を示す数が送信される３ 好適実施例では、繰り返し状態において新規な追加の圧
縮を実現る、。この方法では、同一キャラクタが３回連
続して出瑣した後に符号器よび復号器を自動的に繰り返
し状態に入らせる９３個の同一のキャラクタの後には、
常に数または追加繰り返し状態を示す信号または記号を
発生させる。

次に、繰り返しキャラクタの連続の終端に来るまで、ま
たはさらに１５個の繰り返しキャラクタが受信されるま
で、またはストリームモードにおいてタイミング信号が
保留データを終了させる才でデータは送信されない。

好適方法において、４ビットカウントニブルを使用して
繰り返しキャラクタの出現回数を表す記号を表現る、。

この４ビットニブルの１６進表現は、０〜Ｆの範囲で変
化し得る。Ｆは１５個の追加のキャラクタと繰り返し状
態の続行との両方を意味し、現在のカウントニブルの後
に追加のカウントニブルが続くことを意味る、。

例えば、第１７Ａ図において、例示した入力データの流
れは、一連の３個のｅの繰り返しを含む。

これら３個の繰り返しキャラクタが出現る、と、繰り返
し状態が自動的に符号器および復号器において発生され
る。そしてカウントニブル記号がその次のキャラクタと
して期待される。従って、送信される圧縮されたデータ
流れは、３個のｅの後に繰り返し記号が続いており、こ
の繰り返し記号は繰り返し数を表す、これは最初の３個
のキャラクタに続く０〜１５の数を表す、この数が１５
（１６進数のＦ）であれば、その繰り返し状態はさらに
続行る、。さもなければ繰り返し状態は、受信側におい
て繰り返しキャラクタの指示数が再現された後、終了る
、。第１７Ａ図の場合、合計３個の繰り返しキャラクタ
があるので、繰り返し記号はＯである９ 別の例として第１７Ｂ図を説明る、。繰り返し状態に入
った後、最初の３個のｅの後に別の３個のｅキャラクタ
がある。従って、送信される圧縮データの流れは、３個
のｅと、それに続く繰り返し記号３とであり、この繰り
返し記号３は最初の３個のｅの後に別の３個のｅがある
ことを示している。

１５個の追加キャラクタまで一つの繰り返し記号または
コードで表すことができる。これを越える数は、他の繰
り返しコードが求められる。好適方法において、１６進
キャラクタＦは、１５個の繰り返しの発生と追加の繰り
返し記号が予測されることを示すものである。第１７Ｃ
図において、最初の３個のｅに対して繰り返し状態に入
ると、追加の１５個のｅキャラクタがある９従って、送
信される圧縮データの流れは、３個のｅと、それに続く
繰り返し記号Ｆ（別の１５個のｅキャラクタが出現る、
ことを示す）と、それに続く第２の繰り返し記号０から
なる９この０は、もちろん、追加の１５個のキャラクタ
の連続の後に追加の繰り返しキャラクタは出現しないこ
とを意味る、。

第１７Ｄ図において、一連の１８個の追加キャラクタが
最初の３個のキャラクタの後に続いている。これにより
、圧縮データの流れは、最初の３個のｅと、それに続く
第１の繰り返し記号Ｆであって第１の１５個のキャラク
タと第２の繰り返し記号が続くことを意味る、記号と、
それに続く第２の繰り返し記号３であってデータの流れ
における最終の３（ｌＨのキャラクタを表す記号とから
なる。

最後に第１７Ｅ図は、連続る、繰り返し記号によって、
所望数の連続キャラクタを表し得ることを示す。第１７
Ｅ図の例において、追加の３２個のキャラクタの連続が
最初の３個のキャラクタに続く。好適方法において、こ
のデータの流れは。

繰り返し状態を発生させる３個のｅと、第１の１５個の
キャラクタと追加の繰り返し記号が続くことを意味る、
第１の繰り返し記号Ｆと、次の１５個のキャラクタとさ
らに別の繰り返し記号が続くことを意味る、第２の繰り
返し記号Ｆと、合計３２個のキャラクタのｊｔｆ＆の２
個を収り上げるための最終繰り返し記号２とからなる。

以上説明したように、ｍ個の繰り返しキャラクタの連続
を有る、入力データの流れを圧縮る、好適方法は、繰り
返しキャラクタの所定数ｎ回の出現を検出る、ことによ
って繰り返し状態に入り、所定数ｎ回の繰り返しキャラ
クタを表すデータを送信し、その直後に前記ｎ回の後に
続く繰り返しキャラクタの出現数０を表す符号化された
第１の記号を送信る、ことからなる。ここに開示した好
適方法において、ｎとＯとの合計はｍである。

繰り返しキャラクタ列を処理る、前記方法に基づいて圧
縮されたデータを復元る、方法は、圧縮と同様であって
それと逆のステップからなる。これらステップは、（１
）同一の所定数ｎ回の繰り返しキャラクタの出現を検出
る、ことによって受信データ中に繰り返し状態を検出し
、（２）所定数ｎ回の繰り返しキャラクタを表すｎ個の
復号されたキャラクタを提供し、（３）ｎ個の繰り返し
キャラクタに続いて、該ｎ回に続く０回の繰り返しキャ
ラクタの出現を表す符号化された記号を受信し、（４）
ｎ個のキャラクタに続いて０個の復号されたキャラクタ
を提供る、ことからなる。もちろん、ｎとＯとの合計は
復号器においても符号器においても同様に穎である。

本発明において、繰り返し記号は、０から所定の２個の
キャラクタまでを表し、開示実施例においてはこのｐは
１５である。連続キャラクタの中に最初の３個に加えて
１５個以上のキャラクタがある場合、追加の符号化記号
が使用されて追加のキャラクタの存在を示す。例えば、
好適方法において、一つの符号化記号では十分でない場
合、複数の符号化記号が使用されて繰り返しキャラクタ
の合計数を表す、符号化記号が１５を示せば１．それは
繰り返しキャラクタの追加数１５を示すと共に、追加の
４ビットカウントニブルまたは記号がそれに続くことを
意味る、。この後続の数は、やはり０〜ｐの一つの数で
ある。第１７Ｅ図に示した例のように、３５個の繰り返
しキャラクタが連続している場合、復号器が受信る、の
は、繰り返し状態に入ることを示す最初の３個のキャラ
クタと、１５個のキャラクタおよび追加の記号が続くこ
とを意味る、第１の繰り返し記号Ｆと、１５個のキャラ
クタおよびさらに別の繰り返し記号が続くことを示す第
２の繰り返し記号Ｆと、繰り返し記号２とであり、合計
３個の繰り返し記号を受信る、。

前記した繰り返しキャラクタの好適圧縮方法は、好適実
施例において、第２図の２８０マイクロコンピユータ３
０用のプログラムとして提供される。

本発明の好適実施例は、改良されたストリームモード動
作の能力も有る、。データの各バイトは、奇数のニブル
に変換され得るので、一連のキャラクタのｉｆ＆のキャ
ラクタが完全に伝送されないことがあり得る。これは、
最後のニブルが、完全なバイトが送信されるように第２
のニブルの追加を待つからである。このため好適実施例
においては、タイマ回路またはタイマ機能を設ける。こ
のタイマは、非活動期間を監視し、所定の非活動期間、
例えば１５ｍ５の経過後、未送信のデータを圧縮回路か
ら一掃（フラッシュ）る、。このタイマ機能は、第２図
の割込駆動専用タイマ・カウンタ回路３３を使用して最
適に実現される。

この−掃方法は次の通りである。これらのステップは、
所定の非活動期間が発生したことの指示に応答して実行
される。装置が繰り返し状態にある場合、カウントニブ
ルが送信されて、繰り返し状態は終了る、。次に、奇数
ニブルのデータが未送信で残っていれば、それに１６進
数Ｆのニブルが結合されて完全なバイトとして送信され
る。この時、Ｆは単一二プルの圧縮コードとしては存在
しない唯一のニブルである。この結合したＦが、受信機
／復元器によって、新しいキャラクタに対る、新しい圧
縮コードの第１ニブルとして翻訳されるのを防止る、な
め、フラグバイトが即座に送信される。−掃（フラッシ
ュ）動作がタイマによって引き起こされると、そのフラ
グバイトに続いて無動作（ｎｏ−ｏｐ）コードが送られ
、受信機に動作を全くせずに最後のＦニブルとフラグバ
イトとｎｏ−ｏｐバイトとを放棄る、ように指示る、。

−掃動作がリセット動作によるものであれば、フラグバ
イトの後にリセットコードが続く９この一掃動作は、デ
ータ流れに２．５バイトを付加る、のでデータスループ
ットを低下させるが、この動作はチャネルが１５ｍ５の
期間遊んでいる場合に実行されるだけである。さらに２
．５バイトのデータを９６００ビット／秒（同期）で送
信る、には、２．８ｍｓ必要なだけである。

（発明の効果） 以上説明したように、本発明の開示実施例は、幾つかの
動的特性と利点とを有る、ので、データ圧縮分野に広く
応用可能である。この動的特性の一つは、圧縮コードの
複数のセットまたはアルファベットの使用による９すな
わち、好適実施例においては１５の異なる圧縮レベルが
あり、そのうちの６レベルは第１表〜第■表に示す通り
であるが、これら各レベルは異なる圧縮符号化機構を表
す。データ統計を累算した後、周期的に、これら１５セ
ットのどれが現在の処理データに最適であるかが決定さ
れる。圧縮レベル０は、ランダムデータ（圧縮なし）に
最適であり、圧縮レベル１５は４ビットキャラクタが最
も多いが、極めて規則的なまたは繰り返しのデータに最
適である。レベル８，９は、英語テキストに最適である
と考えられる。

本発明の他の効果は、これら累算されたデータ統計が固
定でないことである。処理済みのデータの記録はその一
部だけが保持されてその統計が評価される。これにより
、変化しつつあるデータタイプや特性に迅速に適応でき
ると共に、圧縮の効果も維持できる。

本発明のさらに別の効果は、圧縮レベルの上昇に柔軟に
適応できることであり、出現頻度に応じて圧縮程度を適
応できることである。例えば、データ中において４個の
キャラクタが極めて頻繁に出現し、これらが４ビットコ
ードを受け収る場合を考えると、データの性質やタイプ
が変化してさらに別の２個のキャラクタが頻繁に出現し
出すと、圧縮レベルはこれら６個のキャラクタに４ビッ
ト圧縮コードを割り当てるように変化る、。

本発明のさらに別の効果は、適応性の速度である。コン
ピュータによって実行されるソート動作は比較的時間が
かかるので、本発明は部分バブルソートを使用し、テー
ブル用に使用されるメモリ配列内の与えられたキャラク
タから始まる所定数のキャラクタの範囲で、キャラクタ
位置の対の交換を行う。これにより、少しのコンピュー
タ命令で、モデムなどの実時間処理用に適した満足でき
る全体ソート速度を実現る、。これらテーブルは、ある
時点において降順の確率による完全なソートな実現る、
ものではないが、より頻繁に出現る、キャラクタは、よ
り頻繁に処理され部分ソートされて配列の開始端に極め
て迅速に移動る、。

本発明のさらに別の効果は、圧縮コード用に任意ビット
長ではなく１／２バイトを使用る、ことである。これは
、市販のマイクロコンピュータ回路で極めて容易に実現
され、可変ワード長を処理る、必要がないので動作が早
い。

本発明のさらに別の効果は、一連の繰り返しキャラクタ
の圧縮方法において実現され、繰り返しキャラクタとし
てエスケープキャラクタを送信しなり使用したりる、必
要がない。ところが従来の装置では、可能なキャラクタ
セットの一つを繰り返しキャラクタ専用にしなければな
らない、これにより、本発明はアルファベットキャラク
タとして追加の一つを解放る、。これは、異なるアルフ
ァベットキャラクタが多用される場合に重要である。

さらに、繰り返し状態は、所定数のキャラクタの後に自
動的に確立されるので、処理時間が節約できる。ある種
の従来構成では、列内に出現る、繰り返し数を決定る、
ために処理時間が浪費され、それが終了して始めて繰り
返しキャラクタと繰り返し数とが送信される３本発明に
おいては、所定数のキャラクタがまず送信され、次に繰
り返し状態に入るので、最初の所定数のキャラクタの後
の繰り返し数を決定る、ために必要な処理は少ない。

従ってデータの流れは、従来の方法に比べて阻害される
ことが少ない； 本発明のさらに別の効果は、実現される圧縮の程度であ
る。前記したデータ圧縮用の好適方法を使用る、ことに
より、テキストファイルからなる試験データでは０．５
４６というデータ圧縮率が実現された。１，２．および
３ニブル圧縮コード法によれば３０〜４０％の圧縮が実
現されると考えられるが、これに繰り返しキャラクタ列
法を加えれば、さらに２〜１０％のファイルサイズ圧縮
が実現される。

なお、本発明の好適実施例は例示的に説明したものであ
り、当業者には明らかなように、特許請求の範囲を逸脱
せずに他の変更形態も可能である。

また、上述した好適実施例において、各々データを表現
る、ために使用されるアルファベットのキャラクタの位
賀の１６進表記と、符号化された圧縮データを表現る、
ために使用される１６進圧縮コードとを示す第工表〜第
■表は、以下に添付しであるので、それを参照されたい
。

【図面の簡単な説明】

第１図は、本発明の好適データ圧縮方法および装置を使
用したデータ通信応用例を示す概略図、第２図は、好適
データ圧縮方法をモデムにおいて実現した場合のマイク
ロコンピュータを基本とした回路を示す概略プロツク図
、 第３図〜第１６図は、各々本発明の方法に基づいて圧縮
したデータ流れの例と圧縮動作における各時点での符号
化テーブルとを示す図。 第１７　（Ａ）図〜第１７（Ｅ）図は、本発明に基づ（
繰り返しキャラクタの圧縮方法を示す図である。 Ｔ１・・・符号テーブル Ｔ２・・・復合化テーブル １０．１５・・・モデム １２・・・電話回線 ２０・・・データ圧縮回路 ２２・・・モデム／コンピュータインタフェース、回路 ２３・・・回線 ２４・・・モデム／電話インターフェース回路２５・・
・データバス ２７．２８・・・制御レジスタ ３０・・・マイクロコンピュータ ３１・・・プログラムメモリ ３２・・・アドレスバス ３３・・・プログラマブルタイマ・カウンタ回路３５・
・・ＲＡＭ

Claims (1)

1. 【特許請求の範囲】 １、（１）アルファベットの各キャラクタに対応づけら
   れており幾つかが他よりも短く設定されている複数のデ
   ジタルコードを有する符号化テーブルを提供し、 （２）前記アルファベットの１キャラクタで表されるデ
   ータ項目を符号化のために提供し、 （３）前記提供されたデータ項目に応じて、前記提供さ
   れたデータ項目が示す前記アルファベットの特定のキャ
   ラクタに対応するコードを前記符号化テーブルから選択
   し、 （４）前記選択されたコードを出力として提供し、（５
   ）符号化用に提供される複数のアルファベットキャラク
   タにおける各キャラクタの出現頻度の関数として前記符
   号化テーブルにおけるアルファベットキャラクタとコー
   ドとの対応関係を周期的に調整する各段階を備え、 符号化用に提供される複数のキャラクタにおける各キャ
   ラクタの出現頻度の変化に応じて、より出現頻度の高い
   キャラクタを前記符号化テーブル中のより短いコードに
   対応させる、動的データ圧縮方法。 ２、（１）前記符号化テーブルと同様の方法においてア
   ルファベットの各キャラクタに対応づけられており幾つ
   かが他よりも短く設定されている複数のデジタルコード
   を有する復号化テーブルを前記圧縮用の符号化テーブル
   と並列に提供し、 （２）前記デジタルコードの一つによって表される符号
   化されたデータの項目を復号用に提供し、（３）前記提
   供された符号化されたデータ項目に応じて、前記符号化
   されたデータ項目が示す特定のデジタルコードに対応す
   るキャラクタを前記復号化テーブルから選択し、 （４）前記選択されたキャラクタを復号化出力として提
   供し、 （５）復号化用に提供される複数のアルファベットキャ
   ラクタにおける各キャラクタの出現頻度の関数として前
   記復号化テーブルにおけるアルファベットキャラクタと
   コードとの対応関係を周期的に調整する各段階を備え、 復号化用に提供される複数のキャラクタにおける各キャ
   ラクタの出現頻度の変化に応じて、より出現頻度の高い
   キャラクタを前記符号化テーブルと並列の前記復号化テ
   ーブル中のより短いコードに対応させる、請求項１に記
   載の方法によって圧縮されたデータを復元するデータ復
   元方法。 ３、前記アルファベットキャラクタと対応コードとが初
   期順序の配列に配置され、より短いコードが前記配列の
   開始端側に配置され、より長いコードが前記配列の終端
   側に配置され、符号化テーブルにおけるアルファベット
   キャラクタとコードとの対応関係を周期的に調整する前
   記段階が、（６）各アルファベットキャラクタのカウン
   ト数を維持し、 （７）符号化用に提供されたデータ項目の表す特定のキ
   ャラクタのコードを前記符号化テーブルから選択した後
   に該キャラクタのカウント数を増分させ、 （８）前記カウント数を増分した後に、当該特定のキャ
   ラクタのカウント数と、前記配列中においてより短いコ
   ードに対応する位置にあると見なされる所定のキャラク
   タのカウント数とを比較し、（９）前記特定のキャラク
   タのカウント数が、前記所定のキャラクタのカウント数
   よりも大きければ、前記配列中における符号化直後の前
   記特定のキャラクタと前記所定のキャラクタとの相対位
   置を交換し、より大きなカウント数を有するキャラクタ
   を前記配列中のより短いコードに対応する位置に対応づ
   ける、請求項１に記載の方法。 ４、前記配列中において、前記所定のキャラクタが前記
   特定のキャラクタから前記配列の開始端方向の所定数の
   各位置に配置される、請求項３に記載の方法。 ５、前記所定数の各位置が１６箇所である、請求項４に
   記載の方法。 ６、前記符号化テーブルが複数セットのデジタルコード
   を備え、前記デジタルコードの長さは各セット内におい
   て同一の所定長さであるが各セット間において長さが異
   なり、アルファベットキャラクタに対応する初期順序の
   配列においては、短いコードのセットが前記配列の開始
   端側に配置され、長いコードのセットが前記配列の終端
   側に配置される、請求項１に記載の方法。 ７、前記各セットが当初は所定のサイズに設定され、前
   記各セットのサイズを周期的に調整する段階をさらに備
   えることにより、前記各セットのデジタルコードによっ
   て表されるキャラクタの数を、符号化用に提供されるデ
   ータ中のキャラクタの出現頻度の関数として変化させる
   、請求項６に記載の方法。 ８、前記各セットのサイズを周期的に調整する段階が、 （１）連続するキャラクタからなる所定グループについ
   て、各グループの各キャラクタのカウント数を合計して
   複数のグループカウント数を提供し、（２）前記配列の
   終端側のグループのカウント数と、前記配列の開始端側
   のキャラクタのカウント数とを比較し、 （３）前記グループのカウント数と前記キャラクタのカ
   ウント数とが最も短いデジタルコードのセットの終端に
   おいて一致するまで、前記最も短いデジタルコードのセ
   ットのサイズを拡大し、 前記グループのカウント数に関係する各キャラクタの出
   現確率よりも高い出現確率を有するキャラクタのより多
   くが前記最も短いデジタルコードのセットに対応づけら
   れるように、該最も短いデジタルコードのセットのサイ
   ズを拡大する、請求項７に記載の方法。 ９、少なくとも３セットのデジタルコードがあり、最も
   長いデジタルコードのセットのサイズが前記グループの
   サイズの増分に伴って増加し、最も短いコードのセット
   のサイズが単一のキャラクタの増分に伴って増加する、
   請求項８に記載の方法。 １０、前記最も短いデジタルコードのセットのサイズが
   要素数０〜１５の範囲で変化する、請求項９に記載の方
   法。 １１、前記最も長いデジタルコードのセットのサイズが
   要素数０〜２４０の範囲で変化する、請求項９に記載の
   方法。 １２、前記最も短いデジタルコードが４ビットであり前
   記最も長いデジタルコードが１２ビットである、請求項
   ９に記載の方法。 １３、前記最も短いデジタルコードのセットの要素数が
   当初において４であり、前記最も長いデジタルコードの
   セットの要素数が当初において６４である、請求項９に
   記載の方法。 １４、前記各セットのサイズを周期的に調整する段階が
   、符号化用に提供される所定数のデータ項目の出現後に
   繰り返される、請求項８に記載の方法。 １５、前記各セットのサイズを周期的に調整する段階に
   おける前記所定数が１２８である、請求項１４に記載の
   方法。 １６、前記連続キャラクタの所定グループの各グループ
   が１６キャラクタからなる、請求項８に記載の方法。 １７、前記各セットのサイズを周期的に調整する段階が
   、符号化用に提供されるデータの各に項目ごとに実行さ
   れる、請求項７に記載の方法。 １８、前記にが１２８である、請求項１７に記載の方法
   。 １９、アルファベット中にｎ個のキャラクタが含まれ、
   前記最も短いデジタルコードのセットの要素数がａであ
   り、前記最も長いデジタルコードのセットの要素数がｃ
   であり、前記各セットのサイズを周期的に調整する段階
   が、 （ｉ）各々がｍキャラクタを含む連続するグループにお
   いて、各グループ内のキャラクタのカウント数を合計す
   ることによりｎ／ｍ個の複数のグループカウント数を提
   供し、 （ｉｉ）グループ（ｎ／ｍ）−ｉ−１のグループカウン
   ト数とキャラクタｊのカウント数とを比較し（ｉはゼロ
   から始まるグループカウント数の整数の指標、ｊは前記
   配列の開始端においてゼロから始まる配列中の整数の指
   標）、 （ｉｉｉ）グループ（ｎ／ｍ　）−ｉ−１のグループカ
   ウント数がキャラクタｊのカウント数よりも小さければ
   、ｉおよびｊを増分して前記第（ｉｉ）段階に戻り、 （ｉｖ）グループ（ｎ／ｍ）−ｉ−１のグループカウン
   ト数がキャラクタｊのカウント数よりも大きいか等しけ
   れば、最も短いデジタルコードの数をｊ＋１とし、最も
   長いデジタルコードの数をｃ＝（ｎ／ｍ）ｘ（ｉ＋１）
   とすることによって、ａ＝ｊ＋１の符号化レベルを確立
   し、これによってａおよびｃの相対数を変化させる、請
   求項７に記載の方法。 ２０、前記最も短いデジタルコードと前記最も長いデジ
   タルコードとの間のサイズを有するデジタルコードに対
   応づけられるキャラクタのセットであって、該セットの
   要素数がｂであり、ｂ＝ｎ−（ｊ＋１）−（（ｎ／ｍ）
   ｘ（ｉ＋１））であるような該キャラクタセットを含む
   、請求項１９に記載の方法。 ２１、アルファベットの各キャラクタに対応づけられて
   おり幾つかが他よりも短く設定されている複数のデジタ
   ルコードを有する符号化テーブルを格納するメモリ手段
   と、 前記アルファベットの１キャラクタで表されるデータ項
   目を符号化のために受け取る手段と、前記提供されたデ
   ータ項目に応じて、前記提供されたデータ項目が示す前
   記アルファベットの特定のキャラクタに対応するコード
   を前記符号化テーブルから選択する手段と、 前記選択されたコードを出力として提供する出力手段と
   、 符号化用に提供される複数のアルファベットキャラクタ
   における各キャラクタの出現頻度の関数として前記符号
   化テーブルにおけるアルファベットキャラクタとコード
   との対応関係を周期的に調整するコード／キャラクタ対
   応関係調整手段とを備え、 符号化用に提供される複数のキャラクタにおける各キャ
   ラクタの出現頻度の変化に応じて、より出現頻度の高い
   キャラクタを前記符号化テーブル中のより短いコードに
   対応させる、動的データ圧縮装置。 ２２、前記符号化テーブルと同様の方法においてアルフ
   ァベットの各キャラクタに対応づけられており幾つかが
   他よりも短く設定されている複数のデジタルコードを有
   する復号化テーブルを前記圧縮用の符号化テーブルと並
   列に格納する第２のメモリ手段と、 前記デジタルコードの一つによって表される符号化され
   たデータの項目を復号用に受け取る手段と、 前記提供された符号化されたデータ項目に応じて、前記
   符号化されたデータ項目が示す特定のデジタルコードに
   対応するキャラクタを前記復号化テーブルから選択する
   手段と、 前記選択されたキャラクタを復号化出力として提供する
   手段と、 復号化用に提供される複数のアルファベットキャラクタ
   における各キャラクタの出現頻度の関数として前記復号
   化テーブルにおけるアルファベットキャラクタとコード
   との対応関係を周期的に調整する手段とを備え、 復号化用に提供される複数のキャラクタにおける各キャ
   ラクタの出現頻度の変化に応じて、より出現頻度の高い
   キャラクタを前記符号化テーブルと並列の前記復号化テ
   ーブル中のより短いコードに対応させる、請求項２１に
   記載の装置によって圧縮されたデータを復元するデータ
   復元装置。 ２３、前記アルファベットキャラクタと対応コードとが
   初期順序の配列において前記メモリ手段内に配置され、
   より短いコードが前記配列の開始端側に配置され、より
   長いコードが前記配列の終端側に配置され、前記調整手
   段が前記メモリ手段に格納された符号化テーブルにおけ
   るアルファベットキャラクタとコードとの対応関係を周
   期的に調整し、さらに、 前記メモリ手段内の各アルファベットキャラクタのカウ
   ント数を維持する手段と、 符号化用に提供されたデータ項目の表す特定のキャラク
   タのコードを前記符号化テーブルから選択した後に該キ
   ャラクタのカウント数を増分させる手段と、 前記カウント数を増分した後に、当該特定のキャラクタ
   のカウント数と、前記配列中においてより短いコードに
   対応する位置にあると見なされる所定のキャラクタのカ
   ウント数とを比較する手段と、 前記特定のキャラクタのカウント数が、前記所定のキャ
   ラクタのカウント数よりも大きければ、前記配列中にお
   ける符号化直後の前記特定のキャラクタと前記所定のキ
   ャラクタとの相対位置を交換することにより、より大き
   なカウント数を有するキャラクタを前記配列中のより短
   いコードに対応する位置に対応づける手段とを備える、
   請求項２１に記載の装置。 ２４、前記配列中において、前記所定のキャラクタが前
   記特定のキャラクタから前記配列の開始端方向の所定数
   の各位置に配置される、請求項２３に記載の装置。 ２５、前記所定数の各位置が１６箇所である、請求項２
   ４に記載の装置。 ２６、前記符号化テーブルが複数セットのデジタルコー
   ドを備え、前記デジタルコードの長さは各セット内にお
   いて同一の所定長さであるが各セット間において長さが
   異なり、前記メモリ手段内でのアルファベットキャラク
   タに対応する初期順序の配列においては、短いコードの
   セットが前記配列の開始端側に配置され、長いコードの
   セットが前記配列の終端側に配置される、請求項２１に
   記載の装置。 ２７、前記各セットが当初は所定のサイズに設定され、
   前記各セットのサイズを周期的に調整する手段をさらに
   備え、前記各セットのデジタルコードによって表される
   キャラクタの数を、符号化用に提供されるデータ中のキ
   ャラクタの出現頻度の関数として変化させる、請求項２
   ６に記載の装置。 ２８、前記各セットのサイズを調整する手段が、連続す
   るキャラクタからなる所定グループについて、各グルー
   プの各キャラクタのカウント数を合計して複数のグルー
   プカウント数を提供する手段と、 前記配列の終端側のグループのカウント数と、前記配列
   の開始端側のキャラクタのカウント数とを比較する手段
   と、 前記グループのカウント数と前記キャラクタのカウント
   数とが最も短いデジタルコードのセットの終端において
   一致するまで、前記最も短いデジタルコードのセットの
   サイズを拡大する手段とを備え、 前記グループのカウント数に関係する各キャラクタの出
   現確率よりも高い出現確率を有するキャラクタのより多
   くが、前記最も短いデジタルコードのセットに対応づけ
   られるように、該最も短いデジタルコードのセットのサ
   イズを拡大する、請求項２７に記載の装置。 ２９、少なくとも３セットのデジタルコードがあり、最
   も長いデジタルコードのセットのサイズが前記グループ
   のサイズの増分に伴って増加し、最も短いコードのセッ
   トのサイズが単一のキャラクタの増分に伴って増加する
   、請求項２８に記載の装置。 ３０、前記最も短いデジタルコードのセットのサイズが
   要素数０〜１５の範囲で変化する、請求項２９に記載の
   装置。 ３１、前記最も長いデジタルコードのセットのサイズが
   要素数０〜２４０の範囲で変化する、請求項２９に記載
   の装置。 ３２、前記最も短いデジタルコードが４ビットであり前
   記最も長いデジタルコードが１２ビットである、請求項
   ２９に記載の装置。 ３３、前記最も短いデジタルコードのセットの要素数が
   当初において４であり、前記最も長いデジタルコードの
   セットの要素数が当初において６４である、請求項２９
   に記載の装置。 ３４、前記各セットのサイズを調整する手段が、符号化
   用に提供される所定数のデータ項目の出現後に動作する
   、請求項２８に記載の装置。 ３５、前記各セットのサイズを調整する上での前記所定
   数が１２８である、請求項３４に記載の装置。 ３６、前記連続キャラクタの所定グループの各グループ
   が１６キャラクタからなる、請求項２８に記載の装置。 ３７、前記各セットのサイズを調整する手段が、符号化
   用に提供されるデータの各に項目ごとに動作する、請求
   項２７に記載の装置。 ３８、前記ｋが１２８である、請求項３７に記載の装置
   。 ３９、アルファベット中にｎ個のキャラクタが含まれ、
   前記最も短いデジタルコードのセットの要素数がａであ
   り、前記最も長いデジタルコードのセットの要素数がｃ
   であり、前記各セットのサイズを調整する手段が、 各々がｍキャラクタを含む連続するグループにおいて、
   各グループ内のキャラクタのカウント数を合計すること
   によりｎ／ｍ個の複数のグループカウント数を提供する
   手段と、 グループ（ｎ／ｍ）−ｉ−１のグループカウント数とキ
   ャラクタｊのカウント数とを比較する手段と（ｉはゼロ
   から始まるグループカウント数の整数の指標、ｊは前記
   配列の開始端においてゼロから始まる配列中の整数の指
   標）、 グループ（ｎ／ｍ）−ｉ−１のグループカウント数がキ
   ャラクタｊのカウント数よりも小さければ、ｉおよびｊ
   を増分して前記比較手段に制御を戻す手段と、 グループ（ｎ／ｍ）−ｉ−１のグループカウント数がキ
   ャラクタｊのカウント数よりも大きいか等しければ、最
   も短いデジタルコードの数をｊ＋１とし、最も長いデジ
   タルコードの数をｃ＝（ｎ／ｍ）ｘ（ｉ＋１）とする手
   段とを備えることによつてａおよびｃの相対数を変化さ
   せる、請求項２７に記載の装置。 ４０、前記最も短いデジタルコードと前記最も長いデジ
   タルコードとの間のサイズを有するデジタルコードに対
   応づけられるキャラクタのセットであって、該セットの
   要素数がｂであり、ｂ＝ｎ−（ｊ＋１）−（（ｎ／ｍ）
   ｘ（ｉ＋１））であるような該キャラクタセットを含む
   、請求項３９に記載の装置。 ４１、前記装置がモデムに使用される、請求項２１に記
   載の装置。 ４２、前記データを受け取る手段と、前記コードを選択
   する手段と、前記出力手段と、前記コード／キャラクタ
   対応関係調整手段とが、プログラムされたマイクロコン
   ピュータによつて構成される、請求項２１に記載の装置
   。 ４３、（１）０〜ｎの範囲の情報を表現するために使用
   されるｎ個のキャラクタを含むアルファベットを提供し
   、 （２）前記ｎ個のキャラクタを初期順序の配列に配置し
   、 （３）前記ｎ個のキャラクタを符号化するために使用さ
   れるｚビットコードのセットを提供し、前記コードの幾
   つかは他よりも長いビット長を有するようにし、短いコ
   ードは前記配列の開始端側の位置に対応づけ、長いコー
   ドは前記配列の終端側に対応づけ、 （４）前記アルファベットのキャラクタによって表現さ
   れる順次入力情報の流れを前記コードで符号化するため
   に提供し、 （５）前記順次入力情報の流れの各項目ｘに対して、（
   ｉ）前記項目ｘに対応するキャラクタの前記配列中にお
   ける相対位置の関数として１個のｚビットコードを前記
   コードセットから選択し、それを出力として提供し、 （ｉｉ）前記順次入力情報の流れの前記特定の項目ｘを
   表現する前記アルファベットのキャラクタのカウント数
   ＣＣを増分し、 （ｉｉｉ）前記キャラクタのカウント数ＣＣと、前記配
   列内の開始端側の所定範囲内の各キャラクタのカウント
   数とを比較し、 （ｉｖ）前記比較の結果、前記キャラクタのカウント数
   ＣＣが前記所定範囲内の１キャラクタのカウント数より
   大きいか等しければ、前記項目ｘに対応する前記キャラ
   クタと前記所定範囲内において前記等しいか小さいカウ
   ント数を有するキャラクタとの前記配列内での相対位置
   を交換する各段階を備え、 前記入力情報の流れにおけるキャラクタの出現頻度が変
   化するのに伴い、より出現頻度の高いキャラクタを前記
   配列の開始端方向に移動させて前記短いコードに対応づ
   ける、モデム等の直列／順次データ送信装置に特に有用
   な動的可変データ圧縮方法。 ４４、前記アルファベット中における第１の所定数ａの
   キャラクタに第１のコードを対応させ、第２の所定数ｂ
   のキャラクタに第２のコードを対応させ、前記第１のコ
   ードは前記第２のコードよりも短く、さらに前記入力情
   報の流れにおける各キャラクタの出現頻度の関数として
   前記ａおよびｂの相対数を調整する段階を備える、請求
   項４３に記載の方法。 ４５、前記ｚが少なくとも４である、請求項４３に記載
   の方法。 ４６、前記ｚが４、８、１２から選択される、請求項４
   ３に記載の方法。 ４７、請求項４３に記載の方法がモデムにおいて通信回
   線を介して圧縮データを送信するために実行され、請求
   項４３に記載の方法によって圧縮されたデータを復元す
   るために前記通信回線の他端において実行される方法を
   さらに備え、該他端において実行される方法が、 （１）請求項４３の複製であるｎｄ個のキャラクタを含
   む第２のアルファベットを提供し、 （２）前記ｎｄ個のキャラクタを請求項４３の配列と同
   一である初期順序の配列に配置し、 （３）前記コードで符号化された順次データの流れを受
   信し、 （４）前記第２のアルファベット中において前記コード
   に対応するキャラクタを参照し、 （５）前記コードに対応するキャラクタを出力として提
   供し、 （６）請求項４３の第（５）（ｉｉ）〜（ｉｖ）段階と
   同様の方法において、前記第２のアルファベットの配列
   の順序を維持する各段階を備え、 前記符号化される入力情報の流れにおけるキャラクタの
   出現頻度が変化するのに伴い、前記符号化用の配列と並
   列に、前記第２のアルファベット中のより出現頻度の高
   い対応キャラクタを前記復号化用の配列の開始端方向に
   移動させる、請求項４３に記載の方法。 ４８、（１）０〜ｎの範囲の情報を表現するために使用
   されるｎ個のキャラクタを含むアルファベットを提供し
   、 （２）前記ｎ個のキャラクタを初期順序の配列に配置し
   、 （３）前記ｎ個のキャラクタのうち第１の所定数ａのキ
   ャラクタを符号化するために使用されるｐビットコード
   の第１のコードセットを提供し、前記ｎ個のキャラクタ
   のうち第２の所定数ｂのキャラクタを符号化するために
   使用されるｑビットコードの第２のコードセットを提供
   し、前記ｎ個のキャラクタのうち第３の所定数ｃのキャ
   ラクタを符号化するために使用されるｒビットコードの
   第３のコードセットを提供し、ａ＋ｂ＋ｃ＝ｎとし、（
   ４）前記アルファベットのキャラクタによって表現され
   る順次入力情報の流れを前記ｐ、ｑ、およびｒビットコ
   ードで符号化するために提供し、（５）前記順次入力情
   報の流れの各項目ｘに対して、（ｉ）前記項目ｘに対応
   するキャラクタの前記配列中における相対位置の関数と
   して１個のｚビットコード（２はｐ、ｑ、またはｒであ
   る）を前記コードセットから選択し、それを出力として
   提供し、（ｉｉ）前記順次入力情報の流れの前記特定の
   項目ｘを表現する前記アルファベットのキャラクタのカ
   ウント数ＣＣを増分し、 （ｉｉｉ）前記キャラクタのカウント数ＣＣと、前記配
   列内の開始端側のｄ箇所（ｄはｎよりも小さい所定数）
   までの所定範囲内の各キャラクタのカウント数とを比較
   し、 （ｉｖ）前記比較の結果、前記キャラクタのカウント数
   ＣＣが前記所定範囲内の１キャラクタのカウント数より
   大きいか等しければ、前記項目ｘに対応する前記キャラ
   クタと前記所定範囲内において前記等しいか小さいカウ
   ント数を有するキャラクタとの前記配列内での相対位置
   を交換し、 （６）前記順次入力情報の流れのｋキャラクタごとに、 （ｉ）各々がｍキャラクタを含む連続するグループにお
   いて、各グループ内のキャラクタのカウント数を合計す
   ることによりｎ／ｍ個の複数のグループカウント数を提
   供し、 （ｉｉ）グループ（ｎ／ｍ）−ｉ−１のグループカウン
   ト数とキャラクタｊのカウント数とを比較し（ｉはゼロ
   から始まるグループカウント数の整数の指標、ｊは前記
   配列の開始端においてゼロから始まる配列中の整数の指
   標）、 （ｉｉｉ）グループ（ｎ／ｍ）−ｉ−１のグループカウ
   ント数がキャラクタｊのカウント数よりも小さければ、
   ｉおよびｊを増分して前記第６（ｉｉ）段階に戻り、 （ｉｖ）グループ（ｎ／ｍ）−ｉ−１のグループカウン
   ト数がキャラクタｊのカウント数よりも大きいか等しけ
   れば、ｐビットのデジタルコードの数をｊ＋１とし、ｒ
   ビットのデジタルコードの数をｃ＝（ｎ／ｍ）ｘ（ｉ＋
   １）とし、ｑビットのデジタルコードの数をｂ＝ｎ−（
   ｊ＋１）−（（ｎ／ｍ）ｘ（ｉ＋１））としてａ＝ｊ＋
   １の符号化レベルを確立することによりａ、ｂ、および
   ｃの相対数によって表される符号化レベルを変更する各
   段階を備える、モデム等の直列／順次データ送信装置に
   特に有用な動的可変データ圧縮方法。 ４９、前記アルファベットがＡＳＣＩＩキャラクタセッ
   トからなり前記ｎが２５６である、請求項４８に記載の
   方法。 ５０、前記各数においてｐ＜ｑ＜ｒである、請求項４８
   に記載の方法。 ５１、前記ｐが４であり前記ｑが８であり前記ｒが１２
   である、請求項５０に記載の方法。 ５２、初期化時において前記ａが４であり前記ｂが１８
   ８であり前記ｃが６４である、請求項４８に記載の方法
   。 ５３、前記ｄが１６である、請求項４８に記載の方法。 ５４、前記ｋが１２８である、請求項４８に記載の方法
   。 ５５、前記ｍが１６である、請求項４８に記載の方法。 ５６、請求項４８に記載の方法がモデムにおいて通信回
   線を介して圧縮データを送信するために実行され、請求
   項４８に記載の方法によって圧縮されたデータを復元す
   るために前記通信回線の他端において実行される方法を
   さらに備え、該他端において実行される方法が、 （１）請求項４８の複製であるｎｄ個のキャラクタを含
   む第２のアルファベットを提供し、 （２）前記ｎｄ個のキャラクタを請求項４８の配列と同
   一である初期順序の配列に配置し、 （３）前記ｎｄ個のキャラクタのうち第１の所定数ａｄ
   のキャラクタを符号化するために使用されるｐｄビット
   コードの第１のコードセットを提供し、前記ｎｄ個のキ
   ャラクタのうち第２の所定数ｂｄのキャラクタを符号化
   するために使用されるｑｄビットコードの第２のコード
   セットを提供し、前記ｎｄ個のキャラクタのうち第３の
   所定数ｃｄのキャラクタを符号化するために使用される
   ｒｄビットコードの第３のコードセットを提供し、ｐｄ
   ＜ｑｄ＜ｒｄとし、ｐｄ、ｑｄ、およびｒｄは符号化段
   階におけるｐ、ｑ、およびｒに対応させ、ａｄ、ｂｄ、
   およびｃｄは符号化段階におけるａ、ｂ、およびｃに対
   応させ、 （４）前記通信回線を介して前記ｐ、ｑ、およびｒビッ
   トコードのｚビットコードで符号化された順次データの
   流れを受信し、 （５）前記順次データの流れの各項目ｘに対して、（ｉ
   ）前記項目ｘを表すｚビットコードと前記第２のアルフ
   ァベットのｎｄキャラクタに対応する各コードとの間に
   一致を探し、 （ｉｉ）前記第２のアルファベットのｎｄキャラクタの
   うち前記項目ｘを表すコードに対応する１個を復元出力
   として提供し、 （ｉｉｉ）前記順次入力情報の流れの前記特定の項目ｘ
   を表現する前記第２のアルファベットのキャラクタのカ
   ウント数ＣＣｄを増分し、 （ｉｖ）前記キャラクタのカウント数ＣＣｄと、前記第
   ２のアルファベットの配列内の開始端側のｄｄ箇所（ｄ
   ｄは前記符号化方法におけるｄに対応）までの所定範囲
   内の各キャラクタのカウント数とを比較し、 （ｖ）前記比較の結果、前記キャラクタのカウント数Ｃ
   Ｃｄが前記第２のアルファベットの所定範囲内の１キャ
   ラクタのカウント数より大きいか等しければ、前記項目
   ｘに対応する前記キャラクタと前記所定範囲内において
   前記等しいか小さいカウント数を有するキャラクタとの
   前記配列内での相対位置を交換し、 （６）前記順次データの流れのｋｄキャラクタ（ｋｄは
   前記符号化方法におけるｋに対応）ごとに、（ｉ）各々
   がｍｄキャラクタ（ｍｄは前記符号化方法におけるｍに
   対応）を含む連続するグループにおいて、各グループ内
   のキャラクタのカウント数を合計することによりｎｄ／
   ｍｄ個の複数のグループカウント数を提供し、 （ｉｉ）グループ（ｎｄ／ｍｄ）−ｉ−１のグループカ
   ウント数とキャラクタｊのカウント数とを比較し（ｉは
   ゼロから始まるグループカウント数の整数の指標、ｊは
   前記配列の開始端においてゼロから始まる配列中の整数
   の指標）、 （ｉｉｉ）グループ（ｎｄ／ｍｄ）−ｉ−１のグループ
   カウント数がキャラクタｊのカウント数よりも小さけれ
   ば、ｉおよびｊを増分して前記第６（ｉｉ）段階に戻り
   、 （ｉｖ）グループ（ｎｄ／ｍｄ）−ｉ−１のグループカ
   ウント数がキャラクタｊのカウント数よりも大きいか等
   しければ、ｐｄビットのデジタルコードの数をｊ＋１と
   し、ｒｄビットのデジタルコードの数をｃｄ＝（ｎｄ／
   ｍｄ）ｘ（ｉ＋１）とし、ｑｄビットのデジタルコード
   の数をｂｄ＝ｎｄ−（ｊ＋１）−（（ｎｄ／ｍｄ）ｘ（
   ｉ＋１））としてａｄ＝ｊ＋１の符号化レベルを確立す
   ることによりａｄ、ｂｄ、およびｃｄの相対数によって
   表される復号化レベルを変更する各段階を備える、請求
   項４８に記載の方法。 ５７、（１）アルファベットの各キャラクタに対応づけ
   られており幾つかが他よりも短く設定されている複数の
   デジタルコードがコード長の短い順に配置された初期順
   序の配列を有する符号化テーブルを提供し、 （２）前記アルファベットの１キャラクタで表されるデ
   ータ項目を符号化のために提供し、 （３）前記提供されたデータ項目に応じて、前記提供さ
   れたデータ項目が示す前記アルファベットの特定のキャ
   ラクタに対応するコードを前記符号化テーブルから選択
   し、 （４）前記選択されたコードを出力として提供し、（５
   ）前記提供されたデータ項目にさらに応じて、前記提供
   されたデータに対応するキャラクタの出現確率の統計記
   録を維持し、 （６）前記提供されたデータ項目にさらに応じて、前記
   提供されたデータ項目を表すキャラクタの配列内の位置
   と、それより低い出現確率を有する１キャラクタの配列
   内の位置とを交換し、より出現頻度の高いキャラクタを
   前記配列内のより短いコードに対応していると見なされ
   る位置に移動させる、動的調整データ圧縮方法。 ５８、前記デジタルコードが複数のコードセットとして
   配置され、出現確率の高いキャラクタに対応づけられる
   セットのコードは出現確率の低いキャラクタに対応づけ
   られるセットのコードより少ないビット数を有し、前記
   各セットに対応づけられる各キャラクタの出現確率の大
   きさの関数として前記各セットのサイズを周期的に調整
   する段階をさらに備え、出現確率の高いキャラクタを最
   も短いコードを有するコードセットに対応させる、請求
   項５７に記載の方法。 ５９、（１）前記符号化テーブルと同様の方法において
   アルファベットの各キャラクタに対応づけられており幾
   つかが他よりも短く設定されている複数のデジタルコー
   ドがコード長の短い順に配置された初期順序の配列を有
   する復号化テーブルを前記圧縮用の符号化テーブルと並
   列に提供し、（２）前記デジタルコードの一つによって
   表される符号化されたデータの項目を復号用に提供し、
   （３）前記提供された符号化されたデータ項目に応じて
   、前記符号化されたデータ項目が示す特定のデジタルコ
   ードに対応するキャラクタを前記復号化テーブルから選
   択し、 （４）前記選択されたキャラクタを復号化出力として提
   供し、 （５）前記提供された符号化されたデータ項目にさらに
   応じて、前記復号されたキャラクタの出現確率の統計記
   録を維持し、 （６）前記提供された符号化されたデータ項目にさらに
   応じて、前記復号されたキャラクタの復号化配列内の位
   置と、それより低い出現確率を有する１キャラクタの復
   号化配列内の位置とを交換し、より出現頻度の高いキャ
   ラクタを前記配列内のより短いコードに対応していると
   見なされる位置に移動させる、請求項５７の方法によっ
   て圧縮されたデータを復元するためのデータ復元方法。 ６０、ｍ個の繰り返しキャラクタの列を有する入力デー
   タ列を圧縮するに当り、 （１）繰り返しキャラクタの所定数ｎ回の出現を検出す
   ることによって繰り返し状態に入り、 （２）前記所定数ｎの繰り返しキャラクタを表すデータ
   を送信し、 （３）前記第（２）段階の直後に、前記繰り返しキャラ
   クタの前記ｎ回に続く出現回数ｏ（ｎ＋ｏ＝ｍ）を表す
   符号化された第１の記号を送信する、モデムによって通
   信回線を介してデータを送信するために特に有用な圧縮
   方法。 ６１、前記所定数ｎが３である、請求項６０に記載の方
   法。 ６２、（１）繰り返しキャラクタの所定数ｎ回の出現を
   検出することによって受信データ内に繰り返し状態を検
   出し、 （２）前記所定数ｎの繰り返しキャラクタを表す復号さ
   れたｎ個のキャラクタを提供し、 （３）前記ｎ個の繰り返しキャラクタに続いて、前記繰
   り返しキャラクタの前記ｎ回に続く出現回数ｏ（ｎ＋ｏ
   ＝ｍ）を表す前記符号化された記号を受信し、 （４）前記ｎ個のキャラクタの後に復号されたｏ個のキ
   ャラクタを提供する、請求項６０の方法によって圧縮さ
   れたデータを復元する方法。 ６３、前記第１の記号が０と所定数ｐとの間のキャラク
   タ数を表す、請求項６０に記載の方法。 ６４、前記第１の記号がｐである場合、前記ｐ個に続く
   繰り返しキャラクタの追加の出現回数を表す第２の符号
   化された記号を提供する段階をさらに備える、請求項６
   ３に記載の方法。 ６５、前記ｐが１５である、請求項６３に記載の方法。