Дерево Киви для поиска шаблонов по тексту

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

Для этого используются:

• Поисковые системы — Google, Яндекс

• Социальные сети — VK, Facebook, …

• Системы мгновенного обмена сообщениями — Telegram, WhatsApp, …

• Прочие сервисы — RSS, YouTube, Instagram, Linkedin, …

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

Можно представить поступающую информацию как поток сообщений, которые имеют данные (aka payload) и метаданные (key-value map). Для простоты, в первом приближении можно считать что ключи и значения метаданных — это текст. Тогда можно выразить подписку на интересующие сообщения как «ключ: шаблон». Шаблон должен поддерживать хотя бы минимальные возможности регулярных выражений.

Существующие Pub/Sub системы не позволяют этого достичь, они ограничены возможностью подписки на «канал» или «топик» (далее — просто «канал»). В некоторых из них, таких как Kafka или NATS есть зачатки фильтрации этих каналов с применением шаблонов (примитивных «глобов» или полноценных регулярных выражений).

Пример wildcard subject из NATS:

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

Пример из Kafka Consumer API:

public void subscribe(Pattern pattern, ConsumerRebalanceListener listener)

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

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

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

Для решения этой задачи удалось применить специальную структуру данных, которая была названа Kiwi Tree. Слово Kiwi здесь является сокращением от Key-Input WIldcard. Следует рассматривать Kiwi Tree как рабочий вариант решения, возможно ещё не самый эффективный.

Для начала потребуется определить, какие типы шаблонов нужно поддерживать. В реализации Kiwi Tree было решено остановиться на формате, приближенном к Unix Globs, который описывает специальные символы, такие как «*», «?» и некоторые другие. Эти глобы должны быть разделены на т. н. «нейтральные» и остальные. Нейтральный глоб может означать только 1 символ. Это различие между глобами понадобится в дальнейшем.

Вставка шаблона в Kiwi дерево изначально работает как в обычном префиксном дереве. Все встреченные глобы заменяются на соответствующие непечатаемые коды, чтобы отличать узлы с глобами от узлов с символами вроде «*».

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

Тогда шаблон — это строка, содержащая обычные символы и символы глобов в произвольном порядке. Пример:

foo*bar?

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

foo*bar*

Главная особенность алгоритма — направление поиска меняется при встрече не-нейтрального глоба на противоположное. То есть от корня дерево является префиксным, но любое поддерево узла с кодом, например 1 (что соответствует символу глоба «*») является суффиксным.

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

Шаги алгоритма поиска:

1. Если текущий узел содержит данные и удовлетворяет текущему контексту поиска, тогда добавить текущий путь в дереве в результаты. Критерии совпадения с контекстом поиска:

   1. Текущее направление дерева — префиксное (не-нейтральные глобы не встречались) и в контексте больше нет символов исходного текста (пусто).

   2. Направление — суффиксное (есть в пути не-нейтральный глом) и оставшиеся символы исходного текста удовлетворяют ему.

2. Взять следующий символ исходного текста из контекста:

   1. Забирать с начала исходного текста, если направление — префиксное.

   2. Забирать с конца, если — суффиксное.

3. Цикл по дочерним узлам:

   1. Сравнить выбранный на шаге (2) символ с:

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

      2. Иначе в дочернем узле — код глоба. Тогда:

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

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

Иллюстрация Kiwi дерева для наглядности:

Эта структура данных была успешно перенесена на MongoDB, а алгоритм был реализован в виде сервиса с gRPC API. С исходным кодом можно ознакомиться здесь: https://github.com/awakari/kiwi-tree

В следующей статье я планирую рассказать, как это применяется в полноценной Pub/Sub системе, построенной на основе Kiwi Tree. Stay tuned.