2016年8月1日月曜日

LOUDSでTrieを作る

LOUDSを用いたTrieです. 文字列をキーとした連想配列で使用することを想定しています.
Trie完備辞書はこのために作成しました.
上2つは公開時から不具合修正と機能追加をしています.

LOUDSは, 木構造をビット列で表現します.
節点を幅優先で走査し, 各節点で子の数だけ"1"を並べ, 節点の終端に"0"を置きます.
子のない節点は"0", 子が1つの節点は"10"です.