[B! algorithm][programming] t-wadaのブックマーク

t-wada id:t-wada

algorithmとprogrammingに関するt-wadaのブックマーク (2)

確率的データ構造を使って巨大な集合を定数メモリで近似しよう
巨大な集合に対して、定数メモリ&定数時間で近似値を計算できる、確率的データ構造の紹介スライドです。本スライドは、株式会社エフ・コードの社内勉強会(2018/08/30)にて使用されたものです。
t-wada 2018/09/03
Bloom Filter, Count-Min Sketch, HyperLogLog などの確率的データ構造をとても分かりやすく説明している資料

algorithm

programming
リンク
トライ (データ構造) - Wikipedia
"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ木トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語
t-wada 2011/10/04
"Trie という名称は retrieval が語源であるため、tree と同じ発音を用いる。しかし、ツリー構造との混同を避けるために「トライ」という読み方を奨励する人もいる。日本語では、「トライ木」という呼び方がほぼ定着

algorithm

programming
リンク
1