Nếu bạn chưa nắm được SA (suffix array) bạn có thể đọc bài viết này nếu muốn :)
1. Prefix - Suffix (tiền tố - hậu tố)
- Cho xâu X có độ dài N kí tự, đánh số từ 0 đến N-1 từ trái sang phải ; xâu X chỉ gồm các kí tự in thường trong bảng chữ cái latin ( a,b,c,d .....,z ).- Xâu P ( độ dài P là p < =N ) gọi là Prefix của xâu X khi và chỉ khi P trùng với p kí tự đầu tiên của X, tức là P = X[ 0...(p-1) ]. Một cách hiểu khác: Tồn tại 1 xâu Y thỏa mãn X = PY thì P là tiền tố của X.
Ví dụ : X = abcdef ; P = abc => Y = def và P là tiền tố của X.
X = abcdef ; P = abb => P không là tiền tố của X.
- Xâu S ( độ dài là m < =N ) gọi là Suffix của xâu X khi và chỉ khi S trùng với m kí tự cuối cùng của X, tức là S = X[ (N-m)....(N-1) ]. Một cách hiểu khác: Tồn tại 1 xâu Z thỏa mãn X = ZS thì S là hậu tố của X.
Ví dụ : X = abcdef ; P = def => Z = abc và S là hậu tố của X.
X = abcdef ; P = de => S không là hậu tố của X.
- Tính chất 1 : Tính chất này mang tính "bắc cầu" :"3
- ( a là tiền tố của b ) + ( b là tiền tố của c ) => ( a cũng là tiền tố của c ).
- ( a là hậu tố của b ) + ( b là hậu tố của c ) => ( a cũng là hậu tố của c ).
Cả 2 tính chất này cực kì dễ chứng minh, nó giống như một nhận xét mặc nhiên đúng vậy : )
- Ký hiệu lưu ý: cho xâu a, độ dài xâu a sẽ được kí hiệu là |a|.
- Tính chất 2 :
- ( a là tiền tố của c ) + ( b là tiền tố của c ) + ( |a| <= |b| ) => ( a là tiền tố của b ).
- ( a là hậu tố của c ) + ( b là hậu tố của c ) + ( |a| <= |b| ) => ( a là hậu tố của b ) .
Cái tính chất này lại càng dễ chứng minh. bạn đọc tự hiểu nha : p
2. Substring (xâu con)
- Cho 2 xâu P (độ dài |P|) và S (độ dài |S|). Nếu xâu P xuất hiện tại một vị trí nào đó trong xâu S thì P là substring của xâu S. ( hay P là một dãy các kí tự liên tiếp bất kì trong S )- Hay nói cách khác, tức là P = S[ k......(k+|P|) ], k là vị trí mà T xuất hiện trong S.
- Một cách hiểu khác, P là xâu con của S khi và chỉ khi P là tiền tố của 1 hậu tố của S. (hoặc P là hậu tố của một tiền tố của S ).
- P là xâu con của S, thì S là xâu mẹ của T.
Ví dụ: S = BANANA T= ANA dể thấy rằng T xuất hiện tại vị trí k=1, đồng thời T là tiền tố của hậu tố ANANA.......... ah quên nữa, T cũng là hậu tố của tiền tố BANA.
3. Suffix Array
Rồi, cuối cùng cũng đến trọng tâm của bài viết này, phần đầu dài dòng lê thê quá =.=`
- Cho xâu T = t[0] t[1] t[2] t[3] t[4] ...... t[n-1] , độ dài là n kí tự, chỉ chứa kí tự trong bảng chữ cái latin.
- Dễ thấy T có n hậu tố, các hậu tố này có dạng : t[k] t[k+1] .......t[n-1] với k=0 .....n-1, các hậu tố có đặc điểm chung là substring của xâu T mà kí tự cuối luôn là t[n-1]. Vì thế ta sẽ đồng nhất mỗi hậu tố với k ( là vị trí bắt đầu của hậu tố đó, còn kết thúc luôn là cuối xâu mẹ T rồi ) để tiện xử lí và tiết kiệm bộ nhớ.
**** Nhắc lại về thứ tự từ điển : Các kí tự được sắp xếp theo một trật tự nhất định, được quy định rõ ràng trong bảng chữ cái a < b < c < d < e < f < .... < y < z. Kí hiệu a < b ám chỉ a có thứ tự từ điển nhỏ hơn b.
- Cho 2 xâu A = a[0] a[1] a[2] a[3] ... a[n-1] và B = b[0] b[1] b[2] b[3] ..... b[m-1].
Ta nói A có thứ tự từ điển nhỏ hơn B khi và chỉ khi tồn tại 0 <= k <= n-1 và 0<= k<= m-1 thỏa mãn: A[0...(k-1)]=B[0..(k-1)] và a[k] < b[k].
Ví dụ : A = abcdef
B = abdefg dễ dàng thấy k=2, A[0..1] = B[0..1] = ab và a[2]=c < b[2] =d.
suy ra A<B.
suy ra A<B.
** Lưu ý : ab < abc, a < ana ......... kí tự trống coi như < a < b .......
- Quay lại vấn đề chính, mỗi hậu tố được đồng nhất với k là vị trí bắt đầu của nó, xâu T có n hậu tố, như vậy ta sẽ sắp xếp các hậu tố này theo thứ tự từ điển tăng dần và lưu vào một mảng, mảng này chính là suffix array.
Ví dụ: T = banana
Các hậu tố : 0 - banana
1 - anana
2 - nana- Quay lại vấn đề chính, mỗi hậu tố được đồng nhất với k là vị trí bắt đầu của nó, xâu T có n hậu tố, như vậy ta sẽ sắp xếp các hậu tố này theo thứ tự từ điển tăng dần và lưu vào một mảng, mảng này chính là suffix array.
Ví dụ: T = banana
Các hậu tố : 0 - banana
1 - anana
3 - ana
4 - na
5 - a
bây h ta sẽ sắp xếp các hậu tố này theo thứ tự từ điển
5 - a
3 - ana
1 - anana
0 - banana
4 - na
2 - nana
Vậy mảng suffix array của chúng ta là SA = { 5 , 3 , 1 , 0, 4, 2 }
4. Cách xây dựng SA (suffix array)
- Đây có lẽ là vấn đề đau đầu nhức óc nhất khi mới học về cấu trúc dữ liệu này, haizzz dà
* Vấn đề đặt ra: Cho xâu T, độ dài n<=10^5 , xây dựng SA
- Thứ nhất, độ phức tạp khi xây dựng SA là cỡ bao nhiêu ?
+ Ban đầu suffix array được xây dựng dựa theo Trie hay suffix tree (nếu chưa biết về 2 cái này, các bạn có thể google search, hoặc mình sẽ viết nó trong thời gian đến ^.^) với độ phức tạp bậc 2 (cỡ O(n^2), ko nhớ chính xác, mà to cỡ đấy). Chậc chậc, 100K mũ 2 = 10 tỷ, máy tính cá nhân chạy tầm 20s, time này quá lâu, rõ ràng phương pháp ban đầu này hoàn toàn ko hiệu quả chút nào.
+ Sau đó người ta đã nghiên cứu và đưa ra phương pháp xây dựng trực tiếp SA mà không cần thông qua Trie hay suffix Tree nữa với độ phức tạp dao động trong khoảng O(n) đến O(n*logn). Nhưng trong hầu hết trường hợp thì độ phức tạp chỉ lớn hơn O(n) đôi chút, trường hợp cực xấu mới lớn đến mức O(n*logn), rõ ràng với n< 100K thỳ thuật toán này hoàn toán đáp ứng yêu cầu về time chạy chương trình. Cộng thêm 1 điều rằng việc code thuật toán này cũng không quá khó khăn, nếu bạn luyện thành thục nó.
**P/s: đã có người nghĩ ra cách xây dựng SA với đpt luôn là O(n), nhưng khá là phức tạp, ( nhìn cái code không thôi là đuối rồi, code xong chắc xỉu tại chỗ, vả lại thi cử thì yếu tố thời gian cực kì quan trọng, việc code 1 chương trình quá phức tạp trong thời gian không cho phép là 1 điều cực kì mạo hiểm, ảnh hưởng nghiêm trọng đến kết quả cá nhân cũng như thành tích chung của đội tuyển, nên nhớ 1 chương trình dù dùng kĩ thuật cao siêu đến đâu mà cài sai thì cũng không bằng 1 chương trình sử dụng kĩ thuật tầm thường.)
Rồi, không nói nhiều dài dòng bên lề nữa, chúng ta sẽ nghiên cứu thuật toán đpt O(n) ~ O(n*logn).
Quay lại giải quyết vấn đề nói ở đầu mục, để có được SA của T thì ta phải dùng các thuật toán sắp xếp để sắp xếp các hậu tố, nếu sử dụng thuật toán quick sort thì đpt sắp xếp là O(n*logn). Tuy nhiên, quick sort là thuật sắp xếp so sánh, để so sánh 2 xâu cần đpt là O(n) => đpt của cả chương trình là O(n^2 * logn) => quá "Trâu bò" . Ý tưởng xây dựng suffix array được dựa trên ý tưởng thuật toán "Trâu bò" mà mình vừa nói. Chúng ta sẽ nghiên cứu để giảm đpt của ý tưởng trên xuống còn n*logn*logn. (còn giảm đến n*logn mình sẽ nói sau, phải từ từ thì mới nắm được cái CTDL khó chịu này)
******** Lại bàn về THỨ TỰ TỪ ĐIỂN
Cho 2 xâu X (độ dài N)và Y (độ dài M), x (độ dài n) là xâu con của X, y (độ dài cũng là n luôn) là xâu con của Y, giả sử rằng x xuất hiện tại vị trí k của X, và y cũng xuất hiện tại vị trí k của Y (k<N và k<M) và X[0..(k-1)] = Y[0..(k-1)] ( tức là k kí tự đầu tiên của X và Y trùng nhau tương ứng đôi một ).
Từ đó ta có tính chất sau:
+ nếu x < y thì X < Y
+ nếu x > y thì X > Y
** Chú ý rằng x,y có cùng độ dài, cùng xuất hiện tại vị trí k của xâu mẹ của chúng. Và X,Y giống nhau ở k kí tự đầu tiên.
Ví dụ: X = abcdefg x = def
Y = abcdeeg y = dee
Quá rõ ràng : k=3, vì X[0..2] = Y[0..2] = abc;
x < y (def < dee)
Do đó X < Y.
** Tính chất này quá dễ chứng minh, coi như mặc nhiên đúng nha :"3
- Nói thêm 1 tý : tính chất này ngó như nó có vẻ nhảm nhí đúng không nào, nhưng nếu áp dụng nó 1 cách tinh tế thì ta có thể giảm đpt của ý tưởng "Trâu bò" nêu trên.
*** Các bước xây dựng thuật toán:
*** Các bước xây dựng thuật toán:
- Đầu tiên chúng ta sắp xếp các hậu tố theo thứ tự tăng dần của kí tự đầu tiên của mỗi hậu tố bằng quicksort.
Do đó, các hậu tố có cùng kí tự đầu tiên sẽ có cùng số thứ tự.
Ví dụ cho dễ thấy nhé : cho T = banana
STT Hậu tố
0 1-anana , 3-ana , 5-a
1 0-banana
2 2-nana, 4-na
Cái này tốn n*logn nhé, vì so sánh mỗi 1 kí tự đầu tiên thôi mà :)
*** Bây giờ để ý nhé, 1 phần mấu chốt vấn đề là ở đây: xét 2 kí tự thuộc T lần lượt ở vị trí i , j . Nếu hậu tố i có STT < STT của hậu tố j thỳ T[i]<T[j]. Nói nôm na ra là STT của hậu tố i đại diện cho thứ tự của kí tự T[i] (kí tự đầu tiên của hậu tố i).
Ví dụ: hậu tố [ 0 - banana ] có STT là 1 (bảng trên),
tương tự hậu tố [ 2 - nana ] có STT là 2,
ta thấy STT của hậu tố 0 < STT của hậu tố 2 (1<2) ,
suy ra T[0]<T[2] (b<n).
Nhận xét này thoạt đầu thấy rất nhảm nhí, giống như đi đường vòng vậy, nhưng nó ẩn chứa nhiều mục đích bên trong lắm đấy. Chúng ta sẽ sử dụng nhận xét này để tiến hành bước tiếp theo.
- Tiếp đến, chúng ta sẽ sắp xếp các hậu tố theo thứ tự tăng dần của 2 kí tự đầu tiên.
Để so sánh thứ tự của 2 hậu tố theo 2 kí tự đầu tiên:
Thoạt tiên, ta so sánh STT của chúng ( STT đã được xây dựng ở bước đầu tiên), thực chất việc so sánh STT chính là so sánh kí tự đầu tiên. (dựa vào nhận xét nói trên). STT bé hơn thỳ thứ tự bé hơn.
Nếu STT bước trên = nhau, ta tiếp tục so sánh STT của hậu tố đứng sau chúng.
bạn cẩn thận chữ đứng sau nhé ( hậu tố (i+1) đứng sau hậu tố i ), ví dụ : T=banana, thì 5-a đứng sau 4-na.
thực chất việc này chính là so sánh kí tự thứ 2 của mỗi hậu tố, việc này chứng minh khá dễ dàng, kí tự thứ 2 của hậu tố i, chính là kí tự thứ 1 của hậu tố (i+1) vì vậy STT của hậu tố đứng sau đại diện cho thứ tự từ điển của kí tự thứ 2 của hậu tố đứng trước.
Sau khi sắp xếp, ta sẽ cập nhật lại STT mới cho các hậu tố, và STT này sẽ mang 1 ý nghĩa khác. (sẽ nói sau)
Rồi, bây giờ ta có bảng sau :
STT Hậu tố
0 5-a
1 1 - anana, 3 - ana
2 2-banana
3 2-nana, 4-na
bước này độ phức tạp n*logn luôn nha, so sánh 2 hậu tố coi như O(1).
OK, bây giờ ta có 1 nhận xét nữa , STT của mỗi hậu tố bây h sẽ đại diện cho thứ tự từ điển của 2 kí tự đầu tiên của mỗi hậu tố. Nói cách khác, STT bây giờ đại diện cho thứ tự từ điển của tiền tố độ dài 2 của mỗi hậu tố. ( Cái này các bạn lấy giấy ra ngẫm nghĩ sẽ thẩm thấu được ngay ).
Suy ra, STT của hậu tố (i+2) sẽ đại diện cho thứ tự của xâu con độ dài 2, xuất hiện tại vị trí 2 của hậu tố i. (bạn đọc tự chứng minh nha)
Các bạn chịu khó xem lại phần ******** Lại bàn về THỨ TỰ TỪ ĐIỂN mình bôi đỏ phía trên nhé. Vì sẽ dùng trong bước tiếp theo đấy :D
Trước tiên ta xét bài toán, so sánh 2 xâu kí tự X và Y có cùng độ dài là 4. Giả sử sử rằng ta có
px là thứ tự của X[0...1], py là thứ tự của Y[0..1], sx là thứ tự của X[2..3], sy là thứ tự của Y[2..3]
Từ tính chất mình nhắc lại ở trên : ta có thể suy ra các trường hợp sau:
- px < py => X < Y và ngược lại
- px = py và sx <sy => X < Y
hoặc px=py và sx>sy => X >Y.
=> độ phức tạp so sánh coi như là O(1)
- Từ nhận xét trên, ta không khó để nghĩ ra bước tiếp theo, sắp xếp các hậu tố theo thứ tự của 4 kí tự đầu tiên, bằng cách so sánh thứ tự tiền tố độ dài 2 và so sánh thứ tự xâu con độ dài 2, xuất hiện ở vị trí 2 của 2 hậu tố cần so sánh, nhờ vào STT của các hậu tố. Nên nhớ STT của hậu tố (i+2) sẽ đại diện cho thứ tự của xâu con độ dài 2, xuất hiện tại vị trí 2 của hậu tố i. (bạn đọc tự chứng minh nha)
- Bây giờ bạn đã có thể hình dung khá rõ ràng thuật toán của chúng ta, khi đã sắp xếp các hậu tố theo thứ tự của k kí tự đầu, thỳ ta có thể sắp xếp các hậu tố theo thứ tự của k*2 kí tự đầu. Lặp việc so sánh đến khi các hậu tố đều được so sánh theo tất cả các kí tự mà chúng có.
-Với xâu n kí tự, ta sắp xếp logn lần, mỗi lần n*logn => đpt tổng cộng là O(n*logn*logn)
- Nhánh cận : đến 1 bước sắp xếp nào đó, STT của tất cả các hậu tố khác nhau đôi một, ta có thể dừng quá trình lặp.
- OK, bây giờ làm sao để độ phức tạp giảm còn n*logn. Tư tưởng ý hệt như trên, cũng lặp lại quá trình sort logn lần, nhưng chúng ta sẽ sử dụng thuật toán sắp xếp đếm phân phối ( vì T chỉ gồm các kí tự chữ cái latin ) để giảm đpt sắp xếp mỗi lần xuống còn O(n).
- Thực nghiệm cho thấy đpt thuật toán trung bình chỉ lớn hơn O(n) đôi chút, xui lắm mới "nờ lốc nờ" thôi :)) anh em yên tâm mà xài.
Code dùng quicksort http://codeforces.com/blog/entry/4025
quá chi tiết <3
Trả lờiXóa