Arquivo Discussoes de Programacao e Tecnologia Galera,o problema e o seguinte:
tenho um banco de dados com varias palavras
Gostaria de desenvolver um programa q dada uma palavra compare esta com o banco e retorne:
Gostaria de ideias pois o que eu desenvolvi ate agora naum eh muito bom…
[]´s.
Qual o nível de “aproximação” que você está buscando?
banan -> banana
ou
bavava -> banana
?
A principio,as palavras nem precisam começar com a mesma letra…
No seu caso, eu preciso achar nos dois casos.
faz pesquisa indexadas por soundex, ou qualquer algorítmo de semelhançaa fonética
No livro Projeto de Algoritmos do Nivio Ziviani tem um algorítmo chamado Shift-And-Aproximado que eu acho muito interessante. Você escolhe o número de diferenças aceitáveis, entre inclusão, remoção ou alteração de caracteres, e manda rodar.
O código dele é bem pequeno e simples de implementar, mas a idéia é bem legal pois ele na verdade cria umas máscaras de bits e fica fazendo um monte de operação bitwise para simular um autônomo de comparação.
E o custo dele é muito bom por se aproveitar do paralelismo de bits. No caso médio ele é linear, de ordem O(kn) onde k é o número de diferenças aceitáveis e n o tamanho do texto.
Esse algoritimo do shift é muito útil… procura sobre ele q vc resolve seu problema… + jah vou te adiantando… se vc colocar uma tolerância maior do que 1, vc consegue palavras q não tem nada a ver com o digitado… + beleza…