New answers tagged data-compression
2
This is called erasure coding. Here each file represents a single symbol, and erasure codes allow to handle erasure of any $n-m$ symbols, i.e., loss of any $n-m$ files. There are many standard schemes that have been proposed.
2
Let $p \geq n$ be prime, and suppose that $p \leq 2^k$; we would like $p$ to be as close to $2^k$ as possible. Convert your input into chunks of $mk$ bits, and interpret each chunk as $m$ integers $0 \leq a_0,\ldots,a_{m-1} < p$. Define a polynomial
$$
P(x) = a_0 + a_1 x + \cdots + a_{m-1} x^{m-1}.
$$
For $0 \leq i \leq n-1$, the $i$'th copy will encode ...
0
The naive solution may be n log n bits. But for the first number you have n choices; you have n-1 choices for the second number, n-2 choices for the third number etc. So log(n!) bits, rounded up to the next integer, would be a possibility.
In practice, if you want the lookup to be fast, looking up number k should locate a range of bits that represent some ...
1
This is equivalent to storing a permutation of $n$ items in memory. There are in general, $n!$ ($n$ factorial) such permutations, and it is well known that $\log(n!)=\Theta(n\log(n))$. Hence, you will need at least $\Omega(n\log(n))$ bits to represent the permutations (which is what you get from the naive solution).
So without even the requirement about the ...
Top 50 recent answers are included