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

Текст из файла

20

Санкт-Петербургский

Государственный морской технический университет

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

Кафедра САУ и БВТ

РЕФЕРАТ

ПО ДИСЦИПЛИНЕ

“ИНФОРМАТИКА”

НА ТЕМУ:

“Основные способы обработки большого количества текстовой информации”.

Выполнил: студентка гр. 31ВМ1 (3111)

Жаркова А.Н.________

Проверил: Д.Т.Н., профессор

Жуков Ю.И.________

Санкт - Петербург

2000 г.

АННОТАЦИЯ

Реферат составлен на страницах. Содержит 2 рисунка, 3 таблицы и 2 приложения.

Ключевые слова: адресация, автокоррекция, сжатие.

Целью реферата является разработка и описание трех практических задач современной информатики:

• адресации элементов баз данных, множества или списка, для определения по первичному ключу местоположения элемента в блоке информации;

• автокоррекции языковых текстов для обнаружения и исправления ошибок в текстах;

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

СОДЕРЖАНИЕ

АННОТАЦИЯ 2

СОДЕРЖАНИЕ 3

Введение 4

ЧАСТЬ 1. МЕТОДЫ АДРЕСАЦИИ 5

ВВЕДЕНИЕ 5

1. Теоретическая часть 5

1.1. Последовательное сканирование списка 5

1. 2. Блочный поиск 5

1.3. Двоичный поиск 5

1.4. Индексно-последовательная организация 6

1.5. Индексно-произвольная организация 6

1.6. Адресация с помощью ключа, эквивалентного адресу 7

1.7. Алгоритм преобразования ключа в адрес 8

Выводы по части 1. 10

ЧАСТЬ 2. АВТОКОРРЕКЦИЯ ТЕКСТА 11

ВВЕДЕНИЕ 11

1. Теоретическая часть 11

1.1. Методы обнаружения ошибок 11

1.2. Автоматизация процесса исправления 11

1.3. Диалоговый и пакетный режимы 12

Выводы по части 2. 13

ЧАСТЬ 3. СЖАТИЕ ИНФОРМАЦИИ 13

ВВЕДЕНИЕ 13

1. Теоретическая часть 13

1.1. Сжатие числовых данных 13

1.2. Сжатие словарей 13

1.3. Сжатие специальных текстов 14

1.4. Сжатие структурированных данных 15

1.5. Сжатие текстовой информации общего вида 15

1.5.1. Адаптивные алгоритмы 16

1.5.2. Статистические алгоритмы. 16

1.5.2.1. Кодирование фрагментов фиксированной длины 16

1.5.2.2. Кодирование фрагментов переменной длины 17

Выводы по части 3. 17

ПРИЛОЖЕНИЕ 1. Методы сжатия данных 18

Метод Шеннона-Фано 18

Метод Хаффмена 18

Заключение. 20

Список литературы 20

Введение

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

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

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

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

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

Задачи программируются на языке программирования, который изучается в курсе «Алгоритмические языки и программирование», и, тем самым, закрепляют навыки, полученные в этой дисциплине. Кроме этого, требование подготовки блок-схем средствами WinWord позволяет углубить знания, связанные, с одной стороны, с логическим проектированием алгоритма, а с другой – с правилами начертания блок-схем.

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

ЧАСТЬ 1. МЕТОДЫ АДРЕСАЦИИ

ВВЕДЕНИЕ

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

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

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

1. Теоретическая часть

1.1. Последовательное сканирование списка

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

1. 2. Блочный поиск

Е сли элементы упорядочены по ключу, то при сканировании списка не требуется чтение каждого элемента. Компьютер мог бы, напри­мер, просматривать каждый n-ный элемент в последовательности возрастания ключей. При нахождении элемента с ключом, большим, чем ключ, используемый при поиске, просматриваются последние n-1 элементов, которые были пропущены. Этот способ называется блочным поиском: элементы группируются в блоки, и каждый блок проверяется по одному разу до тех пор, пока ни будет найден нужный блок. Вычисление оптимального для блочного поиска раз­мера блока выполняется следующим образом: в списке, со­держащем N элементов, число просмотренных элементов минимально при длине блока, равной N. При этом в среднем анализируется N элементов.

1.3. Двоичный поиск

При двоичном поиске рассматривается элемент, находящийся в середине области, в которой выполняется поиск, и его ключ срав­нивается с поисковым ключом. Затем поисковая область делится пополам, и процесс повторяется. При этом, если N велико, то в среднем будет просмотрено примерно log₂N-1 элементов. Это число меньше, чем число просмотров для случая блочного поиска.

1.4. Индексно-последовательная организация

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

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

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

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

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

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

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

Индексно-последовательные файлы представляют собой наибо­лее распространенную форму адресации файлов.

1.5. Индексно-произвольная организация

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

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

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

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

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

1.6. Адресация с помощью ключа, эквивалентного адресу

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

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

Список файлов реферата