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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Někdy, při stavbě
Program, možná budete chtít využít

3
00:00:10,890 --> 00:00:13,190
datové struktury známé jako slovník.

4
00:00:13,190 --> 00:00:17,960
Slovník klíče mapy, které jsou
obvykle řetězce, hodnot, ints,

5
00:00:17,960 --> 00:00:21,900
znaky, ukazatel na nějaký předmět,
co chceme.

6
00:00:21,900 --> 00:00:26,510
Je to jako obyčejné slovníky
že mapa slova přes definic.

7
00:00:26,510 --> 00:00:29,440
>> Slovníky nám poskytují
schopnost ukládat informace

8
00:00:29,440 --> 00:00:32,750
spojené s něčím
a podívat se na to později.

9
00:00:32,750 --> 00:00:36,620
Tak jak jsme se vlastně provádět
slovník, řekněme, C kódu, který můžeme

10
00:00:36,620 --> 00:00:38,460
použití v jednom z našich programů?

11
00:00:38,460 --> 00:00:41,790
No, existuje mnoho způsobů, jak
bychom mohli realizovat slovník.

12
00:00:41,790 --> 00:00:45,930
>> Pro jednoho, mohli bychom použít pole, které jsme
dynamicky re-size, nebo můžeme použít

13
00:00:45,930 --> 00:00:49,150
spojový seznam, hash tabulka
nebo binární strom.

14
00:00:49,150 --> 00:00:52,250
Ale ať si vybereme, měli bychom
dbát na efektivitu a

15
00:00:52,250 --> 00:00:54,300
výkon implementace.

16
00:00:54,300 --> 00:00:57,930
Měli bychom přemýšlet o použitém algoritmu
vložit a vyhledat položky do

17
00:00:57,930 --> 00:00:59,120
naše datová struktura.

18
00:00:59,120 --> 00:01:03,060
>> Nyní předpokládejme, že jsme
chcete používat řetězce jako klíče.

19
00:01:03,060 --> 00:01:07,290
Pojďme se bavit o jedné z možností,
datová struktura se nazývá trie.

20
00:01:07,290 --> 00:01:11,210
Tak tady je vizuální reprezentace
z trie.

21
00:01:11,210 --> 00:01:14,590
>> Jak obrázek naznačuje, trie
je datový stromová struktura s

22
00:01:14,590 --> 00:01:16,050
uzly spojeny.

23
00:01:16,050 --> 00:01:19,420
Vidíme, že tam je jasně kořen
Uzel se některé odkazy se rozšiřuje

24
00:01:19,420 --> 00:01:20,500
ostatní uzly.

25
00:01:20,500 --> 00:01:23,040
Ale to, co dělá každý uzel se skládá z?

26
00:01:23,040 --> 00:01:26,700
Budeme-li předpokládat, že jsme ukládání klíčů
s pouze abecední znaky, a

27
00:01:26,700 --> 00:01:30,150
my se nestaráme o kapitalizaci,
Zde je definice uzlu, který

28
00:01:30,150 --> 00:01:31,100
bude stačit.

29
00:01:31,100 --> 00:01:34,130
>> Objekt, jehož typ struct
uzel má dvě části

30
00:01:34,130 --> 00:01:35,740
volal dat a děti.

31
00:01:35,740 --> 00:01:39,200
Nechali jsme část dat jako komentář
být nahrazena složkou

32
00:01:39,200 --> 00:01:43,190
Prohlášení když struct uzel je
začleněny do programu C.

33
00:01:43,190 --> 00:01:47,040
Datová část uzlu může být
Logická hodnota označující, zda nebo

34
00:01:47,040 --> 00:01:51,160
Není uzel reprezentuje dokončení
ze slovníku klíče, nebo by to mohlo být

35
00:01:51,160 --> 00:01:54,240
Řetězec představující definici
na slova ve slovníku.

36
00:01:54,240 --> 00:01:58,870
>> Budeme používat smajlíky ukázat
, je-li přítomna dat v uzlu.

37
00:01:58,870 --> 00:02:02,310
Existuje 26 prvků v našem
děti pole, jeden index

38
00:02:02,310 --> 00:02:03,690
podle abecedy.

39
00:02:03,690 --> 00:02:06,570
Uvidíme význam
z toho brzy.

40
00:02:06,570 --> 00:02:10,759
>> Pojďme se blíže podívat na kořenový uzel
v našem diagramu, který nemá žádná data

41
00:02:10,759 --> 00:02:14,740
spojené s tím, jak je uvedeno
absence smajlíka v

42
00:02:14,740 --> 00:02:16,110
Datová část.

43
00:02:16,110 --> 00:02:19,910
Šipky vyčnívat z částí
Děti pole reprezentují non-uzel

44
00:02:19,910 --> 00:02:21,640
odkazy na jiné uzly.

45
00:02:21,640 --> 00:02:25,500
Například, šipka sahající od
druhý prvek dětí

46
00:02:25,500 --> 00:02:28,400
představuje písmeno B
ve slovníku klíč.

47
00:02:28,400 --> 00:02:31,920
A ve větším diagramu
jsme to označení s B.

48
00:02:31,920 --> 00:02:35,810
>> Všimněte si, že v širším schématu, kdy jsme
nakreslit ukazatel do jiného uzlu, je

49
00:02:35,810 --> 00:02:39,100
Nezáleží na tom, kde se šipka
odpovídá, že jiný uzel.

50
00:02:39,100 --> 00:02:43,850
Náš vzorek slovník trie obsahuje
dvě slova, která i zoom.

51
00:02:43,850 --> 00:02:47,040
Pojďme se projít příklad
vyhledávání dat na klíč.

52
00:02:47,040 --> 00:02:50,800
>> Předpokládejme, že jsme se chtěli podívat do
odpovídající hodnotu klíče lázně.

53
00:02:50,800 --> 00:02:53,610
Začneme náš pohled vzhůru
na kořenový uzel.

54
00:02:53,610 --> 00:02:57,870
Pak budeme mít první písmeno našeho
klíč, B, a najít odpovídající

55
00:02:57,870 --> 00:03:00,020
místě v našem děti poli.

56
00:03:00,020 --> 00:03:04,490
Všimněte si, že tam je přesně 26 míst
v poli, jeden pro každé písmeno

57
00:03:04,490 --> 00:03:05,330
abeceda.

58
00:03:05,330 --> 00:03:08,800
A budeme mít skvrny představují
písmena abecedy v pořadí.

59
00:03:08,800 --> 00:03:13,960
>> My se podíváme na druhý index pak,
index jeden, pro B. Obecně platí, že pokud bychom

60
00:03:13,960 --> 00:03:17,990
nějaké abecední znak C my
by mohla stanovit odpovídající místo

61
00:03:17,990 --> 00:03:21,520
v dětském pole pomocí
Výpočet takhle.

62
00:03:21,520 --> 00:03:25,140
Mohli jsme použít větší děti
pole, pokud bychom chtěli nabídnout look up

63
00:03:25,140 --> 00:03:28,380
klíče s širším rozsahu znaků,
jako je celé

64
00:03:28,380 --> 00:03:29,880
Znaková sada ASCII.

65
00:03:29,880 --> 00:03:32,630
>> V tomto případě, ukazatel
v našem děti pole v

66
00:03:32,630 --> 00:03:34,320
index jeden není null.

67
00:03:34,320 --> 00:03:36,600
Takže budeme nadále hledat
up klíče lázně.

68
00:03:36,600 --> 00:03:40,130
Pokud se někdy setkali nulový ukazatel
na správném místě, u dětí

69
00:03:40,130 --> 00:03:43,230
pole, když jsme se projet uzly,
pak budeme muset říci, že jsme

70
00:03:43,230 --> 00:03:45,630
nemohl najít nic pro tento klíč.

71
00:03:45,630 --> 00:03:49,370
>> Nyní budeme mít druhý dopis
náš klíč, a dále po

72
00:03:49,370 --> 00:03:52,400
ukazatele tímto způsobem, dokud se
dostat se na konec našeho klíče.

73
00:03:52,400 --> 00:03:56,530
Pokud se dostanete na konec klíče, aniž by
zasáhla všechny slepé uličky, null ukazatele,

74
00:03:56,530 --> 00:03:59,730
jako je tomu v tomto případě, pak pouze
je nutné zkontrolovat ještě jednu věc.

