Сравнительный анализ алгоритма Хаффмана и арифметического кодирования: вычислительная сложность и коэффициент сжатия на гетерогенных данных

Аннотация

В статье представлен сравнительный анализ двух классических алгоритмов сжатия данных без потерь: кодирования Хаффмана и арифметического кодирования. Целью исследования является оценка вычислительной сложности и эффективности компрессии данных (коэффициента сжатия) при обработке гетерогенных данных, включающих русский текст, числовые последовательности, случайные и повторяющиеся паттерны, а также смешанные форматы. Практическая часть реализована на языке Python 3.12, где проведено моделирование и тестирование обоих алгоритмов на различных типах данных с измерением времени выполнения и степени сжатия. Результаты эксперимента демонстрируют, что арифметическое кодирование обеспечивает существенно более высокий коэффициент сжатия на всех типах данных (в среднем более чем в 4 раза выше), однако обладает значительно большей вычислительной сложностью, особенно заметной при увеличении объёма данных. Алгоритм Хаффмана, напротив, показывает высокую скорость работы и слабую зависимость времени выполнения от размера данных, что делает его предпочтительным для систем реального времени и встроенных приложений. На основе проведённого анализа сформулированы практические рекомендации по выбору алгоритма в зависимости от требований конкретной задачи: максимальная компрессия или высокая производительность. Также обоснована перспективность разработки адаптивных и гибридных систем, способных динамически выбирать оптимальный метод сжатия на основе предварительного анализа характеристик входного потока данных.