String Search and Bloom Filters

String Search and Bloom Filters

Substring pattern searching and membership testing are core building blocks for log ingestion, audit trails, and web security proxies. When searching inside massive text streams or verifying whether an order ID exists among millions of records, brute-force checks consume unnecessary CPU cycles and database disk I/O. The boring default in Python is 'pattern' in text and native set objects, but Rabin-Karp rolling hashing and Bloom Filters introduce essential algorithmic and probabilistic efficiencies.

Mental model

Rabin-Karp Rolling Hash

Rather than comparing characters at every position (\(O(n \times m)\)), Rabin-Karp computes a polynomial rolling hash of the pattern. When sliding the window by one character, it subtracts the leaving character and adds the entering character in \(O(1)\) arithmetic:

Text:    [ B O R I N G ] - P Y
Window:  [ B O R ]       Hash = 1042 (Pattern hash: 9811 -> Mismatch)
Slide:     [ O R I ]     Hash = (1042 - 'B'*base) * base + 'I' in O(1)

Bloom Filter: Probabilistic Membership

A Bloom filter is a compact bit array paired with \(k\) independent hash functions:

Bit Array (m bits):
Index:  [ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 ]
Bits:   [ 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 ]
              ^       ^           ^
              h1(ID)  h2(ID)      h3(ID)

1. Insert: Compute \(k\) hash values for an item and set those bit indices to 1.
2. Lookup: Compute \(k\) hash values:
   • If any bit is 0: The item is definitely NOT in the set (0% False Negatives).
   • If all bits are 1: The item is probably in the set (with a small, mathematically tunable False Positive rate).

This allows high-throughput APIs to reject 99% of invalid requests in memory before hitting expensive databases or object storage.

Worked examples

Case 1: Rabin-Karp Rolling Hash Substring Search

Save as rabin_karp.py. Search for audit keywords across log strings in linear time.

# rabin_karp.py
def rabin_karp_search(text: str, pattern: str) -> int:
    n = len(text)
    m = len(pattern)
    if m == 0 or n < m:
        return -1

    base = 256
    mod = 1_000_000_007

    # Calculate base^(m-1) % mod
    h = pow(base, m - 1, mod)

    pattern_hash = 0
    window_hash = 0

    # Initial hash values
    for i in range(m):
        pattern_hash = (base * pattern_hash + ord(pattern[i])) % mod
        window_hash = (base * window_hash + ord(text[i])) % mod

    for i in range(n - m + 1):
        if pattern_hash == window_hash:
            # Hash match -> verify characters (resolves hash collisions)
            if text[i : i + m] == pattern:
                return i

        if i < n - m:
            # Rolling update: remove left char, shift, add right char
            window_hash = (
                base * (window_hash - ord(text[i]) * h) + ord(text[i + m])
            ) % mod
            if window_hash < 0:
                window_hash += mod

    return -1


def main() -> None:
    log_entry = "2026-09-18T10:14:02Z [AUDIT] Desk ticket #8192 marked STATUS=REFUND_APPROVED for user 44"
    keyword = "STATUS=REFUND_APPROVED"

    idx = rabin_karp_search(log_entry, keyword)
    if idx != -1:
        print(f"Keyword match found at character offset {idx}")
        print(f"Snippet: '{log_entry[idx:idx + len(keyword)]}'")
    else:
        print("Pattern not found")


if __name__ == "__main__":
    main()

Run:

uv run python rabin_karp.py

Output:

Keyword match found at character offset 54
Snippet: 'STATUS=REFUND_APPROVED'

Case 2: In-Memory Bloom Filter for Order Existence

Save as bloom_filter.py. Implement a bitset Bloom filter using Python’s bytearray and salted hashing.

# bloom_filter.py
import hashlib


class BloomFilter:
    def __init__(self, size_in_bits: int, num_hashes: int) -> None:
        self.num_bits = size_in_bits
        self.num_hashes = num_hashes
        # Allocate bytes (8 bits per byte)
        num_bytes = (size_in_bits + 7) // 8
        self.bit_array = bytearray(num_bytes)

    def _hashes(self, item: str) -> list[int]:
        indexes: list[int] = []
        raw_bytes = item.encode("utf-8")
        for i in range(self.num_hashes):
            # Salt with index to create independent hash probes
            digest = hashlib.sha256(raw_bytes + bytes([i])).digest()
            val = int.from_bytes(digest[:8], byteorder="big")
            indexes.append(val % self.num_bits)
        return indexes

    def add(self, item: str) -> None:
        for bit_index in self._hashes(item):
            byte_idx = bit_index // 8
            bit_offset = bit_index % 8
            self.bit_array[byte_idx] |= 1 << bit_offset

    def __contains__(self, item: str) -> bool:
        for bit_index in self._hashes(item):
            byte_idx = bit_index // 8
            bit_offset = bit_index % 8
            if not (self.bit_array[byte_idx] & (1 << bit_offset)):
                # Bit is 0 -> definitely NOT in the set!
                return False
        return True  # All bits 1 -> probably in the set!


def main() -> None:
    # 1024 bits with 4 hash probes
    bf = BloomFilter(size_in_bits=1024, num_hashes=4)

    existing_orders = ["ORDER-101", "ORDER-102", "ORDER-103", "ORDER-999"]
    for order_id in existing_orders:
        bf.add(order_id)

    queries = ["ORDER-101", "ORDER-102", "ORDER-500", "ORDER-777"]
    for q in queries:
        if q in bf:
            print(f"Query [{q}]: Probably exists (fetch from database)")
        else:
            print(f"Query [{q}]: Definitely DOES NOT exist (skipped DB read)")


if __name__ == "__main__":
    main()

Run:

uv run python bloom_filter.py

Output:

Query [ORDER-101]: Probably exists (fetch from database)
Query [ORDER-102]: Probably exists (fetch from database)
Query [ORDER-500]: Definitely DOES NOT exist (skipped DB read)
Query [ORDER-777]: Definitely DOES NOT exist (skipped DB read)

The trap

The fatal trap with Bloom filters is attempting to delete elements. Setting a bit back to 0 may corrupt the membership signatures of other distinct items that happened to share that same bit. Standard Bloom filters are strictly append-only.

If item deletion is required, use a Counting Bloom Filter (where each slot stores an integer counter rather than a single bit) or a Cuckoo filter.

The boring rule

1. Use Python’s built-in 'pattern' in text or text.find() for ordinary substring search. CPython implements a highly optimized two-way string search algorithm in C.
2. Use a Bloom filter in front of slow storage layers (like S3 or PostgreSQL) to prevent database queries for records that do not exist.
3. Size Bloom filters using the formula: \(m \approx -\frac{n \ln p}{(\ln 2)^2}\), where \(n\) is expected item count and \(p\) is the acceptable false positive probability (e.g. 0.01 for 1%).
4. Always prepare fallback logic when a Bloom filter reports “probably present” since false positives are a natural property of the structure.

Try this

1. Experimentally verify the false positive rate of BloomFilter by adding 200 items and testing 5,000 non-existent keys.
2. Extend rabin_karp_search to find and return a list of all start indices where a pattern appears in a long text string.