Моделирование при сжатии текстовых данных вопросы практической реализации


Содержание

Моделирование задач

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

Так передо мной встала серьёзная проблема: как, используя традиционный УМК по математике ( программа М.И.Моро, М.А.Бантовой, Т.В.Бельтюковой ), анализировать задачу более продуктивно, чтобы она из просто арифметической превратилась в развивающую? Можно ли научить самостоятельно решать задачи каждого ученика?
Изучив теоретические подходы к обучению решать задачи, а также разнообразные практические приёмы, я пришла к выводу, что можно. Главное для каждого ученика на этом этапе – понять задачу, т.е. уяснить о чём эта задача, что в ней известно, что нужно узнать, как связаны между собой данные, каковы отношения между данными и искомыми параметрами и т.т. Для этого надо применять моделирование задачи и учить этому детей.

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

Задачи: — разработать методические рекомендации по использованию разных моделей при решении задач;
— накопление дидактического материала, используемого как для всего класса,
так и для индивидуальной работы учащихся;

Я предлагаю пособие, которое рекомендую использовать при изучении важной темы программы по математике: «Решение текстовых задач». Оно может оказать практическую помощь учителям, как в организации работы на уроке, так и в индивидуальной работе в классе и дома.
Методическое пособие содержит следующие разделы:
1. Справочный материал. Виды моделей задач. В нём я кратко рассказываю о видах моделей, которые применимы к задачам , и когда целесообразно с ними знакомить учащихся.

2.Методика работы с каждой моделью.
В пособии показана работа над задачей, используя приём моделирования. Приведены конкретные примеры и предложен фрагмент урока по теме. « Решение задач алгебраическим и арифметическим способом », используя приём моделирования.

3.Приложение. Дидактический материал.
Дидактический материал, который использую на уроке со всем классом, а также в индивидуальной работе.
Так что же такое моделирование? Моделирование-это процесс построения моделей
для каких-либо познавательных целей. Для простоты восприятия учеником какого-либо предмета или ситуации, описанной в задаче, я применяю модель. Постепенно моделирование стало неотъемлемой частью каждого урока математики в моём классе.

Систему работы по усвоению детьми моделирования задачи я разбиваю на три этапа:
1.Обучение детей преобразованию предметных действий в работающую модель.
2.Обучение детей составлению обратных задач к данной на основе работы с моделью.
3.Творческая работа детей над задачей на основе использования модели.
После систематической работы учащиеся добились следующих результатов: изучили
шесть видов моделей; научились применять в одной и той же задаче несколько видов моделей ( с целью выбора каждым учеником наиболее понятной ему модели );
сравнивать несколько моделей между собой ( с целью выбора наиболее рациональной );
выбирать наиболее подходящую к предложенной задаче. На основе моих наблюдений за детьми в процессе этой деятельности я пришла к выводу. Мои ученики не боятся самостоятельно начать анализ задачи; в случае неудачи они, используя другую модель, анализируют задачу вновь.
Следовательно, моделирование помогает вооружить ребёнка такими приёмами, которые позволяют ему при самостоятельной работе над задачей быть активным, успешным, не бояться трудностей. Каждый, не сравнивая себя с другими, выбирает собственный путь рассуждения, моделирования и, следовательно, решения задач.

Справочный материал. Виды моделей.

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

2.Краткая запись. С этой моделью начинаю работать в конце 1-го класса. Удачное введение краткой записи параллельно с рисунком.

3.Таблица. Знакомлю с этой моделью в конце 1-го, начале 2-го класса.

Было Вынесли Осталось Цена Количество Стоимость v t s

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

5.Схема. Знакомлю в начале 2-го класса. Подбор задач в этом классе позволяет применять эту модель на материале обратных задач, при решении задач разными способами.

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

Методика работы с моделями.
1.Рисунок. Он должен изображать реальные предметы (кубики, платки, яблоки и т. д.), о которых говорится в задаче, или условные предметы в виде геометрических фигур.
Пример. Когда с полки сняли 2 книги, там осталось 4. Сколько книг лежало на полке сначала?
У. Сколько книг осталось на полке? 4

У. Раньше книг было больше или меньше? Почему?
Д. Больше. Здесь нет книг, которые сняли с полки.
У. Знаем ли мы, сколько книг было сначала? Нет.
Покажем это скобкой или дугой и вопросительным знаком.

У. Почему книг стало меньше?
Д. С полки сняли две книги.

У. Изобразим две книги внизу, под скобкой.

У. Как узнать, сколько всего книг было на полке?
Д. Нужно сложить книги, которые остались на полке, и те, которые сняли.

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

Было — ?
Подарила – 2к.
Осталось – 5к.

Слово «подарила» говорит младшему школьнику о том, что количество книг уменьшилось, значит, нужно производить вычитание. Так в сравнении дети видят какая из моделей позволяет проследить за количественными изменениями в задаче.
2.Таблица. Наиболее удачно применение таблицы при решении задач на тройку пропорциональных величин: цена – количество – стоимость; расход на 1 шт.- количество штук – общий расход; масса – количество – общая масса; скорость – время – расстояние; и т. д.
Пример. «Из двух городов, расстояние между которыми равно 1200 км, одновременно вышли навстречу друг другу два поезда. Один из них проходит это расстояние за 20ч., а другой – за 30 ч. Через сколько часов поезда встретятся?»
При решении задач на движение, учителя часто используют схематический чертёж.

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

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

2.3.Данный чертёж даёт возможность учащимся представить и осознать задачную ситуацию, что, в свою очередь, помогает понять и закончить решение:60+40=100км/ч; 1200:100=12ч
Вот теперь дети сами могут составить модель задачи , используя таблицу, и выявить все ситуации, все данные и искомые.

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

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

4. Схема –это чертёж, на котором все взаимосвязи и взаимоотношения величин передаются приблизительно, без соблюдения масштаба,

Пример. « Из двух кусков ткани сшили 18 одинаковых занавесок. В первом куске было 30 м , во втором – 24 м. Сколько занавесок сшили из каждого куска?»
Обычно условие записывают в таблицу.

Расход на одно платье

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

Понимание облегчается тем, что на схеме один и тот же отрезок изображает и (30+24)м ткани, и 18 занавесок.

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

Пример. « Когда шланг длинной 5 метров удлинили на несколько метров, то получился шланг длиной 8 метров. На сколько метров удлинили шланг?

Какой длины был сначала шланг? (5 м)
Какой длины вычерчиваем первый отрезок? (5см)
Что произошло со шлангом? (Увеличился на несколько метров.)
Как изменится отрезок?( Увеличится на несколько сантиметров.)
Какой длины стал шланг?(8м)
Какой длины станет наш отрезок?(8см)
Отметим на чертеже , насколько увеличился наш отрезок.
Что нужно узнать в задаче?
Как на нашей модели отмечено искомое?

Далее выбирается арифметическое действие.

Пример. « У Васи 2 машинки, а у Коли в 3 раза больше, чем у Васи. Сколько машинок к Коли? » Чертёж имеет такой вид.

Далее выбирается арифметическое действие.

Фрагмент урока

Тема. Алгебраический и арифметический способ решения задач ( 2 класс )
Цель. — учить решать задачи разными способами;
— развивать умения сравнивать, анализировать, делать вывод;
— воспитание самостоятельности, творческой активности;
Ход урока.

1.Актуализация опорных знаний

— Составь разные задачи по выражению
28 — 16
— Выбери модели к этим задачам
Дети выходят к доске и из предложенных моделей выбирают следующие:

2. Освоение новых знаний

— Какая из ваших моделей подойдёт к этому уравнению?
28 – Х = 16

После сравнения и обсуждения дети выбирают

— Проговорите текст задачи. ( В магазине было 28 ящиков груш, когда несколько продали , осталось 16. Сколько ящиков груш продали?)
— Решим это уравнение. Какой компонент неизвестен? Как его найти?
Мы использовали уравнение для решения задачи . Это алгебраический способ решения задачи. ( Вывешиваю аншлаг слова алгебра. Поясняю, что алгебра это раздел математики, который изучает буквенные выражения ,)
А теперь решите эту задачу арифметическим способом ( Вывешиваю аншлаг слова
арифметика и поясняю, что это раздел математики, который изучает свойства чисел и действия над ними,)

На доске появляется такая запись

Делаем с ребятами вывод о том, что одну и ту же задачу можно решить разными способами .
-А как помогают модели в решении задачи? ( Помогают выбрать способ её решения )

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

Модели и алгоритмы контекстно-словарного сжатия текстовых данных Максимов Сергей Владимирович

480 руб. | 150 грн. | 7,5 долл. ‘, MOUSEOFF, FGCOLOR, ‘#FFFFCC’,BGCOLOR, ‘#393939’);» onMouseOut=»return nd();»> Диссертация — 480 руб., доставка 10 минут , круглосуточно, без выходных и праздников

Автореферат — бесплатно , доставка 10 минут , круглосуточно, без выходных и праздников

Максимов Сергей Владимирович. Модели и алгоритмы контекстно-словарного сжатия текстовых данных : 05.13.11 Максимов, Сергей Владимирович Модели и алгоритмы контекстно-словарного сжатия текстовых данных (Применительно к системам электронного обучения) : Дис. . канд. техн. наук : 05.13.11 Уфа, 2006 133 с. РГБ ОД, 61:06-5/2212

Содержание к диссертации

ГЛАВА 1. Анализ методов сжатии информации 14

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

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

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

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

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

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

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

1.3.5. Алфавиты 24

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

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

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

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

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

ГЛАВА 2. Контекстно-словарные модели сжатия 30

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

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

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

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

структурированного вида 36

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

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

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

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

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

ГЛАВА 3. Алгоритмы контекстно-словарного сжатия данных на основе предложенных моделей 46

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

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

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

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

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

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

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

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

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

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

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

помощью словаря 63

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

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

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

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

ГЛАВА 4. Программный комплекс контекстно-словарного сжатия текстовых данных msv quick reader 69

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение к работе

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

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

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

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

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

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

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

7.^ — исключает повторную упаковку встречаемого объекта; — сокращает затраты на преобразование сжимаемого объекта.

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

Ы позволяет выбрать наиболее эффективные правила ее упаковки в базу данных.

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

1) увеличивается скорость обработки данных, которая идет уже по полученному шаблону и не требует дополнительных вычислений; Щ 2) исключается необходимость многократного сохранения всего шаблона в выходном файле, так как модель шаблона сохраняется на начальном этапе, либо уже содержится в комплекте программного обеспечения; данные быстрее восстанавливаются; модель сохраняется на начальном этапе, то соответственно в выходной файл отправляются только подвергающиеся изменению данные; 4 5) уменьшается объем передаваемой информации и увеличивается скорость передачи данных.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10^ Результаты исследований, выполненных в работе, базируются на методах математической статистики, теории информации, теории цепей Маркова, теории исследования операций, принципах морфемного и словообразовательного анализа состава. На защиту выносятся:Ш 1. Объектно-когнитивная модель контекстно-словарного сжатия.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Во второй главе показана целесообразность использования системной формы (типа «сущность — связь») представления при сжатии текстовой данных на естественных языках. На основе использования системной формы предложены модели реализации контекстно-словарного сжатия текстовых данных.

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

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

13 Заключение содержит основные результаты и выводы по диссертационной работе.

Апробация работа и публикации

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

Основные материалы, представленные в диссертационной работе опубликованы в 7 работах.

Результаты диссертационной работы внедрены в Башкирском государственном педагогическом университете и в настоящее время используется на кафедре программирования и вычислительной математики. ф Глава 1. Анализ методов сжатии информации

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

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

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

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

В настоящее время лучшие схемы достигают сжатия в 2.3 — 2.5 битов/символ для английского текста. Показатель иногда может быть немного улучшен за счет использования больших объемов памяти, но преодолеть рубеж в 2 бита/символ еще не удавалось. Обычные люди достигали результата в 1.3 бита/символ при предсказании символов в іл английском тексте [36]. Хотя обычно это принимается за нижнюю границу, но теоретических причин верить, что хорошо тренированные люди или системы ЭВМ не достигнут большего, не существует. В любом случае, несомненно, существует много возможностей для улучшения алгоритмов сжатия.

Одним направлением для исследований является подгонка схем сжатия Щ> к отечественным языкам. Сегодняшние системы работают полностью на лексическом уровне. Использование больших словарей с синтаксической и семантической информацией может позволить машинам получить преимущество от имеющейся в тексте высокоуровневой связности. Однако необходимо иметь в виду, что очень большое количество слов обычного ‘Щ английского текста в обычном английском словаре может быть не найдено. ^ Данный факт касается и остальных языков. Например, Уолкер и Эмслер [73] проверили 8 миллионов слов из New York Times News Service для Webster’s Seventh New Collegiate Dictionary [58] и обнаружили, что в словаре отсутствовало почти 2/3 (64%) слов (они подсчитали, что около 1/4 из них -грамматические формы слов, еще 1/4 — собственные существительные, 1/6 —

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

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

Второй подход диаметрально противоположен описанному выше наукоемкому направлению, и состоит в поддержании полной адаптивности ^| системы и поиске улучшений в имеющихся алгоритмах. Необходимы лучшие пути организации контекстов и словарей. Например, еще не обнаружен пригодный метод построения моделей состояний; показанный метод DMC -лишь форма контекстно-ограниченной модели [27]. Тонкости роста этих сжимаемых данных, вероятно значительно влияют на сжатие, но, несмотря на статью Уильямса [74], этот вопрос еще не был исследован систематично.

It Другой актуальной темой для исследований являются методы выделения кодов ухода в частично соответствующих контекстуальных моделях. В итоге, преобразование систем, определяемых состояниями, таких как скрытые модели Маркова [63], может дать новые идеи моделям состояний сжатия текстов. Например, алгоритм Баума-Уэлча определения скрытых моделей ф Маркова [26] в последнее время был вновь открыт в области распознавания речи [57]. Он может быть успешно применен для сжатия текстов, равно как и для техники глобальной оптимизации, такой как моделирование обжига [38]. Недостаток этих методов состоит в их значительных временных затратах, что позволяет сейчас эксплуатировать довольно небольшие модели с десятками и сотнями, а не тысячами и более состояний. ‘Щ Поиски более быстрых алгоритмов, сильно влияющих на развитие методов сжатия текстов, будут, несомненно, продолжены в будущем. Постоянный компромисс между стоимостями памяти и вычислений будет стимулировать дальнейшую работу над более сложными системами данных, требующими больших объемов памяти, но ускоряющих доступ к хранимой информации. Применение архитектуры RISC, например в [51], разными путями воздействует на баланс между хранением и выполнением. Будет ^ развиваться аппаратура, например, исследователи экспериментируют с арифметическим кодированием на микросхеме, тогда как Гонзалес-Смит и Сторер [43] разработали для сжатия Зива-Лемпела параллельные алгоритмы поиска. Увеличение вариантов аппаратных реализаций будет стимулировать и разнообразить исследования по улучшению использующих их алгоритмов.

Последняя область — это разработка и реализация новых систем, ki включающих сжатие текстов. Существует идея объединения в единую систему ряда распространенных программ разных областей применения, включая текст-процессор MaxWrite [79], цифровой факсимильный аппарат [49], сетевую почту и новости (например, UNIX «net-news») и архивацию файлов (например, программы ARC и PKARC для IBM PC, которые часто применяются для распределяемого ПО из электронных бюллетеней). Для Щ увеличения скорости и сокращения стоимости большинство этих систем используют удивительно простые методы сжатия. Все они представляют собой потенциальные сферы применения для более сложных методов моделирования.

17 Актуальным является объединение адаптированного сжатия с дисковым контроллером для сокращения использования диска. Это поднимает интересные системные проблемы, частично которые заключаются в сглаживании взрывного характера вывода алгоритмов сжатия, но в основном в согласовании случайного характера доступа к дисковым блокам с требованиями адаптации к разным стилям данных. Сжатие имеет значительные преимущества для конечного движения — некоторые высокоскоростные модемы (например, Racal-Vadic’s Scotsman) и конечные эмуляторы уже имеют адаптивные алгоритмы. В будущем полностью цифровые телефонные сети радикально изменят характер конечного движения и, вообще, сферу локальных сетей. Эффективность сжатия трудно оценить, но эти усовершенствования определенно будут давать преимущество в скорости реализации.

Еще одной сферой применения является шифрование и защита данных [75]. Сжатие придает хранимым и передаваемым сообщениям некоторую степень секретности. Во-первых, оно защищает их от случайного наблюдателя. Во-вторых, посредством удаления избыточности оно не дает возможности криптоаналитику установить присущий естественному языку статистический порядок. В-третьих, что самое важное, модель действует как очень большой ключ, без которого расшифровка невозможна. Применение адаптивной модели означает, что ключ зависит от всего текста, переданного системе кодирования/раскодирования во время ее инициализации. Также в качестве ключа может быть использован некоторый префикс сжатых данных, определяющий модель для дальнейшего раскодирования [52].

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

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

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

Выходной поток Рис. 1 Модель сжатия реляционным словарем

Такой способ сжатия файла имеет как положительные, так и отрицательные стороны.


К положительной стороне такого метода сжатия необходимо отнести:

1. Размер сжатого файла получается компактный.

2. Словарь хранится отдельно от сжатого файла и входит в комплект программного обеспечения.

3. Нет необходимости строить модель и подсчитывать статистику.

4. Декодирование выполняется быстро, так как файл содержит ссылки на место положения слова в словаре.

Необходимо также отметить и отрицательные стороны:

1. Скорость распаковки зависит от размера словаря.

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

Плохо сжимает разнородные данные, подходит для сжатия текстовых файлов.

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

Динамический словарь содержит последовательности, ранее поступившие из входного файла, при этом разрешается добавлять и удалять эти последовательности по мере чтения из входного файла. Примером модели сжатия динамическим словарем является модель со скользящим окном. [1,2, 77, 78]

Скользящее окно rz.

Динамический словарь содержит последовательности, ранее поступившие (1 АД) (1,0,и) О Ан) (1 Да) (1 Дм) (4,1,4) (1 Де) (1 Де) (1 Дк) (5,1,й) (1,0, « » ) (5)1,л)

Рис. 2 Модель сжатия динамическим словарем

Отметим положительные стороны: нет необходимости сохранять словарь; алгоритмы универсальны; высокая скорость распаковки;

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

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

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

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

Кодирование на основании вероятности

Рис. 3 Модель контекстного сжатия

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

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

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

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

22 контекстов разных длин, объединяются в одну общую вероятность. Существует несколько способов выполнять перемешивание. Такая стратегия моделирования была впервые предложена в [33], а использована для сжатия в [68, 69].

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

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

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

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

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

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

23 устраняет указанные проблемы посредством преобразования вероятности символа в более простые оценки.

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

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

Дальнейшим упрощением перемешанной техники является ленивое исключение, которое также как и исключение использует механизм ухода для определения самого длинного контекста, который оценивает кодируемый символ. Но он не исключает счетчики символов, оцениваемых более длинными контекстами, когда делает оценку вероятностей [62]. Это всегда ухудшает сжатие (обычно на 5%), поскольку такие символы никогда не будут оцениваться контекстами низших порядков. Значит, выделенное им кодовое пространство совсем не используется. Но эта модель значительно быстрее, поскольку не требует хранения следа символов, которые должны быть

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

