読者です 読者をやめる 読者になる 読者になる

STVF符号

VF符号はvariable length to fixed length codeの事で,可変長の文字列に固定長の符号を割当てる形式のこと.

符号化は割当て領域(文字列)と符号語それぞれについて可変長にするか,固定長にするかで4パターンの符号化が考えられる.

FV, VV符号は圧縮できる反面,符号化した文字列上で元の文字列の切れ目がわかりにくいなどの問題がある.
VF符号はあまり日の目を見なかったが,再評価して実は使えるよというのが今回読んだ論文の内容.

分節木

前提知識として,割り当て領域(文字列)を全て表した木を考える.簡単のため,全ての文字列についてその他の文字列の真のprefixになっていないとする.文字列と符号語は一対一対応するため,この木の葉について符号語がそれぞれ一対一対応する.
iから始まる文字列T[i..]に対応する符号語はこの木を根から順に辿っていって,葉に到達した時の符号語となる(深さをjとするとT[i..i+j-1]が対応する).
直感的に考えて,よい分節木とは文字列T中によく出現する長い文字列を表す木である.ただし,最適な分節木を計算することはとてもむずかしい.

STVF符号

[1] Takuya Kida: Suffix Tree Based VF-Coding for Compressed Pattern Matching. DCC 2009: 449
[2] Shmuel Tomi Klein, Dana Shapira: Improved Variable-to-Fixed Length Codes. SPIRE 2008: 39-50
STVF符号はSuffix Treeを枝刈りすることで作られる分節木.
ほぼ同時期に独立して同じアイディアの方法が提案されたそうだ(自分は[1]しか読んでない).
[1]について日本語の論文もある.
STVF符号 : 頻度刈り込み接尾辞木を用いた効率よいVF符号化 : HUSCAP
Suffix Tree(ST)は全てのsuffixを格納した木で,葉はユニークなsuffixを,また全ての内部ノードは入力文字列中Tの部分文字列を表している.内部ノードに対応する文字列はそのノードから導出する葉の数だけT中に出現する.
STVFはSTの根とその子供のノードを初期状態の木として,葉の数が2^l以下(lは符号長)となる間以下の要領でノードを追加していく.
現在の状態の木の葉から,もっとも多くの葉を導出する内部ノードを選択し,その子供の数を追加しても木のサイズが2^lを超えないなら追加.

これだけ.こうするとSTから高頻度の部分文字列を優先的に抽出した分節木が得られる.
実験ではハフマン符号と比較した時,アルファベットサイズが大きい時(小さすぎない時)STVF符号のほうがよい圧縮率を示している.

STVF符号の改良

[3] Takashi Uemura, Satoshi Yoshida, Takuya Kida, Tatsuya Asai, Seishi Okamoto: Training Parse Trees for Efficient VF Coding. SPIRE 2010: 179-184
STVF符号は沢山出現する部分文字列ほど,符号化時に符号化されやすいという思想から成り立っている.しかし,そうとは限らない例も存在する.
例えば,今T1 = aaaabbbb,T2 = bbbbccccという文字列がそれぞれT中に出現しSTVFにもT1, T2を表すノードがあるとする.
この時T2がaaaabbbbccccの形でしか出現しない時,左から順にT1ccccと符号化されたとすると,T2は符号化でまったく使われない符号語となる可能性もある.
このように部分文字列の頻度と符号化されるときに実際に符号化されるかどうかはまた別問題である.
この論文ではこのような問題を学習アルゴリズムで改善しようとしている.

感想

VF符号化はシンプルでとてもわかり易く,また実験的にも良い結果が示されていて,好感が持てる.
ただSTVFは入力文字列のSuffix Treeが必要なため,大規模なデータに対して適用するのが難しいのが難点.
どうにかオンラインにすることができればなかなかに面白いことになるなのかも.