[B! data_structure] InoHiroのブックマーク

InoHiro id:InoHiro

data_structureに関するInoHiroのブックマーク (2)

簡潔データ構造 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) 木の検索詳解
InoHiro 2017/08/23
data_structure
リンク
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。ありがたい。感銘を受けたので、この本を教材に友達と2人勉強会をした。この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。しかし、いざやってみるといろいろと難しい。次のようなところでひっかかるようだ。例のサイズが小さく、イメージを喚起するのが難しい。最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。単語終端について言及がないので、どのノードが単語を表しているかがわから
InoHiro 2012/02/19
丁寧なダブルアレイの説明

algorithm

data_structure
リンク
1