Chuyển đến nội dung
MINH VO Ghi chép từ công việc
của một kỹ sư tại Việt Nam
Cơ bản10 phút đọc

Trie cho gợi ý tiền tố trong từ điển nhỏ

Tách chi phí tìm tiền tố khỏi tạo kết quả, giữ cờ kết thúc từ và xóa đúng nhánh để bảo toàn các từ dài hơn còn trong từ điển.

Đồ thị vẽ bằng bút chì trên giấy màu be, với các đường màu ô liu nối những đỉnh

Trie đi theo một cạnh cho mỗi ký tự để tìm nút của tiền tố, rồi duyệt những từ bên dưới nút đó. Tìm tiền tố và trả về mọi từ khớp có chi phí khác nhau. Với lập trình viên xây dựng tính năng gợi ý khi gõ, một tiền tố ngắn có thể được tìm rất nhanh nhưng vẫn khớp phần lớn từ điển.

Dùng các từ car, card, care, cat và dog. Tiền tố ca có bốn kết quả. Tiền tố car có ba, gồm chính car. Kết quả cuối đòi hỏi cờ kết thúc từ ở nút r: một nút có con vẫn có thể kết thúc một từ được lưu.

Phân biệt cạnh ký tự với từ hoàn chỉnh

Mỗi nút chứa ánh xạ từ ký tự tới nút con và một cờ Boolean cho biết từ có kết thúc tại đây không. Chèn lại từ đã có chỉ đặt lại cùng cờ, nên trie này biểu diễn tập các chuỗi phân biệt. Nó không đếm tần suất hoặc gắn nhiều tài liệu với cùng từ.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.terminal = False


def insert(root, word):
    if not isinstance(word, str) or not word or any(c not in 'abcdefghijklmnopqrstuvwxyz' for c in word):
        raise ValueError('expected a nonempty lowercase ASCII word')
    node = root
    for character in word:
        if character not in node.children:
            node.children[character] = TrieNode()
        node = node.children[character]
    node.terminal = True


def suggestions(root, prefix, limit=5):
    if not isinstance(prefix, str):
        raise ValueError('expected a string prefix')
    if type(limit) is not int:
        raise ValueError('expected an integer suggestion limit')
    if limit <= 0:
        return []
    node = root
    for character in prefix:
        if character not in node.children:
            return []
        node = node.children[character]
    result, path = [], list(prefix)

    def visit(current):
        if current.terminal:
            result.append(''.join(path))
        if len(result) == limit:
            return
        for character, child in sorted(current.children.items()):
            path.append(character)
            visit(child)
            path.pop()
            if len(result) == limit:
                return

    visit(node)
    return result

root = TrieNode()
for word in ['car', 'card', 'care', 'cat', 'dog']:
    insert(root, word)
assert suggestions(root, 'car') == ['car', 'card', 'care']
assert suggestions(root, 'ca', 2) == ['car', 'card']
assert suggestions(root, 'cab') == []

Trước tiên, hàm đi theo tiền tố mà không tạo danh sách lọc riêng từ toàn bộ từ điển. Khi tới nút tiền tố, phép duyệt xuất đường hiện tại nếu nút có cờ kết thúc rồi xét các con theo thứ tự ký tự. Xuất trước khi đi xuống khiến một từ đứng trước các từ dài hơn bắt đầu bằng nó trong thứ tự từ điển thông thường.

Danh sách path có thể thay đổi giúp tránh tạo một chuỗi tiền tố đầy đủ mới ở mỗi nút trong. Chuỗi chỉ được ghép khi trả về một gợi ý hoàn chỉnh. Các thao tác thêm và lấy ra phải đi theo cặp để nhánh anh em tiếp theo không nhận nhầm ký tự của nhánh trước.

Các nhánh car, card, care và cat dưới tiền tố ca, với cờ kết thúc tại r, d, e và t; nhánh d-o-g riêng nằm ngoài cây con của tiền tốMở ảnh kích thước đầy đủ ↗

Cờ kết thúc ở r phân biệt từ được lưu với tiền tố chỉ dẫn tới những từ dài hơn. Xóa car cần bỏ cờ ấy nhưng giữ các nhánh của card và care. Xóa toàn bộ cây con r sẽ làm mất cả những từ dài hơn vẫn hợp lệ.

Tính cả số ký tự trả về vào chi phí

