Búsqueda


CONCEPTOS GENERALES
Un algoritmo de búsqueda  recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente.

Complejidad computacional
Si la solución se encuentra en el nivel n, y la cantidad máxima de hijos de un nodo es i, habrá que expandir, en el peor de los casos, la cantidad de nodos de un árbol de orden i y de altura n

Por lo tanto, tanto el tiempo de procesamiento como el requerimiento de memoria tendrán un orden exponencial, tanto si evita o no expansiones repetidas.

Ventajas y desventajas
Expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, parta obtener todas las soluciones posibles.
La desventaja principal es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros i y n del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables.

Búsqueda en profundidad
Un algoritmo de búsqueda en profundidad recorre todos los nodos de un árbol de manera ordenada, pero no uniforme. Consiste en ir expandiendo cada uno de los nodos a medida que los encuentra, empezando siempre por el primer nodo hijo no visitado del nodo actual; cuando ya no quedan más nodos hijos que visitar en el actual, regresa (backtracking), y el padre del nodo pasa a ser el nodo actual. El criterio de camino agotado debe ser elegido cuidadosamente, de manera de evitar la expansión indefinida de nodos. Asimismo, para garantizar la convergencia, en muchos casos debe evitarse la expansión de nodos repetidos, al menos en un mismo camino.

Ventajas y desventajas
Expandir un camino hasta su máxima profundidad puede ser útil para acotar la solución en problemas de optimización. Esto es, si se ha encontrado una solución posible con determinada valoración, no se admitirá expandir nodos con una valoración peor, y así el algoritmo puede ir eliminando ramas sin la carga de procesamiento de recorrerlas. Además, el requerimiento de memoria es limitado, aun si se garantiza que no cicle, ya que sólo hace falta guardar los datos de la rama actual.

Complejidad computacional
La cantidad mínima de nodos a ser expandidos para garantizar la mejor solución es la misma que en la búsqueda en anchura. La diferencia es que en este caso no tendremos certeza de haber encontrado la mejor solución hasta que se hayan expandido todas las ramas hasta el nivel de la mejor solución encontrada (siempre hablando de problemas con costo uniforme), y, aunque el problema tenga la mejor solución en un nivel n, el algoritmo podría explorar por otra rama hasta una profundidad mucho mayor, incluso indefinidamente, por lo cual la complejidad computacional en el peor de los casos está determinada por la profundidad a la cual se encuentra la solución más costosa de todas las ramas.

Búsqueda en profundidad iterativa
Un algoritmo de búsqueda en profundidad iterativa recorre los nodos de un árbol en profundidad, pero con un valor de profundidad restringido, que aumentará en cada iteración. Esto evita el riesgo de internarse indefinidamente en una rama no finita, y evita también la necesidad de guardar pista de todos los nodos expandidos (sólo hace falta guardar los de la rama actual).

Ventajas y desventajas
La búsqueda en profundidad iterativa aprovecha ventajas de la búsqueda en anchura y de la búsqueda en profundidad:
  • El requerimiento limitado de memoria.
  • La uniformidad al expandir los nodos, que garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna.

Complejidad computacional
La complejidad temporal para el caso peor es igual a la cantidad máxima de nodos generados hasta una profundidad d (profundidad de la solución con menor profundidad). 

Búsqueda de costo fijo
Un algoritmo de búsqueda de costo fijo tiene asociada una función de costo que se aplica cada nodo, que representará el costo del mejor camino conocido para llegar desde el nodo inicial hasta el nodo en cuestión. El algoritmo de optimización deberá obtener el mejor camino entre el nodo inicial y un nodo caracterizado como el nodo de destino. En cada iteración, la expansión a realizar será la del nodo cuyo costo resulte menor, excepto si éste fuera una solución, en cuyo caso, se tratará de la solución óptima, por no haber ningún nodo con menor costo que pueda expandirse para encontrar una solución mejor. Si el costo de los movimientos es uniforme, la búsqueda seguirá el mismo orden de expansiones que la búsqueda en anchura .

La función de costo
La función de costo de un nodo representa el costo del mejor camino conocido para llegar desde el nodo inicial hasta el nodo. Para el nodo inicial deberá valer 0.


Búsqueda heurística
El nodo que más conviene expandir es el nodo a través del cual pasa el camino con menor costo. Sería útil contar con la información del costo total del camino que significaría atravesar cada nodo. La búsqueda de costo fijo estima este valor con el costo parcial de llegar a este nodo. En muchos casos, esto no es suficiente. No se puede contar con el valor exacto, esto implicaría tener el problema resuelto. Lo que puede hacerse es estimar el costo desde el nodo actual hasta el nodo final, de manera de expandir primero el nodo a través del cual se estime que se llegará a la solución con costo óptimo.

