Simple Article Extractor from HTML

The following is a simple article extractor from a given web(html) page. Being in Python its simple and is less than 55 lines of code. I tried this on a few webpages , and was satisfied with the output.
Though i have mentioned the comments as part of the code, the following is a quick HOWTO of how to make modifications to this article extractor:
1) To extract meta information , like author, title, description, keywords etc -   extract the meta tags in line 30, i.e, after the soup object is constructed, but before the tags are stripped. Also, in strip_tags, return a tuple instead of the text alone.
2) Understand how 'unwanted_tags' works; feel free to add the ids/class names that you might encounter. I have mentioned only a few, but more names like "print","popup","tools","socialtools" can be added.
3) Feel free to suggest any other improvements.

from BeautifulSoup import BeautifulSoup,Comment
import re

invalid_tags = ['b', 'i', 'u','link','em','small','span','blockquote','strong','abbr','ol','h1', 'h2', 'h3','h4','font','tr','td','center','tbody','table']
not_allowed_tags = ['script','noscript','img','object','meta','code','pre','br','hr','form','input','iframe' ,'style','dl','dt','sup','head','acronym']

#attributes that are checked for in a given html tag - if present, the tag is removed.
unwanted_tags=["tags","breadcrumbs","disqus","boxy","popular","recent","feature_title","logo","leaderboard","widget","neighbor","dsq","announcement","button","more","categories","blogroll","cloud","related","tab"]

def unwanted(tag_class):
  for each_class in unwanted_tags:
    if each_class in tag_class:
      return True
  return False

#from http://stackoverflow.com/questions/1765848/remove-a-tag-using-beautifulsoup-but-keep-its-contents
def remove_tag(tag):
  for i, x in enumerate(tag.parent.contents):
    if x == tag: break
  else:
    print "Can't find", tag, "in", tag.parent
    return
  for r in reversed(tag.contents):
    tag.parent.insert(i, r)
  tag.extract()

def strip_tags(html):
  tags = ""
  soup = BeautifulSoup(html)
 
  #remove doctype
  doctype = soup.findAll(text=re.compile("DOCTYPE"))
  [tree.extract() for tree in doctype]
 
  #remove all links
  links = soup.findAll(text=re.compile("http://"))
  [tree.extract() for tree in links]
 
  #remove all comments
  comments = soup.findAll(text=lambda text:isinstance(text, Comment) )
  [comment.extract() for comment in comments]
 
  for tag in soup.findAll(True):
    #remove all the tags that are not allowed.
    if tag.name in not_allowed_tags :
      tag.extract()
      continue
   
    #replace the tags with the content of the tag
    if tag.name in invalid_tags:     
      remove_tag(tag)
   
    # similar to not_allowed_tags but does a check for the attribute-class/id before removing it
    if unwanted(tag.get('class','')) or unwanted(tag.get('id','')) :
      tag.extract()
      continue
   
    # special case of lists - the lists can be part of navbars/sideheadings too,
    # hence check length before removing them
    if tag.name =='li':
      tagc = strip_tags(str(tag.contents))
      if len(str(tagc).split()) < 3:
        tag.extract()
        continue
   
    #finally remove all empty and spurious tags and replce it with its content
    if tag.name in ['div','a','p','ul','li','html','body'] :
      remove_tag(tag)
     
  return soup
#open the file which contains the html
#this step can be replaced with reading directly from the url
#however, i think its always better to store the html in the
#  local storage for any later processing.
html = open("techcrunch.html").read()
soup = strip_tags(html)
content = str(soup.prettify())

#write the stripped content into another file.
outfile = open("tech.txt","w")
outfile.write(content)
outfile.close()


If the formatting is screwed up, then you can access the code here or here.

An Evening with Python's itertool module

Why I love Python? Well, have you been to Himalayas and have watched the morning sunrise? There are certain feelings that cannot be explained. The fun of programming in python cannot be compared. Anywayz...more on Python and the associated 'joyness factor' in a later post. :)

Often while working with large datasets with Python, one needs to take extra care of the memory and even the simplest of the programs have the potential to make the system go slow and consume the entire memory. Python itertools module has some nifty functions which you will end up using most of the time while working with large data sets, especially when working with text. I spent sometime playing around with some basic functions in the itertools module which are simple to use and often find usage across various functionalities. Though the python docs do a pretty fine job of explaining the individual itertools functions, this post is just an enumeration of a few handpicked functions that I often use.

The following snippet does a quick bigram and trigram generation of a given line:

from itertools import *
def bigram(line):
  words = line.split()
  for i in izip(words,words[1:]):
    print i
def trigram(line):
  words = line.split()
  for i in izip(words,words[1:],words[2:]):
    print i

sentence = "Python is the coolest language"
bigram(sentence)
trigram(sentence)

If you notice , 'language' is not part of an empty tuple. If you want to fill the last tuple with a default value, use 'izip_longest'

