Thuật toán 7 — Chuỗi, hashing & cấu trúc xác suất

Vì sao một người làm dữ liệu cần bài này?

Trong hệ thống dữ liệu và ngân hàng, hai thao tác lặp đi lặp lại nhiều nhất là tìm/so khớp chuỗi và băm để định vị. Bạn parse hàng triệu dòng log tìm mã lỗi, gõ tên khách hàng vào ô tìm kiếm và mong nó gợi ý ngay, khử trùng hàng chục triệu giao dịch để không ghi trùng, hay quyết định một customer_id sẽ nằm ở shard nào trong 16 node. Đằng sau tất cả những việc tưởng chừng khác nhau ấy chỉ có vài ý tưởng cốt lõi: rolling hash, trie, hàm băm, Bloom filter và consistent hashing.

Bài này đi từ khớp mẫu trên một chuỗi đơn lẻ đến băm phân tán trên hàng chục node. Điểm chung: khi dữ liệu đủ lớn, thuật toán "ngây thơ" O(nm) hay "tra DB mỗi lần" sẽ giết chết hệ thống, và một cấu trúc đúng biến việc đó thành gần như O(1). Danh mục này là Python nên mọi ví dụ dưới đây là minh hoạ ý tưởng — không phải code production đã tối ưu.

Bài dựa trên nền Cấu trúc dữ liệu (bảng băm, cây) và nối sang Thực chiến dữ liệu. Riêng khoảng cách chỉnh sửa chuỗi đã bàn ở DP / edit distance.

1. Khớp mẫu (pattern matching): tìm chuỗi con

Bài toán kinh điển: cho văn bản text độ dài n và mẫu pattern độ dài m, tìm mọi vị trí pattern xuất hiện trong text.

Cách ngây thơ — O(n·m)

Trượt cửa sổ độ dài m qua từng vị trí và so khớp ký tự. Với mỗi vị trí, tệ nhất phải so m ký tự, nên tổng là O(n·m). Với text vài trăm KB và mẫu dài, con số này bùng nổ.

# (minh hoạ) khớp mẫu ngây thơ O(n*m)
def naive_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    hits = []
    for i in range(n - m + 1):
        if text[i:i + m] == pattern:   # tệ nhất so m ký tự
            hits.append(i)
    return hits

Rabin-Karp — rolling hash, O(n + m) kỳ vọng

Ý tưởng: thay vì so từng ký tự, so hash. Tính hash của mẫu một lần, rồi trượt một "cửa sổ hash" qua văn bản. Mẹo then chốt là rolling hash: hash của cửa sổ kế tiếp tính được từ cửa sổ trước chỉ bằng một số phép toán hằng số — bỏ ký tự đầu, thêm ký tự cuối — thay vì băm lại toàn bộ cửa sổ. Khi hash trùng, ta so lại ký tự để loại va chạm (hai chuỗi khác nhau nhưng cùng hash).

Thời gian kỳ vọng O(n + m); tệ nhất vẫn O(n·m) nếu va chạm hash liên tục (hiếm với hằng số tốt). Bộ nhớ O(1). Điểm mạnh thật sự của Rabin-Karp là tìm nhiều mẫu cùng lúc: băm tất cả mẫu vào một set rồi mỗi cửa sổ chỉ tra set một lần.

