სუფიქსური მასივი

ერთხელ დაალაგე ტექსტის ყველა სუფიქსი და ყოველი შემდგომი კითხვა „გვხვდება თუ არა ეს შაბლონი და რამდენჯერ?“ ორობით ძებნად იქცევა. სუფიქსური მასივები დგას სრულტექსტოვანი ინდექსების, გენომის ინსტრუმენტებისა და მონაცემთა კომპრესორების უკან.

მოწინავე⏱ 12 წთ

←ეყრდნობა

2შერწყმით სორტირება: დაყავი და იბატონესუფიქსები პრეფიქსის სიგრძის გაორმაგებით ლაგდება: არსებითად ეს O(n log n) სორტირების ამოცანაა.2დათვლითი სორტირებარანგების წყვილების დათვლითი სორტირება გაორმაგების ყოველ რაუნდს წრფივს ტოვებს.5ტრაი და ავტოშევსებასუფიქსური მასივი ყველა სუფიქსის ტრაის კომპაქტური შემცვლელია.

გზას უხსნის→

აქ გზამკვლევი სრულდება. გადახედე, რა გზა გაიარე.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01დალაგებული სუფიქსები, შენახული რიცხვებად

n სიგრძის სტრიქონს n სუფიქსი აქვს. სუფიქსური მასივი SA მათ საწყის ინდექსებს სუფიქსების ლექსიკოგრაფიული რიგით ჩამოთვლის. banana-სთვის:

SA = [5, 3, 1, 0, 4, 2], ანუ a < ana < anana < banana < na < nana.

თავად სუფიქსებს არასოდეს ვინახავთ, მხოლოდ n მთელ რიცხვს, ამიტომ მეხსიერება O(n)-ია.

მთავარი თვისება: P შაბლონით დაწყებული ყველა სუფიქსი დალაგებულ რიგში ერთმანეთის გვერდით დგას. მათგან პირველი და ბოლო ორი ორობითი ძებნით ვიპოვოთ, თითო ნაბიჯზე მაქსიმუმ |P| სიმბოლოს შედარებით. ეს O(m log n)-ია თითო მოთხოვნაზე, ბლოკის ზომა კი დამთხვევების რაოდენობაა.

02სწრაფი აგება: პრეფიქსების გაორმაგება

სუფიქსების ჩვეულებრივი სტრიქონული შედარებით დალაგება უარეს შემთხვევაში O(n² log n) ღირს. სტანდარტული ხერხი ალაგებს ჯერ პირველი 1, შემდეგ 2, შემდეგ 4, 8, … სიმბოლოს მიხედვით.

k-ე რაუნდის შემდეგ ყოველ პოზიციას აქვს რანგი: თუ პირველი k სიმბოლო ტოლია, რანგიც ტოლია. შემდეგ რაუნდში i სუფიქსის პირველ 2k სიმბოლოს აღწერს წყვილი (rank[i], rank[i + k]). პატარა რიცხვების წყვილების დალაგება იაფია და სტრიქონების შედარება საერთოდ არ გვჭირდება.

log n რაუნდის შემდეგ ყველა რანგი განსხვავებულია და მზად ვართ. ჩვეულებრივი სორტირებით ეს O(n log² n)-ია, წყვილებზე თანრიგობრივი სორტირებით კი O(n log n). ნახაზზე banana 4-სიმბოლოიანი რაუნდის შემდეგ სრულად დალაგებულია.

03ძებნის მიღმა: LCP მასივი

SA-სთან ერთად ჩვეულებრივ აგებენ LCP მასივს: lcp[i] არის SA[i − 1] და SA[i] სუფიქსების უგრძესი საერთო პრეფიქსის სიგრძე. კასაის ალგორითმი მას O(n)-ში ითვლის.

SA-თი და lcp-თი შეგიძლია რთულად მოჩვენებით კითხვებს უპასუხო:

განსხვავებული ქვესტრიქონების რაოდენობა: n(n+1)/2 − Σ lcp[i]
უგრძესი განმეორებადი ქვესტრიქონი: lcp-ის მაქსიმუმი
ორი სტრიქონის უგრძესი საერთო ქვესტრიქონი: ავაგოთ SA სტრიქონზე A + "#" + B

თუ ერთი შაბლონის ერთჯერადი ძებნა გჭირდება, KMP ან Z უფრო მარტივია. სუფიქსური მასივი მაშინ ამართლებს, როცა ერთ ტექსტზე ბევრი მოთხოვნაა, ან კითხვა ყველა ქვესტრიქონს ერთად ეხება.

ფასი ერთი შეხედვით

აგება (გაორმაგება + თანრიგობრივი სორტირება)O(n log n)

ერთი შაბლონის ძებნაO(m log n)

LCP მასივი (კასაი)O(n)

მეხსიერებაO(n)

დაიმახსოვრე

სუფიქსური მასივი სუფიქსების საწყისი პოზიციების დალაგებული სიაა, ამიტომ მხოლოდ O(n) მთელ რიცხვს იკავებს.
შაბლონის ყველა დამთხვევა SA-ში ერთ უწყვეტ ბლოკს ქმნის, რომელსაც ორობითი ძებნით O(m log n)-ში ვპოულობთ.
პრეფიქსების გაორმაგება ალაგებს 1, 2, 4, … სიმბოლოთი, რანგების წყვილების გამოყენებით, და აგებას O(n log n)-ს ხდის.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: ბოლოს შენიშნე, რომ შესაბამისი სუფიქსები ერთ ბლოკს ქმნის: ორობით ძებნას მხოლოდ მისი კიდეების პოვნა სჭირდება.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

სუფიქსური მასივი: "banana" · სუფიქსები (დაულაგებელი)

0banana

1anana

2nana

3ana

4na

სუფიქსური მასივი სტრიქონის ყველა სუფიქსის დალაგებული რიგია, შენახული საწყისი ინდექსებით. ძლიერია მრავალმოთხოვნიანი ქვესტრიქონის ძებნისთვის.

ფსევდოკოდი

 1 list all suffixes with their start indices 2 sort the suffixes lexicographically → SA = their indices 3 search pattern P: binary search for the contiguous SA range starting with P 4 // SA stores only indices → O(n) memory

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

რა არის "abab"-ის სუფიქსური მასივი?

№2

"banana"-ს SA-ში "na"-თი დაწყებული სუფიქსები 4 და 5 სტრიქონებს იკავებს. რამდენჯერ გვხვდება "na"?

№3

პრეფიქსების გაორმაგებისას როგორ ვადარებთ ორი სუფიქსის პირველ 2k სიმბოლოს?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

CSESFinding Patterns საშუალო↗CSESDistinct Substrings საშუალო↗CSESRepeating Substring მოწინავე↗LeetCodeLongest Duplicate Substring მოწინავე↗