Эффективное пространство

Question

Я пытаюсь реализовать эффективный с пространством три в C. Это моя структура:

struct node {
char val; //character stored in node
int key; //key value if this character is an end of word
struct node* children[256];
};

Когда я добавляю узел, его индекс - это беззнаковое приведение символа.Например, если я хочу добавить «c», тогда

children[(unsigned char)'c']

- указатель на вновь добавленный узел.Однако эта реализация требует, чтобы я объявил массив узлов * из 256 элементов.То, что я хочу сделать, это:

struct node** children;

, а затем при добавлении узла, просто маллок пространство для узла и

children[(unsigned char)'c']

указывают на новый узел.Проблема в том, что если я сначала не использую маллок для детей, то, очевидно, я не могу ссылаться ни на один индекс, иначе это большая ошибка.

Итак, мой вопрос: как мне реализовать trie так, чтобы он только сохранял ненулевые указатели на своих потомков?

Answer 1

Вы можете попробовать использовать briandais trie , где у вас есть только один дочерний указатель для каждого узла, а у каждого узла также есть указатель на «одноуровневый элемент», так что все элементы одного уровня эффективно сохраняются в виде связанного списка, а не на который прямо указывает родитель.

Answer 2

Вы не можете использовать его в обоих направлениях, экономить пространство и искать O (1) в дочерних узлах.

Когда вы выделяете пространство только для фактически добавленных записей, а не длянулевые указатели, вы больше не можете делать

children[(unsigned char)'c']

Поскольку вы больше не можете индексировать непосредственно в массив.

Одна альтернатива - просто выполнить линейный поиск по дочерним элементам.и сохраните дополнительный счетчик количества записей в массиве children, т.е.

children[(unsigned char)'c'] = ...;

должен стать

for(i = 0; i < len; i++) {
  if(children[i] == 'c')
     break;
} 
if(i == len) {
  //...reallocate and add space for one item in children
}
children[i] = ...;

Если ваше дерево заканчивается множеством непустых записейна одном уровне вы можете вставить дочерние элементы в отсортированном порядке и выполнить бинарный поиск.Или вы можете добавить дочерние элементы в виде связанного списка вместо массива.

Answer 3

Вы можете экономить пространство и поддерживать постоянное время поиска, сделав дочерние узлы каждого узла хеш-таблицей узлов. Особенно, когда задействованы символы Юникода и набор символов, который вы можете иметь в своем словаре, не ограничен 52 + некоторыми, это становится скорее требованием, чем хитростью. Таким образом, вы можете сохранить преимущества использования дерева и одновременно экономить время и пространство.

Я также должен добавить, что если набор символов, который вы используете, приближается к неограниченному, шансы на наличие связанного списка узлов могут просто подойти. Если вам нравится неуправляемый кошмар, вы можете выбрать гибридный подход, при котором первые несколько уровней хранят своих детей в хеш-таблицах, а нижние уровни имеют связанный список из них. Для настоящей фермы ошибок выберите динамическую ферму, в которой, когда каждый связанный список преодолевает порог, вы на лету преобразуете его в хэш-таблицу. Вы можете легко амортизировать стоимость.

Возможности бесконечны!

Answer 4

Если вы просто хотите выполнить поиск по ключевым словам на английском языке, я думаю, что вы можете минимизировать размер своих детей, с 256 до 26 - достаточно, чтобы покрыть 26 букв a-z.

Кроме того, вы можете использовать связанный список, чтобы уменьшить количество дочерних элементов, чтобы у нас была более эффективная итерация.

Я еще не просмотрел библиотеки, но думаю, три реализации помогут.