ダブル配列

ウィキペディア小見出し辞書

ダブル配列

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 06:29 UTC 版)

「トライ (データ構造)」の記事における「ダブル配列」の解説

1989年に青江順一がダブル配列を利用する方法を発表した。トライ木は決定性有限オートマトンとして解釈する事が出来るが、決定性有限オートマトンはデフォルト（default）・ベース（base）・次（next）・チェック（check）の4つの配列で表現できる。トライ木の場合はデフォルトは不要である。その上で、s から t へ c により遷移する場合は、以下の関係が成立すれば良い。 check[base[s] + c] = snext[base[s] + c] = t 動的に要素が増えていく場合 next と check は同じように増えていくのでまとめる事が出来るが、base は同じ速度では増えていかず分裂してしまう。そこで、ダブル配列では、base と next を統合し、以下の関係が成立するように管理する。 check[base[s] + c] = sbase[s] + c = t すると、base と check だけが残り、この2つは同じ速さで増えていき、一つの構造体にまとめる事が出来る。 ある要素がトライ木に含まれているかどうか調べる際に、二重連鎖木を使った方法では、兄弟ノードはポインタ（連結リスト）をたどって行かないといけないが、ダブル配列では一発で遷移できる。 実装としては Theppitak Karoonboonyanan が libdatrie を公開している。