(57)【特許請求の範囲】
【請求項１】
データ集合を圧縮する方法であって、
データ集合内で生起する、一つまたは複数の文字である記号列を選択する工程を含み、圧縮された前記データ集合はモード切替のための特殊記号を含むように構成され、
前記データ集合内の前記記号列のそれぞれの位置に対応する記号列符号を、同一の記号列の各位置に基づいて生成する工程であって、前記記号列符号は、同一の記号列についての対応する位置を示し、前記生成する工程は、前記記号列と前記記号列符号との関係が認識できるよう、各記号列に対する前記記号列符号を群終端（EOG；End-of-Group）記号で終了させることとともにさらに、前記特殊記号に基づくモードの一つを指し示すことを含み、前記モードは２つのモードを含み、１つのモードは記号列のあらかじめ決定された順序で通信されるモードであり、別のモードは記号列が前記記号列符号に前置されるモードである、工程と、
前記データ集合内で生起する任意の更なる記号列について、記号列を前記選択する工程、および、記号列符号を前記生成する工程を繰り返す工程と
を含む方法。
【請求項２】
前記データ集合の終端でノー・モア・グループ（No More Groups）信号を挿入する工程をさらに含む、請求項１記載の方法。
【請求項３】
前記圧縮されたデータ符号を記憶する工程、または、前記圧縮されたデータ符号を通信チャネルを通じて送信する工程をさらに含む、請求項１記載の方法。
【請求項４】
システムであって、
プロセッサを含み、前記プロセッサは、
データ集合内で生起する、一つまたは複数の文字である記号列を選択する処理を含み、
圧縮された前記データ集合はモード切替のための特殊記号を含むように構成され、
前記データ集合内の前記記号列のそれぞれの位置に対応する記号列符号を、同一の記号列の各位置に基づいて生成する工程であって、前記記号列符号は、同一の記号列についての対応する位置を示し、前記生成する工程は、前記記号列と前記記号列符号との関係が認識できるよう、各記号列に対する前記記号列符号を群終端（EOG；End-of-Group）記号で終了させることとともにさらに、前記特殊記号に基づくモードの一つを指し示すことを含み、前記モードは２つのモードを含み、１つのモードは記号列のあらかじめ決定された順序で通信されるモードであり、別のモードは記号列が前記記号列符号に前置されるモードである、処理と、
前記データ集合内で生起する任意の更なる記号列について、記号列を前記選択する処理、および、記号列符号を前記生成する処理を繰り返す処理と
を行うように構成されるシステム。
【請求項５】
コンピューティングデバイスによって実行されるコンピュータ実行可能命令を有するコンピュータ記憶媒体であって、前記コンピュータ実行可能命令は、前記コンピューティングデバイスに、
データ集合内で生起する、一つまたは複数の文字である記号列を選択する工程を含み、
圧縮された前記データ集合はモード切替のための特殊記号を含むように構成され、
前記データ集合内の前記記号列のそれぞれの位置に対応する記号列符号を、同一の記号列の各位置に基づいて生成する工程であって、前記記号列符号は、同一の記号列についての対応する位置を示し、前記生成する工程は、前記記号列と前記記号列符号との関係が認識できるよう、各記号列に対する前記記号列符号を群終端（EOG；End-of-Group）記号で終了させることとともにさらに、前記特殊記号に基づくモードの一つを指し示すことを含み、前記モードは２つのモードを含み、１つのモードは記号列のあらかじめ決定された順序で通信されるモードであり、別のモードは記号列が前記記号列符号に前置されるモードである、工程と、
前記データ集合内で生起する任意の更なる記号列について、記号列を前記選択する工程、および、記号列符号を前記生成する工程を繰り返す工程と
を実行させるためのコンピュータ記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
分野
本特許出願は、データ圧縮に関する。
【背景技術】
【０００２】
背景
近年、人々がネットワーク上でデータを共有することが益々一般的になってきた。しかしながら、帯域幅利用の見地から、データの送信にはコストがかかる。従って、例えば、大量のデータは、しばしば圧縮される。圧縮は、磁気メディアまたは他のメディア上にデータを記憶するときにも使用してもよい。
【発明の概要】
【０００３】
本発明は、データ集合を圧縮する方法であって、データ集合内で生起する、一つまたは複数の文字である記号列を選択する工程であって、前記データ集合はモード切替のための特殊記号を含む、工程と、前記データ集合内の前記記号列のそれぞれの位置に対応する記号列符号を生成する工程であって、前記生成する工程は、前記特殊記号に基づいてモードの一つに切り替える工程であって、前記モードは２つのモードを含み、１つのモードは記号列のあらかじめ決定された順序で通信されるモードであり、別のモードは記号列が前置されるモードである、工程と、前記データ集合内で生起する任意の更なる記号列について、記号列を前記選択する工程、および、記号列符号を前記生成する工程を繰り返す工程とを含むものである。
【図面の簡単な説明】
【０００４】
【図１】本発明主題に従う1つの態様を図解する略図である。
【発明を実施するための形態】
【０００５】
本発明主題は、本明細書の結末部分で特に指摘され、明確に特許請求される。しかしながら、本発明主題は、後述の詳細な説明を参照することによって、添付の図面と共に読まれる場合、機構および動作方法の双方について、その目的、特徴、および利点と共に最良に理解され得る。
【０００６】
詳細な説明
後述の詳細な説明では、多くの具体的細部が記述され、本発明主題の徹底的理解を提供する。しかしながら、本発明主題は、これらの具体的細部を伴わずに実施し得ることが、当業者によって理解される。他の場合には、本発明主題を不明瞭にしないように、周知の方法、手続き、構成要素、および／または回路は詳細に説明されていない。
【０００７】
後述の詳細な説明の幾つかの部分は、コンピューティングシステムの内部、例えば、コンピュータおよび／またはコンピューティングシステムメモリの内部に記憶されたデータビットおよび／または2進ディジタル信号に対する動作のアルゴリズムおよび／または記号表示の見地から提示される。アルゴリズムによるこれらの説明および／または表示は、データ処理技術の当業者によって使用される手法であり、それら当業者の作業の内容を他の当業者へ伝達する。アルゴリズムは、本明細書においておよび一般的に、所望の結果につながる動作および／または類似の処理の首尾一貫したシーケンスとして考えられる。動作および／または処理は、物理量の物理的操作を伴ってもよい。典型的には、必ずというわけではないが、これらの量は、記憶、転送、結合、比較、および／または操作することが可能な電気信号および／または磁気信号の形態を取ってもよい。時には、主に共通使用を理由として、これらの信号をビット、データ、値、要素、記号、文字、項、数、数字、および／またはその他として参照することが便利であることが証明されている。しかしながら、これらおよび類似の用語の全ては、適切な物理量に関連づけられるべきであり、便利なラベルにすぎないことを理解すべきである。他に具体的に言明されない限り、後述の論議から明らかであるように、本明細書の全体を通して、「処理」、「コンピューティング」、「計算」、「決定」、および／またはその他のような用語を利用する論議は、コンピューティングプラットフォームのプロセッサ、メモリ、レジスタ、および／または他の情報記憶、送信デバイスおよび／または表示デバイスの内部で、物理電子量および／もしくは磁気量ならびに／または他の物理量として表示されたデータを操作および／または変換するコンピューティングプラットフォーム、例えば、コンピュータまたは同類の電子コンピューティングデバイスの行動および／またはプロセスを指すことが了解される。
【０００８】
本発明主題に関して、範囲を限定しないが、データ圧縮方法の1つの特定の態様が以下で説明される。圧縮されるべきデータの集合または群の中で生起する記号列が選択される。データ内の記号列の一つまたは複数の位置を指し示す記号列符号が生成される。同様に、データ内の更なる記号列について、これが反復されてもよい。次いで、それぞれの記号列符号が組み合わされて、データ符号を形成してもよい。結果として生じるデータ符号は、データの集合または群の圧縮された形態である。このデータ符号は、所望に応じて送信または記憶されてもよい。
【０００９】
1つの特定の態様は、選択された記号列が生起する位置を連続的に識別し、選択された記号列の生起の間の距離を決定し、データ内の選択されたストリングの位置を表示する距離を含む符号を生成することによって、達成され得る。ただし、本発明主題は、この点に関して範囲を限定されない。同様に、ここでは、記号はデータの任意の型、形態、または形式を含んでもよい。例えば、データの型、形態、または形式は、レコード、ファイル、セクタ、クラスタ、群、および／またはこれらの一部分を含んでもよい。記号は、ワード、バイト、ビット、テキスト、文字、および／またはその他を更に含んでもよい。記号列は、単一または複数の記号を含んでもよい。同様に、記号列は固定長または可変長であってもよい。
【００１０】
1つの特定の態様について、記号列は、特定のまたはあらかじめ決定された順序で符号化され得る。ただし、これもまた単に例示的な態様であり、本発明主題は、この点に関して範囲を限定されない。代替的または追加的に、或る順序で符号化するのではなく、記号列は任意の順序で符号化されてもよい。そのような態様において、記号列符号は、例えば、特定の記号列を指し示す或る他の符号が前置されてもよい。ただし、本発明主題は当然この例示的な態様に範囲を限定されない。同様に、1つの特定の態様について、用いられるアプローチは、モード間、例えば、記号列符号が、あらかじめ決定された順序で送信または記憶されるモードと、順序があらかじめ決定されないモードとの間で切り替え可能であり得るが、この後者のモードにおいて、対応する記号列を表示する或る符号は、記号列符号の前にまたはその一部分として送られる。
【００１１】
記号列が記号列の反復を含む場合、記号列符号は、記号列の生起のランの存在を指し示すデータを含み得る。生起のランを指し示すデータの記憶または送信は、典型的には、圧縮の観点から、そのような生起を個別に送るよりも効率的であり得る。1つの特定の態様において、位置はランレングス符号化によって伝達されてもよいが、下記でより詳細に説明されるように、代替的または追加的に、他の符号化方法も可能である。同様に、符号化は、少なくとも部分的に、文脈に依存し得る。符号化されるべきデータの集合または群の長さが、例えば、あらかじめ知られていれば、この長さは、最初の記号列符号に前置され得る。態様の特色に少なくとも部分的に依存して、最後の記号列の位置は、この特定の記号列に対応する追加情報の送信または記憶を伴わずに決定され得る。これについては、下記でより詳細に説明される。
【００１２】
更に、全てまたは幾つかの記号列に関する副次的情報または追加情報も、データ符号の中に含まれ得る。1つの特定の態様において、特定の記号列に関する追加情報は、対応する記号列符号の終端で、または対応する記号列符号に関連づけられて、送られてもよい。あるいは、追加情報は、記号列符号を送った後または記憶した後に、送るか記憶されてもよい。より一般的には、追加情報を任意の時点または任意のやり方で提供することができ、復号器は、追加情報を、対応する記号列に関連づけることができる。使用されるべき記号列のリストまたは表は、例えば、あらかじめ決定されるか、あらかじめ定義され得る。代替的または追加的に、リストまたは表は、例えば、圧縮されるべきデータの中で生起する記号列に少なくとも部分的に基づいて編集され得る。
【００１３】
データの特定の集合または群のための記号列符号が記憶または送信された後、終端符号が使用され得る。最後の記号列を例外として、データの集合の中に存在する記号列の位置が記憶または通信された後、最後の記号列の位置が、少なくとも幾つかの態様において、決定されてもよい。従って、エンコーダは、以下でより詳細に説明されるように、そのような最後の記号列の位置を記憶または通信することを省略してもよい。
【００１４】
同様に、本発明主題によって包含される態様は、例えば、そのような方法を実現することができるコンピュータプログラム、および／またはそのような方法を実現することができるコンピュータシステムを含む。態様は、下記で説明されるような方法を達成することができるハードウェアおよび／またはソフトウェア符号器も含む。この符号器は、データの圧縮を表示するデータ符号からそのようなデータの元の集合または群を再構築することができるハードウェアおよび／またはソフトウェア復号器に組み合わせられる。これらの態様ならびに多くの他の態様は、本発明主題の範囲内にあることが意図される。
【００１５】
説明される少なくとも幾つかの態様において、圧縮はロスレスである。ただし、本発明主題は、この点において範囲を限定されない。例えば、幾つかの態様において、データ符号は、圧縮されるべきデータ内に収容された記号列の位置に関する情報を含んでもよい。
【００１６】
この特定の文脈において、圧縮されるべき関連データの任意の群、集合、または部分は、文字または他の記号の順序づけられたシーケンスとして扱われる。そのようなデータが、例えば、テキストを表示する場合、個々の記号は一つまたは複数のテキスト文字を含み得るが、これは当然必須ではない。多くの他の記号も表示され得る。より一般的には、記号は、データのバイトまたは他のサイズの群によって提示されてもよい。データの、より長いまたはより短い部分を使用することができ、これらの部分は、例えば、バイトまたはディジタルワード長の中に適合するかまたは適合しなくてもよいことも可能である。データが2進形態で表示される場合、記号は、特定の態様に依存して、固定長または可変長の単一ビットまたは複数ビットとして表示することができる。
【００１７】
例えば、ファイル、レコード、または他の単位データの集合として記憶されたデータは、1つの例として、全体として扱われるか、あるいは便利な長さに区画されるかまたは分割されてもよい。この長さは、ここでは記号列と呼ばれる記号群のためには十分に長く、或る圧縮効率量で符号化されるが、便利に処理するのに十分なほど短い。様々なアプローチが下記でより詳細に説明される。
【００１８】
最初に、例えば、1つの特定の態様において、データの集合内で生起し得る記号列のリストまたは表が確立される。このリストに、データの統計に関する経験的な知識または情報に少なくとも部分的に基づく記号列の初期リストを加えてもよい。例えば、テキストについて、幾つかの単純な例を提供すると、一般的な記号列は、「ee」、頻繁に生起する語、例えば「and」もしくは「or」、または句読点符号とそれに続く空白を含む。本発明主題は当然、これらの例またはこの特定の態様に範囲を限定されない。多くの可能な変更も、本発明主題の範囲内に含まれることが意図される。
【００１９】
他の例として、符号化が始まる前に特定のデータ集合を吟味し、一般的に生起する記号列を識別してもよい。代替的または追加的に、区画が適用される場合、これらの区画は、例えば、記号列の初期リストを使用して別個または独立に取り扱われてもよい。この初期リストは、例えば、より早期のデータ区画で発見される記号列から、例えば、少なくとも部分的に決定されていてもよい。
【００２０】
あるいは、記号列は、1つの例として、Lempel-Ziv-Welsh符号化で生起するように、符号化が進行するにつれて加えられてもよい。しかしながら、この態様の例において、記号列の符号化は、下記で説明されるように、LZW符号化で使用されるアプローチとは全く異なる。LZWにおいて、記号列は、他の、より長い記号またはストリングの置換によって符号化される。この理由により、LZWは時にはデータの集合を圧縮せず、幾つかのケースでは、より長いデータ集合を産出し得る。対照的に、本発明主題に従う態様は、以下でより詳細に説明されるように、圧縮を生じる可能性が高い。
【００２１】
データの群または集合を圧縮するため、最初の記号列を、利用可能な記号列のリストから選択してもよい。データ内のこのストリングの生起が位置付けられる。データ内の最初の記号列の位置が保持される。次いでこのプロセスは、データの追加的な記号列について反復され、集合または群を特定する。記号列を含むデータは、任意の順序で処理されてもよい。ただし、データの集合または群の冒頭から終端まで順次に処理できることが、1つの便利なアプローチであり得る。
【００２２】
典型的には、符号化はハードウェアまたはソフトウェア符号器によって達成される。1つの可能な態様において、符号器は、符号化された後のデータを、通信チャネルを渡って復号器へ送信するように並べてもよい。復号器は、リアルタイムまたは他のやり方で、受信された符号化データを使用してデータの集合を再構築するように並べてもよい。
【００２３】
本発明主題はまた、特定の態様に範囲を限定されない。従って、上記または下記で説明される態様は、例示を目的とした単なる例として意図される。多くの他のアプローチおよび／または態様は、これらの具体的な例とは別に、本発明主題の範囲内に包含されることが意図される。それにも拘わらず、これらの例を続けて、ここで図1を参照する。図1は、本発明主題に従う1つの潜在的態様の略図である。
【００２４】
図1の例において、1行のテキストが例示され、データの集合または群を表示する。同様に、ここでは英字「x」である記号列が、この例で処理される。本発明主題は当然、この例示的な態様または任意の1つの特定の態様に限定されない。この例は、解明を目的とした単なる例示である。多くの他の潜在的態様が、本発明主題の範囲内に含まれることが意図される。
【００２５】
ここでは「スタート」と呼ばれ、図1において10で示される場所からスタートして、テキストデータ110は、この例において順次に探索される。本発明主題は当然、先に言及したように、順次の探索に限定されない。それにも拘わらず、ここでも「x」である選択された記号列の生起が発見される場合、生起に関する情報、例えば、この例では「x」の場所が保持される。示された例において、ストリング「x」の最初の生起は、符番20によって指し示されるように、スタート位置10の後の5番目の位置で生起する。「x」は、再びスタートの後の位置9、または符番30によって指し示されるように、先の「x」から更に4位置のところにある。
【００２６】
例を続けると、「x」は、符番40によって示されるように、先の「x」の後で5位置後に再び生起する。後続の位置間隔は符番50、60、70で示されるように、それぞれ3、2、2である。
【００２７】
一旦テキストデータ110が、このようにして「終端」位置、ここでは100まで完全に解析されると、データ集合部分における位置を表示する符号が、この符号を記憶または送信することによって生成される。この特定の態様において、実際には、xが生起しない位置が記憶または伝達される。この文脈において、これはランレングス符号化と呼ばれる。ここでは、xを収容しない位置の「ラン」が符号化される。
【００２８】
図1の単純な例示的な態様において、データは1行のテキストを含み、記号列は英字を含んだ。本発明主題の範囲内にあるこの変更において、より長いおよび／または複雑な記号列の生起を探求してもよい。下記でより詳細に説明されるように、これらの記号列は、固定され、あらかじめ定義された形態を有する記号列を含むか、あるいは、例えば、形態、長さ、および／または組成の柔軟性を有する記号列を含んでもよい。柔軟性の程度はあらかじめ定義されるか、データの或る特性に少なくとも部分的に依存して計算されてもよい。幾つかの更なる例示的な記号列は、下記で示される。
・  任意の英字、記号、または文字a、例えば「x」。これは原則として単一の記号位置を含む。
・  任意の連字a1 a2、例えば「st」。
・  任意の組み合わせa1 a2 a3、例えば「str」。
・  任意の、より長い組み合わせa1 a2 a3 ...an。
【００２９】
最初の記号列の位置が決定された後、可能なまたは公知の記号列のリストの中の第2の記号列の位置が決定され得る。漸進的に、このようにして、データの集合が符号化され得る。符号化が進行するにつれて、符号器は、位置付けられた記号列に関する情報、例えば、位置を、幾つかの態様ではリアルタイムで、復号器へ送信してもよい。あるいは、符号化されたデータは、圧縮された表示として局在的に記憶されてもよい。
【００３０】
例示的な態様は、次のように疑似コードで表すことができる。
For S = 記号列
データの集合の中のSの位置を指し示す
End
【００３１】
更なる例として、8つの記号列の位置S1からS8からなる短いシーケンスSを考える。例示を目的として、ここでの記号列はテキストの断片を含む。ただし、本発明主題は、この点に関して範囲を限定されない。そのような断片は短く、かつ更に、記号列はテキストを全く含まなくてもよいが、依然として本発明主題の範囲内にある。2つの語の間の空白も、下記で例示されるように、この例では記号列を含む。
S: 「the test」
0005498783.tif 000002
【００３２】
この例において、記号列の位置は、任意の便利なアプローチによって指し示すことができる。位置を通信または送信する便利なアプローチは、単純な数字である。記号列の集合は、或る順序のデータ集合に関して評価される。例示する目的で、1つの例として、ここでの記号列は順序「e」「t」「s」「h」「空白」を有すると仮定する。ただし、本発明主題は当然、この例または任意の特定の例に範囲を限定されない。それにも拘わらず、この例について、次の記号列が次のように通信または記憶されてもよい。
0005498783.tif 000003
上記において、3および6は記号列「e」の位置を指し示し、1、5、および8は「t」の位置を指し示す。以下同様である。
【００３３】
この特定の態様について、特定の記号列の追加情報が通信または記憶されないことを指し示す手法が求められる。これを行う1つの方途は、群の終端（EOG）について特殊記号を定義することである。これは、この例示的な態様について、以下が表される。
0005498783.tif 000004
【００３４】
しかしながら、より効率的な符号化が求められる可能性がある。例えば、8つの位置の場合、従来の符号化方法によって記号列当たり3ビットが用いられ、EOGを通信することとは全く別個に、記号列を通信し得る。
【００３５】
圧縮効率を改善するため、連続した記号列の位置にランレングス符号化（RLC）を適用することができる。ランの長さを符号化するために任意の形態または型の符号化が使用され得、本発明主題は特定の形態または型に限定されない。例えば、少数の例を提供するために、Golomb符号器、または2進算術符号器が用いられてもよい。これらの符号器が用いられ、例えば、0および1の連続を符号化してもよい。0および1は、記号列が生起しないおよび生起する（またはその逆）データ集合内の一つまたは複数の位置を指し示す。当然これらは単なる例であり、本発明主題は、そのような例に範囲を限定されない。ランの長さを符号化する多くの他の可能なアプローチが想定され、本発明主題の範囲内に含まれる。
【００３６】
それにも拘わらず、この例を続けると、そのような態様において、記号列の位置は、ランレングス符号化され得る。このケースでは、例えば、6が後に続く3を符号化して記号列「e」の位置を指し示す代わりに、2を符号化して2つの位置が「e」の最初の生起前にスキップされることを指し示し、2を符号化して2つの更なる位置がスキップされ、位置3から位置6に達することを指し示してもよい。以下同様である。
0005498783.tif 000005
これはEOGに加えて、記号0、1、2、3、および6を伴うことによって圧縮を提供する。これは、符号化するためには、9つの記号1〜8プラスEOGよりも小さな集合である。
【００３７】
しかしながら、「有意性切り替え」に類似した方法によって、圧縮が更に改善され得る。より具体的には、ここでは、符号化される各連続記号列について、位置によって決定される記号列が多くなればなるほど、符号化されるべき位置は少なくなる。位置に関するこの追加情報を用いて、追加の圧縮を提供してもよい。
【００３８】
本実施例において、例えば、記号列「e」の位置は既知になるので、これらの位置は後の記号列の可能な位置としては省略されてもよい。実際には、符号化を目的として、スキップされるべき全位置ではなく、幾つの未知の位置がスキップされるべきかが符号化され、追加の圧縮を提供する。ランレングス符号化を有しなければ、この例では以下である。
0005498783.tif 000006
【００３９】
ここでの記号xは、既知である位置を指し示し、したがって伝達される必要はない。「0」および「1」の総数は40から20に低減され、ランレングス符号として、この総数は更に低減される。
0005498783.tif 000007
【００４０】
この特定の態様において、使用される異なる記号の数は、更に0、1、2、およびEOGに低減されている。「e」の位置を特定するためには、RLCは同じである。なぜなら、位置はあらかじめ知られていないからである。しかしながら、「t」の符号化において、「e」を含む位置は省略されてもよい。というのは、それらの位置は既に占拠されており、これらの位置は符号化および／または復号を目的としてRLCにおいて数える必要はないからである。
【００４１】
更に、一旦符号器が、符号化されるべき最後の記号列に来ると、この記号列の位置は追加情報を通信または符号化することなく決定され得る。より具体的には、この例示的な態様において、この記号列は、先に伝達または符号化されなかった位置を占拠する。しかしながら、このことは、符号化されているデータ集合の長さが既知であることを推定している。その場合、「h」のEOGに到達した後、この例における残りの記号列は暗黙的に「空白」であり、プロセスは追加の符号化または通信を伴わずに終了し得る。従って、所与の例において、「空白」は最後の記号列であることが既知であると推定して、追加の圧縮は以下のように得られる。
0005498783.tif 000008
【００４２】
しかしながら、データの集合の長さおよび／または記号列の数が既知でない場合、類似のアプローチを用いることが、幾つかの状況で求められ得る。例えば、符号化されているデータの集合の長さが既知でない状況では、様々なアプローチが可能であり、本発明主題は、特定のアプローチに範囲を限定されない。例えば、これは標準の長さを有することによって取り扱われてもよい。あるいは、長さ情報が、符号化される情報に前置されてもよい。しかしながら、データの複数の集合が符号化されており、大部分の集合が同じ長さを有する場合、長さを前置することは、圧縮の観点から非効率的である。同様に、データの長い通信について、この概念を続けると、標準の長さを用いてデータを細分する場合、標準の長さよりも小さい終端でデータの集合を通信または符号化することによって、標準の長さからの変更を取り扱ってもよい。
【００４３】
1つの方法は、符号化の前にデータ集合の全長を提供する段階を含み得る。標準の区画の長さが存在する場合、符号器および復号器は、幾つの区画が存在するかを決定し得、最後の区画が標準の長さよりも小さければ、最後の区画の長さを決定し得る。例えば、102個の記号列長のデータの集合が符号化されており、区画の標準の長さが5であれば、21個の区画が存在し、最後の区画は2の長さを有する。再び、先に暗示したように、全長は多くの方途でデータ符号の中に含まれてもよく、所与の例は、制限的であることが意図されない。本発明主題は、これらの例示的なアプローチならびに他の可能なアプローチを含むことが意図される。
【００４４】
同様に、記号列の取り扱いに関しても、数種のアプローチが可能である。例えば、先に例示したように、記号列のあらかじめ決定された順序を用いてもよい。しかしながら、交互に、記号列の生起頻度が知られているか、決定または近似され得る場合、記号列は生起頻度に関して順序づけられ得る。例えば、英語を単に例として使用すると、これは以下の順序、即ち、「e」「t」「a」「o」「i」「n」「s」「h」などであってもよい。「空白」は、この統計が例えばサンプル中で指し示すような順序で含まれてもよい。また、生起しない記号列が存在してもよい。このような記号列は、伝達されるべき空の群を形成することができる。そのようなアプローチを用いて、符号器および復号器の双方は、記号列の順序を有する。したがって、復号器が、例えば、EOGを受信する場合、復号器は次順の適切な記号列を決定することができる。
【００４５】
他のアプローチは、例えば、記号列を用いて、データの集合に明白に前置することであってもよい。または同様に、記号列は、前置されるか埋め込まれ、復号器は、符号化されたデータから適切な決定を行ってもよい。システムが2つのモードを用い、1つのモードでは記号列のあらかじめ決定された順序が通信され、他のモードでは記号列が前置されるか埋め込まれることも可能である。これらのモードは任意の順序で生起し得、モードの切り替えは、1つの例では、切り替えの目的に使用される特殊記号によって指し示されてもよい。
【００４６】
更に他の可能な態様において、符号器および復号器は、既に受信された記号列から新しい記号列を構築する方法を用いることができる。この柔軟性のレベルにより、エンコーダが、記号列および通信モードを選択または変更して、圧縮を改善することが可能になる。例えば、それは、あらかじめ定義された記号列が全て使用されるわけではないケースであり得るが、このケースでは、EOG記号を繰り返すことにより多数の空の群を伝達することを避けるため、例えば、データ集合の終端、または、データの終端を効果的に意味するNo More Groupsを伝達する新しい記号列になり得る。
【００４７】
多くの状況において、副次的情報がデータ集合に付随してもよい。例えば、テキストの場合では、フォント、サイズ、重さ、色、および／またはスタイルが、そのような副次的情報を含んでもよい。これは任意の数の方途で通信または符号化されてもよい。例えば、副次的情報はランの長さと共に埋め込まれるか、符号化されたデータの任意の位置に挿入されてもよく、復号器は副次的情報を記号列に適切に関連づけてもよい。1つの態様において、記号列に組み合わせた副次的情報を記号列自体として取り扱い、このようにして追加の群を形成することが望ましい可能性がある。例えば、1つの単純な例として、イタリックの「e」は、正規の「e」とは別個の記号列を形成し得る。同様に、或る態様では、必要に応じて、特殊記号を用いて、異なる埋め込みスタイルまたはアプローチの間を切り替えてもよい。
【００４８】
本発明主題に従う態様は、全ての型のデータの符号化に適用され得る。それらのデータには、非数字データ、例えば、符号化の適用前に任意の便宜的マッピングによって数字形態に変換される記号データが含まれる。注意されるように、態様はランレングス符号化で良好な性能を示す。ただし、本発明主題は当然、この応用に限定されないことが理解される。本発明主題の態様は、多数の異なる型のデータ符号化の任意の1つに適用されることが意図される。従って、本発明主題は、これが適用されるデータの型の見地から限定されることが意図されない。
【００４９】
特定の態様が説明されたが、本発明主題は、特定の態様または実現に範囲を限定されないことが、当然理解される。例えば、1つの態様はハードウェアであってもよく、例えば、1つのデバイスまたはデバイスの組み合わせなどで動作するように実現され、他の態様はソフトウェアで実現されてもよい。同様に、態様は、ファームウェアで実現されるか、例えば、ハードウェア、ソフトウェア、および／またはファームウェアの任意の組み合わせとして実現されてもよい。同様に、本発明主題はこの点に関して範囲を限定されないが、1つの態様は一つまたは複数の物品、例えば、記憶メディアを含んでもよい。この記憶メディア、例えば、一つまたは複数のCD-ROMおよび／またはディスクは、これらに命令を記憶していてもよく、この命令は、システム、例えば、コンピュータシステム、コンピューティングプラットフォーム、または他のシステムによって実行される場合、本発明主題に従う方法の態様、例えば、先に説明された態様の1つが実行され得る。1つの潜在的な例として、コンピューティングプラットフォームは、一つまたは複数の処理ユニットまたはプロセッサ、一つまたは複数の入力／出力デバイス、例えば、ディスプレイ、キーボード、および／もしくはマウス、ならびに／または一つまたは複数のメモリ、例えば、スタティックランダムアクセスメモリ、ダイナミックランダムアクセスメモリ、フラッシュメモリ、および／もしくはハードドライブを含んでもよい。
【００５０】
先の説明では、本発明主題の様々な局面が説明された。解明を目的として、具体的な数、システム、および／または構成が記述され、本発明主題の徹底的理解を提供する。しかしながら、本発明主題は具体的細部を伴わずに実施され得ることが、この開示の恩典を有する当業者に明らかである。他の場合、周知の特徴は省略および／または単純化され、本発明主題を不明瞭にしないようにした。或る一定の特徴が本明細書において例示および／または説明されたが、多くの改変、置換、変更、および／または同等物が、当業者により行われると考えられる。従って、添付された特許請求の範囲は、本発明主題の真の精神に含まれる全ての改変および／または変更を包含するように意図されることが理解されるべきである。
【図１】
0005498783.tif 000009