r - स्ट्रिंग्स के बीच लेवेंसहाइट दूरी की गणना के लिए किए गए संचालन को कैसे जानें?




string levenshtein-distance (2)

Tmfmnk के उत्तर और "ट्रैफ़ोस" विशेषता के साथ खेलने के सुझाव को देखते हुए, यहां एक फ़ंक्शन है जो आपको सम्मिलित या प्रतिस्थापित किए गए सभी वर्णों की एक तालिका दिखाएगा, और उन्हें कितनी बार डाला और प्रतिस्थापित किया गया। यदि आप all_actions = T सेट 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

फ़ंक्शन stringdist , मैं स्ट्रिंग्स के बीच stringdist दूरी की गणना कर सकता हूं: यह एक स्ट्रिंग को दूसरे में बदलने के लिए आवश्यक विलोपन, सम्मिलन और प्रतिस्थापन की संख्या को stringdist । उदाहरण के लिए, stringdist("abc abc","abcd abc") = 1 क्योंकि "डी" को दूसरे स्ट्रिंग में डाला गया था।

क्या दो तारों के बीच लेवेंशेटिन दूरी प्राप्त करने के लिए किए गए संचालन को जानना संभव है? या फिर उन पात्रों को जानने के लिए जो 2 तारों के बीच भिन्न हैं (इस उदाहरण में, केवल "डी")? धन्यवाद।

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

मैं जानना चाहूंगा कि:

  • "d" डाला गया था

  • "ई" डाला गया था

  • "b" को "c" में प्रतिस्थापित किया गया था

या अधिक सरल रूप से, मैं सूची ("डी", "ई", "सी") रखना चाहूंगा।


इसे नीडलमैन-वून्श एल्गोरिथम के रूप में जाना जाता है । यह दो तारों के बीच की दूरी और साथ ही तथाकथित ट्रेसबैक की गणना करता है, जो आपको संरेखण को फिर से संगठित करने की अनुमति देता है।

चूंकि जैविक अनुक्रमों की तुलना करते समय यह समस्या ज्यादातर जीव विज्ञान में होती है, इसलिए यह एल्गोरिथ्म (और संबंधित) आर पैकेज {Biostrings} में लागू किया जाता है, जो {Biostrings} का हिस्सा है।

चूँकि यह पैकेज लागू होता है, इसलिए सामान्य लेवेनशीन दूरी की तुलना में अधिक सामान्य समाधान होते हैं, उपयोग दुर्भाग्य से अधिक जटिल होता है, और उपयोग विगनेट समान रूप से लंबा होता है। लेकिन आपके उद्देश्यों के लिए मौलिक उपयोग इस प्रकार है:

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)

- दूसरे तार में प्रत्येक वर्ण के लिए यह मूल वर्ण में संबंधित वर्ण प्रदान करता है, सम्मिलित वर्णों की जगह - । मूल रूप से, यह पहली स्ट्रिंग को दूसरी स्ट्रिंग में बदलने के लिए एक "नुस्खा" है। ध्यान दें कि इसमें केवल सम्मिलन और प्रतिस्थापन होंगे, हटाएं नहीं। इन्हें प्राप्त करने के लिए, आपको दूसरे तरीके के राउंड को संरेखित करने की आवश्यकता है (यानी स्ट्रिंग तर्क को स्वैप करना)।





stringdist