Алгоритмы сжатия

Существует множество алгоритмов сжатия данных, вот основные из них:

· алгоритм Зива - Лемпела или 'LZ-методы' (LZ77, LZ78, LZH, LZW)

Сжатие по данному алгоритму основано на создании своеобразного словаря, где каждое слово получает свой порядковый номер, и в результате сжатый файл содержит не предложения, а последовательность чисел, что существенно сокращает его размер. Стоит отметить, что данный метод работает эффективнее для сжатия больших файлов, чем маленьких: создание системы словаря, а иногда и 'словаря в словаре' также сказывается на размере итогового файла, что нецелесообразно для сжатия легких файлов. Кстати, компрессия по алгоритму Зива - Лемпела является одним из самых распространенных алгоритмов сжатия без потерь.

· алгоритм Хаффмана или 'HUFF' ('Huffman Coding')

Кодирование по алгоритму Хаффмана описывается несколько сложнее: оно происходит благодаря созданию определенной таблицы данных и добавления к ней новых ячеек, в результате чего получается систематизация данных в виде дерева ('двоичное дерево'). С помощью этого дерева происходит вычисление кода и собственно само кодирование.

· преобразование Барроуза-Уиллера ('BWT')

При сжатии по алгоритму Барроуза и Уиллера упаковка происходит в два этапа: вначале совершается определенное преобразование данных, затем - сам процесс сжатия. На первом этапе происходит сортировка данных, которая получила название 'преобразование Барроуза-Уиллера': в блоке данных разные символы меняются местами таким образом, чтобы обеспечить более действенное сжатие на втором этапе.

· алгоритм преобразования Фурье 'FT' ('Fourier Transform')

· алгоритм PPM ('Prediction by Partial Match')

На данном алгоритме основаны такие программы русских разработчиков как WinRAR, архиваторы PPMD и PPMonstr (автор Дмитрий Шкарин), PPMN (автор Максим Смирнов), PPMY (архиватор Евгения Шелвина).

· алгоритм арифметического кодирования ARC

Арифметическое кодирование является созданием из сжимаемого файла нумерации отдельных его блоков: в последовательности битов файла выделяются биты с одинаковыми частотами для последующей нумерации. Арифметическое кодирование стало основой многих алгоритмов сжатия, включая алгоритм Хаффмана.