Сохранение дерева в файл - C

Question

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

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

Было бы полезно, если бы кто-то мог дать некоторые идеи, чтобы сохранить и прочитать trie, Я программирую, используя C.

Answer 1

Я провел небольшое исследование и нашел в Интернете следующие маленькие жемчужины:

1. trie.h
2. trie.c

Рабочий три с сериализацией и десериализацией. Первоначально он был написан для использования в Python (есть соответствующий triemodule.c для привязки к Python), но это чистый C; Вы можете добывать его для идей или использовать по своему желанию.

Обновление:

Похоже, что ссылки больше не работают. Я сохраню оригиналы, но вот ссылки на машине обратного хода:

1. trie.h
2. trie.c

Answer 2

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

Вот пример псевдокода для чтения / записи узла. Он работает путем рекурсивного чтения / записи дочерних узлов. Он не имеет ничего специфичного для дерева и должен работать и для других древовидных структур данных.

void writeNode(Node *node)
    write node data to file
    write node.numOfChildren to file
    for each child:
        writeNode(child)

Node *readNode()
    Node *node = allocateNewNode()
    read node data from file
    read node.numOfChildren from file
    for (i=0; i<node.numOfChildren; i++)
        Node *child = readNode()
        node.addChild(child)

Answer 3

Если все ваши узлы имеют одинаковый размер, вы можете просто перечислить их (root = 0) и запишите каждый из них в файл по индексу. При их написании вам придется изменить их ссылки на другие узлы на индексы этих узлов. Вам, вероятно, также понадобится NULL значение. Вы могли бы использовать -1 или вы могли бы использовать (root = 1) а также (NULL = 0).

Вы, вероятно, также сможете несколько сжать эти узлы, изменив их поля указателя на меньшие типы.

Если ваши узлы разных размеров, то это сложнее.

Answer 4

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