Lemmatisation

I learned a new term today: "Lemmatisation".

I was in a video conference talking about searching Video On Demand content from a set top box. The company providing the server side indexing system mentioned the concept of "Lemmatisation and Stemming" in passing without any explanation. So...I did a little research and found that this term is used in the linguistics area of artificial intelligence.

Lemmatisation takes a sentence (or any sequence of words) and parses it identifying the part of speech (noun, adverb, etc.) of each word and then reduces the word to its base (cannonical) meaning. For example go, goes, going, and went would all be replaced by "go". Because the analyzer requires a knowledge of the grammar being used different languages require different parsers.

Stemming just removes any common pre/post fixes to get to the root meaning of the word. This is a much simpler form of lemmatisation because it doesn't need to analyze any context nor does it care about language grammar.

In the Video On Demand example, the searchable text and the search string will be lemmatised to reduce the potential dictionary of search terms and make fuzzy connections between what is explicitly being requested and what is being returned.

Pretty powerful stuff.

The Registrar Idiom

Goal

To construct/create objects without hard-coding the class name in the code.

Motivation

I heard that this sort of technique was used by the developers of the AS/400 OS to introduce new printer drivers at runtime. One of the complaints of an old version was the length of time required to install new drivers, so when IBM re-wrote the OS in C++ one of the goals was to have a dynamic run time registration system for new hardware drivers. The developers used this idiom to accomplish that requirement.

C++ vs Java

This is much simpler to do in Java with the static code block facility that is executed when the .class file is loaded by the VM. The solution below details how to accomplish this Idiom in C++, doing the same in Java is omitted for brevity.

Solution

• Add a clone() method to all classes (The 'Virtual Copy Constructor?' Idiom)
• Create a Map instance to use as a registry for all the subclasses of Thing
  • This must use 'construct on first use' semantics
  • This should be a static member of the base class, so the Registrar is referenced as Thing::registrar()
• 'Ugly' code can populate the registry with hard-coded or well known subclasses of 'Thing' as follows
  

  
  Thing::registrar()["ThingA"] = new ThingA();
  Thing::registrar()["ThingB"] = new ThingB();
  ... (one per derived class)
  



• The original goal is achieved as now the following works:
  

  
  String className = ...;
  Thing *t = Thing.getThing(className);
  
  where
  
  Thing* Thing::getThing(String className)
  {
   return Thing::registrar()[className]->clone();
  }
  



• OPTIONAL:
  
  • Use the constructor of a static object in the derived class to populate the registry
  
  
  • If the registry doesn't contain className, then getThing can try to dynamically load a library that could contain the new derived class and then retry querying the registry.
  
  

Example

Shape.h

class Shape
{
public:
  ...
  virtual Shape* clone() const = 0;
  Shape* getShape(String& name);
  ...

protected:
  ...
  static Map& registrar();
  ...
  class Registrarer {
    public:
       Registrarer(String className, Shape* prototype);
  };
  ...

private:
  ...
};

Shape.cpp

Map& Shape::registrar()
{
 static Map* registry = new Map;
 return *registry;
}

Shape* Shape::getShape(String& name)
{
 if (!registrar().containsKey(className))
 {
    String DLLName = className + ".DLL";
    // try to load DLL containing the requested shape...
    ...
    if (!registrar().containsKey(className))
       throw Exception("Can't find: " + className);
 }
 return registrar()[className]->clone();
}

...

Shape::Registrarer(String className, Shape* prototype)
{
 Shape::registrar()[className] = prototype;
}

...

Circle.cpp (note no .h is necessary)

class Circle : public Shape
{
public:
 ...
 virtual Shape* clone() const;
 ...

private:
 ...
 static Shape::Registrarer reg_;
 ...
};

// Automatically add myself to the Shape registry
Shape::Registarer Circle::reg_("Circle", new Circle());

...

Massed Gadgets of Hercules

Google is a pretty fantastic outfit these days. They offer so many different products other than search it's hard to keep track . Here are some I use:

• Analytics - to track if anyone is actually reading this blog
• Blogger - this blog (duh)
• Gmail - awesome web based mail
• Desktop - client side search and more
• Gmail Alerts - automatic email when google news sees a phrase I've registered
• Calendar - web based outlook type calendar
• Page Creator - my homepage
• Personalized Home - replacement google main page with lots of web content at a glance
• Talk - IM client - don't really use this but I have an account
• Google Maps - my first choice for getting directions
• Google Video - almost as good as YouTube - but now that's part of Google
• Froogle - comparison web shopping

Other products I've heard about but haven't used yet

• Docs and Spreadsheets
• AdSense
• Google Earth
• Picasa - photo app

And I'm sure there's plenty more.

What Shall We Do Now?

Part of my role at work is ‘software architecture’ which is a somewhat nebulous term and often crosses in to software design. In an agile environment it can’t cross that boundary, however, because it is up to the teams delivering the feature to buy into and create the design for the software. So with the help of the book “Software Systems Architecture” we’re now defining the architecture as a process to find unwritten requirements, constraints, questions, and assumptions that will restrict the design space to only those designs that meet all the criteria and constraints.

The book is quite good, although it is written from a more ‘waterfall’ type mentality. The ideas it presents are geared towards how to effectively communicate an architecture. The authors present a set of six distinct 'views' of the system. Each view is targeted at a different set of stakeholders (which may include the end user, operators, developers, installers, third party developers, etc.) and the intent is to present only the information the stakeholder cares about in the view. The book describes a template for each view including examples of what one is to consider, a checklist, and a section of common mistakes and pitfalls which is quite useful.

The views they describe are:

• Functional: Describes the systems functional elements, their responsibilities, interfaces and primary interactions
• Information: Describes how the system stores, manipulates, manages and distributes data
• Concurrency: Maps functional elements to concurrency units to identify where parallelism can and will occur
• Development: Describes how the architecture supports the development process including building, testing, and maintaining the system
• Deployment: Describes the target environment into which the architecture will be deployed including processing nodes, network interconnections, bandwidth availability, and disk storage requirements
• Operational: Describes how the system will be operated, administered, upgraded and supported after initial deployment.

In addition to the viewpoints, the authors identified some common non-functional qualities of a system and recognized that meeting those qualities will affect more than one view. These qualities include things like performance, security, availability, and scalability. For each of these qualities there is an associated Perspective that the book outlines.

So I'm experimenting with this format by trying to describe a current feature (EPG Data Delivery) along with an upcoming required enhancement to that feature. We'll see how it goes...