Entropy Segmentation

I'm currently working on a model for page segmentation based on entropy. There's a paper already on this using the DOM, but I'm using a visual rendering so it's much more resilient. Anyway, the problem I'm having is that traditional entropy isn't really working for me. Web pages are very, very noisy visually speaking, more so than using a DOM. The goal is to attempt to cluster similar pieces together. If you do a top-down recursive algorithm to determine possible gaps and then apply entropy to pick a gap, at some point you end up favoring a split that reduces overall noise as opposed to clustering similar objects. An example is in order:

Elements are laid out horizontally on a page in this pattern: XXAXAXAXAXAX. For simplicity, A elements are all the same type of element and X elements have nothing in common at all. Therefore, only A elements are in the same class.

Ideally, we want the algorithm to split on the left side of the first A. This will maximize the order on the right side of the page, or otherwise trap all the As. Doing an entropy measure on the right side of that split (with the sign switched for ease), we get 5/10 lg 5/10 + 5 (1/10 lg 1/10) = 2.66. Now let's compare that with the split at the second A: 4/8 lg 4/8 + 4(1/8 lg 1/8) = 2.5. Apparently here, it's better to split at the second one because we're reducing the number of noise elements in the system. Also, there is no advantage to having larger classes, just less proportional ones.

So I've been playing with different ways of modifying the algorithm. Essentially, you want to make the noise elements worth less in determining entropy.

Reflection-based Visitor

In WebSeer, the program that does my web analysis, the main architecture is based on the concept of visitors analyzing models. So you go to a URL, convert the data stream into a local, easy-to-use object, and then run some analysis depending on the application. If you don't understand what the visitor pattern is, I advise you Google it and come back. I've been using the pattern for five years very heavily so I sort of take it for granted in my writing.

My existing problem is that I have several different types of visitors that are used for different purposes. So let's create an example - say I have a graph based model of something, with types Graph, Node, and Edge. Then I have a GraphVisitor that has three methods: visit(Graph), visit(Node), and visit(Edge). The accept methods in Graph, Node, and Edge take care of the default traversal. Now conveniently, I can print out all the edges in the graph or something else without having to care about the actual graph structure in my visitor code. Great...simple visitor pattern.

Now in my library, I have several different types of models, lets say I have another one that's Tree. Both Tree and Graph inherit the Model interface. Now I want to create a visitor that visits a list of Models without caring what type they are. We sort of have a problem. I can create a ModelVisitor, add an accept(ModelVisitor) method in the Model interface, and then check the type of the ModelVisitor and if it's also a GraphVisitor for instance, then do the component traversal. But that's messy. For the last long while, that's what I've been doing. However, in more interesting cases, it gets silly. You have to write accept methods for every type of visitor that could visit the node. Being as this is a visitor-centric architecture, this gets ridiculous even with inheritance. For instance, my TextNodeImpl class recently looked like:

public class TextNodeImpl implements TextNode {

    ...

    public void accept(TextVisitor visitor) {
        visitor.visit(this);
    }

    public void accept(DataSourceVisitor visitor) {
        visitor.visit(this);
    }

    public void accept(TreeVisitor visitor) {
        visitor.visit(this);
    }

    public void accept(MutableTextVisitor visitor) {
        visitor.visit(this);
    }

}

Kinda crazy, right?

A while back I played around with reflection-based visitors, but I think I took it way too far (I also made the accepting objects reflection-based) and it got hard to understand because there was very little type-checking. However, I revisited it last night and I think I found a good balance.

All the visitors implement the SuperVisitor interface. You can either use a more type-safe generics version:

public interface SuperVisitor {

    public boolean canVisit(Class<?> dataClass);

    public <T> DataSourceVisitor<T> 
                  getVisitor(Class<T> dataClass);

}

where DataSourceVisitor just has one "visit(T object) " method.

or the more handy and yet not as clean way:

public interface SuperVisitor {

    public void visit(Object object);

}

where the visitor will attempt to visit any object and just fail quietly if it can't.

Then in AbstractSuperVisitor which takes care of the reflection, you initialize a Map with a mapping of requested Class to DataSourceVisitor. It initially puts in all the visit methods that are found in the runtime class. Then when a visitor for a particular runtime class is requested, you walk up the class hierarchy tree to find the appropriate visit method(s) that has already been initialized. Then you insert that new mapping into the tree. This caching is necessary to cut down lookup time, since reflection is pretty slow. And while this does create an extra object for each visit method, plus a Map for every Visitor pattern, you rarely have so many visitors that this would matter too much. So the primary cost is the cost of reflection based invocation. If this cost is important, I advise you look into articles that discuss how to replace reflection with byte code generation, which would work perfectly here.

So what this allows is that I can now create a Visitor that can visit any type of object on the fly. Let's say I want to print out everything this visitor comes across. Just put in a visit(Object o) method with a print line in the method and all the visit calls will be resolved to this method.

In addition, I now only need a single accept method in all my model classes, which calls the generic visit on itself and then passes the visitor to its components.

public class Graph {

   ...

   public void accept(SuperVisitor visitor) {
      visitor.visit(this);

      for (Edge edge : edges) {
         edge.accept(visitor);
      }
   }

}

The design loss is in the loss of cohesion between the visitor and the things it's visiting. However, this can be mitigated by still using particular visitor interfaces that are sort of fake visitor guidelines for methods it should implement. So I can still have a GraphVisitor which enforces some methods on the visitor implementation, however, the Graph object will only see it as a SuperVisitor.

Overall, I think this is a neat solution to a model-based architecture where you have a lot of visitors interesting in different aspects of complex models. I also added a preVisit and a postVisit which gives me more control over post-children processing for instance. Hopefully this will be a good enough model for WebSeer.