本論文は,最も新しい無歪みデータ圧縮法の1つであるブロックソートデータ圧縮法(以下,ブロックソート法)に関して,情報理論的な解析を行い圧縮性能を評価したものである.

　ブロックソート法は,DigitalのBurrowsとWheelerによって1994年に提案された新しいデータ圧縮法である.その符号化アルゴリズムは次のとおりである.まず,与えられたシンボル列の一部または全体から成るブロックを,巡回シフトとソートを用いたBurrows-Wheeler変換と呼ばれる変換によって,同じ長さの別のシンボル列に置換する.次に,このシンボル列をMove-To-Front法によって,同じ長さの正整数列に変換する.最後に,この正整数列を算術符号もしくはHuffman符号によって2値符号語に変換することによって圧縮を行う.

　新しく提案された圧縮アルゴリズムが,それまでより高い圧縮性能を達成する場合には,データに存在する冗長性を取り除くための新しい機構が,符号化アルゴリズムの中に明示的に含まれていることが多い.現在既に知られている高性能な圧縮アルゴリズムについては,圧縮性能に寄与する本質的な機構が理論的に明らかになっており,主に,各シンボルを符号化する際にその文脈を用いて予測を行う手法と,系列を部分列に分割して部分列単位で符号化を行う手法の2種類に分けられている.しかしブロックソート法は,コンピュータサイエンスの分野において既知のアルゴリズムである,巡回シフト,ソート,Move-To-Front法等を組み合わせて用いるだけで,これまでに提案されている他の圧縮法以上の圧縮性能を実用的な記憶容量および速度で実現しており,特にこれまでデータ圧縮には用いられていなかったソートという操作を明示的に用いているため,注目されている.

　本圧縮法が提案者らによって発表された後,その高い圧縮性能について,提案者を含めていくつかの定性的な説明が行われてきている.また,実際のサンプルファイルを圧縮することによる実験的な性能評価や,圧縮速度を向上するためのアルゴリズムの改良などがいくつか行われてきた.しかし,本手法の圧縮性能に関する情報理論的な解析は,筆者の知る範囲ではこれまで全く行われていない.その理由として,本圧縮法では与えられたデータを一度,Burrows-Wheeler変換によって同じ長さの全く別のデータに置換してしまうことが挙げられる.この変換から出力されたデータは,データに含まれる各シンボルの出現順序が元のデータとは異なっているために確率過程と見倣すことができない.本手法においてこのデータが入力されるMove-To-Front法は,それ自身1つの圧縮法であり,これまでは定常無記憶情報源と呼ばれる確率過程に対してのみ圧縮性能が評価されていた.しかし,ここでMove-To-Front法に入力されるデータは確率過程とは見倣せないため,一般に確率過程に対して適用される様々な情報理論的な手法が適用不能となってしまい,情報理論的な性能解析を行うことができないと考えられていた.

　本論文では,与えられたデータをBurrows-Wheeler変換することによって生成されるシンボル列だけでなく,Burrows-Wheeler変換の操作全体に着目することにより,与えられたデータの時系列と,この圧縮法で用いられているMove-To-Front法やソートとの相互関係について情報理論的に定式化を行ない,本圧縮法を,各シンボルの文脈を用いて予測を行う符号化法と類似の手法で扱えることを明らかにした.特に,Move-To-Front法の性能評価は,これまでは定常無記憶情報源に対する符号語長の上界の評価しか行われていなかったために,定常性や無記憶性を全く仮定しない一般のシンボル列や,区分的には定常であるが全体としては非定常な系列に対する性能評価がどこまで可能であるか明らかになっていなかった.本研究においては,Move-To-Front法で変換するシンボル列が確率過程であるという前提をおかない場合にも成立し得る性質を明らかにした.また,この性質を利用することにより,定常エルゴード情報源に対するブロックソート法の符号語長を評価できることを指摘した.

　本論文においては実際に,Move-To-Front法から出力される正整数列を,正整数のユニバーサル表現を用いて2値符号語に符号化するバリエーションを考え,そのバリエーションによる漸近的な符号語長の上界を評画した.まず,定常エルゴード情報源に対して,符号化するデータのブロック長を無限に大きくしたときの漸近的な符号語長の上界を具体的に求めた.さらに,定常全エルゴード情報源に対して,複数のシンボルを1シンボルとして扱うシンボル拡大を行った場合の漸近的な符号語長を評画し,概収束符号化定理および平均収束符号化定理を証明した.ここで,定常全エルゴード情報源とは,任意にシンボル拡大を行った系列が全て定常エルゴード情報源と見倣せるような情報源を差し,定常無記憶情報源や,定常エルゴードなマルコフ情報源などを含む,十分広い情報源のクラスである.この定理によって,ブロックソート法が様々な種類のデータに対して高い圧縮性能を達成できることが,初めて理論的に明らかになった.

　ただし,ここで概収束および平均収束符号化定理を導く際に用いたシンボル拡大という操作は,ブロックソート法の符号化アルゴリズムには元々含まれていなかった手続きである.ブロックソート法の様々な実装においては,このシンボル拡大という操作を行わなくても,有限サイズのデータに対してかなり高い圧縮性能を達成するという実験結果が報告されている.そこで,本研究においてはさらに,一般のブロックソート法の実装とほぼ同じ符号化アルゴリズムである,Move-To-Front法から出力される正整数列を算術符号化するバリエーションに対しても漸近的な性能を解析した.この解析においては情報源として定常エルゴードなk次マルコフ情報源を考え,このクラスの情報源に対して上記のバリエーションを用いた場合には,一般に情報源のエントロピーレートを達成することは不可能であることを示した.その上で,上記のバリエーションが定常エルゴードなk次マルコフ情報源のエントロピーレートを達成するための十分条件を示した.これまでのブロックソート法に対する圧縮性能の評価は主に,具体的なサンプルファイルを実際に圧縮することで行われてきたが,この解析によって本手法が高い圧縮性能を示す情報源のクラスが明らかになった.

　以上の解析によって,情報源に対して適当な仮定を置くことにより,ブロックソート法が理論的な圧縮限界までデータを圧縮可能であるという漸近最良性が証明されたため,次の情報理論的な研究課題としては,データのブロック長が有限である場合の,1シンボルあたりの符号語長と理論的な圧縮限界である情報源のエントロピーレートとの差である,冗長度の評価が挙げられる.そこで,本研究においては最後に,ブロック長が有限である場合の圧縮性能の理論的な解析を行った.この解析においては,任意に文脈の集合を設定したときに成立する符号語長の上界を提示した.ここでは,冗長度を具体的な形で求めることはまだ出来ていない.しかし,多階調の自然画像データをブロックソート法で圧縮する場合に,この解析において用いた考え方が有効であることを示した.

　一般に多階調画像データにおいては,アルファベットサイズに比較して符号化するデータのサイズが余り大きくはならない.従って,シンボル列によって構成されるような文脈モデルを構築すると,符号化するデータのサイズに比べてモデルを複雑に作り過ぎてしまうために圧縮性能の低下を招いてしまう,over parameterizationの問題が存在する.このようなデータに対してブロックソート法を用いて圧縮を行った場合には,符号化の際に文脈を明示的に区別しないため,複数の文脈をマージして一つの文脈として扱っているのと同じ効果を得ることができる.この性質により,アルファベットサイズに比べてそれ程大きくないサイズのデータを圧縮する場合にも,ブロックソート法が高性能を達成可能であることが定性的に示された.

　本研究においては以上のように,ブロックソートデータ圧縮法について,漸近的な場合およびデータサイズが十分には大きくない場合のそれぞれについて,情報理論的な解析を行った.その結果により,これまでは特定のファイルを圧縮することによる実験的な評価しか行われていなかったブロックソートデータ圧縮法の圧縮性能を,理論的に評価できることが明らかになった.

　本論文は,「ブロックソートデータ圧縮法に関する情報理論的研究」と題し,5章からなる.

　データ圧縮符号化のうち,復号時に元のデータが1ビットの誤りもなく復号できる符号化を無ひずみデータ圧縮といい,広範囲な情報源を同一の符号で効率よく圧縮できる符号をユニバーサル符号という.無ひずみユニバーサルデータ圧縮符号としては,1970年代に考案されたLempel-Ziv符号を始めとする辞書法が現在も広く用いられている.しかし,1990年代半ばに,新たにソートを利用した圧縮法が幾つか提案され,その中でもブロックソートデータ圧縮法は従来の辞書法に比べて圧縮性能が優れていることから研究者の注目を集めており,また既に一般にも用いられ始めている.辞書法に属するユニバーサルデータ圧縮符号に関しては,情報理論的な解析が多くの研究者によりなされ,その理論的性能評価が詳しくなされている.これに対して,ブロックソートデータ圧縮法では,符号化で用いられるソートによりデータ系列が並び換えられ,データ系列の確率構造が破壊されるため,理論的な解析が難しく,今まで情報理論的な性能評価が全くなされていなかった.本論文では,圧縮するデータ系列の中で同一文脈を持つ文字が,ソート後に引き続いて出現する特性があることを利用して,理論的な性能評価を行っている.具体的には,定常エルゴード情報源に対して,ブロックソートデータ圧縮法に対する漸近的な圧縮率の理論的上界を与えるとともに,定常全エルゴード情報源の場合には,シンボル拡大を行うことにより,ブロックソート法で圧縮限界のエントロピーレートまで漸近的に圧縮可能であることを証明している.

　第1章は「序論」であり,本論文で取り扱っている研究の背景や位置づけを述べるとともに,本論文の構成を示している.

　第2章「データ圧縮」では,本論文の解析で必要となる情報理論的な諸概念および既に知られている情報源符号化定理を要約している.また,データ圧縮符号を分類し,ブロックソートデータ圧縮法がデータ圧縮符号の中でどのような位置付けになっているかを明らかにしている.

　第3章は「ブロックソートデータ圧縮法」と題し,その符号化アルゴリズムおよび復号アルゴリズムを紹介するとともに,ブロックソートデータ圧縮法のさまざまな改良方式を要約している.さらに,ソートを用いた他のデータ圧縮法である文脈ソート法やACB法などの符号化・復号化アルゴリズムを紹介するとともに,それらとブロックソートデータ圧縮法との関係を定性的に明らかにしている.また,ブロックソートデータ圧縮法で利用されているmove-to-front法に関しても従来の研究内容をまとめている.

　第4章「ブロックソート法に対する情報理論的な性能評価」は,本論文の中心的な章であり,ブロックソートデータ圧縮法に対する情報源符号化定理を与えている.ブロックソートデータ圧縮法において,ソートにより並び換えられた系列は,元の系列において同一文脈を持つ文字が連続して出現する特性が有ることを示し,その特性を用いて,個別のデータ系列に対する圧縮率の上界が,そのデータ系列の文脈に基づく各文字の頻度を用いて表現できることをまず証明している.次に,情報源が定常エルゴード情報源の場合に対して,AEP(Asymptotic Equipartition Property)を用いて,頻度とエントロピーを関係付けることにより,エントロピーレートの関数として圧縮率の上界を導出している.そして,平均符号語長がその上界でおさえられることを示す平均収束符号化定理と,その上界より大きくなる確率が符号長が長くなるとともにゼロに収束することを示す概収束符号化定理を証明している.さらに,これらの結果とシンボル拡大(連続した幾つかの文字を一つの文字と見なして符号化をすること)を組み合わせることにより,ブロックソートデータ圧縮法で漸近的に圧縮限界のエントロピーレートまで圧縮可能なことを示す平均符号化定理および概収束符号化定理を証明している.

　これらの成果以外に,ブロックソートデータ圧縮法の幾つかの改良方式に対しても解析がなされている.データ系列の終端記号を利用する改良方式に対しては,上述の符号化定理に対する証明を少し修正することにより,同様に符号化定理が証明できることを明らかにしている.また,ソート後の系列を正整数のユニバーサル表現を使用して2値符号化する代わりに算術符号を用いて2値符号化する場合に関しては,漸近的にエントロピーレートを達成できるための十分条件を与えている.

　上記の解析では,ブロック長が無限に大きくなる漸近的な場合を取り扱っているが,ブロック長が有限の場合に対しても,ブロックソートデータ圧縮法は非常に性能がよい.本論文では,頻度を用いた圧縮率の上界式が文脈の任意の分類に対して成立することを利用して,ブロックソートデータ圧縮法が有限のブロック長でも効率よく圧縮できることを,定性的に明らかにしている.

　第5章は「結論」であり,本論文で得られた成果を纏めるとともに,今後の研究課題に触れている.

　以上を要するに,本論文においては,強力な圧縮性能を有するブロックソートデータ圧縮法に対する情報理論的解析手法を考案し,その情報源符号化定理を初めて証明しており,情報工学上貢献するところが少なくない.

　よって,本論文は博士(工学)の学位請求論文として合格と認められる.