автореферат диссертации по радиотехнике и связи, 05.12.04, диссертация на тему:Исследование и разработка методов сжатия текста на арабском языке

На правах рукописи

АДВИ ХЕКМЕТ САМИР

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ СЖАТИЯ ТЕКСТА НА АРАБСКОМ ЯЗЫКЕ

Специальность 05.12.04. «Радиотехника, в том числе системы и устройства телевидения»

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва-2005

Работа выполнена на кафедре Радиотехнических приборов Московского энергетического института (технического университета)

Научный руководитель: доктор технических наук, профессор

Сизов Виктор Петрович

Официальные оппоненты: доктор технических наук, профессор

Безруков Вадим Николаевич

кандидат технических наук, доцент Сизякова Анна Юрьевна

Ведущая организация: "НИИР-РадиоНет" (г.Москва)

Защита состоится «/ /С » С^^С-Я. 2005 г. в ¡ Г часов ? п минут на заседании диссертационного совета Д.212.157.05 при Московском энергетическом институте (техническом университете) по адресу: 111250, Москва, ул. Красноказарменная, д. 17, аудитория А-402

Отзывы в двух экземплярах, заверенные печатью, просим направлять по адресу: 111250, Москва, ул. Красноказарменная, д. 14, Ученый совет МЭИ(ТУ).

С диссертацией можно ознакомиться в библиотеке МЭИ (ТУ). Автореферат разослан 2005 г.

Ученый секретарь диссертационного совета кандидат технических наук, доцент

Общая характеристика работы

Актуальность темы.

Жизнь современного общества фактически невозможна без хорошо развитых электронных систем. Любая радиотехническая система имеет своей целью доставить информацию о каком-либо явлении, событии или состоянии некоторой материальной системы в условиях, когда источник информации удален от места ее приема. Это может быть текстовая информация (радиосвязь), информация о координатах или скорости движения удаленного объекта (радиолокация), изображение объекта (телевидение), информация о состоянии удаленной материальной системы (телеметрия), команды на изменение состояния объекта (командные радиолинии) и т.д.

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

Основная причина использования сжатия — уменьшение объема, необходимого для хранения информации. Способ сжатия по Бройлю может сократить размер книги на 20% или уменьшить число томов, необходимых для хранения одной печатной книги. Для компьютеров сжатие позволяет увеличить количество информации, хранимой на диске, уменьшить число носителей информации, уменьшить время доступа и т.д.

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

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

Люди часто задаются вопросом, актуально ли сжатие в век персональных компьютеров и автоматизированных рабочих мест. На современных средствах хранения можно разместить мегабайты, возможно гигабайты информации. Очевидно, что пользователей интересует достижение двойного или тройного уменьшения занимаемого пространства.

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

Целью настоящей диссертационной работы является исследование статистики арабских и английских текстов и разработка на этой основе эффективных алгоритмов кодирования.

1. Анализ существующих моделей сжатия текстовой информации для разных языков.

2. Анализ статистики текстов на арабском языке различной тематики и объема.

3. Разработка метода сжатия, основанного на модели 1-го и 2-го порядка.

4. Экспериментально - статистическая проверка разработанного метода и сравнение его с другими методами.

5. Разработка программы кодирования и декодирования, основанной на

данном методе.

Методы исследования

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

Научная новизна

1. Внедрение принципа кодирования текста на базе модели сообщения высокого порядка.

2. Разработка алгоритмов кодирования с моделями первого и второго порядков.

На защиту выносятся

1. Результаты анализа основных особенностей современных и популярных методов статистического кодирования.

2. Результаты анализа текстов на арабском и английском языке и расчет распределения вероятностей их п-грамм.

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

4. Результаты проведенного экспериментального исследовании и подтверждение работоспособности и эффективности предложенного нового метода кодирования.

5. Разработанная программа и алгоритм кодирования на базе диграмм и триграмм.

