Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Аналитическая и процедурные модели поиска текстовых документов в слабо структурированных информационных массивах Хруничев Роберт Вячеславович

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Хруничев Роберт Вячеславович. Аналитическая и процедурные модели поиска текстовых документов в слабо структурированных информационных массивах: диссертация ... кандидата Технических наук: 05.25.05 / Хруничев Роберт Вячеславович;[Место защиты: ФГБОУ ВО «Тамбовский государственный технический университет»], 2018

Содержание к диссертации

Введение

1 Анализ информационно–поисковых систем. Методы документального поиска 13

1.1 Потребность в решении задачи информационного поиска 13

1.2 Типы информационно–поисковых систем 14

1.3 Лингвистические и статистические методы информационно–поисковых систем 18

1.4 Модели поиска 24

1.5 Индексирование в поисковых системах 27

1.6 Поиск при наличии ошибки в запросе 30

1.7 Методы определения меры соответствия индексов 31

1.8 Ранжирование 34

1.9 Атрибуты документов 36

1.10 Оценка качества поиска 39

1.11 Модели баз данных информационно–поисковых систем 41

Выводы по первому разделу 43

2 Аналитическая модель поиска текстовых документов в слабо структурированных информационных массивах. Процедурная модель сравнения битовых последовательностей индексов термов 46

2.1 Требования, предъявляемые к поисковым системам локального характера 46

2.2 Лингвостатистическая обработка документов 48

2.2.1 Выделение массива термов 48

2.2.2 Предварительная лингвистическая обработка документов 49

2.2.3 Векторная модель поиска 51

2.2.4 Частотный анализ термов 52

2.2.5 Определение частоты термов 54

2.3 Атрибуты документов при решении задачи поиска в слабо структурированных информационных массивах 55

2.3.1 Модель метаданных «Дублинское ядро» 55

2.3.2 Выбор атрибутов для решения задачи поиска текстовых документов в слабо структурированных информационных массивах 58

2.3.3 Аналитическая модель поиска в слабо структурированных информационных массивах 61

2.4. Индексирование при поиске с ошибкой 63

2.4.1 Хеширование по сигнатуре 63

2.4.2 Модификация метода хеширования по сигнатуре. Кластеризация термов 68

2.5 Процедурная модель сравнения битовых последовательностей индексов термов 74

2.5.1 Потребность в сравнении индексов при поиске с ошибкой 74

2.5.2 Обоснование выбора метода для решения задачи сравнения индексов при возможном изменении одного бита индекса запроса 77

2.5.3 Разработка целевой функции и набора ограничений на переменную 78

Выводы по второму разделу 83

3 Процедурная модель поиска текстовых документов в слабо структурированных информационных массивах. Оценка качества поиска 85

3.1 Предпосылки формирования векторного пространства 85

3.2 Нормировка вектора содержания по длине документа. Попозиционное взвешивание. Распределение весов между атрибутами документов в векторной модели поиска. Формирование итогового векторного пространства 86

3.2.1 Нормировка вектора содержания по длине документа 86

3.2.2 Зонное индексирование 88

3.2.3 Взвешивание по зонам 91

3.2.4 Распределение весов между зонами 92

3.2.5 Формирование итогового векторного пространства 94

3.3 Запросы в виде векторов 97

3.4 Ранжирование на основе векторной модели 100

3.5 Оценка качества поиска 103

Выводы по третьему разделу 109

4 Разработка структуры и тестирование ИПС 111

4.1 Средства реализации и условия тестирования алгоритмов 111

4.2 Структура и принцип работы приложения анализа текстовой коллекции 112

4.2.1 Состав раздела для работы со словарями 112

4.2.2 Состав раздела по обработке документов 115

4.2.3 Состав раздела отображения текущих действий 117

4.2.4 Состав раздела обработки документов различных форматов 117

4.2.5 Состав раздела вспомогательных классов 120

4.3 Структура и принцип работы ИПС 125

4.4 Тестирование ИПС 132

Выводы по четвертому разделу 135

Основные результаты и выводы 137

Список литературы и источников 138

Приложение А. Акт о внедрении в эксплуатацию 150

Приложение Б. Акт о внедрении в учебный процесс 152

Приложение В. Свидетельства о регистрации программ 153

Введение к работе

Актуальность темы исследования. Электронный документооборот -один из главных аспектов качественного и бесперебойного функционирования любой компании, организации или государственной структуры. Работа с накопленными данными, необходимость быстрой обработки запросов и повышение производительности труда сегодня являются важной стороной работы структуры любого уровня. Работодатели пытаются оценить в денежном эквиваленте время, потраченное их сотрудниками на поиск данных. Кроме этого, рассматриваются качество и эффективность использования уже накопленных данных. Зачастую принимается решение о повторном создании документов, а не о перспективах их обнаружения в базе данных.

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

Степень разработанности темы исследования. Анализ научных работ в области организации информационно-поисковых систем различного уровня (Г. Г. Белоногов, Р. С. Гиляревский, Д. Г. Латухин, Н. В. Лукашевич, И. В. Захарова, А. Н. Бевзов, К. Д. Маннинг, Р. Прабхакар, Ш. Хайнрих, Б. Магнини, Дж. Ципф, Дж. Ульман и др.) показал, что большая часть исследований посвящена глобальному поиску и поиску в локальных БД. Поиск текстовых документов в слабо структурированных информационных массивах в отдельный класс задач не выделяется. Большинство работ в этом направлении отражают исследования конкретных этапов поиска и совершенствование их методик.

Анализ показал, что поиск текстовых документов в слабо структурированных информационных массивах является мало исследованным направлением, но большинство требований, предъявляемых к локальному поиску в целом, характерны и для поиска в таких информационных массивах:

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

применение лингвистического процессора, что позволяет осуществлять поиск по всем словоформам искомого слова или словосочетания;

ранжирование результатов поиска по релевантности.

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

невысокая сложность применяемых методов;

высокое быстродействие;

минимальный объем памяти, занимаемый на сервере;

возможность модификации методов - гибкость алгоритмов;

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

хорошее качество поиска (не ниже 0,6 по критериям точности и полноты).

Объект исследования: информационно-поисковые системы (ИПС).

Предмет исследования: аналитические и процедурные модели ИПС.

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

Цель диссертации. Повысить быстродействие и произвести отбор параметров поиска в слабо структурированных информационных массивах на основе разработки аналитической и процедурных моделей ИПС.

Для достижения цели необходимо решение ряда задач:

  1. Провести анализ предметной области.

  2. Разработать аналитическую модель ИПС в слабо структурированных информационных массивах.

  3. Разработать процедурную модель поиска в слабо структурированных информационных массивах.

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

  5. Разработать блочно-модульную структуру ИПС, провести апробацию на реальном слабо структурированном информационном массиве.

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

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

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

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

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

уменьшением размера сигнатуры до однобайтового формата, позволяющим повысить быстродействие ИПС.

3. Разработана процедурная модель сравнения битовых последователь
ностей индексов термов, отличающаяся тем, что позволяет решить задачи
низкорелевантного («мягкого») поиска и возможного появления коллизии.

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


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

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

Диссертационная работа выполнена в соответствии с требованиями паспорта специальности 05.25.05 «Информационные системы и процессы» и соответствует пункту 7.

Положения, выносимые на защиту:

  1. Аналитическая модель поиска текстовых документов в слабо структурированных информационных массивах.

  2. Процедурная модель поиска текстовых документов в слабо структурированных информационных массивах.

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

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

Внедрение результатов исследования. Реализованная ИПС, а также разработанные модели и методы введены в эксплуатацию в ООО «Смолис» (компоненты «AWS Probe» и «Azure Probe» - подсистемы поиска ресурсов в облачном окружении виртуализации, компоненты «Reports» ПО «Operations Manager» - подсистема электронного документооборота по обновлению аппаратного обеспечения виртуального окружения).

Публикации. По теме исследования опубликовано 15 работ, в том числе 5 статей в изданиях, рекомендованных ВАК при Минобрнауки РФ, и 8 статей в сборниках материалов международных и всероссийских конференций. Получены свидетельства о регистрации программ.

Структура и объем работы. Диссертация состоит из введения, 4 глав, списка использованных источников и приложений. Основной текст работы содержит 149 страниц, 23 рисунка, 15 таблиц. Список использованных источников включает 102 наименования.

Лингвистические и статистические методы информационно–поисковых систем

Компьютерная лингвистика возникла на стыке таких наук, как лингвистика, математика, информатика и искусственный интеллект. Истоки компьютерной лингвистики восходят к исследованиям известного американского ученого Н. Хомского в области формализации структуры естественного языка; ее развитие опирается на результаты в области общей лингвистики [1]. Автоматическая обработка текстов направлена на решение ряда задач, которые условно разделяют на два уровня. Задачи высокого уровня - задачи распознавания речи, реферирования текстов, генерации документов, извлечения информации, т.е. приложения. Задачи низкого уровня - грамматический разбор, снятие смысловой многозначности, корректировка орфографии и синтаксический разбор, т.е. задачи лингвистической обработки [96, 98].

Одной из прикладных задач обработки текста является информационный поиск. Основные методы информационного поиска разрабатываются в рамках одноименной научной дисциплины. Однако большинство таких систем включают лингвистический компонент. По мере развития технологий информационного поиска состав и задачи лингвистического компонента менялись [74].

Лингвистическое обеспечение информационно-поисковых систем -разработка специальных информационно-поисковых языков и информационно-поисковых тезаурусов, а также других специализированных лексикографических ресурсов для обеспечения информационного поиска. В современных поисковых системах, в которых тематически значимые элементы (ключевые слова или понятия) выделяются статистическими методами, в задачи лингвистического обеспечения входит разработка лингвистических методов оптимизации выделения тематически значимых единиц в тексте [74].

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

лингвистический анализ;

статистический анализ.

В свою очередь лингвистический анализ можно разделить на четыре взаимодополняющих анализа [53]:

лексический анализ. Заключается в разборе текстовой информации на отдельные абзацы, предложения, слова, определении национального языка изложения, типа предложения, выявлении типа лексических выражений и т.д. Данный вид анализа не представляет существенной сложности для реализации. Лексема - это слово как совокупность всех его конкретных грамматических форм. В тексте встречаются словоформы (лексемы в определенной форме), а в словаре естественного языка - лексемы, точнее, в словаре записывается каноническая словоформа лексемы, называемая также леммой (для существительных это форма именительного падежа единственного числа [1];

морфологический анализ. Сводится к автоматическому распознаванию частей речи каждого слова текста. Часто морфологический анализ используется в статистических методах анализа при предварительной процедуре обработки документов для приведения слов к базовой форме. Морфологический анализ для русского языка можно реализовать практически со 100% точностью благодаря его развитой морфологии. Одним из современных вариантов реализации бессловарной морфологии в чистом виде является стеммер Портера [1];

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

семантический анализ. Заключатся в определении информативности текстовой информации и выделении информационно-логической основы текста. Проведение автоматизированного семантического анализа текста предполагает решение задачи выявления и оценки смыслового содержания текста. Данная задача является трудно формализуемой вследствие необходимости создания совершенного аппарата экспертной оценки качества информации.

Немаловажным свойством лингвистического анализа является возможность применения разного рода словарей, например синонимического, омонимического, орфографического, частотного, словаря стоп-слов и др.

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

статистика текстов по тематической направленности [55];

статистика датирования текстов [55];

частота употребления слов;

частота употребления словосочетаний (2,3,4,5,6 -граммы) [55];

статистика словоупотреблений по частям речи [92];

частота появления символа языкового алфавита [3];

биграммные (и более) частоты одновременного последовательного появления пары (и более) символов языкового алфавита [3];

статистика чередования гласных и согласных, согласных и гласных, гласных и гласных, согласных и согласных символов языкового алфавита [3];

статистики появления буквы на конкретной позиции в слове [95].

На актуальность применения языковых средств в информационно-поисковых системах ученые и исследователи стали указывать ещё на начальных этапах становления современного информационного поиска. Так, в своей диссертации от 1997 г. "Языковые средства современных информационно-поисковых систем" Захаров В.П. основной целью ставит решение ряда теоретических и практических задач применения лингвистических средств при осуществлении документального поиска [38].

В диссертации от 2014 г. "Модели и методы автоматической обработки неструктурированной информации на основе базы данных онтологического типа" на соискание ученой степени доктора технических наук Лукашевич Н.В. указывает, что " характерной чертой современных методов обработки текстовой информации стало минимальное использование знаний о мире и о языке, опора на статистические методы учета частотностей встречаемости слов в предложении, тексте, наборе документов, совместной встречаемости слов и т.п." [50].

В работах [47, 49, 9, 8, 39, 72, 7] российские и зарубежные исследователи, такие как Белоногов Г.Г., Гиляревский Р.С., Латухин Д.Г., Лукашевич Н.В., Добров Б.В., Ермаков А.Е., Захарова И.В., Терехов А.А., Бевзов А.Н., Кристофер Д. Маннинг, Прабхакар Р., Хайнрих Ш., Магнини Б., Ципф Дж., Ульман Дж. и многие другие изучают вопросы качества информационного поиска и применения онтологий, а также автоматизацию обработки текстов.

Современная исследовательская работа по лингвистическому и статистическому анализу текстов различной тематической направленности с 2003 года проводится специалистами Национального корпуса русского языка [55]. Следует отметить масштабы изучения языка, проводимые специалистами корпуса. Здесь представлены исследования лингвистической структуры языка по отдельным подкорпусам: стилистическому направлению текстов (художественному и нехудожественному), дате создания, словоупотреблений по частям речи; изучаются морфология языка, обороты, синтаксическая структура, лексико–семантические признаки, различные виды частотного анализа текстов. Кроме того, приводится анализ параметров текста, т.е. учитывается его метаразметка.

О важности и актуальности задач анализа текста свидетельствует приведенная частота употребления словосочетаний "лингвистический анализ текста" (рисунок 1.1) и "частота употребления слов" (рисунок 1.2) на миллион словоформ. Диаграммы получены по данным информационно–справочной системы Национального корпуса русского языка с помощью графических решений платформы, основанной на собрании русских текстов в электронной форме.

Анализируя приведенные на рисунках 1.1 и 1.2 диаграммы, можно с уверенностью утверждать, что исследования в области обработки и анализа текста стремительно развиваются, о чем свидетельствует характер диаграмм.

Модификация метода хеширования по сигнатуре. Кластеризация термов

Главной задачей при модификации предлагаемого [12] метода получения индекса хеша является устранение указанных выше недостатков или уменьшение их влияния в процессе поиска.

Во-первых, обозначенная в пунктах 2.2.1 и 2.2.2 предварительная обработка текста (все выделенные термы обработаны стеммером Портера и в процессе лемматизации приведены к общей нормальной основе) позволит свести к минимуму "псевдоразличность" термов и уменьшит вероятность появления пропусков при поиске.

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

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

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

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

В случае подхода с равновероятным появлением символов алфавита в термах распределение количества термов по хешам будет неравномерным, т.е. одному значению хеш-функции может соответствовать несколько термов, а другому всего один [46].

В таблице 2.3 приведены символы алфавита русского языка и частотности их употребления в текстовых коллекциях разной тематической направленности [45].

Основной модификацией метода хеширования по сигнатуре [12] стало применение неравновероятностного подхода при распределении символов языкового алфавита в процессе формирования индексной последовательности хеш-функции, что позволило приблизить распределение выделенных в процессе анализа термов к равномерному и перейти к однобайтовому формату сигнатуры.

Чтобы сумма вероятностей появления символа в каждой группе была приближенно одинаковой, распределим буквы по группам при хешировании по сигнатуре так, как показано в таблице 2.4. Такое распределение позволит в среднем получить равное количество термов, соответствующих одному значению хеш-функции (одному индексу), и уменьшить вероятность ошибки при поиске.

Также при распределении символов алфавита по группам была учтена частотность биграмм [3] таким образом, что символы, обладающие наибольшей биграммной частотностью, были разнесены в разные группы. Это позволило при формировании индексной последовательности хеш-функции получить отличные от нуля биты при наличии данных символов в терме.

На рисунках 2.6 и 2.7 приведены диаграммы распределения букв по группам и их суммарная частотность в случае подхода с равновероятным появлением символов в терме и последовательным распределением этих символов по группам, а также предлагаемой его модификацией с неравновероятным появлением символов в терме и учетом биграммной частотности при распределении символов по группам.

Диаграмма (рисунок 2.6) соответствует двухбайтовому формату формирования индекса хеш-функции, приведенному на рисунке 2.5. Очевидно, что двухбайтовый формат формирования хеш-функций, в случае подхода с равновероятным появлением символов алфавита в термах, является необоснованным и избыточным, поскольку вероятности появления единицы в индексе последних пяти групп малы (рисунок 2.6). Это делает хранение данных битов таких индексов нерациональным.

Вероятности появления "1" в любом бите индекса хеш-функции (рисунок 2.7) в таком подходе равновероятны. Одновременно при распределении символов алфавита по группам, были учтены частотности биграмм так, что наиболее часто встречающиеся подряд символы были, по возможности, разнесены в разные группы. Это позволило добиться равномерного распределения количества выделенных термов по значениям хеш-функции (рисунок 2.8).

Предложенный модифицированный метод формирования индексов при хешировании по сигнатуре устраняет недостатки, присущие существующему методу [12], а именно:

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

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

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

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

Оценка качества поиска

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

1) коллекция документов;

