Persistindo um trie para um arquivo - c

Question

eu tenho um trie que estou usando para fazer algum processamento de string. Eu tenho um compilador simples que gera trie de alguns dados. Uma vez gerado, meu trie não vai mudar no tempo de execução.

Estou procurando uma abordagem em que possa persistir o trie em um arquivo e carregá -lo de maneira eficaz. Eu olhei para sqllite Para entender como eles estão persistindo b-treeMas o formato de arquivo deles parece um pouco avançado e eu posso não precisar de tudo isso.

Seria útil se alguém pudesse fornecer algumas idéias para persistir e ler o trie. Estou programando usando C.

Answer 1

Eu fiz algumas pesquisas e encontrei as seguintes pequenas jóias online:

1. trie.h
2. trie.c

Um trie de trabalho com serialização e deserialização. Foi originalmente escrito para uso em python (há um correspondente triemodule.c por amarrá -lo a Python), mas é puro C; Você poderia explorar as idéias ou usá -lo como desejar.

Atualizar:

Parece que os links não estão mais funcionando. Vou manter os originais, mas aqui estão os links na máquina Wayback:

1. trie.h
2. trie.c

Answer 2

Supondo que toda a sua estrutura de dados se encaixe na memória, uma abordagem de serialização recursiva é mais simples. O SQLLITE funciona com estruturas de dados que não se encaixam na memória; portanto, provavelmente é exagero tentar copiar seus métodos.

Aqui está o exemplo pseudocode para ler/escrever um nó. Funciona lendo/escrevendo recursivamente os nós filhos. Não tem nada específico para trie e também deve funcionar para outras estruturas de dados de árvores.

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

Se todos os seus nós tiverem o mesmo tamanho, você pode simplesmente enumerar seus nós (root = 0) e escreva cada um deles em um arquivo em seu índice. Ao escrever, você terá que mudar suas referências a outros nós para os índices desses nós. Você provavelmente também precisará de um NULL valor. Você poderia usar -1 ou você pode usar (root = 1) e (NULL = 0).

Você provavelmente também poderá comprimir esses nós um pouco, alterando seus campos de ponteiro para serem tipos menores.

Se seus nós são tamanhos diferentes, é mais complicado.