75
00:03:59,730 --> 00:04:02,110
Je to klíč skutečně
ve slovníku?

76
00:04:02,110 --> 00:04:07,660
>> Pokud ano, měli bychom najít hodnotu, dobře
smiley ikona tvář v našem diagramu, kde

77
00:04:07,660 --> 00:04:08,750
slovo končí.

78
00:04:08,750 --> 00:04:12,270
Pokud tam je něco jiného, ​​ukládají se
data, pak se můžeme vrátit.

79
00:04:12,270 --> 00:04:16,500
Například, klíč není v zoo
slovník, i když jsme mohli mít

80
00:04:16,500 --> 00:04:19,810
dosáhl na konci tohoto klíče, aniž by
bít nulový ukazatel, zatímco my

81
00:04:19,810 --> 00:04:21,089
iterovat trie.

82
00:04:21,089 --> 00:04:25,436
>> Pokud jsme se snažili vyhledat klíčové koupel,
Druhý index pole loňského uzlu,

83
00:04:25,436 --> 00:04:28,750
odpovídající písmeno H, by
drželi nulový ukazatel.

84
00:04:28,750 --> 00:04:31,120
Takže koupel není ve slovníku.

85
00:04:31,120 --> 00:04:34,800
A tak trie je unikátní v tom, že klíče
se nikdy výslovně uloženy v

86
00:04:34,800 --> 00:04:36,650
datová struktura.

87
00:04:36,650 --> 00:04:38,810
Tak jak jsme se vložit něco
do trie?

88
00:04:38,810 --> 00:04:41,780
>> Pojďme vložte klíč
zoo do našeho trie.

89
00:04:41,780 --> 00:04:46,120
Pamatujte si, že smajlíky v uzlu
mohla odpovídat v kódu na jednoduché

90
00:04:46,120 --> 00:04:50,170
Booleovská hodnota, která naznačují, že zoo
je ve slovníku, nebo by to mohlo

91
00:04:50,170 --> 00:04:53,710
odpovídají více informací, které jsme
chcete spojit s klíčovým zoo,

92
00:04:53,710 --> 00:04:56,860
jako vymezení
Slovo nebo něco jiného.

93
00:04:56,860 --> 00:05:00,350
V některých ohledech, proces vložit
něco do trie je podobný

94
00:05:00,350 --> 00:05:02,060
hledá něco v trie.

95
00:05:02,060 --> 00:05:05,720
>> Začneme s kořenový uzel znovu,
Následující ukazatele odpovídá

96
00:05:05,720 --> 00:05:07,990
dopisy z našich klíčových.

97
00:05:07,990 --> 00:05:11,310
Naštěstí jsme byli schopni sledovat ukazatele
celou cestu až jsme dorazili do

98
00:05:11,310 --> 00:05:12,770
konec klíče.

99
00:05:12,770 --> 00:05:16,480
Vzhledem k tomu, zoo je prefix slova
zoom, který je členem

100
00:05:16,480 --> 00:05:19,440
slovník, nepotřebujeme, aby
přidělit žádné nové uzly.

101
00:05:19,440 --> 00:05:23,140
>> Můžeme upravit uzel což znamená, že
cesta znaků, které vedou k

102
00:05:23,140 --> 00:05:25,360
představuje klíč v našem slovníku.

103
00:05:25,360 --> 00:05:28,630
Nyní zkusme vložení
Klíčovým BATH do trie.

104
00:05:28,630 --> 00:05:32,260
Začneme na kořenový uzel
a sledovat ukazatele znovu.

105
00:05:32,260 --> 00:05:35,620
Ale v této situaci, zasáhla jsme mrtvý
skončí dříve, než jsme schopni se dostat do

106
00:05:35,620 --> 00:05:36,940
konec klíče.

107
00:05:36,940 --> 00:05:40,980
Nyní budeme muset přidělit některé nové
uzly budou muset přidělit jednu novou

108
00:05:40,980 --> 00:05:43,660
uzel pro každý zbývající
Dopis z našeho klíče.

109
00:05:43,660 --> 00:05:46,740
>> V tomto případě, my prostě potřebujeme
přidělit jeden nový uzel.

110
00:05:46,740 --> 00:05:50,590
Potom budeme potřebovat, aby index H
odkázání se na tento nový uzel.

111
00:05:50,590 --> 00:05:54,070
Opět můžeme změnit uzel
ukazují, že cesta znaků

112
00:05:54,070 --> 00:05:57,120
což vede k tomu představuje
klíč v našem slovníku.

113
00:05:57,120 --> 00:06:00,730
Pojďme uvažovat o asymptotické
Komplexnost našich postupů pro tyto

114
00:06:00,730 --> 00:06:02,110
dvě operace.

115
00:06:02,110 --> 00:06:06,420
>> Všimli jsme si, že v obou případech číslo
z kroků náš algoritmus trvalo byla

116
00:06:06,420 --> 00:06:09,470
úměrná počtu
Písmena na klíčové slovo.

117
00:06:09,470 --> 00:06:10,220
To je pravda.

118
00:06:10,220 --> 00:06:13,470
Chcete-li vyhledat slovo v
trie stačí iterovat

119
00:06:13,470 --> 00:06:17,100
dopisy jeden po druhém, dokud buď
dostanete na konec slova, nebo

120
00:06:17,100 --> 00:06:19,060
hit slepé uličky v trie.

121
00:06:19,060 --> 00:06:22,470
>> A když budete chtít vložit klíč
hodnota dvojice do trie pomocí

122
00:06:22,470 --> 00:06:26,250
Postup jsme diskutovali, nejhorší případ
bude vám přidělení nového uzlu

123
00:06:26,250 --> 00:06:27,550
pro každé písmeno.

124
00:06:27,550 --> 00:06:31,290
A budeme předpokládat, že rozdělení
je konstantní doba provozu.

125
00:06:31,290 --> 00:06:35,850
Takže pokud budeme předpokládat, že délka klíče je
ohraničena pevnou konstantou, a to jak

126
00:06:35,850 --> 00:06:39,400
vkládání a vyhledat konstantní
časové operace pro trie.

127
00:06:39,400 --> 00:06:42,930
>> Pokud se nám nepodaří tuto domněnku, že
délka klíče je ohraničena pevnou

128
00:06:42,930 --> 00:06:46,650
konstantní, pak se po vložení a dívat se,
V nejhorším případě, jsou lineární v

129
00:06:46,650 --> 00:06:48,240
délka klíče.

130
00:06:48,240 --> 00:06:51,800
Všimněte si, že počet položek, uloženo
v trie nemá vliv na vzhled nahoru

131
00:06:51,800 --> 00:06:52,820
nebo vložení čas.

132
00:06:52,820 --> 00:06:55,360
Je to jen vliv
délka klíče.

133
00:06:55,360 --> 00:06:59,300
>> Naopak, přidávání položek, řekněme,
hash tabulky vede k tomu,

134
00:06:59,300 --> 00:07:01,250
budoucnost vypadat pomaleji.

135
00:07:01,250 --> 00:07:04,520
I když to může znít jako lákavá na první pohled,
bychom měli mít na paměti, že

136
00:07:04,520 --> 00:07:08,740
příznivé asymptotická složitost není
znamená, že v praxi jsou data

137
00:07:08,740 --> 00:07:11,410
struktura je nutně
nic vytknout.

138
00:07:11,410 --> 00:07:15,860
Musíme také vzít v úvahu, že k ukládání
slovo v trie potřebujeme, v nejhorším

139
00:07:15,860 --> 00:07:19,700
případ, počet uzlů úměrná
k délce slova.

140
00:07:19,700 --> 00:07:21,880
>> Pokusí mají tendenci používat hodně prostoru.

141
00:07:21,880 --> 00:07:25,620
To je na rozdíl od hash tabulky,
kde budeme potřebovat pouze jeden nový uzel

142
00:07:25,620 --> 00:07:27,940
uložit některé dvojice klíč hodnota.

143
00:07:27,940 --> 00:07:31,370
Nyní, opět teoreticky, velký prostor
Spotřeba nevypadá jako velký

144
00:07:31,370 --> 00:07:34,620
řešit, a to zejména vzhledem k tomu, moderní
počítače mají gigabajtů a

145
00:07:34,620 --> 00:07:36,180
GB paměti.

146
00:07:36,180 --> 00:07:39,200
Ale ukázalo se, že máme stále
se starat o využití paměti a

