Cây hậu tố

Trong khoa học máy tính, một cây hậu tố là một cấu trúc dữ liệu để biểu diễn các hậu tố của một xâu ký tự sao cho có thể thực hiện nhanh chóng nhiều thao tác trên xâu.
Cây hậu tố của xâu  là một cây có cạnh được gắn nhãn là các xâu ký tự và mỗi hậu tố của  tương ứng với chuỗi thu được bằng cách ghép tất cả các nhãn của một đường từ gốc đến lá. Do đó nó là cây cơ số (cụ thể hơn, nó là cây Patricia) của các hậu tố của .
Việc xây dựng cây hậu tố của xâu  sử dụng thời gian và bộ nhớ tuyến tính với độ dài của . Sau khi đã xây dựng xong cây, có thể thực hiện nhanh chóng nhiều thao tác, chẳng hạn như tìm xâu con trong , tìm xâu con với một số lượng lỗi cố định, tìm biểu thức chính quy v.v... Cây hậu tố cũng là một trong những lời giải tuyến tính đầu tiên của bài toán tìm xâu con chung dài nhất. Tuy làm tăng tốc độ các thao tác nhưng việc lưu trữ cây hậu tố thường đòi hỏi nhiều bộ nhớ hơn chỉ lưu trữ xâu ký tự.

Lịch sử

Khái niệm này được đưa ra dưới tên gọi cây vị trí (position tree) bởi Weiner năm 1973, mà Donald Knuth sau đó gọi là "Thuật toán của năm 1973". Thuật toán được đơn giản hóa bởi McCreight năm 1976 , và bởi Ukkonen năm 1995. Ukkonen đưa ra thuật toán trực tuyến đầu tiên cho việc xây dựng cây hậu tố, nay gọi là thuật toán Ukkonen, với thời gian chạy nhanh ngang với thuật toán nhanh nhất khi đó. Các thuật toán này có thời gian chạy tuyến tính khi kích thước bảng chữ cái là hằng số, và có thời gian chạy xấu nhất là  trong trường hợp tổng quát.
Năm 1997, Martin Farach đưa ra thuật toán xây dựng cây hậu tố đầu tiên chạy trong thời gian tuyến tính cho mọi bảng chữ cái. Cụ thể hơn, đây là thuật toán thời gian tuyến tính đầu tiên cho xâu ký tự có bảng chữ cái kích thước đa thức. Thuật toán Farach nay đã trở thành thành phần cơ bản cho các thuật toán mới cho việc xây dựng cây hậu tố cũng như mảng hậu tố, trong bộ nhớ ngoài, nén, v.v...

Cây hậu tố tổng quát

Cây hậu tố tổng quát là cây hậu tố cho một tập hợp các xâu thay vì chỉ một xâu. Nó biểu diễn tất cả các hậu tố của tất cả các xâu trong tập hợp. Mỗi xâu phải dùng một ký tự kết thúc riêng biệt.

Xây dựng trên bộ nhớ ngoài

Bộ nhớ cây hậu tố đòi hỏi nhanh chóng vượt quá dung lượng bộ nhớ trong của máy tính thông thường khi độ dài các xâu đạt đến cỡ gigabyte. Khi đó, cần sử dụng các thuật toán cho bộ nhớ ngoài để xây dựng cây.
Có nhiều kết quả lý thuyết cho việc xây dựng cây hậu tố trong bộ nhớ ngoài. Thuật toán của Farach-Colton et al.  là tối ưu về mặt lý thuyết, với độ phức tạp I/O bằng với sắp xếp. Tuy nhiên, như đánh giá trong  thuật toán này là quá phức tạp nên vẫn chưa được sử dụng trong thực tế.
Mặt khác, đã có những nghiên cứu thực tế cho việc xây dựng cây hậu tố trên đĩa với tốc độ (một vài) GB/giờ. Các phương pháp tốt nhất hiện nay là TDD, TRELLIS , DiGeST, và B²ST .
TDD và TRELLIS chạy được cho tới kích thước của bộ gen người – khoảng 3 GB – tạo ra cây hậu tố kích thước khoảng vài chục gigabyte. Tuy nhiên các phương pháp này chưa thể chạy được cho các dữ liệu lớn hơn 3GB. DiGeST chạy nhanh hơn hẳn trong trường hợp này và xử lý xong dữ liệu 6GB trong 6 giờ. Có thể tìm mã nguồn và tài liệu của DiGeST ở  . Tất cả các phương pháp này là cho việc xây dựng cây hậu tố khi kích thước cây vượt quá kích thước bộ nhớ trong nhưng dữ liệu vào vẫn nằm ở bộ nhớ trong. Phương pháp mới nhất, B²ST, có thể xử lý được dữ liệu vượt ngoài kích thước bộ nhớ trong. ERA là một phương pháp xây dựng cây hậu tố song song mới nhanh hơn hẳn các phương pháp cũ. ERA có thể xử lý bộ gen người trong 19 phút trên một máy tính để bàn 8 nhân với 16GB RAM. Trên một cụm gồm 16 máy tính Linux (mỗi máy 4GB RAM), ERA có thể xử lý bộ gen người trong 9 phút.