Средства и технологии обработки текстовой информации

Размещено на http://www.allbest.ru/

ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ

КАФЕДРА АВТОМАТИЗИРОВАННОЙ ОБРАБОТКИ

ЭКОНОМИЧЕСКОЙ ИНФОРМАЦИИ

КУРСОВАЯ РАБОТА

По дисциплине «Информатика»

На тему: «Средства и технологии обработки текстовой информации»

Краснодар - 2006г.

СОДЕРЖАНИЕ

Введение

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

ВВЕДЕНИЕ

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

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

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

ПРИЛОЖЕНИЕ 1

Методы сжатия данных

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

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

Заключение

Введение

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ

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

Говоря точнее, АК производят автоматически лишь обнаружение ошибок, а собственно коррекция ведется обычно при участии человека.

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

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

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

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

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

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

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

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

Можно предложить три степени автоматизации процесса коррекции текста:

1) только обнаружение ошибок,

2) обнаружение их и выдвижение гипотез (альтернатив, кандидатов) по исправлению;

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

Без первой степени АК немыслим.

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

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

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

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

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

I) Текст имеет вид перечня терминов и терминологических словосочетаний в стандартной их форме, так что в АК достаточно иметь словарь, замкнутый по объему и проблематике. При этом все термины между собой "непохожи" (например, в словаре нет одновременно АДСОРБЦИЯ и АБСОРБЦИЯ).

2) Ошибки носят характер замены кодов исходных букв на коды литер, совпадающих или близких к исходным по начертанию. Например, заменяются коды ASCII русских букв А, В, С, Е, У на коды латинских букв А, В, С, Е, У; латинские буквы I и 0 - на цифры I и 0 и т.п. Сюда же отнесем повторы одной и той же литеры, возникающие из-за продленного нажима клавиши дисплея или его неисправности. В подавляющем большинстве, если в словоформе более 2 -3 букв, такие исправления абсолютно правильны.

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

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

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

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

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

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

ВВЕДЕНИЕ

Объектами сжатия являются:

- числовые данные,

- упорядоченные текстовые данные (словари),

- специальные тексты на формализованных языках,

- естественно-языковые тексты общего вида,

- структурированные данные.

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

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

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

Наиболее распространены методы: разностное кодирование, кодирование повторений и подавление незначащих нулей.

Суть разностного кодирования заключается в хранении вместо абсолютных значений разностей двух смежных чисел или отклонения чисел от их среднего значения. Например, для последовательности чисел 2, 7, 14, 18, 27, 34, первый способ даст последовательность 2, 12, 4, 9, 7. Второй способ порождает последовательность -17, -5, -1, 8, 15 (среднее значение для исходной последовательности -19).

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

Кодирование повторений заключается в замене цепочки одинаковых символов кодом этого числа и числом повторений. Например, для последовательности 5555 6666 888888 применение этого способа даст последовательность 5(4) 6(4) 8(6).

Подавление незначащих нулей означает отбрасывание незначащих нулей в старших разрядах целой части числа и в младших разрядах дробной части. Например, применение этого способа сжатия к последовательности 0010 01,100 011 даст последовательность: 10 1,1 1111.

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

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

вычислитель

вычислительный

вычислять

в результате рассматриваемого способа кодирования будет заменен словарем:

вычислитель

11ный

6ять.

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

встречающийся

заменяющий

с помощью этого способа сжатия заменится на совокупность словарей:

основной вспомогательный

встреча1ся 1- ющий

заменя1

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

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

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

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

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

ТYРЕ *,'ФОРТРАН'

ТYРЕ *,'ПРОГРАММА'

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

программа словарь

1,'ФОРТРАН' 1 - ТУРЕ *

1,'ПРОГРАММА'

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

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

Разнородность данных структурированного типа обуславливает различные типы информационной избыточности, поэтому необходимо использовать комбинацию методов, приспособленных к своим подгруппам данных. Так, для числовых полей целесообразно применять методы п. 1.1, для текстовых - описанные в п. 1.5. По некоторым оценкам комбинация этих методов дает сокращение объема данных в 1,5-4 раза, по другим оценкам - даже до 6 раз.

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

Ф.И.О. студента

отношение к воинской обязанности

домашний адрес

специальность

оценки за сессию,

причем поля имеют длину, соответственно, 40, 20, 50, 15, 10 байт, то при различных значениях тех или иных полей для конкретных студентов часть области памяти, отводимой под отдельные поля, не будет использоваться. Тогда, если поле «Отношение к воинской обязанности» пусто, его можно исключить из конкретной записи и вся запись будет иметь следующий вид:

(Ф.И.О. студента)1(домашний адрес), 3(специальность) 4(оценки за сессию), где индексы означают принадлежность того или иного значения соответствующему полю.

