(57)【要約】  データ圧縮システム、方法、およびコンピュータプログラム製品が開示される。入力ストリームの連続する入力ワードごとに、入力ワードがルックバックテーブル内のエントリと一致するかどうかが決定される。ルックバックテーブルは、入力ワードに応じて更新される。入力ワードは、ゼロランおよびルックバックテーブル内のエントリとの完全一致または部分一致を含む、いくつかのデータタイプの入力ワードであり得る。コードワードは、入力ワードに対応するデータタイプをエントロピー符号化することによって生成される。ルックバックテーブルは、入力ストリーム内の入力ワードの場所によってインデックス付けされ得る。
2018521537.tif 000002
【特許請求の範囲】
【請求項１】
複数の入力ワードの入力ストリームを圧縮するための方法であって、
前記入力ストリームの連続する入力ワードごとに、前記入力ワードがルックバックテーブル内のエントリと一致するかどうかを決定するステップであって、前記ルックバックテーブルが複数のエントリを記憶する、ステップと、
前記入力ワードに応じて前記ルックバックテーブルを更新するステップと、
前記入力ワードに対応するデータタイプをエントロピー符号化することによってコードワードを生成するステップであって、各入力ワードが複数のデータタイプのうちの1つであり、前記複数のデータタイプが、前記入力ワードと前記ルックバックテーブル内のエントリとの間の完全一致を示す第1のデータタイプと、前記入力ワードと前記ルックバックテーブル内のエントリとの間の部分一致を示す第2のデータタイプとを少なくとも含む、ステップと、
出力ストリームを生成するステップであって、前記出力ストリームが、前記入力ストリームの前記入力ワードに対応して順序付けられたコードワードを含む、ステップと、
を備える、方法。
【請求項２】
前記複数のデータタイプが複数の第3のデータタイプを含み、各第3のデータタイプが固有のゼロ数のランレングスを示し、複数のランレングスの各々が異なるコードワードとして符号化される、請求項1に記載の方法。
【請求項３】
前記複数のデータタイプが、前記入力ワードと前記ルックバックテーブル内のエントリとの間の完全一致も部分一致も示さない第4のデータタイプを含む、請求項1に記載の方法。
【請求項４】
前記ルックバックテーブルを更新するステップが、前記ルックバックテーブル内の前記入力ワードのためのテーブルインデックスを記憶するステップを備え、前記テーブルインデックスが前記入力ストリーム内の前記入力ワードの場所を表し、
出力ストリームを生成するステップが、前記第1のデータタイプの入力ワードに対して生成された各コードワードに関連付けられる出力インデックスを生成するステップを備え、前記出力インデックスが、前記入力ストリーム内の完全に一致する入力ワードの場所を表す、請求項1に記載の方法。
【請求項５】
前記出力インデックスが、前記圧縮された出力において、前記入力ストリーム内の前記入力ワードの場所の2を底とする対数に応じて決定されるビット数によって表される、請求項4に記載の方法。
【請求項６】
前記入力ワードと前記ルックバックテーブル内のエントリとの間の部分一致が、前記入力ワードの連続するビットのサブセットと、前記ルックバックテーブル内の前記エントリの連続するビットの対応する配置されたサブセットとのビット単位の一致を備える、請求項1に記載の方法。
【請求項７】
前記ルックバックテーブルを更新するステップが、前記ルックバックテーブル内の前記入力ワードのためのテーブルインデックスを記憶するステップを備え、前記テーブルインデックスが前記入力ストリーム内の前記入力ワードの場所を表し、
出力ストリームを生成するステップが、前記第2のデータタイプの入力ワードに対して生成された各コードワードに関連する不一致ワード部分を生成するステップと、前記第2のデータタイプの入力ワードに対して生成された各コードワードに関連する出力インデックスを生成するステップとを備え、前記出力インデックスが、前記入力ストリーム内の部分的に一致する入力ワードの場所を表す、請求項1に記載の方法。
【請求項８】
前記出力インデックスが、前記圧縮された出力において、前記入力ストリーム内の前記入力ワードの場所の2を底とする対数に応じて決定されるビット数によって表される、請求項7に記載の方法。
【請求項９】
入力ワードと前記ルックバックテーブル内のエントリとの間の完全一致が、前記入力ワードのすべてのビットと前記ルックバックテーブル内の前記エントリのすべてのビットとのビット単位の一致を備える、請求項1に記載の方法。
【請求項１０】
前記ルックバックテーブルを更新するステップが、前記ルックバックテーブル内の前記入力ワードのためのテーブルインデックスを記憶するステップを備え、前記テーブルインデックスが前記入力ストリーム内の前記入力ワードの場所を表し、
前記複数のデータタイプが、前記入力ワードと前記ルックバックテーブル内のエントリとの間の完全一致も部分一致も示さない第4のデータタイプを含み、
出力ストリームを生成するステップが、前記第4のデータタイプの入力ワードに対して生成された各コードワードに関連して不一致の完全ワードを生成するステップを備える、請求項1に記載の方法。
【請求項１１】
複数の入力ワードの入力ストリームを圧縮するためのシステムであって、
メモリと、
前記メモリから前記入力ストリームの連続する入力ワードを読み出すステップを備え、連続する入力ワードごとに、
前記入力ワードがルックバックテーブル内のエントリと一致するかどうかを決定するステップであって、前記ルックバックテーブルが複数のエントリを記憶する、ステップと、
前記入力ワードに応じて前記ルックバックテーブルを更新するステップと、
前記入力ワードに対応するデータタイプをエントロピー符号化することによってコードワードを生成するステップであって、各入力ワードが複数のデータタイプのうちの1つであり、前記複数のデータタイプが、前記入力ワードと前記ルックバックテーブル内のエントリとの間の完全一致を示す第1のデータタイプと、前記入力ワードと前記ルックバックテーブル内のエントリとの間の部分一致を示す第2のデータタイプとを少なくとも含む、ステップと、
出力ストリームを生成するステップであって、前記出力ストリームが、前記入力ストリームの前記入力ワードに対応して順序付けられたコードワードを含む、ステップと、
を備える方法を実行するように構成されたプロセッサと
を備える、システム。
【請求項１２】
前記複数のデータタイプが複数の第3のデータタイプを含み、各第3のデータタイプが固有のゼロ数のランレングスを示し、複数のランレングスの各々が異なるコードワードとして符号化される、請求項11に記載のシステム。
【請求項１３】
前記複数のデータタイプが、前記入力ワードと前記ルックバックテーブル内のエントリとの間の完全一致も部分一致も示さない第4のデータタイプを含む、請求項11に記載のシステム。
【請求項１４】
前記ルックバックテーブルを更新するステップが、前記ルックバックテーブル内の前記入力ワードのためのテーブルインデックスを記憶するステップを備え、前記テーブルインデックスが前記入力ストリーム内の前記入力ワードの場所を表し、
出力ストリームを生成するステップが、前記第1のデータタイプの入力ワードに対して生成された各コードワードに関連付けられる出力インデックスを生成するステップを備え、前記出力インデックスが、前記入力ストリーム内の完全に一致する入力ワードの場所を表す、請求項11に記載のシステム。
【請求項１５】
前記出力インデックスが、前記圧縮された出力において、前記入力ストリーム内の前記入力ワードの場所の2を底とする対数に応じて決定されるビット数によって表される、請求項14に記載のシステム。
【請求項１６】
前記入力ワードと前記ルックバックテーブル内のエントリとの間の部分一致が、前記入力ワードの連続するビットのサブセットと、前記ルックバックテーブル内の前記エントリの連続するビットの対応する配置されたサブセットとのビット単位の一致を備える、請求項11に記載のシステム。
【請求項１７】
前記ルックバックテーブルを更新するステップが、前記ルックバックテーブル内の前記入力ワードのためのテーブルインデックスを記憶するステップを備え、前記テーブルインデックスが前記入力ストリーム内の前記入力ワードの場所を表し、
出力ストリームを生成するステップが、前記第2のデータタイプの入力ワードに対して生成された各コードワードに関連する不一致ワード部分を生成するステップと、前記第2のデータタイプの入力ワードに対して生成された各コードワードに関連する出力インデックスを生成するステップとを備え、前記出力インデックスが、前記入力ストリーム内の部分的に一致する入力ワードの場所を表す、請求項11に記載のシステム。
【請求項１８】
前記出力インデックスが、前記圧縮された出力において、前記入力ストリーム内の前記入力ワードの場所の2を底とする対数に応じて決定されるビット数によって表される、請求項17に記載のシステム。
【請求項１９】
入力ワードと前記ルックバックテーブル内のエントリとの間の完全一致が、前記入力ワードのすべてのビットと前記ルックバックテーブル内の前記エントリのすべてのビットとのビット単位の一致を備える、請求項11に記載のシステム。
【請求項２０】
前記ルックバックテーブルを更新するステップが、前記ルックバックテーブル内の前記入力ワードのためのテーブルインデックスを記憶するステップを備え、前記テーブルインデックスが前記入力ストリーム内の前記入力ワードの場所を表し、
前記複数のデータタイプが、前記入力ワードと前記ルックバックテーブル内のエントリとの間の完全一致も部分一致も示さない第4のデータタイプを含み、
出力ストリームを生成するステップが、前記データタイプの入力ワードに対して生成された各コードワードに関連して不一致の完全ワードを生成するステップを備える、請求項11に記載のシステム。
【請求項２１】
複数の入力ワードの入力ストリームを圧縮するためのコンピュータ実行可能ロジックを記憶したコンピュータ可読記憶媒体であって、前記コンピュータ実行可能ロジックが、
前記入力ストリームの連続する入力ワードごとに、前記入力ワードがルックバックテーブル内のエントリと一致するかどうかを決定するように構成された入力ロジックであって、前記ルックバックテーブルが複数のエントリを記憶する、入力ロジックと、
前記入力ワードに応じて前記ルックバックテーブルを更新するように構成されたルックバックテーブルロジックと、
前記入力ワードに対応するデータタイプをエントロピー符号化することによってコードワードを生成するように構成されたエントロピー符号化ロジックであって、各入力ワードが複数のデータタイプのうちの1つであり、前記複数のデータタイプが、前記入力ワードと前記ルックバックテーブル内のエントリとの間の完全一致を示す第1のデータタイプと、前記入力ワードと前記ルックバックテーブル内のエントリとの間の部分一致を示す第2のデータタイプとを少なくとも含む、エントロピー符号化ロジックと、
出力ストリームを生成するように構成された出力ロジックであって、前記出力ストリームが、前記入力ストリームの前記入力ワードに対応して順序付けられたコードワードを含む、出力ロジックと、
を備える、コンピュータ可読記憶媒体。
【請求項２２】
前記複数のデータタイプが複数の第3のデータタイプを含み、各第3のデータタイプが固有のゼロ数のランレングスを示し、複数のランレングスの各々が異なるコードワードとして符号化される、請求項21に記載のコンピュータ可読記憶媒体。
【請求項２３】
前記ルックバックテーブルロジックが、前記ルックバックテーブル内の前記入力ワードに対するテーブルインデックスを記憶するように構成され、前記テーブルインデックスが、前記入力ストリーム内の前記入力ワードの場所を表し、
前記出力ロジックが、前記第1のデータタイプの入力ワードに対して生成された各コードワードに関連付けられる出力インデックスを生成するように構成され、前記出力インデックスが、前記入力ストリーム内の完全に一致する入力ワードの場所を表す、請求項21に記載のコンピュータ可読記憶媒体。
【請求項２４】
前記出力インデックスが、前記圧縮された出力において、前記入力ストリーム内の前記入力ワードの場所の2を底とする対数に応じて決定されるビット数によって表される、請求項23に記載のコンピュータ可読記憶媒体。
【請求項２５】
前記入力ワードと前記ルックバックテーブル内のエントリとの間の部分一致が、前記入力ワードの連続するビットのサブセットと、前記ルックバックテーブル内の前記エントリの連続するビットの対応する配置されたサブセットとのビット単位の一致を備える、請求項21に記載のコンピュータ可読記憶媒体。
【請求項２６】
前記ルックバックテーブルを更新するステップが、前記ルックバックテーブル内の前記入力ワードのためのテーブルインデックスを記憶するステップを備え、前記テーブルインデックスが前記入力ストリーム内の前記入力ワードの場所を表し、
前記出力ロジックが、前記第2のデータタイプの入力ワードに対して生成された各コードワードに関連する不一致ワード部分を生成し、前記第2のデータタイプの入力ワードに対して生成された各コードワードに関連する出力インデックスを生成するように構成され、前記出力インデックスが、前記入力ストリーム内の部分的に一致する入力ワードの場所を表す、請求項21に記載のコンピュータ可読記憶媒体。
【請求項２７】
前記出力インデックスが、前記圧縮された出力において、前記入力ストリーム内の前記入力ワードの場所の2を底とする対数に応じて決定されるビット数によって表される、請求項26に記載のコンピュータ可読記憶媒体。
【請求項２８】
前記ルックバックテーブルロジックが、前記ルックバックテーブル内の前記入力ワードのためのテーブルインデックスを記憶するように構成され、前記テーブルインデックスが、前記入力ストリーム内の前記入力ワードの場所を表し、
前記複数のデータタイプが、前記入力ワードと前記ルックバックテーブル内のエントリとの間の完全一致も部分一致も示さない第4のデータタイプを含み、
出力ストリームを生成するステップが、前記第4のデータタイプの入力ワードに対して生成された各コードワードに関連して不一致の完全ワードを生成するステップを備える、請求項21に記載のコンピュータ可読記憶媒体。
【請求項２９】
複数の入力ワードの入力ストリームを圧縮するためのシステムであって、
前記入力ストリームの連続する入力ワードごとに、前記入力ワードがルックバックテーブル内のエントリと一致するかどうかを決定するための手段であって、前記ルックバックテーブルが複数のエントリを記憶する、手段と、
前記入力ワードに応じて前記ルックバックテーブルを更新するための手段と、
前記入力ワードに対応するデータタイプをエントロピー符号化することによってコードワードを生成するための手段であって、各入力ワードが複数のデータタイプのうちの1つであり、前記複数のデータタイプが、前記入力ワードと前記ルックバックテーブル内のエントリとの間の完全一致を示す第1のデータタイプと、前記入力ワードと前記ルックバックテーブル内のエントリとの間の部分一致を示す第2のデータタイプとを少なくとも含む、手段と、
出力ストリームを生成するための手段であって、前記出力ストリームが、前記入力ストリームの前記入力ワードに対応して順序付けられたコードワードを含む、手段と、
を備える、システム。
【請求項３０】
前記複数のデータタイプが複数の第3のデータタイプを含み、各第3のデータタイプが固有のゼロ数のランレングスを示し、複数のランレングスの各々が異なるコードワードとして符号化される、請求項29に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
2015年5月11日に出願された米国仮特許出願第62/159,871号「IMPROVED COMPRESSED CACHING IN A VIRTUAL MEMORY SYSTEM」、および2015年7月14日に出願された米国仮特許出願第62/192,136号「IMPROVED COMPRESSED CACHING IN A VIRTUAL MEMORY SYSTEM」の利益は本明細書によってクレームされており、それらの明細書は、この参照によりその全体が本明細書に組み込まれる。
【背景技術】
【０００２】
デスクトップ、ラップトップまたはタブレットコンピュータ、スマートフォン、携帯情報端末、ポータブルゲーム機などのコンピューティングデバイスは、中央処理装置、グラフィック処理装置、デジタル信号プロセッサなどの1つまたは複数のプロセッサと、1つまたは複数のメモリとを含む。コンピュータ周辺デバイスなどの他の電子デバイス、ならびに従来はコンピューティングデバイスと呼ばれていない家庭用電子デバイスもまた、1つまたは複数のプロセッサとメモリとを含み得る。
【０００３】
ポータブルデバイスなどのいくつかのタイプのデバイスは、プロセッサによって必要とされる量と比較すると、物理システムメモリ(ストレージ)の容量が限られている場合がある。限られた物理システムメモリの問題に対処するために、仮想メモリおよびページングとして一般に知られている技法が使用され得る。仮想メモリは、プロセッサによってアクセス可能なより大きい「仮想」アドレス空間を、ダイナミックランダムアクセスメモリ(「DRAM」)などのシステムメモリが動作する、より小さい物理アドレス空間にマッピングすることを指す。ページングは、従来、システムメモリと、不揮発性ストレージあるいはディスクドライブまたはフラッシュメモリなどの他の二次ストレージとの間で情報を転送する技法を指していた。プロセッサがすぐにアクセスする必要のないページは、システムメモリから二次ストレージに追い出される。二次ストレージの容量が限られているか、二次ストレージへのアクセスがレイテンシの増加を伴うポータブルデバイスまたは他のデバイスにおいて、ページングは、追い出されたページを二次ストレージに記憶する代わりに圧縮された形式でシステムメモリに記憶することを含むように進化している。この技法は、圧縮されたキャッシングと呼ばれ得る。
【０００４】
LZおよびWKDMを含むいくつかの圧縮されたキャッシング方法が知られている。WKDM法では、遭遇した最後の16個の固有の入力ワードのルックバックテーブルを維持し、各入力ワードを分類するタグまたはコードワードを生成することによって、ページ内の連続する入力ワードが処理される。4つのコードワードがあるだけなので、2ビットで表すことができる:入力ワードがすべてゼロであることを示すための第1のコードワード(たとえば、「00」)、入力ワードがルックバックテーブル内の16個のエントリのうちの1つと完全に一致することを示すための第2のコードワード(たとえば、「01」)、入力ワードが部分的にのみ(すなわち、最上位ビットのみ)がルックバックテーブル内のエントリのうちの1つと一致することを示すための第3のコードワード(たとえば「10」)、および入力ワードがルックバックテーブル内のエントリのいずれとも一致しないことを示すための第4のコードワード(たとえば、「11」)。圧縮された出力は、コードワードと、ルックバックテーブル内の一致するエントリに完全なワード一致を示すそれらのコードワードを関連付けるインデックスのテーブルと、ルックバックテーブル内のどのエントリとも完全に一致しない入力ワードと、ルックバックテーブル内のエントリに部分的に一致する入力ワードの不一致部分(すなわち、最下位ビット)とを備える。ルックバックテーブルへの効率的なインデックス付けを提供するために、入力ワードにハッシュ関数が使用される。
【発明の概要】
【課題を解決するための手段】
【０００５】
データストリームを圧縮および解凍するためのシステム、方法、およびコンピュータプログラムが開示される。
【０００６】
入力ストリームを圧縮するための例示的な方法では、入力ストリームの連続する入力ワードごとに、入力ワードがルックバックテーブル内のエントリと一致するかどうかが決定される。ルックバックテーブルは、入力ワードに応じて更新される。コードワードは、入力ワードに対応するデータタイプをエントロピー符号化することによって生成される。入力ワードは、複数のデータタイプの入力ワードであり得る。データタイプは、入力ワードとルックバックテーブル内のエントリとの間の完全一致を示す第1のデータタイプと、入力ワードとルックバックテーブル内のエントリとの間の部分一致を示す第2のデータタイプとを少なくとも含む。コードワードを含む出力ストリームが生成される。
【０００７】
入力ストリームを圧縮するための例示的なシステムは、メモリとプロセッサとを含む。プロセッサは、メモリから連続する入力ワードを読み出すように構成される。入力ストリームの連続する入力ワードごとに、プロセッサは、入力ワードがルックバックテーブル内のエントリと一致するかどうかを決定する。プロセッサは、入力ワードに応じてルックバックテーブルを更新する。プロセッサは、入力ワードに対応するデータタイプをエントロピー符号化することによってコードワードを生成する。入力ワードは、複数のデータタイプの入力ワードであり得る。データタイプは、入力ワードとルックバックテーブル内のエントリとの間の完全一致を示す第1のデータタイプと、入力ワードとルックバックテーブル内のエントリとの間の部分一致を示す第2のデータタイプとを少なくとも含む。プロセッサは、コードワードを含む出力ストリームを生成する。
【０００８】
入力ストリームを圧縮するための例示的なコンピュータプログラム製品は、非一時的記憶媒体に具体化されたコンピュータ実行可能ロジックを含む。プロセッサによるロジックの実行は、プロセッサが、入力ストリームの連続する入力ワードごとに、入力ワードがルックバックテーブル内のエントリと一致するかどうかが決定するように構成する。プロセッサは、入力ワードに応じてルックバックテーブルを更新する。プロセッサは、入力ワードに対応するデータタイプをエントロピー符号化することによってコードワードを生成する。入力ワードは、複数のデータタイプの入力ワードであり得る。データタイプは、入力ワードとルックバックテーブル内のエントリとの間の完全一致を示す第1のデータタイプと、入力ワードとルックバックテーブル内のエントリとの間の部分一致を示す第2のデータタイプとを少なくとも含む。プロセッサは、コードワードを含む出力ストリームを生成する。
【０００９】
図面においては、特に断らない限り、様々な図を通して同様の参照番号は同様の部分を指す。「102A」または「102B」などの文字記号(letter character designation)を用いた参照番号については、その文字記号は、同じ図面内に存在する2つの同様の部分または要素を区別することができる。参照番号の文字記号は、すべての部分を包含する参照番号が、すべての図面において同じ参照番号を有することが意図されるときには、省略されることがある。
【図面の簡単な説明】
【００１０】
【図１】データ圧縮機能を有する処理システムのブロック図である。
【図２】データを圧縮するための例示的な方法を示す流れ図である。
【図３】データを圧縮するための例示的な方法を示す別の流れ図である。
【図４】ハッシュ関数を用いたルックバックテーブルへのアクセスを示す概念図である。
【図５】入力ストリーム内の入力ワード場所によるルックバックテーブルエントリのインデックス付けを示す概念図である。
【図６Ａ】ゼロランのコードワードを備える出力ストリームの一部を示すデータ構造図である。
【図６Ｂ】不一致のコードワードと、不一致の完全な入力ワードとを備える出力ストリームの一部を示すデータ構造図である。
【図６Ｃ】完全一致のコードワードと、入力ストリーム内の一致ワードの場所とを備える出力ストリームの一部を示すデータ構造図である。
【図６Ｄ】部分一致のコードワード、入力ストリーム内の部分的に一致するワードの場所、および入力ワードの不一致部分を備える出力ストリームの一部を示すデータ構造図である。
【図７】データ圧縮機能を有する1つまたは複数の処理システムを有するポータブルコンピューティングデバイスのブロック図である。
【発明を実施するための形態】
【００１１】
「例示的な」という用語は、本明細書においては、「1つの例、事例、または例証としての機能を果たす」を意味するように使用される。「例示的な」として本明細書において説明される任意の態様は、必ずしも、他の態様よりも好ましい、または他の態様よりも有利であるように解釈されるべきものとは限らない。
【００１２】
「構成要素」、「データベース」、「モジュール」、「システム」という用語、および同様のものは、ハードウェア、ファームウェア、ハードウェアとソフトウェアの組合せ、ソフトウェア、または実行中のソフトウェアのいずれかであるコンピュータに関連するエンティティを指すように意図されている。たとえば、構成要素は、これだけに限らないが、プロセッサ上で動作するプロセス、プロセッサ、オブジェクト、実行ファイル、実行スレッド、プログラム、および/またはコンピュータとすることができる。例として、コンピューティングデバイス上で動作するアプリケーションとコンピューティングデバイスとは共に構成要素とすることができる。1つまたは複数の構成要素は、プロセスおよび/または実行スレッド内に常駐することができ、また構成要素は、1つのコンピュータ上に局所化される、かつ/または2つ以上のコンピュータ間で分散され得る。さらに、これらの構成要素は、様々なデータ構造がその上に記憶された様々なコンピュータ可読媒体から実行することができる。構成要素は、1つまたは複数のデータパケット(たとえば、ローカルシステム、分散システム内の別の構成要素と、かつ/またはインターネットなどのネットワークを介して、信号により他のシステムと対話する1つの構成要素からのデータなど)を有する信号によるなど、ローカルおよび/または遠隔のプロセスにより通信することができる。
【００１３】
「アプリケーション」または「画像」という用語はまた、オブジェクトコード、スクリプト、バイトコード、マークアップ言語ファイル、およびパッチなどの実行可能なコンテンツを有するファイルを含むことができる。さらに、本明細書で「アプリケーション」と呼ばれるものはまた、開かれる必要のあり得る文書など、実行可能な性質のものではないファイル、またはアクセスされる必要のある他のデータファイルを含むことができる。
【００１４】
「コンテンツ」という用語はまた、オブジェクトコード、スクリプト、バイトコード、マークアップ言語ファイル、およびパッチなどの、実行可能コンテンツを有するファイルを含み得る。加えて、本明細書で言及する「コンテンツ」は、開封される必要があり得るドキュメント、またはアクセスされる必要がある他のデータファイルなど、本質的に実行可能ではないファイルを含むこともある。
【００１５】
「タスク」という用語は、プロセス、スレッド、またはデバイス内の他の任意の実行単位を含み得る。「方法」および「プロセス」という用語は、同義語として使用され得る。
【００１６】
「仮想メモリ」という用語は、メモリを参照しているアプリケーションまたはイメージから見た実際の物理メモリの抽象化を指す。仮想メモリアドレスを物理メモリアドレスに変換するために、変換またはマッピングが使用され得る。マッピングは、1対1(たとえば、物理アドレスが仮想アドレスに等しい)のように単純でもよく、中程度に複雑(たとえば、物理アドレスが仮想アドレスからの一定のオフセットに等しい)でもよく、またはマッピングは複雑でもよい(たとえば、すべての4KBページが一意にマッピングされる)でもよい。マッピングは、静的である(たとえば、起動時に一度実行される)場合があり、または、動的である(たとえば、メモリが割り振られ、空けられながら、連続的に進展する)場合がある。
【００１７】
この説明においては、「通信デバイス」、「ワイヤレスデバイス」、「ワイヤレス電話」、「ワイヤレス通信デバイス」、および「ワイヤレスハンドセット」という用語は互換的に使用される。第3世代(「3G」)ワイヤレス技術と4世代(「4G」)の出現により、より広い帯域幅の可用性が、より多様な無線機能を備えたよりポータブルなコンピューティングデバイスを可能にした。したがって、ポータブルコンピューティングデバイスには、セルラー電話、ページャ、PDA、スマートフォン、ナビゲーションデバイス、またはワイヤレス接続もしくはワイヤレスリンクを有するハンドヘルドコンピュータが含まれる場合がある。
【００１８】
図1に示されるように、例示的な実施形態において、処理システム100は、プロセッサ102およびシステムメモリ104を含む。プロセッサ102およびシステムメモリ104は、バスなどの1つまたは複数の相互接続106を介して、互いに、および他のデバイス(図1には図示せず)と信号を通信することができる。従来のコンピューティング原理に従って、プロセッサ102は、様々な機能または方法を実行するようにプロセッサ102を構成する、オペレーティングシステムコードおよびアプリケーションプログラムコード(明確化のために図示せず)などのプログラミングコードの制御下で動作する。そのような方法は、本明細書に記載されるデータ圧縮方法を含む。そのようなコードを通じて、プロセッサ102は、本明細書に記載されるデータ圧縮方法に関連するデータ圧縮ロジック108で構成され得る。データ圧縮ロジック108は、入力ロジック110、エントロピー符号化ロジック112、ランレングスロジック114、ルックバックテーブルロジック116、および出力ロジック118を含むことができる。ロジック108〜118は、システムメモリ104に記憶されているか、システムメモリ104に存在しているものとして、説明するために概念的に示されているが、ロジック108〜118は、システムメモリ104または別のメモリ(図1には図示せず)に記憶され得るソフトウェアの動作によって生じることが理解される。ロジック108〜118でプログラムまたは構成されているように、プロセッサ102とシステムメモリ104との組合せは、一般に、本明細書に記載されるデータ圧縮方法を実行するように構成された処理システム100を定義する。明確化のために図1には図示されていないが、本明細書に記載されるデータ圧縮方法を実行するように構成されていることに加えて、処理システム100は、たとえばオペレーティングシステム方法およびアプリケーションプログラム方法などの従来の方法を実行するように構成され得る。また、ロジック108〜118または関連するソフトウェア要素と、それらが記憶されている媒体またはそれらが非一時的な形式で存在する媒体(たとえば、システムメモリ104)との組合せは、一般的に、特許辞典において「コンピュータプログラム製品」と呼ばれるものを定義する点に留意されたい。さらに、ロジック108〜118は、以下に記載される機能を実行するための手段を定義する。
【００１９】
後述する例示的なデータ圧縮方法によれば、処理システム100は、入力データ120を出力データ122に圧縮する。当業者には理解されるように、入力データ120は、プロセッサ102が直接利用することができる「非圧縮」形式またはネイティブ形式で存在するが、出力データ122は、プロセッサ102によって直接利用することはできないが、入力データ120よりもシステムメモリ104内のより小さいストレージ空間を占有する、圧縮された形式で存在する。例示的な実施形態を説明するために、入力データ120および出力データ122は、システムメモリ104に存在するか、システムメモリ104に記憶されているように概念的に示されているが、他の実施形態では、そのような入力データおよび出力データは、他の任意の適切なストレージまたは通信媒体に存在し得ることを理解されたい。例示的な方法に関して以下に記載されるように、入力データ120は連続する入力ワードのストリームの形態で受信され、出力データ122は連続する出力ワードのストリームの形態で生成される。
【００２０】
例示的な実施形態では、入力データ120は、圧縮されたキャッシング方式に従って出力データ122に圧縮され得る。たとえば、キャッシング方式が、プロセッサ102は即時アクセスを必要としないと決定する入力データ120の1つまたは複数のページが出力データ122に圧縮され得、以前はそれらのページによって占有されていたシステムメモリ104内の空間が、他の用途に利用可能になる。キャッシング方式が、それらのページの1つまたは複数がプロセッサ102によって再び必要とされることを示すとき、圧縮されたページが解凍され、非圧縮形式でシステムメモリ104に再び記憶され得る。圧縮方法を参照するために明確にするために、本明細書において「入力」および「出力」という用語が使用されるが、圧縮データは、対応する解凍方法への入力として役立つ場合があることを理解されたい。そのようなキャッシング方式は当該技術分野においてよく理解されているので、本明細書に記載された実施形態のキャッシング態様は、さらに詳細には説明されない。
【００２１】
後述するように、ハフマンコーディングなどのエントロピーコーディングが使用される。エントロピーコーディングは当業者にはよく理解されているので、本明細書においては詳細に説明しない。しかしながら、入力データを圧縮する前に、入力データ内で発生する可能性のある異なるデータタイプの発生の相対頻度が決定され得ることが認識されるべきである。たとえば、当技術分野でよく理解されているように、統計的に有意なデータのサンプルを分析することによって、ヒストグラムが構築され得る。次いで、コードワードの長さが頻度に反比例するような方法で、コードワードがデータタイプに割り当てられ得る。すなわち、より短いコードワードがより高い頻度のデータタイプに割り当てられ、より長いコードワードがより低い頻度のデータタイプに割り当てられる。例示的な実施形態において符号化されたデータタイプを以下に記載する。
【００２２】
以下に記載するシステムは、ハフマンコーディング以外の他のエントロピーコーディング方式にも適用され得る。本システムは、任意のタイプの辞書ベースのコーディングに適用され得る。本システムは、データストリーム内のパターンを使用して辞書が構築される任意のタイプの辞書ベースのコーディングに適用可能である。
【００２３】
たとえば、システムは、増分符号化などの他の辞書ベースのコーディング方式にも適用可能であり得る。当業者には理解されるように、増分符号化方式は、そのコーディング方式用の辞書を構築するために、そのコードワードに接尾辞または接頭辞を使用することができる。そのようなコーディング方式は、当業者に理解されるように、テキストベースの無損失コーディング方式と呼ばれることもある。システムによって使用され得る他の辞書ベースのコーディング方式は、WKDMを含む。
【００２４】
本システムはまた、データストリームを圧縮するためにより小さい圧縮技法のセットを選択する前に、数十個の圧縮技法をサンプリングする最良の性能方法によって使用され得る。WinRARおよび7-Zipなどのそのような無損失圧縮技法は、当技術分野で知られている。本システムは、ポータブルドキュメントフォーマット(PDF)のようなAdobe(商標)画像を記憶するために使用されるフォーマット、ならびにジョイントフォトグラフィックエキスパートグループ(JPEG)などの有損失画像圧縮技法などの画像圧縮ツールで使用され得る。本システムはまた、ポータブルネットワークグラフィックス(PNG)圧縮のような無損失画像圧縮技法によって使用され得る。
【００２５】
図2の流れ図によって示されるように、例示的な実施形態では、図1に関して上述したシステムは、入力ストリームを圧縮することができる。ブロック202によって示されるように、本方法は、入力ストリームから入力ワードを読み出すことから始まる。入力ロジック110(図1)は、この機能に寄与することができ、入力バッファ(図示せず)を含むことができる。ブロック204によって示されるように、本方法は、入力ワードがゼロの値を有するかどうか、すなわちすべてのビットがゼロであるかどうかを決定する。入力ワードは、当業者にはよく理解されるように、たとえば、16ビット、32ビット、または他の任意の適切なビット数で構成することができる。入力ワードがゼロの値を有すると決定された場合、ブロック206によって示されるように、同様にゼロ値を有する連続する入力ワードの数のカウント(「ZERO_COUNT」)が増分される。しかしながら、入力ワードがゼロの値を有していないと決定された場合、ブロック208によって示されるように、ZERO_COUNTがゼロより大きいかどうかが決定される。入力ワードはゼロの値を有していないが、ZERO_COUNTはゼロよりも大きいという決定は、ゼロランが発生したことを示す。すなわち、2つ以上の連続する入力ワードはゼロの値を有する。ゼロランが発生したと決定された場合、ブロック210によって示されるように、ゼロランを表すために入力ワードはハフマン符号化される。すなわち、長さZERO_COUNTのゼロランのデータタイプに対してコードワードが生成される。生成されたコードワードは出力ストリームの一部になる。
【００２６】
図6Aに示されるように、ゼロの値を有する2つ以上の連続する入力ワードのデータタイプに対するいくつかの生成されたコードワード606〜608のうちの1つを備える出力ストリームの一部602が生成され得る。複数の異なるコードワード604、606、608等によって図6Aに示されるように、各ランレングス(「ZERO_COUNT」)は一意に符号化される。すなわち、N個の異なる長さのゼロランが、対応するN個の異なる周波数を有する入力ストリームにおいて発生する可能性があると決定される実施形態において、コードワード604〜608はN個であり得る。たとえば、コードワード604は、ゼロの値を有する単一の入力ワードのデータタイプに対して生成され得るが、コードワード606は、ゼロなどの値を有する2つの連続的なまたは連続する入力ワードのデータタイプに対して生成され得、コードワード608は、ゼロの値を有するN個の連続的なまたは連続する入力ワードのデータタイプに対して生成され得る。ゼロの値を有する3個とN-1個との間の連続的なまたは連続する入力ワードのデータタイプに対して生成され得る他のコードワードは、明確化のために図6Aにおいて個々に示されていないが、コードワード606と608との間の省略符号(「...」)記号によって示されている。
【００２７】
よく理解されているハフマンコーディングの原理によれば、X個の連続するゼロのランがY個の連続するゼロのランよりも入力データ内でより頻繁に発生する可能性が高いと決定された場合(たとえば、ヒストグラム法、または当技術分野で知られているような他の適切な方法によって)、X個の連続するゼロのランは、Y個の連続的なゼロのランよりも短いコードワードによって符号化され得る。
【００２８】
本方法は、ブロック212に続く。ブロック212によって示されるように、ハッシュ関数が入力ワードに適用される。ブロック208に関して上述したようにゼロランが検出された場合、入力ワードは、ゼロランの最終ゼロ値入力ワードに続くものである点に留意されたい。図4に示されるように、ハッシュ関数を適用した結果は、ルックバックテーブル構造400内の位置(「LOCATION」)を識別またはアドレス指定するために使用される。ルックバックテーブル構造400は、各位置における値(「VALUE」)および場所(「POSITION」)を記憶するように構成される。言い換えれば、ルックバックテーブル構造400内の各位置は、値と場所の両方を参照する。後述するように、ルックバックテーブル構造400内の対応する位置における値にアクセスするために場所が使用され得る。ルックバックテーブル構造400は、たとえば2048または2kなどの任意の数の位置を有することができる。したがって、そのようなルックバックテーブル構造400は、2048個の値および2048個の対応する場所を記憶するように構成される。最初に、すなわち圧縮(または解凍)方法の開始時に、ルックバックテーブル構造400に記憶された値または他のエントリはない。
【００２９】
再び図2を参照すると、ブロック214によって示されるように、ルックバックテーブル構造400内の識別された位置(すなわち、ハッシュ関数によって識別されるLOCATION)に、入力ワードに一致する記憶された値があるかどうかが決定される。ブロック220の文脈における「一致」という用語は、2つのワードにおけるすべてのビットのビット単位の一致を指す。このタイプの一致は、完全一致とも呼ばれ得る。
【００３０】
入力ワードとルックバックテーブル構造400内の識別された位置に記憶された値との間に完全一致があると決定された場合(ブロック214)、ブロック216によって示されるように、このデータタイプ(すなわち、完全一致)に対してコードワードが生成される。完全一致である入力ワードに対してコードワードを生成することに関連して、入力ストリーム内の入力ワードの場所の表示(「POSITION」)が生成された出力に含まれる。したがって、完全に一致する入力ワードのデータタイプのための生成されたコードワード618と、入力ストリーム内の入力ワードの場所620の表示とを備える出力ストリームの一部616(図6C)が生成され得る。入力ストリーム内の入力ワードの場所の表示(「POSITION」)も、識別された位置においてルックバックテーブル構造400に挿入される。ブロック216に続いて、本方法はブロック202に戻ることができ、そこで入力ストリーム内の次の入力ワードが処理される。
【００３１】
完全一致がないと決定された場合(ブロック214)、部分一致があるかどうかがさらに決定される。ブロック218によって示されるように、入力ワードの修正バージョンにハッシュ関数を適用することによって、位置(「LOCATION」)が最初に決定される。入力ワードの修正バージョンは、部分一致のためにテストされる入力ワードのビットを操作することによって生成され得る。たとえば、各入力ワードが32ビットの長さであり、部分一致が入力ワードの12の上位または最上位ビット(「MSB」)のビット単位の一致、およびルックバックテーブル構造400内の識別された位置に記憶された値として定義される実施形態では、修正ワード(「MODIFIED_WORD」)は、入力ワードの12個のMSBをマスクオフし、12個の関連ビットを最下位ビット(「LSB」)の場所に配置するために20ビットだけシフトさせることによって生成され得る。次いで、ブロック220によって示されるように、入力ストリーム内の入力ワードの場所の表示(「POSITION」)は、識別された位置(「LOCATION」)においてルックバックテーブル構造400に挿入される。
【００３２】
ブロック222によって示されるように、ルックバックテーブル構造400内の識別された位置(「LOCATION」)に記憶された値の対応するビットと一致する入力ワードの隣接するビットまたは連続するビットの一部またはサブセットを比較することによって、部分一致があるかどうかが決定される。入力ワードと、ルックバックテーブル構造400内の識別された位置に記憶された値との間に部分一致があると決定された場合(ブロック222)、ブロック224によって示されるように、このデータタイプ(すなわち、部分一致)に対してコードワードが生成される。部分一致である入力ワードに対してコードワードを生成することに関連して、入力ストリーム内の入力ワードの場所の表示(「POSITION」)が生成された出力に含まれる。入力ワードの不一致部分もまた、生成された出力に含まれる。したがって、部分的に一致する入力ワードのデータタイプに対して生成されたコードワード624と、入力ストリーム内の入力ワードの場所の表示626と、入力ワードの不一致部分628とを備える出力ストリームの一部622(図6D)が生成され得る。たとえば、入力ワードが32ビットからなり、部分一致が12個のMSBの一致として定義される実施形態では、入力ワードの不一致部分628は、最下位20ビット(LSB)で構成される。入力ストリーム内の入力ワードの場所の表示(「POSITION」)も、識別された位置においてルックバックテーブル構造400に挿入される。ブロック224に続いて、本方法はブロック202に戻ることができ、そこで入力ストリーム内の次の入力ワードが処理される。
【００３３】
ブロック214および222に従って、入力ワードがルックバックテーブル構造400のいずれのエントリに完全にも部分的にも一致しないことがそれぞれ決定された場合、ブロック226によって示されるように、修正ワード(「MODIFIED_WORD」)がルックバックテーブル構造400に追加される(すなわち、識別された位置に記憶される)。ブロック228によって示されるように、例示的な実施形態におけるハフマンコーディング方式に従って、このデータタイプ(すなわち、完全一致でも部分一致でもない)に対してコードワードが生成される。完全一致でも部分一致でもない入力ワードに対してコードワードを生成することに関連して、不一致入力ワード自体(「未処理」入力ワードとも呼ばれる)全体が生成された出力に含まれる。したがって、不一致入力ワードのデータタイプならびに入力ワード614のコピーまたはインスタンスに対して生成されたコードワード612を備える出力ストリームの一部610(図6B)が生成され得る。ブロック208に続いて、本方法はブロック202に戻ることができ、そこで入力ストリーム内の次の入力ワードが処理される。明確化のために図2には図示されていないが、本方法は、入力ストリーム内のすべての入力ワードが処理されたときに終了することができる。入力ストリームは、入力データ120(図1)の1つまたは複数のページを表すことができる。
【００３４】
図5を簡単に参照すると、入力ストリームの例示的な部分502は、連続する入力ワード(16進表記で)0101、7D10、ADD1、0101、33A5などを有するものとして示されている。(これらの入力ワードの値は意味を持たず、すなわち任意であり、この例では説明のためにのみ提供される。また、説明の便宜上16ビットのワードとして描かれているが、これらの入力ワードは32ビットであり得る。)やはり図5に示されているのは、ルックバックテーブル構造400(図4)に関して上述したのと同じ構造を有する例示的なルックバックテーブル500である。
【００３５】
したがって、たとえば、例示的なルックバックテーブル500は、2048個の値および2048個の対応する場所を記憶するように構成され得る。この例では、入力ワード0101は、入力ストリーム内の場所0に配置されている。したがって、入力ワード0101が完全一致でも部分一致でもないと決定された場合(ブロック214および222)、入力ワード0101およびその場所0は、上述したハッシュ関数を入力ワード0101に適用することによって決定された例示的なルックバックテーブル500内の位置に記憶される。同様に、この例では、入力ワード7D10が完全一致でも部分一致でもないと決定された場合(ブロック214および222)、入力ワード7D10およびその場所1は、上述したハッシュ関数を入力ワード7D10に適用することによって決定された例示的なルックバックテーブル500内の位置に記憶される。
【００３６】
同様に、この例では、入力ワードADD1が完全一致でも部分一致でもないと決定された場合(ブロック214および222)、入力ワードADD1およびその場所2は、上述したハッシュ関数を入力ワードADD1に適用することによって決定された例示的なルックバックテーブル500内の位置に記憶される。しかしながら、この例では、場所3における入力ワード0101を処理した結果は、「3」によってインデックス付けされた例示的なルックバックテーブル500内の位置に記憶された値と完全一致する。上述したように、ルックバックテーブル構造400に記憶された場所は、ルックバックテーブル構造400内の対応する位置における値をインデックス付けする、またはそれにアクセスするために使用され得る。この例では、例示的なルックバックテーブル500内の対応する位置に記憶された値にアクセスするために入力ワード0101の場所「3」を使用すると、その位置に記憶された値は0101であることがわかる。その位置に記憶された値0101と、場所3における入力ワード0101とを比較すると、完全一致がわかる。従来の圧縮技法と比較して、本発明の方法およびシステムは、ハッシュインデックスをルックバック場所に置き換える。
【００３７】
入力ワードの場所620または626(図6Cおよび図6D)の表示は、生成された出力ストリームの一部を形成し、ルックバックテーブル構造400に記憶された値をインデックス付けするか、または指し示すため、出力インデックスとも呼ばれ得る点に留意されたい。出力ストリーム内の出力インデックスは、ルックバックテーブル構造400が記憶するように構成された場所に対応する。ルックバックテーブル構造400に記憶された各場所がルックバックテーブル構造400に記憶された値にインデックス付けするか、またはそれに対応するので、ルックバックテーブル構造400に記憶された対応する値にアクセスするために出力インデックスが使用され得る。
【００３８】
出力インデックスは、関連する入力ワードの入力ストリーム内の場所の2を底とする対数を使用して、出力ストリームにおいて経済的に表され得る。本方法は、処理される際に各入力ワードの入力ストリーム内の場所を追跡するので、本方法は、入力ストリーム内の場所によって表される大きさの2進数が表され得る最少ビット以上の出力インデックスを表す必要はない。たとえば、本方法は入力ストリーム内の場所3を超える入力ワードを処理する際にそのような出力インデックスを生成することができないため、3の出力インデックスは出力ストリームにおいて2ビット以上で表される必要はない。2を底とする3の対数をとると、約1.5が得られ、その結果に天井関数を適用すると2になる。
【００３９】
したがって、3未満の入力ストリーム内の任意の場所は、わずか2ビットで表すことができると決定され得る。同様に、たとえば、本方法は入力ストリーム内の場所15を超える入力ワードを処理する際にそのような出力インデックスを生成することができないため、15の出力インデックスは出力ストリームにおいて4ビット以上で表される必要はない。2を底とする15の対数をとると、約3.9が得られ、その結果に天井関数を適用すると4になる。したがって、15未満の入力ストリーム内の任意の場所は、わずか4ビットで表すことができると決定され得る。
【００４０】
ルックバック場所によるハッシュインデックス置換技法は、データ圧縮技法において使用される任意の辞書ベースのコーディングによって使用され得る。例示的な辞書ベースのコーディング方法は、いくつか例を挙げると、LZ78、LZW、LZ77、LZMS、LZO、LZS、およびLZRWなどの、WKDM、増分符号化、およびLempel-Zivベースの方法を含むが、これらに限定されない。ハッシュインデックスをルックバック場所に置き換えることは、フラクタル圧縮などの画像のための他の圧縮技法においても有用であり得る。当業者には理解されるように、フラクタル圧縮技法は、通常、画像をいくつかのサブセクションに分割し、本技法は、画像の第1のサブセクションが画像の第2および第3のサブセクションなどにかなり類似している場合に、サブセクションが互いにコピーされ得るかどうかを決定する。
【００４１】
ハッシュインデックスをルックバック場所に置き換えると、プロセッサによるアクセスを必要とするデータ構造の数が削減でき、データを解凍するためにアクセス/レビューするデータ構造が少なくなるため、これはデータストリームが解凍され得る速度を向上することができる。本発明の方法およびシステムの別の利点は、ルックバック場所の辞書が(ハッシュインデックスの代わりに)、ハッシュインデックスのみを記憶する辞書と比較してサイズが無限に大きくなり得ることである。ハッシュインデックスの代わりのルックバック場所の辞書の別の利点は、辞書においてハッシュはもはや使用されないので、ハッシュ衝突を低減または排除することができることである。
【００４２】
本発明の方法およびシステムでは、ルックバック場所を備える各ルックバックテーブルエントリは、データストリームの長さの関数であるサイズを有することができる。たとえば、データストリームの最初のワードの場合、この単一ワードのルックバックエントリは、ゼロの値(単一ビットのサイズ)を有するポインタを備え得る。データストリームの第2のワードの場合、ルックバック場所エントリ(またはポインタ)の長さは1の値(単一ビットのサイズ)を備えることができる。4キロバイトの長さのデータストリームの場合、最終ワードのルックバックエントリ(ポインタ長)は、12ビットの値を有するポインタ長を備えることができる。したがって、本発明の方法およびシステムのポインタ長は徐々に増加し、(ハッシュインデックスの代わりに)ルックバック場所を使用してデータストリームが符号化される。
【００４３】
図3に示されるように、上述の方法はまた、以下のより高いレベルの方法で特徴付けられ得る。ブロック302によって示されるように、入力ストリーム内の連続する入力ワードに対して、入力ワードがルックバックテーブルエントリと完全にまたは部分的に一致するかどうかが決定される。ブロック304によって示されるように、ルックバックテーブルは入力ワードに応じて更新される。ブロック306によって示されるように、エントロピー符号化を使用して、入力ワードがどのデータタイプであるか決定されるコードワードが生成される。例示的な実施形態では、エントロピーコーディング方式はハフマンコーディングであるが、他の実施形態では、そのようなエントロピーコーディング方式は、他の任意のタイプのコーディングであり得る。2つ以上のデータタイプがあり得、そのうちの少なくとも1つは入力ワードとルックバックテーブルエントリとの間の完全一致を示し、そのうちのもう1つは入力ワードとルックバックテーブルエントリとの間の部分的な一致を示す。図2に関して上述した例示的な実施形態では、ゼロラン(および、このデータタイプのサブタイプは、異なる長さのゼロランを示す可能性がある)、完全一致、部分一致、不一致の4つの主要データタイプがある。ブロック308によって示されるように、出力ストリームが生成される。出力ストリームの各連続部分は、入力ストリーム内の連続する入力ワードのうちの1つに対応するコードワードを含み、また、図6A〜図6Dに関して上述したように、出力インデックス、完全ワード、またはワードの一部などの追加情報を含むことができる。
【００４４】
例示的な圧縮方法の前述の説明を考慮して、当業者は、対応する解凍方法を容易に理解するであろう。圧縮データの各連続する部分は、入力ストリーム内の連続する入力ワードのうちの1つに対応するコードワードを含み、また、コードワードに関連して、出力インデックス、完全ワード、またはワードの一部を含むことができる。ゼロランのコードワードの検出に応じて、解凍方法は、コードワードによって示される連続的な数のゼロ値ワードを解凍データとして出力する。不一致のコードワードの検出に応じて、解凍方法は、そのコードワードに関連して圧縮データ内に存在するワードを解凍データとして出力する。完全一致のコードワードの検出に応じて、解凍方法は、ルックバックテーブルエントリを検索するためにそのコードワードに関連して圧縮データ内に存在する出力インデックスを使用し、次いで、解凍方法がその出力インデックスを解凍データとして出力する。部分一致のコードワードの検出に応じて、解凍方法は、ルックバックテーブルエントリを検索するためにそのコードワードに関連して圧縮データ内に存在する出力インデックスを使用して、次いで、解凍方法がそのコードワードに関連して圧縮データ内に存在する部分ワードと関連して出力する。たとえば、入力ワードが32ビットからなる実施形態では、解凍方法は、解凍出力を形成するために、ルックバックテーブルエントリから検索された10LSB〜22MSBを表す部分ワードを付加する。
【００４５】
処理システム100(図1)は、たとえば、図7に示されるポータブル通信デバイス700などの、任意の適切なタイプのデバイスを表してもよく、それに含まれてもよい。ポータブル通信デバイス700は、中央処理装置(「CPU」)704を含むオンチップシステム702を含む。アナログ信号プロセッサ706は、CPU704に結合される。CPU704は、上述した圧縮およびキャッシング方法に関して上述したように動作するように構成され得る。ディスプレイコントローラ708およびタッチスクリーンコントローラ710は、CPU704に結合される。オンチップシステム702の外部のタッチスクリーンディスプレイ712は、ディスプレイコントローラ708およびタッチスクリーンコントローラ710に結合される。たとえば、位相反転線(「PAL」)エンコーダ、sequential couleur avec memoire(「SECAM」)エンコーダ、全国テレビジョン方式委員会(「NTSC」)エンコーダ、または他の任意のビデオエンコーダなどのビデオエンコーダ714は、CPU704に結合される。さらに、ビデオ増幅器716は、ビデオエンコーダ714およびタッチスクリーンディスプレイ712に結合される。ビデオポート718は、ビデオ増幅器716に結合される。USBコントローラ720は、CPU704に結合される。USBポート722は、USBコントローラ720に結合される。メモリ104(図1)に関して上述したように動作することができるメモリ724は、CPU704に結合される。加入者識別モジュール(「SIM」)カード726、およびデジタルカメラ728も、CPU704に結合され得る。例示的な態様では、デジタルカメラ728は、電荷結合素子(「CCD」)カメラ、または相補型金属酸化膜半導体(「CMOS」)カメラである。
【００４６】
ステレオオーディオコーデック730は、アナログ信号プロセッサ706に結合され得る。また、オーディオ増幅器732は、ステレオオーディオコーデック730に結合され得る。例示的な態様では、第1のステレオスピーカ734および第2のステレオスピーカ736は、オーディオ増幅器732に結合される。さらに、マイクロフォン増幅器738は、ステレオオーディオコーデック730に結合され得る。マイクロフォン740は、マイクロフォン増幅器738に結合され得る。特定の態様では、周波数変調(「FM」)ラジオチューナ742は、ステレオオーディオコーデック730に結合され得る。また、FMアンテナ744は、FMラジオチューナ742に結合される。さらに、ステレオヘッドフォン746は、ステレオオーディオコーデック730に結合され得る。
【００４７】
無線周波数(「RF」)トランシーバ748は、アナログ信号プロセッサ706に結合され得る。RFスイッチ750は、RFトランシーバ748とRFアンテナ752との間に結合され得る。RFトランシーバ748は、全地球測位システム(「GPS」)衛星と同様に、モバイル電話ネットワークなどの従来の地上通信ネットワークと通信するように構成され得る。
【００４８】
マイクロフォン756を有するモノラルヘッドセットは、アナログ信号プロセッサ706に結合され得る。さらに、バイブレータデバイス758は、アナログ信号プロセッサ706に結合され得る。電源760は、オンチップシステム702に結合され得る。特定の態様では、電源760は、電力を必要とするポータブル通信デバイス700の様々な構成要素に電力を供給する直流(「DC」)電源である。さらに、特定の態様では、電源は、充電式DCバッテリ、または交流(「AC」)からAC電源に接続されたDC変圧器へと誘導されるDC電源である。
【００４９】
キーパッド754は、アナログ信号プロセッサ706に結合され得る。タッチスクリーンディスプレイ712、ビデオポート718、USBポート722、カメラ728、第1のステレオスピーカ734、第2のステレオスピーカ736、マイクロフォン740、FMアンテナ744、ステレオヘッドフォン746、RFスイッチ750、RFアンテナ752、キーパッド754、モノラルヘッドセット756、バイブレータ758、および電源760は、オンチップシステム702の外部にある。
【００５０】
本明細書に記載された方法ステップ(図2および図3に関して上述したような)は、コンピュータプログラム命令の形態でメモリ724に記憶され得る。これらの命令は、本明細書で説明される方法を実行するためにCPU704または別のプロセッサによって実行され得る。
【００５１】
代替の実施形態は、その趣旨および範囲から逸脱することなしに、本発明が属する技術分野の当業者には明らかになるであろう。したがって、選択された態様が図示され詳細に説明されてきたが、以下の特許請求の範囲によって定義されるように、本発明の趣旨および範囲から逸脱することなく、各態様において様々な置換および改変が行われてよいことが理解されよう。
【符号の説明】
【００５２】
102  プロセッサ
104  システムメモリ
106  相互接続
108  データ圧縮ロジック
110  入力ロジック
112  エントロピー符号化ロジック
114  ランレングスロジック
116  ルックバックテーブルロジック
118  出力ロジック
120  入力データ
122  出力データ
400  ルックバックテーブル構造
500  ルックバックテーブル
502  部分
610  出力ストリームの一部
612  コードワード
614  入力ワード
622  出力ストリームの一部
624  部分的に一致する入力ワードのデータタイプに対して生成されたコードワード
626  入力ストリーム内の入力ワードの場所の表示
628  入力ワードの不一致部分
700  ポータブル通信デバイス
702  オンチップシステム
704  中央処理装置(「CPU」)
706  アナログ信号プロセッサ
708  ディスプレイコントローラ
710  タッチスクリーンコントローラ
712  タッチスクリーンディスプレイ
714  ビデオエンコーダ
716  ビデオ増幅器
718  ビデオポート
720  USBコントローラ
722  USBポート
724  メモリ
726  加入者識別モジュール(「SIM」)カード
728  デジタルカメラ
728  カメラ
730  ステレオオーディオコーデック
732  オーディオ増幅器
734  第1のステレオスピーカ
736  第2のステレオスピーカ
738  マイクロフォン増幅器
740  マイクロフォン
742  周波数変調(「FM」)ラジオチューナ
744  FMアンテナ
746  ステレオヘッドフォン
748  無線周波数(「RF」)トランシーバ
750  RFスイッチ
752  RFアンテナ
754  キーパッド
756  マイクロフォン
758  バイブレータデバイス
758  バイブレータ
760  電源
【図１】
2018521537.tif 000003
【図２】
2018521537.tif 000004
【図３】
2018521537.tif 000005
【図４】
2018521537.tif 000006
【図５】
2018521537.tif 000007
【図６Ａ】
2018521537.tif 000008
【図６Ｂ】
2018521537.tif 000009
【図６Ｃ】
2018521537.tif 000010
【図６Ｄ】
2018521537.tif 000011
【図７】
2018521537.tif 000012
【国際調査報告】
2018521537.tif 000013
2018521537.tif 000014