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

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: A veces, cuando la construcción de una
programa, es posible que desee utilizar un

3
00:00:10,890 --> 00:00:13,190
estructura de datos conocida como un diccionario.

4
00:00:13,190 --> 00:00:17,960
A Mapas Diccionario teclas, que son
generalmente cuerdas, a los valores, enteros,

5
00:00:17,960 --> 00:00:21,900
caracteres, un puntero a un objeto,
lo que queramos.

6
00:00:21,900 --> 00:00:26,510
Es igual que los diccionarios normales
Ese mapa palabras a través de las definiciones.

7
00:00:26,510 --> 00:00:29,440
>> Diccionarios nos dan la
capacidad de almacenar información

8
00:00:29,440 --> 00:00:32,750
asociado con algo
y buscarlo más tarde.

9
00:00:32,750 --> 00:00:36,620
Así que ¿cómo podemos poner en práctica un
Diccionario en, por ejemplo, el código C que podemos

10
00:00:36,620 --> 00:00:38,460
utilizar en uno de nuestros programas?

11
00:00:38,460 --> 00:00:41,790
Bueno, hay un montón de maneras en que
podríamos implementar un diccionario.

12
00:00:41,790 --> 00:00:45,930
>> Por un lado, podríamos utilizar una matriz que
dinámicamente cambiar el tamaño o podríamos utilizar un

13
00:00:45,930 --> 00:00:49,150
lista enlazada, tabla hash
o un árbol binario.

14
00:00:49,150 --> 00:00:52,250
Pero cualquier cosa que elijamos, debemos
tener en cuenta la eficiencia y

15
00:00:52,250 --> 00:00:54,300
el rendimiento de la aplicación.

16
00:00:54,300 --> 00:00:57,930
Debemos pensar en el algoritmo utilizado
para insertar y buscar elementos en

17
00:00:57,930 --> 00:00:59,120
nuestra estructura de datos.

18
00:00:59,120 --> 00:01:03,060
>> Por ahora, vamos a suponer que
desee utilizar cadenas como claves.

19
00:01:03,060 --> 00:01:07,290
Vamos a hablar de una de las posibilidades,
una estructura de datos llamada trie.

20
00:01:07,290 --> 00:01:11,210
Así que aquí está una representación visual
de un trie.

21
00:01:11,210 --> 00:01:14,590
>> A medida que la imagen sugiere, un trie
es una estructura de datos en árbol con

22
00:01:14,590 --> 00:01:16,050
nodos enlazados.

23
00:01:16,050 --> 00:01:19,420
Vemos que hay claramente una raíz
nodo con algunos enlaces que se extiende a

24
00:01:19,420 --> 00:01:20,500
otros nodos.

25
00:01:20,500 --> 00:01:23,040
Pero ¿qué significa cada nodo consiste?

26
00:01:23,040 --> 00:01:26,700
Si asumimos que estamos almacenando claves
con sólo caracteres alfabéticos y

27
00:01:26,700 --> 00:01:30,150
no nos preocupamos por capitalización,
he aquí una definición de un nodo que

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

29
00:01:31,100 --> 00:01:34,130
>> Un objeto cuyo tipo es struct
nodo tiene dos partes

30
00:01:34,130 --> 00:01:35,740
llamada de datos y los niños.

31
00:01:35,740 --> 00:01:39,200
Hemos dejado la parte de datos como un comentario
para ser sustituido por un componente

32
00:01:39,200 --> 00:01:43,190
declaración al nodo de estructura es
incorporado en un programa en C.

33
00:01:43,190 --> 00:01:47,040
La parte de datos de un nodo puede ser un
Valor booleano para indicar si

34
00:01:47,040 --> 00:01:51,160
no el nodo representa la finalización
de una clave de diccionario o podría ser un

35
00:01:51,160 --> 00:01:54,240
cadena que representa la definición
de una palabra en el diccionario.

36
00:01:54,240 --> 00:01:58,870
>> Usaremos una cara sonriente para indicar
cuando los datos está presente en un nodo.

37
00:01:58,870 --> 00:02:02,310
Hay 26 elementos en nuestro
array niños, un índice

