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

• Хруничев, Роберт Вячеславович
• кандидат наук
• 2018

Оглавление диссертации кандидат наук Хруничев, Роберт Вячеславович

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

1 АНАЛИЗ ИНФОРМАЦИОННО-ПОИСКОВЫХ СИСТЕМ. МЕТОДЫ ДОКУМЕНТАЛЬНОГО ПОИСКА

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

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

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

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

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

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

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

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

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

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

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

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

2 АНАЛИТИЧЕСКАЯ МОДЕЛЬ ПОИСКА ТЕКСТОВЫХ ДОКУМЕНТОВ В СЛАБО СТРУКТУРИРОВАННЫХ ИНФОРМАЦИОННЫХ МАССИВАХ. ПРОЦЕДУРНАЯ МОДЕЛЬ СРАВНЕНИЯ БИТОВЫХ

ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИНДЕКСОВ ТЕРМОВ

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

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

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

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

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

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

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

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

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

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

в слабо структурированных информационных массивах

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

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

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

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

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

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

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

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

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

3 ПРОЦЕДУРНАЯ МОДЕЛЬ ПОИСКА ТЕКСТОВЫХ ДОКУМЕНТОВ В СЛАБО СТРУКТУРИРОВАННЫХ ИНФОРМАЦИОННЫХ МАССИВАХ. ОЦЕНКА КАЧЕСТВА ПОИСКА

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

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

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

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

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

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

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

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

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

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

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

4 РАЗРАБОТКА СТРУКТУРЫ И ТЕСТИРОВАНИЕ ИПС

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

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

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

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

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

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

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

СПИСОК ЛИТЕРАТУРЫ И ИСТОЧНИКОВ

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

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

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

Введение диссертации (часть автореферата) на тему «Аналитическая и процедурные модели поиска текстовых документов в слабо структурированных информационных массивах»

ВВЕДЕНИЕ

Актуальность темы исследования. Электронный документооборот -один из главных аспектов качественного и бесперебойного функционирования любой компании, организации или государственной структуры. Работа с накопленными данными, необходимость быстрой обработки запросов и повышение производительности труда сегодня являются важной стороной работы структуры любого уровня. На тему доступности информации руководителями учреждений проводится множество исследований. Работодатели пытаются оценить в денежном выражении время, потраченное их сотрудниками на поиск нужной информации. Помимо финансовой стороны вопроса рассматриваются качество и эффективность использования уже накопленной информации. Зачастую принимается решение о повторном создании документов, а не о перспективах их обнаружения в имеющейся базе данных [14, 29, 89, 90, 101].

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

Поиск данных в слабо структурированных информационных массивах в отдельный класс задач в литературе не выделяется. По сложившейся классификации [33, 47] близким к такому поиску является поиск в локальных базах данных. Но поиск локального уровня имеет кардинальные отличия [46]:

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

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

однако малые компании, как правило, имеют слабо структурированные информационные массивы;

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

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

Основными требованиями, предъявляемыми к локальным системам поиска, являются:

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

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

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

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

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

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

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

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

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

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

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

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

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

Множество исследований, в том числе и авторов, перечисленных выше, были проведены на гранты РФФИ в рамках российского семинара по оценке методов информационного поиска (РОМИП).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Методология и методы исследования. При решении задачи организации поиска в слабо структурированных информационных массивах использовались методы и модели представления и обработки информации; применялись методы структурирования данных; международные стандарты; применялись алгоритмические методы при нахождении оптимального решения задачи оптимизации, а также применялись методы математической статистики. Диссертационная работа выполнена в соответствии с требованиями паспорта специальности 05.25.05 - «Информационные системы и процессы» и соответствует пункту 7: прикладные автоматизированные информационные системы, ресурсы и технологии по областям применения (технические, экономические, гуманитарные сферы деятельности), форматам обрабатываемой, хранимой, представляемой информации (табличная, текстовая, графическая, документальная, фактографическая, первичная или вторичная); аналитические, процедурные, информационные модели предметной области (системы принятия групповых решений, системы проектирования объектов и процессов, экспертные системы и др.), включаемые в контур обработки информации и принятия решений.

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

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

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

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

Реализованная информационно-поисковая система, а также разработанные модели и методы введены в эксплуатацию в ООО «Смолис» (компоненты «AWS Probe» и «Azure Probe» - подсистемы поиска ресурсов в облачном окружении виртуализации, компоненты «Reports» ПО «Operations Manager» - подсистема электронного документооборота по обновлению аппаратного обеспечения виртуального окружения). Результаты исследования внедрены в образовательный процесс и информационную образовательную среду ФГБОУ ВО «Рязанский государственный радиотехнический университет». Акты внедрения в эксплуатацию в OOO «Смолис» и внедрения результатов диссертационной работы в учебный процесс кафедры электронных вычислительных машин, а также информационную образовательную среду ФГБОУ ВО «РГРТУ» прилагаются. Научные результаты реализованы в виде прикладных программ, что подтверждено свидетельствами о регистрации в объединенном фонде электронных ресурсов «Наука и Образование».

Апробация работы. Результаты диссертационного исследования докладывались и обсуждались на XV-ой Всероссийской научно-технической конференции студентов, молодых ученых и специалистов (Рязань, 2 010), XVI-ой Всероссийской научно-технической конференции студентов, молодых ученых и специалистов (Рязань, 2011), 11Х-й международной научно-практической конференции «Современные концепции научных исследований» (Москва, 2014), международной научно-практической конференции «Новая наука: проблемы и перспективы» (Уфа, 2015).

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

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

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

1 АНАЛИЗ ИНФОРМАЦИОННО-ПОИСКОВЫХ СИСТЕМ. МЕТОДЫ

ДОКУМЕНТАЛЬНОГО ПОИСКА

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

По оценке Siemens Business Services, до 80 % своего рабочего времени руководитель тратит на работу с информацией, до 30 % рабочего времени сотрудников уходит на создание, поиск, согласование и отправку документов, каждый внутренний документ копируется в среднем до 20 раз и до 15 % корпоративных документов безвозвратно теряется (при этом, по данным журнала ASAP, среднестатистический служащий тратит ежегодно до 150 ч своего рабочего времени на поиск утерянной информации) [29]. Справедливо замечание о том, что это исследование зарубежной компании, но в целом оно дает представление о том, насколько в современном мире актуальна задача создания и совершенствования методов и моделей информационно-поисковых систем разного уровня.

Сегодня актуальность задачи информационного поиска уже ни у кого не вызывает сомнения, кроме того, она тем выше, чем больше объем накопленных неструктурированных данных. Очевидно, что минимизация временных и вычислительных затрат на поиск нужной информации является основным вектором развития данной отрасли знаний. Современные информационные технологии в области анализа данных направлены на обработку массивов больших данных - технологии «Big Data». Передовые компании выделяют большие средства на разработку и внедрение этих технологий. Основной предпосылкой для развития этих технологий является необходимость обработки большого объема накопленных данных и извлечения из них информации, полезной для выбора стратегии развития и разработки бизнес-моделей [14, 63, 89, 90, 101].

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

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

Передовые исследования в области поиска и анализа информации осуществляются крупными компаниями и направлены, как правило, на глобальный поиск. Поиск же в информационных массивах, порой принципиально отличающийся от глобального, такими средствами и ресурсами исследования не обеспечен. Большая часть российского сектора исследований в этом направлении была осуществлена на гранты РФФИ в рамках проекта российского семинара по оценке методов информационного поиска (РОМИП) [63]. Последние объявления на официальном сайте датированы 2014 годом. Очевидно, что проблема локально поиска и, в частности, поиска в слабо структурированных информационных массивах решается зачастую отдельными исследователями самостоятельно, поскольку коммерческий эффект минимален, но актуальность задачи только возрастает.

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

Первая полноценная поисковая система появилась в 1994 году, ею стала система поиска WebCrawler. Уже в 1995 году появились проекты поисковых систем AltaVista и Lycos. AltaVista удерживала лидирующие позиции в области поиска в течение многих лет. В 1997 году студенты Стэнтфордского университета С. Брин и Л. Пейдж разработали поисковую систему Google, являющуюся лидером в области поиска на сегодняшний день.

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

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

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

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

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

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

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

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

С точки зрения требований, предъявляемых к точности поисковых операций, задачу поиска разделяют на две крупные подзадачи [33]:

• поиск в глобальных базах текстовой информации (интернет);

• поиск в локальных (корпоративных, сайтовых или персональных)

базах.

Наибольшие положительные результаты к настоящему времени достигнуты в сфере глобального поиска (ИПС Google , AltaVista , Yahoo!, Yandex , Rambler, ...). В глобальных базах с большой долей вероятности может быть найден релевантный ответ на запрос пользователя. Поэтому модели поисковых систем для интернета, как правило, базируются на вероятностно-статистических алгоритмах, ориентированных на отбор текстовой информации по относительно простым формальным правилам и признакам. В них практически не учитываются лингвистические особенности и грамматический строй языковой основы отбираемой текстовой информации [33].

Локальные базы (корпораций, ведомств, учреждений) характеризуются значительно меньшими объемами информации. Очевидно, что для поиска точного ответа в локальных базах вероятностно-статистические методы практически неприменимы. Качество работы учреждений зачастую напрямую зависит от оперативности обеспечения персонала необходимой информацией. Успешный поиск точного ответа в локальных и персональных системах может быть реализован только на основе достаточного глубокого лексико-грамматического анализа текстовой базы и запросов пользователей [33].

