(57)【要約】本発明には、デジタルデータが複数のブロックに分割され、その複数のブロックの１以上を各スレッドが含むように複数のスレッドが生成され、その後複数の圧縮されたスレッドを得るために各スレッドが処理され、各圧縮されたスレッドがデジタルデータの１以上の圧縮されたブロックを含んでいる、デジタルデータを処理する方法および装置が記載されている。この方法において、前のパスにおいてすでに圧縮エンジンによって圧縮されたデータを圧縮アルゴリズムが反復的に周期的な方式で圧縮するように、スレッドは圧縮エンジンを使用して処理される。各圧縮パスの間において、その時圧縮されたデータは前のパスにおいて設定されたメタデータを使用して処理され、それによって前のパスにおいて圧縮されたデータ中に存在する冗長が除去される。したがって、本発明は予め定められた圧縮アルゴリズムの多数のパスを使用してデジタルデータを圧縮し、それによって圧縮されたデジタルデータを獲得し、それに後続してその圧縮されたデジタルデータを、対応した圧縮解除アルゴリズムの単一のパスを使用して圧縮し、それによって無損失手順でデジタルデータを獲得する。【選択図】図２
2004533733.tif 000002
【特許請求の範囲】
【請求項１】
デジタルデータを複数のブロックに分割し、
その複数のブロックの１以上をそれぞれが含むように複数の第１のスレッドを生成し、
複数の圧縮された第１のスレッドを得るために複数の第１のスレッドのそれぞれを処理するステップを含んでおり、各圧縮された第１のスレッドがデジタルデータの１以上の圧縮されたブロックを含んでいるデジタルデータを処理する方法。
【請求項２】
第１のスレッドのそれぞれを処理するステップは、無損失圧縮を行う請求項１記載の方法。
【請求項３】
第１のスレッドのそれぞれを処理するステップは、複数の第１のスレッドのそれぞれを独立的に処理する請求項１記載の方法。
【請求項４】
第１のスレッドの少なくともある定まったものは、並列に独立に処理される請求項１記載の方法。
【請求項５】
処理するステップ中において、異なった第１のスレッドを独立的に処理するために２以上の異なった圧縮アルゴリズムが使用される請求項４記載の方法。
【請求項６】
デジタル的に圧縮されたデータを得るために複数の圧縮された第１のスレッドを組合せるステップをさらに含んでいる請求項１記載の方法。
【請求項７】
複数の第１のスレッドを生成するステップは、複数の第１のスレッドのそれぞれの中のブロックがある共通した圧縮特性を共用するようにデジタルデータの複数のブロックのそれぞれを複数の第１のスレッドの１つと関連付けるステップを含んでいる請求項１記載の方法。
【請求項８】
各ブロックの推定される圧縮時間および推定される圧縮量を予測するステップをさらに含んでいる請求項７記載の方法。
【請求項９】
複数の第１のスレッドを生成するステップはまた推定された圧縮時間と推定された圧縮量を使用して、その同じ第１のスレッドと関連付けられるべきブロックを決定する請求項８記載の方法。
【請求項１０】
推定された圧縮時間および推定された圧縮量は選択された圧縮アルゴリズムに基づいて形成され、予測するステップは、選択に利用可能な圧縮アルゴリズムの１つに基づいている提案された推定される完了時間により、そのデジタルデータに対して所望の圧縮量が所望の圧縮時間内に達成されることが可能であるか否かを決定するステップを含んでいる請求項８記載の方法。
【請求項１１】
複数の第１のスレッドのそれぞれを生成するステップは、第１のスレッドのそれぞれが類似のデータタイプを有するブロックを含むように複数のブロックのそれぞれのデータタイプを使用する請求項１記載の方法。
【請求項１２】
データタイプは、各ブロックに関連したヘッダ情報にしたがって決定される請求項１１記載の方法。
【請求項１３】
データタイプは、ブロックデータを種々の予め定められたデータパターンと比較することによって決定される請求項１１記載の方法。
【請求項１４】
各ブロックに対する推定された圧縮時間および推定された圧縮量を予測するステップをさらに含んでいる請求項１記載の方法。
【請求項１５】
複数の第１のスレッドを生成するステップにおいて、推定された圧縮時間および推定された圧縮量を使用して、同じ第１のスレッドと関連付けられるべきブロックを決定する請求項１４記載の方法。
【請求項１６】
データを分割するステップは、各ブロックのデータタイプを考慮して複数のブロックのそれぞれのサイズを決定するステップを含んでいる請求項１記載の方法。
【請求項１７】
圧縮された第１のスレッドのそれぞれを処理して、その圧縮された第１のスレッドのそれぞれを除去すると共に圧縮された第１のブロックを保存し、
複数の圧縮された第１のブロックの１以上をそれぞれが含んでいるように複数の第２のスレッドを生成し、
複数の第２のスレッドのそれぞれを処理して複数の圧縮された第２のスレッドを獲得し、圧縮された第２のスレッドのそれぞれがデジタルデータの１以上の圧縮された第２のブロックを含んでいるステップをさらに含んでいる請求項１記載の方法。
【請求項１８】
第２のスレッドのそれぞれを処理するステップは、複数の第２のスレッドのそれぞれを独立的に処理する請求項１７記載の方法。
【請求項１９】
第２のスレッドの少なくともある定まったものは、並列に独立に処理される請求項１７記載の方法。
【請求項２０】
複数の第２のスレッドのそれぞれを処理するステップにおいて、各ブロックを処理するために使用された同じ圧縮アルゴリズムはまた、対応した圧縮されたブロックを処理するために使用される請求項１７記載の方法。
【請求項２１】
デジタル的に圧縮されたデータを得るために複数の圧縮された第２のスレッドを組合せるステップをさらに含んでいる請求項１７記載の方法。
【請求項２２】
複数の第２のスレッドを生成するステップは、複数の第２のスレッドのそれぞれの中の圧縮された第１のブロックがある共通した圧縮特性を共用するように複数の圧縮された第１のブロックのそれぞれを複数の第２のスレッドの１つと関連付けるステップを含んでいる請求項１７記載の方法。
【請求項２３】
第２のスレッドのそれぞれは、同じ第１のスレッドから生成された圧縮された第１のブロックを含んでいる請求項２２記載の方法。
【請求項２４】
第２のスレッドの数は、第１のスレッドの数より大きい請求項２３記載の方法。
【請求項２５】
第１のスレッドの１つの中に存在していた圧縮された第１のブロックは、２つの異なった第２のスレッドを形成するために使用される請求項２２記載の方法。
【請求項２６】
複数の第１のスレッドのそれぞれを処理するステップの結果、複数の第１のメタデータセットが獲得され、各第１のメタデータセットは、冗長がそこに配置されている可能性があると決定された圧縮された第１のブロックの部分を含んでいる請求項１７記載の方法。
【請求項２７】
第１のスレッドのそれぞれを処理するステップは、各スレッドに対して、第１のメタデータパターンに対応した最初の圧縮された第１のブロックにおけるデータのパターンを維持し、第１のスレッドのそれぞれに対する異なった第１のメタデータパターンのそれぞれが結合して、結果的にその第１のスレッドに対する第１のメタデータセットを生成する請求項２６記載の方法。
【請求項２８】
最初の圧縮された第１のブロックのデータのパターンは、次のステップ期間中維持されている請求項２７記載の方法。
【請求項２９】
第１のスレッドはそれぞれ、関連した第１のメタデータセットを有している請求項１７記載の方法。
【請求項３０】
複数の第２のスレッドを生成するステップは、
どの圧縮された第１のブロックが同じ第２のスレッドと関連付けられるべきかを決定し、
第１のメタデータセットを使用して、第２のスレッドの少なくともあるものに関連付けられた圧縮された第１のブロックのあるものにおける冗長を除去するステップを含んでいる請求項２６記載の方法。
【請求項３１】
複数の第２のスレッドのそれぞれを処理するステップの結果、複数の各第２のメタデータセットが獲得され、各第２のメタデータセットは、冗長がそこに配置されている可能性があると決定された圧縮された第２のブロックの部分を含んでいる請求項３０記載の方法。
【請求項３２】
第２のメタデータセットは、第１のメタデータセットのサブセットである請求項３１記載の方法。
【請求項３３】
第１のスレッドのそれぞれを処理するステップは、各スレッドに対して、第１のメタデータパターンに対応した最初の圧縮された第１のブロックにおけるデータのパターンを維持し、第１のスレッドのそれぞれに対する異なった第１のメタデータパターンのそれぞれが結合して結果的にその第１のスレッドに対する第１のメタデータセットを生成し、
第１のメタデータセットを使用して第２のスレッドの少なくともあるものに関連付けられた圧縮された第１のブロックのあるものにおける冗長を除去するステップは、最初の圧縮された第１のブロックにおけるデータのパターンを維持し、後続的に圧縮される第１のブロック中のデータのパターンを除去する請求項２６記載の方法。
【請求項３４】
第１のメタデータセットを使用して第２のスレッドの少なくともあるものに関連付けられた圧縮された第１のブロックのあるものにおける冗長を除去するステップ中において、後続的に圧縮される第１のブロック中のデータのパターンはポインタおよび動作指示符合と置換され、それによって各第２のスレッド中における複数の圧縮され減少された第１のブロックを獲得する請求項３３記載の方法。
【請求項３５】
複数の第２のスレッドのそれぞれを処理するステップ中において、各ブロックを処理するために使用された同じ圧縮アルゴリズムはまた、対応した圧縮され減少された第１のブロックを処理し、それによって圧縮された第２のブロックを獲得するために使用される請求項３４記載の方法。
【請求項３６】
動作指示符合は、第１の圧縮されたデータブロック中の冗長を除去するために使用される動作を識別し、その動作は比較動作に等しいもの、比較以上のもの、および比較以下のものの１つである請求項３５記載の方法。
【請求項３７】
複数の第２のスレッドのそれぞれを処理するステップ中において、選択された比較動作が適応可能に決定される請求項３６記載の方法。
【請求項３８】
適応可能な決定は、代表的なファイルタイプパターンと比較された圧縮されたブロックのパターンに基づいて行われる請求項３７記載の方法。
【請求項３９】
圧縮されたデジタルデータを得るために予め定められた圧縮アルゴリズムの多数のパスを使用してデジタルデータを圧縮し、
デジタルデータを得るために対応した圧縮解除アルゴリズムの単一パスを使用して圧縮されたデジタルデータの圧縮解除を行うステップを含んでいるデジタルデータの処理方法。
【請求項４０】
圧縮されたデジタルデータを得るために予め定められた圧縮アルゴリズムの多数回のパスを使用してデジタルデータを圧縮する手段と、
デジタルデータを得るために対応した圧縮解除アルゴリズムの単一パスを使用して圧縮されたデジタルデータを圧縮解除する手段とを含んでいるデジタルデータの処理装置。
【請求項４１】
圧縮する手段は、
インターフェース制御装置と、
圧縮エンジンとを含んでいる請求項４０記載の装置。
【請求項４２】
サーチエンジンは単一の中央処理装置を含んでいる請求項４１記載の装置。
【請求項４３】
サーチエンジンは複数の中央処理装置を含んでいる請求項４１記載の装置。
【請求項４４】
複数の中央処理装置のそれぞれが、異なったスレッドを処理する請求項４３記載の装置。
【請求項４５】
複数の中央処理装置は、複数のデジタル信号プロセッサを含んでいる請求項４４記載の装置。
【請求項４６】
第１の圧縮システムにおける第１のデジタルデータの圧縮から得られた第１のデジタルデータにおけるパターンを表すメタデータを獲得し、
第２の圧縮システムが圧縮する必要のある第２のデジタルデータを圧縮するためにそのメタデータを使用することができるように、このメタデータを１以上の第２の圧縮システムに分配するステップを含んでいる複数の圧縮システムがさらに効率的に動作することを可能にする方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報を符号化および復号する方法および装置に関し、とくに多数のパスを使用して符号化し、単一のパスで復号する方法に関する。
【０００２】
【従来の技術】
コンピュータおよび電子送信の普及により、デジタル情報の圧縮および圧縮解除方法が広く使用されている。
【０００３】
システムの要求に影響を与える１つのパラメータは、圧縮が行われるのに必要な速度である。情報を実時間で処理するあるシステムにおいて、圧縮は実時間レートより速いレートで行われなければならない。圧縮がオフラインで行われることを可能にする別のシステムでは、圧縮手順はオフラインで行われることができる。
【０００４】
別のパラメータは、必要とされる圧縮の量である。テキストファイルは小さいので、送信または記憶される前に圧縮は必要ないかもしれないが、画像ファイルは非常に大きくなる可能性が高いため、圧縮されていない画像の送信あるいはメモリまたはディスク中への記憶は著しく高価なものになる。
【０００５】
さらに、圧縮された情報が圧縮解除されるレートは、使用される圧縮のタイプを決定するときに考慮されることのできる別のパラメータである。第２の圧縮解除全体を単一の静止画像に費やすことは問題ないかもしれないが、実時間レートで再生されることができるように一連の画像が圧縮解除されなければならない場合、圧縮解除が行われるレートは重要なファクタになる可能性が高い。
【０００６】
通常の圧縮／圧縮解除システムは、種々の方法で上記およびその他のパラメータのバランスを保っている。たとえば、あるシステムにおいて使用される圧縮アルゴリズムは、圧縮に要する時間にかかわらずそのデジタル情報に関してなされる圧縮の重要度によって決定されることができる。ある別のシステムは種々の程度の圧縮を提供し、それに応じて異なった圧縮アルゴリズムを使用する。
【０００７】
非常に多くの種々の圧縮／圧縮解除システムが存在しているにもかかわらず、もっと効率的に動作するこのようなシステムが継続的に必要とされている。効率をよくする通常の方法は、さらに効率の高い圧縮／圧縮解除アルゴリズムを開発することである。これには大きな利点があるが、使用可能なアルゴリズムの開発は高価で、危険を伴う可能性が高い。
【０００８】
通常の圧縮／圧縮解除システムの一般的な特性として、デジタル情報は、それが圧縮のために受取られると、その受取られたシーケンスで処理される。したがって、最初に受取られたビットのスライスが圧縮された後でのみ、それに続いて受取られたスライスの圧縮が行われる。これは、単一パスで行われる圧縮とみなされることができ、それはデータの各スライスが単一の回数だけ処理され、また、それは一度処理されると、二度と処理されないためである。
【０００９】
連続したスライスを処理するために多数のプロセッサが使用された場合でも、全体的な圧縮レートは最も圧縮の遅いスライスに制限され、また、本質的にシステムは依然として単一パスシステムである。したがって、特定のスライスが圧縮されることができなければ、圧縮動作は失敗する。
【００１０】
したがって、デジタルデータの圧縮および圧縮されたデジタルデータの圧縮解除をもっと効率的でかつ無損失に行うことのできる方法および装置が必要とされている。
【００１１】
【発明が解決しようとする課題】
本発明の目的は、デジタルデータの圧縮および圧縮されたデジタルデータの圧縮解除をもっと効率的かつ無損失に行うことである。
【００１２】
本発明の別の目的は、デジタルデータの圧縮符号化に要するであろう確率期間を適応可能に予測し、使用すべき圧縮符号化を決定するときにそれらの予測を使用することである。
【００１３】
本発明の別の目的は、デジタルデータを多数のスレッドに分割し、所望する量の圧縮を達成するためにその多数のスレッドを独立的に処理することである。
【００１４】
本発明の別の目的は、デジタルデータを多数のスレッドに分割し、所定の期間内に所望する量の圧縮を達成するためにその多数のスレッドを独立的に処理することである。
【００１５】
本発明のさらに別の目的は、パスのシーケンスでデジタルデータを処理し、それによって結果的に得られる圧縮を改善することである。
【００１６】
本発明のさらに別の目的は、以前圧縮されたデータを単一のパスで復号することである。
【００１７】
【課題を解決するための手段】
上記の目的は、とくに単一でまたは組合せられて、デジタルデータが複数のブロックに分割され、その複数のブロックの１以上を各スレッドが含むように複数のスレッドが生成され、その後複数の圧縮されたスレッドを得るために各スレッドが処理され、各圧縮されたスレッドがデジタルデータの１以上の圧縮されたブロックを含んでいるデジタルデータの処理方法および装置が本発明によって達成される。
【００１８】
この方法において、前のパスにおいてすでに圧縮エンジンによって圧縮されたデータを圧縮アルゴリズムが反復的に周期的な方式で圧縮するように、スレッドは圧縮エンジンを使用して処理される。各圧縮パスの間において、その時圧縮されたデータは前のパスにおいて設定されたメタデータを使用して処理され、それによって前のパスにおいて圧縮されたデータ中に存在する冗長が除去される。
【００１９】
したがって、本発明は予め定められた圧縮アルゴリズムの多数のパスを使用してデジタルデータを圧縮して圧縮されたデジタルデータを獲得し、それに後続してその圧縮されたデジタルデータを、対応した圧縮解除アルゴリズムの単一のパスを使用して圧縮し、それによって無損失のプロセスでデジタルデータを獲得する。
【００２０】
【発明の実施の形態】
本発明の上記およびその他の目的、特徴および利点は、本発明の非限定的で例示的な実施形態によって図面を参照として以下の詳細な説明に詳しく説明されている。なお、複数の図面にわたって同じ参照符号が本発明の同じ部分を表している。
最初に、とくに圧縮および圧縮解除に関する本発明の特徴を説明する。その後、本発明のその他の特徴を示す。
圧縮および圧縮解除に関して、本発明は最初に処理されているデジタルデータのファイルについて説明する。本発明の有効の特徴は、テキストファイルまたは画像ファイルのような前に圧縮されていないデータ、ならびにＭＰＥＧファイルまたはＺＩＰファイルのような前に圧縮されたデータを処理し、潜在的に圧縮することができることである。別の特徴として、本発明は認識されたファイルタイプおよび認識されていないファイルタイプを処理することができる。Ｗｉｎｄｏｗｓ（商標名）オペレーティングシステム環境において、各ファイルは、その特定のファイルタイプを規定するヘッダ部分を有している。その結果、大抵の場合にファイルはユーザにより認識可能なフォーマットで処理される。ＭＡＣ，Ｌｉｎｕｘおよびその他のような別のオペレーティングシステムに対しても同様である。当然ながら、種々のオペレーティングシステムは同じファイルタイプの多くを共用することが知られている。したがって、何百ものこのようなファイルタイプが存在しているが、そのほとんどはヘッダ部分に与えられた定義によって認識可能である。
【００２１】
図１は、本発明を使用して処理されることのできる多くの異なったファイルタイプのファイルを含むデジタルデータ１００の例示的な部分を示している。説明を容易にするために、ビットマップファイルＢ、実行可能ファイルＣ、およびジップファイルＺの３つのファイルタイプしか示されていない。明らかになるように、ビットマップファイルＢは圧縮されていないファイルであり、実行可能ファイルＣはプログラムファイルであり、ジップファイルＺは圧縮されたファイルである。デジタルデータ１００のこの例示的な部分は、たとえば、半導体メモリ、ハードディスクドライブまたはＣＤ等のある種のメモリ装置上に記憶される必要のあるデータであってもよく、ある種の伝送路に沿って送信される必要があるか、あるいは圧縮される、またはさらに圧縮されるある別の必要性があるかもしれないデータであることができる。例示的な部分は異なったファイルタイプを示しているが、本発明はまた単一のファイルタイプであるデータを処理することが可能であることが認識され、実際、それが以下に示されているようにこのようなデータを処理した場合、ある利点が明らかになるであろう。
【００２２】
図２は、デジタルデータ１００を処理するシステム２００を示している。この例のために、デジタルデータはデジタル記憶装置２１０中に記憶され、このデジタルデータは圧縮する必要があると仮定される。この説明のために、デジタルデータ１００が一度圧縮されると、それを圧縮されたデジタルデータ１００’’’としてデジタル記憶装置２１０中に再度記憶するシステム２００を説明する。その後、圧縮されたデジタルデータ１００’の復号を説明する。しかしながら、一度圧縮されたデジタルデータ１００’が得られると、それは後の利用のために種々の方法で記憶されるか、あるいは送信されることができることが認識される。以下、圧縮されたデジタルデータ１００’が使用されることのできるある特定の方法を説明するが、記載される方法は何等本発明に制限を課すものではない。
【００２３】
デジタル記憶装置２１０に加えて、図２は、インターフェース制御装置２２０および圧縮／圧縮解除エンジン２３０を含むシステム２００を示している。システム２００のこれらの部分はそれぞれ互いに関して説明されるが、各部分およびその各部分により行われる対応した機能は、固有の特徴を有していることが認識される。
【００２４】
インターフェース制御装置２２０および圧縮／圧縮解除（Ｃ／Ｄ）エンジン２３０は、同じマイクロプロセッサを時分割して使用してもよく、本発明の好ましい実施形態においては、それぞれを行うために異なったプロセッサが使用され、Ｃ／Ｄエンジン２３０は、多数のスレッドを同時に処理することのできる機能を備えた１以上のプロセッサを使用して実施される。以下に説明するように、Ｃ／Ｄエンジン２３０をはるかに効率的に構成するために、さらに別のいくつかの異なった並列のプロセッサが使用されることができる。どちらの形態が使用さその他のコンピュータ言語で書かれた一連のプログラム命令として実施されるか、あるいはその代りにハードウェアで実施されることが好ましい。Ｃ５Ｘ，Ｃ６ＸおよびＣ７Ｘシリーズモデルで提供されているテキサス・インスツルメンツＴＭＳ３２０  ＤＳＰのようなＤＳＰにおいてＣ／Ｄエンジン２３０を実施することがとくに有効であると認められており、このようなＣ５Ｘ，Ｃ６ＸおよびＣ７Ｘシリーズモデルは、それぞれ互いに関する種々の価格−性能トレードオフを提供するが、しかし、同じマイクロプロセッサによる実行を必要とされたアルゴリズムがインターフェース制御装置２３０を制御した場合に可能となる速度よりはるかに速い速度で圧縮および圧縮解除アルゴリズムを動作させることを実効的に可能にする。
【００２５】
以下、図３を参照としてシステム２００の動作によるデジタルデータ１００の圧縮を説明する。最初に、ステップ３１０によって示されているように、ユーザは所望の圧縮率および臨界圧縮符号化時間を定める。これらはユーザアプリケーションに応じて変化するが、一般に圧縮率が高くなり、必要とされる符号化時間が短くなると、システム２００はそれだけ一層、その所望の比率および時間が達成されることを確実にするように動作しなければならなくなることが認識されるであろう。また、ある比率および時間が所望されているが、システム２００が実際にこれらの要求を満足させることができるという保証はないことを認識すべきである。これに関して、使用される特定のタイプの圧縮（および対応した圧縮解除）ルーチンは、本発明の焦点ではないことがさらに認識される。本発明の特徴は、むしろ、種々の圧縮ルーチンに基づいて要求された圧縮のレベルにデジタルデータ１００の全体量を圧縮符号化するのに要する確率期間を、規定された圧縮ルーチンのセットが適応可能に予測し、以下に説明するように、使用すべき圧縮アルゴリズムを決定するときにこれらの予測を使用する能力である。したがって、これらの予測を行う開始時点は、所望された圧縮率および符号化時間をシステム２００に示している。
【００２６】
これらの圧縮率および符号化時間は、異なったタイプのデジタル情報に対して予測されることができる。以下の表１には、異なったタイプのファイルおよび圧縮ルーチンに対して、ファイルのサイズは一般に同じであるファイルでそのファイル中のデジタル情報に関して行われたパスの数に応じて、得られることのできる圧縮率の一例が示されている。典型的に、行われるパスが多くなるとそれだけ一層圧縮は増加する。もっとも、達成される圧縮量は、時間にわたって一般に指数関数的に、すなわち、少なくとも線形で減少するより速く少なくなる。ＬＺＷまたは他のもののような知られてはいるが、しかし、以下に説明されるメタデータ３００の収集による強化はなされていない圧縮ルーチンを使用してデジタル情報が処理されることを仮定する。
【００２７】
ユーザが所望の圧縮率および圧縮符号化時間を入力した後、ステップ３２０が続き、図２の制御インターフェース２２０は、符号化すべきデジタル情報１００を識別する。このような情報を識別し、ある装置（メモリ２１０のような）にその情報を認識させて別の装置（インターフェース制御装置のような）に転送させる方法は、よく知られているので詳細には説明しない。制御インターフェース２２０により識別されると、デジタル情報１００内の各ファイルと関連付けられたヘッダ１１０は、制御インターフェース２２０により認識され、そのヘッダ情報はファイルタイプおよびファイルサイズを検出するために使用される。
【００２８】
ステップ３３０において、インターフェース制御装置は、この情報に基づいてデジタルデータ１００を圧縮符号化するために準備する。
【００２９】
図４のａ乃至ｅは本発明によるデジタルデータに対する圧縮動作の効果を、圧縮動作中の種々の回数の段階についてグラフィックに示している。図４のａには、元のデジタルデータファイル１００が、ある相対シミュラリティを有するファイルがグループ化された（この結果、示されている例では順序は同じである）順序で示されている。全体的レベルの一例として、画像、プログラムおよび圧縮されたファイルが別の画像、プログラムおよび圧縮されたファイルとそれぞれグループ化されることができる。しかしながら、各ファイルのタイプ（各ファイルのヘッダにおいて識別される）が互いに関してグループ化される多くの異なったタイプの画像ファイル、プログラムファイルおよび圧縮されたファイルが存在することが好ましい。したがって、図４のａの特定された例に示されているように、ビットマップＢファイル、実行可能ＣファイルおよびジップＺファイルが存在する。しかしながら、本発明は、システム２００がすでに圧縮されたファイルを除く任意のタイプのファイルを処理し、そのファイルの圧縮を試みることが可能であり、この例においてとくに使用されるものに制限されないことを認識すべきである。
【００３０】
これらのファイルのそれぞれに対応するデータは新しいメモリ位置に物理的に移動されないことが好ましい（理論的にこれは可能であるが）が、しかし順序をファイルタイプに基づいて個々のファイルに関連付けるポインタが生成されることが認識される。これはまた、データが移動されるものとして説明したほうが視覚的に理解が容易になるために以下の説明ではそのような形で説明される。
【００３１】
ユーザはグループ化の細分性を決定することができる。そのようにして、上述のように各ファイルタイプに対するグループ化が行われることが好ましい。その代わり、画像、プログラムおよび圧縮されたファイルのような類似のファイルタイプに対する内容（ｓｕｂｌｅｃｔ  ｍａｔｔｅｒ）のグループ化が行われることができる。１からＮ（ここでＮは、ファイルタイプの最大数より小さく、１より大きい任意の整数である）までのグループ化を行うある別の内容（ｍａｔｔｅｒ）が、たとえば、ファイルが圧縮されることのできる適応可能に予測された量を使用して（以下説明するように）構成されることが可能であり、その場合初期グループ１ファイルは最も大きく圧縮されると予測されたものであり、一方グループＮファイルは最も小さく圧縮されると予測されたものである。その代り、このグループ化は、圧縮に必要となるであろう適応可能に予測された時間により決定されることができ、この場合にはグループ１ファイルは最も高速で圧縮されると予測されたものであり、一方グループＮファイルは最も低速で圧縮されると予測されたものである。
【００３２】
このグループ化は、類似した圧縮特性を有するものとして評価されたデータを含むと予測されたファイルが互いに関連付けられて圧縮されるように相対的に類似するように行われる。これはさらに効率的な圧縮を可能にすると共に、以下に説明する圧縮プロセスの後続する段階で、隠された冗長がもっと容易に明らかになることを可能にする。
【００３３】
さらに、最初のグループ化のあと、ステップ３４０に示されているように、デジタルデータは、ファイルＢ１をヘッダ部分に分割することにより図４のｂに示されているようなブロックに典型的にファイル単位で分割され、その後、部分Ｂ１ａ、Ｂ１ｂ、Ｂ１ｃおよびＢ１ｄが行われる。この分割は、ファイルのタイプに対して、最も容易に圧縮されることのできるサイズに対して最適化されたサイズを各ブロックが有するように行われることが好ましい。ブロックのサイズは広範囲に変化し、典型的に０乃至６５Ｋバイトの範囲である。
【００３４】
ステップ３４０においてブロック化が行われると、それに続いてステップ３５０において、特定の圧縮ルーチンを使用して所望の全体的な圧縮率を達成するために、インターフェース制御装置２２０が各ブロックを処理し、デジタルデータ１００を構成するファイルのそれぞれに対する各ブロックの圧縮を要求される確率期間を適応可能に予測する。類似するタイプの、以前に圧縮符号化されたファイルから得られた知識、およびヘッダ情報に基づいて、デジタルデータ１００の全体量の各ブロックを、特定の圧縮ルーチンに基づいて要求される圧縮のレベルに圧縮符号化するのに要する時間の確率期間の評価が行われ、この評価はその合計を予測するために累算される。
【００３５】
特定のファイルタイプのブロックは全て、ヘッダからのファイルタイプに基づいて同じ相対ブロックサイズに対して同じであると評価される。これに関して、各ファイルタイプに対して特定の圧縮ルーチンを使用して評価された圧縮量およびその圧縮を達成するために要する評価された時間を示す表が使用されることができる。以下に示されている表１から明らかであるように、異なったファイルタイプのそれぞれに対して、圧縮量は、使用されるパスの数が多くなると一般に増加する。
【００３６】
［表１Ａ：ファイルタイプ選択例］
2004533733.tif 000003
［表１Ｂ：比率が予測されたファイルタイプの例］
2004533733.tif 000004
［表１Ｃ：時間が予測されたファイルタイプの例］
2004533733.tif 000005
2004533733.tif 000006
特定の圧縮ルーチンを使用した場合におけるそのタイプのデータが典型的に圧縮する程度の評価に基づいて、必要とされる圧縮の量の評価、その圧縮レベルに達すると評価されたパスの数、そのレベルの圧縮を行うために必要であると評価された時間が獲得されることができる。したがって、デジタル情報１００を全て圧縮するために、異なった圧縮ルーチンおよび、以下説明するように同じ圧縮ルーチンを使用して行われるのと同じ数のパスが使用されることができる。インターフェース制御装置２２０は、所望の圧縮全体を達成しようと試みるために異なったブロックのそれぞれに対する使用を示唆するものを決定することができる。たとえば、典型的に、所定の圧縮ルーチン（上記の表１に示されている）を使用して第１のパスの後に少しだけ圧縮する図１のＺ１のファイルに対して、インターフェース制御装置２２０は、Ｃ／ＤエンジンがＺ１ファイルに対するブロックに関してパスを１回だけ行うことを示唆することができるが、図１におけるＢ１およびＢ２のような別のファイルに対しては、それらのブロックに対して所望の圧縮が得られるように示唆された圧縮ルーチンに適した、２回および３回のパスをそれぞれ行うことを示唆し、デジタル情報１００の全体量に対して所望される圧縮に所望される期間で到達しようと試みることができる。
【００３７】
インターフェース制御装置２２０は、以下さらに詳細に説明するように、これらの最初の予測を行って、これらの最初の予測に関連した制御信号およびメタデータを、処理されるべきデータと共にＣ／Ｄエンジン２３０に送信し、また、Ｃ／Ｄエンジン２３０は特定のブロックを処理しているときに最初にこれらの制御信号およびメタデータを使用するが、Ｃ／Ｄエンジン２３０は、以下において詳細に説明するように、その制御信号およびメタデータにより示唆された動作からはずれて独立的に決定することが可能であることもまた認識される。
【００３８】
制御信号およびメタデータの生成に関して、異なったデータを圧縮するために異なったスレッドを使用する考えに関する本発明の別の特徴を以下に説明する。異なったスレッドは、ファイル内の各ブロックに対して必要とされたときに決定されてもよいし、あるいはいくつかのファイルの全てが同じスレッドを使用してもよい。この決定がどのようにして行われるかを以下に説明する。新しいスレッドを構成するか否かの考慮に関して、再び、インターフェース制御装置２２０は特定の圧縮ルーチンを使用して各ブロックを圧縮するのに必要とされる期待期間について予測していることが認識される。これを見る別の方法は、インターフェース制御装置２２０が、その圧縮ルーチンに対して各ブロックに関してルーチンが行われた符号化パスの数を評価することである。したがって、あるブロックは圧縮が困難であろうとインターフェース制御装置２２０が予測した場合、別のスレッドが識別されることができ、そのスレッドに関してＣ／Ｄエンジン２３０が圧縮ルーチン動作を始めるのに必要な情報が与えられているならば、そのスレッドはそれと固有のメタデータおよび制御信号を関連付けている。このようにして、独立的に圧縮されることをインターフェース制御装置２２０により決定された各ブロックに対して、別のスレッドが生成される。
【００３９】
本発明は必要とされた場合には、各ブロックに関して独立的に動作することができるため、多くの例においてそれは単一のスレッドにより多数のブロックに関して動作するが、図３のステップ３６０によって示されているように、インターフェース制御装置は、新しいスレッドを生成すべき時期または多くのブロックに対して同じスレッドを使用すべき時期を決定することが可能である必要がある。たとえば、データのブロックを圧縮するために必要とされる時間があるしきい値より大きい場合、そのブロックに対して新しいスレッドがインターフェース制御装置２２０によって生成される。そうでない場合には、インターフェース制御装置２２０により同じスレッドを介して圧縮されていることに関してブロックのストリングがタグ付けされるように、別のブロックが前のブロックに追加される。
【００４０】
上記を考慮して、インターフェース制御装置２２０は、各スレッドに対する実行を示唆した圧縮ルーチンを示す制御信号をＣ／Ｄエンジン２３０に発生することが認識される。インターフェース制御装置また、データが適切に転送されることを保証するために別のルーチンハンドシェーキング信号を発生するが、これらの説明は不要である。以下、発生されたある診断制御信号について適宜説明する。
【００４１】
さらに、発生されたメタデータは、圧縮ルーチンの特性と、および処理されているストリームのタイプと関連付けられることのできる重要なパターンとを提供する。図１のｂにはメタデータの編成が示されている。圧縮ルーチンのメタデータ特性に関して、以下の３つが重要である：
１．上述したように所望の圧縮量を達成するために行われる必要があるであろうとインターフェース制御装置により予測されたパスの数をＣ／Ｄエンジンに示す要求パス変数；
２．Ｃ／Ｄエンジンに送られたときにはブランクであるが、Ｃ／Ｄエンジンがインターフェース制御装置にパスし、その結果それがその予測テーブルを更新することができる完了パス変数；
３．メタデータ内において後続するパターンの数を示す変数内パターン。典型的には、最初はパターンがない。圧縮ルーチンにより処理されたストリームの第１のパスの後、パターンがデータ内に見出されるようになり、以下さらに詳細に説明するように、それが使用される。これらのパターンはメタデータ内にセーブされる。
【００４２】
上記説明により、スレッド決定ステップ３６０が完了すると、ステップ３７０が始まり、適切な制御信号、メタデータおよびデータのスレッドがＣ／Ｄエンジン２３０に転送され、その結果所定のスレッド内の各ブロックに対する圧縮が行われることができる。
【００４３】
図３Ｂは、特定のスレッドに関して圧縮ルーチンを行うというリクエストをＣ／Ｄエンジン２３０がインターフェース制御装置２２０から受取ったときに行う種々のステップを示している。ステップ４１０によって示されているように、Ｃ／Ｄエンジン２３０は初期制御信号、メタデータおよび対応したデータブロックをインターフェース制御装置２２０から受取って、関連したメタデータおよびデータブロックを図２に示されているバッファ管理装置２３２のメモリ中に記憶する。バッファ管理装置２３２はまた、以下に説明するように、中間動作結果だけでなく、最終的にはインターフェース制御装置に戻される最終的な圧縮結果もまた記憶するので、それはデータ管理装置として動作する。
【００４４】
続いて、ステップ４２０に示されているように、Ｃ／Ｄエンジン２３０と関連したプロセッサは圧縮ルーチン制御信号を使用して適切な圧縮ルーチンを呼出し、その圧縮ルーチンの第１のパスの実行を開始する。
【００４５】
この第１のパスを理解し易くするために、以下において図２の圧縮／圧縮解除ルーチンブロック２３４に示されている圧縮ルーチンを説明する。圧縮／圧縮解除ルーチンブロック２３４は、各ファイルタイプに対して圧縮／圧縮解除ルーチンと、好ましくはファイルタイプに対して冗長な圧縮／圧縮解除ルーチンと、および利用できるようになることのできる別の圧縮／圧縮解除ルーチンとが存在するように、多数の異なった圧縮およびそれらの対応した圧縮解除ルーチンを含んでいるであろう。別の圧縮／圧縮解除ルーチンが使用可能ではあるが、各圧縮／圧縮解除ルーチンは典型的にＣ＋＋のような適合可能なプログラミング言語で書かれていることが好ましい圧縮／圧縮解除アルゴリズムと、知られているように、これと関連付けられた圧縮／圧縮データのテーブルとから構成されている。上述したように、使用される特定の圧縮／圧縮解除ルーチンは、本発明の技術的範囲内のものとは考えられておらず、したがってこのようなルーチンの詳細な説明は不要である。
【００４６】
第１のパスの後、ある圧縮ルーチンを使用してブロックが符号化されると、符号化された情報に完全に冗長なパターンは含まれないだろう。したがって、通常のシステムでは圧縮はこの時点で完了し、もしさらに圧縮する必要があるならば、別の圧縮ルーチンにより圧縮プロセスを再度スタートする必要がある。しかしながら、本発明においては、ここに記載されているように、すでに圧縮されたデータの部分的に冗長なパターンが得られ、その後メタデータのパターンとして記憶され、それ故、以下さらに詳細に説明するように、前に圧縮されたブロックの２度目のパスでの再圧縮の前に、これらのパターンを使用して圧縮されたシーケンスを変更することができる。
【００４７】
圧縮ルーチン４２０の開始中、圧縮ルーチンに要する時間が追跡され、バッファ管理装置２３２の診断メモリ部分の中に記憶される。ルーチンの実行が成功するのに要した時間がある予め定められた期間より長い場合、ステップ４２２により示されているように警報が設定され、それによって同じ圧縮ルーチンと関連付けられた圧縮データの異なったテーブルのいずれかを使用することか、または異なった圧縮ルーチンを一緒に使用することをＣ／Ｅエンジンに示す。この警報はまた、ルーチンによる実行が所望の期間内に成功したが、達成された圧縮が、たとえば、予測されたものより５乃至１０％大きい等、予測された範囲から数パーセントだけ外れている場合に設定されることができる。
【００４８】
圧縮に要する時間が長くなるか、あるいは圧縮が十分されない理由は多い。たとえば、ヘッダファイルタイプは間違ったラベルを付けられる可能性があるため、それに関連したデータが予想されたものとは異なった特性を示すか、あるいはブロック内のデータは、単に予期されたものとは異なったデータに基づいて異なった特性を示す可能性がある。
【００４９】
ステップ４２２によって示されているように、別の圧縮ルーチンが必要であることが決定された場合、ステップ４２４に進んで、圧縮ルーチンは処理されているブロック内のビットのパターンの評価に基づいて変更される。異なったファイルタイプは典型的に異なったパターンを有しているため、評価においては、あるタイプのテーブル等の中にパターンが記憶されることのできる種々のファイルタイプに関連付けられた異なったパターンの前の知識を有していることに基づいてパターンが認識されることができる。
【００５０】
ステップ４２２における最初のブロックまたは複数のブロックに関する圧縮ルーチンの第１のパスの完了後、中間的なものであってもよい結果が得られ、バッファ管理装置２３２中に記憶される。図４のｃには、これらの中間的な結果が示されており、これは、図４のａに示されているビットマップファイルＢ１の圧縮の一例を示し、このビットマップファイルＢ１は、図４のｂに示されているように、４つのブロックＢ１ａ，Ｂ１ｂ，Ｂ１ｃおよびＢ１ｄに上述のように分割されたものである。このファイル中の全てのブロックは、上述のようにインターフェース制御装置２２０により単一のスレッドから形成されたと仮定すると、圧縮ルーチンによる第１のパスの終りに結果的に得られる出力は４つの対応した圧縮されたブロックＢ１ａｅ，Ｂ１ｂｅ，Ｂ１ｃｅおよびＢ１ｄｅとなる。
【００５１】
しかしながら、ステップ４２０ａによって示されているように、この第１のパス中に、圧縮ルーチンは、説明された例の中の４つのブロックＢ１ａ，Ｂ１ｂ，Ｂ１ｃおよびＢ１ｄのような処理されているブロック内において見出されたパターンのコピーをバッファ管理装置２３２のメモリ中に記憶する。パターンのビット長は変化する可能性があるが、３乃至８ビットのビット長を使用することが好ましく、６ビット長の使用が最も好ましい。これは、それより短い長さのパターンではそれ以上の圧縮が行われず、また、それより長いビット長は結果的に冗長または部分的冗長を有するパターンが少ないからである。ファイルタイプが記憶されるパターンのタイプを決定するために使用されることができることもまた認識すべきである。たとえば、圧縮されていない画像ファイルに対して、多くの冗長が期待されることができる場合、記憶されるパターンの数は典型的に、すでに圧縮されたファイルからのパターンを記憶する場合より少ない。これは、すでに圧縮されたファイル中の冗長なパターンの数がすでに最小だからである。
【００５２】
パターンが検出された時点で、それは図１のｂに示されているようなメタデータ中に記憶され、各パターンの追加を反映するように特性フィールド内パターンが更新される。ステップ４２０ａにおいて、圧縮ルーチンはあるパターンを見出し、その後それが類似していることに基づいてそのパターンをコピーする。パターンが類似しているかどうかは、そのタイプのファイル中のパターンの特性、パターンのランダム度、および前に処理された別のブロックに対して記憶されている別のパターンとの比較に基づくことができる。
【００５３】
上述の基準を適用した場合、第１のパスの時点では、あるものが典型的に部分的に冗長である多くの異なったパターンが潜在的に存在しているため、以下に説明するように、後続するパスに対してこのメタデータが使用される。
【００５４】
このパスの終わりに、圧縮ルーチンはいくつかの動作を行う。また、ステップ４２５によって示されているように、各スレッドと関連したメタデータは、そのメタデータが生成されたブロックに関連付けられる。
【００５５】
さらに、ステップ４２６に示されているように、Ｃ／Ｄエンジンは、行われる必要のある圧縮が行われたか否かを決定する。この決定は、異なったスレッドそれぞれの圧縮を追跡し、さらに圧縮する必要があることを決定することにより行われる。これに関して、異なったスレッドは異なった時間に始まり、終るため、これは、各スレッドの完了により発生する進行中のプロセスであることが認識される。必要とされる所望の全圧縮量が得られると、別のスレッドのそれぞれに対して進行している圧縮プロセスのパスは完了されることができ、あるいは現在のパスが終了され、ステップ４２７で示されているように、完了したパスの結果が使用されることができる。
【００５６】
ステップ４２８により示されるように、圧縮されたブロックの圧縮の続行が決定された場合、その圧縮ルーチンは所定のスレッド内の圧縮されたブロックを再検討して、符号化されたブロックの間にある類似性を決定し、その後ステップ４３０において、類似したパターンを含むブロックが隣合うようにブロックを再度順序付ける。類似性が存在するか否かを決定するステップ４２８において、圧縮ルーチンはいくつかの比較機能（加算、減算、乗算、除算、ＸＯＲ、ＡＮＤおよびこのような他の機能、）を使用して、メタデータ中に記憶されたパターンの部分的な重複があるか否かを決定することが好ましい。同じまたは類似したパターンを見出したとき、等しいか、それ以上であるか、あるいはそれ以下であるかのＧＥＴのツリートラバーサル（ｔｒｅｅ ｔｒａｖｅｒｓａｌ）動作が使用される。
【００５７】
これに関して、メタデータ中に記憶された各パターンはツリー構造であるため、典型的に、ツリー構造が種々のツリートラバーサル動作を使用して容易にトラバースされることを可能にする２進数である対応した番号によって、パターンは全て識別されることが可能であり、部分的な重複を有するパターンは識別され、その後比較機能により処理されることができる。したがって、符号化されたブロック内の１つのパターンが“０１０１”である場合、圧縮ルーチンの第１のパスの後、このような冗長は除去されているため、この同じパターンは存在しない。しかしながら、パターン“０１００”は存在している可能性があり、このパターンはパターン“０１０１”と１つのビットだけ異なっていることが明らかである。したがって、ステップ４２８において、これらのパターンが関連付けられていることが決定され、したがってステップ４３０において、パターン“０１０１”から同数のビット長だけオフセットされたものとしてパターン“０１００”が存在すること、およびその代りパターン“０１００”はパターン“０１０１”マイナス“１”で表されることが可能であることをポインタで示すことによりパターンを再度順序付けることが可能にされる。したがって、符号化されたストリームは、パターン中のこの部分的な重複を反映してそれを除去するように変更される。さらに、これらの動作がストリーム内の前に圧縮されたブロックの全てに対して行われると、圧縮ルーチンによって行われる後続の圧縮パスのためにそのサブセットまたはそのスーパーセットが再び圧縮ルーチンに送られ、さらにまた圧縮されるか、これは、再度圧縮されたストリームのブロック内のパターンと前に第１のパスの圧縮から結果的に得られたパターンとは今や異なったものになっているためである。
【００５８】
パス間において、使用される比較動作のタイプは、適応可能な方法で変更されることができることもまた認識されるべきである。とくに、比較動作の適応可能な決定は、代表的なファイルタイプパターンに比較された圧縮されたブロックのパターンに基づいて行われ、この代表的なファイルタイプのパターンもまた上述のように、システム上のテーブル中に記憶されることができる。
【００５９】
与えられた例で説明を続けると、ブロックＢ１ａｅとＢ１ｃｅが類似性を有し、ブロックＢ１ｂｅとＢ１ｄｅが類似性を有していると決定され、図４のｄに示されているように、そのようにしてブロックを再度順序付けることができる。
【００６０】
決定ステップおよび再順序付けステップを行ったとき、第１のパスで生成された各スレッドは対応した圧縮されたブロックおよび対応した診断信号から除去され、上述したように、インターフェース制御装置２２０に送られ、前に生成された各スレッドが完了されていることを示すであろう。圧縮の第２回以降のパスのこの部分において、使用されるメタデータは前のパスのスレッド内の各ブロックに対して生成されたメタデータに対応していることもまた認識される。したがって、示されている例において、Ｂ１ａｅ、Ｂ１ｂｅ、Ｂ１ｃｅおよびＢ１ｄｅのスレッドからのメタデータは同じスレッドからのものであったため、Ｂ１ａｅ／Ｂ１ｃｅスレッドおよびブロックＢ１ｂｅ／Ｂ１ｄｅスレッドに関して同じメタデータが使用される。しかしながら、ブロックが、以前に２つの別々のスレッドであったものを組合せたものだった場合、２つの別々のスレッドのそれぞれからのメタデータが組合せられ、この動作において使用されることが認識される。しかしながら、この後者の実施はすでに複雑なシステムに複雑な別の層を付け加え、したがって、その実施はこの時点では好ましくない。
【００６１】
再度順序付けられると、圧縮エンジンは、再度順序付けられたデータの特性に基づいてステップ４３２で実施すべき新しいスレッドの数を決定し、信号がインターフェース制御装置に送られ、新しく生成された各スレッドを識別する。したがって、上述された例において、ブロックＢ１ａｅおよびＢ１ｃｅは類似性を有し、ブロックＢ１ｂｅおよびＢ１ｄｅは類似性を有していることが決定されたので、圧縮ルーチンはこれらのそれぞれを別々のスレッドとして実施することを決定してもよい。したがって、将来別々のスレッドとして圧縮されることに備えて、これら２つのスレッドはそれぞれ独立して処理されることが好ましい。
【００６２】
上述のメタデータの使用および再順序付けによりさらに操作された以前圧縮されたデータに対する圧縮動作は、ステップ４２０の説明およびその後に説明したように続行する。しかしながら、所望される圧縮量にまだ達していないために圧縮が続行される場合、パスが繰り返された後にそれ以上圧縮が行われなければ、このプロセスをステップ４３４として示されている手動無効で終了させることが可能であることを認識すべきである。この終了はまた自動的に行われることが可能であり、すなわち、ある整数であるＮ回のパスが繰り返された後に所望の圧縮が得られない場合はプロセスが終了する。
【００６３】
第２のパスの結果、圧縮がさらに行われた各スレッドに対して、上述の第１のパスの後に行われたステップが再び繰り返され、その後プロセスは、それが完了するか、所望の圧縮への完了が不可能であることが決定されるか、あるいは時間切れになるまで繰返えされて続行される（本質的に所望の圧縮の達成が不可能だった場合と同じである）。
【００６４】
以下図５Ａ乃至５Ｅの説明を参照として明らかになるように、第３、第４および第５のパスもまた可能であり、各後続するパスにしたがって、部分的に重複しているメタデータが連続的に小さくなり、それに応じて、プロセスに終りに、残っているメタデータは保存されることが好ましい。
【００６５】
１つの圧縮動作から得られたメタデータ、とくに３、４、５のパスが行われた後に存在しているメタデータはその状態で保存され、その後別の圧縮動作においてメタデータとして使用され、全く異なる圧縮システムによってでも使用され、また、その別の圧縮動作に対しては、それは第１のパスの圧縮動作中に使用された情報として含まれることが可能であることが認識される。これらのパスの後に存在するメタデータ中のパターンは、そうでなければ容易に明らかにならない捕えがたい冗長または部分的冗長を示すために、そうでなければ利用不可能であるメタデータの存在のために別の圧縮動作の速度が増加する。
【００６６】
データのストリームの成功的な圧縮ルーチンの終りにおいて、一連の圧縮されたブロックが結果的に得られ、その後それらはバッファ管理装置２３２によりインターフェース制御装置２２０に送り返される。
【００６７】
以下図５Ａ乃至５Ｅに関してさらに詳細に説明されるように、上述したプロセスにおいて、１、２、１０回以上等の、ある回数のパスの後、データはある量だけ圧縮され、その後、本発明にしたがってさらに圧縮することは不可能になるであろう。したがって、このような時点で、データは可能な限り圧縮されたと考えられることができ、その後送信され、記憶され、あるいは、そうでなければ、圧縮された形態で所望に応じて使用されることができる。しかしながら、ある時点において、圧縮解除が行われるであろう。図５Ａ乃至５Ｅから明らかになるように、本発明によると、圧縮解除動作で行われる動作は圧縮中に行われた動作を反映するため、圧縮解除動作は相反動作である。したがって、圧縮解除アルゴリズムは圧縮アルゴリズムの逆のものであり、上述のように行われるその他の動作は同様に置換されることができる。しかしながら、圧縮動作と圧縮解除動作の間の１つの顕著な違いは、圧縮動作は圧縮するのにおそらく多数のパスで行われる可能性が高いが、圧縮解除動作は常に単一のパスでしか行われないことである。これは、圧縮動作の各パスが上述のように符号化されたデータを処理した同じ圧縮アルゴリズムを使用して動作し、元のデータストリームの全体が圧縮されたデータから最終的に導出されることができるためである。対照的に多くのパスを使用して圧縮する通常の圧縮技術は別のパスを行うときに、圧縮されたデータではなくソースデータに戻って、これを使用するため、このような技術では多数のパスが圧縮解除を行う必要がある。
【００６８】
以下、簡単化されたサンプルデータセットを使用するサンプル動作を図５Ａ乃至５Ｅを参照として説明して、多数パス圧縮および圧縮解除能力の両者を例示する。この例において、上方のボックス中のアルファベットはデータ要素のセットとして使用され、“Ａ”は“Ｂ”の値より１だけ小さい値を有していることを認識すべきである。これはさらに簡潔な説明が与えられることを可能にするために簡単化されたものであるが、しかし本発明が処理し、圧縮および圧縮解除を行うことのできるデータのタイプを制限するものとしてこれを解釈してはならない。さらに、メタデータに基づくツリートラバーサルおよび比較機能動作を説明するときに示されるようなデータは圧縮エンジンにより圧縮されているとみなされ、圧縮エンジンは、たとえば、パターンＡＡＡを圧縮されていない形態のまま残しておかないことまで明らかになるであろう。
【００６９】
示されているように、図５Ａは、図１のｂを参照として上述した情報を有し、以前決定されたメタデータマーカーをすでに有している単一のファイルからのデジタルデータと、および上述したように第１のパス圧縮中に使用可能な異なった圧縮事象からの可能性のある実際のメタデータの一例を示している。しかしながら、以下の例に対して、第１のパスの前はメタデータマーカー部分中にメタデータパターンが１つも存在しないことが仮定されている。
【００７０】
符号化されたブロックＡ乃至Ｅはそれぞれ、図５Ａの“０パス後”の部分により示されているようなブロック自身に細分されることができ、ブロックＡは上述したようにインターフェース制御装置２２０によって最初にブロックＡ１，Ａ２およびＡ３に細分される。示されているように、ブロックＡ１乃至Ｅ３は単一のスレッド中でグループ化されている。圧縮エンジン２３２による第１のパス圧縮の完了およびその第１のパス圧縮に関連したスレッドの除去後、ファイル構造は図５Ａの“１パス後”の部分に示されているものとなる。その後、符号化されたデータは上述のように第２のパスの開始前に処理される。示されているように、ブロックＡ１，Ａ２，Ｂ１，Ｂ２・・・・はラベルによって同じであると識別されるが、しかし、それらはさらに圧縮されていることを認識すべきである。さらに、ブロックＢ１は、図面下方に配置されブロックＢ１と関連付けられている楕円の中にＡ３Ｂ１によって示されているように以前ブロックＡ３およびＢ１であったものを組合せることにより形成されている。
【００７１】
図５Ｂは、各パスで圧縮と関連付けられたメタデータを示している。上述したように、第１のパスにおいてはメタデータパターンが存在しないことが仮定されていたので、第１のパスの前からのメタデータパターンは示されていない。“１パス後”において、示されているメタデータはメタデータパターンＡＡＡ，ＢＢＢ，ＣＣＣ・・・・である。したがって、この例におけるパターン長は３であり、上述されたそれより大きい数ではないことが認識される。これらのメタデータは、図５Ｄに示されている０パス後のデータのブロックＡの第１のサブブロックＡ１において見出されたパターンに対応している。ＡＡＡ，ＢＢＢおよびＣＣＣはそれぞれ互いに類似していないので、それぞれが別個のメタデータパターンとして識別されている。
【００７２】
図５Ｄを参照とすると、第１および第２の符号化されたブロックＡおよびＢが第１のパスの後に、ＧＥＴ＝トラバーサル機能およびａｎ＝比較機能により動作された後に、第１および第２の符号化されたデータ構造が図示されているように発生する。これらの例では簡単化のために比較機能に等しいものだけ使用されているため、この比較機能は識別子により示されていないが、しかし、実際には使用されている比較機能は処理されているパターンに関連した別のデータ内に記憶されていなければならないことが認められる。示されているように、符号化されたデータサブブロックＡ１は単独でおかれており、これは、別のパターンのどれかに等しいパターンがないためである。しかしながら、サブブロックＡ２においてＡＡＡパターンは、図５Ｃに示されているようにブロック識別子、ブロックカウンタ、動作およびデータオフセットである種々の識別子により（ａ２０７）として表される。すなわち、この例において、“ａ”はそのデータがブロックＡからのものであったことを表し、“２”はそのデータが第２のサブブロックからのものであったことを表し、“０”はＧｅｔ＝トラバーサル動作を表し、“７”はそのパターンに対する第１の文字のビット位置を表している。その後示されている他のパターンは、これらの類似性を示すためのこの同じ命名法により例示される。
【００７３】
図５Ｅは、ＧＥＴ＝ツリートラバーサル動作を使用する１パス後からＧＥＴ＞＝ツリートラバーサル動作が使用される２パス後へのトランジションからのデータを示している。示されているように、ＢＢＢはＡＡＡとは１だけ異なっているので、ＢＢＢパターンは（ａ１１４）になり、“ａ”はデータがブロックＡからのものであったことを表し、“１”はデータが第１のサブブロックＡからのものであったことを表し、“１”はＧｅｔ＞＝トラバーサル動作を表し、“４”はそのパターンに対する第４の文字のビット位置を表している。その後に示されている他のパターンは、これらの類似性を示すためのこの同じ命名法により例示される。
【００７４】
再び図５Ｂを参照とすると、パス２後に対するメタデータが変化していることが認識される。これはこのパスの後、残っている利用可能なメタデータパターンがＡＡＡ，ＧＧＧ，ＭＭＭ，ＨＵＵ，ＫＨＫ，およびＸＹＺであるからである。しかしながら、ＡＡＡは、それが再び見出されるであろうという意味においてメタデータではないが、しかしそれは別のパターンが関連しているパターンであるため、それが保持されていることを認識すべきである。
【００７５】
上述の圧縮／圧縮解除システムの特定の適用は多様である。本発明の技術的範囲を理解するために、以下にいくつかの例を示す。
１．デジタルムービーの圧縮／圧縮解除（圧縮時間は気にしなくてよいが、圧縮解除時間は取り扱いに非常に注意を要する）。
【００７６】
２．ディスク装置上の種々のファイルの圧縮／圧縮解除（圧縮の量の取り扱いに非常に注意を要し、圧縮および圧縮解除時間にも注意する必要がある）。
【００７７】
３．インターネット上での配信用の実時間ビデオフィードの圧縮／圧縮解除（圧縮時間および圧縮解除時間の取り扱いに非常に注意を要する）。
【００７８】
この明細書では特定の実施形態を参照として本発明を説明してきたが、上記の開示において修正、種々の変更および置換は自由に行われるものである。たとえば、本発明は簡明にするために別個のコンポーネントである（これは好ましい）インターフェース制御装置およびＣ／Ｄエンジンに関して記載されているが、この明細書に記載されている動作および機能は、依然として本発明の技術的範囲内においてそれらの等価なものを単一のプロセッサまたはもっと多くのプロセッサが行うように適合されることが可能である。したがって、本発明のいくつかの特徴は別の特徴を対応的に使用せずに使用され、また、添付されている請求の範囲に記載されている本発明の技術的範囲を逸脱することなく、別の修正を行うことが可能であることが認識されるであろう。
【図面の簡単な説明】
【図１】
本発明による処理されることのできる異なったファイルタイプを含むデジタルデータの例示的な部分とメタデータとをそれぞれ示す概略図。
【図２】
本発明による圧縮／圧縮解除システムのブロック図。
【図３Ａ】
本発明による圧縮中の最初のインターフェース制御装置の動作を示すフローチャート。
【図３Ｂ】
本発明による圧縮中の圧縮エンジン動作を示すフローチャート。
【図４】
本発明によるデジタルデータに対する圧縮動作の、圧縮動作中の種々の回数での効果を示す概略図。
【図５Ａ】
圧縮動作中の種々の回数におけるデジタルデータの圧縮中における圧縮されたデータおよびメタデータの生成を示す概略図。
【図５Ｂ】
圧縮動作中の種々の回数におけるデジタルデータの圧縮中における圧縮されたデータおよびメタデータの生成を示す概略図。
【図５Ｃ】
圧縮動作中の種々の回数におけるデジタルデータの圧縮中における圧縮されたデータおよびメタデータの生成を示す概略図。
【図５Ｄ】
圧縮動作中の種々の回数におけるデジタルデータの圧縮中における圧縮されたデータおよびメタデータの生成を示す概略図。
【図５Ｅ】
圧縮動作中の種々の回数におけるデジタルデータの圧縮中における圧縮されたデータおよびメタデータの生成を示す概略図。
【図１】
2004533733.tif 000007
【図２】
2004533733.tif 000008
【図３Ａ】
2004533733.tif 000009
【図３Ｂ】
2004533733.tif 000010
【図４】
2004533733.tif 000011
【図５Ａ】
2004533733.tif 000012
【図５Ｂ】
2004533733.tif 000013
【図５Ｃ】
2004533733.tif 000014
【図５Ｄ】
2004533733.tif 000015
【図５Ｅ】
2004533733.tif 000016
【国際公開パンフレット】
2004533733.tif 000017
2004533733.tif 000018
2004533733.tif 000019
2004533733.tif 000020
2004533733.tif 000021
2004533733.tif 000022
2004533733.tif 000023
2004533733.tif 000024
2004533733.tif 000025
2004533733.tif 000026
2004533733.tif 000027
2004533733.tif 000028
2004533733.tif 000029
2004533733.tif 000030
2004533733.tif 000031
2004533733.tif 000032
2004533733.tif 000033
2004533733.tif 000034
2004533733.tif 000035
2004533733.tif 000036
2004533733.tif 000037
2004533733.tif 000038
2004533733.tif 000039
2004533733.tif 000040
2004533733.tif 000041
2004533733.tif 000042
2004533733.tif 000043
2004533733.tif 000044
2004533733.tif 000045
2004533733.tif 000046
2004533733.tif 000047
【国際公開パンフレット（コレクトバージョン）】
2004533733.tif 000048
【国際調査報告】
2004533733.tif 000049
2004533733.tif 000050
2004533733.tif 000051
2004533733.tif 000052
2004533733.tif 000053
2004533733.tif 000054