2) совокупность информационных потребностей потенциальных пользователей, сформированных в виде текстовых запросов;

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

Классификацию "релевантный или нерелевантный" проходит каждый документ текстовой коллекции в зависимости от информационной потребности пользователя. Такой вывод пользователя называют эталонной оценкой релевантности.

Для оценки качества информационного поиска коллекции текстовых документов и запросов пользователей должны иметь достаточно большой объем. Эксперты определяют набор из 50 запросов пользователя как минимально возможный для первичного и очень грубого приближения [47]. Следует учитывать, что релевантность оценивается информационной потребностью, а не запросом пользователя. Документ релевантен запросу, если он удовлетворяет информационную потребность, а не только содержит все слова из запроса. Конечно, для более полного соответствия информационной потребности запросы пользователя должны быть качественно выражены, чтобы можно было однозначно судить о релевантности или нерелевантности найденных документов.

На рисунке 3.5 условно показана последовательность удовлетворения информационной потребности пользователя посредством формирования запроса к информационно-поисковой системе.

Оценка качества функционирования информационно-поисковых систем может осуществляться одновременно на различных уровнях [41]:

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

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

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

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

на уровне применимости системы поиска в целом производят анализ возможного использования результатов поиска при решении задачи, а также изучают полезность этих результатов;

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

Чаще всего на практике применяется метод макрооценки, когда поисковая система в целом рассматривается как «черный ящик»; внимание сосредоточивают на временных и вычислительных затратах, не обращая внимание на особенности структуры, а также на качестве поиска и его эффективности [41].

Как правило, для оценки эффективности поисковой системы выделяют следующие критерии [32]:

1) полноту поиска - возможность поисковой системы найти все документы, релевантные запросу пользователя;

2) точность поиска - возможность поисковой системы отсеивать все документы, не релевантные запросу пользователя;

3) затраты на формирование запроса, просмотр полученных документов и взаимодействие с поисковой системой;

4) предоставление результатов поиска в нужной форме, например ссылки на документ, указание места его положения и т.п.;

5) уровень полноты охвата выдаваемых релевантных документов, интересующих пользователя.

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

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

В процессе оценки этих характеристик вводят специальные коэффициенты:

1) коэффициент полноты поиска - отношение количества релевантных документов по запросу в выдаче к общему количеству документов, находящихся в анализируемой базе;

2) коэффициент точности поиска - отношение количества релевантных документов по запросу в выдаче к общему количеству документов, полученных в результате поиска по базе.

Для формального выражения введенных коэффициентов полноты и точности поиска введем ряд символьных обозначений, позволяющих наглядно выразить эти характеристики поиска [32]:

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

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

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

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

В таблице 3.2 приведена сводная таблица, разделяющая документы на обозначенные подмножества и помогающая наглядно отобразить документы в базе и выдаче с помощью введенных обозначений [32, 41, 71].

С учетом введенных обозначений коэффициенты полноты поиска R и точности поиска Р можно формально выразить следующими соотношениями:

На практике используют и дополнительные оценки качества и эффективности поиска:

1) коэффициент выпадения при поиске F - отношение количества нерелевантных документов, выданных поисковой системой по запросу пользователя, к общему количеству нерелевантных документов во всей коллекции поисковой базы;

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

Все приведенные характеристики (коэффициенты) оценки качества поиска приведены для однократной процедуры запроса к поисковой системе. С учетом многократных обращений пользователей к поисковой системе (к возможных запросов) выражения (3.14)-(3.17) для /-го запроса можно записать в виде (3.18) (3.21) соответственно [41]:

Каждое из выражений (3.18)-(3.21) характеризует точечную оценку соответствующего параметра (коэффициента) для /-го запроса пользователя, которая не является информативной с точки зрения оценки качества функционирования поисковой системы в целом на всем множестве анализируемых документов коллекции.

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

Структура и принцип работы ИПС

Поисковое приложение (реализовано в виде самостоятельной программы SearchEngine) – web-приложение, которое обеспечивает взаимодействие пользователя и системы. Оно разработано с использованием шаблона архитектуры Model-View-Controller (MVC), разделяющим данные приложения, пользовательского интерфейса и управляющей логики на три компонента: модель (model), представление (view), контроллер (controller). Основным преимуществом данной схемы является то, что компоненты могут изменяться и дополняться независимо друг от друга, что позволяет реализовать модульный принцип разработки.

Схема работы приложения SearchEngine представлена на рисунке 4.1.

Компонент Model содержит базу данных, которая отвечает за получение словарей и документов базы, обработанных приложением Console, а запросы POST и GET от этого приложения принимает и обрабатывает компонент Controller (рисунок 4.1). Данный компонент разработан с использованием объектно-ориентированной технологии Entity Framework, которая предоставляет возможность работы с базами данных через код C#. Это дает ряд существенных преимуществ: не требуется постоянно контролировать код доступа к данным; работа с таблицами базы данных происходит сходно работе с классами C#; Entity Framework внутренним инструментарием преобразовывает код C# в SQL-инструкции.

Компонент Model содержит объектные модели данных и процесса поиска, а также модели запросов и ответов пользователя.

126

Рисунок 4.1 – Схема работы программы SearchEngine Модель данных содержит класс DbProvider (наследник класса DbContext), полями которого являются объекты класса DbSet – наборы сущностных классов, которые можно использовать для создания запросов CRUD (create, read, update, delete) к данным. Посредством экземпляров этого класса описываются различные объекты базы данных (таблицы, представления, хранимые процедуры и т.д.). Здесь также описываются представления документов (Document), словарей (Dictionaries), связей между словарями и документами (LinksDictionaryDocument) и история загрузок найденных файлов (HistoryDownloads).

Класс Document модели содержит поля: ID, имени, даты и времени создания, пути к документу, его расширения, текста для предварительного отображения при поиске, а также набор объектов, связывающих словари и документы (LinkDictionaryDocument).

Класс Dictionary модели содержит поля: ID элемента словаря, слова в нормальной форме, хеша слова, типа словаря, а также набора объектов, связывающих словари и документы (LinkDictionaryDocument).

Класс, описывающий историю загрузок включает поля идентификатора записи, IDдокумента и количества обращений к нему.

Связь элементов словаря и документа задается в модели с помощью класса LinkDictionaryDocument, включающего ID записи, документа, элемента словаря и количества вхождений указанного элемента словаря в документ.

Модель поиска документов описывается классами Link, SearchService и Word.

Класс Word описывает слово с позиций частотного анализа. Помимо типов словаря и ID записи в словаре класс содержит такие поля, как общее количество документов D, количество документов с данным словом Dit, количество вхождений данного слова в документ CWD, обратная документальная частота ODC, вес слова в документе W, K – коэффициент, учитываемый при ранжировании.

Класс Link задает ссылку на документ. Его свойствами являются список объектов класса Word - Words, объект класса Document, а также вес ссылки W, представляющий собой косинусную метрику документа.

Класс SearchService реализует алгоритмы поиска и сортировки документов. Он включает поле поставщика данных класса DbProvider.

Метод ProcessingDocument возвращает объект класса Link, обрабатывая объект класса Document и список объектов Words. В процессе работы метода для каждого слова в списке заполняется поле CWD – количество вхождений слова в данный документ (ведется подсчет слов, которые есть и в документе, и в словаре, с помощью поля Count класса LinkDictionaryDocument).

Получить отсортированный по значимости список слов из пользовательского запроса в виде списка объектов класса Word позволяет метод GetListWords, который в свою очередь использует методы FindWord (возвращает объект класса Word – слово в нормальной форме, найденное в словаре) и SortWordsList (первоначально располагаются слова, требующие частотного анализа, – тип словаря Analys, а затем остальные слова).

Метод GetLinks позволяет получить список объектов класса Link и коллекцию объектов класса Document, к которой возможны LINQ-запросы. Входными параметрами являются запросы пользователя. Этими запросами выделяются документы, которые содержат слова из запроса, после чего эти документы обрабатываются методом ProcessingDocument (вместе со списком слов из запроса) и ранжируются по косинусной метрике. Результат – ранжированный список.

Метод Search класса SearchService выполняет поиск документов в базе по запросу пользователя (запрос – объект класса Request). Он возвращает список объектов класса ответа на запрос (ответы – объекты класса Response).

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

После установки всех предварительных ограничений производится поиск по ключевым словам с помощью метода GetLinks. Если ключевые слова не были указаны, то берутся первые 100 документов, найденные по предыдущим ограничениям. На основе найденных документов создаются объекты класса Response и возвращается список этих объектов.

Классы Request и Response являются наследниками класса BaseModel, который содержит следующие поля: Name (строка с названием документа), Keywords (строка с ключевыми словами).

Класс Request содержит дополнительные свойства DateMin и DateMax (ограничивают дату создания документа) и строку форматов искомых документов Formats.

Класс Response содержит поля: ID – идентификатор документа, Text – первые несколько слов документа для его описания, даты создания документов Date, а также строки пути к документам Path.

Компонент Controller обрабатывает действия пользователя, оповещая модель о необходимости изменений. Также он принимает обработанные данные (документы и словари) от приложения Console. Базовым в данном компоненте является класс BaseController, который с помощью поля _dbProvider класса DbProvider обеспечивает взаимодействие с базой данных. Наследниками этого класса являются классы DictionaryController, DocumentController, SearchController.

Класс DictionaryController обеспечивает работу приложения со словарями. Он обрабатывает POST-запросы от приложения Console на занесение обновлённых ранее не существующих данных в модель и GET-запросы от пользователя на очистку базы данных.

Метод Update обрабатывает POST-запросы на обновление словарей, добавляя новые элементы и сохраняя изменения в базе.

Метод Management обрабатывает GET-запросы пользователя на очистку базы данных.

Класс DocumentController реализует обработку действий, связанных с документами.

Метод Save принимает POST-запросы от приложения Console на добавление документа в базу данных. В процессе работы метод создаёт объект класса Document (принадлежащий Model), при этом происходит проверка на существование документа в базе и создание или обновление документа в базе данных. Затем объект класса Document приложения Console передаёт данные объекту класса Document модели (с помощью метода MapDocument). Документ связывается со словарями модели с помощью метода CreateLinks (создается список объектов LinkDictionaryDocument). Изменения сохраняются в базе данных.

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