WWW.LIB.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные матриалы
 

«Факультет СС, СК и ВТ Дипломная работа на тему «Исследование эффективности сжатия текстовых документов модифицированным кодом Хаффмана» Дипломник Панферова ...»

САНКТ-ПЕТЕРБУРГСКИЙ

ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ

им. проф. М. А. БОНЧ-БРУЕВИЧА

Факультет СС, СК и ВТ

Дипломная работа

на тему

«Исследование эффективности сжатия текстовых документов

модифицированным кодом Хаффмана»

Дипломник Панферова М.А.

Руководитель работы Доронин Е.М.

Санкт-Петербург

2010 г.

РЕФЕРАТ

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

Дипломная работа содержит 65 страниц, 25 рисунков и 11 таблиц.

Ключевые слова: Дэвид Хаффман, оптимальное неравномерное кодирование длин серий, модифицированный код Хаффмана, сжатие документов, эффективность применения модифицированного кода Хаффмана, код Хаффмана-Панферовой, эффективность кода ХаффманаПанферовой, модифицированный факсимильный аппарат, алгоритмы приема-передачи факсимильных сообщений для модифицированного факсимильного аппарата.

Цель работы – сделать выводы об эффективности применения модифицированного кода Хаффмана для сжатия документов, которые различаются как содержанием, так и языковым алфавитом, и предложить алгоритмы приема-передачи документов с обработкой их по индивидуальным кодовым таблицам.

В результате проведенных исследований было выявлено, что модифицированный код Хаффмана позволяет сжимать документы в среднем с коэффициентом – 27, и код не чувствителен к языку, на котором составлен документ, предназначенный для передачи.

Предложен алгоритм кодирования на основе построения дерева Хаффмана, сжимающий документ до 72% от его общего объема, но время передачи такого документа на современном этапе развития микропроцессорной техники может составить 3,7 минуты, что не соответствует требованиям Рекомендации Т.4 для ЦФА G3.

СОДЕРЖАНИЕ Введение………………………………………………………………………. 4 Раздел 1. Экспериментальное исследование эффективности сжатия документов на основе оптимального неравномерного кодирования длин серий…………………………………………... 9

1.1. Постановка задачи на исследование…………………………… 9

1.2. Состав аппаратных и программных средств для проведения исследования…………………………………………………………. 10

1.3. Первая часть эксперимента ……………………………………. 11

1.4. Вторая часть эксперимента ……………………………………. 12 Раздел 2. Исследование эффективности сжатия документов, выбранных Хаффманом для построения модифицированного кода……….. 14 Раздел 3. Исследование эффективности сжатия документов, выбранных в дипломной работе………………………………………………… 19 Раздел 4. Анализ эффективности применения модифицированного кода Хаффмана для текстовых документов, составленных на разных языках ……………………………………………………………... 23

4.1. Результаты обработки документов, составленных на разных языках………………………………………………………………… 23

4.2. Обоснование полученных результатов………………………… 30 Раздел 5. Модифицированный код Хаффмана-Панферовой……………. 42

5.1. Построение кода……………………………………………….. 42

5.2. Исследование эффективности применения кода ХаффманаПанферовой для различных документов…………………………… 48

5.3. Блок-схема модифицированного факсимильного аппарата.

Алгоритмы приема-передачи факсимильных сообщений………… 51 Заключение……………………………………………………………………. 60 Список использованных источников……………………………………….. 63 ВВЕДЕНИЕ Сегодня, когда современные технологии связи стремительно меняют одна другую, число компаний, использующих для связи факсимильные аппараты (ФА), и общий объем передаваемых документов с помощью давно проверенной технологии ежегодно растет. Это связано с удобством, простотой и доступностью данного вида передачи информации.

В настоящее время применяется цифровые факсимильные аппараты (ЦФА) группы G3. ЦФА рассматривают изображение как набор дискретных элементов (пикселей). Каждый пиксель может быть или черным (ему соответствует двоичная 1) или белым (двоичный 0). Последовательность двоичных цифр, вырабатываемая при оцифровке изображения, может быть сжата, передана по каналу связи и проконтролирована на наличие ошибок с использованием любых методов, применяемых в модемах.

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

Дэвид Хаффман родился 9 августа1925 года в штате Огайо (Ohio), США.

Хаффман получил степень бакалавра электротехники в государственном университете Огайо (Ohio State University) в возрасте 18 лет. Затем он служил в армии офицером поддержки радара на эсминце, который помогал обезвреживать мины в японских и китайских водах после Второй мировой войны. Впоследствии он получил степень магистра в университете Огайо и степень доктора в Массачусетском Институте Технологий (Massachusetts Institute of Technology - MIT). Хотя Хаффман больше известен за разработку метода построения минимально-избыточных кодов, он так же сделал важный вклад во множество других областей (по большей части в электронике). Он долгое время возглавлял кафедру Компьютерных Наук в MIT.

В 1952 году Дэвид Хаффман создал алгоритм префиксного кодирования с минимальной избыточностью (известный как алгоритм или код Хаффмана).

В 1974, будучи уже заслуженным профессором, он подал в отставку.

Хаффман получил ряд ценных наград. В 1999 - медаль Ричарда Хэмминга от Института Инженеров Электричества и Электроники (Institute of Electrical and Electronics Engineers - IEEE) за исключительный вклад в Теорию информации, медаль Louis E. Levy от Франклинского Института (Franklin Institute) за докторскую диссертацию о последовательно переключающихся схемах. Награду W. Wallace McDowell, награду от Компьютерного Сообщества IEEE, Золотую юбилейную награду за технологические новшества от IEEE в 1998 году и др.

В октябре 1999 года, в возрасте 74 лет Дэвид Хаффман скончался от рака [1].

При разработке модифицированного кода Хаффманом было построено вероятностное распределение серий черных и белых элементов для восьми эталонных документах (табл. В1), которые содержали типичные тексты с изображениями, обычно посылаемые по факсу [2, 3].

Табл. В1. Список эталонных документов Типичное деловое письмо на английском Рисунок электрической цепи (от руки)

–  –  –

Было обнаружено, что чаще всего встречаются серии из 2, 3 и 4 черных элементов, поэтому, им были присвоены самые короткие коды (табл. В2).

Потом шли серии из 2-7 белых элементов, которым были присвоены несколько более длинные коды. Большинство же остальных длин серии встречались реже, и им были назначены длинные, 12-битные коды.

Интересно отметить, что строке из 1664 белых элементов был присвоен короткий код 011000. Дело в том, что при сканировании часто попадаются пустые строки, которым соответствует это число элементов.

Поскольку длина серии одинаковых элементов может быть большой, алгоритм Хаффмана был модифицирован. Сначала коды были приписаны остаткам — сериям длины от 1 до 63 элементов (они показаны в табл. В2).

Другие коды были даны сериям, длины которых кратны 64 (они приведены в табл. В3) [10].

–  –  –

Таким образом, каждый код соответствует либо короткой остаточной серии длины до 64, либо длинной серии, кратной 64.

Заметим, что разные коды были также присвоены пустым сериям белых и черных элементов. Эти коды необходимы, чтобы обозначить серии, длины которых равны 64, 128 или любому числу, кратному 64. Следует отметить, что серии длины 2561 быть не может, так как в строке длиной 8,5 дюймов помещается только 1728 элементов. Поэтому коды для более длинных серий не нужны. Однако могут быть (или появятся в будущем) ФА для широкой бумаги, поэтому коды для ФА Group 3 были созданы с учетом этой возможности.

Каждая строка элементов кодируется отдельно, заканчиваясь специальным 12-битным EOL-кодом 000000000001. К каждой строке также добавляется слева один белый элемент. Это делается для того, чтобы избежать неопределенности в декодировании при получении конца.

Прочитав код EOL для предыдущей строки, приемник знает, что новая строка начнется с одного белого элемента, и игнорирует первый из них.

Заметим, что коды из Табл. В2 должны удовлетворять свойству префикса только в каждом столбце. Дело в том, что каждая отсканированная строка начинается белым элементом, и декодер знает, какого цвета будет следующая серия. Примером нарушения свойства префикса служит код для пяти черных элементов (0011), которым начинаются коды белых серий длины 61, 62 и 63.

Коды для ФА Group 3 не могут исправлять ошибки, но они могут обнаружить многие из них. Дело в том, что даже один плохо переданный бит вынудит приемник потерять синхронизацию и породить последовательность неправильных элементов. Поэтому последовательные строки следует кодировать независимо друг от друга. Если декодер обнаруживает ошибку, он пропускает биты, разыскивая EOL. При таком методе одиночная ошибка может испортить не более одной строки. Если декодер не может долгое время обнаружить EOL, он предполагает высокую зашумленность канала и прерывает процесс, сообщая об этом передатчику. Поскольку длины кодов лежат в диапазоне от 2 до 12, то приемник обнаруживает ошибку, если он не в состоянии выявить правильный код, прочитав 12 бит.

В начале каждой страницы передается код EOL, а в конце страницы передается шесть кодов EOL. Поскольку все строки кодируются независимо, эта схема называется схемой одномерного кодирования. Коэффициент сжатия зависит от передаваемого изображения. Если оно состоит из крупных соприкасающихся белых и черных областей (текст, таблицы или графики), то он будет сильно сжат. А изображения, в которых присутствует много коротких серий, могут вызвать отрицательное сжатие. Это может случиться при передаче полутоновых изображений, например, фотографий. Такие изображения при сканировании порождают множество коротких элементов длины 1 или 2.

Рекомендация Т.4 допускает добавление нулевых бит между кодом данных и кодом EOL.

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

1. Экспериментальное исследование эффективности сжатия документов на основе оптимального неравномерного кодирования длин серий

1.1. Постановка задачи на исследование Для того чтобы сделать выводы об эффективности применения модифицированного кода Хаффмана, необходимо провести несколько экспериментов.

Исследуем вначале документы, которые выбрал Хаффман для проведения своих экспериментов, по результатам которых был построен модифицированный код (табл. В1).

Затем исследуем эффективность модифицированного кода для рисунков, графиков и русского текста. Возьмем следующие документы.

Табл. 1.1. Список документов для исследования Рисунок «Шахматная доска»

Плотный русский текст Таблица Русский текст и рисунок Текст в виде заявления Рисунок с большим содержанием белого Рисунок с большим содержанием черного

1.2. Состав аппаратных и программных средств для проведения исследования В качестве аппаратных средств использованы сканер МФУ HP PSC 1410 и ноутбук MacBook c OC Windows XP (рис.1.1).

Многофункциональное устройство МФУ HP PSC выполняет функции сканера и принтера, а также может использоваться в качестве копира даже без подключения к компьютеру.

HP PSC 1410 прост в установке, настройке и работе. Скорость печати и копирования достигает 18 страниц в минуту в черно-белом режиме и 13 в цветном. Планшетный сканер МФУ HP PSC обеспечивает разрешение 6002400 точек на дюйм с глубиной цвета 36 бит.

–  –  –

Характеристики персонального компьютера MacBook.

Процессор Core 2 Duo 2400 МГц.

Установленная операционная система Windows XP.

Тип графического контроллера – встроенный.

Оптический привод DVD-RW, внутренний.

Беспроводная связь – Bluetooth, Wi-Fi 802.11n.

Размеры (ДШТ) – 32522727.5 мм.

Память – 2048 Мб DDR2 667 МГц.

Дисплей – 13.3 дюймов, 1280x800, широкоформатный.

Графический чипсет – Intel GMA X3100.

Жесткий диск – 250 Гб Serial ATA.

Аккумулятор Li-Pol.

Вес 2.2 кг.

Для соединения ПК МФУ используется USB-кабель.

Рис. 1.2. USB-кабель для подключения МФУ к ПК

Состав программных средств:

1. Операционная система Windows XP

2. Программа обработки и анализа результатов на Visual C++

3. Программа PhotoShop CS4

4. Редактора PaintNet

1.3. Первая часть эксперимента В 1-ой части эксперимента требуется отсканировать изображение и сохранить его в формате для дальнейшего преобразования.

*.bmp Сканирование производилось с разрешением 209 dpi ч/б, что соответствует ч/б изображению с разрешением 17282376, т.е. стандарту 8 строк на миллиметр.

Затем с помощью программы Above Photoshop V8.0 была произведена перекодировка изображения в формат *.wbmp. Также с помощью этой программы было получено изображение с расширением 1728х1188, что соответствует стандарту 4 строки на миллиметр.

На языке С++ был написан код, необходимый для преобразования изображения в последовательность 0 и 1. Программа читает бинарный код изображения и записывает его в виде текстового файла.

Пример:

Рис. 1.3. Изображение и код, записанный в файле в формате *.wbmp Полученный файл будет использован для обработки во второй части эксперимента.

1.4. Вторая часть эксперимента Вторая часть работы заключается в преобразовании ранее полученного файла в формат, пригодный для кодирования и собственно само кодирование, и вычисление среднего коэффициента сжатия. Для этого на

Visual C++6.0 была написана программа. Интерфейс программы имеет вид:

Рис. 1.4. Интерфейс программы для обработки и кодирования изображений Рис. 1.5. Пример результатов работы программы при обработке документа Преобразованный документ сохраняется в файл new.txt, который можно загружать для сжатия. Результаты проделанной работы приведены ниже.

Для отладки программы были выбраны три тестовых изображения:

полностью белое, полностью черное и изображение с двумя белыми и черными вертикальными полосами. Результаты машинной обработки по программе полностью совпали с результатами ручного расчета. Так, для полностью белого изображения коэффициент сжатия равен 63, для полностью черного изображения – 42, для третьего тестового изображения коэффициент сжатия – 13.

