(57)【要約】ＬＺＷデータ圧縮伸長方法論に基づき、まれに出会う列を保存する除外テーブルを含む、データ圧縮伸長システム。コンプレッサ辞書およびデコンプレッサ辞書の更新のために形成される延長列が、除外テーブルに含まれる場合に、その延長列は、保存されず、コードを辞書列に割り当てるコードカウンタは、進められない。この形で、辞書コードが、まれに出会う列によって奪われない。除外テーブルは、頻繁に出会う列を除外テーブルから削除することと、まれに出会う列を除外テーブルに追加することによって、入力データに従って動的に修正される。
2004525567.tif 000002
【特許請求の範囲】
【請求項１】
データ文字の入力ストリームを圧縮コードの出力ストリームに圧縮するデータ圧縮方法であって、
前記入力ストリームで出会うデータ文字の列を保存手段に保存するステップであって、前記保存された列が、めいめいのコードと関連付けられるステップと、
前記入力ストリームと前記保存された列との最長一致を判定するために、前記入力ストリームを前記保存された列と比較することによって前記入力ストリームを検索するステップと、
圧縮されたコードの前記出力ストリームを提供するために、前記最長一致に関連するコードを出力するステップと、
前記保存手段での保存から除外されるデータ文字の列を保存する除外テーブル構造を設けるステップと、
前記入力ストリーム内で前記最長一致に続く次のデータ文字によって延長された前記最長一致を含む延長列を形成するステップと、
前記延長列が前記除外テーブル構造に含まれるか否かを判定するために、前記延長列を前記除外テーブル構造に保存されたデータ文字の列と比較するステップと、
前記延長列が前記除外テーブル構造に含まれない場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てるステップと、
前記延長列が前記除外テーブル構造に含まれる場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てるステップをバイパスするステップと、
前記除外テーブル構造内の頻繁に出会う列を前記除外テーブル構造から削除し、前記保存手段内のまれに出会う列を前記除外テーブル構造に追加することによって、前記除外テーブル構造の内容を修正するステップと
を含むことを特徴とするデータ圧縮方法。
【請求項２】
前記修正するステップが、
前記除外テーブル構造で列に出会う回数をカウントするステップであって、これによって、前記出会う列の除外テーブル列カウントを提供するステップと、
それに関する前記除外テーブル列カウントが所定の閾値を超える場合に、前記出会う列を前記除外テーブル構造から削除するステップと
を含むことを特徴とする請求項１に記載の圧縮方法。
【請求項３】
前記修正するステップが、
前記保存手段に保存された列に出会う回数をカウントするステップであって、これによって、前記出会う列の保存手段列カウントを提供するステップと、
それに関する前記保存手段列カウントが所定の閾値未満である場合に、前記出会う列を前記除外テーブル構造に保存するステップと
を含むことを特徴とする請求項１に記載の圧縮方法。
【請求項４】
前記修正するステップが、さらに、
前記延長列が前記保存手段に保存される場合に、１である前記延長列の保存手段列カウントを提供するステップ
を含むことを特徴とする請求項３に記載の圧縮方法。
【請求項５】
前記検索するステップが、一致しない入力データ文字が発生するまで前記入力ストリームを前記保存された列と比較し、これによって、前記最長一致を判定する、比較するステップを含み、
前記一致しない文字が単一文字列として前記除外テーブル構造に含まれるか否かを判定するステップと、
前記一致しない文字が単一文字列として前記除外テーブル構造に含まれない場合に、最長一致に関する次の列検索を開始するのに前記一致しない文字を使用するステップと、
前記一致しない文字が単一文字列として前記除外テーブル構造に含まれる場合に、前記一致しない文字を出力し、単一文字列として前記除外テーブル構造に含まれない入力データ文字を取り出すまで、さらなる入力データ文字を出力するステップと、
最長一致に関する次の列検索を開始するのに、単一文字列として前記除外テーブル構造に含まれない前記取り出された入力データ文字を使用するステップと
をさらに含むことを特徴とする請求項１に記載の圧縮方法。
【請求項６】
前記修正するステップが、
前記除外テーブル構造内の単一文字列に出会う回数をカウントするステップであって、これによって、前記単一文字列に関する除外テーブル列カウントを提供するステップと、
それに関する前記除外テーブル列カウントが所定の閾値を超える場合に、単一文字列を前記除外テーブル構造から削除するステップと
を含むことを特徴とする請求項５に記載の圧縮方法。
【請求項７】
前記修正するステップが、
前記単一文字列が前記除外テーブル構造に含まれないと判定される回数をカウントするステップであって、これによって、前記単一文字列の保存手段列カウントを提供するステップと、
それに関する前記保存手段列カウントが所定の閾値未満である場合に、前記単一文字列を前記除外テーブル構造に保存するステップと
を含むことを特徴とする請求項６に記載の圧縮方法。
【請求項８】
前記保存手段が、その所定の容量でデータ文字の列を保存している場合に、前記修正するステップを実行するステップ
をさらに含むことを特徴とする請求項１に記載の圧縮方法。
【請求項９】
前記所定の容量が、最大容量を含むことを特徴とする請求項８に記載の圧縮方法。
【請求項１０】
コードカウンタが、前記保存手段に保存された前記列に関連する前記めいめいのコードを割り当て、さらに、
前記コードカウンタからのオーバーフローを検出した後に、前記修正するステップを実行するステップ
を含むことを特徴とする請求項９に記載の圧縮方法。
【請求項１１】
除外テーブル構造を設ける前記ステップが、それぞれ単一文字列、２文字列、後続の長さの列、および所定の列長限度を有する列までを保存する複数の除外テーブルを設けるステップを含み、
さらに、前記延長列の文字の数をカウントするステップを含み、
前記比較するステップが、前記延長列を、前記延長列と同一の文字数を有する列を保存している除外テーブルに保存された列と比較するステップを含む
ことを特徴とする請求項１に記載の圧縮方法。
【請求項１２】
前記延長列の文字数をカウントする前記ステップが、その保存された列文字カウントを提供し、
前記修正するステップが、前記保存された列文字カウントに従って、列を前記複数の除外テーブルに追加するステップを含む
ことを特徴とする請求項１１に記載の圧縮方法。
【請求項１３】
列長限度を設けるステップと、
前記延長列の文字数をカウントするステップと、
前記延長列の前記文字数が前記列長限度を超える場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てるステップをバイパスするステップと
をさらに含むことを特徴とする請求項１に記載の圧縮方法。
【請求項１４】
前記延長列の文字数が前記列長限度を超える場合に、前記延長列の文字が、互いに関して同一であるか否かを判定するステップと、
前記延長列の前記文字数が、前記列長限度を超え、前記延長列の前記文字が、互いに関して同一である場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てるステップと
をさらに含むことを特徴とする請求項１３に記載の圧縮方法。
【請求項１５】
前記保存手段からの除外に関してデータ文字列を前記複数の除外テーブルに移植する方法をさらに含み、該方法は、
それに対して圧縮が実行される、データ文字の前記入力ストリームを表すデータ文字の本体を提供するステップと、
複数のリンクリストデータツリーを確立するステップであって、各ツリーが、圧縮が実行されるアルファベットのめいめいの文字を表すルートノードから始まり、各前記ルートノードがカウンタをそれに関連付けられるステップと
を含み、前記複数のデータツリーが、リンクされた子孫ノードの複数のチェーンを含み、前記チェーンが、前記ルートノードにリンクされ、各子孫ノードが、カウンタをそれに関連付けられ、前記移植する方法が、
各データ文字列を、前記データ文字の本体から前記複数のデータツリーに、前記列長限度まで読み取り、ルートノードおよび各前記列のめいめいの文字の子孫ノードのリンクされたチェーンを設け、関連する文字に出会うたびに各ノードカウンタを増分するステップと、
前記複数のデータツリーの列に関連するノードのノードカウンタが、所定の閾値未満のカウントを含む場合に、前記複数の除外テーブルの１つへの移植のために前記複数のデータツリーから前記列を選択するステップと
を含むことを特徴とする請求項１１に記載の圧縮方法。
【請求項１６】
前記データツリーが、レベルに配置され、前記ルートノードが第１レベルにあり、前記ルートノードの子孫ノードが第２レベルにあり、連続する子孫ノードが、前記列長限度に対応するレベルまでのめいめいの連続するレベルにあり、
単一文字列の前記除外テーブルへの移植のために前記第１レベルのノードから列を選択し、２文字列の前記除外テーブルへの移植のために前記第２レベルのノードから列を選択し、次の長さの列の前記除外テーブルへの移植のために前記めいめいの次のレベルのノードから列を選択し、前記列長限度の列の前記除外テーブルへの移植のために前記列長限度に対応する前記レベルのノードから列を選択する
ことを特徴とする請求項１５に記載の圧縮方法。
【請求項１７】
圧縮コードの入力ストリームをそれに対応するデータ文字の回復された出力ストリームに伸長するデータ伸長方法であって、前記伸長方法が、伸長サイクルで動作し、
前記圧縮コードに対応する列から導出されたデータ文字の列を保存手段に保存するステップであって、前記保存される列が、めいめいのコードと関連付けられるステップと、
入力圧縮コードを現在の伸長サイクルで取り出し、これによって、現在コードを提供する、取り出すステップと、
データ文字の前記回復された出力ストリームを提供するために、前記現在コードに対応する列を出力するステップと、
前記現在の伸長サイクルに先立つ伸長サイクルで取り出されたコードに対応する前コードを提供するステップと、
前記保存手段での保存から除外されるデータ文字の列を保存する除外テーブル構造を設けるステップと、
前記現在コードに対応する前記列の最初のデータ文字によって延長された前記前コードに対応する列を含む延長列を形成するステップと、
前記延長列が前記除外テーブル構造に含まれるか否かを判定するために、前記延長列を前記除外テーブル構造に保存されたデータ文字の列と比較するステップと、
前記延長列が前記除外テーブル構造に含まれない場合に、前記保存手段に前記延長列を保存し、対応するコードを前記保存された延長列に割り当てるステップと、
前記延長列が前記除外テーブル構造に含まれる場合に、前記保存手段に前記延長列を保存し、対応するコードを前記保存された延長列に割り当てる前記ステップをバイパスするステップと、
前記前コードに前記現在コードをセットするステップと、
取り出された現在コードに応答して、前記伸長サイクル中に、前記除外テーブル構造内の頻繁に出会う列を前記除外テーブル構造から削除し、前記保存手段内のまれに出会う列を前記除外テーブル構造に追加することによって、前記除外テーブル構造の内容を修正するステップと
を含むことを特徴とする伸長方法。
【請求項１８】
前記修正するステップが、
前記除外テーブル構造内の列に出会う回数をカウントするステップであって、これによって、前記出会う列の除外テーブル列カウントを提供するステップと、
それに関する前記除外テーブル列カウントが所定の閾値を超える場合に、前記出会う列を前記除外テーブルから削除するステップと
を含むことを特徴とする請求項１７に記載の伸長方法。
【請求項１９】
前記修正するステップが、
前記保存手段に保存された列に出会う回数をカウントするステップであって、これによって、前記出会う列の保存手段列カウントを提供するステップと、
それに関する前記保存手段列カウントが所定の閾値を超える場合に、前記出会う列を前記除外テーブル構造に保存するステップと
を含むことを特徴とする請求項１７に記載の伸長方法。
【請求項２０】
前記修正するステップが、さらに、
前記延長列が前記保存手段に保存される場合に、前記延長列に関して１の保存手段列カウントを提供するステップ
をさらに含むことを特徴とする請求項１９に記載の伸長方法。
【請求項２１】
前記現在コードが、前記保存手段に保存された複数文字列を表すか否かを判定するステップと、
前記現在コードが、前記保存手段に保存された複数文字列を表す場合に、前記保存手段から、前記現在コードに対応する前記列の文字を回復するステップと
をさらに含み、前記出力するステップが、データ文字の前記回復された出力ストリームを提供するために、前記現在コードに対応する前記列の前記文字を出力するステップを含む
ことを特徴とする請求項１９に記載の伸長方法。
【請求項２２】
前記修正するステップが、
前記複数文字列およびその各プレフィックス列に前記保存手段で出会う回数をカウントするために、前記複数文字列およびその各プレフィックス列の保存手段列カウントを維持するステップと、
それに関する前記保存手段列カウントが所定の閾値より小さい場合に、各前記出会う列を前記除外テーブル構造に保存するステップと、
を含むことを特徴とする請求項２１に記載の伸長方法。
【請求項２３】
前記現在コードが単一文字列を表すか否かを判定するステップ
をさらに含み、前記現在コードが単一文字列を表す場合に、
前記形成するステップが、前記単一文字列の文字によって延長された、前記前コードに対応する前記列を含む延長列を形成するステップを含み、
前記出力するステップが、データ文字の前記回復された出力ストリームを提供するために、前記単一文字列の前記文字を出力するステップを含む
ことを特徴とする請求項１７に記載の伸長方法。
【請求項２４】
（ａ）前記単一文字列が前記除外テーブル構造に含まれるか否かを判定するために、前記単一文字列を前記除外テーブル構造に保存されたデータ文字の前記列と比較するステップと、
（ｂ）前記単一文字列が、前記除外テーブル構造に含まれない場合に、前記前コードに前記現在コードをセットする前記ステップを実行し、次の伸長サイクルに進むステップと、
（ｃ）前記単一文字列が、前記除外テーブル構造に含まれる場合に、次の入力圧縮コードを取り出すステップと、
（ｄ）前記次に取り出された入力圧縮コードが、前記除外テーブル構造に含まれる単一文字列を表す場合に、前記除外テーブル構造に含まれる前記単一文字列の文字を出力し、次の入力圧縮コードを取り出し、ステップ（ｄ）を繰り返すステップと、
（ｅ）前記次に取り出された入力圧縮コードが、前記除外テーブル構造に含まれない単一文字列を表す場合に、前記除外テーブル構造に含まれない前記単一文字列の文字を出力し、前記前コードに、前記除外テーブル構造に含まれない前記単一文字列を表す前記取り出された入力圧縮コードをセットし、前記次の伸長サイクルに進むステップと
をさらに含み、前記次に取り出された入力圧縮コードが、複数文字列を表す場合に、前記伸長方法が、前記次の伸長サイクルに進むのに先立つ、
（ｆ）前記保存手段から、前記複数文字列の文字を回復するステップと、
（ｇ）データ文字の前記回復された出力ストリームを提供するために、前記複数文字列の前記文字を出力するステップと、
（ｈ）前記前コードに、前記複数文字列を表す前記取り出された入力圧縮コードをセットするステップと
を含むことを特徴とする請求項２３に記載の伸長方法。
【請求項２５】
前記修正するステップが、
前記除外テーブル構造内の単一文字列に出会う回数をカウントするステップであって、これによって、前記単一文字列の除外テーブル列カウントを提供するステップと、
それに関する前記除外テーブル列カウントが所定の閾値を超える場合に、単一文字列を前記除外テーブル構造から削除するステップと
を含むことを特徴とする請求項２４に記載の伸長方法。
【請求項２６】
前記修正するステップが、
前記単一文字列が、前記除外テーブル構造に含まれないと判定される回数をカウントするステップであって、これによって、前記単一文字列の保存手段列カウントを提供するステップと、
それに関する前記保存手段列カウントが所定の閾値未満である場合に、前記単一文字列を前記除外テーブル構造に保存するステップと
を含むことを特徴とする請求項２５に記載の伸長方法。
【請求項２７】
前記修正するステップが、
前記複数文字列およびその各プレフィックス列に前記保存手段で出会う回数をカウントするために、前記複数文字列およびその各プレフィックス列について保存手段列カウントを維持するステップと、
それに関する前記保存手段列カウントが所定の閾値より小さい場合に、各前記出会う列を前記除外テーブルに保存するステップと
を含むことを特徴とする請求項２４に記載の伸長方法。
【請求項２８】
前記現在コードが、前記保存手段に保存されていない複数文字列を表すか否かを判定するステップと、
前記現在コードが、前記保存手段に保存されていない複数文字列を表す場合に、
前記前コードに対応する前記列の最初のデータ文字によって延長された、前記前コードに対応する前記列を含む例外事例列を形成するステップと、
前記例外事例列を前記保存手段に保存するステップと、
当該保存された例外事例列に対応するコードを割り当てるステップと
によって例外事例処理を実行するステップと
をさらに含み、前記出力するステップが、データ文字の前記回復された出力ストリームを提供するために、前記例外事例列の文字を出力するステップを含み、
前記セットするステップが、前記保存手段に含まれない前記列を表す前記現在コードを、前記前コードにセットするステップを含む
ことを特徴とする請求項１７に記載の伸長方法。
【請求項２９】
前記修正するステップが、
前記例外事例列およびその各プレフィックス列に前記保存手段で出会う回数をカウントするために、前記例外事例列およびその各プレフィックス列の保存手段列カウントを維持するステップと、
それに関する前記保存手段列カウントが所定の閾値より小さい場合に、各前記出会う列を前記除外テーブル構造に保存するステップと
を含むことを特徴とする請求項２８に記載の伸長方法。
【請求項３０】
次の伸長サイクルで使用される例外事例列カウントを提供するステップをさらに含み、該ステップは、
前記前コードに対応する前記列の文字のカウントを提供するステップと、
前記前コードに対応する前記列の前記文字の前記カウントに１を加算するステップであって、これによって、前記例外事例列カウントを提供するステップと
を含むことを特徴とする請求項２８に記載の伸長方法。
【請求項３１】
前記保存手段が、その所定の容量でデータ文字の列を保存している場合に、前記修正するステップを実行するステップ
をさらに含むことを特徴とする請求項１７に記載の伸長方法。
【請求項３２】
前記所定の容量が、最大容量を含むことを特徴とする請求項３１に記載の伸長方法。
【請求項３３】
コードカウンタが、前記保存手段に保存された前記列に関連する前記めいめいのコードを割り当て、
前記コードカウンタからのオーバーフローを検出した後に前記修正するステップを実行するステップ
をさらに含むことを特徴とする請求項３２に記載の伸長方法。
【請求項３４】
除外テーブル構造を設ける前記ステップが、それぞれ単一文字列、２文字列、後続の長さの列、および所定の列長限度を有する列までを保存する複数の除外テーブルを設けるステップを含み、
前記延長列の文字の数のカウントを提供するステップであって、これによって、保存された列文字カウントを提供するステップを含み、
前記比較するステップが、前記延長列を、前記延長列と同一の文字数を有する列を保存している除外テーブルに保存された列と比較するステップをさらに含む
ことを特徴とする請求項１７に記載の伸長方法。
【請求項３５】
前記修正するステップが、前記保存された列文字カウントに従って、列を前記複数の除外テーブルに追加するステップを含むことを特徴とする請求項３４に記載の伸長方法。
【請求項３６】
列長限度を設けるステップと、
前記延長列の文字数のカウントを提供するステップと、
前記延長列の前記文字数が前記列長限度を超える場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てるステップをバイパスするステップと
をさらに含むことを特徴とする請求項１７に記載の伸長方法。
【請求項３７】
前記延長列の文字数が前記列長限度を超える場合に、前記延長列の文字が、互いに関して同一であるか否かを判定するステップと、
前記延長列の前記文字数が、前記列長限度を超え、前記延長列の前記文字が、互いに関して同一である場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てるステップと
をさらに含むことを特徴とする請求項３６に記載の伸長方法。
【請求項３８】
前記延長列の文字の数のカウントを提供するステップが、
前記前コードに対応する列の文字数のカウントを提供するステップと、
前記前コードに対応する前記列の文字数の前記カウントを１つ増分し、これによって、前記延長列の文字数の前記カウントを提供するステップと
を含むことを特徴とする請求項３４に記載の伸長方法。
【請求項３９】
データ文字の入力ストリームを圧縮コードの出力ストリームに圧縮するデータ圧縮装置であって、
前記入力ストリームで出会うデータ文字の列を保存する保存手段であって、前記保存された列が、めいめいのコードと関連付けられる保存手段と、
前記入力ストリームと前記保存された列との最長一致を判定するために、前記入力ストリームを前記保存された列と比較することによって前記入力ストリームを検索する手段と、
圧縮されたコードの前記出力ストリームを提供するために、前記最長一致に関連するコードを出力する手段と、
前記保存手段での保存から除外されるデータ文字の列を保存する除外テーブル構造と、
前記入力ストリーム内で前記最長一致に続く次のデータ文字によって延長された前記最長一致を含む延長列を形成する手段と、
前記延長列が前記除外テーブル構造に含まれるか否かを判定するために、前記延長列を前記除外テーブル構造に保存されたデータ文字の列と比較する手段と、
前記延長列が前記除外テーブル構造に含まれない場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てる手段と、
前記延長列が前記除外テーブル構造に含まれる場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てることをバイパスする手段と、
前記除外テーブル構造内の頻繁に出会う列を前記除外テーブル構造から削除し、前記保存手段内のまれに出会う列を前記除外テーブル構造に追加することによって、前記除外テーブル構造の内容を修正する手段と
を含むことを特徴とするデータ圧縮装置。
【請求項４０】
前記修正する手段が、
前記除外テーブル構造内の列に出会う回数をカウントし、これによって、前記出会う列の除外テーブル列カウントを提供する、カウントする手段と、
それに関する前記除外テーブル列カウントが所定の閾値を超える場合に、前記出会う列を前記除外テーブル構造から削除する手段と
を含むことを特徴とする請求項３９に記載のデータ圧縮装置。
【請求項４１】
前記修正する手段が、
前記保存手段に保存された列に出会う回数をカウントし、これによって、前記出会う列の保存手段列カウントを提供する、カウントする手段と、
それに関する前記保存手段列カウントが所定の閾値未満である場合に、前記出会う列を前記除外テーブル構造に保存する手段と
を含むことを特徴とする請求項３９に記載のデータ圧縮装置。
【請求項４２】
前記修正する手段が、さらに、
前記延長列が前記保存手段に保存される場合に、１である前記延長列の保存手段列カウントを提供する手段
を含むことを特徴とする請求項４１に記載のデータ圧縮装置。
【請求項４３】
前記検索する手段が、一致しない入力データ文字が発生するまで前記入力ストリームを前記保存された列と比較する手段であって、これによって、前記最長一致を判定する手段を含み、
前記装置が、さらに、
前記一致しない文字が単一文字列として前記除外テーブル構造に含まれるか否かを判定する手段と、
前記一致しない文字が単一文字列として前記除外テーブル構造に含まれない場合に、最長一致に関する次の列検索を開始するのに前記一致しない文字を使用する手段と、
前記一致しない文字が単一文字列として前記除外テーブル構造に含まれる場合に、前記一致しない文字を出力し、単一文字列として前記除外テーブル構造に含まれない入力データ文字を取り出すまで、さらなる入力データ文字を取り出し、出力するように動作する手段と、
最長一致に関する次の列検索を開始するのに、単一文字列として前記除外テーブル構造に含まれない前記取り出された入力データ文字を使用する手段と
を含むことを特徴とする請求項４２に記載のデータ圧縮装置。
【請求項４４】
前記修正する手段が、
前記除外テーブル構造内で単一文字列に出会う回数をカウントする手段であって、これによって、前記単一文字列に関する除外テーブル列カウントを提供する手段と、
それに関する前記除外テーブル列カウントが所定の閾値を超える場合に、単一文字列を前記除外テーブル構造から削除する手段と
を含むことを特徴とする請求項４３に記載のデータ圧縮装置。
【請求項４５】
前記修正する手段が、
前記単一文字列が前記除外テーブル構造に含まれないと判定される回数をカウントする手段であって、これによって、前記単一文字列の保存手段列カウントを提供する手段と、
それに関する前記保存手段列カウントが所定の閾値未満である場合に、前記単一文字列を前記除外テーブル構造に保存する手段と
を含むことを特徴とする請求項４３に記載のデータ圧縮装置。
【請求項４６】
前記修正する手段が、前記保存手段がその所定の容量でデータ文字の列を保存している場合に、前記除外テーブル構造の内容を修正するように動作することを特徴とする請求項３９に記載のデータ圧縮装置。
【請求項４７】
前記所定の容量が、最大容量を含むことを特徴とする請求項４６に記載のデータ圧縮装置。
【請求項４８】
前記保存手段に保存された前記列に関連するめいめいのコードを割り当てるコードカウンタをさらに含み、前記修正する手段が、前記コードカウンタからのオーバーフローを検出した後に、前記除外テーブル構造の内容を修正するように動作することを特徴とする請求項４７に記載のデータ圧縮装置。
【請求項４９】
前記除外テーブル構造が、それぞれ単一文字列、２文字列、後続の長さの列、および所定の列長限度を有する列までを保存する複数の除外テーブルを含み、
前記装置が、さらに、前記延長列の文字の数をカウントし、これによってそれに関する保存された列文字カウントを提供する、カウントする手段を含み、
前記比較する手段が、前記延長列を、前記延長列と同一の文字数を有する列を保存している除外テーブルに保存された列と比較する手段を含む
ことを特徴とする請求項３９に記載のデータ圧縮装置。
【請求項５０】
前記修正する手段が、前記保存された列文字カウントに従って、列を前記複数の除外テーブルに追加するように動作することを特徴とする請求項４９に記載のデータ圧縮装置。
【請求項５１】
列長限度を設ける手段と、
前記延長列の文字数をカウントする手段と、
前記延長列の前記文字数が前記列長限度を超える場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てることをバイパスする手段と
をさらに含むことを特徴とする請求項３９に記載のデータ圧縮装置。
【請求項５２】
前記延長列の文字数が前記列長限度を超える場合に、前記延長列の文字が、互いに関して同一であるか否かを判定する手段と、
前記延長列の前記文字数が、前記列長限度を超え、前記延長列の前記文字が、互いに関して同一である場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てる手段と
をさらに含むことを特徴とする請求項５１に記載のデータ圧縮装置。
【請求項５３】
圧縮コードの入力ストリームをそれに対応するデータ文字の回復された出力ストリームに伸長するデータ伸長装置であって、該伸長装置は、伸長サイクルで動作し、
前記圧縮コードに対応する列から導出されたデータ文字の列を保存する保存手段であって、前記保存される列が、めいめいのコードと関連付けられる保存手段と、
入力圧縮コードを現在の伸長サイクルで取り出し、これによって、現在コードを提供する、取り出す手段と、
データ文字の前記回復された出力ストリームを提供するために、前記現在コードに対応する列を出力する手段と、
前記現在の伸長サイクルに先立つ伸長サイクルで取り出されたコードに対応する前コードを提供する手段と、
前記保存手段での保存から除外されるデータ文字の列を保存する除外テーブル構造と、
前記現在コードに対応する前記列の最初のデータ文字によって延長された前記前コードに対応する列を含む延長列を形成する手段と、
前記延長列が前記除外テーブル構造に含まれるか否かを判定するために、前記延長列を前記除外テーブル構造に保存されたデータ文字の列と比較する手段と、
前記延長列が前記除外テーブル構造に含まれない場合に、前記保存手段に前記延長列を保存し、前記保存された延長列に対応するコードを割り当てる手段と、
前記延長列が前記除外テーブル構造に含まれる場合に、前記保存手段に前記延長列を保存し、前記保存された延長列に対応するコードを割り当てることをバイパスする手段と、
前記前コードに前記現在コードをセットする手段と、
取り出された現在コードに応答して、前記伸長サイクル中に、前記除外テーブル構造内の頻繁に出会う列を前記除外テーブル構造から削除することと、前記保存手段内のまれに出会う列を前記除外テーブル構造に追加することとによって、前記除外テーブル構造の内容を修正する手段と
を含むことを特徴とする伸長装置。
【請求項５４】
前記修正する手段が、
前記除外テーブル構造の列に出会う回数をカウントする手段であって、これによって、前記出会う列の除外テーブル列カウントを提供する手段と、
それに関する前記除外テーブル列カウントが所定の閾値を超える場合に、前記出会う列を前記除外テーブル構造から削除する手段と
を含むことを特徴とする請求項５３に記載の伸長装置。
【請求項５５】
前記修正する手段が、
前記保存手段に保存された列に出会う回数をカウントし、これによって、前記出会う列の保存手段列カウントを提供する、カウントする手段と、
それに関する前記保存手段列カウントが所定の閾値を超える場合に、前記出会う列を前記除外テーブル構造に保存する手段と
を含むことを特徴とする請求項５３に記載の伸長装置。
【請求項５６】
前記修正する手段が、さらに、
前記延長列が前記保存手段に保存される場合に、前記延長列に関して１の保存手段列カウントを提供する手段
をさらに含むことを特徴とする請求項５５に記載の伸長装置。
【請求項５７】
前記現在コードが、前記保存手段に保存された複数文字列を表すか否かを判定する手段と、
前記現在コードが、前記保存手段に保存された複数文字列を表す場合に、前記保存手段から、前記現在コードに対応する前記列の文字を回復するように動作する手段と
をさらに含み、前記出力する手段が、データ文字の前記回復された出力ストリームを提供するために、前記現在コードに対応する前記列の前記文字を出力する手段を含む
ことを特徴とする請求項５５に記載の伸長装置。
【請求項５８】
前記修正する手段が、
前記複数文字列およびその各プレフィックス列に前記保存手段で出会う回数をカウントするために、前記複数文字列およびその各プレフィックス列の保存手段列カウントを維持する手段と、
それに関する前記保存手段列カウントが所定の閾値より小さい場合に、各前記出会う列を前記除外テーブル構造に保存する手段と、
を含むことを特徴とする請求項５７に記載の伸長装置。
【請求項５９】
前記現在コードが単一文字列を表すか否かを判定する手段
をさらに含み、前記現在コードが単一文字列を表す場合に、
前記形成する手段が、前記単一文字列の文字によって延長された、前記前コードに対応する列を含む延長列を形成するように動作し、
前記出力する手段が、データ文字の前記回復された出力ストリームを提供するために、前記単一文字列の前記文字を出力するように動作する
ことを特徴とする請求項５３に記載の伸長装置。
【請求項６０】
前記単一文字列が前記除外テーブル構造に含まれるか否かを判定するために、前記単一文字列を前記除外テーブル構造に保存されたデータ文字の前記列と比較する手段
をさらに含み、
（ａ）前記単一文字列が、前記除外テーブル構造に含まれない場合に、前記前コードに前記現在コードをセットし、次の伸長サイクルに進み、
（ｂ）前記単一文字列が、前記除外テーブル構造に含まれる場合に、次の入力圧縮コードを取り出し、
（ｃ）前記次に取り出された入力圧縮コードが、前記除外テーブル構造に含まれる単一文字列を表す場合に、前記除外テーブル構造に含まれる前記単一文字列の文字を出力し、次の入力圧縮コードを取り出し、（ｃ）を繰り返し、
（ｄ）前記次に取り出された入力圧縮コードが、前記除外テーブル構造に含まれない単一文字列を表す場合に、前記除外テーブル構造に含まれない前記単一文字列の文字を出力し、前記前コードに、前記除外テーブル構造に含まれない前記単一文字列を表す前記取り出された入力圧縮コードをセットし、前記次の伸長サイクルに進む
ように動作し、前記次に取り出された入力圧縮コードが、複数文字列を表す場合に、前記伸長装置が、前記次の伸長サイクルに進むのに先立って、
（ｅ）前記保存手段から、前記複数文字列の文字を回復することと、
（ｆ）データ文字の前記回復された出力ストリームを提供するために、前記複数文字列の前記文字を出力することと、
（ｇ）前記前コードに、前記複数文字列を表す前記取り出された入力圧縮コードをセットすることと
を実行するように動作することを特徴とする請求項５９に記載の伸長装置。
【請求項６１】
前記修正する手段が、
前記除外テーブル構造内の単一文字列に出会う回数をカウントし、これによって、前記単一文字列の除外テーブル列カウントを提供する、カウントする手段と、
それに関する前記除外テーブル列カウントが所定の閾値を超える場合に、単一文字列を前記除外テーブル構造から削除する手段と
を含むことを特徴とする請求項６０に記載の伸長装置。
【請求項６２】
前記修正する手段が、
前記単一文字列が、前記除外テーブル構造に含まれないと判定される回数をカウントする手段であって、これによって、前記単一文字列の保存手段列カウントを提供する手段と、
それに関する前記保存手段カウントが所定の閾値未満である場合に、前記単一文字列を前記除外テーブル構造に保存する手段と
を含むことを特徴とする請求項６１に記載の伸長装置。
【請求項６３】
前記修正する手段が、
前記複数文字列およびその各プレフィックス列に前記保存手段で出会う回数をカウントするために、前記複数文字列およびその各プレフィックス列について保存手段列カウントを維持する手段と、
それに関する前記保存手段列カウントが所定の閾値より小さい場合に、各前記出会う列を前記除外テーブルに保存する手段と
を含むことを特徴とする請求項６０に記載の伸長装置。
【請求項６４】
前記現在コードが、前記保存手段に保存されていない複数文字列を表すか否かを判定する手段と、
前記現在コードが、前記保存手段に保存されていない複数文字列を表す場合に、
前記前コードに対応する前記列の最初のデータ文字によって延長された、前記前コードに対応する前記列を含む例外事例列を形成することと、
前記例外事例列を前記保存手段に保存することと、
前記保存された例外事例列に対応するコードを割り当てることと
によって例外事例処理を実行するように動作する手段と
をさらに含み、前記出力する手段が、データ文字の前記回復された出力ストリームを提供するために、前記例外事例列の文字を出力する手段を含み、
前記セットする手段が、前記保存手段に含まれない前記列を表す前記現在コードを、前記前コードにセットする手段を含む
ことを特徴とする請求項５３に記載の伸長装置。
【請求項６５】
前記修正する手段が、
前記例外事例列およびその各プレフィックス列に前記保存手段で出会う回数をカウントするために、前記例外事例列およびその各プレフィックス列の保存手段列カウントを維持する手段と、
それに関する前記保存手段列カウントが所定の閾値より小さい場合に、各前記出会う列を前記除外テーブル構造に保存する手段と
を含むことを特徴とする請求項６４に記載の伸長装置。
【請求項６６】
次の伸長サイクルで使用される例外事例列カウントを提供する手段をさらに含み、該手段は、
前記前コードに対応する前記列の文字のカウントを提供する手段と、
前記前コードに対応する前記列の前記文字の前記カウントに１を加算する手段であって、これによって、前記例外事例列カウントを提供する手段と
を含むことを特徴とする請求項６４に記載の伸長装置。
【請求項６７】
前記修正手段が、前記保存手段がその所定の容量でデータ文字の列を保存している場合に、前記除外テーブル構造の内容を修正するように動作することを特徴とする請求項５３に記載の伸長装置。
【請求項６８】
前記所定の容量が、最大容量を含むことを特徴とする請求項６７に記載の伸長装置。
【請求項６９】
前記保存手段に保存された前記列に関連する前記めいめいのコードを割り当てるコードカウンタをさらに含み、前記修正する手段が、前記コードカウンタからのオーバーフローを検出した後に前記除外テーブル構造の内容を修正するように動作することを特徴とする請求項６８に記載の伸長装置。
【請求項７０】
前記除外テーブル構造が、それぞれ単一文字列、２文字列、後続の長さの列、および所定の列長限度を有する列までを保存する複数の除外テーブルを含み、
前記装置が、さらに、前記延長列の文字の数のカウントを提供する手段であって、これによって、保存された列文字カウントを提供する手段を含み、
前記比較する手段が、前記延長列を、前記延長列と同一の文字数を有する列を保存している除外テーブルに保存された列と比較する手段を含む
ことを特徴とする請求項５３に記載の伸長装置。
【請求項７１】
前記修正する手段が、前記保存された列文字カウントに従って、列を前記複数の除外テーブルに追加する手段を含むことを特徴とする請求項７０に記載の伸長装置。
【請求項７２】
列長限度を設ける手段と、
前記延長列の文字数のカウントを提供する手段と、
前記延長列の前記文字数が前記列長限度を超える場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てることをバイパスする手段と
をさらに含むことを特徴とする請求項５３に記載の伸長装置。
【請求項７３】
前記延長列の文字数が前記列長限度を超える場合に、前記延長列の文字が、互いに関して同一であるか否かを判定する手段と、
前記延長列の前記文字数が、前記列長限度を超え、前記延長列の前記文字が、互いに関して同一である場合に、前記延長列を前記保存手段に保存し、前記保存された延長列に対応するコードを割り当てる手段と
をさらに含むことを特徴とする請求項７２に記載の伸長装置。
【請求項７４】
前記延長列の文字の数のカウントを提供する手段が、
前記前コードに対応する列の文字数のカウントを提供する手段と、
前記前コードに対応する前記列の文字数の前記カウントを１つ増分する手段であって、これによって、前記延長列の文字数の前記カウントを提供する手段と
を含むことを特徴とする請求項７０に記載の伸長装置。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
２０００年１０月１６日出願の米国特許出願第０９／６８８，６０４号は、まれに出会う列の組込みフィルタリングを有するデータ圧縮伸長の方法および装置に関する。前記米国特許出願第０９／６８８，６０４号は、参照によって本明細書に組み込まれる。
【０００２】
本発明は、ＬＺデータ圧縮伸長システム、特に、コンプレッサ（ｃｏｍｐｒｅｓｓｏｒ）辞書およびデコンプレッサ（ｄｅｃｏｍｐｒｅｓｓｏｒ）辞書内のまれに出会うデータ文字列（ｃｈａｒａｃｔｅｒ  ｓｔｒｉｎｇ）の保存（保管）を防ぐことに関するＬＺデータ圧縮伸長システムに関する。具体的には、本発明は、入力データで出会う列（ｓｔｒｉｎｇ）に従って除外される列の動的な適応に関する。
【背景技術】
【０００３】
Ａｂｒａｈａｍ  Ｌｅｍｐｅｌ教授およびＪａｃｏｂ  Ｚｉｖ教授が、現在広く使用されているＬＺデータ圧縮伸長システムの理論的基礎を提供した。彼らの根本の２つの論文は、非特許文献１および非特許文献２に記載された。ＬＺＷと称する、Ｖ．４２ｂｉｓモデム圧縮伸長の標準規格として採用された、いたるところで使用されているデータ圧縮伸長システムが、発明人Welch、1985年１２月１０日発行の特許文献１で説明されている。ＬＺＷは、ＧＩイメージ通信プロトコルで使用される圧縮伸長標準規格として採用され、ＴＩＦＦイメージ通信プロトコルで使用される。ＧＩＦは、ＣｏｍｐｕＳｅｒｖｅ  Ｉｎｃｏｒｐｏｒａｔｅｄ社の開発であり、ＧＩＦの名前は、そのサービスマークである。ＧＩＦ仕様の文献は、非特許文献３がある。ＴＩＦＦは、Ａｌｄｕｓ  Ｃｏｒｐｏｒａｔｉｏｎ社の開であり、ＴＩＦＦの名前は、商標である。ＴＩＦＦ仕様書の文献は、非特許文献４がある。
【０００４】
ＬＺ辞書ベース圧縮伸長システムのさらなる例が、発明人Eastman et al.、1984年８月７日発行の特許文献２、発明人Miller et al.、1989年３月２１日発行の特許文献３、発明人Storer、1989年１０月２４日発行の特許文献４、発明人Clark,、1992年１０月６日発行の特許文献５、発明人Lempel et al.、1994年１２月１３日発行の特許文献６、発明人Cooper,、1998年９月１７日発行の特許文献７、発明人Welch et al.、1999年１月１９日発行の特許文献８、発明人Reynar et al.、1999年９月１４日発行の特許文献９で説明されている。
【０００５】
上述の辞書ベースＬＺ圧縮伸長システムでは、コンプレッサ辞書およびデコンプレッサ辞書を、文字アルファベットのすべての一文字だけの列（以下、単一文字列）によって初期化することができる。いくつかの実施形態で、単一文字列が、保存されていることは明示していないが、認識されたとみなすことにする。そのようなシステムでは、単一文字の値を、そのコードとして使用することができ、複数文字の列に使用される最初の使用可能なコードが、単一文字の値より大きい値を有する。この形で、デコンプレッサによって、単一文字列と複数文字列を区別し、その文字自体を回復(復元)することができる。たとえば、ＡＳＣＩＩ環境で、アルファベットは、２５６文字のアルファベットをサポートする８ビット文字サイズを有する。したがって、文字は、０から２５５までの値を有する。最初に使用可能な複数文字の列のコードは、たとえば、２５８とすることができ、ここで、コード２５６および２５７は、周知の通り、制御コードとして使用される。
【０００６】
従来技術の辞書ベースＬＺ圧縮伸長システムでは、特定の方法論で、辞書を固定サイズに制限する必要があることがしばしばである。たとえば、ＧＩＦプロトコルでは、辞書が、最大４０９５個の列に制限され、１２ビットの最大コードサイズが付随する。最大容量まで満たされた場合に、辞書内容をクリアすることが望ましくなるまで、辞書を凍結し、現存の保存された列を使用してさらなる圧縮を行うことができる。
【０００７】
ＬＺ方法論の動作中に、辞書は、データ文字列および列断片が充てんされ、このデータ文字列および文字列断片の一部は、まれにのみ出会う可能性がある。したがって、複数の使用可能なコードが、あるとしてもごくまれに出会う可能性がある列断片によって占められる可能性がある。そのように占められるコードは、入力データ文字ストリームの圧縮に大きくは貢献しない。上で説明したように、辞書は、サイズが制限される場合があるので、これらのまれに出会う列断片によって占められる使用可能コードの数は、重要になる可能性があり、これが、圧縮効率に悪影響を及ぼすと思われる。
【０００８】
まれに出会う列を辞書から除外することによって、圧縮性能が改善されると思われる。さらに、データ圧縮／伸長技術には、まれに出会う列を、辞書に保存されることおよび貴重な辞書コードを占有することから特に除外する方法または装置は存在しないと思われる。まれに発生するデータ文字列が、圧縮辞書および伸長辞書内の貴重なコードを占有しないようにするデータ圧縮伸長システムが開示されており（たとえば、特許文献１０参照）、その実施形態は、静的除外テーブルの使用に関して説明される。
【０００９】
【特許文献１】
米国特許第４，５５８，３０２号明細書
【特許文献２】
米国特許第４，４６４，６５０号明細書
【特許文献３】
米国特許第４，８１４，７４６号明細書
【特許文献４】
米国特許第４，８７６，５４１号明細書
【特許文献５】
米国特許第５，１５３，５９１号明細書
【特許文献６】
米国特許第５，３７３，２９０号明細書
【特許文献７】
米国特許第５，８３８，２６４号明細書
【特許文献８】
米国特許第５，８６１，８２７号明細書
【特許文献９】
米国特許第５，９５１，６２３号明細書
【特許文献１０】
米国特許出願第０９／６８８，６０４号
【特許文献１１】
米国特許第６，１７２，６２４号明細書
【非特許文献１】
IEEE Transactions on Information Theory, IT-23-3, May 1977, pp. 337-343
【非特許文献２】
IEEE Transactions on Information Theory, IT-24-5, September 1978, pp. 530-536
【非特許文献３】
GRAPHICS INTERCHANGE FORMAT, Version 89a, 31 July, 1990
【非特許文献４】
TIFF, Revision 6.0, Final - June 3, 1992
【非特許文献５】
Marcus et. al.、「Building a Large Annotated Corpus of English: The Penn Treebank」、Computational Linguistics, Vol. 19、No. 2、313〜330頁（１９９３年）
【非特許文献６】
G. Zipf、「Human Behavior and the Principle of Least Effort」、１９４９年
【発明の開示】
【発明が解決しようとする課題】
【００１０】
事前に充てんされた辞書が、データ固有辞書と組み合わせて使用される例があり、この事前に充てんされた辞書は、一般的に発生する文字シーケンスを事前にロードされる（たとえば、特許文献９参照）。データ固有辞書は、通常のＬＺ圧縮モードで使用され、事前に充てんされる辞書またはデータ固有辞書のいずれかからの最長一致が、圧縮出力として使用される。延長列が、データ固有辞書に保存される。まれに発生する文字シーケンスは、データ固有辞書に入力されると思われる。というのは、まれに発生するシーケンスが、事前に充てんされる辞書内の対応するシーケンスを有しないからである。事前に充てんされる辞書には、頻繁に発生するシーケンスが保存されるが、まれに発生するシーケンスが、データ固有辞書から貴重なコードを奪う可能性がある。
【００１１】
本発明の目的は、入力データ統計に適応する動的除外テーブルを使用することによって、まれに発生するデータ文字列が圧縮辞書および伸長辞書内の貴重なコードを占めないようにするデータ圧縮伸長システムを提供することにある。
【課題を解決するための手段】
【００１２】
本発明のシステムには、データ文字の入力ストリームを、圧縮コードの出力ストリームに圧縮するデータコンプレッサが含まれる。辞書には、入力ストリームで出会ったデータ文字の列が保存され、保存される列は、コードを有し、めいめいのコードと関連付けられる。入力ストリームは、入力ストリームを保存された列と比較して、その間の最長一致を判定することによって検索される。最長一致に関連するコードが、圧縮コードの出力ストリームを提供するために出力される。除外テーブルは、辞書への保存から除外されるデータ文字の列を保存するために含まれる。最長一致を有し、入力ストリームの次のデータ文字によって延長された延長列が、形成されると、これが除外テーブルに含まれない場合に、延長列が、辞書に保存(保管)され、コードが割り当てられる。除外テーブルに含まれる場合には、延長列は、保存されず、コードは、別の列に使用可能なままになる。除外テーブルの列に出会う回数が、カウントされ、このカウントが、所定の閾値を超える場合に、その列が、除外テーブルから削除される。この形で、除外テーブルに保存される列が、入力データの統計に適応する。
【００１３】
具体的に言うと、入力ストリームは、一致しない入力文字が出てくるまで、辞書に保存された列と比較され、これによって、最長一致が判定される。一致しない文字は、除外テーブルに含まれないならば、次の列検索の開始に使用される。除外テーブルに含まれる場合には、一致しない文字を出力し、除外テーブルにない入力データ文字が取り出されるまで、次の単一の入力データ文字を、順次取り出し、出力する。この除外テーブルにない文字が、次の列検索の開始に使用される。除外テーブルの各そのような単一データ文字に出会う回数を、カウントし、この単一文字列は、それに関連するカウントが所定の閾値を超える場合に、除外テーブルから削除される。やはり、この形で、除外テーブルに保存される列が、入力データの統計に適応する。
【００１４】
除外テーブルから列を削除するほかに、列が辞書で一致した回数のカウントが維持される。列が辞書で一致した回数が、所定の閾値より低い場合に、その列が、もう一度除外テーブルに追加され、入力データの統計に適応する除外テーブルがもたらされる。
【００１５】
データデコンプレッサに、コンプレッサに含まれる除外テーブルと同一の除外テーブルが含まれ、データデコンプレッサで、コンプレッサで使用される判断基準と同一の除外テーブル列の削除および追加の判断基準が使用される。この形で、デコンプレッサによって、コンプレッサで保存される除外テーブルおよび辞書と同一の、除外テーブルおよび辞書に保存される列が維持される。
【発明を実施するための最良の形態】
【００１６】
以下で説明する最適態様実施形態は、ＬＺＷ方法論に基づき、単一文字列が、明示的に初期化はされないが、コンプレッサおよびデコンプレッサによって認識されるとみなされる、上述の実施形態を使用する。この実施形態は、特許（たとえば、特許文献１０参照）に開示された圧縮伸長システムの修正形態である。
【００１７】
図１を参照すると、データコンプレッサ１０が、辞書１１および入力文字バッファ１２と一緒に、入力１３に印加される入力データ文字のストリームを、出力１４の対応する圧縮コードのストリームに圧縮する。
【００１８】
コンプレッサ１０には、現在一致レジスタ２０、現在文字レジスタ２１、コードカウンタ２２、およびコードサイズレジスタ２３が含まれる。コードカウンタ２２は、周知の形で、データ文字列に割り当てられ、辞書１１に保存(保管)されるコード値を順次生成する。コードサイズレジスタ２３は、周知のように、出力１４から圧縮コードを送出するのに使用されるビット数を制御するのに使用される。
【００１９】
コンプレッサ１０には、入力データストリームで出会う単一文字列に関する統計を累積する単一文字テーブル２４も含まれる。単一文字テーブル２４の詳細を、図２に示す。さらに、辞書１１への保存から除外されるデータ文字列を保存し、本明細書で説明する形で、除外される列に関する統計を累積する、除外テーブル２５が含まれる。除外テーブル２５の詳細を、図３に示す。コンプレッサ１０には、延長列を組み立てる延長列レジスタ２６も含まれる。延長列レジスタ２６は、延長列が除外テーブル２５に含まれるか否かのテスト(判定)を容易にするのに使用される。延長列カウンタ２７は、延長列レジスタ２６内の延長列の文字数のカウントを提供するために含まれる。文字カウントは、本明細書で説明する形で、除外テーブル２５の検索を容易にするのに使用される。
【００２０】
除外テーブル２５から列を削除し、除外テーブル２５に列を追加し、その結果、除外テーブル２５で維持される列が、入力データの統計に動的に適応するようにする、除外テーブル更新論理３０も含まれる。論理３０は、本明細書で説明する形で動作し、それぞれレジスタ３１から３３に保存される所定の除外テーブル閾値パラメータ、所定の辞書列閾値パラメータ、および所定の単一文字テーブル閾値パラメータを使用する。
【００２１】
コンプレッサ１０には、さらに、辞書１１に保存される最大長列を示す列長限度パラメータを保存する列長限度レジスタ３４が含まれる。コンプレッサ１０には、さらに、下で説明する図４の動作流れ図に従うコンプレッサ１０の動作を制御する制御３５が含まれる。
【００２２】
辞書１１は、コンプレッサ１０と協力してデータ文字列を保存するために含まれる。データは、コンプレッサ１０と辞書１１の間で、制御バス４１の制御下にある両方向データバス４０を介して通信される。辞書１１には、たとえば、符号４２に示されているように構成された、４０９６個の位置が含まれる。辞書位置には、プレフィックスコードフィールド４３およびデータ文字フィールド４４とが含まれ、位置は、辞書１１内でアドレス４５によってアクセスされる。４０９６個の位置の辞書では、アドレス４５が、１２ビット幅である。周知の形で、列は、列プレフィックスのコードを、辞書位置のプレフィックスコードフィールド４３に保存し、列延長データ文字を、辞書位置のデータ文字フィールド４４に保存することによって、辞書１１に保存される。便宜上、位置のアドレス４５を、列コードとして使用する。辞書１１は、特許で説明された形（たとえば、特許文献７参照）での列の検索および保存のための連想記憶（ａｓｓｏｃｉａｔｉｖｅ  ｍｅｍｏｒｙ）として便利に構成され、使用される。列の検索および保存は、当技術分野で周知のように（たとえば、特許文献１および特許文献８参照）、ハッシングによるなど、他の配置によって成し遂げることもできる。
【００２３】
下で説明する形で、辞書１１が、除外テーブル２５を更新するために辞書１１に保存される列に関する統計を蓄積するのに使用される。この機能を実行するために、辞書１１の位置４２のそれぞれに、ヒットカウンタ４６および文字カウンタ４７が含まれる。ヒットカウンタ４６によって、ヒットカウンタが関連付けられる文字が辞書１１で一致した回数のカウントが維持される。文字カウンタ４７には、辞書位置に保存される列を含む文字の数のカウントが保存される。したがって、ヒットカウンタ４６によって、辞書１１に保存された文字が、入力データ文字ストリームと一致する頻度に関する統計が累積される。辞書１１内の列に、ごくまれに出会う場合に、この列を、下で説明する形で辞書１１からそれ以降に除外するために除外テーブル２５に含めることができる。文字カウンタ４７は、除外テーブル２５の更新を容易にするのに使用される。ヒットカウンタ４６および文字カウンタ４７は、辞書１１の一部として図示されているが、これらのカウンタを、辞書アドレス４５に適当にインデクシングする別々の配列として維持することができる。
【００２４】
入力文字バッファ１２によって、入力１３で受け取られる入力データ文字ストリームをバッファリングする。入力データ文字は、これから説明する動作によって、入力文字バッファ１２からバス５０を介して現在一致レジスタ２０および現在文字レジスタ２１に印加される。コンプレッサ１０は、入力文字バッファ１２からの入力データ文字の獲得を、制御バス５１を介して制御する。
【００２５】
図２を参照すると、単一文字テーブル２４に、それに対してデータ圧縮が実行されるアルファベットのめいめいの文字の項目６０と、めいめいが文字のそれぞれに関連するカウンタ６１が含まれる。これから説明する形で、カウンタ６１のそれぞれが、それに関連する文字が、除外テーブル２５に含まれない単一文字列として入力データ文字ストリーム内で出会う回数のカウントを維持するのに使用される。コンプレッサ１０に含まれる配列として図示されているが、単一文字テーブル２４を、代わりに、辞書１１内で維持することができる。したがって、カウンタ６１によって、文字項目６０によって表される単一文字列の発生の頻度に関する統計が累積されることを諒解されたい。除外テーブル２５に含まれない単一文字列が、ごくまれに出会う列である場合に、この列を、除外テーブル２５のテーブル７０に入力し、その結果、この文字から始まる列が、その後、辞書１１での保存から除外されるようにする。
【００２６】
図３を参照すると、除外テーブル２５に、単一文字列を保存するテーブル７０、文字対列を保存するテーブル７１、文字３つ組列を保存するテーブル７２、および、図１の列長限度レジスタ３４に保存された列長限度と等しい文字数を有する列を保存するテーブル７３までが含まれる。コンプレッサ１０の、下で説明する動作から、テーブル７０から７３のいずれかに保存される列が、辞書１１への保存から除外されることを理解されたい。さらに、テーブル７０から７３に保存される列の延長が、辞書１１に保存されないことも明白になる。一般に、列長限度レジスタ３４（図１）の列長限度より長い列は、辞書１１に保存されない。したがって、除外テーブル２５に保存される最長の列は、テーブル７３に保存され、列長限度と等しい長さを有する。
【００２７】
テーブル７０から７３に関連するのが、めいめいのカウンタの配列７４から７７である。各配列の各カウンタによって、カウンタが関連する列に除外テーブルの関連する１つで出会う回数のカウントが維持される。したがって、カウンタ７４から７７によって、除外テーブル２５に保存される列の発生の頻度に関する統計が累積される。除外される列に、あまりに頻繁に出会う場合には、その列を、除外テーブル２５から削除し、その結果、この列を、その後、辞書１１に保存できるようにする。カウンタ７４から７７は、除外テーブル２５の一部として図示されているが、これらのカウンタを、テーブル７０から７３の列に適当にインデクシングされる別々の配列として維持することができる。
【００２８】
図１から３の参照を続けると、コンプレッサ１０の動作は、簡単に言うと次の通りである。動作の初期化点で、コードカウンタ２２に、最初の使用可能な複数文字列コードがセットされる。さらに、辞書１１、現在一致レジスタ２０、延長列レジスタ２６、延長列カウンタ２７、除外テーブルカウンタ７４から７７、および単一文字テーブルカウンタ６１がクリアされる。最初の入力データ文字が、現在一致レジスタ２０に取り出されて、圧縮サイクルが開始される。後続の圧縮サイクルの始めに、現在一致レジスタ２０が、前の圧縮サイクルから決定された一致しない文字が含まれるようにセットされる。
【００２９】
サイクルの始めに、除外テーブル２５を調べて、現在一致レジスタ２０の文字が、単一文字のテーブル７０に含まれるか否かを判定する。そうである場合には、その文字に関連するカウンタ配列７４のカウンタを、１つ増分する。この文字が、出力され、次の入力データ文字が、現在一致レジスタ２０に取り出される。これは、現在一致レジスタ２０に取り出された文字が、除外テーブル２５に含まれる文字でなくなるまで継続される。その後、現在一致レジスタ２０の文字が、延長列レジスタ２６にシフトされ、１が、延長列カウンタ２７に加算される。単一文字テーブル２４の対応するカウンタ６１も、１つ増分される。その後、次の入力データ文字が、現在文字レジスタ２１に取り出される。この文字も、延長列レジスタ２６にシフトされ、延長列カウンタ２７が、やはり１つ増分される。
【００３０】
辞書１１は、現在文字を連結された現在一致によって表される列について検索される。その列が、辞書１１で見つかる場合に、一致した列に関連するヒットカウンタ４６が、１つ増分される。その列コードが、現在一致レジスタ２０にロードされ、次の入力データ文字が、現在文字レジスタ２１に取り出される。この文字は、延長列レジスタ２６にもシフトされ、延長列カウンタ２７が、やはり増分される。
【００３１】
検索は、現在一致レジスタ２０の内容および現在文字レジスタ２１の内容によって表される列が、辞書１１で見つからなくなり、現在文字レジスタ２１の文字に、不一致文字が含まれるまで継続される。この形で、最長一致が判定されるまで、入力データ文字ストリームが、辞書１１内の列と突き合わされ、一致した列の出現の頻度の統計が、ヒットカウンタ４６に累積される。最長の一致する列のコードが、コードサイズレジスタ２３によって決定されるビット数を使用して、現在一致レジスタ２０から圧縮出力１４に出力される。
【００３２】
辞書１１で見つからない列は、延長列カウンタ２７の文字カウントが列長限度レジスタ３４の列長限度より小さく、列が除外テーブル２５に含まれない場合に、辞書内の、コードカウンタ２２によって割り当てられるコードの位置に保存される。延長列レジスタ２６および延長列カウンタ２７によって、除外テーブル２５への問合せが容易になる。というのは、延長列カウンタ２７の文字カウントによって、テーブル７０から７３のどれを調べなければならないかが示され、延長列レジスタ２６に、テストされる列延長が格納されるからである。列長が、列長限度より大きくなく、列が、除外テーブル２５に含まれない場合に、その列は、辞書１１の、コードカウンタ２２によって割り当てられる位置に保存され、コードカウンタ２２が、１つ増分される。さらに、保存された列に関連するヒットカウンタ４６に、１がセットされ、保存された列に関連する文字カウンタ４７に、延長列カウンタ２７のカウントがセットされる。この形で、ヒットカウンタ４６によって、保存された列に関する出現頻度の統計が累積される。対応する文字カウンタ４７に、これから説明する除外テーブル更新処理を容易にするために、列の文字数がセットされる。
【００３３】
列が、列長さのゆえに、または除外テーブル２５に含まれるので、いずれかで除外される場合には、辞書１１が、更新されず、コードカウンタ２２が、増分されない。列が、除外テーブル２５に含まれるので除外される場合には、カウンタ７４から７７の関連する１つが、１つ増分されて、その列に関する出現頻度の統計が累積される。
【００３４】
列が、保存から除外される場合に、圧縮サイクルは、現在一致レジスタ２０に、現在文字レジスタ２１の文字をセットすることによって終了する。しかし、列が辞書１１に保存される場合には、テストを実行して、辞書１１が満杯であるか否かを判定する。辞書が満杯でない場合には、圧縮サイクルは、やはり現在一致レジスタ２０に現在文字レジスタ２１の文字をセットすることによって終了する。
【００３５】
辞書が満杯の場合には、現在文字が、出力され、単一文字テーブルカウンタ６１、除外テーブル２５のカウンタ７４から７７、および辞書１１のヒットカウンタ４６によって累積された統計に従って、除外テーブル２５が、そこから列を削除し、そこに列を追加することによって更新される。一般に、除外テーブル２５で頻繁に出会う列は、そこから削除され、辞書１１でまれに出会う列は、除外テーブル２５に追加される。
【００３６】
除外テーブル２５を更新した後に、制御は、上述の初期化点に戻され、そこで、適当なリセットおよびクリアが実行される。
【００３７】
図１から３と共に図４を参照すると、コンプレッサ１０によって実行される詳細な動作を示す制御流れ図が示されている。コンプレッサ１０の制御３５は、動作の実行を制御するために、状態機械などの適当な回路または適当なソフトウェアを含むとみなされる。図４の流れ図は、可変長出力に基づき、コードサイズレジスタ２３が、この効果に使用される。ＡＳＣＩＩ可変長コード実施形態では、コードサイズが、９ビットから始まり、それぞれ、１０ビット（コードは５１２個）、１１ビット（コードは１０２４個）、および１２ビット（コードは２０４８個）に順次増やすことができる。
【００３８】
コンプレッサ１０の動作は、ブロック９０に従って、除外テーブル２５のクリアまたは初期化のいずれかから開始することができる。除外テーブル２５が、まずクリアされる場合には、テーブル７０から７３が、まず、すべての列について空になる。図４に示された動作によって、除外テーブル２５は、辞書１１および単一文字テーブル２４に累積された統計に基づく列を移植される。
【００３９】
その代わりに、列の初期の組を除外テーブル２５に移植する自動手順を、図１７に関して下で提供する。まれに出会う列を識別するこの手順は、頻繁に出会う列を識別する特許で説明される手順の修正形態である（たとえば、特許文献９参照）。
【００４０】
もう１つの代替として、除外テーブル２５に、まず、圧縮されるデータのタイプの列分布統計の知識を有する当業者が、手作業で移植することができる。英語の統計に関する有用な情報が、文献に記載されている（たとえば、非特許文献５および非特許文献６参照）。
【００４１】
どの形であれ、ブロック９０を実施する際に、図４の動作によって、入力データの統計に従って除外テーブル２５の内容が動的に調整される。
【００４２】
制御は、ブロック９１に進み、ここで、コードカウンタ２２を、最初の使用可能なコード、たとえば、ＡＳＣＩＩ環境では２５８に初期化する。ブロック９２で、コードサイズレジスタ２３を、開始コードサイズ、たとえば、ＡＳＣＩＩ環境では９ビットに初期化する。ブロック９３で、現在一致レジスタ２０と、延長列レジスタ２６と、延長列カウンタ２７と、除外テーブルカウンタ７４から７７と、単一文字テーブルカウンタ６１と、ヒットカウンタ４６および文字カウンタ４７を含む辞書１１とをクリアする。
【００４３】
ブロック９４で、入力データ文字を現在一致レジスタ２０に取り出す。処理が、ブロック９３からブロック９４に入る場合には、これは、ブロック９１から９３の初期設定動作およびクリア動作を実行した後の、入力データ文字ストリームから取り出される最初のデータ文字である。ブロック９５で、除外テーブル２５を調べて、現在一致レジスタ２０の文字が、除外すべき単一文字列として含まれるか否かを判定する。したがって、ブロック９５では、単一文字のテーブル７０を調べることだけが必要である。
【００４４】
現在一致レジスタ２０の文字が、テーブル７０に含まれる場合には、ブロック９５からのＹＥＳ分岐でブロック９６に進む。ブロック９６では、その文字に関連するカウンタ配列７４のカウンタを、１つ増分する。したがって、ブロック９６で、除外テーブル２５で出会う単一文字列の出現の頻度に関して統計が累積される。処理はブロック９７に進み、ここで、現在一致レジスタ２０の文字を、コードサイズレジスタ２３によって指定されるビット数を使用して、現在一致レジスタ２０から圧縮出力１４に出力する。処理は、ブロック９７からブロック９４に戻って、次の入力データ文字を現在一致レジスタ２０に取り出す。
【００４５】
ブロック９５で、現在一致レジスタ２０の文字が除外テーブル２５にない場合には、ブロック９５からのＮＯ分岐でブロック９８に進む。ブロック９８では、現在一致レジスタ２０の文字に関連する単一文字テーブル２４のカウンタ６１を、１つ増分する。この形で、入力データ文字ストリームで出会う、除外テーブル２５によって除外されない単一文字列に関する統計が累積される。その後、ブロック９９で、現在一致レジスタ２０の文字を、延長列レジスタ２６にシフトし、ブロック１００で、延長列カウンタ２７のカウンタを１つ増分する。
【００４６】
ブロック１１０で、次の入力データ文字を、現在文字レジスタ２１に取り出す。ブロック１１１で、現在文字レジスタ２１の文字を延長列レジスタ２６にシフトし、ブロック１１２で、延長列カウンタ２７のカウンタを１つ増分する。列の文字が、ブロック１１０で入力データ文字ストリームから取り出されるので、説明する列処理を容易にするために、列の文字が、延長列レジスタ２６に入力され、延長列カウンタ２７によってカウントされることを諒解されたい。
【００４７】
処理は、ブロック１１３で継続され、ここで、辞書１１を検索して、現在文字レジスタ２１の文字が連結した現在一致レジスタ２０のコードに対応する列が、辞書１１にあるか否かを判定する。辞書検索手順は、ブロック１１３の機能の実行に関して当技術分野で周知である（たとえば、特許文献１、特許文献７、または特許文献８参照）。具体的に言うと、辞書１１を、特許（たとえば、特許文献７）で説明されているように、連想式に検索することができる。列が辞書１１に存在するのは、辞書位置のプレフィックスコード４３および文字４４が、現在一致レジスタ２０のコードおよび現在文字レジスタ２１の文字と一致する場合である。位置のアドレス４５によって、一致する列のコードが与えられる。
【００４８】
ブロック１１３で、列が辞書１１で見つかる場合には、ブロック１１３からのＹＥＳ分岐でブロック１１４に進む。ブロック１１４では、一致した列に関連するヒットカウンタ４６を、１つ増分する。一致した列のアドレス４５が、辞書１１内で突き止められたので、関連するヒットカウンタ４６は、すぐにアクセスされ、増分される。この形で、ヒットカウンタ４６によって、一致した列の出現頻度に関する統計が累積される。制御は、ブロック１１５に進み、ここで、現在一致レジスタ２０の内容が、見つかった列のコードを含むように更新される。具体的に言うと、列が見つかった辞書位置の列コードアドレス４５が、現在一致レジスタ２０に入力される。現在一致している列のコードを用いて現在一致レジスタ２０を更新した後に、制御は、ブロック１１０に戻って、次の入力データ文字を現在文字レジスタ２１に取り出す。処理は、上述のブロック１１１および１１２で継続され、現在取り出されている文字が、延長列レジスタ２６にシフトされ、延長列カウンタ２７が１つ増分される。
【００４９】
この形で、ブロック１１０から１１５によって形成されるループで、入力データ文字ストリームを、辞書１１に保存された列と比較して、これらの最長一致を見つける。延長され、辞書１１で検索される入力データ文字列は、延長され、延長列レジスタ２６に保存され続けると同時に、列の文字数のカウントが、延長列カウンタ２７で維持される。さらに、列が延長され突き合わされる際に、関連するヒットカウンタ４６によって、その統計が維持され続ける。
【００５０】
ブロック１１３で、現在一致している列と、ブロック１１０で取り出された次の文字との連結によって、辞書１１にない延長列がもたらされる場合に、ブロック１１３からのＮＯ分岐でブロック１１６に進む。ブロック１１６では、現在一致のコードが、コンプレッサ出力１４で提供される圧縮コードストリームの一部として出力される。現在一致のコードは、現在一致レジスタ２０によって与えられ、コードサイズレジスタ２３によって示されるビット数を使用して出力される。現在一致が、複数文字列である場合に、列のコードは、現在一致レジスタ２０にあり、ブロック１１３に関して上述したように、辞書１１で見つかった最長一致であった。ブロック１１６で出力される現在一致が、単一文字である可能性もあることを諒解されたい。この場合の出力コードは、やはり現在一致レジスタ２０から与えられる文字の値である。
【００５１】
処理は、ブロック１２０に進み、ここで、延長列カウンタ２７の文字カウントを、列長限度レジスタ３４の列長限度と比較して、ブロック１１３で辞書１１で見つからなかった延長列の文字カウントが、列長限度より大きいか否かを判定する。ブロック１２０のテストは、そうでなければ辞書１１に保存された可能性がある延長列を、列が所定の長さより長い場合に除外できるようにするために実行される。この特徴が本発明の好ましい実施形態に含まれるのは、データ、アルファベットのサイズ、および辞書のサイズの統計によると、ある長さを超える反復的でない文字の列が、繰り返されない傾向があることが観察されたからである。たとえば、制限されたサイズの辞書が使用されるＧＩＦ環境で、２５６文字のアルファベットと非反復的データの場合に、約４または５文字の列が、ほとんど繰り返されないことが観察された。
【００５２】
したがって、列長限度を超える列は、また出会うとしてもごくまれに出会うだけなので、辞書１１への保存から除外することができる。この形で、コードカウンタ２２によって割り当てられる文字コードが、そのようなまれに出会う文字によって奪われなくなる。
【００５３】
任意選択として、本発明を、ブロック１２０によって表される特徴を使用せずに実施することができる。そうすることが望まれる場合には、ブロック１２０を削除する。さらに、反復する文字ランが入力データ文字ストリームで発生している場合に、列長制限をバイパスすることができる。この実施形態の修正を、図１８および１９に関して説明する。
【００５４】
ブロック１２０で、延長列の文字カウントが、列長限度より大きくない場合に、ブロック１２０からのＮＯ分岐でブロック１２１に進む。ブロック１２１では、除外テーブル２５を調べて、延長列レジスタ２６の列がそれに含まれるか否かを判定する。延長列カウンタ２７の文字カウントに応じて、テーブル７０から７３の適当な１つを調べる。たとえば、延長列カウンタ２７によって、延長列レジスタ２６の延長列が３文字からなることが示される場合に、文字３つ組のテーブル７２を調べる。延長列レジスタ２６の延長列が、除外テーブル２５に含まれない場合には、ブロック１２１のＮＯ分岐でブロック１２２に進む。
【００５５】
上で説明したように、延長列レジスタ２６の列は、ブロック１１３で辞書１１内で見つからなかった延長列である。ブロック１２２で、この延長列を辞書１１に入力し、コードカウンタ２２の現存コードを、この保存された延長列に割り当てる。ブロック１２２の機能の特定の実施形態の詳細は、既知である（たとえば、特許文献１、特許文献７、または特許文献８参照）。具体的に言うと、本明細書で開示される特定の実施形態では、現在一致レジスタ２０のコードおよび現在文字レジスタ２１の文字が、それぞれ、コードカウンタ２２の現存コードによってアドレッシングされる辞書位置のプレフィックスコードフィールド４３および文字フィールド４４に入力される。延長列が、辞書１１の次の空の位置に入力されることを諒解されたい。本明細書で説明されるコンプレッサ１０の動作に従って、プレフィックスコードフィールド４３に保存される現在一致レジスタ２０の値は、単一文字値または複数文字列コードのいずれかになる可能性がある。
【００５６】
制御は、ブロック１２３に進み、ここで、保存された列に関連するヒットカウンタ４６に、１をセットする。上で説明したように、ヒットカウンタ４６によって、関連する保存された列に関する出現頻度統計が累積される。ブロック１２４で、保存された列に関連する文字カウンタ４７に、延長列カウンタ２７のカウントをセットする。したがって、関連する文字カウンタ４７に、保存された延長列を含む文字数がセットされる。文字カウンタ４７は、説明される形での除外テーブル２５の更新を容易にするのに使用される。
【００５７】
次に、処理はブロック１２５に進み、ここで、コードカウンタ２２のコードをテストして、コードサイズの増大が必要であるか否かを判定する。そうである場合には、処理はブロック１２６に継続され、ここで、コードサイズレジスタ２３を１つ増分する。ブロック１２５でコードサイズの増大が必要でない場合には、ブロック１２６をバイパスして、ブロック１２７で処理を継続する。ブロック１２７では、コードカウンタ２２を１つ増分する。ブロック１２８で、テストを実行して、辞書１１が満杯であるか否かを判定する。このテストは、コードカウンタ２２のオーバーフロー出力を検査して、コードカウンタ２２が、ブロック１２７での増分の結果としてオーバーフローしたか否かを判定することによって、便利に実行される。
【００５８】
ブロック１２８で、辞書１１が満杯である場合には、ブロック１２８からのＮＯ分岐でブロック１３３に進む。ブロック１３３では、現在一致レジスタ２０、延長列レジスタ２６、および延長列カウンタ２７をクリアする。ブロック１３４で、現在文字レジスタ２１の文字を、現在一致レジスタ２０にセットする。したがって、現在一致レジスタ２０に、ブロック１１３で不一致をもたらした文字がセットされる。この文字は、次の圧縮サイクルの開始に使用され、したがって、制御はブロック９５に戻る。
【００５９】
ブロック１２０で、延長列の文字カウントが列長限度より多いか、ブロック１２１で、延長列レジスタ２６の延長列が除外テーブル２５に含まれる場合に、ブロック１２０からの関連するＹＥＳ分岐またはブロック１２１からの関連するＹＥＳ分岐からブロック１３５を介して、ブロック１３３に進んで、ブロック１２２から１２８の処理をバイパスする。これが発生する場合には、延長列が、辞書１１に保存されず、コードカウンタ２２が、増分されない。
【００６０】
延長列が除外テーブル２５に含まれる場合に、ブロック１２１からのＹＥＳ分岐でブロック１３５に進む。ブロック１３５では、延長列に関連する、カウンタ配列７４から７７の適当なカウンタを、１つ増分する。したがって、除外テーブル２５の延長列に出会う頻度に関する統計が累積される。前に説明したように、制御は、ブロック１３５からブロック１３３に進む。
【００６１】
上記から、延長列が辞書１１に保存されるか除外されるかにかかわらずに、処理は、辞書１１が満杯でない場合に、上述のようにブロック１３３で継続されることを諒解されたい。
【００６２】
ブロック１２８で、辞書１１が満杯と判定される場合に、ブロック１２８からのＹＥＳ分岐でブロック１４０に進む。ブロック１４０では、現在文字レジスタ２１の文字を、コードサイズレジスタ２３によって示されるビット数を使用して、圧縮出力１４で出力する。制御は、ブロック１４１に進み、ここで、カウンタ配列７４から７７の関連するカウンタがレジスタ３１の除外テーブル閾値を超える各列を除外テーブル２５から削除することによって、除外テーブル２５を更新する。除外テーブル閾値は、頻繁に出会う列が、除外テーブル２５のテーブル７０から７３から削除されるように選択される。したがって、コンプレッサ１０の後続動作で、ブロック１４１で除外テーブル２５から削除された列は、入力データ文字ストリームで出会う場合に、辞書１１に保存することができる。
【００６３】
処理はブロック１４２に進み、ここで、辞書の列に関連するヒットカウンタ４６が、レジスタ３２の辞書列閾値未満である列が、辞書１１から除外テーブル２５に保存される。辞書列閾値は、辞書１１内でまれにのみ一致する列を、除外テーブル２５にセットでき、その結果、コンプレッサ１０の後続動作で、これらの列を辞書保存から除外できるようになるように選択される。文字カウンタ４７は、列が保存される適当なテーブル７０から７３を識別する際のブロック１４２の機能を容易にするのに使用される。
【００６４】
除外テーブル２５への保存のために辞書１１から列の文字を抽出する手順は、周知である（たとえば、特許文献１、特許文献７、または特許文献８参照）。短く言うと、アクセスされる辞書位置の文字フィールド４４の文字を、保存し、その位置のプレフィックスコードフィールド４３のコードを使用して、辞書１１にアクセスする。文字が、このアクセスされた位置から保存され、そのプレフィックスコードによって、列のこの逆方向トレースでアクセスする次の辞書位置が与えられる。プレフィックスコードが、文字値と等しい場合には、列の文字のすべてが、除外テーブル２５の適当なテーブル７０から７３への保存のために回復されている。
【００６５】
制御は、ブロック１４３に進み、ここで、単一文字テーブル２４からの選択された単一文字列が、除外テーブル２５のテーブル７０に保存される。関連するカウンタ６１が、レジスタ３３の単一文字テーブル閾値未満の非０カウントを有する列が、選択される。したがって、ブロック１４２に関して説明した動作に似た形で、ごくまれに出会った単一文字列を、除外テーブル２５に保存でき、その結果、そのような単一文字から始まる列を、コンプレッサ１０の後続動作で辞書保存から除外できるようになる。
【００６６】
単一文字テーブル２４に、アルファベット文字のそれぞれの項目が含まれるので、ブロック１４３の機能性を実行する際に、非０カウントだけが使用される。代替として、単一文字テーブル２４を、実際に出会った単一文字だけがそのテーブルでカウントされるように配置することができる。この代替配置では、ブロック９３で、単一文字テーブル２４全体がクリアされる。ブロック１４２および１４３に関して、除外テーブル２５に入力される列は、上述のコンプレッサ１０の処理で除外される列ではなかったので、まだ除外テーブルに保存されていないことを諒解されたい。
【００６７】
ブロック１４１から１４３で除外テーブル２５を更新した後に、制御は、ブロック９１に戻って、列によって辞書１１を選択的に充てんするさらなるサイクルを開始するのに先立って、適当なリセットおよびクリアを開始する。
【００６８】
ブロック１４１から１４３で、列を充てんされる辞書１１による除外テーブル２５の更新が実行されるが、本発明を実践するのに、他の実施形態を使用することができることを諒解されたい。たとえば、列に関連するカウンタが除外テーブル閾値３１を超える場合に、必ず、列を除外テーブル２５から「オンザフライ」で削除することができる。同様に、辞書が満杯になるのに先立つ所定の点で、列を辞書１１から除外テーブル２５に転送することができる。
【００６９】
ブロック９０で、クリアされた除外テーブルを用いて動作が開始される場合に、図４の流れ図を介する最初の反復中にブロック１４１をバイパスすることができる。というのは、処理がはじめてブロック１４１に入る場合に、除外テーブル２５が空であるからである。ブロック１４１から１４３を、除外テーブル２５の列の削除および列の追加の両方で説明したが、除外テーブル２５に関して更新動作の１つだけが実行される場合にも本発明を実践できることを諒解されたい。
【００７０】
ブロック１４２および１４３で、テーブル７０から７３の１つまたは複数が満杯である場合に、ブロック１４２および１４３の機能の実行に先立って、適当な列削除戦略を使用することができる。たとえば、除外テーブル２５に入力されたが、その後、コンプレッサ１０の後続の動作でまだ出会っていない列を、削除することができる。そのような列に関連するカウンタ７４から７７は、０のカウントを有する。
【００７１】
ブロック９１、９２、９４、１１０、１１３、１１５、１１６、１２２、１２５から１２７、および１３４によって、基礎になる図４のＬＺＷデータ圧縮処理が示されることを諒解されたい。したがって、ＬＺＷデータ圧縮のすべての既知の実施形態を、これらのＬＺＷデータ圧縮態様の実施に使用することができる。
【００７２】
図５を、図１から３の参照を続けながら参照すると、データデコンプレッサ２１０が、辞書２１１および入力コードバッファ２１２と一緒に、入力２１３に印加される圧縮コードのストリームを、出力２１４のデータ文字の回復されたストリームに伸長する。コンプレッサ１０（図１）の出力１４からの圧縮コードストリームが、デコンプレッサ２１０の入力２１３に印加される場合に、デコンプレッサ２１０の出力２１４での、コンプレッサ１０の入力１３に印加された元の入力データ文字ストリームの回復をもたらすことを諒解されたい。
【００７３】
デコンプレッサ２１０には、現在コードレジスタ２２０、前コードレジスタ２２１、コードカウンタ２２２、およびコードサイズレジスタ２２３が含まれる。コードサイズレジスタ２２３は、コードサイズレジスタ２２３によって、デコンプレッサ２１０が入力圧縮コードで受け取るビット数が判定されるという点で、コンプレッサ１０のコードサイズレジスタ２３に関して上述した機能に類似する機能を実行する。コードカウンタ２２２は、デコンプレッサ２１０によって辞書２１１に保存され、説明される形で着信圧縮コードを処理するのに使用される、延長列に割り当てられるコード値を順次生成する。下の説明では、コードカウンタ２２２が、図１のコンプレッサ１０のコードカウンタ２２との密着した関係を維持することを諒解されたい。
【００７４】
デコンプレッサ２１０には、図１および２に関して上で説明した単一文字テーブル２４と同一の単一文字テーブル２２４も含まれる。上で図２に関して説明した文字配列６０およびカウンタ６１は、デコンプレッサ２１０の単一文字テーブル２２４に関して、文字配列２６０およびカウンタ２６１と表される。説明される形で、デコンプレッサ２１０では、単一文字テーブル２４でコンプレッサ１０によって累積される統計と同一の、単一文字列に関する統計が累積される。
【００７５】
デコンプレッサ２１０には、さらに、図１および３に関して上で説明した除外テーブル２５と同一の除外テーブル２２５が含まれる。図３に関して上で説明したテーブル７０から７３およびカウンタ７４から７７は、デコンプレッサ２１０の除外テーブル２２５に関して、テーブル２７０から２７３およびカウンタ２７４から２７７と表される。説明される形で、デコンプレッサ２１０によって、コンプレッサ１０によって保存され除外テーブル２５に累積されるのと同一の列が保存され、同一の統計が除外テーブル２２５に累積される。
【００７６】
デコンプレッサ２１０には、延長列を組み立てる延長列レジスタ２２６も含まれる。延長列レジスタ２２６は、コンプレッサ１０の延長列レジスタ２６に関して上述した形に似た形で、延長列が除外テーブル２２５にあるか否かの判定を容易にするのに使用される。デコンプレッサ２１０には、さらに、辞書２１１に保存される最大長列を示す列長限度パラメータを保存する列長限度レジスタ２３４が含まれる。列長限度レジスタ２３４は、コンプレッサ１０の列長限度レジスタ３４に関して上述した形で、デコンプレッサ２１０内で使用される。コンプレッサ１０の任意選択の列長限度特徴に関する上の説明は、さらに説明される形でデコンプレッサ２１０で使用される列長限度特徴にも適用される。
【００７７】
除外テーブル更新論理２３０も含まれ、これによって、それぞれレジスタ２３１から２３３に保存される、所定の除外テーブル閾値パラメータ、所定の辞書列閾値パラメータ、および所定の単一文字テーブル閾値パラメータが使用される。論理２３０およびレジスタ２３１から２３３は、図１に関して上述した論理３０およびレジスタ３１から３３と同一である。除外テーブル更新論理２３０は、除外テーブル２２５から列を削除し、これに列を追加し、その結果、そこに保存される列が、説明される形でコンプレッサ１０によって除外テーブル２５に保存される列と同一に維持されるようにするために、デコンプレッサ２１０に含まれる。
【００７８】
デコンプレッサ２１０には、現在列バッファ２５４および現在列カウンタ２５６も含まれる。現在列バッファ２５４には、現在コードに対応する列の文字が保持され、現在列カウンタ２５６は、現在コードに対応する列の文字数のカウントを提供する。さらに、デコンプレッサ２１０には、前列バッファ２５５および前列カウンタ２５７が含まれる。伸長サイクルの終りに、下の説明に従って、現在列バッファ２５４および現在列カウンタ２５６の内容が、適当な場合に、それぞれ前列バッファ２５５および前列カウンタ２５７に転送され、その結果、前の列の情報が、次の伸長サイクルで使用可能になる。
【００７９】
デコンプレッサ２１０には、さらに、説明される形で処理され出力される列を組み立てる、作業バッファ２２７が含まれる。図６から９の動作流れ図によるデコンプレッサ２１０の動作を制御する、制御２３５も含まれる。
【００８０】
辞書２１１は、図１に関して上述した辞書１１と同一の形で構成され、列保存および検索に使用される。辞書２１１は、辞書１１について図１に関して上述したのと同一の形で、デコンプレッサ２１０と協同して、受け取った圧縮コード入力に対応するデータ文字列を保存し、そこに保存された列に関する統計を累積する。データは、制御バス２４１の制御下の両方向データバス２４０を介して、デコンプレッサ２１０と辞書２１１の間で通信される。デコンプレッサ２１１の動作では、辞書２１１の内容が、図１のコンプレッサ１０の辞書１１の内容と同一に維持される。辞書１１の要素４２から４７に関して上で与えた説明は、それぞれ辞書２１１の要素２４２から２４７にも適用される。説明される形で、デコンプレッサ２１０は、コンプレッサ１０によってヒットカウンタ４６および文字カウンタ４７に累積される統計と同一の統計を、ヒットカウンタ２４６および文字カウンタ２４７に累積する。
【００８１】
入力コードバッファ２１２によって、入力２１３で受け取られる入力圧縮コードがバッファリングされる。個々の入力コードは、説明される動作に従って、入力コードバッファ２１２からバス２５０を介して現在コードレジスタ２２０に印加される。デコンプレッサ２１０は、制御バス２５１を介して、入力コードバッファ２１２からの入力コード獲得を制御する。
【００８２】
図２、３、および５の参照を続けて、デコンプレッサ２１０の動作を短く説明する。動作全体を通じて、辞書２１１のヒットカウンタ２４６、除外テーブル２２５のカウンタ配列２７４から２７７、および単一文字テーブル２４４のカウンタ２６１によって、コンプレッサ１０に関して上述した対応するカウンタと同一の統計が、密着した形で累積される。動作の初期化点で、コードカウンタ２２２に、コンプレッサ１０のコードカウンタ２２に当初にセットされる複数文字列コードと同一の最初に使用可能な複数文字列コードがセットされる。さらに、辞書２１１、現在コードレジスタ２２０、前コードレジスタ２２１、前列バッファ２５５、除外テーブルカウンタ２７４から２７７、および単一文字テーブルカウンタ２６１がクリアされる。
【００８３】
デコンプレッサ２１０は、当初に、最初の入力コードを取り出し、出力することによって、最初の前コード情報を与える。上述のコンプレッサ１０の動作によって、最初の入力コードが、単一文字を表し、除外テーブル２２５が、その文字が含まれるか否かを判定するために調べられることを諒解されたい。そうである場合には、少なくとも次の入力コードは、やはり単一文字を表す。したがって、入力コードを取り出し、それによって表される文字を出力する。除外テーブル２２５にない文字を表す最初のそのようなコードが、前コードレジスタ２２１にセットされる。現在コードレジスタ２２０へのコード取出しでは、コードサイズレジスタ２２３内のコードサイズによって決定されるビット数が使用される。除外テーブル２２５に含まれるそのような取り出された文字のそれぞれについて、その文字に関連する除外テーブルカウンタ配列２７４のカウンタを、１つ増分する。除外テーブル２２５にない最初のそのような文字について、その文字に関連する単一文字テーブルカウンタ２６１のカウンタを、１つ増分する。
【００８４】
伸長サイクルは、やはりコードサイズによって決定されるビット数を使用して、デコンプレッサ２１０が、現在コードレジスタ２２０に次の入力コードを取り出すことによって開始される。取り出されたコードを調べて、文字値と等しい、文字値より大きいがコードカウンタ２２２内のコードより小さい、またはコードカウンタ２２２内のコードより小さくないのどれであるかを判定する。
【００８５】
現在コードが、文字値より大きいがコードカウンタ２２２内のコードより小さい場合には、現在コードは、辞書２１１に含まれる複数文字列を表す。現在コードに対応する列の文字を、回復し、出力する。列およびその保存された複数文字プレフィックス列のそれぞれに関連するヒットカウンタ２４６を、１つ増分する。さらに、回復された列の最初の文字に関連する単一文字テーブルカウンタ２６１のカウンタを、１つ増分する。
【００８６】
前コードに対応する列が、現在コードに対応する列の最初の文字と連結されて、延長列が形成される。延長列長が、列長限度を超えず、延長列が、除外テーブル２２５にない場合には、その延長列を、辞書２１１内でコードカウンタ２２２によって割り当てられるコードの場所に保存する。その後、コードカウンタ２２２を増分する。保存された列に関連するヒットカウンタ２４６を、１つ増分する。延長列長が列長限度を超えるか、延長列が除外テーブル２２５に含まれる場合には、その延長列は、保存されず、コードカウンタ２２２は、増分されない。延長列が、除外テーブル２２５に含まれる場合には、延長列に関連する除外テーブルカウンタ配列２７４から２７７のカウンタを、１つ増分する。伸長サイクルは、前コードに現在コードをセットすることによって終わる。
【００８７】
取り出された現在コードが、コードカウンタ２２２のコードより小さくない場合には、取り出された現在コードが、辞書１１（図１）に保存されているが、辞書２１１にまだ保存されていない列を表す。本明細書で説明するデコンプレッサで、取り出された現在コードが、コードカウンタ２２２と等しくなることを諒解されたい。これが発生する場合には、特許で説明された処理に似た例外事例処理を使用する（たとえば、特許文献１参照）。短く言うと、前コードに対応する列を、その最初の文字によって延長し、延長列の文字を、出力する。延長列を、辞書２１１内で、コードカウンタ２２２によって割り当てられるコードに保存する。コードカウンタ２２２を、１つ増分し、保存された列に関連するヒットカウンタ２４６を、１つ増分する。出力され保存されたこの延長列は、現在コードに対応する列である。
【００８８】
現在コードに対応する列を、辞書２１１内でトレースし、列に関連するヒットカウンタ２４６および保存された複数文字プレフィックス列のそれぞれに関連するヒットカウンタ２４６を、１つ増分する。さらに、列の最初の文字に関連する単一文字テーブルカウンタ２６１のカウンタを、１つ増分する。伸長サイクルは、前コードに現在コードをセットすることによって終わる。
【００８９】
入力現在コードが、文字値と等しい場合には、その文字を出力する。前コードに対応する列に、現在コードに対応する文字を連結することによって、延長列を形成する。延長列長が、列長限度を超えず、延長列が、除外テーブル２２５にない場合に、延長列を、辞書２１１内でコードカウンタ２２２によって割り当てられるコードに保存する。その後、コードカウンタ２２２を１つ増分する。保存された列に関連するヒットカウンタ２４６を、１つ増分する。延長列の長さが列長限度を超える場合、または延長列が除外テーブル２２５に含まれる場合には、延長列は、辞書２１１に保存されず、コードカウンタ２２２は、増分されない。延長列が、除外テーブル２２５に含まれる場合には、延長列に関連するカウンタ配列２７４から２７７のカウンタを、１つ増分する。
【００９０】
テストを実行して、辞書２１１が満杯であるか否かを判定する。辞書が満杯でない場合には、除外テーブル２２５を調べて、現在コードに対応する文字がそこに含まれるか否かを判定する。含まれない場合には、前コードに現在コードをセットすることによって、伸長処理が終了する。その文字に関連する単一文字テーブルカウンタ２６１のカウンタを、１つ増分する。
【００９１】
現在コードに対応する文字が、除外テーブル２２５にある場合には、現在コードに対応する文字に関連するカウンタ配列２７４のカウンタを、１つ増分する。この点で、デコンプレッサ２１０は、除外テーブル２２５に含まれる単一文字を表す連続する入力コードを取り出し、出力することによって、上述に似た形で新しい前コード情報を生成する。そのような文字のそれぞれについて、カウンタ配列２７４の関連するカウンタを、１つ増分する。除外テーブルにない単一文字列を表すコードまたは複数文字列を表すコードが取り出された場合には、この取り出された現在コードに対応する列を使用して、新しい前コード情報を提供する。列の１つまたは複数の文字を出力し、前コードに現在コードをセットする。取り出されたコードが、除外テーブルにない単一文字列を表す場合には、単一文字テーブル２２４の関連するカウンタ２６１を、１つ増分する。取り出されたコードが、複数文字列を表す場合には、列および保存されたその複数文字プレフィックス列のそれぞれに関連する辞書２１１のヒットカウンタ２４６を、１つ増分する。さらに、列の最初の文字に関連する単一文字テーブルカウンタ２６１を、１つ増分する。
【００９２】
辞書２１１が満杯である場合には、単一文字テーブルカウンタ２６１、除外テーブル２２５のカウンタ２７４から２７７、および辞書２１１のヒットカウンタ２４６によって累積された統計に従って、除外テーブル２２５から列を削除し、そこに列を追加することによって、除外テーブル２２５を更新する。デコンプレッサ２１０によって、コンプレッサ１０によって除外テーブル２５内で維持される列と同一の列が、除外テーブル２２５内で維持されることを諒解されたい。
【００９３】
除外テーブル２２５を更新した後に、制御は、上述の初期化点に戻り、ここで、適当なリセットおよびクリアが実行される。
【００９４】
図６から９の制御流れ図に、デコンプレッサ２１０によって実行される詳細な動作を示す。制御２３５は、動作の実行を制御するために、状態機械などの適当な回路または適当なソフトウェアを含むとみなされる。
【００９５】
図６を、図２、３、および５の参照を続けながら参照すると、ブロック３００で、図４のブロック９０に関して上述した形との一貫性を有する形で、除外テーブル２２５のクリアまたは初期化のいずれかを行う。ブロック３００は、デコンプレッサ２１０およびコンプレッサ１０が、対応する除外テーブルおよび関連するカウンタ配列に同一の内容を有する状態で処理を開始するようにするために実施される。ブロック３０１で、図４のブロック９１に関して上述した形で、コードカウンタ２２２を初期化する。ブロック３０２で、図４のブロック９２に関して上で説明したように、コードサイズレジスタ２２３を開始コードサイズに初期化する。ブロック３０３で、現在コードレジスタ２２０と、前コードレジスタ２２１と、前列バッファ２５５と、除外テーブルカウンタ２７４から２７７と、単一文字テーブルカウンタ２６１と、ヒットカウンタ２４６および文字カウンタ２４７を含む辞書２１１をクリアする。
【００９６】
ブロック３０４で、コードサイズによって決定されるビット数を使用して、入力圧縮コードを現在コードレジスタ２２０に取り出す。制御が、ブロック３０３からブロック３０４に入る場合には、取り出されたコードが、最初の入力コードである。上で説明したコンプレッサ１０の動作のゆえに、最初に取り出されるコードは、単一文字である。したがって、ブロック３０５で、取り出された現在コードに対応する文字を、デコンプレッサ出力２１４に供給する。
【００９７】
ブロック３０６で、除外テーブル２２５を調べて、現在コードに対応する単一文字列が、除外テーブルに含まれるか否かを判定する。この列は単一文字なので、単一文字のテーブル２７０にアクセスする。現在コードが除外される文字に対応する場合には、ブロック３０６からのＹＥＳ分岐でブロック３０７に進む。ブロック３０７では、現在コードに対応する文字に関連するカウンタ配列２７４の除外テーブルカウンタを、１つ増分する。制御は、ブロック３０７からブロック３０４に戻って、次の入力圧縮コードを現在コードレジスタ２２０に取り出す。ブロック３０４から３０７を含むループは、除外テーブル２２５に含まれない単一文字列を表す入力コードが取り出されるまで実行される。そのような入力コードが取り出された場合に、ブロック３０６からのＮＯ分岐でブロック３１０に進む。
【００９８】
ブロック３０４から３０７で、最初の除外されない列を表すコードを受け取るまで初期入力コードを取り出すことによって、デコンプレッサ２１０に初期前列情報が与えられることを諒解されたい。上で説明したコンプレッサ１０の動作のゆえに、この最初の除外されない列を含むそのような初期入力コードのそれぞれが、単一文字である。デコンプレッサ２１０は、この取り出された現在コードを使用して、説明される形で以下の伸長サイクルの潜在的な保存に関する延長列の基礎になる前列を提供する。
【００９９】
ブロック３１０で、現在コードに対応する文字に関連する単一文字テーブルカウンタ２６１を、１つ増分する。ブロック３１１で、取り出された現在コードに対応する文字を、前列バッファ２５５にシフトし、これを使用して、前の列の１つまたは複数の文字を保持する。それに対応して、ブロック３１２で、前列カウンタ２５７に１をセットする。ブロック３１３で、現在コードレジスタ２２０の現在コードを、前コードレジスタ２２１にセットし、ブロック３１４で、次の入力圧縮コードを現在コードレジスタ２２０に取り出す。
【０１００】
ブロック３１５および３１６は、取り出された現在コードに従って実行される処理のタイプを判定するために含まれている。したがって、制御は、ブロック３１４からブロック３１５に進み、そこで、現在コードが文字値と等しいか否かを判定する。ブロック３１５の機能は、現在コードの値が所定の値未満であるか否かを判定することによって実行することができ、この所定の値は、すべての文字値より大きい。たとえば、既知のコンプレッサ配置およびデコンプレッサ配置では、文字値が、０から特定の値までの範囲内にある。文字値より大きい複数のコード値が、しばしば、制御機能のために予約されている。制御コードより大きいコード値は、複数文字列を表すのに使用される。最初のそのような使用可能なコードが、最初にコードカウンタにセットされる値である。たとえば、ＡＳＣＩＩ環境では、値０から２５５によって、文字を表し、コード２５６および２５７を、制御コードとして使用することができ、コード２５８から４０９５によって、複数文字列を表す。したがって、ＡＳＣＩＩ環境では、ブロック１６２のテストで、現在コードが２５６未満であるか否かを判定する。
【０１０１】
制御コードが、その機能が本発明に関係しないので、圧縮コードストリームに含まれないと見なされることを諒解されたい。したがって、本明細書に記載の処理は、制御コードの存在を無視するとみなされる。
【０１０２】
ブロック３１５で、現在コードが、文字値と等しくない場合に、ブロック３１５からのＮＯ分岐でブロック３１６に進む。現在コードが文字値と等しい場合には、ブロック３１５からのＹＥＳ分岐でブロック３１７に進み、文字処理を実行する。ブロック３１７の文字処理の詳細は、図７に関して説明する。
【０１０３】
ブロック３１６で、現在コードレジスタ２２０の現在コードをコードカウンタ２２２のコードと比較して、現在コードがコードカウンタ未満であるか否かを判定する。ブロック３１６で、現在コードがコードカウンタ未満である場合には、現在コードレジスタ２２０内のコードが、辞書２１１に保存された複数文字列を表す。したがって、ブロック３１６のＹＥＳ分岐でブロック３１８に進み、列処理を実行する。ブロック３１８の列処理の詳細は、図８に関して説明する。
【０１０４】
ブロック３１６で、現在コードレジスタ２２０内のコードが、コードカウンタ２２２のコードと等しい場合には、現在コードが、辞書２１１にまだ保存されていない列を表す。したがって、ブロック３１６からのＮＯ分岐でブロック３１９に進む、例外事例処理を実行する。ブロック３１９の例外事例処理の詳細は、図９に関して説明する。
【０１０５】
ブロック３１８の列処理またはブロック３１９の例外事例処理が終了する場合に、制御は、次の伸長サイクルのためにブロック３１３に戻る。
【０１０６】
ブロック３１７で、現在コードが文字値と等しく、ブロック３１７の文字処理が実行される場合に、処理は、ブロック３３０で継続される。ブロック３３０で、現在コードレジスタ２２０からの文字をデコンプレッサ出力２１４に供給することによって、現在コードに対応する文字を出力する。
【０１０７】
処理は、ブロック３３１に進み、テストを実行して、辞書２１１が満杯であるか否かを判定する。このテストは、コードカウンタ２２２のオーバーフロー出力を検査して、コードカウンタ２２２が、これから説明する図７から９の流れ図の処理中に、その増分の結果としてオーバーフローしたか否かを判定することによって、便利に実行される。
【０１０８】
ブロック３３１で、辞書２１１が満杯でない場合には、ブロック３３１からのＮＯ分岐でブロック３３２に進む。ブロック３３２では、除外テーブル２２５を調べて、現在コードレジスタ２２０の文字が除外テーブル２２５に含まれるか否かを判定する。上でブロック３０６に関して説明したように、便利なことに、単一文字のテーブル２７０を検索して、ブロック３３２の機能を実行することができる。現在コードに対応する文字が、除外テーブル２２５にない場合には、ブロック３３２からのＮＯ分岐でブロック３１０に進む。
【０１０９】
ブロック３３２で、現在コードに対応する文字が除外テーブル２２５に含まれる場合には、ブロック３３２のＹＥＳ分岐でブロック３３３に進む。ブロック３３３では、現在コードに対応する文字に関連するカウンタ配列２７４の除外テーブルカウンタを、１つ増分する。ブロック３３２で、現在コードに対応する文字が、除外テーブル２２５に含まれるので、デコンプレッサ２１０は、前列情報を再初期化する。
【０１１０】
したがって、処理は、ブロック３３３からブロック３３４に進み、次の入力圧縮コードを、現在コードレジスタ２２０に取り出す。ブロック３３５で、現在コードを評価して、それが文字値と等しいか否かを判定する。ブロック３１５に関して説明した処理などの処理を実行して、ブロック３３５の機能を実行する。
【０１１１】
現在コードレジスタ２２０のコードが単一文字を表す場合には、ブロック３３５からのＹＥＳ分岐でブロック３３０に戻って、前列再初期化処理を継続する。ブロック３３５で、現在コードレジスタ２２０のコードが文字値と等しくないが、その代わりに複数文字列を表す場合には、ブロック３３５からのＮＯ分岐で、ブロック３３６の前列再初期化処理に継続する。
【０１１２】
処理のこの点で、ブロック３３５からのＮＯ分岐をたどる場合に、現在コードレジスタ２２０のコードが、辞書２１１に保存された複数文字列を表すことを諒解されたい。ブロック３３２から３３５を介して経験される処理のゆえに、現在コードが、辞書にまだ保存されていない例外事例の列を表すことはできない。
【０１１３】
したがって、ブロック３３６で、列の回復された文字を適当な順序で保持するのに作業バッファ２２７を使用して、辞書２１１から、現在コードレジスタ２２０のコードに対応する列を回復する。前列カウンタ２５７を、列の回復される文字ごとに増分する。本明細書で説明するように、ブロック３３６の列回復機能性を実施するための、辞書から列を回復するのに使用される方法論は、周知である（たとえば特許文献１、特許文献７、または特許文献８参照）。
【０１１４】
さらに、ブロック３３６で、回復された列およびその保存された複数文字プレフィックス列のそれぞれに関連するヒットカウンタ２４６を、１つ増分する。さらに、回復された列の最初の文字に関連する単一文字テーブルカウンタ２６１を、１つ増分する。ブロック３３６の機能性を実行する動作の流れ図を、図１０に関して提供する。
【０１１５】
ブロック３３７で、ブロック３３６で回復された列の文字を、作業バッファ２２７から前列バッファ２５５にシフトする。したがって、説明される形で以下の伸長サイクルでの潜在的な保存について延長列がそれに基づく前列が、提供される。ブロック３３８で、回復された列の文字を、デコンプレッサ出力２１４に供給する。制御は、その後、ブロック３１３に戻って、処理を継続する。
【０１１６】
上記から、ブロック３３２から３３８によって、上述のデコンプレッサ前列再初期化処理が実行され、制御が、ブロック３３２からブロック３１０へ、またはブロック３３８からブロック３１３へのいずれかで戻って、伸長処理が継続されることを諒解されたい。前列再初期化は、説明した形で実行され、その結果、デコンプレッサ２１０が、コンプレッサ１０と同期した状態を継続するようになる。
【０１１７】
ブロック３３１で、辞書２１１が満杯と判定される場合には、ブロック３３１からのＹＥＳ分岐でブロック３５０から３５２に進み、除外テーブル２２５を更新する。ブロック３５０から３５２では、それぞれ、図４のブロック１４１から１４３と同一の機能性が実行され、これらに関して上で示した説明が、ブロック３５０から３５２にも適用される。しかし、コンプレッサ要素を示すのに使用された符号は、対応するデコンプレッサ要素を表すために２００だけ増やされている。
【０１１８】
ブロック３５０から３５２で除外テーブル２２５を更新した後に、制御はブロック３０１に戻って、列による辞書２１１の選択的な充てんのさらなるサイクルの開始に先立つ適当なリセットおよびクリアを開始する。
【０１１９】
上で説明したように、辞書満杯テストブロック３３１は、文字処理３１７が実行されるデコンプレッサ処理分岐に配置される。これは、図４のコンプレッサ流れ図で、コンプレッサの現在文字レジスタ２１の不一致文字が、ブロック１２８でコンプレッサの辞書１１が満杯と判定される場合にブロック１４０で出力されるからである。
【０１２０】
図７を、図２、３、５、および６の参照を続けながら参照すると、図６の文字処理ブロック３１７の詳細が示されている。処理は、図６のブロック３１５からブロック３６０に進んで、延長列レジスタ２２６をクリアする。
【０１２１】
処理は、ブロック３６１に継続され、ここで、現在コードに対応する文字によって延長された前コードに対応する列を、延長列レジスタ２２６にシフトして、延長列を形成する。便利なことに、前コードに対応する列は、前列バッファ２５５に保持され、現在コードに対応する文字は、現在コードレジスタ２２０に保持される。ブロック３６１の列連結機能は、前列バッファ２５５および現在コードレジスタ２２０の内容を延長列レジスタ２２６に適当にシフトすることによって簡単に実行される。
【０１２２】
制御は、ブロック３６２から３７０で継続され、ここで、それぞれ図４のブロック１２０から１２７および１３５に関して上述した処理に類似する処理が実行される。短く言うと、ブロック３６２で、テストを実行して、ブロック３６１で形成された延長列の長さが、列長限度レジスタ２３４に保存された列長限度を超えるか否かを判定する。ブロック３６１で、延長列が、前列に単一文字を連結することによって形成されるので、量（前列カウント＋１）によって、延長列の長さが与えられる。前列カウントは、前列カウンタ２５７から導出される。
【０１２３】
ブロック３６３で、延長列の長さに従って、除外テーブル２２５（図３）のテーブル２７０から２７３の適当な１つを調べる。ブロック３６４の辞書更新機能性は、上で説明したように周知であるが、ここで、前コードが、前コードレジスタ２２１から導出され、現在コードに対応する文字が、現在コードレジスタ２２０から導出される。ブロック３６５および３６６では、関連するヒットカウンタ２４６を増分し、関連する文字カウンタ２４７に、保存された延長列の長さをセットする。
【０１２４】
延長列の長さが、列長限度を超えず（ブロック３６２）、延長列が除外テーブル２２５に含まれない（ブロック３６３）場合には、延長列を、辞書２１１のコードカウンタ２２２によって割り当てられるコードに保存し（ブロック３６４）、コードカウンタ２２２を増分する（ブロック３６９）。しかし、ブロック３６２または３６３で、延長列が列長限度を超えるか、延長列が除外テーブル２２５に含まれる場合に、ブロック３６２からの関連するＹＥＳ分岐または、ブロック３６３からの関連するＹＥＳ分岐およびブロック３７０を介して、ブロック３６４から３６９の処理をバイパスする。これが発生する場合には、延長列が、辞書２１１に保存されず、コードカウンタ２２２が、増分されない。
【０１２５】
延長列が、除外テーブル２２５に含まれる場合に、ブロック３６３からのＹＥＳ分岐でブロック３７０に進む。ブロック３７０では、カウンタ配列２７４から２７７の関連する除外テーブルカウンタを、１つ増分する。
【０１２６】
ブロック３６２から３６９の処理は、デコンプレッサ２１０の辞書２１１およびコードカウンタ２２２が、コンプレッサ１０の辞書１１およびコードカウンタ２２と同期化されたままになるようにするために実行される。
【０１２７】
延長列が、保存されるか辞書２１１から除外されるかにかかわらずに、処理はブロック３７１で継続される。ブロック３７１では、前列バッファ２５５および前列カウンタ２５７をクリアする。処理は、上で説明した図６のブロック３３０で継続される。
【０１２８】
図８を、図２、３、５、６、および７の参照を続けながら参照すると、図６の列処理ブロック３１８の詳細が示されている。図６のブロック３１６から、処理はブロック３８０に入り、ここで、現在列カウンタ２５６、現在列バッファ２５４、および延長列レジスタ２２６をクリアする。
【０１２９】
処理は、ブロック３８１に進み、ここで、現在コードレジスタ２２０のコードに対応する列を、列の回復された文字を適当な順序で保持するのに作業バッファ２２７を使用して、辞書２１１から回復する。さらに、関連するカウンタを増分して、適当な統計を累積する。ブロック３８１の機能性は、実質的に図６のブロック３３６の機能性と同一であり、ブロック３３６に関して上で与えた説明は、全般的にブロック３８１に適用される。ブロック３３６では、前列カウンタ２５７が増分されるが、ブロック３８１では、現在列カウンタ２５６が増分されることに留意されたい。ブロック３８１の機能性の詳細は、図１０に関して下で与える。
【０１３０】
ブロック３８２で、ブロック３８１で回復された列の文字を、作業バッファ２２７から現在列バッファ２５４にシフトする。ブロック３８３で、回復された列の文字を、デコンプレッサ出力２１４に供給する。
【０１３１】
ブロック３８４から３９３は、上で図７に関して説明しためいめいのブロック３６１から３７０に類似した機能を実行し、上でブロック３６１から３７０に関して与えた説明は、全般的にブロック３８４から３９３に適用される。しかし、ブロック３８４で、延長列が、前コードに対応する列に現在コードに対応する列の最初の文字を連結することによって形成されることを諒解されたい。延長文字は、便利なことに、現在列バッファ２５４から入手される。さらに、ブロック３８７で、辞書２１１に保存された延長列に、前コードおよび現在コードに対応する列の最初の文字が含まれる。
【０１３２】
処理は、次に、ブロック３９４に入り、ここで、現在列バッファ２５４に保持された列を、前列バッファ２５５にセットする。ブロック３９５で、現在列カウンタ２５６のカウントを、前列カウンタ２５７にセットする。ブロック３９４および３９５の処理は、次の伸長サイクルで使用される前列情報をデコンプレッサ２１０に与えるために実行される。その後、処理は、図６のブロック３１３に戻る。
【０１３３】
図９を、図２、３、５、６、７、および８の参照を続けながら参照すると、図６のブロック３１９の例外事例処理の詳細が示されている。ブロック３１９の例外事例処理は、現在コードがコードカウンタと等しい場合に実行される。これは、現在コードが、辞書１１に保存されたばかりの列を表し、コンプレッサ１０によって突き合わされたが、まだデコンプレッサ２１０の辞書２１１に保存されていない場合に発生する。例外事例処理は、ＬＺＷデータ圧縮伸長の分野で周知であるが（たとえば、特許文献１参照）、この実施形態では、便利なことに、説明される形で、好ましい実施形態の次の伸長サイクルでの使用のために前列情報が提供される。
【０１３４】
したがって、処理は、図６のブロック３１６からブロック４１０に進む。ブロック４１０で、前コードに対応する列を、前コードに対応する列の最初の文字によって延長する。この機能は、便利なことに、前コードに対応する列の文字を保持する前列バッファ２５５内で実行される。延長され、前列バッファ２５５に保持される列が、図６のブロック３１４で現在コードレジスタ２２０に取り出される現在コードに対応する列であることを諒解されたい。したがって、ブロック４１１で、現在は前列バッファ２５５に保持されている列の文字を、前列バッファ２５５からデコンプレッサ出力２１４に供給する。
【０１３５】
ブロック４１２で、前コードレジスタ２２１からの前コードに前コードに対応する列の最初の文字を連結した列を保存することによって、辞書２１１を更新する。延長文字は、便利なことに、前列バッファ２５５で提供される。この列は、上で説明したように、現在コードに対応するが、辞書２１１内でコードカウンタ２２２によって割り当てられるコードに保存される。前に説明したように、図９の処理は、現在コードがコードカウンタと等しい場合に実行される。
【０１３６】
ブロック４１３で、ブロック４１２で保存された列に関連するヒットカウンタ２４６を、１つ増分する。ブロック４１４で、前列カウンタ２５７を１つ増分し、ブロック４１５で、ブロック４１２で保存された列に関連する文字カウンタ２４７に、前列カウンタ２５７の増分されたカウントをセットする。この前列カウンタ２５７の増分されたカウントが、ブロック４１０で延長されブロック４１２で辞書に保存された列の長さに対応することを諒解されたい。
【０１３７】
処理はブロック４１６に進み、辞書２１１内の現在コードに対応する列をトレースし、列およびその保存された複数文字プレフィックス列のそれぞれに関連するヒットカウンタ２４６に１を加算する。さらに、列の最初の文字に関連する単一文字テーブルカウンタ２６１を、１つ増分する。ブロック４１６の処理は、ヒットカウンタ２４６および単一文字テーブルカウンタ２６１によって維持される統計が、コンプレッサ１０によって累積される統計と同期化されたままになるようにするために実行される。ブロック４１６の機能性は、列文字が回復されず、現在列カウンタが増分されないことを除いて、図８のブロック３８１の機能性に類似する。図１０の詳細な流れ図は、ブロック４３２、４３３、４３７、および４３８がバイパスされることを除いて、ブロック４１６の実施に使用することができる。
【０１３８】
ブロック４１０の処理によって、前列バッファ２５５が、現在コードに対応する列を保持し、この列が、前コードに関連する列より１文字長いことを諒解されたい。したがって、ブロック４１０の処理およびブロック４１４の処理によって、前列カウンタ２５７が１つ増分されるが、前列バッファ２５５および前列カウンタ２５７が、便利なことに、次の伸長サイクルに関する適当な前列情報を提供する。
【０１３９】
処理は、ブロック４１７から４１９で継続され、コードカウンタ２２２が、図４のブロック１２５から１２７に関して上述した形で増分される。その後、処理は、図６のブロック３１３に戻る。
【０１４０】
上で与えた説明から、制御が例外事例処理ブロック３１９に入る場合に、前コードまたは現在コードに対応する列も、前コードに対応する列の最初の文字も、除外テーブル２２５にないことを諒解されたい。したがって、ＬＺＷ例外事例処理は、列除外なしで図９に関して説明したように実行することができる。
【０１４１】
ブロック３０１、３０２、３０４、３０５、３１３から３１６、３６４、３６７から３６９、３８３、３８７、３９０から３９２、４１１、４１２、および４１７から４１９に、図６から９の基礎となるＬＺＷデータ伸長処理が示されていることを諒解されたい。したがって、ＬＺＷデータ伸長のすべての既知の実施形態を、これらのＬＺＷデータ圧縮態様を実施するのに使用することができる。
【０１４２】
図１０を、図６、８、および９の参照を継続しながら参照すると、図６のブロック３３６、図８のブロック３８１、および図９のブロック４６１で実行される動作の詳細が示されている。括弧なしの図１０は、図８のブロック３８１に適用され、括弧つきの図１０は、図６のブロック３３６に適用される。前述から、図８のブロック３８１で、現在列カウンタ２５６が増分され、図６のブロック３３６で、前列カウンタ２５７が増分されることを諒解されたい。
【０１４３】
したがって、ブロック４３０で、現在コードに対応する列に、辞書２１１内でアクセスする。ブロック４３１で、アクセスした列に関連するヒットカウンタ２４６を、１つ増分する。ブロック４３２で、アクセスした列のフィールド２４４のデータ文字を、作業バッファ２２７に転送する。ブロック４３３で、現在列カウンタ２５６（前列カウンタ２５７）を１つ増分する。ブロック４３４で、アクセスした列のフィールド２４３のプレフィックスコードをテストして、それが文字値と等しいか否かを判定する。そうでない場合には、ブロック４３４からのＮＯ分岐でブロック４３５に進み、辞書２１１内でプレフィックスコードに対応する列にアクセスする。その後、制御はブロック４３１に戻る。
【０１４４】
ブロック４３１から４３５を含むループは、ブロック４３４で、アクセスした列のプレフィックスコードが文字値と等しくなるまで実行される。これが発生した場合には、ブロック４３４のＹＥＳ分岐でブロック４３６に進み、文字値に関連する単一文字テーブルカウンタ２６１を、１つ増分し、ブロック４３７で、アクセスした列のプレフィックスコードフィールド２４３の文字を、作業バッファ２２７に転送する。ブロック４３８で、現在列カウンタ２５６（前列カウンタ２５７）を１つ増分する。
【０１４５】
上で説明したように、図１０の流れ図は、ブロック４３２、４３３、４３７、および４３８をバイパスして、図９のブロック４１６を実施するのに使用することもできる。
【０１４６】
図１０の論理を、図４のブロック１４２および図６のブロック３５１で除外テーブルでの保存のために辞書から列を抽出するのに使用することもできる。これに関して、ブロック４３１、４３３、４３６、および４３８が、使用されなくなる。この形で、列の文字を、除外テーブルの適当な１つへの転送のために作業バッファに置くことができる。
【０１４７】
図６から９で、ブロック３０７、３１０、３３３、３３６、３６０、３６５、３７０、３８１、３８８、３８９、３９３、４１３、４１５、および４１６の動作によって、デコンプレッサのヒットカウンタ２４６、文字カウンタ２４７、単一文字テーブルカウンタ２６１、および除外テーブルカウンタ２７４から２７７が、コンプレッサ１０の対応するカウンタで維持される統計と同一の統計を累積することを諒解されたい。さらに、図６で、ブロック３５０から３２２の動作によって、デコンプレッサの除外テーブル２７０から２７３が、コンプレッサ１０の対応する除外テーブルと同期化されたままであることを諒解されたい。デコンプレッサ２１０は、辞書、除外テーブル、単一文字テーブル、およびこれらの間のエスケープコードの転送を必要とせずに、コンプレッサ１０と同期化されたままになる。
【０１４８】
上述のコンプレッサ実施形態およびデコンプレッサ実施形態の動作の例を、図１１から１６に関して提供する。小さいアルファベットサイズおよび辞書容量が、この例で使用され、その結果、辞書充てんおよび除外テーブル更新の完全なサイクルを示すことができるようになっている。２ビットの文字サイズを有する４文字アルファベットを、ａ、ｂ、ｃ、およびｄと表される文字と共に使用する。２ビット文字の数値は、０、１、２、および３である。例の辞書は、４ビット幅のアドレスを必要とする１６個の位置を有する。したがって、コンプレッサおよびデコンプレッサのコードカウンタは、４ビット幅であり、オーバーフローに先立って１５までカウントすることができる。コードカウンタが１５のカウントである場合に、次の１の増分によって、カウンタオーバーフローがもたらされる。
【０１４９】
文字値は０から３なので、コードカウンタは、５のカウントに初期化される。４のカウントは、この例では使用されず、制御コードとして予約することができる。したがって、複数文字列コードは、コード５から１５である。列長限度は、４として選択される。除外テーブル閾値、辞書列閾値、および単一文字テーブル閾値は、それぞれ２として選択される。
【０１５０】
例の辞書は、１６個の列の容量だけを有するが、実用的な実施形態で、辞書が、かなり大きく、たとえば４０９６個の列を保持することを諒解されたい。
【０１５１】
図１１は、当初は空の除外テーブルを使用するコンプレッサ動作の例である。図１１の辞書充てんサイクルの終りに、除外テーブルは、図４のブロック１４１から１４３に関して説明した除外テーブル更新判断基準による、図１１で累積された統計を使用して、列を移植される。図１２は、図１１の動作によって生成される除外テーブルを示す図である。図１３は、コンプレッサのもう１つの動作の例であるが、図１２の除外テーブルが使用される。図１４に、やはり図４のブロック１４１から１４３の除外テーブル更新判断基準を使用して、図１３の動作の例からもたらされる除外テーブルを示す。
【０１５２】
図１５は、図１１の圧縮コード出力に応答するデコンプレッサの動作の例であり、デコンプレッサ除外テーブルは、当初は空である。図１５に示された動作から、デコンプレッサは、図１２の除外テーブルをもたらしたコンプレッサと同一の統計を累積する。デコンプレッサ除外テーブル更新判断基準は、図６のブロック３５０から３５２に関して説明した。図１６は、図１３の圧縮コード出力に応答するが、図１２の除外テーブルを使用するデコンプレッサのもう１つの動作の例である。図１６の動作によって、デコンプレッサは、図１４の除外テーブルも生成する。
【０１５３】
図１１および１５で、コンプレッサおよびデコンプレッサが、空の除外テーブルを用いて動作を開始するので、これらの図には除外テーブルの列がない。コンプレッサおよびデコンプレッサは、空の除外テーブルの列に出会うことができない。図１１から１６で、コードカウンタが、５のコードに初期化されるので、コードサイズは、３ビットに初期化される。動作流れ図の適当なブロックで、コードカウンタが７のカウントを必要とする場合に、３から４ビットへのコードサイズの増加が必要になる。
【０１５４】
図１から４の参照を継続しながら図１１を参照すると、図４の流れ図によるコンプレッサ１０の動作の例が示されている。図１１の最上部に、入力データ文字ストリームが示され、ここで、順次文字が、文字シーケンス番号によって識別される。これは、この例のステップを介する文字の進行に追従するのを容易にするために行われる。シーケンス番号が、文字識別のために示され、実際のデータ文字ストリームに現れないことを諒解されたい。
【０１５５】
この例は、十分にそのままで明らかであり、実行されるアクションが、左端の列に示され、そのアクションに参加する図４のブロックが、右端の列に示されている。延長文字レジスタの列には、アクションで検討される列が示され、延長列カウンタの列には、列の文字数が示されている。あるアクションで、図４のブロック１１４から、一致する列に関連するヒットカウンタの増分が示される場合に、辞書の列で括弧を使用して、一致する列を示す。図１１のアクションでは、除外テーブル２５が空なので、除外テーブルを含めることによって辞書１１から除外される列はない。
【０１５６】
アクション１で、ブロック９１（図４）で、コンプレッサのコードカウンタに、５の最初に使用可能なコードをセットし、ブロック９８で、文字「ａ」に関連する単一文字テーブルカウンタを１つ増分する。
【０１５７】
図１１のアクションを介する基礎となるデータ圧縮処理では、基本的に、ＬＺＷ方法論が使用されるが、図示のように、列統計が、辞書および単一文字テーブルに累積される。たとえば、アクション２で、列「ａａ」が文字コード５に保存され、ブロック１２３で、関連するヒットカウンタに１がセットされ、ブロック１２４で、関連する文字カウンタに２がセットされる。アクション３から５で、列「ａ」および「ａａ」が突き合わされ、延長列「ａａａ」が保存される。アクション３で、一致した文字「ａ」に関連する単一文字テーブルカウンタが、ブロック９８で１つ増分される。アクション４で、列「ａａ」が、辞書内で突き合わされ、関連するヒットカウンタが、１つ増分される。アクション５で、列「ａａ」のコード５が出力される。列「ａａａ」が、プレフィックスコードフィールドにプレフィックスコード５を保存し、延長文字「ａ」を文字フィールドに保存することによって、６の列コードを用いて辞書に保存される。ブロック１２３（図４）で、保存された列に関連するヒットカウンタに、１がセットされ、ブロック１２４で、関連する文字カウンタに、延長列カウンタのカウントがセットされる。
【０１５８】
アクション３３で、５の列長さが列長限度（たとえば４にセットされる）を超えるので、列「ａｂｃａｂ」が、除外される。したがって図４のブロック１２０で、ＹＥＳ分岐をたどって、辞書保存およびコードカウンタ増分をバイパスする。しかし、最長一致「ａｂｃａ」のコード１４は、出力される。
【０１５９】
アクション３５で、列「ｂｃ」が、辞書の最後の空の位置に保存され（ブロック１２２）、アクション３６で、コードカウンタが増分されて、オーバーフローする（ブロック１２７）。アクション３６で、現在文字「ｃ」が出力される（ブロック１４０）。
【０１６０】
図４のブロックに関する図１１のアクションのより詳細な説明は、簡単に明白になり、説明を短くするために示されない。
【０１６１】
図４および１１を参照しながら図１２を参照すると、図１２の除外テーブル２５は、図４のブロック１４１から１４３で図１１の累積された統計からの図示の列を移植される。除外テーブル２５は、図１１の処理には参加しなかったので、ブロック１４１が、上の説明のようにバイパスされる。図４のブロック１４２に関して、図１１のアクション３５で、列「ｂｃ」に関連するヒットカウンタの１のカウントによって示されるように、列「ｂｃ」に１回だけ出会ったことが観察される。関連する文字カウンタは、２のカウントを有する。ヒットカウンタのカウントは、辞書列閾値（たとえば２にセットされる）より小さいので、列「ｂｃ」は、次の辞書充てんサイクルで除外される文字対の除外テーブル７１に保存される。同様に、図１１のアクション２４によって、列「ｃａ」について同一の累積された統計が示され、この列も、テーブル７１に保存される。類似する形で、図１２のテーブル７２および７３に保存される列は、図１１のアクション５、８、および１９で辞書統計を調べることによって得られる。
【０１６２】
図４のブロック１４３に関して、図１２のテーブル７０は、図１１のアクション２３で、関連する統計からの単一文字列「ｃ」を移植される。
【０１６３】
図１、４、１１、および１２の参照を継続しながら図１３を参照すると、図４の流れ図によるコンプレッサ１０の動作のもう１つの例が示されている。図１３は、図１２の除外テーブルを使用する、図１１の動作の継続である。図１３のフォーマットは、実質的に図１１と同一であり、上で図１１に関して与えた説明を、適用可能である。図１３の動作では、除外テーブル統計が累積されるので、除外テーブルの列および関連する除外テーブルカウンタの列が含まれる。
【０１６４】
図１３に示された処理は、実質的に、図１１に関して上述した処理と同一であるが、統計が、辞書のヒットカウンタおよび文字カウンタならびに単一文字テーブルカウンタに累積される。さらに、統計は、アクション５、８、１９、２３、３４から３６、４１、４４、および５５に示されているように、除外テーブルカウンタに累積される。これらのアクションでは、図１２の除外テーブルで出会う、図４のブロック９５および１２１に示された列が、辞書への保存から除外され、コードカウンタが、増分されない。そうでなければこれらの列によって奪われたはずのコードカウンタからのコードが、より有用である傾向がある可能性がある他の列の保存に使用される。
【０１６５】
除外テーブルに基づく辞書からの列の除外が、ＬＺＷ処理と絡み合わされ、その結果、列が除外される場合に、列が、列プレフィックスによって達成された圧縮のどれからでも利益を得るようになることを諒解されたい。これは、除外される列のプレフィックスのコードが、圧縮サイクルの最長一致として図４のブロック１１６で出力されるからである。
【０１６６】
図１１に関して上述した形で、アクション６４および６５で、最後の列が、辞書に保存され、コードカウンタが、増分され、図４のブロック１２８で検出されるカウンタオーバーフローがもたらされる。アクション６５で、現在文字レジスタの文字が、図４のブロック１４０で出力される。
【０１６７】
図１、４、１２、および１３の参照を継続しながら図１４を参照すると、図１３で累積された統計から、図４のブロック１４１から１４３の更新処理からもたらされる更新された除外テーブル２５が示されている。ブロック１４１から１４３の更新動作は、図４および１１に関して上述した。図１３の辞書充てんサイクルの完了の後に、ブロック１４１から１４３によって、図１２に示された除外テーブル２５の状況を修正して、図１４に示された除外テーブル２５を提供する。
【０１６８】
図４のブロック１４１で、関連する除外テーブルカウンタが除外テーブル閾値（たとえば、２にセットされる）より大きい列が、除外テーブルから削除される。したがって、図１３のアクション３６および４４から、列「ｃ」および「ａａａ」が、図１２に示た除外テーブルから削除される。
【０１６９】
図４のブロック１４２で、関連するヒットカウンタが辞書列閾値（たとえば、２にセットされる）より小さい列が、辞書から除外テーブルに保存される。したがって、図１３のアクション３８、６２、６４、および５１から、列「ｄａ」、「ｂｂ」、「ｂｄ」、および「ａｂａｂ」が、図１４の除外テーブルに追加されている。
【０１７０】
図４のブロック１４３で、関連する単一文字テーブルカウンタが単一文字テーブル閾値より小さい非０カウントを有する、単一文字テーブルからの単一文字列が、除外テーブルに保存される。たとえば、単一文字テーブル閾値に、２をセットすることができる。したがって、図１３のアクション３７から、列「ｄ」が、図１４の除外テーブルに追加されている。
【０１７１】
図２、３、５、および６から９の参照を続けながら図１５を参照すると、図６から９の流れ図によるデコンプレッサ２１０の動作の例が示されている。図１５のフォーマットは、全般的に図１１に類似し、図１１に関して上で与えた説明は、図１５に適用可能である。図１５の最上部の入力圧縮コードストリームは、図１１に示されたコンプレッサ出力である。図１５の出力が、図１１の最上部に示された回復されたデータ文字ストリームであることが観察される。さらに、図１１および１５のめいめいの辞書の列から、デコンプレッサ２１０が、コンプレッサ１０の辞書１１と同一のコードに同一の列が保存された辞書２１１の内容を構成することが観察される。また、図１５で、辞書のヒットカウンタおよび文字カウンタならびに単一文字テーブルカウンタによって、図１１と同一の列に関する同一の統計が累積されることを諒解されたい。図１５の延長列レジスタの列に、デコンプレッサ辞書での保存に関してアクションで検討される列が示されている。図１５の動作の例では、空の除外テーブルが使用される（ブロック３００）。アクションで、図６から９のブロック３３６、３８１、および４１６から、回復された列またはトレースされる列およびその複数文字プレフィックス列に関連するヒットカウンタの増分が示される場合に、辞書の列で括弧を使用して、そのような列を示す。
【０１７２】
図１５のアクションを介する基礎となるデータ圧縮処理では、基本的に、ＬＺＷ方法論が使用されるが、列統計が、図示のように、辞書および単一文字テーブルに累積される。たとえば、アクション２１および２２で、図８のブロック３８１に関して、統計が、回復された列「ａｂｃ」に関して累積される。アクション２５から２８で、図９のブロック４１６に関して、トレースされる列「ａｂｃａ」に関して統計が累積される。
【０１７３】
アクション２９で、列「ａｂｃａｂ」は、５という列長が、列長限度（たとえば４にセットされる）を超えるので、除外される。したがって、図７のブロック３６２で、ＹＥＳ分岐をたどって、辞書保存およびコードカウンタ増分をバイパスする。しかし、この列は、アクション２５および２９に示されているように、出力で正しく回復される。
【０１７４】
アクション３０で、列「ｂｃ」が、辞書の最後の空の位置に保存され（ブロック３６４）、アクション３１で、コードカウンタが増分されて、オーバーフローする（ブロック３６９）。アクション３１で、現在コードに対応する文字が出力される（ブロック３３０）。
【０１７５】
アクション３１で、図６のブロック３３１で辞書２１１が満杯と判定される場合に、デコンプレッサ２１０は、ブロック３５０から３５２を実行して、図１２に示されているように除外テーブル２２５に移植する。除外テーブル更新は、図４のブロック１４１から１４３に関する上の説明、図１１の動作の例、および図１２に関して与えた説明と同一である。適当に累積された統計が、図１５のアクション５、６、１７、２０、２３、および３０に示されている。
【０１７６】
図２、３、５、６から９、１２、および１５の参照を継続しながら図１６を参照すると、図６から９の流れ図によるデコンプレッサ２１０の動作のもう１つの例が示されている。図１６は、図１２の除外テーブル２２５を使用する図１５の動作の継続である。図１６のフォーマットは、図１５のフォーマットと実質的に同一であり、図１５に関して上で与えた説明を適用可能である。図１６の動作では、除外テーブル統計が累積されるので、除外テーブルの列および関連する除外テーブルカウンタの列が含まれる。
【０１７７】
図１６の最上部の入力圧縮コードストリームは、図１３に示されたコンプレッサ出力である。図１６の出力が、図１３の最上部に示された回復されたデータ文字ストリームであることが観察される。さらに、図１３および１６のめいめいの辞書の列から、デコンプレッサ２１０が、コンプレッサ１０の辞書１１と同一のコードに同一の列が保存された辞書２１１の内容を構成することが観察される。さらに、図１６の動作により、辞書のヒットカウンタおよび文字カウンタならびに単一文字テーブルカウンタおよび除外テーブルカウンタによって、図１３に関する対応するカウンタと同一の統計が累積される。
【０１７８】
さらに、図１６に示された処理は、実質的に図１５に関して上述した処理と同一であるが、統計が、辞書のヒットカウンタおよび文字カウンタならびに単一文字テーブルカウンタに累積される。さらに、図１６では、統計が、アクション５、６、１６、１８、２５から２７、３２、３４、および４５に示されているように、除外テーブルカウンタに累積される。これらのアクションで、図１２の除外テーブルで出会う列が、図６から９の適当なブロックで、辞書への保存から除外され、コードカウンタが増分されない。
【０１７９】
アクション４９および５０で、図１５に関して上で説明した形で、最後の列が、辞書に保存され、コードカウンタが増分され、図６のブロック３３１で検出されるカウンタオーバーフローがもたらされる。アクション５０で、現在コードに対応する文字が、図６のブロック３３０で出力されている。
【０１８０】
図１６の辞書充てんサイクルが完了した後に、ブロック３５０から３５２によって、図１２に示された除外テーブル２２５の状況を修正して、図１４に示された除外テーブル２２５をもたらす。図６のブロック３５０から３５２の動作は、図４にブロック１４１から１４３に関して図１４で上述した動作と同一である。
【０１８１】
図６のブロック３５０に関して、図１６のアクション２７および３４によって、図１２の除外テーブルからの上で説明した列の削除に関する統計がもたらされる。図６のブロック３５１に関して、図１６のアクション、２９、４０、４７、および４９によって、辞書から除外テーブルへの上述の列の追加に関する統計がもたらされる。図６のブロック３５２に関して、図１６のアクション２７によって、単一文字テーブルから除外テーブルへの上で説明した列の追加に関する統計がもたらされる。
【０１８２】
図１７を参照すると、除外テーブル２５および２２５に列の初期の組を移植する自動手順が与えられる。除外テーブルに移植する列を選択するのに使用されるツリーデータ構造４５０が示されている。データ構造４５０は、めいめいのルートノード４５４から４５６から始まる複数のリンクリストツリー４５１から４５３からなる。ルートノードは、圧縮が実行されるアルファベットのめいめいの文字を表す。ツリー４５２および４５３に関して、図を簡単にするために、ルートノード４５５および４５６だけが示されている。ツリー４５１などの各ツリーは、さらに、リンクされた子孫ノード４６０から４６５からなる。各ノードは、列の１文字を表し、列は、列の文字を表す、ルートノードからのリンクされたノードを介するパスによってツリーに保存される。たとえば、列「文字１、文字ｉ、文字ｋ」は、ノード４５４、４６０、および４６１によって表される。もう１つの例として、部分列「文字１、文字ｉ」が、ノード４５４および４６０によって保存され、列「文字１、文字ｊ」が、ノード４５４および４６３によって保存されることを諒解されたい。
【０１８３】
ツリー４５１から４５３は、レベル１、レベル２、レベル３、．．．、レベルＬと表されるレベルに配置される。ツリーのルートノードは、レベル１である。ルートの子ノードは、レベル２である。孫ノードは、レベル３であり、葉ノードは、レベルＬである。ツリーの深さは、ルートからレベルＬノードへのパスに、列長限度レジスタ３４（図１）に保存された列長限度パラメータと等しい文字数を有する列が保存されるように選択される。したがって、レベル１のルートノードが、単一文字列を表し、レベル２のノードが、文字対を表し、レベル３のノードが、文字３つ組を表し、レベルＬのノードが、列長限度文字の列を表すことを諒解されたい。
【０１８４】
ノードには、そのノードによって表されるめいめいの文字を保存するめいめいの文字フィールド４６６（ａからｉ）が含まれる。ノードには、さらに、説明される形でめいめいのノードが訪問される回数のめいめいのカウントを維持するめいめいのカウンタ４６７（ａからｉ）が含まれる。
【０１８５】
除外テーブルに移植される列を識別するのにツリーデータ構造４５０が使用される形を、これから説明する。圧縮が実行されるデータの大きいサンプルが供給される。データ構造のノードは、データサンプルの文字が読み取られる際に作成される。
【０１８６】
サンプルの最初の文字が読み取られ、適当なルートノードが、その文字フィールド４６６に文字値をセットし、そのカウンタ４６７に１をセットすることによって作成される。最初の文字に続くＬ−１個の文字が、作成されたルートノードから、レベル２からレベルＬまでの子孫ノードのリンクされたチェーンを作成し、その文字フィールド４６６にめいめいの文字値をセットすることによって、ツリーに順次読み取られる。これらの作成されたノードのカウンタ４６７に、１をセットする。
【０１８７】
同じ手順が、繰り返されるが、今回は、サンプルの第２の文字と、第２文字に続くＬ−１個の文字を使用し、適当なルートノードとそこからの適当なノード子孫を作成する。この処理が継続される際に、適当なルートノードおよび子孫ノードが、データ構造に読み取られる列の一部またはすべての文字について既に作成されている場合があることを諒解されたい。文字が読み取られる場合にその文字のノードが既に存在する場合には、そのノードのカウンタ４６７を１つ増分する。この処理は、サンプルの文字列のすべてがデータ構造４５０に読み取られるまでサンプルの各文字について継続される。
【０１８８】
上で説明した処理によって、単一文字列、文字対、文字３つ組から列長限度文字を有する列までを含むサンプル内の列のすべてが、データ構造４５０のツリー４５１から４５３に保存され、各列の出現の数が、関連するカウンタ４６７によって与えられる。列は、ルートから葉に向かってデータ構造４５０のツリーに読み込まれるので、ノードのカウンタ４６７のカウントは、その子孫ノードのすべてのカウンタ４６７のカウント以上になる。
【０１８９】
図２および１７の参照を続けると、データ構造４５０は、そこに読み込まれたサンプルのすべての列と共に、下記の形で除外テーブル２５に移植するのに使用される。テーブル７０に移植される単一文字列は、データ構造４５０のレベル１ルートノードから導出される。テーブル７１に移植される文字対列は、上で説明したように、文字対列を表すレベル２ノードから導出される。同様に、テーブル７２に移植される文字３つ組は、レベル３ノードから導出され、テーブル７２に続くテーブルは、ツリー構造４５０の対応するレベルから移植される。最後のテーブル７３は、レベルＬから導出された列から移植される。
【０１９０】
列は、関連するカウンタ４６７のカウントが所定の閾値未満である場合に、テーブルへの移植に使用される。この閾値は、データ構造４５０全体で同一とすることができ、あるいは、異なるレベルで異なる閾値を使用することができる。閾値は、カウンタ４６７のすべてに反映される出現の数の実際の分布に基づいて確立される。閾値が高ければ、除外テーブル２５に保存される列の数が多くなり、したがって、辞書への保存から除外される列の数が多くなる。
【０１９１】
処理されるテーブルに移植される列は、選択されたノードからリンクするノードを介してルートまでツリーを上向きにトレースすることによって、関連するレベルの選択されたノードから導出される。たとえば、ノード４６５がレベルＬから選択されて、テーブル７３に移植されるそれに関連する列が提供される場合に、ツリー４５１が、ノード４６５からノード４６４、４６０、および４５４を介してアクセスされて、表７３に移植される列「文字１、文字ｉ、文字ｍ、．．．、文字ｐ」がもたらされる。
【０１９２】
データ構造４５０からの列の検索は、すべてのノードが多くとも１つの上位ノードから入る分岐を有するという事実によって容易になる。したがって、ノードからルートへの逆方向トレースは、ノードの一意の組をトラバースし、これによって、除外テーブルのテーブルに移植される一意の列が提供される。
【０１９３】
図１および４の参照を継続しながら図１８を参照すると、同一の符号が図４に関する同一の要素を示すが、入力データ文字ランに関する図４に対する修正が示されている。上で説明したように、列長限度より長い列は、より短く潜在的により有用な列のために辞書コードを予約するために、コンプレッサ辞書１１から除外される。しかし、同一文字のランが発生している場合に、辞書へのランのセグメントの保存から列長制限を除去することが有利な場合がある。この形で、ランデータに関するＬＺＷの圧縮機能は、妨げられない。
【０１９４】
したがって、ブロック４８０は、図４のブロック１２０のＹＥＳ分岐に挿入される。ブロック４８０で、延長列レジスタ２６の列を調べて、その文字が互いに関して同一であるか否かを判定する。文字が同一である場合には、データ文字ランが進行中である可能性が高い。これが発生する場合には、ブロック４８０からのＹＥＳ分岐で図４のブロック１２２に戻って、辞書１１に延長列を保存する。ブロック４８０のＹＥＳ分岐をたどる場合には、除外テーブルを調べる図４のブロック１２１が、バイパスされる。上で説明したように、好ましい実施形態の除外テーブルには、列長限度より長い列が含まれない。
【０１９５】
ブロック４８０で、延長列レジスタ２６の列の文字が、互いに関して同一でない場合には、ブロック４８０からのＮＯ分岐で図４のブロック１３３に戻る。ブロック４８０からのＮＯ分岐をたどる場合には、処理は、図４に関して上述した処理と同一である。
【０１９６】
図５、７、および８の参照を継続しながら図１９を参照すると、同一の符号は、図７および８に関する同一の要素を示すが、図１８の修正のデコンプレッサ修正対応部分が示されている。図１８の修正が、図４のコンプレッサ流れ図で使用される場合に、図１９の修正が、図７および８のデコンプレッサ流れ図で使用され、その結果、デコンプレッサが、コンプレッサと同期化されたままになる。図１９には、図７および８の両方に対する修正が示され、ここで、括弧内の番号は、図８の修正を指す。
【０１９７】
図１８に関して上述した形に似た形で、ブロック４８５（４９０）が、ブロック３６２（３８５）のＹＥＳ分岐に挿入される。ブロック４８５（４９０）では、延長列レジスタ２２６の延長列を調べて、その文字が互いに関して同一であるか否かを判定する。処理の流れおよび動作は、図１８に関して上で説明した処理の流れおよび動作に類似し、説明を短くするために特に繰り返さない。
【０１９８】
図１８および１９の修正が使用される場合に、列長限度より長い列を、辞書に保存することができる。したがって、これらの列に対処するか除外するために、除外テーブルと、図４のブロック１４２および図６の３５１の論理の修正が必要であるかもしれない。
【０１９９】
図１８および１９の修正の代替案または拡張として、特許に開示された技法を、本発明で使用して、入力データ文字ストリームのランを提供することができる（たとえば、2001年１月９日発行の特許文献１１参照）。
【０２００】
特定の除外テーブル構造を、図３に関して上述したが、説明された除外テーブル配置以外の除外テーブル配置を、本発明の実践に使用できることを諒解されたい。さらに、上の説明から、デコンプレッサ２１０が、コンプレッサから受け取る圧縮コードストリームだけを使用して、コンプレッサ１０の辞書１１および除外テーブル２５と同一の辞書２１１および除外テーブル２２５を構成することを諒解されたい。本発明の実践でエスケープコードが不要であることが有利である。
【０２０１】
本発明の上で説明した実施形態では、単一文字列の暗黙の認識が使用され、単一文字列に関する統計を累積するのに単一文字テーブルが使用される。本発明を、単一文字列が辞書に明示的に保存され、突き合わされるアーキテクチャと共に使用することもできることを諒解されたい。そのような実施形態では、単一文字テーブルが、使用されず、関連する統計が、辞書の適当なカウンタで累積される。
【０２０２】
本発明の上で説明した実施形態では、まれに出会う列を辞書から除外するために、動的に更新される除外テーブルを使用する。この実施形態は、単純な修正と共に、動的な基礎で頻繁に出会う列に関する動作を開始するのに使用することもできる。そのような修正の１つに、関連する文字カウンタが所定の閾値より大きい場合に辞書からの列をクリアしないことが含まれる。もう１つの実施形態を、図４のブロック１４１および図６のブロック３５０で、除外テーブルから削除された頻繁に出会う列を辞書に追加することによってもたらすことができる。
【０２０３】
除外テーブルの内容を洗練する、本発明のもう１つの変形形態は、システムのインサービス使用に先立って、大量の代表的データを用いて、上で説明した実施形態の多数のサイクルを使用することである。この形で、除外テーブルが、多数のサイクルにわたって洗練されて、最適に除外される列を含むようになる。これと同一の処理を、事前に保存された頻繁に出会う列の動的な洗練において、本発明の上で説明された変形形態に適用することができる。
【０２０４】
上の実施形態では、入力データ文字を、任意の対応する文字ビットサイズを有する任意のサイズのアルファベット上の文字とすることができる。たとえば、データ文字を、テキストデータ、イメージピクセルデータ、またはビットマップデータとすることができる。入力データは、１ビットサイズの文字を有する２文字のバイナリアルファベット０および１上のバイナリ文字とすることもできる。
【０２０５】
本発明の上で説明した実施形態を、ハードウェア、ファームウェア、ソフトウェア、またはこれらの組合せで実施できることを諒解されたい。ディスクリート回路実施形態を、さまざまな説明された機能を実行するために簡単に実施することができる。ソフトウェア実施形態では、上で説明した流れ図から簡単に生成されるコードを用いてプログラムされた適当なモジュールを使用することができる。
【０２０６】
本発明を、その好ましい実施形態で説明したが、使用された言葉が、制限ではなく説明の言葉であり、広義の態様における本発明の真の範囲および趣旨から逸脱せずに、請求項の範囲内で変更を行えることを理解されたい。
【図面の簡単な説明】
【０２０７】
【図１】本発明による、データを圧縮するデータコンプレッサの概略ブロック図である。
【図２】図１のデータコンプレッサおよび図５のデータデコンプレッサで使用される単一文字テーブルの詳細を示すデータ構造図である。
【図３】図１のデータコンプレッサおよび図５のデータデコンプレッサで使用される除外テーブルの詳細を示すデータ構造図である。
【図４Ａ】本発明に従ってデータ圧縮を実行するために、図１のコンプレッサによって実行される動作を示す流れ図である。
【図４Ｂ】本発明に従ってデータ圧縮を実行するために、図１のコンプレッサによって実行される動作を示す流れ図である。
【図５】図１のコンプレッサによって圧縮されたデータを回復する、本発明に従って実施されるデータデコンプレッサの概略ブロック図である。
【図６Ａ】本発明に従ってデータ伸長を実行するために、図５のデコンプレッサによって実行される動作を示す制御流れ図である。
【図６Ｂ】本発明に従ってデータ伸長を実行するために、図５のデコンプレッサによって実行される動作を示す制御流れ図である。
【図７】図６の流れ図で使用される文字処理論理を示す制御流れ図である。
【図８】図６の流れ図で使用される列処理論理を示す制御流れ図である。
【図９】図６の流れ図で使用される例外事例処理論理を示す制御流れ図である。
【図１０】図６および８の列回復ブロックと図９の列トレースブロックの詳細を示す制御流れ図である。
【図１１Ａ】図４の制御流れ図による図１のコンプレッサの動作と、当初は空の除外テーブルを例示する図である。
【図１１Ｂ】図４の制御流れ図による図１のコンプレッサの動作と、当初は空の除外テーブルを例示する図である。
【図１２】図１１の動作例の図に従う、図１のコンプレッサによって生成される除外テーブルを示す図である。
【図１３Ａ】図４の制御流れ図による図１のコンプレッサの動作と、図１２の除外テーブルを例示する図である。
【図１３Ｂ】図４の制御流れ図による図１のコンプレッサの動作と、図１２の除外テーブルを例示する図である。
【図１３Ｃ】図４の制御流れ図による図１のコンプレッサの動作と、図１２の除外テーブルを例示する図である。
【図１３Ｄ】図４の制御流れ図による図１のコンプレッサの動作と、図１２の除外テーブルを例示する図である。
【図１４】図１３の動作例の図に従う、図１のコンプレッサによって生成される除外テーブルを示す図である。
【図１５Ａ】図６から９の制御流れ図に従う図５のデコンプレッサの動作と、当初は空の除外テーブルを例示する図である。図１５の動作例の図による図５のデコンプレッサの動作によって、図１２の除外テーブルも生成される。
【図１５Ｂ】図６から９の制御流れ図に従う図５のデコンプレッサの動作と、当初は空の除外テーブルを例示する図である。図１５の動作例の図による図５のデコンプレッサの動作によって、図１２の除外テーブルも生成される。
【図１６Ａ】図６から９の制御流れ図に従う図５のデコンプレッサの動作と、図１２の除外テーブルを例示する図である。図１６の動作例の図による図５のデコンプレッサの動作によって、図１４の除外テーブルも生成される。
【図１６Ｂ】図６から９の制御流れ図に従う図５のデコンプレッサの動作と、図１２の除外テーブルを例示する図である。図１６の動作例の図による図５のデコンプレッサの動作によって、図１４の除外テーブルも生成される。
【図１６Ｃ】図６から９の制御流れ図に従う図５のデコンプレッサの動作と、図１２の除外テーブルを例示する図である。図１６の動作例の図による図５のデコンプレッサの動作によって、図１４の除外テーブルも生成される。
【図１７】動作の代替モードで図３の除外テーブルを移植するのに用いられる列を判定する際に使用されるツリー構造を示すデータ構造図である。
【図１８】入力データ文字ランに対応する、図４、７、および８に対する実施形態修正を示す図である。
【図１９】入力データ文字ランに対応する、図４、７、および８に対する実施形態修正を示す図である。
【図１】
2004525567.tif 000003
【図２】
2004525567.tif 000004
【図３】
2004525567.tif 000005
【図４Ａ】
2004525567.tif 000006
【図４Ｂ】
2004525567.tif 000007
【図５】
2004525567.tif 000008
【図６Ａ】
2004525567.tif 000009
【図６Ｂ】
2004525567.tif 000010
【図７】
2004525567.tif 000011
【図８】
2004525567.tif 000012
【図９】
2004525567.tif 000013
【図１０】
2004525567.tif 000014
【図１１Ａ】
2004525567.tif 000015
【図１１Ｂ】
2004525567.tif 000016
【図１２】
2004525567.tif 000017
【図１３Ａ】
2004525567.tif 000018
【図１３Ｂ】
2004525567.tif 000019
【図１３Ｃ】
2004525567.tif 000020
【図１３Ｄ】
2004525567.tif 000021
【図１４】
2004525567.tif 000022
【図１５Ａ】
2004525567.tif 000023
【図１５Ｂ】
2004525567.tif 000024
【図１６Ａ】
2004525567.tif 000025
【図１６Ｂ】
2004525567.tif 000026
【図１６Ｃ】
2004525567.tif 000027
【図１７】
2004525567.tif 000028
【図１８】
2004525567.tif 000029
【図１９】
2004525567.tif 000030
【国際公開パンフレット】
2004525567.tif 000031
2004525567.tif 000032
2004525567.tif 000033
2004525567.tif 000034
2004525567.tif 000035
2004525567.tif 000036
2004525567.tif 000037
2004525567.tif 000038
2004525567.tif 000039
2004525567.tif 000040
2004525567.tif 000041
2004525567.tif 000042
2004525567.tif 000043
2004525567.tif 000044
2004525567.tif 000045
2004525567.tif 000046
2004525567.tif 000047
2004525567.tif 000048
2004525567.tif 000049
2004525567.tif 000050
2004525567.tif 000051
2004525567.tif 000052
2004525567.tif 000053
2004525567.tif 000054
2004525567.tif 000055
2004525567.tif 000056
2004525567.tif 000057
2004525567.tif 000058
2004525567.tif 000059
2004525567.tif 000060
2004525567.tif 000061
2004525567.tif 000062
2004525567.tif 000063
2004525567.tif 000064
2004525567.tif 000065
2004525567.tif 000066
2004525567.tif 000067
2004525567.tif 000068
2004525567.tif 000069
2004525567.tif 000070
2004525567.tif 000071
2004525567.tif 000072
2004525567.tif 000073
2004525567.tif 000074
2004525567.tif 000075
2004525567.tif 000076
2004525567.tif 000077
2004525567.tif 000078
2004525567.tif 000079
2004525567.tif 000080
2004525567.tif 000081
2004525567.tif 000082
2004525567.tif 000083
2004525567.tif 000084
2004525567.tif 000085
2004525567.tif 000086
2004525567.tif 000087
2004525567.tif 000088
2004525567.tif 000089
2004525567.tif 000090
2004525567.tif 000091
2004525567.tif 000092
2004525567.tif 000093
2004525567.tif 000094
2004525567.tif 000095
2004525567.tif 000096
2004525567.tif 000097
2004525567.tif 000098
2004525567.tif 000099
2004525567.tif 000100
2004525567.tif 000101
2004525567.tif 000102
2004525567.tif 000103
2004525567.tif 000104
2004525567.tif 000105
2004525567.tif 000106
2004525567.tif 000107
2004525567.tif 000108
2004525567.tif 000109
2004525567.tif 000110
2004525567.tif 000111
2004525567.tif 000112
2004525567.tif 000113
2004525567.tif 000114
2004525567.tif 000115
2004525567.tif 000116
2004525567.tif 000117
2004525567.tif 000118
2004525567.tif 000119
2004525567.tif 000120
2004525567.tif 000121
2004525567.tif 000122
2004525567.tif 000123
2004525567.tif 000124
2004525567.tif 000125
2004525567.tif 000126
2004525567.tif 000127
2004525567.tif 000128
2004525567.tif 000129
2004525567.tif 000130
2004525567.tif 000131
2004525567.tif 000132
2004525567.tif 000133
2004525567.tif 000134
2004525567.tif 000135
2004525567.tif 000136
2004525567.tif 000137
2004525567.tif 000138
2004525567.tif 000139
2004525567.tif 000140
2004525567.tif 000141
2004525567.tif 000142
2004525567.tif 000143
2004525567.tif 000144
2004525567.tif 000145
2004525567.tif 000146
2004525567.tif 000147
2004525567.tif 000148
2004525567.tif 000149
2004525567.tif 000150
2004525567.tif 000151
2004525567.tif 000152
2004525567.tif 000153
2004525567.tif 000154
2004525567.tif 000155
2004525567.tif 000156
2004525567.tif 000157
2004525567.tif 000158
2004525567.tif 000159
【国際公開パンフレット（コレクトバージョン）】
2004525567.tif 000160
【国際調査報告】
2004525567.tif 000161
2004525567.tif 000162
2004525567.tif 000163