[Перевод] Быстрый поиск опечаток на Rust
Мы запустили наш поисковик по Hacker News и RAG-движок с полусырой системой исправления опечаток. В нашей первой версии тратилось более 30 мс на обработку орфографически правильных запросов. Это достаточно много, поэтому по умолчанию мы отключили данную фичу. Наша новейшая версия работает в 100 раз быстрее, справляется за 300 мкс с корректно записанными запросами и тратит ~5 мс/слово на исправление ошибок. В этом посте мы объясним, как нам удалось этого добиться!
Примеры запросов вам на пробу
Если хотите сами поэкспериментировать с исправлением опечаток на сайте hn.trieve.ai — пощёлкайте по следующим ссылкам:
Создаём словарь лексем с учётом частотности
При работе с небольшими наборами данных эта задача проста. Можно за десять секунд пролистывать массивы текста, сопоставимые по размеру примерно с 1000 постами на HN, для этого хватит одного рабочего потока и функции разделения слов. Однако, по мере роста до таких размеров, какие обрабатываются в нашем датасете Hacker News Demo (38M+ постов), работу требуется распределять.
В конце концов, мы решили составлять словарь при помощи 2 отдельных рабочих программ:
1. При помощи Cronjob прокручивать все документы, присутствующие в поисковых выдачах каждого из наших пользователей и добавлять идентификаторы фрагментов, перенося их из нашей базы данных в очередь Redis по 500 штук за раз.
2. При помощи Word worker элементы выталкиваются из очереди, при этом, программа обрабатывает 500 фрагментов за раз. Подтягивается текст для каждого фрагмента, разделяется на слова, после чего каждое слово загружается в Clickhouse.
Мы решили хранить словарь в ClickHouse, когда стали сталкиваться с взаимными блокировками и с проблемами производительности при записи в Postgres. Эти проблемы нарастали с увеличением числа рабочих потоков. Асинхронные вставки ClickHouse фантастически хороши для такой задачи, с их помощью нам удавалось поглощать весь наш датасет на 38+ миллионов документов менее чем за час.
Выявляем и исправляем опечатки при помощи структуры данных BK-дерево
Мы избрали стандартный подход к исправлению опечаток и на каждый датасет выстраивали деревья Буркхарда-Келлера. Они помогают эффективно сравнивать слова в поисковом запросе и словарь множества данных по алгоритму с временной сложностью O (log N). Подробное объяснение этой структуры данных выходит за рамки данного поста, но вы можете почитать здесь о нашей реализации на Rust или обратиться к вики-источнику.
Мы выстраивали BK-деревья при помощи третьего рабочего потока bktree-worker. Он берёт полные датасеты со словарями, сохранёнными в Clickhouse, а затем, опираясь на данные о словах и их частотности, собирает дерево.
Как только BK-дерево построено, рабочий поток сохраняет его в Redis так, что его можно эффективно загружать в память API-сервера сразу же, как поступит первый запрос к конкретному датасету.
Эта задача оказалась нетривиальной при работе с очень большими датасетами, где размер дерева исчисляется сотнями мегабайт. Мы постоянно сталкивались с задержками при работе Redis в процессе чтения и записи. Мы разработали метод сериализации, при помощи которого разглаживаем и архивируем данные, тем самым делая их компактнее в Redis, а также сокращая задержку при подтягивании и отправке.
Пишем бизнес-логику для исправления опечаток
На стороне API-сервера работает наш typo_operator, который мы специально оптимизировали, повысив скорость обработки до ~300 мкс для орфографически верных запросов и до ~10 мс/слово для запросов с ошибками.
Подтягивание данных из Redis
Чтобы подтянуть из Redis крупную структуру данных, такую как BK-дерево для HN, требуется 300+ мкс. Это нежизнеспособный подход, если такую операцию проделывать при каждом поисковом запросе, поэтому на стороне сервера мы реализовали уровень кэша, чтобы хранить в нём BK-деревья, которые уже один раз были подтянуты. Это делается при помощи lazy_static!
lazy_static! {
static ref BKTREE_CACHE: BKTreeCache = BKTreeCache::new();
}При первой попытке поиска с включённой толерантностью к опечаткам мы предусмотрели холодный старт приблизительно в 200–400 мс, чтобы успеть подтянуть BK-дерево запрашиваемого датасета из Redis в память сервера. За этой операцией следуют операции поиска, при которых для проверки на опечатки используется BK-дерево. Каждая такая проверка занимает всего 100–300 мкс.
Выявление английских слов
1. Предварительная идентификация английских слов
Поскольку наши BK-деревья составляются исключительно из словарей, специфичных для датасета, в них могут присутствовать не все реально существующие английские лексемы. Чтобы предотвратить ненужную коррекцию реальных слов, отсутствующих в дереве, предусмотрим предварительный этап, на котором будут идентифицироваться английские слова:
В оперативной памяти держим хеш-множество примерно из 400 000 английских слов, сохраняемых при помощи English lazy_static!
static ref ENGLISH_WORDS: HashSet = {
include_str!("../words.txt")
.lines()
.map(|s| s.to_lowercase())
.collect()
};
2. Анализ аффиксов
Далее проверяем — вдруг перед нами просто английское слово с приставкой или суффиксом:
static ref PREFIX_TRIE: Trie = {
let prefixes = vec![
"anti", "auto", "de", "dis", "down", "extra", "hyper", "il", "im", "in", "ir", "inter",
"mega", "mid", "mis", "non", "over", "out", "post", "pre", "pro", "re", "semi", "sub",
"super", "tele", "trans", "ultra", "un", "under", "up",
];
Trie::new(&prefixes)
};
static ref SUFFIX_TRIE: Trie = {
let suffixes = vec![
"able", "al", "ance", "ation", "ative", "ed", "en", "ence", "ent", "er", "es", "est",
"ful", "ian", "ible", "ic", "ing", "ion", "ious", "ise", "ish", "ism", "ist", "ity",
"ive", "ize", "less", "ly", "ment", "ness", "or", "ous", "s", "sion", "tion", "ty",
"y",
];
Trie::new(&suffixes)
};1. Для каждого слова в запросе проводим поиск по этим борам и находим самый длинный подходящий префикс и суффикс.
2. Затем отсекаем эти аффиксы от слова, оставляя только корень.
3. После этой операции выполняем окончательную словарную проверку:
4. Ищем корень по словарному корпусу английского языка.
fn is_likely_english_word(word: &str) -> bool {
if ENGLISH_WORDS.contains(&word.to_lowercase()) {
return true;
}
// Проверка префикса
if let Some(prefix_len) = PREFIX_TRIE.longest_prefix(word) {
if ENGLISH_WORDS.contains(&word[prefix_len..].to_lowercase()) {
return true;
}
}
// Проверка суффикса
if let Some(suffix_len) = SUFFIX_TRIE.longest_suffix(word) {
if ENGLISH_WORDS.contains(&word[..word.len() - suffix_len].to_lowercase()) {
return true;
}
}
// Проверка составных слов
if word.contains('-') {
let parts: Vec<&str> = word.split('-').collect();
if parts
.iter()
.all(|part| ENGLISH_WORDS.contains(∂.to_lowercase()))
{
return true;
}
}
false
}4. Поиск несловарных слов по BK-деревьям
Если какие-то слова не прошли вышеуказанную проверку по корпусу английского языка, запускаем поиск по BK-дереву:
1. Запрашиваем BK-дерево в поисках ближайших подходящих слов.
2. Генерируем набор «исправленных» вариантов для каждого несловарного слова.
let mut best_correction = None;
let mut best_score = 0;
for ((correction, freq), distance) in tree.find(word.to_string(), max_distance) {
if distance == 0 {
best_correction = None;
break;
}
if !is_best_correction(word, correction) {
continue;
}
let score = (max_distance - distance) * 1000 + *freq as isize;
if score > best_score || best_correction.is_none() {
best_correction = Some(correction);
best_score = score;
}
}
if let Some(correction) = best_correction {
corrections.insert(word, correction.to_string());
}5. Выбор правок
Когда составим набор возможных исправлений, задействуем скоринговый алгоритм для выбора наилучшего варианта правки:
Наш алгоритм учитывает, прежде всего, совпадение префиксов, а также принимает во внимание частотность каждого слова-кандидата в пределах датасета.
fn is_best_correction(word: &str, correction: &str) -> bool {
// Фильтр на основе длины
let len_diff = (word.len() as i32 - correction.len() as i32).abs();
if len_diff > 2 {
return false;
}
// Совпадение по префиксу (откорректировать длину, если потребуется)
let prefix_len = std::cmp::min(1, std::cmp::min(word.len(), correction.len()));
if word[..prefix_len] != correction[..prefix_len] {
return false;
}
// Сравнение наборов символов
let word_chars: HashSet = word.chars().collect();
let correction_chars: HashSet = correction.chars().collect();
let common_chars = word_chars.intersection(&correction_chars).count();
let similarity_ratio =
common_chars as f32 / word_chars.len().max(correction_chars.len()) as f32;
similarity_ratio >= 0.8
} Неожиданные достоинства
Пользователь Levitating сообщил на HN, что запрос FreeBSD, отсортированный по оценкам, выдаёт нерелевантные результаты. Но наш токенизатор разбивает слова с учётом верблюжьего регистра, поэтому FreeBSD преобразуется в Free BSD FreeBSD. У сюжетов, в которых содержится только «Free», оценок гораздо больше, чем у любых, содержащих «FreeBSD» — следовательно, первые и ранжируются выше. Поэтому открывается возможность для проверки по целым словам на уровне всего датасета, при которой можно автоматически затребовать неанглийские слова. В таком случае запрос FreeBSD превращается в «FreeBSD».
Идеи на будущее
Опираясь на эту же систему, планируем реализовать функционал разбиения и сцепления запросов, поскольку при этих операциях в равной степени актуально требование быстро подыскивать лексемы в словаре.
