ტრაი და ავტოშევსება

საძიებო ველში აკრიფე „te“ და დასრულებამდე შემოგთავაზებს tea-ს, ted-ს და ten-ს. ტრაი სიტყვებს საერთო პრეფიქსებით ინახავს, ამიტომ ძებნა სიტყვის სიგრძე ღირს და არა ლექსიკონის ზომა.

საშუალო⏱ 10 წთ

←ეყრდნობა

5ხეები: ცნებები, თვისებები, შემოვლებიტრაი არის სათავიანი ხე, რომლის ყოველ წიბოზე ერთი ასოა.1ჰეშ-ცხრილები: set და mapტრაის წვეროს შვილებს ხშირად map-ში ვინახავთ, სადაც ასო შვილზე მიუთითებს.

გზას უხსნის→

11პრეფიქს-ფუნქცია და KMPპრეფიქს-ფუნქცია შაბლონის ტრაიში დაბრუნების ბმულებივით მუშაობს: შეუსაბამობისას გადადი უგრძეს საზღვარზე.+სუფიქსური მასივისუფიქსური მასივი ყველა სუფიქსის ტრაის კომპაქტური შემცვლელია.

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

ისწავლე

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

01თითო ასო თითო წიბოზე

ტრაი (პრეფიქსული ხე) ისეთი ხეა, რომლის ყოველ წიბოს ერთი სიმბოლო აწერია, ამიტომ სათავიდან ყოველი გზა რაიმე პრეფიქსს კრებს. ერთნაირად დაწყებული სიტყვები გზის დასაწყისს იზიარებენ: tea, ted და ten სამივე t → e-ზე გადის და მხოლოდ ბოლო ასოზე იყოფა.

სათავე ცარიელია. ყოველი წვერო ინახავს შვილებს, თითოს ყოველი შესაძლო შემდეგი ასოსთვის (ინგლისური პატარა ასოებისთვის 26-ელემენტიანი მასივი ან map), და დროშას end, რომელიც ნიშნავს: „აქ მთელი სიტყვა მთავრდება“. დროშა აუცილებელია: in და inn ერთ გზას, i → n → n-ს, იზიარებენ და მხოლოდ დროშები გვეუბნება, რომ in და inn სიტყვებია, i კი არა.

აგება O(ყველა სიტყვის ჯამური სიგრძე) ღირს: ყოველი ჩასმა ასო-ასო ჩადის ქვემოთ და ახალ წვეროს მხოლოდ იქ ქმნის, სადაც გზა ჯერ არ არსებობს.

02ჩასმა და ძებნა

ორივე ოპერაცია სათავიდან იწყება და თითო ნაბიჯზე ერთ სიმბოლოს ამუშავებს:

insert(word): ყოველი ასოსთვის მივყვებით შვილს, თუ არსებობს, თუ არა და ვქმნით; ბოლოს ვაყენებთ end = true.
search(word): მივყვებით შვილებს; თუ რომელიმე ასოს შვილი არ აქვს, სიტყვა არ არსებობს და მაშინვე ვჩერდებით. თუ სიტყვის ბოლომდე მივედით, პასუხი ამ წვეროს end დროშაა.

ე.ი. სამი შედეგია შესაძლებელი. ten აღწევს end-ით მონიშნულ წვეროს: სიტყვაა. te აღწევს წვეროს, რომელიც მონიშნული არ არის: მხოლოდ პრეფიქსია. tx პირველივე არარსებულ შვილზე ჩერდება.

L სიგრძის სიტყვისთვის ღირებულება O(L)-ია, რამდენი სიტყვაც არ უნდა ინახებოდეს. ჰეშ-სიმრავლეც სწრაფად ამოწმებს წევრობას, მაგრამ პრეფიქსებზე კითხვებს ვერ პასუხობს, და სწორედ აქ ამართლებს ტრაი თავის მეხსიერებას.

03ლექსიკონი, ავტოშევსება, პრეფიქსების დათვლა

ყოველ წვეროში კიდევ ერთი რიცხვი შევინახოთ: cnt, რამდენი ჩასმული სიტყვა გადის მასზე (ჩასმისას ქვემოთ ჩასვლის დროს ვზრდით). ახლა ტრაი სამ კლასიკურ კითხვას პასუხობს:

ლექსიკონი: სიტყვაა თუ არა? ჩავიდეთ და შევამოწმოთ end: O(L).
პრეფიქსების დათვლა: რამდენი სიტყვა იწყება p-თი? ჩავიდეთ p-ის წვერომდე და წავიკითხოთ cnt: O(|p|). te-სთვის პასუხია 3.
ავტოშევსება: რომელი სიტყვები იწყება p-თი? ჩავიდეთ p-ის წვერომდე, მის ქვემოთ გავუშვათ DFS და გამოვიტანოთ end-ით მონიშნული ყოველი წვერო. შვილებს ანბანური რიგით თუ შემოვივლით, შეთავაზებები დალაგებული გამოვა: tea, ted, ten.

რეალური ავტოშევსება პოპულარობის ქულასაც ინახავს და მხოლოდ რამდენიმე საუკეთესოს აბრუნებს, მაგრამ ჩონჩხი იგივეა: ჯერ ჩასვლა, მერე დათვალიერება. ტრაი გამოიყენება მართლწერის შემმოწმებლებში, IP მარშრუტიზაციის ცხრილებში (უგრძესი პრეფიქსის დამთხვევა) და, ასოების ნაცვლად ბიტებით, ცნობილ ამოცანაში „ორი რიცხვის მაქსიმალური XOR“.

პატარა ნიშნები: რამდენი სიტყვა გადის თითოეულ წვეროზე.

04მეხსიერება და როდის გამოვიყენოთ ტრაი

ტრაის ფასი მეხსიერებაა. თუ ყოველ წვეროში 26 მიმთითებლის მასივია, მილიონი მოკლე სიტყვის ლექსიკონს ათეულობით მილიონი მიმთითებელი დასჭირდება, რომელთა უმეტესობა NULL-ია. გავრცელებული გამოსავალი:

შვილები ფიქსირებული მასივის ნაცვლად map-ში ან პატარა დალაგებულ ვექტორში შევინახოთ: ნაკლები მეხსიერება, ოდნავ ნელი ნაბიჯები;
ყველა წვერო ერთ დიდ მასივში შევინახოთ და მიმთითებლების ნაცვლად მთელი ინდექსები გამოვიყენოთ, int nxt[MAXN][26], სპორტული პროგრამირების ჩვეული ვარიანტი;
ერთშვილიანი ჯაჭვები ერთ წიბოდ შევკუმშოთ, რომელსაც მთელი სტრიქონი აწერია (radix ხე).

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

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

L სიგრძის სიტყვის ჩასმა / ძებნაO(L)

p პრეფიქსიანი სიტყვების დათვლაO(|p|)

p პრეფიქსის ავტოშევსებაO(|p| + subtree)

მეხსიერება (შვილების მასივით)O(total length · Σ)

დაიმახსოვრე

ტრაი საერთო პრეფიქსებს იზიარებს: თითო წიბო თითო სიმბოლოზე და სიტყვის დასასრულის დროშა ყოველ წვეროში.
ჩასმა, ძებნა და პრეფიქსების დათვლა სტრიქონის სიგრძის პროპორციულია და არ არის დამოკიდებული შენახული სიტყვების რაოდენობაზე.
ავტოშევსება = ჩადი პრეფიქსის წვერომდე, მერე მის ქვემოთ DFS-ით შეაგროვე სიტყვის დასასრულის ყველა წვერო.

ითამაშე

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

👀 რას უყურო: უყურე პატარა მთვლელებს: თითოეული იმ სიტყვების რაოდენობაა, რომლებიც ამ წვეროზე გადის. ბოლოს ტრაი შენ მიერ არჩეულ პრეფიქსს ავტოშევსებით ასრულებს.

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

პრეფიქსული ხე (ტრაი)

სიტყვის დასასრულიპატარა რიცხვი = რამდენი სიტყვა გადის ამ წვეროზე

ტრაი სტრიქონებს სიმბოლო-სიმბოლო ინახავს: საერთო პრეფიქსებს საერთო წვეროები აქვთ. ვსვამთ: tea, ted, ten, to, in, inn.

ფსევდოკოდი

 1 root is empty; each edge is labelled by a character 2 insert(word): for each char, 3   follow the child if it exists, 4   else create a new child node 5   mark the final node as end-of-word 6 search(word): walk the same way, 7   hit only if the path exists AND the last node is end-of-word 8 // applications: dictionary, autocomplete, prefix count 9 autocomplete(p): walk to the node of prefix p10   DFS below it, collect every end-of-word node11 countPrefix(p) = cnt[node of p]   // O(|p|)

1 / 1

შეამოწმე

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

№1

ტრაიში არის tea, ted, ten, to, in, inn. რას დააბრუნებს search("te")?

№2

რამდენი წვერო აქვს tea, ted, ten, to, in, inn სიტყვების ტრაის, სათავის გარეშე?

№3

რომელ კითხვას პასუხობს ტრაი სწრაფად, ჰეშ-სიმრავლე კი ვერა?

ივარჯიშე

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

LeetCodeLongest Common Prefix დამწყები↗LeetCodeImplement Trie (Prefix Tree) საშუალო↗LeetCodeSearch Suggestions System საშუალო↗LeetCodeReplace Words საშუალო↗LeetCodeMaximum XOR of Two Numbers in an Array საშუალო↗