Atenção: Esta tarefa também será corrigida manualmente. Depois de terminada e corrigida automaticamente, você deve apresentar sua tarefa a um monitor em algum horário de atendimento. Você poderá pedir recorreção, mas o conceito da recorreção será no máximo B.
Árvore
Uma página HTML pode conter links para outras páginas. Queremos entender a hierarquia entre elas se começarmos a visitar um website a partir de uma determinada página. Faça um programa que recebe o link de uma página inicial e mostra a hierarquia entre as páginas que podem ser alcançadas a partir da inicial.
Dizemos que essa hierarquia forma uma árvore em que cada nó
corresponde a uma página distinta. A raiz da árvore é a página
inicial. Os filhos de um nó da árvore são as páginas HTML que são
acessíveis a partir daquele nó. Por exemplo, se começássemos a navegar
a partir de http://exemplo.com/index.html, poderíamos criar uma
árvore como a seguinte.
Visitamos os links na ordem em que os encontramos nas páginas. Assim, ao visitar a página raiz, encontrarmos um link para o índice do blog, onde encontramos um link para o primeiro post e assim por diante. Repare que uma página pode ser acessada através de várias outras páginas, mas ela aparecerá na árvore apenas uma vez. Por exemplo, o índice do blog pode conter um link para o segundo post, mas como já tínhamos visto esse link antes, não o visitamos de novo.
Analisando uma página
Para descobrir os links, você deve analisar o conteúdo de cada página visitada e listar os links que ela possui. Uma página HTML nada mais é do que um arquivo de texto escrito em uma linguagem de marcação de estrutura e formato.
O arquivo é formado por uma sequência de tags balanceadas. Para descobrir os links, basta que você conheça o formato das tags de links. A seguir, há um exemplo de um link que você estará procurando.
<a href="https://ic.unicamp.br/graduacao/engenharia-da-computacao/"> Engenharia da Computação </a>
Essa tag define um link com o texto Engenharia da Computação que, se
clicado, vai para a URL escrita. A parte que interessa é a propriedade
href. Fazer uma análise completa de um arquivo HTML que funcione
para qualquer página da internet não é uma tarefa trivial, mas, algumas
vezes, simplificações são suficientes para o que queremos.
Nesta tarefa, você deve supor que todo link corresponde a uma
substring com a forma href="[URL DA PÁGINA]", então basta procurar
por substrings com esse formato e extrair URL entre as aspas duplas.
Não é difícil escrever um algoritmo para encontrar expressões como essa em uma string. Encontrar um padrão em uma string é uma tarefa tão comum que existe uma ferramenta especializada para ajudar: as expressões regulares. Se você preferir, poderá utilizá-las para encontrar os links presentes na página
Uma expressão regular é uma sequência de símbolos que representa um
determinado padrão. Cada símbolo tem um significado especial. Abaixo,
temos um exemplo de uma expressão regular que corresponde a um número
telefônico. O padrão é definido como dois números entre parênteses
seguidos de quatro ou cinco números, um traço e mais quatro números.
Podemos utilizar o módulo re para definir e utilizar expressões
regulares em Python.
>>> import re >>> regex = r"\(\d{2}\) \d{4,5}-\d{4}" >>> texto = "Esse é o meu número (00) 12345-6789" >>> texto = "Ligue para (00) 2345-6789 ou para (01) 12345-4321" >>> telefones = re.findall(regex, texto) >>> telefones ['(00) 2345-6789', '(19) 12345-4321']
Neste link você pode encontrar vários exemplos interativos de como definir e utilizar expressões regulares. Entender como as expressões regulares mais sofisticadas funcionam é um assunto complicado que você só aprenderá ao estudar compiladores, mas aprender a usar os padrões mais simples pode ser útil. Não gaste muito tempo tentando aprender tudo.
Módulo auxiliar
No diretório, você encontrará um arquivo auxiliar modulo.py com
várias funções já prontas para facilitar o desenvolvimento da tarefa.
Há funções para para normalizar o formato das URLs, verificar se as
URLs encontradas são válidas e para carregar páginas HTML. Essas
funções ajudam nas tarefas descritas a seguir.
Resolvendo URLs
Ao visitar uma página, podemos encontrar endereços relativos ao diretório atual. Por exemplo, na página
https://ic.unicamp.br/~lehilton/mc102qr/unidades/10-eficiencia.html
encontramos um link para
../fixacao/07-ordenacao.html#exercicios-criativos
Nesse caso, a URL do link deve ser resolvida para
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/07-ordenacao.html
Controlando o tamanho da árvore
Se visitarmos todos os links que encontrarmos, pode acontecer de visitarmos milhões de páginas. Para evitar que isso aconteça, vamos restringir os links de interesse.
Primeiro, não queremos visitar links para imagens, documentos PDF ou outros objetos. Assim, só visitaremos URLs que:
- ou terminem com
/, i.e., correspondem ao índice de um diretório; - ou terminem com extensão
.htmou.html, i.e., são arquivos HTML.
Além disso, só visitaremos páginas que estejam no mesmo diretório ou em subdiretórios da página inicial. Por exemplo, se a página inicial é
https://ic.unicamp.br/~lehilton/mc102qr/unidades/11-recursao.html
podemos visitar
https://ic.unicamp.br/~lehilton/mc102qr/unidades/10-eficiencia.html
mas não iremos visitar
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/11-eficiencia.html
tampouco visitaremos
https://www.youtube.com/channel/UC81VD6eeuLLSfyY_D-N8sVw
mesmo que esses links apareçam no código HTML.
Baixando arquivos HTML
Há uma função no módulo que recebe uma URL e baixa o arquivo HTML em um diretório de cache. Por exemplo, se você encontrar o link
https://ic.unicamp.br/~lehilton/mc102qr/index.html
então a função baixará esse arquivo da Web e o guardará em um arquivo dentro do diretório local chamado
cache/ic.unicamp.br/~lehilton/mc102qr/index.html
A função devolverá uma string com todo o conteúdo do arquivo local se
conseguir baixar, ou devolverá None se não tiver sido possível
baixar ou se o conteúdo baixado não for um arquivo HTML.
Para os casos de teste desta tarefa, você já receberá uma cópia de
páginas do site ic.unicamp.br junto do seu repositório, assim não é
necessário estar conectado à internet enquanto estiver testando. Não
altere, nem atualize esses arquivos. Se desejar testar com outras
páginas, então você deve ter o módulo requests instalado.
Entrada e saída
Você deve criar um programa chamado arvore.py.
Entrada
Uma linha com a URL correspondente à página inicial.
https://ic.unicamp.br/~lehilton/mc102qr/index.html
Saída
Seu programa irá mostrar a árvore. Cada subnível da hierarquia é distinguido com um nível de recuo, utilizando 2 espaços.
https://ic.unicamp.br/~lehilton/mc102qr/index.html
https://ic.unicamp.br/~lehilton/mc102qr/apresentacao.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/00-algoritmo.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/01-variaveis.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/02-condicional.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/03-repeticao.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/04-funcoes.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/05-praticas.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/06-listas.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/07-ordenacao.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/08-matrizes.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/09-arquivos.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/10-colecoes.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/11-eficiencia.html
https://ic.unicamp.br/~lehilton/mc102qr/fixacao/12-recursao.html
https://ic.unicamp.br/~lehilton/mc102qr/unidades/01-problemas-algoritmos.html
https://ic.unicamp.br/~lehilton/mc102qr/unidades/02-escrevendo-algoritmos.html
https://ic.unicamp.br/~lehilton/mc102qr/unidades/03-linguagens-programacao.html
https://ic.unicamp.br/~lehilton/mc102qr/unidades/04-estruturas-elementares.html
https://ic.unicamp.br/~lehilton/mc102qr/unidades/05-listas.html
https://ic.unicamp.br/~lehilton/mc102qr/unidades/06-funcoes.html
https://ic.unicamp.br/~lehilton/mc102qr/unidades/07-algortimos-iterativos.html
https://ic.unicamp.br/~lehilton/mc102qr/unidades/08-matrizes.html
https://ic.unicamp.br/~lehilton/mc102qr/unidades/09-colecoes.html
https://ic.unicamp.br/~lehilton/mc102qr/unidades/10-eficiencia.html
https://ic.unicamp.br/~lehilton/mc102qr/unidades/11-recursao.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/14-recursao.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/13-algoritmos-eficientes.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/12-colecoes-dinamicas.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/11-dicionarios-e-tuplas.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/10-imagens-binarias.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/09-conceito-frequencia.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/08-funcoes.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/07-percorrer-listas.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/06-listas.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/05-condicional.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/04-entendendo-algoritmos.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/03-estruturas-controle.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/02-problemas-algoritmos.html
https://ic.unicamp.br/~lehilton/mc102qr/tarefas/01-primeira-tarefa.html