Задача

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

Самое простое решение — использовать фиксированное число битов для каж- дого символа в алфавите, а затем просто объединить цепочки битов для каждого символа. Рассмотрим простой пример: допустим, мы хотим закодировать 26 букв английского языка, а также пробел (для разделения слов) и пять знаков препи- нания: запятую, точку, вопросительный знак, восклицательный знак и апостроф. Таким образом, закодировать нужно 32 символа. Из b битов можно сформировать 2b разных последовательностей, поэтому при использовании 5 битов на символ можно закодировать 25 = 32 символа — вполне достаточно для наших целей. Например, цепочка битов 00000 будет представлять букву «a», цепочка 00001 — букву «b», и т. д. вплоть до цепочки 11111, которая представляет апостроф. Следует учитывать, что соответствие битовых цепочек и символов выбирается произвольно; суть в том, что пяти битов на символ достаточно. Такие схемы ко- дирования, как ASCII, работают именно так, не считая того, что они используют больше количество битов на символ для поддержки наборов с большим количе- ством символов, включая буквы верхнего регистра, скобки и все специальные символы, которые вы видите на клавиатуре пишущей машинки или компьютера.

Вернемся к простейшему примеру с 32 символами. Какие еще требования могут предъявляться к схеме кодирования? Ограничиться 4 битами на символ не удастся, потому что 24 = 16 — недостаточно для имеющегося количества символов.

С другой стороны, неочевидно, что в больших объемах текста код одного символа в среднем должен состоять из 5 битов. Если задуматься, буквы большинства алфавитов ис- пользуются с разной частотой. Скажем, в английском языке буквы e, t, a, o, i и n используются намного чаще букв q, j, x и z (более чем на порядок). Получается, что кодировать их одинаковым количеством битов крайне расточительно; разумнее было бы использовать малое количество битов для часто встречающихся букв, а большее количество битов для редких букв и надеяться на то, что в длинных блоках типичного текста для представления одной буквы в среднем будет исполь- зоваться менее 5 бит.

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача
  15. 3. Задачи и функции социологии
  16. Основные задачи МПП.
  17. Задачи и упражнения
  18. Задачи
  19. Трудная задача