Алгоритм Хаффмана — это один из классических методов сжатия данных, основанный на частоте появления символов в тексте. Символы, которые встречаются чаще всего, кодируются короткими последовательностями бит, а редкие символы — более длинными. В результате общая длина сообщения существенно сокращается.
Реализация такого алгоритма на встроенном языке «1С:Предприятие» — отличная задача для развития алгоритмического мышления. Мы подробно разберем весь процесс: от эффективного подсчета частоты символов до построения бинарного дерева, кодирования и последующего декодирования полученной строки.
Первым делом нам нужно определить «вес» (частоту встречаемости) каждого уникального символа в исходном тексте. На форумах часто предлагают использовать для этого объект ТаблицаЗначений или обходить строку посимвольно в цикле. Однако посимвольный обход длинных строк в 1С работает медленно.
Рассмотрим два решения этой задачи: классическое (через таблицу значений) и оптимизированное (через быстрое сокращение строки с помощью функции СтрЗаменить).
Вариант А. Использование Таблицы Значений (классический подход)
Этот способ интуитивно понятен: мы обходим строку символ за символом, ищем его в таблице частот и увеличиваем счетчик. Если символа еще нет в таблице, мы добавляем новую строку.
ТаблицаЧастот = Новый ТаблицаЗначений;
ТаблицаЧастот.Колонки.Добавить("Символ");
ТаблицаЧастот.Колонки.Добавить("КоличествоСимволов", Новый ОписаниеТипов("Число"));
ТаблицаЧастот.Индексы.Добавить("Символ");
Для сч = 1 по СтрДлина(ИсходныйТекст) Цикл
ТекущийСимвол = Сред(ИсходныйТекст, сч, 1);
СтрокаТаблицыЧастот = ТаблицаЧастот.Найти(ТекущийСимвол, "Символ");
Если СтрокаТаблицыЧастот = Неопределено Тогда
СтрокаТаблицыЧастот = ТаблицаЧастот.Добавить();
СтрокаТаблицыЧастот.Символ = ТекущийСимвол;
КонецЕсли;
СтрокаТаблицыЧастот.КоличествоСимволов = СтрокаТаблицыЧастот.КоличествоСимволов + 1;
КонецЦикла;
ТаблицаЧастот.Сортировать("КоличествоСимволов Убыв");
Этот метод хорошо работает на небольших текстах, однако на объемах в несколько мегабайт он начнет зависать из-за частых вызовов метода Найти() и посимвольного перебора.
Вариант Б. Высокопроизводительный метод через СтрЗаменить (Оптимальный)
Выясним, как ускорить этот процесс в десятки раз. Вместо посимвольного перебора мы можем брать первый символ строки, вычислять разницу длин исходной и результирующей строки после удаления этого символа, а затем полностью вырезать его из текста за один проход платформенным методом.
ТаблицаЧастот = Новый ТаблицаЗначений;
ТаблицаЧастот.Колонки.Добавить("Символ");
ТаблицаЧастот.Колонки.Добавить("КоличествоСимволов", Новый ОписаниеТипов("Число"));
ВременныйТекст = ИсходныйТекст;
ТекДлинаФайла = СтрДлина(ВременныйТекст);
Пока ТекДлинаФайла > 0 Цикл
ТекСимвол = Лев(ВременныйТекст, 1);
// Удаляем все вхождения текущего символа из строки
ВременныйТекст = СтрЗаменить(ВременныйТекст, ТекСимвол, "");
КонДлинаФайла = СтрДлина(ВременныйТекст);
// Разница длин и есть количество вхождений символа
КолвоСимволов = ТекДлинаФайла - КонДлинаФайла;
НоваяСтрока = ТаблицаЧастот.Добавить();
НоваяСтрока.Символ = ТекСимвол;
НоваяСтрока.КоличествоСимволов = КолвоСимволов;
ТекДлинаФайла = КонДлинаФайла;
КонецЦикла;
ТаблицаЧастот.Сортировать("КоличествоСимволов Возр");
Проанализируем ситуацию: данный алгоритм работает в среднем в 20 раз быстрее классического перебора, так как замена выполняется силами платформы на низком уровне, а длина обрабатываемой строки стремительно уменьшается с каждым шагом цикла.
Для построения кодов нам понадобится структура данных «Бинарное дерево». Вопреки сомнениям многих разработчиков, дерево можно легко смоделировать в 1С с помощью обычного объекта Структура. Каждый узел дерева будет содержать вес (частоту), символ (только для конечных листьев) и ссылки на два дочерних узла.
Напишем функцию для генерации узла дерева:
Функция СоздатьУзелДерева(Символ, Вес, ЛевыйУзел = Неопределено, ПравыйУзел = Неопределено)
Узел = Новый Структура;
Узел.Вставить("Символ", Символ);
Узел.Вставить("Вес", Вес);
Узел.Вставить("Левый", ЛевыйУзел);
Узел.Вставить("Правый", ПравыйУзел);
Возврат Узел;
КонецФункции
Теперь объединим наши узлы в единое дерево. Алгоритм выглядит следующим образом:
Посмотрим на пример программной реализации этого процесса:
// Шаг 3.1: Заполняем начальный список листьев
СписокУзлов = Новый Массив;
Для Каждого СтрИзТаблицы Из ТаблицаЧастот Цикл
Лист = СоздатьУзелДерева(СтрИзТаблицы.Символ, СтрИзТаблицы.КоличествоСимволов);
СписокУзлов.Добавить(Лист);
КонецЦикла;
// Шаг 3.2: Объединяем узлы, пока не останется один корень
Пока СписокУзлов.Количество() > 1 Цикл
// Сортируем массив узлов по весу (простая пузырьковая сортировка для примера)
Для и = 0 По СписокУзлов.Количество() - 1 Цикл
Для к = и + 1 По СписокУзлов.Количество() - 1 Цикл
Если СписокУзлов[и].Вес > СписокУзлов[к].Вес Тогда
Временный = СписокУзлов[и];
СписокУзлов[и] = СписокУзлов[к];
СписокУзлов[к] = Временный;
КонецЕсли;
КонецЦикла;
КонецЦикла;
// Извлекаем два элемента с наименьшим весом
ЛевыйПотомок = СписокУзлов[0];
ПравыйПотомок = СписокУзлов[1];
СписокУзлов.Удалить(0);
СписокУзлов.Удалить(0); // После удаления первого элемента, второй сдвинулся на индекс 0
// Создаем родительский узел
РодительскийУзел = СоздатьУзелДерева("", ЛевыйПотомок.Вес + ПравыйПотомок.Вес, ЛевыйПотомок, ПравыйПотомок);
// Возвращаем в список
СписокУзлов.Добавить(РодительскийУзел);
КонецЦикла;
КореньДерева = СписокУзлов[0];
После того как дерево построено, нам необходимо пройтись от корня к каждому листу, чтобы определить уникальный префиксный код каждого символа. При переходе по левой ветке мы будем приписывать к коду "0", а при переходе по правой — "1".
Для этого напишем рекурсивную процедуру обхода дерева:
Процедура ОбойтиДеревоИСоздатьКоды(ТекущийУзел, ТекущийКод, ТаблицаКодов)
// Если у узла нет потомков — это лист, сохраняем его код
Если ТекущийУзел.Левый = Неопределено И ТекущийУзел.Правый = Неопределено Тогда
ТаблицаКодов.Вставить(ТекущийУзел.Символ, ТекущийКод);
Возврат;
КонецЕсли;
// Рекурсивно идем влево (добавляем "0") и вправо (добавляем "1")
Если ТекущийУзел.Левый <> Неопределено Тогда
ОбойтиДеревоИСоздатьКоды(ТекущийУзел.Левый, ТекущийКод + "0", ТаблицаКодов);
КонецЕсли;
Если ТекущийУзел.Правый <> Неопределено Тогда
ОбойтиДеревоИСоздатьКоды(ТекущийУзел.Правый, ТекущийКод + "1", ТаблицаКодов);
КонецЕсли;
КонецПроцедуры
Для запуска генерации кодов достаточно вызвать процедуру следующим образом:
ТаблицаКодов = Новый Соответствие; // Используем Соответствие для быстрого поиска кодов при кодировании
ОбойтиДеревоИСоздатьКоды(КореньДерева, "", ТаблицаКодов);
Теперь мы можем представить наш исходный текст в виде бинарной строки (последовательности символов "0" и "1"). Для этого мы просто заменим каждый символ исходного текста на его префиксный код из соответствия ТаблицаКодов.
ЗакодированнаяСтрока = "";
Для сч = 1 по СтрДлина(ИсходныйТекст) Цикл
ТекущийСимвол = Сред(ИсходныйТекст, сч, 1);
ЗакодированнаяСтрока = ЗакодированнаяСтрока + ТаблицаКодов.Получить(ТекущийСимвол);
КонецЦикла;
Для восстановления исходного текста нам необходимы две вещи: бинарная строка кодов и построенное нами дерево Хаффмана. Мы начинаем обход с корня дерева и читаем закодированную строку по одному биту ("0" или "1"). Если встречаем "0" — спускаемся к левому потомку, если "1" — к правому. Как только мы попадаем в лист дерева, мы извлекаем символ, записываем его в результат и снова возвращаемся к корню дерева.
Рассмотрим детально этот алгоритм:
ДекодированныйТекст = "";
ТекущийУзел = КореньДерева;
Для сч = 1 по СтрДлина(ЗакодированнаяСтрока) Цикл
Направление = Сред(ЗакодированнаяСтрока, сч, 1);
Если Направление = "0" Тогда
ТекущийУзел = ТекущийУзел.Левый;
ИначеЕсли Направление = "1" Тогда
ТекущийУзел = ТекущийУзел.Правый;
КонецЕсли;
// Проверяем, является ли узел листом дерева
Если ТекущийУзел.Левый = Неопределено И ТекущийУзел.Правый = Неопределено Тогда
ДекодированныйТекст = ДекодированныйТекст + ТекущийУзел.Символ;
ТекущийУзел = КореньДерева; // Возвращаемся наверх для поиска следующего символа
КонецЕсли;
КонецЦикла;
Описанный выше алгоритм часто создается в учебных целях, где данные выводятся на экран в виде псевдобинарной текстовой строки вроде "010111". Однако в реальной жизни строка из символов "0" и "1" весит больше оригинала, ведь каждый символ в ней занимает от 8 до 16 бит памяти.
Чтобы выполнить настоящее физическое сжатие в современных версиях платформы 1С (начиная с версии 8.3.13), рекомендуется использовать двоичные данные и побитовые операции. С их помощью текстовую последовательность нулей и единиц можно упаковать в реальные байты:
БуферДвоичныхДанных для выделения памяти под байты.УстановитьБит() или побитовый сдвиг ПобитовыйСдвигВлево() совместно с логическим ПобитовоеИли() для упаковки группы из 8 текстовых символов "0" и "1" в один реальный байт информации.ЗаписьДанных.Такой подход позволяет создавать полноценные, работающие архиваторы непосредственно силами встроенного языка 1С без привлечения внешних библиотек и утилит.