А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
11.5.2. Могут ли при этом остаться неотмеченные позиции и чему они соответствуют? Ответ. Это позиции, в которых оба игрока могут гарантировать сколь угодно длинную игру без проигрыша. Впрочем, правило тро- екратного повторения позиции в шахматах в этом случае позволяет считать партию ничейной. (На самом деле учёт этого правила суще- ственно осложняет ситуацию, поскольку теперь в понятие позиции на- до включать информацию о том, какие конфигурации фигур на доске уже встречались.) А. Л. Брудно заметил, что есть ситуация, в которой такой «ретро- спективный» анализ требует совсем небольших ресурсов и может быть реализован на очень небольшой памяти, хотя для человека соответству- ющая задача не проста: пусть белые имеют короля на поле c3, которого им запрещено двигать, и ферзя (на каком-то другом поле) и хотят по- ставить мат одинокому чёрному королю. Ограничение (неподвижность короля), затрудняющее жизнь человеку-шахматисту, облегчает анализ (уменьшая количество позиций почти что в 64 раза за счёт того, что не надо рассматривать разные положения короля!) 11.5. Ретроспективный анализ 229 Использование таблицы описанного типа можно считать примене- нием метода динамического программирования (мы не вычисляем цену игры для одной и той же позиции снова и снова, обходя дерево, а за- полняем таблицу цен систематически). 12. ОПТИМАЛЬНОЕ КОДИРОВАНИЕ 12.1. Коды Имея 2 𝑛 символов, мы можем кодировать каждый из них 𝑛 бита- ми, поскольку существует 2 𝑛 комбинаций из 𝑛 битов. Например, мож- но закодировать 4 = 2 2 символа А, Г, Т, Ц (используемые при запи- си геномов) двухбитовыми комбинациями 00, 01, 10 и 11. Другой при- мер: последовательностями из 8 битов (байтами) можно закодировать 256 символов (и этого хватает на латинские и русские буквы, знаки препинания и др.). Более формально: пусть нам дан алфавит, то есть конечное мно- жество, элементы которого называются символами или буквами этого алфавита. Кодом для алфавита 𝐴 называется функция (таблица) 𝛼, ко- торая для каждого символа 𝑎 из 𝐴 указывает двоичное слово 𝛼(𝑎), на- зываемое кодовым словом, или просто кодом этого символа. (Двоичное слово | конечная последовательность нулей и единиц.) Не требуется, чтобы коды всех символов имели равные длины. Мы допускаем, чтобы разные символы имели одинаковые коды. Со- гласно нашему определению, разрешается все буквы алфавита закоди- ровать словом 0 (и даже пустым словом) | но, конечно, такой код будет бесполезен. Хороший код должен позволять декодирование (восстано- вление последовательности символов по её коду). Формально это определяется так. Пусть фиксирован алфавит 𝐴 и код 𝛼 для этого алфавита. Для каждого слова 𝑃 в алфавите 𝐴 (то есть для любой конечной последовательности букв алфавита 𝐴) рассмотрим двоичное слово 𝛼(𝑃 ), которое получается, если записать подряд коды всех букв из 𝑃 (без каких-либо разделителей). Код 𝛼 называется одно- значным, если коды различных слов различны: 𝛼(𝑃 ) ̸= 𝛼(𝑃 ′ ) при 𝑃 ̸= 𝑃 ′ 12.1.1. Рассмотрим трёхбуквенный алфавит {𝑎, 𝑏, 𝑐} и код 𝛼(𝑎) = 0, 𝛼(𝑏) = 01 и 𝛼(𝑐) = 00. Будет ли этот код однозначным? 12.2. Неравенство Крафта { Макмиллана 231 Решение. Нет, поскольку слова 𝑎𝑎 и 𝑐 кодируются одинаково. 12.1.2. Для того же алфавита рассмотрим код 𝛼(𝑎) = 0, 𝛼(𝑏) = 10 и 𝛼(𝑐) = 11. Будет ли этот код однозначным? Решение. Будет. Чтобы доказать это, достаточно объяснить, как можно восстановить слово 𝑃 по его коду 𝛼(𝑃 ). Если 𝛼(𝑃 ) начинается с нуля, то ясно, что слово 𝑃 начинается с 𝑎. Если 𝛼(𝑃 ) начинается с единицы, то слово 𝑃 начинается с 𝑏 или с 𝑐 | чтобы узнать, с чего именно, достаточно посмотреть на второй бит слова 𝛼(𝑃 ). Восстановив первую букву слова 𝑃 , мы забываем о ней и о её коде, и продолжаем всё сначала. Верно и более общее утверждение. Назовём код префиксным, если коды букв не являются началами друг друга (слово 𝛼(𝑝) не является началом слова 𝛼(𝑞), если буквы 𝑝 и 𝑞 различны). 12.1.3. Докажите, что любой префиксный код является однознач- ным. Решение. Декодирование можно вести слева направо. Первая буква восстанавливается однозначно: если для двух букв 𝑝 и 𝑞 слова 𝛼(𝑝) и 𝛼(𝑞) являются началами кода, то одно из слов 𝛼(𝑝) и 𝛼(𝑞) является на- чалом другого, что невозможно для префиксного кода. И так далее. 12.1.4. Приведите пример однозначного кода, не являющегося пре- фиксным. [Указание. Пусть 𝛼(𝑎) = 0, 𝛼(𝑏) = 01, 𝛼(𝑐) = 11. Этот код является «суффиксным», но не префиксным.] 12.1.5. Найдите таблицу для азбуки Морзе. Объясните, почему её можно использовать на практике, хотя она не является ни префиксным, ни даже однозначным кодом. 12.2. Неравенство Крафта { Макмиллана Зачем вообще нужны коды с разной длиной кодовых слов? Дело в том, что на практике разные символы алфавита встречаются с разной частотой, и выгодно закодировать частые символы короткими слова- ми. (Это соображение, кстати, учитывалось при составлении азбуки Морзе.) Пусть для каждой буквы 𝑎 алфавита 𝐴 фиксирована её частота 𝑝(𝑎) | положительное число, причём суммы частот всех букв равны 232 12. Оптимальное кодирование единице. Тогда для любого кода 𝛼 можно определить среднюю длину этого кода как сумму 𝐸 = ∑︁ 𝑝(𝑎)|𝛼(𝑎)| по всем буквам 𝑎 ∈ 𝐴, где |𝛼(𝑎)| | длина кодового слова 𝛼(𝑎) буквы 𝑎. (Смысл этого определения: если в слове длины 𝑁 буква 𝑎 встречается с частотой 𝑝(𝑎), то таких букв будет 𝑁𝑝(𝑎) и на их кодирование уйдёт 𝑁𝑝(𝑎)|𝛼(𝑎)| битов; общая длина кода будет ∑︀ 𝑁𝑝(𝑎)|𝛼(𝑎)| и в среднем на кодирование каждой буквы уйдёт 𝐸 битов.) Теперь возникает задача: для данных частот построить однознач- ный код минимальной средней длины. Теоретически это можно сделать перебором (если в коде есть хотя бы одно очень длинное кодовое слово, то его средняя длина велика, поэтому такие коды можно не рассматри- вать; остаётся конечное число вариантов). Но можно обойтись и без перебора, и в этом разделе мы научимся это делать. Для начала поймём, что мешает нам выбирать кодовые слова корот- кими. Оказывается, что есть ровно одно препятствие: длины 𝑛 1 , . . . , 𝑛 𝑘 кодовых слов должны удовлетворять неравенству 2 − 𝑛 1 + 2 − 𝑛 2 + . . . + 2 − 𝑛 𝑘 6 1, называемому в теории кодирования неравенством Крафта { Макмил- лана. 12.2.1. Проверьте, что оно выполнено для рассмотренных выше примеров однозначных кодов. 12.2.2. Докажите, что для всякого префиксного кода выполняется неравенство Крафта { Макмиллана. Решение. Отрезок [0, 1] можно разбить на две половины. Назовём левую 𝐼 0 , а правую 𝐼 1 . Каждую из них разобьём пополам: отрезок 𝐼 0 разделится на левую половину 𝐼 00 и правую 𝐼 01 , аналогично 𝐼 1 делит- ся на 𝐼 10 и 𝐼 11 . И так далее: любому двоичному слову 𝑥 соответствует отрезок 𝐼 𝑥 . Длина этого отрезка есть 2 −| 𝑥| , где |𝑥| | длина слова 𝑥. Если слово 𝑥 является началом слова 𝑦, то отрезок 𝐼 𝑥 содержит отре- зок 𝐼 𝑦 ; если ни одно из слов 𝑥 и 𝑦 не является началом другого, то отрезки 𝐼 𝑥 и 𝐼 𝑦 не перекрываются (на том знаке, где 𝑥 и 𝑦 впервые расходятся, 𝐼 𝑥 и 𝐼 𝑦 попадают в разные половины). Рассмотрим теперь отрезки, соответствующие словам префиксно- го кода. Они не перекрываются. А значит, сумма их длин не больше единицы, что и даёт неравенство Крафта { Макмиллана. 12.2. Неравенство Крафта { Макмиллана 233 12.2.3. Пусть даны 𝑘 целых положительных чисел 𝑛 1 , . . . , 𝑛 𝑘 , удовле- творяющие неравенству Крафта { Макмиллана. Докажите, что можно построить префиксный код для 𝑘-буквенного алфавита с длинами ко- довых слов 𝑛 1 , . . . , 𝑛 𝑘 Решение. И здесь полезно использовать соответствие между слова- ми и отрезками и представлять себе дело так: у нас есть единичный отрезок [0, 1], и мы выделяем его части пользователям по требованию. Если пользователь приходит с числом 𝑛 𝑖 , то это значит, что ему надо выдать в пользование один из отрезков длиной 2 − 𝑛 𝑖 , соответствую- щих кодовым словам длины 𝑛 𝑖 . (Тем самым годятся не любые отрезки такой длины, а лишь «правильно расположенные».) Код должен быть префиксным, это значит, что отрезки разных пользователей не долж- ны перекрываться. Нам дано, что суммарная длина всех требований не больше единицы. Как их удовлетворить? Можно отводить место сле- ва направо, при этом рассматривать требования в порядке убывания длин (тогда более короткие отрезки будут правильно расположены по- сле предыдущих более длинных). 12.2.4. Покажите, что выделять кодовые слова (место на отрезке) можно и в порядке поступления требований (как иногда говорят, в «ре- жиме on-line»): пользователь приходит с числом 𝑛 𝑖 и уходит с правильно расположенным отрезком длины 2 − 𝑛 𝑖 , причём если выполнено неравен- ство Крафта { Макмиллана, то никто не уйдёт обиженным (всем хватит места, и перераспределять его не придётся). [Указание. Нужно поддерживать свободное пространство как объ- единение правильно расположенных отрезков попарно различных длин, выделяя каждому пользователю кусок из кратчайшего подходящего от- резка и доразбивая остаток.] 12.2.5. Покажите, что неравенство Крафта { Макмиллана выполня- ется не только для любого префиксного кода, но и вообще для любого однозначного кода. (Именно это доказал Макмиллан; Крафт доказал неравенство для префиксных кодов.) Решение. Есть разные способы решить эту задачу; мы приведём простое и красивое, хотя и несколько загадочное, решение. Пусть име- ется однозначный код с 𝑘 кодовыми словами 𝑃 1 , . . . , 𝑃 𝑘 . Нам надо дока- зать, что их длины 𝑛 𝑖 = |𝑃 𝑖 | удовлетворяют неравенству Крафта { Мак- миллана. Представим себе, что вместо нулей и единиц используются символы 𝑎 и 𝑏 (какая разница, из чего составлять коды?). Запишем 234 12. Оптимальное кодирование формально сумму всех кодовых слов как алгебраическое выражение 𝑃 1 + 𝑃 2 + . . . + 𝑃 𝑘 (многочлен от 𝑎 и 𝑏, в котором одночлены записаны как произведе- ния переменных 𝑎 и 𝑏, без возведения в степень). Теперь (ещё более странное на первый взгляд действие) возведём это выражение в сте- пень 𝑁 (произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных (не собирая вместе одинаковые переменные) в од- ночленах: (𝑃 1 + 𝑃 2 + . . . + 𝑃 𝑘 ) 𝑁 = сумма одночленов. Например, для кода со словами 0, 10, 11 (которые теперь записываются как 𝑎, 𝑏𝑎, 𝑏𝑏) и для 𝑁 = 2 получаем (𝑎 + 𝑏𝑎 + 𝑏𝑏) 2 = (𝑎 + 𝑏𝑎 + 𝑏𝑏)(𝑎 + 𝑏𝑎 + 𝑏𝑏) = = 𝑎𝑎 + 𝑎𝑏𝑎 + 𝑎𝑏𝑏 + 𝑏𝑎𝑎 + 𝑏𝑎𝑏𝑎 + 𝑏𝑎𝑏𝑏 + 𝑏𝑏𝑎 + 𝑏𝑏𝑏𝑎 + 𝑏𝑏𝑏𝑏. В этом примере все одночлены в правой части различны (если не пере- ставлять переменные), и это не случайно: так будет для любого одно- значного кода. В самом деле, по определению однозначности никакое слово не может быть получено двумя способами при соединении кодо- вых слов. Теперь подставим 𝑎 = 𝑏 = 1/2 в наше равенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится (2 − 𝑛 1 + 2 − 𝑛 2 + . . . + 2 − 𝑛 𝑘 ) 𝑁 (в скобке как раз выражение из неравенства Крафта { Макмиллана). Правую часть мы оценим сверху, сгруппировав слова по длинам: име- ется не более 2 𝑙 слагаемых длины 𝑙, каждое из которых равно 2 − 𝑙 , и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть 𝑁 max 𝑛 𝑖 . Итак, получаем, что (2 − 𝑛 1 + 2 − 𝑛 2 + . . . + 2 − 𝑛 𝑘 ) 𝑁 < 𝑁 max 𝑛 𝑖 , и это верно при любом 𝑁. Если основание степени в левой части больше единицы, то при больших 𝑁 это неравенство нарушится (показательная функция растёт быстрее линейной). Поэтому для однозначного кода выполняется неравенство Крафта { Макмиллана. 12.3. Код Хаффмана 235 12.3. Код Хаффмана Теперь задача о коде минимальной средней длины приобретает та- кую форму: для данных положительных 𝑝 1 , . . . , 𝑝 𝑘 , равных в сумме еди- нице, найти целые положительные 𝑛 1 , . . . , 𝑛 𝑘 , для которых выполнено неравенство Крафта { Макмиллана, а сумма 𝑘 ∑︁ 𝑖=1 𝑝 𝑖 𝑛 𝑖 является минимально возможной (среди наборов 𝑛 1 , . . . , 𝑛 𝑘 , удовлетво- ряющих неравенству). Задача 12.2.5 показывает показывает, что сред- няя длина однозначного кода не меньше этого минимума, а задача 12.2.3 говорит, что этот минимум достигается, причём даже для префиксного кода. Как же найти числа 𝑛 1 , . . . , 𝑛 𝑘 , доставляющие этот минимум? 12.3.1. Докажите, что для двух букв оптимальный код состоит из двух слов длины 1, независимо от частот букв. Чтобы решить задачу в общем случае, начнём с нескольких простых замечаний. 12.3.2. Пусть частоты расположены в убывающем порядке: 𝑝 1 > > 𝑝 2 > . . . > 𝑝 𝑘 . Докажите, что тогда длины слов оптимального кода идут в неубывающем порядке: 𝑛 1 6 𝑛 2 6 . . . 6 𝑛 𝑘 Решение. Если бы более редкая буква имела бы более короткое кодо- вое слово, то, обменяв кодовые слова, мы сократили бы среднюю длину кода. 12.3.3. Останется ли утверждение предыдущей задачи в силе, если частоты расположены в невозрастающем порядке (возможны равные)? Решение. Нет: если, скажем, имеются три буквы с частотой 1/3, то оптимальный код будет иметь длины слов 1, 2, 2 (если бы два кодовых слова имели длину 1, то на третье уже не осталось бы места), и они могут идти в любом порядке. Заметим, однако, что при поиске оптимального кода (для невоз- растающих частот) мы вправе ограничиваться лишь кодами, в кото- рых длины кодовых слов неубывают (поскольку кодовые слова для букв одинаковых частот можно переставлять без изменения средней длины кода). 236 12. Оптимальное кодирование 12.3.4. Пусть частоты расположены в невозрастающем порядке (𝑝 1 > 𝑝 2 > . . . > 𝑝 𝑘 ), а длины слов в оптимальном коде расположены в не- убывающем порядке 𝑛 1 6 𝑛 2 6 . . . 6 𝑛 𝑘 . Докажите, что 𝑛 𝑘−1 = 𝑛 𝑘 (при 𝑘 > 2). Решение. Предположим, что это не так, и что есть единственное са- мое длинное кодовое слово длины 𝑛 𝑘 . Тогда неравенство Крафта { Мак- миллана не может обращаться в равенство, поскольку все слагаемые, кроме наименьшего (последнего), кратны удвоенному последнему сла- гаемому. Значит, в этом неравенстве есть запас, причём не меньший последнего слагаемого. А тогда можно уменьшить 𝑛 𝑘 на единицу, не нарушая неравенства, что противоречит предположению об оптималь- ности исходного кода. Эта задача показывает, что при поиске оптимального кода можно рассматривать лишь коды, в которых две самые редкие буквы имеют коды одинаковой длины. 12.3.5. Как свести задачу отыскания длин кодовых слов оптималь- ного кода для 𝑘 частот 𝑝 1 > 𝑝 2 > . . . > 𝑝 𝑘−2 > 𝑝 𝑘−1 > 𝑝 𝑘 к задаче поиска длин оптимального кода для 𝑘 − 1 частот 𝑝 1 , 𝑝 2 , . . . , 𝑝 𝑘−2 , 𝑝 𝑘−1 + 𝑝 𝑘 (частоты двух самых редких букв объединены)? Решение. Мы уже знаем, что можно рассматривать лишь коды с 𝑛 𝑘−1 = 𝑛 𝑘 . Неравенство Крафта { Макмиллана тогда запишется как 2 − 𝑛 1 + 2 − 𝑛 2 + . . . + 2 − 𝑛 𝑘−2 + 2 − 𝑛 𝑘−1 + 2 − 𝑛 𝑘 = = 2 − 𝑛 1 + 2 − 𝑛 2 + . . . + 2 − 𝑛 𝑘−2 + 2 − 𝑛 6 1, если положить 𝑛 𝑘−1 = 𝑛 𝑘 = 𝑛 + 1. Таким образом, числа 𝑛 1 , . . . , 𝑛 𝑘−2 , 𝑛 должны удовлетворять неравенству Крафта { Макмиллана для 𝑘 − 1 букв. Средняя длины этих двух кодов будут связаны: 𝑝 1 𝑛 1 + . . . + 𝑝 𝑘−2 𝑛 𝑘−2 + 𝑝 𝑘−1 𝑛 𝑘−1 + 𝑝 𝑘 𝑛 𝑘 = = 𝑝 1 𝑛 1 + . . . + 𝑝 𝑘−2 𝑛 𝑘−2 + (𝑝 𝑘−1 + 𝑝 𝑘 )𝑛 + [𝑝 𝑘−1 + 𝑝 𝑘 ]. Последнее слагаемое (квадратная скобка) не зависит от выбираемого кода, поэтому минимизировать надо остальное, то есть как раз сред- нюю длину кода с длинами слов 𝑛 1 , . . . , 𝑛 𝑘−2 , 𝑛 для частот 𝑝 1 , 𝑝 2 , . . . . . . , 𝑝 𝑘−2 , 𝑝 𝑘−1 + 𝑝 𝑘 . После этого надо положить 𝑛 𝑘−1 = 𝑛 𝑘 = 𝑛 + 1, и это даст оптимальный код для исходной задачи. 12.4. Код Шеннона { Фано 237 Используя эту задачу, несложно составить рекурсивную программу для отыскания длин кодовых слов. С каждым вызовом число букв бу- дет уменьшаться, пока мы не сведём задачу к случаю двух букв, когда оптимальный код состоит из слов 0 и 1. Затем можно найти и сами кодовые слова (согласно задаче 12.2.3 ). Но проще объединить эти дей- ствия и сразу искать кодовые слова: ведь замена числа 𝑛 на два числа 𝑛 + 1 соответствует замене кодового слова 𝑃 на два слова 𝑃 0 и 𝑃 1 на единицу большей длины (и эта последняя замена сохраняет префикс- ность кода). Код, построенный таким методом, называется кодом Хаффмана. Мы доказали, что он имеет минимальную среднюю длину среди всех кодов (для данных частот букв). В следующей задаче оценивается чи- сло операций, необходимых для построения кода Хаффмана. 12.3.6. Покажите, что можно обработать частоты 𝑝 1 , . . . , 𝑝 𝑘 , сде- лав 𝑂(𝑘 log 𝑘) операций, после чего 𝑖-е кодовое слово можно указать за время, пропорциональное его длине. [Указание. Заметим, что оценка времени довольно сильная: толь- ко на сортировку чисел 𝑝 𝑖 уже уходит 𝑂(𝑘 log 𝑘) действий. Поэтому, применяя предыдущую задачу, нужно использовать результаты сорти- ровки 𝑘 чисел при сортировке меньшего количества чисел. Это можно сделать с помощью очереди с приоритетами, вынимая два минималь- ных числа и добавляя их сумму за 𝑂(log 𝑘) действий. Это позволяет определить, какие две буквы надо соединять в одну на каждом шаге. Параллельно с соединением букв можно строить дерево кодов, проводя рёбра (помеченные 0 и 1) от соединённой буквы к каждой из её по- ловинок. При этом требуется 𝑂(1) действий на каждом шаге. После завершения построение прослеживать код любой буквы можно символ за символом.] 12.4. Код Шеннона { Фано Мы видели, как можно построить оптимальный код (имеющий ми- нимальную среднюю длину) для данного набора частот. Однако эта конструкция не даёт никакой оценки для средней длины оптимального кода (как функции от частот 𝑝 𝑖 ). Следующие задачи указывает такую оценку (с абсолютной погрешностью не более 1). 12.4.1. Покажите, что для любых положительных частот 𝑝 1 , . . . , 𝑝 𝑘 (в сумме равных единице) существует код средней длиной не более 238 12. Оптимальное кодирование 𝐻(𝑝 1 , . . . , 𝑝 𝑘 ) + 1, где функция 𝐻 (называемая энтропией Шеннона) определяется формулой 𝐻(𝑝 1 , . . . , 𝑝 𝑛 ) = 𝑝 1 (− log 2 𝑝 1 ) + . . . + 𝑝 𝑘 (− log 2 𝑝 𝑘 ) Решение. Если частоты 𝑝 𝑖 представляют собой целые (отрицатель- ные) степени двойки, то это утверждение почти очевидно. Положим 𝑛 𝑖 = − log 𝑝 𝑖 (здесь и далее все логарифмы двоичные). Тогда 2 − 𝑛 𝑖 = 𝑝 𝑖 и потому для чисел 𝑛 𝑖 выполнено неравенство Крафта { Макмиллана. По задаче 12.2.3 можно построить префиксный код с длинами кодовых слов 𝑛 1 , . . . , 𝑛 𝑘 , и средняя длина этого кода будет равна 𝐻(𝑝 1 , . . . , 𝑝 𝑘 ) (и даже единицу добавлять не надо). Эта единица пригодится, если log 𝑝 𝑖 не целые. В этом случае надо взять наименьшее 𝑛 𝑖 , при котором 2 − 𝑛 𝑖 6 𝑝 𝑖 . Для таких 𝑛 𝑖 выполняется неравенство Крафта { Макмиллана, и они больше − log 𝑝 𝑖 не более чем на единицу (потому и после усреднения ухудшение будет не более чем на единицу). Построенный на основе этой задачи код называется кодом Шенно- на { Фано. Это построение легко извлекается из решения задачи 12.2.3 : рассматривая числа 𝑛 𝑖 = −⌊log 𝑝 𝑖 ⌋ (наименьшие целые числа, для ко- торых 2 − 𝑛 𝑖 6 𝑝 𝑖 ) в порядке убывания, мы отводим для каждого из них кодовое слово и соответствующий участок отрезка [0, 1] слева на- право. При этом мы проигрываем в длине кода (по сравнению с оптималь- ным кодом) не более единицы: как мы сейчас увидим, средняя длина любого (в том числе и оптимального) кода не меньше 𝐻(𝑝 1 , . . . , 𝑝 𝑘 ). 12.4.2. (Для знакомых с математическим анализом) Докажите, что (при данных положительных частотах, в сумме дающих единицу) сред- няя длина любого (однозначного) кода не меньше 𝐻(𝑝 1 , . . . , 𝑝 𝑘 ). Решение. Имея в виду неравенство Крафта { Макмиллана, мы дол- жны доказать такой факт: если 2 − 𝑛 1 + . . . 2 − 𝑛 𝑘 6 1, то 𝑝 1 𝑛 1 + . . . + 𝑝 𝑘 𝑛 𝑘 > 𝐻(𝑝 1 , . . . , 𝑝 𝑘 ). Это верно для любых 𝑛 𝑖 , не обязательно целых. Удобно перейти от 𝑛 𝑖 к величинам 𝑞 𝑖 = 2 − 𝑛 𝑖 ; интересующее нас утверждение тогда гласит, что если 𝑝 1 , . . . , 𝑝 𝑘 и 𝑞 1 , . . . , 𝑞 𝑘 | два набора положительных чисел, 12.4. Код Шеннона { Фано 239 и сумма чисел в каждом равна единице, то 𝑝 1 (− log 𝑞 1 ) + . . . + 𝑝 𝑘 (− log 𝑞 𝑘 ) > 𝑝 1 (− log 𝑝 1 ) + . . . + 𝑝 𝑘 (− log 𝑝 𝑘 ). Другими словами, выражение 𝑝 1 (− log 𝑞 1 ) + . . . + 𝑝 𝑘 (− log 𝑞 𝑘 ) (рассматриваемое при фиксированных 𝑝 𝑖 как функция на множестве всех положительных 𝑞 1 , . . . , 𝑞 𝑘 , в сумме равных единице) достигает ми- нимума при 𝑞 𝑖 = 𝑝 𝑖 . Область определения этой функции есть внутрен- ность симплекса (треугольника при 𝑛 = 3, тетраэдра при 𝑛 = 4 и т. д.) и при приближении к границе одно из 𝑞 𝑖 становится малым, а его минус логарифм уходит в бесконечность. Значит, минимум функции достига- ется внутри области. В точке минимума градиент (−𝑝 1 /𝑞 1 , . . . , −𝑝 𝑛 /𝑞 𝑛 ) должен быть перпендикулярен плоскости, на которой функция опре- делена (иначе сдвиг вдоль этой плоскости уменьшал бы функцию), то есть все 𝑝 𝑖 /𝑞 𝑖 равны. Поскольку ∑︀ 𝑝 𝑖 = ∑︀ 𝑞 𝑖 = 1, то это означает, что 𝑝 𝑖 = 𝑞 𝑖 Другое объяснение: функция log выпукла вверх, поэтому для любых неотрицательных коэффициентов 𝛼 𝑖 , в сумме равных единице, и для любых точек 𝑥 𝑖 из области определения логарифма выполняется нера- венство log (︁∑︁ 𝛼 𝑖 𝑥 𝑖 )︁ > ∑︁ 𝛼 𝑖 log 𝑥 𝑖 Остаётся положить 𝛼 𝑖 = 𝑝 𝑖 , 𝑥 𝑖 = 𝑞 𝑖 /𝑝 𝑖 ; в левой части будет логарифм единицы, то есть нуль, а ∑︀ 𝑝 𝑖 log(𝑞 𝑖 /𝑝 𝑖 ) есть как раз разность между левой и правой частями доказываемого неравенства. Велика ли экономия от использования кодов, описанных в этом раз- деле? Это, конечно, зависит от частот букв: если они все одинако- вые, то никакой экономии не будет. Легко заметить, что в русском языке разные буквы имеют разную частоту. Если, скажем, в текстах (TEX-файлах) этой книжки (на момент эксперимента) оставить толь- ко 33 строчные русские буквы от «а» до «я», а все остальные символы не учитывать, то самой частой буквой будет буква «о» (частота 0,105), а самой редкой | твёрдый знак (частота 0,00019). Значение энтропии Шеннона при этом будет равно 4,454 (сравните с 5 битами, необхо- димыми для кодирования 32 букв). Выигрыш не так велик. Он будет больше, если учитывать также и другие символы (прописные буквы, знаки препинания и др.), которые встречаются в тексте гораздо реже. Наконец, можно кодировать не буквы, а двухбуквенные комбинации или 240 12. Оптимальное кодирование ещё что-нибудь. Именно так поступают популярные программы сжатия информации (типа zip), которые позволяют сократить многие тексты в полтора-два раза (а некоторые другие файлы данных | и в большее число раз). 12.4.3. Компания M. утверждает, что её новая программа супер- сжатия файлов позволяет сжать любой файл длиной больше 100 000 бай- тов по крайней мере на 10% без потери информации (можно восстано- вить исходный файл по его сжатому варианту). Докажите, что она врёт. 13. ПРЕДСТАВЛЕНИЕ МНОЖЕСТВ. ХЕШИРОВАНИЕ 13.1. Хеширование с открытой адресацией В главе 6 было указано несколько представлений для множеств, эле- ментами которых являются целые числа произвольной величины. Одна- ко в любом из них хотя бы одна из операций проверки принадлежности, добавления и удаления элемента требовала количества действий, про- порционального числу элементов множества. На практике это бывает слишком много. Существуют способы, позволяющие получить для всех трёх упомянутых операций оценку 𝐶 log 𝑛. Один из таких способов мы рассмотрим в следующей главе. В этой главе мы разберём способ, кото- рые хотя и приводит к 𝐶𝑛 действиям в худшем случае, но зато «в сред- нем» требует значительно меньшего их числа. (Мы не будем уточнять слов «в среднем», хотя это и можно сделать.) Этот способ называется хешированием. Пусть нам необходимо представлять множества элементов типа T, причём число элементов в них заведомо меньше n. Выберем некото- рую функцию h, определённую на значениях типа T и принимающую значения 0 . . . n-1. Было бы хорошо, чтобы эта функция принимала на элементах будущего множества по возможности более разнообразные значения. (Худший случай | это когда её значения на всех элемен- тах хранимого множества одинаковы.) Эту функцию будем называть хеш-функцией, или, как ещё говорят, функцией расстановки. Введём два массива val: array [0..n-1] of T; used: array [0..n-1] of boolean; (мы позволяем себе писать n-1 в качестве границы в определении типа, 242 13. Представление множеств. Хеширование хотя в паскале это не разрешается). В этих массивах будут храниться элементы множества: оно равно множеству всех val [i] для тех i, для которых used [i], причём все эти val [i] различны. По возможности мы будем хранить элемент t на месте h(t), считая это место «искон- ным» для элемента t. Однако может случиться так, что новый элемент, который мы хотим добавить, претендует на уже занятое место (для которого used истинно). В этом случае мы отыщем ближайшее справа свободное место и запишем элемент туда. («Справа» значит «в сторо- ну увеличения индексов»; дойдя до края, мы перескакиваем в начало.) По предположению, число элементов всегда меньше n, так что пустые места заведомо будут. Формально говоря, в любой момент должно соблюдаться такое тре- бование: для любого элемента множества участок справа от его искон- ного места до его фактического места полностью заполнен. Благодаря этому проверка принадлежности заданного элемента t осуществляется легко: встав на h(t), двигаемся направо, пока не дой- дём до пустого места или до элемента t. В первом случае элемент t отсутствует в множестве, во втором | присутствует. Если элемент отсутствует, то его можно добавить на найденное пустое место. Если присутствует, то можно его удалить (положив used = false). 13.1.1. В предыдущем абзаце есть ошибка. Найдите её и исправьте. Решение. Дело в том, что при удалении требуемое свойство «отсут- ствия пустот» может нарушиться. Поэтому будем делать так. Создав дыру, будем двигаться направо, пока не натолкнёмся на элемент, сто- ящий не на исконном месте, или на ещё одно пустое место. Во втором случае на этом можно успокоиться. В первом случае посмотрим, не нужно ли найденный элемент поставить на место дыры. Если нет, то продолжаем поиск, если да, то затыкаем им старую дыру. При этом образуется новая дыра, с которой делаем всё то же самое. 13.1.2. Напишите программы проверки принадлежности, добавле- ния и удаления. Решение. function принадлежит (t: T): boolean; var i: integer; begin i := h (t); while used [i] and (val [i] <> t) do begin i := (i + 1) mod n; end; {not used [i] or (val [i] = t)} 13.1. Хеширование с открытой адресацией 243 принадлежит := used [i] and (val [i] = t); end; procedure добавить (t: T); var i: integer; begin i := h (t); while used [i] and (val [i] <> t) do begin i := (i + 1) mod n; end; {not used [i] or (val [i] = t)} if not used [i] then begin used [i] := true; val [i] := t; end; end; procedure исключить (t: T); var i, gap: integer; begin i := h (t); while used [i] and (val [i] <> t) do begin i := (i + 1) mod n; end; {not used [i] or (val [i] = t)} if used [i] and (val [i] = t) then begin used [i] := false; gap := i; i := (i + 1) mod n; {gap - дыра, которая может закрыться одним из i,i+1,...} while used [i] do begin if i = h (val[i]) then begin {на своём месте, ничего не делать} end else if dist(h(val[i]),i) < dist(gap,i) then begin {gap...h(val[i])...i, ничего не делать} end else begin used [gap] := true; val [gap] := val [i]; used [i] := false; gap := i; end; i := (i + 1) mod n; end; end; end; Здесь dist (a,b) | измеренное по часовой стрелке (слева направо) 244 13. Представление множеств. Хеширование расстояние от a до b, то есть dist (a,b) = (b - a + n) mod n. (Мы прибавили n, так как функция mod правильно работает при поло- жительном делимом.) 13.1.3. Существует много вариантов хеширования. Один из них та- ков: обнаружив, что исконное место (обозначим его 𝑖) занято, будем ис- кать свободное не среди 𝑖 + 1, 𝑖 + 2, . . ., а среди 𝑟(𝑖), 𝑟(𝑟(𝑖)), 𝑟(𝑟(𝑟(𝑖))), . . ., |