najdłuższy wspólny podciąg w R znalezienie nieciągłych dopasowań pomiędzy dwoma ciągami

Question

Mam pytanie dotyczące znalezienia najdłuższego wspólnego podciągu w R. Podczas przeszukiwania kilku postów na StackOverflow, dowiedziałem się o pakiecie qualV. Jednakże widzę, że funkcja LCS w tym pakiecie faktycznie znajduje wszystkie znaki ze string1, które są obecne w string2, nawet jeśli nie sąsiadują ze sobą.

Aby wyjaśnić, czy ciągi są łańcuch1: "Hel lo" łańcuch2: "hel 12345lo" Spodziewam wyjście być hel, jednak mam wyjście jako cześć. Muszę robić coś złego. Zobacz mój kod poniżej.

library(qualV) 
a= "hello" 
b="hel123l5678o" 
sapply(seq_along(a), function(i) 
    paste(LCS(substring(a[i], seq(1, nchar(a[i])), seq(1, nchar(a[i]))), 
       substring(b[i], seq(1, nchar(b[i])), seq(1, nchar(b[i]))))$LCS, 
      collapse = "")) 

Próbowałem również metody Rlibstree, ale nadal pobierają ciągi, które nie sąsiadują. Również długość podciągu jest również wyłączona z moich oczekiwań. Patrz poniżej.

> a = "hello" 
> b = "h1e2l3l4o5" 

> ll <- list(a,b) 
> lapply(data.frame(do.call(rbind, ll), stringsAsFactors=FALSE), function(x) getLongestCommonSubstring(x)) 
$do.call.rbind..ll. 
[1] "h" "e" "l" "o" 

> nchar(lapply(data.frame(do.call(rbind, ll), stringsAsFactors=FALSE), function(x) getLongestCommonSubstring(x))) 
do.call.rbind..ll. 
       21 

Answer 1

Nie jestem pewien, co zrobiłeś, aby uzyskać wynik "cześć". W oparciu o eksperymenty prób i błędów poniżej, wydaje się, że funkcja LCS będzie (a) nie traktować ciągu jako LCS, jeśli znak podąża za czymś, co inaczej byłoby LCS; (b) znaleźć wiele, równie długich LCS (w przeciwieństwie do sub(), który znajduje się tylko pierwszy); (c) kolejność elementów w łańcuchach nie ma znaczenia - co nie ma ilustracji poniżej; oraz (b) kolejność ciągów w wywołaniach LCS nie ma znaczenia - również nie pokazano.

Twoje "cześć" nie miało LCS w b, ponieważ po "hel" z b pojawił się znak. Cóż, to moja obecna hipoteza.

Punkt A powyżej:

a= c("hello", "hel", "abcd") 
b= c("hello123l5678o", "abcd") 
print(LCS(a, b)[4]) # "abcd" - perhaps because it has nothing afterwards, unlike hello123... 

a= c("hello", "hel", "abcd1") # added 1 to abcd 
b= c("hello123l5678o", "abcd") 
print(LCS(a, b)[4]) # no LCS!, as if anything beyond an otherwise LCS invalidates it 

a= c("hello", "hel", "abcd") 
b= c("hello1", "abcd") # added 1 to hello 
print(LCS(a, b)[4]) # abcd only, since the b hello1 has a character 

punkt B powyżej:

a= c("hello", "hel", "abcd") 
b= c("hello", "abcd") 
print(LCS(a, b)[4]) # found both, so not like sub vs gsub of finding first or all 

Answer 2

Oto trzy możliwe rozwiązania.

library(stringi) 
library(stringdist) 

a <- "hello" 
b <- "hel123l5678o" 

## get all forward substrings of 'b' 
sb <- stri_sub(b, 1, 1:nchar(b)) 
## extract them from 'a' if they exist 
sstr <- na.omit(stri_extract_all_coll(a, sb, simplify=TRUE)) 
## match the longest one 
sstr[which.max(nchar(sstr))] 
# [1] "hel" 

Istnieje również adist() i agrep() bazy B, a pakiet stringdist ma kilka funkcji, które działają w sposób LCS. Oto spojrzenie na stringsidt. Zwraca liczbę niesparowanych znaków.

stringdist(a, b, method="lcs") 
# [1] 7 

