如何在C中实现Compact Directed Acyclic Word Graph(CDAWG)？

Question

如何在C中实现此数据结构？它的结构类似于DAWG,但是空间效率是DAWG的两倍,比仅仅压缩前缀的trie更有效.

Answer 1

从我在本文中看到的内容

这是一个带有后缀压缩的trie,可以减少匹配的最终状态变化,因为我曾经做过类似的事情,我也考虑过这样做以节省空间.这是我想到的数据结构的解决方案,我很想知道是否有其他方法:

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
};