In last week's article about the distribution of letters in an English corpus, I presented research results by Peter Norvig who used Google's digitized library and tabulated the frequency of each letter. Norvig also tabulated the frequency of bigrams, which are pairs of letters that appear consecutively within a word. This article uses SAS to visualize the distribution of bigram frequencies.

Cryptanalysts use the frequency of bigrams as part of a statistical analysis of an encrypted. Certain pairs of letter appear more frequently than others. For example, TH, HE, IN, and ER are pairs of letters that appear most frequently in the 744 billion words that Norvig analyzed.

You can download the SAS program that contains the data and creates all the graphs for this article.

The frequency distribution of bigrams

Norvig tabulated the frequencies of each bigram in the corpus. I created a SAS data set named Bigrams that contains the data. The following SAS/IML statements read the data into a 26 x 26 matrix, which is then transposed so that I can visualize it later by using a heat map. In order to distinguish between bigrams that occur rarely (FC in briefcase; YF in boyfriend) from bigrams that never or almost never appear (JT, QW, ZB,...), I assign a missing value to any bigram that appeared in the corpus less than 0.001% of the time. I then create an index vector (idx) that sorts the bigrams in descending order. I then call the SCATTER subroutine to visualize the frequency distribution of the bigrams:

proc iml;
use Bigrams; read all var {"Prop"}; close;
M = T( shape(Prop, 26, 26) );      /* reshape and transpose data into matrix */
M[loc(M=0)] = .;                   /* replace structural zeros with missing */
V = colvec(M);                     /* vector of proportions */
call sortndx(idx, V, 1) descend=1; /* idx sorts V in descending order */
 
/* scatter plot of all frequencies */
title "Relative Frequency of All Bigrams";
ods graphics / width=800 height=500;
N = countN(M);                    /* count of nonmissing proportions */
call scatter(1:N, V[idx[1:N]]) grid={x y} label={"Rank" "Proportion"};

The scatter plot shows the relative frequencies of 495 bigrams that appear in the corpus. There are 23 bigrams that appear more than 1% of the time. The top 100 bigrams are responsible for about 76% of the bigram frequency. The distribution has a long tail. Bigrams like OX (number 300, 0.019%) and DT (number 400, 0.003%) do not appear in many words, but they appear often enough to make the list.

To a cryptanalyst, the important part of the plot is that there are a small number of bigrams that appear more frequently than others. That means that if you are trying to decrypt a coded message (or solve the daily Cryptoquote!), you can use frequency analysis of bigrams to help crack a simple substitution cipher. The following statements create a scatter plot of the top 23 bigrams and label each marker by the bigram it represents:

Letters = "A":"Z";                             /* labels */
Pairs = rowcat(expandgrid(Letters, Letters));  /* all 26 x 26 pairs */
 
/* scatter plot of top bigrams */
TopN = ncol(loc(M>=0.01));            /* count of proportion > 0.01 */
TopIdx = idx[1:TopN];
TopPairs = Pairs[TopIdx];
title "Bigrams with Relative Frequency > 1%";
call scatter(1:TopN, V[TopIdx]) grid={x y} 
            label={"Rank" "Proportion"} datalabel=TopPairs;
print (T(V[TopIdx]))[c=TopPairs L="Top Bigrams" F=percent7.2];

The top bigrams are shown in the scatter plot to the left. Click to enlarge the graph. The bigram TH is by far the most common bigram, accounting for 3.5% of the total bigrams in the corpus. The bigram HE, which is the second half of the common word THE, is the next most frequent. The next most frequently occurring bigrams are IN, ER, AN, RE, and ON.

A continuous heat map of the proportions of bigrams

Creating a plot or printing out the top bigrams is useful, but as a statistician I am also interested in visualizing the frequency distribution of all 26 x 26 bigrams in a way that makes it clear whether a particular bigram is common, rare, or impossible. The best concise visualization of that information is a heat map of the 26 x 26 matrix of proportions.

By using the new HEATMAPCONT subroutine in SAS/IML 13.1, you can create heat maps that use a continuous color ramp to show values in a matrix. The following statement creates a heat map of the bigram proportions:

/* heat map of bigram frequency with continuous color ramp */
ods graphics / width = 900 height=800;
call HeatmapCont(M) xValues=Letters yValues=Letters 
          xaxistop=1 legendtitle="Proportion";

The relative frequencies are encoded by using the default two-color color ramp. The grey cells are bigrams that were not found in the corpus or were extremely rare. To find a particular bigram, trace down the heat map to find the row that corresponds to the first letter, then trace over until you reach the column of the second letter. Here are some observations about the relative frequencies of bigrams:

• The vowels associate with almost all letters. Only the bigrams IY, UQ, and UW were not found in the corpus when a vowel is the first letter of a bigram. For bigrams that have a vowel as the second letter, only QA, QE, QI, and QO were not found in the corpus.
• Vowels begin more than half of the most common bigrams.
• The consonants N and R start many bigrams. All possible bigrams that begin with these consonants were found in the corpus. The consonants D and S are also frequently found at the beginning of a bigram. The consonants L, H, R, S, and T are often found as the second letter in a bigram. It surprised me that there are so many bigrams with H as the second letter. I can't think of many words that contain BH (abhor), DH (adhere), or HH (hitchhiker).
• The letters J, Q, V, X, and Z have only a few friends that they hang out with. There are few bigrams that begin or end with those letters.
• Some letters like to lead, other like to follow. The letter K is a leader: it begins bigrams frequently, but is less likely to follow another letter. In contrast, the letter F is happy follow other letters, but is reluctant to take the lead.

The heat map visually emphasizes the most frequent and the impossible bigrams. If you want to see the very rare bigrams, create a heat map of the log-counts. You can also bin the values in the matrix and use a discrete set of colors to visualize the data. Both of these ideas are implemented in the SAS program for this article.

What interesting facts about bigrams can you find in the heat map? Are there any common or rare bigrams that surprise you? Leave a comment.