A good CPAN solution that I've played with in the past is Tree::Trie. I would discard Data::Trie as it doesn't do prefix lookups.

There's also Text::Trie written by the illustrious ILYAZ. While I find it's good for seriously complex problems, it doesn't make the simple things easy. Lots of make-work code to set up all the necessary callbacks.