(57)【特許請求の範囲】
【請求項１】
データ文字の入力ストリームを出力ストリームに変換するための方法であって、前記入力ストリームは、同じデータ文字の少なくとも１つのランを含み、
前記入力ストリーム中の所定のデータ文字が隣接する所定の数のデータ文字と同じであることを検出することによって、該入力ストリーム中にランが発生していることを検出する工程と、
ここで、前記検出された同じデータ文字のランは、データ文字の数が増加する複数の連続したランセグメントを構成し、該各ランセグメントのデータ文字の数と隣合う１つのランセグメントのデータ文字の数とは、１文字毎に異なり、
前記検出されたランの前記連続したランセグメントに各々対応したコードであって、数値コードを増加するシーケンスのコードを順次生成する工程と、
前記シーケンスの前記コードを、前記検出されたランのそれぞれの前記連続したランセグメントに割り当てる工程と、
前記各検出されたランの前記連続したランセグメントに割り当てられた前記コードを出力する工程と、
前記入力ストリーム中の所定のデータ文字が、隣接する所定の数のデータ文字と同じでないことを検出することによって、該入力ストリーム中にランが発生していないことを検出する工程と、
前記検出されたランの一部でないことを示すデータ文字を出力する工程と
を具え、
前記出力ストリームは、前記検出された各ランであることを示す前記出力されるコードと、前記検出されたランの一部でないことを示す前記出力されるデータ文字としての非ラン文字とを含み、
前記検出された各ランであることを示す前記出力されるコードは、各々、前記出力ストリーム内の前記検出されたランの前記連続したランセグメントを示すことを特徴とする方法。
【請求項２】
前記検出されたランの前記連続したランセグメントは、最終ランセグメントを含み、
前記最終ランセグメントに続く前記入力ストリームが、次に続くランセグメントを構成するように、前記検出されたランのデータ文字と同じ隣接するデータ文字を検出する工程と、
前記データ文字を検出した後で、前記コードのシーケンスをその次に続くコードに増進する工程と
をさらに含むことを特徴とする請求項１記載の方法。
【請求項３】
前記出力されるコードに対して割り当てられた前記検出されたランの各ランセグメントのデータ文字を破棄する工程
をさらに含むことを特徴とする請求項２記載の方法。
【請求項４】
前記最終ランセグメントの破棄された文字に続く前記入力ストリームの次のデータ文字を処理を続行する工程
をさらに含むことを特徴とする請求項３記載の方法。
【請求項５】
それぞれ割り当てられたコードと共に、前記セグメントのデータ文字数を有するランセグメントデータを記憶する工程と、
現在検出中のランが、前記記憶されたあるセグメントのデータ文字数を含むかどうかを判定するために、前記記憶されたランセグメントデータにアクセスする工程と、
前記記憶されたセグメントに割り当てられたコードを出力する工程と
をさらに含むことを特徴とする請求項１記載の方法。
【請求項６】
前記検出されたランに対して、該ランのデータ文字を出力する工程をさらに含み、
前記出力ストリームは、該ランの出力された文字を含むことを特徴とする請求項１記載の方法。
【請求項７】
前記出力された非ラン文字に対して、前記シーケンスのコードをその次に続くコードに増進する工程
をさらに含むことを特徴とする請求項１記載の方法。
【請求項８】
データ文字の入力ストリームを出力ストリームに変換するための装置であって、前記入力ストリームは、同じデータ文字の少なくとも１つのランを含み、
前記入力ストリーム中の所定のデータ文字が隣接する所定の数のデータ文字と同じであることを検出することによって、該入力ストリーム中にランが発生していることを検出する手段と、
ここで、前記検出された同じデータ文字のランは、データ文字の数が増加する複数の連続したランセグメントを構成し、該各ランセグメントのデータ文字の数と隣合う１つのランセグメントのデータ文字の数とは、１文字毎に異なり、
前記検出されたランの前記連続したランセグメントに各々対応したコードであって、数値コードを増加するシーケンスのコードを順次生成する手段と、
前記シーケンスの前記コードを、前記検出されたランのそれぞれの前記連続したランセグメントに割り当てる手段と、
前記各検出されたランの前記連続したランセグメントに割り当てられた前記コードを出力する手段と、
前記入力ストリーム中の所定のデータ文字が、隣接する所定の数のデータ文字と同じでないことを検出することによって、該入力ストリーム中にランが発生していないことを検出する手段と、
前記検出されたランの一部でないことを示すデータ文字を出力する手段と
を具え、
前記出力ストリームは、前記検出された各ランであることを示す前記出力されるコードと、前記検出されたランの一部でないことを示す前記出力されるデータ文字としての非ラン文字とを含み、
前記検出された各ランであることを示す前記出力されるコードは、各々、前記出力ストリーム内の前記検出されたランの前記連続したランセグメントを示すことを特徴とする装置。
【請求項９】
前記検出されたランの前記連続したランセグメントは、最終ランセグメントを含み、
前記最終ランセグメントに続く前記入力ストリームが、次に続くランセグメントを構成するように、前記検出されたランのデータ文字と同じ隣接するデータ文字を検出する手段と、
前記データ文字を検出した後で、前記コードのシーケンスをその次に続くコードに増進する手段と
をさらに含むことを特徴とする請求項８記載の装置。
【請求項１０】
前記出力されるコードに対して割り当てられた前記検出されたランの各ランセグメントのデータ文字を破棄する手段
をさらに含むことを特徴とする請求項９記載の装置。
【請求項１１】
それぞれ割り当てられたコードと共に、前記セグメントのデータ文字数を有するランセグメントデータを記憶する手段と、
現在検出中のランが、前記記憶されたあるセグメントのデータ文字数を含むかどうかを判定するために、前記記憶されたランセグメントデータにアクセスする手段と、
前記記憶されたセグメントに割り当てられたコードを出力する手段と
をさらに含むことを特徴とする請求項８記載の装置。
【請求項１２】
前記検出されたランに対して、該ランのデータ文字を出力する工程をさらに含み、
前記出力ストリームは、該ランの出力された文字を含むことを特徴とする請求項８記載の装置。
【請求項１３】
前記出力された非ラン文字に対して、前記シーケンスのコードをその次に続くコードに増進する手段
をさらに含むことを特徴とする請求項８記載の装置。
【請求項１４】
前記順次生成するための手段は、前記シーケンスを生成するために、１つずつ増分可能なコードカウンタを具えたことを特徴とする請求項８記載の装置。
【発明の詳細な説明】
【０００１】
（発明の背景）
（１．発明の分野）
本発明は、データ圧縮に関し、より詳細には従来技術において今まで開発されたことの無い埋込みランレングス符号化によるデータ圧縮の実施形態を提供することに関する。
【０００２】
（２．従来技術の説明）
Ａｂｒａｈａｍ  Ｌｅｍｐｅｌ博士およびＪａｃｏｂ  Ｚｉｖ博士は、現在、広範に使用されているＬＺデータ圧縮／圧縮解除システムの理論的基礎を提供した。両博士の独創性に富んだ２つの論文は、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ、ＩＴ−２３−３、１９７７年５月、３３７頁から３４３頁とＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ、ＩＴ−２４−５、１９７８年９月、５３０頁から５３６頁に記載されている。Ｖ．４２  ｂｉｓモデム圧縮／圧縮解除の規格として採用されＬＺＷとして知られる広範に使用されているデータ圧縮／圧縮解除システムは、１９８５年１２月１０日に発行されたＷｅｌｃｈによる米国特許第４，５５８，３０２号に記載されている。ＬＺＷは、ＧＩＦ画像通信プロトコルおよびＴＩＦＦ画像通信プロトコルで使用される圧縮／圧縮解除の規格として採用されてきた。
【０００３】
ランレングス符号化（ＲＬＥ）と表示される、もう１つのタイプのデータ圧縮／圧縮解除は、反復する文字とそのラン長を示す圧縮されたコードを提供することによって反復する文字ランを圧縮する。したがって、ＲＬＥは同じ文字の長いストリングの符号化には効果的である。例えば、ＲＬＥは、データファイルの始めに含まれる場合のある空白の長いシーケンスを圧縮することにおいては効果的である。ＲＬＥはまた、画像が、空と陸地の画像における空の部分のように同じ値を有する連続したピクセルの長いランを含む場合には、画像圧縮においても同様に効果的である。
【０００４】
従来技術では、データをランレングスエンコーダに適用し、そのランレングス符号化されたデータをＬＺベースのシステムに適用することによって、ランレングス符号化をＬＺシステムと結合してきた。このようなアーキテクチャでは、コンプレッサのフロントエンドではランレングスエンコーダが使用され、デコンプレッサの出力端部ではランレングスデコーダが使用される。このようなシステムは、機器、費用、制御のオーバーヘッドおよび処理時間の増大という欠点を被る。
【０００５】
ランレングス符号化は、１９９５年２月１４日発行の、Ｓｅｒｏｕｓｓｉ他による米国特許第５，３８９，９２２号のＬＺＷベースのシステムにも含まれている。この特許のシステムでは、コンプレッサからのある種の出力コードは、反復する入力データ文字のランがある場合は抑制される。消失したコードを再生成するためには、デコンプレッサへの入力で、特別のラン補強エンジンが使用される。
【０００６】
データ文字の符号化を必要とするもう１つのデータ圧縮／圧縮解除システムは、１９９９年１月１９日発行の、Ｗｅｌｃｈ他による米国特許第５，８６１，８２７号で開示されている。このシステムのコンプレッサでは、部分的なストリングＷおよび文字Ｃが出現すると、Ｐが最後に送信された出力圧縮コードで送られたストリングであった場合、新しいストリングは、拡張文字とするＣと共にストリングＰＷに記憶される。この圧縮アルゴリズムによって、文字のランはその長さに係わらず２つの圧縮されたコードに符号化される。このシステムのデコンプレッサは、コンプレッサとの同期を維持するために特別な未確認コード方法を使用する。
【０００７】
本発明の目的は、ランレングス符号化を使用する別のデータ圧縮の実施形態を提供することにある。
【０００８】
（発明の概要）
本発明のコンプレッサは、数値的に増加するデータ文字のランの隣接セグメントに対応する数値的に増加する出力コードのシーケンスを生成する。相互に異なる連続する文字は、コンプレッサのコードカウンタの増分と同期して、直接的に送信される。
【０００９】
（好ましい実施形態の説明）
図１を参照すると、データコンプレッサ１０は、入力部１１に適用された入力データ文字のストリームを、対応する出力部１２の圧縮されたコードのストリームに圧縮することが示されている。コンプレッサ１０には、カレント文字レジスタ１３（以下、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３という）、先読みバッファ１４（以下、Ｌｏｏｋ−Ａｈｅａｄバッファという）、ｎレジスタ１５、およびコードサイズレジスタ１６と示される作業レジスタが含まれる。コンプレッサ１０には、さらに、後述する方式でランセグメントおよび非ラン文字を処理するために使用されるコード値を後で生成するためのコードカウンタ１７も含まれる。
【００１０】
コンプレッサ１０は、さらに、先読み比較および文字破棄論理２０を含む。論理２０は、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の文字とＬｏｏｋ−Ａｈｅａｄバッファ１４の文字の間で比較を実行し、後述する方式で先読み文字（以下、Ｌｏｏｋ−Ａｈｅａｄ文字という）を破棄する。コンプレッサ１０はまた、後述する方式で、図２の操作フローチャートに従ってコンプレッサの動作を制御するための制御部２１も含む。
【００１１】
入力部１１で受け取った入力データ文字ストリームをバッファする入力文字バッファ２２も含まれる。個々の入力データ文字は、後述する操作に従って入力文字バッファ２２からバス２３を介してＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３およびＬｏｏｋ−Ａｈｅａｄバッファ１４に適用される。コンプレッサ１０は、コントロールバス２４を介する入力文字バッファ２２からの入力データ文字の獲得を制御する。
【００１２】
コンプレッサ１０の動作を簡単に以下に示す。論理２０がＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒと次の２つの先読み文字との間で比較を実行することを可能にしながら、入力データ文字が入力文字バッファ２２からＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３およびＬｏｏｋ−Ａｈｅａｄバッファ１４にフェッチされる。この３つの文字が同じ場合はラン処理が実行される。同じでない場合、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３にある文字は出力され、次に続くＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒの次の文字がＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３にフェッチされる。
【００１３】
文字ランが検出されると、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３に常駐しそのランを開始する文字と、コードカウンタ１７のコードが出力される。コードカウンタ１７は次いで１つ増分される。次いで、そのランに数値的に増加しているランセグメントが存在するかどうかを判定するために、そのランが調べられる。具体的には、３つの文字、４つの文字、５つの文字、６つの文字等々の隣接するランセグメントが、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の文字に従い一致する、２つの先読み文字に続くランの中に存在するかどうかが判定される。そのような各検出されたランセグメントに対してコードカウンタ１７の中のコードが出力され、コードカウンタ１７が１つ増分される。このプロセスは、ランに不十分な文字しか残留しなくなるまで、シーケンスの次のランセグメントを構成するように続けられる。これが発生すると、コードカウンタ１７は再度１つ進められる。
【００１４】
Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３、Ｌｏｏｋ−Ａｈｅａｄバッファ１４、ｎレジスタ１５および論理２０は、図２を参照しながら後述するような文字ラン処理を実行する際に使用される。
【００１５】
図１から引き続き図２を参照すると、本発明に従ってデータ圧縮を実行するためにコンプレッサ１０が実行する詳細な動作を示す制御フローチャートが示される。制御部２１は、動作の実行を制御するための状態機械などの適切な回路を含むものと想定される。
【００１６】
図２のフローチャートは可変長出力に基づいており、コードサイズレジスタ１６は可変長出力のために使用される。周知のように、例えば８ビットのアルファベットを有するＡＳＣＩＩの実施において、コードサイズは９ビットから始まり、引き続き、それぞれコード５１２、１０２４、２０４８等々で１０、１１、１２、等々ビットに増加する。
【００１７】
したがって、ブロック３０で、コードカウンタ１７は、例えばＡＳＣＩＩ環境の２５８などの第１の使用可能なコードに初期化される。ブロック３１で、コードサイズレジスタ１６は、例えばＡＳＣＩＩ環境の９ビットなどの開始コードサイズに初期化される。
【００１８】
ブロック３２で、第１の入力文字はＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３にフェッチされ、ブロック３３で、ｎレジスタ１５は２にセットされる。ブロック３４で、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の文字が出力部１２に提供される。この文字は、すでに出力済みであってもＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３に依然として常駐していることが理解されよう。
【００１９】
ブロック３５で処理が続行され、レジスタ１３のＣｕｒｒｅｎｔ  ＣｈａｒａｃｔｅｒがＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒに続く次のｎ個の先読み文字に対してテストされ、それらが同じかどうかが判定される。このプロセスは、Ｌｏｏｋ−Ａｈｅａｄバッファ１４にフェッチされる適切な文字を使用して論理２０によって実行される。「ｎ」が２にセットされているので、ブロック３５はＣｕｒｒｅｎｔ  ＣｈａｒａｃｔｅｒをＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒに続く次の２個の先読み文字と比較する。
【００２０】
ブロック３５では、同じ文字のランが間もなく開始されるかどうかが判定されることが理解されよう。Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒが次の２つの先読み文字と同じ場合、ラン処理はブロック３５でＹＥＳの分岐を選ぶことで開始される。２つの先読み文字のうちの１つがＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒと一致しない場合、非ラン処理を実行するためにブロック３５のＮＯの分岐が選ばれる。
【００２１】
図２の論理において、ブロック３５で文字ランが間もなく行われると判定される場合（ＹＥＳ分岐）、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の文字が出力されるべきであることが理解できる。同様に、ブロック３５が、ランがすぐには行われないと判定する場合（ＮＯ分岐）でも、現在の文字が出力されるべきである。選ばれる分岐に係わらず現在の文字は出力されるので、節約のため、ブロック３４はブロック３５の判定より前にアクションを実行する。
【００２２】
ブロック３５から非ラン処理のＮＯ分岐が選ばれる場合、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒはすでにブロック３４で出力済みである。ブロック３６で、コードサイズの増加が必要とされるかどうかを判定するためにコードカウンタ１７のコードがテストされる。必要とされる場合、処理はブロック３７に進み、そこでコードサイズレジスタ１６は１つ増分される。コードサイズの増加が必要とされない場合、ブロック３８で処理を続行するためにブロック３７はバイパスされる。ブロック３８では、ブロック３４でのＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒの出力と同期してコードカウンタ１７が１つ増分される。
【００２３】
処理はブロック３９で続行され、そこでＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒに続く文字がＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３にフェッチされる。次いで制御がブロック３４に戻り、そこで入力データの処理が続行される。
【００２４】
ブロック３５の判定で同じ文字のランが開始されることが示される場合、ブロック５０に向けてＹＥＳの分岐が選ばれる。ブロック５０では、コードカウンタ１７のコードがコンプレッサ１０の出力部１２で提供される。制御フローのこの時点で、潜在的なランの最初の３文字はすでに処理済である。ランの最初の文字はＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の中にあり、ブロック３４ですでに出力済みである。ブロック５０で出力されるコードカウンタ１７のコードは、ブロック３５で使用される２つの先読み文字を表わしている。この２つの文字は、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒに続くランの第１のセグメントである。ブロック５１および５２では、ブロック３６および３７に関して前述したコードサイズ論理が実行される。
【００２５】
ブロック５３では、コードカウンタ１７は、そのランの次のセグメントが行われるべき場合は、その処理に備えてコードカウンタ１７を１つ増分する。ブロック５４では、次いで、処理済みのｎ個の先読み文字が破棄される。この破棄が行われるのは、それらの文字を表わすコードがブロック５０で出力済みだからである。文字の破棄は、適切な文字のＬｏｏｋ−Ａｈｅａｄバッファ１４をクリアすることによって論理２０によって実行される。
【００２６】
処理はブロック５５で続行し、そこでインデックスｎがｎ＋１に進められる。このアクションは、ｎレジスタ１５に関して実行される。したがって処理のこの時点では、次の３つの先読み文字が次の数値的に増分されたランセグメントにランを続けるかどうかの判定に備えて、以前２にセットされたｎが次に３に進められる。
【００２７】
したがって、ブロック５４で破棄された文字に続く次のｎ個の先読み文字に対してＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の中の文字をテストする判断ブロック５６に入る。このプロセスは、Ｌｏｏｋ−Ａｈｅａｄバッファ１４にフェッチされた適切な文字を使用して、論理２０によって実行される。すべてのｎ個の先読み文字がＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒと一致する場合、ＹＥＳの分岐が選ばれる。一致しない場合は、ＮＯの分岐が選ばれる。
【００２８】
ブロック５６からＹＥＳの分岐が選ばれた場合、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の中の文字のランは、次のこのｎ個の文字セグメントに継続される。制御は次いでブロック５０に戻り、前述のような処理を続行する。端的に言えば、ブロック５０は、ブロック５４で破棄されたこのｎ個の文字ランセグメントを表わすコードを出力する。コードカウンタ１７は、再度ブロック５３に進められる。インデックスｎは、もう１つの隣接する数値的に増分したランセグメントが入力部に存在するかどうかをさらに判定するために文字ランを調査するようにブロック５５で進められる。
【００２９】
ブロック５６で、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の文字と同じ不十分な入力文字が、次のランセグメントを構成するように存在すると判定された場合、ブロック５６からＮＯの分岐が選ばれる。ブロック３６および３７に関して前述したコードサイズテストが、次いでブロック５７および５８で実施される。ブロック５９で、コードカウンタ１７が１つ増分される。ブロック６０では、処理を続行するために、論理２０の制御下で、ブロック５４で破棄された文字に続く次の文字がＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３にフェッチされる。したがって、制御は次いでブロック３３に戻る。
【００３０】
ブロック５６からＮＯの分岐が選ばれたときは、ブロック５６のテストを実行するために使用されるｎ個の先読み文字がＬｏｏｋ−Ａｈｅａｄバッファ１４にあることが理解できる。これらの文字は、ブロック６０でＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒとして使用中の文字の最初の文字の処理を続行するために使用される。Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒに続いてＬｏｏｋ−Ａｈｅａｄバッファ１４に記憶されている文字は、次いでブロック３５で必要とされるＬｏｏｋ−Ａｈｅａｄ文字として使用することができる。論理２０は、図２のそれらおよびその他のアクションが、必要に応じて文字を使用し、フェッチし、破棄することによって適切に実行されるように、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３およびＬｏｏｋ−Ａｈｅａｄバッファ１４を制御する。
【００３１】
端的に言えば、判断ブロック３５はランの出現を検出し、そのランはブロック５０〜５６で処理されることが理解できる。非ランデータの処理がブロック３６〜３９によって実行される。不十分な文字がランの次のセグメントを構成するために残留するとき、ブロック５７〜６０は次に続く処理を実行する。
【００３２】
図１および図２に引き続き図３を参照すると、図２のフローチャートに従うコンプレッサ１０の動作の一例が示されている。頁の最上部に入力データストリームが示され、そこでは各文字ランの文字が文字のシーケンス番号によって識別される。これは、この例のステップを通して文字の進展について行くことを容易にするために行われる。これらのシーケンス番号は、文字を識別するために示されるのであって、実際の入力データ文字ストリームには現れないことが理解できる。
【００３３】
この例は、左側の欄に記載の実行されるアクションと右側の欄に示されたアクションに関係する図２のブロックがあるので、概ね説明を要しない。
【００３４】
例えばアクション２では、コードカウンタの中のコード２５８はブロック５０で出力され、コードサイズはブロック５１および５２でテストされ、コードカウンタがブロック５３で２５９に増分され、先読み文字「ａ（２）」および「ａ（３）」がブロック５４で破棄される。同様にアクション３では、ｎレジスタがブロック５５で３に増分され、次の３つの先読み文字、「ａ（４）」、「ａ（５）」、「ａ（６）」がブロック５６で調べられ、コード２５９を出力するために制御がブロック５０に戻り、コードカウンタがブロック５３で２６０に増分され、３つの先読み文字がブロック５４で破棄される。別の例として、アクション１０では、コードサイズがブロック３６および３７でテストされ、コードカウンタがブロック３８で２６５に増分される。次の文字「ｘ」がブロック３９でＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタにフェッチされ、ブロック３４で出力される。次の先読み文字「ｙｚ」がブロック３５でテストされる。
【００３５】
図３は、図２に関連したものであり、その内容は容易に理解できるため、その説明は簡略化する。
【００３６】
図１の参照に続いて図４を参照すると、本発明の好ましい代替実施形態の概略図が示されている。図４に、図１に関して前述した構成要素と同様の、図１と同じ参照番号を与えられた多数の構成要素を有するデータコンプレッサ７０を示す。図１に関してなされた前述の説明は、図４にも適用可能である。
【００３７】
コンプレッサ７０は、図１のＬｏｏｋ−Ａｈｅａｄバッファ１４と類似のＬｏｏｋ−Ａｈｅａｄバッファ７１を含む。図６に関して後述する図４のコンプレッサ７０では、そのための追加の機能性が必要とされる。コンプレッサ７０は、また、図１の論理２０に類似の、先読み比較および文字破棄論理７２も含む。図６に関して後述するコンプレッサ７０では、そのための追加の機能性が必要とされる。
【００３８】
コンプレッサ７０は、図６に関して後述する方式で、コンプレッサ７０の動作中に使用される変数を保持するための、Ｍレジスタ７３およびＲレジスタ７４と呼ばれる作業レジスタをさらに含む。コンプレッサ７０は、後述する方式で図６の動作フローチャートに従ってコンプレッサの動作を制御するための制御部７５も含む。
【００３９】
図１のコンプレッサ１０と異なり、コンプレッサ７０は、ランセグメント数およびランセグメントコードを記憶し、かつ後述する方式で第１エンカウンタ（ｅｎｃｏｕｎｔｅｒ）フラグを提供するためのテーブルおよびフラグ８０を含む。テーブルおよびフラグ８０とのデータ通信は双方向バス８１を介して実施される。データ転送の制御は双方向制御バス８２によって実施される。テーブルおよびフラグ８０の詳細を図５に示す。
【００４０】
図５を参照すると、テーブルおよびフラグ８０は、圧縮が実行されるアルファベット文字のそれぞれに対するランセグメントテーブル８５および第１エンカウンタフラグ８６を含む。例えば「文字１」に対するランセグメントテーブル８５は、データ文字入力で遭遇した文字１のランのランセグメントの数（図中、カウント値）およびコードを記憶する。当初、すべての第１エンカウンタフラグ８６がセットされている。「文字１」のランに始めて遭遇すると、「文字１」に対する第１エンカウンタフラグ８６はリセットされる。図５のテーブルおよびフラグ８０の使用に関する詳細は、図６を参照して後述する。
【００４１】
端的に言って、コンプレッサ７０の動作は以下の通りである。コンプレッサ７０ではランセグメントが処理されているときにランセグメントデータがテーブル８５に記憶されていることを除いて、コンプレッサ７０は、全般的にコンプレッサ１０に関して前述した方式で動作する。同じ文字のランに後で遭遇すると、記憶されたデータは圧縮を強化するために使用される。
【００４２】
動作におけるこのような違いにより、コンプレッサ７０のラン検出論理は、コンプレッサ１０のラン検出論理と若干異なった動作をする。コンプレッサ７０では、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒが次に続く文字と同じでない場合、コンプレッサ１０の非ラン動作と同様の方式で、後で非ランの処理が実行される。次の文字がＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒと同じ場合、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒ用の第１エンカウンタフラグがテストされる。コンプレッサ１０が、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒのランに初めて遭遇する場合、ランセグメントデータの記憶を除いて、コンプレッサ１０と同じラン処理が実施される。この場合、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒおよび次の２つの文字は同じことになる。しかし、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒのこの遭遇したランが、そのような第１のランでない場合、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒ用のランセグメントテーブル８５がランを処理する際に参照される。
【００４３】
図６に関して後述するように、文字ランの処理を実行する際は、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３、Ｌｏｏｋ−Ａｈｅａｄバッファ７１、ｎレジスタ１５、Ｍレジスタ７３、Ｒレジスタ７４および論理７２が使用される。
【００４４】
図４および５に続いて図６を参照すると、コンプレッサ７０が実行するべき詳細な動作を示す制御フローチャートが示される。制御部７５は、動作の実行を制御するための適切な回路を含むものと想定する。図２に関して前述した方式では、図６のフローチャートは可変長出力に基づいている。図６のブロックの多くは図２のブロックと同様であり、同じ参照番号によって示される。図２のそれらのブロックに関して上記でなされた説明は、同様の参照番号を付した図６のブロックにも適用可能である。図６のブロックで図２のブロックと異なるブロックだけを、以下の図６の説明に特記する。
【００４５】
図６のブロック３０〜３２では、コードカウンタ１７およびコードサイズレジスタ１６が初期化され、第１の文字がＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３にフェッチされる。ブロック９０で、すべての第１エンカウンタフラグ８６が、文字のランへの初めての遭遇に備えてセットされる。
【００４６】
ブロック９１で処理が続行し、そこでＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の中の文字が、次に続く文字と同じかどうかを判定するために比較される。Ｌｏｏｋ−Ａｈｅａｄバッファ７１および論理７２はこの機能を実行するために使用される。それらの文字が同じでない場合、非ラン処理を実行するためにブロック９１からＮＯの分岐が選ばれる。２つの文字が同じ場合、ブロック９１からブロック９２に向けてＹＥＳの分岐が選ばれ、そこでＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の中の文字用第１エンカウンタフラグ８６の状況がテストされる。第１エンカウンタフラグがリセット済みの場合、この文字のランにはすでに遭遇しており、そのランのデータはその文字のためのランセグメントテーブル８５に記憶済みであるＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒのランの処理を実行するために、ブロック９２からＹＥＳの分岐が選ばれる。
【００４７】
Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒ用の第１エンカウンタフラグ８６が依然としてセットされている場合、ブロック９２からブロック３３に向けてＮＯの分岐が選ばれ、ブロック３３でｎが２にセットされる。処理はブロック３３からブロック３５に続き、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒが次のｎ個の先読み文字と同じかどうかが判定される。ブロック３３でｎが２にセットされているので、ブロック３５ではＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒと次の２つの文字が同じかどうかを判定する。Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒ用の第１エンカウンタフラグが依然としてセットされているので、この文字用のランのデータはまだ記憶されていない。この状況下でブロック３５からＹＥＳの分岐が選ばれる場合、図２のラン処理に類似したラン処理が実行される。ブロック３５からＮＯの分岐が選ばれる場合、非ラン処理が実行される。
【００４８】
したがって、ブロック３３、３５、９１および９２は、以下の方式でランを検出するように機能することが理解できる。Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒが次の文字と異なる場合は非ラン処理が実行される。Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒが次の文字と同じであり、この文字用のランが既に処理済みである場合、以前に記憶したデータを使用してランの処理が実行される。その文字のランがまだ遭遇も処理もされていない場合、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒが次の２つの文字と同じならばラン処理が実行され、同じでないならば非ラン処理が実行される。
【００４９】
ブロック３５またはブロック９１からＮＯの分岐が選ばれる場合、非ラン処理が実行される。ブロック９３で、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の中の文字が出力される。その後、ブロック３６〜３９の非ラン処理が、図２に関して前述した方式で実行される。ブロック３９の後、処理はブロック９１に戻る。
【００５０】
Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒの３文字のランが初めて検出されると、ブロック３５からＹＥＳの分岐が選ばれる。ブロック９４と９５で処理が続行し、そこでそれぞれにＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒ用の第１エンカウンタフラグはリセットされ、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の中の文字は出力される。制御は次いで、概して図２のブロック５０〜５６に関して前述した方式で、ランのセグメントを処理するためのループに入る。
【００５１】
したがって図６の処理はブロック５０を続行し、そこでコードカウンタ１７の中のコードを出力する。その後ブロック９６に入り、そこでコードカウンタ１７からのコードとｎに等しいカウントとがＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒ用のランセグメントテーブル８５に記憶される。ブロック９６の後、ブロック５１〜５５は、同様の参照番号を付した図２のブロックに関して前述した方式で処理を実行する。例えばブロック５４と５５ではｎ個の先読み文字が破棄され、ｎはｎ＋１に進められる。
【００５２】
ブロック９７で、論理７２は、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒが、１つまたは複数の破棄された文字、例えばブロック５４で破棄された文字に続く次のｎ個の先読み文字と同じかどうかを判定するためにテストする。処理がブロック５５からブロック９７に入る場合、常に複数の文字がブロック５４で破棄済みになっていることになる。図２のブロック５６で常に複数の文字が破棄済みになっていることを除いて、ブロック９７の機能は図２のブロック５６の機能と事実上同じであることが理解できる。以下で明らかになる理由のため、処理がブロック１３２からブロック９７に入る時に、ブロック９７で単一の文字しか破棄済みになっていない可能性がある。したがって、ブロック９７には図２の匹敵するブロック５６の参照番号と異なる参照番号が与えられている。図２のブロック５６に関して前述した方式で、ＹＥＳの分岐はブロック９７からループしてブロック５０に戻り、ランの処理を続行する。
【００５３】
図６のブロック５０〜５５、９６および９７は、図２のブロック５０〜５６と事実上同じ処理を実行することが理解できる。図２の実施形態と図６の実施形態の間の主な相違点は、図２ではランのデータが記憶されていないが、図６ではランのデータが記憶されているということである。したがって図６では、図２と６の両方に表示されているブロック５０と５１の間の処理フローに、記憶を実施するブロック９６が挿入されることが理解されよう。
【００５４】
図５とそれに続く図６を参照すると、図６のブロック５０〜５５、９６および９７の動作は、図５に示すような「文字１」のランで例示することができる。「文字１」はＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の中にあり、「文字１」の３文字のランの第１の遭遇である。ブロック５０〜５５、９６および９７を含む図６のループを連続して反復することにより、コード２５８〜２６７で「文字１」のためのランセグメントテーブル８５の項目が生じる。したがって、ブロック５５でｎが進められ、「文字１」のランの数値的に増加するセグメントがテーブル８５に示すような記憶されたランセグメントデータと遭遇することが理解されよう。前記のように、ランの各セグメントを表わすコードがブロック５０で出力される。
【００５５】
したがって、後述するように「文字１」のこの例示的なランは、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の中のＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒから構成されており、コード２５８によって表わされる２つの文字のランセグメント、コード２５９によって表わされる３つの文字のランセグメント等々、コード２６７によって表わされる１１の文字のセグメントまでその後にセグメントが続く。したがって、このランは６６と７７との間の文字からなる。
【００５６】
引き続き図６を参照すると、ブロック９７で、次のセグメントを構成するために不十分な文字がランに残留する場合、ブロック９７からＮＯの分岐が選ばれる。ブロック５７〜５９および１００で処理が続く。ブロック５７〜５９は、前述のように図２で同様の参照番号を付したブロックと同じであり、ブロック１００は図２のブロック６０と事実上同じである。ブロック９７に関して前述した理由により、ブロック１００に対しては新しい参照番号が使用される。
【００５７】
破棄した１つまたは複数の文字に続く次の文字がＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３にフェッチされた後、入力データ文字ストリームの処理を続行するために制御はブロック９１に戻る。
【００５８】
ブロック９１で２文字のランと遭遇し、その文字用の第１エンカウンタフラグがリセット済みの時、ブロック９２から、その文字に対する以前のランのデータが記憶されているブロック１１０に向けてＹＥＳの分岐が選ばれ、文字のランのラン処理が開始される。パラメータＲは、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒに続く、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒと同じ連続的な文字の数プラス１にセットされる。したがってＲは、遭遇したばかりのＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒのランの文字数に等しいことが理解されよう。Ｒの値がＲレジスタ７４で保持されているブロック１１０の機能を実施する際は、Ｌｏｏｋ−Ａｈｅａｄバッファ７１および論理７２が使用される。
【００５９】
処理はブロック１１１に続行し、そこでパラメータＭはＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の中の文字用ランセグメントテーブルで最大値カウントにセットされる。Ｍは、この最大カウントＭを判定するために、テーブルの下部までスクロールすることによって図５の適切なランセグメントテーブル８５から判定される。Ｍは次いでＭレジスタ７３に保持される。
【００６０】
処理はブロック１１２で続行され、そこでＲレジスタ７４の値がＭレジスタ７３の値と比較される。ＲがＭよりも大きな場合はブロック１１２からＹＥＳの分岐が選ばれ、ＲがＭ以下の場合はブロック１１２からＮＯの分岐が選ばれる。ＹＥＳの分岐が選ばれる場合、現在遭遇中のＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒのランは関連するランセグメントテーブル８５に記憶されている最大ランセグメントよりも大きい。ＮＯの分岐が選ばれる場合、現在遭遇中のＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒのランは関連するランセグメントテーブルに記憶されている最大ランセグメント以下である。
【００６１】
ブロック１１２からＮＯの分岐が選ばれる場合、処理はブロック１１３で続行し、そこでカウントのための関連するランセグメントテーブルからＲに等しいコードがコンプレッサ７０によって出力される。Ｒレジスタ７４の値を関連するランセグメントテーブルのカウントと関連付けによって比較することにより、ブロック１１３の機能が実行される。Ｒがテーブルの中に位置する時、それに対応するコードはすでに位置付けられており、そのコードが出力される。あるいはカウントがＲに等しい場合、適切な記憶位置を発見するために、テーブルに記憶されたカウントを通して単純な順序付けを使用することができる。
【００６２】
処理は次いでブロック１１４と１１５に進み、そこでブロック３６と３７に関して前述した方式でコードサイズがテストされ、調整される。
【００６３】
ブロック１１６でコンプレッサ７０のコードカウンタ１７が１つ増分され、ブロック１１７でＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒに続くＲ−１の１つまたは複数の文字が破棄される。Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の文字と共に破棄されたそれらの文字は、ブロック１１３で出力されるコードによって表わされる。それらの文字の破棄は、論理７２の制御下においてＬｏｏｋ−Ａｈｅａｄバッファ７１を使用して実行される。
【００６４】
ブロック１１８で、ブロック１１７で破棄された１つまたは複数の文字に続く文字がＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１１３にフェッチされる。この機能は、論理７２の制御下においてＬｏｏｋ−Ａｈｅａｄバッファ７１によって実行される。その後、制御はブロック９１に戻り、入力データ文字ストリームの処理を続行する。
【００６５】
Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒの現在遭遇中のランが、関連するランセグメントテーブル８５に記憶されている最長ランセグメントよりも長い場合、ブロック１１２からＹＥＳの分岐が選ばれる。処理はブロック１３０で続行し、そこで関連するランセグメントテーブルからＭに対応するコードが出力される。ＭはＭレジスタ７３に記憶されている値である。関連するランセグメントテーブルは、例えばＭのカウントに対応するコードを関連付けまたはスキャニングによって捜し出し、出力するために、Ｍのこの値を使用してアクセスされる。
【００６６】
処理はブロック１３１で続行し、そこでＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒに続く１つまたは複数のＭ−１文字が破棄される。この破棄の操作は、ブロック５４および１１７などのブロックに関して前述した方式で達成される。ブロック１３１でＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒレジスタ１３の中の文字と共に破棄されたＭ−１文字は、Ｃｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒのランの現在遭遇中のセグメントを含む。それらのＭ文字を表わすコードはブロック１３０で出力されている。
【００６７】
残りのランは、ブロック１３２でｎをＭ＋１にセットすることによって処理される。ブロック１３２の機能は、レジスタ７３の中のＭの値を１つ増分し、この値をｎレジスタ１５に転送することによって実行される。次いで制御はブロック９７に移り、前述のようにランの処理を続行する。
【００６８】
引き続き図６を参照すると、ブロック９３は非ラン処理への入口であり、ブロック９４は文字の最初に遭遇したランの処理への入口であることが理解されよう。ブロック１１０は文字のランの処理への入口であり、そこではその文字の前のランが既に処理され、記憶されている。そのようなランにとって、ブロック１１２は、記憶されている最大ランセグメントよりも大きなランの処理と、記憶されている最大ランセグメント以下のランの処理との分岐点である。
【００６９】
図４〜６の実施形態については図６のブロック９１、９２、３３および３５からなるラン検出論理に関して説明した。代わりに、図２のブロック３３〜３５からなる図１および２の実施形態のラン検出論理を図６で使用することもできることが理解されよう。そのような実施形態では、記憶された長さ２のランセグメントはランセグメントテーブル８５でアクセスされないことになる。この代替構成では、ブロック３３と３５が、ブロック３５に続くブロック９２と共に使用されることになる。次いでブロック９２のＮＯの分岐はブロック９４に至ることになる。ブロック９２のＹＥＳの分岐は、現在説明しているようにブロック１１０に至ることになる。
【００７０】
図４〜６に引き続き図７を参照すると、図６のフローチャートに基づくコンプレッサ７０の動作の一例が示されている。図７のフォーマットは図３のフォーマットと同じであり図３に関してなされた前述の説明が適用可能である。図７は、ランセグメントテーブルに記憶され、後続ランの処理に使用されるランセグメントデータを説明し、パラメータＲおよびＭならびに第１エンカウンタフラグのセットとリセットを示している点で図３と異なる。
【００７１】
具体的には、図７ではランセグメントテーブルにランセグメントデータが記憶されており、第１エンカウンタフラグのセットおよびリセットを説明している点を除いて、図７のアクション１〜６は図３のアクション１〜５と事実上同じである。
【００７２】
同様に、図３では２つの先読み文字を基準に判断が行われるのに対して図７では１つの先読み文字を基準に非ラン判断が行われる点を除いて、図７のアクション９〜１２の非ラン処理は図３のアクション９〜１２と事実上同じである。
【００７３】
図７のアクション１３は、文字「ａ」のランの第２遭遇の検出を示している。このランは「ａ（１３）」から「ａ（２１）」までの文字として示されており、したがって９個の文字から構成される。文字「ａ」のランの最大セグメントは、ランセグメンのカウントを４としてアクション５で記憶されている。アクション１４では、記憶されたセグメントに関するコード２６０が出力され、「ａ（１４）」から「ａ（１６）」までの４個の文字が破棄される。アクション１５では、「ａ（１７）」から「ａ（２１）」までの文字を吸収するのに備えてインデックスｎが５にセットされる。アクション１６では、説明したように、それらの文字を表わすコード２６７が出力され、その文字が破棄され、このランセグメントはランセグメントテーブルに記憶される。
【００７４】
図７の右側の欄に示すような図７のアクションと図６のブロックとの相関関係は、図３に関して前述した説明に類似しており、図７の特定例と図６のブロックの機能性とを比較することによって容易に明らかになろう。
【００７５】
コンプレッサ１０または７０の圧縮された出力に対応する入力データ文字を回復するためにコンプレッサ１０または７０と同期して動作して、その圧縮された出力を受け取る互換性のあるデコンプレッサが容易に実現できることが理解されよう。
【００７６】
図３および７の「出力」欄に示した出力コードのシーケンスがデコンプレッサによって処理される場合、図面で示した入力データ文字ストリームは回復される。デコンプレッサのプロトコルはコンプレッサのプロトコルと互換性があることが理解されよう。図３および７の例では、８ビットでサポートされるＡＳＣＩＩアルファベットを想定している。ＡＳＣＩＩアルファベットは２５６文字で構成される。コードカウンタ１７は、図２および６のブロック３０で２５８のコードに初期化される。例えばコード２５７は、当技術分野でよく知られているように制御コードとして予約することができる。デコンプレッサは、コードカウンタ初期値およびコードの初期サイズなどの、コンプレッサと同じアルファベットサイズおよび初期状態を有するべきである。さらに当技術分野でよく知られているように、本発明によるコンプレッサの実施形態のコードサイズとデコンプレッサのコードサイズは、例えば図２に関して前述したように相互に同期して進められるべきである。
【００７７】
よく知られているように、コンプレッサとデコンプレッサはどちらもすべての単一文字ストリングで初期化するか、それとも単一文字をそれぞれの値によって圧縮コードから識別することができる。ＡＳＣＩＩ文字は２５６以下の値を有するが、図３および７のＡＳＣＩＩの例では、圧縮されたコードは２５８以上の値を有する。他の単一文字コードのプロトコルも使用できることはさらによく知られている。
【００７８】
本発明によるコンプレッサの実施形態で使用される単一文字コードのプロトコルは、デコンプレッサでも使用されるべきである。
【００７９】
コードカウンタ１７は、ラン処理と非ラン処理の間で同期を維持するために前述のように増分されることが理解されよう。これは具体的には前述の図面のブロック３８、５３、５９および１１６で見られる。例えばコードカウンタ１７は、ブロック３４のＣｕｒｒｅｎｔ  Ｃｈａｒａｃｔｅｒの出力との同期を維持するために、ブロック３８で１つ増分される。
【００８０】
前記実施形態は、入力データ文字のストリームを圧縮する。入力データ文字は、対応する任意の文字ビットサイズを有して、いかなるサイズのアルファベットも超えることができる。例えばデータ文字は、８ビット文字の２５６文字のＡＳＣＩＩアルファベットのように、アルファベットを超えるＡＳＣＩＩ文字などのテキスト形式であってよい。入力データは、１ビットサイズの文字を有して、２つの文字のバイナリアルファベット１および０を超えてもよい。テキスト形式のデータは、基礎となるバイナリデータの２文字のアルファベットに亘って圧縮することもできることが理解されよう。
【００８１】
本発明の前記実施形態は、ハードウェア、ファームウェア、ソフトウェアまたはそれらの組合わせで実施することができることが理解されよう。前述の様々な機能を実行するために、個別の回路部品を容易に使用することができる。ソフトウェアの実施形態では、前述のフローチャートから容易に生成される符号化を用いてプログラムされる適切なモジュールを使用することができる。
【００８２】
本発明は好ましい実施形態によって説明したが、使用した用語は限定するためではなく説明するための用語であり、より広範な態様において本発明の範囲および趣旨を逸脱することなく頭書の特許請求の範囲内で変更を行うことができることが理解されよう。
【図面の簡単な説明】
【図１】  本発明の好ましい実施形態を実現するデータコンプレッサの概略的ブロック図である。
【図２】  図１のコンプレッサが本発明によるデータ圧縮を実施するために実行する動作を示す制御フローチャートである。図１および図２の実施形態は、文字ランが遭遇されるたびに改めて処理される非記憶構成である。
【図３】  図２の制御フローチャートに従って図１のコンプレッサの動作を例示するチャートである。
【図４】  本発明のもう１つの好ましい実施形態を実現するデータコンプレッサの概略的ブロック図である。
【図５】  図４のテーブルおよびフラグの詳細を示すデータ構造図である。
【図６】  図４および５のコンプレッサが本発明によるデータ圧縮を実行するために実行する動作を示す、図６Ａおよび６Ｂからなる制御フローチャートである。図４〜６の実施形態は、文字ランに再度遭遇した時にその文字ランデータを再使用することができるように、ストレージを使用してその文字ランデータを保存する。
【図７】  図６の制御フローチャートに従って図４および５のコンプレッサの動作を例示する図である。
【図１】
0003653226.tif 000002
【図２】
0003653226.tif 000003
【図３】
0003653226.tif 000004
【図４】
0003653226.tif 000005
【図５】
0003653226.tif 000006
【図６】
0003653226.tif 000007
0003653226.tif 000008
【図７】
0003653226.tif 000009