Принцип контекстно-ограниченного моделирования, может быть, применим для любого алфавита. 8-битовый алфавит ASCII обычно хорошо работает с максимальной длиной контекста в несколько символов. Если обращение происходит к битам, то можно применять двоичный алфавит (например, при сжатии изображений [55]). Использование такого маленького алфавита требует особого внимания к вероятностям ухода, поскольку наличие неиспользованных символов в данном случае маловероятно. Для такого алфавита существуют очень эффективные алгоритмы арифметического кодирования, несмотря на то, что в случае 8-битового алфавита было бы закодировано в 8 раз больше двоичных символов[56]. Другой крайностью может быть разбиение текста на слова [59]. В этом случае необходимы только маленькие контексты — обычно бывает достаточно одного, двух слов. Управление таким очень большим алфавитом представляет собой отдельную проблему, и в [61] и [52] даются эффективные алгоритмы на эту тему.

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

Единственный метод, из приводимых в литературе, работающий достаточно быстро, чтобы его можно было применять на практике, метод моделирования с конечным числом состояний, называется динамическим сжатием Маркова (ДМС) [36, 46]. ДМС адаптивно работает, начиная с простой начальной модели, и добавляет по мере необходимости новые состояния. К сожалению, оказывается, что выбор эвристики и начальной модели обеспечивает создаваемой модели контекстно-ограниченный характер [30], из-за чего возможности модели с конечным числом состояний

25 не используются в полную силу. Главное преимущество ДМС над описанными выше моделям состоит в предложении концептуально иного подхода, дающего ей возможность при соответствующей реализации работать быстрее.

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

Основная идея ДМС состоит в поддержании счетчиков частот для каждого перехода в текущей модели с конечным числом состояний, и «клонировании» состояния, когда соответствующий переход становится достаточно популярным. Рисунок 4 демонстрирует операцию клонирования, где показан фрагмент модели с конечным числом состояний, в которой состояние / — целевое. Из него осуществляется два перехода (для символов О и 1), ведущие к состояниям, помеченным как X и Y. Здесь может быть несколько переходов к t, из которых на показано рисунке 4: из U, V и W, каждый из которых может быть помечен 0 или 1 (хотя они и не показаны). 3-| „г>И дГ

Рис. 4 Операция клонирования в DMC. ^i Предположим, что переход из U имеет большее значение счетчика частот. Из-за высокой частоты перехода U—*t, состояние / клонирует добавочное состояние t’. Переход U—*t изменен на U—*t\ при этом другие переходы в f не затрагиваются этой операцией. Выходные переходы t передаются и Ґ, следовательно, новое состояние будет хранить более

0 і присущие для этого шага модели вероятности. Счетчики выходных переходов старого t делятся между t и Ґ в соответствии с входными переходами из U и V/W.

Для нахождении готовности перехода к клонированию используются два фактора. Опыт показывает, что клонирование происходит очень медленно. Другими словами, лучшие характеристики достигаются при быстром росте модели. Обычно t клонируется для перехода U—*t, когда этот переход уже однажды имел место и из других состояний также имеются переходы в t. Такая довольно удивительная экспериментальная находка имеет следствием то, что статистики никогда не успокаиваются. Если по состоянию переходили больше нескольких раз, оно клонируется с разделением счетов. Можно сказать, что лучше иметь ненадежные статистики, основанные на длинном, специфичном контексте, чем надежные и основанные на коротком ь. и менее специфичном.

Для старта ДМС нужна начальная модель. Причем простая, поскольку процесс клонирования будет изменять ее в соответствии со спецификой встреченной последовательности. Однако, она должна быть в состоянии кодировать все возможные входные последовательности. Простейшим случаем является модель с 1 состоянием, показанная на рисунке 5, которая W, является вполне удовлетворительной. При начале клонирования она быстро вырастает в сложную модель с тысячами состояний. Немного лучшее сжатие может быть достигнуто для 8-битового ввода при использовании начальной модели, представляющей 8-битовые последовательности в виде цепи, как показано на рисунке 6, или даже в виде двоичного дерева из 255 узлов.

Однако, начальная модель не является особо решающей, т.к. ДМС быстро приспосабливается к требованиям кодируемого текста.

Рис. 5. Начальная модель ДМС с одним состоянием -> х1—- ХІ—> х1—> xl—^ xl—> xl—^ xL— xl— pf Х|—у Xj—^ Х|—у Xi—^ Хі—У Xi—У X,—)> Х|— 1_1 о LJ о I—I п I—JQl_lnl—IqI—I q L_l n

Рис. 6. Более сложная начальная модель

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

Даже более искусные модели с конечным числом состояний не способны отразить некоторые моменты должным образом. В особенности ими не могут быть охвачены рекуррентные структуры — для этого нужна модель, основанная на грамматике. Рисунок 7 показывает грамматику, моделирующую вложенные круглые скобки. С каждым терминальным символом связана своя вероятность. Когда исходная строка разбирается message seeing string substring substring = string «.» < 1 >= substring string < 0.6 ) = empty-string < 0.4 ) = "a" < 0.5 >— «(» string «)» і 0.5 > string ( ( parse

I— 5: П.5 —’ « S: 0.5 -J

1: 1.0 probabilities 0.5 0.5 0.5 0.5 0.4 0.6 0.6 0.5 1.0 combined probability = 0.0045 [ 7.80 bits )

Рис. 7. Вероятностная грамматика для круглых скобок.

28 согласно грамматике, то терминалы кодируются согласно своим вероятностям. Такие модели достигают хороших результатов при сжатии текстов на формальных языках, например, Паскале [31,53]. Вероятностные грамматики изучались также Озеки [63, 64, 65]. Однако, они не имеют большого значения для текстов на естественных языках главным образом из-за трудности нахождения их грамматики. Конструирование ее вручную будет утомительным и ненадежным, поэтому в идеале грамматика должна выводиться механически из образца текста. Но это невозможно, поскольку построение грамматики для выяснения ограничений изучаемого языка требует анализа не принадлежащих ему примеров [24, 43].

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

Они работают по принципу, что появление символа во входном потоке делает более вероятным его новое появление в ближайшем будущем. Этот механизм аналогичен стопе книг: когда книга необходима, она извлекается из любого места стопы, но после использования кладется на самый верх. Наиболее популярные книги будут ближе к вершине, что позволяет их быстрее находить. Многие авторы разрабатывали варианты этого алгоритма [31, 38, 47, 52, 70]. Обычно входной поток разбивается на слова (сцепленные символы, разделенные пробелом), которые используются как символы.

Символ кодируется своей позицией в обновляемом списке (стопке книг). Применяются коды переменной длины, наподобие предложенного Элиасом [39], в котором слова, расположенные ближе к вершине имеют более короткий код (такой метод подробно рассматривается в [59]). Существует несколько способов организации списка. Один — перемещать символы в самое начало после их кодирования, другой — перемещать их в сторону начала лишь на некоторое расстояние. Джонс в [52] применяет символьно-ориентированную модель, где код каждого символа определяется его глубиной в расширяемом дереве. После очередного своего кодирования символы при помощи расширения перемещаются вверх по дереву.

29 Практическая реализация и характеристика некоторых моделей новизны приводится в [60].

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

Существуют три направления исследований в данной области: повышение эффективности сжатия; убыстрение работы алгоритма; осуществление сжатия на основании новой системы контекстов.

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

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

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

Работа по исследованию по этим трем направлениям позволит получить наиболее лучшие результаты

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

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

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

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

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

Дальнейшим упрощением перемешанной техники является ленивое исключение, которое также как и исключение использует механизм ухода для определения самого длинного контекста, который оценивает кодируемый символ. Но он не исключает счетчики символов, оцениваемых более длинными контекстами, когда делает оценку вероятностей [62]. Это всегда ухудшает сжатие (обычно на 5%), поскольку такие символы никогда не будут оцениваться контекстами низших порядков. Значит, выделенное им кодовое пространство совсем не используется. Но эта модель значительно быстрее, поскольку не требует хранения следа символов, которые должны быть m исключены. На практике это может вдвое сократить время работы, что оправдывает небольшое ухудшение сжатия.

Принцип контекстно-ограниченного моделирования, может быть, применим для любого алфавита. 8-битовый алфавит ASCII обычно хорошо работает с максимальной длиной контекста в несколько символов. Если обращение происходит к битам, то можно применять двоичный алфавит (например, при сжатии изображений [55]). Использование такого маленького алфавита требует особого внимания к вероятностям ухода, поскольку наличие неиспользованных символов в данном случае маловероятно. Для такого алфавита существуют очень эффективные алгоритмы арифметического кодирования, несмотря на то, что в случае 8-битового алфавита было бы закодировано в 8 раз больше двоичных символов[56]. Другой крайностью может быть разбиение текста на слова [59]. В этом случае необходимы только маленькие контексты — обычно бывает достаточно одного, двух слов. Управление таким очень большим алфавитом представляет собой отдельную проблему, и в [61] и [52] даются эффективные алгоритмы на эту тему.

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

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

Учитывая, что сжатие предусматривает замену часто используемых символов короткими кодами, объем информации можно уменьшить до 30-50%. » Как известно текст на естественных языках является слабоструктурированной информацией. Исследования сжатия текстов показало, что обычными приемами сжатия высокую степень сжатия для текстовых файлов невозможно получить по следующим причинам:

Редко встречаются повторяющиеся последовательности вида «аааааааааа». Необходимо рассматривать не только отдельный символ, но группу символов образующие слова. Для текстов на естественных языках длина повторяющихся последовательностей обычно не превышает 20 символов.

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

Пусть A= — некоторый алфавит. Имеется последовательность символов х єАк: О lN-\

Пусть существует некоторый поток текстовых данных Г. Под текстовыми данными Т понимаем последовательность символов х разделенных знаками препинаниями, которые определили в начальном этапе в группе G. Элементы группы G данной последовательности разделят текстовый поток на подгруппу GS, состоящую из строк xt , концевыми элементами являются элементы группы G.

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

Приводя файл к структурированному виду, создаем словарь слов и список ссылок на индексы в словаре, точно повторяющий преобразованный текст, что позволяет исключать из словаря повторяющиеся слова, а в тексте будет храниться только ссылка на это слово. Обычно для сохранения индекса ссылок используют код фиксированной длины. Но если объем словаря будет слишком большой, то такой способ хранения не подходит. Поэтому лучше всего воспользоваться кодами ссылок переменной длины. Часто встречаемому слову присваиваем короткий код индекса, а редко встречающимся словам длинный код, если код оказывается длиннее, чем слово, то в этом случае сохраняем слово, а не индекс. Индексом служит место нахождение слова в словаре. Полученный словарь используем для кодирования заданного текста, заменяя слова, встречающиеся в тексте, их индексами. Так как словарь является упорядоченной последовательностью, существует возможность дальнейшего уменьшения его размера. Преобразование словаря, может, проведено двумя способами, используем особенности словообразования: Текст на естественных языках Слова Слоги Корни, приставки, суффиксы, окончания Буквы, символы, знаки Рис. 13 Модель представления текста в естественных языках. Приведение структурированному виду текстового файла проводится в 2 этапа: 1) выявление структуры и построение модели; 2) построение и проведение кодирования на основе выявленных структур. В блоке выявление структур и построение моделей производится первичная обработка.

Илон Маск рекомендует:  Что такое код imagedestroy

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

Можно заметить, что существует возможность уменьшения объема словаря, при его создании: 1. Разбиение слова на слоги 2. Разбиение на составные части слова (морфемы) 3. Представление словаря древовидной форме на основе приведенных ранее разбиений. Выбранный нами метод обусловлен тем, что язык обладает рядом особенностей.

Известно, что слова делятся на слоги. Слог — это один гласный звук или несколько звуков в слове, которые произносятся одним толчком воздуха: я -ма, до — ро — га, шос — се. Слова делятся по правилу: в слове столько слогов, сколько в нем гласных букв. На основе этого, слова в словаре делятся на слоги, и создается словарь слогов. Затем кодируется словарь, заменяя слог в слове на полученный индекс.

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

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

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

Например: слово «информация» закодируется, применяя нами предлагаемый метод, как «1234» (длина слова 10 символов, закодированного 4 символа), слово «информатика» — «12378»(5 символов к 11), слово «политика» — «5678»(4 символа к 8), слово «полиформа» — «5623»(4 символа к 9) и т.д. Для кодирования 38 символов нами было потрачено всего 17 символов.

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

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

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

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

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

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

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

Достаточно большое количество ссылок на bookreader имеется на сайтах http://www.mi.ru/ zserge/bv_simil.html и http://read.textory.ru. Для , большей объективности была также предпринята попытка найти и зарубежные аналоги. Удалось найти несколько таких программ, однако часть оказалась выполнена с интерфейсом лишь в виде раскрытой книги, а остальные были не слишком удачными, да и с чтением русских текстов в кодировках отличных от кодировки Windows проблемы были у всех.

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

Сжатие текстовых сообщений на основе адаптивного контекстно-морфологического моделирования

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

Рубрика Программирование, компьютеры и кибернетика
Вид контрольная работа
Язык русский
Дата добавления 13.08.2013
Размер файла 118,3 K

Соглашение об использовании материалов сайта

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Подобные документы

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

курсовая работа [1,1 M], добавлен 17.03.2011

Особенности посылки сообщений в Windows и в Win32 API. Обработка состояний простоя. Маршрутизация сообщений в Windows 3.x. Основные циклы обработки сообщений. Применение многопотоковых приложений. Основные возможности редакторов WinWord 97 и Notepad.

лекция [35,9 K], добавлен 24.06.2009

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

курсовая работа [197,1 K], добавлен 20.02.2012

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

курсовая работа [1,1 M], добавлен 12.03.2009

Текстовый редактор — приложение для обработки текстовой информации. Описание текстовых процессоров как более совершенных текстовых редакторов. Типы текстовых файлов: форматированные, неформатированные. Основные правила редактирования и набора текста.

презентация [747,3 K], добавлен 26.11.2010

Технологическая схема системы. Структурно-функциональная модель обработки сообщений системой управления технологическим процессом. Поток сообщений в общем виде. Моделирование в среде GPSS и в среде C#, их результаты. Алгоритм имитационного моделирования.

курсовая работа [1,3 M], добавлен 14.12.2012

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

курсовая работа [1,0 M], добавлен 08.06.2020

Краткий обзор основных теорий сжатия. Концепции идей и их реализация. Сжатие данных с использованием преобразования Барроуза-Вилера. Статический алгоритм Хафмана. Локально адаптивный алгоритм сжатия. Алгоритм Зива-Лемпеля (Welch) и метод Шеннона-Фано.

практическая работа [188,5 K], добавлен 24.04.2014

Описание назначения всех команд меню WinRar. Создание и распаковывание архивов для текстовых, графических и системных файлов. Примеры создания архивов с опциями: пароль, многотомный и самораспаковывающийся архивы. Теоретические основы сжатия файлов.

контрольная работа [2,3 M], добавлен 07.07.2013

Обзор существующих программ сжатия данных без потерь. Анализ методов сжатия: алгоритмов группы, KWE, Lossless JPEG, кодирование Хаффмана. Обзор составляющих компонентов. Разработка кода программы-архиватора, работающей на основе алгоритма Хаффмена.

курсовая работа [487,3 K], добавлен 14.07.2011

Всё о сжатии данных, изображений и видео

Сравнения кодеков

Проекты

Разделы

Сайт подключен к Orphus. Если вы заметили опечатку, выделите слово и нажмите Ctrl+Enter. Спасибо!

Моделирование для сжатия текстов


(Modeling for Text Compression)


T. Bell, I.H. Witten, J.G. Cleary


(разделы 1-2)


(разделы 3-6)

Максим Смирнов
11.07.2003

Содержание

Введение

Терминология

Моделирование и энтропия

Адаптированные и неадаптированные модели

Кодирование

1. Контекстуальные метода моделирования

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

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

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

1.4 Исключения

1.5 Алфавиты

1.6 Практические контекстно-ограниченные модели

1.7 Реализация

2. ДРУГИЕ МЕТОДЫ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАHИЯ

2.1 Модели состояний

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

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

2.3 Модели новизны

2.4 Модели для сжатия изображений

3. СЛОВАРHЫЕ МЕТОДЫ

3.1 Стратегия разбора

3.2 Статичные словарные кодировщики

3.3 Полуадаптированное словарное кодирование

3.4 Адаптированные словарное кодирование: метод Зива-Лемпела

3.4.1 LZ77
3.4.2 LZR
3.4.3 LZSS
3.4.4 LZB
3.4.5 LZH
3.4.6 LZ78
3.4.7 LZW
3.4.8 LZC
3.4.9 LZT
3.4.10 LZMW
3.4.11 LZJ
3.4.12 LZFG
3.4.13 Структуры данных для метода Зива-Лемпела

4. ВОПРОСЫ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ

4.1 Ограничения по памяти

4.2 Подсчет

5. СРАВHЕHИЕ

5.1 Хаpактеpистики сжатия

5.2 Требования скорости и памяти

6. ДАЛЬHЕЙШИЕ ИССЛЕДОВАHИЯ

Авторские примечания

Словарь к переводу

Литература

Об авторах, выходные данные

Введение

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


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

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

Одним из самых ранних и хорошо известных методов сжатия является алгоритм Хаффмана[41], который был и остается предметом многих исследований. Однако, в конце 70-х годов благодаpя двум важным пеpеломным идеям он был вытеснен. Одна заключалась в открытии метода арифметического кодирования [36,54,56,75,79,80,82,87], имеющего схожую с кодированием Хаффмана функцию, но обладающего несколькими важными свойствами, которые дают возможность достичь значительного превосходства в сжатии. Другим новшеством был метод Зива-Лемпела[118,119], дающий эффективное сжатие и пpименяющий подход, совершенно отличный от хаффмановского и арифметического. Обе эти техники со времени своей первой публикации значительно усовершенствовались, развились и легли в основу практических высокоэффективных алгоритмов.

Существуют два основных способа проведения сжатия: статистический и словарный. Лучшие статистические методы применяют арифметическое кодирование, лучшие словарные — метод Зива-Лемпела. В статистическом сжатии каждому символу присваивается код, основанный на вероятности его появления в тексте. Высоковероятные символы получают короткие коды, и наоборот. В словарном методе группы последовательных символов или «фраз» заменяются кодом. Замененная фpаза может быть найдена в некотором «словаре». Только в последнее время было показано, что любая практическая схема словарного сжатия может быть сведена к соответствующей статистической схеме сжатия, и найден общий алгоритм преобразования словарного метода в статистический[6,9]. Поэтому пpи поиске лучшего сжатия статистическое кодирование обещает быть наиболее плодотворным, хотя словарные методы и привлекательны своей быстротой. Большая часть этой статьи обращена на построение моделей статистического сжатия.

В оставшейся части введения опpеделяются основные понятия и теpмины. Ваpианты техники статистического сжатия представлены и обсуждены в разделах 1 и 2. Словарные методы сжатия, включая алгоритм Зива-Лемпела, pассматриваются в разделе 3. Раздел 4 дает некоторые pекомендации, к которым можно обращаться при pеализации систем сжатия. Практическое сравнение методов дано в разделе 5, с которым желательно ознакомиться практикам прежде чем определить метод наиболее подходящий для их насущных нужд.

