Use awk para calcular a frequência das letras

Escreva um script awk para determinar as letras mais (e menos) comuns em um conjunto de palavras.

Recentemente comecei a escrever um jogo onde você constrói palavras usando blocos de letras. Para criar o jogo, eu precisava saber a frequência das letras nas palavras regulares do idioma inglês, para poder apresentar um conjunto útil de blocos de letras. A frequência das letras é discutida em vários lugares, inclusive na Wikipedia, mas eu mesmo queria calcular a frequência das letras.

O Linux fornece uma lista de palavras no arquivo /usr/share/dict/words, então já tenho uma lista de palavras prováveis para usar. O arquivo words contém muitas palavras que eu quero, mas algumas que não quero. Eu queria uma lista de todas as palavras que não fossem palavras compostas (sem hífens ou espaços) ou nomes próprios (sem letras maiúsculas). Para obter essa lista, posso executar o comando grep para extrair apenas as linhas que consistem apenas em letras minúsculas:

$ grep  '^[a-z]*$' /usr/share/dict/words

Esta expressão regular pede ao grep para corresponder a padrões que são apenas letras minúsculas. Os caracteres ^ e $ no padrão representam o início e o fim da linha, respectivamente. O agrupamento [a-z] corresponderá apenas às letras minúsculas a a z.

Aqui está um exemplo rápido do resultado:

$ grep  '^[a-z]*$' /usr/share/dict/words | head
a
aa
aaa
aah
aahed
aahing
aahs
aal
aalii
aaliis

E sim, todas essas são palavras válidas. Por exemplo, "aahed" é a exclamação no pretérito de "aah", como no relaxamento. E um "aalii" é um arbusto tropical espesso.

Agora só preciso escrever um script gawk para contar as letras de cada palavra e depois imprimir a frequência relativa de cada letra encontrada.

Contando letras

Uma maneira de contar letras no gawk é iterar cada caractere em cada linha de entrada e contar as ocorrências de cada letra a a z. A função substr retornará uma substring de um determinado comprimento, como uma única letra, de uma string maior. Por exemplo, este exemplo de código avaliará cada caractere c da entrada:

{
    len = length($0); for (i = 1; i <= len; i++) {
        c = substr($0, i, 1);
    }
}

Se eu começar com uma string global LETTERS que contém o alfabeto, posso usar a função index para encontrar a localização de uma única letra no alfabeto. Expandirei o exemplo de código gawk para avaliar apenas as letras a a z na entrada:

BEGIN { LETTERS = "abcdefghijklmnopqrstuvwxyz" }
 
{
    len = length($0); for (i = 1; i <= len; i++) {
        c = substr($0, i, 1);
        ltr = index(LETTERS, c);
    }
}

Observe que a função de índice retorna a primeira ocorrência da letra da string LETTERS, começando com 1 na primeira letra ou zero se não for encontrada. Se eu tiver um array com 26 elementos, posso usar o array para contar as ocorrências de cada letra. Adicionarei isso ao meu exemplo de código para aumentar (usando ++) a contagem de cada letra conforme aparece na entrada:

BEGIN { LETTERS = "abcdefghijklmnopqrstuvwxyz" }
 
{
    len = length($0); for (i = 1; i <= len; i++) {
        c = substr($0, i, 1);
        ltr = index(LETTERS, c);
 
        if (ltr > 0) {
            ++count[ltr];
        }
    }
}

Imprimindo frequência relativa

Depois que o script gawk contar todas as letras, quero imprimir a frequência de cada letra encontrada. Não estou interessado no número total de cada letra da entrada, mas sim na frequência relativa de cada letra. A frequência relativa dimensiona as contagens de modo que a letra com o menor número de ocorrências (como a letra q) seja definida como 1 e as outras letras sejam relativas a isso.

Começarei com a contagem da letra a e depois compararei esse valor com a contagem de cada uma das outras letras b a z:

END {
    min = count[1]; for (ltr = 2; ltr <= 26; ltr++) {
        if (count[ltr] < min) {
            min = count[ltr];
        }
    }
}

No final desse loop, a variável min contém a contagem mínima para qualquer letra. Posso usar isso para fornecer uma escala de contagem para imprimir a frequência relativa de cada letra. Por exemplo, se a letra com menor ocorrência for q, então min será igual à contagem de q.

