(57)【要約】      （修正有）【課題】適応データ圧縮を実行するための方法および装置を提供する。【解決手段】未知の記号がエンコーダによりエンコードされるたびに、エンコーダは辞書に記号を加え、これをエンコードされたストリングで普通に伝送する。コードワードの前にある接頭語ビットの状態は、コードワードが、辞書に記憶される普通記号であるか、または記号もしくは記号のストリングのインデックスであるかを示す。コードワードが普通に記号を記憶する場合、デコーダは、先にデコードされた記号と現在デコードされた記号の第１の記号との連結により生じる一連の記号を加えることにより、かつ、この記号をその辞書に加えることにより、記号を学習する。コードワードがインデックスを記憶する場合、デコーダは、辞書において、それぞれのインデックスで、辞書に記憶される記号または一連の記号を抽出することにより、コードワードをデコードする。【選択図】図６
2008092582.tif 000002
【特許請求の範囲】
【請求項１】
入力ストリングを適応して圧縮するための方法であって、
記号のストリングを受け取り、入力ストリング中に含まれて受け取られた各記号を求めてエンコーダ辞書を探索するステップを備え、記号の幅は入力ストリングにおけるデータの種類に依存して選択され、
記号がエンコーダ辞書に記憶されていないことを検出すると、記号を次のシーケンシャルインデックスでエンコーダ辞書に記憶することにより記号を学習し、コードワードで記号をデコーダに伝送するステップを備え、コードワードは識別子を含み、識別子の状態は、コードワードが学習されるべき記号を含むことを示し、
記号がエンコーダ辞書に記憶されていることを検出すると、先に学習された記号がエンコーダ辞書に記憶されている単一のインデックスを、コードワードで伝送するステップを備え、識別子の状態は、コードワードが単一のインデックスを含むことを示し、
現在の記号の幅に基づく圧縮率がしきい値よりも小さいことを検出すると、記号の幅を修正し、新しい記号の幅をデコーダに連絡するステップを備える、方法。
【請求項２】
一連の記号が辞書に記憶されていないことを検出すると、一連の記号に対して一致する最長接頭語が辞書に記憶されているインデックスを伝送するステップをさらに備え、識別子の状態はコードワードがインデックスを含むことを示す、請求項１に記載の方法。
【請求項３】
インデックスは可変幅である、請求項１に記載の方法。
【請求項４】
インデックスの幅は、辞書に記憶されている複数の学習された項目に依存する、請求項３に記載の方法。
【請求項５】
探索するステップは、一連の記号を求めて探索し、学習するステップは、一連の記号を辞書に記憶することにより一連の記号を学習し、伝送するステップは、一連の記号に対する最長接頭語一致が記憶されているインデックスをコードワードで伝送する、請求項１に記載の方法。
【請求項６】
入力ストリングを適応して圧縮するための装置であって、
記号のストリング中に含まれて受け取られた各記号を記憶するためのエンコーダ辞書を備え、記号の幅は入力ストリングにおけるデータの種類に依存して選択され、
制御ロジックを備え、この制御ロジックは、各記号を求めて辞書を探索し、記号が辞書に記憶されていないことを検出すると、記号をコードワードでデコーダに伝送し、記号を次のシーケンシャルインデックスで辞書に記憶することにより記号を学習し、コードワードは識別子を含み、識別子の状態は、コードワードが学習されるべき記号を含むことを示し、記号がエンコーダ辞書に記憶されていることを検出すると、学習された記号がエンコーダ辞書に記憶されている単一のインデックスを、コードワードで伝送し、識別子の状態は、コードワードが単一のインデックスを含むことを示し、現在の記号の幅に基づく圧縮率がしきい値よりも小さいことを検出すると、記号の幅を修正し、新しい記号の幅をデコーダに連絡する、装置。
【請求項７】
制御ロジックは、一連の記号が辞書に記憶されていないことを検出すると、一連の記号の最長接頭語が記憶されているインデックスをコードワードで伝送する、請求項６に記載の装置。
【請求項８】
インデックスは可変幅である、請求項６に記載の装置。
【請求項９】
インデックスの幅は、辞書に記憶されている複数の学習された項目に依存する、請求項
８に記載の装置。
【請求項１０】
制御ロジックは、一連の記号を求めて辞書を探索し、一連の記号に対する最長接頭語一致が記憶されているインデックスをコードワードで伝送し、一連の記号を辞書に記憶することにより一連の記号を学習する、請求項６に記載の装置。
【請求項１１】
入力ストリングを適応して圧縮するための装置であって、
記号のストリング中に含まれて受け取られた各記号を記憶するためのエンコーダ辞書を備え、記号の幅は入力ストリングにおけるデータの種類に依存して選択され、
各記号を求めて辞書を探索するための手段と、
記号がエンコーダ辞書に記憶されていないことを検出すると、コードワードで記号をデコーダに伝送するための手段とを備え、コードワードは識別子を含み、識別子の状態は、コードワードが学習されるべき記号を含むことを示し、
記号を次のシーケンシャルインデックスで辞書に記憶することにより記号を学習するための手段と、
記号がエンコーダ辞書に記憶されていることを検出すると、記憶された記号がエンコーダ辞書に記憶されている単一のインデックスを、コードワードで伝送する手段とを備え、識別子の状態は、コードワードが単一のインデックスを含むことを示し、
現在の記号の幅に基づく圧縮率がしきい値よりも小さいことを検出すると、記号の幅を修正し、新しい記号の幅をデコーダに連絡する手段を備える、装置。
【請求項１２】
インデックスは可変幅である、請求項１１に記載の装置。
【請求項１３】
インデックスの幅は、辞書に記憶されている複数の学習された項目に依存する、請求項１２に記載の装置。
【請求項１４】
入力ストリングを適応して圧縮するための方法であって、
記号のストリング中に含まれて受け取られた一連の記号に対する最長接頭語一致を求めて辞書を探索するステップを備え、記号の幅は入力ストリングにおけるデータの種類に依存して選択され、
記号のストリングにおける記号がエンコーダ辞書に記憶されていないことを検出するとと、コードワードで記号を伝送し、コードワードは識別子を含み、識別子の状態は、コードワードが、学習されるべき普通記号であるかまたはインデックスであるかを識別し、記号を次のシーケンシャルインデックスでエンコーダ辞書に記憶することにより記号を学習するステップと、
一連の記号が辞書に記憶されていることを検出すると、一連の記号が辞書に記憶されているインデックスをコードワードで伝送するステップとを備え、インデックスの幅は、辞書に記憶されている複数の学習された項目に依存し、
記号がエンコーダ辞書に記憶されていることを検出すると、記憶された記号がエンコーダ辞書に記憶されている単一のインデックスを、コードワードで伝送するステップを備え、識別子の状態は、コードワードが単一のインデックスを含むことを示し、
現在の記号の幅に基づく圧縮率がしきい値よりも小さいことを検出すると、記号の幅を修正し、新しい記号の幅をデコーダに連絡するステップを含む、方法。
【請求項１５】
一連のコードワードを復号するための方法であって、
コードワードを受取るステップを備え、コードワードは識別子を含み、コードワードの幅は、入力ストリングにおけるデータの種類に依存して選択される記号の幅に依存し、
識別子の状態から、コードワードに記号が記憶されていることを検出すると、記号を次のシーケンシャルインデックスでデコーダ辞書に記憶することにより記号を学習するステップと、
デコードされたデータとして記号を与えるステップとを備える、方法。
【請求項１６】
学習するステップはさらに、
先に学習された記号を記号と連結することにより一連の記号を学習するステップと、
一連の記号を次のシーケンシャルインデックスでデコーダ辞書に記憶するステップとを備える、請求項１５に記載の方法。
【請求項１７】
コードワードに記憶されている辞書インデックスを検出すると、インデックスを変換するステップをさらに含む、請求項１５に記載の方法。
【請求項１８】
インデックスを記号へ変換する、請求項１７に記載の方法。
【請求項１９】
インデックスは可変幅である、請求項１７に記載の方法。
【請求項２０】
一連のコードワードを復号するための装置であって、
コードワード中に含まれて受け取られた普通記号を次のシーケンシャルインデックスで記憶するための辞書を備え、コードワードは識別子を含み、識別子の状態は、コードワードが学習されるべき記号を含むことを示し、
ロジックを備え、このロジックは、コードワードを受取り、コードワードに記憶されている普通記号を検出し、記号を辞書に記憶し、デコードされたデータとして記号を与え、記号がエンコーダ辞書に記憶されていることを検出すると、記憶された記号がエンコーダ辞書およびデコーダ辞書の両方に記憶されている単一のインデックスを、コードワードで伝送し、識別子の状態は、コードワードが単一のインデックスを含むことを示し、現在の記号の幅に基づく圧縮率がしきい値よりも小さいことを検出すると、記号の幅を修正し、新しい記号の幅をデコーダに連絡する、装置。
【請求項２１】
ロジックは、先に学習された記号を、コードワードに記憶されている普通記号と連結することにより一連の記号を学習し、一連の記号を次のシーケンシャルインデックスで辞書に記憶する、請求項２０に記載の装置。
【請求項２２】
コードワードに記憶されているインデックスを検出すると、ロジックはインデックスを変換する、請求項２０に記載の装置。
【請求項２３】
インデックスを記号へ変換する、請求項２２に記載の装置。
【請求項２４】
インデックスを一連の記号へ変換する、請求項２２に記載の装置。
【請求項２５】
インデックスは可変幅である、請求項２０に記載の装置。
【発明の詳細な説明】
【背景技術】
【０００１】
発明の背景
データ圧縮は、所与の情報を表わすのに必要なデータの量を減らすプロセスを指す。削減プロセスの根本的原則は、冗長または不必要なデータの除去である。データ圧縮技術は、情報記憶および伝送のための費用を削減する。データ圧縮技術は、簡単なファイルサイズの削減から音声および映像のエンコードの範囲にわたる多くの応用例において用いられる。
【０００２】
圧縮には、無損失なものと損失のあるものとの２つの異なる種類がある。無損失の圧縮では、エンコーダ入力でのソースメッセージは、デコーダの出力で正確に検索される。損失のある圧縮では、メッセージは正確には検索されないが、情報損失は、圧縮方式により対象とされるアプリケーションの種類にとっては許容できるものである。損失のある圧縮は、主に、音声、音響、画像および映像信号のために用いられる。圧縮アルゴリズムの目的は、信号了解度および知覚品質を維持しつつ、最低限のビット数で信号を表わすことである。人の感知によって知覚できないすべての情報を除去することができる。
【０００３】
無損失圧縮技術は、実行可能なソースコードファイルの圧縮、衛星画像化および医療用画像化等の、情報損失が許容されない応用例において用いられる。この技術はまた、損失のある圧縮方式の一部として、より高い圧縮率を得るために用いられる。
【０００４】
無損失圧縮を行なうための１つ周知の技術は、ＬＺＷ（Lempel-Ziv-Welch）（「ＬＺＷ」）アルゴリズムである。ＬＺＷアルゴリズムは、一定の規則に従ったストリング構文解析に基づく汎用アルゴリズムである。これは、よく用いられるシーケンスが、シーケンス全体を１文字ずつ綴るのに必要とされるよりも少ないビット数でエンコードされ得るという概念に基づく。ＬＺＷアルゴリズムは、ソースのアルファベットを含むテーブルの初期設定を必要とする。記号幅が選択され、ソースアルファベットが、記号のために作成され、エンコードプロセスの開始前にエンコーダおよびデコーダにおけるコーディングテーブルに記憶されている。ＬＺＷアルゴリズムは、受取られた一連の記号をエンコードするとき、選択された一連の記号（語彙）を辞書に加える。辞書に含まれるシーケンスは、記号を含むシーケンス全体を１文字ずつ綴るのに必要とされるより少ないビット数でエンコードされ得る。ソースアルファベットのサイズは記号の幅に依存する。たとえば、１バイト（８ビット）の記号幅は２８（２５６）項目のソースアルファベットを必要とし、２バイト（１６ビット）の記号幅は２１６（６４Ｋ）項目のソースアルファベットを必要とする。典型的には、ＬＺＷアルゴリズムは、１バイト（８ビット）の記号幅で実現される。ＬＺＷアルゴリズムは、受取られた一連の記号における最長一致を求めてコーディングテーブルを探索し、辞書に記憶されている最長一致のインデックスを伝送する。
【０００５】
図１には、無損失データ圧縮を実行するための、エンコーダおよびデコーダにおける先行技術のＬＺＷコーディングテーブル１００が示される。ＬＺＷコーディングテーブル１００は、３進連想記憶装置（Contents Addressable Memory）（「ＣＡＭ」）であり得る。記号の入力シーケンス１０２は、ＬＺＷコーディングテーブル１００に記憶されているソースアルファベット１０６および辞書１０８を用いて、エンコーダにより、一連のインデックスに変換される。エンコーダ１１０におけるコーディングテーブル１００、およびデコーダ１１２におけるデコーディングテーブル１２０は、ソースアルファベット１０６および辞書１０８を含む。一連のインデックス１１４は、エンコーダ１１０によって伝送され、デコーダ１１２によってデコードされる。デコーダ１１２は、出力ストリング１０４に、記号の入力シーケンス１０２と同じ記号を与える。エンコーダ１１０が記号の入力
シーケンス１０２をエンコードし始める前に、ソースアルファベット１０６は、エンコーダ１１０およびデコーダ１１２におけるＬＺＷコーディングテーブル１００に記憶されている。エンコーダ１１０からデコーダ１１２に伝送される一連のインデックス１１４は、ソースアルファベット１０６に記憶されている普通テキスト記号のインデックスか、または辞書１０８に記憶されている記号のストリングのインデックスである。エンコーダ１１０およびデコーダ１１２は、独立して、最初のソースアルファベットに応じて新しい一連の記号を学習することにより、それぞれの辞書に項目を作成する。エンコーダ１１０は、辞書に新しい一連の記号を加えるが、先に学習された記号のインデックス、または一連の記号を、一連のインデックス１１４でデコーダ１１２に伝送する。デコーダはまた、新しい一連の記号を学習し、ＬＺＷデコーディングテーブル１２０における新しいインデックスで新しい一連の記号を辞書１０８に記憶する。
【０００６】
図２には、図１に示されるエンコーダ１１０における入力ストリングの先行技術のＬＺＷ圧縮が示される。ソースアルファベット１０６（図１）は、エンコーダ１１０（図１）が記号の入力シーケンス１０２を構文解析し始める前に、またはデコーダがデコードし始める前に、ＬＺＷコーディングテーブル１００（図１）に記憶されている。８ビット記号のためのソースアルファベット１０６（図１）は、インデックス０〜２５５で、コーディングテーブル１００（図１）およびデコーディングテーブル１２０（図１）に記憶されている。ソースアルファベット１０６（図１）における２５６の位置のうち５つの内容が示される。記号「／」はインデックス４７で記憶され、記号「ｂ」はインデックス９８で記憶され、記号「ｄ」はインデックス１００で記憶され、記号「ｅ」はインデックス１０１で記憶され、記号「ｔ」はインデックス１１６で記憶され、記号「ｗ」はインデックス１１９で記憶されている。ＬＺＷコーディングテーブル１００のソースアルファベット１０６におけるインデックス２５６での追加項目２５６は、ストリングの終わり（End Of String）（「ＥＯＳ」）を記憶し、ＬＺＷコーディングテーブル１００の辞書１０８におけるインデックス２５７での項目２５７は、フラッシュコードを記憶する。
【０００７】
記号の入力シーケンス１０２は、エンコーダ１１０（図１）によって受取られる。エンコーダ１１０（図１）は、記号の入力シーケンス１０２を構文解析し、一連のインデックス１１４（図１）を伝送する。記号の入力シーケンス１０２は、記号の入力シーケンス１０２を構文解析し、かつ記号に対する最長一致を求めてＬＺＷコーディングテーブル１００を探索することにより、エンコーダ１１０（図１）によってエンコードされ、ＬＺＷコーディングテーブル１００における項目のために一連のインデックス（コードワード）として伝送される。インデックスは、ソースアルファベット１０６または辞書１０８における項目へのポインタであってもよい。
【０００８】
ＬＺＷコーディングテーブル１００に示されるように、ソースアルファベット１０６における項目に対する、記号「／」を記憶するインデックスは４７である。初めに、コーディングテーブル１００はソースアルファベット１０６だけを記憶する。エンコーダ１１０（図１）は、一連の記号１０２を受取ると、一連の記号１０２を、記号幅に応じて構文解析する。エンコーダ１１０（図１）は、一連の記号１０２（図１）において記号を選択し、この記号を求めてＬＺＷコーディングテーブル１００を探索する。エンコーダは、既知の記号および一連の記号を連結することにより、語彙を学習する。記号が見つかった場合、この記号は次の記号と連結され、２つの記号により形成される一連の記号を求めてＬＺＷコーディングテーブル１００が探索される。一連の記号がＬＺＷコーディングテーブル１００に記憶されていない場合、先に識別された記号または一連の記号のインデックスが伝送され、新しい一連の記号がＬＺＷコーディングテーブル１００に加えられる。
【０００９】
ＬＺＷアルゴリズムを用いるエンコーダの動作が、記号の入力シーケンス１０２を用いて示される。これはすなわち、図２に示されるように、/wed/we/wee/web/wet/であり、か
つ１文字（８ビット）の記号幅である。コーディングテーブル１００は、「／」、「ｗ」、「ｅ」、「ｄ」、「ｂ」、および「ｔ」を含む各８ビット記号に対する項目を含む最初のアルファベットを記憶する。
【００１０】
記号の入力シーケンス１０２の構文解析は、記号「／」から始まる。記号「／」は、インデックス４７でＬＺＷコーディングテーブル１００に記憶され、「／」は次の記号「ｗ」と連結され、コーディングテーブルが一連の記号「/w」を求めて探索される。「/w」は、そのときにＬＺＷコーディングテーブル１００に記憶されていないので、次のシーケンシャルインデックス２５８で「/w」を記憶することにより学習される。先に識別された記号である「／」に対するインデックス、すなわち４７が一連のインデックス１０４において伝送される。
【００１１】
構文解析が、記号の入力シーケンス１０２における記号「ｗ」で再開する。ＬＺＷコーディングテーブル１００が、記号「ｗ」を求めて探索される。記号「ｗ」は、インデックス１１９でＬＺＷコーディングテーブル１００に記憶され、記号「ｗ」は記号の入力シーケンス１０２における次の記号「ｅ」と連結され、コーディングテーブルは一連の記号「we」を求めて探索される。「we」は、そのときにコーディングテーブル１００に記憶されていないので、次のシーケンシャルインデックス２５９でコーディングテーブルに「we」を記憶することにより学習される。先に識別された記号である「ｗ」に対するインデックス、すなわち１１９が一連のインデックス１０４において伝送される。
【００１２】
構文解析が、記号の入力シーケンス１０２における記号「ｅ」で再開する。記号「ｅ」は、インデックス１０１でＬＺＷコーディングテーブル１００に記憶されている。記号「ｅ」は記号の入力シーケンスにおける次の記号「ｄ」と連結され、ＬＺＷコーディングテーブル１００は一連の記号「ed」を求めて探索される。「ed」は、ＬＺＷコーディングテーブル１００に記憶されていないので、インデックス２６０で、次のシーケンシャル項目における「ed」をコーディングテーブルに記憶することにより学習される。先に識別された記号である「ｅ」に対するインデックス、すなわち１０１が一連のインデックス１０４において伝送される。
【００１３】
構文解析が、記号の入力シーケンス１０２における記号「ｄ」で再開する。記号「ｄ」は、インデックス１００でコーディングテーブル１００に記憶されている。記号「ｄ」は記号の入力シーケンス１０２における次の記号「／」と連結され、ＬＺＷコーディングテーブル１００が、一連の記号「d/」を求めて探索される。「d/」は、ＬＺＷコーディングテーブル１００に記憶されていないので、インデックス２６１で、次のシーケンシャル項目における「d/」をコーディングテーブルに記憶することにより学習される。先に識別された記号、「ｄ」に対するインデックス、すなわち１００が一連のインデックス１０４において伝送される。
【００１４】
構文解析が、記号の入力シーケンス１０２における記号「／」から再開する。記号「／」は、インデックス４７でＬＺＷコーディングテーブル１００に記憶されている。記号「／」は記号の入力シーケンス１０２における次の記号「ｗ」と連結され、ＬＺＷコーディングテーブル１００は一連の記号「/w」を求めて探索される。「/w」は、インデックス２５８でコーディングテーブル１００に記憶され、記号の入力シーケンス１０２における「ｅ」と連結され、コーディングテーブルが一連の記号「/we」を求めて探索される。「/we」は、コーディングテーブル１００に記憶されていないので、インデックス２６２で、次のシーケンシャル項目における「/we」をＬＺＷコーディングテーブルに記憶することにより学習される。先に識別された一連の記号「/w」に対するインデックス、すなわち２５８が一連のインデックス１０４において伝送される。
【００１５】
たとえば、８ビットの記号幅については、文字「/we」の１バイトストリングにつき２
４ビット（３バイト×８ビット）に対する一致を見つけると、９ビットインデックス（辞書に記憶されている記号のストリング「/we」のアドレス）が、エンコーダからデコーダに伝送される。これにより、伝送されるビットの数が２４から９に減じられる。９ビットインデックスを受取ると、デコーダは、９ビットインデックスで辞書のそのコピーに記憶されている文字のストリング「/we」を再生成する。対応するシーケンス（接頭語）が辞書に見つからなかった場合、個々の記号、「／」、「ｗ」および「ｅ」に対するインデックスが伝送されるだろう。
【００１６】
２０個の記号の入力シーケンス１０２の伝送には、１６０ビット（１記号につき２０記号×８ビット）必要である。ＬＺＷアルゴリズムは、伝送されるビットの数を１２６ビット（１４インデックス×９ビット）に減ずる。記号の入力シーケンス１０２が構文解析されると、コーディングテーブル１００における辞書１０８に記憶されている語彙が増し、コーディングテーブルに記憶されている一連の記号が長くなる。たとえば、インデックス２６４は一連の４つの記号「/wee」を表わす。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
コーディングテーブルに記憶されている一連の記号が長ければ長いほど、より良好な圧縮が得られる。というのも、伝送されるインデックスの数が減るからである。圧縮は、記号幅を増すことによっても改善され得る。しかしながら、ＬＺＷアルゴリズムで必要とされる最初のソースアルファベットは、記号幅に加えられる各ビットに対して２だけ増え、したがって、複数のバイトの記号幅に対して、最初のソースアルファベットをエンコードするために非実用的なテーブルサイズを必要としてしまう。
【課題を解決するための手段】
【００１８】
発明の概要
この発明は、辞書におけるソースアルファベットの初期設定を必要としない。代わりに、アルファベットおよび語彙がともに、記号の入力ストリングのエンコード中に、学習され、かつ辞書に記憶される。
【００１９】
さらに、先行技術のＬＺＷでは、大きなアルファベットは大きな記号幅インデックスを必要とする。１バイト記号で２５６通りのアルファベットでは、インデックスが９ビットから始まる必要があり、２バイト記号で１６３８４通りのアルファベットは１７ビットの初期インデックスを必要とする。インデックスの幅は、圧縮率に直接影響を及ぼす。この発明においては、アルファベットのサイズは、インデックス幅に直接影響を及ぼさない。さらに、ソースによって用いられる記号だけが、辞書に学習される。このように、この発明は、ソースが乏しい場合に好適である。
【００２０】
辞書が、記号のストリングにおいて受取られた記号または一連の記号を求めて探索される。記号が辞書に記憶されていないことを検出すると、この記号は、辞書に記憶することにより学習され、普通記号がコードワードで伝送される。
【００２１】
記号または一連の記号が辞書に記憶されていることを検出すると、記号または一連の記号が辞書に記憶されているインデックスがコードワードで伝送される。コードワードにおける接頭語フィールドの状態は、コードワードの内容を、学習されるべき普通記号またはインデックスのいずれかとして識別し得る。辞書のインデックスは、学習された記号および一連の記号の数に応じた可変幅であり得る。
【発明の効果】
【００２２】
記号幅はデータの種類に応じて選択され得る。たとえば、テキストの伝送については、単一バイトは個々の文字を容易に規定することができる。しかしながら、オーディオまたは映像データについては、データのストリームが構文解析されるより長い記号幅によって、より良好に圧縮され得る。すべての記号は、最初に記憶されず、それらが発生したときに辞書に記憶されるだけなので、初めにメモリをオーバーロードするおそれなしに、広い記号幅を用いることができる。
【００２３】
この発明の上述および他の目的、特徴および利点は、同様の参照符号が異なる図を通じて同じ部分を指す添付の図面に示されるように、この発明の好ましい実施例のより詳細な以下の記載から明らかとなるであろう。図面は変倍する必要がなく、代わりに、この発明の原理を例示することにより強調される。
【発明を実施するための最良の形態】
【００２４】
発明の詳細な説明
この発明の好ましい実施例の説明は以下のとおりである。
【００２５】
図３には、この発明の原理に従って無損失圧縮を行なうための、コーディングテーブル３００を含むエンコーダ３１０およびデコーディングテーブル３２０を含むデコーダ３１２が示される。最初のソースアルファベットを辞書３０８に記憶せずに、エンコーダ３１０がエンコードし始め、デコーダ３１２がデコードし始める。アルファベットは、エンコーダが記号の入力ストリング３０２を構文解析する間に学習される。記号は、入力ストリング３０２が構文解析される単位である。記号は任意の幅、たとえば複数の文字であり得る。エンコーダによって出力される各コードワードは、１ビットだけ接頭語を付されて、デコーダ３１２がアルファベットを学習することを可能にする。記号がエンコーダ３１０により学習されると、エンコーダ３１０は「０」にセットされたビットが前にあるコードワードで、普通に記号を伝送する。記号が既知の場合、エンコーダ３１０は、「１」にセットされたビットが前にあるインデックスを伝送する。メモリサイズによって制限されるおそれのある初期テーブルがないので、記号の幅に制限はない。アルファベットは動的に学習される。コードワードをデコードするために、デコーダ３１２は、最初に、データの種類を示すビットを識別する。ビット値が「０」である場合、デコーダ３１２は記号を直接出力する。ビット値が「１」である場合、辞書を用いてインデックスを変換する。
【００２６】
普通記号がデコーダ３１２に伝送されるたびに、デコーダ３１２はその辞書３０８に記号を加える。したがって、ソースアルファベット全体が記憶されている必要はない。代わりに、デコーダが受取る記号のみが、辞書３０８に記憶される。
【００２７】
エンコーダ３１０は、入力ストリング３０２を取得し、コーディングテーブル３００における辞書３０８に記憶されている記号および一連の記号を用いて入力ストリングを圧縮し、エンコードされたストリング３１４を伝送する。一実施例では、エンコードされたストリング３１４は、データパケットでネットワーク全体に伝送され、受信ノードにおいてデコーダでデコードされ得る。代替の実施例では、エンコードされたデータは記憶装置に伝送され得る。
【００２８】
先行技術のＬＺＷアルゴリズムとは違って、記号のためのソースアルファベットは、エンコーダ３１０が入力ストリング３０２を構文解析し始める前には、コーディングテーブル３００には記憶されていない。代わりに、エンコーダ３１０は、入力ストリング３０２を構文解析すると、ソースアルファベットおよび語彙を学習する。エンコーダ３１０は、デコーダがソースアルファベットを学習できるように、普通に、エンコードされたストリング３１４上で、新しく学習された記号を送る。
【００２９】
エンコーダ３１０により受取られた記号のストリング３０２をエンコードして、冗長または不必要なデータを除去する。エンコーダ３１０は、選択された記号幅、およびコーディングテーブル３００に記憶されている辞書３０８に応じて、記号のストリングをエンコードする。エンコードされたストリング３１４はデコーダ３１２に伝送される。エンコードされたストリング３１４は一連のコードワードである。各コードワードは、辞書３０８に記憶されている記号、または記号もしくは記号シーケンスに対するインデックスを含む。
【００３０】
デコーダ３１２は、エンコードされたストリング３１４で伝送され、エンコーダ３１０から受取られるアルファベットおよび語彙を学習し、これらをデコーディングテーブル３２０における辞書３０８に記憶する。デコーダ３１２は、デコーディングテーブル３２０における辞書３０８で学習されるソースアルファベットおよび語彙に応じて、受取られたエンコードされたストリング３１４をデコードして、もともとの記号のストリングを与える。
【００３１】
一実施例では、エンコーダ３１０におけるコーディングテーブル３００およびデコーダ３１２におけるデコーディングテーブル３２０は、２進または３進連想記憶装置（「ＣＡＭ」）で実現される。ＣＡＭは探索および学習機能を有する。探索および学習機能により、ＣＡＭは、探索キーがＣＡＭにおいて見つからない場合探索キーを学習することができる。探索キーがＣＡＭにおける項目に記憶されている場合、ＣＡＭは探索キーに対する一致アドレスを戻す。探索キーがＣＡＭにおける項目に記憶されていない場合、ＣＡＭは、ＣＡＭ項目に新しい探索キーを記憶することにより、新しい探索キーを学習する。
【００３２】
コーディングテーブル３００およびデコーディングテーブル３２０は、２つの項目、すなわち、ストリングの終わり（「ＥＯＳ」）３１６およびフラッシュコード３１８で初期設定される。フラッシュコード３１８のインデックスが伝送されて、コーディングテーブル３００がいっぱいであることを示す。コーディングテーブル３００がいっぱいであるとき、ＥＯＳおよびフラッシュコードを除く項目がすべてクリアされ、記号のストリングが受取られると記号および語彙が再び学習される。フラッシュコードがデコーダに伝送され、これにより、デコーダ３１２はそのデコーディングテーブル３２０を初期設定し得る。コーディングテーブル３００の初期設定は、図６に関連して後に記載される。ＥＯＳ項目のインデックスは、エンコードプロセスの終わりに伝送される。
【００３３】
最初のソースアルファベットが不要であるので、記号の幅は、最初のソースアルファベットを記憶するのに必要とされるメモリによってもはや制限されない。さらに、初期インデックス幅は、ソースのアルファベットサイズによってもはや影響を受けない。エンコードされたストリング３１４上で記号を伝送するので、エンコードプロセス中に記号の幅を修正することができ、これにより、デコーダ３１２が新しいアルファベットを学習することが可能となる。圧縮率を上げるために、エンコードプロセス中に圧縮率を監視し、記号幅を適切に修正することができる。たとえば、インターネットを通じてユーザにより要求されるデータの種類が変わると、圧縮されるべきデータの種類は変わり得る。たとえば、要求されるデータの種類は、オーディオファイルから画像ファイルへ、次いでテキストファイルへと変わり得る。伝送されるデータの種類が変わると記号幅を修正する能力を備えることにより、特定の種類の受取られた記号のストリングに対して最適な記号幅を選択し得る。同様に、大きなメモリが記号のために最初のソースアルファベットを記憶する必要なしに、画像における４×４画素ブロック（１６バイト）等の大きな記号を圧縮し得る。
【００３４】
最大の記号幅は、コーディングテーブル３００およびデコーディングテーブル３２０の物理的な幅に依存する。たとえば、７バイト（５６ビット）の記号は７２ビット幅のＣＡＭに記憶され得る。７２ビット幅のＣＡＭは５６ビット（７バイト）を与えて、別のＣＡ
Ｍ項目へのインデックスを記憶するために記号および１４個のビットを記憶する。１４４ビットのＣＡＭはより幅の広い記号を記憶することができる。エンコーダ３１０からエンコードされたストリング３１４としてデコーダ３１２に伝送されるコードワードのフォーマットが、図４Ａ〜図４Ｂに関して記載される。
【００３５】
代替的な実施例では、エンコーダ３１０およびデコーダ３１２は、メモリに記憶され、かつプロセッサによって実行される命令として実現され得る。
【００３６】
図４Ａには、図３に示されるエンコーダ３１０により学習される普通記号を伝送するために、エンコーダ３１０により、エンコードされたストリング３１４上で伝送されるコードワードが示される。エンコーダ３１０（図３）が、普通記号をコーディングテーブル３００（図３）に記憶することにより新しい記号を学習すると、エンコーダ３１０（図３）は、エンコードされたストリング３１４（図３）として、普通に、記号をデコーダ３１２（図３）に伝送する。記号は普通に伝送され、普通記号フィールド４０６に記憶される。普通記号フィールド４０６の前には接頭語ビット４０４がある。接頭語ビット４０４は「０」にセットされて、普通記号が後に続くことを示す。たとえば、記号幅が２バイトであり、学習されるべき記号が「/w」である場合、「/w」は普通記号フィールド４０６に記憶され、「０」は接頭語ビット４０４に記憶される。
【００３７】
図４Ｂには、既知であり、かつ図３に示されるコーディングテーブル３００に記憶されている記号または一連の記号のための、エンコードされたストリング３１４（図３）の上で伝送されるコードワードが示される。コードワードには、接頭語ビット４０４が前にあるテーブルインデックスフィールド４０８が含まれる。テーブルインデックスは、「１」にセットされた接頭語ビット４０４が前にあるテーブルインデックスフィールド４０８に記憶される。テーブルインデックスフィールド４０８は、コーディングテーブル３００およびデコーディングテーブル３２０に記号または一連の記号を記憶する項目のインデックスを記憶する。
【００３８】
テーブルインデックスフィールド４０８の幅は、コーディングテーブル３００およびデコーディングテーブル３２０に記憶されている項目の数に応じて可変である。たとえば、コーディングテーブル３００およびデコーディングテーブル３２０に記憶されている４未満の項目がある場合、テーブルインデックスフィールド４０８は２ビット幅である。コーディングテーブル３００およびデコーディングテーブル３２０に記憶されている１２８から２５５の項目がある場合、テーブルインデックスフィールド４０８は８ビット幅である。
【００３９】
図５には、入力ストリング５０２をエンコードされたストリング３１４（図３）にエンコードするための、制御ロジック５００と、図３に示されるエンコーダ３１０におけるコーディングテーブル３００とが示される。制御ロジック５００は入力ストリング５０２を構文解析して、エンコードされたストリング３１４（図３）を与える。制御ロジックにより伝送されるエンコードされたストリング３１４（図３）は、コードワードを含む。このコードワードは、「０」にセットされた接頭語ビット４０４（図４Ａ）が前にある普通記号フィールド４０６（図４Ａ）に記憶されている普通記号、または「１」にセットされた接頭語ビット４０４（図４Ｂ）が前にあるテーブルインデックスフィールド４０８（図４Ｂ）に記憶されているテーブルインデックスを含む。
【００４０】
入力ストリング５０２は複数の記号を含む。記号の幅は可変であり、単一の文字もしくはバイト（８ビット）または複数のバイトであり得る。記号の幅は、入力ストリング５０２におけるデータの種類に応じて動的に修正され得る。たとえば、テキストファイルが処理されている場合、記号幅は文字幅（８ビット）となるよう選択され得る。画像ファイル
が処理されている場合、記号幅は１６バイトであり得る。制御ロジック５００は、選択された記号幅に応じて入力ストリング５０２を構文解析する。
【００４１】
記号幅は動的に変更され得る。エンコーダ３１０（図３）をセットして、圧縮率（ビットの入力数／ビットの出力数）を監視することができ、この圧縮率が低かったり突然下がったりする場合、制御ロジック５００（図５）で実現される圧縮アルゴリズムは、自動的に、異なる記号幅を試み、最良の圧縮率をもたらす幅を選択し得る。いくつかのしきい値をセットする必要がある。たとえば、どの圧縮率で幅を変更するか、どの幅を最初に試みるかである。記号幅変更、およびエンコーダ３１０（図３）とデコーダ３１２（図３）との間で一致した取決めに対してコードを予約するので、デコーダ３１２（図３）は新しい記号幅を認識するだろう。
【００４２】
さらに、エンコーダ３１０（図３）は、記号幅を変更するたびに、新しい記号幅が後に続く（辞書におけるストリングによって用いられない）特別な予約コードを送る。
【００４３】
記号幅変更を実現するための１つの方法は、コーディングテーブル３００（図５）全体をフラッシュし、新しい幅の記号の学習を再開することである。この方法では、新しい記号幅が直ちに高い圧縮率をもたらす場合、効率的である得るが、新しい幅が入力ストリング５０２（図５）におけるデータの種類に適さない場合、不利な状態に置かれるおそれがある。
【００４４】
用いることのできる別の方法は、辞書３０８（図３）の一部をフラッシュすることである。たとえば、新しい記号幅の倍数ではないすべてのストリングが除去される。これは中間解である。というのも、新しい記号幅が、辞書３０８（図３）におけるいくつかの学習されたストリングから始まるからである。
【００４５】
制御ロジック５００には、ストリングレジスタ５１２、入力ストリングポインタ５１４、インデックス精度レジスタ５１６、現在のストリングの長さレジスタ５１８、項目の数レジスタ５２０、および、最後に加えられた長さレジスタ５２２が含まれる。制御ロジック５００は、ストリングレジスタ５１２および入力ストリングポインタ５１４を用いて、入力ストリング５０２およびインデックス精度レジスタ５１６を構文解析し、エンコードされたストリング３１４（図３）上で伝送されるコードワードにおけるテーブルインデックスフィールド４０８（図４Ｂ）で伝送するビットの数を常に把握するようにする。ストリングレジスタ５１２（図５）は探索キーを記憶するために用いられ、入力ストリングポインタ５１４（図５）は、制御ロジック５００（図５）により現在処理されている入力ストリング５０２（図５）における記号に対するポインタを記憶するために用いられる。
【００４６】
項目の数レジスタ５２０は、記号または一連の記号が辞書３０８（図３）に加えられるたびに増分される。項目の数レジスタ５２０の内容をエンコーダ３１０（図３）により監視して、辞書３０８（図３）がいっぱいであるかどうかを判断する。辞書３０８がいっぱいであると判断すると、エンコーダ３１０（図３）はその辞書３０８（図３）をフラッシュし、フラッシュコードをデコーダ３１２（図３）に送り、このため、デコーダ３１２（図３）もまた、その辞書３０８（図３）をフラッシュすることができる。
【００４７】
最後に加えられた長さレジスタ５２２の内容を用いて、辞書３０８に最後に加えられたストリングの長さを常に把握する。レジスタが「１」にセットされる場合、記号は辞書３０８に最後に加えられた。現在のストリングの長さレジスタ５１８の内容は、入力ストリング５０２から抽出される、探索キーとして現在用いられている記号の数である。
【００４８】
コーディングテーブル３００における辞書３０８は、２つの項目、すなわち、インデッ
クス「０」ではＥＯＳおよびインデックス「１」ではフラッシュコード、ならびにインデックス「３」では記号幅変更で初期設定されて、動的な幅の変更が必要とされる場合これを可能とする。ＥＯＳおよびフラッシュコードは、図３に関連して既に記載されている。制御ロジック５００は、入力ストリング５０２における第１の記号を選択し、命令バス５０６上で「探索および学習」命令とともに、記号を探索キー５０４としてコーディングテーブル３００に送る。コーディングテーブル３００は、コーディング３００における辞書３０８の項目に記憶されている探索キー５０４を求めて探索する。
【００４９】
第１の記号が辞書３０８に記憶されていない場合、コーディングテーブル３００は、それが、辞書３０８に探索キー５０４を記憶することにより探索キー５０４を学習していることを、学習５０８を介して示す。制御ロジック５００は学習５０８を監視し、コーディングテーブル３００が探索キー５０４を学習していることを検出すると、制御ロジック５００は、普通記号フィールド４０６（図４Ａ）における普通記号としてコードワードで記号を送る。普通記号フィールド４０６の前には、図４Ａに関連して先に記載されたように、「０」にセットされた接頭語ビット４０４（図４Ａ）がある。デコーダ３１２（図３）は、「０」にセットされた接頭語ビット４０４（図４Ａ）を検出し、デコーディングテーブル３２０（図３）に対する次のシーケンシャルインデックスにおいて、普通記号フィールド４０６に記憶されている普通記号を辞書３０８（図３）に記憶することにより、記号を学習する。コーディングテーブル３００が探索キー５０４に対する一致を見つける場合、一致インデックス５１０は制御ロジック５００に送られる。探索キー５０４に対して一致を見つける場合、エンコーダ３１０は、辞書３０８に記憶されたより長く一致する一連の記号を求めて、辞書３０８を探索する。制御ロジック５００は、入力ストリング５０２における現在の記号と次の記号とを連結して、次の探索キー５０４を与える。探索キーは、見つからない場合、コーディングテーブル３００に一連の記号（現在の記号、次の記号）を記憶することにより学習される。
【００５０】
これにより、一連の記号の学習が可能となる。これは、アルファベットの文字を組合せることによって言語の語彙を学習することに似ている。最長接頭語一致に対する一致インデックス５１０は、エンコードされたストリング３１４（図３）上で送られ、テーブルインデックスフィールド４０８（図４Ｂ）に記憶される。テーブルインデックスフィールド４０８の前には、「１」にセットされた接頭語ビット４０４（図４Ｂ）がある。一連の記号を学習するための方法が、図９に関連して後に記載される。
【００５１】
制御ロジック５００（図５）は、選択された記号の幅に応じて入力ストリング５０２を構文解析する。最初に、コーディングテーブル３００（図５）は３つの項目、すなわち、ＥＯＳ、フラッシュコードおよび随意には記号幅変更コードを記憶する。制御ロジック５００（図５）は入力ストリングにおける次の記号を選択し、記号を求めてコーディングテーブル３００（図５）を探索する。記号が見つかった場合、制御ロジック５００（図５）は、この記号を入力ストリング５０２（図５）における次の記号と連結する。制御ロジック５００（図５）は、コーディングテーブル３００に現在記憶されていない一連の記号を見つけるまで、入力ストリングにおける記号を連結し続ける。制御ロジック５００（図５）は、「１」にセットされた接頭語ビットが前に付された一連の記号と一致する最長接頭語のインデックスを送る。
【００５２】
記号がコーディングテーブル３００（図５）に記憶されていない場合、制御ロジック５００（図５）は「０」が頭に付された記号のために普通記号を送り、このため、デコーダ３１２（図５）はこの記号を学習することができる。
【００５３】
記号および一連の記号がコーディングテーブル３００（図５）に記憶されると、制御ロジック５００（図５）は項目の数を監視する。項目の数が２の累乗の境界を超えるたびに
、制御ロジック５００（図５）はインデックス幅を増分する。制御ロジック５００（図５）はまた、コーディングテーブル３００（図５）において用いられる項目の数を監視して、コーディングテーブル３００（図５）がいっぱいであるかどうかを判断する。コーディングテーブル３００（図５）がいっぱいであることを検出すると、制御ロジック５００（図５）は、記号および一連の記号を記憶する項目のすべてをクリアすることにより、コーディングテーブル３００（図５）を初期設定し、デコーダ３１２（図３）にフラッシュコードを伝送し、このため、デコーダ３１２（図３）はそのデコーディングテーブル３２０（図３）を初期設定することができる。
【００５４】
代わりに、制御ロジック５００（図５）は、圧縮率を監視し、圧縮が効率的である場合、コーディングテーブル３００（図５）を初期設定しないよう決定することができる。圧縮率を監視するための方法は、全体が引用によりこの明細書中に援用される、クエイサ（K. Quaissa）、アブダト（M. Abdat）およびプルメ（P. Plume）による、「ＬＺＷデータ圧縮における辞書サイズの適応制限」（“Adaptive Limitation of the Dictionary Size
in LZW Data Compression”）（情報理論とその応用シンポジウム（IEEE International
Symposium on Information Theory（ISIT'95））、１９９５年９月、カナダ、ウィスラー）に記載される。
【００５５】
図６は、図５に示される制御ロジック５００において実現される、入力ストリング５０２をエンコードするための方法を示すフロー図である。図６は図５に関連して記載される。
【００５６】
ステップ６００では、コーディングテーブル３００（図５）および制御ロジック５００（図５）の初期設定が行なわれる。辞書は、インデックス「０」で第１の項目におけるＥＯＳコード「０」、インデックス「１」で第２の項目におけるフラッシュコード「１」、および、随意には、インデックス「２」で幅変更コードを記憶することにより初期設定される。説明を簡単にするために、図６に関連して記載される実施例は、幅変更コードを実現しない。この実施例は固定された記号幅を有する。インデックス精度レジスタ５１６（図５）は「１」にセットされ、現在のストリングの長さ５１８（図５）は「１」にセットされ、辞書に記憶されている項目の数５２０（図５）は、記号幅変更コードなしに２にセットされ、最後に加えられた長さ５２２（図５）は「１」にセットされ、入力ストリングポインタ５１４（図５）は、入力ストリング５０２（図５）における第１の記号を指し示す「０」にセットされ、ストリングレジスタ５１２は空ストリング（ＮＵＬＬ）にセットされる。処理はステップ６０１に続く。
【００５７】
ステップ６０１では、制御ロジック５００（図５）は、入力ストリング５０２（図５）における次の記号を選択し、この記号を、ストリングレジスタ５１２（図５）に記憶されている記号と連結するか、またはこの記号を空ストリングレジスタ５１２（図５）に加える。処理はステップ６０２に続く。
【００５８】
ステップ６０２では、制御ロジック５００（図５）は、ストリングレジスタ５１２（図５）の内容を探索キー５０４（図５）としてコーディングテーブル３００に送ることにより、ストリングレジスタ５１２（図５）の内容に対する項目一致を求めて辞書を探索する。制御ロジック５００（図５）はまた、命令バス５０６（図５）上で「探索および学習」命令を送る。処理はステップ６０４に続く。
【００５９】
ステップ６０４では、制御ロジック５００（図５）は、学習５０８（図５）の状態を監視して、探索キー５０４（図５）が学習されているかどうかを判断する。というのも、探索キー５０４がコーディングテーブル３００（図５）に記憶されていないからである。学習５０８（図５）の状態が、探索キー５０４（図５）が学習されていることを示す場合、
処理はステップ６０６に続く。探索キー５０４（図５）が見つかった場合、処理はステップ６２０に続く。
【００６０】
ステップ６０６では、探索キー５０４（図５）はコーディングテーブル３００に見つけられない。探索キー５０４（図５）は、次のシーケンシャルインデックスでコーディングテーブル３００（図５）に記憶されている。処理はステップ６０８に続く。
【００６１】
ステップ６０８では、制御ロジック５００（図５）が、現在のストリングの長さ５１８（図５）に記憶されている値から、ストリングレジスタ５１２（図５）に記憶されている記号の数をチェックする。現在のストリングの長さ５１８（図５）が「１」にセットされる場合、処理がステップ６１０に続いて、普通に記号を伝送する。現在のストリングの長さ５１８（図５）の内容が１より大きく、２以上の記号がストリングレジスタ５１２（図５）に記憶されていることを示している場合、処理はステップ６１２に続く。
【００６２】
ステップ６１０では、制御ロジック５００（図５）が、ストリングレジスタ５１２（図５）に記憶されている普通記号を伝送する。このストリングレジスタ５１２の前には、図４Ａに関連して記載されるように「０」にセットされた接頭語ビット４０４（図４Ａ）がある。処理はステップ６１６に続く。
【００６３】
ステップ６１２では、制御ロジック５００（図５）が、最後に加えられた長さ５２２（図５）をチェックして、辞書３０８に対する、最後に加えられたストリングの長さを判断する。記憶されている最後のストリングの長さが「１」、すなわち１つの記号である場合、処理はステップ６１６に続く。そうでない場合、処理はステップ６１４に続く。
【００６４】
ステップ６１４では、制御ロジック５００（図５）が、コードワードのテーブルインデックスフィールド４０８における先に一致したストリングのインデックスを伝送する。コードワードのテーブルインデックスフィールド４０８の前には、図４Ｂに関連して記載されるように「１」にセットされた接頭語ビット４０４（図４Ｂ）がある。ストリングは既知である。したがって、先に識別された記号のストリングのインデックスが伝送される。処理はステップ６１６に続く。
【００６５】
ステップ６１６では、制御ロジック５００（図５）が、最後に加えられた長さ５２２（図５）を現在のストリングの長さ５１８（図５）の内容にセットする。現在のストリングの長さ５１８（図５）は「１」にセットされる。処理はステップ６１７に続く。
【００６６】
ステップ６１７では、制御ロジック５００（図５）はストリングレジスタを空にセットする。処理はステップ６１８に続く。
【００６７】
ステップ６１８では、制御ロジック５００（図５）が、コーディングテーブル３００（図５）における辞書３０８（図５）がいっぱいであるかどうかをチェックする。制御ロジック５００（図５）はまた、インデックス精度レジスタ５１６が増分されるべきかどうかをチェックする。ステップ６１８は図７に関連して後に記載される。
【００６８】
ステップ６２０では、制御ロジック５００（図５）が入力ストリングポインタ５１４を増分して、入力ストリング５０２（図５）における次の記号を指す。処理はステップ６２１に続く。
【００６９】
ステップ６２１では、制御ロジック５００（図５）が、現在のストリングの長さ５１８に記憶されている記号の数を増分する。処理はステップ６２２に続く。
【００７０】
ステップ６２２では、制御ロジック５００が、エンコードすべきさらなる記号があるかどうかを、入力ストリング５０２（図５）から判断する。ストリングポインタがＥＯＳを指していない場合、デコードすべきさらなる記号が存在する。有効な記号がある場合、処理はステップ６０１に続く。ポインタがＥＯＳを指す場合、処理はステップ６２４に続く。
【００７１】
ステップ６２４では、制御ロジック５００（図５）が入力ストリング５０２（図５）のエンコードを完了した。ストリングが辞書３０８（図３）に存在する場合、制御ロジックは、エンコードされたストリング３１４（図５）上で、「１」にセットされた接頭語ビット４０４（図４Ｂ）が前にあるストリングのインデックスを伝送する。処理が完了する。制御ロジック５００（図５）は、ストリングがストリングの終り（ＥＯＳ）を記憶する場合、ＥＯＳのための、「１」にセットされた接頭語ビット４０４（図４Ｂ）が前にあるコード「１」を、エンコードされたストリング３１４（図５）上で伝送する。
【００７２】
圧縮すべき入力ストリング５０２（図５）が記号幅の倍数でない場合、特殊コードが、エンコーダ３１０（図３）によりデコーダ３１２（図３）に伝送され、その後に、記号に残ったビットの数、次いで普通記号が続く。たとえば、入力ストリング５０２（図５）が「１２３４５６７８９」であり、記号幅が２文字分である場合、構文解析境界は、１２．３４．５６．７８．９．である。こうして、最後の文字＞９＝は、部分的な記号となる。したがって、「９」は、１．特殊コード．９（８ビット上）．８（構文解析すべきビットの数）として伝送される。
【００７３】
図７は、インデックス精度レジスタ５１６（図５）に記憶されている現在のインデックス幅が増分されるべきかどうかを判断するために図６におけるステップ６１８で実行されるステップと、辞書３０８（図５）がいっぱいである場合コーディングテーブル３００（図５）を再初期設定するためのステップとを示すフロー図である。
【００７４】
辞書３００（図５）がいっぱいである場合、フラッシュコードがデコーダ３１２（図３）に伝送されて、フラッシュ動作を実行すべきであることを示す。フラッシュ動作は、コーディングテーブル３００（図５）におけるすべての項目をクリアし、インデックス「０」でＥＯＳ、およびインデックス「１」でフラッシュコードを記憶し、かつインデックス幅を「１」に初期設定することにより、コーディングテーブル３００（図５）を再初期設定する。インデックス幅は、コーディングテーブル３００（図５）に記憶されている項目の数が２の累乗の境界を超えるたびに、１ビットだけ増分される。
【００７５】
ステップ７００では、制御ロジック５００（図５）が、辞書３０８（図５）がいっぱいであるかどうかを、項目の数５２０（図５）の内容から判断する。辞書３０８（図５）がいっぱいである場合、処理はステップ７０６に続く。そうでない場合、処理はステップ７０２に続く。
【００７６】
ステップ７０２では、制御ロジック５００（図５）が、コーディングテーブル３００（図５）における項目の数５２０（図５）の内容を判断し、かつ、コーディングテーブル３００（図５）における項目の数が２の累乗の境界に達したかどうかを判断する。インデックスの幅は、１ビットで始まり、コーディングテーブル３００（図５）における最後に記憶された項目のインデックスが２の累乗の境界に達するたびに、１だけ増分される。たとえば、インデックス精度レジスタ５１６（図５）は、辞書が２3未満の項目、すなわち８未満の項目を記憶する一方で、３ビット幅のインデックスのために３を記憶し、８項目が記憶されているとき４に増分される。コーディングテーブル３００が２の累乗の境界に達した場合、処理はステップ７０４に続く。そうでない場合、処理はステップ６２２（図６）に続く。
【００７７】
ステップ７０４では、コーディングテーブル３００（図５）が２の累乗の境界に達し、インデックス精度レジスタ５１６（図５）が増分される。インデックス精度レジスタ５１６（図５）は、ビットがいくつテーブルインデックスフィールド４０８（図４Ｂ）で伝送されるかを示す。処理はステップ６２２（図６）に続く。
【００７８】
ステップ７０６では、辞書３０８（図５）はいっぱいである。制御ロジック５００（図５）は、辞書３０８（図５）の第２の項目に記憶されているフラッシュコードを伝送する。フラッシュコードが、エンコードされたストリング３１４（図３）上で伝送され、このため、デコーダ３１２（図３）は、コーディングテーブル３００（図５）がフラッシュされていることを知り、その辞書３０８をまたフラッシュすることができる。処理はステップ７０８に続く。
【００７９】
ステップ７０８では、コーディングテーブル３００（図５）におけるテーブル項目のすべてがフラッシュされる。処理はステップ７１０に続く。
【００８０】
ステップ７１０では、コーディングテーブル３００（図５）が初期設定される。記号幅変更が選択されない場合、辞書３０８（図５）は、インデックス「０」で第１の項目における「０」およびインデックス「１」で第２の項目における「１」を記憶することにより、初期設定される。インデックス精度レジスタ５１６（図５）を１にセットし、ストリングレジスタ５１２（図５）に記憶されている記号の数を「１」にセットし、辞書３０８（図５）に記憶されている項目の数５２０（図５）を２にセットし、最後に加えられた長さ５２２（図５）を「１」にセットし、入力ストリングポインタ５１４（図５）を現在の記号における位置のインデックスにセットする。処理はステップ６２２（図６）に続く。
【００８１】
図８Ａ〜図８Ｂは、受取られたエンコードされたストリング３１４（図３）をデコードするための、図３に示されるデコーダ３１２において実現される方法を示すフロー図である。受取られたコードワードをデコードするために、デコーダ３１２（図３）は複数のレジスタを含む。これらレジスタは、最後にデコードされたストリングのインデックスを記憶するためのold＿indexレジスタと、インデックスを記憶するためのnew＿indexレジスタと、現在のデコーダされたストリングを（普通に）記憶するためのデコードされたストリングレジスタと、現在のデコードされたストリングの第１の記号に等しい記号とを含む。
【００８２】
デコーダ３１２（図３）は、受取られる第１のビットを参照して、記号またはインデックスが受取られているかを判断する。デコーダ３１２（図３）は、デコーディングテーブル３２０（図３）に記憶されている一連の学習された記号とインデックスを置換えることにより、受取られたインデックスをデコードする。デコーダ３１２（図３）は、次のシーケンシャルインデックスで普通記号をデコーディングテーブル３２０（図３）に記憶することにより、受取られた普通記号を学習する。
【００８３】
ステップ８００では、デコーダ３１２（図３）が、エンコードされたストリング３１４（図３）から第１のビットを抽出する。初めに、デコーダにおける辞書３０８（図３）は、記号幅変更が選択されない場合、２つの項目を記憶する。デコーダ３１２（図３）は記号を学習し、エンコードされたストリング３１４（図３）において受取られた記号から辞書３０８（図３）に登録する。第１のエンコードされたストリング３１４（図３）における、デコーダ３１２（図３）により受取られる第１のビットは、第１のコードワードが、デコーダ３１２（図３）によって学習されるべき普通記号を記憶する普通記号フィールド４０６（図４Ａ）を含むことを示す。処理はステップ８０２に続く。
【００８４】
ステップ８０２では、受取られる第１のビットが「０」にセットされ、接頭語ビット４
０４が、普通記号フィールド４０６に記憶され、デコーダによって学習されるべき記号の前にあることを示す。デコーダ３１２（図３）は、エンコードされたストリング３１４（図３）から普通記号を抽出する。抽出されるビットの数は、選択された記号の幅に依存する。たとえば、選択された記号幅が１６ビットである場合、デコーダ３１２（図３）は、エンコードされた入力ストリング３１４（図３）における次の１６ビットを得る。処理はステップ８０４に続く。
【００８５】
ステップ８０４では、普通記号が、辞書３０８（図３）における次のシーケンシャルインデックスで、デコーディングテーブル３２０（図３）における辞書３０８（図３）に加えられる。処理はステップ８０６に続く。
【００８６】
ステップ８０６では、old＿indexレジスタが、辞書３０８（図３）における加えられた記号のインデックスにセットされる。処理はステップ８０８に続く。
【００８７】
ステップ８０８では、エンコードされたストリング３１４（図３）に受取られる記号が、デコードされた出力ストリング３０４（図３）として、デコーダにより出力される。処理はステップ８１０に続く。
【００８８】
ステップ８１０では、デコーダ３１２（図３）は、エンコードされたストリング３１４（図３）から次のビットを得て、コードワードが普通記号またはインデックスを含むかどうか判断する。処理はステップ８１２に続く。
【００８９】
ステップ８１２では、デコーダ３１２（図３）が、エンコードされたストリング３１４（図３）に受取られる次のビットを調べて、テーブルインデックス４０８（図４Ｂ）に対して「１」、または普通記号４０６（図４Ａ）に対して「０」にセットされるかどうかを判断する。次のビットが「０」にセットされる場合、処理がステップ８１３に続き、普通記号４０６（図４Ａ）を処理する。次のビットが「１」にセットされる場合、処理がステップ８３０に続いて、テーブルインデックス４０８（図４Ｂ）を処理する。
【００９０】
ステップ８１３では、デコーダ３１２（図３）が、エンコードされたストリング３１４（図３）から次のビットを得る。次のビットの数は記号の幅に依存する。デコーダ３１２（図３）は、これらビットをデコードされたストリングレジスタに記憶する。処理はステップ８１４に続く。
【００９１】
ステップ８１４では、デコーダ３１２（図３）が、デコードされたストリングの第１の記号（記号自体）を記号レジスタに記憶する。処理はステップ８１５に続く。
【００９２】
ステップ８１５では、デコーダ３１２（図３）が、old＿indexでのストリングの連結により得られるストリングと、次のシーケンシャルインデックスにおけるデコードされた記号とを辞書３０８（図３）に記憶する。ストリングまたは記号が辞書３０８（図３）に加えられるたびに、デコーダ３１２（図３）は、辞書３０８（図３）における項目の数が２の累乗に達していないことをチェックする。辞書３０８（図３）における項目の数が２の累乗に達した場合、デコーダ３１２（図３）は、図７に関連してエンコーダのために既に記載されているように、インデックス精度を増分する。エンコーダ３１０（図３）とは違って、デコーダ３１２（図３）は辞書３０８（図３）がいっぱいであるかどうかをチェックする必要はない。というのも、いっぱいな状態は、エンコーダ３１０（図３）によって送られるフラッシュコードにより示されるからである。処理はステップ８１６に続く。
【００９３】
ステップ８１６では、デコーダ３１２（図３）が、次のシーケンシャルインデックスにおけるデコードされた記号を辞書３０８（図３）に記憶する。処理はステップ８１８に続
く。
【００９４】
ステップ８１８では、デコードされた記号または記号のストリングのインデックスが、old＿indexレジスタに記憶される。処理はステップ８２０に続く。
【００９５】
ステップ８２０では、ストリングレジスタに記憶されているデコードされたストリングが、デコーダ３１２（図３）によって出力される。処理はステップ８２２に続く。
【００９６】
ステップ８２２では、デコーダ３１２（図３）は、エンコードされたストリング３１４（図３）にデコードされるべきさらなるビットがあるかどうかを判断する。そうである場合、処理はステップ８１０に続く。そうでない場合、処理が完了する。
【００９７】
ステップ８３０では、new＿indexレジスタが、テーブルインデックスフィールド４０８（図４Ｂ）における次のインデックスの内容にセットされる。新しいインデックスレジスタに記憶されているビットの数は、エンコーダによって選択されるインデックス精度に依存する。処理はステップ８３２に続く。ステップ８３２では、デコーダ３１２（図３）が新しいインデックスレジスタの内容を調べる。デコーダ３１２（図３）は、受取られたインデックスがＥＯＳであるか、またはフラッシュコードであるかをチェックする。受取られたインデックスがフラッシュコードである場合、テーブルは、エンコーダ３１０（図３）のために図７に関連して先に記載されているように初期設定される。受取られたインデックスがＥＯＳである場合、処理は完了する。受取られたインデックスがＥＯＳまたはフラッシュコードでない場合、デコーダは、新しいインデックスが有効であるかどうか判断する。新しいインデックスが有効である場合、処理はステップ８３４に続く。そうでない場合、処理はステップ８３６に続く。
【００９８】
ステップ８３４では、デコーダ３１２（図３）は、デコードされたストリングレジスタにおける新しいインデックスの辞書からの変換を記憶する。処理はステップ８４０に続く。
【００９９】
ステップ８３６では、新しいインデックスは有効ではない。デコーダ３１２（図３）は、古いインデックスの変換を、デコードされたストリングレジスタに記憶する。処理はステップ８３８に続く。
【０１００】
ステップ８３８では、デコーダ３１２（図３）が、デコードされたストリングと記号との連結と等しくなるように、デコードされたストリングをセットする。処理はステップ８４０に続く。
【０１０１】
ステップ８４０では、デコーダ３１２（図３）が、記号レジスタの内容を、デコードされたストリングの第１の記号にセットする。処理はステップ８４２に続く。
【０１０２】
ステップ８４２では、old＿indexで辞書３０８（図５）に記憶されている記号のストリングが記号と連結され、結果として生じるストリングが、次のシーケンシャルインデックスで辞書に記憶される。処理はステップ８１８に続く。
【０１０３】
図９には、入力ストリング、入力ストリング５０２の処理後のエンコーダにおける辞書３０８の内容、およびエンコードされたストリングが示される。図９は、図５および図６に関連して記載される。
【０１０４】
ステップ６００（図６）では、辞書３０８が、インデックス０でＥＯＳを、かつインデックス１でフラッシュコードを記憶することにより初期設定される。図示される実施例で
は、記号幅は２文字（１６ビット）に固定される。しかしながら、記号幅は１６ビットに制限されず、既に記載されたように動的に修正可能である。入力ストリング５０２は、複数の記号９０４1〜９０４10を含む。入力ストリング５０２における最初の１６ビット幅の記号９０４1は「/w」であり、入力ストリングにおける最後の１６ビット幅の記号９０４10は「t/」である。
【０１０５】
ステップ６０１（図６）では、制御ロジック５００（図５）が入力ストリング５０２を構文解析し、入力ストリング５０２から第１の記号９０４1「/w」を抽出する。入力スト
リング５０２から抽出されるべき記号は、ストリングポインタレジスタ５１４（図５）の内容に依存する。初めには、ストリングポインタレジスタ５１４（図５）の内容は、入力ストリング５０２における第１の記号９０４1を指し、ストリングレジスタ５１２（図５
）は空である。制御ロジック５００（図５）は、空であるストリングレジスタ５１２（図５）の内容と記号９０４1を連結する。
【０１０６】
ステップ６０２（図６）では、制御ロジック５００（図５）は、ストリングレジスタ５１２（図５）の内容を探索キー５０４（図５）としてコーディングテーブル３００（図５）に送る。コーディングテーブル３００（図５）は、記号９０４1を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４1は辞書３０８（図５）に見つけられない。ステップ６０６（図６）では、コーディングテーブル３００（図５）は、次のシーケンシャルインデックス、すなわちインデックス２で、記号９０４1を辞書３０８に記憶することにより、記号９０４1を学習し、記号９０４1が学習５０８を通じて学習されることを示す。ステップ６０８（図６）では、ストリングレジスタ５０２（図５）に記憶されている記号の数は「１」であり、こうして、処理はステップ６１０（図６）に続く。ステップ６１０（図６）では、制御ロジック５００（図５）が、エンコードされたストリング３１４（図３）上でコードワード９０６1を送り、このため、デコーダ３１２（図３）は記号９０４1を学習することができる。コードワード９０６1は、図４Ａに関連して記載されるように「０」にセットされた接頭語ビット４０４（図４Ａ）が前にある普通記号９０４1を含む。
【０１０７】
普通記号９０４1が送られた後、制御ロジック５００（図５）は、ステップ６１６（図６）、６１７（図６）および６１８（図６）においてさまざまなレジスタを修正する。ステップ６１６（図６）では、制御ロジック５００（図５）は、最後に加えられた長さ５２２（図５）を現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）を「１」にセットする。ステップ６１７（図６）では、制御ロジック５００（図５）がストリングレジスタ５１２を空にセットする。
【０１０８】
ステップ６２２（図６）では、制御ロジック５００（図５）が、入力ストリング５０２において（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１（図６）に続いて、入力ストリング５０２を構文解析し続ける。
【０１０９】
ステップ６０１（図６）では、入力ストリングポインタレジスタ５１４（図５）の内容は、依然として、入力ストリング５０２（図５）における第１の記号９０４1を指す。制御ロジック５００（図５）は再び第１の記号９０４1を抽出し、これを、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、ストリングレジスタ５１２（図５）の内容を探索キー５０４（図５）としてコーディングテーブル３００（図５）に送る。コーディングテーブル３００（図５）は、記号９０４1を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４1が辞書３０８（図５）に見つけられる。というのも、記号９０４1が、ステップ６０１〜６２２（図６）を経る先の繰返しにおいて、辞書３０８（図５）に記憶されたからである。
【０１１０】
記号９０４1を見つけると、ステップ６２０（図６）では、制御ロジック５００（図５）が入力ストリングポインタ５１４を増分して、入力ストリング５０２（図５）における次の記号９０４2を指す。ステップ６２１（図６）では、制御ロジック５００（図５）が、ストリングレジスタ５１２（図５）に記憶されている記号の数を増分する。ステップ６２２（図６）では、制御ロジック５００（図５）は、エンコードすべきさらなる記号があることを、入力ストリング５０２（図５）から判断する。処理がステップ６０１（図６）に続き、入力ストリングポインタが入力ストリング５０２における第２の記号９０４2を指し、ストリングレジスタ５１２（図５）が第１の記号９０４1「/w」を記憶する。
【０１１１】
ステップ６０１（図６）では、制御ロジック５００（図５）が、記号９０４1を入力ストリング５０２における次の記号９０４2と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）が、連結されたストリング「/wed」を探索キー５０４としてコーディングテーブル３００に送る。ステップ６０４（図６）では、一連の記号「/wed」はコーディングテーブル３００には見つけられない。ステップ６０６（図６）では、一連の記号「/wed」が、次のシーケンシャルインデックス、すなわちインデックス３で、辞書３０８に「/wed」を記憶することにより学習される。一連の記号「/wed」は普通には記憶されていない。代わりに、一連の記号「/wed」は、その接頭語を指すインデックスとともに記憶されている。一連の記号「/wed」に対する接頭語は、インデックス２で記憶されている「/w」である。一連の記号「/wed」は、テーブルインデックス２として記憶されている「/w」および普通に記憶されている「ed」を含む（２，ed）として、インデックス３で記憶されている。ステップ６０８（図６）では、ストリングレジスタ５１２（図５）における記号の数は２である。こうして、ステップ６１２（図６）では、制御ロジック５００（図５）が、最後に加えられたストリングにおける記号の最後の数が１であることを判断し、ステップ６１６（図６）では、制御ロジック５００（図５）が、最後に加えられた長さ５２２（図５）を現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）を「１」にセットする。ステップ６１７（図６）では、制御ロジック５００（図５）はストリングレジスタ５１２を空にセットする。
【０１１２】
ステップ６２２（図６）では、制御ロジック５００（図５）は、入力ストリング５０２に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１（図６）に続く。
【０１１３】
ストリングポインタレジスタ５１４（図５）の内容は記号９０４2を指す。ストリングレジスタ５１２（図５）は空である。ステップ６０１（図６）では、制御ロジックは、入力ストリング５０２（図５）における次の記号９０４2「ed」を、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００は、ストリングレジスタ５１２（図５）の内容、すなわち、入力ストリング５０２における次の記号９０４2「ed」を、探索キー５０４（図５）として、コーディングテーブル３００に送る。コーディングテーブル３００（図５）は、記号９０４2を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４2は見つけられない。ステップ６０６（図６）では、コーディングテーブル３００（図５）は、インデックス４で記号９０４2を辞書３０８に記憶することにより記号９０４2を学習し、記号９０４2が学習５０８を通じて学習されていることを示す。ステップ６０８（図６）では、記憶されている記号の数は「１」であり、こうして、処理はステップ６１０（図６）に続く。ステップ６１０（図６）では、制御ロジック５００（図５）は、エンコードされたストリング３１４（図３）上でコードワード９０６2を送り、このため、デコーダは記号を学習することができる。コードワード９０６2は、図４Ａに関連して記載されるように「０」にセットされた接頭語ビット４０４（図４Ａ）が前にある普通記号９０４2を含む。
【０１１４】
普通記号９０４2が送られた後、制御ロジック５００（図５）はさまざまなレジスタを修正する。ステップ６１６（図６）では、制御ロジック５００（図５）は、最後に加えられた長さ５２２（図５）を現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）は「１」にセットされる。ステップ６１７（図６）では、制御ロジック５００（図５）はストリングレジスタ５１２を空にセットする。
【０１１５】
ステップ６２２（図６）では、制御ロジック５００（図５）が、入力ストリング５０２に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１（図６）に続く。
【０１１６】
ステップ６０１（図６）では、入力ストリングポインタレジスタ５１４（図５）の内容は、依然として、入力ストリング５０２（図５）における記号９０４2を指す。制御ロジック５００は、記号９０４2を、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、ストリングレジスタ５１２（図５）の内容を探索キー５０４（図５）として、コーディングテーブル３００（図５）に送る。コーディングテーブル３００（図５）は、記号９０４2を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４2が辞書３０８（図５）に見つけられる。というのも、記号９０４2が、ステップ６０１〜６２２（図６）を経る先の繰返しにおいて辞書３０８（図５）に記憶されたからである。
【０１１７】
ステップ６２０（図６）では、制御ロジック５００（図５）が入力ストリングポインタ５１４を増分して、入力ストリング５０２（図５）における次の記号９０４3を指す。ステップ６２１（図６）では、制御ロジック５００（図５）は、ストリングレジスタ５１２（図５）に記憶されている記号の数を増分する。ステップ６２２（図６）では、制御ロジック５００（図５）は、エンコードすべきさらなる記号があることを、入力ストリング５０２（図５）から判断する。処理がステップ６０１（図６）に続き、入力ストリングポインタは入力ストリングにおける次の記号９０４3「/w」を指し、ストリングレジスタは記号９０４2「ed」を記憶する。
【０１１８】
ステップ６０１（図６）では、制御ロジック５００（図５）が、ストリングレジスタ５１２（図５）に記憶されている記号９０４2を、入力ストリング５０２における次の記号９０４3と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、一連の記号「ed/w」を探索キー５０４として、コーディングテーブル３００に送る。コーディングテーブル３００は、一連の記号「ed/w」を求めて辞書３０８を探索する。
【０１１９】
ステップ６０４（図６）では、一連の記号「ed/w」は見つけられない。ステップ６０６（図６）では、一連の記号「ed/w」が、インデックス５で一連の記号を辞書３０８に記憶することにより学習される。一連の記号は普通には記憶されない。代わりに、一連の記号「ed/w」はその接頭語を指すインデックス４とともに記憶される。というのも、記号「ed」がインデックス４で記憶されているからである。一連の記号「ed/w」は、インデックス４として記憶されている「ed」および普通に記憶されている「/w」を含む（４，/w）として、インデックス５で記憶される。ストリングレジスタ５１２（図５）における記号の数は２である。こうして、ステップ６１２（図６）では、制御ロジック５００（図５）は、最後に加えられたストリングにおける記号の最後の数が１であることを判断し、ステップ６１６（図６）では、制御ロジック５００（図５）は、最後に加えられた長さ５２２（図５）を、現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）は「１」にセットされる。ステップ６１７（図６）では、制御ロジック５００（図５）はストリングレジスタ５１２を空にセットする。
【０１２０】
ステップ６２２（図６）では、制御ロジック５００（図５）は、入力ストリング５０２
に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１（図６）に続く。
【０１２１】
ストリングポインタレジスタ５１４（図５）の内容は記号９０４3を指す。ストリングレジスタ５１２（図５）は空である。ステップ６０１（図６）では、制御ロジック５００（図５）は、入力ストリング５０２（図５）における次の記号９０４3「/w」を、ストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００は、ストリングレジスタ５１２（図５）の内容、すなわち、入力ストリング５０２における次の記号９０４3「/w」を探索キー５０４（図５）として、コーディングテーブル３００に送る。コーディングテーブル３００（図５）は、記号９０４3を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４3は、インデックス２で辞書３０８（図５）に見つけられる。というのも、記号９０４3が、ステップ６０１〜６２２（図６）を経る先の繰返しにおいて辞書３０８（図５）に記憶されたからである。
【０１２２】
ステップ６２０（図６）では、制御ロジック５００（図５）が、入力ストリングポインタ５１４を増分して、入力ストリング５０２（図５）における次の記号９０４4を指す。
ステップ６２１（図６）では、制御ロジック５００（図５）は、ストリングレジスタ５１２（図５）に記憶されている記号の数を２に増分する。ステップ６２２（図６）では、制御ロジック５００（図５）は、エンコードすべきさらなる記号があることを、入力ストリング５０２（図５）から判断する。処理がステップ６０１（図６）に続き、入力ストリングポインタ５１４（図５）は入力ストリングにおける次の記号９０４4「e/」を指し、ストリングレジスタ５１２（図５）は記号９０４3「/w」を記憶する。
【０１２３】
ステップ６０１（図６）では、制御ロジック５００（図５）が、記号９０４3を入力ストリング５０２における次の記号９０４4と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、一連の記号「/we/」を探索キー５０４としてコーディングテーブル３００に送る。コーディングテーブル３００は、一連の記号「/we/」を求めて辞書３０８を探索する。ステップ６０４（図６）では、一連の記号「/we/」は見つけられない。ステップ６０６（図６）では、一連の記号「/we/」は、インデックス６で一連の記号を辞書３０８に記憶することにより学習される。一連の記号は普通には記憶されない。代わりに、一連の記号「/we/」は、その接頭語を指すインデックス１とともに記憶される。というのも、記号「/w」がインデックス２で記憶されているからである。一連の記号「/we/」は、インデックス２として記憶されている「/w」および普通に記憶されている「e/」を含む（２，e/）として、インデックス６で記憶される。ストリングレジスタ５１２（図５）における記号の数は２である。こうして、ステップ６１２（図６）で、制御ロジック５００（図５）が、最後に加えられたストリングにおける記号の最後の数が２であることを判断し、ステップ６１４（図６）で、制御ロジック５００（図５）が、エンコードされたストリング３１４（図３）上でコードワード９０６3を送る。コードワード９０６3は、図４Ｂに関連して記載されるように「１」が前にあるインデックス２を含む。
【０１２４】
ステップ６１６（図６）では、制御ロジック５００（図５）は、最後に加えられた長さ５２２（図５）を現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）が「１」にセットされる。ステップ６１７では、制御ロジック５００（図５）はストリングレジスタ５１２を空にセットする。
【０１２５】
ステップ６２２（図６）では、制御ロジック５００（図５）が、入力ストリング５０２に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１（図６）に続く。
【０１２６】
ストリングポインタレジスタ５１４（図５）の内容は記号９０４4「e/」を指す。スト
リングレジスタ５１２（図５）は空である。ステップ６０１（図６）では、制御ロジックは、入力ストリング５０２（図５）における次の記号９０４4を、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００は、ストリングレジスタ５１２（図５）の内容、すなわち、入力ストリング５０２における次の記号９０４4「e/」を探索キー５０４（図５）として、コーディングテーブル３００に送る。コーディングテーブル３００（図５）は、記号９０４4を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４4は見つけられない。ステップ６０６（図６）では、コーディングテーブル３００（図５）は、インデックス７で記号９０４4を辞書３０８に記憶することにより記号９０４4を学習し、記号９０４4が学習５０８を通じて学習されていることを示す。ステップ６０８（図６）では、記憶されている記号の数は「１」であり、こうして、処理がステップ６１０（図６）に続く。ステップ６１０（図６）では、制御ロジック５００（図５）は、エンコードされたストリング３１４（図３）上でコードワード９０６4を送り、このため、デコーダは記号を学習することができる。コードワード９０６4は、図４Ａに関連して記載されるように「０」にセットされた接頭語ビット４０４（図４Ａ）が前にある普通記号９０４4を含む。
【０１２７】
普通記号９０４4が送られた後、制御ロジック５００（図５）はさまざまなレジスタを
修正する。ステップ６１６（図６）では、制御ロジック５００（図５）は、最後に加えられた長さ５２２（図５）を現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）が「１」にセットされる。ステップ６１７では、制御ロジック５００（図５）はストリングレジスタ５１２を空にセットする。
【０１２８】
ステップ６２２（図６）では、制御ロジック５００（図５）は、入力ストリング５０２に（ＥＯＳのない）別の有効な記号があることを判断し、処理がステップ６０１（図６）に続く。
【０１２９】
ステップ６０１（図６）では、入力ストリングポインタレジスタ５１４の内容は、依然として、入力ストリング５０２（図５）における記号９０４4を指す。制御ロジック５００は、記号９０４4を、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、ストリングレジスタ５１２（図５）の内容を探索キー５０４（図５）として、コーディングテーブル３００（図５）に送る。コーディングテーブル３００（図５）は、記号９０４4を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４4が辞書３０８（図５）に見つけられる。というのも、記号９０４4が、ステップ６０１〜６２２（図６）を経る先の繰返しにおいて、辞書３０８（図５）に記憶されたからである。
【０１３０】
ステップ６２０（図６）では、制御ロジック５００（図５）が入力ストリングポインタ５１４を増分して、入力ストリング５０２（図５）における次の記号９０４5を指す。ステップ６２１（図６）では、制御ロジック５００（図５）は記号の数を２に増分する。ステップ６２２（図６）では、制御ロジック５００（図５）は、エンコードすべきさらなる記号があることを、入力ストリング５０２（図５）から判断する。処理がステップ６０１（図６）に続き、入力ストリングポインタは入力ストリングにおける次の記号９０４5「we」を指し、ストリングレジスタは記号９０４4「e/」を記憶する。
【０１３１】
ステップ６０１（図６）では、制御ロジック５００（図５）は、記号９０４4を、入力ストリング５０２における次の記号９０４5と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、一連の記号「e/we」を探索キー５０４として、コーディングテーブル３００に送る。コーディングテーブル３００は、一連の記号「e/we」を求めて辞書３０８を探索する。ステップ６０４（図６）では、一連の記号「e/we」は見つけられない。ステップ６０６（図６）では、一連の記号「e/we」が、インデックス８で一連の
記号を辞書３０８に記憶することにより学習される。一連の記号は普通には記憶されない。代わりに、一連の記号「e/we」がその接頭語を指すインデックス７とともに記憶される。というのも、記号「e/」がインデックス７で記憶されているからである。一連の記号「e/we」は、インデックス７として記憶されている「e/」および普通に記憶されている「we」を含む（７，we）として、インデックス８で記憶される。ストリングレジスタ５１２（図５）における記号の数は２である。こうして、ステップ６１２（図６）では、制御ロジック５００（図５）が、最後に加えられたストリングにおける記号の最後の数が１であることを判断し、ステップ６１６（図６）では、制御ロジック５００（図５）が、最後に加えられた長さ５２２（図５）を現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）が「１」にセットされる。ステップ６１７（図６）では、制御ロジック５００（図５）はストリングレジスタ５１２を空にセットする。
【０１３２】
ステップ６２２（図６）では、制御ロジック５００（図５）は、入力ストリング５０２に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１（図６）に続く。
【０１３３】
ストリングポインタレジスタ５１４（図５）の内容は記号９０４5を指す。ストリングレジスタ５１２（図５）は空である。ステップ６０１（図６）では、制御ロジックは、入力ストリング５０２（図５）における次の記号９０４5「we」を、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００は、ストリングレジスタ５１２（図５）の内容、すなわち入力ストリング５０２における次の記号９０４5「we」を探索キー５０４（図５）として、コーディングテーブル３００に送る。コーディングテーブル３００（図５）は、記号９０４5を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４5は見つけられない。ステップ６０６（図６）では、コーディングテーブル３００（図５）は、インデックス９で記号９０４5を辞書３０８に記憶することにより記号９０４5を学習し、記号９０４5が学習５０８を通じて学習されていることを示す。ステップ６０８（図６）では、記憶されている記号の数は「１」であり、こうして、処理はステップ６１０（図６）に続く。ステップ６１０（図６）では、制御ロジック５００（図５）が、エンコードされたストリング３１４（図３）上でコードワード９０６5を送り、このため、デコーダは記号を学習することができる。コードワード９０６5は、図４Ａに関連して記載されるように「０」にセットされた接頭語ビット４０４（図４Ａ）が前にある普通記号９０４5を含む。
【０１３４】
普通記号９０４5が送られた後、制御ロジック５００（図５）はさまざまなレジスタを修正する。ステップ６１６（図６）では、制御ロジック５００（図５）は、最後に加えられた長さ５２２（図５）を、現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）が「１」にセットされる。ステップ６１７（図６）では、制御ロジック５００（図５）はストリングレジスタ５１２を空にセットする。
【０１３５】
ステップ６２２（図６）では、制御ロジック５００（図５）は、入力ストリング５０２に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１（図６）に続く。
【０１３６】
ステップ６０１（図６）では、入力ストリングポインタレジスタ５１４の内容は、依然として、入力ストリング５０２（図５）における記号９０４5を指す。制御ロジック５００は、記号９０４5を、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、ストリングレジスタ５１２（図５）の内容を探索キー５０４（図５）として、コーディングテーブル３００（図５）に送る。コーディングテーブル３００（図５）は、記号９０４5を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４5が辞書３０８（図５）に見つけら
れる。というのも、記号９０４5が、ステップ６０１〜６２２を経る先の繰返しにおいて、辞書３０８（図５）に記憶されたからである。
【０１３７】
ステップ６２０（図６）では、制御ロジック５００（図５）が入力ストリングポインタ５１４を増分して、入力ストリング５０２（図５）における次の記号９０４6を指す。ステップ６２１（図６）では、制御ロジック５００（図５）が記号の数を２に増分する。ステップ６２２（図６）では、制御ロジック５００（図５）は、エンコードすべきさらなる記号があることを、入力ストリング５０２（図５）から判断する。処理がステップ６０１（図６）に続き、入力ストリングポインタは入力ストリングにおける次の記号９０４6「/e」を指し、ストリングレジスタは記号９０４5「we」を記憶する。
【０１３８】
ステップ６０１（図６）では、制御ロジック５００（図５）は、記号９０４5を、入力ストリング５０２における次の記号９０４6と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、一連の記号「wee/」を探索キー５０４として、コーディングテーブル３００に送る。コーディングテーブル３００は、一連の記号「wee/」を求めて辞書３０８を探索する。ステップ６０４（図６）では、一連の記号「wee/」は見つけられない。ステップ６０６（図６）では、一連の記号「wee/」は、インデックス１０で一連の記号を辞書３０８に記憶することにより学習される。一連の記号は普通には記憶されない。代わりに、一連の記号「wee/」が、その接頭語を指すインデックス９とともに記憶される。というのも、記号「we」がインデックス９で記憶されているからである。一連の記号「wee/」は、インデックス９として記憶されている「we」および普通に記憶されている「e/」を含む（９，e/）として、インデックス１０で記憶される。ストリングレジスタ５１２（図５）における記号の数は２である。こうして、ステップ６１２（図６）では、制御ロジック５００（図５）は、最後に加えられたストリングにおける記号の最後の数が１であることを判断し、ステップ６１６では、制御ロジック５００（図５）は、最後に加えられた長さ５２２（図５）を、現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）が「１」にセットされる。ステップ６１７（図６）では、制御ロジック５００（図５）はストリングレジスタ５１２を空にセットする。
【０１３９】
ステップ６２２（図６）では、制御ロジック５００（図５）は、入力ストリング５０２に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１（図６）に続く。
【０１４０】
ストリングポインタレジスタ５１４（図５）の内容は、記号９０４6を指す。ストリングレジスタ５１２（図５）は空である。ステップ６０１（図６）では、制御ロジックは、入力ストリング５０２（図５）における次の記号９０４6を、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００は、ストリングレジスタ５１２（図５）の内容、すなわち入力ストリング５０２における次の記号９０４6「e/」を探索キー５０４（図５）として、コーディングテーブル３００に送る。コーディングテーブル３００（図５）は、記号９０４6を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４6がインデックス７で見つけられる。
【０１４１】
ステップ６２０（図６）では、制御ロジック５００（図５）が入力ストリングポインタ５１４を増分して、入力ストリング５０２（図５）における次の記号９０４7を指す。ステップ６２１（図６）では、制御ロジック５００（図５）が記号の数を増分する。ステップ６２２（図６）では、制御ロジック５００（図５）は、エンコードすべきさらなる記号があることを、入力ストリング５０２（図５）から判断する。処理がステップ６０１（図６）に続き、入力ストリングポインタは、入力ストリングにおける次の記号９０４7「we」を指し、ストリングレジスタは記号９０４6「e/」を記憶する。
【０１４２】
ステップ６０１（図６）では、制御ロジック５００（図５）は、記号９０４6を、入力ストリング５０２における次の記号９０４7と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、一連の記号「e/we」を探索キー５０４として、コーディングテーブル３００に送る。コーディングテーブル３００は、一連の記号「e/we」を求めて辞書３０８を探索する。ステップ６０４（図６）では、一連の記号「e/we」がインデックス８で見つけられる。ステップ６２０（図６）では、制御ロジック５００（図５）が入力ストリングポインタ５１４を増分して、入力ストリング５０２（図５）における次の記号９０４8を指す。ステップ６２１（図６）では、制御ロジック５００（図５）が、記号の数を３に増分する。ステップ６２２（図６）では、制御ロジック５００（図５）は、エンコードすべきさらなる記号があることを、入力ストリング５０２（図５）から判断する。処理がステップ６０１（図６）に続き、入力ストリングポインタ５１４（図５）は入力ストリングにおける次の記号９０４8「b/」を指し、ストリングレジスタ５１２（図５）は記号「e/we」を記憶する。
【０１４３】
ステップ６０１では、制御ロジック５００（図５）は、記号９０４8を、ストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、ストリングレジスタ５１２（図５）の内容「e/web/」を探索キー５０４として、コーディングテーブル３００に送る。コーディングテーブルは、一連の記号「e/web/」を求めて辞書３０８を探索する。ステップ６０４（図６）では、一連の記号「e/web/」は見つけられない。ステップ６０６（図６）では、一連の記号「e/web/」は、インデックス１１で一連の記号を辞書３０８に記憶することにより学習される。一連の記号は普通には記憶されない。代わりに、一連の記号「e/web/」が、その接頭語を指すインデックス８とともに記憶される。というのも、記号「e/we」がインデックス８で記憶されているからである。一連の記号「e/web/」は、インデックス８として既に記憶された「e/we」および普通に記憶されている「b/」を含む（８，b/）として、インデックス１１で記憶される。ストリングレジスタ５１２（図５）における記号の数は３である。こうして、ステップ６１２（図６）では、制御ロジック５００（図５）は、最後に加えられたストリングにおける記号の最後の数が１ではないことを判断し、ステップ６１４（図６）では、制御ロジック５００（図５）は、エンコードされたストリング３１４（図３）上でコードワード９０６6を送る。コードワード９０６6は、記号のストリング「e/we」が記憶されているインデックス８を含み、図４Ｂに関連して記載されるように「１」が前に付される。
【０１４４】
ステップ６２２（図６）では、制御ロジック５００（図５）は、入力ストリング５０２に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１（図６）に続く。
【０１４５】
ストリングポインタレジスタ５１４（図５）の内容は記号９０４8を指す。ストリングレジスタ５１２（図５）は空である。ステップ６０１（図６）では、制御ロジックは、入力ストリング５０２（図５）における次の記号９０４8「b/」を、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００は、ストリングレジスタ５１２（図５）の内容、すなわち入力ストリング５０２における次の記号９０４8「b/」を探索キー５０４（図５）として、コーディングテーブル３００に送る。コーディングテーブル３００（図５）は、記号９０４8を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４8は見つけられない。ステップ６０６（図６）では、コーディングテーブル３００（図５）は、インデックス１２で記号９０４8を辞書３０８に記憶することにより記号９０４8を学習し、記号９０４8が学習５０８を通じて学習されていることを示す。ステップ６０８（図６）では、記憶されている記号の数は「１」であり、こうして、処理がステップ６１０（図６）に続く。ステップ６１０（図６）では、制御ロジック５００（図５）が、エンコードされたストリング３１４（図３）上でコードワード９０６7を送り、このため、デコーダは記号を学習することがで
きる。コードワード９０６7は、図４Ａに関連して記載されるように「０」にセットされた接頭語ビット４０４（図４Ａ）が前にある普通記号９０４8を含む。
【０１４６】
普通記号９０４8が送られた後、制御ロジック５００（図５）はさまざまなレジスタを修正する。ステップ６１６（図６）では、制御ロジック５００（図５）が、最後に加えられた長さ５２２（図５）を現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）が「１」にセットされる。ステップ６１７（図６）では、制御ロジック５００（図５）がストリングレジスタ５１２を空にセットする。
【０１４７】
ステップ６２２（図６）では、制御ロジック５００（図５）は、入力ストリング５０２に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１（図６）に続く。
【０１４８】
ストリングレジスタ５１２（図５）は空である。ステップ６０１（図６）では、入力ストリングポインタレジスタ５１４の内容は、依然として、入力ストリング５０２（図５）における記号９０４8を指す。制御ロジック５００は、記号９０４8をストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、ストリングレジスタ５１２（図５）の内容を探索キー５０４（図５）として、コーディングテーブル３００（図５）に送る。コーディングテーブル３００（図５）は、記号９０４8を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４8が辞書３０８（図５）に見つけられる。というのも、記号９０４8が、ステップ６０１〜６２２（図６）を経る先の繰返しにおいて、辞書３０８（図５）に記憶されたからである。
【０１４９】
ステップ６２０（図６）では、制御ロジック５００（図５）が、入力ストリングポインタ５１４を増分して、入力ストリング５０２（図５）における次の記号９０４9を指す。ステップ６２１（図６）では、制御ロジック５００（図５）が記号の数を増分する。ステップ６２２（図６）では、制御ロジック５００（図５）が、エンコードすべきさらなる記号があることを入力ストリング５０２（図５）から判断する。処理がステップ６０１（図６）に続き、入力ストリングポインタは、入力ストリングにおける次の記号９０４9を指し、ストリングレジスタは記号９０４8「b/」を記憶する。
【０１５０】
ステップ６０１（図６）では、制御ロジック５００（図５）が、記号９０４8を、ストリングレジスタ５１２（図５）に記憶されている次の記号９０４9と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、一連の記号「b/we」を探索キー５０４として、コーディングテーブル３００に送る。コーディングテーブル３００は、一連の記号「b/we」を求めて辞書３０８を探索する。ステップ６０４（図６）では、一連の記号「b/we」は見つけられない。ステップ６０６（図６）では、一連の記号「b/we」は、インデックス１３で一連の記号を辞書３０８に記憶することにより学習される。一連の記号は普通には記憶されない。代わりに、一連の記号「b/we」は、その接頭語を指すインデックス１２とともに記憶される。というのも、記号「b/」がインデックス１２で記憶されているからである。一連の記号「b/we」は、インデックス１２として記憶されている「b/」および普通に記憶されている「we」を含む（１２，we）として、インデックス１３で記憶される。ストリングレジスタ５１２（図５）における記号の数は２である。こうして、ステップ６１２（図６）では、制御ロジック５００（図５）は、最後に加えられたストリングにおける、記憶されている記号の最後の数が１であることを判断し、ステップ６１６（図６）では、制御ロジック５００（図５）が、最後に加えられた長さ５２２（図５）を現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）が「１」にセットされる。ステップ６１７（図６）では、制御ロジック５００（図５）は、ストリングレジスタ５１２を空にセットする。
【０１５１】
ステップ６２２では、制御ロジック５００（図５）は、入力ストリング５０２に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１に続く。
【０１５２】
入力ストリングポインタ５１４（図５）の内容は記号９０４9を指す。ストリングレジスタ５１２は空である。ステップ６０１（図６）では、制御ロジックは、入力ストリング５０２（図５）における次の記号９０４9「we」を、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００は、ストリングレジスタ５１２（図５）の内容、すなわち入力ストリング５０２における次の記号９０４9「we」を探索キー５０４（図５）として、コーディングテーブル３００に送る。コーディングテーブル３００（図５）は、記号９０４9を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４9が見つけられる。
【０１５３】
ステップ６２０（図６）では、制御ロジック５００（図５）が入力ストリングポインタ５１４（図５）を増分して、入力ストリング５０２（図５）における次の記号９０４10を指す。ステップ６２１（図６）では、制御ロジック５００（図５）は記号の数を増分する。ステップ６２２（図６）では、制御ロジック５００（図５）は、エンコードすべきさらなる記号があることを、入力ストリング５０２（図５）から判断する。処理がステップ６０１（図６）に続き、入力ストリングポインタは、入力ストリングにおける次の記号９０４10「t/」を指し、ストリングレジスタは記号９０４9「we」を記憶する。
【０１５４】
ステップ６０１（図６）では、制御ロジック５００（図５）が、記号９０４9を、入力ストリング５０２における次の記号９０４10と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、一連の記号「wet/」を探索キー５０４として、コーディングテーブル３００に送る。コーディングテーブル３００は、一連の記号「wet/」を求めて辞書３０８を探索する。ステップ６０４（図６）では、一連の記号「wet/」は見つけられない。ステップ６０６（図６）では、一連の記号「wet/」は、インデックス１４で一連の記号を辞書３０８に記憶することにより学習される。一連の記号は普通には記憶されない。代わりに、一連の記号「wet/」は、その接頭語を指すインデックス９とともに記憶される。というのも、記号「we」がインデックス９で記憶されているからである。一連の記号「wet/」は、インデックス９として既に記憶された「we」および普通に記憶されている「t/」を含む（９，t/）として、インデックス１４で記憶される。ストリングレジスタ５１２（図５）における記号の数は２である。こうして、ステップ６１２（図６）では、制御ロジック５００（図５）は、最後に加えられたストリングにおける記号の最後の数が１ではないことを判断し、ステップ６１４（図６）では、制御ロジック５００（図５）は、エンコードされたストリング３１４（図３）上でコードワード９０６8を送る。コードワード９０６8は、図４Ｂに関連して記載されるように「１」が前にあるインデックス９を含む。ステップ６１６（図６）では、制御ロジック５００（図５）は、最後に加えられた長さ５２２（図５）を、現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）が「１」にセットされる。ステップ６１７（図６）では、制御ロジック５００（図５）がストリングレジスタ５１２を空にセットする。
【０１５５】
ステップ６２２では、制御ロジック５００（図５）が、入力ストリング５０２に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１に続く。
【０１５６】
ストリングポインタレジスタ５１４（図５）の内容は記号９０４10を指す。ストリングレジスタ５１２（図５）は空である。ステップ６０１（図６）では、制御ロジックは、入力ストリング５０２（図５）における次の記号９０４10「t/」を、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００は、ストリングレジスタ５１２（図５）の内容、すなわち入力ストリング５０２にお
ける次の記号９０４10「t/」を探索キー５０４（図５）として、コーディングテーブル３００に送る。コーディングテーブル３００（図５）は、記号９０４10を求めて辞書３０８を探索する。ステップ６０４（図６）では、記号９０４10は見つけられない。ステップ６０６（図６）では、コーディングテーブル３００（図５）が、インデックス１５で記号９０４10を辞書３０８に記憶することにより、記号９０４10を学習し、記号９０４10が学習５０８を通じて学習されていることを示す。ステップ６０８（図６）では、記憶されている記号の数は「１」であり、こうして、処理がステップ６１０（図６）に続く。ステップ６１０（図６）では、制御ロジック５００（図５）は、エンコードされたストリング３１４（図３）上でコードワード９０６9を送り、このためデコーダは記号を学習することができる。コードワード９０６9は、図４Ａに関連して記載されるように「０」にセットされた接頭語ビット４０４（図４Ａ）が前にある普通記号９０４9を含む。
【０１５７】
普通記号９０４10が送られた後、制御ロジック５００（図５）はさまざまなレジスタを修正する。ステップ６１６（図６）では、制御ロジック５００（図５）は、最後に加えられた長さ５２２（図５）を、現在のストリングの長さ５１８（図５）の内容にセットし、現在のストリングの長さ５１８（図５）が「１」にセットされる。ステップ６１７（図６）では、制御ロジック５００（図５）はストリングレジスタ５１２を空にセットする。
【０１５８】
ステップ６２２（図６）では、制御ロジック５００（図５）は、入力ストリング５０２に（ＥＯＳではない）別の有効な記号があることを判断し、処理がステップ６０１に続く。
【０１５９】
ストリングレジスタ５１２（図５）は空である。ステップ６０１（図６）では、入力ストリングポインタレジスタ５１４の内容は、依然として、入力ストリング５０２（図５）における記号９０４10を指す。制御ロジック５００は、記号９０４10を、空であるストリングレジスタ５１２（図５）の内容と連結する。ステップ６０２（図６）では、制御ロジック５００（図５）は、ストリングレジスタ５１２（図５）の内容を探索キー５０４（図５）として、コーディングテーブル３００（図５）に送る。コーディングテーブル３００（図５）は、記号９０４10を求めて辞書３０８（図５）を探索する。ステップ６０４（図６）では、記号９０４10が辞書３０８（図５）に見つけられる。というのも、記号９０４10が、ステップ６０１〜６２２（図６）を経る先の繰返しにおいて、辞書３０８（図５）に記憶されたからである。
【０１６０】
ステップ６２０（図６）では、制御ロジック５００（図５）が入力ストリングポインタ５１４を増分して、入力ストリング５０２（図５）における次の記号を指す。ステップ６２１（図６）では、制御ロジック５００（図５）が記号の数を増分する。
【０１６１】
ステップ６２２（図６）では、制御ロジックがストリングの終わりを検出する。処理はステップ６２４（図６）に続く。
【０１６２】
ステップ６２４（図６）では、制御ロジック５００（図５）が、コードワード９０６10におけるストリングの終わりのためにインデックスを送る。
【０１６３】
ストリングの終わりを除く１０個の記号を含む入力ストリングは、各記号９０４1〜９０４10が１６ビット幅であると仮定すると、１６０ビット（１０×１６）を必要とする。一連のコードワード９０６1〜９０６10は、伝送されるビットの数を１２０ビットに減らす。１２０ビットは次のように算出される。すなわち、コードワード９０６1、９０６2、９０６4、９０６5、９０６7および９０６9に対して（６×１７）の普通記号、コードワード９０６3におけるインデックス２に対して３ビット、ならびにコードワード９０６6、９０６8および９０６10におけるインデックス８、９および１０に対して５ビットである。
この方法では、アルファベットを記憶するのにより少ない初期メモリですみ、かつ、エンコードされたストリング３１４（図３）を伝送するのにＬＺＷアルゴリズムより少ないビットですむ。記号が学習され、反復または既知のストリングが受取られると、達成される圧縮が向上する。
【０１６４】
エンコードされたデータ３１４の処理は、図８Ａ〜図８Ｂに関連して記載される方法を用いて、デコーダ３１２により行なわれる。
【０１６５】
この発明は、その好ましい実施例に関連して特に例示および記載されてきたが、添付の特許請求の範囲により包含されるこの発明の範囲から逸脱することなく、形状および詳細をこの明細書中でさまざまに変更し得ることを、当業者は理解するであろう。
【図面の簡単な説明】
【０１６６】
【図１】無損失データ圧縮を実行するための、エンコーダにおいて実現される先行技術のＬＺＷコーディングテーブルと、デコーダにおいて実現されるＬＺＷデコーディングテーブルとを示す図である。
【図２】図１に示される、エンコーダにおける入力ストリングの先行技術のＬＺＷ圧縮を示す図である。
【図３】この発明の原理に従って無損失圧縮を行なうための、エンコーダにおいて実現されるコーディングテーブルと、デコーダにおいて実現されるデコーディングテーブルとを示す図である。
【図４Ａ】図３に示されるエンコーダにより学習される普通記号を伝送するために、エンコーダによって、エンコードされたストリングで伝送されるコードワードを示す図である。
【図４Ｂ】既に学習され、かつ図３に示されるコーディングテーブルおよびデコーディングテーブルに記憶される記号のために、エンコードされたストリングで伝送されるコードワードを示す図である。
【図５】エンコードされたストリングで伝送されるコードワードへと入力ストリングを変換するための、制御ロジックと、図３に示されるエンコーダで実現されるコーディングテーブルとを示す図である。
【図６】入力ストリングをエンコードするための、図５に示される制御ロジックで実行される方法を示すフロー図である。
【図７】インデックス幅および辞書の状態を判断するための、図６におけるステップ６１８で実行されるステップを示すフロー図である。
【図８Ａ】受取られたエンコードされたストリングをデコードするための、図３に示されるデコーダで実現される方法を示すフロー図である。
【図８Ｂ】受取られたエンコードされたストリングをデコードするための、図３に示されるデコーダで実現される方法を示すフロー図である。
【図９】入力ストリングと、入力ストリングの処理後のエンコーダにおける辞書の内容と、エンコードされたストリングとを示す図である。
【図１】
2008092582.tif 000003
【図２】
2008092582.tif 000004
【図３】
2008092582.tif 000005
【図４Ａ】
2008092582.tif 000006
【図４Ｂ】
2008092582.tif 000007
【図５】
2008092582.tif 000008
【図６】
2008092582.tif 000009
【図７】
2008092582.tif 000010
【図８Ａ】
2008092582.tif 000011
【図８Ｂ】
2008092582.tif 000012
【図９】
2008092582.tif 000013