автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Модели и алгоритмы контекстно-словарного сжатия текстовых данных

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

МАКСИМОВ Сергей Владимирович

МОДЕЛИ И АЛГОРИТМЫ КОНТЕКСТНО-СЛОВАРНОГО СЖАТИЯ ТЕКСТОВЫХ ДАННЫХ (применительно к системам электронного обучения)

Специальность 05.13.11 —Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

УФА - 2006

Работа выполнена на кафедре информатики Уфимского государственного авиационного технического университета и кафедре программирования и вычислительной математики Башкирского государственного педагогического университета

Защита диссертации состоится 21 апреля 2006 г. в 10 часов на заседании диссертационного совета К-212.288.01 в Уфимском государственном авиационном техническом университете по адресу: 450000, г. Уфа-центр, ул. К.Маркса, 12.

С диссертацией можно ознакомиться в библиотеке Уфимского государственного авиационного технического университета

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

профессор Ю.С. Кабальнов

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

профессор В.П. Житников кандидат технических наук, старший научный сотрудник В.М. Коровин

Ведущее предприятие: Башкирская академия государственной

службы и управления при Президенте Республики Башкортостан

Автореферат разослан 16 марта 2006 г.

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

Р.А. Гараев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность

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

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

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

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

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

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

При решении поставленной задачи автор опирался на труды Д. Ватолина, А. Ратушняка, А. Смирнова, М. Смирнова, В. Юкина, И. Ножова, И.В. Павлова, A.B. Кадача, Д. Мастрюков, Д.Сэломона, Д.Е.Кнута и других ученых.

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

Цель и задачи исследования

Целью работы является разработка контекстно-словарного сжатия, обеспечивающего одновременно высокую гххе1Ш1Ь__сжатия текстовых данных и высокую скорость их распаковки щ иЧЙ^еЦАазш «ранении.

БИБЛИОТЕК'

С.Петер! 9Э

Для достижения цели поставлены следующие задачи:

1. Разработка контекстно-словарных моделей сжатия текстовых данных.

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

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

4. Создание программного обеспечения, реализующего разработанные алгоритмы.

5. Проверка эффективности разработанного программною обеспечения на примере организации хранения и передачи учебной информации.

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

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

Результаты, выносимые на защиту

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

1. Объектно-когнитивная модель контекстно-словарного сжатия.

2. Древовидная логическая модель пополняемой базы элементарных единиц словообразования (морфем).

3. Контекстно-словарные алгоритмы сжатия текстовых данных с использованием элементов статистического прогнозирования.

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

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

В диссертации получены следующие результаты, характеризующиеся научной новизной:

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

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

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

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

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

Разработан программный комплекс MSV Quick Reader, использующий реализованные алгоритмы сжатия. Экспериментальная проверка эффективности предложенных алгоритмов контексгно-словарного сжатия текстовых данных с помощью данного комплекса показала, что опи обеспечивают увеличение степени сжатия для текстовых данных по сравнению с известными его вариантами и как следствие, снижение трафика компьютерных сетей на 5 - 7 %. Использование программного комплекса MSV Quick Reader при электронном обучении позволяет существенно увеличить объемы хранимой в компьютере и передаваемой по компьютерным сетям учебной информации, при одних и тех же характеристиках используемых компьютеров.

Реализация и внедрение результатов работы

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

Апробация работы

Основные положения, представленные в диссертационной работе, докладывались всероссийских и международных конференциях (VI международный симпозиум Intels'2004 (г.Саратов, 2004), V международная научная техническая конференция "Проблемы Техники и Технологий Телекоммуникаций» (г.Самара, 2004); 7-й Международная конференция по проблемам информатики и информационных технологий CSIT'2005 (г.Уфа, 2005)), обсуждались и получили положительную оценку. Достоверность основных результатов работы подтверждена корректным использованием методов поиска информации в иерархических (древовидных) моделях представления данных, теории цепей Маркова,

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

Связь темы с плановыми исследованиями

