EP3
EP3 - Qual é a palavra?
Os objetivos deste exercício são praticar:
- o uso de busca binária e de ordenação;
- o uso listas como parâmetros de funções;
- a manipulação de listas de listas;
- a implementação de dicionários através de lista.
Problema
Vários teclados digitais, como em tablets e smart phones mostram uma lista de palavras "mais prováveis" após a digitação de alguns poucos caracteres. Se a palavra desejada pelo usuário estiver na lista, ele pode selecionar a palavra e assim "acelerar" a digitação. Nesse exercício vamos considerar uma forma de calcular os complementos mais prováveis usando os chamados t-gramas extraídos de um texto utilizado para treinamento.
Palavras, t-gramas e complementos
Como no EP2, chamaremos de palavra qualquer sequência de caracteres pertencentes ao string LETRAS, definido no início do esqueleto do EP.
Um t-grama é um string de comprimento t. Chamamos os 2-gramas e 3-gramas de bi-gramas e tri-gramas, respectivamente Considere, por exemplo, o texto:
'três tigres comeram trinta e três pratos de trigo',
Os tri-gramas que ocorrem nesse texto são: 'trê', 'rês', 'ês ", 's t', ' ti', 'tig', 'igr', e assim por diante.
Note que, diferentemente de palavras, que são constituídas exclusivamente por símbolos no string LETRAS, qualquer caractere faz parte de um t-grama. Assim, por exemplo, caracteres como ' ', '.', ',', . . . fazem parte de t-gramas.
Um complemento (associado a um texto) de um t-grama é uma palavra não vazia formada pela parte final de qualquer palavra que está no texto concatenada imediatamente após o t-grama. O complemento pode, inclusive, corresponder a uma palavra inteira. Por exemplo, em relação ao texto anterior e suas palavras temos que os complementos do bi-grama 'tr' são 'ês', 'inta', 'igo'.
'três tigres comeram trinta e três pratos de trigo'.
Nos exemplos de complementos a seguir o números após um ":" indica o número de ocorrências do complemento do t-grama no texto.
- o bi-grama 'tr' possui os complementos: { "ês":2, "inta":1, "igo":1}
'três tigres comeram trinta e três pratos de trigo';
- o tri-grama 's t' (note o ' ' entre o 's' e o 't') tem o complemento { 'igres':1 }
'três tigres comeram trinta e três pratos de trigo';
- o tri-grama 'rês' não possui complemento algum no texto
'três tigres comeram trinta e três pratos de trigo';
- o tri-grama 'ês ' (note o ' ' no final) tem os complementos { 'tigres':1, 'pratos':1 }
'três_tigres comeram trinta e três_pratos de trigo';
- o tri-grama 's t' (note o ' ' 's' e o 't') tem o complemento { 'igres':1 }
'três_tigres comeram trinta e três pratos de trigo';
Utilizando-se os textos nos arquivos drummond.txt e tigres.txt foram produzidos os exemplos de t-gramas e complementos de t-gramas mostrados nos arquivos exemplo-2grama.txt, exemplo-3grama.txt e exemplo-4grama.txt. Para entender o comportamento das funções que deverão ser implementadas neste EP3 é recomendado que esses exemplos sejam examinados cuidadosamente.
No que diz respeito a problema de predição de palavras, durante a digitação de um texto, os complementos podem ser combinados de acordo com a sequência de t-gramas. Por exemplo, após o tri-grama 'tri', as palavras 'trinta' e 'trigo' podem ser previstas e, após a digitação do caractere 'g' (tri-grama 'rig'), apenas a palavra 'trigo' é prevista. Na prática, outras informações também devem ser consideradas, mas nesse exercício, o seu programa deve apenas computar o dicionário de t-gramas onde uma chave é um t-grama e o valor é o seu dicionário de complementos.
Dicionários dos complementos
Em relação a um texto, um dicionário dos complementos de um t-grama é um dicionário em que as chaves são os complementos do t-grama no texto e o valor associado a cada chave é o número de ocorrências do complemento. Por exemplo, em relação ao texto
'três tigres comeram trinta e três pratos de trigo'.
o dicionário de complementos do t-grama 'tr' é
{ 'ês':2, 'inta':1, 'igo':1 }.
Um dicionário de complementos pode ser representado através de duas listas: a das chaves (= complementos) e a dos respectivos valores (= número de ocorrências).
Dicionários dos t-gramas
Em relação a um texto, um dicionário dos t-gramas é um dicionário em que as chaves são os t-gramas no texto e o valor associado a cada chave é o dicionário de complementos do t-grama. Só estarão presentes no dicionário a chaves correspondentes aos t-gramas que possuem algum complemento não nulo. Por exemplo, em relação ao texto
'três tigres comeram trinta e três pratos de trigo'.
o dicionário de complementos dos 2-gramas é
---------------------------------------- chave | valor
---------------------------------------- 1 ' c' | { 'omeram':1 } 2 ' d' | { 'e':1, 'ois': 1 } 3 ' p' | { 'ratos':1 } 4 ' t' | { 'igre':1, 'igres': 2, 'rigo': 1, 'rinta': 1, 'rês': 2 } 5 'a ' | { 'e':1 } 6 'at' | { 'os':1 } 7 'co' | { 'meram':1 } 8 'do' | { 'is':1 } 9 'e ' | { 'dois':1, 'trigo': 1, 'três': 1 } 10 'er' | { 'am':1 } 11 'gr' | { 'e':1, 'es': 2 } 12 'ig' | { 'o':1, 're': 1, 'res': 2 } 13 'in' | { 'ta':1 } 14 'm ' | { 'tigre':1, 'trinta': 1 } 15 'me' | { 'ram':1 } 16 'nt' | { 'a':1 } 17 'oi' | { 's':1 } 18 'om' | { 'eram':1 } 19 'pr' | { 'atos':1 } 20 'ra' | { 'm':1, 'tos': 1 } 21 're' | { 's':2 } 22 'ri' | { 'go':1, 'nta': 1 } 23 'rê' | { 's':2 } 24 's ' | { 'comeram':1, 'de': 1, 'pratos': 1, 'tigres': 2, 'três': 1 } 25 'ti' | { 'gre':1, 'gres': 2 } 26 'to' | { 's':1 } 27 'tr' | { 'igo':1, 'inta': 1, 'ês': 2 }
Um dicionário t-gramas pode ser representado através de duas listas: a das chaves (= t-gramas) e a dos respectivos valores (= dicionários de complementos).
Implementação dos dicionários
Nos EPs anteriores um dicionário foi representado por meio de duas listas. Uma lista contendo as chaves e outra os valores. Nesse EP3, para facilitar a passagem de dicionários como parâmetros de funções, vamos implementar um dicionário como uma lista contendo essas duas listas. Assim, o dicionário vazio é
[ [], [] ].
Consequentemente, se dicio é o nome de um dicionário, dicio[0] é a lista de suas chaves e dicio[1] é a lista dos seus respectivos valores.
O seu EP lerá um texto de um arquivo e criará um dicionário de t-gramas. Cada valor desse dicionário será é dicionário de complementos do respectivo t-grama. A fim de que buscas e inserções nos dicionários sejam feitas de forma eficiente, o dicionário de t-gramas e os respectivos dicionários de complementos deverão ser manter suas chaves ordenadas em ordem alfabética crescente.
O que você deve fazer
A função main() dada nesse exercício lê um número natural n > 1. e um texto de um arquivo. Você não deve alterar a função main(). Leia essa função com atenção, para entender melhor como devem funcionar as funções que você deve implementar, mas em hipótese alguma a altere.
Você deve escrever as seguintes funções
- indice_binario();
- insere_ordenado(); e
- monta_t_grama().
A especificação de cada uma dessas funções está no doc-string da função no arquivo esqueleto_ep3.py
Embora o texto possa ter caracteres maiúsculos e minúsculos, consideraremos, como no EP2, que esses caracteres são iguais. Desta forma, os strings 'CASA' e 'casa' e 'CaSa' serão considerados iguais. Todas as letras presentes nos dicionários deverão ser minúsculas.
Roteiro
- Faça o download do arquivo esqueleto_ep3.py e demais arquivos dos links abaixo.
- Mude o nome do arquivo esqueleto_ep3.py para NUSP_ep3.py, onde o NUSP é o seu número USP.
- Abra o esqueleto no Spyder ou em qualquer outro editor ou ambiente apropriado para desenvolver programas em Python.
- Leia e preencha o cabeçalho com o seu nome, nusp, etc. Não modifique o resto do cabeçalho.
- Execute o arquivo para ver se está tudo ok. O programa vai pedir o tamanho do t-grama (digite um número qualquer) e o nome de um arquivo, use o arquivo "tigres.txt" para os testes iniciais. Para testes use textos ainda mais simples se necessário. Para isso ele deve estar na mesma pasta que o seu programa NUSP_ep3.py. O programa deve imprimir algo como:
========================================================== ### PROGRAMA N-GRAMA ### ========================================================== Digite o tamanho do t-grama: 2 Digite o nome do arquivo texto: tigres.txt Montando o dicionário. Por favor aguarde... Vixe, ainda não implementei a função monta_t_gramas! acabei. Quantidade de 2-gramas encontrados: 0 ========================================================== ### INICIO ### ========================================================== Digite: 'f': para sair do programa; ou 't': para imprimir todo o dicionário; ou digite um 2-grama: aa Vixe, ainda não implementei a função indice_binario! Não achei o 2-grama aa ========================================================== Digite: 'f': para sair do programa; ou 't': para imprimir todo o dicionário; ou digite um 2-grama: f ========================================================== ========================================================== ### F I M ### ==========================================================
-
Antes de escrever cada função, leia atentamente a função main() até entender o que ela faz e então planeje como as demais funções devem ser implementadas para que o seu programa gere a saída mostrada nos exemplos dos links abaixo. Não modifique a função main().
- Escreva as funções indice_binario(), insere_ordenado() e monta_t_gramas() de acordo com a especificação no respectivo doc-string. A função monta_t_gramas() deve montar o dicionário de t-gramas do texto mantendo a lista de chaves sempre ordenada em ordem alfabética crescente. Além disso, as chaves de cada dicionário de complementos também devem ser mantidas em ordem alfabética crescente. Para isso, use as funções indice_binario() e insere_ordenado().
- Teste cada função separademente das demais usando o console do Spyder (=Python Shell ou IPython). Você também pode usar para os testes um terminal.
- Teste o EP3 completo, chamando agora a função main(), inclusive com outros arquivos de teste além dos fornecidos.
- A saída dos testes completos para 2-gramas, 3-gramas e 4-gramas usando os arquivos drummond.txt e tigres.txt pode ser vista nos arquivos de exemplos fornecidos nos links abaixo.
- Após testar o seu programa com vários textos, entregue o arquivo NUSP_ep3.py (onde NUSP é o seu número USP) usando o botão ENVIAR mais abaixo. Não deixe de seguir as instruções para entrega de EPs.
Entrega:
A primeira entrega deve ser feita até o dia 28/08 (até 23h55m).
O EP receberá comentários até o dia 29/08.
Uma nova versão poderá ser entregue até o dia 30/08 (até 23h55m) 31/08 (até 23h55m).
- 18 agosto 2016, 18:53 PM
- 24 agosto 2016, 22:23 PM
- 21 agosto 2016, 11:38 AM
- 21 agosto 2016, 11:38 AM
- 21 agosto 2016, 11:38 AM
- 21 agosto 2016, 11:38 AM