wavelet tree - 明日ではないから

圧縮検索で使われる技術wavelet treeをテンプレートライブラリとして書いてみました。 →を参考にしてみました。高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」 元となる記事が大変興味深かったのだけど、どうもサンプルコードが複雑すぎるのと、僕の解釈が悪いのか、記事中の説明がコードとつじつまが合わないところがあったので、自分で実装してみたしだい。 記事中ではハフマンコード化の話があるのだけど、あくまでそれは最適な圧縮率を出すための理論にしか過ぎなくて、 頻度の順番で文字をソートしておいて、文字ごとにその文字を１にしたビット列を格納していったほうが素直だろう。(元記事中は該当文字を0としたが1としたほうが操作しやすいと思う) たとえば、文字列T = "abccbbabca"があったときその頻度は'b','c','a'の順番になる。このとき各文字ごとにビット列を作ってい