Диссертационная работа выполнялась в рамках госбюджетного финансирования кафедре информатики Уфимского государственного авиационного технического университета и кафедре профаммирования и вычислительной математики Башкирского государственного педагогического университета, а также в рамках внутривузовского гранта «05.02. Информационные технологии в образовании» (БГПУ).

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

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

Диссертация состоит из введения, четырех глав, заключения, библиографии и 2-х приложений. Работа содержит 96 страницы машинописного текста, 46 страниц приложений и 79 наименований библиографических источников.

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

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

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

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

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

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

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

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

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

древовидная модель словаря ссылок, упрощающая восстановление словаря, используемого для кодирования основного текста. Предложена реляционная модель словаря морфем в виде 4-х-местного кортежа И. = { Г], Г2, г3 , г4}, где г, - порядковый номер (ключ отношения), г2 - морфем, г3 -двоичный код переменной длины, г4 - частота встречаемости в словаре

На рис. 1 показан модель реализации данного способа ежа гая текстовых данных.

>ч

Заголовок файла ^ ^ морфемы

Закодированная часть Древообразная

текста модель словаря

Рис. 1 Структурпая модель представления сжатия текстовой информации

Процесс сжатия текста выглядит следующим образом:

1. построение реляционной модели словаря исключением повторов;

2. сортировка по частоте встречаемости и длине;

3. построение кода;

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

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

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

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

существующие ограничения, можно заметить, что при составлении слов прослеживается иерархическая структура.

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

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

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

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

3. В случае совпадения морфем соответствующего уровня, осуществляется переход на следующий уровень. В случае отсутствия добавляется новая ветка.

4. После окончания обработки каждой ветке присваивается соответствующий контекст.

Уровень 1

1

2 е

3 жа

4 жи

5 ма

6 мое

7 с

8 тие

9 щие

10 ю

Уровень 6

Рис. 2 Модель представления словаря (пример кодирования фрагмента словаря «сжатие, сжимаемое,_сжимающие,_» )

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

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

где

" 1 к к

Ас»-- (3.1)

(3.2)

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

Рис. 2 Модель процесса сжатия текстового файла

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

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

Показана возможность использования разработанных алгоритмов в сочетании с алгоритмами поиска на основе хеш-таблиц. Это позволяет достичь максимальной скорости поиска совпадающих последовательностей бинарных кодов для объектов контекстно-словарного сжатия.

(

а) Выявление структуры и построение модели

6) Построение и проведение кодирования на основе выявленных структур

в) Преобразование словаря (разбиение по составу)

С

Блок №3

I)

1 >

Построение контекстных кодов пеоеменной длины

< ■

Кодирование текстового файла на основе построенных контекстных кодов

Конец блока №2

Для 1=0 до конца словаря

Получаем слово из словаря ♦

Разбиваем слово на слоги (морфемы) правилами грамматики

Добавление полученной последовательности слогов в древовидный словарь в виде ссылок на морфемы

С

Конец блок N113

5

Рис. 3 Приведение структурированному виду текстовых данных (а) Выявление структуры и построение модели, б) Построение и проведение кодирования на основе выявленных структур, в) Преобразование словаря (разбиение по составу)

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

мсшьзоватевдм

Рис 4 Модель программного комплекса MSV Quick Reader

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

9 • - в

Рис. 5 Реализация блока сжатия текстового файла

Рис 6 Реализация распаковки тестового файла

* * . -

Для проверки эффективности разработанного алгоритма было проведено сравнение -модуля сжатия, использующий реализованной в дайной paöoie алгоритм сжатия, с известными программами, имеющими наилучшие показатели по степени сжатия и/или скорости кодирования и декодирования.

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

• научные статьи в формате Plain Text, HTML;

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

Сравнение проводилось на компьютере со следующими характеристиками: процессор Intel Pentium III 866 МГц, 128 Мб оперативной памяти, операционная система Windows ХР.

Для каждой программы измерялись следующие показатели: размер сжатых данных; время кодирования; время декодирования.

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

4 -9tS<*------------

рис 7а Результаты сравнения программ сжатия дм тестового набора файлов (по коэффициенту сжатия)

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

1. Выбранный метод сжатия сжимает данные лучше из всех представленных методов сжатия на 5-7%.

Время упаковки

рис 76 Результаты сравнения программ сжатия для тестового набора файлов (по времени упаковки)

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

Время распаковки

0,45 0,4 0 35 0,3 0,25 0,2 0,15 0,1 0 05 0

-0,237-0-349

; 'К -

Ш-

е?

/ ^

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

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

Русский Английский Немецкий Французский

□ твуСотргеввОГ Ш1_гМА Я(?К ВСАВ И АСЕ «Вг1Р2 ИКАР ОРР1Ш ИРКг1Р

рис. 8 График сравнения коэффициента сжатия от языковых особенностей

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Показана целесообразность использования системной формы (типа «сущность - связь») представления при сжатии текстовой информации на естественных языках. Это позволяет за счет знаний правил словообразований, принятых в том или ином естественном языке, принципиально обеспечить возможность достижения более высокой степени сжатии текстовой информации.

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

3. Предложена древовидная модель словаря ссылок, упрощающая восстановление словаря, используемого для кодирования основного текста.

4. Предложена реляционная модель словаря морфем в виде 4-х-местного кортежа г = {ггъ гз, г4}, где г/- порядковый номер (ключ отношения), г2 - морфем, г} - двоичный код переменной длины, /у- частота встречаемости в словаре.

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

• Замена ссылками на тезаурус сжимаемого текста и построение тем самим тезауруса;

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

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

7 Показана возможность использования разработанных алгоритмов в сочетании с алгоритмами поиска на основе хеш-таблиц. Это позволяет достичь максимальной скорости поиска совпадающих последовательностей бинарных кодов для объектов контекстно-словарного сжатия.

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ю.С. Кабальнов, C.B. Максимов, И.В. Павлов. Сжатие информации использованием статистических прогнозирующих моделей //Проблемы техники и технологий телекоммуникаций: Материалы конф / V международная научная техническая конференция. - Самара, 2004, С. 154-156.

2. C.B. Максимов. Алгоритм передачи данных в телекоммуникационных системах // Вестник МаГУ: Периодический научный журнал. Вып.5 Естественные науки. - Магнитогорск. МаГУ, 2004 - С.330.

3. Ю.С. Кабальнов, Т.В. Микова, C.B. Максимов. Интеллектуальные алгоритмы организационной поддержки практического цикла обучения // Интеллектуальные системы: Труды шестого международного симпозиума: Под ред. К.А.Пулкова. - М.:РУСАКИ, 2004. - С. 458-460

4 Ю.С. Кабальнов, C.B. Максимов Сжатие текстовых данных с учетом особенностей словообразования в русском языке // Ученые записки: сб. науч. статей. Вып.7 - Уфа: БГПУ, 2005. - С. 238-241.

5 Ю.С. Кабальнов, C.B. Максимов, C.B. Павлов. Модели и алгоритмы сжатия информации применением цепей Маркова // Международная конференция CSIT-2005, Уфа, 18-21 сентября 2005 4.1. / УГАТУ - Уфа, 2005. - С. 85-91(на англ.яз.)

6. C.B. Максимов. Древовидная модель словаря представления слов // ЭВТ в обучении и моделировании: Сб. науч. тр./ Бирск, 2005. - 4.2. - С. 201-205.

Соискатель

С.В.Максимов

Максимов Сергей Владимирович

МОДЕЛИ И АЛГОРИТМЫ КОНТЕКСТНО-СЛОВАРНОГО СЖАТИЯ ТЕКСТОВЫХ ДАННЫХ (применительно к системам электронного обучения)