Помимо указанных типов поиска (локального и глобального), Кристофер Д. Маннинг, Прабхакар Рагхаван, Хайнрих Шютце [47] выделяют ещё один -персональный информационный поиск - поиск на локальном компьютере. В этом случае важными характеристиками являются простое сопровождение и инсталляции, небольшой объем занимаемой памяти и размер индекса,

представляющего документ, а также «быстрые» алгоритмы сравнения индексов для уменьшения объема занимаемой кэш-памяти.

Очевидно, что при организации поиска важными характеристиками являются размер индекса и скорость индексации. В поисковых системах Internet размер индекса - не интересующая пользователя информация - это проблема владельца поисковой системы. А от скорости индексации зависит скорость повторного прохода по уже проиндексированным ресурсам. Для локального поиска приоритетность параметров противоположная: размер индекса - главная задача, а скорость индексирования - второстепенная, поскольку индексирование и переиндексирование осуществляются реже [61].

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

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

На данный момент существуют программные решения, позволяющие осуществлять локальный и персональный поиск, например такие, как "Архивариус 3000", " diskMETA", " DVYGUN Smart Search" и др., но практически все они являются платными и не удовлетворяют современным тенденциям поиска информации в слабо структурированных информационных массивах с многопользовательским доступом, а поисковые системы в локальных базах имеют принципиальную разницу с решаемой задачей, так как осуществляют поиск в структурированных базах. Зачастую они содержат дополнительные модули, непосредственного отношения к задаче документального поиска не имеющие, но их наличие накладывает дополнительные требования при применении таких поисковых систем. Кроме того, предоставляемые по лицензии, такие решений не позволяют производить оптимизацию под конкретные условия применения. Основным недостатком персональных систем поиска является то, что они требуют установки ПО на локальный компьютер пользователя, т.е. не поддерживают режим работы по принципу web-приложения, когда любой пользователь локальной сети может выполнить запрос к базе без установки дополнительного ПО. Следует отметить, что слабо структурированные информационные массивы зачастую расположены на обычном ПК стандартной комплектации, который не обладает большими вычислительными мощностями, что накладывает дополнительные ограничения на организацию анализа имеющейся текстовой информации, индексацию и поиск документов.

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

Список литературы диссертационного исследования кандидат наук Хруничев, Роберт Вячеславович, 2018 год

Хеш Список слов

0000000000000 —

1111011100001 автопредприятие, безотрадная, ...

1111011100010 превратный, анапестоидный, ...

1111011100011 сориентироваться, беспрепятственный, ...

1111111111111 высокоразрешающих, ...

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

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

Рисунок 2.5 - Хеширование по сигнатуре при равновероятностном подходе с последовательным распределением символов языкового алфавита Значение индекса хеша не изменится при удалении одного символа (в запросе пропущена буква при вводе слова), когда в терме присутствуют другие символы, принадлежащие той же группе алфавита, в противном случае бит, соответствующий данной группе, изменит свое значение на "0". Аналогичные преобразования индекса хеша могут произойти при вставке символа в слове запроса.

Другая ситуация возникает при замене символов в слове запроса (например, при наборе слова запроса возникла опечатка), в этом случае индекс хеша может остаться неизменным, когда символы принадлежат к одной группе, либо может измениться в 1 или 2 позициях:

^ в первом случае замененный символ относится к группе, в которой ещё есть символы из запроса (значение бита остается неизменным - "1"), а замещающий символ попадает в ту группу, символы которой не встречаются в запросе (значение бита изменяется в "1");

^ во втором случае замененный символ принадлежит к группе, в которой больше нет символов из запроса (значение бита изменится в "0"), а замещающий символ попадает в ту группу, символы которой не встречаются в запросе (значение бита изменится в "1").

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

ошибках: О||Н\к • п / 2Н |.

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

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

• применение подхода с равновероятным появлением символов алфавита и распределение этих символов по группам необоснованно при формировании индексов сигнатур. Очевидным является тот факт (рисунок 2.5), что например, битопозиция, соответствующая редко встречающимся символам «Щ» и «Ъ», в большинстве индексов хешей будет принимать значение «0», а значит, хранение такого бита нецелесообразно;

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

• в процессе сравнения индексов образа (хранимый в базе индекс терма) и запроса такой подход дает большое количество совпадений для различных термов;

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

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

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

термов

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

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

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

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

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

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

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

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

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

[45].

Таблица 2.3 - Частотность употребления символов в русском языке

3 3 3

№ п/п Буква ф >4 Н и о К н о н и а р № п/п Буква ф >4 Н и о К н о н и а р № п/п Буква ф >4 Н и о К н о н и а р

1 о 0,10983 12 м 0,03203 23 й 0,01208

2 е, ё 0,08496 13 д 0,02977 24 х 0,00966