La función de costo
La función de costo es equivalente a la función de costo en la búsqueda de costo fijo.

La función heurística
La función heurística debe estimar la función de costo desde el nodo actual hasta el nodo objetivo. Debe ser optimista, ya que si la estimación fuera superior al valor real, un nodo que llega a la solución óptima puede quedar excluido de la búsqueda. Mientras más se ajuste la heurística al valor real, se expandirán menos nodos innecesariamente.

Complejidad computacional
Para la búsqueda A*, la complejidad temporal y espacial para el caso peor (h() = cte. = 0) es la misma que la complejidad de la búsqueda de costo uniforme; esto es evidente ya que en el caso peor, la función heurística devuelve siempre 0, haciendo que la búsqueda sea en todo sentido igual a la búsqueda de costo fijo.

Implementación
El algoritmo de búsqueda genérico
Para implementar tanto la búsqueda en profundidad, como la búsqueda en anchura, la de costo fijo y la heurística, puede utilizarse un algoritmo genérico:
1.        Colocar el nodo inicial en la lista abierta.
2.        Elegir el próximo elemento de la lista abierta a extraer, y realizar la extracción.
3.        Si se corresponde con un estado final, devolver el elemento o la secuencia de acciones correspondiente, si no, continuar.
4.        Explandirlo, colocando los descendientes que correspondan en la lista abierta.
5.        Colocarlo en la lista cerrada y volver a 2.
De las características de la estructura de datos utilizada como lista abierta, dependerán las características del algoritmo:
Si la estructura es una pila, el algoritmo elegirá siempre el último nodo generado, y a partir de ese nodo generará nuevos nodos, que serán agregados a la pila, y el primero será elegido, y así sucesivamente; es decir que la búsqueda será en profundidad.
Si la estructura es una cola, los nodos se expandirán en el orden que se generen, de manera que todos los nodos de un nivel deberán ser expandidos antes de comenzar a expandir los del siguiente; la búsqueda será en anchura.
Si la estructura es una cola de prioridad, y la función de ordenamiento es la función costo, de manera que el elemento elegido sea siempre el de menor costo, la búsqueda será de costo uniforme. Si la función de ordenamiento combina la función de costo con una función heurística, la búsqueda será heurística.

BÚSQUEDA SECUENCIAL
La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave. Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista. La situación óptima es que el registro buscado sea el primero en ser examinado. El peor caso es cuando las llaves de todos los n registros son comparados con k (lo que se busca). 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.

 
Mejoras en la eficiencia de la búsqueda secuencial
1)Muestreo de acceso
Este método consiste en observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas.
2)Movimiento hacia el frente
Este esquema consiste en que la lista de registros se reorganicen dinámicamente. Con este método, cada vez que búsqueda de una llave sea exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que el.
3)Transposición
Este es otro esquema de reorganización dinámica que consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente se intercambia con el anterior. Con este procedimiento, entre mas accesos tenga el registro, mas rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere mas tiempo de actividad para reorganizar al conjunto de registros . Una ventaja de método de transposición es que no permite que el requerimiento aislado de un registro, cambie de posición todo el conjunto de registros. De hecho, un registro debe ganar poco a poco su derecho a alcanzar el inicio de la lista.
4)Ordenamiento
Una forma de reducir el numero de comparaciones esperadas cuando hay una significativa frecuencia de búsqueda sin éxito es la de ordenar los registros en base al valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como una lista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista.

BÚSQUEDA BINARIA
Búsqueda binaria o dicotómica: Para utilizar este algoritmo, el array debe estar ordenado. La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo. Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos:
Se toma el elemento central y se divide el array en dos: {1,2,3,4}−5-{6,7,8,9} Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4} Se vuelve a dividir el array en dos: {1}−2-{3,4} Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4} Se vuelve a dividir en dos: {}−3-{4} Como el elemento buscado coincide con el central, lo hemos encontrado.
Si al final de la búsqueda todavía no lo hemos encontrado, y el subarray a dividir está vacio {}, el elemento no se encuentra en el array.
La implementación sería:

int desde,hasta,medio,elemento,posicion; // desde y
      // hasta indican los límites del array que se está mirando.
int array[N];
// Dar valor a elemento.
for(desde=0,hasta=N-1;desde<=hasta;) {
   if(desde==hasta) // si el array sólo tiene un elemento:
   {
      if(array[desde]==elemento) // si es la solución:
         posicion=desde; // darle el valor.
      else // si no es el valor:
         posicion=−1; // no está en el array.
      break; // Salir del bucle.
    }
   medio=(desde+hasta)/2; // Divide el array en dos.
   if(array[medio]==elemento) // Si coincide con el central:
   {
      posicion=medio; // ese es la solución
      break; // y sale del bucle.
    }
   else if(array[medio]>elemento) // si es menor:
      hasta=medio-1; // elige el array izquierda.
   else // y si es mayor:
      desde=medio+1; // elige el array de la derecha.
 }

En general, este método realiza log(2,N+1) comparaciones antes de encontrar el elemento, o antes de descubrir que no está. Este número es muy inferior que el necesario para la búsqueda lineal para casos grandes.
Si la tabla de números está ordenada, por ejemplo, en orden creciente, es posible utilizar para la búsqueda un algoritmo más eficiente que se basa en un concepto muy utilizado en la programación: dividir para vencer.
Si está ordenada la tabla y miramos el número situado en la mitad para ver si es mayor o menor que el número buscado (o con suerte igual), sabremos si la búsqueda ha de proceder en la subtabla con la mitad de tamaño que está antes o después de la mitad. Si se repite recursivamente el algoritmo al final o bien encontraremos el número sobre una tabla de un sólo elemento o estaremos seguros de que no se encuentra allí.
Este método permite buscar un valor en una matriz que se esta ordenando ascendentemente utilizando el algoritmo de búsqueda binaria. Se trata de un algoritmo muy eficiente en cuanto el tiempo requerido para realizar una búsqueda es muy pequeño. La sintaxis expresada de forma genérica para realizar este método es la siguiente:
Int BinarySearch ([ ] m. tipo clave)
Donde m representa la matriz, clave es el valor que se desea buscar del mismo tipo que los elementos de la matriz, tipo es cualquier tipo de datos de los siguientes: objet, string, byte, char, short, int, long, flota, double, etc.
La búsqueda binaria sólo se puede implementar si el arreglo está ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector:
int vector[10] = {2,4,6,8,10,12,14,16,18,20};
La clave que queremos buscar es 6. El algoritmo funciona de la siguiente manera
1.        Se determinan un índice arriba y un índice abajo, Iarriba=0 e Iabajo=10 respectivamente.
2.        Se determina un índice central, Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 5.
3.        Evaluamos si vector[Icentro] es igual a la clave de búsqueda, si es igual ya encontramos la clave y devolvemos Icentro.
4.        Si son distintos, evaluamos si vector[Icentro] es mayor o menor que la clave, como el arreglo está ordenado al hacer esto ya podemos descartar una mitad del arreglo asegurándonos que en esa mitad no está la clave que buscamos. En nuestro caso vector[Icentro] = 5 < 6, entonces la parte del arreglo vector[0…5] ya puede descartarse.
5.        Reasignamos Iarriba o Iabajo para obtener la nueva parte del arreglo en donde queremos buscar. Iarriba, queda igual ya que sigue siendo el tope. Iabajo lo tenemos que subir hasta 6, entonces quedaría Iarriba = 10, Iabajo = 6. Y volvemos al paso 2.
CODIGO

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

namespace busquedabinaria
{
    public partial class Form1 : Form
    {
        public int[] num = new int[100];
        public int x;
        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            int Primero = 0, Ultimo = N - 1,Centro = 0;
            if (textBox1 != 0)
            {
                while ((Primero <= Ultimo) && (Encontrado == false))
                {
                    Centro = (Primero + Ultimo) / 2;
                    if ( num[x] == textBox1)
                        Encontrado = true;
                    else
                    {
                        if (num[x] > textBox1)
                            Ultimo = Centro - 1;
                        else
                            Primero = Centro + 1;
                    }
                }
            }
        }

        private void button3_Click(object sender, EventArgs e)
        {
            num[x] = textBox1;
        }

        private void label2_Click(object sender, EventArgs e)
        {
            if (Encontrado == false)
                label2 = "el numero fue encontrado";
            else
                label2 = "el numero no fue encontrado";
        }
    }


BÚSQUEDA SECUENCIAL INTERNA

Es la forma mas simple de los metodos de busqueda, inicia el principio de la lista y va buscando el registro deseado en forma secuencial hasta que lo encuentra o hasta que ha llegado al fin de la lista y entonces termina. Este metodo es aplicable a tablas, arreglos, listas, archivos, etc. que se encuentran en desorden.
Algoritmo
1.- Empezar con el primer elemento de la lista e inicializar la variable que servira de bandera.
2.- Efectuar la busqueda mientras hay elementos en la lista y el valor de la llave no se ha encontrado.
3.- Verificar si se encontro el elemento objeto de la busqueda.
4.- fin
Consiste en recorrer y examinar cada uno de los elementos del array hasta encontrar el o los elementos buscados, o hasta que se han mirado todos los elementos del array.

