Denkanstösse zu Schnittmengensuche gesucht

[NTB]

Hiho,

ich hätte gerne mal Eure konzeptionelle Hilfe.

Ich habe viele "Resourcen". Jede Resource ist mit mindestens einem "Tag" (Keyword) versehen. Also das, was man unter Tagging versteht. Die Tags werden als Set in Resource-Objekten gehalten.

Gegeben sei ein Set von Tags, und ich möchte alle Resourcen finden, in denen möglichst viele dieser gegebenen Tags vorkommen, auf jeden Fall mindestens eins.

Wie kann ich das schlau angehen?

Die Resourcen zu finden, in denen das komplette Set vorkommt wäre mit Set.containsAll ja kein Problem...
...trifft leider nicht, was ich brauche


Falls das noch nicht verständlich genug war, ein bischen Pseudocode:

class Resource {
   Set<Tag> tags
}

class Tag {
   String name
}

main {
   Resource merkel
   merkel.setTags("CDU","Frau","süss","Politik","blond")
   Resource schreinemakers
   schreinemakers.setTags("Fernsehen","blond","Frau")
   Resource frings
   frings.setTags("Fussball","Fernsehen","mann")


   findResourcesForTags("Frau","blond",CDU")
   findResourcesForTags("Fernsehen")
   findResourcesForTags("Frau","blond")
}

Wie implementiere ich schlau mein "findResourcesForTags"? Hat da jemand eine schlaue Idee?

 

[Wildcard]

Man könnte sich da was Lucence abschauen oder Lucence direkt verwenden.

 

[Ariol]

Wärs nicht am einfachsten wenn du die Methode als findResourcesForTags(String[] args) definierst?

Damit kannst du dann beliebig viele Such-Strings angeben.

 

[Marco13]

Prinzipiell kannst du Schnittmengen zwischen Sets bilden - mit retainAll.

Set X = { A, B, C, D }
Set Y = { C, D, E }
X.retainAll(Y);
X = { C, D }

Die Größe des ergebnisses ist dann der Wert, auf dem die Entscheidung basiert. Besonders effizient ist das aber vermutlich nicht. Die gemeinsame Elemente per Hand zu zählen könnte schneller sein (und auch nicht viel komplizierter...)

 

[Marco13]

@Ariol: Das Zauberwort heißt "varargs":

findRessource(String ... x) {...}

findRessource("A"); // OK
findRessource("A", "B"); // OK
findRessource("A", "B", "C"); // OK

 

[NTB]

Man könnte sich da was Lucence abschauen oder Lucence direkt verwenden.

Soll nicht kleinlich wirken, aber ich will Mißverständnisse vermeiden:
Du meinst Lucene (mit nur 1x c) oder?

@Ariol:
Das war Pseudocode, um zu veranschaulichen, was ich möchte.
Ich übergebe gar keine Strings, sondern ein Set von Tags

 

[Wildcard]

Man könnte sich da was Lucence abschauen oder Lucence direkt verwenden.

Soll nicht kleinlich wirken, aber ich will Mißverständnisse vermeiden:
Du meinst Lucene (mit nur 1x c) oder?

Ja, vertippt

 

[NTB]

Prinzipiell kannst du Schnittmengen zwischen Sets bilden - mit retainAll.

Set X = { A, B, C, D }
Set Y = { C, D, E }
X.retainAll(Y);
X = { C, D }

Das war tatsächlich exakt, was ich gesucht habe. Dankeschön. Doof ist dabei nur, dass retainAll nicht die Schnittmenge zurückgibt, sondern das Original verändert. D.h. bevor ich retainall mache, muss ich noch das originale Set kopieren. Das ist natürlich alles sehr teuer...

 

[Marco13]

Wie gesagt - anders ist es auch nicht viel schwerer. Pseudocode:

private int computeIntersectionSize(Set a, Set b)
{
    int intersectionSize = 0;
    for (Object x : a)
    {
        if (b.contains(x)) intersectionSize++;
    } 
    return intersectionsSize;
}

Resource findResource(Set tags)
{
    Resource best = null;
    int bestValue = -Integer.MAX_VALUE;
    for (all resources r)
    {
        int value = computeIntersectionSize(r, tags);
        if (value > bestValue)
        {
             best = r;
             bestValue = value;
        }
    }
    return best;
}

 

[NTB]

danke, ich werde mal ausprobieren.