(57)【要約】データは、逆進的参照ストリングスキームの挿入を実施することによって圧縮される。各参照は、特定のデータストリングを、同一のコンテンツを有する関連付けられる以前のデータストリングに、参照することにより置換される。特に、符号化オブジェクトに対しての逆進的ストリング参照アイテムは、ポインティング及びポインティ・ストリングの制限に基づいて挿入され、参照アイテムは、関連付けられるシグナリング要素によって識別される。
2004518327.tif 000002
【特許請求の範囲】
【請求項１】
特定のデータストリングを、上記特定のデータストリングと同一のコンテンツを有する関連付けられる以前のデータストリングに、参照することにより置換することを指示する逆進的ポインタ−長さ参照ストリングを、データストリームに体系的に挿入することによって、データストリームの圧縮を行う方法であり、
上記逆進的参照ストリングを、ポインティ・オブジェクトへのポインティングによって、符号化オブジェクトを参照するよう挿入する段階と、
シグナリング要素の夫々に関連付けられる値によって、上記逆進的参照ストリングを識別する段階と、
シグナリング要素の夫々に関連付けられる更なる値によって、置換されていないデータを識別する段階と、
上記逆進的参照ストリングに対して、簡単に後方参照する後方参照スキームを与える段階とを含むことを特徴とする方法。
【請求項２】
上記方法は、連続する２つの段階で実行され、
第１の段階は、全ての後方参照を評価し、全てのポインタ−ライン対、及び、上記全てのポインタ−ライン対に関連付けられるポインティ・ストリングを指示し、
第２の段階は、上記ポインタ−ライン対を、上記ポインティ・ストリングによって実際に置換する、請求項１記載の方法。
【請求項３】
上記後方参照スキームは、１ビットのレベルで上記ポインティングを行うことによって与えられる請求項１記載の方法。
【請求項４】
上記後方参照スキームは、標準キャラクタと、上記ポインティングを行うための差別化シグナリング指示を足したストリング長指示と組合わされた、標準キャラクタ長を有するポインタによって上記ポインティングを行うことによって与えられる請求項１記載の方法。
【請求項５】
上記後方参照スキームは、上記逆進的参照ストリングが、順次、標準キャラクタと交互にされ、同時に、上記逆進的参照ストリングと上記標準キャラクタとの間の差別化指示を削除することにより与えられる請求項１記載の方法。
【請求項６】
上記後方参照スキームは、
上記逆進的参照ストリングと上記標準キャラクタとを区別する差別化指示を供給し、
上記差別化指示を含む上記逆進的参照ストリングの第１の標準長部と、上記逆進的参照ストリングの任意の残りの部分と標準キャラクタを含む上記標準キャラクタの第１の標準長部とに、別個のストレージポインタを供給することにより、与えられる請求項１記載の方法。
【請求項７】
上記参照ストリングは、符号化されたオブジェクトの数をシグナリングする長さ指示を有する請求項１記載の方法。
【請求項８】
上記参照ストリングは、符号化されていないキャラクタの数をシグナリングする長さ指示を有する請求項１記載の方法。
【請求項９】
上記参照ストリングは、関連付けられるポインティ・ストリングの最初の又は最後の一部の長さをシグナリングし、上記最初の又は上記最後の一部の長さは、上記ポインティ・ストリングの残りの部分をコピーする際に、省略される、請求項１記載の方法。
【請求項１０】
上記ポインタをキャラクタ単位で特定する請求項１記載の方法。
【請求項１１】
特定のデータストリングを、上記特定のデータストリングと同一のコンテンツを有する関連付けられる以前のデータストリングに、参照することにより置換することを指示する逆進的ポインタ−長さ参照ストリングを、データストリームに体系的に挿入する挿入手段によって、データストリームの圧縮を実行するよう構成された圧縮システムであって、
上記逆進的参照ストリングを、ポインティ・オブジェクトへのポインティングによって、符号化オブジェクトを参照するよう挿入するよう構成される上記挿入手段と、
シグナリング要素の夫々に関連付けられる値によって上記逆進的参照ストリングを識別する手段と、
シグナリング要素の夫々に関連付けられる更なる値によって、置換されていないデータを識別する識別手段と、
上記逆進的参照ストリングに対して、簡単に後方参照する後方参照スキームを与える参照手段とを含むシステム。
【請求項１２】
上記圧縮を連続する２つの段階で実行するよう構成されるシーケンシング手段を有し、
第１の段階は、全ての後方参照を評価し、全てのポインタ−ライン対及びそれらに関連付けられるポインティ・ストリングを指示し、
第２の段階は、上記ポインタ−ライン対を、上記ポインティ・ストリングによって実際に置換する、請求項１１記載のシステム。
【請求項１３】
上記逆進的ストリングと上記標準キャラクタとを区別する差別化指示を供給する供給手段と、
上記差別化指示を含む上記逆進的参照ストリングの第１の標準長部と、上記逆進的参照ストリングの任意の残りの部分と標準キャラクタを含む上記標準キャラクタの第１の標準長部とに、別個のストレージポインタを供給する供給手段とを有することによって、上記後方参照スキームを与えるよう構成される請求項１１記載のシステム。
【請求項１４】
請求項１１記載のシステムに使用するよう構成され、逆進的参照ストリングを、ポインティ・オブジェクトへのポインティングによって、符号化オブジェクトを参照するよう挿入するよう構成される挿入手段と、
シグナリング要素の夫々に関連付けられる値によって、上記逆進的参照ストリングを識別する手段と、
シグナリング要素の夫々に関連付けられる更なる値によって、置換されていないデータを識別する識別手段と、
上記逆進的参照ストリングに直接的に後方参照する後方参照スキームを与える参照手段とを含む、符号化装置。
【請求項１５】
請求項１１記載のシステムに使用されるよう構成され、
後方参照スキームを読出しする読出し手段と、
関連付けられるポインティ・ストリングによってポインタ−長さ対を置換する置換手段と、
復号化されたデータストリームを出力する出力手段とを有する、復号化装置。
【請求項１６】
請求項１５に記載される復号化装置とインタフェースするよう構成される請求項１４記載の符号化装置を用いた請求項１１記載の圧縮システムによって、請求項１記載の圧縮方法を用いて生成される圧縮情報が設けられる記憶媒体。
【発明の詳細な説明】
【０００１】
［発明の背景］
本発明は、請求項１の前提部分に記載される方法に関する。データを記憶する及び伝送する技術は、データ圧縮の利点を認識している。特に有利な圧縮スキームは、理論的に、特定のデータストリングを、全く同一のコンテンツを有する以前に発生した符号化されていない、又は、より正確に言えば、復号化されたデータストリングによって置換することである。そのような置換の信号発信（シグナリング）は、置換するストリングの長さの指示と組合わされた相対ポインタとして作成される。そこで、ポインタ−長さ対は一般的に、標準長のキャラクタより長さが長くなる。従って、このスキームでは、後続の復号化動作の時には、全ての後方参照を決定することを可能にするために、ポインタのレンジ内の全ての以前に復号化された情報を記憶するバッファが必要となる。しかし、実際の埋込みシステムでは、一般的に、そのようなバッファとして機能する利用可能なＲＡＭ記憶空間が不足する。このことは、許容できない費用レベルを示唆するか、又は、更には、この技術を適用できなくしてしまい得る。
【０００２】
［発明の概要］
従って、本発明は、特に、ＲＡＭ記憶空間の要件を少なくすることを可能にすることを目的とする。本願の発明者は、ポインタが以前に符号化されたオブジェクト又はストリングを参照することによって、かなりの利点を実現する手順を認識した。この場合の１つの理由は、ＲＯＭ記憶装置は、一般的に、符号化されたデータを格納するのに十分に利用可能であることである。このことは、多くの埋込みシステムにおいて言えることである。しかし、上述した記憶装置に関連する理由は、本発明の実施の様々な利点を得るのに必要条件ではない。改善されたスキームは、復号化されたデータをバッファリングする必要性をなくし、更に、ある程度のランダムアクセシビリティを可能にする。本発明は特に、比較的安価な電化製品に適用することを考えている。本発明は更に、様々な状況において、高い圧縮係数を可能にする。更に、ポインタは一般的に、キャラクタ、又は、他の標準長のアイテムだけでなく、オリジナルバージョン及びポインタ−長さ対を含む複数のオブジェクトに及ぶ。このような特徴は、同一のポインタ寸法に対し、大きいポインティングレンジを使用することを可能にし、従って、圧縮率が改善される。一方で、以前と同じポインティングレンジを保つことにより、本発明は、短いポインタを使用することを可能にする。その結果、これも圧縮率を改善する。トレードオフも、本発明の有利な実施を表す。
【０００３】
従って、本発明の１つの面では、本発明は、請求項１の特徴を示す部分を特徴とする。
【０００４】
本発明は更に、請求項１に記載される方法を実施するシステムに係り、更に、請求項１に記載される方法を実施するよう構成される符号化装置及び復号化装置に係る。本発明は更に、そのような符号化装置によって生成される情報を格納するか、及び／又は、復号化装置によって復号化されるよう構成される記憶媒体に係る。本発明の更なる有利な面は、従属項に記載される。
【０００５】
［本発明の更なる概念的検討事項］
本発明は、標準長のキャラクタと、ポインタ−長さ対とを、特定のシグナリング要素によって区別することを可能にする。しかし、本発明は、標準長キャラクタとポインタ−長さ対との間で、長さにおける不均一性も有する。この面は、後方に、又は、逆進的な方法で、ポインタによって指されるポインティ・ストリングを見つけることをあまり容易でないようにする。何故なら、特に、ポインタは、標準長のキャラクタと、更なるポインタ−長さ対との両方を、参照し得るからである。しかし、本願の発明者は、この問題を回避する様々な方法を認識した。
【０００６】
第１の解決方法は、１ビットのレベルでポインタを使用することである。これは、８ビットのキャラクタの場合、ポインタの長さを３ビット長くする。この取り組み方法は、簡単且つ十分に実現可能であるが、ポインタの長さが長くなることは、圧縮率を幾らか低下させてしまう。
【０００７】
第２の解決方法は、ポインタ−長さの組合せの寸法を、標準キャラクタの長さの倍数に設定することである。この取り組み方法も十分に実現可能ではあるが、形式の可能な選択を制限してしまう。更に、上述のシグナリング要素を使用することは、８ビットのキャラクタに対しては、対の全長は、通常１７ビット（２×８＋１）となることを意味し、この寸法は、最高条件より大きい。
【０００８】
第３の解決策は、ポインタ−長さ対を、順次、標準長のキャラクタと交互にすることである。このスキームは、差別化情報を必要とすることなく、データとポインタ−長さ対とを区別する問題に対し即座の解決策を提示する。２つの隣接する符号化されていないキャラクタの場合、０の距離を示すポインタが間に入れられる。このスキームは、迅速な双方向の復号化を可能にし、同時に、符号化された圧縮空間におけるポインティングを行う利点を依然として維持する。しかし、０距離のポインタを頻繁に挿入しなければならないことにより、全体の圧縮係数は下がる。
【０００９】
第４の、且つ、現在において好まれている解決方法は、１ビットといったような、上述のシグナリング要素又は差別化情報を、全てのオブジェクトに与えることにある。更に、オブジェクトは２つの部分に分けられ、第１の部分は均一の長さを有して、少なくとも差別化情報を含む。一方、オブジェクトの第２の部分は、残りの部分を有する。従って、第１の部分は、標準キャラクタに１ビットを足した長さを有する。又は、第１の部分は、シグナリングビットのみに相当する。更に、これら２つの部分の記憶装置における場所は、標準長の部分と残りの部分との両方に対し、別個のストレージポインタを維持することによって示される。ストレージポインタは、ストレージ構成に関連し、データシーケンス構成に関連するポインタ−長さ対自体に含まれるポインタとは識別される。実際、ポインタ−長さ対に含まれるポインタは、データシーケンス構成に関連する。
【００１０】
従って、本願の発明者は、オブジェクトを少なくとも２つの部分に分割し、そして、特に、各部分に対し２次的なストレージポインタを維持しながら、少なくとも信号発信情報を標準長の別個の部分におき、第２の部分を残りの部分のために取っておくことは、全ての様々なオブジェクト全ての長さを探す比較的やっかいな範囲が決まった手順を必要とすることなく、迅速な方法で逆進的な復号化を行うことを可能にすることを認識した。これは、以下において、特に開示される現在好適である実施例である。
【００１１】
ポインタ−長さ対における長さ指示について、どの実施例も、符号化されたオブジェクトの数を示す長さを有するか、又は、復号化した後のキャラクタの数を示す長さを有するかの間で選択しなければならない。第１の取り組み方法は、長さを指示するのに必要とするビットは少ないが、サブストリングの符号化をあまり容易には適応しなくなる。第２の取り組み方法は、その反対に有利に働く。
【００１２】
この好適な実施例の更なる拡張は、以下に示す。第１の例では、ポインタは、オブジェクト全体、即ち、ポインタ−長さ対及びキャラクタの夫々を参照すべきである。しかし、これは、以前の参照の全部ではなく、以前の参照の一部のみを含む以前のストリングを参照することができない。しかし、この問題は、ポインタ−長さ対を、ポインタ−長さ−スキップ−トリプルで置換することによって解決される。ポインタ−長さ−スキップ−トリプルでは、スキップ指示が、参照されたアイテムをコピーし始める前に、参照されたアイテムのうち、どの要素が無視されるべきであるか、又は、そのアイテムのどの最終要素が終わりにおいてコピーされるようスキップされるべきであるかを示す。
【００１３】
もう１つの解決方法は、キャラクタ単位でポインタを特定することである。ポインタ−長さ対の場合、長さは確認されなければならない。
【００１４】
［好適な実施例の詳細な説明］
本発明の上述した面及び更なる面、及び、利点は、好適な実施例の開示、特に、添付図面を参照しながら、以下に詳細に説明する。
【００１５】
背景の説明として、図１は、復号化されたデータシーケンスを示す。このシーケンスは、８ビットといった、ブロックとして示される標準長のキャラクタから成る。図示するように、シーケンスＡは、この例では、６つのキャラクタから成り、その後に、３つのキャラクタからなるシーケンスＢが続く。シーケンスＢの後に、シーケンスＡが２回目として生じる。この第２のシーケンスＡの代わりにポインタ−長さ対（Ｐ，Ｌ）を挿入することによってデータ圧縮が実現されるが、これは、ポインタ−長さ対が平均で置換されるシーケンスより短い長さを有する限りにおいて実現する。従って、ここでのポインタは、復号化されたデータシーケンスにおけるポインティ（ｐｏｉｎｔｅｅ）を指す。これは、ポインティは、デコーダがポインタ−長さ対を検出する際に、中間の記憶空間において依然として利用可能でなければならないことを意味する。
【００１６】
図２は、上述した前の技術及び本発明において使用されるべき、例示的なポインタ−長さ対の形式を示す。ポインタ−長さ対は、ポインタ−長さ対を他のデータから識別するシグナリングビットＳと、コピーされなければならないシーケンス（ポインティ）に対するオフセットを示す１０ビットのポインタＰと、コピーされなければならないストリングの長さを示す４ビット長の指示Ｌとからなる。結果として、この実施例では、ポインタのスパンは、１，０２４キャラクタであり、コピーされるシーケンスは最大で１６キャラクタとなりうる。一般的に、標準長のキャラクタも、シグナリングビットを有するべきである。
【００１７】
図３は、本発明の好適な実施例による符号化されたデータシーケンスを示す。ここでは、ポインタは、符号化されたデータシーケンスにおける正しい位置を指す。簡単にするために、標準キャラクタ及びポインタ−長さ対の、上述の差別化要素Ｓは、図では、別個に示していない。符号化されたシーケンスは、オブジェクトＣ、Ｄから始まり、その後に、Ｃの始まりを指すポインタ−長さ対Ｐ／Ｌが続く。図３では、ポインタ−長さ形式は、図２で使用される形式とは同じにはされていない。次に続くポインタＰ´／Ｌ´は、一般的に、Ｅといった１つ又は１つ以上の符号化されたシーケンスを指すが、更に、Ｐ／Ｌといった１つ又は１つ以上の更なるポインタ−長さ対全体も指す。圧縮の効果のために、これは、一般的に、特定のシーケンスがより頻繁にコピーされるようポインタのスパンが増加するか、又は、１０ビットではなく８ビットのみを有するといったように、ポインタが短く維持される。
【００１８】
図４は、スキップフィールドＳｋが設けられるポインタ形式を示す。このポインタ−長さの組合せの残りの部分は、図２に示すポインタ形式と同じである。ここでは、指示Ｓｋはポインティの一部を画成するが、これは、ポインティの、指示Ｓｋに示される以外の部分をコピーする前に省略されるべきポインティの一部である。もう１つの解決方法は、指示Ｓｋはポインティの一部を画成するが、これは、ポインティの指示Ｓｋに示される以外の先行する部分がコピーされた後にコピーされるべきであるポインティの一部である。このような省略（スキッピング）は、本発明の方法の柔軟性の度合いを良好に向上することが分かっている。
【００１９】
図５は、１つの実施例における符号化されたデータのストレージ構成を示す。この場合、７つのオブジェクトがあり、そのうち、４つの標準長キャラクタと３つのポインタ−長さ対がある。各オブジェクトは、図面に示す夫々の概念上のカラム２２を占有する。更に、各オブジェクトは、シグナリングビット２０を有する。ポインタ−長さ対のシグナリングビット２０は、標準長キャラクタのシグナリングビット２０とは異なる値を有する。更に、両方のストレージ部に対し、別個のストレージポインタ２４、２６が更新される。シグナリングビットに対して（２４）は、ポインタ−長さ対の数だけが考慮されるので、その値は、「３」（２進法では、０１１）となる。残りの部分に対して（２６）は、全てのエンティティがカウントされるので、ストレージポインタの値は、「７」（２進法では、１１１）となる。或いは、部分２６は、ポインタ−長さ対の数だけを計数してもよく、従って、その計数値は、「４」（２進法では、１００）となる。尚、シグナリング要素を含むオブジェクトの部分は、問題のオブジェクトの残りの部分の一部を含んでもよく、例えば、その一部に１つのキャラクタの長さを与える。
【００２０】
図６は、符号化装置を示す。標準寸法のキャラクタが、入力３０に到来し、ＦＩＦＯ形式で動作する、ストレージアレイ３２に格納される。次のキャラクタを受信すると同時に、プロセッサ３４は、ストレージアレイ３２にアクセスして、全く同一のコンテンツを有する以前のシーケンスを指すポインタ−長さ対によって置換されるべきである、実施例のポインタスパン内のキャラクタシーケンスを検出する。キャラクタシーケンスが検出されると、ストレージアレイにおける問題のアイテムは、ポインタ−長さ対によって、物理的、又は、実質的に置換される。後者の実質的な置換とは、アドレスシーケンスを修正することによる。ポインタ値が、上述したように、符号化されたオブジェクトの数、又は、符号化した後のキャラクタの数として測定される。更に、レジスタ３６が、アレイ３２における最初と最後の実際の（この場合、物理的、又は、実質的な）エントリ間の実際のスパンを格納する。オーバフローした場合、これらのアイテムは、装置３８を介して、出力４０、大容量記憶装置等へ伝送されるよう転送される。各オブジェクトは、それぞれ関連付けられる信号発信ビットを有し、更に、ストリームは、図５を参照しながら説明した２つのタイプのストレージポインタが散りばめられる。このようなストレージポインタの散りばめることの繰返し率は、一般的に設計の問題である。これは、データシーケンスの任意の点におけるランダムアクセシビリティを決定し得る。
【００２１】
ここで使用するアルゴリズムはグリーディなタイプであり、実行時に適用される。しかし、上述の拡張は、ポインタ−長さ対によって置換されるべき全てのストリングを検出する第１のランの後に、実際に置換を行う第２のランを行うことである。
【００２２】
図７は、復号化装置を示す。入力５０は、オブジェクトのストリーム（キャラクタ及びポインタ−長さ対）と散りばめられたストレージポインタのそれぞれを受信する。従って、別個に示していない入力検出機能は、標準キャラクタとポインタ−長さ対とを区別するビットを探すべき場所を知っている。任意の標準長のキャラクタは、ストレージアレイ５２に格納され、更に、プロセッサ５６によって読み出され、更なる適用の為に出力６２に出力されるよう出力装置５８に転送される。ポインタ−長さ対は、２値検出器６０を活性化し、２値検出器６０が活性化されることによって、プロセッサ５６はポインタ−長さ対を読出し、標準キャラクタを受信する場合に対して上述したように、出力６２で出力するための正しいデータシーケンスにアクセスする。ポインタ−長さ対を見つけた後、実際のストレージアドレスのアドレスカウンタは適切な値でインクリメントされ、それにより、対のポインタ−長さ対が、正しいアドレスオフセットを行うようにされる。ここでも、ポインタの適用可能なアドレススパンから外れると、関連付けられる情報は削除されるか、又は、無視される。
【００２３】
図８は、符号化フローチャートを示す。段階７０において、処理が開始し、適切な量のハードウェア及びソフトウェアが割当てられる。簡単にするために、図８には、処理の終了は示していない。段階７２において、符号化されるべき次のキャラクタを受信する。段階７４において、問題のキャラクタに、ポインタのスパンにおいて以前のストリングと一致するとして拒絶されていないストリングにおける任意の以前のキャラクタが、そのような前との一致があるかどうか確認される。段階７６において、そのような一致のテストが行われる。当然のことながら、ストリングの長さが増加するに従い、ポインタは更に後ろまで戻らないといけなくなる。というのは、そのような一致の可能性は、一般的に、ストリングの長さが増加するに従い低くなるからである。ストリングが見つかった場合（イエス）、段階７８において、長さは１でインクリメントされ、新しいポインタがセーブされ、システムは、段階７２に戻り、更に長いストリングに対し処理が行われる。ノーの場合、段階８０において、前から存在するポインタ−長さ対が格納される。コンパクトにされていないデータとコンパクトにされているデータとの差を考慮に入れるための処理は、上述したように第２のパスの間に行われるか、又は、むしろ、直ぐにポインタ値の再処理の際に行われ得る。その後、処理は段階７２に戻り、新しいストリングの始まりを探し始める。
【００２４】
図９は、復号化フローチャートを示す。段階１００において、処理が開始し、適切な量のハードウェア及びソフトウェアが割当てられる。簡単にするために、図９には、処理の終了は示していない。段階１０２において、適切なストレージポインタが読出しされ、更新される。段階１０４において、関連付けられるオブジェクトが読出しされる。段階１０６において、システムは、問題のオブジェクトがまさにキャラクタであるか否かを検出する。イエスである場合、段階１０８において、問題のキャラクタは復号化され、出力され、更に、記憶される。ノーである場合、段階１１０において、ポインタによって指されるストリングにアクセスする。次に、段階１１２において、問題のストリングが復号化される。最後に、段階１１４において、復号化されたデータが出力され、一方で符号化されたストリングは格納される。次に、システムは、再び段階１０２に戻る。
【図面の簡単な説明】
【図１】
１対のポインタ−長さが設けられた復号化データシーケンスを示す図である。
【図２】
ポインタ形式を示す図である。
【図３】
本発明の符号化されたデータシーケンスを示す図である。
【図４】
スキップフィールドが設けられたポインタ形式を示す図である。
【図５】
１つの実施例におけるストレージ構成を示す図である。
【図６】
符号化装置を示す図である。
【図７】
復号化装置を示す図である。
【図８】
符号化フローチャートを示す図である。
【図９】
復号化フローチャートを示す図である。
【図８】
2004518327.tif 000003
【図９】
2004518327.tif 000004
【国際公開パンフレット】
2004518327.tif 000005
2004518327.tif 000006
2004518327.tif 000007
2004518327.tif 000008
2004518327.tif 000009
2004518327.tif 000010
2004518327.tif 000011
2004518327.tif 000012
2004518327.tif 000013
2004518327.tif 000014
2004518327.tif 000015
2004518327.tif 000016
2004518327.tif 000017
2004518327.tif 000018
2004518327.tif 000019
【国際調査報告】
2004518327.tif 000020
2004518327.tif 000021
2004518327.tif 000022