本記事は20171224に初版が完成し、20180115に公開されました。
背景
表記事で、tar.bz2の作り方をサンプルとして提示した。
しかし、AtCoderに存在しないコマンドはこの方法では呼び出せない。
bcm
bcm。最初はTLEだった。圧縮方式はBWT+ContextModel。BWTはBZip2にも採用されているメソッドである。
ContextModelはPAQを源流とする新しいメソッドであり、低速でありながら非常に圧縮率が高いのが特徴である。bcmを選定に含めたのは、ベンチマークの中でこのツールが突出して高速であったためである。
しかし、実際に動くかは実験するまでわからない。このような選定中は、コードに余り手を入れずに検証したいことが多々ある。そういう場合、バイナリをソースに埋め込んで実行時に展開すればよい。Rubyの場合、Pythonと違ってBZip2やlzma(やbase85)が標準モジュールではないため、zlib.b64が良いだろう。
バイナリは、Debian/Ubuntu環境を用意して、gcc-5(以下)かclangでコンパイルして用意すれば良い。あまり新しすぎるとgcc-5は入っていない場合があるのでclangを使うこと。
bcmはアーカイバ機能がないため、tar.bz2と同様、tar.bcm形式を作成すれば良い。
PPMd
ツール名でもあるPPMdメソッドは、新しくも、7zやRAR、zipにも採用されている実績のあるメソッドである。今回は最新版であるPPMdJ1を採用した。
PPMdはアーカイバ機能があるため、(tarやcpioのような)パイプは使っていない。
ただし、ユーティリティとしての作りに不具合があった。今回は、
- ワイルドカード展開機能を無効にした。そもそもUnixではシェルが担当することである。
- 最適化の都合でgcc -O2だと動作しない部分が一部あった(clang -O2は可。clangは行儀がいいなぁ)。その部分の最適化はコンパイラに任せ、手動での最適化は解除した。
これが、Debianマシンでコンパイル、バイナリを埋め込み、暫定1位を取った提出である(※m1536とあるが誤りで、内部的にはm256として処理されている)。
https://wn2017_1.contest.atcoder.jp/submissions/1883227
ただ、さすがにこれを最終版にするのは気が引けたので、プログラムを1ファイルに結合し、C++でフロントエンドを作成した。
https://wn2017_1.contest.atcoder.jp/submissions/1903817
最終的な成果物は https://bitbucket.org/avenir/ppmdj1 のamalgamated.cppにある。
なお、本家PPMdJ1ではフォーマットのみ記されていて実行オプションががない、ソリッド書庫の作成にも対応している(まあPPMd書庫は仕様上スキップがないですし、ソリッドに出来るならそうすべきなんですけど)。 作成された書庫は本家でも展開できる。
「PPMd (J1) -m256 -o3 -s1 (native/clang/sort)」に記述がある、ファイルサイズ昇順でソートしたソリッド書庫、 494669618バイトが私のAtCoderでの記録である。
LZMA SDK
LZMA SDKにはPPMdH/I2関連のコードがある。アルゴリズムとしてはPPMdI2形式とは互換性があるが、PPMdH形式と互換性を持たせるには、ドキュメントの通り、RangeCoderを変更しなければならない(とはいっても、PPMdI2のRangeCoderを呼び出すだけで良いのだが)。また、アーカイブとしては、7-zipは第一エントリの展開しかできない。今回、PPMdJ1とは別に、PPMdH/I2書庫の互換ツールを作成した(J1が同一ツールで処理できないのは私の技術力不足でもありますが、H->I2とは異なりI2->J1ではRangeCoderにも手が加えられているようです)。
https://bitbucket.org/avenir/unppmd
私が普段作るツールの例に漏れず、pmdファイルのやり取りは標準入出力で行っている。
本家PPMdH/I2では作成できないソリッド書庫の作成に対応し、本家でも展開できるのは同様である。
memory factor
PPMd書庫では、指定できるメモリ量は1MBから256MBまでである。これは 20ビットシフト で実現されている。このシフト数を増やすことで2048MBまで指定することができるようになる(シフト数を変更すると書庫互換性は失われるのであくまで実験用であることに注意)。
今回の入力ファイルの合計サイズは1200MBである。
当然ながら、シフト数を増やせばPPMモデルの再構築コストが減るため、パフォーマンスは向上する。しかしながら、ソリッドモードをオンにしないと当然無意味である。というか、PPMdのソリッドモードの価値は、再構築コストに殆どがあるような気もする。
というわけで、後述の時間制限緩和を含めて、「F=23 PPMd (J1) -m256 -o4 -s1 (native/clang/sort_namer)」の486663763バイトがPPMdでの記録である。
https://wn2017_1.contest.atcoder.jp/submissions/1945161
bcm (再)
時間制限が緩和されたためbcmを動かすことが出来るようになった(高速モードでも320sという結果だったので、緩和に感謝)。アーカイバ機能がないので、今回はソリッド圧縮を行う必要があったことから、C++としては結局実装しなかった。
ただし、tar(等)連携のため、標準入出力を処理するように変更した。
https://bitbucket.org/avenir/bcm
最終的な提出では、極小アーカイバを別途作成しパイプした。
https://wn2017_1.contest.atcoder.jp/submissions/1954477 および https://gist.github.com/cielavenir/d4ac1742dcca0044b70f030be9872aea で、474098088bytes(2531121.79点)である。約12MBも更新されてしまった。
littlearcコマンドのソースは、諸事情により、上記unppmdリポジトリのapplet内に入れてある。
ところで、PPMdはサイズ昇順、bcmはサイズ降順でソートしたほうが圧縮率が良かった。興味深いところである。
その先へ
PPMdJ1である程度頑張りましたが、2バイト先の差を取るという前処理をしたら、逆にサイズが大きくなりました。7z -m0=Delta:2 -m1=...でも同様だったので実装のバグではないようです。bcmも同様でした。おしまい。(完)