(57)【特許請求の範囲】
【請求項１】
通信装置に対して送信されるメッセージを生成する方法であって、
前記通信装置に対して送信されるべきメッセージのヘッダにて示されるべき情報項目を特定する特定ステップと、
前記特定ステップにより特定されたヘッダにて示されるべき複数の情報項目のそれぞれが、ヘッダの情報項目とインデックスとを対応付けたインデックステーブルに登録済みであるか、前記インデックステーブルに登録されていないかを判定する判定ステップと、
前記特定ステップにより特定されたヘッダにて示されるべき複数の情報項目のうち、前記インデックステーブルに登録済みであると前記判定ステップにより判定された情報項目に対応するインデックスと、前記インデックステーブルに登録されていないと前記判定ステップにより判定された情報項目とをそれぞれ表す符号を含むメッセージであって、前記特定ステップにより特定されたヘッダにて示されるべき複数の情報項目のうち、前記インデックステーブルに登録されていないと前記判定ステップにより判定された情報項目をインデックステーブルに登録すべきか否かを規定するビットパターンを含むメッセージを生成する生成ステップと、
を備えることを特徴とする生成方法。
【請求項２】
前記インデックステーブルに登録済みであると前記判定ステップにより判定された情報項目に対応するインデックスを符号化する符号化ステップと、
前記インデックステーブルに未登録であると前記判定ステップにより判定された情報項目を圧縮する圧縮ステップとを備え、
前記生成ステップは、前記符号化ステップによる符号化結果と、前記圧縮ステップによる圧縮結果を含むメッセージを生成することを特徴とする請求項１に記載の生成方法。
【請求項３】
前記インデックステーブルに未登録であると前記判定ステップにより判定された情報項目の少なくとも１つは、前記インデックステーブルに登録済みであると前記判定ステップにより判定された情報項目を参照することで符号化されることを特徴とする請求項２に記載の生成方法。
【請求項４】
前記インデックステーブルに登録されていないと前記判定ステップにより判定された情報項目のリテラル値は、前記インデックステーブルに登録済みであると前記判定ステップにより判定された情報項目との差分に基づいて符号化されることを特徴とする請求項１乃至３のうち、いずれか１項に記載の生成方法。
【請求項５】
前記メッセージは、前記インデックステーブルに登録されていないと前記判定ステップにより判定された情報項目のリテラル値に加えて、当該情報項目が前記インデックステーブルに登録済みの情報項目を参照することで符号化されるか否かを規定するフラグをさらに含むことを特徴とする請求項１乃至４のうち、いずれか１項に記載の生成方法。
【請求項６】
前記ビットパターンは、前記インデックステーブルに登録されていないと判定された情報項目が、既にインデックステーブルに登録済みの他の項目の置き換えにより前記インデックステーブルに追加されなければならないかを規定するためのビットを含むことを特徴とする請求項１乃至５のうち、いずれか１項に記載の生成方法。
【請求項７】
前記メッセージはＨＴＴＰメッセージであり、前記ヘッダはＨＴＴＰヘッダであることを特徴とする請求項１乃至６のうちいずれか１項に記載の生成方法。
【請求項８】
ＨＴＴＰヘッダは、少なくともＨＴＴＰ名及びＨＴＴＰ値から構成され、前記インデックステーブルに登録済みであると判定された情報項目のインデックス化ＨＴＴＰヘッダは、ＨＴＴＰ名をインデックス化するインデックス及びリテラルＨＴＴＰ値を含むことを特徴とする請求項７に記載の生成方法。
【請求項９】
ＨＴＴＰヘッダは、少なくともＨＴＴＰ名及びＨＴＴＰ値から構成され、前記方法は、インデックスレベルフラグをＨＴＴＰヘッダと関連付ける関連付けステップを有し、前記インデックスレベルフラグが、前記ＨＴＴＰヘッダに依存して、前記ＨＴＴＰヘッダが前記インデックステーブルにおける対応する情報項目と同一のＨＴＴＰ名及びＨＴＴＰ値を有することを示す第１のインデックス化状態、又は前記ＨＴＴＰヘッダが前記インデックステーブルにおける前記対応する情報項目と同一のＨＴＴＰ名であるが異なるＨＴＴＰ値を有することを示す第２のインデックス化状態を取ることを更に備えることを特徴とする請求項７に記載の生成方法。
【請求項１０】
前記インデックステーブルに登録されていない情報項目を新しいインデックスと関連付けることにより、前記インデックステーブルを更新する更新ステップを更に備えることを特徴とする請求項１乃至９のうち、いずれか１項に記載の生成方法。
【請求項１１】
前記インデックステーブルは、各インデックスと関連付けられた情報項目を含むグローバルテーブルのエントリに対する参照と前記インデックスを関連付けることを特徴とする請求項１乃至１０のうち、いずれか１項に記載の生成方法。
【請求項１２】
前記グローバルテーブルは、複数の圧縮器の間で共有され、前記複数の圧縮器により処理されたメッセージに含まれる情報項目を含み、各圧縮器が、前記共有されたグローバルテーブルを参照することで、自身が生成するメッセージの情報項目をインデックス化することを特徴とする請求項１１に記載の生成方法。
【請求項１３】
前記グローバルテーブルは、複数のネットワーク接続の間で共有され、対応する複数のそれぞれのローカルインデックステーブルにより参照され、
前記方法は、前記符号化中のある時点において、現在の接続を前記共有されたグローバルテーブルから新しいグローバルテーブルに移行する移行ステップを更に備えることを特徴とする請求項１１に記載の生成方法。
【請求項１４】
符号化されたメッセージの復号化方法であって、
前記メッセージのヘッダを特定する特定ステップと、
前記特定ステップにより特定されたヘッダから、ヘッダの情報項目とインデックスとを対応付けるインデックステーブルにおけるインデックスを抽出する抽出ステップと、
前記特定ステップにより特定されたヘッダから前記抽出ステップにより抽出されたインデックスに対応する情報項目と、前記特定ステップにより特定されたヘッダに含まれる情報項目のうち前記インデックステーブルに登録されていない情報項目との復号結果を得る復号ステップと、
前記特定ステップにより特定されたヘッダに含まれる情報項目のうち前記インデックステーブルに登録されていない情報項目を前記インデックステーブルに登録すべきか否かを規定するビットパターンであって、前記メッセージに含まれるビットパターンを参照する参照ステップと、
前記参照ステップにおいて参照されたビットパターンに応じて、前記メッセージのヘッダに含まれる情報項目のうち、前記インデックステーブルに登録されていない情報項目を前記インデックステーブルに追加する追加ステップと、
を備えることを特徴とする復号化方法。
【請求項１５】
前記インデックステーブルに登録されていない前記情報項目の少なくとも１つは、前記インデックステーブルに登録済みの情報項目を参照することで復号化されることを特徴とする請求項１４に記載の復号化方法。
【請求項１６】
前記メッセージのヘッダを構成する情報項目のうち、前記インデックステーブルに登録されていない情報項目のリテラル値は、前記インデックステーブルに登録済みの情報項目との差分に基づいて符号化されていることを特徴とする請求項１４又は１５に記載の復号化方法。
【請求項１７】
前記インデックステーブルに登録されていない情報項目のリテラル値に加えて、当該情報項目が前記インデックステーブルに登録済みの情報項目を参照することで復号化されるか否かを規定するフラグと、をさらに含むことを特徴とする請求項１４乃至１６のうち、いずれか１項に記載の復号化方法。
【請求項１８】
通信装置に対して送信されるメッセージを生成するデバイスであって、
前記通信装置に対して送信されるべきメッセージのヘッダにて示されるべき情報項目を特定する特定手段と、
前記特定手段により特定されたヘッダにて示されるべき複数の情報項目のそれぞれが、ヘッダの情報項目とインデックスとを対応付けたインデックステーブルに登録済みであるか、前記インデックステーブルに登録されていないかを判定する判定手段と、
前記特定手段により特定されたヘッダにて示されるべき複数の情報項目のうち、前記インデックステーブルに登録済みであると前記判定手段により判定された情報項目に対応するインデックスと、前記インデックステーブルに登録されていないと前記判定手段により判定された情報項目とをそれぞれ表す符号を含むメッセージであって、前記特定手段により特定されたヘッダにて示されるべき複数の情報項目のうち、前記インデックステーブルに登録されていないと前記判定手段により判定された情報項目をインデックステーブルに登録すべきか否かを規定するビットパターンを含むメッセージを生成する生成手段と、
を備えることを特徴とするデバイス。
【請求項１９】
符号化されたメッセージを復号化する復号化デバイスであって、
前記メッセージのヘッダを特定する特定手段と、
前記特定手段により特定されたヘッダから、ヘッダの情報項目とインデックスとを対応付けるインデックステーブルにおけるインデックスを抽出する抽出手段と、
前記特定手段により特定されたヘッダから前記抽出手段により抽出されたインデックスに対応する情報項目と、前記特定手段により特定されたヘッダに含まれる情報項目のうち前記インデックステーブルに登録されていない情報項目との復号結果を得る復号手段と、
前記特定手段により特定されたヘッダに含まれる情報項目のうち前記インデックステーブルに登録されていない情報項目を前記インデックステーブルに登録すべきか否かを規定するビットパターンであって、前記メッセージに含まれるビットパターンを参照する参照手段と、
前記参照手段において参照されたビットパターンに応じて、前記メッセージのヘッダに含まれる情報項目のうち、前記インデックステーブルに登録されていない情報項目を前記インデックステーブルに追加する追加手段と、
を備えることを特徴とする復号化デバイス。
【請求項２０】
コンピュータに、請求項１乃至１３のうち、いずれか１項に記載の生成方法の各ステップを実行させるためのプログラム。
【請求項２１】
コンピュータに、請求項１４乃至１７のうち、いずれか１項に記載の復号化方法の各ステップを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッセージを符号化及び復号化する方法、並びに対応する符号化デバイス及び復号化デバイスに関する。
【０００２】
本発明は、ネットワーク通信の分野、特に通信ネットワークを介してメッセージを送出する際に使用されるデータ圧縮の分野に属する。
【背景技術】
【０００３】
送出対象のメッセージには、多くの場合、符号器において圧縮され且つ復号器において伸張される情報の項目のリスト又はグループがある。例えばこれは、ＨＴＴＰ（ハイパーテキスト転送プロトコルの略である）ペイロードが圧縮されるＨＴＴＰ及びＨＴＴＰヘッダが圧縮されるＳＰＤＹプロトコルの場合である。
【０００４】
ＳＰＤＹは、周知のＨＴＴＰの改良を意図するプロトコルである。本発明を例示するために以下においてＳＰＤＹプロトコルを参照するが、本発明は他の構成に適用されてもよい。特に、本発明は、情報項目のリストが圧縮される多数のデータ送信プロトコル、例えば上述のＨＴＴＰプロトコル及びＳＰＤＹプロトコルに適用されてもよい。
【０００５】
ＨＴＴＰは、一般にウェブページを要求及び送出するために使用され、クライアント／サーバアーキテクチャに基づく。クライアント／サーバアーキテクチャにおいて、クライアントは、要求、すなわちＨＴＴＰ要求をサーバに送出し、サーバは、応答、すなわちＨＴＴＰ応答によりクライアントの要求に応答する。
【０００６】
要求及び応答は、種々のパート、特に非圧縮ＨＴＴＰヘッダ及び圧縮ＨＴＴＰペイロードを含むメッセージである。
【０００７】
図１は、ＨＴＴＰ要求及び次にＨＴＴＰ応答に連続的に一覧表示される６個のＨＴＴＰヘッダの一例を示す。
【０００８】
ＨＴＴＰヘッダは、名前（図１における太文字）と、それに対応する値から構成される。
【０００９】
例えば「Ｈｏｓｔ：ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ」において、Ｈｏｓｔはヘッダ名であり、その値は「ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ」である。このヘッダは、要求されたリソースのホスト（例えば、ｈｔｔｐ：／／ｅｎ．ｗｉｋｉｐｅｄｉａ．ｏｒｇ／ｗｉｋｉ／ＨＴＴＰにおいて使用可能なＨＴＴＰを記述するＷｉｋｉｐｅｄｉａのページ）を示すために使用される。ＨＴＴＰヘッダは当業者には周知であるため、本明細書では更に詳細に説明しない。
【００１０】
ＨＴＴＰの第１のバージョンにおいては、ＴＣＰ／ＩＰ接続は、ＨＴＴＰ要求／応答の送受信毎に確立された。
【００１１】
ＳＰＤＹは、いくつかの方法でＨＴＴＰを向上させるプロトコルである。
【００１２】
第１に、ＳＰＤＹは、いくつかのＨＴＴＰの要求及び応答を一意のＴＣＰ／ＩＰ接続を介して送出できるようにすることにより、そこでＨＴＴＰ送信の集合を規定する。このように、ウェブページの全ての構成要素（ＨＴＭＬ文書、画像、ＪａｖａＳｃｒｉｐｔ等）が同一のＴＣＰ／ＩＰ接続を共有することにより、ウェブページのロードを高速化され得る。
【００１３】
第２に、ＳＰＤＹは、Ｚｌｉｂデフレートアルゴリズム（「ｚｉｐ」形式を通しても知られている）を使用して、共有されたＴＣＰ／ＩＰ接続を介して送受信されたＨＴＴＰヘッダの圧縮を実現する。このようなバイナリ圧縮によりネットワーク負荷を軽減する。
【００１４】
デフレートアルゴリズムは、バイナリ表現の重複ストリングを探索し（スライディングウィンドウを使用して）てそれをそのバックリファレンスで置換し、且つバックリファレンスの記号をハフマン符号で置換することにより、ＨＴＴＰヘッダのシリアル化バイナリ表現の圧縮を実行する。
【００１５】
ＨＴＴＰヘッダのシリアル化バイナリ表現は、ＨＴＴＰヘッダのシリアル化の結果、ビット（又はバイト）のストリームとして得られる。
【００１６】
ＳＰＤＹにより取得された圧縮ゲインは受け入れ可能となっている。
【００１７】
しかし、速度性能は不適切であると観察され、メモリ消費が不都合なほどに高くなる恐れがある。
【００１８】
不適切な速度性能は、多数のヘッダにより得られる潜在的に大きなサイズのシリアル化バイナリ表現に起因する。
【００１９】
ＨＴＴＰサーバが同時に複数のクライアントに対して複数の接続を処理する場合、メモリ消費が高くなる恐れがある。特に接続数が増加する場合、すなわち１つの符号器又は圧縮器が各接続に割り当てられ、且つ専用のメモリ領域が符号器又は圧縮器毎に確保される場合、種々の接続を介して送信されたメモリのヘッダを個別に符号化するには大量のメモリが必要である。
【００２０】
例えば復号器側でメモリリソースの少ない制限されたデバイスと比較して、メモリ消費が高くなる恐れがある。
【００２１】
このような状況において、メモリコスト及び処理コストを実質的に削減しつつ同様の小型化を実現する情報項目（例えば、ＨＴＴＰヘッダ）のリストを圧縮する新しい方法が必要である。実施形態において、そのような新しい方法は、高い圧縮性能を維持するためにデフレート等のバイナリ圧縮に準拠すべきである。
【００２２】
論文「Ａ  Ｐｒｏｐｏｓａｌ  ｆｏｒ  Ｓｈａｒｅｄ  Ｄｉｃｔｉｏｎａｒｙ  Ｃｏｍｐｒｅｓｓｉｏｎ  ｏｖｅｒ  ＨＴＴＰ」（Ｊ．  Ｂｕｔｌｅｒ他、２００８年）は、クロスペイロード冗長を、共有辞書を参照した冗長要素を置き換えることで、符号化するために使用される辞書を開示する。しかし、復号器は、少量のメモリを使用では、多数の符号化要素を迅速に復号化できない。
【００２３】
本発明は、上述の問題のうちの１つ以上に対処するために提案されるものである。
【発明の概要】
【課題を解決するための手段】
【００２４】
本発明の第１の態様では、情報の項目の初期リストを含むメッセージをビットストリームに符号化する方法であって、
ローカルインデックステーブルにおいて既にインデックス化されている初期リストの情報項目と関連付けられたインデックスの第１のグループ及び前記ローカルインデックステーブルにおいてまだインデックス化されていない初期リストの他の情報項目のリテラル値の第２のグループを判定するステップと、
第１のグループのインデックスを符号化するステップと、
第２のグループのリテラル値の少なくともシリアル化バイナリ表現をバイナリ圧縮するステップと、
第１のグループ及び第２のグループを共に連結して情報項目の符号化ビットストリームを取得するステップとを備える方法が提供される。
【００２５】
本発明は、ＨＴＴＰヘッダの冗長性が高い場合、例えばＳＰＤＹの速さの２倍にまで処理速度を実質的に向上させる。更に本発明は、メモリ消費を改善させ得る。
【００２６】
これは、インデックス化ステップに基づいて従来のバイナリ圧縮及びグループ化の前に項目をインデックス化することで実現される。インデックス化により、符号器において限定されたメモリ使用量で非常に高速な冗長探索が可能になる一方で、復号器において、復号化は、情報項目がより高速に構築されることでより効率的になる。
【００２７】
これは、インデックス技術が非常に注目された冗長探索に基づくのに対し、デフレート等のバイナリ圧縮は、より低速な総当たり全数冗長探索を使用するためである。
【００２８】
従って、インデックスが同一のサブパート内でグループ化される符号化ビットストリームを提供することは、少数の符号化データを構文解析しつつ多数の情報項目、すなわちヘッダを復号化する復号器において処理を高速化する。
【００２９】
本発明の第２の態様は、第２の部分と連結された第１の部分を含む符号化データをビットストリームから取得するステップと、
第１の部分を復号化して、ローカルインデックステーブルにおいて既にインデックス化されている情報項目と関連付けられたインデックスの第１のグループを取得するステップと、
第２の部分をバイナリ伸張して、前記ローカルインデックステーブルにおいてまだインデックス化されていない情報項目に対応するリテラル値の第２のグループのシリアル化バイナリ表現を取得するステップと、
第１のグループのインデックスによりインデックス化情報項目及び第２のグループから文字通り復号化された情報項目から構成された復号化リストを提供するステップとを備える符号化メッセージを復号化する方法が提供される。
【００３０】
この方法は、上述の方法と同様の利点を提供するが、復号器においては提供しない。尚、第１のグループ及び第２のグループの情報項目、例えばＨＴＴＰヘッダは同時のものである。
【００３１】
本発明の第３の態様によると、情報の項目のリストを含むメッセージを符号化して複数の接続を介して送出する方法であって、
メッセージが属する接続専用のローカルインデックステーブルを使用してメッセージの情報項目のリストを符号化するステップを備え、
グローバルテーブルは、接続の間で共有され、情報の項目を含み、各接続のローカルインデックステーブルは、インデックスを共有グローバルテーブルのエントリに対する参照と関連付ける方法が提供される。
【００３２】
本発明のこの態様はメモリ消費を最適化する。これは、データ（本明細書においては情報項目）の大部分を格納するグローバルテーブルが、各情報項目を１回だけ格納できるようにする全ての接続の間で共有される一方で、インデックスが接続毎に最短のインデックスを提供する各接続に特有だからである。従って、グローバルテーブルにより、接続の間でインデックステーブルのメモリコストを共有することが可能になる。
【００３３】
逆に、本発明の第４の態様によると、複数の接続を介して受信された情報の項目の符号化リストを含む符号化メッセージを復号化する方法であって、
符号化メッセージが属する接続専用のローカルインデックステーブルを使用して符号化メッセージの情報項目の符号化リストを復号化するステップを備え、
グローバルテーブルは、全ての接続により共有され、情報の項目を含み、各接続のローカルインデックステーブルは、インデックスを共有グローバルテーブルのエントリに対する参照と関連付ける方法が提供される。
【００３４】
この方法は、上述の符号化方法と同様の利点を提供するが、復号器においては提供しない。
【００３５】
本発明の選択的な特徴は、添付の従属請求項において更に規定される。以下において、符号化又は圧縮に対してある特定の特徴を説明する時、符号器における対応する特徴が本発明の復号化又は伸張に対しても使用されてもよいことは、当業者により容易に理解されるだろう。
【００３６】
本発明の一実施形態によると、他の情報項目の少なくとも１つは、ローカルインデックステーブルにおいて既にインデックス化されている情報項目を参照することで符号化され、他の情報項目のリテラル値は、他の情報項目により取られた値と参照として既にインデックス化及び使用されている情報項目により取られた値との差分を示す。これは、後続のヘッダを符号化するために必要とされるデータの量を減少するための、ヘッダ（例えば、ヘッダ名）の間の部分的な冗長に基づく以下において規定されるようなデルタ符号化である。
【００３７】
特定の一実施形態において、他の情報項目に対応するシリアル化バイナリ表現のバイナリサブパートは、他の情報項目のリテラル値に加えて、参照として既にインデックス化及び使用されている情報項目のインデックスを含む。これは、デルタ復号化のために必要とされる情報を有する復号器を提供するためである。
【００３８】
特定の特徴によると、方法は、ローカルインデックステーブルにおいて既にインデックス化されている情報項目を、既にインデックス化されている情報を参照することで符号化された他の情報項目で置き換える（substitute）するステップを更に備える。この提供により、符号化が進行するにつれローカルインデックステーブルの増加は減少する。従って、それによりメモリを効率的に管理する。
【００３９】
本発明の別の実施形態によると、他の情報項目の１つに対応するシリアル化バイナリ表現のバイナリサブパートは、他の情報項目のリテラル値に加えて、他の情報項目がローカルインデックステーブルにおいて既にインデックス化されている情報項目を参照することで符号化されるか否かを規定する第１の１ビットフラグと、他の情報項目が更なるインデックス化のためにローカルインデックステーブルに追加されなければならないか否かを規定する第２のバイナリインデックスフラグとを含む。従って、符号化ヘッダに対するこのバイナリ設計は、符号器と復号器との間で効率的なインデックスの同期を提供する。
【００４０】
特に、第２のバイナリフラグは、他の情報項目が、新しいエントリとして又は参照として既にインデックス化及び使用されている情報項目の置き換えによりローカルインデックステーブルに追加されなければならないかを規定するためのビットを含んでもよい。これは、置き換えインデックス化方式により効率的にメモリを管理しつつ、効率的なインデックスの同期に貢献する。
【００４１】
本発明の実施形態の特定の特徴によると、バイナリサブパートは、他の情報項目により取られた値と参照として既にインデックス化及び使用されている情報項目により取られた値との間の共通部分の長さを規定するためのバイナリフィールドを含む。これは、ヘッダの値の部分を符号化する効率的な方法であり、その符号化は、既にインデックス化されているヘッダを参照する（すなわち、部分的に）ことで行われる。これは、共通部分を規定することは、一般に、その共通部分を構成する値を明示的に又は文字通りに示すことと比較してビットを節約するからである。例えば共通部分は、比較される２つの値を形成する第１の文字（アルファベット又は数字）であってもよい。
【００４２】
特定の特徴によると、バイナリサブパートは、項目名テーブルにおける他の情報項目の名前に対応するインデックスを規定するためのバイナリフィールドを含む。名前テーブルがいくつかのインデックステーブルの間で容易に共有されうるため、一般に、名前テーブルを使用することでメモリが節約される。
【００４３】
本発明の一実施形態において、インデックスの第１のグループは、符号化ビットストリームにおけるリテラル値の第２のグループに先行する。復号器において、これは、インデックスを符号化する第１の部分は、ビットストリームの第２の部分（リテラル値の）に先行する。
【００４４】
この構成により、復号器により復号化する少数の符号化データを含む多数の情報項目、例えばＳＰＤＹにおけるＨＴＴＰヘッダにアクセスする。これは、各インデックス化情報項目を示す大部分のデータがローカルインデックステーブルに格納され、且つビットストリームにおいて符号化されないためである。
【００４５】
別の実施形態において、連結するステップは、連結された第１のグループ及び第２のグループのシリアル化バイナリ表現を生成し、バイナリ圧縮するステップは、シリアル化バイナリ表現全体を圧縮する。インデックスに対する冗長がシリアル化バイナリ表現でより多く発生するため、バイナリ圧縮のためのより短いスライディングウィンドウが使用されてもよい。より短いスライディングウィンドウは、メモリの節約（より少ないビットのバッファリング）及び処理速度の向上（より少ないビットの探索）を意味する。
【００４６】
更に別の実施形態において、情報の項目は、ＨＴＴＰメッセージのＨＴＴＰヘッダである。これは、例えばＳＰＤＹの場合である。
【００４７】
特に、ＨＴＴＰヘッダは、少なくともＨＴＴＰ名及びＨＴＴＰ値から構成され、第１のグループのインデックス化ＨＴＴＰヘッダは、ＨＴＴＰ名をインデックス化するインデックス及びリテラルＨＴＴＰ値を含む。これは、ＨＴＴＰヘッダ名（一般に、連続したＨＴＴＰメッセージにおいて使用される）の間の高い冗長性を利用し、それらの値は、あるメッセージから別のメッセージに高度に変動してもよい。同一の方法は、名前及び値から構成されたあらゆる情報項目に対して使用されてもよい。
【００４８】
特定の特徴によると、ＨＴＴＰヘッダは、少なくともＨＴＴＰ名及びＨＴＴＰ値から構成され、この方法は、インデックスレベルフラグをＨＴＴＰヘッダと関連付けるステップを有し、前記インデックスレベルフラグが、ＨＴＴＰヘッダに依存して、ＨＴＴＰヘッダがローカルインデックステーブルにおける対応する情報項目と同一のＨＴＴＰ名及びＨＴＴＰ値を有することを示す第１の完全なインデックス化状態、又はＨＴＴＰヘッダがローカルインデックステーブルにおける対応する情報項目と同一のＨＴＴＰ名であるが異なるＨＴＴＰ値を有することを示す第２の部分的なインデックス化状態を取ることを更に備える。これにより、徐々に変動するいくつかのＨＴＴＰヘッダの高い冗長性の利用が可能になる。例えば、いくつかのメッセージが単一の秒内で送出されてもよいため、毎秒更新された時間ＨＴＴＰヘッダをインデックス化することが有利であってもよい。その後、後続の秒のメッセージに対して、フラグの部分的なインデックス化状態が使用される。
【００４９】
特に、ＨＴＴＰヘッダは、第１のグループのインデックス化ＨＴＴＰヘッダであってもよい。
【００５０】
特定の特徴によると、インデックス化ＨＴＴＰヘッダに対するインデックスレベルフラグが第２の部分的なインデックス化状態である場合、インデックス化ＨＴＴＰヘッダの異なるＨＴＴＰ値は、異なるＨＴＴＰ値とローカルインデックステーブルにおける対応する情報項目のＨＴＴＰ値との差分を使用して符号化される。
【００５１】
本発明の別の実施形態において、この方法は、ローカルインデックステーブル内で第２のグループの少なくとも１つの情報項目を新しいインデックスと関連付けることにより、そのローカルインデックステーブルを更新するステップを更に備える。これにより、同一の情報項目の新しい出現がインデックス化されうるようにローカルインデックステーブルの供給が可能になる。
【００５２】
特に、この方法は、符号化ストリームにおいて、前記更新中に新しいインデックスと関連付けられる第２のグループのバイナリ圧縮された各情報項目とインデックスフラグを関連付けるステップを更に備えてもよい。これにより、復号器が認識していないかもしれないインデックス化戦略を復号器に示すことが可能になる。
【００５３】
別の特定の特徴によると、この方法は、第２のグループの情報の項目の出現の頻度を判定するステップと、判定された頻度に依存してローカルインデックステーブルにおいて情報の項目をインデックス化することを決定するステップとを更に備えてもよい。この提供により、最も多く出現する項目だけがインデックス化され、それにより、ローカルインデックステーブルを格納するために使用されたメモリとインデックスの使用による処理速度の向上との妥協が最適化される。
【００５４】
本発明の更に別の実施形態において、ローカルインデックステーブルは、前記インデックスと関連付けられた情報の項目を含むグローバルテーブルのエントリに対する参照と各インデックスを関連付ける。これにより、メッセージが送信されるいくつかの接続のために同一のグローバルテーブルの共有が可能になる。このような状況において、ローカルインデックステーブルは接続毎に使用される。
【００５５】
特定の特徴によると、ローカルインデックステーブルは、グローバルテーブルを参照することでインデックス化された情報の少なくとも１つの項目及びローカルインデックステーブル内でのみインデックス化された情報の少なくとも１つの項目を含む。いくつかの接続により共有されるある特定の情報項目又は非常に頻繁なある特定の情報項目（共有グローバルテーブルを参照することで格納されうる）を特定の接続専用のある特定の情報項目（その接続専用のローカルインデックステーブル内に格納されてもよい）と区別する改良されたインデックス化戦略が実現されてもよい。
【００５６】
特に、この方法は、情報の項目の出現の頻度を判定するステップと、判定された頻度に依存してローカルインデックステーブルにおいてのみ、又はグローバルテーブルを参照することで情報の前記項目をインデックス化することを決定するステップを更に備えてもよい。
【００５７】
別の特定の特徴によると、グローバルテーブルは、複数の圧縮器（複数の接続に対応する）の間で共有され、前記複数の圧縮器により処理されたメッセージからの情報の項目を含む。そして各圧縮器が、共有グローバルテーブルを参照することで、自身が処理するメッセージからの情報の項目をインデックス化するためにそのローカルインデックステーブルを有する。この提供は、グローバルテーブルが圧縮器の間で共有されるのに対し、ローカルインデックステーブルは各圧縮器に特有であることを明示的に示す。
【００５８】
更に別の特定の特徴によると、第１のグループ及び第２のグループを判定するステップは、初期リストの情報項目に対応するエントリをグローバルテーブルにおいて探索するステップと、発見されたエントリに対する参照をローカルインデックステーブルにおいて探索するステップとを含む。そのような探索は、共有グローバルテーブルの使用に適応される。
【００５９】
本発明の別の実施形態によると、この方法は、前記判定するステップ、前記連結するステップ及び前記バイナリ圧縮するステップを使用する情報項目の初期リストの第１の符号化、又は項目リテラル値のシリアル化バイナリ表現のバイナリ圧縮のみを使用する情報項目の初期リストの第２の符号化のどちらかを選択するステップ（すなわち、インデックス化を起動すること又は起動しないこと）を更に備え、
ここで第１の符号化のバイナリ圧縮のために使用されたスライディングバイナリウィンドウは、第２の符号化のバイナリ圧縮のために使用されたスライディングバイナリウィンドウより小さい。
【００６０】
この構成により、メモリの使用は、情報項目のインデックスを使用する場合に減少される。これは、インデックス化により、シリアル化バイナリ表現内の冗長がより多く発生するために、これらの冗長を検出するのはより短いスライディングウィンドウで十分だからである。
【００６１】
本発明の更に別の実施形態によると、グローバルテーブルは、複数のネットワーク接続の間で共有され、対応する複数のそれぞれのローカルインデックステーブルにより参照され、
そして、この方法は、符号化中のある時点において、現在の接続を前記共有グローバルテーブルから新しい（共有）グローバルテーブルに移行するステップを更に備える。
【００６２】
グローバルテーブルの移行によりメモリが節約される。これは、メッセージが送受信され且つ情報項目がインデックス化される時、インデックス化情報項目の数が共有グローバルテーブルにおいて増加するためである。移行により、そのテーブルからの未使用のインデックスの消去が可能になることで、メモリを節約する。
【００６３】
それは、本発明の上述の第３の態様の特徴及びその選択的な特徴が本発明の上述の第１の態様において実現されてもよいことを意味する。逆に、本発明の第１の態様及びその選択的な機能において上述した符号化処理は、複数のネットワーク接続のいくつか又は全てにより実現されてもよい。
【００６４】
特定の特徴によると、新しいグローバルテーブルが、現在共有されているグローバルテーブルに関連する少なくとも１つの基準（例えば、そのテーブルの寿命）に依存して、新しい接続に対する要求を受信することで作成されてもよい。その後、この新しい接続を作成する時点で、その新しい接続に対する新しいクリーンなグローバルテーブルに作用するかが決定される。新しいクリーンなグローバルテーブルは、前の共有グローバルテーブルの消去バージョンである。
【００６５】
特に、この方法は、現在共有されているグローバルテーブル及び新しいグローバルテーブルの双方を格納するために使用されたメモリの量に基づいて、現在共有されているグローバルテーブルからエントリを除去するステップを更に備えてもよい。これにより、現在のグローバルテーブルが廃棄及び削除される前に、新しいグローバルテーブル及び現在のグローバルテーブルの双方を使用する際のメモリ制約に準拠することが可能になる。
【００６６】
別の特定の特徴によると、現在の接続を移行するステップは、現在の接続を終了する要求の受信をトリガとされる。
【００６７】
特に、現在の接続を移行するステップは、現在の接続により使用されたエントリを現在共有されているグローバルテーブルから除去するステップと、除去されたこれらのエントリを新しいグローバルテーブルに追加するステップと、その後前記現在共有されているグローバルテーブルをメモリから削除するステップとを含む。この提供は、既存のインデックスが、メモリ空間を解放つつ現在の接続に対して維持されることを保証する。
【００６８】
本発明の更に別の実施形態によると、グローバルテーブルは、複数のネットワーク接続の間で共有され、対応する複数のそれぞれのローカルインデックステーブルにより参照され、共有グローバルテーブルにおける各インデックス化情報項目は、そのインデックス化情報項目を使用して接続数をカウントする接続カウンタと関連付けられ、
この方法は、インデックス化情報項目の接続カウンタに基づいてメモリ節約動作を実行するステップを更に備える。
【００６９】
接続カウンタの使用により、共有グローバルテーブルのエントリ（すなわち、インデックス化情報項目）がいずれの接続によっても使用されなくなる時を容易に検出することが可能になる。このような状況において、このエントリがテーブルから削除されることにより、メモリ空間を解放してもよい。
【００７０】
特に、メモリ節約動作は、対応する接続カウンタがゼロの場合に共有グローバルテーブルからインデックス化情報項目を除去するステップを含む。
【００７１】
別の特定の特徴によると、メモリ節約動作は、閾値より小さい値の接続カウンタと関連付けられたインデックス化情報項目を使用する現在の接続をリセットするステップを含む。削除するためにエントリ（インデックス化情報項目）を使用する接続が依然としてあるかもしれないが、この提供は、メモリ空間を解放することを目的とする。これらの接続をリセットすることにより、それらの対応するインデックステーブルがリセットするとゼロから再構築されるため、依然として削除されたエントリのインデックス化を可能にする。
【００７２】
本発明の更に別の実施形態によると、このい方法は、メモリを解放する要求を受信したことに応じて、ローカルインデックステーブルにおいてインデックス化情報項目の数を保存するステップと、グローバルテーブルをフラッシュするステップＳと、保存した数から始まるインデックスを使用してローカルインデックステーブルにおいて新しい情報項目をインデックス化するステップを備えてもよい。この提供により、符号器及び復号器の双方においてインデックス化機構との互換性を維持しつつ、メモリ空間を解放することが可能になる。
【００７３】
本発明の別の特定の実施形態によると、リテラル値のシリアル化バイナリ表現は、初期リストでのそれらの相対順序に従って前記値を維持する。これは、情報項目の初期の順序が復号器によるレンダリングにとって重要である場合に実現されてもよい。
【００７４】
特に、ビットストリームは、初期リスト内に情報項目の順序を格納する追加情報を含んでもよい。これにより、復号器は、情報項目が処理される前にそれらの元の順序に従ってそれらを配置することが可能になる。
【００７５】
本発明の更に別の実施形態によると、メッセージは情報の項目の第２の初期リストを含み、符号化方法は、第２の初期リストの情報項目のリテラル値のシリアル化バイナリ表現を提供するステップと、第１のグループ及び第２のグループから結果として得られた情報項目の符号化ビットストリームとそれを連結するステップとを備える。従って、本実施形態は、ヘッダを迅速に取得するために復号器がバイナリ部分を直接読み出せるビットストリームを提供した。従って、優先順位ヘッダは、取得されるそれへの迅速なアクセスを保証するためにそのようなリストを使用してビットストリームに含まれてもよい。
【００７６】
特定の特徴によると、第２の初期リストに対するシリアル化バイナリ表現は、結果として得られるビットストリームにおいて符号化ビットストリームに先行する。この場合も、特にビットストリームがストリーミングを通して送出される場合、これは上述の（優先順位）ヘッダを可能な限り早く取得するためである。
【００７７】
次に、より具体的には復号化方法に関していくつかの実施形態の特徴を紹介する。
【００７８】
一実施形態によると、前記ローカルインデックステーブルにおいてまだインデックス化されていない情報項目の少なくとも１つは、ローカルインデックステーブルにおいて既にインデックス化されている情報項目を参照することで復号化され、第２のグループにおける対応するリテラル値は、まだインデックス化されていない情報により取られた値と参照として既にインデックス化及び使用されている情報項目により取られた値との差分を示す、この場合も、これは復号器から見られたようなデルタ符号化である。
【００７９】
特に、まだインデックス化されていない情報項目に対応するシリアル化バイナリ表現のバイナリサブパートは、まだインデックス化されていない情報項目のリテラル値に加えて、参照として既にインデックス化及び使用されている情報項目のインデックスを含んでもよい。従って、復号器は、ヘッダを完全に再構成できる。
【００８０】
特定の特徴によると、この方法は、既にインデックス化されている情報項目を参照することで復号化されると、ローカルインデックステーブルにおいて既にインデックス化されている情報項目をまだインデックス化されていない情報項目で置き換えるステップを更に備える。この提供により、復号化が進行するにつれローカルインデックステーブルの増加は減少する。従って、それによりメモリを効率的に管理する。
【００８１】
本発明の別の実施形態によると、まだインデックス化されていない情報項目の１つに対応するシリアル化バイナリ表現のバイナリサブパートは、まだインデックス化されていない情報項目のリテラル値に加えて、まだインデックス化されていない情報項目がローカルインデックステーブルにおいて既にインデックス化されている情報項目を参照することで復号化されるか否かを規定する第１の１ビットフラグと、まだインデックス化されていない情報項目が更なるインデックス化のためにローカルインデックステーブルに追加されなければならないか否かを規定する第２のバイナリインデックスフラグとを含む、
特に、第２のバイナリフラグは、まだインデックス化されていない情報項目が、新しいエントリとして又は参照として既にインデックス化及び使用されている情報項目の置き換えによりローカルインデックステーブルに追加されなければならないかを規定するためのビットを含んでもよい。
【００８２】
特定の特徴によると、バイナリサブパートは、まだインデックス化されていない前記情報項目により取られた値と参照として既にインデックス化及び使用されている前記情報項目により取られた値との間の共通部分の長さを規定するためのバイナリフィールドを含む。
【００８３】
別の特定の特徴によると、バイナリサブパートは、項目名テーブルにおいてまだインデックス化されていない情報項目の名前に対応するインデックスを規定するためのバイナリフィールドを含む。
【００８４】
これらの提供は、復号器において、符号器に対して上述したような同様の利点、特にインデックス標識がビットストリームにおいてバイナリ規定されるために効率的なインデックスの同期を提供する利点を提供する。
【００８５】
依然としてビットストリームの復号化に関する更に別の実施形態によると、前記ビットストリームから取得された符号化データは、第１の部分及び第２の部分と連結された第３の部分を含み、第３の部分は、追加リストの情報項目のリテラル値のシリアル化バイナリ表現である。
【００８６】
特定の特徴によると、第３の部分は、ビットストリームにおいて第１の部分及び第２の部分に先行する。
【００８７】
これらの提供は、例えばいくつかのヘッダが伸張に依存しないためにビットストリームにおいて早く配置され且つ容易な復号器であるため、復号器がそれらに迅速にアクセスすることに貢献する。
【００８８】
本発明の第５の態様によると、情報の項目の初期リストを含むメッセージをビットストリームに符号化する符号化デバイスであって、
ローカルインデックステーブルにおいて既にインデックス化されている初期リストの情報項目と関連付けられたインデックスの第１のグループ及び前記ローカルインデックステーブルにおいてまだインデックス化されていない初期リストの他の情報項目のリテラル値の第２のグループを判定する判定手段と、
第１のグループのインデックスを符号化する符号器と、
第２のグループのリテラル値の少なくともシリアル化バイナリ表現をバイナリ圧縮する圧縮器と、
第１のグループ及び第２のグループを共に連結して情報項目の符号化ビットストリームを取得する連結モジュールとを備える符号化デバイスが提供される。
【００８９】
本発明の第６の態様によると、符号化メッセージを復号化する復号化デバイスであって、
第２の部分と連結された第１の部分を含む符号化データをビットストリームから取得する取得手段と、
第１の部分を復号化して、ローカルインデックステーブルにおいて既にインデックス化されている情報項目と関連付けられたインデックスの第１のグループを取得する復号器と、
第２の部分をバイナリ伸張して、前記ローカルインデックステーブルにおいてまだインデックス化されていない情報項目に対応するリテラル値の第２のグループのシリアル化バイナリ表現を取得する伸張器と、
第１のグループのインデックスによりインデックス化情報項目及び第２のグループから文字通り復号化された情報項目から構成された復号化リストを提供する出力部とを備える復号化デバイスが提供される。
【００９０】
本発明の第７の態様によると、情報の項目のリストを含むメッセージを符号化して複数の接続を介して送出する符号化デバイスであって、
接続の間で共有され且つ情報の項目を含むグローバルテーブルと、
各々がインデックスを共有グローバルテーブルのエントリに対する参照と関連付ける複数の接続に対応する複数のローカルインデックステーブルと、
メッセージが属する接続専用のローカルインデックステーブルを使用してメッセージの情報項目のリストを符号化する符号器とを備える符号化デバイスが提供される。
【００９１】
本発明の第８の態様によると、複数の接続を介して受信された情報の項目の符号化リストを含む符号化メッセージを復号化する復号化デバイスであって、
接続の間で共有され且つ情報の項目を含むグローバルテーブルと、
各々がインデックスを共有グローバルテーブルのエントリに対する参照と関連付ける複数の接続に対応する複数のローカルインデックステーブルと、
符号化メッセージが属する接続専用のローカルインデックステーブルを使用して符号化メッセージの情報項目の前記符号化リストを復号化する復号器とを備える復号化デバイスが提供される。
【００９２】
本発明の別の態様は、装置のマイクロプロセッサ又はコンピュータシステムにより実行された時に、上述したようなステップを装置に実行させるプログラムを格納する非一時的なコンピュータ可読媒体に関する。
【００９３】
符号化デバイス及び復号化デバイス、並びに非一時的なコンピュータ可読記憶媒体は、符号化又は復号化の方法、特にＨＴＴＰメッセージのＨＴＴＰヘッダ等のメッセージにおける項目のリストを符号化する際に処理速度を向上させ且つメモリ消費を減少する方法に関連して先に及び以下において説明されるものに類似する特徴及び利点を有してもよい。
【００９４】
本発明の他の態様は、添付の図７；図９；図７及び９；図７及び１１；図７及び１２；図７，９及び１１；図７、９及び１２に示され、記述された符号化の方法に関する。
【００９５】
本発明の他の態様は、添付の図８；図１０；図８及び１０；図８及び１１；図８及び１２；図８，１０及び１１；図８、１０及び１２に示され、記述された復号化の方法に関する。
【００９６】
本発明に係る方法の少なくとも一部は、コンピュータにより実現されてもよい。従って、本発明は、全てがハードウェアの実施形態及び全てがソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコード等を含む）、あるいは一般に本明細書において全て「回路」、「モジュール」又は「システム」と呼ばれてもよいソフトウェアの態様とハードウェアの態様とを組み合わせる一実施形態の形式をとってもよい。更に本発明は、コンピュータ使用可能プログラムコードを媒体に取り入れる表現のあらゆる有形の媒体において実施されたコンピュータプログラムの形式をとってもよい。
【００９７】
本発明は、ソフトウェアで実現されうるため、有形のキャリア媒体又は一時的なキャリア媒体等のあらゆる適切なキャリア媒体をプログラム可能な装置に提供するコンピュータ可読コードとして実施されてよい。有形のキャリア媒体は、例えばフロッピディスク、ＣＤ−ＲＯＭ、ハードディスクドライブ、磁気テープデバイス又は固体メモリ素子等の記憶媒体を含んでもよい。一時的なキャリア媒体は、信号、例えば電気信号、電子信号、光信号、音響信号、磁気信号、あるいはマイクロ波又はＲＦ信号等の電磁信号を含んでもよい。
【００９８】
次に、本発明の実施形態を単なる一例として且つ以下の図面を参照して説明する。
【図面の簡単な説明】
【００９９】
【図１】図１は、ＨＴＴＰ要求及びＨＴＴＰ応答のそれぞれに対して６個のＨＴＴＰヘッダを示す図。
【図２ａ】、
【図２ｂ】、
【図２ｃ】、
【図２ｄ】図２は、本発明の原理が実現されるＳＰＤＹの一例を示す図。
【図３】図３は、本発明に係るＳＰＤＹ接続の２つの連続したＨＴＴＰ応答に対するデフレート圧縮に加えてヘッダインデックス化の一例を示す図。
【図４ａ】、
【図４ｂ】図４は、それぞれ個別に且つグローバルテーブルを参照して構築されたローカルインデックステーブルの２つの異なる実現例を示す図。
【図５】図５は、図４の２つの方法に従ってローカルインデックステーブルを格納するために使用されたメモリ空間を示すグラフ。
【図６】図６は、本発明の実施形態が実現されうる処理装置の構成要素を示すブロック図。
【図７】図７は、本発明の一実施形態に係るＨＴＴＰヘッダの符号化処理の一般的なステップを示すフローチャート。
【図８】図８は、本発明の一実施形態に係るＨＴＴＰヘッダの復号化処理の一般的なステップを示すフローチャート。
【図９】図９は、本発明の第２の実施形態に係る共有グローバルテーブルに基づいてＨＴＴＰヘッダの符号化処理の一般的なステップを示すフローチャート。
【図１０】図１０は、本発明の第２の実施形態に係る共有グローバルテーブルに基づいてＨＴＴＰヘッダの復号化処理の一般的なステップを示すフローチャート。
【図１１】図１１は、現在の接続を現在の共有グローバルテーブルから新しい共有グローバルテーブルに移行するステップを示すフローチャート。
【図１２】図１２は、接続の寿命に従って共有グローバルテーブルを最適化するステップを示すフローチャート。
【図１３】図１３は、本発明を使用して取得可能な種々の符号化ビットストリームを概略的に示す図。
【図１４】、
【図１５】、
【図１６】、
【図１７】、
【図１８】図１４〜図１８は、本発明の種々の実施形態に係るヘッダを符号化するバイナリ表現を示す図であり、図１４は、インデックステーブルからインデックスを使用して符号化されたヘッダに対するバイナリ表現を示す図であり、図１５は、文字通り符号化されるヘッダに対するバイナリ表現を示す図であり、図１６及び図１７は、それぞれインデックス化なしでデルタ符号化されるヘッダに対するバイナリ表現及びインデックス化してデルタ符号化されるヘッダに対するバイナリ表現を示す図であり、図１８は、文字通り符号化されるヘッダ値に対するバイナリ表現を部分的に示す図である。
【発明を実施するための形態】
【０１００】
図１を参照すると、本明細書ではＨＴＴＰヘッダである情報項目の第１の部分は、以下において説明されるようなデフレート圧縮を使用してインデックス化及び／又は圧縮される。そして、情報項目の第２の部分は、リテラル値のシリアル化バイナリ表現に変換され、インデックス化も圧縮もされずにビットストリームに入力される。
【０１０１】
情報項目の第１の部分全体が圧縮される場合、情報項目の第２の部分は、以下において説明されるように、完全に又は部分的にインデックス化されるものの非圧縮のヘッダのシリアル化バイナリ表現を更に含んでもよい。
【０１０２】
第２の部分に対する圧縮の欠如は、復号器（例えば、ＨＴＴＰプロキシサーバ）がいくつかのＨＴＴＰヘッダに容易に且つ迅速にアクセスするのに有利である。圧縮されない情報項目から構成された追加の初期リストのヘッダは、例えばヘッダ名に基づいて事前定義済みのリストにおいて規定されうる。例えば、ヘッダ「ＨＴＴＰ  Ｍｅｔｈｏｄ」、「ＨＴＴＰ  Ｖｅｒｓｉｏｎ」及び「Ｓｔａｔｕｓ」（不図示）は、そのような追加の初期リストの一部になりうるという利点がある。
【０１０３】
以下において、図１４〜図１８を参照してヘッダに対するバイナリ表現を説明する。
【０１０４】
符号化ビットストリームにおいて、追加の初期リストのシリアル化バイナリ表現は、一度符号化及び／又は圧縮されると、特に先立って、情報項目の第１の部分に対応する符号化及び圧縮されたビットストリームと連結されてもよい。
【０１０５】
図２の左部分は、３つの接続を有し、且つ３つのクライアントに対してＨＴＴＰヘッダの個別のデフレート圧縮（ＺＩＰ１、ＺＩＰ２及びＺＩＰ３）を実行するサーバ（図２ａ）、並びにＨＴＴＰメッセージを受信するために３つの接続を有し且つ個別の伸張を実行するクライアント（図２ｃ）に対する従来のＳＰＤＹを示す。
【０１０６】
図２の右部分は、本発明の一実施形態を示す。すなわち、３つの個別のデフレートステップ（ＺＩＰ１、ＺＩＰ２及びＺＩＰ３）の前に、ヘッダインデックス化は共有グローバルテーブルに基づいて実行される（図２ｂ）。対応するヘッダインデックス化は、復号器において実行される（図２ｄ）。
【０１０７】
前のインデックス化によって、より少ない数のバイトがデフレートを使用して圧縮又は伸張されるため、これによりデフレートステップの減少が可能になる。また、ヘッダインデックス化のために接続により共有されたグローバルテーブルにより、インデックスメモリコストを更に共有できるようになる。
【０１０８】
図３は、ＳＰＤＹ接続の２つの連続したＨＴＴＰ応答に対するデフレート圧縮に加えてヘッダインデックス化を示す。インデックス化又は圧縮対象でないヘッダの第２の部分が提供される場合、これはヘッダの第１の部分を考慮する。図３ａは、第１の応答に対する状況を示し、図３ｂは、後で発生する第２の応答に対する状況を示す。
【０１０９】
各応答の４つのＨＴＴＰヘッダは、図３の上部に示される。
【０１１０】
ＳＰＤＹ接続における第１の応答に関して、ヘッダがまだ処理及びインデックス化されていないため、前の応答との類似性は発見されない。従って、全ての４つのＨＴＴＰヘッダは、標準的なＳＰＤＹ符号化により文字通り符号化される。すなわち、各ＨＴＴＰヘッダの名前は、最初に文字通り符号化されるかあるいはヘッダ名テーブルを参照してインデックス化され、その後、その値が文字通り符号化される。図１５及び図１８を参照して、そのような符号化のバイナリ表現の一例を以下において説明する。
【０１１１】
次にプロセッサは、デフレート圧縮を符号化ストリーム（すなわち、シリアル化バイナリストリーム）に適用して、ＨＴＴＰ応答においてネットワークを介して送信される圧縮ヘッダストリームを取得する。
【０１１２】
同時に、４つのＨＴＴＰヘッダは、後でインデックスを再利用するために処理済みのヘッダのリストに格納される。このリストは、場合によっては（いくつかの実施形態において）上述のグローバルテーブルを参照するローカルインデックステーブルである。この例において、ＳＰＤＹ接続のためのローカルインデックステーブルは、各ＨＴＴＰヘッダを特定のインデックスと関連付ける。
【０１１３】
ＳＰＤＹ接続において第１の応答より後で発生する第２の応答に関して、４つのＨＴＴＰヘッダが更に処理される。そのうちの３つは、第１の応答の最初の３つのヘッダと全く同一であり、既にローカルインデックステーブルに格納されている。
【０１１４】
例えば図３に示されるようにそれぞれ０、１及び２である対応する３つのインデックスは、ローカルインデックステーブルから検索され、最初の３つのＨＴＴＰヘッダを符号化する。これは、インデックスの第１のリスト又はグループを構成する。図１４を参照して、各符号化インデックスのバイナリ表現の一例を以下において説明する。
【０１１５】
次に、残りのＨＴＴＰヘッダは、インデックスとして符号化され得ないために、ＳＰＤＹ符号化を使用して文字通り符号化される。これは、リテラル値の第２のリスト又はグループを構成し、次に、そのシリアル化バイナリヘッダストリームは、第２の応答においてネットワークを介して送出される前にデフレート圧縮を使用して圧縮され、第１のリスト又はグループと連結される。
【０１１６】
以下の場合、第１のリスト及び第２のリストを参照するが、上述したようにグループも参照されうる。
【０１１７】
再度、圧縮ヘッダの送出と同時に、ローカルインデックステーブルは、文字通り符号化されたヘッダを新しいインデックス（インデックス４）に一致させる新しいエントリを追加することで更新されるため、後続の応答において冗長を効率的に（そのインデックスを用いて）符号化するために使用可能である。
【０１１８】
以下において説明される実施形態において、第２のリストを形成する残りのＨＴＴＰヘッダの各々は、ローカルインデックステーブルにおいて既にインデックス化されているヘッダを参照することにより、デルタ符号化、すなわち符号化される。この例において、テーブルの第４のエントリ（３に等しいインデックスを含む）は、同一のヘッダ名（すなわち、「Ｄａｔｅ」）を有するため、このエントリに対する参照が使用可能であり、残りのＨＴＴＰヘッダにより取られた値とこのエントリにより取られた値との差分が文字通り符号化される。従って、結果として得られるバイナリ表現は、使用されたインデックス及び差分のリテラル値を含む。図１６〜図１８を参照して、そのようなバイナリ表現の一例を以下において挙げる。
【０１１９】
一変形例において、残りのＨＴＴＰヘッダにより取られた値は、差分の代わりに直接文字通り符号化されてよい。
【０１２０】
デルタ符号化が使用される状況において、符号化ヘッダを新しいインデックスに一致させる新しいエントリを追加する一変形例は、ちょうど符号化された残りのＨＴＴＰヘッダと共に参照として使用されたエントリを置き換えることで構成されてもよい。２種類の更新（増分又は置き換えによる）のどちらにするかを判断する基準は、例えばヘッダ名に基づく統計的に規定された戦略に基づいてもよい。
【０１２１】
従って、図１６〜図１８のバイナリ表現は、残りのＨＴＴＰヘッダが新しいエントリとして又は参照として既にインデックス化及び使用されているヘッダの置き換えによりローカルインデックステーブルに追加されなければならないかを規定するためのビットを含む。
【０１２２】
図３ｂの上述の例から明らかなように、ヘッダインデックス化により、デフレート圧縮されるビットの量が減少するために、ＳＰＤＹ符号化を介して処理を向上できる。これらのヘッダ間に高い冗長性がある場合、後続のＨＴＴＰメッセージのＨＴＴＰヘッダに対して処理速度を最大２倍向上させることも可能である。
【０１２３】
当然、ＬＺＷ又はＢＺＩＰ２等のデフレート以外の普遍的な可逆圧縮技術は、例示する目的で本明細書において利用されたデフレート圧縮の代わりに使用可能である。また、本発明は、メッセージにおける情報項目のあらゆるリストに適用され、ＨＴＴＰヘッダが一例として示される。
【０１２４】
また、バイナリストリームを小さくして圧縮する本発明に係るヘッダインデックス化のために、各接続のデフレートスライディングウィンドウが小さくされることにより、メモリ（より少ないバイトのバッファリング）及び速度（より少ないバイトの探索）の双方を節約できてもよい。これは、更なるメモリコストが非常に少ないヘッダインデックス化方法がその状況において速度を向上し続けるが、より大きなスライディングウィンドウのサイズに対して達成された圧縮率を更に維持できるようにするためである。
【０１２５】
例えば、スライディングウィンドウのサイズがメッセージのＨＴＴＰヘッダを示すために使用されたバイトの数より小さくなる場合、一部の冗長がデフレート圧縮により検出されないため、結果として圧縮が低下する。例示するために、同一のヘッダＡが２つの連続したメッセージに現れる場合、ヘッダＡは、第１のメッセージの符号化中に現在のスライディングウィンドウに追加されるが、第２のメッセージのヘッダＡの符号化を開始する前にスライディングウィンドウから除去されてもよい（ウィンドウが短すぎる場合）。従って、より少ない冗長が実際に検索されることにより、圧縮効率の低下を招く恐れがある。
【０１２６】
しかし、インデックス化ヘッダがインデックステーブルに引き続き維持されるため、これはヘッダインデックス化により補償される。従って、依然として冗長を検出できる。
【０１２７】
また、ヘッダインデックス化により、復号器においてＨＴＴＰヘッダにより高速にアクセスすることが可能になる。これは、インデックスにより、構文解析されて符号化ビットストリームからアクセスされ、対応するＨＴＴＰヘッダ（ローカルインデックステーブルに格納された）を取得するために復号化される必要のあるビット又はバイトが殆どないためである。これは、インデックスの第１のリストが符号化ビットストリームにおいてリテラル値の第２のリストに先行する場合に特に当てはまる。
【０１２８】
これらの速度及び圧縮の利点に加えて、いくつかの同時の接続のためにローカルインデックステーブルを効率的に実現することにより、メモリを節約できる。
【０１２９】
図４ａは、第１の接続（上方の「＃１」）及び第２の接続（下方の「＃２」）に対するローカルインデックステーブルの実現例の第１の例を示す。ＨＴＴＰメッセージの符号化中に遭遇される各ＨＴＴＰヘッダの全体は、メッセージが属する接続専用のローカルインデックステーブルに追加される。この結果、同一のＨＴＴＰヘッダを２回格納することになり（例えば、「Ｓｔａｔｕｓ：２００  ＯＫ」）、且つ全体のメモリコストが１５５バイトになるだろう。
【０１３０】
図４ｂは、同一のインデックスのメモリコスト削減の実現例を示す。上述したようなグローバルテーブルは、ＨＴＴＰヘッダを格納し且つそれらを参照（Ａ、Ｂ等）と関連付けるために使用される。従って、ローカルインデックステーブルは、インデックスをグローバルテーブルの参照と関連付けるだけである。図４ａの１５５バイトのコストと比較して結果として得られる１３２バイトのコストにより示されるように、これによりメモリコストが実質的に削減される。
【０１３１】
メモリ空間は約２３バイト節約される。
【０１３２】
参照は図４のグローバルテーブル内に格納されるが、変形例は、各々がＨＴＴＰヘッダのみを格納するグローバルテーブルのエントリに対するポインタをローカルインデックステーブル内に格納することを含んでもよい。
【０１３３】
図５は、接続数に依存してこれらの２つの方法に対して使用されたメモリ空間における差分（個別のインデックステーブル対グローバルテーブルに対する参照）を示す。接続数（すなわちローカルインデックステーブルの）が増加するにつれ、グローバルテーブルを使用することでメモリがより節約されることは、図５から明らかである。これは、より多くの接続があるほど、単一のストリングがいくつかの接続により使用されるために、いくつかのローカルインデックステーブルにおいてインデックス化されることがより多いためである。
【０１３４】
ローカルインデックステーブルが個別に又はグローバルテーブルを参照して実現されるかに関係なく、格納のためのメモリにおける対応するコストは、実質的に、全ての接続のためにデフレートスライディングウィンドウを小さくすることで達成されたメモリの節約により補償される。
【０１３５】
図６は、本発明の少なくとも１つの実施形態を実現するように構成された送信機又は受信機、あるいは双方の機能性を組み込むデバイスである処理装置６００を概略的に示す。処理装置６００は、マイクロコンピュータ、ワークステーション又は光ポータブルデバイス等のデバイスとすることができる。装置６００は、好ましくは以下のものが接続されている通信バス６１３を含む。
−  ＣＰＵで示されるマイクロプロセッサ等の中央処理装置６１１；
−  本発明を実現するためのコンピュータプログラムを格納するＲＯＭで示される読み出し専用メモリ６０７；
−  本発明の実施形態の方法の実行可能なコード、並びに本発明の実施形態に係る方法を実現するために必要な変数及びパラメータを記録するように構成されたレジスタを格納するＲＡＭで示されるランダムアクセスメモリ６１２；そして、
−  処理対象のデジタルデータが送信される通信ネットワーク６０３に接続された通信インタフェース６０２である。
【０１３６】
選択的に、装置６００は、以下の構成要素を更に含んでもよい。
−  本発明の１つ以上の実施形態の方法を実現するためのコンピュータプログラム及び本発明の１つ以上の実施形態の実現例の間に使用又は生成されたデータを格納するハードディスク等のデータ格納手段６０４；
−  ディスク６０６からデータを読み出すかあるいはデータを前記ディスクに書き込むように構成されるディスク６０６に対するディスクドライブ６０５；そして
−  キーボード６１０又は他のあらゆるポインティング手段を使用してユーザによりデータを表示し且つ／あるいはグラフィカルインタフェースとして機能する画面６０９。
【０１３７】
装置６００は、各々がマルチメディアデータを装置６００に供給するように入出力カード（不図示）に接続される種々の周辺装置、例えばデジタルカメラ６００又はマイク６０８等に接続されうる。
【０１３８】
通信バスは、装置６００に含まれるかあるいは接続された種々の要素間で通信及び相互運用性を提供する。バスの表現は限定されておらず、特に中央処理装置は、命令を装置６００のいずれかの要素に直接又は装置６００の別の要素を使用して通信するように動作可能である。
【０１３９】
ディスク６０６は、例えばコンパクトディスク（ＣＤ−ＲＯＭ）、書き換え可能又は書き換え不可能な、ＺＩＰディスク又はメモリカード等のあらゆる情報媒体及び概括的な言葉で、マイクロコンピュータ又はマイクロプロセッサにより読み出され、装置に一体化されるかあるいは一体化されず、場合によっては取り外し可能であり、且つ実行することで本発明に係る方法を実現できるようにする１つ以上のプログラムを格納するように構成されうる情報格納手段により置換されうる。
【０１４０】
実行可能なコードは、読み出し専用メモリ６０７、ハードディスク６０４、あるいは例えば上述したようなディスク６０６等の取り外し可能デジタル媒体上に格納される。一変形例によると、プログラムの実行可能なコードは、実行される前にハードディスク６０４等の装置６００の格納手段のうちの１つに格納されるために、インタフェース６０２を介して通信ネットワーク６０３を使用して受信されうる。
【０１４１】
中央処理装置６１１は、命令が上述の格納手段のうちの１つに格納される本発明に係る１つ又は複数のプログラムのソフトコードの命令又は部分の実行を制御及び指示するように構成される。電源投入時、不揮発性メモリに、例えばハードディスク６０４上にあるいは読み出し専用メモリ６０７に格納される１つ又は複数のプログラムは、１つ又は複数のプログラムの実行可能なコード、並びに本発明を実現するために必要な変数及びパラメータを格納するレジスタを含むランダムアクセスメモリ６１２に転送される。
【０１４２】
本実施形態において、装置は、本発明を実現するためにソフトウェアを使用するプログラム可能な装置である。しかし、あるいは本発明は、ハードウェア（例えば、特定用途向け集積回路、すなわちＡＳＩＣの形態）で実現されてもよい。
【０１４３】
次に、図７〜図１２を参照して、本発明に係る符号化方法及び復号化方法の種々の実施形態を説明する。ネットワークノードは、符号化機能及び復号化機能の一方又は双方を組み込むことができる。
【０１４４】
ノードが符号器及び復号器の双方として動作する場合、同一の接続内での符号化及び復号化のそれぞれに対する２つの別個のローカルインデックステーブルを使用することが好ましくなる。同様に、以下において説明されるような２つのグローバルテーブル及び２つの（余分な）ヘッダ名テーブルが使用されてもよい。これは、一般に、ＨＴＴＰ要求のヘッダがＨＴＴＰ応答のヘッダとは異なるためである。その後、各ローカルインデックステーブルは、同一の接続のために他から独立して処理される。
【０１４５】
しかし、特に同一の接続の要求及び応答内で多数のＨＴＴＰヘッダが類似することが観察される場合、符号化タスク及び復号化タスクのために単一のローカルインデックステーブルを使用することが依然として可能であることは、当業者には理解されるであろう。
【０１４６】
図７は、本発明の一実施形態に係るＨＴＴＰヘッダの符号化処理の一般的なステップを示すフローチャートである。ＳＰＤＹに従ってＨＴＴＰメッセージを処理する際に複数のＨＴＴＰヘッダが符号化されなければならないことは、本明細書において想起される。ＨＴＴＰヘッダ以外のあらゆる種類の情報項目に対しても実現できる。
【０１４７】
説明される処理では、１つの接続しか考慮しないものとする。当然、同一の処理は、他の接続のために動作する他の符号器により同時に実行されてもよい。ＨＴＴＰヘッダの初期の順序が復号器にとって重大及び重要でないヘッダの符号化も参照する。そのような初期の順序が復号器により維持される（すなわち、本発明が送信のために場合によってはこの順序を変更してもよいために検索される）べきである場合、本発明は、ストリーム内で、ヘッダの初期の順序を格納する追加情報（例えば、追加ヘッダ）を提供してもよい。例えばこの追加情報は、初期の順序内のインデックス化ヘッダの各々の厳密な位置を規定してもよく、他のヘッダ（すなわち、インデックス化なしの）は、相対的な初期の順序を維持したまま文字通り符号化される。
【０１４８】
本明細書において、インデックス化及び／又はバイナリ圧縮されるヘッダが考慮される。符号化ビットストリームに挿入される前にバイナリ表現にシリアル化されるだけのヘッダは、図１４〜図１８を参照して以下において説明されるバイナリ表現を使用して上述したように処理される。
【０１４９】
ステップ７００〜７３０間のループにより示されるように、符号化対象のメッセージの各ＨＴＴＰヘッダ上で繰り返すことにより、処理を開始する。
【０１５０】
ヘッダ毎に、ヘッダが既にインデックス化されているか否かを判定するために、現在の接続専用のローカルインデックステーブルにおいて探索が行われる（ステップ７１０）。
【０１５１】
図４ａのようなテーブルを使用する場合、この探索は、ＨＴＴＰヘッダが既にローカルインデックステーブルに存在するか否かを判定することから構成されてもよい。
【０１５２】
図４ｂに示されるようなグローバルテーブルを使用する場合、この探索は、ヘッダに対応するグローバルテーブルにおけるエントリを探索することと、ローカルインデックステーブルにおいて発見されたエントリに対する参照を探索することとを含む。
【０１５３】
ヘッダが既にインデックス化されている場合、そのインデックスは、ローカルインデックステーブルから検索され且つ第１のリストに格納される（ステップ７２０）。この第１のリスト（又はグループ）は、ローカルインデックステーブルにおいて既にインデックス化されているメッセージヘッダのインデックスを含むように構築される。
【０１５４】
一方、ヘッダがまだインデックス化されていない場合、第１のステップ７４０が実行され、ヘッダがローカルインデックステーブルにおいてインデックス化されなければならないか否かが判断され、且つ肯定的な判断の場合にはローカルインデックステーブルにおいてそのヘッダをインデックス化する（場合によっては適宜グローバルテーブルを参照して）ように実行される。そのような判断に対する基準は、例えば事前定義済みの最大メモリ空間と比較して、符号器において使用可能なメモリ空間に基づいてもよい。ローカルインデックステーブル（及び上述したように且つ以下において説明されるように含まれた他のあらゆるテーブル）が事前定義済みの最大メモリ空間に到達するまで、全てのヘッダはインデックス化されてもよい。そのような判断（すなわち、ヘッダがインデックス化されなければならないか否か）を示す情報は、図１５〜図１７に示されるように符号化ヘッダのバイナリ表現で提供される。これは、ローカルインデックステーブルを構築する際に復号器が符号器と同期されることを保証するためである。
【０１５５】
より具体的な戦略は、処理されるヘッダのインデックスを閾値（例えば、２５６個の文字）を下回るサイズを有するヘッダのみに制限してもよい。
【０１５６】
その後、第２のステップ７５０において、ヘッダが符号化される。２つの可能性が考えられる。
【０１５７】
探索は、処理されている現在のヘッダと同一のヘッダ名を有するエントリに対するローカルインデックステーブル（場合によってはグローバルテーブルを含む）において実行される。そのようなエントリが発見される場合（いくつかのエントリが発見される場合、最も類似する値を有するエントリが選択される）、そのようなエントリは、現在のヘッダをデルタ符号化するために参照として使用される。換言すると、現在のヘッダは、ローカルインデックステーブルにおいて選択されたエントリのインデックス（参照）及び選択されたエントリにより取られた値と現在のヘッダにより取られた値との差分を含むデータの集合に符号化される。
【０１５８】
図１６及び図１７を参照して以下において示されるように、差分は、当該２つの値の間の共通部分（例えば、２つのストリングの間の第１の同じ文字数）を示す第１のデータと、値の残りの部分のリテラル値（すなわち、共通部分より小さい現在のヘッダの値）を含む第２のデータとから構成されてもよい。２つの値が数（整数、フロート等）である場合、差分は、２つの値の間の数の差分を示す値のみで構成されてもよい。
【０１５９】
そのようなエントリが発見されない例において又はデルタ符号化が実現される場合、現在のヘッダは文字通り符号化される。
【０１６０】
次に、デフレート等の圧縮アルゴリズムは、データ又はリテラル値の集合のバイナリ表現に適用される（ステップ７６０）。以下において説明される図１５〜図１８は、種々の例のバイナリ表現を示す。
【０１６１】
ステップ７４０は、ローカルインデックステーブル内で、少なくとも１つの文字通り符号化されたヘッダを新しいインデックスと関連付けるか又はデルタ符号化されたヘッダを新しいインデックスと関連付けることにより、あるいはデルタ符号化のために参照として使用された既にインデックス化されているヘッダの置換でそのローカルインデックステーブルを更新する。
【０１６２】
増分インデックス化モードにおいて（すなわち、新しいエントリの加算により）、符号化ヘッダは、ローカルインデックステーブルに付加され、そのインデックスは、符号化ヘッダがローカルインデックステーブルに付加された前に既にテーブルにあるヘッダ数に等しい。
【０１６３】
置き換えインデックス化モードにおいては（すなわち、参照として使用されたエントリの置換では）、符号化ヘッダは、ローカルインデックステーブルにおいて既にインデックス化されているヘッダに対する参照を含み、ローカルインデックステーブルにおいてヘッダを置換する。
【０１６４】
ステップ７４０で現在符号化されているヘッダをインデックス化することを決定するデルタ符号化の場合、符号器は、増分インデックス化及び置き換えインデックス化のどちらにするかも判断しなければならない。そのような判断は、例えばヘッダ名に基づく統計的に規定された戦略に基づいてよい。
【０１６５】
そのような判断（すなわち、増分インデックス化又は置き換えインデックス化）を示す情報は、図１６及び図１７に示されるようなデルタ符号化されたヘッダのバイナリ表現で提供される。これは、ローカルインデックステーブルを構築する際に復号器が符号器と同期されることを保証するためである。
【０１６６】
ステップ７６０でデフレートコンテキストが各処理済みヘッダの間で維持されるため、符号化の結果は、ステップ７５０の発生時に判定された（場合によっては、デルタ符号化の場合には参照ヘッダのインデックス及び共通部分の定義に付与された）全てのリテラル値のシリアル化バイナリ表現に対してデフレート圧縮を適用することと同一である。その場合、リテラル値（インデックス及び共通部分の定義に付与された）が第２のリストに格納されてもよく、且つループ７００〜７３０を終了する場合にデフレート圧縮がその第２のリストのシリアル化バイナリ表現に対して実行されてもよいことは、当業者により理解されるだろう。その第２のリストのシリアル化バイナリ表現は、ステップ７５０に従って処理された各ヘッダのバイナリ表現の連結であってもよい。図１５〜図１８を参照して、各ヘッダに対するそのようなバイナリ表現を以下において説明する。
【０１６７】
ステップ７００〜７５０により全てのヘッダが処理されると、次のステップは、ステップ７２０の発生時に構築された第１のリストのインデックスを符号化することから構成される。そのような符号化は、インデックスのバイナリ表現を取得することから構成されてもよい。インデックスは、単一の値又は値の範囲として符号化される（すなわち、バイナリ表現に変換される）。図１４を参照して、ヘッダを符号化するインデックスに対するバイナリ表現の一例を以下において説明する。
【０１６８】
デフレート等の圧縮技術は、バイナリ表現に対しても使用可能である。その場合、第１のリストに対するシリアル化バイナリ表現及び第２のリストに対するシリアル化バイナリ表現は、共に連結されてよく、バイナリ圧縮することは、結果として得られるシリアル化バイナリ表現全体を圧縮するためにそれに対して実行されてもよい。
【０１６９】
一旦符号化されると、第１のリストのシリアル化バイナリ表現はステップ７７０にて送出される。一変形例においてインデックスヘッダセクションの終端にフラグを立てるように専用のコードが規定されてもよいが、一般に、インデックス化ヘッダ数が最初に符号化されてから各インデックスが符号化されうる。
【０１７０】
次に、圧縮された第２のリストのシリアル化バイナリ表現がステップ７８０で更に送出される。
【０１７１】
例えば、ヘッダインデックスの第１のリストは、リテラル値の第２のリストと連結されてもよいため、結果として得られるリストは、ステップ７７０及び７８０の双方を実行するように送出される（適切な符号化及び圧縮の後で）。
【０１７２】
この処理（及び対応する復号化処理）は、ローカルインデックステーブル内での構築及び探索に対するコストがデフレート圧縮を各インデックス化ヘッダに適用しないことによる節約による補償より多いため節約される。
【０１７３】
当然、インデックス化されるヘッダが多いほど、処理はより節約される。また、ローカルインデックステーブルを格納するために使用されたメモリがデフレートスライディングウィンドウを小さくすることで補償されてもよいため、更なるメモリ消費が制限される。
【０１７４】
図４ａ及び図４ｂの例において、ＨＴＴＰヘッダ全体は、ローカルインデックステーブルにおいて単一のエントリとしてインデックス化される。しかし、インデックス化ステップ７４０を実行する場合、例えばヘッダ全体、ヘッダの一部をインデックス化するか、あるいは基準に応じてヘッダを全くインデックス化しない場合、他のインデックス化戦略又は決定規則が実現されてもよい。
【０１７５】
あるインデックス化戦略によると、ヘッダ名は、ヘッダ値とは別にインデックス化されてもよい。特に、一般にヘッダ名がその値より冗長であるため、ヘッダ名インデックス化（すなわち、ヘッダ名のインデックス化）は、一般にヘッダ値インデックス（すなわち、ヘッダ値をインデックス化すること）より好まれる。例えば、「Ｄａｔｅ」ＨＴＴＰヘッダ値は、ある期間にわたり進化し且つインデックス化されなくてもよいという利点がある一方で、「Ｄａｔｅ」ＨＴＴＰヘッダ名は、経時変化しないままであるためにインデックス化されてもよい。「Ａｇｅ」ヘッダ又は「Ｃｏｎｔｅｎｔ−Ｌｅｎｇｔｈ」ヘッダ等のその特性に従う他のＨＴＴＰヘッダに対して、同様の検討事項が使用されてよい。
【０１７６】
ヘッダ名インデックス化を好む場合、ＨＴＴＰヘッダは、ＨＴＴＰ名及びリテラルＨＴＴＰ値をインデックス化するインデックスに符号化されてもよい。これは、上述したようなデルタ符号化である。
【０１７７】
以下において説明されるように差分値が文字通り符号化されるため、デルタ符号化は、第２のリストを形成するヘッダに適用されることが好ましい。別の実施形態において、第１のリストを形成するヘッダがインデックスを使用して符号化されるため、デルタ符号化はそれらに適用される。
【０１７８】
知られているように、メモリは、ローカルインデックステーブル（及び使用される場合にはグローバルテーブル）を構築するための制約を構成してもよい。従って、特にヘッダ表現を格納するために割り当てられたテーブルエントリ数及びメモリサイズを制限することにより、インデックステーブルにより使用されたメモリサイズを制限することが決定されてもよい。一般にインデックステーブルは、５１２バイト又は１０２４バイトのバッファに制限されうる。その場合、ステップ７４０で新しいヘッダ（又はその一部）をインデックス化するか否かの判断は、既に使用されている割り当てられたメモリの割合に基づいて行われてよい。
【０１７９】
そのように制限されたバッファサイズにより、更なるメモリコストが制限され、一般に結果は、小さなバイナリ表現を有するヘッダ、すなわち一般に６４個より少ない文字を有するヘッダのみをステップ７４０でインデックス化することで改善される。
【０１８０】
その方法の改良点は、大きなバイナリ表現を有するヘッダを漸次インデックス化することを含んでもよい。換言すると、ヘッダのいくつかの出現が発生し且つ処理される時、そのヘッダは漸次インデックス化される。
【０１８１】
例えば、大きなバイナリ表現を有するそのヘッダが遭遇される第１の時間、実際には最初のＮ個の文字（例えば、Ｎ＝６４）のみがインデックステーブルに格納され、インデックスと関連付けられる。その第１の出現に対して、残りの文字は文字通り符号化される。同一のヘッダ（第２の出現）が遭遇される第２の時間、ヘッダ全体が十分な回数発生する場合にそれが格納されるまで、インデックステーブルは、例えば同一のインデックスに対して格納するための文字の数（例えば、２Ｎ）を増加することで更新される。
【０１８２】
別の戦略によると、インデックスフラグは、バイナリ圧縮された各リテラルヘッダと関連付けられて、それがローカルインデックステーブルにおいてインデックス化されなければならないことを示してもよい。従って、復号器は、自身がまだ認識していないあらゆる独自のインデックス化戦略を通知されてよい。例えば、ヘッダのリテラル符号化は、ヘッダをインデックステーブルに追加するかを復号器に知らせるフラグを含む。
【０１８３】
独自の戦略は、インデックス化対象のヘッダ名の事前コンパイルリスト（ヘッダ名テーブル）又はインデックス化対象でないヘッダ名の事前コンパイルリストの符号器による知識等の種々の状況を範囲に含んでもよい。
【０１８４】
例えばリストは、いくつかの接続の間で共有可能なヘッダを含んでよい。一般にクッキーに関連するヘッダは、いくつかの接続の間で共有されなくてもよく且つインデックス化されなくてもよいという利点がある。「Ｓｅｔ−Ｃｏｏｋｉｅ」ヘッダは、その値が変化することが予想されるためにインデックス化されなくてもよいという利点がある。いずれにせよ、インデックス化されないヘッダは、一般に、デフレート圧縮ステップ７６０により効率的に圧縮される。
【０１８５】
別のインデックス化戦略は、いくつかのヘッダがある期間にわたり限られた妥当性を有することに基づいてもよい。例えばこれは、メッセージが送出される日付を含むが精度は二の次の「Ｄａｔｅ」ヘッダの場合である。
【０１８６】
コンピュータが１秒間に多くのメッセージを送出できるため、そのような日付に基づくヘッダをインデックス化することは効率的でありうる。しかし、これは、同一秒数内に生成された少数のメッセージに対してのみ有用となる。いくつかのメッセージは、ウェブページに関連する全てのリソース（スタイル、ＪａｖａＳｃｒｉｐｔ、画像．．．）を取り込むクライアント又はクライアントに応答する際のサーバにより迅速に出されうる。
【０１８７】
ある期間にわたり限られた妥当性をサポートするために、新しいヘッダは、インデックス化されたデルタとしてフラグを立てられてもよい。これは、インデックスに加えて、インデックスに対応するヘッダに対する差分（例において秒で）に関する情報与えることを意味する。これは既に上述されている。
【０１８８】
その場合、インデックスレベルフラグは、ＨＴＴＰヘッダと関連付けられる。前記インデックスレベルフラグは、ＨＴＴＰヘッダに依存して、ＨＴＴＰヘッダがローカルインデックステーブルにおいて対応する情報項目と同一のＨＴＴＰ名及びＨＴＴＰ値を有することを示す第１の完全なインデックス化状態、又はＨＴＴＰヘッダがローカルインデックステーブルにおいて対応する情報項目と同一のＨＴＴＰ名であるが異なるＨＴＴＰ値を有することを示す第２の部分的なインデックス化状態を取る。値の差分は、更に文字通り符号化及び送信されてもよい。
【０１８９】
上述したように、これは、第１のリストのヘッダ又は第２のリストのヘッダに適用されてもよい。
【０１９０】
従って、「部分的なインデックス化状態」は、ヘッダ値の差分が文字通り復号化されなければならないことを復号器に示す。
【０１９１】
図７の上述の例において更に説明されるように、インデックス化ヘッダは、符号化ビットストリーム内で文字通り且つデルタ符号化されたヘッダに先行する。これはいくつかの利点を提供する。
【０１９２】
例えばいくつかのヘッダは、ネットワークノードがＨＴＴＰ要求のＵＲＬ値のような正当な処理エンティティにメッセージを配布するために非常に重要だろう。また、ＨＴＴＰキャッシングヘッダはプロキシに対して有用である。一般にこれらのヘッダは、非常に冗長であるため、迅速にインデックス化される。最初にインデックス化ヘッダを提供することにより、殆どの場合、ネットワークノードは、デフレート伸張及びヘッダストリング構文解析の技術を使用する必要なく最も重要なヘッダに迅速にアクセスできる。また、インデックス化ヘッダを復号化することは、ビットストリームからいくつかのバイトを検索することで実行されうる。それにより、ビットストリームの小さな部分にアクセスすることで多数の復号化ヘッダを取得することが可能になる。
【０１９３】
しかし、変形例が使用されてよい。例えば、必要とされるバッファリングを制限するために、文字通り且つデルタ符号化されたヘッダは、最初にデフレートストリーム及び次に送出されるインデックス化ヘッダとして送出されうる。その場合、特定のコードが文字通り且つデルタ符号化されたヘッダセクションを終了することにより、復号器は、インデックス符号化されたヘッダセクションに迅速に切り替わることができる。
【０１９４】
上述したように、インデックス化又は圧縮（例えば、デフレート）されないヘッダの第３の集合は、インデックス化ヘッダ及び文字通り且つデルタ符号化されたヘッダの前に符号化ビットストリームに更に挿入されてもよい。ローカルインデックステーブル又はバイナリデフレート伸張における探索が必要とされないため、これは、復号器に対するいくつかのヘッダへの容易で迅速なアクセスを提供するためである。
【０１９５】
図７は、インデックス符号化がリテラル／デルタ符号化とは別にされる処理の一例を更に示す。これにより圧縮を改善できるが、それは、インデックス及び／又はリテラル値に対して少量のバッファリングしか更に必要としない。一変形例によると、ヘッダは、処理されるとすぐに符号化及び送出されてもよい。
【０１９６】
最後に、フラグは、ヘッダがインデックステーブルに追加されなければならないことを復号器に示すために、文字通り且つデルタ符号化された各ヘッダの一部として符号化されうる。代替例は、符号器及び復号器の双方が、インデックス化規則を厳密に認識しているために、インデックス化決定情報を通信する必要なくインデックステーブルを同期させたままにすることである。
【０１９７】
図１３は、本発明を使用して取得可能な種々の符号化ビットストリームを概略的に示す。
【０１９８】
図１３ａにおいて、ビットストリームは、第１のリストのインデックスのシリアル化バイナリ表現を含む第１のバイナリ部分１３１０と、第２のリストのヘッダの（デフレート）圧縮されたシリアル化バイナリ表現を含む第２のバイナリ部分１３２０とを含む。本実施形態において、第１のリストのインデックスのシリアル化バイナリ表現は、（デフレート）圧縮されなくてもよい。当然、一変形例によると、第１のバイナリ部分及び第２のバイナリ部分は反転されてもよい。
【０１９９】
図１３ｂにおいて、ビットストリームは、第１のリストのインデックスの（デフレート）圧縮されたシリアル化バイナリ表現を含む第１のバイナリ部分１３１０’と、第２のリストのヘッダの（デフレート）圧縮されたシリアル化バイナリ表現を含む第２のバイナリ部分１３２０とを含む。２つのリストに対するシリアル化バイナリ表現は、（デフレート）圧縮される前に連結される。当然、一変形例によると、第１のバイナリ部分及び第２のバイナリ部分は反転されてもよい。
【０２００】
図１３ｃ及び図１３ｄの例は図１３ａ及び図１３ｂの例に類似するが、（デフレート）圧縮又はインデックス化されないヘッダのシリアル化バイナリ表現を含む第１のバイナリ部分及び第２のバイナリ部分に連結された更なるバイナリ部分１３００を有する。当然、一変形例によると、更なるバイナリ部分は、第１のバイナリ部分及び第２のバイナリ部分と比較してビットストリームにおいて別の場所を取ってもよい。
【０２０１】
図８は、本発明の一実施形態に係るＨＴＴＰヘッダの復号化処理の一般的なステップを示すフローチャートである。特に、図８は、図７の符号化処理に対応する復号化処理である。
【０２０２】
これは、復号器が符号器と同様に動作することを意味する。例えば符号器及び復号器の双方は、使用される場合に同一のローカルインデックステーブル及び同一のグローバルテーブルを有するように同一のインデックス化戦略を使用する。
【０２０３】
符号化処理と同様に、複数のヘッダは復号化する際に処理されなければならない。図８の例において、符号化インデックス化ヘッダは、文字通り且つデルタ符号化されたヘッダに先行して取得される。
【０２０４】
予備のステップ（不図示）は、シリアル化されているだけの、すなわち符号化又はバイナリ圧縮されていないヘッダを含むビットストリームの第１の部分を構文解析すること及び読み出すことから構成されてもよい。この予備のステップは、メッセージヘッダリストに追加されたヘッダの第１の集合を提供する。
【０２０５】
図８の第１のステップは、ステップ８００及び８１０によりインデックス化ヘッダを復号化することから構成される。
【０２０６】
アルゴリズムは、復号化対象の残りのインデックス化ヘッダがあるかを確認することでステップ８００で開始する。このテストは、ヘッダ数を復号化すること、あるいは復号化対象の残りのヘッダがあるかを知らせるコード又はフラグを復号化することに基づいてもよい。
【０２０７】
インデックス化ヘッダが復号化される度に、復号器は、ローカルインデックステーブルを使用してビットストリームからヘッダインデックスを復号化する（ステップ８１０）。ヘッダインデックスは、図１４に示されるようにバイナリ表現から読み出されてもよい。ヘッダは、ビットストリームから復号化されたそのインデックスを使用してインデックステーブルから検索される。
【０２０８】
その後、復号化ヘッダはメッセージヘッダリストに追加される。
【０２０９】
ヘッダの構文解析（ヘッダ名とヘッダ値の分離、専用の構造におけるヘッダ値の構文解析）が実際には必要とされないため、この復号化ステップは高速且つ単純である。従って、復号化速度は向上する。
【０２１０】
全てのインデックス化ヘッダが復号化されると、ビットストリームの文字通り／デルタ符号化されたセクションは、デフレートアルゴリズムを使用して伸張され（ステップ８２０）、取得されたバイナリストリームは、構文解析されて文字通り又はデルタ符号化されたヘッダの各々を処理する（ステップ８３０〜８６０）。
【０２１１】
復号化は、伸張バイナリストリームから復号化するためにバイナリデータが残るかを確認することで開始する（ステップ８３０）。
【０２１２】
その場合、次の符号化ヘッダは、ヘッダ名及びその値を検索することで伸張バイナリストリームから復号化される（ステップ８２０）。図１５〜図１７に示されるような符号化ヘッダのバイナリ表現のフラグは、符号化ヘッダがデルタ復号化されなければならないか（すなわち、ローカルインデックステーブルにおいて既にインデックス化されているヘッダを部分的に参照することで）、あるいは文字通り復号化されなければならないかを復号器が判定するのを支援する。
【０２１３】
デルタ符号化される場合、ヘッダは、ローカルインデックステーブルにおいて参照からヘッダ名を検索すること及び差分値を取得することにより復号化される。
【０２１４】
構文解析又は復号化されると、取得されたヘッダは、メッセージヘッダリストに追加される。
【０２１５】
その後テストが実行され、この取得されたヘッダがインデックス化されなければならないか否かを確認する（ステップ８５０）。復号器は、生成されたビットストリーム情報に基づいて符号器により決定されたインデックス化戦略を実現する。符号器がインデックスフラグをビットストリームに追加した特定の場合において（図１５〜図１７の対応するフラグを参照）、そのフラグは、ビットストリームにおいて復号器により探索され、増分インデックス化と置き換えインデックス化のどちらかのインデックス化モードに従って復号化ヘッダがインデックス化されなければならないか否かを判定する。
【０２１６】
復号化ヘッダは、インデックス化されなければならない場合、新しいエントリ（増分インデックス化）として又はデルタ復号化において参照として使用されたエントリ（置き換えインデックス化）の置換でローカルインデックステーブルに追加される（ステップ８６０）。
【０２１７】
復号化ヘッダがインデックス化されなくてもよい場合又はこのインデックス化ステップ８６０の後で、復号化対象の後続のバイナリデータがステップ８３０で考慮される。
【０２１８】
全てのヘッダが復号化されると、完全なメッセージヘッダリストは、それを処理するアプリケーションに提供される（ステップ８７０）。当然、ヘッダの順序が符号化ビットストリームにおいて規定されている場合、メッセージヘッダリストは、アプリケーションに提供される前に前記順序に従って再順序付けされる。
【０２１９】
上述したように、いくつかのインデックス化戦略により、ある特定のヘッダ表現をグローバルテーブルを通して復号器又は符号器である同一のネットワークノードの種々の接続の間で共有できるようになる。これにより、制限された処理コストで種々の接続により使用されたローカルインデックステーブルのメモリコストを削減できるようになる。すなわち、グローバルヘッダテーブルは、接続のプールに対して規定され、全てのインデックス化ヘッダを格納してもよい。次に、接続毎に、特定のインデックステーブルは、その所定の接続のためにインデックス化されている厳密なヘッダに対する参照を格納する。
【０２２０】
図４ｂは、対応する２つの接続のために共有グローバルテーブル及び２つのローカルインデックステーブルによるそのような戦略を示す。
【０２２１】
次に、図９を参照して、共有グローバルテーブルに基づく符号化処理を説明する。
【０２２２】
共有グローバルテーブルの使用に反して、デフレートバッファが継続的に更新されるため、いくつかの接続の間でデフレートバッファを共有するのは困難である。
【０２２３】
このような状況において、メモリコストを共有するために共有グローバルテーブルを使用することにより、デフレートウィンドウを小さくすることで、インデックステーブルを通して非常に良好な圧縮率を維持しつつ、速度のゲイン及びメモリの節約を達成することが可能になる。
【０２２４】
図７と比較して、ヘッダインデックス化ステップ７４０及びヘッダインデックス検索ステップ（ステップ７１０及び７２０）において、異なる方法が採られる。
【０２２５】
詳細には、符号化処理は、符号化対象のヘッダを検索することで開始する（ステップ９００）。
【０２２６】
次にヘッダは、共有グローバルテーブルにおいて探索される（ステップ９０５）。高速に探索する従来の探索機構が使用されてもよい。
【０２２７】
ヘッダは、発見されない場合にリテラルヘッダとして又はデルタ符号化を使用して符号化される（ステップ９２０〜９４０）。すなわち、ヘッダは、インデックスが判断される場合に共有グローバルテーブルに追加され（ステップ９２０）、その共有グローバルテーブルに格納されたヘッダ表現に対する参照は、当該接続（本明細書において処理されているヘッダを含むメッセージが属する接続−ステップ９３０）専用のローカルインデックステーブルに追加される。その後、ヘッダは、符号化され（参照ヘッダを使用して文字通り又はデルタ）、文字通り且つデルタ符号化されたヘッダの第２のリストにおいてデフレート圧縮される（ステップ９３５及び９４０）。
【０２２８】
ヘッダが共有グローバルテーブルにおいて発見される場合、関連ヘッダ参照（すなわち、共有グローバルテーブルにおけるグローバルインデックス）は、ステップ９５０で検索される。この参照により、接続専用のローカルインデックステーブル内のその参照の存在をチェックすることで、当該接続のためにヘッダが既に符号化されているかを高速に確認できる（ステップ９５５）。
【０２２９】
ヘッダは、接続のためにまだ符号化されていない場合、インデックス化が判断される場合に接続専用のローカルインデックステーブルにおいてインデックス化され（ステップ９３０）、適宜文字通り又はデルタ符号化され、文字通り且つデルタ符号化されたヘッダの第２のリストにおいて圧縮される（ステップ９３５及び９４０）。
【０２３０】
ヘッダが接続のために既に符号化されている場合、ヘッダインデックスは、接続専用のローカルインデックステーブルから検索され、インデックスの第１のリストに格納される（ステップ９６０）。
【０２３１】
全てのヘッダが処理されると、第１のリストのインデックスは、シリアル化バイナリ符号化表現に符号化され、連結された第１のリスト及び第２のリスト（すなわち、それらのシリアル化バイナリ表現）は、ステップ７７０及び７８０と同様に送出される（ステップ９８０及び９９０）。特に、ステップ９４０のデフレート圧縮は、ステップ９７０の後で、文字通り且つデルタ符号化された全てのヘッダのシリアル化バイナリ表現に対して一度だけ選択的に実行されてもよい。
【０２３２】
図９の一変形例において、ステップ９０５で行われた探索は、接続専用のローカルインデックステーブル内でのみ実行されてよい。その場合、ヘッダインデックスは、接続専用のローカルインデックステーブルから直接検索される。例えば、ローカルインデックステーブルが、共有グローバルテーブルに対するポインタを使用してそのグローバルテーブルに実際に格納されるヘッダに対する参照のみを含む場合、これは、ローカルインデックステーブル内で探索されたヘッダに対するポインタを探索することで実行されてもよい。ポインタが発見されない場合、探索されたヘッダが共有グローバルテーブルに既に存在しているか否か、従って探索されたヘッダがローカルインデックステーブルに挿入される際にそのグローバルテーブルに挿入されるか否かを判定する必要がある。その結果、ステップ９０５のこの変形例は、ヘッダがローカルインデックステーブルに挿入される場合は常に共有グローバルテーブルにおいて更なる探索を必要とする。
【０２３３】
特にそのグローバルテーブルを小さくする必要がある場合、この代替例は、共有グローバルテーブルの管理に対して影響を及ぼす。その場合、エントリは、グローバルテーブルから容易に除去されないだろう。１つの可能性は、図１１のグローバルテーブルの移行を参照して以下において説明されるように、あるグローバルテーブルから別のグローバルテーブルに切り替えてある時点で古いグローバルテーブルを除去すること、又は図１２のグローバルテーブルの最適化を参照して以下において説明されるように、しっかりと同期された共有グローバルテーブル及びローカルインデックステーブルを維持することである。
【０２３４】
別の変形例において、共有グローバルテーブルは、共有可能なヘッダだけが実際にグローバルテーブルに格納されるように管理されてもよい。これは、グローバルテーブルにおけるヘッダがいくつかの接続を介して再利用される場合にのみメモリが節約されるためである。
【０２３５】
特に、頻繁に共有可能なヘッダのみがそのグローバルテーブルに実際に格納されうる。例えば共有可能なヘッダは、ＨＴＴＰ標準に基づいて復号器及び符号器の双方により事前に判定され且つ認識されてもよい。それらは、以下において規定される専用ヘッダ以外のヘッダであってもよい。これにより、共有可能に格納される価値のあるヘッダを用いてメモリの使用を最適化することが可能になる。
【０２３６】
管理の種々のレベルは、他のヘッダ（すなわち、共有されるものとして判定されない）に対して適用されてもよい。
【０２３７】
例えば、専用ヘッダ（例えば、クッキー又は機密データ、「Ｈｏｓｔ」又は「Ｒｅｆｅｒｅｒ」等の接続専用のデータ等）は、文字通り符号化されてからデフレート圧縮されてもよい。
【０２３８】
別の例において、２レベルインデックス化機構が使用されることにより、頻繁であり且つ共有されるヘッダが共有グローバルテーブルに格納される一方で、頻繁であるが共有されない（すなわち、専用の）ヘッダは、接続専用のローカルインデックステーブルに格納される。他のヘッダはインデックス化されない。その場合、ローカルインデックステーブルは、グローバルテーブルを参照することでインデックス化されたヘッダと、ローカルインデックステーブル内でのみインデックス化されたヘッダとを含む。また、ローカルインデックステーブルにおいてのみ又はグローバルテーブルを参照することでヘッダをインデックス化することを決定することは、本実施形態において判定されたそのヘッダの頻度に依存する。
【０２３９】
専用の共有可能な且つ／又は頻繁なヘッダは、符号器（及び必要であれば復号器）に提供された事前定義済みのリスト自体において規定されてもよい。
【０２４０】
図１０は、共有グローバルテーブルに基づいて対応する復号化を示すフローチャートである。図７の適応例である図９と同様に、図１０の処理も図８の適応例である。
【０２４１】
しかし、新たにインデックス化された全てのヘッダに対してグローバルテーブルにおいて更なる探索が実行され、これが復号器においてコストがかかりうるため、図１０の処理は、図８の処理よりも多くの処理を必要とする。これは、共有グローバルテーブルを使用して又は使用せずに１つのヘッダ探索のみが必要とされる符号器における処理とは対照的である。これにより、処理速度を犠牲にしてメモリを節約できる。これらの欠点を緩和するために、インデックス化基準は、いくつかのヘッダ、例えば共有可能なヘッダ及び／又は上述したようにいくつかの接続において最も頻繁なヘッダのみをインデックス化するように限定されてもよい。
【０２４２】
インデックス化ヘッダは、一般にビットストリームに最初に入れられるために最初に復号化される（ステップ１０００及び１０１０、シリアル化されているだけの、すなわち符号化又はバイナリ圧縮はされていないヘッダを取得するあらゆる予備のステップに関係なく）。復号器は、ビットストリームからヘッダインデックスを復号化する。ヘッダインデックスは、図１４に示されるようにバイナリ表現から読み出されてもよい。次にヘッダインデックスは、復号化ヘッダインデックスにより接続専用のローカルインデックステーブルにおいて直接ヘッダを発見するか、あるいは接続専用のローカルインデックステーブルにおいてグローバルテーブル及び復号化ヘッダインデックスと関連付けられた参照を使用してヘッダを発見する。その後、復号化ヘッダはメッセージヘッダリストに格納される。
【０２４３】
これは、接続専用のローカルインデックステーブルがヘッダ表現又はグローバルテーブルに格納されるその表現に対する参照を格納できるためである。グローバルテーブルは、ストリングとして又は構文解析された表現でヘッダを直接格納してもよい。
【０２４４】
次に、文字通り／デルタ符号化されたヘッダは、ステップ１０２０〜１０９０により復号化される。
【０２４５】
ビットストリームは、バイナリストリームを取得するために最初にデフレートを使用して伸張される（ステップ１０２０）。
【０２４６】
その後、より多くのデータが使用不可能になるまで（テスト１０３０）、伸張バイナリストリームは、図１５〜図１８に示されるバイナリ表現に従ってそれを構文解析するように処理される。バイナリデータが使用可能である限り、ヘッダは最初に構文解析される。フラグは、符号化ヘッダがデルタ復号化又は文字通り復号化されなければならないかを判定するために読み出される／ヘッダ名及びヘッダ値は、参照ヘッダを使用して取得され（デルタ符号化の場合）、結果として得られる復号化ヘッダは、メッセージヘッダリストに追加される（ステップ１０５０）。
【０２４７】
ステップ８５０と同様に、ヘッダをインデックス化するための戦略は、例えばバイナリ表現で対応するフラグを読み出すことでステップ１０６０で判定される。
【０２４８】
ヘッダがインデックス化されなくてもよい場合、復号化処理は別のヘッダを継続する（ステップ１０３０に戻る）。
【０２４９】
ヘッダがインデックス化されなくてはならない場合、ステップ１０７０でヘッダが既にグローバルテーブルにあるかがテストされる。
【０２５０】
ヘッダは、まだグローバルテーブルにない場合、ステップ１０８０で新しいエントリとして又は使用された参照ヘッダの置換でグローバルテーブルに追加され、これは、その新しいヘッダと関連付けられた参照が作成されることを意味する。特に、殆どの場合、ヘッダは新しいエントリとして追加される。
【０２５１】
ヘッダが既にグローバルテーブルにある場合又はステップ１０８０の後で、ヘッダは、対応するインデックスをグローバルテーブルヘッダエントリに対する参照と関連付けることにより、ステップ１０９０で接続専用のローカルインデックステーブルに追加される。
【０２５２】
全てのバイナリデータが処理されると、復号化ヘッダ（すなわち、場合によっては符号器によりビットストリームにおいて規定された順序に従って再順序付けされたメッセージヘッダリスト全体）は、例えばアプリケーションへの出力として提供される（ステップ１０４０）。
【０２５３】
図１１及び図１２を参照して以下において説明される本発明の特定の実施形態において、共有グローバルテーブルの使用の最適化は、メモリ消費を減少する目的で行われる。
【０２５４】
共有グローバルテーブルがいくつかの接続の寿命にまたがるため、そこにおけるいくつかのヘッダは、所定の接続が解除される場合に関係がなくなるだろう。
【０２５５】
共有グローバルテーブルは、使用されるヘッダ数が実際には増加しないかもしれないが増大し続ける。従って、共有グローバルテーブルにおけるヘッダが既存の接続に関連したままであることを保証し、且つ現在の接続とはもう関係ないグローバルテーブルヘッダから除去する必要性がある。図１１及び図１２の最適化は、符号器においてこの問題に対処する。当然、同様の最適化が対応する復号器において行われるべきである。
【０２５６】
図１１は、現在の接続を現在のグローバルテーブルから新しいグローバルテーブルに移行するステップを示すフローチャートである。新しいグローバルテーブルは、現在のグローバルテーブルとは異なり使用されていないヘッダがない。
【０２５７】
この処理は、所定の時間においてある共有グローバルテーブルから別のグローバルテーブルに切り替えることに基づく。すなわち、ある時点において、共有グローバルテーブルが作成され、全ての新しい接続が新しい共有グローバルテーブルを使用する一方で、古い接続は、初期の共有グローバルテーブルを用いたままである。古い共有グローバルテーブルは、小さい数に減少する接続数を有し、その時間において、残りの接続は新しい共有グローバルテーブルに移行される。古い共有グローバルテーブルは、削除されてメモリ空間を解放する。
【０２５８】
この方法は、グローバルテーブルにより使用されたメモリ全体がある期間にわたり増大し続けないことを保証する。
【０２５９】
図１１の処理は、ローカルインデックステーブル及び現在の共有グローバルテーブルに基づいてメッセージを符号化するネットワークノードにより受信されたネットワーク事象を待つことにより、ステップ１１００で開始する。全ての現在の接続は、同一の現在の共有グローバルテーブルＡにリンクされると仮定され、それは、それらの接続専用のローカルインデックステーブルが全てそのグローバルテーブルＡを示すことを意味する。
【０２６０】
入力ネットワーク事象が新しい接続である場合（ステップ１１１０でのテスト）、現在の共有グローバルテーブルがリフレッシュされる必要があるか否かが最初に確認される（ステップ１１１５）。リフレッシュ基準は、種々の情報、すなわち現在のグローバルテーブルの寿命及び／又はグローバルテーブルが作成されてから解除された接続数等に基づいてもよい。また、現在のグローバルテーブルが既に移行段階にある（以下において説明されるように、新しいグローバルテーブルが既に作成されていることを意味する）場合、現在のグローバルテーブルをリフレッシュする必要はない。
【０２６１】
グローバルテーブルがリフレッシュされる必要がある場合、新しいグローバルテーブルＢがステップ１１２０で作成される。それは、現在共有されているグローバルテーブルに関連する少なくとも１つの基準に依存して、新しい接続に対する要求を受信すると新しいグローバルテーブルが作成されることを意味する。このグローバルテーブルＢは、空のテーブルとして初期されてよく、あるいは一般に使用されるヘッダで事前に満たされてよい。次に、新しい接続（受信される事象に対応する）は、ステップ１１２５でその新しいグローバルテーブルにリンクされ、それは、対応する接続専用のローカルインデックステーブルがインデックスをその新しいグローバルテーブルＢ（現在のグローバルテーブルＡではなく）に対する参照と関連付けることを意味する。
【０２６２】
受信したネットワーク事象が、移行が進行している間の新しい接続（ステップ１１１０でのテスト）又は接続の終了（ステップ１１３０でのテスト）である場合、ヘッダが処理される必要があるか否かがステップ１１５０で確認される。２つのグローバルテーブルＡ及びＢが同時に存在している場合、移行は進行中である。
【０２６３】
ヘッダが処理される（ステップ１１５０で「ｎｏ」を出力する）必要がない場合、受信したネットワーク事象に捧げられた処理は、ステップ１１００に戻ることで新しいネットワーク事象を待つ前にステップ１１７５で実行される。
【０２６４】
ヘッダが処理されなければならない場合、そのヘッダは、接続専用のローカルインデックステーブルに基づいて符号化され（インデックスは、既に存在している場合に接続がリンクされるグローバルテーブルを使用して検索される）、リンクされたグローバルテーブル及び接続専用のローカルインデックステーブルは、処理済みのヘッダが挿入される必要がある場合に更新される（ステップ１１５５）。
【０２６５】
選択的なステップ（ステップ１１６０）は、グローバルテーブルＡ及びＢにより使用された合計メモリを被覆するために実行されてもよい。すなわち、処理済みのヘッダがインデックス化されてテーブルに追加されると合計メモリが所定の閾値を上回る場合（テスト１１６０）、いくつかのエントリは、メモリ消費を減少するためにグローバルテーブルＡから除去されてもよい（ステップ１１７０）。除去可能なエントリの例は、最も古いエントリ、最も頻繁に使用されないエントリ等である。当然、エントリがグローバルテーブルから除去される場合、グローバルテーブルに対する参照が存在しないため、ローカルインデックステーブルにおける対応するエントリも除去されなければならない。
【０２６６】
その後、次のネットワーク事象を待つステップ１１００に戻る。
【０２６７】
受信したネットワーク事象が接続事象の終了であり且つ移行が進行中である（ステップ１１３０で検出された）場合、少数の接続だけが現在のグローバルテーブルＡにリンクされるか否かがステップ１１３５で確認される。少数は、例えば接続中の５％より少ない所定の数の接続を意味するのが有利である。
【０２６８】
このような場合、これらの全ての接続（グローバルテーブルＡにリンクされた）は、新しいグローバルテーブルＢに移行される（ステップ１１４０）。すなわち、これは、現在のグローバルテーブルＡから現在の接続により使用されたエントリを除去することと、除去されたこれらのエントリを新しいグローバルテーブルＢに追加することと、それから前記現在共有されているグローバルテーブルをメモリから削除することとを含む。当然、移行されたこれらの接続のローカルインデックステーブルは、ここで削除されたグローバルテーブルＡの削除されたエントリではなく、新しいグローバルテーブルＢに移行されたエントリを示すように更に更新されなければならない。これらのエントリの重複を回避しつつ、除去されたエントリをＢに追加してもよい。すなわち、除去されたエントリは、Ｂに既に存在している場合にはそこに追加されないが、移行された接続のローカルインデックステーブルは、ここでこの既に存在しているエントリを示すように更新される。
【０２６９】
処理のこの部分において、現在の接続を移行することは、現在の接続を終了する要求を受信するとそのようにトリガされる。
【０２７０】
この処理の利点は、移行段階処理が、時間的に制限され、ネットワークノードが使用可能な処理機能を有する場合に実行されてもよいことである。特に、ステップ１１４０は非同期に実行されてもよい。
【０２７１】
次に、図１２を参照して異なる方法を説明する。図１２において、グローバルテーブルを作成及び削除するのではなく、現在のグローバルテーブルは、現在の接続と同期され続け、すなわち、グローバルテーブルにおける全てのヘッダは現在の接続により使用される（すなわち、ローカルインデックステーブルにより参照される）。現在のグローバルテーブルが長期間にわたり接続と自然に同期されたままでない危険性がある場合、そのような方法は図１１の方法にとって好ましい。
【０２７２】
図１２の方法において、グローバルテーブルにおける各インデックス化ヘッダは、そのインデックス化ヘッダを使用して接続数をカウントする接続カウンタと関連付けられ、メモリ節約動作は、インデックス化ヘッダの接続カウンタに基づいて実行される。特に、メモリ節約動作は、対応する接続カウンタがゼロであるグローバルテーブルから何らかのインデックス化ヘッダを除去することを含む。これは、グローバルテーブルが現在の接続により使用されるヘッダのみを格納することを保証する。従って、グローバルテーブルは現在の接続の状態と同期される。
【０２７３】
処理は、ネットワークノードにより受信されたネットワーク事象を待つことでステップ１２３５で開始してもよい。
【０２７４】
受信した事象に基づいて、新しいヘッダが処理されなければならないか否かがステップ１２００で最初に確認される。
【０２７５】
新しいヘッダが処理されなければならない場合、新しいヘッダがインデックス化されるべきか否かがステップ１２１０で確認される。
【０２７６】
新しいヘッダがインデックス化されるべきである場合、その表現がグローバルテーブルに既にあるか否かがステップ１２２０で確認される。
【０２７７】
その表現が既に存在している場合、グローバルテーブルにおけるそのヘッダのエントリと関連付けられたカウンタは、ステップ１２３０で増分される。カウンタは、対応するヘッダを使用する接続数を反映するために使用される。このような状況において、それは「接続カウンタ」と命名される。
【０２７８】
その表現が存在しない場合、ヘッダはグローバルテーブルに追加され、その接続カウンタは、１だけ増分される（ステップ１２３０）前に０に初期化される（ステップ１２２５）。
【０２７９】
ステップ１２３０の後で、次のネットワーク事象を待つステップ１２３５に戻る。
【０２８０】
受信した事象が処理対象の新しいヘッダではない場合、それが接続の終了事象であるか否かが確認される（ステップ１２４０でのテスト）。
【０２８１】
それが接続の終了事象である場合、接続は、そのように停止されている（対応するローカルインデックステーブルが近い将来削除されることを意味する）。停止された接続専用のローカルインデックステーブルにおいてインデックス化された全てのヘッダは、削除の前に処理される。
【０２８２】
そのローカルインデックステーブルにおけるエントリ毎に（テスト１２５０）、グローバルテーブルにおける対応する接続カウンタは、ステップ１２５５で１だけ減分される。「対応する接続カウンタ」は、グローバルテーブルにおいてローカルインデックステーブルの当該エントリに示された参照を有するエントリと関連付けられたカウンタである。
【０２８３】
接続カウンタが０になる場合（テスト１２６０）、ヘッダ表現は、ステップ１２６５でグローバルテーブルから除去されてメモリ空間を解放する。
【０２８４】
ローカルインデックステーブルの全てのエントリが処理されると、ステップ１２３５に戻る。
【０２８５】
受信したネットワーク事象は、処理対象のヘッダ又は接続の終了事象でもない場合、ステップ１２３５に戻る前にステップ１２７０で専用の処理により慣例的に処理される。
【０２８６】
図１２の処理により、グローバルテーブルとローカルインデックステーブル（すなわち、現在の接続）とをしっかりと同期できる。接続カウンタがグローバルテーブルのヘッダ毎に最新の状態を維持されるため、これは、ネットワーク通信の間に同期に行われなければならない処理及び何らかの更なるメモリ消費を犠牲にして進む。
【０２８７】
グローバルテーブルの使用を最適化するこれらの処理に加えて、更なる最適化処理があってもよい。
【０２８８】
例えば、ネットワークノードがメモリ空間を解放する必要があってもよい。その場合、グローバルテーブルは、削除、すなわちグローバルテーブルを小さくするための適切なエントリを発見するために走査されてもよい。１つの方法は、閾値より小さい値の接続カウンタと関連付けられたインデックス化ヘッダを使用する現在の接続をリセットすることを含む。上述したものと同一の接続カウンタが使用される。接続カウンタが小さい値を有する全てのヘッダを判定すると、対応する接続（判定されたヘッダを使用する接続）はリセットされる。これにより、インデックス化ヘッダを有さない真新しい接続を開くようにクライアントに強制することを犠牲にして、グローバルテーブルから全ての低カウンタヘッダを除去できる。
【０２８９】
当然、ヘッダをグローバルテーブルから強制的に除去するために、接続カウンタ単独以外の基準が使用されてもよい。例えば基準は、グローバルテーブルにおいてエントリ毎に規定された作成日又は最終利用日（日付は完全な日付である必要はないが、例えば０〜１５分の時間を測定できるようにする１分の範囲に対応する４ビットの整数である規則的に増加された短縮整数であってよい）に基づいてもよい。従って、最も古いヘッダのみが除去される。
【０２９０】
別の更なる最適化処理は、メモリを解放する要求を受信すると、ローカルインデックステーブルにおいてインデックス化されたヘッダ数（すなわち、一般に既に使用されているインデックスの最大数）をメモリに保存することと、グローバルテーブルを削除することと、保存した数から始まるインデックスを使用してローカルインデックステーブルにおいて新しいヘッダをインデックス化することとを含んでもよい。当然、これは、削除されたグローバルテーブルにリンクされた接続に対応する全てのローカルインデックステーブルに対して実行されてもよい。
【０２９１】
従って、各ローカルインデックステーブルは、過去のエントリ数を維持し、第１のインデックスとしてその数を使用して新しいエントリ（すなわち、ヘッダ）をインデックス化する。これにより、新しいヘッダインデックスをテーブルをインデックス化する符号器に準拠したままにできる。
【０２９２】
特に、復号器は、過去のエントリ数から始まる新しいインデックスを検出できるため、グローバルテーブルの同一の削除を実行するように強制されない。しかし、復号器は、符号器と同一の削除戦略を実現でき、これは、それら双方が同時にメモリを解放し且つ同一の削除を実行する要求を受信することを意味する。
【０２９３】
一変形例において、復号器は、フラグをビットストリームに追加して、それがメモリを解放した時を復号器に示してもよい。これにより、復号器は、復号化処理において同時にそのメモリ（グローバルテーブル）もフラッシュできるようになる。
【０２９４】
上述の処理は、情報項目（ＳＰＤＹの場合にはＨＴＴＰヘッダ）をインデックス化することに基づく。
【０２９５】
しかし、プロセッサは、いずれか又は全てのネットワーク接続に対するこのヘッダインデックス化を有効又は無効にすることを決定してもよい。この決定をどの基準に基づかせるかは、速度又は圧縮の向上に関連してもよい。
【０２９６】
圧縮の向上に関して、ヘッダインデックス化方法（すなわち、インデックスの使用）は、デフレート圧縮率の計算に基づいて有効にされてもよい。
【０２９７】
例えば、現在の接続の第１の要求及び第２の要求のヘッダに対して達成された圧縮率が計算されてもよい。次に、第２の要求に対する圧縮率（率Ｈ２）が第１の要求の圧縮率（率Ｈ１）よりそれほど高くない場合、ヘッダインデックス化はかなりの圧縮率の向上をもたらす。８０％は率Ｈ２／Ｈ１がヘッダインデックス化をトリガするのに適切な閾値である（Ｈ２／Ｈ１≧８０％の場合）ことが観察されている。
【０２９８】
これは、おそらくコンテキスト（スライディングウィンドウ）が小さすぎるために、第１の要求から構築されたデフレート圧縮コンテキストが第２の要求に対して効率的に使用されないように見えるためであったからである。
【０２９９】
速度の向上に関して、接続において送受信されたメッセージの数は、速度性能に密接に関連するように見える。
【０３００】
これを示すために、単一のメッセージが接続において送受信される場合、ローカルインデックステーブルを構築するコストは、少ない場合であっても、そのインデックステーブルを使用することで補償されない。
【０３０１】
送受信されるメッセージの数が増加するとすぐに、インデックステーブルが益々使用されるようになり、その結果速度ゲインが得られる。一般にヘッダインデックス化は、６個以上のメッセージを含む送受信に対してかなりの速度の向上をもたらし、１１個以上のメッセージを含む送受信に対して２倍の速度の向上をもたらす。
【０３０２】
次にネットワークノードは、接続毎のメッセージの数に対する統計を計算することを決定してもよく、全てのネットワーク化ノードに対する平均数又はネットワークノード毎の平均数に基づいて、ヘッダインデックス化を使用するか否かが決定されてもよい。
【０３０３】
次に、図１４〜図１８を参照して、ヘッダに対するバイナリ表現が符号化される（文字通り、デルタ符号化、インデックス）方法に依存するそれらの例を説明する。
【０３０４】
図１４は、ローカルインデックステーブルからのインデックスを使用して符号化される第１のリストのヘッダに対するバイナリ表現を示す。
【０３０５】
第１のバイトは、ヘッダがインデックスを使用して完全に符号化されることを規定するために「１」に設定された第１のビットを含む。バイトの残りの７ビットは、インデックス値が０〜１２６（「０００  ００００」〜「１１１  １１１０」のビット値）を含むかを規定するために使用される。
【０３０６】
インデックス値が１２６より大きい場合、７ビットは、１２７、すなわち「１１１  １１１１」に設定される。また、後続のバイトは、インデックス値−１２７（１２７〜３８２のインデックスを符号化する「００００  ００００」〜「１１１１  １１１１」のビット値）を規定するために使用される。
【０３０７】
本実施形態において、インデックス値は３８２より大きくなり得ない。当然、例えば別の更なるバイトが使用されることを規定するために更なるバイトに対して１つの特定の値を使用することにより、他の実現例は３８２より大きいインデックス値を許可してもよい。
【０３０８】
図１５は、文字通り符号化される第２のリストのヘッダに対するバイナリ表現を示す。示されるバイトは、そのようなリテラル符号化が使用されることを規定し且つヘッダ名を符号化するために使用される。図１８で以下において示されるようにヘッダ値を文字通り符号化する１つ以上のバイトは、バイト（場合によってはいくつかのバイト）に後続する。
【０３０９】
示されたバイトの第１のビットは、ヘッダが図１４のようなインデックスを使用して符号化されないことを規定するために「０」に設定される。
【０３１０】
第２のビットは、デルタ符号化が使用されるか否かを規定するために使用される（図１６及び図１７を参照して以下のデルタ符号化を参照）。図１５がリテラル符号化に対応する時、この第２のビットは「０」に設定される。
【０３１１】
第３のビットは、符号化されているヘッダが更なるインデックス化のためにローカルインデックステーブルにおいてインデックス化されなければならないか否かを規定するために使用される。同一のビットは、図１６及び図１７）のデルタ符号化の場合に同一の機能に対して使用される。
【０３１２】
符号器がヘッダをインデックス化しないことを決定する場合（ステップ７４０を参照）、この第３のビットは「０」に設定される。符号器がヘッダをインデックス化することを決定する場合、この第３のビットは、ヘッダがローカルインデックステーブルに追加されなければならないことを復号器に示す「１」に設定される。
【０３１３】
残りの５ビットは、（ビット３〜７）は、ヘッダ名を符号化するために使用される。
【０３１４】
一実施形態において、ヘッダ名を符号化するために、周知のＨＴＴＰヘッダ名を含むＨＴＴＰヘッダ名のリストが使用される。最も頻繁なヘッダは、より効率的に符号化されうるように最もインデックス化されていない割り当てられる。このリストは、静的であり、符号器と復号器との間で共有される。すなわち、新しいヘッダ名をこのリストに追加できない。新しくヘッダ名はサーバからダウンロードされてもよい。
【０３１５】
一実施形態において、周知のヘッダ名に加えて余分なヘッダ名が使用されてもよいため、余分なヘッダ名を含む別のリスト（すなわち、余分なヘッダ名のリスト）が更に規定される。このリストは最初は空であるが、符号器は、自由にそこにヘッダ名を追加する。その結果、余分なＨＴＴＰヘッダ名は、所定の接続上に２回以上現れる場合、１回だけ文字通り符号化されて、次に余分なヘッダ名のリストのエントリに対する参照として符号化されるべきである。
【０３１６】
ヘッダ名に対するインデックス化規則は、符号器及び復号器の双方から認識され、同期を保証する。
【０３１７】
残りの５ビットは、以下のいくつかの値を取ってもよい。
【０３１８】
例において「０  ００００」「１  １１００」である値の範囲は、インデックスが０〜２８に含まれる場合に既知のヘッダ名のインデックスを符号化するために使用される；
例において「１  １１０１」である値は、既知のヘッダ名のインデックスが２８より大きいかを示すために使用される。その場合、現在のバイトに後続する１つ又はいくつかの更なるバイト（不図示）は、インデックス−２９を符号化するために追加される；
例において「１  １１１０」である値は、新しい余分なヘッダ名が文字通り符号化されることを示すために使用される。その場合、現在のバイトに後続する１つ又はいくつかの更なるバイト（不図示）は、新しい余分なヘッダ名を文字通り符号化するために追加される。すなわち、その長さが最初に符号化され、次にその値が符号化される。その様な値を検出すれば、新しい余分なヘッダ名が余分なヘッダ名のリストに追加されなければならないことを復号器が認識できる；
この例において「１  １１１１」である値は、ヘッダ名が余分なヘッダ名のリストにおいて既にインデックス化されている余分なヘッダ名のインデックスを使用して符号化される。その場合、現在のバイトに後続する１つ又はいくつかの更なるバイト（不図示）は、余分なヘッダ名のリストにそのような余分なヘッダ名のインデックスを含む。
【０３１９】
図１６及び図１７は、デルタ符号化される第２のリストのヘッダに対するバイナリ表現を示す。図１６は、更なるインデックス化のためにデルタ符号化されたヘッダをインデックス化しないことが決定される場合に対応する。図１７は、更なるインデックス化のためにデルタ符号化されたヘッダをインデックス化することが決定される場合に対応する。
【０３２０】
示されるバイトは、そのようなデルタ符号化が使用されることを規定し、且つデルタ符号化のために参照として使用される既にインデックス化されているヘッダのインデックスを符号化するために使用される。図１８で以下において示されるようなヘッダ値フレームを使用してヘッダ値を符号化し、特にヘッダ値と参照ヘッダにより取られた値との間の共通部分を規定し、且つ値の間の差分を文字通り符号化するために、１つ以上のバイトはバイト（場合によってはいくつかのバイト）に後続する。
【０３２１】
図１５を参照して上述したように、バイトの第１のビットは、ヘッダが図１４のようなインデックスを使用して符号化されないことを規定するために「０」に設定され、第２のビットは、デルタ符号化が使用されることを規定するために「１」に設定される。
【０３２２】
図１６において、ヘッダを符号化するためにインデックスが要求されないため、第３のビットは「０」に設定される。
【０３２３】
その場合、残りの５ビット（ビット３〜７）は、デルタ符号化のために参照として使用された参照ヘッダのインデックスを符号化するために使用される。それらは、以下のいくつかの値を取ってもよい。
【０３２４】
例において「０  ００００」〜「１  １１１０」である値の範囲は、インデックスが０〜３０に含まれる場合に参照ヘッダのインデックスを符号化するために使用される；
例において「１  １１１１」である値は、参照ヘッダのインデックスが３０より大きいことを示すために使用される。その場合、現在のバイトに後続する１つ又はいくつかの更なるバイト（不図示）は、参照ヘッダ−３１のインデックスを含む。
【０３２５】
ヘッダ値を符号化する１つ以上のバイトは、このような１つ又は複数のバイトに後続する。
【０３２６】
一実施形態において、第１のバイト（又は必要であればより多くのバイト）は、符号化されているヘッダ値及び参照ヘッダにより取られたヘッダ値により共有された共通のプレフィックスの長さを含む。共通のプレフィックスは、２つの値の間の同様に開始する文字の数であってもよい。０〜１２７の長さが１バイト上に符号化されるのに対し、１２８〜３２８９６の長さは２バイト上に符号化される。
【０３２７】
図１８で以下において示されるように２つの値の間の差分を文字通り符号化する１つ以上のバイト（すなわち、共通のプレフィックスが符号化されているヘッダ値から破棄されている間の残りのデータ）は、共通のプレフィックスの長さを規定するためのバイトに後続する。
【０３２８】
２つの値（符号化されているヘッダ値及び参照ヘッダにより取られたヘッダ値）が数である別の実施形態において、２つの値の間の数の差分だけが、図１８のヘッダ値フレームのみを使用して文字通り符号化されうる（共通のプレフィックスの長さを規定するためのバイトは使用されていない）。
【０３２９】
図１６とは異なり、図１７において、ヘッダを符号化するためにインデックスが要求されるため、第３のビットは「１」に設定される。
【０３３０】
その場合、第４のビットは、符号器により決定されるようなインデックス化モード、すなわち増分インデックス化と置き換えインデックス化との間のを規定するために使用される。例えば第４のビットは、増分インデックス化が決定されている場合には「０」に設定され、置き換えインデックス化が決定されている場合には「１」に設定される。
【０３３１】
本実施形態において、第３のビットと第４のビットとの組合せは、符号化されているヘッダのインデックス化を規定するためのバイナリフラグを与える。
【０３３２】
残りの４ビット（ビット４〜７）は、デルタ符号化のために参照として使用された参照ヘッダのインデックスを符号化するために使用される。それらは、以下のいくつかの値を取ってもよい。
【０３３３】
例において「００００」〜「１１１０」である値の範囲は、インデックスが０〜１４に含まれる場合に参照ヘッダのインデックスを符号化するために使用される；
例において「１１１１」である値は、参照ヘッダのインデックスが１４より大きいことを示すために使用される。その場合、現在のバイトに後続する１つ又はいくつかの更なるバイト（不図示）は、参照ヘッダ−１５のインデックスを含む。
【０３３４】
図１６の場合と同様に、ヘッダ値を符号化する１つ以上のバイトは、このような１つ又は複数のバイトに後続する。
【０３３５】
一実施形態において、第１のバイト（又は必要であればより多くのバイト）は、符号化されているヘッダ値及び参照ヘッダにより取られたヘッダ値により共有された共通のプレフィックスの長さを含む。共通のプレフィックスは、２つの値の間の同様に開始する文字の数であってもよい。０〜１２７の長さが１バイト上に符号化されるのに対し、１２８〜３２８９６の長さは２バイト上に符号化される。
【０３３６】
図１８で以下において示されるように２つの値の間の差分を文字通り符号化する１つ以上のバイト（すなわち、共通のプレフィックスが符号化されているヘッダ値から破棄されている間の残りのデータ）は、共通のプレフィックスの長さを規定するためのバイトに後続する。
【０３３７】
２つの値（符号化されているヘッダ値及び参照ヘッダにより取られたヘッダ値）が数である別の実施形態において、２つの値の間の数の差分だけが、図１８のヘッダ値フレームのみを使用して文字通り符号化されうる（共通のプレフィックスの長さを規定するためのバイトは使用されていない）。
【０３３８】
図１８は、文字通り符号化される第２のリストのヘッダ値（上述したように異なる値を含む）に対するバイナリ表現を部分的に示す。
【０３３９】
ヘッダ値は、最初にそれらの長さを示し、次にそれらの値を示すことで文字通り符号化される。デルタインデックス化の場合、デルタ値はヘッダ値と同様に符号化される。しかし、相補的なデータは、ヘッダ値全体がこのデルタ値から取得されうる方法を示す（例えば、共通部分の定義バイトを使用して）。
【０３４０】
符号化対象の値の長さは、１バイト又は２バイトに規定される。
【０３４１】
図１８に示されるような第１のバイトの第１のビットは、長さが１バイト（「０」に設定された第１のビット）又は２バイト（「１」に設定された第１のビット）上に符号化されるかを示す。
【０３４２】
第１のビットが「０」である場合、ヘッダ値の長さは、バイトの残りの７ビット（０〜１２７の長さ）上に符号化される。第１のビットが「１」である場合、ヘッダ値の長さ−１２８は、次の１５ビット（１２８〜３２，８９６の長さ）上に符号化される。
【０３４３】
次に値は、以下のバイト（不図示、すなわちその数はヘッダ値の長さに依存する）上に符号化される。
【０３４４】
特定の実施形態を参照して本発明を上述したが、本発明は特定の実施形態に限定されず、本発明の範囲内にある変更は当業者には明らかとなるだろう。単なる一例として与えられ且つ添付の特許請求の範囲により判定されるような本発明の範囲を限定することを意図しない上述の例示的な実施形態を参照することにより、多くの更なる変更及び変形が当業者に提案されるだろう。特に、種々の実施形態とは異なる特徴が適宜交換されてもよい。
【図１】
0006021930.tif 000002
【図２ａ】
0006021930.tif 000003
【図２ｂ】
0006021930.tif 000004
【図２ｃ】
0006021930.tif 000005
【図２ｄ】
0006021930.tif 000006
【図３】
0006021930.tif 000007
【図４ａ】
0006021930.tif 000008
【図４ｂ】
0006021930.tif 000009
【図５】
0006021930.tif 000010
【図６】
0006021930.tif 000011
【図７】
0006021930.tif 000012
【図８】
0006021930.tif 000013
【図９】
0006021930.tif 000014
【図１０】
0006021930.tif 000015
【図１１】
0006021930.tif 000016
【図１２】
0006021930.tif 000017
【図１３】
0006021930.tif 000018
【図１４】
0006021930.tif 000019
【図１５】
0006021930.tif 000020
【図１６】
0006021930.tif 000021
【図１７】
0006021930.tif 000022
【図１８】
0006021930.tif 000023