Wie würde man this data structure in C implementieren? Es ist eine Struktur, die der DAWG ähnelt, aber doppelt so effizient ist wie die DAWG, die effizienter ist als der Trie, der nur Präfixe komprimiert.Wie kann man einen Compact Directed Azyklic Word Graph (CDAWG) in C implementieren?
Von dem, was ich, es ist aus diesem paper
ein Trie mit Suffix Kompression sehen die endgültigen Statusänderungen für ein Spiel zu reduzieren, da hatte ich etwas Ähnliches gearbeitet, dass ich auch, dass in Betracht gezogen hatte, zu tun zu retten Raum. Das war die Lösung, die ich für die Datenstruktur gedacht hatte, ich bin interessiert, um zu sehen, ob es andere Ansätze sind:
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
};
Dies ist eine ziemlich offene Frage, die jemand zu sein scheint zu fragen, nur die Umsetzung Datenstruktur (eine eher spezifische, spezialisierte) für Sie. Sie erhalten möglicherweise eine bessere Antwort, wenn Sie (a) die Datenstruktur beschreiben und (b) zeigen, welche Arbeit Sie bereits geleistet haben oder welche Ideen Sie haben. –