#r #recursion #combinations
Вопрос:
Я пытаюсь использовать определенный метод сопоставления похожих слов. Пожалуйста, не предлагайте другие алгоритмы сопоставления, если они не используют этот метод. Это делается для расчета значения BI-SIM (для расчета BI-SIM есть несколько дополнительных шагов, но я не буду вдаваться в подробности).
Давайте предположим, что у нас есть два слова — книга и лодка.
Они сравниваются с помощью пар букв: «bo», «oo», «ok» по сравнению с «bo», «oa», «at»
Если пара букв идентична, она получает 1 балл. Если только одна буква (в правильном положении) , она получает 0,5 балла.
Пары букв можно опустить, но в противном случае пары букв нельзя использовать не по порядку.
Самый высокий общий балл требуется, если есть более одного способа набрать очки
| a | b | счет |
|---|---|---|
| бо | бо | 1 |
| oo | о а | 0.5 |
| ОК | около | 0 |
Общий балл 1,5
Этот пример довольно прост. Это становится сложнее, когда мы добавляем более длинное слово, такое как бронирование и мигание
| a | b | оценка b | c | оценка c |
|---|---|---|---|---|
| б о | б л | 0.5 | б л | 0.5 |
| оо | li | 0 | ли, в | 0 |
| о к | в | 0 | с к | 0.5 |
| ки | нк | 0 | ки | 1 |
| в | ки | 0 | в | 1 |
| ng | в | 0 | ng | 1 |
| ng | 0 |
Желаемый балл: 4 (т. е. столбец C)
Я легко могу получить свои комбинации букв в парах
first_word lt;- "booking" second_word lt;- "blinking" fw lt;- strsplit(first_word, "", 2)[[1]] fw_bg lt;- paste(head(fw, -1), tail(fw, -1), sep = "", collapse = NULL) sw lt;- strsplit(second_word, "", 2)[[1]] sw_bg lt;- paste(head(sw, -1), tail(sw, -1), sep = "", collapse = NULL) print(fw_bg) # [1] "bo" "oo" "ok" "ki" "in" "ng" print(sw_bg) # [1] "bl" "li" "in" "nk" "ki" "in" "ng" I can apply the score to an individual pair:
sum(strsplit(fw_bg[1],"")[[1]] == strsplit(sw_bg[1],"")[[1]])/2 #[1] 0.5 sum(strsplit(fw_bg[2],"")[[1]] == strsplit(sw_bg[2],"")[[1]])/2 #[1] 0 sum(strsplit(fw_bg[5],"")[[1]] == strsplit(sw_bg[6],"")[[1]])/2 #[1] 1 But I need some way to iterate through all the options on both fw_bg and sw_bg vectors to get the maximum possible score.
I could compute every possible permutation. But I can’t figure out how to check for a matching permutation
x lt;- sw_bg # Arrangements::combinations will create all the combinations for me # including blank rows. # But it sorts alphabetically - so need to make numerical matrix # then populate the letter pairs. mat lt;- unique( arrangements::combinations( x = c(1:(length(x)), rep("", length(x)-1)), k = (length(x))) ) mt2 lt;- matrix(0, nrow = length(mat[,1]), ncol= length(mat[1,])) # I'm sure there is a slicker way to do this bit # but this bit works for (r in 1:length(mat[,1]) ){ for (c in 1:length(mat[1,])) { mt2[r,c] lt;- x[as.numeric(mat[r,c])] } } head(mt2) [,1] [,2] [,3] [,4] [,5] [,6] [1,] "bo" "oo" "ok" "ki" "in" "ng" [2,] "bo" "oo" "ok" "ki" "in" NA [3,] "bo" "oo" "ok" "ki" "ng" NA [4,] "bo" "oo" "ok" "ki" NA NA [5,] "bo" "oo" "ok" "in" "ng" NA I’ve done the same for sw_bg (into mt3):
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [1,] "bl" "li" "in" "nk" "ki" "in" "ng" [2,] "bl" "li" "in" "nk" "ki" "in" NA [3,] "bl" "li" "in" "nk" "ki" "ng" NA [4,] "bl" "li" "in" "nk" "ki" NA NA [5,] "bl" "li" "in" "nk" "in" "ng" NA Что я хочу, так это сравнить / оценить:
mt2[17,]: [17] "bo" "ok" "ki" "in" "ng" NA mt3[49,]: [49] "bl" "nk" "ki" "in" "ng" NA NA Но я предполагаю, что мне нужно будет набрать каждую комбинацию для каждой комбинации на двух матрицах. Затем выберите максимальный балл.
# Replace NA with a double character (different in each matrix # so they don't match but can be split) mt2[is.na(mt2)] lt;- "--" mt3[is.na(mt3)] lt;- "==" width = min(length(mt2[1,]), length(mt3[1,])) score lt;- 0 for (r in 1: length(mt2[,1])) { for (rr in 1:length(mt3[,1])) { rr_score lt;- sum(unlist(strsplit(mt2[r,1:width],""))== unlist(strsplit(mt3[rr,1:width],"")), na.rm=T)/2 if (rr_score gt; score) { score lt;- rr_score } } } cat(score) # 4 Думают ли люди, что есть более эффективный способ сделать это?
Мой сценарий довольно быстр с мелкими словами. Но у меня будет несколько длинных слов длиной 10 символов для сравнения с другими 10 символами, и на одно вычисление уйдет больше минуты.
Комментарии:
1. «Пары букв можно опустить, но в противном случае пары букв нельзя использовать не по порядку» разрешено ли вам несколько пробелов? например , если у нас было
tookиokay, можноokли сравнить буквы s?2. Да, насколько мне известно. Фактическая опубликованная реализация помещает другой префиксный символ перед словом, что фактически дает дополнительные баллы за слово, начинающееся с той же буквы. к, оо, ок против ок, ка, ай по моему описанию выше 1 балл за соответствие ок. В опубликованной реализации они будут использовать Tt, to, oo, ok и Oo, ok, ka, ay, которые набирают 1,5 балла (Oo ~ oo, ok = ok), и они делят его на максимальную длину слова (4), так что это дает 0,375 балла при их реализации. Я протестировал teek и ok, и он набрал 0,125 балла (так что для соответствующего k в ok ~ ek есть 0,5 балла).
Ответ №1:
Вы тратите много времени на str_split unlist свои циклы и в них. Если вы замените строковую матрицу символьной матрицей с двойным количеством столбцов.
Затем используйте стандартные apply и expand.grid , чтобы избежать вложенных for циклов.
... mt2x lt;- t(apply(mt2, 1, function(x) (unlist(strsplit(x, ""))))) mt3x lt;- t(apply(mt3, 1, function(x) (unlist(strsplit(x, ""))))) widths lt;- seq(min(ncol(mt2x), ncol(mt3x))) rows_to_compare lt;- expand.grid(seq(nrow(mt2x)), seq(nrow(mt3x))) scores lt;- apply(rows_to_compare, 1, function(x) sum(mt2x[x[1], widths] == mt3x[x[2], widths]) / 2) max(scores) ...