H 10.7

Heap
Erstie
Erstie
Beiträge: 18
Registriert: 28. Apr 2009 20:38

H 10.7

Beitrag von Heap »

Im Skript von Härder tauchen zwei verschiedene Digitalbäume auf.
In der ersten Methode werden Schlüssel in den Knoten gespeichert, in der anderen nicht.

Sind beim Lösen der Aufgabe beide Methoden zulässig?

Niggi
Mausschubser
Mausschubser
Beiträge: 82
Registriert: 15. Apr 2009 15:16
Kontaktdaten:

Re: H 10.7

Beitrag von Niggi »

also im härder skript seh ich nur ein baum bei der definition des binären digitalen Suchbaums kapitel 8 seite 8 Abb.8.5

und danach kommt dann die definition des patricia baums, da wird patricia baum mit einem binären digitalbaum mit einwegverzweigungen verglichen, vielleicht kommt daher die verwirrung ,
aber ein binärer digitaler Suchbaum ist kein binärer Digitalbaum mit einwegverzweigung so wird ich das sehen und einfach die Baumdefinition von Abb. 8.5 benutzen. Damit bist du ja eigentlich auf der sicheren Seite weil genau der bei der Definition des binären digitalen suchbaums steht

tobiasp
Mausschubser
Mausschubser
Beiträge: 70
Registriert: 5. Okt 2008 23:08

Re: H 10.7

Beitrag von tobiasp »

Sollen beim binären Radix-Baum die Präfixe aus Buchstaben bestehen, oder aus Bits?

Angenommen, ich füge 'A' und 'E' in den Baum ein: Hätte ich dann in der Wurzel ein Präfix 000 stehen und danach halt die Verzweigung Richtung 0000 = 'A' und 0001='E'. Oder hab ich in der Wurzel kein Präfix stehen, weil die Buchstaben 'A' und 'E' nunmal kein Buchstaben-Präfix haben?

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: H 10.7

Beitrag von ivoch »

Die Präfixe sollen aus Buchstaben bestehen.
tobiasp hat geschrieben:Angenommen, ich füge 'A' und 'E' in den Baum ein: Hätte ich dann in der Wurzel ein Präfix 000 stehen und danach halt die Verzweigung Richtung 0000 = 'A' und 0001='E'. Oder hab ich in der Wurzel kein Präfix stehen, weil die Buchstaben 'A' und 'E' nunmal kein Buchstaben-Präfix haben?
In diesem Beispiel würdest du kein Präfix in der Wurzel haben. Die Zahlen IN einem Knoten sind sozusagen die "Bits-Präfixe*" und diese müssen dann in jedem Knoten stehen. Z.B. bei 0000=A und 0001=E würdest du einen Baum aus einem Knoten (der Wurzel) bekommen, der zwei Kinder/Blätter hat. Rechts würde 'E' stehen und Links 'A'. In der Wurzel würde keine Präfix stehen, sondern nur eine 3, da der letzte Bit entscheidend ist und dieser an Position 3 liegt. Auf der linken Kante würde eine 0 stehen und auf der rechten eine 1.

Wenn du "AA" und "AE" kodieren würdest, würdest du genau denselben Baum bekommen, nur würde in der Wurzel (eigentlich NEBEN der Wurzel) noch eine 'A' stehen, denn diese ist ja an beiden Strings gemeinsam.



* - also die Anzahl von Bits, gezählt vom Anfang des gerade untersuchten Strings bis zum ersten unterschiedlichen Bit, die bei den zwei Unterbäume gleich sind.

sina
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Mai 2009 13:58

Re: H 10.7

Beitrag von sina »

ich habe noch eine kurze frage zu patricia- und radixbaum und den inhalt derinneren Knoten.

Ich denke mein entstandener Baum ist schon richtig,aber ich habe das gefühl,dass derinhalt der inneren Knoten nicht überall stimmt.

Also wenn ich folgende 2 Schlüssel habe bzw. Kodierungen

A: 0101 1101
B: 0101 0011
schreibe ich doch, wenn ich A in den baum einfüge ,in den inneren knoten 7 ? oder doch 8?
Wenn ich dann B in den Baum einfüge oder eben auch weitere Schlüssel, muss ich dann einfach immer schauen,wie viele Bits gleich sind, und diese Zahl dann in den inneren Knoten schreiben?Also bei A und B wäre das zum Beispiel dann 4 .

