Python implementation of Normalized Google Distance (Simple web scraping example)

Introduction

Based on the count of google results we can infer the popularity of a word. Also the relationship between the frequency of two words together with respect to its individual frequency is a useful measure of how much two words are related.

Based on these ideas is defined the Normalized Google distance, in this post I show how to implement it in python using basic web scraping tools. The final code can be found here.

The Code

Importing libraries

import requests
from bs4 import BeautifulSoup
import math
import sys

Doing the search and getting the count

Here I implement this function which does a GET to google using headers that specify that we are on a desktop machine (And not on a phone), I also specify the gl parameter to make the search as if I were in USA.

def number_of_results(text):
  headers = {'User-Agent': 'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_10_1) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/39.0.2171.95 Safari/537.36'}
  r = requests.get("https://www.google.com/search?q="+text.replace(" ","+"),params={"gl":"us"},headers=headers)

Then BeautifulSoup is used to extract the html part where the count is specified.

  soup = BeautifulSoup(r.text, "lxml")
  res = soup.find("div", {"id": "resultStats"})

Finally It just prints and returns the parsed number

  print(res.text)
  for t in res.text.split():
    try:
      number = float(t.replace(",",""))
      print("{} results for {}".format(number,text))
      return number
    except:
      pass

  raise Exception("Couldn't find a valid number of results on Google")

Compute the formula

Here we implement the formula specified on wikipedia

# N = number_of_results("the")
N = 25270000000.0
N = math.log(N,2)

def normalized_google_distance(w1, w2):
  f_w1 = math.log(number_of_results(w1),2)
  f_w2 = math.log(number_of_results(w2),2)
  f_w1_w2 = math.log(number_of_results(w1+" "+w2),2)

  return (max(f_w1,f_w2) - f_w1_w2) / (N - min(f_w1,f_w2))

Main Function

All the code is executed from the main function

def main(argv):
  w1 = argv[1]
  w2 = argv[2]
  score = normalized_google_distance(w1,w2)

  print("Score is",round(score,2))
  print("W1='"+ w1+ "' W2='"+ w2+ "'")

# Usage example
# python normalized_google_distance.py shakespeare macbeth
# python normalized_google_distance.py "shakespeare " "macbeth"

main(sys.argv)