[Занимательные задачки, Алгоритмы, Сжатие данных] Кодирование для чайников, ч.1
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Не являясь специалистом в обозначенной области я, тем не менее, прочитал много специализированной литературы для знакомства с предметом и прорываясь через тернии к звёздам набил, на начальных этапах, немало шишек. При всём изобилии информации мне не удалось найти простые статьи о кодировании как таковом, вне рамок специальной литературы (так сказать без формул и с картинками).Статья, в первой части, является ликбезом по кодированию как таковому с примерами манипуляций с битовыми кодами, а во второй я бы хотел затронуть простейшие способы кодирования изображений.0. НачалоПоскольку я обращаюсь к новичкам в этом вопросе, то не посчитаю зазорным обратиться к Википедии. А там для обозначения кодирования информации у нас есть такое определение - процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической переработки.Чего мне не хватало в 70-80-е, так это в школе, пусть не на информатике, а, например, на уроках математики - базовой информации по кодированию. Дело в том, что кодированием информации каждый из нас занимается ежесекундно, постоянно и в целом - не концентрируясь на самом кодировании. То есть в быту мы это делаем постоянно. Так как это происходит?Мимика, жесты, речь, сигналы разного уровня - табличка с надписью, знак на дороге, светофоры, и для современного мира - штрих- и бар-коды, URL, хэш-тэги.Давайте рассмотрим некоторые более подробно.1.1 Речь, мимика, жестыУдивительно, но всё это - коды. С помощью них мы передаём информацию о своих действиях, ощущениях, эмоциях. Самое важное, чтобы коды были понятны всем. Например, родившись в густых лесах у Амазонки и не видя современного городского человека, можно столкнуться с проблемой непонимания кода - улыбка, как демонстрация зубов, будет воспринята как угроза, а не как выражение радости.Следуя определению, что же происходит когда мы говорим? Мысль - как форма, удобная для непосредственного использования, преобразуется в речь - форму удобную для передачи. И, смотрите, так как у звука есть ограничение как на скорость, так и на дальность передачи, то, например, жест, в какой-то ситуации, может быть выбран для передачи той же информации, но на большее расстояние. Но мы всё еще будем ограничены дальностью остроты нашего зрения и тогда человек начинает придумывать другие способы передачи и преобразования информации, например огонь или дым.1.2 Чередующиеся сигналы
Индеец пингуетВ примитивном виде кодирование чередующимися сигналами используется человечеством очень давно. В предыдущем разделе мы сказали про дым и огонь. Если между наблюдателем и источником огня ставить и убирать препятствие, то наблюдателю будет казаться, что он видит чередующиеся сигналы "включено/выключено". Меняя частоту таких включений мы можем выработать последовательность кодов, которая будет однозначно трактоваться принимающей стороной.Наряду с сигнальными флажками на морских и речных судах, при появлении радио начали использовать код Морзе. И при всей кажущейся бинарности (представление кода двумя значениями), так как используются сигналы точка и тире, на самом деле это тернаный код, так как для разделения отдельных кодов-символов требуется пауза в передаче кода. То есть код Морзе кроме "точка-тире", что нам даёт букву "A" может звучать и так - "точка-пауза-тире" и тогда это уже две буквы "ET".
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Всего нами использовано 19 символов (включая пробел). Для хранения в памяти ПК будет затрачено 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 значений мы должны посчитать LOG2(19)=4.25, так как дробное значение бита мы использовать не можем, то мы должны округлить до 5, что нам даёт максимально 32 разных значения (если бы мы захотели использовать 4 бита, то это дало бы лишь 16 значений и мы не смогли бы закодировать всю строку).Нетрудно посчитать, что у нас получится 91*5=455 бит, то есть зная контекст и изменив способ хранения мы смогли уменьшить использование памяти ПК на 37.5%.К сожалению такое представление информации не позволит его однозначно декодировать без хранения информации о символах и новых кодах, а добавление нового словаря увеличит размер данных. Поэтому подобные способы кодирования проявляют себя на бОльших объемах данных.Кроме того, для хранения 19 значений мы использовали количество бит для 32 значений, это снижает эффективность кодирования.2.2 Коды переменной длиныВоспользуемся той же строкой и таблицей и попробуем данные закодировать иначе. Уберём блоки фиксированного размера и представим данные исходя из их частоты использования - чем чаще данные используются, чем меньше бит мы будем использовать. У нас получится вторая таблица:СимволКоличествоПеременный код, битПРОБЕЛ180Р121К1100Е1101У910А811Г4000В3001Ч2010Л2011И2100З2101Д1110Х1111С10000Т10001Ц10010Н10011П10100Для подсчёта длины закодированного сообщения мы должны сложить все произведения количества символов на длины кодов в битах и тогда получим 179 бит.Но такой способ, хоть и позволил прилично сэкономить память, но не будет работать, потому что невозможно его раскодировать. Мы не сможем определить в такой ситуации что означает код "111", это может быть "РРР", "РА", "АР" или "Х".2.3 Префиксные блочные коды Для решения проблемы предыдущего примера нам нужно использовать префиксные коды - это такой код, который при чтении можно однозначно раскодировать в нужный символ, так как он есть только у него. Помните ранее мы говорили про азбуку Морзе и там префиксом была пауза. Вот и сейчас нам нужно ввести в обращение какой-то код, который будет определять начало и/или конец конкретного значения кода.Составим третью таблицу всё для той же строки:СимволКоличествоПрефиксный код с переменными блоками, битПРОБЕЛ180000Р120001К110010Е110011У90100А80101Г40110В30111Ч210001Л210010И210011З210100Д110101Х110110С110111Т111000Ц111001Н111010П111011Особенность новых кодов в том, что первый бит мы используем для указания размера следующего за ним блока, где 0 - бок три бита, 1 - блок четыре бита. Нетрудно посчитать, что такой подход закодирует нашу строку в 379 бит. Ранее при блочном кодировании у нас получился результат в 455 бит.Можно развить этот подход и префикс увеличить до 2 бит, что позволит нам создать 4 группы блоков:СимволКоличествоПрефиксный код с переменными блоками, битПРОБЕЛ18000Р12001К110100Е110101У90110А80111Г410000В310001Ч210010Л210011И210100З210101Д110110Х110111С111000Т111001Ц111010Н111011П111100Где 00 - блок в 1 бит, 01 - 2 бита, 10 и 11 - 3 бита. Подсчитываем размер строки - 356 бит.В итоге за три модификации одного способа мы регулярно уменьшаем размер строки, от 455 до 379, а затем до 356 бит.2.4 Код ХаффманаОдин из популярнейших способов построения префиксных кодов. При соблюдении определенных условий позволяет получить оптимальный код для любых данных, хотя и допускает вольные модификации создания кодов.Такой код гарантирует, что для каждого символа есть только одна уникальная последовательность значений битов. При этом частым символам будут назначены короткие коды.СимволКоличествоКодПРОБЕЛ1800Р12101К11100Е11011У9010А81111Г411011В311001Ч2111011Л2111010И2111001З2111000Д11101011Х11101010С11101001Т11101000Ц11100011Н11100010П1110000Считаем результат - 328 бит.Заметьте, хоть мы и стали использовать коды в 6 и 7 бит, но их слишком мало, чтобы повлиять на исход.2.5.1 Строки и подстрокиДо сих пор мы кодировали данные, рассматривая их как совокупность отдельных символов. Сейчас мы попробуем кодировать целыми словами.Напомню нашу строку: "ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП".Составим таблицу повторов слов:СловоКоличествоПРОБЕЛ18ГРЕКА3В2РАК2РЕКУ2РУКУ2ВИДИТ1ГРЕКУ1ЕХАЛ1ЗА1РЕЧКЕ1СУНУЛ1ЦАП1ЧЕРЕЗ1Для кодирования нам нужно придумать концепцию, например - мы создаём словарь и каждому слову присваиваем индекс, пробелы игнорируем и не кодируем, но считаем, что каждое слово разделяется именно символом пробела.Сначала формируем словарь:СловоКоличествоИндексГРЕКА30В21РАК22РЕКУ23РУКУ24ВИДИТ15ГРЕКУ16ЕХАЛ17ЗА18РЕЧКЕ19СУНУЛ110ЦАП111ЧЕРЕЗ112Таким образом наша строка кодируется в последовательность:7, 0, 12, 3, 5, 0, 1, 9, 2, 10, 0, 4, 1, 3, 2, 8, 4, 6, 11Это подготовительный этап, а вот то, как именно нам кодировать словарь и данные уже после подготовительного кодирования - процесс творческий. Мы пока останемся в рамках уже известных нам способов и начнём с блочного кодирования.Индексы записываем в виде блоков по 4 бита (так можно представить индексы от 0 до 15), таких цепочек у нас будет две, одна для закодированного сообщения, а вторая для соответствия индексу и слову. Сами слова будем кодировать кодами Хаффмана, только нам еще придется задать разделитесь записей в словаре, можно, например, указывать длину слова блоком, самое длинное слово у нас в 5 символов, для этого хватит 3 бита, но так же мы можем использовать код пробела, который состоит из двух бит - так и поступим. В итоге мы получаем схему хранения словаря:Индекс / битыСлово / битыКонец слова / биты0 / 4ГРЕКА / 18ПРОБЕЛ / 21 / 4В / 5ПРОБЕЛ / 22 / 4РАК / 10ПРОБЕЛ / 23 / 4РЕКУ / 12ПРОБЕЛ / 24 / 4РУКУ / 12ПРОБЕЛ / 25 / 4ВИДИТ / 31ПРОБЕЛ / 26 / 4ГРЕКУ / 17ПРОБЕЛ / 27 / 4ЕХАЛ / 20ПРОБЕЛ / 28 / 4ЗА / 10ПРОБЕЛ / 29 / 4РЕЧКЕ / 18ПРОБЕЛ / 210 / 4СУНУЛ / 26ПРОБЕЛ / 211 / 4ЦАП / 17ПРОБЕЛ / 212 / 4ЧЕРЕЗ / 21ПРОБЕЛ / 27012350192100413284611и само сообщение по 4 бита на код.Считаем всё вместе и получаем 371 бит. При этом само сообщение у нас было закодировано в 19*4=76 бит. Но нам всё еще требуется сохранять соответствие кода Хаффмана и символа, как и во всех предыдущих случаях.ПослесловиеНадеюсь статья позволит составить общее впечатление о кодировании и покажет, что это не только военный-шифровальщик или сложный алгоритм для математических гениев.Периодически сталкиваюсь с тем, как студенты пытаются решить задачи кодирования и просто не могут абстрагироваться, подойти творчески к этому процессу. А ведь кодирование, это как причёска или модные штаны, которые таким образом показывают наш социальный код.
===========
Источник:
habr.com
===========
Похожие новости:
- [Data Mining, Алгоритмы, Математика, Научно-популярное] Звездный год (365 дней 369 минут), Тропический год(+ 348.5 минут) и звездные сутки(1436 минут) в радиоактивном распаде
- [Python, Программирование, Data Mining, Алгоритмы, Машинное обучение] ИИ итоги уходящего 2020-го года в мире машинного обучения
- [Алгоритмы, Математика, DIY или Сделай сам] Математически оптимальные рождественские печеньки (перевод)
- [Алгоритмы, Математика] Рекурсивный алгоритм представления Цекендорфа
- [Занимательные задачки, Программирование, Алгоритмы, Компиляторы] Чемпионат по выполнению теста Кнута
- [Программирование, Алгоритмы, Компиляторы, Софт] О реализации точного представления чисел или «где хранить деньги?»
- [Занимательные задачки, R, Визуализация данных, Инфографика] Моя музыка 2020 года в картинках и графиках
- [Терминология IT, Учебный процесс в IT, Образование за рубежом, Карьера в IT-индустрии] Наше ИТ и их Computer Science
- [Open source, Алгоритмы, Lua, Параллельное программирование] Такие важные короткоживущие данные
- [Алгоритмы, Обработка изображений, Машинное обучение] Эксперимент в распознавании рукописных текстов на кириллице. Часть 2
Теги для поиска: #_zanimatelnye_zadachki (Занимательные задачки), #_algoritmy (Алгоритмы), #_szhatie_dannyh (Сжатие данных), #_huffman, #_kodirovanie (кодирование), #_algoritmy (алгоритмы), #_bity._dvoichnaja_sistema (биты. двоичная система), #_zanimatelnye_zadachki (
Занимательные задачки
), #_algoritmy (
Алгоритмы
), #_szhatie_dannyh (
Сжатие данных
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 21:19
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
|
Не являясь специалистом в обозначенной области я, тем не менее, прочитал много специализированной литературы для знакомства с предметом и прорываясь через тернии к звёздам набил, на начальных этапах, немало шишек. При всём изобилии информации мне не удалось найти простые статьи о кодировании как таковом, вне рамок специальной литературы (так сказать без формул и с картинками).Статья, в первой части, является ликбезом по кодированию как таковому с примерами манипуляций с битовыми кодами, а во второй я бы хотел затронуть простейшие способы кодирования изображений.0. НачалоПоскольку я обращаюсь к новичкам в этом вопросе, то не посчитаю зазорным обратиться к Википедии. А там для обозначения кодирования информации у нас есть такое определение - процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической переработки.Чего мне не хватало в 70-80-е, так это в школе, пусть не на информатике, а, например, на уроках математики - базовой информации по кодированию. Дело в том, что кодированием информации каждый из нас занимается ежесекундно, постоянно и в целом - не концентрируясь на самом кодировании. То есть в быту мы это делаем постоянно. Так как это происходит?Мимика, жесты, речь, сигналы разного уровня - табличка с надписью, знак на дороге, светофоры, и для современного мира - штрих- и бар-коды, URL, хэш-тэги.Давайте рассмотрим некоторые более подробно.1.1 Речь, мимика, жестыУдивительно, но всё это - коды. С помощью них мы передаём информацию о своих действиях, ощущениях, эмоциях. Самое важное, чтобы коды были понятны всем. Например, родившись в густых лесах у Амазонки и не видя современного городского человека, можно столкнуться с проблемой непонимания кода - улыбка, как демонстрация зубов, будет воспринята как угроза, а не как выражение радости.Следуя определению, что же происходит когда мы говорим? Мысль - как форма, удобная для непосредственного использования, преобразуется в речь - форму удобную для передачи. И, смотрите, так как у звука есть ограничение как на скорость, так и на дальность передачи, то, например, жест, в какой-то ситуации, может быть выбран для передачи той же информации, но на большее расстояние. Но мы всё еще будем ограничены дальностью остроты нашего зрения и тогда человек начинает придумывать другие способы передачи и преобразования информации, например огонь или дым.1.2 Чередующиеся сигналы  Индеец пингуетВ примитивном виде кодирование чередующимися сигналами используется человечеством очень давно. В предыдущем разделе мы сказали про дым и огонь. Если между наблюдателем и источником огня ставить и убирать препятствие, то наблюдателю будет казаться, что он видит чередующиеся сигналы "включено/выключено". Меняя частоту таких включений мы можем выработать последовательность кодов, которая будет однозначно трактоваться принимающей стороной.Наряду с сигнальными флажками на морских и речных судах, при появлении радио начали использовать код Морзе. И при всей кажущейся бинарности (представление кода двумя значениями), так как используются сигналы точка и тире, на самом деле это тернаный код, так как для разделения отдельных кодов-символов требуется пауза в передаче кода. То есть код Морзе кроме "точка-тире", что нам даёт букву "A" может звучать и так - "точка-пауза-тире" и тогда это уже две буквы "ET".  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Всего нами использовано 19 символов (включая пробел). Для хранения в памяти ПК будет затрачено 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 значений мы должны посчитать LOG2(19)=4.25, так как дробное значение бита мы использовать не можем, то мы должны округлить до 5, что нам даёт максимально 32 разных значения (если бы мы захотели использовать 4 бита, то это дало бы лишь 16 значений и мы не смогли бы закодировать всю строку).Нетрудно посчитать, что у нас получится 91*5=455 бит, то есть зная контекст и изменив способ хранения мы смогли уменьшить использование памяти ПК на 37.5%.К сожалению такое представление информации не позволит его однозначно декодировать без хранения информации о символах и новых кодах, а добавление нового словаря увеличит размер данных. Поэтому подобные способы кодирования проявляют себя на бОльших объемах данных.Кроме того, для хранения 19 значений мы использовали количество бит для 32 значений, это снижает эффективность кодирования.2.2 Коды переменной длиныВоспользуемся той же строкой и таблицей и попробуем данные закодировать иначе. Уберём блоки фиксированного размера и представим данные исходя из их частоты использования - чем чаще данные используются, чем меньше бит мы будем использовать. У нас получится вторая таблица:СимволКоличествоПеременный код, битПРОБЕЛ180Р121К1100Е1101У910А811Г4000В3001Ч2010Л2011И2100З2101Д1110Х1111С10000Т10001Ц10010Н10011П10100Для подсчёта длины закодированного сообщения мы должны сложить все произведения количества символов на длины кодов в битах и тогда получим 179 бит.Но такой способ, хоть и позволил прилично сэкономить память, но не будет работать, потому что невозможно его раскодировать. Мы не сможем определить в такой ситуации что означает код "111", это может быть "РРР", "РА", "АР" или "Х".2.3 Префиксные блочные коды Для решения проблемы предыдущего примера нам нужно использовать префиксные коды - это такой код, который при чтении можно однозначно раскодировать в нужный символ, так как он есть только у него. Помните ранее мы говорили про азбуку Морзе и там префиксом была пауза. Вот и сейчас нам нужно ввести в обращение какой-то код, который будет определять начало и/или конец конкретного значения кода.Составим третью таблицу всё для той же строки:СимволКоличествоПрефиксный код с переменными блоками, битПРОБЕЛ180000Р120001К110010Е110011У90100А80101Г40110В30111Ч210001Л210010И210011З210100Д110101Х110110С110111Т111000Ц111001Н111010П111011Особенность новых кодов в том, что первый бит мы используем для указания размера следующего за ним блока, где 0 - бок три бита, 1 - блок четыре бита. Нетрудно посчитать, что такой подход закодирует нашу строку в 379 бит. Ранее при блочном кодировании у нас получился результат в 455 бит.Можно развить этот подход и префикс увеличить до 2 бит, что позволит нам создать 4 группы блоков:СимволКоличествоПрефиксный код с переменными блоками, битПРОБЕЛ18000Р12001К110100Е110101У90110А80111Г410000В310001Ч210010Л210011И210100З210101Д110110Х110111С111000Т111001Ц111010Н111011П111100Где 00 - блок в 1 бит, 01 - 2 бита, 10 и 11 - 3 бита. Подсчитываем размер строки - 356 бит.В итоге за три модификации одного способа мы регулярно уменьшаем размер строки, от 455 до 379, а затем до 356 бит.2.4 Код ХаффманаОдин из популярнейших способов построения префиксных кодов. При соблюдении определенных условий позволяет получить оптимальный код для любых данных, хотя и допускает вольные модификации создания кодов.Такой код гарантирует, что для каждого символа есть только одна уникальная последовательность значений битов. При этом частым символам будут назначены короткие коды.СимволКоличествоКодПРОБЕЛ1800Р12101К11100Е11011У9010А81111Г411011В311001Ч2111011Л2111010И2111001З2111000Д11101011Х11101010С11101001Т11101000Ц11100011Н11100010П1110000Считаем результат - 328 бит.Заметьте, хоть мы и стали использовать коды в 6 и 7 бит, но их слишком мало, чтобы повлиять на исход.2.5.1 Строки и подстрокиДо сих пор мы кодировали данные, рассматривая их как совокупность отдельных символов. Сейчас мы попробуем кодировать целыми словами.Напомню нашу строку: "ЕХАЛ ГРЕКА ЧЕРЕЗ РЕКУ ВИДИТ ГРЕКА В РЕЧКЕ РАК СУНУЛ ГРЕКА РУКУ В РЕКУ РАК ЗА РУКУ ГРЕКУ ЦАП".Составим таблицу повторов слов:СловоКоличествоПРОБЕЛ18ГРЕКА3В2РАК2РЕКУ2РУКУ2ВИДИТ1ГРЕКУ1ЕХАЛ1ЗА1РЕЧКЕ1СУНУЛ1ЦАП1ЧЕРЕЗ1Для кодирования нам нужно придумать концепцию, например - мы создаём словарь и каждому слову присваиваем индекс, пробелы игнорируем и не кодируем, но считаем, что каждое слово разделяется именно символом пробела.Сначала формируем словарь:СловоКоличествоИндексГРЕКА30В21РАК22РЕКУ23РУКУ24ВИДИТ15ГРЕКУ16ЕХАЛ17ЗА18РЕЧКЕ19СУНУЛ110ЦАП111ЧЕРЕЗ112Таким образом наша строка кодируется в последовательность:7, 0, 12, 3, 5, 0, 1, 9, 2, 10, 0, 4, 1, 3, 2, 8, 4, 6, 11Это подготовительный этап, а вот то, как именно нам кодировать словарь и данные уже после подготовительного кодирования - процесс творческий. Мы пока останемся в рамках уже известных нам способов и начнём с блочного кодирования.Индексы записываем в виде блоков по 4 бита (так можно представить индексы от 0 до 15), таких цепочек у нас будет две, одна для закодированного сообщения, а вторая для соответствия индексу и слову. Сами слова будем кодировать кодами Хаффмана, только нам еще придется задать разделитесь записей в словаре, можно, например, указывать длину слова блоком, самое длинное слово у нас в 5 символов, для этого хватит 3 бита, но так же мы можем использовать код пробела, который состоит из двух бит - так и поступим. В итоге мы получаем схему хранения словаря:Индекс / битыСлово / битыКонец слова / биты0 / 4ГРЕКА / 18ПРОБЕЛ / 21 / 4В / 5ПРОБЕЛ / 22 / 4РАК / 10ПРОБЕЛ / 23 / 4РЕКУ / 12ПРОБЕЛ / 24 / 4РУКУ / 12ПРОБЕЛ / 25 / 4ВИДИТ / 31ПРОБЕЛ / 26 / 4ГРЕКУ / 17ПРОБЕЛ / 27 / 4ЕХАЛ / 20ПРОБЕЛ / 28 / 4ЗА / 10ПРОБЕЛ / 29 / 4РЕЧКЕ / 18ПРОБЕЛ / 210 / 4СУНУЛ / 26ПРОБЕЛ / 211 / 4ЦАП / 17ПРОБЕЛ / 212 / 4ЧЕРЕЗ / 21ПРОБЕЛ / 27012350192100413284611и само сообщение по 4 бита на код.Считаем всё вместе и получаем 371 бит. При этом само сообщение у нас было закодировано в 19*4=76 бит. Но нам всё еще требуется сохранять соответствие кода Хаффмана и символа, как и во всех предыдущих случаях.ПослесловиеНадеюсь статья позволит составить общее впечатление о кодировании и покажет, что это не только военный-шифровальщик или сложный алгоритм для математических гениев.Периодически сталкиваюсь с тем, как студенты пытаются решить задачи кодирования и просто не могут абстрагироваться, подойти творчески к этому процессу. А ведь кодирование, это как причёска или модные штаны, которые таким образом показывают наш социальный код. =========== Источник: habr.com =========== Похожие новости:
Занимательные задачки ), #_algoritmy ( Алгоритмы ), #_szhatie_dannyh ( Сжатие данных ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 21:19
Часовой пояс: UTC + 5