Double-Array Articles
ダブル配列のライブラリを公開しているページです． An Implementation of Double-Array Trie URL: http://linux.thai.net/~thep/datrie/datrie.html Darts: Double-ARray Trie System URL: http://chasen.org/~taku/software/darts/ Dame URL: http://www.void.in/wiki/Dame Tiny Double-Array Library URL: http://nanika.osonae.com/TinyDA/index.html Dynamic Double-Array Library URL: http://nanika.osonae.com/DynDA/index.html
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 を非常に高速に行うことが
ダブル配列におけるキャッシュの効率化
ダブル配列におけるキャッシュの効率化 Cache-Efficienct Double-Array 矢田 晋 森田 和宏 泓田 正雄 平石亘 青江 順一 Susumu Yata Kazuhiro Morita Masao Fuketa Wataru Hiraishi Jun-ichi Aoe 徳島大学工学部 Faculty of Engineering, Tokushima University 1. はじめに 辞書からキーを検索するという処理は，コンパイラ， 索引検索，フィルタリング，形態素解析などの様々な分 野で必要となるため，計算機処理における基礎技術の 一つとされている [1]．特に，文字単位で照合をおこな うトライは，理論的な検索時間がキーの長さで抑えら れる，入力に前方一致するキーを容易に検出できるな どの理由から，自然言語辞書を中心として幅広く利用 されている．このトライを実現す
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
