Basic search engine

Question

I want to improve efficiency of this search engine. It works in about 10 seconds for a search depth of 1, but 4 minutes at 2 etc.

I tried to give straightforward comments and variable names, any suggestions for improved clarity or style/form would also be welcome.

import urllib2
import collections

def get_page(url):
    #return page html from url
    try:
        return [url,urllib2.urlopen(url).read()]
    except:
        return [url,""]         

def get_next_url(page):
    #goes through page html from a starting position and finds the next url
    start_link = page[1].find('<a href="http')
    if start_link == -1:
        return None, 0
    end_link = page[1].find('"', start_link + len('<a href="'))
    url = page[1][start_link + len('<a href="'): end_link]
    return url, end_link           

def get_all_links(page):
    #returns all urls from a page
    links = []
    while True:
        url,end_link = get_next_url(page)
        if url:
            links.append(url)           
            page[1] = page[1][end_link:]
        else:
            return links

def crawl_web(seed, to_crawl, crawled):
    #calls get_all_links to crawl webpage, updates crawled and to_crawl.
    to_crawl.remove(seed)
    if seed not in crawled:
        new_links = set(link for link in get_all_links(get_page(seed)))
        to_crawl = to_crawl.union(new_links)
        crawled.add(seed)

    return crawled, to_crawl, new_links

def track_depth(url, maxdepth):
    #sets depth of webcrawl, feeds seed url to webcrawler
    depth = 0
    tier = [[url]]
    to_crawl = set([url])
    crawled = set()
    while depth < maxdepth:   
        next_tier = []
        for next_url in tier[depth]:
            crawled, to_crawl, new_links = crawl_web(next_url, to_crawl,
                                                     crawled)
            next_tier += list(new_links)
        tier.append(next_tier)
        depth += 1
    return tier, crawled, to_crawl


def get_next_string(page):
    #finds string in html of page using paragraph markers
    start_string = page[1].find('<p>')
    if start_string == -1:
        return None, 0
    end_string = page[1].find('</p>', start_string + len('<p>'))
    string = page[1][start_string + len('<p>'): end_string]
    return string, end_string

def get_page_words(page):
    #gets all strings on page and converts to word list
    page_string = ''
    to_remove = '#$%^&*._,1234567890+=<>/\()":;!?'
    while True:
        string, end_string = get_next_string(page)
        if string:
            page_string += " " + string           
            page[1] = page[1][end_string:]
        else:
            for i in to_remove:        
                page_string = page_string.replace(i, '').lower()
                page_words = page_string.split()
            return page_words

def word_bank(crawled):
    #creates word index mapping url values to word keys    
    crawled = list(crawled)
    word_count = {}  
    for url in crawled:
        for word in get_page_words(get_page(url)):
            if word in word_count:
                if url in word_count[word]:
                    word_count[word][url] += 1
                else:
                    word_count[word][url] = 1
            elif len(word) < 15:
                word_count[word] = {url: 1}
    return word_count

def search_engine(target_string, word_count):
    #searches word_bank for words in string, returns urls words are found at
    targets = list(set(target_string.split()))
    result =[]
    for word in targets:
        if word in word_count:
            result += word_count[word].keys()
    ans = collections.Counter(result).most_common()
    return ans[0][0], ans[1][0], ans[2][0]


crawled = track_depth("http://xkcd.com/1427/", 2)[1]
print "crawling done"
word_count = word_bank(crawled)
print "word_count done"
#print word_count
print search_engine('starting blogs about', word_count)

Answer 1

The slowest part in this are the network requests - by far.

Firstly during the time when the requests are being done you can use your valuable computing time to parse the text instead of just idling. That requires asynchrony I/O (Not sure if there are python libraries that allow this) or using threads.

A possible way to use threads would be:

• Have a queue of URLs that need to be parsed
• Start some threads that retrieve the content of that URL
• Have one (or more) threads that parse the content

The optimal number of threads is dependent on many factors - you'll have to test that yourself and it will vary based on target machine (CPU type (e.g. how many cores) and load, RAM, network speed, ...) and on the sites that you crawl.

