Что называется оператором. Линейные операторы. Умножение линейных операторов

Лекция №4. Сжатие информации

Принципы сжатия информации

Цель сжатия данных - обеспечить компактное представление данных, вырабатываемых источником, для их более экономного сохранения и передачи по каналам связи.

Пусть у нас имеется файл размером 1 (один) мегабайт. Нам необходимо получить из него файл меньшего размера. Ничего сложного - запускаем архиватор, к примеру, WinZip, и получаем в результате, допустим, файл размером 600 килобайт. Куда же делись остальные 424 килобайта?

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

Виды сжатия

Все методы сжатия информации можно условно разделить на два больших непересекающихся класса: сжатие с потерей инфор­мации и сжатие без потери информации.

Сжатие без потери информации.

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

Методы сжатия этого класса не могут допустить утрату информа­ции, поэтому они основаны только на устранении ее избыточности, а информация имеет избыточность почти всегда (правда, если до этого кто-то ее уже не уплотнил). Если бы избыточности не было, нечего было бы и сжимать.

Вот простой пример. В русском языке 33 буквы, десять цифр и еще примерно полтора десятка знаков препинания и прочих спе­циальных символов. Для текста, который записан только про­писными русскими буквами (как в телеграммах и радиограммах) вполне хватило бы шестидесяти разных значений. Тем не менее, каждый символ обычно кодируется байтом, который содержит 8 битов и может выражать 256 различных кодов. Это первое осно­вание для избыточности. Для нашего «телеграфного» текста вполне хватило бы шести битов на символ.

Вот другой пример. В международной кодировке символов ASCII для кодирования любого символа отводится одинаковое количество битов (8), в то время как всем давно и хорошо извест­но, что наиболее часто встречающиеся символы имеет смысл кодировать меньшим количеством знаков. Так, например, в «азбуке Морзе» буквы «Е» и «Т», которые встречаются часто, кодируются одним знаком (соответственно это точка и тире). А такие редкие буквы, как «Ю» ( - -) и «Ц» (- - ), кодиру­ются четырьмя знаками. Неэффективная кодировка - второе основание для избыточности. Программы, выполняющие сжа­тие информации, могут вводить свою кодировку (разную для разных файлов) и приписывать к сжатому файлу некую таблицу (словарь), из которой распаковывающая программа узнает, как в данном файле закодированы те или иные символы или их груп­пы. Алгоритмы, основанные на перекодировании информации, называют алгоритмами Хафмана.

Наличие повторяющихся фрагментов - третье основание для избыточности. В текстах это встречается редко, но в таблицах и в графике повторение кодов - обычное явление. Так, например, если число 0 повторяется двадцать раз подряд, то нет смысла ставить двадцать нулевых байтов. Вместо них ставят один ноль и коэффициент 20. Такие алгоритмы, основанные на выявлении повторов, называют методами RLE (Run Length Encoding ).

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

Сжатие с потерей информации.

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

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

В то же время, существуют материалы, в которых стоит пожерт­вовать несколькими процентами информации, чтобы получить сжатие в десятки раз. К ним относятся фотографические иллюстрации, видеоматериалы и музыкальные композиции. Потеря информации при сжатии и последующей распаковке в таких материалах воспринимается как появление некоторого дополнительного «шума». Но поскольку при создании этих мате­риалов определенный «шум» все равно присутствует, его неболь­шое увеличение не всегда выглядит критичным, а выигрыш в раз­мерах файлов дает огромный (в 10-15 раз на музыке, в 20-30 раз на фото- и видеоматериалах).

К алгоритмам сжатия с потерей информации относятся такие известные алгоритмы как JPEG и MPEG. Алгоритм JPEG исполь­зуется при сжатии фотоизображений. Графические файлы, сжа­тые этим методом, имеют расширение JPG. Алгоритмы MPEG используют при сжатии видео и музыки. Эти файлы могут иметь различные расширения, в зависимости от конкретной программы, но наиболее известными являются.MPG для видео и.МРЗ для музыки.

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

Величиной допустимой потери при сжатии обычно можно управ­лять. Это позволяет экспериментовать и добиваться оптималь­ного соотношения размер/качество. На фотографических иллюст­рациях, предназначенных для воспроизведения на экране, потеря 5% информации обычно некритична, а в некоторых случаях можно допустить и 20-25%.

Алгоритмы сжатия без потери информации

Код Шеннона-Фэно

Для дальнейших рассуждений будет удобно представить наш исходный файл с текстом как источник символов, которые по одному появляются на его выходе. Мы не знаем заранее, какой символ будет следующим, но мы знаем, что с вероятностью p1 появится буква "а", с вероятностью p2 -буква "б" и т.д.

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

Давайте представим себе текст, алфавит которого состоит всего из 16 букв: А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н, О, П, Р. Каждый из этих знаков можно закодировать с помощью всего 4 бит: от 0000 до 1111. Теперь представим себе, что вероятности появления этих символов распределены следующим образом:

Сумма этих вероятностей составляет, естественно, единицу. Разобьем эти символы на две группы таким образом, чтобы суммарная вероятность символов каждой группы составляла ~0.5 (рис). В нашем примере это будут группы символов А-В и Г-Р. Кружочки на рисунке, обозначающие группы символов, называются вершинами или узлами (nodes), а сама конструкция из этих узлов - двоичным деревом (B-tree). Присвоим каждому узлу свой код, обозначив один узел цифрой 0, а другой - цифрой 1.

Снова разобьем первую группу (А-В) на две подгруппы таким образом, чтобы их суммарные вероятности были как можно ближе друг к другу. Добавим к коду первой подгруппы цифру 0, а к коду второй - цифру 1.

