San Diego’s 1st ever SuperHappyDevHouse was a blast and success! Special thanks to Erica and Richard for hosting the hackathon We had about 17-18 software + hardware folks (and one reporter! we have no idea how that happened). The venue was perfect, people brought snacks, drinks, lawn chairs, and we ordered pizza. Most of the attendees are not surprisingly, from the San Diego Hacker News meetup.
While the attendance was really great good for the SDSHDH1, I suspect that it would have been as much as 30% higher if the semester was in session as many of those who voiced interest are college students from the nearby UCSD. Below are some pictures and videos from the event. I’m already looking forward to the next one! Thanks to all who stopped by—”network effects” is key to having a fun SHDH
Updated v1.0.1 5/21/2010 – Improved the exception handling, and changed xrange(len(inputstring)) to xrange(len(inputstring)-nlen+1)). Thanks to colleague Arik Baratz!
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
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'
Draw out your ideas, share it immediately, and get instant feedback on what works and what don’t. If it’s not working, then shelve it. Some elements of it might pop up later. How do you quickly move from idea –> drawing –> prototype –> to a position where you can say, “this is what I want to spend my life doing”. Or “something I want to put away for now so that I can draw out the next idea.”
This is an awesome 1 hour video that I watched over and over just to make sure I absorbed all the points from the awesome serial entrepreneur himself—Marc Andreessen. If I had more time, I’d transcribe it.
Jay Liew is a software entrepreneur passionate about enabler technologies, currently working on Web and mobile applications.
Here I write about my interests in:
Technology. Python, Django, jQuery, Google Android, scaling web apps, etc.
Startups. All things pertaining to building a successful technology startup
Changing the world. Stories of inspiration about how others change the world for the better by solving important problems faced by many—which I absolutely aspire to do!
Occasionally I post about my love for ice hockey and motorcycles (sport bikes & stunt riding).