形式言語理論および十分統計量を用いたデータ圧縮の設計法に関する研究

あるデータ圧縮アルゴリズムが、与えられた情報源のクラス全体に対して、それぞれの情報源の理論的な圧縮限界を漸近的に達成できるとき、この圧縮アルゴリズムはその情報源クラスに対してユニバーサルであると言う。本課題では、無歪みデータ圧縮のユニバーサル性を、文脈自由文法と十分統計量を用いて理解することを目指し、研究を行なってきた。その結果、以下が明らかになった。(1)ユニバーサル性を確率収束によって定義した場合に、任意の情報源に対してユニバーサル符号の存在と漸近的に十分な統計量の存在が同値であることを証明した。これにより、具体的なユニバーサル符号の存在が示されていなかった情報源クラスに対しても、漸近十分統計量の性質を用いることによって、ユニバーサル符号の存在を示せるようになった。(2)ある情報源クラスに対して漸近十分統計量が存在する場合に、漸近十分統計量の性質を用いてユニバーサルデータ圧縮を構成できることを示した。(3)これまでに提案されているいくつかのデータ圧縮アルゴリズム、特に文脈自由文法を用いた文法圧縮のいくつかのバリエーションに対して、漸近十分統計量の性質を用いて符号のユニバーサル性および冗長度の評価を行なうことができた。(4)ユニバーサルデータ圧縮の代表的なバリエーションである、文脈の条件つき確率を用いる圧縮法とブロック分割に基づく圧縮法の両者について、十分統計量の性質を用いてユニバーサル性を証明することができた。これにより、これら2種類の圧縮のユニバーサル性を統一的に理解することができるようになった。

あるデータ圧縮アルゴリズムが、与えられた情報源のクラス全体に対して、それぞれの情報源の理論的な圧縮限界を漸近的に達成できるとき、この圧縮アルゴリズムはその情報源クラスに対してユニバーサルであると言う。本課題では、無歪みデータ圧縮のユニバーサル性を、文脈自由文法と十分統計量を用いて理解することを目指し、研究を行なってきた。その結果、以下が明らかになった。(1)ユニバーサル性を確率収束によって定義した場合に、任意の情報源に対してユニバーサル符号の存在と漸近的に十分な統計量の存在が同値であることを証明した。これにより、具体的なユニバーサル符号の存在が示されていなかった情報源クラスに対しても、漸近十分統計量の性質を用いることによって、ユニバーサル符号の存在を示せるようになった。(2)ある情報源クラスに対して漸近十分統計量が存在する場合に、漸近十分統計量の性質を用いてユニバーサルデータ圧縮を構成できることを示した。(3)これまでに提案されているいくつかのデータ圧縮アルゴリズム、特に文脈自由文法を用いた文法圧縮のいくつかのバリエーションに対して、漸近十分統計量の性質を用いて符号のユニバーサル性および冗長度の評価を行なうことができた。(4)ユニバーサルデータ圧縮の代表的なバリエーションである、文脈の条件つき確率を用いる圧縮法とブロック分割に基づく圧縮法の両者について、十分統計量の性質を用いてユニバーサル性を証明することができた。これにより、これら2種類の圧縮のユニバーサル性を統一的に理解することができるようになった。