E-mail:
Пароль:
Забыли пароль?

Полнотекстовый поиск в системе Беpатоp

«Программная инженерия», № 04, 2013 г.

Константин Селезнёв

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

Постановка задачи

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

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

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

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

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

Морфологический анализ

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

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

Указанную идею трудно реализовать в чистом виде, поскольку словарь общеупотребимых слов содержит более 8 миллионов значений. Это обстоятельство приводит к тому, что файл словаря становится слишком большим, и работа с ним может быть затруднена на некоторых типах мобильных устройств. В этой связи было принято решение разделить словарь общеупотребимых слов на 33 части, каждая из которых содержит все слова на одну и ту же букву: первая – на букву «а», вторая – на букву «б» и так далее. Считается, что буквы «ь», «ъ» и «ы» не могут быть первыми в слове, и потому получилось 30, а не 33 файлов словаря.

Далее было использовано одно очень важное свойство русского языка: в большинстве случаев все словоформы одного слова имеют общий префикс-основу и различаются только окончаниями. Благодаря этому свойству все формы одного и того же слова в большинстве случаев окажутся внутри одного и того же из 30 файлов. Слова-исключения, у которых формы не имеют общего префикса, были вынесены в отдельный файл, и, таким образом, число файлов стало равно 31. Наконец, было решено, что термины потенциально тоже могут изменяться и иметь различные морфологические формы без общего префикса-основы. Таким образом, общее количество словарей системы стало равно 32.

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

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

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

Полнотекстовый индекс

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

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

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

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

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

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

Таким образом, алгоритм полнотекстового поиска состоит их следующих шагов.

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

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

Поисковые подсказки

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

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

Технические характеристики

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

Файл для буквы Размер,байт Файл для буквы Размер,байт
а 241813 р 806832
б 346578 с 1050213
в 1004945 т 335603
г 254746 у 483321
д 520474 ф 150444
е 54094 х 127585
_ 32784 ц 80678
ж 87787 ч 120334
з 810581 ш 165019
и 411417 щ 56220
й 34529 ы 32795
к 539392 э 120470
л 189200 ю 40646
м 355248 я 55502
н 784981 Безосновные слова 32880
о 1274815 Словарь терминов 34223
п 2676977  
 

В сумме все указанные файлы занимают чуть меньше 13 Мб. Это небольшой объём даже по меркам мобильных устройств, что позволяет все словари морфологического анализа загрузить в память сразу же после запуска системы.

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

Файл для буквы Размер, байт Файл для буквы Размер, байт
а 22136 п 189631
б 31433 р 64186
в 70783 с 110624
г 20402 т 35674
д 65236 у 43210
е 5155 ф 19393
_ 16 х 5554
ж 4158 ц 5711
з 38415 ч 12451
и 36440 ш 3809
й 160 щ 137
к 43437 ы 16
л 13646 э 15364
м 34829 ю 880
н 79405 я 4899
о 101432 Остальные слова 5398

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

Архитектура и реализация

Рассматриваемая подсистема полнотекстового поиска имеет распределённую архитектуру и состоит из серверной и клиентской частей.

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

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

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

Заключение

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


Возврат к списку

ѕрокрутить вверх