JPH04502377A - データ圧縮 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 データ圧縮 本発明は、例えばハードディスクのようなマス記憶装置中の記憶に対するデータ によって要求されるスペースを減少させるか或いはデータを転送するのに必要な 帯域を減少させるために使用可能なデータ圧縮システムに関する。本発明は、特 に動的に編集された辞書を使用するデータ圧縮システムに関する。そのようなシ ステムにおいて、入力データ流は辞書に記憶されたストリングと比較される。デ ータ流からの文字が辞書中のワードと整合したとき、そのワードに対するコード は辞書から読取られ、オリジナルの文字の定まった位置に伝送される。入力デー タ流が予め遭遇していない、すなわち辞書に記憶されていない文字シーケンスを 有することを発見されると同時に、辞書は新しく入力し、コードを新しく遭遇し た文字シーケンスに割当てることによって更新される。この過程は圧縮システム の送信側および受信側で重複される。

辞書入力はポインタを新しく遭遇したストリングの付加的な文字と共に予め遭遇 したストリングに記憶することによって普通行われる。

本発明の第１の概念によると、動的に編集された辞書を含むデータ圧縮システム において、辞書はワードおよび部分ワードを含むストリングを記憶することによ って更新される。

部分ワードは入力データ流中のワードの直後に続くストリングからの複数の文字 を含む。

部分ワードはただ２つの文字で構成されることが好ましい。

データ圧縮システムはメイン（ＭＢｎｅ　）単一パスデータ圧縮演算法を使用す るデータを圧縮することが好ましい。既知のシステムにおいて、辞書入力は先行 する整合したワードとの最長ストリングの整合を捜す方法によって延期した単一 不整合文字を結合するか、或いは対の整合したワードを含むように入力すること によって行われる。前者の１例は２ｉｖ　Ｌａｍｐｔ１演算法であり、後者の例 は通常のＭｇ７ｎｅデータ圧縮演算法である。本発明の好ましい例はＭｇ７ｎｅ データ圧縮演算法を使用するが、入力は対のワード全体ではなく１つのワードお よび後続するワードの１部分を含むように、辞書を更新する方法を変更する。本 発明者はこれは演算法の動作の効率において十分な利点を提供し、これらの利点 は特に第２の対のワードからのただ２つの文字が辞書入力を形成する場合に注目 されることを発見した。

本発明の第２の概念によると、Ｍａｙｎｓ演算法を使用するデータ圧縮システム において、各ストリングの整合過程後の辞書の更新中に、対応する辞書入力に対 する指標は転送される。

本発明の１実施例が詳細に説明され、以下の技術説明の従来技術と対照される。

ＢＴＹＺの技術説明−変更したＭａｙ＋ｅ圧縮演算法１、序論 Ｍｓ７ｎ＊演算法は２ｉｙ　Ｌｅｍｐｔｌ演算法より数年前につくられ、１９８ ０年代までは２ｉｖ　Ｌｅｍｐｅｌ演算法の１部に組込まれなかった多くの特徴 を有する。ＭＢｎｅ演算法は初め２重バス適応圧縮方式として提案されたが、単 一バス動作に適応されることができる。この論文は演算法の変更した方法を述べ ているが、詳細は英国特許共同出願８８１５９７８号明細書に開示されている。

メモリに関するリソース要求および処理時間は変更した２ｉｖＬｃｍｐｔｌ演算 法によって達成されたものと類似している。

２、データ構造およびエンコード ｚｉｙ　Ｌｅｍｐｅｌ演算法に関して、Ｍｇｙｎ！演算法はコードワードによっ て入力記号のシーケンスを示す。これは既知のストリングの辞書を使用すること によって達成される。辞書の各入力は対応する指標またはコードワードを有する 。エンコーダは入力記号の最長ストリングと辞書入力を整合し、辞書入力の指標 を送信する。デコーダは指標を受信し、その入力を辞書で調べ、ストリングを回 復する。

この方法の最も複雑な部分はエンコーダによって実行されたストリング整合また は解読であり、これは潜在的に大きい辞書によって捜すことを必要とする。もし 辞書入力が以下示されるように組立てられるならば、この方法はかなり簡単にさ れる。図面に示された構造は“ｔｏで始まる一連のストリングをツリー状で示さ れている。辞書の初期入力は元の値“ｔｏと等しい指標を有する。

