Сергей Холодилов (fat_crocodile) wrote,
Сергей Холодилов
fat_crocodile

Categories:

Хаффман с ограниченной разрядностью

Все знаю про кодирование Хаффманом. Оказывается есть интересные вариации.

На всякий случай напомню о чём это. У нас есть некий алфавит и написанный им текст, и мы хотим записать этот текст в двоичном виде, причём очень простым способом:
  • сопоставить каждой букве алфавита двоичный код

  • записать текст, используя коды вместо букв

При этом
  • длины кодов различных букв могут отличаться

  • хочется, чтобы декодер, читая получившуюся бинарную строку от начала к концу мог однозначно определить границы кодов, не используя какие-то сложные правила. Требуем чтобы ни один код не был префиксом другого. Такой код называется префиксным.

    То есть набор кодов (0, 10, 110, 111) подходит, например строку 00101000100111110 можно однозначно разбить на 0-0-10-10-0-0-10-0-111-110. А (0, 10, 101, 111) не подходит: 1010 это 101-0 или 10-10?
    Это довольно слабое ограничение, например любой код фиксированной длины очевидно префиксный и т.п., отсекаются только довольно странные вещи

  • нужно чтобы бинарная строка была бы покороче

Ну и в общем понятно, что для того чтобы результат получился покороче, символам, которые встречаются почаще стоит дать коды покороче, а тем что пореже -- можно подлиннее. Это и есть основная мысль. Алгоритм построения оптимального (с точки зрения длины получающейся строки) кода, удовлетворяющего этим условиям, придумал David A. Huffman, статья опубликована в 1952-м.

Вот, кстати, интересно: учёный, дожил до 1999, а известен всем только как автор четырёхстраничной статьи написанной в аспирантуре, с алгоритмом, который можно объяснить школьнику. И даже в 1998, а потом в 1999 его ещё два раза наградили за неё, напоследок. Наверное ему было немного обидно от всего этого. Хотя вики и пишет, что у него были значительные достижения в других областях, видимо они были не настолько значительными, чтобы описывать в вики сами эти достижения. Просто хоть не становись знаменитым.

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

Классический алгоритм Хаффмана несложный и широко известный, код действительно оптимальный. Но коды редких символов могут получаться довольно длинными, иногда это неудобно. И оказывается, что попытка наложить ограничение на максимальную длину значительно всё усложняет.

Теперь какие-то чуть менее всем известные вещи.

Значение имеет только размер
Два кода

а <--> 0, б <--> 10, в <--> 11
и
а <--> 1, б <--> 00, в <--> 01

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

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

Например такое соображение: оптимальность, очевидно, зависит от текста, для одного текста код оптимален, для другого нет -- так что "откуда же он знает", процедура построения канонического кода не может от этого зависеть.

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

Например для такой кодировки

а <--> 0
б <--> 10
в <--> 11

Получится примерно такое дерево:
                   +
                  / \
             0   /   \   1
                /     \
               а       + 
                      / \
                  0  /   \  1
                    /     \
                   б       в

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

Для деревьев можно рекурсивно что-нибудь доказывать, а потом переносить это на коды. Например то, что Σ2-li <= 1, где li это длины путей до листов. Доказательство: дерево, состоящее из одного единственного корня-листа удовлетворяет, предположим для деревьев высоты не больше n и докажем для дерева высоты n+1. Для обоих поддеревьев неравенство выполняется, добавочное ребро делит суммы для каждого из них ещё пополам, значит в итоге тоже не больше чем 1. Это неравенство Крафта-Макмиллана и это не только необходимое условие, но и достаточное: если набор длин удовлетворяет неравенству, можно построить дерево. Здесь есть не очень аккуратное доказательство, которое можно немного допилить.

Если у получившегося дерева есть однодетные узлы, то:
- если ребёнок -- лист, его можно отрезать, а букву из этого листа перенести на уровень выше, в бывший узел, который теперь стал листом.
- если ребёнок -- узел, эти два узла можно склеить, а ребро между ними выкинуть.

То есть в обоих случаях код можно улучшить очевидным образом. Назовём коды, которые можно так просто улучшить "глупыми" и больше не будем их принимать во внимание -- действительно, зачем нам глупые коды? Так что можно считать, что у всех интересующих нас кодов у каждого внутреннего узла дерева по два ребёнка. Англичане называют такие бинарные деревья full, русского термина не нашёл, пусть будет "полное".

Для полного дерева Σ2-li == 1.

И собственно к поставленной задаче. То что написано ниже это пересказ в свободной форме следующей статьи:

