最近のtrieの話（xbwなど） - Preferred Networks Research & Development
ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。 今回はtrie（トライ）の最近の話をしたいと思います。 trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS（Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。 同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下
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 整数の配列を使っています
Topcoder
Topcoder is a crowdsourcing marketplace that connects businesses with hard-to-find expertise. The Topcoder Community includes more than one million of the world’s top designers, developers, data scientists, and algorithmists. Global enterprises and startups alike use Topcoder to accelerate innovation, solve challenging problems, and tap into specialized skills on demand.
大規模トライ用のライブラリを開発中 - 2010-01-30 - やた＠はてな日記
Succinct なトライをサポートする sumire-tries があるにもかかわらず，ここしばらく，大規模なトライ用のライブラリを開発しています．sumire-tries を何度も修正したのは，開発の途中でいろいろと気づいて，それらを反映させていたからです．いわゆるオマケという感じです． 今回の開発目的は，sumire-tries より大規模なトライを扱うことです．そして，新しいライブラリの特徴は，以下のようになっています． 64 ビット環境に最適化 32 ビット環境でも使えますが，本来の性能は出ません． トライのサイズ制限なし ノード数の上限は 2^38 = 2700 億です． 一時ファイルの利用 主記憶容量を超えるサイズのトライを構築できます． 構築するだけなら主記憶容量を超えても問題ありませんが，メモリ上に展開できないため，検索するときに mmap() を使うことになります．おそ
Succinct なトライの実験に用いたソースコード - やた＠はてな日記
いつものように，Google Code にアップロードしました．プロジェクトの名前は sumire-tries になっています．名前を sumire にした理由は，なんとなくです…． ドキュメントは準備中ですが，基本的な使い方は後述します． Google Code Archive - Long-term storage for Google Code Project Hosting. 右のメニューにある Featured downloads からアーカイブをダウンロードして，よくある手順を踏めば動作確認できます． ./configure make make check ヘッダのみで構成されているため，make install でインストールしなくても，ヘッダを格納しているディレクトリ（include/）をコピーすれば使えます． トライを構築する手順は，以下のようになっています． 基礎となる
2009-10-29 - やた＠はてな日記 Succinct なトライの実験
実験の概要 Succinct な木構造を用いてトライを実装すると，コンパクトな辞書を構築できます．しかし，検索速度の面では，その他のデータ構造に劣るという欠点を持ちます．そこで，いくつかのトライを C++ で実装し，ちょっとした性能テストをしてみました．今回のテストで実装したトライは，以下のとおりです． BasicTrie 各ノードに「一つ目の子ノードの ID」，「兄弟ノードが存在するか」，「ラベル」を持たせたトライ 兄弟ノードが隣接するように配置 探索時，子ノードを線形探索して移動先を決定 TernaryTrie BasicTrie の各ノードに「子ノードの数」を加えたトライ 探索時，子ノードを二分探索して移動先を決定 DaTrie ダブル配列によるトライ 探索時，ラベルにより移動先を一意に決定 SuccinctTrie 「一つ目の子ノードを左の子」，「兄弟ノードを右の子」とする二分木に
Aho Corasick 法 - naoyaのはてなダイアリー
適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」「店」という単語が含まれていた場合には、これらの単語(と出現位置)が入力に対しての出力になります。 この類の処理は、任意の開始位置から部分一致する辞書中のキーワードをすべて取り出す処理、ということで「共通接頭辞検索 (Common Prefix Search)」などと呼ばれるそうです。形態素解析、Wikipedia やはてなキーワードのキーワードリンク処理などが代表的な応用例です。 Aho Corasick 法 任意のテキストから辞書に含まれるキーワードをすべて抽出するという処理の実現方法は色々とあります。Aho Corasick 法はその方法のひと
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
)
トライ (データ構造) - Wikipedia
"A", "to", "tea", "ted", "ten", "i", "in", "inn" というキー群によるトライ木 トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。 キーが文字列である連想配列の実装構造としても使われる。右図の例では、ノードを表す丸の中にキーが書かれ、連想される値がその下に書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語
Darts: Double ARray Trie System
Darts: Double-ARray Trie System はじめに Darts は, Double-Array [Aoe 1989]を構築するための シンプルな C++ Template Library です. Double-Array は Trie を表現するためのデータ構造です. ハッシュ木, デジタルトライ, パトリシア木, Suffix Array による擬似 Trieといった 他の Trie の実装に比べ高速に動作します. オリジナル の Double-Arrayは, 動的に key の追加削除を行えるような 枠組ですが, Darts は ソート済の辞書を一括してDouble-Array に変換することに機能を絞っています. ハッシュのような単純な辞書として使うことも可能ですが, 形態素解析器の辞書に必須の Common Prefix Search を非常に高速に行うことが
Double-Array
ダブル配列（ Double-Array ）は， トライ（ Trie ）のデータ構造の一種であり， 小さい辞書で高速に検索できるという特長を持っています． 実際に，茶筌（ ChaSen ）や 和布蕪（ MeCab ）などの 形態素解析器で利用されているという実績があります． ダブル配列では，配列を使ってトライを表現します． 配列の各要素が BASE, CHECK という二つの整数を持つので，頭文字をとって配列 BC と呼ぶことにします． 以降の説明では，配列 BC の要素 x の BASE, CHECK を それぞれ BC[x].BASE, BC[x].CHECK と記述します． 通常，BASE, CHECK は個別の配列として紹介されますが， 特に分割して考える必要がないので，このような説明にしました． 基本的に，配列 BC の各要素は トライの節と一対一で対応します． そのため，対応する
画像圧縮アルゴリズム (5) LZ法
この章では、現在のデータ圧縮・画像圧縮などで広く用いられているLZ法について説明します。 前章までで説明したハフマン圧縮では、個々のデータをハフマン符号に変換して圧縮を試みるというものでしたが、LZ法では、あるデータ列に着目して、それが以前に出現したことがあるかをチェックし、すでに出現したことがあるのならば、そのデータ列を示す何らかの符号(当然、データ列より短くなければなりません)に置き換える処理を行うことにより、圧縮を行っています。 LZ法には、いくつかの種類があり、その種類によってさらに名称が変わります。しかし、その違いは符号化の方法だけで、処理の内容については全て同じです。 LZ法は、Abraham LempelとJacob Zivの二人による共同開発によって、1977年に誕生しました。正式名称はZiv-Lempel codingですが、間違ってLZ法として紹介したことから、現在の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
