[B! WaveletMatrix] xefのブックマーク

wavelet行列で高速な「もしかして友だち？」検索 | 株式会社サイバーエージェント

業務経歴： Sierでのソフトウェア開発・大手メディアでのサービス運用を経て2012年サイバーエージェント入社。アメーバ事業本部コミュニティサービスの開発責任者を経て、現在はアドテクスタジオで広告配信技術に注力。好きな分野はグラフ探索とチューリングマシン。ソーシャルサービスでは、ユーザ間のつながりやユーザ同士の類似性がとても重要です。つながりの近いユーザや自分と似ているユーザを「もしかして友だち？」とサジェストすることでユーザ間のつながりを伸展させることができます。そこで、ユーザの「つながり」具合が似ているユーザを「友だちかもしれないユーザ」としてサジェストを行うことを考えました。しかし「つながり」のデータというのはユーザ数のベキ乗であるため、容量が大きくなりやすい性質があります。即ち、「つながり」類似度の算出には時間がかかる、ということです。この「つながり」類似度算出

xef 2014/05/19

WaveletMatrix

リンク

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

ウェーブレット行列の構築方法について。前に書いた記事とは違って、「ウェーブレット行列大好き！」って人*1以外が読んでもあんまり益がない記事だということをあらかじめ書いておく。内容としては、相変わらず中学生以上の知識が必要ということはないけれど。上の記事で書いたように、ウェーブレット行列は 2進数の基数ソートと同じような感じで構築できる。で、基数ソートをするには、元の配列と同じだけの領域が必要になる。だが、ウェーブレット行列のように各段階でのビット列だけが必要であるなら、その領域は必要ない。ウェーブレット行列でも、ウェーブレット木のノードのようなものを持っておくことで、配列長のオーダーでなく、文字の種類のオーダー（一般的に配列長よりずっと小さい）だけの記憶領域で構築できる。ぼくのウェーブレット行列ライブラリである wavelet-matrix-cpp や、 id:echizen

xef 2013/05/05

WaveletMatrix

リンク

ウェーブレット行列を実装した - 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>

xef 2013/03/08

WaveletMatrix

リンク

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

id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。日本以外ではあんまり来ていません。理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。ウェーブレット行列でできること主となる操作は、文字列に対する定数時間の rank() と select()*2 です。 rank() は、「文

xef 2013/03/03