Twitter本文と言及URLの圧縮

最近、Twitterのデータを収集しています。APIで取得したtweet本文や、そこから抽出したURLを片っ端からDBに保存していくと件数が莫大になるので、ディスクスペースを極力節約したいところですが、個別のtweet本文や言及URLは短い文字列なので、普通に1件ずつgzip等で圧縮してもほとんど意味がないか、オーバーヘッドが出て逆効果になってしまいます。

そこで、収集済みのサンプルデータを元にハフマン木を作っておき、それを共通利用してtweetを圧縮してみました。

用意したのは、英語ユーザ/日本語ユーザ/韓国語ユーザ各1000人のtweetサンプルをベースにしたハフマン符号と、tweet本文から抽出したURL文字列をベースにしたハフマン符号の4種類です。

頻度表は次のようになりました。

char (en)	freq (en)	char (ja)	freq (ja)	char (ko)	freq (ko)	char (url)	freq (url)
(space)	1348393	(space)	272693	(space)	1153658	.	117835
e	699224	t	190132	.	223743	/	117587
t	608528	い	142493	t	133262	t	104686
o	533925	/	140918	이	109998	l	96779
a	501332	の	125271	o	106729	i	92201
i	448181	i	124956	e	100288	b	76967
n	421090	o	124626	/	97184	o	72043
s	379668	a	123180	i	90800	m	67298
r	368706	。	113045	a	83993	e	66610
h	296416	e	107796	@	79703	y	65559
l	284100	な	104583	다	76449	c	56271
d	212750	て	92110	n	75734	a	53425
u	196833	た	90285	는	71036	r	49960
c	185527	h	90026	h	66954	w	40989
m	182875	で	88902	p	61647	n	40891
p	170037	し	83075	r	58089	s	39480
...	...	...	...	...	...	...	...

(追記: URLから"http://"は除去済み)

現在、Twitterではbit.lyが良く使われるので、'b','i','t','l','y'のURL使用文字としての出現頻度が高くなっていることが表から分かります。この偏りは今後変わるかもしれません。

これらの固定ハフマン符号を使って、実際にtweet本文や言及URLを圧縮してみたところ、次のような結果になりました。

符号ベース	圧縮対象	圧縮率
英語tweet	英語tweet	61.56%
英語tweet	スペイン語tweet	62.71%
英語tweet	ポルトガル語tweet	65.32%
英語tweet	インドネシア語tweet	66.93%
日本語tweet	日本語tweet	47.64%
韓国語tweet	韓国語tweet	48.12%
URL	URL	68.93%

英語tweetをベースにしたハフマン符号は、西欧言語に対しては大体共通して有効でした。日本語と韓国語が50％を切る優秀な圧縮率なのは、圧縮前の文字列がUTF-8なので、1文字あたり3バイト使われている確率が高くて非効率だったからだと思います。

このように、サンプルデータを元にした固定ハフマン符号を使う方法は、1件あたりの文字数が少ないtweet本文やURLの圧縮において有効だと分かりました。さらに、毎回ハフマン木を作らなくて良いので、パフォーマンス的にも非常に有利だと思います。