>> Kevin Schmid: Kelkfoje, kiam la konstruado de programon, eble vi volas uzi unu
datumstrukturo konata kiel vortaro.
A vortaro mapoj klavoj, kiuj estas kutime kordoj, al valoroj, ints,
signoj, puntero por iu celo, kion ajn ni volas.
Estas nur kiel ordinaraj vortaroj ke mapo vortojn per difinoj.
>> Vortaroj provizi nin per la kapablon konservi informojn
asociita kun iu kaj rigardi ĝin poste.
Do kiel fari ni reale efektivigi vortaro en, ekzemple, C kodo kiun ni povas
uzi en unu el niaj programoj?
Nu, tie estas multaj vojoj kiujn ni povus efektivigi vortaro.
>> Por unu, ni povus uzi tabelo, ke ni dinamike re-grandeco aŭ ni povus uzi
ligillisto, hash tablo aŭ duuma arbo.
Sed kion ajn ni elektos, ni devus ke vi memoru la efikeco kaj
agado de la efektivigo.
Ni devas pensi pri la algoritmo uzita enmeti kaj rigardi supren erojn en
nia datumstrukturo.
>> Por nun, ni supozu, ke ni volas uzi kordoj kiel ŝlosilojn.
Ni parolu pri unu eblo, datumstrukturo nomata trie.
Do jen vida reprezento de trie.
>> Kiel la bildo sugestas, a trie estas arbo datumstrukturo kun
nodoj kunligitaj.
Ni vidas, ke tie estas klare radiko nodo kun kelkaj ligiloj plilongigante
aliaj nodoj.
Sed kion signifas ĉiu nodo konsistos?
Se ni supozas ke ni stokante ŝlosilojn kun nur alfabetaj signoj, kaj
ni ne zorgas pri majuskloj, jen difino de nodo ke
sufiĉos.
>> Objekto kies tipo estas struct nodo havas du partojn
vokis datumoj kaj infanoj.
Ni forlasis la datumoj parto kiel komento esti anstataŭita de komponanto
deklaro kiam struct nodo estas korpigis en C-programo.
La datumoj parto de nodo povus esti Bulea valoro por indiki ĉu aŭ
ne la nodo reprezentas la finaĵon de vortaro ŝlosilo aŭ povus esti
kordo reprezentanta la difino de iu vorto en la vortaro.
>> Ni uzu smiley vizaĝon indiki Kiam datumoj estas ĉeestanta en nodo.
Estas 26 eroj en nia infanoj tabelo, unu indekso
po alfabeta karaktero.
Ni vidos la signifon de tiu baldaŭ.
>> Ni ricevas pli proksima rigardo de la radika nodo en la diagramo, kiu ne havas datumoj
asociita kun ĝi, kiel indikita de la foresto de la ridetanta vizaĝo en la
datumoj porcion.
La sagoj etendanta de la partoj de la idoj tabelo reprezentas ne-nodon
montriloj al aliaj nodoj.
Ekzemple, la sago etendanta de la dua elemento de infanoj
reprezentas la litero B en vortaro ŝlosilo.
Kaj en la pli granda diagramo ni marko ĝin per B.
>> Notu ke en la granda figuro, kiam ni desegni montrilon al alia vertico, ĝi
Ne gravas, kie la Arrowhead renkontas tiu alia nodo.
Nia specimeno vortaro trie enhavas du vortoj, kiuj kaj zoom.
Ni marŝas tra ekzemplo de suprenrigardinte datumoj por ŝlosilo.
>> Supozi ni volis rigardi la responda valoro por la klavo bano.
Ni komencu nian rigardon supren ĉe la radika nodo.
Tiam ni prenos la unua litero de nia klavo, B, kaj trovi la respondajn
spot en niaj infanoj tabelo.
Rimarku, ke estas precize 26 makuloj en la tabelo, unu por ĉiu litero de
la alfabeto.
Kaj ni havos la makuloj reprezentas la literojn de la alfabeto en ordo.
>> Ni rigardu la duan indekso tiam, indekso unu pro B. En ĝenerala, se ni
havi iu alfabeta karaktero C ni povis determini la responda loko
en la infanoj tabelo uzante kalkulo kiel ĉi tio.
Ni povus esti uzata pli grandan infanoj tabelo, se ni volas proponi rigardon supren de
ŝlosilojn kun ampleksa gamo de karakteroj, kiel en la tuta
ASCII-signaro.
>> En ĉi tiu kazo, la montrilo en niaj infanoj tabelo cxe
indekso oni ne estas nula.
Do ni daŭre serĉas ĝis la ŝlosilo bano.
Se ni iam renkontis nula montrilo ĉe la taŭgan lokon en la infanoj
tabelo dum ni trairis la nodoj, tiam ni devos diri ke ni
ne povis trovi ion ajn por tiu klavo.
>> Nu, ni prenu la duan leteron de nia ŝlosilo, A, kaj daŭrigi jenaj
montriloj en tiu vojo ĝis ni atingi la finon de nia ŝlosilo.
Se ni atingas la finon de la ŝlosilo sen bati neniu mortinto pintojn, nula montriloj,
kiel estas la kazo tie, do ni nur devas kontroli alia afero.
Ĉu ĉi tiu ŝlosilo reale en la vortaro?
>> Se jes, ni devus trovi valoron, puto smiley vizaĝon piktogramon en nia diagramo kie
la vorto finiĝas.
Se estas io alia stokita per la datumojn, tiam ni povas reveni al ĝi.
Ekzemple, la ŝlosilo bestoĝardeno ne estas en la vortaro, eĉ se ni povus havi
atingis la finon de ĉi tiu ŝlosilo sen iam ajn bati nula montrilon, dum ni
persisti tra la trie.
>> Se ni provis serĉi la ŝlosilon bano, la dua ĝis lasta nodo tabelo indekso,
responda al la literon H, estus tenis nula montrilo.
Do bano ne estas en la vortaro.
Kaj tiel oni trie estas unika en kiuj la ŝlosilojn neniam estas eksplicite stokitaj en
la datumstrukturo.
Do kiel fari ni enmetas ion enen trie?
>> Ni enmeti la ŝlosilon zoo en nian trie.
Memoru ke smiley vizagxon cxe nodon povus respondi en kodon por simpla
Bulea valoro por indiki ke bestoĝardeno estas en la vortaro aŭ ĝi povis
respondas al pli da informoj, ke ni volas asocii kun la klavo zoo,
same kiel la difino de la vorto aŭ ion alian.
En iuj manieroj, la procezo por enmeti io en trie estas simila al
suprenrigardinte io en trie.
>> Ni komencu per la nodo radiko denove, jenaj pointers responda al
la leterojn de niaj ŝlosilo.
Bonŝance, ni povis sekvi pointers tuta vojo ĝis ni atingis
la finon de la ŝlosilo.
Ekde bestoĝardeno estas prefikso de la vorto zomo, kiu estas membro de la
vortaro, oni ne bezonas atribui al si novajn nodojn.
>> Ni povas modifi la nodo por indiki ke la vojo de la karakteroj kondukante al
ĝi reprezentas klavo en nia vortaro.
Nun, ni provu la enmeto de la ŝlosilo bano en la trie.
Ni komencos je la radika nodo kaj sekvi pointers denove.
Sed en ĉi tiu situacio, ni trafis morta fini antaux ni povis atingi la
fino de la ŝlosilo.
Nun, ni bezonos por atribui iun novan nodojn bezonos atribui unu nova
nodo por ĉiu restanta letero de nia ŝlosilo.
>> En ĉi tiu kazo, ni nur bezonas atribui unu nova nodo.
Tiam ni bezonos por fari la H indekso referenci tiun ĉi novan nodon.
Denove, ni povas modifi la nodo indikas ke la vojo de la karakteroj
kondukante al ĝi reprezentas klavo en nia vortaro.
Ni rezoni pri la asimptota komplekseco de niaj proceduroj por tiuj
du operacioj.
>> Ni rimarkas, ke en ambaŭ kazoj la nombro de paŝas nia algoritmo prenis estis
proporcie kun la nombro de literojn en la ŝlosilvorto.
Tio estas prava.
Kiam vi volas rigardi supren vorto en trie, vi nur devas persisti tra
la literojn unu post alia, ĝis vi ĉu atingi la finon de la vorto aŭ
batis senelirejo en la trie.
>> Kaj kiam vi volas enmeti ŝlosilon valoro paro en trie uzante la
proceduro ni diskutis, la plej malbona kazo havos vi atribuante nova nodo
por ĉiu litero.
Kaj ni vidos supozi ke atribuo Estas konstanta tempo operacio.
Do, se ni supozas ke la ŝlosila longo estas barita per fiksita konstanto, ambaŭ
inserción kaj rigardi supren estas konstanta tempo operacioj por trie.
>> Se ni ne faras ĉi supozo ke la ŝlosilo longeco estas barita per fiksa
konstanta, do Insertion kaj rigardi supren, en la plej malbona kazo, estas lineara en la
longeco de la ŝlosilo.
Rimarku ke la nombro de eroj stokitaj en la trie ne tuŝas la rigardon supren
aŭ inserción tempo.
Ĝi estas nur efikis per la longeco de la ŝlosilo.
>> Kontraste, aldonante Aktualaĵoj al, ni diru, kradon tablo inklinas fari
estonteco rigardi supren malrapida.
Dum tio povas soni apelacianta al la komenco, ni devas memori tion, ke oni
favoraj asimptota komplekseco ne signifas, ke en la praktiko la datumoj
strukturo estas bezone preter riproĉo.
Ni devas ankaŭ konsideri ke stoki vorto en trie ni bezonas, en la plej malbona
kazo, nombro de nodoj proporcia al la longeco de la vorto mem.
>> Tries emas uzi multe da spaco.
Tio estas en kontrasto al hash tablo kie oni nur bezonas unu nova nodo
stoki iuj ŝlosilaj valoro paron.
Nun, denove en teorio, granda spaco konsumado ne ŝajnas kiel granda
trakti, precipe pro tio ke la moderna komputiloj havas gigabajtoj kaj
gigabajtoj da memoro.
Sed tio rezultas ke ni ankoraŭ havas maltrankviligi memoro uzado kaj
organizon por la bono de agado, ekde modernaj komputiloj
havi mekanismojn en loko sub la kapuĉo rapidigi memoro aliron.
>> Sed tiuj ĉi mekanismoj funkcias plej bone kiam memoro aliroj estas faritaj en kompakta
regionoj aŭ zonoj.
Kaj la nodoj de trie povus loĝi ie ajn en tiu amaso.
Sed jen estas la komerco maldungitaj ke ni devas konsideri.
>> Memoru ke, elektinte datumoj strukturon por certa tasko, ni
devas pensi pri kio specoj de operacioj la datumstrukturo bezonu
apogon kaj kiom la agado de ĉiu el tiuj
operacioj aferojn al ni.
Ĉi tiuj operacioj povas eĉ etendi preter nur
bazaj rigardon supren kaj inserción.
Supozi ni volis efektivigi ian de auto-kompletaj funkcioj, multe
kiel Google serĉilon faras.
Tio estas, revenu ĉiuj klavoj kaj potenciale valoroj kiujn
havi donita prefikson.
>> A trie estas unike utilan por tiu ĉi operacio.
Ĝi estas simpla al persisti tra la trie por ĉiu karaktero de
la prefikso.
Ĝuste kiel aspektas supren operacio, ni povis sekvi pointers
karaktero de karaktero.
Tiam, kiam ni alvenos al la fino de la prefikso, ni povus persisti tra la
cetera parto de la datumstrukturo ĉar neniu el la klavoj trans
ĉi punkton havas la prefikson.
>> Ĝi estas ankaŭ facila por akiri ĉi tiun liston en alfabeta ordo ekde la
elementoj de la infanoj tabelo estas ordigita alfabete.
Do espereble vi devos konsideri almozo provas provi.
Mi estas Kevin Schmid, kaj ĉi tiu estas CS50.
>> Ha, ĉi tiu estas la komenco de la dekadenco.
Mi bedaŭras.
Pardonon.
>> Frapu kvar.
Mi estas ekstere.
Pardonon.
Pardonu por fari la persono kiu havas redakti ĉi freneziĝos.
>> Pardonon.
Pardonon.
>> SPEAKER 1: Bonege.
Tio estis vere bone farita.