Wavelet Trees: an Introduction
Today I will talk about an elegant way of answering rank queries on sequences over larger alphabets – a structure called the Wavelet Tree. In my last post I introduced a data structure called RRR, which is used to quickly answer rank queries on binary sequences, and provide implicit compression. A Wavelet Tree organises a string into a hierarchy of bit vectors. A rank query has time complexity is
ChordアルゴリズムによるDHT入門
Chordアルゴリズムの解説ページです。 掲載コンテンツへのリンク先を変更する可能性があるので、ブックマークやリンクは、このページにお願いします。 Chordは、DHT（Distributed Hash Table）と呼ばれる種類のPeer-to-Peerアルゴリズムです。 特に、構造化オーバレイ（Structured Overlay Network）と呼ばれるルーティング手法に特徴があります。 解説スライドでは、そもそもDHTとは何なのかという初歩的なことから、successorやpredecessor、finger tableと呼ばれるChordの有名な経路表の解説や、多くの解説ではあまり触れられることがないけれどもきわめて重要である、ネットワークの構築方法（join・stabilize）についても詳細に解説しています。 スライドのページ数は多いですが、１ページ当たり平均数秒で読めるは
The Aggregate Magic Algorithms
There are lots of people and places that create and collect algorithms of all types (here are a few WWW sites). Unfortunately, in building systems hardware and software, we in The Aggregate often have found it necessary to do relatively obscure low-level things very efficiently. Many of the tricks we've devised or collected either require assembly language coding or are not entirely portable when
べき分布する整数データの圧縮方法 - アスペ日記
今更ながら、Faster and Smaller N-Gram Language Modelsを読んでみました。 この記事については、すでにACL2011論文「Faster and Smaller N-Gram Language Models」を読んだ - EchizenBlog-Zwei やN-gram 言語モデルを圧縮するには - やた＠はてな日記で紹介されているので、自分が興味を持ったところを少しだけ。 上の紹介記事でも言及されているように、この論文では N-gram を [token, context] の形で格納しています。token と context はどちらも ID。この形でソートすると、token も context も前のデータとの差が小さくなるので、差分を取ると小さい数が多い「べき分布」になるから圧縮しやすくていいよね、という話（だと思います）。 その圧縮方法というの
A C++ Frequent Itemset Mining Template Library
Frequent Itemset Mining (FIM) is the most researched field of frequent pattern mining. Over one hundred FIM algorithms were proposed - the majority claiming to be the most efficient. To clarify this chaos and the contradictions, two FIMI competitions were organized. It not only resulted in some excellent implementations but the community also get better understanding (limits, drawbacks, advantages
Maximum subarray problem - Wikipedia
Visualization of how sub-arrays change based on start and end positions of a sample. Each possible contiguous sub-array is represented by a point on a colored line. That point's y-coordinate represents the sum of the sample. Its x-coordinate represents the end of the sample, and the leftmost point on that colored line represents the start of the sample. In this case, the array from which samples a
MapReduce Patterns, Algorithms, and Use Cases
In this article I digested a number of MapReduce patterns and algorithms to give a systematic view of the different techniques that can be found on the web or scientific articles. Several practical case studies are also provided. All descriptions and code snippets use the standard Hadoop’s MapReduce model with Mappers, Reduces, Combiners, Partitioners, and sorting. This framework is depicted in th
Story of Your Life » Blog Archive » Hopscotch Hashingを実装してみた
動機 数年前Cuckoo Hashingも知らないの？と友人から信じられないという目で見られた経験から、いつかCuckoo Hashingを超えるアルゴリズムを実装してやるという(考案してやるという程は高くない)野望を持っていました。 そこで今回はHopscotch Hashingを実装してみました。 Herlihy, M., N. Shavit, and M. Tzafrir, “Hopscotch Hashing,” Proceedings of the 22nd International Symposium on Distributed Computing (DISC), pp. 350-364, Arcachon, France, September 2008. Hopscotch HashingはCuckoo Hashingと同様、定数時間での検索を可能にするハッシュテーブ
Simple-9について解説 - tsubosakaの日記
前回に引き続き転置インデックスの圧縮を実装してみる。今回紹介するのは[2]で提案されているSimple-9というアルゴリズムである。 Simple-9は32bitのwordにできるだけ数字を詰めていくという圧縮アルゴリズムである。例えば2bitの数が16個ならんでいれば32bitで表現できる。しかし、実際は大きい数字も出現するため数字の長さの情報も格納する必要がある。Simple-9では4bitを用いて残りの28bitがどう詰められているかを表す。 28bitの表し方としては 上位bit 符号の個数 符号のビット長 0000 28 1 0001 14 2 0010 9 3 0011 7 4 0100 5 5 0101 4 7 0110 3 9 0111 2 14 1000 1 28 の9通りがあり、これがSimple-9の名前の由来となっている。 例えば ( 3 , 5 , 0 , 0 ,
「第3回自然言語処理勉強会＠東京」でCSAについて発表します - EchizenBlog-Zwei
@nokunoさんの好意で「第3回自然言語処理勉強会＠東京」でCompressed Suffix Arrayについて発表させていただくことになりました。 つきましては参考のため発表資料を以下に置いておきます。参加される方はもちろん、興味のある方はご覧になっていただけるとうれしいです。 第3回自然言語処理勉強会＠東京 : ATND 第3回自然言語処理勉強会＠東京を開催します - nokunoの日記 なお本資料は以下の皆様のアドバイスを頂きました。ありがとうございました(とくに@overlastさんには4-5時間もお付き合い頂きました。おかげさまでスライドの質が大幅アップしました。感謝)。 @overlastさん @tamago_donburiさん @tsubosakaさん @machyさん
大規模グラフアルゴリズムの最先端 - iwiwiの日記
昨日，PFI セミナーにて「大規模グラフアルゴリズムの最先端」というタイトルで発表をさせてもらいました．スライドは以下になります． 大規模グラフアルゴリズムの最先端 View more presentations from iwiwi 当日は Ustream もされており，録画された発表もご覧になれます． http://www.ustream.tv/recorded/19713623 内容の流れとしては，以下のようになっています． 導入 アルゴリズム界隈での話題 最新の研究動向 道路ネットワークでの最短路クエリ処理 基礎的な手法：双方向 Dijkstra，A*, ALT 最新の手法：Highway Dimension + Hub-Labeling Algorithm DB 界隈での話題 最新の研究動向 複雑ネットワークでの最短路クエリ処理 基礎的な手法：ランドマークを用いた最短距離推定 最
Large-Scale Graph Processing〜Introduction〜(LT版)
(※本スライドの内容は別途アップロードしている本番編から、LT用に加工した物になります。) グラフデータの大規模処理はMapReduceよりも効率の良い計算モデル が提案され、Google Pregel・Giraph・Hama・GoldenOrb等のプロジェクトにおいて実装 が進められています。またHamaやGiraphはNextGen Apache Hadoop MapReduceへ の対応が進められています。本LTでは"Large Scale Graph Processing"とはどのようなものをMap Reduceと比較して紹介するとともに、最後に各プロジェクトの特徴を挙げています。Weniger lesen
Compressed Permuterm Index - 射撃しつつ前転 改
hillbigさんに紹介してもらったCompressed Permuterm Indexをちょっと前に読んだ。Compressed Permuterm Index以前にそもそもbackward search自体が理解できなくて、refferされてる別の論文読んだりしてたらだいぶ時間がかかってしまった。 この論文に書かれているアイデアを文章で説明するなら、単語集合を*辞書順にソートしておけば*、Suffix Arrayを作ったときに、単語の先頭から末尾へジャンプするのは簡単だ、という事だ。この事実を利用して、Prefix Suffix Searchが実現できるよーと言うのがこの論文の主張。アイデア自体はすごい単純だし、実装もすごく簡単なんだけど、どんなものを食べればこんなすごいアイデアが出てくるようになるのかはさっぱりわからない。脱帽。 backward searchに関しては、というか、圧
Eigenの実対称行列の固有値問題をARPACKで解く
ハイパーお久しぶりです． 修論に追われていて，先輩方に言われた「正月はもう一週間前に終わった」という言葉をかみしめています (とてもにがい)． 今日は，ARPACK を使って Eigen の実対称行列の固有値・固有ベクトルを求めるために薄いラッパーを書いたので，ご紹介いたします． beam2d/arpaca - GitHub 基本的な使い方は README に書いてあります． 求めたい固有値の数と種類 (実数 (or 絶対値) の意味で大きい (or 小さい) 方からいくつか，あるいは次数の意味で両側から合わせていくつか) を指定して，行列を渡すだけです． 行列は掛け算にだけ用いられるので，Eigen の Expression Template を直接渡すこともできます． また README の 2 番目の例のように，対象となる行列をベクトルにかける演算を自分で書いて渡せば，その固有値を求
marisa-trie における rank/select の実装 - やた＠はてな日記
概要 rank/select は簡潔データ構造（Succinct Data Structures）の核になる関数です．ビット列の k ビット目までに含まれる 0, 1 の数を求めるのが rank，k 番目の 0, 1 の位置（Index）を求めるのが select であり，ビット列の密度（1 の割合）によって，いろいろな実装があります． marisa-trie では，0, 1 の割合が極端に偏らないビット列を想定するとともに，32-bit 環境における性能の劣化を防ぐために，64-bit 整数を使わないようにしました．そのため，ほとんどの部分は以前に開発したライブラリからの流用ですが，新しく書き直した部分もあります．ちなみに，索引のサイズはビット列の長さ n bits に対して (1/4)n bits です． 基本 ビット列の実装 ビット列の格納には 32-bit 整数の配列を使っています
C++: 編集距離を求めるアルゴリズム
編集距離(edit distance)とは二つの文字列がどの程度異なっているかを示す数値であり、レーベンシュタイン距離(Levenshtein distance)を指すことが多い。文字の挿入、削除、置換それぞれを一つの操作として必要な操作の最小数を求めるものだ。例えば、kittenとsittingの編集距離を求める場合、下記のように3回の操作でkittenをsittingに変更できるので編集距離は3となる。 1. sitten (k を s に置換） 2. sittin (e を i に置換） 3. sitting (g を挿入) そこで今回は編集距離を求める複数のアルゴリズムについてC++で実装してみた。 動的計画法 編集距離を求めるもっとも一般的なアルゴリズムは、動的計画法(dynamic programming)だろう。計算時間はO(mn)であり、手軽だ。C++で書いたコードを下に示
話題の新技術、簡潔データ構造の入門用資料をまとめてみた - EchizenBlog-Zwei
最近私の周辺で簡潔データ構造に興味を持つ人が増えてきた。簡潔データ構造といえばGoogle日本語入力でも使われている話題の新技術。自然言語処理界隈で機械学習の次にブームになるのはこれだ！と個人的に思っている。 というわけで入門用の資料をまとめてみた。 簡潔データ構造では、すべての基礎である簡潔ビットベクトルがあって、その上に応用として簡潔木(LOUDSなど。Google日本語入力で利用されている)、簡潔文字列(ウェーブレット木など。FM-Indexに利用されている)がある。最近ではこれらより複雑なデータ構造に対する簡潔構造も研究されている。 ということをふまえて以下の資料を読むと良い。 Efficient dictionary and language model compression for input method editors Taku Kudo et al. Google日本語
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Google Code Archive - Long-term storage for Google Code Project Hosting.
http://hpc.isti.cnr.it/
定兼 邦彦 (Kunihiko Sadakane) - 簡潔データ構造講義資料 - researchmap