сжатие информация текстовый кодирование фрагмент

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

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

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

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

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

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

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

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

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

Строят код постоянной длины для фрагментов переменной длины.

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

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

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

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

Коэффициент сжатия текстовых данных этим методом лежит в пределах 1,8 - 2,5.

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

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

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

пробел 0,174 ы 0,016

о 0,080 з 0,016

е, ё 0,071 ъ 0,014

а 0,061 ь 0,014

и 0,061 б 0,014

т 0,052 г 0,013

м 0,052 ч 0,012

с 0,045 й 0,010

р 0,040 у 0,009

в 0,038 ж 0,007

л 0,035 ю 0,006

к 0,028 ш 0,006

н 0,026 ц 0,003

д 0,025 щ 0,003

п 0,023 э 0,003

у 0,021 ф 0,002

я 0,018 х 0,002

Сами коды рассчитываются на основании частот отдельных символов (в случае таблицы символов) или их комбинаций (в этом случае общая частота рассчитывается как произведение частот отдельных символов, входящих в комбинацию) с помощью методов Шеннона-Фано или Хаффмена (описание методов см. в приложении 1).

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

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

Дальнейшим развитием метода Хаффмена являются арифметические коды. Они происходят из так называемых блочных, кодов. Суть их заключается в том, что выходной код генерируется для цепочки входных символов фиксированной длины без учета межсимвольных корреляций. В основе метода лежит представление вероятности каждой цепочки К входных символов (А1, А2, ... АК ) в виде числа, получаемого как сумма К слагаемых вида

p(А1)p(А2)..р(АI-1)P(АI), I=1, 2, 3, …… K

где р (S) - вероятность символа S,

Р(S)- кумулятивная вероятность символа S, равная сумме вероятностей всех символов AI, для которых р(АI) больше р(S).

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

Другой формой словаря может являться словарь фрагментов переменной длины. Словари фрагментов переменной длины строятся из словоформ, которые выделяются в тексте по естественным разделителям - пробелам и знакам пунктуации. Затем рассчитываются частоты каждой словоформы как отношение числа ее повторений к общему количеству словоформ. Используя эти частоты, применяют метод Хаффмена или Шеннона-Фано для кодирования словоформ кодом переменной длины.

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

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

ПРИЛОЖЕНИЕ 1

Методы сжатия данных

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

Знаки упорядочиваются по возрастанию их частот и образуют частичные суммы Si = (pj (j = 1, 2, 3, ….. i), где рj - частота j-того знака. Далее процесс разбивается на несколько шагов. В первом шаге столбец знаков рассекается на две части так, чтобы частичная сумма сечения была близка к 0,5. Процесс деления подстолбцов повторяется так, чтобы каждый раз частичная сумма в точке сечения оказывалась ближе к среднему арифметическому частичных сумм на нижнем и верхнем краях разделяемого подстолбца. При каждом разбиении элементам верхней части ставится в соответствие 1, нижней - 0. Например: пусть знаки рi

A 0,11

B 0,15

C 0,20

D 0,24

E 0,30

Тогда процедура разбиения складывается из шагов:

Знаки pi коды

A 0,11 1 1 111

B 0,15 1 0 110

C 0,20 0 10

D 0,24 0 1 01

E 0,30 0 00

шаг1 шаг2 шагЗ

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

Знаки упорядочиваются по возрастанию частоты. Два самых редких знака объединяются в один класс, и их частоты складываются. Полученные частоты переупорядочиваются и процесс повторяется до тех пор, пока все знаки ни будут объединены в один класс. Например,

Знаки pi Знаки pi

A 0,11 (0) C 0,20 (0)

B 0,15 (1) D 0,24 (1)

C 0,20 F 0,26

D 0,24 E 0,30

E 0,30

Знаки pi Знаки pi

F 0,26 (0) G 0,44 (0)

E 0,30 (1) H 0,56 (1)

G 0,44

Тогда коды исходных символов (они «собираются» из частных кодов дополнительных обозначений - F, G, H- в обратном относительно хода кодировки порядке):

Исходные Коды Пояснения символы

A 100 (А вошел в F с кодом 0; F вошел в H с кодом 0; у H

код 1. Тогда обратный порядок - 100)

B 101 (B вошел в F с кодом 1; F вошел в H с кодом 0; у H

код 1. Тогда обратный порядок - 101)

С 00 (С вошел в G с кодом 0; у G код 0)

D 01 (D вошел в G с кодом 1; у G код 0. Тогда

обратный порядок - 01)

E 11 (E вошел в H с кодом 1, у H код 1)

Заключение

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

Размещено на Allbest.ru