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

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

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

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

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

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

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

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

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

Ввиду технических особенностей реализаций хранения ссылок при достаточно большом количестве ссылок на одну и ту же копию данных могут появиться несколько хранимых копий этих данных для сохранения малого размера счётчика ссылок, так как это более эффективно.

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

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

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

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