Text retrieval systems - 3A: the Library Builder

[JosAH]

Greetings,

Introduction

Before we start designing and implementing our text builder class(es), I'd like
to mention a reply by Prometheuzz: he had a Dutch version of the entire bible
available, including those apocryphical books. I downloaded the entire shebang,
hacked my King James text processor a bit and now I have two bibles available:
the English 'King James' version and the Dutch 'Staten Vertaling' version.

The Dutch version was even bigger than the King James version, so there :-P

Thanks to Prometheuzz for that valuable piece of text; I really appreciate it.
The Dutch version had less (read: no) inconsistencies while my late neighbour
Dirk's version was a mess here and there. Most of the raw parsing text trouble
happened in Dirk's version. Just a bit of rewriting and quick hacking was
enough to be able to process the Dutch version supplied by Prometheuzz.

The LibraryBuilder

We've got work to do: here's the LibraryBuilder interface again:

public interface LibraryBuilder {
 
    public void preProcess();
    public void postProcess();
 
    public void setTitle(String title);
 
    public void buildGroup(String group);
    public void buildParagraph(String book, String chapter, int para, String text) throws IOException;
 
    public Library build();
}
 

The AbstractBuilder class implements all of this interface and leaves a few
abstract protected methods to be implemented by the specific builders such as
the KJBuilder (for the King James bible version) and the SVBuilder (for the
Staten Vertaling version).

The AbstractBuilder doesn't do all the work itself, i.e. it delegates a lot of
the work to smaller and simpler builders.

Here's the simples builder of them all: the StringsBuilder:

class StringsBuilder extends ArrayList<String> {
 
    private static final long serialVersionUID = 4709552086518644567L;
 
    String[] build() { return this.toArray(new String[size()]); }
}
 

It is simply an implementation of the List<String> interface and it can build
a String[] for us. That's all it does. Remember that the Library itself just
uses a bunch of arrays for the entire text. Arrays can't be resized; that's
one of the reasons I prefer builders that manipulate more flexible, but larger
data structures (classes) while at the end all the arrays are produced.

Here's another simple builder; it builds a single section:

package text.builders;
 
import text.library.Section;
 
class SectionBuilder {
 
    private String name;
    private int index;
    private int total;
 
    SectionBuilder(String name, int index) {
 
        this.name = name;
        this.index= index;
    }
 
    void setTotal(int end) { this.total= end-index; }
 
    String getName() { return name; }
 
    Section build() { return new Section(name, index, total); }
}
 

A Section can be either a section in a group, a book or a chapter. The 'index'
member refers to the corresponding section in an arrray of groups, books or
chapters. The 'total' member is the total number of sections in that particular
array. Also see the previous part of this article for examples of Sections.

The above code can build a Section. The next little builder builds an array
of Sections for us; here it is:

class SectionsBuilder extends ArrayList<SectionBuilder> {
 
    private static final long serialVersionUID = 1476840322184839715L;
 
    boolean addSection(String name, int index, boolean add) {
 
        int n= size();
        SectionBuilder s= (n == 0)?null:get(n-1);
 
        if (add= (add || s == null || !s.getName().equals(name))) {
            add(new SectionBuilder(name, index));
            if (s != null) s.setTotal(index);
        }    
 
        return add;
    }
 
    void postProcess(int total) {
 
        if (size() > 0)
            get(size()-1).setTotal(total);
    }
 
    Section[] build() { 
 
        int n= size();
        Section[] sections= new Section[n];
 
        for (int i= 0; i < n; i++)
            sections[i]= this.get(i).build();
 
        return sections;
    }
}
 

The SectionsBuilder is a List of SectionBuilders (not the different plurals).
When a new Section is about to start, it figures out how many 'things' are
in the previous section. See the addSection() method for that. The boolean
'add' variable (if true) forces a new Section to be build no matter what.
When this variable is false a new Section needs to be built if the name of
the current Section differs from the previous Section, or, if the Section to
be built is the very first Section of them all.

Actually this builder doesn't keep track of Sections at all: it handles
SectionBuilders. The build() method of this builder builds the actual Sections:
it invokes the build() method on every SectionBuilder in its list which in turn
build a single Section each.

Intermezzo

