Moin!

Horst_H hat folgendes geschrieben:

der geneigte Leser hätte das gern mal auf deine Datei angewendet gesehen.

Gerne ich habe einen Ergebnis-Viewer angehangen (ist halt nur in einem TreeView sinnvoll betrachtbar - wobei man eigentlich mit der "Lösung" nix anfangen kann, wenn man es mit den anonymisierten Daten sieht... noch dazu weiß ich nicht, ob die dieser Auswertung zugrundeliegende Datenmenge noch der Beispielliste oben entspricht... )

cu
Narses

Zwei Anmerkungen / Fragen:
Der obige Beispiel-Baum kann doch gar nicht korrekt sein? Und mit Huffman kann dieser auch gar nicht dargestellt werden denn:

1) Huffman ist doch ein Binärbaum, demnach kann man A/B/C mit 1/2/3 nicht wirklich darstellen (jedenalls wie du es in dem Beispiel gemacht hast) 9 gehört ja eben nicht zur Menge #1
2) Die 8 kommt doppelt vor -> Huffman hat jeden Wert jedoch nur einmal -> Der Beispiel-Baum (auch wenn ich es mir nicht genauer angeschaut habe) muss falsch sein.

Edit: hab jetzt erst die Darstellung verstanden
Trotzdem braucht man für A=1, B=2, C=3 3-Äste

Moderiert von Narses: Smily repariert

Moin!

uall@ogc hat folgendes geschrieben:

Huffman ist doch ein Binärbaum

OK, es mag kein Huffman-Baum sein, ich bin lediglich beim Betrachten eines Bildungsbeispiels auf diesen Ansatz "ala Huffman" gekommen.

Wenn du den korrekten Namen für diesen Ansatz kennst, immer her damit.

cu
Narses

Hey,

kann das sein dass ihr mit Kanonen auf Spatzen schießt?
Du hast also eine Menge von Mengen, und wenn's um Zahlen, IP's oder sonstwas geht kann man darauf ja eine Ordnung definieren.
Also baust du dir einen verwurzelten Baum auf, an den linken von der Wurzel ausgehenden Ast hängst du alle Mengen, die (z.B.) die 1 nicht enthalten, an den rechten alle, die die 1 enthalten, usw. usf.
Rekonstruieren kannst du eine Menge dann über die Vereinigung der Elemente von einem Blatt aus hoch zur Wurzel.
Die Laufzeit zum Aufbauen eines solchen Baumes wäre dann durch n*m begrenzt, mit n als die Anzahl der Mengen und m als die Mächtigkeit der Menge, die bei der Vereinigung der Teilmengen entsteht.

Allerdings würde ich dabei die leere Menge als Krücke mit reinnehmen

Hallo Thorsten, besonders kompakt ist der Baum dann allerdings nicht, oder?

Moin!

Thorsten83 hat folgendes geschrieben:

kann das sein dass ihr mit Kanonen auf Spatzen schießt?

Nein, ich denke nicht. Ich "arbeite" inzwischen mit dem Ansatz und es hat sich gezeigt, dass es für meinen Zweck geeignet ist.

Thorsten83 hat folgendes geschrieben:

Du hast also eine Menge von Mengen, und wenn's um Zahlen, IP's oder sonstwas geht kann man darauf ja eine Ordnung definieren. Also baust du dir einen verwurzelten Baum auf, an den linken von der Wurzel ausgehenden Ast hängst du alle Mengen, die (z.B.) die 1 nicht enthalten, an den rechten alle, die die 1 enthalten, usw. usf. Rekonstruieren kannst du eine Menge

Wohlgemerkt: es geht nicht darum, einen Schlüssel effizient aufzufinden, sondern darum, Mengen "sinnvoll" (klar, das ist dann Ansichtssache und zweckabhängig) zusammenzufassen!

Wie alzaimar so schön treffend erkannt hat:

alzaimar hat folgendes geschrieben:

besonders kompakt ist der Baum dann allerdings nicht, oder?

ist das leider wahr, und damit für meinen Zweck unbrauchbar. Aber trotzdem Danke für deinen Vorschlag.

cu
Narses

hmm ok, war wohl ein bißchen voreilig...
Hab das so mal programmiert, richtig schön sind die Bäume wirklich nicht

Falls sich jemand das Trauerspiel angucken will: so wie's momentan programmiert ist muss die Mengenbeispiel.txt im gleichen Verzeichnis wie die .exe sein.