【手続補正書】
【提出日】平成18年12月7日(2006.12.7)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】  アルファベットから得られる記号のグループに対するコードブックを構成する方法であって、可変サイズの記号グループのそれぞれに、記号グループの発生確率に基づく可変長符号が割り当てられる方法において、
入力からシリーズの記号を受信するステップと、
データ構造内に複数の可変サイズの記号グループを記憶するステップであって、各記号グループは、１つ以上の隣接記号によって定義され、前記記号グループに応じた前記受信済みシリーズの記号の解析は、前記受信済みシリーズ全体の前記記号グループに関する発生確率をもたらし、かつ前記解析は、複数回繰り返され、前記記号グループは、前記受信済みシリーズ全体での前記発生確率に基づいて、各解析の後に変更されるステップと、
各記号グループに対し、前記受信済みシリーズ内での前記記号グループの発生確率に基づいて可変長符号を割り当てるステップと、
次に続く可変から可変への圧縮のために、前記記号グループを対応する割り当て済み符号と関連付けるコードブックを出力するステップと
を備えることを特徴とする方法。
【請求項２】  請求項１に記載の方法において、データ構造内に前記記憶するステップは、所定数のエントリを有するコードブックが得られるまで繰り返されることを特徴とする方法。
【請求項３】  請求項２に記載の方法において、前記受信済みの記号は、例示的な入力からのものであることを特徴とする方法。
【請求項４】  請求項１に記載の方法を実行するためのコンピュータ実行可能命令を記憶したことを特徴とするコンピュータ可読媒体。
【請求項５】  請求項１に記載の方法において、前記記号は、メモリストレージ内に記憶されて、適合的にグループ化され、前記ストレージは、前記アルファベットからの１つ以上の記号の記号シリーズによって定義される短い記号グループと、前記短い記号グループの記号シリーズを、前記アルファベットからの１つ以上の記号で拡張することによって定義される長いグループとを含み、
前記記憶するステップは、
短いグループの初期集合を形成するステップと、
短いグループを選択するステップと、
前記短いグループを拡張記号で拡張することによって長いグループを定義するステップと、
前記入力から各長いグループを受信する確率を計算して、高確率グループおよび低確率グループを識別するステップと、
各低確率グループを結合して、前記短いグループの記号シリーズと、各高確率グループの拡張シリーズを除く全ての拡張シリーズを表す拡張記号とを有する結合グループにするステップと
を含むことを特徴とする方法。
【請求項６】  請求項５に記載の方法を実行するためのコンピュータ実行可能命令を記憶したことを特徴とするコンピュータ可読媒体。
【請求項７】  請求項１に記載の方法において、前記記号は、階層メモリストレージ内に記憶されて、適合的にグループ化され、前記ストレージにおける前記階層は、初期グループを含む初期階層レベルを有し、全てのグループは、前記アルファベットからの１つ以上の記号の記号シリーズによって定義され、前記階層は、親グループに対する少なくとも１つの下位グループを含む下位レベルを有し、各下位グループは、前記親シリーズを、前記アルファベットからの１つ以上の文字で拡張することによって定義され、
前記記憶するステップは、
前記階層内に前のレベルの新しい下位レベルを作成するステップと、
前記前の階層レベルから親グループを選択するステップと、
複数の要素を有する記号の拡張セットを定義するステップであって、各要素は、前記アルファベットからの少なくとも１つの記号によって定義されるステップと、
前記拡張セットの各要素について、前記親グループの記号シリーズを前記セット要素で拡張することによって、前記親グループの下位グループを定義するステップと、
各定義済み下位グループについて、前記入力から前記下位グループを受信する確率を計算するステップと、
各下位グループに共通する基本記号シリーズと、高確率である少なくとも１つの記号の拡張シリーズとによって定義される記号シリーズを有する少なくとも１つの高確率の下位グループを識別するステップであって、他の全ての下位グループは低確率であるステップと、
各低確率の下位グループを結合して、前記基本記号シリーズと、各高確率の拡張シリーズとは異なる全ての記号シリーズを表す特定記号とによって表される結合記号シリーズを有する結合グループにするステップと
を含むことを特徴とする方法。
【請求項８】  請求項７に記載の方法を実行するためのコンピュータ実行可能命令を記憶したことを特徴とするコンピュータ可読媒体。
【請求項９】  請求項１に記載の方法において、前記データ構造は、ｎ個の可変サイズの記号グループを記憶し、前記データ構造内で表されていない記号グループは、エスケープエントリで符号化されることを特徴とする方法。
【請求項１０】  ストリーミングデータを圧縮するためのコードブックを作成する方法であって、前記ストリーミングデータは、シリーズの記号によって表され、前記シリーズの記号は、可変長記号グループに集約され、前記可変長記号グループのそれぞれに、代表的なデータソース内の前記グループの発生確率に基づく可変長符号が割り当てられる方法において、
前記記号グループを記憶するための動的に割り当て可能なメモリを有するデータ構造内に、前記記号グループを記憶するステップであって、前記データ構造は、複数の異なる入力シーケンスのそれぞれに割り当てられた異なるエントロピー符号を有するステップと、
高確率を有する記号グループを識別するステップと、
アルファベットから新しい記号を追加することによって、前記記号グループを試験的グループに拡張するステップと、
高確率の試験的グループを識別するステップと、
前記高確率の試験的グループを除く全ての試験的グループを結合して結合グループにするステップと、
前記高確率の試験的グループを前記データ構造内に記憶するステップと、
前記結合グループを前記データ構造内に記憶するステップと
を備えることを特徴とする方法。
【請求項１１】  請求項１０に記載の方法において、前記データ構造は、各記号グループを記憶するためのエントリを有するテーブルとして構成されていることを特徴とする方法。
【請求項１２】  請求項１０に記載の方法において、前記データ構造は、記号を含むノードを有するツリーとして構成され、各記号グループは、前記ツリーにおける走査パスによって識別されることを特徴とする方法。
【請求項１３】  請求項１０に記載の方法において、前記結合グループが高確率を有する場合、前記結合グループを分割するステップをさらに備え、
前記分割するステップは、
前記グループを構成記号に分割するステップと、
高確率を有する構成記号を識別するステップと、
前記高確率の構成記号を除く全ての構成記号を再結合するステップと
を含むことを特徴とする方法。
【請求項１４】  請求項１０に記載の方法において、前記ストリーミングデータは、不揮発性記憶媒体から取り出されることを特徴とする方法。
【請求項１５】  アルファベットから得られる記号のグループに対するコードブックを構成するシステムであって、可変サイズの記号グループのそれぞれに、記号グループの発生確率に基づく可変長符号が割り当てられるシステムにおいて、
シリーズの複数の記号を受信するための入力と、
複数の可変サイズの記号グループを記憶するためのデータ構造を含むように構成されたメモリであって、各記号グループが１つ以上の隣接記号によって定義されるメモリと、
前記記号グループに応じて受信済みシリーズの複数の記号を解析する手段であって、前記解析は、前記受信済みシリーズ全体の前記記号グループに関する発生確率をもたらし、かつ前記解析は、複数回繰り返され、前記記号グループは、前記受信済みシリーズ全体での前記発生確率に基づいて、各解析の後に変更される手段と、
各記号グループに対し、前記受信済みシリーズ内での前記記号グループの発生確率に基づいて可変長符号を割り当てる手段と、
次に続く可変から可変への圧縮のために、前記可変サイズの記号グループを前記割り当て済みの可変長符号と関連付けるコードブックを出力する手段と
を備えたことを特徴とするシステム。
【請求項１６】  請求項１５に記載のシステムにおいて、前記結合グループを構成記号に分割する手段をさらに備えたことを特徴とするシステム。
【請求項１７】  請求項１５に記載のシステムにおいて、前記データ構造は、ｎ個の可変サイズの記号グループを記憶し、かつ前記データ構造は、前記データ構造内で表されていない記号グループを符号化するためのエスケープエントリを記憶することを特徴とするシステム。
【請求項１８】  アルファベットから得られる記号のグループに対するコードブックを構成する方法であって、可変サイズの記号グループのそれぞれに、記号グループの発生確率に基づく可変長符号が割り当てられる方法において、
入力から記号を受信するステップと、
前記入力からの受信済み隣接記号によって定義される可変サイズの記号グループをデータ構造内に記憶するステップであって、
高確率を有する記号グループを識別するステップと、
前記アルファベットから新しい記号を追加することによって、前記記号グループを試験的グループに拡張するステップと、
高確率の試験的グループを識別するステップと、
前記高確率の試験的グループを除く全ての試験的グループを結合して結合グループにするステップと、
前記高確率の試験的グループを前記データ構造内に記憶するステップと、
前記結合グループを前記データ構造内に記憶するステップと
を含むステップと、
各記号グループについて、確率を計算するステップと、
各記号グループに対し、可変長符号を割り当てるステップと
を備えることを特徴とする方法。
【請求項１９】  請求項１８に記載の方法において、高確率を有する前記記号グループが結合グループの場合、
前記結合グループを構成記号に分割し、
高確率を有する構成記号を識別し、
前記高確率の構成記号を除く全ての構成記号を再結合する
ことを特徴とする方法。
【請求項２０】  請求項１９に記載の方法を実行するためのコンピュータ実行可能命令を記憶したことを特徴とするコンピュータ可読媒体。
【請求項２１】  請求項１８に記載の方法において、前記高確率の試験的グループは、最高確率の拡張が後ろに続く高確率を有する前記記号グループにより形成され、前記結合グループは、前記最高確率の拡張とは異なる任意の拡張に対応する特定の拡張が後ろに続く高確率を有する前記記号グループにより形成されることを特徴とする方法。
【請求項２２】  請求項２１に記載の方法において、前記結合グループは、該グループ内の各記号を記憶するための動的に割り当て可能なメモリを有するデータ構造内に記憶されることを特徴とする方法。
【請求項２３】  請求項１８に記載の方法を実行するためのコンピュータ実行可能命令を記憶したことを特徴とするコンピュータ可読媒体。
【請求項２４】  アルファベットから得られる記号のグループに対するコードブックを構成するシステムであって、可変サイズの記号グループのそれぞれに、記号グループの発生確率に基づく可変長符号が割り当てられるシステムにおいて、
複数の記号を受信するための入力と、
前記入力からの受信済み隣接記号によって定義される可変サイズの記号グループを記憶するためのデータ構造を含むように構成されたメモリと、
高確率を有する記号グループを識別する手段と、
前記アルファベットから新しい記号を追加することによって、前記記号グループを試験的グループに拡張する手段と、
高確率の試験的グループを識別する手段と、
前記高確率の試験的グループを除く全ての試験的グループを結合して結合グループにする手段と、
前記高確率の試験的グループを前記データ構造内に記憶する手段と、
前記結合グループを前記データ構造内に記憶する手段と、
各記号グループについて、確率を計算する手段と、
各記号グループに対し、可変長符号を割り当てる手段と
を備えたことを特徴とするシステム。
【請求項２５】  請求項２４に記載のシステムにおいて、前記結合グループが高確率を有する場合、前記結合グループを構成記号に分割する手段をさらに備えたことを特徴とするシステム。
【請求項２６】  アルファベットから得られる記号のグループに対するコードブックを構成するためのコンピュータ実行可能命令を記憶したコンピュータ可読媒体において、前記コードブックは可変から可変への圧縮のためのものであり、
記号グループを初期化して、入力からの受信済みシリーズの記号を解析する処理と、
前記記号グループに応じて前記受信済みシリーズの記号を繰り返し解析する処理であって、前記解析は、前記受信済みシリーズ全体の前記記号グループに関する発生確率をもたらす処理と、
前記受信済みシリーズ全体での前記発生確率に基づいて、前記記号グループを繰り返し変更する処理と、
各記号グループに対し、前記受信済みシリーズ内での前記記号グループの発生確率に基づいて可変長符号を割り当てる処理と、
次に続く可変から可変への圧縮のために、前記記号グループを対応する割り当て済み符号と関連付けるコードブックを出力する処理と
を含む前記コンピュータ実行可能命令をコンピュータに実行させることを特徴とするコンピュータ可読媒体。
【請求項２７】  請求項２６に記載のコンピュータ可読媒体において、前記繰り返される解析処理および変更処理は、前記可変サイズの記号グループの平均サイズを増大させることを特徴とするコンピュータ可読媒体。
【請求項２８】  請求項２６に記載のコンピュータ可読媒体において、所定数の記号グループに関して、前記繰り返される解析処理および変更処理は、前記可変サイズの記号グループの平均サイズを最大化することを特徴とするコンピュータ可読媒体。