|
ГЛАВНАЯ
> Вернуться к содержанию
Программные системы и вычислительные методы
Правильная ссылка на статью:
Горяинов С.И.
Перестройка бинарных деревьев в алгоритме Хаффмана
// Программные системы и вычислительные методы.
2014. № 4.
С. 464-471.
DOI: 10.7256/2454-0714.2014.4.13755 URL: https://nbpublish.com/library_read_article.php?id=13755
Перестройка бинарных деревьев в алгоритме Хаффмана
Горяинов Сергей Игоревич
студент, кафедра Миасский филиал, Челябинский государственный университет
456323, Россия, Челябинская область, г. Миасс, ул. Малышева, 13
Goryainov Sergei Igorevich
456323, Russia, Chelyabinskaya oblast', g. Miass, ul. Malysheva, 13
|
goryainovsergey@gmail.com
|
|
 |
|
DOI: 10.7256/2454-0714.2014.4.13755
Дата направления статьи в редакцию:
30-12-2014
Дата публикации:
13-01-2015
Аннотация:
Предметом данного исследования является время, затрачиваемое на полную перестройку бинарного дерева, а также степень сжатия текста в алгоритме Хаффмана. В работе определяются зависимости времени работы программы и степени сжатия текста от длины строки при произвольном количестве уникальных символов, при фиксированном количестве уникальных символов, а также при фиксированной длине строки и различном количестве уникальных символов. Показано, что время, требуемое на перестройку бинарного дерева, составляет незначительную часть общего времени работы программы. Алгоритм построения кодов символов включает следующие этапы: 1) считывание файла, содержащего текст; 2) подсчёт частот различных символов текста; 3) заполнение массивов данных и их сортировка; 4) построение бинарного дерева. В ряде источников утверждается, что подход, использующий полную перестройку бинарного дерева неэффективен. Однако это утверждение не подкреплено соответствующими фактами. В данной работе с помощью анализа текстов различной длины и количеством уникальных символов, представленного в табличном и графическом виде, показано, что перестройка бинарного дерева незначительно влияет на время работы программы.
Ключевые слова:
алгоритм Хаффмана, перестройка бинарного дерева, сжатие текстовых данных, время работы программы, экономное кодирование информации, префиксное кодирование, уникальные символы, степень сжатия текста, длина входной строки, средняя ошибка аппроксимации
Библиография
1. Александров О.Е. Компрессия данных или измерение и избыточность информации. Метод Хаффмана: Методические указания к лабораторной работе / О. Е. Александров – Екатеринбург: УГТУ–УПИ, 2000. – 36 с.
2. Кудряшов Б.Д. Теория информации: Учебник для вузов. – СПб.: Питер, 2009. – 320 с.: ил. – (Серия «Учебник для вузов»)
3. Колмогоров А.Н. Теория информации и теория алгоритмов. – М.: Наука, 1987. – 304 с.
4. Свирид Ю.В. Основы теории информации: Курс лекций. – Мн.: БГУ, 2003. – 139 с.
5. Смирнов М.А. Обзор применения методов безущербного сжатия данных в СУБД: Рукопись. – СПб.: ГУАП, 2004. – 58 с.
6. Шеннон К. Работы по теории информации и кибернетике. – М.: Издательство иностранной литературы, 1963. – 825 с
References
1. Aleksandrov O.E. Kompressiya dannykh ili izmerenie i izbytochnost' informatsii. Metod Khaffmana: Metodicheskie ukazaniya k laboratornoi rabote / O. E. Aleksandrov – Ekaterinburg: UGTU–UPI, 2000. – 36 s.
2. Kudryashov B.D. Teoriya informatsii: Uchebnik dlya vuzov. – SPb.: Piter, 2009. – 320 s.: il. – (Seriya «Uchebnik dlya vuzov»)
3. Kolmogorov A.N. Teoriya informatsii i teoriya algoritmov. – M.: Nauka, 1987. – 304 s.
4. Svirid Yu.V. Osnovy teorii informatsii: Kurs lektsii. – Mn.: BGU, 2003. – 139 s.
5. Smirnov M.A. Obzor primeneniya metodov bezushcherbnogo szhatiya dannykh v SUBD: Rukopis'. – SPb.: GUAP, 2004. – 58 s.
6. Shennon K. Raboty po teorii informatsii i kibernetike. – M.: Izdatel'stvo inostrannoi literatury, 1963. – 825 s
Ссылка на эту статью
Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также
попробовать найти похожие
статьи
|
|
