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