Недавно понадобилось реализовать поиск по началу строки, по сути WHERE name LIKE 'начало%'. Это был поиск по названию биржевых символов (AAPL, AMZN, EUR/USD и пр.). Хотелось, чтобы поиск работал быстро, и не нагружал лишний раз БД. В итоге пришел к реализации поиска по дереву в памяти, об этом и расскажу.
В моем случае поиск выполняется по примерно 55000 коротким строкам (биржевым символам). То есть индекс по этим данным без проблем полностью ложится в оперативную память. Надо только аккуратно его сформировать, чтобы можно было быстро найти данные по запросу.
Ниже описана реализация поиска. Сразу отмечу, что это не сбалансированное дерево BTree, а префиксное дерево (также бор, луч, нагруженное дерево, trie), где на каждом уровне — очередной символ строки. Реализация такого варианта дерева очень проста и достаточно эффективна для многих задач, когда требуется индексировать не длинные строки.
В статье постарался описать алгоритм поиска без примеров кода. Ссылку на код дам в конце статьи, код оформил в отдельный готовый к использованию пакет.
Структура дерева
В каждом узле дерева храним дочерние элементы в виде сортированной хеш таблицы и само значение узла в виде списка.
Значение узла хранится именно в виде списка, чтобы проще было обрабатывать случаи, когда в искомых значениях могут встречаться разные данные с одинаковым ключом. В нашем случае это, например, символы на разных финансовых рынках:
AAA (BetaShares Australian High Interest Cash ETF, ASX),
AAA (All Active Asset Capital LTD, LSE).
Тогда мы запишем в Index.Data одну запись, внутри которой в Index.Data будет список из двух символов AAA.
В SearchIndex.Data можно хранить данные любой структуры. Таким образом, можно индексировать любые данные по строковому ключу.
Построение дерева для поиска
Дерево необходимо построить один раз, далее по этому готовому индексу можно будет выполнять поиск.
Перед построением дерева ключи предварительно обрабатываются следующим образом.
Все разделители заменяются на пробелы.
Двойные пробелы заменяются на одинарные.
Обрезаются пробелы по краям строк.
Строки переводятся в нижний регистр.
Схожие символы приводятся к единому формату, например, a > a.
Исключаются стоп-слова (опционально).
После этого данные сортируются, по умолчанию — по возрастанию ключа, в алфавитном порядке.
Затем отсортированные данные группируются по ключу, чтобы положить в Index.Data готовый список.
Теперь все готово для добавления данных в индекс. Наша задача теперь — сформировать Index.Children таким образом, чтобы на каждом уровне дерева лежал очередной кусочек ключа (в нашем случае кусочек ключа — это символ индексируемой строки). Например, если мы добавляем в индекс символ AAPL, то мы сформируем такую древовидную структуру (красная линия):
Тут на красной линии расположены на каждой вершине дерева элементы [A], [A], [P], [L]. В квадратных скобках обозначены ключи, которые используются на каждой вершине для индексации. Без скобок обозначены полные ключи, которые получаются при проходе от корня до вершины.
Поскольку мы формируем дерево, то добавление в индекс удобно делать рекурсивно. Добавляем промежуточные узлы, если их нет. И в лист дерева добавляем значение, которое мы индексируем.
Таким же образом последовательно добавляем в индекс все значения.
Поиск по дереву
Когда дерево уже построено, выполнить по нему поиск — задача довольно простая. Для этого выполним три шага.
Выполним предварительную обработку искомой строки тем же алгоритмом как обрабатывали ключи перед индексацией (см. выше).
Найдем в дереве элемент, в котором ключ совпадает с искомой строкой.
Далее последовательным перебором дочерних вершин получаем искомый результат.
Например, если в поиске мы вводим AA, то для описанного выше дерева ожидаем получить в результате такие строки в такой последовательности:
АА
ААА
АAAL
AAALF
AAAP
AAB
AAP
AAPJ
AAPL
AAPT
Чтобы получить этот результат, на первом шаге поиска мы перемещаемся в вершину AA. На втором шаге последовательно перебираем все дочерние вершины слева направо сверху вниз.
Поиск подходящего биржевого символа
Вышеперечисленный алгоритм хорошо подходит для поиска аналогичного WHERE name LIKE 'начало%'. Чтобы было удобно искать подходящий символ на финансовых рынках, этого оказалось недостаточно, и понадобилось учесть следующие моменты.
Если вводят в поиске “EUR”, то в выдаче должны быть “EUR”, “EUR/USD”, “USD/EUR”. То есть поиск должен работать не только с начала строки, но и с начала каждого слова в строке.
Поиск должен работать не только по названию символа, но также и по названию компании. Например, при вводе в поиске “APL”, надо выдать в результатах “APL”, “AAPL” (Apple).
Первыми выдавать в поиске популярные символы.
Чтобы для “EUR”, в выдачу попали не только “EUR”, “EUR/USD”, но и “USD/EUR”, решил класть в индекс по несколько экземпляров значений с разными ключами: подстроки начиная с каждого слова индексируемой строки. Например, при индексации строки “USD/EUR”, в индекс попадают следующие ключи: “usd eur”, “eur”. При индексации строки “Grupo Financiero Galicia SA” в индекс попадают ключи “Grupo Financiero Galicia SA”, “Financiero Galicia SA”, “Galicia SA”, “SA”.
Также чтобы учесть вышеописанные нюансы, понадобилось выполнять поиск в 4 этапа.
Поиск символов по точному совпадению с искомой строкой.
К полученным результатам найти и добавить наиболее популярные символы, у которых начало строки совпадает с введенной для поиска строкой.
Поиск символов по названию компании, добавление результатов к полученным выше.
Поиск символов у которых совпадает с искомой строкой только начало, и добавление этих результатов в итоговый список.
Чтобы получить нужный результат, удалось использовать описанный в предыдущих разделах индекс. Для этого создал три индекса.
Индекс
SearchSymbolIndexпо символам со всех финансовых рынков.Индекс
SearchPopularIndexтолько по популярным символам (10% от всех).Индекс
SearchInstrumentIndexпо названию компании.
Далее — просто последовательный поиск по каждому индексу с небольшой разницей в критерии.
var searchedData []searchindex.SearchData
searchedData = r.SearchSymbolIndex.Search(searchindex.SearchParams{
Text: key,
OutputSize: outputSize,
Matching: searchsymbol.Strict,
})
searchedData = r.SearchPopularIndex.Search(searchindex.SearchParams{
Text: key,
OutputSize: outputSize,
Matching: searchsymbol.Beginning,
StartValues: searchedData,
})
searchedData = r.SearchSymbolIndex.Search(searchindex.SearchParams{
Text: key,
OutputSize: outputSize,
Matching: searchindex.Beginning,
StartValues: searchedData,
})
searchedData = r.SearchInstrumentIndex.Search(searchindex.SearchParams{
Text: key,
OutputSize: outputSize,
Matching: searchindex.Beginning,
StartValues: searchedData,
})StartValues — значения, найденные на предыдущем этапе, они передаются на следующий этап поиска, чтобы в выдачу не добавлялись дубликаты, и не выполнялись лишние итерации поиска, если уже набралось достаточно данных (OutputSize).
searchindex.Strict — поиск точных совпадений.
searchindex.Beginning — поиск совпадений по началу строки.
Итого
Итого, имеем компактную реализацию быстрого поиска по строке в оперативной памяти. Код на данный момент занимает менее 300 строк. Причем реализация индекса получилась довольно универсальной, чтобы ее можно было использовать при реализации различных схожих задач.
Больших бенчмарков по производительности не делал, но на моих данных в 55000 строк создание трех индексов занимает примерно 2 секунды, это с учетом выборки из БД и дополнительных действий. А поиск в 4 последовательные итерации в трех индексах выполняется за 100-200 наносекунд (это если исключить время на обработку http запроса и считать только время поиска), что для моей задачи более чем достаточно.
Этот поиск сейчас используется в финансовом апи для разработчиков, пример можно посмотреть на этой странице, где его можно попробовать вживую.
negasus
Я правильно понимаю, что мы говорим про префиксное дерево?
mnv Автор
Совершенно верно
negasus
Тогда странно, что в во всей статье ни разу это словосочетание не упоминается)
mnv Автор
Спасибо, добавил