Fast and Space Efficient Trie Searches

Эмпирическим путём доказано, что практика отличается от теории.


Array Mapped Tree (AMT)
Вернёмся к нашему самому первому, неоптимальному дереву. Мы (в общем случае) не можем свести стоимость пустых вхождений к нулю. Но можем свести к одному биту.

Идея проста и стара (описана в 1977), как мир: каждому символу сопоставляется один бит. Бит отвечает за то, что путь валидный и существует. То есть, если соответствующий бит включён - то ветвь с таким символом существует и находится в children. А поскольку наш массив - плотный (вмещает только non-NULL указатели), то для получения нужного индекса считаем, сколько битов включено перед ним:

struct AMT{
  uint term:1;
  uint bitmap:26;
  struct AMT* c[];
}

bool search(struct AMT* node, char* str) {
  for (; *str; str++) {
    uint b = 1 << (*str-'a');
    if ((node->bitmap & b) == 0)
      return false;
    uint next = __builtin_popcount(node->bitmap & (b-1));
    node = node->c[next];
  }
  return node->term;
}

(uint term:1 говорит компилятору, что использоваться будет только 1 бит - и тогда он сам подставит нужные битшифты/маски, и даже грамотнее структуру упаковать сможет - не придётся руками возиться. b-1 в popcount делается вот зачем.)

Разберём все действия при поиске:
1. Смотрим, есть ли такая буква в c: сдвигаем 1 на порядковый номер буквы и проверяем, что такой бит в битмаске включён.
2. Чтобы получить индекс нужного нам узла в массиве, считаем, сколько узлов в массиве предшествуют ему. То есть - считаем, сколько единиц в битмаске включено ДО нашего узла.
3. Когда строка кончилась, возвращаем флаг term у последнего узла.

Заметьте: атрибуты term и bitmap, скорее всего, будут храниться в одном uint32, а variable-length поле c представляет из себя обычный указатель. Длину массива хранить нам тоже не надо, ведь она уже заключена в количестве единиц в bitmap целиком. Итого - вся структура с выравниванием весит два машинных слова (вне зависимости от архитектуры), что пока что сопоставимо с ACT. Но отличительная черта - для вставки не нужно решать вычислительно-трудную проблему, а при сжатии дерево идеально занимает всё пространство в массиве без пропусков.

К сожалению, аргумент перестаёт работать с увеличением кардинальности алфавита. Чем больше символов мы учитываем - тем больше бит необходимо хранить. В ACT же кардинальность нигде не хранится, и, следовательно, оно агностично к мощности. Для полного алфавита в 256 символов таблица ACT никак не поменяется, когда как каждый узел AMT будет содержать 32 байта только битмап. Суммарно - 40-48 байт на узел, и это без наследников. Напоминаю, что ACT даже не экономя не вылазит за пределы 16 байт. Старая-добрая дилемма: либо быстро, либо компактно.