The goal of this chapter is to develop a web crawler that tests the “Getting to Philosophy” conjecture, which I presented in “Search Engines”.
In the repository for this book, you’ll find some code to help you get started:
WikiNodeExample.java
contains the code from the previous chapter, demonstrating recursive and iterative implementations of depth-first search (DFS) in a DOM tree.
WikiNodeIterable.java
contains an Iterable
class for traversing a DOM tree. I’ll explain this code in the next section.
WikiFetcher.java
contains a utility class that uses jsoup to download pages from Wikipedia. To help you comply with Wikipedia’s terms of service, this class limits how fast you can download pages; if you request more than one page per second, it sleeps before downloading the next page.
WikiPhilosophy.java
contains an outline of the code you will write for this exercise.
You’ll also find the Ant build file build.xml
. If you run ant WikiPhilosophy
, it will run a simple bit of starter code.
In the previous chapter, I presented an iterative depth-first search (DFS), and suggested that an advantage of the iterative version, compared to the recursive version, is that it is easier to wrap in an Iterator
object. In this section we’ll see how to do that.
If you are not familiar with the Iterator
and Iterable
interfaces, you can read about them at http://thinkdast.com/iterator and http://thinkdast.com/iterable.
Take a look at the contents of WikiNodeIterable.java
. The outer class, WikiNodeIterable
implements the Iterable<Node>
interface so we can use it in a for loop like this:
Node root = ... Iterable<Node> iter = new WikiNodeIterable(root); for (Node node: iter) { visit(node); }
where root
is the root of the tree we want to traverse and visit
is a method that does whatever we want when we “visit” a Node
.
The implementation of WikiNodeIterable
follows a conventional formula:
The constructor takes and stores a reference to the root Node
.
The iterator
method creates a returns an Iterator
object.
Here’s what it looks like:
public class WikiNodeIterable implements Iterable<Node> { private Node root; public WikiNodeIterable(Node root) { this.root = root; } @Override public Iterator<Node> iterator() { return new WikiNodeIterator(root); } }
The inner class, WikiNodeIterator
, does all the real work:
private class WikiNodeIterator implements Iterator<Node> { Deque<Node> stack; public WikiNodeIterator(Node node) { stack = new ArrayDeque<Node>(); stack.push(root); } @Override public boolean hasNext() { return !stack.isEmpty(); } @Override public Node next() { if (stack.isEmpty()) { throw new NoSuchElementException(); } Node node = stack.pop(); List<Node> nodes = new ArrayList<Node>(node.childNodes()); Collections.reverse(nodes); for (Node child: nodes) { stack.push(child); } return node; } }
This code is almost identical to the iterative version of DFS, but now it’s split into three methods:
The constructor initializes the stack (which is implemented using an ArrayDeque
) and pushes the root node onto it.
isEmpty
checks whether the stack is empty.
next
pops the next Node
off the stack, pushes its children in reverse order, and returns the Node
it popped. If someone invokes next
on an empty Iterator
, it throws an exception.
It might not be obvious that it is worthwhile to rewrite a perfectly good method with two classes and five methods. But now that we’ve done it, we can use WikiNodeIterable
anywhere an Iterable
is called for, which makes it easy and syntactically clean to separate the logic of the iteration (DFS) from whatever processing we are doing on the nodes.
When you write a web crawler, it is easy to download too many pages too fast, which might violate the terms of service for the server you are downloading from. To help you avoid that, I provide a class called WikiFetcher
that does two things:
It encapsulates the code we demonstrated in the previous chapter for downloading pages from Wikipedia, parsing the HTML, and selecting the content text.
It measures the time between requests and, if we don’t leave enough time between requests, it sleeps until a reasonable interval has elapsed. By default, the interval is one second.
Here’s the definition of WikiFetcher
:
public class WikiFetcher { private long lastRequestTime = -1; private long minInterval = 1000; /** * Fetches and parses a URL string, * returning a list of paragraph elements. */ public Elements fetchWikipedia(String url) throws IOException { sleepIfNeeded(); Connection conn = Jsoup.connect(url); Document doc = conn.get(); Element content = doc.getElementById("mw-content-text"); Elements paragraphs = content.select("p"); return paragraphs; } private void sleepIfNeeded() { if (lastRequestTime != -1) { long currentTime = System.currentTimeMillis(); long nextRequestTime = lastRequestTime + minInterval; if (currentTime < nextRequestTime) { try { Thread.sleep(nextRequestTime - currentTime); } catch (InterruptedException e) { System.err.println( "Warning: sleep interrupted in fetchWikipedia."); } } } lastRequestTime = System.currentTimeMillis(); } }
The only public method is fetchWikipedia
, which takes a URL as a String
and returns an Elements
collection that contains one DOM element for each paragraph in the content text. This code should look familiar.
The new code is in sleepIfNeeded
, which checks the time since the last request and sleeps if the elapsed time is less than minInterval
, which is in milliseconds.
That’s all there is to WikiFetcher
. Here’s an example that demonstrates how it’s used:
WikiFetcher wf = new WikiFetcher(); for (String url: urlList) { Elements paragraphs = wf.fetchWikipedia(url); processParagraphs(paragraphs); }
In this example, we assume that urlList
is a collection of String
s, and processParagraphs
is a method that does something with the Elements
object returned by fetchWikipedia
.
This example demonstrates something important: you should create one WikiFetcher
object and use it to handle all requests. If you have multiple instances of WikiFetcher
, they won’t enforce the minimum interval between requests.
NOTE: My implementation of WikiFetcher
is simple, but it would be easy for someone to misuse it by creating multiple instances. You could avoid this problem by making WikiFetcher
a singleton, which you can read about at http://thinkdast.com/singleton.
In WikiPhilosophy.java
you’ll find a simple main
method that shows how to use some of these pieces. Starting with this code, your job is to write a crawler that:
Takes a URL for a Wikipedia page, downloads it, and parses it.
It should traverse the resulting DOM tree to find the first valid link. I’ll explain what “valid” means below.
If the page has no links, or if the first link is a page we have already seen, the program should indicate failure and exit.
If the link matches the URL of the Wikipedia page on philosophy, the program should indicate success and exit.
Otherwise it should go back to step 1.
The program should build a List
of the URLs it visits and display the results at the end (whether it succeeds or fails).
So what should we consider a “valid” link? You have some choices here. Various versions of the “Getting to Philosophy” conjecture use slightly different rules, but here are some options:
The link should be in the content text of the page, not in a sidebar or boxout.
It should not be in italics or in parentheses.
You should skip external links, links to the current page, and red links.
In some versions, you should skip a link if the text starts with an uppercase letter.
You don’t have to enforce all of these rules, but I recommend that you at least handle parentheses, italics, and links to the current page.
If you feel like you have enough information to get started, go ahead. Or you might want to read these hints:
As you traverse the tree, the two kinds of Node
you will need to deal with are TextNode
and Element
. If you find an Element
, you will probably have to typecast it to access the tag and other information.
When you find an Element
that contains a link, you can check whether it is in italics by following parent links up the tree. If there is an <i>
or <em>
tag in the parent chain, the link is in italics.
To check whether a link is in parentheses, you will have to scan through the text as you traverse the tree and keep track of opening and closing parentheses (ideally your solution should be able to handle nested parentheses (like this)).
If you start from the Java page (http://thinkdast.com/java), you should get to “Philosophy” (after following seven links, unless something has changed since I ran the code.
OK, that’s all the help you’re going to get. Now it’s up to you. Have fun!