Filter("!", mapply(
    stringdist, 
    stri_sub(b, 1, 1:nchar(b)), 
    stri_sub(a, 1, 1:nchar(b)), 
    MoreArgs = list(method = "lcs") 
)) 
# h he hel 
# 0 0 0 

Teraz kiedy zbadaliśmy to nieco więcej, myślę adist() może być droga. Jeśli ustawimy wartość counts=TRUE, otrzymamy sekwencję dopasowań, wstawień itp. Jeśli więc podasz tę wartość do stri_locate(), możemy użyć tej macierzy, aby uzyskać dopasowania od a do b.

ta <- drop(attr(adist(a, b, counts=TRUE), "trafos"))) 
# [1] "MMMIIIMIIIIM" 

więc wartości M oznaczają prosto meczów. Możemy iść i dostać podciągi z stri_sub()

stri_sub(b, stri_locate_all_regex(ta, "M+")[[1]]) 
# [1] "hel" "l" "o" 

Niestety nie wyjaśniły, że bardzo dobrze, jak nie jestem dobrze zorientowany w algorytmach odległość ciąg.

Answer 3

Wykorzystując @ wglądu RichardScriven że adist mogą być używane, ale funkcja ta łączy w sobie to wszystko,

EDIT To było trudne, ponieważ musieliśmy dostać się longest_string w dwóch kontekstach, więc zrobiłem tę funkcję:

longest_string <- function(s){return(s[which.max(nchar(s))])} 

ten łączy @ pracy RichardSriven za pomocą biblioteki ...

library(stringi) 
library(stringdist) 
lcsbstr <- function(a,b) { 
    sbstr_locations<- stri_locate_all_regex(drop(attr(adist(a, b, counts=TRUE), "trafos")), "M+")[[1]] 
    cmn_sbstr<-stri_sub(longest_string(c(a,b)), sbstr_locations) 
    longest_cmn_sbstr <- longest_string(cmn_sbstr) 
    return(longest_cmn_sbstr) 
} 

możemy przepisać go do uniknięcia stosowania żadnych zewnętrznych bibliotek (ale nadal używa adist) ...

lcsbstr_no_lib <- function(a,b) { 
    matches <- gregexpr("M+", drop(attr(adist(a, b, counts=TRUE), "trafos")))[[1]]; 
    lengths<- attr(matches, 'match.length') 
    which_longest <- which.max(lengths) 
    index_longest <- matches[which_longest] 
    length_longest <- lengths[which_longest] 
    longest_cmn_sbstr <- substring(longest_string(c(a,b)), index_longest , index_longest + length_longest - 1) 
    return(longest_cmn_sbstr) 
} 

Wszystkie zidentyfikować tylko 'hello ' jak najdłuższego wspólnego podciągu, zamiast "hello r':

identical('hello ', 
    lcsbstr_no_lib('hello world', 'hello there'), 
    lcsbstr(  'hello world', 'hello there')) 

EDIT A ponieważ edycji, działa niezależnie od tego, który argument jest już od dwóch:

identical('hello', 
    lcsbstr_no_lib('hello', 'hello there'), 
    lcsbstr(  'hello', 'hello there'), 
    lcsbstr_no_lib('hello there', 'hello'), 
    lcsbstr(  'hello there', 'hello')) 

OSTATNIA EDYCJA Ale to jest dobre tylko, jeśli akceptujesz to zachowanie. Wskazówka ten wynik:

lcsbstr('hello world', 'hello') 
#[1] 'hell' 

Spodziewałem 'hello', ale ponieważ transformacja rzeczywiście porusza się (poprzez skreślenie) W o rld stać się piekło o, więc tylko cholery część jest uważany dopasowanie według M:

drop(attr(adist('hello world', 'hello', counts=TRUE), "trafos")) 
#[1] "MMMMDDDMDDD" 
#[1] vvvv v 
#[1] "hello world" 

zachowanie można zaobserwować przy użyciu [narzędzie Levenstein] - daje dwa możliwe rozwiązania, równoważne z tymi dwie transformacje; czy możemy powiedzieć adist, który wolimy? (Jeden z większej liczby kolejnych M)

#[1] "MMMMDDDMDDD" 
#[1] "MMMMMDDDDDD" 

Wreszcie, nie zapomnij adist pozwala przechodzić w ignore.case = TRUE (FALSE jest domyślne)