1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: De vegades, quan la construcció d'una
programa, és possible que vulgueu utilitzar un

3
00:00:10,890 --> 00:00:13,190
estructura de dades coneguda com un diccionari.

4
00:00:13,190 --> 00:00:17,960
A Mapes Diccionari tecles, que són
generalment cordes, als valors, enters,

5
00:00:17,960 --> 00:00:21,900
caràcters, un punter a un objecte,
el que vulguem.

6
00:00:21,900 --> 00:00:26,510
És igual que els diccionaris normals
Aquest mapa paraules a través de les definicions.

7
00:00:26,510 --> 00:00:29,440
>> Diccionaris ens donen la
capacitat d'emmagatzemar informació

8
00:00:29,440 --> 00:00:32,750
associat amb alguna cosa
i buscar més tard.

9
00:00:32,750 --> 00:00:36,620
Així que com podem posar en pràctica un
Diccionari en, per exemple, el codi C que podem

10
00:00:36,620 --> 00:00:38,460
utilitzar en un dels nostres programes?

11
00:00:38,460 --> 00:00:41,790
Bé, hi ha un munt de maneres en què
podríem implementar un diccionari.

12
00:00:41,790 --> 00:00:45,930
>> D'una banda, podríem utilitzar una matriu que
dinàmicament canviar la mida o podríem utilitzar un

13
00:00:45,930 --> 00:00:49,150
llista enllaçada, taula hash
o un arbre binari.

14
00:00:49,150 --> 00:00:52,250
Però qualsevol cosa que triem, hem
tenir en compte l'eficiència i

15
00:00:52,250 --> 00:00:54,300
el rendiment de l'aplicació.

16
00:00:54,300 --> 00:00:57,930
Hem de pensar en l'algoritme utilitzat
per inserir i cercar elements en

17
00:00:57,930 --> 00:00:59,120
la nostra estructura de dades.

18
00:00:59,120 --> 00:01:03,060
>> Per ara, anem a suposar que
vulgueu utilitzar cadenes com a claus.

19
00:01:03,060 --> 00:01:07,290
Anem a parlar d'una de les possibilitats,
una estructura de dades anomenada trie.

20
00:01:07,290 --> 00:01:11,210
Així que aquí hi ha una representació visual
d'un trie.

21
00:01:11,210 --> 00:01:14,590
>> A mesura que la imatge suggereix un trie
és una estructura de dades en arbre amb

22
00:01:14,590 --> 00:01:16,050
nodes enllaçats.

23
00:01:16,050 --> 00:01:19,420
Veiem que hi ha clarament una arrel
node amb alguns enllaços que s'estén a

24
00:01:19,420 --> 00:01:20,500
altres nodes.

25
00:01:20,500 --> 00:01:23,040
Però què significa cada node consisteix?

26
00:01:23,040 --> 00:01:26,700
Si assumim que estem emmagatzemant claus
amb només caràcters alfabètics i

27
00:01:26,700 --> 00:01:30,150
no ens preocupem per capitalització,
he aquí una definició d'un node que

28
00:01:30,150 --> 00:01:31,100
serà suficient.

29
00:01:31,100 --> 00:01:34,130
>> Un objecte el tipus és struct
node té dues parts

30
00:01:34,130 --> 00:01:35,740
trucada de dades i els nens.

31
00:01:35,740 --> 00:01:39,200
Hem deixat la part de dades com un comentari
per ser substituït per un component

32
00:01:39,200 --> 00:01:43,190
declaració al node d'estructura és
incorporat en un programa en C.

33
00:01:43,190 --> 00:01:47,040
La part de dades d'un node pot ser un
Valor booleà per indicar si

34
00:01:47,040 --> 00:01:51,160
no el node representa la finalització
d'una clau de diccionari o podria ser un

35
00:01:51,160 --> 00:01:54,240
cadena que representa la definició
d'una paraula al diccionari.

36
00:01:54,240 --> 00:01:58,870
>> Farem servir una cara somrient per indicar
quan les dades està present en un node.

37
00:01:58,870 --> 00:02:02,310
Hi ha 26 elements en el nostre
array nens, un índex

38
00:02:02,310 --> 00:02:03,690
per caràcter alfabètic.

39
00:02:03,690 --> 00:02:06,570
Veurem el significat
d'aquest aviat.

40
00:02:06,570 --> 00:02:10,759
>> Anem a prendre una mirada més propera del node arrel
en el nostre diagrama, que no disposa de dades

41
00:02:10,759 --> 00:02:14,740
associat amb ell, com s'indica per la
absència de la cara somrient al

42
00:02:14,740 --> 00:02:16,110
porció de dades.

43
00:02:16,110 --> 00:02:19,910
Les fletxes que s'estenen des de les parts de
els fills de la matriu representen lliure de nodes

44
00:02:19,910 --> 00:02:21,640
punters a altres nodes.

45
00:02:21,640 --> 00:02:25,500
Per exemple, la fletxa que s'estén des
el segon element de nens

46
00:02:25,500 --> 00:02:28,400
representa la lletra B
en clau d'un diccionari.

47
00:02:28,400 --> 00:02:31,920
I en el diagrama més gran
el etiquetem amb una B.

48
00:02:31,920 --> 00:02:35,810
>> Tingueu en compte que en el diagrama més gran, quan
dibuixar un punter a un altre node,

49
00:02:35,810 --> 00:02:39,100
no importa on la punta de fletxa
compleix que un altre node.

50
00:02:39,100 --> 00:02:43,850
El nostre trie diccionari mostra conté
dues paraules, això i zoom.

51
00:02:43,850 --> 00:02:47,040
Anem a veure un exemple de
la recerca de dades per a una clau.

52
00:02:47,040 --> 00:02:50,800
>> Suposem que volem cercar el
valor corresponent per al bany clau.

53
00:02:50,800 --> 00:02:53,610
Començarem la nostra mirada cap amunt
en el node arrel.

54
00:02:53,610 --> 00:02:57,870
Llavors anem a prendre la primera lletra de la nostra
clau, B, i trobar els corresponents

55
00:02:57,870 --> 00:03:00,020
detectar en la nostra sèrie els nens.

56
00:03:00,020 --> 00:03:04,490
Observeu que hi ha exactament 26 punts
en la matriu, un per cada lletra de

57
00:03:04,490 --> 00:03:05,330
l'alfabet.

58
00:03:05,330 --> 00:03:08,800
I tindrem els punts representen la
lletres de l'alfabet en ordre.

59
00:03:08,800 --> 00:03:13,960
>> Mirarem el segon índex de llavors,
índex d'un, per a B. En general, si ens

60
00:03:13,960 --> 00:03:17,990
tenir algun caràcter alfabètic C que
podria determinar el lloc corresponent

61
00:03:17,990 --> 00:03:21,520
en la matriu dels nens utilitzant
un càlcul com aquest.

62
00:03:21,520 --> 00:03:25,140
Podríem haver utilitzat nens més grans
matriu si volíem oferir mirada d'

63
00:03:25,140 --> 00:03:28,380
tecles amb una gamma més àmplia de caràcters,
com la totalitat

64
00:03:28,380 --> 00:03:29,880
Conjunt de caràcters ASCII.

65
00:03:29,880 --> 00:03:32,630
>> En aquest cas, el punter
en la nostra sèrie els nens a

66
00:03:32,630 --> 00:03:34,320
índex no és nul.

67
00:03:34,320 --> 00:03:36,600
Així que seguirem buscant
el bany de la clau.

68
00:03:36,600 --> 00:03:40,130
Si alguna vegada ens trobem amb un punter nul
en el lloc adequat en els nens

69
00:03:40,130 --> 00:03:43,230
array mentre travessem els nodes,
llavors haurem de dir que

70
00:03:43,230 --> 00:03:45,630
No hem pogut trobar res per aquesta tecla.

71
00:03:45,630 --> 00:03:49,370
>> Ara, anem a prendre la segona lletra de l'
la clau, A, i continuar seguint

72
00:03:49,370 --> 00:03:52,400
punters d'aquesta manera fins que
arribar al final de la clau.

73
00:03:52,400 --> 00:03:56,530
Si arribem a la final de la clau sense
colpejar cap carrerons sense sortida, punters nuls,

74
00:03:56,530 --> 00:03:59,730
com és el cas aquí, llavors només
ha de comprovar una cosa més.

