jueves, 28 de mayo de 2009
martes, 26 de mayo de 2009
IMPLEMENTACION DE UNA MATRIZ EN UN ARBOL
Introducción
La matriz binaria, en la que el valor ‘1’ representará al color NEGRO y el valor ‘0’ al color BLANCO.
Otra posible representación de la misma imagen consiste en emplear árboles binarios.
Para realizar la conversión entre una representación de la imagen a su equivalente en árbol binario
debemos suponer que la matriz binaria es cuadrada y el rango de la misma es potencia de 2.
En esta representación obtendremos un árbol por cada fila de la matriz binaria, que almacenaremos en una estructura para poder trabajar posteriormente sobre esta representación en futuras operaciones.
El proceso principal de obtención de un árbol binario consiste en ir dividiendo la fila en dos mitades cuando ésta no tenga un valor constante, hasta que lleguemos al caso de encontrar un trozo de tal fila cuyos elementos tengan el mismo valor o bien tengamos únicamente una fila con un único elemento, guandándose en ese caso información pictórica.
La matriz binaria, en la que el valor ‘1’ representará al color NEGRO y el valor ‘0’ al color BLANCO.
Otra posible representación de la misma imagen consiste en emplear árboles binarios.
Para realizar la conversión entre una representación de la imagen a su equivalente en árbol binario
debemos suponer que la matriz binaria es cuadrada y el rango de la misma es potencia de 2.
En esta representación obtendremos un árbol por cada fila de la matriz binaria, que almacenaremos en una estructura para poder trabajar posteriormente sobre esta representación en futuras operaciones.
El proceso principal de obtención de un árbol binario consiste en ir dividiendo la fila en dos mitades cuando ésta no tenga un valor constante, hasta que lleguemos al caso de encontrar un trozo de tal fila cuyos elementos tengan el mismo valor o bien tengamos únicamente una fila con un único elemento, guandándose en ese caso información pictórica.
Ordenación por el método de Shell (ShellSort)
El método se denomina Shell en honor de su inventor Donald Shell.
Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.
Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas.
Esto quedaría así:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Entonces ordenamos cada columna, lo que nos da
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Cuando lo leemos de nuevo como una única lista de números, obtenemos
[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].
SECUENCIA DE ESPACIOS
La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada.
La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción. se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar.
Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.
Por ejemplo, considere una lista de números como [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]. Si comenzamos con un tamaño de paso de 5, podríamos visualizar esto dividiendo la lista de números en una tabla con 5 columnas.
Esto quedaría así:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Entonces ordenamos cada columna, lo que nos da
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
Cuando lo leemos de nuevo como una única lista de números, obtenemos
[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].
SECUENCIA DE ESPACIOS
La secuencia de espacios es una parte integral del algoritmo Shell sort. Cualquier secuencia incremental funcionaría siempre que el último elemento sea 1. El algoritmo comienza realizando un ordenamiento por inserción con espacio, siendo el espacio el primer número en la secuencia de espacios. Continua para realizar un ordenamiento por inserción con espacio para cada número en la secuencia, hasta que termina con un espacio de 1. Cuando el espacio es 1, el ordenamiento por inserción con espacio es simplemente un ordenamiento por inserción ordinario, garantizando que la lista final estará ordenada.
La secuencia de espacios que fue originalmente sugerida por Donald Shell debía comenzar con N / 2 y dividir por la mitad el número hasta alcanzar 1. Aunque esta secuencia proporciona mejoras de rendimiento significativas sobre los algoritmos cuadráticos como el ordenamiento por inserción. se puede cambiar ligeramente para disminuir más el tiempo necesario medio y el del peor caso. El libro de texto de Weiss demuestra que esta secuencia permite un ordenamiento O(n2) del peor caso, si los datos están inicialmente en el vector como (pequeño_1, grande_1, pequeño_2, grande_2, ...) - es decir, la mitad alta de los números están situados, de forma ordenada, en las posiciones con índice par y la mitad baja de los números están situados de la misma manera en las posiciones con índice impar.
Ordenamiento por Método de inserción binaria
Carácteristicas fundamentales:
1.- La secuencia destino donde debe insertarse el nuevo elemento ya esta ordenada.
2.-Búsqueda Binaria para localizar el lugar de inserción.
3.-Desplazar elementos.
4.-Insertar.
Análisis:
Al realizar la búsqueda binaria se divide una longitud L por la mitad un número determinado de veces.
1.- La secuencia destino donde debe insertarse el nuevo elemento ya esta ordenada.
2.-Búsqueda Binaria para localizar el lugar de inserción.
3.-Desplazar elementos.
4.-Insertar.
Análisis:
Al realizar la búsqueda binaria se divide una longitud L por la mitad un número determinado de veces.
METODOS DE BUSQUEDA
BUSQUEDA
La BUSQUEDA , es una operación que permite recuperar datos previamente almacenados. El resultado puede ser exitoso si se encuentra el elemento solicitado, o fracaso, en otro caso.
METODOS DE BUSQUEDA
Los métodos de búsqueda pueden clasificarse según la ubicación de los datos sobre los que se realizara la búsqueda. Existen dos clases:
Métodos de Búsqueda Interna
Métodos de Búsqueda Externa.
METODOS DE BUSQUEDA INTERNA
Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal. Por ejemplo, almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas ligadas y arboles).
Los métodos de búsqueda mas importantes son:
Secuencial o lineal
Binaria
Por transformación de claves
Arboles de búsqueda
METODOS DE BUSQUEDA EXTERNA
Se denomina búsqueda externa cuando todos los elementos se encuentran en memoria secundaria (archivos almacenados en dispositivos tales como cintas y discos magnéticos).
BUSQUEDA SECUENCIAL
Búsqueda secuencial consiste en revisar elemento por elemento hasta encontrar el dato buscado, o hasta llegar al final de la lista de datos disponible.
CARACTERISTICAS
La búsqueda se puede realizar en arreglos desordenados.
El método es totalmente confiable.
El numero de comparaciones es significativa si el arreglo es muy grande.
En arreglos desordenados de N componentes puede suceder que el elemento no se encuentre, por lo tanto se harán N comparaciones al recorrer todo el arreglo
Cantidad mínima de comparaciones es 1.
Cantidad media de comparaciones es (1+N)/2.
Cantidad máxima de comparaciones es N.
DIAGRAMA DE FLUJO (BUSQUEDA SECUENCIAL)
BUSQUEDA BINARIA
La búsqueda binaria 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 éste es el elemento buscado, entonces la búsqueda ha terminado.
En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sub-lista.
CARACTERISTICAS
Sirve únicamente para arreglos ordenados.
Es mas eficiente que el método de búsqueda secuencial, debido a que el numero de comparaciones se reduce a la mitad por cada iteración del método.
Cantidad mínima de comparaciones es 1.
Cantidad media de comparaciones es (1+log₂(N))/2.
Cantidad máxima de comparaciones es log₂(N).
ALGORITMO
Se compara la llave buscada con la llave localizada al centro del arreglo.
Si la llave analizada corresponde a la buscada fin de búsqueda si no.
Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.
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.
BUSQUEDA POR TRANSFORMACION DE CLAVES (HASH)
Aumenta la velocidad de búsqueda sin necesidad de tener los objetos ordenados.
El tiempo de búsqueda es totalmente independiente del numero de componentes del arreglo.
La búsqueda se realiza por medio de direcciones, creadas por una función hash(H).
FUNCIONES HASH
Las Funciones HASH (H) mas aplicadas son:
Función Modulo (Por división).
Función Cuadrado.
Función Plegamiento.
Función Truncamiento.
La BUSQUEDA , es una operación que permite recuperar datos previamente almacenados. El resultado puede ser exitoso si se encuentra el elemento solicitado, o fracaso, en otro caso.
METODOS DE BUSQUEDA
Los métodos de búsqueda pueden clasificarse según la ubicación de los datos sobre los que se realizara la búsqueda. Existen dos clases:
Métodos de Búsqueda Interna
Métodos de Búsqueda Externa.
METODOS DE BUSQUEDA INTERNA
Se denomina búsqueda interna cuando todos los elementos se encuentran en la memoria principal. Por ejemplo, almacenados en estructuras estáticas (arreglos) o en estructuras dinámicas (listas ligadas y arboles).
Los métodos de búsqueda mas importantes son:
Secuencial o lineal
Binaria
Por transformación de claves
Arboles de búsqueda
METODOS DE BUSQUEDA EXTERNA
Se denomina búsqueda externa cuando todos los elementos se encuentran en memoria secundaria (archivos almacenados en dispositivos tales como cintas y discos magnéticos).
BUSQUEDA SECUENCIAL
Búsqueda secuencial consiste en revisar elemento por elemento hasta encontrar el dato buscado, o hasta llegar al final de la lista de datos disponible.
CARACTERISTICAS
La búsqueda se puede realizar en arreglos desordenados.
El método es totalmente confiable.
El numero de comparaciones es significativa si el arreglo es muy grande.
En arreglos desordenados de N componentes puede suceder que el elemento no se encuentre, por lo tanto se harán N comparaciones al recorrer todo el arreglo
Cantidad mínima de comparaciones es 1.
Cantidad media de comparaciones es (1+N)/2.
Cantidad máxima de comparaciones es N.
DIAGRAMA DE FLUJO (BUSQUEDA SECUENCIAL)
BUSQUEDA BINARIA
La búsqueda binaria 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 éste es el elemento buscado, entonces la búsqueda ha terminado.
En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este proceso, utilizando el elemento central de esa sub-lista.
CARACTERISTICAS
Sirve únicamente para arreglos ordenados.
Es mas eficiente que el método de búsqueda secuencial, debido a que el numero de comparaciones se reduce a la mitad por cada iteración del método.
Cantidad mínima de comparaciones es 1.
Cantidad media de comparaciones es (1+log₂(N))/2.
Cantidad máxima de comparaciones es log₂(N).
ALGORITMO
Se compara la llave buscada con la llave localizada al centro del arreglo.
Si la llave analizada corresponde a la buscada fin de búsqueda si no.
Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.
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.
BUSQUEDA POR TRANSFORMACION DE CLAVES (HASH)
Aumenta la velocidad de búsqueda sin necesidad de tener los objetos ordenados.
El tiempo de búsqueda es totalmente independiente del numero de componentes del arreglo.
La búsqueda se realiza por medio de direcciones, creadas por una función hash(H).
FUNCIONES HASH
Las Funciones HASH (H) mas aplicadas son:
Función Modulo (Por división).
Función Cuadrado.
Función Plegamiento.
Función Truncamiento.
Heapsort
El ordenamiento por heapsort es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional
El Heapsort está basado en el uso de un tipo especial de árbol binario (llamado apilamiento) para estructurar el proceso de ordenamiento. La estructura de ramificación del árbol conserva el número de comparaciones necesarias en O(n log n).
Caracteristicas
Las llaves están acomodadas en los nodos de tal manera que, para cada nodo i, Ki <= Kj donde el nodo j es el padre del nodo i. Es decir, al recorrer el camino desde la raíz hacia abajo, las claves se encuentran en orden descendente.
El árbol se llena de izquierda a derecha, lo que implica que si algún(os) nodo(s) no está(n) en el mismo nivel que el resto, éste(os) estará(n) entonces lo más a la izquierda posible del árbol.
Pasos del Heap
1º. Saca el valor máximo del Heap. (El de la posición 1).
2º. Pone el valor sacado en el arreglo ordenado.
3º. Reconstruir el Heap con un elemento menos.
Ejemplo
El Heapsort está basado en el uso de un tipo especial de árbol binario (llamado apilamiento) para estructurar el proceso de ordenamiento. La estructura de ramificación del árbol conserva el número de comparaciones necesarias en O(n log n).
Caracteristicas
Las llaves están acomodadas en los nodos de tal manera que, para cada nodo i, Ki <= Kj donde el nodo j es el padre del nodo i. Es decir, al recorrer el camino desde la raíz hacia abajo, las claves se encuentran en orden descendente.
El árbol se llena de izquierda a derecha, lo que implica que si algún(os) nodo(s) no está(n) en el mismo nivel que el resto, éste(os) estará(n) entonces lo más a la izquierda posible del árbol.
Pasos del Heap
1º. Saca el valor máximo del Heap. (El de la posición 1).
2º. Pone el valor sacado en el arreglo ordenado.
3º. Reconstruir el Heap con un elemento menos.
Ejemplo
BUSQUDA POR HASH
Procedimiento
Método consistente en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas
Casos de Colision
soluciones para reducir el número de colisiones
-Propagar los registros: Buscar funciones que distribuyan muy aleatoriamente los registros podemos evitar "agrupaciones" de llaves que produzcan las mismas direcciones.
-Usar memoria extra: En el ejemplo anterior planteamos tener una dirección de entre 1000 posibles, el uso de memoria extra se basa en proponer un espacio de direcciones posibles mucho más grande que el número de registros a usar, de modo que si vamos a insertar 100 registros un espacio de 500 direcciones nos una mejor opción de esparcir mejor.
-Colocar más de un registro en una dirección: A diferencia de los casos anteriores donde cada dirección almacena únicamente un registro, este concepto se basa en "buckets" o cubetas de datos en cada dirección, ahí se colocan algunos (casi todos) los registros que colisionan de manera que al hacer una búsqueda debemos recuperar la cubeta entera y ahi buscar por el registro deseado.
Un Algoritmo de Hash
No existe una fórmula "única" para hash, pero el producirla es un algoritmo que básicamente se presenta en 3 pasos:
1) Representar la llave de manera numérica (siempre que no sea de por sí un número)
Una buena opción es usar los valores ASCII o bien los Unicode de las letras
LOWELL= L O W E L L
76 79 87 69 76 76 32 32 32 32 32 32
2) Plegar y Agregar
-Combinar algunos de estos números para generar pequeños trozos con los que podamos trabajar
76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32
De manera que podemos hacer algunas operaciones matemáticas con dichos números para finalmente obtener un número del cual obtendremos la dirección
7679 + 8769 + 7676 + 3232 + 3232 = 30 588
Nota: Respecto a la implementación se puede dar el caso de formar números demasiado grandes, tanto que llegue al overflow del tipo de datos que estemos usando. Para solucionar esto podemos usar funciones como el "mod" intermedias para no tener ese problema.
3) Dividir por un número primo y usar el resultado como dirección Los archivos de hash por lo general suelen limitarse a un cierto rango de direcciones posibles para aprovechar mejor el concepto de memoria. de manera que podemos concluir nuestro algoritmo con la fórmula:
a= s mod n
Donde a es la dirección resultante, s es la suma o resultado de los pasos anteriores y n el número de direcciones posibles en el archivo Existen innumerables operaciones adicionales que pueden aplicarse en las fórmulas, así como las técnicas para limitar el valor final. Entre ellas se encuentran: elevar a alguna potencia, raíz cuadrada, convertir los números de base (hexadecimal, octal), etc...
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 esta 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.
Factores de Eficiencia
La distribución de los valores de llave que realmente se usan
El numero de valores de llave que realmente están en uso con respecto al tamaño del espacio de direcciones
El numero de registros que pueden almacenarse en una dirección dad sin causar una colisión.
La técnica usada para resolver el problema de las colisiones
Tipos de Funcion Hash
Residuo de la división
Medio del cuadrado
Pliegue
Hashing por residuo de 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).
Consideraciones
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.
Factor de Carga
Hashing por Elevacion al 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.
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.
Método consistente en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas
Casos de Colision
soluciones para reducir el número de colisiones
-Propagar los registros: Buscar funciones que distribuyan muy aleatoriamente los registros podemos evitar "agrupaciones" de llaves que produzcan las mismas direcciones.
-Usar memoria extra: En el ejemplo anterior planteamos tener una dirección de entre 1000 posibles, el uso de memoria extra se basa en proponer un espacio de direcciones posibles mucho más grande que el número de registros a usar, de modo que si vamos a insertar 100 registros un espacio de 500 direcciones nos una mejor opción de esparcir mejor.
-Colocar más de un registro en una dirección: A diferencia de los casos anteriores donde cada dirección almacena únicamente un registro, este concepto se basa en "buckets" o cubetas de datos en cada dirección, ahí se colocan algunos (casi todos) los registros que colisionan de manera que al hacer una búsqueda debemos recuperar la cubeta entera y ahi buscar por el registro deseado.
Un Algoritmo de Hash
No existe una fórmula "única" para hash, pero el producirla es un algoritmo que básicamente se presenta en 3 pasos:
1) Representar la llave de manera numérica (siempre que no sea de por sí un número)
Una buena opción es usar los valores ASCII o bien los Unicode de las letras
LOWELL= L O W E L L
76 79 87 69 76 76 32 32 32 32 32 32
2) Plegar y Agregar
-Combinar algunos de estos números para generar pequeños trozos con los que podamos trabajar
76 79 | 87 69 | 76 76 | 32 32 | 32 32 | 32 32
De manera que podemos hacer algunas operaciones matemáticas con dichos números para finalmente obtener un número del cual obtendremos la dirección
7679 + 8769 + 7676 + 3232 + 3232 = 30 588
Nota: Respecto a la implementación se puede dar el caso de formar números demasiado grandes, tanto que llegue al overflow del tipo de datos que estemos usando. Para solucionar esto podemos usar funciones como el "mod" intermedias para no tener ese problema.
3) Dividir por un número primo y usar el resultado como dirección Los archivos de hash por lo general suelen limitarse a un cierto rango de direcciones posibles para aprovechar mejor el concepto de memoria. de manera que podemos concluir nuestro algoritmo con la fórmula:
a= s mod n
Donde a es la dirección resultante, s es la suma o resultado de los pasos anteriores y n el número de direcciones posibles en el archivo Existen innumerables operaciones adicionales que pueden aplicarse en las fórmulas, así como las técnicas para limitar el valor final. Entre ellas se encuentran: elevar a alguna potencia, raíz cuadrada, convertir los números de base (hexadecimal, octal), etc...
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 esta 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.
Factores de Eficiencia
La distribución de los valores de llave que realmente se usan
El numero de valores de llave que realmente están en uso con respecto al tamaño del espacio de direcciones
El numero de registros que pueden almacenarse en una dirección dad sin causar una colisión.
La técnica usada para resolver el problema de las colisiones
Tipos de Funcion Hash
Residuo de la división
Medio del cuadrado
Pliegue
Hashing por residuo de 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).
Consideraciones
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.
Factor de Carga
Hashing por Elevacion al 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.
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.
sábado, 2 de mayo de 2009
Suscribirse a:
Entradas (Atom)
Entradas
