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++: