完備辞書（簡潔ビットベクトル）の解説 - アスペ日記

2014/02/01 66 users 簡潔ビットベクトル trie LOUDS アスペ日記 完備辞書

以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。この「簡潔ビットベクトル」「... 続きを読む

ウェーブレット行列の省メモリ構築方法 - アスペ日記

2013/05/05 54 users 配列 アスペ日記 領域 知識 中学生以上

ウェーブレット行列の構築方法について。前に書いた記事とは違って、「ウェーブレット行列大好き！」って人*1以外が読んでもあんまり益がない記事だということをあらかじめ書いておく。内容としては、相変わらず中学生以上の知識が必要ということはないけれど。 上の記事で書いたように、ウェーブレット行列は 2進数の基数ソートと同じような感じで構築できる。で、基数ソートをするには、元の配列と同じだけの領域が必要にな... 続きを読む

中学生にもわかるウェーブレット行列 - アスペ日記

2013/03/03 440 users アスペ日記 中学生

id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 ”The Wavelet Matrix”」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。日本以外ではあんまり来ていません。理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」と... 続きを読む