algoritmos de busqueda - hash truncamiento
TRANSCRIPT
Universidad Tecnológica de Chile
Ingeniería Informática
Algoritmos de búsqueda.
Truncamiento.
Integrantes : Mario Bustamante Luis Guzmán Asignatura : Análisis de algoritmo Fecha : 17 – 04 – 2014 Sección : 112 Profesora : Pilar Pardo
1 | P á g i n a
Contenido I.- Introducción. ................................................................................................................................... 2
II.- Desarrollo. ...................................................................................................................................... 3
1.- Búsqueda Lineal. ........................................................................................................................ 4
2.- Búsqueda Binaria. ...................................................................................................................... 5
3.- Búsqueda por transformación de claves (hashing). ................................................................... 6
3.1.- Plegamiento. ....................................................................................................................... 6
3.2.- Aritmética Modular. ............................................................................................................ 6
3.3.- Mitad del cuadrado. ............................................................................................................ 7
3.4.- Truncamiento. ..................................................................................................................... 7
6.- Colisiones. ................................................................................................................................ 11
6.1.- Reasignación. .................................................................................................................... 11
6.2.- Arreglos anidados. ............................................................................................................ 12
6.3.- Encadenamiento. .............................................................................................................. 12
III.- Conclusión. .................................................................................................................................. 13
2 | P á g i n a
I.- Introducción.
Los algoritmos de búsqueda son aquellos diseñados para localizar
elementos específicos dentro de una estructura.
En el presente informe se darán a conocer los algoritmos de búsqueda
lineal, binaria, y por transformación de claves o hash. Desarrollando su definición,
su mejor y peor caso, además de su caso promedio, con ejemplos en los casos
mencionados. Dando a destacar el Hash de Truncamiento.
Además se mostrará que sucede en caso de que dos claves choquen
dentro de un arreglo, lo más bien conocido como colisión. Dando a conocer
algunas formas de resolver estas colisiones.
3 | P á g i n a
II.- Desarrollo.
Los algoritmos de búsqueda son aquellos diseñados para localizar a un
elemento con propiedades específicas dentro de una estructura (array) de datos.
Mientras que los algoritmos de ordenamiento son cuales ponen elementos de una
lista o vector en una posición dada por alguna relación de orden, o algún cambio
en su estructura. Existen los siguientes tipos de búsqueda:
- Búsqueda Lineal.
- Búsqueda Binaria.
- Búsqueda por transformación de claves (hashing).
4 | P á g i n a
1.- Búsqueda Lineal.
La búsqueda lineal consiste en buscar de manera secuencial un elemento,
es decir, preguntar si el elemento que se está buscando es igual al primero, si no
pasa al segundo, si no al tercero, así sucesivamente hasta encontrar la igualdad o
llegar al final del vector.
En caso de almacenar el elemento se envía un mensaje con un resultado
positivo y la posición en la que se almacenó, y en caso de que no se almacene se
envía un resultado negativo.
Esta búsqueda no necesita que el vector esté ordenado o que sea par o
impar.
El mejor de los casos se presenta cuando la búsqueda termina tan pronto
como se inicia, puede darse el caso de que la primera posición examinada sea la
que contenga el elemento que se está buscando.
El peor de los casos se presenta cuando el elemento a buscar se encuentra
en la última posición del vector.
El caso promedio es cuando el elemento a buscar se encuentra en la
posición central del vector, esta se presenta con la formula N/2 donde N es el
tamaño del vector.
Ejemplo:
Buscar el elemento “10”, “14”, “19” en el vector.
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
Al buscar el elemento “10” se ejemplifica el mejor de los casos ya que está
presente al comienzo del vector y sólo se debe realizar una comparación. Al
buscar el elemento “14” se observa el caso promedio ya que está en la posición
central del vector. Y al buscar el elemento “19” se muestra el peor de los casos ya
que se debe recorrer todo el vector para encontrar el elemento.
5 | P á g i n a
2.- Búsqueda Binaria.
La búsqueda Binaria consiste en buscar el elemento en el centro del vector,
en caso de que esta posición no sea la que se está buscando se compara si el
índice es mayor o menor, en caso de que el índice sea mayor se considera el
vector desde la posición central hacia los mayores y la otra mitad se desecha, en
caso contrario si el índice es menor se toma desde el centro del vector hasta las
posiciones menores y el resto se desecha. Este procedimiento se hace hasta que
se encuentre la posición requerida con los nuevos vectores más pequeños que se
van generando al realizar el procedimiento.
Un requerimiento de este tipo de búsqueda es que el vector debe estar
ordenado.
Utiliza la lógica de “divide y vencerás”.
El mejor de los casos se presenta cuando la búsqueda requiere de sólo una
comparación. Cuyo esfuerzo mínimo sea 1.
El caso promedio se expresa con el cálculo 1/2log2n.
El peor de los casos está expresada por el cálculo de log2n, lo que
representa el esfuerzo máximo para el algoritmo, lo que quiere decir que tras
todas las divisiones realizadas se localizará el elemento o se tendrá la certeza de
que el elemento no existe.
Ejemplo
6 | P á g i n a
3.- Búsqueda por transformación de claves (hashing).
Hashing consiste en una transformación matemática con una función que
da como resultado la posición en que se guardará o buscará una clave.
3.1.- Plegamiento.
El plegamiento consiste en dividir la clave en distintas partes, luego
combinarlas ya sea mediante una operación de suma o multiplicación para así
obtener un índice. Todas las partes, excluyendo la última, deben tener la misma
cantidad de dígitos. En caso de que el largo de la clave supere el largo del vector
se trunca la clave para que pueda ser almacenada.
Ejemplo.
Vector de 100 posiciones. Clave: 28312405 Procedimiento: H(clave) = 283 + 124 + 05 H(clave) = 412 (resultado que sobrepasa el límite del vector, por este motivo se trunca) 4|12 = 12 Así la clave será guardada en la posición 12 del vector.
3.2.- Aritmética Modular.
La aritmética modular consiste en convertir la clave a un entero, lo que se
hace es dividir la clave por el tamaño del vector, el resto o residuo de esta división
es la posición del vector donde se almacenará.
Ejemplo.
Vector de 100 posiciones. Clave: 12325 Procedimiento: H(clave) = 12325 MOD 100 H(clave) = 25
Lo que quiere decir que la clave será guardada en la posición 25 del vector
7 | P á g i n a
3.3.- Mitad del cuadrado.
La mitad del cuadrado consiste en calcular el cuadrado de la clave y tomar
los dígitos centrales de este resultado, estos dígitos serán la posición del vector
para almacenar el dato (en caso de que la cifra resultante sea impar se toma el
valor central y el número anterior).
La función está expresada por la fórmula: H(x) = X^2 (donde x es la clave).
Ejemplo.
Vector de 100 posiciones. Clave: 562 Procedimiento: H(clave) = 562^2 H(clave) = 315844
Lo que quiere decir que la clave será guardada en la posición 58.
3.4.- Truncamiento.
El truncamiento consiste en tomar algunos dígitos de la clave y con estos
formar una posición en un array. Se ignora parte de la clave para con el resto
formar un índice de almacenamiento.
La idea consiste en tener un listado de números, seleccionar por ejemplo la
posición 2, 4 y 6; para así tener una posición en donde poder almacenar la clave.
Llevando esto a un ejemplo práctico:
5700931 → 703
3498610 → 481
0056241 → 064
9134720 → 142
5174829 → 142
8 | P á g i n a
Lo positivo del truncamiento y una de las ventajas por sobre otros métodos
de búsqueda y ordenamiento es que no solo funciona con valores numéricos,
también funciona con caracteres alfabéticos, esto se puede aplicar de dos formas:
1) Transformar cada carácter en un número asociado a su posición en el
abecedario.
2) Transformar cada carácter en un número asociado a su valor según el
código ASCII.
Una vez obtenida la clave en forma numérica, se puede utilizar
normalmente.
La elección de los dígitos a considerar es arbitraria, pueden tomarse
posiciones pares o impares. Luego se les puede unir de izquierda a derecha o de
derecha a izquierda.
La función queda definida por:
H(K) = dígitos(t1 t2 t3 … tn)+1
Existen casos en los que a la clave generada se le agrega una unidad, esto
es para los casos en el que el vector de almacenamiento tenga valores entre el 1 y
el 100, así se evita la obtención de un valor 0.
H(K1) = dígitos(7 2 5 9) + 1 = 76
H(K2) = dígitos(9 3 5 9) + 1 = 96
Una de las principales desventajas de utilizar truncamiento y en sí el
método de hashing es que dos o más claves puede tomar una misma posición
dentro de la tabla de hash, a esto es a lo que se le llama Colisión. Cuando hay
colisiones se requiere de un proceso adicional para encontrar la posición
disponible para la clave, lo cual disminuye la eficiencia del método.
9 | P á g i n a
Mejor de los casos.
El mejor de los casos es cuando el elemento buscado se encuentra en la
primera posición, en cuyo caso el algoritmo indicará que se encontró la clave tras
una sola comparación. En el caso del ordenamiento se considera el mejor de los
casos cuando todas las claves son perfectamente ordenadas, sin ningún caso de
colisión. Cuando una función logra evitar el 100% de las colisiones es conocida
como Hashing Perfecto.
Caso Promedio.
El caso promedio es cuando el elemento buscado se encuentra, pero no en
la primera posición, eso provoca que el tiempo de búsqueda se alargue para
encontrar la posición requerida. En el caso de ordenamiento se considera el caso
promedio cuando existen algunas colisiones, demorando más al algoritmo en
ordenar, pero sin mayores problemas.
10 | P á g i n a
Peor de los casos.
El peor de los casos que se puede encontrar es cuando se produce una
colisión en las posiciones, esto quiere decir que la posición en la que se va a
almacenar una clave ya está siendo utilizada por otra. En el caso de ordenamiento
se considera el peor de los casos cuando todas las claves van a una sola posición
del array, produciendo una totalidad de colisiones.
11 | P á g i n a
6.- Colisiones.
Una colisión se produce cuando una función hash obtiene una misma dirección para dos
claves distintas. Los métodos más utilizados para resolverlas son:
- Reasignación.
- Arreglos anidados.
- Áreas de desborde.
6.1.- Reasignación.
El método de reasignación trabaja bajo principios de comparación, entre los más utilizados
están:
- Prueba lineal.
- Prueba cuadrática.
- Doble dirección hash.
6.1.1.- Prueba lineal.
La prueba lineal consiste en que una vez que se detecta la colisión se debe recorrer el
vector a partir del punto de colisión, buscando el elemento. Este proceso concluye cuando se
encuentra el elemento buscado o cuando se encuentra una posición vacía. Si el arreglo llega a su
fin se vuelve a comenzar por el inicio de este.
La desventaja de este método es que puede ser que las claves estén agrupadas en zonas
específicas, dejando grandes espacios vacíos.
12 | P á g i n a
6.1.2.- Prueba cuadrática.
La prueba cuadrática se rige bajo los mismos términos que la prueba lineal. La diferencia
está en que las direcciones alternativas se generan con el cuadrado de estas. Esto permite una
mejor distribución de las claves colisionadas. (D + 1, D + 4, D + 9… considerando D como la clave y
el número entero como el cuadrado de la siguiente posición).
La desventaja de este método es que existen casillas que no son vistas.
6.1.3.- Doble dirección hash.
La doble dirección hash consiste en que una vez que se detecta la colisión se debe generar
una nueva dirección utilizando una función hash a la dirección. Esta acción se repite hasta
encontrar el elemento o hasta cuando se encuentre una posición vacía.
6.2.- Arreglos anidados.
Los arreglos anidados consisten en que cada elemento del arreglo tenga otro arreglo en el
cual se almacenan los elementos colisionados. No siendo siempre la solución más efectiva, ya que
lo hace depender mucho del espacio de memoria requerido.
6.3.- Encadenamiento.
El encadenamiento consiste en que cada elemento del arreglo tenga un puntero a una lista
ligada. Así cuando se produzca la colisión se guardará normalmente en su posición, pero de la lista
ligada.
13 | P á g i n a
III.- Conclusión.
Para concluir se puede mencionar que cada algoritmo que existe tiene un
mejor caso, un caso promedio y un peor caso, dados por distintas funciones
obviamente. Cada algoritmo tiene ventajas y desventajas por sobre los demás, es
por esto que al momento de utilizarlos se deben contemplar bien estas ventajas y
desventajas para poder trabajar de la forma más eficiente.
Uno de los puntos a destacar del truncamiento por sobre otros métodos de
ordenamiento es que funciona con caracteres tanto numéricos como alfabéticos.
Además de que es modificable en la selección de los caracteres a considerar para
la posición de la clave a considerar.