The Sunjay Times

Recently, as I was trying to solve a cryptogram, I wrote tool to parse the bigrams and trigrams from the ciphertext, tally the frequency, and then display the results sorted from most to least frequently occuring bigram and trigram.

First, a quick history of why I did this and how this was handy.

One of the ways to solve a substitution cipher is to do a frequency analysis. Here’s a typical distribution of letters in the English language. Just as it is obvious that the alphabet ‘e’ is by far the most popular in the English language, you can also calculate the most frequently occurring bigram (2 consecutive characters) and trigram (3 consecutive characters). In English, the top most frequently occurring bigrams are ‘th’ (1.52%), ‘he’ (1.28%), ‘in’ (0.94%) (full list from Wikipedia here). For trigrams, the most popular are ‘ th’ (note the leading whitespace), ‘he ‘ (trailing whitespace), followed by ‘the’ (full list here). The biggest assumption here is that the plaintext is in English. If it’s in say, German, then you’ll have to find the corresponding statistical distribution (Wikipedia has the 1-gram frequency distribution for other languages here).

Whatever the plaintext’s (human) language is, you’d have to find the top n-grams occurring the ciphertext first—and that’s what this calculator will do for you. You can import the python module and call the function calc_ngram, or just write it from your *nix command line.

Example usage from python shell:

>>> from pyngram import calc_ngram
>>> results = calc_ngram('bubble bobble, bubble bobble, bubble bobble', 3) # (inputstring, n-gram size)
>>> for l in results: print l[0] + ' occured ' + str(l[1]) + ' times'
...
bbl occured 6 times
ble occured 6 times
le  occured 3 times
obb occured 3 times
 bo occured 3 times
e b occured 3 times
ubb occured 3 times
bub occured 3 times
bob occured 3 times
, b occured 2 times
 bu occured 2 times
le, occured 2 times
e,  occured 2 times

You can install pyngram from cheeseshop, Python’s package index with

sudo pip install pyngram

For some strange reason, Perl’s CPAN had a few such utilities (just search for ngram, bigram, digram), but there wasn’t any for Python that I could find. Although CPAN’s offering on average looked more feature-rich, pyngram by comparison is more light-weight. It does one thing and one thing only, and it does it efficiently well.

Writing the calculator was actually the easiest part. Putting it together in a nice package for the pypi repository and making sure it works with pip was the most time consuming part! But it’s worth it, because now that I’ve been through the process once (whole topic on its own), I can easily do it again. Contributing a small module to open source gives me a small jolt of happiness

Here’s the source code. Enjoy!

#!/usr/bin/env python
"""
 A simple Python n-gram calculator.

 Given an arbitrary string, and the value of n as the size of the n-gram (int), this module
 will show you the results, sorted from most to least frequently occuring n-gram.

 The 'sort by value' operation for the dict follows the PEP 265 recommendation.

 Quick start:

 >>> from pyngram import calc_ngram

 method expects inputstring as 1st arg, size of n-gram as 2nd arg

 >>> calc_ngram('bubble bobble, bubble bobble, bubble bobble', 3)

 Or just run it from the command line prompt:
 user@host:~$ ./pyngram.py

 Enjoy!

 Jay Liew
 @jaysern

"""

__version__ = '1.0'
__author__ = 'Jay Liew' # @jaysern from @websenselabs
__license__ = 'MIT'

from operator import itemgetter

def calc_ngram(inputstring, nlen):
    if nlen < 1:
        raise ValueError, "Uh, n-grams have to be of size 1 or greater. Makes no sense to have a 0 length n-gram."

    if len(inputstring) < 1:
        raise ValueError, "umm yeah, ... the inputstring has to be longer than 1 char"

    # now, fish out the n-grams from the input string
    ngram_list = [inputstring[x:x+nlen] for x in xrange(len(inputstring)-nlen+1)]

    ngram_freq = {} # dict for storing results

    for n in ngram_list: # collect the distinct n-grams and count
        if n in ngram_freq:
            ngram_freq[n] += 1
        else:
            ngram_freq[n] = 1 # human counting numbers start at 1

    # set reverse = False to change order of sort (ascending/descending)
    return sorted(ngram_freq.iteritems(), key=itemgetter(1), reverse=True)

if __name__ == '__main__':
    inputstring = raw_input('Enter input string: ')
    nlen_str = raw_input('Enter size of n-gram (int): ')
    nlen = int(nlen_str) # cast string to int

    for t in calc_ngram(inputstring, nlen):
        print t[0] + ' occured ' + str(t[1]) + ' times'

This is a cross-posting from my company’s blog post here: http://community.websense.com/blogs/securitylabs/archive/2010/05/20/a-simple-n-gram-calculator-pyngram.aspx.