Методы сжатия данных

Методы сжатия данных 18 Но в подавляющем большинстве случаев истинная структура источника нам неизвестна, поэтому необходимо строить модель источника, которая позволила бы нам в каждой позиции входной последовательности оценить вероятность p(si) появления каждого элемента si алфавита входной последо-вательности. В этом случае мы оперируем оценкой q(si) вероятности эле-мента si. Методы сжатия могут строить модель источника адаптивно по мере об-работки потока данных или использовать фиксированную модель, создан-ную на основе априорных представлений о природе типовых данных, тре-бующих сжатия. Процесс моделирования может быть либо явным, либо скрытым. Веро-ятности элементов могут использоваться в методе как явным, так и неявным образом. Но всегда сжатие достигается за счет устранения статистической избыточности в представлении информации. Ни один компрессор не может сжать любой файл. После обработки лю-бым компрессором размер части файлов уменьшится, а оставшейся части – увеличится или останется неизменным. Данный факт можно доказать исхо-дя из неравномерности кодирования, т. е. разной длины используемых ко-дов, но наиболее прост для понимания следующий комбинаторный аргу-мент. Существует 2n различных файлов длины n бит, где n = 0, 1, 2, … Если размер каждого такого файла в результате обработки уменьшается хотя бы на 1 бит, то 2n исходным файлам будет соответствовать самое большее 2n-1 различающихся сжатых файлов. Тогда по крайней мере одному архивному файлу будет соответствовать несколько различающихся исходных, и, сле-довательно, его декодирование без потерь информации невозможно в принципе. Ô Вышесказанное предполагает, что файл отображается в один файл и объ-ем данных указывается в самих данных. Если это не так, то следует учиты-вать не только суммарный размер архивных файлов, но и объем информации, необходимой для описания нескольких взаимосвязанных архивных файлов и/или размера исходного файла. Общность доказательства при этом сохраняется. Поэтому невозможен...