The Wu-Manber Algorithm: Architecture of Ultrafast Multiple String Matching

The problem of stream filtering hundreds and thousands of banned words (profanity, spam patterns, stop words) in comments requires deterministic execution time and minimal memory consumption. The Wu-Manber algorithm, developed in 1992, remains one of the most efficient solutions for multiple substring matching. It combines the shift heuristic from the Boyer-Moore algorithm with block character hashing.

Evolution of Solutions: From Simple to Complex

Before implementing Wu-Manber, it is necessary to understand why standard approaches fail to scale on high-load streams.

1. Naive Search (Regex and String.Contains)

In a basic scenario, developers use String.Contains in a loop for each pattern or combine them into a single regular expression (word1|word2|...).

  • Complexity: O(N * K), where N is the text length and K is the number of patterns.
  • Weakness: Compiling a large number of alternatives in regular expressions creates bloated finite state machines (DFA/NFA), leading to a catastrophic drop in performance (Catastrophic Backtracking) and high CPU consumption.

2. Aho-Corasick Algorithm

The official standard for multiple string matching, based on a prefix tree (Trie) with suffix links.

  • Complexity: O(N + M + Z), where M is the total length of all patterns, and Z is the number of occurrences found.
  • Weakness: High memory consumption. Each tree node requires storing links to child elements. The text is read character by character (strictly O(N)); the algorithm cannot “jump” over sections of text.

3. Wu-Manber Algorithm

Instead of character-by-character reading from left to right, Wu-Manber examines blocks of text and allows for jumps, skipping sections that are guaranteed not to match.

  • Complexity: In the best case, sublinear O(N / m), where m is the length of the shortest pattern.
  • Strength: The more patterns there are, the denser the hash table becomes, but the jumps remain long. It is excellent for dictionaries ranging from 100 to 10,000 words with text lengths of several kilobytes.

Anatomy of the Wu-Manber Algorithm

The algorithm operates on three key parameters:

  • K — the number of searched patterns.
  • m — the minimum pattern length in the set. The algorithm aligns all patterns by their first m characters.
  • B — the block size (usually 2 or 3 characters).

Stage 1: Preprocessing (SHIFT and HASH Tables)

The algorithm builds two data structures:

  1. SHIFT Table. An array where the index is the hash of a character block of size B. The value indicates how many characters forward the search “window” can be safely shifted in the text.
    • By default (if the block does not occur in any pattern), the shift value is m - B + 1.
    • If the block occurs in a pattern at position q (where q is the index of the end of the block), the shift is m - q.
  2. HASH Table. A hash table (or array of lists) used when the value in the SHIFT table is 0. It stores a list of patterns ending with the given block hash for exact character-by-character verification.

Stage 2: Scanning

The text is scanned in windows of size m. In each window, the suffix (the last B characters) is taken. Its hash is calculated.

  • The value is extracted from the SHIFT table using this hash.
  • If the shift is > 0, the window is shifted to the right by this value.
  • If the shift is == 0, it means the window’s suffix matches the end of one of the patterns. The HASH table is accessed, the list of possible patterns is extracted, and they are verified character by character against the text. After the check, the window shifts by 1.

Custom Implementation in F#

The code is designed with immutability in mind where it does not harm performance, but it uses mutable arrays for the SHIFT and HASH tables, as O(1) access speed is critical for string algorithms.

F#

module TechMacro.StringSearch.WuManber

open System.Collections.Generic

/// Structure for storing precalculated algorithm data
type WuManberContext = {
    Patterns: string[]
    MinLength: int
    BlockSize: int
    TableSize: int
    ShiftTable: int[]
    HashTable: Dictionary<int, List<string>>
}

/// Calculates a simple hash for a block of characters
let inline getHash (text: string) (endIdx: int) (blockSize: int) (tableSize: int) =
    let mutable h = 0
    for i = endIdx - blockSize + 1 to endIdx do
        h <- (h <<< 5) ^^^ int text.[i]
    abs (h % tableSize)

/// Initialization stage (executed once at service startup)
let buildContext (patterns: string[]) (blockSize: int) =
    if patterns.Length = 0 then 
        invalidArg "patterns" "The pattern dictionary cannot be empty."
    
    let minLen = patterns |> Array.map String.length |> Array.min
    if minLen < blockSize then
        invalidArg "blockSize" "Block size B cannot be greater than the length of the shortest pattern."

    // For B=2, a table size of 64k (2^16) is usually optimal to avoid collisions
    let tableSize = 65536 
    let defaultShift = minLen - blockSize + 1
    
    let shiftTable = Array.create tableSize defaultShift
    let hashTable = Dictionary<int, List<string>>()

    // Filling the SHIFT table
    for p in patterns do
        let prefix = p.Substring(0, minLen) // Working only with a prefix of length minLen
        for i = blockSize - 1 to minLen - 1 do
            let hash = getHash prefix i blockSize tableSize
            let shift = minLen - 1 - i
            
            // Writing the minimum possible shift
            if shiftTable.[hash] > shift then
                shiftTable.[hash] <- shift

            // Filling the HASH table for zero shifts (prefix suffixes)
            if shift = 0 then
                if not (hashTable.ContainsKey(hash)) then
                    hashTable.[hash] <- List<string>()
                if not (hashTable.[hash].Contains(p)) then
                    hashTable.[hash].Add(p)

    {
        Patterns = patterns
        MinLength = minLen
        BlockSize = blockSize
        TableSize = tableSize
        ShiftTable = shiftTable
        HashTable = hashTable
    }

