MARISA: Matching Algorithm with Recursively Implemented StorAge
Abstract: Matching Algorithm with Recursively Implemented StorAge (MARISA) は Trie をコンパクトに表現する程度の能力を持つデータ構造です．libmarisa は MARISA を C++ で実装したライブラリであり，MARISA による辞書を構築したり，辞書からの検索をおこなったりできます．libmarisa の基本的な機能に対応するコマンドラインツールを用意しているので，辞書のサイズがどのくらいになるのか，検索にどのくらい時間がかかるのか，などを手軽に試すことができます． 概要 Matching Algorithm with Recursively Implemented StorAge (MARISA) は Trie に対するコンパクトなデータ構造であり，動的な更新には対応していないものの，高い空間効率と
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 を非常に高速に行うことが
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
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ダブル配列におけるキー削除の効率化手法 | CiNii Research
