通信や記憶装置などの効率化をはかるために，compress, gzip, LHAなどを初めとするデータ圧縮ツールが広く使用されている． このようなデータ圧縮符号は情報源の確率を直接的に用いない アルゴリズムで作られているため，さまざまな種類のデータを同一の 符号で効率よく圧縮でき，そのことからユニバーサル符号と呼ばれている．

従来から広く用いられているユニバーサル無歪みデータ圧縮符号は， Lempel-Ziv符号を基礎とするいわゆる辞書法が主流であった． 辞書法では，圧縮したい部分系列を，あるデータ構造を持つ辞書内で 検索し，その辞書内における一致系列の番号で符号化するとともに， 符号化が終了した部分系列を用いて辞書を動的に更新していく方式で あった．しかし，辞書法とは呼ばれているものの， 辞書内の部分系列の番号付けは，アルファベット順が考慮されている 訳ではなく，その部分系列の生起時刻に基づいて付けられていた．

これに対して，1990年代中ごろから，新たにソートを用いてデータ系列の 文脈を並び換え，文脈の近い順に番号付けを行うことにより，従来の 辞書法よりさらに性能のよい圧縮を実現できる符号が提案され，注目を 集めている（既にブロックソート法は，圧縮ツールbzipとして利用されている）． ソートを用いる新しい符号化法には，Burrows-Wheelerのブロックソート法， Yokoo-Takahashiの文脈ソート法，BuyanovskiのACB法などがあるが， 本チュートリアル講演ではブロックソート法と文脈ソート法を主に 取り上げ，符号化・復号化アルゴリズム，改良方式， 理論解析，他のユニバーサル符号との関連などについて詳しい解説を行う 予定である．

ソートを用いた符号化法は，その性能の良さから， 今後ユニバーサル無歪みデータ圧縮符号の主流になるものと思われるが， 一般にはまだあまり知られていない． 今回は講演を２つに絞り， 十分時間をかけて聴講者に分かりやすい本当のチュートリアル講演が 行えるように配慮されている． 情報理論およびアルゴリズム論の研究者はもちろんのこと， 専門分野外の人でもデータ圧縮に興味のある人は， ぜひこの機会を利用してソート法を知って頂きたい．

• 司会: 星 守 （電通大）
• 1. 山本 博資 （東大）
  「ブロックソーティングによる無歪みデータ圧縮とその周辺」
• 2. 横尾 英俊 （群大）
  「文脈ソーティングによる無歪みデータ圧縮とその周辺」