【手続補正書】
【提出日】平成19年8月9日(2007.8.9)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】  データ文字の入力ストリームを圧縮されたコードの出力ストリームに圧縮するデータ圧縮方法であって、前記方法は、ＬＺＷデータ圧縮処理を含み、前記ＬＺＷデータ圧縮処理は、データ文字のストリングを格納することと、前記格納されたストリングにコードカウンタからの各々のコードを割り当てることと、前記格納されたストリングのそれぞれについて前記コードカウンタを増分することとを含み、
前記入力ストリームの所定の数の隣接するデータ文字が互いに関して同一である時を検出することによって、データ文字のランが前記入力ストリーム内で発生する時を検出するステップであって、
前記検出されたランは、連続する数値的に増加するセグメントを含み、セグメントは、前記検出されるランの次の続く隣接セグメントより１つ少ないデータ文字を有する、検出するステップと、
前記検出されたランの前記連続するセグメントにそれぞれ対応する、前記コードカウンタからの連続コードを判定するステップと、
前記格納されたストリングとの最長一致を判定するために前記入力ストリームを前記格納されたストリングと比較することと、これによってＬＺＷ圧縮されたコードを提供するためにそれに割り当てられた前記コードを供給することとによって、ランが前記入力ストリーム内で発生することを検出されない時に、前記入力ストリームを圧縮するために前記ＬＺＷデータ圧縮処理を使用するステップと、
前記出力ストリームを提供するために、前記検出されたランのデータ文字および前記連続するセグメントに対応する前記連続コードを出力し、前記ＬＺＷ圧縮されたコードを出力するステップと
を備えたことを特徴とするデータ圧縮方法。
【請求項２】  前記判定ステップは、
前記ランが検出される時に、前記ラン内に存在する前記連続する数値的に増加するセグメントを検出するために、前記入力ストリームをルックアヘッドするステップと、
前記コードカウンタからの前記連続コードを、それぞれ、前記検出された連続するセグメントに割り当てるステップと
を備えたことを特徴とする請求項１に記載の方法。
【請求項３】  前記検出されたランは、前記検出されたランの前の隣接するセグメントより１つ多いデータ文字を有する最終セグメントを含み、
前記最終セグメントに続く前記入力ストリームが、次の続く隣接するセグメントを取り込むのに不十分な数の、前記検出されたランのデータ文字と同一である隣接データ文字を含むことを検出するステップと、
前記不十分な数のデータ文字を検出した後に、前記コードカウンタを次の続くコードまで増分するステップと
をさらに含むことを特徴とする請求項２に記載の方法。
【請求項４】  前記判定するステップは、
前記検出されたラン内のデータ文字の数を表す代表数を判定するステップと、
前記代表数を使用する数学的アルゴリズムによって、前記検出されたランの前記連続するセグメントに各々対応する、前記コードカウンタからの前記連続コードを数学的に判定するステップと
を備えたことを特徴とする請求項１に記載の方法。
【請求項５】  前記検出されたランは、前記連続するセグメントに続くさらなるデータ文字を含み、前記さらなるデータ文字は、さらなる連続する数値的に増加するセグメントを含むランを形成し、前記方法は、
前記検出されたランのデータ文字を出力するステップと、
次の続くコードまで前記コードカウンタを増分するステップと、
さらなるデータ文字の前記数を使用して、前記さらなる連続するセグメントにそれぞれ対応する、前記コードカウンタからのさらなる連続コードを数学的に判定するために、前記数学的アルゴリズムを再帰的に使用するステップと、
前記さらなる連続コードを出力するステップと
をさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】  前記数学的に判定するステップおよび前記出力するステップは、
セグメント内のデータ文字の数を表すインデックスを初期化するステップと、
前記コードカウンタ内のコードを出力し、次の続くコードまで前記コードカウンタを増分するステップと、
前記インデックスをそれから減算することによって、前記代表数を減らすステップと、
前記インデックスを１だけ増分するステップと、
前記減らされた代表数を前記増分されたインデックスと比較するステップと、
前記減らされた代表数が前記増分されたインデックス未満になるまで、前記コードカウンタ内の前記コードを出力することから前記減らされた代表数を前記増分されたインデックスと比較することまでの、上記の所与のステップを繰り返すステップと
を含むことを特徴とする請求項４に記載の方法。
【請求項７】  前記減らされた代表数が、前記増分されたインデックス未満であるが、３未満でない時に、
次の続くコードまで前記コードカウンタを増分するステップと、
前記検出されたランの前記データ文字を出力するステップと、
前記インデックスを再初期化するステップと、
前記減らされた代表数が前記増分されたインデックス未満になるまで、前記コードカウンタ内の前記コードを出力することから前記減らされた代表数を前記増分されたインデックスと比較することまでの、前記ステップを繰り返すステップと
をさらに含むことを特徴とする請求項６に記載の方法。
【請求項８】  対応するコードが出力される前記検出されたランの前記セグメントのデータ文字を破棄するステップと、
前記コードカウンタを次の続くコードまで増分するステップと、
前記破棄されたデータ文字に続く前記入力ストリームの次のデータ文字を用いて前記方法を継続するステップと
をさらに含むことを特徴とする請求項４に記載の方法。
【請求項９】  前記数学的に判定するステップおよび前記出力するステップは、
セグメント内のデータ文字の数を表すインデックスを初期化するステップと、
破棄数を初期化するステップと、
前記コードカウンタ内のコードを出力し、前記コードカウンタを次の続くコードまで増分するステップと、
前記破棄数を、それに前記インデックスを加算することによって増やすステップと、
前記代表数を、それから前記インデックスを減算することによって減らすステップと、
前記インデックスを１だけ増分するステップと、
前記減らされた代表数を前記増分されたインデックスと比較するステップと、
前記減らされた代表数が前記増分されたインデックス未満になるまで、前記コードカウンタ内の前記コードを出力することから前記減らされた代表数を前記増分されたインデックスと比較することまでの、上記の所与のステップを繰り返すステップと
を含み、前記方法は、
前記破棄数に従って前記検出されたランのデータ文字を破棄するステップと、
前記コードカウンタを次の続くコードまで増分するステップと、
前記破棄されたデータ文字に続く、前記入力ストリームの次のデータ文字を用いて前記方法を継続するステップと
をさらに含むことを特徴とする請求項４に記載の方法。
【請求項１０】  前記減らされた代表数が、前記増分されたインデックス未満であるが、３未満でない時に、
前記コードカウンタを次の続くコードまで増分するステップと、
前記検出されたランの前記データ文字を出力するステップと、
前記インデックスを再初期化するステップと、
前記減らされた代表数が前記増分されたインデックス未満になるまで、前記コードカウンタ内の前記コードを出力することから前記減らされた代表数を前記増分されたインデックスと比較することまでの、前記ステップを繰り返すステップと
をさらに含むことを特徴とする請求項９に記載の方法。
【請求項１１】  前記数学的に判定するステップおよび前記出力するステップは、
第１の方程式を使用して、前記代表数に関する前記検出されたランに含まれる前記連続する数値的に増加するセグメントの数を計算する、第１の計算を実行するステップと、
前記連続するセグメントの前記数を前記コードカウンタ内のコードへ加算することを含む、第２の方程式を使用して、限界を計算する第２の計算を実行するステップと、
前記次の続くコードが前記限界と等しくなるまで、前記コードカウンタ内の前記コードを出力し、前記コードカウンタを次の続くコードまで増分するステップと
を含むことを特徴とする請求項４に記載の方法。
【請求項１２】  前記第１の計算で計算された数に関して破棄数を計算する、第３の方程式を使用する第３の計算を実行するステップ
をさらに含むことを特徴とする請求項１１に記載の方法。
【請求項１３】  データ文字の入力ストリームを圧縮されたコードの出力ストリームに圧縮するデータ圧縮装置であって、前記装置は、ＬＺＷデータコンプレッサを含み、前記ＬＺＷデータコンプレッサは、データ文字のストリングを格納する辞書と、前記格納されたストリングに各々のコードを割り当てるコードカウンタと、前記格納されたストリングのそれぞれについて前記コードカウンタを増分する手段とを含み、
前記入力ストリームの所定の数の隣接するデータ文字が互いに関して同一である時を検出することによって、データ文字のランが前記入力ストリーム内で発生する時を検出する手段であって、
前記検出されたランは、連続する数値的に増加するセグメントを含み、セグメントは、前記検出されるランの次の続く隣接セグメントより１つ少ないデータ文字を有する、検出する手段と、
前記検出されたランの前記連続するセグメントにそれぞれ対応する、前記コードカウンタからの連続コードを判定する手段と、
前記格納されたストリングとの最長一致を判定するために前記入力ストリームを前記格納されたストリングと比較することと、これによってＬＺＷ圧縮されたコードを提供するためにそれに割り当てられた前記コードを供給することとによって、ランが前記入力ストリーム内で発生することを検出されない時に、前記入力ストリームを圧縮するように動作可能である前記ＬＺＷデータコンプレッサと、
前記出力ストリームを提供するために、前記検出されたランのデータ文字および前記連続するセグメントに対応する前記連続コードを出力し、前記ＬＺＷ圧縮されたコードを出力する手段と
を備えたことを特徴とするデータ圧縮装置。
【請求項１４】  前記判定手段は、
前記ランが検出される時に、前記ラン内に存在する前記連続する数値的に増加するセグメントを検出するために、前記入力ストリームをルックアヘッドする手段と、
前記コードカウンタからの前記連続コードを、それぞれ、前記検出された連続するセグメントに割り当てる手段と
を備えたことを特徴とする請求項１３に記載の装置。
【請求項１５】  前記検出されたランは、前記検出されたランの前の隣接するセグメントより１つ多いデータ文字を有する最終セグメントを含み、
前記最終セグメントに続く前記入力ストリームが、次の続く隣接するセグメントを取り込むのに不十分な数の、前記検出されたランのデータ文字と同一である隣接データ文字を含むことを検出する手段と、
前記不十分な数のデータ文字を検出した後に、前記コードカウンタを次の続くコードまで増分する手段と
をさらに含むことを特徴とする請求項１４に記載の装置。
【請求項１６】  前記判定する手段は、
前記検出されたラン内のデータ文字の数を代表数を判定する手段と、
前記代表数を使用する数学的アルゴリズムによって、前記検出されたランの前記連続するセグメントに各々対応する、前記コードカウンタからの前記連続コードを数学的に判定する手段と
を備えたことを特徴とする請求項１３に記載の装置。
【請求項１７】  前記検出されたランは、前記連続するセグメントに続くさらなるデータ文字を含み、前記さらなるデータ文字は、さらなる連続する数値的に増加するセグメントを含むランを形成し、前記装置は、
前記検出されたランのデータ文字を出力する手段と、
次の続くコードまで前記コードカウンタを増分する手段と、
さらなるデータ文字の前記数を使用して、前記さらなる連続するセグメントにそれぞれ対応する、前記コードカウンタからのさらなる連続コードを数学的に判定するために、前記数学的アルゴリズムを再帰的に使用する手段と、
前記さらなる連続コードを出力する手段と
をさらに含むことを特徴とする請求項１６に記載の装置。
【請求項１８】  前記数学的に判定する手段および前記出力する手段は、
セグメント内のデータ文字の数を表すインデックスを初期化する動作と、
前記コードカウンタ内のコードを出力し、次の続くコードまで前記コードカウンタを増分する動作と、
前記インデックスをそれから減算することによって、前記代表数を減らす動作と、
前記インデックスを１だけ増分する動作と、
前記減らされた代表数を前記増分されたインデックスと比較する動作と、
前記減らされた代表数が前記増分されたインデックス未満になるまで、前記コードカウンタ内の前記コードを出力する動作から前記減らされた代表数を前記増分されたインデックスと比較する動作までの、上記の所与の動作を繰り返す動作と
を実行する反復手段を含むことを特徴とする請求項１６に記載の装置。
【請求項１９】  前記減らされた代表数が、前記増分されたインデックス未満であるが、３未満でない時に、
次の続くコードまで前記コードカウンタを増分する動作と、
前記検出されたランの前記データ文字を出力する動作と、
前記インデックスを再初期化する動作と、
前記減らされた代表数が前記増分されたインデックス未満になるまで、前記コードカウンタ内の前記コードを出力する動作から前記減らされた代表数を前記増分されたインデックスと比較する動作までの、前記動作を繰り返す動作と
を実行する再帰手段をさらに含むことを特徴とする請求項１８に記載の装置。
【請求項２０】  対応するコードが出力される前記検出されたランの前記セグメントのデータ文字を破棄する手段と、
前記コードカウンタを次の続くコードまで増分する手段と、
前記入力ストリームの前記圧縮を継続するために、前記破棄されたデータ文字に続く前記入力ストリームの次のデータ文字をフェッチする手段と
をさらに含むことを特徴とする請求項１６に記載の装置。
【請求項２１】  前記数学的に判定する手段および前記出力する手段は、
セグメント内のデータ文字の数を表すインデックスを初期化する動作と、
破棄数を初期化する動作と、
前記コードカウンタ内のコードを出力し、前記コードカウンタを次の続くコードまで増分する動作と、
前記破棄数を、それに前記インデックスを加算することによって増やす動作と、
前記代表数を、それから前記インデックスを減算することによって減らす動作と、
前記インデックスを１だけ増分する動作と、
前記減らされた代表数を前記増分されたインデックスと比較する動作と、
前記減らされた代表数が前記増分されたインデックス未満になるまで、前記コードカウンタ内のコードを出力する動作から前記減らされた代表数を前記増分されたインデックスと比較する動作までの、上記の所与の動作を繰り返す動作と
を実行する反復手段を含み、前記装置は、
前記破棄数に従って前記検出されたランのデータ文字を破棄する手段と、
前記コードカウンタを次の続くコードまで増分する手段と、
前記入力ストリームの前記圧縮を継続するために、前記破棄されたデータ文字に続く、前記入力ストリームの次のデータ文字をフェッチする手段と
をさらに含むことを特徴とする請求項１６に記載の装置。
【請求項２２】  前記減らされた代表数が、前記増分されたインデックス未満であるが、３未満でない時に、
前記コードカウンタを次の続くコードまで増分する動作と、
前記検出されたランの前記データ文字を出力する動作と、
前記インデックスを再初期化する動作と、
前記減らされた代表数が前記増分されたインデックス未満になるまで、前記コードカウンタ内の前記コードを出力する動作から前記減らされた代表数を前記増分されたインデックスと比較する動作までの、前記動作を繰り返す動作と
を実行する再帰手段をさらに含むことを特徴とする請求項２１に記載の装置。
【請求項２３】  前記数学的に判定する手段および前記出力する手段は、
第１の方程式を使用して、前記代表数に関する前記検出されたランに含まれる前記連続する数値的に増加するセグメントの数を計算する第１の計算と、
前記連続するセグメントの前記数を前記コードカウンタ内のコードへ加算することを含む、第２の方程式を使用して、限界を計算する第２の計算と、
前記次の続くコードが前記限界と等しくなるまで、前記コードカウンタ内の前記コードを出力し、前記コードカウンタを次の続くコードまで増分する動作と
を実行する数学的方程式手段を含むことを特徴とする請求項１６に記載の装置。
【請求項２４】  前記数学的方程式手段は、
前記第１の計算で計算された数に関して破棄数を計算する、第３の方程式を使用する第３の計算
の動作を実行するようにさらに動作することを特徴とする請求項２３に記載の装置。