JPH0629861A - データ圧縮方法 - Google Patents
データ圧縮方法Info
- Publication number
- JPH0629861A JPH0629861A JP29152491A JP29152491A JPH0629861A JP H0629861 A JPH0629861 A JP H0629861A JP 29152491 A JP29152491 A JP 29152491A JP 29152491 A JP29152491 A JP 29152491A JP H0629861 A JPH0629861 A JP H0629861A
- Authority
- JP
- Japan
- Prior art keywords
- data
- byte
- user
- user data
- run
- 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
-
- 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/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)
- Image Processing (AREA)
Abstract
(57)【要約】
【目的】 ３文字未満の同一文字ランの効率的な符号化
を可能にするランレングス符号化によるデータ圧縮方法
を提供する。 【構成】 ２５６コード・ポイント８ビット文字セット
を追加のコード・ポイントを持つように拡張する。この
追加のコード・ポイントは特定の基数の制限レンジ内の
正の整数を表わすために必要とされるゼロでない数字に
対応する数値ウエイトを割り当てることにより、３文字
未満の同一文字ランの効率的な符号化を可能にする。デ
ータ流内のこの追加のエコー・コード・ポイントの存在
は、最後の正規の文字を指定された回数だけエコーする
意味である。このエコー・コード・ポイントは、特定の
基数のゼロでない数字に基づく数値ウエイトの割り当て
がサポートされるレンジ内の任意の要求される値となる
ような追加のシーケンスを提供するという意味において
加算的である。また、最も高い値のコード・ポイントが
任意の回数だけ反復できるために、復号することができ
る同一文字の上限に対するラン長の制約が除去される。
を可能にするランレングス符号化によるデータ圧縮方法
を提供する。 【構成】 ２５６コード・ポイント８ビット文字セット
を追加のコード・ポイントを持つように拡張する。この
追加のコード・ポイントは特定の基数の制限レンジ内の
正の整数を表わすために必要とされるゼロでない数字に
対応する数値ウエイトを割り当てることにより、３文字
未満の同一文字ランの効率的な符号化を可能にする。デ
ータ流内のこの追加のエコー・コード・ポイントの存在
は、最後の正規の文字を指定された回数だけエコーする
意味である。このエコー・コード・ポイントは、特定の
基数のゼロでない数字に基づく数値ウエイトの割り当て
がサポートされるレンジ内の任意の要求される値となる
ような追加のシーケンスを提供するという意味において
加算的である。また、最も高い値のコード・ポイントが
任意の回数だけ反復できるために、復号することができ
る同一文字の上限に対するラン長の制約が除去される。
Description
【０００１】
【産業上の利用分野】本発明はデータを圧縮する方法、
より詳細には、適応アルゴリズムを含む様々な高性能圧
縮アルゴリズムへの入力データを予備圧縮するために使
用されるランレングス符号器（run length encoder）に
関する。
より詳細には、適応アルゴリズムを含む様々な高性能圧
縮アルゴリズムへの入力データを予備圧縮するために使
用されるランレングス符号器（run length encoder）に
関する。
【０００２】
【従来の技術】圧縮とはデータをその表現を最少にする
ために符号化することである。圧縮はデータの伝送速度
を向上させ、また格納の効率を高める。過去数年間にお
いて、データを圧縮するための様々な方法が、特にデー
タ冗長を排除することに重点をおいて開発されてきた。
ために符号化することである。圧縮はデータの伝送速度
を向上させ、また格納の効率を高める。過去数年間にお
いて、データを圧縮するための様々な方法が、特にデー
タ冗長を排除することに重点をおいて開発されてきた。
【０００３】データ冗長には４つの基本タイプがある。
第一のタイプのデータ冗長は文字分布であり、ここで
は、ある典型的な文字ストリング内において、幾つかの
文字が他の文字よりも頻繁に使用される。単一文字ハフ
マン（Huffman ）符号化は、このタイプのデータ冗長を
うまく扱うことができる。ハフマン体系は、入力データ
の固定されたサイズの部分を可変長記号に翻訳すること
によって機能する。通常の使用においては、入力記号の
サイズは、圧縮のために必要とされる翻訳テーブルのサ
イズによって制約される。各々の入力記号及びそれと関
連するコードをリストするテーブルが必要である。ハフ
マン体系の欠点は、圧縮解除のために翻訳されるべき個
々のコードの長さが最初の数ビットが翻訳されるまで知
られていないために複雑であること、及び他のタイプの
データ冗長を扱うことができないことである。
第一のタイプのデータ冗長は文字分布であり、ここで
は、ある典型的な文字ストリング内において、幾つかの
文字が他の文字よりも頻繁に使用される。単一文字ハフ
マン（Huffman ）符号化は、このタイプのデータ冗長を
うまく扱うことができる。ハフマン体系は、入力データ
の固定されたサイズの部分を可変長記号に翻訳すること
によって機能する。通常の使用においては、入力記号の
サイズは、圧縮のために必要とされる翻訳テーブルのサ
イズによって制約される。各々の入力記号及びそれと関
連するコードをリストするテーブルが必要である。ハフ
マン体系の欠点は、圧縮解除のために翻訳されるべき個
々のコードの長さが最初の数ビットが翻訳されるまで知
られていないために複雑であること、及び他のタイプの
データ冗長を扱うことができないことである。
【０００４】第二のタイプのデータ冗長は、単一文字の
反復のストリングが起こる文字反復である。このケース
においては、メッセージは、通常単にその文字記号を反
復するよりもよりコンパクトに符号化できる。このタイ
プの冗長は、ランレングス符号化（run-length encodin
g 、ＲＬＥ）と呼ばれる体系を使用することによってう
まく扱うことができる。一連の同一の文字がカウント欄
並びにこれに反復される文字の識別子を加えたものとし
て符号化される。しかし、この体系はグラフィック・イ
メージに対しては効果的であるが、テキストファイルに
対しては有効でない。
反復のストリングが起こる文字反復である。このケース
においては、メッセージは、通常単にその文字記号を反
復するよりもよりコンパクトに符号化できる。このタイ
プの冗長は、ランレングス符号化（run-length encodin
g 、ＲＬＥ）と呼ばれる体系を使用することによってう
まく扱うことができる。一連の同一の文字がカウント欄
並びにこれに反復される文字の識別子を加えたものとし
て符号化される。しかし、この体系はグラフィック・イ
メージに対しては効果的であるが、テキストファイルに
対しては有効でない。
【０００５】第三のタイプのデータ冗長は、高使用パタ
ーンであり、ここではあるシーケンスの文字が比較的高
頻度にて現われる。これらシーケンスの文字は比較的少
ないビットで表わすことができ、この結果、時間及び空
間の両方の節約となる。通常の固定されたコードテーブ
ルを使用するプログラム化された圧縮体系は、このタイ
プの冗長を扱うことができる。この構成の短所は、最大
の効率を得るために個々のタイプのデータファイルに対
してコードテーブルをプログラムしなければならないこ
とである。
ーンであり、ここではあるシーケンスの文字が比較的高
頻度にて現われる。これらシーケンスの文字は比較的少
ないビットで表わすことができ、この結果、時間及び空
間の両方の節約となる。通常の固定されたコードテーブ
ルを使用するプログラム化された圧縮体系は、このタイ
プの冗長を扱うことができる。この構成の短所は、最大
の効率を得るために個々のタイプのデータファイルに対
してコードテーブルをプログラムしなければならないこ
とである。
【０００６】第四のタイプのデータ冗長は位置冗長であ
り、ここでは、ある文字が各々のデータブロック内の予
測可能な位置に一貫して現われる。入力記号の可変長ス
トリングを固定長コードに変換する適応圧縮はこのタイ
プのデータ冗長を扱うことができる。これら記号ストリ
ングは、全てが殆ど同一の発生確率を持つように選択さ
れる。適応圧縮はまた他の三つのタイプのデータ冗長を
扱うこともできる。これら様々なタイプのデータ冗長が
あるために、データ圧縮体系を使用してデータのサイズ
を縮小することが可能となる。最近の証拠は、データ圧
縮体系を組合わせて使用すると様々なこれら四つのタイ
プのデータ冗長が単一の体系よりもより効率的に扱える
ことを示す。これら組合わせの幾つかは、ランレングス
符号化を静的ハフマン符号化並びにレンプル・ゼブ（Le
mpel Zev）などの他の適応アルゴリズムのための予備圧
縮器として使用することを開示する。
り、ここでは、ある文字が各々のデータブロック内の予
測可能な位置に一貫して現われる。入力記号の可変長ス
トリングを固定長コードに変換する適応圧縮はこのタイ
プのデータ冗長を扱うことができる。これら記号ストリ
ングは、全てが殆ど同一の発生確率を持つように選択さ
れる。適応圧縮はまた他の三つのタイプのデータ冗長を
扱うこともできる。これら様々なタイプのデータ冗長が
あるために、データ圧縮体系を使用してデータのサイズ
を縮小することが可能となる。最近の証拠は、データ圧
縮体系を組合わせて使用すると様々なこれら四つのタイ
プのデータ冗長が単一の体系よりもより効率的に扱える
ことを示す。これら組合わせの幾つかは、ランレングス
符号化を静的ハフマン符号化並びにレンプル・ゼブ（Le
mpel Zev）などの他の適応アルゴリズムのための予備圧
縮器として使用することを開示する。
【０００７】ランレングス符号化（ＲＬＥ）は、前述の
如く、一連の同一文字、あるいは反復文字のストリング
がカウント欄とこれに反復文字の識別子が加えられたも
のとして符号化されるデータ圧縮体系である。この符号
化の結果は、同一文字のランを符号化するためのオーバ
ヘッドの二つの文字（エスケープ文字及び反復カウン
ト）の生成である。これは、有効性を４つあるいはそれ
以上のランに制限する。これに加えて、先行技術による
ＲＬＥ体系は、符号化できる同一文字ランの長さに固定
された上限があるという欠点を持つ。さらに、二進デー
タが圧縮された場合、データ内の（エスケープ文字を含
む）全てのコード・ポイントの生来の存在のためにデー
タ透過性の問題が発生する。
如く、一連の同一文字、あるいは反復文字のストリング
がカウント欄とこれに反復文字の識別子が加えられたも
のとして符号化されるデータ圧縮体系である。この符号
化の結果は、同一文字のランを符号化するためのオーバ
ヘッドの二つの文字（エスケープ文字及び反復カウン
ト）の生成である。これは、有効性を４つあるいはそれ
以上のランに制限する。これに加えて、先行技術による
ＲＬＥ体系は、符号化できる同一文字ランの長さに固定
された上限があるという欠点を持つ。さらに、二進デー
タが圧縮された場合、データ内の（エスケープ文字を含
む）全てのコード・ポイントの生来の存在のためにデー
タ透過性の問題が発生する。
【０００８】
【発明が解決しようとする課題】必要とされるのは、三
つ未満の文字の同一文字ストリングを効率的に符号化で
き、同時に同一文字の長さの上限を拡張することができ
る、それ自体としてあるいは予備圧縮器として使用が可
能なランレングス符号化の方法である。理想的には、こ
の方法は、データ内の全てのコードポイントとエスケー
プ文字の発生に起因するデータ透過性問題の排除あるい
は軽減ができるべきである。
つ未満の文字の同一文字ストリングを効率的に符号化で
き、同時に同一文字の長さの上限を拡張することができ
る、それ自体としてあるいは予備圧縮器として使用が可
能なランレングス符号化の方法である。理想的には、こ
の方法は、データ内の全てのコードポイントとエスケー
プ文字の発生に起因するデータ透過性問題の排除あるい
は軽減ができるべきである。
【０００９】
【課題を解決するための手段】本発明は、普通の２５６
コード・ポイント８ビット文字セットを追加のコードポ
イントを持つように拡張するランレングス符号化（ＲＬ
Ｅ）の方法を開示する。小さなセットの追加の”エコ
ー”コード・ポイントが提供されるが、これは、３文字
よりも小さな同一文字ランの効率的な符号化を可能にす
る。これらエコー・コード・ポイントには、特定の基数
の制限レンジ内の正の整数を表わすために必要とされる
ゼロでない数字に対応する数値ウエイトが割り当てられ
る。例えば、レンジ１から２６をカバーするためにセッ
トの６つの追加のコード・ポイントが必要であるような
場合、基数−３のエコー・コード・ポイントが提供され
る。データ流内のこの追加のエコー・コード・ポイント
の存在は、最後の正規の文字を指定された回数だけエコ
ーする意味であると翻訳される。このエコー・コード・
ポイントは、特定の基数のゼロでない数字に基づく数値
ウエイトの割り当てがサポートされるレンジ内の任意の
要求される値となるように追加のシーケンスを提供する
という意味において加算的である。より具体的には、最
も高い値のコードポイントが任意の回数だけ反復でき、
上限に対するランレングスの制約が除去される。
コード・ポイント８ビット文字セットを追加のコードポ
イントを持つように拡張するランレングス符号化（ＲＬ
Ｅ）の方法を開示する。小さなセットの追加の”エコ
ー”コード・ポイントが提供されるが、これは、３文字
よりも小さな同一文字ランの効率的な符号化を可能にす
る。これらエコー・コード・ポイントには、特定の基数
の制限レンジ内の正の整数を表わすために必要とされる
ゼロでない数字に対応する数値ウエイトが割り当てられ
る。例えば、レンジ１から２６をカバーするためにセッ
トの６つの追加のコード・ポイントが必要であるような
場合、基数−３のエコー・コード・ポイントが提供され
る。データ流内のこの追加のエコー・コード・ポイント
の存在は、最後の正規の文字を指定された回数だけエコ
ーする意味であると翻訳される。このエコー・コード・
ポイントは、特定の基数のゼロでない数字に基づく数値
ウエイトの割り当てがサポートされるレンジ内の任意の
要求される値となるように追加のシーケンスを提供する
という意味において加算的である。より具体的には、最
も高い値のコードポイントが任意の回数だけ反復でき、
上限に対するランレングスの制約が除去される。
【００１０】
【実施例】図面を参照すると、特に図１には、本発明の
予備圧縮データ圧縮システムの好ましい実施例のブロッ
ク図が示される。ビット・データ流１０がビット・チョ
ッパ１２に加えられ、出力１４が生成される。ビット・
チョッパ１２はビット・データ流１０上の文字の文字幅
を定義するために使用され、データ流１０（ユーザ・デ
ータ・ブロック）を複数の同一サイズのデータ・セグメ
ント１４に分割する。チョッパ１２の出力１４は本発明
によって開示されるランレングス符号器（run-length e
ncoder、RLE ）を含む予備圧縮器への入力として供給さ
れる。ランレングス符号器１６の出力１８は次に第２段
高性能圧縮アルゴリズム２０に供給され、二重に圧縮さ
れた出力データ２２が生成される。このデータ・セグメ
ント１４の各々の圧縮は、データ・セグメントの一つの
中の受信された１つのユーザ・データ・バイトがｎ個
（ｎは２より大）前のデータ・バイト、ストリングの最
後のバイト、あるいは１つのデータ・セグメント内の単
一のユーザ・データ・バイトと同一であるか否か決定
し、少なくともｎ個の前のユーザ・データ・バイトと同
一の基数符号化を使用してユーザ・データ・バイトに複
数のランレングス参照番号の一つを割り当てることによ
りなされる。高性能圧縮アルゴリズム２０は、ハフマン
（Huffman ）あるいはシャノン−ファノ（Shannon-Fan
o）、並びにより高度な適応アルゴリズム、例えば、レ
ンペル−ゼブ（Lempel-Zev）であり得る。こうして二重
に圧縮されたデータ流２２は、次に、伝送あるいは格納
などの目的で処理論理３２に入力として供給される。
予備圧縮データ圧縮システムの好ましい実施例のブロッ
ク図が示される。ビット・データ流１０がビット・チョ
ッパ１２に加えられ、出力１４が生成される。ビット・
チョッパ１２はビット・データ流１０上の文字の文字幅
を定義するために使用され、データ流１０（ユーザ・デ
ータ・ブロック）を複数の同一サイズのデータ・セグメ
ント１４に分割する。チョッパ１２の出力１４は本発明
によって開示されるランレングス符号器（run-length e
ncoder、RLE ）を含む予備圧縮器への入力として供給さ
れる。ランレングス符号器１６の出力１８は次に第２段
高性能圧縮アルゴリズム２０に供給され、二重に圧縮さ
れた出力データ２２が生成される。このデータ・セグメ
ント１４の各々の圧縮は、データ・セグメントの一つの
中の受信された１つのユーザ・データ・バイトがｎ個
（ｎは２より大）前のデータ・バイト、ストリングの最
後のバイト、あるいは１つのデータ・セグメント内の単
一のユーザ・データ・バイトと同一であるか否か決定
し、少なくともｎ個の前のユーザ・データ・バイトと同
一の基数符号化を使用してユーザ・データ・バイトに複
数のランレングス参照番号の一つを割り当てることによ
りなされる。高性能圧縮アルゴリズム２０は、ハフマン
（Huffman ）あるいはシャノン−ファノ（Shannon-Fan
o）、並びにより高度な適応アルゴリズム、例えば、レ
ンペル−ゼブ（Lempel-Zev）であり得る。こうして二重
に圧縮されたデータ流２２は、次に、伝送あるいは格納
などの目的で処理論理３２に入力として供給される。
【００１１】ランレングス符号器１６の機能はレジスタ
内に格納された情報について遂行されることが当業者に
理解される。ランレングス符号器１６は、ディスクリー
ト部品を使用して実現することも、あるいはこの流れ図
のステップを遂行するようにプログラムされた小さなコ
ンピュータシステムを使用して遂行することもできる。
内に格納された情報について遂行されることが当業者に
理解される。ランレングス符号器１６は、ディスクリー
ト部品を使用して実現することも、あるいはこの流れ図
のステップを遂行するようにプログラムされた小さなコ
ンピュータシステムを使用して遂行することもできる。
【００１２】図１に戻って、データ圧縮システムの復号
部分について説明する。二重に圧縮されたデータ流３０
は、入力として処理論理３２に供給されるが、これはデ
ータ流３０を受信し、入力を圧縮解除（decompression
）要素３６の入力として供給する。この第２段圧縮解
除要素３６は、高性能圧縮アルゴリズム２０の補数であ
っても良い。この第２段圧縮解除要素の出力３８は、入
力としてランレングス符号器圧縮解除器４０に供給され
る。ランレングス圧縮解除器の出力４２は、チョッパ４
４に供給される。チョッパ４４は、再構成されたデータ
流１０を与え、これは、ホストあるいはチャネル（図示
せず）に供給される。
部分について説明する。二重に圧縮されたデータ流３０
は、入力として処理論理３２に供給されるが、これはデ
ータ流３０を受信し、入力を圧縮解除（decompression
）要素３６の入力として供給する。この第２段圧縮解
除要素３６は、高性能圧縮アルゴリズム２０の補数であ
っても良い。この第２段圧縮解除要素の出力３８は、入
力としてランレングス符号器圧縮解除器４０に供給され
る。ランレングス圧縮解除器の出力４２は、チョッパ４
４に供給される。チョッパ４４は、再構成されたデータ
流１０を与え、これは、ホストあるいはチャネル（図示
せず）に供給される。
【００１３】図２には、図１のランレングス符号器（Ｒ
ＬＥ）１６内で実現されるような１２個の新たな基数−
３エコー・コード・ポイントを定義する基数−３符号化
の例が示される。１６進コード・ポイント５０が個々の
新たなコード・ポイントに対して１０進ウエイト５２及
び基数−３ウエイト５４とともに示される。図２は、最
高７２８文字までの長さを持つランを符号化するのに使
用できる全部で１２の新たな基数−３”エコー”コード
・ポイント５０を示す。この符号化は反復カウントを基
数−３の値として表わし、次にこの値を適当な一つある
いは複数のセットの基数−３エコー・コード・ポイント
を使用して符号化することによって最適に達成できる。
７２８よりも長い長さを持つランは、エコー・コード・
セットをより大きな基数−３値を包含するように拡張す
ることによって、あるいは残りのランレングスが最適レ
ンジに整理されるまで最も高いウエイトのエコー・コー
ド（カラム５０内の０ｘ１０Ｂ）を単に反復し、次に通
常の符号化プロセスを適用することによって収容するこ
とができる。
ＬＥ）１６内で実現されるような１２個の新たな基数−
３エコー・コード・ポイントを定義する基数−３符号化
の例が示される。１６進コード・ポイント５０が個々の
新たなコード・ポイントに対して１０進ウエイト５２及
び基数−３ウエイト５４とともに示される。図２は、最
高７２８文字までの長さを持つランを符号化するのに使
用できる全部で１２の新たな基数−３”エコー”コード
・ポイント５０を示す。この符号化は反復カウントを基
数−３の値として表わし、次にこの値を適当な一つある
いは複数のセットの基数−３エコー・コード・ポイント
を使用して符号化することによって最適に達成できる。
７２８よりも長い長さを持つランは、エコー・コード・
セットをより大きな基数−３値を包含するように拡張す
ることによって、あるいは残りのランレングスが最適レ
ンジに整理されるまで最も高いウエイトのエコー・コー
ド（カラム５０内の０ｘ１０Ｂ）を単に反復し、次に通
常の符号化プロセスを適用することによって収容するこ
とができる。
【００１４】図４には基数−３（３進）を使用して符号
化されたデータ流の一例が示される。符号化されてない
データ流７０が示されるが、これは、２よりも多い個数
のデータバイトすなわち、５７７文字の長さを持つ”
Ｄ”文字のランを含む。反復カウントは、５７６である
が、基数３−値２１０１００として表わされる。この値
は、３つの非ゼロの基数−３の数字を持ち、従って、示
されるように３つの基数−３のエコー・コード７２（０
ｘ１０Ｂ、０ｘ１０８、及び０ｘ１０４）のみを使用し
て最適に符号化できる。
化されたデータ流の一例が示される。符号化されてない
データ流７０が示されるが、これは、２よりも多い個数
のデータバイトすなわち、５７７文字の長さを持つ”
Ｄ”文字のランを含む。反復カウントは、５７６である
が、基数３−値２１０１００として表わされる。この値
は、３つの非ゼロの基数−３の数字を持ち、従って、示
されるように３つの基数−３のエコー・コード７２（０
ｘ１０Ｂ、０ｘ１０８、及び０ｘ１０４）のみを使用し
て最適に符号化できる。
【００１５】図３には、基数−１０（１０進）を使用し
て符号化されたデータ流が示される。５８１バイトを表
わす元の符号化されてない文字シーケンス６０が全部で
８個のコード・ポイント６２に整理される。反復カウン
トを３２に制限する先行技術によるランレングス符号化
体系においては、これと同一のシーケンスが符号化のた
めに全部で２３個のコード・ポイントを必要とする。基
数エコー・コードを使用する本発明は、先行技術のラン
レングス符号器によって示される３２個の固定されたコ
ード・ポイントよりも少ないコード・ポイントを必要と
する。従って、本発明は、ランレングス符号化のために
より少ない通信チャネル・バンド幅を使用することにな
る。
て符号化されたデータ流が示される。５８１バイトを表
わす元の符号化されてない文字シーケンス６０が全部で
８個のコード・ポイント６２に整理される。反復カウン
トを３２に制限する先行技術によるランレングス符号化
体系においては、これと同一のシーケンスが符号化のた
めに全部で２３個のコード・ポイントを必要とする。基
数エコー・コードを使用する本発明は、先行技術のラン
レングス符号器によって示される３２個の固定されたコ
ード・ポイントよりも少ないコード・ポイントを必要と
する。従って、本発明は、ランレングス符号化のために
より少ない通信チャネル・バンド幅を使用することにな
る。
【００１６】本発明は、それがプリンタ・ファイル、テ
キスト、データファイルあるいはグラフィックデータの
いずれから派生されたものであっても、デジタル形式に
て表わせるものであれば、全ての形式の情報を圧縮する
ことができる。このラン長符号器システムは、それのみ
で使用することもできるが、これは、ランレングス符号
器の出力の所に生成される文字をさらに圧縮する高性能
圧縮アルゴリズムを持つ普遍データ圧縮システム内にお
いて一層有効となる。例えば、白黒フォーマットのグラ
フィックデータは、白の背景上の黒いラインが主体とな
る。このようなグラフィックデータがラスタ走査され、
線型部分を表わす文字に整理された場合、非常に多数の
隣接する冗長文字が存在する。同一の文字は、単一の文
字に圧縮あるいは整理され、第二のデータ圧縮システム
内においてさらに圧縮される。
キスト、データファイルあるいはグラフィックデータの
いずれから派生されたものであっても、デジタル形式に
て表わせるものであれば、全ての形式の情報を圧縮する
ことができる。このラン長符号器システムは、それのみ
で使用することもできるが、これは、ランレングス符号
器の出力の所に生成される文字をさらに圧縮する高性能
圧縮アルゴリズムを持つ普遍データ圧縮システム内にお
いて一層有効となる。例えば、白黒フォーマットのグラ
フィックデータは、白の背景上の黒いラインが主体とな
る。このようなグラフィックデータがラスタ走査され、
線型部分を表わす文字に整理された場合、非常に多数の
隣接する冗長文字が存在する。同一の文字は、単一の文
字に圧縮あるいは整理され、第二のデータ圧縮システム
内においてさらに圧縮される。
【００１７】要約すると、本発明は、２５６コード・ポ
イント８ビット文字セットを追加のコード・ポイントを
持つように拡張するランレングス符号化の方法を開示す
る。３文字未満の同一の文字ランの符号化を可能にす
る”エコー”コード・ポイントが提供される。これらエ
コー・コード・ポイントには、特定の基数の制限された
レンジ内の正の整数を表わすのに必要とされるゼロでな
い数字に対応する数値ウエイトが割り当てられる。デー
タ流内のこの追加のエコー・コード・ポイントは、最後
の通常の文字を指定される回数だけエコーすることを意
味するものと解釈される。このエコー・コード・ポイン
トは、特定の基数のゼロでない数字に基づく数値ウエイ
トの割り当てがサポートされるレンジ内の任意の要求さ
れる値となるような追加のシーケンスを提供すると言う
意味において加算的である。この実現は、最も高い値の
コード・ポイントを任意の回数だけ反復することを可能
とし、従って、上限に対するランレングスの制約を除去
する。
イント８ビット文字セットを追加のコード・ポイントを
持つように拡張するランレングス符号化の方法を開示す
る。３文字未満の同一の文字ランの符号化を可能にす
る”エコー”コード・ポイントが提供される。これらエ
コー・コード・ポイントには、特定の基数の制限された
レンジ内の正の整数を表わすのに必要とされるゼロでな
い数字に対応する数値ウエイトが割り当てられる。デー
タ流内のこの追加のエコー・コード・ポイントは、最後
の通常の文字を指定される回数だけエコーすることを意
味するものと解釈される。このエコー・コード・ポイン
トは、特定の基数のゼロでない数字に基づく数値ウエイ
トの割り当てがサポートされるレンジ内の任意の要求さ
れる値となるような追加のシーケンスを提供すると言う
意味において加算的である。この実現は、最も高い値の
コード・ポイントを任意の回数だけ反復することを可能
とし、従って、上限に対するランレングスの制約を除去
する。
【発明の効果】以上のように本発明によれば、エコー・
コード・ポイントを用いることにより、３文字未満の同
一文字ランの効率的な符号化が可能になる。
コード・ポイントを用いることにより、３文字未満の同
一文字ランの効率的な符号化が可能になる。
【図１】本発明による予備圧縮データ圧縮システムの好
ましい実施態様のブロック図である。
ましい実施態様のブロック図である。
【図２】１２の新たな基数−３ エコー・コード・ポイ
ントを定義する基数−３符号化の一例を示す説明図であ
る。
ントを定義する基数−３符号化の一例を示す説明図であ
る。
【図３】基数−１０を使用して符号化されたデータ流の
一例を示す説明図である。
一例を示す説明図である。
【図４】基数−３を使用して符号化されたデータ流の一
例を示す説明図である。
例を示す説明図である。
Claims (6)
- 【請求項１】ユーザ・データ・ブロックを圧縮されたデ
ータ・ブロックに圧縮するデータ圧縮方法において、 受信されたユーザ・データ・バイトがｎ個の前のデータ
・バイト、ストリングの最後のバイト、あるいはデータ
の一つのセグメント内の単一のユーザ・データ・バイト
と同一であるか否かを決定するステップ；少なくとも前
記ｎ個のユーザ・データ・バイトと同一の基数表記法を
使用してユーザ・データ・バイトに複数のランレングス
参照番号の一つを割り当てるステップを含み、ここで、
ｎは２よりも大きな整数を表わすことを特徴とするデー
タ圧縮方法。 - 【請求項２】前記圧縮データ・ブロックを二重に圧縮さ
れたデータ・ブロックを生成するために第２段圧縮器に
供給するステップがさらに含まれることを特徴とする請
求項１のデータ圧縮方法。 - 【請求項３】前記二重に圧縮されたデータ・ブロックを
前記ユーザ圧縮データ・ブロックを生成するために圧縮
解除するステップがさらに含まれることを特徴とする請
求項２のデータ圧縮方法。 - 【請求項４】ユーザ・データ・ブロックを圧縮されたデ
ータ・ブロックに圧縮する方法において、 前記ユーザ・データ・ブロックを複数の同一サイズのデ
ータ・セグメントに分割するステップ、及び前記ユーザ
・データ・ブロック内の前記データ・セグメントの各々
を圧縮するステップを含み、前記圧縮ステップが：前記
データ・セグメントの一つの中の前記受信されたユーザ
・データ・バイトがｎ個前のデータ・バイト、ストリン
グの最後のバイト、あるいは一つのデータ・セグメント
内の単一のユーザ・データ・バイトと同一であるか否か
決定するステップ、 少なくとも前記ｎ個の前のユーザ・データ・バイトと同
一の基数符号化を使用してユーザ・データ・バイトに複
数のランレングス参照番号の一つを割り当てるステップ
を含み、ここで、ｎが２よりも大きな整数であることを
特徴とするデータ圧縮方法。 - 【請求項５】前記圧縮されたセグメントを二重に圧縮さ
れたセグメントを生成するために第２段の圧縮器に供給
するステップがさらに含まれることを特徴とする請求項
４のデータ圧縮方法。 - 【請求項６】前記二重に圧縮されたセグメントを前記ユ
ーザ・データ・バイト及び基数符号化における前記複数
のランレングス参照番号の一つを生成するために圧縮解
除するステップがさらに含まれることを特徴とする請求
項５のデータ圧縮方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US63678390A | 1990-12-31 | 1990-12-31 | |
| US636783 | 1990-12-31 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0629861A true JPH0629861A (ja) | 1994-02-04 |
Family
ID=24553304
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP29152491A Pending JPH0629861A (ja) | 1990-12-31 | 1991-11-07 | データ圧縮方法 |
Country Status (2)
| Country | Link |
|---|---|
| EP (1) | EP0494038A3 (ja) |
| JP (1) | JPH0629861A (ja) |
Families Citing this family (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5627534A (en) * | 1995-03-23 | 1997-05-06 | International Business Machines Corporation | Dual stage compression of bit mapped image data using refined run length and LZ compression |
| US5710561A (en) * | 1996-01-02 | 1998-01-20 | Peerless Systems Corporation | Method and apparatus for double run-length encoding of binary data |
| KR100463001B1 (ko) * | 1997-02-17 | 2005-04-25 | 주식회사 팬택앤큐리텔 | 발생위치가무작위인점들의위치정보부호화방법 |
| CN117155406B (zh) * | 2023-10-30 | 2024-02-02 | 深圳市成为高科技有限公司 | 一种社会调查数据智能管理系统 |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5816344A (ja) * | 1981-07-21 | 1983-01-31 | Nec Corp | デ−タ圧縮記憶装置 |
| JPS63148717A (ja) * | 1986-12-12 | 1988-06-21 | Hitachi Ltd | データ圧縮復元処理装置 |
| JPS63240648A (ja) * | 1987-03-27 | 1988-10-06 | Nec Corp | デ−タ圧縮記憶方式 |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4626829A (en) * | 1985-08-19 | 1986-12-02 | Intelligent Storage Inc. | Data compression using run length encoding and statistical encoding |
| US4955066A (en) * | 1989-10-13 | 1990-09-04 | Microsoft Corporation | Compressing and decompressing text files |
-
1991
- 1991-11-07 JP JP29152491A patent/JPH0629861A/ja active Pending
- 1991-12-06 EP EP19910480181 patent/EP0494038A3/en not_active Withdrawn
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5816344A (ja) * | 1981-07-21 | 1983-01-31 | Nec Corp | デ−タ圧縮記憶装置 |
| JPS63148717A (ja) * | 1986-12-12 | 1988-06-21 | Hitachi Ltd | データ圧縮復元処理装置 |
| JPS63240648A (ja) * | 1987-03-27 | 1988-10-06 | Nec Corp | デ−タ圧縮記憶方式 |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0494038A2 (en) | 1992-07-08 |
| EP0494038A3 (en) | 1992-08-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5045852A (en) | Dynamic model selection during data compression | |
| US5818877A (en) | Method for reducing storage requirements for grouped data values | |
| JP3541930B2 (ja) | 符号化装置及び復号化装置 | |
| EP1057269B1 (en) | Block-wise adaptive statistical data compressor | |
| US5001478A (en) | Method of encoding compressed data | |
| JP3459030B2 (ja) | 符号化システム | |
| US5867114A (en) | Method and apparatus for performing data compression | |
| US5389922A (en) | Compression using small dictionaries with applications to network packets | |
| KR100894002B1 (ko) | 선택적 압축과 복원 및 압축 데이터에 대한 데이터 포맷을위한 장치 및 방법 | |
| US5774081A (en) | Approximated multi-symbol arithmetic coding method and apparatus | |
| US7365658B2 (en) | Method and apparatus for lossless run-length data encoding | |
| US5594435A (en) | Permutation-based data compression | |
| EP0903866B1 (en) | Method and apparatus for data compression | |
| JPH03204233A (ja) | データ圧縮方法 | |
| Gupta et al. | Data compression-lossless and lossy techniques | |
| Mathpal et al. | A research paper on lossless data compression techniques | |
| US5010344A (en) | Method of decoding compressed data | |
| EP0435802B1 (en) | Method of decompressing compressed data | |
| JPH0629861A (ja) | データ圧縮方法 | |
| EP0340039B1 (en) | Search tree data structure encoding for textual substitution data compression systems | |
| EP0340041B1 (en) | Start, step, stop unary coding for data compression | |
| JP3124887B2 (ja) | データ圧縮・復号方式 | |
| JP2005521324A (ja) | 損失のないデータの圧縮および圧縮解除方法および装置 | |
| Jeromel et al. | Comparison of entropy coders for lossless grayscale image compression | |
| US20080001790A1 (en) | Method and system for enhancing data compression |