(57)【要約】平文から暗号文を作成および暗号文を解読するための方法および装置であって、符号化および解読の両方のためにツリー構造を利用し、上記ツリーは、平文シンボルに関連付けられたリーフと、暗号文アルファベットの要素が割当てられたブランチとを有し、符号化の際には、ルートと、平文に対応するリーフとの間でトラバースが行なわれ、各々のトラバースされたブランチに関連付けられた暗号文を記録し、解読の際には、リーフに到達するまで、暗号文を用いて、トラバースされるべきブランチを判断し、このリーフに関連付けられた平文を記録する。
2005504348.tif 000002
【特許請求の範囲】
【請求項１】
平文から暗号文を作成する方法は次のステップから成る。:
(a)平文の１文字を受け取る;
(b)Oommen-Rueda ツリーを、ルートと平文のその文字に対応するリーフの間でトラバースし、そのようにトラバースした各々のブランチのアサイメントバリューを記録する;
(c)平文の次の文字を受け取る;そして
(d)平文が全て処理されるまでb とc のステップを繰り返す。
【請求項２】
平文から暗号文を作成する方法は次のステップから成る。:
(a)Oommen-Rueda ツリーを構築する;
(b)平文の１文字を受け取る;
(c)Oommen-Rueda ツリーを、ルートと平文のその文字に対応するリーフの間でトラバースし、そのようにトラバースした各々のブランチのアサイメントバリューを記録する;
(d)平文の次の文字を受け取る; そして
(e)平文が全て処理されるまでcとdのステップを繰り返す。
【請求項３】
平文から暗号文を作成する方法は次のステップから成る:
(a)Oommen-Rueda ツリーを受け取る;
(b)平文の１文字を受け取る;
(c)Oommen-Rueda ツリーを、ルートと平文のその文字に対応するリーフの間でトラバースし、そのようにトラバースした各々のブランチのアサイメントバリューを記録する;
(d)平文の次の文字を受け取る;そして
(e)平文が全て処理されるまでcとdのステップを繰り返す。
【請求項４】
平文から暗号文を作成する方法は次のステップから成る:
(a)Oommen-Rueda ツリーを構築する。そのOommen-Rueda ツリーは平文の文字のメンバーと関連するリーフを持ち、平文のアルファベットの各メンバーは少なくとも１つのリーフと関連する。そのOommen-Rueda ツリーの内部のノードは少なくともそのノードから一本のブランチが伸びている。そのOommen-Rueda ツリーのブランチはアサイメントバリューと関連し、そのアサイメントバリューは暗号文のアルファベットのメンバーと関連している。このOommen-Rueda ツリーの各ノードは、その各従属ノードとリーフの頻度ウエイト（frequency weight）に関した数と関連している;
(b)平文の１文字を受け取る;
(c)Oommen-Rueda ツリーを、ルートと平文のその文字に対応するリーフの間でトラバースし、そのようにトラバースした各々のブランチのアサイメントバリューを記録する;
(d)平文の次の文字を受け取る; そして
(e)平文が全て処理されるまでc とd のステップを繰り返す。
【請求項５】
平文から暗号文を作成する方法は次のステップから成る:
(a)Oommen-Rueda ツリーを受け取る。そのOommen-Rueda ツリーは平文の文字のメンバーと関連するリーフを持ち、平文のアルファベットの各メンバーは少なくとも１つのリーフと関連する。そのOommen-Rueda ツリーの内部のノードは少なくともそのノードから一本のブランチが伸びている。そのOommen-Rueda ツリーのブランチはアサイメントバリューと関連し、そのアサイメントバリューは暗号文のアルファベットのメンバーと関連している。このOommen-Rueda ツリーの各ノードは、その各従属ノードとリーフの頻度ウエイト（frequency weight）に関した数と関連している;
(b)平文の１文字を受け取る;
(c)Oommen-Rueda ツリーを、ルートと平文のその文字に対応するリーフの間でトラバースし、そのようにトラバースした各々のブランチのアサイメントバリューを記録する；
(d)平文の次の文字を受け取る;そして
(e)平文が全て処理されるまでcとdのステップを繰り返す。
【請求項６】
これらの請求項1, 2, 3, 4 , 5 による平文から暗号文を作成する方法で、少なくとも１本のブランチがトラバースされたもののアサイメントバリューは、ブランチアサイメントルールによって決定される。
【請求項７】
請求項６による平文から暗号文を作成する方法は、暗号文アルファベットのメンバーがそれまでに生成された暗号文の中で少ない頻度で現れている場合、アサイメントの前のように暗号文のアルファベットのメンバーが以前よりも少ない頻度で表わされないように、ブランチアサイメントルールはその暗号文のアルファベットのメンバーをルートとリーフの間でトラバースされている少なくとも１本のブランチに割り当てる。
【請求項８】
請求項６による平文から暗号文を作成する方法は、暗号文アルファベットのメンバーがそれまでに生成された暗号文の中で少ない頻度で現れている場合、アサイメントの前のように暗号文のアルファベットのメンバーが以前よりも少ない頻度で現れないように、ブランチアサイメントルールはその暗号文のアルファベットのメンバーをほかの暗号文のアルファベットのメンバーよりも頻繁にルートとリーフの間でトラバースされているブランチに割り当てる。
【請求項９】
請求項６による平文から暗号文を作成する方法は、暗号文アルファベットのメンバーが二進数の場合、もしゼロがそれまでに生成された暗号文の中に少ない頻度で現れていたら、ブランチアサイメントルールはルートとリーフの間でトラバースされているブランチの大部分にゼロを割り当てる。もし１ががそれまでに生成された暗号文の中に少ない頻度で現れていたら、ブランチアサイメントルールはルートとリーフの間でトラバースされているブランチの大部分に１を割り当てる。
【請求項１０】
請求項６による平文から暗号文を作成する方法は、そこまでに生成された暗号文中の暗号文のアルファベットのメンバーの特定のシークエンスにおいて、暗号文のアルファベットの1 つのメンバーの条件付き頻度がそこまでに生成された暗号文中で少なく現れている場合、ブランチアサイメントルールは、割り当ての前のようにその暗号文のアルファベットのメンバーの条件付頻度が以前よりも少なく現れないように、その暗号文のアルファベットのメンバーをルートとリーフの間でトラバースされている少なくとも１本のブランチに割り当てる。
【請求項１１】
請求項６による平文から暗号文を作成する方法は、そこまでに生成された暗号文中の暗号文のアルファベットのメンバーの特定のシークエンスにおいて、暗号文のアルファベットの1 つのメンバーの条件付き頻度がそこまでに生成された暗号文中で少なく現れている場合、ブランチアサイメントルールは、割り当ての前のようにその暗号文のアルファベットのメンバーの条件付頻度が以前よりも少なく現れないように、その暗号文のアルファベットのメンバーを、ほかの暗号文のアルファベットのメンバーよりも頻繁に、ルートとリーフの間でトラバースされているブランチへ割り当てる。
【請求項１２】
請求項６による平文から暗号文を作成する方法では、ブランチアサイメントルールは、暗号文のアルファベットのメンバーを、少なくとも１本のルートとリーフの間でトラバースされているブランチへ割り当てる。このようなアサイメントはこれまでに生成された暗号文の中のアルファベットの少なくとも１つのメンバーの頻度に関連する数と、偽似乱数ジェネレーターの出力に関係する数との比較により決定される。
【請求項１３】
請求項６による平文から暗号文を作成する方法では、暗号文のアルファベットが２進数の場合、ブランチアサイメントルールは２進数のアルファベットのメンバーを少なくとも１本のルートとリーフの間でトラバースされているブランチへ割り当てる。このような割り当ては、これまでに生成された暗号文の２進数アルファベットのメンバーの頻度と関連した数と、偽似乱数ジェネレーターの出力に関係する数との比較により決定される。
【請求項１４】
請求項６による平文から暗号文を作成する方法では、ブランチアサイメントルールは、暗号文のアルファベットのメンバーを、少なくとも１本のルートとリーフの間でトラバースされているブランチへ割り当てる。このような割り当ては、偽似乱数ジェネレーターの出力に関係する数により決定される。
【請求項１５】
請求項６による平文から暗号文を作成する方法では、暗号文のアルファベットが２進数の場合、ブランチアサイメントルールは２進数のアルファベットのメンバーを少なくとも１本のルートとリーフの間でトラバースされているブランチへ割り当てる。このような割り当ては、偽似乱数に関係した数と偽似乱数を生成するジェネレーターの領域の半分に相当する範囲との比較によって決定される。
【請求項１６】
請求項６による平文から暗号文を作成する方法では、ブランチアサイメントルールは、サイズRの暗号文のアルファベットのメンバーを、少なくとも１本のルートとリーフの間でトラバースされているブランチへ割り当てる。このような割り当ては、少なくとも２度(R - 1)の偽似乱数の実行と、ここまでに生成された暗号文の文字の発生頻度に関する少なくとも１つの偽似乱数の領域、そして、トラバースで遭遇した各ノードのi番目のブランチで平均i/R を持った他の偽似乱数の少なくとも1 つの領域（この時、i はブランチのあらかじめ指定された順番により数が定められたブランチの相対的な位置であり、このブランチアサイメントルールで、このような順番でのi番目のブランチに関連する暗号文の文字がここまでに生成された暗号文のなかで少なく現われていたものが、以前よりも少なくは現われない）によって決定される。
【請求項１７】
請求項６による平文から暗号文を作成する方法では、暗号文のアルファベットが２進数の場合、ブランチアサイメントルールは２進数の暗号文のアルファベットのメンバーを少なくとも１本のルートとリーフの間でトラバースされているブランチへ割り当てる。このような割り当ては、少なくとも２度の偽似乱数の実行と、暗号文の中のゼロの発生頻度に関連する１番目の偽似乱数の領域、そして、平均0.5の２番目の偽似乱数の領域によって決定され、このようなブランチアサイメントルールのために、これまでに生成された暗号文の中で少なく現わされた暗号文のアルファベットの全ての文字が以前よりも少なくは現されない。
【請求項１８】
請求項６による平文から暗号文を作成する方法では、暗号文のアルファベットが２進数の場合、ブランチアサイメントルールは２進数の暗号文のアルファベットのメンバーを少なくとも１本のルートとリーフの間でトラバースされているブランチへ割り当てる。このような割り当ては、少なくとも２つの実行された偽似乱数の出力の比較によって決定される。１番目の偽似乱数はゼロの頻度に関した数と0.5の間の平均を取る領域を持ち、２番目は平均が0.5 の領域を持つ偽似乱数である。これまでに生成された２進数の暗号文の中で少なく現れていた全てのメンバーは、以前よりも少なく現れない。
【請求項１９】
請求項６による平文から暗号文を作成する方法では、暗号文のアルファベットが２進数の場合、ブランチアサイメントルールは、２つの偽似乱数の利用によって、２進数の暗号文のアルファベットのメンバーを少なくとも１本のルートとリーフの間でトラバースされているブランチへ割り当てる。この際、最初の偽似乱数が２番目の偽似乱数より小さい場合ゼロが割り当てられ、この時、第2の偽似乱数の生成は、これまでに生成された暗号文中の0 の頻度に関する数と、１からこれまでに生成された暗号文の中の0の頻度に関した前述の数を引いた数に関連した数の間に制限される。
【請求項２０】
請求項1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19による平文から暗号文を作成する方法では、さらなるステップを含み、Oommen-Rueda ツリーの少なくとも１度のトラバースの後、付随する内部のノードとリーフを含むOommen-Rueda ツリーの、少なくとも１つのノードの頻度ウエイト（the frequency weight）に関連する数を再計算する。それから、ツリーの再構築ルールに従って、Oommen-Rueda ツリーを再構築する。
【請求項２１】
請求項12, 13, 14, 15, 16, 17, 18, 19, 20, による平文から暗号文を作成する方法では、さらに、ブランチアサイメントルールに使われた偽似乱数の少なくとも一つのジェネレーターの最初のシードに関するはじめのキーデータを受け取るというステップを含む。
【請求項２２】
請求項1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21による平文から暗号文を作成する方法では、Oommen-Rueda ツリーのラベル付けと構成に関する２番目のキーデータを受け取るという更なるステップを含む。
【請求項２３】
請求項1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22による平文から暗号文を作成する方法では、平文はあらかじめ指定された接頭的なデータストリームの追加によって処理するまえに修正される。
【請求項２４】
請求項1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23 による平文から暗号文を作成する方法では、少なくとも１つのステップは適切にプログラムされたプロセッサーによって実行されなければならない。
【請求項２５】
請求項1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23による平文から暗号文を作成する方法では、ステップの少なくとも1 つはソフトウェアで実行されたプロセスである。
【請求項２６】
請求項1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23による平文から暗号文を作成する方法では、ステップの少なくとも1つはファームウェアの中で実行されたプロセスである。
【請求項２７】
暗号文を解読する方法は次のステップから成る:
(a)暗号文の最初の文字を受け取る;
(b)最初にエンコーダーに使われたのと同じOommen-Rueda ツリーに対応する構成のOommen-Rueda ツリーを使う。また、ルートに付随するブランチにアサイメントバリューを与えるためにエンコーダーが使ったのと同じブランチアサイメントルールを使い、そのOommen-Rueda Tree をルートからリーフにかけてトラバースする。この際、暗号文の最初の文字が次にトラバースされるブランチを決める;
(c)リーフに到達していない場合、その到達したノードに付随するブランチにアサイメントバリューを与えるためにエンコーダーが使ったのと同じブランチアサイメントルールを使い、暗号文の次の文字を受け取り、その到達したノードからリーフに向かってOommen-Rueda ツリーをトラバースし続ける。この際、暗号文の現在のシンボルが次にトラバースされるブランチを決める;
(d)リーフに到達したら、リーフのラベルに関連した平文の文字を記録し、ルートは更なるプロセスのために到達されたノードとなる;
(e)暗号文のシンボルが全て処理されるまでステップcとdを繰り返す。
【請求項２８】
暗号文を解読する方法は次のステップから成る:
(a)最初にエンコーダーに使われたのと同じOommen-Rueda ツリーに対応するOommen-Rueda ツリー構造を構築する;
(b)暗号文の最初の文字を受け取る;
(c)Oommen-Rueda ツリー構造を使い、そして、ルートに付随するブランチにアサイメントバリューを与えるためにエンコーダーが使ったのと同じブランチアサイメントルールを使い、そのOommen-Rueda Tree をルートからリーフにかけてトラバースする。この際、暗号文の最初の文字が次にトラバースされるブランチを決める。;
(d)リーフに到達していない場合、その到達したノードに付随するブランチにアサイメントバリューを与えるためにエンコーダーが使ったのと同じブランチアサイメントルールを使い、暗号文の次の文字を受け取り、その到達したノードからリーフに向かってOommen-Rueda ツリーをトラバースし続ける。この際、暗号文の現在のシンボルが次にトラバースされるブランチを決める;
(e)リーフに到達したら、リーフのラベルに関連した平文の文字を記録し、ルートは更なるプロセスのために到達されたノードとなる;
(f)暗号文のシンボルが全て処理されるまでステップdとeを繰り返す。
【請求項２９】
暗号文を解読する方法は次のステップから成る:
(a)最初にエンコーダーに使われたOommen-Rueda ツリーに対応する構造を持つOommen-Ruedaを構築するために、最初にエンコーダーに使われたOommen-Rueda ツリーに対応するデータを受け取る;
(b)暗号文の最初の文字を受け取る;
(c)最初にエンコーダーに使われたのと同じOommen-Rueda ツリーに対応する構成のOommen-Rueda ツリーを使う。また、ルートに付随するブランチにアサイメントバリューを与えるためにエンコーダーが使ったのと同じブランチアサイメントルールを使い、そのOommen-Rueda Tree をルートからリーフにかけてトラバースする。この際、暗号文の最初の文字が次にトラバースされるブランチを決める;
(d)リーフに到達していない場合、その到達したノードに付随するブランチにアサイメントバリューを与えるためにエンコーダーが使ったのと同じブランチアサイメントルールを使い、暗号文の次の文字を受け取り、その到達したノードからリーフに向かってOommen-Rueda ツリーをトラバースし続ける。この際、暗号文の現在のシンボルが次にトラバースされるブランチを決める;
(e)リーフに到達したら、リーフのラベルに関連した平文の文字を記録し、ルートは更なるプロセスのために到達されたノードとなる;
(f)暗号文のシンボルが全て処理されるまでステップdとeを繰り返す。
【請求項３０】
請求項27, 28, 29による暗号文の解読方法では、エンコーダーが請求項20によると、ツリーの再構築ルールを使った場合、リーフへのOommen-Ruedaツリーのトラバースが少なくとも１度終わったあと、そこから付随する内部のノードとリーフを含むOommen-Rueda ツリーの少なくとも１つのノードの頻度ウエイト（frequency weight）に関連する数を再計算する。その後、Oommen-Rueda ツリーはエンコーダーに使われたのと同じツリー再構築ルールを使って構築される。
【請求項３１】
請求項27, 28, 29, 30による暗号文の解読方法では、ブランチアサイメントルールに使われた擬似乱数の少なくても１つのジェネレーターの最初のシードに関するキーデータを受け取るという更なるステップを含む。この時、最初のキーデータはエンコーダーに使われた最初のキーデータに対応する。
【請求項３２】
請求項27, 28, 29, 30, 31による暗号文の解読方法では、Oommen-Rueda ツリーの構造とラベル付けに関する２番目のキーデータを受け取るという更なるステップを含む。この時、２番目のキーデータはエンコーダーに使われた２番目のキーデータに関連する。
【請求項３３】
請求項27, 28, 29, 30, 31, 32 による暗号文の解読方法では、平文が、あらかじめ指定された接頭的なデータストリームの追加によって処理する前に修正された場合、暗号文は、接頭的な方法で、符号化されたあらかじめ特定されたデータストリームの追加によって処理する前に修正される。この時、この符号化されあらかじめ特定されたデータストリームはエンコーダーに使用されたあらかじめ特定されたデータストリームと関連したものである。
【請求項３４】
請求項27, 28, 29, 30, 31, 32, 33 による暗号文の解読方法では、少なくとも１つのステップが適切にプログラムされたプロセッサーによって実行される。
【請求項３５】
請求項27, 28, 29, 30, 31, 32, 33 による暗号文の解読方法では、ステップの少なくとも1 つはソフトウェアで実行されたプロセスである。
【請求項３６】
請求項27, 28, 29, 30, 31, 32, 33 による暗号文の解読方法では、ステップの少なくとも1 つはファームウェアの中で実行されたプロセスである。
【請求項３７】
平文から暗号文を作成するためのデバイスは下記のものを含む:
(a)平文のデーターストリームを受け取る受け取り手段;
(b)Oommen-Rueda ツリーのデータ標本を保管する保管手段;
(c)平文のデータストリームを１文字ずつプロセスするプロセス手段。プロセスされる平文の各文字に対して保管されたOommen-Rueda ツリーを繰り返しトラバースする。この時、各トラバースはルートとプロセスされている平文のシンボルに対応するリーフの間で行われる;
(d)平文のデータストリームの処理のためにトラバースされるOommen-Rueda ツリーのブランチのアサイメントバリューを記録する記録手段;
受け取り手段、保管手段、そして記録手段は、プロセス手段とのコミュニケーションにある。
【請求項３８】
請求項３７による平文から暗号文を作成するデバイスはさらに、ブランチアサイメントルールを保管するための、プロセス手段とのコミュニケーションにの下にある、別の保管手段を必要とする。そこでこのプロセス手段は加えて、それまでに生成された暗号文の中の、少なくとも１つの暗号文アルファベットの頻度に関した数を計算し、プロセス中に到達した少なくとも１つのノードから伸びている、少なくとも１本のブランチのアサイメントバリューを計算する。
【請求項３９】
暗号文を解読するデバイスは下記のものを含む:
(a)暗号文のデーターストリームを受け取る受け取り手段;
(b)エンコーダによって使用されたOommen-Rueda ツリーのデータ表現を保管する保管手段;
(c) 以下のためのプロセス手段:
1.暗号文のデータストリームの１文字ずつのプロセス、
2.保管されたOommen-Rueda ツリーをルートとリーフの間で繰り返しトラバースする。どのブランチをトラバースするかは、プロセスされる暗号文の文字とブランチのアサイメントバリューとの比較により決定される;
3.次にプロセスされる暗号文の文字を選び、次にトラバースすべきブランチを決定する。これはリーフに到達するまで続けられる。リーフに到達したら、そのリーフに関連した平文の文字が記録され、プロセスはルートから続く; そして
4.上記のステップ(1),(2)そして(3)を、処理されるべき暗号文が全てプロセスされるまで繰り返す;
(d)プロセス中に到達したリーフと関連した平文の記録の受け取り手段;
受け取り手段、保管手段、そして記録手段は、プロセス手段とのコミュニケーションにある。
【請求項４０】
請求項３９による暗号文の解読のためのデバイスは、さらに、ブランチアサイメントルールを保管するための、プロセス手段とのコミュニケーションにの下にある、別の保管手段を必要とする。そこでこのプロセス手段は加えて、それまでに処理された暗号文の中の、少なくとも１つの暗号文アルファベットの頻度に関した数を計算し、プロセス中に到達した少なくとも１つのノードから伸びている、少なくとも１本のブランチのアサイメントバリューを計算する。
【請求項４１】
安全なコミュニケーション方法は次のステップを含む:
(a)請求項1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26で示された方法によるコミュニケーションの符号化;
(b)符号化されたコミュニケーションの送信;
(c)符号化されたコミュニケーションの受信;
(d)請求項27, 28, 29, 30, 31, 32, 33, 34, 35, 36で示された方法による符号化されたコミュニケーションの解読。
【請求項４２】
安全なデータ保管、および回復方法は次のステップを含む:
(a)請求項1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 15, 19, 20, 21, 22, 23, 24, 25, 26 で示された方法によるデータの符号化;
(b)符号化されたデータの保管;
(c)符号化されたデータの回復;
(d)請求項27, 28, 29, 30, 31, 32, 33, 34, 35, 36で示された方法による符号化されたデータの解読。
【請求項４３】
請求項1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 による平文から暗号文の作成方法は、さらに、請求項1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26のプロセスにより生成された暗号文を続けて（あらゆる一般的な暗号化プロセスによって）暗号化するステップを含む。
【請求項４４】
請求項27, 28, 29, 30, 31, 32, 33, 34, 35, 36による暗号文の解読方法は、さらに、はじめに請求項43で使われた暗号化プロセスに対応する一般的な解読プロセスを使って暗号文のデータストリームを解読するというステップを含む。その後、請求項27, 28, 29, 30, 31, 32, 33, 34, 35, 36によって解読する。
【請求項４５】
平文のメッセージををキャリアーデータへ埋め込む方法は、請求項1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26による平文を暗号文に変換するステップを含む。そしてその後、キャリアー・データにステガノグラフィー（steganography）の要領で暗号文を挿入する。
【請求項４６】
請求項４５従って、ステガノグラフィー（steganography）の要領で埋め込まれた暗号文を含むキャリアーデータから平文のメッセージを抽出する方法は、キャリアーデータから暗号文をステガノグラフィー（steganography）の要領で抽出し、さらに請求項27, 28, 29, 30, 31, 32, 33, 34, 35, 36のプロセスを使った暗号文の解読ステップを含む。
【請求項４７】
擬似乱数を生成する方法は、無作為なデータストリームを受け取り、請求項12, 13, 14, 15, 16, 17, 18,または19に従ってそのデータストリームをプロセスするというステップを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
この発明は、データの符号化および暗号化の分野、特に、平文を暗号文に変換する際に平文の統計的な情報が削除されるデータ暗号化に関連している。
【背景技術】
【０００２】
発明の背景
秘密にメッセージを送る必要性は暗号化の技術および科学の発展をもたらし、１千年間もの間使用されている。この分野および最先端技術に関する優れた調査はMenezes et alで見ることができる。(Handbookof Applied Cryptography, CRC Press, (1996)), Stallings (Cryptography & Network Security: Principles & Practice, Prentice Hall, (1998)), Stinson(Cryptography : Theory and Practice, CRC Press, (1995))。
【０００３】
完璧な暗号体系を持つという証明は、完全な秘密(Perfect Secrecy)と呼ばれる主要な特性を持つことである。この特性というのは、全ての入力データストリームに対して、入力とは関係なく与えられた出力データストリームの産出の確率が同じであるということである。従って、出力データストリームあるいは暗号文には入力データや平文の一致および配分に関する統計の情報はない。
【０００４】
完全な秘密(Perfect Secrecy)を達成するという問題は、元来Cによって形式化された。1949年にShannonは、暗号体系が完全な秘密(Perfect Secrecy)を保つにはシークレットキーの長さが少なくとも平文と同じくらい長くなくてはならないことを示した。(Shannon (Communication Theory of Secrecy Systems, Bell System Technical Journal, 28:656-715, (1949))参照)。この制限は実際の暗号体系の中で完全な秘密(Perfect Secrecy)を非実用的にする。完全な秘密(Perfect Secrecy) を提供するシステムの例はVernam のOne-time padだ。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
データの符号化および暗号学の分野での未解決の関連した2つの問題は次のとおりである。
【０００６】
1.出力確率の最適化
データ圧縮/符号化のために考案された多数の案がある。出力シンボルの無作為の符号化を得るという問題は、少なくとも50年以上もの間研究者達によって研究されている。多くの符号化のアルゴリズム(Huffman、Fano、Shannonの、算術コード化および他のもののような)が、様々な統計と構造モデル(例えばディクショナリー構造、より高いオーダーの統計モデルなど)を使用して開発されている。それらはすべてデータを圧縮するのを目的としている。しかし、それらの主な欠点は、出力シンボルの確率をコントロールすることができないということである。この分野に関する調査はHankerson et alで見ることができる。(Introduction to Information Theory and Data Compression, CRC Press, (1998)), Sayood (Introduction to Data Compression, Morgan Kaufmann, 2nd. edition, (2000)), Witten et al. (Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann, 2nd. edition, (1999))。
【０００７】
以前の案には、一旦データ圧縮/符号化の方法が指定されると、ユーザーは、内容と、圧縮またはコード化されたファイルの統計的なプロパティのコントロールを失うという欠点がある。言いかえれば、出力圧縮ファイルの統計的なプロパティーはユーザのコントロールの及ばないものであり、それらの価値を無圧縮ファイルおよびデータ圧縮方法の統計的なプロパティーの結果として受け入れることになる。
【０００８】
ここ何十年の間解決のつかない問題は、ここではDistribution Optimizing Data Compr ession(または”DODC”)問題と参照するが(あるいは、平文を単に圧縮しないもっと一般的な情況では、Distribution Optimizing Data Encoding(または”DODE”)問題として参照する)、データファイル上で適用された時、ファイルを圧縮すると同時に、ファイルにランダムなノイズとして見せるという圧縮スキームの考案から成り立つ。(Hankerson et al.(Introduction to Information Theory and Data Compression, CRC Press, (1998) pp.75-79) 参照)この問題の詳しい定義は付録Aに参照する。入力文字が2進法の場合、「0」と「1」の入力確率はランダムになりえ、全て平文によって決定される。圧縮ファイルの中のユーザー指定の「0」と「1」の出力確率は、これまで解決のつかない問題と考えられてきた。実際、ユーザーがこの厳重な制約を指定することができたならば、「0」と「1」の出力確率は約0.5となり、それは統計的な情報の抹消につながり、結果は非常に大きいものとなる。
【０００９】
2.統計の完全な秘密(Statistical Perfect Secrecy)の達成
入力データおよび出力データストリームから統計の配分を削除するという問題は、暗号の適用において非常に重要である。優れた暗号体系であるためにはランダムな特性を持つ出力を生み出さなければならないということはよく知られている。(Menezes et al. (Handbook of Applied Cryptography, CRC Press, (1996)), Stallings (Cryptography & Network Security: Principles & Practice, Prentice Hall, (1998)), Stinson (Cryptography : Theory and Practice, CRC Press, (1995)), Shannon (Communication Theory of Secrecy Systems, Bell System Technical Journal, 28:656-715, (1949)) 参照)。
【００１０】
暗号学の主な目的は完全な秘密(Perfect Secrecy) を達成することである。(Stinson, Cryptography : Theory and Practice, CRC Press, (1995))参照)。
【００１１】
この特性を満たす実用的な符号化システムの開発は何十年もの間未解決の問題である。Shannonは、暗号体系が完全な秘密(Perfect Secrecy)を達成するにはシークッレトキーの長さが平文と少なくとも同じくらい長くなくてはならないことを示した。(Menezes (Handbook of Applied Cryptography, CRC Press, (1996)), Stallings Cryptography & Network Security: Principles & Practice, Prentice Hall, (1998)), Stinson (Cryptography : Theory and Practice, CRC Press, (1995)), Shannon (Communication Theory of Secrecy Systems, Bell System Technical Journal, 28:656-715, (1949)) 参照)。これは、VernamのOne-time Padによって実証されたように、現実的な完全な秘密(Perfect Secrecy) を持つ暗号体系の開発を非現実的にする。
【００１２】
X = x[1] ... x[M] が平文のデータストリームで、（この時、各x[k]は平文のアルファベットから取り出される）、S = {s1... sm} とY =y[1] ... y[R] が暗号文のデータストリーム（ここでy[k] ∈ A、サイズr である）であるという体系を考えてみて欲しい。
【００１３】
簡単に言うと,システム(暗号体系、圧縮システム、そして一般的に、符号化システムを含む) は長さkの連続した出力が、すべてのkの値に対してXと無関係で、ほぼ等しく起こる場合、統計の完全な秘密（Statistical Perfect Secrecy）を持っていると言われる。従って、入力ストリームの統計のプロパティーをすべて削除するスキームは、統計の完全な秘密（Statistical Perfect Secrecy）のプロパティーを持つと言える。統計の完全な秘密（Statistical Perfect Secrecy）を持つシステムは、一文字づつ計算された出力のエントロピーを最大限にする。
【００１４】
詳しく言うと,全ての入力Xに対して、ある整数
【００１５】
【数１】
2005504348.tif 000003
【００１６】
と、0に近い小さい、0よりも大きい実数δ0が存在する場合、システムは統計の完全な秘密（Statistical Perfect Secrecy）を有していると言われる。この際、全てのj > j0において、
【００１７】
【数２】
2005504348.tif 000004
【００１８】
で、全てのkが,0 < k < R - j0 である。
【００１９】
この特性を所有するシステムは正確に統計の完全な秘密（Statistical Perfect Secrecy）を保持しているといわれる。これは、統計的な面で、すべての実用的な目的において、そして、有限の長さのサブシークエンスにおいて、あたかもそれが、完全な秘密（Perfect Secrecy）の強い特性があるかのようにシステムが作用するからである。
【００２０】
完全な秘密（Perfect Secrecy）の概念と統計の完全な秘密（Statistical Perfect Secrecy）が関連していることは興味深い。しかしながら、統計の完全な秘密（Statistical Perfect Secrecy）の特性が単なる暗号体系ではなくどんな体系も特徴づけることができるので、Shannonの定理によって要求されるように、入力のサイズとキーのサイズを関連づける必要はない。
【課題を解決するための手段】
【００２１】
発明の要約
この発明の目的はデータを符号化および解読するより良い方法を提供することであり、それらはユーザが暗号文の統計のパラメーターを指定し、平文を暗号文へ符号化する過程に統計情報をコントロール、あるいは削除することを可能にする。
【００２２】
データを符号化および解読するより良い方法を提供することは現在の発明の具体化の一層の目的であり、それらはユーザーが暗号文中の統計の完全な秘密（Statistical Perfect Secrecy）を得ることを可能にする。
【００２３】
データを符号化および解読する、より良い方法を提供することはこの発明の具体化の一層の目的であり、それらは暗号文中の統計の完全な秘密（Statistical Perfect Secrecy）を保証する。
【００２４】
暗号化と解読のより良い方法を提供することはこの発明の具体化の一層の目的である。
【００２５】
steganographyのより良い方法を提供することはこの発明の具体化の一層の目的である。
【００２６】
安全な伝達のより良い方法を提供することはこの発明の具体化の一層の目的である。
【００２７】
安全なデータの保管や回復のより良い方法を提供することはこの発明の具体化の一層の目的である。
【００２８】
従って、１つのやり方としては、この発明は平文から暗号文を作成する方法に関連しており、次のステップから構成される。: (a) 平文の文字を受け取る。; (b) ルートと平文のある文字に対応するリーフをたどってOommen-Rueda ツリーをトラバースする。それぞれのトラバースされたブランチのアサイメントバリューを記録する。; (c) 平文の次の文字を受け取る。そして平文が処理されるまでステップ(b)および(c)を繰り返す。
【００２９】
他のやり方では、この発明は平文から暗号文を作成する方法と関連しており、次のステップから成る。: (a) Oommen-Rueda ツリーを構築する。; (b) 平文の文字を受け取る。; (c) ルートと平文のある文字に対応するリーフをたどってOommen-Ruedaツリーをトラバースする。それぞれのトラバースされたブランチのアサイメントバリューを記録する。; (d)平文の次の文字を受け取る。；そして(e) 平文が処理されるまでまでステップ(c)および(d)を繰り返す。
【００３０】
他のやり方では、この発明は平文から暗号文を作成する方法と関連しており、次のステップから成る。: (a) Oommen-Rueda ツリーを受け取る; (b) 平文の文字を受け取る; (c) ルートと平文のある文字に対応するリーフをたどってOommen-Ruedaツリーをトラバースする。それぞれのトラバースされたブランチのアサイメントバリューを記録する。(d) 平文の次の文字を受け取る。； そして(e) 平文が処理されるまでまでステップ(c) および(d) を繰り返す。
【００３１】
他のやり方では、現在の発明は平文から暗号文を作成する方法と関連しており、次のステップから成る。: (a) Oommen-Ruedaツリーを作成する。Oommen-Rueda ツリーは複数のリーフを含んでおり、そのリーフは平文のアルファベットと関連している、つまり、平文のアルファベットの一字一字が少なくとも１つのリーフと関連している。Oommen-Rueda ツリーの内部のノードはそれぞれその後に続くものによって少なくとも一本のブランチがある。それとともにOommen-Ruedaツリーのブランチには、アサイメントバリューがあり、そのアサイメントバリューは暗号文の中のアルファベットの一つと関連している。Oommen-Rueda ツリーのノードはそれぞれ頻度のウエイト（frequency weight）に関係する数に関連している。(b) 平文の最初の文字を受け取る。; (c) ルートと平文のある文字に対応するリーフをたどってOommen-Ruedaツリーをトラバースする。それぞれのトラバースされたブランチのアサイメントバリューを記録する。; (d) 平文の次のシンボルを受け取る; そして(e) 平文が処理されるまでまでステップ(c) および(d) を繰り返す。
【００３２】
他のやり方では、現在の発明は平文から暗号文を作成する方法と関連しており、次のステップから成る。: (a) Oommen-Ruedaツリーを受け取る。Oommen-Ruedaツリーは複数のリーフを含んでおり、そのリーフは平文のアルファベットと関連している、つまり、平文のアルファベットの一字一字が少なくとも１つのリーフと関連している。Oommen-Rueda ツリーの内部のノードはそれぞれその後に続くものによって少なくとも一本のブランチがある。それとともにOommen-Ruedaツリーのブランチには、アサイメントバリューがあり、そのアサイメントバリューは暗号文の中のアルファベットの一つと関連している。Oommen-Ruedaツリーのノードは、後に続くそれぞれ各ノードとリーフの頻度のウエイト（frequency weight）に関係する数に関連している。; (b) 平文の最初の文字を受け取る。; (c) ルートと平文のある文字に対応するリーフをたどってOommen-Rueda ツリーをトラバースする。それぞれのトラバースされたブランチのアサイメントバリューを記録する。; (d) 平文の次のシンボルを受け取る; そして(e) 平文が処理されるまでまでステップ(c) および(d) を繰り返す。
【００３３】
他のやり方では, 現在の発明は暗号文を解読する方法に関係があり、次のステップから成る。: (a) 暗号文の最初の文字を受け取る。; (b) エンコーダーによって最初に利用され、ルートから従属するブランチにアサイメントバリューを与えるためにエンコーダーによって利用されたのと同じブランチアサイメントルールを使ったOommen-Ruedaツリーに関連した構造を持つOommen-Rueda ツリーを利用する。ルートからリーフにかけてそのようなOommen-Ruedaツリートラバースする（暗号文の最初のシンボルは次にトラバースされるブランチを決める）。; (c) リーフに到達していない場合、現在到達しているノードに従属するブランチにアサイメントバリューを与えるためにエンコーダによって利用されたのと同じブランチアサイメントルールを適用する。そして暗号文の次の文字を受け取り、Oommen-Rueda トリーを現在到達しているノードからリーフにかけてトラバースし続ける（暗号文の現在のシンボルは次にトラバースされるブランチを決める）。; (d) リーフにたどり着いたら, リーフのラベルに関連した平文の文字を記録し、次のプロセスはルートから始まる。; (e) 暗号文のシンボルがすべて処理されるまで、ステップ(c)および(d)を繰り返す。
【００３４】
他のやり方では, この発明は暗号文を解読する方法に関係があり、次のステップから成る。: (a) Oommen-Rueda ツリーを作成する。；(b) 暗号文の最初の文字を受け取る。; (c) エンコーダによって最初に利用され、ルートから従属するブランチにアサイメントバリューを与えるためにエンコーダによって利用されたのと同じブランチアサイメントルールを使ったOommen-Rueda ツリーに関連した構造を持つOommen-Rueda ツリーを利用する。ルートからリーフにかけてそのようなOommen-Rueda ツリートラバースする（暗号文の最初のシンボルは次にトラバースされるブランチを決める）。; (d) リーフに到達していない場合、現在到達しているノードに従属するブランチにアサイメントバリューを与えるためにエンコーダによって利用されたのと同じブランチアサイメントルールを適用する。そして暗号文の次の文字を受け取り、Oommen-Rueda ツリーを現在到達しているノードからリーフにかけてトラバースし続ける（暗号文の現在のシンボルは次にトラバースされるブランチを決める）。; (e) リーフにたどり着いたら, リーフのレベルに関連した平文の文字を記録し、次のプロセスはルートから始まる。; 暗号文のシンボルがすべて処理されるまで、ステップ(d) および(e) を繰り返す。
【００３５】
他のやり方では, この発明は暗号文を解読する方法に関係があり、次のステップから成る。: (a) Oommen-Rueda ツリーを受け取る。；(b) 暗号文の最初の文字を受け取る。; (c) エンコーダによって最初に利用され、ルートから従属するブランチにアサイメントバリューを与えるためにエンコーダによって利用されたのと同じブランチアサイメントルールを使ったOommen-Rueda ツリーに関連した構造を持つOommen-Rueda ツリーを利用する。ルートからリーフにかけてそのようなOommen-Rueda ツリートラバースする（暗号文の最初のシンボルは次にトラバースされるブランチを決める）。; (d) リーフに到達していない場合、現在到達しているノードに従属するブランチにアサイメントバリューを与えるためにエンコーダによって利用されたのと同じブランチアサイメントルールを適用する。そして暗号文の次の文字を受け取り、Oommen-Rueda トリーを現在到達しているノードからリーフにかけてトラバースし続ける（暗号文の現在のシンボルは次にトラバースされるブランチを決める）。; (e)リーフにたどり着いたら, リーフのレベルに関連した平文の文字を記録し、次のプロセスはルートから始まる。; 暗号文のシンボルがすべて処理されるまで、ステップ(d) および(e) を繰り返す。
【００３６】
この発明の具体化の利点は、統計の完全な秘密の（Statistical Perfect Secrecy）の特性を持つデータの符号化または、解読方法を提供するということである。
【００３７】
この発明の具体化の更なる利点は、符号化されたメッセージが統計の完全な秘密（Statistical Perfect Secrecy）の特性を持つことを保証することです。
【００３８】
この発明の具体化の更なる利点は、接頭語的（prefix manner）で、入力データストリームの、最適であると同時にロスのない圧縮の提供に対応できる。
【００３９】
この発明の具体化の更なる利点は、接頭語的（prefix manner）で、入力データストリームと同じサイズのまたはそれより大きい出力の提供に対応できる。
【００４０】
この発明の具体化の更なる利点は、それが暗号化と解読のより良い方法を提供するということである。
【００４１】
この発明の実施例の更なる利点は、それがsteganography のより良い方法を提供するということである。
【００４２】
この発明の具体化の更なる利点は、それが安全な伝達のより良い方法を提供するということである。
【００４３】
この発明の具体化の更なる利点は、それが安全なデータ保管および検索のより良い方法を提供するということである。
【発明を実施するための最良の形態】
【００４４】
好ましい具体化の解説
この発明はOommen-Rueda ツリーというデータ構造上で動作する。サイズmの平文のアルファベットとサイズr 暗号文のアルファベットのOommen-Rueda ツリーを下記に定義する。ここでは、希望の出力度数分布をF*, 測定された（推定された）値を
【００４５】
【数３】
2005504348.tif 000005
【００４６】
とする。
【００４７】
Oommen-Rueda ツリー
最適化されたOommen-Rueda ツリーは, 以下のように複数のノード,複数のリーフと、複数のエッジのセットとして再帰的に定義される。:
1. ツリーは、ツリーのルート(ユニークなノードで、親ノードを持っていない)を指すポインターによって参照される。
【００４８】
2. すべてのノードは、その子供(ノードおよびリーフの両方) のウエイトの合計に関連したウエイトを持っている。
【００４９】
3. 典型的なOommen-Rueda ツリーでは、すべてのノードはrエッジ(あるいはブランチ)を持ち、各々のエッジはそのr子ノード（ノードかリーフ）の１つをポイントしている。しかし、どれかのノードがr未満の子ノードを持つ場合、残りの子ノードたちのウエイトをゼロとすることによって、r 子ノードを持っていることとして概念的に見ることができる。
【００５０】
4. すべてのノードは、子供のウエイトがどのようにソートされるか知っているのと同じ要領でその子供の順番を維持する。
【００５１】
5. 各平文アルファベットシンボルはリーフ(リーフとは子供を持たないノードである)と関係している。各リーフノードのウエイトは、関連する平文のシンボルの発生確率(あるいは推定確率)に関係している。
【００５２】
6. ソースのアルファベットシンボルをリーフにマッピングするハッシュファンクションが維持されるので、それにより、入力シンボルが受け取られた時ルートと、その入力シンボルに対応するリーフの間のパスをトレースできることが保証される。代わりのアプローチ方法としては、Oommen-Ruedaプロセスを非効率的にするが、全ツリーをサーチすることである。
【００５３】
7. 入力シンボルの確率が既知である場合、Oommen-Ruedaツリーは静的に（statically）維持される。そうでなければ、それは上記のプロパティーを維持するために再度ツリーのノードの順序を変えることにより、入力確率の現在の推定によって適応し（adaptively）維持される。
【００５４】
Oommen-Rueda ツリーの特定の実例化は、Huffman ツリーとFano ツリーで、これらのツリーにおいては全てのレベルのノードの順序は兄弟のようなプロパティーを持つ。( Hankerson et al. (Introduction to Information Theory and Data Compression, CRC Press, (1998)) 参照)。
【００５５】
ここに参照するOommen-Rueda ツリーは、上記に定義された最適化されていないOommen-Ruedaツリー（重要な貢献をしない、またはほかのノード、リーフ、エッジと組み合わせることにより重要性が最小化されたノード、リーフ、エッジを使ってデザインでき、より少ない数のノード、リーフおよびエッジを持つ結果となる）のバージョンを含むことを理解しておきたい。
【００５６】
さらに、兄弟特性(sibling property) が左から右の順に維持されない場合、それに対応するアサイメントは左から右の順にはならないことを理解しなければならない。
【００５７】
さらにまた、”平文”という用語はあらゆる種類の制限されないシンボルやデータ（オーディオデータのプロセス中に利用されたデータ、スピーチ、音楽、静止画像、ビデオイメージ、電子メール、インターネットコミュニケーションなど）を包含することを理解しなければならない。
【００５８】
最後に、ここに記述した符号化および解読するプロセスを持ったOommen-Rueda ツリーのコンビネーションは、出力が圧縮されたり、同じサイズだったり、拡張されたりするDistribution Optimizing Data Encoding 問題の解決策を提供することが理解されるだろう。
【００５９】
Oommen-Rueda ツリーを利用した符号化のプロセス
Oommen-Ruedaツリーと関連する符号化のプロセスは、ルートと現在の平文のシンボルに対応するリーフの間のトラバース(Oommen-Rueda ツリーのために維持されたハッシュファンクションに従って)、そしてブランチアサインメントルールに従って決定されるトラバースをしたエッジのブランチアサイメントを記録することを伴う。現在プロセスされている平文のシンボルの実際の符号化は、平文の入力シンボルを、ルートから平文のシンボルに関連したリーフへのパスのエッジのラベル(ブランチアサイメントルールで決定した)に伴うストリングに変換することによって行われる。
【００６０】
符号化プロセスにおけるOommen-Ruedaトリーのトラバース(ハッシュファンクションによって指図されたように) は、ルートからリーフへの方法か、リーフからルートへの方法で（後者のケースでは出力のストリームが特定の平文に変えられる）達成することができる。
【００６１】
ブランチアサイメントルール
1. このルールは、ツリーのエッジのラベルのアサイメントを決定する。
【００６２】
このラベルは、出力のアルファベットシンボルに関連している。
【００６３】
2. アサイメントは、決定的に（deterministically）あるいは無作為に(randomly)決められた定数を含むか、配分が現在の測定(あるいは評価)
【００６４】
【数４】
2005504348.tif 000006
【００６５】
に依存しないランダムな変数を引き出すことによってか、
または少なくとも一つの現在の測定(あるいは評価)
【００６６】
【数５】
2005504348.tif 000007
【００６７】
に依存したランダムな変数をひきだすことによってかのいずれかで選ばれる。
【００６８】
3. アサイメントは前もって定められたF*の値に収束するように設定することができる。加えて、ブランチアサイメントルールはプロセスが確率の配分に収束すると同時に出力シンボルの独立を維持すように設計することができる。これはMarkovian Historyの利用により達成することができる。例えば、出力のアルファベットが２進法の場合、
【００６９】
【数６】
2005504348.tif 000008
【００７０】
と
【００７１】
【数７】
2005504348.tif 000009
【００７２】
を使って、それぞれ
【００７３】
【数８】
2005504348.tif 000010
【００７４】
と
【００７５】
【数９】
2005504348.tif 000011
【００７６】
に収束させる。
【００７７】
ツリー再構築のための規則
1. Oommen-Rueda ツリーが適応して（adaptively）更新される場合、各平文のシンボルがプロセスされた後、Oommen-Rueda ツリーの更新が終わる。例えば、Huffman ツリーの場合には、更新はKnuthによって記述されたテクニックの利用により達成される。(Dynamic Huffman Coding, Journal of Algorithms, 6:163-180, (1985)),またはVitter (Design and Analysis of Dynamic Huffman Codes, Journal of the ACM, 34(4):825-845, (1987)), では、ツリーは各レベルにおいて兄弟の特性（sibling property）を維持するように更新される。
【００７８】
2. Oommen-Ruedaツリーの他の例示化については、その例示化を特徴づけるあらゆるOommen-Rueda ツリーの徹底的なサーチを使用してのツリー再構築や、特定の例示化のプロパティーに基づいて増加するように変えることによって、ツリー再構築のための規則が影響されることがあることを理解しておきたい。
【００７９】
Oommen-Rueda ツリーを利用した解読のプロセス
解読のプロセスは、デコーダーがOommen-Rueda ツリー(そのツリーはあらかじめ指定された平文のシンボルをコード化するため、エンコーダによって利用されたOommen-Rueda ツリーと同一である) を構築するか、与えられると仮定する。実際の解読プロセスは次のステップを伴う。
【００８０】
1. ルートからリーフまでのOommen-Rueda ツリーのデコーダーのコピーのトラバース。トラバースはエンコーダーによって利用されたブランチアサイメントルールおよび暗号文シンボルによって決定される。
【００８１】
2. リーフのラベルは解読されたシンボルとして記録される。
【００８２】
3. Oommen-Rueda ツリーが適応して（adaptively）更新された場合、現在の符号化されたストリングと関連したソースシンボルが考慮された後、上記のツリー再構築の規則により、デコーダのOommen-Rueda ツリーの更新は終わる。これは、各平文シンボルの解読後、エンコーダおよびデコーダの両方が同一のOommen-Rueda ツリーを維持することを保証する。
【００８３】
エンコーダがブランチアサイメントルールを伴うプロセスを利用した場合、デコーダも同じブランチアサイメントルールを利用しなければならないことを理解しておかなければならない。更に、エンコーダがブランチアサイメントルールを伴わないプロセスを利用した場合、デコーダのプロセスもまたブランチアサイメントルールを伴ってはならない。
【００８４】
エンコーダがツリー再構築のための規則を伴うプロセスを利用した場合、デコーダもツリー再構築のための規則を利用しなければならない。更に、エンコーダがツリー再構築のための規則を伴わないプロセスを利用した場合、デコーダのプロセスもまたツリー再構築のための規則を伴ってはならない。
【００８５】
この発明の追加の例示化
Oommen-Rueda ツリーはユーザーの必要性に柔軟に対応でき、あらゆる状況の中で使用されるであろう。
【００８６】
平文の入力シンボルの発生確率が既にわかっている場合、ツリー(そして結果的に、関連したプロセス) はStatic である。逆に、入力シンボルの発生確率が分からない場合、ツリー(そして結果的に、関連したプロセス) はAdaptive である。
【００８７】
上に示されるように、この発明はまた、Oommen-Ruedaツリーのエッジのラベルにブランチアサイメントルールを使用する。ツリーを操作するプロセスは、ブランチアサイメントルールがDeterministic（決定論的）かRandomized（無作為的）かによって、Deterministic（決定論的）、あるいはRandomized（無作為的）と呼ばれる。その特定の例示化を、下に詳述する。
【００８８】
発明の様々な実施例は、ブランチアサイメントルールが(D)eterministic（決定論的）か(R)andomized（無作為的）かを最初に述べることによりここに特定される。randomized（無作為化）されたブランチアサイメントルールの場合、ブランチアサイメントに対する無作為化（randomization）の影響は決まった定数((F)ixed Constant)、変数((V)ariable)、またはランダム変数((R)andom variable) との比較による。
【００８９】
プロセスの第2の特定は、ツリーは(S)tatic か（A)daptive な方法どちらで構築されるかである。
【００９０】
具体化の第3の特定は、Oommen-Rueda ツリーの特定の例示化（instantiation）である。(すなわち、一般化されたOommen-Ruedaツリーが使われるか、あるいは、Huffman かFano ツリーのような特定の例示化が使われるか)。
【００９１】
プロセスの第4の特定はそれが符号化のプロセスなのか解読のプロセスなのかである。
【００９２】
最後の特定は、入力と出力のアルファベットのサイズである。
【００９３】
次のセクションでは、暗号文アルファベットのサイズが2である場合の、この発明の特定の実施例について記述する。暗号文アルファベットのサイズがrである時、対応するr-進法の具体化は出力のlog2r ビットを連結し、この2進法の長さlog2r のストリングを出力のr-進法のアルファベットから一つのシンボルで表すことによって得ることができるのは明解である。r が二乗でない場合、r シンボルは確率fract1; r で構成することができる。従って、他の長さlog2r のストリングを無視するのである。これは、この方法では無視された長さlog2r のストリングに確率ゼロを割り当てるということを意味する。
【００９４】
続いての記述は、上記の命名法（nomenclature）を使用した、この発明のいくつかの特定の実施例である。
【００９５】
【表１】
2005504348.tif 000012
【００９６】
この文書の全体にわたって、別段の定めがない限り、DDODE ( Deterministic Distribution Optimizing Data Encoding) は、統計の完全な秘密(Statistical Perfect Secrecy)をもたらす決定論的( Deterministic )な解決法の総括的な名前として使用される。DDODEの特定の例示化はDS H Em,2, D A H Em,2などである。同様に、RDODE ( Randomized Distribution Optimizing Data Encoding)は、統計の完全な秘密(Statistical Perfect Secrecy) をもたらす無作為化( Randomized ) 解決法の総括的な名前として使用される。RDODE の特定の例示化はRFS H Em,2, RV A H Em,2などである。
【００９７】
D S H Em,2 : Static Huffman Coding を使用した決定論的な（Deterministic）具体化
符号化のプロセス: D S H Em,2
このセクションでは、Huffman ツリーの兄弟特性（sibling property）の使用により出力の分配を最適化する方法を提供するプロセスについて(Hankerson et al. (Introduction to Information Theory and Data Compression,CRC Press, (1998)), Sayood (Introduction to Data Compression,Morgan Kaufmann, 2nd. edition, (2000)), Witten et al. (Managing Gigabytes: Compressing and Indexing Documents and Images, Morgan Kaufmann, 2nd. edition, (1999)) 参照), そして、符号化のプロセスの間に符号化のスキームのラベル付けをダイナミックに変更するdeterministicルールについて記述する。
【００９８】
この論文の中では次のような表記を使用する。
【００９９】
【数１０】
2005504348.tif 000013
【０１００】
は、時間‘n’の出力の中の0 の確率の推定値を表わす。f(n) は、時間‘n’ の出力の中の0の実際の確率を参照する。
【０１０１】
【数１１】
2005504348.tif 000014
【０１０２】
の推定値は、出力で出された最後のtシンボルを含むウインドウ（window）を使用する。
【０１０３】
【数１２】
2005504348.tif 000015
【０１０４】
は
【０１０５】
【数１３】
2005504348.tif 000016
【０１０６】
と推定され, ここではc0(t) はウインドウの中の0 の数である。ここで含まれた分析およびインプリメンテーションにおいては、ウインドウをt = n と考えることにより任意に大きくされた。つまり、window は時間‘n’までのすべての出力シークエンスである。ウインドウのサイズ‘t’の影響は、後に議論されることになる。
【０１０７】
プロセスD S H Em,2は正式に下に参照され、そしてFigure3と4の中で図入りで参照される。
【０１０８】
D S H Em,2の図式
プロセスD S H Em,2の概要の図表を、ここに説明する。入力/出力ブロック(ブロック100) で始まる図の中で、(i) ソースシークエンスX = x[1]...x[M]は符号化されるデータである。(ii) r はHuffman ツリーのルートであり、それはstatic Huffman coding アプローチを使って作られた。(Huffman (A Method for the Construction o Minimum Redundancy Codes, Proceedings of IRE, 40(9), pp. 1098-1101, (1952))参照), (iii) h(s) はハッシュファンクションで、どれか１つの平文シンボルs に関連したノードを指すポインターをリターンする。(iv)f*は出力の中の「0」の要求された確率である。
【０１０９】
ブロック110 では, 出力の中の「0」の推定確率,
【０１１０】
【数１４】
2005504348.tif 000017
【０１１１】
は、初期値0にセットされる。同様に、出力の中のゼロのカウンターc0も、初期値0にセットされる。出力の中のビットのカウンターn, は、初期値1にセットされる。同様に、入力から読まれたシンボルのカウンターもまた、初期値1にセットされる。さらに、これらの数字の簡単な他の初期化も可能である。
【０１１２】
その後、ブロック120の中で決定ブロックが呼ばれる。これは、ループ構造のスタートを構成し、1から入力のシンボルの数Mまで実行される。ブロック130の変数qはツリーの中の今現在調べられているノードへのポインターを記憶し, ハッシュファンクションh(x[k]) を呼ぶことによって現在のシンボルx[k] と関連したノードに初期化される。x[k] に関連したコードワードの長さＬは、初期値0 にセットされる。決定ブロック140 は、ループの出発点を構成し、x[k] と関連したノードからツリーのルートr までのパスをトレースする。ブロック150 は、x[k] と関連したコードワードの長さの値を1 増す。というのも、その長さは実際、パスのエッジの数だからである。決定ブロック160 は対応するパスが左のブランチに行くか右のブランチに行くかをテストする。左ならtrue（ブロック170）、右ならfalse（ブロック180) とする。ブロック185では、現在のポインターqがツリーのルートの方に向かってその親に上がる。コネクター190は、決定ブロック140のブランチの“No”の続きである。つまり、qがツリーのルートに到達した時(q = r) である。コネクター200は、ブロック120の決定“No”の続きで, 全ての入力シンボルが読まれたときに起こる。コネクター210はブロック310の続きで、入力からの次のシンボルを処理するために決定ブロック120に入る。
【０１１３】
ブロック220では、ツリーのルートからx[k]と関連するリーフに向かってのパスをプロセスするために、jが現在のパスの長さに初期化される。ブロック230は、パス中の各ノードが処理されたかどうかの決定を伴う。決定ブロック240は、適用するブランチアサイメントの方法を決めるために、出力の中の「0」の推定確率
【０１１４】
【数１５】
2005504348.tif 000018
【０１１５】
とユーザによって要求された「0」の確率f*,とを比較する。“Yes”のブランチはブロック250へ続き, そのパスが、左(true) に行くか右(false) に行くかテストする。ブロック250の“Yes”のブランチはブロック280に行き、そこで「0」が出力へ送られ、従って、対応するカウンターc0は増加される。ブロック280もまた、ブロック260の中で、“No” と決定した後、到達される。そしてそれは
【０１１６】
【数１６】
2005504348.tif 000019
【０１１７】
を意味し、その結果、ブランチアサイメント1-0 が使われる。ブランチアサイメント0-1 が適用され、パスが右へ行くブロック250の“No”のブランチは, ブロック270へ行き、そこで「1」が出力に送られる。ブロック270はまた、0-1ブランチアサイメントが使用され、パスが右へ行くブロック250 の“No”のブランチからも到達される。
【０１１８】
ブロック290では、出力の中の「0」推定確率が、ゼロの現在のカウンターとnの現在の値を使って更新され、出力のビットカウンターnが増加される。ブロック300は、パスのエッジのカウンターjを減少し、決定ブロック230へ行き、そこではx[k]と関連したノードに到達した時“No”と決定する。この場合、ブロック310 に到達し、そこで入力シンボルのカウンターkが増加し、そのプロセスは全ての入力シンボルが処理されたとき、ループを終了させる（“No” に決める）決定ブロック120へ続き、入力/出力ブロック320に到達する。そこには、一連の符号化されたY = y[1] ... y[R] が保管される。ブロック330は、プロセスD S H Em,2を起動した上レベルのプロセスにコントロールを返し、プロセスDS H Em,2は終了する。
【０１１９】
【数１７】
2005504348.tif 000020
【０１２０】
符号化プロセスの理論的解釈
従来のHuffmanの符号化では下から上に向かってハフマンツリーを構築した後、符号化のスキームが生成される。そしてそれは、ソースシークエンスの各シンボルをその対応するコードワードに変換するために使用される。ラベル付けの手順は、各ブランチにコードアルファベットシンボルを与えることにより個々の内部ノードで実行される。異なるラベル付けの手順は、異なるコード化スキーム、つまり出力シンボルの異なる確率を促す。実際mシンボルのソースアルファベットに対し、2m-1の符号化スキームがある。ラベル付けのスキームがどのように出力の異なる確率を生むことができるか確かめること(次の例のように) は容易である。
【０１２１】
Example 1.
S = ｛a,b,c,d}, P = {0.4, 0.3, 0.2, 0.1}, A = {0, 1}, そして符号化スキームφA: S → CA = ｛1, 00, 010, 011} およびφB : S → CB = {0, 10, 110, 111}であるとする。これらは、Figure 1 に表記されたHuffman ツリーに異なるラベル付けの方法を使って作られた。
【０１２２】
F* = {0.5, 0.5} である場合、φA とφB、どちらがより優れた符号化のスキームかを検討する。
【０１２３】
始めに、両方の符号化スキームに対し、シンボルごとのビットの平均のコードワードの長さを計算する。(計算するにはHankerson et al. (Introduction to Information Theory and Data Compression, CRC Press, (1998))) で正確な公式を参照できる) :
【０１２４】
【数１８】
2005504348.tif 000021
【０１２５】
次に, 最適な配分からφA とφB の距離、dA(FA,F*) とdB(FB;F*)、を(15)を使って計算する。ここでは、Θ = 2, 下記のように:
【０１２６】
【数１９】
2005504348.tif 000022
【０１２７】
となる。
【０１２８】
次に、CA とCB はプレフィックス、
【０１２９】
【数２０】
2005504348.tif 000023
【０１３０】
と
【０１３１】
【数２１】
2005504348.tif 000024
【０１３２】
は最小, そしてdB < dAであることを確認する。従って, F* = {0.5, 0.5}の場合、φB はφA より優れている。
【０１３３】
DODC問題を解決するために、ブルートフォース法がHankerson et al.の中で提案された。(Introduction to Information Theory and Data Compression, CRC Press, (1998)), それは、2m-1以上もの異なった符号化スキームをサーチし、最短距離を達成する符号化スキームを選ぶというものである。このブルートフォース法をもってしても常に要求された出力確率0.5を得られるわけではない。次の例においてそれを証明する。
【０１３４】
Example 2.
S = {a, b, c, d} とA = {0, 1} の場合を考えてもらいたい。要求された入力の中の0の確率がf*= 0.5と仮定する。すると、2m-1 = 8可能な符号化スキームが存在し、そのコードワードの長さは{1, 2, 3, 3}である。(異なるラベル付け法を使って獲得された、Figure 1 に表記されたHuffman ツリーから作られたもの)
Θ = 2 とし、(14)で定義されたように、８つの可能な符号化スキームと、それらの入力の中の0の確率、およびそれらの距離はTable 1 に表記されている。
【０１３５】
これらの符号化はどれも最適値f* = 0:5 を伴っていないことを見て頂きたい。実際, 例えば、φ1を使って出した最短距離は0.001385であり、その入力のなかの0の確率は0.47367である。
【０１３６】
【表２】
2005504348.tif 000025
【０１３７】
Example 2で見たように, 全ての可能な符号化スキームを徹底的にサーチした後でさえ、最適化した入力の中の0 の要求された確率を見つけるのは不可能である。DS H Em,2 は、決まったラベル付けスキームを使うのではなく、毎回ビットが出力に送られる際に違うラベル付けスキームを使う。これらのラベル付けスキームは、Huffman ツリーの構造と、それまでに符号化された一連の出力の配分に基づいて選ばれる。
【０１３８】
基本的に、D S H Em,2はHuffman ツリーの兄弟特性（sibling property）を利用して働く。(Gallager (Variations on a Theme by Huffman, IEEE Transactions on Information Theory, 24(6):668-674, (1978)) 参照)。このプロパティーから、左の子供のウエイトが常に右の子供のウエイトと同じか、もしくはより大きくなることが分かる。Huffman ツリーTを考えてもらいたい。0 の数,c0(n), と、既に出力に送られたビットの数nに注意を払うことによって、T のノードが到達されたときいつも、出力の中の0 の確率を
【０１３９】
【数２２】
2005504348.tif 000026
【０１４０】
と推定することができる。D S H Em,2は
【０１４１】
【数２３】
2005504348.tif 000027
【０１４２】
を伴い、それを下記のようにf*と比較する。:
【０１４３】
【数２４】
2005504348.tif 000028
【０１４４】
がf*と同じ、またはより小さい場合、ブランチアサイメント0-1が0を取り、さもなければブランチアサイメント1-0 が1 を取る。これはthe D S H Em,2ルールとして表記される。
【０１４５】
必然的に、これはプロセスが、与えられ決まったアサイメントから生じたハフマンツリーの指数を適応して合わせることにより得られた複合ハフマンツリーを利用することを意味する。上記のようにこの混合は、適応性があり、オーバーヘッド（負荷）をかけない。この混合機能は、明示的なではなく暗示的であり、f(n) が定められた点f*に収束するよう強いることによって達成される。
【０１４６】
D S H Em,2はまた、ポインターqを保持し、それはルートからT中の現在のシンボルが位置するリーフまでのパスをトレースするのに使われる。このシンボルはDS H Em,2 ルールを使って符号化される。このパスのトレースと符号化の部分は、エンコーダとデコーダの一致を維持するためになされる。次の短い例はこの手順を明確にするのに役立つだろう。
【０１４７】
Example 3.
ソースアルファベットS = {a, b, c, d}と、各々の発生確率P = {0.4, 0.3, 0.2, 0.1}及びコードアルファベットA = {0, 1}であるとする。ソースシークエンスX = bacba を符号化するには, D S H Em,2とHuffmanアルゴリズムを使って初めに構築されたHuffman ツリー( Figure 1 参照) を使う。( Huffman (A Method for the Construction of MinimumRedundancy Codes, Proceedings of IRE, 40(9):1098-1101, (1952)) 参照)。
【０１４８】
プロセスD S H Em,2によってなされた符号化はTable 2 に詳しく参照する。
【０１４９】
初めに, c0(0), n, および
【０１５０】
【数２５】
2005504348.tif 000029
【０１５１】
は全て0 にセットされる。最初のブランチアサイメントは0-1 である。X の各々のシンボルに対し、パスが作られる。そして、このパス(‘方向’ の列) の各エレメントに対し、現在のアサイメントを使用して出力が出される。その後, n0, n, および
【０１５２】
【数２６】
2005504348.tif 000030
【０１５３】
が更新される。
【０１５４】
【表３】
2005504348.tif 000031
【０１５５】
Example 3 で、D S H Em,2の力を観察することができる。出力の中の0の確率
【０１５６】
【数２７】
2005504348.tif 000032
【０１５７】
が出力の中にたった９ビット出した後、約f* = 0.5 となる。これは”ラッキーなストローク”であるように見えるが、この後示されるように, 理論上そして実験上, D S H Em,2 はこの動作に比較的急速に辿り着く。
【０１５８】
解読プロセス: D S H Dm,2
解読プロセスD S H Dm,2は、はるかに容易に実行される。出力シークエンスから受け取った各ビットにおいて、
【０１５９】
【数２８】
2005504348.tif 000033
【０１６０】
がf*と比較される。
【０１６１】
【数２９】
2005504348.tif 000034
【０１６２】
がf*より小さい、あるいは等しい場合0 がブランチアサイメント0-1に取られ、そうでなければ1がブランチアサイメント1-0 に取られる。D S H Dm,2はまた、ポインターqを保持し、それはルートからT中の解読されるシンボルが位置するリーフまでのパスをトレースするのに使われる。
【０１６３】
正式の解読手順は、プロセスD S H Dm,2, で、そして図入りのものはFigures 5 および6に参照する。
【０１６４】
D S H Dm,2の概要
プロセスD S H Dm,2 (Figure 5 と6に参照) は、入力/出力ブロック100に始まり、そこで符号化されたシークエンスY = y[1] ... y[R]、Huffman ツリーのルート, r, および入力の中の要求された「0」の確率f*が読まれる。元のソースシークエンスX が正確に復元されるには、Huffman ツリーはプロセスD S H Dm,2に使用されたものと同じものでなくてはならない。
【０１６５】
ブロック110 では、入力の中の「0」の推定確率
【０１６６】
【数３０】
2005504348.tif 000035
【０１６７】
と、入力の中のゼロのカウンターc0 が、初期値0 にセットされる。一連の入力からプロセスされたビットの数n と、出力に送られたシンボルの数k は、初期値1 にセットされる。D S H Dm,2 にあるように、これらの数の他の簡単な初期化もまた可能であるが、元のソースシークエンスX が正確に復元されるには、エンコーダーとデコーダーは同一の初期化を維持しなければならない。このプロセスはまた、ツリーの現在のノードを指すポインターq を初期化し、ツリーのルートr を指す。
【０１６８】
決定ブロック120 は、ループ構造をスタートさせる。そしてそれは、Y からの全てのビットが処理された時終了する(ブランチは“No” とラベル付けされる) 。決定ブロック130 はY の中の「0」の推定確率
【０１６９】
【数３１】
2005504348.tif 000036
【０１７０】
と希望される確率f* を比較し、
【０１７１】
【数３２】
2005504348.tif 000037
【０１７２】
である場合、“Yes”(ブランチアサイメント0-1) のブランチを通って、ブロック140 へと続く。決定ブロック140は、現在のビットが「0」の場合、ブロック170 へ続く。これは、使われたブランチアサイメントが0-1 で、パスが左に行かなくてはならないからである。逆に、現在のビットが「1」の場合、パスは右へ行かなくてはならない。(ブロック160)
ブロック130 の“No” のブランチは(
【０１７３】
【数３３】
2005504348.tif 000038
【０１７４】
の場合)、決定ブロック150 へ続き、現在のビットを「0」と比較する。もしそのビットが「0」であれば、“Yes” のブランチはブロック160 へ行く。そしてそこで、現在のポインターq はその右の子供を指す。もしそのビットが「1」(ブロック150 の“No” とラベル付けされたブランチ) であれば、そのプロセスはブロック170 へと続き、そこでq はその左の子供を指し、Y の中のゼロのカウンターc0 を増加する。
【０１７５】
コネクター180 はブロック160 あるいは170 が終わった後のプロセスの続きである。コネクター190 は、ブロック120 の“No” のブランチの続きであり、Y からのビットが全て処理されたことを意味する。コネクター200 は、ブロック230 の“Yes” のブランチの続きで、現在のパスをプロセスするためにブロック130 へ行く。コネクター210 は、Y のビットを全て処理するループ構造の続きである。
【０１７６】
ブロック220 では、Y の中の「0」推定確率
【０１７７】
【数３４】
2005504348.tif 000039
【０１７８】
が、現在のゼロのカウンターと、プロセスされたビットカウンターを使って更新される。
【０１７９】
次の決定ブロック(ブロック230)は、現在のポインターqが、リーフを指しているかどうかをチェックする。q が復元されようとしているソースシンボル(“No” のブランチ) と関連したリーフを指している場合、プロセスはブロック240 へ続く。そこで対応したソースシンボルx[k] が、復元され、X の中のソースシンボルのカウンターk が増加され、現在のポインターq は、ツリーのルートへ動かされる。
【０１８０】
ブロック250 は、Y からのビットの全てが処理された時(ブロック120の“No” のブランチ) 実行される。この時、元のソースシークエンスXは、完全に復元され、プロセスDS H Dm,2は、ブロック260の中で終了する。そして、それを実行した上のレベルのプロセスにコントロールが戻される。
【０１８１】
【数３５】
2005504348.tif 000040
【０１８２】
Example 4.
発生確率P = {0.4, 0.3, 0.2, 0.1} であるソースアルファベットがS = {a, b, c, d} で、コードアルファベットがA = {0, 1} であるとする。出力シークエンスY = 011010011 はD S H Dm,2とFigure 1 に表記されたHuffman ツリーを使って解読される。
【０１８３】
解読のプロセスはTable 3に詳細する。D S H Dm,2にあるように、c0(n)とf(n) は0にセットされ, デフォルトのブランチアサイメントは0-1にセットされる。Y から読まれた各ビットy[n] に対して、現在のブランチアサイメントとy[n] がトーレースされたパスの方向を決定する。簡単に言うと、子供qが、どこに向かうか（ 左(L) あるいは右（R））を決定する。その後、c0(n) と
【０１８４】
【数３６】
2005504348.tif 000041
【０１８５】
が更新される。リーフに到達したときには毎回、それに関連したソースシンボルが解読された出力として記録される。最後に、元の入力である、Example 3 のソースシークエンス, X = bacbaが、完全に復元されたことに注目していただきたい。
【０１８６】
【表４】
2005504348.tif 000042
【０１８７】
D S H Dm,2の収束の証明
D S H Dm,2の主なプロパティーは、圧縮されたもの、およびそこから構築される暗号化の特質の決定において重大である。DS H Dm,2のプロパティーを引き出すのを助けるために、2 進法の入力アルファベットのプロパティーが最初に引き出され、その後、マルチシンボルの入力アルファベットのケースの結果が帰納的に引き出される。
【０１８８】
２進数アルファベットの場合
このセクションでは入力が２進数のソースアルファベットである特殊な場合のD S H Dm,2の収束を証明する。この場合、Huffmanツリーはノードをたった３つしか持たない。ルートと２つの子ノードである。この場合の符号化のプロセスはDS H Dm,2と参照される。
【０１８９】
ソースアルファベットS = {0, 1}を考えていただきたい。その符号化の手順は下記にプロセスD S H Dm,2の中で詳細される。おそらくSのシンボルであろうシンボルsはルートの左の子ノードと関連を持つ。そして
【０１９０】
【数３７】
2005504348.tif 000043
【０１９１】
はsの補数(つまり、s が1であれば
【０１９２】
【数３８】
2005504348.tif 000044
【０１９３】
は0。あるいはその逆。) であり、右の子供と関連する。
【０１９４】
【数３９】
2005504348.tif 000045
【０１９５】
この場合のHuffman ツリーは、ルートと２つのリーフノード(0 と1)を持つ単純なものである。このツリーには２つの可能なラベル付け法がある。最初の方法は左のブランチに0、そして右のブランチに1とトラベル付けする。(Figure 6(a)) それは符号化スキームφ0 : S → C = {0, 1} を伴う。もう１つのラベル付け法は左のブランチに1、そして右のブランチに0とラベル付けする。(Figure 6(b)) これは符号化スキームφ1 : S → C = {1, 0}を伴う。入力シークエンスの全てを符号化する決まった符号化スキームを使用するのではなく、出力の中の0の推定確率
【０１９６】
【数４０】
2005504348.tif 000046
【０１９７】
に基づいたブランチアサイメント(0-1 か1-0) を選ぶラベルを付け法が強いられる。
【０１９８】
収束の証明に関しては、入力の中の0の確率pが1 - p（入力の中の1の発生確率）と同じかまたはより大きいと仮定され、従って、
【０１９９】
【数４１】
2005504348.tif 000047
【０２００】
である。これは、Sのシンボルがおそらく0であるということを意味する。p < 0.5である場合においては対照によって解決でき、単純である。入力の中の要求された確率f*は、
【０２０１】
【数４２】
2005504348.tif 000048
【０２０２】
である時D S H E2,2によって達成されることは既に示された。結果は下記のTheorem 1 において述べる。このセオリーの正確な証明は付録Bの中で与えられる。
【０２０３】
Theorem 1 (プロセスD S H E2,2の収束).  アルファベットS = {0, 1}と、その確率P = [p,1-p] の静止した、メモリのないソースを考えてもらいたい。この際
【０２０４】
【数４３】
2005504348.tif 000049
【０２０５】
で、コードアルファベットはA = {0, 1}とする。ソースシークエンスX = x[1],..., x[n],...（この時、x[i]∈ S、i = 1,...,n,...とする）は、プロセスDS H E2,2を使って符号化され、出力シークエンスY = y[1],...,y[n],...（この時、y[i] ∈ A, i = 1,...,n,...とする）を引き出す場合、
【０２０６】
【数４４】
2005504348.tif 000050
【０２０７】
この時f*は入力の中の要求された0の確率で、
【０２０８】
【数４５】
2005504348.tif 000051
【０２０９】
そして
【０２１０】
【数４６】
2005504348.tif 000052
【０２１１】
、c0(n)は時間nまでの符号化された0の数である。
【０２１２】
D S H E2,2が統計の完全な安全（Statistical Perfect Secrecy）を保証するという結果は次に述べる。
【０２１３】
Corollary 1 (プロセスD S H E2,2の統計の完全な安全（Statistical Perfect Secrecy）).  プロセスD S H E2,2は統計の完全な安全（Statistical Perfect Secrecy）を保証する。
【０２１４】
Proof. Theorem 1 の結果、出力シークエンスの中の0の確率は漸近的に要求された値f*に収束する。この時、
【０２１５】
【数４７】
2005504348.tif 000053
【０２１６】
で、確率は1とする。特に、この収束はf*が0.5であればいつでも保証される。
【０２１７】
有限数のステップの後、
【０２１８】
【数４８】
2005504348.tif 000054
【０２１９】
の値が約0.5になることは保証されているので、これは、全ての入力Xに対し、長さkの全ての出力シークエンスの確率  Pr[yj+1...yj+k] は、約
【０２２０】
【数４９】
2005504348.tif 000055
【０２２１】
であることを意味する。結果は下記に示す。
【０２２２】
Equation (57) (付録B)はまた、最適化されたロスのない圧縮を保証する。
【０２２３】
D S H E2,2の収束の特性
Theorem 1 は、
【０２２４】
【数５０】
2005504348.tif 000056
【０２２５】
は確率1でf*に収束することを証明する。しかしながら、一時的な挙動の問題1は明確にされない（1  一時の挙動、そのDODEの解決との密接な係わり合い、そして、与えられた暗号化の中でどのように除去されるかは再度後述される）。ここにf(n) が、非常に早く最終的なソリューションに収束することが示される。実際、予期値が考慮された場合、もしf*が0.5にセットされれば、この数は１ステップで0.5に収束することを示すことが出来る。
Theorem 2 (プロセスD S H E2,2の収束率)  f*が0.5 にセットされた場合、D S H E2,2に対し、
【０２２６】
【数５１】
2005504348.tif 000057
【０２２７】
で、１ステップで予期値に収束することを意味する。
【０２２８】
収束の効果(入力の0の確率を推定するために、出力シークエンスの中の最後のtシンボルを含んだウインドウを使った場合) は、今ここで議論される。
【０２２９】
サイズnの全部のシークエンスを使って出力の中の0の確率が推定された時、
【０２３０】
【数５２】
2005504348.tif 000058
【０２３１】
はf*へ収束することは良く知られている。従って、
【０２３２】
【数５３】
2005504348.tif 000059
【０２３３】
明らかに、その収束が保証されるので、そこからkステップ後には出力の中の0の推定確率は次のようになる。:
【０２３４】
【数５４】
2005504348.tif 000060
【０２３５】
最後のkビットを使って出力のなかの0の確率を推定することによって、変更されたD S H E2,2はまだ、同じ決まったポイントf*に収束することは明らかである。これは、
【０２３６】
【数５５】
2005504348.tif 000061
【０２３７】
であるからである。ここで、c0(k) は、出力シークエンスの最後のkビットの中の0の数である。
【０２３８】
言い換えると、これは、学習機能を実行するためにサイズkのウィンドウを使用する代わりに、D S H E2,2でしたように
【０２３９】
【数５６】
2005504348.tif 000062
【０２４０】
を推定するために、出力に符号化されたシークエンス全体を使うことができることを意味する。このスキームはポイントワイズな収束となる。
【０２４１】
マルチシンボルアルファベットの場合
m > 2 のD S H Em,2の収束を、ここで検討する。この場合、出力の中の達成可能な0の最大確率はfmaxで、最小は1 - fmaxである。この時、fmaxはブランチアサイメント0-1を使用したHuffman ツリーの全てのブランチのラベル付けにより得られた符号化のスキームによって提示された入力の中の0の確率である。この結果は、Huffman ツリーのレベルの数における帰納法（induction）によって示される。２進法の場合の収束の結果を使って、D S H Em,2が、ツリーの全てのレベルにおいて、決まったポイントf*に収束することを証明する。DS H Em,2の収束は、Theorem 4 において言及し、証明する。
【０２４２】
Theorem 3 (プロセスD S H Em,2の収束).  アルファベットS = {s1,...,sm}と、その確率P = [p1,...,pm] の静止した、メモリのないソースを考えてもらいたい。この際、コードアルファベットはA = {0, 1}で、Huffmanのアルゴリズムを使って構築された２進法のHuffman ツリーをT とする。ソースシークエンスX = x[1] ... x[M]、プロセスD S H Em,2およびTによって出力シークエンスY = y[1] ... y[R] を引き出すように符号化された場合、
【０２４３】
【数５７】
2005504348.tif 000063
【０２４４】
この時、f*は出力の中の0 の要求された確率
【０２４５】
【数５８】
2005504348.tif 000064
【０２４６】
で、
【０２４７】
【数５９】
2005504348.tif 000065
【０２４８】
、c0(n)は時間nまでの0の数である。
【０２４９】
Corollary 2.  プロセスD S H Em,2は、統計の完全な秘密（Statistical Perfect Secrecy）を保証する。
【０２５０】
実験の結果
この研究で示された、符号化アルゴリズムの性能を評価するために使われるファイルの1つは、カルガリー大学から得られた。それは、Calgary corpus として知られている標準のテストセットとして長年一般的に使用されてきた2（2  ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus/で入手できる）。他のファイルの一式はCanterbury 大学から得られた。このCanterbury corpusとして知られている基準は、Calgary corpus test suiteの代わりとして1997 年に提案された。(Arnold et al. (A Corpus for the Evaluation of Lossless Compression Algorithms, Proceedings of the IEEE Data Compression Conference pages 201-210, Los Alamitos, CA, IEEE Computer Society Press, (1997)) 参照). これらのファイルは異なる圧縮方法の効率をテストし比較するために広く使用される。それらは実行可能なプログラム、スプレッドシート、ウェブページ、画像、ソースコード、ポストスクリプトソースなどを含む広範囲の異なるファイル、およびアプリケーションなどである。
プロセスD S H Em,2 は、ASCII セットをソースアルファベットと見なすことにより実行され、結果は従来のHu(R)man の暗号化によって得られた結果と比較された。後者は、ここで2進法のHuffman ツリーとブランチアサイメント0-1の使用により得られた、固定置換の符号化スキームと見なされてきた。この方法はTraditional Static Huffman (TSH)法と呼ばれる。0の要求された頻度f*は0.5にセットされ、Θは2になるようにセットされる。実験結果はDS H Em;2およびTSHをCalgary corpus とCanterbury corpus のファイルでテストすることにより得られる。それらはTable 4 と5で各々記される。最初の欄はCalgary かCanterbury corpusのオリジナルのファイルの名前である。二番目の欄
【０２５１】
【数６０】
2005504348.tif 000066
【０２５２】
はHuffman ツリーで達成可能な0 の最大確率である。すなわち、TSHで達成した出力の中の0の確率である。
【０２５３】
【数６１】
2005504348.tif 000067
【０２５４】
はD S H Em,2によって出された出力シークエンスの中の0の推定確率である。最後の欄、
【０２５５】
【数６２】
2005504348.tif 000068
【０２５６】
は、(14)を使って計算された距離である。ここで
【０２５７】
【数６３】
2005504348.tif 000069
【０２５８】
はD S H Em,2によって出された圧縮ファイルの中の0の確率である。
【０２５９】
Table 4 と5 の最後の列“平均”は、距離の加重平均である。
【０２６０】
【表５】
2005504348.tif 000070
【０２６１】
Table 4から、D S H Em,2が要求されたのと非常に近い0の確率を達成していることを見て頂きたい。また、最長距離(Θ= 2 で計算された)ｊは約3.0E-08 で、加重平均は7.5E-09 以下である。
【０２６２】
Canterbury corpus のファイルでは、さらに良い結果(Table 5)が得られた。ファイルgrammar.lsp の圧縮の出力においてが最悪のケースであるが、距離は10E-08、加重平均距離は5.5E-10よりさらに短かった。
【０２６３】
【表６】
2005504348.tif 000071
【０２６４】
グラフの分析
D S H Em,2の性能はグラフに描かれている。Calgary corpus のファイルbib においての距離のグラフはFigure 7 に表記する。x-軸は、出力シークエンスの中に出されたビットの数を表し、y-軸は出力の要求された確率と出力シークエンスの中の0 の確率の間の平均距離を表す。
【０２６５】
上に記された平均距離は下記のように計算される。出された各ビットに対し、距離
【０２６６】
【数６４】
2005504348.tif 000072
【０２６７】
は、(14)を使って計算される。この時、出力のなかの要求された0の確率はf* = 0:5 で、
【０２６８】
【数６５】
2005504348.tif 000073
【０２６９】
は0 の数c0(n)を既に出力に送られたビットの数で割ったものとして推定される。平均距離を計算するために、その出力はgiビットの500のグループに分割され、平均距離は
【０２７０】
【数６６】
2005504348.tif 000074
【０２７１】
をグループの中で作られた各ビットに加え、giで割ることにより計算される。
【０２７２】
図から、距離は速く0 の方へ下がり、0 の近くに留まることが分かるだろう。そのような収束は、Calgary corpus およびCanterbury corpusの両方からのすべてのファイルに対して典型である。
【０２７３】
D A H Em,2 : Adaptive Huffman Coding を使用する決定論的な具体化
符号化のプロセス
Huffmanのadaptiveコード化スキームの使用によりDODCを解決する方法は単純である。もう一度言うが、このデザインはその時に使用されるラベル付け方法を決めるために、すべての時点でツリーの兄弟特性（sibling property） を利用する。この他に、プロセスは、ソースシンボルの確率が推定される学習段階を組み入れなければならない。これはとても標準な方法で、文献に詳しく記されている。(Hankerson et al. (Introduction to Information Theory and Data Compression, CRC Press, (1998)), Gallager (Variations on a Theme by Hu(R)man, IEEE Transactions on Information Theory, 24(6):668-674, (1978)), Knuth (Dynamic Huffman Coding, Journal of Algorithms, 6:163-180, (1985)), and Vitter (Design and Analysis of Dynamic Hu(R)man Codes, Journal of the ACM, 34(4):825-845, (1987)) 参照)。
【０２７４】
適応性のある（adaptive）やり方でHu(R)man の暗号化を使って、アルゴリズムを最適化する配分のための符号化の手順は、下記のプロセスD AH Em,2詳述され、Figures 9 および10 で図解される。
【０２７５】
D A H Em,2の概要
プロセスD A H Em,2の概要の図表をここで説明する。ブロック100で、符号化されるソースシークエンスX = x[1] ... x[M]および出力の中の「0」の要求された確率f*が入力から読まれる。ブロック110ではHuffman(A Method for the Construction o Minimum Redundancy Codes, Proceedings of IRE, 40(9), pp. 1098-1101, (1952)) で示された方法に従って、ソースシンボルに合った確率の配分を想定することによって、Huff-manツリーが構築される。この方法は、ルートr へのポインターとしてのHuffman ツリーと、後に入力からプロセス中のシンボルに関連したノードを見つけるために使われるハッシュ機能h(.)をリターンする。
【０２７６】
ブロック120では, 出力の「0」推定確率
【０２７７】
【数６７】
2005504348.tif 000075
【０２７８】
と、出力の中のゼロのカウンターc0が0にセットされる。出力に送られたビットの数nに対応する全てのカウンターと、入力から処理されたシンボルの数k に対応するものは1にセットされる。DS H Em,2にあるように、これらの数の異なる単純な初期化もまた、可能であるが、元のソースシークエンスX が正確に復元されるにはエンコーダーとデコーダーが同一の初期化を維持しなければならない。
【０２７９】
決定ブロック130は、入力からのMシンボルを処理するループ構造のスタートを構成する。“Yes” のブランチはブロック140 へ続き、そこでハッシュ機能h(.)を実行することによって、現在のポインターqが、処理されている現在のシンボルx[k] に関連するノードを指すようにする。ルートからx[k]と関連するノードまでのパスの長さＬは0 にセットされ、後にHuffmanツリーの更新に使われるテンポラリーポインターq1 はx[k]と関連したノードを保管するq にセットされる。
【０２８０】
決定ブロック150はパスの全てのエッジを処理するループ構造のスタートを構成する。現在のポインターqがルートでない場合、プロセスはr(“Yes” のブランチ) に向かってパスをトレースすることにより続き、ブロック160 へ行く。そこで、パスの長さＬを増加させる。プロセスの次のブロックは決定ブロック170で、ここでは、パスが左の子供から来るのか（パスがブロック180でtrue にセットされる“Yes”のブランチ）、右の子供から来るのか（パスがブロック190 でfalse にセットされる）をチェックする。そして現在のポインターq はその親にセットされる(ブロック195)。ブロック150の“No”のブランチは、ツリーのルートが到達されたことを示し、ブランチアサイメントのプロセスがブロック230で始まる（コネクター200 を通って到達した）。それは出力に送られたビットカウンターjをパスの長さＬにセットする。
【０２８１】
コネクター210は、決定ブロック130の“No”のブランチの続きで、入力からの全てのシンボルが処理されたことを示す。コネクター220はループ構造の続きで、全ての入力シンボルを処理する。
【０２８２】
決定ブロック240は、現在のパスの全てのエッジを処理するループ構造のスタートを構成する。j > 0 (“Yes” のブランチ)である場合、プロセスは現在のエッジのラベル付けをすることによって続く(ブロック250)。出力の「0」の推定確率
【０２８３】
【数６８】
2005504348.tif 000076
【０２８４】
が、要求された確率f*と同じまたは小さい場合、ブランチアサイメント0-1 が使われる。従って、パスが左に行く時、(true またはブロック260“Yes” のブランチ), 「0」が出力に送られ、ゼロのカウンターが増加される(ブロック290)。逆に、パスが右に行く場合、(false またはブロック260 の“No” のブランチ), 「1」が出力に送られる(ブロック280)。ブロック250の“No”のブランチ
【０２８５】
【数６９】
2005504348.tif 000077
【０２８６】
はブランチアサイメント1-0が使われることを示し、決定ブロック270へ続き、そこで“Yes” のブランチはブロック280 へ続き、(「1」が出力に送られる)、そして、“No” のブランチはブロック290 へ続く(「0」が出力に送られ、ゼロのカウンターc0 が増加される)。
【０２８７】
ブロック300では、出力の「0」の推定確率
【０２８８】
【数７０】
2005504348.tif 000078
【０２８９】
が、現在のゼロのカウンターと現在のビットカウンターを使って更新される。パスの中のエッジのカウンターjは、減らされる(ブロック310)。これは今、パスがルートからq1までトレースされるからである。
【０２９０】
パスの中のエッジが全て処理された時(ブロック240 の“No”のブランチ)、インプットから処理されたシンボルのカウンター、k、が減らされ(ブロック320)、HuffmanツリーがKnuth (Dynamic Huffman Coding, Journal of Algorithms, Vol. 6, pp. 163-180, (1985)), あるいはVitter (Design and Analysis of Dynamic Huffman Codes, Journal of the ACM, 34(4):825-845, (1987)), で書かれたような手順を実行することによって、更新される。そして更新されたハッシュファンクションh(.)と、もし変わっていれば、ツリーの新しいルートをリターンする。
【０２９１】
入力からのシンボル全てが処理された時(ブロック130の“No”のブランチ) 符号化されたシークエンスY が保管され、(入力/出力ブロック340)プロセスD AH Em,2は終了し、コントロールはこれを実行した上のレベルのプロセスに返される。(ブロック350)
【０２９２】
【数７１】
2005504348.tif 000079
【０２９３】
解読プロセス
adaptive Huffman コード化の解読プロセスもまた、単純なものである。それは、符号化されたシークエンスY と、Huffman ツリーを初期化するためのルールとそれに伴うパラメーターのみを必要とする。この手順はプロセスD A H Dm,2に詳細され、Figure 11と12に図解される。
【０２９４】
static Huffman codingと違い、デコーダーは符号化されたシークエンスに余分な情報を保管しなくていいことを見て頂きたい。それは先に確立したルールに基づいて、ゼロからスタートする。
【０２９５】
D A H Dm,2の概要
Figure11および12に示されるプロセスD A H Dm,2は、入力/出力ブロック100に始まる。そこで、符号化されたシークエンスY = y[1] ... y[R]と、「0」の要求された確率f*が読まれる。ブロック110では、元のソースシークエンスXを復元するために、プロセスDA H Em,2で使われたソースシンボルと同じ最初の確率の配分を使って、Huffman ツリーを構築する手続きが実行される。ここでも、ツリーはルートを指すポインターrに参照される。
【０２９６】
ブロック120では、Yの中の「0」の推定確率
【０２９７】
【数７２】
2005504348.tif 000080
【０２９８】
と、Yの中のゼロのカウンターc0の両方が0にセットされる。処理されたビットのカウンターnと、出力に送られるシンボルのカウンターkは、「1」にセットされ、現在のポインターq はツリーのルートr を指すようにセットされる。D A H Em,2にあるように、これらの数のほかの単純な初期化もまた可能であるが、元のソースシークエンスが正確に復元されるには、エンコーダーとデコーダーは同一の初期化を維持しなければならない。
【０２９９】
決定ブロック130はYからのビット全てを処理するループ構造のスタートを構成する。次のブロックは決定ブロック140で、Yの中の「0」の推定確率
【０３００】
【数７３】
2005504348.tif 000081
【０３０１】
と、要求された確率f*を比較する。
【０３０２】
【数７４】
2005504348.tif 000082
【０３０３】
の場合、ブランチアサイメント0-1が使われ、その結果、ブロック150の中で、Yから「0」が来た時“Yes”のブランチはqを左の子供に動かし(ブロック180)、y[n]が「1」の時は、現在のポインターq は、右の子供へ移行する。(ブロック170)。決定ブロック140の“No”のブランチ
【０３０４】
【数７５】
2005504348.tif 000083
【０３０５】
は、ブランチアサイメント1-0が使われ、決定ブロック160へ続くことを意味する。現在のビットが「0」の場合、現在のポインターはその右の子供にセットされ(ブロック170)、y[n] が「1」の場合、現在のポインターq はその左の子供にセットされ、Yの中のゼロのカウンターc0は増加される(ブロック180)。
【０３０６】
コネクター190を通って続くプロセスは、その後ブロック230へ続き、そこで、Yの中の「0」の推定確率
【０３０７】
【数７６】
2005504348.tif 000084
【０３０８】
が、現在のゼロのカウンターc0と、処理されたビットのカウンターnを使って更新される。プロセスは、現在のポインターqがテストされる決定ブロック240を実行して続く。q がリーフでない場合(すなわち、左の子供がnilでない)、プロセスは次のビット(パスの次のエッジ)と共にコネクター210を通ってブロック140へ行く。リーフであれば、それに対応したソースシンボルx[k]が復元され、ソースシンボルのカウンターkは増加される(ブロック250)。プロセスはブロック260へ続きそこで、エンコーダーとデコーダーが同じツリーを維持するようにDA H Em,2でしたのと同じ手順でツリーを更新する。ブロック270では、現在のポインターqは、ルートrにセットされ、プロセスは次のシンボルを処理するため、コネクター220を通ってブロック130へ続く。
【０３０９】
決定ブロック130の“No”のブランチは、Yのビット全てが処理されたことを示す。そして、（コネクター200 を通って）入力/出力ブロック280へ続き、そこで、元のソースシークエンスX が保管される。プロセスD A H Dm,2ブロック290で終了する。
【０３１０】
【数７７】
2005504348.tif 000085
【０３１１】
収束の証明
D A H E2,2を使用したDODCの解決法は３つのノード（ルートと２つの子ノード）を持つHuffman ツリーを使う。このツリーは兄弟特性（sibling property）を持ち、従って、ブランチアサイメントルールの決定は
【０３１２】
【数７８】
2005504348.tif 000086
【０３１３】
の値と出力の0の要求された確率f*との比較に基づいて行われる。特定の場合の収束の証明を下記のTheorem 4 に示す。
【０３１４】
Theorem 4 (プロセスD A H E2,2 の収束).  アルファベットS = ｛0, 1}と、その確率
P = [p, 1 - p]、ここで
【０３１５】
【数７９】
2005504348.tif 000087
【０３１６】
であるとした、静止した、メモリのないソースを考えてもらいたい。この際、コードアルファベットはA = {0, 1}とする。もしソースシークエンス  X = x[1],...,x[n],...と,ここでx[i] ∈ S (i = 1,...,n,...)が, プロセスD A H E2,2によって符号化され、出力シークエンスY = y[1],...,y[n],... (y[i] ∈ A, i = 1,...,n,...) を出す場合、
【０３１７】
【数８０】
2005504348.tif 000088
【０３１８】
この時f*は出力の中の0の要求された確率
【０３１９】
【数８１】
2005504348.tif 000089
【０３２０】
で、
【０３２１】
【数８２】
2005504348.tif 000090
【０３２２】
、c0(n)は時間nまでの0の数である。
【０３２３】
D A H Em,2で維持されるHuffman ツリーは、その構造が毎回、時間‘n’で変わるが、兄弟の特性（sibling property）を満たす。従って、D A H Em,2の収束はD A HE2,2の収束に習う。収束結果はTheorem 6に示され、付録Bにおいて証明される。ここでは、出力の中の0 の推定確率が[1 - fmax, fmax]の範囲内で様々であるという事実が使用される。D A H Em,2の最終結果は、統計の完全な秘密（Statistical Perfect Secrecy）を持つ、ということである。
【０３２４】
Theorem 5 (プロセスD A H Em,2の収束).  アルファベット  S ={s1,...,sm}と、その確率P = [p1,...,pm], そしてコードアルファベットA = {0, 1}の、静止した、メモリのないソースを考えてもらいたい。
【０３２５】
ソースシークエンス  X = x[1] ... x[M] がプロセスD A H Em,2によって符号化され、出力シークエンスY = y[1] ... y[R] を出す場合、
【０３２６】
【数８３】
2005504348.tif 000091
【０３２７】
ここでf*は出力の中の0 の要求された確率
【０３２８】
【数８４】
2005504348.tif 000092
【０３２９】
で、
【０３３０】
【数８５】
2005504348.tif 000093
【０３３１】
とし、ここでc0(n) は時間‘n’までの符号化された0の数である。
【０３３２】
Corollary 3. プロセスD A H Em,2は統計の完全な秘密（Statistical Perfect Secrecy）を保証する。
【０３３３】
実験の結果
D A H Em,2の性能を証明するためにCalgary corpusのファイルでテストされた。この実験の結果はTable 6 に表示する。ここで出力の中の「0」の要求された確率はf* = 0:5 とする。
【０３３４】
【数８６】
2005504348.tif 000094
【０３３５】
の欄は、Tradition Adaptive Huffman (TAH)スキームを使ったファイルの符号化の後の、出力の中の0の推定確率に対応する。
【０３３６】
【数８７】
2005504348.tif 000095
【０３３７】
の欄は、D A H Em,2の出力の中の0の推定確率に対応する。D AH Em,2は、これらのファイルにおいて非常に良く働いていることを見て頂きたい。何度かちょうど0.5 を達成している。これはまた、テーブルからも分かるように平均のパフォーマンスにおいても当てはまる。
【０３３８】
D A H Em,2はCanterbury corpus のファイルにおいてもテストされた。
【０３３９】
【表７】
2005504348.tif 000096
【０３４０】
この実験結果はTable 7に表記する。ここでも、出力の中の0の最適確率はf* = 0:5 にセットされた。D A H Em,2の能力は、平均距離が9.0E-10 よりも短いという事実に反映される。そしてその, D A H Em,2は、この基準のセットに含まれる全てのファイルに非常に良く実行された。D A H Em,2によって達成された性能はstatic版のD S H Em,2と同じぐらい良い。加えて前者は、符号化と解読のプロセスと進めるために、符号化されたデータに、オーバーヘッド(ソースの統計的な情報) をまったく必要としないという事実に注目したい。
【０３４１】
【表８】
2005504348.tif 000097
【０３４２】
D A H Em,2の特性に関して他の見解を提供するため、Calgary corpusのファイルbibのプロセスから得られた
【０３４３】
【数８８】
2005504348.tif 000098
【０３４４】
の値のグラフ式の表示を盛り込んだ。このファイルに対する距離のプロットはFigure 12 において示される。
【０３４５】
0の推定確率の収束が非常に早く起こるのとnの増加に伴い、距離が約0に維持されるのに注目していただきたい。一般的に、私たちの実験から、DA H Em,2は、static 版のD S H Em,2よりも速く収束する。ここに示される結果は典型的なものである。- 類似した結果はCalgary corpusのほかのファイルやCanterbury corpus のファイルに見ることができる。
【０３４６】
Adaptive Huffman Coding を使った無作為な具体化
このセクションでは、Distribution Optimizing Data Compression problemの解決のための無作為な具体化を記述する。これらのプロセスはラベル付けアサイメントの決定における様々な確率的な（あるいは無作為的な）規則を組み合わせたものである。一般に、様々な具体化は、普通のOommen-Rueda ツリー上で作動するが、ここに特に記述される具体化はHuffman ツリーを使う。また、Huffman ツリーはstatically もしくはadaptively に維持されることが可能だが、繰り返しを避けるため、無作為化された具体化はAdaptive Huffman ツリーによって記述される。
【０３４７】
符号化のプロセス
最初に記述される具体化はRV A H Em,2である。基礎をなすツリー構造はAdaptive Huffmanツリーである。ブランチアサイメントルールは無作為化され、従って、ブランチアサイメントの決定は擬似乱数を生成した後で決定される。前述の命名法により、それはRVA H Em,2として言及される。
【０３４８】
ソースアルファベットS = {s1,...,sm} とコードアルファベットA ={0, 1}を考えてもらいたい。また、符号化しなければならない入力シークエンスX = x[1] ... x[M] と、出力シークエンスY = y[1] ... y[R]の生成を考えてもらいたい。DODCの無作為的な解決法によるXをYに符号化する正式な手順と、Huffman ツリーのadaptive な方法での使用は下記のプロセスRV A H Em,2において詳述する。このプロセスはまた、Figure 14 and 15 において図解される。時間‘n’で使われるブランチアサイメントはジェネレーターRNG[next random number] から得られる現在の擬似乱数に基づき決定される。それは、スキームが実行される際、利用できると想定する。一般に、暗号的に安全であれば、どんな偽似乱数のジェネレーターでも使用することができる。
【０３４９】
RV A H Em,2の概要
プロセスRV A H Em,2はFigure 14 と15 に表記され、ブロック100 に始まる。そこで、入力シークエンスX = x[1] ... x[M]、出力の中の要求された「0」の確率f*、そしてユーザーの決めたシードβが読まれる。平文を正確に復元するためには最初のシードは解読プロセスRVA H Em,2に使われたものと同一のシードでなければならない。その後、HuffmanツリーがHuffman (A Method for the Construction o Minimum Redundancy Codes, Proceedings of IRE, 40(9), pp. 1098-1101, (1952)) で示された手順に従ってブロック110 で構築され、ソースシンボルに適切な最初の確率の配分を推定する。この手順はツリー全体のリファレンスとして働くツリーのルート, r, を指すポインターと、後にs に関連するノードの位置を突き止めるために使われるハッシュファンクションh(s) をリターンする。
【０３５０】
ブロック120 では、擬似乱数のジェネレーター(RNG)が、ユーザーの決めたシードβを使って初期化される。
【０３５１】
次のステップは出力の中の「0」の推定確率
【０３５２】
【数８９】
2005504348.tif 000099
【０３５３】
と、出力の中のゼロのカウンターc0を初期値0にセットする(ブロック130)。このブロックでは、出力に送られるビットのカウンターn と入力から処理されるソースシンボルのカウンターk が初期値1 にセットされる。そうでなければ、次の決定ブロック(ブロック140) は、入力からのソースシンボルの数のイテレーションの出発点を構成する。処理されるシンボルが存在する場合(“Yes”のブランチ)、プロセスはブロック150 へ続き、そこで現在のノードq は、現在のソースシンボルをパラメーターとして実行された後リターンされたハッシュファンクションに対応する値にセットされる。x[k] に関連したノードq1は現在のノードq にセットされ、そのノードからルートまでの距離Ｌは0にセットされる。決定ブロック160は現在のポインターqがツリーのルートに到達していないかを調べる。到達していない場合、プロセスはブロック170へ続き、そこでパスの長さＬが増加される。プロセスの次のブロックは決定ブロック180で、そこでは現在のノードqが、右の子供か、あるいは左の子供かを調べる。前者の場合、パスはtrue にセットされ(ブロック190)、後者の場合、false にセットされる(ブロック200)。それからプロセスはブロック205 へ続き、そこで現在のポインターq は、その親にセットされる。
【０３５４】
ブロック160の“No”のブランチは、現在のノードがルートに到達したことを示し、プロセスはコネクター210を通ってブロック240へ続き、そこで、現在のパスの中のカウンターj は、その初期値をパスの長さＬにセットされる。決定ブロック250は、現在のパスの全てのノードを処理するループ構造のスタート地点を構成する。パスに残っているエッジがある場合(j > 0)、RNG から得たn番目の乱数が出力の中の「0」の推定確率
【０３５５】
【数９０】
2005504348.tif 000100
【０３５６】
と比較される(ブロック260)。
【０３５７】
【数９１】
2005504348.tif 000101
【０３５８】
の場合、決定ブロック270に続き、もしパス[Ｌ] がtrueであれば左の子供へ行き、ブランチアサイメント0-1が使われる。この場合、出力に「0」が送られ、出力の中のゼロのカウンターc0が増加される(ブロック310)。パス[Ｌ] がfalseの場合、プロセスはブロック290へ続き、そこで、出力に「1」が送られる。決定ブロック260の“No”のブランチは決定ブロック280のプロセスへ続き、ブランチアサイメント1-0 が使われる。パス[Ｌ] がtrue の場合、「1」が出力に送られ(ブロック290) そうでなければプロセスはブロック310へ続く。プロセスの次のブロックはブロック320で、そこでは出力の中の「0」の推定確率
【０３５９】
【数９２】
2005504348.tif 000102
【０３６０】
が更新され、出力に送られるビットのカウンターnが増加する。次のブロック(ブロック320)はパスのエッジのカウンターjを減らし、パスの次のエッジへ続く(決定ブロック250)。現在のパスの全てのエッジが処理されたら、プロセスはブロック330へ続き、そこで処理されたソースシンボルのカウンターk が増加される。プロセスの次のブロックはブロック340 で、そこでKnuth (Dynamic Huffman Coding, Journal of Algorithms, Vol. 6, pp. 163-180, (1985)) あるいはVitter (Design and Analysis of Dynamic Hu(R)man Codes, Journal of the ACM, 34(4):825-845, (1987))で示された手続きを実行して、更新されたハッシュファンクションと、もし変わっていたらツリーの新しいルートをリターンし、Huffman ツリーが更新される。プロセスは決定ブロック140へ(コネクター230 を通って)続く。
全てのソースシンボルが処理されたら(決定ブロック140の“No”のブランチ)プロセスは入力/出力ブロック350 へ(コネクター220 を通って)続き、そこで、符号化されたシークエンスY が保管される。その後、プロセスはブロック360 の中で終了する。
【０３６１】
【数９３】
2005504348.tif 000103
【０３６２】
符号化プロセスの論理的基礎
プロセスRV A H Em,2 は、乱数、Huffman ツリー、そして時間‘n’での出力の中の0の推定確率
【０３６３】
【数９４】
2005504348.tif 000104
【０３６４】
に基づく確率的な規則の実行により働く。時間‘n’において、ジェネレーターから得られた次の乱数αが、現在の
【０３６５】
【数９５】
2005504348.tif 000105
【０３６６】
の値と比較される。αが一様に分配された確率変数によって生成されるので、ブランチアサイメント0-1 が確率
【０３６７】
【数９６】
2005504348.tif 000106
【０３６８】
で選ばれる。従って、ブランチアサイメント1-0 は確率
【０３６９】
【数９７】
2005504348.tif 000107
【０３７０】
で選ばれる。ここに
【０３７１】
【数９８】
2005504348.tif 000108
【０３７２】
を参照する。この時、
【０３７３】
【数９９】
2005504348.tif 000109
【０３７４】
はHuffmanツリーのi番目のノードのウエイトで、
【０３７５】
【数１００】
2005504348.tif 000110
【０３７６】
はその右の兄弟のウエイトとする。
【０３７７】
【数１０１】
2005504348.tif 000111
【０３７８】
であるときはいつでも、ブランチアサイメント0-1は出力が確率piで0になること、そして確率1 - piで1になることを意味する。
【０３７９】
【数１０２】
2005504348.tif 000112
【０３８０】
(sibling property のため) であるので、出力の中の0の数は1の数よりも高い確率で増加される傾向にある。この規則はf(n) をf* = 0.5 へ向かわせる。逆に、
【０３８１】
【数１０３】
2005504348.tif 000113
【０３８２】
の場合、ブランチアサイメント1-0 はf(n)をf*= 0.5に向かって下降させる。これはn → ∞につれて、f(n)を漸近的に決まったポイントf*= 0.5へ収束させる。これは、このセクションの後半で、正式に、そして実験によって証明される。
【０３８３】
プロセスRV A H Em,2は出力の要求された0の確率がf*=0.5であるときのみ働くことを知っておいていただきたい。しかし、RV A H Em,2は、
【０３８４】
【数１０４】
2005504348.tif 000114
【０３８５】
であれば、簡単にf*のどんな値においても働くように適応させることができる。これは、平均が希望されたf*である確率変数からの乱数の生成により達成することができる。
【０３８６】
次の例は上記のブランチアサイメントルールを明確にするだろう。
【０３８７】
Example 5.  時間‘n’でブランチアサイメントの決定がなされらければならないと仮定する。また、α = 0.5972... はリターンされた擬似乱数で、
【０３８８】
【数１０５】
2005504348.tif 000115
【０３８９】
と仮定する。これら両方の値がアサイメントの決定に使われる。これらの値と、範囲[0,1],そして各ブランチアサイメントに対応する範囲は、Figure 15の中で表記される。この議論から、
【０３９０】
【数１０６】
2005504348.tif 000116
【０３９１】
であるので、1よりも0のほうが出力に送られる傾向にあり、従って、
【０３９２】
【数１０７】
2005504348.tif 000117
【０３９３】
は0.3からf*に向かって増加することは簡単にわかる。これはRV A H Em,2が、f*漸近的に収束するように働く方法を示す。
【０３９４】
解読のプロセス
解読プロセスRV A H Em,2は、RV A HEm,2に習ったものだが、その逆の方法で働く。解読プロセスD A H Em,2の場合のように、RV A H Em,2は符号化のシークエンスから既に読まれた0 の数の変化を追うことによって働く。これらは各時間の瞬間の0の確率
【０３９５】
【数１０８】
2005504348.tif 000118
【０３９６】
を推定するのに使用される。また、RV A H Em,2とRV A H Dm,2は、符号化されたシークエンスが正確に解読されるのを確実にするために同じシークエンスの擬似乱数を使用する。この情報とHuffman ツリー(これはadaptively に維持される)を使って、確率的な規則は与えられたストリングを解読するためにどのブランチアサイメントが使用されることになるか(0-1 あるいは1-0)決定するために実行される。Huffman の暗号化をadaptively に使用する解読プロセスのための実際の手続きは、プロセスRV AH Dm,2で形式化され、Figure 17 と18 で図解される。
【０３９７】
RV A H Dm,2の概要
Figure 17 と18 に表記されたプロセスRV A H Dm,2を下記に説明する。プロセスは入力/出力ブロック100ではじまり、そこで、符号化されたシークエンスY = y1] ... y[R]、そして出力の中の「0」の要求された確率f*そしてユーザーの決めたシードβが読まれる。平文が正確に復元されるためには、最初のシードはプロセスRVA H Dm,2に使われたシードとまったく同じでなければならない。
【０３９８】
次のブロック(ブロック110) は、ソースシンボルのための同じ最初の確率を使って、プロセスRV A H Em,2と同じ手順の実行により、Huffmanツリーを生成し、ツリーのルートr をリターンする。
【０３９９】
プロセスの次のブロックはブロック120で、それはユーザーの決めたシードβを使って、プロセスRV A H Em,2と同じ擬似乱数ジェネレーター(RNG)を初期化する。ブロック125では、Yの中の「0」の推定確率
【０４００】
【数１０９】
2005504348.tif 000119
【０４０１】
と、Y の中のゼロのカウンターc0が0 にセットされる。Y から処理されたビットのカウンターn と、処理されたソースシンボルのカウンターk は1にセットされる。前に詳細されたプロセスのように、他のこれらの数の単純な初期かもまた可能であるが、元のシークエンスX が正確に復元されるためにはエンコーダーとデコーダーは同一の初期化を維持しなければならない。このブロックでは、現在のノードを指すポインターqがルートrにセットされる。
【０４０２】
プロセスの次のブロックは決定ブロック130で、これは、処理されたビットの数のイテレーションの出発点であり、このブロックの“Yes”のブランチは、まだ、処理されていないビットが存在していることを示し、決定ブロック140へ続き、RNGからの現在の擬似乱数が、Y の中の「0」の推定確率と比較される。
【０４０３】
【数１１０】
2005504348.tif 000120
【０４０４】
である場合、ブランチアサイメント0-1が使われ、プロセスは決定ブロック150へ続き、そこで、現在のビットが「0」かどうかをテストする。この場合、プロセスはブロック180へ続き、そこで現在のポインターq がその左の子供に動き、Y のゼロのカウンターが増加される。逆に、現在のビットが「1」の場合、プロセスはブロック170 へ続き、そこで現在のポインターq がその右の子供に動く。
【０４０５】
ブロック140 の“No”のブランチは、決定ブロック160へ続き、そこで現在のビットをテストする。このビットが「0」の場合プロセスはブロック170へ続き、そうでなければ、ブロック180へ続く。
【０４０６】
プロセスの次のブロックはブロック230 (コネクター190 を通って到達した)で、そこでY の中の「0」の推定確率が再計算される。決定ブロック240は現在のポインターがリーフに到達していないかをテストする。到達していない場合、プロセスはパスの次のエッジに続き、決定ブロック(コネクター210を通って到達した) へ行く。決定ブロック240の“No”のブランチは、リーフに到達し、対応したシンボルx[k]が復元されること（ブロック240）を示す。従って、ソースシンボルのカウンターkが増加される。
【０４０７】
プロセスの次のブロックはブロック250で、そこでHuffmanツリーが、プロセスRV A H Em,2と同じ更新手順を実行して更新される。ブロック260は、現在のポインターqが、ルートrにセットされ、プロセスは決定ブロック130(コネクター220を通って到達した)へ続く。
【０４０８】
Yからのビットが全て処理された(ブロック130の“No”のブランチ)時、プロセスは入力/出力ブロック270 (コネクター200を通って到達した)へ続く。ソースシークエンスX が保管され、プロセスはブロック280で終了する。
【０４０９】
【数１１１】
2005504348.tif 000121
【０４１０】
収束の証明
RV A H Em,2のより一般的なケースを考慮するに先立って、2進法の入力のケースであるRVA H E2,2を最初に議論する。この特定のケースは、適応して（adaptively ）構築された3 つのノード（ルートと２つの子ノード）を持つHuffman ツリーを使用する。このツリーは兄弟特性（sibling property）を持つ。従って、ブランチアサイメントは
【０４１１】
【数１１２】
2005504348.tif 000122
【０４１２】
の値と生成された偽似乱数に基づいて決定される。出力での要求された確率がf*= 0.5である場合を考えていただきたい。この特定なケースに関する収束の証明3は、Theorem 6 において詳細され、付録Bにおいて証明される4。(3  証明のmodus operandus は、少しTheorem 4と違う。それは、自動学習（automata learning）のLRPスキームの証明にやや似ている。( Lakshmivarahan (Learning Algorithms Theory and Applications. Springer-Verlag, New York, (1981)), およびNarendra et al. (Learning Automata. An Introduction, Prentice Hall, (1989)) 参照)。
【０４１３】
【数１１３】
2005504348.tif 000123
【０４１４】
を利用した、数量
【０４１５】
【数１１４】
2005504348.tif 000124
【０４１６】
が最初に計算される。その後、二度目の予期値を計算し、
【０４１７】
【数１１５】
2005504348.tif 000125
【０４１８】
は差分方程式の分析により計算される。このとき、この差分方程式が一次であることが判明する!  4  DODCの解決策の無作為化の問題点は、分析が複雑になるということである。;
【０４１９】
【数１１６】
2005504348.tif 000126
【０４２０】
は確率変数であり、その平均はf*に収束し、平方偏差はゼロに収束する。従って、平均平方収束、そして結果的に、確率の収束が保証される。）
Theorem 6 (プロセスRV A H E2,2の収束). メモリのないソース、そのアルファベットS = {0, 1}およびコードアルファベットA = {0, 1}を考えてもらいたい。もし、ソースシークエンスX = x[1],...,x[n],...:、（この時x[i] ∈ S、i = 1,..., n,... とする）が、プロセスRV A H E2,2を使って符号化され、出力シークエンスY = y[1],...,y[n],... （この時y[i] ∈ A, i = 1,..., n,...）を出す場合、
【０４２１】
【数１１７】
2005504348.tif 000127
【０４２２】
この際、f*= 0:5 は出力の中の0の要求された確率で、
【０４２３】
【数１１８】
2005504348.tif 000128
【０４２４】
ここでc0(n)時間n間での符号化された0の数である。従って、平均平方および確率の観念から、
【０４２５】
【数１１９】
2005504348.tif 000129
【０４２６】
はf*へ収束する。
【０４２７】
RV A H E2,2がRV A H Em,2の中で維持されたHuffman ツリーに一般化される場合、たとえその構造が毎回時間‘n’で変わったとしても、後者は兄弟特性（sibling property）を満たす。前記のように、RVA H Em,2の収束の証明は2進法の入力アルファベットのスキームRV A HE2,2の収束の特性に依存する。収束結果はTheorem 7 の中で述べられ証明される。この論議の重要な点は、出力の中の0の推定確率は範囲[1 - fmax, fmax]の内で多様になるという事実である。
【０４２８】
Theorem 7 (プロセスRV A H Em;2 の収束).  メモリのないソース、そのアルファベットS = ｛s1,...,sm}、およびコードアルファベットA ={0, 1}を考えてもらいたい。もしソースシークエンスがX = x[1],...,x[M],...（この時x[i] ∈ S, i = 1,..., n,... とする）が、プロセスRV A H Em,2を使って符号化され、出力シークエンスY = y[1],..., y[R],...（この時y[i] ∈ A）を出す場合、
【０４２９】
【数１２０】
2005504348.tif 000130
【０４３０】
この際f* = 0.5は出力の中の0の要求された確率で、
【０４３１】
【数１２１】
2005504348.tif 000131
【０４３２】
、ここでc0(n) は時間nまでの符号化された0の数である。従って、平均平方および確率の観念から、
【０４３３】
【数１２２】
2005504348.tif 000132
【０４３４】
はf*へ収束する。
【０４３５】
Corollary 4. プロセスRV A H Em,2は、統計の完全な秘密（Statistical Perfect Secrecy）を保証する。
【０４３６】
【数１２３】
2005504348.tif 000133
【０４３７】
上記の無作為化された具体化RV A H Em,2 は、実行された乱数と
【０４３８】
【数１２４】
2005504348.tif 000134
【０４３９】
を比較することにより開発された。乱数の平均が0.5 で、値f* = 0.5 へ収束ように意図されるので、時間によって多様な
【０４４０】
【数１２５】
2005504348.tif 000135
【０４４１】
に反するものとして、実行された乱数が定められた値0.5と比較されるように、RV A H Em,2 を修正することは容易である。
【０４４２】
実際、これは単に比較を変更し、プロセスRV A H Em,2を修正することによって達成される。:
【０４４３】
【数１２６】
2005504348.tif 000136
【０４４４】
を、以下のように変更する。:
【０４４５】
【数１２７】
2005504348.tif 000137
【０４４６】
ブランチアサイメントルールの依存は
【０４４７】
【数１２８】
2005504348.tif 000138
【０４４８】
に頼らないので、収束の速度は下がる。しかしながら、それが絶えず
【０４４９】
【数１２９】
2005504348.tif 000139
【０４５０】
を更新する必要をなくすので、この修正されたプロセスRF A H Em,2はRV A H Em,2より計算上効率的である。
【０４５１】
RF A H Em,2の収束および統計の完全な秘密の特性は容易に証明される。
【０４５２】
RF A H Dm,2の正式な記述およびそれに対応する特性の証明は、繰り返しを避けるため省略する。
【０４５３】
【数１３０】
2005504348.tif 000140
【０４５４】
お分かりになるように、上記の無作為化された具体化RV A H Em,2は、呼び出された乱数αと
【０４５５】
【数１３１】
2005504348.tif 000141
【０４５６】
(この比較はRF A H Em,2の中で回避された)を比較することにより開発された。
【０４５７】
新しいプロセスRR A H Em,2が設計され、そこでは呼び出された乱数αは、
【０４５８】
【数１３２】
2005504348.tif 000142
【０４５９】
と比較されず、その領域を
【０４６０】
【数１３３】
2005504348.tif 000143
【０４６１】
に依存した２番目の確率変数と比較される。
【０４６２】
[0,1]の中の乱数の平均は0.5ということに注目して頂きたい。f* = 0.5への収束が意図されるので、RRA H Em,2は、決まった点からどれくらい距離があるかに基づいて、
【０４６３】
【数１３４】
2005504348.tif 000144
【０４６４】
が0.5に近づいて行くことを強いることにより開発される。しかし、決定論的（deterministic）なやり方でこれを達成するのではなく、2つの確率変数の実行により行われる。まず最初に、RRA H Em,で見たように、αは[0,1] の中の値をリターンする。次に、α2は間隔
【０４６５】
【数１３５】
2005504348.tif 000145
【０４６６】
の中のランダムな値とする(もしくは
【０４６７】
【数１３６】
2005504348.tif 000146
【０４６８】
。これは、
【０４６９】
【数１３７】
2005504348.tif 000147
【０４７０】
が0.5より大きいかどうかによる)。α2とαとの比較によってブランチアサイメントは無作為に0-1 もしくは1-0 となる。RVA H Em,2,この論理的基礎においては、間隔
【０４７１】
【数１３８】
2005504348.tif 000148
【０４７２】
(あるいは
【０４７３】
【数１３９】
2005504348.tif 000149
【０４７４】
) がより速い収束を保証するために広げられることと、決まった点のまわりの変化が最小限にされること以外は、RV A HEm,2の場合とまったく同じである。これはFigure 19 で明確になる。
【０４７５】
これらの変更は、単に比較を変更しプロセスRV A H Em,2を修正することによって達成される。:
【０４７６】
【数１４０】
2005504348.tif 000150
【０４７７】
を、以下のように変更する。:
【０４７８】
【数１４１】
2005504348.tif 000151
【０４７９】
それが2つの乱数の呼び出しを必要とするので、このプロセスRR A H Em,2がRVA H Em,2ほど計算上効率的ではないことを理解していただきたい。しかしながら、一時的な動作はよくなり、決まった点のまわりの変化はRVA H Em,2のそれよりも少ない。
【０４８０】
RR A H Em,2の収束および統計の完全な秘密（Statistical Perfect Secrecy）の特性は容易に証明される。
【０４８１】
プロセスRR A H Em,2とRR A H Dm,2の詳しい記述、およびそれらに対応した特性の証明は繰り返しを避けるため省略する。しかしながら、これらのプロセスを含む実験の結果は後述する。
【０４８２】
実験の結果
以前のように、プロセスRV A H Em,2, RF A HEm,2とRR A H Em,2、および、それぞれの解読の対照物はCalgary corpus とCanterbury corpus のファイル上で厳格にテストされた。RV A H Em,2の実行で得られた実験の結果は、Table 8 と9 の中でそれぞれ示される。
【０４８３】
【表９】
2005504348.tif 000152
【０４８４】
二列目の
【０４８５】
【数１４２】
2005504348.tif 000153
【０４８６】
は, Traditional Adaptive Hu(R)man scheme (TAH)から得られた出力の中の0の推定確率に対応する。三列目の
【０４８７】
【数１４３】
2005504348.tif 000154
【０４８８】
は、RV A H Em,2の実行により得られた出力の中の0の推定確率を含んでいる。最後の列は、(14) の中でのように計算されたf* = 0:5 と
【０４８９】
【数１４４】
2005504348.tif 000155
【０４９０】
の
【０４９１】
【表１０】
2005504348.tif 000156
【０４９２】
間の距離に対応する。
【０４９３】
全てのファイルにおけるRV A H Em,2のすばらしい正確さを見て頂きたい。RV AH Em,2の性能はD A H Em,2に匹敵するが、平均距離は、Calgary corpus とCanterbury corpus のファイル上で、2.0E-07 未満である。さらにCalgary corpus とCanterbury corpus のファイル上で距離の最大値が1.5E-06 未満であることに注目していただきたい。
【０４９４】
RV A H Em,2のグラフでの分析は、Calgary corpus のファイルbib の処理により得られた
【０４９５】
【数１４５】
2005504348.tif 000157
【０４９６】
の値をグラフにすることにより示される。この距離のプロットはFigure 20 の中で描かれる。
【０４９７】
0の推定確率が非常に速く(D A H Em,2よりわずかに遅いが)0.5に集中するかに注目して欲しい。これは、距離がnの増加に伴い、0の近くに留まるという事実に反映される同様の結果がCalgary corpus の他のファイル、およびCanterbury corpusのファイルに見られ、ここでは省略する。
【０４９８】
DDODEおよびRDODEの解決策を利用した暗号化プロセス
このセクションでは、様々な暗号化の方法を産出するため、DODEの決定論的（deterministic ）および無作為化された（randomized ）具体化をどのように組込むことができるかを説明する。
【０４９９】
前述のように、使用される記法、DDODEは統計の完全な秘密（Statistical Perfect Secrecy）を持つあらゆる決定論的（Deterministic）な符号化の解決策の総括的な名前である。同様に、RDODEは統計の完全な秘密（Statistical Perfect Secrecy）を持つ、すべての無作為化された（Randomized）符号化の解決策の総括的な名前である。
【０５００】
一時的な動作の除去
あらゆるDDODE、またはRDODEのプロセスの一時的な動作を除去するのに、2つの方法がある。これらを下記に説明する。
【０５０１】
最初の方法では、送信者および受信者が、大きな値(一般的に約1000)を持つようにnを初期化し、
【０５０２】
【数１４６】
2005504348.tif 000158
【０５０３】
を0.5にセットする。
【０５０４】
【数１４７】
2005504348.tif 000159
【０５０５】
の最初の値が、最終的な定められた点にあるので、プロセスは、それに近づくという更新規則によって制御される。これで、一時的な動作は除去される。
【０５０６】
二番目の方法では, 入力シークエンスX の初めに、キーに関連する単純なストリングが挿入される。このストリングは、最も単純な場合、キー自体の反復の定数でよい。より良いインプリメンテーションとしては、この接頭のストリングは、キーから生成された前もって決められた複数の多様なストリングでも良い。送信者および受信者がキーを認識しているので、かれらはまた、その接頭に挿入された部分も認識していることに注目して欲しい。このキーに関連した接頭辞をTransientPrefix と呼ぶ。そのTransientPrefix に課される要求は、それがキーに関連していること、送信者および受信者にあらかじめ知られていること、そしてそれがプロセスされた後、システムが定常状態、あるいは一時的な動作にない状態に入るように、適切な長さでなければならないということだけである。一般的に、数千ビットのストリングはこの現象を保証する。
【０５０７】
一時的な動作の除去の問題は下記のように解決される。送信者は、初めにXにTransientPrefixを挿入し、新しいメッセージXTempを生成する。それは、プロセスDDODEあるいはRDODEのいずれかを利用する暗号化で処理される。そのコード化されたもの（ここでX′Tempと呼ぶ）を送信する前に、送信者は、TransientPrefix の暗号化に関係するX′Tempの中の接頭辞情報TransientPrefix′を削除する。これは、その結果生じるストリングX″Tempを引き出すためである。X″Tempは何の一時的な動作もなく、直ちに0.5 に収束する。受信者はこの挿入される情報と、X′Tempを引き出すプロセスを認識しており、X″Tempを引き出すため、X″TempにTransientPrefix′を挿入し、そこから解読が始まる。
【０５０８】
これを達成するための正式な手順は単純で、簡潔に保つため省略する。今後、DDODEまたはRDODEを含む暗号化に言及する場合は常に、一時的な動作が除去されたものとする。
【０５０９】
従来の暗号化と併せたDDODEあるいはRDODEの連続的な使用
DDODEおよびRDODEは両方共、あらゆる既存の暗号化メカニズムと共に、それらを連続的に利用することにより、暗号化システムを増強するために使用することができる。
【０５１０】
2つの暗号化法、DODE?およびDODE+ は、DODEの解決策に基づく。
DODEの解決法はdeterministic (DDODE)もしくはrandomized (RDODE)のどちらかである。
【０５１１】
1. DODE?は、入出力のランダムな特性を維持しないあらゆる暗号化（ここで、ENCNonPreserveと呼ぶ）と共に、符号化のメカニズムとしてDDODEまたはRDODEのプロセスを使用する。キーを指定するメカニズムなしで、統計の完全な秘密を保証する符号化プロセスとして、DDODEおよびRDODEの両方を使用することができるということに注目していただきたい。この出力が続いて暗号化される場合、DDODEとRDODEは、元の平文で見つかった統計情報を抹消し、同時に秘密を提供するので、統計での方法ではシステムを破ることができない。しかしながら、連続した二つの出力はENCNonPreserveの確率的な特性に依存する。DDODEまたはRDODEと組み合わさって作動する暗号化ENCNonPreserve は、どんなパブリックキー暗号体系あるいはプライベートキー暗号体系でも良い。(Stinson (Cryptography : Theory and Practice, CRC Press, (1995)) 参照)
2. DODE+は、入出力のランダムな特性を維持するあらゆる暗号化（ここで、ENCPreserveと呼ぶ）と組み合わさった符号化のメカニズムとしてDDODEまたはRDODEプロセスを使用する。一般に、すべての優れた代用、あるいは交換暗号化がこれを達成する。(このようなENCPreserveの単純なプロセスは付録C の中で記述される。)前述の議論から、キーを指定するメカニズムなしで、統計の完全な秘密（Statistical Perfect Secrecy）を保証する符号化のプロセスとして、DDODE、RDODEの両方を使用することができることは明らかである。この出力がENCPreserveによって続いて暗号化される場合、DDODEとRDODEが元の平文で見つかった統計情報を抹消するので、統計に頼った方法ではシステムを破ることができない。
ENCPreserveが入出力のランダムな特性を維持するので、縦並びの２つの出力が統計の完全な秘密（Statistical Perfect Secrecy）を保証することが予期できるという点に注目して欲しい。したがって、統計に基づいた暗号解読の方法を使用して、DODE+を破ることは不可能であり、破るにはキースペースの全てを徹底的にサーチしなければならない。DODE+はまた、秘密を提供する。
【０５１２】
RDODE* : RDODEを利用した暗号化
このセクションは、暗号化のためにRDODE(DODEのあらゆる無作為化された具体化)をどのように利用することができるか説明する。暗号化は、RDODEにキーを指定するメカニズムを組み入れることにより得られる。
【０５１３】
圧縮(一般的なOommen-Ruedaツリーの場合では、拡張あるいはデータの長さの特定) と暗号化の2つのプロセスが互いに連続的に作動する、DODE?およびDODE+とは違い、RDODE*の場合は、RDODE*を2つの相互に排他的なプロセスへ分けることは不可能である。それらは、分解不可能なやり方で互いに増加する。
【０５１４】
RDODE*はプライベートキーを使う。このキー5は特定の無作為化された解決策であるRDODE によって実行された乱数生成器（random number generator）によって使用される最初のシードであるβを特定するために使用される。（5  キーアルファベットは特別なシンボル(‘*’,‘)’,‘#’のような), や、ブランクスペースなどを含むことができる。高度に発展したプロトタイプでは、キーアルファベットは、{a,...,z}∪{A,...,Z}∪{0,...,9}∪{space,‘.’}から成る)。ここに、キーからシードへのマッピングを記述する。
【０５１５】
正式には、キー、K、は、シンボルのシークエンスk[1] ... k[T] である。この時∀i, k[i] ∈ B = ｛b1,..., bt}とする。キーは、Kの整数への変換によって擬似乱数生成器（pseudo-random generator）に使用される最初のシードを独自に指定する。この変換を定義する多数の方法がある。第一に、明らかに、長さTのすべてのキー、K、は範囲[0,...,tT-1]の中の整数に変換されることができる。更に、キーのシンボルを変更することができるので、そのようなキーから整数へのマッピングを指定する、多数の可能な変換がある。そのような変換の手順を一つ、下記に提案する。
【０５１６】
キー、K = k[1] ... k[T] (ここで、k[i] ∈ B とする) が、シードβに変換される場合を考えてもらいたい。初めに、Kが整数のシークエンスに変換される。この際、Bの各シンボルは、0 とt - 1 の間のユニークな整数とする。このシークエンスはK′= k′[1] ... k′[T] の形式であり、ここで∀i, k′[i] ∈ {0,..., t-1}とする。この変換の後に、シードβ6は以下のように計算される。（6  この変換は、シードを整数として生成することに注目していただきたい。システムが2進法のシードを要求する場合、それは簡単にβの2進法への拡張から得ることができる。）:
【０５１７】
【数１４８】
2005504348.tif 000160
【０５１８】
各変換されたキーk′[1] ... k′[T]に対して、ユニークな整数βが｛0,..., tT-1}の中に存在し、従って
【０５１９】
【数１４９】
2005504348.tif 000161
【０５２０】
である場合、統計の完全な秘密（Statistical Perfect Secrecy）を達成することができる。ここで、Zmaxは擬似乱数生成器（pseudo-random generator）の最大のシードである。送信者と受信者の両方が、元のソースシークエンスを復元するためには、同じ最初のシード￣ を持っていなければならないということに注目していただきたい。
【０５２１】
βを使ってRNGを実行した後に、シードの値βは更新される。これは、出力のn番目のビットを引き出すラベル付けのブランチアサイメントが、βの現在値を使用して生成された現在の偽似乱数の値によって決定されることを意味する。したがって、偽似乱数の同じシークエンスが暗号化と解読のメカニズムによって利用される。
【０５２２】
あらゆる実際のインプリメンテーションでは、シードが取ることのできる最大の数は、使用されているシステムの精度に依存する。β > Zmaxである場合、（ここで、Zmax はシステムがサポートする最大のシードとする）J偽似乱数を生成するために、βを、Jシード（Z1,...,ZJ）に分解することができる。RDODEの例示化の中で利用される実際の偽似乱数は、(ここでは、αとする), 時間nで生成され、それらの１つ１つはシステムのRNGの特定のインスタンシエーションであるJ 乱数の連結により得られる。したがって、暗号化が192 ビットのセキュリティを保証する場合、それは4つの48ビットの偽似乱数(各々はシステムのRNGの特定のインスタンシエーション)の実行を意味する。
【０５２３】
次の小例は、この手順を明確にするであろう。
【０５２４】
Example 6. メッセージが、64のシンボル（10進の数字、ブランクスペース、大文字、小文字、および‘.’）を含むアルファベットBから取り出されたシンボルで構成されるキー、K = “The Moon” を使用して暗号化されると仮定する。KのK′への変換は以下のように行われる。:
・0から9までの数字は、0から9の整数にマップされる。
【０５２５】
・ブランクスペースは10にマップされる。
【０５２６】
・AからZ までの文字は11から36までの整数にマップされる。
【０５２７】
・aからzまでの文字は37から62までの整数にマップされる。そして、
・ピリオド‘.’は63にマップされる。
【０５２８】
従って、K′ =30 44 41 10 23 51 51 50である。648 = 281, 474, 976, 710, 656の可能なシードがあり、それらはセット{0,...,648 - 1}に含まれる。
シードβは、Kから次のように計算される。:
β= (30)640+(44)641+(41)642+(10)643+(23)644+(51)645+(51)646+(50)647= 223, 462, 168, 369, 950.
このようなキーからシードへの変換はJava （登録商標）プログラミング言語(jdk 1.xx) のような48 ビットの精度で働くRNG インプリメンテーションにとって理想的であることに注目していただきたい。そのような場合、64-シンボルキースペースから選ばれた長さ8のキーが、シードスペースで同等のシードを導く。
【０５２９】
私たちは、前述の結果によって、RDODE*のすべての例示化が統計の完全な秘密（Statistical Perfect Secrecy）を保証することに注目することで、このセクションを終えることにする。したがって、統計に基づいた暗号解読の方法を使用して、RDODE*を破ることは不可能であり、それはキースペース全体の徹底的なサーチを必要とする。
【０５３０】
RV A H Em,2とRR A H Em,2を利用した暗号化のテスト
一時的な動作が除去され、シードがキーに依存した暗号化の能力を実証するために、RV A H Em,2とRR A H Em,2は、完全に運用可能な48ビットのプロトタイプ暗号体系に組み入れられた。これら両方共、様々なテストによって厳格にテストされ、それらの結果は下に列記する。キーからシードへ指定するメカニズムは、上記の例において正確に説明されたものである。
Calgary Corpus およびCanterbury 上でのRV A H Em,2のテストの結果は、Table 10 と11 の中にそれぞれ表記される。すべての場合において、計算された距離の値(14) が0 に近いことに注目して欲しい。Calgary Corpus およびCanterbury Corpus 上でのRR A H Em,2の同様の結果が、Table 12 と13 の中にそれぞれ表記される。
【０５３１】
暗号化されたストリームのファンクションとしての様々な距離が、様々なファイルに描かれた。Figure 21は、カーネルとしてプロセスRV A H Em,2を使用して、ファイルbib (Calgary Corpus からの) を暗号化して得た平均距離をグラフに描いたものである。プロセスRR A H Em,2がカーネルとして使用される、同様の図はFigure 22 に見ることができる。グラフは、最初から一時的な動作なしで0に近いターミナル値に到達していることに注目して欲しい。
【０５３２】
【表１１】
2005504348.tif 000162
【０５３３】
【表１２】
2005504348.tif 000163
【０５３４】
【表１３】
2005504348.tif 000164
【０５３５】
出力のMarkovian モデリングおよび独立性の検定
収束の理論的な分析、およびRV A H Em,2のために議論された実験の結果は、単に出力シンボルの発生の確率を検討することにより行われた。出力シンボルの依存の問題は、今、Markovian 分析およびX2仮説検証分析を使用して研究される。このゴールを達成するために、より高いオーダーのMarkov モデルであるRV AH Em,2によって得られた出力シークエンスの確率が分析される。このモデルは、前のkシンボルの発生において、あるシンボルの条件付確率を考慮し、kth-オーダーモデル-と呼ばれる。
【０５３６】
次の条件付き確率を持ったファーストオーダーのモデルを考えてみて欲しい。f0|0(n) とf1|0(n)(この時、後者は1 - f0|0(n)である)、f0|1(n)、そしてf1|1(n) (これは1-f0|1(n) である)。これらの確率はまた、2×2 行列形式（基本的なtransition matrix ）で表現できる。漸近確率が[0.5, 0.5]であるので、この行列
【０５３７】
【数１５０】
2005504348.tif 000165
【０５３８】
が対称でなければならないことを理解するのは容易である。この時、δ= 0.5はMarkovian dependenceがない場合である。δの値は単純な方法で出力シークエンスから評価される。
【０５３９】
出力の中のシンボルの独立性を検定するために、RV A H Em,2は、Calgary corpus およびCanterbury corpus のファイル上でテストされた。出力の中の0の要求された確率はf* = 0.5 である。Rビットのファイル中の0に与えられた0の推定確率は、以下のように得られる。:
【０５４０】
【数１５１】
2005504348.tif 000166
【０５４１】
ここで、c0|0(R)はYの中でのシークエンス‘00’の発生回数で、c0(R)は、Yの中の0の数である。同様に、
【０５４２】
【数１５２】
2005504348.tif 000167
【０５４３】
が計算される。
【０５４４】
Yが確率変数のシークエンスであると仮定して、出力での独立性の検定はカイ二乗仮説検定の使用により行われる。(Snedecor et al. (Statistical Methods, Iowa State University Press, 8th edition, (1989))参照). Calgary corpus およびCanterbury corpusのファイル上でRV A H Em,2を実行することから得られた実験結果は、それぞれTable 14 と15 の中で示す。
【０５４５】
【表１４】
2005504348.tif 000168
【０５４６】
２番目の列は、上に説明されるように計算された
【０５４７】
【数１５３】
2005504348.tif 000169
【０５４８】
と
【０５４９】
【数１５４】
2005504348.tif 000170
【０５５０】
の間の平均を表わす。三番目の列は、
【０５５１】
【数１５５】
2005504348.tif 000171
【０５５２】
のカイ二乗統計の値を含んでいる。ここでai; ajは0か1で、自由度の数は1である。最後の列は、信頼度98%に基づいた試験の決定を表わす。Calgary corpus およびCanterbury corpusのすべてのファイルにおいて、出力確率変数が独立していることに注目していただきたい。これは、平均平方の観念で値0.5に収束することに加え、RV A H Em,2の出力はまた、信頼度98%により統計的に独立していることを意味する。
【０５５３】
さらに、レベル5までのより高いオーダーのMarkovian モデルの同様の結果が得られ、その中でのRV A H Em,2の出力もまた、信頼度98%で統計的に独立しているのが分かる。
【０５５４】
FIPS 140-1 ：  RDODE*のランダム性の統計テスト
前の2つのサブセクションの結果は、統計の完全な秘密（Statistical Perfect Secrecy）(f* = 0.5への収束) のための暗号化およびMarkovianの独立性の能力を実証する。しかしながら、よい暗号体系はもっとも厳重な統計検定にも耐えなければならないことは周知の事実である。そのような一組の検定が、規定FIPS 140-1 によって推奨されている( Menezes et al. (Handbook of Applied Cryptography, CRC Press, (1996)) pp. 181-183 参照)。これらの検定は頻度検定（frequency test）, ポーカー検定（poker test）, 連検定（runs test）, そして最長連の検定（long runs test）を含む。推奨されたように、これらの検定は、長さ20000 ビットの暗号化されたストリングのためのもので、検定合格のために対応する統計が明確に指定された上で実行されている。カーネルとしてRVA H Em,2を使用するCalgary CorpusおよびCanterbury Corpusのファイルを暗号化した後に得られた実験結果は、それぞれTable 16, 17, 18, 19, 20, 21,22, 23, 24,そして25,の中に表記する。この暗号化がすべての検定に合格することに注目して欲しい。カーネルとしてRRA H Em,2を使用する暗号化の同様の結果も、入手可能である。
【０５５５】
【表１５】
2005504348.tif 000172
【０５５６】
【表１６】
2005504348.tif 000173
【０５５７】
【表１７】
2005504348.tif 000174
【０５５８】
【表１８】
2005504348.tif 000175
【０５５９】
【表１９】
2005504348.tif 000176
【０５６０】
【表２０】
2005504348.tif 000177
【０５６１】
【表２１】
2005504348.tif 000178
【０５６２】
【表２２】
2005504348.tif 000179
【０５６３】
【表２３】
2005504348.tif 000180
【０５６４】
【表２４】
2005504348.tif 000181
【０５６５】
キー-入力-出力依存の統計検定
上に記述されたFIPS 140-1 検定とは別に、RV AH Em,2を使用する暗号化は、キーおよび入力に応じて、暗号化された出力がどのように変わるか確かめるために厳格にテストされた。特に、キーが１ビットによって変わる場合の、出力の観察された変化の確率が計算された。これはTable 26 に表記されている。希望されたように、Calgary Corpus のすべてのファイルにおいてその値が約0.5 であることに注目していただきたい。この値はまた、ほとんどすべてのファイル中で0.5 という希望値に近い。これはTable 27 に表記されている。Canterbury Corpus のファイルにおける同様の結果もまた、入手可能である。
【０５６６】
【表２５】
2005504348.tif 000182
【０５６７】
【表２６】
2005504348.tif 000183
【０５６８】
DDODEとRDODEの適用
適用に関しては、DDODEとRDODE(またそれぞれの例示化)の両方は、自分の力で圧縮/符号化として使用することができる。従って、それらはデータ送信、データ記憶装置、そして磁気媒体中のデータの記録において利用できる。しかしながら、主な適用はそれらの暗号能力から起こるものであり、次のものを含む。:
・インターネットのトラフィック
・E -コマース/ E-バンキング
・電子メール
・ビデオコンファレンス
・安全な有線、または無線のコミュニケーション
・ネットワークセキュリティー  これを明確にするために、ネットワークに保管されたファイルが、この発明で主張されたスキームの1つを使用して保存されると仮定する。この場合、ハッカーがファイアウォールを破ることに成功し、システムに入り込んだとしても、彼はアクセスしたファイルを読むことができないであろう。なぜならそれらはランダムな雑音として効果的に保管されるからである。この利点は非常に貴重である。
【０５６９】
上記以外には、DDODEおよびRDODEのsteganographyの中での適用が考えられる。
【０５７０】
Steganography は情報を隠す古代の芸術である(B.C440 年にさかのぼる)。(Katzenbeisser et al. (Information Hiding Techniques for Steganography and Digital Watermarking, Artech House, (2000)) 参照) 最も一般的なsteganographicな技術のうちの1 つは、イメージ中に情報を隠すことである。実験的にRV A H Em,2の能力を実証するために、後者は、RDODE*の出力での256-グレイスケールイメージの修正により、steganographicな適用に組み入れられた。RVA H Em,2の統計の完全な秘密（Statistical  Perfect Secrecy）の特性により、steganography でのその使用はユニークである。
【０５７１】
一見明白な議論を実証するために、精巧なスキームを使用するのではなく、イメージキャリアのための、Least Significant Bit (LSB)substitution（最下位ビットの換字）アプローチが使用された。この技術はjk番目のピクセルの最下位ビット(あるいは、より明確に言うと、それを表わすバイト) を出力シークエンスのk 番目のビットと取り替えることから成る。R が出力(
【０５７２】
【数１５６】
2005504348.tif 000184
【０５７３】
で、|I|はキャリアー・イメージのサイズ)のサイズである場合、インデックスのセット{j1,...,jR} は、pseudo-random permutations と呼ばれるものを含み、様々な方法で選ぶことができる。この技術の詳細はKatzenbeisser et al.に見ることができる。(Information Hiding Techniques for Steganography and Digital Watermarking, Artech House, (2000)).
これはsteganographyの、RV A HEm,2の適用のかなり単純なアプローチであるが、その能力を実証するために故意に使用された。後に例においてこの問題を明確にする。実験のプロトタイプでは、“Lena” イメージが、キャリアーファイル(RV A H Em,2の出力を運ぶ) として使用された。オリジナルのLena イメージ、そしてCanterbury corpus のファイルfields.cの暗号化から得られた出力を埋め込んだイメージは、Figure 23 の中で示される。2つのイメージが視覚的に類似しているのとは別に、それぞれのヒストグラムは、とても高い信頼度を備えた類似度の検定に合格する。このような結果は典型的である。
【０５７４】
一旦RV A H Em,2の出力が得られたら、現在入手可能な最も精巧なsteganographyツール( Information Hiding Techniques for Steganography and Digital Watermarking, Artech House, (2000) 参照) により、容易にそれをキャリアーに埋め込むことができるので、上記の単純化されたLSB pseudo-random permutation スキームで埋め込む必要はないことに注目して欲しい。
【０５７５】
ここに記述された例は、この発明の好ましい具体化の一例である。しかしながら、ここに記述されたような発明の範囲を逸脱することなく、様々な変形や修正ができることは芸術に熟練している人にとっては明白であろう。
【参考文献】
【０５７６】
[1 ] R. Arnold and T. Bell. A Corpus for the Evaluation of Lossless Compression Algorithms. Proceedings of the IEEE Data Compression Conference pages 201-210, Los Alamitos, CA, 1997. IEEE Computer Society Press.
[2 ] R. Gallager. Variations on a Theme by Hu(R)man. IEEE Transactions on Information Theory, 24(6):668-674, 1978.
[3 ] D. Hankerson, G. Harris, and P. Johnson Jr. Introduction to Information Theory and Data Compression. CRC Press, 1998.
[4 ] D.A. Huffman. A Method for the Construction of Minimum Redundancy Codes. Proceedings of IRE, 40(9):1098-1101, 1952.
[5 ] D. Knuth. Dynamic Huffman Coding. Journal of Algorithms, 6:163-180, 1985.
[6 ] S. Lakshmivarahan. Learning Algorithms Theory and Applications. Springer-Verlag, New York, 1981.
[7 ] A. Menezes, P. van Oorschot, and S. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.
[8 ] K. Narendra and M. Thathachar. Learning Automata. An Introduction. Prentice Hall, 1989.
[9 ] K. Sayood. Introduction to Data Compression. Morgan Kaufmann, 2nd. edition, 2000.
[10 ] G. Snedecor and W. Cochran. Statitical Methods. Iowa State University Press, 8th edition, 1989.
[11 ] C. E. Shannon. Communication Theory of Secrecy Systems. Bell System Technical Journal, 28:656-715, 1949.
[12 ] W. Stallings. Cryptography & Network Security: Principles & Practice. Prentice Hall, 1998.
[13 ] D. R. Stinson. Cyptography : Theory and Practice. CRC Press, 1995.
[14 ] I. Witten, A. Mo(R)at, and T. Bell. Managing Gigabytes: Compressing and Indexing Documents and Images. Morgan Kaufmann, 2nd.edition, 1999.
[15 ] S. Katzenbeisser and F. Peticolas. Information Hiding Techniques for Steganography and Digital Watermarking. Artech House, 2000.
[16 ] J. Vitter. Design and Analysis of Dynamic Hu(R)man Codes. Journal of the ACM, 34(4):825-845, 1987.
［付録Ａ］
DODEの未解決問題の正式なステートメント
与えられたコードアルファベットA = {a1,...,ar}において、ユーザーが、F*= {f*1 ,..., f*r}によって圧縮されたファイルの中の各aj∈ Aの希望の出力確率(あるいは頻度) を指定すると仮定する。このようなレンダリングはエントロピー最適化（“entropy optimal”）レンダリングと呼ばれる。ユーザはまた同時に最適な、もしくは準最適（suboptimal）なロスのない圧縮を要求する。従って、圧縮ファイルに解凍プロセスが実行される場合、復元されたファイルはオリジナルの無圧縮ファイルとまったく同じでなければならない。
【０５７７】
Hankerson et al. (Introduction to Information Theory and Data Compression, CRC Press, (1998) pp.75-79) で示されたように、DistributionOptimizing Data ompression (DODC) 問題7は、下に詳述される。（7  一般に、圧縮の内容外では、この問題はthe Distribution Optimizing Data Encoding (DODE) 問題と呼ばれる。）:
Problem 1. ソースアルファベットS = {s1,...,sm}とその発生の確率P = [p1,...,pm] を考えてみて欲しい。ここで、入力のシークエンスはX = x[1] ... x[M] で、コードアルファベットA = {a1,...,ar} と、各aj,j = 1,...,rの最適頻度F*= {f*1 ,..., f*r}は、出力のシークエンスで要求される。出力となるシークエンスは, Y = y[1] ... y[R] で、その確率はF = {f1,...,fr}で、これらは符号化スキームφ:S → C = {w1,...,wm}（ここで、Ｌiはwiの長さ）によって、下記のように引き出される。:
(i) C は接頭辞（prefix）である,
(ii) 平均のコードワードの長さφ,
【０５７８】
【数１５７】
2005504348.tif 000185
【０５７９】
は最小で、
(iii) 距離
【０５８０】
【数１５８】
2005504348.tif 000186
【０５８１】
は最短である。ここで、
【０５８２】
【数１５９】
2005504348.tif 000187
【０５８３】
は実数である。
【０５８４】
The Distribution Optimization Data Compression (DODC) 問題はd(F,F*)が任意にゼロに近づく符号化スキームを開発することを含む。
【０５８５】
与えられたソースアルファベット、ソースシンボルの発生確率、および符号化スキームに対し、各fjはX,を符号化せずに下記のように計算することができる。ここで、j = 1,...,r とする。:
【０５８６】
【数１６０】
2005504348.tif 000188
【０５８７】
この時、ajは、wiの中にuji回発生する。（i = 1,...,m、j = 1,...,r）
データ圧縮の必要条件と出力確率の必要条件が矛盾しているかもしれないので、この問題は本質的に難しいことに注目していただきたい。無圧縮ファイルの中で「0」の発生率が「1」の発生率よりも著しく低い場合、ファイルを圧縮し、同時に「0」の割合を増やすデータ圧縮法をデザインすることは重要なことである。
【０５８８】
この問題の重要性は、元々Hankerson et al. (Introduction to Information Theory and Data Compression, CRC Press, (1998)) の中に示されたように次のパラグラフに表される。:
“Problem 1 を解決するために巧妙なアルゴリズムを持つことは、特にr = 2 の場合、d(F,F*) の異なる定義によって出力がさまざまな場合、非常に重要である。また、r = 2 の場合、2 進法の回線（binary channels）が、実際に世界で広範囲に使用されているという事実によって特徴付けられる。
【０５８９】
私たちにはこのようなアルゴリズムがない!  恐らく、これを読んだ誰かがいつか提供してくれるだろう...”
［付録Ｂ］
Theoremの証明
Theorem 1 (プロセスD S HE2,2の収束). アルファベットS = {0, 1}と、その確率P = [p, 1-p] （ここで、
【０５９０】
【数１６１】
2005504348.tif 000189
【０５９１】
とする）そしてコードアルファベットA =｛0,1}の、静止した、メモリのないソースを考えてもらいたい。ソースシークエンスX = x[1],...,x[n],...（ここで、x[i] ∈ S, i = 1,...,n,...とする）が、出力シークエンスY = y[1],...,y[n],...,（y[i] ∈ A, i = 1,...,n,...）を引き出すように、プロセスD S H E2,2を使って符号化された場合、
【０５９２】
【数１６２】
2005504348.tif 000190
【０５９３】
この時、f*は、出力の中の0の要求確率で
【０５９４】
【数１６３】
2005504348.tif 000191
【０５９５】
【数１６４】
2005504348.tif 000192
【０５９６】
、c0(n) は、時間n までの符号化された0 の数とする。
【０５９７】
Proof. プロセスD S H E2;2, によって実行され、S中で最もありそうなシンボルが0であるという事実を利用した次のオペレーションのシークエンスによって, y[n + 1] は以下のように符号化される。:
【０５９８】
【数１６５】
2005504348.tif 000193
【０５９９】
この際、
【０６００】
【数１６６】
2005504348.tif 000194
【０６０１】
は、次のように出力の中の0の数とnの比率として得られた出力の中の0の推定確率である。:
【０６０２】
【数１６７】
2005504348.tif 000195
【０６０３】
記法を容易にするために,
【０６０４】
【数１６８】
2005504348.tif 000196
【０６０５】
を使って、条件付確率
【０６０６】
【数１６９】
2005504348.tif 000197
【０６０７】
を表すことにする。これは、実際、与えられた
【０６０８】
【数１７０】
2005504348.tif 000198
【０６０９】
において、時間n + 1 で、出力の中に得られた0 の確率である。(17) と
【０６１０】
【数１７１】
2005504348.tif 000199
【０６１１】
が与えられているという事実を利用して、
【０６１２】
【数１７２】
2005504348.tif 000200
【０６１３】
は、次のように計算される。:
【０６１４】
【数１７３】
2005504348.tif 000201
【０６１５】
この時c0(n) は、時間n での出力の中の0の数である。
【０６１６】
【数１７４】
2005504348.tif 000202
【０６１７】
であるので、それは
【０６１８】
【数１７５】
2005504348.tif 000203
【０６１９】
であることを意味する。従って、(18)は、次のように書き直すことができる。:
【０６２０】
【数１７６】
2005504348.tif 000204
【０６２１】
(16)を満たさなければならないので、(19) の動作は非常に大きいnの値で分析される。もっと細かく言うと、分析は
【０６２２】
【数１７７】
2005504348.tif 000205
【０６２３】
の収束をn → ∞として考えることで行われる。これは、
【０６２４】
【数１７８】
2005504348.tif 000206
【０６２５】
の3つの相互に排他的で包括的なケースの考慮により遂行される。
【０６２６】
最初のケースは
【０６２７】
【数１７９】
2005504348.tif 000207
【０６２８】
の場合での状況を扱う。n → ∞に連れて、f*が、定まった点であることが分かる。すなわち、制限( n → ∞) が0で増やすことにより、
【０６２９】
【数１８０】
2005504348.tif 000208
【０６３０】
が増加し、従って、
【０６３１】
【数１８１】
2005504348.tif 000209
【０６３２】
は、定まった点、f*に留まるのである。
【０６３３】
次のケースは
【０６３４】
【数１８２】
2005504348.tif 000210
【０６３５】
である場合を扱う。プロセスD S H E2,2は、p の方向に
【０６３６】
【数１８３】
2005504348.tif 000211
【０６３７】
をf*へ急速に収束させて、差分
【０６３８】
【数１８４】
2005504348.tif 000212
【０６３９】
に比例した値で
【０６４０】
【数１８５】
2005504348.tif 000213
【０６４１】
を増加させる。
【０６４２】
【数１８６】
2005504348.tif 000214
【０６４３】
からpに近づくに連れて、
【０６４４】
【数１８７】
2005504348.tif 000215
【０６４５】
であるので、f*の値を越さなければならない。これは、
【０６４６】
【数１８８】
2005504348.tif 000216
【０６４７】
となるような、有限のステップkによって成すことができる。
【０６４８】
逆に、
【０６４９】
【数１８９】
2005504348.tif 000217
【０６５０】
である場合は、
【０６５１】
【数１９０】
2005504348.tif 000218
【０６５２】
は、減少する。この減少は、差分
【０６５３】
【数１９１】
2005504348.tif 000219
【０６５４】
に比例した数による。これは、代わりに、
【０６５５】
【数１９２】
2005504348.tif 000220
【０６５６】
の急速な1-pへの収束を引き起こし、前記のように、f*の値と交差する。
【０６５７】
上記の数は
【０６５８】
【数１９３】
2005504348.tif 000221
【０６５９】
と
【０６６０】
【数１９４】
2005504348.tif 000222
【０６６１】
にそれぞれ比例する一方で、それらは両方ともn + 1に反比例することは後に示される。
【０６６２】
これらの2つの収束現象(すなわち第2と第3のケースのもの)は、nが大きい場合、
【０６６３】
【数１９５】
2005504348.tif 000223
【０６６４】
がf*に非常に接近するまで、
【０６６５】
【数１９６】
2005504348.tif 000224
【０６６６】
をf*により接近させる。そして、最初のケースの結果の定まった点は
【０６６７】
【数１９７】
2005504348.tif 000225
【０６６８】
をf*の近くに留まらせる。
【０６６９】
3つのケースの収束特性の組み合わせが強い収束結果(すなわち確率1の収束) を産み出すことに注目していただきたい。次に3つのケースのための正式な分析を示す。
【０６７０】
(i)
【０６７１】
【数１９８】
2005504348.tif 000226
【０６７２】
与えられた
【０６７３】
【数１９９】
2005504348.tif 000227
【０６７４】
でのy[n+1] = 0 の確率の漸近特性の分析が要求される。この場合、(19.(a)) と(19.(d)), そしてPr[x[n+ 1] = 0] = p であるという事実を利用して、次のように計算される。:
【０６７５】
【数２００】
2005504348.tif 000228
【０６７６】
この場合、
【０６７７】
【数２０１】
2005504348.tif 000229
【０６７８】
であるから、(20) 結果は次のようになる。:
【０６７９】
【数２０２】
2005504348.tif 000230
【０６８０】
これは、n → ∞ に連れて、
【０６８１】
【数２０３】
2005504348.tif 000231
【０６８２】
となることを意味する。ここで、f*は、定まった点である。従って、次の式が導き出される。:
【０６８３】
【数２０４】
2005504348.tif 000232
【０６８４】
公式(22)は、非常に強力である。なぜなら、これは、n → ∞に連れて、一旦
【０６８５】
【数２０５】
2005504348.tif 000233
【０６８６】
がf*に辿り着くと、確率１でf*に留まることを意味するからである。
(ii)
【０６８７】
【数２０６】
2005504348.tif 000234
【０６８８】
この場合、与えられた
【０６８９】
【数２０７】
2005504348.tif 000235
【０６９０】
での、y[n + 1] = 0の条件付確率は(20)を使って、次のように計算される。:
【０６９１】
【数２０８】
2005504348.tif 000236
【０６９２】
【数２０９】
2005504348.tif 000237
【０６９３】
および
【０６９４】
【数２１０】
2005504348.tif 000238
【０６９５】
であるので、仮定により、
【０６９６】
【数２１１】
2005504348.tif 000239
【０６９７】
であることは明らかである。従って、:
【０６９８】
【数２１２】
2005504348.tif 000240
【０６９９】
この時、全ての有限値nにおいて、
【０７００】
【数２１３】
2005504348.tif 000241
【０７０１】
となる。
【０７０２】
【数２１４】
2005504348.tif 000242
【０７０３】
がf*と等しい、もしくはそれ以上であることを保証するために要求されるステップの数k,を分析するに先立って、
【０７０４】
【数２１５】
2005504348.tif 000243
【０７０５】
の閉形式（closed-form）の式が最初に引き出される。(23) が
【０７０６】
【数２１６】
2005504348.tif 000244
【０７０７】
を決定するので、
【０７０８】
【数２１７】
2005504348.tif 000245
【０７０９】
は、次のように計算される。
【０７１０】
【数２１８】
2005504348.tif 000246
【０７１１】
方程式(25)はkの帰納的結論（induction）によって証明される。
【０７１２】
Basis step: 明らかに、(23) であるという事実によって、k = 1の場合、(25)は証明される。
【０７１３】
Inductive hypothesis:  全てのj > 1 において(25) が満たされると仮定する。すなわち、:
【０７１４】
【数２１９】
2005504348.tif 000247
【０７１５】
Inductive step: 全てのj+1 において、(25)であるという証明が要求される。(23)の中のn + j にn を代入する。:
【０７１６】
【数２２０】
2005504348.tif 000248
【０７１７】
inductive hypothesis (26) を使って、(27) を、次のように書き直すことができる。:
【０７１８】
【数２２１】
2005504348.tif 000249
【０７１９】
従って、(25) は全ての
【０７２０】
【数２２２】
2005504348.tif 000250
【０７２１】
において満たされる。
【０７２２】
【数２２３】
2005504348.tif 000251
【０７２３】
となるようにk の条件を分析する上で、次の式が満たされなければならない。:
【０７２４】
【数２２４】
2005504348.tif 000252
【０７２５】
両側から
【０７２６】
【数２２５】
2005504348.tif 000253
【０７２７】
を引く。:
【０７２８】
【数２２６】
2005504348.tif 000254
【０７２９】
両側に
【０７３０】
【数２２７】
2005504348.tif 000255
【０７３１】
掛け、
【０７３２】
【数２２８】
2005504348.tif 000256
【０７３３】
で割る。(31)の結果は次のようになる。:
【０７３４】
【数２２９】
2005504348.tif 000257
【０７３５】
k を解く。:
【０７３６】
【数２３０】
2005504348.tif 000258
【０７３７】
従って、有限数n に対し、kステップの後、(有限数k), (30)は、確率１で満たされる。より正式に言うと、
【０７３８】
【数２３１】
2005504348.tif 000259
【０７３９】
(34) によって意味された収束は非常に強力なものであることに注目して欲しい。それは
【０７４０】
【数２３２】
2005504348.tif 000260
【０７４１】
が、確率1の有限数のステップkにおいてf*以上(あるいは等しい)であることを意味する。加えて、その増加がn + 1に反比例するので、
【０７４２】
【数２３３】
2005504348.tif 000261
【０７４３】
は小さな値のnでf*に向かって急速に収束し、n → ∞に連れて確率1 で、f*の近くに留まる。
【０７４４】
【数２３４】
2005504348.tif 000262
【０７４５】
は遅かれ早かれf*を超過するので、この場合の議論はそれへの注意により終えらる。というのも、
【０７４６】
【数２３５】
2005504348.tif 000263
【０７４７】
である場合、ケース(ii)の仮説に違反するので、
【０７４８】
【数２３６】
2005504348.tif 000264
【０７４９】
を異なった方法で計算しなければならない。実際、この場合、ケース(iii)の仮説は満たされ、次の分析は有効になる。
【０７５０】
最後に、
【０７５１】
【数２３７】
2005504348.tif 000265
【０７５２】
である場合、
【０７５３】
【数２３８】
2005504348.tif 000266
【０７５４】
は、ケースの(i)中でのように、(21)を使って計算され、n →∞に連れて、決まったポイントf*へ収束する。
(iii)
【０７５５】
【数２３９】
2005504348.tif 000267
【０７５６】
この場合、与えられた
【０７５７】
【数２４０】
2005504348.tif 000268
【０７５８】
において、y[n + 1] = 0 の推定確率は(19.(b)) と(19.(c)), およびPr[x[n+1] = 0] = p であるという事実を利用して次のように計算される。:
【０７５９】
【数２４１】
2005504348.tif 000269
【０７６０】
【数２４２】
2005504348.tif 000270
【０７６１】
、そして
【０７６２】
【数２４３】
2005504348.tif 000271
【０７６３】
であるので、これは
【０７６４】
【数２４４】
2005504348.tif 000272
【０７６５】
であり、それは
【０７６６】
【数２４５】
2005504348.tif 000273
【０７６７】
であることを意味する。従って、:
【０７６８】
【数２４６】
2005504348.tif 000274
【０７６９】
この際、有限数n に対し、
【０７７０】
【数２４７】
2005504348.tif 000275
【０７７１】
。従って、n の増加に連れ、
【０７７２】
【数２４８】
2005504348.tif 000276
【０７７３】
は、正数Δの分減少する。
【０７７４】
【数２４９】
2005504348.tif 000277
【０７７５】
の閉形（closed-form）の式はここで引き出される。実際、
【０７７６】
【数２５０】
2005504348.tif 000278
【０７７７】
が(35)の中での様に計算される場合、
【０７７８】
【数２５１】
2005504348.tif 000279
【０７７９】
は、次のように計算できることを帰納法（induction）によって示す。
【０７８０】
【数２５２】
2005504348.tif 000280
【０７８１】
:
【０７８２】
【数２５３】
2005504348.tif 000281
【０７８３】
Basis step:方程式(37)は、(35)が満たされるという事実によって、満たされることは明白である。従ってbasis step となる。
【０７８４】
Inductive hypothesis: j > 1 の場合、(37)であると仮定する。すなわち、:
【０７８５】
【数２５４】
2005504348.tif 000282
【０７８６】
Inductive step: j + 1 である場合、(37) は満たされることを示す。(35)の中でnをn + j に代入する。その結果:
【０７８７】
【数２５５】
2005504348.tif 000283
【０７８８】
inductive hypothesis(38) を使って、(39) を次のように書き換えることができる8。（8  このケースの代数は、ケース(ii)の代数を反映する。しかし、まったく同じではない。p と1 - p の場所は逆で、
【０７８９】
【数２５６】
2005504348.tif 000284
【０７９０】
の記号はいろいろな場所で正から負へ変わる。証明は完全性を保つために含まれている。）
【０７９１】
【数２５７】
2005504348.tif 000285
【０７９２】
従って、(37)は、すべての
【０７９３】
【数２５８】
2005504348.tif 000286
【０７９４】
において満たされる。
【０７９５】
【数２５９】
2005504348.tif 000287
【０７９６】
はf*と交差するまで単調に減少するということに注目していただきたい。
【０７９７】
【数２６０】
2005504348.tif 000288
【０７９８】
を満たすためには次の式が満たされなければならない。:
【０７９９】
【数２６１】
2005504348.tif 000289
【０８００】
【数２６２】
2005504348.tif 000290
【０８０１】
を引いて、不等式を逆にすると、次のようになる。:
【０８０２】
【数２６３】
2005504348.tif 000291
【０８０３】
両側に
【０８０４】
【数２６４】
2005504348.tif 000292
【０８０５】
を掛けて、
【０８０６】
【数２６５】
2005504348.tif 000293
【０８０７】
で割る。(43)の結果は、:
【０８０８】
【数２６６】
2005504348.tif 000294
【０８０９】
前のように、k を解く。:
【０８１０】
【数２６７】
2005504348.tif 000295
【０８１１】
従って、有限数nに対し、k ステップの後(k は有限数), (42) は確率１で満たされる。すなわち、:
【０８１２】
【数２６８】
2005504348.tif 000296
【０８１３】
(34)の場合でのように、方程式(46)は強い収束結果を表わす。
それは
【０８１４】
【数２６９】
2005504348.tif 000297
【０８１５】
からスタートして、
【０８１６】
【数２７０】
2005504348.tif 000298
【０８１７】
は有限数のステップk の中で、確率１でf*未満(あるいは等しい) になるであろうことを意味する。さらに、減少がn+1 に反比例するので、
【０８１８】
【数２７１】
2005504348.tif 000299
【０８１９】
は小さな値のnでf*へ急速に収束し、n → ∞に連れて確率１でf*の近くに留まる。
【０８２０】
【数２７２】
2005504348.tif 000300
【０８２１】
は遅かれ早かれf*と同じ、もしくはこれよりも小さくなるので、この場合はそれへの注意によって終えられる。というのも、
【０８２２】
【数２７３】
2005504348.tif 000301
【０８２３】
である場合、ケース(iii)の仮説に違反するので、
【０８２４】
【数２７４】
2005504348.tif 000302
【０８２５】
を異なった方法で計算しなければならない。この場合、ケース(ii )の仮説は満たされ、ケース(ii)の以前の分析は有効になる。
【０８２６】
【数２７５】
2005504348.tif 000303
【０８２７】
である場合、
【０８２８】
【数２７６】
2005504348.tif 000304
【０８２９】
は、ケース(i)中での様に(21)を使って計算され、n → ∞に連れて、決まったポイントf*へ収束することは明確である。
【０８３０】
この証明を完全にするため、総計の確率
【０８３１】
【数２７７】
2005504348.tif 000305
【０８３２】
がf*へ収束することを示すために、３つのケースの分析が組み合わされる。
【０８３３】
(34)から、次のようなm > n が存在する。
【０８３４】
【数２７８】
2005504348.tif 000306
【０８３５】
これは
【０８３６】
【数２７９】
2005504348.tif 000307
【０８３７】
であることを意味するが、
【０８３８】
【数２８０】
2005504348.tif 000308
【０８３９】
が(35) に従うので、
【０８４０】
【数２８１】
2005504348.tif 000309
【０８４１】
である。
【０８４２】
方程式(35) は次の式を引きだす。:
【０８４３】
【数２８２】
2005504348.tif 000310
【０８４４】
この時、n → ∞に連れてδ→0となる。従って、次のようなn0> mと、無作為な小さな数∈が存在する。:
【０８４５】
【数２８３】
2005504348.tif 000311
【０８４６】
(46)の正反対の場合は、次のようなm > n が存在することが知られている。:
【０８４７】
【数２８４】
2005504348.tif 000312
【０８４８】
従って、
【０８４９】
【数２８５】
2005504348.tif 000313
【０８５０】
であるが、
【０８５１】
【数２８６】
2005504348.tif 000314
【０８５２】
である。(23)から、次のことが分かる。:
【０８５３】
【数２８７】
2005504348.tif 000315
【０８５４】
この時、n → ∞に連れてδ → 0 となる。ここでも、n0= mと、無作為な小さい数∈が次のように存在する。:
【０８５５】
【数２８８】
2005504348.tif 000316
【０８５６】
(22) と(49)、そして(52) を組み合わせて、次の式が引き出せる。:
【０８５７】
【数２８９】
2005504348.tif 000317
【０８５８】
前に論議した３つのケースから総計の確率
【０８５９】
【数２９０】
2005504348.tif 000318
【０８６０】
が次のように評価される。:
【０８６１】
【数２９１】
2005504348.tif 000319
【０８６２】
条件付けられた事象は相互に重なりなく，漏れがない（mutually exclusive and collectively exhaustive）ので, (53)、(54)、(55)、そして(56)を組み合わせて次のものを引き出す。:
【０８６３】
【数２９２】
2005504348.tif 000320
【０８６４】
そして結果は証明される。
Theorem 2 (プロセスD S HE2,2の収束の割合). f*が0.5 にセットされた場合、プロセスD S H E2,2で、
【０８６５】
【数２９３】
2005504348.tif 000321
【０８６６】
となり、これは、ワンステップで期待値へ収束することを意味する。
【０８６７】
Proof. (23) から、
【０８６８】
【数２９４】
2005504348.tif 000322
【０８６９】
は次の値となることが分かる。
【０８７０】
【数２９５】
2005504348.tif 000323
【０８７１】
これは、いつでも
【０８７２】
【数２９６】
2005504348.tif 000324
【０８７３】
であれば満たされる。
【０８７４】
しかし、初期化プロセスで
【０８７５】
【数２９７】
2005504348.tif 000325
【０８７６】
の値のセットと無関係に、この数は
【０８７７】
【数２９８】
2005504348.tif 000326
【０８７８】
の計算において取り消され、次のような単純な式(n = 0 とセットして得られる) が導き出される。
【０８７９】
【数２９９】
2005504348.tif 000327
【０８８０】
である場合、
【０８８１】
【数３００】
2005504348.tif 000328
【０８８２】
同様に、(35)の式を使って、
【０８８３】
【数３０１】
2005504348.tif 000329
【０８８４】
が次のような値をとることは明確である。
【０８８５】
【数３０２】
2005504348.tif 000330
【０８８６】
である場合、1 - p
【０８８７】
【数３０３】
2005504348.tif 000331
【０８８８】
の値を確率sで, f*より小さく初期設定することで、次の式が導かれる。:
【０８８９】
【数３０４】
2005504348.tif 000332
【０８９０】
そしてこれは、行列として次のように表せる。:
【０８９１】
【数３０５】
2005504348.tif 000333
【０８９２】
もちろん上の行列は
【０８９３】
【数３０６】
2005504348.tif 000334
【０８９４】
は確率1 - s でf*よりも大きく初期設定できる。
従って、
【０８９５】
【数３０７】
2005504348.tif 000335
【０８９６】
そしてこれは、行列として次のように表せる。:
【０８９７】
【数３０８】
2005504348.tif 000336
【０８９８】
(59)および(60)から、そして
【０８９９】
【数３０９】
2005504348.tif 000337
【０９００】
を使ってベクトル
【０９０１】
【数３１０】
2005504348.tif 000338
【０９０２】
を表すことにより、
【０９０３】
【数３１１】
2005504348.tif 000339
【０９０４】
と
【０９０５】
【数３１２】
2005504348.tif 000340
【０９０６】
の期待値は次のようになる。:
【０９０７】
【数３１３】
2005504348.tif 000341
【０９０８】
この時、Mは次に示されるマルコフ推移行列（Markov transition matrix）である。:
【０９０９】
【数３１４】
2005504348.tif 000342
【０９１０】
Mの固有地を計算すると，λ1 = 1 および，λ2 = 0となり、従って、マルコフ連鎖（Markov chain）は１回のステップで収束する!!
従って、
【０９１１】
【数３１５】
2005504348.tif 000343
【０９１２】
が確率s = 0.5 で一様に初期設定される場合、１回のステップで
【０９１３】
【数３１６】
2005504348.tif 000344
【０９１４】
はf*= 0.5の値に到達する。
【０９１５】
Theorem 3 (プロセスD S HEm,2の収束). アルファベットS = {s1,...,sm}と、その確率P = [p1,...,pm], コードアルファベットA = {0, 1}、そしてHuffman のプロセスを使って構築された２進数のHuffman ツリーT の、静止した、メモリのないソースを考えてもらいたい。ソースシークエンスX = x[1] ... x[M]がプロセスD S HEm,2とTによって符号化され、出力シークエンスY = y[1] ... y[R]を産出する場合、
【０９１６】
【数３１７】
2005504348.tif 000345
【０９１７】
この時、f*は、出力の中の0 の要求された確率
【０９１８】
【数３１８】
2005504348.tif 000346
【０９１９】
で、
【０９２０】
【数３１９】
2005504348.tif 000347
【０９２１】
、c0(n) は、時間n までに符号化された0 の数である。
【０９２２】
Proof. T のレベルの数の最大値がj であると仮定する。入力シークエンスから来る異なったシンボルが符号化されているので、レベルj がすべてのシンボルのために到達されるのではないことは明らかである。ツリーの最初のノードはX から来る全てのシンボルのために到達されることに注目して欲しい。-  全てのパスはTのルートから始まるのでこれは明らかである。この事実を利用して基礎ステップ（Basis step）は証明され、そして、Tの各レベル(j - 1 までの)において定まった点f*,に到達すると仮定し、レベルjでもまた、f*に到達するという帰納法のステップが証明される。
【０９２３】
Basis step: T の最初のレベルで、定まった点f*に到達することは証明された。ルートノードは確率１であるので、その左の子ノードは確率
【０９２４】
【数３２０】
2005504348.tif 000348
【０９２５】
を持ち、(兄弟特性（sibling property）のため)、そして右の子供は確率1 - p1である。これは、Theorem 1における、Huffman ツリーと３つのノードとまったく同じである。
【０９２６】
【数３２１】
2005504348.tif 000349
【０９２７】
であるかどうかによって、
【０９２８】
【数３２２】
2005504348.tif 000350
【０９２９】
の値はΔ1の分増加する(Theorem 1 のケース(ii) )、あるいはΔ1の分減少する(Theorem 1 のケース(iii)) 。これらは、(24)または(36)にそれぞれ示されている。
【０９３０】
【数３２３】
2005504348.tif 000351
【０９３１】
が漸近的にf*の値に到達するときはいつでも、この決まったポイントに留まる。(Theorem 1 のケース(i)) Theorem 1 の正確な分析に従うことによって（簡潔にするため省略）、
【０９３２】
【数３２４】
2005504348.tif 000352
【０９３３】
はn → ∞に連れて、確率１で漸近的に定まった点f*に到達することは明らかである。
【０９３４】
Inductive hypothesis:  定められた点f*が、レベルj-1 > 2で、n → ∞に連れて、確率１でプロセスD S H Em,2によって到達されると仮定する。
【０９３５】
Inductive step:  定められた点f*はレベルl = jで漸近的に到達されることが示される。レベルj は、入力シークエンスから来る全てのシンボルに到達されることはないので、それらのシンボルのためのアサイメントを0-1にするかまたは1-0にするかという決定はレベルk < j でなされなければならない。この場合、この論議はinductive hypothesis により、j で成立する。
【０９３６】
レベルj に到達する場合については、ブランチアサイメントに関する決定がサブツリーTjで行われ、そのルート(レベルj で) はウエイトｗを持ち、その2つのリーフは確率pj1とpj2を持つ。正規化した(つまり、ｗで割る)後に、Tjのルートは、関連する正規化された確率1 を、左の子供は関連する正規化された確率
【０９３７】
【数３２５】
2005504348.tif 000353
【０９３８】
を、そして右の子供は確率
【０９３９】
【数３２６】
2005504348.tif 000354
【０９４０】
を持つ。この時、兄弟特性（sibling property）のため、
【０９４１】
【数３２７】
2005504348.tif 000355
【０９４２】
となる。
【０９４３】
ブランチアサイメントに関する決定がTjのルートで成されているので、
【０９４４】
【数３２８】
2005504348.tif 000356
【０９４５】
である場合、(24) で示されたように、
【０９４６】
【数３２９】
2005504348.tif 000357
【０９４７】
の値はΔjの分増加させられる。これはTheorem 1 のケース(ii) に対応する。逆に、
【０９４８】
【数３３０】
2005504348.tif 000358
【０９４９】
である場合、(36)で示されるように、
【０９５０】
【数３３１】
2005504348.tif 000359
【０９５１】
はΔjの分減少し、これは、Theorem 1 のケース(iii) に対応する。最後に、
【０９５２】
【数３３２】
2005504348.tif 000360
【０９５３】
である場合、
【０９５４】
【数３３３】
2005504348.tif 000361
【０９５５】
は漸近的に定められた点f*に留まる(Theorem 1 のケース(i))。基礎ステップ（basis step）でのように、Theorem 1, の正確な分析に従うことにより(簡潔にするため省略)、
【０９５６】
【数３３４】
2005504348.tif 000362
【０９５７】
はn → ∞につれて、確率１で漸近的に定まった点f*を達成することにつながる。
【０９５８】
帰納法（induction）は続き、theorem は証明される。
【０９５９】
Theorem 4 (プロセスD A HE2,2の収束). アルファベットS = {0, 1}とコードアルファベットA = {0, 1}の、メモリのないソースを考えてもらいたい。ソースシークエンスX = x[1],..., x[n],...（ここでx[i] ∈ S、i = 1,...,n,...とする）がプロセスD A HE2,2を使って符号化され、出力シークエンス  Y = y[1],...,y[n],...（ここでy[i] ∈ A, i = 1,...,n,...となるような）を産出する場合、
【０９６０】
【数３３５】
2005504348.tif 000363
【０９６１】
ここで、f*は出力の中の0の要求された確率で、
【０９６２】
【数３３６】
2005504348.tif 000364
【０９６３】
、c0(n)は時間nまでに符号化された0 の数である。
【０９６４】
Proof. ここで定められた点f*はn → ∞に連れて、確率１でプロセスDA H E2,2によって漸近的に達成されることが示される。各時点で、プロセスD AH E2,2が兄弟特性（sibling property）を持つHuffman ツリーTnを維持することに注目していただきたい。Tnはルートを持ち、その確率、あるいはウエイトは１であり、確率
【０９６５】
【数３３７】
2005504348.tif 000365
【０９６６】
の左の子供と、
【０９６７】
【数３３８】
2005504348.tif 000366
【０９６８】
の右の子供を持つ。この時、兄弟特性（sibling property）のため、
【０９６９】
【数３３９】
2005504348.tif 000367
【０９７０】
である。
【０９７１】
この証明の詳細はTheorem 1 の証明と全く同じであるので、ここでは繰り返さない。しかしながら、各瞬間の時間‘n’ で、
【０９７２】
【数３４０】
2005504348.tif 000368
【０９７３】
に３つのケースがあることは明らかである。:
(i)
【０９７４】
【数３４１】
2005504348.tif 000369
【０９７５】
: この場合、Theorem 1 のケース(i) の実行により、nが無限に増加するのに伴い、
【０９７６】
【数３４２】
2005504348.tif 000370
【０９７７】
は定められた点f*に留まる。この時、時間‘n’ での入力の中の0の確率は
【０９７８】
【数３４３】
2005504348.tif 000371
【０９７９】
である。
(ii)
【０９８０】
【数３４４】
2005504348.tif 000372
【０９８１】
: この場合、(24) で示されたように
【０９８２】
【数３４５】
2005504348.tif 000373
【０９８３】
の値はΔの分増加するこれはTheorem 1 のケース(ii) に対応する。
(iii)
【０９８４】
【数３４６】
2005504348.tif 000374
【０９８５】
: この場合、(36)で示されたように、
【０９８６】
【数３４７】
2005504348.tif 000375
【０９８７】
の値はΔの分減少する。これはTheorem 1 のケース(iii) に対応する。
【０９８８】
これらの3 つのケースと、Theorem 1 の中で成されたのと同じ正確な分析を照らし合わせることで、出力の中の0の推定確率
【０９８９】
【数３４８】
2005504348.tif 000376
【０９９０】
がn → ∞に連れて定められた点f*に収束すると結論を下すことができる。(64)で示されたように、これは確率１で起こる。
【０９９１】
Theorem 5 (プロセスD A HEm,2の収束). アルファベットS = {s1,...,sm}とその確率P = [p1,...,pm], そしてコードアルファベットA = {0, 1}の、メモリのないソースを考えてもらいたい。ソースシークエンスX =x[1] ... x[M] がプロセスD A H Em,2によって符号化され、出力シークエンスY = y[1] ... y[R] を産出する場合、
【０９９２】
【数３４９】
2005504348.tif 000377
【０９９３】
この時、f*は出力
【０９９４】
【数３５０】
2005504348.tif 000378
【０９９５】
の中の要求された0の確率で、
【０９９６】
【数３５１】
2005504348.tif 000379
【０９９７】
、c0(n)は時間n間でに符号化された0 の数である。
【０９９８】
Proof. S のシンボルのための初期の配分を考えて、Huffman ツリーT0は、プロセスD A H Em,2の始めで構築される。プロセスDS H Em,2 の中でと同様に、Tkのレベルの最大値はl = j と推定される。このレベルは全ての瞬間の時間において到達されることはない。しかしながら、すべてのパスはTkのルートからスタートするので、最初のノードはXから来るすべてのシンボルによって到達される。定められた点f*はTkのすべてのレベル(j - 1 までの) で到達されると仮定して、レベルjでもf*に漸近的に到達することが帰納法（induction ）によって示される。
【０９９９】
Basis step: T0のルートノードは正規化されたウエイト１を持ち、その左の子ノードは正規化されたウエイト
【１０００】
【数３５２】
2005504348.tif 000380
【１００１】
を持ち、結果として、右の子ノードは正規化されたウエイト
【１００２】
【数３５３】
2005504348.tif 000381
【１００３】
を持つ。この時、兄弟特性（sibling property）のため、
【１００４】
【数３５４】
2005504348.tif 000382
【１００５】
である。ここでもまた、
【１００６】
【数３５５】
2005504348.tif 000383
【１００７】
とf*の関連性において三つのケースがある。
【１００８】
(i)
【１００９】
【数３５６】
2005504348.tif 000384
【１０１０】
である時はいつでも,
【１０１１】
【数３５７】
2005504348.tif 000385
【１０１２】
はn → ∞に連れて定められた点f*に漸近的に留まる。
(ii)
【１０１３】
【数３５８】
2005504348.tif 000386
【１０１４】
である場合、
【１０１５】
【数３５９】
2005504348.tif 000387
【１０１６】
はTheorem 4 のケース(ii) のように、Δ1の分増加する。
【１０１７】
(iii)
【１０１８】
【数３６０】
2005504348.tif 000388
【１０１９】
である場合、
【１０２０】
【数３６１】
2005504348.tif 000389
【１０２１】
はΔ1の分減少する(Theorem 4 のケース(iii))。
【１０２２】
これら三つのケースとTheorem 4で成された分析から、
【１０２３】
【数３６２】
2005504348.tif 000390
【１０２４】
がn → ∞に連れて、確率１でf*へ収束し、結果的に、(65) が満たされることが示される。
【１０２５】
Inductive hypothesis: n → ∞で、w. p. 1 D A H Em,2によって、定められた点f*はTkの全てのレベルj - 1 > 2 において到達されると仮定する。
【１０２６】
Inductive step: l = j においてf*が漸近的に到達されることを証明するために、２つのケースが考えられる。第1 のケースは、レベルj が符号化されているシンボルによって到達されない場合である。この場合、ラベル付けの方法は、レベルi < j の中で考慮され、結果はinductive hypothesis から導かれる。
【１０２７】
レベルjが到達されるケースにおいては、ラベル付けの決定はサブツリーTkjの中で行われる。そのサブツリーのルートは推定確率
【１０２８】
【数３６３】
2005504348.tif 000391
【１０２９】
を持ち、その２つのリーフは推定確率
【１０３０】
【数３６４】
2005504348.tif 000392
【１０３１】
と
【１０３２】
【数３６５】
2005504348.tif 000393
【１０３３】
を持つ。正規化の後(すなわち、
【１０３４】
【数３６６】
2005504348.tif 000394
【１０３５】
で割る)、Tkjのルートは確率１を持ち、左の子供の確率は
【１０３６】
【数３６７】
2005504348.tif 000395
【１０３７】
、右の子供の確率は
【１０３８】
【数３６８】
2005504348.tif 000396
【１０３９】
となる。この時、兄弟特性（sibling property）のため、
【１０４０】
【数３６９】
2005504348.tif 000397
【１０４１】
である。
【１０４２】
ここでも、ローカルサブツリーのための
【１０４３】
【数３７０】
2005504348.tif 000398
【１０４４】
の３つのケースがある。
【１０４５】
【数３７１】
2005504348.tif 000399
【１０４６】
である場合、
【１０４７】
【数３７２】
2005504348.tif 000400
【１０４８】
は定められた点f*に漸近的に留まる。
【１０４９】
【数３７３】
2005504348.tif 000401
【１０５０】
である場合はいつでも
【１０５１】
【数３７４】
2005504348.tif 000402
【１０５２】
は(24)で計算されたように、Δj(k) の分増加する。これは、
【１０５３】
【数３７５】
2005504348.tif 000403
【１０５４】
に頼っているので、正数である。
【１０５５】
【数３７６】
2005504348.tif 000404
【１０５６】
である場合、(36) で示されたように、
【１０５７】
【数３７７】
2005504348.tif 000405
【１０５８】
はΔj(k)の分減少する。(これもまた、
【１０５９】
【数３７８】
2005504348.tif 000406
【１０６０】
なので正数である。) これら３つのケースとTheorem 5で成された分析から、それは、(65)の中で述べられた様に、プロセスDA H Em,2がn → ∞に連れて、確率１で定められた点f*に到達するのと似た方法で続く。
【１０６１】
Theorem 6 (プロセスRV A HE2,2の収束). アルファベットS = {0, 1}とコードアルファベットA = {0, 1}の、メモリのないソースを考えてもらいたい。ソースシークエンスX = x[1],...,x[n],...（ここで、x[i] ∈ S、i = 1,...,n,...）とする）がプロセスRV A HE2,2によって符号化され、出力シークエンスY = y[1],...,y[n],...（ここで、y[i] ∈ A, i =1,...,n,...であるような）を産出する場合、
【１０６２】
【数３７９】
2005504348.tif 000407
【１０６３】
この際、f* = 0.5は出力の中の0の要求された確率で、
【１０６４】
【数３８０】
2005504348.tif 000408
【１０６５】
、c0(n)は時間nまでに符号化された0の数とする。従って、平均平方の、そして確率の観念から、
【１０６６】
【数３８１】
2005504348.tif 000409
【１０６７】
はf*へ収束する。
【１０６８】
Proof. 与えられた
【１０６９】
【数３８２】
2005504348.tif 000410
【１０７０】
の値と、時間‘n + 1’での出力の中の0の推定確率
【１０７１】
【数３８３】
2005504348.tif 000411
【１０７２】
は次のように計算される。:
【１０７３】
【数３８４】
2005504348.tif 000412
【１０７４】
この時、
【１０７５】
【数３８５】
2005504348.tif 000413
【１０７６】
は、出力の中の0の数と、
【１０７７】
【数３８６】
2005504348.tif 000414
【１０７８】
としたnとの間の比率として得られた出力の中の0の推定確率である。
【１０７９】
他方では、時間n + 1 でのプロセスRV A HE2,2の出力は次のような確率で生成される。:
【１０８０】
【数３８７】
2005504348.tif 000415
【１０８１】
この時、
【１０８２】
【数３８８】
2005504348.tif 000416
【１０８３】
は時間‘n’での入力の中の0の推定確率で、兄弟特性（sibling property）のため、
【１０８４】
【数３８９】
2005504348.tif 000417
【１０８５】
である。
【１０８６】
プロセスD S H E2,2の収束の分析で、
【１０８７】
【数３９０】
2005504348.tif 000418
【１０８８】
の正確な値が計算されたのと違い、ここでは、
【１０８９】
【数３９１】
2005504348.tif 000419
【１０９０】
の期待値が計算される。記法の容易にするため、与えられた
【１０９１】
【数３９２】
2005504348.tif 000420
【１０９２】
において、
【１０９３】
【数３９３】
2005504348.tif 000421
【１０９４】
を
【１０９５】
【数３９４】
2005504348.tif 000422
【１０９６】
の期待値とする。(68) の中のc0(n)の値を
【１０９７】
【数３９５】
2005504348.tif 000423
【１０９８】
と置き換えて、(69)を使うと二次の用語はすべて消える。すると、
【１０９９】
【数３９６】
2005504348.tif 000424
【１１００】
は次のように評価される。:
【１１０１】
【数３９７】
2005504348.tif 000425
【１１０２】
いくつか代数を操作すると、(70) を、次のように書き直せる。:
【１１０３】
【数３９８】
2005504348.tif 000426
【１１０４】
(76)の収束は、
【１１０５】
【数３９９】
2005504348.tif 000427
【１１０６】
の代わりに、
【１１０７】
【数４００】
2005504348.tif 000428
【１１０８】
の収束が調べられるということを除いてTheorem 1 の収束結果と平行することができる。この証明は、
【１１０９】
【数４０１】
2005504348.tif 000429
【１１１０】
のための3 つの相互に排他的なケースの分析により達成される。
【１１１１】
(i)
【１１１２】
【数４０２】
2005504348.tif 000430
【１１１３】
この場合、方程式(71)は漸近的に
【１１１４】
【数４０３】
2005504348.tif 000431
【１１１５】
へ導く。これは、
【１１１６】
【数４０４】
2005504348.tif 000432
【１１１７】
が、定められた点f*である場合、n → ∞に連れてそこに留まり、従って(66) は満たされるということを意味する。
【１１１８】
(ii)
【１１１９】
【数４０５】
2005504348.tif 000433
【１１２０】
この場合、方程式(71) を次のように書き換えることができる。:
【１１２１】
【数４０６】
2005504348.tif 000434
【１１２２】
この時、
【１１２３】
【数４０７】
2005504348.tif 000435
【１１２４】
なので、
【１１２５】
【数４０８】
2005504348.tif 000436
【１１２６】
である。
【１１２７】
(72) は(24) と類似していることに注意していただきたい。ここで、Δ > 0 は
【１１２８】
【数４０９】
2005504348.tif 000437
【１１２９】
が時間‘n’でf*に向かって増加することを意味する。
【１１３０】
(iii)
【１１３１】
【数４１０】
2005504348.tif 000438
【１１３２】
このケースの分析は(71)が下記のように表される。:
【１１３３】
【数４１１】
2005504348.tif 000439
【１１３４】
この時、
【１１３５】
【数４１２】
2005504348.tif 000440
【１１３６】
なので、
【１１３７】
【数４１３】
2005504348.tif 000441
【１１３８】
である。
【１１３９】
この場合、
【１１４０】
【数４１４】
2005504348.tif 000442
【１１４１】
が(36) の
【１１４２】
【数４１５】
2005504348.tif 000443
【１１４３】
と代わること以外は、(73)は(36)と類似する。ここで、Δ > 0 である。
【１１４４】
これら３つのケースと次のTheorem 1 の詳しい分析で、(簡潔にするため省略)   次のようになる。
【１１４５】
【数４１６】
2005504348.tif 000444
【１１４６】
従って
【１１４７】
【数４１７】
2005504348.tif 000445
【１１４８】
は確率変数で、その期待値
【１１４９】
【数４１８】
2005504348.tif 000446
【１１５０】
はn → ∞に連れて、出力の中の0の希望確率f*へ収束する。この確率変数
【１１５１】
【数４１９】
2005504348.tif 000447
【１１５２】
の漸近の変化を分析するための計算は以下のとおりである。:
【１１５３】
【数４２０】
2005504348.tif 000448
【１１５４】
【数４２１】
2005504348.tif 000449
【１１５５】
を評価するための、(68)からの条件付期待値
【１１５６】
【数４２２】
2005504348.tif 000450
【１１５７】
は次のように記される。:
【１１５８】
【数４２３】
2005504348.tif 000451
【１１５９】
【数４２４】
2005504348.tif 000452
【１１６０】
を含む２乗の用語がすべて取り消された(幸運にも)。予期値をもう一度計算すると、
【１１６１】
【数４２５】
2005504348.tif 000453
【１１６２】
は
【１１６３】
【数４２６】
2005504348.tif 000454
【１１６４】
の一次関数、
【１１６５】
【数４２７】
2005504348.tif 000455
【１１６６】
を含まない
【１１６７】
【数４２８】
2005504348.tif 000456
【１１６８】
といくつかの定数、となる。
【１１６９】
【数４２９】
2005504348.tif 000457
【１１７０】
は
【１１７１】
【数４３０】
2005504348.tif 000458
【１１７２】
を意味する。
【１１７３】
【数４３１】
2005504348.tif 000459
【１１７４】
この方程式の両側に(n+1)2を掛けて正規化すると、次のようになる。
【１１７５】
【数４３２】
2005504348.tif 000460
【１１７６】
ここでシークエンスが収束する場合と、しない場合の２つのケースがある。後者の場合、
【１１７７】
【数４３３】
2005504348.tif 000461
【１１７８】
はn2よりもゆっくりと収束する。n → ∞として極限を求めると、これは
【１１７９】
【数４３４】
2005504348.tif 000462
【１１８０】
という結果になる。もっと意味のある結果は
【１１８１】
【数４３５】
2005504348.tif 000463
【１１８２】
がn2よりも速く収束する場合に得られる。この場合、両側を展開し、
【１１８３】
【数４３６】
2005504348.tif 000464
【１１８４】
をその終了値
【１１８５】
【数４３７】
2005504348.tif 000465
【１１８６】
(これが最終的にとかれるものなので、式の左側へ動く) にセットすると、次のようになる。:
【１１８７】
【数４３８】
2005504348.tif 000466
【１１８８】
n2がここでも取り消され、これは、有限の回答が存在することを意味することに注目して欲しい。これが次の式を導く。:
【１１８９】
【数４３９】
2005504348.tif 000467
【１１９０】
または、:
【１１９１】
【数４４０】
2005504348.tif 000468
【１１９２】
【数４４１】
2005504348.tif 000469
【１１９３】
は0.5 で、
【１１９４】
【数４４２】
2005504348.tif 000470
【１１９５】
は0.25 なので、
【１１９６】
【数４４３】
2005504348.tif 000471
【１１９７】
はゼロとなる。従って、
【１１９８】
【数４４４】
2005504348.tif 000472
【１１９９】
は、平均f*、そして分散ゼロで確率変数へ収束する。これは、平均平方収束と確率の収束の両方を意味する。従って、次のtheorem へつながる。
【１２００】
Theorem 7 (Convergence of Process RV A H Em,2). アルファベットがS = {s1,...,sm}で、コードアルファベットがA = {0, 1}であるメモリのないソースを考えて欲しい。もしソースシークエンスX =x[1],..., x[M],... が（ここで、x[i] ∈ S, i = 1,..., M,...とする）、
プロセス  RV A H Em,2を使って符号化され、出力シークエンスY =y[1],...,y[R],...（ここでy[i] ∈ A, i = 1,...,R,... となるような）を産出する場合、
【１２０１】
【数４４５】
2005504348.tif 000473
【１２０２】
この時、f* = 0.5 は出力の中の0の要求された確率で、
【１２０３】
【数４４６】
2005504348.tif 000474
【１２０４】
、c0(n) は時間n までに符号化された0の数である。従って、平方平均と確率の観念から、
【１２０５】
【数４４７】
2005504348.tif 000475
【１２０６】
はf*へ収束する。
【１２０７】
Proof. プロセスRV A H Em,2ごとに、Huffman ツリーT0 は、はじめに推定された複数のシンボルS の配分に基づいて構築される。プロセスD A H Em,2の収束の証明にあるように、(Theorem 5), Tkの最大のレベルはl = j と仮定される。このレベルは全ての瞬間的時間において到達されることはない。しかしながら、全てのパスはTk のルートから始まるので、最初のノードはX から来る全てのシンボルによって到達されるTheorem 6 の証明は、ここで、basis case の証明を完全とする。
【１２０８】
法の議論（inductive argument）については、帰納法の仮説（inductive hypothesis）が使用される。すなわち、定められた点f*はTkの全てのレベル(j-1 まで) において、到達される。Theorem 5 の証明と同じ方法で論議することによって、(繰り返しを避けるため省略), 結果は、ツリーTk のレベルの数においての帰納法（induction）によって続く。
［付録Ｃ］
DODE+に使える単純な暗号化
この付録はENCPreserveの特別なケースのDODE+の中で使える単純な暗号化を記す。
【１２０９】
入力シークエンスXがdeterministic またはrandomized なDODEの具体化を使って符号化され、出力シークエンスY = y[1] ... y[R]（この時、y[i] ∈ A = ｛0, 1}である）を産出すると仮定する。Y はm = 2k ソースシンボルS = {s0,...,sm-1}（それを二進数に直したものは一般的な方法で得られる、すなわち、0000... から1111... まで)を使って構文解析される。出力Y′は、特定の符号化スキームφ : S = ｛s0,...,sm-1} →C = ｛w0,...,wm-1}から得られたwiに対応するY のR div k シンボルsiの１つ１つの符号化によって生成される。残りのR mod k ビットは、小さな数のビットのための似たようなマッピングを使って符号化できる。
【１２１０】
m!の異なる符号化スキームがあり、その各符号化スキームはユニークなキー、K（このキーは0からm!-1までの整数）を持つことに注目して欲しい。与えられたキーをマッピングに変えるプロセスは、m!からスタートする数Zでキーを何度も割り１まで減少させることから成る。
【１２１１】
すべての段階における余りは現在のマッピングを指定し、被除数は、次に減少したZの値で割られる。
【１２１２】
正式には、まず、wj ∈ C をwj0wj1... wjk と参照する。
【１２１３】
マッピングの手順は次に記す。最初はS = {s0,...,sm-1}で始まる。K をmで割り、被除数d0と余りj0を得る。C のコードワードw0はsj0で、これはS から取り除かれる。次に、d0 をm-1で割り、d1 とj1を得る。そして同じようにS のシンボルが全て取り除かれるまで続ける。
【１２１４】
このプロセスは単純で、一般的な教科書の中で説明されており、簡潔さのためにここでは省略される。しかしながら、次の小例は、この手続きを明確にすることを助けるだろう。
【１２１５】
Example 7. S = {000; 001; 010; 011; 100; 101; 110; 111} を、DODE から得られた出力がY = 011101001010110010110 でキーがK = 2451 である場合のソースアルファベットとする。
【１２１６】
マッピングの構築手続きはTable 28 の中に示す。Kを8 で割り、d0=308とi0 = 3を得る。従って、s3 = 011がw0に割り当てられる。; s3(テーブル中のボールドフェイス文字) がSから取り除かれる。308を7で割り、d1 = 43 とi1 = 5 が得られる。従って、s5= 110 がw1に割り当てられる。; s5 がS から取り除かれる。(テーブル中のボールドフェイス文字)
マッピング構築手続きは、同じやり方で、下のTable 29 の中で示される次のマッピングを得るために続く。
【１２１７】
最後に、このマッピングを使って, Y 構文解析する。従って、Y′=100000110001101001101 が得られる。
【１２１８】
【表２７】
2005504348.tif 000476
【１２１９】
【表２８】
2005504348.tif 000477
【１２２０】
S のシンボルが平等に配分された場合、(DODE とRDODEは統計の完全な秘密（Statistical Perfect Secrecy）を保証するので) 上に示されたキーの特定の性能はDODE+を、統計の完全な秘密（Statistical Perfect Secrecy）を保証する上に、非常に機能的な暗号体系にする。従って、統計平均を使用するDODE+ の暗号解析は不可能である。DODE+を破るためには、必ずキースペース全体の徹底的な探索を伴う。
【図面の簡単な説明】
【１２２１】
【図１】入力アルファベットS = {a, b, c, d, e, f}と、その確率P = {0.1, 0.15, 0.27, 0.2, 0.05, .23}、および出力アルファベットA = {0, 1} を含むOommen-Ruedaツリーである。ルートノードは２つの子ノードをポイントする。各ノードはウェート(子ノードのウェートの合計) を含有している。さらに各ノードは子ノードのウェートによる順序を含有している。すなわち、左の子供のウェートは、右の子供のウェートよりも大きいか、またはその逆かを含有している。この例ではDODEを使用しており、符号化は最適のデーター圧縮を達成してはいないが、ランダムな出力確率は達成することができる。
【図２】はS = {a, b, c, d}, P = {0.4, 0.3, 0.2, 0.1}, A = {0, 1}でHuffmanのアルゴリズムを使ったHuffman ツリーである。
【図３】一連の入力データをコード化するために使用されるプロセスD S H Em,2の概要の図である。プロセスへの入力はStatic Huffmanツリー, T, と、一連のソースX。一連の出力, Y。T の中にリーフとしての入力アルファベットの位置を見つけるハッシュ機能があると想定されている。
【図４】一連の入力データをコード化するために使用されるプロセスD S H Em,2の概要の図である。プロセスへの入力はStatic Huffmanツリー, T, と、一連のソースX。一連の出力, Y。T の中にリーフとしての入力アルファベットの位置を見つけるハッシュ機能があると想定されている。
【図５】次のプロセスD S H Em,2によってコード化された一連のデータを解読するために使用されるプロセスDS H Dm,2を示す概要の図である。プロセスへの入力はstatic Huffman ツリー, T,と、コード化されたシークエンス, Yである。出力は解読されたシークエンス、つまりオリジナルのソースのシークエンスである, X。
【図６】次のプロセスD S H Em,2によってコード化された一連のデータを解読するために使用されるプロセスDS H Dm,2を示す概要の図である。プロセスへの入力はstatic Huffman ツリー, T,と、コード化されたシークエンス, Yである。出力は解読されたシークエンス、つまりオリジナルのソースのシークエンスである, X。
【図７】プロセスD S H E2,2のために構築されたHuffman ツリーに対応可能な２種類のラベル付け方法を説明する。ここではS = {0, 1}, P= [p, 1 - p],
【１２２２】
【数４４８】2005504348.tif 000478
【１２２３】
とする。
【図８】Calgary CorpusからのファイルbibにD S H Em,2を実行した後に得た平均距離を図に表したものである。ここではf*= 0.5,  Θ = 2 とする。
【図９】一連の入力データをコード化するために使用されるプロセスD A H Em,2を示す概要の図である。プロセスへの入力は初期のAdaptive Hu(R)ffmanツリー, T , ソースシークエンスX. 出力シークエンス, Y。Tの中にリーフとしての入力アルファベットの位置を見つけるハッシュファンクションがあると想定されている。
【図１０】一連の入力データをコード化するために使用されるプロセスD A H Em,2を示す概要の図である。プロセスへの入力は初期のAdaptive Huffmanツリー, T , ソースシークエンスX. 出力シークエンス, Y。Tの中にリーフとしての入力アルファベットの位置を見つけるハッシュファンクションがあると想定されている。
【図１１】次のプロセスD S H Em,2によってコード化された一連のデータを解読するために使用されるプロセスDS H Dm,2を示す概要の図である。プロセスへの入力は、D S HEm,2に使用されたAdaptive Huffman ツリー, T, と、コード化されたシークエンス, Y。出力は解読されたシークエンス、つまりオリジナルのソースのシークエンスである,X。
【図１２】次のプロセスD S H Em,2によってコード化された一連のデータを解読するために使用されるプロセスDS H Dm,2を示す概要の図である。プロセスへの入力は、D S HEm,2に使用されたAdaptive Huffman ツリー, T, と、コード化されたシークエンス, Y。出力は解読されたシークエンス、つまりオリジナルのソースのシークエンスである,X。
【図１３】Calgary Corpus からのファイルbibにD A H Em,2を実行した後に得た平均距離を図に表したものである。ここではf*= 0.5, Θ = 2 とする。
【図１４】一連の入力データをコード化するために使用されるプロセスRV A H Em,2の概要の図である。プロセスへの入力は初めのHuffman ツリー, T , ソースシークエンス, X。出力はシークエンス, Y。T の中にリーフとしての入力アルファベットの位置を見つけるハッシュファンクションがあると想定されている。
【図１５】一連の入力データをコード化するために使用されるプロセスRV A H Em,2の概要の図である。プロセスへの入力は初めのHuffman ツリー, T , ソースシークエンス, X。出力はシークエンス, Y。T の中にリーフとしての入力アルファベットの位置を見つけるハッシュファンクションがあると想定されている。
【図１６】プロセスRV A H Em,2でのブランチアサイメントルールの決定がどのように
【１２２４】
【数４４９】2005504348.tif 000479
【１２２５】
と、擬似乱数, αの値に基づいているか実証する。
【図１７】次のプロセスRV A H Em,2によって符号化された一連のデータを解読するために使用されるプロセスRVA H Dm,2の概要の図である。プロセスへの入力は, プロセスRV A HEm,2に使用される, 最初と同じAdaptive Huffman ツリー, T , そして符号化されたシークエンス, Y。出力は解読されたシークエンス、つまりオリジナルのソースのシークエンスである, X。
【図１８】次のプロセスRV A H Em,2によって符号化された一連のデータを解読するために使用されるプロセスRVA H Dm,2の概要の図である。プロセスへの入力は, プロセスRV A HEm,2に使用される, 最初と同じAdaptive Huffman ツリー, T , そして符号化されたシークエンス, Y。出力は解読されたシークエンス、つまりオリジナルのソースのシークエンスである, X。
【図１９】プロセスRR A H Em,2でのブランチアサイメントルールの決定がどのように
【１２２６】
【数４５０】2005504348.tif 000480
【１２２７】
と、２つの擬似乱数の呼び出しの値に基づいているか実証する。
【図２０】Calgary Corpusからのファイルbib に, プロセスRV A H Em,2を実行した後に得た平均距離を図に表したものであり、ここではf*= 0.5、Θ = 2 とする。
【図２１】Calgary Corpusからのファイルbibに, プロセスRV A H Em,2を実行した後に得た平均距離を図に表したものであり、ここではf*= 0.5、Θ = 2 そして一時的な挙動は除去されたとする。
【図２２】Calgary Corpusからのファイルbibに, プロセスRR A H Em,2を実行した後に得た平均距離を図に表したものであり、ここではf* = 0.5, Θ = 2、そして一時的な挙動は除去されたとする。
【図２３】Canterbury corpus からのファイルfields.c の出力にsteganographic な技術を適用した結果のイメージ、オリジナルのキャリヤーイメージ、有名なLena イメージである。使用されるsteganographic法はかなり単純化した方法であるが、プロセスRVA H Em,2によって暗号化されたメッセージを含んでいる。
【図３】
2005504348.tif 000481
【図４】
2005504348.tif 000482
【図５】
2005504348.tif 000483
【図６】
2005504348.tif 000484
【図７】
2005504348.tif 000485
【図９】
2005504348.tif 000486
【図１０】
2005504348.tif 000487
【図１１】
2005504348.tif 000488
【図１２】
2005504348.tif 000489
【図１４】
2005504348.tif 000490
【図１５】
2005504348.tif 000491
【図１７】
2005504348.tif 000492
【図１８】
2005504348.tif 000493
【国際公開パンフレット】
2005504348.tif 000494
2005504348.tif 000495
2005504348.tif 000496
2005504348.tif 000497
2005504348.tif 000498
2005504348.tif 000499
2005504348.tif 000500
2005504348.tif 000501
2005504348.tif 000502
2005504348.tif 000503
2005504348.tif 000504
2005504348.tif 000505
2005504348.tif 000506
2005504348.tif 000507
2005504348.tif 000508
2005504348.tif 000509
2005504348.tif 000510
2005504348.tif 000511
2005504348.tif 000512
2005504348.tif 000513
2005504348.tif 000514
2005504348.tif 000515
2005504348.tif 000516
2005504348.tif 000517
2005504348.tif 000518
2005504348.tif 000519
2005504348.tif 000520
2005504348.tif 000521
2005504348.tif 000522
2005504348.tif 000523
2005504348.tif 000524
2005504348.tif 000525
2005504348.tif 000526
2005504348.tif 000527
2005504348.tif 000528
2005504348.tif 000529
2005504348.tif 000530
2005504348.tif 000531
2005504348.tif 000532
2005504348.tif 000533
2005504348.tif 000534
2005504348.tif 000535
2005504348.tif 000536
2005504348.tif 000537
2005504348.tif 000538
2005504348.tif 000539
2005504348.tif 000540
2005504348.tif 000541
2005504348.tif 000542
2005504348.tif 000543
2005504348.tif 000544
2005504348.tif 000545
2005504348.tif 000546
2005504348.tif 000547
2005504348.tif 000548
2005504348.tif 000549
2005504348.tif 000550
2005504348.tif 000551
2005504348.tif 000552
2005504348.tif 000553
2005504348.tif 000554
2005504348.tif 000555
2005504348.tif 000556
2005504348.tif 000557
2005504348.tif 000558
2005504348.tif 000559
2005504348.tif 000560
2005504348.tif 000561
2005504348.tif 000562
2005504348.tif 000563
2005504348.tif 000564
2005504348.tif 000565
2005504348.tif 000566
2005504348.tif 000567
2005504348.tif 000568
2005504348.tif 000569
2005504348.tif 000570
2005504348.tif 000571
2005504348.tif 000572
2005504348.tif 000573
2005504348.tif 000574
2005504348.tif 000575
2005504348.tif 000576
2005504348.tif 000577
2005504348.tif 000578
2005504348.tif 000579
2005504348.tif 000580
2005504348.tif 000581
2005504348.tif 000582
2005504348.tif 000583
2005504348.tif 000584
2005504348.tif 000585
2005504348.tif 000586
2005504348.tif 000587
2005504348.tif 000588
2005504348.tif 000589
2005504348.tif 000590
2005504348.tif 000591
2005504348.tif 000592
2005504348.tif 000593
2005504348.tif 000594
2005504348.tif 000595
2005504348.tif 000596
2005504348.tif 000597
2005504348.tif 000598
2005504348.tif 000599
2005504348.tif 000600
2005504348.tif 000601
2005504348.tif 000602
2005504348.tif 000603
2005504348.tif 000604
2005504348.tif 000605
2005504348.tif 000606
2005504348.tif 000607
2005504348.tif 000608
2005504348.tif 000609
2005504348.tif 000610
2005504348.tif 000611
2005504348.tif 000612
2005504348.tif 000613
2005504348.tif 000614
2005504348.tif 000615
2005504348.tif 000616
2005504348.tif 000617
2005504348.tif 000618
2005504348.tif 000619
2005504348.tif 000620
2005504348.tif 000621
2005504348.tif 000622
2005504348.tif 000623
2005504348.tif 000624
2005504348.tif 000625
2005504348.tif 000626
2005504348.tif 000627
2005504348.tif 000628
2005504348.tif 000629
2005504348.tif 000630
2005504348.tif 000631
2005504348.tif 000632
2005504348.tif 000633
2005504348.tif 000634
2005504348.tif 000635
2005504348.tif 000636
2005504348.tif 000637
2005504348.tif 000638
2005504348.tif 000639
2005504348.tif 000640
2005504348.tif 000641
2005504348.tif 000642
2005504348.tif 000643
2005504348.tif 000644
2005504348.tif 000645
2005504348.tif 000646
2005504348.tif 000647
2005504348.tif 000648
2005504348.tif 000649
2005504348.tif 000650
2005504348.tif 000651
2005504348.tif 000652
2005504348.tif 000653
2005504348.tif 000654
2005504348.tif 000655
2005504348.tif 000656
2005504348.tif 000657
2005504348.tif 000658
2005504348.tif 000659
2005504348.tif 000660
2005504348.tif 000661
2005504348.tif 000662
2005504348.tif 000663
2005504348.tif 000664
2005504348.tif 000665
2005504348.tif 000666
2005504348.tif 000667
2005504348.tif 000668
2005504348.tif 000669
2005504348.tif 000670
2005504348.tif 000671
2005504348.tif 000672
2005504348.tif 000673
2005504348.tif 000674
2005504348.tif 000675
2005504348.tif 000676
2005504348.tif 000677
2005504348.tif 000678
2005504348.tif 000679
2005504348.tif 000680
2005504348.tif 000681
2005504348.tif 000682
2005504348.tif 000683
2005504348.tif 000684
2005504348.tif 000685
2005504348.tif 000686
2005504348.tif 000687
2005504348.tif 000688
2005504348.tif 000689
2005504348.tif 000690
2005504348.tif 000691
2005504348.tif 000692
2005504348.tif 000693
2005504348.tif 000694
2005504348.tif 000695
2005504348.tif 000696
2005504348.tif 000697
2005504348.tif 000698
2005504348.tif 000699
【国際公開パンフレット（コレクトバージョン）】
2005504348.tif 000700
【国際調査報告】
2005504348.tif 000701
2005504348.tif 000702
2005504348.tif 000703