Prefiksipuu sammhaaval

Puus on kuusteist sõna, igas sõlmes üks täht. Ühesuguse algusega sõnad jagavad sama teed: car, card ja cart läbivad kõik sõlmed c, a, r. Topeltring tähistab sõlme, kus sõna lõpeb. Sisesta sõna, vali toiming ja vaata seda sammhaaval.

Näidisarvutus — Prefiksipuu sammhaaval

Prefiksipuu, sõna “car” otsing: loetud tähti	3, salvestatud
Paisktabel ilma kollisioonideta: loetud tähti	6
Algusega “car” sõnad	6: car, card, care, careful, cargo, cart
Paisktabel: loetud sõnu (kõik sõnad)	16
Sõna “car” lisamisel lisandub	0 sõlme: prefiksipuule 0 baiti, loendile 0
Prefiksipuu sõlmi, iga eri prefiksi kohta üks	30 sõlme 70 tähe kohta (57,1% ühist)
Tavaline loend: tähed ja 9 baiti sõna kohta	214
18-baidiste sõlmedega prefiksipuu koos juurega	558

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Prefiksipuu sammhaaval

Prefiksipuu ehk trie salvestab sõnade hulga puuna, kus igale eri prefiksile vastab üks sõlm. Juur tähistab tühja prefiksit ja iga serv kannab üht tähte. Teel juurest sõlmeni saadaksegi selle sõlme prefiks. Sõlm on märgitud, kui tema prefiks on terviklik salvestatud sõna. Ühesuguse algusega sõnad jagavad ühisele algusele vastavat teed. Otsing järgib sõna tähti juurest alates; prefiksiotsing jõuab prefiksi sõlmeni ja leiab kõik märgitud sõlmed selle all. Edward Fredkin andis sellele andmestruktuurile nime 1960. aastal, võttes selle sõnast retrieval, ning mõtles seda hääldada nagu inglise sõna tree.

Mida iga sümbol tähendab

W: sõnade arv loendis
L: tähtede arv kõigis sõnades kokku
N: sõlmede arv ilma juureta, iga eri prefiksi kohta üks

Eeldab: Kasutatakse väiketähti a kuni z, iga täht võtab ühe baidi ja viidad on 64-bitised. Kummagi andmestruktuuri puhul ei arvestata joondustäidet ega mäluhalduri lisakulu. Kahendotsingul loetakse iga võrreldud tähepaar ning võrdlus peatub esimese erineva paari juures. Sõna lõppu jõudmine lisakulu ei tekita. Paisktabelis pole ühtegi kollisiooni: see on tema jaoks parim juht. 18-baidise sõlme alamsõlmed on tähestikulises järjekorras, nii et nende läbivaatus peatub kohe, kui otsitavast tähest möödutakse.

Kahendotsing loeb tähti c, a, r neli korda, prefiksipuu ühe korra 🖖

Vajuta Otsi car. Prefiksipuus läbitakse igal sammul üks täht ning jõutakse sõnaks märgitud sõlmeni car: loetakse 3 tähte. Kahendotsing kontrollib samas 16 sõnaga järjestatud loendis sõnu catch, careful, card ja car. Kõik algavad tähtedega ca, mistõttu tuleb iga võrdluse käigus lugeda 3 tähte, enne kui saab otsustada, kummas suunas jätkata: kokku 12. Paisktabelis loetakse 3 tähte asukoha arvutamiseks ja veel 3 sealt leitud sõna kontrollimiseks, kokku 6. Kõigi 16 salvestatud sõna otsimiseks loetakse prefiksipuus 70 tähte, paisktabelis 140 ja kahendotsingul 169. Ühised algused säästavad prefiksipuus sõlmi, kuid muudavad kahendotsingu võrdlused pikaks. Kui salvestada kõik 17 576 kolmetähelist sõnet aaa-st zzz-ni, tuleb kahendotsingul ühe leidmiseks lugeda keskmiselt 26,4 tähte; prefiksipuus piisab endiselt 3 tähest.

Ka järjestatud loend sobib sõnade lõpetamiseks. Paisktabel peab lugema iga sõna 🖖

Vajuta Algusega car sõnad. Prefiksipuus läbitakse c, a, r ja seejärel külastatakse sõlme car all olevat 8 sõlme. Kokku on neid 11 ning 6 sõlmes lõpeb sõna. Sõnadeni dog, plan ja teisteni ei jõutagi. Järjestatud loendis saab samuti piirduda vajalike sõnadega, sest kõik car-algulised sõnad paiknevad kõrvuti. Kahendotsing leiab neist esimese 5 sõna kontrollimisega. Sealt edasi järjest lugedes leitakse kõik 6 ning peatutakse sõnal cat, mis esimesena enam ei sobi: kokku loetakse 12 sõna. Paisktabel paigutab sõnad car, card ja cargo üksteisest sõltumatutesse kohtadesse. Seetõttu tuleb lugeda kõiki 16 sõna ja igaühe algust kontrollida. Sõnade lisamisel on prefiksipuul järjestatud loendi ees selge eelis. Vajuta Lisa carpet: prefiksipuusse lisandub 3 sõlme ja midagi ei nihutata. Järjestatud loendis tuleb ruumi tegemiseks nihutada 11 sõna viidad ühe koha võrra edasi.

