Mini-challenge — Autocomplete top-K với Trie + frequency

Bạn đang làm ô tìm kiếm cho một sàn thương mại điện tử có 1 triệu sản phẩm. Người dùng gõ "lap", hệ thống phải trả về ngay top 5 sản phẩm khớp prefix đó, xếp theo lượt tìm gần đây.

Cách làm: dùng Trie (bài 08) để tìm prefix trong O(L), lưu frequency (tần suất tìm kiếm) tại mỗi node, rồi DFS subtree từ node prefix và dùng min-heap để lấy top-K nhanh.

Sau bài này bạn tự cài được lớp nền của các bộ gợi ý tìm kiếm.

Yêu cầu bài toán

Viết cấu trúc Autocomplete với API sau:

• insert(word, frequency): insert word hoặc cộng dồn frequency cho word. Gọi nhiều lần với cùng word thì frequency được cộng dồn.
• suggest(prefix, k): trả về top K word khớp prefix, sắp xếp frequency giảm dần. Khi bằng frequency thì xếp theo alphabet tăng dần.

Yêu cầu Big-O:

Ràng buộc: 1 triệu word, alphabet a-z, độ dài tối đa 20.

Starter: cấu trúc dữ liệu và interface

-- Cấu trúc node của Trie
AutocompleteNode:
    children: Map<ký_tự, AutocompleteNode>
    frequency: int      -- 0 nếu không phải cuối từ
    word: String        -- null nếu không phải cuối từ

-- Interface cần cài đặt
Autocomplete:
    root: AutocompleteNode

    insert(word, frequency):
        -- TODO

    suggest(prefix, k):
        -- TODO: trả về List<String>

Hãy tự làm 20–25 phút trước khi xem gợi ý. Trước khi code, liệt kê các input biên (prefix không tồn tại, prefix rỗng, k lớn hơn số kết quả, insert cùng một word hai lần); cách nghĩ về chúng nằm ở Edge case.

Test case

a <- Autocomplete mới
a.insert("laptop", 50)
a.insert("lap", 10)
a.insert("lapis", 30)
a.insert("legend", 5)

assert a.suggest("la", 3)  = ["laptop", "lapis", "lap"]
assert a.suggest("lap", 1) = ["laptop"]
assert a.suggest("xyz", 5) = []

-- bằng frequency thì xếp alphabet tăng dần
a.insert("apple", 20)
a.insert("apply", 20)
assert a.suggest("ap", 2) = ["apple", "apply"]

Gợi ý

Lời giải

-- Cấu trúc Node
Node:
    children: Map<ký_tự, Node>
    frequency: int     -- 0 nếu không phải cuối từ
    word: String       -- null nếu không phải cuối từ

-- Cấu trúc chính
Autocomplete:
    root: Node mới (rỗng)

-- Insert word với frequency (cộng dồn nếu gọi lại)
insert(word, frequency):
    node <- root
    for each ký_tự c trong word:
        if c không trong node.children:
            node.children[c] <- Node mới
        node <- node.children[c]
    node.frequency <- node.frequency + frequency   -- cộng dồn khi insert lại
    node.word <- word

Time: O(L)  Space: O(L) cho node mới trên path

-- Suggest top K word có prefix matching
suggest(prefix, k):
    -- Bước 1: đi xuống trie theo prefix
    node <- root
    for each ký_tự c trong prefix:
        node <- node.children.get(c)
        if node = null: return []          -- prefix không tồn tại

    -- Bước 2: DFS subtree + min-heap kích thước k
    -- Comparator: loại phần tử "kém giá trị nhất" trước
    --   kém nhất = frequency thấp nhất; nếu bằng = alphabetically lớn nhất
    heap <- MinHeap(key: (frequency tăng dần; tie: word giảm dần alphabetical))
    collect(node, heap, k)

    -- Bước 3: poll + đảo ngược (heap pop nhỏ nhất trước)
    result <- []
    while heap không rỗng:
        result.append(heap.poll().word)
    result.reverse()
    return result

Time: O(L + matches × log K)  Space: O(k)

-- DFS collect: thêm word vào min-heap, giữ size <= k
collect(node, heap, k):
    if node.word != null:
        heap.push(node)
        if heap.size() > k:
            heap.poll()                -- evict phần tử kém nhất
    for each child trong node.children.values():
        collect(child, heap, k)

Các bẫy hay gặp

Bẫy 1: Quên field word, phải mang theo chuỗi prefix trong DFS.

-- LỘN XỘN: không có field word nên phải mang chuỗi prefix qua đệ quy
collect(node, currentPrefix, heap, k):
    if node.frequency > 0:
        heap.push(currentPrefix)      -- cấp phát string mỗi lần
    for each (ký_tự c, child) trong node.children:
        collect(child, currentPrefix + c, heap, k)   -- O(L) allocation mỗi bước

Lưu word tại node cuối từ là đánh đổi bộ nhớ để lấy code gọn hơn, và khỏi phải cấp phát chuỗi O(L) ở mỗi bước DFS. Với 1 triệu word, mỗi chuỗi tối đa 20 ký tự, tổng bộ nhớ vẫn chấp nhận được.

Bẫy 2: Sắp xếp cả subtree thay vì dùng min-heap top-K.

-- CHẬM: sắp xếp toàn bộ match rồi lấy K đầu
all <- []
collectAll(node, all)
all.sort(theo frequency giảm dần)
return all[0..k-1]