2. Исследование эффективности сжатия документов, выбранных Хаффманом для построения модифицированного кода Размер документов 17282376, разрешение по вертикали – 8 строк на миллиметр.

1. Типичное деловое письмо на английском (ftp://nic.funet.fi/pub/graphics/misc/test-images/):

Коэффициент сжатия – 42.646

2. Рисунок электрической цепи, выполненный от руки:

Коэффициент сжатия – 22.81

3. Печатная форма, заполненная на машинке на французском:

Коэффициент сжатия – 18.218

4. Плотно напечатанный отчет на французском:

Коэффициент сжатия – 24.125

5. Техническая статья с иллюстрациями на французском:

Коэффициент сжатия – 18.231

6. График с напечатанными подписями на французском:

Коэффициент сжатия – 20.845

7. Плотный документ:

Коэффициент сжатия – 15.689 Рис. 2.1. Интерфейс программы обработки отсканированного документа №7

8. Рукописная записка белым по черному на английском:

Коэффициент сжатия – 12.406

3. Исследование эффективности сжатия документов, выбранных в дипломной работе Размер документов 17281188, разрешение по вертикали – 8 строк на миллиметр.

1. Шахматная доска:

Коэффициент сжатия – 7.205

–  –  –

Коэффициент сжатия – 16.242

3. Таблица:

Коэффициент сжатия – 19.859

4. Русский текст и рисунок:

Коэффициент сжатия – 28.965

5. Текст в виде заявления:

Коэффициент сжатия – 49.296

6. Рисунок с большим содержанием белого:

Коэффициент сжатия – 14.146

7. Рисунок с большим содержанием черного:

Коэффициент сжатия – 10.520

4. Анализ эффективности применения модифицированного кода Хаффмана для текстовых документов, составленных на разных языках

4.1. Результаты обработки документов, составленных на разных языках Для проведения данного эксперимента был использован один и тот же текст, переведенный на разные языки, что позволило получить более «чистые» результаты исследования.

1. Документ, составленный на русском языке:

Рис. 4.1. Обработка отсканированного документа на русском языке Коэффициент сжатия – 23.289

2. Документ, составленный на английском языке:

Коэффициент сжатия – 19.621

3. Документ, составленный на датском языке:

Коэффициент сжатия – 19.195

4. Документ, составленный на итальянском языке:

Коэффициент сжатия – 20.558

5. Документ, составленный на французском языке:

Коэффициент сжатия – 19.993

6. Документ, составленный на испанском языке:

Коэффициент сжатия – 20.388

7. Документ, составленный на корейском языке:

Коэффициент сжатия – 32.169

8. Документ, составленный на японском языке:

Коэффициент сжатия – 22.548

9. Документ, составленный на китайском языке:

Коэффициент сжатия – 25.160

10. Документ, составленный на голландском языке:

Коэффициент сжатия – 20.213

11. Документ, составленный на арабском языке:

Коэффициент сжатия – 12.532

12. Документ, составленный на немецком языке:

Коэффициент сжатия – 20.628

13. Документ, составленный на финском языке:

Коэффициент сжатия – 19.912 Итоговая сопоставительная таблица результатов сжатия текстов, составленных на различных языках:

Табл. 4.1. Коэффициент сжатия текстовых документов, составленных на разных языках

–  –  –

Выводы: Таким образом, мы получили, что модифицированный код Хаффмана для большинства языков дает приблизительно одинаковый коэффициент сжатия в пределах от 19 до 21, исключение составляют арабский язык, для которого коэффициент сжатия – минимальный среди проанализированных языков – 12,532, а также корейский язык, для которого коэффициент сжатия максимальный – 32,169.

4.2. Обоснование полученных результатов Пример 1. Буква на арабском языке. Исходный размер буквы 4,257,625 мм, так как мы используем разрешение 8 строк на миллиметр, то получим 3461 пикселей.

–  –  –

Всего двоичных символов – 2074.

Количество символов в закодированном виде – 698.

Ксж=2074/698=2.97.

Пример 2. Буква на арабском языке.

Исходный размер буквы 4,6259,375 мм, так как мы используем разрешение 8 строк на миллиметр, то получим 3775 пикселей.

Рис. 4.3. Отсканированная арабская буква (пример 2) Всего двоичных символов – 2775.

Количество символов в закодированном виде – 1434.

Ксж=2775/1434=1.935.

Пример 3. Буква на арабском языке.

Исходный размер буквы 4,6255,625 мм, так как мы используем разрешение 8 строк на миллиметр, то получим 3745 пикселей.

–  –  –

Всего двоичных символов – 1665.

Количество символов в закодированном виде – 898.

Ксж=1665/898=1.854 Пример 4. Буква на корейском языке. Исходный размер буквы 4,8755,375 мм, так как мы используем разрешение 8 строк на миллиметр, то получим 3943 пикселей Рис. 4.5. Отсканированная корейская буква (пример 4)

–  –  –

Всего двоичных символов – 1677.

Количество символов в закодированном виде – 573.

Ксж=1677/573=2.927.

Пример 5. Буква на корейском языке.

Исходный размер буквы 3,55,5 мм, так как мы используем разрешение 8 строк на миллиметр, то получим 2844 пикселей.

–  –  –

Всего двоичных символов – 1232.

Количество символов в закодированном виде – 412.

Ксж=1677/573=2.99.

Пример 6. Буква на корейском языке.

Исходный размер буквы 55 мм, так как мы используем разрешение 8 строк на миллиметр, то получим 4040 пикселей.

Рис. 4.7. Отсканированная корейская буква (пример 6)

–  –  –

Всего двоичных символов – 1600.

Количество символов в закодированном виде – 878.

Ксж=1677/573=1.822.

Пример 7. Буква на русском языке.

Исходный размер буквы – 2,54 мм, так как мы используем разрешение 8 строк на миллиметр, то получим 2032 пикселей.

–  –  –

Всего двоичных символов – 640.

Количество символов в закодированном виде – 540.

Ксж=640/540=1.185.

Пример 8. Буква на русском языке.

Исходный размер буквы – 2,52,375 мм, так как мы используем разрешение 8 строк на миллиметр, то получим 2019 пикселей.

–  –  –

Всего двоичных символов – 380.

Количество символов в закодированном виде – 248.

Ксж=380/248=1.532.

Пример 9. Буква на русском языке.

Исходный размер буквы – 2,52,375 мм, так как мы используем разрешение 8 строк на миллиметр, то получим 2019 пикселей.

–  –  –

Всего двоичных символов – 380.

Количество символов в закодированном виде – 393.

Ксж=380/393=0.967.

Кроме приведенных 9 примеров в работе исследовались и другие буквы алфавитов, результаты исследования представлены в следующей таблице:

Табл. 4.2. Сопоставительная таблица букв различных алфавитов Выводы: при сжатии документов, составленных на различных языках, получены следующие результаты: хуже всего сжимается арабский текст и луче всего корейский. Если анализировать коэффициенты сжатия букв различных алфавитов, то получим, что некоторые буквы арабского алфавита сжимаются хуже, чем буквы корейского. Однако в обоих алфавитах есть буквы, которые плохо сжимаются. Таким образом, проведя ряд экспериментов, мы приходим к выводу о том, что алгоритм сжатия Хаффмана не чувствителен к алфавиту, и средний коэффициент сжатия для документов различного рода колеблется от 18 до 25.

5. Модифицированный код Хаффмана-Панферовой

5.1. Построение кода Попробуем предложить несколько модифицированный код Хаффмана, строя таблицы кодирования с учетом содержания самого документа. За основу построения кода возьмем бинарное дерево Хаффмана [6].

Определение 1: Пусть A={a1,a2,...,an} алфавит из n различных символов, W={w1,w2,...,wn} соответствующий ему набор положительных целых весов.

Тогда набор бинарных кодов C={c1,c2,...,cn}, такой что:

ci не является префиксом для cj, при ij 1) 2) минимальна (|ci| длина кода ci) называется минимально-избыточным префиксным кодом или иначе кодом Хаффмана.

