TRABAJO INVESTIGATIVOBÚSQUEDAS INTERNAS

CATALINA MARÍA HERNÁNDEZ RUIZ20112020083

KAREN VANESSA ANGULO SOGAMOSO20112020055

UNIVERSIDAD DISTRITAL FRANCISCO JOSÉ DE CALDASINGENIERÍA DE SISTEMAS

CIENCIAS DE LA COMPUTACIÓN IIBOGOTÁ, 19 DE FEBRERO DE 2014

TABLA DE CONTENIDO

Pág.

INTRODUCCIÓN 3

1. OBJETIVO GENERAL 4

2. OBJETIVOS ESPECÍFICOS 4

3. BÚSQUEDA 5

3.1. BÚSQUEDAS INTERNAS 53.1.1. MÉTODOS 5

3.1.1.1 BÚSQUEDA SECUENCIAL 53.1.1.1.1 ALGORITMO 63.1.1.1.2. ANÁLISIS DE LA BÚSQUEDA SECUENCIAL 73.1.1.1.3. PRINCIPALES APLICACIONES 7

3.1.1.2. BÚSQUEDA BINARIA 83.1.1.2.1. ALGORITMO 83.1.1.2.2. ANÁLISIS DE LA BÚSQUEDA BINARIA 93.1.1.2.3. PRINCIPALES APLICACIONES 10

3.1.1.3. BÚSQUEDA POR TRANSFORMACIÓN DE 11 CLAVES3.1.1.3.1. ANÁLISIS DEL MÉTODO POR 11 TRANSFORMACIÓN DE CLAVES 3.1.1.3.2. FUNCIÓN HASH POR MÓDULO: DIVISIÓN 123.1.1.3.3. FUNCIÓN HASH CUADRADO 133.1.1.3.4. FUNCIÓN HASH POR PLEGAMIENTO 133.1.1.3.5. FUNCIÓN HASH POR TRUNCAMIENTO 143.1.1.3.6. SOLUCIÓN DE COLISIONES 15

3.1.1.3.6.1. REASIGNACIÓN 163.1.1.3.6.1.1. PRUEBA LINEAL 163.1.1.3.6.1.2. PRUEBA CUADRÁTICA 17 3.1.1.3.6.1.3. DOBLE DIRECCIÓN HASH 18

3.1.1.3.6.2. ARREGLOS ANIDADOS 193.1.1.3.6.3. ENCADENAMIENTO 20

4. CONCLUSIONES 22

5. BIBLIOGRAFÍA 22

2

INTRODUCCIÓN

En las diferentes estructuras de datos es necesario acceder y modificar la información, por lo cual cuentan con diversas operaciones diseñadas para ello. Uno de estos procesos son las búsquedas, que permiten encontrar datos, claves, registros almacenados.

El siguiente trabajo aborda esta temática, profundizando en uno de los tipos de búsquedas, las internas, sus métodos, características y condiciones necesarias para su realización y aplicación.

3

1. OBJETIVO GENERAL

Investigar sobre las búsquedas internas que se pueden aplicar en las diferentes estructuras de datos.

2. OBJETIVOS ESPECÍFICOS

Comprender las diferencias básicas entre los métodos de búsquedas internas, sus características y condiciones de aplicación.

Entender los diferentes procedimientos que hacen parte de cada operación de los métodos de búsquedas internas.

Realizar algunos ejemplos que evidencien la forma que se realizan las búsquedas internas, comprendiendo sus ventajas y desventajas en la aplicación.

4

3. BÚSQUEDA

Es una operación que permite recuperar información previamente almacenada, su resultado puede ser de éxito al encontrar el dato o de fracaso si no. Se puede realzar sobre elementos ordenados o desordenados.

Las búsquedas se pueden realizar a nivel interno o externo

3.1. BÚSQUEDAS INTERNAS

Son aquellas que se realizan sobre elementos que se encuentran en memoria principal de la máquina. Es común en estructuras de datos estáticas como arreglos, y dinámicas como árboles y listas.

3.1.1. Métodos

Los métodos de búsqueda interna más importantes son:

- Búsqueda secuencial- Búsqueda binaria- Búsqueda por transformación de claves o hash

o Módulo

o Cuadrado

o Plegamiento

o Truncamiento

3.1.1.1 Búsqueda secuencial:

También se le conoce como búsqueda lineal. Es la forma más simple de los métodos de búsqueda, consiste en revisar elemento tras elemento hasta encontrar

5

el dato buscado, o llegar al final del conjunto de datos disponibles. Este método es aplicable a tablas, arreglos, listas, archivos, etc.

3.1.1.1.1 Algoritmo:

1.- Empezar con el primer elemento de la lista e inicializar la variable que servirá de localizador.

2.- Efectuar la búsqueda mientras hay elementos en la lista y el valor de la clave no se ha encontrado.

3.- Verificar si se encontró el elemento objeto de la búsqueda.

Figura 1: Diagrama de flujo Método secuencial

6

3.1.1.1.2. Análisis de la Búsqueda Secuencial:

La situación óptima es que la clave buscada sea la primera en ser examinada. El peor caso es cuando la información de todas las claves es comparada con la buscada, es decir el fin de la estructura de datos. Mientras que el caso promedio es n/2 comparaciones.

Este método de búsqueda es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas. Si los valores de la llave no son únicos, para encontrar todos los registros con una llave particular, se requiere buscar en toda la lista.

Además, a continuación se presenta para los distintos valores de N, los numero mínimo, mediano y máximo de comparaciones que se requieren para buscar secuencialmente un elemento en un arreglo o lista ligada

Cmin=1Cmed=(1+n)2

Cmax=N

Ejemplo. 

Si tenemos una estructura con los elementos 5, 8, 3, 2, 9, 5, 7, 0, 5, 1 y estamos buscando el número 5, el resultado de la búsqueda nos mostraría las posiciones 0, 5 y 8 y el proceso terminaría al llegar al número 1 que es el último de la lista de elementos.

Elementos 5 8 3 2 9 5 7 0 5 1

Posiciones 0 1 2 3 4 5 6 7 8 9

Posiciones dondeencontró el número

5

√ × × × × √ × × √ ×

3.1.1.1.3. Principales Aplicaciones:

Los archivos secuenciales son típicamente utilizados en aplicaciones de proceso de lotes Y son óptimos para dichas aplicaciones si se procesan todos los registros. La organización secuencias de archivos es la única que es fácil de usar tanto en disco como en cinta.

7

Un ejemplo claro para utilizar esta técnica de búsqueda es cuando se tiene una base de datos no muy grande en un negocio pequeño donde los registros más usados son llamados con frecuencia, es aquí donde esta técnico es fuerte, ya que se aplica a un patrón de búsqueda pequeño, sencillo y manejable; es decir como si fuera una descripción, es uno tras otro.

Ejemplo:

Número de cliente, nombre, apellido, dirección, corp.

3.1.2.2. Búsqueda Binaria

Consiste en dividir el intervalo de búsqueda en dos partes, comparando el elemento buscado con el que ocupa la posición central en el arreglo. Para el caso de que no fueran iguales se redefinen los extremos del intervalo, según el elemento central sea mayor o menor que el elemento buscado, disminuyendo de esta forma el espacio de búsqueda. El proceso concluye cuando el elemento es encontrado, o cuando el intervalo de búsqueda se anula, es vacío.

Este método funciona exclusivamente para arreglos ordenados, no se pude utilizar con listas, porque no podríamos retroceder para encontrar intervalos de búsqueda, ni con arreglos desordenados.

Con cada iteración del método el espacio de búsqueda se reduce a la mitad, lo que quiere decir que el número de comparaciones se reduce notablemente.

3.1.2.2.1. Algoritmo:

1. Se compara la llave buscada con la llave localizada en el centro del arreglo.

2. Si la llave analizada corresponde a la buscada se finaliza la búsqueda, el dato ha sido encontrado.

Si no

1. Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.

8

2. El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero, lo cual implica que el valor de la llave buscada no está en la lista.

3.1.1.2.2. Análisis de la Búsqueda Binaria

Para establecer la complejidad de la búsqueda binaria es necesario establecer los casos más favorables y desfavorables que se pudiesen presentar en el proceso de búsqueda.

El primero sucede cuando el elemento buscado se encuentra en el centro, en dicho caso solo se hará una comparación.

El segundo sucede cuando elemento no se encuentra en el arreglo; entonces se harán aproximadamente log 2(n) comparaciones, ya que con cada comparación el número de elementos en los cuales se debe buscar se reduce en un factor de 2

El esfuerzo promedio es de ½log 2(n).

Sabiendo esto, en las siguientes formulas se determinan los números mínimo, mediano y máximo de comparaciones que se deben realizar cuando se utiliza este tipo de búsqueda.

Cmin=1Cmed=(1+ log2 (N ) )

2Cmax=log2N

De esta forma, se evidencia que método de búsqueda binaria es más eficiente que el método de búsqueda secuencial. Además, la diferencia se hace significativa conforme más grande sea el tamaño del arreglo.

Cabe recalcar que el tiempo de búsqueda en este tipo de algoritmo es proporcional a su número de componentes. Es decir a mayor número de elementos se deben realizar mayor número de comparaciones.

Algunas de sus ventajas son:

Es un método eficiente siempre que el vector esté ordenado. En la práctica, esto suele suceder, pero no siempre. Por esta razón la búsqueda binaria exige una ordenación previa del archivo.

Proporciona un medio para reducir el tiempo requerido para buscar en una lista. Este método, sin embargo, exige que los datos estén ordenados.

9

Es más rápido por su recursividad, su mayor ventaja es con los archivos extensos.

El código del procedimiento de esta búsqueda es corto en comparación con las demás técnicas de búsqueda.

En esencia, con una sola comparación eliminamos la mitad de la tabla; este es el método más eficiente de buscar en una lista ordenada sin emplear tablas o índices adicionales.

Ejemplo. 

Si tenemos una estructura ordenada 0, 1, 2, 3, 5, 5, 5, 7, 8, 9 y estamos buscando el número 5, el resultado de la búsqueda nos mostraría la posicione  4 y el proceso terminaría ya que el elemento buscado no es diferente al que está en la posición central.

Elementos 0 1 2 3 5 5 5 7 8 9

Posiciones 0 1 2 3 4 5 6 7 8 9

Posiciones dondeencontró el número

5

i √ F

3.1.1.2.3. Principales aplicaciones:

Es común en la búsqueda para arboles binarios ordenados

Se distinguen 2 casos triviales con solución directa: árbol vacío (elemento no encontrado) o raíz del árbol. El segundo se da cuando es necesario aplicar búsqueda binaria para encontrar el dato, partiendo el árbol en subárboles hasta encontrar la clave.

3.1.1.3. Búsqueda por transformación de claves:

También conocida hash, permite aumentar la velocidad de búsqueda sin necesidad de tener los elementos ordenados. Cuenta con la ventaja de que el tiempo de búsqueda es independiente del número de componentes del arreglo.

El método de transformación de claves permite localizar el dato en forma directa, además trabaja utilizando una función que convierte una clave dada en dirección (índice) dentro del arreglo.

10

Dirección ← H (clave)

La función hash (H) aplicada a la clave genera un índice del arreglo que permite acceder directamente al elemento. El caso más trivial se presenta cuando las claves son números enteros consecutivos.

La función hash permitirá transformar la clave para obtener una dirección apropiada. La asignación deberá ser la más uniforme posible. Es decir, debe generar posiciones diferentes dadas dos claves también diferentes.

Si no se generan posiciones diferentes dadas dos claves también diferentes, hay una colisión, que se define como la asignación de una misma dirección a dos o más claves distintas.

Para trabajar con este método de búsqueda se debe seleccionar previamente:

- Una función hash que sea fácil de calcular y que distribuya uniformemente las claves.

- Un método para resolver las colisiones. Que generara posiciones alternativas si esto se presenta.

Para encontrar la función hash no existe una regla que permita determinar cuál será la función más apropiada para generar un conjunto de claves que aseguren la máxima uniformidad en la distribución de las mismas. Algunas de las funciones hash más utilizadas son las siguientes:

- Función módulo (por división).

- Función cuadrada.

- Función plegamiento.

- Función truncamiento.

3.1.1.3.1. Análisis del método por transformación de claves

Para el análisis de este método es necesario realizar varios cálculos probabilísticos. La dificultad del análisis se debe a que principalmente no sólo interviene la función hash sino también el método utilizado para resolver las colisiones. Por tanto se deben analizar todas las posibles combinaciones que se pueden realizar.

11

Según Lipschutz, la probabilidad de llevar a cabo una búsqueda con éxito (S) y otra sin éxitos (Z) están determinadas por las siguientes formulas:

S ( λ )=[(1+ 1

(1−λ ) )]2

Z ( λ )=[(1+ 1

(1−λ )2 )]2

M= número de elementos del arreglo

N= tamaño del arreglo

λ = factor de ocupación de un arreglo, definido como MN

Nota: Cabe aclarar que estas fórmulas son válidas solamente en casos de funciones hash con el método lineal de solución de colisiones

3.1.1.3.2. Función Hash por Módulo: división

La función hash por módulo o división consiste en tomar el residuo de la división de la clave entre el número de componentes del arreglo (total de elementos de arreglo).

dirección=(clave% total elementos)

Para lograr una mayor uniformidad en la distribución de los elementos, se debe buscar que el valor que se usa en el total de elementos sea un número primo o divisible entre muy pocos números más cercano al tamaño de la estructura.

Ejemplo.

Si tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las direcciones generadas son las siguientes:

dirección=(7259%100 )=59

dirección=(9359%100 )=59

Estos dos casos generan una colisión, ya que los dos números no se pueden asignar dentro de la misma dirección en la estructura, para evitar la colisión, se cambia el valor de 100 por el numero primo más cercano a él, en este caso sería un 97, lo que generaría las siguientes direcciones:

12

dirección=(7259%97 )=81

dirección=(9359%97 )=47

3.1.1.3.3. Función Hash Cuadrado

La función hash cuadrado consiste en elevar al cuadrado la clave y tomar los dígitos centrales como dirección. El número de dígitos que se debe considerar se encuentra determinado por el rango del índice.

Se define la fórmula para la función hash así:

H (K )=dig itoCentrales (K2 )+1

K: la clave del dato a buscar

La suma de la unidad a los dígitos centrales es útil para obtener un valor comprendido entre 1 y N.

Ejemplo.

Si tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las direcciones generadas son las siguientes:

(K 12)=52693081

(K 22)=87590881

Entonces,

H 1 (K )=digitoCentrales (K12 )+1=94

H 2 (K )=digitoCentrales (K22 )+1=91

Como el rango de claves es de 1 a 100 se toman dos dígitos centrales.

3.1.1.3.4. Función Hash por Plegamiento

La función hash por Plegamiento consiste en dividir la clave en partes, tomando igual número de dígitos aunque la última puede tener menos, y operar entre ellas, asignando como dirección los numero menos significativos.

13

Las operaciones entre las partes se pueden realizar por medio de sumas o multiplicaciones.

La función hash por plegamiento se define de la siguiente forma:

H (K )=digmensig ( (d1…d i)+ (d i+1…d j )+…+(d1…dn))+1

K: la clave del dato a buscar

K está formada por los dígitos d1 , d2…dn

Digmensig: dígitos menos significativos.

Se nota que el operador que aparece en la fórmula es operando las partes de la clave es la suma, pero también podría ser la multiplicación.

La suma de la unidad a los dígitos menos significativos es para obtener un valor comprendido entre 1 y N.

Ejemplo.

Si tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las direcciones generadas son las siguientes:

H 1 (K )=digmensig (72+59 )+1=digmensig (131 )+1=32

H 2 (K )=digmensig (93+59 )+1=digmensig (152 )+1=53

Como el rango de claves es de 1 a 100 se toman dos dígitos para las particiones y para la dirección.

3.1.1.3.5. Función Hash por Truncamiento

La función hash por truncamiento consiste en tomar algunos dígitos de la clave y formar con ellos una dirección.

Este es uno de los métodos más sencillos, pero de igual forma es uno de los que menos ofrece uniformidad en la distribución de claves.

La función hash por truncamiento se define de la siguiente forma:

14

H (K )=elegirDigitos ((d1 , d2…dn ))+1

K: la clave del dato a buscar

K está formada por los dígitos d1 , d2…dn

La suma de la unidad a los dígitos seleccionados es indispensable para obtener valores entre 1 y N.

La elección de los dígitos es arbitraria, podrían tomarse los de las posiciones pares o impares para con ellos generar la dirección donde se almacenara la clave, uniendo los dígitos de izquierda a derecha o de derecha a izquierda.

Ejemplo.

Si tenemos un total de 100 elementos y dos claves que sean 7259 y 9359, las direcciones generadas son las siguientes:

H 1 (K )=elegirdigitos (7259 )+1=75+1=76

H 2 (K )=elegirdigitos (9359 )+1=95+1=96

Para este caso se tomaron los dígitos impares y se unieron de izquierda a derecha.

3.1.1.3.6. Solución de colisiones

Un método para la solución de colisiones es tan importante como la función hash, este método debe entrar en operación cuando la función hash asigna la misma dirección a dos o más claves diferentes.

La manera más natural de resolver el problema de las colisiones es reservar una casilla por claves; es decir, aquellas que se correspondan una a una con las posiciones del arreglo. Esta solución tiene un alto costo de memoria. Por lo que se busca un equilibrio entre el uso de memoria y el tiempo de búsqueda.

Por tanto se presentan algunos métodos para la solución de colisiones y se clasifican así:

15

- Reasignación- Arreglos anidados- Encadenamiento.

3.1.1.3.6.1. Reasignación

Existen varios métodos que trabajan bajo el principio de comparación y reasignación de elementos. A continuación se presentan tres de ellos

- Prueba lineal- Prueba cuadrática - Doble dirección hash

3.1.1.3.6.1.1. Prueba lineal

El método de prueba lineal consiste en que una vez se ha detectado la colisión, se recorre el arreglo secuencialmente a partir del punto de la colisión, buscando al elemento. El proceso de búsqueda concluye cuando el elemento es hallado, o cuando se encuentra una posición vacía.

El arreglo se trata como a una estructura circular: el siguiente elemento después del último es el primero.

La principal desventaja de este método es que puede haber un fuerte agrupamiento alrededor de ciertas claves, mientras que otras del arreglo podrían permanecer vacías. Se pierden las ventajas del método hash.

Ejemplo.

Sea V un arreglo unidimensional de 10 elementos. Las claves 25, 43, 56, 35, 54, 13, 80 y 104 fueron asignados según la función hash:

H (K )=(K mod10 )+1

El dato a buscar es igual a 35. Al aplicar la función hash a la clave 35, se obtiene que la dirección (D) es igual a 6. Sin embargo, en esta posición no se encuentra el elemento buscado por lo que se empieza a recorrer secuencialmente el arreglo a partir de la posición (DX) igual a 7. En este caso la búsqueda concluye cuando se encuentra al valor buscado en la posición 8.

16

Figura 2: Solución de colisiones por la prueba lineal.

3.1.1.3.6.1.2. Prueba cuadrática

El método de prueba cuadrática es similar al de prueba lineal, la diferencia radica en que las direcciones alternativas se generan como D+1 , D+4 ,D+9…D+i2. Esta variación permite una mejor distribución de las claves que colisionan.

Ejemplo.

Sea V un arreglo unidimensional de 10 elementos. Las claves 25, 43, 56, 35, 54, 13, 80 y 104 fueron asignados según la función hash:

H (K )=(K mod10 )+1

El dato a buscar es igual a 35. Al aplicar la función hash a la clave 35, se obtiene una dirección (D) igual a 6; sin embargo, en esa dirección no se encuentra el valor buscado. Se calcula posteriormente el DX, como la suma de D+(i∗i), onteniendose de esta forma la dirección 7, el algoritmo de búsqueda concluye cuando se encuentra el valor desea en la décima posición.

17

Figura 3: Solución de colisiones por la prueba cuadrática K = 35

Figura 4: Solución de colisiones por la prueba cuadrática. A) arreglo. B) tabla con H(K)

3.1.1.3.6.1.3. Doble Dirección hash

El método de doble dirección hash consiste en que una vez que se detecta la colisión, se genera otra dirección aplicando la misma función hash a la dirección previamente obtenida. El proceso se finaliza cuando el elemento es hallado o cuando hay una posición vacía.

La función hash que se aplica no necesariamente tiene que ser sobre la misma que originalmente se aplicó a la clave; podría ser sobre cualquier otra.

18

Ejemplo

Sea V un arreglo unidimensional de 10 elementos. Las claves 25, 43, 56, 35, 54, 13, 80 y 104 fueron asignados según la función hash:

H (K )=(K mod10 )+1

Además se define una función H’’ para calcular direcciones alternativas en caso de haber colisión.

H ' (K )=((D+1)mod 10 )+1

Al aplicar la función hash (H) a la clave 13, se obtuvo una dirección (D) igual a 4, como en esta posición no se encuentra el numero buscado, se aplica reiteradamente H’, generando direcciones hasta hallar el valor deseado.

Figura 5: Solución de colisiones por doble dirección hash . A) arreglo. B) tabla con H(K), H’(D), H’(D’), H’(D’’)

19

3.1.1.3.6.2. Arreglos anidados

El método de arreglos anidados consiste en que cada elemento del arreglo tengo otro arreglo, en el cual se almacenen elementos que colisionan. Si bien la solución parece ser sencilla, es claro que resulta ser ineficiente. Al trabajar con arreglos se depende del espacio que haya asignado a éstos, lo cual conduce a un nuevo problema difícil de solucionar: elegir un tamaño adecuado de un arreglo que permita un equilibrio entre el costo de memoria y el número de valores (que colisionan) que pudieran almacenar.

Ejemplo.

Sea V un arreglo unidimensional de 10 elementos. Las claves 25, 43, 56, 35, 54, 13, 80 y 104 fueron asignados según la función hash:

H (K )=(K mod10 )+1

Figura 6: Solución de colisiones con arreglos anidados. A) arreglo. B) tabla con H(K).

20

3.1.1.3.6.3. Encadenamiento

El método de encadenamiento consiste en que cada elemento del arreglo tenga un apuntador a una lista ligada, la cual se ira generando y almacenará los valores que colisionan.

Este método es más eficiente debido a que las listas son estructuras dinámicas.

Cualquiera que sea el número de colisiones que se presenten, se podrán resolver sin inconvenientes.

La desventaja de este método es que se ocupa espacio adicional en la tabla y exige el manejo de listas ligadas. Además, si las listas son demasiado grandes se pierde el acceso directo al método hash.

Ejemplo.

Sea V un arreglo unidimensional de 10 elementos. Las claves 25, 43, 56, 35, 54, 13, 80 y 104 fueron asignados según la función hash:

H (K )=(K mod10 )+1

Una vez se detecta una colisión en cierta posición del arreglo, se debe recorrer la lista asociada a ella hasta encontrar el elemento buscado o llegar a su final.

Figura 7: Solución de colisiones por encadenamiento. A) arreglo. B) tabla con H(K).

21

4. CONCLUSIONES

Se entendieron aspectos básicos de los diferentes métodos de las búsquedas internas, como sus condiciones necesarias para su aplicación, ya sea que la estructura esta ordenada o que tenga que conocerse el tamaño de ella o la cantidad total de registros.

Se explicaron los procesos para llevar a cabo cada una de los procesos de los diferentes métodos de búsquedas internas, es decir se conocieron paso a paso sus algoritmos.

Se comprobó mediante ejemplos la teoría expuesta, de tal manera que el ejercicio práctico evidencio que cada método de búsquedas internas requiere de ciertas condiciones, por lo cual son específicos de cierto tipo de circunstancias específicas, dependiendo de la necesidad y del caso que se presente.

5. BIBLIOGRAFÍA

SEDGEWICK, Robert. Algoritmos en C++. Ediciones Addison – Wesley / Díaz de Santos, 1995.

CAIRÓ, Osvaldo. Estructura de Datos, tercera Edición. Mc Graw Hill.

22