17.2-2 Разработайте основанный на динамическом программировании алгоритм для решения дискретной задачи о рюкзаке. Алгоритм должен работать за время 0(nW) (п - количество вещей, W - максимальный вес рюкзака).

17.2-3 Пусть в дискретной задаче о рюкзаке вещи можно упорядочить таким образом, чтобы одновременно выполнялись неравенства W\ W2 • • • wn п v\ г>2 • • • vn. Разработайте эффективный алгоритм для нахождения оптимального набора и докажите, что он правилен.

17.2-4 Профессор едет по шоссе из Петербурга в Москву, имея при себе карту с указанием всех стоящих на шоссе бензоколонок и расстояний между ними. Известно расстояние, которое может проехать машина с полностью заправленным баком. Разработайте эффективный алгоритм, позволяющий выяснить, на каких бензоколонках надо заправляться, чтобы количество заправок было минимально. (В начале пути бак полон.)

17.2-5 Дано п точек х\, х2,... ,хп на координатной прямой; требуется покрыть все эти точки наименьшим числом отрезков длины 1. Разработайте эффективный алгоритм, решающий эту оптимизационную задачу.

17.2-6* Предполагая известным решение задачи 10-2, найдите решение непрерывной задачи о рюкзаке за время 0(п).

17.3. Коды Хаффмена

Коды Хаффмена широко используются при сжатия информации (в типичной ситуации выигрыш может составить от 20% до 90% в зависимости от типа файла). Алгоритм Хаффмена находит оптимальные коды символов (исходя из частоты использования этих символов в сжимаемом тексте) с помощью жадного выбора.

Пусть в файле длины 100 000 известны частоты символов (рис. 17.3). Мы хотим построить двоичный код (binary character code), в котором каждый символ представляется в виде конечной последовательности битов, называемой кодовым словом (codeword). При использовании равномерного кода (fixed-length code), в котором все кодовые слова имеют одинаковую длину, на каждый символ (из шести имеющихся) надо потратить как минимум три бита, например, а = 000, b = 001,..., f = 101. На весь файл уйдет 300 000 битов - нельзя ли уменьшить это число?

Неравномерный код (variable-length code) будет экономнее, если часто встречающиеся символы закодировать короткими последо-

abedе f

Количество (в тысячах) 45 13 12 169 5

Равномерный кодООО 001 010 011100101

Неравномерный код0 101 100 11111011100

Рис. 17.3 Задача о выборе кода. В файле длиной 100 ООО символов встречаются только латинские буквы от а до f (в таблице указано, по скольку раз каждая). Если каждую букву закодировать тремя битами, то всего будет 300 ООО битов. Если использовать неравномерный код (нижняя строка), то достаточно 224 000 битов.

вательностями битов, а редко встречающиеся - длинными. Один такой код показан на рис. 17.3: буква а изображается однобитовой последовательностью 0, а буква f - четырёхбитовой последовательностью 1100. При такой кодировке на весь файл уйдёт

(45 • 1 + 13 • 3 + 12 • 3 + 16 • 3 + 9 • 4 + 5 • 4) • 1000 = 224 000

битов, что даёт около 25% экономии. (Далее мы увидим, что этот код будет оптимальным.)

Префиксные коды

Мы будем рассматривать только коды, в которых из двух последовательностей битов, представляющих различные символы, ни одна не является префиксом другой. Такие коды называются префиксными кодами (prefix codes; таков общепринятый термин, хотя логичнее было бы называть их «беспрефиксными» кодами). Можно показать (мы этого делать не будем), что для любого кода, обеспечивающего однозначное восстановление информации, существует не худший его префиксный код, так что мы ничего не теряем.

При кодировании каждый символ заменяется на свой код. Например, для неравномерного кода рис. 17.3 строка abc запишется как 0101100. Для префиксного кода декодирование однозначно и выполняется слева направо. Первый символ текста, закодированного префиксным кодом, определяется однозначно, так как кодирующая его последовательность не может быть началом кода какого-то иного символа. Найдя этот первый символ и отбросив кодировавшую его последовательность битов, мы повторяем процесс для оставшихся битов, и так далее. Например, строка 001011101 (при использовании неравномерного кода рис. 17.3) разбивается на части 0 0 1011101 и декодируется как aabe.

Для эффективной реализации декодирования надо хранить информацию о коде в удобной форме. Одна из возможностей - представить код в виде двоичного дерева, листья которого соответствуют кодируемым символам. При этом путь от вершины дерева до кодируемого символа определяет кодирующую последовательность битов: поворот налево даёт 0, а поворот направо - 1.

Рис. 17.4 Деревья, соответствующие двум кодам рис. 17.3. В каждом листе указан соответствующий символ и частота его использования в тексте. Во внутренних узлах указана сумма частот для листьев соответствующего поддерева, (а) Дерево, соответствующее равномерному коду а = ООО, . . . , f = 100. (б) Дерево, соответствующее оптимальному префиксному коду а = 0, b = 101, . . . , f =

На рис. 17.4 изображены деревья, соответствующие двум кодам рис. 17.3.

Оптимальному (для данного файла) коду всегда соответствует двоичное дерево, в котором всякая вершина, не являющаяся листом, имеет двоих детей (см. упражнение 17.3-1). В частности, равномерный код из нашего примера оптимальным быть не может, так как в соответствующем дереве (рис. 17.4а) есть вершина с одним ребёнком (коды некоторых символов начинаются с 10 ..., но ни один код символа не начинается с 11...). Такое свойство оптимального кода позволяет легко доказать, что дерево оптимального префиксного кода для файла, в котором используются все символы из некоторого множества С и только они, содержит ровно \С\ листьев, по одному на каждый символ, и ровно С - 1 узлов, не являющихся листьями.

Зная дерево Г, соответствующее префиксному коду, легко найти количество битов, необходимое для кодирования файла. Именно, для каждого символа с из алфавита С пусть f[c] обозначает число его вхождений в файл, a dj(c) - глубину соответствующего листа в дереве или, что то же самое, длину последовательности битов, кодирующей с. Тогда для кодирования файла потребуется

1100.

сЕС

битов. Назовем это число стоимостью (cost) дерева Т.