Tuesday, July 8, 2008

Stemming, Part 1: Introduction

What Is Stemming?

One problem with the tokenizer we’ve developed is that it doesn’t recognize any relationship between the same word with different endings, between, say, cat and cats or between walk, walks, walked, and walking. One way to identify those relationships is by using stemming, a process that removes the suffixes from a word (-s, -ed, or -ing) and returns just the word’s base (cat or walk).

Porter Stemmer

There are various algorithms to do this automatically. One of the most common is the Porter Stemmer, developed by Martin Porter in 1980, and available online for a variety of programming languages. This web site also has some test data and its expected output, and we’ll test our implementation against that.

In this section of the series, we’ll build a stemmer using the original C version of the algorithm as a guide. Don’t worry, though: you don’t need to know C to follow along here.

Although stemming may seem a minor process, it’s actually more complex than the simple tokenization we implemented earlier. Essentially, it walks the word being stemmed through five steps:

  1. Get rid of plurals, -ed, and -ing, and turn -y to -i, so it will be recognized as a suffix in later steps;
  2. Collapse multiple suffixes, such as -ational, -ator, -iveness, and others, to a single suffix, such as -ate, -ate, and -ive, respectively;
  3. Collapse a different set of multiple suffixes or remove a small set of single suffixes;
  4. Remove a set of suffixes including -ance, -ic, and -ive; and
  5. Remove final -e and change -ll to -l in some circumstances.

This process is going to require more programming constructs and data structures than we’ve used so far. But then, what we’ve used up to now is pretty basic, and the new constructs will be necessary for anything but the most simple programs.

Functional Programming

I said earlier that I’m using the C implementation of the Porter Stemmer as a reference implementation. But C is a very different programming language than Clojure. C is imperative: Programs in C are composed of a series of statements that operate primarily by changing data.

However, as I’ve mentioned before, Clojure is a [functional language][functional]: Programs in Clojure are composed of functions that are put together and that transform data without changing it.

A Contrived Example

For example, a word processor written in C would make changes directly to the document. Each change would obliterate what had been there before it. The final draft of a paper in this program might be perfect, but the program would have no record of how it got to be that way.

A word processor written in Clojure would be different, though. Instead of obliterating parts of a document as it made changes, it would keep the old version and make the changes on a new copy of the document. The final document, in this case, is the sum of the original document plus all the changes that had been made to it.

All of Clojure’s data structures actually keep a reference to the old document and just keep a track of the changes that have been made to it.

(For the rest of this posting, and probably for the rest of this series, I’m going to talk about Clojure making copies of things and changing the copies. That’s not correct. Clojure actually keeps as much of the original uncopied as it can and passes around the original, plus changes. Of course, copy-and-change sounds inefficient—and it is—but what Clojure does is far more efficient. Still, generally, if you think of what Clojure does as copy-and-change, you’ll get the gist of it, and I think it’s less complicated to reason about. It’s certainly less cumbersome to write. )

Now, from the perspective of a user of the word processor, there might not be any difference between the C word processor and the Clojure one. But the Clojure program would work better in certain contexts. For example, imagine that you were editing a document in a collaborative environment, and someone else were editing it simultaneously. With the C word processor, if someone makes a change right after you did, their change would erase any record of yours.

However, with the Clojure, the word processor would be able to see that your friend’s change was to a different version of the document. It could then reconcile these changes.

In fact, Clojure has features for building exactly this kind of collaborative environment. We’ll talk about that later. First, let’s glance at some of the characteristics of functional programming, which we’ll explore them in more detail in coming posts.

Side-Effect-Free Programming

One of the primary rules of functional programming is to avoid side effects. A side effect is a change to a data structure or any other part of the computer’s environment.

To continue the word processor example, say you have a function that adds “The End” to the bottom of a document. An imperative version of the function would simply take the input document, add “The End,” and return the changed document. That modification is a side effect.

The functional version would create a new document that was exactly the same as the original, except it had “The End” at the bottom. It would return the new document, but leave the old one unchanged. That is side-effect free.

Now imagine we have another function that prints a hard copy of a document. Printing—either to the screen or to a printer—is a side effect, but it’s a desirable one. Avoiding side effects is an ideal, but we should be reasonable about it.

Immutable Data Structures

I’ve been talking about creating new data instead of changing them. In the C word processor, the document can be changed. In the Clojure program, it can’t be changed. Not please don’t, not you shouldn’t, not we really recommend not, but you can’t. If you want to change a Clojure data structure, you have to copy-and-change.