for i in izip_longest(words,words[1:],fillvalue='-'):
  print i

A sentence can have many non-alphabetic characters, 'filter' does a quick job of removing them. It takes a function as an argument and a list. The function is applied on individual elements of the list.

print filter(str.isalpha,words)

'imap' would probably be one of the most jazziest and coolest of the itertools functions. Lets see its usage in the following example. Assume that you want to find out the longest word in a given file which contains a word list. What is the 'conventional' way of doing this?

infile = open('words.txt', 'r')
len_longest_word = 0
while 1:
  word=infile.readline()
  if not word:
    break
  tmp_len = len(word)
  if tmp_len > len_longest_word :
    len_longest_word = tmp_len
print 'len_longest_word :',len_longest_word
infile.close()

 The same when done via imap is just one sentence :) ..as follows. (note : we are reading the entire file in one go).

infile = open('words.txt', 'r')
contents = infile.read()
words = contents.split()
print "len_longest_word:",max(imap(len, words))
infile.close()

Now, lets say we have to analyse the frequency distribution of a few lists or lets say we have to process a group of lists by accessing successive elements, then the following is a very simple and neat way of acheiving this. (Try doing a frequency distribution of n lists containing numbers using 'chain')

from itertools import chain
a=[10,20,30]
b=[100,200,300]
for i in chain(a,b):
  print i

Often, we want to group elements in a dictionary by its values; instead of iterating through the dictionary and writing redundant code, itertools comes with a cool 'groupby' which allows us to specify the dimension in which we want to group.

from operator import itemgetter
d = dict(a=1, b=2, c=1, d=2, e=1, f=2, g=3)
di = sorted(d.iteritems(), key=itemgetter(1))
for k, g in groupby(di, key=itemgetter(1)):
    print k, map(itemgetter(0), g)

 The above example on groupby was obtained from here.

Python Huntington Hill method

The following python code implements the Huntington Hill method which was used to generate the apportionment details in my previous post.

import math

def huntington_hill(popln,num_seats):
  num_states = len(popln)
  representatives = [1]*num_seats
  std_divs = [math.sqrt(2)]*num_states
  for j in range(num_states,num_seats):
    max = 0
    for i in range(1,num_states):
      if (popln[i][1]/std_divs[i]) > (popln[max][1]/std_divs[max]):
        max = i        
    representatives[max] +=  1    
    std_divs[max]=math.sqrt(representatives[max] * (representatives[max]+1))
  return representatives
  
  
POPULATION= [("JAMMU & KASHMIR",10143700),("HIMACHAL PRADESH",6077900),("PUNJAB",24358999),
("CHANDIGARH",900635),("UTTARANCHAL",8489349),("HARYANA",21144564),("DELHI",13850507),
("RAJASTHAN",56507188),("UTTAR PRADESH",166197921),("BIHAR",82998509),
("SIKKIM",540851),("ARUNACHAL PRADESH",1097968),("NAGALAND",1990036),
("MANIPUR",2166788),("MIZORAM",888573),("TRIPURA",3199203),
("MEGHALAYA",2318822),("ASSAM",26655528),("WEST BENGAL",80176197),
("JHARKHAND",26945829),("ORISSA",36804660),("CHHATTISGARH",20833803),
("MADHYA PRADESH",60348023),("GUJARAT",50671017),("DAMAN & DIU",158204),
("DADRA & NAGAR HAVELI",220490),("MAHARASHTRA",96878627),("ANDHRA PRADESH",76210007),
("KARNATAKA",52850562),("GOA",1347668),("LAKSHADWEEP",60650),
("KERALA",31841374),("TAMIL NADU",62405679),("PONDICHERRY",974345),
("ANDAMAN & NICOBAR ISLANDS",356152)
]

NUMBER_SEATS= 545

mps = huntington_hill(POPULATION,NUMBER_SEATS)
for i in range(len(POPULATION)):
  print POPULATION[i][0]+","+str(POPULATION[i][1])+","+str(mps[i])

Huntington-Hill Method on Indian Census Data of 2001

In USA, the apportionment of seats is based on the census taken (based on the population of each the states). The USA Census Bureau uses an algorithm called Huntington-Hill method for apportioning. Watch the following video which explains it :

The algorithm is pretty simple and you have a look at it here.  I ran this algorithm on the India Census data collected in 2001.  I got the present distribution of Lok Sabha seats across states from wikipedia. The following table shows the distribution of seats based on the Algorithm(2nd column) and the 3rd column shows the present scheme of apportionment. The last(and colored) column displays the difference.

I am not sure how the present Indian apportionment process works, but looks like we are not way off from the USA's apportionment process.

Do you know how United Kingdom(UK) computes the apportionment? It would be fun to compare, as India was ruled by East India Company and we can know the correlation between the Indian, American and the British way of apportionment of seats.