[B! LOUDS] manabouのブックマーク

「木構造と自然数の重複あり集合は等価だよね」というはなし - EchizenBlog-Zwei

「木構造と自然数の重複あり集合は等価だよね」というはなしをする。簡潔データ構造な人向けに言うとLOUDSの話。とはいえこの記事は特に簡潔データ構造の知識を要求しない。データ構造とか情報量とかに興味がある人全般を対象としている。 ※簡潔勢にとっては既知な話のはずなのであえて読む必要はないです。まず結論から述べる。以下のような幅優先で番号を振った木構造を考える。親 → 子 (1) → (2, 3) (2) → (4) (3) → (5)この木構造は以下の重複あり集合によって表現することができる。 { 2, 4, 5, 5, 5 }これだけ書くとなんのこと？と思われるかもしれない。そこでこれから2つのことを説明する。ひとつは「何故、木構造が自然数の重複あり集合で表現できるか」、もうひとつは「重複あり集合で表現することに何の意味があるか」ということ。何故、木構造が自然数の重複あり集合で表現

manabou 2014/01/31

リンク

jumbled pattern matchingというのを知った - EchizenBlog-Zwei

Binary Jumbled Pattern Matching via All-Pairs Shortest Paths(http://arxiv.org/pdf/1401.2065v1.pdf)という論文がLOUDS論文をreferしていて興味があったので読んでいた。jumbled pattern matchingという問題の時間計算量を改善したよ、という話だった。不勉強ながらjumbled pattern matchingという言葉を知らなかった(もしくは忘れていた)。幸い、この論文にどういう問題であるか解説があったので容易に理解することが出来た。なので忘れないうちにメモしておく。 jumbled pattern matchingというのはマッチさせる単語の文字の順番が入れ替わっていてもマッチさせるパターンマッチ。つまりabracadabraに対してabraだけでなくbaraもマッ

manabou 2014/01/14

リンク

Perlで完備辞書(Fully Indexable Dictionary)のモジュールを書いた - EchizenBlog-Zwei

ウェーブレット木/行列など「高速文字列解析の世界」で扱っているデータ構造やアルゴリズムは完備辞書(Fully Indexable Dictionary)を基本的な道具として用いるものが多い。とはいえ実用的な完備辞書を一から作るのは大変なので、高速文字列本を読んで「ちょっとウェーブレット行列を作ってみようかな」と思ったとしても完備辞書は適当なモックで済まさないといけなかったりして面白くない。というわけでPerlモジュールを書いた。 https://github.com/echizentm/FullyIndexableDictionary 例えば以下のような感じ。これでLOUDSもウェーブレット行列もさくさく作れますね！ use FullyIndexableDictionary; my $fid = FullyIndexableDictionary->new(); $fid->set(1,

manabou 2013/02/16

リンク

簡潔データ構造 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) 木の検索詳解

manabou 2012/04/22

リンク

たぶん30分でよくわかるLOUDS入門 - EchizenBlog-Zwei

IME本の効果でLOUDSの認知度が高まってきた気がする。が、一方で難しいという意見もチラホラある様子。というわけでLOUDSをどこまでわかりやすく説明できるか？ということに挑戦したくなったので記事を書いてみるよ。 LOUDSというのは木を表すデータ構造。木というのは以下のようなものを想像すればよい。この木を表すデータ構造を作りたい。単純に考えると各ノード毎に子ノードのIDを持たせておけばよい。つまり 0 => {1, 4, 5} 1 => {2, 3} 2 => {} 3 => {} 4 => {} 5 => {6} 6 => {7}というようなものを考える。ここで各IDと子ノード数を各1バイトで管理したとして 0 => {1, 4, 5} # 1 + 3 = 4バイト 1 => {2, 3} # 1 + 2 = 3バイト 2 => {} # 1 + 0 = 1バイト 3 => {}