За счет происходит сжатие информации. Сжатие изображений: JPEG и JPEG2000. JPEG теряет качество при редактировании файла

А сегодня мы с Вами будем учиться раскрашивать наши объекты:)

Если у кого-то с самостоятельным обучением возникают какие-либо затруднения, то вы можете взять через Skype.

Заливка цветом с помощью палитры «Образцы» (Swatches)

Чтобы закрасить объект, откройте свою палитру «Образцы» (Swatches Palette). Выделите свой объект и нажмите на нужный цвет в палитре.

Заливка цветом с помощью палитры цветов (Color Picker)

Еще один способ закрасить объект — кликнуть два раза по значку «Заливка» (Fill) в Вашей панели инструментов. Выскочит окошко «Палитра цветов» (Color Picker), и Вы сможете выбрать нужный Вам цвет.

Изменяем заливку и обводку, используя управляющую палитру (Сontrol Palette)

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

Концы обводки

От того, какой тип конца обводки Вы выберете, будет зависеть вид ее начальной и конечной точек. Этот инструмент применяется только к открытым контурам. Вы можете выбрать между срезанным (Butt), скругленным (Round) и выступающим (Projecting) концами.

Срезание (Milter Limit)

Срезание (Milter Limit) применяется к стыкам в фигурах. Обратите внимание, как выглядят стыки звезды после применения разных настроек срезания.

Применение градиента к объектам

Чтобы применить градиент к Вашему объекту, на панели инструментов выставьте градиентную заливку (Gradient Fill).

Затем откройте палитры «Градиент» (Gradient) и «Цвет» (Color). По умолчанию у нас стоит режим цвета «Градации серого» (Grayscale). Нажмите на иконку настроек в углу и выберите режим RGB.

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

Проделаем то же самое для начальной точки в градиентной шкале (сейчас она белая). Выставьте режим RGB и выберите голубой цвет.

Чтобы добавить новый цвет в градиентную шкалу, Tony предлагает кликнуть левой кнопкой мышки прямо под шкалой в нужном месте. Затем к новому цвету можно применить процедуру, описанную выше, выбрав на этот раз белый цвет.

Лично я обычно поступаю немного по-другому. Если в палитре «Образцы» (Swatches) есть нужный мне цвет, то я просто перетаскиваю его мышкой на градиентную шкалу в нужное мне место.

Чтобы убрать лишний цвет из градиентной шкалы, просто потяните ползунок мышкой вниз.

Если Вы хотите изменить направление градиента, выберите инструмент «Градиент» (Gradient Tool) на панели инструментов (Tool Palette). Кликните на объект и, удерживая левую кнопку мышки, задайте градиенту нужное направление.

Радиальный градиент

Чтобы изменить тип градиента на радиальный, выберите «Радиальный» (Radial) вместо «Линейного» (Linear).

Текстурная заливка

Чтобы создать бесшовную текстурную заливку, выберите заливку «Узор» (Pattern swatches) из палитры «Образцы» (Swatches).

Заключение

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

Кстати, насчет этих самых колокольчиков:) Они тоже не лежат просто так в портфолио Tony, а активно приносят ему деньги, продаваясь на Istockphoto:)

Не пропустите следующий урок:

Сегодня Натали Ульрих поделится с нами несколькими очень интересными «фишками». В этой статье мы поговорим о работе с цветом, градиентными заливками и особенностях работы с инструментом Пипетка (Eyedropper Tool). Также мы снова поговорим о выравнивании объектов и узнаем, как выровнять объекты с обводкой. Лично я нашла в этой статье много новой и полезной информации.

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

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

Быстрая отмена заливки или обводки

Если хотите отменить Заливку или Обводку, нажмите кнопку с косой чертой /.

Чтобы поменять местами цвет заливки и обводки, нажмите сочетание клавиш Shift + X.

Выбираем Пипеткой только цвет

По умолчанию инструмент Пипетка (Eyedropper Tool) копирует внешний вид объекта, а именно: цвет заливки и обводки, настройки обводки и прозрачности и т. д. Эти настройки можно задать в окне, которое откроется, если дважды щелкнуть по кнопке инструмента (см. рисунок).

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

Трансформация узора отдельно от объекта

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

Используем Глобальный цвет

Глобальный цвет позволяет создать документ, в котором легко поменять цвета всех объектов. Создайте новый образец цвета в палитре Каталог (Swatches panel). Дважды щелкните созданный образец и в открывшемся окне Параметры образцов (Swatch Options) поставьте галочку возле Глобальные.

Используйте этот образец для всех объектов, цвет которых вы хотите изменить. Если есть возможность, примените Глобальный цвет просто двойным щелчком по его образцу в палитре. Или перетащите в палитре на Глобальный цвет другой образец, удерживая клавишу Option/Alt. На рисунке (см. ниже) было создано два Глобальных цвета. Один для фона, другой для объектов. И можно легко изменить цвет всех объектов, не выделяя их как группу.

Образец цвета из любой точки экрана

Скопировать цвет можно из любой точки экрана. Даже за пределами Adobe Illustrator. Выберите инструмент Пипетка и щелкните в любом свободном месте. Удерживая кнопку мышки, перетащите инструмент на любой видимый цвет, даже в любой другой программе или просто на рабочем столе. При перемещении курсора цвет меняется автоматически. Можно выбрать любой цвет, кроме цвета кнопки «Start» в операционной системе Windows Vista.

Применяем выбранные цвета

После того как вы выбрали цвет инструментом Пипетка, его можно применить к невыделенному объекту, если удерживать клавишу Option/Alt. При этом кончик инструмента становится черным.

Выбираем цвет градиента

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

Копируем цвет на Шкале градиента

Если вам нужен одинаковый цвет в разных местах градиента, можно скопировать цвет растяжки. Удерживая клавишу Option/Alt, щелкните прямоугольничек на шкале градиента и перетащите в нужное место, создав новый прямоугольничек.

Меняем местами цвета на Шкале градиента

Чтобы поменять местами цвета на Шкале градиента, перетащите один прямоугольничек на другой, удерживая клавишу Option/Alt.

Используем для градиента образцы из Каталога цветов

Если выбрать прямоугольничек на градиентной шкале в палитре Градиент (Gradient panel), а затем щелкнуть образец в палитре Каталог цветов (Swatches panel), изменится цвет объекта, а не градиента. Чтобы изменить цвет прямоугольничка на градиентной шкале, выберите необходимый прямоугольничек, нажмите клавишу Option/Alt и щелкните образец в палитре Каталог цветов. Также можно перетащить образец из палитры Каталог цветов (Swatches panel) на градиентную шкалу в палитре Градиент (Gradient panel), чтобы изменить цвет прямоугольничка или создать новый.

Меняем цвет обводки

Цвет обводки можно легко и быстро изменить, даже не выделяя. Перетащите образец цвета из палитры Каталог или Цвет на обводку. Если в палитре инструментов обводка не активна, перетаскивая образец, удерживайте клавишу Shift.

Меняем цветовую модель в палитре Цвет

Чтобы изменить цветовую модель в палитре Цвет (Color panel), например RGB или HSB, щелкайте Спектр палитры (Color Spectrum Bar), удерживая клавишу Shift. И выберите нужную вам цветовую модель из тех, что есть.

Если вам нужен серый цвет, получить его можно двумя способами. Можно использовать цветовой режим Серая шкала (Grayscale) и менять насыщенность цвета от белого (0%) до черного (100%). Но при этом объект всегда будет оставаться серым, и вы не сможете сделать его цветным, пока не измените цветовой режим. Чтобы этого избежать, выберите в палитре Цвет (Color panel) цветовую модель CMYK и задайте в поле значение для K. Для остальных установите — 0%.

При выравнивании объектов или изменении их размеров в Adobe Illustrator учитываются контуры объекта, а толщина обводки по умолчанию игнорируется. Чтобы учитывалась толщина обводки, поставьте галочку возле команды Использовать границы просмотра (Use Preview Bounds) в окне Установки (меню Редактирование, Установки, Основные). Чтобы открыть окно, используйте сочетание клавиш Cmd/Ctrl + K. Теперь все изменения и расчеты будут производиться с учетом толщины обводки (см. рисунок ниже).

Единственный недостаток этого совета в том, что выбранная опция будет влиять на все дальнейшие действия и изменения. Но при использовании палитры Выравнивание (Align panel), эту опцию можно включать/выключать в меню палитры.

У вас остались вопросы или есть что добавить по теме статьи?

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

Клавиши работы с документом в иллюстраторе

CTRL+N – создать новый документ.
CTRL+O – открыть документ.
CTRL+W – закрыть документ.
CTRL+S – Сохранить документ. Сохраняйте ваш документ каждые 10-15 минут.
CTRL+SHIFT+S – Сохранить как.

