Vereinigung aller sich überschneidenden Mengen

Question

Bei einer Liste von Objekten mit mehreren Attributen muss ich die Liste der Mengen finden, die durch eine Vereinigung aller sich überschneidenden Teilmengen entsteht.

Konkret handelt es sich dabei um Person-Objekte, die jeweils viele Attribute haben. Ich muss eine Liste von "Master"-Sets erstellen, die auf einer Handvoll eindeutiger Identifikatoren wie SSN, DLN usw. basieren.

Wenn z. B. Person A und Person B dieselbe SSN haben, bilden sie eine Menge i. Wenn dann Person B und C dieselbe DLN haben, bilden sie eine Menge ii. Person D und E haben dieselbe SSN, aber sie (und alle anderen Identifikatoren) stimmen mit keinem der Identifikatoren der Personen A, B oder C überein. Nach dem Zusammenführen aller sich überschneidenden Teilmengen würde ich eine Menge mit den Personen A, B, C und eine weitere Menge mit den Personen D, E erhalten.

Hier ist der Pseudocode für meine Lösung. Ich bin neugierig, ob jemand bereits einen effizienteren Weg gefunden hat, um alle möglichen sich überschneidenden Sätze zusammenzuführen. Denken Sie daran, dass die Verknüpfungen zwischen den Mengen X Personen lang sein können (d.h. wenn A mit B durch die SSN und B mit C durch die DLN übereinstimmt und C mit D durch die SSN und D mit E durch einen anderen Identifikator übereinstimmt, würden die Personen A-E in einer Menge enthalten sein). Nehmen Sie außerdem an, dass die Sprache, in der dies implementiert werden soll, Mengenoperationen unterstützt.

bigSetList = array of all of the uniq Sets
fullyTested = false
while (bigSetList.size() > 1) or (fullyTested is false)
    foreach thisSet in bigSetList  order by size desc
        if count(sets that intersect with thisSet) > 0
            newThisSet = thisSet
            intersectingSets = []
            bigSetList.delete(thisSet)
            foreach testSet in bigSetList
                if thisSet.intersects(testSet)
                    newThisSet.addAll(testSet)
                    intersectingSets.push(testSetID)
                end if
            end
            bigSetList.delete(intersectingSets)
            bigSetList.push(newThisSet)
            bigSetList.sort()
            break
        end if
    end foreach
    fullyTested = true  // have looped through every set in the list and found 0 intersect partners
end

Answer 1

Um meinen Kommentar im ursprünglichen Beitrag zu erweitern, möchten Sie eine Liste von Mengen erstellen, bei der jedes Mitglied einer bestimmten Menge mindestens ein Attribut mit mindestens einem anderen Mitglied dieser Menge teilt.

Naiverweise kann dies entweder durch die Suche nach allen Paaren, die ein Attribut gemeinsam haben, oder durch die iterative Zusammenführung von Paaren, die denselben Partner haben, gelöst werden. Dies wäre O(N^3) (N^2 für die Iteration über die Paare und bis zu N separate Sätze zur Bestimmung der Zugehörigkeit).

Sie können sich dieses Problem auch so vorstellen, dass Sie die zusammenhängender Teil eines Graphen , wobei jedes Objekt und jeder eindeutige Attributwert ein Knoten ist; jedes Objekt wäre mit jedem seiner Attributwerte verbunden. Der Aufbau dieses Graphen würde lineare Zeit in Anspruch nehmen, und man könnte die verbundenen Komponenten in linearer Zeit mit einer Suche in der Breite oder Tiefe ermitteln.

Answer 2

Ich würde vermuten, dass Sie einen relativ kleinen Satz von Attributen für das Person-Objekt haben (im Vergleich zu der Anzahl der Person-Objekte, die Sie in Betracht ziehen). Wenn Sie das mehrmalige Durchlaufen der Liste der Person-Objekte reduzieren möchten, können Sie eine Person nehmen, ihre Attribute in eine Liste bekannter möglicher Verbindungen aufnehmen und dann zur nächsten Person weitergehen. Bei jeder weiteren Person prüfen Sie, ob sie mit einer früheren Verbindung verbunden ist. Wenn ja, fügen Sie ihre eindeutigen Attribute zu den möglichen Verbindungen hinzu. Sie sollten in der Lage sein, alle Personenobjekte in einem Durchgang zu verarbeiten. Es ist möglich, dass Sie einige unverbundene Gruppen in den Ergebnissen haben, daher kann es sich lohnen, die unverbundenen Personenobjekte zu untersuchen, nachdem Sie das erste Diagramm erstellt haben.

Answer 3

Ihre Sammlung könnte also beispielsweise so aussehen:

A { ss |-> 42, dl |-> 123 }
B { ss |-> 42, dl |-> 456 }
C { ss |-> 23, dl |-> 456 }
D { ss |-> 89, dl |-> 789 }
E { ss |-> 89, dl |-> 432 }

Dann würde ich vorschlagen, einen Algorithmus zu verwenden, bei dem Sie mehrere Sammlungen durch schrittweises Zusammenführen oder Einfügen jeder Sammlung in die Mehrfachsammlungen aufbauen:

Iteration 1. Die erste Kollektion wird zur einzigen Multikollektion:

{A} { ss |-> [42], dl |-> [123] }

Iteration 2. Die nächste Sammlung wird mit der ersten zusammengeführt, da SSN bereits vorhanden ist:

{A,B} { ss |-> [42], dl |-> [123,456] }

Iteration 3. Wieder zusammenführen, da die DLN bereits vorhanden ist:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }

Iteration 4. Füge eine neue Mehrfachsammlung ein, da es keine Übereinstimmung gibt:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D}     { ss |-> [89],    dl |-> [789]     }

Iteration 5. Zusammenführung mit der zweiten Multisammlung, da die SSN dort vorhanden ist:

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D,E}   { ss |-> [89],    dl |-> [432,789] }

In jeder Iteration (eine für jede Sammlung) müssen Sie also Folgendes identifizieren todo Mehrfachsammlungen, die gemeinsame Werte mit der zu bearbeitenden Sammlung haben, und führen Sie zusammen todo diese zusammen.

Wenn es n Sammlungen mit jeweils einer konstanten Anzahl k von Attributen gibt, läuft dieser Algorithmus in der Zeit O(nnk) = O(n 2 ). Der ungünstigste Fall liegt vor, wenn alle Attributwerte unterschiedlich sind. Wenn es mehr gemeinsame Attributwerte gibt, wird die Zeit, die für das Einfügen und die Bestimmung der Zugehörigkeit zu den Attributwertsätzen benötigt wird (wie [23,42]), zum dominierenden Faktor, so dass die Attributwertsätze effizient sein sollten.

Wenn Sie optimale disjunkte Mengen dann läuft jeder Such- oder Zusammenführungsvorgang in amortisierter Zeit O(α(n)).

Für jede Iteration gibt es also höchstens n Multisammlungen (die Situation, wenn noch keine Multisammlungen zusammengeführt wurden). Um die neue Sammlung in die Multisammlungen zu integrieren, muss für jede der k Multisammlungen eine Suchoperation durchgeführt werden, um alle zusammenzuführenden Multisammlungen zu identifizieren, was eine durch O(nkα(n)) begrenzte Zeit benötigt. Die Zusammenführung der auf diese Weise gefundenen höchstens k Multisammlungen dauert O(k 2 α(n)).

Für alle Iterationen ist die Zeit also begrenzt durch O(n(nkα(n)+k 2 α(n))) = O(n(nkα(n))) = O(n 2 kα(n)) = O(n 2 α(n)), da k eine Konstante ist.

Da α(n) für alle praktischen Zwecke ebenfalls eine Konstante ist, ist die Gesamtzeit durch O(n) begrenzt 2 ).

Answer 4

while (!people.isEmpty()) {
    Person first = people.get(0);
    people.remove(first);
    Set<Person> set = makeSet(first);
    for (Person person : people) {
        for (Person other : set) {
            if (person.isRelatedTo(other)) {
                set.add(person);
                people.remove(person);
            }
        }
    }
    sets.add(set);
}
for (Set<Person> a : sets) {
    for (Set<Person> b : sets.except(a)) {
        for (Person person : a)
            for (Person other : b) {
                if (person.isRelatedTo(other)) {
                    a.addAll(b);
                    b.clear();
                    sets.remove(b);
                    break;
                }
            }
    }
}

Answer 5

Erstens: Gibt es eine inhärente Hierarchie bei Identifikatoren, und heben widersprüchliche Identifikatoren einer höheren Art den gleichen Identifikator einer niedrigeren Art auf? Wenn beispielsweise A und B dieselbe SSN haben, B und C dieselbe DLN haben und C und D dieselbe SSN haben, die nicht mit der SSN von A und B übereinstimmt, bedeutet das, dass es zwei Gruppen gibt oder eine?

Wenn man davon ausgeht, dass Widersprüche keine Rolle spielen, hat man es mit Äquivalenzklassen zu tun, wie Nutzer 57368 (unbekanntes Google) feststellt. Für Äquivalenzklassen wendet man sich oft an die Unionsfundstelle Struktur. Die Durchführung dieser Zusammenschlüsse ist nicht ganz trivial, da ich davon ausgehe, dass Sie keine direkte Verbindung zwischen A und B haben, wenn A und B die gleiche SSN haben. Stattdessen werden unsere Mengen aus zwei Arten von Elementen bestehen. Jede (attribute type, attribute value) = attribute Paar ist ein Element. Sie haben auch Elemente entsprechend object s. Wenn Sie durch die Liste der Attribute für ein Objekt iterieren, führen Sie die Vereinigung (object, attribute) .

Eines der wichtigsten Merkmale der Union-find-Datenstruktur ist, dass die resultierende Struktur die Menge darstellt. Sie ermöglicht die Abfrage "In welcher Menge ist A?". Wenn dies nicht ausreicht, lassen Sie es uns wissen und wir können das Ergebnis verbessern.

Das wichtigste Merkmal ist jedoch, dass der Algorithmus für jede Vereinigungs- und Abfrageoperation so etwas wie ein zeitkonstantes Verhalten aufweist.