Как стать автором
Обновить
54.94
Naumen
Мечтай. Создавай. Меняй мир к лучшему

Как мы ищем документы в Naumen Disk или еще один вариант организации FTS

Время на прочтение 14 мин
Количество просмотров 3.1K

Вступление

Меня зовут Агапов Андрей. В компании Naumen я работаю более 2 лет, из них полтора года занимаюсь продуктом Naumen Disk. На мне архитектура продукта, разработка функций системы и программирование на backend. Naumen Disk позволяет хранить, структурировать и искать документы, а также совместно работать над ними. Более подробно о решении можно почитать тут.

Одна из задач продукта Naumen Disk (далее ND) — обеспечить поиск по содержимому загружаемых файлов. Файлы в основном представляют собой документацию в различных форматах, в том числе без содержания текстового слоя (например, сканы). В статье я опишу процесс решения задачи по полнотекстовому поиску в таких документах: из каких вариантов мы выбирали и на чем в итоге остановились.

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

  1. Выполнять полнотекстовый поиск (т. е. с учетом различных видов словоформ) по загруженным документам.

  2. Выполнять сортировку результатов по релевантности.

  3. Подсказывать и исправлять опечатки в поисковой фразе пользователя.

  4. В результатах поиска строить сниппет (фрагмент текста с искомыми словами).

Забегая вперед скажу, мы стремились к вот такому решению для пользователя и в итоге реализовали его:

Какие варианты мы рассматривали

В итоге данную задачу решили с использованием СУБД PostgreSQL (как системы хранения данных) и возможностей NLP (Natural Language Processing) в Python. Но мы, конечно, рассматривали существующие движки Full Text Search (далее FTS), сделав упор на:

  • ElasticSearch;

  • PostgreSQL FTS.

Оба варианта вполне могли удовлетворить наши потребности с некоторыми нюансами. Кратко о них.

ElasticSearch

ElasticSearch — отличный масштабируемый движок для FTS. Однако у нас вся информация о загружаемых документах и прочих сущностях хранится в реляционной БД PostgreSQL. Использование ES привело бы к дублированию части информации и необходимости синхронизации, а также обслуживанию еще одного компонента системы. Кроме того, собственный опыт показывал достаточно большие аппетиты ES к серверным ресурсам. Для наших задач и планируемых серверных требований под продукт это могло бы стать проблемой.

PostgreSQL FTS

В рамках RND мы полностью прошли путь по решению задачи желаемого полнотекстового поиска на FTS движке СУБД PostgreSQL (13,4). Причем тестировались как на GIN индексах, так и на расширении для RUM индексов, который, действительно, сильно ускоряет получение результатов. Но есть ряд моментов, которые нас смутили:

1. Ограничения длины текста для построения tsvector (1 мегабайт), с помощью которого осуществляется полнотекстовый поиск (см. документацию). У нас могут быть достаточно большие тексты, которые не укладываются в него, а цель — искать во всём содержимом документа. При работе с тестовыми примерами достаточно часто получали ошибку на превышение максимальной длины.

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

3. В интерфейсе нам нужен был сниппет. Для этого в PostgreSQL FTS используется функция ts_headline. Мы столкнулись с тем, что функция не всегда возвращает текст для сниппета. Подобрать конкретные значения параметров функции (MaxFragments, MaxWords) при которых ts_headline всегда будет возвращать корректный текст сниппета не удалось. По умолчанию она возвращает некоторое число символов из начала текста, если она не нашла искомый фрагмент. Достаточно часто именно такой результат мы и получали несмотря на то, что фрагмент в тексте присутствует. Сложилось впечатление, что нужно придумывать некий алгоритм динамической подстановки параметров в зависимости от каждого конкретного текста. Реализовывать же свою такого рода функцию — не самая тривиальная задача, если иметь только tsvector.

В итоге мы параллельно с этими исследованиями в рамках RND прошли путь по построению поискового движка на базе PostgreSQL (как системы хранения данных, без использования FTS) и с NLP возможностями Python по обработке текста.

Рассмотрим все этапы по порядку с акцентом на организации поиска.

Выделение текста из файла

Для старта поиска по тексту нам, естественно, надо этот текст выделить.

Для этих целей мы используем две библиотеки:

  • Apache Tika для документов, которые содержат текстовый слой.

  • Tesseract Ocr — для документов без текстового слоя (картинок, pdf без текстового слоя и т. п.).

Tesseract во время работы активно потребляет RAM, поэтому для ускорения мы разбиваем большие файлы (в частности многостраничные PDF) на страницы, а оцифровку выполняем батчами. Также мы контролируем разрешение картинок: уменьшаем их, если они превышают порог.

Токенизация и нормализация текста

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

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

Например, фраза:

