Top-k文書列挙問題 - DO++
いろいろとありまして去年読んだ論文で面白かったものランキングとか書けなかったのが残念ですが、もしあげるとしたら次の論文は入れると思います（知ったのは年明けだったけど）。 "Space-Efficient Framework for Top-k String Retrieval Problems", FOCS 2009, Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter (pdf) 扱っているのは次のような問題です（説明のため本来のと言い換えています） n個の葉からなる木が入力として与えられ，各葉には色（1以上d以下の整数とします）が与えられています． この時、木中の任意の節点と正整数kがクエリとして与えられたときに、その節点の子孫の中で出現回数が大きい色を順にk個答えよという問題です。 簡単に思いつくのは，各節点に適当な個数(d)の答えをあ
Tx: Succinct Trie Data Structure
English 概要 TxはコンパクトなTrieを構築するためのライブラリです．従来のTrieの実装（darts等）に比べ1/4〜1/10の作業領域量で辞書を保持することができ、数億〜十億キーワードなど大規模な辞書を扱うことが可能です．Trieは文字列からなるキー集合を処理するデータ構造で、キーが辞書に含まれているかのみではなく、キーのPrefixが含まれているかを高速に求めることができます．内部データ構造にはSuccinct Data StructureであるLevel-Order Unary Degree Sequence (LOUDS)を利用しています． ダウンロード Txはフリーソフトウェアです．BSD ライセンスに従って本ソフトウェアを使用,再配布することができます. tx-0.12.tar.gz: HTTP Archives tx-0.11.tar.gz: HTTP tx
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Native Libraries Guide