Data Format

There are 5 separate datasets (1, 2, 3, 4 and 5 grams) with a combined size of 318 GB. There are also other languages, but I only considered English.

Variables:

• n-gram
• year
• occurrences during the year
• pages the n-gram appeared on during the year
• books the n-gram appeared in during the year

Advantages of the Dataset

Anyone who has attempted to write a palindrome knows that it is very challenging to string together words that flow and make any sense. The Google Ngrams dataset is ideal for addressing these issues for a few reasons:

• It comes from actual text in books. Rather than taking words from a dictionary and randomly permuting them into ngrams, the strings are from actual texts and more likely to make sense. Words and phrases that wouldn’t appear in a dictionary are also included for this reason. However, this also means that we need to weed out more strings that aren’t actual words or phrases.
• We can quantify how common the word/phrase is. By using the number of occurrences, we are able to order the palindromes by usage frequency.

Cleaning

I removed ngrams with:

• Special characters or numbers
  • However, apostrophes were kept to allow for contractions (e.g. “don’t nod”)
• Only single characters in each gram (e.g. “A”, or “I I”)
• Year outside of 1990 to 2000
  • I chose a ten year range to sufficiently capture words that don’t occur often but also limit the size of the dataset to avoid unnecesary query time.

I also made all ngrams lowercase to combine ngrams of the same word (e.g. “DID”, “Did” and “did” all become “did”).

Determining whether a string is a palindrome

I used the following code to determine whether a string was a palindrome, which tests whether the (lowercase) string with spaces and apostrophes removed is the same forwards and backwards. That is,

regexp_replace(gram,'\'| ','')= REVERSE(regexp_replace(gram,'\'| ',''))

• I removed spaces to allow for multiple word palindromes (e.g. “If I”).
• I removed apostrophes to allow for contractions (e.g. “Sara’s”).

Word clouds

Below are word clouds of the 1, 2, 3, 4 and 5 grams with size proportional to usage frequency. Note that apostrophes were considered their own gram, which is why a word like “ma’am” is considered a 3gram. We produced less results for the higher values of n, and only three different 5grams (after cleaning), including the famous Sator Square.

Access the data on AWS S3

We accessed the dataset with the desired language and value of \(n\) (English 2grams).

set lang=eng-us-all;
set gram=2gram;

CREATE EXTERNAL TABLE IF NOT EXISTS ngrams (
gram string,
year int,
occurrences bigint,
pages bigint,
books bigint
)
ROW FORMAT DELIMITED FIELDS TERMINATED BY '\t'
STORED AS SEQUENCEFILE
LOCATION 
's3://datasets.elasticmapreduce/ngrams/books/20090715/${hiveconf:lang}/${hiveconf:gram}/';

Clean Data

We create a new table with the ngram and cumulative occurrences between 1990 and 2000. We convert each ngram to lowercase to combine words with difference cases. We also remove ngrams that include characters other than letters, apostrophes and spaces (e.g. numbers and special characters).

CREATE EXTERNAL TABLE IF NOT EXISTS cleaned (
gram string,
cumoccurrences bigint);

INSERT OVERWRITE TABLE cleaned
SELECT LOWER(gram), SUM(occurrences) FROM ngrams 
WHERE 
year >= 1990 AND year < 2000 
AND gram REGEXP '^[A-z\' ]+$'  
GROUP BY LOWER(gram);

Produce palindrome output

We set our output text file (with palindrome ngram and cumulative occurrences) to go into the desired bucket on AWS S3. To determine whether an ngram is a palindrome, we first use regexp_replace() to remove apostrophes and spaces, and then compare the resulting string to the REVERSE() of the string. This allowed us to produce palindromes with contractions such as “don’t nod”. We remove ngrams with only \(n\) length (after spaces/apostrophes are removed) to avoid ngrams such as “I I”. Finally, we ordered the table so that the top entries are the most frequently used ngrams.

set outputbucket=s3n://ngrampalindrome/output/twogram;

CREATE TABLE IF NOT EXISTS palindromengrams (
palindromengram string,
cumoccurrences bigint)
ROW FORMAT DELIMITED FIELDS TERMINATED BY '\t'
STORED AS TEXTFILE
LOCATION '${hiveconf:outputbucket}';

INSERT OVERWRITE TABLE palindromengrams 
SELECT gram, cumoccurrences FROM cleaned 
WHERE LENGTH(regexp_replace(gram,'\'| ',''))>2 
AND regexp_replace(gram,'\'| ','')= REVERSE(regexp_replace(gram,'\'| ','')) 
ORDER BY cumoccurrences DESC;