定兼 邦彦 (Kunihiko Sadakane) - 簡潔データ構造講義資料 - researchmapresearchmapは、日本の研究者情報を収集・公開するとともに、研究者等による情報発信の場や研究者等の間の情報交換の場を提供することを目的として、国立研究開発法人科学技術振興機構（JST）が運営するサービスです。
簡潔データ構造超入門V 〜LOUDSというメモリ効率のよい木構造の話(本編)〜 - EchizenBlog-Zwei
前回に引き続きLOUDSという簡潔木の話。前回準備したunaryの簡潔ビットベクトルを使って親ノード、子ノードへのアクセスが効率的に可能な木構造であるLOUDSの話をする。 前回までの記事： 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei 簡潔データ構造超入門IV 〜LOUDSというメモリ効率のよい木構造の話(準備編)〜 - EchizenBlog-Zwei さて、LOUDS(Level Order Unary Degree Sequence、ラウズ)は木構造を表すデータ構造のひとつ。データサイズを小さく抑えつつ
簡潔データ構造超入門IV 〜LOUDSというメモリ効率のよい木構造の話(準備編)〜 - EchizenBlog-Zwei
今回はLOUDS(Level Order Unary Degree Sequence, ラウズ)というデータ構造の話。LOUDSは木構造の簡潔データ構造版、簡潔木と呼ばれているものの一種。 簡潔木には他にBP(Balanced Parentheses)やDFUDS(Depth First Unary Degree Sequence)というものがある。BPやDFUDSは部分木の大きさを効率的に計算できるという利点がある。実際は各ノードから親ノード、子ノードへのアクセスが効率的に出来れば十分な場合も多いので、そういう場合はLOUDSが活躍する。 今回はそんなLOUDSのお話の準備編。LOUDSに必要なデータ構造を用意するところまで。 前回までの記事： 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な
簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei
前回までで簡潔ビットベクトルというデータ構造を実装した。簡潔ビットベクトルとは普通のビット列に少しの追加データを持たせることでrank/selectという2つの操作が可能にしたもの。そしてrank/selectとはそれぞれ以下の操作のこと。 rank(x) : x番目のビット以前(xの位置を含む)の立っているビットの数 select(i): i番目に立っているビットの位置今回は簡潔ビットベクトルを利用して転置インデックスを効率的に実装してみる。 前回までの記事： 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 転置インデックスとは検索エンジンに用いられるインデックスで apple 1, 3 orange 1, 2, 4, 6のように各単
私のブックマーク ： 簡潔データ構造
田部井靖生（科学技術振興機構 ERATO湊離散構造処理系プロジェクト研究員) はじめに 近年、Web技術や計測技術の発展により言語やゲノムデータは大規模化しています。従来のデータ構造は大規模データを扱うにはサイズが大きくメモリに載らない、 しかし、圧縮するとランダムアクセスをすることができないという欠点があります。 簡潔データ構造とはデータを小さく保存かつ高速な操作が可能なデータ構造です。 近年、集合、文字列、木、グラフデータを扱うための簡潔データ構造が提案され注目を集めています。 私たちの身近なアプリケーションとして、Google日本語入力では簡潔木LOUDSの実装が使われ、実際に使われはじめています。 また、有志によるそれらを解説したサイトやライブラリなども利用可能になりつつあります。 そこで、このページでは簡潔データ構造を用いた研究開発のためのいろいろなリソースを紹介します。 解説記
簡潔データ構造超入門VI 〜これまでのまとめと集合の簡潔構造〜 - EchizenBlog-Zwei
今回は集合の簡潔構造について話をする。今回で簡潔構造の初歩的な話は一段落となるので、いままでの話をまとめつつ集合の簡潔構造とは？どういうことに使えるのか？という話をする。 集合の簡潔構造は大変重要で、ここを理解すれば簡潔構造の基礎はだいたいOKといえる。 前回までの記事： 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei 簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜 - EchizenBlog-Zwei 簡潔データ構造超入門IV 〜LOUDSというメモリ効率のよい木構造の話(準備編)〜 - EchizenBlog-Zwei 簡潔データ構造超入門V 〜LOUDSというメモリ効率のよい木構造の話(本編
簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造(Succinct Data Structure)の魅力を紹介する本シリーズ。前回の記事では疎ベクトルを簡潔データ構造を使って効率的に実装する方法を紹介した。 前回の実装ではビットベクトルのサイズの上限が256だった。今回はこれを拡張して任意の大きさを扱える簡潔ビットベクトルの実装例を紹介する。 また前回はrank()を定数時間で実現する方法を紹介した。今回はこれを使ってselect()を二分探索(O(logN))で実装する。 以上の2つの改善によってビットベクトルのサイズに制限がなくrank()/select()の双方を備えた、実用性のある簡潔ビットベクトルが実現できる。 前回の記事： 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei サイズに制限のないビットベクトルは前回実装した簡潔ビットベクトルのsbvクラスを用いて実装する
簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造は各種操作を高速に保ったままでデータサイズを情報理論的な下限近くまで圧縮できる。大規模データを扱うことの多くなってきた現在、特に注目を集めている技術である(※個人的な見解です)。 しかし有用性とは裏腹にまとまった教科書等がないこともあり入門者に対して敷居が高いようにも感じられる。そこで本記事では簡潔データ構造の基本であるビットベクトルに対する簡潔構造の実装方法をC/C++のコードを交えて解説してみる。 ビットベクトルに対する簡潔構造は、単純には疎ベクトルを表現するのに利用することができる。よって本記事でも簡潔ビットベクトルを実装し、疎ベクトルを実現してみようと思う。 今回は疎ベクトルとして値がint(4byte)の256次元のベクトルを考える。ただし疎ベクトルなので256次元のうちいくつかの次元にしか値が入っていないものを仮定する。例えば v[5] = 10 v[100] =
簡潔データ構造(Succinct Data Structure)で最初に読むと良さそうな論文 - EchizenBlog-Zwei
最近、簡潔データ構造(Succinct Data Structure)まわりの論文を色々読んでいる。その中で良さそうなものをいくつかピックアップしてみた。まだ調査中なので他に良いものがあったら教えてもらえると嬉しいです。 (1) Space-efficient Static Trees and Graphs(link) G. Jacobson; IEEE1989 まずはLOUDS論文。簡潔データ構造の元祖なので最初に読むと良さげ。 (2) Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees and Multisets(link) R. Raman, V. Raman, and S. S. Rao; SODA2002 簡潔ビットベクトルは通常n+o(n)なんだけど、これをnH0+o(n)にしたよ、
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
