Исследование и разработка методов сжатия текста на арабском языке тема диссертации и автореферата по ВАК РФ 05.12.04, кандидат технических наук Адви Хекмет Самир

• Адви Хекмет Самир
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Адви Хекмет Самир

ВВЕДЕНИЕ.

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

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат технических наук Адви Хекмет Самир, 2005 год

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