for(i=j=0;i<N;i++)
   if(array[i]==elemento)
   {
      solucion[j]=i;
      j++;
    }
Este algoritmo se puede optimizar cuando el array está ordenado, en cuyo caso la condición de salida cambiaría a:
for(i=j=0;array[i]⇐elemento;i++)
o cuando sólo interesa conocer la primera ocurrencia del elemento en el array:
for(i=0;i<N;i++)
   if(array[i]==elemento)
      break;
En este último caso, cuando sólo interesa la primera posición, se puede utilizar un centinela, esto es, dar a la posición siguiente al último elemento de array el valor del elemento, para estar seguro de que se encuentra el elemento, y no tener que comprobar a cada paso si seguimos buscando dentro de los límites del array:
array[N]=elemento;
for(i=0;;i++)
   if(array[i]==elemento)
      break;
Si al acabar el bucle, i vale N es que no se encontraba el elemento. El número medio de comparaciones que hay que hacer antes de encontrar el elemento buscado es de (N+1)/2.


CODIGO
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

namespace WindowsApplication2
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        public static int[] arreglo = new int[10];
        private void cmdLista_Click(object sender, EventArgs e)
        {
            Random num = new Random();
            int top, izq;
            top = 5; izq = 3;
            for (int i = 0; i < arreglo.Length; i++)
            {
                arreglo[i] = num.Next(100, 999);Aqui se genera el arreglo.
                listBox1.Items.Add(arreglo[i]);
                top++;
                if (top >= 25)
                {
                    izq = izq + 15;
                    top = 5;
                }
            }
        }

        private void cmdBuscar_Click(object sender, EventArgs e)
        {
            int bus, j,con=0;

            bus = System.Int32.Parse(txtBuscado.Text);

            bool encontrado = false;

            j = 0;
            encontrado = false;
            while (j < arreglo.Length && encontrado == false)
            {
                if (bus == arreglo[j])
                    encontrado = true;
                else
                    j++;
            }
            if (encontrado == false)
            {
                lblMensaje.Text = ("No Esta El Elemento " + bus + " En El Arreglo");
            }
            else
            {
                con = j + 1;
                lblMensaje.Text = ("El Elemento " + bus + " Está En La Posición " + con);
            } 
        }
    }
}

BÚSQUEDA POR HASH
 
Hasta ahora las técnicas de localización de registros vistas, emplean un proceso de búsqueda que implica cierto tiempo y esfuerzo. El siguiente método nos permite encontrar directamente el registro buscado. 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 calculo 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 mas 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.
 
Ventaja
1.        Se pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar
2.        Se logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones
3.        No se requiere almacenamiento adicional para los índices.
Desventajas
1.        No pueden usarse registros de longitud variable
2.        El archivo no esta clasificado
3.        No permite llaves repetidas
4.        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 mas comunes son:
·         Residuo de la división
·         Medio del cuadrado
·         Pliegue
 
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. ¿Como escoger este numero? 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 numero 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 mas común es elegir el número primo mas próximo al total de direcciones.
Ejemplo:
 
Independientemente de que tan bueno sea el divisor, cuando el espacio de direcciones de un archivo esta completamente lleno, la probabilidad de colisión crece dramáticamente. La saturación de archivo de mide mediante su factor de carga, el cual se define como la relación del numero de registros en el archivo contra el numero de registros que el archivo podría contener si estuviese completamente lleno. Todas las funciones hash comienzan a trabajar probablemente cuando el archivo esta casi lleno. Por lo general el máximo factor de carga que puede tolerarse en un archivo para un rendimiento razonable es de entre el 70 % y 80 %.
 
 
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.
 
Ejemplo:
 
    Utilizando esta función hashing el tamaño del archivo resultante es de 10n donde n es el numero de dígitos extraídos de los valores de la llave elevada al cuadrado.
 
 
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 numero 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.
 
Ejemplo:
 
COMPARACIÓN ENTRE LAS FUNCIONES HASH
 
