Suche geeignete Datenstruktur

[SamHotte]

Moin,

kennt jemand eine gute Datenstruktur für ein 2-dimensionales Array, das mit booleschen Werten besetzt wird und "schwach besetzt" ist?

Hintergrund: ich habe einen Baum mit ca. 3500 Einträgen sowie ein Array mit Suchergebnissen, die zu den gesuchten Einträgen passen (Suche über 1..n Einträge). Suchergebnisse sind momentan ca. 700 möglich.

Der erste Versuch war, ein 2-dimensionales Array zu bauen. Das Problem ist, dass ich nicht dieses Riesenarray mit wenigen "true"-Einträgen verwenden möchte, sondern etwas möglichst geschicktes; es soll aber trotzdem nach beiden Dimensionen abfragbar sein, damit ich im Ergebnis die zutreffenden Einträge bekomme, aber die Ergebnisdarstellung auch noch nach der Trefferanzahl sortieren kann.

Mit Google finde ich zwar einiges, aber das passt nicht zu meinem Problem ... hat jemand eine Idee?

 

[foobar]

Wie wäre es mit einer Map?

 

[Lim_Dul]

Listenstruktur.

Und zwar für horizontal und vertikal. Jedes Element speichert den Index des nächsten Elements in der gleichen Zeile, sowie den Index des nächsten Elementes in der gleichen Spalte.

Beispiel:

Matrix, * = Eintrag

* - - * - -
- * - - - *
- - - * - -
* - - - - *
- * - - * -

Würde wie folgt aussehen

Das Element in (1,1) hat als Nachfolger horizontal die 4 und vertikal auch die 4
Das Element in (1,4) hat als Nachfolger horizontal null und vertikal die 3.

Verständlich?

 

[SamHotte]

Also zwei Listen, eine für horizontal und eine für vertikal?

Oder eine Liste mit Elementen, die zwei Koordinaten und zwei Nachfolger haben?

 

[AlArenal]

kennt jemand eine gute Datenstruktur für ein 2-dimensionales Array, das mit booleschen Werten besetzt wird und "schwach besetzt" ist?

So doof es auch klingt: Ein Schwarz-Weiß-Foto
Und: Das gute alte TableModel

 

[SamHotte]

Und wie sortier' ich dann nach Zeilen oder Spalten?

 

[AlArenal]

Mit nem Integer für die Anzahl der Treffer pro Spalte und Zeile? Beispielsweise über zwei Maps (eine für Reihen, eine für Spalten) mit dem Index als Key und der Trefferzahl als Value.

 

[SamHotte]

Ich brauch' aber nicht nur die Trefferzahl, sondern auch jedes einzelne Trefferchen für die Darstellung. Kapier' nicht, wie das mit zwei Maps gehen soll :bahnhof:

 

[AlArenal]

Und was gefällt dir an nem Schwarz-Weiß-Bild und nem TableModel nicht? Habe meine passenden Bücher (Algorithms and Data Structures in Java) leider daheim...

 

[SamHotte]

Naja, ich kapier halt nicht, wie das zu meinem Problem passt. Ich beschreib' es nochmal grob:

1. ich hab einen Baum mit Einträgen, und ich habe Dinge, die mit diesen Einträgen verknüpft sind.
2. ich suche nach den Dingen, die mit bestimmten Einträgen verknüpft sind
3. ich möchte folgende Ausgabe:

Ding 1 (17 Treffer)
- (Teil-)Baum mit den 17 Treffern

Ding 2 (12 Treffer)
- (Teil-)Baum mit den 12 Treffern

Ding 3 (11 Treffer)
- (Teil-)Baum

Ding 4 .. x (y Treffer)
- (Teil-)Baum (jeweils)

Daher brauche ich erstmal eine Datenstruktur (schwach besetzte Matrix), in die ich die Treffer eintragen kann, und dann muss ich sie nach Trefferanzahl sortieren, aber dann auch wieder die richtigen Einträge herausfinden können.

Edit: das mit dem S/W-Foto blick' ich nicht wirklich, sorry ;-)

 

[AlArenal]

Nicht böse sien, wenn meine Antowrt etwas doof klingen mag, aber wenn deine "Einträge" (was immer das auch konkret bei dir sein mag) schon mit dem "Ding" im Baum verknüpft sind, was brauchst du dann noch ne Datenstruktur, geschweige denn eine Suche?

Da sind wir nämlich bei der Frage was womit in welcher Richtung und wie verknüpft ist. Bei einer Ding->Eintrag Verknüpfung, ist alles geritzt. Bei einer Ding->Eintrag Verknüpfung muss man halt die Einträge durchlaufen und schauen, was zum gerade aktuellen Ding passt.

Was hats nun genau mit der Suche auf sich? Wonach wird worin gesucht?

Hört sich für mich bisher nach nem normalen TreeModel, evtl. mit ein klein wenig Knoff-Hoff, an.

P.S.:
Ein S/W-Foto ist eine zweidimensionale binäre Matrix...

 

[SamHotte]

Keine Sorge, bin nicht böse, mir ist nur nach dem letzten Post der Internetzugang abgeraucht

TreeModel für den Baum ist schon korrekt, dazu habe ich für jeden Eintrag im Baum potenziell eine n:m-Verknüpfung zu den "Dingen". Die Suche läuft nun so, dass ich eine Anzahl Einträge auswähle und alle Dinge sehen möchte, die mit mindestens einem dieser Einträge verknüpft sind.

Da ich diese Treffer dann noch sortieren möchte, brauche ich eben zur Zwischenspeicherung etwas Matrix-ähnliches. Vor der Sortierung kommt nämlich noch eine Gewichtung, da ein Blatt in der 7-ten Hierarchieebene mehr aussagt (also höher zu bewerten ist) als der Wurzelknoten.

Wenn ich jetzt die Suche starte, dann weiß ich ja noch nicht, wie viele Treffer ich bekommen werde, kann also noch keine Matrix bauen - außer, es gäbe eine schlauere Datenstruktur, analog zur Liste für eindimensionale Daten.

Damit etwas besser erklärt?

 

[AlArenal]

Dummerweise erlischt mit deinem letzten Post die Klarheit, die ich nach deinem vorletzten Post meinte erlangt zu haben

Ich dachte ursprünglich du sucht zu einem Ding im Baum die verknüpften Einträge. Nun liest es sich so, dass zu einer Gruppe Einträge die zugehörigen Dinge im Baum suchst.
Könnte auch babylonisches SPrachgewirr sein. Das kommt dann davon, wenn man den Kindern so doofe Namen gibt

Was immer du da auch suchst: Als was werden die Ergebnisse dann letzten Endes angezeigt? Ich hatte es ursprünglich so verstanden, dass sie als Liste irgendwo im Baum eingehängt werden. Sortierung und Gewichtung wären dann dasgleiche, nur evtl. in zwei Durchlaufen oder mehreren Arbeitsschritten. Wenn du sowohl Sortier- als auch Gewichtungskriterien in Zahlen oder Buchstaben ausdrücken kannst, kannst du daraus eine gemeinsame Zahl der Form [Kat-Nr][Sort-Nr] (beide mit fester Anazhl Stellen) bilden und darüber den Comparator laufen lassen. Auf die Weise ist die Kategorisierung das erste und deine sonstige Sortierung das zweite Sortierkriterium.

Vielleicht kannste auch mal was zeichnen oder hast nen Screenhot, was am Ende rauskommen soll? Hab nämlich schwer den Eindruck, das wir aneinander vorbei reden....

 

[SamHotte]

Sorry, nein. Das im Baum sind die Einträge. Dazu habe ich mehrere hundert Dinge, die mit jeweils ein paar Einträgen verknüpft sind.

Suchen möchte ich nach allen Dingen, die mit bestimmten Einträgen verknüpft sind.

Das Ergebnis soll absteigend sortierbar sein (zunächst nach der puren Trefferanzahl, später nach etwas besserer Gewichtung).
Für jeden Treffer (=gefundenes Ding) möchte ich den Teilbaum sehen, der zutrifft (also die Einträge, nach denen gesucht wurde und die mit diesem Ding verknüpft sind - und nicht alle seine Verknüpfungen).

Mir fällt grad kein hinreichend anonymisiertes alternatives Begriffspaar zu "Einträge" - "Dinge" ein

Edit: zeichnen kann ich das nicht wirklich, aber das macht nix. Das Ergebnis soll eigentlich einfach nur ein scrollbare Liste aus Komponenten sein, in denen drinsteht:

[b]Ding-Name (x Treffer)[/b]
Teilbaum:
Wurzel
+-- bla
     +-- blubb
     +-- blorg

 

[AlArenal]

Hast leider noch nicht damit rausgerückt, wie genau diese "Verknüpfung" implementiert ist. Haben die DInger Referenzen aufeinander, oder musst du nach Attributen wühlen? Im ersteren Fall würde ich vorschlagen die Suche zumindest zu vereinfachen, indem du den Aufbau des Index verlagerst. In den Apache Jakarta Commons gibts ein Projekt Collections. Darin müsste eine BidDiMap liegen, also eine bidirektionale Map. Da kannste in beiden Richtungen suchen.
Wenn du nun bereits beim Lesen deiner Daten / Erzeugen der Objekte zusätzlich diese Map mit aufbaust, ist das Finden von verknüpften Objekten später ein Einzeiler. Da sparst du dir schonmal einen Durchlauf über alle Objekte.

Sortierung machste über Comparator. Den kannste ja später entsprechend erweitern.

Frage der Frage, für den Fall dass es immer dieselbe Suche ist (und man nicht wie in einer Suchmasch9ine nen Arsch voll vorher unbekannter Kriterien eingeben kann): Wieso zum Teufel haben die Einträge im baum keine Referenzen (List) auf die mit ihnen verknüpften Einträge?

Ist doch wesentlich einfacher alles, was man zur Suche braucht schon im Normalbetrieb aufzubauen (wie es einen Datenbank ja auch macht) und den eigentlichen Suchvorgang auf eine Filterung und Sortierung zu beschränken, anstatt dann erst den Index aufzubauen.

 

[SamHotte]

Die Verknüpfung ist eine eigene Relation, in der ich Paare von Primärschlüsseln ablege (n:m). Die Primärschlüssel der Baum-Einträge sind einfache int-Werte, die der "Dinge" sind zusammengesetzt aus int und einem Zeitstempel.

Suchlauf ist nicht immer gleich, sondern ich will jedesmal nach anderen Einträgen suchen können (aus dem Baum).

Die Idee, dass ich jedem Eintrag die Referenzen gleich mitgebe, finde ich nicht schlecht; würde allerdings einiges an der Implementierung des Baums verändern (eines der Probleme ist die Tatsache, dass ich die Baumreihenfolge sicherstellen muss und auch hin- und herschieben von Knoten möglich sein soll -- es werden damit Prozesse dargestellt).

Daher würde ich lieber erstmal einen überhaupt funktionierenden Suchlauf bauen -- der kommt nicht soo häufig vor (außer jetzt beim Entwickeln) und braucht daher nicht performant zu sein.

 

[AlArenal]

Hin-/Herschieben, bzw. Hoch-/Runterschieben ist ja nicht weiter tragisch. Jedem Node ne Referenz auf seinen 'linken' und 'rechten' Node geben, wenn null dann ist man selbst 'ganz links/rechts'. Beim Verschieben innerhalb einer Eben, wie über Ebenen hinweg sind entsprechend nur die Referenzen zu ändern - verkettete Liste eben.

 

[AlArenal]

Und was die Suche angeht:

Bevor du dir da noch groß einen zusammen hampelst, schau dir doch mal JoSQL an: http://josql.sourceforge.net/

 

[SamHotte]

Schon klar, und das steht ja auch bereits. Den Baum würde ich gerne so, wie er ist, belassen. Ich bekomme ja für die Suche ein Array der Eintrags-Primärschlüssel. Ich hab auch bereits eine GUI-Komponente, die mir einen mit so einem Array gefilterten View auf den Baum gibt. Das ist nicht das Problem.

Das Problem ist auch nicht die Suche. Die dauert zwar, aber das kann ich verschmerzen.

Das Problem ist das vernünftige Speichern der Suche, damit ich anschließend die Geschichten mit der Gewichtung einbauen kann. Und die Sortierbarkeit, damit das Suchergebnis nicht einfach alphabetisch ist.

Also brauche ich sowas wie ein zweidimensionales Array (zunächst aus boolean-Werten, denke aber, dass sich das in Richtung int ändern muss wg. der Gewichtung). Nur dass ich das Array nicht initialisieren kann, ehe ich die Anzahl der Treffer habe.

Natürlich kann ich die Suche in zwei Phasen aufteilen: (1) suchen, (2) Array bauen.
Schöner wäre aber eben eine "schlauere" Datenstruktur, nach der ich in diesem Fred suche

 

[SamHotte]

Und was die Suche angeht:

Bevor du dir da noch groß einen zusammen hampelst, schau dir doch mal JoSQL an: http://josql.sourceforge.net/

Danke für den Tipp - ich fürchte aber, das hilft nicht weiter, denn ich brauche später eine Mischung aus dieser Baumverknüpfungssuche und einer Volltextsuche. Da gibt's vermutlich noch nix für.

 

[AlArenal]

Volltestsuche in SQL geht

 

[AlArenal]

Das Problem ist das vernünftige Speichern der Suche, damit ich anschließend die Geschichten mit der Gewichtung einbauen kann. Und die Sortierbarkeit, damit das Suchergebnis nicht einfach alphabetisch ist.

Also brauche ich sowas wie ein zweidimensionales Array (zunächst aus boolean-Werten, denke aber, dass sich das in Richtung int ändern muss wg. der Gewichtung). Nur dass ich das Array nicht initialisieren kann, ehe ich die Anzahl der Treffer habe.

Natürlich kann ich die Suche in zwei Phasen aufteilen: (1) suchen, (2) Array bauen.
Schöner wäre aber eben eine "schlauere" Datenstruktur, nach der ich in diesem Fred suche

Ich sag immernoch: TableModel

 

[SamHotte]

Weiß ich, danke. Brauche aber eher 'ne Lucene-Anbindung ... damit die ToDo's nicht ausgehen

 

[AlArenal]

Weiß ich, danke. Brauche aber eher 'ne Lucene-Anbindung ... damit die ToDo's nicht ausgehen

Dazu hab ich ein nettes eBook gekauft.. ich müsste es aber mal lesen..

 

[SamHotte]

Hab mit TableModel noch nie gearbeitet, da ich an 'ner SWT-Anwendung bastle... werd' ich mir dann wohl mal 'reinziehen. Scheint mir aber auch erst dann zu gehen, wenn ich die Anzahl der Spalten weiß, oder?

Edit: Mist, die addColumn()-Methode übersehen

 

[SamHotte]

Bin mit Lucene noch ganz am Anfang, hab bislang nur die c't/iX-Artikel dazu gelesen. Scheint aber sehr brauchbar zu sein.

 

[AlArenal]

Hab mit TableModel noch nie gearbeitet, da ich an 'ner SWT-Anwendung bastle... werd' ich mir dann wohl mal 'reinziehen. Scheint mir aber auch erst dann zu gehen, wenn ich die Anzahl der Spalten weiß, oder?

Edit: Mist, die addColumn()-Methode übersehen

Wäre dann im Grunde eine Komposition, die ein TableModel beinhaltet und eben noch ein paar Maps, um die Zuordnung von Reihen und Spalten zu Objekten zu machen. Das Interface selber hat keine #addColumn o.ä., braucht es aber auch nicht, denn es hat ja #getRowCount und #getgetColumnCount

 

[SamHotte]

Hatte die auch aus der Default-Implementierung. Ich probier' die mal aus und gebe Bescheid, danke erstmal für die guten Anregungen!