【手続補正書】
【提出日】平成17年2月7日(2005.2.7)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】発明の名称
【補正方法】変更
【補正の内容】
【発明の名称】接頭語予測を用いた符号化方法及び装置
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
入力データ記号を符号化する符号化方法であって、
ノードのセットと枝のセットとを含むツリー構造を決定するステップと、
前記ノードのセットに含まれるノードの各々のため、記号のセットにおける数値表現の中の１つのデータに対応する区画データを選択するステップであって、前記区画データは、前記記号のセットにおける既知の確率に対応していて、選択された前記区画データの各々は、前記ノードで記号を区画して生じる確率の不均衡を最大にする区画データであるステップと、
前記ノードのセットに含まれるノードに存在する前記記号のセットを、前記選択された区画データの値に対応して、下向きに分岐される２つのノードに区画するステップであって、前記下向きに分岐されるノード、前記根ノード及び前記葉ノードは前記ノードのセットに含まれ、前記２つのノードへの区画は、前記記号のセットを含む根ノードから始め、前記記号のセットに含まれる単一記号を含む葉ノードで終了するステップと、
前記ツリー構造における前記枝のセットに確率を割り当てるステップであって、この確率は、前記記号のセットに含まれる記号の確率に対応していて、確率の割り当てにおいて、未知の、不正確な又は人為的に割り当てられた確率をもつ記号より既知の確率をもつ記号を優先するステップと、
前記記号のセットに含まれる記号を、前記根ノードから前記記号と関連する葉ノードへの最短経路を形成する前記枝の確率に関して、符号化するステップと
からなることを特徴とする符号化方法。
【請求項２】
前記ツリー構造はバイナリツリーであることを特徴とする請求項１に記載された符号化方法。
【請求項３】
前記区画データは単一ビットであることを特徴とする請求項１又は２に記載された符号化方法。
【請求項４】
既知の確率を、未知の、不正確な又は人為的に割り当てられた確率から区別するとき、前記既知の確率が第一に用いられることを特徴とする請求項１、２及び３のいずれかに記載された符号化方法。
【請求項５】
前記ノードの前記枝の確率は、和が１となる１対の浮動小数点式の数又は有理数として、表現されることを特徴とする請求項１、２、３及び４のいずれかに記載された符号化方法。
【請求項６】
前記１対の浮動小数点式の数又は有理数に関連する前記値の間の前記不均衡が、他の未使用のビットを用いる全ての他の有り得る区画に関して最大となることを特徴とする請求項５に記載された符号化方法。
【請求項７】
入力データ記号を符号化する符号化方法であって、
記号のセットを文字列に順序付けるステップと、
前記記号のセットに含まれる各記号を、接頭語を含む文脈に結合するステップと、
前記記号のセットに対応する前記接頭語の予測テーブルを生成するステップと、
前記予測テーブルに対応し、ノードのセットを含み、前記記号のセットのビットごとの符号化に用いられるツリーを生成するステップと、
前記ノードのセットに含まれるノードの各々のため、前記記号のセットにおける二進表現の中の１つのデータに対応する区画データを選択するステップと、
前記ノードのセットに含まれる前記ノードに存在する前記記号のセットを、前記選択された区画データの値に対応して、下向きに２つに分岐されるノードに区画するステップであって、前記下向きに分岐されるノード、前記根ノード及び前記葉ノードは前記ノードのセットに含まれ、前記２つのノードへの区画が、前記記号のセットを含む根ノードから始め、前記記号のセットにおける単一記号を含む葉ノードで終了するステップと、
前記ツリーにある各枝に確率を、前記記号のセットに含まれる記号の確率に対応して、未知の、不正確な又は人為的に割り当てられた確率をもつ記号より既知の確率をもつ記号を優先しつつ、割り当てるステップと、
前記記号のセットにおける記号を、前記根ノードから前記記号と関連する葉ノードへの最短経路を形成する前記枝の確率に関して、符号化するステップと
ことを特徴とする符号化方法。
【請求項８】
前記順序付けステップは、バロウズ・ホイラー変換と前方移行変換のうちの少なくとも１つの実行を含むことを特徴とする請求項７に記載された符号化方法。
【請求項９】
前記予測テーブルの生成ステップは、０次のテーブル、１次のテーブル、２次のテーブル及び３次のテーブルのうちの少なくとも１つの生成を含むことを特徴とする請求項７又は８に記載された符号化方法。
【請求項１０】
前記予測テーブルは、前記記号の既知の確率と拡張値を含み、前記拡張値は、個々の確率が未知の、不正確な又は人為的に割り当てられている、記号のサブセットの集合的な確率に相当することを特徴とする請求項７、８及び９のいずれかに記載された符号化方法。
【請求項１１】
前記区画ビットの選択ステップは、より高い優先順位を有する前記記号の既知の確率に関し、かつ、未知の、不正確な又は人為的に割り当てられた前記記号に関して相対的な不均衡の決定を含むことを特徴とする請求項７、８、９及び１０のいずれかに記載された符号化方法。
【請求項１２】
前記ノードのセットは、根ノード、分岐ノードと終端の葉ノードを含むことを特徴とする請求項７、８、９、１０及び１１のいずれかに記載された符号化方法。
【請求項１３】
１つ以上の前記終端の葉ノードは、その確率値が事前知識または事前に得られている統計からの既知の記号、または、ある公式でモデル化されているが未知の記号に関連することを特徴とする請求項６又は１２に記載された符号化方法。
【請求項１４】
データを圧縮するために用いられることを特徴とする請求項１、２、３、４、５、６、７、８、９、１０、１１、１２及び１３のいずれかに記載された符号化方法。
【請求項１５】
コンピュータに、請求項１から５のいずれかに記載されたステップを実行させるためのプログラム。
【請求項１６】
コンピュータに、請求項７または８に記載されたステップを実行させるためのプログラム。
【請求項１７】
入力データ記号を符号化する符号化装置であって、
ノードのセットと枝のセットとを含むツリー構造を決定する決定手段と、
前記ノードのセットに含まれるノードの各々のため、記号のセットにおける数値表現の中の１つのデータに対応する区画データを選択する選択手段であって、前記区画データは、前記記号のセットにおける既知の確率に対応していて、選択された前記区画データの各々は、区画データとして選択可能な区画データの中で、前記ノードで前記シンボルの区画から生じる前記記号のグループの確率の不均衡を最大にする区画データである選択手段と、
前記ノードのセットに含まれる前記ノードに存在する前記記号のセットを、前記選択された区画データの値に対応して、下向きに分岐される２つのノードに区画する区画手段であって、前記下向きに２つに分岐されるノード、前記根ノード及び前記葉ノードは前記ノードのセットに含まれ、前記２つのノードへの区画が前記記号のセットを含む根ノードから始め、前記記号のセットに含まれる単一記号を含む葉ノードで終了する区画手段と、
前記ツリー構造における前記枝のセットに確率を、前記記号のセットに含まれる記号の確率に対応して、未知の、不正確な又は人為的に割り当てられた確率をもつ記号より既知の確率をもつ記号を優先しつつ割り当てる割当手段と、
前記記号のセットに含まれる記号を、前記根ノードから前記記号と関連する葉ノードへの最短経路を形成する前記枝の確率に関して、符号化する符号化手段と
からなる符号化装置。
【請求項１８】
前記ツリー構造はバイナリツリーであることを特徴とする請求項１７に記載された符号化装置。
【請求項１９】
前記区画データは単一ビットであることを特徴とする請求項１７又は１８に記載された符号化装置。
【請求項２０】
前記既知の確率を第一に用いて、前記既知の確率と、未知の、不正確な又は人為的に割り当てられた確率とを区別することを特徴とする請求項１７、１８及び１９のいずれかに記載された符号化装置。
【請求項２１】
前記ノードの前記枝の確率は、合計すると１となる１対の浮動小数点式の数又は有理数として表現されることを特徴とする請求項１７、１８、１９及び２０のいずれかに記載された符号化装置。
【請求項２２】
他の未使用のビットを用いて起こり得る他の全ての区画に比べ、前記１対の浮動小数点数又は有理数と結びつけられる前記値の間の不均衡が最大となることを特徴とする請求項２１に記載された符号化装置。
【請求項２３】
１つ以上の前記終端葉は、その確率値が事前知識または事前に得られている統計から既知の記号、または、ある公式でモデル化されているが未知の記号に関連することを特徴とする請求項２２に記載された符号化装置。
【請求項２４】
入力データ記号を符号化する符号化装置であって、
記号のセットを文字列に順序付ける順序付け手段と、
前記記号のセットに含まれる各記号を、接頭語を含む文脈に結びつける関連手段と、
前記記号のセットに対応する前記接頭語のための予測テーブルを生成する予測テーブル生成手段と、
ノードのセットを含み、前記記号のセットをビットごとの符号化に用いられ、前記予測テーブルに対応するツリーを生成するツリー生成手段と、
前記記号のセットの二進表現におけるあるビットの位置に対応する区画ビットを、前記ノードのセットにおいて選択されたノードと結びつけて選択する選択手段と、
前記ノードのセットに含まれるノードに存在する前記記号のセットを、前記選択された区画データの値に対応して、下向きに分岐される２つのノードに区画するステップであって、前記下向きに２つに分岐されるノード、前記根ノード及び前記葉ノードは前記ノードのセットに含まれ、前記２つのノードへの区画が、前記記号のセットを含む根ノードから始め、前記記号のセットに対応する単一記号を含む葉ノードで終了する区画手段と、
前記ツリーにある各分岐ノードに確率を、前記記号のセットに含まれる記号の確率に対応して、未知の、不正確な又は人為的に割り当てられた確率をもつ記号より既知の確率をもつ記号を優先しつつ、割り当てる割当手段と、
前記記号のセットに含まれる記号を、前記根ノードから前記記号と関連する葉ノードへの最短経路を形成する前記枝の確率に関して、符号化する符号化手段と
からなる符号化装置。
【請求項２５】
前記順序付け手段は、バロウズ・ホイラー変換と前方移行変換のうちの少なくとも１つを実行することを特徴とする請求項２４に記載された符号化装置。
【請求項２６】
前記予測テーブル生成手段は、０次のテーブル、１次のテーブル、２次のテーブル及び３次のテーブルのうちの少なくとも１つを生成することを特徴とする請求項２４又は２５に記載された符号化装置。
【請求項２７】
前記予測テーブルは、前記記号の既知の確率と、記号のサブセットの集合的な確率であってその個々の確率が未知、不正確又は人為的に割り当てられている確率に相当する拡張値とを含むことを特徴とする請求項２４、２５及び２６のいずれかに記載された符号化装置。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
ハフマン符号化やその変形例が、例えばモールス符号から始まって、ＵＮＩＸ(登録商標)のpack/unpackやcompress/uncompress(圧縮/解凍)の命令に至るまでの多様な事例で利用されている。ハフマン符号化やハフマン符号化の変形例では、キャラクタの相対頻度を判定して、特定の頻度に基づいてコードを割り当てている。繰り返し出現する頻度の高いキャラクタは、頻度の低いキャラクタより短いコードを持っているものである。好ましくは一番長いコードを最下層に据え、最上層に至って一番短いコードで終わるバイナリツリー構造が生成されている。最下層から読まれるのが好ましいのではあるが、復号器がビット符号化されたメッセージを受け取り、ツリー構造を下層の方へとたどっていることから、これらのツリー構造は、実際には最上層から読まれる。このように、最も頻繁に出現するキャラクタが最初に遭遇することになる。ハフマン符号化の問題点の１つには、キャラクタに割り当てられた確率が予測できないということにある。一般的に、ハフマンツリー構造は、特定のデータセットにあてはまるかどうか判断のつかない予め定まった頻度を用いて生成されている。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
【発明が解決しようとする課題】
適応統計学を用いることにより、記号セットが事前認識できるかどうかに関わる問題点の一部に対処する対策がえられる。一般に、適応符号化アルゴリズムでは、記号一覧テーブルや接頭語一覧テーブルにない記号を符号化することができる。未知の記号が発見されたならば、拡張コード（ＥＳＣ値）がだされてコード化ストリームに入れられる。符号器は、より低次(order)の接頭語で符号化処理を継続し、符号化したビットストリームへ追加データを加える。最も低次の予測テーブル（たいていは、０次テーブル(order 0 table)）には、あらゆる出現し得る記号がそのテーブルから見つかるように、全ての発生し得る記号を含んでいなければならない。ＥＳＣコードは、確率を用いて符号化されていなければならない。しかしながら、新しい記号は予測不可能であるから、ＥＳＣコードの確率は、先行するデータから正確に推測することはできない。ある一定の接頭語に対するＥＳＣ値の確率はしばしば経験的に判断されているので、効率としては最適なものではない。このようにして、適応符号化アルゴリズムにＥＳＣコードを採用するには、２つの問題が浮上してくる。第一に、新しい記号についてはＥＳＣコードでは限られた情報しか得られない。従って、新しい記号に関する限り、低次の接頭語予測テーブルを用いて常に符号化されなければならない。第二に、ＥＳＣコードの確率は正確にモデル化できない。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
また別の面での本発明では、確率テーブルに表われず、従来の圧縮技術を用いて効率よく圧縮することが特に難しい記号を、効率よく評価及び符号化することが可能である。例えば、ハフマン符号化においては、未知の記号または拡張値の出現頻度が非常に高ければ、これによって短いコード（そして、そのために他の既知の記号に用いられるコードが長くなる）が要求される。好ましい実施の形態においては、記号は、結合されたバイナリツリーにおいて、根から葉までの進路をなぞるように符号化される。単一ステップにおいて記号を符号化する従来アプローチとは異なり、その好ましい実施の形態においては、記号は、バイナリツリーの階層に対応する各ステップを伴う、複数のステップで符号化される。記号は、少しずつ効果的に符号化される。このビット毎の分解により２つの利点が得られる。第一に、来ている記号がどのようなものかについて疑いがないとき、ビット毎の分解がＥＳＣ値の使用をもっと遅い時間に遅らせる。第二に、それがＥＳＣ値を特定の記号へ辿ってもいくことが回避され、より低次の接頭語を伴って再度、記号を符号化する必要を除去する。バイナリツリーが結局いずれかの進路に沿って記号に辿り着くに違いないので、符号化された進路により、記号の発見に導かれるのである。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
接頭語予測（１００を以て示す）を用いる符号化システムは、演算装置１１０を含む。この演算装置１１０は、中央処理装置１１５、メモリー１２０及び操作者インタフェース１３０と接続したＩ／Ｏ部１２５からなる。メモリー１２０は、磁気ディスク、磁気テープ、光デバイス、光磁気デバイス或いは他の大容量記憶装置のような比較的大量の情報を格納するデバイスが備わっていてもよい。ここで使う「演算装置」という用語は、広義的な意味での装置であり、プログラムにより制御可能なプロセッサを有するか、パーソナルコンピュータ、ラップトップやパーソナルデジタルアシスタントのような、その他の一般的にチューリング機械の範疇にある装置を含むものを意味する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
１次予測テーブル２１０は、１つ以上の接頭語記号２１５のセット、各接頭語記号２１５の後続する可能性のある１つ以上の記号２２０のセット、及び確率値２２５のセットを含んでいる。接頭語記号２１５は、特定の順序付けされた文字列のごく初めにあるものとして、識別される記号である。記号２２０のセットは、複数の現実の文字とＥＳＣ２２１との両方を含む。確率値２２５は、特定の記号２２０が当該の接頭語２１５の後続する確率を反映する。１次テーブル２１０において、各接頭語記号２１５の長さは１文字分に限定されている。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
データツリー３００は、トップダウンで読まれるように設計されたバイナリツリーである。根３０５には、記号の全てのセットが含まれている（特定の用途で発生し得る全記号）。分岐ノード（３１０、３２０、３３０、３４０、３５０、又は３６０で示した部分）には記号のサブセットが含まれている。末端のノードは葉と呼ばれ、各葉は単一な記号を含み、全セットの記号とは異なる記号である。ノードの左枝はゼログループと呼ばれ、右のグループがワングループと呼ばれる。ゼログループは０ビット値で表した枝と関連する。ワングループは１ビット値で表した枝と関連する。各枝は、ゼログループまたはワングループである下位ノードにおける記号の確率を表わす浮動小数点式の数と関連している。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
バイナリデータツリー３００は、テーブル２１０に表記された値と確率を用いて構築される。根３０５は、記号の全てのセット（この場合は、｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ｝）を含み、その内のＡ、Ｂ、Ｃ及びＤがヒット記号であり、Ｅ、Ｆ、Ｇ及びＨがミス記号である。全セットの記号はｂ２の値に基づいてゼロとワングループとに区画される。これらの記号のｂ２ビットが０であるから、ノード３１０におけるワングループには、Ｄ、Ｆ、Ｇ及びＨが含まれている。ｂ２は、ゼログループにおけるヒット記号（Ａ、Ｂ、Ｃ）の確率合計のＯＰは、０．９となり、ワングループにおけるヒット記号（Ｄ）の確率合計のＺＰは、０．０７となるから、最初の区画に選択される。ｂ１が０．６５（ゼログループのＡ、Ｅ、Ｆ、Ｇ）と０．３２（ワングループのＢ、Ｃ、Ｄ、Ｈ）の区画になり、ｂ０が０．８７（ゼログループのＡ、Ｂ、Ｄ、Ｆ）と０．１０（ワングループのＣ、Ｅ、Ｇ、Ｈ）の区画になるとすれば、これは最も不均衡な結果である。ツリーを下位の方へ辿っていけば、ノード３１０はｂ０で区画される。結果として構築されるツリーが同じ確率値を有しているから、ノード３２０は、ｂ１かｂ０のいずれかで区画されてもよい。ｂ１ビットがミス記号（ＦとＧ）だけを含んでいるゼログループとなる一方、ｂ０ビットがミス記号（ＧとＨ）だけを含んでいるワングループとなる。あいまいな表現をさけるため、より高い位置（例えば、左側において）のビットを選んでいる。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００３３
【補正方法】変更
【補正の内容】
【００３３】
ある特定の接頭語の下での記号Ｘの符号化は、下記の３ステップで行われる。
１．特定接頭語の予測テーブルに基づくバイナリツリーの構築
２．根から記号Ｘへの進路の識別
３．進路における各確率の符号化
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００３４
【補正方法】変更
【補正の内容】
【００３４】
例えば、同図において、記号Ｄは３つの確率である、０．０７２２、０．８３７８及び０．９０３２を用いて符号化されており、Ｅは０．９２７８、０．１１１１及び０．０６９８を用いて符号化されている。各確率値は、標準の算術符号化方法を用いて符号化される。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００４０
【補正方法】変更
【補正の内容】
【００４０】
ステップ４２０では、コンピュータプログラム１４０はバロウズ・ホイラー変換と前方移行変換(Move-to-front transform)を用いて、データ１５０の順序を変更すべく命令セットを実行する。データの中に含まれる記号の順序を変更すると、分布の確率が変ったり、入力値が位置インデックスにより取り替えられたりする。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００４３
【補正方法】変更
【補正の内容】
【００４３】
ステップ４３５では、図４に示すように、コンピュータプログラム１４０が、各一組のゼロ及びワングループにおけるヒット記号（ミス記号を除外する）の確率合計の不均衡を最大にするようにバイナリツリーを生成する。各記号は、その記号に対する根に結合された一意の進路により表現される。進路は複数の枝からなり、各枝には暫定的な確率値が割り当てられる。記号の符号化は、根からその記号へ至る進路に割り当てられた確率値へ符号化することにより行われる。