# Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$

More precisely: The input is set of $M$ sets (most likely stored sequentially on disk) that contain partitions of the set $\{1..N\}$. I want to efficiently (as far as memory and time complexity goes) represent this structure. Let's call this hypothetical structure $S$. I need the structure to support just a single function $p : S \times \{1 \ldots N\} \rightarrow \{1 \ldots M\}$.

It's also safe to assume that I will call this function in order, meaning I will be interested first in $p(S, 1)$, then in $p(S,2)$, etc.

I can represent this structure as an array of $N \times \lceil log_2(M)\rceil$ bits, but that seems too memory inefficient when $M$ is small and $N$ is in billions. I have a hunch that perfect-hashing might be of use here.

• Perfect hashing won't help you here; if the distribution of values in the codomain is flat and random (i.e. there are no correlations higher than zero-order), any perfect hash function which represents the function exactly must itself require at least $N \log M$ bits for its representation. – Pseudonym Sep 27 '14 at 14:42
• Just to clarify, are the partitions of 1..N sequential or arbitrary? Eg is a partition {{1,3},{2}} of {1,2,3} allowed? – jkff Sep 29 '14 at 6:17
• Sadly arbitrary, otherwise I could represent the data in O(M), which would have been ideal. – TheCuriousOne Sep 29 '14 at 6:24

You can reduce your $N \lceil \log_2 M \rceil$ bits to $\lceil N \log_2 M\rceil$ by using Dodis et al's "Changing Base without Losing Space".

I don't think you're going to get much smaller than $N \log_2 M$ bits. For $N \gg M$, many functions will be surjective. In particular, there are $\{{N \atop M}\}$ surjective functions, which is at least $M^{N-M}$. Thus, at least $\log_2 \left(M^{N-M}\right) = N \log_2 M - M \log_2 M \in \Omega(N \log_2 M)$ bits must be used to represent one, on average.

• Given that it will be called in order, arithmetic coding will also do the trick. – Pseudonym Sep 27 '14 at 14:38
• Thanks. @Pseudonym could you elaborate, please? I do not see how calling in order relates to the arithmetic coding. – TheCuriousOne Sep 28 '14 at 14:56
• Think of compressing a file via your favourite compression tools, like zlib. Tools like that support compressing and decompressing a file in order from start to finish. This is basically the same as calling the function in order. You have to get trickier if you need random access. – Pseudonym Sep 29 '14 at 2:29

You essentially want to store a compressed string of size N, with characters from an alphabet of size M. I suspect that wavelet trees http://www.dcc.uchile.cl/~gnavarro/ps/cpm12.pdf may be exactly what you need. They are a "succinct data structure", which means they take almost the information-theoretically optimal amount of space.

• Yes, that is another way to phrase it. I will take a look, thanks for the suggestion. – TheCuriousOne Sep 29 '14 at 6:25
• You may want to read about "rank/select dictionaries" first - they are a key primitive used in wavelet trees, and generally a very useful data structure (e.g. you can partition a range 0..N and look up which range a number belongs to in essentially O(1), which is actually much faster than binary search not only in theory but in practice). – jkff Sep 29 '14 at 16:07