# (minh hoạ) Rabin-Karp với rolling hash
def rabin_karp(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    base, mod = 256, 1_000_000_007
    high = pow(base, m - 1, mod)          # trọng số ký tự đầu cửa sổ

    def h(s):                              # hash m ký tự đầu của s
        v = 0
        for ch in s[:m]:
            v = (v * base + ord(ch)) % mod
        return v

    hp = h(pattern)
    hw = h(text)
    hits = []
    for i in range(n - m + 1):
        if hw == hp and text[i:i + m] == pattern:  # xác nhận, tránh va chạm
            hits.append(i)
        if i < n - m:                       # cuộn hash sang cửa sổ kế
            hw = (hw - ord(text[i]) * high) % mod
            hw = (hw * base + ord(text[i + m])) % mod
            hw %= mod
    return hits

KMP và regex — khi nào dùng gì

• KMP (Knuth-Morris-Pratt): đảm bảo O(n + m) tệ nhất (không phụ thuộc va chạm) nhờ tính trước bảng "prefix function" để không bao giờ lùi con trỏ văn bản. Chọn KMP khi cần bảo đảm chặt và chỉ tìm một mẫu.
• Rabin-Karp: gọn, tuyệt cho đa mẫu và cho các bài "so vân tay" (fingerprint) như phát hiện trùng lặp đoạn văn.
• Regex (re trong Python): công cụ thực dụng nhất cho parse log/giao dịch — trích mã giao dịch, IP, timestamp bằng biểu thức. Đằng sau nó vẫn là automata; nhưng cẩn thận regex "catastrophic backtracking" có thể chạy chậm bùng nổ với mẫu tồi.

Ứng dụng: lọc dòng log theo mã lỗi, tách trường từ chuỗi giao dịch cố định, dò chữ ký (signature) trong luồng dữ liệu.

2. Trie (cây tiền tố): autocomplete & khớp danh sách từ khoá

Khi bài toán là "tìm theo tiền tố" — gõ NG gợi ý NGUYEN, NGO, NGHIEM — bảng băm bó tay vì hash phá vỡ thứ tự tiền tố. Trie là cây mà mỗi cạnh mang một ký tự; đi từ gốc theo các ký tự của một từ sẽ tới nút đánh dấu kết thúc từ đó. Mọi từ chung tiền tố chia sẻ chung nhánh đầu.

# (minh hoạ) trie đơn giản cho autocomplete
class Trie:
    def __init__(self):
        self.root = {}                     # dict lồng nhau; '$' = kết thúc từ

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['$'] = True

    def _find(self, prefix: str):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def autocomplete(self, prefix: str) -> list[str]:
        node = self._find(prefix)
        if node is None:
            return []
        out = []
        def dfs(n, acc):
            if '$' in n:
                out.append(prefix + acc)
            for ch, child in n.items():
                if ch != '$':
                    dfs(child, acc + ch)
        dfs(node, "")
        return out

t = Trie()
for name in ["NGUYEN", "NGO", "NGHIEM", "TRAN"]:
    t.insert(name)
# t.autocomplete("NG") -> ['NGUYEN', 'NGO', 'NGHIEM']

Chi phí: tra/thêm một từ độ dài L là O(L), không phụ thuộc số từ trong trie — đây là điểm ăn đứt việc quét tuyến tính danh sách. Đổi lại trie tốn bộ nhớ hơn (mỗi nút một dict con).

Trie vs hash: hash cho tra khớp chính xác cực nhanh nhưng không làm được tiền tố; trie làm được tiền tố, sắp xếp theo thứ tự từ điển, và khớp danh sách từ khoá hiệu quả (nạp cả danh sách cấm/blacklist vào một trie rồi quét văn bản một lần — thuật toán Aho-Corasick là mở rộng đa mẫu của ý tưởng này). Use case ngân hàng: autocomplete tên/mã khách hàng, sàng lọc tên theo danh sách trừng phạt (sanctions), gợi ý mã sản phẩm theo tiền tố.

3. Hàm băm & bảng băm: nền của dict/set

Hàm băm ánh xạ một khoá bất kỳ (chuỗi, số, tuple) thành một số nguyên trong khoảng cố định. Ba tính chất cần có cho mục đích phân phối/tra cứu:

1. Xác định (deterministic): cùng đầu vào luôn ra cùng giá trị.
2. Phân bố đều (uniform): các khoá rải đều khắp dải, tránh dồn cục.
3. Nhanh: tính trong O(độ dài khoá).

Va chạm (collision) — hai khoá khác nhau cùng giá trị hash — là không tránh khỏi (nguyên lý chuồng bồ câu). Bảng băm xử lý va chạm bằng chaining (mỗi ô một danh sách) hoặc open addressing. Khi phân bố đều, tra cứu/chèn/xoá là O(1) trung bình — chính là lý do dict và set của Python nhanh. Chi tiết cấu trúc xem Cấu trúc dữ liệu.

Cảnh báo quan trọng — hai loại hash rất khác nhau:

• Hash phân phối/dedup (mục tiêu: nhanh + đều): hash() của Python, MurmurHash, CRC32, FNV. Không dùng cho bảo mật.
• Hash mật mã (mục tiêu: chống đảo ngược & va chạm cố ý): SHA-256, bcrypt, Argon2. Chậm hơn có chủ đích. Dùng để băm mật khẩu, chữ ký số. Đừng bao giờ dùng hash() để bảo vệ dữ liệu, và cũng đừng dùng bcrypt để phân shard. Lưu ý: hash() chuỗi trong Python bị randomize theo tiến trình (chống DoS) — muốn hash ổn định giữa các lần chạy cho dedup/partition, dùng hashlib (vd md5/sha1 cắt ngắn) hoặc thư viện mmh3.

Use case trực tiếp của hash cho dữ liệu: dedup (băm cả bản ghi thành một "vân tay", trùng vân tay là trùng bản ghi) và lookup (dùng set các khoá đã thấy). Nhưng khi số phần tử lên hàng chục–trăm triệu, giữ nguyên set trong RAM là quá đắt — đó là lúc cần Bloom filter.

4. Bloom filter: "có thể có / chắc chắn không"

Bloom filter là cấu trúc xác suất trả lời câu hỏi thành viên (membership) với bộ nhớ cực tiết kiệm. Nó gồm một mảng bit kích thước m (khởi tạo toàn 0) và k hàm băm độc lập. Khi thêm phần tử: băm nó bằng k hàm, bật k bit tương ứng lên 1. Khi kiểm tra: băm lại, nếu bất kỳ bit nào trong k bit đang là 0 → phần tử chắc chắn chưa từng thêm; nếu tất cả đều 1 → phần tử có thể đã có (cũng có thể là trùng bit ngẫu nhiên của phần tử khác).

Tính chất định mệnh:

• Không có false negative: nếu Bloom filter nói "chưa thấy" thì đúng là chưa thấy. Rất quý.
• Có false positive: đôi khi nói "có thể có" trong khi thực ra chưa từng thêm. Tỷ lệ này kiểm soát được bằng cách chọn m và k.

Công thức (đã kiểm chứng): tỷ lệ false positive xấp xỉ p ≈ (1 - e^(-kn/m))^k, với n là số phần tử đã thêm. Với n và tỷ lệ mục tiêu p cho trước, kích thước tối ưu là m = -n·ln(p) / (ln 2)² và số hàm băm tối ưu k = (m/n)·ln 2. Ví dụ 10 triệu phần tử, mục tiêu 1% false positive: cần ~11.98 bit/phần tử (~14 MB) và k ≈ 7 — nhỏ hơn nhiều so với giữ 10 triệu chuỗi trong set.

# (minh hoạ) Bloom filter tối giản
import hashlib

class BloomFilter:
    def __init__(self, size: int, k: int):
        self.size = size
        self.k = k
        self.bits = bytearray((size + 7) // 8)   # mảng bit

    def _hashes(self, item: str):
        # dùng md5 làm nguồn, tách thành k chỉ số (double hashing đơn giản)
        d = hashlib.md5(item.encode()).digest()
        h1 = int.from_bytes(d[:8], "big")
        h2 = int.from_bytes(d[8:], "big")
        for i in range(self.k):
            yield (h1 + i * h2) % self.size

    def _set(self, idx):  self.bits[idx // 8] |= (1 << (idx % 8))
    def _get(self, idx):  return bool(self.bits[idx // 8] & (1 << (idx % 8)))

    def add(self, item: str) -> None:
        for idx in self._hashes(item):
            self._set(idx)

    def __contains__(self, item: str) -> bool:
        return all(self._get(idx) for idx in self._hashes(item))

bf = BloomFilter(size=1_000_000, k=7)
bf.add("txn_9f2a")
# "txn_9f2a" in bf  -> True (chắc chắn từng thêm, hoặc false positive)
# "txn_0000" in bf  -> hầu như luôn False (không bao giờ false negative)

Vì "chắc chắn không" là tuyệt đối đúng, Bloom filter được dùng làm cửa lọc rẻ trước một thao tác đắt: nếu filter nói "chưa có" thì khỏi tra DB/khỏi gọi mạng; chỉ khi nói "có thể có" mới tra thật để xác nhận. Đây là mẫu tăng tốc dedup luồng lớn ở mục use case.

5. Consistent hashing: phân phối key ổn định khi đổi số node

Cách chia đơn giản nhất là hash(key) % N với N là số node. Nó rất tốt khi N cố định. Nhưng khi thêm/bớt một node (N đổi), gần như mọi key đổi số dư → mọi key phải di chuyển. Với cache phân tán hay cluster, đó là thảm hoạ: toàn bộ cache lạnh, dữ liệu đổ dồn.

Consistent hashing giải quyết đúng nỗi đau này. Ta hình dung không gian hash là một vòng tròn (ring) từ 0 đến giá trị hash lớn nhất. Cả node lẫn key đều được băm lên vòng đó. Một key thuộc về node đầu tiên gặp khi đi theo chiều kim đồng hồ từ vị trí key. Khi thêm/bớt một node, chỉ những key nằm giữa node đó và node liền trước cần di chuyển — trung bình chỉ 1/N lượng key, phần còn lại đứng yên.

Để tránh phân bố lệch (một node "ôm" cung lớn), mỗi node vật lý được đặt nhiều vị trí ảo (virtual nodes / vnodes) rải khắp vòng. Càng nhiều vnode, tải càng đều và khi một node chết, tải của nó được chia đều cho các node còn lại thay vì dồn hết vào một hàng xóm.

# (minh hoạ) consistent hashing với virtual nodes
import hashlib, bisect

class ConsistentHash:
    def __init__(self, nodes=None, vnodes=100):
        self.vnodes = vnodes
        self.ring = {}          # hash -> node
        self.sorted_keys = []   # danh sách hash đã sắp xếp để tìm nhị phân
        for n in (nodes or []):
            self.add_node(n)

    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node: str) -> None:
        for i in range(self.vnodes):
            h = self._hash(f"{node}#{i}")
            self.ring[h] = node
            bisect.insort(self.sorted_keys, h)

    def remove_node(self, node: str) -> None:
        for i in range(self.vnodes):
            h = self._hash(f"{node}#{i}")
            self.ring.pop(h, None)
            self.sorted_keys.remove(h)

    def get_node(self, key: str) -> str | None:
        if not self.ring:
            return None
        h = self._hash(key)
        idx = bisect.bisect(self.sorted_keys, h) % len(self.sorted_keys)  # node CW kế tiếp
        return self.ring[self.sorted_keys[idx]]

ch = ConsistentHash(["nodeA", "nodeB", "nodeC"], vnodes=100)
# ch.get_node("customer_42")  -> "nodeB" (ổn định kể cả khi thêm nodeD)

Use case: cache phân tán (memcached/Redis cluster), load balancing giữ session dính đúng server, và sharding dữ liệu ổn định khi mở rộng cụm.

6. Hashing cho phân vùng & dedup

Hai ứng dụng "cơm áo" nhất của hash trong đường ống dữ liệu:

• Phân vùng (partition): partition = hash(key) % N. Đây chính là cách Kafka chọn partition cho một message theo key (cùng key → cùng partition → giữ đúng thứ tự), và cách phân mảnh bảng theo hash được bàn ở phân vùng & sharding. Ưu điểm: đơn giản, phân bố đều. Nhược điểm: rehash khi đổi N — nên dùng consistent hashing nếu số node hay thay đổi. Với BigQuery/DB có thể phân mảnh theo MOD(FARM_FINGERPRINT(customer_id), N).
• Dedup: băm nội dung bản ghi thành vân tay (vd SHA-1 của các trường định danh) rồi giữ trong set/Bloom filter; vân tay trùng → bản ghi trùng. Cùng ý tưởng dùng cho content-addressable storage (Git, dedup block trong backup).

Ghi nhớ khi phân vùng: chọn khoá phân vùng có phân bố đều (customer_id thường tốt; ngày tháng dễ tạo "hot partition"). Khoá lệch làm một partition/shard quá tải trong khi số còn lại rảnh — đây là lỗi vận hành phổ biến nhất.

Use case thực tế

Khử trùng luồng giao dịch bằng Bloom filter

Bối cảnh: một luồng Kafka đổ về hàng chục triệu bản ghi giao dịch/ngày. Cần đảm bảo mỗi transaction_id chỉ ghi vào kho một lần (idempotency), tránh double-post. Tra bảng dedup trong DB mỗi bản ghi là quá đắt và làm nghẽn ghi.

Kiến trúc lọc hai tầng:

1. Duy trì một Bloom filter trong bộ nhớ chứa các transaction_id đã xử lý (vd 100 triệu phần tử, mục tiêu 0.1% FP → vài trăm MB).
2. Với mỗi bản ghi mới: hỏi Bloom filter.
   • Trả lời "chưa thấy" (chắc chắn đúng) → bản ghi mới, xử lý và add vào filter, không cần tra DB. Đây là đa số lưu lượng → tiết kiệm khổng lồ.
   • Trả lời "có thể có" → mới tra bảng dedup thật để xác nhận (loại false positive). Chỉ ~0.1% + số trùng thật mới phải tra DB.

Kết quả: giảm hầu hết lượt truy vấn DB đắt tiền, vì Bloom filter không bao giờ bỏ sót (không false negative) nên không có nguy cơ ghi trùng lọt lưới. Đây chính là mẫu "cửa lọc rẻ trước thao tác đắt".

Sharding theo consistent hashing

Bối cảnh: lưu hồ sơ khách hàng trên một cụm cache/KV gồm nhiều node, sharded theo customer_id. Yêu cầu: khi tăng từ 8 lên 12 node vào giờ cao điểm, không được làm sập cache toàn cụm.

Với hash(customer_id) % N: đổi từ 8 sang 12 khiến ~11/12 số key đổi node → cache miss hàng loạt, DB backend bị "sấm sét" (thundering herd). Với consistent hashing + vnodes: chỉ ~1/12 lượng key di chuyển sang các node mới, phần còn lại giữ nguyên vị trí và cache vẫn ấm. Kèm vnodes, tải mới được chia đều thay vì dồn vào một node. Cùng nguyên lý áp dụng khi một node chết đột ngột: tải của nó phân tán, không sập dây chuyền.

Ghi nhớ

• Tìm chuỗi con: naive O(n·m) → dùng KMP (O(n+m) bảo đảm, một mẫu) hoặc Rabin-Karp (rolling hash, tuyệt cho đa mẫu/vân tay). Regex cho parse log/giao dịch, coi chừng backtracking.
• Trie cho tìm theo tiền tố và autocomplete: tra O(độ dài từ), không phụ thuộc số từ. Hash làm khớp chính xác, trie làm tiền tố — chọn theo bài toán.
• Hàm băm tốt = xác định + phân bố đều + nhanh; va chạm là không tránh khỏi, bảng băm giải quyết để đạt O(1) trung bình (nền của dict/set).
• Bloom filter: tiết kiệm bộ nhớ, không false negative, có false positive kiểm soát được bằng m, k. Dùng làm cửa lọc rẻ trước khi tra DB/gọi mạng đắt tiền.
• Consistent hashing thay % N khi số node hay đổi: thêm/bớt node chỉ di chuyển ~1/N key; dùng vnodes để cân tải. Nền của cache phân tán, load balancing, sharding.
• Phân biệt tuyệt đối: hash cho phân phối/dedup (nhanh, đều — MurmurHash, CRC, hashlib cắt ngắn) KHÁC hash mật mã (SHA-256, bcrypt, Argon2 — chống tấn công). Không dùng nhầm. Nhớ hash() chuỗi của Python bị randomize theo tiến trình.

Đọc tiếp: Cấu trúc dữ liệu cho bảng băm & cây, DP / edit distance cho so khớp chuỗi mờ, và Thực chiến dữ liệu để ráp mọi thứ vào một đường ống thật.

Nguồn tham khảo: Rabin–Karp — Wikipedia, Bloom filter — Wikipedia, Consistent Hashing Explained — AlgoMaster.