«В случае возникновения у Клиента мотивированных претензий по соответствию оказанных услуг условиям Договора»

преобразуется в набор токенов в нижнем регистре:

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

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

Перейдем к реализации. Токенизация выполняется микросервисом, написанным на Python. Токенизацию мы производим на основе библиотеки NLTK. Библиотека широко применяется для задач обработки естественного языка и предоставляет множество полезных функций для обработки текстов, включая различные методы токенизации текста. Мы используем функцию word_tokenize, которая принимает на вход текст и возвращает набор токенов. Словарь стоп‑слов имеется в библиотеке NLTK, и им можно пользоваться для фильтрации, но он не достаточно полный, поэтому в данном случае мы применяем морфологический анализатор pymorphy2 для обработки полученных токенов — убираем с его помощью предлоги (PREP), союзы (CONJ), частицы (PRCL), междометия (INTJ). Для лемматизации токенов мы также работаем с pymorphy2.

Всё, что не подходит для добавления в поисковый индекс (is_term), будет отброшено в дальнейшем.

POS_EXCLUDE = ("PREP", "CONJ", "PRCL", "INTJ")
for token in word_tokenize(text):
   p = morph.parse(token)[0]
   pos = p.tag.POS or p.tag._POS
   is_term = pos not in POS_EXCLUDE
   normal_form = p.normal_form

Получаем для нашей фразы:

Токен

Часть речи (см. источник)

Нужно ли добавлять в поисковый индекс

Нормализованная форма

в

PREP

False

в

случае

NOUN

True

случай

возникновения

NOUN

True

возникновение

у

PREP

False

у

клиента

NOUN

True

клиент

мотивированных

ADJF

True

мотивированный

претензий

NOUN

True

претензия

по

PREP

False

по

соответствию

NOUN

True

соответствие

оказанных

PRTF

True

оказать

услуг

NOUN

True

услуга

условиям

NOUN

True

условие

договора

NOUN

True

договор

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

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

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

  1. Позиция начала и окончания токена в тексте.

  2. Позиция начала и окончания для отображения фрагмента текста в сниппете (три слова влево и три слова вправо).

  3. Term frequency слова — число повторений слова в документе к общему числу слов в документе.

Построение индекса, фильтрация и ранжирование документов

Сам «поисковый индекс» (токены с их характеристиками) мы храним в PostgreSQL в таблицах. Поиск выполняется через SQL‑запрос, который на вход получает набор токенов из поисковой фразы, введенной пользователем. Поисковая фраза разбивается на токены по тем же самым правилам, описанным выше. Для ранжирования документов по релевантности мы выбрали величину Term Frequency (TF) — отношение числа вхождений некоторого слова к общему числу слов в документе. За счет этого оценивается важность слова в пределах отдельного документа, а чтобы ранжировать документы между собой, достаточно сложить суммы всех TF по найденным в них токенам. Документ с самым большим суммарным значением TF будет располагаться выше остальных.

Например, есть два документа — Документ_1 и Документ_2. 

Документ_1 содержит 160 слов. Документ_2 — 183 слова. 

Ищем по слову «юрист». 

В Документ_1 оно встречается 5 раз, в Документ_2 — 7 раз. 

TF Документ_1 = 5/160 =0.031, 

TF Документ_2 = 7/183 = 0.038. 

Таким образом Документ_2 будет выше при ранжировании, чем Документ_1.

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

Вариант 1. Хранение токенов в простом виде в таблице.

Схема данных:

В этом случае поиск документов, а также ранжирование подходящих документов решались бы простым SQL‑запросом:

select *
from (select d.id_doc, d.nm_doc, sum(di.vl_frequency) vl_doc_frequency
      from doc d
      join doc_index di on di.id_doc = d.id_doc
      where di.nm_token in (<список токенов>)
      group by d.id_doc, d.nm_doc) t
order by t.vl_doc_frequency desc;

Думаю, понятно, почему данный вариант нельзя считать рабочим. При загрузке порядка 180 тыс. документов с текстовым слоем мы получили около 80 млн строк в таблице (сколько токенов):). Размер таблички ушел за 40 GB, хотя сами документы на диске занимают около 10 GB. Тем не менее сам SQL‑запрос прекрасно работал и выдавал результаты в пределах 1–2 сек. Оставлять так было нельзя: обслуживание таких объемов могло стать непростой задачей, да и обосновать такое «распухание» дискового пространства было бы сложно (превышение в десятки раз объема для хранения поискового индекса над общим размером файлов).

Вариант 2. Хранение токенов в JSONB-массиве на документе.

Чтобы значительно снизить объемы на хранение в сравнении с вариантом 1, можно было бы токены сохранить в виде JSON‑поля массива объектов, который описывает токен (фактически аналогичен структуре таблицы doc_index из варианта 1 выше) прямо в таблице документов.

