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
Spaghetti Source - 複数パターン検索 (Aho-Corasick)
説明 複数のパターン文字列からなる集合と長い文字列が与えられる．長い文字列に対してマッチするパターン文字列をすべて求めるアルゴリズムが Aho Corasick である．これは複数パターン文字列をあらかじめ trie に変換してから KMP を実行し，パターンマッチング・オートマトンを構成していることになる． 詳しくは適当な成書や http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf などを参考のこと． 計算量 構築 O(m)． 検索 O(n + m)． ただし m はパターンの文字列長の総和，n は検索テキスト長． 使い方 struct PMA; を適宜設定のこと． buildPMA(char *p[], int m) 0 ... m-1 の複数の検索パターンから，パターンマッチング・オートマトンを構築する． match(c
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
