• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Manhoso

[Dúvida] - String hashing

8 mensagens neste tópico

Boas.

Estou a tentar construir um dicionário, coisa que já fiz nas aulas, mas em java. 

O que me faltou na altura foi mesmo a implementação de hash para reduzir nos tempos de execução. Como não percebi a matéria das hashes muito bem, pedia que alguém me esclarecesse em como posso fazer a pesquisa num vector com muitos (10K+) elementos. Estes elementos estão ordenados e é tudo texto.

Lá está; sei que com hashes o prog porta-se muito bem, mas não estou a ver como fazer.

Desde já obrigado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

não usando hash podes usar pesquisa dicotómica acho eu que se chama assim

comparas a chave com o elemento do meio, se for maior usas a segunda metade, senão usas a primeira metada...

voltas a comparar mas agora com o elemento do meio da meta escolhida....assim sucessivamente...

não sei se me fiz entender?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se já tens o dicionário ordenado, uma pesquisa binária é a solução mais fácil.

Para implementar uma hash table, qualquer função que te disperse bem as palavras pode ser usada. Normalmente recomenda-se que uma hash table tenha pelo menos 30% mais posições do que o número máximo de palavras, e que esse número seja primo.

Depois arranjas uma função, que dada uma palavra, te retorna uma posição no vector. (usa aritmética modular).

De seguida, é só inserires as strings todas na hash table, e sempre que quiseres pesquisar, fazes o processo inverso.

O modo como lidas com colisões (duas palavras diferentes que mapeiam para a mesma posição de memória) pode variar: ou cada posição representa uma lista das palavras com essa hash, ou passas para a posição seguinte. E neste caso tens que ter cuidado ao inserir/verificar, e fica muito complicado remover.

Isto assim um resumo de hash tables, o resto deves poder resolver por ti.

No entanto, a maioria dos dicionários é feita com Tries por ser mais eficiente. Mas vais ter mais trabalho a implementar:

http://en.wikipedia.org/wiki/Trie

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Obrigado a todos.

Amanhã vou ter exame, mas se tiver tempo hj ainda tento fazer alguma coisa.

Também pensei em pesquisa binária, que foi o que utilizei no trabalho que falei (o tal em Java). Depois lembrei-me que o que era lento era a carregar as palavras de um ficheiro (lusiadas). :-[

Mais uma vez obrigado, quando tiver alguma coisa de concreto posto o resultado no Armazém de Código da linguagem.

Hasta

P.S.: Podem fechar este tópico.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não há qualquer necessidade de fechar o tópico, fica aberto em caso de necessidade.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora