Fast and Space Efficient Trie Searches

У людей в среднем менее двух ног.


Array Compacted Tree (ACT)
Для освежения памяти: Look-Up Table (LUT) - это обычный статический массив, но с его элементами в таком порядке, чтобы их значение ассоциировалось с конкретным индексом. То есть, чтобы вело себя, как хэшмапа. ASCII символы, например, это самые обычные числа 0..255, которыми массив на 256 вхождений спокойно индексируется, и даже без bound checks. Да и места обычно тоже не сильно много занимает. Похожим образом я у себя в indigo hex-значения декодирую: в таблице из 256 восьмибитных чисел для ASCII-символов 0-9, a-f и A-F лежат соответствующие заранее рассчитанные значения. На валидацию я, естественно, хуй клал. А ещё с ними можно очень хорошо оптимизировать декомпрессор кода Хаффмана, что для HTTP/2 и 3 очень даже полезно.

Ближе к делу. ACT - это просто все субдеревья (узлы) размазали на плоские LUT, и сплавили вместе так, чтобы на пустующих местах одного LUT были размещены узлы другого. Так и называются - overlaid tries, потому что налазят друг на друга. Различают они их по тэгу Parent, чтобы понимать, чьему субдереву этот узел приходится. Если Parent совпадает - отлично, такой вариант развития событий в дереве заложен. Тогда мы берём от него XBase - корневой узел следующего интересующего нас субдерева, и индексируем наш следующий LUT, но уже относительно этого XBase. Вы ничего не поняли, но не переживайте, сейчас я попробую всё подробнее разъяснить.

Дадим же наконец определение:

struct ACTNode{
  int XBase;
  int Parent;
}

typedef ACTNode ACT[N]; // N is to be specified

bool search(ACT trie, char* str) {
  for (int base = trie[0].XBase; *str; str++) {
    struct ACTNode node = trie[base + (*str-'a')];
    if (node.Parent != base)
      return false;
    base = node.XBase;
  }
  return base == NULL;
}

Атрибуты структуры именованы в соответствии с таблицей. Столбец Letter там добавлен для удобства, а Node это просто индекс узла в массиве.