入ってくるストリングｔｈｅ　ｑｕｉｃｋ、、“と整合するために、初めの文字 “ｔ”が読取られ、対応する入力は直ぐ近くに位置される（オリジナル値“ｔ” と等しい）。次の文字“ｈｏが読取られ、捜索は第１の入力に従属するものの中 で開始される（この例では３だけ）。文字が整合されるとき、次の入力文字が読 取られ、その過程が繰返される。このようにして、ストリングｔｈｅ”は容易に 位置され、エンコーダは次の文字“を位置するように試みるとき、ストリング″ ｔｈｅ’″が辞書の中には存在しないことがすぐに明らかである。入力“ｔｈｅ “の指標値は伝送され、ストリング整合過程は文字“で再開される。これは分類 および捜索演算法（以下説明される第４節参照）の一般的な分野で十分に理解さ れる原理に基づく。

辞書は簡単な方法で動的に更新されることができる。上述の状態が生じるとき、 すなわちストリングＳが整合されたがしかしストリングＳ＋Ｃは整合されないと きに、付加的な文字Ｃは辞書に追加され、入力Ｓに結合される。この手段によっ て、上記辞書はストリングｔｈｅ“を含み、ストリングが遭遇された次のときに 改良された圧縮を達成する。

Ｍａ７ｎ＊演算法の２つのパス形式は以下のように動作する：（ａ）辞書構成 接頭辞ストリングと呼ばれる辞書入力と整合する入力記号の最長ストリングを見 付ける。この過程を繰返し、この第２の整合されたストリングを接尾辞ストリン グと呼ぶ。接尾辞ストリングを接頭辞ストリングに付加し、それを辞書に追加す る。この過程は入力データ流全体が読取られるまで繰返される。各辞書入力は関 係する周波数カウントを有し、それは使用するごとにインクレメントされる。エ ンコーダは記憶スペースを使い果たしたとき、最小の頻度で使用された辞書人力 を発見し、新しいストリングに再び使用する。

（ｂ）エンコード 辞書入力が整合する入力記号の最長ストリングを発見する方法は繰返される。し かし、整合が発見されるとき、辞書入力の指標は伝送される。２つのバス方式に おいて、辞書はエンコード中変更されない。

辞書更新過程中ＭＢｎｅ演算法単−バスを実行させるために、各ストリング整合 過程の後、対応する辞書入力の指標は伝送される。

小さい辞書による経験上、完全なストリングを付加することは辞書がデータ特性 に十分に適していない長いストリングを満たすようにさせることが知られている 。大きい辞書（すなわち４０９６＋入力）では、これはその場合に適切ではない 。

第２のストリングの最初の２つの文字を第１のストリングに付加することによっ て、性能はかなり改良される。接尾辞ストリングは長さにおいて２つ以上の文字 であるならば、辞書更新過程は２つの文字を付加するように変更されるか、或い は接尾辞ストリングは長さ１からなるならば、その過程は１つの文字を付加する ように変更される。

入力露文字のオリジナル値 実行（ 入力流から次の文字を読取り、延長したストリングが発見されるとき、延長した ストリング用のストリング捜索辞書に付加し、 延長したストリングが発見されるならば、入力＝整合した辞書入力の指標） 一方、（発見） ／入力で戻る一最後の整合入力、文字−最後の文字の読／第１のストリングを整 合／ 整合（入力、入力流、文字） 出力入力 ／第２のストリングを整合／ 整合（入力、入力流、文字） 出力入力 第２の入力の初めの２つの文字を第１の入力に付加し、辞書に追加する 一方（エンコードされるデータ） 例えば、辞書がストリングｍＯ”と“ｕｓ”を含むとすれば、ワード“ｍｏｕｓ ｅ”はＭＢｎ！演算法演算−パス方法を使用してエンコードされる。

（ｉ）　“ｍ”と、延長したストリングｍＯ”を与える後続文字“Ｏ”を読取る 。

（ｉｉ）　“ｍｏ”について脱座の辞書で捜索し、ストリング“ｍＯ”の指標を 入力させる。

（ｉｉｉ　）次の文字“Ｕ”を読取り、延長したストリング“ｍｏｕ″を与える 。

