3
$\begingroup$

Let's say that I have a file that I really don't want to lose.

I want to convert the original file into $n$ files in the way that will allow me to recover the original file if I have any $m$ of the converted files. I want an algorithm that will solve this problem for any given $m$ and $n$, where $0 < m < n$.

A trivial way to do it would be to just have $n$ copies of the original file but I want the converted files to be as small as possible.

Is there a name for the problem that I am trying to describe? I tried googling things like "redundant encoding" but I was not able to find what I am looking for. Error-correction algorithms seem to deal with some bits of the file lost or corrupted but in my case each of the converted files is either lost completely or fully available and uncorrupt.

I would really appreciate if someone would tell me where to look for existing approaches to solving this problem. Thanks in advance!

$\endgroup$
2
  • $\begingroup$ RAID revisited? $\endgroup$
    – greybeard
    Dec 3 '21 at 17:58
  • $\begingroup$ @greybeard the idea is kinda similar, but I'm not sure if RAID algorithm can provide an arbitrary level of redundancy $\endgroup$
    – vovanz
    Dec 4 '21 at 8:02
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ This is easier than erasure coding, since the erased bits are not arbitrary. Also, erasure coding is mentioned by the OP, when they mention algorithms handling bits which are "lost". $\endgroup$ Dec 3 '21 at 20:27
  • $\begingroup$ @YuvalFilmus, erasure coding works on erasure of symbols, not just erasure of bits. Here each file represents a single symbol. $\endgroup$
    – D.W.
    Dec 3 '21 at 20:35
  • $\begingroup$ It's still a rather unorthodox setting, since the alphabet is huge. $\endgroup$ Dec 3 '21 at 21:42
  • 1
    $\begingroup$ @YuvalFilmus, definitely. Your construction is in the Wikipedia article on erasure codes: en.wikipedia.org/wiki/Erasure_code#General_case $\endgroup$
    – D.W.
    Dec 3 '21 at 22:12
2
$\begingroup$

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 this chunk as $P(i) \bmod p$.

The idea is that given the values of $P(i)$ for $m$ many values of $i$, we can use Lagrange interpolation to recover $a_0,\ldots,a_{m-1}$. This amount to solving a certain system of linear equations.

For the experts: we can use any finite field of size at least $n$. If we choose a finite field of characteristic 2, then computations become more difficult, but the encoding scheme becomes completely lossless.

$\endgroup$
1
  • $\begingroup$ Actually, this is exactly the algorithm I was thinking about when I asked this question. I came up with it when I was reading about Shamir's Secret Sharing that also uses Lagrange polynomials. But I thought, surely, I am not the first one to think about it so I decided to try and find the generalized problem and read about existing approaches. $\endgroup$
    – vovanz
    Dec 4 '21 at 8:11

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.