AhoCorasickSearch {AhoCorasickTrie}R Documentation

Fast searching for one or more keywords in one or more texts


Builds an Aho-Corasick trie from one or more keywords and uses it to search one or more texts. For a large number of keywords, Aho-Corasick is much faster than a naive approach (such as lapply(keywords, gregexpr, text)).

Use AhoCorasickSearchList instead of AhoCorasickSearch when you want to keep the matches of each input text separate. If the input texts have names, the resulting list of matches will include those names and non-matched texts will be excluded from the results. If the input texts do not have names, then the resulting list of matches will be in the same order as the input texts, and non-matched texts will be kept to preserve that order. Thus, it is more efficient to use named input texts (so non-matched texts can be dropped).

The default alphabet allows all 128 ASCII characters in the keywords and the texts. Characters outside this range will cause an error. A more efficient trie is possible if the alphabet size can be reduced. For example, DNA sequences use at most 19 distinct characters and usually only 4; protein sequences use at most 26 distinct characters and usually only 20. Set the alphabet parameter if a reduced alphabet is appropriate.

UTF-8 (Unicode) matching is not currently supported.


  alphabet = "ascii",
  groupByKeyword = FALSE,
  iterationFeedback = 0L



Character vector of one or more keywords


Character vector of one or more texts to search


Alphabet to use; one of ascii, aminoacid, or nucleicacid


If true, matches are grouped by keyword (instead of by text)


When set to a positive integer i, console output will indicate when searching every ith text


List of matches, grouped by either text or by keyword

See Also


listEquals = function(a, b) { is.null(unlist(a)) && is.null(unlist(b)) ||
                              !is.null(a) && !is.null(b) && all(unlist(a) == unlist(b)) }

# 1. Search for multiple keywords in a single text
keywords = c("Abra", "cadabra", "is", "the", "Magic", "Word")
oneSearch = AhoCorasickSearch(keywords, "Is Abracadabra the Magic Word?")
stopifnot(listEquals(oneSearch[[1]][[1]], list(keyword="Abra", offset=4)))
stopifnot(listEquals(oneSearch[[1]][[2]], list(keyword="cadabra", offset=8)))
stopifnot(listEquals(oneSearch[[1]][[3]], list(keyword="the", offset=16)))
stopifnot(listEquals(oneSearch[[1]][[4]], list(keyword="Magic", offset=20)))
stopifnot(listEquals(oneSearch[[1]][[5]], list(keyword="Word", offset=26)))

# 2. Search multiple named texts in a named list with keyword grouping and aminoacid alphabet
# * all matches to a keyword are accessed by name
# * non-matched keywords are dropped
peptides = c("PEPTIDE", "DERPA", "SEQUENCE", "KEKE", "PEPPIE")

peptideSearch = AhoCorasickSearch(peptides, proteins, alphabet="aminoacid", groupByKeyword=TRUE)
stopifnot(listEquals(peptideSearch$PEPTIDE, list(list(keyword="protein1", offset=1),
                                                 list(keyword="protein1", offset=8),
                                                 list(keyword="protein1", offset=37),
                                                 list(keyword="protein2", offset=38))))
stopifnot(listEquals(peptideSearch$DERPA, list(list(keyword="protein2", offset=1),
                                               list(keyword="protein2", offset=6))))
stopifnot(listEquals(peptideSearch$SEQUENCE, list(list(keyword="protein2", offset=47))))
stopifnot(listEquals(peptideSearch$KEKE, list(list(keyword="protein1", offset=29),
                                              list(keyword="protein1", offset=31),
                                              list(keyword="protein1", offset=33))))
stopifnot(listEquals(peptideSearch$PEPPIE, NULL))

# 3. Grouping by keyword without text names: offsets are given without reference to the text
names(proteins) = NULL
peptideSearch = AhoCorasickSearch(peptides, proteins, groupByKeyword=TRUE)
stopifnot(listEquals(peptideSearch$PEPTIDE, list(1, 8, 37, 38)))
stopifnot(listEquals(peptideSearch$DERPA, list(1, 6)))
stopifnot(listEquals(peptideSearch$SEQUENCE, list(47)))
stopifnot(listEquals(peptideSearch$KEKE, list(29, 31, 33)))

[Package AhoCorasickTrie version 0.1.2 Index]