hirokistのブックマーク - はてなブックマーク

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

データ構造
リンク
簡潔データ構造 LOUDS の解説（全12回、練習問題付き）
「日本語入力を支える技術」（通称「徳永本」）や「高速文字列解析の世界」（通称「岡野原本」）で紹介されている LOUDS というデータ構造を、12回に分けて解説しました。友達に教える時に使ったもので、練習問題付きです。実際に紙に書いてやってみるとわかりやすいと思います。詳解 LOUDS (1) LOUDS とは詳解 LOUDS (2) ビット列を作ってみる詳解 LOUDS (3) 0番ノード詳解 LOUDS (4) ビットの意味詳解 LOUDS (5) 木構造の復元詳解 LOUDS (6) インデックスでノードを表す詳解 LOUDS (7) ノード番号からインデックスを得る詳解 LOUDS (8) インデックスからノード番号を得る詳解 LOUDS (9) 子ノードから親ノード詳解 LOUDS (10) 親ノードから子ノード詳解 LOUDS (11) 木の検索詳解
hirokist 2013/01/13
データ構造
リンク
logsumexp は人類の黒歴史 - アスペ日記
あえて言い切る。ここでは主に計算量について言っているので、スクリプト言語でデモ的なものを作るような場合は除く。この記事では C++ を使って書く。 logsumexp でどのように計算の量が増えるかはunnonouno: logsumexpとスケーリング法に詳しい。ちょっと引用。 linear-chain CRFのパラメタ推定に必要なのは対数尤度関数の微分です．これの計算に必要なのが，前向き・後ろ向きのスコアαとβです．時刻t（系列上での位置）とラベルiに対する前向きスコアαは，以下の式で計算されます．fは特徴ベクトル，wは重みベクトルです．この後の話の流れは、掛け算いっぱいで大変！オーバー／アンダーフローしちゃうよ！じゃあ log の世界で扱えばいいんじゃね？足し算もあるよ！どうするの？「logsumexp〜」すごい！これでオーバーフローしないし安心だね！でも重い
hirokist 2012/06/26
logsumexp
リンク
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。ありがたい。感銘を受けたので、この本を教材に友達と2人勉強会をした。この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。しかし、いざやってみるといろいろと難しい。次のようなところでひっかかるようだ。例のサイズが小さく、イメージを喚起するのが難しい。最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。単語終端について言及がないので、どのノードが単語を表しているかがわから
hirokist 2012/02/24
データ構造
リンク
1