Автор: Victor_VG
Дата сообщения: 27.06.2009 13:36
HelioSS
Можно и нужно пояснить, вещь действительно сложная и абстрактная, более того, это математические абстракции более гораздо более высокого порядка, чем привычное нам трёхмерное пространство - это многомерное пространство, а его нам представить очень трудно.
[more=Пояснение]Допустим у нас есть некоторый набор данных и алгоритм сжатия способный использовать несколько режимов работы.
Сами алгоритмы сжатия рассматривают любой файл как двоичную последовательность фиксированной длинны равной длине файла. Т.е. они подразумевают обработку файла бит за битом, а раз так, то по определению мы имеем дело с потоком описываемым одномерной величиной у которой есть одно измерение - порядковый номер элемента от точки отсчёта. А по определению это бинарный поток, т.е изменяющаяся во времени последовательность бит. Второй координатой его выступает момент времени наблюдения, но она как бы свёрнута, замкнута сама на себя, поскольку мы говорим только о текущем моменте времени, в который некий условный индекс потока равен порядковому номеру наблюдаемого в данный момент бита.
Алгоритм сжатия действует по простому принципу: берём некоторую выборку из входного потока и смотрим её повторяемость. Если выборка встречается более одного раза, то мы заносим её в специальный набор данных размер элемента в котором равен размеру выборки - словарь, а в потоке заменяем номером записи в словаре. Далее цикл повторяем до исчерпания входного потока. В итоге длинные повторяющиеся участки в потоке заменятся короткими индексными ссылками на словарь и признаком что это блок в словаре, а не элемент исходных данных, а суммарный размер сжатого набора будет равен размеру выходного потока плюс размер словаря плюс заголовок содержащий указатели на начало блока данных, словаря и размеры блоков. Это в идеале. В реальности обычно индекс содержит номер блока в словаре замен, а для указания факта замены блоков используется таблица содержащая специальный маркер-признак определяющий для алгоритма как при восстановлении понимать тот или иной блок данных как непосредственные данные, или как ссылку на блок словаря.
Разные алгоритмы используют разные способы поиска повторов и разные величины выборки, и разную структуру блока данных и словаря, а это прямо влияет на размер выходного архива. Например если использовать непрерывное сжатие, то алгоритм лучше сжимает набор файлов именно потому, что считает их непрерывным потоком состоящим из отдельных фрагментов. Да, информация об их длинах сохраняется, но на этапе подготовки сжатия. Тогда алгоритм формирует псевдо-непрерывный поток, содержащий специальную таблицу длин отдельных элементов, но сжимает его как единое целое, и создаёт служебные структуры для него как для целого. А если непрерывное сжатие не использовать, то каждый файл сжимается отдельно и объём служебной информации увеличивается на некоторую величину, зато упрощается процесс распаковки и изменения архива.
В случае непрерывного архива извлечь отдельный элемент мы можем перейдя к его начальной точке в непрерывном потоке, но любая модификация архива потребует его распаковки во временную папку, и нового цикла сжатия как единого целого. А если архив состоит из отдельных элементов, то мы по таблице находим ссылку на нужной, читаем/меняем его и обновляем таблицы не трогая другие элементы архива. Таким образом мы экономим время, но теряем на степени сжатия.
Разные алгоритмы оптимизированы для разных по своим свойствам наборов данных, и подбор алгоритма может дать нам некоторый выигрыш либо по степени сжатия, либо во времени. Но, чем больше размер блока в словаре, тем теоретически можно получить большее сжатие. Но, это теория, а реально существует прямая зависимость между размером словаря и входным потоком - оптимальный текущий размер блока словаря всегда равен текущему размеру повторяющихся элементов потока. А фиксированный размер словаря что-то может и пропустить, и размер файла увеличится.
Для упрощения реализации алгоритмов обычно используется фиксированный размер блока словаря. А для достижения максимальной степени сжатия, пусть и за счёт увеличения времени обработки и расхода памяти, т.к. сравниваемый блок-шаблон на время сравнения нужно держать в каком-то рабочем буфере, можно использовать и адаптивную (переменную во времени) величину блока словаря.
Кроме того, в зависимости от алгоритма и заданных для него начальных условий предельная степень сжатия на одних и тех же данных будет разной, причины мы видим выше.[/more]
А с mc вообще пришлось долго возится со справкой - не знаю кто напихал такую смесь кодировок в неё - что ни абзац, то собственная.