[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

タグ

darrayとtrieに関するhiromarkのブックマーク (4)

  • Google Code Archive - Long-term storage for Google Code Project Hosting.

    Code Archive Skip to content Google About Google Privacy Terms

    hiromark
    hiromark 2008/10/10
    "This project provides a clone of the Darts (Double-ARray Trie System). "
  • 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 を非常に高速に行うことが

    hiromark
    hiromark 2008/09/15
    ダブル配列を構築するための シンプルな C++ Template Library
  • Double-Array

    ダブル配列( Double-Array )は, トライ( Trie )のデータ構造の一種であり, 小さい辞書で高速に検索できるという特長を持っています. 実際に,茶筌( ChaSen )や 和布蕪( MeCab )などの 形態素解析器で利用されているという実績があります. ダブル配列では,配列を使ってトライを表現します. 配列の各要素が BASE, CHECK という二つの整数を持つので,頭文字をとって配列 BC と呼ぶことにします. 以降の説明では,配列 BC の要素 x の BASE, CHECK を それぞれ BC[x].BASE, BC[x].CHECK と記述します. 通常,BASE, CHECK は個別の配列として紹介されますが, 特に分割して考える必要がないので,このような説明にしました. 基的に,配列 BC の各要素は トライの節と一対一で対応します. そのため,対応する

    hiromark
    hiromark 2008/09/15
    ダブル配列の説明。 "ダブル配列では,配列を使ってトライを表現します", "配列構造と同じくらい高速で,リスト構造と同じくらいコンパクトになるとされています"
  • An Implementation of Double-Array Trie

    Contents What is Trie? What Does It Take to Implement a Trie? Tripple-Array Trie Double-Array Trie Suffix Compression Key Insertion Key Deletion Double-Array Pool Allocation An Implementation Download Other Implementations References What is Trie? Trie is a kind of digital search tree. (See [Knuth1972] for the detail of digital search tree.) [Fredkin1960] introduced the trie terminology, which is

    hiromark
    hiromark 2006/02/06
    TRIE の実装についての解説。
  • 1