Em seguida, percorro cada letra e imprimo-a com sua frequência relativa. Eu divido cada contagem por min para imprimir a frequência relativa, o que significa que a letra com a contagem mais baixa será impressa com uma frequência relativa de 1. Se outra letra aparecer duas vezes mais que a contagem mais baixa, isso letra terá uma frequência relativa de 2. Estou interessado apenas em valores inteiros aqui, então 2,1 e 2,9 são iguais a 2 para meus propósitos:

END {
    min = count[1]; for (ltr = 2; ltr <= 26; ltr++) {
        if (count[ltr] < min) {
            min = count[ltr];
        }
    }
 
    for (ltr = 1; ltr <= 26; ltr++) {
        print substr(LETTERS, ltr, 1), int(count[ltr] / min);
    }
}

Juntando tudo

Agora tenho um script gawk que pode contar a frequência relativa das letras em sua entrada:

#!/usr/bin/gawk -f
 
# only count a-z, ignore A-Z and any other characters
 
BEGIN { LETTERS = "abcdefghijklmnopqrstuvwxyz" }
 
{
    len = length($0); for (i = 1; i <= len; i++) {
        c = substr($0, i, 1);
        ltr = index(LETTERS, c);
 
        if (ltr > 0) {
            ++count[ltr];
        }
    }
}
 
# print relative frequency of each letter
    
END {
    min = count[1]; for (ltr = 2; ltr <= 26; ltr++) {
        if (count[ltr] < min) {
            min = count[ltr];
        }
    }
 
    for (ltr = 1; ltr <= 26; ltr++) {
        print substr(LETTERS, ltr, 1), int(count[ltr] / min);
    }
}

Salvarei isso em um arquivo chamado letter-freq.awk para que eu possa usá-lo mais facilmente na linha de comando.

Se preferir, você também pode usar chmod +x para tornar o arquivo executável por conta própria. O #!/usr/bin/gawk -f na primeira linha significa que o Linux irá executá-lo como um script usando o programa /usr/bin/gawk. E como a linha de comando do gawk usa -f para indicar qual arquivo deve ser usado como script, você precisa do -f suspenso para que a execução letter-freq.awk no shell será interpretado corretamente como executando /usr/bin/gawk -f letter-freq.awk.

Posso testar o script com algumas entradas simples. Por exemplo, se eu alimentar o alfabeto em meu script gawk, cada letra deverá ter uma frequência relativa de 1:

$ echo abcdefghijklmnopqrstuvwxyz | gawk -f letter-freq.awk
a 1
b 1
c 1
d 1
e 1
f 1
g 1
h 1
i 1
j 1
k 1
l 1
m 1
n 1
o 1
p 1
q 1
r 1
s 1
t 1
u 1
v 1
w 1
x 1
y 1
z 1

Repetir esse exemplo mas adicionar uma instância extra da letra e imprimirá a letra e com uma frequência relativa de 2 e todas as outras letras como 1:

$ echo abcdeefghijklmnopqrstuvwxyz | gawk -f letter-freq.awk
a 1
b 1
c 1
d 1
e 2
f 1
g 1
h 1
i 1
j 1
k 1
l 1
m 1
n 1
o 1
p 1
q 1
r 1
s 1
t 1
u 1
v 1
w 1
x 1
y 1
z 1

E agora posso dar o grande passo! Usarei o comando grep com o arquivo /usr/share/dict/words e identificarei a frequência das letras para todas as palavras escritas inteiramente com letras minúsculas:

$ grep  '^[a-z]*$' /usr/share/dict/words | gawk -f letter-freq.awk
a 53
b 12
c 28
d 21
e 72
f 7
g 15
h 17
i 58
j 1
k 5
l 36
m 19
n 47
o 47
p 21
q 1
r 46
s 48
t 44
u 25
v 6
w 4
x 1
y 13
z 2

De todas as palavras minúsculas no arquivo /usr/share/dict/words, as letras j, q e x ocorrem com menos frequência. A letra z também é bastante rara. Não é de surpreender que a letra e seja a usada com mais frequência.