（ｉｖ）　“ｍｏｕ”について辞書で捜索するが、存在しない。

（Ｖ）ストリングｍｏ”の指標を入力する。

（ｖｉ）ストリングを不整合の文字″Ｕ′″にリセットする。

（ｖｉｉ　）次の文字“Ｓ”を読取り、ストリングｕｓ”を与え−る。

（ｖｉｉｉ）辞書で捜索し、対応する辞書入力の数を入力に割当てる。

（ｉｘ）次の文字“ｅ”を読取り、延長したストリング“ｕｓｅ”を与える。

（Ｘ）　“ｕｓｅ”について辞書で捜索するが、存在しない。

（ｘｉ）ストリングｕｓ”の指標を入力する。

Ｑｉｉ　）’ｍｏ”十”ｕｓ”を辞書に追加する。

（ｒｉｉｉ）不整合の“ｅ″で再開。

（ｘｉｙ　）次の文字を読取り０．。

演算法の幾つかの他の概念は適切な実時間構成が達成される前に限定または変更 を必要とする。これは辞書を構成する手段と、関係する演算法と、記憶回復に関 する。上記で限定された辞書構造の型式を構成する多くの手段で知られている。

Ｋ＋ｕｔｈ　（１９６８）はこれらの幾つかについて述べているが、その他はご く最近に述べられている。２つの特定の方式は簡潔に述べられる： （ｉ）ツリー構造 変更された’ｌ：ｖ　ＬｅｒｎｐｅＩ演算法の上述の適用はこれに適切なツリー 構造［３］について述べる。これはモデムの適用に対して十分に速い方法を提供 するために示されている。方式はストリング中の所定の位置に対する別の文字を 示すために結合されたリストを使用し、１つの辞書入力当り約７バイトを捜索を 速めるためのノ＼ツシングまたは散乱記憶の使用は［４コ〜［６コにより従来か ら知られている。数学機能は位置されるべきアイテム、ここではアドレスを発生 させるストリングに適用されることが原理である。理想的に、捜索は単にハツシ ング機能を与え適切な入力を調べることから成立つ場合に、記憶されたアイテム とハツシュされたアドレスとの１対ｌの対応が存在する。実際、同じアドレスは 幾つかの異なるデータ組すなわち不一致によって発生されることができる。故に 捜索は所望のアイテムを位置付けることを含む。

変更されたＭＢｎｅ演算法（および実際変更された２ｉｙ　ＬｅＩＩｐｃ１演算 法）におけるキーファクターは特定の捜索技術を使用することを必要しないこと である。新しい辞書入力を割当てる方法が十分に定義される限り、ツリー技術を 使用するエンコーダはハツシングを使用するデコーダによって相互作用できる。

メモリ要求は両技術に対して類似する。

記憶回復は以下詳細に第４節に記載され、Ｍａｙｎｚ氏により説明された記憶回 復より効率的な置換が記載されている。

３、デコード デコーダはエンコーダからコードワードを受信し、エンコーダと等価のツリー構 造を使用することによってコードワードで示された文字のストリングを回復し、 それを出力する。

それはそれぞれ接頭辞および接尾辞としてデコードされたストリングを処理し、 エンコーダと同様にその辞書を更新する。

末尾の参考文献［７］に記載されたＫｗ問題はＭａｙｎｅ演算法に生じないこと が注目される。この問題はＷｅｌｃｈの２ｉｖＬｅｍｐｅｌ構成と、Ｍｉｌｌｕ とＷｅｇｒｎａｎにおいて生じる。なぜなら、エンコーダはデコーダの１ステツ プ前でその辞書を更新することが可能であるからである。

コードワードを受信する。

辞書で入力を調べる。

ストリングを出力する。

接頭辞としてストリングを蓄える。

コードワードを受信する。

辞書で入力を調べる。

ストリングを出力する。

ストリングの最初の２つの文字を接頭辞に付加し、辞書に追加する。） 一方（エンコードされるデータ） ４、辞書保守 ４．　ａ　辞書更新 エンコーダの辞書は各接尾辞ストリングがエンコードされた後に更新され、デコ ーダは類似する機能を実行する。新しい辞書入力は、辞書が満たされるまで連続 して割当てられ、その後に以下説明される第４．ｂ節に記載されるように回復さ れる。

