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

Текст из файла (страница 3)

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

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

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

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

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

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

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

Суть разностного кодирования заключается в хранении вмес­то абсолютных значений разностей двух смежных чисел или отк­лонения чисел от их среднего значения. Например, для последо­вательности чисел 2, 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 011 даст после­довательность: 10 1,1 11 11.

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.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

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

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