Алгоритм расчёта расстояния между строками

По работе стояла задача оптимизации поиска по адресам (улицы, дома и объекты). Главный критерий - нахождение адреса, если написано с ошибками или не дописан он в полной мере. 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). Поэтому для быстрого поиска он не используется. Может можно его как-то ускорить, однако я пока не смог придумать.

Поисковый движок отлично подойдёт, если сравниваются строки по словам, нужно локально реализовать и вопрос скорости не стоит слишком остро (качество выдачи приоритетнее).