Trie

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Trong khoa học máy tính, trie, hay cây tiền tố, là một cấu trúc dữ liệu sử dụng cây có thứ tự, dùng để lưu trữ một mảng liên kết của các xâu kí tự. Không như cây nhị phân tìm kiếm, mỗi nút trong cây không liên kết với một khóa trong mảng. Thay vào đó, mỗi nút liên kết với một xâu kí tự sao cho các xâu kí tự của tất cả các nút con của một nút đều có chung một tiền tố, chính là xâu kí tự của nút đó. Nút gốc tương ứng với xâu kí tự rỗng.

Thuật ngữ trie xuất phát từ từ tiếng Anh retrieval. Theo từ nguyên học, người phát minh ra trie là Edward Fredkin phát âm nó là cây / triː/.[1] Tuy nhiên nhiều tác giả khác lại phát âm là /ˈtraɪ/.[1][2]

Khóa trong trie không nhất thiết phải là xâu kí tự mà có thể là một danh sách có thứ tự của bất kì đối tượng nào, chẳng hạn như chữ số, hay hình dạng.

Lợi thế của trie so với các cấu trúc dữ liệu tìm kiếm khác[sửa | sửa mã nguồn]

Sau đây là những lợi thế chính của trie so với cây nhị phân tìm kiếm:

  • Thời gian tìm kiếm nhỏ hơn. Thao tác tìm kiếm một khóa độ dài m đòi hỏi O(m) phép so sánh kí tự. Một cây nhị phân tìm kiếm sử dụng O(\log n) phép so sánh xâu (n là số lượng khóa). Trong trường hợp xấu nhất, cây nhị phân tìm kiếm cần dùng O(m\log n) phép so sánh kí tự.
  • Trie sử dụng ít bộ nhớ hơn bởi các tiền tố chung chỉ cần được lưu trữ một lần
  • Trie cho phép tìm kiếm tiền tố trùng hợp dài nhất.
  • Số lượng nút từ gốc tới lá đúng bằng độ dài của khóa.

Sau đây là những lợi thế chính của trie so với bảng băm:

  • Trie cho phép liệt kê các khóa theo thứ tự từ điển
  • Trie cho phép tìm kiếm tiền tố trùng hợp dài nhất
  • Do không phải tính hàm băm nên trie thường nhanh hơn bảng băm trong trường hợp khóa bé chẳng hạn như số nguyên hay con trỏ.

Ứng dụng[sửa | sửa mã nguồn]

Thay thế các cấu trúc dữ liệu khác[sửa | sửa mã nguồn]

Như đã nói ở trên, trie có nhiều ưu điểm so với cây nhị phân tìm kiếm. Trie cũng có thể được dùng thay cho bảng băm.

Biểu diễn từ điển[sửa | sửa mã nguồn]

Một ứng dụng phổ biến của trie là dùng để biểu diễn từ điển.. Trie đặc biệt phù hợp cho các ứng dụng đòi hỏi tìm kiếm xấp xỉ, chẳng hạn như phần mềm soát lỗi chính tả.

Xem thêm[sửa | sửa mã nguồn]

Ghi chú[sửa | sửa mã nguồn]

  1. ^ a ă Black, Paul E. (16 tháng 11 năm 2009). “trie”. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. Bản gốc lưu trữ ngày 19 tháng 5 năm 2010. 
  2. ^ Knuth, Donald (1997). “6.3: Digital Searching”. The Art of Computer Programming Volume 3: Sorting and Searching (ấn bản 2). Addison-Wesley. tr. 492. ISBN 0201896850.