/// Text stream scanning stage
let search (ctx: WuManberContext) (text: string) : string seq =
    seq {
        let n = text.Length
        let mutable i = ctx.MinLength - 1

        while i < n do
            let hash = getHash text i ctx.BlockSize ctx.TableSize
            let shift = ctx.ShiftTable.[hash]

            if shift > 0 then
                // Safe jump
                i <- i + shift
            else
                // Potential match, checking the HASH table
                if ctx.HashTable.ContainsKey(hash) then
                    let candidates = ctx.HashTable.[hash]
                    let startPos = i - ctx.MinLength + 1
                    
                    for p in candidates do
                        let pLen = p.Length
                        // Checking if the word exceeds the text boundaries
                        if startPos + pLen <= n then
                            let mutable matchFound = true
                            let mutable j = 0
                            while matchFound && j < pLen do
                                if text.[startPos + j] <> p.[j] then
                                    matchFound <- false
                                j <- j + 1
                            
                            if matchFound then
                                yield p
                
                // After checking a zero shift, always move 1 character forward
                i <- i + 1
    }

Usage

F#

let badWords = [| "spam"; "scam"; "crypto"; "casino"; "buy now" |]
let context = buildContext badWords 2

let comment = "Hello, please buy now our amazing crypto tokens, totally not a scam!"
let foundWords = search context comment |> Seq.toList
// Result: ["buy now"; "crypto"; "scam"]

Architectural Anti-patterns: What Not to Do

1. Adding Short Words to the Common Dictionary

Mistake: Adding words of 1-2 characters in length (e.g., prepositions or short abbreviations) to the common array of Wu-Manber patterns.

Consequence: The parameter m (minimum pattern length) becomes 2. The maximum algorithm jump m - B + 1 (with B=2) becomes 1. The algorithm degrades to character-by-character scanning O(N), losing all its advantages and running slower than standard Aho-Corasick.

Solution: Separate dictionaries by length. Search for short words (length < 3) using a separate lightweight algorithm, and use Wu-Manber for the bulk of words 3 characters and longer.

2. Ignoring Unicode Surrogate Pairs

Mistake: Working with text at the char level in C#/F#, assuming that 1 char = 1 visual character (grapheme).

Consequence: Emojis and rare characters occupy 2 chars (a surrogate pair). If the hash window splits a surrogate pair in half, the shift calculation will execute, but the character-by-character verification might throw an index out-of-bounds exception or yield a false positive.

Solution: For strict moderation systems, normalize the text beforehand (removing diacritics, converting to lowercase) and use System.Globalization.StringInfo for proper grapheme splitting if the patterns contain complex Unicode structures.

3. String Allocation During Verification

Mistake: Using text.Substring(startPos, pLen) == p inside the verification loop upon a zero shift.

Consequence: Allocating new memory in the Heap for every false positive. In a high-load stream, this triggers aggressive Garbage Collector (GC) activity, leading to CPU micro-freezes.

Solution: Verification must strictly rely on indices of the original string text.[startPos + j] <> p.[j], as implemented in the example above, or use ReadOnlySpan<char>.

Comparison with Competitors

AlgorithmAdvantagesDisadvantagesTarget Scenario
Aho-CorasickGuaranteed O(N) execution time. Independent of the shortest word length.High RAM consumption. Slower on long texts without matches.Token and short command search. Systems with abundant memory (e.g., routing).
Rabin-KarpSimple to implement. Excels at searching for a single pattern or patterns of strictly the same length.Terrible performance with patterns of varying lengths. High collision rate.Plagiarism checkers (where block size is fixed, e.g., 50 characters).
Wu-ManberJumps save CPU (up to O(N/m)). Excellent performance with thousands of varying-length patterns.Requires B tuning. Vulnerable to the presence of very short patterns.Comment filtering, chat moderation, antivirus scanning (signatures).

FinOps: Infrastructure Costs

If you isolate comment moderation into a separate microservice on Google Cloud Run:

  • Memory Usage: A Wu-Manber instance with a 65,536-entry table consumes less than 2 MB of RAM. Unlike Aho-Corasick, which can consume 50-100 MB per tree for a 10,000-word dictionary.
  • CPU / Costs: Thanks to the jumps, a single vCPU (in Cloud Run) can process tens of thousands of comments per second. This allows restricting the microservice to the lowest tier (1 vCPU, 512MB RAM, concurrency=80). The cost of processing 1 million comments will approach the base network overhead of Cloud Run (under $0.50).

Lesser-Known Features of the Tool

  • Combining with a Bloom Filter: In systems with extreme loads (e.g., DPI routers), a Bloom Filter can be placed before calling the HashTable on a 0 shift. Using an additional fast hash, it will filter out 99% of block hash collisions, preventing costly character-by-character verification.
  • Prefix Table: In the original paper, the authors suggest storing not only the words themselves along with the HASH table but also the hashes of their first B characters. Then, upon a zero shift, the algorithm first verifies the word’s prefix, and only upon a match does it initiate the full while loop. This radically accelerates the algorithm when scanning natural languages with a large number of cognates.

Similar Posts