Jump to: Results summary, Complete results

The primary goal of the KType project is to improve communication for people with disabilities. Typing long words and sentences can be very difficult for such users and the best way to reduce the discomfort is to predict what they want to type based on just a few keystrokes. Chances are that a user who starts to type “goo” wants to say “good morning” or “good bye”. Search engines like Google do a great job at showing possible search phrases with just a few letters. Google Scribe is another good example of predictive typing.

Since the users of the KType iPad app could be offline for long periods, the predictive typing feature cannot rely on any web service. Once I knew I had to build my own auto-complete suggestion database, I started to look for large text datasets. Project Gutenberg makes tens of thousands of books available but normal people don't talk like that. For the same reason, I can't use text from Wikipedia, news articles, or even personal blogs. Where do people type normally? In personal emails, instant messages, text/sms messages, and luckily for me, Twitter. I came across a rich dataset with over 9 million tweets by Infolab via reddit and immediately started data crunching.

Predicting what word or phrase a user is trying to type depends on the text they have already typed. The phrase “you for” could be “you for the” if it was preceded by “thank”, otherwise it could be “you forgot my” or “you forgot to”. The simplest way to guess what word or phrase comes next would be to analyze the 9 million short sentences written by over a hundred thousand people and count all the 2-3-4 word phrases they use and how often. These phrases are called n-grams where 'n' is the number of words in the phrase. N-grams are relatively easy to generate from plain-text and I extracted 1-grams (or single words) in my US Presidential Tag-Cloud project a few years ago. For KType's prediction algorithm, I think 1-4-grams would be sufficient.

Each line of the Infolab tweet data that I obtained contained a unique ID for each user, a unique ID for each tweet, the tweet text, and the time it was posted. For my purposes, I only needed the user's ID and tweet text. To keep things simple for KType users, I limited the n-grams to lowercase alphabets only: a-z. So there are no punctuation marks, quotes, capital letters, numbers, URLs, emoticons/smileys, or special characters. For my purposes, that is more than sufficient. If you want a more thorough n-gram list, you can check out Google Books Ngram Viewer dataset.

Initially, I only looked at the raw tweet text and created my 1-4-gram tables based solely on how many times a word or phrase was used. Naturally, words like 'the', 'of', 'in' showed up on the top but surprisingly words like 'gangsta' and 'apache' also featured quite high. Digging in, I found that some users were typing the latter phrases way too many times, possibly band names or song lyrics. That's why I started looking at the user's ID to limit the effect a single user could have on the weight of a given word or phrase.

After playing with a sample of 25,000 tweets, I ended up with a simple formula that appeared to work well in ensuring that common words and phrases rank high and the few users who repeated their own company, band, or product names too many times couldn't skew the results drastically.

N-gram score = (101 points when a user first mentions an n-gram) + (1 point for each additional time they mention it, up to 98 times).

User 1 says "I love puppies"                     101 points (1st time for User 1)
User 1 says "Also I love kitties"                  1 point  (2nd time for User 1)
User 2 says "But I love to sleep all day"        101 points (1st time for User 2)
User 1 says "What I love the most is pie"          1 point  (3rd time for User 1)
---------------------------------------------------------------------------------
Total score for 'I love'                         204 points (2 users, 4 mentions)

If any user mentions 'I love' more than 99 times, it will not add any points beyond the first 101 + 98 = 199 points. This means a phrase said by two users just once will always have a higher score than a phrase said 1000 times by a single user. However, it is possible that five people can say a phrase 50 times each (150 * 5 = 750) and that is higher than seven people saying it seven times each.

As a learning experience, I wrote the entire code for this project in Python. The code itself is pretty inefficient and creates huge in-memory arrays. Though I had no problems running the script on 25,000 sample tweets on my laptop, it caused memory errors when I ran it on the 9 million tweets. While it would have been interesting to reprogram the script to use a database instead of arrays, to save my time and energy I just launched an Amazon EC2 instance with 64GB of RAM and ran the program there. Total cost: $2. Absolutely worth it.

Download: ktype-twitter-ngrams.zip (30 mb).

The file contains sample tweet data, the original Python script I used, and the complete 1-2-3-4-gram lists I generated. It does not contain the entire 9 million tweet dataset. I had to prep the Infolab dataset by removing any newline characters within tweets and sorting the entire file by the user ID. So if you download the original source files I used, you will have to do the same before the above Python script can be run.

The following graph plots the calculated weight for the 1000 most popular 1-4 word phrases I found in the 9 million tweets I analyzed. The weight is based on the frequency and popularity of the phrase and is calculated using the n-gram formula mentioned above.

The following table shows the 1000 most popular 1-4 word phrases within the 9 million tweets I analyzed. The associated weight is based on the frequency and popularity of the phrase and is calculated using the n-gram formula mentioned above. I have also included an unedited/uncensored list of top 1000 non-dictionary words used in the tweets. The associated weight is calculated from the n-gram weight for each occurrence of the non-dictionary word in the 4 n-gram lists.