Gọi P là độ dài tiền tố, V là số nút đã thăm bên dưới nút tiền tố trước khi đạt giới hạn và B là tổng số ký tự trong các chuỗi trả về. Với bảng chữ cái cố định gồm 26 ký tự và truy cập từ điển có chi phí kỳ vọng hằng số, cài đặt này cần O(P + V + B) công việc. Sắp các con của từng nút có chi phí bị chặn ở đây vì bảng chữ cái chỉ có 26 ký tự.

Nếu bảng ký tự không bị chặn, cần tính thêm chi phí sắp các khóa cạnh đi ra ở mỗi nút đã thăm. Nếu gợi ý được duy trì sẵn theo thứ tự trong cấu trúc khác, chi phí ấy chuyển sang chèn hoặc bảo trì. Không biểu diễn nào loại bỏ được công việc tạo B ký tự cho bên gọi.

Truy vấn có thể dừng sau số kết quả yêu cầu nhưng vẫn phải đi qua đường dài mới gặp chúng. Một nút có thể bắt đầu chuỗi dài chỉ có một từ kết thúc ở cuối. Cận như O(P + số từ khớp) che mất độ dài đường đi cùng kích thước các chuỗi trả về.

Phần trie của Princeton và cài đặt TrieST tách tra cứu khóa khỏi thu thập theo tiền tố. Biểu diễn ký tự bằng mảng ở đó có chi phí bộ nhớ mỗi nút khác với từ điển thưa trong ví dụ này.

Chọn quy tắc xếp hạng trước khi thêm bộ nhớ đệm

Thứ tự chữ cái đơn giản và xác định, nhưng tính năng gợi ý trong sản phẩm thường xếp theo tần suất, độ mới hoặc ngữ cảnh người dùng. Duyệt sâu theo chữ cái không bảo đảm trả về những kết quả có thứ hạng cao nhất theo các quy tắc ấy. Có thể cần cấu trúc ưu tiên, danh sách gợi ý tốt nhất lưu tại mỗi tiền tố hoặc chỉ mục tìm kiếm riêng.

Lưu đệm các gợi ý tốt nhất ở mọi nút giúp đọc rẻ hơn nhưng cập nhật đắt hơn. Đổi tần suất của một từ có thể ảnh hưởng mọi nút trên đường của nó. Xóa một từ có thể đòi tìm ứng viên thay thế ngoài tập đang lưu đệm. Đây là yêu cầu bảo trì mới, không chỉ là thay đổi nhỏ ở cờ kết thúc.

Bộ nhớ cũng cần được xem xét theo tải. Trie dùng chung tiền tố nhưng vẫn lưu các nút và ánh xạ con cho từng tiền tố phân biệt. Mảng từ đã sắp kết hợp hai phép tìm kiếm nhị phân để xác định khoảng tiền tố có thể nhỏ hơn và đủ dùng khi từ điển ít thay đổi. Trie nén giảm các chuỗi nút chỉ có một con, nhưng làm thay đổi cách khớp cạnh và cập nhật.

Giữ quy tắc chuẩn hóa nhất quán

Ví dụ chỉ nhận các từ ASCII viết thường, không rỗng. Nó không âm thầm chuyển chữ thường hoặc bỏ dấu. Ứng dụng nhiều ngôn ngữ cần chính sách chuẩn hóa và đối chiếu thứ tự được áp dụng nhất quán khi chèn và tra cứu. Chuẩn hóa chữ hoa/thường theo Unicode (case folding) có thể thay đổi độ dài chuỗi, còn thứ tự mã ký tự không phải thứ tự chữ cái của mọi ngôn ngữ. Chẳng hạn, str.casefold của Python đổi chữ ß trong tiếng Đức thành ss. Áp dụng phép đổi này sẽ thay đổi chính sách phân biệt khóa; ví dụ không tự áp dụng nó.

Tiền tố truy vấn rỗng bắt đầu từ gốc và trả các gợi ý đầu tiên theo giới hạn trên toàn từ điển. Tiền tố chứa ký tự không hỗ trợ không có kết quả trong cài đặt này. Nếu API cần từ chối truy vấn sai định dạng, phải thêm bước xác thực ấy thành hợp đồng tường minh.

Hãy kiểm tra từ đồng thời là tiền tố của từ khác, chèn lặp, cạnh không tồn tại và giới hạn bằng không, một hoặc lớn hơn số kết quả hiện có. Với phép xóa, cần thử bỏ cờ kết thúc trong khi các hậu duệ còn tồn tại. Những trường hợp này kiểm tra kết quả người dùng thấy, không chỉ xác nhận đã cấp phát vài nút.

Xóa một từ mà vẫn giữ các phần mở rộng

