Расстояние Дамерау-Левенштейна между двумя векторами

Расстояние Дамерау-Левенштейна между двумя строками abc и acb будет равно 1, потому что оно включает одну транспозицию между b и c.

> stringdist("abc", "acb", method = "dl")
[1] 1

Теперь предположим, что у меня есть следующие два вектора символов:

A = c("apple", "banana", "citrus")
B = c("apple", "citrus", "banana")

Как рассчитать расстояние Дамерау-Левенштейна между A и B, чтобы результат был идентичен расстоянию между abc и acb, поскольку между цитрусовыми и бананом существует одна транспозиция? Другими словами, как рассчитать расстояние Дамерау-Левенштейна между A и B, чтобы каждый элемент считался одним символом в строке?


r distance similarity damerau-levenshtein
person Ian    schedule 31.03.2021    source источник
comment
Попробуйте это (если я вас хорошо понял, хотя и не уверен): abs(match(A, B) - seq_along(A)), если предположить, что оба этих атомных вектора содержат одни и те же элементы, только в другом порядке, также A является ссылкой   -  person PKumar    schedule 31.03.2021
comment
Мне нужно одно расстояние между A и B (= 1), а не расстояние между каждой парой элемента в A и элементом в B.   -  person Ian    schedule 31.03.2021
comment
взять максимум предыдущего выражения   -  person PKumar    schedule 31.03.2021
comment
stringdist(paste(substr(A, 1, 1), collapse=""), paste(substr(B, 1, 1), collapse=""), method="dl") ? (кстати, stringdist не является базовой функцией R, пожалуйста, включите загрузку пакета в свой вопрос)   -  person Cath    schedule 31.03.2021
comment
Я добавил (и позже обновил) ответ, который должен охватывать все стандартные случаи расстояния Дамерау-Левенштейна, когда каждый элемент вектора рассматривается как один символ в строке. :-)   -  person Oliver    schedule 31.03.2021

Ответы (1)


arrow_upward
0
arrow_downward

Как насчет

vecdist <- function(x, y){
  matches <- match(x, y, nomatch = 0)
  nomatch <- matches == 0
  # No match = we need 1 permutation
  # Other matches: Compare index, for each "not inverted" index, (not 3 vs -3) we need 1 permutation
  perm_match <- (matches - seq_along(matches))[!nomatch]
  perm_n <- sum(perm_match != 0) - sum(duplicated(abs(perm_match)))
  sum(nomatch) + perm_n + sum(!y %in% x)
}

Основная идея здесь такова:

  1. Проверьте наличие отсутствующих совпадений в x и y и наоборот. Каждая из них представляет собой 1 перестановку
  2. Для остальных нам нужно проверить индексы соответствия. Здесь я использую небольшой трюк, проверяя, должны ли какие-либо поля переключаться друг с другом с помощью duplicated(abs(...)). Например, abcd, badc — это 2 перестановки, а abcd, bdca — это 3.

Это очень похоже на то, как stringdist работает для одиночных строк.

A = c("apple", "banana", "citrus")
B = c("apple", "citrus", "banana")
vecdist(A, B)
[1] 1
A <- c(A, 'pear')
vecdist(A, B)
[1] 2
vecdist(B, A)
[1] 2
A <- c('apple', 'banana', 'citrus', 'pear')
B <- c('pear', 'citrus', 'banana', 'apple')
vecdist(A, B)
[1] 2
vecdist(B, A)
[1] 2
A <- c('apple', 'banana', 'citrus', 'pear')
B <- c('pear', 'citrus', 'apple', 'banana')
vecdist(A, B)
[1] 3
vecdist(B, A)
[1] 3
person Oliver    schedule 31.03.2021