データ圧縮
【課題】ターミナルサービス環境において通信を行うためのデータ圧縮を提供する。
【解決手段】データ内の初期シーケンスと一致するＬＵＴ内のインデックスを見つけることでデータを圧縮する。ＬＵＴは複数のエントリを含み、各エントリは複数のインデックスの内の特定の１つを使用して発見できる。各エントリは対応するインデックスがヒストリバッファ内に置かれているかどうかを示す参照であり、もし置かれていれば、ヒストリバッファ内の対応するインデックスの１つまたは複数の位置を示す参照となる。マッチングインデックスの対応するエントリが複数の位置を参照している場合、各位置についてマッチングインデックスがあるシーケンスを初期シーケンスを含むデータ内のシーケンスと比較する。マッチングシーケンスは、複数の位置のそれぞれにあるシーケンスの長さ及び位置に基づく比較から導かれる。
【解決手段】データ内の初期シーケンスと一致するＬＵＴ内のインデックスを見つけることでデータを圧縮する。ＬＵＴは複数のエントリを含み、各エントリは複数のインデックスの内の特定の１つを使用して発見できる。各エントリは対応するインデックスがヒストリバッファ内に置かれているかどうかを示す参照であり、もし置かれていれば、ヒストリバッファ内の対応するインデックスの１つまたは複数の位置を示す参照となる。マッチングインデックスの対応するエントリが複数の位置を参照している場合、各位置についてマッチングインデックスがあるシーケンスを初期シーケンスを含むデータ内のシーケンスと比較する。マッチングシーケンスは、複数の位置のそれぞれにあるシーケンスの長さ及び位置に基づく比較から導かれる。
【発明の詳細な説明】
【背景技術】
【０００１】
本発明は、一般に、データ圧縮の分野に関するものであり、より具体的には、データ圧縮のためのシステム、サーバ、方法、およびコンピュータ読み取り可能な媒体に関するものである。
【０００２】
増大の一途を辿るデータへのアクセスに使用される方法は、ますます多様化する一方である。例えば、ユーザは、Ｗｅｂサイトにアクセスして、コンサートイベントの放送、つまりＷｅｂ放送を受信することができる。さらに、ゲームおよびその他のアプリケーションについても、携帯電話を利用して無線ネットワーク経由でアクセスすることができる。このようなデータをユーザに提供するために、クライアントによるレンダリングのためにネットワーク経由でサーバからクライアントへデータをストリーミング配信することができる。ユーザは、その後、映画を見る、歌を聴くなどにより、レンダリングされたデータと対話することができる。
【０００３】
データのストリーミング配信（Ｓｔｒｅａｍｉｎｇ ｄａｔａ）は、ユーザがデータをすばやく受信できるような機能性の向上をユーザに提供する。ストリーミング配信でなければ、クライアントがデータを出力する前にサーバからデータの全量を受信する必要がある場合には、クライアント側でデータをレンダリングする際に、ユーザは遅れを感じるかもしれない。データをストリーミング配信することにより、ユーザが遭遇する遅延を減らすことができる。データのストリーミング配信は、データの「リアルタイム」レンダリングを提供するために使用することができる。
【０００４】
データをストリーミング配信するために、一般的にはパケットを使用して、データをストリーミング配信でまたは連続的にサーバから伝送し、その後、データを含むファイル全体がクライアント側で使用可能になるまでレンダリングされないデータとは対照的に、データが到着したときにクライアント側でレンダリングする。ビデオデータ、オーディオデータ、メディアデータなどのさまざまな種類のデータにストリーミング配信を使用できる。ビデオデータのストリームは、伝送され、イメージが到達したときにレンダリングされる「動画」のシーケンスを提供する。同様に、オーディオデータのストリームは、オーディオデータが到着したときに再生される音声データを提供する。メディアデータのストリームは、オーディオデータとビデオデータの両方を含む。
【０００５】
ストリーミングデータは、圧縮することにより、ネットワーク経由でデータをサーバからクライアントに効率よくストリーミング配信し、ストリーミング配信されたデータの有用性を高めることができる。例えば、通信によりサーバをクライアントに接続するネットワークは、帯域幅が限られていることがある。帯域幅が限られていると、サーバからクライアントに一時に通信できるデータの量が制限される場合があり、したがって、ネットワーク経由でデータをストリーミング配信したときにクライアントに提供される機能も制限される場合がある。例えば、ストリーミング配信されるビデオデータは、高帯域幅ネットワークが使用される場合の解像度に比べて、帯域幅が限られているためより低い解像度に制限されることがある。したがって、より高い解像度のストリーミングビデオデータを望むユーザは、否応なくさらに高い帯域幅の接続に投資せざるを得ない。ストリーミングデータを圧縮することにより、低い帯域幅のネットワーク経由で一度により多くのデータを転送することができ、したがって、ストリーミング配信されたデータの有用性が向上する。
【０００６】
しかし、ストリーミングデータを圧縮する場合、データの集合全体の圧縮、例えばブロック圧縮とは対照的に、厄介な問題が加わることがある。例えば、映画全体を一度に圧縮するには、圧縮ルーチンが、データを圧縮するために、その映画を構成する全データ量を調べる場合がある。圧縮ルーチンは、映画を構成するデータ全体を通して含まれる共通のシーケンスの表現を提供することができる。しかし、ストリーミングデータは、データの「リアルタイム」レンダリングのために供給される。したがって、クライアントによるデータのリアルタイムレンダリングを提供するために、ストリーミングデータを分析する時間は、制限される可能性がある。さらに、共通のシーケンスの表現を提供するために、常に比較に利用できるデータの量も限られることがある。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
したがって、データ圧縮に対する継続的な必要性がある。
【課題を解決するための手段】
【０００８】
データ圧縮について説明する。
一実施例では、クライアントからのリモートアクセスの要求に応じて送信されたデータや、ターミナルサービス環境でのデータなどをクライアントにストリーミング配信するために、データを圧縮する圧縮モジュールがサーバにより実行される。圧縮モジュールは、クライアントにすでにストリーミング配信されているデータを含むヒストリバッファを使用する。圧縮モジュールは、実行されると、ストリーミング配信されるデータ内のシーケンスとヒストリバッファ内の１つまたは複数のシーケンスとを比較して、マッチングシーケンスを見つける。ヒストリバッファ内のシーケンスの位置を特定するために、複数のインデックスのうちの１つでそれぞれ発見可能な複数のエントリを有するルックアップテーブルを使用する。これらのエントリのそれぞれは、対応するインデックスがヒストリバッファ内に置かれているかどうかを示す参照であり、もし置かれていれば、さらに、ヒストリバッファ内の対応するインデックスの１つまたは複数の位置を示す参照となる。したがって、圧縮モジュールは、ストリーミング配信されるデータ内の初期シーケンスをルックアップテーブルのインデックスとして使用し、ヒストリバッファ内のマッチングインデックスを見つけることができる。その後、データ内のマッチングシーケンスは、ヒストリバッファ内のマッチングシーケンスの位置および長さを記述する表現で置き換えられ、これによりクライアントにストリーミング配信する圧縮データを形成することができる。
【０００９】
他の実施例では、方法は、サーバにより提供されるターミナルサービスからデータをクライアントにネットワーク経由で通信するためにリソースが使用可能かどうかを示すフィードバックを受け取ること、およびそのフィードバックに応じて、データを圧縮するために使用される圧縮ルーチンの１つまたは複数のパラメータをチューニングすることを含む。
【００１０】
さらに他の実施例では、方法は、サーバを通じて利用可能なアプリケーションまたはファイルへのリモートアクセスの要求をクライアントからサーバで受け取ることを含む。ネットワーク経由で、その要求に応じてデータを伝達するためにリソースが使用可能であるかどうかが判別される。データを圧縮するために使用される圧縮ルーチンの１つまたは複数のパラメータは、上記判別されたリソースの使用可能性に基づいてチューニングされる。
【００１１】
なお、説明の中の例において、同じ参照番号は、類似の構造およびコンポーネントを参照するために使用する。
【図面の簡単な説明】
【００１２】
【図１】データがネットワーク経由でサーバからクライアントへストリーミング配信される環境を示す一実施例の図である。
【図２】図１のサーバおよびクライアントをさらに詳細に示している一実施例の図である。
【図３】ストリーミング配信するデータを圧縮用に構成する例示的な手順を示す流れ図である。
【図４】ストリーミング配信されるパケットへの参照を含むように構成されている図３のルックアップテーブルを使用してパケットを圧縮する例示的な手順を示す流れ図である。
【図５】伸張モジュールを実行することを通じてクライアントにより図４の圧縮されたパケットを伸張する一実施例の手順を示す流れ図である。
【図６】ストリーミング配信されるデータを含めるためヒストリバッファにおいてスライディングウィンドウが使用される一実施例の図である。
【図７】ストリーミングデータの圧縮をさらに最適化する一実施例の手順を示す流れ図である。
【図８】データ圧縮をさらに最適化するためにシーケンスの比較が最適化される一実施例の図である。
【図９】システムから受け取ったフィードバックに応じて圧縮が動的にチューニングされる一実施例のシステムの図である。
【発明を実施するための形態】
【００１３】
・概要
データ圧縮について説明する。一実施例では、圧縮モジュールは、サーバからクライアントへストリーミング発信するデータを圧縮するためサーバにより実行される。圧縮モジュールは、クライアントにすでにストリーミング配信されているデータを含むヒストリバッファを使用する。圧縮モジュールは、実行時に、ストリーミング配信されるデータ内のシーケンスとヒストリバッファ内の１つまたは複数のシーケンスとを比較して、マッチングシーケンスを見つける。ヒストリバッファ内のシーケンスの位置を特定するために、複数のエントリを有するルックアップテーブルが使用される。これらのエントリはそれぞれ、複数のインデックスのうちの特定の１つを使用して発見可能である。各エントリは、対応するインデックスがヒストリバッファ内に置かれているかどうかを示す参照であり、もし置かれていれば、さらに、ヒストリバッファ内の対応するインデックスの１つまたは複数の位置を示す参照となる。したがって、圧縮モジュールは、ストリーミング配信されるデータ内の初期シーケンスをルックアップテーブルのインデックスとして使用し、エントリを１つ見つけることができる。このようにして、圧縮モジュールは、ヒストリバッファ内の各シーケンスをストリーミング配信されるデータ内のシーケンス毎に別々に比較することなく、初期シーケンスを有するヒストリバッファ内でそれぞれの位置をすばやく特定することができる。
【００１４】
マッチングインデックスの対応するエントリが複数の位置を参照している場合、圧縮モジュールは、マッチングインデックスがある各位置のシーケンスを初期シーケンスを含むデータ内のシーケンスと比較することによりマッチングシーケンスを導出することができる。その後、データ内のマッチングシーケンスは、ヒストリバッファ内のマッチングシーケンスの位置および長さを記述する表現で表すことができる。その後、その表現を含む圧縮データを形成することができる。続いて、圧縮データはクライアントにストリーミング配信される。クライアントは、サーバからクライアントにすでにストリーミング配信されているデータも含んでいるヒストリバッファを使用することにより圧縮データを伸張する。クライアントは、伸張モジュールの実行を通じて、データを再構成するためにその表現により示される長さおよび位置を使用してクライアントのヒストリバッファ内のマッチングシーケンスを見つける。このようにして、データを失うことなくデータの圧縮および伸張を行うことができるような可逆データ圧縮技術が実現される。例えば、ビデオデータは、このデータ圧縮技術を使用することで、データの一部を失わずに、したがってビデオデータの解像度を維持して、圧縮および圧縮解除を行うことができる。
【００１５】
・例示的環境
図１は、データがネットワーク１０６経由でサーバ１０２からクライアント１０４へストリーミング配信される環境１００を示す一実施例の図である。クライアント１０４は、さまざまな方法で構成することができる。例えば、クライアント１０４は、図示されているようなデスクトップコンピュータ、および、移動局、娯楽機器、セットトップボックス、携帯電話などのネットワーク１０６経由で通信することが可能な装置として構成することができる。クライアント１０４は、さらに、クライアント１０４を操作する人および／またはエンティティ（ｅｎｔｉｔｙ）に関係していてもよい。つまり、クライアント１０４は、ユーザおよび／またはマシンを含む論理クライアントを記述しているとすることができる。１つのクライアント１０４が図示されているが、複数のクライアントをネットワーク１０６に通信可能に接続することができる。ネットワーク１０６は、インターネットとして図示されているが、さらに、イントラネット、有線または無線電話網などのさまざまな他のネットワークを含むこともできる。
【００１６】
サーバ１０２は、ネットワーク１０６経由でデータをクライアント１０４にストリーミング配信するように構成されている。サーバ１０２は、クライアント１０４によるレンダリングのために、さまざまなストリーミングデータを供給する。一実施例では、サーバ１０２は、クライアント１０４にストリーミング配信されるコンサートのＷｅｂ放送を提供することができる。クライアント１０４によりレンダリングされると、ユーザはそのＷｅｂ放送を視聴できる。他の実施例では、クライアント１０４は、このクライアント１０４により出力するために、サーバ１０２からストリーミング配信される楽曲を含むデータを受信することができる。
【００１７】
さらなる実施例では、サーバ１０２は、さらに、リモートアプリケーション実行用のターミナルサービス（ｔｅｒｍｉｎａｌ ｓｅｒｖｉｃｅｓ）を提供することもできる。例えば、サーバ１０２は、複数のアプリケーション１０８（１）、…、１０８（ｎ）、…、１０８（Ｎ）を含むことができるが、ただし、「ｎ」は２から「Ｎ」までの任意のアプリケーションとすることができる。アプリケーション１０８（１）〜１０８（Ｎ）はそれぞれ、サーバ１０２上で実行される。サーバ１０２は、ネットワーク１０６経由で、アプリケーション１０８（１）〜１０８（Ｎ）を実行することを通じて供給される画面情報をクライアント１０４にストリーミング配信する。例えば、画面情報は、オペレーティングシステムにより与えられるデスクトップの表示、およびワードプロセッサの実行に関係する情報を表示するウィンドウ、ならびにオペレーティングシステムおよび／またはワードプロセッサにより与えられるオーディオ情報も含むことができる。
【００１８】
サーバ１０２からストリーミング配信される画面情報は、ユーザが見られるようにクライアント１０４によりレンダリングされる。ユーザは、クライアント１０４と対話し、マウス１０８および／またはキーボード１１０などのクライアント１０４の入力デバイスを使用して入力することができる。入力は、キーボード１１０を使用することにより供給される、ワードプロセッサ用のテキスト入力などのレンダリングされた画面情報に対応することができる。それらの入力は、ネットワーク１０６経由でクライアント１０４からサーバ１０２へ通信される。入力は、サーバ１０２により受信されると、複数のアプリケーション１０８（１）〜１０８（Ｎ）を実行するときに使用することができる。例えば、ワードプロセッサは、ドキュメントに含めるためにテキスト入力を受け、画面情報をクライアント１０４にストリーミング配信して、このテキストを含むドキュメントを示すことができる。サーバ１０２上でのアプリケーション１０８（１）〜１０８（Ｎ）の実行と、画面情報のクライアント１０４へのストリーミング配信を通じて、クライアント１０４は、クライアント１０４自体では他の方法だと利用できない機能を利用することができる。
【００１９】
例えば、クライアント１０４は、例えば、限られた処理および／またはメモリリソースを有する「シン」クライアントとして構成することができる。しかし、サーバ１０２は、例えば、クライアント１０４よりも処理および／またはメモリリソースの量をより多くもたせることにより、機能を豊富にすることができる。したがって、サーバ１０２は、クライアント１０４では実行できない、および／またはクライアント１０４で実行すると低速となるアプリケーションを実行することができる。サーバ１０２は、画面情報をクライアント１０４に送信することによりアプリケーション１０８（１）〜１０８（Ｎ）の１つまたは複数の実行結果をクライアント１０４に送り、ネットワーク１０６経由でクライアントから入力を受け取る。このようにして、処理リソース、メモリリソース、および複数のアプリケーション１０８（１）〜１０８（Ｎ）など、サーバ１０２が備える機能を、他の方法だとこの機能を利用できないクライアント１０４に提供することができる。
【００２０】
ネットワーク経由でサーバ１０２とクライアント１０４間の通信を提供するために、サーバ１０２とクライアント１０４は、それぞれ、リモートデスクトッププロトコル（ＲＤＰ）１１２、１１４を実装することができる。ＲＤＰ １１２、１１４は、すでに説明したようにアプリケーション１０８（１）〜１０８（Ｎ）に対しネットワーク接続を介したリモート表示および入力機能を提供するように設計されている。例えば、ＲＤＰを使用することにより、サーバ１０２からクライアント１０４にデバイス通信（ｄｅｖｉｃｅ ｃｏｍｍｕｎｉｃａｔｉｏｎ）およびプレゼンテーションデータを搬送する個別の仮想チャネルとともに、クライアント１０４からサーバ１０２に通信される暗号化された入力を可能にする。
【００２１】
ＲＤＰ １１２、１１４は、さらに、圧縮および伸張モジュール１１６、１１８をサーバ１０２およびクライアント１０４のそれぞれに含めることにより帯域幅を削減することもできる。圧縮モジュール１１６はＲＤＰ １１２の実装を通じてサーバ１０２により実行され、ネットワーク１０６経由でストリーミング配信する前にデータを圧縮することができる。同様に、伸張モジュール１１８はＲＤＰ １１４の実装を通じてクライアント１０４により実行されることにより、ネットワーク１０６経由でサーバ１０２からストリーミング配信された圧縮データを伸張することができる。
【００２２】
圧縮および伸張モジュール１１６、１１８は、実行時にそれぞれ、ネットワーク１００６経由でストリーミング配信されるデータの圧縮および伸張を行う。すでに述べたように、ストリーミングデータの圧縮および伸張では、一度にデータセット全体の圧縮および伸張を行うのとは対照的に、つまりブロック圧縮とは対照的に、独自の複雑な状況をもたらす場合がある。例えば、データは「リアルタイム」でストリーミング配信することができるため、データのストリーミング配信に遅延が生じるとデータの有用性を低下させる場合がある。圧縮および伸張モジュール１１６、１１８では、ストリーミングデータの独自の複雑な状況に対処し、それにより、図３から５に関してさらに詳しく説明されているように、ネットワーク１０６経由で圧縮データのストリーミング配信を提供する。
【００２３】
ターミナルサービス（ＴＳ）を使用することにより、クライアント１０４は、サーバ１０２にインストールされているアプリケーション１０８（１）〜１０８（Ｎ）のうちの１つまたは複数にアクセスし、サーバ１０２上のアプリケーションを実行し、クライアント１０４上にそのアプリケーションのユーザインターフェイス（ＵＩ）を表示することができる。アプリケーション１０８（１）〜１０８（Ｎ）はサーバ１０２上で実行されるため、ＴＳにより、クライアント１０４は、クライアント１０４がクライアント１０４自体でリソースをローカルで実行するのに適したハードウェアおよびソフトウェアを有しているかどうかに関係なく、企業インフラのリソースを活用することができる。
【００２４】
クライアント１０４は、複数のアプリケーション１０８（１）〜１０８（Ｎ）がサーバ１０２により実行されるターミナルサービス環境で説明しているが、クライアント１０４は、複数のアプリケーション１２０（１）、…、１２０（ｍ）、…、１２０（Ｍ）のうちの１つまたは複数を実行することもできる。例えば、アプリケーション１２０（１）〜１２０（Ｍ）のうちの１つは、ユーザが見るために表示するデータをレンダリングし、マウス１０８および／またはキーボード１１０などのユーザからの入力を受け取るためにＲＤＰ １１４とともに利用されるインターフェイスを備えることができる。さらに、圧縮および伸張モジュール１１６、１１８は、それぞれのＲＤＰ １１２、１１４の一部として図示されているが、圧縮および伸張モジュール１１６、１１８は、それぞれストリーミングデータの圧縮および伸張のため実行されるスタンドアロンのソフトウェアコンポーネントとして構成することができる。
【００２５】
さらに、以下の説明の一部では、ターミナルサービス環境における圧縮の使用について説明しているが、本明細書で説明している圧縮および伸張技術は、他のさまざまな環境でも利用することができる。例えば、この圧縮技術を使用することにより、リモートアクセス環境で使用されるデータを圧縮することができる。リモートアクセスとは、遠く離れた場所からコンピュータまたはネットワークにアクセスできることを表す。例えば、企業の遠隔地にある事務所では、企業のネットワークにアクセスすることを所望し、リモートアクセスを利用して、電話回線網、インターネットなどを経由し、そこに収容されているファイルおよびアプリケーションにアクセスする場合がある。サーバ１０２は、ネットワークにリモートでアクセスすることを求めているクライアントを処理するためにセットアップされている関連ソフトウェアを有するリモートアクセスサーバとして構成することができる。一実施例では、リモートアクセスサーバは、セキュリティ用のファイヤウォールサーバおよびリモートアクセス要求をネットワークの他の部分に転送するルータを含む。リモートアクセスサーバは、さらに、仮想プライベートネットワーク（ＶＰＮ）の一部として使用することもできる。
【００２６】
図２は、図１のサーバ１０２およびクライアント１０４をさらに詳しく示している一実施例２００の図である。サーバ１０２は、プロセッサ２０２およびメモリ２０４を備える。ＲＤＰ １１２およびその個別の圧縮モジュール１１６は、プロセッサ２０２上で実行されているように例示され、メモリ２０４に格納可能である。同様に、クライアント１０４は、プロセッサ２０６およびメモリ２０８を備える。ＲＤＰ １１４およびその個別の伸張モジュール１１８は、プロセッサ２０６上で実行されているように例示され、メモリ２０８に格納可能である。
【００２７】
サーバ１０２からクライアント１０４にストリーミング配信されるべきデータは、ビデオカメラ、マイクなどの入力デバイス２１０から受け取った、アプリケーション１０８（１）〜１０８（Ｎ）のうちの１つまたは複数の実行など、さまざまなソースから供給することができる。圧縮モジュール１１６は、サーバ１０２のプロセス２０２上で実行され、クライアント１０４にストリーミング配信するデータを圧縮する。そのデータは、サーバ１０２からクライアント１０４へパケットでストリーミング配信することができる。
【００２８】
例えば、圧縮モジュール１１６は、所与の長さの未圧縮のシーケンスを有するデータを受け取り、そのシーケンスを、より小さな（現在圧縮されている）長さに圧縮すること、例えばバイト数、ビット数などを減らすことを試みることができる。圧縮モジュール１１６は、シーケンスを、置き換えられるシーケンスに比べて格納時に使用されるメモリリソースが少なくて済む、例えばバイト数の少ない表現で置き換えることにより、パケット毎にデータを圧縮することができる。
【００２９】
圧縮モジュール１１６がシーケンスを圧縮できる場合、圧縮データがＲＤＰ接続の終点、つまりクライアント１０４のＲＤＰ １１４に送信される。伸張モジュール１１８はクライアント１０４により実行され、圧縮データを伸張してデータを再構成する。圧縮モジュール１１６がデータを圧縮できない場合、データは、非圧縮形式で、つまりリテラルシーケンスでクライアント１０４にストリーミング配信することができる。圧縮モジュール１１６は、その後、サーバ１０２により実行され、後続のシーケンスの圧縮を試みることができる。
【００３０】
データを圧縮するために使用される基本オペレーションは、以前にストリーミング配信されたシーケンスとともに圧縮されるデータ内のシーケンスのパターンマッチングを伴う。これを達成するために、圧縮モジュール１１６は、クライアント１０４にすでにストリーミング配信されているデータを収容しているヒストリバッファ２１２を維持する。圧縮モジュール１１６は、実行時に、ストリーミング配信されるデータ内のシーケンスとすでにクライアント１０４にストリーミング配信されているデータに含まれる１つまたは複数のシーケンスとを照合する。その後、ヒストリバッファ内のシーケンスと一致するストリーミング配信されるデータ内のシーケンスは、ヒストリバッファ２１２内のマッチングシーケンスを参照する１つまたは複数の表現を使用して表現することができる。これらの表現は、より小さい、つまり、圧縮する実際のシーケンス、すなわちマッチングシーケンスを格納するために使用されるメモリリソースよりも、使用するメモリリソースをより少なくすることができる。このことは、ストリーミング配信されるデータに含まれるデータの量を有効に低減する。
【００３１】
ヒストリバッファ２１２を使用したパターンマッチングの基本例を例示するために、ヒストリバッファ２１２は、以下のシーケンスを含むと仮定する。
１ ２ ７ ４ ５ ６ ３ ９ ４ ５ １ ４ ９ １
圧縮モジュール１１６は、サーバ１０２のプロセッサ２０２上で実行され、以下のシーケンスを受け取る。
４ ５ ９ ７ ４ ５ ６ ３ ９ ４ ５ １ ４ ６
圧縮モジュール１１６は、実行時に、圧縮されるデータ内のシーケンスと一致するヒストリバッファ内で最長のシーケンス、つまりマッチングシーケンス（ｍａｔｃｈｉｎｇ ｓｅｑｕｅｎｃｅ）を見つける。この場合、ヒストリバッファ内に現れるマッチングシーケンスは、以下では太字で示されている。マッチングシーケンスは、長さ１０バイトで、ヒストリバッファ２１２の先頭から３バイトのところで始まる（左から開始し、０からカウントする）。
【００３２】
【数１】
【００３３】
したがって、圧縮モジュール１１６は、実行時に、ストリーミング配信されるデータを以下のように表現することにより、圧縮データを作成することができる。
４ ５ ９ （バッファの先頭から３バイトのところで始まる長さ１０バイトの一致）
６
サーバ１０２では、ヒストリバッファ内のマッチングシーケンスを参照することにより、クライアント１０４にすでにストリーミング配信されているシーケンスを再送する必要はない。それ故に、圧縮モジュール１１６は、ストリーミング配信されるデータ内の繰り返しパターンを見つけて、この繰り返しパターン、つまりマッチングシーケンスを、ネットワーク１０６経由で送信されたときに使用するメモリリソースおよび帯域幅がより少ない表現で置き換えることにより、ストリーミング配信されるデータを圧縮する。
【００３４】
圧縮データを伸張するために、クライアント１０４は、伸張モジュール１１８およびヒストリバッファ２１４を備える。クライアント１０４のヒストリバッファ２１４は、サーバ１０２のヒストリバッファ２１２のように、すでにストリーミング配信されているデータを格納する。したがって、伸張モジュール１１８は、クライアント１０４により実行されると、ヒストリバッファ２１４を使用することによりクライアント１０４にストリーミング配信されている圧縮データを伸張することができる。前の実施例の続きとして、クライアント１０４が以下のように示されている圧縮データを受け取ると仮定する。
４ ５ ９ （バッファの先頭から３バイトのところで始まる長さ１０バイトの一致）
６
伸張モジュール１１８は、圧縮データに含まれる表現に基づき、実行時に、ヒストリバッファ２１４から圧縮されたシーケンスを取り出すことができ、これは、以下のように太字で示される。
【００３５】
【数２】
【００３６】
こうして、伸張モジュール１１８は、ヒストリバッファ２１４を使用して圧縮された文字列を伸張することができる。
【００３７】
サーバ１０２は、ヒストリバッファ２１２内でマッチングシーケンスを見つけるためのルックアップテーブル２１６を備えることもできる。例えば、ルックアップテーブル２１６は、複数のインデックスのうちの対応する１つによりそれぞれ発見可能な複数のエントリを含むことができる。それぞれのエントリは、対応するインデックスを有するヒストリバッファ２１２内の各位置を記述する。したがって、圧縮モジュール１１６は、サーバ１０２により実行されると、ルックアップテーブル２１６を使用することによりヒストリバッファ２１２内の特定のシーケンスをすばやく特定することができる。ルックアップテーブル２１６およびヒストリバッファ２１２についてのさらなる検討は、図３〜４の関連で見出すことができる。
【００３８】
サーバ１０２は、ハフマン符号化、算術符号化、プレフィクス符号化（Ｐｒｅｆｉｘ ｅｎｃｏｄｉｎｇ）、およびマルコフ符号化などの符号化技術を使用して、ストリーミング配信用にデータをさらに圧縮することもできる。例えば、ストリーミング配信されるデータは、ヒストリバッファ内のシーケンスと一致しないシーケンスを含むことができる。これらのシーケンスは、「リテラル」シーケンス（“ｌｉｔｅｒａｌ”ｓｅｑｕｅｎｃｅｓ）と呼ばれる。ハフマン符号化を使用して、データ内のリテラルシーケンスの一部または全部を圧縮すると、データをさらに圧縮することができる。例えば、ハフマン符号化は、さらに圧縮するそれぞれのリテラルシーケンスの出現度数を関連付ける出現度数テーブルから始めることができる。出現度数ケーブルは、データ自体および／または代表データから生成することができる。例えば、すでにストリーミング配信されているパケットを処理することでリテラルシーケンスの出現度数を求め、その後それを利用して、それぞれの後続のパケットを処理することができる。
【００３９】
例えば、可変長文字列を、一意的なプレフィクス（ｐｒｅｆｉｘ）などのその特定のリテラルシーケンスを一意に表すそれぞれのリテラルシーケンスに割り当てることができる。その後、その可変長文字列をツリー状に配列して、各リテラルシーケンスおよび表現をそれぞれ符号化および復号化する。リテラルシーケンスを符号化するために、符号化されるリテラルシーケンスをツリー内に配置する。リテラルシーケンスを含む葉を特定するために使用されるツリーの枝を利用して、リテラルシーケンスを符号化する、つまり、リテラルシーケンスの表現を与える。例えば、ハフマン符号化に使用されるツリーの各枝には出力アルファベットの記号、例えば、ビット０と１がマークされ、符号化は、ツリーのルートから符号化されるリテラルシーケンスまでの経路上の枝マーキングの列挙となる。各表現の復号化は、リテラルシーケンスを含むツリーの葉に到達するまで、可変長文字列内のそれぞれの連続する値に基づいて、ツリーをその原点から枝を通り下ってツリーの葉へと縦走（ｔｒａｖｅｒｓｉｎｇ）することによって行われる。
【００４０】
リテラルシーケンスのハフマン符号化について説明してきたが、ハフマン符号化を使用することによりさらにさまざまなデータを圧縮することができる。例えば、ハフマンテーブル２１８では、リテラル２２２シーケンスおよびバックポインタ２２４の両方を符号化することができる。リテラルシーケンスは、すでに説明しているように、ヒストリバッファ２１２内に見つからないシーケンスを含む。したがって、ハフマンテーブル２１８を使用することで、リテラル２２２シーケンスを圧縮することができる。ハフマンテーブル２１８を利用してバックポインタ２２４も圧縮できる。バックポインタ２２４は、ヒストリバッファ２１２内の特定のシーケンスの位置を記述する。例えば、すでに説明しているように、ヒストリバッファ２１２内のシーケンスと一致するデータ内のシーケンス、つまりマッチングシーケンスは、「バッファの先頭からＹバイトのところで始まる長さＸバイトの一致」として記述することができる。バックポインタ２２４は、ヒストリバッファ２１２内のマッチングシーケンスの位置、つまりＹバイトを記述する。ハフマンテーブル２２０を使用することにより、マッチングシーケンスの長さ分２２６、つまりＸバイト分を圧縮することができる。
【００４１】
サーバ１０２からクライアント１０４にストリーミング配信された圧縮データを伸張するために、それぞれサーバ１０２のハフマンテーブル２１８、２２０に対応するハフマンテーブル２２８、２３０を使用して、クライアント１０４により、伸張モジュール１１６が実行される。例えば、ハフマンテーブル２２８は、リテラル２３２シーケンスおよびバックポインタ２３４を伸張するために使用でき、一方、ハフマンテーブル２３０は、マッチングシーケンスの長さ２２６を伸張するために使用することができる。ハフマンテーブルのさらなる検討は、図７の関連で見出すことができる。
【００４２】
サーバ１０２およびクライアント１０４は、さらに、それぞれＬＲＵ（ｌａｓｔ ｒｅｃｅｎｔｌｙ ｕｓｅｄ：最も長い間参照されていない）テーブル２３６、２３８を含むこともできる。ＬＲＵテーブル２３６、２３８はそれぞれ、バックポインタが「最も長い間参照されていない」バックポインタのうちの１つであったかどうかに基づきバックポインタをさらに符号化するために使用することができる。例えば、ＬＲＵテーブル２３６は、それぞれ、最後の４つのバックポインタ毎に、ＬＲＵ表現を与えるために使用することができる。ＬＲＵ表現は、ＬＲＵテーブル２３６内で特定のバックポインタを特定するためのインデックスとして使用される。この方法で、繰り返されるバックポインタは、さらに圧縮することができる。ＬＲＵテーブルのさらなる検討は、図７の関連で見出すことができる。
【００４３】
サーバ１０２からクライアント１０４にストリーミング配信されるデータの圧縮について説明しているが、クライアント１０４は、データを圧縮してサーバ１０２にストリーミング配信で送り返すこともできる。さらに、以下では、サーバ１０２からクライアント１０４にストリーミング配信されるパケットに関してデータの圧縮について説明しているが、データのさまざまな集合を使用して、サブパケットバイトシーケンス（ｓｕｂ‐ｐａｃｋｅｔ ｂｙｔｅ ｓｅｑｕｅｎｃｅｓ）、複数パケットなどのデータを圧縮することができる。さらに、以下では、バイトシーケンスについて説明しているが、ビットなど、データ内の他のシーケンスについても考慮されている。
【００４４】
・手順の実施例
図３は、ストリーミング配信するデータを圧縮用に構成する例示的手順３００を示す流れ図である。ブロック３０２で、データがヒストリバッファ２１２に追加される。例えば、ヒストリバッファ２１２は、ネットワーク１０６経由で図２のサーバ１０２からクライアント１０４にストリーミング配信された、かつ／またはストリーミング配信する準備ができている複数のパケット３０４（１）、３０４（２）を含むことができる。他の実施例では、パケット３０４（１）、３０４（２）は、圧縮モジュール１１６の実行によりすでに処理されているデータに対応することができる。
【００４５】
サーバ１０２は、ストリーミング配信されるパケット３０４（３）を受信する。圧縮モジュール１１６は、サーバ１０２により実行されると、パケット３０４（３）をヒストリバッファ２１２に追加し、これによりヒストリバッファは、ストリーミング配信されたパケット３０４（１）、３０４（２）およびストリーミング配信されるパケット３０４（３）を含む。
【００４６】
ブロック３０６で、圧縮モジュール１１６は、サーバ１０２により実行されると、ルックアップテーブル２１６を更新して、追加データ、つまりパケット３０４（３）を参照する。ルックアップテーブル２１６は、「ｋ」を「１」から「Ｋ」までの任意のインデックスとし、複数のインデックス３０８（ｋ）を含むように構成される。インデックス３０８（ｋ）はそれぞれ、ルックアップテーブル２１６内の複数のエントリのうちのそれぞれ１つを発見するために使用される。各エントリは、複数のインデックス３０８（ｋ）のうちの対応する１つがヒストリバッファ２１２内に置かれているかどうかを示す参照であり、もし置かれていれば、ヒストリバッファ２１２内の対応するインデックス３０８（ｋ）の１つまたは複数の位置を示す参照となる。例えば、複数のエントリのうちの１つで、インデックス３０８（ｋ）のうちの対応する１つを持つヒストリバッファ２１２内の複数の位置を参照することができる。複数の位置はそれぞれ、複数のハッシュチェーン３１０（ｋ）のうちの対応する１つの使用を通じて説明されているように、図示されている。
【００４７】
例えば、インデックス３０８（ｋ）は、シーケンス「４ ５」を持つものとして図示されている。ルックアップテーブル２１６内のインデックス３０８（ｋ）の対応するエントリ、つまり、ハッシュチェーン３１０（ｋ）は、ヒストリバッファ２１２内のインデックス３０８（ｋ）「４ ５」の各位置を記述する。例えば、パケット３０４（１）は、図３では、以下のシーケンスを持つものとして図示されている。
０ １ ２ ３ ４ ５ ６ ７
パケット３０４（２）は、図３では、以下のシーケンスを持つものとして図示されている。
８ ９ ４ ５ ３ １ ３ ０
図２のクライアント１０４にストリーミング配信されるパケット３０４（３）は、図３では、以下のシーケンスを持つものとして図示されている。
４ ５ ６ ７ ０ ８ ２ ４
パケット３０４（１）〜３０４（３）は、以下のシーケンスが観察されるようにヒストリバッファ内に順次配列される。
０ １ ２ ３ ４ ５ ６ ７ ８ ９ ４ ５ ３ １ ３ ０ ４ ５ ６
７ ０ ８ ２ ４
ハッシュチェーン３１０（ｋ）は、ヒストリバッファ２１２内のインデックス３０８（ｋ）「４ ５」のそれぞれの位置を記述する。各位置は、さまざまな方法で記述することができる。例えば、これらの位置は、ヒストリバッファ２１２の先頭から数え、番号０から始めたときのシーケンスの第１のバイトの位置として記述することができる。ハッシュチェーン３１０（ｋ）は、ハッシュチェーン３１０（ｋ）内の「１ ６」からパケット３０４（３）の先頭まで図３において点線で示すように、ヒストリバッファ２１２内のシーケンスの先頭から１６バイトのところにあるインデックス３０８（ｋ）「４ ５」の第１の位置を記述する。同様に、ハッシュチェーン３１０（ｋ）は、ハッシュチェーン３１０（ｋ）内の「１ ０」からパケット３０４（２）の第３バイトまで図３において点線で図示されている、ヒストリバッファ２１２内のシーケンスの先頭から１０バイトのところにあるインデックス３０８（ｋ）「４ ５」の第２の位置を記述する。さらに、ハッシュチェーン３１０（ｋ）は、ヒストリバッファ２１２内の４バイトのところにあるインデックス３０８（ｋ）「４ ５」の第３および最終の位置を含む。したがって、ルックアップテーブル２１６は、ヒストリバッファ２１２内のインデックス３０８（ｋ）の各位置、例えば、４、１０、１６を記述するハッシュチェーン３１０（ｋ）を参照する対応するエントリを持つインデックス３０８（ｋ）、例えば「４ ５」を含む。ルックアップテーブル２１６を更新することにより、圧縮モジュール１１６は、実行時に、図４に関して後でさらに詳しく説明するように、より効率的な方法でストリーミング配信されるデータを圧縮することができる。
【００４８】
各インデックス３０８（ｋ）は、図３では、複数のハッシュチェーン３１０（ｋ）のうちの対応する１つを持つものとして図示されているが、インデックス３０８（ｋ）が対応するハッシュチェーンを持たない場合もある。例えば、場合によっては、ヒストリバッファ２１２がインデックスを含まないこともある。したがって、そのインデックスに対応するルックアップテーブル２１６内のエントリは、ハッシュチェーンを含み得ない。言い換えると、そのインデックスに対するハッシュチェーンは値０を持つ、つまり対応するインデックスを含む場所はヒストリバッファ２１２内にはないということである。さらに、複数のハッシュチェーン３１０（ｋ）はそれぞれルックアップテーブル２１６内に含まれるように図示されているが、ハッシュチェーン３１０（ｋ）の１つまたは複数をさまざまな方法で提供することができる。例えば、ルックアップテーブル２１６内の各エントリは、ルックアップテーブル２１６とは別の配列として構成される対応するハッシュチェーンへのポインタを含むことができる。
【００４９】
図４は、ストリーミング配信されるパケット３０４（３）への参照を含むように構成されている図３のルックアップテーブル２１６を使用してパケット３０４（３）を圧縮する例示的手順４００を示す流れ図である。ブロック４０２で、圧縮モジュール１１６は、実行時に、カレントポインタ４０４を、図３のブロック３０２のヒストリバッファ２１２に追加されたデータ、つまりパケット３０４（３）のところで開始する。
【００５０】
ブロック４０６で、圧縮モジュール１１６は、サーバ１０２により実行され、カレントポインタ４０４が指す初期シーケンスと一致するルックアップテーブル２１６内のインデックスを見つける。例えば、圧縮モジュール１１６は、カレントポインタ４０４のところの２バイト、例えば「４ ５」からなる初期シーケンスを使用して、その初期シーケンスと一致する複数のインデックス３０８（ｋ）のうちの１つを見つけることができる。この例では、ルックアップテーブル２１６のインデックス３０８（ｋ）「４ ５」は、ヒストリバッファ２１２内のカレントポインタ４０４が指す初期シーケンス「４ ５」と一致する。インデックス３０８（ｋ）は、ヒストリバッファ２１２内のインデックス「４ ５」３０８（ｋ）の各位置を記述するハッシュチェーン３１０（ｋ）を参照する対応するエントリをルックアップテーブル２１６内に持つ。したがって、その対応するエントリは、ヒストリバッファ２１２内の初期シーケンスの各位置を記述する。
【００５１】
マッチングインデックス３０８（ｋ）の対応するエントリが複数の位置を参照する場合、マッチングインデックス３０８（ｋ）「４ ５」を有するヒストリバッファ２１２内の各位置のシーケンスが、カレントポインタ４０４が指す初期シーケンスを有するデータ内のシーケンスと比較される。例えば、カレントポインタ４０４、つまりヒストリバッファ２１２内の位置「１６」のところの初期シーケンス「４ ５」、およびヒストリバッファ２１２内の位置「１０」にあるシーケンスは、長さ「２」である、つまり、各位置のバイトシーケンス内の先頭２バイトのみで一方を他方と照合する。すでに述べたように、この実施例のハッシュチェーン３１０（ｋ）内の位置は、ヒストリバッファ２１２の先頭から番号０を先頭番号として数えることで記述される。カレントポインタ４０４が指す初期シーケンスおよびヒストリバッファ２１２内の位置「４」のシーケンスは長さ「４」である。つまり、位置「４」にあるバイトシーケンス内の４バイトは、位置「４」のところのシーケンス内の４バイトに一致する。このようにして、マッチングシーケンス「４ ５ ６ ７」は、計算で求められた長さから導かれる。最適なマッチングシーケンスを見つけるために、図７に関してさらに詳しく説明されているように、最大長が計算で求められ、かつ／またはしきい値に達するまで、ハッシュチェーン３１０（ｋ）内の各位置を、圧縮されるデータのシーケンス、つまり、パケット３０４（３）と比較することができる。比較を最適化するため、次のバイトはシーケンス、例えば、初期シーケンスまたはヒストリバッファ２１２内のインデックスの後に続く１バイトを最初に比較することができるが、それは、最初の２バイトが一致すること照合から知られているからである。シーケンス内の「次の」バイトに基づく比較のさらなる検討が、図８の関連で見出すことができる。
【００５２】
ブロック４０８で、マッチングシーケンスは、圧縮データを形成するために使用される表現で表される。例えば、パケット３０４（３）内のマッチングシーケンス「４ ５ ６ ７」は、ヒストリバッファ２１２内のマッチングシーケンスの長さおよびマッチングシーケンスの位置を記述する表現で表すことができる。この表現は、タプル（ｔｕｐｌｅ）、つまり指定された順序を持つ集まりとして形式化でき、｛バックポインタ，長さ｝という形式となる。バックポインタは、マッチングシーケンスの相対的位置をヒストリバッファ２１２内のオフセットとして記述することができる。例えば、バックポインタは、ヒストリバッファ２１２内におけるマッチングシーケンスの絶対的位置とカレントポインタ４０４の絶対的位置との間のオフセットとして相対的位置を記述することができる。この例では、マッチングシーケンスの絶対的位置は、ヒストリバッファ２１２内の位置４であり、カレントポインタ４０４の絶対的位置は、「１６」である。したがって、マッチングシーケンスの相対的位置は、カレントポインタ４０４から１２バイトのところである。長さは、マッチングシーケンスの長さを記述し、例えば「４」である。したがって、パケット３０４（３）を、マッチングシーケンス「４ ５ ６ ７」を表現「｛１２，４｝」で表すことにより圧縮し、圧縮データ、例えば、パケット４１０を形成することができる。他の実施例では、マッチングシーケンスの位置は、ヒストリバッファのマッチングシーケンスの絶対的位置、例えば、位置４から得られる。
【００５３】
こうして、ルックアップテーブル２１６からは、ヒストリバッファ２１２内の各インデックス３０８（ｋ）の各位置が得られる。したがって、圧縮モジュール１１６が実行されると、初期シーケンスのそれぞれの位置を、マッチングシーケンスを見つけるためにヒストリバッファ２１２内で個々のビットまたはバイトを「尋ね歩く」ことをせずに、ヒストリバッファ２１２内で見つけることができる。そのため、圧縮モジュール１１６は、ストリーミング配信されるデータを効率よく圧縮することができる。
【００５４】
図５は、伸張モジュール１２８の実行を通じてクライアント１０４により図４の圧縮されたパケットを伸張する例示的な手順５００を示す流れ図である。ブロック５０２で、クライアント１０４は、図４のサーバからクライアント１０４にストリーミング配信された、圧縮されたデータ、例えばパケット４１０を受け取る。
【００５５】
ブロック５０４で、伸張モジュール１２８は、実行時に、クライアント１０４のヒストリバッファ２１４内のマッチングシーケンスを検出する。クライアント１０４のヒストリバッファ２１４は、サーバ１０２のヒストリバッファ２１２のように、サーバ１０２からクライアント１０４へストリーミング配信されているデータを含めることができる。そのため、圧縮データ、例えばパケット４１０が形成される前に、クライアント１０４のヒストリバッファ２１４は、サーバ１０２のヒストリバッファ２１２と一致する。したがって、伸張モジュール１１８は、実行時に、サーバのヒストリバッファ２１２内のマッチングシーケンスの長さおよび位置を記述する表現からクライアント１０４のヒストリバッファ２１４内のマッチングシーケンスを見つけることができる。前の実施例の続きとして、マッチングシーケンス「４ ５ ６ ７」が、位置「１２」で見つかるが、それは、すでに説明したように相対的位置である。
【００５６】
ブロック５０６で、伸張モジュール１１８は、実行時に、この表現をマッチングシーケンスで置き換えて、データを再構成する。例えば、表現「｛１２，４｝」は、マッチングバイトシーケンス「４ ５ ６ ７」で置き換えられ、図４のブロック４０８で圧縮されたパケット３０４（３）のシーケンスと一致するシーケンス「４ ５ ６ ７ ０ ８ ２ ４」を含むパケット５０８を形成する。例えば、圧縮データは、マッチングシーケンスの代わりに表現を含む新しいデータセットを形成することによりストリーミング配信されるデータから形成することができる。そのため、この実施例で示されるように、クライアント１０４は、ルックアップテーブル２１６を使用せずに圧縮データを伸張することができる。したがって、ストリーミング配信される圧縮データは、クライアント１０４がサーバ１０２に比べて削減されたハードウェアおよび／またはソフトウェアリソースを有する場合でも、クライアント１０４により伸張することができる。
【００５７】
図３〜４に関連してそれぞれ説明した例示的な手順３００、４００では、ルックアップテーブル２１６は、複数のインデックス３０８（ｋ）のそれぞれが２バイトを含むように構成されている。したがって、ルックアップテーブル２１６に、ホストバッファ２１２内のすべての２バイトシーケンスを記述している６５，５３６個の対応するエントリを入れることができる。これにより、ルックアップテーブル２１６で直接、初期シーケンスを使用することができる。つまり、初期シーケンスは、対応するエントリを発見するためにルックアップテーブル２１６とともに使用するように変換されないということである。２バイトを持つインデックス３０８（ｋ）について説明しているが、３バイトシーケンス、４バイトシーケンスなどのさまざまな長さのインデックスを使用することができる。
【００５８】
図６は、ストリーミング配信されるデータを含めるためヒストリバッファ２１２でスライディングウィンドウが使用される一実施例６００の図である。図３に関連して説明している実施例では、パケット３０４（３）がヒストリバッファ２１２に追加されている。その後、パケット３０４（３）を参照するために、ルックアップテーブル２１６が更新される。しかし、ヒストリバッファ２１２は、記憶容量が限れている場合がある。したがって、スライディングウィンドウを使用して、ヒストリバッファ２１２に新規追加データを含める。
【００５９】
例えば、ヒストリバッファ２１２は、図３のブロック３０２でパケット３０４（３）を追加した結果としてシーケンス６０２を含めることができる。この実施例のヒストリバッファ２１２は、最大で２４バイト格納することができる。したがって、８バイトあるシーケンス６０４を追加するために、圧縮モジュール１１６を実行してヒストリバッファ２１２の先頭から８バイトあるシーケンス６０６を取り除き、残りのシーケンスをヒストリバッファ２１２の先頭に移動させる。その後、新しいシーケンス６０４がヒストリバッファ２１２の末尾に追加される。シーケンスの移動と追加により、ヒストリバッファ２１２には、新規追加シーケンス６０４を含む２４バイトあるシーケンス６０８を有することとなる。
【００６０】
ルックアップテーブル２１６を更新してシーケンス６０８を反映させるために、ルックアップテーブル２１６内のハッシュチェーン３１０（ｋ）内の各位置において、ヒストリバッファ２１２内でバイトのそれぞれがシフトされたバイト数に対応する数を減じることができる。例えば、この実施例では、バイトのそれぞれが８バイト分シフトされ、新しいシーケンス６０４用に空きが作られている。したがって、複数のハッシュチェーン３１０（１）〜３１０（Ｋ）によって記述されるそれぞれの位置は、その位置から「８」が減じられ、ヒストリバッファ２１２内の対応するインデックス３０８（ｋ）の新しい位置を反映する。ヒストリバッファ２１２内にもはや含まれていないハッシュチェーン３１０（ｋ）のそれぞれから位置を削除するために、０未満の値を持つ任意の位置をハッシュチェーン３１０（ｋ）から削除する。
【００６１】
図７は、ストリーミングデータの圧縮をさらに最適化する一実施例における手順７００を示す流れ図である。図３〜４に関して説明した前の手順３００、４００では、ルックアップテーブル２１６は、ヒストリバッファ２１２内の初期シーケンスを効率よく特定するため対応するインデックス３０８（ｋ）のヒストリバッファ２１２内の各位置を記述するように構成されている。ヒストリバッファ２１２内でマッチングシーケンスを見つけることをさらに最適化して、データ圧縮の効率をさらに高めることができる。
【００６２】
例えば、ブロック７０２では、マッチングシーケンスは、ルックアップテーブルを使用し、またしきい値を使用して見つけられる。さまざまなしきい値が使用できる。例えば、マッチングシーケンスを見つけるための比較は、実行される比較の回数を制限するためヒストリバッファ内の所定の数の位置で実行するようにできる。ストリーミング配信されるデータと比較されるヒストリバッファ内の位置の数を制限することにより、位置のサイズ（例えば、バイト数）を制限することができる。例えば、すでに説明したように、ヒストリバッファ２１２内のマッチングシーケンスの位置は、マッチングシーケンスの先頭または末尾とカレントポインタの先頭または末尾との間の相対的位置として記述することができ、これはバックポインタにより記述することができる。したがって、実行される比較の回数を制限することにより、マッチングシーケンスは、カレントポインタの「より近く」に配置される可能性が高くなる。したがって、この「近さ」ゆえに、位置はより小さな値をもつことができ、例えば、使用するバイトをより少なくできる。他の実施例では、所定のしきい値を超える値を持つ位置を考慮しないような、またこの位置に対する値のサイズを制限する役目をすることができるようなしきい値を採用することができる。そのため、探索する位置の数、それぞれの位置を記述する値のサイズ、それぞれの配置されているシーケンスの長さを記述する値のサイズなど、さまざまなしきい値を使用することができる。
【００６３】
決定ブロック７０４で、マッチングシーケンスの位置を記述するバックポインタが最も長い間参照されていない（ＬＲＵ）テーブルに含まれているかどうかに関して判別する。ＬＲＵテーブルを使用して、最も長い間参照されていないバックポインタを格納することができる。マッチングシーケンスのバックポインタがＬＲＵテーブルに含まれている場合、ＬＲＵテーブル内のバックポインタに対応するＬＲＵ表現は、マッチングシーケンスのバックポインタを符号化するために使用される。例えば、ＬＲＵテーブルは、４つの最も長い間参照されていないバックポインタがＬＲＵテーブルに格納されるように深さ４（ｄｅｐｔｈ ｏｆ ｆｏｕｒ）を持つことができる。ＬＲＵ内のバックポインタはそれぞれ、ＬＲＵテーブルへマッピングする対応するＬＲＵ表現を有する。したがって、バックポインタがＬＲＵテーブルに含まれている場合、その後ブロック７０６で、バックポインタをＬＲＵテーブルからのＬＲＵ表現を用いて符号化することができる。このようにして、圧縮モジュールは、ストリーミングデータ内に見つけられる追加パターンを処理して、さらにデータを圧縮することができる。例えば、サーバからクライアントにストリーミング配信されるグラフィックデータは、ヒストリバッファ内の類似のオフセットで繰り返されるマッチングシーケンスを含むことができる。したがって、マッチングシーケンスは、マッチングシーケンスの長さおよび位置を含み、その位置はさらにＬＲＵ表現を使用することにより圧縮される、表現を使用して圧縮することができる。
【００６４】
バックポインタがＬＲＵテーブルに含まれていない場合、次いでブロック７０８で、バックポインタを図２のハフマンテーブル２２８を使用して符号化することができる。ハフマン符号化は、さらに圧縮するそれぞれのバックポインタの出現度数を関連付ける出現度数テーブルから始めることができる。それぞれのバックポインタに、そのバックポインタを一意に表す可変長文字列が割り当てられる。例えば、それぞれの可変長文字列に一意的なプレフィクス（ｐｒｅｆｉｘ）をもつことができる。その後、それらの文字列をツリー状に配列して、各バックポインタおよび表現をそれぞれ符号化および復号化することができる。バックポインタを符号化するために、バックポインタはツリー内に配置される。バックポインタを含む葉を特定するために使用されるツリーの枝を利用して、バイトシーケンスを符号化する、つまり、バックポインタの表現を与える。例えば、ハフマン符号化に使用されるツリーの各枝には出力アルファベットの記号、例えば、ビット０と１がマークされ、符号化は、ツリーのルートから符号化されるバックポインタまでの経路上の枝マーキングの列挙となる。各表現の復号化は、バックポインタを含むツリーの葉に到達するまで、文字列内のそれぞれの連続する値に基づき、ツリーをその原点から下へ枝を通りツリーの葉へとたどることによって実行される。
【００６５】
ブロック７１０で、マッチングシーケンスの長さも、ハフマンテーブルを使用して符号化される。例えば、図２のハフマンテーブル２３０を使用して、ヒストリバッファ内のマッチングシーケンスの長さを符号化し、さらにデータを圧縮することができる。長さは、バックポインタについて説明されているとおりに符号化することができる。
【００６６】
ブロック７１２で、マッチングシーケンスは、ヒストリバッファ内のマッチングシーケンスの位置およびマッチングシーケンスの長さを記述するバックポインタを含むタプルとして構成された表現により表される。ブロック７１４で、コスト関数を使用することにより、マッチングシーケンスに比べて、その表現がより効率的かどうか、例えば、使用されるメモリリソースが格納時により少なく、かつ／または使用される帯域幅がストリーミング配信時により小さいかを判別する。例えば、場合によっては、マッチングシーケンスに使用されるバイト数は、ヒストリバッファ内のマッチングシーケンスの位置および長さを記述する表現よりも少ない。したがって、コスト関数を使用して、表現またはマッチングシーケンス、つまり、データ内のリテラルシーケンスがより効率的かどうかを判別することができる。さまざまなコスト関数が使用できる。例えば、コスト関数は、バックポインタのサイズとマッチングシーケンスの長さのとの積を使用することができる。
【００６７】
決定ブロック７１６で、その表現がより効率的である場合、次いでブロック７１８で、マッチングシーケンスをその表現で表すことにより圧縮データが形成される。ブロック７２０で、カレントポインタが更新され、次の初期シーケンスが処理される。例えば、カレントポインタは、マッチングシーケンスの長さずつ増分され、データ内の次のシーケンスについてこの手順を繰り返すことができる。ストリーミング配信するデータを通じてカレントポインタが増分されると、圧縮データは、クライアントにストリーミング配信される。
【００６８】
決定ブロック７１６で、表現があまり効率的でない場合、ブロック７２２で、マッチングシーケンスはすでに説明したようにハフマンテーブルを使用して表される。ブロック７２０で、カレントポインタは、マッチングシーケンス内のバイト数ずつ増分され、次のシーケンスについてこの手順が続いて行われる。
【００６９】
すでに説明しているように、ハフマンテーブルにより、ストリーミング配信されるデータをさらに圧縮することができる。バックポインタ、長さ、およびリテラルシーケンスをそれぞれ符号化するための３つのハフマンテーブルを説明してきた。他の実施例では、ハフマンテーブルを組み合わせることができる。例えば、図２に示されるように、ハフマンテーブル２２８を使用して、リテラル２３２バイトシーケンスおよびバックポインタ２３４を符号化することができる。圧縮ストリーム内のバックポインタとリテラルシーケンスとを区別するために、バックポインタおよびリテラルシーケンスに、それぞれの一意的なプレフィクスを与えることができ、例えば、それぞれのバックポインタがビット「０」から始まり、それぞれのリテラルシーケンスがビット「１」から始まるようにすることができる。他の実施例では、統一インデックスコード（ｕｎｉｆｉｅｄ ｉｎｄｅｘ ｃｏｄｅ）を使用して、バックポインタおよびリテラルシーケンスがそれぞれ異なる文字を有するように、リテラルシーケンスとバックポインタの両方を単一のアルファベットに組み合わせることにより、リテラルシーケンスとバックポインタの両方を符号化することができる。
【００７０】
すでに説明してあるハフマンテーブルなどの符号化テーブルは、さまざまな方法で提供することができる。例えば、一実施例では、ストリーミング配信されるデータのパケット毎に符号化テーブルを計算する必要がないように、符号化テーブルを圧縮モジュールおよび伸張モジュールが使用するためにあらかじめ構成しておく。これを使用することにより、暗号化プロセスの速度を高めることができる。他の実施例では、符号化テーブルは、所定の間隔で動的に計算される。例えば、符号化テーブルは、所定の数のパケットを受信し符号化テーブルを更新する毎に再計算されるようにしてもよい。
【００７１】
図８は、データ圧縮をさらに最適化するためにシーケンスの比較が最適化される一実施例８００の図である。前述同様に、サーバ１０２は、ヒストリバッファ２１２およびルックアップテーブル２１６を備える。サーバ１０２は、圧縮モジュール１１６を実行して、パケット３０４（３）を圧縮する。ヒストリバッファ２１２の先頭から最初の２バイトが同じである最も右側のシーケンスの先頭までのオフセットを、ｉ１＝ＨＡＳＨ［ＨＡＳＨ＿ＳＵＭ（ｓ）］と表すことができる。示されている実施例では、「ｓ」は「４ ５」に等しく、ヒストリバッファ２１２の先頭から数えゼロから始める場合、ｉ１＝１０である。ヒストリバッファ２１２の先頭から次に最も右側のシーケンスまでの次のオフセットは、ｉ２＝ＮＥＸＴ［ｉ１］と表すことができる。図８に示されている実施例では、ハッシュチェーン８０２（ｋ）内でｉ２＝ＮＥＸＴ［１０］＝４である。同様に、ヒストリバッファ２１２の先頭からの続く各オフセットは、ｉ３＝ＮＥＸＴ［ｉ２］などハッシュチェーン８０２（ｋ）内で表すことができる。示されている実施例では、「４ ５」を含むヒストリバッファ２１２内にはほかにシーケンスがないためｉ３＝０である。
【００７２】
圧縮モジュール１１６は、実行時に、ヒストリバッファ２１２内の位置１６にある「４
５」から始まるパケット３０４（３）を圧縮する手順を開始することができる。圧縮モジュール１１６は、まず、ハッシュチェーン８０２（ｋ）の位置ｉ１＝ＨＡＳＨ［ＨＡＳＨ＿ＳＵＭ （’４’，’５’）］＝１０から初期シーケンス「４ ５」を含むシーケンスをヒストリバッファ２１２内で特定することができる。この位置は記憶され、ＮＥＸＴ［１６］は１０に設定され、ＨＡＳＨ［ＨＡＳＨ＿ＳＵＭ（’４’，’５’）］は１６に設定される。シーケンスは、最初にそれぞれのシーケンス内で次に続くバイトを比較することによって、現在位置（１６）および位置ｉ１（１０）で、一方を他方と比較される。この場合、パケット３０４（３）内の第３バイトとパケット３０４（２）内の第５バイトとを比較して、一致を見つける。示されている実施例では、ＨＩＳＴＯＲＹ［１０＋３］＝’３’およびＨＩＳＴＯＲＹ［１６＋３］＝’６’であるため、次に続くバイト（つまり、それぞれのシーケンス内の３番目のバイト）は異なる。したがって、期待されるマッチングシーケンスの長さは２のままであり、期待されるマッチングシーケンスの位置は１０のままである。
【００７３】
その後、圧縮モジュール１１６は、ルックアップテーブル２１６から位置ｉ２＝ＮＥＸＴ［ｉ１］＝４にある、ヒストリバッファ２１２内の次のシーケンスを特定することができる。ｉ２はゼロに等しくないため、少なくとも２つのバイトの一致がある。それぞれのバイト「４ ５」に続く次のバイトが前のように比較され、結果的に４バイトの一致が得られる。したがって、期待されるマッチングシーケンスの長さは４に設定され、期待されるマッチングシーケンスの位置は４に設定される。その後、圧縮モジュール１１６は、ハッシュチェーン８０２（ｋ）から位置ｉ３＝ＮＥＸＴ［ｉ２］＝０にある、ヒストリバッファ２１２内の他のシーケンスを特定することができる。ｉ３はゼロに等しいため、それはハッシュチェーン８０２（ｋ）の末尾であり、他の位置は比較されない。一実施例では、圧縮モジュール１１６は、ハッシュチェーン８０２（ｋ）の末尾を特にはチェックしないことに留意されたい。その代わりに、位置「ｉ０」（図８に示す例では１６）、ＮＥＸＴ［０］にあるシーケンスはｉ０に等しく設定される。したがって、ハッシュチェーン８０２（ｋ）の末尾（ｉＮ＝ＮＥＸＴ［ｉ｛Ｎ−１｝］＝０）に到達したときに、チェックされ、圧縮モジュール１１６はｉ｛Ｎ＋１｝＝ＮＥＸＴ［ｉＮ］＝ｉ０に進む。
【００７４】
期待されるマッチングシーケンスの長さの後の続く「次の」バイトを比較することにより、比較速度を改善することができる。例えば、前の実施例では、ＨＩＳＴＯＲＹ［ｉ０＋ＭａｔｃｈＬｅｎｇｔｈ］はＨＩＳＴＯＲＹ［ｉ０＋ＭａｔｃｈＬｅｎｇｔｈ］と比較された。ヒストリバッファ２１２内に比較すべき他のシーケンスがない場合、それぞれの位置にあるシーケンス全体の比較が実行される。つまり、ヒストリバッファ２１２内のそれぞれの位置にあるそれぞれのシーケンス内で、各バイトについて一方が他方と比較される。シーケンス全体の比較が成功すると、マッチングシーケンスが導かれる。このようにして、ヒストリバッファ２１２内のシーケンスの比較において、かなりのスピードアップを得ることができる。
【００７５】
図９は、システムから受け取ったフィードバックに応じて圧縮が動的にチューニングされる一実施例におけるシステム９００の図である。ネットワーク上のサーバ１０２とクライアント１０４間の通信は、さまざまなファクタにより変化する場合がある。例えば、クライアント１０４では、ソフトウェアおよび／またはハードウェアリソースの制限があり、クライアント１０４でのデータの伸張は、サーバ１０２での圧縮よりも時間が長くかかる場合がある。他の実施例では、サーバ１０２は、データを複数のクライアントに供給するので、クライアントは、サーバ１０２がそれらのクライアントのそれぞれのためにデータを圧縮できる速度よりも、高速にデータを伸張することができる。すでに説明した圧縮パラメータの１つまたは複数をチューニングすることにより、サーバ１０２とクライアント１０４のハードウェアおよび／またはソフトウェアリソースならびにそれらを通信可能に接続するネットワーク１０６のリソースを考慮に入れ、サーバ１０２とクライアント１０４間の通信を最適化することができる。例えば、サーバ１０２がクライアント１０４に圧縮データを送信するのを「待機している」場合、サーバ１０２は、追加圧縮計算を実行して、さらにデータを圧縮することができる。
【００７６】
ＲＤＰ １１２の圧縮モジュール１１６のパラメータをチューニングするために、フィードバックを求める。さまざまなファクタをフィードバックとして使用し、一般的なネットワーク特性などの圧縮パラメータをチューニングすることができる。例えば、圧縮モジュール１１６が、低速なリンクであるためネットワークの逆圧（ｂａｃｋｐｒｅｓｓｕｒｅ）が生じていることを示すネットワークレイヤからの情報を使用して、さらにデータを圧縮するにはさらに時間がかかることを示すことができる。したがって、逆圧がある場合、最終的な出力サイズの削減のためデータの圧縮にさらに時間をかけるように、圧縮モジュール１１６を動的にチューニングすることができる。
【００７７】
他の実施例では、ＲＤＰ １１２は、ヒストリバッファ９０４（１）、…、９０４（ｈ）、…、９０４（Ｈ）の固定プール９０２を利用することができる。データを送信しなければならない上位レイヤは、プール９０２にバッファ（例えば、バッファ９０４（ｈ））を要求すること（割り当てること）、バッファ９０４（ｈ）にデータを埋め込むこと（データを圧縮することを含む）、その後圧縮されたデータをクライアント１０４に送信することで動作する。バッファ９０４（ｈ）は、バッファのコンテンツが送信されている場合のみ、プール９０２に戻される、つまり「解放される」。この技術により、ＲＤＰ １１２、より具体的には圧縮モジュール１１６は、バッファを「解放して」バッファプールに戻すのに要する時間の長さに基づいて、ネットワーク接続が低速であるか、または高速であるか（例えば、帯域幅の大きさ）、クライアントが低速であるか、または高速であるか（例えば、クライアントがデータを伸張するのに要する時間）などに関するフィードバック、つまり逆圧情報（ｂａｃｋｐｒｅｓｓｕｒｅ ｉｎｆｏｒｍａｔｉｏｎ）を取得することができる。
【００７８】
さらに他の実施例では、プール９０２のバッファ９０４（１）〜９０４（Ｈ）のどれもが使用できない場合、圧縮にさらに時間をかけるようにさまざまな圧縮しきい値をチューニングすることにより、圧縮モジュール１１６を「いっそう働く」ように適合させることができる。いったんネットワーク状態が改善されたら、圧縮モジュール１１６をチューニングして、データの送出がさらに速くなるように圧縮動作回数を減らすこともできる。例えば、ネットワーク１０６に使用可能な帯域幅がかなりある場合、データ通信にかかる時間を短縮する必要がないため、実行される圧縮動作の回数を減らすことができる。このように、変動するネットワーク状態に基づき実行時に圧縮パラメータが変更されるように動的な技術を採用することができる。他の実施例では、ネットワーク速度の初期測定を利用してパラメータをチューニングし、その後、これらのパラメータをセッション全体で使用する。
【００７９】
すでに述べたように、圧縮モジュール１１６のチューニングに使用されるファクタについては、サーバ１０２のハードウェアおよび／またはソフトウェアリソースも考慮に入れることできる。例えば、サーバ１０２上の負荷を考慮に入れることができ（例えば、どれくらいのアクティブセッションがサーバ１０２により提供されているか、図２のプロセッサ２０２上の負荷など）、圧縮の強さを動的にチューニングし、圧縮でＣＰＵをあまり使わないことにより補償することができる。チューニングできる圧縮パラメータの一例として、検索ウィンドウのサイズがある。例えば、検索ウィンドウのサイズを６４Ｋから５１２Ｋまででチューニングすることができる。ウィンドウのサイズを大きくすると、相対的圧縮度が高くなるが、実行が遅くなることがある。したがって、ネットワークが低速であるとみなされる場合には、大きなウィンドウに「切り換える」と都合がよい。
【００８０】
圧縮モジュール１１６をチューニングするために使用されるファクタの他の例では、一致を探すためにトラバースされるハッシュチェーン内のリンクの数をチューニングすることができる。例えば、長いチェーンリンクを辿ると、より長い一致が見つかる確率が高まるが、照合を実行するのに追加のハードウェアおよび／またはソフトウェアリソースのコストがかかる場合がある。
【００８１】
圧縮モジュール１１６をチューニングするために使用されるファクタのさらなる例は、検索を終了するために見つかった最長一致を指定するしきい値である。すでに説明しているように、しきい値を使用することにより、一致を見つけるために実行される検索の回数を制限することができる。このしきい値が大きいほど、より長い一致が見つかる確率が高まり、したがってデータの圧縮がさらに行われる。しかし、この検索を実行する場合、さらに多くの処理リソースが使用される場合もある。さまざまなファクタおよびパラメータについて説明してきたが、他のさまざまなファクタおよびパラメータも、本明細書で説明したように使用することができる。
【００８２】
本発明を、構造的特徴および／または方法論的動作に固有の専門用語で説明してきたが、添付の特許請求の範囲で規定する本発明は、説明した特定の機能または動作に必ずしも限定されるものではないことを理解されたい。むしろ、特定の機能および動作は、請求する本発明の例示的な実施形態として開示している。
【符号の説明】
【００８３】
１０２ サーバ
１０４ クライアント
１０６ ネットワーク
１０８（１），１０８（ｎ），１０８（Ｎ） アプリケーション
１１６ 圧縮モジュール
１１８ 伸張モジュール
１２０（１），１２０（ｍ），１２０（Ｍ） アプリケーション
２０２ プロセッサ
２０４，２０８ メモリ
２０６ プロセッサ
２１０ 入力デバイス
２１２，２１４ ヒストリバッファ
２１６ ルックアップテーブル
２１８ ハフマンテーブル
２２０，２２８，２３０ ハフマンテーブル
２２２ リテラルバイト
２２４ バックポインタ値
２２６ 一致長
２３２ リテラル
２３６，２３８ ＬＲＵテーブル
２３４ バックポインタ
【背景技術】
【０００１】
本発明は、一般に、データ圧縮の分野に関するものであり、より具体的には、データ圧縮のためのシステム、サーバ、方法、およびコンピュータ読み取り可能な媒体に関するものである。
【０００２】
増大の一途を辿るデータへのアクセスに使用される方法は、ますます多様化する一方である。例えば、ユーザは、Ｗｅｂサイトにアクセスして、コンサートイベントの放送、つまりＷｅｂ放送を受信することができる。さらに、ゲームおよびその他のアプリケーションについても、携帯電話を利用して無線ネットワーク経由でアクセスすることができる。このようなデータをユーザに提供するために、クライアントによるレンダリングのためにネットワーク経由でサーバからクライアントへデータをストリーミング配信することができる。ユーザは、その後、映画を見る、歌を聴くなどにより、レンダリングされたデータと対話することができる。
【０００３】
データのストリーミング配信（Ｓｔｒｅａｍｉｎｇ ｄａｔａ）は、ユーザがデータをすばやく受信できるような機能性の向上をユーザに提供する。ストリーミング配信でなければ、クライアントがデータを出力する前にサーバからデータの全量を受信する必要がある場合には、クライアント側でデータをレンダリングする際に、ユーザは遅れを感じるかもしれない。データをストリーミング配信することにより、ユーザが遭遇する遅延を減らすことができる。データのストリーミング配信は、データの「リアルタイム」レンダリングを提供するために使用することができる。
【０００４】
データをストリーミング配信するために、一般的にはパケットを使用して、データをストリーミング配信でまたは連続的にサーバから伝送し、その後、データを含むファイル全体がクライアント側で使用可能になるまでレンダリングされないデータとは対照的に、データが到着したときにクライアント側でレンダリングする。ビデオデータ、オーディオデータ、メディアデータなどのさまざまな種類のデータにストリーミング配信を使用できる。ビデオデータのストリームは、伝送され、イメージが到達したときにレンダリングされる「動画」のシーケンスを提供する。同様に、オーディオデータのストリームは、オーディオデータが到着したときに再生される音声データを提供する。メディアデータのストリームは、オーディオデータとビデオデータの両方を含む。
【０００５】
ストリーミングデータは、圧縮することにより、ネットワーク経由でデータをサーバからクライアントに効率よくストリーミング配信し、ストリーミング配信されたデータの有用性を高めることができる。例えば、通信によりサーバをクライアントに接続するネットワークは、帯域幅が限られていることがある。帯域幅が限られていると、サーバからクライアントに一時に通信できるデータの量が制限される場合があり、したがって、ネットワーク経由でデータをストリーミング配信したときにクライアントに提供される機能も制限される場合がある。例えば、ストリーミング配信されるビデオデータは、高帯域幅ネットワークが使用される場合の解像度に比べて、帯域幅が限られているためより低い解像度に制限されることがある。したがって、より高い解像度のストリーミングビデオデータを望むユーザは、否応なくさらに高い帯域幅の接続に投資せざるを得ない。ストリーミングデータを圧縮することにより、低い帯域幅のネットワーク経由で一度により多くのデータを転送することができ、したがって、ストリーミング配信されたデータの有用性が向上する。
【０００６】
しかし、ストリーミングデータを圧縮する場合、データの集合全体の圧縮、例えばブロック圧縮とは対照的に、厄介な問題が加わることがある。例えば、映画全体を一度に圧縮するには、圧縮ルーチンが、データを圧縮するために、その映画を構成する全データ量を調べる場合がある。圧縮ルーチンは、映画を構成するデータ全体を通して含まれる共通のシーケンスの表現を提供することができる。しかし、ストリーミングデータは、データの「リアルタイム」レンダリングのために供給される。したがって、クライアントによるデータのリアルタイムレンダリングを提供するために、ストリーミングデータを分析する時間は、制限される可能性がある。さらに、共通のシーケンスの表現を提供するために、常に比較に利用できるデータの量も限られることがある。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
したがって、データ圧縮に対する継続的な必要性がある。
【課題を解決するための手段】
【０００８】
データ圧縮について説明する。
一実施例では、クライアントからのリモートアクセスの要求に応じて送信されたデータや、ターミナルサービス環境でのデータなどをクライアントにストリーミング配信するために、データを圧縮する圧縮モジュールがサーバにより実行される。圧縮モジュールは、クライアントにすでにストリーミング配信されているデータを含むヒストリバッファを使用する。圧縮モジュールは、実行されると、ストリーミング配信されるデータ内のシーケンスとヒストリバッファ内の１つまたは複数のシーケンスとを比較して、マッチングシーケンスを見つける。ヒストリバッファ内のシーケンスの位置を特定するために、複数のインデックスのうちの１つでそれぞれ発見可能な複数のエントリを有するルックアップテーブルを使用する。これらのエントリのそれぞれは、対応するインデックスがヒストリバッファ内に置かれているかどうかを示す参照であり、もし置かれていれば、さらに、ヒストリバッファ内の対応するインデックスの１つまたは複数の位置を示す参照となる。したがって、圧縮モジュールは、ストリーミング配信されるデータ内の初期シーケンスをルックアップテーブルのインデックスとして使用し、ヒストリバッファ内のマッチングインデックスを見つけることができる。その後、データ内のマッチングシーケンスは、ヒストリバッファ内のマッチングシーケンスの位置および長さを記述する表現で置き換えられ、これによりクライアントにストリーミング配信する圧縮データを形成することができる。
【０００９】
他の実施例では、方法は、サーバにより提供されるターミナルサービスからデータをクライアントにネットワーク経由で通信するためにリソースが使用可能かどうかを示すフィードバックを受け取ること、およびそのフィードバックに応じて、データを圧縮するために使用される圧縮ルーチンの１つまたは複数のパラメータをチューニングすることを含む。
【００１０】
さらに他の実施例では、方法は、サーバを通じて利用可能なアプリケーションまたはファイルへのリモートアクセスの要求をクライアントからサーバで受け取ることを含む。ネットワーク経由で、その要求に応じてデータを伝達するためにリソースが使用可能であるかどうかが判別される。データを圧縮するために使用される圧縮ルーチンの１つまたは複数のパラメータは、上記判別されたリソースの使用可能性に基づいてチューニングされる。
【００１１】
なお、説明の中の例において、同じ参照番号は、類似の構造およびコンポーネントを参照するために使用する。
【図面の簡単な説明】
【００１２】
【図１】データがネットワーク経由でサーバからクライアントへストリーミング配信される環境を示す一実施例の図である。
【図２】図１のサーバおよびクライアントをさらに詳細に示している一実施例の図である。
【図３】ストリーミング配信するデータを圧縮用に構成する例示的な手順を示す流れ図である。
【図４】ストリーミング配信されるパケットへの参照を含むように構成されている図３のルックアップテーブルを使用してパケットを圧縮する例示的な手順を示す流れ図である。
【図５】伸張モジュールを実行することを通じてクライアントにより図４の圧縮されたパケットを伸張する一実施例の手順を示す流れ図である。
【図６】ストリーミング配信されるデータを含めるためヒストリバッファにおいてスライディングウィンドウが使用される一実施例の図である。
【図７】ストリーミングデータの圧縮をさらに最適化する一実施例の手順を示す流れ図である。
【図８】データ圧縮をさらに最適化するためにシーケンスの比較が最適化される一実施例の図である。
【図９】システムから受け取ったフィードバックに応じて圧縮が動的にチューニングされる一実施例のシステムの図である。
【発明を実施するための形態】
【００１３】
・概要
データ圧縮について説明する。一実施例では、圧縮モジュールは、サーバからクライアントへストリーミング発信するデータを圧縮するためサーバにより実行される。圧縮モジュールは、クライアントにすでにストリーミング配信されているデータを含むヒストリバッファを使用する。圧縮モジュールは、実行時に、ストリーミング配信されるデータ内のシーケンスとヒストリバッファ内の１つまたは複数のシーケンスとを比較して、マッチングシーケンスを見つける。ヒストリバッファ内のシーケンスの位置を特定するために、複数のエントリを有するルックアップテーブルが使用される。これらのエントリはそれぞれ、複数のインデックスのうちの特定の１つを使用して発見可能である。各エントリは、対応するインデックスがヒストリバッファ内に置かれているかどうかを示す参照であり、もし置かれていれば、さらに、ヒストリバッファ内の対応するインデックスの１つまたは複数の位置を示す参照となる。したがって、圧縮モジュールは、ストリーミング配信されるデータ内の初期シーケンスをルックアップテーブルのインデックスとして使用し、エントリを１つ見つけることができる。このようにして、圧縮モジュールは、ヒストリバッファ内の各シーケンスをストリーミング配信されるデータ内のシーケンス毎に別々に比較することなく、初期シーケンスを有するヒストリバッファ内でそれぞれの位置をすばやく特定することができる。
【００１４】
マッチングインデックスの対応するエントリが複数の位置を参照している場合、圧縮モジュールは、マッチングインデックスがある各位置のシーケンスを初期シーケンスを含むデータ内のシーケンスと比較することによりマッチングシーケンスを導出することができる。その後、データ内のマッチングシーケンスは、ヒストリバッファ内のマッチングシーケンスの位置および長さを記述する表現で表すことができる。その後、その表現を含む圧縮データを形成することができる。続いて、圧縮データはクライアントにストリーミング配信される。クライアントは、サーバからクライアントにすでにストリーミング配信されているデータも含んでいるヒストリバッファを使用することにより圧縮データを伸張する。クライアントは、伸張モジュールの実行を通じて、データを再構成するためにその表現により示される長さおよび位置を使用してクライアントのヒストリバッファ内のマッチングシーケンスを見つける。このようにして、データを失うことなくデータの圧縮および伸張を行うことができるような可逆データ圧縮技術が実現される。例えば、ビデオデータは、このデータ圧縮技術を使用することで、データの一部を失わずに、したがってビデオデータの解像度を維持して、圧縮および圧縮解除を行うことができる。
【００１５】
・例示的環境
図１は、データがネットワーク１０６経由でサーバ１０２からクライアント１０４へストリーミング配信される環境１００を示す一実施例の図である。クライアント１０４は、さまざまな方法で構成することができる。例えば、クライアント１０４は、図示されているようなデスクトップコンピュータ、および、移動局、娯楽機器、セットトップボックス、携帯電話などのネットワーク１０６経由で通信することが可能な装置として構成することができる。クライアント１０４は、さらに、クライアント１０４を操作する人および／またはエンティティ（ｅｎｔｉｔｙ）に関係していてもよい。つまり、クライアント１０４は、ユーザおよび／またはマシンを含む論理クライアントを記述しているとすることができる。１つのクライアント１０４が図示されているが、複数のクライアントをネットワーク１０６に通信可能に接続することができる。ネットワーク１０６は、インターネットとして図示されているが、さらに、イントラネット、有線または無線電話網などのさまざまな他のネットワークを含むこともできる。
【００１６】
サーバ１０２は、ネットワーク１０６経由でデータをクライアント１０４にストリーミング配信するように構成されている。サーバ１０２は、クライアント１０４によるレンダリングのために、さまざまなストリーミングデータを供給する。一実施例では、サーバ１０２は、クライアント１０４にストリーミング配信されるコンサートのＷｅｂ放送を提供することができる。クライアント１０４によりレンダリングされると、ユーザはそのＷｅｂ放送を視聴できる。他の実施例では、クライアント１０４は、このクライアント１０４により出力するために、サーバ１０２からストリーミング配信される楽曲を含むデータを受信することができる。
【００１７】
さらなる実施例では、サーバ１０２は、さらに、リモートアプリケーション実行用のターミナルサービス（ｔｅｒｍｉｎａｌ ｓｅｒｖｉｃｅｓ）を提供することもできる。例えば、サーバ１０２は、複数のアプリケーション１０８（１）、…、１０８（ｎ）、…、１０８（Ｎ）を含むことができるが、ただし、「ｎ」は２から「Ｎ」までの任意のアプリケーションとすることができる。アプリケーション１０８（１）〜１０８（Ｎ）はそれぞれ、サーバ１０２上で実行される。サーバ１０２は、ネットワーク１０６経由で、アプリケーション１０８（１）〜１０８（Ｎ）を実行することを通じて供給される画面情報をクライアント１０４にストリーミング配信する。例えば、画面情報は、オペレーティングシステムにより与えられるデスクトップの表示、およびワードプロセッサの実行に関係する情報を表示するウィンドウ、ならびにオペレーティングシステムおよび／またはワードプロセッサにより与えられるオーディオ情報も含むことができる。
【００１８】
サーバ１０２からストリーミング配信される画面情報は、ユーザが見られるようにクライアント１０４によりレンダリングされる。ユーザは、クライアント１０４と対話し、マウス１０８および／またはキーボード１１０などのクライアント１０４の入力デバイスを使用して入力することができる。入力は、キーボード１１０を使用することにより供給される、ワードプロセッサ用のテキスト入力などのレンダリングされた画面情報に対応することができる。それらの入力は、ネットワーク１０６経由でクライアント１０４からサーバ１０２へ通信される。入力は、サーバ１０２により受信されると、複数のアプリケーション１０８（１）〜１０８（Ｎ）を実行するときに使用することができる。例えば、ワードプロセッサは、ドキュメントに含めるためにテキスト入力を受け、画面情報をクライアント１０４にストリーミング配信して、このテキストを含むドキュメントを示すことができる。サーバ１０２上でのアプリケーション１０８（１）〜１０８（Ｎ）の実行と、画面情報のクライアント１０４へのストリーミング配信を通じて、クライアント１０４は、クライアント１０４自体では他の方法だと利用できない機能を利用することができる。
【００１９】
例えば、クライアント１０４は、例えば、限られた処理および／またはメモリリソースを有する「シン」クライアントとして構成することができる。しかし、サーバ１０２は、例えば、クライアント１０４よりも処理および／またはメモリリソースの量をより多くもたせることにより、機能を豊富にすることができる。したがって、サーバ１０２は、クライアント１０４では実行できない、および／またはクライアント１０４で実行すると低速となるアプリケーションを実行することができる。サーバ１０２は、画面情報をクライアント１０４に送信することによりアプリケーション１０８（１）〜１０８（Ｎ）の１つまたは複数の実行結果をクライアント１０４に送り、ネットワーク１０６経由でクライアントから入力を受け取る。このようにして、処理リソース、メモリリソース、および複数のアプリケーション１０８（１）〜１０８（Ｎ）など、サーバ１０２が備える機能を、他の方法だとこの機能を利用できないクライアント１０４に提供することができる。
【００２０】
ネットワーク経由でサーバ１０２とクライアント１０４間の通信を提供するために、サーバ１０２とクライアント１０４は、それぞれ、リモートデスクトッププロトコル（ＲＤＰ）１１２、１１４を実装することができる。ＲＤＰ １１２、１１４は、すでに説明したようにアプリケーション１０８（１）〜１０８（Ｎ）に対しネットワーク接続を介したリモート表示および入力機能を提供するように設計されている。例えば、ＲＤＰを使用することにより、サーバ１０２からクライアント１０４にデバイス通信（ｄｅｖｉｃｅ ｃｏｍｍｕｎｉｃａｔｉｏｎ）およびプレゼンテーションデータを搬送する個別の仮想チャネルとともに、クライアント１０４からサーバ１０２に通信される暗号化された入力を可能にする。
【００２１】
ＲＤＰ １１２、１１４は、さらに、圧縮および伸張モジュール１１６、１１８をサーバ１０２およびクライアント１０４のそれぞれに含めることにより帯域幅を削減することもできる。圧縮モジュール１１６はＲＤＰ １１２の実装を通じてサーバ１０２により実行され、ネットワーク１０６経由でストリーミング配信する前にデータを圧縮することができる。同様に、伸張モジュール１１８はＲＤＰ １１４の実装を通じてクライアント１０４により実行されることにより、ネットワーク１０６経由でサーバ１０２からストリーミング配信された圧縮データを伸張することができる。
【００２２】
圧縮および伸張モジュール１１６、１１８は、実行時にそれぞれ、ネットワーク１００６経由でストリーミング配信されるデータの圧縮および伸張を行う。すでに述べたように、ストリーミングデータの圧縮および伸張では、一度にデータセット全体の圧縮および伸張を行うのとは対照的に、つまりブロック圧縮とは対照的に、独自の複雑な状況をもたらす場合がある。例えば、データは「リアルタイム」でストリーミング配信することができるため、データのストリーミング配信に遅延が生じるとデータの有用性を低下させる場合がある。圧縮および伸張モジュール１１６、１１８では、ストリーミングデータの独自の複雑な状況に対処し、それにより、図３から５に関してさらに詳しく説明されているように、ネットワーク１０６経由で圧縮データのストリーミング配信を提供する。
【００２３】
ターミナルサービス（ＴＳ）を使用することにより、クライアント１０４は、サーバ１０２にインストールされているアプリケーション１０８（１）〜１０８（Ｎ）のうちの１つまたは複数にアクセスし、サーバ１０２上のアプリケーションを実行し、クライアント１０４上にそのアプリケーションのユーザインターフェイス（ＵＩ）を表示することができる。アプリケーション１０８（１）〜１０８（Ｎ）はサーバ１０２上で実行されるため、ＴＳにより、クライアント１０４は、クライアント１０４がクライアント１０４自体でリソースをローカルで実行するのに適したハードウェアおよびソフトウェアを有しているかどうかに関係なく、企業インフラのリソースを活用することができる。
【００２４】
クライアント１０４は、複数のアプリケーション１０８（１）〜１０８（Ｎ）がサーバ１０２により実行されるターミナルサービス環境で説明しているが、クライアント１０４は、複数のアプリケーション１２０（１）、…、１２０（ｍ）、…、１２０（Ｍ）のうちの１つまたは複数を実行することもできる。例えば、アプリケーション１２０（１）〜１２０（Ｍ）のうちの１つは、ユーザが見るために表示するデータをレンダリングし、マウス１０８および／またはキーボード１１０などのユーザからの入力を受け取るためにＲＤＰ １１４とともに利用されるインターフェイスを備えることができる。さらに、圧縮および伸張モジュール１１６、１１８は、それぞれのＲＤＰ １１２、１１４の一部として図示されているが、圧縮および伸張モジュール１１６、１１８は、それぞれストリーミングデータの圧縮および伸張のため実行されるスタンドアロンのソフトウェアコンポーネントとして構成することができる。
【００２５】
さらに、以下の説明の一部では、ターミナルサービス環境における圧縮の使用について説明しているが、本明細書で説明している圧縮および伸張技術は、他のさまざまな環境でも利用することができる。例えば、この圧縮技術を使用することにより、リモートアクセス環境で使用されるデータを圧縮することができる。リモートアクセスとは、遠く離れた場所からコンピュータまたはネットワークにアクセスできることを表す。例えば、企業の遠隔地にある事務所では、企業のネットワークにアクセスすることを所望し、リモートアクセスを利用して、電話回線網、インターネットなどを経由し、そこに収容されているファイルおよびアプリケーションにアクセスする場合がある。サーバ１０２は、ネットワークにリモートでアクセスすることを求めているクライアントを処理するためにセットアップされている関連ソフトウェアを有するリモートアクセスサーバとして構成することができる。一実施例では、リモートアクセスサーバは、セキュリティ用のファイヤウォールサーバおよびリモートアクセス要求をネットワークの他の部分に転送するルータを含む。リモートアクセスサーバは、さらに、仮想プライベートネットワーク（ＶＰＮ）の一部として使用することもできる。
【００２６】
図２は、図１のサーバ１０２およびクライアント１０４をさらに詳しく示している一実施例２００の図である。サーバ１０２は、プロセッサ２０２およびメモリ２０４を備える。ＲＤＰ １１２およびその個別の圧縮モジュール１１６は、プロセッサ２０２上で実行されているように例示され、メモリ２０４に格納可能である。同様に、クライアント１０４は、プロセッサ２０６およびメモリ２０８を備える。ＲＤＰ １１４およびその個別の伸張モジュール１１８は、プロセッサ２０６上で実行されているように例示され、メモリ２０８に格納可能である。
【００２７】
サーバ１０２からクライアント１０４にストリーミング配信されるべきデータは、ビデオカメラ、マイクなどの入力デバイス２１０から受け取った、アプリケーション１０８（１）〜１０８（Ｎ）のうちの１つまたは複数の実行など、さまざまなソースから供給することができる。圧縮モジュール１１６は、サーバ１０２のプロセス２０２上で実行され、クライアント１０４にストリーミング配信するデータを圧縮する。そのデータは、サーバ１０２からクライアント１０４へパケットでストリーミング配信することができる。
【００２８】
例えば、圧縮モジュール１１６は、所与の長さの未圧縮のシーケンスを有するデータを受け取り、そのシーケンスを、より小さな（現在圧縮されている）長さに圧縮すること、例えばバイト数、ビット数などを減らすことを試みることができる。圧縮モジュール１１６は、シーケンスを、置き換えられるシーケンスに比べて格納時に使用されるメモリリソースが少なくて済む、例えばバイト数の少ない表現で置き換えることにより、パケット毎にデータを圧縮することができる。
【００２９】
圧縮モジュール１１６がシーケンスを圧縮できる場合、圧縮データがＲＤＰ接続の終点、つまりクライアント１０４のＲＤＰ １１４に送信される。伸張モジュール１１８はクライアント１０４により実行され、圧縮データを伸張してデータを再構成する。圧縮モジュール１１６がデータを圧縮できない場合、データは、非圧縮形式で、つまりリテラルシーケンスでクライアント１０４にストリーミング配信することができる。圧縮モジュール１１６は、その後、サーバ１０２により実行され、後続のシーケンスの圧縮を試みることができる。
【００３０】
データを圧縮するために使用される基本オペレーションは、以前にストリーミング配信されたシーケンスとともに圧縮されるデータ内のシーケンスのパターンマッチングを伴う。これを達成するために、圧縮モジュール１１６は、クライアント１０４にすでにストリーミング配信されているデータを収容しているヒストリバッファ２１２を維持する。圧縮モジュール１１６は、実行時に、ストリーミング配信されるデータ内のシーケンスとすでにクライアント１０４にストリーミング配信されているデータに含まれる１つまたは複数のシーケンスとを照合する。その後、ヒストリバッファ内のシーケンスと一致するストリーミング配信されるデータ内のシーケンスは、ヒストリバッファ２１２内のマッチングシーケンスを参照する１つまたは複数の表現を使用して表現することができる。これらの表現は、より小さい、つまり、圧縮する実際のシーケンス、すなわちマッチングシーケンスを格納するために使用されるメモリリソースよりも、使用するメモリリソースをより少なくすることができる。このことは、ストリーミング配信されるデータに含まれるデータの量を有効に低減する。
【００３１】
ヒストリバッファ２１２を使用したパターンマッチングの基本例を例示するために、ヒストリバッファ２１２は、以下のシーケンスを含むと仮定する。
１ ２ ７ ４ ５ ６ ３ ９ ４ ５ １ ４ ９ １
圧縮モジュール１１６は、サーバ１０２のプロセッサ２０２上で実行され、以下のシーケンスを受け取る。
４ ５ ９ ７ ４ ５ ６ ３ ９ ４ ５ １ ４ ６
圧縮モジュール１１６は、実行時に、圧縮されるデータ内のシーケンスと一致するヒストリバッファ内で最長のシーケンス、つまりマッチングシーケンス（ｍａｔｃｈｉｎｇ ｓｅｑｕｅｎｃｅ）を見つける。この場合、ヒストリバッファ内に現れるマッチングシーケンスは、以下では太字で示されている。マッチングシーケンスは、長さ１０バイトで、ヒストリバッファ２１２の先頭から３バイトのところで始まる（左から開始し、０からカウントする）。
【００３２】
【数１】
【００３３】
したがって、圧縮モジュール１１６は、実行時に、ストリーミング配信されるデータを以下のように表現することにより、圧縮データを作成することができる。
４ ５ ９ （バッファの先頭から３バイトのところで始まる長さ１０バイトの一致）
６
サーバ１０２では、ヒストリバッファ内のマッチングシーケンスを参照することにより、クライアント１０４にすでにストリーミング配信されているシーケンスを再送する必要はない。それ故に、圧縮モジュール１１６は、ストリーミング配信されるデータ内の繰り返しパターンを見つけて、この繰り返しパターン、つまりマッチングシーケンスを、ネットワーク１０６経由で送信されたときに使用するメモリリソースおよび帯域幅がより少ない表現で置き換えることにより、ストリーミング配信されるデータを圧縮する。
【００３４】
圧縮データを伸張するために、クライアント１０４は、伸張モジュール１１８およびヒストリバッファ２１４を備える。クライアント１０４のヒストリバッファ２１４は、サーバ１０２のヒストリバッファ２１２のように、すでにストリーミング配信されているデータを格納する。したがって、伸張モジュール１１８は、クライアント１０４により実行されると、ヒストリバッファ２１４を使用することによりクライアント１０４にストリーミング配信されている圧縮データを伸張することができる。前の実施例の続きとして、クライアント１０４が以下のように示されている圧縮データを受け取ると仮定する。
４ ５ ９ （バッファの先頭から３バイトのところで始まる長さ１０バイトの一致）
６
伸張モジュール１１８は、圧縮データに含まれる表現に基づき、実行時に、ヒストリバッファ２１４から圧縮されたシーケンスを取り出すことができ、これは、以下のように太字で示される。
【００３５】
【数２】
【００３６】
こうして、伸張モジュール１１８は、ヒストリバッファ２１４を使用して圧縮された文字列を伸張することができる。
【００３７】
サーバ１０２は、ヒストリバッファ２１２内でマッチングシーケンスを見つけるためのルックアップテーブル２１６を備えることもできる。例えば、ルックアップテーブル２１６は、複数のインデックスのうちの対応する１つによりそれぞれ発見可能な複数のエントリを含むことができる。それぞれのエントリは、対応するインデックスを有するヒストリバッファ２１２内の各位置を記述する。したがって、圧縮モジュール１１６は、サーバ１０２により実行されると、ルックアップテーブル２１６を使用することによりヒストリバッファ２１２内の特定のシーケンスをすばやく特定することができる。ルックアップテーブル２１６およびヒストリバッファ２１２についてのさらなる検討は、図３〜４の関連で見出すことができる。
【００３８】
サーバ１０２は、ハフマン符号化、算術符号化、プレフィクス符号化（Ｐｒｅｆｉｘ ｅｎｃｏｄｉｎｇ）、およびマルコフ符号化などの符号化技術を使用して、ストリーミング配信用にデータをさらに圧縮することもできる。例えば、ストリーミング配信されるデータは、ヒストリバッファ内のシーケンスと一致しないシーケンスを含むことができる。これらのシーケンスは、「リテラル」シーケンス（“ｌｉｔｅｒａｌ”ｓｅｑｕｅｎｃｅｓ）と呼ばれる。ハフマン符号化を使用して、データ内のリテラルシーケンスの一部または全部を圧縮すると、データをさらに圧縮することができる。例えば、ハフマン符号化は、さらに圧縮するそれぞれのリテラルシーケンスの出現度数を関連付ける出現度数テーブルから始めることができる。出現度数ケーブルは、データ自体および／または代表データから生成することができる。例えば、すでにストリーミング配信されているパケットを処理することでリテラルシーケンスの出現度数を求め、その後それを利用して、それぞれの後続のパケットを処理することができる。
【００３９】
例えば、可変長文字列を、一意的なプレフィクス（ｐｒｅｆｉｘ）などのその特定のリテラルシーケンスを一意に表すそれぞれのリテラルシーケンスに割り当てることができる。その後、その可変長文字列をツリー状に配列して、各リテラルシーケンスおよび表現をそれぞれ符号化および復号化する。リテラルシーケンスを符号化するために、符号化されるリテラルシーケンスをツリー内に配置する。リテラルシーケンスを含む葉を特定するために使用されるツリーの枝を利用して、リテラルシーケンスを符号化する、つまり、リテラルシーケンスの表現を与える。例えば、ハフマン符号化に使用されるツリーの各枝には出力アルファベットの記号、例えば、ビット０と１がマークされ、符号化は、ツリーのルートから符号化されるリテラルシーケンスまでの経路上の枝マーキングの列挙となる。各表現の復号化は、リテラルシーケンスを含むツリーの葉に到達するまで、可変長文字列内のそれぞれの連続する値に基づいて、ツリーをその原点から枝を通り下ってツリーの葉へと縦走（ｔｒａｖｅｒｓｉｎｇ）することによって行われる。
【００４０】
リテラルシーケンスのハフマン符号化について説明してきたが、ハフマン符号化を使用することによりさらにさまざまなデータを圧縮することができる。例えば、ハフマンテーブル２１８では、リテラル２２２シーケンスおよびバックポインタ２２４の両方を符号化することができる。リテラルシーケンスは、すでに説明しているように、ヒストリバッファ２１２内に見つからないシーケンスを含む。したがって、ハフマンテーブル２１８を使用することで、リテラル２２２シーケンスを圧縮することができる。ハフマンテーブル２１８を利用してバックポインタ２２４も圧縮できる。バックポインタ２２４は、ヒストリバッファ２１２内の特定のシーケンスの位置を記述する。例えば、すでに説明しているように、ヒストリバッファ２１２内のシーケンスと一致するデータ内のシーケンス、つまりマッチングシーケンスは、「バッファの先頭からＹバイトのところで始まる長さＸバイトの一致」として記述することができる。バックポインタ２２４は、ヒストリバッファ２１２内のマッチングシーケンスの位置、つまりＹバイトを記述する。ハフマンテーブル２２０を使用することにより、マッチングシーケンスの長さ分２２６、つまりＸバイト分を圧縮することができる。
【００４１】
サーバ１０２からクライアント１０４にストリーミング配信された圧縮データを伸張するために、それぞれサーバ１０２のハフマンテーブル２１８、２２０に対応するハフマンテーブル２２８、２３０を使用して、クライアント１０４により、伸張モジュール１１６が実行される。例えば、ハフマンテーブル２２８は、リテラル２３２シーケンスおよびバックポインタ２３４を伸張するために使用でき、一方、ハフマンテーブル２３０は、マッチングシーケンスの長さ２２６を伸張するために使用することができる。ハフマンテーブルのさらなる検討は、図７の関連で見出すことができる。
【００４２】
サーバ１０２およびクライアント１０４は、さらに、それぞれＬＲＵ（ｌａｓｔ ｒｅｃｅｎｔｌｙ ｕｓｅｄ：最も長い間参照されていない）テーブル２３６、２３８を含むこともできる。ＬＲＵテーブル２３６、２３８はそれぞれ、バックポインタが「最も長い間参照されていない」バックポインタのうちの１つであったかどうかに基づきバックポインタをさらに符号化するために使用することができる。例えば、ＬＲＵテーブル２３６は、それぞれ、最後の４つのバックポインタ毎に、ＬＲＵ表現を与えるために使用することができる。ＬＲＵ表現は、ＬＲＵテーブル２３６内で特定のバックポインタを特定するためのインデックスとして使用される。この方法で、繰り返されるバックポインタは、さらに圧縮することができる。ＬＲＵテーブルのさらなる検討は、図７の関連で見出すことができる。
【００４３】
サーバ１０２からクライアント１０４にストリーミング配信されるデータの圧縮について説明しているが、クライアント１０４は、データを圧縮してサーバ１０２にストリーミング配信で送り返すこともできる。さらに、以下では、サーバ１０２からクライアント１０４にストリーミング配信されるパケットに関してデータの圧縮について説明しているが、データのさまざまな集合を使用して、サブパケットバイトシーケンス（ｓｕｂ‐ｐａｃｋｅｔ ｂｙｔｅ ｓｅｑｕｅｎｃｅｓ）、複数パケットなどのデータを圧縮することができる。さらに、以下では、バイトシーケンスについて説明しているが、ビットなど、データ内の他のシーケンスについても考慮されている。
【００４４】
・手順の実施例
図３は、ストリーミング配信するデータを圧縮用に構成する例示的手順３００を示す流れ図である。ブロック３０２で、データがヒストリバッファ２１２に追加される。例えば、ヒストリバッファ２１２は、ネットワーク１０６経由で図２のサーバ１０２からクライアント１０４にストリーミング配信された、かつ／またはストリーミング配信する準備ができている複数のパケット３０４（１）、３０４（２）を含むことができる。他の実施例では、パケット３０４（１）、３０４（２）は、圧縮モジュール１１６の実行によりすでに処理されているデータに対応することができる。
【００４５】
サーバ１０２は、ストリーミング配信されるパケット３０４（３）を受信する。圧縮モジュール１１６は、サーバ１０２により実行されると、パケット３０４（３）をヒストリバッファ２１２に追加し、これによりヒストリバッファは、ストリーミング配信されたパケット３０４（１）、３０４（２）およびストリーミング配信されるパケット３０４（３）を含む。
【００４６】
ブロック３０６で、圧縮モジュール１１６は、サーバ１０２により実行されると、ルックアップテーブル２１６を更新して、追加データ、つまりパケット３０４（３）を参照する。ルックアップテーブル２１６は、「ｋ」を「１」から「Ｋ」までの任意のインデックスとし、複数のインデックス３０８（ｋ）を含むように構成される。インデックス３０８（ｋ）はそれぞれ、ルックアップテーブル２１６内の複数のエントリのうちのそれぞれ１つを発見するために使用される。各エントリは、複数のインデックス３０８（ｋ）のうちの対応する１つがヒストリバッファ２１２内に置かれているかどうかを示す参照であり、もし置かれていれば、ヒストリバッファ２１２内の対応するインデックス３０８（ｋ）の１つまたは複数の位置を示す参照となる。例えば、複数のエントリのうちの１つで、インデックス３０８（ｋ）のうちの対応する１つを持つヒストリバッファ２１２内の複数の位置を参照することができる。複数の位置はそれぞれ、複数のハッシュチェーン３１０（ｋ）のうちの対応する１つの使用を通じて説明されているように、図示されている。
【００４７】
例えば、インデックス３０８（ｋ）は、シーケンス「４ ５」を持つものとして図示されている。ルックアップテーブル２１６内のインデックス３０８（ｋ）の対応するエントリ、つまり、ハッシュチェーン３１０（ｋ）は、ヒストリバッファ２１２内のインデックス３０８（ｋ）「４ ５」の各位置を記述する。例えば、パケット３０４（１）は、図３では、以下のシーケンスを持つものとして図示されている。
０ １ ２ ３ ４ ５ ６ ７
パケット３０４（２）は、図３では、以下のシーケンスを持つものとして図示されている。
８ ９ ４ ５ ３ １ ３ ０
図２のクライアント１０４にストリーミング配信されるパケット３０４（３）は、図３では、以下のシーケンスを持つものとして図示されている。
４ ５ ６ ７ ０ ８ ２ ４
パケット３０４（１）〜３０４（３）は、以下のシーケンスが観察されるようにヒストリバッファ内に順次配列される。
０ １ ２ ３ ４ ５ ６ ７ ８ ９ ４ ５ ３ １ ３ ０ ４ ５ ６
７ ０ ８ ２ ４
ハッシュチェーン３１０（ｋ）は、ヒストリバッファ２１２内のインデックス３０８（ｋ）「４ ５」のそれぞれの位置を記述する。各位置は、さまざまな方法で記述することができる。例えば、これらの位置は、ヒストリバッファ２１２の先頭から数え、番号０から始めたときのシーケンスの第１のバイトの位置として記述することができる。ハッシュチェーン３１０（ｋ）は、ハッシュチェーン３１０（ｋ）内の「１ ６」からパケット３０４（３）の先頭まで図３において点線で示すように、ヒストリバッファ２１２内のシーケンスの先頭から１６バイトのところにあるインデックス３０８（ｋ）「４ ５」の第１の位置を記述する。同様に、ハッシュチェーン３１０（ｋ）は、ハッシュチェーン３１０（ｋ）内の「１ ０」からパケット３０４（２）の第３バイトまで図３において点線で図示されている、ヒストリバッファ２１２内のシーケンスの先頭から１０バイトのところにあるインデックス３０８（ｋ）「４ ５」の第２の位置を記述する。さらに、ハッシュチェーン３１０（ｋ）は、ヒストリバッファ２１２内の４バイトのところにあるインデックス３０８（ｋ）「４ ５」の第３および最終の位置を含む。したがって、ルックアップテーブル２１６は、ヒストリバッファ２１２内のインデックス３０８（ｋ）の各位置、例えば、４、１０、１６を記述するハッシュチェーン３１０（ｋ）を参照する対応するエントリを持つインデックス３０８（ｋ）、例えば「４ ５」を含む。ルックアップテーブル２１６を更新することにより、圧縮モジュール１１６は、実行時に、図４に関して後でさらに詳しく説明するように、より効率的な方法でストリーミング配信されるデータを圧縮することができる。
【００４８】
各インデックス３０８（ｋ）は、図３では、複数のハッシュチェーン３１０（ｋ）のうちの対応する１つを持つものとして図示されているが、インデックス３０８（ｋ）が対応するハッシュチェーンを持たない場合もある。例えば、場合によっては、ヒストリバッファ２１２がインデックスを含まないこともある。したがって、そのインデックスに対応するルックアップテーブル２１６内のエントリは、ハッシュチェーンを含み得ない。言い換えると、そのインデックスに対するハッシュチェーンは値０を持つ、つまり対応するインデックスを含む場所はヒストリバッファ２１２内にはないということである。さらに、複数のハッシュチェーン３１０（ｋ）はそれぞれルックアップテーブル２１６内に含まれるように図示されているが、ハッシュチェーン３１０（ｋ）の１つまたは複数をさまざまな方法で提供することができる。例えば、ルックアップテーブル２１６内の各エントリは、ルックアップテーブル２１６とは別の配列として構成される対応するハッシュチェーンへのポインタを含むことができる。
【００４９】
図４は、ストリーミング配信されるパケット３０４（３）への参照を含むように構成されている図３のルックアップテーブル２１６を使用してパケット３０４（３）を圧縮する例示的手順４００を示す流れ図である。ブロック４０２で、圧縮モジュール１１６は、実行時に、カレントポインタ４０４を、図３のブロック３０２のヒストリバッファ２１２に追加されたデータ、つまりパケット３０４（３）のところで開始する。
【００５０】
ブロック４０６で、圧縮モジュール１１６は、サーバ１０２により実行され、カレントポインタ４０４が指す初期シーケンスと一致するルックアップテーブル２１６内のインデックスを見つける。例えば、圧縮モジュール１１６は、カレントポインタ４０４のところの２バイト、例えば「４ ５」からなる初期シーケンスを使用して、その初期シーケンスと一致する複数のインデックス３０８（ｋ）のうちの１つを見つけることができる。この例では、ルックアップテーブル２１６のインデックス３０８（ｋ）「４ ５」は、ヒストリバッファ２１２内のカレントポインタ４０４が指す初期シーケンス「４ ５」と一致する。インデックス３０８（ｋ）は、ヒストリバッファ２１２内のインデックス「４ ５」３０８（ｋ）の各位置を記述するハッシュチェーン３１０（ｋ）を参照する対応するエントリをルックアップテーブル２１６内に持つ。したがって、その対応するエントリは、ヒストリバッファ２１２内の初期シーケンスの各位置を記述する。
【００５１】
マッチングインデックス３０８（ｋ）の対応するエントリが複数の位置を参照する場合、マッチングインデックス３０８（ｋ）「４ ５」を有するヒストリバッファ２１２内の各位置のシーケンスが、カレントポインタ４０４が指す初期シーケンスを有するデータ内のシーケンスと比較される。例えば、カレントポインタ４０４、つまりヒストリバッファ２１２内の位置「１６」のところの初期シーケンス「４ ５」、およびヒストリバッファ２１２内の位置「１０」にあるシーケンスは、長さ「２」である、つまり、各位置のバイトシーケンス内の先頭２バイトのみで一方を他方と照合する。すでに述べたように、この実施例のハッシュチェーン３１０（ｋ）内の位置は、ヒストリバッファ２１２の先頭から番号０を先頭番号として数えることで記述される。カレントポインタ４０４が指す初期シーケンスおよびヒストリバッファ２１２内の位置「４」のシーケンスは長さ「４」である。つまり、位置「４」にあるバイトシーケンス内の４バイトは、位置「４」のところのシーケンス内の４バイトに一致する。このようにして、マッチングシーケンス「４ ５ ６ ７」は、計算で求められた長さから導かれる。最適なマッチングシーケンスを見つけるために、図７に関してさらに詳しく説明されているように、最大長が計算で求められ、かつ／またはしきい値に達するまで、ハッシュチェーン３１０（ｋ）内の各位置を、圧縮されるデータのシーケンス、つまり、パケット３０４（３）と比較することができる。比較を最適化するため、次のバイトはシーケンス、例えば、初期シーケンスまたはヒストリバッファ２１２内のインデックスの後に続く１バイトを最初に比較することができるが、それは、最初の２バイトが一致すること照合から知られているからである。シーケンス内の「次の」バイトに基づく比較のさらなる検討が、図８の関連で見出すことができる。
【００５２】
ブロック４０８で、マッチングシーケンスは、圧縮データを形成するために使用される表現で表される。例えば、パケット３０４（３）内のマッチングシーケンス「４ ５ ６ ７」は、ヒストリバッファ２１２内のマッチングシーケンスの長さおよびマッチングシーケンスの位置を記述する表現で表すことができる。この表現は、タプル（ｔｕｐｌｅ）、つまり指定された順序を持つ集まりとして形式化でき、｛バックポインタ，長さ｝という形式となる。バックポインタは、マッチングシーケンスの相対的位置をヒストリバッファ２１２内のオフセットとして記述することができる。例えば、バックポインタは、ヒストリバッファ２１２内におけるマッチングシーケンスの絶対的位置とカレントポインタ４０４の絶対的位置との間のオフセットとして相対的位置を記述することができる。この例では、マッチングシーケンスの絶対的位置は、ヒストリバッファ２１２内の位置４であり、カレントポインタ４０４の絶対的位置は、「１６」である。したがって、マッチングシーケンスの相対的位置は、カレントポインタ４０４から１２バイトのところである。長さは、マッチングシーケンスの長さを記述し、例えば「４」である。したがって、パケット３０４（３）を、マッチングシーケンス「４ ５ ６ ７」を表現「｛１２，４｝」で表すことにより圧縮し、圧縮データ、例えば、パケット４１０を形成することができる。他の実施例では、マッチングシーケンスの位置は、ヒストリバッファのマッチングシーケンスの絶対的位置、例えば、位置４から得られる。
【００５３】
こうして、ルックアップテーブル２１６からは、ヒストリバッファ２１２内の各インデックス３０８（ｋ）の各位置が得られる。したがって、圧縮モジュール１１６が実行されると、初期シーケンスのそれぞれの位置を、マッチングシーケンスを見つけるためにヒストリバッファ２１２内で個々のビットまたはバイトを「尋ね歩く」ことをせずに、ヒストリバッファ２１２内で見つけることができる。そのため、圧縮モジュール１１６は、ストリーミング配信されるデータを効率よく圧縮することができる。
【００５４】
図５は、伸張モジュール１２８の実行を通じてクライアント１０４により図４の圧縮されたパケットを伸張する例示的な手順５００を示す流れ図である。ブロック５０２で、クライアント１０４は、図４のサーバからクライアント１０４にストリーミング配信された、圧縮されたデータ、例えばパケット４１０を受け取る。
【００５５】
ブロック５０４で、伸張モジュール１２８は、実行時に、クライアント１０４のヒストリバッファ２１４内のマッチングシーケンスを検出する。クライアント１０４のヒストリバッファ２１４は、サーバ１０２のヒストリバッファ２１２のように、サーバ１０２からクライアント１０４へストリーミング配信されているデータを含めることができる。そのため、圧縮データ、例えばパケット４１０が形成される前に、クライアント１０４のヒストリバッファ２１４は、サーバ１０２のヒストリバッファ２１２と一致する。したがって、伸張モジュール１１８は、実行時に、サーバのヒストリバッファ２１２内のマッチングシーケンスの長さおよび位置を記述する表現からクライアント１０４のヒストリバッファ２１４内のマッチングシーケンスを見つけることができる。前の実施例の続きとして、マッチングシーケンス「４ ５ ６ ７」が、位置「１２」で見つかるが、それは、すでに説明したように相対的位置である。
【００５６】
ブロック５０６で、伸張モジュール１１８は、実行時に、この表現をマッチングシーケンスで置き換えて、データを再構成する。例えば、表現「｛１２，４｝」は、マッチングバイトシーケンス「４ ５ ６ ７」で置き換えられ、図４のブロック４０８で圧縮されたパケット３０４（３）のシーケンスと一致するシーケンス「４ ５ ６ ７ ０ ８ ２ ４」を含むパケット５０８を形成する。例えば、圧縮データは、マッチングシーケンスの代わりに表現を含む新しいデータセットを形成することによりストリーミング配信されるデータから形成することができる。そのため、この実施例で示されるように、クライアント１０４は、ルックアップテーブル２１６を使用せずに圧縮データを伸張することができる。したがって、ストリーミング配信される圧縮データは、クライアント１０４がサーバ１０２に比べて削減されたハードウェアおよび／またはソフトウェアリソースを有する場合でも、クライアント１０４により伸張することができる。
【００５７】
図３〜４に関連してそれぞれ説明した例示的な手順３００、４００では、ルックアップテーブル２１６は、複数のインデックス３０８（ｋ）のそれぞれが２バイトを含むように構成されている。したがって、ルックアップテーブル２１６に、ホストバッファ２１２内のすべての２バイトシーケンスを記述している６５，５３６個の対応するエントリを入れることができる。これにより、ルックアップテーブル２１６で直接、初期シーケンスを使用することができる。つまり、初期シーケンスは、対応するエントリを発見するためにルックアップテーブル２１６とともに使用するように変換されないということである。２バイトを持つインデックス３０８（ｋ）について説明しているが、３バイトシーケンス、４バイトシーケンスなどのさまざまな長さのインデックスを使用することができる。
【００５８】
図６は、ストリーミング配信されるデータを含めるためヒストリバッファ２１２でスライディングウィンドウが使用される一実施例６００の図である。図３に関連して説明している実施例では、パケット３０４（３）がヒストリバッファ２１２に追加されている。その後、パケット３０４（３）を参照するために、ルックアップテーブル２１６が更新される。しかし、ヒストリバッファ２１２は、記憶容量が限れている場合がある。したがって、スライディングウィンドウを使用して、ヒストリバッファ２１２に新規追加データを含める。
【００５９】
例えば、ヒストリバッファ２１２は、図３のブロック３０２でパケット３０４（３）を追加した結果としてシーケンス６０２を含めることができる。この実施例のヒストリバッファ２１２は、最大で２４バイト格納することができる。したがって、８バイトあるシーケンス６０４を追加するために、圧縮モジュール１１６を実行してヒストリバッファ２１２の先頭から８バイトあるシーケンス６０６を取り除き、残りのシーケンスをヒストリバッファ２１２の先頭に移動させる。その後、新しいシーケンス６０４がヒストリバッファ２１２の末尾に追加される。シーケンスの移動と追加により、ヒストリバッファ２１２には、新規追加シーケンス６０４を含む２４バイトあるシーケンス６０８を有することとなる。
【００６０】
ルックアップテーブル２１６を更新してシーケンス６０８を反映させるために、ルックアップテーブル２１６内のハッシュチェーン３１０（ｋ）内の各位置において、ヒストリバッファ２１２内でバイトのそれぞれがシフトされたバイト数に対応する数を減じることができる。例えば、この実施例では、バイトのそれぞれが８バイト分シフトされ、新しいシーケンス６０４用に空きが作られている。したがって、複数のハッシュチェーン３１０（１）〜３１０（Ｋ）によって記述されるそれぞれの位置は、その位置から「８」が減じられ、ヒストリバッファ２１２内の対応するインデックス３０８（ｋ）の新しい位置を反映する。ヒストリバッファ２１２内にもはや含まれていないハッシュチェーン３１０（ｋ）のそれぞれから位置を削除するために、０未満の値を持つ任意の位置をハッシュチェーン３１０（ｋ）から削除する。
【００６１】
図７は、ストリーミングデータの圧縮をさらに最適化する一実施例における手順７００を示す流れ図である。図３〜４に関して説明した前の手順３００、４００では、ルックアップテーブル２１６は、ヒストリバッファ２１２内の初期シーケンスを効率よく特定するため対応するインデックス３０８（ｋ）のヒストリバッファ２１２内の各位置を記述するように構成されている。ヒストリバッファ２１２内でマッチングシーケンスを見つけることをさらに最適化して、データ圧縮の効率をさらに高めることができる。
【００６２】
例えば、ブロック７０２では、マッチングシーケンスは、ルックアップテーブルを使用し、またしきい値を使用して見つけられる。さまざまなしきい値が使用できる。例えば、マッチングシーケンスを見つけるための比較は、実行される比較の回数を制限するためヒストリバッファ内の所定の数の位置で実行するようにできる。ストリーミング配信されるデータと比較されるヒストリバッファ内の位置の数を制限することにより、位置のサイズ（例えば、バイト数）を制限することができる。例えば、すでに説明したように、ヒストリバッファ２１２内のマッチングシーケンスの位置は、マッチングシーケンスの先頭または末尾とカレントポインタの先頭または末尾との間の相対的位置として記述することができ、これはバックポインタにより記述することができる。したがって、実行される比較の回数を制限することにより、マッチングシーケンスは、カレントポインタの「より近く」に配置される可能性が高くなる。したがって、この「近さ」ゆえに、位置はより小さな値をもつことができ、例えば、使用するバイトをより少なくできる。他の実施例では、所定のしきい値を超える値を持つ位置を考慮しないような、またこの位置に対する値のサイズを制限する役目をすることができるようなしきい値を採用することができる。そのため、探索する位置の数、それぞれの位置を記述する値のサイズ、それぞれの配置されているシーケンスの長さを記述する値のサイズなど、さまざまなしきい値を使用することができる。
【００６３】
決定ブロック７０４で、マッチングシーケンスの位置を記述するバックポインタが最も長い間参照されていない（ＬＲＵ）テーブルに含まれているかどうかに関して判別する。ＬＲＵテーブルを使用して、最も長い間参照されていないバックポインタを格納することができる。マッチングシーケンスのバックポインタがＬＲＵテーブルに含まれている場合、ＬＲＵテーブル内のバックポインタに対応するＬＲＵ表現は、マッチングシーケンスのバックポインタを符号化するために使用される。例えば、ＬＲＵテーブルは、４つの最も長い間参照されていないバックポインタがＬＲＵテーブルに格納されるように深さ４（ｄｅｐｔｈ ｏｆ ｆｏｕｒ）を持つことができる。ＬＲＵ内のバックポインタはそれぞれ、ＬＲＵテーブルへマッピングする対応するＬＲＵ表現を有する。したがって、バックポインタがＬＲＵテーブルに含まれている場合、その後ブロック７０６で、バックポインタをＬＲＵテーブルからのＬＲＵ表現を用いて符号化することができる。このようにして、圧縮モジュールは、ストリーミングデータ内に見つけられる追加パターンを処理して、さらにデータを圧縮することができる。例えば、サーバからクライアントにストリーミング配信されるグラフィックデータは、ヒストリバッファ内の類似のオフセットで繰り返されるマッチングシーケンスを含むことができる。したがって、マッチングシーケンスは、マッチングシーケンスの長さおよび位置を含み、その位置はさらにＬＲＵ表現を使用することにより圧縮される、表現を使用して圧縮することができる。
【００６４】
バックポインタがＬＲＵテーブルに含まれていない場合、次いでブロック７０８で、バックポインタを図２のハフマンテーブル２２８を使用して符号化することができる。ハフマン符号化は、さらに圧縮するそれぞれのバックポインタの出現度数を関連付ける出現度数テーブルから始めることができる。それぞれのバックポインタに、そのバックポインタを一意に表す可変長文字列が割り当てられる。例えば、それぞれの可変長文字列に一意的なプレフィクス（ｐｒｅｆｉｘ）をもつことができる。その後、それらの文字列をツリー状に配列して、各バックポインタおよび表現をそれぞれ符号化および復号化することができる。バックポインタを符号化するために、バックポインタはツリー内に配置される。バックポインタを含む葉を特定するために使用されるツリーの枝を利用して、バイトシーケンスを符号化する、つまり、バックポインタの表現を与える。例えば、ハフマン符号化に使用されるツリーの各枝には出力アルファベットの記号、例えば、ビット０と１がマークされ、符号化は、ツリーのルートから符号化されるバックポインタまでの経路上の枝マーキングの列挙となる。各表現の復号化は、バックポインタを含むツリーの葉に到達するまで、文字列内のそれぞれの連続する値に基づき、ツリーをその原点から下へ枝を通りツリーの葉へとたどることによって実行される。
【００６５】
ブロック７１０で、マッチングシーケンスの長さも、ハフマンテーブルを使用して符号化される。例えば、図２のハフマンテーブル２３０を使用して、ヒストリバッファ内のマッチングシーケンスの長さを符号化し、さらにデータを圧縮することができる。長さは、バックポインタについて説明されているとおりに符号化することができる。
【００６６】
ブロック７１２で、マッチングシーケンスは、ヒストリバッファ内のマッチングシーケンスの位置およびマッチングシーケンスの長さを記述するバックポインタを含むタプルとして構成された表現により表される。ブロック７１４で、コスト関数を使用することにより、マッチングシーケンスに比べて、その表現がより効率的かどうか、例えば、使用されるメモリリソースが格納時により少なく、かつ／または使用される帯域幅がストリーミング配信時により小さいかを判別する。例えば、場合によっては、マッチングシーケンスに使用されるバイト数は、ヒストリバッファ内のマッチングシーケンスの位置および長さを記述する表現よりも少ない。したがって、コスト関数を使用して、表現またはマッチングシーケンス、つまり、データ内のリテラルシーケンスがより効率的かどうかを判別することができる。さまざまなコスト関数が使用できる。例えば、コスト関数は、バックポインタのサイズとマッチングシーケンスの長さのとの積を使用することができる。
【００６７】
決定ブロック７１６で、その表現がより効率的である場合、次いでブロック７１８で、マッチングシーケンスをその表現で表すことにより圧縮データが形成される。ブロック７２０で、カレントポインタが更新され、次の初期シーケンスが処理される。例えば、カレントポインタは、マッチングシーケンスの長さずつ増分され、データ内の次のシーケンスについてこの手順を繰り返すことができる。ストリーミング配信するデータを通じてカレントポインタが増分されると、圧縮データは、クライアントにストリーミング配信される。
【００６８】
決定ブロック７１６で、表現があまり効率的でない場合、ブロック７２２で、マッチングシーケンスはすでに説明したようにハフマンテーブルを使用して表される。ブロック７２０で、カレントポインタは、マッチングシーケンス内のバイト数ずつ増分され、次のシーケンスについてこの手順が続いて行われる。
【００６９】
すでに説明しているように、ハフマンテーブルにより、ストリーミング配信されるデータをさらに圧縮することができる。バックポインタ、長さ、およびリテラルシーケンスをそれぞれ符号化するための３つのハフマンテーブルを説明してきた。他の実施例では、ハフマンテーブルを組み合わせることができる。例えば、図２に示されるように、ハフマンテーブル２２８を使用して、リテラル２３２バイトシーケンスおよびバックポインタ２３４を符号化することができる。圧縮ストリーム内のバックポインタとリテラルシーケンスとを区別するために、バックポインタおよびリテラルシーケンスに、それぞれの一意的なプレフィクスを与えることができ、例えば、それぞれのバックポインタがビット「０」から始まり、それぞれのリテラルシーケンスがビット「１」から始まるようにすることができる。他の実施例では、統一インデックスコード（ｕｎｉｆｉｅｄ ｉｎｄｅｘ ｃｏｄｅ）を使用して、バックポインタおよびリテラルシーケンスがそれぞれ異なる文字を有するように、リテラルシーケンスとバックポインタの両方を単一のアルファベットに組み合わせることにより、リテラルシーケンスとバックポインタの両方を符号化することができる。
【００７０】
すでに説明してあるハフマンテーブルなどの符号化テーブルは、さまざまな方法で提供することができる。例えば、一実施例では、ストリーミング配信されるデータのパケット毎に符号化テーブルを計算する必要がないように、符号化テーブルを圧縮モジュールおよび伸張モジュールが使用するためにあらかじめ構成しておく。これを使用することにより、暗号化プロセスの速度を高めることができる。他の実施例では、符号化テーブルは、所定の間隔で動的に計算される。例えば、符号化テーブルは、所定の数のパケットを受信し符号化テーブルを更新する毎に再計算されるようにしてもよい。
【００７１】
図８は、データ圧縮をさらに最適化するためにシーケンスの比較が最適化される一実施例８００の図である。前述同様に、サーバ１０２は、ヒストリバッファ２１２およびルックアップテーブル２１６を備える。サーバ１０２は、圧縮モジュール１１６を実行して、パケット３０４（３）を圧縮する。ヒストリバッファ２１２の先頭から最初の２バイトが同じである最も右側のシーケンスの先頭までのオフセットを、ｉ１＝ＨＡＳＨ［ＨＡＳＨ＿ＳＵＭ（ｓ）］と表すことができる。示されている実施例では、「ｓ」は「４ ５」に等しく、ヒストリバッファ２１２の先頭から数えゼロから始める場合、ｉ１＝１０である。ヒストリバッファ２１２の先頭から次に最も右側のシーケンスまでの次のオフセットは、ｉ２＝ＮＥＸＴ［ｉ１］と表すことができる。図８に示されている実施例では、ハッシュチェーン８０２（ｋ）内でｉ２＝ＮＥＸＴ［１０］＝４である。同様に、ヒストリバッファ２１２の先頭からの続く各オフセットは、ｉ３＝ＮＥＸＴ［ｉ２］などハッシュチェーン８０２（ｋ）内で表すことができる。示されている実施例では、「４ ５」を含むヒストリバッファ２１２内にはほかにシーケンスがないためｉ３＝０である。
【００７２】
圧縮モジュール１１６は、実行時に、ヒストリバッファ２１２内の位置１６にある「４
５」から始まるパケット３０４（３）を圧縮する手順を開始することができる。圧縮モジュール１１６は、まず、ハッシュチェーン８０２（ｋ）の位置ｉ１＝ＨＡＳＨ［ＨＡＳＨ＿ＳＵＭ （’４’，’５’）］＝１０から初期シーケンス「４ ５」を含むシーケンスをヒストリバッファ２１２内で特定することができる。この位置は記憶され、ＮＥＸＴ［１６］は１０に設定され、ＨＡＳＨ［ＨＡＳＨ＿ＳＵＭ（’４’，’５’）］は１６に設定される。シーケンスは、最初にそれぞれのシーケンス内で次に続くバイトを比較することによって、現在位置（１６）および位置ｉ１（１０）で、一方を他方と比較される。この場合、パケット３０４（３）内の第３バイトとパケット３０４（２）内の第５バイトとを比較して、一致を見つける。示されている実施例では、ＨＩＳＴＯＲＹ［１０＋３］＝’３’およびＨＩＳＴＯＲＹ［１６＋３］＝’６’であるため、次に続くバイト（つまり、それぞれのシーケンス内の３番目のバイト）は異なる。したがって、期待されるマッチングシーケンスの長さは２のままであり、期待されるマッチングシーケンスの位置は１０のままである。
【００７３】
その後、圧縮モジュール１１６は、ルックアップテーブル２１６から位置ｉ２＝ＮＥＸＴ［ｉ１］＝４にある、ヒストリバッファ２１２内の次のシーケンスを特定することができる。ｉ２はゼロに等しくないため、少なくとも２つのバイトの一致がある。それぞれのバイト「４ ５」に続く次のバイトが前のように比較され、結果的に４バイトの一致が得られる。したがって、期待されるマッチングシーケンスの長さは４に設定され、期待されるマッチングシーケンスの位置は４に設定される。その後、圧縮モジュール１１６は、ハッシュチェーン８０２（ｋ）から位置ｉ３＝ＮＥＸＴ［ｉ２］＝０にある、ヒストリバッファ２１２内の他のシーケンスを特定することができる。ｉ３はゼロに等しいため、それはハッシュチェーン８０２（ｋ）の末尾であり、他の位置は比較されない。一実施例では、圧縮モジュール１１６は、ハッシュチェーン８０２（ｋ）の末尾を特にはチェックしないことに留意されたい。その代わりに、位置「ｉ０」（図８に示す例では１６）、ＮＥＸＴ［０］にあるシーケンスはｉ０に等しく設定される。したがって、ハッシュチェーン８０２（ｋ）の末尾（ｉＮ＝ＮＥＸＴ［ｉ｛Ｎ−１｝］＝０）に到達したときに、チェックされ、圧縮モジュール１１６はｉ｛Ｎ＋１｝＝ＮＥＸＴ［ｉＮ］＝ｉ０に進む。
【００７４】
期待されるマッチングシーケンスの長さの後の続く「次の」バイトを比較することにより、比較速度を改善することができる。例えば、前の実施例では、ＨＩＳＴＯＲＹ［ｉ０＋ＭａｔｃｈＬｅｎｇｔｈ］はＨＩＳＴＯＲＹ［ｉ０＋ＭａｔｃｈＬｅｎｇｔｈ］と比較された。ヒストリバッファ２１２内に比較すべき他のシーケンスがない場合、それぞれの位置にあるシーケンス全体の比較が実行される。つまり、ヒストリバッファ２１２内のそれぞれの位置にあるそれぞれのシーケンス内で、各バイトについて一方が他方と比較される。シーケンス全体の比較が成功すると、マッチングシーケンスが導かれる。このようにして、ヒストリバッファ２１２内のシーケンスの比較において、かなりのスピードアップを得ることができる。
【００７５】
図９は、システムから受け取ったフィードバックに応じて圧縮が動的にチューニングされる一実施例におけるシステム９００の図である。ネットワーク上のサーバ１０２とクライアント１０４間の通信は、さまざまなファクタにより変化する場合がある。例えば、クライアント１０４では、ソフトウェアおよび／またはハードウェアリソースの制限があり、クライアント１０４でのデータの伸張は、サーバ１０２での圧縮よりも時間が長くかかる場合がある。他の実施例では、サーバ１０２は、データを複数のクライアントに供給するので、クライアントは、サーバ１０２がそれらのクライアントのそれぞれのためにデータを圧縮できる速度よりも、高速にデータを伸張することができる。すでに説明した圧縮パラメータの１つまたは複数をチューニングすることにより、サーバ１０２とクライアント１０４のハードウェアおよび／またはソフトウェアリソースならびにそれらを通信可能に接続するネットワーク１０６のリソースを考慮に入れ、サーバ１０２とクライアント１０４間の通信を最適化することができる。例えば、サーバ１０２がクライアント１０４に圧縮データを送信するのを「待機している」場合、サーバ１０２は、追加圧縮計算を実行して、さらにデータを圧縮することができる。
【００７６】
ＲＤＰ １１２の圧縮モジュール１１６のパラメータをチューニングするために、フィードバックを求める。さまざまなファクタをフィードバックとして使用し、一般的なネットワーク特性などの圧縮パラメータをチューニングすることができる。例えば、圧縮モジュール１１６が、低速なリンクであるためネットワークの逆圧（ｂａｃｋｐｒｅｓｓｕｒｅ）が生じていることを示すネットワークレイヤからの情報を使用して、さらにデータを圧縮するにはさらに時間がかかることを示すことができる。したがって、逆圧がある場合、最終的な出力サイズの削減のためデータの圧縮にさらに時間をかけるように、圧縮モジュール１１６を動的にチューニングすることができる。
【００７７】
他の実施例では、ＲＤＰ １１２は、ヒストリバッファ９０４（１）、…、９０４（ｈ）、…、９０４（Ｈ）の固定プール９０２を利用することができる。データを送信しなければならない上位レイヤは、プール９０２にバッファ（例えば、バッファ９０４（ｈ））を要求すること（割り当てること）、バッファ９０４（ｈ）にデータを埋め込むこと（データを圧縮することを含む）、その後圧縮されたデータをクライアント１０４に送信することで動作する。バッファ９０４（ｈ）は、バッファのコンテンツが送信されている場合のみ、プール９０２に戻される、つまり「解放される」。この技術により、ＲＤＰ １１２、より具体的には圧縮モジュール１１６は、バッファを「解放して」バッファプールに戻すのに要する時間の長さに基づいて、ネットワーク接続が低速であるか、または高速であるか（例えば、帯域幅の大きさ）、クライアントが低速であるか、または高速であるか（例えば、クライアントがデータを伸張するのに要する時間）などに関するフィードバック、つまり逆圧情報（ｂａｃｋｐｒｅｓｓｕｒｅ ｉｎｆｏｒｍａｔｉｏｎ）を取得することができる。
【００７８】
さらに他の実施例では、プール９０２のバッファ９０４（１）〜９０４（Ｈ）のどれもが使用できない場合、圧縮にさらに時間をかけるようにさまざまな圧縮しきい値をチューニングすることにより、圧縮モジュール１１６を「いっそう働く」ように適合させることができる。いったんネットワーク状態が改善されたら、圧縮モジュール１１６をチューニングして、データの送出がさらに速くなるように圧縮動作回数を減らすこともできる。例えば、ネットワーク１０６に使用可能な帯域幅がかなりある場合、データ通信にかかる時間を短縮する必要がないため、実行される圧縮動作の回数を減らすことができる。このように、変動するネットワーク状態に基づき実行時に圧縮パラメータが変更されるように動的な技術を採用することができる。他の実施例では、ネットワーク速度の初期測定を利用してパラメータをチューニングし、その後、これらのパラメータをセッション全体で使用する。
【００７９】
すでに述べたように、圧縮モジュール１１６のチューニングに使用されるファクタについては、サーバ１０２のハードウェアおよび／またはソフトウェアリソースも考慮に入れることできる。例えば、サーバ１０２上の負荷を考慮に入れることができ（例えば、どれくらいのアクティブセッションがサーバ１０２により提供されているか、図２のプロセッサ２０２上の負荷など）、圧縮の強さを動的にチューニングし、圧縮でＣＰＵをあまり使わないことにより補償することができる。チューニングできる圧縮パラメータの一例として、検索ウィンドウのサイズがある。例えば、検索ウィンドウのサイズを６４Ｋから５１２Ｋまででチューニングすることができる。ウィンドウのサイズを大きくすると、相対的圧縮度が高くなるが、実行が遅くなることがある。したがって、ネットワークが低速であるとみなされる場合には、大きなウィンドウに「切り換える」と都合がよい。
【００８０】
圧縮モジュール１１６をチューニングするために使用されるファクタの他の例では、一致を探すためにトラバースされるハッシュチェーン内のリンクの数をチューニングすることができる。例えば、長いチェーンリンクを辿ると、より長い一致が見つかる確率が高まるが、照合を実行するのに追加のハードウェアおよび／またはソフトウェアリソースのコストがかかる場合がある。
【００８１】
圧縮モジュール１１６をチューニングするために使用されるファクタのさらなる例は、検索を終了するために見つかった最長一致を指定するしきい値である。すでに説明しているように、しきい値を使用することにより、一致を見つけるために実行される検索の回数を制限することができる。このしきい値が大きいほど、より長い一致が見つかる確率が高まり、したがってデータの圧縮がさらに行われる。しかし、この検索を実行する場合、さらに多くの処理リソースが使用される場合もある。さまざまなファクタおよびパラメータについて説明してきたが、他のさまざまなファクタおよびパラメータも、本明細書で説明したように使用することができる。
【００８２】
本発明を、構造的特徴および／または方法論的動作に固有の専門用語で説明してきたが、添付の特許請求の範囲で規定する本発明は、説明した特定の機能または動作に必ずしも限定されるものではないことを理解されたい。むしろ、特定の機能および動作は、請求する本発明の例示的な実施形態として開示している。
【符号の説明】
【００８３】
１０２ サーバ
１０４ クライアント
１０６ ネットワーク
１０８（１），１０８（ｎ），１０８（Ｎ） アプリケーション
１１６ 圧縮モジュール
１１８ 伸張モジュール
１２０（１），１２０（ｍ），１２０（Ｍ） アプリケーション
２０２ プロセッサ
２０４，２０８ メモリ
２０６ プロセッサ
２１０ 入力デバイス
２１２，２１４ ヒストリバッファ
２１６ ルックアップテーブル
２１８ ハフマンテーブル
２２０，２２８，２３０ ハフマンテーブル
２２２ リテラルバイト
２２４ バックポインタ値
２２６ 一致長
２３２ リテラル
２３６，２３８ ＬＲＵテーブル
２３４ バックポインタ
【特許請求の範囲】
【請求項１】
データを圧縮するための方法であって、
記憶手段に格納されているデータ内のシーケンスと一致する、ルックアップテーブル内のインデックスを検索するステップであって、前記ルックアップテーブルは、インデックスに対応する１つまたは複数の、前記記憶手段内の位置を有する、ステップと、
前記検索されたシーケンスに対応する位置が、ＬＲＵ（Last Recently Used）テーブルにおいて参照されていない時間が最も長い複数の位置の１つと一致するかどうかを判別するステップであって、前記ＬＲＵテーブル中の各位置は、対応するシーケンスの位置を符号化するためのＬＲＵ表現を有し、かつ、以前ストリーミング配信されたデータ内のシーケンスが参照されていない時間が最も長い複数の位置の１つを示す参照となる、ステップと、
前記検索されたシーケンスの位置が前記ＬＲＵテーブルに含まれる場合は、前記ＬＲＵテーブルを参照し、対応するＬＲＵ表現を使用して前記検索されたシーケンスの位置を符号化し、かつ、第１のハフマン符号を使用して前記検索されたシーケンスの長さを符号化するステップであって、前記データは、前記検索されたシーケンスの位置および長さを符号化することにより圧縮される、ステップと、または、
前記検索されたシーケンスの位置が前記ＬＲＵテーブルに含まれない場合は、前記ＬＲＵ表現を使用せずに、前記検索されたシーケンスの位置を符号化し、かつ、第１のハフマン符号を使用して前記検索されたシーケンスの長さを符号化するステップであって、前記データは、前記検索されたシーケンスの位置および長さを符号化することにより圧縮される、ステップと
を備えることを特徴とする方法。
【請求項２】
前記符号化された１つまたは複数の位置を含む圧縮データをストリーミング配信するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記インデックスを検索するステップは、前記検索されたインデックスの各位置を含むハッシュチェーンを参照することを特徴とする請求項１に記載の方法。
【請求項４】
前記シーケンスおよび前記インデックスは、それぞれ、少なくとも２バイトからなることを特徴とする請求項１に記載の方法。
【請求項５】
前記圧縮データは、１つまたは複数のパケットとして形成されており、前記パケットは、圧縮が各パケットごとに行われるようネットワーク経由送信のために圧縮されることを特徴とする請求項１に記載の方法。
【請求項６】
前記検索されたシーケンスの位置は、ハフマン符号化と、算術符号化と、プレフィクス符号化と、マルコフ符号化とからなるグループから選択された符号化技術を使用して符号化されることを特徴とする請求項１に記載の方法。
【請求項７】
前記インデックスを検索するステップでは、しきい値を使用して実行することを特徴とする請求項１に記載の方法。
【請求項８】
請求項１に記載の方法をコンピュータに実行させるためのコンピュータ実行可能命令を備えるプログラムを記録したコンピュータ読み取り可能な媒体。
【請求項９】
データを前記記憶手段に追加するステップと、
追加されたデータを前記ルックアップテーブルに含めるために前記記憶手段を参照するルックアップテーブルを更新するステップとをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１０】
データを圧縮するためのサーバであって、
記憶手段に格納されているデータ内のシーケンスと一致する、ルックアップテーブル内のインデックスを検索し、前記ルックアップテーブルは、対応するインデックスの１つまたは複数の、前記記憶手段内の位置を有する位置を有しており、
前記検索されたシーケンスの位置が、ＬＲＵ（Last Recently Used）テーブルにおける最も長い間参照されていない複数の位置の１つと一致するかどうかを判別し、前記ＬＲＵテーブル中の各位置は、対応するシーケンスの位置を符号化するためのＬＲＵ表現を有し、かつ、以前ストリーミング配信されたデータ内のシーケンスの最も長い間参照されていない複数の位置の１つを示す参照となり、
前記検索されたシーケンスの位置が前記ＬＲＵテーブルに含まれる場合は、前記ＬＲＵテーブルを参照し、対応するＬＲＵ表現を使用して前記検索されたシーケンスの位置を符号化し、かつ、第１のハフマン符号を使用して前記検索されたシーケンスの長さを符号化する処理であって、前記データは、前記検索されたシーケンスの位置および長さを符号化することにより圧縮される、処理と、または、
前記検索されたシーケンスの位置が前記ＬＲＵテーブルに含まれない場合は、前記ＬＲＵ表現を使用せずに、前記検索されたシーケンスの位置を符号化し、かつ、第１のハフマン符号を使用して前記検索されたシーケンスの長さを符号化する処理であって、前記データは、前記検索されたシーケンスの位置および長さを符号化することにより圧縮される、処理と
を実行するように構成されていることを特徴とするサーバ。
【請求項１１】
前記サーバはさらに、前記符号化された１つまたは複数の位置を含む圧縮データをストリーミング配信するように構成されていることを特徴とする請求項１０に記載のサーバ。
【請求項１２】
前記サーバは、インデックスを検索する場合に、前記検索されたインデックスの各位置を含むハッシュチェーンを参照することを特徴とする請求項１０に記載のサーバ。
【請求項１３】
前記シーケンスおよび前記インデックスは、それぞれ、少なくとも２バイトからなることを特徴とする請求項１０に記載のサーバ。
【請求項１４】
前記圧縮データは、１つまたは複数のパケットとして形成されており、前記パケットは、圧縮が各パケットごとに行われるようネットワーク経由送信のために圧縮されることを特徴とする請求項１０に記載のサーバ。
【請求項１５】
前記検索されたシーケンスの位置は、ハフマン符号化と、算術符号化と、プレフィクス符号化と、マルコフ符号化とからなるグループから選択された符号化技術を使用して符号化されることを特徴とする請求項１０に記載のサーバ。
【請求項１６】
ネットワークと、
サーバであって、
複数のバイトを有する第１のヒストリバッファと、
複数のエントリを含むルックアップテーブルであって、前記エントリのそれぞれは複数のインデックスのうちの特定の１つを使用して発見可能であり、前記エントリのそれぞれは対応する前記インデックスが前記ヒストリバッファ内に置かれているかを示す参照であり、もし置かれていれば、前記ヒストリバッファ内の前記対応する前記インデックスの１つまたは複数の位置を示す参照である、ルックアップテーブルと、
前記ヒストリバッファ内のマッチングシーケンスの長さ分の符号を含む第１のハフマンテーブルと、
マッチングシーケンスの位置およびリテラルバイトを含む第２のハフマンテーブルと、
圧縮モジュールであって、
リモートアクセスの要求に応じてストリーミング配信されるデータ内のカレントポインタが指す初期シーケンスと一致する前記ルックアップテーブル内の前記インデックスの１つを見つけ、
前記マッチングインデックスの前記対応する前記エントリが１つまたは複数の前記位置を参照している場合、
前記マッチングインデックスを持つ前記位置のそれぞれのシーケンスと前記カレントポインタが指す前記データ内のシーケンスとを比較し、
前記比較からマッチングシーケンスを導き、
前記第１のヒストリバッファ内の前記マッチングシーケンスの前記位置および長さを含む表現を含むようにデータを構成し、前記第１のハフマンテーブルを使用してマッチングシーケンスの位置を符号化し、ＬＲＵ（Last Recently Used）テーブルを使用してマッチングシーケンスの位置を符号化し、前記ＬＲＵテーブルは、最近のマッチングシーケンスの参照された複数の位置をリスト化しており、前記マッチングシーケンスの位置が前記ＬＲＵテーブルに存在しない場合は、前記マッチングシーケンスの位置が前記第２のハフマンテーブルを使用して符号化されて、前記マッチングシーケンスの前記長さだけ前記カレントポインタを進め、
前記マッチングインデックスの前記対応するエントリが前記位置をどれも参照しない場合、前記初期シーケンスを含むようにデータを構成し、前記第２のハフマンテーブルを使用して前記初期シーケンスのリテラルバイトを符号化して、前記初期シーケンスの長さだけ前記カレントポインタを進め、
前記カレントポインタが前記追加データを通じて進めたときに、前記ネットワーク経由で、パケット化済みの構成されたデータをストリーミング配信するようにサーバを実行させる圧縮モジュールと、を備えるサーバと、
前記サーバと通信するために、前記ネットワークに通信接続され、第２のプロセッサおよび第２のメモリを備え、第２のヒストリバッファ、マッチングシーケンスの位置およびリテラルバイトを復号化するための符号を含む第３のハフマンテーブル、マッチングシーケンスの長さ分を復号化するための符号を含む第４のハフマンテーブル、ＬＲＵテーブル、および、ストリーミング配信データを伸張可能にする伸張モジュールを備えるクライアントと、を備え、
前記クライアントは、前記構成されたデータを受信するように構成されており、
符号化された表現が前記構成されたデータに存在している場合、前記伸張モジュールに従ってクライアントは、前記ＬＲＵテーブル、前記第３のハフマンテーブルおよび前記第４のハフマンテーブルを使用して、前記表現により示される復号後の位置および復号後の長さに基づいて前記第２のヒストリバッファ内のマッチングシーケンスを見つけることにより、前記表現を復号するように構成されていることを特徴とするシステム。
【請求項１】
データを圧縮するための方法であって、
記憶手段に格納されているデータ内のシーケンスと一致する、ルックアップテーブル内のインデックスを検索するステップであって、前記ルックアップテーブルは、インデックスに対応する１つまたは複数の、前記記憶手段内の位置を有する、ステップと、
前記検索されたシーケンスに対応する位置が、ＬＲＵ（Last Recently Used）テーブルにおいて参照されていない時間が最も長い複数の位置の１つと一致するかどうかを判別するステップであって、前記ＬＲＵテーブル中の各位置は、対応するシーケンスの位置を符号化するためのＬＲＵ表現を有し、かつ、以前ストリーミング配信されたデータ内のシーケンスが参照されていない時間が最も長い複数の位置の１つを示す参照となる、ステップと、
前記検索されたシーケンスの位置が前記ＬＲＵテーブルに含まれる場合は、前記ＬＲＵテーブルを参照し、対応するＬＲＵ表現を使用して前記検索されたシーケンスの位置を符号化し、かつ、第１のハフマン符号を使用して前記検索されたシーケンスの長さを符号化するステップであって、前記データは、前記検索されたシーケンスの位置および長さを符号化することにより圧縮される、ステップと、または、
前記検索されたシーケンスの位置が前記ＬＲＵテーブルに含まれない場合は、前記ＬＲＵ表現を使用せずに、前記検索されたシーケンスの位置を符号化し、かつ、第１のハフマン符号を使用して前記検索されたシーケンスの長さを符号化するステップであって、前記データは、前記検索されたシーケンスの位置および長さを符号化することにより圧縮される、ステップと
を備えることを特徴とする方法。
【請求項２】
前記符号化された１つまたは複数の位置を含む圧縮データをストリーミング配信するステップをさらに備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記インデックスを検索するステップは、前記検索されたインデックスの各位置を含むハッシュチェーンを参照することを特徴とする請求項１に記載の方法。
【請求項４】
前記シーケンスおよび前記インデックスは、それぞれ、少なくとも２バイトからなることを特徴とする請求項１に記載の方法。
【請求項５】
前記圧縮データは、１つまたは複数のパケットとして形成されており、前記パケットは、圧縮が各パケットごとに行われるようネットワーク経由送信のために圧縮されることを特徴とする請求項１に記載の方法。
【請求項６】
前記検索されたシーケンスの位置は、ハフマン符号化と、算術符号化と、プレフィクス符号化と、マルコフ符号化とからなるグループから選択された符号化技術を使用して符号化されることを特徴とする請求項１に記載の方法。
【請求項７】
前記インデックスを検索するステップでは、しきい値を使用して実行することを特徴とする請求項１に記載の方法。
【請求項８】
請求項１に記載の方法をコンピュータに実行させるためのコンピュータ実行可能命令を備えるプログラムを記録したコンピュータ読み取り可能な媒体。
【請求項９】
データを前記記憶手段に追加するステップと、
追加されたデータを前記ルックアップテーブルに含めるために前記記憶手段を参照するルックアップテーブルを更新するステップとをさらに備えることを特徴とする請求項１に記載の方法。
【請求項１０】
データを圧縮するためのサーバであって、
記憶手段に格納されているデータ内のシーケンスと一致する、ルックアップテーブル内のインデックスを検索し、前記ルックアップテーブルは、対応するインデックスの１つまたは複数の、前記記憶手段内の位置を有する位置を有しており、
前記検索されたシーケンスの位置が、ＬＲＵ（Last Recently Used）テーブルにおける最も長い間参照されていない複数の位置の１つと一致するかどうかを判別し、前記ＬＲＵテーブル中の各位置は、対応するシーケンスの位置を符号化するためのＬＲＵ表現を有し、かつ、以前ストリーミング配信されたデータ内のシーケンスの最も長い間参照されていない複数の位置の１つを示す参照となり、
前記検索されたシーケンスの位置が前記ＬＲＵテーブルに含まれる場合は、前記ＬＲＵテーブルを参照し、対応するＬＲＵ表現を使用して前記検索されたシーケンスの位置を符号化し、かつ、第１のハフマン符号を使用して前記検索されたシーケンスの長さを符号化する処理であって、前記データは、前記検索されたシーケンスの位置および長さを符号化することにより圧縮される、処理と、または、
前記検索されたシーケンスの位置が前記ＬＲＵテーブルに含まれない場合は、前記ＬＲＵ表現を使用せずに、前記検索されたシーケンスの位置を符号化し、かつ、第１のハフマン符号を使用して前記検索されたシーケンスの長さを符号化する処理であって、前記データは、前記検索されたシーケンスの位置および長さを符号化することにより圧縮される、処理と
を実行するように構成されていることを特徴とするサーバ。
【請求項１１】
前記サーバはさらに、前記符号化された１つまたは複数の位置を含む圧縮データをストリーミング配信するように構成されていることを特徴とする請求項１０に記載のサーバ。
【請求項１２】
前記サーバは、インデックスを検索する場合に、前記検索されたインデックスの各位置を含むハッシュチェーンを参照することを特徴とする請求項１０に記載のサーバ。
【請求項１３】
前記シーケンスおよび前記インデックスは、それぞれ、少なくとも２バイトからなることを特徴とする請求項１０に記載のサーバ。
【請求項１４】
前記圧縮データは、１つまたは複数のパケットとして形成されており、前記パケットは、圧縮が各パケットごとに行われるようネットワーク経由送信のために圧縮されることを特徴とする請求項１０に記載のサーバ。
【請求項１５】
前記検索されたシーケンスの位置は、ハフマン符号化と、算術符号化と、プレフィクス符号化と、マルコフ符号化とからなるグループから選択された符号化技術を使用して符号化されることを特徴とする請求項１０に記載のサーバ。
【請求項１６】
ネットワークと、
サーバであって、
複数のバイトを有する第１のヒストリバッファと、
複数のエントリを含むルックアップテーブルであって、前記エントリのそれぞれは複数のインデックスのうちの特定の１つを使用して発見可能であり、前記エントリのそれぞれは対応する前記インデックスが前記ヒストリバッファ内に置かれているかを示す参照であり、もし置かれていれば、前記ヒストリバッファ内の前記対応する前記インデックスの１つまたは複数の位置を示す参照である、ルックアップテーブルと、
前記ヒストリバッファ内のマッチングシーケンスの長さ分の符号を含む第１のハフマンテーブルと、
マッチングシーケンスの位置およびリテラルバイトを含む第２のハフマンテーブルと、
圧縮モジュールであって、
リモートアクセスの要求に応じてストリーミング配信されるデータ内のカレントポインタが指す初期シーケンスと一致する前記ルックアップテーブル内の前記インデックスの１つを見つけ、
前記マッチングインデックスの前記対応する前記エントリが１つまたは複数の前記位置を参照している場合、
前記マッチングインデックスを持つ前記位置のそれぞれのシーケンスと前記カレントポインタが指す前記データ内のシーケンスとを比較し、
前記比較からマッチングシーケンスを導き、
前記第１のヒストリバッファ内の前記マッチングシーケンスの前記位置および長さを含む表現を含むようにデータを構成し、前記第１のハフマンテーブルを使用してマッチングシーケンスの位置を符号化し、ＬＲＵ（Last Recently Used）テーブルを使用してマッチングシーケンスの位置を符号化し、前記ＬＲＵテーブルは、最近のマッチングシーケンスの参照された複数の位置をリスト化しており、前記マッチングシーケンスの位置が前記ＬＲＵテーブルに存在しない場合は、前記マッチングシーケンスの位置が前記第２のハフマンテーブルを使用して符号化されて、前記マッチングシーケンスの前記長さだけ前記カレントポインタを進め、
前記マッチングインデックスの前記対応するエントリが前記位置をどれも参照しない場合、前記初期シーケンスを含むようにデータを構成し、前記第２のハフマンテーブルを使用して前記初期シーケンスのリテラルバイトを符号化して、前記初期シーケンスの長さだけ前記カレントポインタを進め、
前記カレントポインタが前記追加データを通じて進めたときに、前記ネットワーク経由で、パケット化済みの構成されたデータをストリーミング配信するようにサーバを実行させる圧縮モジュールと、を備えるサーバと、
前記サーバと通信するために、前記ネットワークに通信接続され、第２のプロセッサおよび第２のメモリを備え、第２のヒストリバッファ、マッチングシーケンスの位置およびリテラルバイトを復号化するための符号を含む第３のハフマンテーブル、マッチングシーケンスの長さ分を復号化するための符号を含む第４のハフマンテーブル、ＬＲＵテーブル、および、ストリーミング配信データを伸張可能にする伸張モジュールを備えるクライアントと、を備え、
前記クライアントは、前記構成されたデータを受信するように構成されており、
符号化された表現が前記構成されたデータに存在している場合、前記伸張モジュールに従ってクライアントは、前記ＬＲＵテーブル、前記第３のハフマンテーブルおよび前記第４のハフマンテーブルを使用して、前記表現により示される復号後の位置および復号後の長さに基づいて前記第２のヒストリバッファ内のマッチングシーケンスを見つけることにより、前記表現を復号するように構成されていることを特徴とするシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−１９５３２（Ｐ２０１２−１９５３２Ａ）
【公開日】平成２４年１月２６日（２０１２．１．２６）
【国際特許分類】
【出願番号】特願２０１１−１８０７８３（Ｐ２０１１−１８０７８３）
【出願日】平成２３年８月２２日（２０１１．８．２２）
【分割の表示】特願２００５−２８１９４（Ｐ２００５−２８１９４）の分割
【原出願日】平成１７年２月３日（２００５．２．３）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
【公開日】平成２４年１月２６日（２０１２．１．２６）
【国際特許分類】
【出願日】平成２３年８月２２日（２０１１．８．２２）
【分割の表示】特願２００５−２８１９４（Ｐ２００５−２８１９４）の分割
【原出願日】平成１７年２月３日（２００５．２．３）
【出願人】（５０００４６４３８）マイクロソフト コーポレーション (3,165)
【Ｆターム（参考）】
[ Back to top ]