markdown:
# Cây hậu tố
Trong
[khoa học máy tính](/wiki/Khoa_h%E1%BB%8Dc_m%C3%A1y_t%C3%ADnh), 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ố](/w/index.php?title=H%E1%BA%ADu_t%E1%BB%91_(khoa_h%E1%BB%8Dc_m%C3%A1y_t%C3%ADnh)&action=edit&redlink=1) của một [xâu kí tự](/w/index.php?title=X%C3%A2u_k%C3%AD_t%E1%BB%B1&action=edit&redlink=1) 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](/wiki/C%C3%A2y_(c%E1%BA%A5u_tr%C3%BAc_d%E1%BB%AF_li%E1%BB%87u)) 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ố](/w/index.php?title=C%C3%A2y_c%C6%A1_s%E1%BB%91&action=edit&redlink=1) (cụ thể hơn, nó là [cây Patricia](/w/index.php?title=C%C3%A2y_Patricia&action=edit&redlink=1)) 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](/w/index.php?title=X%C3%A2u_con&action=edit&redlink=1) 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](/wiki/Bi%E1%BB%83u_th%E1%BB%A9c_ch%C3%ADnh_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](/w/index.php?title=B%C3%A0i_to%C3%A1n_t%C3%ACm_x%C3%A2u_con_chung_d%C3%A0i_nh%E1%BA%A5t&action=edit&redlink=1). 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ự.
## Mục lục
[§](#L.E1.BB.8Bch_s.E1.BB.AD)Lịch sử[ [sửa](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&action=edit§ion=1)]
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à [1] [Donald Knuth](/wiki/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. [[2]](#cite_note-McC76-2) [[3]](#cite_note-Ukk95-3) Ukkonen đưa ra [[4]](#cite_note-GK97-4) [thuật toán trực tuyến](/wiki/Thu%E1%BA%ADt_to%C3%A1n_tr%E1%BB%B1c_tuy%E1%BA%BFn)đầu tiên cho việc xây dựng cây hậu tố, nay gọi là [thuật toán Ukkonen](/w/index.php?title=Thu%E1%BA%ADt_to%C3%A1n_Ukkonen&action=edit&redlink=1), 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\log n)](http://upload.wikimedia.org/math/f/4/9/f49341ab621f12e8cb93d0146ea51d34.png)
Năm 1997,
[Martin Farach](/w/index.php?title=Martin_Farach&action=edit&redlink=1) đư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. [5] [Thuật toán Farach](/w/index.php?title=Thu%E1%BA%ADt_to%C3%A1n_Farach&action=edit&redlink=1)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ố](/w/index.php?title=M%E1%BA%A3ng_h%E1%BA%ADu_t%E1%BB%91&action=edit&redlink=1), trong bộ nhớ ngoài, nén, v.v...
[§](#.C4.90.E1.BB.8Bnh_ngh.C4.A9a)Định nghĩa[ [sửa](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&action=edit§ion=2)]
Cây hậu tố cho xâu
độ dài
là cây sao cho (
trang 90): [6]
- các đường từ gốc tới lá có tương ứng 1-1 với các hậu tố của
,
- 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
một kí tự đặc biệt không xuất hiện trong
(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út lá, ứng với
hậu tố của
. 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 = 2 *n* 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](/w/index.php?title=Thu%E1%BA%ADt_to%C3%A1n_Farach&action=edit&redlink=1) 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
, trong đó
là một kí tự và
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
. 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.C3.A2y_h.E1.BA.ADu_t.E1.BB.91_t.E1.BB.95ng_qu.C3.A1t)Cây hậu tố tổng quát[ [sửa](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&veaction=edit&vesection=3) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&action=edit§ion=3)] [Cây hậu tố tổng quát](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91_t%E1%BB%95ng_qu%C3%A1t&action=edit&redlink=1) 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.E1.BB.A9c_n.C4.83ng)Chức năng[ [sửa](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&veaction=edit&vesection=4) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&action=edit§ion=4)]
Có thể xây dựng cây hậu tố cho xâu
độ dài
trong thời gian
, 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ố).
Với bảng chữ cái lớn hơn, đa số thời gian chạy là cho việc [5] [sắp xếp](/wiki/Thu%E1%BA%ADt_to%C3%A1n_s%E1%BA%AFp_x%E1%BA%BFp)các chữ cái để đưa chúng về kích thước ![ O(n)](http://upload.wikimedia.org/math/7/b/a/7ba55e7c64a9405a0b39a1107e90ca94.png)
![ O(n\log n)](http://upload.wikimedia.org/math/f/4/9/f49341ab621f12e8cb93d0146ea51d34.png)
Giả sử đã có cây hậu tố cho xâu
độ dài
, hoặc đã có
[cây hậu tố tổng quát](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91_t%E1%BB%95ng_qu%C3%A1t&action=edit&redlink=1) cho tập hợp các xâu
với tổng độ dài
. Ta có thể:
- Tìm kiếm xâu con:
- Kiểm tra xem xâu
độ dài
có phải xâu con hay không trong thời gian
(
trang 92). [[6]](#cite_note-Gus97-6)
- Tìm lần xuất hiện đầu tiên của một trong các mẫu
với tổng độ dài
trong thời gian
.
- Tìm tất cả
lần xuất hiện của các mẫu
với tổng độ dài
trong thời gian
(
trang 123). [[6]](#cite_note-Gus97-6)
- Tìm kiếm
[biểu thức chính quy](/wiki/Bi%E1%BB%83u_th%E1%BB%A9c_ch%C3%ADnh_quy) *P*trong thời gian kì vọng [dưới tuyến tính](/w/index.php?title=D%C6%B0%E1%BB%9Bi_tuy%E1%BA%BFn_t%C3%ADnh&action=edit&redlink=1)theo
(
). [[7]](#cite_note-BYG96-7)
- Tìm cho mọi hậu tố của mẫu
, độ dài chuỗi giống nhau dài nhất giữa tiền tố của
và các xâu con của
trong thời gian
(
trang 132). [[6]](#cite_note-Gus97-6)
- Kiểm tra xem xâu
- Xác định tính chất của xâu:
- Tìm
[xâu con chung dài nhất](/w/index.php?title=B%C3%A0i_to%C3%A1n_t%C3%ACm_x%C3%A2u_con_chung_d%C3%A0i_nh%E1%BA%A5t&action=edit&redlink=1)của xâu
và
trong thời gian
(
trang 125). [[6]](#cite_note-Gus97-6)
- Tìm tất cả
[cặp tối đại](/w/index.php?title=C%E1%BA%B7p_t%E1%BB%91i_%C4%91%E1%BA%A1i&action=edit&redlink=1)trong thời gian
(
trang 144). [[6]](#cite_note-Gus97-6)
- Tìm mọi phân tích
[Lempel–Ziv](/w/index.php?title=Lempel%E2%80%93Ziv&action=edit&redlink=1)trong thời gian
(
trang 166). [[6]](#cite_note-Gus97-6)
- Tìm
[xâu con lặp lại dài nhất](/w/index.php?title=B%C3%A0i_to%C3%A1n_t%C3%ACm_x%C3%A2u_con_l%E1%BA%B7p_l%E1%BA%A1i_d%C3%A0i_nh%E1%BA%A5t&action=edit&redlink=1)trong thời gian
.
- Tìm xâu con lặp lại nhiều lần nhất với chiều dài ít nhất một số cho trước trong thời gian
.
- Tìm xâu ngắn nhất dùng bảng chữ cái
mà không xuất hiện trong
, trong thời gian
, nếu có
xâu như vậy.
- Tìm xâu con ngắn nhất chỉ xuất hiện đúng một lần trong thời gian
.
- Tìm, với mỗi
, xâu con ngắn nhất của
không xuất hiện ở chỗ nào khác trong
trong thời gian
.
- Tìm
Có thể xây dựng một cấu trúc dữ liệu hỗ trợ cho cây hậu tố trong thời gian
để tìm
[tổ tiên chung thấp nhất](/w/index.php?title=T%E1%BB%95_ti%C3%AAn_chung_th%E1%BA%A5p_nh%E1%BA%A5t&action=edit&redlink=1) của các nút trong thời gian hằng số( chương 8). Khi đó có thể: [6]
- Tìm tiền tố chung dài nhất của hai hậu tố
và
trong thời gian
(
trang 196). [[6]](#cite_note-Gus97-6)
- Tìm mẫu
*P*độ dài *m*với không quá *k*lỗi sai trong thời gian
, trong đó
*z*là số lần xuất hiện ( trang 200). [[6]](#cite_note-Gus97-6)
- Tìm tất cả
[xâu đối xứng](/w/index.php?title=X%C3%A2u_%C4%91%E1%BB%91i_x%E1%BB%A9ng&action=edit&redlink=1)tối đại trong
(
trang 198), hoặc thời gian [[6]](#cite_note-Gus97-6)
nếu cho phép bỏ qua
kí tự, hoặc
nếu cho phép
lỗi sai (
trang 201). [[6]](#cite_note-Gus97-6)
- Tìm tất cả
xâu lặp lại hai lần liên tiếp nhau trong thời gian
, và nếu cho phép
*k*lỗi sai thì thời gian là
(
trang 204). [[6]](#cite_note-Gus97-6)
- Tìm
[xâu con chung dài nhất](/w/index.php?title=B%C3%A0i_to%C3%A1n_t%C3%ACm_x%C3%A2u_con_chung_d%C3%A0i_nh%E1%BA%A5t&action=edit&redlink=1)của ít nhất
xâu trong
với
trong thời gian
(
trang 205). [[6]](#cite_note-Gus97-6)
- Tìm
[xâu con đối xứng dài nhất](/w/index.php?title=X%C3%A2u_con_%C4%91%E1%BB%91i_x%E1%BB%A9ng_d%C3%A0i_nh%E1%BA%A5t&action=edit&redlink=1)của một xâu cho trước (bằng cây hậu tố của xâu cho trước và xâu ngược lại) trong thời gian tuyến tính ( trang 197–199). [[6]](#cite_note-Gus97-6)
[§](#.E1.BB.A8ng_d.E1.BB.A5ng)Ứng dụng[ [sửa](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&veaction=edit&vesection=5) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&action=edit§ion=5)]
Cây hậu tố được sử dụng rộng rãi để giải quyết các bài toán về xâu kí tự trong soạn thảo văn bản, tìm kiếm văn bản, tin sinh học, và nhiều lĩnh vực ứng dụng khác.
Các ứng dụng chính bao gồm: [8] [[8]](#cite_note-allisons-8) [Tìm kiếm xâu kí tự](/w/index.php?title=T%C3%ACm_ki%E1%BA%BFm_x%C3%A2u_k%C3%AD_t%E1%BB%B1&action=edit&redlink=1), 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](/wiki/Tin_sinh_h%E1%BB%8Dc), tìm kiếm mẫu trong dãy [DNA](/wiki/ADN) hoặc [protein](/wiki/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](/wiki/N%C3%A9n_d%E1%BB%AF_li%E1%BB%87u); 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](/w/index.php?title=Bi%E1%BA%BFn_%C4%91%E1%BB%95i_Burrows%E2%80%93Wheeler&action=edit&redlink=1). Một biến thể của thuật toán nén [LZW](/wiki/LZW) sử dụng cây hậu tố ( [LZSS](/w/index.php?title=LZSS&action=edit&redlink=1)). Cây hậu tố được sử dụng trong [phân nhóm cây hậu tố](/w/index.php?title=Ph%C3%A2n_nh%C3%B3m_c%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&action=edit&redlink=1), một thuật toán [phân nhóm dữ liệu](/wiki/Ph%C3%A2n_nh%C3%B3m_d%E1%BB%AF_li%E1%BB%87u) dùng cho công cụ tìm kiếm (đưa ra đầu tiên bởi ). [9]
[§](#Ph.C6.B0.C6.A1ng_th.E1.BB.A9c_l.E1.BA.ADp_tr.C3.ACnh)Phương thức lập trình[ [sửa](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&veaction=edit&vesection=6) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&action=edit§ion=6)]
Nếu mỗi nút và cạnh có thể được biểu diễn trong bộ nhớ
, thì có thể lưu trữ cả cây trong bộ nhớ
. Tổng độ dài các xâu trên các cạnh của cây là
, 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à
. 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](/w/index.php?title=T%E1%BB%AB_fibonacci&action=edit&redlink=1), đòi hỏi
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](/w/index.php?title=Danh_s%C3%A1ch_li%C3%AAn_k%E1%BA%BFt&action=edit&redlink=1) 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](/wiki/B%E1%BA%A3ng_b%C4%83m), [mảng](/w/index.php?title=C%E1%BA%A5u_tr%C3%BAc_d%E1%BB%AF_li%E1%BB%87u_m%E1%BA%A3ng&action=edit&redlink=1) đã sắp hoặc chưa sắp (sử dụng kĩ thuật [gấp đôi mảng](/w/index.php?title=M%E1%BA%A3ng_%C4%91%E1%BB%99ng&action=edit&redlink=1)), hoặc [cây nhị phân cân bằng](/w/index.php?title=C%C3%A2y_nh%E1%BB%8B_ph%C3%A2n_c%C3%A2n_b%E1%BA%B1ng&action=edit&redlink=1). 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
là kích thước bảng chữ cái. Khi đó các chi phí là như sau:
|Tìm kiếm||Chèn||Duyệt|
|Danh sách chị em / mảng chưa sắp||
|![]()
|
|![]()
|
|![]()
|Bảng băm||
|![]()
|
|![]()
|
|![]()
|Cây tìm kiếm cân bằng||
|![]()
|
|![]()
|
|![]()
|Mảng đã sắp||
|![]()
|
|![]()
|
|![]()
|Bảng băm + danh sách chị em||
|![]()
|
|![]()
|
|![]()
Ghi chú là chi phí chèn là chi phí trừ dần (do
[gấp đôi mảng](/w/index.php?title=G%E1%BA%A5p_%C4%91%C3%B4i_m%E1%BA%A3ng&action=edit&redlink=1)) 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ố](/w/index.php?title=M%E1%BA%A3ng_h%E1%BA%ADu_t%E1%BB%91&action=edit&redlink=1) 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.C3.A2y_d.E1.BB.B1ng_tr.C3.AAn_b.E1.BB.99_nh.E1.BB.9B_ngo.C3.A0i)Xây dựng trên bộ nhớ ngoài[ [sửa](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&veaction=edit&vesection=7) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&action=edit§ion=7)]
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 [10] 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ế. [[11]](#cite_note-Smyth03-11)
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 , [12] DiGeST, [[13]](#cite_note-trellis-13) và B [[14]](#cite_note-digest-14) 2ST . [[15]](#cite_note-b2st-15)
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.
[[12]](#cite_note-tdd-12) 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. [13] 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ờ. [[14]](#cite_note-digest-14) Có thể tìm mã nguồn và tài liệu của DiGeST ở [[14]](#cite_note-digest-14) . 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 [[16]](#cite_note-digestimpl-16) 2ST, có thể xử lý được dữ liệu vượt ngoài kích thước bộ nhớ trong. ERA [[15]](#cite_note-b2st-15) 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. [[17]](#cite_note-Mansour2011-17)
[§](#Xem_th.C3.AAm)Xem thêm[ [sửa](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&veaction=edit&vesection=8) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&action=edit§ion=8)]
[§](#T.C3.A0i_li.E1.BB.87u_tham_kh.E1.BA.A3o)Tài liệu tham khảo[ [sửa](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&veaction=edit&vesection=9) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&action=edit§ion=9)] **P. Weiner (1973). “Linear pattern matching algorithm”.** [^](#cite_ref-Wei73_1-0) *14th Annual IEEE Symposium on Switching and Automata Theory*. tr. 1–11. [doi](/wiki/DOI): [10.1109/SWAT.1973.13](http://dx.doi.org/10.1109%2FSWAT.1973.13). **Edward M. McCreight (1976). “A Space-Economical Suffix Tree Construction Algorithm”.** [^](#cite_ref-McC76_2-0) *Journal of the ACM* **23**(2): 262–272. [doi](/wiki/DOI): [10.1145/321941.321946](http://dx.doi.org/10.1145%2F321941.321946). **E. Ukkonen (1995).** [^](#cite_ref-Ukk95_3-0) [“On-line construction of suffix trees”](http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf). *Algorithmica* **14**(3): 249–260. [doi](/wiki/DOI): [10.1007/BF01206331](http://dx.doi.org/10.1007%2FBF01206331). **R. Giegerich and S. Kurtz (1997).** [^](#cite_ref-GK97_4-0) [“From Ukkonen to McCreight and Weiner: A Unifying View of Linear-Time Suffix Tree Construction”](http://www.zbh.uni-hamburg.de/staff/kurtz/papers/GieKur1997.pdf). *Algorithmica* **19**(3): 331–353. [doi](/wiki/DOI): [10.1007/PL00009177](http://dx.doi.org/10.1007%2FPL00009177).
- ^
**a** [M. Farach (1997).](#cite_ref-Far97_5-1) **ă** [“Optimal Suffix Tree Construction with Large Alphabets”](http://www.cs.rutgers.edu/~farach/pubs/Suffix.pdf). *FOCS*: 137–143.
- ^
**a** **ă** **â** **b** **c** **d** **đ** **e** **ê** **g** **h** **i** **k** **l** [Gusfield, Dan (1999) [1997].](#cite_ref-Gus97_6-14) **m** *Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology*. USA: Cambridge University Press. [ISBN](/wiki/ISBN) [0-521-58519-8](/wiki/%C4%90%E1%BA%B7c_bi%E1%BB%87t:Ngu%E1%BB%93n_s%C3%A1ch/0-521-58519-8). **Ricardo A. Baeza-Yates and Gaston H. Gonnet (1996). “Fast text searching for regular expressions or automaton searching on tries”.** [^](#cite_ref-BYG96_7-0) *Journal of the ACM*(ACM Press) **43**(6): 915–936. [doi](/wiki/DOI): [10.1145/235809.235810](http://dx.doi.org/10.1145%2F235809.235810). Đã bỏ qua tham số không rõ
|address=(
[trợ giúp](//en.wikipedia.org/wiki/Help:CS1_errors#parameter_ignored))
- ^
**a** [Allison, L.](#cite_ref-allisons_8-1) **ă** [“Suffix Trees”](http://www.allisons.org/ll/AlgDS/Tree/Suffix/). Truy cập ngày 14 tháng 10 năm 2008. **Oren Zamir and Oren Etzioni (1998). “Web document clustering: a feasibility demonstration”.** [^](#cite_ref-zamir98_9-0) *SIGIR '98: Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval*. ACM. tr. 46–54. Đã bỏ qua tham số không rõ
|address=(
[trợ giúp](//en.wikipedia.org/wiki/Help:CS1_errors#parameter_ignored)) **Martin Farach-Colton, Paolo Ferragina, S. Muthukrishnan (2000). “On the sorting-complexity of suffix tree construction.”.** [^](#cite_ref-F00_10-0) *Journal of the ACM* **47**(6): 987–1011. [doi](/wiki/DOI): [10.1145/355541.355547](http://dx.doi.org/10.1145%2F355541.355547). **Smyth, William (2003).** [^](#cite_ref-Smyth03_11-0) *Computing Patterns in Strings*. [Addison-Wesley](/w/index.php?title=Addison-Wesley&action=edit&redlink=1).
- ^
**a** [Sandeep Tata, Richard A. Hankins, and Jignesh M. Patel (2003). “Practical Suffix Tree Construction”.](#cite_ref-tdd_12-1) **ă** *VLDB '03: Proceedings of the 30th International Conference on Very Large Data Bases*. Morgan Kaufmann. tr. 36–47.
- ^
**a** [Benjarath Phoophakdee and Mohammed J. Zaki (2007). “Genome-scale disk-based suffix tree indexing”.](#cite_ref-trellis_13-1) **ă** *SIGMOD '07: Proceedings of the ACM SIGMOD International Conference on Management of Data*. ACM. tr. 833–844. Đã bỏ qua tham số không rõ
|address=(
[trợ giúp](//en.wikipedia.org/wiki/Help:CS1_errors#parameter_ignored))
- ^
**a** **ă** [Marina Barsky, Ulrike Stege, Alex Thomo, and Chris Upton (2008). “A new method for indexing genomes using on-disk suffix trees”.](#cite_ref-digest_14-2) **â** *CIKM '08: Proceedings of the 17th ACM Conference on Information and Knowledge Management*. ACM. tr. 649–658. Đã bỏ qua tham số không rõ
|address=(
[trợ giúp](//en.wikipedia.org/wiki/Help:CS1_errors#parameter_ignored))
- ^
**a** [Marina Barsky, Ulrike Stege, Alex Thomo, and Chris Upton (2009). “Suffix trees for very large genomic sequences”.](#cite_ref-b2st_15-1) **ă** *CIKM '09: Proceedings of the 18th ACM Conference on Information and Knowledge Management*. ACM. Đã bỏ qua tham số không rõ
|address=(
[trợ giúp](//en.wikipedia.org/wiki/Help:CS1_errors#parameter_ignored)) [^](#cite_ref-digestimpl_16-0) [“The disk-based suffix tree for pattern search in sequenced genomes”](http://webhome.cs.uvic.ca/~mgbarsky/DIGEST_SEARCH). Truy cập ngày 15 tháng 10 năm 2009. **Mansour, Essam; Amin Allam, Spiros Skiadopoulos, Panos Kalnis (2011).** [^](#cite_ref-Mansour2011_17-0) [“ERA: Efficient Serial and Parallel Suffix Tree Construction for Very Long Strings”](http://www.vldb.org/pvldb/vol5/p049_essammansour_vldb2012.pdf). *PVLDB* **5**(1): 49–60. Truy cập ngày 4 tháng 11 năm 2011.
[§](#Li.C3.AAn_k.E1.BA.BFt_ngo.C3.A0i)Liên kết ngoài[ [sửa](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&veaction=edit&vesection=10) | [sửa mã nguồn](/w/index.php?title=C%C3%A2y_h%E1%BA%ADu_t%E1%BB%91&action=edit§ion=10)] [Cây hậu tố](http://www.cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm)bởi [Sartaj Sahni](/w/index.php?title=Sartaj_Sahni&action=edit&redlink=1) [Cây hậu tố](http://www.allisons.org/ll/AlgDS/Tree/Suffix/)bởi Lloyd Allison [Định nghĩa cây hậu tố tại NIST](http://www.nist.gov/dads/HTML/suffixtree.html) [suffix_tree](http://mila.cs.technion.ac.il/~yona/suffix_tree/)Thuật toán cây hậu tố viết bằng ngôn ngữ ANSI C [libstree](http://www.cl.cam.ac.uk/~cpk25/libstree/), một thư viện cây hậu tố viết bằng ngôn ngữ C [Tree::Suffix](http://search.cpan.org/dist/Tree-Suffix/), giao diện Perl cho libstree [Strmat](http://www.cs.ucdavis.edu/~gusfield/strmat.html)một thư viện cây hậu tố viết bằng C (dùng mảng thay vì danh sách liên kết) [SuffixTree](http://hkn.eecs.berkeley.edu/~dyoo/python/suffix_trees/)giao diện Python cho Strmat [Universal Data Compression Based on the Burrows-Wheeler Transformation: Theory and Practice](http://www.balkenhol.net/papers/t1043.pdf.gz), ứng dụng của cây hậu tố cho BWT [Theory and Practice of Succinct Data Structures](http://www.cs.helsinki.fi/group/suds/), thuật toán cây hậu tố viết bằng ngôn ngữ C++ [Practical Algorithm Template Library](http://code.google.com/p/patl/), một thư viện cây hậu tố viết bằng C++ bởi Roman S. Klyujkov [Thuật toán cây hậu tố viết bằng Java](http://en.literateprograms.org/Suffix_tree_(Java))
|
|
Cây hậu tố · |Cây
|k-d
|Cây không nhị phân||
|
|Cây phân chia không gian||
|
|Các cây khác||
|

X-Content-Type-Options: nosniff

Content-language: vi

X-UA-Compatible: IE=Edge

Vary: Accept-Encoding,Cookie

Via: 1.1 varnish, 1.1 varnish

X-Cache: cp1054 miss (0), cp1067 frontend miss (0)

Cache-Control: private, s-maxage=0, max-age=0, must-revalidate


markdown:
# Fort Jennings, Ohio
Bách khoa toàn thư mở Wikipedia
|
|Fort Jennings, Ohio
|—
| —
|
|[40°54′17″B 84°17′53″T / 40,9047°B 84,2981°T](//tools.wmflabs.org/geohack/geohack.php?language=vi&pagename=Fort_Jennings%2C_Ohio¶ms=40.9047_N_-84.2981_E_type:city(485)_region:US-OH_globe:earth) [Quốc gia](/wiki/Qu%E1%BB%91c_gia) [Hoa Kỳ](/wiki/Hoa_K%E1%BB%B3) [Tiểu bang](/wiki/Ti%E1%BB%83u_bang_Hoa_K%E1%BB%B3) [Ohio](/wiki/Ohio) [Quận](/w/index.php?title=Danh_s%C3%A1ch_c%C3%A1c_qu%E1%BA%ADn_%E1%BB%9F_Ohio&action=edit&redlink=1) [Quận Putnam](/wiki/Qu%E1%BA%ADn_Putnam,_Ohio) **Dân số**(2010) [Múi giờ](/wiki/M%C3%BAi_gi%E1%BB%9D) [CST](/wiki/M%C3%BAi_gi%E1%BB%9D_mi%E1%BB%81n_Trung_(B%E1%BA%AFc_M%E1%BB%B9))( [UTC-5](/wiki/UTC-5)) [DST](/wiki/Quy_%C6%B0%E1%BB%9Bc_gi%E1%BB%9D_m%C3%B9a_h%C3%A8)) **CDT**( [UTC-4](/wiki/UTC-4)) **Fort Jennings** là một [làng](/wiki/L%C3%A0ng) thuộc [quận Putnam](/wiki/Qu%E1%BA%ADn_Putnam,_Ohio), tiểu bang [Ohio](/wiki/Ohio), [Hoa Kỳ](/wiki/Hoa_K%E1%BB%B3). Năm 2010, dân số của làng này là 485 người. [[1]](#cite_note-1)
## Dân số[
[sửa](/w/index.php?title=Fort_Jennings,_Ohio&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=Fort_Jennings,_Ohio&action=edit§ion=1)]
- Dân số năm 2000: 432 người.
- Dân số năm 2010: 485 người.
## Chú thích[
[sửa](/w/index.php?title=Fort_Jennings,_Ohio&veaction=edit&vesection=2) | [sửa mã nguồn](/w/index.php?title=Fort_Jennings,_Ohio&action=edit§ion=2)] [^](#cite_ref-1) [“2010 Census Gazetteer Files”](http://www.census.gov/geo/www/gazetteer/gazetteer2010.html). [Cục Thống kê Dân số Hoa Kỳ](/wiki/C%E1%BB%A5c_Th%E1%BB%91ng_k%C3%AA_D%C3%A2n_s%E1%BB%91_Hoa_K%E1%BB%B3). Truy cập ngày 16 tháng 10 năm 2012.

WARC-Type: response

Content-Type: application/http; msgtype=response

Content-Type: text/html; charset=UTF-8

Connection: close

Content-Encoding: gzip

Accept-Ranges: bytes

X-Cache: cp1068 miss (0), cp1067 frontend miss (0)


markdown:
# Tòa nhà Chrysler
|Chrysler Building|
|Kỷ lục chiều cao|
|Là công trình cao nhất thế giới từ năm 27 tháng 5 năm 1930 đến năm
|[40 Wall Street](/w/index.php?title=40_Wall_Street&action=edit&redlink=1) [Empire State Building](/wiki/T%C3%B2a_nh%C3%A0_Empire_State) [Lexington Avenue](/w/index.php?title=Lexington_Avenue&action=edit&redlink=1), [New York](/wiki/Manhattan), [New York](/wiki/Th%C3%A0nh_ph%E1%BB%91_New_York), [Mỹ](/wiki/Hoa_K%E1%BB%B3)
111.201 sq. m
[William Van Alen](/w/index.php?title=William_Van_Alen&action=edit&redlink=1)
Chrysler Building là một
[nhà chọc trời](/wiki/Nh%C3%A0_ch%E1%BB%8Dc_tr%E1%BB%9Di) [Art Deco](/wiki/Art_Deco) ở phía đông của [Manhattan](/wiki/Manhattan), [Thành phố New York](/wiki/Th%C3%A0nh_ph%E1%BB%91_New_York), [Hoa Kỳ](/wiki/Hoa_K%E1%BB%B3), tại giao lộ của [42nd Street](/w/index.php?title=42nd_Street&action=edit&redlink=1) và [Lexington Avenue](/w/index.php?title=Lexington_Avenue_(Manhattan)&action=edit&redlink=1). Tòa nhà này có chiều cao 319 m với 77 tầng., . Hoàn thành năm [1] [1930](/wiki/1930). Đến thời điểm đầu năm 2008, đây là [cao thứ 26 thế giới](/wiki/Danh_s%C3%A1ch_c%C3%B4ng_tr%C3%ACnh_cao_nh%E1%BA%A5t_th%E1%BA%BF_gi%E1%BB%9Bi). Tòa nhà này trong một thời gian ngắn là tòa nhà cao nhất thế giới trước khi bị [Empire State Building](/wiki/T%C3%B2a_nh%C3%A0_Empire_State)quan mặt năm 1931. Tuy nhiên, Chrysler Building vẫn là tòa nhà bằng gạch cao nhất thế giới. [[2]](#cite_note-2) Sau vụ khủng bố phá hủy [[3]](#cite_note-3) [Trung tâm Thương mại Thế giới](/wiki/Trung_t%C3%A2m_Th%C6%B0%C6%A1ng_m%E1%BA%A1i_Th%E1%BA%BF_gi%E1%BB%9Bi), nó lại một lần nữa là tòa nhà cao thứ hai ở Thành phố New York cho đến tháng 12 năm 2007, khi chóp của [Bank of America](/wiki/Bank_of_America_Tower_(New_York))cao 385,8 m, đẩy Chrysler Building xuống vị trí thứ 3. Ngoài ra [New York Times Building](/wiki/T%C3%B2a_nh%C3%A0_New_York_Times), khai trương năm 2007, cao ngang với Chrysler Building, cho nên hai tháp này đồng hạng 3. . [[4]](#cite_note-4)
## Tham khảo[
[sửa](/w/index.php?title=T%C3%B2a_nh%C3%A0_Chrysler&veaction=edit&vesection=1) | [sửa mã nguồn](/w/index.php?title=T%C3%B2a_nh%C3%A0_Chrysler&action=edit§ion=1)]
Phương tiện liên quan tới
[Chrysler Building](//commons.wikimedia.org/wiki/Category:Chrysler_Building) tại [Wikimedia Commons](/wiki/Wikimedia_Commons)
|Trước||
|Tòa nhà Chrysler |Sau|
|
||
|
|
|

X-Cache: cp1065 miss (0), cp1053 frontend miss (0)


markdown:
# wake
Từ điển mở Wiktionary
## Mục lục
[§](#Ti.E1.BA.BFng_Anh)Tiếng Anh[ [sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-eng-&action=edit§ion=T-1)]
[§](#C.C3.A1ch_ph.C3.A1t_.C3.A2m)Cách phát âm[ [sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-pron-&action=edit§ion=T-1)]
[§](#Danh_t.E1.BB.AB)Danh từ[ [sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-noun-&action=edit§ion=T-1)] **wake** [/ˈweɪk/](/wiki/Wiktionary:IPA)
[§](#Th.C3.A0nh_ng.E1.BB.AF)Thành ngữ[ [sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-expr-&action=edit§ion=T-1)] **to follow in the wake of somebody**:
- Theo
[chân](/wiki/ch%C3%A2n)ai, theo [liền](/wiki/li%E1%BB%81n) [ngay](/wiki/ngay)sau ai.
- (
*Nghĩa bóng*) [Theo gương](/wiki/theo_g%C6%B0%C6%A1ng)ai.
- Theo
[§](#Danh_t.E1.BB.AB_2)Danh từ[ [sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-noun-&action=edit§ion=T-1)] **wake** [/ˈweɪk/](/wiki/Wiktionary:IPA)
[§](#N.E1.BB.99i_.C4.91.E1.BB.99ng_t.E1.BB.AB)Nội động từ[ [sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-intr-verb-&action=edit§ion=T-1)] **wake** *nội động từ (woke, waked; waked, woken)* [/ˈweɪk/](/wiki/Wiktionary:IPA)
[§](#Ngo.E1.BA.A1i_.C4.91.E1.BB.99ng_t.E1.BB.AB)Ngoại động từ[ [sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-tr-verb-&action=edit§ion=T-1)] **wake** *ngoại động từ* [/ˈweɪk/](/wiki/Wiktionary:IPA)
- Đánh
[thức](/wiki/th%E1%BB%A9c).
- Làm
[hồi tỉnh](/wiki/h%E1%BB%93i_t%E1%BB%89nh)lại, làm [sống lại](/wiki/s%E1%BB%91ng_l%E1%BA%A1i).
- Làm
[náo động](/wiki/n%C3%A1o_%C4%91%E1%BB%99ng)(nơi nào); [phá](/wiki/ph%C3%A1)(sự yên tĩnh).
- Làm
[dội](/wiki/d%E1%BB%99i)lại (tiếng vang). [Khêu gợi](/wiki/kh%C3%AAu_g%E1%BB%A3i), [gợi lại](/w/index.php?title=g%E1%BB%A3i_l%E1%BA%A1i&action=edit&redlink=1)(một kỷ niệm). *to*— gợi lại những ký ức **wake**memories *to*— khêu gợi dục vọng **wake**desires
-
[Thức](/wiki/th%E1%BB%A9c) [canh](/wiki/canh)(người chết).
[§](#Chia_.C4.91.E1.BB.99ng_t.E1.BB.AB)Chia động từ[ [sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-forms-&action=edit§ion=T-1)]
wake
|Dạng không chỉ ngôi|
|Động từ
|**wake** [Phân từ](/wiki/ph%C3%A2n_t%E1%BB%AB) [hiện tại](/wiki/hi%E1%BB%87n_t%E1%BA%A1i) [waking](/wiki/waking) [quá khứ](/wiki/qu%C3%A1_kh%E1%BB%A9) [waked](/wiki/waked) [Lối trình bày](/wiki/l%E1%BB%91i_tr%C3%ACnh_b%C3%A0y) **wake** **wake**hoặc [wakest](/w/index.php?title=wakest&action=edit&redlink=1)¹ [wakes](/wiki/wakes)hoặc [waketh](/w/index.php?title=waketh&action=edit&redlink=1)¹ **wake** **wake** **wake** [waked](/wiki/waked) [waked](/wiki/waked)hoặc [wakedst](/w/index.php?title=wakedst&action=edit&redlink=1)¹ [waked](/wiki/waked) [waked](/wiki/waked) [waked](/wiki/waked) [waked](/wiki/waked) [Tương lai](/wiki/t%C6%B0%C6%A1ng_lai) [will](/wiki/will)/ [shall](/wiki/shall)² **wake** **wake**hoặc [wilt](/wiki/wilt)/ [shalt](/wiki/shalt)¹ **wake** **wake** **wake** **wake** **wake** [Lối cầu khẩn](/wiki/l%E1%BB%91i_c%E1%BA%A7u_kh%E1%BA%A9n) **wake** **wake**hoặc [wakest](/w/index.php?title=wakest&action=edit&redlink=1)¹ **wake** **wake** **wake** **wake** [waked](/wiki/waked) [waked](/wiki/waked) [waked](/wiki/waked) [waked](/wiki/waked) [waked](/wiki/waked) [waked](/wiki/waked) [were](/wiki/were)to **wake**hoặc [should](/wiki/should) **wake** **wake**hoặc should **wake** **wake**hoặc should **wake** **wake**hoặc should **wake** **wake**hoặc should **wake** **wake**hoặc should **wake** [Lối mệnh lệnh](/wiki/l%E1%BB%91i_m%E1%BB%87nh_l%E1%BB%87nh) **wake** **wake** **wake**
- Cách chia động từ cổ.
- Thường nói
*will*; chỉ nói *shall*để nhấn mạnh. Ngày xưa, ở ngôi thứ nhất, thường nói *shall*và chỉ nói *will*để nhấn mạnh.
[§](#Tham_kh.E1.BA.A3o)Tham khảo[ [sửa](/w/index.php?title=B%E1%BA%A3n_m%E1%BA%ABu:-ref-&action=edit§ion=T-1)]
- Hồ Ngọc Đức,
[Dự án Từ điển tiếng Việt miễn phí](http://www.informatik.uni-leipzig.de/~duc/Dict/)( [chi tiết](/wiki/Wiktionary:Ngu%E1%BB%93n_g%E1%BB%91c/FVDP))

X-Cache: cp1054 miss (0), cp1066 frontend miss (0)


markdown:
![ dvi](https://photo.tinhte.vn/store/avatars/l/475/475767.jpg?1394077624)
- Hoạt động lần cuối:
- 11/3/15
- Tham gia:
- 30/3/10
- Bài viết:
- 62
- Được thích:
- 6
- Điểm thưởng:
[8](members/dvi.475767/trophies)
# dvi
Thành viên, 35, from
[Da Nang, Vietnam, Vietnam](misc/location-info?location=Da+Nang%2C+Vietnam%2C+Vietnam)
- dvi lần cuối xem:
- 11/3/15
- Đang tải...
-
Không có tin nhắn trong hồ sơ của dvi.
- Đang tải...
- Đang tải...
-
### Giới thiệu
### Tương tác
- Đang tải...

Server: LiteSpeed

Vary: User-Agent

Cache-control: private, max-age=0

Set-Cookie: xf_session=699607c275415d02160ceabc40a286a4; path=/; secure; httponly

X-Frame-Options: SAMEORIGIN