Сжатие текста
жүктеу/скачать 130,54 Kb.
|
Ðнализ пÑедмеÑной облаÑÑи
- Бұл бет үшін навигация:
- 1 Формулирование требований Описание программы
- Функции, выполняемые программой
- Поиск файла Программа должна найти файл по названию которое указал пользователь Анализ содержимого файла
- Сохранение информации в архивном файле Программа должна сохранить сжатую информацию в архивном файле 1.2.5 Восстановление исходного текста
- Входные и выходные данные
- 1.4 Пользовательский интерфейс
- 2. Анализ предметной области
- 2.1 Сжатие исходного текста
- 2.2 Восстановление сжатого текста
- 2.3 Список использованных источников
|
Министерство науки и высшего образования РФ ФГАОУ ВПО Национальный исследовательский технологический университет «МИСиС» Институт Информационных технологий и компьютерных наук (ИТКН) Кафедра Инфокоммуникационных технологий (ИКТ)
Исполнители:
Проверил: ст. преп. каф. ИКТ Карпишук А.В. _____________ Москва, 2021 1 Формулирование требований Описание программы Пользователь указывает файл, содержащий большой объем текста. Программа осуществляет сжатие информации, сохранение ее в архивном файле и последующее восстановление исходного текста из архива. Функции, выполняемые программой Программа должна реализовывать следующие возможности: Поиск файла ; Анализ содержимого файла; Сжатие информации; Сохранение информации в архивном файле ; Восстановление исходного текста; Поиск файла Программа должна найти файл по названию которое указал пользователь Анализ содержимого файла Программа должна изучить содержимое файла и убедится что там только текст Сжатие информации Программа должна осуществить сжатие информации содержащиеся в файле Сохранение информации в архивном файле Программа должна сохранить сжатую информацию в архивном файле 1.2.5 Восстановление исходного текста Программа должна восстановить исходный текст , используя созданный архивный файл Входные и выходные данные Входные данные файла вместе с сжатым архивным файлом сохраняются на диске в отдельных специальных папках. Программа должна сканировать содержимое папки для сжатия или восстановления исходного текста. Содержимое файла – Исходный или сжатый текст из файла указанного пользователем . 1.4 Пользовательский интерфейс Примерный внешний вид основных окон программы приведен на рис. 1.1-1.3 Рис. 1.1-Окно ввода названия файла для поиска Рис. 1.2- Окно ошибки , возникающие если файл не отвечает требованиям Рис. 1.3.-Окно восстановления исходного текста из архивного файла 2. Анализ предметной области Опираясь на описанные в первом разделе функциональные возможности будущей программы, можно выделить основные задачи, требующие предварительного исследования: Сжатие исходного текста Восстановление сжатого текста Рассмотрим каждую задачу отдельно 2.1 Сжатие исходного текста Для сжатия текста мы будем пользоваться алгоритмом 1) «Хаффмана». Идея, положенная в основу кодировании Хаффмана, основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает новый очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код. Это нужно, так как мы хотим, чтобы, когда мы обработали весь ввод, самые частые символы заняли меньше всего места (и меньше, чем они занимали в оригинале), а самые редкие — побольше (но так как они редкие, это не имеет значения). Предположим, у нас есть строка «beep boop beer!», для которой, в её текущем виде, на каждый знак тратится по одному байту. Это означает, что вся строка целиком занимает 15*8 = 120 бит памяти. После кодирования строка займёт 40 бит. Чтобы получить код для каждого символа на основе его частотности, нам надо построить бинарное дерево, такое, что каждый лист этого дерева будет содержать символ (печатный знак из строки). Дерево будет строиться от листьев к корню, в том смысле, что символы с меньшей частотой будут дальше от корня, чем символы с большей. Чтобы построить дерево, мы воспользуемся слегка модифицированной очередью с приоритетами — первыми из неё будут извлекаться элементы с наименьшим приоритетом, а не наибольшим. Это нужно, чтобы строить дерево от листьев к корню. Для начала посчитаем частоты всех символов: Рисунок 1.4 – кодирование символов После вычисления частот создадется узел бинарного дерева для каждого знака и добавление их в очередь, используя частоту в качестве приоритета: Рисунок 1.5 – создание узла бинарного дерева Теперь мы достаём два первых элемента из очереди и связываем их, создавая новый узел дерева, в котором они оба будут потомками, а приоритет нового узла будет равен сумме их приоритетов. После этого мы добавим получившийся новый узел обратно в очередь. Рисунок 1.6-создание нового узла После чего все эти шаги повторяются последовательно. Рисунок 1.7-итоговое дерево Теперь, чтобы получить код для каждого символа, надо просто пройтись по дереву, и для каждого перехода добавлять 0, если мы идём влево, и 1 — если направо: Рисунок 1.8-закодированное дерево Рисунок 1.9-итоговая таблица с закодированными символами Чтобы расшифровать закодированную строку, нам надо, соответственно, просто идти по дереву, сворачивая в соответствующую каждому биту сторону до тех пор, пока мы не достигнем листа. При реализации данного алгоритма сразу после построения дерева строится таблица Хаффмана. Данная таблица — это по сути связный список или массив, который содержит каждый символ и его код, потому что это делает кодирование более эффективным. Довольно затратно каждый раз искать символ и одновременно вычислять его код, так как мы не знаем, где он находится, и придётся обходить всё дерево целиком. Как правило, для кодирования используется таблица Хаффмана, а для декодирования — дерево Хаффмана. Входная строка: «beep boop beer!» Входная строка в бинарном виде: «0110 0010 0110 0101 0110 0101 0111 0000 0010 0000 0110 0010 0110 1111 0110 1111 0111 0000 0010 0000 0110 0010 0110 0101 0110 0101 0111 0010 0010 000» Закодированная строка: «0011 1110 1011 0001 0010 1010 1100 1111 1000 1001» 2.2 Восстановление сжатого текста Для восстановления сжатого текста нужно воспользоваться таблицей , с закодированными символами , после чего декодировать строку . 2.3 Список использованных источников 1. Пример алгоритма https://www.cyberforum.ru/csharp-beginners/thread1845788.html 2.Объяснение без практической части https://habr.com/ru/post/438512/ 3. Объяснение с парктической частьюhttps://habr.com/ru/post/144200/ 4. Еще один пример алгоритма без листингаhttps://www.nookery.ru/coding-by-huffman-algorithm-using-a-dictionary-in-c/ 5. Пример алгоритма с листингом и объяснением https://studassistent.ru/charp/algoritm-haffmana-realizaciya-c жүктеу/скачать 130,54 Kb. Достарыңызбен бөлісу:
|