JPH08204579A - データ圧縮方法及び装置 - Google Patents
データ圧縮方法及び装置Info
- Publication number
- JPH08204579A JPH08204579A JP7201047A JP20104795A JPH08204579A JP H08204579 A JPH08204579 A JP H08204579A JP 7201047 A JP7201047 A JP 7201047A JP 20104795 A JP20104795 A JP 20104795A JP H08204579 A JPH08204579 A JP H08204579A
- Authority
- JP
- Japan
- Prior art keywords
- data
- character
- characters
- encoding table
- stream
- 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.)
- Pending
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/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
- H03M7/3088—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing the use of a dictionary, e.g. LZ78
-
- 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
-
- 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
- H03M7/42—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code using table look-up for the coding or decoding process, e.g. using read-only memory
-
- 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/46—Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
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)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【課題】 データ圧縮を改善するためのリアルタイム方
法を提供する。 【解決手段】 モデム（１０）に提供されるデータ文字
間の相関関係が判断される。データ文字間の相関関係を
判断するために、符号化テーブル（１６）内のツリー
（６）の形および圧縮率（９６）という２つの基準が利
用される。データ文字間の相関関係が２つの基準を利用
して判断されると、符号化テーブル（１６）のサイズを
変更できる。データ文字に相関関係がない場合、すなわ
ち、データがランダムまたは擬似乱数であることを意味
する場合、符号化テーブルのサイズは減らされる。デー
タ文字が強い相関関係にある場合、符号化テーブルのサ
イズを変更すると、圧縮できないデータを圧縮しようと
して費やされる時間が削減され、圧縮可能なデータのデ
ータ圧縮が増加する。
法を提供する。 【解決手段】 モデム（１０）に提供されるデータ文字
間の相関関係が判断される。データ文字間の相関関係を
判断するために、符号化テーブル（１６）内のツリー
（６）の形および圧縮率（９６）という２つの基準が利
用される。データ文字間の相関関係が２つの基準を利用
して判断されると、符号化テーブル（１６）のサイズを
変更できる。データ文字に相関関係がない場合、すなわ
ち、データがランダムまたは擬似乱数であることを意味
する場合、符号化テーブルのサイズは減らされる。デー
タ文字が強い相関関係にある場合、符号化テーブルのサ
イズを変更すると、圧縮できないデータを圧縮しようと
して費やされる時間が削減され、圧縮可能なデータのデ
ータ圧縮が増加する。
Description
【０００１】
【発明の属する技術分野】本発明は、データ圧縮に係
り、更に詳しくは、データ圧縮に当てられる処理時間と
達成されるデータ圧縮の関係を最適化するために、リア
ルタイムでデータ圧縮のための符号化テーブルのサイズ
を監視、調整するリアルタイム適応型データ圧縮方法及
び装置に関する。
り、更に詳しくは、データ圧縮に当てられる処理時間と
達成されるデータ圧縮の関係を最適化するために、リア
ルタイムでデータ圧縮のための符号化テーブルのサイズ
を監視、調整するリアルタイム適応型データ圧縮方法及
び装置に関する。
【０００２】
【従来の技術】ストリングをベースにしたデータ圧縮ア
ルゴリズムは、データ・ストリーム内で繰り返し現れる
文字のストリングを識別し、ストリングを短いコードワ
ードで置換することにより動作する。多くのデータ圧縮
用のスキームおよび装置が従来、知られている。もっと
も一般的なデータ圧縮アルゴリズムは、短いコードワー
ドで置換するデータ・ストリーム内の文字の数を最大限
にしようとする。広義には、文字のストリングは「符号
化」テーブル又はライブラリ内に格納される。符号化テ
ーブル内の各ストリングは、コードワードに対応づけら
れている。データ文字のストリームが、符号化テーブル
内のストリングと比較される。データ文字ストリーム内
のデータ文字の一部が符号化テーブルの文字ストリング
と一致すると、コードワードがデータ・ストリーム内の
そのデータ文字のかわりに使われる。符号化テーブル内
の文字ストリングに一致するデータ・ストリームからの
文字数が多いほど、データ圧縮率も高くなる。従って、
符号化テーブル内の文字ストリングが入力されるデータ
に、より一致すればするほど、データ圧縮量も大きくな
る。
ルゴリズムは、データ・ストリーム内で繰り返し現れる
文字のストリングを識別し、ストリングを短いコードワ
ードで置換することにより動作する。多くのデータ圧縮
用のスキームおよび装置が従来、知られている。もっと
も一般的なデータ圧縮アルゴリズムは、短いコードワー
ドで置換するデータ・ストリーム内の文字の数を最大限
にしようとする。広義には、文字のストリングは「符号
化」テーブル又はライブラリ内に格納される。符号化テ
ーブル内の各ストリングは、コードワードに対応づけら
れている。データ文字のストリームが、符号化テーブル
内のストリングと比較される。データ文字ストリーム内
のデータ文字の一部が符号化テーブルの文字ストリング
と一致すると、コードワードがデータ・ストリーム内の
そのデータ文字のかわりに使われる。符号化テーブル内
の文字ストリングに一致するデータ・ストリームからの
文字数が多いほど、データ圧縮率も高くなる。従って、
符号化テーブル内の文字ストリングが入力されるデータ
に、より一致すればするほど、データ圧縮量も大きくな
る。
【０００３】おそらく、符号化テーブルをデータ・スト
リームにもっとも一致させるもっとも容易な方法は、伝
送されるデータを符号化テーブル中で事前にスキャンす
ることである。理論的には、これは最適なデータ圧縮ア
ルゴリズムになる。理論的には、伝送対象のデータを事
前にスキャンし、最適スキャニング・アルゴリズムを定
式化することができる。
リームにもっとも一致させるもっとも容易な方法は、伝
送されるデータを符号化テーブル中で事前にスキャンす
ることである。理論的には、これは最適なデータ圧縮ア
ルゴリズムになる。理論的には、伝送対象のデータを事
前にスキャンし、最適スキャニング・アルゴリズムを定
式化することができる。
【０００４】しかしながら、変調／復調装置（モデム）
を含んだデータ通信などのリアルタイムの応用では、デ
ータを事前にスキャンし、もっとも効率的なデータ符号
化スキームを設定することは必ずしも可能若しくは望ま
しくない。このようなアプリケーションにおいては、デ
ータの性質が変化し、固定された圧縮スキームでは、非
効率的になったり、有害になったりさえする。したがっ
て、リアルタイムでデータの性質に適応する圧縮スキー
ムが望ましい。
を含んだデータ通信などのリアルタイムの応用では、デ
ータを事前にスキャンし、もっとも効率的なデータ符号
化スキームを設定することは必ずしも可能若しくは望ま
しくない。このようなアプリケーションにおいては、デ
ータの性質が変化し、固定された圧縮スキームでは、非
効率的になったり、有害になったりさえする。したがっ
て、リアルタイムでデータの性質に適応する圧縮スキー
ムが望ましい。
【０００５】従来の適応型リアルタイム・データ圧縮方
法の大部分は、符号化装置および復号化装置の両方で動
的に作成されるテーブルに依存している。ベーコン（Ｂ
ａｃｏｎ）他に付与された、米国特許番号４，６１２，
５３２では、データ・ストリーム内の一連の文字が、符
号化装置の動的に作成されるテーブルに従って符号化さ
れ、復号化装置は、符号化されたデータを復号化するた
めの対応するテーブルを作成するように構成され、符号
化されたデータ構造に依存して、復号化テーブルを動的
に作成する。おもに、符号化装置は、データ・ストリー
ム内の所定の文字に続く文字は、所定の確率で、次に続
く文字の候補集合の内の１つであるという仮定に依存し
ている。したがって、符号化装置は、所定の文字に対し
て、だいたいの発生頻度の順で、データ・ストリーム内
で発生する次に続く文字の候補リストが提示されるテー
ブルを作成する。所定の文字がデータ・ストリーム内で
発生し、その後にテーブル内の文字が続くと、符号化装
置は、テーブル内での文字の順序を示す位置に基づいて
テーブル内の文字を表すため、バイナリ・コードを送信
する。このコードは、もっとも頻繁に発生する候補の場
合に最短となり、余り頻繁に発生しない候補の場合は長
くなる。このテーブルは、所定の文字の後に続く文字の
局所的な発生頻度に基づいて作成および更新され、それ
によりテーブルをローカル・データの性質の変化に従っ
て、動的に変更できるようにする。
法の大部分は、符号化装置および復号化装置の両方で動
的に作成されるテーブルに依存している。ベーコン（Ｂ
ａｃｏｎ）他に付与された、米国特許番号４，６１２，
５３２では、データ・ストリーム内の一連の文字が、符
号化装置の動的に作成されるテーブルに従って符号化さ
れ、復号化装置は、符号化されたデータを復号化するた
めの対応するテーブルを作成するように構成され、符号
化されたデータ構造に依存して、復号化テーブルを動的
に作成する。おもに、符号化装置は、データ・ストリー
ム内の所定の文字に続く文字は、所定の確率で、次に続
く文字の候補集合の内の１つであるという仮定に依存し
ている。したがって、符号化装置は、所定の文字に対し
て、だいたいの発生頻度の順で、データ・ストリーム内
で発生する次に続く文字の候補リストが提示されるテー
ブルを作成する。所定の文字がデータ・ストリーム内で
発生し、その後にテーブル内の文字が続くと、符号化装
置は、テーブル内での文字の順序を示す位置に基づいて
テーブル内の文字を表すため、バイナリ・コードを送信
する。このコードは、もっとも頻繁に発生する候補の場
合に最短となり、余り頻繁に発生しない候補の場合は長
くなる。このテーブルは、所定の文字の後に続く文字の
局所的な発生頻度に基づいて作成および更新され、それ
によりテーブルをローカル・データの性質の変化に従っ
て、動的に変更できるようにする。
【０００６】別の符号化スキームは、国際電信電話諮問
委員会（「ＣＣＩＴＴ」）によりＶ．４２ｂｉｓ規格と
して勧告されており、本明細書中に参照により取り入れ
られている。Ｖ．４２ｂｉｓ規格は、単独のコードワー
ドを使用して複数の文字が符号化されるという点を除
き、前記と同様に動作する。Ｖ．４２ｂｉｓ規格は、ア
ルファベットの各文字に「ルート文字」というラベルを
つける。ルート文字の後に発生するか、ルート文字に続
く文字が、ストリングまたはブランチと呼ばれる。例え
ば、図１に示す従来技術による符号化スキーム、および
ルート文字４の「Ａ」、「Ｂ」、「Ｃ」および「Ｄ」の
それぞれを参照されたい。ルート文字「Ｂ」ぶら下がる
文字は、「Ａ」および「Ｉ」である。さらに、文字
「Ａ」および「Ｉ」にぶら下がる文字がある。このよう
にして、ワード「ＢＡＧ」および「ＢＩＮ」がルート文
字「Ｂ」の下のストリングにスペルアウトされている。
「ＤＥ」、「ＤＯ」、および「ＤＯＧ」のようなルート
文字にぶら下がる文字グループのそれぞれは、ストリン
グ５と呼ばれる。
委員会（「ＣＣＩＴＴ」）によりＶ．４２ｂｉｓ規格と
して勧告されており、本明細書中に参照により取り入れ
られている。Ｖ．４２ｂｉｓ規格は、単独のコードワー
ドを使用して複数の文字が符号化されるという点を除
き、前記と同様に動作する。Ｖ．４２ｂｉｓ規格は、ア
ルファベットの各文字に「ルート文字」というラベルを
つける。ルート文字の後に発生するか、ルート文字に続
く文字が、ストリングまたはブランチと呼ばれる。例え
ば、図１に示す従来技術による符号化スキーム、および
ルート文字４の「Ａ」、「Ｂ」、「Ｃ」および「Ｄ」の
それぞれを参照されたい。ルート文字「Ｂ」ぶら下がる
文字は、「Ａ」および「Ｉ」である。さらに、文字
「Ａ」および「Ｉ」にぶら下がる文字がある。このよう
にして、ワード「ＢＡＧ」および「ＢＩＮ」がルート文
字「Ｂ」の下のストリングにスペルアウトされている。
「ＤＥ」、「ＤＯ」、および「ＤＯＧ」のようなルート
文字にぶら下がる文字グループのそれぞれは、ストリン
グ５と呼ばれる。
【０００７】符号化テーブル内のストリングのそれぞれ
がコードワードに対応づけられている。「ＢＡＧ」とい
うデータ文字のシーケンスが、符号化テーブル内の「Ｂ
ＡＧ」ストリングと照合されるデータ・ストリーム内で
検出されると、ワード「ＢＡＧ」を表すバイナリ・コー
ドワードが、ワード「ＢＡＧ」の代わりに伝送される。
１つのルート文字にぶらさがるすべてのブランチは、あ
わせて、ツリー６と呼ばれる。ツリーは、短い、広い、
長い、狭いなどのさまざまな形になり得る。
がコードワードに対応づけられている。「ＢＡＧ」とい
うデータ文字のシーケンスが、符号化テーブル内の「Ｂ
ＡＧ」ストリングと照合されるデータ・ストリーム内で
検出されると、ワード「ＢＡＧ」を表すバイナリ・コー
ドワードが、ワード「ＢＡＧ」の代わりに伝送される。
１つのルート文字にぶらさがるすべてのブランチは、あ
わせて、ツリー６と呼ばれる。ツリーは、短い、広い、
長い、狭いなどのさまざまな形になり得る。
【０００８】Ｖ．４２ｂｉｓ規格では、各ツリー内のス
トリング５の性質は、データ・ストリーム内のデータに
応じて動的に変更される。このようにして、より最近に
使用されたワードに対する符号化テーブル内の文字は、
データ・ストリーム内のデータに基づいて保存され、増
大する。一方、ツリーのあまり最近使われていないリー
フ文字は枝刈りされ得る。例えば、図１中のワード「Ｂ
ＡＴ」を有するストリングが拡張されて、ワード「ＢＡ
ＴＴＬＥ」を符号化するかもしれない。したがって、も
っとも最近使用したワードのディクショナリが作成さ
れ、符号化テーブルおよび複合化テーブル内にリアルタ
イムで格納される。
トリング５の性質は、データ・ストリーム内のデータに
応じて動的に変更される。このようにして、より最近に
使用されたワードに対する符号化テーブル内の文字は、
データ・ストリーム内のデータに基づいて保存され、増
大する。一方、ツリーのあまり最近使われていないリー
フ文字は枝刈りされ得る。例えば、図１中のワード「Ｂ
ＡＴ」を有するストリングが拡張されて、ワード「ＢＡ
ＴＴＬＥ」を符号化するかもしれない。したがって、も
っとも最近使用したワードのディクショナリが作成さ
れ、符号化テーブルおよび複合化テーブル内にリアルタ
イムで格納される。
【０００９】当業者になじみのある、もう一つのデータ
圧縮スキームは、マイクロコム・ネットワーキング・プ
ロトコル−７（ＭＮＰ−７）である。このプロトコル
は、文字のいくつかのペアを１つのコードワードに対応
させる。理論的には、ペアを対応させ、時間が経過する
と、考えられるすべての組み合わせを含むライブラリを
構築することができる。２５６個の考えられる文字のそ
れぞれが可能性のあるすべてのペアへなるよう組み合わ
される場合、その組み合わせを記憶するためにだいたい
２分の１メガバイトのメモリを要することになる。した
がって、もっとも一般的なペアが、通常、大きさが１０
２４バイトのメモリ内に保存される。新しいペアがメモ
リに加えられるにと、ペアは循環され、メモリから追い
出される。メモリ・サイズに対する実用上の制限のた
め、ＭＮＰ−７は限られたサイズに保たれ、そのテーブ
ルのエントリは、最近使用されたペアが繰り返されると
いう理論に基づいて選択される。
圧縮スキームは、マイクロコム・ネットワーキング・プ
ロトコル−７（ＭＮＰ−７）である。このプロトコル
は、文字のいくつかのペアを１つのコードワードに対応
させる。理論的には、ペアを対応させ、時間が経過する
と、考えられるすべての組み合わせを含むライブラリを
構築することができる。２５６個の考えられる文字のそ
れぞれが可能性のあるすべてのペアへなるよう組み合わ
される場合、その組み合わせを記憶するためにだいたい
２分の１メガバイトのメモリを要することになる。した
がって、もっとも一般的なペアが、通常、大きさが１０
２４バイトのメモリ内に保存される。新しいペアがメモ
リに加えられるにと、ペアは循環され、メモリから追い
出される。メモリ・サイズに対する実用上の制限のた
め、ＭＮＰ−７は限られたサイズに保たれ、そのテーブ
ルのエントリは、最近使用されたペアが繰り返されると
いう理論に基づいて選択される。
【００１０】また、データ圧縮に対する「スライディン
グ・ウィンドウ」アプローチも、当業者になじみがあ
る。もっとも最近に受け取られたデータのブロックが記
憶される（ウィンドウ）。文字が受け取られると、ウィ
ンドウ内の「もっとも古い」文字が落とされていく。こ
のようにして、ウィンドウは連続的に新しいデータで更
新される。各文字が受け取られた後、カレント・ウィン
ドウが一致するストリングがないかどうかレビューされ
る。ストリングがウィンドウ内に発見された場合は、ウ
ィンドウ内のそのストリングへのポインタが復号化テー
ブルに送られる。復号化テーブルはポインタを利用し
て、専用の複製ウィンドウにアクセスし、文字を復号化
する。
グ・ウィンドウ」アプローチも、当業者になじみがあ
る。もっとも最近に受け取られたデータのブロックが記
憶される（ウィンドウ）。文字が受け取られると、ウィ
ンドウ内の「もっとも古い」文字が落とされていく。こ
のようにして、ウィンドウは連続的に新しいデータで更
新される。各文字が受け取られた後、カレント・ウィン
ドウが一致するストリングがないかどうかレビューされ
る。ストリングがウィンドウ内に発見された場合は、ウ
ィンドウ内のそのストリングへのポインタが復号化テー
ブルに送られる。復号化テーブルはポインタを利用し
て、専用の複製ウィンドウにアクセスし、文字を復号化
する。
【００１１】
【発明が解決しようとする課題】当業者にはわかるであ
ろうが、前記のデータ圧縮システムは、データ文字がラ
ンダムではないという仮定のもと動作する。このスキー
ムは、あるワードが一度発生すると、それは、再度発生
するであろうと仮定する。さらに、Ｖ．４２ｂｉｓは、
文法規則により定義されるもののような、人間の言語に
おける文字間の固有の相関関係に依存している。
ろうが、前記のデータ圧縮システムは、データ文字がラ
ンダムではないという仮定のもと動作する。このスキー
ムは、あるワードが一度発生すると、それは、再度発生
するであろうと仮定する。さらに、Ｖ．４２ｂｉｓは、
文法規則により定義されるもののような、人間の言語に
おける文字間の固有の相関関係に依存している。
【００１２】前記のデータ圧縮スキームのすべてにおい
て、符号化テーブルが大きいほど、記憶されるストリン
グの数が増えるか、記憶されるストリングが長くなる
か、あるいはその両方となり、符号化テーブルに記憶さ
れるストリングの数と長さが大きくなればなるほど、デ
ータ文字ストリームが復号化テーブル内のストリングと
一致する可能性が高くなる。したがって、符号化テーブ
ルが大きいほど、データ圧縮が大きくなるというのは、
正しいことが多い。
て、符号化テーブルが大きいほど、記憶されるストリン
グの数が増えるか、記憶されるストリングが長くなる
か、あるいはその両方となり、符号化テーブルに記憶さ
れるストリングの数と長さが大きくなればなるほど、デ
ータ文字ストリームが復号化テーブル内のストリングと
一致する可能性が高くなる。したがって、符号化テーブ
ルが大きいほど、データ圧縮が大きくなるというのは、
正しいことが多い。
【００１３】任意のスキーム内の総ツリー・ブランチの
幅および長さは、符号化テーブルに割り当てられる総メ
モリ・スペースにより制限される。Ｖ．４２ｂｉｓ規格
を使用するモデムでは、通常、符号化テーブルに割り当
てられるメモリ・スペースは、３２，７６８バイトのメ
モリで、２０４８個のエントリ又はストリングを保持す
るように最初は設定される。
幅および長さは、符号化テーブルに割り当てられる総メ
モリ・スペースにより制限される。Ｖ．４２ｂｉｓ規格
を使用するモデムでは、通常、符号化テーブルに割り当
てられるメモリ・スペースは、３２，７６８バイトのメ
モリで、２０４８個のエントリ又はストリングを保持す
るように最初は設定される。
【００１４】符号化テーブルの記憶に消費されるメモリ
・スペースを制限する必要性以外に、符号化テーブルの
サイズは、２つのトレードオフによっても制限される。
まず第一に、モデムはルート文字の下の各ストリングを
レビューし、データ・ストリーム内の文字と一致するス
トリングを発見しなければならない。この文字ストリー
ム内の各文字をレビューし、ストリーム内の文字を符号
化テーブル内のストリングと一致させようとする処理
は、膨大な処理時間を要する。したがって、符号化テー
ブルのサイズの制限には、大きな符号化テーブルを使う
ことにより、より多くのストリングをデータ・ストリー
ムに一致させ、より大きなデータ圧縮を達成させること
と、より大きな符号化テーブルを利用することにより生
じる実行時間、ひいてはデータ・スループット時間の低
速化との間の固有のトレードオフがある。
・スペースを制限する必要性以外に、符号化テーブルの
サイズは、２つのトレードオフによっても制限される。
まず第一に、モデムはルート文字の下の各ストリングを
レビューし、データ・ストリーム内の文字と一致するス
トリングを発見しなければならない。この文字ストリー
ム内の各文字をレビューし、ストリーム内の文字を符号
化テーブル内のストリングと一致させようとする処理
は、膨大な処理時間を要する。したがって、符号化テー
ブルのサイズの制限には、大きな符号化テーブルを使う
ことにより、より多くのストリングをデータ・ストリー
ムに一致させ、より大きなデータ圧縮を達成させること
と、より大きな符号化テーブルを利用することにより生
じる実行時間、ひいてはデータ・スループット時間の低
速化との間の固有のトレードオフがある。
【００１５】第２のトレードオフは、符号化テーブルの
サイズを大きくすると、コードワードのサイズを大きく
する必要があるという点である。例えば、８ビットのコ
ードワードは、最大で２５６（２8 ）ストリングを表
す。したがって、符号化テーブルのサイズを２５６個以
上のストリングを格納するために大きくすると、より大
きなコードワードを使用しなければならない。従って、
符号化テーブルのストリングがより多く及び長くなる
と、さらに多くのストリングを一致させることにより圧
縮を増加させ得るが、必要となるコードワードの数が増
加し、コードワード・サイズが大きくなるため、スルー
プットおよび圧縮率が低下する。他方、符号化テーブル
が小さいと、ストリング数は少なくなるが、コードワー
ドの長さは短くなる。
サイズを大きくすると、コードワードのサイズを大きく
する必要があるという点である。例えば、８ビットのコ
ードワードは、最大で２５６（２8 ）ストリングを表
す。したがって、符号化テーブルのサイズを２５６個以
上のストリングを格納するために大きくすると、より大
きなコードワードを使用しなければならない。従って、
符号化テーブルのストリングがより多く及び長くなる
と、さらに多くのストリングを一致させることにより圧
縮を増加させ得るが、必要となるコードワードの数が増
加し、コードワード・サイズが大きくなるため、スルー
プットおよび圧縮率が低下する。他方、符号化テーブル
が小さいと、ストリング数は少なくなるが、コードワー
ドの長さは短くなる。
【００１６】当業者にはよく知られているように、前記
データ圧縮／符号化スキームは、データが強い相関関係
を有する、すなわち伝送中のファイルがテキストまたは
数（ただし、その両方ではない）であると事前に決定さ
れ、データはランダムではない応用形態を前提とし、そ
のような応用形態に最も適している。しかしながら、リ
アルタイム通信システムのようなデータのタイプが予測
不可能で、時間を経ると変化する応用形態では、前記方
法は最適ではないコードを用いることになる。前記圧縮
スキームは、固定サイズの符号化テーブル内でコードワ
ードをリアルタイムで再割当てすることによってデータ
間の相関関係の変化に適応するのみである。
データ圧縮／符号化スキームは、データが強い相関関係
を有する、すなわち伝送中のファイルがテキストまたは
数（ただし、その両方ではない）であると事前に決定さ
れ、データはランダムではない応用形態を前提とし、そ
のような応用形態に最も適している。しかしながら、リ
アルタイム通信システムのようなデータのタイプが予測
不可能で、時間を経ると変化する応用形態では、前記方
法は最適ではないコードを用いることになる。前記圧縮
スキームは、固定サイズの符号化テーブル内でコードワ
ードをリアルタイムで再割当てすることによってデータ
間の相関関係の変化に適応するのみである。
【００１７】したがって、あらゆるタイプのデータまた
はデータのタイプの分布に関して、より大きな動的適応
性を達成する適応型データ圧縮方法を提供する必要があ
る。
はデータのタイプの分布に関して、より大きな動的適応
性を達成する適応型データ圧縮方法を提供する必要があ
る。
【００１８】さらに、ランダム・データまたは擬似ラン
ダム・データの圧縮の試行に費やされる処理時間を制限
する必要性を調和させ、非ランダム（相関関係のある）
データの高率でのデータ圧縮を達成するリアルタイム・
データ符号化スキームが必要とされている。
ダム・データの圧縮の試行に費やされる処理時間を制限
する必要性を調和させ、非ランダム（相関関係のある）
データの高率でのデータ圧縮を達成するリアルタイム・
データ符号化スキームが必要とされている。
【００１９】さらに、同一文字から成る長いストリング
を符号化テーブルに渡すことを排除する符号化スキーム
が必要とされている。具体的には、同一文字から成る１
つのストリングがモデムで受け取られると、モデムは、
符号化テーブルを変更し、伝送前に圧縮される同一文字
の非常に長いストリングを格納するようにする。この長
い文字ストリングは、符号化テーブルおよび復号化テー
ブルに対する歪みとなり、しばしば、Ｖ．４２ｂｉｓ規
格のユーザに非効率を生じさせる。具体的には、符号化
テーブル内の貴重なスペースが、同一文字のストリング
を格納するために使われ、このストリングは、通常、デ
ータ伝送の間役に立たない。
を符号化テーブルに渡すことを排除する符号化スキーム
が必要とされている。具体的には、同一文字から成る１
つのストリングがモデムで受け取られると、モデムは、
符号化テーブルを変更し、伝送前に圧縮される同一文字
の非常に長いストリングを格納するようにする。この長
い文字ストリングは、符号化テーブルおよび復号化テー
ブルに対する歪みとなり、しばしば、Ｖ．４２ｂｉｓ規
格のユーザに非効率を生じさせる。具体的には、符号化
テーブル内の貴重なスペースが、同一文字のストリング
を格納するために使われ、このストリングは、通常、デ
ータ伝送の間役に立たない。
【００２０】本発明の目的は、最小処理時間にて最大デ
ータ圧縮を提供するために、符号化テーブルおよび復号
化テーブルのサイズを最適化するデータ圧縮スキームを
提供することである。
ータ圧縮を提供するために、符号化テーブルおよび復号
化テーブルのサイズを最適化するデータ圧縮スキームを
提供することである。
【００２１】本発明の第２の目的は、データのストリー
ム内のデータ文字間の検出された相関関係に応えて符号
化テーブルのサイズを調整し、それにより、よりランダ
ムなデータの場合には、符号化テーブルのサイズが減ら
され、相関関係がより強いデータの場合には符号化テー
ブルのサイズが増やされる、データ通信で利用されるデ
ータ圧縮スキームを提供することである。
ム内のデータ文字間の検出された相関関係に応えて符号
化テーブルのサイズを調整し、それにより、よりランダ
ムなデータの場合には、符号化テーブルのサイズが減ら
され、相関関係がより強いデータの場合には符号化テー
ブルのサイズが増やされる、データ通信で利用されるデ
ータ圧縮スキームを提供することである。
【００２２】本発明の第３の目的とは、データが符号化
テーブルに渡される前に、同一データ文字の連続発生が
ラン・レングス・エンコーダで符号化され、それにより
モデムの符号化テーブルの悪化を防止する、データ通信
ネットワークでモデムとともに使用するためのデータ圧
縮スキームを提供することである。
テーブルに渡される前に、同一データ文字の連続発生が
ラン・レングス・エンコーダで符号化され、それにより
モデムの符号化テーブルの悪化を防止する、データ通信
ネットワークでモデムとともに使用するためのデータ圧
縮スキームを提供することである。
【００２３】
【課題を解決するための手段】本発明は、データのラン
ダム対非ランダムの性質が判断され、この情報が、符号
化テーブルのサイズを調整するために使われ、データ圧
縮およびデータ圧縮速度を最適化するリアルタイム・デ
ータ圧縮用スキームを提供する。具体的には、相関関係
が強いデータの場合、より大きなデータ圧縮を達成する
ために符号化テーブルのサイズを大きくする。相関関係
が弱いデータの場合には、よい性能をだすために符号化
テーブルの大きさを小さくする。ランダム・データまた
は擬似ランダム・データの場合は、符号化テーブルのサ
イズは、データを圧縮しようとして費やされる時間を削
減し、短いコードワードを使うために、縮小される。
ダム対非ランダムの性質が判断され、この情報が、符号
化テーブルのサイズを調整するために使われ、データ圧
縮およびデータ圧縮速度を最適化するリアルタイム・デ
ータ圧縮用スキームを提供する。具体的には、相関関係
が強いデータの場合、より大きなデータ圧縮を達成する
ために符号化テーブルのサイズを大きくする。相関関係
が弱いデータの場合には、よい性能をだすために符号化
テーブルの大きさを小さくする。ランダム・データまた
は擬似ランダム・データの場合は、符号化テーブルのサ
イズは、データを圧縮しようとして費やされる時間を削
減し、短いコードワードを使うために、縮小される。
【００２４】本発明は、データ文字のストリームを圧縮
するためのコンピュータ・システムで動作する。コンピ
ュータ・システムは、文字から成る複数のストリングを
有する符号化テーブルを具備し、符号化テーブル内の文
字ストリングは、文字のストリームの一部が符号化テー
ブル内の文字ストリングの１つと一致した際、データ文
字のストリームの部分と置換されるコードワードに関連
づけられており、これにより、文字のストリームの部分
は、対応するコードワードで置き換えられる。本発明
は、データ圧縮の効率およびデータ圧縮率を改善するた
めに符号化テーブルのサイズを制御する装置および方法
である。この方法は、入力されるデータ文字間の相関関
係を判断するステップと、入力データ文字間の判断され
た相関関係に基づいて、符号化テーブルに割り当てられ
るメモリ・スペースを調整するステップを有する。テー
ブルに割り当てられるメモリ・スペースを調整する際に
講じられるステップは、データ文字間の判断された相関
関係に応えて性能指標を調整し、性能指標が事前に決定
した第１の値を上回ると、符号化テーブルに割り当てら
れるメモリ・スペースを縮小し、性能指標が事前に決定
した第２の値を下回ると、符号化テーブルに割り当てら
れるメモリ・スペースを拡大する。
するためのコンピュータ・システムで動作する。コンピ
ュータ・システムは、文字から成る複数のストリングを
有する符号化テーブルを具備し、符号化テーブル内の文
字ストリングは、文字のストリームの一部が符号化テー
ブル内の文字ストリングの１つと一致した際、データ文
字のストリームの部分と置換されるコードワードに関連
づけられており、これにより、文字のストリームの部分
は、対応するコードワードで置き換えられる。本発明
は、データ圧縮の効率およびデータ圧縮率を改善するた
めに符号化テーブルのサイズを制御する装置および方法
である。この方法は、入力されるデータ文字間の相関関
係を判断するステップと、入力データ文字間の判断され
た相関関係に基づいて、符号化テーブルに割り当てられ
るメモリ・スペースを調整するステップを有する。テー
ブルに割り当てられるメモリ・スペースを調整する際に
講じられるステップは、データ文字間の判断された相関
関係に応えて性能指標を調整し、性能指標が事前に決定
した第１の値を上回ると、符号化テーブルに割り当てら
れるメモリ・スペースを縮小し、性能指標が事前に決定
した第２の値を下回ると、符号化テーブルに割り当てら
れるメモリ・スペースを拡大する。
【００２５】本発明の典型的動作では、データ圧縮の効
率および圧縮率を改善するために符号化テーブルを制御
する方法は、以下のステップを含む。まず、コンピュー
タ・システムに入力されるデータ文字のストリームの圧
縮率を決定するステップで、圧縮率は、コンピュータ・
システムに入力される文字数を、コンピュータ・システ
ムから出力されるデータ文字ストリーム内のデータ文字
数で割ったものに等しい。また、使用カウントを決定す
るステップを含み、使用カウントは、符号化テーブルの
ツリーの平均幅に比例する。また、圧縮率および使用カ
ウントを利用して性能指標を計算するステップ、および
性能指標の値に基づいて符号化テーブルに割り当てられ
るメモリ・スペースを増減するステップを含む。性能指
標は、コンピュータ・システムに入力されるデータ文字
のストリーム中のデータ文字間の相関関係を示す。
率および圧縮率を改善するために符号化テーブルを制御
する方法は、以下のステップを含む。まず、コンピュー
タ・システムに入力されるデータ文字のストリームの圧
縮率を決定するステップで、圧縮率は、コンピュータ・
システムに入力される文字数を、コンピュータ・システ
ムから出力されるデータ文字ストリーム内のデータ文字
数で割ったものに等しい。また、使用カウントを決定す
るステップを含み、使用カウントは、符号化テーブルの
ツリーの平均幅に比例する。また、圧縮率および使用カ
ウントを利用して性能指標を計算するステップ、および
性能指標の値に基づいて符号化テーブルに割り当てられ
るメモリ・スペースを増減するステップを含む。性能指
標は、コンピュータ・システムに入力されるデータ文字
のストリーム中のデータ文字間の相関関係を示す。
【００２６】このようにして、本発明は、入力されるデ
ータ文字間の相関関係を検出するために、（１）実際に
達成されるデータ圧縮率、（２）符号化テーブル中の１
つ以上のツリーの幅という２つの基準を利用する。当業
者により符号化ディクショナリと呼ばれることもある、
符号化テーブルに割り当てられるメモリ・スペースは、
現在達成されているデータ圧縮率および符号化テーブル
のツリーの見積もられた特徴に応じて拡大または縮小さ
れる。したがって、符号化テーブルのサイズは、入力デ
ータのランダムまたは非ランダム性質に従って調整さ
れ、それによりデータを圧縮しようとして費やされる時
間を制限しつつ、圧縮を最適化する。
ータ文字間の相関関係を検出するために、（１）実際に
達成されるデータ圧縮率、（２）符号化テーブル中の１
つ以上のツリーの幅という２つの基準を利用する。当業
者により符号化ディクショナリと呼ばれることもある、
符号化テーブルに割り当てられるメモリ・スペースは、
現在達成されているデータ圧縮率および符号化テーブル
のツリーの見積もられた特徴に応じて拡大または縮小さ
れる。したがって、符号化テーブルのサイズは、入力デ
ータのランダムまたは非ランダム性質に従って調整さ
れ、それによりデータを圧縮しようとして費やされる時
間を制限しつつ、圧縮を最適化する。
【００２７】データ文字間の圧縮率を決定する本発明の
典型的な方法にさらに詳細に述べると、当業者は、今日
販売されているモデムは、モデムにより達成される圧縮
率を監視し、更新するということが分かるであろう。例
えば、本発明の譲受人であるヘイズ・マイクロコンピュ
ータ製品社（Ｈａｙｅｓ Ｍｉｃｒｏｃｏｍｐｕｔｅｒ
Ｐｒｏｄｕｃｔｓ Ｉｎｃ．）が販売するモデムで
は、モデムが、伝送するためにコンピュータから受け取
られる、固定数の文字の後に、例えば、５０００文字の
後に圧縮率を計算する。そして、圧縮率が低いと、弱い
相関関係、ランダム、または擬似乱数となりがちであ
る。なぜなら、そのようなデータは比較的圧縮不可能な
ためである。また、圧縮率が高くなると、データ文字間
の相関関係も強くなる。
典型的な方法にさらに詳細に述べると、当業者は、今日
販売されているモデムは、モデムにより達成される圧縮
率を監視し、更新するということが分かるであろう。例
えば、本発明の譲受人であるヘイズ・マイクロコンピュ
ータ製品社（Ｈａｙｅｓ Ｍｉｃｒｏｃｏｍｐｕｔｅｒ
Ｐｒｏｄｕｃｔｓ Ｉｎｃ．）が販売するモデムで
は、モデムが、伝送するためにコンピュータから受け取
られる、固定数の文字の後に、例えば、５０００文字の
後に圧縮率を計算する。そして、圧縮率が低いと、弱い
相関関係、ランダム、または擬似乱数となりがちであ
る。なぜなら、そのようなデータは比較的圧縮不可能な
ためである。また、圧縮率が高くなると、データ文字間
の相関関係も強くなる。
【００２８】本発明で、処理中のデータ中の文字の相関
関係を判断するために利用される第２の基準は、符号化
テーブル内のツリーの形である。例えば、モデムがラン
ダム・データを圧縮しようとしている場合、ツリーの幅
は、通常、比較的に高くなる。なぜなら、任意の文字が
別の文字の後に続きそうになるからである。実際には、
２５６個の文字が、各ルート文字に直接ぶらさがるかも
しれない。したがって、ランダム・データの場合、符号
化テーブル内のツリーの幅は広くなる傾向がある。反対
に、相関関係が強いデータを受け取る符号化テーブル
は、長く狭いツリーを持つと仮定される。本発明は、ツ
リーが長くて狭いか、あるいは短くて広いということを
検出する。
関係を判断するために利用される第２の基準は、符号化
テーブル内のツリーの形である。例えば、モデムがラン
ダム・データを圧縮しようとしている場合、ツリーの幅
は、通常、比較的に高くなる。なぜなら、任意の文字が
別の文字の後に続きそうになるからである。実際には、
２５６個の文字が、各ルート文字に直接ぶらさがるかも
しれない。したがって、ランダム・データの場合、符号
化テーブル内のツリーの幅は広くなる傾向がある。反対
に、相関関係が強いデータを受け取る符号化テーブル
は、長く狭いツリーを持つと仮定される。本発明は、ツ
リーが長くて狭いか、あるいは短くて広いということを
検出する。
【００２９】データ文字間の相関関係を判断するために
利用される第２の基準は、「使用カウント」と呼ばれて
いる。使用カウントをさらに詳細に述べると、使用カウ
ントは、ストリング一致プログラム、符号化テーブル・
エントリ削除ループ・プログラムの中に挿入されるか、
あるいは別個のプログラムとなるプログラム・モジュー
ルを使用して決定される。使用カウントは、後述される
ように、比較的に低い処理速度を使うため、エントリ削
除プログラムに挿入されるのが望ましい。
利用される第２の基準は、「使用カウント」と呼ばれて
いる。使用カウントをさらに詳細に述べると、使用カウ
ントは、ストリング一致プログラム、符号化テーブル・
エントリ削除ループ・プログラムの中に挿入されるか、
あるいは別個のプログラムとなるプログラム・モジュー
ルを使用して決定される。使用カウントは、後述される
ように、比較的に低い処理速度を使うため、エントリ削
除プログラムに挿入されるのが望ましい。
【００３０】当業者にはよく知られているように、エン
トリ削除プログラムは、定期的に呼び出され、削除対象
となるリーフ文字を発見するために、メモリ内のエント
リを順次に探索する。エントリ削除プログラムは、削除
するリーフ文字を探してすべてのエントリの中を進み、
使用カウントは、リーフ文字を見つける前にレビューさ
れる文字の数に基づいたツリーの幅である。使用カウン
トは、エントリ削除プログラムの複数の呼び出しにわた
って保存される。そして、正規化された使用カウント
は、以下の公式を使用して計算される。
トリ削除プログラムは、定期的に呼び出され、削除対象
となるリーフ文字を発見するために、メモリ内のエント
リを順次に探索する。エントリ削除プログラムは、削除
するリーフ文字を探してすべてのエントリの中を進み、
使用カウントは、リーフ文字を見つける前にレビューさ
れる文字の数に基づいたツリーの幅である。使用カウン
トは、エントリ削除プログラムの複数の呼び出しにわた
って保存される。そして、正規化された使用カウント
は、以下の公式を使用して計算される。
【００３１】
【数１】正規化使用カウント＝（総使用カウント）／
（エントリ削除プログラム呼出回数） 使用カウントは、削除されるリーフが発見される前に調
べられる文字の数であり、使用カウントは、エントリ削
除プログラムの多数の呼出にわたって平均化され、ツリ
ーの幅の概算に妥当かつ安定した基盤を提供する。この
ようにして、正規化使用カウントは、符号化テーブル内
のツリーの形を見積もるために利用される。必要であれ
ば、符号化テーブル内のツリーの平均幅は、以下の公式
を使って計算することができる。
（エントリ削除プログラム呼出回数） 使用カウントは、削除されるリーフが発見される前に調
べられる文字の数であり、使用カウントは、エントリ削
除プログラムの多数の呼出にわたって平均化され、ツリ
ーの幅の概算に妥当かつ安定した基盤を提供する。この
ようにして、正規化使用カウントは、符号化テーブル内
のツリーの形を見積もるために利用される。必要であれ
ば、符号化テーブル内のツリーの平均幅は、以下の公式
を使って計算することができる。
【００３２】平均幅＝１＋２＊（正規化使用カウント） このようにして、ツリーの幅は、エントリ削除プロセス
内の使用カウントによりカウントされる文字の総数に基
づく正規化使用カウントの値を使用して概算される。正
規化使用カウント値が低い場合、ツリーは狭いと見積も
られ、データの強い相関関係を示す。低い正規化使用カ
ウントは、ルート文字とリーフ文字の間に文字が多くあ
るために生じる。この場合、性能指標は、所定の値によ
り増分（インクリメント）される。他方、正規化使用カ
ウントが高い場合、データはよりランダムである。この
場合、性能指標は減分（デクリメント）される。
内の使用カウントによりカウントされる文字の総数に基
づく正規化使用カウントの値を使用して概算される。正
規化使用カウント値が低い場合、ツリーは狭いと見積も
られ、データの強い相関関係を示す。低い正規化使用カ
ウントは、ルート文字とリーフ文字の間に文字が多くあ
るために生じる。この場合、性能指標は、所定の値によ
り増分（インクリメント）される。他方、正規化使用カ
ウントが高い場合、データはよりランダムである。この
場合、性能指標は減分（デクリメント）される。
【００３３】入力データのランダム対非ランダムの性質
を判断し、それに応えて符号化テーブルのサイズを調整
するための方法はいろいろなものが有り得る。典型的に
は、本発明では、プロセッサは、データ文字のストリー
ム内の文字間の相関関係に対応する「性能指標」を作成
する。性能指標は、初期値（５０）が与えられ、その値
は、圧縮率と正規化使用カウントにより定義されるよう
に、受け取られるデータのストリーム内のデータ文字間
の相関関係に基づいて増分または減分される。性能指標
が事前に決めた最大値または最小値（それぞれ１００ま
たは０）に達すると、符号化テーブルのサイズは縮小ま
たは拡大される。符号化テーブルのサイズを拡大または
縮小した後、性能指標は中間値（５０）に再設定され、
上記プロセスを反復する。
を判断し、それに応えて符号化テーブルのサイズを調整
するための方法はいろいろなものが有り得る。典型的に
は、本発明では、プロセッサは、データ文字のストリー
ム内の文字間の相関関係に対応する「性能指標」を作成
する。性能指標は、初期値（５０）が与えられ、その値
は、圧縮率と正規化使用カウントにより定義されるよう
に、受け取られるデータのストリーム内のデータ文字間
の相関関係に基づいて増分または減分される。性能指標
が事前に決めた最大値または最小値（それぞれ１００ま
たは０）に達すると、符号化テーブルのサイズは縮小ま
たは拡大される。符号化テーブルのサイズを拡大または
縮小した後、性能指標は中間値（５０）に再設定され、
上記プロセスを反復する。
【００３４】本発明の典型的な例では、２つの基準（圧
縮率および符号化テーブルの特徴）が、ともに、性能指
標が増分されるのか、あるいは減分されるのかを判断す
る。データ圧縮率が１未満の場合、コンピュータからモ
デムに入力されるデータは、実際には、変調されデータ
通信回線上に出力される前に拡張されている。本発明の
このケースでは、性能指標は大きな値で減分される。圧
縮率が１をわずかに上回る場合、性能指標はより小さな
値で減分される。圧縮率が１をはるかに越える場合、性
能指標はより大きな値で増分される。符号化テーブル内
のツリーが狭いと判断されると、性能指標は増分される
が、ツリーが広いと判断されると、性能指標は減分され
る。ツリーの幅は、計算された正規化使用カウントで評
価される。
縮率および符号化テーブルの特徴）が、ともに、性能指
標が増分されるのか、あるいは減分されるのかを判断す
る。データ圧縮率が１未満の場合、コンピュータからモ
デムに入力されるデータは、実際には、変調されデータ
通信回線上に出力される前に拡張されている。本発明の
このケースでは、性能指標は大きな値で減分される。圧
縮率が１をわずかに上回る場合、性能指標はより小さな
値で減分される。圧縮率が１をはるかに越える場合、性
能指標はより大きな値で増分される。符号化テーブル内
のツリーが狭いと判断されると、性能指標は増分される
が、ツリーが広いと判断されると、性能指標は減分され
る。ツリーの幅は、計算された正規化使用カウントで評
価される。
【００３５】入力データ・ストリーム内の文字間の相関
関係は、このようにして、計算された数、つまり性能指
標により特徴付けられる。性能指標は、圧縮率および利
用カウンタに基づいて調整される。性能指標がゼロ
（０）以下の値になると、データが、弱い相関関係を有
する、ランダム、または擬ランダムであるため、符号化
テーブルのサイズは縮小させられる。符号化テーブルの
サイズを縮小すると、符号化テーブル内の文字ストリン
グとデータ・ストリーム内の文字の間の一致を探すのに
費やされる処理時間が減少する。さらに、符号化テーブ
ルのサイズを縮小すると、コードワードのサイズも小さ
くなる。
関係は、このようにして、計算された数、つまり性能指
標により特徴付けられる。性能指標は、圧縮率および利
用カウンタに基づいて調整される。性能指標がゼロ
（０）以下の値になると、データが、弱い相関関係を有
する、ランダム、または擬ランダムであるため、符号化
テーブルのサイズは縮小させられる。符号化テーブルの
サイズを縮小すると、符号化テーブル内の文字ストリン
グとデータ・ストリーム内の文字の間の一致を探すのに
費やされる処理時間が減少する。さらに、符号化テーブ
ルのサイズを縮小すると、コードワードのサイズも小さ
くなる。
【００３６】同様に、性能指標が１００以上の値になる
と、入力データ・ストリームは相関関係が強い文字を含
み、よって、プロセッサは符号化テーブルに割り当てる
メモリ・スペースを拡大する。これにより、符号化テー
ブルに記憶できるようになるストリングがさらに多くな
るか、さらに長くなるか、あるいはその両方となるた
め、データ圧縮を増大できる。
と、入力データ・ストリームは相関関係が強い文字を含
み、よって、プロセッサは符号化テーブルに割り当てる
メモリ・スペースを拡大する。これにより、符号化テー
ブルに記憶できるようになるストリングがさらに多くな
るか、さらに長くなるか、あるいはその両方となるた
め、データ圧縮を増大できる。
【００３７】計算された性能指標が第１しきい値と第２
しきい値（０と１００）の間である場合、符号化テーブ
ルに割り当てられた現在のメモリ・スペースは、許容で
きるプロセッサ時間を使ったデータ圧縮の最適レベルを
生成すると仮定される。したがって、符号化テーブルの
サイズは変更されない。
しきい値（０と１００）の間である場合、符号化テーブ
ルに割り当てられた現在のメモリ・スペースは、許容で
きるプロセッサ時間を使ったデータ圧縮の最適レベルを
生成すると仮定される。したがって、符号化テーブルの
サイズは変更されない。
【００３８】前述した２つの基準は結合されて、性能指
標をもたらす。例えば、圧縮率が低く、正規化使用カウ
ントが低い場合（ランダム・データ）、性能指標は大き
く減らされ、性能指標がゼロ未満であると、符号化テー
ブルに割り当てられるメモリ・スペースは少なくなる。
他方、圧縮率が高く、正規化使用カウントが高いと（相
関関係が強いデータ）、性能指標は増やされ、符号化テ
ーブルに割り当てられるメモリ・スペースが増やされ
る。
標をもたらす。例えば、圧縮率が低く、正規化使用カウ
ントが低い場合（ランダム・データ）、性能指標は大き
く減らされ、性能指標がゼロ未満であると、符号化テー
ブルに割り当てられるメモリ・スペースは少なくなる。
他方、圧縮率が高く、正規化使用カウントが高いと（相
関関係が強いデータ）、性能指標は増やされ、符号化テ
ーブルに割り当てられるメモリ・スペースが増やされ
る。
【００３９】性能指標の増分量または減分量は、本明細
書中、「デルタ」値と呼ばれ、デルタ値は、基準が平均
値からどれほど偏向するかに従って、前述の基準のそれ
ぞれの中で上げ下げすることができる。したがって、シ
ステムは、データの相関関係（または非相関関係）の度
合いに対する調整可能な感度を備える。
書中、「デルタ」値と呼ばれ、デルタ値は、基準が平均
値からどれほど偏向するかに従って、前述の基準のそれ
ぞれの中で上げ下げすることができる。したがって、シ
ステムは、データの相関関係（または非相関関係）の度
合いに対する調整可能な感度を備える。
【００４０】符号化テーブルでは、データが最初にモデ
ムで受け取られるときは、符号化テーブルに割り当てら
れるメモリ・スペースは最大２０４８個のエントリまで
許容される。したがって、この符号化テーブルは２０４
８エントリ・テーブルであると呼ばれる。符号化テーブ
ルに割り当てられる典型的な総メモリ・スペースは、５
１２個、１０２４個、２０４８個、４０９６個、８１９
２個、または１６３８４個のエントリを許容する。符号
化テーブルは、性能指標の値により指示され、以上のサ
イズのなかで上がり下がりする。符号化テーブルのサイ
ズが変更されると、コードワードのサイズが変更され
る。したがって、符号化テーブルが５１２個、１０２４
個、２０４８個、４０９６個、８１９２個または１６３
８４個エントリを保持する場合、コードワードは、それ
ぞれ９ビット、１０ビット、１１ビット、１２ビット、
１３ビットまたは１４ビットとなる。
ムで受け取られるときは、符号化テーブルに割り当てら
れるメモリ・スペースは最大２０４８個のエントリまで
許容される。したがって、この符号化テーブルは２０４
８エントリ・テーブルであると呼ばれる。符号化テーブ
ルに割り当てられる典型的な総メモリ・スペースは、５
１２個、１０２４個、２０４８個、４０９６個、８１９
２個、または１６３８４個のエントリを許容する。符号
化テーブルは、性能指標の値により指示され、以上のサ
イズのなかで上がり下がりする。符号化テーブルのサイ
ズが変更されると、コードワードのサイズが変更され
る。したがって、符号化テーブルが５１２個、１０２４
個、２０４８個、４０９６個、８１９２個または１６３
８４個エントリを保持する場合、コードワードは、それ
ぞれ９ビット、１０ビット、１１ビット、１２ビット、
１３ビットまたは１４ビットとなる。
【００４１】前述の動作の結果は、データの相関関係が
弱いか、相関関係がない場合、符号化テーブルのサイズ
は減らされるが、データの相関関係が強い場合は、符号
化テーブルのサイズは増やされるということである。符
号化テーブルのサイズを減らすと、データ圧縮に当てら
れるマイクロプロセッサ時間量とコードワードのサイズ
が減少する。これは、データがランダムであるために圧
縮できない場合に適切であり、データの相関関係が弱い
場合に、性能を改善することができる。他方、符号化テ
ーブルのサイズを増やすと、データ圧縮に当てられるマ
イクロプロセッサ時間量が増える。
弱いか、相関関係がない場合、符号化テーブルのサイズ
は減らされるが、データの相関関係が強い場合は、符号
化テーブルのサイズは増やされるということである。符
号化テーブルのサイズを減らすと、データ圧縮に当てら
れるマイクロプロセッサ時間量とコードワードのサイズ
が減少する。これは、データがランダムであるために圧
縮できない場合に適切であり、データの相関関係が弱い
場合に、性能を改善することができる。他方、符号化テ
ーブルのサイズを増やすと、データ圧縮に当てられるマ
イクロプロセッサ時間量が増える。
【００４２】本発明は、多くのストリング符号化および
圧縮スキームで使用できる。これらの圧縮スキームは、
文字のバッファ（履歴）を保持し、データ内のストリン
グを、同じデータ・ストリングの以前の発生にあわされ
たコードワードで置き換えることにより動作する。バッ
ファ・サイズ対コードワード・サイズおよび処理時間と
いう点での同様のトレードオフは、これらのストリング
・ベースの圧縮スキームのすべてに当てはまり、本発明
は、計算された性能指標に応えてバッファ・サイズを動
的に変更することにより、性能の同様な最適化を達成す
るために利用できる。したがって、本発明は、Ｖ．４２
ｂｉｓ、ＭＮＰ−７符号化アルゴリズム、およびそれ以
外の多くのデータ圧縮または符号化スキームで有効であ
る。
圧縮スキームで使用できる。これらの圧縮スキームは、
文字のバッファ（履歴）を保持し、データ内のストリン
グを、同じデータ・ストリングの以前の発生にあわされ
たコードワードで置き換えることにより動作する。バッ
ファ・サイズ対コードワード・サイズおよび処理時間と
いう点での同様のトレードオフは、これらのストリング
・ベースの圧縮スキームのすべてに当てはまり、本発明
は、計算された性能指標に応えてバッファ・サイズを動
的に変更することにより、性能の同様な最適化を達成す
るために利用できる。したがって、本発明は、Ｖ．４２
ｂｉｓ、ＭＮＰ−７符号化アルゴリズム、およびそれ以
外の多くのデータ圧縮または符号化スキームで有効であ
る。
【００４３】また、本発明は、符号化テーブルの歪みを
防止するのに役立つ前処理機能も備える。本発明の通常
の環境では、ラン・レングス・エンコーダは、モデム内
でデータ圧縮回路（符号化テーブル）の前に位置してい
る。ラン・レングス・エンコーダは、コンピュータから
モデムに送信されているデータ内の同一文字から成るス
トリングを認識し、それによりコードに置換する。それ
から、コードは符号化テーブルで符号化され、モデムか
ら伝送される。コードは、復号化テーブルで受け取られ
てから復号化される。
防止するのに役立つ前処理機能も備える。本発明の通常
の環境では、ラン・レングス・エンコーダは、モデム内
でデータ圧縮回路（符号化テーブル）の前に位置してい
る。ラン・レングス・エンコーダは、コンピュータから
モデムに送信されているデータ内の同一文字から成るス
トリングを認識し、それによりコードに置換する。それ
から、コードは符号化テーブルで符号化され、モデムか
ら伝送される。コードは、復号化テーブルで受け取られ
てから復号化される。
【００４４】本発明の前処理機能は、データがモデムを
介して端末から通信回線へ通信され、モデムが符号化テ
ーブルを使用してデータを圧縮するシステムで利用され
る。本発明は、モデムが前記に参照される、符号化テー
ブルを備える符号化方法を使用してデータを符号化する
前に、データ内の同一文字から成るストリングを事前に
符号化する方法であり、モデムから伝送される一連の連
続した同一文字を検出するステップと、圧縮のために前
記の符号化テーブルに渡されるデータ内の一連の連続し
た同一文字の代わりにコードで置換するステップを含
む。このコードは事前に決定した信号であり、３回繰り
返された検出済みの同一文字、および同一文字が繰り返
された総回数に等しい数を含む。モデムは、データが符
号化テーブルに渡され、Ｖ．４２ｂｉｓプロトコルに従
って圧縮される前に、データを圧縮する。
介して端末から通信回線へ通信され、モデムが符号化テ
ーブルを使用してデータを圧縮するシステムで利用され
る。本発明は、モデムが前記に参照される、符号化テー
ブルを備える符号化方法を使用してデータを符号化する
前に、データ内の同一文字から成るストリングを事前に
符号化する方法であり、モデムから伝送される一連の連
続した同一文字を検出するステップと、圧縮のために前
記の符号化テーブルに渡されるデータ内の一連の連続し
た同一文字の代わりにコードで置換するステップを含
む。このコードは事前に決定した信号であり、３回繰り
返された検出済みの同一文字、および同一文字が繰り返
された総回数に等しい数を含む。モデムは、データが符
号化テーブルに渡され、Ｖ．４２ｂｉｓプロトコルに従
って圧縮される前に、データを圧縮する。
【００４５】
【発明の実施の形態】次に、類似した数字が類似した部
分を示している図１〜図９を参照しながら、本発明の実
施の形態を示す。図２は、本発明の望ましいデータ圧縮
法および装置を利用するデータ通信アプリケーションを
示す概要図である。本発明のデータ圧縮スキームは、本
発明の実施の形態において、電話回線１２上のモデム１
０および１５の間でデータを通信するために実現され
る。開示される実施の形態は、モデムで使用するための
ものであるが、本発明は、大容量データ記憶装置、デー
タベース圧縮、遠隔測定法、ビデオ／画像圧縮、音声圧
縮、地震データ圧縮等のあらゆるタイプのデータ圧縮ア
プリケーションでの利用に適している。
分を示している図１〜図９を参照しながら、本発明の実
施の形態を示す。図２は、本発明の望ましいデータ圧縮
法および装置を利用するデータ通信アプリケーションを
示す概要図である。本発明のデータ圧縮スキームは、本
発明の実施の形態において、電話回線１２上のモデム１
０および１５の間でデータを通信するために実現され
る。開示される実施の形態は、モデムで使用するための
ものであるが、本発明は、大容量データ記憶装置、デー
タベース圧縮、遠隔測定法、ビデオ／画像圧縮、音声圧
縮、地震データ圧縮等のあらゆるタイプのデータ圧縮ア
プリケーションでの利用に適している。
【００４６】本発明の実施の形態は、データを圧縮する
ための符号化装置、および圧縮したデータを復号化する
ための別個ではあるが平行した復号化装置の使用に依存
している。それに従って、実施の形態に従って構築され
たモデム１０は、符号化テーブル１６と関連付けられ、
第２のモデム１５は、後述の方法で構築され保守される
復号化テーブル１８を備える。
ための符号化装置、および圧縮したデータを復号化する
ための別個ではあるが平行した復号化装置の使用に依存
している。それに従って、実施の形態に従って構築され
たモデム１０は、符号化テーブル１６と関連付けられ、
第２のモデム１５は、後述の方法で構築され保守される
復号化テーブル１８を備える。
【００４７】本実施の形態の符号化テーブル１６および
復号化テーブル１８は、ともに、図３に示されるような
マイクロコンピュータまたはマイクロプロセッサ３０と
結び付いたメモリ内に含まれるデータ・アレイとして実
現される。図３は、モデム１０でデータ圧縮の望ましい
方法を実現するためのマイクロプロセッサ３０をベース
にした回路のブロック概要図である。通常、モデム１０
は、本明細書で開示されるデータ圧縮法を実現するため
の手段を搭載し、データ圧縮回路２０を具備する。デー
タ圧縮回路２０は、モデム・コンピュータ・インタフェ
ース回路２２に接続される。モデム・コンピュータ・イ
ンタフェース回路部２２は、従来のモデム回路で、コン
ピュータ９のような入力ソースからライン２３上、デー
タの文字を受信し、データのその項目を伝送のために準
備するための回路部を具備する。一般的には、データの
文字は８ビット・バイトとして受け取られるが、より大
きなバイトのデータも利用され得る。この８ビット・バ
イトは、データ圧縮回路２０に接続されるデータ・バス
２５に提供される。
復号化テーブル１８は、ともに、図３に示されるような
マイクロコンピュータまたはマイクロプロセッサ３０と
結び付いたメモリ内に含まれるデータ・アレイとして実
現される。図３は、モデム１０でデータ圧縮の望ましい
方法を実現するためのマイクロプロセッサ３０をベース
にした回路のブロック概要図である。通常、モデム１０
は、本明細書で開示されるデータ圧縮法を実現するため
の手段を搭載し、データ圧縮回路２０を具備する。デー
タ圧縮回路２０は、モデム・コンピュータ・インタフェ
ース回路２２に接続される。モデム・コンピュータ・イ
ンタフェース回路部２２は、従来のモデム回路で、コン
ピュータ９のような入力ソースからライン２３上、デー
タの文字を受信し、データのその項目を伝送のために準
備するための回路部を具備する。一般的には、データの
文字は８ビット・バイトとして受け取られるが、より大
きなバイトのデータも利用され得る。この８ビット・バ
イトは、データ圧縮回路２０に接続されるデータ・バス
２５に提供される。
【００４８】データ圧縮の結果は、データ・バス２５に
提供され、モデム電話インタフェース回路２４へ送られ
る。該回路２４は、圧縮回路２０からデータを受信し、
電話会社の回線のような通信リンク上でのシリアル伝送
のためにデータを調整する。本実施の形態では、圧縮回
路２０からモデム電話インタフェース回路２４へ提供さ
れるデータは、後述する方法で符号化され、モデム・コ
ンピュータ・インタフェース回路２２により圧縮回路に
提供された文字を表すようになる。
提供され、モデム電話インタフェース回路２４へ送られ
る。該回路２４は、圧縮回路２０からデータを受信し、
電話会社の回線のような通信リンク上でのシリアル伝送
のためにデータを調整する。本実施の形態では、圧縮回
路２０からモデム電話インタフェース回路２４へ提供さ
れるデータは、後述する方法で符号化され、モデム・コ
ンピュータ・インタフェース回路２２により圧縮回路に
提供された文字を表すようになる。
【００４９】図３を続けて参照すると、データ圧縮回路
２０の本実施の形態は、マイクロプロセッサ３０を具備
し、該プロセッサ３０は、モデム・コンピュータ・イン
タフェース回路２２から１バイトのデータを受信し、そ
れを圧縮し、その後で符号化した結果を、シリアル伝送
のためモデム電話インタフェース回路２４に向けてデー
タ・バス上に戻すために反応する。マイクロプロセッサ
３０は、ザイログ社（Ｚｉｌｏｇ Ｃｏｒｐｏｒａｔｉ
ｏｎ）のＺ８０マイクロコンピュータやインテル社の８
０４８６マイクロプロセッサなどの数多くのマイクロコ
ンピュータやマイクロプロセッサのいずれでもよい。こ
れらのマイクロプロセッサのプログラミングおよび動作
は、当業者には周知であり、装置に付属する文献に説明
されている。
２０の本実施の形態は、マイクロプロセッサ３０を具備
し、該プロセッサ３０は、モデム・コンピュータ・イン
タフェース回路２２から１バイトのデータを受信し、そ
れを圧縮し、その後で符号化した結果を、シリアル伝送
のためモデム電話インタフェース回路２４に向けてデー
タ・バス上に戻すために反応する。マイクロプロセッサ
３０は、ザイログ社（Ｚｉｌｏｇ Ｃｏｒｐｏｒａｔｉ
ｏｎ）のＺ８０マイクロコンピュータやインテル社の８
０４８６マイクロプロセッサなどの数多くのマイクロコ
ンピュータやマイクロプロセッサのいずれでもよい。こ
れらのマイクロプロセッサのプログラミングおよび動作
は、当業者には周知であり、装置に付属する文献に説明
されている。
【００５０】マイクロプロセッサ３０に接続されるメモ
リ・デバイス３１には、マイクロプロセッサ３０の動作
のためのプログラムが格納されている。メモリ・デバイ
ス３１は、本実施の形態ではプログラマブル読出し専用
メモリ（ＰＲＯＭ）であるが、当業者に周知のそれ以外
の種類のメモリ、例えば、読出し専用メモリ、ランダム
・アクセス・メモリまたは電気的に消去・書込み可能な
読出し専用メモリ等を使用することもできる。メモリ・
デバイス３１は、プログラム命令がプログラム制御を受
けてマイクロプロセッサ３０に送られるように、データ
・バス２５に接続されている。ラインＡ０−Ａ１５から
構成されるマイクロプロセッサ３０のアドレス・バス３
２は、マイクロプロセッサ３０からのアドレス信号が既
知のやり方でプログラム・メモリをアドレス指定できる
ように、メモリ・デバイス３１とマイクロプロセッサ３
０の間で接続されている。当業者は、データ圧縮回路２
０に他の構成も利用できることが分かるであろう。例え
ば、データ・バス２５は１６ビット、アドレス・バス３
２は３２ビットにしたり、マイクロプロセッサ３０をハ
ードウェア・ロジック・ステートマシーンで置き換える
ことができる。
リ・デバイス３１には、マイクロプロセッサ３０の動作
のためのプログラムが格納されている。メモリ・デバイ
ス３１は、本実施の形態ではプログラマブル読出し専用
メモリ（ＰＲＯＭ）であるが、当業者に周知のそれ以外
の種類のメモリ、例えば、読出し専用メモリ、ランダム
・アクセス・メモリまたは電気的に消去・書込み可能な
読出し専用メモリ等を使用することもできる。メモリ・
デバイス３１は、プログラム命令がプログラム制御を受
けてマイクロプロセッサ３０に送られるように、データ
・バス２５に接続されている。ラインＡ０−Ａ１５から
構成されるマイクロプロセッサ３０のアドレス・バス３
２は、マイクロプロセッサ３０からのアドレス信号が既
知のやり方でプログラム・メモリをアドレス指定できる
ように、メモリ・デバイス３１とマイクロプロセッサ３
０の間で接続されている。当業者は、データ圧縮回路２
０に他の構成も利用できることが分かるであろう。例え
ば、データ・バス２５は１６ビット、アドレス・バス３
２は３２ビットにしたり、マイクロプロセッサ３０をハ
ードウェア・ロジック・ステートマシーンで置き換える
ことができる。
【００５１】符号化テーブル１６（圧縮解除が実行され
る場合には、復号化テーブル１８）は、ランダム・アク
セス・メモリ（ＲＡＭ）３５内に格納されており、該メ
モリ３５は、アドレス・バス３２上のアドレス信号を受
信し、データ・バス２５でデータ信号を受信し、送信す
るよう接続される。本実施の形態では、ＲＡＭ３５は、
後述するテーブルおよびレジスタとともに、符号化テー
ブル１６のために１６３８４のエントリまで記憶するこ
とができる。各エントリには、７バイトの記憶領域が必
要なため、１６３８４エントリでは少なくとも１１４，
６８８バイトのメモリが必要になる。少なくとも１２
８，０００バイト、またはシステム・デザイナーによっ
て選択される他の十分なサイズのＲＡＭ３５が使用され
るのが望ましい。
る場合には、復号化テーブル１８）は、ランダム・アク
セス・メモリ（ＲＡＭ）３５内に格納されており、該メ
モリ３５は、アドレス・バス３２上のアドレス信号を受
信し、データ・バス２５でデータ信号を受信し、送信す
るよう接続される。本実施の形態では、ＲＡＭ３５は、
後述するテーブルおよびレジスタとともに、符号化テー
ブル１６のために１６３８４のエントリまで記憶するこ
とができる。各エントリには、７バイトの記憶領域が必
要なため、１６３８４エントリでは少なくとも１１４，
６８８バイトのメモリが必要になる。少なくとも１２
８，０００バイト、またはシステム・デザイナーによっ
て選択される他の十分なサイズのＲＡＭ３５が使用され
るのが望ましい。
【００５２】マイクロプロセッサ３０に関連する制御信
号は、このような要素が当業者にとって周知であるた
め、図３には示されていない。当業者は、ライン３６上
の割込み信号（ＩＮＴ）が、データ文字がコンピュータ
・インタフェース回路２２によりデータ圧縮回路２０に
提供される旨を伝えることが分かるであろう。類似した
やり方で、電話インタフェース回路２４は、システムが
復号化モードで利用される場合に、ＩＮＴ信号を提供す
る。割込み信号は、マイクロプロセッサ３０に、データ
符号化またはデータ復号化のためのデータがデータ・バ
ス２５上に存在することを知らせる。代わりに、そして
より高速な通信の場合、ダイレクト・メモリ・アクセス
が、コンピュータ・インタフェース回路２２から文字を
受け入れるために利用される。
号は、このような要素が当業者にとって周知であるた
め、図３には示されていない。当業者は、ライン３６上
の割込み信号（ＩＮＴ）が、データ文字がコンピュータ
・インタフェース回路２２によりデータ圧縮回路２０に
提供される旨を伝えることが分かるであろう。類似した
やり方で、電話インタフェース回路２４は、システムが
復号化モードで利用される場合に、ＩＮＴ信号を提供す
る。割込み信号は、マイクロプロセッサ３０に、データ
符号化またはデータ復号化のためのデータがデータ・バ
ス２５上に存在することを知らせる。代わりに、そして
より高速な通信の場合、ダイレクト・メモリ・アクセス
が、コンピュータ・インタフェース回路２２から文字を
受け入れるために利用される。
【００５３】また、モデム・インタフェース回路２２お
よび２４に具備されているのは、それぞれ制御レジスタ
２７および２８である。該レジスタ２７、２８は、モデ
ム・インタフェース回路とデータ圧縮回路２０の間のイ
ンタフェースを補助するために利用される。制御レジス
タ２７および２８は、マイクロプロセッサ３０とのイン
タフェースのために必要となるさまざまな制御信号を提
供する。例えば、マイクロプロセッサ３０が符号化状態
となるように設定される場合、マイクロプロセッサ３０
は、符号化のための回路２２からの各文字の受信を肯定
応答（ａｃｋｎｏｗｌｅｄｇｅ）しなければならない。
したがって、マイクロプロセッサ３０は、割込みを肯定
応答し、マイクロプロセッサ３０がビジーである旨を伝
えるために、制御レジスタ２７の１ビットをセットする
ことにより、モデム・コンピュータ・インタフェース回
路２２からの割込みに対してハンドシェイク法での応答
をする。マイクロプロセッサ３０が符号化のために別の
文字を受け入れることができる場合は、このビジー信号
はクリアされて、そして、モデム・コンピュータ・イン
タフェース回路２２が圧縮および最終的な伝送のために
別の文字を提供するようされる。
よび２４に具備されているのは、それぞれ制御レジスタ
２７および２８である。該レジスタ２７、２８は、モデ
ム・インタフェース回路とデータ圧縮回路２０の間のイ
ンタフェースを補助するために利用される。制御レジス
タ２７および２８は、マイクロプロセッサ３０とのイン
タフェースのために必要となるさまざまな制御信号を提
供する。例えば、マイクロプロセッサ３０が符号化状態
となるように設定される場合、マイクロプロセッサ３０
は、符号化のための回路２２からの各文字の受信を肯定
応答（ａｃｋｎｏｗｌｅｄｇｅ）しなければならない。
したがって、マイクロプロセッサ３０は、割込みを肯定
応答し、マイクロプロセッサ３０がビジーである旨を伝
えるために、制御レジスタ２７の１ビットをセットする
ことにより、モデム・コンピュータ・インタフェース回
路２２からの割込みに対してハンドシェイク法での応答
をする。マイクロプロセッサ３０が符号化のために別の
文字を受け入れることができる場合は、このビジー信号
はクリアされて、そして、モデム・コンピュータ・イン
タフェース回路２２が圧縮および最終的な伝送のために
別の文字を提供するようされる。
【００５４】同様に、制御レジスタ２８は、マイクロプ
ロセッサ３０と電話インタフェース回路２４の間のイン
タフェースを容易にする。ある文字のコード化された圧
縮表現が伝送できる状態にある場合、マイクロプロセッ
サ３０は、モデム電話インタフェース回路２４の制御レ
ジスタ２４の１ビットをセットし、この回路に、コード
が伝送できる状態にあり、回路２４内の適切な格納レジ
スタ（不図示）への取り込みのためにデータ・バス上に
配置された旨を知らせる。
ロセッサ３０と電話インタフェース回路２４の間のイン
タフェースを容易にする。ある文字のコード化された圧
縮表現が伝送できる状態にある場合、マイクロプロセッ
サ３０は、モデム電話インタフェース回路２４の制御レ
ジスタ２４の１ビットをセットし、この回路に、コード
が伝送できる状態にあり、回路２４内の適切な格納レジ
スタ（不図示）への取り込みのためにデータ・バス上に
配置された旨を知らせる。
【００５５】システムが復号化モードに設定されている
場合、データ・パスは、前述した構成の逆になる。デー
タは電話回線１２（図２）から受信され、モデム電話イ
ンタフェース回路２４を経由して、圧縮解除のためにマ
イクロプロセッサ３０に提供されてから、ライン２３上
をコンピュータへ提供するためにモデム・コンピュータ
・インタフェース回路２２に提供される。ライン３６上
の割込み信号は、文字が電話インタフェース回路２４か
ら圧縮解除回路２０に渡すことのできる状態にある旨を
知らせる。モデム回路２２、２４からの割込みは、いず
れもが割込みを生成できるように、ワイヤードＯＲされ
ている。
場合、データ・パスは、前述した構成の逆になる。デー
タは電話回線１２（図２）から受信され、モデム電話イ
ンタフェース回路２４を経由して、圧縮解除のためにマ
イクロプロセッサ３０に提供されてから、ライン２３上
をコンピュータへ提供するためにモデム・コンピュータ
・インタフェース回路２２に提供される。ライン３６上
の割込み信号は、文字が電話インタフェース回路２４か
ら圧縮解除回路２０に渡すことのできる状態にある旨を
知らせる。モデム回路２２、２４からの割込みは、いず
れもが割込みを生成できるように、ワイヤードＯＲされ
ている。
【００５６】実施の形態の説明に入る前に、一般には
「Ｖ．４２ｂｉｓ」と呼ばれているデータ圧縮技法につ
いて見直すと役立つであろう。本実施の形態は、Ｖ．４
２ｂｉｓデータ圧縮システムに関連して利用されてい
る。符号化テーブル１６は、複数のルート文字４を有
し、各エントリのサイズが典型的には約７バイトであ
る、５１２個から１６，３８４個のエントリが割り当て
られたことが望ましいＲＡＭ３５内で、始めにセットア
ップされる。当業者が熟知しているように、符号化テー
ブル１６は、Ｖ．４２ｂｉｓ規格によれば６５，５３６
個のエントリ、又はＲＡＭ３５が保持できる十分に多く
のエントリを含むことが可能である。図１及び図４を参
照すると、符号化テーブル１６の内容は、ルート文字４
から発展した文字から成るストリング５である。文字
「Ｂ」などのルート文字４は、それにぶら下がる文字を
有し、ツリー６を形成する。他の文字がぶらさがらず、
かつルート文字４ではない符号化テーブル１６内の文字
は、リーフ文字７である。符号化テーブル１６（および
対応する復号化テーブル１８）内に文字を格納するやり
方は、ＣＣＩＴＴ勧告のＶ．４２ｂｉｓ規格により定義
されている。
「Ｖ．４２ｂｉｓ」と呼ばれているデータ圧縮技法につ
いて見直すと役立つであろう。本実施の形態は、Ｖ．４
２ｂｉｓデータ圧縮システムに関連して利用されてい
る。符号化テーブル１６は、複数のルート文字４を有
し、各エントリのサイズが典型的には約７バイトであ
る、５１２個から１６，３８４個のエントリが割り当て
られたことが望ましいＲＡＭ３５内で、始めにセットア
ップされる。当業者が熟知しているように、符号化テー
ブル１６は、Ｖ．４２ｂｉｓ規格によれば６５，５３６
個のエントリ、又はＲＡＭ３５が保持できる十分に多く
のエントリを含むことが可能である。図１及び図４を参
照すると、符号化テーブル１６の内容は、ルート文字４
から発展した文字から成るストリング５である。文字
「Ｂ」などのルート文字４は、それにぶら下がる文字を
有し、ツリー６を形成する。他の文字がぶらさがらず、
かつルート文字４ではない符号化テーブル１６内の文字
は、リーフ文字７である。符号化テーブル１６（および
対応する復号化テーブル１８）内に文字を格納するやり
方は、ＣＣＩＴＴ勧告のＶ．４２ｂｉｓ規格により定義
されている。
【００５７】本発明の実施の形態では、符号化テーブル
１は、最初は長さ１のストリング５（ルート文字４）を
含み、符号化テーブル１６は、データがＣＣＩＴＴ
Ｖ．４２ｂｉｓ規格に基づいてモデム１０で受信される
に従って満たされる。本発明の望ましい環境は、複数の
文字ストリングを含む符号化テーブル１６を備え、スト
リングのそれぞれは、多くのルート文字の内の１つにぶ
ら下がる。符号化テーブル１６は、文字のストリームの
部分と置換されることがあるストリングに関連付けられ
たコードワードを含む。Ｖ．４２ｂｉｓシステムにおい
てのように、モデム１０のマイクロプロセッサ３０は、
データ文字の入力ストリーム中の文字を符号化テーブル
中の文字ストリングと比較し、データ文字のストリーム
中の文字が符号化テーブル１６中のストリング５の１つ
に一致すると、マイクロプロセッサ３０はデータ文字の
ストリーム中の文字をコードワードの対応するもので置
き換える。ただし、符号化テーブルに、一般的に利用さ
れるワードや記号を事前にロードすることもできる。
１は、最初は長さ１のストリング５（ルート文字４）を
含み、符号化テーブル１６は、データがＣＣＩＴＴ
Ｖ．４２ｂｉｓ規格に基づいてモデム１０で受信される
に従って満たされる。本発明の望ましい環境は、複数の
文字ストリングを含む符号化テーブル１６を備え、スト
リングのそれぞれは、多くのルート文字の内の１つにぶ
ら下がる。符号化テーブル１６は、文字のストリームの
部分と置換されることがあるストリングに関連付けられ
たコードワードを含む。Ｖ．４２ｂｉｓシステムにおい
てのように、モデム１０のマイクロプロセッサ３０は、
データ文字の入力ストリーム中の文字を符号化テーブル
中の文字ストリングと比較し、データ文字のストリーム
中の文字が符号化テーブル１６中のストリング５の１つ
に一致すると、マイクロプロセッサ３０はデータ文字の
ストリーム中の文字をコードワードの対応するもので置
き換える。ただし、符号化テーブルに、一般的に利用さ
れるワードや記号を事前にロードすることもできる。
【００５８】本発明の実施の形態は、ストリングに関係
付けられたコードワードがどのようにデータのストリー
ム中の文字と置換されるのかに依存していない。言い替
えると、データ圧縮スキームには、Ｖ．４２ｂｉｓ、Ｍ
ＮＰ−７、またはそれ以外のストリング・ベースの圧縮
スキームを使用できる。本実施の形態は、データ圧縮に
おいて達成された過去の成功に焦点を当て、以上のスト
リング・ベースの圧縮スキームのいずれにおいても、よ
り効率的なデータ圧縮を行うために符号化テーブル１６
のサイズを調整する。しかしながら、本発明の実施の形
態についてさらによく理解できるようにするために、モ
デム１０に入力されるデータ・ストリーム内のデータ・
ストリングを圧縮する方法を簡略に説明する。
付けられたコードワードがどのようにデータのストリー
ム中の文字と置換されるのかに依存していない。言い替
えると、データ圧縮スキームには、Ｖ．４２ｂｉｓ、Ｍ
ＮＰ−７、またはそれ以外のストリング・ベースの圧縮
スキームを使用できる。本実施の形態は、データ圧縮に
おいて達成された過去の成功に焦点を当て、以上のスト
リング・ベースの圧縮スキームのいずれにおいても、よ
り効率的なデータ圧縮を行うために符号化テーブル１６
のサイズを調整する。しかしながら、本発明の実施の形
態についてさらによく理解できるようにするために、モ
デム１０に入力されるデータ・ストリーム内のデータ・
ストリングを圧縮する方法を簡略に説明する。
【００５９】データは、以下のように、Ｖ．４２ｂｉｓ
規格に従って本実施の形態の使用とともに圧縮されるの
が望ましい。図１および図３を参照し、コンピュータ９
からモデム１０で受け取られた文字ストリングが「ＢＡ
Ｙ」であると考える。ストリング「Ｂ」を探して、符号
化テーブルが探索される。この文字がルート・ノード４
として発見されると、次の文字が読み取られ、付加され
て、「ＢＡ」を形成する。符号化テーブル１６は、新し
いストリングがないかどうか探索され、それが発見され
てから、次の文字「Ｙ」が読み取られ、ストリングに付
加され、ストリング「ＢＡＹ」を形成する。「ＢＡＹ」
がないかどうか符号化テーブル１６が探索され、「ＢＡ
Ｙ」は存在していないので、「Ｙ」は削除され、ストリ
ング一致プロシージャは、「ＢＡ」を一致ストリングと
し、「Ｙ」を不一致文字として終了する。「ＢＡ」のコ
ードワードが符号化され、伝送される。新しいストリン
グ「ＢＡＹ」が、符号化テーブル１６中で「ＢＡ」に
「Ｙ」を付加することにより作成され、コードワードが
「ＢＡＹ」に割り当てられる。文字「Ｙ」は、次のスト
リング一致動作を開始するために使用される。当業者
は、符号化テーブル１６および復号化テーブル１８が、
データが誤って解釈されないように、同一となるように
発展することが分かるであろう。
規格に従って本実施の形態の使用とともに圧縮されるの
が望ましい。図１および図３を参照し、コンピュータ９
からモデム１０で受け取られた文字ストリングが「ＢＡ
Ｙ」であると考える。ストリング「Ｂ」を探して、符号
化テーブルが探索される。この文字がルート・ノード４
として発見されると、次の文字が読み取られ、付加され
て、「ＢＡ」を形成する。符号化テーブル１６は、新し
いストリングがないかどうか探索され、それが発見され
てから、次の文字「Ｙ」が読み取られ、ストリングに付
加され、ストリング「ＢＡＹ」を形成する。「ＢＡＹ」
がないかどうか符号化テーブル１６が探索され、「ＢＡ
Ｙ」は存在していないので、「Ｙ」は削除され、ストリ
ング一致プロシージャは、「ＢＡ」を一致ストリングと
し、「Ｙ」を不一致文字として終了する。「ＢＡ」のコ
ードワードが符号化され、伝送される。新しいストリン
グ「ＢＡＹ」が、符号化テーブル１６中で「ＢＡ」に
「Ｙ」を付加することにより作成され、コードワードが
「ＢＡＹ」に割り当てられる。文字「Ｙ」は、次のスト
リング一致動作を開始するために使用される。当業者
は、符号化テーブル１６および復号化テーブル１８が、
データが誤って解釈されないように、同一となるように
発展することが分かるであろう。
【００６０】一般的に、望ましいデータ圧縮法は、マイ
クロプロセッサ３０用のプログラムとして実現される一
連のステップから構成される。図４は、入力データの特
徴を判断し、それに応えて符号化テーブル１６（および
復号化テーブル１８）を調整し、必要な処理時間に対し
てデータ圧縮を最適化する際に講じられるステップのフ
ローチャートである。
クロプロセッサ３０用のプログラムとして実現される一
連のステップから構成される。図４は、入力データの特
徴を判断し、それに応えて符号化テーブル１６（および
復号化テーブル１８）を調整し、必要な処理時間に対し
てデータ圧縮を最適化する際に講じられるステップのフ
ローチャートである。
【００６１】図３および図４を参照すると、データ圧縮
回路２０に入る第１文字はステップ５０で検出され、ス
テップ５２でルート文字４と照合される。第１文字がス
テップ５２でルート文字４と照合されてから、データ圧
縮回路２０（図３）はステップ５４で第２のデータ文字
を待つ。ステップ５４でデータ文字がデータ圧縮回路２
０に入力されない場合、マイクロプロセッサ３０は、
「ＮＯ」ブランチに従ってステップ５５へ進み、タイム
アウトが発生したかどうかを判断する。タイムアウトは
ソフトウェア・タイマ（不図示）で、マイクロプロセッ
サ３０（図３）により実行されるメモリ３１内で実行可
能なコードから構成される。当業者は、ハードウェア・
タイマやカウンタ等が、ソフトウェア・タイマの代わり
に使用できることが分かるであろう。
回路２０に入る第１文字はステップ５０で検出され、ス
テップ５２でルート文字４と照合される。第１文字がス
テップ５２でルート文字４と照合されてから、データ圧
縮回路２０（図３）はステップ５４で第２のデータ文字
を待つ。ステップ５４でデータ文字がデータ圧縮回路２
０に入力されない場合、マイクロプロセッサ３０は、
「ＮＯ」ブランチに従ってステップ５５へ進み、タイム
アウトが発生したかどうかを判断する。タイムアウトは
ソフトウェア・タイマ（不図示）で、マイクロプロセッ
サ３０（図３）により実行されるメモリ３１内で実行可
能なコードから構成される。当業者は、ハードウェア・
タイマやカウンタ等が、ソフトウェア・タイマの代わり
に使用できることが分かるであろう。
【００６２】ステップ５５でのタイムアウトは、データ
圧縮回路２０が、さらにデータ文字を受け取るためにそ
れ以上待たないことを示す。したがって、タイムアウト
がステップ５５で発生したら、「ＹＥＳ」ブランチに従
ってステップ５６に進む。本実施の形態においては、ス
テップ５６でデータが圧縮され、電話回線１２上を伝送
される。ステップ５６でのデータの伝送の後に、データ
圧縮回路２０は、再度、ステップ５０で文字入力を待
つ。当業者は、大容量データ記憶装置のような別のシス
テムにおいては、データは、ステップ５５でのタイムア
ウト後に単に圧縮され、格納されるだけであることが分
かるであろう。
圧縮回路２０が、さらにデータ文字を受け取るためにそ
れ以上待たないことを示す。したがって、タイムアウト
がステップ５５で発生したら、「ＹＥＳ」ブランチに従
ってステップ５６に進む。本実施の形態においては、ス
テップ５６でデータが圧縮され、電話回線１２上を伝送
される。ステップ５６でのデータの伝送の後に、データ
圧縮回路２０は、再度、ステップ５０で文字入力を待
つ。当業者は、大容量データ記憶装置のような別のシス
テムにおいては、データは、ステップ５５でのタイムア
ウト後に単に圧縮され、格納されるだけであることが分
かるであろう。
【００６３】他方、タイムアウトがステップ５５で発生
しないこともある。この場合、ステップ５５からの「Ｎ
Ｏ」ブランチに従って、データ圧縮回路２０（図３）
は、データ文字がステップ５４で受け取られたかどうか
を判断する。ステップ５０で検出された文字に続いて受
け取られた第２のデータ文字は、ステップ５４で検出さ
れる。「ＹＥＳ」ブランチに続き、ステップ５４での文
字の受け取りに応えて、ステップ５８が実行される。
しないこともある。この場合、ステップ５５からの「Ｎ
Ｏ」ブランチに従って、データ圧縮回路２０（図３）
は、データ文字がステップ５４で受け取られたかどうか
を判断する。ステップ５０で検出された文字に続いて受
け取られた第２のデータ文字は、ステップ５４で検出さ
れる。「ＹＥＳ」ブランチに続き、ステップ５４での文
字の受け取りに応えて、ステップ５８が実行される。
【００６４】可能である場合は、モデム１０に到達する
第２のデータ文字が、ステップ５８で符号化テーブル１
６中のストリング５（図１）内の文字と一致させられ
る。それ以降の入力データ文字もステップ５４で検出さ
れ、ステップ５８でストリングに一致させられる。この
ようにして、ステップ５４および５８で、入力文字
（群）が検出され、符号化テーブル１６中のストリング
５と一致させられる。
第２のデータ文字が、ステップ５８で符号化テーブル１
６中のストリング５（図１）内の文字と一致させられ
る。それ以降の入力データ文字もステップ５４で検出さ
れ、ステップ５８でストリングに一致させられる。この
ようにして、ステップ５４および５８で、入力文字
（群）が検出され、符号化テーブル１６中のストリング
５と一致させられる。
【００６５】ステップ５８で、データストリーム内の入
力文字を符号化テーブル中のストリング５と一致させら
れなかった場合には、その後、一致したストリングの置
換コードワードがステップ５９で見つけられる。一致し
ない文字は格納され、ステップ５２でルート文字４に一
致され、前述のように、符号化テーブル１６中のストリ
ングと入力文字の照合を開始するのに使用される。一致
したストリングに対応するコードワードは、最終的に、
ステップ５６で受け取り側モデム１５（図２）に伝送さ
れる。一致しない文字は、ステップ５６で圧縮されずに
伝送され、復号化テーブル１８（図２）に次のルート文
字４を知らせ、一致しない文字はルート文字４と照合さ
れ、図４のステップ５２でシード文字として使用され
る。当業者には、ＣＣＩＴＴ勧告のＶ．４２ｂｉｓ規格
に記述されるような、コードワードによる文字ストリン
グの置換、および符号化テーブルと復号化テーブルのマ
ーキングの構築ならびに保守は周知である。
力文字を符号化テーブル中のストリング５と一致させら
れなかった場合には、その後、一致したストリングの置
換コードワードがステップ５９で見つけられる。一致し
ない文字は格納され、ステップ５２でルート文字４に一
致され、前述のように、符号化テーブル１６中のストリ
ングと入力文字の照合を開始するのに使用される。一致
したストリングに対応するコードワードは、最終的に、
ステップ５６で受け取り側モデム１５（図２）に伝送さ
れる。一致しない文字は、ステップ５６で圧縮されずに
伝送され、復号化テーブル１８（図２）に次のルート文
字４を知らせ、一致しない文字はルート文字４と照合さ
れ、図４のステップ５２でシード文字として使用され
る。当業者には、ＣＣＩＴＴ勧告のＶ．４２ｂｉｓ規格
に記述されるような、コードワードによる文字ストリン
グの置換、および符号化テーブルと復号化テーブルのマ
ーキングの構築ならびに保守は周知である。
【００６６】コンピュータ９（図３）により生成され、
データ圧縮回路２０に入るデータ文字の入力ストリーム
がステップ５９で圧縮されるかどうかには関係なく、ス
テップ６０で、符号化テーブル１６は「枝刈り」され
る。例えば、図１、図２、および図４を参照すると、符
号化テーブル１６に到達するデータ・ストリーム内のワ
ードは、「ＢＡＴＳ」かもしれない。図１に示される符
号化テーブルエントリのストリング内にあるのは、ワー
ド「ＢＡＴ」だけである。一致しない文字「Ｓ」は、符
号化テーブル１６でワード「ＢＡＴＳ」を形成するため
に、文字「Ｔ」にぶら下がるように加えられ、そして、
コードワードは、当業者によく知られたやり方、例え
ば、ストリングおよびコードワードのメモリ・ロケーシ
ョンをマッピングまたは直接リンクするなどして、ＲＡ
Ｍ３５内で「ＢＡＴＳ」と関連付けられる。しかし、符
号化テーブル１６のサイズは固定である。したがって、
文字「Ｓ」を符号化テーブル１６に加えるには、別の文
字の削除が必要になる。
データ圧縮回路２０に入るデータ文字の入力ストリーム
がステップ５９で圧縮されるかどうかには関係なく、ス
テップ６０で、符号化テーブル１６は「枝刈り」され
る。例えば、図１、図２、および図４を参照すると、符
号化テーブル１６に到達するデータ・ストリーム内のワ
ードは、「ＢＡＴＳ」かもしれない。図１に示される符
号化テーブルエントリのストリング内にあるのは、ワー
ド「ＢＡＴ」だけである。一致しない文字「Ｓ」は、符
号化テーブル１６でワード「ＢＡＴＳ」を形成するため
に、文字「Ｔ」にぶら下がるように加えられ、そして、
コードワードは、当業者によく知られたやり方、例え
ば、ストリングおよびコードワードのメモリ・ロケーシ
ョンをマッピングまたは直接リンクするなどして、ＲＡ
Ｍ３５内で「ＢＡＴＳ」と関連付けられる。しかし、符
号化テーブル１６のサイズは固定である。したがって、
文字「Ｓ」を符号化テーブル１６に加えるには、別の文
字の削除が必要になる。
【００６７】プログラム・メモリ３１に格納されるエン
トリ削除ルーチン６１（図３）は、ステップ６０でマイ
クロプロセッサ３０により実行される。エントリ削除ル
ーチン６１は、入力文字に対して一致するものが符号化
テーブル１６で見つからない場合に、リーフ文字７をツ
リー６（図１）から枝刈りするのに使われる。したがっ
て、エントリ削除ルーチン６１は、通常、文字がデータ
圧縮回路２０で受け取られ、その文字がステップ５８で
符号化テーブル１６中の文字と一致しなかった後に呼び
出される。当業者には、エントリ削除ルーチン６１が、
どのようにしてツリー６内のリーフ文字７を見つけ出
し、符号化テーブル１６から削除するのかはよく知られ
ている。本発明の実施の形態は、ステップ６０で、Ｖ．
４２ｂｉｓ勧告に記述される枝刈り技法を取り入れる。
トリ削除ルーチン６１（図３）は、ステップ６０でマイ
クロプロセッサ３０により実行される。エントリ削除ル
ーチン６１は、入力文字に対して一致するものが符号化
テーブル１６で見つからない場合に、リーフ文字７をツ
リー６（図１）から枝刈りするのに使われる。したがっ
て、エントリ削除ルーチン６１は、通常、文字がデータ
圧縮回路２０で受け取られ、その文字がステップ５８で
符号化テーブル１６中の文字と一致しなかった後に呼び
出される。当業者には、エントリ削除ルーチン６１が、
どのようにしてツリー６内のリーフ文字７を見つけ出
し、符号化テーブル１６から削除するのかはよく知られ
ている。本発明の実施の形態は、ステップ６０で、Ｖ．
４２ｂｉｓ勧告に記述される枝刈り技法を取り入れる。
【００６８】図４、図５、および図６を参照すると、符
号化テーブル１６がステップ６０で修正されてから、符
号化テーブル制御プログラム６２が実行される。プログ
ラム６２では、データ文字間の相関関係が分析され、符
号化テーブル１６のサイズが変更されることがある（図
５）。
号化テーブル１６がステップ６０で修正されてから、符
号化テーブル制御プログラム６２が実行される。プログ
ラム６２では、データ文字間の相関関係が分析され、符
号化テーブル１６のサイズが変更されることがある（図
５）。
【００６９】図４を参照すると、プログラム６２は、ス
テップ６４およびステップ６６を包含するように、点線
で示されている。コンピュータ９（図３）からデータ圧
縮回路２０に到達するデータのストリーム内の文字間の
相関関係は、ステップ６４で判断される。本実施の形態
では、データのストリーム内の文字間の相関関係は、
（１）前に受け取られたデータの圧縮率、および（２）
符号化テーブル１６の特徴を分析することにより判断さ
れる。ステップ６４でデータ文字間の相関関係を判断し
てから、符号化テーブル１６のサイズがステップ６６で
調整される。
テップ６４およびステップ６６を包含するように、点線
で示されている。コンピュータ９（図３）からデータ圧
縮回路２０に到達するデータのストリーム内の文字間の
相関関係は、ステップ６４で判断される。本実施の形態
では、データのストリーム内の文字間の相関関係は、
（１）前に受け取られたデータの圧縮率、および（２）
符号化テーブル１６の特徴を分析することにより判断さ
れる。ステップ６４でデータ文字間の相関関係を判断し
てから、符号化テーブル１６のサイズがステップ６６で
調整される。
【００７０】図５は、望ましい符号化テーブル制御プロ
グラム６２の詳細なフローチャートであり、データ・ス
トリーム内の文字間の相関関係を判断し、符号化テーブ
ル１６のサイズを調整することにより、データ圧縮を最
適化し、データを圧縮しようとして費やされるプロセッ
サ時間を最小限に抑えるために講じられるステップを示
す。図５のフローチャートの説明するのに、まず、デー
タ圧縮回路２０に到達するデータのストリーム内の文字
間の相関関係を判断するのに使用される望ましい技法に
ついて概説する。符号化テーブル１６が狭いツリーまた
は広いツリー６を持つのかどうかを判断するために、ス
テップ６５で符号化テーブル１６の特徴が分析される。
この特徴は、「正規化使用カウント」と呼ばれ、後に詳
細に述べる。次に、データ・ストリームの圧縮率がステ
ップ６８で決定される。ステップ６５および６８で判断
されるこれらの２つの基準は、ステップ７２であわされ
て性能指標を算出する。性能指標は、ステップ６６での
符号化テーブル１６のサイズの調整を制御するために利
用される。
グラム６２の詳細なフローチャートであり、データ・ス
トリーム内の文字間の相関関係を判断し、符号化テーブ
ル１６のサイズを調整することにより、データ圧縮を最
適化し、データを圧縮しようとして費やされるプロセッ
サ時間を最小限に抑えるために講じられるステップを示
す。図５のフローチャートの説明するのに、まず、デー
タ圧縮回路２０に到達するデータのストリーム内の文字
間の相関関係を判断するのに使用される望ましい技法に
ついて概説する。符号化テーブル１６が狭いツリーまた
は広いツリー６を持つのかどうかを判断するために、ス
テップ６５で符号化テーブル１６の特徴が分析される。
この特徴は、「正規化使用カウント」と呼ばれ、後に詳
細に述べる。次に、データ・ストリームの圧縮率がステ
ップ６８で決定される。ステップ６５および６８で判断
されるこれらの２つの基準は、ステップ７２であわされ
て性能指標を算出する。性能指標は、ステップ６６での
符号化テーブル１６のサイズの調整を制御するために利
用される。
【００７１】図５のプログラム６２についての詳説に進
む前に、図６を簡単に参照する。図６は、本発明の実施
の形態でコンピュータ９からモデム１０に到達するデー
タ・ストリーム内のデータ文字間の相関関係を計算する
ために、マイクロプロセッサ・ベースの回路（図３）に
より使用されるレジスタおよびテーブルのブロック図で
ある。具体的には、レジスタ９０は正規化使用カウント
８９を保持し、レジスタ９５は圧縮率９６を保持し、レ
ジスタ１０９は性能指標１１０を保持する。さらに、テ
ーブル９３は使用カウント・デルタ９２を格納し、第２
テーブル９７は圧縮率デルタ９８を格納する。これらは
以下に詳細に説明する。レジスタ９０、９５、および１
０９、ならびにテーブル９３および９７は、実施の形態
のＲＡＭ３５（図３）内のメモリ位置である。ただし、
テーブルおよびレジスタは、当業者にとっては明かなよ
うに、あらゆるデータ格納のための装置または手段で
の、固定されたメモリ位置または可変メモリ位置とする
ことができる。
む前に、図６を簡単に参照する。図６は、本発明の実施
の形態でコンピュータ９からモデム１０に到達するデー
タ・ストリーム内のデータ文字間の相関関係を計算する
ために、マイクロプロセッサ・ベースの回路（図３）に
より使用されるレジスタおよびテーブルのブロック図で
ある。具体的には、レジスタ９０は正規化使用カウント
８９を保持し、レジスタ９５は圧縮率９６を保持し、レ
ジスタ１０９は性能指標１１０を保持する。さらに、テ
ーブル９３は使用カウント・デルタ９２を格納し、第２
テーブル９７は圧縮率デルタ９８を格納する。これらは
以下に詳細に説明する。レジスタ９０、９５、および１
０９、ならびにテーブル９３および９７は、実施の形態
のＲＡＭ３５（図３）内のメモリ位置である。ただし、
テーブルおよびレジスタは、当業者にとっては明かなよ
うに、あらゆるデータ格納のための装置または手段で
の、固定されたメモリ位置または可変メモリ位置とする
ことができる。
【００７２】本発明の実施の形態では、データの性質
は、まず、符号化テーブル１６のツリーの形に基づいて
ステップ６５（図５）で分析される。図５および図６を
参照すると、符号化テーブル１６のツリーの形は、レジ
スタ９０の正規化使用カウント８９を使用して評価され
る。正規化使用カウント８９は、使用カウントの平均値
である。使用カウントは、プログラム・メモリ３１内の
エントリ削除ルーチン６１（図３）が実行されるたびに
計算されることが望ましい。したがって、本実施の形態
では、使用カウントは、データ文字のストリングがコー
ドワードと照合されるたびに計算される。正規化使用カ
ウント８９は、モデム１０でコンピュータ９から５００
番目の文字が受け取られるたびに、計算されるのが望ま
しい。５００番目の文字が受け取られた後、次の正規化
使用カウント８９の計算を開始するために、使用カウン
トおよび正規化使用カウント８９はゼロにリセットされ
る。
は、まず、符号化テーブル１６のツリーの形に基づいて
ステップ６５（図５）で分析される。図５および図６を
参照すると、符号化テーブル１６のツリーの形は、レジ
スタ９０の正規化使用カウント８９を使用して評価され
る。正規化使用カウント８９は、使用カウントの平均値
である。使用カウントは、プログラム・メモリ３１内の
エントリ削除ルーチン６１（図３）が実行されるたびに
計算されることが望ましい。したがって、本実施の形態
では、使用カウントは、データ文字のストリングがコー
ドワードと照合されるたびに計算される。正規化使用カ
ウント８９は、モデム１０でコンピュータ９から５００
番目の文字が受け取られるたびに、計算されるのが望ま
しい。５００番目の文字が受け取られた後、次の正規化
使用カウント８９の計算を開始するために、使用カウン
トおよび正規化使用カウント８９はゼロにリセットされ
る。
【００７３】当業者にはよく知られているように、プロ
グラム・メモリ３１内のエントリ削除ルーチン６１（図
３）は、ツリー６のリーフ文字７を見つけて削除するた
めに擬似乱数法を利用する。具体的には、エントリ削除
ルーチンのために、カウンタは符号化テーブルのエント
リにわたって増分でカウントする。エントリ削除ルーチ
ン６１が起動されると、カウンタは次のエントリに移動
し、エントリにヌル・ポインタが設定されている（リー
フ文字７である。図１参照）かどうかを判断する。エン
トリにヌル・ポインタが設定されている場合、それはリ
ーフ文字であり、削除される。エントリにヌル・ポイン
タが設定されていない場合、それはリーフ文字ではない
ので、カウンタは増分され、削除するリーフ文字を見つ
けるために、次のエントリが調べられる。当業者には、
エントリ削除ルーチン６１のようなプログラムはよく知
られている。使用カウントは、単に、削除対象のリーフ
・エントリを見つけるために探索が行われたエントリの
総数である。
グラム・メモリ３１内のエントリ削除ルーチン６１（図
３）は、ツリー６のリーフ文字７を見つけて削除するた
めに擬似乱数法を利用する。具体的には、エントリ削除
ルーチンのために、カウンタは符号化テーブルのエント
リにわたって増分でカウントする。エントリ削除ルーチ
ン６１が起動されると、カウンタは次のエントリに移動
し、エントリにヌル・ポインタが設定されている（リー
フ文字７である。図１参照）かどうかを判断する。エン
トリにヌル・ポインタが設定されている場合、それはリ
ーフ文字であり、削除される。エントリにヌル・ポイン
タが設定されていない場合、それはリーフ文字ではない
ので、カウンタは増分され、削除するリーフ文字を見つ
けるために、次のエントリが調べられる。当業者には、
エントリ削除ルーチン６１のようなプログラムはよく知
られている。使用カウントは、単に、削除対象のリーフ
・エントリを見つけるために探索が行われたエントリの
総数である。
【００７４】正規化使用カウント８９は、以下に示すよ
うに計算される。
うに計算される。
【００７５】
【数２】正規化使用カウント＝（使用カウント）／（エ
ントリ削除プログラムの呼出回数） 正規化使用カウント８９は、ステップ６５でレジスタ９
０の中にロードされ、符号化テーブル１６のツリー幅の
概算値として利用される。符号化テーブル１６のツリー
の平均幅は、正規化使用カウント８９に基づいて計算す
ることができ、以下の公式に基づいている。
ントリ削除プログラムの呼出回数） 正規化使用カウント８９は、ステップ６５でレジスタ９
０の中にロードされ、符号化テーブル１６のツリー幅の
概算値として利用される。符号化テーブル１６のツリー
の平均幅は、正規化使用カウント８９に基づいて計算す
ることができ、以下の公式に基づいている。
【００７６】平均幅＝１＋２＊正規化使用カウント 使用カウントは、調べられた文字またはエントリの総数
である。正規化使用カウント８９は、使用カウントの平
均値である。正規化使用カウント８９は、本明細書中、
符号化テーブル１６のツリーの平均幅を示すものとして
使用される。当業者は、計算された平均幅が、データ文
字間の相関関係を評価するために利用可能であり、符号
化テーブル１６のツリーの特徴を評価する他の基準を計
算することも可能であることが分かるであろう。当業者
は、使用カウント、正規化使用カウント、平均幅、また
はそれ以外の、符号化テーブル１６のツリーの形を示す
値を計算するための複数の異なった方法がわかるであろ
う。
である。正規化使用カウント８９は、使用カウントの平
均値である。正規化使用カウント８９は、本明細書中、
符号化テーブル１６のツリーの平均幅を示すものとして
使用される。当業者は、計算された平均幅が、データ文
字間の相関関係を評価するために利用可能であり、符号
化テーブル１６のツリーの特徴を評価する他の基準を計
算することも可能であることが分かるであろう。当業者
は、使用カウント、正規化使用カウント、平均幅、また
はそれ以外の、符号化テーブル１６のツリーの形を示す
値を計算するための複数の異なった方法がわかるであろ
う。
【００７７】図５のステップ６５を続行すると、正規化
使用カウント８９を使って概算される、符号化テーブル
１６のツリーの幅は、テーブル９３（図６（ａ））と比
較される。テーブル９３内では、使用カウント値９４ａ
−ｅおよび使用カウント・デルタ９２ａ−ｅが関係付け
られている。正規化使用カウント８９は、使用カウント
９４ａ−ｅの事前に決定したしきい値と比較される。使
用カウント値９４ａ−ｅは、正規化使用カウント８９を
相対値使用カウント・デルタ９２ａ−ｅに変換する。正
規化使用カウント値９４ａ−ｅは、それぞれ、６４、３
２、１６、８および４であるのが望ましい。ただし、こ
れらの値はデータ圧縮回路２０の感度を調整するために
変更できる。事前に決定した各使用カウント値９４ａ−
ｅは、使用カウント・デルタ９２ａ−ｅに関連付けられ
ている。使用カウント８９は使用カウント値９４ａ−ｅ
および対応する使用カウント・デルタ９２ａ−ｅと照合
される。例えば、正規化使用カウント８９が値４０とし
て計算されると、それにもっとも近い使用カウント値９
４ａ−ｅは、３２に等しい使用カウント値９４ｂであ
る。「−５」の使用カウント・デルタ９２ｂが、使用カ
ウント値９４ｂに割り当てられており、値「−５」は、
後述するように、性能指標１１０に加算される。
使用カウント８９を使って概算される、符号化テーブル
１６のツリーの幅は、テーブル９３（図６（ａ））と比
較される。テーブル９３内では、使用カウント値９４ａ
−ｅおよび使用カウント・デルタ９２ａ−ｅが関係付け
られている。正規化使用カウント８９は、使用カウント
９４ａ−ｅの事前に決定したしきい値と比較される。使
用カウント値９４ａ−ｅは、正規化使用カウント８９を
相対値使用カウント・デルタ９２ａ−ｅに変換する。正
規化使用カウント値９４ａ−ｅは、それぞれ、６４、３
２、１６、８および４であるのが望ましい。ただし、こ
れらの値はデータ圧縮回路２０の感度を調整するために
変更できる。事前に決定した各使用カウント値９４ａ−
ｅは、使用カウント・デルタ９２ａ−ｅに関連付けられ
ている。使用カウント８９は使用カウント値９４ａ−ｅ
および対応する使用カウント・デルタ９２ａ−ｅと照合
される。例えば、正規化使用カウント８９が値４０とし
て計算されると、それにもっとも近い使用カウント値９
４ａ−ｅは、３２に等しい使用カウント値９４ｂであ
る。「−５」の使用カウント・デルタ９２ｂが、使用カ
ウント値９４ｂに割り当てられており、値「−５」は、
後述するように、性能指標１１０に加算される。
【００７８】図５および図６（ｂ）を参照すると、デー
タの性質は、次に、レジスタ９５に格納されたデータ圧
縮率９６を使って、ステップ６８で分析される。圧縮率
９６は、コンピュータ９からモデム１０に入力されたビ
ット数を、モデム１０からモデム１５（図２）へ出力さ
れたビット数で割ったものである。モデム１０等の、今
日、販売されている「インテリジェント」モデムでは、
圧縮率は５００文字がコンピュータ９からモデム１０に
入った後に計算される。計算された圧縮率９６は、計算
されるたびに計算された圧縮率でロードされるモデム１
０内のメモリ位置からレジスタ９５の中にロードされる
のが望ましい。代わりに、プログラム・メモリ３１内の
プログラム６２は、事前に決定した文字数後毎に１度、
モデムにより達成されている圧縮率を計算することもで
きる。当業者は、圧縮率９６が計算される頻度を、希望
どおりに調整可能であることが分かるであろう。
タの性質は、次に、レジスタ９５に格納されたデータ圧
縮率９６を使って、ステップ６８で分析される。圧縮率
９６は、コンピュータ９からモデム１０に入力されたビ
ット数を、モデム１０からモデム１５（図２）へ出力さ
れたビット数で割ったものである。モデム１０等の、今
日、販売されている「インテリジェント」モデムでは、
圧縮率は５００文字がコンピュータ９からモデム１０に
入った後に計算される。計算された圧縮率９６は、計算
されるたびに計算された圧縮率でロードされるモデム１
０内のメモリ位置からレジスタ９５の中にロードされる
のが望ましい。代わりに、プログラム・メモリ３１内の
プログラム６２は、事前に決定した文字数後毎に１度、
モデムにより達成されている圧縮率を計算することもで
きる。当業者は、圧縮率９６が計算される頻度を、希望
どおりに調整可能であることが分かるであろう。
【００７９】レジスタ９５内の圧縮率９６は、圧縮率デ
ルタ９９ａ−ｅ（図６（ｂ））を計算するために、圧縮
率値９８ａ−ｅのテーブル９７と比較される。例えば、
圧縮率９６が１．１である場合、圧縮率は、事前に決定
した圧縮率値９８ａ−ｅに比較され、「１．０」にもっ
とも近い。したがって、この例では、「−１０」に等し
い圧縮率デルタ９９ａが、「１．１」という圧縮率と関
係付けられる。圧縮率レジスタ９６が圧縮率デルタ９９
ａ−ｅと照合された後、デルタは性能指標１１０に加算
される。
ルタ９９ａ−ｅ（図６（ｂ））を計算するために、圧縮
率値９８ａ−ｅのテーブル９７と比較される。例えば、
圧縮率９６が１．１である場合、圧縮率は、事前に決定
した圧縮率値９８ａ−ｅに比較され、「１．０」にもっ
とも近い。したがって、この例では、「−１０」に等し
い圧縮率デルタ９９ａが、「１．１」という圧縮率と関
係付けられる。圧縮率レジスタ９６が圧縮率デルタ９９
ａ−ｅと照合された後、デルタは性能指標１１０に加算
される。
【００８０】図５および図６（ｃ）を参照すると、ステ
ップ６５で決定された使用カウント・デルタ９２ａ−ｅ
およびステップ６８で決定された圧縮率デルタ９９ａ−
ｅは、ステップ７２で性能指標１１０を計算するのに使
用される。この例では、使用カウント・デルタ９２ｅお
よび圧縮率デルタ９９ａが、性能指標１１０に加えられ
る。それ以降、ステップ７４および７６で、性能指標１
１０は、それぞれ事前に決定した第１および第２しきい
値１２０および１２２と比較される。本実施の形態で
は、高しきい値１２０が１００と等しく、低しきい値１
２２が０に等しい。しきい値１２０、１２２は、メモリ
３１（図３）に格納されている。低しきい値と高しきい
値を、システムの感度を制御するために調整することに
より、符号化テーブル１６のサイズの変更頻度を増減で
きることは、当業者にとって明かであろう。さらに、ス
テップ７４および７６の実行の順序は、固定されていな
い。
ップ６５で決定された使用カウント・デルタ９２ａ−ｅ
およびステップ６８で決定された圧縮率デルタ９９ａ−
ｅは、ステップ７２で性能指標１１０を計算するのに使
用される。この例では、使用カウント・デルタ９２ｅお
よび圧縮率デルタ９９ａが、性能指標１１０に加えられ
る。それ以降、ステップ７４および７６で、性能指標１
１０は、それぞれ事前に決定した第１および第２しきい
値１２０および１２２と比較される。本実施の形態で
は、高しきい値１２０が１００と等しく、低しきい値１
２２が０に等しい。しきい値１２０、１２２は、メモリ
３１（図３）に格納されている。低しきい値と高しきい
値を、システムの感度を制御するために調整することに
より、符号化テーブル１６のサイズの変更頻度を増減で
きることは、当業者にとって明かであろう。さらに、ス
テップ７４および７６の実行の順序は、固定されていな
い。
【００８１】性能指標１１０が、ステップ７４で、高し
きい値１２０より大きいと判断されると、「ＹＥＳ」ブ
ランチに従ってステップ７５に進み、符号化テーブル１
６のサイズが増やされる。他方、ステップ７６で性能指
標１１０が低しきい値１２２より低いと、符号化テーブ
ル１６のサイズはステップ７７で小さくされる。
きい値１２０より大きいと判断されると、「ＹＥＳ」ブ
ランチに従ってステップ７５に進み、符号化テーブル１
６のサイズが増やされる。他方、ステップ７６で性能指
標１１０が低しきい値１２２より低いと、符号化テーブ
ル１６のサイズはステップ７７で小さくされる。
【００８２】性能指標１１０がしきい値１２０と１２２
の間の値である場合、ステップ７４および７６で「Ｎ
Ｏ」ブランチに従い、符号化テーブル１６が入力データ
を符号化するために正しいサイズであることが示され
る。このようにして、符号化テーブル１６のサイズは、
該サイズが、モデム１０に到達するデータ文字ストリー
ムの間の相関関係に比較して適切ではない場合にのみ、
調整される。
の間の値である場合、ステップ７４および７６で「Ｎ
Ｏ」ブランチに従い、符号化テーブル１６が入力データ
を符号化するために正しいサイズであることが示され
る。このようにして、符号化テーブル１６のサイズは、
該サイズが、モデム１０に到達するデータ文字ストリー
ムの間の相関関係に比較して適切ではない場合にのみ、
調整される。
【００８３】ステップ６６を要約すると、性能指標１１
０がステップ７４で高しきい値１２０より大きい場合、
正規化使用カウント８９および圧縮率９６の値が性能指
標１１０を調整するために結合され、入力データが強く
相関関係付けられていることを示す。このようにして、
符号化テーブル１６に割り当てられるメモリ・スペース
は、ステップ７５で増やされる。他方、性能指標１１０
が、ステップ７６で低しきい値１２２より低い場合、正
規化使用カウント８９および圧縮率９６は、性能指数１
１０が、入力データが、よくても弱い相関関係にあるこ
とを示すようしたことになる。したがって、符号化テー
ブル１６に割り当てられるメモリ・スペースは、ステッ
プ７７で減らされる。
０がステップ７４で高しきい値１２０より大きい場合、
正規化使用カウント８９および圧縮率９６の値が性能指
標１１０を調整するために結合され、入力データが強く
相関関係付けられていることを示す。このようにして、
符号化テーブル１６に割り当てられるメモリ・スペース
は、ステップ７５で増やされる。他方、性能指標１１０
が、ステップ７６で低しきい値１２２より低い場合、正
規化使用カウント８９および圧縮率９６は、性能指数１
１０が、入力データが、よくても弱い相関関係にあるこ
とを示すようしたことになる。したがって、符号化テー
ブル１６に割り当てられるメモリ・スペースは、ステッ
プ７７で減らされる。
【００８４】当業者は、性能指標１１０、使用カウント
・デルタ９２ａ−ｅ、圧縮率デルタ９９ａ−ｅ、および
しきい値１２０と１２２が相対的なものであり、希望の
通りに変更できることが分かるであろう。本明細書中に
記述されている使用カウント値９４ａ−ｅおよび圧縮率
値９８ａ−ｅは例示的なもので、ユーザはそれ以外の値
を選択することができ、設計の仕様に従って、これらの
値より多くまたは少なく設定することができる。さら
に、符号化テーブル１６のサイズは、本発明の範囲内の
さまざまなレベルで増減させることができる。使用カウ
ント・デルタ９２ａ−ｅ、圧縮率デルタ９９ａ−ｅ、お
よび性能増分（後述する）の値が適切に変更されるなら
ば、性能指標１１０が事前に決定したしきい以上の（ま
たは、等しい）場合、符号化テーブル１６のサイズが大
きくされ、性能指標１１０が事前に決定したしきい以下
の（または、等しい）場合、符号化テーブル１６のサイ
ズが減らされることは明かであろう。
・デルタ９２ａ−ｅ、圧縮率デルタ９９ａ−ｅ、および
しきい値１２０と１２２が相対的なものであり、希望の
通りに変更できることが分かるであろう。本明細書中に
記述されている使用カウント値９４ａ−ｅおよび圧縮率
値９８ａ−ｅは例示的なもので、ユーザはそれ以外の値
を選択することができ、設計の仕様に従って、これらの
値より多くまたは少なく設定することができる。さら
に、符号化テーブル１６のサイズは、本発明の範囲内の
さまざまなレベルで増減させることができる。使用カウ
ント・デルタ９２ａ−ｅ、圧縮率デルタ９９ａ−ｅ、お
よび性能増分（後述する）の値が適切に変更されるなら
ば、性能指標１１０が事前に決定したしきい以上の（ま
たは、等しい）場合、符号化テーブル１６のサイズが大
きくされ、性能指標１１０が事前に決定したしきい以下
の（または、等しい）場合、符号化テーブル１６のサイ
ズが減らされることは明かであろう。
【００８５】符号化テーブル１６のサイズは、次に示す
ように、ＲＡＭ３５内で増減される。符号化テーブル１
６に割り当てられるメモリ・スペースがステップ７７で
増やされる場合、符号化テーブルのストリングの長さ、
最大コードワード・サイズ、およびコードワードの総数
等の、符号化テーブル１６のサイズを制限するパラメー
タが増やされる。パラメータを増加させると、符号化テ
ーブル１６内のストリング、および符号化テーブル自体
がより大きなサイズになるようになる。符号化テーブル
１６に割り当てられる新しいメモリ・スペースには、デ
ータ文字がモデム１０で受け取られるに従って、ストリ
ングがロードされる。
ように、ＲＡＭ３５内で増減される。符号化テーブル１
６に割り当てられるメモリ・スペースがステップ７７で
増やされる場合、符号化テーブルのストリングの長さ、
最大コードワード・サイズ、およびコードワードの総数
等の、符号化テーブル１６のサイズを制限するパラメー
タが増やされる。パラメータを増加させると、符号化テ
ーブル１６内のストリング、および符号化テーブル自体
がより大きなサイズになるようになる。符号化テーブル
１６に割り当てられる新しいメモリ・スペースには、デ
ータ文字がモデム１０で受け取られるに従って、ストリ
ングがロードされる。
【００８６】符号化テーブル１６に割り当てられるメモ
リ・スペースがステップ７５で減らされる場合は、符号
化テーブル１６から既存のエントリを削除しなければな
らない。本実施の形態では、符号化テーブル１６は、符
号化テーブル１６のサイズが減らされるときは、完全に
再初期化される。具体的には、ルート文字４を除くすべ
ての文字が削除され、符号化テーブル１６のサイズを制
限するパラメータである、符号化テーブルのストリング
の長さ、最大コードワード・サイズ、およびコードワー
ドの総数が減らされる。それから、ストリング５は、モ
デム１０ではデータが受け取られていなかったかのよう
に、符号化テーブル１６の中のルート文字４から発展す
る。当業者には明かであるように、符号化テーブル１６
を再初期化すると、ストリング５が形成され、現在の小
さくなった符号化テーブル１６に割り当てられたＲＡＭ
３５を満たす間、ある程度の遅延が生じる。しかし、符
号化テーブル１６のサイズが減らされた時は、データの
ストリームの文字の相関関係は弱く、符号化テーブル１
６は、再初期化される前、データをうまく圧縮していな
かった。したがって、符号化テーブル１６を再初期化す
ることは有効である。当業者は、テーブル１６から選択
して文字を削除することにより、テーブル１６のサイズ
を減らすことも可能であることが分かるであろう。ただ
し、この場合、テーブルのサイズの調整に費やされるマ
イクロプロセッサ３０の時間は増加する。
リ・スペースがステップ７５で減らされる場合は、符号
化テーブル１６から既存のエントリを削除しなければな
らない。本実施の形態では、符号化テーブル１６は、符
号化テーブル１６のサイズが減らされるときは、完全に
再初期化される。具体的には、ルート文字４を除くすべ
ての文字が削除され、符号化テーブル１６のサイズを制
限するパラメータである、符号化テーブルのストリング
の長さ、最大コードワード・サイズ、およびコードワー
ドの総数が減らされる。それから、ストリング５は、モ
デム１０ではデータが受け取られていなかったかのよう
に、符号化テーブル１６の中のルート文字４から発展す
る。当業者には明かであるように、符号化テーブル１６
を再初期化すると、ストリング５が形成され、現在の小
さくなった符号化テーブル１６に割り当てられたＲＡＭ
３５を満たす間、ある程度の遅延が生じる。しかし、符
号化テーブル１６のサイズが減らされた時は、データの
ストリームの文字の相関関係は弱く、符号化テーブル１
６は、再初期化される前、データをうまく圧縮していな
かった。したがって、符号化テーブル１６を再初期化す
ることは有効である。当業者は、テーブル１６から選択
して文字を削除することにより、テーブル１６のサイズ
を減らすことも可能であることが分かるであろう。ただ
し、この場合、テーブルのサイズの調整に費やされるマ
イクロプロセッサ３０の時間は増加する。
【００８７】符号化テーブル１６のサイズが、ステップ
７７で減らされるか、ステップ７５で増やされた後、性
能指標１１０はステップ７８で中間値にセットし直され
る。性能指標１１０は値「５０」（「１００」という高
しきい値１２９と「０」という低しきい値の間）にセッ
トし直されるのが望ましい。このようにして、データ文
字間の相関関係を検出し、それに応えて性能指標１１０
を調整し、符号化テーブル１６のサイズを調整するプロ
セスが繰り返される。必要であれば、この時点でしきい
値、または前記のそれ以外の値を変更し、データ文字間
の相関関係に対する感度を増減させることができる。
７７で減らされるか、ステップ７５で増やされた後、性
能指標１１０はステップ７８で中間値にセットし直され
る。性能指標１１０は値「５０」（「１００」という高
しきい値１２９と「０」という低しきい値の間）にセッ
トし直されるのが望ましい。このようにして、データ文
字間の相関関係を検出し、それに応えて性能指標１１０
を調整し、符号化テーブル１６のサイズを調整するプロ
セスが繰り返される。必要であれば、この時点でしきい
値、または前記のそれ以外の値を変更し、データ文字間
の相関関係に対する感度を増減させることができる。
【００８８】符号化テーブル１１６のサイズが変更され
るかどうかに関係なく、図５のステップ８０に入る。ス
テップ８０は、性能指標１１０に対して、事前に決定し
た性能増分を加算または減算することを要求する。具体
的には、本実施の形態では、事前に決定した値は、
「５」という値を持つ性能増分である。図７は、性能指
標に性能増分を加えるために講じられるステップのフロ
ーチャートである。簡単に図７を参照すると、性能指標
１１０がステップ８２で「５５」より大きい場合、
「５」という性能増分がステップ８４で性能指標１１０
から差し引かれる。性能指標がステップ８６で「４５」
未満であると、性能増分「５」がステップ８８で性能指
標１１０に加えられる。ステップ８０の後、プログラム
は図４のステップ５０に戻る。
るかどうかに関係なく、図５のステップ８０に入る。ス
テップ８０は、性能指標１１０に対して、事前に決定し
た性能増分を加算または減算することを要求する。具体
的には、本実施の形態では、事前に決定した値は、
「５」という値を持つ性能増分である。図７は、性能指
標に性能増分を加えるために講じられるステップのフロ
ーチャートである。簡単に図７を参照すると、性能指標
１１０がステップ８２で「５５」より大きい場合、
「５」という性能増分がステップ８４で性能指標１１０
から差し引かれる。性能指標がステップ８６で「４５」
未満であると、性能増分「５」がステップ８８で性能指
標１１０に加えられる。ステップ８０の後、プログラム
は図４のステップ５０に戻る。
【００８９】図７に示されたステップの効果は、性能指
標１１０を中間値にわずかに近づけることである。使用
カウント・デルタ９２ａ−ｅおよび圧縮率デルタ９９ａ
−ｅの小さい値が、ゆっくりと性能指標１１０に加えら
れ、最終的に符号化テーブル１６のサイズの変更を生じ
させることは望ましくない。性能増分は、データ圧縮回
路２０（図３）に到達するデータ・ストリーム内の文字
間の相関関係の実質的な変化に対応してのみ発生するよ
うに、符号化テーブル１６のサイズに対する変更を制限
する。性能指標の値が、システム感度を増減させるため
に選択可能であることは当業者にとって明かであろう。
標１１０を中間値にわずかに近づけることである。使用
カウント・デルタ９２ａ−ｅおよび圧縮率デルタ９９ａ
−ｅの小さい値が、ゆっくりと性能指標１１０に加えら
れ、最終的に符号化テーブル１６のサイズの変更を生じ
させることは望ましくない。性能増分は、データ圧縮回
路２０（図３）に到達するデータ・ストリーム内の文字
間の相関関係の実質的な変化に対応してのみ発生するよ
うに、符号化テーブル１６のサイズに対する変更を制限
する。性能指標の値が、システム感度を増減させるため
に選択可能であることは当業者にとって明かであろう。
【００９０】実施の形態では、符号化テーブルのサイズ
は増分で調整される。例えば、望ましい実施の形態で
は、符号化テーブル１６のサイズは最初は２０４８エン
トリである。符号化テーブル１６に割り当てられるメモ
リ・スペースがステップ７５（図５）で増やされると、
符号化テーブル１６は４０９６エントリに増やされる。
符号化テーブル１６の次の増分ステップは、８１９２エ
ントリである。これが本実施の形態の符号化テーブル１
６の最大サイズである。ただし、当業者にとっては明ら
かなように、符号化テーブル１６をさらに小さくしたり
または大きくしたりできるし、増分ステップをさらに広
くしたり細かくしたりすることができる。同様に、望ま
しい符号化テーブル１６は、サイズが８１９２エント
リ、４０９６エントリ、２０４８エントリから１０２４
エントリへ、段階的に減らされる。
は増分で調整される。例えば、望ましい実施の形態で
は、符号化テーブル１６のサイズは最初は２０４８エン
トリである。符号化テーブル１６に割り当てられるメモ
リ・スペースがステップ７５（図５）で増やされると、
符号化テーブル１６は４０９６エントリに増やされる。
符号化テーブル１６の次の増分ステップは、８１９２エ
ントリである。これが本実施の形態の符号化テーブル１
６の最大サイズである。ただし、当業者にとっては明ら
かなように、符号化テーブル１６をさらに小さくしたり
または大きくしたりできるし、増分ステップをさらに広
くしたり細かくしたりすることができる。同様に、望ま
しい符号化テーブル１６は、サイズが８１９２エント
リ、４０９６エントリ、２０４８エントリから１０２４
エントリへ、段階的に減らされる。
【００９１】符号化テーブル１６のサイズが調整される
に従って、コードワードのサイズも同様に調整される。
例えば、コードワードは、符号化テーブル１６のサイズ
が１０２４エントリ、２０４８エントリ、４０９６エン
トリと増分されるのに従って、１０ビット、１１ビッ
ト、１２ビットと増やされる。これにより、伝送される
データのタイプに対応するように、コードワードのサイ
ズが調整される。
に従って、コードワードのサイズも同様に調整される。
例えば、コードワードは、符号化テーブル１６のサイズ
が１０２４エントリ、２０４８エントリ、４０９６エン
トリと増分されるのに従って、１０ビット、１１ビッ
ト、１２ビットと増やされる。これにより、伝送される
データのタイプに対応するように、コードワードのサイ
ズが調整される。
【００９２】符号化テーブル１６の特徴に基づいてデー
タ文字間の相関関係を判断する方法は複数ある。具体的
には、例えば、ツリー幅を決定するために、符号化テー
ブル１６全体でのリーフ文字７の総数をカウントしても
よい。正規化使用カウント８９が、エントリ削除ルーチ
ン６１の間以外にも計算され得ることは、当業者にとっ
て明かであろう。例えば、正規化使用カウント８９は、
各データ文字がモデム１０で受け取られた後、あるいは
事前に決定した文字数がモデム１０で受け取られて後
（例えば、１００文字ごとに）、決定するようにするこ
とができる。当業者は、符号化テーブル１６の特徴を、
モデム１０で受け取られる各文字を符号化テーブル内の
文字と照合しようとするプログラムの探索ループ部分
（図４のステップ５４および５８）の間、またはシステ
ム・デザイナーにより選択されるそれ以外の時点で分析
されるようにすることができることが分かるであろう。
しかしながら、符号化テーブルの特徴の計算するための
処理負担は、最小限に抑えられるべきである。
タ文字間の相関関係を判断する方法は複数ある。具体的
には、例えば、ツリー幅を決定するために、符号化テー
ブル１６全体でのリーフ文字７の総数をカウントしても
よい。正規化使用カウント８９が、エントリ削除ルーチ
ン６１の間以外にも計算され得ることは、当業者にとっ
て明かであろう。例えば、正規化使用カウント８９は、
各データ文字がモデム１０で受け取られた後、あるいは
事前に決定した文字数がモデム１０で受け取られて後
（例えば、１００文字ごとに）、決定するようにするこ
とができる。当業者は、符号化テーブル１６の特徴を、
モデム１０で受け取られる各文字を符号化テーブル内の
文字と照合しようとするプログラムの探索ループ部分
（図４のステップ５４および５８）の間、またはシステ
ム・デザイナーにより選択されるそれ以外の時点で分析
されるようにすることができることが分かるであろう。
しかしながら、符号化テーブルの特徴の計算するための
処理負担は、最小限に抑えられるべきである。
【００９３】要約すると、データ圧縮回路２０の実施の
形態は、符号化テーブル１６のサイズを調整する方法を
実行し、データ圧縮を最適化し、費やされるマイクロプ
ロセッサ３０の時間を最小限に抑えるために、図５に示
されるように以下のステップ（ａ）〜（ｅ）を行う。
形態は、符号化テーブル１６のサイズを調整する方法を
実行し、データ圧縮を最適化し、費やされるマイクロプ
ロセッサ３０の時間を最小限に抑えるために、図５に示
されるように以下のステップ（ａ）〜（ｅ）を行う。
【００９４】（ａ）ステップ６５で正規化使用カウント
８９および使用カウント・デルタ９２ａ−ｅを決定す
る。
８９および使用カウント・デルタ９２ａ−ｅを決定す
る。
【００９５】（ｂ）ステップ６８でデータの圧縮率９６
および圧縮率デルタ９９ａ−ｅを決定する。
および圧縮率デルタ９９ａ−ｅを決定する。
【００９６】（ｃ）ステップ７２で性能指標１１０に、
使用カウント・デルタ９２ａ−ｅおよび圧縮率デルタ９
９ａ−ｅを追加する。
使用カウント・デルタ９２ａ−ｅおよび圧縮率デルタ９
９ａ−ｅを追加する。
【００９７】（ｄ）性能指標１１０と、第１低しきい値
及び第２高しきい値を、それぞれステップ７４および７
６で比較する。
及び第２高しきい値を、それぞれステップ７４および７
６で比較する。
【００９８】（ｉ）性能指標１１０がステップ７４で高
しきい値１２０より大きい場合、符号化テーブル１６に
割り当てられるＲＡＭ３５内のメモリ・スペースを増や
す。
しきい値１２０より大きい場合、符号化テーブル１６に
割り当てられるＲＡＭ３５内のメモリ・スペースを増や
す。
【００９９】（ｉｉ）性能指標１１０がステップ７６で
低しきい値１２２未満の場合、符号化テーブル１６に割
り当てられるＲＡＭ３５内のメモリ・スペースを減ら
す。 （ｉｉｉ）符号化テーブル内の平均ツリー幅が高しきい
値１２０と低しきい値１２２の間の場合、符号化テーブ
ルのサイズを調整しない。
低しきい値１２２未満の場合、符号化テーブル１６に割
り当てられるＲＡＭ３５内のメモリ・スペースを減ら
す。 （ｉｉｉ）符号化テーブル内の平均ツリー幅が高しきい
値１２０と低しきい値１２２の間の場合、符号化テーブ
ルのサイズを調整しない。
【０１００】（ｅ）ステップ８０で性能増分に制動係数
を加える。
を加える。
【０１０１】符号化テーブル１６を修正するために図４
および図５で講じられるステップは、モデム１５（図
２）の復号化テーブル１８で同様に行われる。当業者
は、同一の符号化テーブル１６と復号化テーブル１８を
それぞれ同時に維持する方法をよく知っている。例え
ば、図５において、符号化テーブル１６のサイズがステ
ップ７５で増やされると、あるいはステップ７７で減ら
されると、それに従って、復号化テーブル１８のサイズ
も、モデム１５で実行される図４−７と同様の動作によ
り調整される。
および図５で講じられるステップは、モデム１５（図
２）の復号化テーブル１８で同様に行われる。当業者
は、同一の符号化テーブル１６と復号化テーブル１８を
それぞれ同時に維持する方法をよく知っている。例え
ば、図５において、符号化テーブル１６のサイズがステ
ップ７５で増やされると、あるいはステップ７７で減ら
されると、それに従って、復号化テーブル１８のサイズ
も、モデム１５で実行される図４−７と同様の動作によ
り調整される。
【０１０２】当業者は、性能指標が、データのランダム
または非ランダム（相関関連を有する）性質を測定する
ために使われる相対値であることが分かるであろう。他
の尺度または基準を利用して、データ文字間の相関関係
を反映し、追跡することもできる。さらに、使用カウン
トまたは圧縮率のどちらかを個別に性能指標に加えるこ
とも可能であるし、性能指標を計算するために、他の基
準を、個別にあるいは一緒に利用することもできる。
または非ランダム（相関関連を有する）性質を測定する
ために使われる相対値であることが分かるであろう。他
の尺度または基準を利用して、データ文字間の相関関係
を反映し、追跡することもできる。さらに、使用カウン
トまたは圧縮率のどちらかを個別に性能指標に加えるこ
とも可能であるし、性能指標を計算するために、他の基
準を、個別にあるいは一緒に利用することもできる。
【０１０３】また、符号化テーブルを調整するサイズ
は、設計者および本発明のユーザの好みの問題である。
本発明は、圧縮されるデータ間の相関関係を評価し、そ
れに基づいてデータ圧縮に使われる符号化テーブルのサ
イズを調整するのに符号化テーブルの特徴が利用される
あらゆるシステムを実現する。
は、設計者および本発明のユーザの好みの問題である。
本発明は、圧縮されるデータ間の相関関係を評価し、そ
れに基づいてデータ圧縮に使われる符号化テーブルのサ
イズを調整するのに符号化テーブルの特徴が利用される
あらゆるシステムを実現する。
【０１０４】当業者にとって、前記の実施の形態がデー
タ通信環境外で利用するために変更できることも明かで
あろう。データの相関関係の性質に応えて符号化テーブ
ルのサイズをリアルタイムで調整する技法は、データベ
ースにデータを格納するコンピュータ内等のさまざまな
環境でのデータ圧縮に利用できる。本発明の範囲は、こ
のようなシステムを含むことを意図している。さらに、
本発明は、Ｖ．４２ｂｉｓ以外の符号化スキームととも
に利用してもよい。
タ通信環境外で利用するために変更できることも明かで
あろう。データの相関関係の性質に応えて符号化テーブ
ルのサイズをリアルタイムで調整する技法は、データベ
ースにデータを格納するコンピュータ内等のさまざまな
環境でのデータ圧縮に利用できる。本発明の範囲は、こ
のようなシステムを含むことを意図している。さらに、
本発明は、Ｖ．４２ｂｉｓ以外の符号化スキームととも
に利用してもよい。
【０１０５】当業者には明かになるように、本発明は、
ファジー論理やニューラル・ネットワークのような技法
を利用した実現に非常に適している。図８（ａ）および
（ｂ）は、それぞれ使用カウント値９４ａ−ｅおよび圧
縮率値９８ａ−ｅに関連付けられたファジー集合を示
す。従来の論理または集合論では、アイテムはある集合
または別の集合に属すると見なされている。したがっ
て、図８（ａ）および（ｂ）は、大まかに、使用カウン
ト値９４ａ−ｅと圧縮率値９９ａ−ｅを非常に高いから
非常に低いまでの集合に関連付けている。
ファジー論理やニューラル・ネットワークのような技法
を利用した実現に非常に適している。図８（ａ）および
（ｂ）は、それぞれ使用カウント値９４ａ−ｅおよび圧
縮率値９８ａ−ｅに関連付けられたファジー集合を示
す。従来の論理または集合論では、アイテムはある集合
または別の集合に属すると見なされている。したがっ
て、図８（ａ）および（ｂ）は、大まかに、使用カウン
ト値９４ａ−ｅと圧縮率値９９ａ−ｅを非常に高いから
非常に低いまでの集合に関連付けている。
【０１０６】しかしながら、ファジー集合論では、値
は、集合への所属度を持つと見なされ、複数の集合に属
し得る。メンバシップ関数は、値と集合の関係を定義す
る。図９（ａ）は、計算された正規化使用カウント８９
の実例となるメンバシップ関数、および「非常に高い」
１２０ａ、「高い」１２０ｂ、「中間」１２０ｃ、「低
い」１２０ｄ、および「非常に低い」１２０ｅという集
合を示す。図９（ｂ）は、圧縮率９６（図６（ｂ））の
実例となるメンバシップ関数および「非常に高い］１２
２ａ、「高い」１２２ｂ、「中間」１２２ｃ、「低い」
１２２ｄ、および「非常に低い」１２２ｅという集合を
示す。したがって、図９（ａ）および（ｂ）の集合のそ
れぞれの所属は、「非常に高い」、「高い」、「中
間」、「低い」および「非常に低い」である。
は、集合への所属度を持つと見なされ、複数の集合に属
し得る。メンバシップ関数は、値と集合の関係を定義す
る。図９（ａ）は、計算された正規化使用カウント８９
の実例となるメンバシップ関数、および「非常に高い」
１２０ａ、「高い」１２０ｂ、「中間」１２０ｃ、「低
い」１２０ｄ、および「非常に低い」１２０ｅという集
合を示す。図９（ｂ）は、圧縮率９６（図６（ｂ））の
実例となるメンバシップ関数および「非常に高い］１２
２ａ、「高い」１２２ｂ、「中間」１２２ｃ、「低い」
１２２ｄ、および「非常に低い」１２２ｅという集合を
示す。したがって、図９（ａ）および（ｂ）の集合のそ
れぞれの所属は、「非常に高い」、「高い」、「中
間」、「低い」および「非常に低い」である。
【０１０７】例えば、図９（ａ）に示すように、正規化
利用カウント８９が２５であると、これは集合「中間」
１２０ｃに対して所属度が０．４で、集合「高い」１２
０ｂに対して所属度が０．６であることになり、使用カ
ウント・デルタ９２は、以下に示すように、各集合に対
応する値の重み付けされた和として計算される。
利用カウント８９が２５であると、これは集合「中間」
１２０ｃに対して所属度が０．４で、集合「高い」１２
０ｂに対して所属度が０．６であることになり、使用カ
ウント・デルタ９２は、以下に示すように、各集合に対
応する値の重み付けされた和として計算される。
【０１０８】
【数３】使用カウント・デルタ＝０．４＊０＋０．６＊
（−５）＝−３ 同様に、図９（ｂ）に示すように、圧縮率９５が１．８
である場合、集合「低い」１２２ｂに対する所属度は
０．２で、集合「中間」１２２ｃに対する所属度は０．
８になる。圧縮率デルタ９９は、各集合に対応する値の
重み付けされた和として計算される。
（−５）＝−３ 同様に、図９（ｂ）に示すように、圧縮率９５が１．８
である場合、集合「低い」１２２ｂに対する所属度は
０．２で、集合「中間」１２２ｃに対する所属度は０．
８になる。圧縮率デルタ９９は、各集合に対応する値の
重み付けされた和として計算される。
【０１０９】
【数４】圧縮率デルタ＝０．２＊（−５）＋０．８＊０
＝−１ それから、性能指標１１０は、前記の計算済みのデルタ
値を使って、以下に示すように計算される。
＝−１ それから、性能指標１１０は、前記の計算済みのデルタ
値を使って、以下に示すように計算される。
【０１１０】
【数５】性能指標＝前の性能指標＋使用カウント・デル
タ＋圧縮率デルタ したがって、上記の例では、「−３」という使用カウン
ト・デルタと「−１」という圧縮率デルタの加算に基づ
いて、「−４」という値が性能指標１１０に加えられ
る。
タ＋圧縮率デルタ したがって、上記の例では、「−３」という使用カウン
ト・デルタと「−１」という圧縮率デルタの加算に基づ
いて、「−４」という値が性能指標１１０に加えられ
る。
【０１１１】図１０および図３に従って、本発明により
提供される別の機能が示される。具体的には、データ
は、モデム１０でデータ圧縮回路２０により圧縮される
前にラン・レングス符号化（ＲＬＥ）プログラム１３０
により前処理される。ＲＬＥ１３０は、プログラム・メ
モリ３１に記憶されるのが望ましいが、それ以外の、モ
デム１０あるいはコンピュータ９内のメモリ・ロケーシ
ョンに格納することもできる。
提供される別の機能が示される。具体的には、データ
は、モデム１０でデータ圧縮回路２０により圧縮される
前にラン・レングス符号化（ＲＬＥ）プログラム１３０
により前処理される。ＲＬＥ１３０は、プログラム・メ
モリ３１に記憶されるのが望ましいが、それ以外の、モ
デム１０あるいはコンピュータ９内のメモリ・ロケーシ
ョンに格納することもできる。
【０１１２】本実施の形態では、出ていくデータがデー
タ圧縮回路２０に渡される前に、データはＲＬＥ１３０
により分析される。ＲＬＥ１３０は、（１）一連の連続
する同一文字を検出し、（２）その一連の同一文字をコ
ードワードで置換するという２つの一般的なステップを
実行する。ＲＬＥ１３０は、文字が符号化テ−ブル１６
及び復号化テ−ブル１８（図３）を歪める前に、同一連
続文字の連なりを取り除く。
タ圧縮回路２０に渡される前に、データはＲＬＥ１３０
により分析される。ＲＬＥ１３０は、（１）一連の連続
する同一文字を検出し、（２）その一連の同一文字をコ
ードワードで置換するという２つの一般的なステップを
実行する。ＲＬＥ１３０は、文字が符号化テ−ブル１６
及び復号化テ−ブル１８（図３）を歪める前に、同一連
続文字の連なりを取り除く。
【０１１３】図１０を参照すると、ラン・レングス符号
化プログラム１３０の詳細な動作が示されている。望ま
しいＲＬＥ１３０は、ステップ１３２でデータ・バス２
５（図３）上の第１文字を検出するように書かれたソフ
トウェアである。ステップ１３４で、第１文字は格納さ
れ、カウンタは増分され、第１文字は、符号化テーブル
１６を使って第１文字を符号化するために、図４に示さ
れるプログラムの実行を開始するマイクロプロセッサ３
０により調べられる。
化プログラム１３０の詳細な動作が示されている。望ま
しいＲＬＥ１３０は、ステップ１３２でデータ・バス２
５（図３）上の第１文字を検出するように書かれたソフ
トウェアである。ステップ１３４で、第１文字は格納さ
れ、カウンタは増分され、第１文字は、符号化テーブル
１６を使って第１文字を符号化するために、図４に示さ
れるプログラムの実行を開始するマイクロプロセッサ３
０により調べられる。
【０１１４】ステップ１３６で、第２文字が検出され
る。第１文字および第２文字は、ステップ１３８で比較
される。ステップ１３８で文字が同一ではないと決定さ
れる場合、ラン・レングス符号化プログラム１３０は、
「ＮＯ」ブランチに従い、ステップ１３２へ進み、再度
開始される。
る。第１文字および第２文字は、ステップ１３８で比較
される。ステップ１３８で文字が同一ではないと決定さ
れる場合、ラン・レングス符号化プログラム１３０は、
「ＮＯ」ブランチに従い、ステップ１３２へ進み、再度
開始される。
【０１１５】他方、第１文字と第２文字がステップ１３
８で同一であると決定される場合は、「ＹＥＳ」ブラン
チに従って、ステップ１４０に進む。ステップ１４０で
は、カウンタが増分され、別の同一文字が検出されたこ
とを示す。さらに、第２文字は、前述のように、符号化
テーブル１６を利用して第２文字を符号化するために、
図４に示されるプログラムの実行を開始するマイクロプ
ロセッサにより調べられる。
８で同一であると決定される場合は、「ＹＥＳ」ブラン
チに従って、ステップ１４０に進む。ステップ１４０で
は、カウンタが増分され、別の同一文字が検出されたこ
とを示す。さらに、第２文字は、前述のように、符号化
テーブル１６を利用して第２文字を符号化するために、
図４に示されるプログラムの実行を開始するマイクロプ
ロセッサにより調べられる。
【０１１６】ステップ１４２で、カウンタ・トータルが
分析される。カウンタ・トータルがステップ１４２で３
未満の場合、「ＮＯ」ブランチに従いステップ１３６に
進み、次の文字を待つ。したがって、カウンタ・トータ
ルが、３つの連続した同一文字が検出されたことを意味
する３に等しくなるまで、データ文字は単に観察される
のみで、図４に示されるような符号化テーブル１６を使
った符号化のために渡される。
分析される。カウンタ・トータルがステップ１４２で３
未満の場合、「ＮＯ」ブランチに従いステップ１３６に
進み、次の文字を待つ。したがって、カウンタ・トータ
ルが、３つの連続した同一文字が検出されたことを意味
する３に等しくなるまで、データ文字は単に観察される
のみで、図４に示されるような符号化テーブル１６を使
った符号化のために渡される。
【０１１７】３つの同一文字が連続して受け取られる
と、カウンタ・トータルはステップ１４２で３に等しく
なる。この場合、「ＹＥＳ」ブランチに従い、ステップ
１４４が実行される。ステップ１４４では、３つの同一
文字に続く文字が検出される。ステップ１４６で後に受
け取られた各文字が３つの同一文字と同一であると確認
されると、カウンタがステップ１４８で増分される。さ
らに文字は保持され、文字が符号化テーブル１６を使っ
て符号化されていないため、モデム１０から送出されな
いことを意味する。ステップ１４８の後で、モデム１０
はステップ１４４で別の文字を待つ。
と、カウンタ・トータルはステップ１４２で３に等しく
なる。この場合、「ＹＥＳ」ブランチに従い、ステップ
１４４が実行される。ステップ１４４では、３つの同一
文字に続く文字が検出される。ステップ１４６で後に受
け取られた各文字が３つの同一文字と同一であると確認
されると、カウンタがステップ１４８で増分される。さ
らに文字は保持され、文字が符号化テーブル１６を使っ
て符号化されていないため、モデム１０から送出されな
いことを意味する。ステップ１４８の後で、モデム１０
はステップ１４４で別の文字を待つ。
【０１１８】結局は、ステップ１４６で、最初の３つの
同一文字に同一ではない文字が検出される。同一ではな
い文字がステップ１４６で検出されると、「ＮＯ」ブラ
ンチに従ってステップ１５に進み、そこで前述の符号化
テーブル１６を使った符号化のために、カウント・トー
タルが図４のプログラムに渡される。さらに、カウンタ
はゼロにリセットされる。それから、ＲＬＥプログラム
１３０はステップ１３４に進み、同一ではなかった文字
は、同一文字を見つけるために使用される新しい文字と
して格納される。カウンタはステップ１３４で１に増分
され、ステップ１４４で検出され、ステップ１４６で同
一ではないと判断された文字は、符号化テーブル１６
（図２）による符号化のために渡される。
同一文字に同一ではない文字が検出される。同一ではな
い文字がステップ１４６で検出されると、「ＮＯ」ブラ
ンチに従ってステップ１５に進み、そこで前述の符号化
テーブル１６を使った符号化のために、カウント・トー
タルが図４のプログラムに渡される。さらに、カウンタ
はゼロにリセットされる。それから、ＲＬＥプログラム
１３０はステップ１３４に進み、同一ではなかった文字
は、同一文字を見つけるために使用される新しい文字と
して格納される。カウンタはステップ１３４で１に増分
され、ステップ１４４で検出され、ステップ１４６で同
一ではないと判断された文字は、符号化テーブル１６
（図２）による符号化のために渡される。
【０１１９】３つの同一文字から成る連続グループのそ
れぞれは、符号化テーブル１６により符号化するために
渡される。しかしながら、最初の３つの同一文字の後、
続く同一文字は、符号化テーブル１６を使って分析され
ない。カウンタは、それぞれの同一文字が検出される毎
にカウントアップする。このようにして、連続同一文字
の総数がカウントされる。一連の連続同一文字と同一で
はない文字が受け取られると、受け取られた同一文字の
総数が、符号化テーブル１６を使った符号化のためにマ
イクロプロセッサ３５に伝送される。このようにして、
１つのコードが、同一文字の長い連なりに対して形成さ
れる。具体的には、３つの同一文字の後には、常に、同
一文字の総数を表す数が続く。したがって、コードは、
同一文字が繰り返された回数を表す数が後に続く３つの
同一文字である。
れぞれは、符号化テーブル１６により符号化するために
渡される。しかしながら、最初の３つの同一文字の後、
続く同一文字は、符号化テーブル１６を使って分析され
ない。カウンタは、それぞれの同一文字が検出される毎
にカウントアップする。このようにして、連続同一文字
の総数がカウントされる。一連の連続同一文字と同一で
はない文字が受け取られると、受け取られた同一文字の
総数が、符号化テーブル１６を使った符号化のためにマ
イクロプロセッサ３５に伝送される。このようにして、
１つのコードが、同一文字の長い連なりに対して形成さ
れる。具体的には、３つの同一文字の後には、常に、同
一文字の総数を表す数が続く。したがって、コードは、
同一文字が繰り返された回数を表す数が後に続く３つの
同一文字である。
【０１２０】復号化テーブル１８（図２）に続くデコー
ダ（不図示）は、３つの同一文字を受け取ると、次に受
け取られる文字がストリング内の同一文字の総数を表す
数であることを認識している。同一文字の他の数を利用
して、同一文字のストリングに対するコードを特定する
こともできる。例えば、４つの同一文字が同一文字数の
カウントの前に来るようにすることもできる。設計者
は、コードが置換される前に検出されなければならない
連続同一文字の最小数を設定することができる。これに
より、おそらくデータ拡張という結果になるたった２つ
の同一の連続する文字をコードで置換することをなくせ
る。モデム１０、１５は、ラン・レングス符号化が使用
される機能であるかどうかを、当業者によく知られた方
法で最初のハンドシェイク中に設定する。
ダ（不図示）は、３つの同一文字を受け取ると、次に受
け取られる文字がストリング内の同一文字の総数を表す
数であることを認識している。同一文字の他の数を利用
して、同一文字のストリングに対するコードを特定する
こともできる。例えば、４つの同一文字が同一文字数の
カウントの前に来るようにすることもできる。設計者
は、コードが置換される前に検出されなければならない
連続同一文字の最小数を設定することができる。これに
より、おそらくデータ拡張という結果になるたった２つ
の同一の連続する文字をコードで置換することをなくせ
る。モデム１０、１５は、ラン・レングス符号化が使用
される機能であるかどうかを、当業者によく知られた方
法で最初のハンドシェイク中に設定する。
【０１２１】当業者は、実施の形態の前述される発明の
構成要素の多くを、ソフトウェアまたはハードウェアの
いずれにもすることができることが分かるであろう。例
えば、カウンタおよび加算器は、当業者には容易に、ソ
フトウェアまたはハードウェアで実現できる。
構成要素の多くを、ソフトウェアまたはハードウェアの
いずれにもすることができることが分かるであろう。例
えば、カウンタおよび加算器は、当業者には容易に、ソ
フトウェアまたはハードウェアで実現できる。
【図１】ストリング・ベースのデータ符号化テーブルの
ツリーの図である。
ツリーの図である。
【図２】本発明の望ましいデータ圧縮方法および装置を
利用するデータ通信アプリケーションを示す概要図であ
る。
利用するデータ通信アプリケーションを示す概要図であ
る。
【図３】モデムにおいてデータ圧縮の望ましい方法を実
現するためのマイクロプロセッサ・ベースの回路のブロ
ック概要図である。
現するためのマイクロプロセッサ・ベースの回路のブロ
ック概要図である。
【図４】符号化テーブルを利用してデータを符号化し、
データ中の文字間の相関関係を判断し、それに応えて符
号化テーブルを調整するために講じられるステップのフ
ローチャートである。
データ中の文字間の相関関係を判断し、それに応えて符
号化テーブルを調整するために講じられるステップのフ
ローチャートである。
【図５】データ・ストリーム内のデータ間の相関関係を
判断し、符号化テーブルのサイズを調整するために講じ
られるステップの詳細なフローチャートである。
判断し、符号化テーブルのサイズを調整するために講じ
られるステップの詳細なフローチャートである。
【図６】データ・ストリーム内の文字間の相関関係を計
算するために、図３のマイクロプロセッサ・ベースの回
路により使用されるレジスタおよびテーブルのブロック
図である。
算するために、図３のマイクロプロセッサ・ベースの回
路により使用されるレジスタおよびテーブルのブロック
図である。
【図７】符号化テーブルのサイズの変更の頻度を制限す
るために講じられるステップのフローチャートである。
るために講じられるステップのフローチャートである。
【図８】本発明のデータ圧縮の望ましい方法を実行する
ためのファジー論理技法の利用を示す図である。
ためのファジー論理技法の利用を示す図である。
【図９】本発明のデータ圧縮の望ましい方法を実行する
ためのファジー論理技法のメンバシップ関数を示す図で
ある。
ためのファジー論理技法のメンバシップ関数を示す図で
ある。
【図１０】符号化テーブルに渡す前にデータ・ストリー
ムが前処理されるラン・レングス符号化プログラムの動
作のフローチャートである。
ムが前処理されるラン・レングス符号化プログラムの動
作のフローチャートである。
４ ルート文字 ５ ストリング ６ ツリー ７ リーフ文字 ９ コンピュータ １０，１５ モデム １２ 電話回線 １６ 符号化テーブル １８ 復号化テーブル ２２ コンピュータインタフェースモデム回路部 ２４ 電話インタフェースモデム回路部 ２７，２８ 制御レジスタ ３１ プログラムメモリ ３０ マイクロコンピュータ ３５ ＲＡＭ
Claims (24)
- 【請求項１】 複数の文字ストリングを含む符号化テー
ブルを具備し、該符号化テーブル内の文字ストリング
が、文字ストリームの一部が前記符号化テーブル内の文
字ストリングの１つに一致するときに、データ文字スト
リームの部分と置換され得るコードワードに関連付けら
れているデータ文字ストリームを圧縮する装置におけ
る、データ圧縮効率およびデータ圧縮率を改善するため
に符号化テーブルを制御するデータ圧縮方法において、 データ文字・ストリーム内のデータ文字の相関関係を評
価するステップと、 データ文字間の前記評価された相関関係に応えて性能指
標を調整するステップと、 前記性能指標に応えて前記符号化テーブルに割り当てら
れるメモリ・スペースを変更するステップと、から構成
されることを特徴とするデータ圧縮方法。 - 【請求項２】 入力データ文字間の相関関係を判断する
ステップが、 装置に入力されるデータ文字ストリームの圧縮率を、装
置に入力される文字数を装置から出力されるデータ・バ
イト数で割ったものに等しくなるよう決定するステップ
と、 前記符号化テーブル内のツリーの内の少なくとも１つの
平均長さおよび幅の特徴の１つを評価するために使用さ
れる使用カウントを決定するステップと、から構成され
ることを特徴とする請求項１に記載のデータ圧縮方法。 - 【請求項３】 前記決定されたデータ文字間の相関関係
に応えて前記性能指標を調整するステップが、 前記圧縮率および前記使用カウントの決定された値に基
づいて前記性能指標を調整することを特徴とする請求項
２に記載のデータ圧縮方法。 - 【請求項４】 前記性能指標を調整するステップが、 前記圧縮率が事前に決定した第１の値より下で、前記使
用カウントが事前に決定した第２の値より大きい場合
に、事前に決定した第１の量で、前記性能指標を増加さ
せるステップと、 前記圧縮率が事前に決定した第３の値より大きく、前記
使用カウントが事前に決定した第４の値未満の場合に、
事前に決定した第２の量で、前記性能指標を減少させる
ステップと、から構成されることを特徴とする請求項３
に記載のデータ圧縮方法。 - 【請求項５】 前記使用カウントが、エントリ削除ルー
チン実行時に事前に決定した回数にわたって正規化され
た値として計算され、前記エントリ削除ルーチンがリー
フ文字を決定し、前記符号化テーブルから削除すること
を特徴とする請求項２に記載のデータ圧縮方法。 - 【請求項６】 前記使用カウントが、ツリー内の文字数
の平均を経時的に取ることにより計算されることを特徴
とする請求項５に記載のデータ圧縮方法。 - 【請求項７】 前記使用カウントが、データ文字ストリ
ーム内の文字と符号化テーブル内の文字の間で一致が見
つけ出される前に探索されるストリング中の文字数をカ
ウントし、経時的に平均をとり、文字数を２で乗算する
ことにより決定されることを特徴とする請求項２に記載
のデータ圧縮方法。 - 【請求項８】 使用カウントが、符号化テーブル内のリ
ーフ文字の総数をカウントすることにより決定されるこ
とを特徴とする請求項２に記載のデータ圧縮方法。 - 【請求項９】 前記メモリ・テーブルに割り当てられる
メモリ・スペースを変更するステップが、 前記性能指標が事前に決定した第１の値を上回ったとき
に前記符号化テーブルに割り当てられるメモリ・スペー
スを減らすステップと、 前記性能指数が事前に決定した第２の値を下回ったとき
に前記符号化テーブルに割り当てられるメモリ・スペー
スを増やすステップと、を含むことを特徴とする請求項
４に記載のデータ圧縮方法。 - 【請求項１０】 複数の文字ストリングを含む符号化テ
ーブルを具備し、該符号化テーブル内の文字ストリング
が、文字ストリームの一部が前記符号化テーブル内の文
字ストリングの１つに一致するときに、データ文字スト
リームの部分と置換され得るコードワードに関連付けら
れているデータ文字ストリームを圧縮する装置におけ
る、データ圧縮効率およびデータ圧縮率を改善するため
に符号化テーブルを制御するデータ圧縮方法において、 データ文字ストリーム内のデータ文字間の相関関係を判
断するステップと、 前記判断されたデータ文字間の相関関係に応えて性能指
標を調整するステップと、 前記性能指数が事前に決定した第１の値を上回ると、前
記符号化テーブルに割り当てられるメモリ・スペースを
縮小させるステップと、 前記性能指標が事前に決定した第２の値を下回ると、前
記符号化テーブルに割り当てられるメモリ・スペースを
拡大するステップと、から構成されることを特徴とする
データ圧縮方法。 - 【請求項１１】 複数の文字ストリングを含む符号化テ
ーブルを具備し、該符号化テーブル内の文字ストリング
が、文字ストリームの一部が前記符号化テーブル内の文
字ストリングの１つに一致するときに、データ文字スト
リームの部分と置換され得るコードワードに関連付けら
れているデータ文字ストリームを圧縮する装置におけ
る、データ圧縮効率およびデータ圧縮率を改善するため
に符号化テーブルを制御するデータ圧縮方法において、 データ文字ストリーム内のデータ文字間の相関関係を判
断するステップと、 前記判断されたデータ文字間の相関関係に応えて調整さ
れる性能指標を作成するステップと、 前記性能指標が事前に決定した第１の値を下回ると、前
記符号化テーブルに割り当てられるメモリ・スペースを
減らすステップと、 前記性能指標が事前に決定した第２の値を上回ると、前
記符号化テーブルに割り当てられるメモリ・スペースを
増やすステップと、から構成されることを特徴とするデ
ータ圧縮方法。 - 【請求項１２】 複数の文字ストリングを含む符号化テ
ーブルを具備し、該符号化テーブル内の文字ストリング
が、文字ストリームの一部が前記符号化テーブル内の文
字ストリングの１つに一致するときに、データ文字スト
リームの部分と置換され得るコードワードに関連付けら
れている、入力されるデータ文字ストリームを圧縮する
装置における、データ圧縮効率およびデータ圧縮率を改
善するために符号化テーブルを制御するデータ圧縮方法
において、 装置に入力されるデータ文字ストリームの圧縮率を、装
置に入力される文字の数を装置から出力されるデータ・
バイト数で割ったものに等しくなるよう決定するステッ
プと、 前記ストリングの平均的な長さおよび前記符号化テーブ
ル内のツリーの幅の１つを表す使用カウントを決定する
ステップと、 前記圧縮率および前記使用カウントを利用して性能指標
を計算するステップと、 前記性能指数が事前に決定した第１の値未満の時、前記
符号化テーブルに割り当てられたメモリ・スペースを減
らすステップと、 前記性能指標が事前に決定した第２の値より大きい時、
前記符号化テーブルに割り当てられるメモリ・スペース
を増やすステップと、から構成されることを特徴とする
データ圧縮方法。 - 【請求項１３】 前記使用カウントが、前記符号化テー
ブル内の各ルートに直接ぶら下がるストリングの数をカ
ウントすることにより概算されることを特徴とする請求
項１２に記載のデータ圧縮方法。 - 【請求項１４】 前記使用カウントが、データストリー
ム内のデータ文字と符号化テーブル内の文字の間で一致
が見つけ出される前に探索されるストリング内の文字の
数をカウントし、該カウントされた値を２で乗算するこ
とにより概算されることを特徴とする請求項１２に記載
のデータ圧縮方法。 - 【請求項１５】 前記使用カウントが、符号化テーブル
からエントリを削除するプロセスの間に、ルート・ノー
ドと削除対象のエントリの間のブランチ内の文字の数を
カウントし、該カウントされた値を２で乗算することに
より決定されることを特徴とする請求項１２に記載のデ
ータ圧縮方法。 - 【請求項１６】 使用カウントが、前記符号化テーブル
内のリーフ文字の総数の一部をカウントすることにより
計算されることを特徴とする請求項１２に記載のデータ
圧縮方法。 - 【請求項１７】 文字ストリングの１つがデータ文字ス
トリームの一部と一致するかどうかを判断するために、
符号化テーブル内の文字ストリングをデータ文字ストリ
ームと比較するステップと、 前記文字ストリングに関連付けられ、前記文字ストリン
グの１つが前記データ文字ストリームの一部と一致する
ときに、その１つが前記文字のストリームの一部と置換
され得るコードワードを提供するステップと、 データ文字ストリーム内のデータ文字間の相関関係を決
定するステップと、 データ文字ストリーム内のデータ文字間の前記相関関係
に基づいて、前記符号化テーブルに割り当てられるメモ
リ・スペースを調整するステップと、から構成されるこ
とを特徴とするデータ文字ストリームの圧縮方法。 - 【請求項１８】 複数の文字ストリングを含む符号化テ
ーブルを具備し、該符号化テーブル内の文字ストリング
が、文字ストリームの一部が前記符号化テーブル内の文
字ストリングの１つに一致するときに、データ文字スト
リームの部分と置換され得るコードワードに関連付けら
れている、入力されるデータ文字ストリームを圧縮する
装置において、 データストリーム内のデータ文字間の相関関係を判断す
るための手段と、 データ文字ストリーム内のデータ文字間の判断された相
関関係に応えて符号化テーブルのサイズを調整するため
の手段と、から構成されることを特徴とする装置。 - 【請求項１９】 装置に入力されるデータストリームの
圧縮率を計算する手段と、 符号化テーブルのツリーの幅および長さの１つを計算す
る手段と、 データ文字間の相関関係を表す性能指標を作成するため
に、前記圧縮率および前記ツリーの幅および長さの１つ
を結合する手段と、を更に具備することを特徴とする請
求項１８に記載の装置。 - 【請求項２０】 コンピュータ装置内で受け取られるデ
ータ文字ストリームを圧縮するための方法であって、 データ文字ストリーム内の第１文字を検出するステップ
と、 該検出された文字を符号化テーブル内のルート文字に一
致させるステップと、 前記第１文字に続くデータ文字ストリーム内の文字を検
出するステップと、 前記第１文字に続くデータ文字ストリーム内の前記文字
を、前記ルート文字にぶら下がるストリングと照合する
ステップと、 データ文字ストリーム内の前記文字と一致する前記スト
リングをコードワードで置換するステップと、 データ文字ストリーム内のデータ文字間の相関関係を判
断するステップと、 データ文字間の前記判断された相関関係に応えて調整さ
れる性能指標を作成するステップと、 前記性能指標が事前に決定した第１の値と等しいとき
に、前記符号化テーブルに割り当てられるメモリ・スペ
ースを減らすステップと、 前記性能指標が事前に決定した第２の値と等しいとき
に、前記符号化テーブルに割り当てられるメモリ・スペ
ースを増やすステップと、から構成されることを特徴と
する方法。 - 【請求項２１】 データがモデムを通して端末から通信
回線に通信され、前記モデムが前記データを符号化テー
ブルを利用して圧縮するシステムにおける、前記モデム
が符号化テーブルを利用して前記データを符号化する前
に、前記データを事前に符号化する方法において、 前記モデムから伝送されようとする一連の連続する同一
文字を検出するステップと、 圧縮のために符号化テーブルに渡される前記データ内の
前記一連の連続する同一文字の少なくとも一部の代わり
にコードを代用するステップと、から構成されることを
特徴とする方法。 - 【請求項２２】 一連の連続する同一文字を検出するス
テップが、 ３つの同一文字を識別するステップと、 該３つの同一文字の後に受け取られる、該３つの同一文
字に同一な文字の数をカウントするステップと、から構
成されることを特徴とする請求項２１に記載の方法。 - 【請求項２３】 コードが前記３つの同一文字、および
前記３つの同一文字を含む前記同一文字の総カウント数
に等しい数から構成されることを特徴とする請求項２２
に記載の方法。 - 【請求項２４】 前記モデムがＶ．４２ｂｉｓプロトコ
ルに従って符号化テーブルを利用してデータを圧縮する
ことを特徴とする請求項２１に記載の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/286,705 US5627533A (en) | 1994-08-05 | 1994-08-05 | Adjusting encoding table size and memory allocation for data compression in response to input data |
| US08/286,705 | 1994-08-05 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH08204579A true JPH08204579A (ja) | 1996-08-09 |
Family
ID=23099813
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7201047A Pending JPH08204579A (ja) | 1994-08-05 | 1995-08-07 | データ圧縮方法及び装置 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US5627533A (ja) |
| EP (1) | EP0702459B1 (ja) |
| JP (1) | JPH08204579A (ja) |
| CA (1) | CA2154978A1 (ja) |
| DE (1) | DE69528691T2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008299718A (ja) * | 2007-06-01 | 2008-12-11 | Hitachi Ltd | 記憶システム、記憶制御装置及びデータ圧縮方法 |
| JP2011199782A (ja) * | 2010-03-23 | 2011-10-06 | Fujitsu Toshiba Mobile Communications Ltd | 通信装置 |
| JP2020184672A (ja) * | 2019-05-07 | 2020-11-12 | 国立大学法人 筑波大学 | データの圧縮及び解凍方法、データ圧縮方法、データ圧縮装置、データ圧縮プログラム、データ解凍方法、データ解凍装置、データ解凍プログラム |
Families Citing this family (71)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6075665A (en) * | 1994-09-28 | 2000-06-13 | International Business Machines Corporation | Optimization of multimedia magnetic disk storage devices |
| US5878416A (en) * | 1996-06-14 | 1999-03-02 | Electronic Data Systems Corporation | Automated system and method for matching an item of business property to a recipient |
| US6125392A (en) * | 1996-10-11 | 2000-09-26 | Intel Corporation | Method and apparatus for high speed event log data compression within a non-volatile storage area |
| US6345121B1 (en) * | 1996-11-07 | 2002-02-05 | Matsushita Electric Industrial Co., Ltd. | Image encoding apparatus and an image decoding apparatus |
| US5892980A (en) * | 1997-02-28 | 1999-04-06 | Comsys Communication And Signal Processing Ltd. | System for dynamically changing the length of transmit and receive sample buffers utilizing previous responding to an interrupt in a communications system |
| US5835036A (en) * | 1997-05-12 | 1998-11-10 | Cisco Systems Co. | Method of encoding data for transmission |
| US7898442B1 (en) * | 1997-05-30 | 2011-03-01 | International Business Machines Corporation | On-line data compression analysis and regulation |
| US6415061B1 (en) * | 1997-06-13 | 2002-07-02 | Cisco Technology, Inc. | Method of updating dictionaries in a data transmission system using data compression |
| US7240087B1 (en) * | 1997-06-27 | 2007-07-03 | International Business Machines Corporation | Communication network having adjustable response timeouts and method therefore |
| US6704866B1 (en) | 1997-07-11 | 2004-03-09 | Cisco Technology, Inc. | Compression and encryption protocol for controlling data flow in a network |
| US6401188B1 (en) | 1998-02-27 | 2002-06-04 | Cisco Technology, Inc. | Method for selection on a pattern sequence |
| US6289130B1 (en) | 1999-02-02 | 2001-09-11 | 3Com Corporation | Method for real-time lossless data compression of computer data |
| US6341346B1 (en) | 1999-02-05 | 2002-01-22 | Cisco Technology, Inc. | Method for comparison between a pattern sequence and a variable length key |
| JP3990115B2 (ja) * | 2001-03-12 | 2007-10-10 | 株式会社東芝 | サーバ側プロキシ装置及びプログラム |
| DE10140993A1 (de) * | 2001-08-21 | 2003-03-20 | Deutsche Telekom Ag | Verfahren zur Kompression von Daten |
| US6961011B2 (en) * | 2001-08-27 | 2005-11-01 | Freescale Semiconductor, Inc. | Data compression system |
| GB0123410D0 (en) * | 2001-09-28 | 2001-11-21 | Memquest Ltd | Memory system for data storage and retrieval |
| US7533214B2 (en) | 2002-02-27 | 2009-05-12 | Microsoft Corporation | Open architecture flash driver |
| US7085879B2 (en) * | 2002-02-27 | 2006-08-01 | Microsoft Corporation | Dynamic data structures for tracking data stored in a flash memory device |
| US6901499B2 (en) | 2002-02-27 | 2005-05-31 | Microsoft Corp. | System and method for tracking data stored in a flash memory device |
| US7010662B2 (en) * | 2002-02-27 | 2006-03-07 | Microsoft Corporation | Dynamic data structures for tracking file system free space in a flash memory device |
| US6985853B2 (en) * | 2002-02-28 | 2006-01-10 | Broadcom Corporation | Compressed audio stream data decoder memory sharing techniques |
| US7580429B1 (en) * | 2002-09-05 | 2009-08-25 | U.S. Robotics | System and methods for improving data compression |
| US7778996B2 (en) * | 2002-09-25 | 2010-08-17 | Teradata Us, Inc. | Sampling statistics in a database system |
| US7093101B2 (en) | 2002-11-21 | 2006-08-15 | Microsoft Corporation | Dynamic data structures for tracking file system free space in a flash memory device |
| KR20060048060A (ko) * | 2004-05-28 | 2006-05-18 | 톰슨 라이센싱 | 텍스트 압축을 사용한 사용자 인터페이스 |
| US7079054B2 (en) * | 2004-06-04 | 2006-07-18 | Broadcom Corporation | V.42bis standalone hardware accelerator and architecture of construction |
| US11416903B2 (en) * | 2005-05-16 | 2022-08-16 | Price Setter Llc | Transaction arbiter system and method |
| JP4556766B2 (ja) * | 2005-05-23 | 2010-10-06 | ソニー株式会社 | 文字列検索回路及び文字列検索方法 |
| US8392684B2 (en) | 2005-08-12 | 2013-03-05 | Silver Peak Systems, Inc. | Data encryption in a network memory architecture for providing data based on local accessibility |
| US8171238B1 (en) | 2007-07-05 | 2012-05-01 | Silver Peak Systems, Inc. | Identification of data stored in memory |
| US8095774B1 (en) | 2007-07-05 | 2012-01-10 | Silver Peak Systems, Inc. | Pre-fetching data into a memory |
| US8929402B1 (en) | 2005-09-29 | 2015-01-06 | Silver Peak Systems, Inc. | Systems and methods for compressing packet data by predicting subsequent data |
| US8489562B1 (en) | 2007-11-30 | 2013-07-16 | Silver Peak Systems, Inc. | Deferred data storage |
| US8811431B2 (en) | 2008-11-20 | 2014-08-19 | Silver Peak Systems, Inc. | Systems and methods for compressing packet data |
| US8483492B2 (en) * | 2005-10-25 | 2013-07-09 | William Marsh Rice University | Method and apparatus for signal detection, classification and estimation from compressive measurements |
| US8885632B2 (en) | 2006-08-02 | 2014-11-11 | Silver Peak Systems, Inc. | Communications scheduler |
| US8755381B2 (en) | 2006-08-02 | 2014-06-17 | Silver Peak Systems, Inc. | Data matching using flow based packet data storage |
| US8307115B1 (en) | 2007-11-30 | 2012-11-06 | Silver Peak Systems, Inc. | Network memory mirroring |
| US8321386B1 (en) * | 2008-04-14 | 2012-11-27 | Netapp, Inc. | System and method for estimating a compressibility of data in a storage device |
| US8743683B1 (en) | 2008-07-03 | 2014-06-03 | Silver Peak Systems, Inc. | Quality of service using multiple flows |
| US10164861B2 (en) | 2015-12-28 | 2018-12-25 | Silver Peak Systems, Inc. | Dynamic monitoring and visualization for network health characteristics |
| US10805840B2 (en) | 2008-07-03 | 2020-10-13 | Silver Peak Systems, Inc. | Data transmission via a virtual wide area network overlay |
| US9717021B2 (en) | 2008-07-03 | 2017-07-25 | Silver Peak Systems, Inc. | Virtual network overlay |
| US8140488B2 (en) * | 2009-02-26 | 2012-03-20 | Red Hat, Inc. | Reducing memory required for prediction by partial matching models |
| IL197882A (en) * | 2009-03-24 | 2015-03-31 | Oleg Litvak | A method and device for compression of communication signals |
| CN101931414B (zh) | 2009-06-19 | 2013-04-24 | 华为技术有限公司 | 脉冲编码方法及装置、脉冲解码方法及装置 |
| EP2378766A1 (en) * | 2010-04-16 | 2011-10-19 | Liberty Global Europe Holding B.V. | Electronic Program Guide compression method and system |
| US10162553B2 (en) | 2010-11-24 | 2018-12-25 | Western Digital Technologies, Inc. | Methods and systems for object level de-duplication for solid state devices |
| US9130991B2 (en) | 2011-10-14 | 2015-09-08 | Silver Peak Systems, Inc. | Processing data packets in performance enhancing proxy (PEP) environment |
| US9626224B2 (en) | 2011-11-03 | 2017-04-18 | Silver Peak Systems, Inc. | Optimizing available computing resources within a virtual environment |
| CN103853855A (zh) * | 2012-11-29 | 2014-06-11 | 北京华大九天软件有限公司 | 一种电路仿真模拟同步波形压缩格式 |
| US8812744B1 (en) | 2013-03-14 | 2014-08-19 | Microsoft Corporation | Assigning priorities to data for hybrid drives |
| US9626126B2 (en) | 2013-04-24 | 2017-04-18 | Microsoft Technology Licensing, Llc | Power saving mode hybrid drive access management |
| US9946495B2 (en) | 2013-04-25 | 2018-04-17 | Microsoft Technology Licensing, Llc | Dirty data management for hybrid drives |
| US20150121111A1 (en) * | 2013-10-24 | 2015-04-30 | Qualcomm Incorporated | System and method for providing multi-user power saving codebook optmization |
| US9864536B2 (en) | 2013-10-24 | 2018-01-09 | Qualcomm Incorporated | System and method for conserving power consumption in a memory system |
| US9948496B1 (en) | 2014-07-30 | 2018-04-17 | Silver Peak Systems, Inc. | Determining a transit appliance for data traffic to a software service |
| US9875344B1 (en) | 2014-09-05 | 2018-01-23 | Silver Peak Systems, Inc. | Dynamic monitoring and authorization of an optimization device |
| KR20170045928A (ko) * | 2015-10-20 | 2017-04-28 | 삼성에스디에스 주식회사 | 인메모리 데이터베이스를 이용한 데이터 관리 방법 및 그 장치 |
| US10594491B2 (en) * | 2015-12-24 | 2020-03-17 | Intel Corporation | Cryptographic system memory management |
| US10432484B2 (en) | 2016-06-13 | 2019-10-01 | Silver Peak Systems, Inc. | Aggregating select network traffic statistics |
| US9967056B1 (en) | 2016-08-19 | 2018-05-08 | Silver Peak Systems, Inc. | Forward packet recovery with constrained overhead |
| US10257082B2 (en) | 2017-02-06 | 2019-04-09 | Silver Peak Systems, Inc. | Multi-level learning for classifying traffic flows |
| US11044202B2 (en) | 2017-02-06 | 2021-06-22 | Silver Peak Systems, Inc. | Multi-level learning for predicting and classifying traffic flows from first packet data |
| US10892978B2 (en) | 2017-02-06 | 2021-01-12 | Silver Peak Systems, Inc. | Multi-level learning for classifying traffic flows from first packet data |
| US10771394B2 (en) | 2017-02-06 | 2020-09-08 | Silver Peak Systems, Inc. | Multi-level learning for classifying traffic flows on a first packet from DNS data |
| US11212210B2 (en) | 2017-09-21 | 2021-12-28 | Silver Peak Systems, Inc. | Selective route exporting using source type |
| US10419022B2 (en) | 2017-11-30 | 2019-09-17 | International Business Machines Corporation | Run-length base-delta encoding for high-speed compression |
| EP3624019A4 (en) * | 2017-12-30 | 2021-03-24 | Cambricon Technologies Corporation Limited | CHIP DEVICE WITH INTEGRATED CIRCUIT AND ASSOCIATED PRODUCT |
| US10637721B2 (en) | 2018-03-12 | 2020-04-28 | Silver Peak Systems, Inc. | Detecting path break conditions while minimizing network overhead |
Family Cites Families (14)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4366551A (en) * | 1977-06-24 | 1982-12-28 | Holtz Klaus E | Associative memory search system |
| US4464650A (en) * | 1981-08-10 | 1984-08-07 | Sperry Corporation | Apparatus and method for compressing data signals and restoring the compressed data signals |
| US4814746A (en) * | 1983-06-01 | 1989-03-21 | International Business Machines Corporation | Data compression method |
| US4558302A (en) * | 1983-06-20 | 1985-12-10 | Sperry Corporation | High speed data compression and decompression apparatus and method |
| US4612532A (en) * | 1984-06-19 | 1986-09-16 | Telebyte Corportion | Data compression apparatus and method |
| US5434568A (en) * | 1985-01-10 | 1995-07-18 | Moll; Edward W. | Data compression by removing repetition and unnecessary information |
| US4626829A (en) * | 1985-08-19 | 1986-12-02 | Intelligent Storage Inc. | Data compression using run length encoding and statistical encoding |
| US4841299A (en) * | 1987-08-31 | 1989-06-20 | Digital Recording Research Limited Partnership | Method and apparatus for digital encoding and decoding |
| US4881075A (en) * | 1987-10-15 | 1989-11-14 | Digital Equipment Corporation | Method and apparatus for adaptive data compression |
| US4847619A (en) * | 1987-10-19 | 1989-07-11 | Hewlett-Packard Company | Performance-based reset of data compression dictionary |
| US4870415A (en) * | 1987-10-19 | 1989-09-26 | Hewlett-Packard Company | Data compression system with expansion protection |
| US4929946A (en) * | 1989-02-09 | 1990-05-29 | Storage Technology Corporation | Adaptive data compression apparatus including run length encoding for a tape drive system |
| US5467087A (en) * | 1992-12-18 | 1995-11-14 | Apple Computer, Inc. | High speed lossless data compression system |
| US5455576A (en) * | 1992-12-23 | 1995-10-03 | Hewlett Packard Corporation | Apparatus and methods for Lempel Ziv data compression with improved management of multiple dictionaries in content addressable memory |
-
1994
- 1994-08-05 US US08/286,705 patent/US5627533A/en not_active Expired - Lifetime
-
1995
- 1995-07-28 CA CA002154978A patent/CA2154978A1/en not_active Abandoned
- 1995-08-01 EP EP95112096A patent/EP0702459B1/en not_active Expired - Lifetime
- 1995-08-01 DE DE69528691T patent/DE69528691T2/de not_active Expired - Lifetime
- 1995-08-07 JP JP7201047A patent/JPH08204579A/ja active Pending
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2008299718A (ja) * | 2007-06-01 | 2008-12-11 | Hitachi Ltd | 記憶システム、記憶制御装置及びデータ圧縮方法 |
| US9342521B2 (en) | 2007-06-01 | 2016-05-17 | Hitachi, Ltd. | Storage system, storage controller and data compression method |
| JP2011199782A (ja) * | 2010-03-23 | 2011-10-06 | Fujitsu Toshiba Mobile Communications Ltd | 通信装置 |
| JP2020184672A (ja) * | 2019-05-07 | 2020-11-12 | 国立大学法人 筑波大学 | データの圧縮及び解凍方法、データ圧縮方法、データ圧縮装置、データ圧縮プログラム、データ解凍方法、データ解凍装置、データ解凍プログラム |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0702459A2 (en) | 1996-03-20 |
| EP0702459B1 (en) | 2002-10-30 |
| CA2154978A1 (en) | 1996-02-06 |
| DE69528691D1 (de) | 2002-12-05 |
| EP0702459A3 (en) | 1999-04-07 |
| US5627533A (en) | 1997-05-06 |
| DE69528691T2 (de) | 2003-07-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH08204579A (ja) | データ圧縮方法及び装置 | |
| US5374916A (en) | Automatic electronic data type identification process | |
| US5467087A (en) | High speed lossless data compression system | |
| JP3017380B2 (ja) | データ圧縮方法及び装置並びにデータ伸長方法及び装置 | |
| US5003307A (en) | Data compression apparatus with shift register search means | |
| US11044495B1 (en) | Systems and methods for variable length codeword based data encoding and decoding using dynamic memory allocation | |
| US5949355A (en) | Method and apparatus for adaptive data compression | |
| US5463390A (en) | Data compression apparatus and method | |
| US5414650A (en) | Parsing information onto packets using context-insensitive parsing rules based on packet characteristics | |
| US5521597A (en) | Data compression for network transport | |
| EP0283735A2 (en) | Adaptive data compression method and apparatus | |
| US20030030575A1 (en) | Lossless data compression | |
| EP0375221A1 (en) | Data compression | |
| JP2979106B2 (ja) | データ圧縮 | |
| US5650783A (en) | Data coding/decoding device and method | |
| US5594435A (en) | Permutation-based data compression | |
| US6515598B2 (en) | System and method for compressing and decompressing data in real time | |
| CN108023597B (zh) | 一种数控系统可靠性数据压缩方法 | |
| WO2001063772A1 (en) | Method and apparatus for optimized lossless compression using a plurality of coders | |
| EP0885429A1 (en) | System and method for the fractal encoding of datastreams | |
| JPH10271013A (ja) | データの圧縮方法および画像データの圧縮方法と圧縮装置 | |
| US6415061B1 (en) | Method of updating dictionaries in a data transmission system using data compression | |
| US20050193022A1 (en) | Method and apparatus for lossless compression and decompression of data | |
| EP0721699A1 (en) | Method and apparatus for a unique and efficient use of a data structure for compressing data | |
| US5838691A (en) | Codebook-based lossy data compression encoding system |