Kuigi 70 tähest on 40 ühised, on prefiksipuu ikka loendist 2,6 korda suurem 🖖

16 sõnas on 70 tähte. Prefiksipuus mahuvad need 30 sõlme, sest car, card, care ja teised jagavad sõlmi c, a, r. Sõlm vajab aga ruumi ka muuks kui täheks. Säästlikus variandis on igas sõlmes bait tähe jaoks, bait sõna lõpumärgi jaoks ning kaks 8-baidist viita: üks esimesele alamsõlmele ja teine järgmisele sama vanemaga sõlmele. See teeb 18 baiti sõlme kohta ning koos juurega kulub 31 sõlmele 558 baiti. Tavalises loendis võtab iga täht ühe baidi, lisaks kulub iga sõna kohta lõpumärgi bait ja 8-baidine viit: kokku 214. Kui anda igale sõlmele viit tähestiku iga tähe jaoks, nii et igal sammul piisab ühest massiiviindeksist, võtab prefiksipuu 6 479 baiti ehk 30 korda rohkem kui loend. Siin on sõnad kõige rohkem 14 tähe pikkused. Selliste sõnade puhul kulutab uue sõna lisamine prefiksipuusse vähem mälu vaid siis, kui ühtegi sõlme ei lisandu, näiteks plan puusse, kus on juba planet, või kui lisandub 1 sõlm ja sõnas on vähemalt 10 tähte. Säästlik sõlm nõuab ka rohkem otsinguaega: iga tähe leidmiseks tuleb sama vanema alamsõlmed järjest läbi vaadata. Sõna doorbell leidmiseks kulub siis 10 võrdlust, 1 võrra rohkem kui kahendotsingul.

Ülesanne täielikult lahendatud

Kui palju ühiseid algusi on vaja, et prefiksipuu võtaks vähem ruumi? 4 sammu
Vajuta Pikad sõnad: 85 tähte mahuvad 21 sõlme ja kolmveerand tähtedest on ühised, kuid 18-baidiste sõlmedega prefiksipuu võtab ikka 396 baiti loendi 157 vastu. Kui loendi kõik sõnad on k tähe pikkused, saab prefiksipuu suurima eelise siis, kui loendis on kõik võimalikud sellised sõnad. Milline on vähim k, mille korral võtab prefiksipuu siin kasutatud baidiarvestuse järgi vähem ruumi kui tavaline loend?

Ava see ülesanne tööriistas
1. Siin on 21 sõlme ja juur: 22 × 18 = 396 baiti. Loendis on 85 tähte ning iga 8 sõna kohta lõpumärgi bait ja 8-baidine viit: 85 + 9 × 8 = 157.
  
  $22 \times 18 = 396, 85 + 9 \times 8 = 157$
2. Kõiki k-tähelisi sõnesid on 26^k, igaühes k tähte. Seega võtab loend (k + 9) × 26^k baiti.
  
  $list = (k + 9) \cdot 2 6^{k}$
3. Prefiksipuus on vaja sõlme iga 1 kuni k tähe pikkuse sõne jaoks: 26 + 26² + … + 26^k. See summa on pisut väiksem kui 26/25 × 26^k. Koos juurega ja 18-ga korrutades võtab prefiksipuu veidi alla 18,72 × 26^k baidi.
  
  $N = 26 + 2 6^{2} + \dots + 2 6^{k} = \frac{26}{25} (2 6^{k} - 1), 18 (N + 1) < 18.72 \cdot 2 6^{k}$
4. Loend võtab seega rohkem ruumi, kui k + 9 ületab 18,72. Esimest korda juhtub see väärtusel k = 10. Kui k = 9, on prefiksipuu loendist 4,0% suurem; kui k = 10, on see 1,5% väiksem.
  
  $k + 9 > 18.72 ⟺ k \geq 10 : \frac{trie}{list} = 1.040 (k = 9), 0.985 (k = 10)$
Vastus

10 tähte, kui loendis on kõik 26¹⁰ võimalikku sõnet ehk umbes 1,4 × 10¹⁴ sõna. 209-baidiste sõlmede korral peab sama arvutuse järgi k + 9 ületama ligikaudu 217; selleks peavad sõnad olema 209 tähe pikkused.

$k = 10, 2 6^{10} \approx 1.4 \times 1 0^{14} words$

Õpitee

Mida andmestruktuur võimaldab odavalt teha

Allikad (3)

The name, its origin in "retrieval", and Fredkin's intended pronunciation, quoted in the definition: Paul E. Black, "trie", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., NIST, entry modified 12 February 2019.
The paper that named the structure: Edward Fredkin, "Trie memory," Communications of the ACM 3(9), September 1960, pp. 490–499.
The earlier description of searching on letter-by-letter keys: René de la Briandais, "File searching using variable length keys," Papers presented at the Western Joint Computer Conference, San Francisco, 3–5 March 1959, pp. 295–298.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.