Let's pause for a minute here: we can build single Sections (using the
SectionBuilder) and we can build arrays of Sections (using the SectionsBuilder).
We can also build arrays of Strings using the StringsBuilder.

But we need more: we need to know in which paragraphs a word occurs. In other
words (sic) we need a mapping between a single word and list of indexes in the
paragraphs List. A single paragraph is a String representing the indexes of
the single words and punctuation characters again. (see the previous article
part for how paragraphs are compressed).

More work to do ...

More builders

Here is a WordBuilder; it keeps track of the paragraph numbers in which a word
occurs. It doesn't care which word though; that has been figured out somewhere
else. It does know that it's the 'index'-th word in the entire text. Here's
the implementation:

class WordBuilder {
 
    private int index;
    private List<Integer> paragraphs= new ArrayList<Integer>();
 
    WordBuilder(int paragraph) {
 
        this.index= paragraph;
    }
 
    int getIndex() { return index; }
 
    void addParagraph(int paragraph) { paragraphs.add(paragraph); }
 
    int[] build() {
 
        int n= paragraphs.size();
        int array[]= new int[n];
 
        for (int i= 0; i < n; i++) array[i]= paragraphs.get(i);
 
        return array;
    }
}
 

It basically keeps track of a list of paragraph numbers in which this particular
word occurs and it can build an array of integers, the indexes of the paragraphs
in which the word occurs again. It's not particularly rocket science.

The last builder maps words to WordBuilders; it doesn't come as a surprise that
this builder is named WordMapBuilder; here it is:

class WordMapBuilder extends HashMap<String, WordBuilder> {
 
    private static final long serialVersionUID = -5282145470567550534L;
 
    WordMap build() {
 
        WordMap map= new WordMap();
 
        for (Map.Entry<String, WordBuilder> entry : entrySet()) 
            map.put(entry.getKey(), entry.getValue().build());
 
        return map;
    }
}
 

It maps a word (a String) to a WordBuilder (see above) and it can produce
a WordMap. We'll see that thing later but I think you can guess what it is: it
maps Strings (words) to Integer[]s which are the paragraph numbers in which the
words occur.

AbstractBuilder

We have the constituents for our LibraryBuilder implementation now, let's see
what this implementation is all about. This class is an abstract class because
it leaves a few simple methods to an extending class:

protected abstract String clean(String book, String chapter, 
                int paragraph, String text);
protected abstract Collection<String> getNoise();
 

The first method is supposed to clean up a paragraph text. Most of it has been
cleaned up already in a general way, but a specific builder may want to clean
up the text even a bit more.

In Dirk's King James version some of the words had curly braces and some other
braces around them. I don't want those curly braces, so my KJBuilder's clean()
method implementation looks like this:

protected String clean(String book, String chapter, 
            int paragraph, String text) {
 
    text= text.replaceAll("[({\\[\\]})]", "");
 
    return text.replaceAll("[^\\x20-\\x7e]", "");
}
 

I clean up the text a bit more by removing all the non 7 bits ASCII characters
from the text (remember those 'y's with dots on top from the first article part?
This gets rid of them).

The second method is supposed to return a Collection of Strings that are not
supposed to be indexed at all. Think of words such as 'the', 'a', 'is' etc.
The AbstractBuilder does all the work, it just needs to know *which* words are
supposed to be excluded from the WordMap (see above).

Here is how the KJBuilder (extending the AbstractBuilder) returns its noise words:

private static final Set<String> noise= new HashSet<String>();
 
static { 
    noise.addAll(Arrays.asList(new String[] {
 
        "O", "s",
        "The", "the", 
        "A", "a", "An", "an", 
        "Of", "of", "By", "by", "On", "on",
        "Am", "am", "Are", "are", "Is", "is", "Be", "be",
        "Had", "had", "Has", "has", "Have", "have",
        "At", "at", "As", "as", "In", "in", 
        "Do", "do",
 
    }));
}
 
protected Collection<String> getNoise() {
 
    return noise;
}
 

A HashSet is a Set and a Set is a Collection. The Arrays.asList() method can
build a List out of an array and a Set can take a List which is also a
Collection as a constructor parameter and that's what is finally returned by
the getNoise() method.

This was enough typing for today; I go get myself some coffee. I hope to see
you in the next fragment of this article part below.

kind regards,

Jos

Part B