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

Question

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

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

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

Answer 1

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

1. trie.h
2. trie.c

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

Update:

Он не появляется ссылки больше не работают. Я буду держать оригиналы, но вот ссылки на Вайбаке машины:

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).

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

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