EMZETT.
Login

Emzett Wiki

Text search algorithms: naive, KMP, Boyer-Moore and Rabin-Karp

Properties1
tagsglossar, algorithmen, strings

2 min read

Text search algorithms: naive, KMP, Boyer-Moore and Rabin-Karp

In short: To find a pattern in a text, naive search compares position by position; KMP, Boyer-Moore and Rabin-Karp use prior knowledge about the pattern to skip comparisons.

In more detail: Ctrl+F, grep, editors, plagiarism checks, DNA search: everywhere a pattern (length m) is searched in a text (length n). The right method depends on length, alphabet and number of searches.

In Depth

Naive

Place the pattern at every position of the text and compare characters; on mismatch shift by one.

def search(text, pattern):
    n, m = len(text), len(pattern)
    return [i for i in range(n - m + 1) if text[i:i + m] == pattern]

Worst case O(n·m) (text aaaa…a, pattern aaab); on average with natural text often close to O(n) and practically sufficient (Python’s in, str.find use optimised variants).

Knuth-Morris-Pratt (KMP)

Computes a table beforehand (prefix/failure function): how long is the longest proper prefix of the pattern that is also a suffix of what has been read so far? On a mismatch you jump back in the pattern without re-reading the text. O(n + m), no going back in the text (good for data streams). Example pattern ABABC: table [0,0,1,2,0].

Boyer-Moore and Rabin-Karp

  • Boyer-Moore: compares the pattern from the back; with bad-character and good-suffix rules it often skips whole chunks (on average sublinear, especially with long patterns/large alphabet). Basis of grep and many editors (Horspool variant).
  • Rabin-Karp: computes hash values (rolling hash) of the pattern and each text window; compares only on equal hash. Several patterns at once, good for plagiarism detection. Expected O(n + m), worst case O(n·m) with many hash collisions.
  • Aho-Corasick: searches many patterns in parallel (virus scanners, word filters).
  • Suffix trees/arrays: many searches in the same text (bioinformatics).
  • Regular expressions (see regex) extend to patterns with wildcards/repetitions: implemented via finite automata.
  • Fuzzy search: edit distance (Levenshtein), n-grams, phonetics (Cologne phonetics) for typos/names; search engines (inverted index, Elasticsearch) for documents.
  • Unicode/case: normalise (NFC), casefold.
  • Choice: single search → built-in function; many searches in the same text → index; many patterns → Aho-Corasick; streaming → KMP.
  • Exam: show the procedure by hand on a small example, compare running times.

See also: Regex, Big-O notation, Hashmap, Bloom filter and trie

Backlinks