akkun_choi pedia
mindia › akkun_choi pedia › 単語

Double Array Trie

akkun_choi · 2008-11-11 更新 · 履歴(2)

Trieの実装といえばこれ。
普通の配列だとsparseになる。リストだとキー数に比例して遅くなって効率悪い。

Double Array Trieでは、2つの配列を使う。ひとつは文字を整数にマッピングしたものと、もうひとつはリンク関係を記述したもの。Baseの値に文字の整数表現を足した値が次のノードになっている。

http://nanika.osonae.com/DArray/dary.html

タグ