Em um texto em português (brasileiro) qual é a letra que mais aparece? Podemos pensar que seja a letra 'A' e, muito provavelmente, estaremos certos. Mas qual é a segunda letra mais comum? Quais as menos usadas? Você 'chutaria' que a talvez a letra 'z' seja mesmo usada? Neste caso, você estaria enganado. As letras 'K', 'Y' e 'J' são ainda menos comuns em um texto longo que o 'X'. E como podemos ter essa certeza? Uma forma de termos essa 'certeza' é realizar a leitura de texto longo em português e fazer uma contagem de quantas vezes aparece a letra 'A', a letra 'B', ... e assim por diante. Claro, devemos fazer essa tarefa de contagem usando algum programa de computador. Em nosso experimento, obtivemos a seguinte tabela de frequência:
Letra |
Probabilidade |
A | 0.1454151 |
E | 0.1295147 |
O | 0.1049440 |
S | 0.0748605 |
I | 0.0695045 |
R | 0.0627958 |
M | 0.0510300 |
U | 0.0489846 |
N | 0.0482226 |
D | 0.0472308 |
T | 0.0430525 |
C | 0.0334780 |
L | 0.0299851 |
P | 0.0245926 |
V | 0.0177271 |
H | 0.0129726 |
Q | 0.0124038 |
G | 0.0121887 |
F | 0.0101579 |
B | 0.0100850 |
Z | 0.0043461 |
X | 0.0034163 |
J | 0.0030226 |
K | 0.0000292 |
Y | 0.0000292 |
Metodologia.Nós escolhemos o romance 'Memórias Póstumas de Brás Cubas' de Machado de Assis (fonte aqui). Após baixar o arquivo para o nosso computador, fizemos alguns 'ajustes' no texto original. O primeiro passo foi converter de arquivo '.PDF' para o formato '.txt'. Depois, convertemos as vogais acentuadas (ex: 'ü', 'é', 'ã', ...) em não acentuadas ('u', 'e', 'a', ...). Também consideramos todas as letras como maiúsculas (ex: 'a' = 'A', 'b' = 'B'). Caracteres de pontuação (ex: ',', '.', ';', ...) e espaço em branco não foram considerados (o caractere mais frequente é o espaço em branco). Neste experimento 'desprezamos' o 'ç'.
Limitações
Claramente, a escolha do texto de Machado de Assis foi arbitrária. Poderíamos ter escolhido, por exemplo, um escritor mais contemporâneo. Poderíamos também ter compilado um conjunto de textos de origens e fontes distintas para servir como arquivo de trabalho. Um texto de química certamente apresenta uma distribuição de frequência distinta de um texto puramente literário. Poderíamos também ter feito distinção entre vogais acentuadas de não acentuadas, incluído o 'ç', etc.
Entropia e Comprimento Médio de Símbolos
A entropia, no contexto da teoria da informação, mede a incerteza ou o conteúdo de informação de uma fonte de dados. É fundamental para entender a eficiência da codificação e compressão em comunicação digital.
A entropia H de uma fonte com n símbolos é dada por:
\[ H = -\sum_{i=1}^{n} p_i log_2(p_i) \]
onde pi é a probabilidade do símbolo i.
- Alta entropia: Maior incerteza, mais bits necessários para codificação.
- Baixa entropia: Maior previsibilidade, menos bits necessários.
Aplicações:
- Compressão de dados: Define o limite teórico para compressão sem perda.
- Codificação eficiente: Usada em algoritmos como Huffman e codificação aritmética.
- Criptografia: Fontes com alta entropia geram chaves mais seguras.
- Detecção de erros: Avalia redundância para correção de erros.
Comprimento Médio de Símbolos
O comprimento médio de símbolos $L_{med}$ é a média ponderada dos comprimentos dos códigos atribuídos aos símbolos, dado por:
\[ L_{med} = \sum_{i=1}^{n} p_i l_i \]
onde li é o comprimento do código do símbolo i.
Significado:
- Um código eficiente tem $L_{med}$ próximo da entropia $H$.
- O Teorema de Shannon garante que $L_{med}$ ≥ $H$.
- Códigos como Huffman minimizam $L_{med}$ atribuindo códigos mais curtos a símbolos frequentes.
Exemplo:
Para símbolos A (p=0.5), B (p=0.25), C (p=0.25):
Símbolo |
Probabilidade |
Código |
Comprimento |
A | 0.5 | 0 | 1 bit |
B | 0.25 | 10 | 2 bits |
C | 0.25 | 11 | 2 bits |
Entropia: H ≈ 1.5 bits. Comprimento médio: L = 0.5·1 + 0.25·2 + 0.25·2 = 1.5 bits.
Aplicação: Avalia a eficiência de codificação em compressão e transmissão de dados, minimizando o uso de largura de banda ou armazenamento.
Experimento e resultados.
Usamos o seguinte código Scilab para a leitura do arquivo texto e calcular a sua entropia:
clc; close; close; close; close;
function h=Ht(v); /// Entropia
vL = log2(v);
h = -sum(v.*vL);
endfunction
// Função para ler arquivo e contar frequência de caracteres
function carac=leraquivo(nome_arquivo)
// Abre o arquivo para leitura
fid = mopen(nome_arquivo, 'r');
// Lê todo o conteúdo do arquivo
texto = mgetl(fid);
// Fecha o arquivo
mclose(fid);
// Converte o texto para uma única string
texto = strcat(texto);
// Converte a string em um vetor de caracteres
carac = strsplit(texto);
endfunction
p = [0.3, 0.2, 0.2, 0.2, 0.1];
H = Ht(p);
disp(H);
nome = 'C:\Users\DIPPG\Downloads\memoriasBras2.txt'
caracs = leraquivo(nome);
ncarc = ascii(caracs);
v2 = zeros(1:255);
for k=1:max(size(caracs))
letra = ascii(caracs(k));
if max(size(letra))<2
then
if (letra > 96)&(letra < 123) then letra = letra - 32; end;
v2(letra) = v2(letra) + 1;
end;
end
figure; bar(65:90,v2(65:90),0.1);
/// Mais usadas:
Lt = v2(65:90);
total = sum(Lt);
vmx = [];
pmx = [];
for p=1:25
[mx,px] = max(Lt);
vmx = [vmx, ascii(px+64)];
pmx = [pmx, mx/total];
Lt(px) = 0;
end
disp(vmx);
disp(pmx);
H = Ht(pmx);
disp(H);
O resultado foi:
column 1 to 12
"A" "E" "O" "S" "I" "R" "M" "U" "N" "D" "T" "C"
column 13 to 24
"L" "P" "V" "H" "Q" "G" "F" "B" "Z" "X" "J" "K"
column 25
"Y"
column 1 to 5
0.1454151 0.1295147 0.104944 0.0748605 0.0695045
column 6 to 10
0.0627958 0.05103 0.0489846 0.0482226 0.0472308
column 11 to 15
0.0430525 0.033478 0.0299851 0.0245926 0.0177271
column 16 to 20
0.0129726 0.0124038 0.0121887 0.0101579 0.010085
column 21 to 25
0.0043461 0.0034163 0.0030226 0.0000292 0.0000292
3.9824685
E o gráfico:
Com 25 símbolos (as 25 letras do alfabeto), precisaríamos de 5 bits para representar o alfabeto ($2^5$ = 32 possibilidades). Entretanto, a entropia é um pouco menor que 4 bits, então é possível encontrar uma codificação em que os símbolos tenham em média 4 bits de comprimento.