LAWRENCE L. LARMORE, DANIEL S. HIRSCHBERG
"A Fast Algorithm for Optimal Length-Limited Huffman Codes"
Journal of the Association for Computing Machinery, Vol. 37, No. 3, July 1990

Статья гуглится.

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

[Насколько я понимаю] та же задача, но в другой формулировке -- задача про нумизмата, пошедшего по миру. У него есть коллекция монет, с помощью которой он пытается расплатиться в магазине. При этом продавец принимает монеты по номинальной стоимости, а нумизмат ещё на что-то надеется и старается уменьшить суммарную потраченную нумизматическую ценность.

В частном случае, если
- нужно набрать ровно указанную сумму, без сдачи
- номинальная стоимость монет это степени двойки

эту задачу можно решить за линейное время.

Итак, пусть I -- набор монет, пар (номинал, нумизмат), а X -- требуемая сумма. Номиналы -- степени двойки, возможно отрицательные, нумизматы -- положительные вещественные числа. X -- положительное рациональное число, представимое конечной суммой степеней двойки. Назовём это задачей (I, X) и будем решать рекурсивно.

- если X = 0, ответ -- пустое множество
- если X > 0, а I -- пустое, ответа нет

разложим X по степеням двойки, найдём минимальную входящую в X степень -- lsd (least significant digit)

- если lsd < min номинал из I, решения нет
- если lsd == min номинал из I, и монета с таким номиналом в I одна, то дальше можно решать задачу (I - эта_монета, X - lsd), а потом добавить монету к решению
- если lsd == min номинал из I, и монет с таким номиналом в I несколько, то из них нужно выбрать с наименьшим нумизматической ценностью и как в предыдущем пункте
- если lsd > min номинал из I, и монета с минимальным номиналом в I одна, решать задачу можно без неё, она не пригодится.
- если lsd > min номинал из I, и монет с минимальным номиналом в I несколько, выберем две с наименьшей нумизматической ценностью, обмотаем изолентой и будем считать одной монетой удвоенного номинала (и с соответствующей нумизматической ценностью)

В каждой ветке либо мы получаем результат, либо мощность I уменьшается на 1, так что рекурсия всегда заканчивается; оценка для количества шагов сверху -- исходная мощность I.

Алгоритм называется "package-merge", название относится к двум стадиям рекурсивного перехода к задаче меньшего размера в последней рассмотренной ветке.
- package обозначает обматывание изолентой -- т.е. удаление двух монет из набора и создание из них новой "монеты".
- merge -- "и будем считать одной монетой удвоенного номинала" -- т.е. внесение новой монеты в набор.


Здесь всё прекрасно, кроме понятия "нумизматическая ценность", которое не хочется с собой тащить дальше. Поэтому, вспомнив о греках, римлянах и действительно тяжёлых деньгах, заменим его на вес. Пусть это будет не нумизмат, а обычный человек, который собрался за хлебом, но много денег ему не поднять, вес надо экономить. Тем более, что у символов -- вот удача -- тоже веса. И как будет видно их тоже нужно именно экономить.

Сведение построения кодового дерева ограниченной высоты к задаче нумизмата
Пусть у нас есть n символов с весами wi и соответствующее кодовое дерево. Минимизировать нужно взвешенную сумму длин путей, то есть Σliwi. Идея номер один в том, чтобы каждому ребру каждого пути сопоставить монету веса wi.

Замечательно. Осталось
- выбрать исходный набор монет
- придумать, что такое "номинал" для каждой монеты
- найти сумму, которая должна совпадать у всех полных кодовых деревьев с n листьями (глубины не больше L).
- доказать, что при минимизации получится именно дерево, а не что-то другое.

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

- для каждого символа генерируем L монет, весом wi и номиналом от 2-1 до 2-L.
- по задумке, монеты соответствуют рёбрам пути от листа до корня, номинал это 2-глубина ребра.
- одному и тому же ребру в дереве соответствует столько монет, сколько путей лист-корень через него проходит
- для полного дерева сумма номиналов соответствующих монет равна n-1, где n это количество листьев (несложно доказывается рекурсивно)

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

Доказательство
Как вообще доказать, что из выбранных рёбер можно построить дерево? Очевидно, что если получилось дерево, то:
- все символы должны участвовать (иначе это не то дерево, которое нам нужно)
- если для символа есть ребро глубины k>1, то есть и ребро глубины k-1 (путь от листа до корня непрерывен)
- длины путей удовлетворяют неравенству Крафта

Так как неравенство Крафта не только необходимо, но и достаточно, эти три пункта тоже достаточны. То есть, если:
(1) в получившемся наборе монет присутствуют монеты, соответствующие каждому символу
(2) если выбрана монета, соответствующая i-му символу номиналом 2-k, где k>1, то выбрана и монета с номиналом 2-(k-1)
(3) длины путей удовлетворяют неравенству Крафта

То дерево получится.

Лемма 1: все символы в игре.
Это совсем просто, нужно прикинуть общую сумму номиналов всех символов без одного и понять, что она меньше чем n-1.

Лемма 2: если X целое, то для минимального набора монет с суммарным номиналом X выполняется (2).
Пусть это не так. Обозначим этот набор монет как A и рассмотрим набор A', получающийся заменой монеты (2-k, wi) на (2-(k-1), wi). Суммарный вес не изменился, суммарный номинал равен X + 2-k. Вспоминаем алгоритм package-merge и понимаем, что где-то в A' должно быть подмножество монет, отвечающих за 2-k, которые можно выкинуть и получить набор A'', с суммарным номиналом X и меньшим весом, чем A. Противоречие.

То есть можно говорить о том, что для каждого символа получится путь длиной li.

Лемма 3: для набора n путей {li} сумма номиналов равна n - Σ2-li
Это можно просто почитать.

Следствие: так как у нас сумма номиналов равна n-1, Σ2-li == 1, значит неравенство Крафта удовлетворено.

Ура.

Но это мы доказали, что если package-merge дал результат, то получится дерево.
Ещё один вопрос -- почему он даст результат? Алгоритм находит оптимальное решение, если n <= 2L, то хоть какое-то кодовое дерево существует (тривиально строится), значит хоть какое-то решение алгоритм найдёт, значит оно будет оптимальным. А если n > 2L, ожидать решений было бы странно.

Ура-ура.

Особенности package-merge в данном случае
У нас целая сумма и номиналы вида 2-k. Значит по алгоритму нужно сливать-сливать-сливать, по крайней мере, пока не получится 1. После чего нужно выбрать n-1 единиц минимальной ценности. Но единиц получится всего не больше чем n-1, значит все они нам и нужны. Если остановиться на уровне 1/2, то их нужно взять 2n-2 штук, то есть либо все, либо все без последней.

Код:

# Так как мы всегда работаем с монетами одного и того же номинала, хранить его явно не нужно.
# В классической реализации монета хранила бы ссылки на свои компоненты, но они нужны только для двух целей:
#
# - во время работы алгоритма -- вычислить суммарный вес монеты
# - в конце -- найти максимальную глубину вхождения для символов
#
# поэтому монеты хранят суммарный вес и максимальную глубину вхождения для известных монете символов. 
# при слиянии веса суммируются, а глубины выбираются максимальные
def merge_coins(c1, c2):
    w = c1[0] + c2[0]

    d = c1[1].copy()
    for k,v in c2[1].iteritems():
        if k not in d: d[k] = 0   # defaultdict для ленивых
        d[k] = max(d[k], v)

    return w, d

# Вход: 
# - предельная глубина дерева
# - отсортированный по возрастанию список весов
# Выход:
# - список длин кодов
def bounded_haffman(L, weight):
    if 2**L < len(weight):
        raise Exception('ничего не получится')

    coins = []

    for level in range(L, 0, -1):
        # монетки с текущего уровня
        new_coins = [(w, {i:level}) for i,w in enumerate(weight)]
        # монетки, полученные объединением двух монет с предыдущего уровня
        prev_coins = [merge_coins(coins[2*i], coins[2*i+1]) for i in range(len(coins) / 2)]
        # функция imerge сливает два сортированных списка
        coins = list(imerge(prev_coins, new_coins, lambda x,y: x[0] < y[0]))

    # Сливаем результаты
    res = [0] * len(weight)

    for i in range(len(weight) * 2 - 2):
        for k,v in coins[i][1].items():
            if res[k] < v: res[k] = v

    return res
Tags: архиваторы, математика, программинг
Subscribe

  • (no subject)

    Очень простую штуку объяснили, как-то мимо проходила. В книжках про ассемблер и прочее такое пишут про "представление отрицательных чисел в…

  • (no subject)

    Наконец вроде осознал, когда и зачем аксиома выбора нужна, а когда она не нужна. Если у нас есть одно непустое множество X и нам нужно взять…

  • CRC-3: как его обойти

    CRC не криптографически-стойкий алгоритм, он предназначен для обнаружения ошибок, вызванных неразумными обстоятельствами, а не разумным противником.…

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments