Comment on Runtime's (GetDataBack) 'Fragmented files are not recoverable'

Runtime (developers of GetDataBack) list their expectations and estimates for recovery success in an article here

While in most part well-written, their section of fragmentation says:

As annoying as it is, ... [fragmented] files are unrecoverable.

There is no automated data recovery software available that can solve fragmentation satisfactory. If you want to recombine a file consisting of 10 clusters on a 20 GB drive you must analyze, given a cluster size of 32 KB, all possible combinations of one known cluster with 9 other clusters out of possible 625000. There are 6250009 possible combinations, a number with 52 digits.

The only possible and more intelligent approach is a "manual" data recovery for a particular file.

Even data recovery service companies will most likely not produce better results.

Putting aside the fact that I know the files are recoverable, because for some while I do these recoveries routinely, the calculation is not correct.

Given there are M clusters in file, and N clusters on the disk, the naïve approach is indeed to try N(M-1) combinations and see which of them produces a valid file. Obviously, this implementation is too slow. What's worse it is error-prone - the validation routine is bound to produce some false positives should you try to validate too many different candidate files.

However, there other factors at play, and there are algorithms which are not nearly that slow:

  • File is unlikely to be fragmented so much as to have no adjacent clusters at all.
  • There is no need to try and determine all clusters simultaneously, in one go. In most files, we can look for clusters in turn. This changes required number of tests from N(M-1) to N*(M-1). It is still bad, but not nearly as bad as before.
  • If the file format allows to detect long continuous fragments, the effort is reduced even further.

The conclusion is that while the task is indeed computationally enormous, it is not untractable, especially for media of practical size like memory cards.

Created Wednesday, January 24, 2018

Updated 20 May 2018