Im Skript steht ja ,dass man in den inneren knoten immer die Anzahl der Bits schreiben soll,die übersprungen werden können, aber wenn ich mir das Beispiel in den folien s.76 anschaue, dann werden in die inneren Knoten immer die Anzahl der Knoten (aus nebenstehendem binärbaum) in den inneren Knoten des Patricia baums geschrieben,die quasi nur einen Nachbarn haben...

Zeichne ich mir zur b) immer den entsprechenden Binärnbaum(wie in den folien), dann bekomme ich zwar die selbe Position der schlüssel,aber in den inneren Knoten stehen eben an manchen stellen andere zahlen,als wenn ich wie oben beschrieben vorgehe.ich weiß jetzt irgendwie nicht ganz welche der beiden Möglichkeiten richtig ist(falls eine stimmt:-) )

Wie sollte man am besten vorgehen??

Radze
Erstie
Erstie
Beiträge: 21
Registriert: 10. Okt 2008 10:14

Re: H 10.7

Beitrag von Radze »

Hallo

Ich hab ein Problem mit der Aufgabe 10.7 b)
Hier sollen wir ja den schrittweisen Aufbau eines Patricia Baums mit den gegebenen Codierungen darstellen. Das Problem: Es gibt nirgendwo ein Beispiel wie sowas aussehen würde. Jede Darstellung zu P.Bäumen, die ich gefunden habe, zeigt einen fertigen Baum. Wäre nett, wenn jemand mal posten könnte, wies aussieht, wenn man z.B die Knoten:
A : 1100
B : 1001
in einen leeren Patricia Baum einfügt.

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: H 10.7

Beitrag von ivoch »

Radze hat geschrieben:A : 1100
B : 1001
Wenn du sie in dieser Reihenfolge einfügst:

Vor dem Einfügen von "A" ist der Baum leer, also wird A zur Wurzel (und einzigem Knoten). Zur besserer Unterscheidung werden die Blätter im Baum mit Vierecken gezeichnet, und alle anderen Knoten wie gewohnt mit Kreisen. Also zeichnest du einfach einen Viereck, schreibst du "A" drin und fertig.

Jetzt willst du "B" einfügen. "A" und "B" werden somit zu Blättern im neuen Baum und du fügst eine neue Wurzel. Drin steht wie viele Bits du überspringen musst, bevor du zu einem Unterschiedlichen Wert in den beiden Kodierungen gelangst. In deinem Beispiel würdest du also 1 schreiben, da das erste Bit in beiden Schlüsseln identisch ist und das zweite nicht mehr. Der fertige Baum sieht dann wie unten angegeben (nicht lachen, MSPaint machts möglich! :lol: )

Im sina's Beispiel würde der Baum genau so aussehen, nur wird in der Wurzel eine 4 stehen, denn hier sind die ersten 4 Bits identisch und müssen somit übersprungen werden.

Die Zahlen auf den Kanten zeigen an, was der Wert des (n+1)-ten Bits ist (oder in Programmierstil, des Bits auf Index "n" im Array, da man ja hier mit 0 anfängt).

Und nicht vergessen, die Bits auf den Kanten werden mitgezählt, wenn du jetzt einen dritten Schlüssel hinzufügen willst. Z.B. du willst "C" = 1010 hinzufügen - dann musst du links einen neuen Knoten hinzufügen, dessen zwei Blätter dann "B" und "C" sind. Im Knoten wird eine 0 stehen, denn das erste Bit hast du ja schon in der Wurzel übersprungen, das Zweite ist auf der Kante angegeben und das dritte ist schon bei "B" und "C" unterschiedlich.

Bei Radix Bäumen ist es dann wieder anders - hier werden immer nur die Bits des jeweils aktuellen Zeichens verglichen, also fängst du bei jedem neuen Zeichen bei 0 zu zählen, und nicht wie bei Patricia, wo du nur bei der Wurzel bei 0 anfängst. Also wenn du zwei lange Wörter in Patricia einfügst, dessen ersten m Buchstaben gleich sind und jede Buchstabe n Zeichen hast, dann wirst du (n*m)+c in der Wurzel stehen, wobei c die Anzahl der Bits ist, die bei den ersten unterschiedlichen Buchstaben gleich sind. In einem Radix Baum wirst du dagegen höchstens (n-1) in der Wurzel schreiben, dafür aber auch die ersten m gleichen Buchstaben neben der Wurzel.
Dateianhänge
pbaum.PNG
pbaum.PNG (1.71 KiB) 1627 mal betrachtet

