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

簡潔データ構造の入門の入門 - EchizenBlog-Zwei
最近、簡潔データ構造(Succinct Data Structure)がじわじわ人気が出てきているように感じるので入門の入門、くらいの記事を書いておく。この記事では簡潔データ構造において最も基本的なデータ構造である完備辞書(Fully Indexable Dictionary)について説明する。新しい概念が出てきた時に気になるのは「どうやって実現するのか」「それができると何が嬉しいのか」という2点だと思う。前者についてはこの記事(http://d.hatena.ne.jp/takeda25/20140201/1391250137)がわかりやすいのでここでは述べない。この記事では「完備辞書があると何が嬉しいのか」について説明する。完備辞書とは完備辞書はrankおよびselectという操作が定数時間で実行できるビット列のこと。rank(i)はi番目のビットより前にいくつ1があるかを返
emonkak 2014/05/17
algorithm
リンク
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もマッ
emonkak 2014/01/13
algorithm
リンク
ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix" - EchizenBlog-Zwei
久しぶりに論文を読んだ。 http://www.dcc.uchile.cl/~gnavarro/publ.html The Wavelet Matrix Claude & Navarro; SPIRE2012 "The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。機能としてはウェーブレット木と同一でデータ列に対するaccess,rank,selectを提供する。しかし実装は既存手法と比べて効率的でしかも簡単になっている。これまでにウェーブレット木の実装としてはノードをポインタでつないだ普通の木として実装する方法(Standard Wavelet Tree. 論文のAlgorithm 1)と、木の階層ごとにノードをつなげた配列で表現する方法(Levelwise Wavelet Tree. 論文
emonkak 2013/02/23
algorithm

wavelet
リンク
1