著者情報
-
データ圧縮やデータ構造、またそれらの応用としての自然言語処理、機械学習に興味があります。
http://hillbig.cocolog-nifty.com/(blog)
※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です
執筆記事
-
2006/07/05高速な算術圧縮を実現する「Range Coder」
本記事では全体のサイズが最小となる算術圧縮を高速に実現するRange Coder（以下RC）を紹介します。算術符号は圧縮率が高い反面、ビット単位の演算処理が大量に発生するため、符号化/復号化ともにHuffman符号に比べ遅いという問題点があります。今回紹介するRCは算術符号の処理をバイト単位で行うことで高速な処理を可能とします。
-
2006/05/10高速に符号／復号を行える最小冗長符号「Canonical Huffman Code」
本記事ではデータ圧縮の基盤である最小冗長符号を実現するCanonical Huffman Code（以下、CHC）を紹介します。最小冗長符号は、各文字の出現確率が分かっている場合にそのデータを最小長で表現可能な符号です。CHCは良く知られたHuffman符号の一種ですが、木を用いずに表引きのみで処理を行うので高速に符号/復号が可能です。また、符号の長さ制限をつけた場合の最適な符号を求めるreverse package merge法も紹介します。
-
2006/01/26高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
本記事では大規模なデータを扱うためのデータ構造であるwavelet tree（WT）を紹介します。WTは文字列が与えられた時、文字cのi番目の出現位置や、文字cの位置pまでの出現回数を定数時間で答えるデータ構造です。作業領域量は元テキストの約2倍です。WTはsucBVの延長上にあるデータ構造であり、WTを用いることで圧縮索引やsuccinct data structureなどを実装できます。
-
2006/01/18
高速かつ省メモリなbit vector「sucBV」を作る
本記事では大規模なデータを扱うためのデータ構造である操作付きBit Array (SUCcinct Bit Vector: sucBV)を紹介します。sucBVは、vectorと同様に2値配列情報を保存する他にrank, selectと呼ばれる二つの操作を定数時間でサポートします。作業領域量はvectorの約3倍です。sucBVを用いることで、圧縮索引やsuccinct data structureなどを実装できます。