Будем повторять эту операцию до тех пор, пока на каждой вершине нашего "дерева" не останется по одному символу. Полное дерево для нашего алфавита будет иметь 31 узел.

Коды символов (крайние правые узлы дерева) имеют коды неодинаковой длины. Так, буква А, имеющая для нашего воображаемого текста вероятность p=0.2, кодируется всего двумя битами, а буква Р (на рисунке не показана), имеющая вероятность p=0.013, кодируется аж шестибитовой комбинацией.

Итак, принцип очевиден - часто встречающиеся символы кодируются меньшим числом бит, редко встречающиеся - большим. В результате среднестатистическое количество бит на символ будет равно

где ni - количество бит, кодирующих i-й символ, pi - вероятность появления i-го символа.

Код Хаффмана.

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

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте.

2. Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагаем равной сумме вероятностей составляющих его символов. В конце концов построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него.

3. Прослеживаем путь к каждому листу дерева, помечая направление к каждому узлу (например, направо - 1, налево - 0) . Полученная последовательность дает кодовое слово, соответствующее каждому символу (рис.).

Построим кодовое дерево для сообщения со следующим алфавитом:

Недостатки методов

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

Решением этой проблемы является статистический анализ кодируемых данных, выполняемый в ходе первого прохода по данным, и составление на его основе кодового дерева. Собственно кодирование при этом выполняется вторым проходом.

Еще один недостаток кодов - это то, что минимальная длина кодового слова для них не может быть меньше единицы, тогда как энтропия сообщения вполне может составлять и 0,1, и 0,01 бит/букву. В этом случае код становится существенно избыточным. Проблема решается применением алгоритма к блокам символов, но тогда усложняется процедура кодирования/декодирования и значительно расширяется кодовое дерево, которое нужно в конечном итоге сохранять вместе с кодом.

Данные коды никак не учитывают взаимосвязей между символами, которые присутствуют практически в любом тексте. Например, если в тексте на английском языке нам встречается буква q, то мы с уверенностью сможем сказать, что после нее будет идти буква u.

Групповое кодирование - Run Length Encoding (RLE) - один из самых старых и самых простых алгоритмов архивации. Сжатие в RLE происходит за счет замены цепочек одинаковых байт на пары "счетчик, значение". («красный, красный, ..., красный» записывается как «N красных»).

Одна из реализаций алгоритма такова: ищут наименнее часто встречающийся байт, называют его префиксом и делают замены цепочек одинаковых символов на тройки "префикс, счетчик, значение". Если же этот байт встретичается в исходном файле один или два раза подряд, то его заменяют на пару "префикс, 1" или "префикс, 2". Остается одна неиспользованная пара "префикс, 0", которую можно использовать как признак конца упакованных данных.

При кодировании exe-файлов можно искать и упаковывать последовательности вида AxAyAzAwAt..., которые часто встречаются в ресурсах (строки в кодировке Unicode)

К положительным сторонам алгоритма, можно отнести то, что он не требует дополнительной памяти при работе, и быстро выполняется. Алгоритм применяется в форматах РСХ, TIFF, ВМР. Интересная особенность группового кодирования в PCX заключается в том, что степень архивации для некоторых изображений может быть существенно повышена всего лишь за счет изменения порядка цветов в палитре изображения.

LZW-код (Lempel-Ziv & Welch) является на сегодняшний день одним из самых распространенных кодов сжатия без потерь. Именно с помощью LZW-кода осуществляется сжатие в таких графических форматах, как TIFF и GIF, с помощью модификаций LZW осуществляют свои функции очень многие универсальные архиваторы. Работа алгоритма основана на поиске во входном файле повторяющихся последовательностей символов, которые кодируются комбинациями длиной от 8 до 12 бит. Таким образом, наибольшую эффективность данный алгоритм имеет на текстовых файлах и на графических файлах, в которых имеются большие одноцветные участки или повторяющиеся последовательности пикселов.

Отсутствие потерь информации при LZW-кодировании обусловило широкое распространение основанного на нем формата TIFF. Этот формат не накладывает каких-либо ограничений на размер и глубину цвета изображения и широко распространен, например, в полиграфии. Другой основанный на LZW формат - GIF - более примитивен - он позволяет хранить изображения с глубиной цвета не более 8 бит/пиксел. В начале GIF - файла находится палитра - таблица, устанавливающая соответствие между индексом цвета - числом в диапазоне от 0 до 255 и истинным, 24-битным значением цвета.

Алгоритмы сжатия с потерей информации

Алгоритм JPEG был разработан группой фирм под названием Joint Photographic Experts Group. Целью проекта являлось создание высокоэффективного стандарта сжатия как черно-белых, так и цветных изображений, эта цель и была достигнута разработчиками. В настоящее время JPEG находит широчайшее применение там, где требуется высокая степень сжатия - например, в Internet.

В отличие от LZW-алгоритма JPEG-кодирование является кодированием с потерями. Сам алгоритм кодирования базируется на очень сложной математике, но в общих чертах его можно описать так: изображение разбивается на квадраты 8*8 пикселов, а затем каждый квадрат преобразуется в последовательную цепочку из 64 пикселов. Далее каждая такая цепочка подвергается так называемому DCT-преобразованию, являющемуся одной из разновидностей дискретного преобразования Фурье. Оно заключается в том, что входную последовательность пикселов можно представить в виде суммы синусоидальных и косинусоидальных составляющих с кратными частотами (так называемых гармоник). В этом случае нам необходимо знать лишь амплитуды этих составляющих для того, чтобы восстановить входную последовательность с достаточной степенью точности. Чем большее количество гармонических составляющих нам известно, тем меньше будет расхождение между оригиналом и сжатым изображением. Большинство JPEG-кодеров позволяют регулировать степень сжатия. Достигается это очень простым путем: чем выше степень сжатия установлена, тем меньшим количеством гармоник будет представлен каждый 64-пиксельный блок.

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

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

