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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: Às vezes, quando a construção de um
programa, você pode querer utilizar um

3
00:00:10,890 --> 00:00:13,190
estrutura de dados conhecida como um dicionário.

4
00:00:13,190 --> 00:00:17,960
Um dicionário chaves mapas, que são
geralmente cordas, com os valores, ints,

5
00:00:17,960 --> 00:00:21,900
caracteres, um ponteiro para algum objeto,
o que quisermos.

6
00:00:21,900 --> 00:00:26,510
É como dicionários comuns
que mapa palavras através de definições.

7
00:00:26,510 --> 00:00:29,440
>> Dicionários nos fornecer o
capacidade de armazenar informações

8
00:00:29,440 --> 00:00:32,750
associado a algo
e procurá-lo mais tarde.

9
00:00:32,750 --> 00:00:36,620
Então, como é que vamos realmente implementar um
dicionário, digamos, em código C que pudermos

10
00:00:36,620 --> 00:00:38,460
usar em um de nossos programas?

11
00:00:38,460 --> 00:00:41,790
Bem, há uma série de maneiras que
poderíamos implementar um dicionário.

12
00:00:41,790 --> 00:00:45,930
>> Por um lado, nós poderíamos usar uma matriz que
dinamicamente re-size ou nós poderíamos usar um

13
00:00:45,930 --> 00:00:49,150
lista ligada, tabela hash
ou uma árvore binária.

14
00:00:49,150 --> 00:00:52,250
Mas o que quer que nós escolhemos, devemos
estar consciente da eficiência e da

15
00:00:52,250 --> 00:00:54,300
desempenho da implementação.

16
00:00:54,300 --> 00:00:57,930
Devemos pensar sobre o algoritmo usado
para inserir e procurar os itens em

17
00:00:57,930 --> 00:00:59,120
a estrutura de dados.

18
00:00:59,120 --> 00:01:03,060
>> Por enquanto, vamos supor que nós
quer usar strings como chaves.

19
00:01:03,060 --> 00:01:07,290
Vamos falar sobre uma possibilidade,
uma estrutura de dados chamada de trie.

20
00:01:07,290 --> 00:01:11,210
Então aqui está uma representação visual
de um trie.

21
00:01:11,210 --> 00:01:14,590
>> Como a imagem sugere, um trie
é uma estrutura de dados em árvore com

22
00:01:14,590 --> 00:01:16,050
nós ligados.

23
00:01:16,050 --> 00:01:19,420
Vemos que há claramente uma raiz
nó com alguns links que se estende até

24
00:01:19,420 --> 00:01:20,500
outros nós.

25
00:01:20,500 --> 00:01:23,040
Mas o que é que cada nó consiste?

26
00:01:23,040 --> 00:01:26,700
Se assumirmos que estamos armazenar chaves
com apenas caracteres alfabéticos, e

27
00:01:26,700 --> 00:01:30,150
que não se preocupam com a capitalização,
aqui está uma definição de um nó que

28
00:01:30,150 --> 00:01:31,100
será suficiente.

29
00:01:31,100 --> 00:01:34,130
>> Um objeto cujo tipo é struct
nó tem duas peças

30
00:01:34,130 --> 00:01:35,740
chamada de dados e crianças.

31
00:01:35,740 --> 00:01:39,200
Nós deixamos a parte de dados como um comentário
para ser substituído por um componente

32
00:01:39,200 --> 00:01:43,190
declaração quando nó struct é
incorporados em um programa C.

33
00:01:43,190 --> 00:01:47,040
A parte de dados de um nó pode ser um
Valor booleano para indicar se

34
00:01:47,040 --> 00:01:51,160
não representa o nó a conclusão
de uma chave de dicionário ou pode ser uma

35
00:01:51,160 --> 00:01:54,240
string representando a definição
de uma palavra no dicionário.

36
00:01:54,240 --> 00:01:58,870
>> Vamos usar um rosto sorridente para indicar
quando os dados estão presentes em um nó.

37
00:01:58,870 --> 00:02:02,310
Há 26 elementos em nosso
variedade crianças, um índice

38
00:02:02,310 --> 00:02:03,690
por caractere alfabético.

39
00:02:03,690 --> 00:02:06,570
Vamos ver o significado
deste breve.

40
00:02:06,570 --> 00:02:10,759
>> Vamos olhar mais de perto do nó raiz
no nosso diagrama, que não tem dados

41
00:02:10,759 --> 00:02:14,740
associada com ele, tal como indicado pela
ausência do rosto sorridente no

42
00:02:14,740 --> 00:02:16,110
porção de dados.

43
00:02:16,110 --> 00:02:19,910
As setas que se estendem a partir das partes de
os filhos de matriz representam não-nó

44
00:02:19,910 --> 00:02:21,640
ponteiros para outros nós.

45
00:02:21,640 --> 00:02:25,500
Por exemplo, a seta que se estende a partir de
o segundo elemento de crianças

46
00:02:25,500 --> 00:02:28,400
representa a letra B
em uma chave de dicionário.

47
00:02:28,400 --> 00:02:31,920
E no diagrama maior
que rotulá-la com um B.

48
00:02:31,920 --> 00:02:35,810
>> Note que, no diagrama de maior, quando
desenhar um ponteiro para outro nó, ele

49
00:02:35,810 --> 00:02:39,100
Não importa onde a ponta da seta
cumpre que outro nó.

50
00:02:39,100 --> 00:02:43,850
Nosso dicionário amostra contém trie
duas palavras, que e zoom.

51
00:02:43,850 --> 00:02:47,040
Vamos examinar um exemplo de
olhando para cima de dados para uma chave.

52
00:02:47,040 --> 00:02:50,800
>> Suponha que queria procurar o
valor correspondente para o banho de chave.

53
00:02:50,800 --> 00:02:53,610
Vamos começar o nosso olhar para cima
no nó de raiz.

54
00:02:53,610 --> 00:02:57,870
Então nós vamos ter a primeira letra do nosso
chave, B, e encontrar o correspondente

55
00:02:57,870 --> 00:03:00,020
detectar, em nossa disposição filhos.

56
00:03:00,020 --> 00:03:04,490
Observe que há exatamente 26 pontos
na matriz, um para cada letra

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

58
00:03:05,330 --> 00:03:08,800
E nós vamos ter os pontos representam o
letras do alfabeto em ordem.

59
00:03:08,800 --> 00:03:13,960
>> Nós vamos olhar para o segundo índice, em seguida,
índice de um, para B. Em geral, se

60
00:03:13,960 --> 00:03:17,990
tem algum character C nós
poderia determinar o ponto correspondente

61
00:03:17,990 --> 00:03:21,520
na matriz crianças usando
um cálculo assim.

62
00:03:21,520 --> 00:03:25,140
Poderíamos ter usado um crianças maiores
array se queríamos oferecer olhar-se de

63
00:03:25,140 --> 00:03:28,380
teclas com uma ampla gama de caracteres,
, tais como o todo

64
00:03:28,380 --> 00:03:29,880
Conjunto de caracteres ASCII.

65
00:03:29,880 --> 00:03:32,630
>> Neste caso, o ponteiro
na nossa gama crianças em

66
00:03:32,630 --> 00:03:34,320
índice não é nulo.

67
00:03:34,320 --> 00:03:36,600
Então, vamos continuar procurando
o banho de chave.

68
00:03:36,600 --> 00:03:40,130
Se alguma vez encontrou um ponteiro nulo
no local apropriado nas crianças

69
00:03:40,130 --> 00:03:43,230
array enquanto atravessamos os nós,
então nós vamos ter que dizer que nós

70
00:03:43,230 --> 00:03:45,630
não poderia encontrar qualquer coisa para essa chave.

71
00:03:45,630 --> 00:03:49,370
>> Agora, vamos dar a segunda letra
nossa chave, A, e continuar seguindo

72
00:03:49,370 --> 00:03:52,400
ponteiros, desta forma até que nós
chegar ao fim da nossa chave.