75
00:03:59,730 --> 00:04:02,110
És això realment clau
en el diccionari?

76
00:04:02,110 --> 00:04:07,660
>> Si és així, cal trobar un valor, o bé un
icona de cara somrient al nostre diagrama on

77
00:04:07,660 --> 00:04:08,750
la paraula acaba.

78
00:04:08,750 --> 00:04:12,270
Si hi ha alguna cosa més emmagatzemat amb
les dades, llavors podem tornar-lo.

79
00:04:12,270 --> 00:04:16,500
Per exemple, el zoològic clau no està en el
diccionari, tot i que podríem tenir

80
00:04:16,500 --> 00:04:19,810
arribat al final d'aquesta tecla sense
colpejar a un punter nul, mentre que

81
00:04:19,810 --> 00:04:21,089
recórrer el trie.

82
00:04:21,089 --> 00:04:25,436
>> Si tractem de buscar el bany de tecla, el
segon per l'índex de matriu de l'últim node,

83
00:04:25,436 --> 00:04:28,750
corresponent a la lletra H, es
han celebrat un punter nul.

84
00:04:28,750 --> 00:04:31,120
Així bany no és al diccionari.

85
00:04:31,120 --> 00:04:34,800
I així un trie és únic en què les tecles
mai s'emmagatzemen de manera explícita en

86
00:04:34,800 --> 00:04:36,650
l'estructura de dades.

87
00:04:36,650 --> 00:04:38,810
Llavors, com inserim alguna cosa
en un trie?

88
00:04:38,810 --> 00:04:41,780
>> Anem a inserir la clau
zoològic a la nostra trienni.

89
00:04:41,780 --> 00:04:46,120
Recordi que una cara somrient en un node
podria correspondre en el codi a un simple

90
00:04:46,120 --> 00:04:50,170
Valor booleà per indicar que el zoològic
és al diccionari o podria

91
00:04:50,170 --> 00:04:53,710
corresponen a més informació que ens
desitgi associar amb el zoo clau,

92
00:04:53,710 --> 00:04:56,860
com la definició de la
paraula o alguna altra cosa.

93
00:04:56,860 --> 00:05:00,350
En certa manera, el procés per inserir
alguna cosa en un trie és similar a

94
00:05:00,350 --> 00:05:02,060
buscar alguna cosa en un trie.

95
00:05:02,060 --> 00:05:05,720
>> Anem a començar amb el node arrel de nou,
següents indicadors corresponents a

96
00:05:05,720 --> 00:05:07,990
les cartes de la clau.

97
00:05:07,990 --> 00:05:11,310
Per sort, hem estat capaços de seguir punters
tot el camí fins que arribem a

98
00:05:11,310 --> 00:05:12,770
l'extrem de la clau.

99
00:05:12,770 --> 00:05:16,480
Des del zoològic és un prefix de la paraula
de zoom, que és un membre de la

100
00:05:16,480 --> 00:05:19,440
diccionari, que no cal
assignar els nous nodes.

101
00:05:19,440 --> 00:05:23,140
>> Podem modificar el node per indicar que
el camí de caràcters que condueixen a

102
00:05:23,140 --> 00:05:25,360
representa una tecla al diccionari.

103
00:05:25,360 --> 00:05:28,630
Ara, anem a tractar d'inserir el
BANY clau al trienni.

104
00:05:28,630 --> 00:05:32,260
Començarem en el node arrel
i seguir els punters de nou.

105
00:05:32,260 --> 00:05:35,620
Però en aquesta situació, arribem a un mort
acabar abans que som capaços d'arribar a la

106
00:05:35,620 --> 00:05:36,940
extrem de la clau.

107
00:05:36,940 --> 00:05:40,980
Ara, haurem d'assignar un nou
nodes hauran de assignar una nova

108
00:05:40,980 --> 00:05:43,660
node per a cada restant
carta de la clau.

109
00:05:43,660 --> 00:05:46,740
>> En aquest cas, només tenim
assignar un node nou.

110
00:05:46,740 --> 00:05:50,590
Llavors haurem de fer que l'índex H
fer referència a aquest nou node.

111
00:05:50,590 --> 00:05:54,070
Un cop més, podem modificar el node a
indicar que la ruta d'accés de caràcters