Клавиши редактирования

CTRL+Z – Undo (Отменить).
CTRL+SHIFT+Z – Redo (Повторить отмененное действие).
CTRL+ D – повторить последнее действие по трансформации объекта.

Копирование объектов

CTRL+X, F2 – Вырезать.
CTRL+C, F3 – Скопировать.
CTRL+V, F4 – Вклеить.
Перетаскиваем объект, удерживая ALT.
CTRL+F – вставить сверху в тоже место откуда копировали
CTRL+B – вставить снизу в тоже место откуда копировали

Масштабирование и навигация (перемещение по документу)

Ctrl+R вызов линейки.
CTRL+U – вызвать умные направляющие.
Ctrl+ + увеличить масштаб.
Ctrl+ – уменьшить масштаб.
Ctrl+) – станет виден весь печатный лист.
Ctrl+пробел временное переключение в режим инструмента Масштаб увеличить.
Ctrl+Alt+пробел временное переключение в режим инструмента Масштаб уменьшить.
Пробел – временное переключение в режим перемещения.

Работа с объектами

Ctrl+Shift+B – рамка трансформации (габаритный контейнер) показать/скрыть

Палитра Слои

Ctrl+L создание нового слоя
Ctrl+Alt+L создание нового слоя с вызовом настроек

Изменение цвета

D – значения цветов по умолчанию, цвет заливки – белый, цвет обводки – черный.
X – переключение между заливкой и обводкой.
/ – сделать цвет прозрачным (отмена заливки).
– заливка градиентом.
F9 – показать/скрыть палитру Градиент.
F10 – показать/скрыть палитру Обводка.

Расположение объектов в документе

