簡潔データ構造 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) 木の検索 詳解
LOUDS(Level-Order Unary Degree Sequence)を調べたのでメモ - EchizenBlog-Zwei
最近よく目にするLOUDS(Level-Order Unary Degree Sequence)というのが気になっていたので調べた。実は最初に提案されたのは1989年。結構昔からあったと知ってびっくり。 Space-efficient Static Trees and Graphs G. Jacobson, 1989 LOUDSというのは木構造を表現するデータ構造をひとつ。単純に考えると木構造を実装するにはノードを表すオブジェクトに子ノードへのポインタを持たせる、というものが思いつく。この実装はノードへのアクセスは効率的にできるけれどメモリをたくさん使ってしまう(O(NlogN))。 そこでノードへのアクセス効率をあまり悪くせずに、省メモリな木構造が欲しい。これを実現したのがLOUDS。LOUDSはノードの追加や削除が起きないstaticな木構造にしか使えないが、必要なメモリはO(N)で済
情報系修士にもわかるLOUDS - アスペ日記
一回でわかりやすく書くのは難しいので、簡潔データ構造 LOUDS の解説（全12回、練習問題付き）というシリーズにまとめました。 (2014/01/26) 古い内容を削除しました。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
