Say I have two sets, set1 = {a,b,c,d,e,f} and set2 = {a,b,c,d,e,g}. Rather than expressing these explicitly, I want to create something like
common = {a,b,c,d,e}
set1 = common + f
set2 = common + g
If we wanted to represent {a,b,c,h}, we could represent it as common - d - e + h.
My goal is basically to be able to generate the optimal common portion to be used. With only one common section this isn't too challenging, but I need to allow more than one (but not unlimited, or the benefits gained would be trivial).
By optimal, I mean "least number of elements expressed". So in the above example, it "costs" 5 (number of elements) to make the common variable. Then sets 1 and 2 both cost 2 (one to reference common, one to add the extra element), totalling 7. Without the substitution, these would cost 12 to store (6 elements each). Similarly, in subtracting an element from a referenced would "cost" 1.
Another example,
{a,b,c,d}, {a,c,d,e}, {e,f,g,h} and {e,f}
could be
common1 = {a,c,d}
common2 = {e,f,g}
set1 = common1 + b
set2 = common1 + e
set3 = common2 + h
set4 = common2 - g
By allowing multiple common portions this becomes a lot more challenging. Is there a name for this type of problem, or something similar? It seems like it could be related to compression, but I haven't been able to find too many resources on where to start with this.
Some other details that may be relevent:
- Being allowed to reference multiple common portions to represent one set can be valid, but isn't required.
- For my use case, the sets will typically be around 20 elements and around 10 different sets.