JP3958211B2

JP3958211B2 - 静的な情報知識を用いたバイナリー圧縮方法

Info

Publication number: JP3958211B2
Application number: JP2002543788A
Authority: JP
Inventors: ハンスハンヌ，; クリステルスヴァンブロ，; ヤンクリストッフェルッソン，
Original assignee: テレフオンアクチーボラゲットエルエムエリクソン（パブル）
Priority date: 2000-11-16
Filing date: 2001-11-15
Publication date: 2007-08-15
Anticipated expiration: 2021-11-15
Also published as: CN1316749C; CA2428788A1; TW543311B; JP2004514366A; WO2002041497A3; CN1486536A; CA2428788C; EP1334557A2; WO2002041497A2; AU2002215287A1

Description

【０００１】
［関連出願についての相互参照］
本願は、２０００年１１月１６日に出願された米国特許出願第６０／２４９，９２３（代理人整理番号３４６４５−５２２ＵＳＰＬ）、「リクエスト−リプライの通信パターンを利用したデータ圧縮のための通信システム及び方法」と題して同時に出願された米国特許出願第０９／８１４４０７（代理人整理番号３４６４５−５２３ＵＳＰＴ）、「暫定的な圧縮テーブルを用いて通信するシステム及び方法」と題して同時に出願された米国特許出願第０９／８１４２６８（代理人整理番号３４６４５−５２４ＵＳＰＴ）及び「共通コンテキスト圧縮のための通信システム及び方法」と題して同時に出願された米国特許出願第０９／０８１４４３４（代理人整理番号３４６４５−５２５ＵＳＰＴ）に関連するものであり、これらを基礎として優先権を主張するものである。
【０００２】
［発明の背景］
［発明の属する技術分野］
本発明は、例えばインターネットプロトコルなどのデータプロトコルを使用して送受信されるメッセージの圧縮に関するものである。
【０００３】
［本発明の背景と目的］
ここ数年で大衆によって幅広く使用されるようになった２つのコミュニケーションテクノロジーはセルラー電話とインターネットである。セルラー電話によって提供されたいくつかの利点は、移動に関する自由度と、ユーザーの場所に依存せず妥当なサービス品質でアクセスできることであった。最近まで、セルラー電話によって提供されてきた主なサービスは通話サービスであった。それに対し、インターネットは、様々なタイプの柔軟性を提供する一方で、固定のコネクションと大きな端末とに主な焦点が当てられてきた。しかしながら、インターネット電話のようないくつかのサービスについての経験的な品質は、一般に全く低いものであると思われてきた。
【０００４】
相当な数のインターネットプロトコル（ＩＰ）がインターネットや他のネットワークの至るところでの通信のためにめに開発されてきた。そのようなインターネットプロトコルの例が、セッション・イニシーエーション・プロトコル（ＳＩＰ）である。ＳＩＰは、マルチメディア・セッションやマルチメディア呼を確立し、変更し、切断させるためのアプリケーション層のプロトコルである。これらのセッションとしては、インターネット・マルチメディア会議や、インターネット電話、及び類似のアプリケーションが含まれるかもしれない。当分野で理解されているように、ＳＩＰは、トランスミッション・コントロール・プロトコル（ＴＣＰ）か、ユーザー・データグラム・プロトコル（ＵＤＰ）上で使用できる。
【０００５】
インターネットプロトコルのもう１つの例は、リアルタイム・ストリーミング・プロトコル（ＲＴＳＰ）であり、これは、オーディオデータ及びビデオデータのようなリアルタイム特性を有するデータの伝送をコントロールするための、アプリケーションレベルのプロトコルである。ＲＴＳＰは、同様にＵＤＰ、ＴＣＰ、あるいはトランスポート・プロトコルのような他のプロトコルと共に使用可能である。さらに他のインターネットプロトコルの例は、セッション・デスクリプション・プロトコル（ＳＤＰ）であり、マルチメディア会議を通告したり、会議用のアドレスや使用ツールの仕様情報などを伝達するために使用されている。同様に、ＳＤＰは、一般的なリアルタイムのマルチメディア・セッションを記述する目的で用いている。ＳＤＰは、ＳＩＰメッセージやＲＴＳＰメッセージのメッセージボディに搭載されて伝送される。ＳＩＰ、ＲＴＳＰ、及びＳＤＰは皆、ＵＴＦ−８符号化におけるＩＳＯ１０６４６の文字セットを使用するアスキーテキストベースのプロトコルである。
【０００６】
新しい技術を開発するために、インターネット及びセルラー電話の技術が統合され始めている。将来のセルラー装置は、インターネットプロトコル（ＩＰ）スタックを搭載し、ウェブのブラウジングや電子メール、及びその他の望ましいサービスだけでなく、ＩＰ上での通話（ＶｏＩＰ）もサポートすることになろう。「オールＩＰ」若しくは「全線ＩＰ」の実現で、通信システムのエンド−エンドでインターネットプロトコルが使用される。セルラーシステムにおいては、セルラー回線や無線ホップを介したＩＰオーバーセルラー回線やＩＰオーバー無線ホップが含まれるかもしれない。インターネットプロトコルは、ＳＩＰ又はＲＴＳＰデータのような制御データや、音声あるいはストリーミングデータのようなユーザーデータなどを含む全てのタイプのトラフィックに使用できる。そのようなテクノロジーの統合により、セルラーテクノロジーの利点である移動性と共にＩＰの利点である柔軟性が提供されよう。
【０００７】
当分野において理解されているように、ＳＩＰ、ＲＴＳＰ及びＳＤＰプロトコルは、セルラー無線アクセスでの使用に密接に関連した類似の特性を有している。これらの類似点の１つは、プロトコルの一般的なリクエスト（要求）性質とリプライ（応答）性質である。一般に、送信機はリクエストを送信すると、リプライを受信するまでアイドル状態を継続する。上述したように、もう１つの類似点は、ＳＩＰ、ＲＴＳＰ及びＳＤＰも皆、ＵＴＦ−８符号化を用いるＩＳＯ１０６４６文字セットを使用したＡＳＣＩＩテキストを基盤としたプロトコルだということである。結果として、同一の情報をバイナリーで表現する場合よりも多くのビットを用いて表現されるのが通常である。これらのプロトコルによって共有されるさらに他の特徴は、セッションの参加者に対して必要な情報を供給するため、そのサイズが一般に大きくなってしまうことである。
【０００８】
ＩＰを用いることでの不利な点は、大きなヘッダーとテキストベースの信号伝達プロトコルとが原因で、ＩＰプロトコルスィートによってもたらされる比較的大きなオーバヘッドである。セルラーシステムにおいては、効率のよい手法を用いて乏しい無線リソースを使用することが常に重要である。セルラーシステムにおいて、１のセルあたりで十分な数のユーザーをサポートすることが重要であり、さもないと、実装コストと運用コストが制限されてしまうからである。このように周波数スペクトルと帯域幅は、セルラー回線における高価なリソースであり、システムリソースは効率よく最大限に使用されるべきである。
【０００９】
ＵＭＴＳ及びＥＤＧＥなどの移動体通信システムや、ＧＳＭ及びＩＳ−９５のような第２世代システムの将来のリリースにおいて、インターネットプロトコルを使用することで、多数のシグナリング・トラフィックが実現されよう。上述したように、インターネットプロトコルのほとんどは比較的に広帯域の固定用コネクション向けに開発されてきた。帯域の狭いセルラー回線上でアクセスが実行される場合には、セットアップにかかる時間や遅延時間のようなサービス要求品質を満たすために、プロトコルメッセージの圧縮が必要とされる。一般に、通信経路上の全てにわたって圧縮することは必要ではない。しかしながら、無線ユーザー端末からコアネットワークまでのような無線回線上では、トラフィックを圧縮することが大いに望まれる。
【００１０】
Ｌｅｍｐｅｌ−ＺｉｖやＨｕｆｆｍａｎ（ハフマン）符号化のような標準的なバイナリー圧縮技術は、圧縮対象データの構造についての明確な知識を利用しないことが、大変一般的である。例えばＳＩＰとＲＴＳＰなどのインターネット・データ・プロトコルにおいてそのような方法を使用して通信メッセージを効率良く圧縮するには、現在のところ困難をともなう。今日において利用可能な標準的なバイナリー圧縮方法は、一般に大きなデータファイル用に設計されている。その結果、繰り返される文字列がわずかであるような小さなメッセージを圧縮するためにそのような方法を使用しても、一般には、非常に不十分な圧縮パフォーマンスしか得られない。実際、もし圧縮対象のメッセージが小さいか、繰り返しの文字列がわずかしか含まれていなければ、標準的な圧縮方法を使用しても元の圧縮されていないパケットよりも現実には大きくなってしまうので、逆効果となってしまうだろう。
【００１１】
バイナリー圧縮方式を実現するための一つの方法は、辞書の使用を基礎とした圧縮技術である。概して、辞書圧縮方式は、辞書として知られているデータ構造を使用し、入力データで見つけられたシンボル文字列を蓄積する。この方式は、入力データを読み込んで、辞書の文字列と一致するシンボルの文字列を探索する。もし文字列の一致が見つかれば、辞書内でのその文字列の位置へのポインターあるいはインデックスが出力され、その文字列自体の代わりにポインターやインデックスが送信される。もしインデックスがそれによって置き換えられた文字列より小さければ、圧縮効果が得られる。圧縮を伸張する装置であるデコンプレッサ−は、圧縮辞書の代表を含んでおり、受信されたインデックスから元の文字列を再構成できる。辞書圧縮方法の例としては、Ｌｅｍｐｅｌ−Ｚｉｖ（ＬＺ７７）アルゴリズムがある。このアルゴリズムは、前のファイルで生じた文字列を、前の事象へのリファレンスと置換してゆくことで動作する。もちろん、繰り返された文字列が多ければ、この方法は特に良い結果をもたらす。
【００１２】
辞書圧縮方式は、一般に、静的なものと動的なものとに分類可能である。静的な辞書は、あらかじめ定義された辞書であり、圧縮が開始される前に構築されており、圧縮処理の間は変更されることはない。静的な辞書は、典型的には、圧縮装置（コンプレッサー）と伸張装置（デコンプレッサー）に、使用前に記憶される、あるいは圧縮動作が開始される前までに送信されて記憶される。
【００１３】
一方で、動的又は適応型の辞書方式は、圧縮の発生に応じて辞書の内容の変更を許容する方式である。概して動的辞書方式は、辞書なし又は予め定義されたデフォルトの辞書を用いて始動し、圧縮処理において新しい文字列を辞書に追加していく。もし入力データの文字列が辞書において見つからなければ、その文字列が辞書中の新しいポジションに追加され、新しいインデックス値が割り当てられる。新しい文字列は伸張装置に送信され、伸張装置の辞書に追加される。新しい文字列のポジションは送信されなくてもよく、伸張装置が新しい文字列を受信したと判定するとその文字列を伸張装置の辞書において、圧縮装置の辞書でのポジションと同一のポジションに追加する。この方法においては、更新された辞書を使用し、入力データにおいて以後発生する文字列を圧縮することができる。その結果として、コンプレッサーとデコンプレッサーの辞書が構築され、圧縮が達成されるように動的に更新される。
【００１４】
辞書圧縮の他の方法は、スライディング・ウインドウ圧縮として知られているタイプである。この方法において圧縮装置は、圧縮処理の間、固定サイズのスライディング・ウインドウを左から右までファイル内を移動する。圧縮アルゴリズムはウインドウの左へとファイルをサーチし、ウインドウ内の現在の文字列とマッチするものを探索する。もしマッチしている文字列が見つかれば、文字列はマッチした長さへのリファレンスに従って、ファイル内のマッチした位置へのリファレンスと置換される。代替的には、最近伸張された文章の大きな１ブロックとルックアヘッド・バッファーとを有するテキストウィンドウで構成されたウインドウであってもよい。このバージョンでは、ルックアヘッド・バッファーがテキストウィンドウ内のマッチを捜すために使用される。もしマッチが見つかれば、文字列はテキストウィンドウ内のマッチした場所のリファレンスと、マッチの長さへのリファレンスとに置換される。この情報は、オリジナルの情報を再生するために同一の辞書を保持している伸張装置によって使用される。
【００１５】
データ圧縮のための他の方法は、２進符号木（バイナリー・コード・ツリー）を使用する方法である。２進符号木において、圧縮対象のシンボル又は文字列は、可変数のビットによる木構造の中で表現され、各シンボルが一義的に伸張可能となる。一般に、入力データにいおいて高い出現確率のシンボルは、出現確率の低いシンボルよりも短い数のビットにより表現される。２進符号木の構築において、個々のシンボルは、２進木から伸びたリーフノード（葉節）の文字列として区画される。より高い出現確率のシンボルは、木の中でより短い枝（ブランチ）として表現され、その結果、文字列を表現するためのビットの数はより少なくなる。逆に、出現確率のより低いシンボルは、その木の中でより長い枝として表現され、より多数のビットが必要となる。入力データ中の文字列が圧縮装置の２進符号木内のシンボルと一致すると、そのシンボルのコードがシンボル自体の代わりに送信され、その結果、データ圧縮が達成される。コードを受信した伸張装置は、同一の２進符号木を使用してオリジナルのシンボル又は文字列を再構成する。
【００１６】
辞書圧縮と同じように、２進符号木には静的なものと動的なものとがある。静的な２進符号木方式では、あらかじめ定義された２進符号木が圧縮処理の前に構築され、圧縮処理の間はその内容が変更されることはない。静的な辞書と同様に、静的な２進符号木が前もって圧縮装置と伸張装置とに記憶されるか、あるいは圧縮処理の開始前までに送信されて記憶される。
【００１７】
動的又は適応型２進符号木では、圧縮処理中であっても符号木への新しいシンボル又は文字列の追加が許容されている。新しいシンボルの追加と、符号木の再構成とを可能にするために使用される２進符号木の圧縮タイプに依存した様々な方法が、符号木のノードを更新するために使用可能である。同様に、伸張装置内の２進符号木は、圧縮装置の２進符号木と同じ規則に従って更新されなければならない。
【００１８】
２進符号木圧縮方式の１つの例は、Ｈｕｆｆｍａｎ符号化による圧縮方式である。Ｈｕｆｆｍａｎ圧縮は、元来アスキー形式のファイルの圧縮用に開発された一般的な圧縮方法である。すなわち、ファイル内で頻繁に出現する文字がより短いコードと置換されて、ＡＳＣＩＩコードによって使用される８ビットよりも少ないビットのコードとして表現される。比較的に少ない数の文字が使用されているようなファイルであればＨｕｆｆｍａｎ圧縮は成功するであろう。
【００１９】
前述の二進圧縮アルゴリズムを使用した圧縮が成功するための一般的な基準は、圧縮されるファイルが合理的に大きいことである。Ｈｕｆｆｍａｎ圧縮のためのコードは圧縮されているファイルと比べて大きくないはずである。標準的なＬｅｍｐｅｌ−Ｚｉｖ圧縮に関していえば、効率の良い圧縮を達成するためには、圧縮対象のファイルが、多くの繰り返された文字列を有するほど十分に大きくなければならない。前述のプロトコルによって生成されたメッセージは、たいてい数百バイトであるが、これはメッセージを基準としみれば、前述のアルゴリズムを使用して圧縮しても効率の良い圧縮を達成するには、十分な大きさとはいえない。
ＥＰ０９３３８７６Ａ１は、通信セッションの開始の際に第１の通信装置から第２の通信装置へと固定の圧縮辞書を送信する、パケット送信用のデータ圧縮方法が開示されている。この第１の端末は、送信した固定の辞書に従ってデータを圧縮し、第２の端末は、受信した固定の辞書に従ってデータを伸張する。
【００２０】
よって、通信プロトコルを使用して送信されるメッセージの圧縮についての効率とパフォーマンスとを高め、帯域幅の制限された通信回線やチャンネル介してメッセージを使用できるようにするためのニーズが当業界には存在するといえる。
【００２１】
［発明の概要］
本発明は、帯域幅の制限された通信回線を介して使用される通信プロトコルの圧縮効率を高めるための方法、システム及び装置に関連する。本発明の一側面によれば、構造の知識や通信プロトコルの内容を使用して、静的な辞書又は静的な２進符号木を作成する。その結果、圧縮効率は大いに高められよう。本発明の他の側面によれば、静的な辞書と動的な辞書とを組み合わせたもの、又は静的な２進符号木と動的な２進符号木とを組み合わせたものを供給して、通信プロトコルの圧縮処理を実行する。本発明の他の側面によれば、静的な２進符号木又は静的な辞書は、それらの使用の意図された条件におけるデータプロトコルのフローを監視することによって構築される。
【００２２】
［好ましい例示的な実施形態に関する詳細な説明］
以下において、本発明の好ましい実施形態が示される添付図面への参照とともに、本発明はより完全に説明される。しかしながら、本発明は多数の種々の形式において実現可能であり、ここに説明される実施形態にのみ限定して解釈されるべきではない。ここでの開示は完全で完成したものであり、本発明の範囲を完全に伝ることができるよう、これらの実施形態を当業者に提供する。
【００２３】
図１は、本発明に従った例示的な通信システムを示す図である。移動端末１１０は、例えば無線回線などの通信回線１１５を介し、通信プロトコルを使用して基地局１２０と通信する。基地局１２０は、通信回線１２５を経由して、ＰＳＴＮなどの固定ネットワーク１３０と通信する。固定ネットワーク１３０は、通信回線１３５を介して基地局１４０と通信する。基地局１４０は、通信回線１４５を介して、端末１５０と通信する。端末１５０は、移動端末又は固定端末のどちらでもよい。本発明の実施形態によれば、移動端末１１０は、圧縮されたデータを使用し、通信回線１１５を介して基地局１２０と通信している。同様に、基地局１４０は、圧縮されたデータを使用して端末１５０と通信してもよい。これは理解されるべきことであるが、移動端末１１０及び基地局１４０のような、図１のシステムにおけるコンポーネントは、圧縮や伸張を実現するためのソフトウェア・インストラクションを記憶するメモリ１６０や、それを実行するプロセッサ１５５を備えていてもよい。同様に理解されているべきことであるが、本発明は、セルラーネットワークのように圧縮が望まれる回線を介して通信プロトコルを使用するような他の通信システムに適用されてもよい。
【００２４】
図２は、本発明の例示的な実施形態を示す図である。この実施形態において、エンティティＡ（２１０）は、データ圧縮が使用されている通信回線（２５０、２５５）を使用してエンティティＢと通信する。各々のエンティティは、データ・コンプレッサー（２１５、２４５）とデータ・デコンプレッサー（２２５、２３５）を備えている。本発明の例示的な実施形態においては、辞書圧縮方法が使用される。この実施形態では、各エンティティ内の静的な辞書２２０は、データプロトコルを使用して通信回線を介して送受信されるデータを圧縮したり伸張したりするために使用される。これは理解されるべきことであるが、コンプレッサー及び／またはデコンプレッサーは、プロセッサと、圧縮又は伸張アルゴリズム用のインストラクションを記憶した付随メモリとを使用して実現されてもよい。これも理解されるべきことであるが、通信エンティティは複数の通信装置を含んでいてもよい。例えば、エンティティＡは移動端末１１０を含んでもよいし、エンティティＢは、基地局１４０を含んでもよい。
【００２５】
本発明の実施形態によれば、エンティティＡ（２１０）とエンティティＢ（２３０）は同一の静的な辞書２２０を使用する。静的な辞書２２０は、通信回線（２５０，２５５）を介して通信するために使用されている、例えばインターネットなどの通信プロトコルによって使用されているプロトコル・フィールド名と共通のシンボル文字列とから構成してもよい。理解されるべきことであるが、通信エンティティは複数の通信装置を含んでもよい。例えば、エンティティＡは移動端末を、エンティティＢは基地局を含むかもしれない。
【００２６】
辞書を形成するために使用されうるエントリーの例としては、音声、映像及び画像情報などのメディアタイプの情報が含まれよう。辞書を形成するための辞書エントリーの他の例としては、ＧＥＴ、ＨＥＡＤ及びＰＯＳＴなどのプロトコル・トークン方法や、コネクション（Ｃｏｎｎｅｃｔｉｏｎ）、日付（Ｄａｔｅ）及びアクセプト（Ａｃｃｅｐｔ）のような特定のプロトコルにおいて使用されているヘッダー・フィールド名が含まれる。この例示的な実施形態において、辞書で見つかりうるデータパケットの部分だけが圧縮されるが、一方、当業者により知られている他の方法を使用して、データパケットの残り部分を非圧縮で又は圧縮して送信してもよい。
【００２７】
図３は、本発明における圧縮と伸張用の例示的なデータパケット３１０を示した図である。この実施形態によると、データパケット３１０は、所与のデータプロトコルに従って送信される情報を表現している。文字列Ａ（３２０）及び文字列Ｃ（３４０）は、静的な辞書で見つからなかったデータパケット３１０の一部を表現している。文字列Ｂ（３３０）及び文字列Ｄ（３５０）は、静的な辞書で見つかったデータパケット３１０の一部を表現している。文字列Ｂ（３３０）及び文字列Ｄ（３５０）を送信する代わりに、静的な辞書内での文字列Ｂの位置へのインデックス３７０と静的な辞書内での文字列Ｄの位置へのインデックス３８０だけが、データパケット３１０のこれらの部分として送信される必要がある。文字列Ａ（３２０）と文字列Ｃ（３４０）とが非圧縮データとしてインデックス３７０とインデックス３８０とに付加され、圧縮されたデータパケット３６０が生成される。代替的に、文字列Ａ（３２０）及び文字列Ｃ（３４０）は当業者により知られている他の圧縮方法を用いて圧縮されてもよい。圧縮されたデータパケット３６０は、受信側のエンティティに対して送信される。
【００２８】
受信側のエンティティによって圧縮されたデータパケットが受信された後、インデックス３７０及びインデックス３８０が、同一の静的な辞書における対応するエントリーと整合処理され、文字列Ｂ（３３０'）と文字列Ｄ（３５０'）とが再構成される。受信された文字列Ａ（３２０'）及び文字列Ｃ（３４０'）は、再構成された文字列Ｂ（３３０'）及び文字列Ｄ（３５０'）とに結合され、オリジナルのデータパケット（３１０'）が再形成すされる。代替的に、文字列Ａ（３２０）及び文字列Ｃとが送信の前に圧縮されていた場合には、再構成された文字列Ｂ（３３０'）及び文字列Ｄ（３５０'）と結合する前に、圧縮されていた文字列Ａ（３２０）及び文字列Ｃを伸張してから、オリジナルのデータパケット（３１０'）を再構成する。
【００２９】
図４は本発明に係る他の例示的な実施形態を示す図である。双方向通信を利用して送信されるデータの性質及びフォーマットはしばしば通信方向ごとに異なっているため、各通信方向ごとに適合可能な圧縮方式が有効である。この実施形態において、エンティティＡ（４１０）は、関連する静的な辞書Ａ（４２０）を伴うデータ・コンプレッサー４１５と、関連する静的な辞書Ｂ（４３０）を伴うデータ・デコンプレッサー４２５とを備える。エンティティＢ（４４０）は、関連する静的な辞書Ａ（４２０）を伴うデータ・デコンプレッサー４４５と、関連する静的な辞書Ｂ（４３０）を伴うデータ・コンプレッサー４５５とを備える。
【００３０】
動作中は、エンティティＡ（４１０）が、データ・コンプレッサー４１５を使用してメッセージ又はデータを圧縮し、通信回線４６０を介してエンティティＢ（４４０）へと送信し、そこで、静的な辞書Ａ（４２０）を使用してデコンプレッサー４４５により伸張処理を実行する。この方法で、エンティティＡ（４１０）のコンプレッサー４１５と、エンティティＢ（４４０）のデコンプレッサー４４５は、圧縮処理及び伸張処理において同一の静的な辞書Ａ（４２０）を使用する。同様に、エンティティＢ（４４０）は、データ・コンプレッサー４５５を使用してメッセージ又はデータを圧縮し、通信回線４６５を介してエンティティＡ（４１０）へと送信し、そこで、静的な辞書Ａ（４２０）を使用してデコンプレッサー４２５により伸張を行なう。エンティティＢ（４４０）のコンプレッサー４５５と、エンティティＡ（４１０）のデコンプレッサー４２５は、圧縮及び伸張において同一の静的な辞書Ｂ（４３０）を使用する。本発明の例示的な実施形態によれば、各通信方向に最適化された静的な辞書を設計することが可能になる。
【００３１】
図５は、静的な辞書と動的な辞書との組み合わせを使用する本発明の他の例示的な実施形態を示した図である。この実施形態では、各通信エンティティにおいて、初期の静的な辞書がコンプレッサー及びデコンプレッサー用の開始の辞書として使用される。通信が開始されるやいなや、この辞書は動的な辞書として動作し始める。この実施形態では、関連する静的／動的辞書５２０を有するコンプレッサー５１５を備えるエンティティＡ（５１０）は、第１の通信回線５５０を利用して、関連する静的／動的辞書５４０を有するデコンプレッサー５３５を備えるエンティティＢ（５１０）と通信する。
【００３２】
エンティティＡ（５１０）において圧縮されたのち、エンティティＢ（５３０）に対して送信されるメッセージは、辞書５２０を用いてテスト処理される。もしメッセージの一部が辞書のエントリーと整合すれば、その部分は対応するインデックスと置換される。辞書内のいずれのエントリーとも整合しないメッセージの部分、あるいは代替的にこのメッセージ部分について選択されたフィールドは、将来の圧縮処理において利用すべく、辞書５２０へと追加される。そして、インデックスと圧縮されていない部分とがエンティティＢ（５３０）へと第１の通信回線を介して送信される。
【００３３】
そして、エンティティＢ（５３０）は、受信したメッセージを伸張し、インデックス情報と非圧縮部分とに分離する。エンティティＢ（５３０）のデコンプレッサー５３５は、このインデックスを内部の辞書５４０内のエントリーと整合させることで圧縮された情報を再生して、非圧縮データへと追加し、オリジナルのメッセージを形成する。エンティティＡ（５１０）において辞書５２０へと追加されたメッセージ部分は、エンティティＢ（５３０）の辞書５４０へと追加され、これにより各エンティティが一致した辞書を維持できるようになる。
【００３４】
エンティティＡ（５１０）からエンティティＢ（５３０）へと送信されるその後のメッセージは、更新された辞書５２０を使用して圧縮され、更新した辞書５２０を使用してエンティティＢ（５３０）により伸張される。その結果、エンティティＡ（５１０）の辞書５２０とエンティティＢの辞書５４０は動的に更新されるため、送信されるデータに圧縮手法を適合させることが可能となる。よって、圧縮効率が継続的に改善されることになる。
【００３５】
さらに、エンティティＡ（５１０）がデコンプレッサー５２５を備え、エンティティＢ（５３０）がコンプレッサー５４５を備えてもよく、この場合は、第２の通信回線５５５を使用してエンティティＢ（５３０）は第２の圧縮されたメッセージをエンティティＡ（５１０）へと送信できるようになる。このように配置させることで、双方向の圧縮された通信機能を提供できる。エンティティＡ（５１０）のデコンプレッサー５２５は、コンプレッサー５１５が使用する静的／動的辞書５２０と同一の辞書を使用してもよい。同様に、エンティティＢ（５３０）のコンプレッサー５４５は、デコンプレッサー５３５が使用する静的／動的辞書５２０と同一の辞書を使用してもよい。代替的に、分離された静的／動的辞書を各コンプレッサー／デコンプレッサーのペアが使用してもよく、この場合は、各通信方向にとって最適化が可能な静的／動的な辞書を使用することができよう。
【００３６】
静的な辞書と動的な辞書とのコンビネーションを使用する本発明の他の例示的な実施形態では、スライディング・ウインドウ辞書による圧縮方法を使用できる。上述の実施形態で説明したように、初期の静的辞書が開始の辞書としてコンプレッサーとデコンプレッサーとにより使用され、通信が開始されるとすぐに動的な辞書として機能し始める。第１のステップにおいて、コンプレッサーを含む第１のエンティティの辞書に対して圧縮対象のメッセージが追加登録される。次のステップにおいて、追加登録されたメッセージを有する辞書が、例えばＬｅｍｐｅｌ−Ｚｉｖなどのスライディング・ウインドウ圧縮方法に従って処理され、圧縮されたメッセージが作成される。このステップにおいて、追加されたメッセージに従ってこの辞書を圧縮してもよい。
【００３７】
さらに次のステップにおいて、静的／動的辞書と対応する圧縮されたメッセージの部分が削除され、辞書内の対応する場所へのリファレンス又はインデックスと置換される。以降のステップにおいて、リファレンス情報に加えて、圧縮されたメッセージの残りが第２のエンティティのデコンプレッサーへと送信される。
【００３８】
さらに次のステップにおいて、受信されたメッセージが、第２のエンティティ内の圧縮されたバージョンの静的／動的辞書へと追加登録されることで、デコンプレッサーがコンプレッサーと同じ辞書を備えることができる。以降のステップにおいて、例えばＬｅｍｐｅｌ−Ｚｉｖなどの対応する伸張方法によって処理され、オリジナルのメッセージが生成される。
【００３９】
上述した方法の代替的な実施形態としては、圧縮方法を用いて辞書を圧縮しないものがある。この実施形態では、実際に動作する前に辞書をバッファへとプリロードしておき、圧縮アルゴリズムの実行の際にツリーを利用して探索してもよい。圧縮対象のメッセージが到着すると、メッセージがロードされているバッファ内の位置から実際の圧縮処理が開始される。このように辞書は圧縮されずに、メッセージ自体だけが圧縮されていてもよい。この実施形態によると、デコンプレッサーの対応する辞書は、同様に、圧縮されていない形式であってもよい。
【００４０】
本発明の重要な側面は、静的な辞書の構築である。本発明に従った静的な辞書の構築に関する１つの例示的な方法には、データパケットのフローを監視し、圧縮が望まれている通信回線上での好ましい通信プロトコルについての統計データを収集する処理が含まれる。
【００４１】
この統計データを通じ、所与の通信プロトコルにおいて、最もよく利用されているプロトコル・フィールド名と他の普通の文字列とを得て、それを使用して静的な辞書を構築してもよく、これにより送信対象のメッセージ又はデータの最適な圧縮が提供される。静的な辞書は、使用前に構築され、第１の通信エンティティと第２のエンティティとに記憶される。このように使用前に記憶しておくことで、通信セッションの最初に発生するオーバーヘッドを削減しうるので、短い通信セッションにおいて使用するのに特に有用である。代替的に、圧縮が開始される前に通信セッションの開始においてコンプレッサーからデコンプレッサーへと静的な辞書を送信してもよい。
【００４２】
辞書圧縮方式の代替案として、静的な２進符号木方式を使用してもよい。静的な２進符号木は、通信回線上で望ましいデータプロトコルのためのパケットのフローを監視するような、統計的な方法を使用して構築してもよい。この統計情報を使用して、出現確率のより高いデータプロトコルのプロトコル・フィールド名や他の一般的な文字列を、出現確率のより低いものよりも少ないビット数で表現するよう、静的な２進符号木が構築される。その結果、圧縮効率が高められる。本発明の実現において利用可能な２進符号木圧縮方式についてのこのような１例は、Ｈｕｆｆｍａｎ符号化方法であるかもしれない。
【００４３】
本発明のさらに他の例示的な実施形態では、静的な２進符号木を静的な辞書との組み合わせで使用してもよい。この例示的な実施形態では、本発明に従って説明された手法の一つのような望ましい手法を使用して初めに静的な辞書を構築する。使用中の静的な辞書を用いて望ましいデータプロトコルについてのパケットのフローを監視し、それに従って静的な２進符号木を構築してもよい。静的な辞書圧縮と、Ｈｕｆｆｍａｎ符号化のような静的な２進符号木圧縮と組み合わせて使用することで、送信データの圧縮効率を高めることができるかもしれない。
【００４４】
本発明に係る方法、システム及び装置についての様々な実施形態を、添付の図面と上述の詳細な説明を用いて例示してきたが、本発明は開示された実施形態に限定されるものではなく、請求項により定義された発明の範囲を逸脱することなく、種々の設計変更、修正及び置換も可能である。
【図面の簡単な説明】
本発明のシステム、方法及び装置についての完全な理解は、添付の対応する図面を参照しつつ詳細な説明を読むことにより得られよう。
【図１】図１は、本発明に関する例示的な通信システムを示した図である。
【図２】図２は、本発明に係る例示的な実施形態を示した図である。
【図３】本発明の圧縮及び伸張に関する例示的なデータパケットを示した図である。
【図４】本発明の他の例示的な実施形態を示した図である。
【図５】本発明の他の例示的な実施形態を示した図である。