-- O(matches × log matches) thay vì O(matches × log K)
-- K=5, matches=10.000: sắp xếp tốn cỡ 130k phép so sánh; min-heap top-5 tốn cỡ 25k

Bẫy 3: Comparator đặt ngược chiều khi xử lý trường hợp bằng frequency.

Min-heap giữ lại phần tử lớn hơn theo comparator (phần tử nhỏ hơn bị loại). Để giữ word đứng trước theo alphabet (ưu tiên "apple" hơn "apply" khi frequency bằng nhau), comparator phải coi "apply" là nhỏ hơn trong heap:

-- SAI: khi bằng frequency lại giữ "apply" thay vì "apple", ngược thứ tự alphabet
comparator(a, b):
    if a.frequency != b.frequency: return a.frequency - b.frequency
    return a.word.compareTo(b.word)     -- "apple" < "apply" => "apple" bị evict trước -- sai!

-- ĐÚNG: "apply" "nhỏ hơn" trong heap => bị evict trước => giữ "apple"
comparator(a, b):
    if a.frequency != b.frequency: return a.frequency - b.frequency
    return b.word.compareTo(a.word)     -- đảo ngược: "apply" < "apple" trong heap

Hãy test kỹ trường hợp bằng frequency trước khi tin vào logic của comparator.

So sánh bốn cách

Từ chậm đến nhanh khi query: quét cả HashMap, Trie + DFS + sort, Trie + DFS + min-heap, rồi Trie với top-K tính sẵn ở mỗi node. Khoảng cách cụ thể tuỳ dữ liệu và K, hãy tự đo trên bộ dữ liệu của bạn. Khi K nhỏ, min-heap thắng sắp xếp rõ rệt; top-K tính sẵn thắng khi workload chủ yếu là query, nhưng insert chậm hơn và tốn bộ nhớ hơn (đánh đổi ở mục dưới).

Biến thể để tự thử

Biến thể 1: tính sẵn top-K ở mỗi node (đưa suggest về O(L)):

Thay vì DFS mỗi lần suggest, lưu sẵn danh sách top-K trong mỗi node. Khi insert, đi xuống từng node trên đường đi và cập nhật danh sách top-K tại mỗi node. suggest chỉ cần đi tới node prefix rồi trả về node.topK, O(L).

Đánh đổi: insert tốn O(L × K log K) thay vì O(L). Hợp khi số lần gọi suggest nhiều hơn insert rất nhiều, điển hình cho ô tìm kiếm production (bộ từ vựng ổn định, query liên tục).

Biến thể 2: tìm gần đúng với edit distance 1:

Prefix hiện tại yêu cầu khớp chính xác. Nếu người dùng gõ "latop" thay vì "laptop", bài này trả về rỗng. Hãy thêm khả năng chịu 1 lỗi gõ: DFS có một bộ đếm số ký tự sai, bỏ nhánh khi bộ đếm vượt 1. Phức tạp hơn đáng kể.

Biến thể 3: frequency theo từng người dùng:

Thêm yếu tố riêng cho từng người dùng: mỗi người có lịch sử tìm kiếm riêng. Cách 1: một Trie chung kèm map frequency cho từng người, suggest lấy kết quả chung rồi xếp hạng lại theo sở thích của người đó. Cách 2: mỗi người một Trie, tốn bộ nhớ nhưng query gọn hơn. Với 1 triệu người dùng và 1 triệu word, Trie riêng cho từng người là bất khả thi, nên cách 1 (Trie chung cộng xếp hạng lại) là hướng thực tế cho sản phẩm.

Thử ngẫmbiến thể 3 kết luận Trie riêng cho từng người dùng là bất khả thi với 1 triệu người dùng. Nếu chỉ 1% người dùng có lượng truy cập đủ lớn để cá nhân hoá đáng giá, kết luận đó còn đúng không?

Dùng ở đâu trong thực tế

Field kiểu completion của Elasticsearch: dùng Finite State Transducer (FST), một biến thể nén của trie. FST mã hoá trie thành một automaton hữu hạn không chu trình ở dạng tối giản, tiết kiệm bộ nhớ hơn trie thường, và lấy được top-N theo weight mà không phải duyệt hết subtree.

Lucene: engine nằm dưới Elasticsearch, dùng FST cho term dictionary. Mỗi segment có FST riêng chứ không phải một trie toàn cục duy nhất, nhờ vậy gộp (merge) và xoá segment hiệu quả.

Xem thêm case study Lucene và ClamAV ở khoá Thuật toán ứng dụng.

Điều bạn vừa làm được

• Mở rộng Trie cơ bản (bài 08) bằng field frequency để gợi ý top-K có xếp hạng.
• Cài DFS gom word trong subtree cùng min-heap kích thước K: O(matches × log K) thay vì O(matches × log matches).
• Nắm cách đặt comparator cho min-heap khi bằng frequency: phải đảo chiều thì heap mới giữ đúng phần tử.
• Hiểu đánh đổi giữa DFS lúc query và top-K tính sẵn: tốc độ insert so với tốc độ query.
• Biết cách làm này là họ hàng gần của completion suggester trong Elasticsearch (dùng FST, biến thể nén của trie).

Bài tiếp theo: Case Study: MySQL InnoDB B+tree + Redis dict rehash