CTRL+SHIFT+] – поместить объект на передний план.
CTRL+SHIFT+[ – поместить объект на задний план.
CTRL+] – переместить объект на 1 объект выше.
CTRL+[ – переместить объект на 1 объект ниже.
CTRL+G – группировать объекты.
CTRL+2 – заблокировать выделенные объекты.
CTRL+ALT+2 – заблокировать невыделенные объекты.
CTRL+SHIFT+2 – разблокировать объекты.

Панель инструментов

TAB – скрыть/показать панель инструментов и все палитры.
SHIFT+TAB – скрыть/показать все палитры, не показывая панели инструментов.

Выделение

CTRL+A – Выделить все.
CTRL+SHIFT+A – убрать выделение.

Группировка объектов

CTRL+G – сгруппировать объекты.
CTRL+SHIFT+G – разгруппировать объекты.

Работа с кривыми Безье

CTRL+J – соединить 2 точки в одну

CTRL+Y – переключение между режимами просмотра документа, например просмотреть все объекты в виде контуров.

CapsLock – смена курсора инструментов рисования.

Подробности Категория: Adobe решение проблем, советы Просмотров: 687

Как заполнить область в Illustrator

Читай больше по темам:

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

1. Щелкните на значке «Инструмент выбора» или «Инструмент прямого выбора», который представляет собой черные или белые стрелки на панели «Инструменты», а затем щелкните объект, который вы хотите заполнить. В качестве альтернативы нажмите «V» на клавиатуре, чтобы использовать инструмент «Выделение», или нажмите «A», чтобы использовать инструмент «Прямой выбор».
2. Нажмите значок «Заполнить» на панели «Инструменты» или нажмите «X», чтобы активировать инструмент «Заливка». Значок инструмента «Заливка» представляет собой сплошной квадрат двух перекрывающихся квадратов на панели «Инструменты». Другой квадрат, который имеет черный ящик посередине, предназначен для внешнего края объекта, известного как штрих.
3. Выберите цвет, который вы хотите использовать для заполнения панели «Цвет», которая открывается при активации инструмента «Заливка». Вы также можете открыть панель «Образцы» или «Градиент» и выбрать цвет из этих библиотек. Один из последних вариантов - дважды щелкнуть инструмент «Заполнить», выбрать цвет в окне «Выбор цвета» и нажать «ОК».

Наконечник

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

Предупреждение

Информация в этой статье относится к Adobe Illustrator CS6. Он может немного отличаться или значительно отличаться от других версий или продуктов.

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

В этой статье я коснусь фундаментальных моментов сжатия и основных типов алгоритмов.

Сжатие. Нужно ли оно в наше время?

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

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

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

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

Итак, перейдем к рассмотрению алгоритмов сжатия без потерь.

Универсальные методы сжатия без потерь

В общем случае можно выделить три базовых варианта, на которых строятся алгоритмы сжатия.
Первая группа методов – преобразование потока. Это предполагает описание новых поступающих несжатых данных через уже обработанные. При этом не вычисляется никаких вероятностей, кодирование символов осуществляется только на основе тех данных, которые уже были обработаны, как например в LZ – методах (названных по имени Абрахама Лемпеля и Якоба Зива). В этом случае, второе и дальнейшие вхождения некой подстроки, уже известной кодировщику, заменяются ссылками на ее первое вхождение.

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

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

Общие принципы, на которых основано сжатие данных

Все методы сжатия данных основаны на простом логическом принципе. Если представить, что наиболее часто встречающиеся элементы закодированы более короткими кодами, а реже встречающиеся – более длинными, то для хранения всех данных потребуется меньше места, чем если бы все элементы представлялись кодами одинаковой длины.
Точная взаимосвязь между частотами появления элементов, и оптимальными длинами кодов описана в так называемой теореме Шеннона о источнике шифрования(Shannon"s source coding theorem), которая определяет предел максимального сжатия без потерь и энтропию Шеннона.

Немного математики

Если вероятность появления элемента s i равна p(s i), то наиболее выгодно будет представить этот элемент - log 2 p(s i) битами. Если при кодировании удается добиться того, что длина всех элементов будет приведена к log 2 p(s i) битам, то и длина всей кодируемой последовательности будет минимальной для всех возможных методов кодирования. При этом, если распределение вероятностей всех элементов F = {p(s i)} неизменно, и вероятности элементов взаимно независимы, то средняя длина кодов может быть рассчитана как

Это значение называют энтропией распределения вероятностей F, или энтропией источника в заданный момент времени.
Однако обычно вероятность появления элемента не может быть независимой, напротив, она находится в зависимости от каких-то факторов. В этом случае, для каждого нового кодируемого элемента s i распределение вероятностей F примет некоторое значение F k , то есть для каждого элемента F= F k и H= H k .

Иными словами, можно сказать, что источник находится в состоянии k, которому соответствует некий набор вероятностей p k (s i) для всех элементов s i .

Поэтому, учитывая эту поправку, можно выразить среднюю длину кодов как

Где P k - вероятность нахождения источника в состоянии k.

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

Кодирование без памяти

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

Пусть задан некоторый алфавит , состоящий из некоторого (конечного) числа букв. Назовем каждую конечную последовательность символов из этого алфавита (A=a 1 , a 2 ,… ,a n) словом , а число n - длиной этого слова.

Пусть задан также другой алфавит. Аналогично, обозначим слово в этом алфавите как B.

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

Пусть также задано отображение F, которое ставит в соответствие каждому слову A из первого алфавита некоторое слово B=F(A) из второго. Тогда слово B будет называться кодом слова A, а переход от исходного слова к его коду будет называться кодированием .

Поскольку слово может состоять и из одной буквы, то мы можем выявить соответствие букв первого алфавита и соответствующих им слов из второго:
a 1 <-> B 1
a 2 <-> B 2
…
a n <-> B n

Это соответствие называют схемой , и обозначают ∑.
В этом случае слова B 1 , B 2 ,…, B n называют элементарными кодами , а вид кодирования с их помощью - алфавитным кодированием . Конечно, большинство из нас сталкивались с таким видом кодирования, пусть даже и не зная всего того, что я описал выше.

Итак, мы определились с понятиями алфавит, слово, код, и кодирование . Теперь введем понятие префикс .

Пусть слово B имеет вид B=B"B"". Тогда B" называют началом, или префиксом слова B, а B"" - его концом. Это довольно простое определение, но нужно отметить, что для любого слова B, и некое пустое слово ʌ («пробел»), и само слово B, могут считаться и началами и концами.

Итак, мы подошли вплотную к пониманию определения кодов без памяти. Последнее определение, которое нам осталось понять - это префиксное множество. Схема ∑ обладает свойством префикса, если для любых 1≤i, j≤r, i≠j, слово B i не является префиксом слова B j .
Проще говоря, префиксное множество – это такое конечное множество, в котором ни один элемент не является префиксом (или началом) любого другого элемента. Простым примером такого множества является, например, обычный алфавит.

Итак, мы разобрались с основными определениями. Так как же происходит само кодирование без памяти?
Оно происходит в три этапа.

1. Составляется алфавит Ψ символов исходного сообщения, причем символы алфавита сортируются по убыванию их вероятности появления в сообщении.
2. Каждому символу a i из алфавита Ψ ставится в соответствие некое слово B i из префиксного множества Ω.
3. Осуществляется кодирование каждого символа, с последующим объединением кодов в один поток данных, который будет являться результатам сжатия.

Одним из канонических алгоритмов, которые иллюстрируют данный метод, является алгоритм Хаффмана.

Алгоритм Хаффмана

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

В первую очередь при кодировании алгоритмом Хаффмана, нам нужно построить схему ∑. Делается это следующим образом:

1. Все буквы входного алфавита упорядочиваются в порядке убывания вероятностей. Все слова из алфавита выходного потока (то есть то, чем мы будем кодировать) изначально считаются пустыми (напомню, что алфавит выходного потока состоит только из символов {0,1}).
2. Два символа a j-1 и a j входного потока, имеющие наименьшие вероятности появления, объединяются в один «псевдосимвол» с вероятностью p равной сумме вероятностей входящих в него символов. Затем мы дописываем 0 в начало слова B j-1 , и 1 в начало слова B j , которые будут впоследствии являться кодами символов a j-1 и a j соответственно.
3. Удаляем эти символы из алфавита исходного сообщения, но добавляем в этот алфавит сформированный псевдосимвол (естественно, он должен быть вставлен в алфавит на нужное место, с учетом его вероятности).

Шаги 2 и 3 повторяются до тех пор, пока в алфавите не останется только 1 псевдосимвол, содержащий все изначальные символы алфавита. При этом, поскольку на каждом шаге и для каждого символа происходит изменение соответствующего ему слова B i (путем добавление единицы или нуля), то после завершения этой процедуры каждому изначальному символу алфавита a i будет соответствовать некий код B i .

Для лучшей иллюстрации, рассмотрим небольшой пример.
Пусть у нас есть алфавит, состоящий из всего четырех символов - { a 1 , a 2 , a 3 , a 4 }. Предположим также, что вероятности появления этих символов равны соответственно p 1 =0.5; p 2 =0.24; p 3 =0.15; p 4 =0.11 (сумма всех вероятностей, очевидно, равна единице).

Итак, построим схему для данного алфавита.

1. Объединяем два символа с наименьшими вероятностями (0.11 и 0.15) в псевдосимвол p".
2. Объединяем два символа с наименьшей вероятностью (0.24 и 0.26) в псевдосимвол p"".
3. Удаляем объединенные символы, и вставляем получившийся псевдосимвол в алфавит.
4. Наконец, объединяем оставшиеся два символа, и получаем вершину дерева.

Если сделать иллюстрацию этого процесса, получится примерно следующее:

Как вы видите, при каждом объединении мы присваиваем объединяемым символам коды 0 и 1.
Таким образом, когда дерево построено, мы можем легко получить код для каждого символа. В нашем случае коды будут выглядить так:

A 1 = 0
a 2 = 11
a 3 = 100
a 4 = 101

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

Пусть на входу у нас была строка из 1000 символов, в которой символ a 1 встречался 500 раз, a 2 - 240, a 3 - 150, и a 4 - 110 раз.

Изначально данная строка занимала 8000 бит. После кодирования мы получим строку длинной в ∑p i l i = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 бит. Итак, нам удалось сжать данные в 4,54 раза, потратив в среднем 1,76 бита на кодирование каждого символа потока.

Напомню, что согласно Шеннону, средняя длина кодов составляет . Подставив в это уравнение наши значения вероятностей, мы получим среднюю длину кодов равную 1.75496602732291, что весьма и весьма близко к полученному нами результату.
Тем не менее, следует учитывать, что помимо самих данных нам необходимо хранить таблицу кодировки, что слегка увеличит итоговый размер закодированных данных. Очевидно, что в разных случаях могут с использоваться разные вариации алгоритма – к примеру, иногда эффективнее использовать заранее заданную таблицу вероятностей, а иногда – необходимо составить ее динамически, путем прохода по сжимаемым данным.

Заключение

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

Литература

• Ватолин Д., Ратушняк А., Смирнов М. Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео; ISBN 5-86404-170-X; 2003 г.
• Д. Сэломон. Сжатие данных, изображения и звука; ISBN 5-94836-027-Х; 2004г.