2010年2月19日のブックマーク (3件)

  • 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)の答えをあ

    Top-k文書列挙問題 - DO++
    takahi-i
    takahi-i 2010/02/19
    nlp
  • Native Libraries Guide

    takahi-i
    takahi-i 2010/02/19
    hadoop native libralies
  • 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

    takahi-i
    takahi-i 2010/02/19
    LOUDS