Set Vereinfachung

Question

Angenommen, ich habe zwei Sätze, set1 = {a,b,c,d,e,f} und set2 = {a,b,c,d,e,g}. Anstatt diese explizit zum Ausdruck, ich so etwas wie

common = {a,b,c,d,e} 
set1 = common + f 
set2 = common + g 

erstellen möchten Wenn wir vertreten {a,b,c,h} wollten, könnten wir es als common - d - e + h darstellen.

Mein Ziel ist grundsätzlich in der Lage, den optimalen gemeinsamen Anteil zu generieren, der verwendet werden soll. Mit nur einem gemeinsamen Abschnitt ist dies nicht zu schwierig, aber ich muss mehr als einen zulassen (aber nicht unbegrenzt, oder die Vorteile wären trivial).

Mit optimaler meine ich "kleinste Anzahl von Elementen ausgedrückt". Also im obigen Beispiel "kostet" 5 (Anzahl der Elemente) die Variable common variabel zu machen. Die Sätze 1 und 2 kosten beide 2 (eins zum Referenzieren, eins zum Hinzufügen des zusätzlichen Elements), insgesamt 7. Ohne die Ersetzung würden diese 12 speichern (je 6 Elemente). In ähnlicher Weise würde ein Element aus einem referenzierten in Subtrahieren „Kosten“ 1.

Ein weiteres Beispiel, {a,b,c,d}, {a,c,d,e}, {e,f,g,h} and {e,f}

common1 = {a,c,d} 
common2 = {e,f,g} 
set1 = common1 + b 
set2 = common1 + e 
set3 = common2 + h 
set4 = common2 - g 

Indem mehrere gemeinsame Abschnitte könnte dies viel schwieriger wird. Gibt es einen Namen für diese Art von Problem oder ähnliches? Es scheint, dass es mit der Komprimierung zusammenhängen könnte, aber ich konnte nicht zu viele Ressourcen finden, um damit anzufangen.

Einige andere Details, die relevent werden können:

• dürfen mehrere gemeinsame Abschnitte referenzieren einen Satz darstellen kann gültig sein, aber nicht erforderlich ist.
• Für meinen Anwendungsfall werden die Sätze in der Regel etwa 20 Elemente und etwa 10 verschiedene Sätze sein.

Answer 1

Sie können alle atomaren Sets finden, das sind alle Sets, die nie getrennt voneinander gesehen werden.

Dies ist ein wenig näher, aber es löst nicht den minimalen Abbau.

Ich denke nicht, dass Sie das minimale finden können, weil ich vermute, dass es NP-Hard ist. Wenn Sie eine Menge S betrachten und ein Diagramm erstellen, in dem jede mögliche Teilmenge von S ein Knoten G ist. Geben Sie nun eine Knotengewichtung entsprechend der Länge der Teilmenge an und zeichnen Sie eine Kante zwischen jedem Knoten, die der Änderungsmenge entspricht. {abc} -> {a} hat eine Gewichtung von 2. {bcd} -> {abe} hat eine Gewichtung von 4. Um nun eine minimale Lösung für das Common-Set-Problem zu finden, müssen Sie einen minimalen Spannbaum finden, der die Deckung abdeckt Jedes der Sets, an denen Sie interessiert sind. Wenn Sie feststellen, dass Sie damit ein minimales gemeinsames Set erstellen können, wären diese gleichwertig. Das Auffinden eines minimalen Gewichtsbaums in einem Knoten-gewichteten Diagramm wird als Knoten-gewogenes Steinerbaum-Problem bezeichnet. Ein Knoten-gewichtetes Steinerbaumproblem kann dem Steinerbaumproblem gleichgestellt werden. Das Steiner-Tree-Problem kann sich als NP-Hard zeigen. Ich vermute also stark, dass das Problem, das Sie lösen wollen, NP-Hard ist.

http://theory.cs.uni-bonn.de/info5/steinerkompendium/node15.html

http://theory.cs.uni-bonn.de/info5/steinerkompendium/node17.html