[SP-pm] Conceito para fazer busca[ OFF ]

Nilson Santos Figueiredo Jr. acid06 at gmail.com
Tue Aug 11 22:47:15 PDT 2009


2009/8/11 Daniel de Oliveira Mantovani <daniel.oliveira.mantovani at gmail.com>:
> Olá pessoal, reparei em alguns sites que não importa se você coloca
> acento ou não, acha do mesmo jeito.

Isso não precisa de conceito avançado nenhum. Você cria o índice de
busca ignorando acentos (e.g. substitui um "é" por "e") e depois, na
hora de procurar, faz a mesma coisa.

> Eu queria saber o nome do conceito que isso tem para poder procurar e aprender.
> Tem alguns que você até pode escrever errado e acha, no site do Google
> tem uma coisa mais legal ainda que você vai digitando a palavra e vai
> completando, já vi em outros sites também.

Autocomplete é algo bem simples e todas a bibliotecas de JS recentes
fazem com que seja bem fácil fazer isso.

O negócio de escrever errado e achar é mais complicado. O que o Google
usa é uma espécie de busca estatística que é ativada quando você faz
uma busca que traz poucos resultados.

O algoritmo funciona mais ou menos assim: ele tenta trocar letras
consecutivas (ab => ba), realizar inserções de uma letra (aa => aba),
realizar remoções de uma letra (aba => aa), trocar letras por outras
não presentes (aba => aca) e provavelmente mais algumas operações mais
especializadas. Ele realiza essas substituições diversas vezes até
achar um bom resultado.

Então, por exemplo, se você procurar por "slhsdto", ele vai entender
que você quis procurar por "slashdot".
Porque? Observe as seguintes transformações:

1 - slhsdto
2 - slshdto (troca "h" com "s")
3 - slshdot (troca "t" com "o")
4 - slashdot (insere "a" entre o "l" e o "s")

Eu fiz um módulo em Perl que faz algo similar, mas ele é *bastante*
lento, por isso não está na CPAN. ;-)
Eu não sei teoria o suficiente pra conseguir implementar isso de
maneira otimizada.

-Nilson Santos F. Jr.


More information about the SaoPaulo-pm mailing list