(57)【特許請求の範囲】
【請求項１】
データ通信方法であって、
（Ａ）データの入力ストリームを複数のパケットに分割するステップ、
（Ｂ）前記複数のパケットの内の特定のパケットに対し、それぞれのパケットヒストリー状態を少なくとも１つの受領確認ベクトルに関連して特定するステップ、
（Ｃ）前記複数のパケットの内の特定のパケットを、関連するパケットヒストリーに関連して符号化するステップ、及び
（Ｄ）前記複数のパケットを圧縮データストリームに圧縮するステップ
から成る方法。
【請求項２】
前記パケットに関連するそれぞれのパケットヒストリー状態を、複数の受信したパケットを特徴付ける情報を含む少なくとも１つの受領確認ベクトルに関連して特定することを特徴とする請求項１記載の方法。
【請求項３】
前記複数の受信したパケットは、受信器が伝送エラーなしで以前に受信したパケットを表すことを特徴とする請求項２記載の方法。
【請求項４】
各パケットは、それぞれパケットヘッダーを有し、前記パケットヘッダーは、前記パケットのそれぞれのパケットヒストリー状態を特定する少なくとも１つのヒストリーベクトルを含むことを特徴とする請求項２記載の方法。
【請求項５】
前記受領確認ベクトルは、最後に受領した特定の受領パケットのシーケンス番号を含むことを特徴とする請求項３記載の方法。
【請求項６】
通信チャネルを介して送信側と受信側との間で通信ストリームを送信する方法において、
（Ａ）通信ストリームを複数のパケットに分割するステップ、
（Ｂ）前記パケットの特定のパケットに対するそれぞれのパケットヒストリー状態を第１の受領確認ベクトルに関連して特定するステップであって、前記第１受領確認ベクトルは受信側から送られて送信側が受領する、ステップ、
（Ｃ）前記パケットの内、特定のパケットはそれに関連するそれぞれのパケットヒストリーに関連して符号化するステップであって、前記各パケットは、それに関連するパケットヘッダーを有し、前記パケットヘッダーは、パケットのそれぞれのパケットヒストリー状態を特定する少なくともヒストリーベクトルを含んでいる、ステップ
（Ｄ）複数のパケットを圧縮データストリームに圧縮するステップ、及び
（Ｅ）通信チャネルを介してこの圧縮データストリームを送信側から受信側に送信するステップ
からなる方法。
【請求項７】
圧縮されたデータストリームからデータを再生する方法において、
（Ａ）圧縮されたデータストリームを受領するステップであって、前記圧縮されたデータストリームは、複数の符号化パケットを含んでいる、ステップ、
（Ｂ）符号化パケットの内の特定のパケットに関連するそれぞれのパケットヒストリー状態を特定するステップ、及び
（Ｃ）データを再生するために前記圧縮されたデータストリームを脱圧縮するステップであって、前記符号化パケットの内の特定のパケットは、前記それぞれのパケットヒストリーに関連して脱圧縮される、ステップ
からなる方法。
【請求項８】
データ通信装置であって、
送信用に、複数のパケットを有するデータストリームを受領する受信器、
前記パケットに関連する複数のパケットヒストリー状態を、少なくとも１つの受領確認ベクトルに関連して特定し、前記複数のパケットを複数のヒストリー状態に関連して符号化する符号化器、及び
前記パケットを圧縮データストリームに圧縮する圧縮器
から成るデータ通信装置。
【請求項９】
圧縮デジタル信号を処理するための装置において、デジタルデータの入力ストリームを複数のパケットに分割し、特定のいくつかのパケット対するそれぞれのパケットヒストリー状態を少なくとも１つの受領確認ベクトルに関連して識別し、該特定のいくつかのパケットをそれに関連したそれぞれのパケットヒストリーに関連して符号化し、各パケットがそれに関連するパケットヘッダーを有し、該パケットヘッダーが該パケットのそれぞれのヒストリー状態を識別する少なくとも１つのヒストリーベクトルを含み、符号化されたパケットを圧縮デジタル信号に圧縮し、および該圧縮デジタル信号を通信チャネルに適用することによって、該圧縮デジタル信号が生成される装置であって、該装置が、
該通信チャネルからの該圧縮デジタル信号を受信するための受信器、及び
受信された該圧縮デジタル信号を脱圧縮し、脱圧縮された該デジタル信号からの該デジタルデータの入力ストリームを再生する脱圧縮器
からなる装置。
【請求項１０】
複数のインストラクションを記憶した機械読み取り可能記録媒体であって、該複数のインストラクションが、機械によって実行されるときに、送信側と受信側との間で通信チャネルを介して、
該通信ストリームを複数のパケットに分割し、特定のいくつかのパケット対するそれぞれのパケットヒストリー状態を少なくとも第１の受領確認ベクトルに関連して識別し、該第１の受領ベクトルが該送信側によって該受信側から受信され、該特定のいくつかのパケットをそれに関連したそれぞれのパケットヒストリーに関連して符号化し、各パケットがそれに関連するパケットヘッダーを有し、該パケットヘッダーが該パケットのそれぞれのヒストリー状態を識別する少なくとも１つのヒストリーベクトルを含み、該複数のパケットを圧縮データストリームに圧縮し、該通信チャネルを介して、該送信側から該受信側へ該圧縮データストリームを送信する
ことによって通信ストリームを送信する方法を該機械に実行させる
機械読み取り可能記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、データ圧縮に関し、特にパケットネットワーク内で行われるデータ圧縮を改善する方法に関する。
【０００２】
【従来の技術】
従来のデータ圧縮技術とそのシステムは、デジタルデータのストリームをこの圧縮符号ストリームに符号化して、この圧縮符号ストリームを対応する元のデータストリームに復号化（脱圧縮）している。この符号ストリームは、「圧縮された」と称するが、その理由は通常ストリームは元のデータストリーム内に含まれるシンボルよりも少ない数の符号から成り立っているからである。このような符号の数が少なくなることにより、データをより少量のメモリ内に記憶することが出来る。更に圧縮された符号ストリームは、通信システム内で、例えば有線通信システム、無線通信システム、或いは光ファイバ通信システム内で圧縮されない状態の元のデータよりもより短時間で送信することが出来る。今日の通信ネットワークにおいてデータ伝送と記憶容量の向上に対する需要は常に高まっている。斯くして、データ圧縮は、現代の伝送プロトコル及び通信ネットワークにおいて重要な役目を果たす。
【０００３】
従来公知のように、データを圧縮するのには２種類の方法があり、所謂特殊目的圧縮と汎用目的圧縮である。特殊目的の圧縮技術は、特殊な形式のデータを圧縮し実現するのは比較的安上がりである。例えば、特殊目的の圧縮技術はラン−レングス符号化、０−抑制符号化、ヌル−圧縮符号化、パターン置換符号化を含む。これらの技術は圧縮比率が低いが、通常の特性及び冗長性を有するデータを圧縮するからである。圧縮比率は、圧縮された符号の長さ対元のデータの長さの比である。しかし、特殊目的の圧縮技術は、より一般的な特性を有するデータ（即ち、共通の特性を高いレベルで所有することのないデータ）を圧縮するのには効率的でなくなる傾向がある。
【０００４】
これに対し汎用目的の圧縮技術は、あるタイプのデータを特別に圧縮するよう設計されたものではなく、種々雑多なタイプのデータを圧縮するのに適している。最も広く知られ有効な汎用目的の圧縮技術は、J.ZivとA.Lempelの開発したアルゴリズム群から得られたものである。これを通常「ランペル−ジブ（Ｌｅｍｐｅｌ−Ｚｉｖ）符号化」と称する。特にZiv et al.著の「“A Universal Algorithm for Sequential Data CompressionM”，IEEE Transactions on Information Theory，IT−23（3）：337−343，May 19977（describing the comonly denominated“LZl”algorithm）」（通常ＬＺ１アルゴリズムと称する）とZiv et al.著の「“Compression of Individual  Sequences Via Variable−Rate Coding”，“IEEE Transactions on Information Technology，IT−24（5）：530−536，September 1978（describing the commonly denominated“LZ2”algorithm）」（ＬＺ２アルゴリズムと称する）を参照のこと。ＬＺ１とＬＺ２のデータ圧縮技術は、従来公知であるのでその詳細な説明は割愛する。
【０００５】
しかし簡単に説明すると、ＬＺ１（ＬＺ７７とも称する）データ圧縮プロセスは、前に現れたシーケンス（即ち、マッチングシーケンス）を参照して文字の繰り返しシーケンスを置換するという原理に基づいている。基準（reference;例えばポインター）は、以前に発生した位置の表示（繰り返しシーケンスの開始点からオフセット（ずれた）されたバイトと繰り返されるキャラクターの長さ、すなわちマッチした長さ）で表される。通常基準は、従来のＬＺ１符号化によれば、＜offset  length＞ペアとして表される。これに対しＬＺ２（ＬＺ７８とも称する）の圧縮は、入力データキャラクターのストリームを、自動的に成長するルックアップテーブル、あるいは圧縮プロセスの間生成される字引に基づいて符号化値に解析している。すなわちＬＺ２は、任意のバイト境界及びＬＺ１符号化内の長さでもってマッチングを見いだすことはなく、字引のワードがソースストリングにマッチングしたときには、新たなワードが字引に追加される。そしてこの字引は後続のソースストリングバイトとマッチングしたワードを加えたものから成り立っている。ＬＺ２符号化によれば、マッチングはポインターとして、あるいは字引内のワードに対するインデックスとして符号化される。
【０００６】
前述したようにＬＺ１アルゴリズムとＬＺ２アルゴリズムにより具体化された基本原理に基づいて派生した沢山の圧縮系が存在する。例えば、ＴｅｒｒｙＡ．Ｗｅｌｃｈ（T.A.Welch,“A.Technique for High Performance Data Compression”,IEEE Computer,pp.8-19,June 1984,and U.S.Patent No.4,558,302,issued to welch on December 10,1985,each of which is incorporated by reference for all purposes）は、ＬＺ２符号化プロセスを公知のLempel-Ziv-Welch（ＬＺＷ）圧縮プロセスとしてまとめ上げた。ＬＺ２圧縮技術とＬＺＷ圧縮技術の両方は、入力キャラクターのストリングを固定長さの符号にマッピングするような、いわゆるストリングテーブルの生成及び使用に基づいている。具体的に説明すると、これらの圧縮技術は、データキャラクターのストリームを圧縮ストリームに圧縮するために、キャラクターストリームを直列的にサーチし、テーブル内、すなわち字引内に以前に記憶された対応する最長の可能性のあるストリングにマッチするたシンボルのシーケンスに基づいて符号を生成することによりデータキャラクターのストリームを圧縮している。  マッチングが行われ符号シンボルが生成されると、この圧縮プロセスはデータストリーム内のマッチングしたシーケンスとデータストリーム内の次のキャラクターシンボル遭遇を加えたものを含む字引内の新たなストリングエントリーを記憶する。
【０００７】
前述したようにLempel-Ziv符号化の本質は、元のデータストリーム内、例えば送信すべきドキュメント内で繰り返されるストリングとサブストリングを見いだすことである。圧縮された状態のドキュメント中に繰り返されるフレーズは、ポインターでもってそれらが元のデータストリーム、例えばドキュメント中に以前に発生した場所に置換される。斯くして復号化データ、例えばこのようにして圧縮されたテキストは、ポインターが指摘した、すでに復号化されたテキストでもってポインターを置換することが必要となる。従来公知のようにLempel-Ziv符号化技術を採用する際に考慮すべき重要な点は、ポインターがどこまで後ろにさかのぼるかに対する制限を設定すべきか否かを決定すること、及びこの制限はどんなものであるかを決定することである。Lempel-Ziv符号化でさらに設計的に考慮すべき事項は、所望の制限内にどのサブストリングがポインターの目標となり得るかである。即ち、ポインターが前のテキストに到達することが制限されていない場合、所謂、ウィンドウを成長させるか、あるいは前のＮ個のキャラクターから成る固定サイズのウィンドウに制限されるかである。ここでＮは数千キャラクター、例えば３キロバイトの範囲内にある。この符号化によれば、ストリングの繰り返しが発見されると、それらの両方がウィンドウ内に現れる場合にのみ圧縮される。Lempel-Ziv符号化設計に関し、なされた考慮すべき事項は、速度とメモリーの大きさとその圧縮比率の間の妥協点を見いだすことである。
【０００８】
圧縮はネットワークの効率を改善するためには考慮すべき点である。例えば、利用可能な計算資源、即ちデータ処理要件が利用可能なネットワークの帯域幅に比較して大きい場合には、ネットワークにデータパケットを伝送する前にデータパケットを圧縮するのが好ましい。当然のことながら実際に採用する圧縮系は速度と全体的な圧縮効率の関係から注意深く選択しなければならない。即ち、遅い圧縮系は、ネットワークの性能を低下させ、非効率な圧縮系は潜在的な伝送利得を制限してしまう。
【０００９】
さらに複雑なネットワーク効率の問題は、多くのパケットネットワークが本来的に信頼性を有しないということである。即ち、現在知られているパケットネットワーク、例えばインターネットは、ネットワーク内を伝送されるパケットを日常的にドロップしたり、あるいは再度順序付けているが、これによりデータ伝送にエラーが発生する。例えば、ある圧縮系がパケット間のある種の相互依存性を導入し、そしてその後ネットワークがこのパケットをドロップしたり、再度要求するような場合そして受信器で前のパケットが失われている場合には、パケット間の相互依存性により、特定のパケットを脱圧縮することはできない（元に戻すことはできない）。斯くして、ある種のアプローチがこのような問題を解決するために採用されている。（１）ネットワークの信頼性の改善。これによりインターネットにおいては、より信頼性のある端末間のトランスポート層のサービス、例えば公知のトランスミッション制御プロトコル（Transmission Control Protocol； ＴＣＰ）が適用されてトランスポートレベルでパケットを圧縮する。（２）無状態（ステイトレス）圧縮を採用する。これは、各パケットは独立に圧縮され、これにより各パケットが受信器で脱圧縮される。（３）ストリーミング（Streaming）圧縮は信頼性が広く行き渡っていることを仮定し、この仮定が破られた時にはリセットメカニズムを採用する。具体的に説明すると、パケットが失われたときには受信器は圧縮がリセットされるまで後続の各パケットを廃棄する。リセットの後はそれ以降のパケットは前のパケットには依存せず、脱圧縮は通常の形態で再開される。これら２つの公知のストリーミングタイプの圧縮技術は、Point−to−Point  Protocol（ＰＰＰ）圧縮制御プロトコルとUse  Datagram  Protocol（ＵＤＰ）パケットに対し採用されるＩＰヘッダー圧縮プロトコルを有する。
【００１０】
上に説明したパケット圧縮系は、パケットの相互依存性から発生する問題を解決するのには有効であるが、このような圧縮系はまた別の問題を発生させる。例えば、トランスポートレベルでのパケットの圧縮は端末間の利用を必要とし、通常、伝送中にアプリケーションによるあるレベルの共同作業を必要とする。同様にステイトレスの圧縮は、ある種の頑強さを提供するが、ステイトレスの圧縮のパケットの独立性の特性により、実際の圧縮比率が下がるが、これはこのような圧縮が１個のパケット内のデータを検査するからである。斯くして、例えば、この圧縮アプローチは隣接するパケットのネットワークヘッダー内に通常見いだされる大量の冗長性を除去することができない。さらにまた、ストリーミング圧縮はより大きな圧縮技術を与えることができるが、これらの圧縮系はパケットがネットワーク内で喪失した場合には、パケットの喪失の影響を大幅に増やし、これにより受信器が他の数個のパケットを受領できないことになる。信頼性が低いネットワーク、例えばインターネットにおいてはこのパケットの大きな影響は、ストリーミング圧縮を採用する利便性を低下させることになる。
【００１１】
【発明が解決しようとする課題】
本発明の目的は、従来の圧縮系の欠点を有さず、頑強性を増し、圧縮比率を増加させるような圧縮技術を提供することである。本発明の目的は、従来の圧縮系の欠点、例えばパケットの喪失による悪影響の拡大を有さず、頑強性を増し、圧縮比率を増加させるような圧縮方法と装置を提供することである。
【００１２】
【課題を解決するための手段】
本発明の態様によれば、所謂、受領確認ベクトル（acknowledgement vector）に関連して決定された選択ヒストリー状態（select history state）が採用される。本発明の一態様によれば、この受領確認ベクトルは通信チャネルを介し従来どうり転送する際、成功裏に受領したパケットの識別子に関する情報を含む。即ちパケットヒストリー状態はそれぞれのパケットの選択ヒストリー状態である。通信チャネルの第１端（例、送信器側）には、第２端（例、受信器）が成功裏に受信したパケットに関連するある種の情報が与えられ、それを認識している。脱圧縮器には選択ヒストリーが与えられ、それを認識し、これにより送信器側から送信された圧縮パケットを効率的に脱圧縮する（伸張する、戻す）。即ち脱圧縮は、このようなパケットを圧縮する間のヒストリーすなわち選択ヒストリー状態として用いられたパケットに関連して（基づいて）行われる。斯くして本発明の選択ヒストリー状態と受領確認の観点により圧縮器と脱圧縮器（通信チャネルの何れかの側にある）は、共同して機能して通信チャネルで行われた圧縮を改善している。
【００１３】
本発明の一実施例によれパケットは符号化され、少なくともヒストリーベクトルを含むヘッダーが付与される。このヒストリー状態は、パケットのそれぞれのヒストリー状態を特定している。さらにまた、本発明の一態様によれば受領確認ベクトルが構築され、送信器側に送られて、これにより送信器側の特定の圧縮アルゴリズムが成功裏に受領したパケットに対する圧縮アルゴリズムにより使用されたヒストリーを制限することができる。斯くして、本発明の一態様によれば、ヒストリーとして用いたパケットを特定するベクターが圧縮されたパケット内に含まれて、これにより受信器がパケットを脱圧縮するのに必要なパケットヒストリー状態を再構築する。
【００１４】
本発明の一態様によれば、頑強さ及び圧縮比率の向上は様々な圧縮方法、あるいは通信チャネルの装置で達成することができる。即ち、本発明の原理は特定の種類の圧縮系によらず、そのため本発明の様々な態様を採用することにより圧縮技法及び通信チャネル技法で本発明の利点は実現できる。
【００１５】
【発明の実施の形態】
本発明は様々な装置及び方法で実現することができる。本発明はフロッピーディスク、ＣＤ−ＲＯＭ、ハードドライブあるは他の機械が読み取り可能な記憶媒体等で具体化されるプログラムコードの形態で実現できる。また、プログラムコードはコンピュータ内に組み込み実行できる場合には、このようなコンピュータは本発明を実行するための装置である。本発明はまた、記憶媒体中のプログラムコードの形態でも実現でき、記憶媒体中でそして機械により搭載、及び機械により実行され伝送媒体を通して送信されるようなプログラムコード の形態で実現できる。プログラムコードがコンピュータのような機械で実現できる場合には、このような機械は本発明の装置となる。汎用プロセッサーで本発明が実現される場合にはプログラムコードは、プロセッサーとプログラム構造のセグメントはプロセッサと組み合わされて特定の論理回路を実行するような装置を提供できる。
【００１６】
図１はデータを脱圧縮したりするシステム１００のブロック図である。このシステム１００は特に伝送媒体、例えば有線、無線あるいは光ファイバーを介して情報を送受信するのに有効である。さらにまた、システム１００はコンピュータディスクドライブのような磁気記録媒体、あるいはＣＤ−ＲＯＭのような光学的に読み取り可能な媒体から情報を読み出したり、そこに情報を記録するのに有効である。斯くして、磁気ディスクドライブのような磁気媒体、ＣＤ−ＲＯＭのような光学読み取り可能な媒体を含む記録媒体に本発明により圧縮されたデータを記録することができる。図１において入力データストリーム１０５、例えばテキストがデータ符号化器１１０に与えられる。データ符号化器１１０は本発明によれば可変のヒストリー状態パケット間圧縮を適応して入力データストリームをあらかじめ処理し符号化する。符号化プロセスにおける本発明の様々な態様は、図２を参照して以下詳述する。
【００１７】
図１のシステム１００において、本発明により生成された符号化入力データストリーム１１５が圧縮器１２０に与えられる。この圧縮器１２０は本発明により圧縮技法例えばLempel-Ziv圧縮を適応して符号化入力データストリーム１１５を圧縮して圧縮データ１２５を形成する。前述したようにLempel-Ziv形の圧縮は本発明により符号化入力データストリーム１１５を圧縮する際有効に用いられる。圧縮データ１２５はその後チャネル符号化器１３０により符号化され、チャネル符号化情報１３５を生成する。チャネル符号化技術が情報を圧縮した情報に加えられ、データ読み取りプロセスにおいてエラー検出及び／または訂正が可能となる。従来のチャネル符号化技術は、公知のリードソロモン符号化技術を含み、これにより１ビットあるいは複数のビットにより表されるシンボルのシーケンスを符号化する。これらのシンボルはその後、変調符号化器１４０により変調符号化され変調されたデータストリーム１４５を生成し、この変調されたデータストリーム１４５がチャネル／媒体１５０上に記録されるか、あるいは通信チャネルを介して送信されるチャネルシーケンスを規定する。
【００１８】
データストリームの伝送あるいは記録プロセスの間、ノイズと干渉がチャネル／媒体１５０内に時に導入されることがある。斯くして、変調復号化器１５５とチャネル復号化器１６０はノイズを含んだ変調されたデータストリーム１４５を受領し、そして公知の方法でそれぞれチャネル符号化器１３０と変調符号化器１４０の符号化処理の逆を行う。チャネル復号化器１６０からのデータストリームは圧縮器１２０により生成された圧縮データ１２５に対応する。その後、このデータストリームを本発明により脱圧縮器１６５で脱圧縮され、データ復号化器１７０で復合化されて図４で詳述するように出力データストリーム１７５を生成する。
【００１９】
本発明の様々な態様は、圧縮の頑強性及び圧縮技術の改善を実現するのに向けられる。図２は図１のシステムで用いられ、本発明によりデータを圧縮する動作２００のフローチャートを示す。具体的に説明すると、入力データストリームを受領し、そして成功裏に受領したパケットが検査される（図２ブロック２１０）。本発明によればこの成功裏に受領したパケットを検査することにより、パケットのヒストリー状態の特定が受領確認ベクトルに関連して可能となる（ブロック２２０）。本発明の一実施例によればパケットのヒストリー状態は、現在のパケットの圧縮が決定される元となったパケットの前の組である。例えば、Lempel-Ziv７７においては、圧縮ヒストリー状態はこのLempel-Ziv圧縮で採用された、所謂、字引との直接相関である。興味深いことにネットワークパケットのステイトレス圧縮と、ストリーミング圧縮との間の大きな違いは、各形が採用する特定のヒストリー状態である。即ち、ステイトレス圧縮はヒストリー状態を採用せず、一方ストリーミング圧縮によれば前のパケットをヒストリーとして採用する。このような差は、本発明の原理でも依然として存在する。
【００２０】
さらに具体的に説明すると、本発明の一実施例によれば、パケットヒストリー状態は受信器側により通信チャネルを介して成功裏に受領した特定のパケットに関連する選択ヒストリー状態である。そしてこの受信器側には、送信され圧縮されたパケットを効率的に脱圧縮することができるような選択ヒストリーが与えられ、通知される。好ましいことに本発明によれば、選択されたパケット間ヒストリー状態を用いることにより、本来的にパケットの喪失の被害を受ける従来のストリーミング圧縮系に対し、圧縮の頑強性及び圧縮比率の改善を図ることができる。
【００２１】
前述したように選択パケットヒストリー状態を特定した後、このヒストリー状態を採用して送信側から送信するために待機しているパケットに対し、ある種の情報を符号化する。具体的に説明すると本発明によれば、個々のパケットはそれに関連するそれぞれのパケットヒストリー状態に関連して符号化される（ブロック２３０）。本発明によれば各パケットにはヘッダーが付与され、このヘッダーは例えばパケットに関連したそれぞれのパケットヒストリーを特定するヒストリーベクトルを含む。図２を参照すると３００が図２の操作に従って圧縮された状態を示す。図３の実施例においては、パケットヘッダーはシーケンス番号及び受領確認ベクトルのような付属のアイテムを含む。即ち、本発明によれば前述した受領確認ベクトルはパケットヘッダーの一部として送信される。受領確認ベクトルが符号化パケットとは別個に送信されたか、あるいはパケットヘッダーの一部として送信されたかの決定は、本発明の適応にあたっては、設計的選択事項である。例えば、受領確認ベクトルはいわゆるpiggybacking技術を用いて送信者側に送信することができる。そしてこのpiggybacking技術は受信器から送信器側への反対方向内のデータストリームが存在する。
【００２２】
例えば３００は一連のパケットを含む（例、図３ではパケット１からパケットＮはパケット３０５−３１１として示されている）。さらにまた各パケットはヘッダーを含む（例、Ｈ１からＨｎはヘッダー３２０−３３０として示されている）。さらにまた、ヘッダー１  ３２０はシーケンス番号３３５とヒストリーベクトル３４０と受領確認ベクトルを含む。
【００２３】
本発明の一実施例によれば、シーケンス番号、例えばシーケンス番号３３５は送信器側と受信器側の両方で用いられ、本発明により圧縮されたパケットを特定する。シーケンス番号を符号化するのに必要とされるビットの数は、ネットワーク全体を移動するのに必要な最大時間の間、所謂「ラッピング；wrapping」される悪影響を回避するのに十分な程度に必要である。例えば、シーケンス番号３３５は２４ビットの長さで示されている。
【００２４】
さらにまた本発明の一実施例においては、ヒストリーベクトル、例えばヒストリーベクトル３４０は圧縮するのに用いられた前のパケットの組、即ち選択ヒストリー状態を記述する。ヒストリーを決定するために受領確認パケットを利用する本発明の実施例においては、パケットが送信される時間とパケットがヒストリーとして用いられる時間との間のネットワークの往復時間に関連する時間遅延が発生する。斯くして、本発明の一実施例によれば、ヒストリーベクトルはオフセットとビットマスクを用いて符号化され、その結果オフセットはパケットのシーケンス番号から減算されて、最も最後のヒストリーパケットのシーケンス番号を確立する。ビットマスクは最後のヒストリーパケットの直前の付加的なヒストリーパケットを特定する。具体的に説明すると、ヘッダー１  ３２０においては、ヒストリーベクトル３４０は８ビットのオフセットと８ビットのマスクとを含み、これによりヒストリー状態を最後の２６３内の最大９個の連続パケットに制限する。
【００２５】
前述したように図３のパケットヘッダーは、最後の方で受信したパケットの組を記述する受領確認ベクトル、例えば受領確認ベクトルを含む形で具体化されている。この受領確認ベクトルは、最後に受領したパケットのシーケンス番号と、その直前のパケットの状態を記述するビットマスクを少なくとも含む。例えば受領確認ベクトルは３２ビットの長さで、シーケンス番号に対しては２４ビットをカバーし、関連マスクに対しては８ビットをカバーする。
【００２６】
図２に戻ってパケットを本発明により、それぞれパケットヒストリー状態に関連して符号化した後（ブロック２３０）、これらのパケットはその後圧縮される。前述したように本発明の利点は、様々な既存の圧縮技術と共に適応可能な点である点である。例えば、以下に詳述するように本発明は基地のデフレート（Deflate）圧縮系、あるいはＬＺ７７圧縮に適用されるパケットストリームの圧縮技術を改善する。選択的な圧縮系を符号化パケットに適用した後（ブロック２４０）、この圧縮されたパケットは送信用に待機する（ブロック２５０）。
【００２７】
本発明の一態様によれば、ネットワーク内を伝送するパケットに関連して選択ヒストリー状態を採用することにより、洗練された圧縮ツールが達成できる。即ち、本発明によれば各パケットに関連するパケットヒストリー状態が送信器側で選択ヒストリー状態であり、この送信器側に受信器側が成功裏に受領したパケットに関連するある種の情報を与え通知される。そして、受信器側にはこのパケットに関連する選択ヒストリー状態が与えられ通知され、これにより送信器側から送信された圧縮パケットの効率的な脱圧縮が可能となる。斯くして本発明の選択ヒストリー状態と受領確認の技術により送信器側と受信器側は共同して通信チャネルにおける圧縮を改善する。
【００２８】
具体的に説明すると本発明によれば、受領確認ベクトルを特定の圧縮アルゴリズムと共に用いて送信器側が正確に受領したパケットに対し、圧縮アルゴリズムで用いたヒストリーを定める。斯くして本発明の一実施例によればヒストリーとして用いられたパケットを特定するベクトルが圧縮されたパケットに含まれ、これにより受信器は、パケットを脱圧縮するのに必要なパケットヒストリー状態を再構築する。さらに本発明によれば、受領確認ベクトルは、圧縮されたパケットとは別に送信される。更に又、実施例では単一の通信チャネル構成について議論しているが、本発明は複数の通信チャネル構成についても等しく適用可能である。さらに本発明の態様によれば、選択ヒストリー状態を用いることにより圧縮の頑強性及び圧縮比率を従来のストリーミング圧縮系（パケット喪失の場合に妥協せざるを得ない従来のストリーミング）よりも改善する。
【００２９】
本発明の圧縮テスト結果を記述する前に本発明の脱圧縮について説明する。図４は、本発明によりデータを脱圧縮する操作４００のフローチャートである。受信したパケットの圧縮ストリームから（ブロック４１０）ヒストリーベクトルをパケット毎のベースで抽出する（ブロック４２０）。例えば、以下のプログラム（一部擬似符号を含む）が本発明の一実施例によりこれらのアイテムの抽出を記述する。
―――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――パケットからシーケンス番号を抽出する。
ヒストリーベクトルのオフセットとマスクを抽出する。
オフセットが０の場合には、ヒストリーは存在しない。
それ以外の場合｛「シーケンス番号からオフセットを抽出してヒストリーの第１パケットを与える。」マスク！＝０｛シーケンス番号から１を減算する。
低ビットがマスク内に設定された場合には、パケットをヒストリーに追加する。
マスクを最も右の１ビットにシフトする。  ｝｝パケットを脱圧縮する。
受領確認ベクトルと最後に受信したパケットのシーケンス番号とビットマスクを抽出する。
――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――――上記のプログラム（一部擬似符号を含む）を用いて本発明を実行するＣプログラム言語でコンピュータをプログラムすることが出来る。ヒストリーベクトルの抽出から脱圧縮状態のパケットのヒストリー状態が特定される（ブロック４３０）。さらに本発明によれば、抽出は受領確認ベクトルとパケットヘッダーからのシーケンス番号の抽出を含む。現行パケットの脱圧縮は、特定されたヒストリー状態に関連して行われる（ブロック４４０）。その結果現在の未圧縮パケットがそれぞれの脱圧縮器、例えば特定の通信チャネルの受信器側にある脱圧縮器の現在受領したパケット状態に追加される（ブロック４５０）。これにより受信したパケットの組を更新する。最後に現行パケットを脱圧縮した後、受領確認ベクトルが構築され、送信者側に送信して戻される（ブロック４６０）。前述したように受領確認ベクトルは、最後に受領したパケットの組を記述し、送信器側がそれを用いて選択ヒストリー状態と共に今後のパケットを圧縮する。
【００３０】
本発明は、従来公知の２つの圧縮フォーマットを用いるある種の圧縮シミュレーションでも適用可能である。具体的に説明すると、Deflate圧縮フォーマットは、データパケットの所定のシーケンスと共に用いられた。Deflateは、gzip、zip、pmgのような公知のファイルフォーマットの基礎となる一般的な圧縮フォーマットである。Deflateは、ＬＺ７７とハフマン符号化技術とを組み合わせ、ネットワークプロトコル内ではＰＰＰと共に使用される。上記のフォーマットは、http:www.cdrom.com/pub/infozip/zlibでインターネットを介して入手可能である。DeflateのZlibの実行は、６個のデフォルタ値に設定された圧縮レベルと共に用いられる。
【００３１】
具体的に説明すると、公知のCalgary Corpus（a widely used standard reference for evauating the effectiveness of compression algorithms；圧縮アルゴリズムの有効性を評価する広く用いられている標準基準）からの１４個の通常使用されているファイル（これに関してはT.C.Bell et al.著の「Modeling for text compression,Computing Surveys 21(4）:557-591,December 1989」を参照のこと）を用いて圧縮用の入力データストリームを特定した。バイトシーケンスがアルファベットの順番で１４個のCalgary Corpusファイルを連続させることにより形成され、１６００バイトのパケットと１２５バイトのパケットから成る固定サイズのパケットに入力ストリームを分割した。本発明は、通信チャネルを伝送させるパケットの受領確認を含む。本発明の圧縮シミュレーションの例とモデルと圧縮器に到達した様々な受領確認の中の圧縮器に到達した受領確認、即ちパケットが遅延する。
【００３２】
ここに示した実施例は、１６００バイトと１２５バイトのパケットサイズに対し、入力バイトに対する出力バイトの数に対する遅延の影響の比較を示す。特に図５は、公知のstateless圧縮系（５２０）と公知のstreaming圧縮系（５３０）と本発明による圧縮（受領確認圧縮 ；acknowledged compression ;Ackと称する）の間を比較するためにそれぞれのパケットサイズに対するシミュレーションの結果である５００と５１０を示す。Ａｃｋ結果５４０と、シミュレーション結果５００と５１０から判るように、Ａｃｋ結果５４０はstateless圧縮の結果５２０よりもより大きな圧縮を示すが、streaming圧縮の結果５３０程ではない。streaming圧縮の結果５３０は、このような圧縮に本来的に付随するパッケット喪失の影響を考慮に入れていない。これに対し本発明のＡｃｋ結果５４０は、このようなパケット喪失による影響を受けない。
【００３３】
図に示したブロックは、本発明を実現する回路の概念を表すものである。フローチャート、フローダイヤグラム、状態遷移図、仮コード、プログラムコード等は、コンピュータで読み込み可能な媒体の中で行われる様々なプロセスを表し、そしてコンピュータ、マシンプロセッサーにより実行されるが、このようなコンピュータ、マシンプロセッサーは図には明確には示していない。
【００３４】
特許請求の範囲に発明の構成要件の後の括弧内の符号が記載されている場合は、構成要件と実施例と対応づけて発明を容易に理解させる為であり、特許請求の範囲の解釈に用いるべきのものではない。
【図面の簡単な説明】
【図１】データを圧縮したり、脱圧縮したりするシステムのブロック図。
【図２】図１のシステムで使用される本発明によるデータを圧縮する操作を表すフローチャート図。
【図３】図２の動作に従って圧縮されたパケットストリームを表す図。
【図４】図１のシステムで使用される本発明によるデータを脱圧縮する操作を表すフローチャート図。
【図５】従来の圧縮系と本発明の圧縮系との間の比較を行うために様々な大きさのパケットに対する圧縮結果を表す図。
【符号の説明】
１００  システム
１０５  入力データストリーム
１１０  データ符号化器
１１５  符号化入力データストリーム
１２０  圧縮器
１２５  圧縮データ
１３０  チャネル符号化器
１３５  チャネル符号化情報
１４０  変調符号化器
１４５  変調されたデータストリーム
１５０  チャネル／媒体
１５５  変調復号化器
１６０  チャネル復号化器
１６５  脱圧縮器
１７０  データ復号化器
１７５  出力データストリーム
２１０  受領パケットを検査する
２２０  受領確認ベクトルの関数としてパケットヒストリー状態を特定する
２３０  個々のパケットヒストリー状態の関数として符号化する
２４０  符号化パケットを圧縮する
２５０  圧縮されたパケットを送信する
３０５  パケット１
３２０  ヘッダー１
３２５  ヘッダー２
３１０  パッケト２
３３０  ヘッダーＮ
３１５  パッケトＮ
３３５  シーケンス番号
３４０  ヒストリーベクトル
３４５  受領確認ベクトル
４１０  圧縮されたパケットを受領する
４２０  パケット毎にヒストリーベクトルを抽出する
４３０  ヒストリー状態を特定する
４４０  現パケットをヒストリー状態の関数として脱圧縮する
４５０  圧縮していない現パケットを受領したパッケト状態に追加する
４６０  受領確認ベクトルを構築し送信する
【図１】
0003875502.tif 000002
【図２】
0003875502.tif 000003
【図３】
0003875502.tif 000004
【図４】
0003875502.tif 000005
【図５】
0003875502.tif 000006