Double-Array Trie verständnisproblem
-
Hi,
ein eher komplexes Thema.. ich hoffe ihr könnt mir helfen. Ich habe mich mal anhand dieses Artikels: http://linux.thai.net/~thep/datrie/datrie.html darüber schlau gemacht wie das ganze funktioniert. Gestoßen bin ich darauf durch flex dass code erzeugt der diese methode nutzt. Ich denke ich habe das Prinzip verstanden.. jedoch hab ich probleme bei der realisierung.
Also beispielsweise ich möchte das Wort "int" durch diese Methode "retrieven". Also als erstes brauche ich so eine Tabelle
States Labels 1 "Start" 2 i 3 n 4 t 5 "jedes andere zeichen"Denke ma so fängts schon an. Das kommt mir so schon falsch vor. Selbst wenn das richtig is... wie kriege ich daraus die base, next, check arrays?
Klar is mir dass das nächste state bei 2 -> 3 sein soll, bzw. zu 3 -> 4...Bin über jede Hilfe dankbar.
mfg
-
Ein Trie ist ein Baum.
Du brauchst einen Datentyp, welcher die Knoten der Trie-Struktur repräsentiert. In den Instanzen dieses Datentyps kannst Du dann die entsprechenden Infos unterbringen.
Ein paar weitere Quellen mit Denkanstößen liefert wie so oft Wikipedia:
Trie
Radix-Tree
Da gibt es zum Teil sogar Pseudo-Code.
-
Als Datentyp für die Knoten benutze ich Zahlen, also Zustände. Genau wie in dem Artikel in meinem ersten Post.
Mein trie würde dann so aussehen (siehe Anhang). Daraus würden also die folgenden Zustände folgen:enum States { STATE_ILLEGAL, STATE_START, STATE_I, STATE_IN, STATE_INT };Mal angenommen meine akzeptierten Chars wären:
enum AcceptedChars { CHAR_ILLEGAL, CHAR_SMALLI, CHAR_SMALLN, CHAR_SMALLT };dann müsste mein "next" array ja folgendermaßen aufgebaut sein
States next[4] = { STATE_ILLEGAL, STATE_I, STATE_IN, STATE_INT };allerdings is das next array ja immer abhängig von dem base array und dass is auch das was ich noch nich ganz gecheckt habe. Und dann gibt es ja noch das check array.... jedenfalls bei dem Tripple-Array Trie, den ich auch realisieren will
EDIT:
sorry anhang vergessen
-
up
kann keiner helfen?
