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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19 UML диаграммы

20 BK-дерево

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

22 Хеш-таблица

23 Схема БД

24 Доступ ИА к БД