Fortunately Clojure makes this easy. Instead, Clojure’s built-in functions never modify a data structure. Instead, they return a modified copy of the data structures they operate on.

Thus, if you limit yourself to use Clojure’s native, immutable data structures, you will be avoiding side effects. In the code for this series, we’re going to stick with Clojure’s data structures every chance we have.

Caveat: Dysfunctional Java

Of course, Java’s data structures are anything but immutable. Any time you use them, you’re risking losing the benefits of functional programming. This isn’t critical now, but once we start working in a concurrent (i.e., collaborative) environment, using Java data structures invites problems.

I’m sure I’ll harp on this more later.

First-Order Functions

At its heart, functional programming is about using functions as data.

In Clojure, the word processing function to add “The End” to a document is a function that can be passed to another function. It can be wrapped in a function that takes a directory of documents and adds “The End” to all of them.

We’ve already seen how functions are data in their own right. Remember how we used map and filter to implement stop words.

The benefits to using functions in this way is that each function is usually small enough to see what it does easily, and programs are easier to think about, to test, and to understand.

Getting Started

Enough talk. Let’s code.

To keep things neat, put the stemmer in its own file and its own namespace: Create a new file in the same directory as word.clj, and name this file porter.clj. Now add this to the top of the file:

(in-ns 'porter)
(clojure/refer 'clojure)

That’s enough programming for one day, don’t you think?

For the next posting, we’ll take tour of some of the primary Clojure data structures, and we’ll consider what would be the best way to represent the stemmer’s work-in-progress, its working state.

Sunday, July 6, 2008

Hiatus

Hey. This is a short post to let you know I haven’t disappeared: life’s just gotten in the way.

My wife had a kidney stone (it’s passed now).

July 4th weekend.

And this blog. The next topic—stemming—is going to take longer than I’d planned. It’s going to touch on a lot of topics that I wanted to put off to later. So I’m taking some time to figure out the best way to approach things.

But I’m still here.

Tuesday, July 1, 2008

Tokenization: Part 8, Summary

Have we really been covering tokenizing for seven posts? I thought it has been much longer than that.

Looking back on it, however, we’ve really talked about many things besides tokenizing and stop words:

  • regular expressions;
  • string and number literals;
  • variables;
  • calling functions;
  • creating functions;
  • saving source code;
  • namespaces;
  • calling Java methods;
  • higher-order functions;
  • sequence literals;
  • quoting;
  • sets;
  • sets as functions;
  • function overloading; and
  • recursive functions.

Many of these things we only touched on, and we’ll revisit them later in more depth. However, these are all basic concepts that we’ll use over and over during this series.

In the meantime, feel free to pat yourselves on the back!

For the next posting, we’ll start creating a filter to stem the tokens, which we’ll use as an excuse to explore functional programming in more detail.

Monday, June 30, 2008

Tokenization: Part 7, File Reading

So far, we’ve only tokenized data from strings that we’ve typed in. Today, let’s learn how to tokenize the text in a file.

slurp

The easiest way to read in the data from a file is using the slurp function. It takes a file name and returns the contents of that file as a string:

user=> (slurp "LICENSE.txt")
"Copyright (c) 2008, Eric Rochester\nAll ...."

We can then pass that string to tokenize-str to get the list of tokens in the file:

user=> (take 10 (word/tokenize-str (slurp "LICENSE.txt")))
("copyright" "c" "2008" "eric" "rochester" "all" "rights" "reserved" "redistribution" "and")

(take pulls the first n items from a list and returns them.)

tokenize

Of course, it would be nice to have this wrapped into its own function, so let’s add this into word.clj after tokenize-str:

(defn tokenize
  ([filename]
   (tokenize-str (slurp filename)))
  ([filename stop-word?]
   (tokenize-str (slurp filename) stop-word?)))

This function works just like tokenize-str, except it takes a filename and returns the tokens in that file.

Warning!

There’s one big problem with tokenize. Try to tokenize a file that’s several hundred gigabytes in size, and you’ll probably find that problem quickly: it reads the entire file into memory all at once.

There are ways, such as reading the file a line at a time and tokenizing that, to deal with this problem, and Clojure actually makes it relatively easy to do this. However, to keep things simple, at this we’re going to leave tokenize the way it is.

At this point, just keep this limitation in mind. You have been warned.

Friday, June 27, 2008

Tokenization, Part 6: Function Overloading

In the last posting, we added the ability to filter a list of input tokens with a list of stop words, usually words that are so common that they aren’t interesting for many types of analysis. But because we don’t want to use a stop list every time, we didn’t add such filtering to the tokenize-str function. Today, we’ll do that.

Function Overloading

Clojure allows what can be called function overloading. Basically, you can have several different versions of the same function all assigned to the same variable name. Each version has to have a different number of arguments. (The number of arguments is sometimes referred to as the function’s arity, so each different version of the function has to have a different arity.) Since the overloaded functions have different argument lists, Clojure can tell which version to use when you call that function.

(Actually, calling this function overloading is misleading. That makes it sound as if we’re assigning multiple function objects to the same variable. The overloading really happens inside a function object, and a single function object is assigned to a variable.)

For reference, here is the current version of tokenize-str and an example of using it and filtering with a stop words list:

(defn tokenize-str [input-string]
  (map to-lower-case (re-seq token-regex input-string)))

(filter (complement stop-words) (tokenize-str "Input string here."))

To define tokenize-str as an overloaded function, wrap each set of arguments and the function body that belongs with it in parentheses:

(defn tokenize-str
  ([input-string]
   (map to-lower-case (re-seq token-regex input-string))))

Next add another set of arguments plus function body on the same parentheses-level as the one already there:

(defn tokenize-str
  ;; This is the first, original version of the function.
  ([input-string]
   (map to-lower-case (re-seq token-regex input-string)))
  ;; This is the second, overridden version of the function.
  ([input-string stop-word?]
   (filter (complement stop-word?)
           (map to-lower-case (re-seq token-regex input-string)))))

There are a couple of things that are new here. Let’s break them down.

First, I’ve included a couple of comments. When Clojure reads a semicolon (";"), it ignores everything to the end of the line. Comments are there for you to read.

Second, I’ve included a new override for the function that takes two arguments (arity 2, also written tokenize-str/2). The second argument is a function that returns true if a token is a stop word. filter then calls the complement of this function on what is essentially the body of the original version of tokenize-str (tokenize-str/1).

(Hint: It can be difficult to read functional programming. Sometimes it’s easier to read from right to left. First, look at (re-seq ...) and read left to (map ...) and (filter ...).)

So how do we use this? Call (load-file "word.clj") to load the most recent code, and let’s run the example from yesterday with this function.

user=> (word/tokenize-str "The cat in the hat.")
("the" "cat" "in" "the" "hat")
user=> (word/tokenize-str "The cat in the hat." word/stop-words)
("cat" "hat")

Recursive Functions

This works, but it’s a little messy. What if we want to change how we tokenize at the most basic level? We’ll need to change our code in two places, and that’s twice as many places to make an error.

It would be useful if we could call the first version of the function from inside the second version, and we can. Just call it the way we would from any other place in the code. It would look like this:

(defn tokenize-str
  ;; This is the first, original version of the function.
  ([input-string]
   (map to-lower-case (re-seq token-regex input-string)))
  ;; This is the second, overridden version of the function.
  ([input-string stop-word?]
   (filter (complement stop-word?) (tokenize-str input-string))))

Now, if we want to modify the way we tokenize, we only need to do it once, in tokenize-str/1 (the original version of the function). tokenize-str/2 only implements stop-word filtering.

Of course, a function calling itself could be dangerous: if you’re not careful, it could end up calling itself forever. Whenever we have a function call itself, we need to make sure that there is a path through the function that must get traveled at some point and that does not call itself. In this case, the first version acts as such a path: if we call the second version, it calls the first version, which just returns with a list of tokens.

Recursion can be a little mind-bending. Don’t worry about that at this point. We’ll see recursion again many times, and soon it will become an old friend.

A little strange, but an old friend nevertheless.

So far, we’ve only been tokenizing strings that we type in. Of course, in practice we’ll want to read data in from a file. Next time, I’ll talk about how to do that.

Thursday, June 26, 2008

Tokenization, Part 5: Stop Words

Stop Words

For many types of analyses, you need to hang onto every token that comes through the pipeline. For other types of analyses, however, you may want to focus on words that carry meaning: names, nouns, and verbs. Plus, words like the, of, and and occur more than any other words in English, and if you aren’t going to be using them, why keep track of them? For example, in a million word corpus (collection of texts) I have laying around, the alone is 6.8% of the total number of tokens. The twelve most frequent tokens (see below) is 25.6% of the total number of tokens. Considering that you’ll often want to be dealing with huge amounts of text, this can free up a tremendous amount of resources!

(I mentioned this above, but I want to reiterate: contrary to expectations, a lot of interesting linguistic stuff is happening with those frequent but “unimportant” items. If you’re interested in them or think you might be, you should probably forgo a stop list, bite the bullet, and process everything.)

To filter out those most-frequent tokens, many NLP applications use a list of stop words. Anything on the list is removed from the stream of input tokens before any further processing is done.

Which and how many stop words to use depends on the analysis you’re going to do. For the purposes of illustration, we’re going to use a list of the 12 most frequent tokens in the corpus I mentioned earlier. Here they are with their frequencies:

the 69969
of 36472
and 28935
to 26191
a 23529
in 21422
that 10789
is 10101
was 9815
he 9795
for 9498
it 9094

Sets

We’ll keep the stop words in a Clojure set. Sets allow you to store items, but no duplicates. You can create a set using the set function or by using a set literal, which is a hash mark and the items in the list surrounded by curly braces.

Open word.clj in your editor and add this near the top of the file, after you define token-regex, maybe:

(def stop-words
  #{"a" "in" "that" "for" "was" "is"
    "it" "the" "of" "and" "to" "he"})

Sets as Functions

So far, we’ve only used functions as functions. That is, every time we’ve called a function, we’ve called it on a function object, things like map and re-seq. But Clojure also allows some other data types to act like functions. A set is one of those. A set/function takes one argument and tests if that argument is in the set.

For example, call (load-file "word.clj") to update your REPL and try this:

user=> word/stop-words
#{"a" "in" "that" "for" "was" "is" "it" "the" "of" "and" "to" "he"}
user=> (word/stop-words "clojure")
nil
user=> (word/stop-words "was")    
"was"

You can see that when we call stop-words with a word that isn’t in the set, it returns nil. nil is just a special value in Clojure and other lisps that means nothing (it’s like None in Python or null in Java), and it always tests false. If the word is in the set, like "was", it returns that item, which will test true.

Great, now we have a list of the stop words and a function that tells whether a given word is a stop word, all in one object. Let’s put it to use.

Filtering Tokens

To filter out the stop words, we’ll use the filter function. It takes a predicate (a function of one argument that returns a true or false value) and a list. It calls the predicate on every item in the list and returns a new list made up of those items from the original list for which the predicate returned true.

This may make more sense with an example:

user=> (filter pos? '(-2 -1 0 1 2))
(1 2)

pos? is a predicate that returns true if a value is positive. You can see that filter here returns all the values in the original list that are positive, that is, for which pos? returned true.

Let’s try this with stop-words:

user=> (filter word/stop-words '("the" "cat" "in" "the" "hat"))
("the" "in" "the")

Hmm. That return all the tokens that are stop words: the exact opposite of what we want. We need something that will return the opposite of what stop-words would return.

Fortunately for us, Clojure defines such a function: complement takes a function and returns a new one that always returns the logical opposite of the original function. Where the first function returns true, the new function returns false, and vice verse.

Let’s try the example above again, this time using the complement of stop-words:

user=> (filter (complement word/stop-words) '("the" "cat" "in" "the" "hat"))
("cat" "hat")

Exactly.

As I mentioned before, you won’t always want to use a list of stop words, so we won’t immediately make it part of the tokenize-str function. However, in the next posting, I’ll show you how to add a set of stop words as an optional argument to tokenize-str.

Wednesday, June 25, 2008

Tokenization, Part 4: Organization

Improved Tokenization

As I’ve already said, the way we’re tokenizing is lacking. One major problem at this point is that "The" and "the" are returned as two separate tokens. To take care of that, we need to convert all tokens to lower-case as they’re processed.

That’s a two-step process: first, convert a token to lower case; second, apply that conversion to each token as it’s read in.

How do we do this?

Java Interop

In Clojure, strings are the same as Java strings: a Clojure string takes the same methods as a Java string, and like a Java string, a Clojure string is immutable: once you’ve created it, you can’t change it.

So now the question is how do we call Java methods?

In fact, it’s fairly simple: to call the length method on a string, use .length (a dot and the method name) as the function to call, and pass the string as the first argument to that function. Other arguments are passed in after the method:

user=> (def a-string "My name")
#'user/a-string
user=> (.length a-string)
7
user=> (.substring a-string 3)
"name"
user=> (.substring a-string 3 5)
"na"

This also works for calling static methods, just pass in the name of the class instead of a class instance as the first argument. For example, the first line below calls the static method Runtime.getRuntime():

user=> (def rt (.getRuntime Runtime))
#'user/rt
user=> (.freeMemory rt)
30462304

(Runtime gets automatically imported from java.lang. Later I’ll show you how to import other Java classes and how to create instances of them.)

Java strings have a toLowerCase method, which will do exactly what we want. The only problem is that Java methods aren’t the same as Clojure functions, so we’ll need to wrap the method call in a function. Open the word.clj file you’ve been working on and add this before tokenize-str:

(defn to-lower-case [token-string]
  (.toLowerCase token-string))

That creates a function called to-lower-case, which just wraps a method call to String.toLowerCase.

Higher-Order Functions

Now we need to solve the second part of the problem: applying to-lower-case to every token as we create it.

Clojure, like all lisps, Python, Ruby, and many other computer languages, treat functions as objects in their own right. That means you can take a function, assign it to a variable (which is what defn does), and pass it around as an argument. Plus, Clojure has a number of functions—called higher-order functions—that take functions as arguments and do interesting things with them, either creating new functions based on the original function or applying that function to a set of data.

map is one of those functions. It takes another function and a sequence, and it applies the function to every item in the sequence. Finally, it returns a new sequence containing the results of applying the function to each item in the input sequence. For example, let’s apply to-lower-case to a sequence of strings (make sure you call (load-file "word.clj") so that to-lower-case is defined in the REPL):

user=> (map to-lower-case '("This" "IS" "my" "name"))
("this" "is" "my" "name")

Now let’s combine map with what’s already in tokenize-str to create a new version of the function that converts all tokens to lower-case:

(defn tokenize-str [input-string]
  (map to-lower-case (re-seq token-regex input-string)))

Call (load-file "word.clj") again and test the new version of tokenize-str:

user=> (tokenize-str "This is a LIST OF TOKENS.")
("this" "is" "a" "list" "of" "tokens")

There we go: all lower-case tokens.

Sequence Literals

In the first map example above, I included something that we haven’t seen before: sequence literals. Sequences, or lists, are a big part of any lisp, including Clojure.

A list in Clojure is printed like they are in all lisps: a space-delimited list of items surrounded by parentheses. They look just like a function call, which is awkward. It means that if you just type in a list, Clojure will try to call it like a function:

user=> ("my" "name")
java.lang.ClassCastException: java.lang.String cannot be cast to clojure.lang.IFn

That’s a poor way of saying that you can’t treat a string like its a function.

To type the list and have Clojure recognize it as a list, you have to quote it: put a single-quote character in front of the list:

user=> '("my" "name")
("my" "name")

Organizing Your Code

So far we haven’t had any problem with variable names clashing with each other. But if we start using different libraries and files written by different people, we could easily run across several that use the same variable name for different things.

How do we get around that? We need some way to keep all those names separate.

Namespaces

Clojure uses namespaces to keep variable names from clashing. (These are different than Java’s packages, if you’re familiar with those.) By default, all of the built-in functions are in the clojure namespace. When you’re in the REPL, everything is in the user namespace. Remember what the REPL prompt looks like?

user=>

The user at the beginning of the prompt tells which namespace we’re currently working in. Clojure indicates which namespace a variable is in by printing the namespace and a forward slash before the variable name. For example, the user/tokenize-str that is printed after loading word.clj indicates that the last variable read in was tokenize-str in the user namespace.

Here we want to define everything we’re working on in a namespace called word. To do that, just add these lines to the top of word.clj:

(in-ns 'word)
(clojure/refer 'clojure)

The first line creates a new namespace, word, and uses that to contain all the variables defined in the rest of the file.

Immediately after the first line, we can’t reference any of the functions that Clojure provides. The second line fixes that, (clojure/refer 'clojure) call makes everything in the clojure namespace available in the word namespace. Remember that clojure/refer references the refer variable in the clojure namespace. So even though the we can’t access Clojure’s built-ins directly at this point, we can still reference them using their full (namespace plus name) names.

(As an aside, notice that in the second line, the second clojure is quoted. That’s because symbols can either be variables or symbol objects in their own rights. Without the quote, Clojure thinks that the symbol is a variable; with the quote, it reads the second clojure as a symbol, which is what refer wants.)

Now, quit Clojure, go back in, and re-load the file. (We want to start with a clear slate; otherwise, the old function definitions will still be hanging around to confuse us.)

user=> (load-file "word.clj")                    
#'word/tokenize-str

The first thing to notice is that the variable returned at the end has a new namespace prefix, word. Let’s try to use it:

user=> (tokenize-str "This is a String.")
java.lang.Exception: Unable to resolve symbol: tokenize-str in this context

Oops. No tokenize-str is found. We have to tell Clojure to look in the word namespace:

user=> (word/tokenize-str "This is a String.")
("this" "is" "a" "string")

Remember to check out the new code from this posting in the Google Code project for word-clj.

We’ve covered a lot—probably too much—for today. Tomorrow, I’ll tackle just one topic: we’ll add stop-list filtering to our tokenizing.