Домашние животные мне строго противопоказаны. Как-то раз у меня жил ручной камень. Он умер.
Unary Search Tree (UST)
Деревья тем прекрасны, что для решения одной проблемы дерева, мы используем другое дерево.
Имея, что AMT сильно страдает от увеличения кардинальности алфавита, мы можем обменять быстрое нахождение ветви через popcount на старый добрый бинарный поиск. Тогда нам больше не нужна битмапа, заместо неё остаётся только
uint8 clen. Вот мы и получаем:
struct UST{
int term:1;
int symb:8;
int clen:8;
struct UST* c[];
}
bool search(struct UST* node, char* s) {
for (; *s; s++)
if (!(node = binsearch(node->c, node->clen, *s)))
return false;
return node->term;
}
(Где symb - символ, который ведёт к узлу.)
Мои поздравления - мы совершили кругосветное путешествие и вернулись к старому доброму бинарному поиску! Поиск узла, конечно, больше не O(1) (принимая сложность popcount за константу; кстати благодаря SSE - до него это было либо медленно, либо вообще отсутствовало), но O(log m) (m - кардинальность алфавита). Но это всё ещё максимум 8 сравнений в худшем случае, для узла со всеми 256 ветвями. А вот из преимуществ - узел UST влазит в одно 64-разрядное машинное слово, если уместить его в массив (4 байта индекс ветви + 1 байт длина массива + 1 байт символ узла + 1 байт (выровненный) терминальный флаг = 7 байт). Узел, весом с указатель - это абсолютный рекорд. Абсолютно компактно, совершенно не быстро.
Унарным оно, кстати, и называется потому, что структура номинально содержит лишь один-единственный указатель.
В заключение.
С деревьями можно играться нескончаемо. В эквиваленте 13 страниц А4 я лишь вкратце рассказал про основополагающие вариации, и только лишь для сопоставления строк - словно капля в море. В работе, на которую я опирался, префиксные деревья как compressed m-way trie упоминаются очень вскользь, и то только в конце, хотя компактность представляет центральный интерес бумаги. Потому и желаю вам вырабатывать должную интуицию и не полагаться на заучивание. Человека умнее делает не слово, а контекст.
—
Большая часть материала и целых два скрина были взяты из [Bagwell 2000] (на что заголовок, собственно, и отсылает). Сам документ я оставил в комментариях.