Методы архивирования

Существует два основных метода архивации:

Алгоритм Хаффмана. Алгоритм основан на том факте, что некоторые символы в произвольном тексте могут встречаться чаще среднего периода повтора, а другие, соответственно, – реже. Например, буква "а" в русских текстах встречается явно чаще буквы "ъ". Следовательно, если для записи распространенных символов использовать короткие последовательности бит, длиной меньше 1 байта, а для записи редких символов – более длинные, то суммарный объем файла уменьшится. Например буквы а,о,е,и встречаются очень часто в русском тексте, объем памяти для хранения каждой буквы равен 1 байт (8 бит), и их можно заменить на цифры 0,1,2,3, которые можно разместить в 2-х битах. Тогда коэффициент сжатия будет равен 25% (сжатие в 4 раза).

Алгоритм Лемпеля-Зива (LZW). Классический алгоритм Лемпеля-Зива – LZ77, названный так по году своего опубликования. Он формулируется следующим образом: «если в более раннем тексте уже встречалась подобная последовательность байт, то в архивный файл записывается только ссылка на эту последовательность (смещение, длина), а не сам текст». Так фраза «КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ»[24] закодируется в последовательность «КОЛО(-4,3)_О(-6,4)_(-7,7)ЬНИ»[13]. Коэффициент сжатия - 54%. Аналогично сжимается изображение. Большие области одного цвета заменяются на ссылку: (цвет, число пикселей). Графические файлы сжимаются очень хорошо– в 100..00 раз.

Не нашли, что искали? Воспользуйтесь поиском: