3
$\begingroup$

Assume we'd like to be able to encode variables $x_1,x_2,\cdots,x_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x_i\leq N$ and $$\sum_{i=1}^{r}x_i=M$$

It's easy to store the variables using $r\log N$ bits, but this doesn't take advantage of the fact that their sum is bounded.

Furthermore, in my application $r$ is not fixed and could vary from $\frac{M}{N}$ to $M$, so I would need $M\log N$ bits in the worst case if I use the naive encoding.

So the questions are as follows:

How many bits are required to encode the variables, given that an adversary picks the values of $r$ and $x_1,x_2,\cdots,x_r$?

Is there an data structure that uses close-to-optimal space for this that supports efficient replacement operations (where replace$(i,j)$ increases the value of $x_j$ by 1 and decrements the value of $x_i$ by 1)?


If it helps, you may assume $M=N$ (which is what I need for my application), but I think it's interesting for general $M,N$.

$\endgroup$
  • $\begingroup$ I'm not an expert, but I think that you can get a good bound if you think that with $M,x_1,...,x_r$ you can encode an arbitrary binary string $y$ of length $|y| = \log M + \log x_1 + ... + \log x_r$; the sum constraint allows each $x_i$ to be $M/r$ so $|y|= \log M + r \log(M/r)$. If you pick $y$ incompressible, then there is no way to do better. $\endgroup$ – Marzio De Biasi Jun 14 '14 at 10:55
  • $\begingroup$ ... a little fix: $|y| = \log M + (r-1)\log(M/r)$ because the last $x_r$ must be use to "pad" the sum to $M$. $\endgroup$ – Marzio De Biasi Jun 14 '14 at 11:08
  • $\begingroup$ @MarzioDeBiasi - As I wrote in the question, $r$ isn't fixed (I'd like to be able to perform "replace" operations). Do you mean I need $\text{max}\{\log M + (r-1)\log(\frac{M}{r}) | r\in \{\frac{M}{N},\frac{M}{N}+1,\ldots,M\}\}$ bits? Do you think of a way I could use such encoding and perform the "replacement" operations in reasonable time (say $O(\log(MN))$)? $\endgroup$ – R B Jun 14 '14 at 12:58
  • $\begingroup$ This seems to be the same question as cstheory.stackexchange.com/questions/24869/… or at least very close. $\endgroup$ – Zsbán Ambrus Jun 17 '14 at 12:19
  • $\begingroup$ @ZsbánAmbrus - it's related but not the same. In the other question I was wondering about a arbitrary set encoding and here I'd like to encode a multi set with fixed number of total elements. While you can use the solution there over here, it'll be inefficient. $\endgroup$ – R B Jun 17 '14 at 13:40
4
$\begingroup$

Answer to question 1: $\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode the variables.

Proof: Count how many ways there are to choose $y_1,\ldots,y_r$ such that $y_i \ge 0$ and $\sum y_i = M-r$. There are exactly $\binom{M-1}{r-1}$ such ways (see e.g. here). Now, if there are only $k$ possible values for a variable, then $\lceil \log k \rceil$ bits suffice to encode that variable. Therefore, $opt=\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode our input.

Answer to question 2: This is a bit more tricky. The best approach is to check the literature on succinct rank-select or other succinct data structures: I suspect you can match the results for succinct rank-select, so to get something like $opt+o(M)$ space and $O(\log M)$ running times for all operations. If you're interested, tell me in the comments and I'll try to look it up and tell you my best guess on what's possible. You might also want to check out Dodis-Patrascu-Thorup for some ideas.

$\endgroup$
  • $\begingroup$ Also, R.B.: since there's a lot of literature on the topic, if you'd like me to check it for you, please say specifically which solutions you'd like over others in the tradeoff. For example, do you prefer a solution with $2M+O(\sqrt{M})$ space and $O(1)$ operation times over a solution with $2M+O(M^{1/3})$ space and $O(\sqrt{M})$ operation times? etc etc $\endgroup$ – mobius dumpling Jun 15 '14 at 0:47
  • 2
    $\begingroup$ Because $x_i \ge 1$ for all $i$, the variables can be encoded in $M$ bits. Just take binary sequence $B$ of length $M$, and set $B[k]=1$, if $\sum_{i=1}^{j} x_{i} = k$ for some $j$. $\endgroup$ – Jouni Sirén Jun 16 '14 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.