Benutzeravatar
olg
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 297
Registriert: 1. Okt 2008 19:24

Re: H 10.7

Beitrag von olg »

ivoch hat geschrieben: Der fertige Baum sieht dann wie unten angegeben (nicht lachen, MSPaint machts möglich! :lol: )
Leicht Offtopic, aber probiere es doch mal mit Graphviz.
http://www.graphviz.org/Download_windows.php

Beispiele hier: http://www.graphviz.org/Gallery.php

Sehr einfache Syntax, besonders für Graphen, Automaten und Flussdiagramme zu empfehlen :)

In deinem Beispiel wäre das wirklich nur das folgende :)

Code: Alles auswählen

digraph untitled
	{
		1 -> A [label ="1"];
		1 -> B [label ="0"];


	}
Danke nochmal für die Gegenüberstellung der beiden Bäume, Patricia Trie habe ich noch was gefunden, aber zu Radix wurde es dann irgendwie knapp und mir war der Unterschied nicht deutlich!
"To Perl, or not to Perl, that is the kvetching." ~Larry Wall

mister_tt
Kernelcompilierer
Kernelcompilierer
Beiträge: 502
Registriert: 29. Sep 2008 15:54

Re: H 10.7

Beitrag von mister_tt »

ivoch hat geschrieben: Und nicht vergessen, die Bits auf den Kanten werden mitgezählt, wenn du jetzt einen dritten Schlüssel hinzufügen willst. Z.B. du willst "C" = 1010 hinzufügen - dann musst du links einen neuen Knoten hinzufügen, dessen zwei Blätter dann "B" und "C" sind. Im Knoten wird eine 0 stehen, denn das erste Bit hast du ja schon in der Wurzel übersprungen, das Zweite ist auf der Kante angegeben und das dritte ist schon bei "B" und "C" unterschiedlich.
Moment... Das wäre aber inkonsistent zu den Folien UND zum Härder-Skript... Folie #76, Härder-Skript S. 201 - gleiches Beispiel. Das erste Bit kann übersprungen werden, weil es bei allen gleich ist, daher die eins in der Wurzel. Für K1 und K2 muss ich nach links, da das zweite Bit eine 0 ist. Dann "stehe" ich auf dem dritten Bit, überspringe das, sowie das vierte, da eine zwei im Knoten steht. Dann komme ich zum letzten Bit, wo K1 eine 0 und K2 eine 1 hat.
Da wird offensichtlich das Bit auf den Kanten NICHT mitgezählt... Kann es sein, dass du dich da vertan hast?

Und beim binären Radix-Baum geben die Folien auch widersprüchliche Informationen... Nach Folie #79 sollen die Anzahl der übersprungenen Bits + 1 (relativ!) angegeben werden. Angeblich sei das konsistent zum Härder-Skript, wobei da klar gesagt wird, dass man angeben soll, welches Bit zu testen ist (was sich für mich nach einer absoluten Angabe anhört)... Was ist denn nun richtig??

Prinzipiell schon doof, wenn eine Hausaufgabe gestellt wird, bei der man Dinge anwenden soll, die nicht ausreichend gelehrt wurden... Widersprüchliche Folien / widersprüchliches Skript, keine Gruppenübung dazu... Poor...

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: H 10.7

Beitrag von ivoch »

Erm, ich habe den Härder Skript nicht, aber auf Folie 76 wird der Patricia Baum doch genau so aufgebaut, wie ichs in meinem vorigen Beitrag erklärt habe. Sogar du erklärst es genau so:
mister_tt hat geschrieben:Moment... Das wäre aber inkonsistent zu den Folien UND zum Härder-Skript... Folie #76, Härder-Skript S. 201 - gleiches Beispiel. Das erste Bit kann übersprungen werden, weil es bei allen gleich ist, daher die eins in der Wurzel. Für K1 und K2 muss ich nach links, da das zweite* Bit eine 0 ist. Dann "stehe" ich auf dem dritten Bit, überspringe das, sowie das vierte, da eine zwei im Knoten steht. Dann komme ich zum letzten Bit, wo K1 eine 0 und K2 eine 1 hat.
Da wird offensichtlich das Bit auf den Kanten NICHT mitgezählt... Kann es sein, dass du dich da vertan hast?
* - also zählst du doch das Bit das auf den Kanten steht


