Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.
Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.
Результат поиска
Наименование:
Курсовик «Реализация кодирования информации методом Фано»
Информация:
Тип работы: Курсовик.
Добавлен: 22.12.2013.
Страниц: 27.
Уникальность по antiplagiat.ru: < 30%
Описание (план):
Введение 3 Разработка программы 3 Модель и метод решения задачи 3 Описание структуры данных 6 Алгоритм решения задачи 7 Руководство пользователя 8 Руководство программиста 10 Тестирование программы и его результаты 12 Выводы 13 Листинг 13
Введение Программа - «Код Фано» должна представлять собой программный продукт, отвечающий ряду требований. Данная программа должна отвечать требованиям, поставленным кафедрой ИВТ к курсовым работам студентов второго курса и иметь удобный интерфейс для работы. Также работа должна сопровождаться отчетом в 15 страниц (без листинга) документа MSWord, содержащим рекомендации по применению, руководство программиста и анализ проделанной работы. Программа должна: · Обеспечить реализацию кодирования текстового файла методом Фано. Под кодируемыми сообщениями подразумеваются отдельные слова, записанные в предварительно созданный текстовый файл. · Реализовать удобный интерфейс, позволяющий выбирать файлы, подлежащие кодированию. · Позволять осуществлять просмотр файла в закодированном виде, и после декодирования. · Предусмотреть вывод на экран закодированного файла в виде набора из нулей и единиц. · Подсчитать степень сжатия. · Частотный словарь организовать с помощью дерева бинарного поиска. Данная программа была реализована в среде программирования Borland C++ Builder 6. Разработка программы Модель и метод решения задачи Код Фано. При кодировании по методу Фано все сообщения записываются в таблицу по степени убывания вероятности и разбиваются на две группы примерно (насколько это возможно) равной вероятности. Соответственно этой процедуре из корня кодового дерева исходят два ребра, которым в качестве весов присваиваются полученные вероятности. Двум образовавшимся вершинам приписывают кодовые символы 0 и 1. Затем каждая из групп вероятностей вновь делится на две подгруппы примерно равной вероятности. В соответствии с этим из каждой вершины 0 и 1 исходят по два ребра с весами, равными вероятностям подгрупп, а вновь образованным вершинам приписывают символы 00 и 01, 10 и 11. В результате многократного повторения процедуры разделения вероятностей и образования вершин приходим к ситуации, когда в качестве веса, приписанного ребру бинарного дерева, выступает вероятность одного из данных сообщений. В этом случае вновь образованная вершина оказывается листом дерева, т.к. процесс деления вероятностей для нее завершен. Задача кодирования считается решенной, когда на всех ветвях кодового бинарного дерева образуются листья. Пример. Закодировать по Фано сообщения, имеющие следующие вероятности: сообщение 1 2 3 4 5 6 7 вероятность 0,4 0,2 ,1 0,1 0,1 0,05 0,05 Решение 1 (с использованием кодового дерева)
Рис. 1 Листья кодового дерева представляют собой кодируемые сообщения с присвоенными им кодовыми словами. Решение 2 (табличный способ)
Частотный словарь. Пусть задана некоторая последовательность значений, которые могут повторяться. Необходимо подсчитать, сколько раз каждое значение входит в последовательность. Иначе говоря, нужно построить частотный словарь. (Например, для заданного текста подсчитать, сколько раз входит в него каждое из слов).Если диапазон возможных значений в последовательности конечен и не слишком велик, то это можно сделать с помощью массива, каждый элемент которого представляет собой счетчик для соответствующего значения. Для каждого очередного значения последовательности увеличивается значение его счетчика. Однако если диапазон возможных значений бесконечен или конечен, но слишком велик (например, количество разных слов в тексте), то мы не можем использовать массив, так как неизвестна его длина. В этом случае задача построения частотного словаря может быть решена с помощью дерева поиска. К каждому узлу дерева добавляется поле счетчика. Для каждого очередного значения в последовательности осуществляется его поиск в дереве. Если такого значения в дереве еще нет (то есть оно встретилось в первый раз), в дереве создается узел, полю счетчика которого присваивается значение 1. Если узел с таким значением найден (значение встретилось уже не в первый раз), то поле счетчика этого узла увеличивается на 1. После завершения последовательности значений можно выполнить b-обход построенного дерева, распечатывая для каждого узла его значение и величину счетчика, в результате чего получим отсортированный частотный словарь. Рассмотрим процедуру построения такого дерева на примере подсчета частного словаря символов некоторого текста. (Конечно, такую задачу можно решить и с помощью массива, так как количество разных символов в тексте конечно и невелико, но для примера рассмотрим ее решение с помощью дерева поиска). Например, для последовательности символов фразы ‹построение частотного словаря› (без учета пробелов) будет построено следующее дерево:
Выполнив b-обход этого дерева, получим частотный словарь: Символ а в г е и л н о п р с т ч я Частота 2 1 1 2 1 1 6 1 2 3 3 1 1 Описание структуры данных
В этой программе входными данными является слова, записанные в текстовом файле. Для кодирования использовался бинарное дерево. Для этого было создано структура code_F. struct code_F { int ca; // частота AnsiString word; // слово AnsiString code; // код code_F *left, *right; // указатели на правый и левый сыновья int begin, end;
};
И структура для построения частотного словаря. struct tree_F { int count, number; AnsiString word; //слово AnsiString code; //код tree_F *left, *right; // указатели };
Алгоритм решения задачи Для выполнения кодирования информации методом Фано в данной работе кодируемыми сообщениями были отдельные слова, записанные в текстовом файле. Алгоритм кодирования: 1. Открывается текстовый файл и считывается все ...