辞書は初めの文字の組と小さい数の制御専用コードワードを含む。辞書スペース の残留物はストリング記憶に割当てられる。割当てられた第１の入力は制御コー ドワードに後続する第１の辞書入力である。

各辞書入力はポインタおよび文字からなり（例えば参考文献［３］　）　、第２ 節で示された一般的な形式で観入力に結合される。新しい入力を生成することは 文字および適切な結合ポインタを入力に割当てられたメモリ位置に書込むことか らなる（例えば参考文献［６］）。

４、ｂ　記憶回復 辞書が満たされるときに、エンコーダがデータ流中の変化に連続的に適応するこ とができるように記憶を回復すること・は必要である。処理オーバヘッドをほと んど必要せず、付加的な記憶装置も必要としないので、参考文献［６］に記載さ れた原理は変更されたＭＢｎｚ演算法に適用されている。

辞書が満たされているとき、入力は簡単な連続的な順序で辞書のストリング記憶 区域を走査することによって回復される。もし入力は１ｅａｆすなわちストリン グの最後の文字であるならば、それは消去される。消去されるべき次の入力の捜 索は最後の文字が回復された後に入力で始める。記憶回復過程は新しい入力が生 じる前ではなくその後に実行され、これは整合入力の不注意な消去を阻止する。

５、全データが圧縮可能ではなく、圧縮可能なファイルでさえも短時間の圧縮で きないデータを含むことができる。したがって、データ圧縮機能は効率の損失を 自動的に検出可能で、圧縮されない或いは透過の動作に復帰可能であることが望 ましい。

透過モードおよび圧縮モードの２つのモードの動作がある。

エンコーダはＤＴＥインターフェイスから文字を受入れ、圧縮されない形式で通 過させる。しかし、通常のエンコード過程は保持され、上述のようにエンコーダ 辞書は更新される。

したがって、エンコーダ辞書は透過モードでさえもデータ特性を変化するように 構成されることが可能である。

（ｂ）デコーダ デコーダはエンコーダから圧縮されない文字を受入れ、ＤＴＥインターフェイス にその文字を通過させ、等価なストリング整合機能を実行する。したがって、デ コーダは実際エンコーダ機能の複写を含む。

（ｃ）透過モードからの転移 エンコーダおよびデコーダは処理された文字の数および圧縮が続けられるときの エンコードされるビット数のカウントを維持する。エンコーダおよびデコーダの 両方はストリング整合の同様の動作を実行するので、これは簡単な処理である。

各辞書が更新した後に、文字カウントが試験される。カウントはしきい値ａｘｆ 　ｄｅｌａｙを超過するとき、圧縮比が計算される。圧縮比はｌよりも大きいな らば、圧縮はオンに切換えられ、エンコーダおよびデコーダは圧縮モードに入力 する。

（ｉｉ）圧縮モード （ａ）エンコーダ エンコーダはＤＴＥインターフェイスから読取られた文字デコーダは受信された コードワードから文字ストリングを回復するために第３節に記載されたデコード 方法を使用する。

（ｃ）透過モードへの転移 エンコーダは恐らく上述の試験を利用してその効率またはデータ流の圧縮性を任 意に試験する。エンコード処理の効率が損なわれることが明らかであるとき、エ ンコーダは圧縮モードへの転移を示すために明白コードワードをデコーダに伝送 する。第１節で説明された試験が、システムを圧縮モードに復帰すべきであるこ とを示すまで、示されたデータは透過形式で転送される。エンコーダおよびデコ ーダは透過モードに切換えた後に接頭辞モードに復帰する。

６、ＤＴＥタイムアウト、フレームの終了、またはメツセージの終了の動作 フラッシュ動作はエンコーダに残っている任意のデータが転送されることを保証 するために行われる。これは１バイトの部分を記憶できるエンコードおよびデコ ードプロセスに対するビット方向付は素子があるとき必要である。したがって、 転送されるべき次のデータはバイト境界で開始する。圧縮モード内のみに存在す ることが可能であるこの動作が使用されるとき、明白コードワードはデコーダが ビット方向付はプロセスを編成できるように伝送される。これは以下のように使 用される： （ａ）ＤＴＥタイムアウト ＤＴＥタイムアウトまたは類似する状態が生じるとき、任意のストリング整合過 程を終了し、エンコーダをフラッシュすることを必要とする。そのステップはス トリング整合過程から出て、部分的に整合されたストリングに対応するコードワ ードおよびフラッシュコードワードを伝送し、バッファをフラッシュすることを 含む。

（ｂ）バッファの終了 バッファの終了において、転送されるべきデータがこれ以上ないときフラッシュ 過程は使用されない。この効果はコードワードがフレーム境界を交差することを 許容することである。もしこれ以上転送されるべきデータがなければ、（ａ）で 限定された動作が実行される。

（ｃ）メツセージの終了 （ａ）で説明された過程が実行される。

７、例 （ｉ）辞書更新 ストリングｅ　１　ｅｐｈａｎ　ｔｏを入力する。すてに“ｅ　１　ｅ”と“ｐ ｈ”は辞書中に入力されている。

“ｅｌｅ”と“ｐｈ”を整合し、“ｐ′をｅｌｅ″に追加し、“ｈ”を“ｅｌｅ ｐ”に追加し、”ｅｌｅｐｈ”を与える。

“ａ”とｎ”を整合し、“ｎ”を“ａ″に追加し、“ａｎ”を与える。

“ｔｏと“を整合し、“を“ｔ”に追加し、“ｔ　”を与える。

（ｉｉ）透過検査 上記のように整合過程によってストリングｅ　１　ｅｐｈａｎｔ“を入力する。

ｅｌｅ″を整合し、３つずつ文字カウントを増加する。

コードワード長だけ圧縮ビットカウントを増加する。

“ｐｈ”を整合し、２つずつ文字カウントを増加する。

コードワード長だけ圧縮ビットカウントを増加する。

新しい辞書入力を追加する。

文字カウントが試験間隔より大きいとき、文字カウントオクテツト寸法（８）に 対して圧縮ビットを検査する。

透過モードにおいて圧縮ビットは文字カウント８よりも小さいとき、圧縮モード に切換える。

さらに、圧縮モードにおいて圧縮ビットが文字カウント８よりも大きいとき、透 過モードに切換える。

カウントをリセットする。

すなわち、“ｅｌｅ“＋“ｐｈ”、“ａ”＋“ｎｏ、“ｔ”十“である。文字カ ウントが試験間隔を超過し、性能と比較するとき、ここで試験しわかる。

（ｉｉｉ　）フラッシュ動作 上記のようにストリングを入力するが、“ｐ”の後にタイムアウトが生じる。

（ａ）圧縮モード “ｐ”に対応する不完全な入力でさえも、現在の整合ストリングのためにコード ワードを伝送する。

フラッシュコードワードを伝送する。ビットバッキングルーチンからビットをフ ラッシュし、再オクテツトが整列する。

エンコーダを接頭辞状態にリセットする。

ストリングをゼロ状態にリセットし、次の文字を待つ。

（ｂ）透過 現在のバッファ内容を伝送する。

８、構成概念 演算法は変更された２ｉｖ　Ｌｃｍｐｅｌ演算法に対する複雑性と比較される。

メモリ要求は第１の２６０辞書入力に対して１つの・辞書入力当り２バイトであ り、与えた後、各エンコーダおよびデコーダ辞書に対して１つの入力当り７バイ トである＝１０２４人カニ６にバイト ２０４８人カニ　１３にバイト ４０９６人カニ２７にバイト 処理速度は非常に速い。９．６にビット以上３８．４にビット以下の速度での動 作に対して、２８０フアミリプロセツサが要求されるに過ぎない。

応答時間はタイムアウトコードワードの使用によって最小限にされる。エンコー ダは間欠トラフィック（すなわちキーボード動作）を検出し部分的に整合された ストリングを伝送することを許容する。圧縮効率が最大であるとき、この機構は 連続するデータ流の条件下での動作を妨害しない。

９、概要 上述の演算法は高い圧縮を提供し、少量のメモリで簡単で低コストのマイクロプ ロセッサで実現されることができるので、モデム環境に理想的に適している。

構成の範囲は速度、性能およびコストに関して製造者にフレキシブル性を与える ことが可能である。これは構成コストを最小限にしたいという製造者の希望と、 最高の性能を提供したいという他の製造者の希望を実現させる。しかしながら、 この演算法は十分に限定されるので、異なる構成間の両立性を保証することが可 能である。

