Comment peut-on implémenter un CDAWG (Compact Directed Acyclic Word Graph) en C?

Question

Comment implémenterait-on this data structure en C? C'est une structure similaire mais deux fois plus efficace que le DAWG, plus efficace que le trie qui compresse seulement les préfixes.

Answer 1

D'après ce que je peux voir de ce paper

C'est une structure arborescente avec compression suffixe pour réduire les changements d'état final pour un match, puisque j'avais travaillé sur quelque chose de semblable, je l'avais aussi envisagé de le faire que pour sauver espace. Ce fut la solution que j'avais pensé pour la structure de données, je suis curieux de voir s'il y a d'autres approches:

struct cdawg 
{ 
    int issuffix:1; 
    int length:31; 
    char *s; // suffix if issuffix == 1, else array of valid transition chars 
    struct cdawg *trans; // array of next states based on the index of trans char in s, null if suffix 
};