Сравнительный обзор методов поиска информации в базе знаний

Размещено на http://www.allbest.ru/

Сравнительный обзор методов поиска информации в базе знаний

Галиуллина Н.А., студент магистратуры кафедры информатики и

прикладной математики ФГБОУ ВО «Казанский национальный исследовательский

технологический университет» Россия, г. Казань

Аннотация

В рамках данной исследовательской работы была поднята актуальная тема оптимизации запросов к базе данных. Исследование было проведено с использованием программного продукта - базы знаний, внедренной в корпоративный мессенджер. Термин “оптимизация” связан с проведением работ по усовершенствованию чего-либо. В контексте данной задачи мы преследовали цели максимизации точности поиска и минимизации времени поиска. Цели исследования считали выполненными при следующих условиях:

• точность поиска увеличилась;

• время поиска уменьшилось или не изменилось.

В процессе исследования использовали следующие методы:

• полное сканирование базы - при поиске инструкций по разделами и ключевым словам;

• сканирование по полнотекстовому индексу - при поиске инструкций по заголовку;

• отбор при соответствии смысловых векторов - при усовершенствованном поиске инструкций по заголовку.

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

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

(вставка/изменение/удаление), увеличивается размер БД, поэтому к добавлению индексов следует относиться осторожно.

Некоторые общие принципы, связанные с созданием индексов:

• индексы необходимо создавать для столбцов, которые используются в джойнах, по которым часто производится поиск и операции сортировки. При этом необходимо учесть, что индексы всегда автоматически создаются для столбцов, на которые накладывается ограничение primarykey. Чаще всего они создаются и для столбцов с foreignkey(в Access- автоматически);

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

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

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

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

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

Fulltextindex- полнотекстовый специализированный индекс, для больших объемов текстовых данных, которые хранятся в столбцах строкового типа VARCHAR, TEXT. Для относительно небольших типов данных используется обычный индекс.

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

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

Следует рассмотреть положительные и отрицательные характеристики.

Плюсы:

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

• Нет необходимости устанавливать дополнительное программное обеспечение.

• Поиск по готовому индексу проходит достаточно быстро.

• Простота и точность.

Минусы:

• Необходимо содержать дополнительное поле.

• Потери производительности при вставке и обновлении записей будут довольно ощутимыми.

• Дополнительная нагрузка на сервер

• Несколько дополнительных объектов в схеме

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

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

На рисунке 1 показан пример поиска по разделу, здесь: 1 - номер шаблона для поиска, “Установка программных компонентов” - название раздела. В примере видно, что метод поиска напрямую чувствителен к регистру и совершенно не подходит для решения задачи поиска в базе знаний.

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

• регистр не имеет значения;

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

На рисунке 2 показаны эксперименты с поиском инструкций по заголовку, здесь: 3 - номер шаблона, “инструкция” - слово, встречающееся в заголовке.

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

Рисунок 3. Пример поиска по заголовку в другом падеже

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

Реализуем данный алгоритм следующим образом:

1. разделим запрос на слова;

2. найдем вектора каждого слова;

3. определим вектор выражения;

4. перебором по матрице заголовков инструкций найдем косинусное сходство между каждым из заголовков и входным запросом;

5. найдем самые близкие по смыслу к входному запросу заголовки;

6. сформулируем результат поиска.

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

представленным выше.

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

На рисунке 4 изображен результат работы word2ve^ по запросу “установка программных компонентов” нашлись самые подходящие по смыслу инструкции. Среди достоинств можно отметить:

• независимость от регистра введенного запроса;

• поиск инструкций по смыслу;

• быстрота поиска;

Рисунок 4. Результат поиска с использованием word2vec

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

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

Использованные источники

1. Воройский Ф. Информатика. Новый систематизированный толковый словарь.3-е изд., перераб. и доп. -- М.: ФИЗМАТЛИТ, 2003. -- 760 c.

2. Лесковец Ю., Раджараман А., Ульман Д.Д. Анализ больших наборов данныхМ.: ДМК Пресс, 2016. -- 488 c.

3. Бабкин А.В. и др. Формирование цифровой информатики в России: сущность, особенности, техническая нормализация, проблемы развития -- Научнотехнические ведомости Санкт-Петербургского государственного политехнического университета, 2017. -- Т. 10. -- №. 3

4. Matthias Jarke, Jurgen Koch. Query Optimization in Database Systems. Computing Surveys, Vol. 16, No. 2, June 1984

5. Кузнецов С., “Методы оптимизации выполнения запросов в реляционных СУБД” // Центр Информационных Технологий [Электронный ресурс]. URL: http://citforum.ru/database/articles/art 26.shtml (дата обращения: 29.06.2021).

6. Chaudhuri, S., Shim K. Optimization of Queries with User-Defined Predicates. In Proc. of VLDB, Mumbai, 1996.

7. Избачков, Ю.С. Информационные системы. учебник / Ю.С. Избачков, В.Н. Петров // СПб.: Питер, 2008. -- 656 c.

Размещено на Allbest.ru