Дедупликация данных

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Дедупликация данных — метод сжатия данных (информации), работающий следующим образом:

  • данные делятся на участки;
  • выполняется поиск одинаковых участков (копий, дублей, повторов);
  • все одинаковые участки, кроме первого, заменяются ссылками на первый участок.

Применение[править | править вики-текст]

Метод обычно используется:

Принцип работы[править | править вики-текст]

В процессе дедупликации:

  • данные (информация) разбиваются на участки (фрагменты, элементы, блоки) (англ. chunks);
  • для каждого участка вычисляется уникальное число — хеш;
  • каждый новых хеш сравнивается с хешами, вычисленными ранее;
  • если новый хеш уникален, новых хеш сохраняется в списке хешей для последующих сравнений; если новый хеш уже имеется в списке хешей, соответствующий участок данных заменяется ссылкой на уже имеющийся участок (или на него перенаправляется уже существующая ссылка), а пространство, занимаемое участком-дубликатом, высвобождается.

Дедупликацию не стоит путать с более традиционными алгоритмами сжатия, например, RLE, LZ77 или LZO. Эти алгоритмы производят поиск одинаковых участков в пределах отдельного файла (так называемое «скользящее окно»), тогда как алгоритм дедупликации производит поиск копий по огромному массиву данных.

Эффективность[править | править вики-текст]

Метод эффективен при наличии большого количества похожих элементов, например, файлов при резервном копировании. Однако, метод не эффективен при внесении небольших изменений в файлы большого размера (например, базы данных или архивы почтовых сообщений), так как будут скопированы не изменённые участки файлов, а файлы целиком.

Ссылки[править | править вики-текст]