Metodos De Busqueda

UNIDAD 8

METODOS DE BUSQUEDA

La recuperación de información es una de las aplicaciones más importantes de las computadoras. La búsqueda de información está relacionada con las tablas para consultas. Estas tablas contienen una cantidad de información que se almacenan en forma de listas de parejas de datos. Por ejemplo un catálogo con una lista de libros de matemáticas, en donde es necesario buscar con frecuencia elementos en una lista. Existen diferentes tipos de búsqueda, pero en este informe describiremos sólo la de tipo Secuencial y Binaria.

8.1 Búsqueda Binaria Interna

Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado.

Esta búsqueda utiliza un método de “divide y vencerás” para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si este es el elemento buscado entonces la búsqueda ha terminado. En caso contrario se determina si el elemento buscado está en la primera o segunda mitad de la lista y a continuación se repite el proceso anterior, utilizando el elemento central de esta sublista. Este tipo de búsqueda se utiliza en vectores ordenados.

8.1.1 Búsqueda Secuencial Interna

Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.

Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo.

Diferencias entre búsquedas

Secuencial Binaria

No requiere ningún requisito por parte del vector El vector debe estar ordenado

Compara cada elemento del vector con el que se desea encontrar Divide el espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento deseado

Se examina el vector partiendo del primer elemento hasta llegar al último Se examina el vector partiendo desde el elemento central de la lista

Consume excesivo tiempo en la localización del elemento, por ello es recomendable para vectores de pocos datos Eficiente con relación al tiempo, si el vector está ordenado, por ello es recomendable para conjunto de grandes datos

8.1.2 Búsqueda Hash

La idea básica de este método consiste en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas. Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando R (k1 )= R(k2)

Pero: K1 diferente de K2 decimos que hay una colisión. A dos llaves diferentes que les corresponda la misma dirección relativa se les llama sinónimos.

A las técnicas de cálculo de direcciones también se les conoce como:

• Técnicas de almacenamiento disperso

• Técnicas aleatorias

• Métodos de transformación de llave - a- dirección

• Técnicas de direccionamiento directo

• Métodos de tabla Hash

• Métodos de Hashing

Pero el término más usado es el de Hashing. Al cálculo que se realiza para obtener una dirección a partir de una llave se le conoce como función hash.

Ventajas

- Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar

- Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones

- No se requiere almacenamiento adicional para los índices.

Desventajas

- No pueden usarse registros de longitud variable

- El archivo no está clasificado

- No permite llaves repetidas

- Solo permite acceso por una sola llave

Costos

- Tiempo de procesamiento requerido para la aplicación de la función hash

- Tiempo de procesamiento y los accesos E/S requeridos para solucionar las colisiones.

La eficiencia de una función hash depende de:

1. La distribución de los valores de llave que realmente se usan

2. El numero de valores de llave que realmente están en uso con respecto al tamaño del espacio de direcciones

3. El numero de registros que pueden almacenarse en una dirección dad sin causar una colisión

4. La técnica usada para resolver el problema de las colisiones

Las funciones hash más comunes son:

• Residuo de la división

• Medio del

HASHING POR RESIDUO DE LA DIVISIÓN

La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor).

Mientras que el valor calculado real de una dirección relativa, dados tanto un valor de llave como el divisor, es directo; la elección del divisor apropiado puede no ser tan simple. Existen varios factores que deben considerarse para seleccionar el divisor:

1.- El rango de valores que resultan de la operación "llave % divisor", va desde cero hasta el divisor 1. Luego, el divisor determina el tamaño del espacio de direcciones relativas. Si se sabe que el archivo va a contener por lo menos n registros, entonces tendremos que hacer que divisor > n, suponiendo que solamente un registro puede ser almacenado en una dirección relativa dada.

2.- El divisor deberá seleccionarse de tal forma que la probabilidad de colisión sea minimizada. ¿Cómo escoger este número? Mediante investigaciones se ha demostrado que los divisores que son números pares tienden a comportase pobremente, especialmente con los conjuntos de valores de llave que son predominantemente impares. Algunas investigaciones sugieren que el divisor deberá ser un número primo. Sin embargo, otras sugieren que los divisores no primos trabajan también como los divisores primos, siempre y cuando los divisores no primos no contengan ningún factor primo menor de 20. Lo más común es elegir el número primo más próximo al total de direcciones.

HASHING POR MEDIO DEL CUADRADO

En esta técnica, la llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa. Si se desea una dirección de n dígitos, entonces los dígitos se truncan en ambos extremos de la llave elevada al cuadrado, tomando n dígitos intermedios. Las mismas posiciones de n dígitos deben extraerse para cada llave.

HASHING POR PLIEGUE

En esta técnica el valor de la llave es particionada en varias partes, cada una de las cuales (excepto la ultima) tiene el mismo número de dígitos que tiene la dirección relativa objetivo. Estas particiones son después plegadas una sobre otra y sumadas. El resultado, es la dirección relativa. Igual que para el método del medio del cuadrado, el tamaño del espacio de direcciones relativas es una potencia de 10.

MÉTODOS PARA RESOLVER EL PROBLEMA DE LAS COLISIONES

Considere las llaves K1 y K2 que son sinónimas para la función hash R. Si K1 es almacenada primero en el archivo y su dirección es R (K1), entonces se dice que K1 está almacenado en su dirección de origen.

Existen dos métodos básicos para determinar donde debe ser alojado K2:

• Direccionamiento abierto.- Se encuentra entre dirección de origen para K2 dentro del archivo.

• Separación de desborde (Área de desborde).- Se encuentra una dirección para K2 fuera del área principal del archivo, en un área especial de desborde, que es utilizada exclusivamente para almacenar registro que no pueden ser asignados en su dirección de origen

Los métodos más conocidos para resolver colisiones son:

Sondeo lineal

Que es una técnica de direccionamiento abierto. Este es un proceso de búsqueda secuencial desde la dirección de origen para encontrar la siguiente localidad vacía. Esta técnica es también conocida como método de desbordamiento consecutivo.

Para almacenar un registro por Hashing con sondeo lineal, la dirección no debe caer fuera del límite del

...