Не будучи специалистом в обозначенной области, я тем не менее прочитал много специализированной литературы для ознакомления с предметом и, прорываясь сквозь тернии к звездам, набрал немало шишек на начальных этапах.
При всем обилии информации мне не удалось найти простых статей о кодировании как таковом, вне рамок специализированной литературы (так сказать, без формул и с картинками).
Статья, в первой части, представляет собой ликбез по кодированию как таковому с примерами манипуляций с битовыми кодами, а во второй хотелось бы затронуть простейшие способы кодирования изображений.
0. Начало
Поскольку я обращаюсь к новичкам в этом вопросе, не посчитаю зазорным обратиться к Википедии.И там для обозначения кодирования информации мы имеем следующее определение — процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической обработки.
Чего мне не хватало в 70-80-е годы, так это в школе, пусть даже не по информатике, а, например, на уроках математики - базовой информации по кодированию.
Дело в том, что каждый из нас занимается кодированием информации ежесекундно, постоянно и вообще – не концентрируясь на самом кодировании.
То есть в повседневной жизни мы делаем это постоянно.
Так как же это происходит? Мимика, жесты, речь, сигналы разного уровня – знак с надписью, знак на дороге, светофор, а для современного мира – штрих-коды и штрих-коды, URL-адреса, хеш-теги.
Давайте рассмотрим некоторые более подробно.
1.1 Речь, мимика, жесты
Удивительно, но это все коды.С их помощью мы передаем информацию о наших действиях, чувствах и эмоциях.
Самое главное, чтобы коды были понятны всем.
Например, если вы родились в густых лесах Амазонки и не видели современного городского человека, вы можете столкнуться с проблемой непонимания кода – улыбка, как и показ зубов, будет воспринята как угроза, и не как выражение радости.
Согласно определению, что происходит, когда мы говорим? Мысль — как форма, удобная для непосредственного употребления, — преобразуется в речь — форму, удобную для передачи.
И, посмотрите, поскольку звук имеет ограничение и по скорости, и по дальности передачи, то, например, жест в какой-то ситуации может быть выбран для передачи той же информации, но на большее расстояние.
Но мы все равно будем ограничены диапазоном остроты нашего зрения, и тогда человек начнет придумывать другие способы передачи и преобразования информации, например, огонь или дым.
1.2 Переменные сигналы
Индийские пинги В примитивном виде кодирование переменными сигналами используется человечеством очень давно.
В предыдущем разделе мы говорили о дыме и огне.
Если между наблюдателем и источником огня будет размещено и удалено препятствие, будет казаться, что наблюдатель видит чередующиеся сигналы включения/выключения.
Изменяя частоту таких включений, мы можем разработать последовательность кодов, которая будет однозначно интерпретироваться принимающей стороной.
Наряду с сигнальными флагами на морских и речных судах с появлением радио стала использоваться азбука Морзе.
И несмотря на всю кажущуюся бинарность (представление кода двумя значениями), поскольку используются сигналы точки и тире, по сути это троичный код, поскольку для разделения отдельных кодов символов необходима пауза в передаче кода.
То есть азбука Морзе, кроме «точки-тире», которая дает нам букву «А», может звучать так – «точка-пауза-тире» и тогда это уже две буквы «ЕТ».
1.3 Контекст
Когда мы пользуемся компьютером, мы понимаем, что информация может быть разной – звук, видео, текст. Но каковы основные различия? И прежде чем приступить к кодированию информации, чтобы, например, передать ее по каналам связи, необходимо понять, что это за информация в каждом конкретном случае, то есть обратить внимание на содержание.Звук — это серия дискретных значений звукового сигнала, видео — это серия кадров изображения, текст — это серия текстовых символов.
Если не учитывать контекст, а, например, использовать азбуку Морзе для передачи всех трёх видов информации, то если для текста этот способ может быть приемлемым, то для звука и видео время, затрачиваемое на передачу, например, 1 секунда информации может оказаться слишком долгой – час или даже пара недель.
2. Кодировка текста
От общего описания кодирования перейдем к практической части.Из условных обозначений примем за константу то, что мы будем кодировать данные для персонального компьютера, где за единицу информации принимается бит и байт. Бит подобен атому информации, а байт — условному блоку размером в 8 бит. Текст в компьютере представляет собой часть из 256 символов, на каждый отводится один байт и в качестве кода могут использоваться значения от 0 до 255. Поскольку данные в ПК представлены в двоичной системе счисления, один байт (со значением ноль) равен записи 00000000, а 255 — как 11111111. Это числовое представление читается справа налево, то есть будет записываться единица.
как 00000001. Итак, в английском алфавите 26 символов верхнего регистра и 26 строчных, 10 цифр.
Также присутствуют знаки препинания и другие символы, но для экспериментов мы будем использовать только заглавные буквы (заглавные) и пробел.
Тестовая фраза «ГРЕК ЕЗД ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕКЕ РАК РУКУ ГРЕКА В РЕКУ ДАК ПОЛОЖИЛ РУКУ ГРЕКА В РЕКУ РАК».
2.1 Блочное кодирование
Информация в ПК уже представлена в виде 8-битных блоков, но зная контекст, мы попробуем представить ее в виде блоков меньшего размера.Для этого нам необходимо собрать информацию о представленных символах и на будущее сразу посчитать частоту использования каждого символа:
| Символ | Количество |
|---|---|
| КОСМОС | 18 |
| р | 12 |
| К | 11 |
| ? | 11 |
| ты | 9 |
| А | 8 |
| г | 4 |
| В | 3 |
| ЧАС | 2 |
| л | 2 |
| И | 2 |
| З | 2 |
| Д | 1 |
| Икс | 1 |
| С | 1 |
| Т | 1 |
| С | 1 |
| Н | 1 |
| п | 1 |
Для хранения в памяти ПК 18+12+11+11+9+8+4+3+2+2+2+2+1+1+1+1+1+1+1=91 байт (91* 8 =728 бит).
Мы принимаем эти значения как константы и пытаемся изменить подход к хранению блоков.
Для этого мы замечаем, что из 256 кодов символов мы используем только 19. Чтобы узнать, сколько бит нужно для хранения 19 значений, мы должны вычислить LOG 2 (19) = 4,25, так как мы не можем использовать дробное значение бита, мы должны округлить до 5, что дает нам максимум 32 различных значения (если бы мы хотели использовать 4 бита, это дало бы только 16 значений и мы не смогли бы закодировать всю строку).
Нетрудно подсчитать, что мы получим 91*5=455 бит, то есть зная контекст и изменив способ хранения, мы смогли сократить использование памяти ПК на 37,5%.
К сожалению, такое представление информации не позволит ее однозначно декодировать без сохранения информации о символах и новых кодах, а добавление нового словаря приведет к увеличению размера данных.
Поэтому такие методы кодирования проявляются на больших объемах данных.
Кроме того, для хранения 19 значений мы использовали то же количество бит, что и 32 значения, что снижает эффективность кодирования.
2.2 Коды переменной длины
Давайте воспользуемся той же строкой и таблицей и попробуем закодировать данные по-другому.Давайте удалим блоки фиксированного размера и представим данные в зависимости от частоты их использования — чем чаще используются данные, тем меньше битов мы будем использовать.
Мы получим вторую таблицу:
| Символ | Количество | Код переменной, бит |
|---|---|---|
| КОСМОС | 18 | 0 |
| р | 12 | 1 |
| К | 11 | 00 |
| ? | 11 | 01 |
| ты | 9 | 10 |
| А | 8 | 11 |
| г | 4 | 000 |
| В | 3 | 001 |
| ЧАС | 2 | 010 |
| л | 2 | 011 |
| И | 2 | 100 |
| З | 2 | 101 |
| Д | 1 | 110 |
| Икс | 1 | 111 |
| С | 1 | 0000 |
| Т | 1 | 0001 |
| С | 1 | 0010 |
| Н | 1 | 0011 |
| п | 1 | 0100 |
В такой ситуации мы не сможем определить, что означает код «111»; это может быть «PPR», «RA», «AP» или «X».
2.3 Префиксные блочные коды
Для решения задачи предыдущего примера нам необходимо использовать префиксные коды — это код, который при чтении можно однозначно декодировать в нужный символ, поскольку он есть только у него.Помните, ранее мы говорили об азбуке Морзе и в префиксе была пауза.
И теперь нам нужно ввести в оборот некий код, который будет определять начало и/или конец конкретного значения кода.
Давайте создадим третью таблицу для той же строки:
| Символ | Количество | Префиксный код с переменными блоками, биты |
|---|---|---|
| КОСМОС | 18 | 0 000 |
| р | 12 | 0 001 |
| К | 11 | 0 010 |
| ? | 11 | 0 011 |
| ты | 9 | 0 100 |
| А | 8 | 0 101 |
| г | 4 | 0 110 |
| В | 3 | 0 111 |
| ЧАС | 2 | 1 0001 |
| л | 2 | 1 0010 |
| И | 2 | 1 0011 |
| З | 2 | 1 0100 |
| Д | 1 | 1 0101 |
| Икс | 1 | 1 0110 |
| С | 1 | 1 0111 |
| Т | 1 | 1 1000 |
| С | 1 | 1 1001 |
| Н | 1 | 1 1010 |
| п | 1 | 1 1011 |
| Символ | Количество | Префиксный код с переменными блоками, биты |
|---|---|---|
| КОСМОС | 18 | 00 0 |
| р | 12 | 00 1 |
| К | 11 | 01 00 |
| ? | 11 | 01 01 |
| ты | 9 | 01 10 |
| А | 8 | 01 11 |
| г | 4 | 10 000 |
| В | 3 | 10 001 |
| ЧАС | 2 | 10 010 |
| л | 2 | 10 011 |
| И | 2 | 10 100 |
| З | 2 | 10 101 |
| Д | 1 | 10 110 |
| Икс | 1 | 10 111 |
| С | 1 | 11 000 |
| Т | 1 | 11 001 |
| С | 1 | 11 010 |
| Н | 1 | 11 011 |
| п | 1 | 11 100 |
Вычисляем размер строки — 356 бит. В результате в трех модификациях одного метода мы регулярно уменьшаем размер строки с 455 до 379, а затем и до 356 бит.
2.4 Код Хаффмана
Один из самых популярных способов построения префиксных кодов.При определенных условиях он позволяет получить оптимальный код для любых данных, хотя и допускает свободную модификацию методов создания кодов.
Этот код гарантирует, что для каждого символа существует только одна уникальная последовательность битовых значений.
В этом случае часто встречающимся символам будут присвоены короткие коды.
| Символ | Количество | Код |
|---|---|---|
| КОСМОС | 18 | 00 |
| р | 12 | 101 |
| К | 11 | 100 |
| ? | 11 | 011 |
| ты | 9 | 010 |
| А | 8 | 1111 |
| г | 4 | 11011 |
| В | 3 | 11001 |
| ЧАС | 2 | 111011 |
| л | 2 | 111010 |
| И | 2 | 111001 |
| З | 2 | 111000 |
| Д | 1 | 1101011 |
| Икс | 1 | 1101010 |
| С | 1 | 1101001 |
| Т | 1 | 1101000 |
| С | 1 | 1100011 |
| Н | 1 | 1100010 |
| п | 1 | 110000 |
2.5.1 Строки и подстроки
До сих пор мы кодировали данные, рассматривая их как набор отдельных символов.Теперь попробуем закодировать целые слова.
Напомню нашу строчку: «ГРЕК ПРОЕЗДАЛ ЧЕРЕЗ РЕКУ, ВИДИТ ГРЕКА В РЕКЕ РАК РУКИ ГРЕКА ДАКА ВЛОЖИЛ РУКУ ГРЕКА В РЕКУ РАК».
Составим таблицу повторов слов:
| Слово | Количество |
|---|---|
| КОСМОС | 18 |
| ГРЕЧЕСКИЙ | 3 |
| В | 2 |
| РАК | 2 |
| РЕКА | 2 |
| РУКА | 2 |
| ВИДИТ | 1 |
| ГРЕЧЕСКИЙ | 1 |
| УПРАВЛЯЕМЫЙ | 1 |
| ПОЗАДИ | 1 |
| РЕКА | 1 |
| СУНУЛ | 1 |
| ЦАП | 1 |
| ЧЕРЕЗ | 1 |
Сначала создадим словарь:
| Слово | Количество | Индекс |
|---|---|---|
| ГРЕЧЕСКИЙ | 3 | 0 |
| В | 2 | 1 |
| РАК | 2 | 2 |
| РЕКА | 2 | 3 |
| РУКА | 2 | 4 |
| ВИДИТ | 1 | 5 |
| ГРЕЧЕСКИЙ | 1 | 6 |
| УПРАВЛЯЕМЫЙ | 1 | 7 |
| ПОЗАДИ | 1 | 8 |
| РЕКА | 1 | 9 |
| СУНУЛ | 1 | 10 |
| ЦАП | 1 | 11 |
| ЧЕРЕЗ | 1 | 12 |
Мы пока останемся в рамках уже известных нам методов и начнем с блочного кодирования.
Индексы запишем в виде блоков по 4 бита (так можно представлять индексы от 0 до 15), таких цепочек у нас будет две, одна для закодированного сообщения, а вторая для сопоставления индекса и слова.
Сами слова будем кодировать кодами Хаффмана, только нам еще придется в словаре задать разделитель записей, можно например указать длину слова в блоке, самое длинное слово у нас 5 символов, 3 бит для этого достаточно, но мы можем использовать и пространственный код, состоящий из двух битов – этим мы и займемся.
В результате получаем схему хранения словаря:
| Индекс/биты | Слово/биты | Конец слова/битов |
|---|---|---|
| 0 / 4 | ГРЕКА / 18 | ПРОБЕЛ / 2 |
| 1 / 4 | В 5 | ПРОБЕЛ / 2 |
| 2 / 4 | РАК / 10 | ПРОБЕЛ / 2 |
| 3 / 4 | РЕКА / 12 | ПРОБЕЛ / 2 |
| 4 / 4 | АРМ / 12 | ПРОБЕЛ / 2 |
| 5 / 4 | ВИДИТ / 31 | ПРОБЕЛ / 2 |
| 6 / 4 | ГРЕКУ / 17 | ПРОБЕЛ / 2 |
| 7 / 4 | УПРАВЛЕННЫЙ / 20 | ПРОБЕЛ / 2 |
| 8 / 4 | ЗА/10 | ПРОБЕЛ / 2 |
| 9 / 4 | РЕКА / 18 | ПРОБЕЛ / 2 |
| 10 / 4 | СУНУЛ / 26 | ПРОБЕЛ / 2 |
| 11 / 4 | ЦСР/17 | ПРОБЕЛ / 2 |
| 12 / 4 | ВИА/21 | ПРОБЕЛ / 2 |
| 7 | 0 | 12 | 3 | 5 | 0 | 1 | 9 | 2 | 10 | 0 | 4 | 1 | 3 | 2 | 8 | 4 | 6 | 11 |
Послесловие
Надеюсь, статья даст вам общее представление о кодировании и покажет, что это не только военный криптограф или сложный алгоритм для математических гениев.Время от времени я сталкиваюсь с тем, как студенты пытаются решить задачи по кодированию и просто не могут абстрагироваться или подойти к этому процессу творчески.
Но кодирование похоже на прическу или модные брюки, которые таким образом показывают наш социальный код. УПД: Поскольку редактор Хабра уничтожил написанную вторую часть, а администрация на мое обращение не отреагировала, то продолжение (написанное еще в январе) скорее всего никогда не увидит свет (две недели непрерывной работы).
У меня нет стимула снова писать, считать таблицы, писать программы для проверки и скриншоты, как нет у меня и желания писать что-то на ресурсе, где несогласные с «линией партии» получают негативную карму.
Теги: #Алгоритмы #Занимательные задачи #Сжатие данных #кодирование #хаффман #биты.
бинарная система
-
Новая Форма Оплаты Покупок Rbk Money
19 Oct, 24 -
Сколько Стоит Iphone Для Людей?
19 Oct, 24 -
Развитие Предметного Мышления У Учащихся
19 Oct, 24 -
Живые Мертвецы
19 Oct, 24 -
Icq/Mrim/Jabber/Вконтакте Шлюз
19 Oct, 24
