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$.

Improve this question
$\endgroup$
5
  • $\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
    Commented Jun 14, 2014 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
    Commented Jun 14, 2014 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
    Commented Jun 14, 2014 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
    Commented Jun 17, 2014 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
    Commented Jun 17, 2014 at 13:40

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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$
    – greg
    Commented Jun 15, 2014 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
    Commented Jun 16, 2014 at 21:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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