Сжатие текста методом Хаффмана

Суть метода

Сначала считаем символы. Вы должны подсчитать частоту появления каждой буквы в строке, чтобы определить их вес для построения дерева.

Строим дерево. После того как вы расставите все знаки в порядке возрастания частоты, нужно объединять самые мелкие элементы в узлы.

Пример: буква «м» встречается четыре раза, а пробел — трижды, поэтому они станут основой для ветвей дерева.

Процесс кодирования

Назначаем биты. Каждому ребру на получившейся структуре присваивается значение ноль или единица, что позволяет превратить текст в последовательность цифр.

Ищем пути. Чтобы получить код для конкретной буквы, нужно пройти от корня дерева до нужного листа, записывая направление каждого шага.

Для фразы «мама мыла раму» буква «м» получит короткий код из двух бит, в то время как редкая «ы» заберет больше места.

Результат работы

Сжимаем данные. Полученная цепочка нулей и единиц будет значительно короче исходного текста, если частота повторения символов распределена неравномерно.

Проверяем точность. Если дерево построено верно, то при обратном декодировании вы получите абсолютно идентичную фразу без потери ни одного знака.