Another speed optimization would be to only parse text that contains information.
So discard images, videos, .js, .css and the myriad of other weird stuff you encounter (e.g. many PDFs would need to be parsed to find out the text (Because it's compressed)).
You can filter out based on the HTTP response field Content-Type.

While those will already reduce the search time you will not archive anything that is just near an order of magnitude near professional search engines.
The main bottleneck still are the network requests - you have limited up/down speed and the computer on the other end also needs processing time for your request.
So cache the content and update it periodically (That has it's own issues mainly with storage capacity and hard drive failure - Google has a paper on how they solved that here).

Then you have some assumptions about the HTML layout of the site that may not always be true.

1. That the p tag will have no attributes at all
2. That href attribute is always the first one, always is separated with only one space and the the link always starts with "http" (not necessarily true for links on the same domain, not true if it starts with "//" which means the same connection type (HTTP vs HTTPS) but another domain)

The proper way to solve these issues would be with a proper HTML parser, e.g. BeautifulSoup.
Please note that actually parsing it will make the crawler slower but more reliable.

Apart from that you should respect the robots.txt

Answer 2

Personally I would recommend lxml over BeautifulSoup. lxml can be a pain to install because of it's dependencies, but it is a newer, higher performance library which implements the ElementTree API and which features lend to more reliable code, for example lxml does not use 'magic attributes'. lxml also supports css selectors which is basically awesome. (I love to talk about the merits of lxml but this is not the place to enumerate them, suffice to say it's a great library and you will profit from having it in your skillset)

@Ralph to improve efficiency tasks which block while waiting for i/o must be spread over separate threads. There is no need to make a separate processing thread and little point in doing so, in practise it works fine if each thread requests a page and processes the page, then moves onto the next page. This in essence is how multithreaded web servers work, each thread receives a request and processes the request and returns the response. Here is a skeleton of a basic multi-threaded site scraper the kind of which I've used several times: (Apologies that this is Python3, the imports might be different in 2.7)

import time
import queue
from threading import Thread
import lxml.html

def process_queue(url_queue, seen, domain):
    while True:
        try:
            url = None
            url = url_queue.get_nowait()
            print('Processing {}'.format(url))
            # Download and parse url
            root = lxml.html.parse(url).getroot()
            # Rewrite relative urls to absolute urls
            root.make_links_absolute(url)
            # Select all elements with href element.
            for e in root.cssselect('[href]'):
                # Discard bookmarks
                href = e.get('href').split('#')[0]
                # Filter external links, and already added links
                if href.startswith(domain) and href not in seen:
                   seen.add(href)
                   url_queue.put(href)
                   # There is a miniscule chance of href being added to queue 
                   # twice. It will just be processed twice. That's all.
            for e in root.iter('p'):
                p_text = e.text_content()
                # ... do something with text of paragraph
        except queue.Empty:
            # Nothing left to do
            return

        finally:
            if url is not None:
                # If we popped a task, mark as complete.
                url_queue.task_done()

def crawl(domain, num_threads=4):
    url_queue = queue.Queue()
    url_queue.put(domain)
    seen = set()
    for i in range(0, num_threads):
        t = Thread(target=process_queue, kwargs={"url_queue": url_queue, "seen": seen, "domain": domain})
        t.start()
        time.sleep(1) # Stagger thread start.
    # Wait for the queue to become empty.
    url_queue.join()
    print('All done!')

if __name__ == '__main__':
    crawl('http://localhost', 4)

That code actually does nothing except crawl the site (i.e. stress test the server), using the number of threads you specify. But I included an example of how you extract text from paragraphs in lxml.

process_queue is a function which pops a url from the queue, processes the url, and adds new urls onto the queue. In order to track depth you could add a tuple (url, depth) to the queue and add no new urls once the depth has reached maximum.

process_queue is run in multiple threads, it simply runs until completion. Once the process_queue function returns (due to the queue being empty) the thread quits automatically. The main thread resumes once url_queue is empty and has had all tasks marked as complete.

This example would require more refined exception handling as an unhandled exception kills the handling thread.

Since it's not easy to find this piece of data, I will mention that in CPython most basic operations on most containers are atomic and thus thread-safe. Thus you can share a set, list, dict or deque over multiple threads. There are some things you cannot do, for example you cannot have one thread iterate over a dict while another thread adds to it. But you can have multiple threads performing simple atomic operations like append, pop, add, 'in' and so on. AFAIK this isn't guaranteed by the language specification, it's just how CPython happens to work.