3 а 0,07998 14 п 0,02804 25 ж 0,0094

4 и 0,07367 15 у 0,02615 26 ш 0,00718

5 н 0,067 16 я 0,02001 27 ю 0,00639

6 т 0,06318 17 ы 0,01898 28 ц 0,00486

7 с 0,05473 18 ь 0,01735 29 щ 0,00361

8 р 0,04746 19 г 0,01687 30 э 0,00331

9 в 0,04533 20 з 0,01641 31 ф 0,00267

10 л 0,04343 21 б 0,01592 32 ъ 0,00037

11 к 0,03486 22 ч 0,0145

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

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

Таблица 2.4 - Неравновероятный подход появления символов алфавита

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

Бит 1 2 3 4 5 6 7 8 —

Рк 5 4 2 2 5 с^ 4 00 4 с^ 16 5 с^ 5 4 с^ 00 15 с^ 2 14 с^ 2 15 с^ 32 8 ЕЕ Рк="1 /=1 к=1

о о о о о о о о

В таблице 2.4 рк - сумма вероятностей по ьму символу и к-ой группе символов.

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

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

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

Сумма вероятностей по группе (равновероятностный подход)

0,25 0,2 0,15 0,1 0,05 0

а в е б г ж

д

з и й

к л

м н о

п р

с т

у

1 1_

1 1

а и ■ ■а. 1.1

□ II 1 1 ^ ^ ^

ф ц щ

х ч ъ ш

ы ь

э

ю я

Рисунок 2.6 - Диаграмма распределения вероятностей появления символа в группе при равновероятностном подходе

Сумма вероятностей по группе (неравновероятностный подход)

0,15

0,1

0,05

ИИ!!!!

-тг-1-1-1-1-1-1-1-г

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

0

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

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

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

ЙД К ПЛ У МВ Ф ШЮЧХЫ Я Б ЪЭЩЖ Ц ГЬЗ

Рисунок 2.8 - Хеширование с учетом неравновероятного появления символов

алфавита в термах

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

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

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

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

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

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

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

термов

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

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

В качестве одного из возможных решений предлагается построение конечного автомата, но он не позволяет реализовать задачу низкорелевантного («мягкого») поиска [28].

Также существуют методы побитового исключающего "ИЛИ", побитового "И", "ИЛИ", "НЕ", но все они основаны на принципе точного соответствия и низкорелевантный поиск также не реализуют [65].

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

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

Как уже было показано ранее, уменьшение размера индекса сигнатуры до однобайтового формата может привести к ситуации, когда несколько термов -некоторый кластер (подмассив от общего количества термов), выделенный в процессе анализа документов всей коллекции информационного массива, -соответствуют одной сигнатуре [84].

Значение хеш-функции Н() при безошибочном запросе, является

ключом к тому кластеру (подмассиву) индексов термов, которые соответствуют одному индексу сигнатуры sign( wJ). В случае если индексу сигнатуры sign( ^)

соответствует один терм, то он удовлетворяет задаче поиска и решение задачи сравнения индексов не требуется. Когда же кластер термов содержит более одного элемента (в литературе употребляют термин "коллизия"), то уже тогда возникает необходимость решения задачи обработки индексов термов образов (хранимый в базе индекс терма, выделенного в процессе анализа всей коллекции документов локальной базы данных) кластера на предмет соответствия индексу терма из запроса [84].

Задача низкорелевантного поиска основана на предположении о возможном допущении ошибок (пропуск буквы или набор лишней, замена символов, перестановка их местами и т.п.) в запросе. Перестановка букв в терме, как было

показано в пункте 2.4.2, не приводит к изменению хеш-индекса сигнатуры. Но при возможном допущении одной ошибки возможны следующие гипотезы [84]:

• изменения индекса хеша не произошло (в запросе ещё есть символы алфавита из данной группы), что не привело к изменению сигнатуры и по ключу Н (щ) найден кластер, в котором один терм образа - соответствие установлено;

• изменения индекса хеша не произошло, что не привело к изменению сигнатуры, и по ключу Н(щ) найден кластер, в котором несколько термов

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

• произошло изменение одного бита индекса сигнатуры и ключу Н (щ)

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

• произошло изменение одного бита индекса сигнатуры, но алгоритм "не понимает", что совершена ошибка, и вычисленному сигнатурному ключу Н (wj) находится соответствие - кластер, в котором нет термов, соответствующих

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

• произошло изменение одного бита индекса сигнатуры, но алгоритм "не понимает", что совершена ошибка, и вычисленному сигнатурному ключу Н (щ) находится соответствие - кластер, в котором есть термы, соответствующие запросу, с учетом того, что возможно изменение в одном бите индекса терма запроса; в этом случае нужно просмотреть кластер индексов на соответствие запросу.

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

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