Однако формат JPEG не является пределом совершенства в стремлении уменьшить размер конечного файла. В последнее время ведутся интенсивные исследования в области так называемого вейвлет-преобразования (или всплеск-преобразования). Основанные на сложнейших математических принципах вейвлет-кодеры позволяют получить большее сжатие, чем JPEG, при меньших потерях информации. Несмотря на сложность математики вейвлет-преобразования, в программной реализации оно проще, чем JPEG. Хотя алгоритмы вейвлет-сжатия пока находятся в начальной стадии развития, им уготовано большое будущее.

Фрактальное сжатие

Фрактальное сжатие изображений - это алгоритм сжатия изображений c потерями, основанный на применении систем итерируемых функций (IFS, как правило являющимися аффинными преобразованиями) к изображениям. Данный алгоритм известен тем, что в некоторых случаях позволяет получить очень высокие коэффициенты сжатия (лучшие примеры - до 1000 раз при приемлемом визуальном качестве) для реальных фотографий природных объектов, что недоступно для других алгоритмов сжатия изображений в принципе. Из-за сложной ситуации с патентованием широкого распространения алгоритм не получил.

Фрактальная архивация основана на том, что с помощью коэффициентов системы итерируемых функций изображение представляется в более компактной форме. Прежде чем рассматривать процесс архивации, разберем, как IFS строит изображение.

Строго говоря, IFS - это набор трехмерных аффинных преобразований, переводящих одно изображение в другое. Преобразованию подвергаются точки в трехмерном пространстве (x координата, у координата, яркость).

Основа метода фрактального кодирования - это обнаружение самоподобных участков в изображении. Впервые возможность применения теории систем итерируемых функций (IFS) к проблеме сжатия изображения была исследована Майклом Барнсли и Аланом Слоуном. Они запатентовали свою идею в 1990 и 1991 гг. Джеквин (Jacquin) представил метод фрактального кодирования, в котором используются системы доменных и ранговых блоков изображения (domain and range subimage blocks), блоков квадратной формы, покрывающих все изображение. Этот подход стал основой для большинства методов фрактального кодирования, применяемых сегодня. Он был усовершенствован Ювалом Фишером (Yuval Fisher) и рядом других исследователей.

В соответствии с данным методом изображение разбивается на множество неперекрывающихся ранговых подизображений (range subimages) и определяется множество перекрывающихся доменных подизображений (domain subimages). Для каждого рангового блока алгоритм кодирования находит наиболее подходящий доменный блок и аффинное преобразование, которое переводит этот доменный блок в данный ранговый блок. Структура изображения отображается в систему ранговых блоков, доменных блоков и преобразований.

Идея заключается в следующем: предположим, что исходное изображение является неподвижной точкой некоего сжимающего отображения. Тогда можно вместо самого изображения запомнить каким-либо образом это отображение, а для восстановления достаточно многократно применить это отображение к любому стартовому изображению.

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

Вкратце метод, предложенный Барнсли, можно описать следующим образом. Изображение кодируется несколькими простыми преобразованиями (в нашем случае аффинными), то есть определяется коэффициентами этих преобразований (в нашем случае A, B, C, D, E, F).

Например, изображение кривой Коха можно закодировать четырмя аффинными преобразованиями, мы однозначно определим его с помощью всего 24-х коэффициентов.

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

Наиболее известны два изображения, полученных с помощью IFS: треугольник Серпинского и папоротник Барнсли. Первое задается тремя, а второе - пятью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считанными байтами, в то время как изображение, построенное с их помощью, может занимать и несколько мегабайт.

Становится понятно, как работает архиватор, и почему ему требуется так много времени. Фактически, фрактальная компрессия - это поиск самоподобных областей в изображении и определение для них параметров аффинных преобразований.

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

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

Сравнение с JPEG

Сегодня наиболее распространенным алгоритмом архивации графики является JPEG. Сравним его с фрактальной компрессией.

Во-первых, заметим, что и тот, и другой алгоритм оперируют 8-битными (в градациях серого) и 24-битными полноцветными изображениями. Оба являются алгоритмами сжатия с потерями и обеспечивают близкие коэффициенты архивации. И у фрактального алгоритма, и у JPEG существует возможность увеличить степень сжатия за счет увеличения потерь. Кроме того, оба алгоритма очень хорошо распараллеливаются.

Различия начинаются, если мы рассмотрим время, необходимое алгоритмам для архивации/разархивации. Так, фрактальный алгоритм сжимает в сотни и даже в тысячи раз дольше, чем JPEG. Распаковка изображения, наоборот, произойдет в 5-10 раз быстрее. Поэтому, если изображение будет сжато только один раз, а передано по сети и распаковано множество раз, то выгодней использовать фрактальный алгоритм.

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

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

Вытеснение JPEG фрактальным алгоритмом в повсеместном использовании произойдет еще не скоро (хотя бы в силу низкой скорости архивации последнего), однако в области приложений мультимедиа, в компьютерных играх его использование вполне оправдано.

Архив - Сжатие файлов: Как это происходит? - Журнал «Компьютер»

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

Виталий

Совершенно верно, Виталий, это действительно не так просто себе представить, тем более, если не знаешь алгоритма. Но читателям журнала «Компьютер» повезло;), поскольку я в свое время много интересовался алгоритмами сжатия данных и, как программист, даже пробовал писать собственный архиватор.

Сжатие данных (англ. data compression) - алгоритмическое преобразование данных, производимое с целью уменьшения их объема. Применяется для более рационального использования устройств хранения и передачи данных. Процесс сжатия еще называют упаковкой данных или компрессией. Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).

Сжатие основано на устранении избыточности, содержащейся в исходных данных. Простейшим примером избыточности является повторение в тексте фрагментов (например, слов естественного или машинного языка).

Итак, давайте начнем с простого примера. Допустим, у нас есть текстовый файл, который содержит строку текста:

АААГГДЕЕЕЕЖЖУУУККККИИИ

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

А3Г2Д1Е4Ж2У3К4И3

Таким образом, вместо 22 символов мы получили 16 символов. Конечно, такие тексты как наш исходный встречаются довольно редко, не говоря уже о бессмыслице, которая заключена в нем. Но ведь файлы, подвергающиеся сжатию, бывают не только текстовые, но и всякие картинки, музыка, видео, программы.

Данный пример довольно упрощен и не отражает эффективность, которую обычно демонстрируют при сжатии архиваторы. Так у нас получилось сжатие в 22/16 = 1,375 раза, хотя архиваторы, как правило, способны сжимать файлы в 2-10000 раз. Все зависит от повторяемости значений байт в файле.

Какие архиваторы бывают

Например, во времена незабвенной MS-DOS были архиваторы ARJ, PKZIP, HA, RAR, ARC, ACE и упаковщики программ LZEXE и PKLITE. Позднее для операционной системы Windows были созданы WinAce, WinZIP, WinRAR, 7Zip и известный мне упаковщик UPX.

Сжатие бывает с потерями и без. Сжатие без потерь позволяет восстановить исходные данные с точностью до бита. Такое сжатие применяется для упаковки текста, программ, различных данных в купе и осуществляется всеми перечисленными выше архиваторами.

Сжатие с потерями можно назвать адаптивным сжатием, и применяется для упаковки изображений, видео и звука, поскольку такие данные сжатию без потерь поддаются весьма незначительно (всего примерно до 2 раз).

Благодаря сжатию с потерями можно добиться многократного уменьшения объема данных, и при отображении распакованных данных человек практически не ощутит разницы между оригиналом.

На сколько сжимаются разные файлы

Текстовые

Действительно, например, текстовые файлы могут сжиматься весьма плотно. Так, например, книга Аркадия и Бориса Стругацких «Трудно быть богом» размером 354 329 байт архиватором WinRAR сжимается до 140 146 байт, т.е. в 2,5 раза.

Программы

Файлы программ тоже могут подвергаться сжатию. При этом сжатию как для более плотного хранения на диске, так и сжатию, при котором программа остается программой, но при запуске разжимает сама себя.

Для этого существуют упаковщики программ на подобие UPX и др. Например, мой текстовый редактор Superpad.exe размером 524 288 байт упаковщиком UPX сжимается до 179 200 байт (в 2,9 раза) и при этом может по-прежнему запускаться самостоятельно как программа.

Изображения

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

Одним из первых алгоритмов сжатия изображений был алгоритм RLE, который я описал выше. Он применяется в формате хранения изображений PCX. RLE является алгоритмом сжатия без потерь. Но в некоторых случаях он мог приводить не к уменьшению объема данных, а к его увеличению.

Поэтому для сжатия изображений был предложен и используется до сих пор алгоритм побитового сжатия LZW. Сам по себе алгоритм уже гораздо эффективнее RLE и тоже не предусматривает потери. Но поскольку применяется для изображений с палитрой цветов, то за счет адаптации и оптимизации (уплотнения) палитры можно добиться существенного повышения эффективности сжатия.

Рис. 1. Красивый лягушонок в формате BMP

Для сравнения, возьмем красивого лягушонка (рис. 1) разрешение 799x599 пикселей (точек) и сохраним в разные форматы хранения изображений. Получим файлы:

frog.bmp - размер 1 437 654 байта и тут, по сути, никакого сжатия и никаких потерь качества, поскольку картинка занимает положенные ей байты в формате Ширина x Высота x 3 байта на пиксель + заголовок формата файла BMP согласно качеству True colors (24 бит/пиксель). Т.е. каждая точка представлена тремя компонентами RGB (Red-красный, Green-зеленый и Blue-синий), каждая из которых занимает один байт.

frog24.png - 617 059 байт, сжатие в 2,33 раза и без потерь - основное свойство формата PNG-24. Данные BMP и PNG практически идентичны.

Рис. 2. Файл frog_256colors.gif

frog_256colors.gif - 261 956 байт (рис. 2), сжатие в 5,48 раза с потерями, базовая палитра 256 цветов (8 бит/пиксель). Уловить разницу между этим файлом и оригиналом в BMP довольно сложно, как в той игре «Найди десять отличий».

Рис. 3. Файл frog_64colors.gif

frog_64colors.gif - 187 473 байта (рис. 3), сжатие в 7,67 раза с потерями, базовая палитра уплотнена до 64 цветов (6 бит/пиксель). А вот тут цвета уже блеклые, но вполне сходное с оригиналом изображение. Особенно это заметно, если посмотреть на глаз лягушонка.

JPEG

Особое место занимает в сжатии и хранении изображений формат JPEG. Поэтому ему хочу уделить особое внимание. Алгоритм JPEG в наибольшей степени пригоден для сжатия фотографий и картин, содержащих реалистичные сцены с плавными переходами яркости и цвета. Наибольшее распространение JPEG получил в цифровой фотографии и для хранения и передачи изображений с использованием сети Интернет.

С другой стороны, JPEG малопригоден для сжатия чертежей, текстовой и знаковой графики, где резкий контраст между соседними пикселями приводит к появлению заметных артефактов. Такие изображения целесообразно сохранять в форматах без потерь, таких как TIFF, GIF, PNG или RAW.

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

JPEG не должен использоваться и в тех случаях, когда недопустимы даже минимальные потери, например, при сжатии астрономических или медицинских изображений. В таких случаях может быть рекомендован предусмотренный стандартом JPEG режим сжатия Lossless JPEG (который, к сожалению, не поддерживается большинством популярных кодеков) или стандарт сжатия JPEG-LS.

Описание алгоритма сжатия JPEG довольно не простое, поэтому кто захочет, может ознакомиться с ним по ссылке http://el-izdanie.narod.ru/gl4/4-3.htm. Ну и для сравнения сожмем нашу исходную картинку с разным уровнем качества:

frog100%.jpg - 216 168 байт, сжатие в 6,65 раза, потери якобы 0%, т.е. 100%-е качество картинки, но даже на это рассчитывать я бы не стал. Поверьте, отличия есть, правда, на глаз абсолютно неотличимые.

frog60%.jpg - 85 910 байт, сжатие в 16,7 раза, т.е. качество картинки 60%, но картинка снова кажется одинаковой, хотя, если присмотреться к участкам с однородным фоном или мелким деталям, то заметны артефакты в виде смазанности или квадратных одноцветных сегментов.

frog20%.jpg - 36 426 байт, сжатие в 39,5 раз, качество картинки 20% от исходного изображения, но по-прежнему картинка еще способна обмануть неискушенный глаз, но на однородном фоне отчетливо видны одноцветные угловатые сегменты, а мелкие детали окончательно потеряли свои четкие очертания.

MPEG

Это один из самых первых и самых распространенных форматов хранения видео. Несколько раз модернизировался. Но в упрощенном виде, можно сказать, что алгоритм очень напоминает сжатие как в JPEG, но с учетом того, что первый кадр видео всегда является исходным и оригинальным, а последующие кадры хранят лишь разницу между предыдущим и следующим кадрами. Благодаря этому каждый последующий кадр является предсказуемым с точки зрения распаковки (рис. 4 и 5).

Рис. 4. Исходные кадры видео

Рис. 5. Межкадровая разница без применения алгоритмов компенсации движения

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

Однако, из-за движения каких-либо объектов в кадре (или самой камеры) использование подобия соседних кадров было неполным. Технология компенсации движения позволяет находить похожие участки, даже если они сдвинуты относительно предыдущего кадра.

Компенсация движения (англ. Motion Compensation) - один из основных алгоритмов, применяемых при обработке и сжатии видеоданных. Алгоритм использует сходство соседних кадров в видео последовательности и находит векторы движения отдельных частей изображения (обычно блоков 16x16 и 8x8).

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

Практически в любом видео соседние кадры похожи, имеют общие объекты, которые, как правило, смещаются друг относительно друга. И совершенно естественно желание закодировать видео так, чтобы объекты не кодировались многократно, а просто описывались некоторые их смещения.

При этом, изображение разбивается на так называемые ключевые кадры - это группы кадров, идущих подряд несколько секунд. Управляя длительностью таких ключевых кадров можно эффективно управлять сжатием.

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

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

Звук и музыка

Звук и музыка могут без потерь, либо с потерями храниться в формате WAV. Например, формат WAV (Windows PCM) не предусматривает сжатие и хранит звуковой сигнал в оригинале, если можно так выразиться.

Формат WAV (ACM Waveform), по сути, является контейнером и может хранить звук, сжатый по алгоритму MPEG layer 3, либо хранить музыку в формате MP3, хотя много и других форматов OGG, FLAC и д.р.

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

Слайд 2

• Для длительного хранения данных на различных носителях информации
• Для передачи данных по каналам связи

Слайд 3

Избыточность данных

• Большинство данных являются избыточными
• Избыточность улучшает восприятие и обработку информации
• При хранении избыточность уменьшают
• Наибольшая избыточность у видеоинформации, затем идет графическая, звуковая, и самая низкая избыточность у текстовой информации

Слайд 4

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

• С частичной потерей информации:Производится при сжатии кода изображения, видео и звукаТакая возможность связана с субъективными возможностями человеческого зрения и слуха.
• Без потери информации:- использование неравномерного символьного кода;- выявления повторяющихся фрагментов кода.

Слайд 5

С частичной потерей

• На зрение более существенное воздействие оказывает яркость пикселя, нежели его цвет. Поэтому объем видеокода можно сократить за счет того, что коды цвета хранить не для каждого пикселя, а через один, два и т.д. пикселей растра. Чем больше такие пропуски, тем больше сжимаются видеоданные, но при этом ухудшается качество изображения.
• При кодировании видеофильмов - динамичного изображения, учитывается свойство инерционности зрения. Быстро меняющиеся фрагменты фильма можно кодировать менее подробно, чем статические кадры.
• Труднее всего сжатию поддается звуковой код. Здесь также используются психофизиологические особенности человеческого слуха. Учитывается, к каким гармоникам естественного звука наш слух более восприимчив, а к каким - менее. Слабо воспринимаемые гармоники отфильтровываются путем математической обработки. Сжатию способствует также учет нелинейной зависимости между амплитудой звуковых колебаний и восприятием нашим ухом громкости звучания.

Слайд 6

• Применяется для таких типов данных, для которых формальная утрата части содержания не приводит к потере потребительских свойств и обеспечивает высокую степень сжатия.
• Примеры:видео MPG, звук MP3, рисунки JPG.

Слайд 7

Без потери – «обратимый»

• Применяется к текстам, базам данных, и ко всем остальным вышеназванным типам.
• Пример: рисунки – GIF, TIF,PCX, видео - AVI, любой тип данных – ZIP, ARJ, RAR и др.

Слайд 8

Архивы

• Архив – файл, содержащий в себе один или несколько файлов в сжатом виде.
• Расширение архивного файла зависит от программы-архиватора.
• Архиватор – программы для создания и чтения архивов.Пример:WinRar, WinZip, WinArj.

Слайд 9

Архивы применяют с целью

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

Слайд 10

Возможности архиваторов

Просмотр содержимого архива

Контроль целостности данных

Распаковка архива

Восстановление поврежденного архива

Установка защиты

Добавление файла в архив

Создание многотомных архивов

Создание самораспаковывающихся архивов

Блокировка от случайной модификации

Слайд 11

Самораспаковывающийся

(SFX, от англ. SelF-eXtracting) - это архив, к которому присоединен исполнимый модуль. Этот модуль позволяет извлекать файлы простым запуском архива как обычной программы. Таким образом, для извлечения содержимого SFX-архива не требуется дополнительных внешних программ. SFX-архивы удобны в тех случаях, когда вам нужно передать кому-то архив, но при этом вы не уверены, что у адресата есть соответствующий архиватор для его распаковки.

План:

Введение

• 1 Принципы сжатия данных
• 2 Характеристики алгоритмов сжатия и их применимость
  • 2.1 Коэффициент сжатия
  • 2.2 Допустимость потерь
  • 2.3 Системные требования алгоритмов
• 3 Алгоритмы сжатия данных неизвестного формата
Литература

Введение

Сжатие данных (англ. data compression ) - алгоритмическое преобразование данных, производимое с целью уменьшения их объёма. Применяется для более рационального использования устройств хранения и передачи данных. Синонимы - упаковка данных, компрессия, сжимающее кодирование, кодирование источника. Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).

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

1. Принципы сжатия данных

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

Все методы сжатия данных делятся на два основных класса:

• Сжатие без потерь
• Сжатие с потерями

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

2. Характеристики алгоритмов сжатия и их применимость

2.1. Коэффициент сжатия

Коэффициент сжатия - основная характеристика алгоритма сжатия. Она определяется как отношение объёма исходных несжатых данных к объёму сжатых, то есть:

k = S o /S c ,

где k - коэффициент сжатия, S o - объём исходных данных, а S c - объём сжатых. Таким образом, чем выше коэффициент сжатия, тем алгоритм эффективнее. Следует отметить:

• если k = 1, то алгоритм не производит сжатия, то есть выходное сообщение оказывается по объёму равным входному;
• если k < 1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

Ситуация с k < 1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n бит составляет ровно 2 n , число различных сообщений с длиной меньшей или равной n (при наличии хотя бы одного сообщения меньшей длины) будет меньше 2 n . Это значит, что невозможно однозначно сопоставить все исходные сообщения сжатым: либо некоторые исходные сообщения не будут иметь сжатого представления, либо нескольким исходным сообщениям будет соответствовать одно и то же сжатое, а значит их нельзя отличить.

Коэффициент сжатия может быть как постоянным (некоторые алгоритмы сжатия звука, изображения и т. п., например А-закон, μ-закон, ADPCM, усечённое блочное кодирование), так и переменным. Во втором случае он может быть определён либо для каждого конкретного сообщения, либо оценён по некоторым критериям:

• средний (обычно по некоторому тестовому набору данных);
• максимальный (случай наилучшего сжатия);
• минимальный (случай наихудшего сжатия);

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

2.2. Допустимость потерь

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

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

2.3. Системные требования алгоритмов

Различные алгоритмы могут требовать различного количества ресурсов вычислительной системы, на которых они реализованы:

• оперативной памяти (под промежуточные данные);
• постоянной памяти (под код программы и константы);
• процессорного времени.

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

Так как алгоритмы сжатия и восстановления работают в паре, имеет значение соотношение системных требований к ним. Нередко можно усложнив один алгоритм значительно упростить другой. Таким образом, возможны три варианта:

Алгоритм сжатия требует больших вычислительных ресурсов, нежели алгоритм восстановления. Это наиболее распространённое соотношение, характерное для случаев, когда однократно сжатые данные будут использоваться многократно. В качестве примера можно привести цифровые аудио- и видеопроигрыватели. Алгоритмы сжатия и восстановления требуют приблизительно равных вычислительных ресурсов. Наиболее приемлемый вариант для линий связи, когда сжатие и восстановление происходит однократно на двух её концах (например, в цифровой телефонии). Алгоритм сжатия существенно менее требователен, чем алгоритм восстановления. Такая ситуация характерна для случаев, когда процедура сжатия реализуется простым, часто портативным устройством, для которого объём доступных ресурсов весьма критичен, например, космический аппарат или большая распределённая сеть датчиков. Это могут быть также данные, распаковка которых требуется в очень малом проценте случаев, например запись камер видеонаблюдения.

3. Алгоритмы сжатия данных неизвестного формата

Имеется два основных подхода к сжатию данных неизвестного формата.

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

Литература

• Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - Диалог-МИФИ, 2002. - С. 384. - ISBN 5-86404-170-X 3000 экз.
• Д. Сэломон. Сжатие данных, изображения и звука. - М .: Техносфера, 2004. - С. 368. - ISBN 5-94836-027-X 3000 экз.

Термин оператор встречается в разных разделах математики, его точное значение зависит от раздела. Как правило, под операторами понимают какие-то особые (для данной области математики) отображения, например в функциональном анализе под операторами понимают отображение, ставящее в соответствие функции другую функцию («оператор на пространстве функций» звучит лучше, чем «функция от функции»).

Наиболее часто встречающиеся операторы:

• Функциональный анализ : Операторы на пространствах функций (дифференцирование, интегрирование, свертка с ядром, преобразование Фурье).
• Линейная алгебра : Отображения (в особенности линейные) векторных пространств (проекторы, повороты координат, гомотетии, умножения вектора на матрицу).
• Дискретная математика : Преобразование последовательностей (свертки дискретных сигналов, медианный фильтр и т. п.).

Энциклопедичный YouTube

• 1 / 5

  Пусть оператор A {\displaystyle A} действует из множества X {\displaystyle X} в множество Y {\displaystyle Y} .

  • Оператор может быть не всюду определен на X {\displaystyle X} ; тогда говорят о его области определения D A = D (A) ⊂ X {\displaystyle D_{A}=D(A)\subset X} .
  • Для x ∈ X {\displaystyle x\in X} результат применения оператора A {\displaystyle A} к x {\displaystyle x} обозначают A (x) {\displaystyle A(x)} или A x {\displaystyle Ax} .
  • Если X {\displaystyle X} и Y {\displaystyle Y} - векторные пространства , то в множестве всех операторов из X {\displaystyle X} в Y {\displaystyle Y} можно выделить класс линейных операторов .
  • Если X {\displaystyle X} и Y {\displaystyle Y} - векторные топологические пространства , то в множестве операторов из X {\displaystyle X} в Y {\displaystyle Y} естественно выделяется класс непрерывных операторов , а также класс линейных ограниченных операторов и класс линейных компактных операторов (называемые также вполне непрерывными).

  Простые примеры

  Оператор, действующий над пространствами функций - это правило, согласно которому одна функция преобразуется в другую. Преобразование функции согласно правилу A {\displaystyle A} в другую функцию y (t) {\displaystyle y(t)} имеет вид y (t) = A { x (t) } {\displaystyle y(t)=A\{x(t)\}} или, проще, y = A x {\displaystyle y=Ax} .

  Примеры подобных преобразований - умножение на число: y (t) = c x (t) {\displaystyle y(t)=cx(t)} и дифференцирование: y (t) = d x (t) d t {\displaystyle \scriptstyle y(t)={\frac {dx(t)}{dt}}} . Соответствующие операторы называются операторами умножения на число, дифференцирования, интегрирования, решения дифференциального уравнения и т. д.

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

  F (ω) = 1 2 π ∫ − ∞ ∞ f (t) e − i t ω d t = F { f (t) } . {\displaystyle F(\omega)={\frac {1}{\sqrt {2\pi }}}\int \limits _{-\infty }^{\infty }f(t)e^{-it\omega }\,dt={\mathcal {F}}\{f(t)\}.}

  Отличие оператора от простой суперпозиции функций в данном случае заключается в том, что значение функции y {\displaystyle y} , вообще говоря, в каждой точке t {\displaystyle t} зависит не только от x (t) {\displaystyle x(t)} , а от значений функции x {\displaystyle x} во всех точках t {\displaystyle t} . Поясним на примере преобразования Фурье. Значение этого преобразования (спектр функции) в точке ω {\displaystyle \omega } меняется при непрерывном изменении исходной функции в окрестности любой точки t {\displaystyle t} .

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

  Фундаментальным для практики является класс так называемых линейных операторов . Он также является наиболее исследованным. В качестве примера линейного оператора можно привести операцию умножения n {\displaystyle n} -мерного вектора на матрицу размером n × m {\displaystyle n\times m} . Этот оператор отображает n {\displaystyle n} -мерное пространство векторов в m {\displaystyle m} -мерное.

  Линейные операторы

  Оператор L {\displaystyle L} (действующий из векторного пространства в векторное же) называется линейным однородным (или просто линейным ), если он обладает следующими свойствами:

  Из 2) следует, что для линейного однородного оператора справедливо свойство L (0) = 0 {\displaystyle L(0)=0} .

  Оператор L {\displaystyle L} называется линейным неоднородным , если он состоит из линейного однородного оператора с прибавлением некоторого фиксированного элемента:

  L { x } = L 0 { x } + φ {\displaystyle L\{x\}=L_{0}\{x\}+\varphi } ,

  где L 0 {\displaystyle L_{0}} - линейный однородный оператор.

  В случае линейного преобразования дискретных функций (последовательностей, векторов) новые значения функций y k {\displaystyle y_{k}} являются линейными функциями от старых значений x k {\displaystyle x_{k}} :

  y k = ∑ l = 1 n T k l x l {\displaystyle y_{k}=\sum _{l=1}^{n}T_{kl}\,x_{l}} .

  В более общем случае непрерывных функций двумерная матрица весов принимает вид функции двух переменных K (t , ω) {\displaystyle K(t,\;\omega)} , и называется ядром линейного интегрального преобразования:

  φ (t) = ∫ V K (t , ω) f (ω) d ω = K { f (ω) } . {\displaystyle \varphi (t)=\int \limits _{V}\!K(t,\omega)f(\omega)\,d\omega =K\{f(\omega)\}.}

  Функция-операнд в данном случае называется спектральной функцией. Спектр может быть и дискретным, тогда f (ω) {\displaystyle f(\omega)} заменяется вектором W {\displaystyle W} . В этом случае φ (t) {\displaystyle \varphi (t)} представимо конечным или бесконечным рядом функций:

  φ (t) = ∑ i = 1 n T i (t) w i . {\displaystyle \varphi (t)=\sum _{i=1}^{n}T_{i}(t)w_{i}.}

  Нулевой оператор

  Оператор O {\displaystyle O} нулевой вектор 0 {\displaystyle \mathbf {0} } , очевидно, линейный; он называется нулевым оператором .

  Единичный (тождественный) оператор

  Оператор E {\displaystyle E} , ставящий в соответствие каждому вектору a {\displaystyle \mathbf {a} } сам вектор a {\displaystyle \mathbf {a} } , очевидно, линейный; он называется единичным или тождественным оператором.

  Частный случай линейного оператора, возвращающий операнд в неизменном виде:

  E a = a , {\displaystyle E\mathbf {a} =\mathbf {a} ,}

  то есть как матричный оператор определяется равенством

  ∑ k E i k a k = a i {\displaystyle \sum _{k}E_{ik}\,a_{k}=a_{i}}

  и как интегральный оператор - равенством

  ∫ α β E (x , t) a (t) d t = a (x) {\displaystyle \int \limits _{\alpha }^{\beta }\!E(x,t)a(t)\,dt=a(x)} .

  Единичная матрица E i k {\displaystyle E_{ik}} записывается большей частью с помощью символа δ i k = δ k i {\displaystyle \delta _{ik}=\delta _{ki}} (символ Кронекера). Имеем: δ i k = 1 {\displaystyle \delta _{ik}=1} при i = k {\displaystyle i=k} и δ i k = 0 {\displaystyle \delta _{ik}=0} при i ≠ k {\displaystyle i\neq k} .

  Единичное ядро E (x , t) {\displaystyle E(x,t)} записывается в виде E (x , t) = δ (t − x) {\displaystyle E(x,t)=\delta (t-x)} (дельта-функция). δ (x − t) = 0 {\displaystyle \delta (x-t)=0} всюду, кроме x = t {\displaystyle x=t} , где функция становится бесконечной и притом такой, что

  ∫ α β δ (x − t) d t = 1 {\displaystyle \int \limits _{\alpha }^{\beta }\!\delta (x-t)\,dt=1} .

  Запись

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

  • префиксная : где первым идёт оператор и операнды следом, например:
  Q (x 1 , x 2 , … , x n) ; {\displaystyle Q(x_{1},\;x_{2},\;\ldots ,\;x_{n});}
  • постфиксная : если символ оператора следует за операндами, например:
  (x 1 , x 2 , … , x n) Q ; {\displaystyle (x_{1},\;x_{2},\;\ldots ,\;x_{n})\;Q;}
  • инфиксная : оператор вставляется между операндами, применяется преимущественно с двоичными операторами:
  x 1 Q x 2 ; {\displaystyle x_{1}\;Q\;x_{2};}
  • позиционная : знак оператора опускается, оператор присутствует неявно. Чаще всего не пишется оператор произведения (переменных, численного значения на физическую единицу, матриц, композиция функций), например, 3 кг. Такая способность одного оператора действовать над разнородными сущностями достигается перегрузкой операторов ;
  • подстрочная или надстрочная слева или справа; главным образом используется для операций возведения в степень и выбора элемента вектора по индексу.

  Как можно заметить, запись оператора часто принимает сокращённую форму от общепринятой записи функций. При использовании префиксной или постфиксной записи скобки опускаются в большинстве случаев, если известна арность оператора. Так, одинарный оператор Q {\displaystyle Q} над функцией f {\displaystyle f} обычно для краткости записывается Q f {\displaystyle Qf} вместо Q (f) {\displaystyle Q(f)} ; скобками пользуются для ясности, например, операция над произведением Q (f g) {\displaystyle Q(fg)} . Q {\displaystyle Q} , действующий на f (x) {\displaystyle f(x)} , также записывают (Q f) (x) {\displaystyle (Qf)(x)} . Для обозначения некоторых операторов вводятся специальные знаки, например, унарные n ! {\displaystyle n!} (факториал «!», справа от операнда), − n {\displaystyle -n} (отрицание, слева) или каллиграфические символы, как в случае с Фурье-преобразованием функции F { f (t) } {\displaystyle {\mathcal {F}}\{f(t)\}} . Возведение в степень n x {\displaystyle n^{x}} можно считать бинарным оператором двух аргументов либо степенной или показательной функцией одного аргумента.

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

  Пусть x = (x 1 , … , x n) {\displaystyle x=(x_{1},\ldots ,x_{n})} и имеются мультииндексы α = (α 1 , … , α n) {\displaystyle \alpha =(\alpha _{1},\ldots ,\alpha _{n})} и β = (β 1 , … , β n) {\displaystyle \beta =(\beta _{1},\ldots ,\beta _{n})} . Тогда положим

  D α x β = ∂ | α | ∂ x 1 α 1 ⋯ ∂ x n α n x 1 β 1 ⋯ x n β n = ∂ α 1 ∂ x 1 α 1 x 1 β 1 ⋯ ∂ α n ∂ x n α n x n β n . {\displaystyle {\begin{aligned}D^{\alpha }x^{\beta }&={\frac {\partial ^{\vert \alpha \vert }}{\partial x_{1}^{\alpha _{1}}\cdots \partial x_{n}^{\alpha _{n}}}}x_{1}^{\beta _{1}}\cdots x_{n}^{\beta _{n}}\\&={\frac {\partial ^{\alpha _{1}}}{\partial x_{1}^{\alpha _{1}}}}x_{1}^{\beta _{1}}\cdots {\frac {\partial ^{\alpha _{n}}}{\partial x_{n}^{\alpha _{n}}}}x_{n}^{\beta _{n}}.\end{aligned}}}

  Пусть P -- линейный дифференциальный оператор порядка k на евклидовом пространстве R d . Тогда P является полиномом от производной D , в мультииндексной записи это будет записываться так

  P = p (x , D) = ∑ | α | ≤ k a α (x) D α . {\displaystyle P=p(x,D)=\sum _{|\alpha |\leq k}a_{\alpha }(x)D^{\alpha }.}

  Полином p , по определению, является полным символом P :

  σ P (ξ) = p (x , ξ) = ∑ | α | ≤ k a α ξ α . {\displaystyle \sigma P(\xi)=p(x,\xi)=\sum _{|\alpha |\leq k}a_{\alpha }\xi ^{\alpha }.}

  Главный символ оператора состоит из мономов максимальной степени σP :

  σ P (ξ) = ∑ | α | = k a α ξ α {\displaystyle \sigma _{P}(\xi)=\sum _{|\alpha |=k}a_{\alpha }\xi ^{\alpha }}