По работе стояла задача оптимизации поиска по адресам (улицы, дома и объекты). Главный критерий - нахождение адреса, если написано с ошибками или не дописан он в полной мере. Bert’ы, косинусные расстояния эмбеддингов и т.д. не подходили, так как они заточены под смысловой поиск, а в адресах смысла нет. TF-IDF c лемматизацией тоже не очень подходил для этой задачи, результаты были плохие.
Для реализации начал использовать расстояние Дамерау-Левенштейна, и в последствие, развил это до собственного алгоритма, который находит расстояние между двумя строками.
Цель данного поста описание только алгоритма.
Описание алгоритма
Процесс работы алгоритма
Формула
Tew - это получаемое расстояние между двумя строками.
Если рассмотреть по этапам:
Реализация кодом на R
Функция реализации алгоритма.
library(stringr)
library(data.table)
library(magrittr)
library(stringdist)
Присоединяю пакет: 'stringdist'
Следующий объект скрыт от 'package:magrittr':
extract
stringDistination <- function(src_query, trg_query){
clearSplit <- function(x){
x %>%
strsplit(split = " ") %>%
unlist() %>%
tolower() %>%
.[. %ilike% "\\w+"] %>%
str_squish()
}
# Splitting queries
src = clearSplit(src_query)
trg = clearSplit(trg_query)
# By every word find closeness
x <- list()
y <- c()
for (i in seq(length(src))) {
for (l in seq(length(trg))) {
y[trg[l]] <- stringdist(a = trg[l], b = src[i], weight = c(0.8, 1, 1, 1)) / max(nchar(src[i]), nchar(trg[l]), na.rm = TRUE) # finding similarity word by word
}
x[[src[i]]] <- y
}
# min value by each word
vec <- x %>%
unlist() %>%
{
str <- names(.) %>% tstrsplit(split = "\\.")
c(
setNames(
object = .,
nm = str[[1]]
),
setNames(
object = .,
nm = str[[2]]
)
)
} %>%
sort %>%
.[unique(names(.))]
# finding digitals
num_names <- which(str_detect(string = names(vec), pattern = "\\d+"))
# if number, number have to be low impactable
if(length(num_names) > 0){
mean_val <- mean(vec, na.rm = TRUE)
vec[num_names] <- fifelse(vec[num_names] > mean_val, vec[num_names], mean_val)
}
vec %>%
.[seq(length(src))] %>%
{
. * (1/log(order(.)+1)) # calculate distance value depending on its position
} %>%
mean() %>% # take mean value
{
if(length(src) == length(trg)){ . * (1 - 0.005)} else {.} # if lengths of src and trg are equal, in this case the obtained average value is reduced by 0.5%
}
}Пример работы функции
queries <- c("Эски сары", "Нарты")
target_vector <- c("Эски сары кёл", "Хасаутская", "Нартов", "Новый Карачай", "Мара-Аягъы", "Кавказская")
data.table(query = rep(queries, each = length(target_vector)),
target = rep(target_vector, length(queries))) %>%
.[, similarity := stringDistination(src_query = query, trg_query = target) %>% round(3), by = 1:nrow(.)] %>%
.[, .SD[order(similarity)], by = query] %>%
.[, position := 1:.N, by = query]
query target similarity position
1 Эски сары Эски сары кёл 0.000 1
2 Эски сары Нартов 0.784 2
3 Эски сары Мара-Аягъы 0.824 3
4 Эски сары Новый Карачай 0.836 4
5 Эски сары Хасаутская 0.941 5
6 Эски сары Кавказская 0.941 6
7 Нарты Нартов 0.478 1
8 Нарты Эски сары кёл 0.519 2
9 Нарты Мара-Аягъы 1.005 3
10 Нарты Новый Карачай 1.030 4
11 Нарты Хасаутская 1.148 5
12 Нарты Кавказская 1.292 6
Вывод
По сравнению с существующими поисковыми движками (а сравнивал с meilisearch) есть свои преимущества:
Алгоритм показывает достойный результат в задачах нечёткого поиска. Например, основная проблема поисковых движков в том, что второе слово и последующие очень слабо влияют на выдачу, а первое крайне сильно, так что если местами поменять слова при вводе, то и результат изменится. Разработанный поисковик таких проблем не имеет.
Не нужно отдельное место для сервера, оркестрирование контейнеров и т.д. А также индексацию проводить. Работает всё сразу.
Недостатки:
Он медленнее существующих поисковых движков (0,4 секунды против 0,09). Поэтому для быстрого поиска он не используется. Может можно его как-то ускорить, однако я пока не смог придумать.
Поисковый движок отлично подойдёт, если сравниваются строки по словам, нужно локально реализовать и вопрос скорости не стоит слишком остро (качество выдачи приоритетнее).
Комментарии (17)
SpiderEkb
07.04.2024 16:17+2Интересная задачка. Сам с подобной сейчас работаю. Но у меня все хуже - нужно сравнить два массива адресов и найти совпадения. Массивы достаточно большие - в пределе порядка 250млн в одном и порядка 1млн в другом (это верхние оценки).
Причем совпадение считается, например,
РОССИЙСКАЯ ФЕДЕРАЦИЯ, Г. САНКТ-ПЕТЕРБУРГ, УЛ. ВАСИ АЛЕКСЕЕВА, Д. 26, ЛИТ. А, ПОМ. 2Ни
Д. 26, УЛ. АЛЕКСЕЕВА ВАСИ, Г. САНКТ-ПЕТЕРБУРГГде один из адресов неполный и порядок слов не сопадает.
Первое что делаем - нормализуем адрес.
РОССИЙСКАЯ ФЕДЕРАЦИЯ, Г. САНКТ-ПЕТЕРБУРГ, УЛ. ВАСИ АЛЕКСЕЕВА, Д. 26, ЛИТ. А, ПОМ. 2НВ нормализованном виде выглядит
САНКТ ПЕТЕРБУРГ ВАСИ АЛЕКСЕЕВА 26 ЛИТ ПОМ 2НДалее разбиваем адрес на элементы (слова) и составляем из него набор уникальных элементов.
Совпадение двух адресов - когда все уникальные элементы меньшего (с меньшим количеством элементов) набора входят в больший набор.
Т.е. остается только взять тот набор, где элементов меньше и проверить чтобы все его элементы присутствовали во втором наборе, где элементов больше или равно.
В принципе, когда все адреса лежат в БД, можно держать "витрину" адресов (где адреса представлены наборами элементов) и тогда задача решается одним SQL запросом.
zodchiy
07.04.2024 16:17Также решал задачу слияния справочника по лекарствам от разных аптек. Нормализуем до символов и цифр, удаляем остальное, удаляем пробелы, разбиваем на чанки по 3 символа, с возвратом на один, т.е. получаем набор из символов [0-2],[2-4],[4-6] и т.д., делаем хэши чанков и пишем в бд. При поиске аналога делает также, и ищем получившиеся хэши, немного магии сортировки и получаем аналог с приемлемой точностью. Делал 8 лет назад, уже подробности не помню.
SpiderEkb
07.04.2024 16:17Увы, но "приемлемая точность" тут не годится. Речь идет о формировании стоплистов для контроля платежей а основе совпадений адресов клиентов и адресов разного рода злодеев из списков росфинмониторинга.
Хеши тут излишни - в витринах хранятся элементы. Дальше просто - есть набор элементов адреса клиента и количество уникальных элементов в нем. Аналогично для субъекта списка росфина.
А дальше скулем просто пары выбираем тех, у кого количество пересечений по уникальным элементам равно или количеству элементов адреса клиента, или количество элементов адреса субъекта.
26rus_mri
07.04.2024 16:17если массив адресов, в котором ищем, преобразовать в дерево Города - Улицы города - Дома на улице - Квартиры в доме, то скорость поиска будет логарифмичекской, причём с основанием не 2, как у бинарного дерева, а с размером вложенных массивов. Соответственно проверяемые адреса тоже имеет смысл нормализовывать не в строки, а в кортежи Город Улица Дом Квартира.
SpiderEkb
07.04.2024 16:17В теории все верно. Но есть проблема реализации всего этого на практике.
Да, на стороне клиентов есть т.н. "структурированные адреса". Там действительно все разбито на поля - страна, регион, населенный пункт, район и т.п. Правда, там сложнее все с адресами. Населенный пункт может быть не просто город, а поселок с черте города (нп. г.Екатеринбург, пос.Медный). А улицы вообще может не быть.... Например, вполне реальный адрес - "Тюменская область, г.Тобольск, микрорайон 7А д.5Д"
Но проблема в том, что много адресов не структурированы (и там совершенно не обязательно будет идти строго в порядке регион-населенный пункт-улица-дом-квартира, там ччто угодно и как угодно может быть - как д.10, кв.5, дат и 10-5, например...). Т.е. просто строка. Как их разбирать? Руками? Кто это будет делать? При этом любой адрес может быть не полным...
И проблема тут не столько в сравнении двух адресов - это как раз быстро. Проблема в том, что в БД лежит с одной стороны 250млн адресов, а с другой еще 1млн. И нужно за осмысленное время сравнить все со всеми. И не просто "вроде бы похоже...", а "этот совпал, тот не совпал".
Т.е. проблемы в объемах. И реализации быстрого поиска совпадений. Пока что удалось добиться - на тестовом юните 17тыс с одной стороны, 18тыс с другой находит чуть менее 11тыс совпадений (это тестовые данные) за 277сек при параллельной обработке в 5 потоков. Быстрее пока не получается никак...
Но это с "витринами", где адреса уже разложены по элементам и можно SQL запросом сразу искать пересечения по элементам.
nin-jin
07.04.2024 16:17+7Выбранное вами расстояние не нормализовано - это очень не удобно в использовании, так как по значению не понятна степень различия. При перестановке слов получается большое различие, хотя для человека, очевидно, различие минимально. Кроме того, точное вычисление этого расстояния довольно дорогое удовольствие.
Гляньте лучше расстояние Карловского, где сначала для каждого текста в отдельности строится профиль (вектор в пространстве триплетов), который можно кешировать, а потом от них просто берётся нормализованная манхеттенская норма.
На ваших примерах это даёт следующую картину:
Эски сары ~ Эски сары кёл = 0.18181818181818182 Эски сары ~ Хасаутская = 1 Эски сары ~ Нартов = 1 Эски сары ~ Новый Карачай = 1 Эски сары ~ Мара-Аягъы = 0.8947368421052632 Эски сары ~ Кавказская = 1 Нарты ~ Эски сары кёл = 1 Нарты ~ Хасаутская = 1 Нарты ~ Нартов = 0.2727272727272727 Нарты ~ Новый Карачай = 0.8888888888888888 Нарты ~ Мара-Аягъы = 0.8666666666666667 Нарты ~ Кавказская = 1Обратите внимание, что полностью различные тексты - это именно полностью различные, без градации по степени непохожести.
Ой, опять $mol рекламирую. По жопе мне.
seriych
07.04.2024 16:17+1В clickhouse для этого есть всякие готовые ngramDistance*(). Неплохо работает для приведенных примеров (даже явно получше, чем в статье для
Нарт). Оно смотрит процент совпадающих последовательностей байт в строках - можно это реализовать на удобном вам языке.Hidden text
with ['Эски сары', 'Нарты'] as queries, ['Эски сары кёл', 'Хасаутская', 'Нартов', 'Новый Карачай', 'Мара-Аягъы', 'Кавказская'] as target_vector select arrayJoin(queries) as query, arrayJoin(target_vector) as target, ngramDistance(query, target) as similarity1, ngramDistanceCaseInsensitiveUTF8(query, target) as similarity2 order by query, similarity2, similarity1 format PrettyCompactMonoBlock ; +-query-----+-target--------+-similarity1-+-similarity2-+ 1. | Нарты | Нартов | 0.375 | 0.42857143 | 2. | Нарты | Эски сары кёл | 0.85714287 | 1 | 3. | Нарты | Мара-Аягъы | 0.9130435 | 1 | 4. | Нарты | Новый Карачай | 0.9310345 | 1 | 5. | Нарты | Хасаутская | 1 | 1 | 6. | Нарты | Кавказская | 1 | 1 | 7. | Эски сары | Эски сары кёл | 0.2 | 0.22222222 | 8. | Эски сары | Хасаутская | 0.7419355 | 1 | 9. | Эски сары | Нартов | 0.82608694 | 1 | 10. | Эски сары | Кавказская | 0.87096775 | 1 | 11. | Эски сары | Мара-Аягъы | 0.93333334 | 1 | 12. | Эски сары | Новый Карачай | 0.9444444 | 1 | +-----------+---------------+-------------+-------------+https://fiddle.clickhouse.com/466ee362-dbff-4161-9553-ae6abcd565ec
TSjB Автор
07.04.2024 16:17Спасибо, интересный результат выдаёт
На R делал "процент совпадающих последовательностей байт в строках", но у меня результат был хуже в поиске. Возможно в кликхаусе прокаченнее функция, изучу
SpiderEkb
07.04.2024 16:17Специфика адресов и имен/наименований в том, что там нельзя сравнивать последовательности байт. Сравнение должно идти по наборам слов (элементов). И с учетом полный/неполный. Для имен то же самое:
ИВАНОВ ИВАН ИВАНОВИЧи
ИВАН ИВАНОВсчитаются совпадением т.к все уникальные элементы более коротого набора
ИВАН ИВАНОВвходят в более длинный
ИВАН ИВАНОВ ИВАНОВИЧАналогично и для адресов.
Т.е. на самом деле там очень простой алгоритм:
Нормализуем строки (приведение к одному регистру, удаление лишних символов, возможно, исключение каких-то "лишних" слов и т.п.
Разбиваем строки на слова (элементы) и заносим в наборы с уникализацией (все элементы в наборе уникальны)
Выбираем набор с меньшим количеством элементов (если количество элементов набора равное - любой набор).
Проходим поэлементно по выбранному набору и проверяем каждый элемент на присутствие во втором наборе.
Если все элементы меньшего набора присутствуют в большем - есть совпадение.
Вот как-то так.
seriych
07.04.2024 16:17В первом же абзаце статьи: "Главный критерий - нахождение адреса, если написано с ошибками или не дописан он в полной мере." Чуть опечатался и всё, разбиение на слова и точная проверка ломаются сразу. Ну и выше вам показывали про дом с квартирой. Тоже самое с улицей и населенным пунктом может быть.
ИВАНОВ ИВАН ИВАНОВИЧ
и
ИВАН ИВАНОВ
считаются совпадением т.к все уникальные элементы более коротого набораМне кажется, что ИВАНОВ ИВАН ИВАНОВИЧ и ИВАНОВ ИВАН ИВАНОВИЧ всё-таки совпадение получше, то есть логично меру для ИВАН ИВАНОВ и ИВАНОВ ИВАН ИВАНОВИЧ видеть хуже.
Возможно, вы не совсем поняли про "последовательности байт" (собственно я и не пояснял особо). Там ищется не максимально длинное совпадение. Там строки разбиваются на все возможные последовательности N байт (для фиксированного N), например: 'ИВАН', 'ВАН ', 'АН И', 'Н ИВ' и т.д. И вот число совпадающих этих наборов сравнивается. Это достаточно хорошо работает с перестановками слов, опечатками и.т.п. (поэтому я и предложил метод автору). Но пункт про нормализацию строк в той или иной степени может быть полезен в каких-то случаях и здесь.
P.S. Я ни разу не специалист в этой теме, не знаю, как лучше будет работать у автора статьи и как лучше будет работать у вас. Я лишь запостил еще один вариант. Кажется, что у каждого метода есть недостатки, выстреливающие в зависимости от ситуации. Собственно не было бы нескольких разных методов если бы это было не так.
SpiderEkb
07.04.2024 16:17С опечатками да - беда.
Дом-квартира - есть такая проблема, наш бизнес в курсе, пока мирятся. Но это вопрос нормализации. Если д.5, кв.10 нормализовать не в 5 10, а в Д5 КВ10 - проблема уйдет. В принципе, это алгоритмизуется.
Насчет "недописали" - это как раз неполное имя/адрес. Т.е. ИВАНОВ ИВАН и ИВАН ИВАНОВИЧ ИВАНОВ запросто может быть одним и тем же человеком. А вот ИВАНОВ ИВАН ИВАНОВИЧ и ИВАН ПЕТРОВИЧ ИВАНОВ - разные люди и тут совпадений не будет (т.к. у них нет пересечений по полному количеству элементов ни для одного из наборов - в обеих наборах есть элементы, отсутствующие в другом).
В целом это достаточно непростая на самом деле задача, особенно когда речь идет о больших объемах данных.
Сначала мы думали использовать "ключевое слово" - элемент адреса, который реже всего встречается в витрине элементов с которыми надо искать совпадения. И делать предвыборку адресов где потенциально возможны совпадения, а потом уже каждый адрес из предвыборки проверять на совпадения по алгоритму. Но не взлетело - очень плохая селективность получилась и слишком большие объемы для достаточно "тяжелого" точного сравнения. Сейчас перешли на поиск по пересечению витрин. Вот отдали на нагрузочное тестирование на копии промсреды, ждем результат.
Zara6502
не знаком с R, но немного пишу на C# и там LINQ (SQL подобная семантика) весьма медленная, при очень простом и быстром написании сложных многоуровневых команд. Нет ли в вашем случае такой же проблемы?
Skykharkov
LINQ - весьма быстр. Быстрее циклов и так далее. А еще есть Parallel LINQ. Просто, как и SQL, его надо "уметь готовить". На SQL можно SELECT FROM SELECT FROM SELECT... И удивляться, что-ж оно так медленно. Так и LINQ - нужно понимать и экспериментировать, что куда и как.
Zara6502
Я соглашусь с тем что инструментом нужно уметь пользоваться, но абсолютно не согласен что LINQ быстрый. Если например почитать статьи или StackOverflow, то про низкую производительность говорят регулярно. Я в своей статье эту тему затрагивал.