38
00:02:02,310 --> 00:02:03,690
por carácter alfabético.

39
00:02:03,690 --> 00:02:06,570
Veremos el significado
de este pronto.

40
00:02:06,570 --> 00:02:10,759
>> Vamos a tomar una mirada más cercana del nodo raíz
en nuestro diagrama, que no dispone de datos

41
00:02:10,759 --> 00:02:14,740
asociado con él, como se indica por la
ausencia de la cara sonriente en el

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

43
00:02:16,110 --> 00:02:19,910
Las flechas que se extienden desde las partes de
los hijos de la matriz representan libre de nodos

44
00:02:19,910 --> 00:02:21,640
punteros a otros nodos.

45
00:02:21,640 --> 00:02:25,500
Por ejemplo, la flecha que se extiende desde
el segundo elemento de niños

46
00:02:25,500 --> 00:02:28,400
representa la letra B
en clave de un diccionario.

47
00:02:28,400 --> 00:02:31,920
Y en el diagrama más grande
lo etiquetamos con una B.

48
00:02:31,920 --> 00:02:35,810
>> Tenga en cuenta que en el diagrama más grande, cuando
dibujar un puntero a otro nodo,

49
00:02:35,810 --> 00:02:39,100
no importa donde la punta de flecha
cumple que otro nodo.

50
00:02:39,100 --> 00:02:43,850
Nuestro trie diccionario muestra contiene
dos palabras, eso y zoom.

51
00:02:43,850 --> 00:02:47,040
Vamos a ver un ejemplo de
la búsqueda de datos para una clave.

52
00:02:47,040 --> 00:02:50,800
>> Supongamos que queremos buscar el
valor correspondiente para el baño clave.

53
00:02:50,800 --> 00:02:53,610
Comenzaremos nuestra mirada hacia arriba
en el nodo raíz.

54
00:02:53,610 --> 00:02:57,870
Entonces vamos a tomar la primera letra de nuestra
clave, B, y encontrar los correspondientes

55
00:02:57,870 --> 00:03:00,020
detectar en nuestra serie los niños.

56
00:03:00,020 --> 00:03:04,490
Observe que hay exactamente 26 puntos
en la matriz, uno por cada letra de

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

58
00:03:05,330 --> 00:03:08,800
Y tendremos los puntos representan la
letras del alfabeto en orden.

59
00:03:08,800 --> 00:03:13,960
>> Miraremos el segundo índice de entonces,
índice de uno, para B. En general, si nos

60
00:03:13,960 --> 00:03:17,990
tener algún carácter alfabético C que
podría determinar el lugar correspondiente

61
00:03:17,990 --> 00:03:21,520
en la matriz de los niños utilizando
un cálculo como éste.

62
00:03:21,520 --> 00:03:25,140
Podríamos haber utilizado niños más grandes
matriz si queríamos ofrecer mirada de

63
00:03:25,140 --> 00:03:28,380
teclas con una gama más amplia de caracteres,
como la totalidad

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

65
00:03:29,880 --> 00:03:32,630
>> En este caso, el puntero
en nuestra serie los niños en

66
00:03:32,630 --> 00:03:34,320
índice no es nulo.

67
00:03:34,320 --> 00:03:36,600
Así que vamos a seguir buscando
el baño de la clave.

68
00:03:36,600 --> 00:03:40,130
Si alguna vez nos encontramos con un puntero nulo
en el lugar adecuado en los niños

69
00:03:40,130 --> 00:03:43,230
array mientras atravesamos los nodos,
entonces vamos a tener que decir que

70
00:03:43,230 --> 00:03:45,630
No hemos podido encontrar nada para esa tecla.

71
00:03:45,630 --> 00:03:49,370
>> Ahora, vamos a tomar la segunda letra del
la llave, A, y continuar siguiendo

72
00:03:49,370 --> 00:03:52,400
punteros de esta manera hasta que
llegar al final de la llave.

73
00:03:52,400 --> 00:03:56,530
Si llegamos a la final de la llave sin
golpear ningún callejones sin salida, punteros nulos,

74
00:03:56,530 --> 00:03:59,730
como es el caso aquí, entonces sólo
tiene que comprobar una cosa más.

75
00:03:59,730 --> 00:04:02,110
¿Es esto realmente clave
en el diccionario?

76
00:04:02,110 --> 00:04:07,660
>> Si es así, hay que encontrar un valor, bien un
icono de cara sonriente en nuestro diagrama donde

77
00:04:07,660 --> 00:04:08,750
la palabra termina.

78
00:04:08,750 --> 00:04:12,270
Si hay algo más almacenado con
los datos, entonces podemos devolverlo.

79
00:04:12,270 --> 00:04:16,500
Por ejemplo, el zoológico llave no está en el
diccionario, a pesar de que podríamos tener

80
00:04:16,500 --> 00:04:19,810
alcanzado el final de esta tecla sin
golpear a un puntero nulo, mientras que

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

82
00:04:21,089 --> 00:04:25,436
>> Si tratamos de buscar el baño de tecla, el
segundo para el índice de matriz del último nodo,

83
00:04:25,436 --> 00:04:28,750
correspondiente a la letra H, se
han celebrado un puntero nulo.

84
00:04:28,750 --> 00:04:31,120
Así baño no está en el diccionario.

85
00:04:31,120 --> 00:04:34,800
Y así un trie es único en que las teclas
nunca se almacenan de manera explícita en

86
00:04:34,800 --> 00:04:36,650
la estructura de datos.

87
00:04:36,650 --> 00:04:38,810
Entonces, ¿cómo insertamos algo
en un trie?

88
00:04:38,810 --> 00:04:41,780
>> Vamos a insertar la llave
zoológico en nuestra trie.

89
00:04:41,780 --> 00:04:46,120
Recuerde que una cara sonriente en un nodo
podría corresponder en el código a un simple

90
00:04:46,120 --> 00:04:50,170
Valor booleano para indicar que el zoológico
está en el diccionario o podría

91
00:04:50,170 --> 00:04:53,710
corresponden a más información que nos
desee asociar con el zoo clave,

92
00:04:53,710 --> 00:04:56,860
como la definición de la
palabra o alguna otra cosa.

93
00:04:56,860 --> 00:05:00,350
En cierto modo, el proceso para insertar
algo en un trie es similar a

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

95
00:05:02,060 --> 00:05:05,720
>> Vamos a empezar con el nodo raíz de nuevo,
siguientes indicadores correspondientes a

96
00:05:05,720 --> 00:05:07,990
las cartas de la llave.

97
00:05:07,990 --> 00:05:11,310
Por suerte, hemos sido capaces de seguir punteros
todo el camino hasta que llegamos a

98
00:05:11,310 --> 00:05:12,770
el extremo de la llave.

99
00:05:12,770 --> 00:05:16,480
Desde el zoológico es un prefijo de la palabra
de zoom, que es un miembro de la

100
00:05:16,480 --> 00:05:19,440
diccionario, que no es necesario
asignar los nuevos nodos.

101
00:05:19,440 --> 00:05:23,140
>> Podemos modificar el nodo para indicar que
el camino de caracteres que conducen a

102
00:05:23,140 --> 00:05:25,360
representa una tecla en el diccionario.

103
00:05:25,360 --> 00:05:28,630
Ahora, vamos a tratar de insertar el
BAÑO llave en el trie.

104
00:05:28,630 --> 00:05:32,260
Empezaremos en el nodo raíz
y seguir los punteros de nuevo.

105
00:05:32,260 --> 00:05:35,620
Pero en esta situación, llegamos a un muerto
terminar antes de que somos capaces de llegar a la

106
00:05:35,620 --> 00:05:36,940
extremo de la llave.

107
00:05:36,940 --> 00:05:40,980
Ahora, tendremos que asignar un nuevo
nodos tendrán que asignar una nueva

108
00:05:40,980 --> 00:05:43,660
nodo para cada restante
carta de la llave.

109
00:05:43,660 --> 00:05:46,740
>> En este caso, sólo tenemos
asignar un nodo nuevo.

110
00:05:46,740 --> 00:05:50,590
Entonces tendremos que hacer que el índice H
hacer referencia a este nuevo nodo.

111
00:05:50,590 --> 00:05:54,070
Una vez más, podemos modificar el nodo a
indicar que la ruta de acceso de caracteres

112
00:05:54,070 --> 00:05:57,120
dando lugar a que representa un
clave en nuestro diccionario.

113
00:05:57,120 --> 00:06:00,730
Vamos a razonar acerca de la asintótica
complejidad de nuestros procedimientos para estos

114
00:06:00,730 --> 00:06:02,110
dos operaciones.

115
00:06:02,110 --> 00:06:06,420
>> Nos damos cuenta de que en ambos casos el número
de los pasos de nuestro algoritmo se tomó

116
00:06:06,420 --> 00:06:09,470
proporcional al número de
letras en la palabra clave.

117
00:06:09,470 --> 00:06:10,220
Eso es correcto.

118
00:06:10,220 --> 00:06:13,470
Cuando se quiere buscar una palabra en una
trie sólo tiene que recorrer

119
00:06:13,470 --> 00:06:17,100
las letras una por una hasta que ya sea
llegar al final de la palabra o

120
00:06:17,100 --> 00:06:19,060
un callejón sin salida en el trie.

121
00:06:19,060 --> 00:06:22,470
>> Y cuando se desea introducir una clave
par en un trie valor utilizando el

122
00:06:22,470 --> 00:06:26,250
procedimiento ya comentamos, el peor de los casos
tendrá que asignar un nuevo nodo

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

124
00:06:27,550 --> 00:06:31,290
Y vamos a suponer que la asignación
es una operación constante de tiempo.

125
00:06:31,290 --> 00:06:35,850
Así que si suponemos que la longitud de la clave es
delimitada por una constante fija, tanto

126
00:06:35,850 --> 00:06:39,400
inserción y mirar hacia arriba son constantes
operaciones de tiempo para un trie.

127
00:06:39,400 --> 00:06:42,930
>> Si no hacemos esta suposición de que
la longitud de la clave está limitada por una fijo

128
00:06:42,930 --> 00:06:46,650
constante, entonces la inserción y mirar hacia arriba,
en el peor de los casos, son lineales en el

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

130
00:06:48,240 --> 00:06:51,800
Note que el número de elementos almacenados
en el trie no afecta a la mirada hasta

131
00:06:51,800 --> 00:06:52,820
o el tiempo de inserción.

132
00:06:52,820 --> 00:06:55,360
Sólo ha afectado por la
longitud de la clave.

133
00:06:55,360 --> 00:06:59,300
>> Por el contrario, la adición de entradas a, digamos,
una tabla hash tiende a hacer

134
00:06:59,300 --> 00:07:01,250
futuro mirar hacia arriba más lento.

135
00:07:01,250 --> 00:07:04,520
Si bien esto puede sonar atractivo al principio,
debemos tener en cuenta que un

136
00:07:04,520 --> 00:07:08,740
complejidad asintótica favorables no
significa que en la práctica los datos

137
00:07:08,740 --> 00:07:11,410
estructura es necesariamente
irreprochable.

138
00:07:11,410 --> 00:07:15,860
También hay que considerar que para almacenar un
palabra en un trie que necesitamos, en el peor de los casos

139
00:07:15,860 --> 00:07:19,700
caso, un número de nodos proporcional
a la longitud de la palabra en sí misma.

140
00:07:19,700 --> 00:07:21,880
>> Tries tienden a utilizar una gran cantidad de espacio.

141
00:07:21,880 --> 00:07:25,620
Eso está en contraste con una tabla hash,
donde sólo necesitamos uno nuevo nodo a

142
00:07:25,620 --> 00:07:27,940
almacenar algún par de valores clave.

143
00:07:27,940 --> 00:07:31,370
Ahora, de nuevo, en teoría, gran espacio
el consumo no parece ser un gran

144
00:07:31,370 --> 00:07:34,620
hacer frente, sobre todo teniendo en cuenta que moderno
computadoras tienen gigabytes y

145
00:07:34,620 --> 00:07:36,180
gigabytes de memoria.

146
00:07:36,180 --> 00:07:39,200
Pero resulta que aún tenemos
que preocuparse por el uso de memoria y

147
00:07:39,200 --> 00:07:42,540
organización por el bien de
rendimiento, ya que las computadoras modernas

148
00:07:42,540 --> 00:07:46,960
contar con mecanismos en el marco del
campana para acelerar el acceso de memoria.

149
00:07:46,960 --> 00:07:51,180
>> Sin embargo, estos mecanismos funcionan mejor cuando
accesos de memoria se hacen en compacto

150
00:07:51,180 --> 00:07:52,810
regiones o zonas.

151
00:07:52,810 --> 00:07:55,910
Y los nodos de un trie podrían residir
en cualquier lugar de ese montón.

152
00:07:55,910 --> 00:07:58,390
Pero estas son las compensaciones
que debemos considerar.

153
00:07:58,390 --> 00:08:01,440
>> Recuerde que, al elegir un dato
estructura para una determinada tarea,

154
00:08:01,440 --> 00:08:04,420
debe pensar en qué tipo de
operaciones de la estructura de datos tiene que

155
00:08:04,420 --> 00:08:07,140
el apoyo y la cantidad de las prestaciones
de cada uno de los

156
00:08:07,140 --> 00:08:09,080
materia de operaciones a nosotros.

157
00:08:09,080 --> 00:08:11,300
Estas operaciones pueden incluso
extenderse más allá de simplemente

158
00:08:11,300 --> 00:08:13,430
básica mirada y la inserción.

159
00:08:13,430 --> 00:08:17,010
Supongamos que queremos implementar un tipo
de la funcionalidad de autocompletar, y mucho

160
00:08:17,010 --> 00:08:18,890
como motor de búsqueda de Google hace.

161
00:08:18,890 --> 00:08:22,210
Es decir, devolver todas las llaves y
valores que potencialmente

162
00:08:22,210 --> 00:08:24,130
tener un prefijo dado.

163
00:08:24,130 --> 00:08:27,050
>> Un trie es únicamente útil
para esta operación.

164
00:08:27,050 --> 00:08:29,890
Es sencillo para recorrer
trie para cada carácter de

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

166
00:08:30,950 --> 00:08:33,559
Al igual que una operación de mirar hacia arriba,
podríamos seguir punteros

167
00:08:33,559 --> 00:08:35,400
carácter por carácter.

168
00:08:35,400 --> 00:08:38,659
Luego, cuando llegamos a la final de la
prefijo, podríamos recorrer la

169
00:08:38,659 --> 00:08:42,049
porción restante de la estructura de datos
desde cualquiera de las teclas más allá

170
00:08:42,049 --> 00:08:43,980
este punto tiene el prefijo.

171
00:08:43,980 --> 00:08:47,670
>> También es fácil obtener este anuncio
en orden alfabético desde la

172
00:08:47,670 --> 00:08:50,970
elementos de la matriz niños
se ordenan alfabéticamente.

173
00:08:50,970 --> 00:08:54,420
Así que espero que usted considere
dar intentó el intento.

174
00:08:54,420 --> 00:08:56,085
Soy Kevin Schmid, y esto es CS50.

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

176
00:08:58,745 --> 00:09:00,790
>> Ah, este es el comienzo
de la disminución.

177
00:09:00,790 --> 00:09:01,350
Lo siento.

178
00:09:01,350 --> 00:09:01,870
Lo siento.

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

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

181
00:09:03,130 --> 00:09:03,950
>> Huelga de cuatro.

182
00:09:03,950 --> 00:09:04,360
Estoy fuera.

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

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

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

186
00:09:07,490 --> 00:09:12,352
Lo siento por hacer la persona que
tiene que editar este se vuelva loco.

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

188
00:09:13,280 --> 00:09:13,880
Lo siento.

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

190
00:09:15,080 --> 00:09:15,680
Lo siento.

191
00:09:15,680 --> 00:09:16,280
>> ALTAVOZ 1: Bien hecho.

192
00:09:16,280 --> 00:09:17,530
Eso estaba muy bien hecho.

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