Arquivo direto

Disponível somente no TrabalhosFeitos
  • Páginas : 9 (2247 palavras )
  • Download(s) : 0
  • Publicado : 24 de janeiro de 2013
Ler documento completo
Amostra do texto
Universidade Federal de São Carlos – Departamento de Computação

Organização e Recuperação da
Informação 2010
Arquivo Direto

Cleiton Queiroz Silva , RA: 344508
Renan Luciano Regonato RA: 286621
Rodrigo Scapim Furtado, RA: 344761
Thaymiller Marques De Marco, RA: 344672
Thiago Vasconcelos Ferratto RA 344281

INTRODUÇÃO
Existem inúmeras áreas da computação voltadas para a organizaçãoe recuperação da
informação , e um dos principais tópicos abordados é sempre como obter o melhor
desempenho quando deseja-se recuperar uma informação em um volume considerável
de dados. Imagine durante uma busca a possibilidade de se ter a posição exata do
registro especifico, antes mesmo acessar qualquer outro registro de dados presente na
coleção , e quando não for a posição exata seja omais próximo possível de se alcançá-la.
A ideia de Arquivos diretos e Hashing consiste exatamente nisso : dada uma chave em
um registro é possível determinar qual posição no arquivo ou memoria ele irá ocupar, e
caso ele não esteja na mesma é possível determinar qual a próxima posição mais
provável que ele pode ser encontrado, sem a necessidade de uma estrutura auxiliar e
com base em uma funçãoque determine qual é a posição que o registro deve ocupar .
Um arquivo direto é semelhante a um arquivo indexado , visto que ambos visão agilizar
pesquisas entretanto diferem na medida que enquanto um arquivo indexado necessita de
uma estrutura auxiliar de índice o arquivo direto se dispõe a partir de uma e função
matemática que dada uma determinada entrada ( chave ) , gera uma saída a qualdetermina a posição do registro no arquivo.

DETERMINAR A POSIÇÃO DE UM REGISTRO EM UM ARQUIVO DIRETO
Considere as informações abaixo :
Para cada registro é inserido nome , numero e salario , onde numero é a chave.
E → posição no arquivo
F() → função qualquer que dada a chave como parâmetro gera uma posição real do
arquivo, F() é denominada Função Hash , considere que F(150) = 5
Suponha quea busca seja pelo registro de chave 150
chave: 150 → E=F(numero) → E = 5
O registro poderá ser localizado na posição 5 do arquivo.
Nome Numer Salari
o
o
1 Paulo

30

3000

90

2000

150

1500

2
3

Ana

4
5 Fabio

O ideal para um bom arquivo direto é determinar uma função o mais determinística
possível ou seja, para um entrada só existe um saída e para uma saída sóexiste um
entrada associada a ela , o que é cada vez mais complicado conforme aumenta o domínio
de dados ao qual o arquivo se destina. Dessa forma , se determina uma função

probabilística o mais eficiente possível para que se evite de duas chaves coincidirem em
suas posições.
Uma vez que a função não é mais determinística ocorre o problema de colisões.

ESCOLHA DE FUNÇÕES HASH
O primeiropasso é garantir que a função gere posições dentro do escopo do problema,
ou seja , da posição inicial do arquivo até a ultima posição do arquivo, não podendo gerar
valores fora dessa faixa . Uma estrategia interessante para garantir que uma função
nunca gere valores que excedam o numero de posições é efetuar sempre a operação de
resto da divisão pelo tamanho máximo da tabela -1 o que garantetal condição.
Para que essa função possa ser perfeita ou seja Determinística é necessário que se
conheça todas as chaves que serão inseridas, um exemplo pratico disso é por exemplo
um dicionario ou uma tabela de palavras reservadas de uma linguagem onde os dados
são estáticos .Caso isso não ocorra então é necessário uma analise critica para se der
terminar uma função que chegue o mais próximodisso.
Uma função perfeita é uma função bijetora em que a imagem é igual ao contradomínio e o
contradomínio é igual ao domínio da função.
Vale lembrar que essas são funções matemáticas e portanto aceitam numero como
entrada e por isso a chave deve ser convertida em valores numéricos de acordo com
algum critério pré-determinado.

Exemplo de Função Ideal

TRATAMENTO DE COLISÕES
Uma...
tracking img