73
00:03:52,400 --> 00:03:56,530
Se chegar ao final da chave sem
bater nos becos sem saída, os ponteiros nulos,

74
00:03:56,530 --> 00:03:59,730
como é o caso aqui, então nós só
tem que verificar mais uma coisa.

75
00:03:59,730 --> 00:04:02,110
É esta chave realmente
no dicionário?

76
00:04:02,110 --> 00:04:07,660
>> Se assim for, devemos encontrar um valor, bem a
ícone do smiley face em nosso diagrama onde

77
00:04:07,660 --> 00:04:08,750
a palavra termina.

78
00:04:08,750 --> 00:04:12,270
Se há algo mais armazenado com
os dados, então podemos devolvê-lo.

79
00:04:12,270 --> 00:04:16,500
Por exemplo, o jardim zoológico de chave não está no
dicionário, mesmo que pudéssemos ter

80
00:04:16,500 --> 00:04:19,810
atingido o fim desta chave sem nunca
bater um ponteiro nulo, enquanto nós

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

82
00:04:21,089 --> 00:04:25,436
>> Se tentei olhar para o banho de chave, o
segundo para índice da matriz do último nó,

83
00:04:25,436 --> 00:04:28,750
correspondente à letra H, que
realizaram um ponteiro nulo.

84
00:04:28,750 --> 00:04:31,120
Então banho não está no dicionário.

85
00:04:31,120 --> 00:04:34,800
E assim um trie é único em que as chaves
nunca são explicitamente armazenada em

86
00:04:34,800 --> 00:04:36,650
a estrutura de dados.

87
00:04:36,650 --> 00:04:38,810
Então, como vamos inserir algo
numa trie?

88
00:04:38,810 --> 00:04:41,780
>> Vamos inserir a chave
zoológico em nossa trie.

89
00:04:41,780 --> 00:04:46,120
Lembre-se que um rosto sorridente em um nó
poderia corresponder em código para um simples

90
00:04:46,120 --> 00:04:50,170
Valor booleano para indicar que zoo
está no dicionário ou poderia

91
00:04:50,170 --> 00:04:53,710
correspondem a mais informações que nós
deseja associar com o zoológico chave,

92
00:04:53,710 --> 00:04:56,860
como a definição do
palavra ou outra coisa.

93
00:04:56,860 --> 00:05:00,350
De certa forma, o processo para inserir
algo em um trie é semelhante ao

94
00:05:00,350 --> 00:05:02,060
procurando algo em uma trie.

95
00:05:02,060 --> 00:05:05,720
>> Vamos começar com o nó raiz de novo,
seguintes ponteiros correspondentes a

96
00:05:05,720 --> 00:05:07,990
as letras da nossa chave.

97
00:05:07,990 --> 00:05:11,310
Felizmente, fomos capazes de seguir ponteiros
todo o caminho até chegarmos

98
00:05:11,310 --> 00:05:12,770
a extremidade da chave.

99
00:05:12,770 --> 00:05:16,480
Desde zoológico é um prefixo da palavra
zoom, que é um membro da

100
00:05:16,480 --> 00:05:19,440
dicionário, não precisa
alocar quaisquer novos nós.

101
00:05:19,440 --> 00:05:23,140
>> Nós podemos modificar o nó para indicar que
o caminho de caracteres que conduzem a

102
00:05:23,140 --> 00:05:25,360
ela representa uma chave no nosso dicionário.

103
00:05:25,360 --> 00:05:28,630
Agora, vamos tentar inserir o
BANHO chave na trie.

104
00:05:28,630 --> 00:05:32,260
Vamos começar no nó raiz
e siga os ponteiros novamente.

105
00:05:32,260 --> 00:05:35,620
Mas nesta situação, nós batemos um morto
acabar antes somos capazes de chegar ao

106
00:05:35,620 --> 00:05:36,940
extremidade da chave.

107
00:05:36,940 --> 00:05:40,980
Agora, vamos ter de alocar algum novo
nós terá de atribuir uma nova

108
00:05:40,980 --> 00:05:43,660
nó para cada restante
carta de nossa chave.

109
00:05:43,660 --> 00:05:46,740
>> Neste caso, só precisamos
para alocar um novo nó.

110
00:05:46,740 --> 00:05:50,590
Então nós vamos ter que fazer o índice H
referência a este novo nó.

111
00:05:50,590 --> 00:05:54,070
Mais uma vez, podemos modificar o nó
indicar que o caminho de caracteres

112
00:05:54,070 --> 00:05:57,120
levando a que ele representa um
chave no nosso dicionário.

113
00:05:57,120 --> 00:06:00,730
Vamos raciocinar sobre o assintótica
complexidade dos nossos procedimentos para estes

114
00:06:00,730 --> 00:06:02,110
duas operações.

115
00:06:02,110 --> 00:06:06,420
>> Notamos que em ambos os casos, o número
de passos de nosso algoritmo tomou foi

116
00:06:06,420 --> 00:06:09,470
proporcional ao número de
letras da palavra-chave.

117
00:06:09,470 --> 00:06:10,220
Isso mesmo.

118
00:06:10,220 --> 00:06:13,470
Quando você quiser procurar uma palavra num
trie você só precisa para percorrer

119
00:06:13,470 --> 00:06:17,100
as letras uma a uma até que você quer
alcançar o fim da palavra ou

120
00:06:17,100 --> 00:06:19,060
atingido um beco sem saída no trie.

121
00:06:19,060 --> 00:06:22,470
>> E quando você deseja inserir uma chave
par de valores em uma trie usando o

122
00:06:22,470 --> 00:06:26,250
procedimento discutimos, o pior caso
terá que alocar um novo nó

123
00:06:26,250 --> 00:06:27,550
para cada letra.

124
00:06:27,550 --> 00:06:31,290
E vamos supor que a alocação
é uma operação de tempo constante.

125
00:06:31,290 --> 00:06:35,850
Assim, se assumirmos que o comprimento da chave é
delimitada por uma constante fixa, tanto

126
00:06:35,850 --> 00:06:39,400
inserção e olhar para cima são constantes
operações de tempo para uma trie.

127
00:06:39,400 --> 00:06:42,930
>> Se não fizermos esta suposição de que
o comprimento da chave é delimitada por um fixo

128
00:06:42,930 --> 00:06:46,650
constante, em seguida, inserção e olhar para cima,
no pior dos casos, são lineares no

129
00:06:46,650 --> 00:06:48,240
comprimento da chave.

130
00:06:48,240 --> 00:06:51,800
Note-se que o número de itens armazenados
no trie não afeta o olhar para cima

131
00:06:51,800 --> 00:06:52,820
ou o tempo de inserção.

132
00:06:52,820 --> 00:06:55,360
É só impactado pela
comprimento da chave.

133
00:06:55,360 --> 00:06:59,300
>> Em contraste, a adição de entradas para, por exemplo,
uma tabela hash tende a fazer

134
00:06:59,300 --> 00:07:01,250
futuro olhar para cima mais lento.

135
00:07:01,250 --> 00:07:04,520
Embora isso possa parecer atraente à primeira vista,
devemos ter em mente que um

136
00:07:04,520 --> 00:07:08,740
complexidade assintótica favorável não
significa que, na prática os dados

137
00:07:08,740 --> 00:07:11,410
estrutura é necessariamente
irrepreensível.

138
00:07:11,410 --> 00:07:15,860
Devemos considerar também que para armazenar um
palavra em uma trie que precisamos, no pior

139
00:07:15,860 --> 00:07:19,700
caso, um número de nós proporcional
para o comprimento da própria palavra.

140
00:07:19,700 --> 00:07:21,880
>> Tries tendem a usar um monte de espaço.

141
00:07:21,880 --> 00:07:25,620
Isso está em contraste com uma tabela hash,
em que só precisa de um novo nó a

142
00:07:25,620 --> 00:07:27,940
armazenar algumas par de valores chave.

143
00:07:27,940 --> 00:07:31,370
Agora, de novo, em teoria, o espaço grande
consumo não parece ser um grande

144
00:07:31,370 --> 00:07:34,620
lidar, especialmente tendo em conta que a moderna
computadores têm gigabytes e

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

146
00:07:36,180 --> 00:07:39,200
Mas acontece que ainda temos
se preocupar com o uso de memória e

147
00:07:39,200 --> 00:07:42,540
organização em prol da
desempenho, uma vez que os computadores modernos

148
00:07:42,540 --> 00:07:46,960
ter mecanismos em vigor sob o
capa para acelerar o acesso à memória.

149
00:07:46,960 --> 00:07:51,180
>> Mas esses mecanismos funcionam melhor quando
acessos à memória são feitos em compacto

150
00:07:51,180 --> 00:07:52,810
regiões ou zonas.

151
00:07:52,810 --> 00:07:55,910
E os nós de um trie pode residir
em qualquer lugar que heap.

152
00:07:55,910 --> 00:07:58,390
Mas estes são os trade-offs
que devemos considerar.

153
00:07:58,390 --> 00:08:01,440
>> Lembre-se que, ao escolher um data
estrutura para uma determinada tarefa, nós

154
00:08:01,440 --> 00:08:04,420
deve pensar em que tipo de
operações a estrutura de dados precisa

155
00:08:04,420 --> 00:08:07,140
suporte e quanto ao desempenho
de cada um daqueles

156
00:08:07,140 --> 00:08:09,080
assuntos operações para nós.

157
00:08:09,080 --> 00:08:11,300
Estas operações podem até
vão além de simples

158
00:08:11,300 --> 00:08:13,430
Olhe para cima e inserção básico.

159
00:08:13,430 --> 00:08:17,010
Suponha que queria implementar uma espécie
de funcionalidade de auto-completar, muito

160
00:08:17,010 --> 00:08:18,890
como motor de busca Google faz.

161
00:08:18,890 --> 00:08:22,210
Ou seja, retornar todas as chaves e
valores que potencialmente

162
00:08:22,210 --> 00:08:24,130
ter um determinado prefixo.

163
00:08:24,130 --> 00:08:27,050
>> Uma trie é exclusivamente útil
para esta operação.

164
00:08:27,050 --> 00:08:29,890
É simples para percorrer
o trie para cada personagem de

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

166
00:08:30,950 --> 00:08:33,559
Assim como um olhar para a operação,
poderíamos seguir ponteiros

167
00:08:33,559 --> 00:08:35,400
caractere por caractere.

168
00:08:35,400 --> 00:08:38,659
Em seguida, quando chegar ao fim do
prefixo, poderíamos percorrer a

169
00:08:38,659 --> 00:08:42,049
parte restante da estrutura de dados
desde que qualquer uma das teclas além

170
00:08:42,049 --> 00:08:43,980
Neste ponto temos o prefixo.

171
00:08:43,980 --> 00:08:47,670
>> É também fácil de obter este anúncio
em ordem alfabética desde o

172
00:08:47,670 --> 00:08:50,970
elementos da matriz crianças
são ordenados por ordem alfabética.

173
00:08:50,970 --> 00:08:54,420
Portanto, esperamos que você vai considerar
doação tenta uma tentativa.

174
00:08:54,420 --> 00:08:56,085
Eu sou Kevin Schmid, e este é CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, isso é o começo
do declínio.

177
00:09:00,790 --> 00:09:01,350
Sinto muito.

178
00:09:01,350 --> 00:09:01,870
Desculpe.

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

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

181
00:09:03,130 --> 00:09:03,950
>> Greve de quatro.

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

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

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

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

186
00:09:07,490 --> 00:09:12,352
Desculpem-me por fazer a pessoa que
tem para editar este enlouquecer.

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

188
00:09:13,280 --> 00:09:13,880
Desculpe.

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

190
00:09:15,080 --> 00:09:15,680
Desculpe.

191
00:09:15,680 --> 00:09:16,280
>> COLUNA 1: Bem feito.

192
00:09:16,280 --> 00:09:17,530
Isso foi muito bem feito.

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