Схема данных:

Где js_doc_terms

[
   {
      "frequency":0.1,
      "name":"случай",
      "positions":[
         [
            0,
            32,
            2,
            8
         ]
      ]
   },
   {
      "frequency":0.1,
      "name":"соответствие",
      "positions":[
         [
            33,
            108,
            71,
            83
         ]
      ]
   }
]

В таком варианте поиск документов с их ранжированием будет работать так:

select *
from (select d.id_doc, sum((j ->> 'frequency')::numeric) vl_doc_frequency
     from doc d
     cross join jsonb_array_elements(d.js_doc_terms) j
     where j ->> 'name' in (<список токенов>)
     group by d.id_doc) t
order by t.vl_doc_frequency desc;

Этот вариант значительно экономит место под хранение. Но основная проблема подхода — разворачивание больших JSON‑массивов. Функция jsonb_array_elements справляется с этим не лучшим образом и начинает серьезно деградировать по скорости. Еще, конечно, плохо, что по всем документам нужно разворачивать токены, чтобы понять, подходит ли нам документ. У этой проблемы есть решение (см. вариант 3), но в совокупности основную проблему (разворачивание JSON‑массивов) оно не решало.

Вариант 3. Хранение токенов с группировкой по первому символу в виде JSON-массива. 

Это вариант совмещения 1 и 2.

Нужно решить проблемы:

  1. Быстро отбирать документы по токенам (в пределах десятков миллисекунд) .

  2. По найденным документам оперативно получать  информацию о параметрах токенов, в частности по frequency, и выполнять их ранжирование.

  3. Не забыть про проблему «распухания» потребляемого места на диске (см. вариант 1).

Схема данных:

где doc.nm_terms — массив уникальных слов документа. По нему создаем GIN индекс с array_ops, что позволит выполнять фильтрацию документов максимально быстро.

Далее надо решить задачу ранжирования. Для этого нужна таблица doc_index, которая хранит информацию по токенам и их характеристикам в разрезе документа, но с группировкой по первому символу токена. Это дает возможность существенно сократить накладные расходы на разворачивание JSON-массива в SQL‑запросе — сами массивы JSON становятся значительно меньше. Кроме того вариант можно масштабировать в дальнейшем: хранить по двум, трем и т.д. символам токена. 

Ниже пример, как выглядят данные в таблице doc_index

В таком варианте поиск документов с их ранжированием будет работать так:

with cte_terms as
        (select term
         from unnest(array [<список токенов>]) term),
    cte_letters as
        (select distinct substring(term, 1, 1) vl_first_letter
         from cte_terms),
    cte_docs as
        (select d.id_doc, d.nm_doc
         from doc d
         where d.nm_terms @> array(select term from cte_terms))

select d.id_doc, d.nm_doc, sum((j ->> 'frequency')::float) vl_doc_frequency
from cte_docs d
        cross join cte_letters l
        join doc_index di on di.id_doc = d.id_doc and l.vl_first_letter = di.nm_term_part
        cross join jsonb_array_elements(di.js_doc_terms) j

where (j ->> 'name') in (select term from cte_terms)
group by d.id_doc, d.nm_doc
order by vl_doc_frequency desc

Документы фильтруются по переданным словам. Оператор включения одного массива в другой @> будет использовать созданный GIN индекс на поле nm_terms. За счет этого отбор документов произойдет за несколько десятков миллисекунд. Затем по каждому входному токену получаем список уникальных первых символов и по этим символам уже переходим (join) в doc_index на нужные токены, тем самым значительно облегчив работу jsonb_array_elements.

В отличие от варианта 1 мы колоссально экономим на занимаемом пространстве (даже с учетом некоторого дублирования токенов). 40 GB превратились в 8 GB. По мере роста данных узким местом варианта может стать сортировка. Если пользователь будет вводить очень частотные (часто встречаемые в документах) слова, то существенное время запроса станет уходить на group by и order by. Эту же проблему мы наблюдали и в PostgreSQL FTS с ts_rank функцией для ранжирования данных. Решение одно — на уровне cte_docs прописывать limit, подобрав подходящее число для защиты от частотных слов. 

В итоге на этом варианте мы и остановились на данный момент. Он позволит в случае деградации по скорости функции разворачивания массива JSON объектов (jsonb_array_elements) увеличить число символов для партицирования.

Скорость построения поискового индекса

Мы проводили тестирование, отправляя в обработку по 10 документов асинхронно (через asyncio). При этом брали достаточно большие по объему документы — ГОСТы из открытых источников. В MS Word в таких документах в среднем более 100 страниц текста.

Количество документов: 100.

Количество символов в документе: от 47 965 до 373 701, среднее значение 172 016. 