147
00:07:39,200 --> 00:07:42,540
organizace v zájmu
výkon, protože moderní počítače

148
00:07:42,540 --> 00:07:46,960
mají mechanismy v místě pod
kapuce urychlit přístup do paměti.

149
00:07:46,960 --> 00:07:51,180
>> Ale tyto mechanismy fungují nejlépe, když
paměťové přístupy jsou v kompaktním

150
00:07:51,180 --> 00:07:52,810
regiony nebo oblasti.

151
00:07:52,810 --> 00:07:55,910
A uzly trie mohla pobývat
kdekoliv v této hromadě.

152
00:07:55,910 --> 00:07:58,390
Ale to jsou kompromisy
že musíme vzít v úvahu.

153
00:07:58,390 --> 00:08:01,440
>> Pamatujte si, že při výběru dat
struktura pro určitý úkol, se

154
00:08:01,440 --> 00:08:04,420
by měl přemýšlet o tom, jaké druhy
operace datová struktura musí

155
00:08:04,420 --> 00:08:07,140
Podpora a kolik výkonu
každého z nich

156
00:08:07,140 --> 00:08:09,080
operace záleží na nás.

157
00:08:09,080 --> 00:08:11,300
Tyto operace mohou dokonce
přesahují jen

158
00:08:11,300 --> 00:08:13,430
Základní vzhled a vložení.

159
00:08:13,430 --> 00:08:17,010
Předpokládejme, že bychom chtěli zavést jakousi
automatického dokončování funkcí, hodně

160
00:08:17,010 --> 00:08:18,890
jako vyhledávač Google dělá.

161
00:08:18,890 --> 00:08:22,210
To znamená, že vrátí všechny klíče a
potenciálně hodnoty, které

162
00:08:22,210 --> 00:08:24,130
mají danou předponu.

163
00:08:24,130 --> 00:08:27,050
>> Trie je jednoznačně užitečná
pro tuto operaci.

164
00:08:27,050 --> 00:08:29,890
Je to jednoduché iteraci
trie pro každý znak

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

166
00:08:30,950 --> 00:08:33,559
Stejně jako se podívat do provozu,
jsme mohli sledovat ukazatele

167
00:08:33,559 --> 00:08:35,400
znak po znaku.

168
00:08:35,400 --> 00:08:38,659
Pak, když dorazíme na konec
prefix, můžeme iterovat

169
00:08:38,659 --> 00:08:42,049
Zbývající část datové struktury
protože každá z klíčů po

170
00:08:42,049 --> 00:08:43,980
Tento bod má předponu.

171
00:08:43,980 --> 00:08:47,670
>> Je také snadné získat tento zápis
v abecedním pořadí od

172
00:08:47,670 --> 00:08:50,970
prvky dětského pole
jsou řazeny abecedně.

173
00:08:50,970 --> 00:08:54,420
Takže doufejme, že budete uvažovat
dávání se snaží vyzkoušet.

174
00:08:54,420 --> 00:08:56,085
Já jsem Kevin Schmid, a to je CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ach, to je začátek
poklesu.

177
00:09:00,790 --> 00:09:01,350
Je mi to líto.

178
00:09:01,350 --> 00:09:01,870
Promiňte.

179
00:09:01,870 --> 00:09:02,480
Promiňte.

180
00:09:02,480 --> 00:09:03,130
Promiňte.

181
00:09:03,130 --> 00:09:03,950
>> Strike čtyři.

182
00:09:03,950 --> 00:09:04,360
Jsem mimo.

183
00:09:04,360 --> 00:09:05,280
Promiňte.

184
00:09:05,280 --> 00:09:06,500
Promiňte.

185
00:09:06,500 --> 00:09:07,490
Promiňte.

186
00:09:07,490 --> 00:09:12,352
Omlouváme se za osobu, která
má-li upravit tento zbláznit.

187
00:09:12,352 --> 00:09:13,280
>> Promiňte.

188
00:09:13,280 --> 00:09:13,880
Promiňte.

189
00:09:13,880 --> 00:09:15,080
Promiňte.

190
00:09:15,080 --> 00:09:15,680
Promiňte.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Výborně.

192
00:09:16,280 --> 00:09:17,530
To bylo opravdu dobře.

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