112
00:05:54,070 --> 00:05:57,120
donant lloc al fet que representa un
clau en el nostre diccionari.

113
00:05:57,120 --> 00:06:00,730
Anem a raonar sobre la asimptòtica
complexitat dels nostres procediments per a aquests

114
00:06:00,730 --> 00:06:02,110
dues operacions.

115
00:06:02,110 --> 00:06:06,420
>> Ens adonem que en els dos casos el nombre
dels passos del nostre algorisme es va prendre

116
00:06:06,420 --> 00:06:09,470
proporcional al nombre de
lletres a la paraula clau.

117
00:06:09,470 --> 00:06:10,220
Això és correcte.

118
00:06:10,220 --> 00:06:13,470
Quan es vol buscar una paraula en una
trie només ha de recórrer

119
00:06:13,470 --> 00:06:17,100
les lletres una per una fins que ja sigui
arribar al final de la paraula o

120
00:06:17,100 --> 00:06:19,060
un carreró sense sortida al trienni.

121
00:06:19,060 --> 00:06:22,470
>> I quan es vol introduir una clau
parell en un trie valor utilitzant el

122
00:06:22,470 --> 00:06:26,250
procediment ja vam comentar, el pitjor dels casos
haurà d'assignar un nou node

123
00:06:26,250 --> 00:06:27,550
per a cada lletra.

124
00:06:27,550 --> 00:06:31,290
I anem a suposar que l'assignació
és una operació constant de temps.

125
00:06:31,290 --> 00:06:35,850
Així que si suposem que la longitud de la clau és
delimitada per una constant fixa, tant

126
00:06:35,850 --> 00:06:39,400
inserció i mirar cap amunt són constants
operacions de temps per a un trie.

127
00:06:39,400 --> 00:06:42,930
>> Si no fem aquesta suposició que
la longitud de la clau està limitada per una fix

128
00:06:42,930 --> 00:06:46,650
constant, llavors la inserció i mirar cap amunt,
en el pitjor dels casos, són lineals en el

129
00:06:46,650 --> 00:06:48,240
longitud de la clau.

130
00:06:48,240 --> 00:06:51,800
Noti que el nombre d'elements emmagatzemats
al trie no afecta la mirada fins

131
00:06:51,800 --> 00:06:52,820
o el temps d'inserció.

132
00:06:52,820 --> 00:06:55,360
Només ha afectat per la
longitud de la clau.

133
00:06:55,360 --> 00:06:59,300
>> Per contra, l'addició d'entrades a, diguem,
una taula hash tendeix a fer

134
00:06:59,300 --> 00:07:01,250
futur mirar cap amunt més lent.

135
00:07:01,250 --> 00:07:04,520
Si bé això pot semblar atractiu al principi,
hem de tenir en compte que un

136
00:07:04,520 --> 00:07:08,740
complexitat asimptòtica favorables no
significa que en la pràctica les dades

137
00:07:08,740 --> 00:07:11,410
estructura és necessàriament
irreprotxable.

138
00:07:11,410 --> 00:07:15,860
També cal considerar que per emmagatzemar un
paraula en un trie que necessitem, en el pitjor dels casos

139
00:07:15,860 --> 00:07:19,700
cas, un nombre de nodes proporcional
de la longitud de la paraula en si mateixa.

140
00:07:19,700 --> 00:07:21,880
>> Tries tendeixen a utilitzar una gran quantitat d'espai.

141
00:07:21,880 --> 00:07:25,620
Això està en contrast amb una taula hash,
on només necessitem un de nou node a

142
00:07:25,620 --> 00:07:27,940
emmagatzemar algun parell de valors clau.

143
00:07:27,940 --> 00:07:31,370
Ara, de nou, en teoria, gran espai
el consum no sembla ser un gran

144
00:07:31,370 --> 00:07:34,620
fer front, sobretot tenint en compte que modern
ordinadors tenen gigabytes i

145
00:07:34,620 --> 00:07:36,180
gigabytes de memòria.

146
00:07:36,180 --> 00:07:39,200
Però resulta que encara tenim
de preocupar per l'ús de memòria i

147
00:07:39,200 --> 00:07:42,540
organització pel bé de
rendiment, ja que les computadores modernes

148
00:07:42,540 --> 00:07:46,960
disposar de mecanismes en el marc del
campana per accelerar l'accés de memòria.