Время на формирование поискового индекса: 53 секунды.

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

Построение сниппета

Если иметь информацию о позиции слова в тексте, построить сниппет несложная задача. Напомню, что мы сразу при сохранении вычислили для слова позицию начала «минус три слова» и конца «плюс три слова» для сниппета. 

Например, при поиске по слову «информационные» для текста ниже:

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

Сниппет будет:

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

Мы «нарезаем» фрагменты текста для сниппета, учитывая, что:

  1. Фрагменты не должны пересекаться, если пересекаются — объединяем в один.

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

Подсказки по мере ввода

Любой поиск включает в себя подсказки пользователю на основе введенной фразы.

Они могут быть двух видов:

  1. подсказки, дополняющие ввод слова;

  2. подсказки следующего слова.

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

Словарь слов

Мы используем CountVectorizer из библиотеки sklearn, чтобы построить словарь совстречаемых слов со счетчиком их встречаемости в тексте документа.

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

cv = CountVectorizer(
max_features=nd_max_features, 
min_df=nd_min_df, 
stop_words=set(stopwords.words('russian')),
ngram_range=(1, 2)
)

cvdocs = cv.fit_transform(docs)
vocabcv = cv.get_feature_names()
counts = cvdocs.sum(axis=0).A1
freq_distribution = dict(zip(vocabcv, counts))

freq_distribution_counter = Counter()
freq_distribution_counter.update(freq_distribution)
bigram_tokens_dict = {}
unigram_tokens_dict = {}

for token, occurr_num in freq_distribution_counter.most_common():
   token_parts = token.split(" ")
   if len(token_parts) > 1:
       bigram_tokens_dict.setdefault(token_parts[0], []).append(token_parts[1])
   else:
       unigram_tokens_dict[token] = int(occurr_num)

Униграммы будут содержать слова с их счетчиками встречаемости в тексте:

{'значение': 562985, 'должны': 511503, 'российской': 183658, 'федерации': 180691, 'иметь': 113890, 'возможность': 96536, 'соответствовать': 49857, 'округа': 14449, 'городского': 13436, 'конституции': 46385}

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

{'городского': ['округа'], 'российской': ['федерации','конституции'],
'должны': ['иметь', 'соответствовать'],'иметь': ['значение', 'возможность'],}

В итоге на основе таких структур всё сохраняем в реляционную таблицу вида:

Подсказки

Чтобы по такой таблице построить подсказки для пользователя, нужно действовать поэтапно.

  1. Для дополнения слова следует рассмотреть две вариации:

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

    2. Если предыдущего слова нет, то просто ищем по всему словарю через like с учетом частоты слова в тексте.

SQL-запрос будет состоять из двух частей. 

Первая — для отбора, когда есть предыдущее слово (разворачиваем JSON с совстречаемыми словами и ищим в них):

select value name_token, (1 / (ordinality::numeric)) vl_token_number
     from token_dict td
              cross join jsonb_array_elements_text(td.js_token_hint) with ordinality
     where
         td.nm_token = :previousWord
       and (value) like :query
order by vl_token_number desc

Вторая часть для случаев, когда предыдущего слова нет:

select td.nm_token name_token, td.vl_token_number
from token_dict td
where
   td.nm_token like :query
order by vl_token_number desc

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

  1. Для подсказки следующего слова берем текущее и выдаем самые популярные совстречаемые слова:

select value nm_hint
from token_dict t
        cross join jsonb_array_elements_text(t.js_token_hint) with ordinality
where t.nm_token = :word
order by ordinality
limit :numHints

Исправление опечаток

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

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

select t.nm_token as tokenname
from (select levenshtein_less_equal(td.nm_token, :word, 5) vl_lev,  
             td.nm_token, td.vl_token_number, td.vl_frequency_rus
     from token_dict td) t
where t.vl_lev < (:numOperationLevenshtein)
order by t.vl_lev, vl_token_number desc
limit 1

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

Заключение

Итак, мы рассказали, как ищем документы в Naumen Disk. На хабре есть достаточно много статей по поисковым движкам, в том числе по собственным решениям на различных языках программирования для FTS. У нас используется свой метод, который базируется на общепринятых подходах. На данном этапе развития проекта он нас полностью устраивает: решает задачи и покрывает объемы документов, с которыми мы сталкиваемся (сотни тысяч документов, но и к миллионам мы готовы :) ). Данный метод поиска мы полностью контролируем, можем самостоятельно видоизменять и дорабатывать под специфические требования. 

Теги:
Хабы:
+9
Комментарии 7
Комментарии Комментарии 7

Публикации

Информация

Сайт
www.naumen.ru
Дата регистрации
Дата основания
Численность
1 001–5 000 человек
Местоположение
Россия