packed trie irgendwie urgent!

[sebus]

Hi!
Hab mir gerade den Packed Trie angesehen (und im forum dazu gestöbert) und Fragen dazu!

1) Wie errechnet sich der Index der Wurzel? Beispiel im Skriptum: Index der Wurzel = 2; aha und wieso?

Hat das was damit zu tun, mit was die Wörter beginnen dürfen? Wohl kaum, da es Wörter mit "a" und mit mit "d" am Anfang geben darf!
Also kann der Index der Wurzel also nicht der "Einstiegspunkt" sein oder?

2)Wie ist das mit "Zwei Knoten dürfen niemals den gleichen Anfangsindex haben" gemeint?

Ich mein, ich hab da zum Schluss (Skriptum) zum Beispiel:

Index: 1 2 3 4 5 6 7 8 9 10
c: T T T F F T F T T T
end: a a c d d a d b d a
next: N 7 4 6 1 N 10 4 N N
Index der Wurzel = 2
Na da hab ich doch eh lauter verschiedene Indizes oder? Also von 1 - 10? Aber das iss doch nicht gemeint?

Ich habe da sowas im Forum gelesen mit einem Beispiel

A1 C1
B2 D2
1 2 3 4
A B C D
3 4 / /
Da dürfte man dann angeblich nicht so machen
1 2 3 4
A B C D
3 4 / /

Sorry, falls das jetzt nicht eindeutig rüberkommt, aber falls unverständlich, bin ich auch schon mit einer Allgemeinen erklärung zufrieden - vielleicht kann jemand ein Beispiel angeben, wie man es NICHT machen darf, und wie man es machen muss.

Und wie iss das mit der Wurzel?

Danke danke danke,

Please god of algorithm, let somebody answer in T(n) = O(1hour) for n in {I don't care}

derSeb

[mjx_biz]

ad 1)

Ich vermute, dass der Index der Wurzel aus folgendem Grund 2 ist:
Beim Indexed Trie (von dem man ausgeht), ist die erste Tabelle die mit

a b c d
t f f f
/ /
. Die wird so "gepackt", dass sie im endgültigen Packed Trie bei Index 2 anfängt. So hab ich mir das halt zusamengereimt :idea:.

ad 2)

Der Index jeder Tabelle beginnt an der Stelle, wo diese im Packed Trie eingefügt wurde. Im Skriptum hat also Knoten (1) den Index 2, Knoten (2) den Index 7 usw.

Wenn du es anhand des Wortes "da" machst, musst du bei Index 5 anfangen. Da dort das Wort nicht enden darf, musst du zum Index 1 weiterschauen (steht beim next-Verweis), denn dort beginnt der Knoten (2). Dort darf das Wort enden und es gibt auch keinen Eintrag bei next.

1h = O(1h20m) :)

Achja, viel Glück morgen ;). Wir machen das schon :D!

[IRBaboon]

ad Wurzel: Der Wurzelknoten ist ein Knoten wie jeder andere, der mit der selben Heuristik in das grosse Array gepackt wird, eben wie alle anderen Knoten auch. Entsprechend muss der Wurzelknoten nicht unbedingt bei Index 0 (oder 1) liegen sondern kann irgendwo sein. Ist ja auch prinzipiell egal, man muss halt nur wissen, wo, und in dem Beispiel ist es halt Pos. 2.

ad gleicher Index: Wenn du zwei Knoten "ineinander packst", dann erkennst du, ob ein entsprechender Index (und damit die dort hinterlegten Daten "Wortende" bzw. "Verweis auf Nachfolgeknoten") auch wirklich zu dem Knoten gehoert, am dort gespeicherten Buchstaben. Naja, und jetzt sollte das Problem erkennbar sein: Wenn 2 Knoten mit dem selben Startindex existieren, dann kannst du anhand des gespeicherten Buchstabens nicht mehr unterscheiden, zu welchem Knoten die Daten gehoeren.
Speichert man 2 Knoten am selben Index ab, dann macht man eigentlich sowas wie eine "Suffix-Compression", wobei, in diesem Fall nicht gewollt, mit unterschiedlichen Daten, also genauer eigentlich eine "Suffix-Verschmelzung".

Ach ja, was auch gerne falsch gesagt / gemacht wird: packed Trie hat NICHTS mit Suffix-Compression zu tun! Natuerlich, wenn man einen Trie moeglichst kompakt haben moechte, wird man vor dem Packen auch die Suffix-Compression durchfuehren, aber prinzipiell ist das NICHT notwendig! Und es gibt ja auch Anwendungen fuer Packed Tries ohne Suffix-Compression (z.B. dynamische Tries).

I.R.Baboon

[mjx_biz]

Ok, ganz so gut wie IRBaboon hab ich das wohl nicht hinbekommen mit der Erklärung *g*.

Und wie sieht es mit der Prüfung heute aus? Was kommt da :D?

[matrium]

für das wissen was heute kommt würde ich töten :D

[mjx_biz]

für das wissen was heute kommt würde ich töten :D

Ich würds auch ganz umsonst nehmen :shinner:.

[IRBaboon]

Ich sag nix, ich verbrenn mir nicht die Zunge ... :engel:

[matrium]

oh nooo packed trie ist ja wirklich gekommen! i dislike very much

generell war der test aber sehr fair/einfach.. ich war einfach nicht genug vorbereitet glaub ich.. z.b. quadratisches sondieren.. ist watschn-einfach, hab ich mir aber einfach nicht angesehen weil ich dachte kommt bestimmt eh nur double hashing.. haha :)
auch sonst hab ich ziemlich alles falsch gemacht was man falsch machen konnte, also ich habs ziemlich sicher nicht geschafft :(

[mjx_biz]

Hab die Prüfung auch recht fair gefunden, vor allem nachdem mein erster Versuch total in die Hose ging. Aber beim Packed Trie hab ich mich zum Schluss vertan ... und vorher noch groß geredet *g*.