# Creating a large surjective dictionary without repeated elements?

I would like to have a surjective dictionary that saves the following associations

{a[1]->a[1]+a[2]+..., a[2]->a[1]+a[2]+..., ...,
b[1]->b[1]+b[2]+..., b[2]->b[1]+b[2]+..., ...,
...}


So basically, each element a[i] or b[i] etc refers to the sum of all a[i] or b[i] etc respectively. Clearly, there is no need to save the sum a[1]+a[2]+... for each a[i] key separately, since they are always the same. Is there a way to save it only once and instead provide some sort of "pointer" to it in the dictionary?

Yes, that is possible. We start with a very redundant association rules.

n = 1000;
rules = Association[
Join @@ Map[Thread[# -> Total[#]] &, {Array[a, n], Array[b, n]}]
];


Next, we find the set of all values and create an Association named valuetable with consecutive integers as keys. (We could also use a simple List for that.) Afterwards, we look up which "pointer" key to assign to the keys in rules, store that in keytable and create a rudimentary query function dictionary which would look like the actual dictionary for the user.

With[{duplicatefreevals = DeleteDuplicates[Values[rules]]},
Range[Length[duplicatefreevals]],
duplicatefreevals
];
keytable =  With[{
duplicatefreevals,
Range[Length[duplicatefreevals]]
]
},
];
];
dictionary[query_] := valuetable@keytable@query;


Let's compare the ByteCounts:

ByteCount[rules]
ByteCount[valuetable] + ByteCount[keytable]


144810376

512992

We can access, e.g. the entry of a[6] by dictionary[a[6]].

There is also a slightly different that exploits that Association has the attribute HoldAllComplete. The only tweak, is that we map valuetable over Range[Length[duplicatefreevals]] before we define valuetable. This way, we can call keytable now dictionary are skip the definition of the query function:

With[{duplicatefreevals = DeleteDuplicates[Values[rules]]},
ClearAll[valuetable];
dictionary = With[{
repo =
duplicatefreevals,
valuetable /@ Range[Length[duplicatefreevals]]]
},
];
valuetable =
Range[Length[duplicatefreevals]],
duplicatefreevals
];
];
dictionary // Short


On the pro side: We can put queries to dictionary in the same way as for every other Association without further coding.

On the con side: dictionary is a tiny bit bigger than before:

ByteCount[dictionary] + ByteCount[keytable]


831600

More importantly, it may be not as robust since, e.g., Maping anything onto dictionary will evaluate values; I am not sure if this is always desireable...

Edit

The OP had the very good idea to also write an interface for appending entries subsequently. I take the freedom to incorporate this in a data type dictionary:

ClearAll[dictionary]
SetAttributes[dictionary, HoldAll];
toDictionary[rules_] := Module[{$dictionary},$dictionary =
With[{duplicatefreevals = DeleteDuplicates[Values[rules]]},
With[{repo =
Range[Length[duplicatefreevals]]]},
Association[
"ValueTable" ->
duplicatefreevals],
"ValueIndex" ->
Range[Length[duplicatefreevals]]],
"KeyTable" ->
]
]
];
dictionary[$dictionary] ]; dictionary /: dictionary[$dictionary_][query__] := With[{
keytable = $dictionary[["KeyTable"]], valuetable =$dictionary[["ValueTable"]]
},
valuetable[keytable[query]]
];

dictionary /: ByteCount[dict : dictionary[$dictionary_]] := ByteCount[$dictionary];

dictionary /: associateTo[dictionary[$dictionary_], key_ -> value_] := With[{ pos = ($dictionary[["ValueIndex"]])[value]
},
If[MissingQ[pos],
With[{i = Length[$dictionary[["ValueTable"]]] + 1}, AssociateTo[$dictionary[["ValueTable"]], i -> value];
AssociateTo[$dictionary[["ValueIndex"]], value -> i]; AssociateTo[$dictionary[["KeyTable"]], key -> i];
],
AssociateTo[\$dictionary[["KeyTable"]], key -> pos];
]
];


New is the "ValueIndex" which we employ to find out quickly if a certain value is alread know and what its repective number is. Unfortunately, this increases the size of the data container a bit. That may be only neglected if there are really only few different values compared to the number of keys that have to be stored. Here a short usage example:

n = 5;
rules = Association[Join @@ Map[Thread[# -> Total[#]] &, {Array[a, n], Array[b, n]}]];
dict = toDictionary[rules];
ByteCount[dict]
associateTo[dict, c[4] -> Total@Array[c, n]]
ByteCount[dict]
associateTo[dict, d[1] -> Total@Array[a, n]]
ByteCount[dict]
dict[c[4]]

5056

6336

6592

c[1] + c[2] + c[3] + c[4] + c[5]

• Is there a way to generate the optimized dictionary "on-line" as entry bunches a[i] or b[i] etc become available, by adding them one after another? I would rather not construct the entire rules object before saving it to a better dictionary. – Kagaratsch Mar 5 '18 at 13:38

Do you intend to manipulate the association at some point? Otherwise I'd suggest defining a function:

dict[f_[_Integer]] := Plus@@Array[f, 3]


So dict[a[2]] gives a[1] + a[2] + a[3]. The number of terms in the sum is specified by the second argument of Array`.

• Problem is, in my actual example all the terms of the dictionary would be more complicated to generate and would create an overhead, which is why I'd like to save them in a dictionary in the first place. – Kagaratsch Mar 4 '18 at 20:25