Исследование и разработка методов сжатия текста на арабском языке

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

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

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

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

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

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

.

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

В конце 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 разработано кодирующее — декодирующее устройство (кодек) для предлагаемого метода кодирования.

ЗАКЛЮЧЕНИЕ

.