Home
Este trabalho tem como objetivo desenvolver uma spellchecker utilizando tabela hash. O spell checker é um programa que testa as palavras de um texto contra um dicionário, se uma determinada palavra do texto é encontrada no dicionário, presume-se que ela está escrita corretamente.Se a palavra não é encontrada no dicionário, considera-se que ela esteja escrita de forma incorreta ou que o dicionário em questão ainda não a contém.
Uma função de hash tem como objetivo transformar o que vai ser guardado em um valor inteiro para daí determinar sua posição na tabela hash.A função de hash utilizada no desenvolvimento deste trabalho foi uma função chamada djb2 que é uma das melhores funções de hash para palavras. Seu funcionamento é simples, o valor de hash é inicializado em um número primo grande(normalmente 5381) depois disso o valor de hash será este número vezes 33 adicionado o valor da letra em ASIIC isso para cada letra da palavra.
Observe a implementação dela abaixo:
Quando vamos inserir um novo elemento na nossa tabela depois de calcularmos o valor de hash para definir o local onde esse elemento vai ficar tiramos o mod (resto da divisão inteira)desse valor de hash de acordo com a quantidade de buckets que a nossa tabela tem por mais que nossa função de hash seja boa, como temos um número limitado de buckets dependendo da quantidade de itens que queremos inserir quase sempre vai gerar colisões ,ou seja, itens caindo no mesmo bucket, para tratarmos essas colisões temos várias maneiras.
Encadeamento é uma das maneiras mais simples de resolução de colisão. Com esse tratamento cada elemento da tabela de hash é uma lista encadeada. Para inserir um item na tabela basta inserir esse item na lista encadeada específica caso tenha colisão todos esses itens ficaram na mesma lista. Na hora de pesquisar basta ir na lista correspondente daquele item e olhar se ele está lá ou não.
O custo de inserção é sempre contínuo pois basta definir o valor de hash e dar um prepend neste item na lista, já o custo de pesquisa varia com a função de hash utilizada, se ele distribui bem ou não os itens, e com a quantidade de buckets. Se tivermos uma boa função de hash a pesquisa terá uma tempo de O(M/N) onde M é a quantidade de itens inseridos, N é a quantidade de buckets.
Implementação da inserção e pesquisa usando encadeamento utilizando C++:
Implementação da inserção e pesquisa usando encadeamento utilizando C++:
A parte da implementação da lista encadeada pode ser encontrada aqui.
a inserção fica assim:
e a pesquisa assim:
Usando o código acima para carregar o dicionário cedido pelo professor e checar um total de palavras variando a quantidade de buckets e contando apenas o tempo que levou para pesquisar as palavras os resultados foram os seguintes:
No eixo x temos a quantidade de buckets e no eixo y temos o tempo em milisegundos.
Como podemos ver com o gráfico depois de aproximadamente 1600 buckets o tempo de pesquisa começa a estabilizar por volta de 500 ms ,isso porque a função de hash é muito boa e espalha bem as palavras nos buckets.
Linear probing
O endereçamento aberto linear é uma técnica de tratamento de colisões onde todos os itens são guardados em um array porém caso haja uma colisão o valor de hash desse item irá antes do mod ser incrementado de um em um até que o índice se refira a um bucket vazio, e na hora da pesquisa a mesma coisa depois de calcular o valor de hash e tirar o mod se aquela posição for uma posição ocupada e não for aquele item terá que ser feito o incremento do mesmo jeito e comparar até achar aquele item e confirmar que ele está lá ou achar um bucket vazio e assim confirmar que o item não está nessa tabela.
Matematicamente a fórmula que define próximo índice ficaria assim:
Exemplo de inserção usando linear probing:
Para a utilização desse modo de tratamento de colisão o número de itens a serem inseridos nesta tabela tem que ser menor ou igual ou número de buckets
Quanto ao custo da inserção e da pesquisa não dá para atribuir um valor pois seria constante caso não tenha nenhuma colisão ,mas como é difícil não ocorrer colisões o custo passa a ser uma probabilidade de alguém tá ocupando ou não o bucket correspondente daquele item e os seus subsequentes.
Implementação da inserção e pesquisa usando linear probing usando C++:
O quadratic probing tem basicamente o mesmo funcionamento do Linear probing, mas agora o incremento é feito não mais de um em um e sim com o quadrado do próximo valor de incremento.
Neste caso a fórmula que define o valor da próxima índice fica assim:
Exemplo de inserção usando quadratic probing:
Quanto ao custo ,é mesma coisa da linear probing também não existe um custo estabelecido e sim uma probabilidade do próximo índice está ocupado ou não.
Implementação da inserção e pesquisa usando quadratic probing usando C++: