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.

...