サクサク読めて、アプリ限定の機能も多数！
トップへ戻る
衆院選
nanika.osonae.com
ダブル配列 （ Double-Array ） とは， トライ （ Trie ） のデータ構造の一つで， 「小さい辞書で高速な検索」が特長になります． トライを表現したデータ構造ですから， 「入力文字列の前方部分列と一致するキーの検索」が可能です． 使い方としては，フィルタリングや構文解析，形態素解析などがあります． ライブラリとしては，おそらく Darts が有名です． Darts: Double-ARay Trie System TinyDA は， Darts に影響されて作成したライブラリです． キーを整列して辞書に一括登録するようになっていて， レコードについては，型を特定せず，領域だけを確保するようになっています． そのため，辞書を作成した後でキーを追加することはできませんが， レコードを変更することは可能です． ただし，レコードを変更する場合は， 書き込む領域を誤ると辞書が破損し
トライは抽象的なデータ構造であり，実際に構築する場合， 具体的なデータ構造を考える必要があります． 以降の説明では，具体的なデータ構造のことを， 単純にデータ構造と記述するものとします． トライの単純なデータ構造として，配列構造とリスト構造があります． 文字通り，配列構造はトライを配列により実現し， リスト構造はトライを連結リストにより実現します． また，配列構造の利点は高速なことで，リスト構造の利点はコンパクトなことです． 配列構造とリスト構造の説明では，以下に示すトライを例として使います．
トライ（ Trie ）とは， 自然言語処理やコンパイラ，フィルタリングなどに用いられている木構造です． 二分探索木などとは異なり，文字単位で探索が進行するので， 入力文字列の前方部分と一致するキーを列挙したり， どの文字まで探索に成功していたかという情報を取得したりできます． また，キー数の増加によって検索速度が遅くなりにくいという特徴もあります． トライは文字列を格納するのに適した木構造です． トライの節（ Node ）あるいは 枝（ Arc ）には 文字が付与されていて（ Label ）， 根（ Root ）から 葉（ Leaf ）への 経路（ Path ）上の文字を連結することにより， 登録されている文字列を復元することができます． 例えば，三つの文字列 "bird", "bison", "cat" を登録したトライは以下のようになります． 図中の節についている番号は，すべての節を一
ダブル配列は動的に更新できるデータ構造として提案されました． しかし，キーを追加するとき，衝突（ Collision ） という厄介な問題が発生します． そこでまず，キーの追加や削除を考慮せず， 登録するキーがすべて分かっている状態からの構築方法について説明します． 更新が遅いと評判のダブル配列ですが， 登録するキーの数が 10 万件くらいであれば， 1 秒以内で構築することができます． ただし，なぜか評価実験でよく使われている郵便番号のように， 網羅性の高いキー集合を対象とする場合は時間がかかります． なお，網羅性が高いという表現は，分岐数（節から出る枝の数）の平均が 大きいことを意味しています． ダブル配列を構築する前に，マルチキークイックソート （ Multikey Quicksort ） などを使用してキー集合を整列します． マルチキークイックソートは基数ソートとクイックソートを合
C 言語から C++ に移行しています． たまに C# が増えるかもしれません． 現在のところ，C / C++ / C# のライブラリや データ構造とアルゴリズムに関する記事があります．
ダブル配列のライブラリを公開しているページです． 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
ダブル配列（ Double-Array ）は， トライ（ Trie ）のデータ構造の一種であり， 小さい辞書で高速に検索できるという特長を持っています． 実際に，茶筌（ ChaSen ）や 和布蕪（ MeCab ）などの 形態素解析器で利用されているという実績があります． ダブル配列では，配列を使ってトライを表現します． 配列の各要素が BASE, CHECK という二つの整数を持つので，頭文字をとって配列 BC と呼ぶことにします． 以降の説明では，配列 BC の要素 x の BASE, CHECK を それぞれ BC[x].BASE, BC[x].CHECK と記述します． 通常，BASE, CHECK は個別の配列として紹介されますが， 特に分割して考える必要がないので，このような説明にしました． 基本的に，配列 BC の各要素は トライの節と一対一で対応します． そのため，対応する
ダブル配列 （ Double-Array ） とは， トライ （ Trie ） のデータ構造の一つで， 「小さい辞書で高速な検索」が特長になります． トライを表現したデータ構造ですから， 「入力文字列の前方部分列と一致するキーの検索」が可能です． 使い方としては，フィルタリングや構文解析，形態素解析などがあります． ライブラリとしては，おそらく Darts が有名です． Darts: Double-ARay Trie System
このページを最初にブックマークしてみませんか？
『Something in C / C++ / C#』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