参考文献 ［１］　Ｉｎｆｏｒｍａｔｉｏｎ　Ｃｏｍｐｒｅｓｓｉｏｎ　ｂｙ　Ｆａｃｔｏ ｔｉｒｉｎｇ　ＣｏｍｍｏｎＳｔｒｉｎｇｓ ＾、　Ｍ！Ｆｌ＋！、　Ｅ、　Ｂ、　ＪａｍｅｓＣｏｍｐｕ＋ｔｒ　Ｊｏｕｒｎ ａｌ、Ｖｏｌ　１８．２１５７乃至１６０頁、１９７５年［２］　Ｃｏｍｐｒｅ ｓｓｉｏｎ　Ｉｎｄｉｖｉｄｕａｌ　５ｅｑｕｅｎｃｅｓ　ｖｉａ　Ｖａｒｉａ ｂｌｅＲａｔｅＣｏｄｉｎｇ Ｊ、−２ｉｖ、　Ａ、　Ｌｅｍｐ！Ｉ ＩＥＥＥ　Ｔｒａｍｓ、　ＩＴ　２４．５．５３０乃至５３６頁、１９７８年［ ３−コ　Ｕｓｅ　ｏｆ　Ｔｒｒｅ　５ｔｒｕｃｔｕｒｅｓ　ｆｏｒ　Ｐｒｏｃｅ ｓｓｉｎｇ　Ｆｉｌ　ＣｓＥ、　Ｈ，Ｓｕｓｓｓｎｇｕｌｈ ＣＡＣＭ、Ｖｏｌ　６．５．２７２乃至２７９頁、１９６３年［４］　Ｔｈ！Ａ ｒｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｐｒｏｇｒａｍｍｉｎｇ、Ｖｏｌ　３　Ｓｏｒ ｔＩｎｇａｎｄ　Ｓ！ａｒｃｈｉｎｇ　Ｄ、Ｋｎｕｔｈ、＾ｄｄｉｓｏｎ　Ｗｅ ｓｌｅｙ、　１９６８年［５］　１９６８年の５ｃｘＮＣｒ　Ｓｔｏｒａｇｔ　 ＴｅｃｈｎｉｑｕｅｓＲ，Ｍｏｒｔｉｓ ＣＡＣＭ、　Ｖｏｌ　１１．１３ｇ乃至４４頁［５］　Ｔ！ｃｈｎｉｃａｌ　Ｄ ｅｓｃｒｉｐ目ｏｎ　ｏｆ　ＢＴＬ２Ｂｒｉｊｉｓｈ　Ｔｔｌ！ｃｏｍ　ｃｏｎ ｔｒｉｂｕｔｉｏｎ　ｔｏ　ＣＣＩＴＴ　５ＧＸＶＩＩ［７］　Ａ　ｔｏｃｈｎ ｉｑｕＣｆｏｒ　Ｈｉｇｈ　Ｐｅｔｆｏｒｍｘｎｃｔ　ＤａｔａＣｏｍｐｒｔｓ ｓｉｏｎ 丁Ｗｅｌｃｈ Ｃｏｍｐｕｔｒｒ、　８乃至１９頁、１９８４年６月ｔａｐ　ｔｈａ　ｔｈｅ　 ｔｈｉ 補正書の翻訳文提出書く４！許法第１８４条の８）平成３年６月１０日

Claims (4)

【特許請求の範囲】
1. １．動的に編集された辞書を含むデータ圧縮システムにおいて、 辞書はワードおよび部分ワードを含むストリングを記憶することによって更新さ れ、部分ワードは入力データ流中のワードの直後に続くストリングからの複数の 文字を具備していることを特徴とするシステム。
2. ２．部分ワードはただ２つの文字を具備している請求項１記載のシステム。
3. ３．データ圧縮システムはメイン単一パスデータ圧縮演算法を使用するデータを 圧縮している請求項１または２記載のシステム。
4. ４．各ストリング整合過程の後の辞書の更新中に、対応する辞書入力に対する指 標が伝送されるメイン単一パスデータ圧縮演算法を使用するデータ圧縮システム 。