ウェーブレット行列を実装した - hirokazu1020の日記

元のデータに対して十分小さいサイズでありながら各種操作を高速に処理でき、文字列のみならず2次元データやグラフデータまで表現できるというウェーブレット行列を実装してみた。「高速文字列解析の世界」とかブログとか読んでやっとのことで実装した。 ウェーブレット行列の各操作のオーダーの表記では、文字集合のサイズをσ、文字列長をnとしている。 2014/8/25:プログラム修正 inline int popCount(unsigned int x){ x = (x>>1 & 0x55555555)+(x & 0x55555555); x = (x>>2 & 0x33333333)+(x & 0x33333333); x = (x>>4 & 0x0f0f0f0f)+(x & 0x0f0f0f0f); x = (x>>8 & 0x00ff00ff)+(x & 0x00ff00ff); return (x>