大量の HTML 文書は URL 順に整列してから圧縮する

概要

大規模なウェブコーパスを作成するときは，HTML 文書を URL 順に整列することで，圧縮率をかなり改善できます．理由は，類似した文書を固めることができるからです．

という内容が，n-yo さんに紹介していただいた論文 ``On Compressing the Textual Web (2010)''（http://www.di.unipi.it/~ferragin/wsdm022.pdf）で紹介されていました．

※ 正確には，``Bigtable: A distributed storage system for structured data (2008)'' にて述べられているようです．元になっていると思われる論文 ``Bigtable: A distributed storage system for structured data (2006)''（http://www.cs.utexas.edu/users/dahlin/Classes/GradOS/papers/chang06bigtable.pdf） はダウンロードできます．

言われてみると当たり前のことなので，今まで気づいていなかったことに少し凹みました．誰かに聞いてみるというのは大切なことですね．

実験

URL 順に整列した方が圧縮しやすくなることを示すために，10,000 件の HTML 文書（376,502,866 bytes）を入力として，どのくらい圧縮できるかを調べてみました．

コマンド	ランダム順	URL 順
gzip	91,037,890（24.2%）	86,937,222（23.1%）
bzip2	74,992,057（19.9%）	65,487,403（17.4%）
xz	65,342,880（17.4%）	57,744,988（15.3%）
xz -9	58,321,728（15.5%）	55,076,976（14.6%）

URL 順にすることで，圧縮後のサイズが 1-2% 程度小さくなっています．コマンドについては，やはり xz が優秀です．

# bzip2 には復元に時間がかかるという欠点もあるので，圧縮のためにリソースを用意できるのであれば，xz を選んでおけばよさそうです．

※ 圧縮にかかる時間では gzip の方がずっと優れています．例えば，gzip が 1 分で圧縮できるとき，bzip2 は 5 分かかり，xz は 15 分かかるという具合です．

次に，アーカイブの規模が影響することを確認するために，30,000 件（1,185,806,756 bytes）に増やして実験してみました．

# 本当はもっと大きなアーカイブで試すべきなのですが，さくっと終わらせたかったので，30,000 件に抑えました．

コマンド	URL 順
gzip	256,196,569（21.6%）
bzip2	185,379,783（15.6%）
xz	162,603,260（13.7%）
xz -9	154,711,948（13.0%）

10,000 件で試したときと比べると，かなり小さくなっています．アーカイブの規模を 10 万件，100 万件と増やしていくと，もっと圧縮できそうな気がします．

※ データの偏りが影響している可能性は十分にあります．

結論

ウェブコーパスが完成した段階で，すべての HTML 文書を URL 順に整列してから圧縮しなおすという方針が有力です．とはいえ，最終段階になってから整列すると時間がかかりすぎるので，最終段階はマージだけで済むように，ブロック単位で整列しておこうと思います．

追記（2010-07-02）：30,000 件での実験結果（bzip2）が間違っていたので修正しました．

追記（2010-07-02）：64 万件のデータと 70 万件のデータで URL 順 + xz -9 の組み合わせを試してみたところ，圧縮後のサイズはそれぞれ 10.7%, 11.1% になりました．当初の想定（ランダム順 + bzip2）と比べると，60% 以下になっています．