Data Compression Conference 2019（DCC2019）に参加してきましたので、興味のあった論文・発表（可逆圧縮関係）について概要を説明したいと思います。
Data Compression Conferenceとは
DCCはその名の通りデータ圧縮に関する国際会議で、主に動画像、文字列の圧縮技術や圧縮索引技術を対象にしています。毎年3月終盤に米国ユタ州ソルトレイクシティのスキー場snowbirdで開催されます。
snowbirdのスキー場はとても広大でスキー、スノーボード好きにとっては最高の場所ですが、一方そうでない人にとっては何もすることもなくただ毎日部屋と会場を行き来するだけで退屈に感じる人も多いかもしれません。
ホテルから5分ほど歩いたスキー場のレストランでは、アメリカらしいハンバーガーやステーキを楽しむことができます。ステーキ屋は混むので事前に予約するのがおすすめです。
前置きはこれぐらいにして、さっそく気になった論文・発表を紹介していきたいと思います。
BWT
BWT、FM-indexに関する解説記事はこちら。
招待講演：25 Years of the Burrows-Wheeler Transform: The Past and the Future of an Unusual Compressor
25 Years of the Burrows-Wheeler Transform: The Past and the Future of an Unusual Compressor
Prof. Giovanni Manzini
University of Piemonte Orientale "Amedeo Avogadro", Italy
BWTが提案されて今日までの25年を振り返るお話です。
BWTの歴史
BWTはBurrows Wheeler Transformの略で、1994年著者のBurrowsさんとWheelerさんがTechnical Reportで提案した文字列の変換方法のことである（実は1983年にはアイディアを思いついていたものの、当時としては先進的すぎて初期のレビュアーはその重要性を見逃してしまっていたそうだ）。BW変換は入力文字列の文字をある規則で入れ替える、BW変換後の文字列はとても圧縮しやすく、また元の文字列を復元することが可能となるため、データ圧縮の前処理として有効に機能する。BWTをベースにした圧縮プログラムbzipはgzipなどに比べ圧縮率も高く、現在でも広く普及されている。その後BWTに転機が訪れる。2000年に、BWTは圧縮だけでなく圧縮索引としても使えるということが分かった。この圧縮索引が有名なFM-indexである（招待講演者のManziniさんとFerraginaさんが提案し、二人の頭文字をとってFM-indexと名付けられた）。その後多くのBWTの亜種が誕生し、文字列だけでなくtreeやdagなど様々な種類のデータの圧縮、圧縮索引に応用されている。
Wheeler Graph
[Gagie, Manzini, Sirén, TCS2017]は数多く存在するBWTの亜種を対象とする統フレームワークWheeler Graphを提案した。Wheeler GraphによりBWTが持つ性質をより高い視点から捉えることが出来る。
感想
Wheeler Graphは面白そうなデータ構造なので勉強してみたいと思った。講演で、「Wheeler Graph上のパターンの検索はNFA上のパターンの検索を効率化していると捉えることが出来る」、というような説明をしていたのが目から鱗だった。確かに言われてみるとそうなっている。
Tunneling on Wheeler Graphs
Tunneling on Wheeler Graphs
Jarno N. Alanko, Travis Gagie, Gonzalo Navarro, and Louisa Seelbach Benkner
[Baier, CPM2018]はBWTの冗長な性質を捉えるtunneling techniqueを提案した。著者らはこのtunnelingがWheeler Graphについても適用可能なことを示し、かつFM-index likeな検索もサポート可能であることを示した（[Baier, CPM2018]では検索がサポートされていなかった）。
感想：tunneling techniqueが非常に面白かった。tunnelingはWheeler graphな同型のパスをまとめる（潰す）様な技術で、視覚的に見るとその凄さがよく分かる。BWTは同じ文脈（部分文字列）の先行する文字は同じ文字になりやすいという性質を捉えている（なので圧縮しやすい）、tunnelingはそれを拡張して同じ文脈の先行する文字列は同じ文字列になりやすいという性質を捉えている、ということだと思う（間違ってたらごめんなさい）。
BWT Tunnel Planning is hard but manageable
BWT Tunnel Planning is hard but manageable
Uwe Baier and Kadir Dede
tunneling techniqueの効果の最大化問題はmaximum coverage problemに帰着できNP-hardであることを示した。この問題はある制限をかけるとPになり、著者らはこの制限下において高速かつ高圧縮なheuristicアルゴリズムを提案した。
感想：前の発表でも思ったけどtunneling techniqueの図が好き。
Space-Efficient Computation of the Burrows-Wheeler Transform
Space-Efficient Computation of the Burrows-Wheeler Transform
José Fuentes-Sepúlveda, Gonzalo Navarro, and Yakov Nekrich
実用のためにはBWTを高速に、かつ省領域で求めるアルゴリズムはとても重要である。現在のstate of the artは[Munro, Navarro & Nekrich, SODA 2017]による$O(n)$時間$O(n \log \sigma)$ bits領域アルゴリズムだが、実用上遅いという問題がある（ここで$n$は入力文字列長、$\sigma$はアルファベットサイズ）。著者らは実用上高速な実装法を提案し、実際に高速であることを実験で確かめた。
感想：どちらかというと元になっている[SODA 2017]の内容が気になった。BWTはSuffix Arrayがあると簡単に計算できるが、Suffix Arrayを使うと$O(n \log n)$ bitsと大きな領域が必要となる。それを解決するためにどんな工夫をしているのかとても興味を持った。
LZ77
LZ77についての解説記事はこちら。
LZRR: LZ77 Parsing with Right Reference
LZRR: LZ77 Parsing with Right Reference
Takaaki Nishimoto and Yasuo Tabei
LZ77を拡張したより強い圧縮法LZRRを提案する。
LZ77は入力文字列を左から右に走査しフレーズと呼ばれる部分文字列の列に分解する分解法である。各フレーズは現在の読み込み地点から出現する文字列で、かつそれよりも前の位置でも出現する最長共通部分文字列で分解する。各フレーズを以前に出現した最長共通部分文字列の出現位置と長さで表現すると、このフレーズ列は入力文字列を表す圧縮表現であり、各フレーズは以前の文字列を参照することで復元することが出来る。
LZ77の各フレーズは現在地点の左側の文字列を辞書と見なし、その中で最長の文字列を参照している、と見ることが出来る。LZRRは左側だけでなく右側の文字列も辞書とみなし、その中で最長の文字列を選択する戦略を取る。ただし、循環参照を許すとフレーズの復元が不可能になるので、循環参照を行わないように参照する文字列を選択する。この様な方針で行うと入力の逆文字列のLZRRサイズは順文字列のLZ77サイズ以下になることが証明できる。
感想：戦略はとても単純でこのアルゴリズムがLZ77の誕生から40年以上の間、誰も提案していなかったことに驚いた。理論的には$O(n^2)$時間だが、実用では$O(n)$時間の挙動をする点も素晴らしい。
Practical Indexing of Repetitive Collections using Relative Lempel-Ziv
Practical Indexing of Repetitive Collections using Relative Lempel-Ziv
Gonzalo Navarro and Victor Sepulveda
Highly-repetitiveなデータ（同じ文字列がたくさん出現するデータ、genomeやwikipediaの編集履歴など）を扱うgold-standardなソフトウェアとしてLZ圧縮が使われている。[Kuruppu, Puglisi, and J. Zobel, SPIRE 2010]はLZ圧縮と同等の圧縮率で文字列の参照が用意なRelative Lempel Ziv（RLZ）を提案した。しかしアルゴリズムは複雑で実装されていないという問題があった。著者らはRLZと競争可能な理論保証を持ちながら、よりシンプルで実装可能なアルゴリズムを提案した。
感想：このテーマで研究をするには、各種データ構造の幅広い知識、それも理論から実用まで、を理解する必要があってなかなか戦うのは大変だなとしみじみ思う。実装も得意でないといけないし。
On Lempel-Ziv Decompression in Small Space
On Lempel-Ziv Decompression in Small Space
Simon J. Puglisi and Massimiliano Rossi
LZ77の圧縮表現から元文字列の復元は、左から順にフレーズを読み参照する文字列を展開することで完了する。しかし、この方法では展開した文字列をすべてメモリ上に格納する必要があり大きな領域が必要となる。[Bille, Ettienne, Gagie, Gørtz, and N. Prezza, arxiv 2018]はLZ77サイズに比例する領域で高速に動作するLZ77展開アルゴリズムを提案した。著者らはBilleのアルゴリズムを実装し、Billeのアルゴリズムは実用上遅く領域も多く必要なことを確認した、またspace-time tradeoffな最適化を施し、この最適化が有効なことを実験的に確認した。
（ここらへん理解があやふやなので注意）[Bille+, arxive 2018]の戦略は各フレーズの先頭、後頭の展開文字列を指定されたサイズ$\tau$だけ展開しそれらを連結した文字列を使って展開する。つまりこれらをキャッシュとみなすことにより高速に展開する。
感想：技術的に難しいところはどこか、それをどのように解決するのかまで理解できなかった。残念。
文法圧縮
文法圧縮、Re-Pairについての解説記事はこちら。
MR-RePair: Grammar Compression based on Maximal Repeats
MR-RePair: Grammar Compression based on Maximal Repeats
Isamu Furuya, Takuya Takagi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Takuya Kida
文法圧縮で最も圧縮率の高いアルゴリズムの1つとしてRe-Pairが知られている。著者らはRe-Pairと文字列の特徴を表すmaximal repeatsとの関係性を解析した。また、maximal repeatsとRe-Pairを融合したMR-Repairと呼ぶ文法圧縮アルゴリズムを提案し、そのサイズがオリジナルRe-Pairのサイズ以下になることを示した。また実験によりMR-RepairサイズはオリジナルRe-Pairサイズに比べ良いときで55%の圧縮率の改善に成功することを確認した。
Re-Pairは2回以上出現する最頻出のbi-gramを見つけ、そのbi-gramを導出する規則・変数を追加、bi-gramを変数に置き換え、この作業を繰り返すことにより、文法規則を得るアルゴリズムである。maximal repeatsは左に1文字追加しても右に1文字追加しても出現回数が減少するような文字列である。
Re-Pairとmaximal repeastsには以下のような関係性がある
- 最頻出bi-gramは1つの最頻出maximal repeats中に1回だけ出現する
- 最頻出bi-gramの頻度と最頻出maximal repeatsの頻度は一致する
- 最頻出maximal repeats同士は高々1文字overlapする
Re-Pairサイズは最頻出bi-gramの置き換え順序によって変化する（あるbi-gramの置き換えにより、他のbi-gramの頻度が減少する、ということが起こるため）。
このとき、最頻出maximal repeatに含まれる最頻出bi-gramの置き換え順序はRe-Pairサイズに影響しないということを示した（上記の関係性から）。つまり、最頻出maximal repeatの選択順序（MR-order）がRe-Pairサイズを決定する。
さらに、Re-Pairが最頻出のbi-gramで置き換えるところを、最頻出のmaximal repeatsで置き換えるように変更したのMR-Repairを提案する。つまり、オリジナルRe-Pairの規則の右辺サイズが2だったものが、MR-Repairでは2以上になる。MR-RepairサイズはMR-orderが同一のRe-Pairサイズ以下に必ずなる。これはmaximal repeats中のbi-gramの置き換え順序はサイズに影響しないため、bi-gramずつ置き換えるよりも複数文字を表す規則を1つ追加するほうがサイズが小さくなるためである。
感想：maximal repeatsとRe-Pairの置き換え規則という一見関係なさそうな事柄が関係していることが面白い。MR-orderによってサイズが異なるので、良いサイズのMR-orderを選択する方法はあり得るのか、多項式時間で出来るのかなどが気になった。
RePair in Compressed Space and Time
RePair in Compressed Space and Time
Kensuke Sakai, Tatsuya Ohno, Keisuke Goto, Yoshimasa Takabatake, Tomohiro I, and Hiroshi Sakamoto
これまたRePairの話。Re-Pairは圧縮率の高いアルゴリズムであることが知られているものの、その反面、計算領域が非常に大きい（入力サイズの数十倍）ことが知られている。著者らは入力文字列をまず軽量なonline文法圧縮アルゴリズムで圧縮し、その文法圧縮上でRe-Pairを計算する、つまり再圧縮する手法を提案した。
文法の根の規則を再帰的に展開した導出木を考えると、元文字列は導出木の葉の列に対応する。またRe-Pairは規則の右辺サイズが2以下であるため、導出木は2分木となる。このとき、任意のbi-gramの出現はいずれかの規則$X_i=X_l, X_r$の$X_l$と$X_r$をまたがって出現する。この性質により、bi-gramの頻度を計算するとき展開文字列上のすべての出現を考える必要はなく、上記のようにまたがって出現するような規則$X_i$を見つけ、導出木中の$X_i$の出現頻度を計算すれば良い。つまり頻度計算が圧縮上で可能である。
Re-Pairでは置き換えた新しい変数を含むbi-gramの頻度を計算する必要があり、この計算を如何に圧縮データ上で実現するかが論文の肝である。$X_i=X_l X_r$にまたがるbi-gram abを$A$に置き換えたとき、$X_i=X_l^\prime A X_r^\prime$のように規則を書き換える、ここで$X_l^\prime$は$X_l$から末尾のaを取り除いた新しい規則、$X_r^\prime$は$X_r$から先頭のbを取り除いた新しい規則である。このように、すべての変数は左規則、置き換え文字列、右規則という形で表現できるので、各変数で左規則 or 右規則でまたがる、置き換え文字列中で出現するbi-gramを計算し、$X_i$の頻度を計算すれば良い。
感想：計算機実験によると、提案アルゴリズムは極めて少ない領域で動作する一方、時間は膨大にかかってしまう。途中まで上記のように計算し、ある程度まで圧縮した後、通常のRe-Pairアルゴリズムで計算するアルゴリズムも提案されており、その場合、速度が大きく改善されるものの、使用領域がオリジナルRe-Pairの1/3程度使用する結果になっている。もう少し工夫することで計算時間にしろ領域にしろ改善できないものかなぁと思う。
Regular Expression Search on Compressed Text
Regular Expression Search on Compressed Text
Pierre Ganty and Pedro Valero
文法圧縮領域上で文法サイズに対して線形時間で指定された正規表現にマッチする行の個数を計算する。
感想：よくわからなかった(´・ω・｀)
その他
Dv2v: A Dynamic Variable-to-Variable Compressor
Dv2v: A Dynamic Variable-to-Variable Compressor
Nieves R. Brisaboa, Antonio Farin ̃a, Adri ́an G ́omez-Brando ́n, Gonzalo Navarro, and Tirso V. Rodeiro
単語を1文字と考えた圧縮法。LZ78の様に辞書を持ち、現在の地点から辞書にマッチする最大の文字列で分解する。このとき、1つ前の文字とマッチした文字列のすべてのprefixを足した文字列を辞書に登録する。また、符号化方法がbyte単位の可変長（つまり、1 byte, 2 byte, …と割り当てる）で、これまでにマッチした回数、出現頻度に依存して頻度の大きい文字列ほど短い符号語を割り当てる。
感想：符号化のやり方が面白い。ところでこれは自然言語、単語ベースの文字列にしか有効でないのだろうか？
Parameterized Text Indexing with One Wildcard
Parameterized Text Indexing with One Wildcard
Arnab Ganguly, Wing-Kai Hon, Yu-An Huang, Solon Pissis, Rahul Shah, and Sharma Thankachan
parameterized matchとは文字の写像を考慮した文字列照合である。例えば文字列ababcとxyxyzは(a→x, b→y, c→z)という写像により文字列が一致するため、ababcとxyxyzはparameterized matchすると言う。
著者らはwild-card文字を高々1つ含むparameterized match問題を考え（wild-card文字はどんな文字ともマッチする）、その問題を効率的に計算可能な索引構造を提案した。
感想：Parameterized Match難しい。
Polynomial Time Algorithms for Constructing Optimal AIFV Codes
Polynomial Time Algorithms for Constructing Optimal AIFV Codes
Mordecai Golin and Elfarouk Harb
固定サイズの文字列を可変長で符号化するFixed-to-Variable（FV）符号ではHuffman符号が最適だということが知られている。しかし、即時復号可能（符号の終端bitを読むと、その時点でそこが符号の切れ目ということが分かる）という制約条件を緩めるとより最適な符号化が存在する。AIFVはalmost instantaneous（AI）に復号が可能なFV符号である。AIFV-m codesはm個の符号木を使い、高々m bitsのdelayで復号可能（終端bitから追加でm bits読むことで復号できる）。最適なAIFVの計算にはcost parameter Cを変え収束するまで反復的に処理をする。その反復回数はこれまで見積もることができなかったが、著者らはその反復回数あ多項式時間に収まる新たなアルゴリズムを提案した。
感想：AIFVの原理は面白かった。ただ、良い符号木を作るコストが大きいのでどういう分野で使われる、適しているのかが気になった（まだ成熟してない？）。
Constructing Antidictionaries in Output-Sensitive Space
Constructing Antidictionaries in Output-Sensitive Space
Lorraine A.K. Ayad, Golnaz Badkobeh, Gabriele Fici, Alice H ́eliou and Solon P. Pissis
文字列xが入力文字列に出現せず、xの先頭1文字削ったsuffixと後頭1文字を削ったprefix両方が入力文字列に出現するときxをMinimal Absent Word（MAW）と呼ぶ（MAWの日本語解説記事はこちら）。MAWはデータ圧縮やバイオインフォマティクスの分野で応用されている。MAWは$O(\sigma n)$個あり、$O(\sigma n)$ time or $O(n + M)$ time時間アルゴリズムが提案されている、ここで$M$は出力MAWサイズ。多くのアルゴリズムはSuffix Arrayなどの索引構造を用いるため$\Omega(n)$領域を必要とし、大きなサイズを入力とする場合問題となる。著者らは出力サイズに対して依存するアルゴリズムを提案した。
感想：MAWの応用について気になるところ。