Zählen Sie das Auftreten aller möglichen Teilstrings und deren Auftreten

Question

Gegeben eine Zeichenfolge, ich möchte jede mögliche Teilzeichenfolge in der Zeichenfolge berechnet. Zum Beispiel gegeben einen String

str = "abab" 

Ich möchte alle möglichen Teilstrings und ihre Werte berechnen:

"A" = 2 
"B" = 2 
"AA" = 0 
"AB" = 2 
"BA" = 1 
"BB" = 0 

I wie unten eine Funktion geschrieben haben:

countSubstrings <- function(string_try ="", items = NULL) 
{ 
    string_try <- toupper(string_try) 

    if(is.null(items)) 
    { 
    items <- strsplit(string_try, "")[[1]] 
    } 

    n <- length(unique(items)) 

    counts_substrings <- c() 
    substrings_all <- c() 

    for (i in 1:n) # Number of characters in substring 
    { 
    substrings_combo <- gtools::permutations(n, i, unique(items), repeats=TRUE) 

    print(paste("The number of combinations is: ", 
      nrow(substrings_combo), "for substrings of length", i)) 

    for(j in 1:nrow(substrings_combo)) 
    { 
     tosearch <- paste(substrings_combo[j,], collapse = "") 

     substrings_all <- c(substrings_all, tosearch) 

     total <- sum(grepl(tosearch, 
       sapply(1:(nchar(string_try) - 1), 
         function(ii) substr(string_try, ii, ii + 1)))) 

     counts_substrings <- c(counts_substrings, find_overlaps(tosearch, string_try)) 

    } 
    } 

    return(list(substrings_all,counts_substrings)) 
} 

Es tut, was ich will aber es ist lächerlich langsam. Ein möglicher Fehler, den ich sehe, ist, dass mein Programm Teilstrings "aaa" betrachtet, selbst wenn das Auftreten von "aa" gleich Null ist. Dies ist in der Sequenzanalyse und im Muster-Mining beliebt. Ich frage mich, ob es schon eine schnellere Implementierung gibt oder irgendwie optimiert werden kann. Brauchen Sie eine R-Lösung.

Answer 1

Alle aufeinander folgenden Teilstrings? Ihr Beispiel hat einige Werte von 0, die keine Teilstrings als solche sind.

Wie wäre:

eine Funktion erstellen, die Extrakte (not just unique) Teillängen n

allsubstr <- function(x, n) substring(x, 1:(nchar(x) - n + 1), n:nchar(x)) 

Diese jede Gruppe von 1 extrahieren, 2, 3, ..., n Teil

allsubstr("abab", 1) 
#> [1] "a" "b" "a" "b" 
allsubstr("abab", 2) 
#> [1] "ab" "ba" "ab" 
allsubstr("abab", 3) 
#> [1] "aba" "bab" 
allsubstr("abab", 4) 
#> [1] "abab" 

dann kann dies für 1 bis zur Länge der gewünschten Zeichenfolge wiederholt werden, und eine Tabelle der Vorkommen erstellt

Einschließlich aller anderen möglichen Zeichenkombinationen ist dies eine mögliche Erweiterung und erfordert nur die Überprüfung einer Liste der Kombinationen mit dieser Tabelle.

Answer 2

I quanteda Paket sehr nützlich für diese Art von Operationen finden,

library(quanteda) 
x <- "abab" 

ngrams(strsplit(x, '')[[1]], n = 2, concatenator = '') 
#[1] "ab" "ba" "ab" 

#or 
table(ngrams(strsplit(x, '')[[1]], n = 2, concatenator = '')) 
#ab ba 
# 2 1 

#or to get all combinations, 
unlist(sapply(1:nchar(x), function(i)table(ngrams(strsplit(x, '')[[1]], n = i, concatenator = '')))) 
#a b ab ba aba bab abab 
#2 2 2 1 1 1 1