Criando um mecanismo de busca na internet em Android Java (Motor de Busca)

No post anterior eu mostrei como acessar uma página na web programaticamente utilizando Java Android. Também sugeri que o post poderia ser utilizado para a criação de um motor de busca na web similar às bases do Google, Yahoo, etc. Certamente um motor de busca como o Google é muito mais sofisticado do que eu vou apresentar aqui, mas os fundamentos não mudam.

A ideia é bem simples. Vou descrever o algoritmo abaixo e em seguida disponibilizo o código.

ALGORITMO

  1. Adicione em uma lista o link para uma página web
  2. Acesse este link
  3. Marque o link como visitado
  4. Leia o conteúdo da página retornada
  5. Procure os links existentes na página
  6. Adicione os links encontrados em uma lista
  7. Pegue o próximo link da lista
  8. Repita isso até que não existam mais links na lista ou atinja um limite de links máximos estipulados

Veja que o algoritmo base é bem simples. Além disso, o que cabe fazer é:

  1. Tratar os diferentes tipos de formatos de links que podem ocorrer
  2. Limitar os links desejados
  3. Otimizar a pesquisa

Na classe de exemplo abaixo, eu montei um motor de pesquisa bem simples apontando para a página inicial da Framework e procurando até 100 links.

CLASSE

package framework;

import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.Reader;
import java.net.URL;
import java.net.URLConnection;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class SearchMain {

    private List<MyLink> links = new ArrayList<MyLink>();
    private int MAX_LINKS = 100;
    private int count = 0;

    private class MyLink {

        private String link;
        private boolean visited = false;
        private int level = 0;
        
        public String getLink() {
            return link;
        }
        public void setLink(String link) {
            this.link = link;
        }
        public boolean isVisited() {
            return visited;
        }
        public void setVisited(boolean visited) {
            this.visited = visited;
        }
        public int getLevel() {
            return level;
        }
        public void setLevel(int level) {
            this.level = level;
        }
        
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + getOuterType().hashCode();
            result = prime * result + ((link == null) ? 0 : link.hashCode());
            return result;
        }
        
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            MyLink other = (MyLink) obj;
            if (!getOuterType().equals(other.getOuterType()))
                return false;
            if (link == null) {
                if (other.link != null)
                    return false;
            } else if (!link.equals(other.link))
                return false;
            return true;
        }
        private SearchMain getOuterType() {
            return SearchMain.this;
        }
        
        
    }    

    public static void main(String[] args) {
        
        SearchMain searchMain = new SearchMain();
        searchMain.init(“http://www.frameworksystem.com”);
        searchMain.navigate();
        searchMain.printLinks();
    }

    public void init(String url) {
        MyLink myLink = new MyLink();
        myLink.setLink(url);
        links.add(myLink);
    }

    private void navigate() {

        while((count < links.size()) && (links.size() < MAX_LINKS)) {

            MyLink parentLink = links.get(count);
            
            if (!parentLink.isVisited()) {
                String page = visitPage(parentLink);
                List<String> list = findHref(page);
                addLinks(parentLink, list);
                
                count++;
                
            }

        }    

        System.out.println(“———————————————————“);
        System.out.println(” Aborting after ” + MAX_LINKS + ” storaged links in cache”);
        System.out.println(“———————————————————“);
    }

    public void printLinks() {

        for(MyLink myLink: links) {
            System.out.println(myLink.getLink() + ” – visited: ” + myLink.isVisited() + ” – level: ” + myLink.getLevel());
        }

    }

    private void addLinks(MyLink parentLink, List<String> list) {

        for (String link:list) {

            MyLink myLink = new MyLink();
            myLink.setLink(link);
            myLink.setLevel(parentLink.getLevel() + 1);

            if (link.contains(links.get(0).getLink()) &&
                (!link.contains(“tag”)) &&
                (!link.contains(“respond”)) &&
                (!link.contains(“wp-login”)) &&
                (!link.contains(“comments”)) &&
                (!link.contains(“jpg”)) &&
                (!link.contains(“png”)) &&
                (!links.contains(myLink))) {
                    links.add(myLink);
            }
        }
        
    }
    
    private List<String> findHref(String page) {

        String regex = “\\b” + “a href” + “\\b”;
        Pattern pattern = Pattern.compile(regex);
        Matcher matcher = pattern.matcher(page);

        List<String> list = new ArrayList<String>();

        while(matcher.find() == true){
            int end = matcher.end();
            String hrefQuote = page.substring(end + 1, end + 2);
            int index = page.indexOf(hrefQuote, end + 2);
            
            if (page.substring(index – 1, index).equals(“/”))
                index = index – 1;

            String word = page.substring(end + 2, index);
            list.add(word);
        }

        return list;
    
    }
    
    private String visitPage(MyLink myLink) {

        try {
        
            System.out.println(“Visiting: ” + myLink.getLink() + ” – total links in cache: ” + links.size());
            
            myLink.setVisited(true);

            URL url = new URL(myLink.getLink());
            URLConnection conn = url.openConnection();
            InputStream inputStream = conn.getInputStream();

            final int bufferSize = 1024;
            final char[] buffer = new char[bufferSize];
            final StringBuilder out = new StringBuilder();
            Reader in = new InputStreamReader(inputStream, “UTF-8”);
            for (; ; ) {
                int rsz = in.read(buffer, 0, buffer.length);
                if (rsz < 0)
                    break;
                out.append(buffer, 0, rsz);
            }
            
            return out.toString();
            
        
        } catch (Exception e) {
            e.printStackTrace();
            return “”;
        }

    }

    
}

No próximo post irei utilizar o Motor de Busca para localizar quais as páginas possuem uma determinada palavra e montar uma página web com os links para as páginas encontradas no estilo Google Search.

NOTA 1: Me perguntaram se este algoritmo poderia ter sido implementado como um caminho em árvore ou grafo. O uso de lista sequencial é bem mais simples que o “caminhamento” em árvore ou grafo e é menos custoso em recursos quando temos que invariavelmente percorrer todos os elementos (quando fazemos pesquisa em árvore indexada b-tree, black-red, hash, etc, aí teremos o ganho do ln(n) – exemplo: indexação de colunas de banco, o que não é nosso caso aqui).  Neste caso específico, para manter as referências de árvore sem usar árvore propriamente dita é criar um campo no MyLink contendo o endereço do link pai ou uma referência para o objeto pai. Muita atenção ao uso de referências em Java para não causar um leak de memória e um estouro de heap.

NOTA 2: Me perguntaram se este algoritmo poderia ser recursivo. Certamente poderia, mas todo algoritmo recursivo é mais complexo que um linear e mais passível de estouro de memória (Heap). Apesar do algoritmo recursivo ficar mais compacto, ele vai empilhando o estados e só desempilha no final da recursividade. No caso de uma otimização do algoritmo através de paralelismo e threads, uma transformação recursiva pudesse ser considerada depois de uma boa análise e um bom desenho. Somente utilize recursividade, principalmente em Java, se você tiver total controle sobre seu algoritmo.

DICA: EM SEUS PROJETOS, NUNCA SE ESQUEÇAM DE IMPLEMENTAR O TESTCASE (TESTE UNITÁRIO) PARA SEUS MÉTODOS E REGRAS DE NEGÓCIO. UM TESTE CASE É IGUAL VACINA: “SALVA VIDAS!”

Add Comment

Your email address will not be published. Required fields are marked *

Phone: (31) 3646-1612
Fax: (31) 3646-1614
Loja 01, Lourdes, Belo Horizonte/MG
Rua Rio de Janeiro, 1278