Match! Boardgame about the heuristics in data matching(?)

This morning I was enjoying a bit of Good Clean Family Christmas TV You Can Trust and one of the subjects covered was a new Danish board game that you could spend your Christmas vacation playing. It's called Match! and here I will try to outline the rules as I understand them:

• Each player has 3 game cards with a picture of something on their hand.
• A picture is shown to all players and they now has to match that picture with one of the pictures on their hand.
• In the example shown on the TV there was a picture of some sausages on a grill. The example matches of the three players where:
  • Danish politician Pia Kjærsgaard - both she and the sausages represent something very danish and something they'd like to put on a grill!
  • A used roll of toilet paper - related to a different kind of "sausage"!
  • A crowd at a musical festival - a place where you'd love to eat a grilled sausage.

The matches themselves where not the best I've seen but they do point out an important feature of a good matching engine: Using simple similarity checks is not enough. You need to understand not only the spelling, phonetics etc. of the things you are trying to match, but also the semantics. Of course a good example of this in Denmark is our country's biggest company: "Maersk", which can rather easily be matched with "Mærsk" but it's more difficult to get the synonym "A.P. Møller" into the matching rules except if you hardcode it somehow. And if matching goes beyond just names other associative matching rules might apply.

Well... Can't wait to play Match! It sounds like a fun game and it will definately be in the back of my head to try and record some of the interesting heuristics applied there.

Pattern finder 2.0 - the latest feature in DataCleaner

I'm happy to be able to present a feature in this blog post that I know a lot of you have been asking for: A new and improved "Pattern finder" (as known in DataCleaner).

The new Pattern finder works similarly to the old one. The new thing is that it supports a wide variety of configuration options (and it has been designed so that it will be significantly easier to add more options, if needed). Here are the current available options:

Property	Default value	Description
Discriminate text case	true	Sets whether or not text tokens that are upper case and lower case should be treated as different types of tokens.
Discriminate negative numbers	false	Sets whether or not negative numbers should be treated as different token types than positive numbers.
Discriminate decimals	true	Sets whether or not decimal numbers should be treated as different token types than integers.
Enable mixed tokens	true	Enables the "mixed" token type (denoted as '?' output). This type of token will occur when numbers and letters occur without separation of whitespaces.
Ignore repeated spaces	false	Sets whether or not repeated whitespaces should be ignored (ie. matched with single whitespaces)
Decimal separator	,*	The separator used to identify decimal numbers.
Thousands separator	.*	The character used as a thousands separator in large numbers.
Minus sign	-*	The character used to denote negative numbers.
Predefined token name	(none)	Can be used to define an anticipated "predefined token" that should be replaced before any subsequent pattern recognition. Requires that the "Predefined token regexes" property is also set. An example of a name could be "Titulation"
Predefined token regexes	(none)	Defines a set of regular expressions for the "predefined token". Requires that the "Predefined token name" property is also set. An example value for these regular expressions could be "[Mr,Mrs,Miss,Mister]" (which would correspond to the "Titulation" name).

* = Depending on locale, the shown value is the typical one.

This may all seem complicated, but rest assured that the default values are reasonable and almost exactly resembles what you would expect from the Pattern finder in DataCleaner (except for the "Discriminate text case" property, which is inherently turned off in DataCleaner).

Here's how it works with a set of different inputs (job title, email, name) and configurations:

> java -jar target/AnalyzerBeans.jar -conf examples/conf.xml -job examples/patternfinder_job.xml 

RESULT:
                            Match count Sample      
Aaaaa Aaa                            17 Sales Rep   
AA Aaaaaaaaa                          2 VP Sales    
Aaaaa Aaaaaaa (AAAA)                  2 Sale Manager (EMEA) 
Aaaaa Aaaaaaa (AAAAA, AAAA)           1 Sales Manager (JAPAN, APAC) 
Aaaaaaaaa                             1 President   


RESULT:
                                  Match count Sample      
aaaaaa.aaa@aaaaaaa[Domain suffix]           4 foo.bar@company.com 
aaaaaaa@aaaaaaaa[Domain suffix]             3 santa@claus.com 


RESULT:
                 Match count Sample      
aaaaaaa aaaaa              4 Jane Doe    
aaaaaaaa, aaaaaa           2 Bar, Foo    
aaa. aaaaaa aaa            1 Mrs. Foobar Foo

Notice that in the email example the two patterns end with "[Domain suffix]". This is because I've registered a corresponding "Predefined token" for this:

<analyzer>
  <descriptor ref="Pattern finder" />
  <properties>
    <property name="Predefined token name" value="Domain suffix" />
    <property name="Predefined token regexes" value="[\.com,\.org]" />
  </properties>
  <input ref="col_email" />
</analyzer>

So now that you've seen the new Pattern finder... Does it meet all your expectations? Let me know if you've got any ideas or unresolved issues!

A nice abstraction over regular expressions

Often when you're developing data profiling, matching or cleansing software, you're dealing with expression matching, typically through regular expressions (regexes). One thing that I find is that it is often a tedious and error-prone task to define and reuse regexes or parts of regexes. In AnalyzerBeans there's a huge need for easier and reusable pattern matching. To counter this requirement I've come up with a helper-class, Named Pattern, which you can use to match and identify tokens in the patterns in a type-safe and easy way. Here's a short example for matching and tokenizing names based on two simple patterns:

//First define an enum with the tokens in the pattern(s)
public enum NamePart { FIRSTNAME, LASTNAME, TITULATION }

// The two patterns
NamedPattern<NamePart> p1 = new NamedPattern("TITULATION. FIRSTNAME LASTNAME", NamePart.class);
NamedPattern<NamePart> p2 = new NamedPattern("FIRSTNAME LASTNAME", NamePart.class);
NamedPattern<NamePart> p3 = new NamedPattern("LASTNAME, FIRSTNAME", NamePart.class);

// notice the type parameter <NamePart> - the match result type is typesafe!
NamedPatternMatch<NamePart> match = p1.match("Sørensen, Kasper");
assert match == null;

match = p2.match("Sørensen, Kasper");
assert match == null;

// here's a match!
match = p3.match("Sørensen, Kasper");
assert match != null;

String firstName = match.get(NamePart.FIRSTNAME);
String lastName = match.get(NamePart.LASTNAME);
String titulation = match.get(NamePart.TITULATION);

All in all I think that the NamedPattern class (and the NamedPatternMatch) in combination with your own enums is a pretty elegant way to do string pattern matching. There's also a way to specify how the underlying regular expression will be built by letting the enum implement the HasGroupLiteral interface.

Developers can dive into the details of these classes and interfaces at the Javadoc / API Documentation for AnalyzerBeans (package org.eobjects.analyzer.util).