Building a better legal search engine, part 1: Searching the U.S. Code
· Michael Bommarito
As I mentioned last week, I'm excited to give a keynote in two weeks on Law and Computation at the University of Houston Law Center alongside Stephen Wolfram, Carl Malamud, Seth Chandler, and my buddy Dan from CLS. The first part in my blog series leading up to this talk will focus on indexing and searching the U.S. Code with structured, public domain data and open source software.
Before diving into the technical aspects, I thought it would be useful to provide some background on what the U.S. Code is and why it exists. Let's start with an example - the Dodd-Frank Wall Street Reform and Consumer Protection Act. After the final version of HR 4173 was passed by both houses and enrolled in July of 2010, it received a new identifier, Public Law 111-230. This public law, along with private laws, resolutions, amendments, and proclamations, is published in order of enactment in the Statutes at Large. The Statutes at Large is therefore a compilation of all these sources of law dating back to the Declaration of Independence itself, and as such, is the authoritative source of statutory law.
If we think about the organization and contents of the Statutes at Large, it quickly becomes clear why the Code exists. The basic task of a legal practitioner is to determine what the state of law is with respect to a given set of facts at a certain time, typically now. Let's return to the Dodd-Frank example above. Let's say we're in the compliance department at a financial institution and we'd like to know how the new proprietary trading rules affect us. To do this, we might perform the following tasks:
- Search for laws by concept, e.g., depository institution or derivative.
- Ensure that these laws are current and comprehensive.
- Build a set of rules or guidelines from these laws.
- Interpret these rules in the context of our facts.
However, the Statutes at Large is not well-suited to these tasks.
- It is sorted by date of enactment, not by concept.
- It contains laws that may affect multiple legal concepts.
- It contains laws that reference other laws for definitions or rules.
- It contains laws that amend or repeal other laws.
Based on our goal and these properties of the Statutes, we need to perform an exhaustive search every time we have a new question. This is pretty clearly bad if we want to get anything done (but hey, maybe you're not in-house and you bill by the hour). So what might we do to re-organize the Statutes to make it easier for us to use the law?
- Organize the law by concept, possibly hierarchically.
- Combine laws that refer or amend one another.
- Remove laws that have expired or have been repealed.
- Provide convenient citations or identifiers for legal concepts.
A systematic organization of the Statutes at Large that followed these rules would make our lives significantly easier. We could search for concepts and use the hierarchical context of these results to navigate related ideas. We could rest assured that the material we read was near-comprehensive and current. Furthermore, we could communicate more succintly by referencing a small number of organized sections instead of hundreds of Public Laws.
As you might have guessed, this organizational scheme defines the United States Code as produced by the Office of the Law Revision Counsel. While the LRC traditionally distributes copies of the Code as ASCII files on CD-ROMs, they recently began distributing copies of the code in XHTML. We'll be using these copies to build our index, so if you'd like to follow along, you should download them from here - http://uscode.house.gov/xhtml/.
If we'd like to build a legal search engine, the Code is arguably the best place to start. While there are other important statutory and judicial sources like the Code of Federal Regulations or the Federal Reporter, the Code is as close to capital-L Law as it gets.
In this part of the post series, I'm going to build an index of the text of the Code from the 2009 and 2010 LRC snapshots. To do this, we'll use the excellent Apache Lucene library for Java. Lucene is, in their own words, a "a high-performance, full-featured text search engine library written entirely in Java." As we'll see in later posts, Lucene (with its sister project, Solr) is a very easy and powerful tool to develop fast, web-based search interfaces. Before we dive into the code below the break, let's take a look at what we're working towards. Below is a search for the term "swap" across the entire Code. We're displaying the top five results, and these were produced in a little over a second on my laptop.
$ mvn -q exec:java -Dexec.mainClass="org.mjb.searchCodeIndex" -Dexec.args="text swap" documentid:7 U.S.C. 6s currentthrough:20110107 score:2.2053032 itempath: Title 7 CHAPTER 1 >§6s. Registration and regulation of swap dealers and major swap participants documentid:7 U.S.C. 6r currentthrough:20110107 score:2.0396917 itempath: Title 7 CHAPTER 1 >§6r. Reporting and recordkeeping for uncleared swaps documentid:7 U.S.C. 7b-3 currentthrough:20110107 score:1.7781076 itempath: Title 7 CHAPTER 1 >§7b–3. Swap execution facilities documentid:7 U.S.C. 24a currentthrough:20110107 score:1.6279716 itempath: Title 7 CHAPTER 1 >§24a. Swap data repositories documentid:15 U.S.C. 77b-1 currentthrough:20100201 score:1.5701554 itempath: Title 15 CHAPTER 2A >SUBCHAPTER I >>§77b–1. Swap agreements
Building the index: buildCodeIndex.java
The first step is to construct the index of the Code with Lucene. In order to do this, I extract the LRC XHTML files from the ZIPs in-memory, tokenize these XHTML documents into sections, and pass these sections into Lucene's analzyer. This analyzer stems the document's tokens and strips stopwords, leaving only frequency information on the possible terms. This information, along with metadata about the section, is added into the Lucene index. The process took a little over two minutes on my laptop and around three minutes on a c1.xlarge EC2 instance.
/**
* @author Michael J Bommarito II
* @date Apr 9, 2011
* @license MIT, (C) Michael J Bommarito II 2011
*/
package org.mjb;
// Java standard library imports
import java.io.*;
import java.util.*;
import java.util.regex.*;
import java.util.zip.*;
// Lucene imports
import org.apache.lucene.*;
import org.apache.lucene.analysis.*;
import org.apache.lucene.analysis.standard.*;
import org.apache.lucene.document.*;
import org.apache.lucene.index.*;
import org.apache.lucene.store.*;
import org.apache.lucene.util.Version;
import org.htmlparser.*;
import org.htmlparser.visitors.*;
class CodeIndex {
// Lucene Index objects
private IndexWriter indexWriter;
// private IndexWriterConfig indexWriterConfig;
// Pattern matching regular expression objects
private Pattern patternDocumentID, patternUSCKey, patternCurrentThrough,
patternItemPath;
/**
* Constructor that initializes the Lucene index and regular expression
* objects.
*
* @param indexPath
* @throws IOException
*/
public CodeIndex(String indexPath) throws IOException {
// Create the index directory
Directory indexDir = FSDirectory.open(new File(indexPath));
// This syntax works for 3.1; however, Mahout won't play nice, so we
// need to use an older version.
// indexWriterConfig = new IndexWriterConfig(Version.LUCENE_31, new
// StandardAnalyzer(Version.LUCENE_31));
// indexWriter = new IndexWriter(indexDir, indexWriterConfig);
// Construct the Lucene index.
indexWriter = new IndexWriter(indexDir, new StandardAnalyzer(
Version.LUCENE_29), true, IndexWriter.MaxFieldLength.UNLIMITED);
// Compile the regular expressions
patternDocumentID = Pattern.compile("documentid:([^\\s]+)");
patternUSCKey = Pattern.compile("usckey:([^\\s]+)");
patternCurrentThrough = Pattern.compile("currentthrough:([0-9]+)");
patternItemPath = Pattern.compile("itempath:(.+) -->");
}
/**
* This method shuts down the Lucene index.
*
* @throws IOException
*/
public void close() throws IOException {
// Shut down the indexer, but wait for merges
indexWriter.close();
}
/**
* This method parses an HTML document and adds it to the index.
*
* @param htmlBuffer
*/
public void parseHTML(final String htmlBuffer) {
// Keep track of our position in the buffer.
int fragmentStart = 0, fragmentEnd = 0;
String documentString = "";
fragmentStart = htmlBuffer.indexOf("<!-- documentid");
while (fragmentStart > 0) {
// Find the next document or end of file.
fragmentEnd = htmlBuffer.indexOf("<!-- documentid",
fragmentStart + 1);
// Store the substring.
if (fragmentEnd > 0) {
documentString = htmlBuffer.substring(fragmentStart,
fragmentEnd);
} else {
documentString = htmlBuffer.substring(fragmentStart);
}
// Now parse the document.
parseDocument(documentString);
// Set up the next search.
fragmentStart = fragmentEnd;
}
}
private String extractDocumentID(final String documentBuffer) {
/**
* Extract the documentid metadata from the <document>.
*/
// Get the string positions
int fragmentStart = documentBuffer.indexOf("documentid:")
+ "documentid:".length();
int fragmentEnd = documentBuffer.indexOf(" ", fragmentStart);
// Return the substring
if (fragmentEnd > 0) {
return documentBuffer.substring(fragmentStart, fragmentEnd);
} else {
return documentBuffer.substring(fragmentStart);
}
}
private String extractUSCKey(final String documentBuffer) {
/**
* Extract the usckey metadata from the <document>.
*/
// Get the string positions
int fragmentStart = documentBuffer.indexOf("usckey:")
+ "usckey:".length();
int fragmentEnd = documentBuffer.indexOf(" ", fragmentStart);
// Return the substring
if (fragmentEnd > 0) {
return documentBuffer.substring(fragmentStart, fragmentEnd);
} else {
return documentBuffer.substring(fragmentStart);
}
}
private String extractCurrentThrough(final String documentBuffer) {
/**
* Extract the currentthrough metadata from the <document>.
*/
// Get the string positions
int fragmentStart = documentBuffer.indexOf("currentthrough:")
+ "currentthrough:".length();
int fragmentEnd = documentBuffer.indexOf(" ", fragmentStart);
// Return the substring
if (fragmentEnd > 0) {
return documentBuffer.substring(fragmentStart, fragmentEnd);
} else {
return documentBuffer.substring(fragmentStart);
}
}
private String extractItemPath(final String documentBuffer) {
/**
* Extract the itempath metadata from the <document>.
*/
// Get the string positions.
int fragmentStart = documentBuffer.indexOf("itempath:")
+ "itempath:".length();
int fragmentEnd = documentBuffer.indexOf(" -->", fragmentStart);
// Return the substring
if (fragmentEnd > 0) {
return documentBuffer.substring(fragmentStart, fragmentEnd);
} else {
return documentBuffer.substring(fragmentStart);
}
}
private String extractExpCite(final String documentBuffer) {
/**
* Extract the expcite metadata from the <document>.
*/
// Get the string positions.
int fragmentStart = documentBuffer.indexOf("expcite:")
+ "expcite:".length();
int fragmentEnd = documentBuffer.indexOf(" -->", fragmentStart);
// Return the substring
if (fragmentEnd > 0) {
return documentBuffer.substring(fragmentStart, fragmentEnd);
} else {
return documentBuffer.substring(fragmentStart);
}
}
public void parseDocument(final String documentBuffer) {
/**
* This method parses an individual <document> from larger XHTML LRC
* document.
*/
// Get the document-level metadata.
String documentID = extractDocumentID(documentBuffer);
String uscKey = extractUSCKey(documentBuffer);
String currentThrough = extractCurrentThrough(documentBuffer);
String itemPath = extractItemPath(documentBuffer);
String expCite = extractExpCite(documentBuffer);
int fieldStart = 0, fieldEnd = 0;
// Now split the document into fields.
String fieldString = "", textHead = "", textStatute = "";
fieldStart = documentBuffer.indexOf("<!-- field-start");
while (fieldStart > 0) {
fieldEnd = documentBuffer.indexOf("<!-- field-end", fieldStart + 1);
// Store the substring.
if (fieldEnd > 0) {
fieldString = documentBuffer.substring(fieldStart, fieldEnd);
} else {
fieldString = documentBuffer.substring(fieldStart);
}
// Parse the fields depending on type.
if (fieldString.contains("field-start:head")) {
textHead = extractFieldText(fieldString);
} else if (fieldString.contains("field-start:statute")) {
textStatute = extractFieldText(fieldString);
}
// Find the next field.
if (fieldEnd > 0) {
fieldStart = documentBuffer.indexOf("<!-- field-start",
fieldEnd);
} else {
fieldStart = -1;
}
}
try {
indexDocument(documentID, uscKey, currentThrough, itemPath,
textHead, textStatute);
} catch (Exception E) {
E.printStackTrace();
}
}
private String extractFieldText(final String fieldBuffer) {
/**
* Parse the field buffer and return the text.
*/
// Create the parser and visitor.
Parser htmlParser = Parser.createParser(fieldBuffer, "UTF-8");
TextExtractingVisitor textVisitor = new TextExtractingVisitor();
try {
// Now try to parse the string and store the text.
htmlParser.visitAllNodesWith(textVisitor);
return textVisitor.getExtractedText().trim();
} catch (Exception E) {
return "";
}
}
private void indexDocument(String documentID, String uscKey,
String currentThrough, String itemPath, String head, String text)
throws IOException {
/**
* This method actually writes the document into the index.
*/
if ((text.length() == 0) || (documentID.length() == 0)) {
return;
}
// Create document.
Document doc = new Document();
doc.add(new Field("documentid", documentID, Field.Store.YES,
Field.Index.NOT_ANALYZED));
doc.add(new Field("usckey", uscKey, Field.Store.YES,
Field.Index.NOT_ANALYZED));
doc.add(new Field("currentthrough", currentThrough, Field.Store.YES,
Field.Index.NOT_ANALYZED));
doc.add(new Field("itempath", itemPath, Field.Store.YES,
Field.Index.ANALYZED));
doc.add(new Field("head", head, Field.Store.YES, Field.Index.ANALYZED,
Field.TermVector.YES));
doc.add(new Field("text", text, Field.Store.NO, Field.Index.ANALYZED,
Field.TermVector.YES));
// Write into index.
indexWriter.addDocument(doc);
}
}
/**
* This class is the driver that processes ZIP files to construct a CodeIndex.
*/
public class buildCodeIndex {
// CodeIndex object
private static CodeIndex codeIndex;
public static void main(final String[] args) {
// Check that a proper command line is passed and fail if not.
if (args.length == 0) {
System.err.println("Usage: buildCodeIndex <path to ZIP files>");
System.exit(-1);
}
// Now check that the argument is a directory that exists.
File directory = new File(args[0]);
if (!directory.exists() && directory.isDirectory()) {
System.err.println("Usage: buildCodeIndex <path to ZIP files>");
System.err
.println("The specified path to ZIP files does not exists.");
System.exit(-1);
}
try {
// Create the CodeIndex object.
codeIndex = new CodeIndex("index/");
// Start the indexing by processing the directory.
processDirectory(directory);
// Shut down the index.
codeIndex.close();
} catch (Exception E) {
E.printStackTrace();
System.exit(-1);
}
}
/**
* This method processes the ZIP files in a given directory. These ZIP files
* should be obtained from this URL: http://uscode.house.gov/xhtml/
*
* @param directoryPath
* : path to the directory that contains the U.S. Code ZIP files.
*/
private static void processDirectory(final File directory) {
// Build the sorted list of files
File[] fileList = directory.listFiles();
java.util.Arrays.sort(fileList);
// Iterate over all files
for (File f : fileList) {
// Check if this is a ZIP file and process it if so.
if (f.getName().toLowerCase().endsWith(".zip")) {
System.out.println("Processing " + f.getAbsolutePath());
processZIP(f.getAbsolutePath());
}
}
}
/**
* This method process a specific ZIP file that should contain the XHTML
* files from the Law Revision Counsel at the U.S. House of Representatives.
*
* @param fileName
* : File name of the ZIP to be processed.
*/
private static void processZIP(final String fileName) {
// Try to open the ZIP file and return if we can't.
final ZipFile zipFile;
try {
zipFile = new ZipFile(fileName);
} catch (Exception E) {
E.printStackTrace();
return;
}
// Now iterate over all entries in the ZIP file and parse the HTML ones.
for (final Enumeration<? extends ZipEntry> entryList = zipFile
.entries(); entryList.hasMoreElements();) {
// Get the current entry
ZipEntry entry = entryList.nextElement();
// Now read the entry and process it if non-null.
String entryBuffer = readZIPEntry(zipFile, entry);
if (entryBuffer != null) {
codeIndex.parseHTML(entryBuffer);
}
}
}
/**
* This method reads a ZIP entry and returns a String representation of the
* buffer.
*
* @param zipFile
* : ZipFile containing the ZipEntry to be read.
* @param zipEntry
* : ZipEntry to be read.
*/
private static String readZIPEntry(final ZipFile zipFile,
final ZipEntry zipEntry) {
InputStream inputStream;
InputStreamReader inputStreamReader;
StringWriter stringBuffer = new StringWriter();
// Read the entry data from the ZIP
try {
// Create the InputStream objects.
inputStream = zipFile.getInputStream(zipEntry);
inputStreamReader = new InputStreamReader(inputStream);
// Read buffer-sized chunks into the StringWriter.
char[] buffer = new char[16384];
while (inputStreamReader.read(buffer, 0, buffer.length) != -1) {
stringBuffer.append(String.valueOf(buffer));
}
// Close the InputStream objects.
inputStreamReader.close();
inputStream.close();
// Return the string buffer.
return stringBuffer.toString();
} catch (Exception E) {
// Handle the exception.
E.printStackTrace();
return null;
}
}
}
Source: https://gist.github.com/mjbommar/912731
Searching the index: searchCodeIndex.java
Once we've built the index, we need to build a tool to search it. The code below is an example of a simple, single term search interface for the index. The results above for the "swap" term are an example of the output of this program.
/**
* @author Michael J Bommarito II
* @date Apr 9, 2011
* @license MIT, (C) Michael J Bommarito II 2011
*/
package org.mjb;
// Java standard library imports
import java.io.*;
// Lucene imports
import org.apache.lucene.document.Document;
import org.apache.lucene.index.*;
import org.apache.lucene.search.*;
import org.apache.lucene.store.*;
public class searchCodeIndex {
// Lucene index searcher
private static Searcher indexSearcher;
public static void main(String[] args) {
// Check if the proper command line was passed.
if (args.length != 2) {
System.err.println("Usage: searchCodeIndex <field> <term>");
System.exit(-1);
}
// Load the index
loadIndex("index/");
// Setup the query
Term term = new Term(args[0], args[1]);
Query termQuery = new TermQuery(term);
try {
// Execute the search and iterate over the top documents.
TopDocs topDocs = indexSearcher.search(termQuery, 5);
ScoreDoc[] scoreDosArray = topDocs.scoreDocs;
for (ScoreDoc scoredoc : scoreDosArray) {
// Retrieve the matched document and show relevant details
Document doc = indexSearcher.doc(scoredoc.doc);
// Output basic document information
String documentID = doc.getField("documentid").stringValue();
System.out.println("documentid:"
+ documentID.replace("_", " U.S.C. "));
System.out.println("currentthrough:"
+ doc.getField("currentthrough").stringValue());
System.out.println("score:" + scoredoc.score);
// Output the path information for the document
String[] paths = doc.getField("itempath").stringValue()
.split("/");
String tabBuffer = "";
System.out.println("itempath:");
System.out.println("Title "
+ Integer.valueOf(documentID.split("_")[0]));
for (int i = 2; i < paths.length - 1; i++) {
System.out.println(tabBuffer + paths[i]);
tabBuffer += ">";
}
System.out.println(tabBuffer
+ doc.getField("head").stringValue());
System.out.println();
}
} catch (Exception E) {
E.printStackTrace();
}
}
private static void loadIndex(String indexPath) {
// Load the index searcher
try {
Directory indexDir = FSDirectory.open(new File(indexPath));
indexSearcher = new IndexSearcher(indexDir);
} catch (Exception E) {
E.printStackTrace();
}
}
}
Source: https://gist.github.com/mjbommar/912734
Compiling the project: pom.xml
Last but not least, you might also want to use Maven to compile and manage this project. If you do, here's the pom.xml that goes along with the code.
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>org.mjb</groupId>
<artifactId>uscs</artifactId>
<version>0.1</version>
<packaging>jar</packaging>
<name>uscs</name>
<description>United States Code Search</description>
<url>http://maven.apache.org</url>
<properties>
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
</properties>
<dependencies>
<dependency>
<groupId>junit</groupId>
<artifactId>junit</artifactId>
<version>3.8.1</version>
<scope>test</scope>
</dependency>
<dependency>
<groupId>org.apache.lucene</groupId>
<artifactId>lucene-core</artifactId>
<version>3.0.2</version>
</dependency>
<dependency>
<groupId>org.htmlparser</groupId>
<artifactId>htmlparser</artifactId>
<version>1.6</version>
</dependency>
</dependencies>
<build>
<plugins>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-compiler-plugin</artifactId>
<configuration>
<source>1.5</source>
<target>1.5</target>
</configuration>
</plugin>
</plugins>
</build>
</project>
Source: https://gist.github.com/mjbommar/912853
Stay tuned next week for the next part in the series. I'll be using Apache Mahout to build an intelligent recommender system and cluster the sections of the Code.