Skip to main content

Trie

Hung NguyenJune 28, 2024About 11 mindsadata-structuredsadata-structure

1. Giới thiệu về Trie

Trie (còn được gọi là cây tiền tố, cây tìm kiếm từ) là một cấu trúc dữ liệu dạng cây. Như tên gọi, nó là một cây giống như một từ điển. Nó là một cách lưu trữ từ điển. Mỗi từ trong từ điển được biểu diễn trong Trie dưới dạng một đường dẫn từ nút gốc, các cạnh trên đường dẫn kết nối các chữ cái lại với nhau để tạo thành chuỗi tương ứng.

Ví dụ dưới đây là một cây Trie, bao gồm 7 từ: a, abc, acb, acc, ach, b, chb.

20220210142323.png
20220210142323.png

Từ hình vẽ, chúng ta có thể thấy rằng cây Trie sử dụng các cạnh để biểu diễn các chữ cái, đường dẫn từ nút gốc đến một nút cụ thể đại diện cho một từ. Ví dụ, 1 → 2 → 6 → 10 biểu diễn từ acc. Để đánh dấu từ một cách rõ ràng, chúng ta có thể thêm một đánh dấu end (nút màu đỏ trong hình) tại vị trí nút kết thúc của mỗi từ, đại diện cho một từ từ nút gốc đến đó.

Cấu trúc của Trie khá đơn giản, bản chất của nó là một cây nhiều nhánh được sử dụng để tìm kiếm chuỗi nhanh chóng, mỗi nút trên cây chứa con trỏ đến nhiều ký tự. Kết hợp các ký tự đi qua từ nút gốc đến một nút cụ thể sẽ tạo thành chuỗi tương ứng với nút đó.

Ý tưởng cốt lõi của Trie: Sử dụng không gian để trao đổi thời gian, sử dụng tiền tố chung của chuỗi để giảm thiểu thời gian tìm kiếm, giảm thiểu so sánh chuỗi không cần thiết, nhằm tăng hiệu suất.

Dưới đây, chúng ta sẽ tóm tắt các thuộc tính cơ bản của Trie:

2. Các thao tác cơ bản trên Trie

Các thao tác cơ bản trên Trie bao gồm tạo Trie, chèn, tìm kiếmxóa. Trong đó, thao tác xóa là thao tác ít được sử dụng nhất, chúng ta sẽ tập trung vào việc tạo Trie, chèn và tìm kiếm.

2.1 Cấu trúc của Trie

2.1.1 Cấu trúc nút Trie

Trước tiên, chúng ta sẽ định nghĩa cấu trúc nút Trie.

Như đã đề cập, Trie là một cây nhiều nhánh, và cách triển khai "nhiều nhánh" có thể sử dụng mảng hoặc bảng băm. Tiếp theo, chúng ta sẽ giới thiệu hai cấu trúc nút Trie này.

class Node:                                         # Cấu trúc nút Trie
    def __init__(self):                             # Khởi tạo nút Trie
        self.children = [None for _ in range(26)]    # Khởi tạo các nút con
        self.isEnd = False                          # isEnd được sử dụng để đánh dấu từ kết thúc

Trong đoạn mã trên, self.children được triển khai bằng mảng, đại diện cho tất cả các nút con của nút hiện tại. isEnd được sử dụng để đánh dấu xem từ đã kết thúc hay chưa.

Khi chèn một từ vào Trie, chúng ta cần chuyển đổi các ký tự trong từ thành số và tạo nút ký tự tương ứng, sau đó chèn nút đó vào mảng có độ dài 26.

class Node:                                     # Cấu trúc nút Trie
    def __init__(self):                         # Khởi tạo nút Trie
        self.children = dict()                  # Khởi tạo các nút con
        self.isEnd = False                      # isEnd được sử dụng để đánh dấu từ kết thúc

Trong đoạn mã trên, self.children được triển khai bằng bảng băm, đại diện cho tất cả các nút con của nút hiện tại. isEnd được sử dụng để đánh dấu xem từ đã kết thúc hay chưa. Khi chèn một từ vào Trie, chúng ta chỉ cần tạo nút ký tự tương ứng với các ký tự trong từ và chèn nút đó vào bảng băm tương ứng.

Dưới đây, để thống nhất mã và viết dễ dàng, tất cả mã trong bài viết này sẽ sử dụng bảng băm để biểu diễn nhiều nút con của nút hiện tại.

2.1.2 Cấu trúc cơ bản của Trie

Sau khi định nghĩa cấu trúc nút Trie, chúng ta sẽ định nghĩa cấu trúc cơ bản của Trie. Trong quá trình khởi tạo Trie, chúng ta định nghĩa một nút gốc và nút gốc này không lưu trữ ký tự. Trong các thao tác chèn và tìm kiếm, chúng ta sẽ bắt đầu từ nút gốc của Trie. Đoạn mã dưới đây mô tả cấu trúc cơ bản của Trie.

class Trie:                                     # Trie

    # Khởi tạo Trie
    def __init__(self):                         # Khởi tạo Trie
        self.root = Node()                      # Khởi tạo nút gốc (nút gốc không lưu trữ ký tự)

2.2 Tạo và chèn vào Trie

Tạo Trie đề cập đến việc chèn tất cả các từ trong mảng chuỗi vào Trie. Trong khi chèn đề cập đến việc chèn một từ vào Trie.

2.2.1 Thao tác chèn vào Trie

Trước khi giải thích về việc tạo Trie, chúng ta hãy xem cách chèn một từ vào Trie. Các bước cụ thể như sau:

# Chèn một từ vào Trie
def insert(self, word: str) -> None:
    cur = self.root
    for ch in word:                         # Lặp qua từng ký tự trong từ
        if ch not in cur.children:          # Nếu không tồn tại nút con với khóa ch
            cur.children[ch] = Node()       # Tạo một nút mới và lưu trữ trong nút con của nút hiện tại
        cur = cur.children[ch]              # Cho nút hiện tại trỏ đến nút mới và tiếp tục xử lý ký tự tiếp theo
    cur.isEnd = True                        # Đánh dấu nút hiện tại là kết thúc của từ

2.2.2 Tạo Trie

Việc tạo Trie khá đơn giản, các bước cụ thể như sau:

trie = Trie()
for word in words:
    trie.insert(word)

2.3 Thao tác tìm kiếm trên Trie

2.3.1 Tìm kiếm từ trong Trie

Việc tìm kiếm một từ trong Trie thực ra tương tự như thao tác chèn vào Trie. Các bước cụ thể như sau:

# Tìm kiếm một từ trong Trie
def search(self, word: str) -> bool:
    cur = self.root
    for ch in word:                         # Lặp qua từng ký tự trong từ
        if ch not in cur.children:          # Nếu không tồn tại nút con với khóa ch
            return False                    # Trả về False
        cur = cur.children[ch]              # Chỉ định nút hiện tại trỏ đến nút với khóa ch và tiếp tục tìm kiếm ký tự tiếp theo

    return cur is not None and cur.isEnd    # Kiểm tra xem nút hiện tại có đánh dấu kết thúc từ hay không

2.3.2 Tìm kiếm tiền tố trong Trie

Việc tìm kiếm một tiền tố trong Trie tương tự như thao tác tìm kiếm từ trong Trie, khác biệt là không cần kiểm tra xem nút hiện tại có đánh dấu kết thúc từ hay không.

# Tìm kiếm một tiền tố trong Trie
def startsWith(self, prefix: str) -> bool:
    cur = self.root
    for ch in prefix:                       # Lặp qua từng ký tự trong tiền tố
        if ch not in cur.children:          # Nếu không tồn tại nút con với khóa ch
            return False                    # Trả về False
        cur = cur.children[ch]              # Chỉ định nút hiện tại trỏ đến nút với khóa ch và tiếp tục tìm kiếm ký tự tiếp theo
    return cur is not None                  # Kiểm tra xem nút hiện tại có tồn tại hay không

3. Mã nguồn triển khai Trie

class Node:                                     # Node của Trie
    def __init__(self):                         # Khởi tạo Node
        self.children = dict()                  # Khởi tạo các Node con
        self.isEnd = False                      # isEnd được sử dụng để đánh dấu kết thúc từ
        
        
class Trie:                                     # Trie
    
    # Khởi tạo Trie
    def __init__(self):                         # Khởi tạo Trie
        self.root = Node()                      # Khởi tạo Node gốc (Node gốc không lưu trữ ký tự)

    # Chèn một từ vào Trie
    def insert(self, word: str) -> None:
        cur = self.root
        for ch in word:                         # Lặp qua từng ký tự trong từ
            if ch not in cur.children:          # Nếu không tồn tại Node con với khóa ch
                cur.children[ch] = Node()       # Tạo một Node mới và lưu trữ trong Node con của Node hiện tại
            cur = cur.children[ch]              # Cho Node hiện tại trỏ đến Node mới và tiếp tục xử lý ký tự tiếp theo
        cur.isEnd = True                        # Đánh dấu Node hiện tại là kết thúc của từ

    # Tìm kiếm một từ trong Trie
    def search(self, word: str) -> bool:
        cur = self.root
        for ch in word:                         # Lặp qua từng ký tự trong từ
            if ch not in cur.children:          # Nếu không tồn tại Node con với khóa ch
                return False                    # Trả về False
            cur = cur.children[ch]              # Chỉ định Node hiện tại trỏ đến Node với khóa ch và tiếp tục tìm kiếm ký tự tiếp theo

        return cur is not None and cur.isEnd    # Kiểm tra xem Node hiện tại có đánh dấu kết thúc từ hay không

    # Tìm kiếm một tiền tố trong Trie
    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for ch in prefix:                       # Lặp qua từng ký tự trong tiền tố
            if ch not in cur.children:          # Nếu không tồn tại Node con với khóa ch
                return False                    # Trả về False
            cur = cur.children[ch]              # Chỉ định Node hiện tại trỏ đến Node với khóa ch và tiếp tục tìm kiếm ký tự tiếp theo
        return cur is not None                  # Kiểm tra xem Node hiện tại có tồn tại hay không

4. Phân tích thuật toán của Trie

Giả sử độ dài của từ là n, độ dài của tiền tố là m, số ký tự trong tập hợp ký tự là d, thì:

5. Ứng dụng của Trie

Một ứng dụng điển hình của Trie là trong các công cụ tìm kiếm. Khi nhập một phần nội dung vào công cụ tìm kiếm, công cụ sẽ tự động hiển thị một số nội dung tìm kiếm liên quan. Chúng ta có thể chọn nội dung tìm kiếm mà chúng ta muốn mà không cần nhập toàn bộ nội dung. Chức năng này giúp tiết kiệm thời gian tìm kiếm.

Ví dụ, khi chúng ta nhập "Trie" vào công cụ tìm kiếm, các nội dung tìm kiếm liên quan với tiền tố "Trie" sẽ được hiển thị dưới.

Cơ chế cơ bản để thực hiện chức năng này là Trie. Tất nhiên, các công cụ tìm kiếm như Google, Bing, … đã thực hiện nhiều cải tiến và tối ưu hóa phía sau chức năng này, nhưng cơ sở cơ bản nhất của nó vẫn là cấu trúc dữ liệu "Trie".

Ngoài ra, chúng ta có thể chia ứng dụng của Trie thành các loại sau: