Twas brillig at 01:42:01 03.09.2008 UTC+04 when at@altlinux.ru did gyre and gimble:

 AT> Тут ещё такое дело что кодироване указателями иногда ничего не
 AT> даёт.  Напр. компонент "/usr" в строке занимает четыре байта, и
 AT> укзатель тоже занимает четыре байта, так что замена коротких
 AT> компонентов пути на указатель ничего не даёт.  Более того, игра в
 AT> указатели имеет подводную часть -- malloc bookkeeping (malloc is
 AT> not *that* free) и фрагментация памяти.

Я когда игрался - обошёлся без выделения памяти, построив всё trie в
одном chunk-е памяти со смещениями в узлах дерева (тип узла, буква и
смещение укладываются в 4 байта), имя пакета, естественно, хранил ровно
один раз (на именах тоже можно trie организовать, но я не
попробовал). Правда, такая структура данных потребует всасывания большой
части файла в память.

Ещё можно выиграть за счёт введения путей типа /foo/bar/some/* -> some.

--