岡野原です。 ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。 今回はtrie（トライ）の最近の話をしたいと思います。 trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情... 続きを読む

• research.preferred.jp
• テクノロジー

rxはGoogle日本語入力（Mozc）でも使われているTrieのライブラリである。LOUDSというツリーを表す簡潔データ構造を使ってTrieを実現している。第2回自然言語処理勉強会@東京に行ってきて、そういえばrxは読んでなかったなと思ったので、ちょっとだけ読んでみた... 続きを読む

• d:id:tkng
• テクノロジー

概要marisa-trie では，1 byte のラベル（Single-byte（SB）ラベル）は各トライに格納し，2 bytes 以上のラベル（Multi-byte（MB）ラベル）は次のトライもしくは TAIL に格納するようになっています．そのため，SB/MB ラベルを区別するためのフラグを各ノードに... 続きを読む

• d:id:s-yata
• テクノロジー

概要rank/select は簡潔データ構造（Succinct Data Structures）の核になる関数です．ビット列の k ビット目までに含まれる 0, 1 の数を求めるのが rank，k 番目の 0, 1 の位置（Index）を求めるのが select であり，ビット列の密度（1 の割合）によって，いろ... 続きを読む

• d:id:s-yata
• テクノロジー

研究 | [2010/02/21 更新: marisa-trie 0.1.3][2010/02/18 更新: marisa-trie の仕様変更に伴い，追記の記述を整合性が取れるよう変更; 最新版では未確認]id:s-yata さんが marisa-trie を公開されたので，例によってベンチマークを取った結果を公開しておきま... 続きを読む

• d:id:ny23
• テクノロジー

概要トライのライブラリを公開しました．ドキュメントはまったく用意できていませんが，とりあえず使えます．http://code.google.com/p/marisa-trie/インストールビルド・インストールの方法は configure と make です．以下のようにすればインストールできます... 続きを読む

• d:id:s-yata
• テクノロジー

最近、趣味で開発しているStaKKのためにTrieライブラリを書いているのですが、参考にするためオープンソースのTrieライブラリについて調べました。簡潔データ構造を用いたものが中心です。 @hillbig氏によるもの tx LOUDSによる圧縮でメモリ使用量を削減したTri... 続きを読む

• d:id:nokuno
• テクノロジー

トライを構築したときのノード数が分からない，TAIL を導入したときにサイズがどのくらい小さくなるのか分からない，そんな悩みに答えるちょっとしたツールのソースコードです．各ノードのサイズとノード数が分かればトライのサイズは簡単に求まるので，トライ... 続きを読む

• d:id:s-yata
• テクノロジー

Introduction There are many algorithms and data structures to index and search strings inside a text, some of them are included in the standard libraries, but not all of them; the trie data structure is a good example of one that isn't. Let w... 続きを読む

• www.topcoder.com
• 学び

紫蘇カンファレンス2010というイベントでLTをしました。紫蘇カンファレンス 2010 - しソ部Togetter - 「紫蘇カンファレンス 2010」内容は、StaKKのスペル訂正機能についての解説です。統計的自然言語処理エンジンStaKK - nokunoの日記shisoconf 2010 Spelling C... 続きを読む

• d:id:nokuno
• テクノロジー

common lisp, algorithm『Ideal Hash Trees』*1という論文を(必要なところだけ、だいたい)読み終わったので、そのメモ等。 概要AMT(Array Mapped Trie)という基盤的なデータ構造を使って、ideal(nearly ideal)なHash Treesを作ろう、というような話。AMTの応用... 続きを読む

• d:id:sile
• テクノロジー

02:08 | Succinct なトライをサポートする sumire-tries があるにもかかわらず，ここしばらく，大規模なトライ用のライブラリを開発しています．sumire-tries を何度も修正したのは，開発の途中でいろいろと気づいて，それらを反映させていたからです．いわゆる... 続きを読む

• d:id:s-yata
• テクノロジー

21:45 | いつものように，Google Code にアップロードしました．プロジェクトの名前は sumire-tries になっています．名前を sumire にした理由は，なんとなくです…．ドキュメントは準備中ですが，基本的な使い方は後述します． sumire-tries - Project Hostin... 続きを読む

• d:id:s-yata
• テクノロジー

15:46 | 実験の概要Succinct な木構造を用いてトライを実装すると，コンパクトな辞書を構築できます．しかし，検索速度の面では，その他のデータ構造に劣るという欠点を持ちます．そこで，いくつかのトライを C++ で実装し，ちょっとした性能テストをしてみまし... 続きを読む

• d:id:s-yata
• テクノロジー

適当な単語群を含む辞書があったとします。「京都の高倉二条に美味しいつけ麺のお店がある」*1という文章が入力として与えられたとき、この文章中に含まれる辞書中のキーワードを抽出したい、ということがあります。例えば辞書に「京都」「高倉二条」「つけ麺」... 続きを読む

• d:id:naoya
• テクノロジー

English 概要 TxはコンパクトなTrieを構築するためのライブラリです．従来のTrieの実装（darts等）に比べ1/4〜1/10の作業領域量で辞書を保持することができ、数億〜十億キーワードなど大規模な辞書を扱うことが可能です．Trieは文字列からなるキー集合を処理す... 続きを読む

• www-tsujii.is.s.u-toky...
• テクノロジー

This project provides a clone of the Darts (Double-ARray Trie System). The clone library has an advantage in memory. The Darts is a C++ header library for the double-array that was presented by Jun-ichi Aoe as an efficient implementation of a... 続きを読む

• code.google.com
• 学び

トライ木（Trie）とは、順序付き木構造 (データ構造)の一種。プレフィックス木（Prefix Tree）とも呼ばれる。キーが文字列である連想配列の実装構造として使われる。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置と... 続きを読む

• ja.wikipedia.org
• テクノロジー

Darts: Double-ARray Trie System はじめに Darts は, Double-Array [Aoe 1989]を構築するための シンプルな C++ Template Library です. Double-Array は Trie を表現するためのデータ構造です. ハッシュ木, デジタルトライ, パトリシア木, Suffix Array によ... 続きを読む

• chasen.org:taku
• テクノロジー

ダブル配列（ Double-Array ）は， トライ（ Trie ）のデータ構造の一種であり， 小さい辞書で高速に検索できるという特長を持っています． 実際に，茶筌（ ChaSen ）や 和布蕪（ MeCab ）などの 形態素解析器で利用されているという実績があります． ダブル配... 続きを読む

• nanika.osonae.com
• テクノロジー