Сжатие текстовых файлов методом Хаффмана на русском языке

Суть работы сводится к программной реализации кодирования Хаффмана и расчету коэффициента сжатия для двух принципиально разных типов текстов на русском языке. Базовый принцип метода заключается в замене стандартных байтовых кодов на битовые цепочки переменной длины. Чем чаще буква встречается в тексте, тем более короткий код она получает. Для расшифровки без разделителей полученный код должен обладать свойством префиксности, когда ни одно кодовое слово не совпадает с началом другого.

Математическая основа и построение бинарного дерева

В теоретической части покажи, как именно вычисляется энтропия источника сообщений по формуле Шеннона. Это позволит определить теоретический предел сжатия текста без потерь. Разбери механику работы с очередью с приоритетами или кучей. В них последовательно объединяются узлы с минимальными весами до образования единого бинарного дерева. Проиллюстрируй этот шаг конкретной таблицей частот фрагмента из 10–15 букв, построив для них граф с листьями на бумаге или в виде векторной диаграммы.

Программная реализация алгоритма и сериализация таблицы

Проектный блок требует рабочего кода на Python, C++ или другом объектно-ориентированном языке. Обязательно опиши три этапа работы программы: подсчет частот каждого символа, генерацию кодовой таблицы путем обхода полученного дерева и битовую упаковку исходного текста. Отдельно покажи алгоритм декомпрессии. Файл должен не просто уменьшаться в оперативной памяти, но и корректно распаковываться обратно в исходный текст без потери данных.

Сравнительный эксперимент на прозе и техническом тексте

Практическую ценность работе придает эксперимент с русскоязычными исходниками разного характера. Возьми фрагменты художественной прозы и специализированные технические статьи объемом от 50 до 500 килобайт. Художественный стиль отличается богатой лексикой и плавным частотным распределением, близким к распределению классического корпуса русского языка. Технический текст насыщен узкой терминологией, формульными обозначениями, цифрами и знаками препинания, что резко меняет форму дерева Хаффмана.

• Рассчитай исходный размер текстовых файлов в кодировке UTF-8 и Windows-1251 перед запуском сжатия.
• Замерь размер полученного бинарного файла с учетом заголовка, хранящего структуру дерева кодов.
• Вычисли коэффициент сжатия как отношение исходного объема к полученному и процент экономии места.
• Сопоставь частотные профили букв 'о', 'е', 'а' в обоих текстах с академическими данными Национального корпуса русского языка.

Критерии оценки преподавателем

Учитель информатики будет проверять корректность битовых операций. Метод Хаффмана формирует битовые последовательности, но файловые системы пишут информацию байтами. Если программа записывает биты в виде символьных строк из нулей и единиц, файл вырастет в восемь раз вместо сжатия. Преподаватель обязательно оценит правильность упаковки битов в байты через побитовые сдвиги и маски, а также точность сохранения служебной информации, необходимой для распаковки архива.

Источники данных и текстовые материалы

Для теоретической базы используй классический труд Томаса Кормена 'Алгоритмы. Построение и анализ', где детально разобран жадный выбор при построении дерева. Частотность букв русского алфавита возьми из частотного словаря Ольги Ляшевской и Сергея Шарова, созданного на базе Национального корпуса русского языка. В качестве прозы отлично подойдут главы из произведений Льва Толстого или Ивана Тургенева. Для технического корпуса используй ГОСТы, фрагменты документации по языкам программирования или руководства по эксплуатации оборудования.