Реализация в R: Нахождение расстояния между двумя списками символов

Question

Я новичок в R и пытаюсь понять, как реализовать алгоритм, приведенный ниже в R. У меня есть два списка символов, и я хочу посмотреть, каково минимальное расстояние между этими двумя.

List 1: "a", "b", "c"
List 2: "a", "b", "c", "d"

На первом шаге: я создал таблицу, подобную этой:

  a   b   c
a 0   1   2
b 1
c 2
d 3

На втором шаге: я заполнил остальную часть матрицы нулями

  a   b   c
a 0   1   2
b 1   0   0
c 2   0   0
d 3   0   0

Теперь я хочу начать вычисление расстояния между этими двумя списками с помощью этого алгоритма и обновить матрицу:

if (characters_in_header_of_matrix[i]==characters_in_column_of_matrix [j] & value[i,j] == value[i+1][j-1] )
then {get the 'diagonal value' #diagonal value= value[i, j-1]}

else{
value[i,j] = min(value[i-1, j], value[i-1, j-1],  value[i, j-1]) + 1
}
endif

, чтобы найти разницу между двумя списками, которые вы видите в заголовке иВ столбце матрицы я использовал функцию strcmp().Но я не могу реализовать это.Окончательный результат должен выглядеть следующим образом:

  a   b   c
a 0   1   2
b 1   0   1
c 2   1   0
d 3   2   1

Буду признателен за помощь. Спасибо

Answer 1

В R есть несколько вещей, которые вы можете делать грубой силой с помощью for циклов и условных выражений, но их легко можно сделать векторизованным методом.Преимущество может быть в скорости (хотя может и нет), но часто может быть оценено в более простом коде и (как только вы сможете использовать функции) удобочитаемости и удобства обслуживания.

Возьмем, к примеру, эту проблему:

l1 <- c("a", "b", "c")
l2 <- c("a", "b", "c", "d")

Вы хотите найти «расстояние» (точнее, абсолютное расстояние) между каждой буквой в l1 и каждой буквой в l2.Функция outer создает «внешнее произведение» из двух векторов.Например, если бы мы конструктивно (не на самом деле) делали outer(a:c, 1:3), это было бы парами a1, a2, a3, b1, ..., c3.(Это недопустимый код R, он просто используется для демонстрации, хотя это можно сделать довольно легко с помощью нескольких незначительных дополнений.)

В нашем случае, если мы сделаем outer(l1, l2), функция, которая использует значения по умолчаниюк умножению (*), поскольку его первоначальное использование часто находится в линейной алгебре, но эту функцию можно легко переопределить с помощью FUN=.Внутренне, что он делает, это создает два (гораздо более длинных) вектора, выполняющих все спаривания.Мы можем видеть, что происходит под капотом, если мы введем функцию отладки для проверки состояния.

debugfunc <- function(a, b) { browser(); 1; }

(1 там только как заполнитель.)

outer(l1, l2, FUN=debugfunc)
# Called from: FUN(X, Y, ...)
# Browse[2]> 
a # <--- the object 'a' here is the first argument to this function
#  [1] "a" "b" "c" "a" "b" "c" "a" "b" "c" "a" "b" "c"
# Browse[2]> 
b # <--- the second argument
#  [1] "a" "a" "a" "b" "b" "b" "c" "c" "c" "d" "d" "d"

По порядку это пары "a" с "a", затем "b" с "a", затем "c" с "a" и т. Д. Он исчерпывает первый (l1) вектор и затем увеличиваетвторой вектор, повторяющийся, пока оба не исчерпаны.На этом этапе debugfunc вызывается ровно один раз с этими двумя векторами (не один раз на пару, как некоторые подозревают), поэтому ваша функция FUN= должна иметь возможность выполнять все операции за один вызов.

Кто-то может захотеть посмотреть на расстояния здесь.Вы можете определить положение отдельной буквы в алфавите, используя match("a", letters) (компаньон LETTERS - заглавные буквы).В общем, match находит позицию первого аргумента (ов) во втором.Итак, продолжаем в пределах debugfunc:

# Browse[2]> 
match(a, letters)
#  [1] 1 2 3 1 2 3 1 2 3 1 2 3
# Browse[2]> 
match(b, letters)
#  [1] 1 1 1 2 2 2 3 3 3 4 4 4

Так что вы действительно хотите разницу между этими двумя числовыми векторами.Можно легко сделать:

# Browse[2]> 
match(a, letters) - match(b, letters)
#  [1]  0  1  2 -1  0  1 -2 -1  0 -3 -2 -1

, но так как нам нужно абсолютное расстояние, нам действительно нужно

# Browse[2]> 
abs( match(a, letters) - match(b, letters) )
#  [1] 0 1 2 1 0 1 2 1 0 3 2 1

Хорошо, поэтому я думаю, что у нас есть наша функция здесь,Давайте вырвемся из отладчика (Q) и попробуем это немного более формально:

distfunc <- function(a, b) abs( match(a, letters) - match(b, letters) )
outer(l1, l2, FUN=distfunc)
#      [,1] [,2] [,3] [,4]
# [1,]    0    1    2    3
# [2,]    1    0    1    2
# [3,]    2    1    0    1

Обратите внимание, что первый аргумент становится строками, поэтому l1 с длиной 3 дает нам 3 строки,Если вам нужно применить имена строк / столбцов, то:

o <- outer(l1, l2, FUN=distfunc)
dimnames(o) <- list(l1, l2)
o
#   a b c d
# a 0 1 2 3
# b 1 0 1 2
# c 2 1 0 1

(Изменение порядка аргументов даст вам именно ту матрицу, которую вы ищете.)