Comentários?
Qual o consumo de tempo da função insira_ordenado()?
Qual o consumo de tempo da função monte_t_gramas()?
def monte_t_gramas(t, texto): '''(int, str) -> dicionário Recebe um inteiro t e um string texto e cria e retorna um dicionário de t-gramas do texto. Exemplos: >>> monte_t_gramas(1,"testes") [['e', 's', 't'], [2, 2, 2]] >>> monte_t_gramas(2,"testes") [['es', 'st', 'te'], [2, 1, 2]] >>> monte_t_gramas(2,"tesTes") [['Te', 'es', 'sT', 'te'], [1, 2, 1, 1]] >>> monte_t_gramas(2,"tEsTes") [['Es', 'Te', 'es', 'sT', 'tE'], [1, 1, 1, 1, 1]] >>> monte_t_gramas(2,"tes tes") [[' t', 'es', 's ', 'te'], [1, 2, 1, 2]] >>> monte_t_gramas(1,"banana") [['a', 'b', 'n'], [3, 1, 2]] >>> monte_t_gramas(2,"banana") [['an', 'ba', 'na'], [2, 1, 2]] >>> monte_t_gramas(3,"banana") [['ana', 'ban', 'nan'], [2, 1, 1]] >>> ''' dicio = [[],[]] n = len(texto) for i in range(n-t+1): # pegue o t-grama texto[i:i+t] tgrama = '' for j in range(t): tgrama += texto[i+j] # insira o tgrama no dicionário insira_ordenado(tgrama, dicio) return dicio def insira_ordenado(tgram, dicio): ''' (str, dicio) -> None Recebe um t-grama tgram e um dicionário de t-gramas dicio. Se tgram é uma chave no dicionário, então a função incrementa o valor correspondente, em caso contrário a chave tgram é inserida no dicionário com valor 1. Importante: as chaves do dicionário deverão ser mantidas em em ordem alfabética crescente. Exemplos: >>> dicio = [['es', 'te'], [1, 1]] >>> tgram = 'st' >>> insira_ordenado(tgram,dicio) >>> print(dicio) [['es', 'st', 'te'], [1, 1, 1]] >>> tgram = 'te' >>> insira_ordenado(tgram,dicio) >>> print(dicio) [['es', 'st', 'te'], [1, 1, 2]] >>> tgram = 'es' >>> insira_ordenado(tgram,dicio) >>> print(dicio) [['es', 'st', 'te'], [2, 1, 2]] ''' # apelidos (= aliases) chaves = dicio[0] valores = dicio[1] n = len(chaves) # procure a chave no dicionário i = n-1 while i >= 0 and chaves[i] > tgram: i -= 1 # verifique se a chave está no dicionário if i == -1 or chaves[i] != tgram: # chave não está no dicionário # acrescente uma posição no dicionário chaves.append('') valores.append(0) # desloque as chaves e valores k = n-1 while k > i: chaves[k+1] = chaves[k] valores[k+1] = valores[k] k -= 1 # insira chave no dicionário chaves[i+1] = tgram valores[i+1] = 1 else: # chave está no dicionário na posição i valores[i] += 1
Python 3.5.2 (default, Jul 5 2016, 12:43:10) [GCC 5.4.0 20160609] on linux Type "help", "copyright", "credits" or "license" for more information. >>> >>> monte_t_gramas(2,"testes") [['es', 'st', 'te'], [2, 1, 2]] >>> monte_t_gramas(1,"testes") [['e', 's', 't'], [2, 2, 2]] >>> monte_t_gramas(2,"testes são testes") [[' s', ' t', 'es', 'o ', 's ', 'st', 'sã', 'te', 'ão'], [1, 1, 4, 1, 1, 2, 1, 4, 1]] >>> monte_t_gramas(1," non scholæ sed vitæ discimus") [[' ', 'c', 'd', 'e', 'h', 'i', 'l', 'm', 'n', 'o', 's', 't', 'u', 'v', 'æ'], [5, 2, 2, 1, 1, 3, 1, 1, 2, 2, 4, 1, 1, 1, 2]] >>> monte_t_gramas(2," non scholæ sed vitæ discimus") [[' d', ' n', ' s', ' v', 'ch', 'ci', 'd ', 'di', 'ed', 'ho', 'im', 'is', 'it', 'læ', 'mu', 'n ', 'no', 'ol', 'on', 'sc', 'se', 'tæ', 'us', 'vi', 'æ '], [1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2]] >>> monte_t_gramas(2,"師傅領進門，修行在個人") [['修行', '個人', '傅領', '在個', '師傅', '行在', '進門', '門，', '領進', '，修'], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]] >>> monte_t_gramas(2,"師傅領進門, 修行在個人") [[' 修', ', ', '修行', '個人', '傅領', '在個', '師傅', '行在', '進門', '門,', '領進'], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]] >>> monte_t_gramas(1,"師傅領進門, 修行在個人") [[' ', ',', '人', '修', '個', '傅', '在', '師', '行', '進', '門', '領'], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]] >>> monte_t_gramas(1,"אל תסתכל בקנקן, אלא במה שבתוכו") [[' ', ',', 'א', 'ב', 'ה', 'ו', 'כ', 'ל', 'מ', 'ן', 'נ', 'ס', 'ק', 'ש', 'ת'], [5, 1, 3, 3, 1, 2, 2, 3, 1, 1, 1, 1, 2, 1, 3]] >>> monte_t_gramas(2,"אל תסתכל בקנקן, אלא במה שבתוכו") [[' א', ' ב', ' ש', ' ת', ', ', 'א ', 'אל', 'במ', 'בק', 'בת', 'ה ', 'וכ', 'כו', 'כל', 'ל ', 'לא', 'מה', 'ן,', 'נק', 'סת', 'קן', 'קנ', 'שב', 'תו', 'תכ', 'תס'], [1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]] >>>