Оценка параметров модели контекстного предсказания при восстановлении сжатых текстовых сообщений

Тип работы:
Реферат
Предмет:
Общие и комплексные проблемы естественных и точных наук


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА_Сер. 9. 2007. Вып. 3. Ч. II
Я. В. Шишкин
ОЦЕНКА ПАРАМЕТРОВ МОДЕЛИ КОНТЕКСТНОГО ПРЕДСКАЗАНИЯ ПРИ ВОССТАНОВЛЕНИИ СЖАТЫХ ТЕКСТОВЫХ СООБЩЕНИЙ
В настоящее время в различных областях деятельности человека пристальное внимание уделяется вопросам обработки больших массивов текстовых сообщений. Это объясняется постоянно возрастающими потребностями людей в обмене различного рода сведениями, текстовое представление которых получило широкое распространение в системах цифровой связи и персональных системах обработки и хранения информации, а также многообразием технических средств их формирования (персональные компьютеры, мобильные телефоны). Процессы обмена текстовыми сообщениями с использованием представленных средств отличаются активностью, что вызывает необходимость формирования специфических моделей текстовых сообщений для решения различных задач их последующей автоматизированной обработки на ПЭВМ (обнаружение текстов, распознавание применяемых кодов и языка, идентификация автора, реферирование, восстановление, хранение). Актуальность этих задач также связана с возможностью повсеместного доступа к ресурсам глобальной сети Интернет в процессе поиска и отбора интересующих сведений.
При решении представленных задач рассмотрим множество дискретных знаков (букв, знаков препинания и т. д.) я. е конечного алфавита объема Ы, формируемых источником Бщ. Для передачи совокупностей этих знаков в виде текстовых сообщений посредством телекоммуникационных сетевых технологий применяются специальные способы сжатия сообщений на основе префиксных кодов (ПК)1. Связи этих знаков с другими знаками или их сочетаниями характеризуются условными вероятностями их появления в определенных контекстах длины X. Оценки вероятностей будем
интерпретировать нормированными частотными характеристиками со (V) появления знаков при условии некоторого контекста к^ длины X, причем, г = 1(1) ТУ& quot-, У = 1(1)"/ (J — общее число возможных контекстов).
В основу процесса формирования модели текстовых сообщений в рамках решения рассмотренных выше задач положим контекстное разложение, выражение для реализации которого можно представить следующим образом:
где нормированные частотные характеристики 0) Гу. |к.) отождествляются с коэффициентами разложения на длине Ц исследуемого сообщения (л,)^.
Для оценки рассмотренных параметров воспользуемся моделью контекстного предсказания, в которой обработанные знаки сообщения /ц предназначены для
© Н. В. Шишкин, 2007
предсказания очередного входного символа е и оценивания коэффициентов контекстного разложения2. Основу модели составляет статистический способ переоценки распределения вероятностей символов источника при условии ограниченного контекста к^, ] = порядка X, причем, значение X является переменной величиной. Оценивание вероятностных характеристик для предсказания очередного входного символа е при различных значениях % будем осуществлять путем совместного использования моделей различных порядков. Максимальная длина контекста Ятах является величиной постоянной, значение которой определяется на основе сравнения производительностей моделей контекстного предсказания, оперирующих контекстами различной максимальной длины А, таг[. В качестве исходных данных в предложенной процедуре оценивания
используются контекстно-ограниченные модели порядка = Ятах (-1)0, а для каждой
модели-все обнаруженные ранее контексты у = 1(1)/ аналогичного порядка
и частота их появлений в обработанном тексте.
На шаге анализа для символа ^,? = 1 (1)|0. осуществляем последовательный поиск предшествующего ему контекста к^ в контекстной базе модели порядка начиная с Х1 = А. тах. Отсутствие контекста к^ в контекстной базе применяемой модели является признаком необходимости снижения порядка Х (применяемой модели.
При обнаружении совпадения анализируемого контекста у = 1(1)/ с од-
ним из существующих в контекстной базе применяемой в конкретный момент времени модели принимаем решение относительно порядка модели, выбранной для предсказания
символа и оценивания условной вероятности ш ^) его появления. На основе этих данных пересчитываем значения вероятностей (о) для каждого символа ,
/ = 1 (1) Аг, появившегося в рассматриваемом контексте к^. Таким образом, в процессе моделирования и оценивания происходит адаптация вероятностей со (5. ^ к сообщению {й,) по мере поступления очередных входных символов.
Рассмотрим зависимость порядка модели контекстного предсказания (длины используемого контекста к^) от значения / = 1 (1)ц для текстовых сообщений на английском языке при различных исходных данных.
Оценивание параметров контекстного разложения при корректном выборе префиксного кода
На рисунке 1 приведен пример распределения длины Х1 используемых для предсказания контекстов 7 = 1(1)7 на каждом шаге анализа? = 1(1)|и для сформированного в результате декодирования ПК текстового сообщения (д,.)^ на английском языке в случае совпадения параметров выбранного для декодирования и применяемого для передачи ПК.
текстового формата данных на английском языке
На представленном рисунке различимы участки, соответствующие двум этапам работы процедуры предсказания и оценивания:
1 & lt- / & lt-? — этап, соответствующий переходному режиму функционирования (первичное заполнение контекстных баз для моделей различных порядков X) —
t & lt- г & lt- оо — этап, соответствующий установившемуся режиму функционирования (предсказание и незначительное пополнение контекстных баз).
Значения порядков А,(моделей, используемых для предсказания в переходном режиме, представляют собой малые величины. Для установившегося режима характерно окончание предварительного формирования контекстных баз, в силу чего в этом режиме значения порядков Х1 моделей, используемых для предсказания, возрастают. Следует отметить, что значение зависит от вероятностных свойств источника.
Оценка математического ожидания М (Х1) порядка Х1 модели, используемой для предсказания символов в текстовом сообщении, осуществляется на основе следующего выражения:
(2)
я,=о
Тогда зависимость математического ожидания порядка модели исполь-
зуемой для предсказания, от постоянно возрастающей величины t в установившемся режиме функционирования можно представить неубывающей функцией, не содержащей локальных максимумов. Максимальным значением М{Х () является.
Оценивание параметров контекстного предсказания при некорректном выборе префиксного кода
Рассмотрим ситуацию, когда параметры исходного и выбранного префиксных кодов отличаются. Тогда восстановленное сообщение). представляет собой набор символов случайного характера, в силу чего общее число разрешенных контекстных составляющих возрастает (у =, X = 0(1)& gt-^тах)• Это приводит к увеличению длительности переходного режима. Следует отметить, что возрастание значения математического ожидания М (Х () порядка Х1 модели предсказания для случайного набора символов английского алфавита осуществляется медленнее, чем для сообщений текстового формата данных на английском языке.
Пример зависимости значений М (Л () для сообщений текстового формата данных на английском языке и случайного набора букв английского алфавита представлен на рисунке 2.
М (1)
4,5 '- Тркгтпяпр:: (- ----
4 '- сообщение — ----Г
3,5 '-
3 '- / ! 1
2,5 7 [ 1
2 & quot- 1 |
1,5 Случайней набор — буйв:
1 '-

0,5 '-
0 5000 10 000 15 000 I
Рис. 2. Пример зависимостей М (Х!) для сообщений текстового формата данных на английском языке и случайного набора букв
Оценивание параметров контекстного предсказания при наличии искажений в текстовом сообщении
Рассмотрим ситуацию появления искажений в сообщении текстового фор мата данных в процессе декодирования ПК. Вследствие этого исходное сообщение (я. ^ и сообщение (д./ ., формируемое на приемной стороне, отличаются.
Пусть на выходе декодера ПК формируется сообщение (з-)^ текстового формата данных, в котором в момент t^ появляется искажение ограниченной длины 1. 15к.
Тогда в момент значение математического ожидания) длины контекста к^ изменяется в сторону уменьшения.
Для получения количественной оценки математического ожидания длины контекста к^ будем использовать выражение (2), где элементы распределения вероятностей 1 ^
ш (Л,) = / -гу находятся в обратной функциональной зависимости от размерности
контекстных баз.
В результате взаимодействия случайных символов 5., / = 1 (1)^ на интервале формируются межсимвольные связи случайного вида, что проявляется в появлении
дополнительных контекстных составляющих у = 1(1),/ и приводит к значительному
увеличению размерности контекстных баз (/((. уД.) «J ((s. s}])).
По этой причине в момент появления отличий между сообщениями ($,¦) и. значения как условных, так и безусловных вероятностей появления контекстных составляющих к^ различных длин Х1 уменьшаются, в силу чего (X,) при
Пример зависимости значений М (X,) для искаженного сообщения текстового формата
данных представлен на рисунке 3. В момент ^ появления искажения наблюдается локальный максимум функции М (Л ().
Рис. 3. Пример зависимостей значений М (Яг) для искаженного сообщения текстового формата данных
В силу рассмотренных обстоятельств математическое ожидание М (А,) длины
контекста к^ может быть использовано для обнаружения искажений в текстовых сообщениях при декодировании ПК источника.
В заключение следует отметить, что в силу сложного характера взаимосвязей отдельных элементов текстовых сообщений создать универсальную модель, учитывающую специфику любого сообщения и пригодную для решения всех возникающих задач,
не представляется возможным. Поэтому в рамках каждой конкретной задачи разрабатываются частные модели, детально отражающие те или иные особенности, характеристики и параметры конкретных ситуаций.
1 Кричевский Р. Е. Сжатие и поиск информации. М.: Радио и связь, 1989.
2 Teahan WJ. Modeling English text, Ph.D. dissertation. New Zealand, Hamilton: University of Waikato, 1998.
Статья принята к печати 26 февраля 2007 г.

ПоказатьСвернуть
Заполнить форму текущей работой