

%magic to do it work

\Section{Хаффман и жадность}{11 декабря}{Лобанов Артём}

\Subsection{Задача о шахматном коне (Правило Варнсдорфа)}
    
\Subsubsection{Постановка задачи}

    Найти гамельтонов путь на шахматном поле n на n ходом коня.
    
\Subsubsection{Правило Варнсдорфа}

Давайте строить путь жадно. На каждой итерации следует добавлять вершину наименьшей остаточной степени (из ещё не посещённых и доступных из последней клетки пути). Утверждается, что с большой вероятностью мы найдём гамельтонов путь. 


\Subsubsection{Куда идти, если вершин наименьшей степени несколько?}


1) \textquotedblleft Куда-нибудь\textquotedblright ~- плохо. Возможна ситуация, когда такой алгоритм не найдёт путь.

2) Random - хорошо. С большой вероятностью путь будет найден (а если нет, можно попробовать ещё раз т.к. алгоритм недетерминированный).

3) Утверждается, что хорошо работает стратегия \textquotedblleft прижиматься к краю\textquotedblright~т.е. при равенстве остаточных степеней выбирать вершину, расстояние от которой до ближайшего края меньше. При равенстве расстояний - случайную.
    
\Subsubsection{Откуда начинать?}

1) Можно пробовать стартовать со случайных клеток.

2) Можно перед этим попробовать начать с \textquotedblleft особенных\textquotedblright~клеток (угловой, крайней, центральной).

\Subsubsection{Обобщение для произвольного графа (всё ещё жадность)}

Берём вершину минимальной степени, среди таких - случайную. Начинаем со случайной.

\Subsubsection{Улучшение}

1) Остаток должен быть связен и все вершины должны быть достижимы из текущей вершины (dfs). Иначе гамельтонов путь с таким префиксом не получится.

2) Существует не более одной вершины степени 1.  Иначе гамельтонов путь с таким префиксом не получится.

3) Пробовать ходить в первые k вершин в порядке увеличения степени. Чем меньше k тем больше вероятность не найти путь, чем больше k тем дольше алгоритм работает.


~\\~\\

\Subsection{Хаффман и сжатие данных}

\Subsubsection{Идеальный архиватор}

Не существует алгоритма, который сжимает любую битовую строку длины n (без потери информации).

Действительно, строк длины n ровно $2^n$, а строк строго меньшей длины ровно $2^n - 1$, что, очевидно, меньше.

\Subsubsection{Кодирование}

$\sum$ - алфавит, $|\sum| = n$.

Не любой набор кодов подходит для кодирования. Например, если мы выбрали коды для символов так: a -> 0, b -> 1, c -> 01, то запись 01 нельзя будет декодировать однозначно (подойдёт и \textquotedblleft ab\textquotedblright, и \textquotedblleft c\textquotedblright).

Набор слов называется беспрефиксным, если никакое слово не является префиксом другого.

Заметим, что если коды обладают этим свойством (беспрефиксностью), то любую корректную запись можно однозначно декодировать. Для эффективной расшифровки можно использовать структуру данных Бор, в которой будут храниться коды.

Мы будем кодировать текст следующим образом: первые k бит (заранее известное число) - длина закодированного текста, потом какое-то количество бит отведено под кодирование дерева кодов, потом последовательная запись кодов символов.


\Subsubsection{Алгоритм Хаффмана}

Алгоритм Хаффмана подбирает такой беспрефиксный набор кодов к алфавиту, что последовательная запись кодов символов текста, имеет минимальную возможную длину. Иными словами, если $cnt_i$ - количество вхождений i-ого символа, а $len_i$ - длина кода, соответствующего i-ому символу, то $\sum (cnt_i \cdot len_i) \rightarrow min$.

\Subsubsection{Наблюдения}

1) Из двух различных кодов более короткий следует отдать символу, который используется чаще. (Действительно, попробуем сделать наоборот, и заметим, что суммарная длина неуменьшится).

2) Заметим, что коды могут заканчиваться только в листях бора. Действительно, иначе такой код будет префиксом другого кода (вершина имела детей => спустившись вниз по бору мы получим ещё какой-то код).

3) Рассмотрим бор из кодов. Заметим, что любая вершина должна быть либо листом, либо иметь два ребёнка. Действительно, пусть какая-то вершина имеет одного ребёнка. Удалим её, а её ребёнка подвесим к предку. Беспрефиксность не сломалась, а какой-то код (как минимум один, к которому вела ветка) стал короче.

\Subsubsection{Алгоритм}

Попытаемся выбрать оптимальное дерево кодов.

Представим, что мы уже нашли ответ. Рассмотри самую глубокую ветку. Предпоследняя вершина в этой ветке обязана иметь два ребёнка (а т.к. рассматриваемая ветка была самая глубокая, то второй ребёнок тоже обязан быть листом). Из наблюдения №1 следует, что коды, соответствующие этим листям, должны использоваться для кодирования самых редких символов (Если таких несколько - выберем любые два). Пусть эти символы $c_1$ и $c_2$. Удалим оба листа из дерева, а их предку поставим в соответствие мнимый символ, количество вхождений которого будет равно сумме частот вхождений $c_1$ и $c_2$. Пусть мы теперь найдём оптимальное решение для новой задачи. Заметим, что если мы теперь вернём листы с $c1$ и $c2$ в дерево (проведём из мнимой вершины рёбра 0 и 1 в $c_1$ и $c_2$ соответственно), то величина [$\sum(cnt_i\cdot~len_i)$] изменится на константу (на суммарное количество вхождений $c_1$ и $c_2$). Тоже самое происходило и при удалении этих вершин (указанная величина тоже менялась на константу). Таким образом, из оптимального дерева для новой задачи должно получаться оптимальное решение для старой задачи. Тогда мы можем решать задачу итеративно, уменьшая на каждом этапе количество символов в алфавите на 1. Последнее наблюдение - алфавиту из одного символа должно соответствовать дерево из одной вершины (Действительно, рассмотрим корень дерева. Двух детей у него быть не может т.к. дерево должно содержать только один код; одного ребёнка быть не может по наблюдению №3, а значит, корень не имеет детей).

\Subsubsection{Сохранение дерева кодов}

К сожалению, для декодирования текста нам нужно опять построить дерево кодов. Существует несколько способов передачи дерева:

1) Можно передавать всю таблицу количества вхождений. Это займёт $n \cdot k + 32$ бита, где k - минимальное количество бит, необходимое для кодирования количества вхождений ($k = \log_2MAX\_CNT$ с округлением вверх, где $MAX\_CNT$ - количество вхождений самого частого символа). 32 бита (например) уйдёт на кодирование дополнительной информации (k или длины всей таблицы).

2) Можно закодировать сразу само дерево. Например, так:
        
        Закодируем поддерево вершины A. Если A имеет детей, то запишем \textquotedblleft 0(код левого поддерева)(код правого поддерева)\textquotedblright, иначе (A - лист) \textquotedblleft1(код символа, которому соответствует этот лист)\textquotedblright.
        
%3) (!!в разработке!!) Пусть $K_n$ - количество деревьев с n листами. Символы алфавита могут соответствовать листям одним из n! способов. Тогда наше дерево можно также зашифровать с помощью 
%$\log(n! \cdot K_n)$ бит (округление вверх).




 



 