✨Cây hậu tố

phải|Cây hậu tố cho xâu BANANA. Mỗi xâu con được kết thúc bởi ký tự đặc biệt $. Sáu đường từ gốc đến lá (ký hiệu bởi ô vuông) tương ứng với sáu hậu tố A$, NA$, ANA$, NANA$, ANANA$ và BANANA$. Các số trên lá là vị trí bắt đầu của hậu tố. Các liên kết hậu tố được vẽ bằng đường đứt né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 $S$ 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 $S$ 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 $S$.

Việc xây dựng cây hậu tố của xâu $S$ sử dụng thời gian và bộ nhớ tuyến tính với độ dài của $S$. 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 $S$, 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à $O(n\backslash log\; n)$ 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...

Định nghĩa

Cây hậu tố cho xâu $S$ độ dài $n$ là cây sao cho ( trang 90):

• các đường từ gốc tới lá có tương ứng 1-1 với các hậu tố của $S$,
• các cạnh đều có nhãn là các xâu khác rỗng,
• mọi nút trong (ngoại trừ nút gốc) đều có ít nhất hai con.

Do cây thỏa mãn tính chất trên có thể không tồn tại, ta chèn thêm vào cuối $S$ một ký tự đặc biệt không xuất hiện trong $S$(thường ký hiệu là $). Điều này đảm bảo không có hậu tố nào là tiền tố của một hậu tố khác, và có do đó cây có đúng $n$ nút lá, ứng với $n$ hậu tố của $S$. Do mọi nút trong khác gốc đều có hơn một con, cây có không quá n −  1 nút như vậy, và tổng cộng không quá n + (n − 1) + 1 = 2n nút (n lá, n − 1 nút trong khác gốc, 1 gốc).

Liên kết hậu tố là một yếu tố quan trọng của các thuật toán đầu tiên nhưng các thuật toán về sau dựa trên thuật toán Farach không sử dụng chúng. Trong cây hậu tố đầy đủ, mọi nút trong đều có một liên kết hậu tố tới một nút trong khác. Nếu đường từ gốc tới một nút ứng với xâu $\backslash chi\backslash alpha$, trong đó $\backslash chi$ là một ký tự và $\backslash alpha$ là một xâu (có thể rỗng), thì nó có liên kết hậu tố tới nút có đường từ gốc tới nó ứng với xâu $\backslash alpha$. Chẳng hạn trong ví dụ trên, liên kết hậu tố của ANA trỏ tới nút NA. Liên kết hậu tố cũng được sử dụng bởi nhiều thuật toán trên cây.

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.

Chức năng

Có thể xây dựng cây hậu tố cho xâu $S$ độ dài $n$ trong thời gian $\backslash Theta(n)$, nếu bảng chữ cái có kích thước đa thức (và do đó cũng đúng khi bảng chữ cái có kích thước hằng số).). ** Tìm cho mọi hậu tố của mẫu $P$, độ dài chuỗi giống nhau dài nhất giữa tiền tố của $P[i\backslash dots\; m]$ và các xâu con của $D$ trong thời gian $\backslash Theta(m)$ (

• Tìm kiếm xâu ký tự, trong thời gian O(m), trong đó m là độ dài mẫu cần tìm (với thời gian O(n) để xây dựng cây hậu tố trước khi tìm)
• Tìm kiếm xâu con lặp lại dài nhất
• Tìm kiếm xâu con chung dài nhất
• Tìm xâu con đối xứng dài nhất

Cây hậu tố thường được sử dụng trong các ứng dụng tin sinh học, tìm kiếm mẫu trong dãy DNA hoặc protein (có thể được xem là các xâu ký tự dài). Khả năng tìm kiếm cho phép có lỗi sai là một điểm mạnh của cấu trúc dữ liệu này. Cây hậu tố cũng được sử dụng trong nén dữ liệu; có thể dùng nó để tìm dữ liệu lặp lại cũng như trong giai đoạn sắp xếp của biến đổi Burrows–Wheeler. Một biến thể của thuật toán nén LZW sử dụng cây hậu tố (LZSS). Cây hậu tố được sử dụng trong phân nhóm cây hậu tố, một thuật toán phân nhóm dữ liệu dùng cho công cụ tìm kiếm (đưa ra đầu tiên bởi ).

Phương thức lập trình

Nếu mỗi nút và cạnh có thể được biểu diễn trong bộ nhớ $\backslash Theta(1)$, thì có thể lưu trữ cả cây trong bộ nhớ $\backslash Theta(n)$. Tổng độ dài các xâu trên các cạnh của cây là $O(n^2)$, nhưng có thể lưu mỗi cạnh bằng vị trí bắt đầu và kết thúc của một xâu con của S, nên tổng bộ nhớ cần dùng là $\backslash Theta(n)$. Trường hợp xấu nhất của bộ nhớ cần dùng cho cây hậu tố là khi dữ liệu vào là một từ fibonacci, đòi hỏi $2n$ nút.

Một lựa chọn quan trọng khi lập trình cây hậu tố là biểu diễn liên kết giữa nút cha và con trong cây. Cách đơn giản nhất là sử dụng danh sách liên kết gọi là danh sách chị em. Mỗi nút có một con trỏ trỏ tới nút con đầu tiên, và một con trỏ thứ hai trỏ tới nút kế tiếp trong danh sách chị em của nút đó. Cũng có thể sử dụng bảng băm, mảng đã sắp hoặc chưa sắp (sử dụng kĩ thuật gấp đôi mảng), hoặc cây nhị phân cân bằng. Mỗi lựa chọn cho một thời gian chạy khác nhau. Ta quan tâm tới:

• Chi phí tìm cạnh tới nút con có nhãn bắt đầu bằng một ký tự cho trước.
• Chi phí chèn thêm một nút con.
• Chi phí duyệt tất cả các nút con (chia trung bình cho mỗi nút con).

Đặt $\backslash sigma$ là kích thước bảng chữ cái. Khi đó các chi phí là như sau:

Ghi chú là chi phí chèn là chi phí trừ dần (do gấp đôi mảng) và chi phí của bảng băm là khi sử dụng băm hoàn hảo.

Lượng thông tin cần lưu cho mỗi cạnh và nút của cây hậu tố là rất tốn kém, tiêu tốn khoảng 10 đến 20 lần lượng bộ nhớ cần thiết để lưu xâu ký tự ban đầu. Mảng hậu tố giảm tỉ lệ này xuống còn 4 và các nhà nghiên cứu vẫn đang tìm cấu trúc dữ liệu mới để giảm tỉ lệ này xuống nhỏ hơn nữa.

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. . 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, 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.