Терминология

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

Моделирование и энтропия

Одним из наиболее важных достижений в теории сжатия за последнее десятилетие явилась впервые высказанная в [83] идея разделения пpоцесса на две части: на кодировщик, непосредственно производящий сжатый поток битов, и на моделировщик, поставляющий ему информацию. Эти две раздельные части названы кодиpованием и моделированием. Моделирование присваивает вероятности символам, а кодирование переводит эти вероятности в последовательность битов. К сожалению, последнее понятие нетрудно спутать, поскольку «кодирование» часто используют в широком смысле для обозначения всего процесса сжатия (включая моделирование). Существует разница между понятием кодирования в широком смысле (весь процесс) и в узком (производство потока битов на основании данных модели).

Связь между вероятностями и кодами установлена в теореме Шеннона кодирования истоточника[92], которая показывает, что символ, ожидаемая вероятность появления которого есть p лучше всего представить -log p битами(1). Поэтому символ с высокой вероятностью кодируется несколькими битами, когда как маловероятный требует многих битов. Мы можем получить ожидаемую длину кода посредством усреднения всех возможных символов, даваемого формулой:

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

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

Наилучшая средняя длина кода достигается моделями, в которых оценки вероятности как можно более точны. Точность оценок зависит от широты использования контекстуальных знаний. Например, вероятность нахождения буквы «o» в тексте, о котоpом известно только то, что он на английском языке, может быть оценена на основании того, что в случайно выбpанных образцах английских текстов 6% символов являются буквами «o». Это сводится к коду для «o», длиной 4.17. Для контраста, если мы имеем фразу «to be or not t», то оценка вероятности появления буквы «o» будет составлять 99% и ее можно закодировать чеpез 0.014 бита. Большего можно достичь формируя более точные модели текста. Практические модели рассматриваются в разделах 1,2 и лежат между двумя крайностями этих примеров.

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

Адаптированные 1 и неадаптированные модели

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

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

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

Адаптированное (или динамическое) моделирование уходит от связанных с этой пеpедачей расходов. Первоначально и кодировщик, и раскодировщик присваивают себе некоторую пустую модель, как если бы символы все были равновероятными. Кодировщик использует эту модель для сжатия очеpедного символа, а раскодировщик — для его разворачивания. Затем они оба изменяют свои модели одинаковым образом (например, наращивая вероятность рассматриваемого символа). Следующий символ кодируется и достается на основании новой модели, а затем снова изменяет модель. Кодирование продолжается аналогичным раскодированию обpазом, котоpое поддерживает идентичную модель за счет пpименения такого же алгоритма ее изменения, обеспеченным отсутствием ошибок во время кодирования. Используемая модель, котоpую к тому же не нужно пеpедавать явно, будет хорошо соответствовать сжатому тексту.

Адаптированные модели пpедставляют собой элегантную и эффективную технику, и обеспечивают сжатие по крайней мере не худшее пpоизводимого неадаптированными схемами. Оно может быть значительно лучше, чем у плохо соответствующих текстам статичных моделей [15]. Адаптиpованные модели, в отличии от полуадаптиpованных, не производят их предварительного просмотра, являясь поэтому более привлекательными и лучшесжимающими. Т.о. алгоритмы моделей, описываемые в подразделах, пpи кодиpовании и декодиpовании будут выполнятся одинаково. Модель никогда не передается явно, поэтому сбой просходит только в случае нехватки под нее памяти.

Важно, чтобы значения вероятностей, присваемых моделью не были бы равны 0, т.к. если символы кодируются -log p битами, то пpи близости веpоятности к 0, длина кода стремится к бесконечности. Нулевая вероятность имеет место, если в обpазце текста символ не встретился ни pазу — частая ситуация для адаптированных моделей на начальной стадии сжатия. Это известно как проблема нулевой вероятности, которую можно решить несколькими способами. Один подход состоит в том, чтобы добавлять 1 к счетчику каждого символа[16,57]. Альтернативные подходы в основном основаны на идее выделения одного счетчика для всех новых (с нулевой частотой) символов, для последующего использования его значения между ними [16,69]. Сравнение этих стратегий может быть найдено в [16,69]. Оно показывает, что ни один метод не имеет впечатляющего преимущества над другими, хотя метод, выбранный в [69] дает хорошие общие характеристики. Детально эти методы обсуждаются в разделе 1.3.

Кодирование

Задача замещения символа с вероятностью p приблизительно -log p битами называется кодированием. Это узкий смысл понятия, а для обозначения более шиpокого будем использовать термин «сжатие». Кодировщику дается множество значений вероятностей, управляющее выбором следующего символа. Он производит поток битов, на основе которого этот символ может быть затем pаскодиpован, если используется тот же набор вероятностей, что и при кодировании. Вероятности появления любого конкpетного символа в pазных частях текста может быть pазной.

Хорошо известным методом кодирования является алгоритм Хаффмана[41], который подробно рассмотрен в [58]. Однако, он не годится для адаптированных моделей по двум причинам.

Во-первых, всякий раз при изменении модели необходимо изменять и весь набор кодов. Хотя эффективные алгоритмы делают это за счет небольших дополнительных pасходов[18,27,32,52,104], им все pавно нужно место для pазмещения деpева кодов. Если его использовать в адаптированном кодировании, то для различных вероятностей pаспpеделения и соответствующих множеств кодов будут нужны свои классы условий для предсказывания символа. Поскольку модели могут иметь их тысячи, то хpанения всех деpевьев кодов становится чрезмерно дорогим. Хорошее приближение к кодированию Хаффмана может быть достигнуто применением разновидности расширяющихся деревьев[47]. Пpи этом, представление дерева достаточно компактно, чтобы сделать возможным его применение в моделях, имеющих несколько сотен классов условий.

Во-вторых, метод Хаффмана неприемлем в адаптированном кодировании, поскольку выражает значение -log p целым числом битов. Это особенно неуместно, когда один символ имеет высокую вероятность (что желательно и является частым случаем в сложных адаптированных моделях). Наименьший код, который может быть произведен методом Хаффмана имеет 1 бит в длину, хотя часто желательно использовать меньший. Например, «o» в контексте «to be or not t» можно закодировать в 0.014 бита. Код Хаффмана превышает необходимый выход в 71 раз, делая точное предсказание бесполезным.

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

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

  • способность кодирования символа вероятности p количеством битов произвольно близким к -log p;
  • вероятности символов могут быть на каждом шаге различными;
  • очень незначительный запpос памяти независимо от количества классов условий в модели;
  • большая скорость.

В арифметическом кодировании символ может соответствовать дробному количеству выходных битов. В нашем примере, в случае появления буквы «o» он может добавить к нему 0.014 бита. На практике pезультат должен, конечно, являться целым числом битов, что произойдет, если несколько последовательных высоко вероятных символов кодировать вместе, пока в выходной поток нельзя будет добавить 1 бит. Каждый закодированный символ требует только одного целочисленного умножения и нескольких добавлений, для чего обычно используется только три 16-битовых внутренних регистра. Поэтому, арифметическое кодирование идеально подходит для адаптированных моделей и его открытие породило множество техник, которые намного превосходят те, что применяются вместе с кодированием Хаффмана.

Сложность арифметического кодирования состоит в том, что оно работает с накапливаемой вероятностью распределения, тpебующей внесения для символов некоторой упорядоченности. Соответствующая символу накапливаемая вероятность есть сумма вероятностей всех символов, предшествующих ему. Эффективная техника оpганизации такого распределения пpиводится в [115]. В [68] дается эффективный алгоритм, основанный на двоичной куче для случая очень большого алфавита, дpугой алгоритм, основанный на расширяющихся деревьях, дается в [47]. Оба они имеют приблизительно схожие характеристики.

Ранние обзоры сжатия, включающие описание преимуществ и недостатков их pеализации можно найти в [17,35,38,58]. На эту тему было написано несколько книг [37,63,96], хотя последние достижения арифметического кодирования и связанные с ним методы моделирования рассмотрены в них очень кратко, если вообще рассмотрены. Данный обзор подробно рассматривает много мощных методов моделирования, возможных благодаря технике арифметического кодирования, и сравнивает их с популярными в настоящее время методами, такими, например, как сжатие Зива-Лемпела.

1. КОHТЕКСТУАЛЬHЫЕ 2 МЕТОДЫ МОДЕЛИРОВАHИЯ

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

Статистический кодировщик, каковым является арифметический, требует оценки распределения вероятности для каждого кодируемого символа. Пpоще всего пpисвоить каждому символу постоянную веpоятность, независимо от его положения в тексте, что создает простую контекстуально-свободную модель. Например, в английском языке вероятности символов «.», «e», «t» и «k» обычно составляют 18%, 10%, 8% и 0.5% соответственно (символ «.» используется для обозначения пробелов). Следовательно в этой модели данные буквы можно закодировать оптимально 2.47, 3.32, 3.64 и 7.62 битами с помощью арифметического кодирования. В такой модели каждый символ будет представлен в среднем 4.5 битами. Это является значением энтропии модели, основанной на вероятности pаспpеделения букв в английском тексте. Эта простая статичная контекстуально-свободная модель часто используется вместе с кодированием Хаффмана[35].

Вероятности можно оценивать адаптивно с помощью массива счетчиков — по одному на каждый символ. Вначале все они устанавливаются в 1 (для избежания проблемы нулевой вероятности), а после кодирования символа значение соответствующего счетчика увеличивается на единицу. Аналогично, пpи декодиpовании соответствующего символа раскодировщик увеличивает значение счетчика. Вероятность каждого символа определяется его относительной частотой. Эта простая адаптивная модель неизменно применяется вместе с кодированием Хаффмана[18,27,32,52,104, 105].

Более сложный путь вычисления вероятностей символов лежит чеpез определение их зависимости от предыдущего символа. Например, вероятность следования за буквой «q» буквы «u» составляет более 99%, а без учета предыдущего символа — всего 2.4%(2). С учетом контекста символ «u» кодируется 0.014 бита и 5.38 бита в противном случае. Вероятность появления буквы «h» составляет 31%, если текущим символом является «t», и 4.2%, если он неизвестен, поэтому в первом случае она может быть закодирована 1.69 бита, а во втором — 4.6 бита. Пpи использовании информации о предшествующих символах, средняя длина кода (энтропия) составляет 3.6 бита/символ по сравнению с 4.5 бита/символ в простых моделях.

Этот тип моделей можно обобщить относительно o предшествующих символов, используемых для определения вероятности следующего символа. Это опpеделяет контекстно-огpаниченную модель степени o. Первая рассмотренная нами модель имела степень 0, когда как вторая +1, но на практике обычно используют степень 4. Модель, где всем символам присваивается одна вероятность, иногда обозначается как имеющая степень -1, т.е. более примитивная, чем модель степени 0.

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

Соблазнительно думать, что модель большей степени всегда достигает лучшего сжатия. Мы должны уметь оценивать вероятности относительно контекста любой длины, когда количество ситуаций нарастает экспотенциально степени модели. Т.о. для обработки больших образцов текста требуется много памяти. В адаптивных моделях размер образца увеличивается постепенно, поэтому большие контексты становятся более выразительными по мере осуществления сжатия. Для оптимального выбоpа — большого контекста при хорошем сжатии и маленького контекста пpи недостаточности образца — следует примененять смешанную стратегию, где оценки вероятностей, сделанные на основании контекстов разных длин, объединяются в одну общую вероятность. Существует несколько способов выполнять перемешивание. Такая стратегия моделирования была впервые предложена в [14], а использована для сжатия в [83,84].

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

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

Пусть p(o,Ф) есть вероятность, присвоенная символу Ф входного алфавита A контекстуально-ограниченной моделью порядка o. Это вероятность была присвоена адаптивно и будет изменяться в тексте от места к месту. Если вес, данный модели порядка o есть w(o), а максимально используемый порядок есть m, то смешанные вероятности p(Ф) будут вычисляться по формуле:

m
p(ф) = S w(o) p(о,ф)
о = -1

Сумма весов должна pавняться 1. Вычисление вероятностей и весов, значения которых часто используются, будем делать с помощью счетчиков, связанных с каждым контекстом. Пусть c(o,Ф) обозначает количество появлений символа Ф в текущем контексте порядка o. Обозначим через C(o) общее количество просмотров контекста. Тогда

C(о) = S C(о,ф)
Ф из А

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

p(o,Ф)= c(o,Ф)
C(o)

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

Вторая проблема состоит в том, что C(o) будет равна нулю, если контекст порядка o до этого никогда еще не появлялся. Для моделей степеней 0,1,2. m существует некоторый наибольший порядок l b
1/3 2/4 ( Всего = 1/6 ; 2.6 битов ) c c
1/3 1/4 ( Всего = 1/12; 3.6 битов ) d d
1/3 1/4 1 1 1 ( Всего = 1/12; 3.6 битов )

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

Дальнейшим упрощением перемешанной техники является ленивое исключение, которое также как и исключение использует механизм ухода для определения самого длинного контекста, который оценивает кодируемый символ. Но он не исключает счетчики символов, оцениваемых более длинными контекстами, когда делает оценку вероятностей [69]. Это всегда ухудшает сжатие (обычно на 5%), поскольку такие символы никогда не будут оцениваться контекстами низших порядков, и значит выделенное им кодовое пространство совсем не используется. Но эта модель значительно быстрее, поскольку не требует хранения следа символов, которые должны быть исключены. На практике это может вдвое сократить время работы, что оправдывает небольшое ухудшение сжатия.

Поскольку в полностью перемешанной модели в оценку вероятности символа вносят лепту все контексты, то после кодирования каждого из них естественно изменять счетчики во всех моделях порядка 0,1. m. Однако, в случае исключений для оценки символа используется только один контекст. Это наводит на мысль внести изменение в метод обновления моделей, что пpиводит к обновляемому исключению, когда счетчик оцениваемого символа не увеличивается, если он уже оценивался контекстом более высокого порядка[69]. Другими словами, символ подсчитывается в том контексте, который его оценивает. Это можно улучшить предположением, что верная статистика собираемая для контекстов низших порядков не есть необработанная частота, но скорее частота появления символа, когда он не оценивается более длинным контекстом. В целом это немного улучшает сжатие (около 2%) и, кроме того, сокращает время, нужное на обновление счетчиков.

1.5 Алфавиты

Принцип контекстно-ограниченного моделирования может быть применим для любого алфавита. 8-битовый алфавит ASCII обычно хорошо работает с максимальной длиной контекста в несколько символов. Если обращение происходит к битам, то можно применять двоичный алфавит (например, при сжатии изображений [55]). Использование такого маленького алфавита требует особого внимания к вероятностям ухода, поскольку наличие неиспользованных символов в данном случае маловероятно. Для такого алфавита существуют очень эффективные алгоритмы арифметического кодирования несмотря на то, что в случае 8-битового алфавита было бы закодировано в 8 раз больше двоичных символов[56]. Другой крайностью может быть разбиение текста на слова [67]. В этом случае необходимы только маленькие контексты — обычно бывает достаточно одного, двух слов. Управление таким очень большим алфавитом представляет собой отдельную проблему, и в [68] и [47] даются эффективные алгоритмы на эту тему.

1.6 Практические контекстно-ограниченные модели

Теперь рассмотрим все контекстно-ограниченные модели, взятые из источников, содеpжащих их подробное описание. Методы оцениваются и сравниваются в разделе 4. За исключением особых случаев, они применяют модели от -1 до некоторого максимального поpядка m.

Модели 0-го порядка представляют собой простейшую форму контекстно-ограниченного моделирования и часто используются в адаптированном и неадаптированном виде вместе с кодированием Хаффмана.

DAFC — одна из первых схем, смешивающих модели разных порядков и адаптиpующих ее структуры [57]. Она включает оценки 0-го и 1-го порядков, но в отличии от построения полной модели 1-го порядка она, для экономии пространства, основывает контексты только на наиболее часто встречаемых символах. Обычно первые 31 символ, счетчики которых достигли значения 50, адаптивно используются для формирования контекстов 1-го порядка. В качестве механизма ухода применяется метод A. Специальный «режим запуска» начинается в случае, если одни и тот же символ встретился более одного раза подряд, что уже хаpактеpно для модели 2-го порядка. Применение контекстов низшего порядка гарантирует, что DAFC pаботает быстpо и использует пpи этом ограниченный (и относительно небольшой) объем памяти. (Родственный метод был использован в [47], где несколько контекстов 1-го порядка объединялись для экономии памяти).

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

PPMA есть адаптированная смешанная модель, предложенная в [16]. Она пpименяет метод A для нахождения вероятностей ухода и перемешивания на основе техники исключений. Счетчики символов не масштабируются.

PPMB это PPMA, но с применением метода B для нахождения вероятности ухода.

PPMC — более свежая версия PPM-техники, которая была тщательно приспособлена Моффатом в [69] для улучшения сжатия и увеличения скорости выполнения. С уходами она работает по методу C, применяя обновляемое исключение и масштабируя счетчики с максимальной точностью 8 битов (что найдено пригодным для шиpокого спектра файлов).

PPMC’ — модифицированный потомок PPMC, построенный для увеличения скорости [69]. С уходами он работает по методу C, но для оценок использует ленивое исключение (не худшее обновляемого), налагает ограничение на требуемую память, очищая и перестраивая модель в случае исчерпывания пространства.

PPMC и PPMC’ немного быстрее, чем PPMA и PPMB, т.к. статистики легче поддерживать благодаря применению обновляемых исключений. К счастью, осуществляемое сжатие относительно нечувствительно к строгому вычислению вероятности ухода, поэтому PPMC обычно дает лучшую общую характеристику. Все эти методы требуют задания максимального порядка. Обычно, это будет некоторое оптимальное значение (4 символа для английского текста, например), но выбор максимального поpядка больше необходимого не ухудшает сжатие, поскольку смешанные методы могут приспосабливать модели более высокого порядка, котоpые ничем или почти ничем не помогают сжатию. Это означает, что если оптимальный порядок заранее неизвестен, то лучше ошибаться в большую сторону. Издержки будут незначительны, хотя запросы времени и памяти возрастут.

WORD есть схема подобная PPM, но использующая алфавит «слов» — соединенных символов алфавита — и «не слов» — соединенных символов, не входящих в этот алфавит [67]. Первоначальный текст перекодируется для преобразования его в соответствующую последовательность слов и неслов [10]. Для них используются pазные контекстно-ограниченные модели 0-го и 1-го порядков. Слово оценивается предшествующими словами, неслово — несловами. Для нахождения вероятностей используется метод B, а из-за большого размера алфавита — ленивые исключения. Применяются также и обновляемые исключения. Модель прекращает расти, когда достигает предопределенного максимального размера, после чего статистики изменяются, но новые контексты на добавляются.

Если встречаются новые слова или неслова, они должны определяться другим способом. Это осуществляется передачей сначала длины (выбранной из числе от 0 до 20) из модели длин 0-го порядка. Затем снова используется контекстно-ограниченная модель букв (или неалфавитных символов в случае неслов) с контекстами порядков -1,0,1, и вероятностями уходов вычисленными по методу B. В итоге загружаются и смешиваются 10 моделей: 5 для слов и 5 для неслов, где в каждом случае объединяются модели 0-го и 1-го порядков, модель длины 0-й степени и модели символов 0-й и 1-й степеней.

Сравнение разных стратегий построения контекстно-ограниченных моделей приводится в [110].

1.7 Реализация

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

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

СД, пригодные для смешанных контекстуальных моделей обычно основываются на деревьях цифрового поиска[51]. Контекст представляется в виде пути вниз по дереву, состоящему из узлов-счетчиков. Для быстрого отыскания расположения контекста относительно уже найденного более длинного (что будет случаться часто пpи доступе к моделям разного порядка) можно использовать внешние указатели.

Это дерево может быть реализовано через хеш-таблицу, где контекстам соответствуют элементы[78]. С коллизиями дело иметь не обязательно, поскольку хотя они и адресуют разные контексты, но маловероятны и на сжатие будут оказывать небольшое влияние (скорее на корректность системы).

2. ДРУГИЕ МЕТОДЫ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАHИЯ

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

Это наблюдение было использовано Шенноном [93] для нахождения предела сжатия для английского текста. Он работал с людьми, пытающимися предугадать следующие друг за другом символы текста. На основании результатов этого опыта, Шеннон заключил, что лучшая модель имеет значение энтропии между 0.6 и 1.3 бит/символ. К сожалению, для осуществления сжатия и развертывания нам будет нужна пара дающих одинаковые предсказания близнецов. Джемисоны[45] использовали опыт Шеннона для оценки энтропии английского и итальянского текстов. Ковер и Кинг [21] описывали усовершенствованный эксперимент, состоявший в заключении пари между людьми по поводу появления следующего символа, позволивший сузить эти гpаницы. Эта методология была использована Таном для малайского текста [99].

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

2.1 Модели состояний

Вероятностные модели с конечным числом состояний основываются на конечных автоматах (КА). Они имеют множество состояний S(i) и вероятостей перехода P(i,j) модели из состояния i в состояние j. Пpи этом каждый переход обозначается уникальным символом. Т.о., чеpез последовательность таких символов любой исходный текст задает уникальный путь в модели (если он существует). Часто такие модели называют моделями Маркова, хотя иногда этот термин неточно используется для обозначения контекстно-ограниченных моделей.

Модели с конечным числом состояний способны имитировать контекстно-огpаниченные модели. Например, модель 0-й степени простого английского текста имеет одно состояние с 27 переходами обратно к этому состоянию: 26 для букв и 1 для пробела. Модель 1-й степени имеет 27 состояний, каждое с 27 переходами. Модель n-ой степени имеет 27^n состояниями с 27 переходами для каждого из них.

Модели с конечным числом состояний способны представлять более сложные по сравнению с контекстно-ограниченными моделями структуры. Простейший пример дан на рисунке 1. Это модель состояний для строки, в которой символ «a» всегда встречается дважды подряд. Контекстуальная модель этого представить не может, поскольку для оценки вероятности символа, следующего за последовательностью букв «a», должны быть pассмотpены пpоизвольно большие контексты.

Рисунок 1. Модель с ограниченным числом состояний для пар «a»

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

К сожаления удовлетворительные методы для создания хороших моделей с конечным числом состояний на основании обpазцов строк еще не найдены. Один подход заключается в просмотре всех моделей возможных для данного числа состояний и определении наилучшей из них. Эта модель растет экспотенциально количеству состояний и годится только для небольших текстов [30,31]. Более эвристический подход состоит в построении большой начальной модели и последующем сокращении ее за счет объединения одинаковых состояний. Этот метод был исследован Виттеном [111,112], который начал с контекстно-ограниченной модели k-го порядка. Эванс [26] применил его с начальной моделью, имеющей одно состояние и с количеством переходов, соответствующим каждому символу из входного потока.

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

Единственный из пpиводимых в литеpатуpе pаботающий достаточно быстpо, чтобы его можно было пpименять на пpактике, метод моделирования с конечным числом состояний, называется динамическим сжатием Маркова (ДМС) [19,40]. ДМС адаптивно работает, начиная с простой начальной модели, и добавляет по меpе необходимости новые состояния. К сожалению, оказывается что выбор эвристики и начальной модели обеспечивает создаваемой модели контекстно-огpаниченный хаpактеp [8], из-за чего возможности модели с конечным числом состояний не используются в полную силу. Главное преимущество ДМС над описанными в разделе 1 моделями состоит в предложении концептуально иного подхода, дающего ей возможность при соответсвующей реализации работать быстрее.

По сравнению с другими методами сжатия ДМС обычно осуществляет побитовый ввод, но принципиальной невозможности символьно-ориентированной версии не существует. Однако, на практике такие модели зачастую требуют много ОП, особенно если используется пpостая СД. Модели с побитовым вводом не имеют проблем с поиском следующего состояния, поскольку в зависимости от значения следующего бита существуют только два пеpехода из одного состояния в другое. Еще важно, что работающая с битами модель на каждом шаге осуществляет оценку в форме двух вероятностей p(0) и p(1) (в сумме дающих 0). В этом случае применение адаптивного арифметического кодирования может быть особенно эффективным [56].

Основная идея ДМС состоит в поддержании счетчиков частот для каждого пеpехода в текущей модели с конечным числом состояний, и «клонировании» состояния, когда соответствующий переход становится достаточно популярным. Рисунок 2 демонстрирует операцию клонирования, где показан фрагмент модели с конечным числом состояний, в которой состояние t — целевое. Из него осуществляется два перехода (для символов 0 и 1), ведущие к состояниям, помеченным как X и Y. Здесь может быть несколько переходов к t, из которых на рисунке показано 3: из U, V и W, каждый из которых может быть помечен 0 или 1 (хотя они и не показаны).

Рисунок 2. Операция клонирования в DMC

Предположим, что переход из U имеет большее значение счетчика частот. Из-за высокой частоты перехода U->t, состояние t клонирует добавочное состояние t’. Переход U->t изменен на U->t’, пpи этом другие переходы в t не затрагиваются этой операцией. Выходные переходы t передаются и t’, следовательно новое состояние будет хранить более присущие для этого шага модели вероятности. Счетчики выходных переходов старого t делятся между t и t’ в соответствии со входными переходами из U и V/W.

Для определении готовности перехода к клонированию используются два фактора. Опыт показывает, что клонирование происходит очень медленно. Другими словами, лучшие характеристики достигаются при быстром росте модели. Обычно t клонируется для перехода U->t, когда этот переход уже однажды имел место и из дpугих состояний также имеются пеpеходы в t. Такая довольно удивительная экспериментальная находка имеет следствием то, что статистики никогда не успокаиваются. Если по состоянию переходили больше нескольких раз, оно клонируется с разделением счетов. Можно сказать, что лучше иметь ненадежные статистики, основанные на длинном, специфичном контексте, чем надежные и основанные на коротком и менее специфичном.

Для старта ДМС нужна начальная модель. Причем простая, поскольку пpоцесс клонирования будет изменять ее в соответствии со спецификой встреченной последовательности. Однако, она должна быть в состоянии кодировать все возможные входные последовательности. Простейшим случаем является модель с 1 состоянием, показанная на рисунке 3, которая является вполне удовлетворительной. При начале клонирования она быстро вырастает в сложную модель с тысячами состояний. Немного лучшее сжатие может быть достигнуто для 8-битового ввода при использовании начальной модели, представляющей 8-битовые последовательности в виде цепи, как показано на рисунке 4, или даже в виде двоичного дерева из 255 узлов. Однако, начальная модель не является особо решающей, т.к. ДМС быстро приспосабливается к требованиям кодируемого текста.

Рисунок 3. Начальная модель ДМС с одним состоянием

Рисунок 4. Более сложная начальная модель

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

Даже более искусные модели с конечным числом состояний не способны отразить некоторые моменты должным обpазом. В особенности ими не могут быть охвачены pекуppентные стpуктуpы — для этого нужна модель, основанная на грамматике. Рисунок 5 показывает грамматику, моделирующую вложенные круглые скобки. С каждым терминальным символом связана своя вероятность. Когда исходная строка

Рисунок 5. Вероятностная грамматика для круглых скобок

pазбиpается согласно грамматике, то терминалы кодируются согласно своим вероятностям. Такие модели достигают хороших результатов при сжатии текстов на формальных языках, например, Паскале [13,50]. Вероятностные грамматики изучались также Озеки [72-74]. Однако, они не имеют большого значения для текстов на естественных языках главным образом из-за трудности нахождения их грамматики. Конструирование ее вручную будет утомительным и ненадежным, поэтому в идеале грамматика должна выводится механически из образца текста. Но это невозможно, поскольку постpоение гpамматики для выяснения огpаничений изучаемого языка требует анализа не принадлежащих ему пpимеpов [2,33].

2.3 Модели новизны

Они работают по принципу, что появление символа во входном потоке делает более веpоятным его новое появление в ближайшем будущем. Этот механизм аналогичен стопе книг: когда книга необходима, она извлекается из любого места стопы, но после использования кладется на самый верх. Т.о. наиболее популяpные книги будут ближе к вершине, что позволяет их быстрее находить. Многие автоpы разрабывали варианты этого алгоритма [10,24,39,47,88]. Обычно входной поток разбивается на слова (сцепленные символы, разделенные пробелом), которые используются как символы.

Символ кодируется своей позицией в обновляемом списке (стопке книг). Пpименяются коды переменной длины, наподобие предложенного Элиасом[23], в котоpом слова, расположенные ближе к вершине имеют более короткий код (такой метод подробно рассматривается в [58]). Существует несколько способов организации списка. Один — перемещать символы в самое начало после их кодирования, другой — перемещать их в сторону начала лишь на некоторое расстояние. Джонс в [47] применяет символьно-ориентированную модель, где код каждого символа определяется его глубиной в расширяемом дереве. После очеpедного своего кодиpования символы пpи помощи pасшиpения перемещаются вверх по дереву. Практическая реализация и характеристика некоторых моделей новизны приводится в [67].

2.4 Модели для сжатия изображений

До сих пор мы рассматривали модели применительно к текстам, хотя большинство из них может быть применено и для изображений. В цифровом представлении изобpажений главным объектом является пиксель, который может быть двоичным числом (для черно-белых изображений), оттенком серого цвета или кодом цвета. По меpе сканиpования изобpажения в качестве контекста будет полезно pассматpивать ближайшие пиксели из пpедыдущих линий. Техника, пригодная для черно-белых изображений, была предложена в [55], а для оттенков серого цвета в [102]. Пpименяемые копировальными машинами пpостые модели описаны в [42]. Метод сжатия картинок, которые по мере раскодирования становятся более узнаваемыми, описан в [113].

Сноски:
1 По-русски это, очевидно, «адаптивные» модели.
2 Обычно говорят «контекстные методы моделирования». наверх

Сайт подключен к Orphus. Если вы заметили опечатку, выделите слово и нажмите Ctrl+Enter. Спасибо!

Курсовая работа: Алгоритмы сжатия данных

Алгоритмы сжатия данных

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

Комбинаторная, вероятностная и алгоритмическая оценка количества информации

Моделирование и кодирование

Некоторые алгоритмы сжатия данных

BWT — преобразование и компрессор

Алгоритм арифметического кодирования

Реализация алгоритма арифметического кодирования

Доказательство правильности декодирования

Приращаемая передача и получение

Переполнение и завершение

Адаптивная модель для арифметического кодирования

Приложение 1. Программный код

Приложение 2. Интерфейс программы

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

Первые алгоритмы сжатия были примитивными в связи с тем, что была примитивной вычислительная техника. С развитием мощностей компьютеров стали возможными все более мощные алгоритмы. Настоящим прорывом было изобретение Лемпелем и Зивом в 1977 г. словарных алгоритмов. До этого момента сжатие сводилось к примитив­ному кодированию символов. Словарные алгоритмы позволяли кодир­овать повторяющиеся строки символов, что позволило резко повысить степень сжатия. Важную роль сыграло изобретение примерно в это же время арифметического кодирования, позволившего воплотить в жизнь идею Шеннона об оптимальном кодировании. Следующим прорывом было изобретение в 1984 г. алгоритма РРМ. Следует отметить, что это изобретение долго оставалось незамеченным. Дело в том, что алгоритм сложен и требует больших ресурсов, в первую очередь больших объемов памяти, что было серьезной проблемой в то время. Изобретенный в том же 1984 г. алгоритм LZW был чрезвычайно популярен благодаря своей простоте, хорошей рекламе и нетребовательности к ресурсам, несмотря на относительно низкую степень сжатия. На сегодняшний день алгоритм РРМ является наилучшим алгоритмом для сжатия текстовой информации, aLZW давно уже не встраивается в новые приложения (однако широко используется в старых).

Будущее алгоритмов сжатия тесно связано с будущим компью­терных технологий. Современные алгоритмы уже вплотную приблизи­лись к Шенноновской оценке 1.3 бита на символ, но ученые не видят причин, по которым компьютер не может предсказывать лучше, чем человек. Для достижения высоких степеней сжатия приходится использовать более сложные алгоритмы. Однако существовавшее одно время предубеждение, что сложные алгоритмы с более высокой степенью сжатия всегда более медленны, несостоятельно. Так, существуют крайне быстрые реализации алгоритмов РРМ для текстовой информации и SPIHT для графики, имеющие очень высокую степень сжатия.

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

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

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

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

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

При реализации алгоритма арифметического кодирования использовался язык C# и визуальная среда программирования MicrosoftVisualStudio 2005. Язык C# имеет следующие преимущества: простота, объектная ориентированность, типовая защищенность, “сборка мусора”, поддержка совместимости версий, упрощение отладки программ.

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

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

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

Таким образом, для передачи состояния объекта достаточно I=log2 Nбит информации. Заметим, что количество информации может быть дробным. Разумеется, дробное количество информации невозможно сохранить на носителе или передать по каналам связи. В то же время, если необходимо передать либо сохранить большое количество блоков информации дробной длины, их всегда можно сгруппировать таким образом, чтобы полностью исключить потери (например, посредством арифметического кодирования).

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

Обозначим через р(у|х) условную вероятность того, что наступит событие у если событие х уже наступило. В таком случае условная энтропия для переменной Y, которая может принимать М значений yi с условными вероятностями р(уi |х) будет

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

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

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

Моделирование обеспечивает предсказание вероятности наступ­ления возможных событий, кодирование обеспечивает представление события в виде -log2 pбит, где р — предсказанная вероятность наступ­ления события. Задача моделирования, как правило, более сложная. Это обусловлено высокой сложностью современных моделей данных. В то же время кодирование не является серьезной проблемой. Существует большое количество стандартных кодеров, различающихся по степени сжатия и быстродействию. Как правило, в системах сжатия исполь­зуемый кодер при необходимости может быть легко заменен другим.

Этот словарный алгоритм сжатия является самым старым среди методов LZ. Описание было опубликовано в 1977 г., но сам алгоритм разработан не позднее 1975 г.

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

Скользящее окно имеет длину N, т. е. в него помещается N символов, и состоит из двух частей:

■ последовательности длины W=N-nуже закодированных символов, которая и является словарем;

■ упреждающего буфера, или буфера предварительного просмотра, длины n; обычно и на порядки меньше W.

Пусть к текущему моменту времени мы уже закодировали tсимволов S1 , S2 , . St . Тогда словарем будут являться Wпредшествующих символов St -( W -1) , St -( W -1)+1, …, St . Соответственно, в буфере находятся ожидающие кодирования символы St +1 , St +2 , …, St + n . Очевидно, что если W≥ t, то словарем будет являться вся уже обработанная часть входной последовательности.

Идея алгоритма заключается в поиске самого длинного совпадения между строкой буфера, начинающейся с символа St +1 , и всеми фразами словаря. Эти фразы могут начинаться с любого символа St -( W -1) , St -( W -1)+1, …, St выходить за пределы словаря, вторгаясь в область буфера, но должны лежать в окне. Следовательно, фразы не могут начинаться с St +1 . поэтому буфер не может сравниваться сам с собой. Длина совпадения не должна превышать размера буфера. Полученная в результате поиска фраза St -( i -1) , St -( i -1)+1, …, St -( i -1)+( j -1) кодируется с помощью двух чисел:

1) смещения (offset) от начала буфера, i;

2) длины соответствия, или совпадения (matchlength), j;

Смещение и длина соответствия играют роль указателя (ссылки), одно­значно определяющего фразу. Дополнительно в выходной поток записывается символ s, непосредственно следующий за совпавшей строкой буфера.

Таким образом, на каждом шаге кодер выдает описание трех объектов: смещения и длины соответствия, образующих код фразы, равной обработанной строке буфера, и одного символа s(литерала). Затем окно смещается на j+1 символов вправо и осуществляется переход к новому циклу кодирования. Величина сдвига объясняется тем, что мы реально закодировали именно j+1 символов: j с помощью указателя на фразу в словаре и 1(? i) с помощью тривиального копирования. Передача одного символа в явном виде позволяет разрешить проблему обработки еще ни разу не виденных символов, но существенно увеличивает размер сжатого блока.

Алгоритм LZ78, предложенный в 1978 г. Лемпелом и Зивом, нашел свое практическое применение только после реализации LZW84, предложенной Велчем в 1984 г.

Словарь является расширяющимся (expanding). Первоначально в нем содержится только 256 строк длиной в одну букву-все коды ASCII. В процессе работы словарь разрастается до своего максимального объема |Vmax | строк (слов). Обычно, объем словаря достигает нескольких десятков тысяч слов. Каждая строка в словаре имеет свою известную длину и этим похожа на привычные нам книжные словари и отличается от строк LZ77, которые допускали использование подстрок. Таким образом, количество слов в словаре точно равно его текущему объему. В процессе работы словарь пополняется по следующему закону:

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позиции posисходного текста. Так как словарь первоначально не пустой, такое слово всегда найдется;

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

. Длина кода равна |position|+|B||=[logVmax]+8 (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте posсмещается на |strB|=|str|+l байт дальше к символу, следующему за В.

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

Птак как словарь увеличивается постепенно и одинаково для кодировщика и декодировщика, для кодирования позиции нет необходимости использовать [logVmax ] бит, а можно брать лишь [logV] бит, где V-текущий объем словаря.

Самая серьезная проблема LZ78-переполнение словаря: если словарь полностью заполнен, прекращается его обновление и процесс сжатия может быть заметно ухудшен (метод FREEZE). Отсюда следует вывод-словарь нужно иногда обновлять. Самый простой способ как только словарь заполнился его полностью обновляют. Недостаток очевиден кодирование начинается на пустом месте, как бы с начала, и пока словарь не накопится сжатие будет незначительным, а дальше-замкнутый цикл опять очистка словаря. Поэтому предлагается словарь обновлять не сразу после его заполнения, а только после того, как степень сжатия начала падать (метод FLUSH). Более сложные алгоритмы используют два словаря, которые заполняются синхронно, но с задержкой на |V|/2 слов один относительно другого. После заполнения одного словаря, он очищается, а работа переключается на другой (метод SWAP). Еще более сложными являются эвристические методы обновления словарей в зависимости от частоты использования тех или иных слов (LRU, TAG).

Выходной код также формируется несколько иначе (сравните с предыдущим описанием):

1. В словаре ищется слово str, максимально совпадающее с текущим кодируемым словом в позицииposисходного текста;

2. В выходной файл помещается номер найденного слова в словаре

. Длина кода равна |position|=[logV] (бит);

3. Если словарь еще не полон, новая строка strВ добавляется в словарь по адресу last_position, размер словаря возрастает на одну позицию;

4. Указатель в исходном тексте posсмещается на |str| байт дальше к символу В.

Алгоритм PPM (predictionbypartialmatching) — это метод контекстно-ограниченного моделирования, позволяющий оценить вероятность символа в зависимости от предыдущих символов. Строку символов, непосредственно предшествующую текущему символу, будем называть контекстом. Модели, в которых для оценки вероятности используются контексты длиной не более чем N, принято называть моделями порядка N.

Вероятность символа может быть оценена в контекстах разных порядков. Например, символ «о» в контексте «tobeornott» может быть оценен в контексте первого порядка «t», в контексте второго порядка «_t», в контексте третьего порядка «t_t» и т.д. Он также может быть оценен в контексте нулевого порядка, где вероятности символов не зависят от контекста, и в контексте минус первого порядка, где все символы равновероятны. Контекст минус первого порядка используется для того, чтобы исключить ситуацию, когда символ будет иметь нулевую вероятность и не сможет быть закодирован. Это может случиться, если вероятность символа не будет оценена ни в одном из контекстов (что возможно, если символ в них ранее не встречался).

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

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

BWT — преобразование и компрессор

BWT-компрессор (Преобразование Барроуза – Уиллера) — сравнительно новая и революционная техника для сжатия информации (в особенности-текстов), основанная на преобразовании, открытом в 1983 г. и описанная в 1994 г.. BWT является удивительным алгоритмом. Во-первых, необычно само преобразование, открытое в научной области, далекой от архиваторов. Во-вторых,даже зная BWT, не совсем ясно, как его применить к сжатию информации. В-третьих, BW преобразование чрезвычайно просто. И, наконец, сам BWT компрессор состоит из «магической» последовательности нескольких рассмотренных ранее алгоритмов и требует, поэтому, для своей реализации самых разнообразных программных навыков.

BWT не сжимает данные, но преобразует блок данных в формат, исключительно подходящий для компрессии. Рассмотрим его работу на упрощенном примере. Пусть имеется словарь V из N символов. Циклически переставляя символы в словаре влево, можно получить N различных строк длиной N каждая. В нашем примере словарь-это слово V=»БАРАБАН» и N=7. Отсортируем эти строки лексикографически и запишем одну под другой:

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

Фактический «выход» преобразования состоит из строки L=»РББАНАА» и первичного индекса I, показывающего, какой символ из L является действительным первым символом словаря V (в нашем случае I=2). Зная L и I можно восстановить строку V.

Этот алгоритм кодиро­вания информации был предложен Д.А. Хаффманом в 1952 году. Идея алгоритма состоит в следующем: зная вероятности вхождения символов в сообщение, можно описать процедуру построения кодов переменной длины, состоящих из целого количества битов. Символам с большей вероятностью присваиваются более короткие коды. Коды Хаффмана имеют уникальный префикс, что и позволяет однозначно их декодировать, несмотря на их переменную длину.

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево). Алгоритм построения Н-дерева прост и элегантен.

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

2. Выбираются два свободных узла дерева с наименьшими весами.

3. Создается их родитель с весом, равным их суммарному весу.

4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.

5. Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0.

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

Допустим, у нас есть следующая таблица частот:

Название: Алгоритмы сжатия данных
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 02:50:21 26 июля 2009 Похожие работы
Просмотров: 1052 Комментариев: 14 Оценило: 3 человек Средний балл: 5 Оценка: неизвестно Скачать
15 7 6 6 5
А Б В Г Д

На первом шаге из листьев дерева выбираются два с наименьшими весами — Г и Д. Они присоединяются к новому узлу-родителю, вес которого устанавливается в 5+6 = 11. Затем узлы Г и Д удаляются из списка свободных. Узел Г соответствует ветви 0 родителя, узел Д — ветви 1.

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

Рис. 2. Дерево кодирования Хаффмана после второго шага

На следующем шаге «наилегчайшей» парой оказываются узлы Б/В и Г/Д. Для них еще раз создается родитель, теперь уже с весом 24. Узел Б/В соответствует ветви 0 родителя, Г/Д—ветви 1.

На последнем шаге в списке свободных осталось только два узла — это А и узел (Б/В)/(Г/Д). В очередной раз создается родитель с весом 39 и бывшие свободными узлы присоединяются к разным его ветвям.


Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается. Н-дерево представлено на рис. 3.

Рис. 3. Окончательное дерево кодирования Хаффмана

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

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

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

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

Арифметическое сжатие — достаточно изящный метод, в основе которого лежит очень простая идея. Мы представляем кодируемый текст в виде дроби, при этом строим дробь таким образом, чтобы наш текст был представлен как можно компактнее. Для примера рассмотрим построение такой дроби на интервале [0, 1) (0 — включается, 1 — нет). Интервал [0, 1) выбран потому, что он удобен для объяснений. Мы разбиваем его на подынтервалы с длинами, равными вероятностям появления символов в потоке. В дальнейшем будем называть их диапазонами соответствующих символов.

Пусть мы сжимаем текст «КОВ.КОРОВА» (что, очевидно, означает «коварная корова»). Распишем вероятности появления каждого символа в тексте (в порядке убывания) и соответствующие этим символам диапазоны:

Символ Частота Вероятность Диапазон
О 3 0.3 [0.0; 0.3)
К 2 0.2 [0.3; 0.5)
В 2 0.2 [0.5; 0.7)
Р 1 0.1 [0.7; 0.8)
А 1 0.1 [0.8; 0.9)
“.” 1 0.1 [0.9; 1.0)

Будем считать, что эта таблица известна в компрессоре и декомпрессоре. Кодирование заключается в уменьшении рабочего интервала. Для первого символа в качестве рабочего интервала берется [0, 1). Мы разбиваем его на диапазоны в соответствии с заданными частотами символов (см. таблицу диапазонов). В качестве следующего рабочего интервала берется диапазон, соответствующий текущему кодируемому символу. Его длина пропорциональна вероятности появления этого символа в потоке. Далее считываем следующий символ. В качестве исходного берем рабочий интервал, полученный на предыдущем шаге, и опять разбиваем его в соответствии с таблицей диапазонов. Длина рабочего интервала уменьшается пропорционально вероятности текущего символа, а точка начала сдвигается вправо пропорционально началу диапазона для этого символа. Новый построенный диапазон берется в качестве рабочего и т. д.

Используя исходную таблицу диапазонов, кодируем текст «КОВ.КОРОВА»:

Исходный рабочий интервал [0,1).

Символ «К» [0.3; 0.5) получаем [0.3000; 0.5000).

Символ «О» [0.0; 0.3) получаем [0.3000; 0.3600).

Символ «В» [0.5; 0.7) получаем [0.3300; 0.3420).

Символ «.» [0.9; 1.0) получаем [0,3408; 0.3420).

Графический процесс кодирования первых трех символов можно представить так, как на рис. 4.

Рис. 4. Графический процесс кодирования первых трех символов

Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а его начало зависит от порядка следования символов в потоке. Можно обозначить диапазон символа с как [а[с]; b[с]), а интервал для i-го кодируемого символа потока как [li , hi ).

Большой вертикальной чертой на рисунке выше обозначено произвольное число, лежащее в полученном при работе интервале [/i , hi ). Для последовательности «КОВ.», состоящей из четырех символов, за такое число можно взять 0.341. Этого числа достаточно для восстановления исходной цепочки, если известна исходная таблица диапазонов и длина цепочки.

Рассмотрим работу алгоритма восстановления цепочки. Каждый следующий интервал вложен в предыдущий. Это означает, что если есть число 0.341, то первым символом в цепочке может быть только «К», поскольку только его диапазон включает это число. В качестве интервала берется диапазон «К» — [0.3; 0.5) и в нем находится диапазон [а[с]; b[с]), включающий 0.341. Перебором всех возможных символов по приведенной выше таблице находим, что только интервал [0.3; 0.36), соответствующий диапазону для «О», включает число 0.341. Этот интервал выбирается в качестве следующего рабочего и т. д.

Ниже показан фрагмент псевдокода процедур кодирования и декодирования. Символы в нем нумеруются как 1,2,3. Частотный интервал для i-го символа задается от cum_freq[i] до cum_freq[i-1]. Пpи убывании i cum_freq[i] возрастает так, что cum_freq[0] = 1. (Причина такого «обpатного» соглашения состоит в том, что cum_freq[0] будет потом содеpжать ноpмализующий множитель, котоpый удобно хpанить в начале массива). Текущий pабочий интеpвал задается в [low; high] и будет в самом начале pавен [0; 1) и для кодиpовщика, и для pаскодиpовщика.

С каждым символом текста обpащаться к пpоцедуpе encode_symbol(). Пpовеpить, что «завеpшающий» символ закодиpован последним. Вывести полученное значение интеpвала [low; high).

range = high — low

high = low + range*cum_freq[symbol-1]

low = low + range*cum_freq[symbol]

Value — это поступившее на вход число. Обpащение к пpоцедуpе decode_symbol() пока она не возвpатит «завеpшающий» символ.

//поиск такого символа, что

Из выражения (1) имеем:

В отличие от псеводокода, программа представляет low и high целыми числами. В псевдокоде текущий интеpвал пpедставлен чеpез [low; high), а в пpогpамме это [low; high] — интеpвал, включающий в себя значение high. Hа самом деле более пpавильно, хотя и более непонятно, утвеpждать, что в пpогpамме пpедставляемый интеpвал есть [low; high + 0.1111. ) по той пpичине, что пpи масштабитовании гpаниц для увеличения точности, нули смещаются к младшим битам low, а единицы смещаются в high.

По меpе сужения кодового интеpвала, стаpшие биты low и high становятся одинаковыми, и поэтому могут быть пеpеданы немедленно, т.к. на них будущие сужения интеpвала все pавно уже не будут влиять. Поскольку мы знаем, что low≤high, это воплотится в следующую пpогpамму:

low = 2 * (low — Half);

high = 2 * (high — Half) + 1;

гаpантиpующую, что после ее завеpшения будет спpеведливо неpавенство: low Half)

value = 2 * (value — Half) + input_bit();

low = 2 * (low — Half);

high = 2 * (high — Half) + 1;

Как показано в псевдокоде, арифметическое кодирование работает при помощи масштабирования накопленных вероятностей, поставляемых моделью в интервале [low; high] для каждого передаваемого символа. Пpедположим, что low и high настолько близки дpуг к дpугу, что опеpация масштабиpования пpиводит полученные от модели pазные символы к одному целому числу, входящему в [low; high]. В этом случае дальнейшее кодиpование пpодолжать невозможно. Следовательно, кодиpовщик должен следить за тем, чтобы интеpвал [low; high] всегда был достаточно шиpок. Пpостейшим способом для этого является обеспечение шиpины интеpвала не меньшей max_frequency — максимального значения суммы всех накапливаемых частот.

Как можно сделать это условие менее стpогим? Объясненная выше опеpация битового сдвига гаpантиpует, что low и high могут только тогда становиться опасно близкими, когда заключают между собой half. Пpедположим, они становятся настолько близки, что

first_qtr ≤low 14 — 1 и top_value = 2 16 — 1.

Мы pассмотpели пpоблему отpицательного пеpеполнения только относительно кодиpовщика, поскольку пpи декодиpовании каждого символа пpоцесс следует за опеpацией кодиpования, и отpицательное пеpеполнение не пpоизойдет, если выполняется такое же масштабиpование с теми же условиями.

Теперь рассмотрим возможность переполнения при целочисленном умножении. Переполнения не произойдет, если произведение range*max_frequency вмещается в целое слово, т.к. накопленные частоты не могут превышать max_frequency. range имеет наибольшее значение в top_value + 1, поэтому максимально возможное произведение в программе есть 2 16 *(2 14 — 1), которое меньше 2 30 .

При завершении процесса кодирования необходимо послать уникальный завершающий символ (EOF-символ), а затем послать вслед достаточное количество битов для гарантии того, что закодированная строка попадет в итоговый рабочий интервал. Т.к. пpоцедуpа done_encoding() может быть увеpена, что low и high огpаничены либо выpажением (1a), либо (1b), ему нужно только пеpедать 01 или 10 соответственно, для удаления оставшейся неопpеделенности. Удобно это делать с помощью пpоцедуpы bit_plus_follow(). Пpоцедуpа input_bit() на самом деле будет читать немного больше битов, из тех, что вывела output_bit(), потому что ей нужно сохpанять заполнение нижнего конца буфеpа. Hеважно, какое значение имеют эти биты, поскольку EOF уникально опpеделяется последними пеpеданными битами.

Программа должна работать с моделью, которая предоставляет пару перекодировочных таблиц index_to_char[] и char_to_index[], и массив накопленных частот cum_freq[]. Причем к последнему предъявляются следующие требования:

никогда не делается попытка кодиpовать символ i, для котоpого

cum_freq[0] — 4 битов/символ.

Дополнительные затpаты на масштабиpование счетчиков отчасти больше, но все pавно очень малы. Для коpотких текстов (меньших 2 14 байт) их нет. Hо даже с текстами в 10 5 — 10 6 байтов накладные pасходы, подсчитанные экспеpиментально, составляют менее 0.25% от кодиpуемой стpоки.

Адаптивная модель, пpи угpозе пpевышения общей суммой накопленных частот значение max_frequency, уменьшает все счетчики. Это пpиводит к тому, что взвешивать последние события тяжелее, чем более pанние. Т.о. показатели имеют тенденцию пpослеживать изменения во входной последовательности, котоpые могут быть очень полезными.

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

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

Для реализации использовался язык C# и визуальная среда программирования MicrosoftVisualStudio 2005. В результате программное обеспечение очень компактно, интуитивно понятно и эффективно в работе.

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

2. Сэломон Д. Сжатие данных, изображений и звука. Data Compression Methods. Серия: Мир программирования. Издательство: Техносфера, 2004. — 368 с.

3. Артюшенко В. М., Шелухин О. И., Афонин М. Ю. Цифровое сжатие видеоинформации и звука. Издательство: Дашков и Ко, 2004. — 426 с.

4. Седжвик Р. Фундаментальные алгоритмы на C++. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск. Издательство: ДиаСофт, 2002. — 688 с.

// Количество бит для кода

// Максимально возможное значениекода

const int top_value = (int)(((long)1 = 0; i—)

freq[i] = (freq[i] + 1) / 2;

/* Обновление перекодировочных таблиц в случае перемещения символа */

for (i = symbol; freq[i] == freq[i — 1]; i—) ;

Вопрос 36. Содержание процесса моделирования

Моделирование систем — это метод, с помощью которого, варь­ируя в эксперименте потоки материалов или предметов через опера­ции или процессы, можно определить влияние изменений различных переменных в системе. Моделирование представляет собой средство опытной проверки идей и представлений в условиях, которые невоз­можно было бы создать для реального эксперимента, учитывая свя­занные с этим затраты, время и риск. Это метод накопления опыта и обучения, результатом которого может быть разработка новой и луч­шей системы, оценка нескольких альтернативных систем или нахож­дение лучшего способа функционирования заданной системы. Моде­лирование по существу своему является заменой практического опы­та, который иначе был бы слишком дорог, продолжителен и рискован. Может оказаться, что специалисты моделирования, накопившие успешный опыт его применения, ориентируются в методике, но не ориентируются в постановке проблемы или в возможностях, имею­щихся в той или иной области. Они склонны применять эту методику независимо от того, существует ли сама проблема или возможность практического ее решения. Необходимо помнить, что моделирование систем представляет собой орудие исследования, и никто не может заранее предсказать, какими методами выразить лучшее понимание системы. Суждение от­носительно целесообразности усилий, направленных на создание мо­дели системы, должно основываться на рассматриваемой системе и ясном представлении, что в некоторых случаях эти усилия могут дать лишь незначительный результат. Процесс моделирования обязательно включает и построение аб­стракций и умозаключения по аналогии и конструирование новых сис­тем. Основная особенность моделирования в том, что это метод опо­средованного познания с помощью объектов заменителей. Модель выступает как своеобразный инструмент познания, который исследо­ватель ставит между собой и объектом и с помощью которого изучает интересующий его объект. Процесс моделирования включает три элемента: субъект (ис­следователь); объект исследования; модель, опосредующая отноше­ние познающего субъекта и познаваемого объекта. Первый этап моделирования — построение модели. Он пред­полагает наличие некоторых знаний об объекте — оригинале. На этом этапе важен вопрос о необходимой и достаточной мере сходства ори­гинала и модели. Любая модель замещает оригинал лишь в строго ог­раниченном смысле, и изучение одних сторон моделируемого объекта осуществляется ценой отказа от отражения других сторон. Из этого следует, что для одного объекта может быть построено несколько специализированных моделей, концентрирующих внимание на опре­деленных сторонах исследуемого объекта ила же характеризующих объект с разной степенью детализации.

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

1. Принцип компромисса между ожидаемой точностью резуль­татов моделирования и сложностью модели. В соответствии с этим принципом в процессе создания модели устанавливается разумный компромисс с использованием критерия «точность модели — затраты на создание модели». 2. Принцип баланса, точности требует соразмерности систе­матической погрешности моделирования и случайной погрешности в задании параметров описания. Этот принцип устанавливает требова­ние соответствия между точностью исходных данных и точностью мо­дели, между точностью отдельных элементов модели, между система­тической погрешностью модели и случайной погрешностью при интер­претации и усреднении результатов. 3. Принцип разнообразия элементов модели, в соответствии с которым количество элементов должно быть достаточным для прове­дения конкретных исследований 4. Принцип наглядности модели трактует, что при прочих рав­ных условиях модель, которая привычна, удобна, построена на обще­принятых терминах, обеспечивает, как правило, более значительные результаты, чем менее удобная и наглядная 5. Принцип блочного представления модели. Для его реали­зации следует соблюдать следующие правила:

— обмен информацией между блоками должен быть минималь­ным;

— блок модели, мало влияющей на интерпретацию результатов моделирования, является несущественным и подлежащим удалению;

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

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

— замена блока воздействиями, наихудшими по отношению к ис­следуемой части системы Прежде чем использовать модель необходимо в процессе ис­следования проверить, отвечает ли она предъявляемым требованиям:

— полноты, адаптивности, возможности включения достаточно широких изменений;

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

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

— удовлетворять требованиям и условиям, ограничивающим время решения задачи. При исследовании в реальном масштабе вре­мени допустимое время решения определяется ритмом функциониро­вания объекта при нештатных ситуациях;

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

— по возможности строиться с использованием общепринятой терминологии;

— предусматривать возможность проверки соответствия ее ориги­налу, проверки адекватности;

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

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

Вопрос 37 Имитационное моделирование, его место в исследовании и управлении

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

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

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

Имитационная модель строится по аналогии с объектом иссле­дования. Элементы могут описываться произвольно выбранными ис­следователем методами. Различают два вида имитационных моде­лей:

— детерминированные — модели с фиксированными входными параметрами и параметрами модели;

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

Имитационные модели как подкласс математических моде­лей можно классифицировать на статические, динамические и стохастические; дискретные и непрерывные.

Порядок построения имитационной модели и ее исследование включают следующие этапы.

1. Определение системы — установление границ, ограничений и измерителей эффективности системы, подлежащей изучению.

2. Формирование модели — переход от реальной системы к неко­торой логической схеме (абстрагирование).

3. Подготовка данных — отбор данных, необходимых для построе­ния модели, и представление их в соответствующей форме.

4. Трансляция модели — описание модели на языке, приемлемом для используемой ЭВМ.

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

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

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

8. Экспериментирование — процесс осуществления имитации с целью получения желаемых данных и анализа чувствительности.

9. Интерпретация — построение выводов по данным, полученным путем имитации.

10. Реализация — практическое использование модели и (или) ре­зультатов моделирования.

11. Документирование — регистрация хода осуществления проек­та и его результатов, а также документирование процесса создания и использования модели.

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

Оценка адекватности и точности математической модели явля­ется важнейшей задачей моделирования, так как любые исследования на неадекватной модели теряют смысл. Но с ростом адекватности и точности модели возрастают как стоимость, так и ценность ее для ис­следования. Приходится решать вопрос о компромиссе между стоимо­стью модели и последствиями ошибочных решений из-за ее неадек­ватности исследуемому процессу. Оценка адекватности и точности модели представляет собой непрерывный процесс, начинающийся с начала исследования и осуществляющийся на практике за счет повто­рения цикла «построение модели — проверка модели».

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

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Сдача сессии и защита диплома — страшная бессонница, которая потом кажется страшным сном. 8774 — | 7145 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

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

Аннотация научной статьи по народному образованию и педагогике, автор научной работы — Мокрый Валерий Юрьевич

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

Похожие темы научных работ по народному образованию и педагогике , автор научной работы — Мокрый Валерий Юрьевич,

области информационно-коммуникационных технологий у будущих учителей информатики

Development of information and technological competence of pre-service teachers of informatics based on the example of Course «Methods, algorithms and technologies of compression of information»

The development of information and technological competence as a leading component of professional competence of pre-service teachers of informatics is described based on the example of the elective course «Methods, algorithms and technologies of compression of information». The approach to the selection of the contents is described and the results of the theoretical and experimental research carried out are highlighted.

Текст научной работы на тему «Развитие информационно-технологической компетентности будущих учителей информатики на примере изучения дисциплины «Методы, алгоритмы и технологии сжатия информации»»

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

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

Ключевые слова: ФГОС ВПО, компетентностный подход, компетенции, методы, алгоритмы и технологии сжатия информации.

Development of information and technological competence of pre-service teachers of informatics based on the example of Course «Methods, algorithms and technologies of compression of information»

The development of information and technological competence as a leading component of professional competence of pre-service teachers of informatics is described based on the example of the elective course «Methods, algorithms and technologies of compression of information». The approach to the selection of the contents is described and the results of the theoretical and experimental research carried out are highlighted.

Keywords: competency approach, professional competencies, information technology competence, methods, algorithms and technologies of information.

В связи с переходом на новые ФГОС ВПО основной целью подготовки магистров направления «Педагогическое образование» становится развитие профессиональных компетенций будущего учителя информатики. В ФГОС ВПО магистров направления «Педагогическое образование» выделены профессиональные компетенции, формирующиеся у магистранта в процессе изучения дисциплин информационно-технологического цикла, в областях научно-исследовательской, проектной и методической деятельности.

Под компетенцией понимается «способность применять знания, умения и личностные качества для успешной деятельности в определенной области» [3, с. 18]. Кроме развития профессиональных компетенций в нашем исследовании изучается развитие профессиональной компетентности будущего учителя информатики.

Следуя за изложенным в работе [4, а 8], под профессиональной компетентностью учителя будем понимать «интегральную характеристику, определяющую способность решать профессиональные проблемы и ти-

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

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

Теоретический анализ исследований по проблеме развития ИТ-компетентности позволяет принять следующее определение понятия «ИТ-компетентность»: готовность учителя к решению профессиональных задач с использованием средств информационных технологий (задачи, связанные с учебно-методической и организационно-педагогической деятельностью учителя) [1].

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

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

Вариативность в подготовке магистров реализуется за счет модульной технологии обучения. В ФГОС ВПО модуль определяется как дисциплина базового или вариативного общенаучного или профессионального цикла и обеспечивает междисциплинарные связи учебного процесса (Г. А. Бордовский, Н. Ф. Радионова, Е. В. Пискунова).

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

• вариативный модуль, который можно встраивать в разные образовательные программы подготовки магистров;

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

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

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

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

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

Анализ подходов к определению понятия «информация» позволяет принять определение информации как некоторой измеримой величины или меры неопределенности (К. Шеннон). Термин «информация» как известие или руководство к действию превращается в сообщение, которое должно быть передано (М. Вернер). Сообщения или сигналы, содержащие абстрактную информацию, оцифровываются (данные, дискретная информация), а затем передаются по каналам связи (Д. С. Ватолин, В. И. Шульгин). Так как информация передается от источника по каналу связи к приемнику информации, то обязательно используются операции кодирования/декодирования информации.

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

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

Под методом сжатия, следуя за авторами работы [8], будем понимать «некоторое количество алгоритмов, объединенных методикой обработки определенного вида информации». С другой стороны, алгоритм сжатия — конкретная последовательность действий, определяющая процесс сжатия данных и реализованная в виде программы на одном из языков программирования.

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

Мы рассматриваем методику обучения будущих учителей информатики методам и алгоритмам сжатия данных.

Анализ программ подготовки магистров направления «Педагогическое образование»

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

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

B. Г. Маняхина, Т. Ю. Ильина, И. А. Румянцев, Е. Н. Самойлик, И. В. Симонова).

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

Анализ научных работ (А. И. Гурьев,

C. И. Змеев, С. И. Калинин, И. П. Подласый и др.), позволил выделить ведущие принципы отбора содержания дисциплины «Методы, алгоритмы и технологии сжатия информации»:

• научность — в содержание дисциплины необходимо включить изучение «магистральных» направлений в области сжатия информации, а именно рассмотреть распространенные стандарты сжатия изображений (JPEG и JPEG2000) и перспективные технологии сжатия информации (вейвлет-сжатие). Содержание обучения должно соответствовать уровню подготовки магистрантов, поэтому сначала изучаются методы (метод Хаффмана) и алгоритмы сжатия текстовых данных (алгоритмы арифметического и словарного сжатия), а затем — технологии сжатия изображений (стандарт JPEG,

технологии фрактального сжатия и вейвлет-сжатия изображений);

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

• доступность и наглядность — при изучении методов, алгоритмов и технологий сжатия данных необходимо использовать схемы, поясняющие этапы сжатия, имитационные модели и доступное программное обеспечение; объяснение темы необходимо сопровождать демонстрацией слайдов презентации с основными положениями изучаемой темы и использовать раздаточные материалы;

• систематичность и последовательность изложения — в структуре содержания дисциплины «Методы, алгоритмы и технологии сжатия данных» выделены вариативные (технологии фрактального сжатия) и инвариантные блоки (сжатие текстовой информации, стандарт JPEG, технологии вейвлет-сжатия изображений), определена последовательность изучения тем дисциплины (сначала изучаются методы и алгоритмы сжатия текстовой информации, основы работы в системе MATLAB, стандарт JPEG, затем технологии фрактального сжатия и вейвлет-сжатия изображений). Содержание дисциплины можно представить в виде блоков, относительно друг от друга не зависимых, которые можно интегрировать в содержание других дисциплин информационно-технологического цикла (модульная структура дисциплины);

• приоритет самостоятельной деятельности, опора на опыт магистрантов и ин-

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

• межпредметные связи — дисциплина «Методы, алгоритмы и технологии сжатия информации» является междисциплинарной. В процессе отбора содержания дисциплины учитывались связи с фундаментальными разделами информатики (теория информации, теория кодирования, теория цвета, теория обработки сигналов) и математики (математический анализ, теория множеств, геометрия, математическое моделирование). В программу дисциплины необходимо включить задания на актуализацию у магистрантов межпредметных связей (например, составление кластеров, выделение ключевых слов, анализ текстов);

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

Анализ рекомендаций по преподаванию информатики в университетах Computing Curricula 2001, требований ФГОС ВПО магистров направления «Педагогическое образование», ООП «Информационные технологии в физико-математическом образова-

Урок 7
Моделирование в среде текстового процессора

Представление о моделировании в среде текстового процессора

Словесные модели

Одним из видов знаковых моделей являются словесные модели — это описание мысленной модели на естественном языке.

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

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

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

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

Рассмотрим поэтапно суть использования словесных моделей.

ПОСТАНОВКА ЗАДАЧИ

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

ЦЕЛИ МОДЕЛИРОВАНИЯ

РАЗРАБОТКА МОДЕЛИ

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

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

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

Компьютерный эксперимент со знаковой моделью включает следующие стадии работы:

ЗАДАЧА 2.1. Словесный портрет

I этап. Постановка задачи

ОПИСАНИЕ ЗАДАЧИ

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

ЦЕЛЬ МОДЕЛИРОВАНИЯ

Набрать и расположить на странице текст. Сохранить текст.

ФОРМАЛИЗАЦИЯ ЗАДАЧИ

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

II этап. Разработка модели

ИНФОРМАЦИОННАЯ МОДЕЛЬ

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

КОМПЬЮТЕРНАЯ МОДЕЛЬ


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

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

1. Создать документ в прикладной среде текстового процессора.

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

3. Набрать текст, используя основные правила набора текста:

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

4. Проверить орфографию.

5. Расставить переносы при помощи команды Расстановка переносов.

6. Сохранить текст под некоторым именем.

III этап. Компьютерный эксперимент

ПЛАН ЭКСПЕРИМЕНТА

1. Провести тестирование модели как компьютерного документа.

2. Провести тестирование смыслового содержания модели.

ПРОВЕДЕНИЕ ИССЛЕДОВАНИЯ

1. Убедиться, что оформление компьютерного документа соответствует замыслу, в противном случае изменить параметры текста.

2. Для проверки смыслового содержания текста зачитайте его своим одноклассникам. Спросите их мнение.

IV этап. Анализ результатов

Если компьютерная модель соответствует замыслу, передать текст на конкурс. Иначе вернуться к предыдущим этапам.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

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

Моделирование составных документов

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

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

ЗАДАЧА 2.3. Поздравительная открытка

I этап. Постановка задачи

ОПИСАНИЕ ЗАДАЧИ

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

ЦЕЛЬ МОДЕЛИРОВАНИЯ

Красиво оформить поздравление.

ФОРМАЛИЗАЦИЯ ЗАДАЧИ

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

II этап. Разработка модели

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

1. Создать новый документ в среде текстового процессора.

2. Установить параметры страницы.

3. Установить обрамление страницы.

4. Установить 2 колонки.

5. Вставить рисунок из коллекции рисунков.

6. Установить выравнивание по центру строки.

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

8. Вставить объект WordArt в качестве заголовка.

9. Набрать текст и подпись.

10. Подобрать параметры текста опытным путем.

III этап. Компьютерный эксперимент

1. Пошаговый просмотр.

2. Просмотр документа.

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

IV этап. Анализ результатов

♦ Если вид объекта не соответствует замыслу, изменить значения параметров объекта.

♦ Если вид документа не соответствует замыслу, откорректировать модель.

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

ЗАДАЧА 2.4. Научный текст

I этап. Постановка задачи

ОПИСАНИЕ ЗАДАЧИ

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

Оформите как научный текст фрагмент материала из учебника по физике или математике.

ЦЕЛЬ МОДЕЛИРОВАНИЯ

Набрать и оформить текст в виде, способствующем лучшему запоминанию. Сохранить информацию.

ФОРМАЛИЗАЦИЯ ЗАДАЧИ

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

II этап. Разработка модели

ИНФОРМАЦИОННАЯ МОДЕЛЬ

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

КОМПЬЮТЕРНАЯ МОДЕЛЬ

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

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

III — IV этапы. Компьютерный эксперимент и анализ результатов

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

Понятен ли текст?

Какие приемы оформления способствуют лучшему пониманию?

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

2.5. Наградной диплом.

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

РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ

1. Рассмотрите примеры дипломов, предлагаемые, например, в среде Word.

2. Используйте обрамление страницы.

3. Для создания красивых полос используйте символы шрифта Wingdings английской раскладки клавиатуры En.

2.6. Объявление.

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

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

Составьте эскиз объявления на выбранную тему.

РЕКОМЕНДАЦИИ ПО ВЫПОЛНЕНИЮ

Для указания в объявлении контактного телефона используйте инструментарий встроенной векторной графики.

Педагогический опыт «Метод моделирования при решении текстовых задач»

«НАЧАЛЬНАЯ ШКОЛА № 15»

«Учитель года 2020»

при решении текстовых задач»

«Математике должно учить в школе

еще с той целью, чтобы познания,

здесь приобретаемые, были достаточными

для обыкновенных потребностей в жизни»

ИНФОРМАЦИЯ ОБ ОПЫТЕ

1.Актуальность педагогического опыта

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

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

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

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

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

Разрешение этих противоречий и обусловило выбор темы: «Метод моделирования при решении текстовых задач».

Я считаю, что богатые возможности для развития интереса к математике, логического мышления младших школьников открывает система работы над текстовыми задачами методом моделирования.

2.Методологическая база педагогического опыта

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

Условно можно выделить два основных направления в исследованиях по использованию моделирования в обучении:

    Первое направление посвящено вопросам влияния моделирования на умственное развитие ученика (, , ). Второе направление исследований затрагивает в основном методические аспекты применения моделирования в учебном процессе (, , ГА. Варданян, СИ. Волкова, Я. Дадоджанов, , ).

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

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

Для реализации цели необходимо решение следующих задач:

Систематически применять существующий методический подход к обучению решению задач. Формировать у обучающихся через уроки математики умение моделировать. Разработать и ввести в педагогическую практику уроки с использованием метода моделирования.

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

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

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

3. План мероприятий по реализации опыта работы

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

Изучение и анализ:

— концепции развивающего обучения (, , );

— сюжетных задач по математике ()

Разработка содержания педагогического опыта

Формулирование проблемы, идеи, цели и задач проекта, составление плана мероприятий

январь 2020 года

Составление классификации учебных моделей

Описание метода направленного на развитие способности моделирования младшего школьника

Описание ожидаемых результатов

Подбор диагностического инструментария для определения уровня развития способности моделирования

Практическая реализация проекта

май 2020, 2020, 2020, 2020 г. г.

Практическое использование метода моделирования на уроках математики

с февраля 2020 года

Составление технологической карты урока

Ведение диагностики с последующей обработкой результатов

декабрь, май ежегодно

Описание собственной педагогической практики с анализом и выводами

Прохождение курсовой подготовки: курсы, семинары и т. д.

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

Учебно-методические материалы (методические рекомендации, сценарии уроков, научные статьи и др.);

2020-2020 учебный год

Составление методических рекомендаций для учителей начальных классов

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

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

Личностные универсальные учебные действия

— внутренняя позиция учащегося;

— адекватная мотивация учебной деятельности;

— ориентация на моральные нормы и их выполнение.

Регулятивные универсальные учебные действия

— способностью принимать и сохранять учебную задачу;

— планировать реализацию задачи;

— контролировать и оценивать свои действия;

— вносить коррективы в выполнение действий.

Познавательные универсальные учебные действия

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

Коммуникативные универсальные учебные действия

— умения учитывать позицию собеседника;

— организовывать сотрудничество и кооперацию с учителем и сверстниками;

— адекватно воспринимать и передавать информацию;

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

Кроме этого предполагается повышение уровня сформированности умения решать текстовые задачи при помощи моделирования на уроках математики по возрастам:

Учащиеся должны уметь:

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

Программа для 1 класса (по )

Понятия, которыми должны овладеть учащиеся

Виды задач, решаемые в данном классе

1. Представление о задаче.

2. Вопрос (требование) задачи.

3. Известные (данные) значения величин.

4. Искомое значение величины.

5. Слова-признаки соотношений сложения и вычитания.

1. Расчленение текста простой задачи на условие и требование (вопрос).

2. Построение схематической модели простых задач на сложение и вычитание.

3. Составление простых задач на сложение и вычитание:

а) по заданному условию;

б) по заданному вопросу.

1. Простые задачи вида равенства и неравенства.

2. Простые разрешаемые задачи на сложение и вычитание.

3. Косвенные простые задачи на сложение и вычитание.

Учащиеся должны уметь:

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

Понятия, которыми должны овладеть учащиеся

Виды задач, решаемые в данном классе

1. Слова-признаки соотношения разностного сравнения.

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

3. Слова-признаки разбиения целого на равные части.

1. Составление задачи, обратной данной.

2. Построение схематичной и графической модели задач.

3. Составление текста задачи по ее модели.

4. Составление задач по результатам наблюдений, измерений.

5. Подбор данных к заданному вопросу и подбор вопроса к заданным данным.


1.Простые задачи соотношения:

а) разностного соотношения;

б) перехода от одной единицы счета или измерения к другой;

в) разбиения целого на равные части.

2. Сложные открытые задачи из двух соотношений.

Учащиеся должны уметь:

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

Понятия, которыми должны овладеть учащиеся

Виды задач, решаемые в данном классе

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

Учащиеся должны уметь:

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

Понятия, которыми должны овладеть учащиеся

Виды задач, решаемые в данном классе

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

— владеть методом формирования у обучающихся умения моделирования при решении текстовых задач.

5.Описание деятельностного аспекта

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

«Моделирование – процесс построения моделей для каких-либо познавательных целей. Модель – это объект или система, исследование которой служит средством для получения знаний о другом объекте – оригинале или прототипе модели». (, ).

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

Исходя из общей классификации моделей, я использую в своей работе таблицу «Моделирование текстовых задач»:

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

Поэтому обучение моделированию веду целенаправленно, соблюдая ряд условий:

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

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

1. Использование чертежа при решении простых задач

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

а) Задача (1 кл.). В вазе лежит всего 10 яблок, из них одно зеленое, а остальные красные. Сколько красных яблок в вазе?

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

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

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

б) Моделирование текстовой задачи в виде отрезка продолжаю и в следующих классах.

Пример моделирования нестандартной текстовой задачи в виде отрезка.

Задача. На чемпионате в школе по игре в шахматы Сережа сыграл 12 партий. Когда у него спросили, сколько же партий он выиграл, Сережа ответил: “Две партии я проиграл, а из остальных на каждые две партии вничью у меня 3 выигранных”. Сколько шахматных побед у Сережи?

Модель данной задачи.

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

2. Предметное моделирование

Изобрази с помощью кружков красного и белого цвета то, о чем говорится в задаче: “У дома 3 клумбы и у школы столько же клумб. Сколько всего клумб у дома и школы?” Что обозначают кружки красного цвета? Кружки желтого цвета?

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

3. Схематический рисунок

Задача (1 кл.). У хозяйки 9 кур, а уток на 4 больше.

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

Маша сделала такой рисунок:

Кто прав: Маша или Миша?

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

4. Математическое моделирование (формулы)

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

(К каждому выражению нужно поставить вопрос).

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

5. Информационная модель (таблица, график, диаграмма)

Задача. Отец старше сына в 4 раза, через 20 лет он будет старше сына в 2 раза. Сколько лет отцу?

Возраст через 20лет (отец)

Возраст через 20лет (сын)

Нет
Нет
Нет
Нет
В 2 раза

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

6.Выводы и результаты работы

по моделированию задач на уроках математики:

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

При поступлении в 1 класс школьники не проходят никакого отбора, обучаются все с учётом индивидуальных особенностей и склонностей. В сентябре 2015 я начала работать в 1 «В» классе. В октябре была проведена диагностика по методике и на выявления уровня интеллектуального развития младших школьников. Результаты диагностики показали, что сформировалось несколько различных групп. Из 28 учащихся класса имеют:

высокий уровень – 8% обучающихся;

нормальный уровень – 24% обучающихся;

ниже среднего – 32% обучающихся;

низкий – 36% обучающихся.

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

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

— у большинства обучающихся сформировалась положительная мотивация к изучению математики;

— более эффективно формируется навык творческого подхода к решению практических задач;

— создаются предпосылки для более осознанного изучения математики;

— более эффективно развиваются ключевые компетентности;

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

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

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

Подготовительные упражнения для моделирования задач.

1. Обозначить на чертеже числа из рассказов.

а) в одном ведре было а кг яблок, а в другом е кг.

б) в одном ведре было р кг яблок, а в другом на в кг меньше.

2. Построить модель отношения «больше на» и определить способ нахождения большей величины.

а) в парке росло 150 берез и несколько лип. Лип было на 30 больше, чем берез. Сколько было лип?

3. Составь по чертежу задачу о покупке красных и синих шаров. Одну задачу составь со словом «больше», другую со словом «меньше». Реши задачи.

4.Какой чертеж будешь использовать, решая задачу: «В книге 36 страниц. Это на 17 страниц больше, чем во второй книге. Сколько страниц во второй книге?»

5. Какой могла быть модель, если решение задачи было таким: 18+13,
17 – 10 ?

7. Как нужно изменить чертеж, если вопрос задачи будет таким: «На сколько больше ящиков с помидорами, чем с огурцами, привезли в магазин?»

8. Построй модель к задаче: «В двух коробках 36 карандашей. Сколько карандашей во второй коробке, если в первой их 17?»

9. Запиши в нужные клетки таблицы следующие числа: 57, 75, 44, 74, 55, 77, 47. Какие числа нужно записать в оставшиеся клетки?

Как найти величину, обозначенную знаком «?» ? Запишите формулу.

11. Сколько разностей можно составить из чисел 30, 25, 17, 9, если для их составления брать по два числа? Будут ли среди них разности, значение которых равны?

Графические модели решения задач по математике.

Таня нарисовала 5 домиков, а Сережа на 4 больше. Сколько домиков нарисовал Сережа?

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

1. а) в виде рисунка

б) в виде условного рисунка

в) в виде чертежа

г) в виде схематизированного чертежа

«КЛЮЧЕВЫЕ» СЛОВА В ТЕКСТЕ ЗАДАЧИ

    В … раз (больше, меньше)

Целое из равных частей

    по … в каждом …,
    поровну в каждом ряду …,

    В одинаковых …,

    … доля …

Целое из разных частей

    Было

    Привезли (купили, подарили, приехали, …)

    Стало

«Таблица отношений величин»

Задача. У девочки несколько зеленых шаров и 3 красных. Всего 8 шаров. Сколько зеленых шаров у девочки?

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

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

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

Опишите ситуацию с помощью схемы.

а) Было 4 треугольника синего и один красный. Всего 5 треугольников.

б) Было 5 треугольников. Из них 4 синих, а 1 красный.

в) Синих квадратов 2, а красных на 4 больше.

Составьте рассказ по схемам (неизвестна часть и целое)

Прочитайте и расшифруйте схему (предлагаются модели различного вида).

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

Задача. На швейной фабрике мастер шил одинаковые пальто, израсходовав на них 24 м ткани. Его ученица сшила на 6 пальто меньше, израсходовав на них в 4 раза меньше ткани. Сколько всего пальто сшили мастер и ученица?

Задачу можно решить традиционно — по вопросам (6 действий), находя расход ткани на одно изделие. Но можно решить и другим способом — гораздо быстрее. Из чертежа модели текста задачи следует, что на 3 части приходится 6 пальто, тогда на 1 часть – 2 пальто. Всего – 5 частей (1+4) или 10 пальто (по 2 – 5 раз, 2х5=10).

3. При решении задач осуществляю дифференцированный подход:

Задача. В двух корзинах 75 яблок. Когда из первой взяли 6, а из второй 9, то в корзине осталось яблок поровну. Сколько яблок было в каждой корзине?

Для самостоятельного решения данной задачи в соответствии с уровнем подготовленности детям предлагаю следующие чертежи.

По этим чертежам предлагаю следующие задания:

Рассмотри чертеж и реши задачу. Закончи чертеж к задаче. Обозначь на нем данные и искомое и реши задачу.

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

При решении текстовых задач действия должны пройти через 3 этапа:

1. Целенаправленно отрабатывается в операциях с объемным предметам или их заменителями;

2. Проговаривается, сначала громко, затем про себя;

3. Переход в умственные действия.

Использую следующие графические схемы.

Дети посадили у школы 6 лип и 4 березы. Сколько всего деревьев посадили дети у школы?

В нашем доме 9 этажей, Это на 4 этажа больше, чем в соседнем. Сколько этажей в соседнем доме?

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

Например, я предлагаю выбрать модель к задаче №3 «На ветке сидело несколько птиц. После того как 5 птиц улетели, их осталось 9. Сколько птиц сидело на ветке?»

«ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ АНАЛИЗА И МОДЕЛИРОВАНИЯ ТЕКСТОВЫХ ДАННЫХ Монография Воронеж Издательство «Научная книга» УДК . »

Л.С. Ломакина, А.С. Cуркова

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

АНАЛИЗА И МОДЕЛИРОВАНИЯ

ТЕКСТОВЫХ ДАННЫХ

Издательство «Научная книга»

Рецензенты:

Турлапов В.Е. д-р. техн. наук (Нижегородский государственный

университет им. Н.И. Лобачевского)

д-р физ.-мат. наук (Институт прикладной физики РАН)

Л 74 Ломакина, Л.С. Информационные технологии анализа и моделирования текстовых структур: Монография / Л.С. Ломакина, А.С. Суркова. – Воронеж: Издательство «Научная книга», 2015. – 208 c.

ISBN 978-5-98222-863-5 В книге излагаются актуальные проблемы построения моделей текстовых данных и создания на их основе систем обработки и анализа текстов с учетом структурных особенностей текстов. Основные задачи анализа текстовых данных кластеризация, классификация,

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

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

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

Рис. 47. Табл. 27. Библиогр.: 131 назв.

УДК 004.912 ББК 32.81 Л 74 © Ломакина Л.С., Суркова А.С., 2015 ISBN 978-5-98222-863-5

СОДЕРЖАНИЕ

Часть I. Методологические аспекты анализа и моделирования текстовых данных

1. Основные задачи анализа и обработки текстовых данных. 8

2. Основные принципы анализа текстовых данных

2.1. Принцип системного представления текстов

2.2. Принцип нечеткой логики

2.3. Принцип обучающихся систем

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

Часть II. Теоретические аспекты анализа и обработки текстовых данных

4. Основные аспекты системного представления текстов

4.1. Основные понятия и определения

4.2. Структурно-статистический подход

4.3. Информационный подход

4.4. Использование N-грамм

4.5. Использование моделей сжатия

5. Основные аспекты нечеткой логики

5.1. Основные понятия и определения

5.2. Модели нечеткой кластеризации

6. Основные аспекты обучающихся систем

6.1. Модель процесса обучения

6.2. Алгоритмический подход к построению обучающихся систем 122

6.3. Задачи классификации в обучающихся системах

6.4. Основные понятия и определения нейросетевых технологий. 133 Часть III. Практические аспекты анализа и обработки текстовых данных

7. Алгоритмическое и программное обеспечение анализа и обработки текстов

7.1. Алгоритмы на основе структурно-иерархического представления текста

7.2. Алгоритмы на основе методов сжатия

7.3. Нечеткие алгоритмы в задачах анализа и обработки текстов. 151

7.4. Алгоритмы с использованием нейросетевых технологий. 163

7.5. Алгоритмы с использованием деревьев принятия решений. 166

8. Практическая реализация алгоритмов решения основных задач 171


8.1. Примеры кластеризации текстовых данных

8.2. Примеры классификации текстовых данных

8.3. Примеры идентификации текстовых данных

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

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

Область, занимающаяся проблемами обработки все увеличивающегося объема текстовой информации, получила название Text Mining. На русский этот термин можно перевести как Интеллектуальный анализ текстов аналогично уже устоявшемуся понятию Data Mining – интеллектуальный анализ данных. Предметную область Text Mining как согласованную совокупность задач можно описать следующим образом. К числу традиционных проблем можно отнести задачи определения авторства, автоматического извлечения ключевых слов, аннотирования и реферирования, кластеризации и классификации по тематическим категориям и т.д. К недавно возникшим задачам относятся проблема анализа текстов в глобальной сети для обеспечения безопасности и выявления потенциально опасных или нежелательных сообщений, а также задачи, связанные с многоязыковыми текстами и проблемой «переводного» плагиата и заимствования.

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

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

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

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

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

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

В третьей части в разделе «Алгоритмическое и программное обеспечение анализа и обработки текстов» приведены конкретные алгоритмы анализа текстовых данных, основанные на системном представлении текстов. Рассмотрены базовые нечеткие методы кластеризации, такие как fuzzy c-means (FCM), Kernel Fuzzy Clustering и др. и предложенные модификации алгоритмов классификации и кластеризации на основе нечетких отношений. Также в данном разделе описаны алгоритмы решения основных задач анализа текстов на основе нейронных сетей, деревьев принятия решений и подхода Random forest.

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

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

Библиографический список Андреев А.М., Березкин Д.В., Морозов В.В., Симаков К.В. Метод кластеризации документов текстовых коллекций и синтеза аннотаций кластеров // Труды 10-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции»

– RCDL’2008, Дубна, Россия, 2008. с 220-229 Арапов М.В. Квантитативная лингвистика. – М.: Наука, 1988. – 184 с.

Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. Методы и 3.

модели анализа данных: OLAP и Data Mining. – СПб.: БХВ-Петербург, 2004. – 336 с.

Белозерова Н.Н. Можно ли поверить дискурс фракталом? //Язык и литература, 2002, №16. – Тюмень, изд-во ТюмГУ, 2002.

Белоногов Г.Г., Кузнецов Б.А. Языковые средства автоматизированных 5.

информационных систем. М., 1983. Мельников Г.П. Системный подход в лингвистике. // Системные исследования. Ежегодник. – М.: Наука, 1972.

Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). М., Наука. 1974. 416 с.

Верещагин Н.К., Успенский В.А., Шень А. Колмогоровская сложность и 7.

алгоритмическая случайность. – М.: МЦНМО, 2013.

Воронцов К.В. Машинное обучение (курс лекций). Режим доступа:

Гальперин И.Р. Текст как объект лингвистического исследования – М.:

Наука, 1981. – 140 с.

Гладких А.В. Синтаксические структуры естественного языка в автоматизированных системах сообщений. – М.: Наука, 1985.

Городецкий Б.Ю. Компьютерная лингвистика: моделирование языкового 11.

общения //Новое в зарубежной лингвистике. Вып. 24. — М., 1989.

Дмитриев А.С. Хаос, фракталы и информация //Наука и жизнь, 2001, №5 12.

Дюран Б., Одел П. Кластерный анализ. М., Статистика, 1977. – 128 с.

Егорушкин А. У каждого свой язык. //Компьютера – 2002, №21.

Еремеев А.П. Построение решающих функций на базе тернарной логики 15.

в системах принятия решений в условиях неопределенности // Изв. РАН.

Теория и системы управления. 1997. N 5. — с. 138-143 Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир. – 1976. – 164 с.

Заде Л.А. Размытые множества и их применение в распознавании образов 17.

и кластер-анализе // Классификация и кластер. М.: Мир, 1980., с. 208-247 Колмогоров А.Н. Три подхода к определению понятия «Количество информации» // Новое в жизни, науке, технике. Сер. “Математика, кибернетика”. 1991, №1, стр. 24-29 Костышин А.С. О применимости некоторых формальных методов для исследования полных строений текстов. //Материалы конференции КВАЛИСЕМ-2000 – Новосибирск, изд-во Новосибир. гос. пед. ун-та., 2000.

Кофман А. Введение в теорию нечетких множеств. – М., Радо и связь, 20.

Ландэ Д.В., Снарский А.А., Безсуднов И.В. Интернетика. Навигация в 21.

сложных сетях: модели и алгоритмы. – M.: Либроком, 2009. – 264 с.

Леоненков А.В. Нечеткое моделирование в среде Matlab и fuzzyTECH. – 22.

С.Пб.: BHV-Санкт-Петербург, 2003. – 736 с.

Леонтьева Н.Н. Динамика единиц в семантических структурах. //Труды 23.

Международного семинара Диалог-2002 по компьютерной лингвистике и ее приложениям. Том 1. Теоретические проблемы. – М., 2002.

Лингвистический энциклопедический словарь. – М.: 1990.

Ломакин Д.В., Панкратова А.З., Суркова А.С. Золотая пропорция как инвариант структуры текста. // Журнал «Вестник Нижегородского университета им. Н.И. Лобачевского», 2011, №4, с. 196-199.

Ломакина Л.С., Мордвинов А.В., Суркова А.С. Построение и исследование 26.

модели текста для его классификации по предметным категориям. // Системы управления и информационные технологии, 2011, №1(43), с. 16-20.

Ломакина Л.С., Родионов В.Б., Суркова А.С. Иерархическая кластеризация текстовых документов. // Системы управления и информационные технологии, 2012, № 2(48), с. 39-44.

Ломакина Л.С., Суркова А.С. Автоматизированные информационнопоисковые системы. Задачи. Принципы. Методология: учеб. пособие / Л.С. Ломакина, А.С. Суркова; Нижегор. гос. техн. ун-т им. Р.Е. Алексеева. – Н. Новгород, 2011. – 109 с.

Ломакина Л.С., Суркова А.С., Буденков С.С. Кластеризация текстовых 29.

данных на основе нечеткой логики // Системы управления и информационные технологии, №1(55), 2014. – С. 73-77.

Мартыненко Г.Я. Основы стилеметрии. – Л.: Изд-во ЛГУ, 1988. – 176 с.

Мельничук А. С. Понятие системы и структуры языка. // Вопросы языкознания, 1970, №1. С. 27 Мельчук И.А. Русский язык в модели «Смысл Текст». Москва-Вена, 32.

Минский М. Фреймы для представления знаний. — М.: Энергия. 1979.

Москальская О.И. Грамматика текста. М.: Наука, 1981.

Москальчук Г.Г. Структура текста как синергетический процесс. М.:

УРСС, 2003. Москальчук Г.Г. Структурная организация и самоорганизация текста. – Барнаул, 1998.

Мурзин Л.Н., Штерн А.С. Текст и его восприятие – Свердловск, 1991.

Нариньяни А.С. Автоматическое понимание текста — новая перспектива // 37.

Труды международного семинара Диалог-97 по компьютерной лингвистике и ее приложениям. — Москва, 1997, с. 203-208.

Негуляев В.А. Исследование коммуникативных микроструктур патентного текста и их роли для автоматической обработки информации.

//Вычислительная лингвистика. М.: Наука, 1976.

Нечеткие множества в моделях управления и искусственного интеллекта 39.

/ Под ред. Д.А.Поспелова. – М., Наука, 1986. 312 с.

Нечеткие множества и теория возможностей. Последние достижения / 40.

Под ред. Р.Р.Ягера. – М.: Радио и связь, 1986.– 408 с.

Орлов Ю.К. Обобщенный закон Ципфа-Мандельброта и частотные 41.

структуры информационных единиц различных уровней.

//Вычислительная лингвистика. М.: Наука, 1976.

Поликарпов А.А. Циклические процессы в становлении лексической системы языка: моделирование и эксперимент – М., 2001.

Пономаренко И.Н. Фрактал в структуре художественного текста 43.

//Русский язык: исторические судьбы и современность. II Международный конгресс русистов-исследователей. – М., 2004.

Прангишвили И.В. Системный подход и общесистемные закономерности.

– М.: СИНТЕГ, 2000, 528с.

Прикладная статистика: Классификации и снижение размерности: Справ.

изд. / Под ред. С. А. Айвазяна. — М.: Финансы и статистика, 1989. — 607 с.

Романов А.С. Методика идентификации автора текста на основе аппарата 46.

опорных векторов // Доклады ТУСУРа. – 2009. – № 1 (19), ч. 2. – С. 36–42 Руспини Э.Г. Последние достижения в нечетком кластер-анализе // Нечеткие множества и теория возможностей: Последние достижения / Под ред. Р.Р. Ягера; — М: Радио и связь, 1986.— с. 114-132.

Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. — М.: Горячая линия — Телеком, 2006.

Рыжов А.П. Элементы теории нечетких множеств и измерения нечеткости. М., Диалог-МГУ, 1998.

Сайт, посвященный литературоведческой атрибуции: http://corneillemoliere.com/.

Сафронова Ю.Б. Некоторые системно-количественные характеристики 51.

лексико-семантических парадигм разных видов. //Уч. зап. ТГУ. Вып. 745.

Скороходько Э.Ф. Семантические сети и автоматическая обработка текста. Киев, Наукова думка, 1983. – 218 с.

Сметанин Ю. Г., Ульянов М. В. Мера символьного разнообразия: подход 53.

комбинаторики слов к определению обобщенных характеристик временных рядов // Бизнес-информатика №3 (29) 2014. с. 40–48.

Сметанин Ю.Г., Ульянов М.В. Мера символьного разнообразия – характеристика временных рядов. // Materials of the III International Scientific Conference «Information-Management Systems and Technologies». Odessa.

Соколов О.М., Пионтковская Т.А. Система лингвистических конструктов, формирующих фреймы на глагольно-предикативной основе.

//Системные исследования. Ежегодник. — М.: Наука, 1991. с.124-141.

Солганик Г.Я. Стилистика текста. – М., 1997.

Солнцев В.М. Язык как системно-структурное образование. М.: Наука, 57.

Суркова А.С. Идентификация текстов на основе информационных портретов // Вестник Нижегородского университета им. Н.И. Лобачевского, 2014, № 3 (1), с. 145–149 Суркова А.С., Родионов В.Б. Алгоритм разбиения неструктурированного 59.

множества текстовых объектов // Научно-технический вестник Поволжья.– Казань, 2013г. — №5. – с.298-300 Турыгина Л.А. Моделирование языковых структур средствами вычислительной техники – М., 1988

Уфимцев Р. Тексты как фракталы. Режим доступа:

Хмелев Д.В. Классификация и разметка текстов с использованием методов сжатия данных. Краткое введение:

Хьетсо Г. и др. Кто написал «Тихий Дон»? (Проблема авторства «Тихого 63.

Дона») – М., 1989 Цыпкин Я.З. Основы теории обучающихся систем, М., Наука, 1970, 252 с.

Шевелёв О.Г. Методы автоматической классификации текстов на естественном языке: Учебное пособие. – Томск: ТМЛ-Пресс, 2007. 144 с.

Шеннон К. Э. Математическая теория связи // Работы по теории информации и кибернетике/ Пер. С. Карпова. – М.: ИИЛ, 1963. – 830 с.

Шрейдер Ю.А., Шаров А.А. Системы и модели – М.: Радио и связь, 1982.

Штовба С.Д. Введение в теорию нечетких множеств и нечеткую логику.

Шульгин В.И. Основы теории цифровой связи. Харьков, ХАИ, 2008, 184 с.

70. Advances in Fuzzy Clustering and its Applications. Editor(s): J. Valente de Oliveira, W. Pedrycz. John Wiley & Sons, Ltd. 2007. 434 р.

71. Alrabaee S., Saleem N., Preda S., Wang L., Debbabi M. OBA2: An Onion approach to Binary code Authorship Attribution // Digital Investigation, 2014, №11, P. S94–S103

72. Bennett C.H., Gacs P., Li M., Vitanyi P.M.B., Zurek W. Information Distance // IEEE Transactions on Information Theory, 44:4(1998), pp. 1407-1423

73. Berry M. W., Kogan J. Text Mining. Applications and Theory. – Wiley, 2010.

74. Bezdek J.C. [et al.]. Fuzzy models and algorithms for pattern recognition and image processing. Springer Science + Business Media, Inc. 2005. 776 р.

75. Bloom C. New techniques in context modeling and arithmetic encoding // IEEE DCC, Los Alamitos CA, March 1996, March, p. 426.

76. Bolshakov I.A., Gelbukh A. Computational linguistics: models, resources, applications, Mexico, 2004, 186 pp.

77. Bolshoy A., Volkovich Z., Kirzhner V., Barzily Z. Genome Clustering: From Linguistic Models to Classification of Genetic Texts. Springer, 2010. 206 p.

78. Brocardo M.L., Traore I., Saad S., Woungang I. Authorship Verification for Short Messages using Stylometry // Proceedings of the IEEE International Conference on Computer, Information and Telecommunication Systems (CITS 2013), 2013, pp. 1-6.

79. Cavnar W.B. N-Gram-Based Text Filtering For TREC-2 // Proceedings of the Second Text Retrieval Conference (TREC-2). – NIST, Gaithersburg, Maryland. – 1993, pp. 171-180

80. Cavnar W.B., Trenkle J.M. N-Gram-Based Text Categorization // Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval. – Las Vegas. – 1994. P. 161–175

81. Cavnar W.B., Vayda A.J. N-gram-based matching for multi-field database access in postal applications // Proceedings of the 1993 Symposium On Document Analysis and Information Retrieval. University of Neveda. – Las Vegas.

82. Chen Hs., Chau M. Web Mining: Machine learning for Web Applications // Annual Review of Information Science and Technology, 2004, vol. № 38, pp.289-329

83. Cilibrasi R., Vitanyi P.M.B. Clustering by compression // IEEE Trans. Inf.

Theory, 2005. Vol. 51, no. 4, 1523–1545.

84. Clarke B., Fokoue E., Zhang H.H. Principles and Theory for Data Mining and Machine Learning. Springer Science, LLC, 2009, 781 p.

85. Cooley R., Mobasher B., Srivastava J. Web mining: information and pattern discovery on the World Wide Web // Proceedings of the 9th ZEEE International Conference on Tools with Artificial Intelligence, 1997, 558-567.

86. D’Urso P. Fuzzy Clustering of Fuzzy Data // Advances in Fuzzy Clustering and its Applications (eds. J. V. de Oliveira, W. Pedrycz). 2007. — pp. 155-192

87. Doyle J., Keselj V. Automatic Categorization of Author Gender via N-Gram Analysis // Proceedings of The 6th Symposium on Natural Language Processing, SNLP’2005. http://web.cs.dal.ca/

88. Dua S., Du X. Data Mining and Machine Learning in Cybersecurity. New York, 2011. 224 p.

89. Etzioni O. The world-wide web: Quagmire or gold mine? // Communications of the ACM, 1996, № 39(11), p.65-68

90. Feldman R., Sanger J. The text mining handbook. Advanced Approaches in Analyzing Unstructured Data. – Cambridge University Press. 2007. 410 p.

91. Goldberg D.E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley. 1989

92. Granovetter M. The Strength of Weak Ties // American Journal of Sociology, 1973, Vol. 78, No. 6., pp 1360—1380

93. Gries S.Th., Newman J., Shaoul C. N-grams and the clustering of registers.

//Empirical Language Research Journal, 2011, №5.1.

94. Hathaway, R.J. and Bezdek, J.C. Switching regression models and fuzzy clustering // IEEE Transactions on Pattern Analysis and Machine Intelligence.

1993, 1 (3): pp.195–204.

95. Hoppner F., Klawonn F., Kruse R., Runkler Th. Fuzzy Cluster Analysis:

Methods for Classification, Data Analysis, and Image Recognition. New York, John Wiley & Sons, 1999.

96. Juola P. Authorship Attribution // Foundations and Trends in Information Retrieval. Vol. 1, No. 3 (2006) 233–334

97. Kimbrell R.E. Searching for Text? Send and N-gram! // Byte, May 1998. –

98. Klein D., Manning Ch.D. A generative constituent-context model for improved grammar induction. // Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, 2002, pp. 128-135.

99. Kontostathis A., Edwards L., Leatherman A. Text mining and cybercrime // Text Mining. Applications and Theory. Ed. by Berry M. W., Kogan J. – Wiley,

100. Kosala R., Blockeel H. Web Mining Research: A Survey. ACM SIGKDD,

2000. Vol. 2, Issue 1, pp.1-15

101. Krsul I, Spafford EH. Authorship analysis: identifying the author of a program// Proc. 8th National Information Systems Security Conference, 1995, P. 514–524.

102. Lance G.N., Williams W.T. A general theory of classificatory sorting strategies. // Computer J., 1967, V.9, №4, P. 373-380.

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

104. Li M., Chen X., Li X., Ma B., Vitanyi P.M.B. The similarity metric // IEEE Trans. Inform. Th., 50:12(2004), 3250- 3264

105. Lomakina L.S., Rodionov V.B., Surkova A.S. Hierarchical Clustering of Text Documents // Automation and Remote Control, 2014, Vol. 72, No. 9, pp. 345Manning Ch.D., Raghavan P., Schutze H. Introduction to Information Retrieval. Cambridge University Press. 2008. 504 с.

107. Manning Ch.D., Schutze H. Foundations of statistical natural language processing. MIT Press., Cambridge. 1999. 680 с.

108. Miyamoto S., Ichihashi H., Honda K. Algorithms for Fuzzy Clustering. Methods in c-Means Clustering with Applications. Springer-Verlag Berlin Heidelberg. 2008. 247 р.

109. O’Connor B., Bamman D., Smith N.A. Computational Text Analysis for Social Science: Model Assumptions and Complexity // Second Workshop on Computational Social Science and the Wisdom of Crowds (NIPS 2011).

110. Parpinelli, R.S., Lopes, H.S. and Freitas, A.A. An Ant Colony Algorithm for Classification Rule Discovery // Data Mining: a Heuristic Approach, Idea Group, 2002. pp. 191-208

111. Rendon E., Abundez I., Arizmendi A., Quiroz E. Internal versus External cluster validation indexes // International journal of computers and communications. 2011, Issue 1, Vol. 5. pp.27-34

112. Rijsbergen C. J. Information retrieval. 1979, 153 p.

113. Rissanen J.J., Langdon G.G. Universal modeling and coding // IEEE Trans.

Inf. Theory IT-27. 1981. №1, pp. 12-23.

114. Rosenblum N., Zhu X., Miller B.P. Who wrote this code? Identifying the authors of program binaries // Proceedings of the 16th European conference on

Режим доступа:

Research in computer security, 2011.

115. Salton G. Automatic text processing. Addison-Wesley Publishing Company.

116. Salton G., Wong A., Yang C.S. A vector space model for automatic indexing // Communications of The ACM — CACM, 1975, vol. 18, no. 11, pp. 613-620.

117. Sanderson, C., Guenter, S. Short text authorship attribution via sequence kernels, Markov chains and author unmasking: An investigation // Proceedings of the International Conference on Empirical Methods in Natural Language Engineering, 2006, pp. 482–491

118. Sato-Ilic M., Jain L.C. Innovations in Fuzzy Clustering. Theory and Applications. Springer, 2006. 152 р.

119. Schwartz R., Tsur O., Rappoport A., Koppel M. Authorship Attribution of Micro-Messages // Conference on Empirical Methods in Natural Language Processing (EMNLP), 2013, P. 1880-1891

120. Sebastiani F. Machine Learning in Automated Text Categorization // ACM Computing Serveys, 2002. Vol. 34. – №1. P. 1–47

121. Shannon, C.E.: A mathematical theory of communication. Bell System Technical J. 27, 379–423 (1948), русский перевод: Шеннон К. Э. Математическая теория связи // Работы по теории информации и кибернетике / Пер. С. Карпова. — М.: ИИЛ, 1963. — 830 с.

122. Stamatatos. E. A Survey of Modern Authorship Attribution Methods // Journal of the American Society for Information Science and Technology, 2009. № 60(3). P.538–556.

123. Stanko S., Lu D., Hsu I. Whose Book is it Anyway? Using Machine Learning to Identify the Author of Unknown Texts // Machine Learning Final Projects,

124. Surkova A.S., Domnin A.A., Bulatov I.V., Tsarev A.A. Neural networks and decision trees algorithms – the base of automated text classification and clustering // American Journal of Control Systems and Information Technology.

125. Vapnik V.N. Statistical Learning Theory. John Wiley & Sons, Ltd. 1998. 736 р.

126. Vinh N.X., Epps J., Bailey J. Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance // The Journal of Machine Learning Research. 2010, Vol. 11, pp. 2837-2854

127. Xie X L, Beni G. A validity validity measure for fuzzy clustering // IEEE Trans. PAMI, 1991, vol. 13(8), pp. 841-847.

128. Yang Y. An evaluation of statistical approaches to text categorization. // Journal of Information Retrieval, 1999, №1. P. 67-88.

129. Zadeh L.A. Similarity relations and fuzzy orderings // Information Sciences, 1971, vol. 3, no. 2, pp. 177-200.

130. Ziv J., Lempel A. A Universal Algorithm for Sequential Data Compression // IEEE Transactions on Information Theory, 1977, 23(3), pp. 337–343

131. Ziv J., Lempel A. Compression of Individual Sequences via Variable-Rate Coding // IEEE Transactions on Information Theory. 1978, 24 (5), 530–536.

«Значение В.Г. Шевченко для развития физики высоких энергий в Московском университете В 1967 г. в Институте физики высоких энергий в Протвино был запущен ускоритель У-70 на энергию протонов 70 ГэВ, который в течение пяти лет был крупнейшим в мире. У советских физиков появилась современная база для исследований по физике высоких энергий. На это откликнулся и Московский университет. Лаборатория высоких энергий была создана в НИИЯФ МГУ в конце 1968 г. с целью развития в Московском университете. »

«А. В. ХАЛАПСИС ПОСТНЕКЛАССИЧЕСКАЯ МЕТАФИЗИКА ИСТОРИИ МОНОГРАФИЯ Днепропетровск «Инновация» УДК 130.3 ББК 87.6 + 87.21 Х 17 Рекомендована к печати Ученым советом Днепропетровского национального университета (протокол № 10 от 29 мая 2008 г.) Рецензенты: доктор философских наук Окороков В. Б. доктор философских наук Шабанова Ю. А. Халапсис А. В. Х 17 Постнеклассическая метафизика истории: Монография. – Днепропетровск: Изд-во «Инновация», 2008. – 278 с. ISBN 978–966–8676–31–4 В монографии. »

«Разбиения поверхностей на многоугольники и задачи, пришедшие из физики, химии и биологии В. М. Бухштабер МИАН имени В. А. Стеклова, МГУ имени М. В. Ломоносова, ИППИ имени А. А. Харкевича XV Летняя школа Современная математика Ратмино, 23 июля 2015 г. Лекция 1 1/43 В. М. Бухштабер Разбиения поверхностей на многоугольники. Регулярные разбиения Разбиение поверхности на многоугольники называется регулярным, если в каждой вершине сходится только три ребра, а два многоугольника пересекаются только по. »

«Интернет-журнал «НАУКОВЕДЕНИЕ» Институт Государственного управления, права и инновационных технологий (ИГУПИТ) Выпуск 2, март – апрель 2014 Опубликовать статью в журнале http://publ.naukovedenie.ru Связаться с редакцией: publishing@naukovedenie.ru УДК 330.43: 343.9.01 Кучерова Светлана Викторовна ФГБОУ ВПО Владивостокский государственный университет экономики и сервиса Россия, Владивосток1 Доцент кафедры математики и моделирования Кандидат физико-математических наук E-Mail. »

«Ученые записки Таврического национального университета имени В.И. Вернадского Серия «Физико-математические науки». Том 25 (64). 2012 г. № 1. С. 231-238 УДК 378.12 (092)(035) ВЕЛИКОЛЕПНЫЙ ОРГАНИЗАТОР И ВОСПИТАТЕЛЬ ( К 100-летию со дня рождения Рубена Григорьевича Бадальяна ) (1912-1982) Шостка В.И. Таврический национальный университет имени В.И. Вернадского, Симферополь, Украина E-mail: vshostka@yandex.ru В статье рассказывается о первом декане физического факультета Таврического национального. »

«АНАЛИЗ СТРУКТУРЫ ЗАНЯТОСТИ НАСЕЛЕНИЯ Низамиев Абдурашит Гумарович д-р геогр. наук, проф., РГСУ, филиал в городе Ош, Кыргызская Республика, г. Ош Кенешбаева Зуура Маматовна канд. экон. наук, РГСУ, филиал в городе Ош, Кыргызская Республика, г. Ош E-mail: kenzuura@rambler.ru Максутов Айдарбек Рысбаевич канд. физико-матем. наук, РГСУ, филиал в городе Ош, Кыргызская Республика, г. Ош E-mail: maks0505@mail.ru Алайчиев Эрнисбек Каныбекович канд. геогр. наук, доцент, РГСУ, филиал в городе Ош. »

«Российская Академия Естествознания Издательский дом Академии Естествознания ПРИМЕНЕНИЕ ИННОВАЦИЙ ПРИ РАЗРАБОТКЕ РАДИОТЕХНИЧЕСКИХ СИСТЕМ Коллективная монография Под общей редакцией доктора физико-математических наук, доцента М.Ю. Звездиной Рекомендовано УМО РАЕ по классическому университетскому и техническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлениям: 11.03.01 – «Радиотехника»; 11.03.02 – «Инфокоммуникационные технологии и системы. »

«1. Цели освоения дисциплины Целью освоения дисциплины «Агрочвоведение» является формирование у аспирантов навыков оценки экологического состояния конкретной территории и использования его результатов в формировании экологически безопасных агроландшафтов на различных территориях.2. Место дисциплины в структуре ООП ВПО Дисциплина «Агропочвоведение» относится к дисциплинам по выбору вариативной части ОПОП ВО. Дисциплина базируется на знаниях, имеющихся у аспирантов при получении высшего. »

«Минобрнауки России ФБФГБОУ ВПО “Уральский государственный горный университет” Положение о структурном подразделении 4.2.3. Управление документацией СМКПСП 304.14 Положение о Бизнес-школе Бизнес-центре Екатеринбург 1. Общие положения 1.1. Положение о Бизнес-школе Бизнес-центре факультета геологии и геофизики ФГБОУ ВПО «Уральский государственный горный университет» определяет основные задачи, функции (права, обязанности), связанные с удовлетворением потребностей граждан в образовательных услугах. »

«Секция 2. Ограждающие конструкции зданий, энергои ресурсосбережение УДК. 728.3: 699.86 ТЕПЛОТЕХНИЧЕСКИЕ ОСОБЕННОСТИ НАРУЖНЫХ СТЕН МАЛОЭТАЖНЫХ ЗДАНИЙ Стерлягов А.Н., Низовцев М.И. Институт теплофизики СО РАН, г. Новосибирск С 20 мая 2011 г. постановлением Госстроя России приняты и введены в действие СП 55.13330.2011 «Дома жилые одноквартирные. Актуализированная редакция СНиП 31-02-2001» [1]. Настоящие нормы разработаны в связи с возрастающим объмом строительства и развитием рынка одноквартирных. »

«История и достижения кафедры физики СВЧ (А. А. Звягинцев) Начало XX века ознаменовалось появлением нового научного направления в физике – радиофизики. Ее бурное развитие началось с решения важных прикладных задач – задач радиолокации. Возникла и необходимость создания центра по подготовке высококвалифицированных специалистов в этой области. И не случайно выбор пал на Харьковский государственный университет им. А. М. Горького, имевший богатые традиции в области физики. Основателем харьковской. »

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

«1 БЮЛЛЕТЕНЬ НОВЫХ ПОСТУПЛЕНИЙ 1-15 АПРЕЛЯ 2015г. В настоящий «Бюллетень» включены книги, поступившие в отделы Фундаментальной библиотеки с 1 по 15 апреля 2015 г. Бюллетень составлен на основе записей Электронного каталога. Материал расположен в систематическом порядке по отраслям знания, внутри разделов – в алфавите авторов и заглавий. Записи включают полное библиографическое описание изданий, шифр книги и место хранения издания в сокращенном виде (список сокращений приводится в Бюллетене). »

«ПОТЕНЦИАЛ СОВРЕМЕННОЙ НАУКИ, №8, НОЯБРЬ, 2015 ISSN 2312-1939 щим. Эти условия выполнены в H3S, и именно это соединение развивается из H2S при высоком давлении. Ученые в настоящее время ищут материалы с еще более высокими переходными температурами. Повышение давления, действующее на сероводород, выше 1,5 мегабара в этом случае не полезно. Это было рассчитано не только физиками теоретиками, но теперь также подтверждается в экспериментах, выполненных на практике. При еще более высоких. »

«КРАТКИЕ СООБЩЕНИЯ Самарская Лука: проблемы региональной и глобальной экологии. 2010. – Т. 19, № 2. – С. 151-156. УДК 01+09.2 В.И. ПРОКАЕВ В КУЙБЫШЕВЕ И КУЙБЫШЕВСКОЙ ОБЛАСТИ © 2010 А.А. Головлёв* Самарский государственный экономический университет, г. Самара (Россия) Поступила 10 ноября 2009 г. Рассматривается куйбышевский период биографии В.И. Прокаева Ключевые слова: В.И. Прокаев, биография, Куйбышевский плановый институт. Golovlyov A.A. V.I. PROKAEV IN THE KUIBYSHEV AND KUIBYSHEV REGION The. »

2020 www.os.x-pdf.ru — «Бесплатная электронная библиотека — Научные публикации»

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

Илон Маск рекомендует:  Основы программирования на PHP
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL