(57)【要約】      （修正有）【課題】ＬＺ７７ベース機構を用いて入力データストリームの圧縮方法及びシステムを提供。【解決手段】バイトの現在シーケンスと同一である既に処理されたデータバイトの一致シーケンスがサーチされ、リテラル（一致シーケンスの部分を形成しないバイト）又は一致コード（エンコードされた一致シーケンス）のシーケンスがリテラル又は一致コードの数を示すカウント値によって識別される。圧縮及び圧縮解除には一致円形ヒストリバッファが使用され、これは、送信されるエンコードデータの各フレームと共に含まれるコヒレンスバイトを用いて同期される。エンコードされたフレームが圧縮解除装置によって受け取られない場合は、圧縮解除装置が圧縮装置へフラッシュ要求送信する。圧縮装置は、そのフラッシュ要求に応答してヒストリバッファをフラッシュし、ヒストリバッファに記憶された既処理されたバイトを一致シーケンスの部分にならないようにする。【選択図】図１
2007243959.tif 000002
【特許請求の範囲】
【請求項１】
パケット当たりｍ以下のデータバイトを有するパケットに分割されたデータバイトの入力ストリームを受け取る処理と、
ｍより大きなサイズｎの円形ヒストリバッファに１つ以上のパケットを順次に挿入する処理と、
前記ヒストリバッファに直前のパケットが挿入された後にヒストリバッファの終わりに残っているバイトがｘ未満であるときにヒストリバッファの最初のｘバイトにサイズｘのパケットを挿入する処理と、
現在のバイトストリングと同一である既に処理されたデータバイトの一致ストリングをサーチする処理と、
エンコードされたデータストリームに、このような一致ストリングの部分を形成しない各データバイトを付加する処理と、このようなデータバイトはリテラルであり、
前記エンコードされたデータストリームに、前記一致ストリングの入力ストリームにおける位置と、前記一致ストリングにおけるデータバイトの数との両方を識別する一致コードを付加する処理と、を含むデータ圧縮方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般にデータ圧縮方法及びシステムに係り、より詳細には、コンピュータ内通信環境においてＬＺ７７ベースの圧縮を使用してデータを圧縮する方法及びシステムに係る。
【背景技術】
【０００２】
１９７７年５月のＩＥＥＥトランザクションズ・オン・インフォーメーション・セオリ２３（３）：第３３７ないし３４３ページに掲載されたジブ・ジャコブ及びレンペル・アブラハム著の「逐次データ圧縮用の汎用アルゴリズム(A Universal Algorithm for Sequential Data Compression)」に述べられた研究から種々のデータ圧縮アルゴリズムが導出される。これらのアルゴリズムは、一般に、ＬＺ７７圧縮機構と称する。このＬＺ７７圧縮機構は、キャラクタの繰り返しストリングを、そのストリングの以前の発生を指すポインタと置き換えられるという原理に基づいている。ポインタは、通常、以前の発生の位置の指示（典型的に繰り返しストリングのスタートからのオフセット）と、一致するキャラクタの数（長さ）とによって表される。ポインタは、通常、＜オフセット、長さ＞対として表される。例えば、次のストリング”ａｂｃｄａｂｃｄａｃｄａｃｄａｃｄａｅａａａａａａ”は、圧縮形態では次のように表される。
”ａｂｃｄ＜４，５＞＜３，９＞ｅａ＜１，５＞”
【０００３】
最初のキャラクタ”ａｂｃｄ”はその手前のいずれのキャラクタにも一致しないので、リテラルとして非圧縮形態で出力される。対＜４，５＞は、オフセット４でスタートして５キャラクタ分だけ延びるストリングが”ａｂｃｄａ”と繰り返されることを指示する。対＜３，９＞は、オフセット３でスタートして９キャラクタ分だけ延びるストリングが繰り返されることを指示する。”ｅａ”はリテラルとして出力され、そして対＜１，５＞は、オフセット１でスタートして５キャラクタ分だけ延びるストリング（”ａａａａａ”）を指示する。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
圧縮は、繰り返されるストリングを、そのストリングを繰り返すのに要するよりも少数のビットをもつポインタとして表すことにより行われる。典型的に、リテラルとして知られている非一致の単一バイトは、ポインタとして表されない。むしろ、リテラルは、バイト自体が後に続くリテラルエンコードを指示するフラグと共に出力される。ポインタは、典型的に、オフセット及び長さが後に続く相違フラグによってリテラルエンコードとは区別される。オフセット及び長さは、種々の仕方でエンコードすることができる。各リテラル及び各ポインタにフラグを追加することにより、公知のＬＺベースのシステムは、最適な圧縮に及ぶことがなく、拡張を生じることすらある。
【０００５】
公知の圧縮システムの大部分は、フロッピー（登録商標）ディスク又はコンピュータハードドライブのような単一の媒体に記憶されたデータの圧縮に関するものである。しかしながら、ネットワーク又はモデム通信の場合のように信頼性のないリンクを経てロスのない一般的なデータ圧縮を行う分野については、ほとんど研究が行われていない。このような場合には、圧縮装置及び圧縮解除装置が物理的に取り外され、圧縮装置が圧縮解除装置に送信する情報が経路に沿って失われることがある。
【０００６】
近代的なネットワークは層構成で動作する。ネットワークの上位の層の１つにおいては、レダイレクタ又はリクエスタが、データベース又はファイルのような均質なデータのブロックを送信する。これらのデータブロックは、通常、搬送層へ送られ、この層は、データブロックを、１．５キロバイト（Ｋ）以下のような限定されたサイズのパケットに分割する。次いで、この搬送層は、搬送ヘッダをパケットに追加し、そしてこれらパケットをメディアアクセスコントローラ（ＭＡＣ）へ送り、該コントローラはパケットにフレームヘッダを追加してフレームを形成し、これがネットワークを経て送信される。搬送層から送られるパケットはしばしば単一データブロックの連続部分であるが、２つの異なる送信が同時に保留となっている場合には、搬送層が、異なるバッファに記憶された２つ以上のブロックからパケットを送ることがある。
【０００７】
搬送層においてデータの均質性が与えられると、搬送層をイネーブルしてデータを圧縮することにより最適な圧縮が得られる。しかしながら、搬送層は非常に複雑であって、ＤＯＳ、ウインドウズ、ＯＳ／２及びＵＮＩＸ（登録商標）のような既存のオペレーティングシステムとインターフェイスする必要があり、従って、圧縮を伴う新たな搬送層を形成するタスクは非常に膨大となる。更に、既存の搬送層は、既に幅広く使用されているので、新たな搬送層を形成しても、既存の搬送層の多数のユーザに自動的に圧縮を与えることにはならない。
【０００８】
ある開発者は、ＭＡＣレベルで圧縮を使用するよう試みている。ある努力は、各パケットごとに搬送ヘッダを圧縮することに限定される。他のものは各パケットにおいてデータを圧縮するが、手前のフレームのデータを使用せずに各パケットを別々に圧縮する。公知システムの中で、信頼性のないリンクを経て手前のフレームのデータに基づいてフレームを圧縮するものはない。更に、公知システムの中で、ＬＺ７７ベースの圧縮を用いて、信頼性のない通信リンクを経て送られるフレームを圧縮するものもない。
【０００９】
本発明の目的は、ＬＺ７７に基づく機構を使用してデータの入力ストリームを圧縮する方法及びシステムを提供することである。
【００１０】
本発明の別の目的は、第１コンピュータにおいて入力ストリームを圧縮し、その圧縮された入力ストリームを第２コンピュータへ送り、そして第２コンピュータにおいてその圧縮されたストリームを圧縮解除する方法及びシステムを提供することである。
【課題を解決するための手段】
【００１１】
本発明のこれら及び他の目的は、以下の詳細な説明から明らかとなるデータ圧縮方法及びシステムによって達成される。好ましい実施例においては、データバイトの入力ストリームが、ＬＺ７７ベースの機構を用いてエンコードされたストリームへと圧縮される。好ましい方法は、バイトの現在シーケンスと同一の既に処理されたデータバイトの一致シーケンスをサーチする。このような同一シーケンスの部分を形成しない各データバイトは、エンコードされたストリームに付加され、このようなデータバイトはリテラルである。一致シーケンスが見つかったときは、この方法は、一致シーケンスの入力ストリームにおける位置と、一致シーケンスにおけるデータバイトの数との両方を識別する一致コードをエンコードされたデータストリームに付加する。この方法は、エンコードされたデータストリームにおける所定数のリテラルのシーケンスを識別し、そしてその識別されたリテラルのシーケンスに、その識別されたシーケンスにおけるリテラルの数を指示するカウント値を付加する。この方法は、エンコードされたデータストリームにおける所定数の一致コードのシーケンスを識別し、そしてその識別された一致コードシーケンスに、その識別された一致コードシーケンスにおける一致コードの数を指示するカウント値を付加する。
【００１２】
好ましくは、入力ストリームは、圧縮装置の円形ヒストリバッファに記憶される。上記方法は、エンコードされたデータストリームを複数のエンコードされたフレームに分割しそして各々のエンコードされたフレームにコヒレンスコードを付加する。上記方法は、各エンコードされたフレームを圧縮解除するための円形ヒストリバッファを有するリモート圧縮解除装置に各エンコードされたフレームを送信する。上記方法は、コヒレンスコードを使用して、圧縮解除装置のヒストリバッファを圧縮装置のヒストリバッファと同期させる。エンコードされたフレームが圧縮解除装置によって受け取られない場合には、その圧縮解除装置はフラッシュ要求を圧縮装置に送信する。圧縮装置は、そのフラッシュ要求に応答してヒストリバッファをフラッシュし、そのフラッシュ段階は、ヒストリバッファに記憶された既に処理されたバイトが一致シーケンスの部分とならないようにする。圧縮装置は、次のエンコードされたフレームのコヒレンスコードに、フラッシュ要求が圧縮装置によって受け取られたかどうかを指示する制御コードを備えている。
【００１３】
好ましい実施例においては、圧縮解除装置は、エンコードされたデータストリームを、入力ストリームと同一の圧縮解除されたストリームへと圧縮解除する。この圧縮解除段階は、一致カウント値を位置決めし、その一致カウント値に等しい多数の一致コードをデコードし、そしてそのデコードされた一致コードを圧縮解除されたストリームに付加するという段階を備えている。又、圧縮解除段階は、リテラルカウント値を位置決めし、そして圧縮解除されたストリームに、そのリテラルカウント値に等しい多数のリテラルを付加することも含む。
【００１４】
（実施例）
本発明は、ＬＺ７７ベースのエンコードを用いて入力データストリームを圧縮データストリームに圧縮するための方法及びシステムを提供する。又、本発明は、圧縮されたストリームを圧縮解除して、入力ストリームと同一の圧縮解除ストリームを形成する方法及びシステムも提供する。好ましい実施例では、入力ストリームは、各バイトが分析された後に円形ヒストリバッファへ順次に挿入される。圧縮システムは、ヒストリバッファをサーチし、現在バイトシーケンスに一致するバイトシーケンスの以前の発生を含んでいるかどうか判断する。ヒストリバッファがこのような一致バイトシーケンスを含んでいる場合には、圧縮システムは、その現在バイトシーケンスを、一致バイトシーケンス及び一致の長さに対するポインタとしてエンコードし、これは、そのエンコードが一致シーケンスを表すことを示す一致フラグを伴う。ヒストリバッファがこのような一致シーケンスを含まないときには、圧縮システムは、現在バイトシーケンスの最初のバイトを、そのバイトが非一致リテラルバイトであることを示すリテラルフラグとともに出力する。好ましくは、圧縮システムは、連続リテラル又は連続一致コードのストリングを識別し、そして一致又はリテラルフラグを各一致又はリテラルと共に出力するのではなく、連続リテラル又は一致コードの数を示すカウント値を出力する。好ましい実施例では、圧縮システムは、ローカルエリアネットワーク（ＬＡＮ）又はワイドエリアネットワーク（ＷＡＮ）のようなコンピュータネットワークに関連して使用される。好ましいネットワークの実施例では、入力ストリームは、限定されたサイズのパケットに分割され、そしてパケットをフレームへと形成するときに各圧縮されたパケットにコヒレンスバイトが付加され、パケットが圧縮されたのと同じ順序でフレームが圧縮解除されるようにする。手前のパケットの後にヒストリバッファの終わりにパケットを完全に適合できない場合には、ラップアラウンドの問題を回避するためにそのパケットはヒストリバッファの始めに挿入されるのが好ましい。
【００１５】
図１は、本発明の好ましい実施例によるデータ圧縮システム１０の全体的なブロック図である。このデータ圧縮システムは、サーバコンピュータ１２を備え、これは、通信リンク１６を経てクライエントコンピュータ１４に接続され、通信リンクは、これらコンピュータ間で圧縮データを搬送する。通信リンク１６は、コンピュータ間にデータを通す任意のリンクでよく、ＬＡＮ用のケーブル或いはＷＡＮ用の電話又はサテライト接続を含む。サーバ及びクライエントコンピュータの各々は、中央処理ユニット（ＣＰＵ）１７Ａ、１７Ｂと、メモリ１８Ａ、１８Ｂと、ネットワークコネクタ２０Ａ、２０Ｂとを備えており、これらはデータバス２２Ａ、２２Ｂによって相互接続される。ネットワークコネクタは各コンピュータを通信リンク１６に物理的に接続し、例えば、モデムは各コンピュータを電話線に物理的に接続する。別のシステムでは、一連の１つ以上のコンピュータが種々の通信リンクを経て物理的に接続され、データは通信リンクを経てあるコンピュータから別のコンピュータへと送られる。従って、このデータ圧縮システムの精神は、２つのコンピュータ又は２つのエンドポイントのみに限定されるものではない。２つ以上の通信リンクがコンピュータへ接続されるかのように１つ以上のコンピュータが通信リンクを経て接続されてもよい。
【００１６】
各メモリ１８Ａ、１８Ｂは、ネットワークコネクタ２０Ａ、２０Ｂを経、通信リンク１６を経て送られるデータを制御するネットワークコントローラ２３Ａ、２３Ｂを記憶する。各ネットワークコントローラ２３Ａ、２３Ｂはレディレクタサーバ２４Ａ、２４Ｂを備え、これは従来の搬送部２６Ａ、２６Ｂに接続され、そしてこの搬送部はメディアアクセスコントローラ（ＭＡＣ）２８Ａ、２８Ｂに接続される。ディレクタは、ＣＰＵ１７Ａ、１７Ｂ及びメモリ１８Ａ、１８Ｂとインターフェイスして、ファイル入力及び出力を与える。搬送部は、サーバコンピュータ１２とクライエントコンピュータ１４との間の確実なデータ通信を確保するもので、ＴＣＰ／ＩＰ、ＩＰＸ／ＳＰＸ及びＮＥＴＢＥＵＩのような従来の搬送部（トランスポート）でよい。又、この搬送部は、コンピュータ間で搬送されるデータを１．５キロバイト以下のような限定されたサイズのパケットに分割する。各パケットに含まれるのは、データを送信するコンピュータのアドレスと、データを受信するように意図されたコンピュータのアドレスとを含む搬送ヘッダである。ＭＡＣは、データ送信を同期すると共に、フレームヘッダをパケットに追加してコンピュータ間に送信するフレームを形成する役目を果たす。フレームヘッダは、同期、フレーム形式、フレーム長さ、及び繰り返し冗長チェック（ＣＲＣ）のためのバイトを含む。良く知られたように、ＣＲＣは、フレーム内のデータに基づいて計算された値であり、受信側ＭＡＣはこれを用いてコンピュータ間の送信中にデータが失われたか又は崩壊したかどうかを決定する。各ＭＡＣは、フレームを形成して送信する前にパケットを圧縮するための圧縮装置３０Ａ、３０Ｂと、フレームを圧縮解除するための圧縮解除装置３２Ａ、３２Ｂとを備えている。
【００１７】
図２及び３は、図１に示された圧縮装置３０Ａ、３０Ｂにより制御される圧縮システム１０のフローチャートである。以下の説明は、入力データストリームがサーバコンピュータ１２において圧縮フレームへと圧縮されそしてその圧縮フレームがクライエントコンピュータ１４へと通されて、そこで、クライエントコンピュータ１４によって圧縮解除される例に向けられる。入力ストリームがクライエントコンピュータにおいて圧縮されて、圧縮解除のためにサーバコンピュータへ通されるときにも同じストリームが生じる。
【００１８】
入力ストリームは、搬送部２６Ａによりメモリ１８Ａに形成された搬送バッファに記憶される。圧縮システム１０は、入力ストリームの第１パケットが圧縮する価値のあるものかどうか判断する（ステップ３４）ことによって開始する。小さなフレームは、典型的に、それらを圧縮するに要する処理時間及び努力を正当化する程度にまで圧縮することはできない。更に、マルチキャスト及びブロードキャスト（放送）フレームは、好ましい実施例では、圧縮されない。というのは、通常は、これらフレームがユーザデータを含まずそして送信又は受信されているフレームの現在データストリームとインターフェイスされるからである。パケットが圧縮する価値のないものである場合には、以下に述べるように、非圧縮フレームとしてフレーム構成されて出力される。
【００１９】
ステップ３４においてパケットが圧縮する価値のあるものであると判断された場合に、ステップ３６において、圧縮システムは、パケットの限定された数のバイト（好ましくは２バイト）のシーケンスを現在バイトシーケンスとして選択する。ステップ３８において、圧縮システムは、バイトシーケンスを記憶するサーチデータ構造において入力ストリームに既に生じている一致シーケンスが見つかるかどうかを判断する。既に生じているバイトシーケンスは、現在バイトシーケンスと同じパケットの一部であるか又は既に処理されたパケットの一部である。サーチ構造において一致シーケンスが見つかった場合には、ステップ４０において、現在バイトシーケンスの第１バイトがメモリ１８Ａに維持された円形ヒストリバッファに挿入される。このヒストリバッファは、８キロバイトのサイズであるのが好ましいが、良好な圧縮を得るためにはそれより大きくすることができ、又はメモリの消費を少なくするためにはそれより小さくすることができる。ステップ４１において、ステップ４１において、ヒストリバッファにおける一致シーケンスに続くバイトが、現在バイトシーケンスに続くバイトと比較され、より長い一致を見つけるように試みられる。
【００２０】
現在バイトシーケンスに続くバイトが、一致シーケンスに続くバイトに一致する場合には、ステップ４０において、現在バイトシーケンスの第２のバイトがヒストリバッファに挿入される。バイトの一致が見つかるたびに、一致シーケンス及び現在バイトシーケンスが一致バイトと共に増大される。ステップ４０及び４１は、現在バイトシーケンスに続くバイトが一致シーケンスに続く対応バイトに一致しないことがステップ４１で決定されるまで繰り返される。ステップ４１で次のバイトが比較される前にステップ４０において各次々のバイトをヒストリバッファに挿入することにより、圧縮システム１０は、一致シーケンスを現在バイトシーケンスに重畳させることができる。
【００２１】
例えば、バイトＡ及びＢがヒストリバッファにおいて位置１及び２に記憶されそして入力ストリームの次の３つのバイトがＡ、Ｂ及びＡであると仮定する。ステップ３８において、圧縮システム１０は、入力ストリームの現在バイトシーケンスにおけるＡＢと一致させるようにヒストリバッファにおけるシーケンスＡＢを見つける。ステップ４０において、現在バイトシーケンスのＡが、一致シーケンスＡＢに続いて位置３においてヒストリバッファに挿入される。ステップ４１において、圧縮システムは、現在バイトシーケンスに続くＡが、ヒストリバッファにちょうど挿入されたＡに一致することを決定する。その結果、一致シーケンスはＡＢＡとなりそして一致シーケンスのＡ（位置３）は現在バイトシーケンスの最初のＡと同じであり、従って、シーケンスが重畳される。ステップ４１において次の比較がなされる前に、ステップ４０において現在バイトシーケンスの最初のＡがヒストリバッファに挿入されなかった場合には、一致シーケンスＡＢＡは見つけられることがない。
【００２２】
ステップ４１において、現在バイトシーケンスに続く次のバイトが、一致シーケンスに続く次のバイトに一致しないことが決定された場合には、ステップ４２において、圧縮システムは、ステップ４１のバイトごとの比較により生じる最も長い一致をエンコードする。使用するエンコード機構は、可変であるのが好ましく、即ち短い一致は、長い一致よりも少数のビットでエンコードされる。このような可変エンコード機構は公知であり、その例は、参考としてここに取り上げる１９８７年ニュージーランドのＰｈ．Ｄ．  Ｔｈｅｓｉｓ、Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｃａｎｔｅｒｂｕｒｙのベル氏著の「ユニフィケーション理論及びテキスト圧縮のための既存の解決策に対する改良(A Unifying Theory and Improvement for Existing Approaches to Text Compression) 」に見ることができる。ステップ４３において、一致した現在バイトシーケンスの最後のバイトがヒストリバッファに挿入される。
【００２３】
公知の圧縮システムにおいては、各エンコードされた一致は、次に続くデータがエンコードされた一致を表すことを示す一致フラグと共にエンコードデータストリームに付加される。各一致フラグの目的は、エンコードされた一致と、一致シーケンスが見つからないときに出力される生のバイト又はリテラルバイトとの間を区別することである。多数の連続するエンコードされた一致がある場合には、各エンコードされた一致間に一致フラグを使用する必要はない。本発明の好ましい実施例では、不必要な一致フラグの少なくとも幾つかが、置き換えられる一致フラグの数を指示するカウント値と置き換えられる。好ましい実施例において、一致カウントをエンコードするのに使用する記憶量は、一致カウントと置き換えられる一致フラグをエンコードするのに使用される記憶量よりも典型的に少ない。
【００２４】
図２のフローチャートに戻ると、圧縮システム１０は、連続するエンコードされた一致の数が所定値Ｘ（例えば、Ｘは好ましい実施例では６に等しい）に達したかどうかをステップ４４において決定する。連続する一致の数がＸ未満の場合には、圧縮システムは、ステップ４９においてエンコードされたデータストリームに一致フラグを付加し、そしてステップ４８においてエンコードされたストリームにエンコードされた一致を付加する。連続する一致の数がＸ以上である場合には、ステップ５０において、圧縮システムは、連続する一致の数がＸに等しいかどうかを決定する。もしそうであれば、ステップ５２において一致カウント０がエンコードされたストリームに付加されそしてステップ４８においてエンコードされた一致がエンコードされたストリームに付加される。一致の値がＸより大きい場合には、ステップ５４において、圧縮システムは、エンコードされたストリームに最も最新に(most recently)付加された一致カウントを増加する。ステップ４８において、圧縮システムは、最大最新エンコードされた一致の直後に、エンコードされたストリームにエンコードされた一致を付加する。
【００２５】
好ましい実施例においては、各一致カウントごとに５ビットが指定される。これら５ビットでは、３２の一致カウント値しか考えられず、従って、０から３１までの一致カウントが考えられる。３１より多い一致が最初のｘ個の一致に続く場合には、３１番目の一致の直後に第２の一致カウントが続く。このように、３１個の一致の各次々のストリングの後に新たな一致カウントが続く。
【００２６】
現在バイトシーケンスに対して一致シーケンスが見つからないときには、公知の圧縮システムは、現在バイトシーケンスの最初のバイトを、一致シーケンスが見つからなかったことを示すリテラルフラグと共に、生のバイト又はリテラルとして出力する。連続する一致により生じる冗長度と同様に、リテラルのストリングの各リテラルと共にリテラルフラグを含むことは不要であり且つ無駄である。好ましい実施例において、リテラルフラグの少なくとも幾つかは、置き換えられるリテラルフラグの数を指示するリテラルカウント値と置き換えられる。好ましい実施例では、リテラルカウントをエンコードするのに使用される記憶量は、典型的に、リテラルカウントにより置き換えられるリテラルフラグをエンコードするのに使用される記憶量よりも少ない。
【００２７】
図２のフローチャートに戻ると、ステップ３８において現在バイトシーケンスのサーチ構造に一致シーケンスが見つからない場合には、圧縮システムは、ステップ５６において連続するリテラルの数が所定値Ｙ（例えば、Ｙは好ましい実施例では６に等しい）より小さいかどうかを判断する。もしそうであれば、ステップ５８においてエンコードされたストリームにリテラルフラグが付加され、そしてステップ６０においてエンコードされたストリームにリテラルが付加される。連続するリテラルの数がＹ未満であることがステップ５６において決定された場合には、圧縮システムは、ステップ６２において連続するリテラルの数がＹに等しいかどうかを決定する。もしそうであれば、リテラルカウント０がステップ６４においてエンコードされたストリームに付加され、そしてリテラルがステップ６０においてエンコードされたストリームに付加される。もしそうでなければ、リテラルの数はＹより大きくなければならず、従って、既に付加されたリテラルカウントがステップ６６において増加されて、Ｙを越える連続リテラルの数を反映するようにする。一致カウントと同様に、好ましい実施例では、各リテラルカウントが０ないし３１（５ビット）に限定され、３１個のリテラルの各次々のストリングの後に新たなリテラルカウントが続く。ステップ６０において、直前のリテラルに続くエンコードされたストリームにリテラルが付加される。ステップ６７では、ステップ６０においてエンコードされたストリームに付加された各リテラルがヒストリバッファに付加されて各リテラルの将来の一致をイネーブルする。
【００２８】
フローチャートは、ステップ６８において図３へと続き、サーチ構造体のエントリがデータバイトの最大最新の発生を指すよう確保するためにサーチ構造体が更新される。この更新は、好ましいサーチ構造体の以下の例の説明から容易に理解されよう。
【００２９】
図４は、好ましい実施例の例示的サーチデータ構造体７０を円形ヒストリバッファ７２に関連して示すブロック図である。円形ヒストリバッファ７２は、この例において文字で表されたデータバイトの入力ストリームの１つ以上のパケットを含んでいる。ヒストリバッファの各文字の上の数字は、ヒストリバッファ内における文字の位置を示している。例えば、文字「ｆ」は、ヒストリバッファ内の１０番目の位置である。
【００３０】
サーチデータ構造体７０は、各々の考えられるバイト値ごとにエントリを含む多次元直接アドレステーブルである。従って、バイトが８ビットを含むときは、このテーブルは２５６個のエントリを含む。例えば、ＡＳＣＩＩ "ａ”のバイト値は６１ｈである。６１ｈによって指示されたエントリは、ＡＳＣＩＩ "ａ”即ちバイト値６１ｈで始まるバイトシーケンスに関するサーチ情報を含む。各エントリは多数のスロットを含む。１つのスロットは、ヒストリバッファにおけるバイトシーケンスの手前の発生を識別する情報を含んでいる。図４の例では、各エントリが４つのスロットを含む。好ましい実施例では、各エントリが８つのスロットを含む。別の実施例では、各エントリは、入力ストリームにおけるバイト値の予想される頻度に基づいて可変数のスロットを有する。当業者に明らかなように、より多くのスロットを使用することにより、より多量の圧縮を得ることができるが、一般的には、より長い圧縮時間がかかることになる。エントリが４つのスロットを含むときには、サーチデータ構造体は、インデックスされたバイト値で始まる４バイトシーケンスに対する情報を含むことができる。各スロットは、次のバイトフィールド７０Ａ及び位置フィールド７０Ｂを含む。次のバイトフィールドはインデックスバイトの後の次のバイトのバイト値を含む。位置フィールドは、ヒストリバッファにおける次のバイトの位置を含む。当業者に明らかなように、次のバイトフィールドは、スピードサーチのために含まれている。次のバイトのバイト値は、位置フィールドをヒストリバッファへのインデックスとして使用することにより得ることができる。
【００３１】
図４に示すように、サーチデータ構造７０は、現在バイトシーケンスが矢印で示すようにヒストリバッファの９番目の位置でスタートするときに手前のバイトシーケンスの情報を含む。ヒストリバッファの最初の８バイトは、一致バイトシーケンスを含まない。”ａ”のサーチデータ構造体は、”ａ”で始まる４つの手前のバイトシーケンスの各々、即ち”ａｄ”、”ａｃ”、”ａｂ”及び”ａｅ”を識別するスロットを含んでいる。位置９及び１０の”ａｆ”である現在バイトシーケンスが処理されるときには、サーチデータ構造体７０は、”ａｆ”が手前のバイトシーケンスとして識別されるかどうか判断するためにサーチされる（図２のステップ３８）。この例において、”ａ”によりインデックスされたエントリに対するスロットで、次のバイト値として”ｆ”を含むものはない。従って、圧縮システムは、最も最新でなく(least recently)更新された文字”ａ”に対するスロットをオーバーライトする。この場合に、バイトシーケンス”ａｄ”を識別するスロットは、現在バイトシーケンス”ａｆ”を識別する情報と置き換えられる。より詳細には、次のバイトフィールドは”ｆ”でオーバーライトされ、そして位置フィールドは１０でオーバーライトされる。”ａ”で始まる次のバイトシーケンス、位置１１の”ａｅ”、に遭遇すると、圧縮システムは、一致シーケンス、即ち手前のバイトシーケンス”ａｅ”を識別する”ａ”でインデックスされたエントリの入力をサーチする。第４のスロットは”ｅ”を含むので、一致シーケンスが見つかる。第４のスロットは、一致シーケンスの最後のバイト（”ｅ”）の位置として位置８を指す。圧縮システムは、位置１３のバイトを位置９のバイトと比較することにより一致シーケンスを拡張するように試み、そして一致シーケンス”ａｅａ”を見つける（図２のステップ４０）。圧縮システムは、位置１４のバイトを位置１０のバイトと比較するが、一致シーケンスを拡張することはできない。圧縮システムは、現在バイトシーケンス”ａｅａ”を一致コードとして表し、この一致コードは、（７、３）と表された一致コードの場合に、位置７で始まる位置シーケンス”ａｅａ”に対するポインタと、一致シーケンスの長さのカウント値とを含む（図２のステップ４２）。繰り返し一致コードをチェックした後（ステップ４４）、圧縮システムは、一致コード及び一致フラグをエンコードされたストリームに付加する（ステップ４６、４８）。圧縮システムは、４番目のスロットの位置を位置１２と置き換えることによりサーチ構造体７０を更新し、現在バイトシーケンスを識別する（ステップ６８）。
【００３２】
ＬＲＵ（least recently used：最長時間未使用法）データ構造体７４は、各バイト値ごとにエントリを含み、そしてバイト値によってインデックスされる。エントリは、サーチデータ構造体における対応エントリーに対してもっとも長期間更新されていないスロットを識別する。ＬＲＵ構造体（図示された）は、実際には、最も最新に更新されたスロットのスロット番号（０・・・３）を含む。もっとも長期間更新されていないスロットは、ＬＲＵエントリの値に１を加えることによって得られる。例えば、”ａ”に対するもっとも長期間更新されていないスロットは、スロット０であり、従って、ＬＲＵデータ構造体は３（３＋１ｍｏｄ４＝０）を含む。現在バイトシーケンスがサーチデータ構造体におけるいずれのバイトシーケンスにも一致しない場合には、ＬＲＵは、次のスロットを指すように更新され（円形の形態で）、そして次のスロットは、現在バイトシーケンスの第１バイト及び位置でオーバーライトされる。当業者に明らかなように、もっとも長期間更新されていないスロットの推定は、位置の値が最も小さいスロットを選択し、ひいては、ＬＲＵデータ構造体を不要とすることによって行うことができる。
【００３３】
別の実施例では、バイトシーケンスは、いかなる数のバイトでもよい。サーチデータ構造体は、２つのバイトによってインデックスされる直接アクセステーブルとして実施することができ、従って、２16のエントリを有する。或いは又、サーチデータ構造体は、ハッシュテーブルとして実施することもできる。ハッシュテーブルが使用されるときには、異なる第１バイトをもつバイトシーケンスを同じエントリに対してハッシュし、衝突を生じることがある。衝突が生じると、スロットによって識別された各バイトシーケンスの第１バイトをチェックして一致を判断することが必要である。別の実施例では、各エントリに対するスロットをリンクされたリストとして維持することができる。リンクされたリストは、入力ストリームにおける各バイトごとにスロットをもつ入力ストリームに平行なアレーとして実施することができる。サーチデータ構造体の各エントリは、次のバイト値を識別するスロットのリンクされたリストを指す。リンクされたリストにおけるスロットは、同じ第１バイトに対して次のバイト値を一緒にリンクする。リンクされたリストをサーチするときには、ある数のスロットのみが一致に対してチェックされる。一致が見つからなかったときには、リンクされたリストの開始に新たなスロットが付加され、現在バイトシーケンスを識別する。一致スロットが見つかったときには、リンクされたリストからそれが除去され、そしてリンクされたリストの始めに新たなスロットが加えられて、現在バイトシーケンスを識別するのが好ましい。
【００３４】
図３に戻ると、ステップ７６において、圧縮システム１０は、パケットに端に達したかどうかを判断する。もしそうでなければ、圧縮システムは、新たな現在バイトシーケンスでステップ３６ないし６８をループする。最も最新の現在バイトシーケンスが一致を生じない場合は、新たな現在バイトシーケンスが手前の現在バイトシーケンスの第２バイトで開始する。手前の現在バイトシーケンスが一致を生じた場合には、現在バイトシーケンスは、手前の現在バイトシーケンスに続く第１バイトで始まる（ステップ４１のバイトごとに比較で見つかった一致バイトによって増大される）。
【００３５】
圧縮システムの好ましい実施例は、ネットワークに関連して使用されるので、特に、ＷＡＮを使用するときには、サーバコンピュータ１２からクライエントコンピュータ１４への送信中に、エンコードされたフレームの全部又は一部分が失われるという明らかなおそれがある。公知のネットワーク圧縮システムは、圧縮プログラムと共にメディアアクセスコントローラ（ＭＡＣ）に保証された付与機構を設けることにより、フレーム脱落の問題を軽減すると考えられている。このような公知の機構は、１つ以上のフレームを受け取った後に受信側ＭＡＣが送信側ＭＡＣに確認を返送することを必要とする。このような付与保証機構は、著しい送信時間を浪費し、ＭＡＣを不必要に複雑にする。更に、ネットワーク搬送部は、既に付与を保証しており、従って、ＭＡＣ付与保証は冗長となる。このように、搬送部は、フレームを再送するが、メディアアクセスコントローラも同じことを行うように試み、従って、フレームは２回送信される。
【００３６】
ＭＡＣ２８Ａに付与保証機構を含ませるのではなくて、圧縮システム１０は、単に搬送部２６Ａ、２６Ｂに基づいて付与を確保する。これは、各フレームが手前のフレームのデータに基づいて圧縮されるという点で問題を生じるが、搬送部２６ＡはＭＡＣ２８Ａの上に置かれているので、搬送部がＭＡＣ２８ＡからＭＡＣ２８Ｂへの付与を保証する方法はなく、搬送部２６Ａから搬送部２６Ｂへ保証するだけである。従って、何の手段もとらない場合には、圧縮解除装置がその後のフレームを圧縮するように試みるが、脱落したフレームは圧縮解除装置のヒストリバッファに入っていないので、圧縮解除装置はその後のフレームを正確に圧縮解除することはできない。この潜在的な問題を補償するために、圧縮システム１０は、コヒレンスバイトを各フレームに追加し、圧縮解除装置のヒストリバッファが圧縮装置のヒストリバッファと同期されたままにする。
【００３７】
図３に戻ると、圧縮システム１０がステップ７６においてパケットの終わりに達したと判断した場合には、圧縮システムは、ステップ７８においてＣＲＣ及びコヒレンスバイトを含むフレームバッファを追加することによってパケットをフレーム構成し、フレームを形成する。ステップ８０において、フレームは、通信リンク１６を経てクライエントコンピュータの圧縮解除装置３２Ｂへ送られる。ステップ８２において、圧縮装置１０は、全てのパケットが処理されたかどうかを判断する。もしそうならば、圧縮システムは終了となり、システムがデータをコンピュータ間に送信させるところに実行復帰する。
【００３８】
処理すべきパケットが更にある場合には、圧縮システム１０は、ステップ８６において、圧縮解除装置からフラッシュ要求が受け取られたどうかを判断する。このようなフラッシュ要求は、フレームが乱れた状態で受け取られた場合に圧縮解除装置３２Ｂによって発生され、これは、フレームが送信中に脱落したことを示す非順次コヒレンスバイトによって指示される。このようなフラッシュ要求を受け取った場合には、圧縮装置３０Ａは、ステップ８８において、ヒストリバッファに現在あるバイトを無効化することによりそのヒストリバッファをフラッシュする。ステップ９０において、圧縮システムは次のコヒレンスバイトをセットし、フラッシュ要求が受け取られたことを指示すると共に、コヒレンスバイトと共に送られるべきフレームがリセットヒストリバッファで圧縮されたことを指示する。ステップ９２において、圧縮システムはフラグをセットし、次のパケットの各バイトを、それが一致に対して分析された後に、ヒストリバッファの始めに挿入し、手前のパケットを参照せずに次のパケットが圧縮されるようにすべきであることを指示する。
【００３９】
ステップ８６においてフラッシュ要求が受け取られない場合には、次いで、ステップ９４において、圧縮システム１０は、直前のパケットの後の次のパケットのためにヒストリバッファに充分なスペースがあるかどうかを判断する。もしそうならば、ステップ９６において、圧縮システムはフラグをセットして、次のパケットの各バイトを、それが一致に対して分析された後に、その手前のパケットの直後にヒストリバッファに挿入しなければならないことを指示する。もしそうでなければ、ステップ９２において、フラグがセットされて、次のパケットの各バイトを、それが一致に対して分析された後に、ヒストリバッファの開始に挿入しなければならないことを指示する。次のパケットを、それがバッファの終わりに完全に適合できないときにバッファの始めに挿入することにより、圧縮システムは、一致シーケンスをヒストリバッファの終わりから始めへと続けることに関連したラップアラウンドの問題を回避する。このようなラップアラウンドの問題は、ヒストリバッファ内に留めるために圧縮及び圧縮解除中にバッファの終わりに達したかどうかを常にチェックしなければならないことを含む。次のパケットをヒストリバッファに挿入した後に、プロセスは、入力ストリームの全てのパケットが処理されてしまうまでステップ３６ないし９２を経てループする。
【００４０】
図５及び６は、圧縮解除装置３２Ｂによって制御される圧縮システム１０の圧縮解除セクションを示すフローチャートである。ステップ９８において、圧縮解除装置３２Ｂは、圧縮装置３０Ａからフレームを受け取る。ステップ１００において、圧縮解除装置は、圧縮装置３０Ａからフラッシュ要求が受け取られたかどうかを判断する。このようなフラッシュ要求が受け取られた場合には、ステップ１０２において、圧縮解除装置は、ヒストリバッファに現在あるバイトを無効化することによりヒストリバッファをフラッシュする。ステップ１０４では、圧縮解除装置は、次のコヒレンスバイトをセットして、フラッシュ要求が受け取られたことを指示すると共に、コヒレンスバイトと共に送られたフレームがリセットヒストリバッファで圧縮解除されたことを指示する。ステップ１０６において、圧縮解除装置はフラグをセットし、次のフレームの各バイトを、それが圧縮解除された後に、ヒストリバッファの始めに挿入して、手前のフレームを参照せずに次のフレームが圧縮解除されるようにすべきであることを指示する。
【００４１】
ステップ１００においてフラッシュ要求が受け取られない場合には、ステップ１０８において、圧縮解除装置３２Ｂは、その直前のフレームの後の次のフレームに対しヒストリバッファに充分なスペースがあるかどうか判断する。もしそうであれば、ステップ１１０において、圧縮解除装置はフラグをセットし、次のパケットの各バイトを、それが圧縮解除された後に、その手前のフレームの直後にヒストリバッファに挿入しなければならないことを指示する。もしそうでなければ、ステップ１０６では、フラグがセットされて、次のパケットの各バイトを、それが圧縮解除された後に、ヒストリバッファの始めに挿入しなければならないことを指示する。このようなバッファチェックは、圧縮解除装置のヒストリバッファを圧縮装置のヒストリバッファと同期状態に保持する。
【００４２】
ステップ１１２において、圧縮解除装置は、フレームのコヒレンスバイトの逐次番号をチェックすることにより、受け取ったフレームが正しい逐次の順序にあるかどうかを判断する。逐次番号が正しくない場合には、圧縮解除装置は、サーバコンピュータ１２とクライエントコンピュータ１４との間の送信中にフレームが脱落したかどうか判断する。ステップ１１４において、圧縮解除装置は、圧縮装置にフラッシュ要求を発生し、これは、圧縮装置に、次のパケットを圧縮する前にそのヒストリバッファをリセットするように告げる。次いで、圧縮解除装置は、ステップ９８において次のフレームを受け取るように復帰する。
【００４３】
図７は、サーバコンピュータ１２とクライエントコンピュータ１４との間で送信されるフレームの例を示すタイミング図である。フレーム１ないし４は、各々逐次コヒレンスバイト００ないし０３と共に送信される。フレーム１及び２は、クライエントコンピュータにより誤りなく受け取られるが、フレーム３は、クライエントコンピュータによって正しく受け取られない。クライエントコンピュータは、指定の時間内にフレームを受け取らないか、又はフレームは受け取るが、ＣＲＣがそのフレーム内のデータに一致しないと判断することにより、フレームが脱落したことを検出する。脱落したフレームに応答して、クライエントコンピュータは、ＦＦのようなフラッシュ要求コヒレンスバイトをもつ制御フレームを送信することにより、サーバコンピュータにフラッシュ要求を送信する。送信遅延があるために、クライエントコンピュータから送られたフラッシュ要求は、サーバコンピュータがフレーム４をクライエントコンピュータに送信した後まで、サーバコンピュータによって受け取られない。このように、クライエントコンピュータは、コヒレントバイト（０３）をもつフレーム４を受け取り、これは、サーバコンピュータの圧縮ヒストリバッファがフラッシュされたことを確認するものではない。その結果、クライエントコンピュータは、フレーム４が乱れていると判断し、これを圧縮解除しない。サーバコンピュータは、コヒレンスバイトの上位ニブルが１に変化したフレーム５を送信し、これは、サーバの圧縮ヒストリバッファがフラッシュされたことを指示すると共に、フレーム５がフレーム１ないし４を参照せずに圧縮されたことを指示する。クライエントコンピュータは、フレーム５を受け取ると、コヒレンスバイトの上位ニブルの１を、バッファフラッシュの指示として確認し、そしてクライエントコンピュータは、サーバコンピュータのフラッシュされた圧縮ヒストリバッファに一致するようにその圧縮解除ヒストリバッファがフラッシュされた状態でフレーム５を圧縮解除する。
【００４４】
コヒレンスバイトは常に厳密な逐字の順序ではないことを理解されたい。図７に示すように、フレーム７は、コヒレンスバイト１２ではなくてコヒレンスバイト７Ｅと共に送信され、これは、フレーム６のコヒレンスバイト１１の後に順次に続くものである。このコヒレンスバイト７Ｅは、小さなマルチキャスト及びブロードキャストフレームのような好ましくは圧縮されないフレームに対して指定されるものである。
【００４５】
又、図７は、フレームがクライエントコンピュータからサーバコンピュータへ送信される間にフレームをサーバコンピュータ１２からクライエントコンピュータ１４へ送信する好ましい圧縮システムの能力も示している。クライエントコンピュータへ送られるフレームは、通常、フレームが脱落したとき以外は、サーバコンピュータによって受け取られるフレームとは個別に処理される。例えば、サーバコンピュータは、時にはフレーム１０が送信される前に、クライエントコンピュータからサーバコンピュータへの送信中にフレームＢが脱落したと判断する。逐次コヒレンスバイト１４と共にフレーム１０を送信しそしてフラッシュ要求コヒレンスバイトと共に個別の制御フレームを送信するのではなく、サーバコンピュータは、フレーム１０のコヒレンスバイトをフラッシュ要求コヒレンスバイトと合成して、コヒレンスバイト９４を発生する。クライエントコンピュータはフレーム１０を受け取り、そしてフレーム１０が適切な逐次順序にあること及びそれがフラッシュ要求と結合されたことを検出する。その結果、クライエントコンピュータは、その圧縮ヒストリバッファをフラッシュし、そしてフレームＣをコヒレンスバイト１０と共に送信する。その上位ニブルの１は、バッファがフラッシュされたことを指示し、そしてその下位ニブルの０は、フレームの新たな数字順序のスタートを指示する。
【００４６】
圧縮解除のフローチャートは、図６へと続き、フレームが適切な順序で受け取られた場合に、圧縮解除装置は、ステップ１１６において所定数（Ｙ）のリテラル（好ましい実施例では、Ｙは６に等しい）のシーケンスを既に処理したかどうかを判断する。リテラルのシーケンスが処理された場合には、ステップ１１８において、圧縮解除装置は、リテラルのシーケンスにおいてＹを越えるリテラルの数を指示するカウント値（Ｌ）を得る。ステップ１２０において、圧縮解除装置は、次のＬバイトをリテラルとして出力する。ステップ１２２において、圧縮解除装置は、Ｌリテラルの直後の一致をデコードする。一致フラグをもたない一致は常にリテラルのストリングに続くことを想起されたい。というのは、別のリテラルがリテラルのストリングに続く場合に、そのリテラルがリテラルのストリングの一部となるからである。ステップ１２４において、圧縮解除装置は、デコードされた一致を出力する。
【００４７】
長さＹのリテラルのシーケンスがない場合は、ステップ１２６において、圧縮解除装置は、所定数（Ｘ）の一致コードのシーケンスがあるかどうかを判断する（好ましい実施例では、Ｘは６に等しい）。もしあれば、ステップ１２８において、圧縮解除装置は、一致コードのシーケンスにおいてＸより大きな一致コードの数を指示するカウント値（ｍ）を得る。ステップ１３０において、圧縮解除装置は、サーバコンピュータ１２の圧縮ヒストリバッファと同一に維持された圧縮解除ヒストリバッファにおける一致シーケンスをサーチすることにより、Ｍ個の連続する一致コードをデコードする。圧縮解除ヒストリバッファにおける各一致シーケンスの開始部を見つけた際に、圧縮解除装置は、各エンコードによって示されたバイトの数を単にカウントし、そしてステップ１３２においてデコードされた一致を出力する。ステップ１３４において、圧縮解除装置は、Ｍ個の一致の直後のリテラルを出力する。
【００４８】
一致コード又はリテラルのシーケンスがない場合には、圧縮解除装置は、ステップ１３６において、次のビット（１つ又は複数）にリテラルフラグが見つかったかどうか（各フラグにおけるビットの数に基づいて）判断する。もしそうであれば、ステップ１３４において、圧縮解除装置はリテラルを出力する。もしそうでなければ、次のビットは一致フラグでなければならず、ステップ１２２において、圧縮解除装置は、一致フラグに続く一致コードをデコードし、そしてステップ１２４においてそのデコードされた一致を出力する。
【００４９】
ステップ１２０、１２４、１３２及び１３４においてリテラル又は一致を出力した後に、圧縮解除装置は、ステップ１３８において現在フレームの終わりに達したかどうか判断する。もしそうでなければ、エンコードされたフレームの次のセクションに対しステップ１１６ないし１３８を経て実行がループする。フレームの終わりに達すると、圧縮解除装置は、全てのフレームが処理されたかどうか判断する（ステップ１４０）。受け取るべきフレームがもっとある場合は、圧縮解除装置は、次のフレームに対しステップ９８ないし１４０を経てループする。全てのフレームが処理されたときには、圧縮解除装置は終了となり、ステップ１４２において、クライエントコンピュータのオペレーティングシステムに実行を復帰する。
【００５０】
上記したように、圧縮システム１０は、手前のパケットの後に新たなパケットをヒストリバッファの終わりに適合できないときにその新たなパケットをヒストリバッファの始めに挿入するのが好ましい。別の実施例では、バッファの終わりに適合しない新たなパケットの部分のみがバッファの始めに挿入される。圧縮システムは、ヒストリバッファの終わりの直後に続く拡張バッファセクションを予め割り当てる。パケットがヒストリバッファに完全に適合しない場合には、その適合しないパケットの部分がその拡張されたバッファセクションに挿入される。これは、ヒストリバッファの終わりに生じる現在バイトシーケンスをその拡張されたバッファセクションへと延ばして、圧縮装置が現在バイトシーケンスを圧縮する間にバッファの始めへとラップアラウンドしなくてもよいようにする。拡張されたバッファへと延びるパケットの部分は、そのパケットの圧縮が完了した後に更に別の圧縮のためにヒストリバッファの始めへとコピーされる。
【００５１】
別の実施例が図６に示されている。図６には、８Ｋの円形ヒストリバッファ１４４と、このヒストリバッファの終わりの直後に配置された１．５Ｋ拡張バッファ１４６とが示されている。パケット１ないし５は、ヒストリバッファに既に挿入されており、そして上記したように圧縮されている。圧縮されるべき次のパケットは、長さが１．５Ｋのパケット６である。圧縮システムは、パケット６の最初の０．５Ｋバイトをパケット５の直後にヒストリバッファに挿入し、そしてパケット６の残りの１Ｋを拡張したバッファに挿入する。パケット６の最初の４９９バイトは上記したように正常に圧縮されると仮定する。このように、現在バイトシーケンスは、ヒストリバッファの最後のバイトで始まり、そして拡張されたバッファへと延びる。拡張されたバッファは、現在バイトシーケンスがヒストリバッファを越えて延びる事実を圧縮システムが無視できるようにすると共に、拡張された一致シーケンスが見つかった場合に現在バイトシーケンスを必要なだけ増大できるようにする。例えば、位置７９９９（ヒストリバッファの最終位置）及び８００４から延びる現在バイトシーケンスに対して一致が見つかった場合には、ヒストリバッファの始めへラップアラウンドせずに一致を見つけてエンコードすることができる。パケット６の次の現在バイトシーケンスがヒストリバッファ内で始まらないとすれば、パケット６の最後の１Ｋバイトがヒストリバッファの始めへ挿入され、これにより、パケット１の最初の１Ｋバイトをオーバーライトする。それ故、次の現在バイトシーケンスは、ヒストリバッファ内で位置５のバイト（手前の現在バイトシーケンスの終了の直後に続くバイト）で始まり、そして圧縮は通常通りに進められる。
【００５２】
以上の説明から、本発明の特定の実施例について説明したが、本発明の精神及び範囲から逸脱せずに種々の変更がなされ得ることが明らかであろう。従って、本発明は、特許請求の範囲によってのみ限定されるものとする。
【図面の簡単な説明】
【００５３】
【図１】本発明によるデータ圧縮システムのブロック図である。
【図２】本発明によるデータ圧縮方法のフローチャートの一部分を示す図である。
【図３】本発明によるデータ圧縮方法のフローチャートの残り部分を示す図である。
【図４】図２及び３に示された圧縮方法に用いる好ましいサーチデータ構造体のブロック図である。
【図５】図１に示すデータ圧縮システムによって使用するデータ圧縮解除方法のフローチャートの一部分を示す図である。
【図６】図１に示すデータ圧縮システムによって使用するデータ圧縮解除方法のフローチャートの残り部分を示す図である。
【図７】図１に示すシステムに用いられるヒストリバッファを同期する方法を示すタイミング図である。
【図８】本発明の別の実施例に用いられるデータ記憶構造体のブロック図である。
【符号の説明】
【００５４】
１０  データ圧縮システム
１２  サーバコンピュータ
１４  クライエントコンピュータ
１６  通信リンク
１７Ａ、１７Ｂ  中央処理ユニット
１８Ａ、１８Ｂ  メモリ
２０Ａ、２０Ｂ  ネットワークコネクタ
２２Ａ、２２Ｂ  バス
２３Ａ、２３Ｂ  ネットワークコントローラ
２４Ａ、２４Ｂ  レディレクタサーバ
２６Ａ、２６Ｂ  搬送部
２８Ａ、２８Ｂ  メディアアクセスコントローラ（ＭＡＣ）
３０Ａ、３０Ｂ  圧縮装置
３２Ａ、３２Ｂ  圧縮解除装置
【図１】
2007243959.tif 000003
【図２】
2007243959.tif 000004
【図３】
2007243959.tif 000005
【図４】
2007243959.tif 000006
【図５】
2007243959.tif 000007
【図６】
2007243959.tif 000008
【図７】
2007243959.tif 000009
【図８】
2007243959.tif 000010
【手続補正書】
【提出日】平成19年4月11日(2007.4.11)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
パケット当たりｍ以下のデータバイトを有するパケットに分割されたデータバイトの入力ストリームを受信する処理と、
ｍより大きなサイズｎの円形ヒストリバッファに１つ以上のパケットを順次に挿入する処理と、
直前のパケットが前記ヒストリバッファに挿入された後、ヒストリバッファの終端に残っているバイトがｘ未満であるときにヒストリバッファの先頭のｘバイトにサイズｘのパケットを挿入する処理と、
既に処理されたデータバイトの中で現在のバイトストリングに一致する一致ストリングを見つけるためにサーチする処理と、
このような一致ストリングの部分を形成しない各データバイトをエンコードされたデータストリームに追加する処理と、このようなデータバイトはリテラルであり、
前記入力ストリームにおける前記一致ストリングの位置と、前記一致ストリングにおけるデータバイトの数との両方を識別する一致コードを、前記エンコードされたデータストリームに追加する処理と、を含むデータ圧縮方法。
【請求項２】
パケット当たりｍ以下のデータバイトを有するパケットに分割されたデータバイトの入力ストリームを受信する処理と、
ｍより大きなサイズｎの円形ヒストリバッファに１つ以上のパケットを順次に挿入する処理と、
前記ヒストリバッファの終端の直後にｍ−１バイトのオーバーフロー記憶領域を提供する処理と、
前記直前のパケットが前記ヒストリバッファに挿入された後、当該ヒストリバッファに残っているスペースがｙバイトであるときに、前記ヒストリバッファにｘバイトのパケットのうちのｙバイトを挿入する処理と、
前記ｘバイトのパケットのうちのｘ−ｙバイトを前記オーバーフロー記憶スペースに挿入する処理と、
前記ｘバイトのパケットのうちのｘ−ｙバイトを前記ヒストリバッファの先頭のｘ−ｙバイトにコピーする処理と、
既に処理されたデータバイトの中で現在のバイトストリングに一致する一致ストリングを見つけるためにサーチする処理と、
このような一致ストリングの部分を形成しない各データバイトをエンコードされたデータストリームに追加する処理と、このようなデータバイトはリテラルであり、
前記入力ストリームにおける前記一致ストリングの位置と、前記一致ストリングにおけるデータバイトの数との両方を識別する一致コードを、前記エンコードされたデータストリームにｒする処理と、を含むデータ圧縮方法。
【請求項３】
入力ストリングのシーケンスを圧縮するためのデータ圧縮方法であって、
前記入力ストリングのシーケンスを受信する処理と、
前記入力ストリングのシーケンスのうちの複数の入力ストリングそれぞれについて、
(i)前記入力ストリングを圧縮装置のヒストリバッファに記憶する処理と、
(ii)前記ヒストリバッファに記憶されている既に処理された１以上の一致ストリングに基づき、前記入力ストリングをエンコードする処理と、
(iii)前記エンコードされたストリングをリモート圧縮解除装置へ送信する処理と、
前記エンコードされたストリングが前記圧縮解除装置によって正しく受信されない場合、当該圧縮解除装置からのフラッシュ(flush)要求を受信する処理と、
前記フラッシュ要求に応答してヒストリバッファをフラッシュする処理であって、前記ヒストリバッファに既に記憶されている入力ストリングが、一致ストリングの一部分になり得ないようにする該フラッシュ処理と、
前記フラッシュ要求を受信するより前にエンコードされた任意の入力ストリングを参照することなく、前記フラッシュ要求を受信した後で入力ストリングをエンコードする処理と、
前記エンコードされた入力ストリングを前記圧縮解除装置に送信する処理と、を含むことを特徴とするデータ圧縮方法。
【請求項４】
エンコードされた各ストリングにコヒーレンス・コード(coherency code)を追加する処理をさらに含み、当該コヒーレンス・コードは、フラッシュ要求を受け取ったかどうかを示す制御コードと、エンコードされたストリングのシーケンス中のどこに前記エンコードされたストリングが配置されているかを示すシーケンシャル・コードと、を含むことを特徴とする請求項３に記載の方法。
【請求項５】
各入力ストリングがデータバイトを含み、そして、
前記エンコード処理が、
前記入力ストリングに一致する処理済みの一致ストリングについて前記ヒストリバッファをサーチする処理と、
同一ストリングにおいて部分を形成しない各データバイトを、エンコードされたデータストリームに追加する処理と、そのようなデータバイトはリテラルであり、
前記ヒストリバッファにおける前記一致ストリングの位置と、前記一致ストリングにおけるデータバイト数との両方を識別する一致コードを、前記エンコードされたデータストリームに追加する処理と、
前記エンコードされたデータストリームにおいて所定数の一致コードシーケンスを識別するとともに、前記識別された一致コードシーケンスの一致コードの数を示すカウント値を、前記識別された一致コードシーケンスに追加する処理とを含むことを特徴とする請求項３に記載の方法。
【請求項６】
前記エンコードされたデータストリームにおいて、一致コードシーケンスの部分を形成しない一致コードの隣に一致コードフラグを追加する処理と、
一致コードフラグを各一致コードシーケンスに追加する処理と、をさらに含むことを特徴とする請求項５に記載の方法。
【請求項７】
前記エンコードされたデータストリームを前記圧縮解除装置に送信する処理と、
前記エンコードされたデータストリームを圧縮解除後のストリーム中へ圧縮解除する処理であって、前記入力バイトのシーケンスと前記圧縮解除後のストリームとは同一である該処理と、をさらに含むことを特徴とする請求項５に記載の方法。
【請求項８】
前記圧縮解除の処理は、
一致コードの数を示す一致カウント値を見つけ出し(locate)、
前記一致カウント値に等しい数の一致コードをデコード(decode)し、
前記デコードされた一致コードを前記圧縮解除されたストリームへ追加する、ことを含む請求項７に記載の方法。
【請求項９】
各入力ストリングはデータバイトを含み、かつ前記入力ストリングのシーケンスはせいぜい１パケットあたりｍデータバイトを有する１以上のパケットに分割され、
前記方法は、１以上のパケットを、ｍより大きいサイズｎの円形ヒストリバッファに順次挿入する処理をさらに含むことを特徴とする請求項３に記載の方法。
【請求項１０】
前記ヒストリバッファに直前のパケットが挿入された後、前記ヒストリバッファの終端にｘバイト以上残っていない場合、サイズｘのパケットを前記ヒストリバッファの先頭のｘバイトに挿入する処理をさらに含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記ヒストリバッファの終端の直後にｍ−１バイトのオーバーフロー記憶スペースを設ける処理と、
前記直前のパケットが前記ヒストリバッファに挿入された後、当該ヒストリバッファに残っているスペースがｙバイト存在するときは、ｘバイトのパケットうちのｙバイトを前記ヒストリバッファに挿入する処理と、
前記ｘバイトのパケットのうちのｘ−ｙバイトを、前記オーバーフロー記憶スペースに挿入する処理と、
前記ｘバイトのパケットのうちのｘ−ｙバイトを、前記ヒストリバッファの最初のｘ−ｙバイトにコピーする処理と、をさらに含むことを特徴とする請求項９に記載の方法。
【請求項１２】
各入力ストリングはデータバイトを含み、かつ前記入力ストリングのシーケンスはせいぜい１パケットあたりｍデータバイトを有する１以上のパケットに分割され、
前記方法は、所定最少数のデータバイトよりも少ないパケットかどうかを判断する処理と、
前記パケットが前記所定最少数のデータバイトよりも少ないと判断された場合に、同一データバイトのストリングをサーチすることなく、前記圧縮解除装置へ前記パケットを送信する処理をさらに含むことを特徴とする請求項３に記載の方法。
【請求項１３】
データバイトの入力ストリームを受信する処理と、
既に処理されたデータバイトのうち、現在のデータバイトストリングに一致する一致ストリングをサーチする処理と、
このような一致ストリングの部分を形成しない各データバイトをエンコードされたデータストリームに追加する処理と、このようなデータバイトはリテラルであり、
前記入力ストリームにおける前記一致ストリングの位置と、前記一致ストリングにおけるデータバイトの数との両方を識別する一致コードを、前記エンコードされたデータストリームに追加する処理と、
前記エンコードされたデータストリームにおいて一致コードのシーケンスを識別するとともに、当該識別された一致コードシーケンスの一致コードの数を示すカウント値をその識別された一致コードシーケンスに追加する処理と、を含むことを特徴とするデータ圧縮方法。
【請求項１４】
前記エンコードされたデータストリームをリモート圧縮解除装置へ送信する処理と、
前記エンコードされたデータストリームを圧縮解除後のストリーム中へ圧縮解除する処理であって、前記入力ストリームと前記圧縮解除後のストリームとは同一である該処理と、を更に含んだ請求項１３に記載の方法。
【請求項１５】
前記圧縮解除の処理は、
一致コードの数を示す一致カウント値を見つけ出し(locate)、
前記一致カウント値に等しい多数の一致コードをデコード(decode)し、
前記デコードされた一致コードを前記圧縮解除されたストリームに追加する、ことを含む請求項１４に記載の方法。
【請求項１６】
各一致コードシーケンスに一致コードフラグを追加する処理を更に含むことを特徴とする請求項１３に記載の方法。
【請求項１７】
前記入力ストリームはせいぜい１パケットあたりｍデータバイトを有する１以上のパケットに分割され、前記方法は、更に、
所定最少数のデータバイトよりも少ないパケットかどうかを判断する処理と、
前記パケットが前記所定最少数のデータバイトよりも少ないと判断された場合に、同一データバイトのシーケンスをサーチすることなく、前記エンコードされたデータストリームへ前記パケットを送信する処理を含むことを特徴とする請求項１３に記載の方法。
【請求項１８】
前記一致コードのシーケンスを識別する処理は、所定数の連続一致コードを識別することを含み、そして当該所定数の連続一致コードに続く前記カウント値が、前記一致コードシーケンスにおける一致コード数を示している、請求項１３に記載の方法。
【請求項１９】
一致コードフラグを追加する処理は、リテラルのシーケンスの直後に前記一致コードが続かない場合のみ、前記エンコードされたデータストリームにおいて、一致コードシーケンスの部分を形成しない各一致コードの隣に一致コードフラグを追加することを含む、請求項１６に記載の方法。
【請求項２０】
データバイトの入力ストリームを圧縮装置の円形ヒストリバッファに記憶する処理と、
既に処理されたデータバイトの中で現在のバイトストリングに一致する一致ストリングを見つけるために前記円形ヒストリバッファをサーチする処理と、
同一ストリングの部分を形成しない各データバイトを、エンコードされたデータストリームに追加する処理と、このようなデータバイトはリテラルであり、
前記ヒストリバッファにおける前記一致ストリングの位置と、前記一致ストリングにおけるデータバイト数との両方を識別する一致コードを、前記エンコードされたデータストリームに追加する処理と、
前記エンコードされたデータストリームを複数のフレームに分割する処理と、
コヒーレンス・コード(coherency code)を各フレームに追加する処理であって、当該コヒーレンス・コードは、前記フレームがエンコードされているかどうか、そしてエンコードされている場合は、そのコヒーレンス・コードがエンコードフレーム・シーケンス内でのフレームの位置を示すシーケンス数を含んでいる当該追加処理と、
各エンコードフレームを圧縮解除するための円形ヒストリバッファを有するリモート圧縮解除装置に、各エンコードフレームを送信する処理と、
前記コヒーレンス・コードを用いて、前記圧縮解除装置の円形ヒストリバッファと、前記圧縮装置の円形ヒストリバッファとを同期させる処理と、を含むことを特徴とするデータ圧縮方法。
【請求項２１】
エンコードフレームが前記圧縮解除装置によって受信されない場合、前記圧縮解除装置から前記圧縮装置にフラッシュ要求を送信する処理と、
前記フラッシュ要求に応答してヒストリバッファをフラッシュする処理であって、前記ヒストリバッファに記憶されている既に処理済みのバイトが、一致ストリングの部分になり得ないようにする該フラッシュ処理と、を更に含むことを特徴とする請求項２０に記載の方法。
【請求項２２】
フラッシュ要求を前記圧縮装置が受信したかどうかを示す制御コードを、前記コヒーレンス・コードの１つが含むことを特徴とする請求項２１に記載の方法。
【請求項２３】
前記エンコードされたデータストリームにおいて所定数の一致コードのシーケンスを識別する処理と、
前記識別された一致コードシーケンスの一致コードの数を示すカウント値を、前記識別された一致コードシーケンスに追加する処理とを、更に含むことを特徴とする請求項２０に記載の方法。
【請求項２４】
各一致コードシーケンスに一致コードフラグを追加する処理を更に含むことを特徴とする請求項２３に記載の方法。
【請求項２５】
前記各エンコードされたデータストリームをリモート圧縮解除装置に送信する処理と、
前記エンコードされたデータストリームを、前記入力ストリームと同一の圧縮解除ストリームに圧縮解除する処理、とを更に含むことを特徴とする請求項２３に記載の方法。
【請求項２６】
一致コードの数を示す一致カウント値を見つけ出す(locate)処理と、
前記一致カウント値に等しい数の一致コードをデコード(decode)する処理と、
前記デコードされた一致コードを前記圧縮解除されたストリームに追加する処理と、を含む請求項２５に記載の方法。
【請求項２７】
前記入力ストリームをせいぜい１パケットあたりｍデータバイトを有する１以上のパケットに分割し、前記方法は、更に、
所定最少数のデータバイトよりも少ないパケットかどうかを判断する処理と、
前記パケットが前記所定最少数のデータバイトよりも少ないと判断された場合に、同一データバイトのシーケンスをサーチすることなく、前記エンコードされたデータストリームに前記パケットを送信する処理を含むことを特徴とする請求項２０に記載の方法。
【請求項２８】
複数のリテラル及び一致を含むデータのエンコード・ストリームを記憶するコンピュータシステムにおける方法であって、
前記エンコード・ストリームの各リテラルについて、該リテラルを記憶する処理と、
所定最少数の一致の直後に一致が続かない各一致について、該一致を記憶する処理と、
前記一致を記憶するという指示(indication)を記憶する処理と、
順次、所定数の一致を記憶した後に、連続するその一致の数の指示(indication)を記憶する処理と、
前記一致を記憶するという指示(indication)を記憶することなく、連続するその一致のそれぞれを記憶する処理と、を含むことを特徴とする方法。
【請求項２９】
複数のリテラル及び一致を含むデータのエンコード・ストリームを記憶するコンピュータシステムにおける方法であって、
（１）前記エンコード・ストリームの各リテラルについて、該リテラルを記憶する処理と、
（２）一致シーケンスの部分になっていない各一致について、
(i)前記一致が一致シーケンスの部分でないことの指示(indication)を記憶する処理と、
(ii)前記一致及び各一致シーケンスを記憶する処理と、
(iii)前記シーケンスの指示(indication)を記憶する処理と、
(iv)前記シーケンスにおける一致数の(indication)を記憶する処理と、
(v)前記シーケンスの各一致を記憶する処理と、
を含むことを特徴とする方法。
【請求項３０】
シーケンスが所定最少数の一致であることを特徴とする請求項２９に記載の方法。
【請求項３１】
バイトの入力データストリームを圧縮するコンピュータシステムにおける方法であって、前記コンピュータシステムは、前記入力データストリームのバイトを記憶するために先頭と終端を有する入力バッファを備え、
前記入力データストリームの複数のバイトを受信する処理と、
前記受信された複数のバイトを記憶するために、前記入力バッファに記憶された最新のバイトと、前記入力バッファの終端との間にある入力バッファスペースが十分にあるかどうかを判断する処理と、
前記入力バッファスペースが十分にある場合は、前記入力バッファに記憶された最新のバイトと、前記入力バッファの終端との間に、前記受信された複数のバイトを記憶する処理と、
前記入力バッファスペースが十分にない場合は、前記受信された複数のバイトを前記入力バッファの先頭を開始位置にして記憶する処理と、
現在のバイトストリングに一致するバイトストリングについて、前記入力バッファをサーチする処理と、
現在のバイトストリングに一致するバイトストリングを基準にして前記現在のバイトストリングをエンコードする処理と、を含むことを特徴とする方法。
【請求項３２】
圧縮システムと圧縮解除システムの同期を維持するコンピュータシステムにおける方法であって、前記圧縮システムは既にエンコードされたデータを基準にデータをエンコードし、前記方法は、
（１）前記圧縮システムの制御下で、エンコードされたデータのパケットを生成するとともに、当該パケットを前記圧縮解除システムに送信する処理と、
（２）前記圧縮解除システムの制御下で、前記送信されたパケットが正しく受信されなかった場合、前記圧縮システムにフラッシュ要求を送信する処理と、
（３）前記圧縮システムの制御下で、
(a)前記送信されたフラッシュ要求を受信する処理と、
(b)前記送信されたフラッシュ要求の受信に応答して、
(i)既に処理されたどんなパケットも参照することなく、エンコードされたデータのパケットを生成する処理であって、当該生成されたパケットは同期指示(synchronization indicator)を含む該処理と、
(ii)前記生成されたパケットを前記圧縮解除システムに送信する処理と、
（４）前記圧縮解除システムの制御下で、前記送信されたパケットが前記同期指示とともに受信された場合、既に処理されたどんなパケットも参照することなく、前記受信パケットのエンコードデータを圧縮解除する処理と、を含み、
これにより、前記圧縮解除システムがパケットを正しく受信しなかったとしても、前記圧縮システムと圧縮解除システムの同期が維持されることを特徴とする方法。
【請求項３３】
圧縮装置からの圧縮データを圧縮解除装置に送信するコンピュータシステムにおける方法であって、
（１）複数の入力ストリングのそれぞれについて、
前記入力ストリングを受信する処理と、
前記受信された入力ストリングに一致する、既に受信済みの入力ストリングに基づいて、前記受信された入力ストリングをエンコードする処理と、
前記エンコードされた入力ストリングを前記圧縮解除装置に送信する処理と、
（２）前記圧縮解除装置が、前記送信された入力ストリングを正しく受信しなかったことの指示(indication)を受信する処理と、
（３）前記指示を受信することに応答して、前記圧縮解除装置が圧縮解除できるようにするために、不正確に受信された入力ストリングを参照することなく、前記指示の受信後に受信した入力ストリングにのみ基づいて、その後に受信した入力ストリングをエンコードする処理と、を含むことを特徴とする方法。
【請求項３４】
複数のリテラルと一致を含むデータのエンコード・ストリームを圧縮解除するコンピュータシステムにおける方法であって、
前記データのエンコード・ストリームを個々の部分で構文解析(parse)する処理と、
前記構文解析された部分のうちの現在部分が、一致シーケンスにおける一致数を表す一致コードカウントを含むかどうかを判断する処理と、
前記現在部分が一致コードカウントを含むと判断された場合、前記一致シーケンスの各一致について、その一致を値シーケンスにデコードする処理、とを含むことを特徴とする方法。
【請求項３５】
前記現在部分が一致コードカウントを含まないと判断された場合、その現在部分が、一致シーケンス、及び前記一致シーケンスにおける一致数を示す一致コードカウントを含む部分の直後に続くかを判断する処理と、
前記現在部分が、一致コードカウントを含む部分の直後に続く場合、その現在部分についてのリテラルを出力する処理と、を更に含むことを特徴とする請求項３４に記載の方法。
【請求項３６】
前記現在部分が、リテラルのシーケンス、及びそのリテラルシーケンスにおけるリテラル数を示すリテラルコードカウントを含む部分の直後に続くかを判断する処理と、
前記現在部分が、リテラルコードカウントを含む部分の直後に続く場合、前記現在部分を１つの一致として、値のシーケンスへデコードする処理と、を更に含むことを特徴とする請求項３４に記載の方法。
【請求項３７】
圧縮解除装置で受信された圧縮装置からのエンコードデータを圧縮解除するコンピュータシステムにおける方法であって、
複数のエンコード・ストリングを前記圧縮装置から受信する処理であって、該複数のエンコード・ストリングのそれぞれは、既に受信されたエンコード・ストリングに対応する入力ストリングに基づいてエンコードされる該処理と、
前記圧縮解除装置が前記エンコード・ストリングを正しく受信しなかったという指示(indication)を、前記圧縮装置に送信する処理と、
前記圧縮解除装置から前記指示を受信した後に受信した入力ストリングにのみ基づいて、前記圧縮装置によってエンコードされたエンコード・ストリングを引き続き受信する処理と、
正しく受信されなかったエンコード・ストリングに対応する入力ストリングを参照することなく、前記引き続き受信されたエンコード・ストリングを圧縮解除する処理と、を含むことを特徴とする方法。