6. Разработанное устройство кодирования - декодирования (кодек) для предлагаемого метода сжатия с моделями источника сообщения высокого порядка.

Практическая ценность и внедрение

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

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

Структура и объем работы

Диссертационная работа состоит из введения, четырех глав, заключения, список литературы включает 69 наименований и приложений. Работа изложена на 132 страницах машинного текста, включая 27 таблиц и 41 рисунка.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава посвящена рассмотрению вопросов необходимости и целесообразности сжатия текстов. Глава содержит краткий обзор наиболее известных существующих методов сжатия текста (в порядке их исторического появления). Приведены описания следующих методов: Шеннона - Фано; Хаффмена; адаптивное сжатие Хаффмена; арифметическое кодирование. Сжатие сокращает объем пространства, требуемого для хранения файлов в ЭВМ, и количество времени, необходимого для передачи информации по каналу установленной ширины пропускания. Мы рассматриваем лишь обратимое сжатие или сжатие без наличия помех, где первоначальный текст может быть в точности восстановлен из сжатого состояния. Большинство широко изучаемых алгоритмов сжатия данных основаны на кодах Хаффмена.

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

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

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

событий с известными вероятностями рир2.....Р„, сумма которых равна 1. Их

"энтропия" показывает, как широк набор, в среднем, при выборе события, или, что эквивалентно, как не уверены мы в результате выбора. В своей работе, ознаменовавшей рождение теории информации, Шеннон постулировал, что энтропия должна удовлетворить следующим требованиям:

• Е— непрерывная функция от р,.

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

• Если выбор сделан в несколько последовательных этапов, то Е должна быть суммой энтропии выборов на каждом этапе, взвешенной в соответствии с их вероятностями.

Как показал Шеннон, единственная функция, которая удовлетворяет этим требованиям, есть

где положительная константа к вводит единицы, в которых измеряется энтропия. Обычно в качестве единиц используются "биты" (при этом к = 1), а логарифм берётся по основанию 2:

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

Полученные нами предварительные результаты сжатия художественных текстов на арабском и английском языках с помощью нескольких алгоритмов (HUFF - хаффменовский, AHUFF - адаптивный Хаффменовский, ARITH -арифметический, LZSS, LZW12, LZW15V - разновидности алгоритма Лемпеля и Зива) изображены на графике рис. 1, где левые столбики относятся к английскому языку, а правые - к арабскому. Рис. 1 позволяет сравнить степени сжатия текстов по каждому из этих алгоритмов.

60% 50% 40% 30% 20% 10% 0%

1Ш"1Ш II К

Huff A Huff Arith LZSS LZW12 LZW15V

Рис. 1. Сравнение степени сжатия английских и арабских текстов

Такие результаты можно объяснить следующим образом. С одной стороны, в английском языке, в отличие от арабского, заглавная и прописная буквы имеют различные коды. С другой же стороны, в арабском

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

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

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

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

В итоге, процессы кодирования и декодирования сообщения принимают вид, показанный на рис. 2.

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

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

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

может быть основано на различных моделях). Чтобы перевести обсуждение в количественное русло, мы рассмотрим некоторые статистические результаты, подобранные из большого количества письменных текстов на арабском и английском языке. Однако использование эмпирических распределений может быть неудобным. Например, чтобы найти новую статистику или оценить новый предиктор (предсказатель), необходимо возвратиться к исходным данным и повторно проанализировать их новым способом. Такие проблемы были бы решены или, по крайней мере, облегчены, если бы статистические распределения, найденные в тексте, могли бы быть аппроксимированы математическими моделями. Поэтому, исследуем некоторые простые распределения вероятности, которые связаны с естественным языком и потому, как представляется, соответствуют статистике, наблюдаемой практически. К сожалению, действительно удовлетворительные математические модели естественного языка отсутствуют. Наконец, рассмотрим попытки измерить "истинное" информационное содержание арабского языка (а также английского языка), и просуммируем результаты большого количества экспериментов по анализу того, как хорошо люди на основании текущего текста могут предсказать его будущее содержание.

