Как узнать, какие операции выполняются для вычисления расстояния Левенштейна между строками? - PullRequest
Новая
       63

Как узнать, какие операции выполняются для вычисления расстояния Левенштейна между строками?

9 голосов
/ 30 июня 2019

С помощью функции stringdist я могу вычислить расстояние Левенштейна между строками: оно подсчитывает количество удалений, вставок и замен, необходимых для превращения строки в другую.Например, stringdist("abc abc","abcd abc") = 1, потому что «d» было вставлено во вторую строку.

Можно ли узнать, какие операции были сделаны для получения расстояния Левенштейна между двумя струнами?Или же узнать символы, которые отличаются между двумя строками (в этом примере только «d»)?Спасибо. 

library(stringdist)
stringdist("abc abc","abcde acc") = 3

Я хотел бы знать, что:

  • "d" было вставлено

  • "e"был вставлен

  • "b" был заменен на "c"

Или, проще говоря, я хотел бы получить список ("d", "е", "с").

Ответы [ 3 ]

10 голосов
/ 30 июня 2019

С помощью adist() вы можете получить операции: 

drop(attr(adist("abc abc","abcde acc", count = TRUE), "counts"))

ins del sub 
  2   0   1

Из ?adist:

Если значение TRUE, то количество преобразований возвращается как "считает "атрибут этой матрицы как трехмерный массив с размерами, соответствующими элементам x, элементам y и типу преобразования (вставки, удаления и замены) соответственно.

8 голосов
/ 01 июля 2019

Это известно как алгоритм Нидлмана-Вунша .Он рассчитывает как расстояние между двумя строками, так и так называемый traceback , который позволяет восстановить выравнивание.

Поскольку эта проблема в основном возникает в биологии при сравнении биологических последовательностей,этот алгоритм (и связанные с ним) реализованы в пакете R {Biostrings} , который является частью Bioconductor .

Поскольку этот пакет реализует более общее решение, чемпростое расстояние Левенштейна, использование, к сожалению, более сложное, а виньетка использования соответственно длинна.Но основное использование для ваших целей заключается в следующем: 

library(Biostrings)

dist_mat = diag(27L)
colnames(dist_mat) = rownames(dist_mat) = c(letters, ' ')

result = pairwiseAlignment(
    "abc abc", "abcde acc",
    substitutionMatrix = dist_mat,
    gapOpening = 1, gapExtension = 1
)

Это просто не даст вам список c('b', 'c', 'c'), потому что этот список не полностью отражает то, что на самом деле здесь произошло.Вместо этого он вернет выравнивание между двумя строками.Это может быть представлено в виде последовательности с подстановками и пробелами: 

score(result)
# [1] 3
aligned(result)
as.matrix(aligned(result))
#      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
# [1,] "a"  "b"  "c"  "-"  "-"  " "  "a"  "b"  "c"
aligned(result)

- Для каждого символа во второй строке он предоставляет соответствующий символ в исходной строке, заменяя вставленные символы на -.По сути, это «рецепт» для преобразования первой строки во вторую.Обратите внимание, что он будет содержать только вставки и замены, но не удаления.Чтобы получить их, вам нужно выполнить выравнивание в обратном направлении (т.е. поменять местами строковые аргументы).

7 голосов
/ 01 июля 2019

Построение ответа tmfmnk и предложения поиграться с атрибутом "trafos", вот функция, которая покажет вам таблицу всех символов, вставленных или замененных, и сколько раз они были вставлены и заменены. Если вы установите all_actions = T, он также покажет вам совпадения. 

f <- function(x, y, all_actions = FALSE){
  o <- adist(x, y, count = TRUE)
  cva <- 
    list(char = strsplit(y, '')[[1]], 
         action = strsplit(attr(o,"trafos"), '')[[1]])
  if(!all_actions)
    cva <- lapply(cva, '[', cva$action %in% c('I', 'S'))
  do.call(table, cva)
}

f(x = "abc abc", y = "abcde acc")
#     action
# char I S
#    c 0 1
#    d 1 0
#    e 1 0

f(x = "abc abc", y = "abcde acc", all_actions = T)
#     action
# char I M S
#      0 1 0
#    a 0 2 0
#    b 0 1 0
#    c 0 2 1
#    d 1 0 0
#    e 1 0 0
...