Phép xóa cần phân biệt từ được lưu, tiền tố tới được và nhánh không còn dùng. Trước tiên đi theo toàn bộ từ, ghi lại cha cùng ký tự của mỗi cạnh. Nếu thiếu cạnh hoặc nút cuối không có cờ kết thúc, trả về mà không thay đổi gì. Nếu từ tồn tại, bỏ cờ rồi loại các nút rỗng không kết thúc từ khi đi ngược về gốc.

def remove(root, word):
    if not isinstance(word, str) or not word or any(c not in 'abcdefghijklmnopqrstuvwxyz' for c in word):
        raise ValueError('expected a nonempty lowercase ASCII word')
    node, trail = root, []
    for character in word:
        if character not in node.children:
            return False
        trail.append((node, character))
        node = node.children[character]
    if not node.terminal:
        return False
    node.terminal = False
    for parent, character in reversed(trail):
        child = parent.children[character]
        if child.terminal or child.children:
            break
        del parent.children[character]
    return True

assert remove(root, 'car')
assert suggestions(root, 'ca') == ['card', 'care', 'cat']
assert not remove(root, 'car')
assert remove(root, 'card')
assert suggestions(root, 'ca') == ['care', 'cat']
assert remove(root, 'care')
assert suggestions(root, 'ca') == ['cat']
assert 'r' not in root.children['c'].children['a'].children
assert suggestions(root, 'd') == ['dog']

Sau khi xóa car, nút r còn các con d và e nên quá trình cắt nhánh dừng ngay. Xóa card sau đó bỏ lá d nhưng dừng tại r vì care còn tồn tại. Cuối cùng, xóa care bỏ cả e và r; quá trình dừng tại a vì nhánh t vẫn lưu cat. Nhánh dog riêng không tham gia đường duyệt này.

Ba trạng thái xóa dưới tiền tố ca: bỏ cờ car vẫn giữ card và care, xóa card vẫn giữ care, rồi xóa care cắt nhánh r không còn dùng trong khi giữ catMở ảnh kích thước đầy đủ ↗

Điều kiện dừng bảo vệ hai kiểu nút hữu ích. Nút có con vẫn nối tới các từ dài hơn; nút kết thúc có thể lưu một từ ngắn hơn ngay cả khi con cuối cùng bị xóa. Dừng ở một trong hai điều kiện giữ đúng từ điển. Đối tượng gốc không bao giờ bị xóa, nên bên gọi có điểm truy cập ổn định ngay cả sau khi bỏ từ cuối cùng.

Với từ dài L, phép xóa cần O(L) công việc kỳ vọng và O(L) mục lưu đường đi, theo cùng giả định truy cập từ điển như phép chèn. Nó không dùng đệ quy. Tuy nhiên, phần thu thập gợi ý phía trên vẫn đệ quy: một từ đơn rất dài vẫn có thể vượt giới hạn đệ quy Python khi được liệt kê. Hỗ trợ độ dài từ không bị chặn đòi hỏi ngăn xếp duyệt tường minh hoặc giới hạn độ dài đã công bố; phép xóa dạng lặp không giải quyết vấn đề riêng đó.

Kiểm tra giới hạn số nguyên cũng ảnh hưởng hợp đồng kết quả. Giới hạn phân số sẽ không bằng bất kỳ số lượng kết quả nguyên nào, khiến điều kiện dừng trước đây bỏ lỡ mức trần dự định. API này nhận giới hạn là kiểu số nguyên tích hợp, trả rỗng với giá trị không dương và từ chối Boolean cùng giới hạn phân số. Tiền tố sai kiểu bị từ chối; ký tự không hỗ trợ nằm trong một chuỗi chỉ khiến không tìm thấy cạnh.

Để luyện tập, duy trì một tập từ tham chiếu qua các lần chèn và xóa ngẫu nhiên. Với mỗi truy vấn, lọc bằng startswith, sắp xếp rồi áp dụng cùng quy tắc giới hạn không dương trước khi so sánh kết quả. Kiểm tra xóa từ vắng mặt không làm đổi bất kỳ nút nào, và xóa từ cuối cùng để xác nhận gốc vẫn dùng được cho lần chèn sau. Cách này kiểm tra cả gợi ý quan sát được lẫn hợp đồng cắt nhánh.

Nguồn tham khảo & đọc thêm

  1. Princeton Algorithms, Tries
  2. Princeton Algorithms, TrieST implementation
  3. Python documentation, str.casefold
← Về trang bài viết

Hình minh họa

100%