Сохранение trie в файл - C
У меня есть a trie который я использую, чтобы сделать некоторую строковую обработку. У меня есть простой компилятор, который генерирует trie от некоторых данных. После того, как сгенерированный, мой trie не изменится во время выполнения.
Я ищу подход, где я могу сохранить trie в файле и загрузить его эффективно. Я посмотрел на sqllite понять, как они сохраняются b-treeно их формат файла смотрит усовершенствованный бит, и мне, возможно, не понадобятся все те.
Было бы полезно, если кто-то может обеспечить некоторые идеи сохраниться и читать trie. Я программирую использование C.
3 ответа
Я провел небольшое исследование и нашел в Интернете следующие маленькие жемчужины:
Рабочее дерево с сериализацией и десериализацией. Первоначально он был написан для использования в Python (есть соответствующий triemodule.c для привязки его к Python), но это чистый C; вы можете использовать его для поиска идей или использовать по своему усмотрению.
Обновление :
Похоже, ссылки больше не работают. Я сохраню оригиналы, но вот ссылки в машине возврата:
Если все ваши узлы имеют одинаковый размер, вы можете просто пронумеровать свои узлы (root = 0) и записать каждый из них в файл по их индексу. Однако при их написании вам придется изменить их ссылки на другие узлы на индексы этих узлов. Возможно, вам также понадобится значение NULL . Вы можете использовать -1 или (root = 1) и ( NULL = 0).
Вы, вероятно, также сможете несколько сжать эти узлы, изменив их поля указателей на меньшие типы.
Если ваши узлы разного размера, все сложнее.
Предполагая, что вся ваша структура данных умещается в памяти, подход рекурсивной сериализации является самым простым. 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)