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

На правах рукописи

АНДРОНОВ Григорий Дмитриевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ ОБРАБОТКИ ПОТОКОВ ОПЕРАТИВНЫХ ИНФОРМАЦИОННЫХ СООБЩЕНИЙ

05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 1997

Работа выполнена в научно-исследовательском центре информатики при Министерстве Иностранных Дел Российской Федерации

Научный руководитель:

доктор физико-математических наук, профессор Баранов С.Н. Официальные оппоненты:

доктор технических наук, профессор Пономарев В.М. кандидат технических наук, доцент Мустафин Н.А.

Ведущая организация:

Московский физико-технический институт

Защита состоится \99/£_ г. в Л? часов

на заседании диссертационного совета Д.003.62.01 при Санкт-Петербургском институте информатики и автоматизации Российской академии наук (199178, С,- Петербург, 14-я линия, д.39)

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского института информатики и автоматизации РАН (199178, С,- Петербург, 14-я линия, д.39)

Автореферат разослан

Ученый секретарь диссертационного совета

Копыльцов А.В.

1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Диссертация является обобщением результатов исследовательской и практической деятельности автора в течение пяти лет в области обработки потоков оперативных информационных сообщений (ОИС). В работе исследуются характеристики ОИС специального вида, предлагаются методы их обработки и организации в оперативные базы данных (ОБД), разрабатывается модель и технология автоматической обработки оперативных сообщений.

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

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

Целью работы является построение модели автоматической обработки ОИС специального вида и создание на ее базе технологии автоматического администрирования ОБД с возможностями оптимизации.

Научная новизна работы состоит в следующем:

• выявлены специфические особенности ОИС и введены понятия эквивалентности, подмножеств и других зависимостей между ОИС;

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

• разработана и исследована новая модель обработки ОИС, не зависящая от используемой системы управления базами данных;

• предложено интегрирование различных методик обработки ОИС в рамках единой системы, позволяющей проводить автоматическое администрирование.

Практическая ценность. Научные результаты автора были использованы при разработке "Общего технического задания на ИС ВПВ МИД РФ" и позволили разработать программный комплекс "Инфо-сервис" (ПК), предназначенный для обработки ОИС. ПК может быть применен при проведении научных исследований, где требуется анализ ОИС и выделение информации, обладающей заданными признаками, из общих потоков сообщений средств массовой информации, коммерческих предложений, научных сообщений и т.д.

Первая версия ПК была внедрена в МИД России в январе 1994 года. Опыт эксплуатации ПК во многих подразделениях МИД подтвердил правильность предложенных подходов. До настоящего момента времени происходит непрерывный рост числа пользователей, работающих с комплексом. ПК используется для обработки ОИС агентств "ИТАР-ТАСС", "Интерфакс", РИА "Новости", USIA, газет и

журналов, брифингов и других сообщений. ПК был представлен на выставках "СопгНек-96", "Мс1сош-96", "Соггиек-97" и ряде других.

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

Апробация работы и публикации. По теме диссертации опубликовано 5 работ. Характерные черты ОИС, предложенные автором методы их обработки и технология автоматического администрирования ОБД докладывались и обсуждались на конференциях "Региональная информатика-95" в Санкт-Петербурге, "Сложные проекты и решения на основе высоких информационных технологий", "Новнет" в Москве. Описание модели обработки ОИС и ПК "Инфо-сервис" приведено в статьях, опубликованных в сборниках "Информационные технологии и интеллектуальные методы" Санкт-Петербургского института информатики и автоматизации и в журнале "Банковские технологии".

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и 1 приложения. Общий объем работы с учетом списка литературы и приложения составляет 148 страниц машинописного текста.

2. СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Существующие информационные системы анализируются на наличие необходимых для обработки ОИС функций (индексирование, автоматическая обработка текстов, определение значений атрибутов, поиск зависимостей и др.) и устанавливается, что большинство систем включают их не в полном объеме и не полностью удовлетворяют требованиям по времени их выполнения.

Рассматриваются существующие методы индексирования и поиска текстовых сообщений. Отмечается необходимость использования корректируемых пользователями классификаторов и словарей при обработке, поиске и анализе ОИС.

Анализируются различные варианты поисковых стратегий и делается вывод о целесообразности применения к ОБД комбинированного варианта. Рассматривается новый вариант поисковой задачи по отношению к ОИС, в котором в качестве запроса фигурирует документ или список документов, то есть поисковое предписание формулируется в виде "Является ли документ ] релевантным документу (списку) I ?".

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

• провести анализ особенностей потоков ОИС и применимости существующих методов и технологии обработки документов к этим потокам;

• разработать методы и построить модель предварительной обработки ОИС специального вида;

• разработать технологию автоматической обработки ОИС специального вида;

• разработать программные средства, реализующие построенную модель, поддерживающие методы автоматической обработки ОИС и созданную технологию.

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

• большие ежедневные потоки (от нескольких сотен до нескольких тысяч сообщений);

• относительно небольшой средний объем (от 1 до 10 кбайт в зависимости от источников сообщений);

• быстрое уменьшение актуальности с течением времени (за сутки вероятность обращения к сообщению уменьшается более чем в 2 раза);

• наличие в текстах исходных сообщений структурированных элементов, требующих распознавания;

• возможные ошибки в исходных сообщениях;

• наличие зависимостей: = Бг, Б1 ~ Бг (совпадение или эквивалентность сообщений и Бг), с 82 (вхождение одних сообщений в другие, например, аннотации и краткие сводки), 81=82+83 (линейные комбинации, например, хроника дня) и др.

В качестве примеров ОИС приводятся сообщения информационных агентств "ИТАР-ТАСС", "Интерфакс", "Рейтер", РИА "Новости", электронные версии газет и журналов "Известия", "Российские вести", "Итоги", "Московские новости", финансовые и коммерческие сообщения "Финмаркет", научные и другие сообщения.

Отмечается необходимость автоматического администрирования ОБД, предусматривающего автоматическое индексирование, которое для обеспечения эффективного поиска требуемой информации должно включать:

• определение значений ряда атрибутов ОИС (например, названий сообщений, дат формирования, наименований источников) по структурированным элементам текстов;

• определение значений ряда атрибутов ОИС (например, тематики, стран или городов, о которых упоминается в сообщениях) по неструктурированным фрагментам текстов;

• построение инверсного индекса по всем словам текстов ОИС;

• определение значений специальных атрибутов по устанавливаемым зависимостям между ОИС.

Предлагается новый метод "досье" организации ОИС в ОБД, в соответствии с которым каждое досье представляет собой набор документов (оперативных сообщений или их фрагментов), характеризуемых своей структурой поискового образа (ПОД), и подразделяется на ОБД администратора, предназначенную для предварительной обработки ОИС, и ОБД пользователей,

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

Метод "досье" обеспечивает пользователям непрерывный доступ к ОБД и минимизирует время блокирования работы администратора (/„=£?, ta->min) при обновлении ОБД, а также исключает случайное или несанкционированное удаление сообщений, решая при этом задачу поддержания целостности ОБД.

Экспериментально определены характеристики ежедневных потоков ОИС и пользовательских запросов в ИС ВПВ. В 1996 году ежедневно обрабатывалось около 350 ОИС из 12 источников информации, при этом средняя длина одного сообщения составила 2,7 кбайт, а максимальная - 360 кбайт. Отмечен непрерывный рост потоков ОИС и пользовательских запросов.

На основе полученных экспериментальных данных проведена

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

получение только самой свежей информации или на включение в ответ

сведений о событиях, произошедших несколько дней назад, и откликах

на эти события. Отмечается необходимость хранения в ОБД

сообщений в течение ограниченного времени txp=const (для потоков

ОИС в ИС ВПВ - последние N дней). Приводится алгоритм,

позволяющий оценить оптимальное значение N', при котором

пользователи получают в ответ на запросы максимальное число

релевантных сообщений, то есть суммарное число требуемых

сообщений (число отказов), которые еще не поступили в ОБД (Jo) и

уже были удалены из нее (Ji) минимально:

N K(i) N K(i) A*t'

Jo + Ji (N) = ц * t'* (1 -1 — ) * (50-N) + ц * t' * I-— *-->min ,

i=l К i=l К 8*i

где ц и X - математическое ожидание соответственно числа запросов и числа новых сообщений, поступивших в единицу времени,

I' - время предварительной обработки сообщений и обновления ОБД, К 0) - число запросов, предполагающих поиск сообщений за последние 1 дней, К - общее число запросов.

Для потока ОИС "Интерфакса" и пользовательских запросов к ОБД в ИС ВПВ с апреля 1995 года по январь 1997 года оптимальное время хранения в ОБД составило Ы' ~ 8 суток (рис.1):

Рис. 1. Зависимость числа отказов от количества дней хранения сообщений

Отмечена необходимость корректировки исходных данных, в первую очередь вспомогательных словарей, по результатам анализа пользовательских запросов к ОБД,

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

Предлагается базовая технология обработки оперативных сообщений, предусматривающая организацию ОБД по методу "досье",

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

Рис.2. Схема обработки ОИС

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

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

Сделан вывод о целесообразности снижения времени предварительной обработки ОИС за счет некоторого увеличения времени поиска:

и и

2 I инд. (О + £ I поиска 0) -> ПИП, 1: поиска 0) < Т пор. 0=1,..., Ьг),

1=1

где и««. - время индексирования сообщения, поиска - время выполнения поискового запроса, 1л и Ьг - среднее ежедневное количество соответственно ОИС и поисковых запросов, ТПОр -максимально допустимое время поиска оперативной информации.

Исследована применимость различных методов построения инверсного индекса к текстам ОИС, среди которых рассмотрены:

• последовательный поиск в неупорядоченном массиве;

• поиск в упорядоченном массиве слов, предусматривающий его организацию в виде двоичного дерева;

• использование различных функций расстановки.

Установлено, что приведенные методы не позволяют реализовать

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

его ^я буква, а К определяется путем статистического анализа

контрольной выборки для заданных источников ОИС специального вида.

Разработан алгоритм предварительного определения функции расстановки И(\у), зависящей от переменного числа первых букв слов ОИС специального вида и равномерно присваивающей словам различные значения в диапазоне от 1 до заданного числа п, по контрольной выборке для заданных источников ОИС, а также алгоритм использования вычисленных значений Дчг) при индексировании текстов новых ОИС. Отмечается независимость разработанных алгоритмов от языка, на котором составлены исходные ОИС. Предложен также алгоритм автоматического определения стоп-слов для источников ОИС.

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

• поиск в индексе, построенном для словарей, всех различных слов текстов;

• поиск в индексе, построенном для текстов, всех различных слов словарей.

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

Проведено сравнение двух вариантов поиска словосочетаний:

• поиск каждого слова и комбинирование результатов поиска;

• поиск одного из слов и просмотр всех фрагментов, содержащих это слово, на предмет вхождения в него других слов.

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

вхождение которых в тексты по результатам обработки контрольной выборки менее вероятно.

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

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

Сделан вывод, что разработанный метод автоматического индексирования позволяет удовлетворить информационные потребности пользователей ОБД при минимизации времени, затрачиваемого на предварительную обработку ОИС, что позволяет использовать его в технологическом процессе обработки ОИС специального вида.

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

В четвертой главе описываются особенности и рассматриваются примеры практического использования разработанного автором программного комплекса "Инфо-сервис", ориентированного на исследование ОИС и автоматическую обработку их потоков, использующего разработанные методы, реализующего модель и

технологию обработки ОИС специального вида. Приводятся основные функции ПК:

• ориентация на обработку ОИС специального вида;

• организация ОБД по методу "досье";

• возможность поиска требуемых сообщений по произвольно заданным словосочетаниям на естественном языке с анализом вводимых запросов различных типов;

• быстрая настройка на новые источники оперативной информации;

• наличие ряда специфических процедур, таких, как проверка сообщений на идентичность и определение зависимостей между ОИС;

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

Приводится порядок построения нового досье:

• определение конфигурации;

• описание структуры ПОД;

• определение, подключение и корректировка требуемых классификаторов и словарей.

Рассматриваются процедуры построения инверсного индекса и последующего поиска словосочетаний. Оценивается объем сформированных индексных файлов, составляющий примерно 7*Ы~, где М~ - общее количество слов в выборке ОИС, что немного меньше суммарного объема текстов этой выборки и является допустимым для ОБД.

Временные характеристики обработки ежедневных потоков ОИС специального вида (около 450 сообщений суммарным объемом текстов около 1,5 Мбайт, процессор Р5-90) в ПК "Инфо-сервис" приведены в табл. 1.

Таблица 1

Обработка ежедневных потоков ОИС в ПК "Инфо-сервис"

Наименование операции Время выполнения

Разбиение на документы и определение значений атрибутов по структурированным элементам текстов 3 мин.

Определение значений поисковых атрибутов по неструктурированным элементам текстов 5 мин.

Поиск устаревших сообщений и их архивирование 2,5 мин.

Перенос в ОБД и построение инверсного индекса 1,5 мин.

Отождествление копий 2 мин.

Суммарное время обновления ОБД 14 мин.

Для сравнения, соответствующее время обновления ОБД в среде Lotus Notes, используемой для обработки и хранения документов, без учета отсутствующих в ней процедур автоматического определения значений поисковых атрибутов, составляет около 25 мин.

Отмечается, что комплекс не ориентирован на конкретную вычислительную сеть и работает в сетях, взаимодействующих с MS-DOS, MS Windows или Windows-95. Версия ПК для MS-DOS написана на языках С++ и Clipper; версия для Windows 3.1 и Windows-95 - на языках С++ для Windows и Visual FoxPro.

В ПК реализованы основные функции, обработки потоков ОИС. Многие процедуры комплекса, предназначенные для исследования особенностей и автоматической обработки ОИС были введены или скорректированы на основе рекомендаций пользователей: сотрудников

подразделений различной иерархии МИД России, специалистов аналитических групп ряда государственных и коммерческих предприятий.

В приложении 1 приведен пример тематического классификатора и словаря для ОИС средств массовой информации.

Заключение содержит перечисление основных результатов работы.

3. ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Предложен новый метод "досье" для организации ОИС специального вида в ОБД.

3. Разработан новый метод автоматического индексирования ОИС, учитывающий особенности их потоков, позволяющий минимизировать время их предварительной обработки и обеспечивающий наиболее полное удовлетворение информационных потребностей пользователей ОБД.

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

5. Разработан и внедрен комплекс программных средств "Инфо-сервис", подцеживающий методы и реализующий технологию автоматической обработки ОИС, работающий в подразделениях различной иерархии (секретариатах заместителей министров, исполнительных секретариатах, департаментах) МИД России с сообщениями средств массовой информации и другими видами ОИС.

4. РАБОТЫ, ОПУБЛИКОВАННЫЕ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Андронов Г. Д. Особенности построения комплекса программных средств для работы с оперативной информацией // Информационные технологии и интеллектуальные методы: Сб. научн. тр. асп. СПИИ РАН. - СПб., 1996. - С. 21-30.

2. Андронов Т.Д. Методы автоматической обработки сообщений СМИ // Информационные технологии и интеллектуальные методы: Сб. научн. тр. асп. СПИИ РАН. - СПб., 1997. - С. 167-178.

3. Андронов Т.Д., Стеценко A.B. Обработка оперативных сообщений в АБС // М., Банковские технологии. - 1997. - №6. - С. 56-59.

4. Андронов Г.Д. Особенности обработки оперативной информации на примере оперативных информационных сообщений ИТАР-ТАСС // Тез. докл. IV Санкт-Петербургской межд. конф. "Региональная информатика", 15-18 мая 1995 г. - СПб., 1995. - ч.1, С. 117-118.

5. Андронов Г.Д. "Фильтр-М" - система автоматической обработки потоков текстовой информации // Тез. докл. научн.-практ. конф. "Сложные проекты и решения на основе высоких информационных технологий", 14 ноября 1996 г. - М., 1996. - С. 46-50.