Корреляции между буквами стоящими рядом в тексте проявляются в частотном распределении буквенных последовательностей. Пару рядом стоящих букв называют диграммой, три последовательные буквы - триграммой и так далее. Многие пары букв например, (диграммы) вообще никогда не встречаются в реальных текстах. Для более длинных последовательностей букв этот эффект ещё заметней. Например, в нормальном тексте из алфавита в 94 символа, встречается всего около 39% возможных диграмм (всего их 94x94=8836), около 3,6% триграмм и всего 0,2% возможных тэтраграмм.

На рис. 3. показаны распределения вероятностей символов в моделях порядка 0 (одиночные символы), порядка 1 (диграммы) и порядка 2 (триграммы) для арабского языка.

Р1 0.2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

\

Рис. 3. Сравнение распределений монограмм, диграмм и триграмм для арабского языка

где Р, - вероятность появления ^ i - монограмма, диграмма, или триграмма.

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

Согласно традиционным знаниям о печати, наиболее частыми в арабском языке являются следующие 20 символов (в порядке убывания частоты, начиная справа налево:

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

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

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

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

аЬа^дасаЬс1Ы адЬЬасй^а о

Первый символ кодируемого сообщения передадим без кодировки, в своём естественном виде (пусть это будет, например, 8-битовый символ "а"). Второй символ будет иметь уже непосредственно предшествующий ему символ, и предстоит выяснить, сколько имеется других диграмм в тексте, содержащих тот же самый первый символ. Пусть это будут, например, диграммы, показанные на рис. 4.

Рис. 4. Дерево Хаффмена для диграмм, начинающихся с символа "а"

При помощи построенного на их основе дерева Хаффмена находим коды, соответствующие различным диграммам, начинающимся с символа "а" (Табл. 1).

Таблица 1. Коды Хаффмена для диграмм, начинающихся с символа "а"

аЪ-00

ас-01

ad-10

ag-110

ао-111

Если второй символ нашего сообщения - "Ь", то, согласно табл. 1, диграмма "ab" кодируется кодом "00". Продолжая таким образом до конца сообщения, получим следующий кодовый поток рис. 5:

Рис. 5. Результирующий кодовый поток

При декодировании в качестве первого символа переносится первый байт <а> кодового потока (см. рис. 5). Затем, на основании статистической информации о частости диграмм с первым символом "а" строится дерево Хаффмена (рис. 4), и по коду "00" на нём находится второй символ "Ь" декодированного сообщения.

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

диграмм исходного текста, то при кодировании по модели сообщения п-го порядка используется информация о частости (л+Гуграмм.

В качестве примера на рис. 6. проведены результаты сжатия арабских текстов по монограммам и диграммам. Результаты этих сравнений показали, что при любых объемах текста степень сжатия диграммами лучше, чем монограммами.

1000 10000 50000 100000 300000

объем текста (байт)

Рис. 6. Сравнение степени сжатия монограммами и диграммами

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

% _

В монограммы

■ триграммы с учетом двух предыдущее символов

объем текста (байт^

Рис. 7. Сравнение степени сжатия монограммами и триграммами

При данном способе кодирования, самая существенная проблема - это необходимость передачи вместе со сжатым текстом еще и таблицы частости «-грамм. Последние необходимы для построения деревьев при раскодировании текста. Если при обычном хаффменовском сжатии таблица частости символов (монограмм) имеет максимальную длину в 255 байт (реально она гораздо меньше), то при кодировании диграмм максимальная длина таблицы равна 256x256=65536 байт. Реально длина такой таблицы в среднем составляет около 10000 байт. Это означает, что к сжатому тексту нужно добавлять дополнительно 10 кбайт текста без сжатия.

В качестве решения, свободного от этого недостатка, можно предложить следующий способ. Обработав множество текстов, составляем таблицу частости диграмм. По этой таблице строится дерево кодов. Таблица и соответствующие коды будут использоваться затем для кодирования всех текстов данного языка. Назовем эту таблицу обобщенной таблицей частости (рис. 8). По данной таблице строится обычным способом дерево и кодируются диграммы. Обобщенная таблица не требует специальной передачи при

кодировании. Она просто один раз запоминается как на передающей, так и на приемной стороне.

Рис. 8. Усредненное распределение триграмм

где, Ы, - частость появления триграммы i

Использовав модели сообщения 2-ого порядка (на базе триграмм), мы получили повышенные коэффициенты сжатия, достигающие 80%. Можно использовать модели и более высоких порядков, но это приводит к усложнению программы кодирования и к большому объему кодовой таблицы.

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

При выборе элементной базы основное внимание было уделено выбору исполнительного устройства. Решение задачи возможно с применением программируемых логических интегральных схем (ПЛИС) или микропроцессоров. Использование ПЛИС позволяет реализовать максимально высокое быстродействие устройства, но требует большого объёма как

программного, так и аппаратного обеспечения, что связано с большими материальными затратами.

При выборе типа микропроцессора, наиболее подходящего для решения данной задачи, были рассмотрены варианты использования микроконтроллеров фирм Atmel, Intel, Microchip и сигнального процессора Taxes Instruments. При этом для макетного образца было предложено использовать недорогие микроконтроллеры. Среди фирм производящих микроконтроллеры предпочтение было отдано фирме Microchip и семейству её недорогих Контроллеров PIC.

ОЗУ 1 Данные для сжатия -"S ПЛИС или микропроцессор ОЗУ 2 Сжатые данные

Рис. 9. Структурная схема кодека Хаффмана

Данные для сжатия поступают последовательно по линии связи и записываются в ОЗУ 1. В ПЛИС или микропроцессор (далее по тексту -исполнительное устройство (ИУ) ) поступает команда, под действием который ИУ постепенно обрабатывает данные из ОЗУ 1 и, сжимая их по методу Хаффмена при модели определенного порядка, записывает в ОЗУ 2. В результате в ОЗУ 2 находится результат сжатия данных, которые дальше передаются по линии связи.

Основные выводы и результаты работы

1. Рассмотрены известные в настоящее время методы статистического кодирования текстов и сделан вывод о недостаточном практическом использовании моделей источников сообщений высокого порядка.

2. Рассмотрены статистические характеристики текстов на арабском и английском языках с точки зрения частости появления в них различных монограмм, диграмм и триграмм.

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

4. Для уменьшения объема передаваемых декодеру статистических характеристик кодируемого текста предложено в качестве функций распределения его ^грамм использовать обобщенные распределения, получаемые усреднением по множеству различных текстов. Успешное использование таких распределений продемонстрировано на ряде конкретных примеров.

5. Разработаны и отлажены на языке C++ программы кодирования и декодирования текстов по предложенному методу для моделей источника сообщения первого и второго порядков.

6. На базе микроконтроллера PIC16F877, разработано кодирующее - декодирующее устройство (кодек) для предлагаемого метода кодирования.

Основные результаты работы изложены в следующих публикациях:

1) Сизов В.П., Адви Х.С. Сравнительный анализ эффективности сжатия текстов на английском и арабском языках // Девятая международная научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика»: Тез. докл. - М.: Изд. МЭИ, 2003. - Т.1. - С. 88-89.

2) Сизов В.П., Адви Х.С. Анализ статистики ^грамм в арабских текстах различной тематики.// Радиотехнические тетради. — 2004. — № 29. - С. 41-44.

Подписано в печать ^¡,В5>СЬГ. За к. Тир. ¡00 Пл.

Полиграфический центр МЭИ (ТУ)

Красноказарменная ул., д. 13

О 9 ИЮЛ 2005

Л ы \

i be***,' i «if> i

\

V У

1692

ВВЕДЕНИЕ.

ГЛАВА 1. СУЩНОСТЬ И НЕОБХОДИМОСТЬ СЖАТИЯ ТЕКСТОВ.

1.1. Важность и эффективность использования текстового сжатия.

1.2. Предмет текстового сжатия.

1.3. Область применения методов сжатия текстов на практике.

1.4. Алгоритм Шеннона - Фано.

1.5. Алгоритм Хаффмена.

1.6. Адаптивное кодирование Хаффмена.

1.7. Арифметическое кодирование.

Выводы к главе 1.

ГЛАВА 2. АНАЛИЗ СТАТИСТИКИ АРАБСКИХ И АНГЛИЙСКИХ ТЕКСТОВЫХ СООБЩЕНИЙ.

2.1. Измерение информации в компьютерной системе.

2.2. Энтропия — мера количества информации.

2.3. Сравнительная характеристика степени сжатия текстов на арабском и английском языках.

2.4. Статистический подход к сжатию текстов через моделирование и кодирование.

2.5. Моделирование естественного языка.

2.6. Анализ вероятности появления очередных символов в арабских текстах.

2.7. Сравнительный анализ арабских и английских текстов.

Выводы к главе 2.

ГЛАВА 3. МЕТОДЫ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ ОБОБЩЕННОГО СТАТИСТИЧЕСКОГО РАСПРЕДЕЛЕНИЯ СИМВОЛОВ АЛФАВИТА.

3.1. Методика кодирования по модели сообщения первого порядка.

3.2. Методика декодирования.

3.3. Сравнительная характеристика разных способов сжатия.

3.4. Сравнение предлагаемого метода с другими способами сжатия по модели высокого порядка.

3.5. Описание алгоритмов программ.

3.5.1. Общая схема программы.

3.5.2. Процедуры подсчета диграмм и триграмм.

3.5.3. Процедуры построения деревьев для диграмм и триграмм.

Выводы к главе 3.

ГЛАВА 4. ВОПРОСЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ КОДЕКА С МОДЕЛЬЮ ИСТОЧНИКА СООБЩЕНИЯ ВЫСОКОГО ПОРЯДКА.

4.1. структурная схема кодека.

4.2. Выбор элементной базы.

4.3. Микроконтроллер PIC16F877.

4.4. Микросхема статистического ОЗУ 62256.

4.5. Программатор PIC-контроллеров.

Выводы к главе

Жизнь современного общества фактически невозможна без хорошо развитых электронных систем. Любая радиотехническая система имеет своей целью доставить информацию о каком-либо явлении, событии или состоянии некоторой материальной системы в условиях, когда источник информации удален от места ее приема. Это может быть текстовая информация (радиосвязь), информация о координатах или скорости движения удаленного объекта (радиолокация), изображение объекта (телевидение), информация о состоянии удаленной материальной системы (телеметрия), команды на изменение состояния объекта (командные радиолинии) и т.д.

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

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

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

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

Актуальность темы.

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

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

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

Основная причина использования сжатия — уменьшение объема, необходимого для хранения информации. Способ сжатия по Бройлю может сократить размер книги на 20% или уменьшить число томов, необходимых для хранения одной печатной книги. Для компьютеров сжатие позволяет увеличить количество информации, хранимой на диске, уменьшить число носителей информации, уменьшить время доступа и т.д.

Сжатие означает уменьшение объема текста. Другими словами, сжатие текста - это нахождение способа представить его меньшим количеством битов или байтов. Необходимо, чтобы закодированная форма не осложняла восстановление первоначального (оригинального) текста, и обычно важно, чтобы оригинал восстанавливался точно, а не приблизительно. Это отличает сжатие текста от сокращения многих других видов данных, типа голоса или кодирования картины, где небольшая деградация качества может быть вполне терпима, если достигнуто более компактное представление информации.

Люди часто задаются вопросом, актуально ли сжатие в век персональных компьютеров и автоматизированных рабочих мест. На современных средствах хранения можно разместить мегабайты, возможно гигабайты информации. Очевидно, что пользователей интересует достижение двойного или тройного уменьшения занимаемого объема.

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

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

Цель работы

Целью настоящей диссертационной работы является исследование статистики арабских и английских текстов и разработка на этой основе эффективных алгоритмов кодирования.

Задачи

1. Анализ существующих моделей сжатия текстовой информации для разных языков.

2. Анализ статистики текстов на арабском языке различной тематики и объема.

3. Разработка метода сжатия, основанного на модели 1-го и 2-го порядка.

4. Экспериментально - статистическая проверка разработанного метода и сравнение его с другими методами.

5. Разработка программы кодирования и декодирования, основанной на данном методе.

Методы исследования

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

Научная новизна

1. Внедрение принципа кодирования текста на базе модели сообщения высокого порядка.

2. Разработка алгоритмов кодирования с моделями первого и второго порядков.

Практическая ценность

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

Личный вклад. Все основные научные результаты в диссертационной работы получены автором лично.

Публикации. По материалам диссертационной работы опубликовано 2 научные работы и третья в процессе издания. Основные положения, выносимые на защиту:

1. Результаты анализа основных особенностей современных и самых распространенных методов статистического кодирования.

2. Результаты анализа текстов на арабском и английском языке и расчет распределения вероятностей их п-грамм.

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

4. Результаты проведенного экспериментального исследовании и подтверждение работоспособности и эффективности предложенного нового метода кодирования.

5. Разработаны программа и алгоритм кодирования на базе диграмм и триграмм.

6. Разработано устройство кодирования - декодирования (кодек) для предлагаемого метода сжатия с моделями источника сообщения высокого порядка.

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, список литературы включает 69 наименований и приложений. Работа изложена на 132 страницах машинного текста, включая 27 таблиц и 41 рисунка.

Основные результаты полученные в диссертации:

1. Рассмотрены известные в настоящее время методы статистического кодирования текстов и сделан вывод о недостаточном практическом использовании моделей источников сообщений высокого порядка.

2. Исследованы статистические характеристики текстов на арабском и английском языках с точки зрения частоты появления в них различных монограмм, диграмм и триграмм.

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

4. Для уменьшения объема передаваемых декодеру статистических характеристик кодируемого текста предложено в качестве функций распределения его «-грамм использовать обобщенные распределения, получаемые усреднением по множеству различных текстов. Успешное использование таких распределений продемонстрировано на ряде конкретных примеров.

5. Разработаны и отлажены на языке С++ программы кодирования и декодирования текстов по предложенному методу для моделей источника сообщения первого и второго порядков.

6. На базе микроконтроллера PIC 16F877 разработано кодирующее — декодирующее устройство (кодек) для предлагаемого метода кодирования.

ЗАКЛЮЧЕНИЕ

1. ьаева 11.11. и др. Многоканальные системы передачи. М.: Радио и связь, 1997. -560с.

2. Борисов В.А. и др. Под ред. Калмыкова В.В. Радиотехнические системы передачи информации. М.: Радио и связь, 1990. -304с.

3. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. -205с.

4. Былянски П., Ингрем Д. Цифровые системы передачи. Пер. с англ. Под ред. Визеля А.А. М.: Связь, 1980. -360с.

5. Гордиенко B.IL, Крухмалев В.В. Проектирование и техническая эксплуатация систем передачи. М.: Радио и связь, 1996. -344с.

6. Гитлнц М.В., Лев АЛО. Теоретические основы многоканальный связи. М.: Радио и связь, 1986. -246с.

7. Гуткнн Л.С. Проектирование радиосистем и радиоустройств. М.: Радио и связь, 1986. -288с.

8. Гольденберг Л.М., Матюшкин Б.Д., Поляк M.II. Цифровая обработка сигналов. М.: Радио и связь, 1990.-256с

9. Зюко А.Г., Фалько А.И., ПанфиловИ.П. Помехоустойчивость и эффективность систем передачи информации. М.: Радио и связь, 1985. -272с.

10. Захарченко Н.В., Владишевский Б.С., Шувалов В.П. Передача данных. Учебное пособие. ОЭИС, 1982. -80с.

11. Кларк Дж., Кейн Дж., Кодирование с исправлением ошибок в системах цифровой связи. М.: Радио и связь, 1987. -391с.

12. Кловского Д.Д., Боккер П. Передача данных. Техника связи в системах телеобработки данных. М.: Связь, 1980. -264с.

13. Колмогоров A.IL Алгоритм, информация, сложность. М.: Знание, 1991. -88с.

14. Колмогоров А.Н. Теория информации и теория алгоритмов. М.: Наука, 1987. -303с.

15. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. М.: Наука, 1982.-416с.

16. Кричевский Р.Е. Сжатие и поиск информации. М.: Радио и связь, 1989. -168с.

17. Курицин С.А. Теоретические основы построения адаптивных систем. Учебн. Пособие. Л.: ЛЭИС, 1983. -64с.

18. Лазарева Е.Е. Система передачи информации. Циклические и сверочные коды. М.: Изд. МЭИ, 1986. -51с.

19. Лазарева Е.Е. Системы передачи информации. Помехоустойчивые коды в системах передачи цифровой информации. М.: МЭИ, 1980. -62с.

20. Липкин И.А. Статистическая радиотехника. Теория информация и кодирования. М.: Вузовская книга, 2002. -314с.

21. Левин Л.С., Плоткин М.А. Цифровые системы передачи информации. М.: Радио и связь, 1982. -215с.

22. Марков А.А. Введение в теорию кодирования. М.: Изд. Наука, 1982. -192с.

23. Мак-Вильямс и др. Теория кодов исправляющих ошибки. М.: Изд. Связь, 1979. -287с.

24. Назаров М.В., Кувшинков Б.И., Попов О.В. Теория передачи сигналов. М.: Связь, 1970. -367с.

25. Нарышкин А.К. Основы статистического кодирования. М.: Изд. МЭИ, 2002. -24с.

26. Нарышкин А.К. Комбинационные цифровые устройство. М.: Изд. МЭИ, 2002. -88с.

27. Нарышкин А.К. Основы теории радиотехнических систем извлечения информации. М.: Изд. МЭИ, 1996. -60с.

28. Нарышкин А.К. Информативность радиолокационных объектов, сигналов и систем. М.: Изд. МЭИ, 1994. -98с.

29. Норенков И.П., Трудоношин В.А. Телекоммуникационные технологии и сети. М.: МГТУ, 1998. -231с.

30. ЗО.Орищенко В.И., Санников В.Г., Свириденко В.А. Сжатие данных в системах сбора и передачи информации. М.: Радио и связь, 1985. -184с.

31. Пенин П.И., Филиппов Л.И. Радиотехнические системы передачи информации. М.: Радио и связь, 1984. -256с.

32. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. Перевод с английского. Под ред. Добрушина Р.Л. М.: Мир, 1978. -594с.

33. Пуртов Л.П., Пушкин В.М. Дискретные каналы в системах передачи данных. Л.: ЛЭИС, 1980. -69с.

34. Прокис Д. Цифровая связь. М.: Радио и связь, 2000. -800с.

35. Паппас К., Мюррей У. Руководство программиста по Си / Си++ . В двух книгах. М.: СК Пресс, 1997.

36. Сизов В.П., Адви Х.С. Сравнительный анализ эффективности сжатия текстов на английском и арабском языках. Тезисы докладов, НТК, том1, Радиоэлектроника, электротехника и энергетика. М.: МЭИ, 2003 — Т.1 — С.88-89.

37. Сизов В.П., Адви Х.С. Анализ статистики n-грамм в арабских текстах различной тематики//Радиотехнические тетради . -2004. -№ 29. -с.41-44.

38. Сизов В.П., Адви Х.С. Кодирования арабских и английских текстов методом Хаффмена при модели источника сообщения первого и второго порядков // Радиотехнические тетради. 2005. - № 31 (в процессе издания).

39. Сташин В.В., Урусов А.В., Мологонцева О.М. Проектирование цифровых устройств. На однокристальных микроконтроллерах. М.: Энергоатомиздат, 1990.-115с.

40. Тепляков И.М., Рощин Б.В., Фомин А.И., Вейцель В.А. Радиосистемы передачи информации. М.: Радио и связь, 1982. -264с.

41. Хаффмен Д. А. Метод построения кодов с минимальной избыточностью Кибернетический сборник.-М., 1961. —Вып. 3.- 79-87с.

42. Шэннон К. Статистическая теория передачи электрических сигналов. Теория передачи электрических сигналов при наличии помех. Сб. Переводов под ред. Н. А. Железнова. М.: Издательство иностранной литературы, 1953. 7-88с.

43. Цымбал В.П. Теория информация и кодирование. Киев.: Изд. Высшая школа, 1982.-303с.

44. Шувалов В.П. Передача дискретных сообщений. М.: Радио и связь, 1990. -462с.

45. Якубовский С.А. и др. Цифровые и аналоговые интегральные микросхемы. Справочник. М.: Радио и связь, 1990.

46. Логические интегральные схемы КР1533, КР1554. Справочник. В двух частях. М.: Бином, 1993.

47. Abramson D.M. An adaptive dependency source model for data compression. Commun. ACM 32,1989. 77-83c.

48. Bell T.C., Cleary J.G., Witten I.H. Text compression. Prentice Hall PRT, Englewood Cliffs, New Jersey, 1990. -310c.

49. Bell T.C., Moffat A.M. A note on the DMC data compression scheme. Computer J. 32, 1989. 16-20c.

50. Bently J.L., Sleator D.D., Taijan R.E., Wei V.K. A Locally Adaptive Data Compression Scheme. CACM. 1986. Vol. 29, N 4. 320-330 p.

51. Brent R.P. A linear algorithm for data compression. Augt. Comput. J. 19, 2, 1987. 64-68c.

52. Cortesi D. An effective text-compression algorithm. Byte 7, 1982. 397-403c.

53. Jones D.W. Application of splay trees to data compression. Commun. ACM 31, 1988. 996-1007c.

54. Lelewer D.A. and Hirschberg D.S. Data compression. Comput. Surv. 13, 1987. 261-296c.

55. Lynch T.J. Data compression: Techniques and application. Lifetime Learning Publications, Belmont, CA, 1985. -160c.

56. Nelson M. The data compression book. New York: M & P, 1958. -527c.

57. Rubin F. Experiments in text file compression. Commun. ACM. 19, 1976. 617-623с.

58. Rissanen J.J. and Langdon G.G. Universal modeling and coding. IEEE Trans. Inf. Theory IT-27, 1981. 12-23c.

59. Storer J.A. Data compression: Methods and Theory. Computer Science Press, Rockville, MD. 1988.-235c.

60. Tischer P. A modified Lemple-Ziv-Welch data compression scheme. Aust. Сотр. Sci. Commun. 9,1. 1987. -272c.

61. Wanas M.A., Zayad A.I., Shaker M.M. and Taha E.H. First-second- and third-order entropies of Arabic text. IEEE Trans. Information Theory, IT-22(1), 123, January, 1976.-123c.

62. Welch T.A. A technique for high-performance data compression. IEEE Computer 17, 1984. 8-19c.

63. Witten I.H., Neal R. and Cleaiy J.G. Arithmetic coding for data compression. Commun. ACM 30, 1987. 520-540c.

64. CD-ROM Microchip Technical Library. CD-ROM. First Edition, 2000.

65. CD-ROM MAXIM. Program, 1996.66. http://www.arabic2000.com67. http://www.moon 15.com68. http://www.euronews.com69. http://www.picall.comlud