Разработка информационного агента (робота) информационно-поисковой системы для сбора информации в сети Интернет Малков Владимир

Введение Экспоненциальные темпы роста объемов информации Поиск информации –Отсутствие универсальных методов –Необходимость разработки новых методов и инструментов поиска информации –Сбор данных - неотъемлемый этап работы системы поиска информации

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

Постановка задачи (2) Требования к ИА –Взаимодействие с БД по TCP/IP –Экономное потребление ОЗУ –Переносимость Модуль лексический анализа документов –Вход: текст документа –Идентификация лексем по словарю ЕЯ –Формирование списка лексем-кандидатов для неизвестных лексем –Выход: мета-такст

О взаимодействии с БД?

Решение задач лексического анализа Вход: лексема-запрос Поиск –Известные лексемы (car->recordID): поиск точными методами –Неизвестные лексемы (kyboard- >{keyboard, cyborg}; ) Мера близости для выявления «похожих» лексем в словаре

Поиск по подобию (ПП) Метризация пространства поиска –Множество поиска - лексемы словаря системы –Метрика Левенштейна (как один из вариантов меры близости лексем!) –Поиск на базе вычисления метрики По диапазону {1,k} Ближайших соседей Нижняя оценка трудоемкости задачи и существование эффективных методов поиска – открытые проблемы

Пути оптимизации ПП Учитывать характер объектов МП –Дискретная метрика –Ограниченный диаметр множества поиска –BK-дерево как базовый метод (Burkhard-Keller) Равномерное наполнение поддеревьев Остановка на точном совпадении Оптимизировать вычисление метрики нельзя: черный ящик для гибкости меры близости Сократить количество вызовов метрики Минимизация операций ПП на основе специфики входных данных задачи

Результаты предварительного анализа текстов

Алгоритм распознавания лексем Вход: лексема 1.Точный поиск в хеш-таблице 2.Распознавание неизвестных лексем a.Точный поиск в кеше результатов ПП на тернарном дереве поиска b.Поиск в BK-дереве только первого вхождения неизвестной лексемы и сохранения результата в кеш Поисковые структуры данных строить над общим словарем

Результаты (1)

Результаты (2)

Результаты (3) Задача распознавания лексем сведена к поиску в МП Минимизировано количество обращений к процедуре приближенного поиска Реализован ИА

Заключение Методы поиска в МП имеют большое практическое значение Дальнейшие исследования –Удаление СНЛ –Предварительная оценка релевантности –Учет морфологии ЕЯ –Методы ПП

Спасибо за внимание

Пример мета-текста

Грамматика мета-текста

Графики всех замеров крупно

UML диаграммы

BK-дерево

Тернарное дерево

Хеш-таблица

Схема БД

Доступ ИА к БД