149
00:07:46,960 --> 00:07:51,180
>> No obstant això, aquests mecanismes funcionen millor quan
accessos de memòria es fan en compacte

150
00:07:51,180 --> 00:07:52,810
regions o zones.

151
00:07:52,810 --> 00:07:55,910
I els nodes d'un trie podrien residir
en qualsevol lloc d'aquest munt.

152
00:07:55,910 --> 00:07:58,390
Però aquestes són les compensacions
que hem de considerar.

153
00:07:58,390 --> 00:08:01,440
>> Recordeu que, en triar una dada
estructura per a una determinada tasca,

154
00:08:01,440 --> 00:08:04,420
ha de pensar en quin tipus de
operacions de l'estructura de dades ha de

155
00:08:04,420 --> 00:08:07,140
el suport i la quantitat de les prestacions
de cada un dels

156
00:08:07,140 --> 00:08:09,080
matèria d'operacions a nosaltres.

157
00:08:09,080 --> 00:08:11,300
Aquestes operacions poden fins i tot
estendre més enllà de simplement

158
00:08:11,300 --> 00:08:13,430
bàsica mirada i la inserció.

159
00:08:13,430 --> 00:08:17,010
Suposem que volem implementar un tipus
de la funcionalitat d'autocompletar, i molt

160
00:08:17,010 --> 00:08:18,890
com a motor de cerca de Google fa.

161
00:08:18,890 --> 00:08:22,210
És a dir, tornar totes les claus i
valors que potencialment

162
00:08:22,210 --> 00:08:24,130
tenir un prefix donat.

163
00:08:24,130 --> 00:08:27,050
>> Un trie és únicament útil
per a aquesta operació.

164
00:08:27,050 --> 00:08:29,890
És senzill per recórrer
trie per a cada caràcter de

165
00:08:29,890 --> 00:08:30,950
el prefix.

166
00:08:30,950 --> 00:08:33,559
Igual que una operació de mirar cap amunt,
podríem seguir punters

167
00:08:33,559 --> 00:08:35,400
caràcter per caràcter.

168
00:08:35,400 --> 00:08:38,659
Després, quan vam arribar a la final de l'
prefix, podríem recórrer la

169
00:08:38,659 --> 00:08:42,049
porció restant de l'estructura de dades
des de qualsevol de les tecles més enllà

170
00:08:42,049 --> 00:08:43,980
aquest punt té el prefix.

171
00:08:43,980 --> 00:08:47,670
>> També és fàcil obtenir aquest anunci
en ordre alfabètic des de la

172
00:08:47,670 --> 00:08:50,970
elements de la matriu nens
s'ordenen alfabèticament.

173
00:08:50,970 --> 00:08:54,420
Així que espero que vostè consideri
donar intentar l'intent.

174
00:08:54,420 --> 00:08:56,085
Sóc Kevin Schmid, i això és CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ah, aquest és el començament
de la disminució.

177
00:09:00,790 --> 00:09:01,350
Ho sento.

178
00:09:01,350 --> 00:09:01,870
Ho sento.

179
00:09:01,870 --> 00:09:02,480
Ho sento.

180
00:09:02,480 --> 00:09:03,130
Ho sento.

181
00:09:03,130 --> 00:09:03,950
>> Vaga de quatre.

182
00:09:03,950 --> 00:09:04,360
Estic fora.

183
00:09:04,360 --> 00:09:05,280
Ho sento.

184
00:09:05,280 --> 00:09:06,500
Ho sento.

185
00:09:06,500 --> 00:09:07,490
Ho sento.

186
00:09:07,490 --> 00:09:12,352
Ho sento per fer la persona que
ha d'editar aquest es torni boig.

187
00:09:12,352 --> 00:09:13,280
>> Ho sento.

188
00:09:13,280 --> 00:09:13,880
Ho sento.

189
00:09:13,880 --> 00:09:15,080
Ho sento.

190
00:09:15,080 --> 00:09:15,680
Ho sento.

191
00:09:15,680 --> 00:09:16,280
>> ALTAVEU 1: Ben fet.

192
00:09:16,280 --> 00:09:17,530
Això estava molt ben fet.

193
00:09:17,530 --> 00:09:18,430