Ассоциация символа и кода символа

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

Вернемся к исследованию предложения "Подготовка к ГИА и ЕГЭ". Как видно, данное предложение содержит достаточно много различных букв из русского алфавита, а также имеются повторяющиеся буквы, например, буквы 'о', 'а', 'к', 'Г' и др. Сразу небольшая оговорка: одна и та же малая и большая буквы имеют различный двоичный код в таблице ASCII, то есть буквы 'а' и 'А' будут кодироваться различным набором из 0 и 1.

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

Символ русского алфавита	Двоичный код символа
'А'
'Б'
'В'
'Г'
…	…
'Я'
'а'
…	…
'я'

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

Сходу возникает вопрос: а почему отводится восемь позиций на двоичный код символа при кодировании текстовой информации? Потому что для хранения одного символа будет задействован 1 байт информации или 8 бит. Таким образом устроена кодировочная таблица ASCII. Отсюда вытекает умозаключение, что максимальное количество закодированных символов в таблице ASCII не может превышать 256, так как 2⁸ = 256. Существует кодировочная таблица, называемая Unicode, вот она при кодировании текстовой информации преобразует символы в шестнадцатипозиционный двоичный код. Это связано с тем, что для хранения одного символа задействуется 2 байта памяти или 16 бит информации. Следовательно, таблица Unicode может кодировать до 2¹⁶ = 65536 различных символов.

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

Давайте произведем кодирование текстовой информации, а конкретно предложения "Подготовка к ГИА и ЕГЭ". Для этого построим таблицу, в которой каждому символу русского алфавита сопоставим двоичный код из кодировочной таблицы ASCII. Разделители между словами, то есть знаки пробела, также закодируем.

П	о	д	г	о	т	о	в	к	а

 

	к		Г	И	А		и		Е	Г	Э

То есть перед тем, как записать текстовое предложение "Подготовка к ГИА и ЕГЭ" на жесткий диск, компьютер произведет кодирование текстовой информации и получит следующий бинарный код:

А вот подобные цепочки, наборы из 0 и 1 прекрасно распознаются процессором и он максимально оперативно произведет всю необходимую обработку над ними.

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

Кодирование звука

Кодирование звука применяется с целью уменьшения объема файла и осуществляется при помощи специальных алгоритмов сжатия, именуемых кодеками. Наиболее распространённый алгоритм сжатия аудио MP3 (MPEG Layer-3) — создан немецким институтом Фраунгофера (Fraunhofer Institut für Integrierte Schaltungen) в 1989 году.

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

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

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

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

 

Помимо грамотно разрекламированного алгоритма сжатия mp3, существует менее популярный, но более поздний и более качественный алгоритм сжатия, разработанный компанией Майкрософт — WMA (Windows Media Audio). Данный формат позволяет осуществлять сжатие звука до 64 кб/секунду при частоте дискретизации 48 кГц, что существенно снижает объем файла. И это при том, что сохраняется частотный диапазон до 20 000 кГц.

Для сравнения, сжатие звука в формате mp3 до 64 кб/секунду возможно только с частотой дискретизации 22050 Гц, что приводит к сужению диапазона до 7 кГц. Справедливости ради стоит заметить, что сейчас, когда носители информации размером с ноготь — способны хранить от 1 гигабайта информации и больше, нет необходимости в столь сильном сжатии.

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

Истинные же ценители звука предпочитают слушать виниловые пластинки, считая их звучание непревзойденным. На самом же деле, только новая виниловая пластинка (без пробега) способна хранить частоту до 25 кГц, которую, кстати, не способны воспроизводить даже ультрасовременные музыкальные центры. А непревзойденным следует считать звучание живого музыкального инструмента без студийной обработки. Да и человеческое ухо не способно слышать ультразвук. Качество же винилового носителя, после трех прослушиваний, снижается до 18 кГц, а каждые последующие три прослушивания "съедают" качество записи винила вплоть до 12 кГц.

Алгоритмы сжатия картинок

Легко подсчитать, что несжатое полноцветное изображение, размером 2000*1000 пикселов будет иметь размер около 6 мегабайт. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений.
Все существующие алгоритмы можно разделить на два больших класса:

 

· Алгоритмы сжатия без потерь;

· Алгоритмы сжатия с потерями.

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

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

 

Алгоритм RLE

Все алгоритмы серии RLE основаны на очень простой идее: повторяющиеся группы элементов заменяются на пару (количество повторов, повторяющийся элемент). Рассмотрим этот алгоритм на примере последовательности бит. В этой последовательности будут чередовать группы нулей и единиц. Причём в группах зачастую будет более одного элемента. Тогда последовательности 11111 000000 11111111 00 будет соответствовать следующий набор чисел 5 6 8 2. Эти числа обозначают количество повторений (отсчёт начинается с единиц), но эти числа тоже необходимо кодировать. Будем считать, что число повторений лежит в пределах от 0 до 7 (т.е. нам хватит 3 бит для кодирования числа повторов). Тогда рассмотренная выше последовательность кодируется следующей последовательностью чисел 5 6 7 0 1 2. Легко подсчитать, что для кодирования исходной последовательности требуется 21 бит, а в сжатом по методу RLE виде эта последовательность занимает 18 бит.
Хоть этот алгоритм и очень прост, но эффективность его сравнительно низка. Более того, в некоторых случаях применение этого алгоритма приводит не к уменьшению, а к увеличению длины последовательности. Для примера рассмотрим следующую последовательность 111 0000 11111111 00. Соответствующая ей RL-последовательность выглядит так: 3 4 7 0 1 2. Длина исходной последовательности – 17 бит, длина сжатой последовательности – 18 бит.
Этот алгоритм наиболее эффективен для чёрно-белых изображений. Также он часто используется, как один из промежуточных этапов сжатия более сложных алгоритмов.

 

Словарные алгоритмы

Идея, лежащая в основе словарных алгоритмов, заключается в том, что происходит кодирование цепочек элементов исходной последовательности. При этом кодировании используется специальный словарь, который получается на основе исходной последовательности.
Существует целое семейство словарных алгоритмов, но мы рассмотрим наиболее распространённый алгоритм LZW, названный в честь его разработчиков Лепеля, Зива и Уэлча.
Словарь в этом алгоритме представляет собой таблицу, которая заполняется цепочками кодирования по мере работы алгоритма. При декодировании сжатого кода словарь восстанавливается автоматически, поэтому нет необходимости передавать словарь вместе с сжатым кодом.
Словарь инициализируется всеми одноэлементными цепочками, т.е. первые строки словаря представляют собой алфавит, в котором мы производим кодирование. При сжатии происходит поиск наиболее длинной цепочки уже записанной в словарь. Каждый раз, когда встречается цепочка, ещё не записанная в словарь, она добавляется туда, при этом выводится сжатый код, соответствующий уже записанной в словаре цепочки. В теории на размер словаря не накладывается никаких ограничений, но на практике есть смысл этот размер ограничивать, так как со временем начинаются встречаться цепочки, которые больше в тексте не встречаются. Кроме того, при увеличении размеры таблицы вдвое мы должны выделять лишний бит для хранения сжатых кодов. Для того чтобы не допускать таких ситуаций, вводится специальный код, символизирующий инициализацию таблицы всеми одноэлементными цепочками.
Рассмотрим пример сжатия алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Предположим, что словарь будет вмещать 32 позиции, а значит, каждый его код будет занимать 5 бит. Изначально словарь заполнен следующим образом:

Эта таблица есть, как и на стороне того, кто сжимает информацию, так и на стороне того, кто распаковывает. Сейчас мы рассмотрим процесс сжатия.

В таблице представлен процесс заполнения словаря. Легко подсчитать, что полученный сжатый код занимает 105 бит, а исходный текст (при условии, что на кодирование одного символа мы тратим 4 бита) занимает 116 бит.
По сути, процесс декодирования сводится к прямой расшифровке кодов, при этом важно, чтобы таблица была инициализирована также, как и при кодировании. Теперь рассмотрим алгоритм декодирования.

Строку, добавленную в словарь на i-ом шаге мы можем полностью определить только на i+1. Очевидно, что i-ая строка должна заканчиваться на первый символ i+1 строки. Т.о. мы только что разобрались, как можно восстанавливать словарь. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c — это один символ, а S — строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.