Замечания:

1. Свойство (1) называется свойством префиксности. Оно позволяет однозначно декодировать коды переменной длины.

2. Сумму в свойстве (2) можно трактовать как размер закодированных данных в битах. На практике это очень удобно, т.к. позволяет оценить степень сжатия, не прибегая непосредственно к кодированию.

В дальнейшем, чтобы избежать недоразумений, под кодом будем понимать битовую строку определенной длины, а под минимальноизбыточным кодом или кодом Хаффмана множество кодов (битовых строк), соответствующих определенным символам и обладающих определенными свойствами.

Известно, что любому бинарному префиксному коду соответствует определенное бинарное дерево.

Определение 2: Бинарное дерево, соответствующее коду Хаффмана, будем называть деревом Хаффмана.

Задача построения кода Хаффмана равносильна задаче построения соответствующего ему дерева. Приведем общую схему построения дерева Хаффмана.

1. Составим список кодируемых символов (при этом будем рассматривать каждый символ как одноэлементное бинарное дерево, вес которого равен весу символа).

2. Из списка выберем два узла с наименьшим весом.

3. Сформируем новый узел и присоединим к нему, в качестве дочерних, два узла выбранных из списка. При этом вес сформированного узла положим равным сумме весов дочерних узлов.

4. Добавим сформированный узел к списку.