Aunque alguna otra técnica pueda desempeñarse mejor en situaciones particulares, la técnica del residuo de la división proporciona el mejor desempeño. Ninguna función hash se desempeña siempre mejor que las otras. El método del medio del cuadrado puede aplicarse en archivos con factores de cargas bastantes bajas para dar generalmente un buen desempeño. El método de pliegues puede ser la técnica mas fácil de calcular pero produce resultados bastante erráticos, a menos que la longitud de la llave se aproximadamente igual a la longitud de la dirección.
Si la distribución de los valores de llaves no es conocida, entonces el método del residuo de la división es preferible. Note que el hashing puede ser aplicado a llaves no numéricas. Las posiciones de ordenamiento de secuencia de los caracteres en un valor de llave pueden ser utilizadas como sus equivalentes "numéricos". Alternativamente, el algoritmo hash actúa sobre las representaciones binarias de los caracteres.
Todas las funciones hash presentadas tienen destinado un espacio de tamaño fijo. Aumentar el tamaño del archivo relativo creado al usar una de estas funciones, implica cambiar la función hash, para que se refiera a un espacio mayor y volver a cargar el nuevo archivo.
 
 
 
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 esta 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 (Area 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 mas 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 limite del archivo, En lugar de terminar cuando el limite del espacio de dirección se alcanza, se regresa al inicio del espacio y sondeamos desde ahí. Por lo que debe ser posible detectar si la dirección base ha sido encontrada de nuevo, lo cual indica que el archivo esta lleno y no hay espacio para la llave.
Para la búsqueda de un registro por hashing con sondeo lineal, los valores de llave de los registros encontrados en la dirección de origen, y en las direcciones alcanzadas con el sondeo lineal, deberá compararse con el valor de la llave buscada, para determinar si el registro objetivo ha sido localizado o no. El sondeo lineal puede usarse para cualquier técnica de hashing. Si se emplea sondeo lineal para almacenar registros, también deberá emplearse para recuperarlos.

Doble hashing
 
En esta técnica se aplica una segunda función hash para combinar la llave original con el resultado del primer hash. El resultado del segundo hash puede situarse dentro del mismo archivo o en un archivo de sobreflujo independiente; de cualquier modo, será necesario algún método de solución si ocurren colisiones durante el segundo hash. 
La ventaja del método de separación de desborde es que reduce la situación de una doble colisión, la cual puede ocurrir con el método de direccionamiento abierto, en el cual un registro que no esta almacenado en su dirección de origen desplazara a otro registro, el que después buscará su dirección de origen. Esto puede evitarse con direccionamiento abierto, simplemente moviendo el registro extraño a otra localidad y almacenando al nuevo registro en la dirección de origen ahora vacía.
Puede ser aplicado como cualquier direccionamiento abierto o técnica de separación de desborde.
Para ambas métodos para la solución de colisiones existen técnicas para mejorar su desempeño como:
 
 
1.- Encadenamiento de sinónimos

Una buena manera de mejorar la eficiencia de un archivo que utiliza el calculo de direcciones, sin directorio auxiliar para guiar la recuperación de registros, es el encadenamiento de sinónimos. Mantener una lista ligada de registros, con la misma dirección de origen, no reduce el numero de colisiones, pero reduce los tiempos de acceso para recuperar los registros que no se encuentran en su localidad de origen. El encadenamiento de sinónimos puede emplearse con cualquier técnica de solución de colisiones.
Cuando un registro debe ser recuperado del archivo, solo los sinónimos de la llave objetivo son accesados.
 
2.- Direccionamiento por cubetas
 
Otro enfoque para resolver el problema de las colisiones es asignar bloques de espacio (cubetas), que pueden acomodar ocurrencias múltiples de registros, en lugar de asignar celdas individuales a registros. Cuando una cubeta es desbordada, alguna nueva localización deberá ser encontrada para el registro. Los métodos para el problema de sobrecupo son básicamente los mismo que los métodos para resolver colisiones.
 
 
COMPARACIÓN ENTRE SONDEO LINEAL Y DOBLE HASHING
 
    De ambos métodos resultan distribuciones diferentes de sinónimos en un archivo relativo. Para aquellos casos en que el factor de carga es bajo (< 0.5), el sondeo lineal tiende a agrupar los sinónimos, mientras que el doble hashing tiende a dispersar los sinónimos mas ampliamente a travéz del espacio de direcciones.
 
    El doble hashing tiende a comportarse casi también como el sondeo lineal con factores de carga pequeños (< 0.5), pero actúa un poco mejor para factores de carga mayores. Con un factor de carga > 80 %, el sondeo lineal por lo general resulta tener un comportamiento terrible, mientras que el doble hashing es bastante tolerable para búsquedas exitosas pero no así en búsquedas no exitosas.

Suscribirse a: Entradas (Atom)