Сохранение дерева в файл - 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).

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

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