Специальность 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Подписано в печать 13.03.2006. Формат 60x84 1/16 Бумага офсетная Печать плоская. Гарнитура Times New Roman. Усл. печ. л. 1,0. Усл. кр.-отт. 0,9. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ № 92

Уфимский государственный авиационный технический университет Центр оперативной полиграфии УГАТУ 450000, г Уфа-центр, ул. К.Маркса, 12

»-7 146

!

а»

J

/

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ МЕТОДОВ СЖАТИИ ИНФОРМАЦИИ.

1.1. Предварительные замечания.

1.2. Модели словарного сжатия.

1.3. Модели контекстного сжатия.

1.3.1. Модели с фиксированным контекстом.

1.3.2. Контекстуально-смешанные модели.

1.3.3. Вероятность ухода.

1.3.4. Исключения.

1.3.5. Алфавиты.

1.4. Другие методы статистического моделирования.

1.4.1. Динамическое сжатие Маркова.

1.4.2. Грамматические модели.

1.4.3. Модели новизны.

1.4.4. Выводы по первой главе.

ГЛАВА 2. КОНТЕКСТНО-СЛОВАРНЫЕ МОДЕЛИ СЖАТИЯ.

2.1. Предварительные замечания.

2.2. Сжатие текстовых файлов.

2.3. Структурная модель представления сжатия текстовой информации

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

2.5. Модель сжатия использующий контекстно-словарный метод.

2.5.1. Модель хранения сжатого текста.

2.5.2. Древовидная модель словаря.

2.5.3. Модель словаря морфем.

2.6. Выводы по второй главе.

ГЛАВА 3. АЛГОРИТМЫ КОНТЕКСТНО-СЛОВАРНОГО СЖАТИЯ ДАННЫХ НА ОСНОВЕ ПРЕДЛОЖЕННЫХ МОДЕЛЕЙ.

3.1. Предварительные замечания.

3.2. Приведение информации к структурированному виду.

3.3. Преобразование словаря.

3.3.1. Разбиение слова на слоги.

3.3.2. Разбиение на составные части слова.

3.3.3. Древовидное представление структуры словаря.

3.4. Оценка построение структуры словаря от способа разложения слов.

3.5. Кодирование текста с использованием полученного словаря.

3.5.1. Построение кодов переменной длины.

3.5.2. Применение кодирования контекстных индексов арифметического кодирования.

3.6. Оценка эффективности полученных кодов алгоритма кодирования с помощью словаря.

3.6.1. Стоимость кодирования текста.

3.6.2. Оценка объема необходимой памяти.

3.7. Управление распределением памяти.

3.8. Выводы по третьей главе.

ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС КОНТЕКСТНО

СЛОВАРНОГО СЖАТИЯ ТЕКСТОВЫХ ДАННЫХ MSV QUICK READER

4.1. Основные требования к техническому облику программного комплекса MSV Quick Reader.

4.2. Область применения программного комплекса.

4.3. Проблемы существующих систем.

4.4. Задачи разработки программного комплекса.

4.5. Этапы разработки программного комплекса.

4.6. Реализация блока сжатия файлов.

4.6.1. Реализация блока Compress.

4.6.2. Реализация блока Decompress.

4.7. Сравнительная оценка эффективности.

4.7.1. Тестовые данные.

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

4.7.3. Результаты сравнения.

4.8. Пример преобразования и кодирования слов.

4.9. Выводы по четвертой главе.

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

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

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

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

- затрачивается время на определение структуры, выявление правил и т.д.

- необходимо следить за целостностью данных в течение всего времени обработки.

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

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

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

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

- выносить за пределы сжимаемого файла часто встречаемые данные, включая их в комплект программного обеспечения;

- исключает повторную упаковку встречаемого объекта;

- сокращает затраты на преобразование сжимаемого объекта.

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

Приведение к структурированному виду позволяет улучшить параметры сжатия по сравнению со сжатием неструктурированных данных, что приводит к следующему:

1) увеличивается скорость обработки данных, которая идет уже по полученному шаблону и не требует дополнительных вычислений;

2) исключается необходимость многократного сохранения всего шаблона в выходном файле, так как модель шаблона сохраняется на начальном этапе, либо уже содержится в комплекте программного обеспечения;

3) данные быстрее восстанавливаются;

4) модель сохраняется на начальном этапе, то соответственно в выходной файл отправляются только подвергающиеся изменению данные;

5) уменьшается объем передаваемой информации и увеличивается скорость передачи данных.

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

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

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

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

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

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

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

При решении поставленной задачи автор опирался на труды Д. Ватолина, А. Ратушняка, А. Смирнова, М. Смирнова, В. Юкина, И. Ножова,

И.В. Павлова, А.В. Кадача, Д. Мастрюков, Д.Сэломона, Д.Е.Кнута и других ученых.

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

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

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

Цель диссертационной работы

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

Задачи исследования

Для достижения цели поставлены следующие задачи:

1. Разработка контекстно-словарных моделей сжимающих текстовые данные.

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

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

4. Создание программного обеспечения, реализующего разработанные алгоритмы.

5. Проверка эффективности разработанного программного обеспечения на примере организации хранения и передачи учебной информации.

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

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

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

1. Объектно-когнитивная модель контекстно-словарного сжатия.

2. Древовидная логическая модель пополняемой базы элементарных единиц словообразования (морфем).

3. Контекстно-словарные алгоритмы сжатия текстовых данных с использованием элементов статистического прогнозирования.

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

Научная новизна работы заключается в следующем:

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

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

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

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

Практическая значимость работы:

1. Разработан программный комплекс MSV Quick Reader, использующий реализованные алгоритмы сжатия. Экспериментальная проверка эффективности предложенных алгоритмов контекстно-словарного сжатия текстовых данных с помощью данного комплекса показала, что они обеспечивают увеличение степени сжатия для текстовых данных по сравнению с известными его вариантами и как следствие, снижение трафика компьютерных сетей на 5 - 7 %.

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

3. Программный комплекс MSV Quick Reader внедрен в Башкирском государственном педагогическом университете и в настоящее время используется на кафедре программирования и вычислительной математики. Программное обеспечение данного комплекса имеет открытую архитектуру, что позволяет развивать данный программный комплекс с помощью добавления соответствующих модулей.

Связь темы с плановыми исследованиями

Диссертационная работа выполнялась в рамках госбюджетного финансирования кафедре информатики Уфимского государственного авиационного технического университета и кафедре программирования и вычислительной математики Башкирского государственного педагогического университета, а также в рамках внутривузовского гранта «05.02. Информационные технологии в образовании» (БГПУ).

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

Диссертация состоит из введения, четырех глав, заключения, библиографии и 2 приложения. Работа содержит 96 страницы машинописного текста, 46 страниц приложения и 79 наименований библиографических источников.

4.9. Выводы по четвертой главе

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

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

89

Заключение

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

1) В рамках работы был произведен анализ существующих подходов сжатия данных.

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

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

4) Экспериментальная проверка эффективности предложенных алгоритмов контекстно-словарного сжатия текстовых данных с помощью данного комплекса показала, что они обеспечивают увеличение степени сжатия для текстовых данных по сравнению с известными его вариантами и как следствие, снижение трафика компьютерных сетей на 5 - 7 %. Решает следующие задачи:

- систематизацию текстовых данных;

- хранение учебной информации;

- передачу учебной информации по линиям связи;

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

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

1. Ватолин Д., Ратушняк А., Смирнов А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М:. ДИАЛОГ - МИФИ, 2002. - 384 с.

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

3. Вадим Юкин. Операция BWT, или новые методы сжатия. // Hard&Soflt. -2001 -№4-С.80-85.

4. Игорь Ножов. Синтаксический анализ // "Компьютерра" 2002. - №21

5. Кнут Д.Е. Искусство программирования. Т. 1. Основные алгоритмы. 3-е изд. — М.: Вилиямс, 2000. — 720 с.

6. Кнут Д.Е. Искусство программирования. Т.З: Сортировка и поиск. 2-е изд. — М.: Вилиямс, 2000. — 822с.

7. Кабальнов Ю.С., Максимов С.В., Павлов И.В. Сжатие информации с использованием статистических прогнозирующих моделей. // Ежегодной международной конференция "Проблемы Техники и Технологий Телекоммуникаций» г. Самара, 2004

8. Кабальнов Ю.С. Максимов С.В. Сжатие текстовых данных с учетом особенностей словообразования в русском языке. // Ученые записки: Сб. Науч. Статей: вып.7 Уфа: БГПУ 2005. с.238-241

9. Кабальнов Ю.С., Микова, Максимов С.В. Интеллектуальные алгоритмы организационной поддержки практического цикла обучения. // Интеллектуальные системы: Труды шестого международного симпозиума: Под ред. К.А.Пупкова. М.:РУСАКИ, 2004. С458-460.

10. Кадач А.В. Эффективные алгоритмы неискажающего сжатия текстовой информации. Диссертация. — Новосибирск, 1997.

11. Лекции по структуральной поэтике// Ю. М. Лотман и тартуско-московская семиотическая школа. М., 1994. С. 11-246.

12. Максимов С.В. Древовидная модель словаря представления слов. // ЭВТ в обучении и моделировании: Сб. научн. тр.: в 2-х ч. Бирск: 2005. С.

13. Мастрюков Д. Алгоритмы сжатия информации. Часть 1. Сжатие по Хаффмену // Монитор.— 1993. — N 7-8. — С. 14-24.

14. Мастрюков Д. Алгоритмы сжатия информации. Часть 2. Арифметическое кодирование // Монитор.— 1994. —N 1. — С. 20-27.

15. Мастрюков Д. Алгоритмы сжатия информации. Часть 3. Алгоритмы группы LZ // Монитор.— 1994. — N 2. — С. 10-19.

16. М.Вернер. Основы кодирования. Учебник для ВУЗов. М:. Техносфера, 2004.-288 с.

17. Налимов В.В. Вероятностная модель языка. О соотношении естественных и искусственных языков. М., «Наука», 1974, 272 с.

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

19. Потапов В.Н. Теория информации. Кодирование дискретных вероятностных источников. Учебное пособие.—Новосибирск, 1999.-71 с.

20. М А. Смирнов. (1999) PPMN РРМ-компресор. hllpy/www.rarr^i^ion.ru/ms/

21. Шеннон К. Работы по теории информации и кибернетике. М.: Издательство иностранной литературы, 1963. — 829 с.

22. Шанский Н.М. Русский язык. Лексика. Словообразование. Пособие для учителя. М., «Просвещение», 1975. -239 с.

23. Angluin D. and Smith C.H. 1983. Inductive inference: Theory and methods. Comput.Surv. 15, 3(Sept.), 237-269.

24. Auslander M., Harrison W., Miller V., and Wegman M. 1985. PCTERM: A terminal emulator using compression. In Proceedings of the IEEE Globecom'85. IEEE Press, pp.860-862.

25. Baum L.E., Petrie Т., Soules G. and Weiss N. 1970. A maximization technique occuring in the statistical analysis of probabilistic functions of Markov chains. Ann. Math. Stat.41, pp.164-171.

26. Bell T.C. and Moffat A.M. 1989. A note on the DMC data compression scheme. Computer J. 32, l(Feb.), pp. 16-20.

27. Bell T.C. 1987. A unifying theory and improvements for existing approaches to text compression. Ph.D. dissertation, Dept. of Computer Science, Univ. of Canterbury, New Zealand.

28. Bell T.C. and Witten I.H. 1987. Greedy macro text compression. Res. Rept.87/285/33. Department of Computers Science, University of Calgary

29. Bell T.C. and Moffat A.M. 1989. A note on the DMC data compression scheme. Computer J. 32,1 (Feb.), 16-20.

30. Bentley J.L., Sleator D.D., Tarjan R.E. and Wei V.K. 1986. A locally adaptive data compression scheme. Commun. 29, 4(Apr.), 320-330.

31. Cameron R.D. 1986. Source encoding using syntactic information source model. LCCR Tech. Rept. 86-7, Simon Fraser University.

32. Cleary J.G. 1980. An associative and impressible computer. Ph.D. dissertation. Univ. of Canterbury, Christchurch, New Zealand.

33. Cleary J.G. and Witten I.H. 1984b. Data compression using adaptive coding and partial string matching. IEEE Trans. Commun. COM-32, 4(Apr.), pp.396402.

34. Cormack G.V. and Horspool R.N. 1984. Algorithms for adaptive Huffman codes. Inf.Process.Lett. 18, 3(Mar.), 159-166.

35. Cormack G.V. and Horspool R.N. 1987. Data compression using dynamic Markov modelling. Comput. J. 30,6(Dec.), 541-550

36. Cover T.M. and King R.C. 1978. A convergent dambling estimate of the entropy of English. IEEE Trans. Inf. Theory IT-24, 4(Jul.), pp.413-421.

37. Elias P. 1987. Interval and recency rank source coding: Two on-line adaptive variable-length schemes. IEEE Trans. Inf. Theory IT-33, l(Jan.), pp.3-10.

38. Elias P. 1975. Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory IT-21, 2(Mar.), pp. 194-203.

39. El Gamal A.A., Hemachandra L.A., Shperling I. and Wei V.K. 1987. Using simulated annealing to design good codes. IEEE Trans. Inf. Theory, IT-33, 1, pp.116-123.

40. Faller N. 1973. An adaptive system for data compression. Record of the 7th Asilomar Conference on Circuits, Systems and Computers. Naval Postgraduate School, Monterey, CA, pp.593-597.

41. Gallager R.G. 1978. Variations on a theme by Huffman. IEEE Trans.Inf.Theory IT-24, 6(Nov.), pp.668-674.

42. Gold E.M. 1978. On the complexity of automation identification from given data. Inf.Control 37, 302-320.

43. Gonzalez-Smith M.E. and Storer J.A. 1985. Parralel algorithms for data compression. J.ACM 32, 2, pp.344-373.

44. G. & C. Merriam Company 1963. Webster's Seventh New Collegiate Dictionary. Springfield, MA.

45. Horspool R.N. and Cormack G.V. 1986. Dynamic Markov modelling A prediction technique. In Proceedings of the International Conference on the System Sciences, Honolulu, HI, pp.700-707.

46. Horspool R.N. and Cormack G.V. (1983). Data compression based on token recognition. Unbublished.

47. Huffman D.A. 1952. A method for the construction of minimum redundancy codes. In Proceedings of the Institute of Electrical and Radio Engineers 40, 9(Sept.), pp. 1098-1101.

48. Huffman D.A. 1952. A method for the construction of minimum redundancy codes. In Proceedings of the Institute of Electrical and Radio Engineers 40, 9(Sept.), pp. 1098-1101.

49. Hunter R. and Robinson A.H. 1980. International digital facsimile coding standarts. In Proceedings of the Institute of Electrical and Electronic Engineers 68, 7(Jul.), pp.854-867.

50. Jagger D. 1989. Fast Ziv-Lempel decoding using RISC architecture. Res. Rept., Dept. of Computer Science, Univ. of Canterbury, New Zealand.

51. Jones D.W. 1988. Application of splay trees to data compression. Commun. ACM 31, 8(Aug.), pp.996-1007.

52. Katajainen J., Renttonen M. and Teuhola J. 1986. Syntax-directed compression of program files. Software-Practice and Experience 16, 3, 269276.

53. Knuth D.E. 1985. Dynamic Huffman coding. J. Algorithms 6, pp. 163-180.

54. Langdon G.G. and Rissanen J J. 1981. Compression of black-white images with arithmetic coding. IEEE Trans.Commun.COM-29, 6(Jun.), pp.858-867.

55. Langdon G.G. and Rissanen J.J. 1982. A simple general binary source code. IEEE Trans. Inf. Theory IT-28 (Sept.), pp.800-803.

56. Levinson S.E., Rabiner L.R. and Sondni M. 1983. An introduction to the application of the theory of probabilistic function of a Markov process to automatic speech recognition. Bell Syst. Tech. J. 62, 4(Apr.), pp.1035-1074.

57. Lelewer D.A. and Hirschberg D.S. 1987. Data compression. Comput. Surv. 13, 3(Sept.), pp.261-296.

58. Lempel A. and Ziv J. 1976. On the complexity of finite sequences. IEEE Trans. Inf. Theory IT-22,1 (Jan.),75-81.

59. Moffat A. 1987. Word based text compression. Res. Rept., Dept. of Computer Science, Univ. of Melbourne, Victoria, Australia.

60. Moffat A. 1988a. A data structure for arithmetic encoding on large alphabets. In Proceeding of the 11th Australian Computer Science Conference. Brisbane, Australia (Feb.), pp.309-317.

61. Moffat A. 1988b. A note on the PPM data compression algorithm. Res.Rept.88/7, Dept. of Computer Science, Univ. of Melbourne, Victoria, Australia.

62. Ozeki K. 1974a. Optimal encoding of linguistic information. Systems, Computers, Controls 5, 3, 96-103. Translated from Denshi Tsushin Gakkai Ronbunshi, Vol.57-D, N0.6, June 1974, pp.361-368.

63. Ozeki К. 1974b. Stochastic context-free grammar and Markov chain. Systems, Computers, Controls 5, 3, 104-110. Translated from Denshi Tsushin Gakkai Ronbunshi, Vol.57-D, No.6, June 1974, pp.369-375.

64. Rabiner L.R. and Juang B.H. 1986. An Introduction to Hidden Markov models. IEEE ASSP Mag. (Jan.).

65. Rissanen J.J. 1983. A universal data compression system. IEEE Trans. Inf. Theory IT-29, 5(Sept.), pp.656-664.

66. Rissanen J.J. and Langdon G.G. 1981. Universal modeling and coding. IEEE Trans. Inf. Theory IT-27, l(Jan.), pp. 12-23.

67. Roberts M.G. 1982. Local order estimating Markovian analysis for noiseless source coding and authorship identification. Ph. D. dissertation. Stanford Univ.

68. Ryabko B.Y. 1980. Data compression by means of a "book stack". Problemy Peredachi Informatsii 16, 4.

69. Schwartz E.S. A dictionary for minimum redundancy encoding // J. ACM. -1963. Vol. 10, № 4. - P. 413-439.

70. Vitter J.S. 1987. Design and analysis of dynamic Huffman codes. J.ACM 34, 4(Oct.), 825-845.

71. Williams R. 1988. Dynamics-history predictive compression. Inf.Syst. 13, 1, pp. 129-140

72. Witten I.H. and Cleary J. 1983. Picture coding and transmission using adaptive modelling of quad trees. In Proceeding of the International Elecrical, Electronics conference 1, Toronto, ON, pp.222-225.

73. Witten I.H., Neal R. and Cleary J.G. 1987. Arithmetic coding for data compression. Commun.ACM 30, 6(Jun.), 520-540.

74. Ziv J. Lempel A. A universal algorithm for sequential data compression // IEEE Trans. Inform. Theory. — 1977. — Vol. 23, N 3. — P. 337-343.

75. Ziv J. Lempel A. Compression of individuals sequences via variable-rate coding // IEEE Trans. Inform. Theory. — 1978. — Vol. 24, N 5. — P. 530536.

76. Young D.M. 1985. Mac Write file formats. Wheels for the mind (Newsletter of the Australian Apple University Consortium), University of Western Australia, Nedlands, WA 6009, Australia, p.34