(57)【特許請求の範囲】
【請求項１】
データ部分の入力シーケンスを圧縮する方法であって、
前記入力シーケンスを部分毎に順次トラバースして、各部分で開始する少なくとも所定の最小部分数である部分の第１の最長シーケンスが、先にトラバースされた部分の第２のシーケンスと整合するかどうかを判定するステップと、
前記第１のシーケンスが整合する場合、前記第１のシーケンスの長さおよび前記第１のシーケンスと整合する第２のシーケンスとの間のオフセットを示すステップと、
前記データ部分の少なくとも１つの非整合シーケンスのストリームを順次記録するステップと、
前記ストリームとは別個の順序付きコードワードシーケンスを生成するステップであって、該コードワードはそれぞれ、整合する第１のシーケンスに先行する非整合シーケンスの長さ、前記関連するオフセット、および前記整合する第１のシーケンスの長さを示す３つのデータアイテムを含む生成するステップと
を含み、
前記コードワードはバイト配列していなく、前記データアイテムはそれぞれ、バイト配列していない可変ビット長のものであり、
前記データアイテムは、
データアイテムを２ｍで割った余りを表すｍビットと、
前記ｍビットの前に付けられる少なくとも１つのデリミタビットと、
データアイテムが２ｍ−１よりも大きい場合、前記データアイテムを２ｍで割った商を表す、前記デリミタビットとは異なり、前記デリミタビットの前に付けられる前記少なくとも１つのビットと
を含むビットシーケンスで表される
方法。
【請求項２】
ある長さの１つの前記順序付きコードワードシーケンスおよびデータ部分の前記少なくとも１つの非整合シーケンスのストリームを生成するステップ
をさらに含む請求項１記載の方法。
【請求項３】
前記デリミタビットとは異なり、前記デリミタビットの前に付けられる少なくとも１つのビットは、１つまたは複数のビットを含み、該ビットはそれぞれ２ｍデータ部分を表す
請求項１記載の方法。
【請求項４】
データ部分の入力シーケンスを圧縮する方法であって、
前記入力シーケンスを部分毎に順次トラバースして、各部分で開始する少なくとも所定の最小部分数である部分の第１の最長シーケンスが、先にトラバースされた部分の第２のシーケンスと整合するかどうかを判定するステップと、
前記第１のシーケンスが整合する場合、前記第１のシーケンスの長さおよび前記第１のシーケンスと整合する第２のシーケンスとの間のオフセットを示すステップと、
前記データ部分の少なくとも１つの非整合シーケンスのストリームを順次記録するステップと、
前記ストリームとは別個の順序付きコードワードシーケンスを生成するステップであって、該コードワードはそれぞれ、整合する第１のシーケンスに先行する非整合シーケンスの長さ、前記関連するオフセット、および前記整合する第１のシーケンスの長さを示す３つのデータアイテムを含む生成するステップと
を含み、
前記コードワードはバイト配列していなく、前記データアイテムはそれぞれ、バイト配列していない可変ビット長のものであり、
前記コードワードそれぞれにおける前記データアイテムは、
前記データアイテムそれぞれを２ｍで割った余りそれぞれを表し、前記入力シーケンスの圧縮中に求められる第１、第２、および第３の余りビット数と、
前記第１、第２、および第３の余りビット数それぞれの前に付けられる少なくとも１つのデリミタビットと、
データアイテムが２ｍ−１よりも大きい場合、前記データアイテムを２ｍで割った商を表す、前記デリミタビットとは異なり、前記デリミタビットの前に付けられる少なくとも１つのビットと、を含むビットシーケンスで表され、
前記コードワードは、各コードワードにおける前記第１、第２、および第３の余りビット数を示す情報をさらに含む
方法。
【請求項５】
データ部分の入力シーケンスを圧縮する圧縮システムであって、
前記入力シーケンスを部分毎に順次トラバースして、各部分で開始する少なくとも所定の最小部分数である第１の最長シーケンス部分が、先にトラバースされた部分の第２のシーケンスと整合するかどうかを判定する手段と、
前記整合した第１のシーケンスの長さおよび前記第１のシーケンスと整合する第２のシーケンスとの間のオフセットを示す手段と、
前記データ部分の少なくとも１つの非整合シーケンスのストリームを順次記録する手段と、
前記ストリームとは別個の順序付きコードワードシーケンスを生成する手段であって、前記コードワードはそれぞれ、整合する第１のシーケンスに先行する非整合シーケンスの長さ、前記関連するオフセット、および前記整合する第１のシーケンスの長さを示す３つのデータアイテムを含む手段と
を備え、
前記コードワードはバイト配列していなく、前記データアイテムはそれぞれ、バイト配列していない可変ビット長のものであり、
前記データアイテムは、
データアイテムを２ｍで割った余りを表すｍビットと、
前記ｍビットの前に付けられる少なくとも１つのデリミタビットと、
データアイテムが２ｍ−１よりも大きい場合、前記データアイテムを２ｍで割った商を表す、前記デリミタビットとは異なり、前記デリミタビットの前に付けられる少なくとも１つのビットと
を含むビットシーケンスで表される
圧縮システム。
【請求項６】
ある長さの１つの前記順序付きコードワードシーケンスおよびデータ部分の前記少なくとも１つの非整合シーケンスのストリームを生成する手段
をさらに備える請求項５記載の圧縮システム。
【請求項７】
前記デリミタビットとは異なり、前記デリミタビットの前に付けられる前記少なくとも１つのビットは、１つまたは複数のビットを含み、該ビットはそれぞれ２ｍデータ部分を表す
請求項５記載の圧縮システム。
【請求項８】
データ部分の入力シーケンスを圧縮する圧縮システムであって、
前記入力シーケンスを部分毎に順次トラバースして、各部分で開始する少なくとも所定の最小部分数である第１の最長シーケンス部分が、先にトラバースされた部分の第２のシーケンスと整合するかどうかを判定する手段と、
前記整合した第１のシーケンスの長さおよび前記第１のシーケンスと整合する第２のシーケンスとの間のオフセットを示す手段と、
前記データ部分の少なくとも１つの非整合シーケンスのストリームを順次記録する手段と、
前記ストリームとは別個の順序付きコードワードシーケンスを生成する手段であって、前記コードワードはそれぞれ、整合する第１のシーケンスに先行する非整合シーケンスの長さ、前記関連するオフセット、および前記整合する第１のシーケンスの長さを示す３つのデータアイテムを含む手段と
を備え、
前記コードワードはバイト配列していなく、前記データアイテムはそれぞれ、バイト配列していない可変ビット長のものであり、
前記コードワードそれぞれにおける前記データアイテムは、
前記データアイテムそれぞれを２ｍで割った余りそれぞれを表し、前記入力シーケンスの圧縮中に求められる第１、第２、および第３の余りビット数と、
前記第１、第２、および第３の余りビット数それぞれの前に付けられる少なくとも１つのデリミタビットと、
データアイテムが２ｍ−１よりも大きい場合、前記データアイテムを２ｍで割った商を表す、前記デリミタビットとは異なり、前記デリミタビットの前に付けられる少なくとも１つのビットと、を含むビットシーケンスで表され、
前記コードワードは、各コードワードにおける前記第１、第２、および第３の余りビット数を示す情報をさらに含む
圧縮システム。
【請求項９】
計算装置読み取り可能なプログラム格納装置であって、前記プログラム格納装置は、データ部分の入力シーケンスを圧縮する方法を前記計算装置に実行させる命令プログラムを有形に具現し、
前記方法は、
前記入力シーケンスを部分毎に順次トラバースして、各部分で開始する少なくとも所定の最小部分数である第１の最長シーケンス部分が、先にトラバースされた部分の第２のシーケンスと整合するかどうかを判定するステップと、
前記第１のシーケンスが整合する場合、前記第１のシーケンスの長さおよび前記第１のシーケンスと整合する第２のシーケンスとの間のオフセットを示すステップと、
前記データ部分の少なくとも１つの非整合シーケンスのストリームを順次記録するステップと、
前記ストリームとは別個の順序付きコードワードシーケンスを生成するステップであって、前記コードワードはそれぞれ、整合する第１のシーケンスに先行する非整合シーケンスの長さ、関連するオフセット、および前記整合する第１のシーケンスの長さを示す３つのデータアイテムを含む生成するステップと
を含み、
前記コードワードはバイト配列していなく、前記データアイテムはそれぞれ、バイト配列していない可変ビット長のものであり、
前記データアイテムは、
データアイテムを２ｍで割った余りを表すｍビットと、
前記ｍビットの前に付けられる少なくとも１つのデリミタビットと、
データアイテムが２ｍ−１よりも大きい場合、前記データアイテムを２ｍで割った商を表す、前記デリミタビットとは異なり、前記デリミタビットの前に付けられる前記少なくとも１つのビットと
を含むビットシーケンスで表される
プログラム格納装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、本発明はデータ圧縮に関し、特に、Ｌｅｍｐｅｌ−Ｚｉｖ技法の変形を使用してデータシーケンスを圧縮するシステムおよび方法に関する。
【０００２】
【従来の技術】
データ圧縮技法は、格納または伝送すべきデータ量を低減して記憶容量および伝送時間それぞれを低減するために使用される。いずれの場合であっても、元データを再構築可能にするために、対応する解凍技法を提供する必要がある。
【０００３】
多くのデータ圧縮および解凍技法が知られているが、Ｌｅｍｐｅｌ−Ｚｉｖ（ＬＺ）技法およびその変形が最も普及している。
Welchによる「High Speed Data Compression and Decompression Apparatus and Method」と題する米国特許第４，５５８，３０２号、Waterworthによる「Data Compression System」と題する米国特許第４，７０１，７４５号、およびMiller他による「Data Compression Method」と題する米国特許第４，８１４，７４６号が、こういったＬＺ技法のいくつかを開示する特許である。
ＬＺ変形の１つは、ＬＺ  Ｏｂｅｒｈｕｍｅｒ（ＬＺＯ）技法として知られている。
図１は、ＬＺＯ技法を使用して入力文字シーケンスを圧縮することによって得られる出力コードストリームを示す。
出力コードストリームは、入力文字シーケンスからの非整合文字シーケンスで間が埋められたコードワードを含む。
コードワードは、出力コードワードを解凍するときに、先に現れた文字シーケンスを参照して、元の入力文字シーケンスをコードストリームから再構築することができる。
【０００４】
ＬＺＯ技法には改良の余地がある。
コードワードは、非整合文字シーケンスで間を埋められるため、バイト配列する必要がある。
コードワードが可変長である場合、デリミタも必要である。
コードワードをバイト配列する必要性およびデリミタの必要性により、結果としてＬＺＯ出力コードストリームに異質なビットが含まれることになる。
コードワードが固定長である場合、デリミタは必要ない。
しかし、このような固定長コードワードは、コードワード中のデータアイテムによって表現可能な値までの長さの文字シーケンスしか表すことができない。
【０００５】
【発明が解決しようとする課題】
したがって、本発明の目的は、データ部分の入力シーケンスを圧縮するシステムおよび方法を提供することである。
【０００６】
【課題を解決するための手段】
本発明の態様によれば、データ部分の入力シーケンスを圧縮する方法が提供される。
入力シーケンスを部分毎に順次トラバースして、各部分で開始する第１のシーケンス部分が先にトラバースされた第２のシーケンス部分と整合するかどうかを判定する。
第１のシーケンスが第２のシーケンスと整合する場合、第１のシーケンスの長さおよび第１のシーケンスと整合する第２のシーケンスとの間のオフセットを示す。
入力シーケンス中のデータ部分の少なくとも１つの非整合シーケンスのストリームを順次記録する。
ストリームとは別個に順序付けられたコードワードシーケンスを生成する。
各コードワードは、整合する第１のシーケンスに先行する非整合シーケンスの長さ、関連するオフセット、および整合する第１のシーケンスの長さを示す３つのデータアイテムを含む。
【０００７】
本発明の別の態様によれば、上述したようにデータ部分の入力シーケンスを圧縮する手段を備えた圧縮システムが提供される。
【０００８】
本発明の別の態様によれば、計算装置によって実行可能であり、データ部分の入力シーケンスを圧縮する上記方法を実行させる命令プログラムを有形に具現する計算装置読み取り可能なプログラム格納装置が提供される。
【０００９】
本発明は、図面を参照することによってよりよく理解されよう。
【００１０】
【発明の実施の形態】
図２は、本発明の教示を組み込んだデータ圧縮／解凍システム２を示す模式図である。
本システムは、転送媒体１２を介して解凍システム１０に転送するために、文字シーケンス６（図４）を表すデータのバイト等データ部分の入力シーケンスを圧縮して出力コードストリーム８（図４）にする手段を内蔵した圧縮システム４を含む。
解凍システム１０は、コードストリーム８を受信し、コードストリーム８を解凍または拡張して、文字シーケンス６を再構築する。
【００１１】
図３は、圧縮システム４および解凍システム１０として機能するように適宜プログラムすることのできる計算システム１４の通常の要素を示すブロック図である。
要素は、システムバス２０を介してシステムメモリ１８に接続されたプログラマブルプロセッサ１６を含む。
プロセッサ１６は、システムメモリ１８ならびに他の入出力（Ｉ／Ｏ）チャネル２２および周辺装置２４にアクセスする。
計算システム１４はさらに、ＣＤ−ＲＯＭ、テープ、磁気媒体、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＲＯＭ等少なくとも１つのプログラム格納装置２６を含む。
計算システムは、本発明の実施形態によるデータシーケンスを圧縮する方法を実施する１つまたは複数のコンピュータプログラムを格納する。
プロセッサ１６は、１つまたは複数のコンピュータプログラムを読み取り実行して、本方法を実行する。
各コンピュータプログラムは、任意所望のコンピュータプログラミング言語（機械語、アセンブリ言語、高水準手続き形言語、またはオブジェクト指向プログラミング言語を含む）で実施することができる。
いずれの場合であっても、言語はコンパイル済みのまたは解釈済みの言語であることができる。
【００１２】
図４は、本方法を使用して文字シーケンス６を圧縮することによって得られる出力コードストリーム８を示す。
概して、圧縮システム４は、各文字がバイトに格納されている場合、バイト毎に文字シーケンス６を順次トラバースして、トラバースされた各バイトで開始する第１のバイトシーケンスが先にトラバースされた第２のバイトシーケンスと整合するかどうかを判定する。
第１のシーケンス４２が第２のシーケンス４４と整合する場合、圧縮システム４は、第１のシーケンス４２のバイト単位の長さ、第１のシーケンス４２の冒頭と第２のシーケンス４４の冒頭との間のバイト単位でのオフセットを示す。
圧縮システム４はまた、文字シーケンス６中の任意の非整合バイトシーケンス４６を順次記録する。
文字シーケンス６が完全にトラバースされると、非整合シーケンス４６のストリームとは別個のコードワード５０の順序付きシーケンス４８が生成される。
コードワードのこの順序付きシーケンス４８および非整合シーケンス４６のストリームは、文字シーケンス６の圧縮データを定義する。
コードワード５０および非整合シーケンス４６はそれぞれ、文字シーケンス６に現れる順序に並べられる。
各コードワード５０は、整合する第１のシーケンス４２に先行する非整合シーケンス４６の長さ、整合した第１のシーケンス４２と整合する第２のシーケンス４４との間のオフセット、および整合した第１のシーケンス４２の長さを示す３つのデータアイテムを含む。
【００１３】
図５は、圧縮システム４を使用して文字シーケンス６を圧縮する方法の一連のステップ６０を示すフローチャートである。
この圧縮順６０について、文字シーケンス６をトラバースすなわち処理する順に従って述べる。
圧縮順６０は、入力シーケンス受信ステップ６２で開始され、圧縮システム４が文字シーケンス６を受信する。
図４における文字シーケンス６は、文字シーケンス６でのそれぞれの位置に従って番号がふられた２５個の文字を含む。
圧縮順６０は、文字シーケンス６を受信した後、初期化ステップ６４に進み、ポインタ（図示せず）が、文字シーケンス６中の最初の文字"Ａ"の前の文字位置を指すように初期化される。
【００１４】
次に、圧縮順６０は入力シーケンスが空になったか否かを判定するステップ６６に進み、圧縮システム４が、文字シーケンス６中のすべての文字が完全に処理されたか否かを判定する。
このステップ６６において、文字シーケンス６に処理する文字が残っていると判定された場合、圧縮順６０はポインタを進めるステップ６８に進む。
このステップ６８において、圧縮システム４はポインタを１つの文字位置分進めて、ポインタが文字シーケンス６中の次の文字を指すようにする。
文字シーケンス６処理のこの時点において、ポインタは、文字"Ａ"（１番目の文字）を指すように進められる。
圧縮順６０は次に、整合シーケンスをチェックするステップ７０に進む。
このステップ７０において、圧縮システム４は、ポインタが指している文字で開始する所定の最小文字数の第１のシーケンスが、先にトラバースすなわち処理された第２の文字シーケンスと整合するか否かを判定する。
マッチングは、他のＬＺ技法に使用されているハッシュ法を使用して行われる。
【００１５】
整合シーケンスをチェックするステップ７０に従って、整合するシーケンスがないと判定された場合、圧縮順６０は非整合シーケンス更新ステップ７２に進み、圧縮システム４が非整合文字カウンタ（図示せず）を増分する。
次いで、圧縮順６０は、入力シーケンスが空になったか否かを判定するステップ６６に戻る。
圧縮順６０は、ポインタを進めるステップ６８において、ポインタが７番目の文字"Ｂ"を指すまで、文字シーケンス６の第１の非整合シーケンス"ＡＢＣＤＥＦ"（１番目から６番目の文字）を処理する場合、ステップ６６〜７２をループする。
この時点において、非整合文字カウンタが、非整合シーケンス"ＡＢＣＤＥＦ"の文字数または長さにより６の値に増分されている。
【００１６】
整合シーケンスをチェックするステップ７０において、所定の最小文字数、たとえば３個の文字の第１のシーケンスと第２のシーケンスとが整合すると判定された場合、圧縮順６０は最長整合を見つけるステップ７４に進む。
これは、別のシーケンス"ＢＣＤ"（２番目から４番目の文字）と整合するシーケンス"ＢＣＤ"（７番目から９番目の文字）に直面する場合である。
最長整合を見つけるステップ７４では、圧縮システム４が、先に処理された文字の第２の文字シーケンスと整合する、ポインタが指す文字で開始する最長の第１のシーケンスを判定する。
文字シーケンス６の処理におけるこの時点で、最長の第１のシーケンス４２は"ＢＣＤ"（７番目から９番目の文字）である。
圧縮システム４は、２つの整合するシーケンス４２、４４の冒頭の間のオフセットすなわち文字数と、これらシーケンス４２、４４のうちの一方の長さすなわち文字数とを示す。
オフセットおよび長さは、整合した第１のシーケンス"ＢＣＤ"（７番目から９番目の文字）についてそれぞれ５個および３個の文字である。
【００１７】
次に、圧縮順６０は、非整合シーケンスをチェックするステップ７６に進み、圧縮システム４が、現在の整合した第１のシーケンス４２の前に非整合シーケンスがあるか否かを判定する。
このステップ７６において非整合シーケンス４６があると判定された場合、圧縮システム４は、第１の出力ステップ７８において、非整合シーケンス４６の文字数すなわち長さをシステムメモリ１８中の第１のバッファ（図示せず）に付加する。
非整合シーケンス"ＡＢＣＤＥＦ"（１番目から６番目の文字）の場合、６の値が、後述する符号化フォーマットに従って第１のバッファに書き込まれる。
また、第１の出力ステップ７８において、圧縮システム４は、非整合文字シーケンス４６をシステムメモリ１８中の第２のバッファ（図示せず）に付加する。
文字シーケンス６処理のこの時点において、圧縮システム４は、シーケンス"ＡＢＣＤＥＦ"を第２のバッファに書き込む。
【００１８】
非整合シーケンスをチェックするステップ７６において、非整合シーケンスがないと判定された場合、圧縮システム４は、第２の出力ステップ８０において、値０を第１のバッファに付加する。
第１の出力ステップ７８および第２の出力ステップ８０から、圧縮順６０は第３の出力ステップ８２に進み、圧縮システム４が整合した第１のシーケンス４２のオフセットおよび長さを第１のバッファに付加する。
オフセットおよび長さの双方もまた、符号化フォーマットに従って符号化される。
この第３の出力ステップ８２において、圧縮システム４はまた、相応に進められ、非整合文字カウンタをクリアする。
文字シーケンス６処理のこの時点まで、第１のバッファは値６、５、および２それぞれを有する３つのデータアイテムを含む。
これら３つのデータアイテムがコードワード５０を形成する。
【００１９】
次いで、圧縮順６０は、入力シーケンスが空になったか否かを判定するステップ６６に戻り、文字シーケンス６中のすべての文字が処理されるまで、上記ステップ６８〜８２を繰り返す。
具体的には、圧縮順６０は、非整合シーケンス"ＧＨＩ"（１０番目から１２番目の文字）を処理する場合、ステップ６６〜７２を繰り返す。
圧縮順６０は、ステップ７０においてシーケンス"ＣＤＧ"（１３番目から１５番目の文字）を処理する場合、別のシーケンス"ＣＤＧ"（８番目から１０番目の文字）に整合するため、最長整合を見つけるステップ７４に進む。
最長整合を見つけるステップ７４において、最長の整合シーケンスはシーケンス"ＣＤＧＨＩＣ"（１３番目から１８番目の文字）であると判定される。
このシーケンス"ＣＤＧＨＩＣ"に関連するオフセットは５であり、シーケンスの長さは６である。
したがって、圧縮システム４は、第１の出力ステップ７８および第３の出力ステップ８２において、第１のバッファに値３、５、および６のデータアイテムを有する別のコードワードを付加する。
圧縮システム４はまた、第２の出力ステップ８０において、整合シーケンス"ＣＤＧＨＩＣ"（１３番目から１８番目の文字）の前の非整合シーケンス"ＧＨＩ"（１０番目から１２番目の文字）を第２のバッファに付加する。
【００２０】
同様に、圧縮順６０を使用して、文字シーケンス６の残りのシーケンス"ＥＦＢＣＩＪＫ"（１９番目から２５番目の文字）を処理する。
シーケンス"ＥＦＢＣ"（１９番目から２２番目の文字）を処理すると、値０、１４、および４のデータアイテムを有する第３のコードワードが第１のバッファに付加されることになる。
第３のコードワード５０における値０の第１のデータアイテムは、第２の出力ステップ８０において、第１のバッファに付加される。
この値０のデータアイテムは、整合シーケンス"ＥＦＢＣ"（１９番目から２２番目の文字）と先の整合シーケンス"ＣＤＧＨＩＣ"（１３番目から１８番目の文字）の間に非整合シーケンスがないことを示す。
【００２１】
最後の３個の文字"ＩＪＫ"（２３番目から２５番目の文字）を処理する際、圧縮順６０は、ステップ６６において、文字シーケンス６中のすべての文字が処理されたことを判定する。
次いで、圧縮順６０は第４の出力ステップ８４に進む。
この第４の出力ステップ８４では、圧縮システム４が残りの非整合シーケンス"ＩＪＫ"（２３番目から２５番目の文字）を第２のバッファに書き込む。
圧縮順６０は最終的に終了ステップ８６において終了し、転送媒体１２を介して解凍システム１０（図２）に転送するためなど、圧縮されたデータすなわちコードワード５０によって定義されるコードストリームおよび非整合シーケンス４６を使用する準備が整う。
コードワード５０および非整合シーケンス４６が単一メッセージにおいて解凍システム１０に連続して送信される場合、コードストリームは、偶然に非整合シーケンス４６の冒頭であるコードワード５０のシーケンス４８の終わりを示す情報をさらに含む。
この情報は、固定ビット数で符号化しうるコードワードのシーケンス４８の長さであることができる。
【００２２】
次に、コードワード中のデータアイテムの符号化フォーマットについて述べる。
各データアイテムは、少なくとも１つのデリミタビットが前に付いた所定数のビット（ｍビット）によって表される。
所定数のビットは、単一の"１"デリミタビットが前に付いた６ビットであることができる。
６ビットで表すことのできる最大の値は、２６−１＝６３である。
データアイテムの値が６３以下である場合、値を表すには７ビット（１つのデリミタビット＋６ビット）で十分である。
しかし、値が６３を越える場合、６ビットは、その値を２６で割った余りを表すことになる。
値を２６で割った商は、たとえば、"１"のデリミタビットとは認識可能に異なる等しい数の"０"ビットで表される。
これら"０"ビットはそれぞれ、６４の追加の値を表す。
以下の表は、各種値を表すために使用されるビット列の例を示す。
値４５は、デリミタの"１"ビット（太字の斜体）および６ビットを含む７ビットで表される。
値６７は、さらなる"０"ビットを"１"デリミタビットの前に含む８ビットで表される。
同様に、値２００は、合計値１９２を表す先行する３個の"０"ビットを含む１０ビットで表される。
【００２３】
【表１】
0003910932.tif 000002
【００２４】
上記符号化フォーマットを使用すると、コードワードの表現には最小の２１ビットが採用される。したがって、非整合シーケンスとして第２のバッファに１つまたは２つの整合文字を書き込むほうが、かかるコードワードを使用して表すよりも経済的である。整合シーケンスをチェックするステップ７０における所定の最小文字数が３文字になるように選択されるのはこのためである。
【００２５】
有利なことに、上述した圧縮方法は、最後のコードワード以外のすべてのコードワードをバイト位置合わせする必要がない。
コードワードは共にグループ化されるため、非整合文字シーケンスからコードワードを区切る必要もなくなる。
【００２６】
本発明を上記実施形態において実施するものとして説明したが、本発明がそれだけに限定されると解釈すべきではない。
たとえば、入力シーケンスをバイト毎に処理する代わりに、他の長さのデータ部分を使用して処理してもよい。
【００２７】
別の例として、固定数のｍビットの代わりに可変数のビットを使用して、データアイテム値を２ｍで割った余りを表してもよい。
たとえば、各コードワード中の３つのデータアイテムそれぞれのこの余り部分を、別のビット数で表してもよい。
コードワード中の各データアイテムの余りビット数は、圧縮中に決定することができる。
この場合、データアイテムの余り部分を表すために使用される余りビット数を示すさらなる情報を出力コードストリームに含める必要がある。
【図面の簡単な説明】
【図１】文字シーケンスおよび従来技術によるＬｅｍｐｅｌ−Ｚｉｖ−Ｏｂｅｒｈｕｍｅｒ（ＬＺＯ）技法を使用して文字シーケンスを圧縮することによって得られる出力コードストリームを示す模式図である。
【図２】解凍システムに転送するために、本発明の実施形態による、データシーケンスを圧縮してコードストリームにする圧縮システムを含むデータ圧縮／解凍システムの模式図である。
【図３】図２の圧縮システムおよび解凍システムとして使用しうる計算システムの典型的なハードウェア要素を示すブロック図である。
【図４】図２の圧縮システムを使用して図１における文字シーケンスを圧縮することによって得られる出力コードストリームを示す模式図である。
【図５】文字シーケンスを圧縮するために図２に示す圧縮システムにおける一連のステップを示すフローチャートである。
【符号の説明】
２・・・データ圧縮／解凍システム、
４・・・圧縮システム、
６・・・文字シーケンス、
８・・・出力コードストリーム、
１０・・・解凍システム、
１２・・・転送媒体、
１４・・・計算システム、
１６・・・プログラマブルプロセッサ、
１８・・・システムメモリ、
２０・・・システムバス、
２２・・・入出力（Ｉ／Ｏ）チャネル、
２４・・・周辺装置、
２６・・・プログラム格納装置、
４２・・・第１のシーケンス、
４４・・・第２のシーケンス、
４６・・・非整合バイトシーケンス、
４８・・・順序付きシーケンス、
５０・・・コードワード
【図１】
0003910932.tif 000003
【図２】
0003910932.tif 000004
【図３】
0003910932.tif 000005
【図４】
0003910932.tif 000006
【図５】
0003910932.tif 000007