Основные способы обработки большого количества текстовой информации (стр. 5 из 6)
По использованию статистики и грамматики алгоритмы сжатия можно разделить на семантически зависимые и семантически независимые. Первые (лингвистические) методы опираются на грамматику естественного языка для выделения в текстах элементов, подлежащих кодированию (как правило, это отдельные слова – словоформы).
Семантически независимые методы сжатия в свою очередь можно разделить на те, которые не используют, и те, которые используют априорные сведения о статистике текста. В соответствии с этим существуют два типа алгоритмов сжатия: одно - и двухфазные, которые будем называть соответственно адаптивными и статистическими.
Семантически зависимые методы не используют для сжатия никаких априорных сведений о статистике текста. Кодирование производится в процессе однократного сканирования текста. Оно сводится к замене цепочек символов текста на встроенные указатели, адресованные к той части текста, где такие цепочки уже встречались. В этом случае говорят о внутренней адресации, а сами методы называются адаптивными.
В алгоритмах второго типа выполняется ссылка на таблицу кодов, которая может создаваться заново для каждого текста или использоваться одна на все гипотетические тексты. В этом случае говорят о внешней адресации и локальных или глобальных кодовых таблицах.
Строят код постоянной длины для фрагментов переменной длины.
Сжимают текст в процессе однократного его сканирования. Кодирование заключается в нахождении повторяющихся участков текста и замене каждого участка указателем, адресованным к той части текста, где такой участок уже встречался. Для декодирования в этом случае кодовой таблицы не требуется. В качестве указателя может использоваться структура (m, n), где m – количество символов назад или вперед по тексту, переместившись на которые можно найти подобный фрагмент текста; n – длина фрагмента в символах.
Существует два типа встроенных указателей, указывающих на предшествующие или последующие участки. Алгоритмы, использующие указатели назад, могут работать с непрерывным входным потоком данных, генерируя непрерывный выходной поток сжатой информации. На каждом шаге алгоритма входной текст заполняет буфер фиксированной длины, внутри которого производится идентификация одинаковых подстрок максимально возможной длины. При нахождении двух таких подстрок вторая заменяется указателем, адресованным в начало первой.
Алгоритмы с указателями вперед могут работать лишь с текстами конечной длины, поскольку требуют обратного сканирования текста. Здесь также используется поиск совпадающих подстрок в буфере переменной длины с уже закодированным текстом.
Одной из характерных черт адаптивных алгоритмов является достаточная их универсальность, т.е. возможность работать с любыми, не только текстовыми данными, ненужность начальной информации о характере данных и их статистике. Эта черта снижает эффективность сжатия и достигаемое сжатие, как правило, меньше полученного другими методами. Но часто адаптивные алгоритмы просты и все же приемлемы по эффективности.
Коэффициент сжатия текстовых данных этим методом лежит в пределах 1,8 - 2,5.
1.5.2. Статистические алгоритмы.
1.5.2.1. Кодирование фрагментов фиксированной длины
Простейшей формой словаря в этом случае является кодовая таблица символов алфавита, ставящая в соответствие каждому символу свой код. Коды выбираются с таким расчетом, чтобы общая длина закодированного ими текста была минимальной. Такую же таблицу можно составить для всех или наиболее часто встречающихся комбинаций из двух, трех и т.д. букв, т.е. фрагментов с фиксированным числом символов. Ниже приведены частоты букв в русском языке:
пробел 0,174 ы 0,016
о 0,080 з 0,016
а 0,061 ь 0,014
и 0,061 б 0,014
с 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,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. Кодирование фрагментов переменной длины
Другой формой словаря может являться словарь фрагментов переменной длины. Словари фрагментов переменной длины строятся из словоформ, которые выделяются в тексте по естественным разделителям – пробелам и знакам пунктуации. Затем рассчитываются частоты каждой словоформы как отношение числа ее повторений к общему количеству словоформ. Используя эти частоты, применяют метод Хаффмена или Шеннона-Фано для кодирования словоформ кодом переменной длины.
В процессе ускоренной компьютеризации общества объемы данных, хранимых на машинных носителях, быстро растут. Ещё совсем недавно они измерялись килобайтами и мегабайтами, а теперь - гигабайтами и более крупными единицами. Естественно желание хранить эти данные предельно компактно. Причем интересны обратимые методы, устраняющие избыточность информации при сжатии и восстанавливающие её при разжатии. Описанные в реферате методы обратимы.
ПРИЛОЖЕНИЕ 1. Методы сжатия данных
Знаки упорядочиваются по возрастанию их частот и образуют частичные суммы Si = Spj (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 110C 0,20 0 10
D 0,24 0 1 01E 0,30 0 00