Jak działa deduplikacja?

0

Mamy kilkukilobajtowy blok danych , niekoniecznie równo 4 kiB czy wielokrotność, niekoniecznie zaczynający się na granicy potęgi dwójki, porównuje z drugim blokiem dokładnie tego samego rozmiaru, ale o dowolnym innym położeniu w tym samym lub innym pliku.
Działa na zasadzie haszu cyklicznego, Mamy okno przesuwne, haszujemy nowe bajty i bajty tez mogą opuszczać okno. Ale tu zaczynają się schody, bo oprócz okna kilkukilobajtowego definiuje się dla hasz pewną długość , np 48 bajtów (?). Hasz to wielomian , potrzezba np. 48 bitów , znajduje się w liczbie 64 bitowej i teraz pokazuje wartość dla 48 bajtów a nie całych np. 5000 bajtów? Jak to jest, te 48 bajtów stanowią jakis znacznik w całym większym bloku?
I chciąłbym się coś więcej dowiedzieć o deduplikacji nie bloków kilkukilobajtowych ale kilkudziesięcio-bajtowych (jak SampleByte)

0

Tu jest opisany jeden sposób: http://mattmahoney.net/dc/dce.html#Section_527

5.2.7. Deduplication
Deduplication is the application of LZ77 to a file system rather than a data stream. The idea is to find duplicate files or files containing large blocks of data duplicated elsewhere, and replace them with pointers. Deduplication can save disk space, but is more commonly used for incremental backups where only data that has been changed is saved.

Whole file deduplication is easy to implement. If a file system enforces a "last modified" timestamp or an "archive" flag, then files that have not been modified since the last backup need not be saved. Otherwise, or for on-disk deduplication, a secure hash such as SHA-1 of each file can be computed. If two files have the same 160 bit hash, then it is safe to assume that the contents are identical. It is not impossible for different files to have the same hash, but the probability of a collision, 2-160 is far smaller than the 2-60 probability of a disk I/O error. Furthermore, it is believed to be computationally infeasible to deliberately produce a collision.

Compression can be improved by dividing large files into smaller blocks and searching for duplicates among them. This can be done efficiently by computing a hash of each block and saving pointers to the blocks in a hash table. To save space, it might be desirable to use a smaller but insecure hash and check for potential collisions by comparing the blocks.

Dividing large files into fixed sized blocks (typically 8 KB to 64 KB) will not find duplicates between versions in which a small amount of data was inserted or deleted near the beginning because the data afterward would has moved relative to the block boundaries. This problem can be solved by selecting boundaries that depend on a rolling hash function over a sliding window. We set a boundary whenever n bits of the hash are equal to a fixed value. The average block size will be 2n. For example, the following rolling hash function uses a sliding window of 32 bytes and marks a boundary on average every 16 KB when the high 14 bits of the hash are set to 1.

  uint32_t h = 0;  // rolling hash value
  int c;           // input byte
  const int K = 876543210; // a random 32 bit even number not a multiple of 4
  while ((c = getchar()) != EOF) {
    h = (h + c + 1) * K;
    if (h >= 0xfffc0000)
      mark_boundary();
  }
0

A gdzie w kodzie zapisane że okno ma 32 bajty?

0

Wynika to z konstrukcji hasza, który jest tutaj dość trikowy. Przez to, że K jest dwukrotnością nieparzystej liczby, bajt występujący X bajtów temu nie wpływa na X najniższych bitów w haszu. Hasz jest 32-bitowy, więc okno to też 32 bajty, gdyż dopiero 32 bajt wstecz nie wpływa na żaden bit obecnego hasza.

Bardziej elastycznym i prawdopodobnie bardziej odpornym na patologiczne ciągi wejściowe byłby https://en.wikipedia.org/wiki/Rolling_hash#Polynomial_rolling_hash

1 użytkowników online, w tym zalogowanych: 0, gości: 1