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

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

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