统计所有可能子串的出现次数及其出现次数

Question

给定一个字符串，我想计算字符串中出现的每个可能的子字符串。例如，给定一个字符串

str = "abab"

我想计算所有可能的子字符串及其值：

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

我写了一个函数如下：

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))
}

它可以满足我的要求，但速度慢得离谱。我看到的一个潜在缺陷是，即使 "aa" 的出现次数为零，我的程序也会考虑子字符串 "aaa"。这在序列分析和模式挖掘中很流行。我想知道是否已经有更快的实现或者可以以某种方式对其进行优化。需要一个 R 解决方案。

Answer 1

所有连续的子串？你的例子有一些 0 的值，它们本身不是子字符串。

怎么样：

创建一个提取 () 个长度为 n

的子字符串的函数

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

这可以提取任意一组 1, 2, 3, ..., n 个子串

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"

然后可以迭代 1 到所需字符串的长度，并创建 table 次出现

substrings_table <- function(string) table(unlist(sapply(1:nchar(string), allsubstr, x=string)))

substrings_table("abab")
#>  a   ab  aba abab    b   ba  bab 
#>  2    2    1    1    2    1    1

包括所有其他可能的字符组合是对此的潜在扩展，只需要根据此检查组合列表 table。

Answer 2

我发现 quanteda 包对这些类型的操作非常有用，

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

统计所有可能子串的出现次数及其出现次数

Count the occurrence of all possible substrings and their occurrence

string

r

frequency