5. Если в списке больше одного узла, то повторить п. 25.

Для того чтобы эффективно кодировать документы, необходимо просканировать конкретный документ в факсимильном аппарате, затем составить таблицу кодирования/декодирования, исключительно для этого документа. Составленная таблица должна передаваться вместе с закодированным (сжатым) факсимильным сообщением на приемный факсимильный аппарат, чтобы осуществить декодирование. В качестве основного алгоритма составления оптимального кода, используем алгоритм Хаффмана [5, 6].

Для примера составления таблицы кодирования/декодирования возьмем небольшой фрагмент документа.

W.4.4.10.3.811.1.13.1.881 W.5.3.12.1.347.1.9.2.450.2.12.3.881 W.5.3.360.2.8.2.449.2.14.2.881 W.5.3.360.3.6.2.449.2.16.1.881 W.5.3.362.1.6.1.449.2.17.1.881 W.5.3.818.3.899 W.5.3.817.3.900 W.5.3.817.3.900

–  –  –

Составим таблицу для белых символов, для начала выпишем все белые символы.

White = {4, 10, 811, 13, 881, 5, 12, 347, 9, 450, 12, 881, 5, 360, 8, 449, 14, 881, 5, 360, 6, 449, 16, 881, 5, 362, 6, 449, 17, 881, 5, 818, 899,5, 817,900, 5, 817,900} Теперь выпишем неповторяющиеся белые символы и присвоим им вес 1, а также повторяющиеся символы, их вес будет определяться числом повторений, итак получим:

Теперь проделаем все пункты, описанные в алгоритме выше.

–  –  –

Из табл. 5.3 видно, что могут быть одинаковые коды для белых и черных серий. Чтобы избежать путаницы, будем передавать вместе с каждой строкой документа в качестве первого пикселя код белого – 1000000000000 или код черного – 00000000000001, тогда все последующие цвета будут чередоваться, и одинаковые коды для разных цветов не спутаются.

Закодированный фрагмент документа будет иметь вид:

–  –  –

Коэффициент сжатия (с учетом добавленных в начало каждой строки двоичного кода белого, содержащего 13 символов):

Ксж=13825/249=55,52.

Полученный Ксж больше коэффициента сжатия, который был получен при использовании таблиц, разработанных Хаффманом.

Исследование эффективности применения кода ХаффманаПанферовой для различных документов

Выберем изображение – «Шахматная доска»:

Рис. 5.3. Исследуемое изображение «Шахматная доска»

При использовании стандартного алгоритма сжатия кодом Хаффмана при помощи разработанной программы, получили следующий результат:

Видим, что коэффициент сжатия – 15,152.

Построим оптимальный неравномерный код для этого изображения и посмотрим, какой коэффициент сжатия получится в этом случае.

Для этого проанализируем результаты, полученные при обработке изображения, то есть построчно посчитанное количество белых и черных серий, также в каждой строке указано, с какого цвета начинается строка.

Для наглядности приведем часть результатов:

B.445.421.445.417 B.445.421.445.417 B.445.421.445.417 B.445.421.445.417 B.445.421.445.417 W.437.433.436.422 W.437.433.436.422 W.437.433.436.422 W.437.433.436.422 W.437.433.436.422 W.437.433.436.422 W.437.433.436.422 Далее посчитаем количество одинаковых белых и черных серий и у каждой такой серии напишем ее вес.

Для белых серий получим следующее:

{231, 13061, 12972, 17284, 424567, 436567, 417568, 437567, 4211133, 4321464} (((((231+13061)2+12972)4+17284)8+(424567+436567)1134)1142+((417568+437567)1135 +4211133)2268)3410+4321464)4874

Построим дерево Хаффмана для белых серий данного изображения:

–  –  –

{8701, 4181, 8661, 8651, 8401, 438567, 422568, 431734, 4331299, 4451700} (((((8701+4181)2+(8661+8651)2)4)+((8401+438567)568+422568)1136)1140+ (431734+4331299)2033)3173+4451700)4873

Построим дерево Хаффмана для черных серий данного изображения:

–  –  –

Таким образом, если закодировать строки с помощью приведенных комбинаций, то всего в документе получим 58583 символа, в исходном документе их количество составляет 4219776, коэффициент сжатия:

Ксж=4219776/58583=72,03.

5.3. Блок-схема модифицированного факсимильного аппарата.

Алгоритмы приема-передачи факсимильных сообщений Блок – схема модифицированного факсимильного аппарата, в котором для каждого передаваемого документа строится оптимальный неравномерный код для кодирования белых и черных серий может иметь следующий вид (рис. 5.4).

На схеме:

Синяя стрелка – передача в режиме 1/прием в режиме 1 (используется стандартное кодирование методом Хаффмана).

Фиолетовая стрелка – передача в режиме 2/прием в режиме 2 (для кодирования строится дерево Хаффмана и индивидуальная кодовая таблица для каждого документа).

Устройство сканирования – осуществляет сканирование документа.

Прогр1 – программа преобразует размеры отсканированного документа17282376 и сохраняет его в формате *. wbmp.

Прогр2 – программа преобразует отсканированное изображение документа в последовательность бит.

Прогр3 часть 1 – считает количество белых и черных серий в каждой строке, анализирует первый символ белый или черный и создает документ с этими данными.

Прогр3 часть 2 – осуществляет кодирование документа при помощи стандартных таблиц Хаффмана.

МБ математический блок – осуществляет математические преобразования для документа, полученного в 1 части прогр3, далее осуществляет построение дерева Хаффмана и выводит таблицу кодирования для текущего документа.

Кодер – осуществляет кодирование серий при помощи таблицы, полученной на предыдущем шаге.

Шифратор – осуществляет шифрование полученного документа (для передачи 1) и таблицы, и документа (для передачи 2) от злоумышленников.

Дешифратор – осуществляет дешифрование полученного документа (для передачи 1) и таблицы, и документа (для передачи 2).

Декодер – осуществляет декодирование документа при помощи полученной таблицы.

Устройство вывода на печать – осуществляет подготовку документа на печать и печатает его.

На рис. 5.5 показана блок-схема алгоритма передачи факсимильных сообщений.

Рис. 5.4. Блок – схема модифицированного факсимильного аппарата Рис. 5.5.

Блок-схема алгоритма передачи факсимильных сообщений Анализ быстродействия передачи ФС (для анализа использовался ноутбук MACBOOK T8300):

Рис. 5.6. MACBOOK T8300

1. Сканирование изображения – 12 с

2. Запуск процессора – 60 с

3. Выполнение прогр1 – 0,75 с

4. Выполнение прогр2 – 7,3 с

5. Выполнение прогр3 часть1 – 11,8 с прогр3 часть1,2 – 13,24 с

6. Работа МБ: 1 лист – 66 строк – обработка 1 с, обработка 1 строки – 0,01с = 120 листов (объем документа, представленного в виде последовательности серий) – 120 с

7. Построение дерева Хаффмана и таблицы кодирования – одна операция сложения по времени составляет – 2,3910-9 с, для построения дерева Хаффмана потребуется, как минимум, 18 операций сложения (если брать в качестве примера шахматную доску) – итого – 4,30210-8 с. Далее для построения самого дерева потребуется еще 36 графических операций – то есть на 36 операций затратим 8,60410-8 с. Для составления таблицы кодирования по дереву потребуется еще время на 80 операций, т.е. 19,1210-8 с, итого – 32,02610-8 с = 0,32 мкс

8. Кодирование 5 с

9. Шифрование – 5 с (с таблицей), 3 с (без таблицы) Итак: для передачи файла с помощью ФА, использующего стандартные таблицы Хаффмана, потребуется 1,6 минуты, а для передачи файла с помощью модифицированного ФА, использующего метод построения дерева Хаффмана и индивидуальной таблицы кодирования – 3,7 минуты.

На рис. 5.7 показана блок-схема алгоритма приема факсимильных сообщений.

Анализ быстродействия приема ФС:

1. Работа дешифратора 3 с (без таблицы), 5 с (с таблицей)

2. Выполнение программы 3 часть1,2 – 13,24 с, часть1 – 11,8 с

3. Декодирование 10 с

4. Выполнение программы 2,1 – 7,3 с / 0,75 с

5. Печать – 0, 3 с Итак, для приема файла с помощью ФА, использующего стандартные таблицы Хаффмана, потребуется 24,59 с, а для приема файла с помощью ФА, использующего метод построения дерева Хаффмана и индивидуальной таблицы кодирования – 35,15 с.

Рис. 5.7. Блок-схема алгоритма приема факсимильных сообщений ЗАКЛЮЧЕНИЕ В ходе дипломной работы был проведен ряд экспериментов и исследована эффективность сжатия документов модифицированным кодом Хаффмана. Документы различались как содержанием, так и языковым алфавитом.

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

Проведенные исследования позволили сделать следующие выводы:

коэффициенты сжатия для документов, которые исследовал Хаффман для построения таблиц, в среднем составляют: минимальный 12,4 максимальный – 42,06;

алгоритм кодирования Хаффмана не чувствителен к языку, на котором составлен документ, предназначенный для передачи. Максимальный коэффициент сжатия получается для корейского языка – 32,2, что обусловлено наличием чередования длинных белых и черных серий, а минимальный – для арабского языка – 12,5, что обусловлено частым чередованием коротких белых и черных серий;

предложен собственный алгоритм кодирования на основе построения дерева Хаффмана, расчеты показали, что эффективность сжатия таким алгоритмом может составить до 72% от всего документа. Но время на передачу такого документа может составить 3,7 минуты, что не соответствует Рекомендации Т.4 для ЦФА G3 [9, 10]. Поэтому, несмотря на то, что данный алгоритм позволяет хорошо сжимать изображение документа, он не может быть рекомендован для практического использования на современном этапе развития микропроцессорной техники;

в качестве альтернативного варианта можно предложить разработку факсимильного аппарата, в основу которого будут заложены, например, 5 стандартных кодовых таблиц для разных классов документов: изображение, текст, таблица, график, документ с большим содержанием белого (например, рукописное заявление).

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

Номер таблицы может быть передан вместе со сжатым документом. Это позволит исключить ручные действия по переключению тумблеров на ФА.

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. http://ru.wikipedia.org/wiki/Дэвид_Хаффман

2. Сэломон Д. Сжатие данных, изображений и звука. — М.: Техносфера, 2004.

3. http://rain.ifmo.ru/cat/view.php/theory/data-compression/facsimilecompression-2006#src

4. ftp://nic.funet.fi/pub/graphics/misc/test-images/

5. http://www.compression.ru/download/articles/huff/ simakov_2002_huffcode.html

6. Рябов А. Построение дерева Хаффмана (2000)

7. http://opds.sut.ru

8. Руководящий документ отрасли РД.45.129-2000. Телематические службы.

9. Том VII – Выпуск VII.3. Оконечное оборудование и протоколы для телематических служб. Рекомендации серии Т, 1984.

10. Рекомендации Т.4 Стандартизация факсимильной аппаратуры

Похожие работы:

«КРАТКАЯ ЭНЦИКЛОПЕДИЯ Общее знакомство с породами собак Часть 6. С – (2-22) Т – (23-40) Саге Коче Саге Коче является прямым предком среднеазиатской овчарки. Эту породу без преувеличения можно назвать аборигеном Афганистана. Собаки породы Саге Коче используются в качестве сторожевых, охранных, пастушьих, а...»

«VA2246-LED/VA2246m-LED/ VA2246a-LED/VA2246ma-LED LCD Display Руководство пользователя Номер модели: VS15451 Соответствие стандартам ПРИМЕЧАНИЕ: В данном разделе содержатся все сведения о соблюдении нормативных требований и правил. Утвержденные сведения о назначении см. на паспортных та...»

«аудио-видео №11(90) 2006 Владимир Постоловский ЛЯМБДА–ЗОНД Лямбда-зонд устанавливается в потоке отработавших газов двигателя и измеряет уровень содержания кислорода в них. Анализируя осциллограмму напряжения выходного сигнала лямбда...»

«АТОЛ 77Ф Контрольно-кассовая техника Руководство по эксплуатации Руководство по эксплуатации AL.P070.00.000 РЭ Версия документации от 25.01.2017 [Содержание] Содержание Введение Подготовка ККТ к эксплуатации Использование ККТ по назначению Взаимодействие с ФНС через ОФД Требования безопасност...»

«Михаил ДЕЛЯГИН СВЕТОЧИ ТЬМЫ ФИЗИОЛОГИЯ ЛИБЕРАЛЬНОГО КЛАНА От Гайдара и Березовского до Собчак и Навального Жизнь быстротечна: даже участники трагедии 90х забывают ее детали. Что же говорить о новых поколениях, выросших после августа не только 1991го, но и 1998го? О тех, кто...»

«Управление образования администрации муниципального образования городского округа Сыктывкар (УО АМО ГО "Сыктывкар") "Сыктывкар" кар кытшын муниципальнй юкнлн администрацияса йзс велдмн веськдланiн ПРИКАЗ "14" сентября 2016 г. № 819 О проведении муниципального конкурса информационных проектов по...»

«Федеральное агентство морского и речного транспорта Федеральное государственное бюджетное образовательное учреждение высшего образования "Государственный университет морского и речного флота имени адмирала С.О. Макарова" ПОЛОЖЕ...»

«Техника безопасности Опасайтесь удара током!– рабочие части батареи могут находиться под напряжением, даже когда устройство не подсоединено к сети питания.– не открывайте крышку: внутренние части устройства нельзя обслуживать самостоятельно. Обратитесь в сервисный центр. Для уменьшения риска удара током о...»









 
2017 www.lib.knigi-x.ru - «Бесплатная электронная библиотека - электронные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.