Zu Radix-Bäumen hatte ich gar nicht im Skript geschaut, da meine eigene Lösung den meisten Beispiele im Internet UND der Musterlösung dieser Übung entsprach und deswegen dachte ich, dass die Erklärung in den Folien/Härder auch genauso hätte sein sollen. Jetzt habe ich mal nachgeschaut und du hast tatsächlich Recht, was der Information in den Folien angeht. Im Härder Skript ist es aber dann wieder richtig, wenn es genauso erklärt wird, wie du sagst. "Welches Bit zu testen ist" bedeutet "Anzahl der übersprungenen Bits + 0", wenn man die Aussage in "Folien-Sprache" übersetzt ;) (also wenn man von 0 anfängt zu zählen). "Relativ" ist es aber auf jeden Fall, auch wenn es im Härder nicht explizit angegeben wurde, denn nur dann machen Radix Bäume überhaupt Sinn. Wenn du nichts überspringst, dann würde doch dein Baum genau wie einen Patricia Baum mit extra Buchstaben/Strings auf manchen Knoten aussehen (die auch wiederum überflüßig sein würden, denn alle nötigen Informationen sind beim Patricia Baum ja schon in den Knoten/Blättern bzw. Kanten enthalten).

Also auf jeden Fall, meine Erklärung von gestern ist genau nach der Musterlösung gerichtet und anscheinend auch nach Härder, also könnt ihr eure Bäume ruhig so aufbauen, wie ich es erklärt habe. :)

sina
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Mai 2009 13:58

Re: H 10.7

Beitrag von sina »

wenn ich das so mache,wie du ivoch beschrieben hast,komme ich jetzt auch auf den in den folien s.76 gezeigten Patricia Baum:-) ich hatte wie gesagt andere Zahlen drin stehen,da ich nicht wusste dass man die kanten mitzählen muss,was aber im grunde schon sinn macht:-)

Kann ich die Zahlen auf den Kanten dann auch hinschreiben,oder lässt man das eher weg??In den Folien stehen die ja leider nicht da.

Benutzeravatar
Le_Coeur
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 135
Registriert: 18. Apr 2009 12:39
Kontaktdaten:

Re: H 10.7

Beitrag von Le_Coeur »

Habe ich hier richtig PATRICIA-Baum gemacht?:)
Dateianhänge
IMG_0090.jpg
IMG_0090.jpg (26.2 KiB) 1522 mal betrachtet

sina
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Mai 2009 13:58

Re: H 10.7

Beitrag von sina »

ich denke die rechte seite des baumes stimmt, aber ich glaube ,dass du auf der linken seite den knoten mit der 4 weglassen kannst und gleich das blatt mit dem code drin hinschreiben kannst...zumindest habe ich das so bei dem beispiel in den folien s.76 gemacht und kam damit auf den baum der auch rauskommen soll...

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: H 10.7

Beitrag von ivoch »

sina hat geschrieben:ich denke die rechte seite des baumes stimmt, aber ich glaube ,dass du auf der linken seite den knoten mit der 4 weglassen kannst und gleich das blatt mit dem code drin hinschreiben kannst...zumindest habe ich das so bei dem beispiel in den folien s.76 gemacht und kam damit auf den baum der auch rauskommen soll...
Genau. Nur du "kannst" den Knoten nicht weglassen, sondern "musst" du es tun. Denn eine Zahl in einem Knoten macht nur dann Sinn, wenn du zwei Unterbäume hast, die du vergleichen kannst.

sina
Windoof-User
Windoof-User
Beiträge: 35
Registriert: 27. Mai 2009 13:58

Re: H 10.7

Beitrag von sina »

ok, dann dürfte jetzt mein Problem mit den "Zahlen in den inneren Knoten" geklärt sein:-) und ich bekomme,dann bei meinem Patricia-Baum auch nicht mehr so große Zahlen vor :D

Danke für die Hilfe,werde jetzt dann auch mal meinen Radixbaum abändern

Antworten

Zurück zu „Archiv“