Claims

通信プロトコルを使用して送信されるメッセージを圧縮する通信装置であって、
静的辞書と動的辞書とを組み合わせた静的／動的辞書と、
前記静的／動的辞書を用いて動作するコンプレッサーと
を含み、
前記静的／動的辞書に含まれる前記静的辞書は、前記通信プロトコルの少なくとも一つの第１シンボルに対応する少なくとも一つの第１シンボル文字列を備え、前記静的辞書内の少なくとも一つのエントリーは、前記通信プロトコルによるデータフローの統計に基づいて登録されており、
前記静的／動的辞書に含まれる前記動的辞書は、前記通信プロトコルの少なくとも一つの第２シンボルに対応する少なくとも一つの第２シンボル文字列を備え、
前記コンプレッサーは、前記通信プロトコルに従った第１通信メッセージに含まれる前記少なくとも一つの第１シンボル文字列を圧縮するために前記静的辞書を使用し、前記通信プロトコルに従った以降の通信メッセージに含まれる少なくとも一つのシンボル文字列を圧縮するために前記動的辞書を使用することを特徴とする通信装置。
前記第１通信メッセージに含まれる残りのシンボル文字列が前記静的辞書に含まれていないときは、前記残りのシンボル文字列については圧縮せずに、前記第１通信メッセージを送信するとともに、前記残りのシンボル文字列を前記動的辞書に追加し、それ以降の通信メッセージに前記残りのシンボル文字列と同一のシンボル文字列が含まれていたときは、前記動的辞書を用いて該シンボル文字列を圧縮することを特徴とする請求項１に記載の通信装置。
前記通信装置はさらに、
前記静的／動的辞書を用いて動作するデコンプレッサーを含み、
前記デコンプレッサーは、前記静的／動的辞書を使用して、前記通信プロトコルに従った第２通信メッセージに含まれる前記少なくとも一つのシンボル文字列を伸張することを特徴とする請求項１又は２に記載の通信装置。
前記通信装置はさらに、
前記コンプレッサーと作用する２進符号木を含み、
前記コンプレッサーは、前記２進符号木を使用して、前記通信プロトコルに従った第１通信メッセージに含まれる前記少なくとも一つのシンボル文字列を圧縮することを特徴とする請求項１に記載の通信装置。
前記２進符号木にはハフマン２進符号木が含まれることを特徴とする請求項４に記載の通信装置。
前記２進符号木には静的２進符号木が含まれることを特徴とする請求項４に記載の通信装置。
前記通信プロトコルの前記少なくとも一つのシンボルには、前記通信プロトコルにおける少なくとも一つのフィールド名が含まれることを特徴とする請求項１に記載の通信装置。
前記コンプレッサーはスライディング・ウインドウ圧縮方法を使用することを特徴とする請求項１に記載の通信装置。
通信プロトコルを使用して受信したメッセージを伸張する通信装置であって、
静的辞書と動的辞書とを組み合わせた静的／動的辞書と、
前記静的／動的辞書を用いて動作するデコンプレッサーと
を含み、
前記静的／動的辞書に含まれる前記静的辞書は、前記通信プロトコルの少なくとも一つの第１シンボルに対応する少なくとも一つの第１シンボル文字列を備え、前記静的辞書内の少なくとも一つのエントリーは、前記通信プロトコルによるデータフローの統計に基づいて登録されており、
前記静的／動的辞書に含まれる前記動的辞書は、前記通信プロトコルの少なくとも一つの第２シンボルに対応する少なくとも一つの第２シンボル文字列を備え、
前記デコンプレッサーは、前記通信プロトコルに従った第１通信メッセージに含まれる前記少なくとも一つの第１シンボル文字列を伸張するために前記静的辞書を使用し、前記通信プロトコルに従った以降の通信メッセージに含まれる少なくとも一つのシンボル文字列を伸張するために前記動的辞書を使用することを特徴とする通信装置。
前記第１通信メッセージに非圧縮のシンボル文字列が含まれていたときは、該シンボル文字列を前記動的辞書に追加し、それ以降の通信メッセージに前記非圧縮のシンボル文字列に対応する圧縮されたシンボル文字列が含まれていたときは、前記動的辞書を用いて該圧縮されたシンボル文字列を伸張することを特徴とする請求項９に記載の通信装置。
前記静的／動的辞書を用いて動作するコンプレッサーを含み、
前記コンプレッサーは、前記静的／動的辞書を使用して、前記通信プロトコルに従った第２通信メッセージに含まれる少なくとも一つのシンボル文字列を圧縮することを特徴とする請求項９又は１０に記載の通信装置。
前記デコンプレッサーと作用する２進符号木を含み、
前記デコンプレッサーは、前記２進符号木を使用して、前記通信プロトコルに従った第１のメッセージに含まれる少なくとも一つのシンボル文字列を伸張することを特徴とする請求項９に記載の通信装置。
前記２進符号木には静的２進符号木が含まれることを特徴とする請求項１２に記載の通信装置。
前記２進符号木にはハフマン２進符号木が含まれることを特徴とする請求項１２に記載の通信装置。
前記通信プロトコルの前記少なくとも一つのシンボルには、前記通信プロトコルにおける少なくとも一つのフィールド名が含まれることを特徴とする請求項９に記載の通信装置。
前記コンプレッサーはスライディング・ウインドウ伸張方法を使用することを特徴とする請求項９に記載の通信装置。
圧縮されたメッセージの通信を容易にする通信システムであって、
請求項１ないし８の何れか１項に記載された通信装置である第１通信装置と、
前記第１通信装置から通信メッセージを受信する、請求項９ないし１６の何れか１項に記載された通信装置である第２通信装置と
を含み、
前記第１通信装置が使用する前記静的／動的辞書と、前記第２通信装置が使用する前記静的／動的辞書とは実質的に等価の辞書であることを特徴とする通信システム。
通信プロトコルを使用して圧縮されたメッセージの通信を容易にする方法であって、
静的辞書と動的辞書とを組み合わせてなる静的／動的辞書が使用され、前記静的辞書は、前記通信プロトコルの少なくとも一つの第１シンボルに対応する少なくとも一つの第１シンボル文字列を備え、前記静的辞書内の少なくとも一つのエントリーは、前記通信プロトコルによるデータフローの統計に基づいて登録されており、前記動的辞書は、前記通信プロトコルの少なくとも一つの第２シンボルに対応する少なくとも一つの第２シンボル文字列を備えており、
前記方法は、
通信メッセージ内に含まれている、前記通信プロトコルに対応するシンボル文字列を静的／動的辞書から探索するステップと、
前記静的／動的辞書が前記シンボル文字列を含んでいるという肯定的な確認が得られると、前記静的／動的辞書から前記シンボル文字列に関係する圧縮されたシンボル文字列を抽出するステップと、
前記通信メッセージ内において、前記シンボル文字列を前記圧縮されたシンボル文字列と置換するステップと、
前記通信プロトコルを使用して前記通信メッセージを送信するステップと
を含むことを特徴とする方法。
前記通信メッセージに含まれる残りのシンボル文字列が前記静的辞書に含まれていないときは、前記残りのシンボル文字列を圧縮せずに、前記通信メッセージを送信するとともに、前記残りのシンボル文字列を前記動的辞書に追加することで、それ以降の通信メッセージに前記残りのシンボル文字列と同一のシンボル文字列が含まれていたときは、前記動的辞書を用いて該シンボル文字列を圧縮することを特徴とする請求項１８に記載の方法。
通信プロトコルを使用して圧縮されたメッセージの通信を容易にする方法であって、
静的辞書と動的辞書とを組み合わせてなる静的／動的辞書が使用され、前記静的辞書は、前記通信プロトコルの少なくとも一つの第１シンボルに対応する少なくとも一つの第１シンボル文字列を備え、前記静的辞書内の少なくとも一つのエントリーは、前記通信プロトコルによるデータフローの統計に基づいて登録されており、前記動的辞書は、前記通信プロトコルの少なくとも一つの第２シンボルに対応する少なくとも一つの第２シンボル文字列を備えており、
前記方法は、
通信プロトコルを使用して、圧縮されたシンボル文字列を含んだ通信メッセージを受信するステップと、
前記圧縮されたシンボル文字列に関連する圧縮前の文字列を静的／動的辞書から抽出するステップと、
前記通信メッセージ内において、前記圧縮されたシンボル文字列を前記圧縮前のシンボル文字列と置換するステップと
を含むことを特徴とする方法。
前記通信メッセージに非圧縮のシンボル文字列が含まれていたときは、該シンボル文字列を前記動的辞書に追加し、それ以降の通信メッセージに前記非圧縮のシンボル文字列に対応する圧縮されたシンボル文字列が含まれていたときは、前記動的辞書を用いて該圧縮されたシンボル文字列を伸張することを特徴とする請求項２０に記載の方法。