C에서 CDAWG (Compact Directed Acyclic Word Graph)를 어떻게 구현할 수 있습니까?

Question

C에서 this data structure을 어떻게 구현합니까? DAWG와 비슷한 구조이지만 공간 효율성이 두 배나 높습니다. 접두어 만 압축하는 트리보다 효율적입니다.

내가 또한 저장 그 일을 생각했다고 비슷한에 근무했던 나는 그것이 경기의 최종 상태 변경을 줄이기 위해 접미사 압축과 트라이의이 paper

에서 볼 수있는에서

Answer 1

이후 공간. 이것은 내가 데이터 구조에 대해 생각해 본 해결책이었습니다. 다른 접근법이 있는지 궁금합니다.

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