休みは長かったけど、家の用事も多かったので、あまり論文を読むことができなかった。ただ、以前から少しずつ調査しているRe-Pairに関する論文を1本だけ読んだ。 A fully linear-time approximation algorithm for grammar-based compression Hiroshi Sakamoto, Journal of Discrete Algorithms, 2005. http://www.sciencedirect.com/science/article/pii/S1570866704000632 線形時間で、Re-Pair圧縮が可能なアルゴリズムである。Re-Pairの辞書の簡潔データ構造は、Navarro神らのチームが提案してくれていて、DAGベースの簡潔データ構造で実現できる。しかし、構築の方は、論文数もあまりなさそうで、上記の論文の