Отметим, что индексы при хешировании по сигнатуре и индексы термов в кластерах - это не одинаковые индексы. Индексы термов в кластерах имеют 2-байтовый формат сигнатуры (таблица 2.5).

Таблица 2.5 - Формат сигнатуры термов в кластере

Значение хеш-функции Сигнатура терма (2-байтовый формат) Терм Инвертированный индекс терма

Н (^) 110001011...11101 x

110001011...11011 у

101011000...11011 z

В таблице 2.5 N N N - номера документов, в которых встречаются соответственно термы x, у и z.

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

Любая задача дискретной оптимизации заключается в нахождении экстремума функции, заданной на дискретном множестве точек. Если область определения функции состоит из небольшого конечного числа точек, то такую задачу можно решить методами перебора всего этого множества. Но на практике, даже в случае конечного числа точек, множество допустимых значений функции, которое чаще всего бывает очень велико, методы перебора неэффективны. Для решения задачи дискретной оптимизации применяют эвристические методы, основанные на методе ветвей и границ [58].

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

(допущение ошибки в запросе, которая привела к изменению индекса) индекса терма запроса.

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

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

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

Ключ Н (щ), полученный по модифицированному методу хеширования по

сигнатуре, обращает поисковый алгоритм к кластеру (рисунок 2.9), содержащему р индексов образов термов, или же возникает задача сравнения всех индексов массива образов термов, выделенных в процессе анализа [84].

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

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

Рисунок 2.9 - Обращение по ключу Н (щ) к кластеру индексов термов

Приведем реализацию целевой функции применительно к задаче низкорелевантного поиска и поясним суть ее применения. Целевая функция [84]

f (х) =

m

m

X х -Х х

/=1

/=1

< 1

xeD

(2.8)

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

ГА Л

37 3-у

X *Ук " X

D:

¿к Х ¿к к=3 - у-2 к=3 - у -2

у к<т к<т у

< 1, ] = 1, л

(2.9)

х е{0,1>.

В формулах (2.8) и (2.9) т - размер индекса терма запроса и образа в базе, «=&у(т, 3)+1 - количество выделенных непересекающихся троек (триад) бит в

индексе (+1 в случае не кратного трем числа бит в индексе), х и хг' - значение /го бита в индексах терма запроса и образа, у - номер битовой триады в индексе, к - позиция в триаде [84].

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

Суть предлагаемого метода [84]. Поскольку задача низкорелевантного поиска решается с допущением о том, что возможно изменение в одном бите, то ограничения меньше единицы показывают, что разность сумм индексов не должна превышать этого порогового значения. Но поскольку размеры индексов термов могут быть большими (для задачи качественного поиска), то вычислять разницу сумм для каждой пары индексов запроса и образа нерационально. По всем т позициям временные и, главное, вычислительные затраты будут значительными.

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

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

В качестве оценок на условие ограничения на множестве D были выбраны триады по двум основаниям:

1) при использовании двух бит для ограничения условие бы не выполнялось только в 2 случаях из возможных 16: при сравнении «00-11» и «1100». Это дает вероятность невыполнения условия, равную 0,125 на каждую двойку, следовательно, происходит большее количество сравнений, что ведет к увеличению вычислительных затрат;

2) при ограничении в 4 и более бит вероятность невыполнения условия растет уже заметно медленнее и, например, для 4 бит сравнения составляет -0,29

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

По произведенной оценке оптимальное значение на невыполнение условия по вероятностным (-0,22 на тройку) и вычислительным характеристикам достигается для ограничения триадами.

Приведем иллюстрацию, поясняющую работу метода на примере рисунка 2.10 с произвольными индексами терма образа в базе и запроса пользователя.

к=1

к~4

к=7

1 0 1 1 1 1 1 0 1 ... ...

м ]=2

0 0 1 1 0 0 1 0 0 ... ...

Индекс запроса

Индекс образа

Рисунок 2.10 - Сравнение индексных последовательностей запроса и образа

триадами

На рисунке 2.10 видно, что, например, для первой триады (/=1) условия по

3 3

ограничению выполняются: ^ хк х'к< 1, а для второй тройки (/=2) уже нет:

к=1 к=1

6 6

^ хк - ^ х'к> 1 . В этом случае осуществляется переход к следующей ветви

к=4 к=4

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

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

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

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

В ходе проводимых исследований был сделан акцент на учет особенностей поиска текстовых документов в слабо структурированных информационных массивах, а именно:

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

• предметная ориентированность таких информационных массивов;

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

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

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

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

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

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

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

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

3 ПРОЦЕДУРНАЯ МОДЕЛЬ ПОИСКА ТЕКСТОВЫХ ДОКУМЕНТОВ В СЛАБО СТРУКТУРИРОВАННЫХ ИНФОРМАЦИОННЫХ МАССИВАХ.

ОЦЕНКА КАЧЕСТВА ПОИСКА

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

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

Главной целью при распределении весов термов в векторной модели поиска является возможность оценить соответствие между термом запроса t и документом d, основываясь на весе конкретного терма t в документе d [47]. Но такое представление документа характеризует его лишь с позиции его содержания (атрибут description в модели DC) и не учитывает наличие других важных атрибутов документа.

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

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

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

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

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

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

пространства

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

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

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

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

Для устранения указанного недостатка обычно для пары документов и с/1+\

вычисляют косинусную меру сходства между векторами di и с/!+], описывающими документ в векторном пространстве [48]:

sim(di, dt+1) =

d

d

i+i

(3.1)

Видим, что косинусная мера сходства векторов di и с/!+] есть отношение их скалярного произведения к произведению евклидовых норм этих векторов.

В процессе лингвостатистического анализа документов было выделено т

/ - - \ т

термов (выражение (2.4)), тогда Аналогично, полагая, что

7=1

векторы di и di+l /и-координатные, находим их евклидовы нормы в виде:

d.

V

2Ж)-

j=1

(3.2)

Выражение (3.2) в формуле (3.1) нормирует векторы й? и с/!+] по длине так, чтобы их длины стали равны единице:

d,

di Л 4+1

— И d;+1 - —^

d.

d,

i+i

(3.3)

С учетом нормировки (3.3) выражение (3.1) можно представить в виде [46]:

sim{dt,dt+x) = {&t,Àt+ï). (3.4)

Фактически, выражение (3.4) - скалярное произведение нормированных векторов, соответствующих документам i и i+1.

Условно модель векторного пространства по трем термам зоны description можно проиллюстрировать в виде рисунка 3.1.

Рисунок 3.1 - Условное представление документов по трем термам в векторном

пространстве

На рисунке 3.1 условно обозначены три вектора с!1 , ¿/2 и ¿/3 , которые описывают соответствующие документы термами /2 и Ь,. Углы а, (3 и у для вектора с12 показывают зависимость этого вектора от перечисленных термов, т.е. характеризуют его меру отклонения в пространстве в зависимости от весов термов ¿1, ¿2 и Н- Очевидно, что чем ближе вектор к одному из термов, тем больший вес данный терм имеет в документе. Угол 0 между векторами и с12 характеризует меру сходства документов по указанным трём термам.

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

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

Когда пользовательский запрос не ограничивается лишь поиском по описанию документа или по запросу не найдено документов, то задается ещё и

t

2

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

Зоны представляют собой поля, содержанием которых является произвольный текст. Отличие зон от полей состоит в том, что последние могут иметь относительно небольшое количество значений, а зона же содержит произвольный и неограниченный объем текста [47].

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

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

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

Таблица 3.1 - Зонное индексирование

Создание инвертированного индекса

Зона Номер документа 1 ... i ... j ... k ...

Заголовок (headline) r — — Hir — Hjr — Hkr —

s — — His — Hjs — Hks —

l — — Hil — Hjl — Hkl —

Автор (author) — — Aia — Aja — Aka —

Описание (description) x — — NiX — Njx — Nkx —

y — — Niy — Njy — Nky —

Создание инвертированного индекса

z — — Niz — Njz — Nkz —

Формат (format) — — Fif — Fjf — Fkf —

Дата (time) — — Tit — Tjt — Tjt —

В таблице 3.1 введены следующие обозначения [88]:

• h е H - множество термов в названиях документов. Организуется в виде словаря, в котором содержатся все термы, выделенные из названий документов коллекции;

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

• ke N - множество термов, выделенных в процессе анализа коллекции документов;

• t е T - множество временных интервалов, отражающих работу над документом;

• fe F - множество форматов представления документа. Организуется в виде словаря с возможными форматами создания документов.

Поясним на примере документа i образование индекса. Наличие H^, His, Н означает, что в заголовке документа под номером i в базе содержатся слова под номерами r, s, и l из словаря, содержащего все возможные слова в заголовках документов. Aia означает, что автором документа является разработчик/подразделение под номером а в словаре авторов/подразделений в i-м документе. Наличие Nix, Niy, Niz говорит о том, что в содержательной части документа i содержатся термы x, y и z, выделенные в процессе лингвостатистического анализа текста. Документ i имеет формат под номером f в словаре форматов, о чем говорит наличие Fif. И, наконец, Tit задает временной интервал, в течение которого документ мог быть создан/отредактирован [88].

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

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

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

Для удобства ранжирования документов в выдаче каждой зоне в итоговом векторе, описывающей документ, приписывается вес ^, ^ е[0.1] такой, что [82]

I

£ 8к = 1, (3.5)

к=1

где 1 й к й I. В этом случае через sk обозначается булева величина, означающая соответствие или отсутствие между запросом и к-й позицией вектора, описывающего документ.

Отображение принадлежности того или иного атрибута запроса соответствующей позиции вектора может осуществлять любая функция, принимающая значение, равное «1», если атрибут запроса присутствует в данной позиции, и «0» - если нет [47]. Таким образом, взвешенную попозиционную релевантность можно представить в виде [47, 82]:

I

М= £(gk ■ ). (3.6)

к=1

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

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

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

С учетом введенных обозначений (3.5) и (3.6) условно модернизированная модель атрибутов «Дублинское ядро», посредством применения метода попозиционного взвешивания графически может быть представлена в виде рисунка 3.2.

Веса между атрибутами распределяются таким образом, что их сумма равна «1». При этом следует обратить внимание на то обстоятельство, что такой атрибут, как Description, уже содержит внутренние веса, учитывающие частоту встречаемости терма в пределах одного документа и всей коллекции документов в

целом. При этом необходимо установить диапазон значений, в пределах которых может изменяться вес этого атрибута. Важно, чтобы он не выходил за границы диапазона [0.1] и задача ранжирования была осуществима [82]. Было показано, что величина g3 не может принимать значение, превышающее «1», и что чаще всего ^ <1. Величина wJ■i не является бинарной и изменяется также в диапазоне [0.1], это следует из оценки формулы, по которой она определяется:

^ = I (г,) • I (р)

I (г]Р) = 1ов

V Р1

р = 1,1-

(3.7)

но на практике р<<1. В формуле (3.7) I(г7) - частота термина ^ в документе I(г]р) - обратная документальная частота для термина г в коллекции документов

С, содержащей В документов, а dpJ - количество документов в коллекции С, содержащих термин г . При этом выполняется условие dp&В.

Рисунок 3.2 - Модернизированная модель метаданных «Дублинское ядро» Оценивая величину I (г7), можно сказать, что ее значение не превышает

п.

«1», поскольку определяется из соотношения 0 < I(г ) = -*- < 1 или, что точнее

п

р

<

п

0<Д^) = ^«1, (3.8)

пр

где п - число, равное количеству упоминаний термина ^ в документе а п^ -общее количество выделенных термов в документе ^. Величина

f (tp ) = log

К dp'J

^1, (3.9)

поскольку разрешающая способность, ограничивающая пространство терминов согласно закону Ципфа [85], определена таким образом, что величина dpj сравнима с D и отличается от неё порядка 10 раз. Если порядок сравнения величин dpj и D отличается от указанного, то термы выходят за пределы разрешающей способности и в анализе не участвуют.

Таким образом, оценка веса Wjt в выражении (3.7) с учетом (3.8) и (3.9) имеет вид 0 ^ wjt ^ 1. Тогда g3 • Wj<< 1.

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

Ранее, в пункте 2.2.5 было получено векторное представление документов с позиции только одного атрибута - description, формально описанное выражением (2.4).

Сопоставляя результаты, полученные в п. 2.2.5 и в процессе применения метода попозиционного взвешивания к модели атрибутов «Дублинское ядро», можно условно описать векторное пространство, характеризующее коллекцию документов информационного массива в виде [82] :

L^iKg^gaJ^g^f^g^t^g^), (3.10)

где А. - множество слов в заголовках /-го документа с весом gn ; а. - автор или структурное подразделение, выпустившее /-й документ с весовым коэффициентом gj2 ; d. - вектор, потермально описывающий содержание /-го

документа с весом g;3; f - формат /-го документа с весом gi4; t. - дата создания или последнего редактирования j-го документа с весом gi5.

Если вектор di в выражении (3.10) заменить выражением (2.4), в котором каждый вектор нормирован по длине, а зону headline представить в виде множества слов заголовков документов, выделенных при анализе коллекции, то результирующий вектор будет иметь вид:

А-=.сз.и)

В выражении (3.11) предполагается, что в процессе анализа коллекции документов было выделено к различных слов в заголовках и m термов по результатам частотного анализа текстов.

Таким образом, исходная векторная модель (2.4), которая представляла лишь содержание документа и имела размерность m - количества термов, выделенных в процессе лингвостатистического анализа, - пространства, была расширена за счет добавления в нее дополнительных атрибутов. Поскольку в словаре возможных слов из заголовков документов содержится к позиций, то размерность пространства векторной модели увеличится с m до «m+k+З».

Представление документа в виде вектора (3.11) в условиях предметно-ориентированного поиска обладает рядом преимуществ:

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

• когда некоторые атрибуты документа утрачены или неизвестны, то и в этом случае документ может быть найден по известным компонентам вектора (зонам), что обусловлено гибкостью модели, т.е. возможностью варьирования количеством компонент вектора запроса;

• при ранжировании возможно учитывать только те атрибуты компонент векторов, которые совпали в запросе пользователя и в описании

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

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

Векторное представление документа с дополнительным набором атрибутов одновременно увеличивает и размерность векторного пространства. Так, с учетом ввода четырех дополнительных атрибутов размерность пространства увеличится с «т» - количества термов, выделенных в процессе обработки и частотного анализа текста, до «т+к+3». Это оказывает незначительное влияние на процесс построения вектора, поскольку словарь, содержащий слова из заголовков документов, имеет размерность к<<т размерности словаря термов, выделенных в процессе частотного анализа. Аналогичное заключение можно сделать относительно осуществления процесса ранжирования документов в выдаче по запросу пользователя. Но, учитывая указанные недостатки, можно сказать, что эффективность и качество поиска возрастают.

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

А = причем размерность, а значит и сложность

вычислений значительно сокращаются по сравнению с обычной векторной моделью (т<<п, где п - размерность стандартной векторной модели, не предполагающей предметно-ориентированного поиска) [82].

В итоге размерность каждого вектора для любого документа в базе равна у=т+к+3. Сокращение вычислительной сложности достигается за счёт применения предварительного частотного анализа текста с применением словарей предметной области. Произведенная оценка увеличения вычислительных затрат

показала, что за счет предварительной кластеризации (сортировки термов) сложность поиска по атрибуту description составляет O(log(m)) - бинарный поиск, а для остальных атрибутов (учет k дополнительных измерений атрибута headline и по одному измерению для атрибутов author, time, format) является линейной со сложностью O(k+3) [88]. Но поскольку m>>(k+3), то сложность поиска расширенной (зонной) векторной модели можно оценить как O(log(v)), что меньше сложности алгоритма стандартной векторной модели O(n).

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

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

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

значение релевантности, равное скалярному произведению (q, [47].

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

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

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

(ц, 4)

соБ(р = ясоге(с[, = --=г-. (3.12)

4

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

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

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

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

т>>к+3, не происходит существенного увеличения размерности векторного пространства.

Условно изобразим в пространстве трех термов и, и (рисунок 3.3) вектор (¡- вектор-запрос пользователя, - вектор, описывающий документ и

¿12 - вектор, описывающий документ ¿/2 коллекции, содержащей В документов. Поскольку для вычисления подобия векторов используется косинусная метрика, то чем меньше угол (р1 , тем больше соответствие документа запросу.

Расположение векторов с!1 и ¿/2 в пространстве термов и Ь характеризует

частотную зависимость документов й\ и й2 от указанных термов [69].

/

/

/

/

/ . а

* 2

Рисунок 3.3 - Векторы запроса с] и документов , ¿12 по трем координатам

t2 и tз

Из рисунка видно, то документ ^ больше соответствует запросу д, поскольку угол (рх<ф2, а следовательно, косинусная его мера больше. Также видно, что и в документе , и в документе встречаются все три терма 1\, 12 и но частотные характеристики встречаемости этих термов в документе с!\ выше и

корреляция между векторами запроса д и документа больше. Это означает, что

документ d1 более релевантен запросу q и при сортировке в выдаче должен находиться на более высокой позиции по отношению к документу d2.

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

Анализируя имеющуюся документальную коллекцию информационного массива и запрос пользователя к нему, на выходе получают векторное представление каждого документа ¿/г коллекции и векторное представление запроса пользователя (¡.

Для решения задачи ранжирования требуется вычислить косинусную меру соответствия векторов ¿/г и ц (3.13), а также задать некоторое положительное число K, которое определяет количество документов коллекции с наибольшими значениями релевантности (косинусной меры):

Задача ранжирования заключается в сортировке этих K документов в порядке убывания релевантности. Отмечается [47], что для большинства поисковых систем определяют K=10.

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

Алгоритм ранжирования на основе косинусной меры соответствия:

1 float scores [N]=0;

2 инициализация Lenght[N];

3 for each зоны запроса l // для каждой зоны запроса;

4 do вычислить gkq и извлечь инвертированный список для зоны l;

5 for each пары (d, gk,d) в инвертированном списке;

6 do scores[d] += gk,dx gk,q;

7 прочитать массив Lenght[N];

qi g di

(3.13)

8 for each d;

9 do scores[d]= scores[d]/ Lenght[d];

10 return наибольшие K компонентов массива scores[].

Массив Lenght включает коэффициенты нормировки (длины) векторов, полученных для каждого из N документов коллекции, а массив scores содержит релевантность каждого их этих документов.

На третьем этапе начинается цикл, который обновляет массив scores, просматривая поочередно каждую зону. Четвертый этап определяет вычисление веса зоны / в векторе q . На этапах 5-7 происходит обновление релевантности каждого документа путем прибавления вклада зоны l. Этот процесс накопления вкладов или суммирования (аккумулирования) вкладов от каждой зоны по очереди называют ранжированием по атрибутам (зонам).